[LoopSimplify] Fix incorrect SCEV invalidation

[mkazantsev]

Summary

In the function simplifyOneLoop we optimistically assume that changes in the
inner loop only affect this very loop and have no impact on its parents. In fact,
after rL329047 has been merged, we can now calculate exit counts for outer
loops which may depend on inner loops. Thus, we need to invalidate all parents
when we do something to a loop.

There is an evidence of incorrect behavior of simplifyOneLoop: when we insert
SE->verify() check in the end of this funciton, it fails on a bunch of existing
test, in particular:

LLVM :: Transforms/LoopUnroll/peel-loop-not-forced.ll
LLVM :: Transforms/LoopUnroll/peel-loop-pgo.ll
LLVM :: Transforms/LoopUnroll/peel-loop.ll
LLVM :: Transforms/LoopUnroll/peel-loop2.ll

Note that previously we have fixed issues of this variety, see rL328483.
This patch makes this function invalidate the outermost loop properly.

[chandlerc]

LGTM, good spot. I'll also definitely check if this fixes the mystery stage2 miscompile we've seen on PPC. It's a good fix either way though.

[sanjoy]

ScalarEvolution::verify has false positives (i.e. it fails when it shouldn't) in some corner cases which is why it isn't run by default from verifyAnalysis[0]. So I don't think it is safe to add calls to ScalarEvolution::verify like this (this should really have been a comment on ScalarEvolution::verify -- I'll add that once these new call sites are removed).

[0] An an example, going by memory, it will complain if you change the trip count of a loop from undef to undef + 1. Of course, undef + 1 is undef, but SCEV does not know that -- it assumes undef is an unknown constant.

[mkazantsev]

Thanks @sanjoy, it seems that I am seeing something of this sort right now on one of my Fuzzer tests. I will undo the verification.

[mstorsjo]

FWIW, I'm also running into issues where this commit made compilation of one source file run forever. Previously, compilation of the file took 47 seconds, now it doesn't finish in 10+ minutes.

If you want to have a look at that case in case it's an issue different from the others, it's available at https://martin.st/temp/glew-preproc.c, try building with clang -target x86_64-w64-mingw32 -c -O2 glew-preproc.c.

[mkazantsev]

Hi @mstorsjo, I will take a look. Can I ask you to file a bug on https://bugs.llvm.org/ so that we could keep records of our findings?

Basically this patch is a correctness fix, but maybe there are cases where we could be a bit less aggressive.

[mstorsjo]

In D45937#1080630, @mkazantsev wrote:

Hi @mstorsjo, I will take a look. Can I ask you to file a bug on https://bugs.llvm.org/ so that we could keep records of our findings?

Basically this patch is a correctness fix, but maybe there are cases where we could be a bit less aggressive.

FWIW, it seems like this issue has disappeared since - the latest trunk is good now again, but I haven't bisected again to find exactly which commit fixed it.

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

public:
   bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
 
   /// This method should be called by the client when it has changed a loop in
   /// a way that may effect ScalarEvolution's ability to compute a trip count,
   /// or if the loop is deleted.  This call is potentially expensive for large
   /// loop bodies.
   void forgetLoop(const Loop *L);
 
+  // This method invokes forgetLoop for the outermost loop of the given loop
+  // \p L, making ScalarEvolution forget about all this subtree. This needs to
+  // be done whenever we make a transform that may affect the parameters of the
+  // outer loop, such as exit counts for branches.
+  void forgetTopmostLoop(const Loop *L);
+
   /// This method should be called by the client when it has changed a value
   /// in a way that may effect its value, or which may disconnect it from a
   /// def-use chain linking it to a loop.
   void forgetValue(Value *V);
 
   /// Called when the client has changed the disposition of values in
   /// this loop.
   ///

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

while (!LoopWorklist.empty()) {
 
     LoopPropertiesCache.erase(CurrL);
     // Forget all contained loops too, to avoid dangling entries in the
     // ValuesAtScopes map.
     LoopWorklist.append(CurrL->begin(), CurrL->end());
   }
 }
 
