[GHC] #16329: Simplifier ticks exhausted when fusioning list literals

16 Feb 2019

      #16329: Simplifier ticks exhausted when fusioning list literals
-------------------------------------+-------------------------------------
           Reporter:  autotaker      |             Owner:  (none)
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.6.3
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 GHC 8.6.3 cannot compile the following code with `-O`.

 {{{#!hs
 module Main10(func) where
 import Control.Monad
 import Data.IORef

 func :: Int -> IO Int
 func n = do
     ref <- newIORef False
     let xs = map (n+) [1,2,3,4,5,6,7,8,9,10]
         step acc x = do
             when (x `mod` 2 == 0) $ modifyIORef' ref not
             pure (acc + 1)
     foldM step 0 xs
 }}}

 {{{
 $ stack ghc -- --version
 The Glorious Glasgow Haskell Compilation System, version 8.6.3
 $ stack ghc -- -O Main10.hs
 [1 of 1] Compiling Main10           ( Main10.hs, Main10.o )
 Simplifier ticks exhausted
   When trying RuleFired +#
   To increase the limit, use -fsimpl-tick-factor=N (default 100).

   If you need to increase the limit substantially, please file a
   bug report and indicate the factor you needed.

   If GHC was unable to complete compilation even with a very large factor
   (a thousand or more), please consult the "Known bugs or infelicities"
   section in the Users Guide before filing a report. There are a
   few situations unlikely to occur in practical programs for which
   simplifier non-termination has been judged acceptable.

   To see detailed counts use -ddump-simpl-stats
   Total ticks: 14321
 }}}
 GHC 8.4.4 and 8.2.2 also fail to compile this but GHC 8.0.2 can.

 I tried `-fsimpl-tick-factor=10000`, then GHC could compile the program
 but quite slow (it took some minutes).

 I measured the total ticks in the dumps from `-ddump-simpl-stats`, while
 changing the length of the constant literal (`[1,2,...,10]`) in the
 program between 3 to 10.
 Here is the result. Simplifier ticks seems to be exponential in the length
 of the constant list.

 {{{
 # length, Total ticks
 3,    706
 4,   1286
 5,   2982
 6,   8026
 7,  23114
 8,  68334
 9, 203950
 10,610754
 }}}

-- 
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16329
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler