Opened 19 months ago

Last modified 18 months ago

#14844 new task

SpecConstr also non-recursive function

Reported by: nomeata Owned by:
Priority: normal Milestone:
Component: Compiler Version: 8.5
Keywords: SpecConstr Cc: sgraf
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

In order to fix the regressions introduced by loopification (#14068), we probably need to get SpecConstr also do something about non-recursive functions.

In a first iteration, we might want to enable it for non-recursive functions straight-away, and see if it fixes the regressions introduced by Loopification.

But if this turns out to be too slow/too expensive, we should try specializing non-recursive local functions if there is only one call-patterns. That ought to be a straight win in all cases anyways.

Change History (10)

comment:1 Changed 19 months ago by simonpj

Keywords: SpecConstr added

comment:2 Changed 19 months ago by sgraf

See also my closing thoughts in Trac:855#comment:12. TLDR; Integrate SpecConstr into the simplifier as a fallback for when the inliner bails out. May even apply to non-recursive bindings, at least when there's only one call pattern.

comment:3 Changed 18 months ago by nomeata

@sgraf, are you actively working on SpecConstr, and if so, is your patch going to help with this (specconstring non-recursive functions)?

comment:4 Changed 18 months ago by nomeata

I have been staring at the SpecConstr code quite a bit now (which is pretty dense, I must say), and am no longer able to say with certainty that SpecConstr only works on recursive functions. In fact, it seems that Note [Local let bindings] implies local non-recursive lets are being specialized! (despite Note [Good arguments] claiming it only works for self-recursive functions…

It seems that specialization for non-recursive functions was added in changeset:99f41975ae61fc919638aa389199b32742332eff by Simon PJ (maybe not all notes were updated to reflect this change)?

comment:5 Changed 18 months ago by nomeata

I stared some more at the code, and learned:

  • Currently, SpecConstr does specialize local non-recursive functions, but not top-level non-recursive functions. Comment in the source code about that: “Oddly, we don't seem to specialise top-level non-rec functions”. This can be fixed in scTopBind.
  • Together with loopification, SpecConstr only specialized everything as before if it is run twice, with a simplification in between. Otherwise, it refuses to specialize the outer non-recursive function because it does not see that its parameters are being scrutinized. I hope this can somehow be fixed in SpecConstr, so that it anticipates the state after simplifications.
Last edited 18 months ago by nomeata (previous) (diff)

comment:6 Changed 18 months ago by nomeata

And here some details on the second point. After the first run of SpecConstr, we have somthing like this

$w$lf_s6DU [InlPrag=NOUSERINLINE[0]]
  :: Double -> Double -> GHC.Prim.Int# -> (# Double, Double #)
[LclId, Arity=3, Str=<L,U(U)><L,U(U)><S,U>m]
$w$lf_s6DU
  = \ (ww_s6AD :: Double)
      (ww_s6AE :: Double)
      (ww_s6AI :: GHC.Prim.Int#) ->
      joinrec {
        $s$l$w$lf_s6Hv :: GHC.Prim.Int# -> GHC.Prim.Double# -> GHC.Prim.Double# -> (# Double, Double #)
        [LclId[JoinId(3)], Arity=3, Str=<L,U><L,U><L,U>]
        $s$l$w$lf_s6Hv (sc_s6Hu :: GHC.Prim.Int#)
                       (sc_s6Ht :: GHC.Prim.Double#)
                       (sc_s6Hs :: GHC.Prim.Double#)
…

        $l$w$lf_X6Ep [Occ=LoopBreaker] :: Double -> Double -> GHC.Prim.Int# -> (# Double, Double #)
        [LclId[JoinId(3)],
         Arity=3,
         RULES: "SC:$l$w$lf0"
                    forall (sc_s6Hu :: GHC.Prim.Int#)
                           (sc_s6Ht :: GHC.Prim.Double#)
                           (sc_s6Hs :: GHC.Prim.Double#).
                      $l$w$lf_X6Ep (GHC.Types.D# sc_s6Hs) (GHC.Types.D# sc_s6Ht) sc_s6Hu
                      = jump $s$l$w$lf_s6Hv sc_s6Hu sc_s6Ht sc_s6Hs]
        $l$w$lf_X6Ep (ww_X6B9 [Dmd=<L,U(U)>] :: Double)
                     (ww_X6Bb [Dmd=<L,U(U)>] :: Double)
                     (ww_X6Bg [Dmd=<S,U>] :: GHC.Prim.Int#)
…
            }; } in
      jump $l$w$lf_X6Ep ww_s6AD ww_s6AE ww_s6AI
…
…
…
                                             case $w$lf_s6DU
                                                    (GHC.Types.D# (GHC.Prim.cosDouble# wild2_a5jY))
                                                    (GHC.Types.D# (GHC.Prim.sinDouble# wild2_a5jY))
                                                    wild_XM
                                             of

We can clearly see that $w$lf_s6DU has been loopified, with a local joinrec $l$w$lf_X6Ep, and that this local join rec $l$w$lf_X6Ep has been SpecConstr’ed to $s$l$w$lf_s6Hv.

But why does $w$lf_s6DU not get `SpecConstr’ed? Because of

specialise entry {
  $w$lf_s6DU [$w$lf_s6DU (D# (cosDouble# wild2_a5jY))
                         (D# (sinDouble# wild2_a5jY)) wild_XM]
callToPats
  [D# (cosDouble# wild2_a5jY), D# (sinDouble# wild2_a5jY), wild_XM]
  [unk-occ, unk-occ, unk-occ]

which means that it sees the calls passing constructors, but it does not know that the arguments (e.g. ww_s6AD) get scrutinizes, so it does not act on this.

After simplification, however, we have

$w$lf_s6DU [InlPrag=NOUSERINLINE[0]]
  :: Double -> Double -> GHC.Prim.Int# -> (# Double, Double #)
[LclId,
 Arity=3,
 Str=<L,U(U)><L,U(U)><S,U>m,
 RULES: "SC:$w$lf0" [0]
            forall (sc_s6KF :: GHC.Prim.Int#)
                   (sc_s6KE :: GHC.Prim.Double#)
                   (sc_s6KD :: GHC.Prim.Double#).
              $w$lf_s6DU (GHC.Types.D# sc_s6KD) (GHC.Types.D# sc_s6KE) sc_s6KF
              = $s$w$lf_s6KG sc_s6KF sc_s6KE sc_s6KD]
$w$lf_s6DU
  = \ (ww_s6AD :: Double)
      (ww_s6AE :: Double)
      (ww_s6AI :: GHC.Prim.Int#) ->
      joinrec {
        $s$l$w$lf_s6Hv [Occ=LoopBreaker]
          :: GHC.Prim.Int#
             -> GHC.Prim.Double# -> GHC.Prim.Double# -> (# Double, Double #)
…
            }; } in
      case ww_s6AD of ww3_s6DY { GHC.Types.D# ww4_s6DZ ->
      case ww_s6AE of ww5_s6E1 { GHC.Types.D# ww6_s6E2 ->
      case GHC.Prim.remInt# ww_s6AI 2# of {
        __DEFAULT ->
          case ww_s6AI of wild_X11 {
…

i.e. $l$w$lf_X6Ep has been inlined and thus exposed a case analysis of ww_s6AD, and now $w$lf_s6DU gets specialized as expected.

comment:7 Changed 18 months ago by nomeata

I distilled this example to show the effect

module T14844Example (bar1, bar2) where

large x = x
{-# NOINLINE large #-}


foo :: Int -> (a -> b -> Bool) -> (a,b) -> Bool
foo 0 _ _ = False -- to be lazy in t0
foo s f t0 = l s' t0
   where
     l 0 t = False -- to be lazy in t
     l 1 t = case t of (x,y) -> f x y
     l n (x,y) = l (n-1) (x,y) -- repackage tuple, to trigger SpecConstr
     s' = -- To prevent inlining
       large $ large $ large $ large $ large $ large $ large $ large $
       large $ large $ large $ large $ large $ large $ large $ large $
       s

bar1 :: Int -> (a -> b -> Bool) -> a -> b -> Bool
bar1 s f x y = foo s f (x,y)

bar2 :: Int ->  (a -> b -> Bool) -> a -> b -> Bool
bar2 s f x y = foo (s + 1) f (x,y)

This needs to rounds of SpecConstr to specialize foo for the (x,y) call pattern; in the first round, l is specialized, then the (then non-recursive l) gets inlined into foo, then foo gets specialized.

Last edited 18 months ago by nomeata (previous) (diff)

comment:8 Changed 18 months ago by nomeata

So here is an idea that might help here, and that I want to run past people who know SpecConstr well (is that anyone else but SPJ at this point?).

… moved to #14951

Last edited 18 months ago by nomeata (previous) (diff)

comment:9 Changed 18 months ago by sgraf

I'm currently on vacation, so I'm afraid I won't be able to write much code.

I'm not doing anything targeting non-recursive functions, that in itself should be pretty much independent. But given that you seem to have stumbled over the same "phase dependency" problems, here are some notes:

Re: "anticipates the state after simplifications": That's what I figured out, too, and becomes much more crucial once you add lambdas, which does beta-reduction and makes seeing which arguments are scrutinized a little harder. Currently, SpecConstr only gets its ArgOccs (which is a criterion for how deep it's worth to specialise in absence of forced SPEC) only considers the original RHS. Specialised RHS' Occs are never considered, although /calls/ from their RHSs are considered. My plan forward is to revise the fix-pointing scheme in a way that we can translate occurences in specialised RHSs back to occurences on the original RHS' arguments.

In the case of lambdas, this also involves unification of call patterns with bound variables, which is rather nasty and what I've been fiddling with the last weeks.

comment:10 Changed 18 months ago by sgraf

Cc: sgraf added
Note: See TracTickets for help on using tickets.