Avoid triangle loops.

[oota-llvm.git] / lib / Transforms / Scalar / GVN.cpp

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index edd11e8e493b0dff793a18e7c4c49f80e1799925..d1a15c10816fa53b74a08117c2fc0d0256883665 100644 (file)
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -671,6 +671,7 @@ namespace {
                             DenseMap<BasicBlock*, Value*> &Phis,
                             bool top_level = false);
     void dump(DenseMap<BasicBlock*, Value*>& d);
+    bool iterateOnFunction(Function &F);
   };
   
   char GVN::ID = 0;
@@ -748,40 +749,59 @@ Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
   if (Phis.count(BB) == 0)
     Phis.insert(std::make_pair(BB, PN));
   
-  bool all_same = true;
-  Value* first = 0;
-  
   // Fill in the incoming values for the block.
   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
     Value* val = GetValueForBlock(*PI, orig, Phis);
-    if (first == 0)
-      first = val;
-    else if (all_same && first != val)
-      all_same = false;
     
     PN->addIncoming(val, *PI);
   }
   
-  if (all_same) {
-    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
-    
-    MD.removeInstruction(PN);
-    PN->replaceAllUsesWith(first);
-    
-    SmallVector<BasicBlock*, 4> toRemove;
-    for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
-         E = Phis.end(); I != E; ++I)
-      if (I->second == PN)
-        toRemove.push_back(I->first);
-    for (SmallVector<BasicBlock*, 4>::iterator I = toRemove.begin(),
-         E= toRemove.end(); I != E; ++I)
-      Phis[*I] = first;
-    
-    PN->eraseFromParent();
-    
-    Phis[BB] = first;
-    
-    return first;
+  Value* v = PN->hasConstantValue();
+  if (v) {
+    if (Instruction* inst = dyn_cast<Instruction>(v)) {
+      DominatorTree &DT = getAnalysis<DominatorTree>();  
+      if (DT.dominates(inst, PN)) {
+        MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
+
+        MD.removeInstruction(PN);
+        PN->replaceAllUsesWith(inst);
+
+        SmallVector<BasicBlock*, 4> toRemove;
+        for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
+             E = Phis.end(); I != E; ++I)
+          if (I->second == PN)
+            toRemove.push_back(I->first);
+        for (SmallVector<BasicBlock*, 4>::iterator I = toRemove.begin(),
+             E= toRemove.end(); I != E; ++I)
+          Phis[*I] = inst;
+
+        PN->eraseFromParent();
+
+        Phis[BB] = inst;
+
+        return inst;
+      }
+    } else {
+      MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
+
+      MD.removeInstruction(PN);
+      PN->replaceAllUsesWith(v);
+
+      SmallVector<BasicBlock*, 4> toRemove;
+      for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
+           E = Phis.end(); I != E; ++I)
+        if (I->second == PN)
+          toRemove.push_back(I->first);
+      for (SmallVector<BasicBlock*, 4>::iterator I = toRemove.begin(),
+           E= toRemove.end(); I != E; ++I)
+        Phis[*I] = v;
+
+      PN->eraseFromParent();
+
+      Phis[BB] = v;
+
+      return v;
+    }
   }
 
   phiMap[orig->getPointerOperand()].insert(PN);
@@ -856,10 +876,19 @@ bool GVN::processLoad(LoadInst* L,
   
   // ... to a pointer that has been loaded from before...
   MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
+  bool removedNonLocal = false;
   Instruction* dep = MD.getDependency(L);
   if (dep == MemoryDependenceAnalysis::NonLocal &&
-      L->getParent() != &L->getParent()->getParent()->getEntryBlock())
-    processNonLocalLoad(L, toErase);
+      L->getParent() != &L->getParent()->getParent()->getEntryBlock()) {
+    removedNonLocal = processNonLocalLoad(L, toErase);
+    
+    if (!removedNonLocal)
+      last = L;
+    
+    return removedNonLocal;
+  }
+  
+  
   bool deletedLoad = false;
   
   while (dep != MemoryDependenceAnalysis::None &&
@@ -905,7 +934,7 @@ bool GVN::processLoad(LoadInst* L,
   return deletedLoad;
 }
 
-/// buildsets_availout - When calculating availability, handle an instruction
+/// processInstruction - When calculating availability, handle an instruction
 /// by inserting it into the appropriate sets
 bool GVN::processInstruction(Instruction* I,
                                 ValueNumberedSet& currAvail,
@@ -917,7 +946,27 @@ bool GVN::processInstruction(Instruction* I,
   
   unsigned num = VN.lookup_or_add(I);
   
-  if (currAvail.test(num)) {
+  if (PHINode* p = dyn_cast<PHINode>(I)) {
+    Value* constVal = p->hasConstantValue();
+    
+    if (constVal) {
+      if (Instruction* inst = dyn_cast<Instruction>(constVal)) {
+        DominatorTree &DT = getAnalysis<DominatorTree>();  
+        if (DT.dominates(inst, p)) {
+          for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end();
+               PI != PE; ++PI)
+            if (PI->second.count(p))
+              PI->second.erase(p);
+        
+          p->replaceAllUsesWith(inst);
+          toErase.push_back(p);
+        }
+      } else {
+        p->replaceAllUsesWith(constVal);
+        toErase.push_back(p);
+      }
+    }
+  } else if (currAvail.test(num)) {
     Value* repl = find_leader(currAvail, num);
     
     VN.erase(I);
@@ -935,7 +984,21 @@ bool GVN::processInstruction(Instruction* I,
 // GVN::runOnFunction - This is the main transformation entry point for a
 // function.
 //
-bool GVN::runOnFunction(Function &F) {
+bool GVN::runOnFunction(Function& F) {
+  bool changed = false;
+  bool shouldContinue = true;
+  
+  while (shouldContinue) {
+    shouldContinue = iterateOnFunction(F);
+    changed |= shouldContinue;
+  }
+  
+  return changed;
+}
+
+
+// GVN::iterateOnFunction - Executes one iteration of GVN
+bool GVN::iterateOnFunction(Function &F) {
   // Clean out global sets from any previous functions
   VN.clear();
   availableOut.clear();