[Utils] Skip RemoveRedundantDbgInstrs in MergeBlockIntoPredecessor (PR47746)

[vsk]

Summary

This patch changes MergeBlockIntoPredecessor to skip the call to
RemoveRedundantDbgInstrs, in effect partially reverting D71480 due to
some compile-time issues spotted in LoopUnroll and SimplifyCFG.

The call to RemoveRedundantDbgInstrs appears to have changed the
worst-case behavior of the merging utility. Loosely speaking, it seems
to have gone from O(#phis) to O(#insts).

It might not be possible to mitigate this by scanning a block to
determine whether there are any debug intrinsics to remove, since such a
scan costs O(#insts).

So: skip the call to RemoveRedundantDbgInstrs. There's surprisingly
little fallout from this, and most of it can be addressed by doing
RemoveRedundantDbgInstrs later. The exception is (the block-local
version of) SimplifyCFG, where it might just be too expensive to call
RemoveRedundantDbgInstrs.

[fhahn]

So: skip the call to RemoveRedundantDbgInstrs. There's surprisingly little fallout from this, and most of it can be addressed by doing RemoveRedundantDbgInstrs later.

As an alternative, would it make sense to have a dedicated pass to eliminate redundant debug instructions, that's run late in the pipeline? not sure if running it once, but for every function will be better or worse in the end. It should be easy to skip for functions without debug info though.

[bjope]

In D88928#2316194, @fhahn wrote:

So: skip the call to RemoveRedundantDbgInstrs. There's surprisingly little fallout from this, and most of it can be addressed by doing RemoveRedundantDbgInstrs later.

As an alternative, would it make sense to have a dedicated pass to eliminate redundant debug instructions, that's run late in the pipeline? not sure if running it once, but for every function will be better or worse in the end. It should be easy to skip for functions without debug info though.

I don't remember exactly, but isn't one goal with removing the redundant dbg instructions early to speed up compilation (when -g is used). It's like saying that we shouldn't remove dead code until late in the pipeline to me (spending time on optimizing the dead code all the way through opt).

Looks like it has been unfortunate to do the RemoveRedundantDbgInstrs inside MergeBlockIntoPredecessor for the CodeGenPrepare use-case, as it can end up merging blocks in several steps (resulting in bad complexity). So for example having an option to MergeBlockIntoPredecessor (or a wrapper) to be able to postpone the cleanup to afterwards in such use-cases seems like a good idea to me.
There actually is a pass that only is used in lit tests (afaik) that is doing this kind of cleanup (RedundantDbgInstElimination). But if we want to cleanup along the way, we might end up wanting to run that pass after every pass that may introduce redundant dbg instrs. In the end that might be more costly, since we wouldn't know if the earlier passes actually did any transformations or not. The currently implementation tries to limit the amount of cleanup by doing it at transforms that are known to introduce redundant dbg instrs.

One thing I realize is that we probaly spend time looking for dbg instrs also in non-debug builds, right? I'm not sure if there is a quick way to check if the IR has dbg instrs or not, to make an early return in RemoveRedundantDbgInstrs if the module/function/basicblock is known to not having any dbg instrs. Any ideas on how to do that?

[vsk]

In D88928#2316235, @bjope wrote:

In D88928#2316194, @fhahn wrote:

So: skip the call to RemoveRedundantDbgInstrs. There's surprisingly little fallout from this, and most of it can be addressed by doing RemoveRedundantDbgInstrs later.

As an alternative, would it make sense to have a dedicated pass to eliminate redundant debug instructions, that's run late in the pipeline? not sure if running it once, but for every function will be better or worse in the end. It should be easy to skip for functions without debug info though.

I don't remember exactly, but isn't one goal with removing the redundant dbg instructions early to speed up compilation (when -g is used). It's like saying that we shouldn't remove dead code until late in the pipeline to me (spending time on optimizing the dead code all the way through opt).

Right.

Looks like it has been unfortunate to do the RemoveRedundantDbgInstrs inside MergeBlockIntoPredecessor for the CodeGenPrepare use-case, as it can end up merging blocks in several steps (resulting in bad complexity). So for example having an option to MergeBlockIntoPredecessor (or a wrapper) to be able to postpone the cleanup to afterwards in such use-cases seems like a good idea to me.

An obstacle here is that code that calls MergeBlockIntoPredecessor tends not to have enough context to pass in a flag to enable RemoveRedundantDbgInstrs at the right time. I can think of two examples:

• SimplifyCFGOpt::simplifyOnce(BB) can do block merging repeatedly. It seems better to call RemoveRedundantDbgInstrs just once in SimplifyCFGOpt::run() after all changes are done.
• CodeGenPrepare::eliminateFallthrough() can also do block merging repeatedly, but it seems better to call RemoveRedundantDbgInstrs after all the merging is done.

There actually is a pass that only is used in lit tests (afaik) that is doing this kind of cleanup (RedundantDbgInstElimination). But if we want to cleanup along the way, we might end up wanting to run that pass after every pass that may introduce redundant dbg instrs. In the end that might be more costly, since we wouldn't know if the earlier passes actually did any transformations or not. The currently implementation tries to limit the amount of cleanup by doing it at transforms that are known to introduce redundant dbg instrs.

One thing I realize is that we probaly spend time looking for dbg instrs also in non-debug builds, right? I'm not sure if there is a quick way to check if the IR has dbg instrs or not, to make an early return in RemoveRedundantDbgInstrs if the module/function/basicblock is known to not having any dbg instrs. Any ideas on how to do that?

I don't think there's a quick way to check whether a function/basicblock has debug instructions (e.g. you can always inline dbg intrinsics into a function without a !dbg attachment). We could change the IR to make that kind of lookup fast. Strawman idea: we could add a NumDebugInstrs bit to BasicBlock or Function, just like llvm::Value has a IsUsedByMD bit, and keep it up-to-date whenever the BasicBlock/Function ilist changes. But I think that idea fails two tests: it's not very general (seems very specific to this problem), and it moves us away from the high-level direction of removing debug insts from the instruction stream.

[jmorse]

Assuming I understand the history correctly, this patch in itself won't introduce any inaccuracy into debug-info, and has a motivating performance example, so LGTM.

As an aside, Vedant wrote:

I don't think there's a quick way to check whether a function/basicblock has debug instructions (e.g. you can always inline dbg intrinsics into a function without a !dbg attachment).

(Genuine question:) wouldn't dbg intrinsics be useless without a DISubprogram attached to the Function though, seeing how there wouldn't be a DW_AT_subprogram in the dwarf for variables to be placed in?

[vsk]

In D88928#2324986, @jmorse wrote:

I don't think there's a quick way to check whether a function/basicblock has debug instructions (e.g. you can always inline dbg intrinsics into a function without a !dbg attachment).

(Genuine question:) wouldn't dbg intrinsics be useless without a DISubprogram attached to the Function though, seeing how there wouldn't be a DW_AT_subprogram in the dwarf for variables to be placed in?

Yes, unless the dbg intrinsic is inlined into a function that does have a DISubprogram (and its scope is correctly fixed up).

[ctetreau]

I pushed D89818, which is based on the patch that I submitted to my downstream to fix this issue.

[ctetreau]

I don't know if this patch as-is exhaustively removes redundant debug instructions in all cases it did before, or if we care, so I can't approve it, but I am OK with this approach.

I would like to see this issue addressed sooner than later though. If this patch is merged, then D89818 should be abandoned.

[vsk]

In D88928#2343046, @ctetreau wrote:

I don't know if this patch as-is exhaustively removes redundant debug instructions in all cases it did before, or if we care, so I can't approve it, but I am OK with this approach.

I would like to see this issue addressed sooner than later though. If this patch is merged, then D89818 should be abandoned.

@ctetreau thanks for taking a look. This patch changes llvm to remove redundant dbg insts in fewer instances than it did before, but I think that's ok. Looking through the history:

• D71480 replaced some hand-rolled duplicated dbg inst removal code with a call to RemoveRedundantDbgInstrs
• The original removal code was added for llvm.org/PR35113 ; I've fixed up LoopRotationUtils.cpp to avoid breaking the associated test

As I mentioned in D89818, I think the RemoveRedundantDbgInstrs behavior should be opt-in as it has a compile-time cost.

I was hoping for another +1 after Jeremy lgtm'd this change to be safe. Seeing as this appears to be time-sensitive, if there aren't any concerns/objections I'll land this by end of day tomorrow (PST).

[ctetreau]

In D88928#2343175, @vsk wrote:

I was hoping for another +1 after Jeremy lgtm'd this change to be safe. Seeing as this appears to be time-sensitive, if there aren't any concerns/objections I'll land this by end of day tomorrow (PST).

It's not *that* time sensitive, it can wait a few days. I just don't want it to fall through the cracks, and I pushed my patch because progress seemed to have stalled (and this patch was billed as being exploratory).

[ctetreau]

Looks good to me.

llvm/lib/CodeGen/CodeGenPrepare.cpp

bool CodeGenPrepare::eliminateFallThrough(Function &F) {
   bool Changed = false;
   // Scan all of the blocks in the function, except for the entry block.
   // Use a temporary array to avoid iterator being invalidated when
   // deleting blocks.
   SmallVector<WeakTrackingVH, 16> Blocks;
   for (auto &Block : llvm::make_range(std::next(F.begin()), F.end()))
     Blocks.push_back(&Block);
 
+  SmallSet<WeakTrackingVH, 16> Preds;
   for (auto &Block : Blocks) {
     auto *BB = cast_or_null<BasicBlock>(Block);
     if (!BB)
       continue;
     // If the destination block has a single pred, then this is a trivial
     // edge, just collapse it.
     BasicBlock *SinglePred = BB->getSinglePredecessor();
 
     // Don't merge if BB's address is taken.
     if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue;
 
     BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
     if (Term && !Term->isConditional()) {
       Changed = true;
       LLVM_DEBUG(dbgs() << "To merge:\n" << *BB << "\n\n\n");
 
       // Merge BB into SinglePred and delete it.
       MergeBlockIntoPredecessor(BB);
+      Preds.insert(SinglePred);
     }
   }
+
+  // (Repeatedly) merging blocks into their predecessors can create redundant
+  // debug intrinsics.
+  for (auto &Pred : Preds)
+    if (auto *BB = cast_or_null<BasicBlock>(Pred))
+      RemoveRedundantDbgInstrs(BB);
+
   return Changed;
 }
 
 /// Find a destination block from BB if BB is mergeable empty block.
 BasicBlock *CodeGenPrepare::findDestBlockOfMergeableEmptyBlock(BasicBlock *BB) {
   // If this block doesn't end with an uncond branch, ignore it.
   BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
   if (!BI || !BI->isUnconditional())

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

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
-  // entry PHI node post-splice.
-  RemoveRedundantDbgInstrs(PredBB);
-
   // Inherit predecessors name if it exists.
   if (!PredBB->hasName())
     PredBB->takeName(BB);
 
   if (LI)
     LI->removeBlock(BB);
 
   if (MemDep)

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

do {
     if (MSSAU && VerifyMemorySSA)
       MSSAU->getMemorySSA()->verifyMemorySSA();
 
     // Now that the CFG and DomTree are in a consistent state again, try to merge
     // the OrigHeader block into OrigLatch.  This will succeed if they are
     // connected by an unconditional branch.  This is just a cleanup so the
     // emitted code isn't too gross in this common case.
     DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
-    MergeBlockIntoPredecessor(OrigHeader, &DTU, LI, MSSAU);
+    BasicBlock *PredBB = OrigHeader->getUniquePredecessor();
+    bool DidMerge = MergeBlockIntoPredecessor(OrigHeader, &DTU, LI, MSSAU);
+    if (DidMerge)
+      RemoveRedundantDbgInstrs(PredBB);
 
     if (MSSAU && VerifyMemorySSA)
       MSSAU->getMemorySSA()->verifyMemorySSA();
 
     LLVM_DEBUG(dbgs() << "LoopRotation: into "; L->dump());
 
     ++NumRotated;
 

llvm/test/Transforms/SimplifyCFG/hoist-dbgvalue-inlined.ll

 ; RUN: opt -simplifycfg -hoist-common-insts=true -S < %s | FileCheck %s
 ; Verify that we don't crash due an invalid !dbg location on the hoisted llvm.dbg.value
 
 define i64 @caller(i64* %ptr, i64 %flag) !dbg !10 {
 init:
   %v9 = icmp eq i64 %flag, 0
   br i1 %v9, label %a, label %b
 
 ; CHECK:  %vala = load i64, i64* %ptr
 ; CHECK-NEXT:  call void @llvm.dbg.value(metadata i64 %vala, metadata [[MD:![0-9]*]]
+; CHECK-NEXT:  call void @llvm.dbg.value(metadata i64 %vala, metadata [[MD]]
 ; CHECK-NEXT:  %valbmasked = and i64 %vala, 1
 
 a:                                              ; preds = %init
   %vala = load i64, i64* %ptr, align 8
   call void @llvm.dbg.value(metadata i64 %vala, metadata !8, metadata !DIExpression()), !dbg !12
   br label %test.exit
 
 b:                                              ; preds = %init
   %valb = load i64, i64* %ptr, align 8
   call void @llvm.dbg.value(metadata i64 %valb, metadata !8, metadata !DIExpression()), !dbg !13
   %valbmasked = and i64 %valb, 1
   br label %test.exit
 
 test.exit:                                      ; preds = %a, %b
   %retv = phi i64 [ %vala, %a ], [ %valbmasked, %b ]
   ret i64 %retv
 }
 
+; CHECK: [[MD]] = !DILocalVariable(name: "var"
+
 ; Function Attrs: nounwind readnone speculatable
 declare void @llvm.dbg.value(metadata, metadata, metadata) #0
 
 attributes #0 = { nounwind readnone speculatable }
 
 !llvm.module.flags = !{!0}
 !llvm.dbg.cu = !{!1}