Fix PR5262: when folding select into PHI, make sure all operands are available

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

diff --git a/lib/Transforms/Scalar/LoopRotation.cpp b/lib/Transforms/Scalar/LoopRotation.cpp
index ae9ab95ca784f424d8637fb530a244953261f2d1..70c69bb1dae0016735483fc40806cf2288ef668a 100644 (file)
--- a/lib/Transforms/Scalar/LoopRotation.cpp
+++ b/lib/Transforms/Scalar/LoopRotation.cpp
@@ -32,7 +32,7 @@ using namespace llvm;
 STATISTIC(NumRotated, "Number of loops rotated");
 namespace {
 
-  class VISIBILITY_HIDDEN RenameData {
+  class RenameData {
   public:
     RenameData(Instruction *O, Value *P, Instruction *H) 
       : Original(O), PreHeader(P), Header(H) { }
@@ -42,8 +42,7 @@ namespace {
     Instruction *Header; // New header replacement
   };
   
-  class VISIBILITY_HIDDEN LoopRotate : public LoopPass {
-
+  class LoopRotate : public LoopPass {
   public:
     static char ID; // Pass ID, replacement for typeid
     LoopRotate() : LoopPass(&ID) {}
@@ -178,6 +177,11 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) {
 
   // Now, this loop is suitable for rotation.
 
+  // Anything ScalarEvolution may know about this loop or the PHI nodes
+  // in its header will soon be invalidated.
+  if (ScalarEvolution *SE = getAnalysisIfAvailable<ScalarEvolution>())
+    SE->forgetLoopBackedgeTakenCount(L);
+
   // Find new Loop header. NewHeader is a Header's one and only successor
   // that is inside loop.  Header's other successor is outside the
   // loop.  Otherwise loop is not suitable for rotation.
@@ -352,10 +356,9 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) {
 
   // Removing incoming branch from loop preheader to original header.
   // Now original header is inside the loop.
-  for (BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
-       I != E; ++I)
-    if (PHINode *PN = dyn_cast<PHINode>(I))
-      PN->removeIncomingValue(OrigPreHeader);
+  for (BasicBlock::iterator I = OrigHeader->begin();
+       (PN = dyn_cast<PHINode>(I)); ++I)
+    PN->removeIncomingValue(OrigPreHeader);
 
   // Make NewHeader as the new header for the loop.
   L->moveToHeader(NewHeader);
@@ -371,12 +374,9 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) {
 /// PHINode may not have an entry for the original pre-header.
 void LoopRotate::updateExitBlock() {
 
-  for (BasicBlock::iterator I = Exit->begin(), E = Exit->end();
-       I != E; ++I) {
-
-    PHINode *PN = dyn_cast<PHINode>(I);
-    if (!PN)
-      break;
+  PHINode *PN;
+  for (BasicBlock::iterator I = Exit->begin();
+       (PN = dyn_cast<PHINode>(I)); ++I) {
 
     // There is already one incoming value from original pre-header block.
     if (PN->getBasicBlockIndex(OrigPreHeader) != -1)
@@ -384,7 +384,7 @@ void LoopRotate::updateExitBlock() {
 
     const RenameData *ILoopHeaderInfo;
     Value *V = PN->getIncomingValueForBlock(OrigHeader);
-    if (isa<Instruction>(V) && 
+    if (isa<Instruction>(V) &&
         (ILoopHeaderInfo = findReplacementData(cast<Instruction>(V)))) {
       assert(ILoopHeaderInfo->PreHeader && "Missing New Preheader Instruction");
       PN->addIncoming(ILoopHeaderInfo->PreHeader, OrigPreHeader);
@@ -439,7 +439,8 @@ void LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) {
   // Right now original pre-header has two successors, new header and
   // exit block. Insert new block between original pre-header and
   // new header such that loop's new pre-header has only one successor.
-  BasicBlock *NewPreHeader = BasicBlock::Create("bb.nph",
+  BasicBlock *NewPreHeader = BasicBlock::Create(OrigHeader->getContext(),
+                                                "bb.nph",
                                                 OrigHeader->getParent(), 
                                                 NewHeader);
   LoopInfo &LI = LPM.getAnalysis<LoopInfo>();
@@ -455,13 +456,10 @@ void LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) {
            "Unexpected original pre-header terminator");
     OrigPH_BI->setSuccessor(1, NewPreHeader);
   }
-  
-  for (BasicBlock::iterator I = NewHeader->begin(), E = NewHeader->end();
-       I != E; ++I) {
-    PHINode *PN = dyn_cast<PHINode>(I);
-    if (!PN)
-      break;
 
+  PHINode *PN;
+  for (BasicBlock::iterator I = NewHeader->begin();
+       (PN = dyn_cast<PHINode>(I)); ++I) {
     int index = PN->getBasicBlockIndex(OrigPreHeader);
     assert(index != -1 && "Expected incoming value from Original PreHeader");
     PN->setIncomingBlock(index, NewPreHeader);
@@ -518,26 +516,30 @@ void LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) {
       DF->addBasicBlock(L->getHeader(), LatchSet);
     }
 
-    // If a loop block dominates new loop latch then its frontier is
-    // new header and Exit.
+    // If a loop block dominates new loop latch then add to its frontiers
+    // new header and Exit and remove new latch (which is equal to original
+    // header).
     BasicBlock *NewLatch = L->getLoopLatch();
-    DominatorTree *DT = getAnalysisIfAvailable<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);
+
+    assert(NewLatch == OrigHeader && "NewLatch is inequal to OrigHeader");
+
+    if (DominatorTree *DT = getAnalysisIfAvailable<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.erase(NewLatch);
+            BSet.insert(L->getHeader());
+            BSet.insert(Exit);
+          } else {
+            DominanceFrontier::DomSetType BSet;
+            BSet.insert(L->getHeader());
+            BSet.insert(Exit);
+            DF->addBasicBlock(B, BSet);
+          }
         }
       }
     }
@@ -545,23 +547,7 @@ void LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) {
 
   // 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) {
-    unsigned N = PN->getNumIncomingValues();
-    for (unsigned index = 0; index < N; ++index)
-      if (PN->getIncomingBlock(index) == NExit) {
-        PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName(),
-                                         NExit->begin());
-        NewPN->addIncoming(PN->getIncomingValue(index), L->getLoopLatch());
-        PN->setIncomingValue(index, NewPN);
-        PN->setIncomingBlock(index, NExit);
-        break;
-      }
-  }
+  SplitEdge(L->getLoopLatch(), Exit, this);
 
   assert(NewHeader && L->getHeader() == NewHeader &&
          "Invalid loop header after loop rotation");