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

4 files changed, 111 insertions, 9 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