This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Determine the result of a select based on a dominating condition.
ClosedPublic

Authored by mcrosier on Apr 26 2016, 11:45 AM.

Details

Summary

This patch attempts to determine the result of a select based on a dominating condition. This is similar to what is done in JumpThreading and SimplifyCFG, except those passes only consider conditional branches and not selects.

AFAICT, the transformation in pr21210.ll is safe, but the comments in the lit test seem to indicate otherwise.

@Gerolf - Would you mind helping me better understand what pr21210.ll is trying to test?

I didn't run into any correctness issues with the test-suite or SPEC200X.

This also addresses PR23333.

Please take a look,
Chad

Diff Detail

Repository
rL LLVM

Event Timeline

mcrosier updated this revision to Diff 55054.Apr 26 2016, 11:45 AM
mcrosier retitled this revision from to [InstCombine] Determine the result of a select based on a dominating condition..
mcrosier updated this object.
mcrosier added reviewers: Gerolf, majnemer, sanjoy.
mcrosier added subscribers: llvm-commits, gberry, bmakam, Gerolf.
mcrosier updated this object.Apr 26 2016, 11:53 AM
mcrosier updated this revision to Diff 55068.Apr 26 2016, 12:39 PM
mcrosier updated this object.

@bmakam reminded me that this will also fix PR23333.
-Add a test case accordingly.

Gerolf added inline comments.Apr 26 2016, 5:41 PM
test/Transforms/InstCombine/pr21210.ll
44 ↗(On Diff #55068)

cond can be different from len, so you cannot replace it.
bb-> bb1 vs entry -> b1.

I think this test covers self-build issues I had ran into when I missed some cases in the icmp->select->icmp optimization which removes the select in some narrow cases.

reames requested changes to this revision.Apr 26 2016, 6:33 PM
reames added a reviewer: reames.
reames added a subscriber: reames.

Mostly minor comments, once addressed should be ready to go in.

lib/Analysis/ValueTracking.cpp
3970 ↗(On Diff #55068)

I'm confused by this bit. How do we get here? Do we have a select with a non-i1 condition? If so, maybe the check should be in the caller and we should assert both are i1s?

test/Transforms/InstCombine/pr21210.ll
34 ↗(On Diff #55068)

Add a check that shows this select disappears.

44 ↗(On Diff #55068)

I believe the optimization as posted is correct. Geroff, were you trying to say it wasn't? If so, I didn't understand your point. Could you explain again?

This revision now requires changes to proceed.Apr 26 2016, 6:33 PM
mcrosier updated this revision to Diff 55229.Apr 27 2016, 7:46 AM
mcrosier edited edge metadata.

Address Philip's comments:
-Added CHECK-NOT: select to all test cases
-Move the test case from pr21210.ll into select-implied.ll as I believe we all agree the test case is valid to transform and it isn't likely representative of the problem described in PR21210.
-Added a comment about why we might have a mismatch. In the 30+ examples I reviewed all were cases where we were comparing a scalar cmp against a vector compare. I imagine this case will occur in the future, so I somewhat prefer we keep the check in the callee unless you strongly object.

mcrosier added inline comments.Apr 27 2016, 8:05 AM
test/Transforms/InstCombine/pr21210.ll
25 ↗(On Diff #55229)

I'm not exactly sure how to fix this test case so it exhibits the original problem as I don't fully understand the original problem. Therefore, I move the test case into my new test case. I can file a PR to make sure we follow up on this, but I'd prefer this issue not block this patch.

Gerolf edited edge metadata.Apr 27 2016, 10:43 AM

I sharpened the test case.

-Gerolf

mcrosier updated this revision to Diff 55268.Apr 27 2016, 11:30 AM
mcrosier edited edge metadata.

Update patch now that pr21210.ll has been updated. Thanks, Gerolf.

reames accepted this revision.Apr 29 2016, 1:37 PM
reames edited edge metadata.

LGTM w/optional minor comment.

lib/Transforms/InstCombine/InstCombineSelect.cpp
1219 ↗(On Diff #55268)

Minor, but this would be easier to read as:
if (BasicBlock *Dom = Parent->getSinglePredecessor()) {

auto *PBI = dyn_cast<BranchInst>(Dom->getTerminator());
if (PBI && PBI->isConditional() &&
    PBI->getSuccessor(0) != PBI->getSuccessor(1) &&
    (PBI->getSuccessor(0) == Parent || PBI->getSuccessor(1) == Parent)) {
This revision is now accepted and ready to land.Apr 29 2016, 1:37 PM
This revision was automatically updated to reflect the committed changes.
bmakam added inline comments.May 4 2016, 2:28 PM
test/Transforms/InstCombine/select-implied.ll
84 ↗(On Diff #55229)

D18841 broke this test, because the icmp now can be folded as false. I reverted rL268521 because of this failure.
Is it reasonable to reapply rL268521 by fixing this test to reflect the new change?
So instead of CHECK: %cmp11 = icmp eq i32 %len, 8 we will now have
CHECK-NOT: %cmp11 = icmp eq i32 %{{.*}}, 8
CHECK: br i1 false, label %b0, label %b1