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

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.

 (patch coming)

--

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