Optimize remainders by powers of two for Integer and Natural

It appears that GHC does not optimise even (n :: Integer) to a bitwise check, as it does for Int and Word (#14437 (closed)). Here is a benchmark:

import Data.Time.Clock

evenRem :: Integer -> Bool
evenRem n = fromIntegral n `rem` 2 == (0 :: Word)

lim :: Integer
lim = 100000000

main :: IO ()
main = do
  t0 <- getCurrentTime
  print $ maximum $ filter even [1..lim]
  t1 <- getCurrentTime
  putStrLn "even"
  print $ diffUTCTime t1 t0

  t0 <- getCurrentTime
  print $ maximum $ filter evenRem [1..lim]
  t1 <- getCurrentTime
  putStrLn "evenRem"
  print $ diffUTCTime t1 t0

$ ghc -O2 Even.hs
[1 of 1] Compiling Main             ( Even.hs, Even.o )
Linking Even ...
$ ./Even
100000000
even
6.367393s
100000000
evenRem
4.35664s

The reason is that even (n :: Integer) results in remInteger call in CMM, which remains unoptimized.

One possible solution is to add a special case of divisor 2 to GHC.Integer.Type.remInteger. Or perhaps even something like

remInteger n (S# d#)
  | isPowerOfTwo (I# d#) = fromIntegral (fromIntegral n `rem` I# d#)

isPowerOfTwo :: Int -> Bool
isPowerOfTwo d = d /= 0 && d .&. (complement d + 1) == d

Since remInteger is not inlined during Core pipeline, such implementation of even will pattern-match in runtime, which is a bit suboptimal. On my machine it benchmarks halfway between even and evenRem above.

Alternative approach is to add new rules to PrelRules.builtinIntegerRules to avoid any possible runtime slowdown. Is is appropriate?

Trac metadata

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