[LoopUnrollPeel] Fix potentially incorrect invalidation of SCEV in peelLoop

[mkazantsev]

Summary

Current peeling code invalidates parent loop saying that it might have changed
after the inner loop has changed, but it doesn't bother to do the same to its parents.
With patch rL329047, SCEV becomes much smarter about calculation of exit counts for
outer loops. We might need to invalidate not only the immediate parent, but also
any of its parents as well.

There is no clear evidence that there is some miscompile happening because of this
, but the common sense says that the current code may be wrong.

[mkazantsev]

Ping?

[fhahn]

If the current code is correct in that the parent loop needs to be forgotten, then I agree that we should forget all parent loops.

But do we actually need to invalidate the parent? IIUC (and I am not very familiar with the SCEV invalidation code), there are the following ways a SCEVExpr from the peeled loop could impact an SCEV Expr in a parent loop:

1. Add rec expr escaping from L: those should be kept track in LoopUsers and should be properly invalidated by forgetLoop
2. expressions based on L's header phis: those should be invalidated by forgetLoop too.
3. loop invariant value escaping from L: those should be unchanged by peeling/unrolling, so there should be no need for invalidation.

[mkazantsev]

Hi Florian,

If you take a look at computeBackedgeTakenCount method, it constructs BackedgeTakenInfo that contains references on loop's exiting blocks inside. This info is then cached in BackedgeTakenCounts. If we change an inner loop so that one of these blocks gets deleted or stops being exiting, any of its parents may end up keeping dangling pointers to this block (because exiting block of inner loop can also be an exiting block of its parents).

[fhahn]

In D46044#1388382, @mkazantsev wrote:

Hi Florian,

If you take a look at computeBackedgeTakenCount method, it constructs BackedgeTakenInfo that contains references on loop's exiting blocks inside. This info is then cached in BackedgeTakenCounts. If we change an inner loop so that one of these blocks gets deleted or stops being exiting, any of its parents may end up keeping dangling pointers to this block (because exiting block of inner loop can also be an exiting block of its parents).

Ah right, Loop peeling currently is restricted to loops with a unique exiting block that is also the loop latch. I am not sure if it is possible to have parent loops that share the peeled loop's exiting block: if there's only one exiting block, the parent loop should be the loop containing the exit block?

But I suppose it would be fine to be cautious here, especially because simplifyLoop already uses forgetTopmostLoop. So maybe just use forgetTopmostLoop here and preserving SE in simplifyLoop should unnecessary.

While playing around with the invalidation here, I found another potential issue: not invalidating when L has no parent. After peeling the exit count of L will have changed -> D58192.

lib/Transforms/Utils/LoopUnrollPeel.cpp

else
       BackEdgeWeight = 1;
     MDBuilder MDB(LatchBR->getContext());
     MDNode *WeightNode =
         HeaderIdx ? MDB.createBranchWeights(ExitWeight, BackEdgeWeight)
                   : MDB.createBranchWeights(BackEdgeWeight, ExitWeight);
     LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
   }
 
-  // If the loop is nested, we changed the parent loop, update SE.
+  // If the loop is nested, we could have changed any of its parent loops,
+  // update SE.
   if (Loop *ParentLoop = L->getParentLoop()) {
-    SE->forgetLoop(ParentLoop);
+    SE->forgetTopmostLoop(ParentLoop);
 
     // FIXME: Incrementally update loop-simplify
     simplifyLoop(ParentLoop, DT, LI, SE, AC, PreserveLCSSA);
   } else {
     // FIXME: Incrementally update loop-simplify
     simplifyLoop(L, DT, LI, SE, AC, PreserveLCSSA);
   }
 
   NumPeeled++;
 
   return true;
 }