diff --git a/llvm/lib/CodeGen/StackSlotColoring.cpp b/llvm/lib/CodeGen/StackSlotColoring.cpp
--- a/llvm/lib/CodeGen/StackSlotColoring.cpp
+++ b/llvm/lib/CodeGen/StackSlotColoring.cpp
@@ -90,8 +90,47 @@
     // UsedColors - "Colors" that have been assigned. This is per stack ID
     SmallVector<BitVector, 2> UsedColors;
 
+    // Join all intervals sharing one color into a single live range to speedup
+    // range overlap test.
+    struct ColorAssignmentInfo {
+      unsigned NumLRAssigned = 0;   // Num of liveranges assigned to the color.
+      LiveRange *FirstLR = nullptr; // First liverange (used to avoid copy when
+                                    // there is a sigle liverange per color).
+      LiveRange JoinedLR; // Joined liverange used when NumLRAssigned > 1.
+
+      // Return true if LiveInterval overlaps with any
+      // intervals that have already been assigned to this color.
+      bool overlaps(LiveInterval *LI) const {
+        if (!NumLRAssigned)
+          return false;
+        return NumLRAssigned > 1 ? JoinedLR.overlaps(*LI)
+                                 : FirstLR->overlaps(*LI);
+      }
+
+      // Add new LiveInterval to this color.
+      void add(LiveInterval *LI, BumpPtrAllocator &Allocator) {
+        assert(!overlaps(li));
+        switch (NumLRAssigned) {
+        case 0:
+          FirstLR = LI;
+          break;
+        case 1:
+          assert(FirstLR);
+          JoinedLR.assign(*FirstLR, Allocator);
+          LLVM_FALLTHROUGH;
+        default: {
+          LiveRangeUpdater Updater(&JoinedLR);
+          auto *VNI = JoinedLR.getValNumInfo(0); // Don't care about valno.
+          for (auto &S : LI->segments)
+            Updater.add(LiveRange::Segment(S.start, S.end, VNI));
+        } break;
+        }
+        ++NumLRAssigned;
+      }
+    };
+
     // Assignments - Color to intervals mapping.
-    SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments;
+    SmallVector<ColorAssignmentInfo, 16> Assignments;
 
   public:
     static char ID; // Pass identification
@@ -116,7 +155,6 @@
   private:
     void InitializeSlots();
     void ScanForSpillSlotRefs(MachineFunction &MF);
-    bool OverlapWithAssignments(LiveInterval *li, int Color) const;
     int ColorSlot(LiveInterval *li);
     bool ColorSlots(MachineFunction &MF);
     void RewriteInstruction(MachineInstr &MI, SmallVectorImpl<int> &SlotMapping,
@@ -247,19 +285,6 @@
     NextColors[I] = AllColors[I].find_first();
 }
 
-/// OverlapWithAssignments - Return true if LiveInterval overlaps with any
-/// LiveIntervals that have already been assigned to the specified color.
-bool
-StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const {
-  const SmallVectorImpl<LiveInterval *> &OtherLIs = Assignments[Color];
-  for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) {
-    LiveInterval *OtherLI = OtherLIs[i];
-    if (OtherLI->overlaps(*li))
-      return true;
-  }
-  return false;
-}
-
 /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.
 int StackSlotColoring::ColorSlot(LiveInterval *li) {
   int Color = -1;
@@ -272,7 +297,7 @@
     // Check if it's possible to reuse any of the used colors.
     Color = UsedColors[StackID].find_first();
     while (Color != -1) {
-      if (!OverlapWithAssignments(li, Color)) {
+      if (!Assignments[Color].overlaps(li)) {
         Share = true;
         ++NumEliminated;
         break;
@@ -298,7 +323,7 @@
   assert(MFI->getStackID(Color) == MFI->getStackID(FI));
 
   // Record the assignment.
-  Assignments[Color].push_back(li);
+  Assignments[Color].add(li, LS->getVNInfoAllocator());
   LLVM_DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n");
 
   // Change size and alignment of the allocated slot. If there are multiple
@@ -515,8 +540,6 @@
   OrigSizes.clear();
   AllColors.clear();
   UsedColors.clear();
-  for (unsigned i = 0, e = Assignments.size(); i != e; ++i)
-    Assignments[i].clear();
   Assignments.clear();
 
   return Changed;