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

[GHC]

#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:                    |
-------------------------------------+-------------------------------------

Comment (by GordonBGood):

 Replying to [comment:14 simonpj]:
 > ...

 > 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].

 Yes, I saw that.

 > 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.

 I had wondered if the work on join points might help here...

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

 I just wondered if strictness might be a clue, as the FAST version
 consumes very low heap, whereas the SLOW version takes an amount of heap
 which is about the calculated amount for numLOOPS times the number of
 primes culled...

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

 No, I didn't think it was trivial, just that the optimisation gets
 triggered in the one case; I couldn't see why it couldn't be extended to
 the other...

 > 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.

 Don't worry about the big example in the description as if the small
 example in comment 10 and this latest example in comment 12 get fixed, I'm
 pretty sure it will take core of that larger case too.

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

 That is encouraging news the the Join Point Analysis should catch this.
 Thanks for looking at this, as I think it important in many cases beyond
 this.

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