Re: [GHC] #12808: For non-strict code including primitive (Addr#) code, Loop Invariant Code Flow not lifted outside the loop...

9 Dec 2016

      #12808: For non-strict code including primitive (Addr#) code, Loop Invariant Code
Flow not lifted outside the loop...
-------------------------------------+-------------------------------------
        Reporter:  GordonBGood       |                Owner:
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:  8.2.1
       Component:  Compiler          |              Version:  8.0.1
      Resolution:                    |             Keywords:  JoinPoints
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by simonpj):

 * keywords:   => JoinPoints
 * cc: maurerl@… (added)

Comment:

 Interesting.  Looking at comment:12, note the difference between the SLOW
 version:
 {{{
 let nxtc c = if c > top
              then return ()
              else do { ...; nxtc (c+p) }
 in do { nxtc ss; nxtp (p + 1) }
 }}}
 and the FAST version
 {{{
 let nxtc c = if c > top
              then nxtp (p + 1) else do
              else do { ...; nxtc (c+p) }
 in nxtc ss
 }}}
 In SLOW, `nxtc` is represented by a heap-allocated closure, whereas in
 FAST `nxtc` is a join point, and hence not allocated at all (you can see
 that from the `let-no-escape` in the STG).  See our paper
 [https://www.microsoft.com/en-us/research/publication/compiling-without-
 continuations/ Compiling without continuations], and [wiki:SequentCore].

 Notice that in SLOW, the call to `nxtc s` is ''followed by'' a call to
 `nxtp (p+1)`.  But in FAST we move that call right into `nxtc` itself, in
 the return branch of the `if`.  That's what makes `nxtc` into a join
 point.

 (None of this has anything to do with non-strictness, incidentally.)

 This is a rather non-trivial transformation. You clearly think it's a
 pretty obvious optimisation, but it doesn't look obvious to me.

 Happily, though, our new Core-with-join-point (described in the paper)
 should catch this nicely.  If we start with SLOW, after a bit we'll get
 this
 {{{
 let nxtc c s = if c > top
                then (# s,c #)
                else case ... of (# s',p #) -> nxtc (c+p) s' }
 in case nxtc ss s of
      (# s', r #) -> nxtp (p + 1) s' }
 }}}
 Now if we do float-in, to move the `let nxtc` in to the scruintee of the
 case, it becomes a join point, and join-point analysis should find it.
 After that, the transformations in the paper will turn it into FAST.

 The example in comment:10 looks similar:
 {{{
   case doit adr# sp# of sd# -> cullp (p + 2) sd# in cullp 1 s4# }}}}}
 }}}
 Here again, `doit` will become a join point if we float it in.  The
 example in the Descrption is too big for me to analyse.

 I've cc'd Luke Maurer who is implementing Core with join points; this
 looks like another good example.  (cf #12781)

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