Enhance GVN to propagate simple conditionals. This fixes PR3921.

llvm-svn: 68172

1 files changed, 38 insertions, 10 deletions

diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp
index e537986f306..5ce51c74fde 100644
--- a/llvm/lib/Transforms/Scalar/GVN.cpp
+++ b/llvm/lib/Transforms/Scalar/GVN.cpp
@@ -121,6 +121,7 @@ namespace {
       AliasAnalysis* AA;
       MemoryDependenceAnalysis* MD;
       DominatorTree* DT;
+      uint32_t true_vn, false_vn;
   
       uint32_t nextValueNumber;
     
@@ -138,7 +139,14 @@ namespace {
       Expression create_expression(CallInst* C);
       Expression create_expression(Constant* C);
     public:
-      ValueTable() : nextValueNumber(1) { }
+      ValueTable() : nextValueNumber(1) {
+        true_vn = lookup_or_add(ConstantInt::getTrue());
+        false_vn = lookup_or_add(ConstantInt::getFalse());
+      }
+      
+      uint32_t getTrueVN() { return true_vn; }
+      uint32_t getFalseVN() { return false_vn; }
+      
       uint32_t lookup_or_add(Value* V);
       uint32_t lookup(Value* V) const;
       void add(Value* V, uint32_t num);
@@ -1294,9 +1302,27 @@ bool GVN::processInstruction(Instruction *I,
   uint32_t nextNum = VN.getNextUnusedValueNumber();
   unsigned num = VN.lookup_or_add(I);
   
+  if (BranchInst* BI = dyn_cast<BranchInst>(I)) {
+    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
+    
+    if (!BI->isConditional() || isa<Constant>(BI->getCondition()))
+      return false;
+    
+    Value* branchCond = BI->getCondition();
+    uint32_t condVN = VN.lookup_or_add(branchCond);
+    
+    BasicBlock* trueSucc = BI->getSuccessor(0);
+    BasicBlock* falseSucc = BI->getSuccessor(1);
+    
+    localAvail[trueSucc]->table.insert(std::make_pair(condVN,
+                                                      ConstantInt::getTrue()));
+    localAvail[falseSucc]->table.insert(std::make_pair(condVN,
+                                                      ConstantInt::getFalse()));
+    return false;
+    
   // Allocations are always uniquely numbered, so we can save time and memory
-  // by fast failing them.
-  if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) {
+  // by fast failing them.  
+  } else if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) {
     localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
     return false;
   }
@@ -1405,18 +1431,11 @@ bool GVN::runOnFunction(Function& F) {
 
 
 bool GVN::processBlock(BasicBlock* BB) {
-  DomTreeNode* DTN = DT->getNode(BB);
   // FIXME: Kill off toErase by doing erasing eagerly in a helper function (and
   // incrementing BI before processing an instruction).
   SmallVector<Instruction*, 8> toErase;
   bool changed_function = false;
   
-  if (DTN->getIDom())
-    localAvail[BB] =
-                  new ValueNumberScope(localAvail[DTN->getIDom()->getBlock()]);
-  else
-    localAvail[BB] = new ValueNumberScope(0);
-  
   for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
        BI != BE;) {
     changed_function |= processInstruction(BI, toErase);
@@ -1607,6 +1626,15 @@ bool GVN::performPRE(Function& F) {
 bool GVN::iterateOnFunction(Function &F) {
   cleanupGlobalSets();
 
+  for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()),
+       DE = df_end(DT->getRootNode()); DI != DE; ++DI) {
+    if (DI->getIDom())
+      localAvail[DI->getBlock()] =
+                   new ValueNumberScope(localAvail[DI->getIDom()->getBlock()]);
+    else
+      localAvail[DI->getBlock()] = new ValueNumberScope(0);
+  }
+
   // Top-down walk of the dominator tree
   bool changed = false;
 #if 0