[Assignment Tracking Analysis][1/*] Add analysis pass core

[Orlando]

Summary

This patch stack implements the assignment tracking analysis. This patch contains the main body, but there are unfortunately a few more large code blobs to follow.

The problem and goal

Using the Assignment Tracking "model" it's not possible to determine a variable location just by looking at a debug intrinsic in isolation. Instructions without any metadata can change the location of a variable. The meaning of dbg.assign intrinsics changes depending on whether there are linked instructions, and where they are relative to those instructions. So we need to analyse the IR and convert the embedded information into a form that SelectionDAG can consume to produce debug variable locations in MIR.

The core of the solution is a dataflow analysis which, aiming to maximise the memory location coverage for variables, outputs a mapping of instruction positions to variable location definitions.

High level overview and API

AssignmentTrackingAnalysis is a pass that analyses IR to produce a mapping of instruction positions to variable location definitions. The results are encapsulated by the FunctionVarLocs class.

The pass is integrated with LLVM in this patch but the analysis is not used yet. A future patch updates SelectionDAG separately.

The results of the analysis are exposed via getResults using the returned const FunctionVarLocs *'s const methods:

const VarLocInfo *single_locs_begin() const;
const VarLocInfo *single_locs_end() const;
const VarLocInfo *locs_begin(const Instruction *Before) const;
const VarLocInfo *locs_end(const Instruction *Before) const;
void print(raw_ostream &OS, const Function &Fn) const;

Debug intrinsics can be ignored after running the analysis. Instead, variable location definitions that occur between an instruction Inst and its predecessor (or block start) can be found by looping over the range:

locs_begin(Inst), locs_end(Inst)

Similarly, variables with a memory location that is valid for their lifetime can be iterated over using the range:

single_locs_begin(Inst), single_locs_end(Inst)

Dataflow high level details

The analysis itself is a standard fixed point dataflow algorithm that traverses the CFG using a worklist that is initialised with every block in reverse post order. It computes a result for each visited block that is used to compute the result of successor blocks. Each time the result changes for a block its successors are added to the worklist if not already present. The analysis terminates when the result of every block is stable. Care has been taken to ensure that the merging of information from predecessor blocks yields a result that changes monotonically.

For each block we track "live-in" (LiveIn) and "live-out" (LiveOut) results. The former represents the currently known input to a block, which is the merged (join) result of the live-outs of visited predecessors (empty for the entry block). The live-in set is copied to create a working set for the block (LiveSet). The working set is modified as each instruction in the block is processed (process). After processing the last instruction in the block, the working set is the live-out result for the block. The "results" are BlockInfo objects. These encode assignments to memory and to variables, and track whether each variable's memory location is a good debug location for the variable or not. The actual variable location information (concrete implicit location value, or memory address) is stored off to the side in InsertBeforeMap, which is used after the dataflow is complete to build the instruction -> location definition mapping.

Patch tour

Here's a high-level call-graph that hopefully helps patch navigation.

+-runOnFunction
  +-analyzeFunction
    +-run
      +-process
      | +-processNonDbgInstruction
      | | +-processTaggedInstruction
      | | +-processUntaggedInstruction
      | |  
      | +-processDbgInstruction
      |   +-processDbgAssign
      |   +-processDbgValue
      |   
      +-join
        +-joinBlockInfo
          +-joinLocMap
          | +-joinKind
          |
          +-joinAssignmentMap
            +-joinAssignment

AssignmentTrackingLowering::run (just run above) is where the dataflow starts. Most of this function is dedicated to initialize helper structures and setup worklist traversal scaffolding. The important functions called from here are join and process.

It's probably easier to start with join as it will result in an understanding of the types involved, giving process more meaning. join is responsible for merging the live-outs of predecessors. See the docu-comment at the forward declaration in the class definition. join calls other joinXYZ methods and those call another set, working on merging every element of BlockInfo.

BlockInfo is made up of 3 maps.

LocMap LiveLoc;
AssignmentMap StackHomeValue;
AssignmentMap DebugValue;

LiveLoc maps variables to LocKind, which describes the current kind of location for each variable.
StackHomeValue maps variables the last Assignment to its stack slot (N.B. looking at this now, maybe it should be keyed by address rather than variable - this can come later as a refactor if necessary as it will likely need changing with one of the TODO list items (in D132220)).
DebugValue maps variables to the last Assignment to the variable.

process is where instructions in a block are analysed. The important functions here are addMemDef, addDbgDef, setLocKind, and emitDbgValue. All the leaf process functions call these so I didn't add them to the call graph map. A call to addMemDef states a store with a given ID to a variable fragments's memory location has occurred . Similarly, addDbgDef states an assignment with an ID to a fragment of a variable has occurred. When the variable's memory location assignment and the debug assignment "match" a variable location definition describing the memory location is emitted. Otherwise, an appropriate implicit location value is chosen. setLocKind sets whether the current variable location for the variable is Mem, Val or None and emitDbgValue saves the location to InsertBeforeMap.

The analysis tracks locations for each fragment of each variable that has a definition (/is used in a debug intrinsic). addMemDef, addDbgDef, and setLocKind apply their changes to all fragments contained fully within the one passed in. So, an assignment to bits [0, 64) of a variable is noted for bits [0, 32) too.

I'm aware this patch is large and that tour is not. Hopefully it gives reviewers a good starting point though. Please don't hesitate to ask questions!

---

Tests are coming in a separate patch.

[nlopes]

Please avoid using UndefValue::get as much as possible as we are trying to get rid of undef. Please use PoisonValue whenever possible.
Thank you!

[StephenTozer]

Still reviewing, with possibly higher-level comments coming, but just putting forward some of the smaller stuff now.

llvm/include/llvm/CodeGen/AssignmentTrackingAnalysis.h

25

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

57–58

I think the main value is in having FunctionVarLocs be a read-only interface, which I think makes the split worthwhile.

63

177

Could be a little more verbose.

188–189

Is there a reason this couldn't be inserted with .insert()? The for-loop with emplace_back would only be necessary if Variables and Builder->Variables were different types I think, but I might be missing something.

275–279

Does this behaviour need to be performed by operator==? I see it's used explicitly in hasVarWithValue to determine whether a valid stack home location exists for a variable, and also in equ to compare AssignmentMaps, but before looking for the definition for this operator I was a bit confused as to when that function would ever return true, since the Source field here would be different between DbgDefs and MemDefs. It's a bit of a surprise that operator== doesn't compare all of the fields in this class, especially since this is close to being a POD-type; if this isn't needed to make some template class functions work, could this be changed to be a distinct function isJoinableWith (or another name if you see fit)?

309–313

Minor typo. Also, is there a reason that the argument assigned to ID is called Value? Asking more to actually understand the name assuming that there is a reason, although if there isn't any particular reason then I'd suggest changing the name.

311

330

Slight rename request; either this or anything along these lines.

353

535–538

Comment seems out-of-date w.r.t. the arguments; would it be more accurate as "Return true if Var has an assignment in M equal to AV." or something similar?
Also, the name feels slightly misleading here, as "Value" might be reasonably interpreted as referring to a Value, whereas this function only cares about the Status and DIAssignID; seems similar to the use of Value in the Assignment constructor above.

591

Nit, but I think you can just use the boolean value of an optional for this?

677–679

Not sure I understand the first part of this comment, "Use an assignment ID that nothing can match against" - is this just referring to the fact that there is no DIAssignID, so makeNoneOrPhi must be used to create the Assignment? Also, minor typo.

692–693

732

Could do with a shortened version of the comment as an assert message here.

761

974

This check looks identical to the definition of Assignment::operator!=, could use that instead (though I think it should also be a distinct function instead of an operator, see comment above).

[Orlando]

Many thanks for taking this review on. I've answered some of your questions in line.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

188–189

They are indeed different types - Variables is a SmallVector and Builder->Variables is a UniqueVector (I figured there was no need in paying the additional memory overhead cost of a UniqueVector since we're done inserting elements at this point.

275–279

SGTM

309–313

Hmmm, no reason that I can remember. I think it's probably just a prototype-hangover - I'll change it.

535–538

Yep you are right there. Agree that the name is misleading, I'll change that.

677–679

is this just referring to the fact that there is no DIAssignID, so makeNoneOrPhi must be used to create the Assignment

Pretty much. By "nothing can match against [it]" I meant hasVarWithValue will return false now for Known AssignmentValues. I am not sure this extra commentary is necessary though - I think I'll cut it down.

[StephenTozer]

General implementation of the patch LGTM!

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

188–189

Sorry, I meant the element types of the vectors - even for different vector types, I believe Variables.insert(Variables.begin(), Builder->Variables.begin(), Builder->Variables.end()); should work - if not, then please ignore!

663

Just confirming, will this loop body be executed multiple times for the same variable if the base alloca is linked to multiple DbgAssignIntrinsics? I don't think it would result in any incorrectness if that is the case, since this loop body is idempotent, but it might slow things down a little and possibly spam dbgs() a bit.

1235

Could remove the !Pending.empty() condition, since Pending is empty when we reach this loop and is asserted to be empty at the end of each iteration?

1289–1291

Nit, shadowed variables here and in the "Insert the other DEFs" loop below (could use structured bindings?)

1319

Nit: Normally not too bothered about having many asserts even when they seem obvious, but assert(Simple) probably isn't needed just a few statements down from if (!Simple) { ...; continue; }

1396

[Orlando]

In D136320#3870269, @nlopes wrote:

Please avoid using UndefValue::get as much as possible as we are trying to get rid of undef. Please use PoisonValue whenever possible.
Thank you!

Hi @nlopes. This patch is part of the series in which we agreed this could be addressed after landing the stack: https://reviews.llvm.org/D133293#inline-1286892. That is the next item on my TODO list and I plan to make the change for all debug info modes (rather than just this new one). Is that still okay with you?

---

Thanks @StephenTozer, I've made those changes.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

188–189

Aha, gotcha, thanks. Changed to use append.

663

Yeah it will. I think that having multiple identical dbg.assigns linked to an alloca is unlikely though - IMO it's not worth filtering them out.

1235

True, nice catch.

1289–1291

could use structured bindings

Not for the outer loop as first isn't used & causes an unused variable warning. Will do for the second (this code was written before the move to C++17!).

1319

I've added a comment - if you still think it should go then I'll remove it.

[nlopes]

In D136320#3930388, @Orlando wrote:

In D136320#3870269, @nlopes wrote:

Please avoid using UndefValue::get as much as possible as we are trying to get rid of undef. Please use PoisonValue whenever possible.
Thank you!

Hi @nlopes. This patch is part of the series in which we agreed this could be addressed after landing the stack: https://reviews.llvm.org/D133293#inline-1286892. That is the next item on my TODO list and I plan to make the change for all debug info modes (rather than just this new one). Is that still okay with you?

Ah, yes, sorry, my spam bot is very indiscriminate..

[jmorse]

I'm in as far as line 900, hitting submit to clear the queue of comments just in case I don't get back to this. Random remarks:

NB: the locs_begin and single_locs_begin ranges could also have a locs() and single_locs() methods that return iterator_range objects made with make_range, that allows you to use range-based for loops. On the other hand, there's only two places in this patch that they're used, so it might not be a big deal.

Using the term "location" everywhere initially made me twitch as in the IR we have Values... but then again the whole point of assignment tracking is that the location can sometimes be the stack, where the Value isn't know.

Why does NotAlwaysStackHomed ignore fragments -- can't SROA cut up variables into parts, some of which could be partially promoted and mutated, others of which aren't? Perhaps it's an approximation where any partially promoted variable gets explicitly tracked for all fields (this seems fine).

llvm/include/llvm/CodeGen/AssignmentTrackingAnalysis.h

2–3

meganit, s/LIB/INCLUDE/, or something

9–12

Is this convention, to close and open the namespace each time?

34

36

39–42

Shouldn't the comment wording be inverted -- it maps a position to a range, no?

56–58

I'd suggest returning a (const?) reference unless there's a real need to return a temporary.

66

I recommend std::advance to do exactly the same thing, but making it very clear to the reader that you're messing with iterators, rather than having to consider that there's pointer arithmetic happening. Here and elsewhere.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

2

IIRC clang-format has an opinion on the order of includes

78–80

Return a const reference instead?

84

Recommend returning a SmallVectorImpl pointer, which I think is a superclass of SmallVector. There's no practical difference but it avoids implicitly encoding the size of the vector in the method information.

(I get the feeling this wants to be std::optional too, however you can't have optional references iirc, so it's probably a bad idea).

91–95

Given the usage of this method, consider an rvalue / std::moveable method too, that might save some un-necessary memory allocations.

105

I want to say "use emplace_back", but I can't imagine it makes much difference. Up to you.

165

Reference argument instead of pointer? It's unconditionally dereferenced.

176

auto & or you'll generate a temporary, I think.

180

205

Passing in a reference to a pointer might be slightly neater -- depends whether the explicit dereferencing of Expression is designed to signal to the reader that there's a side-effect. An alternative would be returning a {Value,Expression} pair. This is slightly stylistic, up to you.

212–213

This prepending could be put inside the conditional, yes?

238–240

This doesn't seem to be how joinKind implements it; additionally if we can switch from {Mem,Val} to None, and then {None,Mem} to Mem, doesn't that mean there can be a "Val" in a predecessor block but this isn't reflected in the lattice value.

245

I'm not sure -> it's not clear, to avoid the reader questioning "who?"

268–273

IMO: too much detail about the algorithm for just a field, better to have that detail in a function, and just the first line documenting the field.

312

IMHO, simpler to read if it's Status == NoneOrPHI || ID, YMMV.

325–326

A map of maps sounds expensive -- do both keys of this really need to be randomly accessed, or could they instead be inserted and sorted at a later date? (I haven't read far down enough to get a grip of how the container is used.

361

This is another one of those places where I feel the word "dominance frontier" can be inserted to a) make ourselves feel clever, and b) actually disambiguate what's going on. i.e., "NoneOrPhi indicates whether there is a single dominating definition which can be found in StackHomeValue or DebugValue". Or something like that? (Might not be right).

384–385

These translate to maps of maps again, which risks an expensive reallocation. There isn't necessarily anything to do about this if that's not triggered by the workloads that actaully exist.

[jmorse]

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

393

const & argument?

414–415

This wants explaining why -- it's because the top value represents "don't know", right?

426–427

If it's initialized, pass by reference instead?

435

and below

444

As ever, default to passing the BlockInfo by reference, and AV as const reference, just for simplicity and to avoid un-necessary locals? And below.

475

Var itself is a fragment, right? Small risk that the reader thinks it's a DILocalVariable? (Our terminology doesn't help).

493–494

This slightly threw me; the "None" value being set isn't important because everything that calls addMemDef calls setLocKind too, right? If so, best to document this in a comment please.

565–568

If it's a scenario that llvm will never generate nowadays, and the test is testing something unrelated, might be easier to fix the test rather than make the actual code suffer for the past.

571

Hhrrrrmmmm. Using getNextNode makes me twitch on account of it being the source of various debug-affects-codegen problems in the past, or hard-to-unpick debug behaviours. In this context it's certainly the right thing to use though (fry-eyes.jpg)

635

This is all fine; IMO there needs to be a moderately detailed comment about what this is doing at the overall-algorithm level, i.e. "interpret stack stores that are not tagged as an assignment in memory because [blah]". I remember this from past discussions, IMO it should be stated at the outset what this method is aiming to do.

648

Is this cast necessary? Might be better to put a trailing type on the lambda to make it un-necessary? Any particular need for a lambda instead of something else?

679

716

This looks good; I suspect I'd find tests highly valuable in this situation to understand exactly the behaviour that's being created, I understand they're in a later patch though.

751

early-continue here will save a level of indentation for the rest of the loop.

825

It looks slightly out of place that the LocKind is recorded as a Val, but then emitDbgValue is used with LocKind::Mem -- I suppose the problem is that I don't know what's meant by elision of the original store. What are the effects of this scenario {LocKind==Val,emitDbgValue(Mem...)}?

838

\n

847–849

Would I be right in thinking that these dbg.values turn up because of promotion, and thus the dbg.values are "normally" attached to PHIs? If so, is it possible to assert that fact. If not maybe the comment could be reworded to give the impression that this isn't an omission in the design, it's the natural effect of the design. (I think the term "we must..." makes me feel like it's a defect).

[jmorse]

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

916

Note to self, returning a DenseMap by value is probably fine if it gets NRVO'd.

933

auto & or you might get storage.

976

Coming immediately after the leading comment, shouldn't this also check if A.Status == NoneOrPhi?

1088

/me squints -- I want to say that BBLiveIn being the argument and the return value will lead to some kind of aliasing weirdness or performance slowdown (in the form of un-necessary DenseMap copies). I can't actually put my finger on why that would be forced though. Do you have any feeling for it?

1192

[jmorse]

(Ticking "request changes" to take it out of the review queue)

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

1329

auto &, don't want to risk copying the mapvector

[Orlando]

Ah, yes, sorry, my spam bot is very indiscriminate..

Great, thanks! & no worries.

---

Thanks @jmorse for the detailed review - that should be all the inline comments addressed (or responded-to) but please do ping if I missed any.

NB: the locs_begin and single_locs_begin ranges could also have a locs() and single_locs() methods that return iterator_range objects made with make_range, that allows you to use range-based for loops. On the other hand, there's only two places in this patch that they're used, so it might not be a big deal.

Initially I opted to avoid adding more code, happy to change that if you prefer.

Using the term "location" everywhere initially made me twitch as in the IR we have Values... but then again the whole point of assignment tracking is that the location can sometimes be the stack, where the Value isn't know.

Why does NotAlwaysStackHomed ignore fragments -- can't SROA cut up variables into parts, some of which could be partially promoted and mutated, others of which aren't? Perhaps it's an approximation where any partially promoted variable gets explicitly tracked for all fields (this seems fine).

Yeah it is an approximation - we only consider variables that are wholly located in one alloca as ones to put in the MachineFunction stacked-homed-variable side table. SROAd variables that you described above will fall back to using location lists (which may include stack locations).

llvm/include/llvm/CodeGen/AssignmentTrackingAnalysis.h

2–3

Changed to copy other headers in include/CodeGen.

9–12

Ah, nope, that was include-what-you-use. Fixed.

39–42

It made sense to me but happy to change it.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

2

clang-format was happy with (/reinstated) this order (perhaps xxx.h is allowed at the top of xxx.cpp).

91–95

I think the next patches in the stack have similar usage so I've just removed the copying version.

205

signal to the reader that there's a side-effect

That was the intention, but I prefer yout pair idea. Done.

238–240

This comment is wrong / out of date, sorry. Fixed.

268–273

Moved the comment body into joinAssignment.

325–326

The maps are { instruction that comes after : { variable frag instance : location definition }. The location definitions are added to the map each time they're calculated. Huh - I think this needs to clear the sub-map each before each instruction is visited. And after doing that, I can see that we don't need the sub-map at all. Replaced and added resetInsertionPoint. Good spot, thanks.

361

That code comment is indeed confusing at best. I've had a go at rewording it, let me know what you think. Happy to make further changes.

384–385

I'm not sure that these ones can be avoided. These are at least initialized to a size equal to the number of basic blocks, down in AssignmentTrackingLowering::run.

414–415

I've elaborated a bit. Is this ok or does it need more?

426–427

I chose to use a pointer to hint at call sites that it is modified. If that is not compelling (or the hint is not doing its job) I can change it - just thought I'd offer up my rationale first in case it made a difference.

444

(process reply applies - made the const& change though)

475

Yes (if by "is a fragment" you mean is an ID that identifies a {DILocalVariable, FragmentInfo, InlinedAt} tuple aka a DebugVariable, which indeed includes fragment information). I don't think I've deviated massively from common naming practices but I agree that our terminology isn't necessarily helpful here. DebugVariable should probably be called something like VariableInstanceFragment (but that is outside the scope of this patch of course). Do you have any suggestions for Var / VariableID?

493–494

Yeah that's right, in this instance we're just adding Var to LiveSet if it isn't there already (using insert). I'll update the comment

565–568

It still happens - it's what is returned in by getVariableLocationOp when the wrapped Value is replaced with empty metadata.

635

I've put that here but is there somewhere better for it should live / be copied to, do you think? (& what do you think of the comment?).

648

Ah, AssignmentInfo has no default ctor so we can't do this:

AssignmentInfo Info;
if ...
    Info = ....
else if ...
     Info = ...

Let me know if you'd prefer that though as I can just add one.

825

It looks slightly out of place that the LocKind is recorded as a Val, but then emitDbgValue is used with LocKind::Mem

It does look slightly out of place. This could be a bug - I'll get back to you on this one.

847–849

They should mostly be attached to PHIs, but can sneak in in other ways too. I'll reword it.

916

That's what I'm counting on, but I'm happy to change it if it's unconventional / looks suspicious.

933

Good point - and changed to use structured binding for the pair while I'm here (and in`joinAssignmentMap`).

976

That is checked right here above your review comment. I used separate ifs for readability, but happy to combine them if this was counterproductive?

1088

Hmmm, I don't remember this sticking out in the profiles but it was a while ago that I looked at the performance. I have wrapped the argument in a std::move, which could help.

[jmorse]

Looks good with some nits fixed, a spurious return removed, and the question on line 825 addressed.

Of course, landing this would require some tests; I believe you'll get stern looks if this lands with nothing covering it. Thus you might want to fold in the tests from patch 5 as appropriate, when they're reviewed.

llvm/include/llvm/CodeGen/AssignmentTrackingAnalysis.h

66

(done below, but here appreciated too, not a blocker)

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

165

While we're at it, const auto &

361

Much more understandable now, cheers!

384–385

Hrrrmmm. I suppose over in LiveDebugValues we have exactly this, but with a SmallVector of DenseMaps where the block number is the index. That's pretty much identical to LiveIn / LiveOut here. Given this is a dataflow algorithm, random access to blocks is unavoidable, and within those random access to variables, which requires two levels of map.

That being said, I eventually found it faster to deal with a single variable at a time and trade one locality with another. But again, we should only re-visit this if it turns out that there's a performance loss.

414–415

SGTM

426–427

(I think this was applied to process before the comments floated) This is moderately a style thing, so up to you in the end.

475

Nah, just making sure I understood correctly.

648

No need, a potentially un-necessary lambda is better than opening the scope of "bugs we can introduce by allowing default-constructed data structures".

656

825

(This space intentionally left blank -- to signal to myself that there'll be a response coming back from you at some point).

898

Reference rather than pointer given it's unconditionally dereferenced?

900

Leftover return from prototyping?

976

Nah, I'm just blind apparently

[Orlando]

That should be all comments addressed

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

384–385

SGTM

825

Updated this (use same LocKind for setLocKind / emitDbgValue here). I am not sure that we need the undef check at all though as this pattern is no longer generated (at least not on purpose). This change results in a DBG_VALUE $noreg to lose DW_OP_deref from its expression in mem-loc-frag-fill.ll in the test patch.

[Orlando]

Of course, landing this would require some tests; I believe you'll get stern looks if this lands with nothing covering it. Thus you might want to fold in the tests from patch 5 as appropriate, when they're reviewed.

My original plan / hope was to land these analysis patches and tests contiguously. If that isn't agreeable then I can try to fold some in, though it'll still require either squashing or contiguous patch landing because this patch requires D136331 to land before it can actually be tested.

[Orlando]

In improving test coverage in D136335 I discovered a bug: the fragments that untagged stores affect were not added to the OverlapMap` (map of fragment to fragments that are contained within). This meant that fragments were not always correctly clobbered upon visiting an untagged store. I've fixed this by adding yet more analysis setup code to buildOverlapMapAndRecordDeclares. This function now also interprets untagged stores to add the fragments to the OverlapMap and populates UntaggedStoreVars, caching the assignment info (offset, size, base alloca, variable fragment) for lookup during the analysis.

[Orlando]

Fix another bug to do with fragments that was found with a new test in D136335. In short: we weren't checking for matching assignments to fragments contained within a fragment, so a def of a larger fragment would still be considered live after a def to a contained fragment (if the larger fragment assignment was queried only).

[jmorse]

Latest two revisions look good -- except that you've not merged them together when uploading them, so the latter overwrite the former!

Overall LGTM -- as discussed offline, it's awkward that these five patches all depend on each other. We should try for landing the lot together (and seeing what magnitude of breakage the buildbots discover) and then possibly decompose the merged patch down from there.

[Orlando]

Latest two revisions look good -- except that you've not merged them together when uploading them, so the latter overwrite the former!

Ah, nice catch - I'd re-ordered my patches in a rebase and then missed the first patch (reordered to top of stack) from the second update (and accidentally dragged in other changes too). Sorry about that! That should be fixed now.

[Orlando]

Squashed into 1d1de7467c32d52926ca56b9167a2c65c451ecfa

llvm/include/llvm/CodeGen/AssignmentTrackingAnalysis.h

+#ifndef LLVM_LIB_CODEGEN_ASSIGNMENTTRACKINGANALYSIS_H
+#define LLVM_LIB_CODEGEN_ASSIGNMENTTRACKINGANALYSIS_H
+
+#include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/Pass.h"
+#include "llvm/IR/DebugLoc.h"
+
+namespace llvm { class Function; }
+namespace llvm { class Instruction; }
+namespace llvm { class Value; }
+namespace llvm { class raw_ostream; }
+class FunctionVarLocsBuilder;
+
+namespace llvm {
+/// Type wrapper for integer ID for Variables. 0 is reserved.
+enum class VariableID : unsigned { Reserved = 0 };
+/// Variable location definition used by FunctionVarLocs.
+struct VarLocInfo {
+  llvm::VariableID VariableID;
+  DIExpression *Expr = nullptr;
+  DebugLoc DL;
+  Value *V = nullptr; // TODO: Needs to be value_s_ for variadic expressions.
+};
+
+/// Datastructure describing the variable locations in a function. Used as the
+/// result of the AssignmentTrackingAnalysis pass. Essentially read-only
+/// outside of AssignmentTrackingAnalysis where it is built.
+class FunctionVarLocs {
+  /// Maps VarLocInfo.VariableID to a DebugVariable for VarLocRecords.
+  SmallVector<DebugVariable> Variables;
+  /// List of variable location changes grouped by the instruction the
+  /// change occurs before (see VarLocsBeforeInst). The elements from
+  /// zero to SingleVarLocEnd represent variable with a single location.
+  SmallVector<VarLocInfo> VarLocRecords;
+  // End of range of VarLocRecords that represent variables with a single
+  // location that is valid for the entire scope. Range starts at 0.
+  unsigned SingleVarLocEnd = 0;
+  // Maps a range of VarLocRecords to the position before a particular
+  // instruction.
+  DenseMap<const Instruction *, std::pair<unsigned, unsigned>>
+      VarLocsBeforeInst;
+
+public:
+  /// Return the DILocalVariable for the location definition represented by \p
+  /// ID.
+  DILocalVariable *getDILocalVariable(const VarLocInfo *Loc) const {
+    VariableID VarID = Loc->VariableID;
+    return getDILocalVariable(VarID);
+  }
+  /// Return the DILocalVariable of the variable represented by \p ID.
+  DILocalVariable *getDILocalVariable(VariableID ID) const {
+    return const_cast<DILocalVariable *>(getVariable(ID).getVariable());
+  }
+  /// Return the DebugVariable represented by \p ID.
+  DebugVariable getVariable(VariableID ID) const {
+    return Variables[static_cast<unsigned>(ID)];
+  }
+
+  ///@name iterators
+  ///@{
+  /// First single-location variable location definition.
+  const VarLocInfo *single_locs_begin() const { return VarLocRecords.begin(); }
+  /// One past the last single-location variable location definition.
+  const VarLocInfo *single_locs_end() const {
+    return VarLocRecords.begin() + SingleVarLocEnd;
+  }
+  /// First variable location definition that comes before \p Before.
+  const VarLocInfo *locs_begin(const Instruction *Before) const {
+    auto Span = VarLocsBeforeInst.lookup(Before);
+    return VarLocRecords.begin() + Span.first;
+  }
+  /// One past the last variable location definition that comes before \p
+  /// Before.
+  const VarLocInfo *locs_end(const Instruction *Before) const {
+    auto Span = VarLocsBeforeInst.lookup(Before);
+    return VarLocRecords.begin() + Span.second;
+  }
+  ///@}
+
+  void print(raw_ostream &OS, const Function &Fn) const;
+
+  ///@{
+  /// Non-const methods used by AssignmentTrackingAnalysis (which invalidate
+  /// analysis results if called incorrectly).
+  void init(FunctionVarLocsBuilder *Builder);
+  void clear();
+  ///@}
+};
+
+class AssignmentTrackingAnalysis : public FunctionPass {
+  std::unique_ptr<FunctionVarLocs> Results;
+
+public:
+  static char ID;
+
+  AssignmentTrackingAnalysis();
+
+  bool runOnFunction(Function &F) override;
+
+  static bool isRequired() { return true; }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+
+  const FunctionVarLocs *getResults() { return Results.get(); }
+};
+
+} // end namespace llvm
+#endif // LLVM_LIB_CODEGEN_ASSIGNMENTTRACKINGANALYSIS_H

llvm/include/llvm/InitializePasses.h

 
 void initializeAAEvalLegacyPassPass(PassRegistry&);
 void initializeAAResultsWrapperPassPass(PassRegistry&);
 void initializeADCELegacyPassPass(PassRegistry&);
 void initializeAddDiscriminatorsLegacyPassPass(PassRegistry&);
 void initializeAddFSDiscriminatorsPass(PassRegistry &);
 void initializeModuleAddressSanitizerLegacyPassPass(PassRegistry &);
 void initializeASanGlobalsMetadataWrapperPassPass(PassRegistry &);
+void initializeAssignmentTrackingAnalysisPass(PassRegistry &);
 void initializeAddressSanitizerLegacyPassPass(PassRegistry &);
 void initializeAggressiveInstCombinerLegacyPassPass(PassRegistry&);
 void initializeAliasSetPrinterPass(PassRegistry&);
 void initializeAlignmentFromAssumptionsPass(PassRegistry&);
 void initializeAlwaysInlinerLegacyPassPass(PassRegistry&);
 void initializeAssumeSimplifyPassLegacyPassPass(PassRegistry &);
 void initializeAssumeBuilderPassLegacyPassPass(PassRegistry &);
 void initializeAnnotation2MetadataLegacyPass(PassRegistry &);

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

+#include "llvm/CodeGen/AssignmentTrackingAnalysis.h"
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/IntervalMap.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/UniqueVector.h"
+#include "llvm/Analysis/Interval.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DebugInfo.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/IR/PrintPasses.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include <assert.h>
+#include <cstdint>
+#include <sstream>
+#include <unordered_map>
+
+using namespace llvm;
+#define DEBUG_TYPE "debug-ata"
+
+static cl::opt<unsigned>
+    MaxNumBlocks("debug-ata-max-blocks", cl::init(10000),
+                 cl::desc("Maximum num basic blocks before debug info dropped"),
+                 cl::Hidden);
+/// Print the results of the analysis. Respects -filter-print-funcs.
+static cl::opt<bool> PrintResults("print-debug-ata", cl::init(false),
+                                  cl::Hidden);
+
+// Implicit conversions are disabled for enum class types, so unfortunately we
+// need to create a DenseMapInfo wrapper around the specified underlying type.
+template <> struct llvm::DenseMapInfo<VariableID> {
+  using Wrapped = DenseMapInfo<unsigned>;
+  static inline VariableID getEmptyKey() {
+    return static_cast<VariableID>(Wrapped::getEmptyKey());
+  }
+  static inline VariableID getTombstoneKey() {
+    return static_cast<VariableID>(Wrapped::getTombstoneKey());
+  }
+  static unsigned getHashValue(const VariableID &Val) {
+    return Wrapped::getHashValue(static_cast<unsigned>(Val));
+  }
+  static bool isEqual(const VariableID &LHS, const VariableID &RHS) {
+    return LHS == RHS;
+  }
+};
+
+/// Helper class to build FunctionVarLocs, since that class isn't easy to
+/// modify. TODO: There's not a great deal of value in the split, it could be
+/// worth merging the two classes.
+class FunctionVarLocsBuilder {
+  friend FunctionVarLocs;
+  UniqueVector<DebugVariable> Variables;
+  // Use an unordered_map so we don't invalidate iterators after
+  // insert/modificaitons.
+  std::unordered_map<const Instruction *, SmallVector<VarLocInfo>>
+      VarLocsBeforeInst;
+
+  SmallVector<VarLocInfo> SingleLocVars;
+
+public:
+  /// Find or insert \p V and return the ID.
+  VariableID insertVariable(DebugVariable V) {
+    return static_cast<VariableID>(Variables.insert(V));
+  }
+
+  /// Get a variable from its \p ID.
+  DebugVariable getVariable(VariableID ID) const {
+    return Variables[static_cast<unsigned>(ID)];
+  }
+
+  /// Return ptr to wedge of defs or nullptr if no defs come just before /p
+  /// Before.
+  const SmallVector<VarLocInfo> *getWedge(const Instruction *Before) const {
+    auto R = VarLocsBeforeInst.find(Before);
+    if (R == VarLocsBeforeInst.end())
+      return nullptr;
+    return &R->second;
+  }
+
+  /// Replace the defs that come just before /p Before with /p Wedge.
+  void setWedge(const Instruction *Before,
+                const SmallVector<VarLocInfo> &Wedge) {
+    VarLocsBeforeInst[Before] = Wedge;
+  }
+
+  /// Add a def for a variable that is valid for its lifetime.
+  void addSingleLocVar(DebugVariable Var, DIExpression *Expr, DebugLoc DL,
+                       Value *V) {
+    VarLocInfo VarLoc;
+    VarLoc.VariableID = insertVariable(Var);
+    VarLoc.Expr = Expr;
+    VarLoc.DL = DL;
+    VarLoc.V = V;
+    SingleLocVars.push_back(VarLoc);
+  }
+
+  /// Add a def to the wedge of defs just before /p Before.
+  void addVarLoc(Instruction *Before, DebugVariable Var, DIExpression *Expr,
+                 DebugLoc DL, Value *V) {
+    VarLocInfo VarLoc;
+    VarLoc.VariableID = insertVariable(Var);
+    VarLoc.Expr = Expr;
+    VarLoc.DL = DL;
+    VarLoc.V = V;
+    VarLocsBeforeInst[Before].push_back(VarLoc);
+  }
+};
+
+void FunctionVarLocs::print(raw_ostream &OS, const Function &Fn) const {
+  // Print the variable table first. TODO: Sorting by variable could make the
+  // output more stable?
+  unsigned Counter = -1;
+  OS << "=== Variables ===\n";
+  for (const DebugVariable &V : Variables) {
+    ++Counter;
+    // Skip first entry because it is a dummy entry.
+    if (Counter == 0) {
+      continue;
+    }
+    OS << "[" << Counter << "] " << V.getVariable()->getName();
+    if (auto F = V.getFragment())
+      OS << " bits [" << F->OffsetInBits << ", "
+         << F->OffsetInBits + F->SizeInBits << ")";
+    if (const auto *IA = V.getInlinedAt())
+      OS << " inlined-at " << *IA;
+    OS << "\n";
+  }
+
+  auto PrintLoc = [&OS](const VarLocInfo &Loc) {
+    OS << "DEF Var=[" << (unsigned)Loc.VariableID << "]"
+       << " Expr=" << *Loc.Expr << " V=" << *Loc.V << "\n";
+  };
+
+  // Print the single location variables.
+  OS << "=== Single location vars ===\n";
+  for (auto It = single_locs_begin(), End = single_locs_end(); It != End;
+       ++It) {
+    PrintLoc(*It);
+  }
+
+  // Print the non-single-location defs in line with IR.
+  OS << "=== In-line variable defs ===";
+  for (const BasicBlock &BB : Fn) {
+    OS << "\n" << BB.getName() << ":\n";
+    for (const Instruction &I : BB) {
+      for (auto It = locs_begin(&I), End = locs_end(&I); It != End; ++It) {
+        PrintLoc(*It);
+      }
+      OS << I << "\n";
+    }
+  }
+}
+
+void FunctionVarLocs::init(FunctionVarLocsBuilder *Builder) {
+  // Add the single-location variables first.
+  for (auto VarLoc : Builder->SingleLocVars)
+    VarLocRecords.emplace_back(VarLoc);
+  // Mark the end of the section.
+  SingleVarLocEnd = VarLocRecords.size();
+
+  // Insert a contiguous block of VarLocInfos for each instruction, mapping it
+  // to the start and end position in the vector with VarLocsBeforeInst.
+  for (auto &P : Builder->VarLocsBeforeInst) {
+    unsigned BlockStart = VarLocRecords.size();
+    for (auto VarLoc : P.second)
+      VarLocRecords.emplace_back(VarLoc);
+    unsigned BlockEnd = VarLocRecords.size();
+    // Record t
+    if (BlockEnd - BlockStart != 0)
+      VarLocsBeforeInst[P.first] = {BlockStart, BlockEnd};
+  }
+
+  // Copy the Variables vector from the builder's UniqueVector.
+  assert(Variables.empty() && "Expect clear before init");
+  // UniqueVectors IDs are one-based (which means the VarLocInfo VarID values
+  // are one-based) so reserve an extra and insert a dummy.
+  Variables.reserve(Builder->Variables.size() + 1);
+  Variables.push_back(DebugVariable(nullptr, None, nullptr));
+  for (auto VarLoc : Builder->Variables)
+    Variables.emplace_back(VarLoc);
+}
+
+void FunctionVarLocs::clear() {
+  Variables.clear();
+  VarLocRecords.clear();
+  VarLocsBeforeInst.clear();
+  SingleVarLocEnd = 0;
+}
+
+/// Walk backwards along constant GEPs and bitcasts to the base storage from \p
+/// Start as far as possible. Prepend \Expression with the offset and append it
+/// with a DW_OP_deref that has been implicit until now.
+static Value *walkToAllocaAndPrependOffsetDeref(const DataLayout &DL,
+                                                Value *Start,
+                                                DIExpression **Expression) {
+  APInt OffsetInBytes(DL.getTypeSizeInBits(Start->getType()), false);
+  Value *End =
+      Start->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetInBytes);
+  SmallVector<uint64_t, 3> Ops;
+  if (OffsetInBytes.getBoolValue())
+    Ops = {dwarf::DW_OP_plus_uconst, OffsetInBytes.getZExtValue()};
+  *Expression = DIExpression::prependOpcodes(
+      *Expression, Ops, /*StackValue=*/false, /*EntryValue=*/false);
+  *Expression = DIExpression::append(*Expression, {dwarf::DW_OP_deref});
+  return End;
+}
+
+/// A whole (unfragmented) source variable.
+using DebugAggregate = std::pair<const DILocalVariable *, const DILocation *>;
+static DebugAggregate getAggregate(const DbgVariableIntrinsic *DII) {
+  return DebugAggregate(DII->getVariable(), DII->getDebugLoc().getInlinedAt());
+}
+
+/// AssignmentTrackingLowering encapsulates a dataflow analysis over a function
+/// that interprets assignment tracking debug info metadata and stores in IR to
+/// create a map of variable locations.
+class AssignmentTrackingLowering {
+public:
+  /// The kind of location in use for a variable, where Mem is the stack home,
+  /// Val is an SSA value or const, and None means that there is not one single
+  /// kind (either because there are multiple or because there is none; it may
+  /// prove useful to split this into two values in the future).
+  ///
+  /// LocKind is a join-semilattice with the partial order:
+  /// None > Mem, Val
+  ///
+  /// i.e.
+  /// join(Mem, Val)  = None
+  /// join(None, Mem) = Mem
+  /// join(None, Val) = Val
+  ///
+  /// Note: the order is not `None > Val > Mem` because we're using DIAssignID
+  /// to name assignments and are not tracking the actual stored values.
+  /// Therefore currently there's no way to ensure that Mem values and Val
+  /// values are the same. This could be a future extension, though I'm not
+  /// sure that many additional locations would be recovered that way in
+  /// practice as the likelihood of this sitation arising naturally seems
+  /// incredibly low.
+  enum class LocKind { Mem, Val, None };
+
+  /// An abstraction of the assignment of a value to a variable or memory
+  /// location.
+  ///
+  /// An Assignment is Known or NoneOrPhi. A Known Assignment means we have a
+  /// DIAssignID ptr that represents it. UnknownOrPhi means that we don't (or
+  /// can't) know the ID of the last assignment that took place.
+  ///
+  /// The Status of the Assignment (Known or NoneOrPhi) is another
+  /// join-semilattice. The partial order is:
+  /// NoneOrPhi > Known {id_0, id_1, ...id_N}
+  ///
+  /// i.e. for all values x and y where x != y:
+  /// join(x, x) = x
+  /// join(x, y) = NoneOrPhi
+  struct Assignment {
+    enum S { Known, NoneOrPhi } Status;
+    DIAssignID *ID;
+    /// The dbg.assign that marks this dbg-def. Mem-defs don't use this field.
+    /// This is used to lookup the value + expression in the debug program if
+    /// the stack slot gets assigned a value earlier than expected. Because
+    /// we're only tracking the one dbg.assign, we can't capture debug PHIs.
+    /// It's unlikely that we're losing out on much coverage by avoiding that
+    /// extra work.
+    DbgAssignIntrinsic *Source;
+
+    bool operator==(const Assignment &Other) const {
+      // Don't include Source in the equality check. Assignments are
+      // defined by their ID, not debug intrinsic(s).
+      return std::tie(Status, ID) == std::tie(Other.Status, Other.ID);
+    }
+    void dump(raw_ostream &OS) {
+      static const char *LUT[] = {"Known", "NoneOrPhi"};
+      OS << LUT[Status] << "(id=";
+      if (ID)
+        OS << ID;
+      else
+        OS << "null";
+      OS << ", s=";
+      if (Source)
+        OS << *Source;
+      else
+        OS << "null";
+      OS << ")";
+    }
+    bool operator!=(const Assignment &Other) const { return !(*this == Other); }
+
+    static Assignment make(DIAssignID *ID, DbgAssignIntrinsic *Source) {
+      return Assignment(Known, ID, Source);
+    }
+    static Assignment makeFromMemDef(DIAssignID *ID) {
+      return Assignment(Known, ID, nullptr);
+    }
+    static Assignment makeNoneOrPhi() {
+      return Assignment(NoneOrPhi, nullptr, nullptr);
+    }
+    // Again, need a Top value?
+    Assignment()
+        : Status(NoneOrPhi), ID(nullptr), Source(nullptr) {
+    } // Can we delete this?
+    Assignment(S Status, DIAssignID *Value, DbgAssignIntrinsic *Source)
+        : Status(Status), ID(Value), Source(Source) {
+      // If the Status is Kown then we expect there to be a Value.
+      assert(Status != Known || Value != nullptr);
+    }
+  };
+
+  using AssignmentMap = DenseMap<VariableID, Assignment>;
+  using LocMap = DenseMap<VariableID, LocKind>;
+  using OverlapMap = DenseMap<VariableID, SmallVector<VariableID, 4>>;
+
+private:
+  /// Map a variable to the set of variables that it fully contains.
+  OverlapMap VarContains;
+
+  // Machinery to defer inserting dbg.values.
+  using InsertMap = MapVector<Instruction *, MapVector<VariableID, VarLocInfo>>;
+  InsertMap InsertBeforeMap;
+  void emitDbgValue(LocKind Kind, const DbgVariableIntrinsic *Source,
+                    Instruction *After);
+
+  static bool equ(const AssignmentMap &A, const AssignmentMap &B) {
+    if (A.size() != B.size())
+      return false;
+    for (const auto &Pair : A) {
+      VariableID Var = Pair.first;
+      const Assignment &AV = Pair.second;
+      auto R = B.find(Var);
+      // Check if this entry exists in B, otherwise ret false.
+      if (R == B.end())
+        return false;
+      // Check that the assignment value is the same.
+      if (AV != R->second)
+        return false;
+    }
+    return true;
+  }
+
+  /// Represents the stack and debug assignments in a block. Used to describe
+  /// the live-in and live-out values for blocks, as well as the "current"
+  /// value as we process each instruction in a block.
+  struct BlockInfo {
+    /// Location kind for each variable.
+    /// NOTE: LiveLoc is not derivable from StackHomeValue and DebugValue
+    /// values because the model is simplistic, representing PHIs and unkown
+    /// locations with the same value (UnknownOrPhi). The elements of a PHI of
+    /// assignments in StackHomeValue isn't useful information as a debug
+    /// intrinsic only has one DIAssignID and indeed a PHI in memory doesn't
+    /// invalidate the memory location. So a PHI of assignments doesn't cause
+    /// the LocKind to become None (Mem or Val is preserved) but it will save
+    /// the assignment as UnkownOrPHI in the AssignmentMap maps. This means
+    /// that we can't deduce the LocKind of a variable by just looking at the
+    /// two maps.
+    LocMap LiveLoc;
+    AssignmentMap StackHomeValue;
+    AssignmentMap DebugValue;
+
+    /// Compare every element in each map to determine structural equality
+    /// (slow).
+    bool operator==(const BlockInfo &Other) const {
+      return LiveLoc == Other.LiveLoc &&
+             equ(StackHomeValue, Other.StackHomeValue) &&
+             equ(DebugValue, Other.DebugValue);
+    }
+    bool operator!=(const BlockInfo &Other) const { return !(*this == Other); }
+    bool isValid() {
+      return LiveLoc.size() == DebugValue.size() &&
+             LiveLoc.size() == StackHomeValue.size();
+    }
+  };
+
+  Function &Fn;
+  const DataLayout &Layout;
+  const DenseSet<DebugAggregate> *VarsWithStackSlot;
+  FunctionVarLocsBuilder *FnVarLocs;
+  DenseMap<const BasicBlock *, BlockInfo> LiveIn;
+  DenseMap<const BasicBlock *, BlockInfo> LiveOut;
+
+  /// Helper for process methods to track variables touched each frame.
+  DenseSet<VariableID> VarsTouchedThisFrame;
+
+  /// The set of variables that sometimes are not located in their stack home.
+  DenseSet<DebugAggregate> NotAlwaysStackHomed;
+
+  VariableID getVariableID(DebugVariable Var) {
+    return static_cast<VariableID>(FnVarLocs->insertVariable(Var));
+  }
+
+  /// Join the LiveOut values of preds that are contained in \p Visited into
+  /// LiveIn[BB]. Return True if LiveIn[BB] has changed as a result. LiveIn[BB]
+  /// values monotonically increase. See the @link joinMethods join methods
+  /// @endlink documentation for more info.
+  bool join(const BasicBlock &BB, const SmallPtrSet<BasicBlock *, 16> &Visited);
+  ///@name joinMethods
+  /// Functions that implement `join` (the least upper bound) for the
+  /// join-semilattice types used in the dataflow. There is an explicit bottom
+  /// value (⊥) for some types and and explicit top value (⊤) for all types.
+  /// By definition:
+  ///
+  ///     Join(A, B) >= A && Join(A, B) >= B
+  ///     Join(A, ⊥) = A
+  ///     Join(A, ⊤) = ⊤
+  ///
+  /// These invariants are important for monotonicity.
+  ///
+  /// For the map-type functions, all unmapped keys are assumed to be
+  /// associated with a top value (⊤).
+  ///@{
+  static LocKind joinKind(LocKind A, LocKind B);
+  static LocMap joinLocMap(const LocMap &A, const LocMap &B);
+  static Assignment joinAssignment(const Assignment &A, const Assignment &B);
+  static AssignmentMap joinAssignmentMap(const AssignmentMap &A,
+                                         const AssignmentMap &B);
+  static BlockInfo joinBlockInfo(const BlockInfo &A, const BlockInfo &B);
+  ///@}
+
+  /// Process the instructions in \p BB updating \p LiveSet along the way. \p
+  /// LiveSet must be initialized with the current live-in locations before
+  /// calling this.
+  void process(BasicBlock &BB, BlockInfo *LiveSet);
+  ///@name processMethods
+  /// Methods to process instructions in order to update the LiveSet (current
+  /// location information).
+  ///@{
+  void processNonDbgInstruction(Instruction &I, BlockInfo *LiveSet);
+  void processDbgInstruction(Instruction &I, BlockInfo *LiveSet);
+  /// Update \p LiveSet after encountering an instruciton with a DIAssignID
+  /// attachment, \p I.
+  void processTaggedInstruction(Instruction &I, BlockInfo *LiveSet);
+  /// Update \p LiveSet after encountering an instruciton without a DIAssignID
+  /// attachment, \p I.
+  void processUntaggedInstruction(Instruction &I, BlockInfo *LiveSet);
+  void processDbgAssign(DbgAssignIntrinsic &DAI, BlockInfo *LiveSet);
+  void processDbgValue(DbgValueInst &DVI, BlockInfo *LiveSet);
+  /// Add an assignment to memory for the variable /p Var.
+  void addMemDef(BlockInfo *LiveSet, VariableID Var, Assignment AV);
+  /// Add an assignment to the variable /p Var.
+  void addDbgDef(BlockInfo *LiveSet, VariableID Var, Assignment AV);
+  ///@}
+
+  /// Set the LocKind for \p Var.
+  void setLocKind(BlockInfo *LiveSet, VariableID Var, LocKind K);
+  /// Get the live LocKind for a \p Var. Requires addMemDef or addDbgDef to
+  /// have been called for \p Var first.
+  LocKind getLocKind(BlockInfo *LiveSet, VariableID Var);
+
+  // Emit info for variables that are fully promoted.
+  bool emitPromotedVarLocs(FunctionVarLocsBuilder *FnVarLocs);
+
+public:
+  AssignmentTrackingLowering(Function &Fn, const DataLayout &Layout,
+                             const DenseSet<DebugAggregate> *VarsWithStackSlot)
+      : Fn(Fn), Layout(Layout), VarsWithStackSlot(VarsWithStackSlot) {}
+  /// Run the analysis, adding variable location info to \p FnVarLocs. Returns
+  /// true if any variable locations have been added to FnVarLocs.
+  bool run(FunctionVarLocsBuilder *FnVarLocs);
+};
+
+void AssignmentTrackingLowering::setLocKind(BlockInfo *LiveSet, VariableID Var,
+                                            LocKind K) {
+  auto SetKind = [this](BlockInfo *LiveSet, VariableID Var, LocKind K) {
+    VarsTouchedThisFrame.insert(Var);
+    LiveSet->LiveLoc[Var] = K;
+  };
+  SetKind(LiveSet, Var, K);
+
+  // Update the LocKind for all fragments contained within Var.
+  for (VariableID Frag : VarContains[Var])
+    SetKind(LiveSet, Frag, K);
+}
+
+AssignmentTrackingLowering::LocKind
+AssignmentTrackingLowering::getLocKind(BlockInfo *LiveSet, VariableID Var) {
+  auto Pair = LiveSet->LiveLoc.find(Var);
+  assert(Pair != LiveSet->LiveLoc.end());
+  return Pair->second;
+}
+
+void AssignmentTrackingLowering::addMemDef(BlockInfo *LiveSet, VariableID Var,
+                                           Assignment AV) {
+  auto AddDef = [](BlockInfo *LiveSet, VariableID Var, Assignment AV) {
+    LiveSet->StackHomeValue[Var] = AV;
+    // Add (Var -> ⊤) to DebugValue if Var isn't in DebugValue yet.
+    LiveSet->DebugValue.insert({Var, Assignment::makeNoneOrPhi()});
+    // Add (Var -> ⊤) to LiveLocs if Var isn't in LiveLocs yet.
+    LiveSet->LiveLoc.insert({Var, LocKind::None});
+  };
+  AddDef(LiveSet, Var, AV);
+
+  // Use this assigment for all fragments contained within Var, but do not
+  // provide a Source because we cannot convert Var's value to a value for the
+  // fragment.
+  Assignment FragAV = AV;
+  FragAV.Source = nullptr;
+  for (VariableID Frag : VarContains[Var])
+    AddDef(LiveSet, Frag, FragAV);
+}
+
+void AssignmentTrackingLowering::addDbgDef(BlockInfo *LiveSet, VariableID Var,
+                                           Assignment AV) {
+  auto AddDef = [](BlockInfo *LiveSet, VariableID Var, Assignment AV) {
+    LiveSet->DebugValue[Var] = AV;
+    // Set StackHome[Var] = ⊤ if Var isn't in StackHome yet.
+    LiveSet->StackHomeValue.insert({Var, Assignment::makeNoneOrPhi()});
+    // Add (Var -> ⊤) to LiveLocs if Var isn't in LiveLocs yet.
+    LiveSet->LiveLoc.insert({Var, LocKind::None});
+  };
+  AddDef(LiveSet, Var, AV);
+
+  // Use this assigment for all fragments contained within Var, but do not
+  // provide a Source because we cannot convert Var's value to a value for the
+  // fragment.
+  Assignment FragAV = AV;
+  FragAV.Source = nullptr;
+  for (VariableID Frag : VarContains[Var])
+    AddDef(LiveSet, Frag, FragAV);
+}
+
+static DIAssignID *getIDFromInst(const Instruction &I) {
+  return cast<DIAssignID>(I.getMetadata(LLVMContext::MD_DIAssignID));
+}
+
+static DIAssignID *getIDFromMarker(const DbgAssignIntrinsic &DAI) {
+  return cast<DIAssignID>(DAI.getAssignID());
+}
+
+/// Return true if Var exists in A and B and has the same value.
+static bool hasVarWithValue(VariableID Var,
+                            AssignmentTrackingLowering::Assignment AV,
+                            AssignmentTrackingLowering::AssignmentMap &M) {
+  auto R = M.find(Var);
+  if (R == M.end())
+    return false;
+  return R->second == AV;
+}
+
+const char *locStr(AssignmentTrackingLowering::LocKind Loc) {
+  using LocKind = AssignmentTrackingLowering::LocKind;
+  switch (Loc) {
+  case LocKind::Val:
+    return "Val";
+  case LocKind::Mem:
+    return "Mem";
+  case LocKind::None:
+    return "None";
+  };
+  llvm_unreachable("unknown LocKind");
+}
+
+void AssignmentTrackingLowering::emitDbgValue(
+    AssignmentTrackingLowering::LocKind Kind,
+    const DbgVariableIntrinsic *Source, Instruction *After) {
+
+  DILocation *DL = Source->getDebugLoc();
+  auto Emit = [this, Source, After, DL](Value *Val, DIExpression *Expr) {
+    assert(Expr);
+    // It's possible that getVariableLocationOp(0) is null. Occurs in
+    // llvm/test/DebugInfo/Generic/2010-05-03-OriginDIE.ll Treat it as undef.
+    if (!Val)
+      Val = UndefValue::get(Type::getInt1Ty(Source->getContext()));
+
+    // Find a suitable insert point.
+    Instruction *InsertBefore = After->getNextNode();
+    assert(InsertBefore && "Shouldn't be inserting after a terminator");
+
+    VariableID Var = getVariableID(DebugVariable(Source));
+    VarLocInfo VarLoc;
+    VarLoc.VariableID = static_cast<VariableID>(Var);
+    VarLoc.Expr = Expr;
+    VarLoc.V = Val;
+    VarLoc.DL = DL;
+    // Insert it into the map for later.
+    InsertBeforeMap[InsertBefore][Var] = VarLoc;
+  };
+
+  // NOTE: This block can mutate Kind.
+  if (Kind == LocKind::Mem) {
+    const auto *DAI = cast<DbgAssignIntrinsic>(Source);
+    // Check the address hasn't been dropped (e.g. the debug uses may not have
+    // been replaced before deleting a Value).
+    if (Value *Val = DAI->getAddress()) {
+      DIExpression *Expr = DAI->getAddressExpression();
+      assert(Expr->getFragmentInfo().hasValue() == false &&
+             "fragment info should be stored in value-expression only");
+      // Copy the fragment info over from the value-expression to the new
+      // DIExpression.
+      if (auto OptFragInfo = Source->getExpression()->getFragmentInfo()) {
+        auto FragInfo = OptFragInfo.getValue();
+        Expr = *DIExpression::createFragmentExpression(
+            Expr, FragInfo.OffsetInBits, FragInfo.SizeInBits);
+      }
+      // The address-expression has an implicit deref, add it now.
+      Val = walkToAllocaAndPrependOffsetDeref(Layout, Val, &Expr);
+      Emit(Val, Expr);
+      return;
+    } else {
+      // The address isn't valid so treat this as a non-memory def.
+      Kind = LocKind::Val;
+    }
+  }
+
+  if (Kind == LocKind::Val) {
+    /// Get the value component, converting to Undef if it is variadic.
+    Value *Val =
+        Source->hasArgList()
+            ? UndefValue::get(Source->getVariableLocationOp(0)->getType())
+            : Source->getVariableLocationOp(0);
+    Emit(Val, Source->getExpression());
+    return;
+  }
+
+  if (Kind == LocKind::None) {
+    Value *Val = UndefValue::get(Source->getVariableLocationOp(0)->getType());
+    Emit(Val, Source->getExpression());
+    return;
+  }
+}
+
+void AssignmentTrackingLowering::processNonDbgInstruction(
+    Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {
+  if (I.hasMetadata(LLVMContext::MD_DIAssignID))
+    processTaggedInstruction(I, LiveSet);
+  else
+    processUntaggedInstruction(I, LiveSet);
+}
+
+void AssignmentTrackingLowering::processUntaggedInstruction(
+    Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {
+  assert(!I.hasMetadata(LLVMContext::MD_DIAssignID));
+
+  auto OptInfo = [&I, this]() {
+    // Don't bother checking if this is an AllocaInst. We know this
+    // instruction has no tag which means there are no variables associated
+    // with it.
+    if (auto *SI = dyn_cast<StoreInst>(&I))
+      return at::getAssignmentInfo(Layout, SI);
+    if (auto *MI = dyn_cast<MemIntrinsic>(&I))
+      return at::getAssignmentInfo(Layout, MI);
+    // Alloca or non-store-like inst.
+    return (Optional<at::AssignmentInfo>)None;
+  }();
+  if (!OptInfo)
+    return;
+  at::AssignmentInfo Info = *OptInfo;
+  if (!Info.Base)
+    return; // Couldn't walk back to alloca.
+  auto Linked = at::getAssignmentMarkers(Info.Base);
+  if (Linked.empty())
+    return; // No variable information around.
+
+  LLVM_DEBUG(dbgs() << "processUntaggedInstruction on UNTAGGED INST " << I
+                    << "\n");
+
+  // Find markers linked to this alloca.
+  for (DbgAssignIntrinsic *DAI : Linked) {
+    if (DAI->getExpression()->getNumElements() != 0)
+      continue; // Don't bother with tricky situations.
+
+    // Something has gone wrong if VarsWithStackSlot doesn't contain a variable
+    // that is linked to an alloca.
+    assert(VarsWithStackSlot->count(getAggregate(DAI)));
+
+    DIExpression::FragmentInfo F;
+    F.OffsetInBits = Info.OffsetInBits;
+    F.SizeInBits = Info.SizeInBits;
+    VariableID Var = getVariableID(DebugVariable(
+        DAI->getVariable(), F, DAI->getDebugLoc().getInlinedAt()));
+
+    // Use an assignment ID that nothing can match against (the instruction has
+    // no DIAssignID) - this instruction is treate as both a dbg and mem def (of
+    // the same value), meaning the memory location is used.
+    addMemDef(LiveSet, Var, Assignment::makeNoneOrPhi());
+    addDbgDef(LiveSet, Var, Assignment::makeNoneOrPhi());
+    setLocKind(LiveSet, Var, LocKind::Mem);
+    LLVM_DEBUG(dbgs() << "  setting Stack LocKind to: " << locStr(LocKind::Mem)
+                      << "\n");
+    // Build the dbg.value to insert.
+    //
+    // DIExpression: Add fragment and offset.
+    DIExpression *DIE = DIExpression::get(I.getContext(), None);
+    if (!Info.StoreToWholeAlloca) {
+      auto R = DIExpression::createFragmentExpression(DIE, Info.OffsetInBits,
+                                                      Info.SizeInBits);
+      if (!R)
+        assert(false && "unexpected createFragmentExpression failure");
+      DIE = R.getValue();
+    }
+    SmallVector<uint64_t, 3> Ops;
+    if (Info.OffsetInBits)
+      Ops = {dwarf::DW_OP_plus_uconst, Info.OffsetInBits / 8};
+    Ops.push_back(dwarf::DW_OP_deref);
+    DIE = DIExpression::prependOpcodes(DIE, Ops, /*StackValue=*/false,
+                                       /*EntryValue=*/false);
+
+    // Find a suitable insert point.
+    Instruction *InsertBefore = I.getNextNode();
+    assert(InsertBefore && "Shouldn't be inserting after a terminator");
+
+    VarLocInfo VarLoc;
+    VarLoc.VariableID = static_cast<VariableID>(Var);
+    VarLoc.Expr = DIE;
+    VarLoc.V = const_cast<AllocaInst *>(Info.Base);
+    VarLoc.DL = DAI->getDebugLoc();
+    // 3. Insert it into the map for later.
+    InsertBeforeMap[InsertBefore][Var] = VarLoc;
+  }
+}
+
+void AssignmentTrackingLowering::processTaggedInstruction(
+    Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {
+  auto Linked = at::getAssignmentMarkers(&I);
+  // No dbg.assign intrinsics linked.
+  // FIXME: All vars that have a stack slot this store modifies that don't have
+  // a dbg.assign linked to it should probably treat this like an untagged
+  // store.
+  if (Linked.empty())
+    return;
+
+  LLVM_DEBUG(dbgs() << "processTaggedInstruction on " << I << "\n");
+  for (DbgAssignIntrinsic *DAI : Linked) {
+    VariableID Var = getVariableID(DebugVariable(DAI));
+    // Something has gone wrong if VarsWithStackSlot doesn't contain a variable
+    // that is linked to a store.
+    assert(VarsWithStackSlot->count(getAggregate(DAI)));
+
+    Assignment AV = Assignment::makeFromMemDef(getIDFromInst(I));
+    addMemDef(LiveSet, Var, AV);
+
+    LLVM_DEBUG(dbgs() << "   linked to " << *DAI << "\n");
+    LLVM_DEBUG(dbgs() << "   LiveLoc " << locStr(getLocKind(LiveSet, Var))
+                      << " -> ");
+
+    // The last assignment to the stack is now AV. Check if the last debug
+    // assignment has a matching Assignment.
+    if (hasVarWithValue(Var, AV, LiveSet->DebugValue)) {
+      // The StackHomeValue and DebugValue for this variable match so we can
+      // emit a stack home location here.
+      LLVM_DEBUG(dbgs() << "Mem, Stack matches Debug program\n";);
+      LLVM_DEBUG(dbgs() << "   Stack val: "; AV.dump(dbgs()); dbgs() << "\n");
+      LLVM_DEBUG(dbgs() << "   Debug val: ";
+                 LiveSet->DebugValue[Var].dump(dbgs()); dbgs() << "\n");
+      setLocKind(LiveSet, Var, LocKind::Mem);
+      emitDbgValue(LocKind::Mem, DAI, &I);
+    } else {
+      // The StackHomeValue and DebugValue for this variable do not match. I.e.
+      // The value currently stored in the stack is not what we'd expect to
+      // see, so we cannot use emit a stack home location here. Now we will
+      // look at the live LocKind for the variable and determine an appropriate
+      // dbg.value to emit.
+      LocKind PrevLoc = getLocKind(LiveSet, Var);
+      switch (PrevLoc) {
+      case LocKind::Val: {
+        // The value memory in memory has changed but we're not currently using
+        // the memory location. Do nothing.
+        LLVM_DEBUG(dbgs() << "Val, (unchanged)\n";);
+        setLocKind(LiveSet, Var, LocKind::Val);
+      } break;
+      case LocKind::Mem: {
+        // There's been an assignment to memory that we were using as a
+        // location for this variable, and the Assignment doesn't match what
+        // we'd expect to see in memory.
+        if (LiveSet->DebugValue[Var].Status == Assignment::NoneOrPhi) {
+          // We need to terminate any previously open location now.
+          LLVM_DEBUG(dbgs() << "None, No Debug value available\n";);
+          setLocKind(LiveSet, Var, LocKind::None);
+          emitDbgValue(LocKind::None, DAI, &I);
+        } else {
+          // The previous DebugValue Value can be used here.
+          LLVM_DEBUG(dbgs() << "Val, Debug value is Known\n";);
+          setLocKind(LiveSet, Var, LocKind::Val);
+          Assignment PrevAV = LiveSet->DebugValue.lookup(Var);
+          if (PrevAV.Source) {
+            emitDbgValue(LocKind::Val, PrevAV.Source, &I);
+          } else {
+            // PrevAV.Source is nullptr so we must emit undef here.
+            emitDbgValue(LocKind::None, DAI, &I);
+          }
+        }
+      } break;
+      case LocKind::None: {
+        // There's been an assignment to memory and we currently are
+        // not tracking a location for the variable. Do not emit anything.
+        LLVM_DEBUG(dbgs() << "None, (unchanged)\n";);
+        setLocKind(LiveSet, Var, LocKind::None);
+      } break;
+      }
+    }
+  }
+}
+
+void AssignmentTrackingLowering::processDbgAssign(DbgAssignIntrinsic &DAI,
+                                                  BlockInfo *LiveSet) {
+  // Only bother tracking variables that are at some point stack homed. Other
+  // variables can be dealt with trivially later.
+  if (!VarsWithStackSlot->count(getAggregate(&DAI)))
+    return;
+
+  VariableID Var = getVariableID(DebugVariable(&DAI));
+  Assignment AV = Assignment::make(getIDFromMarker(DAI), &DAI);
+  addDbgDef(LiveSet, Var, AV);
+
+  LLVM_DEBUG(dbgs() << "processDbgAssign on " << DAI << "\n";);
+  LLVM_DEBUG(dbgs() << "   LiveLoc " << locStr(getLocKind(LiveSet, Var))
+                    << " -> ");
+
+  // Check if the DebugValue and StackHomeValue both hold the same
+  // Assignment.
+  if (hasVarWithValue(Var, AV, LiveSet->StackHomeValue)) {
+    // They match. We can use the stack home because the debug intrinsics state
+    // that an assignment happened here, and we know that specific assignment
+    // was the last one to take place in memory for this variable.
+    if (isa<UndefValue>(DAI.getAddress())) {
+      // Address may be undef to indicate that although the store does take
+      // place, this part of the original store has been elided.
+      LLVM_DEBUG(
+          dbgs() << "Val, Stack matches Debug program but address is undef\n";);
+      setLocKind(LiveSet, Var, LocKind::Val);
+    } else {
+      LLVM_DEBUG(dbgs() << "Mem, Stack matches Debug program\n";);
+      setLocKind(LiveSet, Var, LocKind::Mem);
+    };
+    emitDbgValue(LocKind::Mem, &DAI, &DAI);
+  } else {
+    // The last assignment to the memory location isn't the one that we want to
+    // show to the user so emit a dbg.value(Value). Value may be undef.
+    LLVM_DEBUG(dbgs() << "Val, Stack contents is unknown\n";);
+    setLocKind(LiveSet, Var, LocKind::Val);
+    emitDbgValue(LocKind::Val, &DAI, &DAI);
+  }
+}
+void AssignmentTrackingLowering::processDbgValue(DbgValueInst &DVI,
+                                                 BlockInfo *LiveSet) {
+  // Only other tracking variables that are at some point stack homed.
+  // Other variables can be dealt with trivally later.
+  if (!VarsWithStackSlot->count(getAggregate(&DVI)))
+    return;
+
+  VariableID Var = getVariableID(DebugVariable(&DVI));
+  // We have no ID to create an Assignment with so we must mark this
+  // assignment as NoneOrPhi. Note that the dbg.value still exists, we just
+  // cannot determine the assignment responsible for setting this value.
+  Assignment AV = Assignment::makeNoneOrPhi();
+  addDbgDef(LiveSet, Var, AV);
+
+  LLVM_DEBUG(dbgs() << "processDbgValue on " << DVI << "\n";);
+  LLVM_DEBUG(dbgs() << "   LiveLoc " << locStr(getLocKind(LiveSet, Var))
+                    << " -> Val, dbg.value override");
+
+  setLocKind(LiveSet, Var, LocKind::Val);
+  emitDbgValue(LocKind::Val, &DVI, &DVI);
+}
+
+void AssignmentTrackingLowering::processDbgInstruction(
+    Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {
+  assert(!isa<DbgAddrIntrinsic>(&I) && "unexpected dbg.addr");
+  if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(&I))
+    processDbgAssign(*DAI, LiveSet);
+  else if (auto *DVI = dyn_cast<DbgValueInst>(&I))
+    processDbgValue(*DVI, LiveSet);
+}
+
+void AssignmentTrackingLowering::process(BasicBlock &BB, BlockInfo *LiveSet) {
+  for (auto II = BB.begin(), EI = BB.end(); II != EI;) {
+    assert(VarsTouchedThisFrame.empty());
+    // Process the instructions in "frames". A "frame" includes a single
+    // non-debug instruction followed any debug instructions before the
+    // next non-debug instruction.
+    if (!isa<DbgInfoIntrinsic>(&*II)) {
+      processNonDbgInstruction(*II, LiveSet);
+      assert(LiveSet->isValid());
+      ++II;
+    }
+    while (II != EI) {
+      if (!isa<DbgInfoIntrinsic>(&*II))
+        break;
+      processDbgInstruction(*II, LiveSet);
+      assert(LiveSet->isValid());
+      ++II;
+    }
+
+    // We've processed everything in the "frame". Now determine which variables
+    // cannot be represented by a dbg.declare.
+    for (auto Var : VarsTouchedThisFrame) {
+      LocKind Loc = getLocKind(LiveSet, Var);
+      // If a variable's LocKind is anything other than LocKind::Mem then we
+      // must note that it cannot be represented with a dbg.declare.
+      // Note that this check is enough without having to check the result of
+      // joins() because for join to produce anything other than Mem after
+      // we've already seen a Mem we'd be joining None or Val with Mem. In that
+      // case, we've already hit this codepath when we set the LocKind to Val
+      // or None in that block.
+      if (Loc != LocKind::Mem) {
+        DebugVariable DbgVar = FnVarLocs->getVariable(Var);
+        DebugAggregate Aggr{DbgVar.getVariable(), DbgVar.getInlinedAt()};
+        NotAlwaysStackHomed.insert(Aggr);
+      }
+    }
+    VarsTouchedThisFrame.clear();
+  }
+}
+
+AssignmentTrackingLowering::LocKind AssignmentTrackingLowering::joinKind(LocKind A, LocKind B) {
+  // Partial order:
+  // None > Mem, Val
+  return A == B ? A : LocKind::None;
+}
+
+AssignmentTrackingLowering::LocMap
+AssignmentTrackingLowering::joinLocMap(const LocMap &A, const LocMap &B) {
+  // Join A and B.
+  //
+  // U = join(a, b) for a in A, b in B where Var(a) == Var(b)
+  // D = join(x, ⊤) for x where Var(x) is in A xor B
+  // Join = U ∪ D
+  //
+  // This is achieved by performing a join on elements from A and B with
+  // variables common to both A and B (join elements indexed by var intersect),
+  // then adding LocKind::None elements for vars in A xor B. The latter part is
+  // equivalent to performing join on elements with variables in A xor B with
+  // LocKind::None (⊤) since join(x, ⊤) = ⊤.
+  LocMap Join;
+  SmallVector<VariableID, 16> SymmetricDifference;
+  // Insert the join of the elements with common vars into Join. Add the
+  // remaining elements to into SymmetricDifference.
+  for (auto Pair : A) {
+    VariableID Var = Pair.first;
+    const LocKind Loc = Pair.second;
+    // If this Var doesn't exist in B then add it to the symmetric difference
+    // set.
+    auto R = B.find(Var);
+    if (R == B.end()) {
+      SymmetricDifference.push_back(Var);
+      continue;
+    }
+    // There is an entry for Var in both, join it.
+    Join[Var] = joinKind(Loc, R->second);
+  }
+  unsigned IntersectSize = Join.size();
+  (void)IntersectSize;
+
+  // Add the elements in B with variables that are not in A into
+  // SymmetricDifference.
+  for (auto Pair : B) {
+    VariableID Var = Pair.first;
+    if (A.count(Var) == 0)
+      SymmetricDifference.push_back(Var);
+  }
+
+  // Add SymmetricDifference elements to Join and return the result.
+  for (auto Var : SymmetricDifference)
+    Join.insert({Var, LocKind::None});
+
+  assert(Join.size() == (IntersectSize + SymmetricDifference.size()));
+  assert(Join.size() >= A.size() && Join.size() >= B.size());
+  return Join;
+}
+
+AssignmentTrackingLowering::Assignment
+AssignmentTrackingLowering::joinAssignment(const Assignment &A, const Assignment &B) {
+  // Partial order:
+  // NoneOrPhi(null, null) > Known(v, ?s)
+
+  // If either are NoneOrPhi the join is NoneOrPhi.
+  // If either value is different then the result is
+  // NoneOrPhi (joining two values is a Phi).
+  if (A.Status != B.Status || A.ID != B.ID)
+    return Assignment::makeNoneOrPhi();
+
+  if (A.Status == Assignment::NoneOrPhi)
+    return Assignment::makeNoneOrPhi();
+
+  // The source may differ in this situation:
+  // Pred.1:
+  //   dbg.assign i32 0, ..., !1, ...
+  // Pred.2:
+  //   dbg.assign i32 1, ..., !1, ...
+  // Here the same assignment (!1) was performed in both preds in the source,
+  // but we can't use either one unless they are identical (e.g. .we don't
+  // want to arbitrarily pick between constant values).
+  auto *Source = [&]() -> DbgAssignIntrinsic * {
+    if (A.Source == B.Source)
+      return A.Source;
+    if (A.Source == nullptr || B.Source == nullptr)
+      return nullptr;
+    if (A.Source->isIdenticalTo(B.Source))
+      return A.Source;
+    return nullptr;
+  }();
+  assert(A.Status == B.Status && A.Status == Assignment::Known);
+  assert(A.ID == B.ID);
+  return Assignment::make(A.ID, Source);
+}
+
+AssignmentTrackingLowering::AssignmentMap
+AssignmentTrackingLowering::joinAssignmentMap(const AssignmentMap &A,
+                                              const AssignmentMap &B) {
+  // Join A and B.
+  //
+  // U = join(a, b) for a in A, b in B where Var(a) == Var(b)
+  // D = join(x, ⊤) for x where Var(x) is in A xor B
+  // Join = U ∪ D
+  //
+  // This is achieved by performing a join on elements from A and B with
+  // variables common to both A and B (join elements indexed by var intersect),
+  // then adding LocKind::None elements for vars in A xor B. The latter part is
+  // equivalent to performing join on elements with variables in A xor B with
+  // Status::NoneOrPhi (⊤) since join(x, ⊤) = ⊤.
+  AssignmentMap Join;
+  SmallVector<VariableID, 16> SymmetricDifference;
+  // Insert the join of the elements with common vars into Join. Add the
+  // remaining elements to into SymmetricDifference.
+  for (const auto &Pair : A) {
+    VariableID Var = Pair.first;
+    const Assignment AV = Pair.second;
+    // If this Var doesn't exist in B then add it to the symmetric difference
+    // set.
+    auto R = B.find(Var);
+    if (R == B.end()) {
+      SymmetricDifference.push_back(Var);
+      continue;
+    }
+    // There is an entry for Var in both, join it.
+    Join[Var] = joinAssignment(AV, R->second);
+  }
+  unsigned IntersectSize = Join.size();
+  (void)IntersectSize;
+
+  // Add the elements in B with variables that are not in A into
+  // SymmetricDifference.
+  for (const auto &Pair : B) {
+    VariableID Var = Pair.first;
+    if (A.count(Var) == 0)
+      SymmetricDifference.push_back(Var);
+  }
+
+  // Add SymmetricDifference elements to Join and return the result.
+  for (auto Var : SymmetricDifference)
+    Join.insert({Var, Assignment::makeNoneOrPhi()});
+
+  assert(Join.size() == (IntersectSize + SymmetricDifference.size()));
+  assert(Join.size() >= A.size() && Join.size() >= B.size());
+  return Join;
+}
+
+AssignmentTrackingLowering::BlockInfo
+AssignmentTrackingLowering::joinBlockInfo(const BlockInfo &A, const BlockInfo &B) {
+  BlockInfo Join;
+  Join.LiveLoc = joinLocMap(A.LiveLoc, B.LiveLoc);
+  Join.StackHomeValue = joinAssignmentMap(A.StackHomeValue, B.StackHomeValue);
+  Join.DebugValue = joinAssignmentMap(A.DebugValue, B.DebugValue);
+  assert(Join.isValid());
+  return Join;
+}
+
+bool AssignmentTrackingLowering::join(
+    const BasicBlock &BB, const SmallPtrSet<BasicBlock *, 16> &Visited) {
+  BlockInfo BBLiveIn;
+  bool FirstJoin = true;
+  // LiveIn locs for BB is the join of the already-processed preds' LiveOut
+  // locs.
+  for (auto I = pred_begin(&BB), E = pred_end(&BB); I != E; I++) {
+    // Ignore backedges if we have not visited the predecessor yet. As the
+    // predecessor hasn't yet had locations propagated into it, most locations
+    // will not yet be valid, so treat them as all being uninitialized and
+    // potentially valid. If a location guessed to be correct here is
+    // invalidated later, we will remove it when we revisit this block.  This
+    // is essentially the same as initialising all LocKinds and Assignments to
+    // an implicit ⊥ value which is the identity value for the join operation.
+    const BasicBlock *Pred = *I;
+    if (!Visited.count(Pred))
+      continue;
+
+    auto PredLiveOut = LiveOut.find(Pred);
+    // Pred must have been processed already. See comment at start of this loop.
+    assert(PredLiveOut != LiveOut.end());
+
+    // Perform the join of BBLiveIn (current live-in info) and PrevLiveOut.
+    if (FirstJoin)
+      BBLiveIn = PredLiveOut->second;
+    else
+      BBLiveIn = joinBlockInfo(BBLiveIn, PredLiveOut->second);
+    FirstJoin = false;
+  }
+
+  auto CurrentLiveInEntry = LiveIn.find(&BB);
+  // Check if there isn't an entry, or there is but the LiveIn set has changed
+  // (expensive check).
+  if (CurrentLiveInEntry == LiveIn.end() ||
+      BBLiveIn != CurrentLiveInEntry->second) {
+    LiveIn[&BB] = std::move(BBLiveIn);
+    // A change has occured.
+    return true;
+  }
+  // No change.
+  return false;
+}
+
+/// Return true if A fully contains B.
+static bool fullyContains(DIExpression::FragmentInfo A,
+                          DIExpression::FragmentInfo B) {
+  auto ALeft = A.OffsetInBits;
+  auto BLeft = B.OffsetInBits;
+  if (BLeft < ALeft)
+    return false;
+
+  auto ARight = ALeft + A.SizeInBits;
+  auto BRight = BLeft + B.SizeInBits;
+  if (BRight > ARight)
+    return false;
+  return true;
+}
+
+/// Build a map of {Variable x: Variables y} where all variable fragments
+/// contained within the variable fragment x are in set y. This means that
+/// y does not contain all overlaps because partial overlaps are excluded.
+/// While we're iterating over the function, add single location defs for
+/// dbg.declares to \p FnVarLocs.
+static AssignmentTrackingLowering::OverlapMap
+buildOverlapMapAndRecordDeclares(Function &Fn,
+                                 FunctionVarLocsBuilder *FnVarLocs) {
+  DenseSet<DebugVariable> Seen;
+  DenseMap<DebugAggregate, SmallVector<DebugVariable, 8>> FragmentMap;
+  for (auto &BB : Fn) {
+    for (auto &I : BB) {
+      if (auto *DDI = dyn_cast<DbgDeclareInst>(&I)) {
+        FnVarLocs->addSingleLocVar(DebugVariable(DDI), DDI->getExpression(),
+                                   DDI->getDebugLoc(), DDI->getAddress());
+      } else if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {
+        DebugVariable DV = DebugVariable(DII);
+        DebugAggregate DA = {DV.getVariable(), DV.getInlinedAt()};
+        if (Seen.insert(DV).second)
+          FragmentMap[DA].push_back(DV);
+      }
+    }
+  }
+
+  // Sort the fragment map for each DebugAggregate in non-descending
+  // order of fragment size. Assert no entries are duplicates.
+  for (auto &Pair : FragmentMap) {
+    SmallVector<DebugVariable, 8> &Frags = Pair.second;
+    std::sort(
+        Frags.begin(), Frags.end(), [](DebugVariable Next, DebugVariable Elmt) {
+          assert(!(Elmt.getFragmentOrDefault() == Next.getFragmentOrDefault()));
+          return Elmt.getFragmentOrDefault().SizeInBits >
+                 Next.getFragmentOrDefault().SizeInBits;
+        });
+  }
+
+  // Build the map.
+  AssignmentTrackingLowering::OverlapMap Map;
+  for (auto Pair : FragmentMap) {
+    auto &Frags = Pair.second;
+    for (auto It = Frags.begin(), IEnd = Frags.end(); It != IEnd; ++It) {
+      DIExpression::FragmentInfo Frag = It->getFragmentOrDefault();
+      // Find the frags that this is contained within.
+      //
+      // Because Frags is sorted by size and none have the same offset and
+      // size, we know that this frag can only be contained by subsequent
+      // elements.
+      SmallVector<DebugVariable, 8>::iterator OtherIt = It;
+      ++OtherIt;
+      VariableID ThisVar = FnVarLocs->insertVariable(*It);
+      for (; OtherIt != IEnd; ++OtherIt) {
+        DIExpression::FragmentInfo OtherFrag = OtherIt->getFragmentOrDefault();
+        VariableID OtherVar = FnVarLocs->insertVariable(*OtherIt);
+        if (fullyContains(OtherFrag, Frag))
+          Map[OtherVar].push_back(ThisVar);
+      }
+    }
+  }
+
+  return Map;
+}
+
+bool AssignmentTrackingLowering::run(FunctionVarLocsBuilder *FnVarLocsBuilder) {
+  if (Fn.size() > MaxNumBlocks) {
+    LLVM_DEBUG(dbgs() << "[AT] Dropping var locs in: " << Fn.getName()
+                      << ": too many blocks (" << Fn.size() << ")\n");
+    at::deleteAll(&Fn);
+    return false;
+  }
+
+  FnVarLocs = FnVarLocsBuilder;
+
+  // The general structure here is inspired by VarLocBasedImp.cpp
+  // (LiveDebugValues).
+
+  // Build the variable fragment overlap map.
+  // Note that this pass doesn't handle partial overlaps correctly (FWIW
+  // neither does LiveDebugVariables) because that is difficult to do and
+  // appears to be rare occurance.
+  VarContains = buildOverlapMapAndRecordDeclares(Fn, FnVarLocs);
+
+  // Prepare for traversal.
+  ReversePostOrderTraversal<Function *> RPOT(&Fn);
+  std::priority_queue<unsigned int, std::vector<unsigned int>,
+                      std::greater<unsigned int>>
+      Worklist;
+  std::priority_queue<unsigned int, std::vector<unsigned int>,
+                      std::greater<unsigned int>>
+      Pending;
+  DenseMap<unsigned int, BasicBlock *> OrderToBB;
+  DenseMap<BasicBlock *, unsigned int> BBToOrder;
+  { // Init OrderToBB and BBToOrder.
+    unsigned int RPONumber = 0;
+    for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
+      OrderToBB[RPONumber] = *RI;
+      BBToOrder[*RI] = RPONumber;
+      Worklist.push(RPONumber);
+      ++RPONumber;
+    }
+    LiveIn.init(RPONumber);
+    LiveOut.init(RPONumber);
+  }
+
+  // Perform the traversal.
+  //
+  // This is a standard "union of predecessor outs" dataflow problem. To solve
+  // it, we perform join() and process() using the two worklist method until
+  // the LiveIn data for each block becomes unchanging. The "proof" that this
+  // terminates can be put together by looking at the comments around LocKind,
+  // Assignment, and the various join methods, which show that all the elements
+  // involved are made up of join-semilattices; LiveIn(n) can only
+  // monotonically increase in value throughout the dataflow.
+  //
+  SmallPtrSet<BasicBlock *, 16> Visited;
+  while (!Worklist.empty() || !Pending.empty()) {
+    // We track what is on the pending worklist to avoid inserting the same
+    // thing twice.
+    SmallPtrSet<BasicBlock *, 16> OnPending;
+    LLVM_DEBUG(dbgs() << "Processing Worklist\n");
+    while (!Worklist.empty()) {
+      BasicBlock *BB = OrderToBB[Worklist.top()];
+      LLVM_DEBUG(dbgs() << "\nPop BB " << BB->getName() << "\n");
+      Worklist.pop();
+      bool InChanged = join(*BB, Visited);
+      // Always consider LiveIn changed on the first visit.
+      InChanged |= Visited.insert(BB).second;
+      if (InChanged) {
+        LLVM_DEBUG(dbgs() << BB->getName() << " has new InLocs, process it\n");
+        // Mutate a copy of LiveIn while processing BB. After calling process
+        // LiveSet is the LiveOut set for BB.
+        BlockInfo LiveSet = LiveIn[BB];
+
+        // Process the instructions in the block.
+        process(*BB, &LiveSet);
+
+        // Relatively expensive check: has anything changed in LiveOut for BB?
+        if (LiveOut[BB] != LiveSet) {
+          LLVM_DEBUG(dbgs() << BB->getName()
+                            << " has new OutLocs, add succs to worklist: [ ");
+          LiveOut[BB] = std::move(LiveSet);
+          for (auto I = succ_begin(BB), E = succ_end(BB); I != E; I++) {
+            if (OnPending.insert(*I).second) {
+              LLVM_DEBUG(dbgs() << I->getName() << " ");
+              Pending.push(BBToOrder[*I]);
+            }
+          }
+          LLVM_DEBUG(dbgs() << "]\n");
+        }
+      }
+    }
+    Worklist.swap(Pending);
+    // At this point, pending must be empty, since it was just the empty
+    // worklist
+    assert(Pending.empty() && "Pending should be empty");
+  }
+
+  // That's the hard part over. Now we just have some admin to do.
+
+  // Record whether we inserted any intrinsics.
+  bool InsertedAnyIntrinsics = false;
+
+  // Identify and add defs for single location variables.
+  //
+  // Go through all of the defs that we plan to add. If the aggregate variable
+  // it's a part of is not in the NotAlwaysStackHomed set we can emit a single
+  // location def and omit the rest. Add an entry to AlwaysStackHomed so that
+  // we can identify those uneeded defs later.
+  DenseSet<DebugAggregate> AlwaysStackHomed;
+  for (auto Pair : InsertBeforeMap) {
+    auto &MapVec = Pair.second;
+    for (auto Pair : MapVec) {
+      DebugVariable Var = FnVarLocs->getVariable(Pair.first);
+      DebugAggregate Aggr{Var.getVariable(), Var.getInlinedAt()};
+      // Copy because we may modify this.
+      VarLocInfo VarLoc = Pair.second;
+
+      // Skip this Var if it's not always stack homed.
+      if (NotAlwaysStackHomed.contains(Aggr))
+        continue;
+
+      // Skip complex cases such as when different fragments of a variable have
+      // been split into different allocas. Skipping in this case means falling
+      // back to using a list of defs (which could reduce coverage, but is no
+      // less correct).
+      bool Simple =
+          VarLoc.Expr->getNumElements() == 1 && VarLoc.Expr->startsWithDeref();
+      if (!Simple) {
+        NotAlwaysStackHomed.insert(Aggr);
+        continue;
+      }
+
+      // All source assignments to this variable remain and all stores to any
+      // part of the variable store to the same address (with varying
+      // offsets). We can just emit a single location for the whole variable.
+      //
+      // Unless we've already done so, create the single location def now.
+      if (AlwaysStackHomed.insert(Aggr).second) {
+        assert(isa<AllocaInst>(VarLoc.V));
+        assert(Simple);
+        VarLoc.Expr = DIExpression::get(Fn.getContext(), None);
+        DebugVariable Var = FnVarLocs->getVariable(VarLoc.VariableID);
+        FnVarLocs->addSingleLocVar(Var, VarLoc.Expr, VarLoc.DL, VarLoc.V);
+        InsertedAnyIntrinsics = true;
+      }
+    }
+  }
+
+  // Insert the other DEFs.
+  for (auto Pair : InsertBeforeMap) {
+    Instruction *InsertBefore = Pair.first;
+    auto &MapVec = Pair.second;
+    SmallVector<VarLocInfo> NewDefs;
+    for (auto Pair : MapVec) {
+      DebugVariable Var = FnVarLocs->getVariable(Pair.first);
+      const VarLocInfo &VarLoc = Pair.second;
+      DebugAggregate Aggr{Var.getVariable(), Var.getInlinedAt()};
+      // If this variable is always stack homed then we have already inserted a
+      // dbg.declare and deleted this dbg.value.
+      if (AlwaysStackHomed.contains(Aggr))
+        continue;
+      NewDefs.push_back(VarLoc);
+      InsertedAnyIntrinsics = true;
+    }
+
+    FnVarLocs->setWedge(InsertBefore, NewDefs);
+  }
+
+  InsertedAnyIntrinsics |= emitPromotedVarLocs(FnVarLocs);
+
+  return InsertedAnyIntrinsics;
+}
+
+bool AssignmentTrackingLowering::emitPromotedVarLocs(
+    FunctionVarLocsBuilder *FnVarLocs) {
+  bool InsertedAnyIntrinsics = false;
+  // Go through every block, translating debug intrinsics for fully promoted
+  // variables into FnVarLocs location defs. No analysis required for these.
+  for (auto &BB : Fn) {
+    for (auto &I : BB) {
+      // Skip instructions other than dbg.values and dbg.assigns.
+      auto *DVI = dyn_cast<DbgValueInst>(&I);
+      if (!DVI)
+        continue;
+      // Skip variables that haven't been promoted - we've dealt with those
+      // already.
+      if (VarsWithStackSlot->contains(getAggregate(DVI)))
+        continue;
+      // Wrapper to get a single value (or undef) from DVI.
+      auto GetValue = [DVI]() -> Value * {
+        // Conditions for undef: Any operand undef, zero operands or single
+        // operand is nullptr. We also can't handle variadic DIExpressions yet.
+        // Some of those conditions don't have a type we can pick for
+        // undef. Use i32.
+        if (DVI->isUndef() || DVI->getValue() == nullptr || DVI->hasArgList())
+          return UndefValue::get(Type::getInt32Ty(DVI->getContext()));
+        return DVI->getValue();
+      };
+      Instruction *InsertBefore = I.getNextNode();
+      assert(InsertBefore && "Unexpected: debug intrinsics after a terminator");
+      FnVarLocs->addVarLoc(InsertBefore, DebugVariable(DVI),
+                           DVI->getExpression(), DVI->getDebugLoc(),
+                           GetValue());
+      InsertedAnyIntrinsics = true;
+    }
+  }
+  return InsertedAnyIntrinsics;
+}
+
+static DenseSet<DebugAggregate> findVarsWithStackSlot(Function &Fn) {
+  DenseSet<DebugAggregate> Result;
+  for (auto &BB : Fn) {
+    for (auto &I : BB) {
+      // Any variable linked to an instruction is considered
+      // interesting. Ideally we only need to check Allocas, however, a
+      // DIAssignID might get dropped from an alloca but not stores. In that
+      // case, we need to consider the variable intersting for NFC behaviour
+      // with this change. TODO: Consider only looking at allocas.
+      for (DbgAssignIntrinsic *DAI : at::getAssignmentMarkers(&I)) {
+        Result.insert({DAI->getVariable(), DAI->getDebugLoc().getInlinedAt()});
+      }
+    }
+  }
+  return Result;
+}
+
+static void analyzeFunction(Function &Fn, const DataLayout &Layout,
+                            FunctionVarLocsBuilder *FnVarLocs) {
+  // The analysis will generate location definitions for all variables, but we
+  // only need to perform a dataflow on the set of variables which have a stack
+  // slot. Find those now.
+  DenseSet<DebugAggregate> VarsWithStackSlot = findVarsWithStackSlot(Fn);
+  AssignmentTrackingLowering Pass(Fn, Layout, &VarsWithStackSlot);
+  Pass.run(FnVarLocs);
+}
+
+bool AssignmentTrackingAnalysis::runOnFunction(Function &F)  {
+  LLVM_DEBUG(dbgs() << "AssignmentTrackingAnalysis run on " << F.getName()
+                    << "\n");
+  auto DL = std::make_unique<DataLayout>(F.getParent());
+
+  // Clear previous results.
+  Results->clear();
+
+  FunctionVarLocsBuilder Builder;
+  analyzeFunction(F, *DL.get(), &Builder);
+
+  // Save these results.
+  Results->init(&Builder);
+
+  if (PrintResults && isFunctionInPrintList(F.getName()))
+    Results->print(errs(), F);
+
+  // Return false because this pass does not modify the function.
+  return false;
+}
+
+AssignmentTrackingAnalysis::AssignmentTrackingAnalysis()
+    : FunctionPass(ID), Results(std::make_unique<FunctionVarLocs>()) {}
+
+char AssignmentTrackingAnalysis::ID = 0;
+
+INITIALIZE_PASS(AssignmentTrackingAnalysis, DEBUG_TYPE,
+                "Assignment Tracking Analysis", false, true)

llvm/lib/CodeGen/CMakeLists.txt

if (DEFINED LLVM_HAVE_TF_API)
     list(APPEND MLLinkDeps ${tensorflow_c_api} ${tensorflow_fx})
   endif()
 endif()
 
 add_llvm_component_library(LLVMCodeGen
   AggressiveAntiDepBreaker.cpp
   AllocationOrder.cpp
   Analysis.cpp
+  AssignmentTrackingAnalysis.cpp
   AtomicExpandPass.cpp
   BasicTargetTransformInfo.cpp
   BranchFolding.cpp
   BranchRelaxation.cpp
   BreakFalseDeps.cpp
   BasicBlockSections.cpp
   CalcSpillWeights.cpp
   CallingConvLower.cpp

llvm/lib/CodeGen/CodeGen.cpp

 #include "llvm-c/Initialization.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/PassRegistry.h"
 
 using namespace llvm;
 
 /// initializeCodeGen - Initialize all passes linked into the CodeGen library.
 void llvm::initializeCodeGen(PassRegistry &Registry) {
+  initializeAssignmentTrackingAnalysisPass(Registry);
   initializeAtomicExpandPass(Registry);
   initializeBasicBlockSectionsPass(Registry);
   initializeBranchFolderPassPass(Registry);
   initializeBranchRelaxationPass(Registry);
   initializeCFGuardLongjmpPass(Registry);
   initializeCFIInstrInserterPass(Registry);
   initializeCheckDebugMachineModulePass(Registry);
   initializeCodeGenPreparePass(Registry);