[debuginfo][lsr] SCEV-based salvaging for LoopStrengthReduction

[chrisjackson]

Summary

This patch extends salvaging of debuginfo in the Loop Strength Reduction (LSR)
pass by translating Scalar Evaluations (SCEV) into DIExpressions. The method is
as follows:

Cacheing Step
Pre-lsr, Examine the DVIs (dbg.value) in the loop and cache information on
those that are deemed salvageable (the location op has a SCEV that can be
translated toa DIExpression). The location op, SCEV for the location op and
the DIExpr are stored in a record. Currently only old-style single location
op DVI are salvageable, but the code is readily extensible to multiple ops
and generates multi-location DVI if necessary during the salvage step.
Salvaging of variadic debug values is the likely next iteration of this
patch, if accepted.

Obtain the Loop Induction Variable (IV)
The Loop class provides two methods to get the IV. Sometimes these fail to
return anything (even in the presence of a loop.body block with a PHI node
labelled 'lsr.iv'). When these methods fail, pick a SCEVable PHI node from
the loop header and use this as the IV. A similar PHI-node selection is
made in the current lsr salvage method DbgGatherEqualValues().

Induction Variable to iteration count DIExpr translation
The SCEV for the IV/PHI node is translated to a DIExpr that results in the
current iteratoun count.

Salvage
The cached DVI are examined. If the location has been marked as unavailable,
Generate an expression that enables the value to be recovered. The
expression uses the iteration count and the location op's SCEV that was
cached to calculate the value.

I have stripped the the existing salvaging as it is capable of recovering only a
subset of the source values recovered by this implementation. However, this more
general method relies on deriving the iteration count. So, in some cases a
longer DIExpression is produced compared to the exiting method. If this is
deemed unsatisfactory there are two options:

Restore the previous functionality and select that method of salvaging when
possible. This is probably not as messy as it sounds, as I have used similar
methods for cacheing data of the salvageable DVIs. Simply restore some of the
functionality to DbgGatherSalvagableDVI() and prioritise rewriting DVIs using
constant offsets of a phi node value.

I expect this is very little work. An important detail is that the new method
caches salvageable DVI slightly earlier in ReduceLoopStrength() than the
existing method.

Have a function that finds no-ops in the generated DIExpression once the
iteration count and source value DIExpressions are combined. This will be more
complicated than the first option, but may be able to simplify a greater
number of cases.
This is not as simple, but I'm sure simplifying stack-based arithmetic is well
understood and I expect implementations exist.

There are implementation limitations.

Support top-level SCEVs for values that are SCEVCommutativeExpr. A SCEV is
of the form {Start,+,stride}, a recurrence relation, with the start applied
at initialisation and stride applied per-iteration. In LLVM this is known as
a SCEVAddRecExpr However, some values cannot be fully expressed in this
form as they are dependant on multiple phis. In this case one or more
SCEVCommutativeExpr wrap the SCEVAddRecExpr e.g.
(({start,+stride} * %a * %b) + %c).
I did not encounter these expressions when examining values that had been
optimised out, some functionality to tranlate these SCEVs has been omitted.

Recovery of DIExpressions that had multiple location ops before
LSR. Note thatsalvaged DVI with multiple location ops can be generated. DVI
with a single location op and a non-empty DIExpression are salvageable.
To implement salavaging of variadic DVI the append(DIExpr*) function must be
altered to append referenced location Ops to the SCEVDbgBuilders Values
vector. If any of these are now 'undef', then generate an expression to
recover the value.

Translation of chain (non-affine) SCEVs. LLVM has a C++
implementation that evaluates a chain SCEV with the iteration number that
should prove useful.

Translation of nested SCEVAddRecs. These are SCEVs with a loop-variant start
value and are created by nested loops.

MinMax SCEVs have not been addressed. I intended to add a push() function for
these when one was encountered. However, not a single test in the lit
Transmforms suite appeared to generate any.

[djtodoro]

@chrisjackson thanks for working on this!

(I've just started looking into this, so I've included a few nits for now.)

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5850

SCEVDbgValueBuilder instead?

5851

SCEVDbgBuilder() = default;

5917

const auto& ?

[chrisjackson]

Updated with changes suggested by @djtodoro

[markus]

I like this approach. It seems a lot more elaborate than my original patch from last fall. If any of my input is requested I will be on vacation for the three coming weeks so it likely wont happen until after that. Anyway thanks for working on this!

[lebedev.ri]

Correct me if i'm misremembering things, but weren't there something like that (SCEV-driven debuginfo salvaging/recovery) already,
and it had problems with holding to the dead IR, and was removed because of that?
Does have similar correctness concerns?

[markus]

In D105207#2862867, @lebedev.ri wrote:

Correct me if i'm misremembering things, but weren't there something like that (SCEV-driven debuginfo salvaging/recovery) already,
and it had problems with holding to the dead IR, and was removed because of that?

There was and it was briefly removed before being re-landed again after the issues with holding on to dead IR were addressed (2a6782bb9f1d6).

[chrisjackson]

Applied clang-format.

[chrisjackson]

Prevent a couple of warnings that had escaped attention and correct a call to clear().

[chrisjackson]

Ping.

[chrisjackson]

This change improves the selection of the IV, by using the PHi node inserted by ScalarEvolutionExpander, which is typically called "%lsr.iv" or similar. The decision to do this resulted from analysis of a build of clang3.4. While the previous method of using Loop->getInductionVariable()/getCanonicalInductionVariable() provided correct IVs, these tended to be relatively short lived and were often optimised away by subsequent passes. Some care is needed in using this PHi as ScalarEvolutionExpander holds Maps of handles to the new PHi node.

[chrisjackson]

Replace passing of pointer to IV and clear() call with a WeakVH..

[chrisjackson]

Adjusted new IV selection when multiple IVs are produced by ScalarEvolutionExpander.

[jmorse]

Looks good in principle; I've added some nits, and there are a couple of things that need to be revised,

• I think the DWARF stack operands go on in the wrong order for casts, plus it needs test coverage,
• Fail gracefully with unrecognised casts rather than asserting.
• InsertedIVs needs to be clear()'able from SCEVExpander

CC @reames and @fhahn who appear to frequently touch SCEV -- this patch exports a vector of induction variables from SCEVExpander, which we assume is OK as SCEVExpander already exports inserted instructions and similar. The induction variables are used to salvage variable locations when a Value is optimised out of a loop during strength reduction. CCing to make you aware of the API change.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5600

Performance-nit: could be a const reference to WeakVH instead of constructing a new one each time around the loop.

5927

Mega nit, I think the style convention is to pre-increment

5940–5941

Doesn't the DWARF stack work by operating on things already pushed onto the stack; and thus shouldn't the Inner value be pushed onto the stack before the convert operation is? (Like you do with "div" below).

Possibly I've missed something; but there should also definitely be a test that covers such casting, and it doesn't look like the tests cover anything that produces DW_OP_LLVM_convert.

5944–5947

Can we not use pushSCEV for Inner in all circumstances and not expand the if/else cases?

5959–5960

This probably wants to return false, rather than assert, better to drop debug-info than stop compiling.

(If the four casts listed cover all cast types, even better would be putting that in a call to assert, rather than using a conditional).

5966

clang-format? I suspect the empty line doesn't meet the style guidelines.

6132

6137–6138

Redundant given the above conditional?

6179–6180

clang-format

6234

[jmorse]

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

196–198

The style in this class appears to be that data fields are private and at the top of the class declaration; public accessors near the bottom. IMO, to fit in with the style, this vector should move towards where InsertedValues is declared, with a public accessor that returns a const reference.

204–205

You're going to need to clear InsertedIVs here.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6242

if (!IV) continue;? Avoid extra indentation, same with the extra condition below.

llvm/test/Transforms/LoopStrengthReduce/debuginfo-scev-variadic-value-0.ll

62 ↗

(On Diff #360727)

NB, we usually strip un-necessary attributes to avoid needless maintenance; see also @djtodoro 's meta-burn tool on the mailing list. (Probably not necessary for these tests as they're fairly small already).

[chrisjackson]

After a rebase I observed additional DVIs that were single location op when cached (pre-LSR) but had multiple location ops post-LSR, when scev-salvaging was applied. Instead of skipping these, restore the pre-LSR information and attempt SCEV salvaging.

Thanks for the review @jmorse, I will address your comments next.

[chrisjackson]

Apply changes in response to @jmorse's review. Additionally:

• Make LSR IV vector private and add accessor.
• Collapse shortened PushCast() into PushSCEV().
• Fix formatting.
• Fix a mistake in pushSCEV()'s call to pushArithmeticImpl().

A lit test covering pushCast will follow.

[chrisjackson]

Added a lit test that covers PushCast(), which translates SCEVCastExpr. Removed some unnecessary details from the existing tests and changed the test names to something more descriptive.

[chrisjackson]

Rebased.

[chrisjackson]

Applied clang-format.

[jmorse]

Thanks for the additional test; ideally the "switching dbg.value(!DIArgList..." back to single-value dbg.values would be covered by a test case too, just to ensure that this doesn't change in the future. LGTM with some nits.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

86

209

IIRC, this needs to be SmallVectorImpl to abstract the size of the underlying vector from the way of accessing it.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

2091

Similarly wants to be SmallVectorImpl to avoid relying on the vector size detail.

5964–5966

I don't quite get why we're willing to return-false if there are unrecognised operators; but assert false if there are unrecognised cast operators. Are these four classes the only derived classes from SCEVCastExpr, and the idea is to fire the assertion if someone adds another? If so, a comment to that effect would be good.

6194–6204

Ideally would want a test.

[chrisjackson]

Applied changes requested by @jmorse: changed accessors to use SmallVectorImpl and added a comment in pushCast().
The path covering the salvage of dbg.value that were changed from single location op to multi location op by LSR is covered already e.g. debuginfo-scev-salvage-1.ll. I'm not certain how to make this clear as all the modifications to the intrinsic occur within the pass.

[chrisjackson]

Corrected a comment.

[chrisjackson]

