Added support for spilling

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

3 files changed, 146 insertions, 8 deletions

diff --git a/lib/CodeGen/RegAlloc/LiveRange.h b/lib/CodeGen/RegAlloc/LiveRange.h
index 0d0f8ae1b8..23c217cd7a 100644
--- a/lib/CodeGen/RegAlloc/LiveRange.h
+++ b/lib/CodeGen/RegAlloc/LiveRange.h
@@ -55,6 +55,11 @@ class LiveRange : public ValueSet
 
   bool CanUseSuggestedCol;
 
+  // if this LR is spilled, its stack offset from *FP*. The spilled offsets
+  // must always be relative to the FP.
+  int SpilledStackOffsetFromFP;
+  bool HasSpillOffset;
+
  public:
 
 
@@ -88,6 +93,33 @@ class LiveRange : public ValueSet
   
   inline void markForSpill() { mustSpill = true; }
 
+  inline bool isMarkedForSpill() { return  mustSpill; }
+
+  inline void setSpillOffFromFP(int StackOffset) {
+    assert( mustSpill && "This LR is not spilled");
+    SpilledStackOffsetFromFP = StackOffset;
+    HasSpillOffset = true;
+  }
+
+  inline void modifySpillOffFromFP(int StackOffset) {
+    assert( mustSpill && "This LR is not spilled");
+    SpilledStackOffsetFromFP = StackOffset;
+    HasSpillOffset = true;
+  }
+
+
+
+  inline bool hasSpillOffset() {
+    return  HasSpillOffset;
+  }
+
+
+  inline int getSpillOffFromFP() const {
+    assert( HasSpillOffset && "This LR is not spilled");
+    return SpilledStackOffsetFromFP;
+  }
+
+
   inline void markForSaveAcrossCalls() { mustSaveAcrossCalls = true; }
 
   // inline void markForLoadFromStack() { mustLoadFromStack = true; 
@@ -135,6 +167,11 @@ class LiveRange : public ValueSet
   }
 
 
+
+
+
+
+
   inline LiveRange() : ValueSet() /* , CallInterferenceList() */
     {
       Color = SuggestedColor = -1;      // not yet colored 
@@ -143,6 +180,7 @@ class LiveRange : public ValueSet
       UserIGNode = NULL;
       doesSpanAcrossCalls = false;
       CanUseSuggestedCol = true;
+      HasSpillOffset  = false;
     }
 
 };
diff --git a/lib/CodeGen/RegAlloc/PhyRegAlloc.h b/lib/CodeGen/RegAlloc/PhyRegAlloc.h
index 306947df81..59de619531 100644
--- a/lib/CodeGen/RegAlloc/PhyRegAlloc.h
+++ b/lib/CodeGen/RegAlloc/PhyRegAlloc.h
@@ -29,8 +29,6 @@
 
 */ 
 
-
-
 #ifndef PHY_REG_ALLOC_H
 #define PHY_REG_ALLOC_H
 
@@ -41,11 +39,21 @@
 
 #include <deque>
 
+
+//----------------------------------------------------------------------------
+// Class AddedInstrns:
+// When register allocator inserts new instructions in to the existing 
+// instruction stream, it does NOT directly modify the instruction stream.
+// Rather, it creates an object of AddedInstrns and stick it in the 
+// AddedInstrMap for an existing instruction. This class contains two vectors
+// to store such instructions added before and after an existing instruction.
+//----------------------------------------------------------------------------
+
 class AddedInstrns
 {
  public:
-  deque<MachineInstr *> InstrnsBefore;
-  deque<MachineInstr *> InstrnsAfter;
+  deque<MachineInstr *> InstrnsBefore;  // Added insts BEFORE an existing inst
+  deque<MachineInstr *> InstrnsAfter;   // Added insts AFTER an existing inst
 
   AddedInstrns() : InstrnsBefore(), InstrnsAfter() { }
 };
@@ -54,6 +62,80 @@ typedef hash_map<const MachineInstr *, AddedInstrns *> AddedInstrMapType;
 
 
 
