[DebugInfo] Fix incorrect handling of variadic salvaging in Loop Strength Reduce

[StephenTozer]

Summary

This patch fixes two issues observed upon applying D91722 to current main:

The first change has been moved to a separate patch, D99423.

The second issue is that LoopStrengthReduce, when trying to "repair" undef debug values by replacing them with equal values, must first restore the original location metadata. Without variadic debug values, no active restore was necessary, because you would always have a single undef location operand which would be replaced; because of the updated salvaging, it is now possible for the number of operands to change. This causes errors because we cannot identify which post-salvage operands map to the original operands. Restoring the original location metadata before attempting to repair it removes this issue.

[Orlando]

FWIW the SelectionDAG fix LGTM. I'll leave the LSR part to someone more familiar with it.

[jmorse]

I like the direction of the SelectionDAG change; reducing duplication of information is a worthy goal. My knee-jerk reaction is that we need a test for it, but I imagine it's hard to hit something that deep into DAG Combining. If you've got a reproducer to hand, it'd be good to add that as a test, if not maybe we can skip it. IMO it's also worth breaking this off from the LSR modification.

For the LSR part: this definitely wants a test, it's a fairly fragile scenario (recovering a dbg.value that's been salvaged to death), and it seems likely that future patches could miss this scenario. I've put some minor nits inline, but otherwise this all LGTM (with a test).

llvm/lib/CodeGen/SelectionDAG/SDNodeDbgValue.h

141 ↗

(On Diff #330723)

Probably wants a comment explaining what they're in addition _to_.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5833–5836

To confirm my understanding: this swapping of key/value is effectively NFC, right?

5868–5871

A comment pointing out that this is to preserve the syntactic structure of variadic variable locations would help the reader. Producing the Metadata* value as a separately named variable would let you describe its intention in the variables name too.

5888–5910

IMO: this should explicitly say "in a failed salvage attempt", to avoid giving the impression LSR does any salvaging itself right now. I'd also say "reset" rather than refresh, as the latter implies it's making it valid (to me at least, YMMV).

5894

Opinion: just declare Idx as unsigned? Avoids un-necessary uncertainty.

5912

Am I right in thinking that when we reset the operands / expression, and we fail to find an equal Value to replace an operand with, we'll still be left with an undef dbg.value? IMO it'd be good to encode this as an assertion somehow -- it would communicate to the reader our expectation is that an equal expr is found, OR the dbg.value exits the loop as undef. Not finding an equal expr and still being valid should be illegal (AFAIUI).

[StephenTozer]

Remove ISel changes from this patch, address review comments.

[StephenTozer]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5833–5836

More or less; in this case, we're not swapping the key/value, but reordering it. The point being that rather than EqualValues being grouped by <dbg.value, location op index>, we're grouping <location op index, EqualValues> by dbg.value. This is because as of this change, we want to process each dbg.value entirely in one pass.

[markus]

Sorry for the delay, have been on parental leave. Will look at this later today or tomorrow.

Test needed? Or does this fix breakage in an existing test (which one)?

[StephenTozer]

Added test case.

[StephenTozer]

In D98644#2670759, @markus wrote:

Sorry for the delay, have been on parental leave. Will look at this later today or tomorrow.

Test needed? Or does this fix breakage in an existing test (which one)?

A test has been added; as noted in the description however, this patch fixes an issue that only appears when D91722 is added to main (it was added previously but has been reverted), so the test should currently pass even without this patch, but will fail once D91722 is added.

[markus]

Thanks for the test case. I have verified that it fails as expected without this patch (with D91722 applied).

In general this LGTM with the caveat that I am a bit rusty and this code has been modified a few times since my original patch.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5892

Is it really safe to always refresh from the map here? Isn't there a risk that we restore an old pre-LSR location that is no longer valid and if it turns out that we cannot find an, non-deleted, equivalent value in the loop below then we leave the dbg.value with incorrect information and not just undef?

[jmorse]

LGTM with a nit, and modulo @markus 's comment.

llvm/test/Transforms/LoopStrengthReduce/dbg-preserve-2.ll

3–5

Super-nit, but for the future readers, indicating which dbg.value gets salvaged-and-undef'd behind the scenes would really help -- ideally there'd only be one dbg.value in the function, if that's technically possible.

[StephenTozer]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5892

I believe so: the "raw location" that is the first argument of a debug variable intrinsic will be either a DIArgList or a ValueAsMetadata, rather than a direct Value pointer. Both of these classes have handlers for RAUW and value deletion, and so should not point to an invalid location. The only case that could slip past here, I think, is a potential "use before def" situation if a value referred to by the old location metadata is still valid but has sunk past the debug intrinsic; I can put a guard against that to be on the safe side.

[markus]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5892

Ok, sounds good. Feel free to add the guard but I am fine either way.

llvm/include/llvm/IR/IntrinsicInst.h

public:
   Metadata *getRawVariable() const {
     return cast<MetadataAsValue>(getArgOperand(1))->getMetadata();
   }
 
   Metadata *getRawExpression() const {
     return cast<MetadataAsValue>(getArgOperand(2))->getMetadata();
   }
 
+  /// Use of this should generally be avoided; instead,
+  /// replaceVariableLocationOp and addVariableLocationOps should be used where
+  /// possible to avoid creating invalid state.
+  void setRawLocation(Metadata *Location) {
+    return setArgOperand(0, MetadataAsValue::get(getContext(), Location));
+  }
+
   /// Get the size (in bits) of the variable, or fragment of the variable that
   /// is described.
   Optional<uint64_t> getFragmentSizeInBits() const;
 
   /// \name Casting methods
   /// @{
   static bool classof(const IntrinsicInst *I) {
     switch (I->getIntrinsicID()) {

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequiredID(LoopSimplifyID);
   AU.addRequired<IVUsersWrapperPass>();
   AU.addPreserved<IVUsersWrapperPass>();
   AU.addRequired<TargetTransformInfoWrapperPass>();
   AU.addPreserved<MemorySSAWrapperPass>();
 }
 
 using EqualValues = SmallVector<std::tuple<WeakVH, int64_t>, 4>;
 using EqualValuesMap =
-    DenseMap<std::pair<DbgValueInst *, unsigned>, EqualValues>;
-using ExpressionMap = DenseMap<DbgValueInst *, DIExpression *>;
+    DenseMap<DbgValueInst *, SmallVector<std::pair<unsigned, EqualValues>>>;
+using LocationMap =
+    DenseMap<DbgValueInst *, std::pair<DIExpression *, Metadata *>>;
 
 static void DbgGatherEqualValues(Loop *L, ScalarEvolution &SE,
                                  EqualValuesMap &DbgValueToEqualSet,
-                                 ExpressionMap &DbgValueToExpression) {
+                                 LocationMap &DbgValueToLocation) {
   for (auto &B : L->getBlocks()) {
     for (auto &I : *B) {
       auto DVI = dyn_cast<DbgValueInst>(&I);
       if (!DVI)
         continue;
       for (unsigned Idx = 0; Idx < DVI->getNumVariableLocationOps(); ++Idx) {
         // TODO: We can duplicate results if the same arg appears more than
         // once.
for (auto &I : *B) {
             continue;
           auto PhiSCEV = SE.getSCEV(&Phi);
           Optional<APInt> Offset =
               SE.computeConstantDifference(DbgValueSCEV, PhiSCEV);
           if (Offset && Offset->getMinSignedBits() <= 64)
             EqSet.emplace_back(
                 std::make_tuple(&Phi, Offset.getValue().getSExtValue()));
         }
-        DbgValueToEqualSet[{DVI, Idx}] = std::move(EqSet);
-        DbgValueToExpression[DVI] = DVI->getExpression();
+        DbgValueToEqualSet[DVI].push_back({Idx, std::move(EqSet)});
+        // If we fall back to using this raw location, at least one location op
+        // must be dead. A DIArgList will automatically undef arguments when
+        // they become unavailable, but a ValueAsMetadata will not; since we
+        // know the value should be undef, we use the undef value directly here.
+        Metadata *RawLocation =
+            DVI->hasArgList() ? DVI->getRawLocation()
+                              : ValueAsMetadata::get(UndefValue::get(
+                                    DVI->getVariableLocationOp(0)->getType()));
+        DbgValueToLocation[DVI] = {DVI->getExpression(), RawLocation};
       }
     }
   }
 }
 
 static void DbgApplyEqualValues(EqualValuesMap &DbgValueToEqualSet,
-                                ExpressionMap &DbgValueToExpression) {
+                                LocationMap &DbgValueToLocation) {
   for (auto A : DbgValueToEqualSet) {
-    auto DVI = A.first.first;
-    auto Idx = A.first.second;
+    auto *DVI = A.first;
     // Only update those that are now undef.
-    if (!isa_and_nonnull<UndefValue>(DVI->getVariableLocationOp(Idx)))
+    if (!DVI->isUndef())
       continue;
-    for (auto EV : A.second) {
+    // The dbg.value may have had its value or expression changed during LSR by
+    // a failed salvage attempt; refresh them from the map.
+    auto *DbgDIExpr = DbgValueToLocation[DVI].first;
+    DVI->setRawLocation(DbgValueToLocation[DVI].second);
+    DVI->setExpression(DbgDIExpr);
+    assert(DVI->isUndef() && "dbg.value with non-undef location should not "
+                             "have been modified by LSR.");
+    for (auto IdxEV : A.second) {
+      unsigned Idx = IdxEV.first;
+      for (auto EV : IdxEV.second) {
         auto EVHandle = std::get<WeakVH>(EV);
         if (!EVHandle)
           continue;
-      // The dbg.value may have had its value changed by LSR; refresh it from
-      // the map, but continue to update the mapped expression as it may be
-      // updated multiple times in this function.
-      auto DbgDIExpr = DbgValueToExpression[DVI];
-      auto Offset = std::get<int64_t>(EV);
+        int64_t Offset = std::get<int64_t>(EV);
         DVI->replaceVariableLocationOp(Idx, EVHandle);
         if (Offset) {
           SmallVector<uint64_t, 8> Ops;
           DIExpression::appendOffset(Ops, Offset);
           DbgDIExpr = DIExpression::appendOpsToArg(DbgDIExpr, Ops, Idx, true);
         }
         DVI->setExpression(DbgDIExpr);
-      DbgValueToExpression[DVI] = DbgDIExpr;
         break;
       }
     }
   }
+}
 
 static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE,
                                DominatorTree &DT, LoopInfo &LI,
                                const TargetTransformInfo &TTI,
                                AssumptionCache &AC, TargetLibraryInfo &TLI,
                                MemorySSA *MSSA) {
 
   bool Changed = false;
   std::unique_ptr<MemorySSAUpdater> MSSAU;
   if (MSSA)
     MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
 
   // Run the main LSR transformation.
   Changed |=
       LSRInstance(L, IU, SE, DT, LI, TTI, AC, TLI, MSSAU.get()).getChanged();
 
   // Debug preservation - before we start removing anything create equivalence
   // sets for the llvm.dbg.value intrinsics.
   EqualValuesMap DbgValueToEqualSet;
-  ExpressionMap DbgValueToExpression;
-  DbgGatherEqualValues(L, SE, DbgValueToEqualSet, DbgValueToExpression);
+  LocationMap DbgValueToLocation;
+  DbgGatherEqualValues(L, SE, DbgValueToEqualSet, DbgValueToLocation);
 
   // Remove any extra phis created by processing inner loops.
   Changed |= DeleteDeadPHIs(L->getHeader(), &TLI, MSSAU.get());
   if (EnablePhiElim && L->isLoopSimplifyForm()) {
     SmallVector<WeakTrackingVH, 16> DeadInsts;
     const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
     SCEVExpander Rewriter(SE, DL, "lsr", false);
 #ifndef NDEBUG
     Rewriter.setDebugType(DEBUG_TYPE);
 #endif
     unsigned numFolded = Rewriter.replaceCongruentIVs(L, &DT, DeadInsts, &TTI);
     if (numFolded) {
       Changed = true;
       RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts, &TLI,
                                                            MSSAU.get());
       DeleteDeadPHIs(L->getHeader(), &TLI, MSSAU.get());
     }
   }
 
-  DbgApplyEqualValues(DbgValueToEqualSet, DbgValueToExpression);
+  DbgApplyEqualValues(DbgValueToEqualSet, DbgValueToLocation);
 
   return Changed;
 }
 
 bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) {
   if (skipLoop(L))
     return false;
 

llvm/test/Transforms/LoopStrengthReduce/dbg-preserve-2.ll

+; RUN: opt < %s -loop-reduce -S | FileCheck %s
+
+; Test that LSR does not produce invalid debug info when a debug value is
+; salvaged during LSR by adding additional location operands, then becomes
+; undef, and finally recovered by using equal values gathered before LSR.
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+define i32 @_Z3fooiii(i32 %Result, i32 %Step, i32 %Last) local_unnamed_addr !dbg !7 {
+; CHECK-LABEL: @_Z3fooiii(
+entry:
+  call void @llvm.dbg.value(metadata i32 %Result, metadata !12, metadata !DIExpression()), !dbg !17
+  call void @llvm.dbg.value(metadata i32 %Step, metadata !13, metadata !DIExpression()), !dbg !17
+  call void @llvm.dbg.value(metadata i32 %Last, metadata !14, metadata !DIExpression()), !dbg !17
+  call void @llvm.dbg.value(metadata i32 0, metadata !16, metadata !DIExpression()), !dbg !17
+  br label %do.body, !dbg !18
+
+do.body:                                          ; preds = %do.body, %entry
+; CHECK-LABEL: do.body: 
+  %Result.addr.0 = phi i32 [ %Result, %entry ], [ %or, %do.body ]
+  %Itr.0 = phi i32 [ 0, %entry ], [ %add, %do.body ], !dbg !17
+; CHECK-NOT: call void @llvm.dbg.value(metadata !DIArgList
+; CHECK: call void @llvm.dbg.value(metadata i32 %lsr.iv, metadata ![[VAR_ITR:[0-9]+]], metadata !DIExpression()
+  call void @llvm.dbg.value(metadata i32 %Itr.0, metadata !16, metadata !DIExpression()), !dbg !17
+  call void @llvm.dbg.value(metadata i32 %Result.addr.0, metadata !12, metadata !DIExpression()), !dbg !17
+  %add = add nsw i32 %Itr.0, %Step, !dbg !19
+  call void @llvm.dbg.value(metadata i32 %add, metadata !16, metadata !DIExpression()), !dbg !17
+  %call = tail call i32 @_Z3barv(), !dbg !21
+  call void @llvm.dbg.value(metadata i32 %call, metadata !15, metadata !DIExpression()), !dbg !17
+  %shl = shl i32 %call, %add, !dbg !22
+  %or = or i32 %shl, %Result.addr.0, !dbg !23
+  call void @llvm.dbg.value(metadata i32 %or, metadata !12, metadata !DIExpression()), !dbg !17
+  %and = and i32 %call, %Last, !dbg !24
+  %tobool.not = icmp eq i32 %and, 0, !dbg !25
+  br i1 %tobool.not, label %do.end, label %do.body, !dbg !26, !llvm.loop !27
+
+do.end:                                           ; preds = %do.body
+  ret i32 %or, !dbg !30
+}
+
+declare !dbg !31 dso_local i32 @_Z3barv() local_unnamed_addr
+
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+; CHECK: ![[VAR_ITR]] = !DILocalVariable(name: "Itr"
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 13.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "test.cpp", directory: "/")
+!2 = !{}
+!3 = !{i32 7, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{!"clang version 13.0.0"}
+!7 = distinct !DISubprogram(name: "foo", linkageName: "_Z3fooiii", scope: !1, file: !1, line: 3, type: !8, scopeLine: 3, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !11)
+!8 = !DISubroutineType(types: !9)
+!9 = !{!10, !10, !10, !10}
+!10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!11 = !{!12, !13, !14, !15, !16}
+!12 = !DILocalVariable(name: "Result", arg: 1, scope: !7, file: !1, line: 3, type: !10)
+!13 = !DILocalVariable(name: "Step", arg: 2, scope: !7, file: !1, line: 3, type: !10)
+!14 = !DILocalVariable(name: "Last", arg: 3, scope: !7, file: !1, line: 3, type: !10)
+!15 = !DILocalVariable(name: "Bar", scope: !7, file: !1, line: 4, type: !10)
+!16 = !DILocalVariable(name: "Itr", scope: !7, file: !1, line: 5, type: !10)
+!17 = !DILocation(line: 0, scope: !7)
+!18 = !DILocation(line: 6, column: 3, scope: !7)
+!19 = !DILocation(line: 7, column: 9, scope: !20)
+!20 = distinct !DILexicalBlock(scope: !7, file: !1, line: 6, column: 6)
+!21 = !DILocation(line: 8, column: 11, scope: !20)
+!22 = !DILocation(line: 9, column: 20, scope: !20)
+!23 = !DILocation(line: 9, column: 12, scope: !20)
+!24 = !DILocation(line: 10, column: 16, scope: !7)
+!25 = !DILocation(line: 10, column: 12, scope: !7)
+!26 = !DILocation(line: 10, column: 3, scope: !20)
+!27 = distinct !{!27, !18, !28, !29}
+!28 = !DILocation(line: 10, column: 22, scope: !7)
+!29 = !{!"llvm.loop.mustprogress"}
+!30 = !DILocation(line: 11, column: 3, scope: !7)
+!31 = !DISubprogram(name: "bar", linkageName: "_Z3barv", scope: !1, file: !1, line: 1, type: !32, flags: DIFlagPrototyped, spFlags: DISPFlagOptimized, retainedNodes: !2)
+!32 = !DISubroutineType(types: !33)
+!33 = !{!10}