Improve LSR debug-info

[markus]

Summary

This is a prototype implementation of what was discussed in http://lists.llvm.org/pipermail/llvm-dev/2020-September/144990.html

So, given the following input compiled with clang -g -O3 lsrdbg.c -mllvm -print-after-all

#pragma donotinline
void foo(unsigned char *p) {
#pragma clang loop unroll(disable)
  for (unsigned char i = 0; i < 32; i++) {
    p += 3;
    *p = i;
  }
}

the IR shows that after LSR two llvm.dbg.value have been updated to reference %lsr.iv instead of the deleted %p.addr.05 and %add.ptr. Also note the compensation in one of the DIExpression.

*** IR Dump After Canonicalize Freeze Instructions in Loops ***
; Preheader:
entry:
  call void @llvm.dbg.value(metadata i8* %p, metadata <0x10159f90>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x101530a0>)
  call void @llvm.dbg.value(metadata i8 0, metadata <0x1015bb70>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x1015b6c0>)
  br label %for.body, !dbg !DILocation(line: 4, column: 3, scope: <0x1015b6c0>)

; Loop:
for.body:                                         ; preds = %entry, %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 <0x1015bb70>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x1015b6c0>)
  call void @llvm.dbg.value(metadata i8* %p.addr.05, metadata <0x10159f90>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x101530a0>)
  %add.ptr = getelementptr inbounds i8, i8* %p.addr.05, i64 3, !dbg !DILocation(line: 5, column: 7, scope: <0x1015cd00>)
  call void @llvm.dbg.value(metadata i8* %add.ptr, metadata <0x10159f90>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x101530a0>)
  store i8 %i.06, i8* %add.ptr, align 1, !dbg !DILocation(line: 6, column: 8, scope: <0x1015cd00>), !tbaa <0x1015c2f8>
  %inc = add nuw nsw i8 %i.06, 1, !dbg !DILocation(line: 4, column: 38, scope: <0x1015c580>)
  call void @llvm.dbg.value(metadata i8 %inc, metadata <0x1015bb70>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x1015b6c0>)
  %exitcond.not = icmp eq i8 %inc, 32, !dbg !DILocation(line: 4, column: 31, scope: <0x1015c580>)
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body, !dbg !DILocation(line: 4, column: 3, scope: <0x1015b6c0>), !llvm.loop <0x1015d820>

; Exit blocks
for.cond.cleanup:                                 ; preds = %for.body
  ret void, !dbg !DILocation(line: 8, column: 1, scope: <0x101530a0>)
The following llvm.dbg.value needs to be updated:
  {(3 + %p)<nsw>,+,3}<nuw><%for.body> :  call void @llvm.dbg.value(metadata i8* %add.ptr, metadata !13, metadata !DIExpression()), !dbg !16
    {(3 + %p)<nsw>,+,3}<nuw><%for.body> :  %lsr.iv = phi i8* [ %scevgep, %entry ], [ %scevgep7, %for.body ]
      Match with offset 0
  {%p,+,3}<nuw><%for.body> :  call void @llvm.dbg.value(metadata i8* %p.addr.05, metadata !13, metadata !DIExpression()), !dbg !16
    {(3 + %p)<nsw>,+,3}<nuw><%for.body> :  %lsr.iv = phi i8* [ %scevgep, %entry ], [ %scevgep7, %for.body ]
      Match with offset -3
*** IR Dump After Loop Strength Reduction ***
; Preheader:
entry:
  call void @llvm.dbg.value(metadata i8* %p, metadata <0x10159f90>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x101530a0>)
  call void @llvm.dbg.value(metadata i8 0, metadata <0x1015bb70>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x1015b6c0>)
  %scevgep = getelementptr i8, i8* %p, i64 3, !dbg !DILocation(line: 4, column: 3, scope: <0x1015b6c0>)
  br label %for.body, !dbg !DILocation(line: 4, column: 3, scope: <0x1015b6c0>)

; Loop:
for.body:                                         ; preds = %entry, %for.body
  %lsr.iv = phi i8* [ %scevgep, %entry ], [ %scevgep7, %for.body ]
  %i.06 = phi i8 [ 0, %entry ], [ %inc, %for.body ]
  call void @llvm.dbg.value(metadata i8 %i.06, metadata <0x1015bb70>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x1015b6c0>)
  call void @llvm.dbg.value(metadata i8* %lsr.iv, metadata <0x10159f90>, metadata !DIExpression(DW_OP_constu, 3, DW_OP_minus, DW_OP_stack_value)), !dbg !DILocation(line: 0, scope: <0x101530a0>)
  call void @llvm.dbg.value(metadata i8* %lsr.iv, metadata <0x10159f90>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x101530a0>)
  store i8 %i.06, i8* %lsr.iv, align 1, !dbg !DILocation(line: 6, column: 8, scope: <0x1015cd00>), !tbaa <0x1015c2f8>
  %inc = add nuw nsw i8 %i.06, 1, !dbg !DILocation(line: 4, column: 38, scope: <0x1015c580>)
  call void @llvm.dbg.value(metadata i8 %inc, metadata <0x1015bb70>, metadata !DIExpression()), !dbg !DILocation(line: 0, scope: <0x1015b6c0>)
  %scevgep7 = getelementptr i8, i8* %lsr.iv, i64 3, !dbg !DILocation(line: 4, column: 31, scope: <0x1015c580>)
  %exitcond.not = icmp eq i8 %inc, 32, !dbg !DILocation(line: 4, column: 31, scope: <0x1015c580>)
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body, !dbg !DILocation(line: 4, column: 3, scope: <0x1015b6c0>), !llvm.loop <0x1015d820>

; Exit blocks
for.cond.cleanup:                                 ; preds = %for.body
  ret void, !dbg !DILocation(line: 8, column: 1, scope: <0x101530a0>)

[markus]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5878

There must be a better way to get hold of these. I would assume that LSR itself keeps track of the phi-node instructions it builds

5884

There must be a better way to do this. Perhaps we can modify DeleteDeadPHIs to accept an additional std::function argument that replaces the salvageDebugInfo call. It would still default to salvageDebugInfo but would allow us to pass a lambda here that does the SCEV comparison (and possible replace) on the dbg-uses right before an instruction is about to be removed.

[markus]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5884

Actually I see that commit 37b96d51d0cfc82a64598aaae2a567fa77e44de9 introduced a AboutToDeleteCallback that seem to serve exactly this purpose. We just need to expose it a bit further up in DeleteDeadPHIs.

[aprantl]

Could you add test that showcases the effect?

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5817

either we check the result or this should be
auto *UseOfI = cast<Instruction>()

[markus]

Change of appraoch. Instead of hooking into deleteDeadPHIs with an AboutToDeleteCallback we do a pre-pass to store a way the llvm.dbg.value of the loop as well as their SCEV expressions. After LSR has done its thing we go through those stored away llvm.dbg.value and if any of them now has an undef variable location we try to update it using its stored SCEV.

At least this way is clean and simple.

[markus]

Updated with full context patch.

[jmorse]

This is looking good, a few nits inline. Some slightly broader questions: do you know if there's any risk of debug-info affecting decisions made by SCEV, i.e. causing codegen to change when compiling -g? I don't have any reason to believe that could be the case, but it's a fear in the back of my mind.

Why does the DIExpression need to become a temporary / be cloned -- my understanding is that it's immutable metadata once created, so we should be able to keep the raw pointer to it.

I ran a clang-3.4 build with this patch, and according to llvm-locstats roughly 6000 variable locations have left the 0% coverage bucket, while roughly 6000 (potentially the same) variables have entered the 100% coverage bucket. That's about 0.2% of all variables, which is a decent improvement to get.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5795

Can this be brace initialized?

5831

