This is an archive of the discontinued LLVM Phabricator instance.

CVP: Improve handling of Selects used as incoming PHI values
ClosedPublic

Authored by dotdash on Apr 16 2015, 5:44 AM.

Details

Summary

If the branch that leads to the PHI node and the Select instruction
depend on correlated conditions, we might be able to directly use the
corresponding value from the Select instruction as the incoming value
for the PHI node, allowing later removal of the select instruction.

Diff Detail

Event Timeline

dotdash updated this revision to Diff 23850.Apr 16 2015, 5:44 AM
dotdash retitled this revision from to CVP: Improve handling of Selects used as incoming PHI values.
dotdash updated this object.
dotdash edited the test plan for this revision. (Show Details)
dotdash added a subscriber: Unknown Object (MLST).
dotdash updated this revision to Diff 23899.Apr 17 2015, 2:16 AM

Updated the patch to only apply the optimization to selects with a scalar condition.

FWIW, this helps with an optimization problem we hit with the rust compiler:

https://github.com/rust-lang/rust/issues/24489
reames added a subscriber: reames.Apr 29 2015, 9:41 AM

Seems like a reasonable approach. A couple of small comments, but once those are addressed, should be easy to sign off on.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
115

I don't understand why we need the vector type check? Is this a limitation of LVI? If so, it should be pushed inside the LVI function being called. (i.e. returning Unknown for a vector type is perfectly reasonable)

118

I wonder whether a wrapper function on LVI which just take an ICmpInst would be more clear here. The comparison of against true is slightly opaque at first.

test/Transforms/CorrelatedValuePropagation/select.ll
9

A few more tests would be good. In particular:

  • a negative test for the vector case
  • a simple case without the loop to express the idea
  • a negative test for when the select condition *isn't* implied by the branch test.
dotdash added inline comments.Apr 29 2015, 11:23 AM
lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
118

Actually, I can just use getConstantOnEdge, which is easier to read and better at handling the vector types. Not sure what made me think that I could not use that. With the predicate approach, the false case matches all vectors except for the one with all ones, which is why I had excluded the vector types. I'm currently struggling at coming up with a test for the vector types though.

dotdash updated this revision to Diff 24753.Apr 30 2015, 11:25 AM

Updated the patch to use getConstantOnEdge to improve readability. Added a
simpler test case without a loop and a negative test case. LVI doesn't support
vector types yet, so there's no test for that, but I left a note that support
for vector types may be added later.

Could somebody have another look at this?

Thanks!

reames accepted this revision.May 12 2015, 3:31 PM
reames added a reviewer: reames.

LGTM.

This revision is now accepted and ready to land.May 12 2015, 3:31 PM
This revision was automatically updated to reflect the committed changes.