[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

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

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5833–5834

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.

5884–5885

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).

5890

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

5906

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–5834

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

5888

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 ↗

(On Diff #335486)

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

5888

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

5888

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/CodeGen/SelectionDAG/SDNodeDbgValue.h

 public:
   // FIXME: These SmallVector sizes were chosen without any kind of performance
   // testing.
   using LocOpVector = SmallVector<SDDbgOperand, 2>;
   using SDNodeVector = SmallVector<SDNode *, 2>;
 
 private:
   LocOpVector LocationOps;
-  SDNodeVector SDNodes;
+  SDNodeVector AdditionalDependencies;
   DIVariable *Var;
   DIExpression *Expr;
   DebugLoc DL;
   unsigned Order;
   bool IsIndirect;
   bool IsVariadic;
   bool Invalid = false;
   bool Emitted = false;
 
 public:
   SDDbgValue(DIVariable *Var, DIExpression *Expr, ArrayRef<SDDbgOperand> L,
              ArrayRef<SDNode *> Dependencies, bool IsIndirect, DebugLoc DL,
              unsigned O, bool IsVariadic)
       : LocationOps(L.begin(), L.end()),
-        SDNodes(Dependencies.begin(), Dependencies.end()), Var(Var), Expr(Expr),
-        DL(DL), Order(O), IsIndirect(IsIndirect), IsVariadic(IsVariadic) {
+        AdditionalDependencies(Dependencies.begin(), Dependencies.end()),
+        Var(Var), Expr(Expr), DL(DL), Order(O), IsIndirect(IsIndirect),
+        IsVariadic(IsVariadic) {
     assert(IsVariadic || L.size() == 1);
     assert(!(IsVariadic && IsIndirect));
   }
 
   /// Returns the DIVariable pointer for the variable.
   DIVariable *getVariable() const { return Var; }
 
   /// Returns the DIExpression pointer for the expression.
   DIExpression *getExpression() const { return Expr; }
 
   ArrayRef<SDDbgOperand> getLocationOps() const { return LocationOps; }
 
   LocOpVector copyLocationOps() const { return LocationOps; }
 
   // Returns the SDNodes which this SDDbgValue depends on.
-  ArrayRef<SDNode *> getSDNodes() const { return SDNodes; }
+  SDNodeVector getSDNodes() const {
+    SDNodeVector Dependencies;
+    for (SDDbgOperand DbgOp : LocationOps)
+      if (DbgOp.getKind() == SDDbgOperand::SDNODE)
+        Dependencies.push_back(DbgOp.getSDNode());
+    Dependencies.append(AdditionalDependencies);
+    return Dependencies;
+  }
 
-  SDNodeVector copySDNodes() const { return SDNodes; }
+  ArrayRef<SDNode *> getAdditionalDependencies() const {
+    return AdditionalDependencies;
+  }
 
   /// Returns whether this is an indirect value.
   bool isIndirect() const { return IsIndirect; }
 
   bool isVariadic() const { return IsVariadic; }
 
   /// Returns the DebugLoc.
   DebugLoc getDebugLoc() const { return DL; }

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

 ///
 /// SDNode
 SDDbgValue *SelectionDAG::getDbgValue(DIVariable *Var, DIExpression *Expr,
                                       SDNode *N, unsigned R, bool IsIndirect,
                                       const DebugLoc &DL, unsigned O) {
   assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
          "Expected inlined-at fields to agree");
   return new (DbgInfo->getAlloc())
-      SDDbgValue(Var, Expr, SDDbgOperand::fromNode(N, R), N, IsIndirect, DL, O,
+      SDDbgValue(Var, Expr, SDDbgOperand::fromNode(N, R), {}, IsIndirect, DL, O,
                  /*IsVariadic=*/false);
 }
 
 /// Constant
 SDDbgValue *SelectionDAG::getConstantDbgValue(DIVariable *Var,
                                               DIExpression *Expr,
                                               const Value *C,
                                               const DebugLoc &DL, unsigned O) {
if (SizeInBits) {
           continue;
       auto Fragment = DIExpression::createFragmentExpression(Expr, OffsetInBits,
                                                              SizeInBits);
       if (!Fragment)
         continue;
       Expr = *Fragment;
     }
 
-    auto NewDependencies = Dbg->copySDNodes();
-    std::replace(NewDependencies.begin(), NewDependencies.end(), FromNode,
-                 ToNode);
+    auto AdditionalDependencies = Dbg->getAdditionalDependencies();
     // Clone the SDDbgValue and move it to To.
     SDDbgValue *Clone = getDbgValueList(
-        Var, Expr, NewLocOps, NewDependencies, Dbg->isIndirect(),
+        Var, Expr, NewLocOps, AdditionalDependencies, Dbg->isIndirect(),
         Dbg->getDebugLoc(), std::max(ToNode->getIROrder(), Dbg->getOrder()),
         Dbg->isVariadic());
     ClonedDVs.push_back(Clone);
 
     if (InvalidateDbg) {
       // Invalidate value and indicate the SDDbgValue should not be emitted.
       Dbg->setIsInvalidated();
       Dbg->setIsEmitted();
case ISD::ADD:
           SmallVector<uint64_t, 3> ExprOps;
           DIExpression::appendOffset(ExprOps, Offset);
           DIExpr = DIExpression::appendOpsToArg(DIExpr, ExprOps, i, true);
           Changed = true;
         }
         (void)Changed;
         assert(Changed && "Salvage target doesn't use N");
 
-        auto NewDependencies = DV->copySDNodes();
-        std::replace(NewDependencies.begin(), NewDependencies.end(), &N,
-                     N0.getNode());
+        auto AdditionalDependencies = DV->getAdditionalDependencies();
         SDDbgValue *Clone = getDbgValueList(DV->getVariable(), DIExpr,
-                                            NewLocOps, NewDependencies,
+                                            NewLocOps, AdditionalDependencies,
                                             DV->isIndirect(), DV->getDebugLoc(),
                                             DV->getOrder(), DV->isVariadic());
         ClonedDVs.push_back(Clone);
         DV->setIsInvalidated();
         DV->setIsEmitted();
         LLVM_DEBUG(dbgs() << "SALVAGE: Rewriting";
                    N0.getNode()->dumprFull(this);
                    dbgs() << " into " << *DIExpr << '\n');

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

for (const Value *V : Values) {
     // this point if it hasn't been done yet.
     SDValue N = NodeMap[V];
     if (!N.getNode() && isa<Argument>(V)) // Check unused arguments map.
       N = UnusedArgNodeMap[V];
     if (N.getNode()) {
       // Only emit func arg dbg value for non-variadic dbg.values for now.
       if (!IsVariadic && EmitFuncArgumentDbgValue(V, Var, Expr, dl, false, N))
         return true;
-      Dependencies.push_back(N.getNode());
       if (auto *FISDN = dyn_cast<FrameIndexSDNode>(N.getNode())) {
         // Construct a FrameIndexDbgValue for FrameIndexSDNodes so we can
         // describe stack slot locations.
         //
         // Consider "int x = 0; int *px = &x;". There are two kinds of
         // interesting debug values here after optimization:
         //
         //   dbg.value(i32* %px, !"int *px", !DIExpression()), and
         //   dbg.value(i32* %px, !"int x", !DIExpression(DW_OP_deref))
         //
         // Both describe the direct values of their associated variables.
+        Dependencies.push_back(N.getNode());
         LocationOps.emplace_back(SDDbgOperand::fromFrameIdx(FISDN->getIndex()));
         continue;
       }
       LocationOps.emplace_back(
           SDDbgOperand::fromNode(N.getNode(), N.getResNo()));
       continue;
     }
 

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)});
+        DbgValueToLocation[DVI] = {
+            DVI->getExpression(),
+            DVI->hasArgList() ? DVI->getRawLocation()
+                              : ValueAsMetadata::get(UndefValue::get(
+                                    DVI->getVariableLocationOp(0)->getType()))};
       }
     }
   }
 }
 
 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 by LSR;
+    // refresh them from the map.
+    auto DbgDIExpr = DbgValueToLocation[DVI].first;
+    DVI->setRawLocation(DbgValueToLocation[DVI].second);
+    DVI->setExpression(DbgDIExpr);
+    for (auto IdxEV : A.second) {
+      auto 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);
         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;