Skip to content
GitLab
Projects Groups Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
  • GHC GHC
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 5,259
    • Issues 5,259
    • List
    • Boards
    • Service Desk
    • Milestones
    • Iterations
  • Merge requests 565
    • Merge requests 565
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
    • Test Cases
  • Deployments
    • Deployments
    • Releases
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Code review
    • Insights
    • Issue
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Glasgow Haskell CompilerGlasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #14437
Closed
Open
Issue created Nov 07, 2017 by Bodigrim@BodigrimDeveloper

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
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Assignee
Assign to
Time tracking