[DebugInfo][LoopStrengthReduction] Produce shorter expressions when using scev-based salvaging

[chrisjackson]

Summary

The scev-based salvaging for LSR can sometimes produce unnecessarily verbose expressions. This patch adds logic to detect when the expression for the value to be recovered and the induction variable differ by only a constant offset, Then the expression to derive the current iteration count can be omitted from the dbg.value. This functionality is similar to the previous method for value recovery.

[chrisjackson]

Rebase.

[chrisjackson]

Updated diff so that it is based on the parent patch instead of the main branch,

[aprantl]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6230

Does this mean the presence of debug info would change codegen?

[chrisjackson]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6230

No. I was using this return bool to check if debuginfo had changed, RewriteDVIUsingIterCount() has a similar return bool. However, the return values are currently unused. I will remove this return value for now as it seems its only use is to be possibly confusing.

[chrisjackson]

Remove unused (and potentially confusing) bool return value from functions that rewrite the dbg.value intrinsics.

[chrisjackson]

Required a minor modification as I realised the parent patch (D107016) was unnecessary

[chrisjackson]

Applied clang-format.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

 
 struct DVIRecoveryRec {
   DbgValueInst *DVI;
   DIExpression *Expr;
   Metadata *LocationOp;
   const llvm::SCEV *SCEV;
 };
 
