[GHC] #16363: Modular constant folding

25 Feb 2019

      #16363: Modular constant folding
-------------------------------------+-------------------------------------
           Reporter:  hsyl20         |             Owner:  (none)
               Type:  feature        |            Status:  new
  request                            |
           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:
-------------------------------------+-------------------------------------
 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
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler