Give GVN back the ability to perform simple conditional propagation on conditional branch values.

I still think that LVI should be handling this, but that capability is some ways off in the future,
and this matters for some significant benchmarks.


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

2 files changed, 137 insertions, 52 deletions

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index 094c50f..dcab962 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -657,46 +657,52 @@ namespace {
     
     /// NumberTable - A mapping from value numers to lists of Value*'s that
     /// have that value number.  Use lookupNumber to query it.
-    DenseMap<uint32_t, std::pair<Value*, void*> > NumberTable;
+    struct NumberTableEntry {
+      Value *Val;
+      BasicBlock *BB;
+      NumberTableEntry *Next;
+    };
+    DenseMap<uint32_t, NumberTableEntry> NumberTable;
     BumpPtrAllocator TableAllocator;
     
     /// insert_table - Push a new Value to the NumberTable onto the list for
     /// its value number.
-    void insert_table(uint32_t N, Value *V) {
-      std::pair<Value*, void*>& Curr = NumberTable[N];
-      if (!Curr.first) {
-        Curr.first = V;
+    void insert_table(uint32_t N, Value *V, BasicBlock *BB) {
+      NumberTableEntry& Curr = NumberTable[N];
+      if (!Curr.Val) {
+        Curr.Val = V;
+        Curr.BB = BB;
         return;
       }
       
-      std::pair<Value*, void*>* Node =
-        TableAllocator.Allocate<std::pair<Value*, void*> >();
-      Node->first = V;
-      Node->second = Curr.second;
-      Curr.second = Node;
+      NumberTableEntry* Node = TableAllocator.Allocate<NumberTableEntry>();
+      Node->Val = V;
+      Node->BB = BB;
+      Node->Next = Curr.Next;
+      Curr.Next = Node;
     }
     
     /// erase_table - Scan the list of values corresponding to a given value
     /// number, and remove the given value if encountered.
-    void erase_table(uint32_t N, Value *V) {
-      std::pair<Value*, void*>* Prev = 0;
-      std::pair<Value*, void*>* Curr = &NumberTable[N];
+    void erase_table(uint32_t N, Value *V, BasicBlock *BB) {
+      NumberTableEntry* Prev = 0;
+      NumberTableEntry* Curr = &NumberTable[N];
 
-      while (Curr->first != V) {
+      while (Curr->Val != V || Curr->BB != BB) {
         Prev = Curr;
-        Curr = static_cast<std::pair<Value*, void*>*>(Curr->second);
+        Curr = Curr->Next;
       }
       
       if (Prev) {
-        Prev->second = Curr->second;
+        Prev->Next = Curr->Next;
       } else {
-        if (!Curr->second) {
-          Curr->first = 0;
+        if (!Curr->Next) {
+          Curr->Val = 0;
+          Curr->BB = 0;
         } else {
-          std::pair<Value*, void*>* Next =
-            static_cast<std::pair<Value*, void*>*>(Curr->second);
-          Curr->first = Next->first;
-          Curr->second = Next->second;
+          NumberTableEntry* Next = Curr->Next;
+          Curr->Val = Next->Val;
+          Curr->BB = Next->BB;
         }
       }
     }
@@ -1837,28 +1843,26 @@ bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) {
 // question.  This is fast because dominator tree queries consist of only
 // a few comparisons of DFS numbers.
 Value *GVN::lookupNumber(BasicBlock *BB, uint32_t num) {
-  std::pair<Value*, void*> Vals = NumberTable[num];
-  if (!Vals.first) return 0;
-  Instruction *Inst = dyn_cast<Instruction>(Vals.first);
-  if (!Inst) return Vals.first;
-  BasicBlock *Parent = Inst->getParent();
-  if (DT->dominates(Parent, BB))
-    return Inst;
+  NumberTableEntry Vals = NumberTable[num];
+  if (!Vals.Val) return 0;
   
-  std::pair<Value*, void*>* Next =
-    static_cast<std::pair<Value*, void*>*>(Vals.second);
+  Value *Val = 0;
+  if (DT->dominates(Vals.BB, BB)) {
+    Val = Vals.Val;
+    if (isa<Constant>(Val)) return Val;
+  }
+  
+  NumberTableEntry* Next = Vals.Next;
   while (Next) {
-    Instruction *CurrInst = dyn_cast<Instruction>(Next->first);
-    if (!CurrInst) return Next->first;
-    
-    BasicBlock *Parent = CurrInst->getParent();
-    if (DT->dominates(Parent, BB))
-      return CurrInst;
+    if (DT->dominates(Next->BB, BB)) {
+      if (isa<Constant>(Next->Val)) return Next->Val;
+      if (!Val) Val = Next->Val;
+    }
     
-    Next = static_cast<std::pair<Value*, void*>*>(Next->second);
+    Next = Next->Next;
   }
 
-  return 0;
+  return Val;
 }
 
 
@@ -1888,7 +1892,7 @@ bool GVN::processInstruction(Instruction *I,
 
     if (!Changed) {
       unsigned Num = VN.lookup_or_add(LI);
-      insert_table(Num, LI);
+      insert_table(Num, LI, LI->getParent());
     }
 
     return Changed;
@@ -1897,10 +1901,36 @@ bool GVN::processInstruction(Instruction *I,
   uint32_t NextNum = VN.getNextUnusedValueNumber();
   unsigned Num = VN.lookup_or_add(I);
 
+  // For conditions branches, we can perform simple conditional propagation on
+  // the condition value itself.
+  if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
+    insert_table(Num, I, I->getParent());
+  
+    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);
+  
+    if (TrueSucc->getSinglePredecessor())
+      insert_table(CondVN,
+                   ConstantInt::getTrue(TrueSucc->getContext()),
+                   TrueSucc);
+    if (FalseSucc->getSinglePredecessor())
+      insert_table(CondVN,
+                   ConstantInt::getFalse(TrueSucc->getContext()),
+                   FalseSucc);
+    
+    return false;
+  }
+
   // Allocations are always uniquely numbered, so we can save time and memory
   // by fast failing them.
   if (isa<AllocaInst>(I) || isa<TerminatorInst>(I) || isa<PHINode>(I)) {
-    insert_table(Num, I);
+    insert_table(Num, I, I->getParent());
     return false;
   }
 
@@ -1908,7 +1938,7 @@ bool GVN::processInstruction(Instruction *I,
   // need to do a lookup to see if the number already exists
   // somewhere in the domtree: it can't!
   if (Num == NextNum) {
-    insert_table(Num, I);
+    insert_table(Num, I, I->getParent());
     return false;
   }
   
@@ -1917,7 +1947,7 @@ bool GVN::processInstruction(Instruction *I,
   Value *repl = lookupNumber(I->getParent(), Num);
   if (repl == 0) {
     // Failure, just remember this instance for future use.
-    insert_table(Num, I);
+    insert_table(Num, I, I->getParent());
     return false;
   }
   
@@ -2144,7 +2174,7 @@ bool GVN::performPRE(Function &F) {
       ++NumGVNPRE;
 
       // Update the availability map to include the new instruction.
-      insert_table(ValNo, PREInstr);
+      insert_table(ValNo, PREInstr, PREPred);
 
       // Create a PHI to make the value available in this block.
       PHINode* Phi = PHINode::Create(CurInst->getType(),
@@ -2157,13 +2187,13 @@ bool GVN::performPRE(Function &F) {
       }
 
       VN.add(Phi, ValNo);
-      insert_table(ValNo, Phi);
+      insert_table(ValNo, Phi, CurrentBlock);
 
       CurInst->replaceAllUsesWith(Phi);
       if (MD && Phi->getType()->isPointerTy())
         MD->invalidateCachedPointerInfo(Phi);
       VN.erase(CurInst);
-      erase_table(ValNo, CurInst);
+      erase_table(ValNo, CurInst, CurrentBlock);
 
       DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
       if (MD) MD->removeInstruction(CurInst);
@@ -2226,14 +2256,14 @@ void GVN::verifyRemoved(const Instruction *Inst) const {
 
   // Walk through the value number scope to make sure the instruction isn't
   // ferreted away in it.
-  for (DenseMap<uint32_t, std::pair<Value*, void*> >::const_iterator
+  for (DenseMap<uint32_t, NumberTableEntry>::const_iterator
        I = NumberTable.begin(), E = NumberTable.end(); I != E; ++I) {
-    std::pair<Value*, void*> const * Node = &I->second;
-    assert(Node->first != Inst && "Inst still in value numbering scope!");
+    const NumberTableEntry *Node = &I->second;
+    assert(Node->Val != Inst && "Inst still in value numbering scope!");
     
-    while (Node->second) {
-      Node = static_cast<std::pair<Value*, void*>*>(Node->second);
-      assert(Node->first != Inst && "Inst still in value numbering scope!");
+    while (Node->Next) {
+      Node = Node->Next;
+      assert(Node->Val != Inst && "Inst still in value numbering scope!");
     }
   }
 }
diff --git a/test/Transforms/GVN/condprop.ll b/test/Transforms/GVN/condprop.ll
new file mode 100644
index 0000000..be6c349
--- /dev/null
+++ b/test/Transforms/GVN/condprop.ll
@@ -0,0 +1,55 @@
+; RUN: opt < %s -basicaa -gvn -S | FileCheck %s
+
+@a = external global i32		; <i32*> [#uses=7]
+
+; CHECK: @foo
+define i32 @foo() nounwind {
+entry:
+	%0 = load i32* @a, align 4
+	%1 = icmp eq i32 %0, 4
+	br i1 %1, label %bb, label %bb1
+
+bb:		; preds = %entry
+	br label %bb8
+
+bb1:		; preds = %entry
+	%2 = load i32* @a, align 4
+	%3 = icmp eq i32 %2, 5
+	br i1 %3, label %bb2, label %bb3
+
+bb2:		; preds = %bb1
+	br label %bb8
+
+bb3:		; preds = %bb1
+	%4 = load i32* @a, align 4
+	%5 = icmp eq i32 %4, 4
+; CHECK: br i1 false, label %bb4, label %bb5
+	br i1 %5, label %bb4, label %bb5
+
+bb4:		; preds = %bb3
+	%6 = load i32* @a, align 4
+	%7 = add i32 %6, 5
+	br label %bb8
+
+bb5:		; preds = %bb3
+	%8 = load i32* @a, align 4
+	%9 = icmp eq i32 %8, 5
+; CHECK: br i1 false, label %bb6, label %bb7
+	br i1 %9, label %bb6, label %bb7
+
+bb6:		; preds = %bb5
+	%10 = load i32* @a, align 4
+	%11 = add i32 %10, 4
+	br label %bb8
+
+bb7:		; preds = %bb5
+	%12 = load i32* @a, align 4
+	br label %bb8
+
+bb8:		; preds = %bb7, %bb6, %bb4, %bb2, %bb
+	%.0 = phi i32 [ %12, %bb7 ], [ %11, %bb6 ], [ %7, %bb4 ], [ 4, %bb2 ], [ 5, %bb ]
+	br label %return
+
+return:		; preds = %bb8
+	ret i32 %.0
+}
\ No newline at end of file