[Compile Time] Make it possible to skip redundant debuginst removal

[ctetreau]

Summary

MergeBlockIntoPredecessor unconditionally calls RemoveRedundantDbgInstrs,
which iterates twice over the instructions of the basic block.
MergeBlockIntoPredecessor is itself called in a hot inner loop,
and as a result, RemoveRedundantDbgInstrs was taking 98% of
the runtime in some cases, and causing 10 minute compile times in some
downstream workloads.

Make the call to RemoveRedundantDbgInstrs optional in
MergeBlockIntoPredecessor, and call RemoveRedundantDbgInstrs after the
loop is unrolled in LoopUnrollPass. This reduces the runtime usage of
RemoveRedundantDbgInstrs to 3%. There are places it can be moved where
the usage will be lower, but moving it into a function called
"simplifyLoopAfterUnroll" seemed a good fit.

See: Bug 47746

[ctetreau]

This patch is basically the same thing we ended up doing in our downstream to resolve the issue. We're seeing it in LoopUnroll, so that's where we are skipping it.

If this problem crops up in other places, we could do something similar there. And if all the callsites have a mitigation, then we can safely remove RemoveRedundantDbgInstrs from MergeBlockIntoPredecessor

[aprantl]

Is this an NFC patch? If not, can you please add a test case?

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

93–97

please document under what circumstances one would pass true to the last two parameters

llvm/lib/Transforms/Utils/LoopUnroll.cpp

867

please add a comment that explains why passing true is correct/needed/right here.

[ctetreau]

In D89818#2342652, @aprantl wrote:

Is this an NFC patch? If not, can you please add a test case?

This patch is NFC. Before this patch, for each merge in the loop, we remove redundant instructions. After this patch, for each merge in the loop, we defer, then for each basic block in the loop, we remove redundant instructions. Either way, all the redundant debug instructions are removed.

[ctetreau]

address code review issues

[vsk]

IIRC the original motivation for calling RemoveRedundantDbgInsts in MergeBlockIntoPredecessor was to improve compile time. It's been reported that the change inadvertently regressed compile time within SimplifyCFG as well as LoopUnroll. Imo, instead of making all the clients of MergeBlockIntoPredecessor opt-out of something that could be unexpectedly expensive, it would be better if they could opt-in instead (this is the approach taken in D88928). That still leaves open the possibility of making compile-time improvements in a targeted way, based on profiles.

[ctetreau]

I think your patch is reasonable. Mine is more conservative, yours more aggressive. Both solve the problem. If this patch is merged, yours should be abandoned.

I would like to see this issue addressed sooner than later though. This is causing actual problems in our downstream.

[bjope]

As I see it this solution focuses on the problem seen in LoopUnroll. So I agree, it is conservative and simple so if it solves the PR I think it is just fine.

Comparing with the D88928 patch (in its current state), that patch removes the RemoveRedundantDbgInstrs call from MergeBlockIntoPredecessor, but only replaces that with extra calls to RemoveRedundantDbgInstrs in a few places where MergeBlockIntoPredecessor is used (so afaict that patch currently removes a lot of DbgInstr cleanups?). IMO this patch makes it more of an active choice to decide if the removal can be deferred or not. With D88928 it is easier to forget about such cleanups.

An alternative could be to mix the solutions a bit. We could have a version of MergeBlockIntoPredecessor that is doing the cleanup automatically, and one that skips the cleanup but instead returns the predecessor BB when a merge was made. The latter could be used in usecases such as the one in CodeGenPrepare, when we want to collect all the pred blocks in a set and defer calling of RemoveRedundantDbgInstrs for each of those blocks until after the inner loop.

[vsk]

In D89818#2344014, @bjope wrote:

Comparing with the D88928 patch (in its current state), that patch removes the RemoveRedundantDbgInstrs call from MergeBlockIntoPredecessor, but only replaces that with extra calls to RemoveRedundantDbgInstrs in a few places where MergeBlockIntoPredecessor is used (so afaict that patch currently removes a lot of DbgInstr cleanups?). IMO this patch makes it more of an active choice to decide if the removal can be deferred or not. With D88928 it is easier to forget about such cleanups.

I did some digging (documented in D88928) about why we bother calling RemoveRedundantDbgInstrs in the first place, and couldn't find much besides a reference to llvm.org/PR35113. If it's a correctness concern, then we should make the dbg inst cleanup behavior opt-out (that's what this patch does). If it's a compile-time concern, we should make the cleanup behavior opt-in, because doing the cleanup increases the worst-case complexity of MergeBlockIntoPredecessor.

An alternative could be to mix the solutions a bit. We could have a version of MergeBlockIntoPredecessor that is doing the cleanup automatically, and one that skips the cleanup but instead returns the predecessor BB when a merge was made. The latter could be used in usecases such as the one in CodeGenPrepare, when we want to collect all the pred blocks in a set and defer calling of RemoveRedundantDbgInstrs for each of those blocks until after the inner loop.

Assuming that RemoveRedundantDbgInstrs is a compile-time fix: that sounds reasonable, but also more complicated. We might as well just have one version of the utility, and call RemoveRedundantDbgInstrs in cases where it demonstrably improves compile-time.

[vsk]

Friendly ping. On the assumption that the debug inst cleanup in MergeBlockIntoPredecessor was intended to be a compile-time optimization, I propose making it opt-in as the performance impact can be unexpected. I.e., I suggest that we land D88928 soon-ish (tomorrow barring any concerns/objections).

[ctetreau]

The other patch was merged.

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr,
                     MemorySSAUpdater *MSSAU = nullptr);
 
 /// Attempts to merge a block into its predecessor, if possible. The return
 /// value indicates success or failure.
 /// By default do not merge blocks if BB's predecessor has multiple successors.
 /// If PredecessorWithTwoSuccessors = true, the blocks can only be merged
 /// if BB's Pred has a branch to BB and to AnotherBB, and BB has a single
 /// successor Sing. In this case the branch will be updated with Sing instead of
 /// BB, and BB will still be merged into its predecessor and removed.
