[Assignment Tracking Analysis][3/*] Memory location fragment filling

[Orlando]

Summary

This patch adds another dataflow analysis to the AssignmentTrackingAnalysis pass (though it is much simpler than D136320).

The problem and goal

Disjoint and adjacent fragments compose well, however in the back-end, the following sequence

1. dbg.value ... Fragment(0, 64)
2. dbg.value ... Fragment(0, 32)

is effectively interpreted as setting Fragment(32, 32) (bits [32, 64)) to undef. Perhaps this scenario is uncommon or doesn't present much of an issue currently. However, this is a problem for assignment tracking where overlapping fragments are common between memory location definitions.

The goal of this analysis is to add new variable location definitions that preserve the "bits in memory" at subsequent definitions.

Dataflow high level details

Similar to the "core" analysis, this is a fixed point dataflow analysis. The main difference is that instead of working with join-semilattice types (monotonic increase to a fixed point) it works with meet-semilattice types (monotonic decrease to a fixed point). Basically, instead of performing something like a union when merging predecessor "live-outs" this one performs something like an intersect.

Implementation details

The value computed for each block is a map of aggregate variable to fragment memory locations. The fragment locations are tracked using an IntervalMap (one for each aggregate variable). The values mapped in the IntervalMaps are IDs that represent a stack slot.

In this patch it's probably easier to start looking at process first then join.

In process the location defs - generated by the first analysis - in each block are iterated over. At each location def for a fragment the relevant IntervalMap is updated. A new interval is inserted and new memory location defs for all partially overlapped intervals that are in memory are saved into BBInsertBeforeMap such that the not-overlapped bits in memory get a new def. For example:

Before:

var x bits 0 to 63:  value in memory
some instructions
var x bits 0 to 31:  value is %0

After:

var x bits 0 to 63:  value in memory
some instructions
var x bits 0 to 31:  value is %0
var x bits 32 to 61: value in memory ; <-- new location definition

In join we perform an intersect-like operation on the IntervalMaps. Essentially, we keep only the (sections of) the intervals where all predecessors agree the memory location is in use.

---

Again, tests coming in another patch.

[StephenTozer]

Comments aside, LGTM.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

42

255

This could be inverted and made into an early return.

310

A more descriptive name might be useful, painful as it is for a map of maps; even just VarFragMap or AggFragMap would be reasonable I think.

329

equ functions may be worth renaming.

462

Might be worth putting in a function comment that A is modified to contain the result of the meeting, while B is not modified; if you can think of good variable names to represent that as well (I can't) then that would be a good idea as well.

541

Maybe worth adding an assert(StartBit < EndBit && "Cannot create fragment of size <= 0") here as a guard against any future modifications to this pass (it seems like a possible result of some incorrect handling of intervals; there were a few cases in this patch I thought this error might appear until I investigated further).

555

Is the After parameter misnamed? As far as I can tell the intent is that this Def becomes live before After, which technically makes sense (the instruction comes "after" the def) but uses the opposite naming convention to elsewhere, where the paramater is named Before as-in "The instruction we're inserting before".

586–587

It looks like the condition has indeed been removed, unless the actual conditional check appears elsewhere in this pass?

619

Should this be LastOverlap.stop() > EndBit? I could have some misunderstandings about how this works, but to my understanding since this is a half-open interval map, if LastOverlap.start() >= EndBit then the interval map wouldn't consider it an overlap at all (e.g. [0, 16) does not overlap with [16, 32)).

625–628

I believe this example is actually incorrect - IntersectStart and IntersectStop are only true if the existing fragment extends beyond the start and end of this fragment, i.e.

     [ f ]
[  -   i   -  ]
+
[ i ][ f ][ i ]

In the example given in this comment, IntersectStart would be false because this fragment and the existing fragment have the same start bit, and so we would (correctly) fall through to the else block below.

[StephenTozer]

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

619

Nevermind, I get it now - I was thinking of LastOverlap as "the last existing fragment that overlaps with this fragment", but it's just the existing fragment that overlaps with EndBit if any exists.

[Orlando]

Thanks @StephenTozer

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

541

SGTM!

555

Yeah, sorry about that. This changed a few times during development.

586–587

That's the ternary operator condition below.

625–628

Yeah looks like you're right. Nice catch - I appreciate the keen-eyed review!

[StephenTozer]

Changes LGTM.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

586–587

Missed that, all good then.

[jmorse]

This is well motivated and useful -- I'm having some trouble building a mental model of what the lattice looks like though. IIUC we're seeking to identify the ranges of variable location that are well defined by the fragment ranges, but, because we later drop overlapped ranges at a later date, we want to explicitly state the not-overlapped memory location so that it isn't dropped. I don't quite see how meetFragments achieves that, as it only selects the bits that do overlap. Is the lattice collecting all the ranges where there's genuine overlap, so that later dbg.values split their ranges across the intersection? And if so, why does addDef delete "fully contained" overlaps, shouldn't it break all definitions up?

Another concern is the high cost of copying a DenseMap of IntervalMap's each join/meet -- this is probably fine if there are only a few leaked + partially promoted variables in a function, which is typically the case, do you have any statistics on how frequently that happens in a clang build for example? This might be a scenario where we need to land+evaluate on wider code bases before refining. It also might be acceptable to have a cut-off point where there are too many leaked variable locations to track, to avoid excessive work.

One also wonders whether @CarlosAlbertoEnciso 's IntervalTree would be useful to collect and identify overlapping areas. That would probably want a "global view" of the function where all fragments are split up from the beginning, wheras I suppose taking the dataflow approach limits it to only the regions where there's some overlap.

(Hitting request changes to take it out of the review queue).

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

228–230

Sounds good, potentially this is useful as a method of DIExpression, but let's think about that later.

266–267

Just to check my understanding: so anything that ends with DW_OP_stack_value is going to get filtered out by this check, yes?

288

".. and so we try to recover the rest of the fragment location here."

316–317

Mmmmm, map of map of interval map. Reallocations of this are going to be expensive. Do you have any statistics wrt. how frequently these scenarios present themseves?

558

const VarLocInfo &

592–595

Something unclear to me is what VarLoc.V is in this scenario -- it's being treated as if it's an alloca base, but the comment in patch 1 of "Needs to be value_s_ for variadic expressions." suggests that V is the actual value of an assignment. Commentry on the Bases container of what types it contains would be good.

611

Early return, avoid indentation?

[Orlando]

In D136325#3944096, @jmorse wrote:

This is well motivated and useful -- I'm having some trouble building a mental model of what the lattice looks like though. IIUC we're seeking to identify the ranges of variable location that are well defined by the fragment ranges, but, because we later drop overlapped ranges at a later date, we want to explicitly state the not-overlapped memory location so that it isn't dropped. I don't quite see how meetFragments achieves that, as it only selects the bits that do overlap. Is the lattice collecting all the ranges where there's genuine overlap, so that later dbg.values split their ranges across the intersection? And if so, why does addDef delete "fully contained" overlaps, shouldn't it break all definitions up?

it only selects the bits that do overlap

meetFragments is merging the LiveOut results of preds. If all preds agree the memory location for some bits is valid (intersect of variable fragments in memory) then that information is propagated. Bits not in that intersect are not treated as located in memory. During process (processing a block) the opposite occurs; the interval map is built up by taking the union of "bits in memory" according to the map and the encountered debug intrinsic. Where there is an intersection in that union we need to emit debug intrinsics to explicitly re-instate the memory location for the bits outside the intersect (union minus intersect). In other worse, the bits in memory that are "not shadowed" by a subsequent overlapping location def need a new location def.

Another concern is the high cost of copying a DenseMap of IntervalMap's each join/meet -- this is probably fine if there are only a few leaked + partially promoted variables in a function, which is typically the case, do you have any statistics on how frequently that happens in a clang build for example? This might be a scenario where we need to land+evaluate on wider code bases before refining. It also might be acceptable to have a cut-off point where there are too many leaked variable locations to track, to avoid excessive work.

I don't have any to hand but I can try and dig some out.

One also wonders whether @CarlosAlbertoEnciso 's IntervalTree would be useful to collect and identify overlapping areas. That would probably want a "global view" of the function where all fragments are split up from the beginning, wheras I suppose taking the dataflow approach limits it to only the regions where there's some overlap.

I did briefly investigate this during development and chose to use IntervalMap for the reasons you've just mentioned.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

266–267

Yes that's right.

316–317

Same as for the other patches, LiveIn and LiveOut are initialised to have a number of elements equal to the number of basic blocks, so in terms of reallocations we only pay for those done by the inner map, VarFragMap (which is a map of intervalmaps though - perhaps this is what you were talking about?).

592–595

MemLocFragFill (this pass) only works with memory locations.

a) AssignmentTrackingLowering (the previous pass) rewrites memory locations in terms of the base alloca
b) Variadic address component of a dbg.assign is not supported (and there are no plans for that)

So, here VarLoc.V is a) the base pointer for the whole variable and b) will never be variadic (even if/when the value component is updated to support variadic expressions).

611

Done, and have done the same for the outer else block (pulled it to the top just above here).

[Orlando]

+ Address comments

[jmorse]

I think I've clocked that this is a two-value lattice of \top and \bottom / true and false, indicating "this bit is in memory" or not in memory, and the intersection on meet ensures that it monotonically goes downwards, so we gradually remove bits from being in memory. Which sounds good and correct.

I had a slight concern that insertMemLoc might end up recording a history of what happens during dataflow exploration, instead of determining memory locations once a fixedpoint has been reached. What if we have this:

entry:
  everything-is-in-memory bits 0-to-127,
  br loophead
loophead:
  def bits 0-63
  br anotherblock
anotherblock:
  def bits 64-95
  br i1 %foo loophead, exit
exit:
  return

After chatting with Orlando elsewhere, it looks like on the first pass through the loop we'll start with bits 0 to 127 being in memory, then:

• On processing loophead, fragment it into being only bits 64 to 127 being in memory,
• Record that fact in BBInsertBeforeMap via insertMemLoc,
• Process anotherblock, now only bits 96 to 127 are in memory,
• Record that fact in BBInsertBeforeMap too,
• Loop back round to loophead,
• meet/merge the interval maps and determine that we have to go through the loop again,
• Clear BBInsertBeforeMap for loophead,
• Walk through loophead again generating data...
• (etc etc etc)

I'm a lot happier that I understand what's going on now, will check through comment responses...

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

328

Some commentry on the usage of this data structure appreciated -- specifically the fact that it always records the _last_ (AFAUI) memory/fragment map through a block. I didn't clock that it was repeatedly cleared until much later.

[jmorse]

LGTM, with a request for some more documentation comments in the earlier comment.

[Orlando]

Thanks again for all the reviews!

[Orlando]

Squashed into 1d1de7467c32d52926ca56b9167a2c65c451ecfa

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

 STATISTIC(NumDefsRemoved, "Number of dbg locs removed");
 STATISTIC(NumWedgesScanned, "Number of dbg wedges scanned");
 STATISTIC(NumWedgesChanged, "Number of dbg wedges changed");
 
 static cl::opt<unsigned>
     MaxNumBlocks("debug-ata-max-blocks", cl::init(10000),
                  cl::desc("Maximum num basic blocks before debug info dropped"),
                  cl::Hidden);
+/// Option for debugging the pass, determines if the memory location fragment
+/// filling happens after generating the variable locations.
+static cl::opt<bool> EnableMemLocFragFill("mem-loc-frag-fill", cl::init(true),
+                                          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>;
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, Expression};
 }
 
+/// Extract the offset used in \p DIExpr. Returns None if the expression
+/// doesn't explicitly describe a memory location with DW_OP_deref or if the
+/// expression is too complex to interpret.
+static Optional<int64_t> getDerefOffsetInBytes(const DIExpression *DIExpr) {
+  int64_t Offset = 0;
+  const unsigned NumElements = DIExpr->getNumElements();
+  const auto Elements = DIExpr->getElements();
+  unsigned NextElement = 0;
+  // Extract the offset.
+  if (NumElements > 2 && Elements[0] == dwarf::DW_OP_plus_uconst) {
+    Offset = Elements[1];
+    NextElement = 2;
+  } else if (NumElements > 3 && Elements[0] == dwarf::DW_OP_constu) {
+    NextElement = 3;
+    if (Elements[2] == dwarf::DW_OP_plus)
+      Offset = Elements[1];
+    else if (Elements[2] == dwarf::DW_OP_minus)
+      Offset = -Elements[1];
+    else
+      return None;
+  }
+
+  // If that's all there is it means there's no deref.
+  if (NextElement >= NumElements)
+    return None;
+
+  // Check the next element is DW_OP_deref - otherwise this is too complex or
+  // isn't a deref expression.
+  if (Elements[NextElement] != dwarf::DW_OP_deref)
+    return None;
+
+  // Check the final operation is either the DW_OP_deref or is a fragment.
+  if (NumElements == NextElement + 1)
+    return Offset; // Ends with deref.
+  else if (NumElements == NextElement + 3 &&
+           Elements[NextElement] == dwarf::DW_OP_LLVM_fragment)
+    return Offset; // Ends with deref + fragment.
+
+  // Don't bother trying to interpret anything more complex.
+  return None;
+}
+
 /// 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());
 }
+static DebugAggregate getAggregate(const DebugVariable &Var) {
+  return DebugAggregate(Var.getVariable(), Var.getInlinedAt());
+}
+
+/// In dwarf emission, the following sequence
+///    1. dbg.value ... Fragment(0, 64)
+///    2. dbg.value ... Fragment(0, 32)
+/// effectively sets Fragment(32, 32) to undef (each def sets all bits not in
+/// the intersection of the fragments to having "no location"). This makes
+/// sense for implicit location values because splitting the computed values
+/// could be troublesome, and is probably quite uncommon.  When we convert
+/// dbg.assigns to dbg.value+deref this kind of thing is common, and describing
+/// a location (memory) rather than a value means we don't need to worry about
+/// splitting any values, so we try to recover the rest of the fragment
+/// location here.
+/// This class performs a(nother) dataflow analysis over the function, adding
+/// variable locations so that any bits of a variable with a memory location
+/// have that location explicitly reinstated at each subsequent variable
+/// location definition that that doesn't overwrite those bits. i.e. after a
+/// variable location def, insert new defs for the memory location with
+/// fragments for the difference of "all bits currently in memory" and "the
+/// fragment of the second def".
+class MemLocFragmentFill {
+  Function &Fn;
+  FunctionVarLocsBuilder *FnVarLocs;
+  const DenseSet<DebugAggregate> *VarsWithStackSlot;
+
+  // 0 = no memory location.
+  using BaseAddress = unsigned;
+  using OffsetInBitsTy = unsigned;
+  using FragTraits = IntervalMapHalfOpenInfo<OffsetInBitsTy>;
+  using FragsInMemMap = IntervalMap<
+      OffsetInBitsTy, BaseAddress,
+      IntervalMapImpl::NodeSizer<OffsetInBitsTy, BaseAddress>::LeafSize,
+      FragTraits>;
+  FragsInMemMap::Allocator IntervalMapAlloc;
+  using VarFragMap = DenseMap<unsigned, FragsInMemMap>;
+
+  /// IDs for memory location base addresses in maps. Use 0 to indicate that
+  /// there's no memory location.
+  UniqueVector<Value *> Bases;
+  UniqueVector<DebugAggregate> Aggregates;
+  DenseMap<const BasicBlock *, VarFragMap> LiveIn;
+  DenseMap<const BasicBlock *, VarFragMap> LiveOut;
+
+  struct FragMemLoc {
+    unsigned Var;
+    unsigned Base;
+    unsigned OffsetInBits;
+    unsigned SizeInBits;
+    DebugLoc DL;
+  };
+  using InsertMap = MapVector<Instruction *, SmallVector<FragMemLoc>>;
+
+  /// BBInsertBeforeMap holds a description for the set of location defs to be
+  /// inserted after the analysis is complete. It is updated during the dataflow
+  /// and the entry for a block is CLEARED each time it is (re-)visited. After
+  /// the dataflow is complete, each block entry will contain the set of defs
+  /// calculated during the final (fixed-point) iteration.
+  DenseMap<const BasicBlock *, InsertMap> BBInsertBeforeMap;
+
+  static bool intervalMapsAreEqual(const FragsInMemMap &A,
+                                   const FragsInMemMap &B) {
+    auto AIt = A.begin(), AEnd = A.end();
+    auto BIt = B.begin(), BEnd = B.end();
+    for (; AIt != AEnd; ++AIt, ++BIt) {
+      if (BIt == BEnd)
+        return false; // B has fewer elements than A.
+      if (AIt.start() != BIt.start() || AIt.stop() != BIt.stop())
+        return false; // Interval is different.
+      if (AIt.value() != BIt.value())
+        return false; // Value at interval is different.
+    }
+    // AIt == AEnd. Check BIt is also now at end.
+    return BIt == BEnd;
+  }
+
+  static bool varFragMapsAreEqual(const VarFragMap &A, const VarFragMap &B) {
+    if (A.size() != B.size())
+      return false;
+    for (const auto &APair : A) {
+      auto BIt = B.find(APair.first);
+      if (BIt == B.end())
+        return false;
+      if (!intervalMapsAreEqual(APair.second, BIt->second))
+        return false;
+    }
+    return true;
+  }
+
+  /// Return a string for the value that \p BaseID represents.
+  std::string toString(unsigned BaseID) {
+    if (BaseID)
+      return Bases[BaseID]->getName().str();
+    else
+      return "None";
+  }
+
+  /// Format string describing an FragsInMemMap (IntervalMap) interval.
+  std::string toString(FragsInMemMap::const_iterator It, bool Newline = true) {
+    std::string String;
+    std::stringstream S(String);
+    if (It.valid()) {
+      S << "[" << It.start() << ", " << It.stop()
+        << "): " << toString(It.value());
+    } else {
+      S << "invalid iterator (end)";
+    }
+    if (Newline)
+      S << "\n";
+    return S.str();
+  };
+
+  FragsInMemMap meetFragments(const FragsInMemMap &A, const FragsInMemMap &B) {
+    FragsInMemMap Result(IntervalMapAlloc);
+    for (auto AIt = A.begin(), AEnd = A.end(); AIt != AEnd; ++AIt) {
+      LLVM_DEBUG(dbgs() << "a " << toString(AIt));
+      // This is basically copied from process() and inverted (process is
+      // performing something like a union whereas this is more of an
+      // intersect).
+
+      // There's no work to do if interval `a` overlaps no fragments in map `B`.
+      if (!B.overlaps(AIt.start(), AIt.stop()))
+        continue;
+
+      // Does StartBit intersect an existing fragment?
+      auto FirstOverlap = B.find(AIt.start());
+      assert(FirstOverlap != B.end());
+      bool IntersectStart = FirstOverlap.start() < AIt.start();
+      LLVM_DEBUG(dbgs() << "- FirstOverlap " << toString(FirstOverlap, false)
+                        << ", IntersectStart: " << IntersectStart << "\n");
+
+      // Does EndBit intersect an existing fragment?
+      auto LastOverlap = B.find(AIt.stop());
+      bool IntersectEnd =
+          LastOverlap != B.end() && LastOverlap.start() < AIt.stop();
+      LLVM_DEBUG(dbgs() << "- LastOverlap " << toString(LastOverlap, false)
+                        << ", IntersectEnd: " << IntersectEnd << "\n");
+
+      // Check if both ends of `a` intersect the same interval `b`.
+      if (IntersectStart && IntersectEnd && FirstOverlap == LastOverlap) {
+        // Insert `a` (`a` is contained in `b`) if the values match.
+        // [ a ]
+        // [ - b - ]
+        // -
+        // [ r ]
+        LLVM_DEBUG(dbgs() << "- a is contained within "
+                          << toString(FirstOverlap));
+        if (AIt.value() && AIt.value() == FirstOverlap.value())
+          Result.insert(AIt.start(), AIt.stop(), AIt.value());
+      } else {
+        // There's an overlap but `a` is not fully contained within
+        // `b`. Shorten any end-point intersections.
+        //     [ - a - ]
+        // [ - b - ]
+        // -
+        //     [ r ]
+        auto Next = FirstOverlap;
+        if (IntersectStart) {
+          LLVM_DEBUG(dbgs() << "- insert intersection of a and "
+                            << toString(FirstOverlap));
+          if (AIt.value() && AIt.value() == FirstOverlap.value())
+            Result.insert(AIt.start(), FirstOverlap.stop(), AIt.value());
+          ++Next;
+        }
+        // [ - a - ]
+        //     [ - b - ]
+        // -
+        //     [ r ]
+        if (IntersectEnd) {
+          LLVM_DEBUG(dbgs() << "- insert intersection of a and "
+                            << toString(LastOverlap));
+          if (AIt.value() && AIt.value() == LastOverlap.value())
+            Result.insert(LastOverlap.start(), AIt.stop(), AIt.value());
+        }
+
+        // Insert all intervals in map `B` that are contained within interval
+        // `a` where the values match.
+        // [ -  - a -  - ]
+        // [ b1 ]   [ b2 ]
+        // -
+        // [ r1 ]   [ r2 ]
+        while (Next != B.end() && Next.start() < AIt.stop() &&
+               Next.stop() <= AIt.stop()) {
+          LLVM_DEBUG(dbgs()
+                     << "- insert intersection of a and " << toString(Next));
+          if (AIt.value() && AIt.value() == Next.value())
+            Result.insert(Next.start(), Next.stop(), Next.value());
+          ++Next;
+        }
+      }
+    }
+    return Result;
+  }
+
+  /// Meet \p A and \p B, storing the result in \p A.
+  void meetVars(VarFragMap &A, const VarFragMap &B) {
+    // Meet A and B.
+    //
+    // Result = meet(a, b) for a in A, b in B where Var(a) == Var(b)
+    for (auto It = A.begin(), End = A.end(); It != End; ++It) {
+      unsigned AVar = It->first;
+      FragsInMemMap &AFrags = It->second;
+      auto BIt = B.find(AVar);
+      if (BIt == B.end()) {
+        A.erase(It);
+        continue; // Var has no bits defined in B.
+      }
+      LLVM_DEBUG(dbgs() << "meet fragment maps for "
+                        << Aggregates[AVar].first->getName() << "\n");
+      AFrags = meetFragments(AFrags, BIt->second);
+    }
+  }
+
+  bool meet(const BasicBlock &BB,
+            const SmallPtrSet<BasicBlock *, 16> &Visited) {
+    LLVM_DEBUG(dbgs() << "meet block info from preds of " << BB.getName()
+                      << "\n");
+
+    VarFragMap BBLiveIn;
+    bool FirstMeet = true;
+    // LiveIn locs for BB is the meet of the already-processed preds' LiveOut
+    // locs.
+    for (auto I = pred_begin(&BB), E = pred_end(&BB); I != E; I++) {
+      // Ignore preds that haven't been processed yet. This is essentially the
+      // same as initialising all variables to implicit top value (⊤) which is
+      // the identity value for the meet operation.
+      const BasicBlock *Pred = *I;
+      if (!Visited.count(Pred))
+        continue;
+
+      auto PredLiveOut = LiveOut.find(Pred);
+      assert(PredLiveOut != LiveOut.end());
+
+      if (FirstMeet) {
+        LLVM_DEBUG(dbgs() << "BBLiveIn = " << Pred->getName() << "\n");
+        BBLiveIn = PredLiveOut->second;
+        FirstMeet = false;
+      } else {
+        LLVM_DEBUG(dbgs() << "BBLiveIn = meet BBLiveIn, " << Pred->getName()
+                          << "\n");
+        meetVars(BBLiveIn, PredLiveOut->second);
+      }
+
+      // An empty set is ⊥ for the intersect-like meet operation. If we've
+      // already got ⊥ there's no need to run the code - we know the result is
+      // ⊥ since `meet(a, ⊥) = ⊥`.
+      if (BBLiveIn.size() == 0)
+        break;
+    }
+
+    auto CurrentLiveInEntry = LiveIn.find(&BB);
+    // If there's no LiveIn entry for the block yet, add it.
+    if (CurrentLiveInEntry == LiveIn.end()) {
+      LLVM_DEBUG(dbgs() << "change=true (first) on meet on " << BB.getName()
+                        << "\n");
+      LiveIn[&BB] = std::move(BBLiveIn);
+      return /*Changed=*/true;
+    }
+
+    // If the LiveIn set has changed (expensive check) update it and return
+    // true.
+    if (!varFragMapsAreEqual(BBLiveIn, CurrentLiveInEntry->second)) {
+      LLVM_DEBUG(dbgs() << "change=true on meet on " << BB.getName() << "\n");
+      CurrentLiveInEntry->second = std::move(BBLiveIn);
+      return /*Changed=*/true;
+    }
+
+    LLVM_DEBUG(dbgs() << "change=false on meet on " << BB.getName() << "\n");
+    return /*Changed=*/false;
+  }
+
+  void insertMemLoc(BasicBlock &BB, Instruction &Before, unsigned Var,
+                    unsigned StartBit, unsigned EndBit, unsigned Base,
+                    DebugLoc DL) {
+    assert(StartBit < EndBit && "Cannot create fragment of size <= 0");
+    if (!Base)
+      return;
+    FragMemLoc Loc;
+    Loc.Var = Var;
+    Loc.OffsetInBits = StartBit;
+    Loc.SizeInBits = EndBit - StartBit;
+    assert(Base && "Expected a non-zero ID for Base address");
+    Loc.Base = Base;
+    Loc.DL = DL;
+    BBInsertBeforeMap[&BB][&Before].push_back(Loc);
+    LLVM_DEBUG(dbgs() << "Add mem def for " << Aggregates[Var].first->getName()
+                      << " bits [" << StartBit << ", " << EndBit << ")\n");
+  }
+
+  void addDef(const VarLocInfo &VarLoc, Instruction &Before, BasicBlock &BB,
+              VarFragMap &LiveSet) {
+    DebugVariable DbgVar = FnVarLocs->getVariable(VarLoc.VariableID);
+    if (skipVariable(DbgVar.getVariable()))
+      return;
+    // Don't bother doing anything for this variables if we know it's fully
+    // promoted. We're only interested in variables that (sometimes) live on
+    // the stack here.
+    if (!VarsWithStackSlot->count(getAggregate(DbgVar)))
+      return;
+    unsigned Var = Aggregates.insert(
+        DebugAggregate(DbgVar.getVariable(), VarLoc.DL.getInlinedAt()));
+
+    // [StartBit: EndBit) are the bits affected by this def.
+    const DIExpression *DIExpr = VarLoc.Expr;
+    unsigned StartBit;
+    unsigned EndBit;
+    if (auto Frag = DIExpr->getFragmentInfo()) {
+      StartBit = Frag->OffsetInBits;
+      EndBit = StartBit + Frag->SizeInBits;
+    } else {
+      assert(static_cast<bool>(DbgVar.getVariable()->getSizeInBits()));
+      StartBit = 0;
+      EndBit = *DbgVar.getVariable()->getSizeInBits();
+    }
+
+    // We will only fill fragments for simple memory-describing dbg.value
+    // intrinsics. If the fragment offset is the same as the offset from the
+    // base pointer, do The Thing, otherwise fall back to normal dbg.value
+    // behaviour. AssignmentTrackingLowering has generated DIExpressions
+    // written in terms of the base pointer.
+    // TODO: Remove this condition since the fragment offset doesn't always
+    // equal the offset from base pointer (e.g. for a SROA-split variable).
+    const auto DerefOffsetInBytes = getDerefOffsetInBytes(DIExpr);
+    const unsigned Base =
+        DerefOffsetInBytes && *DerefOffsetInBytes * 8 == StartBit
+            ? Bases.insert(VarLoc.V)
+            : 0;
+    LLVM_DEBUG(dbgs() << "DEF " << DbgVar.getVariable()->getName() << " ["
+                      << StartBit << ", " << EndBit << "): " << toString(Base)
+                      << "\n");
+
+    // First of all, any locs that use mem that are disrupted need reinstating.
+    // Unfortunately, IntervalMap doesn't let us insert intervals that overlap
+    // with existing intervals so this code involves a lot of fiddling around
+    // with intervals to do that manually.
+    auto FragIt = LiveSet.find(Var);
+
+    // Check if the variable does not exist in the map.
+    if (FragIt == LiveSet.end()) {
+      // Add this variable to the BB map.
+      auto P = LiveSet.try_emplace(Var, FragsInMemMap(IntervalMapAlloc));
+      assert(P.second && "Var already in map?");
+      // Add the interval to the fragment map.
+      P.first->second.insert(StartBit, EndBit, Base);
+      return;
+    }
+    // The variable has an entry in the map.
+
+    FragsInMemMap &FragMap = FragIt->second;
+    // First check the easy case: the new fragment `f` doesn't overlap with any
+    // intervals.
+    if (!FragMap.overlaps(StartBit, EndBit)) {
+      LLVM_DEBUG(dbgs() << "- No overlaps\n");
+      FragMap.insert(StartBit, EndBit, Base);
+      return;
+    }
+    // There is at least one overlap.
+
+    // Does StartBit intersect an existing fragment?
+    auto FirstOverlap = FragMap.find(StartBit);
+    assert(FirstOverlap != FragMap.end());
+    bool IntersectStart = FirstOverlap.start() < StartBit;
+
+    // Does EndBit intersect an existing fragment?
+    auto LastOverlap = FragMap.find(EndBit);
+    bool IntersectEnd = LastOverlap.valid() && LastOverlap.start() < EndBit;
+
+    // Check if both ends of `f` intersect the same interval `i`.
+    if (IntersectStart && IntersectEnd && FirstOverlap == LastOverlap) {
+      LLVM_DEBUG(dbgs() << "- Intersect single interval @ both ends\n");
+      // Shorten `i` so that there's space to insert `f`.
+      //      [ f ]
+      // [  -   i   -  ]
+      // +
+      // [ i ][ f ][ i ]
+      auto EndBitOfOverlap = FirstOverlap.stop();
+      FirstOverlap.setStop(StartBit);
+      insertMemLoc(BB, Before, Var, FirstOverlap.start(), StartBit,
+                   FirstOverlap.value(), VarLoc.DL);
+
+      // Insert a new interval to represent the end part.
+      FragMap.insert(EndBit, EndBitOfOverlap, FirstOverlap.value());
+      insertMemLoc(BB, Before, Var, EndBit, EndBitOfOverlap,
+                   FirstOverlap.value(), VarLoc.DL);
+
+      // Insert the new (middle) fragment now there is space.
+      FragMap.insert(StartBit, EndBit, Base);
+    } else {
+      // There's an overlap but `f` may not be fully contained within
+      // `i`. Shorten any end-point intersections so that we can then
+      // insert `f`.
+      //      [ - f - ]
+      // [ - i - ]
+      // |   |
+      // [ i ]
+      // Shorten any end-point intersections.
+      if (IntersectStart) {
+        LLVM_DEBUG(dbgs() << "- Intersect interval at start\n");
+        // Split off at the intersection.
+        FirstOverlap.setStop(StartBit);
+        insertMemLoc(BB, Before, Var, FirstOverlap.start(), StartBit,
+                     FirstOverlap.value(), VarLoc.DL);
+      }
+      // [ - f - ]
+      //      [ - i - ]
+      //          |   |
+      //          [ i ]
+      if (IntersectEnd) {
+        LLVM_DEBUG(dbgs() << "- Intersect interval at end\n");
+        // Split off at the intersection.
+        LastOverlap.setStart(EndBit);
+        insertMemLoc(BB, Before, Var, EndBit, LastOverlap.stop(),
+                     LastOverlap.value(), VarLoc.DL);
+      }
+
+      LLVM_DEBUG(dbgs() << "- Erase intervals contained within\n");
+      // FirstOverlap and LastOverlap have been shortened such that they're
+      // no longer overlapping with [StartBit, EndBit). Delete any overlaps
+      // that remain (these will be fully contained within `f`).
+      // [ - f - ]       }
+      //      [ - i - ]  } Intersection shortening that has happened above.
+      //          |   |  }
+      //          [ i ]  }
+      // -----------------
+      // [i2 ]           } Intervals fully contained within `f` get erased.
+      // -----------------
+      // [ - f - ][ i ]  } Completed insertion.
+      auto It = FirstOverlap;
+      if (IntersectStart)
+        ++It; // IntersectStart: first overlap has been shortened.
+      while (It.valid() && It.start() >= StartBit && It.stop() <= EndBit) {
+        LLVM_DEBUG(dbgs() << "- Erase " << toString(It));
+        It.erase(); // This increments It after removing the interval.
+      }
+      // We've dealt with all the overlaps now!
+      assert(!FragMap.overlaps(StartBit, EndBit));
+      LLVM_DEBUG(dbgs() << "- Insert DEF into now-empty space\n");
+      FragMap.insert(StartBit, EndBit, Base);
+    }
+  }
+
+  bool skipVariable(const DILocalVariable *V) { return !V->getSizeInBits(); }
+
+  void process(BasicBlock &BB, VarFragMap &LiveSet) {
+    BBInsertBeforeMap[&BB].clear();
+    for (auto &I : BB) {
+      if (const auto *Locs = FnVarLocs->getWedge(&I)) {
+        for (const VarLocInfo &Loc : *Locs) {
+          addDef(Loc, I, *I.getParent(), LiveSet);
+        }
+      }
+    }
+  }
+
+public:
+  MemLocFragmentFill(Function &Fn,
+                     const DenseSet<DebugAggregate> *VarsWithStackSlot)
+      : Fn(Fn), VarsWithStackSlot(VarsWithStackSlot) {}
+
+  /// Add variable locations to \p FnVarLocs so that any bits of a variable
+  /// with a memory location have that location explicitly reinstated at each
+  /// subsequent variable location definition that that doesn't overwrite those
+  /// bits. i.e. after a variable location def, insert new defs for the memory
+  /// location with fragments for the difference of "all bits currently in
+  /// memory" and "the fragment of the second def". e.g.
+  ///
+  ///     Before:
+  ///
+  ///     var x bits 0 to 63:  value in memory
+  ///     more instructions
+  ///     var x bits 0 to 31:  value is %0
+  ///
+  ///     After:
+  ///
+  ///     var x bits 0 to 63:  value in memory
+  ///     more instructions
+  ///     var x bits 0 to 31:  value is %0
+  ///     var x bits 32 to 61: value in memory ; <-- new loc def
+  ///
+  void run(FunctionVarLocsBuilder *FnVarLocs) {
+    if (!EnableMemLocFragFill)
+      return;
+
+    this->FnVarLocs = 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 "intersect of predecessor outs" dataflow problem. To
+    // solve it, we perform meet() and process() using the two worklist method
+    // until the LiveIn data for each block becomes unchanging.
+    //
+    // This dataflow is essentially working on maps of sets and at each meet we
+    // intersect the maps and the mapped sets. So, initialized live-in maps
+    // monotonically decrease 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.  We could avoid this with a custom priority queue, but
+      // this is probably not worth it.
+      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 = meet(*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. Once we've processed
+          //  the terminator LiveSet is the LiveOut set for BB.
+          //  This is an expensive copy!
+          VarFragMap LiveSet = LiveIn[BB];
+
+          // Process the instructions in the block.
+          process(*BB, LiveSet);
+
+          // Relatively expensive check: has anything changed in LiveOut for BB?
+          if (!varFragMapsAreEqual(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");
+    }
+
+    // Insert new location defs.
+    for (auto Pair : BBInsertBeforeMap) {
+      InsertMap &Map = Pair.second;
+      for (auto Pair : Map) {
+        Instruction *InsertBefore = Pair.first;
+        assert(InsertBefore && "should never be null");
+        auto FragMemLocs = Pair.second;
+        auto &Ctx = Fn.getContext();
+
+        for (auto FragMemLoc : FragMemLocs) {
+          DIExpression *Expr = DIExpression::get(Ctx, None);
+          Expr = *DIExpression::createFragmentExpression(
+              Expr, FragMemLoc.OffsetInBits, FragMemLoc.SizeInBits);
+          Expr = DIExpression::prepend(Expr, DIExpression::DerefAfter,
+                                       FragMemLoc.OffsetInBits / 8);
+          DebugVariable Var(Aggregates[FragMemLoc.Var].first, Expr,
+                            FragMemLoc.DL.getInlinedAt());
+          FnVarLocs->addVarLoc(InsertBefore, Var, Expr, FragMemLoc.DL,
+                               Bases[FragMemLoc.Base]);
+        }
+      }
+    }
+  }
+};
 
 /// 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
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);
 
   bool Changed = false;
 
+  // Use a scope block to clean up AssignmentTrackingLowering before running
+  // MemLocFragmentFill to reduce peak memory consumption.
+  {
     AssignmentTrackingLowering Pass(Fn, Layout, &VarsWithStackSlot);
     Changed = Pass.run(FnVarLocs);
+  }
 
   if (Changed) {
+    MemLocFragmentFill Pass(Fn, &VarsWithStackSlot);
+    Pass.run(FnVarLocs);
+
     // Remove redundant entries. As well as reducing memory consumption and
     // avoiding waiting cycles later by burning some now, this has another
     // important job. That is to work around some SelectionDAG quirks. See
     // removeRedundantDbgLocsUsingForwardScan comments for more info on that.
     for (auto &BB : Fn)
       removeRedundantDbgLocs(&BB, *FnVarLocs);
   }
 }