Re: [GHC] #855: Improvements to SpecConstr

26 Feb 2018

      #855: Improvements to SpecConstr
-------------------------------------+-------------------------------------
        Reporter:  simonpj           |                Owner:  (none)
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:  ⊥
       Component:  Compiler          |              Version:  6.4.2
      Resolution:                    |             Keywords:  SpecConstr
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |            Test Case:  N/A
      Blocked By:                    |             Blocking:  915
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by sgraf):

 This is what I have so far:
 [https://github.com/sgraf812/ghc/compare/8529fbba309cd692bbbb0386321515d05a6e...
 #diff-992f9a53caac96c0e6303669d68a20e1 diff]

 The reason why I couldn't find the lambda's free vars in the `ValueEnv`
 earlier is that the matching
 [https://github.com/sgraf812/ghc/compare/8529fbba309cd692bbbb0386321515d05a6e...
 #diff-992f9a53caac96c0e6303669d68a20e1R2140 argToPat case] didn't add them
 before. That's a problem for our specific case, where the free vars of the
 lambda are bound within the call-pattern, e.g. `Just (let x = 4 in \y. x +
 y)`.

 With that fix in place, the free var values are detected just fine and
 guided by the `ConVal` case I could implement the
 [https://github.com/sgraf812/ghc/compare/8529fbba309cd692bbbb0386321515d05a6e...
 #diff-992f9a53caac96c0e6303669d68a20e1R2180 specialisation code]. From
 what I can tell, the generated specialisation looks great, but it isn't
 called anywhere because now the rules no longer fire.

 My particular solution would just introduce let bindings into the lambda
 body that re-bind things we find to be values (similar to how arguments of
 a data con are handled). Example:

 {{{
 let {
   lvl_s4md = *# sc_s4rb sc_s4rb
   lvl_s4lL = I# lvl_s4md
   lvl_s4ll = Yield @ Bool @ Int False lvl_s4lL } in
 MkStream
   @ Int
   @ Bool
   (\ (ds_d2Fz :: Bool) ->
     case ds_d2Fz of {
       False -> Stop @ Bool @ Int;
       True -> lvl_s4ll
     })
   True

 ==>

 let {
   lvl_s4md = *# sc_s4rb sc_s4rb
   lvl_s4lL = I# lvl_s4md
   lvl_s4ll = Yield @ Bool @ Int False lvl_s4lL } in
 MkStream
   @ Int
   @ Bool
   (\ (ds_d2Fz :: Bool) ->
     let {
       lvl_s4ll = Yield @ Bool @ Int False (I# sc_s4md) } in
     case ds_d2Fz of {
       False -> Stop @ Bool @ Int;
       True -> lvl_s4ll
     })
   True
 }}}

 Kind-of a manual float-in of all bindings we know are values and have
 corresponding `ScrutOcc` (which we ignore at the moment).

 This results in a much better specialisation for `Just (MkStream <lam>
 True)` I believe (`dump-simpl`):

 {{{
 $s$wgo_s4rg :: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# ->
 GHC.Prim.Int#
 $s$wgo_s4rg (sc_s4rf :: GHC.Prim.Int#)
             (sc1_s4re :: GHC.Prim.Int#)
             (sc2_s4rd :: GHC.Prim.Int#)
   = jump $wgo_s4ph
       GHC.Types.SPEC
       (GHC.Prim.+# sc2_s4rd sc_s4rf)
       sc1_s4re
       (GHC.Base.Just
         @ (Stream Int)
         (Main.MkStream
             @ Int
             @ Bool
             (\ (ds_d2Fz :: Bool) ->
               case ds_d2Fz of {
                 False -> Main.Stop @ Bool @ Int;
                 True ->
                   Main.Yield @ Bool @ Int GHC.Types.False (GHC.Types.I#
 sc_s4rf)
               })
             GHC.Types.False));
 }}}

 There's a problem though: That function doesn't get called any more,
 because the corresponding RULE looks like this:

 {{{
 "SC:$wgo2" [0]
   forall (sc_s4rj :: GHC.Prim.Int#)
           (sc_s4rk :: Bool)
           (sc_s4ri :: GHC.Prim.Int#)
           (sc_s4rh :: GHC.Prim.Int#).
     $wgo_s4ph GHC.Types.SPEC
               sc_s4rh
               sc_s4ri
               (GHC.Base.Just
                   @ (Stream Int)
                   (Main.MkStream
                     @ Int
                     @ Bool
                     (\ (ds_d2Fz :: Bool) ->
                         let {
                           sc_s4rf :: GHC.Prim.Int#
                           [LclId]
                           sc_s4rf = sc_s4rj } in
                         let {
                           lvl_s4ll :: Step Bool Int
                           [LclId]
                           lvl_s4ll
                             = Main.Yield
                                 @ Bool
                                 @ Int
                                 GHC.Types.False
                                 (GHC.Types.I# sc_s4rf) } in
                         case ds_d2Fz of {
                           False -> Main.Stop @ Bool @ Int;
                           True -> lvl_s4ll
                         })
                     sc_s4rk))
     = jump $s$wgo_s4rr sc_s4rj sc_s4rk sc_s4ri sc_s4rh
 }}}

 E.g. the extra bindings I introduced obstruct the RULE engine. I can
 probably figure out how to generate the right rules tomorrow.

 Please yell if I'm missing some critical pass or function to do this!

-- 
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/855#comment:17
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler