Added support for spilling

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

9 files changed, 550 insertions, 106 deletions

diff --git a/include/llvm/CodeGen/RegClass.h b/include/llvm/CodeGen/RegClass.h
index 9f5a46902a..3fb448a5cd 100644
--- a/include/llvm/CodeGen/RegClass.h
+++ b/include/llvm/CodeGen/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(); 
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(); 
diff --git a/lib/Target/SparcV9/RegAlloc/LiveRange.h b/lib/Target/SparcV9/RegAlloc/LiveRange.h
index 0d0f8ae1b8..23c217cd7a 100644
--- a/lib/Target/SparcV9/RegAlloc/LiveRange.h
+++ b/lib/Target/SparcV9/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/Target/SparcV9/RegAlloc/PhyRegAlloc.h b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h
index 306947df81..59de619531 100644
--- a/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h
+++ b/lib/Target/SparcV9/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/Target/SparcV9/RegAlloc/RegClass.h b/lib/Target/SparcV9/RegAlloc/RegClass.h
index 9f5a46902a..3fb448a5cd 100644
--- a/lib/Target/SparcV9/RegAlloc/RegClass.h
+++ b/lib/Target/SparcV9/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(); 
diff --git a/lib/Target/SparcV9/SparcV9Internals.h b/lib/Target/SparcV9/SparcV9Internals.h
index 3564251607..653a2018a7 100644
--- a/lib/Target/SparcV9/SparcV9Internals.h
+++ b/lib/Target/SparcV9/SparcV9Internals.h
@@ -113,9 +113,17 @@ public:
 
 
 
+
+
+//----------------------------------------------------------------------------
+// class UltraSparcRegInfo
+//
+//----------------------------------------------------------------------------
+
+
 class LiveRange;
 class UltraSparc;
-
+class PhyRegAlloc;
 
 
 class UltraSparcRegInfo : public MachineRegInfo
@@ -144,6 +152,9 @@ class UltraSparcRegInfo : public MachineRegInfo
     FloatCCRegType
   };
 
+  // the size of a value (int, float, etc..) stored in the stack frame
+  
+
 
   // WARNING: If the above enum order must be changed, also modify 
   // getRegisterClassOfValue method below since it assumes this particular 
@@ -158,6 +169,9 @@ class UltraSparcRegInfo : public MachineRegInfo
   unsigned const NumOfIntArgRegs;
   unsigned const NumOfFloatArgRegs;
   int const InvalidRegNum;
+  int SizeOfOperandOnStack;
+
+
 
   //void setCallArgColor(LiveRange *const LR, const unsigned RegNo) const;
 
@@ -246,7 +260,8 @@ class UltraSparcRegInfo : public MachineRegInfo
   UltraSparcRegInfo(const UltraSparc *const USI ) : UltraSparcInfo(USI), 
 						    NumOfIntArgRegs(6), 
 						    NumOfFloatArgRegs(32),
-						    InvalidRegNum(1000)
+						    InvalidRegNum(1000),
+						    SizeOfOperandOnStack(8)
   {    
     MachineRegClassArr.push_back( new SparcIntRegClass(IntRegClassID) );
     MachineRegClassArr.push_back( new SparcFloatRegClass(FloatRegClassID) );
@@ -255,6 +270,7 @@ class UltraSparcRegInfo : public MachineRegInfo
 
     assert( SparcFloatRegOrder::StartOfNonVolatileRegs == 32 && 
 	    "32 Float regs are used for float arg passing");
+
   }
 
   // ***** TODO  Delete
@@ -317,7 +333,7 @@ class UltraSparcRegInfo : public MachineRegInfo
 		       AddedInstrns *const FirstAI) const;
 
   void colorCallArgs(const MachineInstr *const CallMI, LiveRangeInfo& LRI,
-		     AddedInstrns *const CallAI) const;
+		     AddedInstrns *const CallAI,  PhyRegAlloc &PRA) const;
 
   void colorRetValue(const MachineInstr *const RetI,   LiveRangeInfo& LRI,
 		     AddedInstrns *const RetAI) const;
@@ -402,6 +418,11 @@ class UltraSparcRegInfo : public MachineRegInfo
     return InvalidRegNum;
   }
 
+
+  void insertCallerSavingCode(const MachineInstr *MInst, 
+			      const BasicBlock *BB, PhyRegAlloc &PRA ) const;
+
+
 };
 
 
@@ -1115,7 +1136,9 @@ public:
   static const int FirstOutgoingArgOffsetFromSP            = 128;
   static const int FirstOptionalOutgoingArgOffsetFromSP    = 176;
   static const int StaticStackAreaOffsetFromFP             =  -1;
-  
+
+  static const int FirstIncomingArgOffsetFromFP           = 126;
+
   static int       getFirstAutomaticVarOffsetFromFP (const Method* method);
   static int       getRegSpillAreaOffsetFromFP      (const Method* method);
   static int       getFrameSizeBelowDynamicArea     (const Method* method);
diff --git a/lib/Target/SparcV9/SparcV9RegInfo.cpp b/lib/Target/SparcV9/SparcV9RegInfo.cpp
index dfb5517696..11180f5995 100644
--- a/lib/Target/SparcV9/SparcV9RegInfo.cpp
+++ b/lib/Target/SparcV9/SparcV9RegInfo.cpp
@@ -129,7 +129,7 @@ UltraSparcRegInfo::getCallInstNumArgs(const MachineInstr *CallMI) const {
   assert( (NumArgs != -1)  && "Internal error in getCallInstNumArgs" );
   return (unsigned) NumArgs;
  
-
+  
 }
 
 
@@ -321,20 +321,56 @@ void UltraSparcRegInfo::colorMethodArgs(const Method *const Meth,
       if( isArgInReg ) 
 	AdMI = cpReg2RegMI( UniArgReg, UniLRReg, RegType );
 
-      else 
-	assert(0 && "TODO: Color an Incoming arg on stack");
+      else {
 
-      // Now add the instruction
-      FirstAI->InstrnsBefore.push_back( AdMI );
+	// Now the arg is coming on stack. Since the LR recieved a register,
+	// we just have to load the arg on stack into that register
+	int ArgStakOffFromFP = 
+	  UltraSparcFrameInfo::FirstIncomingArgOffsetFromFP + 
+	  argNo * SizeOfOperandOnStack;
 
-    }
+	AdMI = cpMem2RegMI(getFramePointer(), ArgStakOffFromFP, 
+			   UniLRReg, RegType );
+      }
 
-    else {                                // LR is not colored (i.e., spilled)
-      
-      assert(0 && "TODO: Color a spilled arg ");
+      FirstAI->InstrnsBefore.push_back( AdMI );   
       
-    }
+    } // if LR received a color
+
+    else {                             
+
+      // Now, the LR did not receive a color. But it has a stack offset for
+      // spilling.
+
+      // So, if the arg is coming in UniArgReg register,  we can just move
+      // that on to the stack pos of LR
+
+
+      if( isArgInReg ) {
 
+	MachineInstr *AdIBef = 
+	  cpReg2MemMI(UniArgReg, getFramePointer(), 
+		      LR->getSpillOffFromFP(), RegType );
+
+	FirstAI->InstrnsBefore.push_back( AdMI );   
+      }
+
+      else {
+
+	// Now the arg is coming on stack. Since the LR did NOT 
+	// recieved a register as well, it is allocated a stack position. We
+	// can simply change the stack poistion of the LR. We can do this,
+	// since this method is called before any other method that makes
+	// uses of the stack pos of the LR (e.g., updateMachineInstr)
+
+	int ArgStakOffFromFP = 
+	  UltraSparcFrameInfo::FirstIncomingArgOffsetFromFP + 
+	  argNo * SizeOfOperandOnStack;
+
+	LR->modifySpillOffFromFP( ArgStakOffFromFP );
+      }
+
+    }
 
   }  // for each incoming argument
 
@@ -452,10 +488,10 @@ void UltraSparcRegInfo::suggestRegs4CallArgs(const MachineInstr *const CallMI,
 // to instert copy instructions.
 //---------------------------------------------------------------------------
 
-
 void UltraSparcRegInfo::colorCallArgs(const MachineInstr *const CallMI,
 				      LiveRangeInfo& LRI,
-				      AddedInstrns *const CallAI) const {
+				      AddedInstrns *const CallAI,
+				      PhyRegAlloc &PRA) const {
 
   assert ( (UltraSparcInfo->getInstrInfo()).isCall(CallMI->getOpCode()) );
 
@@ -502,30 +538,33 @@ void UltraSparcRegInfo::colorCallArgs(const MachineInstr *const CallMI,
     // put copy instruction
     
     if( !recvCorrectColor ) {
+
+      unsigned RegType = getRegType( RetValLR );
+
+      // the  reg that LR must be colored with 
+      unsigned UniRetReg = getUnifiedRegNum( RegClassID, CorrectCol);	
       
       if( RetValLR->hasColor() ) {
 	
-	unsigned RegType = getRegType( RetValLR );
-
 	unsigned 
 	  UniRetLRReg=getUnifiedRegNum(RegClassID,RetValLR->getColor());
-
-	// the  reg that LR must be colored with
-	unsigned UniRetReg = getUnifiedRegNum( RegClassID, CorrectCol);	
 	
 	// the return value is coming in UniRetReg but has to go into
 	// the UniRetLRReg
 
 	AdMI = cpReg2RegMI( UniRetReg, UniRetLRReg, RegType ); 	
-	CallAI->InstrnsAfter.push_back( AdMI );
-	
-	
+
       } // if LR has color
       else {
+
+	// if the LR did NOT receive a color, we have to move the return
+	// value coming in UniRetReg to the stack pos of spilled LR
 	
-	assert(0 && "LR of return value is splilled");
+	AdMI = 	cpReg2MemMI(UniRetReg, getFramePointer(), 
+			    RetValLR->getSpillOffFromFP(), RegType );
       }
-      
+
+      CallAI->InstrnsAfter.push_back( AdMI );
       
     } // the LR didn't receive the suggested color  
     
@@ -600,18 +639,74 @@ void UltraSparcRegInfo::colorCallArgs(const MachineInstr *const CallMI,
       if( isArgInReg ) 
 	AdMI = cpReg2RegMI(UniLRReg, UniArgReg, RegType );
 
-      else 
-	assert(0 && "TODO: Push an outgoing arg on stack");
+      else {
+	// Now, we have to pass the arg on stack. Since LR received a register
+	// we just have to move that register to the stack position where
+	// the argument must be passed
 
-      // Now add the instruction
-      CallAI->InstrnsBefore.push_back( AdMI );
+	int ArgStakOffFromSP = 
+	  UltraSparcFrameInfo::FirstOutgoingArgOffsetFromSP + 
+	  argNo * SizeOfOperandOnStack;
 
+	AdMI = cpReg2MemMI(UniLRReg, getStackPointer(), ArgStakOffFromSP, 
+			   RegType );
+      }
+
+      CallAI->InstrnsBefore.push_back( AdMI );  // Now add the instruction
     }
 
-    else {                                // LR is not colored (i.e., spilled)
-      
-      assert(0 && "TODO: Copy a spilled call arg to an output reg ");
+    else {                          // LR is not colored (i.e., spilled)      
       
+      if( isArgInReg ) {
+
+	// Now the LR did NOT recieve a register but has a stack poistion.
+	// Since, the outgoing arg goes in a register we just have to insert
+	// a load instruction to load the LR to outgoing register
+
+
+	AdMI = cpMem2RegMI(getStackPointer(), LR->getSpillOffFromFP(),
+			   UniArgReg, RegType );
+
+	CallAI->InstrnsBefore.push_back( AdMI );  // Now add the instruction
+      }
+
+      else {
+	// Now, we have to pass the arg on stack. Since LR  also did NOT
+	// receive a register we have to move an argument in memory to 
+	// outgoing parameter on stack.
+	
+	// Optoimize: Optimize when reverse pointers in MahineInstr are
+	// introduced. 
+	// call PRA.getUnusedRegAtMI(....) to get an unused reg. Only if this
+	// fails, then use the following code. Currently, we cannot call the
+	// above method since we cannot find LVSetBefore without the BB 
+	
+	int TReg = PRA.getRegNotUsedByThisInst( LR->getRegClass(), CallMI );
+	int TmpOff = PRA.getStackOffsets().getNewTmpPosOffFromFP();
+	int ArgStakOffFromSP = 
+	  UltraSparcFrameInfo::FirstOutgoingArgOffsetFromSP + 
+	  argNo * SizeOfOperandOnStack;
+
+	MachineInstr *Ad1, *Ad2, *Ad3, *Ad4;
+
+	// Sequence:
+	// (1) Save TReg on stack    
+	// (2) Load LR value into TReg from stack pos of LR
+	// (3) Store Treg on outgoing Arg pos on stack
+	// (4) Load the old value of TReg from stack to TReg (restore it)
+
+	Ad1 = cpReg2MemMI(TReg, getFramePointer(), TmpOff, RegType );
+	Ad2 = cpMem2RegMI(getFramePointer(), LR->getSpillOffFromFP(), 
+			  TReg, RegType ); 
+	Ad3 = cpReg2MemMI(TReg, getStackPointer(), ArgStakOffFromSP, RegType );
+	Ad4 = cpMem2RegMI(getFramePointer(), TmpOff, TReg, RegType ); 
+
+	CallAI->InstrnsBefore.push_back( Ad1 );  
+	CallAI->InstrnsBefore.push_back( Ad2 );  
+	CallAI->InstrnsBefore.push_back( Ad3 );  
+	CallAI->InstrnsBefore.push_back( Ad4 );  
+      }
+
     }
 
   }  // for each parameter in call instruction
@@ -658,9 +753,14 @@ void UltraSparcRegInfo::suggestReg4RetValue(const MachineInstr *const RetMI,
 
 }
 
-//---------------------------------------------------------------------------
+
 
 //---------------------------------------------------------------------------
+// Colors the return value of a method to %i0 or %f0, if possible. If it is
+// not possilbe to directly color the LR, insert a copy instruction to move
+// the LR to %i0 or %f0. When the LR is spilled, instead of the copy, we 
+// have to put a load instruction.
+//---------------------------------------------------------------------------
 void UltraSparcRegInfo::colorRetValue(const  MachineInstr *const RetMI, 
 				      LiveRangeInfo& LRI,
 				      AddedInstrns *const RetAI) const {
@@ -682,7 +782,7 @@ void UltraSparcRegInfo::colorRetValue(const  MachineInstr *const RetMI,
 	cerr << endl;
 	// assert( LR && "No LR for return value of non-void method");
 	return;
-   }
+    }
 
     unsigned RegClassID =  getRegClassIDOfValue(RetVal);
     unsigned RegType = getRegType( RetVal );
@@ -720,9 +820,14 @@ void UltraSparcRegInfo::colorRetValue(const  MachineInstr *const RetMI,
       AdMI = cpReg2RegMI( UniLRReg, UniRetReg, RegType); 
       RetAI->InstrnsBefore.push_back( AdMI );
     }
-    else 
-      assert(0 && "TODO: Copy the return value from stack\n");
+    else {                              // if the LR is spilled
 
+      AdMI = cpMem2RegMI(getFramePointer(), LR->getSpillOffFromFP(), 
+			 UniRetReg, RegType); 
+      RetAI->InstrnsBefore.push_back( AdMI );
+      cout << "\nCopied the return value from stack";
+    }
+  
   } // if there is a return value
 
 }
@@ -878,80 +983,115 @@ MachineInstr * UltraSparcRegInfo::cpMem2RegMI(const unsigned SrcPtrReg,
 
 
 
+//----------------------------------------------------------------------------
+// This method inserts caller saving/restoring instructons before/after
+// a call machine instruction.
+//----------------------------------------------------------------------------
 
 
+void UltraSparcRegInfo::insertCallerSavingCode(const MachineInstr *MInst, 
+					       const BasicBlock *BB,
+					       PhyRegAlloc &PRA) const {
+  // assert( (getInstrInfo()).isCall( MInst->getOpCode() ) );
 
-//---------------------------------------------------------------------------
-// Only  constant/label values are accepted.
-// ***This code is temporary ***
-//---------------------------------------------------------------------------
+ 
+  PRA.StackOffsets.resetTmpPos();
 
+  hash_set<unsigned> PushedRegSet;
 
-MachineInstr * UltraSparcRegInfo::cpValue2RegMI(Value * Val, 
-						const unsigned DestReg,
-						const int RegType) const {
+  // Now find the LR of the return value of the call
+  // The last *implicit operand* is the return value of a call
+  // Insert it to to he PushedRegSet since we must not save that register
+  // and restore it after the call.
+  // We do this because, we look at the LV set *after* the instruction
+  // to determine, which LRs must be saved across calls. The return value
+  // of the call is live in this set - but we must not save/restore it.
 
-  assert( ((int)DestReg != InvalidRegNum) && "Invalid Register");
 
-  /*
-  unsigned MReg;
-  int64_t Imm;
+  const Value *RetVal = getCallInstRetVal( MInst );
 
-  MachineOperand::MachineOperandType MOTypeInt = 
-    ChooseRegOrImmed(Val, ADD,  *UltraSparcInfo, true, MReg, Imm);
-  */
+  if( RetVal ) {
 
-  MachineOperand::MachineOperandType MOType;
+    LiveRange *RetValLR = PRA.LRI.getLiveRangeForValue( RetVal );
+    assert( RetValLR && "No LR for RetValue of call");
 
-  switch( Val->getValueType() ) {
+    PushedRegSet.insert(
+			getUnifiedRegNum((RetValLR->getRegClass())->getID(), 
+				      RetValLR->getColor() ) );
+  }
 
-  case Value::ConstantVal: 
-  case Value::GlobalVariableVal:
-    MOType = MachineOperand:: MO_UnextendedImmed;  // TODO**** correct???
-    break;
 
-  case Value::BasicBlockVal:
-  case Value::MethodVal:
-    MOType = MachineOperand::MO_PCRelativeDisp;
-    break;
+  const LiveVarSet *LVSetAft =  PRA.LVI->getLiveVarSetAfterMInst(MInst, BB);
 
-  default:
-    cerr << "Value Type: " << Val->getValueType() << endl;
-    assert(0 && "Unknown val type - Only constants/globals/labels are valid");
-  }
+  LiveVarSet::const_iterator LIt = LVSetAft->begin();
 
+  // for each live var in live variable set after machine inst
+  for( ; LIt != LVSetAft->end(); ++LIt) {
 
+   //  get the live range corresponding to live var
+    LiveRange *const LR = PRA.LRI.getLiveRangeForValue(*LIt );    
 
-  MachineInstr * MI = NULL;
+    // LR can be null if it is a const since a const 
+    // doesn't have a dominating def - see Assumptions above
+    if( LR )   {  
+      
+      if( LR->hasColor() ) {
 
-  switch( RegType ) {
-    
-  case IntRegType:
-    MI = new MachineInstr(ADD);
-    MI->SetMachineOperand(0, MOType, Val, false);
-    MI->SetMachineOperand(1, SparcIntRegOrder::g0, false);
-    MI->SetMachineOperand(2, DestReg, true);
-    break;
+	unsigned RCID = (LR->getRegClass())->getID();
+	unsigned Color = LR->getColor();
 
-  case FPSingleRegType:
-    assert(0 && "FP const move not yet implemented");
-    MI = new MachineInstr(FMOVS);
-    MI->SetMachineOperand(0, MachineOperand::MO_SignExtendedImmed, Val, false);
-    MI->SetMachineOperand(1, DestReg, true);
-    brea