Page MenuHomePhabricator

[ARM] Recognize bit-reversal idioms

Authored by jmolloy on Nov 2 2015, 7:36 AM.



ARM's RBIT instruction can be used to implement bit-reversal. This patch uses a similar approach to finding bit reversal patterns as instcombine does to find byteswaps - it expects a sequence of test-and-set operations linked together by ORs:

bitreverse(a) = (test(X, 0) ? set(Y, 31) : 0) | (test(X, 1) ? set(Y, 30) : 0) | ...;

This sequence can be in any order.

We can recognize an entire 32-bit RBIT or any partial bitreverse. Partial bitreverses can be masked together with the original value to take avantage of the RBIT instruction.

Diff Detail


Event Timeline

jmolloy updated this revision to Diff 38920.Nov 2 2015, 7:36 AM
jmolloy retitled this revision from to [ARM] Recognize bit-reversal idioms.
jmolloy updated this object.
jmolloy set the repository for this revision to rL LLVM.
jmolloy added a subscriber: llvm-commits.
meadori added a subscriber: meadori.Nov 2 2015, 8:26 AM

I haven't worked through all the logic yet, but this seems like a very specific optimization. How often have you found that it fires in practice? Any benchmark results?

Also, changing the test case to:

--- test.ll	2015-11-02 10:21:04.000000000 -0600
+++ crash.ll	2015-11-02 10:20:51.000000000 -0600
@@ -11,7 +11,7 @@
   %a.lobit = lshr i32 %a, 31
   %and1 = lshr i32 %a, 29
-  %0 = and i32 %and1, 2
+  %0 = and i32 %and1, 1
   %and6 = lshr i32 %a, 27
   %1 = and i32 %and6, 4
   %and11 = lshr i32 %a, 25

causes the following assert to fire:

Assertion failed: (bitPosition < getBitWidth() && "Bit position out of bounds!")

Any particular reason this is performRBITCombine instead of PerformRBITCombine? The coding standard calls for functions to start with lowercase letters, but it looks like most of the functions in this file are already start with uppercase letters.

arsenm added a subscriber: arsenm.Nov 2 2015, 12:17 PM

Could this be added to DAGCombiner instead with a new generic BITREVERSE node?

Hi Matt,

Sure. That's certainly a possibility. Does your target have a similar instruction?


Hi Matt,

Sure. That's certainly a possibility. Does your target have a similar instruction?


Yes, AMDGPU has a bitreverse instruction

jmolloy accepted this revision.Nov 3 2015, 6:16 AM
jmolloy added a reviewer: jmolloy.


OK, I'll abandon this and work on a target-independent version in InstCombine.



This revision is now accepted and ready to land.Nov 3 2015, 6:16 AM
jmolloy closed this revision.Nov 3 2015, 6:16 AM

I meant close, not accept.