[GHC] #14437: Optimise remainders by powers of two

7 Nov 2017

      #14437: Optimise remainders by powers of two
-------------------------------------+-------------------------------------
           Reporter:  Bodigrim       |             Owner:  (none)
               Type:  feature        |            Status:  new
  request                            |
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.2.1
           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:
-------------------------------------+-------------------------------------
 Current GHC optimises quotients, but not remainders by powers of two. For
 instance, even `even :: Word -> Bool` requires division:

 {{{#!hs
 evenWord :: Word -> Bool
 evenWord = even
 }}}

 results in CMM, containing

 {{{#!c
 if (I64[R1 + 7] % 2 != 0) goto c2sK; else goto c2sQ;
 }}}

 My proposal is to optimise `MO_{S,U}_Rem` by powers of two in
 `CmmOpt.cmmMachOpFoldM`, similar to existing cases for `MO_{S,U}_Quot`.
 Something like this may do:

 {{{#!hs
 MO_U_Rem rep
    | Just _ <- exactLog2 n ->
          Just (cmmMachOpFold dflags (MO_And rep) [x, CmmLit (CmmInt (n -
 1) rep)])
 MO_S_Rem rep
    | Just p <- exactLog2 n ->
           Just (cmmMachOpFold dflags (MO_Sub rep)
             [x, cmmMachOpFold dflags (MO_Shl rep)
               [cmmMachOpFold dflags (MO_S_Quot rep) [x, y], CmmLit (CmmInt
 p rep)]])
 }}}

 Function `even` is used by default definition of `stimes`
 (`Data.Semigroup.Internal.stimesDefault`). If `<>` is cheap, division may
 become a bottleneck.

 It is also used by `GHC.Real.^`. Here is a simple benchmark:

 {{{#!hs
 v :: Int
 v = maximum [ x ^ (6 :: Word)  | x <- [1..100000000 :: Int] ]
 }}}

 It takes 4.5 seconds on my PC before the patch above (`-O2`) and only 2.2
 seconds after.

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