Opened 5 years ago

Last modified 3 months ago

#7337 new feature request

GHC does not generate great code for bit-level rotation

Reported by: bos Owned by:
Priority: normal Milestone:
Component: Compiler (NCG) Version: 7.6.1
Keywords: Cc: simonmar
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

I'm working on some hashing functions at the moment, and I notice that GHC generates an or and a pair of shifts for a rotate. The LLVM back end is smart enough to recover the code's intent via strength reduction and emit a single rot instruction, but the regular code generator emits three instructions.

Change History (9)

comment:1 Changed 4 years ago by igloo

difficulty: Unknown
Milestone: 7.8.1

Thanks for the report.

comment:2 Changed 3 years ago by thoughtpolice

Milestone: 7.8.37.10.1

Moving to 7.10.1

comment:3 Changed 3 years ago by thomie

Cc: simonmar added
Component: CompilerCompiler (NCG)

comment:4 Changed 3 years ago by thoughtpolice

Milestone: 7.10.17.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:5 Changed 2 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:6 Changed 19 months ago by thomie

Milestone: 8.0.1

comment:7 Changed 18 months ago by jberryman

For my uses (also hashing) a uncheckedRotateL# :: Word# -> Int# -> Word# would be sufficient.

comment:8 Changed 18 months ago by jberryman

FWIW I'm trying my hand at this, though it may take me a while as it's my first time working on GHC, and I'm not sure how much time I'll have to spend.

It looks like I can take my lead from the byteswap patches (git show 5ae238504 da7db19 1c5b0511 c5d5e3ac 86ca77ecb). Also I'm considering just implementing a rotateR primop since that's what ARM supports (I think) and my use case only has constant rotate values which I know GHC would simplify to a single instruction if Data.Bits.rotateL was implemented in terms of the rotateR primop. Hm, but that would be extra bad for people who have variable left rotate values which also might be 0, because they's need to do a AND mask and a subtraction.

comment:9 Changed 3 months ago by bgamari

Any progress on this?

Note: See TracTickets for help on using tickets.