StackColoring: smarter check for slot overlap

[arielb1]

Summary

The old check for slot overlap treated 2 slots S and T as
overlapping if there existed a CFG node in which both of the slots could
possibly be active. That is overly conservative and caused stack blowups
in Rust programs. Instead, check whether there is a single CFG node in
which both of the slots are possibly active *together*.

Fixes PR32488.

[thanm]

Hi Ariel,

I am thinking that maybe there is something wrong with the patch on phab-- I downloaded it and it would not compile:

StackColoring.cpp:1050:5: error: use of undeclared identifier 'UI'
    UI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator);

I fixed that up in the obvious way.

Aside from that, I'd say that so far I don't think I completely understand how your strategy works. Part of this may be due simple to terminology and the names you've given to the new things.

For example, I don't get why you've chosen the name "Use" for the new set in BlockInfo. The fact that gets recorded in this set is not really a "use" of the stack slot. Consider these two blocks:

BB1:
  lifetime_end slot 5
  branch

BB2:
  lifetime_end slot 5
  lifetime_start slot 5
  use of slot 5
  branch

The way the code works now, "Use" will be set for BB1 and not for BB2, even though BB2 has an actual use (reference to) the slot and BB2 does not. This is very confusing for people reading the code.

Similar confusion over your use of the term "active" in the comment ("active" is also used at various other places in the file comments, and I don't think your definition of "active" is the same as that used in the other places). Ditto for "IntervalStarts" -- why is it named this way?

Another point of confusion is over the use of the term "interference graph" in the comments-- the data structure being used to capture interferences is not really a graph, there are no explicit edges to speak of. A real interference graph would be an improvement over what's there (could be more precise in a number of cases), but that's not what exists in the code today.

A final question is what sort of testing you've done so far to make sure this works for all the odd corner cases. LNT and bootstrap build are two things that come to mind.

With that said, please keep working on this, I think it's worth pursuing. I am OOO all this week and possibly next, so I won't have a lot of time to look at it, but I'll get there eventually.

Regards,

Than

[arielb1]

Typofix UI -> SI

[arielb1]

In D31583#718444, @thanm wrote:

Hi Ariel,

I am thinking that maybe there is something wrong with the patch on phab-- I downloaded it and it would not compile:

StackColoring.cpp:1050:5: error: use of undeclared identifier 'UI'
    UI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator);

I fixed that up in the obvious way.

Fixed that.

Aside from that, I'd say that so far I don't think I completely understand how your strategy works. Part of this may be due simple to terminology and the names you've given to the new things.

For example, I don't get why you've chosen the name "Use" for the new set in BlockInfo. The fact that gets recorded in this set is not really a "use" of the stack slot. Consider these two blocks:

BB1:
  lifetime_end slot 5
  branch

BB2:
  lifetime_end slot 5
  lifetime_start slot 5
  use of slot 5
  branch

The way the code works now, "Use" will be set for BB1 and not for BB2, even though BB2 has an actual use (reference to) the slot and BB2 does not. This is very confusing for people reading the code.

BLI.Use refes, as it says, to a slot that begins and ends within the same block. Maybe I should have called it "BeginAndEnd" or something? Maybe I should have Use also include Begin (actually, let's do that)?

Similar confusion over your use of the term "active" in the comment ("active" is also used at various other places in the file comments, and I don't think your definition of "active" is the same as that used in the other places). Ditto for "IntervalStarts" -- why is it named this way?

I thought "active" was a new fresh term. I informally referred to it as "live", but unfortunately "live" has another meaning. Is there a better term than "active"?

Another point of confusion is over the use of the term "interference graph" in the comments-- the data structure being used to capture interferences is not really a graph, there are no explicit edges to speak of. A real interference graph would be an improvement over what's there (could be more precise in a number of cases), but that's not what exists in the code today.

I was thinking about things theoretically.

A final question is what sort of testing you've done so far to make sure this works for all the odd corner cases. LNT and bootstrap build are two things that come to mind.

I bootstrapped rustc and passed all of its tests. I don't know how to bootstrap LLVM, so I didn't do that.

With that said, please keep working on this, I think it's worth pursuing. I am OOO all this week and possibly next, so I won't have a lot of time to look at it, but I'll get there eventually.

Thanks.

Regards,

Than

[• dberlin]

To try to echo a bit what than is saying:, i think it would be helpful if you could write some paragraphs of what you think the high level design of this new part is.

IE something like:
we create a dataflow problem that tells us x
we do this by computing these attributes on a per-block basis, and then finding a maximal fixpoint.
We then use x to prune y.

or whatever.

I can think of a lot of different approaches than stack coloring currently takes (IE you could do real liveness analysis, as than mentions, you could build interference graphs and simplify them, etc), but they are more fundamental changes than i see here.

[arielb1]

Change names and comment to not mention interference graph.

[arielb1]

In D31583#719207, @dberlin wrote:

To try to echo a bit what than is saying:, i think it would be helpful if you could write some paragraphs of what you think the high level design of this new part is.

IE something like:
we create a dataflow problem that tells us x
we do this by computing these attributes on a per-block basis, and then finding a maximal fixpoint.
We then use x to prune y.

or whatever.

I can think of a lot of different approaches than stack coloring currently takes (IE you could do real liveness analysis, as than mentions, you could build interference graphs and simplify them, etc), but they are more fundamental changes than i see here.

I have a big comment in the source code that is supposed to be that explanation. Is there anything missing?

[• dberlin]

lib/CodeGen/StackColoring.cpp

1125

Or you could just augment the standard dataflow problem with more info?
You also just kind of assert it doesn't give very good results, but it's pretty widely used with good results :)

1163

Errr, what?
It is very possible to do this in N time with N dataflow facts.

[arielb1]

lib/CodeGen/StackColoring.cpp

1125

What I said is that what the old code was doing - propagating the N S active facts across the CFG and that
saying that 2 nodes interfere if they are both potentially active at a point - is overconservative at merge points.
Merging this PR caused x16 stack usage reductions in real world Rust compiler stack usage.

My algorithm also propagates the N S active facts, but uses them along with S active starts non-propagated facts to compute S active & T active more precisely.

Liveness can make it smarter, but aliasing makes it annoying to compute (and if there are opaque function calls in the merge BB, impossible to compute).

[dotdash]

test/CodeGen/X86/StackColoring.ll

539

I think you want to use %bar here.

[arielb1]

Clean up code to LLVM standards - thanks @doener. Also add support for multiple live ranges.

[dotdash]

Since I had a hand in changing the logic for the live interval calculation, I
feel like I should take some time to explain the approach that was taken here.

Originally, the stack coloring pass collected the lifetime markers and assumed
that there are at most two such markers per MBB. Either in the order start ->
end, creating a single segment in the live interval. Or in the order end ->
start, creating two segments in the live interval, the slot being dead in the
middle of the MBB.

Later the code was adjusted to handle more than two markers per block. Because
the collected markers were in a random order, instead of forming multiple
segments only a single segment was created and extended as needed.
Unfortunately this actually broke the logic for handling two markers in the
order end -> start. This is because the LiveIn and LiveOut bits would then also
be set, and the segment gets extended to cover the whole MBB.

By now, we're iterating over the instructions in the MBB in order anyway, so we
can actually handle multiple start/end markers properly and create multiple
segments in the live interval even within a single block.

The semantics are as follows:

A slot for which there are no lifetime markers is always live.

For slots that have lifetime markers:

In the entry MBB, the slot starts out as dead. In other MBBs, the slot starts
out as live if the dataflow analysis determined it to be live coming into this
block, otherwise it starts as dead.

Iterating over the instructions in the MBB in sequential order:

A dead slot becomes live when it encounters a START (which could be a use), and
stays live until it encounters an END. Any START encountered while a slot is
live has no effect. This is necessary, because the START could be a plain use
rather than a lifetime_start and may thus not shorten the live interval.

A live slot becomes dead when it encounters an END. At this point, the slots
live interval gets a new segment that starts at the index where the slot became
live, and ends at the index the END was encountered. Any END encountered while
a slot is dead has no effect.

Building upon that, the improvement this patch was initially motivated by is
described below.

Because a lifetime end on a dead slot has no effect, a frontend may choose to
combine certain code paths to produce fewer BBs. Consider this pseudocode:

A = alloca TYPE
B = alloca TYPE
C = alloca TYPE_WITH_DTOR

main:
  LT_START(C)

  if COND {
    LT_START(A)
    INVOKE func UNWIND cleanup_A
    LT_END(A)
  } else {
    LT_START(B)
    INVOKE func UNWIND cleanup_B
    LT_END(B)
  }

  DTOR(C)
  LT_END(C)

  RETURN

cleanup_A:
  LP
  LT_END(A)
  br cleanup;

cleanup_B:
  LP
  LT_END(B)
  br cleanup;

cleanup:
  DTOR(C)
  LT_END(C)
  RESUME

Here we need two distinct cleanup paths and landing pads just to ensure that
the old stack coloring code can merge slots A and B. But assuming that a
lifetime end on a dead slot is a no-op, we could also write:

A = alloca TYPE
B = alloca TYPE
C = alloca TYPE_WITH_DTOR

main:
  LT_START(C)

  if COND {
    LT_START(A)
    INVOKE func UNWIND cleanup_A
    LT_END(A)
  } else {
    LT_START(B)
    INVOKE func UNWIND cleanup_B
    LT_END(B)
  }

  DTOR(C)
  LT_END(C)

  RETURN

cleanup:
  LP
  LT_END(A)
  LT_END(B)
  DTOR(C)
  LT_END(C)
  RESUME

Now the problem is that both A and B are only "possibly live" coming into
"cleanup". "Possibly live" meaning that a slot is live on one but not
necessarily all incoming edges. Using a plain overlap check on the live
intervals created using this information causes false positives, stopping the
slots from being merged.

To solve this, we can use an alternative approach to check whether two slots
are live at the same time. For two slots to be live at the same time, one of
them needs to become live when the other is live as well. We can check this by
keeping track of the points at which a slot becomes live. As these points tell
us that a slot is "definitely" live, we get more accurate results.

I hope this explains the approach we've taken well enough.

[arielb1]

Ready and just waiting for review.

[arielb1]

rnk can you review this? This is stuck in the queue for almost a month.

[thanm]

In D31583#754945, @arielb1 wrote:

Ready and just waiting for review.

Thanks for the ping/reminder.

I read through Björn's April 17th comment. The explanation makes sense, but this is something that should be in the code as opposed to only in a Phab review. Please add something along these lines to the "Implementation Notes" command section -- that is where other material exists relating to how the data flow analysis works.

My existing comments regarding naming still stand (overloading of the terms "active" and naming of the BB set "Use").

Ditto on my previous comment regarding testing. I recommend running a clang/llvm bootstrap build to make sure you haven't broken anything. You can find instructions on how to do bootstrap builds at http://llvm.org/docs/AdvancedBuilds.html. This is purely an advisory suggestion, you are free to ignore it (I mention it mainly since when I made changes to stack coloring previously it was helpful in flushing out problems that I hadn't anticipated).

[arielb1]

Tests run locally.

[arielb1]

Updated comment.

[arielb1]

Works locally.

[arielb1]

Ping. I think the new comment is good enough to go.

[thanm]

I pulled your patch and did a bootstrap build with it, no issues. Overall this seems like an improvement over the initial patch. Please see inline comments.

lib/CodeGen/StackColoring.cpp

127

This is kind of a nit, but if I am reading this correctly, your use of "non-conservative" here refers to a slot that is not degenerate, which is not talked about until down on line 342. Maybe it would make sense to put in a forward reference?

646

I see "if (!IsStart && ..." -- seems like the "!IsStart" is redundant at this point, no?

1000

A couple of observations:

First, relative to your first patch I think I can make more more sense out of what's going on. I can also see where you're getting the improvement, since doing the conflict check based on starts is inherently more precise.

Second, there is a concern that in a large function with many packets overlapped together you could get into quadratic compile time behavior (since in the worst case the interval has O(N) items and the LiveStarts vector has O(N) items). If you haven't seen any issues in practice, though, I suppose it's probably not worrying too much about.

[arielb1]

Changed else/if nesting in that part.

I'm not too worried about any O(n^2) part - both the old and the new code do an O(# slots) * O(# slots) overlap check, and I don't remember it being a particularly expensive pass.

[arielb1]

Use "degenerate" in all comments.

[thanm]

LGTM.

FWIW I tried a self-build of clang with and without the change and looked at the -stats output to see what sort of improvement there is. Looks pretty modest (<1%) but it is positive overall.

lib/CodeGen/StackColoring.cpp

 //     slot 2: b5
 //
 // Achieving this allocation is tricky, however, due to the way
 // lifetime markers are inserted. Here is a simplified view of the
 // control flow graph for the code above:
 //
 //                +------  block 0 -------+
 //               0| LIFETIME_START b1, b2 |
 //               1| <test 'if' condition> |
 //                +-----------------------+
 //                   ./              \.
 //   +------  block 1 -------+   +------  block 2 -------+
 //  2| LIFETIME_START b3     |  5| LIFETIME_START b4, b5 |
 //  3| <uses of b1, b3>      |  6| <uses of b2, b4, b5>  |
 //  4| LIFETIME_END b3       |  7| LIFETIME_END b4, b5   |
 //   +-----------------------+   +-----------------------+
 //                   \.              /.

 // If in RPO ordering chosen to walk the CFG  we happen to visit the b[k]
 // before visiting the memcpy block (which will contain the lifetime start
 // for "b" then it will appear that 'b' has a degenerate lifetime.
 //
 
 //===----------------------------------------------------------------------===//
 //                           StackColoring Pass
 //===----------------------------------------------------------------------===//