+void ScalarEvolution::forgetTopmostLoop(const Loop *L) {
+  while (Loop *Parent = L->getParentLoop())
+    L = Parent;
+  forgetLoop(L);
+}
+
 void ScalarEvolution::forgetValue(Value *V) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I) return;
 
   // Drop information about expressions based on loop-header PHIs.
   SmallVector<Instruction *, 16> Worklist;
   Worklist.push_back(I);
 

llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp

if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
         if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) {
 
           DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in "
                        << ExitingBlock->getName() << "\n");
 
           BI->setCondition(ConstantInt::get(Cond->getType(),
                                             !L->contains(BI->getSuccessor(0))));
 
-          // This may make the loop analyzable, force SCEV recomputation.
-          if (SE)
-            SE->forgetLoop(L);
-
           Changed = true;
         }
       }
 
   // Does the loop already have a preheader?  If so, don't insert one.
   BasicBlock *Preheader = L->getLoopPreheader();
   if (!Preheader) {
     Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
       if (!FoldBranchToCommonDest(BI))
         continue;
 
       // Success. The block is now dead, so remove it from the loop,
       // update the dominator tree and delete it.
       DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block "
                    << ExitingBlock->getName() << "\n");
 
-      // Notify ScalarEvolution before deleting this block. Currently assume the
-      // parent loop doesn't change (spliting edges doesn't count). If blocks,
-      // CFG edges, or other values in the parent loop change, then we need call
-      // to forgetLoop() for the parent instead.
-      if (SE)
-        SE->forgetLoop(L);
-
       assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock));
       Changed = true;
       LI->removeBlock(ExitingBlock);
 
       DomTreeNode *Node = DT->getNode(ExitingBlock);
       const std::vector<DomTreeNodeBase<BasicBlock> *> &Children =
         Node->getChildren();
       while (!Children.empty()) {
         DomTreeNode *Child = Children.front();
         DT->changeImmediateDominator(Child, Node->getIDom());
       }
       DT->eraseNode(ExitingBlock);
 
       BI->getSuccessor(0)->removePredecessor(
           ExitingBlock, /* DontDeleteUselessPHIs */ PreserveLCSSA);
       BI->getSuccessor(1)->removePredecessor(
           ExitingBlock, /* DontDeleteUselessPHIs */ PreserveLCSSA);
       ExitingBlock->eraseFromParent();
     }
   }
 
+  // Changing exit conditions for blocks may affect exit counts of this loop and
+  // any of its paretns, so we must invalidate the entire subtree if we've made
+  // any changes.
+  if (Changed && SE)
+    SE->forgetTopmostLoop(L);
+
+#ifndef NDEBUG
+  // Make sure that after all our transforms SE is correct.
+  if (SE)
+    SE->verify();
+#endif
+
   return Changed;
 }
 
 bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
                         ScalarEvolution *SE, AssumptionCache *AC,
                         bool PreserveLCSSA) {
   bool Changed = false;
 

llvm/trunk/test/Transforms/LoopSimplify/preserve-scev.ll

 ;
 ; After simplifying, the max backedge count is refined.
 ; Second SCEV print:
 ; CHECK-LABEL: Determining loop execution counts for: @mergeExit
 ; CHECK: Loop %while.cond191: <multiple exits> backedge-taken count is 0
 ; CHECK: Loop %while.cond191: max backedge-taken count is 0
 ; CHECK: Loop %while.cond191: Predicated backedge-taken count is 0
 ; CHECK: Loop %while.cond191.outer: <multiple exits> Unpredictable backedge-taken count.
-; CHECK: Loop %while.cond191.outer: Unpredictable max backedge-taken count.
+; CHECK: Loop %while.cond191.outer: max backedge-taken count is false
 ; CHECK: Loop %while.cond191.outer: Unpredictable predicated backedge-taken count.
 define void @mergeExit(i32 %MapAttrCount) nounwind uwtable ssp {
 entry:
   br i1 undef, label %if.then124, label %if.end126
 
 if.then124:                                       ; preds = %entry
   unreachable