[GHC] #14437: Optimise remainders by powers of two
GHC
ghc-devs at haskell.org
Tue Nov 7 18:44:03 UTC 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
More information about the ghc-tickets
mailing list