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

[reames]

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.

[sanjoy]

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]

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.

lib/Analysis/LazyValueInfo.cpp

LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
   Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
   if (Ret != Unknown)
     return Ret;
 
   // TODO: Move this logic inside getValueAt so that it can be cached rather
   // than re-queried on each call.  This would also allow us to merge the
   // underlying lattice values to get more information 
   if (CxtI) {
+    BasicBlock *BB = CxtI->getParent();
+
+    // Function entry or an unreachable block.  Bail to avoid confusing
+    // transforms below.
+    pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+    if (PI == PE)
+      return Unknown;
+
+    // If V is a PHI node in the same block as the context, we need to ask
+    // questions about the predicate as applied to the incoming value along
+    // each edge. This is useful for eliminating cases where the predicate is
+    // known along all incoming edges.
+    if (auto *PHI = dyn_cast<PHINode>(V))
+      if (PHI->getParent() == BB) {
+        Tristate Baseline = Unknown;
+        for (unsigned i = 0; i < PHI->getNumIncomingValues(); i++) {
+          Value *Incoming = PHI->getIncomingValue(i);
+          BasicBlock *PredBB = PHI->getIncomingBlock(i);
+          // Note that PredBB may be BB itself.        
+          Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
+                                               CxtI);
+
+          // Keep going as long as we've seen a consistent known result for
+          // all inputs. 
+          auto mergeResults = [](Tristate Baseline, Tristate Result) {
+            return Baseline == Result ? Baseline : Unknown;
+          };
+          Baseline = (Baseline == Unknown) ? Result /* First iteration */
+            : mergeResults(Baseline, Result); /* All others */
+          if (Baseline == Unknown)
+            break;
+        }
+        if (Baseline != Unknown)
+          return Baseline;
+      }
+    
     // For a comparison where the V is outside this block, it's possible
     // that we've branched on it before.  Look to see if the value is known
     // on all incoming edges.
-    BasicBlock *BB = CxtI->getParent();
-    pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
-    if (PI != PE &&
-        (!isa<Instruction>(V) ||
+    if ((!isa<Instruction>(V) ||
          cast<Instruction>(V)->getParent() != BB)) {
       // For predecessor edge, determine if the comparison is true or false
       // on that edge.  If they're all true or all false, we can conclude 
       // the value of the comparison in this block.
       Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
       if (Baseline != Unknown) {
         // Check that all remaining incoming values match the first one.
         while (++PI != PE) {

test/Transforms/JumpThreading/phi-known.ll

+; RUN: opt -S -jump-threading %s | FileCheck %s
+
+; Value of predicate known on all inputs (trivial case)
+; Note: InstCombine/EarlyCSE would also get this case
+define void @test(i8* %p, i8** %addr) {
+; CHECK-LABEL: @test
+entry:
+  %cmp0 = icmp eq i8* %p, null
+  br i1 %cmp0, label %exit, label %loop
+loop:
+; CHECK-LABEL: loop:
+; CHECK-NEXT: phi
+; CHECK-NEXT: br label %loop
+  %p1 = phi i8* [%p, %entry], [%p1, %loop]
+  %cmp1 = icmp eq i8* %p1, null
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Value of predicate known on all inputs (non-trivial)
+define void @test2(i8* %p) {
+; CHECK-LABEL: @test2
+entry:
+  %cmp0 = icmp eq i8* %p, null
+  br i1 %cmp0, label %exit, label %loop
+loop:
+  %p1 = phi i8* [%p, %entry], [%p2, %backedge]
+  %cmp1 = icmp eq i8* %p1, null
+  br i1 %cmp1, label %exit, label %backedge
+backedge:
+; CHECK-LABEL: backedge:
+; CHECK-NEXT: phi
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: load
+; CHECK-NEXT: cmp
+; CHECK-NEXT: br 
+; CHECK-DAG: label %backedge
+  %addr = bitcast i8* %p1 to i8**
+  %p2 = load i8*, i8** %addr
+  %cmp2 = icmp eq i8* %p2, null
+  br i1 %cmp2, label %exit, label %loop
+exit:
+  ret void
+}
+
+; If the inputs don't branch the same way, we can't rewrite
+; Well, we could unroll this loop exactly twice, but that's
+; a different transform.
+define void @test_mixed(i8* %p) {
+; CHECK-LABEL: @test_mixed
+entry:
+  %cmp0 = icmp eq i8* %p, null
+  br i1 %cmp0, label %exit, label %loop
+loop:
+; CHECK-LABEL: loop:
+; CHECK-NEXT: phi
+; CHECK-NEXT: %cmp1 = icmp
+; CHECK-NEXT: br i1 %cmp1
+  %p1 = phi i8* [%p, %entry], [%p1, %loop]
+  %cmp1 = icmp ne i8* %p1, null
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  ret void
+}
+