+//----------------------------------------------------------------------------
+// Class RegStackOffsets:
+// This class is responsible for managing stack frame of the method for
+// register allocation.
+//
+//----------------------------------------------------------------------------
+
+class RegStackOffsets {
+
+ private:
+  int curSpilledVarOff;                 // cur pos of spilled LRs
+  int curNewTmpPosOffset;               // cur pos of tmp values on stack
+  bool isTmpRegionUsable;               // can we call getNewTmpPosOffFromFP
+
+  const int SizeOfStackItem;            // size of an item on stack
+  const int StackSpillStartFromFP;      // start position of spill region
+  int StartOfTmpRegion;                 // start of the tmp var region
+
+ public:
+
+  // constructor  
+
+  RegStackOffsets(int SEnSize=8, int StartSpill=176 ) : 
+    SizeOfStackItem(SEnSize),  StackSpillStartFromFP(StartSpill) {
+
+    curSpilledVarOff = StartSpill;   
+    isTmpRegionUsable = false;
+  };
+
+
+  int getNewSpillOffFromFP() { 
+    int tmp =  curSpilledVarOff;     
+    curSpilledVarOff += SizeOfStackItem;
+    return tmp;   // **TODO: Is sending un-incremented value correct?
+  };
+
+
+  // The following method must be called only after allocating space
+  // for spilled LRs and calling setEndOfSpillRegion()
+  int getNewTmpPosOffFromFP() { 
+    assert( isTmpRegionUsable && "Spill region still open");
+    int tmp = curNewTmpPosOffset;
+    curNewTmpPosOffset += SizeOfStackItem;
+    return tmp; //**TODO: Is sending un-incremented val correct?
+  };
+
+
+  // This method is called when we have allocated space for all spilled
+  // LRs. The tmp region can be used only after a call to this method.
+
+  void setEndOfSpillRegion() {
+    assert(( ! isTmpRegionUsable) && "setEndOfSpillRegion called again");
+    isTmpRegionUsable = true;
+    StartOfTmpRegion = curSpilledVarOff; 
+  }
+  
+
+  // called when temporary values allocated on stack are no longer needed
+  void resetTmpPos() { 
+    curNewTmpPosOffset = StartOfTmpRegion;
+  }
+ 
+
+};
+
+
+
+//----------------------------------------------------------------------------
+// class PhyRegAlloc:
+// Main class the register allocator. Call allocateRegisters() to allocate
+// registers for a Method.
+//----------------------------------------------------------------------------
+
+
 class PhyRegAlloc
 {
 
@@ -71,7 +153,7 @@ class PhyRegAlloc
 
   AddedInstrMapType AddedInstrMap;      // to store instrns added in this phase
 
-
+  RegStackOffsets StackOffsets;
 
   //------- private methods ---------------------------------------------------
 
@@ -81,8 +163,8 @@ class PhyRegAlloc
   void addInterferencesForArgs();
   void createIGNodeListsAndIGs();
   void buildInterferenceGraphs();
-  void insertCallerSavingCode(const MachineInstr *MInst, 
-			      const BasicBlock *BB );
+  //void insertCallerSavingCode(const MachineInstr *MInst, 
+  //			      const BasicBlock *BB );
 
   void setCallInterferences(const MachineInstr *MInst, 
 			    const LiveVarSet *const LVSetAft );
@@ -91,6 +173,12 @@ class PhyRegAlloc
 			 const MachineInstr *DelayedMI );
 
   void markUnusableSugColors();
+  void allocateStackSpace4SpilledLRs();
+
+  RegStackOffsets & getStackOffsets() {
+    return  StackOffsets;
+  }
+
 
   inline void constructLiveRanges() 
     { LRI.constructLiveRanges(); }      
@@ -101,8 +189,14 @@ class PhyRegAlloc
 
   void printLabel(const Value *const Val);
   void printMachineCode();
-  
+
+  friend class UltraSparcRegInfo;
+  void setRegsUsedByThisInst(RegClass *RC, const MachineInstr *MInst );
+  int getRegNotUsedByThisInst(RegClass *RC, const MachineInstr *MInst);
+
+
  public:
+
   PhyRegAlloc(const Method *const M, const TargetMachine& TM, 
 	      MethodLiveVarInfo *const Lvi);
 
@@ -117,5 +211,8 @@ class PhyRegAlloc
 
 
 
+
+
+
 #endif
 
diff --git a/lib/CodeGen/RegAlloc/RegClass.h b/lib/CodeGen/RegAlloc/RegClass.h
index 9f5a46902a..3fb448a5cd 100644
--- a/lib/CodeGen/RegAlloc/RegClass.h
+++ b/lib/CodeGen/RegAlloc/RegClass.h
@@ -100,6 +100,9 @@ class RegClass
     { IG.mergeIGNodesOfLRs(LR1, LR2); }
 
 
+  inline bool * getIsColorUsedArr() { return IsColorUsedArr; }
+
+
   inline void printIGNodeList() const {
     cerr << "IG Nodes for Register Class " << RegClassID << ":" << endl;
     IG.printIGNodeList();