[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 bgamari):

 At this point I'm pretty certain that `bound` for the deep `(:.)`
 instances is the culprit here. For instance, the implementation for
 `((((((((Z :. Int) :. Int) :. A) :. A) :. A) :. A) :. A) :. A)` grows from
 `{terms: 10, types: 59, coercions: 147}` to `{terms: 1,375,016, types:
 1,282,534, coercions: 14,151}` in one simplifier iteration (phase 0).

 Let's follow the specialized implementation of `bound` for `((Z .: Int) :.
 Int) :. Int` which clearly exhibits this explosion, but on a much smaller
 scale (from `{terms: 10, types: 23, coercions: 33}` to `{terms: 2,789,
 types: 2,743, coercions: 78}` over the same simplifier iteration; it's not
 clear that the smaller types are exploding quite as much, namely they
 still have 0 coercions after the simplifier does its work).

 It starts simple enough,

 {{{#!hs
 $s$fShape:._$cbound_sbQv
   :: forall a_aaK6.
      ((Z :. Int) :. Int) :. Int
      -> ((Z :. Int) :. Int) :. Int
      -> Data.Array.Accelerate.Type.Boundary a_aaK6
      -> Either a_aaK6 (((Z :. Int) :. Int) :. Int)
 $s$fShape:._$cbound_sbQv =
   \ (@ a142_abqH)
     (w4_abqI :: ((Z :. Int) :. Int) :. Int)
     (w5_abqJ :: ((Z :. Int) :. Int) :. Int)
     (w6_abqK :: Data.Array.Accelerate.Type.Boundary a142_abqH) ->
     Data.Array.Accelerate.Array.Sugar.$w$cbound
       @ ((Z :. Int) :. Int)
       $s$fElt:._sbKS
       ($s$fShape(,)_sbz9 `cast` ...)
       @ a142_abqH
       w4_abqI
       w5_abqJ
       w6_abqK
 }}}

 This gets simplified to this,
 https://gist.github.com/bgamari/c6e360478b0e98df62e3.

 More analysis shortly.

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