3 files changed, 61 insertions, 27 deletions

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 5bad4b2..fba6e20 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -2549,14 +2549,14 @@ PushDefUseChildren(Instruction *I,
 /// the Scalars map if they reference SymName. This is used during PHI
 /// resolution.
 void
-ScalarEvolution::ForgetSymbolicName(Instruction *I, const SCEV *SymName) {
+ScalarEvolution::ForgetSymbolicName(Instruction *PN, const SCEV *SymName) {
   SmallVector<Instruction *, 16> Worklist;
-  PushDefUseChildren(I, Worklist);
+  PushDefUseChildren(PN, Worklist);
 
   SmallPtrSet<Instruction *, 8> Visited;
-  Visited.insert(I);
+  Visited.insert(PN);
   while (!Worklist.empty()) {
-    I = Worklist.pop_back_val();
+    Instruction *I = Worklist.pop_back_val();
     if (!Visited.insert(I)) continue;
 
     std::map<SCEVCallbackVH, const SCEV *>::iterator It =
@@ -2568,12 +2568,15 @@ ScalarEvolution::ForgetSymbolicName(Instruction *I, const SCEV *SymName) {
         continue;
 
       // SCEVUnknown for a PHI either means that it has an unrecognized
-      // structure, or it's a PHI that's in the progress of being computed
-      // by createNodeForPHI.  In the former case, additional loop trip
-      // count information isn't going to change anything. In the later
-      // case, createNodeForPHI will perform the necessary updates on its
-      // own when it gets to that point.
-      if (!isa<PHINode>(I) || !isa<SCEVUnknown>(It->second)) {
+      // structure, it's a PHI that's in the progress of being computed
+      // by createNodeForPHI, or it's a single-value PHI. In the first case,
+      // additional loop trip count information isn't going to change anything.
+      // In the second case, createNodeForPHI will perform the necessary
+      // updates on its own when it gets to that point. In the third, we do
+      // want to forget the SCEVUnknown.
+      if (!isa<PHINode>(I) ||
+          !isa<SCEVUnknown>(It->second) ||
+          (I != PN && It->second == SymName)) {
         ValuesAtScopes.erase(It->second);
         Scalars.erase(It);
       }
@@ -2696,9 +2699,21 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
         return SymbolicName;
       }
 
-  // It's tempting to recognize PHIs with a unique incoming value, however
-  // this leads passes like indvars to break LCSSA form. Fortunately, such
-  // PHIs are rare, as instcombine zaps them.
+  // If the PHI has a single incoming value, follow that value, unless the
+  // PHI's incoming blocks are in a different loop, in which case doing so
+  // risks breaking LCSSA form. Instcombine would normally zap these, but
+  // it doesn't have DominatorTree information, so it may miss cases.
+  if (Value *V = PN->hasConstantValue(DT)) {
+    bool AllSameLoop = true;
+    Loop *PNLoop = LI->getLoopFor(PN->getParent());
+    for (size_t i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+      if (LI->getLoopFor(PN->getIncomingBlock(i)) != PNLoop) {
+        AllSameLoop = false;
+        break;
+      }
+    if (AllSameLoop)
+      return getSCEV(V);
+  }
 
   // If it's not a loop phi, we can't handle it yet.
   return getUnknown(PN);
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index 6ee1fd6..4fe08e4 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -384,17 +384,18 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
   // in this loop, insert a canonical induction variable of the largest size.
   Value *IndVar = 0;
   if (NeedCannIV) {
-    // Check to see if the loop already has a canonical-looking induction
-    // variable. If one is present and it's wider than the planned canonical
-    // induction variable, temporarily remove it, so that the Rewriter
-    // doesn't attempt to reuse it.
-    PHINode *OldCannIV = L->getCanonicalInductionVariable();
-    if (OldCannIV) {
+    // Check to see if the loop already has any canonical-looking induction
+    // variables. If any are present and wider than the planned canonical
+    // induction variable, temporarily remove them, so that the Rewriter
+    // doesn't attempt to reuse them.
+    SmallVector<PHINode *, 2> OldCannIVs;
+    while (PHINode *OldCannIV = L->getCanonicalInductionVariable()) {
       if (SE->getTypeSizeInBits(OldCannIV->getType()) >
           SE->getTypeSizeInBits(LargestType))
         OldCannIV->removeFromParent();
       else
-        OldCannIV = 0;
+        break;
+      OldCannIVs.push_back(OldCannIV);
     }
 
     IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType);
@@ -404,17 +405,21 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
     DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n');
 
     // Now that the official induction variable is established, reinsert
-    // the old canonical-looking variable after it so that the IR remains
-    // consistent. It will be deleted as part of the dead-PHI deletion at
+    // any old canonical-looking variables after it so that the IR remains
+    // consistent. They will be deleted as part of the dead-PHI deletion at
     // the end of the pass.
-    if (OldCannIV)
-      OldCannIV->insertAfter(cast<Instruction>(IndVar));
+    while (!OldCannIVs.empty()) {
+      PHINode *OldCannIV = OldCannIVs.pop_back_val();
+      OldCannIV->insertBefore(L->getHeader()->getFirstNonPHI());
+    }
   }
 
   // If we have a trip count expression, rewrite the loop's exit condition
   // using it.  We can currently only handle loops with a single exit.
   ICmpInst *NewICmp = 0;
-  if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && ExitingBlock) {
+  if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) &&
+      !BackedgeTakenCount->isZero() &&
+      ExitingBlock) {
     assert(NeedCannIV &&
            "LinearFunctionTestReplace requires a canonical induction variable");
     // Can't rewrite non-branch yet.
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index 57bab60..2e1f935 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -159,6 +159,22 @@ ReprocessLoop:
     }
   }
 
+  // If there are exiting blocks with branches on undef, resolve the undef in
+  // the direction which will exit the loop. This will help simplify loop
+  // trip count computations.
+  SmallVector<BasicBlock*, 8> ExitingBlocks;
+  L->getExitingBlocks(ExitingBlocks);
+  for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(),
+       E = ExitingBlocks.end(); I != E; ++I)
+    if (BranchInst *BI = dyn_cast<BranchInst>((*I)->getTerminator()))
+      if (BI->isConditional()) {
+        if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) {
+          BI->setCondition(ConstantInt::get(Cond->getType(),
+                                            !L->contains(BI->getSuccessor(0))));
+          Changed = true;
+        }
+      }
+
   // Does the loop already have a preheader?  If so, don't insert one.
   BasicBlock *Preheader = L->getLoopPreheader();
   if (!Preheader) {
@@ -250,8 +266,6 @@ ReprocessLoop:
         break;
       }
   if (UniqueExit) {
-    SmallVector<BasicBlock*, 8> ExitingBlocks;
-    L->getExitingBlocks(ExitingBlocks);
     for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
       BasicBlock *ExitingBlock = ExitingBlocks[i];
       if (!ExitingBlock->getSinglePredecessor()) continue;