[IndVars] Delay forgetValue() call

[nikic]

Summary

While working on D82730 I ran into a case where nearly all compile-time is spent inside the forgetValue() call in rewriteLoopExitValues(). Currently it forgets values eagerly, regardless of whether the phi node will actually get replaced or not. This patch moves the forgetValue() call to just before the phi gets replaced, so we don't waste time forgetting values that don't get changed.

However, this causes a test change in elim-extend.ll. The reason is that an earlier Phi node replacement in IV widening did not perform the forgetValue() call, and as such left behind stale SCEVs (still correct, but possibly sub-accurate). Insert the missing call.

[nikic]

Compile-time numbers: There's various minor improvements, and larger ones for ClamAV (2% in LTO -g configuration). So it seems that this does affect more than just the particularly pathological case I hit.

[nikic]

Ping

[nikic]

Ping x2

[fhahn]

I think there might be more cases where we miss proper invalidation now. When building MultiSource & SPEC2006 with the patch, there are ~20 binary changes (out of 237)

[nikic]

@fhahn Thanks for taking a look!

For the first diff I checked, the issue appears to be lack of "ext of min/max" to "min/max of ext" canonicalization in SCEV. Which is a peculiar oversight, because SCEV already tries to push exts through most everything else. I'll try adding that.

[fhahn]

In D82799#2151699, @nikic wrote:

@fhahn Thanks for taking a look!

For the first diff I checked, the issue appears to be lack of "ext of min/max" to "min/max of ext" canonicalization in SCEV. Which is a peculiar oversight, because SCEV already tries to push exts through most everything else. I'll try adding that.

Sounds good. I could also take a look tomorrow, if you could share a test case.

[nikic]

Abandoning as a variant of this landed in D111495.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

if (LI->getLoopFor(UsePhi->getParent()) != L) {
           return nullptr;
 
         PHINode *WidePhi =
           PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",
                           UsePhi);
         WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
         IRBuilder<> Builder(&*WidePhi->getParent()->getFirstInsertionPt());
         Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
+        SE->forgetValue(UsePhi);
         UsePhi->replaceAllUsesWith(Trunc);
         DeadInsts.emplace_back(UsePhi);
         LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "
                           << *WidePhi << "\n");
       }
       return nullptr;
     }
   }

llvm/lib/Transforms/Utils/LoopUtils.cpp

for (BasicBlock *ExitBB : ExitBlocks) {
     BasicBlock::iterator BBI = ExitBB->begin();
     while ((PN = dyn_cast<PHINode>(BBI++))) {
       if (PN->use_empty())
         continue; // dead use, don't replace it
 
       if (!SE->isSCEVable(PN->getType()))
         continue;
 
-      // It's necessary to tell ScalarEvolution about this explicitly so that
-      // it can walk the def-use list and forget all SCEVs, as it may not be
-      // watching the PHI itself. Once the new exit value is in place, there
-      // may not be a def-use connection between the loop and every instruction
-      // which got a SCEVAddRecExpr for that loop.
-      SE->forgetValue(PN);
-
       // Iterate over all of the values in all the PHI nodes.
       for (unsigned i = 0; i != NumPreds; ++i) {
         // If the value being merged in is not integer or is not defined
         // in the loop, skip it.
         Value *InVal = PN->getIncomingValue(i);
         if (!isa<Instruction>(InVal))
           continue;
 
for (const RewritePhi &Phi : RewritePhiSet) {
 
     // Only do the rewrite when the ExitValue can be expanded cheaply.
     // If LoopCanBeDel is true, rewrite exit value aggressively.
     if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
       DeadInsts.push_back(ExitVal);
       continue;
     }
 
+    // It's necessary to tell ScalarEvolution about this explicitly so that
+    // it can walk the def-use list and forget all SCEVs, as it may not be
+    // watching the PHI itself. Once the new exit value is in place, there
+    // may not be a def-use connection between the loop and every instruction
+    // which got a SCEVAddRecExpr for that loop.
+    SE->forgetValue(Phi.PN);
+
     NumReplaced++;
     Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
     PN->setIncomingValue(Phi.Ith, ExitVal);
 
     // If this instruction is dead now, delete it. Don't do it now to avoid
     // invalidating iterators.
     if (isInstructionTriviallyDead(Inst, TLI))
       DeadInsts.push_back(Inst);