Page MenuHomePhabricator

[SimplifyCFG] Constant fold a branch implied by it's incoming edge
ClosedPublic

Authored by reames on Sep 21 2015, 5:34 PM.

Details

Summary

The most common use case is when eliminating redundant range checks in an example like the following:
c = a[i+1] + a[i];

For the moment, the implies function only handles a single simple case. I plan to extend this function to handle more complex examples, but I wanted to separate a single transform based on it to make review easy. I'll also be implementing a profile guided version targeted at removing range checks in (a[i] + a[i+1]) as well. That will follow in a later patch.

In terms of code placement/testing, do folks think it would make sense to implement the implies function in InstructionSimplify? You can phrase an implication question as icmpa <= icmpb. Having it in InstSimpify would make it easier to test, but I'm not sure we actually want to start handling complex implications in InstSimplify. Thoughts?

Diff Detail

Repository
rL LLVM

Event Timeline

reames updated this revision to Diff 35330.Sep 21 2015, 5:34 PM
reames retitled this revision from to [SimplifyCFG] Constant fold a branch implied by it's incoming edge.
reames updated this object.
reames added a subscriber: llvm-commits.
sanjoy edited edge metadata.Sep 21 2015, 5:55 PM

I think it makes sense to put this in InstructionSimplify for now. If it gets too large we can think of moving it into its own LogicUtils.h file.

lib/Transforms/Utils/SimplifyCFG.cpp
2345 ↗(On Diff #35330)

Why not use matchers from PatternMatch.h here? I think that will make the logic a lot more obvious.

I moved the implication logic into SimplifyInstruction and separated that into it's own review (http://reviews.llvm.org/D13074). Once that has gone in, I'll update this review.

reames updated this revision to Diff 37413.Oct 14 2015, 3:53 PM
reames edited edge metadata.

Rebase. Ping. Sanjoy?

reames updated this revision to Diff 37421.Oct 14 2015, 4:27 PM

Fix a minor merge problem I hadn't noticed in the last diff.

sanjoy accepted this revision.Oct 24 2015, 1:06 AM
sanjoy edited edge metadata.

lgtm modulo minor nits

lib/Transforms/Utils/SimplifyCFG.cpp
2515 ↗(On Diff #37421)

I don't think you need to check PBI->getSuccessor(0) != PBI->getSuccessor(1) -- please verify this, but I think getSinglePredecessor (as opposed to getUniquePredecessor) should return nullptr if you have two branches from the same block to BB.

2518 ↗(On Diff #37421)

Since you're not creating vectors of i1s, I think ConstantInt::getTrue(BB->getContext()) should be sufficient.

This revision is now accepted and ready to land.Oct 24 2015, 1:06 AM
This revision was automatically updated to reflect the committed changes.
reames marked an inline comment as done.Oct 28 2015, 8:14 PM
reames added inline comments.
lib/Transforms/Utils/SimplifyCFG.cpp
2515 ↗(On Diff #37421)

After reading the code, I wasn't sure about this. I saw nothing which made it obvious, so I left the code as is.

2518 ↗(On Diff #37421)

Fixed.