+///
+/// Pass True to SkipRedundantDebugValElimination in order to skip redundant
+/// debug val elimination. This elimination has O(#instructions) time
+/// complexity, and may result in unreasonably long compile times.
 bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr,
                                LoopInfo *LI = nullptr,
                                MemorySSAUpdater *MSSAU = nullptr,
                                MemoryDependenceResults *MemDep = nullptr,
-                               bool PredecessorWithTwoSuccessors = false);
+                               bool PredecessorWithTwoSuccessors = false,
+                               bool SkipRedundantDebugValElimination = false);
 
 /// Merge block(s) sucessors, if possible. Return true if at least two
 /// of the blocks were merged together.
 /// In order to merge, each block must be terminated by an unconditional
 /// branch. If L is provided, then the blocks merged into their predecessors
 /// must be in L. In addition, This utility calls on another utility:
 /// MergeBlockIntoPredecessor. Blocks are successfully merged when the call to
 /// MergeBlockIntoPredecessor returns true.

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
       Changed |= RecursivelyDeleteDeadPHINode(PN, TLI, MSSAU);
 
   return Changed;
 }
 
 bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU,
                                      LoopInfo *LI, MemorySSAUpdater *MSSAU,
                                      MemoryDependenceResults *MemDep,
-                                     bool PredecessorWithTwoSuccessors) {
+                                     bool PredecessorWithTwoSuccessors,
+                                     bool SkipRedundantDebugValElimination) {
   if (BB->hasAddressTaken())
     return false;
 
   // Can't merge if there are multiple predecessors, or no predecessors.
   BasicBlock *PredBB = BB->getUniquePredecessor();
   if (!PredBB) return false;
 
   // Don't break self-loops.
if (PredecessorWithTwoSuccessors) {
     if (MSSAU)
       if (MemoryUseOrDef *MUD = cast_or_null<MemoryUseOrDef>(
               MSSAU->getMemorySSA()->getMemoryAccess(PredBB->getTerminator())))
         MSSAU->moveToPlace(MUD, PredBB, MemorySSA::End);
   }
   // Add unreachable to now empty BB.
   new UnreachableInst(BB->getContext(), BB);
 
-  // Eliminate duplicate/redundant dbg.values. This seems to be a good place to
-  // do that since we might end up with redundant dbg.values describing the
+  if (!SkipRedundantDebugValElimination) {
+    // Eliminate duplicate/redundant dbg.values. This seems to be a good place
+    // to do that since we might end up with redundant dbg.values describing the
     // entry PHI node post-splice.
     RemoveRedundantDbgInstrs(PredBB);
+  }
 
   // Inherit predecessors name if it exists.
   if (!PredBB->hasName())
     PredBB->takeName(BB);
 
   if (LI)
     LI->removeBlock(BB);
 

llvm/lib/Transforms/Utils/LoopUnroll.cpp

for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
       Instruction *Inst = &*I++;
 
       if (Value *V = SimplifyInstruction(Inst, {DL, nullptr, DT, AC}))
         if (LI->replacementPreservesLCSSAForm(Inst, V))
           Inst->replaceAllUsesWith(V);
       if (isInstructionTriviallyDead(Inst))
         BB->getInstList().erase(Inst);
     }
+    RemoveRedundantDbgInstrs(BB);
   }
 
   // TODO: after peeling or unrolling, previously loop variant conditions are
   // likely to fold to constants, eagerly propagating those here will require
   // fewer cleanup passes to be run.  Alternatively, a LoopEarlyCSE might be
   // appropriate.
 }
 
for (BasicBlock *Latch : Latches) {
     BranchInst *Term = dyn_cast<BranchInst>(Latch->getTerminator());
     assert((Term ||
             (CompletelyUnroll && !LatchIsExiting && Latch == Latches.back())) &&
            "Need a branch as terminator, except when fully unrolling with "
            "unconditional latch");
     if (Term && Term->isUnconditional()) {
       BasicBlock *Dest = Term->getSuccessor(0);
       BasicBlock *Fold = Dest->getUniquePredecessor();
-      if (MergeBlockIntoPredecessor(Dest, &DTU, LI)) {
+      // Deferring redundant debug value elimination. For sufficiently
+      // complicated loop bodies, this can result in multi-minute compile times.
+      if (MergeBlockIntoPredecessor(Dest, &DTU, LI, nullptr, nullptr, false,
+                                    true)) {
         // Dest has been folded into Fold. Update our worklists accordingly.
         std::replace(Latches.begin(), Latches.end(), Dest, Fold);
         UnrolledLoopBlocks.erase(std::remove(UnrolledLoopBlocks.begin(),
                                              UnrolledLoopBlocks.end(), Dest),
                                  UnrolledLoopBlocks.end());
       }
     }
   }