Add a stack slot coloring pass. Not yet enabled.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51934 91177308-0d34-0410-b5e6-96231b3b80d8

10 files changed, 523 insertions, 47 deletions

diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index e941a45..b6f38df 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -35,6 +35,7 @@ namespace llvm {
   /// merge point), it contains ~0u,x. If the value number is not in use, it
   /// contains ~1u,x to indicate that the value # is not used. 
   ///   def   - Instruction # of the definition.
+  ///         - or reg # of the definition if it's a stack slot liveinterval.
   ///   copy  - Copy iff val# is defined by a copy; zero otherwise.
   ///   hasPHIKill - One or more of the kills are PHI nodes.
   ///   kills - Instruction # of the kills.
@@ -100,15 +101,16 @@ namespace llvm {
     typedef SmallVector<LiveRange,4> Ranges;
     typedef SmallVector<VNInfo*,4> VNInfoList;
 
-    unsigned reg;        // the register of this interval
+    bool isSS;           // True if this represents a stack slot
+    unsigned reg;        // the register or stack slot of this interval
     unsigned preference; // preferred register to allocate for this interval
     float weight;        // weight of this interval
     Ranges ranges;       // the ranges in which this register is live
     VNInfoList valnos;   // value#'s
 
   public:
-    LiveInterval(unsigned Reg, float Weight)
-      : reg(Reg), preference(0), weight(Weight) {
+    LiveInterval(unsigned Reg, float Weight, bool IsSS = false)
+      : isSS(IsSS), reg(Reg), preference(0), weight(Weight) {
     }
 
     typedef Ranges::iterator iterator;
@@ -139,6 +141,17 @@ namespace llvm {
       return I;
     }
 
+    /// isStackSlot - Return true if this is a stack slot interval.
+    ///
+    bool isStackSlot() const { return isSS; }
+
+    /// getStackSlotIndex - Return stack slot index if this is a stack slot
+    /// interval.
+    int getStackSlotIndex() const {
+      assert(isStackSlot() && "Interval is not a stack slot interval!");
+      return reg;
+    }
+
     bool containsOneValue() const { return valnos.size() == 1; }
 
     unsigned getNumValNums() const { return (unsigned)valnos.size(); }
@@ -313,6 +326,11 @@ namespace llvm {
     /// FindLiveRangeContaining - Return an iterator to the live range that
     /// contains the specified index, or end() if there is none.
     iterator FindLiveRangeContaining(unsigned Idx);
+
+    /// findDefinedVNInfo - Find the VNInfo that's defined at the specified
+    /// index (register interval) or defined by the specified register (stack
+    /// inteval).
+    VNInfo *findDefinedVNInfo(unsigned DefIdxOrReg) const;
     
     /// overlaps - Return true if the intersection of the two live intervals is
     /// not empty.
diff --git a/include/llvm/CodeGen/LiveStackAnalysis.h b/include/llvm/CodeGen/LiveStackAnalysis.h
new file mode 100644
index 0000000..87ed67f
--- /dev/null
+++ b/include/llvm/CodeGen/LiveStackAnalysis.h
@@ -0,0 +1,71 @@
+//===-- LiveStackAnalysis.h - Live Stack Slot Analysis ----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the live stack slot analysis pass. It is analogous to
+// live interval analysis except it's analyzing liveness of stack slots rather
+// than registers.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_LIVESTACK_ANALYSIS_H
+#define LLVM_CODEGEN_LIVESTACK_ANALYSIS_H
+
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/LiveInterval.h"
+#include "llvm/Support/Allocator.h"
+#include <map>
+
+namespace llvm {
+
+  class LiveStacks : public MachineFunctionPass {
+    /// Special pool allocator for VNInfo's (LiveInterval val#).
+    ///
+    BumpPtrAllocator VNInfoAllocator;
+
+    /// s2iMap - Stack slot indices to live interval mapping.
+    ///
+    typedef std::map<int, LiveInterval> SS2IntervalMap;
+    SS2IntervalMap s2iMap;
+
+  public:
+    static char ID; // Pass identification, replacement for typeid
+    LiveStacks() : MachineFunctionPass((intptr_t)&ID) {}
+
+    typedef SS2IntervalMap::iterator iterator;
+    typedef SS2IntervalMap::const_iterator const_iterator;
+    const_iterator begin() const { return s2iMap.begin(); }
+    const_iterator end() const { return s2iMap.end(); }
+    iterator begin() { return s2iMap.begin(); }
+    iterator end() { return s2iMap.end(); }
+    unsigned getNumIntervals() const { return (unsigned)s2iMap.size(); }
+
+    LiveInterval &getOrCreateInterval(int Slot) {
+      SS2IntervalMap::iterator I = s2iMap.find(Slot);
+      if (I == s2iMap.end())
+        I = s2iMap.insert(I,std::make_pair(Slot,LiveInterval(Slot,0.0F,true)));
+      return I->second;
+    }
+
+    BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; }
+
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+    virtual void releaseMemory();
+
+    /// runOnMachineFunction - pass entry point
+    virtual bool runOnMachineFunction(MachineFunction&);
+
+    /// print - Implement the dump method.
+    virtual void print(std::ostream &O, const Module* = 0) const;
+    void print(std::ostream *O, const Module* M = 0) const {
+      if (O) print(*O, M);
+    }
+  };
+}
+
+#endif /* LLVM_CODEGEN_LIVESTACK_ANALYSIS_H */
diff --git a/include/llvm/CodeGen/MachineFrameInfo.h b/include/llvm/CodeGen/MachineFrameInfo.h
index 0f40550..b47ef67 100644
--- a/include/llvm/CodeGen/MachineFrameInfo.h
+++ b/include/llvm/CodeGen/MachineFrameInfo.h
@@ -195,6 +195,13 @@ public:
   ///
   int getObjectIndexEnd() const { return (int)Objects.size()-NumFixedObjects; }
 
+  /// getNumFixedObjects() - Return the number of fixed objects.
+  unsigned getNumFixedObjects() const { return NumFixedObjects; }
+
+  /// getNumObjects() - Return the number of objects.
+  ///
+  unsigned getNumObjects() const { return Objects.size(); }
+
   /// getObjectSize - Return the size of the specified object
   ///
   int64_t getObjectSize(int ObjectIdx) const {
@@ -203,6 +210,13 @@ public:
     return Objects[ObjectIdx+NumFixedObjects].Size;
   }
 
+  // setObjectSize - Change the size of the specified stack object...
+  void setObjectSize(int ObjectIdx, int64_t Size) {
+    assert(unsigned(ObjectIdx+NumFixedObjects) < Objects.size() &&
+           "Invalid Object Idx!");
+    Objects[ObjectIdx+NumFixedObjects].Size = Size;
+  }
+
   /// getObjectAlignment - Return the alignment of the specified stack object...
   unsigned getObjectAlignment(int ObjectIdx) const {
     assert(unsigned(ObjectIdx+NumFixedObjects) < Objects.size() &&
@@ -324,12 +338,8 @@ public:
   /// RemoveStackObject - Remove or mark dead a statically sized stack object.
   ///
   void RemoveStackObject(int ObjectIdx) {
-    if (ObjectIdx == (int)(Objects.size()-NumFixedObjects-1))
-      // Last object, simply pop it off the list.
-      Objects.pop_back();
-    else
-      // Mark it dead.
-      Objects[ObjectIdx+NumFixedObjects].Size = ~0ULL;
+    // Mark it dead.
+    Objects[ObjectIdx+NumFixedObjects].Size = ~0ULL;
   }
 
   /// CreateVariableSizedObject - Notify the MachineFrameInfo object that a
diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h
index 898416a..dd677fa 100644
--- a/include/llvm/CodeGen/Passes.h
+++ b/include/llvm/CodeGen/Passes.h
@@ -172,6 +172,9 @@ namespace llvm {
   /// createMachineSinkingPass - This pass performs sinking on machine
   /// instructions.
   FunctionPass *createMachineSinkingPass();
+
+  /// createStackSlotColoringPass - This pass performs stack slot coloring.
+  FunctionPass *createStackSlotColoringPass();
   
 } // End llvm namespace
 
diff --git a/lib/CodeGen/LLVMTargetMachine.cpp b/lib/CodeGen/LLVMTargetMachine.cpp
index e4ad872..73f2902 100644
--- a/lib/CodeGen/LLVMTargetMachine.cpp
+++ b/lib/CodeGen/LLVMTargetMachine.cpp
@@ -38,12 +38,13 @@ static cl::opt<bool>
 EnableSinking("enable-sinking", cl::init(false), cl::Hidden,
               cl::desc("Perform sinking on machine code"));
 static cl::opt<bool>
-AlignLoops("align-loops", cl::init(true), cl::Hidden,
-           cl::desc("Align loop headers"));
+EnableStackColoring("stack-coloring",
+            cl::init(true), cl::Hidden,
+            cl::desc("Perform stack slot coloring"));
 static cl::opt<bool>
-PerformLICM("machine-licm",
-            cl::init(false), cl::Hidden,
-            cl::desc("Perform loop-invariant code motion on machine code"));
+EnableLICM("machine-licm",
+           cl::init(false), cl::Hidden,
+           cl::desc("Perform loop-invariant code motion on machine code"));
 
 // When this works it will be on by default.
 static cl::opt<bool>
@@ -88,7 +89,7 @@ LLVMTargetMachine::addPassesToEmitFile(PassManagerBase &PM,
   if (PrintMachineCode)
     PM.add(createMachineFunctionPrinterPass(cerr));
 
-  if (PerformLICM)
+  if (EnableLICM)
     PM.add(createMachineLICMPass());
   
   if (EnableSinking)
@@ -101,21 +102,28 @@ LLVMTargetMachine::addPassesToEmitFile(PassManagerBase &PM,
   // Perform register allocation to convert to a concrete x86 representation
   PM.add(createRegisterAllocator());
   
-  if (PrintMachineCode)
+  // Perform stack slot coloring.
+  if (EnableStackColoring)
+    PM.add(createStackSlotColoringPass());
+
+  if (PrintMachineCode)  // Print the register-allocated code
     PM.add(createMachineFunctionPrinterPass(cerr));
-    
-  PM.add(createLowerSubregsPass());
   
-  if (PrintMachineCode)  // Print the subreg lowered code
-    PM.add(createMachineFunctionPrinterPass(cerr));
-
   // Run post-ra passes.
   if (addPostRegAlloc(PM, Fast) && PrintMachineCode)
     PM.add(createMachineFunctionPrinterPass(cerr));
 
+  PM.add(createLowerSubregsPass());
+  
+  if (PrintMachineCode)  // Print the subreg lowered code
+    PM.add(createMachineFunctionPrinterPass(cerr));
+
   // Insert prolog/epilog code.  Eliminate abstract frame index references...
   PM.add(createPrologEpilogCodeInserter());
   
+  if (PrintMachineCode)
+    PM.add(createMachineFunctionPrinterPass(cerr));
+  
   // Second pass scheduler.
   if (!Fast && !DisablePostRAScheduler)
     PM.add(createPostRAScheduler());
@@ -140,7 +148,7 @@ LLVMTargetMachine::addPassesToEmitFile(PassManagerBase &PM,
   if (addPreEmitPass(PM, Fast) && PrintMachineCode)
     PM.add(createMachineFunctionPrinterPass(cerr));
 
-  if (AlignLoops && !Fast && !OptimizeForSize)
+  if (!Fast && !OptimizeForSize)
     PM.add(createLoopAlignerPass());
 
   switch (FileType) {
@@ -218,7 +226,7 @@ bool LLVMTargetMachine::addPassesToEmitMachineCode(PassManagerBase &PM,
   if (PrintMachineCode)
     PM.add(createMachineFunctionPrinterPass(cerr));
 
-  if (PerformLICM)
+  if (EnableLICM)
     PM.add(createMachineLICMPass());
   
   if (EnableSinking)
@@ -228,25 +236,32 @@ bool LLVMTargetMachine::addPassesToEmitMachineCode(PassManagerBase &PM,
   if (addPreRegAlloc(PM, Fast) && PrintMachineCode)
     PM.add(createMachineFunctionPrinterPass(cerr));
 
-  // Perform register allocation to convert to a concrete x86 representation
+  // Perform register allocation.
   PM.add(createRegisterAllocator());
-  
+
+  // Perform stack slot coloring.
+  if (EnableStackColoring)
+    PM.add(createStackSlotColoringPass());
+
   if (PrintMachineCode)
     PM.add(createMachineFunctionPrinterPass(cerr));
     
+  // Run post-ra passes.
+  if (addPostRegAlloc(PM, Fast) && PrintMachineCode)
+    PM.add(createMachineFunctionPrinterPass(cerr));
+
+  if (PrintMachineCode)  // Print the register-allocated code
+    PM.add(createMachineFunctionPrinterPass(cerr));
+  
   PM.add(createLowerSubregsPass());
   
   if (PrintMachineCode)  // Print the subreg lowered code
     PM.add(createMachineFunctionPrinterPass(cerr));
 
-  // Run post-ra passes.
-  if (addPostRegAlloc(PM, Fast) && PrintMachineCode)
-    PM.add(createMachineFunctionPrinterPass(cerr));
-
   // Insert prolog/epilog code.  Eliminate abstract frame index references...
   PM.add(createPrologEpilogCodeInserter());
   
-  if (PrintMachineCode)  // Print the register-allocated code
+  if (PrintMachineCode)
     PM.add(createMachineFunctionPrinterPass(cerr));
   
   // Second pass scheduler.
@@ -258,6 +273,7 @@ bool LLVMTargetMachine::addPassesToEmitMachineCode(PassManagerBase &PM,
     PM.add(createBranchFoldingPass(getEnableTailMergeDefault()));
 
   PM.add(createGCMachineCodeAnalysisPass());
+
   if (PrintMachineCode)
     PM.add(createMachineFunctionPrinterPass(cerr));
   
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 48c25a1..24081b9 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -358,6 +358,20 @@ LiveInterval::FindLiveRangeContaining(unsigned Idx) {
   return end();
 }
 
+/// findDefinedVNInfo - Find the VNInfo that's defined at the specified index
+/// (register interval) or defined by the specified register (stack inteval).
+VNInfo *LiveInterval::findDefinedVNInfo(unsigned DefIdxOrReg) const {
+  VNInfo *VNI = NULL;
+  for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end();
+       i != e; ++i)
+    if ((*i)->def == DefIdxOrReg) {
+      VNI = *i;
+      break;
+    }
+  return VNI;
+}
+
+
 /// join - Join two live intervals (this, and other) together.  This applies
 /// mappings to the value numbers in the LHS/RHS intervals as specified.  If
 /// the intervals are not joinable, this aborts.
@@ -664,7 +678,9 @@ void LiveRange::dump() const {
 
 void LiveInterval::print(std::ostream &OS,
                          const TargetRegisterInfo *TRI) const {
-  if (TRI && TargetRegisterInfo::isPhysicalRegister(reg))
+  if (isSS)
+    OS << "SS#" << reg;
+  else if (TRI && TargetRegisterInfo::isPhysicalRegister(reg))
     OS << TRI->getName(reg);
   else
     OS << "%reg" << reg;
@@ -672,7 +688,7 @@ void LiveInterval::print(std::ostream &OS,
   OS << ',' << weight;
 
   if (empty())
-    OS << "EMPTY";
+    OS << " EMPTY";
   else {
     OS << " = ";
     for (LiveInterval::Ranges::const_iterator I = ranges.begin(),
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 5473853..f184191 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -65,6 +65,7 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
 }
 
 void LiveIntervals::releaseMemory() {
+  MBB2IdxMap.clear();
   Idx2MBBMap.clear();
   mi2iMap_.clear();
   i2miMap_.clear();
@@ -229,8 +230,8 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
 void LiveIntervals::print(std::ostream &O, const Module* ) const {
   O << "********** INTERVALS **********\n";
   for (const_iterator I = begin(), E = end(); I != E; ++I) {
-    I->second.print(DOUT, tri_);
-    DOUT << "\n";
+    I->second.print(O, tri_);
+    O << "\n";
   }
 
   O << "********** MACHINEINSTRS **********\n";
@@ -1160,17 +1161,6 @@ bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
   return false;
 }
 
-static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) {
-  const VNInfo *VNI = NULL;
-  for (LiveInterval::const_vni_iterator i = li.vni_begin(),
-         e = li.vni_end(); i != e; ++i)
-    if ((*i)->def == DefIdx) {
-      VNI = *i;
-      break;
-    }
-  return VNI;
-}
-
 /// RewriteInfo - Keep track of machine instrs that will be rewritten
 /// during spilling.
 namespace {
@@ -1318,7 +1308,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
           HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
         else {
           // If this is a two-address code, then this index starts a new VNInfo.
-          const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index));
+          const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index));
           if (VNI)
             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
         }
diff --git a/lib/CodeGen/LiveStackAnalysis.cpp b/lib/CodeGen/LiveStackAnalysis.cpp
new file mode 100644
index 0000000..9358c10
--- /dev/null
+++ b/lib/CodeGen/LiveStackAnalysis.cpp
@@ -0,0 +1,50 @@
+//===-- LiveStackAnalysis.cpp - Live Stack Slot Analysis ------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the live stack slot analysis pass. It is analogous to
+// live interval analysis except it's analyzing liveness of stack slots rather
+// than registers.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "livestacks"
+#include "llvm/CodeGen/LiveStackAnalysis.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/ADT/Statistic.h"
+using namespace llvm;
+
+char LiveStacks::ID = 0;
+static RegisterPass<LiveStacks> X("livestacks", "Live Stack Slot Analysis");
+
+void LiveStacks::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+}
+
+void LiveStacks::releaseMemory() {
+  // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
+  VNInfoAllocator.Reset();
+  s2iMap.clear();
+}
+
+bool LiveStacks::runOnMachineFunction(MachineFunction &) {
+  // FIXME: No analysis is being done right now. We are relying on the
+  // register allocators to provide the information.
+  return false;
+}
+
+/// print - Implement the dump method.
+void LiveStacks::print(std::ostream &O, const Module* ) const {
+  O << "********** INTERVALS **********\n";
+  for (const_iterator I = begin(), E = end(); I != E; ++I) {
+    I->second.print(O);
+    O << "\n";
+  }
+}
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 456ee63..8bfa868 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -12,10 +12,11 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "regalloc"
-#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "PhysRegTracker.h"
 #include "VirtRegMap.h"
 #include "llvm/Function.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveStackAnalysis.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
@@ -67,6 +68,7 @@ namespace {
     MachineRegisterInfo *reginfo_;
     BitVector allocatableRegs_;
     LiveIntervals* li_;
+    LiveStacks* ls_;
     const MachineLoopInfo *loopInfo;
 
     /// handled_ - Intervals are added to the handled_ set in the order of their
@@ -103,6 +105,8 @@ namespace {
       // Make sure PassManager knows which analyses to make available
       // to coalescing and which analyses coalescing invalidates.
       AU.addRequiredTransitive<RegisterCoalescer>();
+      AU.addRequired<LiveStacks>();
+      AU.addPreserved<LiveStacks>();
       AU.addRequired<MachineLoopInfo>();
       AU.addPreserved<MachineLoopInfo>();
       AU.addPreservedID(MachineDominatorsID);
@@ -171,6 +175,9 @@ namespace {
   char RALinScan::ID = 0;
 }
 
+static RegisterPass<RALinScan>
+X("linearscan-regalloc", "Linear Scan Register Allocator");
+
 void RALinScan::ComputeRelatedRegClasses() {
   const TargetRegisterInfo &TRI = *tri_;
   
@@ -258,6 +265,7 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
   reginfo_ = &mf_->getRegInfo();
   allocatableRegs_ = tri_->getAllocatableSet(fn);
   li_ = &getAnalysis<LiveIntervals>();
+  ls_ = &getAnalysis<LiveStacks>();
   loopInfo = &getAnalysis<MachineLoopInfo>();
 
   // We don't run the coalescer here because we have no reason to
@@ -504,6 +512,26 @@ static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){
   }
 }
 
+/// addStackInterval - Create a LiveInterval for stack if the specified live
+/// interval has been spilled.
+static void addStackInterval(LiveInterval *cur, LiveStacks *ls_,
+                             LiveIntervals *li_, VirtRegMap &vrm_) {
+  int SS = vrm_.getStackSlot(cur->reg);
+  if (SS == VirtRegMap::NO_STACK_SLOT)
+    return;
+  LiveInterval &SI = ls_->getOrCreateInterval(SS);
+  VNInfo *VNI;
+  if (SI.getNumValNums())
+    VNI = SI.getValNumInfo(0);
+  else
+    VNI = SI.getNextValue(~0U, 0, ls_->getVNInfoAllocator());
+
+  LiveInterval &RI = li_->getInterval(cur->reg);
+  // FIXME: This may be overly conservative.
+  SI.MergeRangesInAsValue(RI, VNI);
+  SI.weight += RI.weight;
+}
+
 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
 /// spill.
 void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
@@ -717,6 +745,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
     DOUT << "\t\t\tspilling(c): " << *cur << '\n';
     std::vector<LiveInterval*> added =
       li_->addIntervalsForSpills(*cur, loopInfo, *vrm_);
+    addStackInterval(cur, ls_, li_, *vrm_);
     if (added.empty())
       return;  // Early exit if all spills were folded.
 
@@ -769,6 +798,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
       earliestStart = std::min(earliestStart, i->first->beginNumber());
       std::vector<LiveInterval*> newIs =
         li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_);
+      addStackInterval(i->first, ls_, li_, *vrm_);
       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
       spilled.insert(reg);
     }
@@ -782,6 +812,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
       earliestStart = std::min(earliestStart, i->first->beginNumber());
       std::vector<LiveInterval*> newIs =
         li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_);
+      addStackInterval(i->first, ls_, li_, *vrm_);
       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
       spilled.insert(reg);
     }
diff --git a/lib/CodeGen/StackSlotColoring.cpp b/lib/CodeGen/StackSlotColoring.cpp
new file mode 100644
index 0000000..24bd028
--- /dev/null
+++ b/lib/CodeGen/StackSlotColoring.cpp
@@ -0,0 +1,271 @@
+//===-- StackSlotColoring.cpp - Sinking for machine instructions ----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the stack slot coloring pass.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "stackcoloring"
+#include "llvm/CodeGen/LiveStackAnalysis.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
+#include <vector>
+using namespace llvm;
+
+static cl::opt<bool>
+DisableSharing("no-stack-slot-sharing",
+             cl::init(false), cl::Hidden,
+             cl::desc("Surpress slot sharing during stack coloring"));
+
+static cl::opt<int>
+DeleteLimit("slot-delete-limit", cl::init(-1), cl::Hidden,
+             cl::desc("Stack coloring slot deletion limit"));
+
+STATISTIC(NumEliminated,   "Number of stack slots eliminated due to coloring");
+
+namespace {
+  class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass {
+    LiveStacks* LS;
+    MachineFrameInfo *MFI;
+
+    // SSIntervals - Spill slot intervals.
+    std::vector<LiveInterval*> SSIntervals;
+
+    // OrigAlignments - Alignments of stack objects before coloring.
+    SmallVector<unsigned, 16> OrigAlignments;
+
+    // OrigSizes - Sizess of stack objects before coloring.
+    SmallVector<unsigned, 16> OrigSizes;
+
+    // AllColors - If index is set, it's a spill slot, i.e. color.
+    // FIXME: This assumes PEI locate spill slot with smaller indices
+    // closest to stack pointer / frame pointer. Therefore, smaller
+    // index == better color.
+    BitVector AllColors;
+
+    // NextColor - Next "color" that's not yet used.
+    int NextColor;
+
+    // UsedColors - "Colors" that have been assigned.
+    BitVector UsedColors;
+
+    // Assignments - Color to intervals mapping.
+    SmallVector<SmallVector<LiveInterval*,4>,16> Assignments;
+
+  public:
+    static char ID; // Pass identification
+    StackSlotColoring() : MachineFunctionPass((intptr_t)&ID), NextColor(-1) {}
+    
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+      AU.addRequired<LiveStacks>();
+      MachineFunctionPass::getAnalysisUsage(AU);
+    }
+
+    virtual bool runOnMachineFunction(MachineFunction &MF);
+    virtual const char* getPassName() const {
+      return "Stack Slot Coloring";
+    }
+
+  private:
+    bool InitializeSlots();
+    bool OverlapWithAssignments(LiveInterval *li, int Color) const;
+    int ColorSlot(LiveInterval *li);
+    bool ColorSlots(MachineFunction &MF);
+  };
+} // end anonymous namespace
+
+char StackSlotColoring::ID = 0;
+
+static RegisterPass<StackSlotColoring>
+X("stack-slot-coloring", "Stack Slot Coloring");
+
+FunctionPass *llvm::createStackSlotColoringPass() {
+  return new StackSlotColoring();
+}
+
+namespace {
+  // IntervalSorter - Comparison predicate that sort live intervals by
+  // their weight.
+  struct IntervalSorter {
+    bool operator()(LiveInterval* LHS, LiveInterval* RHS) const {
+      return LHS->weight > RHS->weight;
+    }
+  };
+}
+
+/// InitializeSlots - Process all spill stack slot liveintervals and add them
+/// to a sorted (by weight) list.
+bool StackSlotColoring::InitializeSlots() {
+  if (LS->getNumIntervals() < 2)
+    return false;
+
+  int LastFI = MFI->getObjectIndexEnd();
+  OrigAlignments.resize(LastFI);
+  OrigSizes.resize(LastFI);
+  AllColors.resize(LastFI);
+  UsedColors.resize(LastFI);
+  Assignments.resize(LastFI);
+
+  // Gather all spill slots into a list.
+  for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) {
+    LiveInterval &li = i->second;
+    int FI = li.getStackSlotIndex();
+    if (MFI->isDeadObjectIndex(FI))
+      continue;
+    SSIntervals.push_back(&li);
+    OrigAlignments[FI] = MFI->getObjectAlignment(FI);
+    OrigSizes[FI]      = MFI->getObjectSize(FI);
+    AllColors.set(FI);
+  }
+
+  // Sort them by weight.
+  std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
+
+  // Get first "color".
+  NextColor = AllColors.find_first();
+  return true;
+}
+
+/// 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 SmallVector<LiveInterval*,4> &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;
+  bool Share = false;
+  if (!DisableSharing &&
+      (DeleteLimit == -1 || (int)NumEliminated < DeleteLimit)) {
+    // Check if it's possible to reuse any of the used colors.
+    Color = UsedColors.find_first();
+    while (Color != -1) {
+      if (!OverlapWithAssignments(li, Color)) {
+        Share = true;
+        ++NumEliminated;
+        break;
+      }
+      Color = UsedColors.find_next(Color);
+    }
+  }
+
+  // Assign it to the first available color (assumed to be the best) if it's
+  // not possible to share a used color with other objects.
+  if (!Share) {
+    assert(NextColor != -1 && "No more spill slots?");
+    Color = NextColor;
+    UsedColors.set(Color);
+    NextColor = AllColors.find_next(NextColor);
+  }
+
+  // Record the assignment.
+  Assignments[Color].push_back(li);
+  int FI = li->getStackSlotIndex();
+  DOUT << "Assigning fi #" << FI << " to fi #" << Color << "\n";
+
+  // Change size and alignment of the allocated slot. If there are multiple
+  // objects sharing the same slot, then make sure the size and alignment
+  // are large enough for all.
+  unsigned Align = OrigAlignments[FI];
+  if (!Share || Align > MFI->getObjectAlignment(Color))
+    MFI->setObjectAlignment(Color, Align);
+  int64_t Size = OrigSizes[FI];
+  if (!Share || Size > MFI->getObjectSize(Color))
+    MFI->setObjectSize(Color, Size);
+  return Color;
+}
+
+/// Colorslots - Color all spill stack slots and rewrite all frameindex machine
+/// operands in the function.
+bool StackSlotColoring::ColorSlots(MachineFunction &MF) {
+  unsigned NumObjs = MFI->getObjectIndexEnd();
+  std::vector<int> SlotMapping(NumObjs, -1);
+  SlotMapping.resize(NumObjs, -1);
+
+  bool Changed = false;
+  for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
+    LiveInterval *li = SSIntervals[i];
+    int SS = li->getStackSlotIndex();
+    int NewSS = ColorSlot(li);
+    SlotMapping[SS] = NewSS;
+    Changed |= (SS != NewSS);
+  }
+
+  if (!Changed)
+    return false;
+
+  // Rewrite all MO_FrameIndex operands.
+  // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands.
+  for (MachineFunction::iterator MBB = MF.begin(), E = MF.end();
+       MBB != E; ++MBB) {
+    for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end();
+         MII != EE; ++MII) {
+      MachineInstr &MI = *MII;
+      for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
+        MachineOperand &MO = MI.getOperand(i);
+        if (!MO.isFrameIndex())
+          continue;
+        int FI = MO.getIndex();
+        if (FI < 0)
+          continue;
+        FI = SlotMapping[FI];
+        if (FI == -1)
+          continue;
+        MO.setIndex(FI);
+      }
+    }
+  }
+
+  // Delete unused stack slots.
+  while (NextColor != -1) {
+    DOUT << "Removing unused stack object fi #" << NextColor << "\n";
+    MFI->RemoveStackObject(NextColor);
+    NextColor = AllColors.find_next(NextColor);
+  }
+
+  return true;
+}
+
+bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
+  DOUT << "******** Stack Slot Coloring ********\n";
+
+  MFI = MF.getFrameInfo();
+  LS = &getAnalysis<LiveStacks>();
+
+  bool Changed = false;
+  if (InitializeSlots())
+    Changed = ColorSlots(MF);
+
+  NextColor = -1;
+  SSIntervals.clear();
+  OrigAlignments.clear();
+  OrigSizes.clear();
+  AllColors.clear();
+  UsedColors.clear();
+  for (unsigned i = 0, e = Assignments.size(); i != e; ++i)
+    Assignments[i].clear();
+  Assignments.clear();
+
+  return Changed;
+}