if (!isa<...>(...))
  continue;`

To save some indentation.

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

30

It's best practice to capture the metadata reference number and confirm it further down with

CHECK: ![[VARNUMBER]]  = !DILocalVariable(name: "p"

or similar.

40–41

Best to delete any un-necessary attributes to reduce later maintenence.

[markus]

Fixed most of the review remarks.

[markus]

In D87494#2285378, @jmorse wrote:

This is looking good, a few nits inline. Some slightly broader questions: do you know if there's any risk of debug-info affecting decisions made by SCEV, i.e. causing codegen to change when compiling -g? I don't have any reason to believe that could be the case, but it's a fear in the back of my mind.

I would not expect so. AFAIK it is part of the LLVM debug-info philosophy that no transformation may be affected by the presence of debug-info so that would be a bug (elsewhere) if any transformation behaved differently due to the updated llvm.dbg.value intrinsics. As for that fact that we borrow the SCEV object from LSR to do some additional queries I cant see how that would reasonably affect any further queries passed to that SCEV object. But of course that is just my gut felling.

Why does the DIExpression need to become a temporary / be cloned -- my understanding is that it's immutable metadata once created, so we should be able to keep the raw pointer to it.

Turns out that it did not. I initially got some compilation errors that led me to beleive that the simple pointer approach was not possible. So I guess this is fine as long as the memory of the DIExpression we are pointing at is not released when it is possiby replaced during salvageDebugInfo as part of the normal LSR.

I ran a clang-3.4 build with this patch, and according to llvm-locstats roughly 6000 variable locations have left the 0% coverage bucket, while roughly 6000 (potentially the same) variables have entered the 100% coverage bucket. That's about 0.2% of all variables, which is a decent improvement to get.

Cool. Thanks for taking the time.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5795

Quite possibly but I seem to be unable to pull it off :)

[jmorse]

LGTM; I guess it'd be better if SCEV exposed a helper method, rather than this patch having to expose one, but that's well out of scope.

[bjope]

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

7

Is the target triple needed?

Since the test is put in a general folder and not a target specific one, I guess this could lead to problems if the x86 target isn't built.

[bjope]

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

45

I usually clear these (no gain in exposing my own directory structures in upstream test cases).

[markus]

Addressed minor comments by @bjope

[bjope]

One more nit related to making computeConstantDifference public , but I'm happy with the fixup related to making the test case more target-agnostic.

llvm/include/llvm/Analysis/ScalarEvolution.h

1781

nit: Probably cleaner to move this declaration up into the public section, now when it is made available in the public API.

[markus]

Added safety code to make sure that we are comparing SCEVs of the same Type.

[markus]

Tuns out that previous "safety code" caused problems when bootstraping clang. Apparently it is not safe to do getType() on all SCEVs so instead we now store away the type information and compare on the Value instead of the SCEV.

[markus]

Really minor changes since last approved revision but I would prefer if someone gave a renewed blessing.

[bjope]

I've checked the late "better safe than sorry type checks" and they LGTM.

[nikic]

I've temporarily reverted this change, because it breaks building test-suite using the ReleaseLTO-g.cmake configuration: https://llvm-compile-time-tracker.com/show_error.php?commit=a3caf7f6102dc863425f9714b099af58397f0cd2

I thought this was a crash in clang, but now that I look again this is apparently the linker crashing, which should be GNU ld 2.34 in this case. So possibly the generated debug info exposes a linker bug?

[nikic]

Ah, I forgot that this is an LTO configuration, so naturally it would crash inside the linker :) And indeed, the backtrace shows that the crash occurs during LSR:

0x00007ffff3b2bb7e in ReduceLoopStrength(llvm::Loop*, llvm::IVUsers&, llvm::ScalarEvolution&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::TargetTransformInfo const&, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::MemorySSA*) () from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
(gdb) bt
#0  0x00007ffff3b2bb7e in ReduceLoopStrength(llvm::Loop*, llvm::IVUsers&, llvm::ScalarEvolution&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::TargetTransformInfo const&, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::MemorySSA*) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#1  0x00007ffff3b2e990 in (anonymous namespace)::LoopStrengthReduce::runOnLoop(llvm::Loop*, llvm::LPPassManager&) () from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#2  0x00007ffff40a586b in llvm::LPPassManager::runOnFunction(llvm::Function&) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#3  0x00007ffff44d6858 in llvm::FPPassManager::runOnFunction(llvm::Function&) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#4  0x00007ffff44d73a9 in llvm::FPPassManager::runOnModule(llvm::Module&) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#5  0x00007ffff44d5a03 in llvm::legacy::PassManagerImpl::run(llvm::Module&) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#6  0x00007ffff2b546ce in (anonymous namespace)::codegen(llvm::lto::Config const&, llvm::TargetMachine*, std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)>, unsigned int, llvm::Module&, llvm::ModuleSummaryIndex const&)
    () from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#7  0x00007ffff2b55437 in llvm::lto::backend(llvm::lto::Config const&, std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)>, unsigned int, std::unique_ptr<llvm::Module, std::default_delete<llvm::Module> >, llvm::ModuleSummaryIndex&) () from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#8  0x00007ffff2b4a9ed in llvm::lto::LTO::runRegularLTO(std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)>) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#9  0x00007ffff2b4b001 in llvm::lto::LTO::run(std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)>, std::function<std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)> (unsigned int, llvm::StringRef)>) ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#10 0x00007ffff18604e5 in runLTO() () from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#11 0x00007ffff1862047 in all_symbols_read_hook() ()
   from /home/nikic/llvm-project/build/bin/../lib/LLVMgold.so
#12 0x0000555555584572 in ?? ()
#13 0x00005555555784f7 in ?? ()
#14 0x0000555555564445 in ?? ()
#15 0x00007ffff7c760b3 in __libc_start_main (main=0x555555563df0, argc=253, argv=0x7fffffff87f8, 
    init=<optimized out>, fini=<optimized out>, rtld_fini=<optimized out>, 
    stack_end=0x7fffffff87e8) at ../csu/libc-start.c:308
#16 0x0000555555564aee in ?? ()

[saugustine]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5797

Someone reverted this change while I was tracking down a segfault related to it, but the problem is with this line.
Sometimes D->getVariableLocation() returns null because a variable's location has been lost or can't be found.

A simple fix would be a null check on this line:

if (!V || !SE.isSCEVable(V->getType())))

[markus]

@nikic, @saugustine, thanks for reverting and having a look. I did not receive any notification mail about those build-bot failures AFAICT. I got two but one failure went away on a subsequent run and the other complained about internal compiler error in g++ which seemed unrelated. Anyway I will try to reproduce locally and address the issue as suggested. Thanks again.

[markus]

Addressing the issues with use of stored SCEV after IR had been deleted (see https://reviews.llvm.org/D91711).

The new approach is to, before rewrite, compute a set of SCEV equivalent values (with potential offset) and then store these values with a WeakVH to detect deletion.

After rewrite, for those llvm.dbg.value that now reference undef we pick one of the remaining equivalent values (if any).

So from a black-box point of view operation should be identical to before but now without abusing the SCEV API.

[jmorse]

LGTM, this sounds like it works just as well as before, thanks for pursuing.

(I was wondering whether we need to handle dbg.values with nullptr operands, but with D80264 landed, we don't need to worry about that any more.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L,
                                     SCEVUnionPredicate &A);
   /// Tries to convert the \p S expression to an AddRec expression,
   /// adding additional predicates to \p Preds as required.
   const SCEVAddRecExpr *convertSCEVToAddRecWithPredicates(
       const SCEV *S, const Loop *L,
       SmallPtrSetImpl<const SCEVPredicate *> &Preds);
 
+  /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
+  /// constant, and None if it isn't.
+  ///
+  /// This is intended to be a cheaper version of getMinusSCEV.  We can be
+  /// frugal here since we just bail out of actually constructing and
+  /// canonicalizing an expression in the cases where the result isn't going
+  /// to be a constant.
+  Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS);
+
 private:
   /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
   /// Value is deleted.
   class SCEVCallbackVH final : public CallbackVH {
     ScalarEvolution *SE;
 
     void deleted() override;
     void allUsesReplacedWith(Value *New) override;
private:
   /// prove them individually.
   bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS,
                                     const SCEV *RHS);
 
   /// Try to match the Expr as "(L + R)<Flags>".
   bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
                       SCEV::NoWrapFlags &Flags);
 
-  /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
-  /// constant, and None if it isn't.
-  ///
-  /// This is intended to be a cheaper version of getMinusSCEV.  We can be
-  /// frugal here since we just bail out of actually constructing and
-  /// canonicalizing an expression in the cases where the result isn't going
-  /// to be a constant.
-  Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS);
-
   /// Drop memoized information computed for S.
   void forgetMemoizedResults(const SCEV *S);
 
   /// Return an existing SCEV for V if there is one, otherwise return nullptr.
   const SCEV *getExistingSCEV(Value *V);
 
   /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
   /// pointer.
   bool checkValidity(const SCEV *S) const;

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

 
 #include "llvm/Transforms/Scalar/LoopStrengthReduce.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/IVUsers.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE,
                                AssumptionCache &AC, TargetLibraryInfo &TLI,
                                MemorySSA *MSSA) {
 
   bool Changed = false;
   std::unique_ptr<MemorySSAUpdater> MSSAU;
   if (MSSA)
     MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
 
+  // Debug preservation - record all llvm.dbg.value from the loop as well as
+  // the SCEV of their variable location. Since salvageDebugInfo may change the
+  // DIExpression we need to store the original here as well (i.e. it needs to
+  // be in sync with the SCEV).
+  SmallVector<std::tuple<DbgValueInst *, const SCEV *, DIExpression *>, 32>
+      DbgValues;
+  for (auto &B : L->getBlocks()) {
+    for (auto &I : *B) {
+      if (DbgValueInst *D = dyn_cast<DbgValueInst>(&I)) {
+        auto V = D->getVariableLocation();
+        if (!SE.isSCEVable(V->getType()))
+          continue;
+        auto DS = SE.getSCEV(V);
+        DbgValues.push_back(std::make_tuple(D, DS, D->getExpression()));
+      }
+    }
+  }
+
   // Run the main LSR transformation.
   Changed |=
       LSRInstance(L, IU, SE, DT, LI, TTI, AC, TLI, MSSAU.get()).getChanged();
 
   // 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());
     }
   }
+  // Debug preservation - go through all recorded llvm.dbg.value and for those
+  // that now have an undef variable location use the recorded SCEV to try and
+  // update it. Compare with SCEV of Phi-nodes of loop header to find a
+  // suitable update candidate. SCEV match with constant offset is allowed and
+  // will be compensated for in the DIExpression.
+  if (Changed) {
+    for (auto &D : DbgValues) {
+      auto DbgValue = std::get<DbgValueInst *>(D);
+      auto DbgValueSCEV = std::get<const SCEV *>(D);
+      auto DbgDIExpr = std::get<DIExpression *>(D);
+      if (!isa<UndefValue>(DbgValue->getVariableLocation()))
+        continue;
+      for (PHINode &Phi : L->getHeader()->phis()) {
+        if (!SE.isSCEVable(Phi.getType()))
+          continue;
+        auto PhiSCEV = SE.getSCEV(&Phi);
+        if (DbgValueSCEV->getType() != PhiSCEV->getType())
+          continue;
+        if (Optional<APInt> Offset =
+                SE.computeConstantDifference(DbgValueSCEV, PhiSCEV)) {
+          auto &Ctx = DbgValue->getContext();
+          DbgValue->setOperand(
+              0, MetadataAsValue::get(Ctx, ValueAsMetadata::get(&Phi)));
+          if (Offset.getValue().getSExtValue()) {
+            SmallVector<uint64_t, 8> Ops;
+            DIExpression::appendOffset(Ops, Offset.getValue().getSExtValue());
+            DbgDIExpr = DIExpression::prependOpcodes(DbgDIExpr, Ops, true);
+          }
+          DbgValue->setOperand(2, MetadataAsValue::get(Ctx, DbgDIExpr));
+        }
+      }
+    }
+  }
   return Changed;
 }
 
 bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) {
   if (skipLoop(L))
     return false;
 
   auto &IU = getAnalysis<IVUsersWrapperPass>().getIU();
bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) {
   auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
   MemorySSA *MSSA = nullptr;
   if (MSSAAnalysis)
     MSSA = &MSSAAnalysis->getMSSA();
   return ReduceLoopStrength(L, IU, SE, DT, LI, TTI, AC, TLI, MSSA);
 }
 
 PreservedAnalyses LoopStrengthReducePass::run(Loop &L, LoopAnalysisManager &AM,
                                               LoopStandardAnalysisResults &AR,
                                               LPMUpdater &) {
   if (!ReduceLoopStrength(&L, AM.getResult<IVUsersAnalysis>(L, AR), AR.SE,
                           AR.DT, AR.LI, AR.TTI, AR.AC, AR.TLI, AR.MSSA))
     return PreservedAnalyses::all();
 
   auto PA = getLoopPassPreservedAnalyses();
   if (AR.MSSA)
     PA.preserve<MemorySSAAnalysis>();
   return PA;
 }
 
 char LoopStrengthReduce::ID = 0;
 
 INITIALIZE_PASS_BEGIN(LoopStrengthReduce, "loop-reduce",

llvm/test/DebugInfo/COFF/fpo-shrink-wrap.ll

 
 ; ASM:         calll   _doSomething
 
 ; ASM:         popl    %esi
 ; ASM:         popl    %edi
 ; ASM:         popl    %ebx
 ; ASM: [[EPILOGUE]]:                                 # %return
 ; ASM:         retl    $8
-; ASM: Ltmp10:
+; ASM: Ltmp11:
 ; ASM:         .cv_fpo_endproc
 
 ; Note how RvaStart advances 7 bytes to skip the shrink-wrapped portion.
 ; OBJ: SubSectionType: FrameData (0xF5)
 ; OBJ:    FrameData {
 ; OBJ:      RvaStart: 0x0
 ; OBJ:      CodeSize: 0x34
 ; OBJ:      PrologSize: 0x9

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

+; RUN: opt < %s -loop-reduce -S | FileCheck %s
+
+; Test that LSR preserves debug-info for induction variables.
+
+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 i8* %lsr.iv, metadata ![[MID_p:[0-9]+]], metadata !DIExpression(DW_OP_constu, 3, DW_OP_minus, DW_OP_stack_value)), !dbg !16
+  %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 i8* %lsr.iv, metadata ![[MID_p]], metadata !DIExpression()), !dbg !16
+  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)
+
+!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 12.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "lsrdbg.c", 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 12.0.0"}
+!7 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 2, type: !8, scopeLine: 2, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !12)
+!8 = !DISubroutineType(types: !9)
+!9 = !{null, !10}
+!10 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !11, size: 64)
+!11 = !DIBasicType(name: "unsigned char", size: 8, encoding: DW_ATE_unsigned_char)
+!12 = !{!13, !14}
+!13 = !DILocalVariable(name: "p", arg: 1, scope: !7, file: !1, line: 2, type: !10)
+; CHECK: ![[MID_p]] = !DILocalVariable(name: "p", arg: 1, scope: !7, file: !1, line: 2, type: !10)
+!14 = !DILocalVariable(name: "i", scope: !15, file: !1, line: 4, type: !11)
+!15 = distinct !DILexicalBlock(scope: !7, file: !1, line: 4, column: 3)
+!16 = !DILocation(line: 0, scope: !7)
+!17 = !DILocation(line: 0, scope: !15)
+!18 = !DILocation(line: 4, column: 3, scope: !15)
+!19 = !DILocation(line: 8, column: 1, scope: !7)
+!20 = !DILocation(line: 5, column: 7, scope: !21)
+!21 = distinct !DILexicalBlock(scope: !22, file: !1, line: 4, column: 42)
+!22 = distinct !DILexicalBlock(scope: !15, file: !1, line: 4, column: 3)
+!23 = !DILocation(line: 6, column: 8, scope: !21)
+!24 = !{!25, !25, i64 0}
+!25 = !{!"omnipotent char", !26, i64 0}
+!26 = !{!"Simple C/C++ TBAA"}
+!27 = !DILocation(line: 4, column: 38, scope: !22)
+!28 = !DILocation(line: 4, column: 31, scope: !22)
+!29 = distinct !{!29, !18, !30, !31}
+!30 = !DILocation(line: 7, column: 3, scope: !15)
+!31 = !{!"llvm.loop.unroll.disable"}