Fix bug26682 -- IndVar breaks LCSSA

[david2050]

Summary

This fixes a bug where the initial value reaching definition is needs
to be widen and there is a cached widening operation which dominates
but is defined inside a different loop that is not an outer loop.

https://llvm.org/bugs/show_bug.cgi?id=26682

[wmi]

I think the bug has been fixed in r259815. Please update to the head and verify whether it fixes your problem. Looks like your fix here is the same with r259815. But still many thanks for trying to help.

[david2050]

Thanks Wei, you are correct that master fixes this problem.

include/llvm/Analysis/LoopInfo.h

if (!Contains(OldLoop, NewLoop)) {
         auto *DefBlock = DefI->getParent();
         if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop)
           return false;
       }
     }
 
     return true;
   }
+  
+  /// Checks if using a specific instruction can break LCSSA in any loop.
+  ///
+  /// Return true if using \p Inst just before \p NewLoc will break LCSSA,
+  /// assuming that the function containing \p Inst and \p NewLoc is currently
+  /// in LCSSA form.
+  bool usePreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) {
+    assert(Inst->getFunction() == NewLoc->getFunction() && "Can't reason about IPO!");
+    
+    auto *OldBB = Inst->getParent();
+    auto *NewBB = NewLoc->getParent();
+    
+    // Movement within the same loop does not break LCSSA (the equality check is
+    // to avoid doing a hashtable lookup in case of intra-block movement).
+    if (OldBB == NewBB)
+      return true;
+    
+    auto *OldLoop = getLoopFor(OldBB);
+    auto *NewLoop = getLoopFor(NewBB);
+    
+    return OldLoop->contains(NewLoop);
+  }
 };
 
 // Allow clients to walk the list of nested loops...
 template <> struct GraphTraits<const Loop*> {
   typedef const Loop NodeType;
   typedef LoopInfo::iterator ChildIteratorType;
 
   static NodeType *getEntryNode(const Loop *L) { return L; }

lib/Analysis/ScalarEvolutionExpander.cpp

Value *SCEVExpander::expand(const SCEV *S) {
   // from being reverted.
   if (!(LSRMode && SE.containsAddRecurrence(S))) {
     // If S is scConstant, it may be worse to reuse an existing Value.
     if (S->getSCEVType() != scConstant && Set) {
       // Choose a Value from the set which dominates the insertPt.
       for (auto const &Ent : *Set) {
         if (Ent && isa<Instruction>(Ent) && S->getType() == Ent->getType() &&
             cast<Instruction>(Ent)->getFunction() == InsertPt->getFunction() &&
-            SE.DT.dominates(cast<Instruction>(Ent), InsertPt)) {
+            SE.DT.dominates(cast<Instruction>(Ent), InsertPt) &&
+            SE.LI.usePreservesLCSSAForm(cast<Instruction>(Ent), InsertPt)) {
           V = Ent;
           break;
         }
       }
     }
   }
   if (!V)
     V = visit(S);