• Add 'REQUIRES' clause to lit tests to prevent failure on aarch64.
• A failure on buildbot sanitixer-X86_64-linux indicates that SCEVUknown::getValue() can return nullptr. Account for this by returning false and abandoning the salvage attempt.

[chrisjackson]

Added missing RESTRICT in lit test.

[mstorsjo]

This causes crashes for me, I’ll provide reproduction samples shortly.

The release branch has been created, so whatever fixes/reverts are done has to be made similarly for the release branch, cc @tstellar.

[mstorsjo]

The crash is reproducible with this reduced sample:

$ cat repro.c 
struct a { 
  char *b
} static c; 
d(());
e(struct a *f) { d(f->b); }
g() { 
  while (h())
    e(&c);
}
$ clang -target x86_64-linux-gnu -c -g -O2 repro.c

[Abpostelnicu]

I think this introduced a build crash on Firefox. I'm saying this because the build crash occurs in the function touched by this patch, and the yesterday build, that didn't have this patch worked just fine!

[chrisjackson]

Thanks for the reports, I have reverted and will look into the crash ASAP.

[Abpostelnicu]

In D105207#2909571, @chrisjackson wrote:

Thanks for the reports, I have reverted and will look into the crash ASAP.

Thank you for doing this! At Mozilla we have a nightly build with clang-trunk for Firefox in order to test performance degradation or build failures with the latest clang trunk.

[chrisjackson]

getVariableLocationOp() can sometimes return nullptr. Guard against this.

[chrisjackson]

Remove erroneous assert.

[mstorsjo]

In D105207#2909571, @chrisjackson wrote:

Thanks for the reports, I have reverted and will look into the crash ASAP.

Thanks! Can you make sure the 13.x release branch is fixed too? (I guess it's best to revert there too, and then possibly backport the reapplied version of the patch if deemed relevant?)

[chrisjackson]

In D105207#2911458, @mstorsjo wrote:

In D105207#2909571, @chrisjackson wrote:

Thanks for the reports, I have reverted and will look into the crash ASAP.

Thanks! Can you make sure the 13.x release branch is fixed too? (I guess it's best to revert there too, and then possibly backport the reapplied version of the patch if deemed relevant?)

Of course, I will revert the commit in 13.x release.

[chrisjackson]

In D105207#2911458, @mstorsjo wrote:

In D105207#2909571, @chrisjackson wrote:

Thanks for the reports, I have reverted and will look into the crash ASAP.

Thanks! Can you make sure the 13.x release branch is fixed too? (I guess it's best to revert there too, and then possibly backport the reapplied version of the patch if deemed relevant?)

The 13.x release branch has been reverted, as requested. I hope to land the updated commit in that branch too.

[mstorsjo]

In D105207#2912050, @chrisjackson wrote:

In D105207#2911458, @mstorsjo wrote:

In D105207#2909571, @chrisjackson wrote:

Thanks for the reports, I have reverted and will look into the crash ASAP.

Thanks! Can you make sure the 13.x release branch is fixed too? (I guess it's best to revert there too, and then possibly backport the reapplied version of the patch if deemed relevant?)

The 13.x release branch has been reverted, as requested.

Thanks!

I hope to land the updated commit in that branch too.

Please hold off of that for a little while, as the updated version still breaks things for me.

[mstorsjo]

Unreduced repro: https://martin.st/temp/d3dx-preproc.c

clang -target aarch64-linux-gnu -w -c -g -O2 d3dx-preproc.c

[jmorse]

(Chris is out today,)

In D105207#2912487, @mstorsjo wrote:

Unreduced repro: https://martin.st/temp/d3dx-preproc.c

clang -target aarch64-linux-gnu -w -c -g -O2 d3dx-preproc.c

Thanks for the repo -- I've just pushed up rG2537120c8 as an obvious fix, none affine expressions are being fed to a function that doesn't expect them, and it's safe to return and not salvage variable locations in that case. I think it's just a case of an assertion being insufficiently filtered for.

If there's more / continued turbulence then we'll revert though, and we'll add test coverage for non-affine SCEVs being salvaged either way.

[mstorsjo]

In D105207#2913088, @jmorse wrote:

(Chris is out today,)

In D105207#2912487, @mstorsjo wrote:

Unreduced repro: https://martin.st/temp/d3dx-preproc.c

clang -target aarch64-linux-gnu -w -c -g -O2 d3dx-preproc.c

Thanks for the repo -- I've just pushed up rG2537120c8 as an obvious fix, none affine expressions are being fed to a function that doesn't expect them, and it's safe to return and not salvage variable locations in that case. I think it's just a case of an assertion being insufficiently filtered for.

If there's more / continued turbulence then we'll revert though, and we'll add test coverage for non-affine SCEVs being salvaged either way.

Thanks for the quick fix on this matter! For now I think it seems like this issue is fixed wrt the code I test build regularly, but I'll know more exhaustively tomorrow.

[tstellar]

Please backport whatever is necessary to fix this in the release/13.x branch (or file a bug and I can do it).

[mstorsjo]

In D105207#2915494, @tstellar wrote:

Please backport whatever is necessary to fix this in the release/13.x branch (or file a bug and I can do it).

AFAIK this was reverted in the release branch already, in 67d0736b14c7888e63af16dcc71129ce07383010, so the branch should be good wrt that. @chrisjackson expressed a desire to backport the working version of the commit though.

The current reapplied version of this in the main branch with the fix from rG2537120c8 seems to work fine for me now.

[tstellar]

@chrisjackson Should we backport rG2537120c8 ?

[JosephTremoulet]

We've got a regression (assertion failure) with this change that didn't get fixed with 2537120c870c. I've opened PR 51329 for it. If this change gets backported to release/13.x, we'll need the fix for this assertion failure to also get backported.

[chrisjackson]

Apologies for thre slow response, I currently have covid so I needed some time off. Thanks for reporting the failure I will attempt to address the assertion failure today. If I fix that then I am keen for this to be backported.

[chrisjackson]

In D105207#2922863, @JosephTremoulet wrote:

We've got a regression (assertion failure) with this change that didn't get fixed with 2537120c870c. I've opened PR 51329 for it. If this change gets backported to release/13.x, we'll need the fix for this assertion failure to also get backported.

Please see D107348 for a simple patch that provides a fix.

[JosephTremoulet]

In D105207#2924918, @chrisjackson wrote:

Apologies for thre slow response, I currently have covid so I needed some time off. Thanks for reporting the failure I will attempt to address the assertion failure today. If I fix that then I am keen for this to be backported.

In D105207#2922863, @JosephTremoulet wrote:

We've got a regression (assertion failure) with this change that didn't get fixed with 2537120c870c. I've opened PR 51329 for it. If this change gets backported to release/13.x, we'll need the fix for this assertion failure to also get backported.

Please see D107348 for a simple patch that provides a fix.

Thanks for the quick turnaround. I've verified that 21ee38e24f98 fixes the original issues in our rolling tests as well as the reduced repro. I'm happy for this change to get backported along with 21ee38e24f98.

[chrisjackson]

In D105207#2926535, @JosephTremoulet wrote:

In D105207#2924918, @chrisjackson wrote:

Apologies for thre slow response, I currently have covid so I needed some time off. Thanks for reporting the failure I will attempt to address the assertion failure today. If I fix that then I am keen for this to be backported.

In D105207#2922863, @JosephTremoulet wrote:

We've got a regression (assertion failure) with this change that didn't get fixed with 2537120c870c. I've opened PR 51329 for it. If this change gets backported to release/13.x, we'll need the fix for this assertion failure to also get backported.

Please see D107348 for a simple patch that provides a fix.

Thanks for the quick turnaround. I've verified that 21ee38e24f98 fixes the original issues in our rolling tests as well as the reduced repro. I'm happy for this change to get backported along with 21ee38e24f98.

My pleasure. Thanks for verifying. Just to confirm, I will backport the required three patches to the 13.x release branch:

rG0ba8595287ea2203ef2250e2b0b41f284a055518
rG2537120c8
rG21ee38e24f9801a567306b2a88defacf6e589a8b

[chrisjackson]

-EDIT-
Diff changed in error.

[chrisjackson]

Restored diff. I accidentally updated this diff with a file intended for a separate issue.

[bjope]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6024

Is this some kind of optimization on IR/MIR level?

Seems like this can result in DBG_VALUE with DW_OP_LLVM_arg in the DIExpression (i.e. neither having a DIArgList or using DBG_VALUE_LIST). But it also seem like that particular scenario doesn't seem to be handled by DwarfDebug. See https://github.com/llvm/llvm-project/issues/55097

Maybe such things should be expected by all passes? Or is this just a pseudo optimization introducing a special case that complicate logic in other passes?

Well, I haven't analysed things so closely so maybe this choice is needed for some other reason.

[jmorse]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6024

(Drive-by comment) IIRC this clause is here to optimise scenarios where the expression starts with DW_OP_LLVM_arg, 0, and where there are no other arguments to the expression, meaning it could be replaced by a plain dbg.value(%123, ..., !DIExpression(blah)), rather than a variadic dbg.value. (Maybe it's faulty, I haven't dug in either).

[bjope]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6024

Ok, I see now that the comment for setShortFinalExpression actually say "omit DW_OP_llvm_arg" and not "emit DW_OP_llvm_arg" as I read it the first time.

So maybe the case here is that there are several references to "DW_OP_LLVM_arg, 0" and not only at the expression start. And then we can't just skip adding a DIArgList.

[StephenTozer]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6024

I think I see the issue here, I brought up the same thing on the more recent LSR-salvage patch: This check is overly permissive. Specifically, the check Values.size() == 1 only checks that there is only one value in the value list, not that there is only one DW_OP_LLVM_arg in the expression; i.e. if the DIExpression is !(DW_OP_LLVM_arg 0, DW_OP_LLVM_arg 0, DW_OP_plus), it would still return true. Thus, when this function sees an expression like that, it assumes that it is safe to emit the short form and drops the first operator, producing dbg.value(%value, !123, !DIExpression(DW_OP_LLVM_arg 0, DW_OP_plus).

Also, Chris's new patch stack will fix this when it lands, and I'm just about to approve it - will that be suitable, or is a temp fix needed? (For a very quick and dirty temp fix, adding && std::count_if(expr_op_iterator(Expr.begin()), expr_op_iterator(Expr.end()), [](auto ExprOp) { return ExprOp.getOp() == llvm::dwarf::DW_OP_LLVM_arg; }) == 1 would be the simplest fix.

[bjope]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6024

Thank you for quick answers and explanations!

From my point of view I'm happy to use the workaround downstream until the other patches has landed.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

class SCEVExpander : public SCEVVisitor<SCEVExpander, Value *> {
   DenseSet<AssertingVH<Value>> InsertedValues;
   DenseSet<AssertingVH<Value>> InsertedPostIncValues;
 
   /// Keep track of the existing IR values re-used during expansion.
   /// FIXME: Ideally re-used instructions would not be added to
   /// InsertedValues/InsertedPostIncValues.
   SmallPtrSet<Value *, 16> ReusedValues;
 
+  // The induction variables generated.
+  SmallVector<WeakVH, 2> InsertedIVs;
+
   /// A memoization of the "relevant" loop for a given SCEV.
   DenseMap<const SCEV *, const Loop *> RelevantLoops;
 
   /// Addrecs referring to any of the given loops are expanded in post-inc
   /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add
   /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new
   /// phi starting at 1. This is only supported in non-canonical mode.
   PostIncLoopSet PostIncLoops;
~SCEVExpander() {
     // Make sure the insert point guard stack is consistent.
     assert(InsertPointGuards.empty());
   }
 
 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
   void setDebugType(const char *s) { DebugType = s; }
 #endif
 
   /// Erase the contents of the InsertedExpressions map so that users trying
   /// to expand the same expression into multiple BasicBlocks or different
   /// places within the same BasicBlock can do so.
   void clear() {
     InsertedExpressions.clear();
     InsertedValues.clear();
     InsertedPostIncValues.clear();
     ReusedValues.clear();
     ChainedPhis.clear();
+    InsertedIVs.clear();
   }
 
   ScalarEvolution *getSE() { return &SE; }
+  const SmallVectorImpl<WeakVH> &getInsertedIVs() const { return InsertedIVs; }
 
   /// Return a vector containing all instructions inserted during expansion.
   SmallVector<Instruction *, 32> getAllInsertedInstructions() const {
     SmallVector<Instruction *, 32> Result;
     for (auto &VH : InsertedValues) {
       Value *V = VH;
       if (ReusedValues.contains(V))
         continue;

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

class LSRInstance {
   static const unsigned MaxChains = 8;
 
   /// IV users can form a chain of IV increments.
   SmallVector<IVChain, MaxChains> IVChainVec;
 
   /// IV users that belong to profitable IVChains.
   SmallPtrSet<Use*, MaxChains> IVIncSet;
 
+  /// Induction variables that were generated and inserted by the SCEV Expander.
+  SmallVector<llvm::WeakVH, 2> ScalarEvolutionIVs;
+
   void OptimizeShadowIV();
   bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse);
   ICmpInst *OptimizeMax(ICmpInst *Cond, IVStrideUse* &CondUse);
   void OptimizeLoopTermCond();
 
   void ChainInstruction(Instruction *UserInst, Instruction *IVOper,
                         SmallVectorImpl<ChainUsers> &ChainUsersVec);
   void FinalizeChain(IVChain &Chain);
class LSRInstance {
   void ImplementSolution(const SmallVectorImpl<const Formula *> &Solution);
 
 public:
   LSRInstance(Loop *L, IVUsers &IU, ScalarEvolution &SE, DominatorTree &DT,
               LoopInfo &LI, const TargetTransformInfo &TTI, AssumptionCache &AC,
               TargetLibraryInfo &TLI, MemorySSAUpdater *MSSAU);
 
   bool getChanged() const { return Changed; }
+  const SmallVectorImpl<WeakVH> &getScalarEvolutionIVs() const {
+    return ScalarEvolutionIVs;
+  }
 
   void print_factors_and_types(raw_ostream &OS) const;
   void print_fixups(raw_ostream &OS) const;
   void print_uses(raw_ostream &OS) const;
   void print(raw_ostream &OS) const;
   void dump() const;
 };
 
for (const LSRFixup &Fixup : Uses[LUIdx].Fixups) {
       Rewrite(Uses[LUIdx], Fixup, *Solution[LUIdx], Rewriter, DeadInsts);
       Changed = true;
     }
 
   for (const IVChain &Chain : IVChainVec) {
     GenerateIVChain(Chain, Rewriter, DeadInsts);
     Changed = true;
   }
+
+  for (const WeakVH &IV : Rewriter.getInsertedIVs())
+    if (IV && dyn_cast<Instruction>(&*IV)->getParent())
+      ScalarEvolutionIVs.push_back(IV);
+
   // Clean up after ourselves. This must be done before deleting any
   // instructions.
   Rewriter.clear();
 
   Changed |= RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts,
                                                                   &TLI, MSSAU);
 
   // In our cost analysis above, we assume that each addrec consumes exactly

 };
 
 } // end anonymous namespace
 
 LoopStrengthReduce::LoopStrengthReduce() : LoopPass(ID) {
   initializeLoopStrengthReducePass(*PassRegistry::getPassRegistry());
 }
 
 void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const {
   // We split critical edges, so we change the CFG.  However, we do update
   // many analyses if they are around.
   AU.addPreservedID(LoopSimplifyID);
 
   AU.addRequired<LoopInfoWrapperPass>();
   AU.addPreserved<LoopInfoWrapperPass>();
   AU.addRequiredID(LoopSimplifyID);
   AU.addRequired<DominatorTreeWrapperPass>();
   AU.addPreserved<DominatorTreeWrapperPass>();
   AU.addRequired<ScalarEvolutionWrapperPass>();
   AU.addPreserved<ScalarEvolutionWrapperPass>();
   AU.addRequired<AssumptionCacheTracker>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   // Requiring LoopSimplify a second time here prevents IVUsers from running
   // twice, since LoopSimplify was invalidated by running ScalarEvolution.
   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<DbgValueInst *, SmallVector<std::pair<unsigned, EqualValues>>>;
-using LocationMap =
-    DenseMap<DbgValueInst *, std::pair<DIExpression *, Metadata *>>;
-
-static void DbgGatherEqualValues(Loop *L, ScalarEvolution &SE,
-                                 EqualValuesMap &DbgValueToEqualSet,
-                                 LocationMap &DbgValueToLocation) {
+struct SCEVDbgValueBuilder {
+  SCEVDbgValueBuilder() = default;
+  SCEVDbgValueBuilder(const SCEVDbgValueBuilder &Base) {
+    Values = Base.Values;
+    Expr = Base.Expr;
+  }
+
+  /// The DIExpression as we translate the SCEV.
+  SmallVector<uint64_t, 6> Expr;
+  /// The location ops of the DIExpression.
+  SmallVector<llvm::ValueAsMetadata *, 2> Values;
+
+  void pushOperator(uint64_t Op) { Expr.push_back(Op); }
+  void pushUInt(uint64_t Operand) { Expr.push_back(Operand); }
+
+  /// Add a DW_OP_LLVM_arg to the expression, followed by the index of the value
+  /// in the set of values referenced by the expression.
+  void pushValue(llvm::Value *V) {
+    Expr.push_back(llvm::dwarf::DW_OP_LLVM_arg);
+    auto *It =
+        std::find(Values.begin(), Values.end(), llvm::ValueAsMetadata::get(V));
+    unsigned ArgIndex = 0;
+    if (It != Values.end()) {
+      ArgIndex = std::distance(Values.begin(), It);
+    } else {
+      ArgIndex = Values.size();
+      Values.push_back(llvm::ValueAsMetadata::get(V));
+    }
+    Expr.push_back(ArgIndex);
+  }
+
+  void pushValue(const SCEVUnknown *U) {
+    llvm::Value *V = cast<SCEVUnknown>(U)->getValue();
+    pushValue(V);
+  }
+
+  void pushConst(const SCEVConstant *C) {
+    Expr.push_back(llvm::dwarf::DW_OP_consts);
+    Expr.push_back(C->getAPInt().getSExtValue());
+  }
+
+  /// Several SCEV types are sequences of the same arithmetic operator applied
+  /// to constants and values that may be extended or truncated.
+  bool pushArithmeticExpr(const llvm::SCEVCommutativeExpr *CommExpr,
+                          uint64_t DwarfOp) {
+    assert((isa<llvm::SCEVAddExpr>(CommExpr) || isa<SCEVMulExpr>(CommExpr)) &&
+           "Expected arithmetic SCEV type");
+    bool Success = true;
+    unsigned EmitOperator = 0;
+    for (auto &Op : CommExpr->operands()) {
+      Success &= pushSCEV(Op);
+
+      if (EmitOperator >= 1)
+        pushOperator(DwarfOp);
+      ++EmitOperator;
+    }
+    return Success;
+  }
+
+  // TODO: Identify and omit noop casts.
+  bool pushCast(const llvm::SCEVCastExpr *C, bool IsSigned) {
+    const llvm::SCEV *Inner = C->getOperand(0);
+    const llvm::Type *Type = C->getType();
+    uint64_t ToWidth = Type->getIntegerBitWidth();
+    bool Success = pushSCEV(Inner);
+    uint64_t CastOps[] = {dwarf::DW_OP_LLVM_convert, ToWidth,
+                          IsSigned ? llvm::dwarf::DW_ATE_signed
+                                   : llvm::dwarf::DW_ATE_unsigned};
+    for (const auto &Op : CastOps)
+      pushOperator(Op);
+    return Success;
+  }
+
+  // TODO: MinMax - although these haven't been encountered in the test suite.
+  bool pushSCEV(const llvm::SCEV *S) {
+    bool Success = true;
+    if (const SCEVConstant *StartInt = dyn_cast<SCEVConstant>(S)) {
+      pushConst(StartInt);
+
+    } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
+      if (!U->getValue())
+        return false;
+      pushValue(U->getValue());
+
+    } else if (const SCEVMulExpr *MulRec = dyn_cast<SCEVMulExpr>(S)) {
+      Success &= pushArithmeticExpr(MulRec, llvm::dwarf::DW_OP_mul);
+
+    } else if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
+      Success &= pushSCEV(UDiv->getLHS());
+      Success &= pushSCEV(UDiv->getRHS());
+      pushOperator(llvm::dwarf::DW_OP_div);
+
+    } else if (const SCEVCastExpr *Cast = dyn_cast<SCEVCastExpr>(S)) {
+      // Assert if a new and unknown SCEVCastEXpr type is encountered.
+      assert((isa<SCEVZeroExtendExpr>(Cast) || isa<SCEVTruncateExpr>(Cast) ||
+              isa<SCEVPtrToIntExpr>(Cast) || isa<SCEVSignExtendExpr>(Cast)) &&
+             "Unexpected cast type in SCEV.");
+      Success &= pushCast(Cast, (isa<SCEVSignExtendExpr>(Cast)));
+
+    } else if (const SCEVAddExpr *AddExpr = dyn_cast<SCEVAddExpr>(S)) {
+      Success &= pushArithmeticExpr(AddExpr, llvm::dwarf::DW_OP_plus);
+
+    } else if (isa<SCEVAddRecExpr>(S)) {
+      // Nested SCEVAddRecExpr are generated by nested loops and are currently
+      // unsupported.
+      return false;
+
+    } else {
+      return false;
+    }
+    return Success;
+  }
+
+  void setFinalExpression(llvm::DbgValueInst &DI, const DIExpression *OldExpr) {
+    // Re-state assumption that this dbg.value is not variadic. Any remaining
+    // opcodes in its expression operate on a single value already on the
+    // expression stack. Prepend our operations, which will re-compute and
+    // place that value on the expression stack.
+    assert(!DI.hasArgList());
+    auto *NewExpr =
+        DIExpression::prependOpcodes(OldExpr, Expr, /*StackValue*/ true);
+    DI.setExpression(NewExpr);
+
+    auto ValArrayRef = llvm::ArrayRef<llvm::ValueAsMetadata *>(Values);
+    DI.setRawLocation(llvm::DIArgList::get(DI.getContext(), ValArrayRef));
+  }
+
+  /// If a DVI can be emitted without a DIArgList, omit DW_OP_llvm_arg and the
+  /// location op index 0.
+  void setShortFinalExpression(llvm::DbgValueInst &DI,
+                               const DIExpression *OldExpr) {
+    assert((Expr[0] == llvm::dwarf::DW_OP_LLVM_arg && Expr[1] == 0) &&
+           "Expected DW_OP_llvm_arg and 0.");
+    DI.replaceVariableLocationOp(
+        0u, llvm::MetadataAsValue::get(DI.getContext(), Values[0]));
+
+    // See setFinalExpression: prepend our opcodes on the start of any old
+    // expression opcodes.
+    assert(!DI.hasArgList());
+    llvm::SmallVector<uint64_t, 6> FinalExpr(Expr.begin() + 2, Expr.end());
+    auto *NewExpr =
+        DIExpression::prependOpcodes(OldExpr, FinalExpr, /*StackValue*/ true);
+    DI.setExpression(NewExpr);
+  }
+
+  /// Once the IV and variable SCEV translation is complete, write it to the
+  /// source DVI.
+  void applyExprToDbgValue(llvm::DbgValueInst &DI,
+                           const DIExpression *OldExpr) {
+    assert(!Expr.empty() && "Unexpected empty expression.");
+    // Emit a simpler form if only a single location is referenced.
+    if (Values.size() == 1 && Expr[0] == llvm::dwarf::DW_OP_LLVM_arg &&
+        Expr[1] == 0) {
+      setShortFinalExpression(DI, OldExpr);
+    } else {
+      setFinalExpression(DI, OldExpr);
+    }
+  }
+
+  /// Return true if the combination of arithmetic operator and underlying
+  /// SCEV constant value is an identity function.
+  bool isIdentityFunction(uint64_t Op, const SCEV *S) {
+    if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
+      int64_t I = C->getAPInt().getSExtValue();
+      switch (Op) {
+      case llvm::dwarf::DW_OP_plus:
+      case llvm::dwarf::DW_OP_minus:
+        return I == 0;
+      case llvm::dwarf::DW_OP_mul:
+      case llvm::dwarf::DW_OP_div:
+        return I == 1;
+      }
+    }
+    return false;
+  }
+
+  /// Convert a SCEV of a value to a DIExpression that is pushed onto the
+  /// builder's expression stack. The stack should already contain an
+  /// expression for the iteration count, so that it can be multiplied by
+  /// the stride and added to the start.
+  /// Components of the expression are omitted if they are an identity function.
+  /// Chain (non-affine) SCEVs are not supported.
+  bool SCEVToValueExpr(const llvm::SCEVAddRecExpr &SAR, ScalarEvolution &SE) {
+    assert(SAR.isAffine() && "Expected affine SCEV");
+    // TODO: Is this check needed?
+    if (isa<SCEVAddRecExpr>(SAR.getStart()))
+      return false;
+
+    const SCEV *Start = SAR.getStart();
+    const SCEV *Stride = SAR.getStepRecurrence(SE);
+
+    // Skip pushing arithmetic noops.
+    if (!isIdentityFunction(llvm::dwarf::DW_OP_mul, Stride)) {
+      if (!pushSCEV(Stride))
+        return false;
+      pushOperator(llvm::dwarf::DW_OP_mul);
+    }
+    if (!isIdentityFunction(llvm::dwarf::DW_OP_plus, Start)) {
+      if (!pushSCEV(Start))
+        return false;
+      pushOperator(llvm::dwarf::DW_OP_plus);
+    }
+    return true;
+  }
+
+  /// Convert a SCEV of a value to a DIExpression that is pushed onto the
+  /// builder's expression stack. The stack should already contain an
+  /// expression for the iteration count, so that it can be multiplied by
+  /// the stride and added to the start.
+  /// Components of the expression are omitted if they are an identity function.
+  bool SCEVToIterCountExpr(const llvm::SCEVAddRecExpr &SAR,
+                           ScalarEvolution &SE) {
+    assert(SAR.isAffine() && "Expected affine SCEV");
+    if (isa<SCEVAddRecExpr>(SAR.getStart())) {
+      LLVM_DEBUG(dbgs() << "scev-salvage: IV SCEV. Unsupported nested AddRec: "
+                        << SAR << '\n');
+      return false;
+    }
+    const SCEV *Start = SAR.getStart();
+    const SCEV *Stride = SAR.getStepRecurrence(SE);
+
+    // Skip pushing arithmetic noops.
+    if (!isIdentityFunction(llvm::dwarf::DW_OP_minus, Start)) {
+      if (!pushSCEV(Start))
+        return false;
+      pushOperator(llvm::dwarf::DW_OP_minus);
+    }
+    if (!isIdentityFunction(llvm::dwarf::DW_OP_div, Stride)) {
+      if (!pushSCEV(Stride))
+        return false;
+      pushOperator(llvm::dwarf::DW_OP_div);
+    }
+    return true;
+  }
+};
+
+struct DVIRecoveryRec {
+  DbgValueInst *DVI;
+  DIExpression *Expr;
+  Metadata *LocationOp;
+  const llvm::SCEV *SCEV;
+};
+
+static bool 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;
+
+  // 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;
+
+  LLVM_DEBUG(dbgs() << "scev-salvage: Value to salvage SCEV: "
+                    << *CachedDVI.SCEV << '\n');
+
+  const auto *Rec = cast<SCEVAddRecExpr>(CachedDVI.SCEV);
+  if (!Rec->isAffine())
+    return false;
+
+  // 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;
+
+  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
+DbgRewriteSalvageableDVIs(llvm::Loop *L, ScalarEvolution &SE,
+                          llvm::PHINode *LSRInductionVar,
+                          SmallVector<DVIRecoveryRec, 2> &DVIToUpdate) {
+  if (DVIToUpdate.empty())
+    return false;
+
+  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)) {
+    SCEVDbgValueBuilder IterCountExpr;
+    IterCountExpr.pushValue(LSRInductionVar);
+    if (!IterCountExpr.SCEVToIterCountExpr(*IVAddRec, SE))
+      return false;
+
+    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);
+      }
+
+      Changed |= 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) {
   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.
-        Value *V = DVI->getVariableLocationOp(Idx);
-        if (!V || !SE.isSCEVable(V->getType()))
-          continue;
-        auto DbgValueSCEV = SE.getSCEV(V);
-        EqualValues EqSet;
-        for (PHINode &Phi : L->getHeader()->phis()) {
-          if (V->getType() != Phi.getType())
-            continue;
-          if (!SE.isSCEVable(Phi.getType()))
-            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].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};
-      }
+
+      if (DVI->hasArgList())
+
+      if (!DVI->getVariableLocationOp(0) ||
+          !SE.isSCEVable(DVI->getVariableLocationOp(0)->getType()))
+
+      SalvageableDVISCEVs.push_back(
+          {DVI, DVI->getExpression(), DVI->getRawLocation(),
+           SE.getSCEV(DVI->getVariableLocationOp(0))});
+      DVIHandles.insert(DVI);
     }
   }
 }
 
-static void DbgApplyEqualValues(EqualValuesMap &DbgValueToEqualSet,
-                                LocationMap &DbgValueToLocation) {
-  for (auto A : DbgValueToEqualSet) {
-    auto *DVI = A.first;
-    // Only update those that are now undef.
-    if (!DVI->isUndef())
-      continue;
-    // 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;
-        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);
-        break;
-      }
-    }
+/// Ideally pick the PHI IV inserted by ScalarEvolutionExpander. As a fallback
+/// any PHi from the loop header is usable, but may have less chance of
+/// surviving subsequent transforms.
+static llvm::PHINode *GetInductionVariable(const Loop &L, ScalarEvolution &SE,
+                                           const LSRInstance &LSR) {
+  // For now, just pick the first IV generated and inserted. Ideally pick an IV
+  // that is unlikely to be optimised away by subsequent transforms.
+  for (const WeakVH &IV : LSR.getScalarEvolutionIVs()) {
+    if (!IV)
+      continue;
+
+    assert(isa<PHINode>(&*IV) && "Expected PhI node.");
+    if (SE.isSCEVable((*IV).getType())) {
+      PHINode *Phi = dyn_cast<PHINode>(&*IV);
+      const llvm::SCEV *S = SE.getSCEV(Phi);
+      LLVM_DEBUG(dbgs() << "scev-salvage: IV : " << *IV << "with SCEV: " << *S
+                        << "\n");
+      return Phi;
+  assert(false && "moo");
+  for (PHINode &Phi : L.getHeader()->phis()) {
+    if (!SE.isSCEVable(Phi.getType()))
+      continue;
+
+    const llvm::SCEV *PhiSCEV = SE.getSCEV(&Phi);
+    if (const llvm::SCEVAddRecExpr *Rec = dyn_cast<SCEVAddRecExpr>(PhiSCEV))
+      if (!Rec->isAffine())
+        continue;
+
+    LLVM_DEBUG(dbgs() << "scev-salvage: Selected IV from loop header: " << Phi
+                      << " with SCEV: " << *PhiSCEV << "\n");
+    return &Phi;
   }
+  return nullptr;
 }
 
 static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE,
                                DominatorTree &DT, LoopInfo &LI,
                                const TargetTransformInfo &TTI,
                                AssumptionCache &AC, TargetLibraryInfo &TLI,
                                MemorySSA *MSSA) {
 
+  // Debug preservation - before we start removing anything identify which DVI
+  // meet the salvageable criteria and store their DIExpression and SCEVs.
+  SmallVector<DVIRecoveryRec, 2> SalvageableDVI;
+  SmallSet<AssertingVH<DbgValueInst>, 2> DVIHandles;
+  DbgGatherSalvagableDVI(L, SE, SalvageableDVI, DVIHandles);
+
   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;
-  LocationMap DbgValueToLocation;
-  DbgGatherEqualValues(L, SE, DbgValueToEqualSet, DbgValueToLocation);
+  const LSRInstance &Reducer =
+      LSRInstance(L, IU, SE, DT, LI, TTI, AC, TLI, MSSAU.get());
+  Changed |= Reducer.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());
     }
   }
 
