[GHC] #10491: Regression, simplifier explosion with Accelerate, cannot compile, increasing tick factor is not a workaround

[GHC]

#10491: Regression, simplifier explosion with Accelerate, cannot compile,
increasing tick factor is not a workaround
-------------------------------------+-------------------------------------
        Reporter:  robertce          |                   Owner:
            Type:  bug               |                  Status:  new
        Priority:  highest           |               Milestone:  7.10.2
       Component:  Compiler          |                 Version:  7.10.1
      Resolution:                    |                Keywords:
Operating System:  Unknown/Multiple  |            Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |               Test Case:
      Blocked By:                    |                Blocking:
 Related Tickets:                    |  Differential Revisions:
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Interesting!  Looking at
 [​https://github.com/AccelerateHS/accelerate/blob/release/0.15/Data/Array/Accelerate/Array/Representation.hs#L110
 this code] (linked in comment:38), we see that if `bound` is inlined, we
 get ''seven'' new calls to `bound`.   And each of those seven will yield
 seven new ones, and so on.   Very exponential!

 Some thoughts:

  * One could rewrite the linked code to say
 {{{
 ... where bound1 = bound sh ix bndy
 }}}
   and use `bound1` for all seven occurrences of `bound sh ix bndy`.  Does
 that help?

  * If it does, one might have hoped that CSE would catch it.  But GHC's
 current CSE is not very clever.  I have an idea for how to improve it so
 that it ''would'' catch it, if anyone interested in optimisation would
 like to try it out.  RSVP.

  * Use `-ddump-inlinings` to see why HEAD is choosing not to inline it.

  * In general this kind of thing is quite hard to prevent. The classic
 case is
 {{{
  f x = f (x-1) + f (x-2)
 }}}
  but GHC doesn't inline recursive functions, so we are ok.  This case is
 more like
 {{{
  f1 x = f2 (x-1) + f2 (x-2)
  f2 x = f3 (x-1) + f3 (x-2)
  f3 x = f4 (x-1) + f4 (x-2)
  ...etc...
 }}}
  But the successive f's are generated by the nested instance declarations.
 And I tried hard NOT to prevent inlining in these cases becuase it can be
 dramatically better to allow it.  (E.g. look at the definition of
 `fromIndex` at the same link.

  I don't know a good way to trim off unproductive exponential inlinings
 without killing off good inlinings too.

 In short, I don't know a general solution.  But any definition that has a
 seven-way (or even two-way) expansion over a recursive type index is going
 to cause trouble.  Worth looking out for these.

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