Use LVI to eliminate conditional branches where we've tested a related condition previously. Update tests for this change.

This fixes PR5652.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@112270 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 41 insertions, 1 deletions

diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 31ca2de..7e00f14 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -656,7 +656,8 @@ LVILatticeVal LVIQuery::getEdgeValue(BasicBlock *BBFrom, BasicBlock *BBTo) {
           
           // Figure out the possible values of the query BEFORE this branch.  
           LVILatticeVal InBlock = getBlockValue(BBFrom);
-          if (!InBlock.isConstantRange()) return InBlock;
+          if (!InBlock.isConstantRange())
+            return LVILatticeVal::getRange(TrueValues);
             
           // Find all potential values that satisfy both the input and output
           // conditions.
diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp
index 8abd842..3d4db28 100644
--- a/lib/Transforms/Scalar/JumpThreading.cpp
+++ b/lib/Transforms/Scalar/JumpThreading.cpp
@@ -669,6 +669,45 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) {
           }
       }
     }
+    
+    // For a comparison where the LHS is outside this block, it's possible
+    // that we've branch on it before.  Used LVI to see if we can simplify
+    // the branch based on that.
+    BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
+    Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1));
+    if (LVI && CondBr && CondConst && CondBr->isConditional() &&
+        (!isa<Instruction>(CondCmp->getOperand(0)) ||
+         cast<Instruction>(CondCmp->getOperand(0))->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 simplify the
+      // branch.
+      // FIXME: We could handle mixed true/false by duplicating code.
+      unsigned Trues = 0, Falses = 0, predcount = 0;
+      for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);PI != PE; ++PI){
+        ++predcount;
+        LazyValueInfo::Tristate Ret =
+          LVI->getPredicateOnEdge(CondCmp->getPredicate(), 
+                                  CondCmp->getOperand(0), CondConst, *PI, BB);
+        if (Ret == LazyValueInfo::True)
+          ++Trues;
+        else if (Ret == LazyValueInfo::False)
+          ++Falses;
+      }
+      
+      // If we can determine the branch direction statically, converted
+      // the conditional branch to an unconditional one.
+      if (Trues && Trues == predcount) {
+        RemovePredecessorAndSimplify(CondBr->getSuccessor(1), BB, TD);
+        BranchInst::Create(CondBr->getSuccessor(0), CondBr);
+        CondBr->eraseFromParent();
+        return true;
+      } else if (Falses && Falses == predcount) {
+        RemovePredecessorAndSimplify(CondBr->getSuccessor(0), BB, TD);
+        BranchInst::Create(CondBr->getSuccessor(1), CondBr);
+        CondBr->eraseFromParent();
+        return true;
+      }
+    }
   }
 
   // Check for some cases that are worth simplifying.  Right now we want to look