Re: [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
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by autotaker):

 {{{#!hs
 func :: Int -> IO Int
 func n = foldM step 0 xs
     where
     xs = map (n+) [1,2,3]
     step acc x =
         case x `mod` 3  of
             0 -> pure acc
             1 -> pure $ acc + 1
             2 -> pure $ acc + 2
 }}}
 is simplified to the following core code
 {{{
 func n =
     case n + 1 `mod` 3 of
         0 -> case n + 2 `mod` 3 of
             0 -> case n + 3 `mod` 3 of
                 0 -> pure 0
                 1 -> pure 1
                 2 -> pure 2
             1 -> case n + 3 `mod` 3 of
                 0 -> pure 1
                 1 -> pure 2
                 2 -> pure 3
             2 -> case n + 3 `mod` 3 of
                 0 -> pure 2
                 1 -> pure 3
                 2 -> pure 4
         1 -> case n + 2 `mod` 3 of
             0 -> case n + 3 `mod` 3 of
                 0 -> pure 1
                 1 -> pure 2
                 2 -> pure 3
             1 -> case n + 3 `mod` 3 of
                 0 -> pure 2
                 1 -> pure 3
                 2 -> pure 4
             2 -> case n + 3 `mod` 3 of
                 0 -> pure 3
                 1 -> pure 4
                 2 -> pure 5
         2 -> case n + 2 `mod` 3 of
             0 -> case n + 3 `mod` 3 of
                 0 -> pure 2
                 1 -> pure 3
                 2 -> pure 4
             1 -> case n + 3 `mod` 3 of
                 0 -> pure 3
                 1 -> pure 4
                 2 -> pure 5
             2 -> case n + 3 `mod` 3 of
                 0 -> pure 4
                 1 -> pure 5
                 2 -> pure 6
 }}}
 The size of this code is O(3^L^).

 On the other hand, a pure version of `func`, that is
 {{{#!hs
 func' n = foldl step 0 xs
     where
     xs = map (n+) [1,2,3]
     step acc x =
         case x `mod` 3 of
             0 -> acc
             1 -> acc + 1
             2 -> acc + 2
 }}}
 is simplified to the following core code
 {{{
 func' n =
     join j2 w2 =
         join j1 w1 =
             case n + 3  `mod` 3 of
                 0 -> w1
                 1 -> w1 + 1
                 2 -> w1 + 2
         in case n + 2 `mod` 3 of
             0 -> jump j1 w2
             1 -> jump j1 (w2 + 1)
             2 -> jump j1 (w2 + 2)
     in case n + 1 `mod` 3 of
         0 -> jump j2 0
         1 -> jump j2 1
         2 -> jump j2 2
 }}}
 The size of this code is O(L).

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