Opened 4 years ago

Last modified 2 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 (8)

comment:1 Changed 3 years ago by igloo

  • difficulty set to Unknown
  • Milestone set to 7.8.1

Thanks for the report.

comment:2 Changed 2 years ago by thoughtpolice

  • Milestone changed from 7.8.3 to 7.10.1

Moving to 7.10.1

comment:3 Changed 17 months ago by thomie

  • Cc simonmar added
  • Component changed from Compiler to Compiler (NCG)

comment:4 Changed 16 months ago by thoughtpolice

  • Milestone changed from 7.10.1 to 7.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 8 months ago by thoughtpolice

  • Milestone changed from 7.12.1 to 8.0.1

Milestone renamed

comment:6 Changed 3 months ago by thomie

  • Milestone 8.0.1 deleted

comment:7 Changed 2 months ago by jberryman

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

comment:8 Changed 2 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.

Note: See TracTickets for help on using tickets.