[GHC] #16363: Modular constant folding

[GHC]

#16363: Modular constant folding
-------------------------------------+-------------------------------------
        Reporter:  hsyl20            |                Owner:  hsyl20
            Type:  feature request   |               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:                    |
-------------------------------------+-------------------------------------
Description changed by hsyl20:

Old description:

> The following code (taken from #16329):
>
> {{{#!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
>
> 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:
>
> {{{#!hs
> 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
>

> 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
> }}}
>
> Case-folding with modular arithmetic should remove the nesting.
>
> (patch coming)

New description:

 The following code (taken from #16329):

 {{{#!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

 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:

 {{{#!hs
 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


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

 Case-folding with modular arithmetic should remove the nesting.

--

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