-static bool RewriteDVIUsingIterCount(DVIRecoveryRec CachedDVI,
+static void RewriteDVIUsingIterCount(DVIRecoveryRec CachedDVI,
                                      const SCEVDbgValueBuilder &IterationCount,
                                      ScalarEvolution &SE) {
   // LSR may add locations to previously single location-op DVIs which
   // are currently not supported.
   if (CachedDVI.DVI->getNumVariableLocationOps() != 1)
-    return false;
+    return;
 
   // SCEVs for SSA values are most frquently of the form
   // {start,+,stride}, but sometimes they are ({start,+,stride} + %a + ..).
   // This is because %a is a PHI node that is not the IV. However, these
   // SCEVs have not been observed to result in debuginfo-lossy optimisations,
   // so its not expected this point will be reached.
   if (!isa<SCEVAddRecExpr>(CachedDVI.SCEV))
-    return false;
+    return;
 
   LLVM_DEBUG(dbgs() << "scev-salvage: Value to salvage SCEV: "
                     << *CachedDVI.SCEV << '\n');
 
   const auto *Rec = cast<SCEVAddRecExpr>(CachedDVI.SCEV);
   if (!Rec->isAffine())
-    return false;
+    return;
 
   // Initialise a new builder with the iteration count expression. In
   // combination with the value's SCEV this enables recovery.
   SCEVDbgValueBuilder RecoverValue(IterationCount);
   if (!RecoverValue.SCEVToValueExpr(*Rec, SE))
-    return false;
+    return;
 
   LLVM_DEBUG(dbgs() << "scev-salvage: Updating: " << *CachedDVI.DVI << '\n');
   RecoverValue.applyExprToDbgValue(*CachedDVI.DVI, CachedDVI.Expr);
   LLVM_DEBUG(dbgs() << "scev-salvage: to: " << *CachedDVI.DVI << '\n');
-  return true;
 }
 
-static bool
+static void RewriteDVIUsingOffset(DVIRecoveryRec &DVIRec, llvm::PHINode &IV,
+                                  int64_t Offset) {
+  assert(!DVIRec.DVI->hasArgList() && "Expected single location-op dbg.value.");
+  DbgValueInst *DVI = DVIRec.DVI;
+  SmallVector<uint64_t, 8> Ops;
+  DIExpression::appendOffset(Ops, Offset);
+  DIExpression *OldExpr =
+      DIExpression::prependOpcodes(DVI->getExpression(), Ops, true);
+  LLVM_DEBUG(dbgs() << "scev-salvage: Updating: " << *DVIRec.DVI << '\n');
+  DVI->setExpression(OldExpr);
+  llvm::Value *ValIV = dyn_cast<llvm::Value>(&IV);
+  DVI->replaceVariableLocationOp(
+      0u, llvm::MetadataAsValue::get(DVI->getContext(),
+                                     llvm::ValueAsMetadata::get(ValIV)));
+  LLVM_DEBUG(dbgs() << "scev-salvage: updated with offset to IV: "
+                    << *DVIRec.DVI << '\n');
+}
+
+static void
 DbgRewriteSalvageableDVIs(llvm::Loop *L, ScalarEvolution &SE,
                           llvm::PHINode *LSRInductionVar,
                           SmallVector<DVIRecoveryRec, 2> &DVIToUpdate) {
   if (DVIToUpdate.empty())
-    return false;
+    return;
 
   const llvm::SCEV *SCEVInductionVar = SE.getSCEV(LSRInductionVar);
   assert(SCEVInductionVar &&
          "Anticipated a SCEV for the post-LSR induction variable");
 
-  bool Changed = false;
   if (const SCEVAddRecExpr *IVAddRec =
           dyn_cast<SCEVAddRecExpr>(SCEVInductionVar)) {
     if (!IVAddRec->isAffine())
-      return false;
+      return;
 
+    // The iteratioun count is required to recover location values.
     SCEVDbgValueBuilder IterCountExpr;
     IterCountExpr.pushValue(LSRInductionVar);
     if (!IterCountExpr.SCEVToIterCountExpr(*IVAddRec, SE))
-      return false;
+      return;
 
     LLVM_DEBUG(dbgs() << "scev-salvage: IV SCEV: " << *SCEVInductionVar
                       << '\n');
 
     // Needn't salvage if the location op hasn't been undef'd by LSR.
     for (auto &DVIRec : DVIToUpdate) {
       if (!DVIRec.DVI->isUndef())
         continue;
 
       // Some DVIs that were single location-op when cached are now multi-op,
       // due to LSR optimisations. However, multi-op salvaging is not yet
       // supported by SCEV salvaging. But, we can attempt a salvage by restoring
       // the pre-LSR single-op expression.
       if (DVIRec.DVI->hasArgList()) {
         if (!DVIRec.DVI->getVariableLocationOp(0))
           continue;
         llvm::Type *Ty = DVIRec.DVI->getVariableLocationOp(0)->getType();
         DVIRec.DVI->setRawLocation(
             llvm::ValueAsMetadata::get(UndefValue::get(Ty)));
-        DVIRec.DVI->setExpression(DVIRec.Expr);
       }
+      // LSR may have updated the expression, so restore to the expression
+      // that corresponds to te cached SCEV.
+      DVIRec.DVI->setExpression(DVIRec.Expr);
+
+      LLVM_DEBUG(dbgs() << "scev-salvage: value to recover SCEV: "
+                        << *DVIRec.SCEV);
 
-      Changed |= RewriteDVIUsingIterCount(DVIRec, IterCountExpr, SE);
+      // Create a simple expression if the IV and value to salvage SCEVs
+      // start values differ by only a constant value.
+      if (Optional<APInt> Offset =
+              SE.computeConstantDifference(DVIRec.SCEV, SCEVInductionVar)) {
+        if (Offset.getValue().getMinSignedBits() <= 64)
+          RewriteDVIUsingOffset(DVIRec, *LSRInductionVar,
+                                           Offset.getValue().getSExtValue());
+      } else {
+        RewriteDVIUsingIterCount(DVIRec, IterCountExpr, SE);
+      }
     }
   }
-  return Changed;
 }
 
 /// Identify and cache salvageable DVI locations and expressions along with the
 /// corresponding SCEV(s). Also ensure that the DVI is not deleted before
 static void
 DbgGatherSalvagableDVI(Loop *L, ScalarEvolution &SE,
                        SmallVector<DVIRecoveryRec, 2> &SalvageableDVISCEVs,
                        SmallSet<AssertingVH<DbgValueInst>, 2> &DVIHandles) {

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

-; RUN: opt < %s -loop-reduce -S | FileCheck %s
+; RUN: opt -loop-reduce -S %s | FileCheck %s
 
-; Test that LSR preserves debug-info for induction variables.
+;; Test that LSR preserves debug-info for induction variables and scev-based
+;; salvaging produces short DIExpressions that use a constant offset from the
+;; induction variable.
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
 define dso_local void @foo(i8* nocapture %p) local_unnamed_addr !dbg !7 {
 ; CHECK-LABEL: @foo(
 entry:
   call void @llvm.dbg.value(metadata i8* %p, metadata !13, metadata !DIExpression()), !dbg !16
   call void @llvm.dbg.value(metadata i8 0, metadata !14, metadata !DIExpression()), !dbg !17
   br label %for.body, !dbg !18
 
 for.cond.cleanup:                                 ; preds = %for.body
   ret void, !dbg !19
 
 for.body:                                         ; preds = %entry, %for.body
 ; CHECK-LABEL: for.body:
   %i.06 = phi i8 [ 0, %entry ], [ %inc, %for.body ]
   %p.addr.05 = phi i8* [ %p, %entry ], [ %add.ptr, %for.body ]
   call void @llvm.dbg.value(metadata i8 %i.06, metadata !14, metadata !DIExpression()), !dbg !17
   call void @llvm.dbg.value(metadata i8* %p.addr.05, metadata !13, metadata !DIExpression()), !dbg !16
 ; CHECK-NOT: call void @llvm.dbg.value(metadata i8* undef
-; CHECK: call void @llvm.dbg.value(metadata !DIArgList(i8* %lsr.iv, i8* %p), metadata ![[MID_p:[0-9]+]], metadata !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_consts, 3, DW_OP_LLVM_arg, 1, DW_OP_plus, DW_OP_minus, DW_OP_consts, 3, DW_OP_div, DW_OP_consts, 3, DW_OP_mul, DW_OP_LLVM_arg, 1, DW_OP_plus, DW_OP_stack_value))
+; CHECK: all void @llvm.dbg.value(metadata i8* %lsr.iv, metadata ![[MID_p:[0-9]+]],  metadata !DIExpression(DW_OP_constu, 3, DW_OP_minus, DW_OP_stack_value))
   %add.ptr = getelementptr inbounds i8, i8* %p.addr.05, i64 3, !dbg !20
   call void @llvm.dbg.value(metadata i8* %add.ptr, metadata !13, metadata !DIExpression()), !dbg !16
 ; CHECK-NOT: call void @llvm.dbg.value(metadata i8* undef
-; CHECK: call void @llvm.dbg.value(metadata !DIArgList(i8* %lsr.iv, i8* %p), metadata ![[MID_p]], metadata !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_consts, 3, DW_OP_LLVM_arg, 1, DW_OP_plus, DW_OP_minus, DW_OP_consts, 3, DW_OP_div, DW_OP_consts, 3, DW_OP_mul, DW_OP_consts, 3, DW_OP_LLVM_arg, 1, DW_OP_plus, DW_OP_plus, DW_OP_stack_value))
+; CHECK: call void @llvm.dbg.value(metadata i8* %lsr.iv, metadata ![[MID_p]], metadata !DIExpression())
   store i8 %i.06, i8* %add.ptr, align 1, !dbg !23, !tbaa !24
   %inc = add nuw nsw i8 %i.06, 1, !dbg !27
   call void @llvm.dbg.value(metadata i8 %inc, metadata !14, metadata !DIExpression()), !dbg !17
   %exitcond.not = icmp eq i8 %inc, 32, !dbg !28
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body, !dbg !18, !llvm.loop !29
 }
 
 declare void @llvm.dbg.value(metadata, metadata, metadata)