Page MenuHomePhabricator

Added InstCombine for ((1 << X) & C) pattern
ClosedPublic

Authored by dinesh.d on May 8 2014, 8:01 AM.

Details

Summary

Basically this patch transforms
(1 << X) & C -> (X == lg(C)) ? (1 << X) : 0, if C is Power of 2
(1 << X) & C -> (X < lg(C+1)) ? (1 << X) : 0, if C + 1 is Power of 2

This patch can handles following cases from http://nondot.org/sabre/LLVMNotes/InstCombine.txt

if (!((1 << which_alternative) & 0x3)) --> if (which_alternative >= 2)

if (((1 << which_alternative) & 0x7)) --> if (which_alternative < 3)

I need suggestion regarding this

  1. Names for comp and select instruction, for now, it is getting set automatically.
  2. Do we have to have check if X is not greater than the bit-width
  3. If check for the last of added test-case is ok.

Diff Detail

Repository
rL LLVM

Event Timeline

dinesh.d updated this revision to Diff 9223.May 8 2014, 8:01 AM
dinesh.d retitled this revision from to Added InstCombine for ((1 << X) & C) pattern.
dinesh.d updated this object.
dinesh.d edited the test plan for this revision. (Show Details)
dinesh.d added reviewers: nadav, rafael, chandlerc.
dinesh.d updated this object.
dinesh.d added a subscriber: Unknown Object (MLST).
dinesh.d updated this revision to Diff 9273.EditedMay 9 2014, 1:49 PM

I have written smt-lib program to verify these transformations.

http://rise4fun.com/Z3/Skhom (verifies ((1 << x) & c) => (x == lg(c))? c : 0, if c is power of 2)
http://rise4fun.com/Z3/p4BF (verifies ((1 << x) & c) => (x == lg(c+1))? (1 << x) : 0, if c+1 is power of 2)

This verification assumes:

  1. c > 0, this case is ensured by existing code, => x & 0 = 0
  2. (1 << x) does not overflow, assumed handled in existing code, (http://reviews.llvm.org/D3371)

Update patch to use c in place of (1 << x) in ICmp in new SelectInst.
Updated test case for (1 << x) & 8, to non 'if' version as there are similar test case in icmp.ll (test17, test19)

bkramer added a subscriber: bkramer.May 9 2014, 3:06 PM

Getting the cases from Chris' note right is great. However, I don't think

(X == lg(C)) ? (1 << X) : 0

is preferable to

(1 << X) & C

in the general case. You're trading a shift + and for icmp + shift + select here. That's more complex and select tends to be an expensive operation. Can you try a more direct way, for example by starting at the icmp operation in instcombine and matching the operands?

Thanks for review. I have tested it for test cases with if(..) and saw that select instruction I introduced is getting combined with select instruction from if statement and resulted code had less instructions.

I agree with you point and will update patch accordingly.

dinesh.d updated this revision to Diff 9286.May 10 2014, 3:00 PM

Updated as per comment

bkramer edited edge metadata.May 31 2014, 5:48 AM

This is going into the right direction, thanks. One minor tweak left.

lib/Transforms/InstCombine/InstCombineCompares.cpp
2542–2550 ↗(On Diff #9286)

I think it would be better to generate an ICMP_UGT directly instead of emitting an ICMP_UGE which is turned into ugt later on.

2589–2597 ↗(On Diff #9286)

Same here.

dinesh.d updated this revision to Diff 9988.May 31 2014, 1:11 PM
dinesh.d edited edge metadata.

Update as per comments.

lib/Transforms/InstCombine/InstCombineCompares.cpp
2542–2550 ↗(On Diff #9286)

done

2589–2597 ↗(On Diff #9286)

This is already using ULT. Updated code to have symmetry with ICMP_EQ case.

bkramer accepted this revision.Jun 1 2014, 7:17 AM
bkramer edited edge metadata.

LGTM

This revision is now accepted and ready to land.Jun 1 2014, 7:17 AM
dinesh.d closed this revision.Jun 2 2014, 1:05 AM
dinesh.d updated this revision to Diff 10008.

Closed by commit rL210007 (authored by dinesh).