Avoid triangle loops.

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

diff --git a/lib/Transforms/Scalar/LoopRotation.cpp b/lib/Transforms/Scalar/LoopRotation.cpp
index 807d463abb8351b92f9a9ac9805e488018582cf7..a9c3fb9533fa9abc9c770ebbdcd6c00aa63cbda1 100644 (file)
--- a/lib/Transforms/Scalar/LoopRotation.cpp
+++ b/lib/Transforms/Scalar/LoopRotation.cpp
@@ -112,7 +112,7 @@ LoopPass *llvm::createLoopRotatePass() { return new LoopRotate(); }
 /// Rotate Loop L as many times as possible. Return true if
 /// loop is rotated at least once.
 bool LoopRotate::runOnLoop(Loop *Lp, LPPassManager &LPM) {
-  
+
   bool RotatedOneLoop = false;
   initialize();
   LPM_Ptr = &LPM;
@@ -477,8 +477,6 @@ void LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) {
             "Expected only one incoming value from Original PreHeader");
   }
 
-  SplitEdge(L->getLoopLatch(), Exit, this);
-
   if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) {
     DT->addNewBlock(NewPreHeader, OrigPreHeader);
     DT->changeImmediateDominator(L->getHeader(), NewPreHeader);
@@ -497,38 +495,82 @@ void LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) {
 
   if(DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) {
 
-    // New Preheader's dominance frontier is same as original preheader.
-    DominanceFrontier::iterator DFI = DF->find(OrigPreHeader);
-    if (DFI != DF->end()) {
-      DominanceFrontier::DomSetType NPHSet(DFI->second), NHSet(DFI->second);
-      //      NPHSet.insert(DFI->second.begin(), DFI->second.end(), NPHSet.begin());
-      DF->addBasicBlock(NewPreHeader, NPHSet);
-      
-      DominanceFrontier::iterator DHI = DF->find(L->getHeader());
-      if (DHI != DF->end()) {
-        DominanceFrontier::DomSetType DHSet = DHI->second;
-        DHSet.clear();
-        DHSet.insert(DFI->second.begin(), DFI->second.end());
-      } else {
-        DominanceFrontier::DomSetType NHSet(DFI->second);
-        //      NHSet.insert(DFI->second.begin(), DFI->second.end(), NHSet.begin());
-        DF->addBasicBlock(L->getHeader(), NHSet);
-      }
+    // New Preheader's dominance frontier is Exit block.
+    DominanceFrontier::DomSetType NewPHSet;
+    NewPHSet.insert(Exit);
+    DF->addBasicBlock(NewPreHeader, NewPHSet);
+
+    // New Header's dominance frontier now includes itself and Exit block
+    DominanceFrontier::iterator HeadI = DF->find(L->getHeader());
+    if (HeadI != DF->end()) {
+      DominanceFrontier::DomSetType & HeaderSet = HeadI->second;
+      HeaderSet.clear();
+      HeaderSet.insert(L->getHeader());
+      HeaderSet.insert(Exit);
+    } else {
+      DominanceFrontier::DomSetType HeaderSet;
+      HeaderSet.insert(L->getHeader());
+      HeaderSet.insert(Exit);
+      DF->addBasicBlock(L->getHeader(), HeaderSet);
+    }
+
+    // Original header (new Loop Latch)'s dominance frontier is Exit.
+    DominanceFrontier::iterator LatchI = DF->find(L->getLoopLatch());
+    if (LatchI != DF->end()) {
+      DominanceFrontier::DomSetType &LatchSet = LatchI->second;
+      LatchSet = LatchI->second;
+      LatchSet.clear();
+      LatchSet.insert(Exit);
+    } else {
+      DominanceFrontier::DomSetType LatchSet;
+      LatchSet.insert(Exit);
+      DF->addBasicBlock(L->getHeader(), LatchSet);
     }
 
-    // Original header no longer dominates Exit
-    DFI = DF->find(OrigHeader);
-    if (DFI != DF->end()) {
-      for (succ_iterator SI = succ_begin(Exit), SE = succ_end(Exit);
-           SI != SE; ++SI) {
-        BasicBlock *Succ = *SI;
-        DominanceFrontier::DomSetType::iterator DSI = DFI->second.find(Succ);
-        if (DSI != DFI->second.end())
-          DFI->second.erase(DSI);
+    // If a loop block dominates new loop latch then its frontier is
+    // new header and Exit.
+    BasicBlock *NewLatch = L->getLoopLatch();
+    DominatorTree *DT = getAnalysisToUpdate<DominatorTree>();
+    for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end();
+         BI != BE; ++BI) {
+      BasicBlock *B = *BI;
+      if (DT->dominates(B, NewLatch)) {
+        DominanceFrontier::iterator BDFI = DF->find(B);
+        if (BDFI != DF->end()) {
+          DominanceFrontier::DomSetType &BSet = BDFI->second;
+          BSet = BDFI->second;
+          BSet.clear();
+          BSet.insert(L->getHeader());
+          BSet.insert(Exit);
+        } else {
+          DominanceFrontier::DomSetType BSet;
+          BSet.insert(L->getHeader());
+          BSet.insert(Exit);
+          DF->addBasicBlock(B, BSet);
+        }
       }
     }
   }
 
+  // Preserve canonical loop form, which means Exit block should
+  // have only one predecessor.
+  BasicBlock *NExit = SplitEdge(L->getLoopLatch(), Exit, this);
+
+  // Preserve LCSSA.
+  BasicBlock::iterator I = Exit->begin(), E = Exit->end();
+  PHINode *PN = NULL;
+  for (; (PN = dyn_cast<PHINode>(I)); ++I) {
+    PHINode *NewPN = new PHINode(PN->getType(), PN->getName());
+    unsigned N = PN->getNumIncomingValues();
+    for (unsigned index = 0; index < N; ++index)
+      if (PN->getIncomingBlock(index) == NExit) {
+        NewPN->addIncoming(PN->getIncomingValue(index), L->getLoopLatch());
+        PN->setIncomingValue(index, NewPN);
+        PN->setIncomingBlock(index, NExit);
+        NExit->getInstList().push_front(NewPN);
+      }
+  }
+
   assert (NewHeader && L->getHeader() == NewHeader 
           && "Invalid loop header after loop rotation");
   assert (NewPreHeader && L->getLoopPreheader() == NewPreHeader