At end of LSR, replace uses of now constant (as result of SplitCriticalEdge) PHI...

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

diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp
index ede3bd9dde630acb39c3ca052605664eac27bfc1..8a094aa9678a80b92191cda8d3618b64efb77768 100644 (file)
--- a/lib/Transforms/Scalar/LICM.cpp
+++ b/lib/Transforms/Scalar/LICM.cpp
@@ -265,7 +265,7 @@ bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
   //
   // Traverse the body of the loop in depth first order on the dominator tree so
   // that we are guaranteed to see definitions before we see uses.  This allows
-  // us to sink instructions in one pass, without iteration.  AFter sinking
+  // us to sink instructions in one pass, without iteration.  After sinking
   // instructions, we perform another pass to hoist them out of the loop.
   //
   SinkRegion(DT->getNode(L->getHeader()));
@@ -446,7 +446,7 @@ bool LICM::isLoopInvariantInst(Instruction &I) {
 void LICM::sink(Instruction &I) {
   DOUT << "LICM sinking instruction: " << I;
 
-  std::vector<BasicBlock*> ExitBlocks;
+  SmallVector<BasicBlock*, 8> ExitBlocks;
   CurLoop->getExitBlocks(ExitBlocks);
 
   if (isa<LoadInst>(I)) ++NumMovedLoads;
@@ -623,7 +623,7 @@ bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) {
       return true;
 
   // Get the exit blocks for the current loop.
-  std::vector<BasicBlock*> ExitBlocks;
+  SmallVector<BasicBlock*, 8> ExitBlocks;
   CurLoop->getExitBlocks(ExitBlocks);
 
   // For each exit block, get the DT node and walk up the DT until the
@@ -725,7 +725,7 @@ void LICM::PromoteValuesInLoop() {
   //
   std::set<BasicBlock*> ProcessedBlocks;
 
-  std::vector<BasicBlock*> ExitBlocks;
+  SmallVector<BasicBlock*, 8> ExitBlocks;
   CurLoop->getExitBlocks(ExitBlocks);
   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
     if (ProcessedBlocks.insert(ExitBlocks[i]).second) {
@@ -759,15 +759,24 @@ void LICM::PromoteValuesInLoop() {
 }
 
 /// FindPromotableValuesInLoop - Check the current loop for stores to definite
-/// pointers, which are not loaded and stored through may aliases.  If these are
-/// found, create an alloca for the value, add it to the PromotedValues list,
-/// and keep track of the mapping from value to alloca.
-///
+/// pointers, which are not loaded and stored through may aliases and are safe
+/// for promotion.  If these are found, create an alloca for the value, add it 
+/// to the PromotedValues list, and keep track of the mapping from value to 
+/// alloca. 
 void LICM::FindPromotableValuesInLoop(
                    std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues,
                              std::map<Value*, AllocaInst*> &ValueToAllocaMap) {
   Instruction *FnStart = CurLoop->getHeader()->getParent()->begin()->begin();
 
+  SmallVector<Instruction *, 4> LoopExits;
+  SmallVector<BasicBlock *, 4> Blocks;
+  CurLoop->getExitingBlocks(Blocks);
+  for (SmallVector<BasicBlock *, 4>::iterator BI = Blocks.begin(),
+         BE = Blocks.end(); BI != BE; ++BI) {
+    BasicBlock *BB = *BI;
+    LoopExits.push_back(BB->getTerminator());
+  }
+
   // Loop over all of the alias sets in the tracker object.
   for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end();
        I != E; ++I) {
@@ -777,7 +786,7 @@ void LICM::FindPromotableValuesInLoop(
     // volatile loads or stores.
     if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias() &&
         !AS.isVolatile() && CurLoop->isLoopInvariant(AS.begin()->first)) {
-      assert(AS.begin() != AS.end() &&
+      assert(!AS.empty() &&
              "Must alias set should have at least one pointer element in it!");
       Value *V = AS.begin()->first;
 
@@ -791,6 +800,42 @@ void LICM::FindPromotableValuesInLoop(
           break;
         }
 
+      // If one use of value V inside the loop is safe then it is OK to promote 
+      // this value. On the otherside if there is not any unsafe use inside the
+      // looop then also it is OK to  promote this value. Otherwise it is
+      // unsafe to promote this value.
+      if (PointerOk) {
+        bool oneSafeUse = false;
+        bool oneUnsafeUse = false;
+        for(Value::use_iterator UI = V->use_begin(), UE = V->use_end();
+            UI != UE; ++UI) {
+          Instruction *Use = dyn_cast<Instruction>(*UI);
+          if (!Use || !CurLoop->contains(Use->getParent()))
+            continue;
+          for (SmallVector<Instruction *, 4>::iterator 
+                 ExitI = LoopExits.begin(), ExitE = LoopExits.end();
+               ExitI != ExitE; ++ExitI) {
+            Instruction *Ex = *ExitI;
+            if (!isa<PHINode>(Use) && DT->dominates(Use, Ex)) {
+              oneSafeUse = true;
+              break;
+            }
+            else 
+              oneUnsafeUse = true;
+          }
+
+          if (oneSafeUse)
+            break;
+        }
+
+        if (oneSafeUse)
+          PointerOk = true;
+        else if (!oneUnsafeUse)
+          PointerOk = true;
+        else
+          PointerOk = false;
+      }
+      
       if (PointerOk) {
         const Type *Ty = cast<PointerType>(V->getType())->getElementType();
         AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart);