Page MenuHomePhabricator

Added instruction combine to transform few more negative values addition to subtraction (Part 3)
ClosedPublic

Authored by dinesh.d on Jun 19 2014, 5:22 AM.

Details

Summary

First Part: http://reviews.llvm.org/D3733
2nd Part: http://reviews.llvm.org/D4209

This patch enable following transform

(x + (~(y | c) + 1)   -->   x - (y | c) if c is odd
(x + (~((y >> z) | c) + 1)   -->   x - ((y>>z) | c)  if c is odd

Z3 verification code:

http://rise4fun.com/Z3/ZA06

Diff Detail

Repository
rL LLVM

Event Timeline

dinesh.d updated this revision to Diff 10629.Jun 19 2014, 5:22 AM
dinesh.d retitled this revision from to Added instruction combine to transform few more negative values addition to subtraction (Part 3).
dinesh.d updated this object.
dinesh.d edited the test plan for this revision. (Show Details)
dinesh.d added a subscriber: Unknown Object (MLST).
dinesh.d updated this revision to Diff 10820.Jun 24 2014, 11:52 PM

Removed code setting NSW/ NUW flag for now

jingyue edited edge metadata.Jun 25 2014, 8:56 PM

Looks good overall.

I have a more high-level question. Why are these logics in checkForNegativeOperand instead of visitXor? Aren't transformations such as

XOR(AND(Z, ~C), (~C + 1)) => NEG(OR(Z, C))

beneficial even the XOR is not the RHS of an ADD?

lib/Transforms/InstCombine/InstCombineAddSub.cpp
962 ↗(On Diff #10820)

Make sure this TODO goes away after you rebase.

998 ↗(On Diff #10820)

typo "LHS"

1007 ↗(On Diff #10820)
LHS == NOT(AND(Z, ~C2))

is not consistent with previous comments using

NEG(OR(Z, C))

Are they mathematically equivalent? If so, could you make the comments consistent?

test/Transforms/InstCombine/add2.ll
154 ↗(On Diff #10820)

I'd love to see some comments on what math expression these IR instructions compute, and what those magic numbers (e.g., -1431655766) mean.

Same for the next two test cases.

dinesh.d updated this revision to Diff 10879.EditedJun 26 2014, 12:11 AM
dinesh.d edited edge metadata.

I have updated patch for comments with following extra changes.

  1. ADD(XOR(AND(Z, ~C), ~C), 1) == NEG(OR(Z, C)) is true for both if C is even or odd. [http://rise4fun.com/Z3/Pwkf]
  2. Rearranged test cases, generated from following test code

    int test10(int x, int y) { return y + (~((x >> 3) & 0x55555555) + 1); } int test11(int x, int y) { return y + (~(x & 0x55555555) + 1); } int test12(int x, int y) { return (y + 1) + ~(x & 0x55555555); }

    int test13(int x, int y) { return y + (~(x & 0x55555556) + 1); } int test14(int x, int y) { return (y + 1) + ~(x & 0x55555556); }

    int test15(int x, int y) { return y + (~(x | 0x55555556) + 1); } int test16(int x, int y) { return (y + 1) + ~(x | 0x55555556); }

    int test17(int x, int y) { return y + (~(x | 0x55555555) + 1); } int test18(int x, int y) { return (y + 1) + ~(x | 0x55555555); }
dinesh.d added inline comments.Jun 26 2014, 12:12 AM
lib/Transforms/InstCombine/InstCombineAddSub.cpp
962 ↗(On Diff #10820)

sure, will take care of it.

998 ↗(On Diff #10820)

updated.

1007 ↗(On Diff #10820)

updated.

test/Transforms/InstCombine/add2.ll
154 ↗(On Diff #10820)

updated

I have a more high-level question. Why are these logics in checkForNegativeOperand instead of visitXor? Aren't transformations such as
XOR(AND(Z, ~C), (~C + 1)) => NEG(OR(Z, C))
beneficial even the XOR is not the RHS of an ADD?

NEG(X) gets converted to XOR.

NEG(X) = XOR(x, -1) + 1

So it is not useful to transform XOR(..) to NEG(..) and it will loop infinitely.

jingyue accepted this revision.Jun 26 2014, 11:22 AM
jingyue edited edge metadata.
This revision is now accepted and ready to land.Jun 26 2014, 11:22 AM
dinesh.d closed this revision.Jun 27 2014, 12:55 AM
dinesh.d updated this revision to Diff 10916.

Closed by commit rL211881 (authored by dinesh).