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 = evenresults 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 |