Optimise remainders by powers of two

Current GHC optimises quotients, but not remainders by powers of two. For instance, even even :: Word -> Bool requires division:

evenWord :: Word -> Bool
evenWord = even

results in CMM, containing

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:

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:

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.

Trac metadata

Trac field	Value
Version	8.2.1
Type	FeatureRequest
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture