This is an archive of the discontinued LLVM Phabricator instance.

Teach LVI to look through Phi nodes when trying to prove a predicate
ClosedPublic

Authored by reames on Aug 26 2015, 3:17 PM.

Details

Summary

If asked to prove a predicate about a value produced by a PHI node, LazyValueInfo was unable to do so even if the predicate was known to be true for each input to the PHI. This prevented JumpThreading from eliminating a provably redundant branch.

The problematic test case looks something like this:
ListNode *p = ...;
while (p != null) {

if (!p) return;
x = g->x; // unrelated
p = p->next

}

The null check at the top of the loop is redundant since the value of 'p' is null checked on entry to the loop and before executing the backedge. This resulted in us a) executing an extra null check per iteration and b) not being able to LICM unrelated loads after the check since we couldn't prove they would execute or that their dereferenceability wasn't effected by the null check on the first iteration.

Diff Detail

Event Timeline

reames updated this revision to Diff 33256.Aug 26 2015, 3:17 PM
reames retitled this revision from to Teach LVI to look through Phi nodes when trying to prove a predicate.
reames updated this object.
reames added reviewers: hfinkel, nicholas, sanjoy.
reames added a subscriber: llvm-commits.
sanjoy edited edge metadata.Aug 26 2015, 4:07 PM

This change looks fine to me (minor comments inline); but I'll wait for someone more familiar with this area to take a look.

lib/Analysis/LazyValueInfo.cpp
1288

LLVM style says i = 0, e = getNumIncomingValues(); i != e; i++.

1300

I'd check for "first iteration" using i == 0 instead.

hfinkel accepted this revision.Aug 27 2015, 4:36 PM
hfinkel edited edge metadata.

Aside from the couple of things on which Sanjoy commented, LGTM.

lib/Analysis/LazyValueInfo.cpp
1297

Not really sure it is worth defining a simple one-line lambda function that is only used once, but if you think it makes the code more readable, then I won't object.

This revision is now accepted and ready to land.Aug 27 2015, 4:36 PM
This revision was automatically updated to reflect the committed changes.