diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -346,6 +346,7 @@ void initializeRAGreedyPass(PassRegistry&); void initializeReachingDefAnalysisPass(PassRegistry&); void initializeReassociateLegacyPassPass(PassRegistry&); +void initializeRedundantDbgInstEliminationPass(PassRegistry&); void initializeRegAllocFastPass(PassRegistry&); void initializeRegBankSelectPass(PassRegistry&); void initializeRegToMemPass(PassRegistry&); diff --git a/llvm/include/llvm/LinkAllPasses.h b/llvm/include/llvm/LinkAllPasses.h --- a/llvm/include/llvm/LinkAllPasses.h +++ b/llvm/include/llvm/LinkAllPasses.h @@ -159,6 +159,7 @@ (void) llvm::createPostDomOnlyViewerPass(); (void) llvm::createPostDomViewerPass(); (void) llvm::createReassociatePass(); + (void) llvm::createRedundantDbgInstEliminationPass(); (void) llvm::createRegionInfoPass(); (void) llvm::createRegionOnlyPrinterPass(); (void) llvm::createRegionOnlyViewerPass(); diff --git a/llvm/include/llvm/Transforms/Scalar.h b/llvm/include/llvm/Transforms/Scalar.h --- a/llvm/include/llvm/Transforms/Scalar.h +++ b/llvm/include/llvm/Transforms/Scalar.h @@ -53,6 +53,13 @@ // Pass *createDeadInstEliminationPass(); +//===----------------------------------------------------------------------===// +// +// RedundantDbgInstElimination - This pass removes redundant dbg intrinsics +// without modifying the CFG of the function. It is a FunctionPass. +// +Pass *createRedundantDbgInstEliminationPass(); + //===----------------------------------------------------------------------===// // // DeadCodeElimination - This pass is more powerful than DeadInstElimination, diff --git a/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h b/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h --- a/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -94,6 +94,10 @@ MemoryDependenceResults *MemDep = nullptr, bool PredecessorWithTwoSuccessors = false); +/// Try to remove redundant dbg.value instructions from given basic block. +/// Returns true if at least one instruction was removed. +bool RemoveRedundantDbgInstrs(BasicBlock *BB); + /// Replace all uses of an instruction (specified by BI) with a value, then /// remove and delete the original instruction. void ReplaceInstWithValue(BasicBlock::InstListType &BIL, diff --git a/llvm/lib/Transforms/Scalar/DCE.cpp b/llvm/lib/Transforms/Scalar/DCE.cpp --- a/llvm/lib/Transforms/Scalar/DCE.cpp +++ b/llvm/lib/Transforms/Scalar/DCE.cpp @@ -25,6 +25,7 @@ #include "llvm/Pass.h" #include "llvm/Support/DebugCounter.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" using namespace llvm; @@ -81,6 +82,43 @@ return new DeadInstElimination(); } +//===--------------------------------------------------------------------===// +// RedundantDbgInstElimination pass implementation +// + +namespace { +struct RedundantDbgInstElimination : public FunctionPass { + static char ID; // Pass identification, replacement for typeid + RedundantDbgInstElimination() : FunctionPass(ID) { + initializeRedundantDbgInstEliminationPass(*PassRegistry::getPassRegistry()); + } + bool runOnFunction(Function &F) override { + if (skipFunction(F)) + return false; + bool Changed = false; + for (auto &BB : F) + Changed |= RemoveRedundantDbgInstrs(&BB); + return Changed; + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + } +}; +} + +char RedundantDbgInstElimination::ID = 0; +INITIALIZE_PASS(RedundantDbgInstElimination, "redundant-dbg-inst-elim", + "Redundant Dbg Instruction Elimination", false, false) + +Pass *llvm::createRedundantDbgInstEliminationPass() { + return new RedundantDbgInstElimination(); +} + +//===--------------------------------------------------------------------===// +// DeadCodeElimination pass implementation +// + static bool DCEInstruction(Instruction *I, SmallSetVector &WorkList, const TargetLibraryInfo *TLI) { diff --git a/llvm/lib/Transforms/Scalar/Scalar.cpp b/llvm/lib/Transforms/Scalar/Scalar.cpp --- a/llvm/lib/Transforms/Scalar/Scalar.cpp +++ b/llvm/lib/Transforms/Scalar/Scalar.cpp @@ -90,6 +90,7 @@ initializeNaryReassociateLegacyPassPass(Registry); initializePartiallyInlineLibCallsLegacyPassPass(Registry); initializeReassociateLegacyPassPass(Registry); + initializeRedundantDbgInstEliminationPass(Registry); initializeRegToMemPass(Registry); initializeRewriteStatepointsForGCLegacyPassPass(Registry); initializeSCCPLegacyPassPass(Registry); diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp --- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -324,6 +324,124 @@ return true; } +/// Remove redundant instructions within sequences of consecutive dbg.value +/// instructions. This is done using a backward scan to keep the last dbg.value +/// describing a specific variable/fragment. +/// +/// BackwardScan strategy: +/// ---------------------- +/// Given a sequence of consecutive DbgValueInst like this +/// +/// dbg.value ..., "x", FragmentX1 (*) +/// dbg.value ..., "y", FragmentY1 +/// dbg.value ..., "x", FragmentX2 +/// dbg.value ..., "x", FragmentX1 (**) +/// +/// then the instruction marked with (*) can be removed (it is guaranteed to be +/// obsoleted by the instruction marked with (**) as the latter instruction is +/// describing the same variable using the same fragment info). +/// +/// Possible improvements: +/// - Check fully overlapping fragments and not only identical fragments. +/// - Support dbg.addr, dbg.declare. dbg.label, and possibly other meta +/// instructions being part of the sequence of consecutive instructions. +static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB) { + SmallVector ToBeRemoved; + SmallDenseSet VariableSet; + for (auto &I : reverse(*BB)) { + if (DbgValueInst *DVI = dyn_cast(&I)) { + DebugVariable Key(DVI->getVariable(), + DVI->getExpression(), + DVI->getDebugLoc()->getInlinedAt()); + auto R = VariableSet.insert(Key); + // If the same variable fragment is described more than once it is enough + // to keep the last one (i.e. the first found since we for reverse + // iteration). + if (!R.second) + ToBeRemoved.push_back(DVI); + continue; + } + // Sequence with consecutive dbg.value instrs ended. Clear the map to + // restart identifying redundant instructions if case we find another + // dbg.value sequence. + VariableSet.clear(); + } + + for (auto &Instr : ToBeRemoved) + Instr->eraseFromParent(); + + return !ToBeRemoved.empty(); +} + +/// Remove redundant dbg.value instructions using a forward scan. This can +/// remove a dbg.value instruction that is redundant due to indicating that a +/// variable has the same value as already being indicated by an earlier +/// dbg.value. +/// +/// ForwardScan strategy: +/// --------------------- +/// Given two identical dbg.value instructions, separated by a block of +/// instructions that isn't describing the same variable, like this +/// +/// dbg.value X1, "x", FragmentX1 (**) +/// +/// dbg.value X1, "x", FragmentX1 (*) +/// +/// then the instruction marked with (*) can be removed. Variable "x" is already +/// described as being mapped to the SSA value X1. +/// +/// Possible improvements: +/// - Keep track of non-overlapping fragments. +static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) { + SmallVector ToBeRemoved; + DenseMap > VariableMap; + for (auto &I : *BB) { + if (DbgValueInst *DVI = dyn_cast(&I)) { + DebugVariable Key(DVI->getVariable(), + NoneType(), + DVI->getDebugLoc()->getInlinedAt()); + auto VMI = VariableMap.find(Key); + // Update the map if we found a new value/expression describing the + // variable, or if the variable wasn't mapped already. + if (VMI == VariableMap.end() || + VMI->second.first != DVI->getValue() || + VMI->second.second != DVI->getExpression()) { + VariableMap[Key] = { DVI->getValue(), DVI->getExpression()}; + continue; + } + // Found an identical mapping. Remember the instruction for later removal. + ToBeRemoved.push_back(DVI); + } + } + + for (auto &Instr : ToBeRemoved) + Instr->eraseFromParent(); + + return !ToBeRemoved.empty(); +} + +bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB) { + bool MadeChanges = false; + // By using the "backward scan" strategy before the "forward scan" strategy we + // can remove both dbg.value (2) and (3) in a situation like this: + // + // (1) dbg.value V1, "x", DIExpression() + // ... + // (2) dbg.value V2, "x", DIExpression() + // (3) dbg.value V1, "x", DIExpression() + // + // The backward scan will remove (2), it is made obsolete by (3). After + // getting (2) out of the way, the foward scan will remove (3) since "x" + // already is described as having the value V1 at (1). + MadeChanges |= removeRedundantDbgInstrsUsingBackwardScan(BB); + MadeChanges |= removeRedundantDbgInstrsUsingForwardScan(BB); + + if (MadeChanges) + LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: " + << BB->getName() << "\n"); + return MadeChanges; +} + void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Value *V) { Instruction &I = *BI; diff --git a/llvm/test/Transforms/DCE/dbg-value-removal.ll b/llvm/test/Transforms/DCE/dbg-value-removal.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/DCE/dbg-value-removal.ll @@ -0,0 +1,112 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -S -redundant-dbg-inst-elim | FileCheck %s + +; All dbg.value with location "!dbg !19" are redundant in the input. +; FIXME: We do not handle non-overlapping/overlapping fragments perfectly yet. + +define dso_local i16 @main(i16 %a1, i16 %a2) local_unnamed_addr #0 !dbg !7 { +; CHECK-LABEL: @main( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[BB0:%.*]] +; CHECK: bb0: +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 13, metadata !13, metadata !DIExpression()), !dbg !16 +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 14, metadata !14, metadata !DIExpression()), !dbg !18 +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 13, metadata !13, metadata !DIExpression()), !dbg !18 +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 12, metadata !12, metadata !DIExpression()), !dbg !18 +; CHECK-NEXT: br label [[BB1:%.*]] +; CHECK: bb1: +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 [[A1:%.*]], metadata !14, metadata !DIExpression()), !dbg !18 +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 888, metadata !13, metadata !DIExpression()), !dbg !18 +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 [[A2:%.*]], metadata !12, metadata !DIExpression()), !dbg !18 +; CHECK-NEXT: [[T1:%.*]] = call i16 @bar(i16 0) +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 [[T1]], metadata !13, metadata !DIExpression()), !dbg !18 +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 [[A2]], metadata !12, metadata !DIExpression(DW_OP_constu, 2, DW_OP_shr, DW_OP_stack_value)), !dbg !18 +; CHECK-NEXT: br label [[BB2:%.*]] +; CHECK: bb2: +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 [[A1]], metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 8)), !dbg !18 +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 [[A1]], metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 8, 8)), !dbg !18 +; CHECK-NEXT: [[T2:%.*]] = call i16 @bar(i16 [[T1]]) +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 [[T2]], metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 8)), !dbg !18 +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 [[A1]], metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 8, 8)), !dbg !19 +; CHECK-NEXT: br label [[BB3:%.*]] +; CHECK: bb3: +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 [[A1]], metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 8)), !dbg !19 +; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 [[A1]], metadata !13, metadata !DIExpression()), !dbg !18 +; CHECK-NEXT: br label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret i16 [[T2]] +; +entry: + br label %bb0 + +bb0: + call void @llvm.dbg.value(metadata i16 999, metadata !12, metadata !DIExpression()), !dbg !19 + call void @llvm.dbg.value(metadata i16 996, metadata !13, metadata !DIExpression()), !dbg !19 + call void @llvm.dbg.value(metadata i16 13, metadata !13, metadata !DIExpression()), !dbg !17 + call void @llvm.dbg.value(metadata i16 998, metadata !12, metadata !DIExpression(DW_OP_constu, 2, DW_OP_shr, DW_OP_stack_value)), !dbg !19 + call void @llvm.dbg.value(metadata i16 14, metadata !14, metadata !DIExpression()), !dbg !16 + call void @llvm.dbg.value(metadata i16 997, metadata !12, metadata !DIExpression()), !dbg !19 + call void @llvm.dbg.value(metadata i16 13, metadata !13, metadata !DIExpression()), !dbg !16 + call void @llvm.dbg.value(metadata i16 12, metadata !12, metadata !DIExpression()), !dbg !16 + br label %bb1 + +bb1: + call void @llvm.dbg.value(metadata i16 %a1, metadata !14, metadata !DIExpression()), !dbg !16 + call void @llvm.dbg.value(metadata i16 888, metadata !13, metadata !DIExpression()), !dbg !16 + call void @llvm.dbg.value(metadata i16 %a2, metadata !12, metadata !DIExpression()), !dbg !16 + %t1 = call i16 @bar(i16 0) + call void @llvm.dbg.value(metadata i16 %a1, metadata !14, metadata !DIExpression()), !dbg !19 + call void @llvm.dbg.value(metadata i16 %t1, metadata !13, metadata !DIExpression()), !dbg !16 + call void @llvm.dbg.value(metadata i16 %a2, metadata !12, metadata !DIExpression(DW_OP_constu, 2, DW_OP_shr, DW_OP_stack_value)), !dbg !16 + br label %bb2 + +bb2: + call void @llvm.dbg.value(metadata i16 %a1, metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 8)), !dbg !19 + call void @llvm.dbg.value(metadata i16 %a1, metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 8, 8)), !dbg !19 + call void @llvm.dbg.value(metadata i16 %a1, metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 8)), !dbg !16 + call void @llvm.dbg.value(metadata i16 %a1, metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 8, 8)), !dbg !16 + %t2 = call i16 @bar(i16 %t1) + call void @llvm.dbg.value(metadata i16 %t2, metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 8)), !dbg !16 + call void @llvm.dbg.value(metadata i16 %a1, metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 8, 8)), !dbg !19 + br label %bb3 + +bb3: + call void @llvm.dbg.value(metadata i16 %a1, metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 8)), !dbg !19 + call void @llvm.dbg.value(metadata i16 %a1, metadata !13, metadata !DIExpression()), !dbg !16 + br label %exit + +exit: + ret i16 %t2 +} + +declare void @llvm.dbg.value(metadata, metadata, metadata) #1 +declare i16 @bar(i16) #2 + +attributes #0 = { noinline nounwind } +attributes #1 = { nounwind readnone speculatable willreturn } +attributes #2 = { noinline nounwind readnone } + +!llvm.dbg.cu = !{!0} +!llvm.module.flags = !{!3, !4, !5} +!llvm.ident = !{!6} + +!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 10.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, globals: !2, nameTableKind: None) +!1 = !DIFile(filename: "foo.c", directory: "") +!2 = !{} +!3 = !{i32 7, !"Dwarf Version", i32 4} +!4 = !{i32 2, !"Debug Info Version", i32 3} +!5 = !{i32 1, !"wchar_size", i32 1} +!6 = !{!"clang version 10.0.0"} +!7 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 8, type: !8, scopeLine: 8, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !11) +!8 = !DISubroutineType(types: !9) +!9 = !{!10} +!10 = !DIBasicType(name: "int", size: 16, encoding: DW_ATE_signed) +!11 = !{!12, !13, !14} +!12 = !DILocalVariable(name: "x", scope: !7, file: !1, line: 9, type: !10) +!13 = !DILocalVariable(name: "y", scope: !7, file: !1, line: 10, type: !10) +!14 = !DILocalVariable(name: "u", scope: !15, file: !1, line: 11, type: !10) +!15 = distinct !DILexicalBlock(scope: !7, file: !1, line: 11, column: 3) +!16 = !DILocation(line: 0, scope: !7) +!17 = !DILocation(line: 0, scope: !7, inlinedAt: !18) +!18 = !DILocation(line: 1, scope: !7) +!19 = !DILocation(line: 77, scope: !7)