-
+
 namespace {
-/// StackColoring - A machine pass for merging disjoint stack allocations,
-/// marked by the LIFETIME_START and LIFETIME_END pseudo instructions.
-class StackColoring : public MachineFunctionPass {
-  MachineFrameInfo *MFI;
-  MachineFunction *MF;
-
-  /// A class representing liveness information for a single basic block.
-  /// Each bit in the BitVector represents the liveness property
-  /// for a different stack slot.
-  struct BlockLifetimeInfo {
-    /// Which slots BEGINs in each basic block.
-    BitVector Begin;
-    /// Which slots ENDs in each basic block.
+/// StackColoring - A machine pass for merging disjoint stack allocations,
+/// marked by the LIFETIME_START and LIFETIME_END pseudo instructions.
+class StackColoring : public MachineFunctionPass {
+  MachineFrameInfo *MFI;
+  MachineFunction *MF;
+
+  /// A class representing liveness information for a single basic block.
+  /// Each bit in the BitVector represents the liveness property
+  /// for a different stack slot.
+  struct BlockLifetimeInfo {
+    /// Which slots BEGIN in this block and survive to its end.
+    BitVector Begin;
+    /// Which slots BEGIN and END in this block.
+    BitVector Use;
+    /// Which slots END in this block.
     BitVector End;
-    /// Which slots are marked as LIVE_IN, coming into each basic block.
-    BitVector LiveIn;
-    /// Which slots are marked as LIVE_OUT, coming out of each basic block.
-    BitVector LiveOut;
-  };
-
-  /// Maps active slots (per bit) for each basic block.
-  typedef DenseMap<const MachineBasicBlock*, BlockLifetimeInfo> LivenessMap;
-  LivenessMap BlockLiveness;
-
-  /// Maps serial numbers to basic blocks.
-  DenseMap<const MachineBasicBlock*, int> BasicBlocks;
-  /// Maps basic blocks to a serial number.
-  SmallVector<const MachineBasicBlock*, 8> BasicBlockNumbering;
-
-  /// Maps liveness intervals for each slot.
-  SmallVector<std::unique_ptr<LiveInterval>, 16> Intervals;
+    /// Which slots are marked as LIVE_IN, coming into this block.
+    BitVector LiveIn;
+    /// Which slots are marked as LIVE_OUT, coming out of this block.
+    BitVector LiveOut;
+  };
+
+  /// Maps active slots (per bit) for each basic block.
+  typedef DenseMap<const MachineBasicBlock*, BlockLifetimeInfo> LivenessMap;
+  LivenessMap BlockLiveness;
+
+  /// Maps serial numbers to basic blocks.
+  DenseMap<const MachineBasicBlock*, int> BasicBlocks;
+  /// Maps basic blocks to a serial number.
+  SmallVector<const MachineBasicBlock*, 8> BasicBlockNumbering;
+
+  /// Maps slots to their activity interval. Outside of this interval, slots
+  /// values are either dead or `undef` and they will not be written to.
+  SmallVector<std::unique_ptr<LiveInterval>, 16> Intervals;
+  /// Maps slots to the set of gen-points of their intervals.
+  SmallVector<std::unique_ptr<LiveInterval>, 16> IntervalStarts;
   /// VNInfo is used for the construction of LiveIntervals.
   VNInfo::Allocator VNInfoAllocator;
   /// SlotIndex analysis object.
   SlotIndexes *Indexes;
   /// The stack protector object.
   StackProtector *SP;
 
   /// The list of lifetime markers found. These markers are to be removed
private:
   /// This procedure checks all of the instructions in the function and
   /// invalidates lifetime ranges which do not contain all of the instructions
   /// which access that frame slot.
   void removeInvalidSlotRanges();
 
   /// Map entries which point to other entries to their destination.
   ///   A->B->C becomes A->C.
   void expungeSlotMap(DenseMap<int, int> &SlotRemap, unsigned NumSlots);
-
-  /// Used in collectMarkers
-  typedef DenseMap<const MachineBasicBlock*, BitVector> BlockBitVecMap;
-};
-} // end anonymous namespace
-
-char StackColoring::ID = 0;
-char &llvm::StackColoringID = StackColoring::ID;
-
-INITIALIZE_PASS_BEGIN(StackColoring,
-                   "stack-coloring", "Merge disjoint stack slots", false, false)
-INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
-INITIALIZE_PASS_DEPENDENCY(StackProtector)
-INITIALIZE_PASS_END(StackColoring,
-                   "stack-coloring", "Merge disjoint stack slots", false, false)
-
-void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.addRequired<SlotIndexes>();
-  AU.addRequired<StackProtector>();
-  MachineFunctionPass::getAnalysisUsage(AU);
-}
-
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-LLVM_DUMP_METHOD void StackColoring::dumpBV(const char *tag,
-                                            const BitVector &BV) const {
-  dbgs() << tag << " : { ";
-  for (unsigned I = 0, E = BV.size(); I != E; ++I)
-    dbgs() << BV.test(I) << " ";
-  dbgs() << "}\n";
-}
-
-LLVM_DUMP_METHOD void StackColoring::dumpBB(MachineBasicBlock *MBB) const {
-  LivenessMap::const_iterator BI = BlockLiveness.find(MBB);
-  assert(BI != BlockLiveness.end() && "Block not found");
-  const BlockLifetimeInfo &BlockInfo = BI->second;
-
-  dumpBV("BEGIN", BlockInfo.Begin);
-  dumpBV("END", BlockInfo.End);
-  dumpBV("LIVE_IN", BlockInfo.LiveIn);
-  dumpBV("LIVE_OUT", BlockInfo.LiveOut);
-}
-
-LLVM_DUMP_METHOD void StackColoring::dump() const {
-  for (MachineBasicBlock *MBB : depth_first(MF)) {
-    dbgs() << "Inspecting block #" << MBB->getNumber() << " ["
-           << MBB->getName() << "]\n";
-    dumpBB(MBB);
-  }
-}
-
-LLVM_DUMP_METHOD void StackColoring::dumpIntervals() const {
-  for (unsigned I = 0, E = Intervals.size(); I != E; ++I) {
-    dbgs() << "Interval[" << I << "]:\n";
-    Intervals[I]->dump();
+
+  /// Used in collectMarkers
+  typedef DenseMap<const MachineBasicBlock*, BitVector> BlockBitVecMap;
+};
+} // end anonymous namespace
+
+char StackColoring::ID = 0;
+char &llvm::StackColoringID = StackColoring::ID;
+
+INITIALIZE_PASS_BEGIN(StackColoring,
+                   "stack-coloring", "Merge disjoint stack slots", false, false)
+INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
+INITIALIZE_PASS_DEPENDENCY(StackProtector)
+INITIALIZE_PASS_END(StackColoring,
+                   "stack-coloring", "Merge disjoint stack slots", false, false)
+
+void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<SlotIndexes>();
+  AU.addRequired<StackProtector>();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+LLVM_DUMP_METHOD void StackColoring::dumpBV(const char *tag,
+                                            const BitVector &BV) const {
+  dbgs() << tag << " : { ";
+  for (unsigned I = 0, E = BV.size(); I != E; ++I)
+    dbgs() << BV.test(I) << " ";
+  dbgs() << "}\n";
+}
+
+LLVM_DUMP_METHOD void StackColoring::dumpBB(MachineBasicBlock *MBB) const {
+  LivenessMap::const_iterator BI = BlockLiveness.find(MBB);
+  assert(BI != BlockLiveness.end() && "Block not found");
+  const BlockLifetimeInfo &BlockInfo = BI->second;
+
+  dumpBV("BEGIN", BlockInfo.Begin);
+  dumpBV("USE", BlockInfo.Use);
+  dumpBV("END", BlockInfo.End);
+  dumpBV("LIVE_IN", BlockInfo.LiveIn);
+  dumpBV("LIVE_OUT", BlockInfo.LiveOut);
+}
+
+LLVM_DUMP_METHOD void StackColoring::dump() const {
+  for (MachineBasicBlock *MBB : depth_first(MF)) {
+    dbgs() << "Inspecting block #" << MBB->getNumber() << " ["
+           << MBB->getName() << "]\n";
+    dumpBB(MBB);
+  }
+}
+
+LLVM_DUMP_METHOD void StackColoring::dumpIntervals() const {
+  for (unsigned I = 0, E = Intervals.size(); I != E; ++I) {
+    dbgs() << "Interval[" << I << "]:\n";
+    Intervals[I]->dump();
+    dbgs() << "IntervalStarts[" << I << "]:\n";
+    IntervalStarts[I]->dump();
   }
 }
 #endif
 
 static inline int getStartOrEndSlot(const MachineInstr &MI)
 {
   assert((MI.getOpcode() == TargetOpcode::LIFETIME_START ||
           MI.getOpcode() == TargetOpcode::LIFETIME_END) &&
for (MachineInstr &MI : *MBB) {
         if (MI.getOpcode() == TargetOpcode::LIFETIME_START) {
           BetweenStartEnd.set(Slot);
           NumStartLifetimes[Slot] += 1;
         } else {
           BetweenStartEnd.reset(Slot);
           NumEndLifetimes[Slot] += 1;
         }
         const AllocaInst *Allocation = MFI->getObjectAllocation(Slot);
-        if (Allocation) {
-          DEBUG(dbgs() << "Found a lifetime ");
-          DEBUG(dbgs() << (MI.getOpcode() == TargetOpcode::LIFETIME_START
-                               ? "start"
-                               : "end"));
-          DEBUG(dbgs() << " marker for slot #" << Slot);
-          DEBUG(dbgs() << " with allocation: " << Allocation->getName()
-                       << "\n");
-        }
-        Markers.push_back(&MI);
-        MarkersFound += 1;
-      } else {
-        for (const MachineOperand &MO : MI.operands()) {
-          if (!MO.isFI())
-            continue;
-          int Slot = MO.getIndex();
-          if (Slot < 0)
-            continue;
-          if (! BetweenStartEnd.test(Slot)) {
-            ConservativeSlots.set(Slot);
-          }
-        }
-      }
-    }
-    BitVector &SeenStart = SeenStartMap[MBB];
-    SeenStart |= BetweenStartEnd;
-  }
-  if (!MarkersFound) {
-    return 0;
-  }
-
-  // PR27903: slots with multiple start or end lifetime ops are not
-  // safe to enable for "lifetime-start-on-first-use".
-  for (unsigned slot = 0; slot < NumSlot; ++slot)
-    if (NumStartLifetimes[slot] > 1 || NumEndLifetimes[slot] > 1)
-      ConservativeSlots.set(slot);
-  DEBUG(dumpBV("Conservative slots", ConservativeSlots));
-
-  // Step 2: compute begin/end sets for each block
-
-  // NOTE: We use a depth-first iteration to ensure that we obtain a
-  // deterministic numbering.
-  for (MachineBasicBlock *MBB : depth_first(MF)) {
-
-    // Assign a serial number to this basic block.
-    BasicBlocks[MBB] = BasicBlockNumbering.size();
-    BasicBlockNumbering.push_back(MBB);
-
-    // Keep a reference to avoid repeated lookups.
-    BlockLifetimeInfo &BlockInfo = BlockLiveness[MBB];
-
-    BlockInfo.Begin.resize(NumSlot);
-    BlockInfo.End.resize(NumSlot);
-
-    SmallVector<int, 4> slots;
-    for (MachineInstr &MI : *MBB) {
-      bool isStart = false;
-      slots.clear();
-      if (isLifetimeStartOrEnd(MI, slots, isStart)) {
-        if (!isStart) {
-          assert(slots.size() == 1 && "unexpected: MI ends multiple slots");
-          int Slot = slots[0];
-          if (BlockInfo.Begin.test(Slot)) {
-            BlockInfo.Begin.reset(Slot);
-          }
-          BlockInfo.End.set(Slot);
-        } else {
-          for (auto Slot : slots) {
-            DEBUG(dbgs() << "Found a use of slot #" << Slot);
-            DEBUG(dbgs() << " at BB#" << MBB->getNumber() << " index ");
-            DEBUG(Indexes->getInstructionIndex(MI).print(dbgs()));
-            const AllocaInst *Allocation = MFI->getObjectAllocation(Slot);
-            if (Allocation) {
-              DEBUG(dbgs() << " with allocation: "<< Allocation->getName());
-            }
-            DEBUG(dbgs() << "\n");
-            if (BlockInfo.End.test(Slot)) {
-              BlockInfo.End.reset(Slot);
+        if (Allocation) {
+          DEBUG(dbgs() << "Found a lifetime ");
+          DEBUG(dbgs() << (MI.getOpcode() == TargetOpcode::LIFETIME_START
+                               ? "start"
+                               : "end"));
+          DEBUG(dbgs() << " marker for slot #" << Slot);
+          DEBUG(dbgs() << " with allocation: " << Allocation->getName()
+                       << "\n");
+        }
+        Markers.push_back(&MI);
+        MarkersFound += 1;
+      } else {
+        for (const MachineOperand &MO : MI.operands()) {
+          if (!MO.isFI())
+            continue;
+          int Slot = MO.getIndex();
+          if (Slot < 0)
+            continue;
+          if (! BetweenStartEnd.test(Slot)) {
+            ConservativeSlots.set(Slot);
+          }
+        }
+    BitVector &SeenStart = SeenStartMap[MBB];
+    SeenStart |= BetweenStartEnd;
+  }
+  if (!MarkersFound) {
+    return 0;
+  }
+
+  // PR27903: slots with multiple start or end lifetime ops are not
+  // safe to enable for "lifetime-start-on-first-use".
+  for (unsigned slot = 0; slot < NumSlot; ++slot)
+    if (NumStartLifetimes[slot] > 1 || NumEndLifetimes[slot] > 1)
+      ConservativeSlots.set(slot);
+  DEBUG(dumpBV("Conservative slots", ConservativeSlots));
+
+  // Step 2: compute begin/end sets for each block
+
+  // NOTE: We use a depth-first iteration to ensure that we obtain a
+  // deterministic numbering.
+  for (MachineBasicBlock *MBB : depth_first(MF)) {
+
+    // Assign a serial number to this basic block.
+    BasicBlocks[MBB] = BasicBlockNumbering.size();
+    BasicBlockNumbering.push_back(MBB);
+
+    // Keep a reference to avoid repeated lookups.
+    BlockLifetimeInfo &BlockInfo = BlockLiveness[MBB];
+
+    BlockInfo.Begin.resize(NumSlot);
+    BlockInfo.Use.resize(NumSlot);
+    BlockInfo.End.resize(NumSlot);
+
+    SmallVector<int, 4> slots;
+    for (MachineInstr &MI : *MBB) {
+      bool isStart = false;
+      slots.clear();
+      if (isLifetimeStartOrEnd(MI, slots, isStart)) {
+        if (!isStart) {
+          assert(slots.size() == 1 && "unexpected: MI ends multiple slots");
+          int Slot = slots[0];
+          if (BlockInfo.Begin.test(Slot)) {
+            BlockInfo.Begin.reset(Slot);
+            BlockInfo.Use.set(Slot);
+          }
+          BlockInfo.End.set(Slot);
+        } else {
+          for (auto Slot : slots) {
+            DEBUG(dbgs() << "Found a use of slot #" << Slot);
+            DEBUG(dbgs() << " at BB#" << MBB->getNumber() << " index ");
+            DEBUG(Indexes->getInstructionIndex(MI).print(dbgs()));
+            const AllocaInst *Allocation = MFI->getObjectAllocation(Slot);
+            if (Allocation) {
+              DEBUG(dbgs() << " with allocation: "<< Allocation->getName());
+            }
+            DEBUG(dbgs() << "\n");
+            if (BlockInfo.End.test(Slot)) {
+              BlockInfo.End.reset(Slot);
+            }
+            if (BlockInfo.Use.test(Slot)) {
+              BlockInfo.Use.reset(Slot);
             }
             BlockInfo.Begin.set(Slot);
           }
         }
       }
     }
   }
 
void StackColoring::calculateLocalLiveness()
   while (changed) {
     changed = false;
     ++NumIters;
 
     for (const MachineBasicBlock *BB : BasicBlockNumbering) {
 
       // Use an iterator to avoid repeated lookups.
       LivenessMap::iterator BI = BlockLiveness.find(BB);
       assert(BI != BlockLiveness.end() && "Block not found");
       BlockLifetimeInfo &BlockInfo = BI->second;
 
       // Compute LiveIn by unioning together the LiveOut sets of all preds.
       BitVector LocalLiveIn;
       for (MachineBasicBlock::const_pred_iterator PI = BB->pred_begin(),
            PE = BB->pred_end(); PI != PE; ++PI) {
         LivenessMap::const_iterator I = BlockLiveness.find(*PI);
         assert(I != BlockLiveness.end() && "Predecessor not found");
while (changed) {
     }
   }// while changed.
 
   NumIterations = NumIters;
 }
 
 void StackColoring::calculateLiveIntervals(unsigned NumSlots) {
   SmallVector<SlotIndex, 16> Starts;
-  SmallVector<SlotIndex, 16> Finishes;
-
-  // For each block, find which slots are active within this block
-  // and update the live intervals.
-  for (const MachineBasicBlock &MBB : *MF) {
-    Starts.clear();
-    Starts.resize(NumSlots);
-    Finishes.clear();
-    Finishes.resize(NumSlots);
-
-    // Create the interval for the basic blocks containing lifetime begin/end.
-    for (const MachineInstr &MI : MBB) {
-
-      SmallVector<int, 4> slots;
-      bool IsStart = false;
-      if (!isLifetimeStartOrEnd(MI, slots, IsStart))
-        continue;
-      SlotIndex ThisIndex = Indexes->getInstructionIndex(MI);
-      for (auto Slot : slots) {
-        if (IsStart) {
-          if (!Starts[Slot].isValid() || Starts[Slot] > ThisIndex)
-            Starts[Slot] = ThisIndex;
-        } else {
-          if (!Finishes[Slot].isValid() || Finishes[Slot] < ThisIndex)
-            Finishes[Slot] = ThisIndex;
-        }
-      }
-    }
-
-    // Create the interval of the blocks that we previously found to be 'alive'.
-    BlockLifetimeInfo &MBBLiveness = BlockLiveness[&MBB];
-    for (int pos = MBBLiveness.LiveIn.find_first(); pos != -1;
-         pos = MBBLiveness.LiveIn.find_next(pos)) {
-      Starts[pos] = Indexes->getMBBStartIdx(&MBB);
-    }
-    for (int pos = MBBLiveness.LiveOut.find_first(); pos != -1;
-         pos = MBBLiveness.LiveOut.find_next(pos)) {
-      Finishes[pos] = Indexes->getMBBEndIdx(&MBB);
-    }
-
-    for (unsigned i = 0; i < NumSlots; ++i) {
-      //
-      // When LifetimeStartOnFirstUse is turned on, data flow analysis
-      // is forward (from starts to ends), not bidirectional. A
-      // consequence of this is that we can wind up in situations
-      // where Starts[i] is invalid but Finishes[i] is valid and vice
-      // versa. Example:
-      //
-      //     LIFETIME_START x
-      //     if (...) {
-      //       <use of x>
-      //       throw ...;
-      //     }
-      //     LIFETIME_END x
-      //     return 2;
-      //
-      //
-      // Here the slot for "x" will not be live into the block
-      // containing the "return 2" (since lifetimes start with first
-      // use, not at the dominating LIFETIME_START marker).
-      //
-      if (Starts[i].isValid() && !Finishes[i].isValid()) {
-        Finishes[i] = Indexes->getMBBEndIdx(&MBB);
-      }
-      if (!Starts[i].isValid())
-        continue;
-
-      assert(Starts[i] && Finishes[i] && "Invalid interval");
-      VNInfo *ValNum = Intervals[i]->getValNumInfo(0);
-      SlotIndex S = Starts[i];
-      SlotIndex F = Finishes[i];
-      if (S < F) {
-        // We have a single consecutive region.
-        Intervals[i]->addSegment(LiveInterval::Segment(S, F, ValNum));
-      } else {
-        // We have two non-consecutive regions. This happens when
-        // LIFETIME_START appears after the LIFETIME_END marker.
-        SlotIndex NewStart = Indexes->getMBBStartIdx(&MBB);
-        SlotIndex NewFin = Indexes->getMBBEndIdx(&MBB);
-        Intervals[i]->addSegment(LiveInterval::Segment(NewStart, F, ValNum));
-        Intervals[i]->addSegment(LiveInterval::Segment(S, NewFin, ValNum));
+  SmallVector<SlotIndex, 16> Finishes;
+
+  // For each block, find which slots are active within this block
+  // and update the live intervals.
+  for (const MachineBasicBlock &MBB : *MF) {
+    Starts.clear();
+    Starts.resize(NumSlots);
+    Finishes.clear();
+    Finishes.resize(NumSlots);
+
+    // Create the interval for the basic blocks containing lifetime begin/end.
+    for (const MachineInstr &MI : MBB) {
+
+      SmallVector<int, 4> slots;
+      bool IsStart = false;
+      if (!isLifetimeStartOrEnd(MI, slots, IsStart))
+        continue;
+      SlotIndex ThisIndex = Indexes->getInstructionIndex(MI);
+      for (auto Slot : slots) {
+        if (IsStart) {
+          if (!Starts[Slot].isValid() || Starts[Slot] > ThisIndex)
+            Starts[Slot] = ThisIndex;
+        } else {
+          if (!Finishes[Slot].isValid() || Finishes[Slot] < ThisIndex)
+            Finishes[Slot] = ThisIndex;
+        }
+      }
+    }
+
+    // Create the interval of the blocks that we previously found to be 'alive'.
+    BlockLifetimeInfo &MBBLiveness = BlockLiveness[&MBB];
+    for (int pos = MBBLiveness.LiveIn.find_first(); pos != -1;
+         pos = MBBLiveness.LiveIn.find_next(pos)) {
+      Starts[pos] = Indexes->getMBBStartIdx(&MBB);
+    }
+    for (int pos = MBBLiveness.LiveOut.find_first(); pos != -1;
+         pos = MBBLiveness.LiveOut.find_next(pos)) {
+      Finishes[pos] = Indexes->getMBBEndIdx(&MBB);
+    }
+
+    for (unsigned i = 0; i < NumSlots; ++i) {
+      //
+      // When LifetimeStartOnFirstUse is turned on, data flow analysis
+      // is forward (from starts to ends), not bidirectional. A
+      // consequence of this is that we can wind up in situations
+      // where Starts[i] is invalid but Finishes[i] is valid and vice
+      // versa. Example:
+      //
+      //     LIFETIME_START x
+      //     if (...) {
+      //       <use of x>
+      //       throw ...;
+      //     }
+      //     LIFETIME_END x
+      //     return 2;
+      //
+      //
+      // Here the slot for "x" will not be live into the block
+      // containing the "return 2" (since lifetimes start with first
+      // use, not at the dominating LIFETIME_START marker).
+      //
+      if (Starts[i].isValid() && !Finishes[i].isValid()) {
+        Finishes[i] = Indexes->getMBBEndIdx(&MBB);
+      }
+      if (!Starts[i].isValid())
+        continue;
+
+      assert(Starts[i] && Finishes[i] && "Invalid interval");
+      VNInfo *ValNum = Intervals[i]->getValNumInfo(0);
+      VNInfo *ValNumS = IntervalStarts[i]->getValNumInfo(0);
+      SlotIndex S = Starts[i];
+      SlotIndex F = Finishes[i];
+      if (S < F) {
+        // We have a single consecutive region.
+        Intervals[i]->addSegment(LiveInterval::Segment(S, F, ValNum));
+        // FIXME: stop cargo culting
+        if (MBBLiveness.Begin.test(i) || MBBLiveness.Use.test(i)) {
+          IntervalStarts[i]->addSegment(LiveInterval::Segment(S, F, ValNumS));
+        }
+      } else {
+        // We have two non-consecutive regions. This happens when
+        // LIFETIME_START appears after the LIFETIME_END marker.
+        SlotIndex NewStart = Indexes->getMBBStartIdx(&MBB);
+        SlotIndex NewFin = Indexes->getMBBEndIdx(&MBB);
+        Intervals[i]->addSegment(LiveInterval::Segment(NewStart, F, ValNum));
+        Intervals[i]->addSegment(LiveInterval::Segment(S, NewFin, ValNum));
+        // FIXME: stop cargo culting
+        if (MBBLiveness.Begin.test(i) || MBBLiveness.Use.test(i)) {
+          IntervalStarts[i]->addSegment(LiveInterval::Segment(NewStart, F, ValNumS));
+          IntervalStarts[i]->addSegment(LiveInterval::Segment(S, NewFin, ValNumS));
+        }
       }
     }
   }
 }
 
 bool StackColoring::removeAllMarkers() {
   unsigned Count = 0;
   for (MachineInstr *MI : Markers) {
for (MachineInstr &I : BB) {
         // outside of the lifetime markers, or that the user has a bug.
         // NOTE: Alloca address calculations which happen outside the lifetime
         // zone are are okay, despite the fact that we don't have a good way
         // for validating all of the usages of the calculation.
 #ifndef NDEBUG
         bool TouchesMemory = I.mayLoad() || I.mayStore();
         // If we *don't* protect the user from escaped allocas, don't bother
         // validating the instructions.
-        if (!I.isDebugValue() && TouchesMemory && ProtectFromEscapedAllocas) {
-          SlotIndex Index = Indexes->getInstructionIndex(I);
-          const LiveInterval *Interval = &*Intervals[FromSlot];
-          assert(Interval->find(Index) != Interval->end() &&
-                 "Found instruction usage outside of live range.");
-        }
-#endif
-
-        // Fix the machine instructions.
-        int ToSlot = SlotRemap[FromSlot];
-        MO.setIndex(ToSlot);
-        FixedInstr++;
-      }
-    }
-
-  // Update the location of C++ catch objects for the MSVC personality routine.
-  if (WinEHFuncInfo *EHInfo = MF->getWinEHFuncInfo())
-    for (WinEHTryBlockMapEntry &TBME : EHInfo->TryBlockMap)
-      for (WinEHHandlerType &H : TBME.HandlerArray)
-        if (H.CatchObj.FrameIndex != INT_MAX &&
-            SlotRemap.count(H.CatchObj.FrameIndex))
-          H.CatchObj.FrameIndex = SlotRemap[H.CatchObj.FrameIndex];
-
-  DEBUG(dbgs()<<"Fixed "<<FixedMemOp<<" machine memory operands.\n");
-  DEBUG(dbgs()<<"Fixed "<<FixedDbg<<" debug locations.\n");
-  DEBUG(dbgs()<<"Fixed "<<FixedInstr<<" machine instructions.\n");
-}
-
-void StackColoring::removeInvalidSlotRanges() {
-  for (MachineBasicBlock &BB : *MF)
-    for (MachineInstr &I : BB) {
-      if (I.getOpcode() == TargetOpcode::LIFETIME_START ||
-          I.getOpcode() == TargetOpcode::LIFETIME_END || I.isDebugValue())
-        continue;
-
-      // Some intervals are suspicious! In some cases we find address
-      // calculations outside of the lifetime zone, but not actual memory
-      // read or write. Memory accesses outside of the lifetime zone are a clear
-      // violation, but address calculations are okay. This can happen when
-      // GEPs are hoisted outside of the lifetime zone.
-      // So, in here we only check instructions which can read or write memory.
-      if (!I.mayLoad() && !I.mayStore())
-        continue;
+        if (!I.isDebugValue() && TouchesMemory && ProtectFromEscapedAllocas) {
+          SlotIndex Index = Indexes->getInstructionIndex(I);
+          const LiveInterval *Interval = &*Intervals[FromSlot];
+          assert(Interval->find(Index) != Interval->end() &&
+                 "Found instruction usage outside of live range.");
+        }
+#endif
+
+        // Fix the machine instructions.
+        int ToSlot = SlotRemap[FromSlot];
+        MO.setIndex(ToSlot);
+        FixedInstr++;
+      }
+
+  // Update the location of C++ catch objects for the MSVC personality routine.
+  if (WinEHFuncInfo *EHInfo = MF->getWinEHFuncInfo())
+    for (WinEHTryBlockMapEntry &TBME : EHInfo->TryBlockMap)
+      for (WinEHHandlerType &H : TBME.HandlerArray)
+        if (H.CatchObj.FrameIndex != INT_MAX &&
+            SlotRemap.count(H.CatchObj.FrameIndex))
+          H.CatchObj.FrameIndex = SlotRemap[H.CatchObj.FrameIndex];
+
+  DEBUG(dbgs()<<"Fixed "<<FixedMemOp<<" machine memory operands.\n");
+  DEBUG(dbgs()<<"Fixed "<<FixedDbg<<" debug locations.\n");
+  DEBUG(dbgs()<<"Fixed "<<FixedInstr<<" machine instructions.\n");
+}
+
+void StackColoring::removeInvalidSlotRanges() {
+  for (MachineBasicBlock &BB : *MF)
+    for (MachineInstr &I : BB) {
+      if (I.getOpcode() == TargetOpcode::LIFETIME_START ||
+          I.getOpcode() == TargetOpcode::LIFETIME_END || I.isDebugValue())
+        continue;
+
+      // Some intervals are suspicious! In some cases we find address
+      // calculations outside of the lifetime zone, but not actual memory
+      // read or write. Memory accesses outside of the lifetime zone are a clear
+      // violation, but address calculations are okay. This can happen when
+      // GEPs are hoisted outside of the lifetime zone.
+      // So, in here we only check instructions which can read or write memory.
+      if (!I.mayLoad() && !I.mayStore())
+        continue;
+
+      // Check all of the machine operands.
+      for (const MachineOperand &MO : I.operands()) {
+        if (!MO.isFI())
+          continue;
+
+        int Slot = MO.getIndex();
 
-      // Check all of the machine operands.
-      for (const MachineOperand &MO : I.operands()) {
-        if (!MO.isFI())
-          continue;
-
-        int Slot = MO.getIndex();
-
-        if (Slot<0)
-          continue;
-
-        if (Intervals[Slot]->empty())
-          continue;
-
-        // Check that the used slot is inside the calculated lifetime range.
-        // If it is not, warn about it and invalidate the range.
-        LiveInterval *Interval = &*Intervals[Slot];
-        SlotIndex Index = Indexes->getInstructionIndex(I);
-        if (Interval->find(Index) == Interval->end()) {
-          Interval->clear();
-          DEBUG(dbgs()<<"Invalidating range #"<<Slot<<"\n");
-          EscapedAllocas++;
-        }
-      }
-    }
-}
-
-void StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap,
-                                   unsigned NumSlots) {
-  // Expunge slot remap map.
-  for (unsigned i=0; i < NumSlots; ++i) {
-    // If we are remapping i
-    if (SlotRemap.count(i)) {
-      int Target = SlotRemap[i];
-      // As long as our target is mapped to something else, follow it.
-      while (SlotRemap.count(Target)) {
-        Target = SlotRemap[Target];
-        SlotRemap[i] = Target;
-      }
-    }
-  }
-}
+        if (Slot<0)
+          continue;
+
+        if (Intervals[Slot]->empty())
+          continue;
+
+        // Check that the used slot is inside the calculated lifetime range.
+        // If it is not, warn about it and invalidate the range.
+        LiveInterval *Interval = &*Intervals[Slot];
+        SlotIndex Index = Indexes->getInstructionIndex(I);
+        if (Interval->find(Index) == Interval->end()) {
+          Interval->clear();
+          DEBUG(dbgs()<<"Invalidating range #"<<Slot<<"\n");
+          EscapedAllocas++;
+        }
+      }
+    }
+}
+
+void StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap,
+                                   unsigned NumSlots) {
+  // Expunge slot remap map.
+  for (unsigned i=0; i < NumSlots; ++i) {
+    // If we are remapping i
+    if (SlotRemap.count(i)) {
+      int Target = SlotRemap[i];
+      // As long as our target is mapped to something else, follow it.
+      while (SlotRemap.count(Target)) {
+        Target = SlotRemap[Target];
+        SlotRemap[i] = Target;
+      }
+    }
+  }
+}
+
+bool StackColoring::runOnMachineFunction(MachineFunction &Func) {
+  DEBUG(dbgs() << "********** Stack Coloring **********\n"
+               << "********** Function: "
+               << ((const Value*)Func.getFunction())->getName() << '\n');
+  MF = &Func;
+  MFI = &MF->getFrameInfo();
+  Indexes = &getAnalysis<SlotIndexes>();
+  SP = &getAnalysis<StackProtector>();
+  BlockLiveness.clear();
+  BasicBlocks.clear();
+  BasicBlockNumbering.clear();
+  Markers.clear();
+  Intervals.clear();
+  IntervalStarts.clear();
+  VNInfoAllocator.Reset();
+
+  unsigned NumSlots = MFI->getObjectIndexEnd();
+
+  // If there are no stack slots then there are no markers to remove.
+  if (!NumSlots)
+    return false;
+
+  SmallVector<int, 8> SortedSlots;
+  SortedSlots.reserve(NumSlots);
+  Intervals.reserve(NumSlots);
+
+  unsigned NumMarkers = collectMarkers(NumSlots);
+
+  unsigned TotalSize = 0;
+  DEBUG(dbgs()<<"Found "<<NumMarkers<<" markers and "<<NumSlots<<" slots\n");
+  DEBUG(dbgs()<<"Slot structure:\n");
+
+  for (int i=0; i < MFI->getObjectIndexEnd(); ++i) {
+    DEBUG(dbgs()<<"Slot #"<<i<<" - "<<MFI->getObjectSize(i)<<" bytes.\n");
+    TotalSize += MFI->getObjectSize(i);
+  }
+
+  DEBUG(dbgs()<<"Total Stack size: "<<TotalSize<<" bytes\n\n");
+
+  // Don't continue because there are not enough lifetime markers, or the
+  // stack is too small, or we are told not to optimize the slots.
+  if (NumMarkers < 2 || TotalSize < 16 || DisableColoring ||
+      skipFunction(*Func.getFunction())) {
+    DEBUG(dbgs()<<"Will not try to merge slots.\n");
+    return removeAllMarkers();
+  }
+
+  for (unsigned i=0; i < NumSlots; ++i) {
+    std::unique_ptr<LiveInterval> LI(new LiveInterval(i, 0));
+    LI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator);
+    Intervals.push_back(std::move(LI));
+
+    // Just cargo culting. Please help me DTRT.
+    std::unique_ptr<LiveInterval> SI(new LiveInterval(i, 0));
+    SI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator);
+    IntervalStarts.push_back(std::move(SI));
+
+    SortedSlots.push_back(i);
+  }
+
+  // Calculate the liveness of each block.
+  calculateLocalLiveness();
+  DEBUG(dbgs() << "Dataflow iterations: " << NumIterations << "\n");
+  DEBUG(dump());
 
-bool StackColoring::runOnMachineFunction(MachineFunction &Func) {
-  DEBUG(dbgs() << "********** Stack Coloring **********\n"
-               << "********** Function: "
-               << ((const Value*)Func.getFunction())->getName() << '\n');
-  MF = &Func;
-  MFI = &MF->getFrameInfo();
-  Indexes = &getAnalysis<SlotIndexes>();
-  SP = &getAnalysis<StackProtector>();
-  BlockLiveness.clear();
-  BasicBlocks.clear();
-  BasicBlockNumbering.clear();
-  Markers.clear();
-  Intervals.clear();
-  VNInfoAllocator.Reset();
-
-  unsigned NumSlots = MFI->getObjectIndexEnd();
-
-  // If there are no stack slots then there are no markers to remove.
-  if (!NumSlots)
-    return false;
-
-  SmallVector<int, 8> SortedSlots;
-  SortedSlots.reserve(NumSlots);
-  Intervals.reserve(NumSlots);
-
-  unsigned NumMarkers = collectMarkers(NumSlots);
-
-  unsigned TotalSize = 0;
-  DEBUG(dbgs()<<"Found "<<NumMarkers<<" markers and "<<NumSlots<<" slots\n");
-  DEBUG(dbgs()<<"Slot structure:\n");
-
-  for (int i=0; i < MFI->getObjectIndexEnd(); ++i) {
-    DEBUG(dbgs()<<"Slot #"<<i<<" - "<<MFI->getObjectSize(i)<<" bytes.\n");
-    TotalSize += MFI->getObjectSize(i);
-  }
-
-  DEBUG(dbgs()<<"Total Stack size: "<<TotalSize<<" bytes\n\n");
-
-  // Don't continue because there are not enough lifetime markers, or the
-  // stack is too small, or we are told not to optimize the slots.
-  if (NumMarkers < 2 || TotalSize < 16 || DisableColoring ||
-      skipFunction(*Func.getFunction())) {
-    DEBUG(dbgs()<<"Will not try to merge slots.\n");
-    return removeAllMarkers();
-  }
-
-  for (unsigned i=0; i < NumSlots; ++i) {
-    std::unique_ptr<LiveInterval> LI(new LiveInterval(i, 0));
-    LI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator);
-    Intervals.push_back(std::move(LI));
-    SortedSlots.push_back(i);
-  }
-
-  // Calculate the liveness of each block.
-  calculateLocalLiveness();
-  DEBUG(dbgs() << "Dataflow iterations: " << NumIterations << "\n");
-  DEBUG(dump());
-
-  // Propagate the liveness information.
-  calculateLiveIntervals(NumSlots);
-  DEBUG(dumpIntervals());
-
-  // Search for allocas which are used outside of the declared lifetime
-  // markers.
-  if (ProtectFromEscapedAllocas)
-    removeInvalidSlotRanges();
-
-  // Maps old slots to new slots.
-  DenseMap<int, int> SlotRemap;
-  unsigned RemovedSlots = 0;
-  unsigned ReducedSize = 0;
-
-  // Do not bother looking at empty intervals.
-  for (unsigned I = 0; I < NumSlots; ++I) {
-    if (Intervals[SortedSlots[I]]->empty())
-      SortedSlots[I] = -1;
-  }
-
-  // This is a simple greedy algorithm for merging allocas. First, sort the
-  // slots, placing the largest slots first. Next, perform an n^2 scan and look
-  // for disjoint slots. When you find disjoint slots, merge the samller one
-  // into the bigger one and update the live interval. Remove the small alloca
-  // and continue.
-
-  // Sort the slots according to their size. Place unused slots at the end.
-  // Use stable sort to guarantee deterministic code generation.
-  std::stable_sort(SortedSlots.begin(), SortedSlots.end(),
-                   [this](int LHS, int RHS) {
-    // We use -1 to denote a uninteresting slot. Place these slots at the end.
-    if (LHS == -1) return false;
-    if (RHS == -1) return true;
-    // Sort according to size.
-    return MFI->getObjectSize(LHS) > MFI->getObjectSize(RHS);
-  });
-
-  bool Changed = true;
-  while (Changed) {
-    Changed = false;
-    for (unsigned I = 0; I < NumSlots; ++I) {
-      if (SortedSlots[I] == -1)
-        continue;
-
-      for (unsigned J=I+1; J < NumSlots; ++J) {
-        if (SortedSlots[J] == -1)
-          continue;
-
-        int FirstSlot = SortedSlots[I];
-        int SecondSlot = SortedSlots[J];
-        LiveInterval *First = &*Intervals[FirstSlot];
-        LiveInterval *Second = &*Intervals[SecondSlot];
-        assert (!First->empty() && !Second->empty() && "Found an empty range");
-
-        // Merge disjoint slots.
-        if (!First->overlaps(*Second)) {
-          Changed = true;
-          First->MergeSegmentsInAsValue(*Second, First->getValNumInfo(0));
+  // Propagate the liveness information.
+  calculateLiveIntervals(NumSlots);
+  DEBUG(dumpIntervals());
+
+  // Search for allocas which are used outside of the declared lifetime
+  // markers.
+  if (ProtectFromEscapedAllocas)
+    removeInvalidSlotRanges();
+
+  // Maps old slots to new slots.
+  DenseMap<int, int> SlotRemap;
+  unsigned RemovedSlots = 0;
+  unsigned ReducedSize = 0;
+
+  // Do not bother looking at empty intervals.
+  for (unsigned I = 0; I < NumSlots; ++I) {
+    if (Intervals[SortedSlots[I]]->empty())
+      SortedSlots[I] = -1;
+  }
+
+  // This is a simple greedy algorithm for merging allocas. First, sort the
+  // slots, placing the largest slots first. Next, perform an n^2 scan and look
+  // for disjoint slots. When you find disjoint slots, merge the samller one
+  // into the bigger one and update the live interval. Remove the small alloca
+  // and continue.
+
+  // Sort the slots according to their size. Place unused slots at the end.
+  // Use stable sort to guarantee deterministic code generation.
+  std::stable_sort(SortedSlots.begin(), SortedSlots.end(),
+                   [this](int LHS, int RHS) {
+    // We use -1 to denote a uninteresting slot. Place these slots at the end.
+    if (LHS == -1) return false;
+    if (RHS == -1) return true;
+    // Sort according to size.
+    return MFI->getObjectSize(LHS) > MFI->getObjectSize(RHS);
+  });
+
+  bool Changed = true;
+  while (Changed) {
+    Changed = false;
+    for (unsigned I = 0; I < NumSlots; ++I) {
+      if (SortedSlots[I] == -1)
+        continue;
+
+      for (unsigned J=I+1; J < NumSlots; ++J) {
+        if (SortedSlots[J] == -1)
+          continue;
+
+        int FirstSlot = SortedSlots[I];
+        int SecondSlot = SortedSlots[J];
+        LiveInterval *First = &*Intervals[FirstSlot];
+        LiveInterval *FirstS = &*IntervalStarts[FirstSlot];
+        LiveInterval *Second = &*Intervals[SecondSlot];
+        LiveInterval *SecondS = &*IntervalStarts[SecondSlot];
+        assert (!First->empty() && !Second->empty() && "Found an empty range");
+
+        // Merge disjoint slots. Now, the condition for this is a little bit
+  // tricky.
+        //
+        // The fundamental condition we want to preserve is that each stack
+        // slot has the correct contents at each point it is live.
+        //
+        // We *could* compute liveness using the standard backward dataflow
+        // algorithm. Unfortunately, that does not give very good results in the
+        // presence of aliasing, so we have frontends emit `lifetime.start` and
+        // `lifetime.end` intrinsics that make undesirable accesses UB.
+        //
+        // The effect of these intrinsics is as follows:
+        //   1) at start, each stack-slot is marked as *out-of-scope*, unless no
+        //   lifetime intrinsic refers to that stack slot, in which case
+        //   it is marked as *in-scope*.
+        //   2) on a `lifetime.start`, a stack slot is marked as *in-scope* and
+        //   the stack slot is overwritten with `undef`.
+        //   3) on a `lifetime.end`, a stack slot is marked as *out-of-scope*.
+        //   4) on function exit, all stack slots are marked as *out-of-scope*.
+        //   5) the effects of calling `lifetime.start` on an *in-scope* stack-slot,
+        //   or `lifetime.end` on an *out-of-scope* stack-slot, are left unspecified.
+        //   6) memory accesses to *out-of-scope* stack slots are UB.
+        //   7) when a stack-slot is marked as *out-of-scope*, all pointers to it
+        //   are invalidated unless it looks like they might be used (?). This
+        //   is used to justify not marking slots as live until the pointer
+        //   to them is used, but I think this should be clarified better.
+  //
+  // If we define a slot as *active* at a program point if it either can
+  // be written to, or if it has a live and non-undef content, then it
+  // is obvious that slots that are never active together can be merged.
+  //
+        // From our rules, we see that *out-of-scope* slots are never *active*,
+        // and from (7) we see that "non-conservative" slots remain non-*active*
+        // until their address is taken. Therefore, we can approximate slot activity
+        // using dataflow.
+        //
+        // Now, naively, we might think that we could construct our interference
+  // graph by propagating `S active` through the CFG for every stack-slot `S`,
+  // and having `S` and `T` interfere if there is a point in which they are
+  // both *active*. That is sound, but overly conservative in some important
+  // cases: it is possible that `S` is active on one predecessor edge and
+  // `T` is active on another. See PR32488.
+  //
+  // If we want to construct the interference graph precisely, we could
+        // propagate `S active` and `S&T active` predicates through the CFG. That
+        // would be precise, but requires propagating `O(n^2)` dataflow facts.
+        //
+        // Instead, we rely on a little trick: for an `S&T active` predicate to
+        // start holding, there has to be either
+        // A) a point in the gen-set of `S active` where `T` is *active*
+        // B) a point in the gen-set of `T active` where `S` is *active*
+        // C) a point in the gen-set of both `S active` and `T active`.
+        //
+        // Of course, the `S&T active` predicate can be propagated further, but
+        // it holding at 1 point is enough for us to mark an edge on the interference
+        // graph. So that's what we do.
+        if (!First->overlaps(*SecondS) && !FirstS->overlaps(*Second)) {
+          Changed = true;
+          First->MergeSegmentsInAsValue(*Second, First->getValNumInfo(0));
+          FirstS->MergeSegmentsInAsValue(*SecondS, FirstS->getValNumInfo(0));
           SlotRemap[SecondSlot] = FirstSlot;
           SortedSlots[J] = -1;
           DEBUG(dbgs()<<"Merging #"<<FirstSlot<<" and slots #"<<
                 SecondSlot<<" together.\n");
           unsigned MaxAlignment = std::max(MFI->getObjectAlignment(FirstSlot),
                                            MFI->getObjectAlignment(SecondSlot));
 
           assert(MFI->getObjectSize(FirstSlot) >=

test/CodeGen/X86/StackColoring.ll

if.else:                                          ; preds = %entry
   call void @inita(i32* %arraydecay1) #3
   %arraydecay3 = getelementptr inbounds [128 x i32], [128 x i32]* %b3, i64 0, i64 0
   call void @inita(i32* %arraydecay3) #3
   %tobool25 = icmp eq i32 %x, 0
   br i1 %tobool25, label %if.end, label %while.body.lr.ph
 
 while.body.lr.ph:                                 ; preds = %if.else
   %tmp2 = bitcast [128 x i32]* %b3 to i8*
-  br label %while.body
-
-while.body:                                       ; preds = %while.body.lr.ph, %while.body
-  %x.addr.06 = phi i32 [ %x, %while.body.lr.ph ], [ %dec, %while.body ]
-  %dec = add nsw i32 %x.addr.06, -1
-  call void @llvm.lifetime.start(i64 512, i8* %tmp2) #3
-  call void @inita(i32* %arraydecay3) #3
-  call void @llvm.lifetime.end(i64 512, i8* %tmp2) #3
-  %tobool2 = icmp eq i32 %dec, 0
-  br i1 %tobool2, label %if.end.loopexit, label %while.body
-
-if.end.loopexit:                                  ; preds = %while.body
+  br label %while.body
+
+while.body:                                       ; preds = %while.body.lr.ph, %while.body
+  %x.addr.06 = phi i32 [ %x, %while.body.lr.ph ], [ %dec, %while.body ]
+  %dec = add nsw i32 %x.addr.06, -1
+  call void @llvm.lifetime.start(i64 512, i8* %tmp2) #3
+  call void @inita(i32* %arraydecay3) #3
+  call void @llvm.lifetime.end(i64 512, i8* %tmp2) #3
+  %tobool2 = icmp eq i32 %dec, 0
+  br i1 %tobool2, label %if.end.loopexit, label %while.body
+
+if.end.loopexit:                                  ; preds = %while.body
+  br label %if.end
+
+if.end:                                           ; preds = %if.end.loopexit, %if.else, %if.then
+  call void @llvm.lifetime.end(i64 512, i8* %tmp1) #3
+  call void @llvm.lifetime.end(i64 512, i8* %tmp) #3
+  ret i32 0
+}
+
+; Test case motivated by PR27903. Same routine inlined multiple times
+; into a caller results in a multi-segment lifetime, but the second
+; lifetime has no explicit references to the stack slot. Such slots
+; have to be treated conservatively.
+
+;CHECK-LABEL: twobod_b27903:
+;YESCOLOR: subq  $96, %rsp
+;NOFIRSTUSE: subq  $96, %rsp
+;NOCOLOR: subq  $96, %rsp
+
+define i32 @twobod_b27903(i32 %y, i32 %x) {
+entry:
+  %buffer.i = alloca [12 x i32], align 16
+  %abc = alloca [12 x i32], align 16
+  %tmp = bitcast [12 x i32]* %buffer.i to i8*
+  call void @llvm.lifetime.start(i64 48, i8* %tmp)
+  %idxprom.i = sext i32 %y to i64
+  %arrayidx.i = getelementptr inbounds [12 x i32], [12 x i32]* %buffer.i, i64 0, i64 %idxprom.i
+  call void @inita(i32* %arrayidx.i)
+  %add.i = add nsw i32 %x, %y
+  call void @llvm.lifetime.end(i64 48, i8* %tmp)
+  %tobool = icmp eq i32 %y, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %tmp1 = bitcast [12 x i32]* %abc to i8*
+  call void @llvm.lifetime.start(i64 48, i8* %tmp1)
+  %arrayidx = getelementptr inbounds [12 x i32], [12 x i32]* %abc, i64 0, i64 %idxprom.i
+  call void @inita(i32* %arrayidx)
+  call void @llvm.lifetime.start(i64 48, i8* %tmp)
+  call void @inita(i32* %arrayidx.i)
+  %add.i9 = add nsw i32 %add.i, %y
+  call void @llvm.lifetime.end(i64 48, i8* %tmp)
+  call void @llvm.lifetime.end(i64 48, i8* %tmp1)
   br label %if.end
 
-if.end:                                           ; preds = %if.end.loopexit, %if.else, %if.then
-  call void @llvm.lifetime.end(i64 512, i8* %tmp1) #3
-  call void @llvm.lifetime.end(i64 512, i8* %tmp) #3
-  ret i32 0
-}
+if.end:                                           ; preds = %if.then, %entry
+  %x.addr.0 = phi i32 [ %add.i9, %if.then ], [ %add.i, %entry ]
+  ret i32 %x.addr.0
+}
+
 
-; Test case motivated by PR27903. Same routine inlined multiple times
-; into a caller results in a multi-segment lifetime, but the second
-; lifetime has no explicit references to the stack slot. Such slots
-; have to be treated conservatively.
-
-;CHECK-LABEL: twobod_b27903:
-;YESCOLOR: subq  $96, %rsp
-;NOFIRSTUSE: subq  $96, %rsp
-;NOCOLOR: subq  $96, %rsp
-
-define i32 @twobod_b27903(i32 %y, i32 %x) {
-entry:
-  %buffer.i = alloca [12 x i32], align 16
-  %abc = alloca [12 x i32], align 16
-  %tmp = bitcast [12 x i32]* %buffer.i to i8*
-  call void @llvm.lifetime.start(i64 48, i8* %tmp)
-  %idxprom.i = sext i32 %y to i64
-  %arrayidx.i = getelementptr inbounds [12 x i32], [12 x i32]* %buffer.i, i64 0, i64 %idxprom.i
-  call void @inita(i32* %arrayidx.i)
-  %add.i = add nsw i32 %x, %y
-  call void @llvm.lifetime.end(i64 48, i8* %tmp)
-  %tobool = icmp eq i32 %y, 0
-  br i1 %tobool, label %if.end, label %if.then
-
-if.then:                                          ; preds = %entry
-  %tmp1 = bitcast [12 x i32]* %abc to i8*
-  call void @llvm.lifetime.start(i64 48, i8* %tmp1)
-  %arrayidx = getelementptr inbounds [12 x i32], [12 x i32]* %abc, i64 0, i64 %idxprom.i
-  call void @inita(i32* %arrayidx)
-  call void @llvm.lifetime.start(i64 48, i8* %tmp)
-  call void @inita(i32* %arrayidx.i)
-  %add.i9 = add nsw i32 %add.i, %y
-  call void @llvm.lifetime.end(i64 48, i8* %tmp)
-  call void @llvm.lifetime.end(i64 48, i8* %tmp1)
-  br label %if.end
-
-if.end:                                           ; preds = %if.then, %entry
-  %x.addr.0 = phi i32 [ %add.i9, %if.then ], [ %add.i, %entry ]
-  ret i32 %x.addr.0
-}
+;CHECK-LABEL: pr32488:
+;YESCOLOR: subq  $256, %rsp
+;NOFIRSTUSE: subq  $256, %rsp
+;NOCOLOR: subq  $512, %rsp
+define i1 @pr32488(i1, i1)
+{
+entry-block:
+  %foo = alloca [32 x i64]
+  %bar = alloca [32 x i64]
+  %foo_i8 = bitcast [32 x i64]* %foo to i8*
+  %bar_i8 = bitcast [32 x i64]* %bar to i8*
+  br i1 %0, label %if_false, label %if_true
+if_false:
+  call void @llvm.lifetime.start(i64 256, i8* %bar_i8)
+  call void @baz([32 x i64]* %foo, i32 0)
+  br i1 %1, label %if_false.1, label %onerr
+if_false.1:
+  call void @llvm.lifetime.end(i64 256, i8* %bar_i8)
+  br label %merge
+if_true:
+  call void @llvm.lifetime.start(i64 256, i8* %foo_i8)
+  call void @baz([32 x i64]* %foo, i32 1)
+  br i1 %1, label %if_true.1, label %onerr
+if_true.1:
+  call void @llvm.lifetime.end(i64 256, i8* %foo_i8)
+  br label %merge
+merge:
+  ret i1 false
+onerr:
+  call void @llvm.lifetime.end(i64 256, i8* %foo_i8)
+  call void @llvm.lifetime.end(i64 256, i8* %bar_i8)
+  call void @destructor()
+  ret i1 true
+}
+
+%Data = type { [32 x i64] }
+
+declare void @destructor()
+
+declare void @inita(i32*)
 
-declare void @inita(i32*)
+declare void @initb(i32*,i32*,i32*)
 
-declare void @initb(i32*,i32*,i32*)
+declare void @bar([100 x i32]* , [100 x i32]*) nounwind
 
-declare void @bar([100 x i32]* , [100 x i32]*) nounwind
+declare void @baz([32 x i64]*, i32)
 
 declare void @llvm.lifetime.start(i64, i8* nocapture) nounwind
 
 declare void @llvm.lifetime.end(i64, i8* nocapture) nounwind
 
 declare i32 @foo(i32, i8*)