-  DbgApplyEqualValues(DbgValueToEqualSet, DbgValueToLocation);
+  if (SalvageableDVI.empty())
+    return Changed;
+
+  // Obtain relevant IVs and attempt to rewrite the salvageable DVIs with
+  // expressions composed using the derived iteration count.
+  // TODO: Allow for multiple IV references for nested AddRecSCEVs
+  for (auto &L : LI) {
+    if (llvm::PHINode *IV = GetInductionVariable(*L, SE, Reducer))
+      DbgRewriteSalvageableDVIs(L, SE, IV, SalvageableDVI);
+    else {
+      LLVM_DEBUG(dbgs() << "scev-salvage: SCEV salvaging not possible. An IV "
+                           "could not be identified.\n");
+    }
+  }
 
+  DVIHandles.clear();
   return Changed;
 }
 
 bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) {
   if (skipLoop(L))
     return false;
 
   auto &IU = getAnalysis<IVUsersWrapperPass>().getIU();

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
     }
     PN->addIncoming(IncV, Pred);
   }
 
   // After expanding subexpressions, restore the PostIncLoops set so the caller
   // can ensure that IVIncrement dominates the current uses.
   PostIncLoops = SavedPostIncLoops;
 
-  // Remember this PHI, even in post-inc mode.
+  // Remember this PHI, even in post-inc mode. LSR SCEV-based salvaging is most
+  // effective when we are able to use an IV inserted here, so record it.
   InsertedValues.insert(PN);
-
+  InsertedIVs.push_back(PN);
   return PN;
 }
 
 Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {
   Type *STy = S->getType();
   Type *IntTy = SE.getEffectiveSCEVType(STy);
   const Loop *L = S->getLoop();
 

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

 
 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
+; 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))
   %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
+; 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))
   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/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.
+; undef, and finally recovered by SCEV salvaging.
 
 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()
+; CHECK: call void @llvm.dbg.value(metadata !DIArgList(i32 %lsr.iv, i32 %Step), metadata ![[VAR_ITR:[0-9]+]], metadata !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_minus, DW_OP_LLVM_arg, 1, DW_OP_div, DW_OP_LLVM_arg, 1, DW_OP_mul, DW_OP_stack_value))
   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

llvm/test/Transforms/LoopStrengthReduce/debuginfo-scev-salvage-0.ll

+; RUN: opt -S -loop-reduce %s -o - | FileCheck %s
+; REQUIRES: x86-registered-target
+
+;; Ensure that we retain debuginfo for the induction variable and dependant
+;; variables when loop strength reduction is applied to the loop.
+;; This IR produced from:
+;;
+;; clang -S -emit-llvm -Xclang -disable-llvm-passes -g lsr-basic.cpp -o
+;; Then executing opt -O2 up to the the loopFullUnroll pass.
+;; void mul_pow_of_2_to_shift(unsigned size, unsigned *data) {
+;; unsigned i = 0;
+;; #pragma clang loop vectorize(disable)
+;;    while (i < size) {
+;;         unsigned comp = i * 8;
+;;         data[i] = comp;
+;;        i++;                // DexLabel('mul_pow_of_2_induction_increment')
+;;   }
+;; }
+; CHECK: call void @llvm.dbg.value(metadata i64 %lsr.iv, metadata ![[i:[0-9]+]], metadata !DIExpression(DW_OP_consts, 8, DW_OP_div, DW_OP_stack_value))
+; CHECK: call void @llvm.dbg.value(metadata i64 %lsr.iv, metadata ![[comp:[0-9]+]], metadata !DIExpression(DW_OP_consts, 8, DW_OP_div, DW_OP_consts, 8, DW_OP_mul, DW_OP_stack_value))
+; CHECK: call void @llvm.dbg.value(metadata i64 %lsr.iv, metadata ![[i]], metadata !DIExpression(DW_OP_consts, 8, DW_OP_div, DW_OP_consts, 1, DW_OP_plus, DW_OP_stack_value))
+; CHECK: ![[i]] = !DILocalVariable(name: "i"
+; CHECK: ![[comp]] = !DILocalVariable(name: "comp"
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define dso_local void @_Z21mul_pow_of_2_to_shiftjPj(i32 %size, i32* nocapture %data) local_unnamed_addr !dbg !7 {
+entry:
+  call void @llvm.dbg.value(metadata i32 %size, metadata !12, metadata !DIExpression()), !dbg !13
+  call void @llvm.dbg.value(metadata i32* %data, metadata !14, metadata !DIExpression()), !dbg !13
+  call void @llvm.dbg.value(metadata i32 0, metadata !15, metadata !DIExpression()), !dbg !13
+  %cmp4.not = icmp eq i32 %size, 0, !dbg !13
+  br i1 %cmp4.not, label %while.end, label %while.body.preheader, !dbg !13
+
+while.body.preheader:                             ; preds = %entry
+  %wide.trip.count = zext i32 %size to i64, !dbg !13
+  br label %while.body, !dbg !13
+
+while.body:                                       ; preds = %while.body, %while.body.preheader
+  %indvars.iv = phi i64 [ 0, %while.body.preheader ], [ %indvars.iv.next, %while.body ]
+  call void @llvm.dbg.value(metadata i64 %indvars.iv, metadata !15, metadata !DIExpression()), !dbg !13
+  %0 = trunc i64 %indvars.iv to i32, !dbg !16
+  %mul = shl i32 %0, 3, !dbg !16
+  call void @llvm.dbg.value(metadata i32 %mul, metadata !18, metadata !DIExpression()), !dbg !16
+  %arrayidx = getelementptr inbounds i32, i32* %data, i64 %indvars.iv, !dbg !16
+  store i32 %mul, i32* %arrayidx, align 4, !dbg !16
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1, !dbg !16
+  call void @llvm.dbg.value(metadata i64 %indvars.iv.next, metadata !15, metadata !DIExpression()), !dbg !13
+  %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count, !dbg !13
+  br i1 %exitcond, label %while.body, label %while.end.loopexit, !dbg !13, !llvm.loop !19
+
+while.end.loopexit:                               ; preds = %while.body
+  br label %while.end, !dbg !13
+
+while.end:                                        ; preds = %while.end.loopexit, %entry
+  ret void, !dbg !13
+}
+
+; Function Attrs: nofree nosync nounwind readnone speculatable willreturn
+declare void @llvm.dbg.value(metadata, metadata, metadata) #0
+
+attributes #0 = { nofree nosync nounwind readnone speculatable willreturn }
+
+!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: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "lsr-basic.cpp", directory: "/tmp")
+!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: "mul_pow_of_2_to_shift", linkageName: "_Z21mul_pow_of_2_to_shiftjPj", scope: !1, file: !1, line: 18, type: !8, scopeLine: 18, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!8 = !DISubroutineType(types: !9)
+!9 = !{null, !10, !11}
+!10 = !DIBasicType(name: "unsigned int", size: 32, encoding: DW_ATE_unsigned)
+!11 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !10, size: 64)
+!12 = !DILocalVariable(name: "size", arg: 1, scope: !7, file: !1, line: 18, type: !10)
+!13 = !DILocation(line: 0, scope: !7)
+!14 = !DILocalVariable(name: "data", arg: 2, scope: !7, file: !1, line: 18, type: !11)
+!15 = !DILocalVariable(name: "i", scope: !7, file: !1, line: 19, type: !10)
+!16 = !DILocation(line: 22, column: 27, scope: !17)
+!17 = distinct !DILexicalBlock(scope: !7, file: !1, line: 21, column: 22)
+!18 = !DILocalVariable(name: "comp", scope: !17, file: !1, line: 22, type: !10)
+!19 = distinct !{!19, !20, !21, !22, !23}
+!20 = !DILocation(line: 21, column: 5, scope: !7)
+!21 = !DILocation(line: 25, column: 5, scope: !7)
+!22 = !{!"llvm.loop.mustprogress"}
+!23 = !{!"llvm.loop.vectorize.width", i32 1}

llvm/test/Transforms/LoopStrengthReduce/debuginfo-scev-salvage-1.ll

+; RUN: opt -S -loop-reduce %s -o - | FileCheck %s
+; REQUIRES: x86-registered-target
+
+;; Ensure that we retain debuginfo for the induction variable and dependant
+;; variables when loop strength reduction is applied to the loop.
+;; This IR produced from:
+;;
+;; clang -S -emit-llvm -Xclang -disable-llvm-passes -g lsr-basic.cpp -o
+;; Then executing opt -O2 up to the the loopFullUnroll pass.
+;; void mul_to_addition(unsigned k, unsigned size, unsigned *data) {
+;;     int i = 0;
+;; #pragma clang loop vectorize(disable)
+;;     while (i < size) {
+;;         int comp = (4 * i) + k;
+;;         data[i] = comp;
+;;        i += 1;
+;;     }
+;; }
+; CHECK: call void @llvm.dbg.value(metadata i64 %lsr.iv, metadata ![[i:[0-9]+]], metadata !DIExpression())
+; CHECK: call void @llvm.dbg.value(metadata !DIArgList(i64 %lsr.iv, i32 %k), metadata ![[comp:[0-9]+]], metadata !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_consts, 4, DW_OP_mul, DW_OP_LLVM_arg, 1, DW_OP_plus, DW_OP_stack_value))
+; CHECK: call void @llvm.dbg.value(metadata i64 %lsr.iv, metadata ![[i]],  metadata !DIExpression(DW_OP_consts, 1, DW_OP_plus, DW_OP_stack_value))
+; CHECK: ![[i]] = !DILocalVariable(name: "i"
+; CHECK: ![[comp]] = !DILocalVariable(name: "comp"
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define dso_local void @_Z15mul_to_additionjjPj(i32 %k, i32 %size, i32* nocapture %data) local_unnamed_addr !dbg !7 {
+entry:
+  call void @llvm.dbg.value(metadata i32 %k, metadata !13, metadata !DIExpression()), !dbg !14
+  call void @llvm.dbg.value(metadata i32 %size, metadata !15, metadata !DIExpression()), !dbg !14
+  call void @llvm.dbg.value(metadata i32* %data, metadata !16, metadata !DIExpression()), !dbg !14
+  call void @llvm.dbg.value(metadata i32 0, metadata !17, metadata !DIExpression()), !dbg !14
+  br label %while.cond, !dbg !14
+
+while.cond:                                       ; preds = %while.body, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %add1, %while.body ], !dbg !14
+  call void @llvm.dbg.value(metadata i32 %i.0, metadata !17, metadata !DIExpression()), !dbg !14
+  %cmp = icmp ult i32 %i.0, %size, !dbg !14
+  br i1 %cmp, label %while.body, label %while.end, !dbg !14
+
+while.body:                                       ; preds = %while.cond
+  %mul = mul nsw i32 %i.0, 4, !dbg !19
+  %add = add i32 %mul, %k, !dbg !19
+  call void @llvm.dbg.value(metadata i32 %add, metadata !21, metadata !DIExpression()), !dbg !19
+  %idxprom = zext i32 %i.0 to i64, !dbg !19
+  %arrayidx = getelementptr inbounds i32, i32* %data, i64 %idxprom, !dbg !19
+  store i32 %add, i32* %arrayidx, align 4, !dbg !19
+  %add1 = add nuw nsw i32 %i.0, 1, !dbg !19
+  call void @llvm.dbg.value(metadata i32 %add1, metadata !17, metadata !DIExpression()), !dbg !14
+  br label %while.cond, !dbg !14, !llvm.loop !22
+
+while.end:                                        ; preds = %while.cond
+  ret void, !dbg !14
+}
+
+; Function Attrs: nofree nosync nounwind readnone speculatable willreturn
+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_C_plus_plus_14, file: !1, producer: "clang version 12.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "basic.cpp", directory: "/test")
+!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: "mul_to_addition", linkageName: "_Z15mul_to_additionjjPj", scope: !8, file: !8, line: 64, type: !9, scopeLine: 64, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!8 = !DIFile(filename: "./basic.cpp", directory: "/test")
+!9 = !DISubroutineType(types: !10)
+!10 = !{null, !11, !11, !12}
+!11 = !DIBasicType(name: "unsigned int", size: 32, encoding: DW_ATE_unsigned)
+!12 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !11, size: 64)
+!13 = !DILocalVariable(name: "k", arg: 1, scope: !7, file: !8, line: 64, type: !11)
+!14 = !DILocation(line: 0, scope: !7)
+!15 = !DILocalVariable(name: "size", arg: 2, scope: !7, file: !8, line: 64, type: !11)
+!16 = !DILocalVariable(name: "data", arg: 3, scope: !7, file: !8, line: 64, type: !12)
+!17 = !DILocalVariable(name: "i", scope: !7, file: !8, line: 65, type: !18)
+!18 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!19 = !DILocation(line: 68, column: 23, scope: !20)
+!20 = distinct !DILexicalBlock(scope: !7, file: !8, line: 67, column: 22)
+!21 = !DILocalVariable(name: "comp", scope: !20, file: !8, line: 68, type: !18)
+!22 = distinct !{!22, !23, !24, !25, !26}
+!23 = !DILocation(line: 67, column: 5, scope: !7)
+!24 = !DILocation(line: 71, column: 5, scope: !7)
+!25 = !{!"llvm.loop.mustprogress"}
+!26 = !{!"llvm.loop.vectorize.width", i32 1}

llvm/test/Transforms/LoopStrengthReduce/debuginfo-scev-salvage-2.ll

+; RUN: opt -S -loop-reduce %s -o - | FileCheck %s
+; REQUIRES: x86-registered-target
+
+;; Ensure that we retain debuginfo for the induction variable and dependant
+;; variables when loop strength reduction is applied to the loop.
+;; This IR produced from:
+;;
+;; clang -S -emit-llvm -Xclang -disable-llvm-passes -g lsr-basic.cpp -o
+;; Then executing opt -O2 up to the the loopFullUnroll pass.
+;; void basic_recurrence(unsigned k, unsigned size, unsigned *data)
+;; {
+;;    unsigned i = 0;
+;; #pragma clang loop vectorize(disable)
+;;    while (i < size) {
+;;         unsigned comp = i * k; 
+;;         data[i] = comp;
+;;         i++;
+;;    }
+;; }
+; CHECK: call void @llvm.dbg.value(metadata i64 %lsr.iv, metadata ![[i:[0-9]+]], metadata !DIExpression())
+; CHECK: call void @llvm.dbg.value(metadata !DIArgList(i64 %lsr.iv, i32 %k), metadata ![[comp:[0-9]+]], metadata !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_mul, DW_OP_stack_value))
+; CHECK: call void @llvm.dbg.value(metadata i64 %lsr.iv, metadata ![[i]],  metadata !DIExpression(DW_OP_consts, 1, DW_OP_plus, DW_OP_stack_value))
+; CHECK: ![[i]] = !DILocalVariable(name: "i"
+; CHECK: ![[comp]] = !DILocalVariable(name: "comp"
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define dso_local void @_Z16basic_recurrencejjPj(i32 %k, i32 %size, i32* nocapture %data) local_unnamed_addr !dbg !7 {
+entry:
+  call void @llvm.dbg.value(metadata i32 %k, metadata !13, metadata !DIExpression()), !dbg !14
+  call void @llvm.dbg.value(metadata i32 %size, metadata !15, metadata !DIExpression()), !dbg !14
+  call void @llvm.dbg.value(metadata i32* %data, metadata !16, metadata !DIExpression()), !dbg !14
+  br label %while.cond, !dbg !14
+
+while.cond:                                       ; preds = %while.body, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.body ]
+  call void @llvm.dbg.value(metadata i32 %i.0, metadata !17, metadata !DIExpression()), !dbg !14
+  %cmp = icmp ult i32 %i.0, %size, !dbg !14
+  br i1 %cmp, label %while.body, label %while.end, !dbg !14
+
+while.body:                                       ; preds = %while.cond
+  %mul = mul i32 %i.0, %k, !dbg !18
+  call void @llvm.dbg.value(metadata i32 %mul, metadata !20, metadata !DIExpression()), !dbg !18
+  %idxprom = zext i32 %i.0 to i64, !dbg !18
+  %arrayidx = getelementptr inbounds i32, i32* %data, i64 %idxprom, !dbg !18
+  store i32 %mul, i32* %arrayidx, align 4, !dbg !18
+  %inc = add nuw i32 %i.0, 1, !dbg !18
+  call void @llvm.dbg.value(metadata i32 %inc, metadata !17, metadata !DIExpression()), !dbg !14
+  br label %while.cond, !dbg !14, !llvm.loop !21
+
+while.end:                                        ; preds = %while.cond
+  ret void, !dbg !14
+}
+
+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_C_plus_plus_14, file: !1, producer: "clang version 12.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "basic.cpp", directory: "/test")
+!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: "basic_recurrence", linkageName: "_Z16basic_recurrencejjPj", scope: !8, file: !8, line: 82, type: !9, scopeLine: 83, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!8 = !DIFile(filename: "./basic.cpp", directory: "/test")
+!9 = !DISubroutineType(types: !10)
+!10 = !{null, !11, !11, !12}
+!11 = !DIBasicType(name: "unsigned int", size: 32, encoding: DW_ATE_unsigned)
+!12 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !11, size: 64)
+!13 = !DILocalVariable(name: "k", arg: 1, scope: !7, file: !8, line: 82, type: !11)
+!14 = !DILocation(line: 0, scope: !7)
+!15 = !DILocalVariable(name: "size", arg: 2, scope: !7, file: !8, line: 82, type: !11)
+!16 = !DILocalVariable(name: "data", arg: 3, scope: !7, file: !8, line: 82, type: !12)
+!17 = !DILocalVariable(name: "i", scope: !7, file: !8, line: 84, type: !11)
+!18 = !DILocation(line: 87, column: 27, scope: !19)
+!19 = distinct !DILexicalBlock(scope: !7, file: !8, line: 86, column: 22)
+!20 = !DILocalVariable(name: "comp", scope: !19, file: !8, line: 87, type: !11)
+!21 = distinct !{!21, !22, !23, !24, !25}
+!22 = !DILocation(line: 86, column: 5, scope: !7)
+!23 = !DILocation(line: 90, column: 5, scope: !7)
+!24 = !{!"llvm.loop.mustprogress"}
+!25 = !{!"llvm.loop.vectorize.width", i32 1}

llvm/test/Transforms/LoopStrengthReduce/debuginfo-scev-salvage-3.ll

+; RUN: opt -S -loop-reduce %s -o - | FileCheck %s
+; REQUIRES: x86-registered-target
+
+;; Ensure that we retain debuginfo for the induction variable and dependant
+;; variables when loop strength reduction is applied to the loop.
+;; This IR produced from:
+;;
+;; clang -S -emit-llvm -Xclang -disable-llvm-passes -g lsr-basic.cpp -o
+;; Then executing opt -O2 up to the the loopFullUnroll pass.
+;; void mul_pow_of_2_to_shift_var_inc(unsigned size, unsigned *data, unsigned multiplicand) {
+;;     unsigned i = 0;
+;; #pragma clang loop vectorize(disable)
+;;     while (i < size) {
+;;         unsigned comp = i * multiplicand;
+;;         data[i] = comp; 
+;;         i++;
+;;     }
+;; }
+; CHECK: call void @llvm.dbg.value(metadata i64 %lsr.iv, metadata ![[i:[0-9]+]], metadata !DIExpression())
+; CHECK: call void @llvm.dbg.value(metadata !DIArgList(i64 %lsr.iv, i32 %multiplicand), metadata ![[comp:[0-9]+]], metadata !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_mul, DW_OP_stack_value))
+; CHECK: call void @llvm.dbg.value(metadata i64 %lsr.iv, metadata ![[i]], metadata !DIExpression(DW_OP_consts, 1, DW_OP_plus, DW_OP_stack_value))
+; CHECK: ![[i]] = !DILocalVariable(name: "i"
+; CHECK: ![[comp]] = !DILocalVariable(name: "comp"
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@__const.main.data = private unnamed_addr constant [16 x i32] [i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15], align 16
+
+define dso_local void @_Z21mul_pow_of_2_to_shiftjPjj(i32 %size, i32* nocapture %data, i32 %multiplicand) local_unnamed_addr !dbg !7 {
+entry:
+  call void @llvm.dbg.value(metadata i32 %size, metadata !12, metadata !DIExpression()), !dbg !13
+  call void @llvm.dbg.value(metadata i32* %data, metadata !14, metadata !DIExpression()), !dbg !13
+  call void @llvm.dbg.value(metadata i32 %multiplicand, metadata !15, metadata !DIExpression()), !dbg !13
+  call void @llvm.dbg.value(metadata i32 0, metadata !16, metadata !DIExpression()), !dbg !13
+  br label %while.cond, !dbg !13
+
+while.cond:                                       ; preds = %while.body, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.body ], !dbg !13
+  call void @llvm.dbg.value(metadata i32 %i.0, metadata !16, metadata !DIExpression()), !dbg !13
+  %cmp = icmp ult i32 %i.0, %size, !dbg !13
+  br i1 %cmp, label %while.body, label %while.end, !dbg !13
+
+while.body:                                       ; preds = %while.cond
+  %mul = mul i32 %i.0, %multiplicand, !dbg !17
+  call void @llvm.dbg.value(metadata i32 %mul, metadata !19, metadata !DIExpression()), !dbg !17
+  %idxprom = zext i32 %i.0 to i64, !dbg !17
+  %arrayidx = getelementptr inbounds i32, i32* %data, i64 %idxprom, !dbg !17
+  store i32 %mul, i32* %arrayidx, align 4, !dbg !17
+  %inc = add nuw i32 %i.0, 1, !dbg !17
+  call void @llvm.dbg.value(metadata i32 %inc, metadata !16, metadata !DIExpression()), !dbg !13
+  br label %while.cond, !dbg !13, !llvm.loop !20
+
+while.end:                                        ; preds = %while.cond
+  ret void, !dbg !13
+}
+
+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_C_plus_plus_14, file: !1, producer: "clang version 13.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "basic.cpp", directory: "/test")
+!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: "mul_pow_of_2_to_shift", linkageName: "_Z21mul_pow_of_2_to_shiftjPjj", scope: !1, file: !1, line: 17, type: !8, scopeLine: 17, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!8 = !DISubroutineType(types: !9)
+!9 = !{null, !10, !11, !10}
+!10 = !DIBasicType(name: "unsigned int", size: 32, encoding: DW_ATE_unsigned)
+!11 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !10, size: 64)
+!12 = !DILocalVariable(name: "size", arg: 1, scope: !7, file: !1, line: 17, type: !10)
+!13 = !DILocation(line: 0, scope: !7)
+!14 = !DILocalVariable(name: "data", arg: 2, scope: !7, file: !1, line: 17, type: !11)
+!15 = !DILocalVariable(name: "multiplicand", arg: 3, scope: !7, file: !1, line: 17, type: !10)
+!16 = !DILocalVariable(name: "i", scope: !7, file: !1, line: 18, type: !10)
+!17 = !DILocation(line: 21, column: 27, scope: !18)
+!18 = distinct !DILexicalBlock(scope: !7, file: !1, line: 20, column: 22)
+!19 = !DILocalVariable(name: "comp", scope: !18, file: !1, line: 21, type: !10)
+!20 = distinct !{!20, !21, !22, !23, !24}
+!21 = !DILocation(line: 20, column: 5, scope: !7)
+!22 = !DILocation(line: 24, column: 5, scope: !7)
+!23 = !{!"llvm.loop.mustprogress"}
+!24 = !{!"llvm.loop.vectorize.width", i32 1}

llvm/test/Transforms/LoopStrengthReduce/debuginfo-scev-salvage-4.ll

+; RUN: opt -S -loop-reduce %s -o - | FileCheck %s
+; REQUIRES: x86-registered-target
+
+;; Ensure that we retain debuginfo for the induction variable and dependant
+;; variables when loop strength reduction is applied to the loop. This test
+;; covers the translation of a SCEVCastExpr to DIExpression containg 
+;; DW_OP_LLVM_CONVERT. This IR produced from:
+;;
+;; clang -S -emit-llvm -Xclang -disable-llvm-passes -g lsr-basic.cpp -o
+;; Then executing opt -O2 up to the the loopFullUnroll pass.
+;; void mul_pow_of_2_to_shift(unsigned size, unsigned *data) {
+;; 
+;; void zext_scev(int64_t *arr, uint32_t factor0, int16_t factor1) {
+;;     uint32_t i = 0;
+;;     while(i < 63) {
+;;         uint32_t comp = factor0 - (4*i*factor1);
+;;         arr[i] = comp;
+;;         ++i;
+;;     }
+;; }
+; CHECK: call void @llvm.dbg.value(metadata i64 %lsr.iv, metadata ![[i:[0-9]+]], metadata !DIExpression())
+; CHECK: call void @llvm.dbg.value(metadata !DIArgList(i64 %lsr.iv, i16 %factor1, i32 %factor0), metadata ![[comp:[0-9]+]], metadata !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_consts, 18446744073709551612, DW_OP_LLVM_arg, 1, DW_OP_LLVM_convert, 32, DW_ATE_signed, DW_OP_mul, DW_OP_mul, DW_OP_LLVM_arg, 2, DW_OP_plus, DW_OP_stack_value))
+; CHECK: call void @llvm.dbg.value(metadata i64 %lsr.iv, metadata ![[i]], metadata !DIExpression(DW_OP_consts, 1, DW_OP_plus, DW_OP_stack_value))
+; CHECK: ![[i]] = !DILocalVariable(name: "i"
+; CHECK: ![[comp]] = !DILocalVariable(name: "comp"
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define dso_local void @_Z9zext_scevPljs(i64* nocapture %arr, i32 %factor0, i16 signext %factor1) local_unnamed_addr !dbg !90 {
+entry:
+  call void @llvm.dbg.value(metadata i64* %arr, metadata !94, metadata !DIExpression()), !dbg !95
+  call void @llvm.dbg.value(metadata i32 %factor0, metadata !96, metadata !DIExpression()), !dbg !95
+  call void @llvm.dbg.value(metadata i16 %factor1, metadata !97, metadata !DIExpression()), !dbg !95
+  call void @llvm.dbg.value(metadata i32 0, metadata !98, metadata !DIExpression()), !dbg !95
+  %conv = sext i16 %factor1 to i32
+  %mul.neg = mul i32 %conv, -4
+  call void @llvm.dbg.value(metadata i32 0, metadata !98, metadata !DIExpression()), !dbg !95
+  br label %while.body, !dbg !95
+
+while.body:                                       ; preds = %while.body, %entry
+  %i.04 = phi i32 [ 0, %entry ], [ %inc, %while.body ]
+  call void @llvm.dbg.value(metadata i32 %i.04, metadata !98, metadata !DIExpression()), !dbg !95
+  %mul1.neg = mul i32 %mul.neg, %i.04, !dbg !99
+  %sub = add i32 %mul1.neg, %factor0, !dbg !99
+  call void @llvm.dbg.value(metadata i32 %sub, metadata !101, metadata !DIExpression()), !dbg !99
+  %conv2 = zext i32 %sub to i64, !dbg !99
+  %idxprom = zext i32 %i.04 to i64, !dbg !99
+  %arrayidx = getelementptr inbounds i64, i64* %arr, i64 %idxprom, !dbg !99
+  store i64 %conv2, i64* %arrayidx, align 8, !dbg !99
+  %inc = add nuw nsw i32 %i.04, 1, !dbg !99
+  call void @llvm.dbg.value(metadata i32 %inc, metadata !98, metadata !DIExpression()), !dbg !95
+  %cmp = icmp ult i32 %inc, 63, !dbg !95
+  br i1 %cmp, label %while.body, label %while.end, !dbg !95, !llvm.loop !102
+
+while.end:                                        ; preds = %while.body
+  ret void, !dbg !95
+}
+
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+attributes #0 = { nofree nosync nounwind readnone speculatable willreturn }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!84, !85, !86, !87, !88}
+!llvm.ident = !{!89}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 13.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, imports: !3, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "cast.cpp", directory: "/test")
+!2 = !{}
+!3 = !{!4, !12, !16, !20, !24, !27, !29, !31, !33, !35, !37, !39, !41, !44, !46, !51, !55, !59, !63, !65, !67, !69, !71, !73, !75, !77, !79, !82}
+!4 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !6, file: !11, line: 48)
+!5 = !DINamespace(name: "std", scope: null)
+!6 = !DIDerivedType(tag: DW_TAG_typedef, name: "int8_t", file: !7, line: 24, baseType: !8)
+!7 = !DIFile(filename: "/usr/include/x86_64-linux-gnu/bits/stdint-intn.h", directory: "")
+!8 = !DIDerivedType(tag: DW_TAG_typedef, name: "__int8_t", file: !9, line: 36, baseType: !10)
+!9 = !DIFile(filename: "/usr/include/x86_64-linux-gnu/bits/types.h", directory: "")
+!10 = !DIBasicType(name: "signed char", size: 8, encoding: DW_ATE_signed_char)
+!11 = !DIFile(filename: "/usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/cstdint", directory: "")
+!12 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !13, file: !11, line: 49)
+!13 = !DIDerivedType(tag: DW_TAG_typedef, name: "int16_t", file: !7, line: 25, baseType: !14)
+!14 = !DIDerivedType(tag: DW_TAG_typedef, name: "__int16_t", file: !9, line: 38, baseType: !15)
+!15 = !DIBasicType(name: "short", size: 16, encoding: DW_ATE_signed)
+!16 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !17, file: !11, line: 50)
+!17 = !DIDerivedType(tag: DW_TAG_typedef, name: "int32_t", file: !7, line: 26, baseType: !18)
+!18 = !DIDerivedType(tag: DW_TAG_typedef, name: "__int32_t", file: !9, line: 40, baseType: !19)
+!19 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!20 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !21, file: !11, line: 51)
+!21 = !DIDerivedType(tag: DW_TAG_typedef, name: "int64_t", file: !7, line: 27, baseType: !22)
+!22 = !DIDerivedType(tag: DW_TAG_typedef, name: "__int64_t", file: !9, line: 43, baseType: !23)
+!23 = !DIBasicType(name: "long int", size: 64, encoding: DW_ATE_signed)
+!24 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !25, file: !11, line: 53)
+!25 = !DIDerivedType(tag: DW_TAG_typedef, name: "int_fast8_t", file: !26, line: 68, baseType: !10)
+!26 = !DIFile(filename: "/usr/include/stdint.h", directory: "")
+!27 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !28, file: !11, line: 54)
+!28 = !DIDerivedType(tag: DW_TAG_typedef, name: "int_fast16_t", file: !26, line: 70, baseType: !23)
+!29 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !30, file: !11, line: 55)
+!30 = !DIDerivedType(tag: DW_TAG_typedef, name: "int_fast32_t", file: !26, line: 71, baseType: !23)
+!31 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !32, file: !11, line: 56)
+!32 = !DIDerivedType(tag: DW_TAG_typedef, name: "int_fast64_t", file: !26, line: 72, baseType: !23)
+!33 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !34, file: !11, line: 58)
+!34 = !DIDerivedType(tag: DW_TAG_typedef, name: "int_least8_t", file: !26, line: 43, baseType: !10)
+!35 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !36, file: !11, line: 59)
+!36 = !DIDerivedType(tag: DW_TAG_typedef, name: "int_least16_t", file: !26, line: 44, baseType: !15)
+!37 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !38, file: !11, line: 60)
+!38 = !DIDerivedType(tag: DW_TAG_typedef, name: "int_least32_t", file: !26, line: 45, baseType: !19)
+!39 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !40, file: !11, line: 61)
+!40 = !DIDerivedType(tag: DW_TAG_typedef, name: "int_least64_t", file: !26, line: 47, baseType: !23)
+!41 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !42, file: !11, line: 63)
+!42 = !DIDerivedType(tag: DW_TAG_typedef, name: "intmax_t", file: !26, line: 111, baseType: !43)
+!43 = !DIDerivedType(tag: DW_TAG_typedef, name: "__intmax_t", file: !9, line: 61, baseType: !23)
+!44 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !45, file: !11, line: 64)
+!45 = !DIDerivedType(tag: DW_TAG_typedef, name: "intptr_t", file: !26, line: 97, baseType: !23)
+!46 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !47, file: !11, line: 66)
+!47 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint8_t", file: !48, line: 24, baseType: !49)
+!48 = !DIFile(filename: "/usr/include/x86_64-linux-gnu/bits/stdint-uintn.h", directory: "")
+!49 = !DIDerivedType(tag: DW_TAG_typedef, name: "__uint8_t", file: !9, line: 37, baseType: !50)
+!50 = !DIBasicType(name: "unsigned char", size: 8, encoding: DW_ATE_unsigned_char)
+!51 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !52, file: !11, line: 67)
+!52 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint16_t", file: !48, line: 25, baseType: !53)
+!53 = !DIDerivedType(tag: DW_TAG_typedef, name: "__uint16_t", file: !9, line: 39, baseType: !54)
+!54 = !DIBasicType(name: "unsigned short", size: 16, encoding: DW_ATE_unsigned)
+!55 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !56, file: !11, line: 68)
+!56 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint32_t", file: !48, line: 26, baseType: !57)
+!57 = !DIDerivedType(tag: DW_TAG_typedef, name: "__uint32_t", file: !9, line: 41, baseType: !58)
+!58 = !DIBasicType(name: "unsigned int", size: 32, encoding: DW_ATE_unsigned)
+!59 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !60, file: !11, line: 69)
+!60 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint64_t", file: !48, line: 27, baseType: !61)
+!61 = !DIDerivedType(tag: DW_TAG_typedef, name: "__uint64_t", file: !9, line: 44, baseType: !62)
+!62 = !DIBasicType(name: "long unsigned int", size: 64, encoding: DW_ATE_unsigned)
+!63 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !64, file: !11, line: 71)
+!64 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint_fast8_t", file: !26, line: 81, baseType: !50)
+!65 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !66, file: !11, line: 72)
+!66 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint_fast16_t", file: !26, line: 83, baseType: !62)
+!67 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !68, file: !11, line: 73)
+!68 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint_fast32_t", file: !26, line: 84, baseType: !62)
+!69 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !70, file: !11, line: 74)
+!70 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint_fast64_t", file: !26, line: 85, baseType: !62)
+!71 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !72, file: !11, line: 76)
+!72 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint_least8_t", file: !26, line: 54, baseType: !50)
+!73 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !74, file: !11, line: 77)
+!74 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint_least16_t", file: !26, line: 55, baseType: !54)
+!75 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !76, file: !11, line: 78)
+!76 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint_least32_t", file: !26, line: 56, baseType: !58)
+!77 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !78, file: !11, line: 79)
+!78 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint_least64_t", file: !26, line: 58, baseType: !62)
+!79 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !80, file: !11, line: 81)
+!80 = !DIDerivedType(tag: DW_TAG_typedef, name: "uintmax_t", file: !26, line: 112, baseType: !81)
+!81 = !DIDerivedType(tag: DW_TAG_typedef, name: "__uintmax_t", file: !9, line: 62, baseType: !62)
+!82 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !5, entity: !83, file: !11, line: 82)
+!83 = !DIDerivedType(tag: DW_TAG_typedef, name: "uintptr_t", file: !26, line: 100, baseType: !62)
+!84 = !{i32 7, !"Dwarf Version", i32 4}
+!85 = !{i32 2, !"Debug Info Version", i32 3}
+!86 = !{i32 1, !"wchar_size", i32 4}
+!87 = !{i32 7, !"uwtable", i32 1}
+!88 = !{i32 7, !"frame-pointer", i32 2}
+!89 = !{!"clang version 13.0.0"}
+!90 = distinct !DISubprogram(name: "zext_scev", linkageName: "_Z9zext_scevPljs", scope: !1, file: !1, line: 4, type: !91, scopeLine: 4, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!91 = !DISubroutineType(types: !92)
+!92 = !{null, !93, !56, !13}
+!93 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !21, size: 64)
+!94 = !DILocalVariable(name: "arr", arg: 1, scope: !90, file: !1, line: 4, type: !93)
+!95 = !DILocation(line: 0, scope: !90)
+!96 = !DILocalVariable(name: "factor0", arg: 2, scope: !90, file: !1, line: 4, type: !56)
+!97 = !DILocalVariable(name: "factor1", arg: 3, scope: !90, file: !1, line: 4, type: !13)
+!98 = !DILocalVariable(name: "i", scope: !90, file: !1, line: 5, type: !56)
+!99 = !DILocation(line: 7, column: 39, scope: !100)
+!100 = distinct !DILexicalBlock(scope: !90, file: !1, line: 6, column: 19)
+!101 = !DILocalVariable(name: "comp", scope: !100, file: !1, line: 7, type: !56)
+!102 = distinct !{!102, !103, !104, !105}
+!103 = !DILocation(line: 6, column: 5, scope: !90)
+!104 = !DILocation(line: 10, column: 5, scope: !90)
+!105 = !{!"llvm.loop.mustprogress"}