--added suggesting colors; call/ret arg handling

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

2 files changed, 235 insertions, 48 deletions

diff --git a/lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp b/lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp
index 658f3d2..4d3e925 100644
--- a/lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp
+++ b/lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp
@@ -4,12 +4,15 @@ LiveRangeInfo::LiveRangeInfo(const Method *const M,
 			     const TargetMachine& tm,
 			     vector<RegClass *> &RCL) 
                              : Meth(M), LiveRangeMap(), 
-			       TM(tm), RegClassList(RCL)
+			       TM(tm), RegClassList(RCL),
+			       MRI( tm.getRegInfo()),
+			       CallRetInstrList()
 { }
 
 
 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
-// Note: the caller must make sure that L1 and L2 are distinct
+// Note: the caller must make sure that L1 and L2 are distinct and both
+// LRs don't have suggested colors
 
 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *const L1, LiveRange *L2)
 {
@@ -24,6 +27,15 @@ void LiveRangeInfo::unionAndUpdateLRs(LiveRange *const L1, LiveRange *L2)
     L1->add( *L2It );            // add the var in L2 to L1
     LiveRangeMap[ *L2It ] = L1;  // now the elements in L2 should map to L1    
   }
+
+
+  // Now if LROfDef(L1) has a suggested color, it will remain.
+  // But, if LROfUse(L2) has a suggested color, the new range
+  // must have the same color.
+
+  if(L2->hasSuggestedColor())
+    L1->setSuggestedColor( L2->getSuggestedColor() );
+
   delete ( L2 );                 // delete L2 as it is no longer needed
 }
 
@@ -58,7 +70,7 @@ void LiveRangeInfo::constructLiveRanges()
     // create a temp machine op to find the register class of value
     //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
 
-    unsigned rcid = (TM.getRegInfo()).getRegClassIDOfValue( Val );
+    unsigned rcid = MRI.getRegClassIDOfValue( Val );
     ArgRange->setRegClass(RegClassList[ rcid ] );
 
     			   
@@ -68,16 +80,24 @@ void LiveRangeInfo::constructLiveRanges()
     }
   }
 
+  // Now suggest hardware registers for these method args 
+  MRI.suggestRegs4MethodArgs(Meth, *this);
+
+
+
+  // Now find speical LLVM instructions (CALL, RET) and LRs in machine
+  // instructions.
 
-  // Now find all LRs for machine the instructions. A new LR will be created 
-  // only for defs in the machine instr since, we assume that all Values are
-  // defined before they are used. However, there can be multiple defs for
-  // the same Value in machine instructions.
 
   Method::const_iterator BBI = Meth->begin();    // random iterator for BBs   
 
   for( ; BBI != Meth->end(); ++BBI) {            // go thru BBs in random order
 
+    // Now find all LRs for machine the instructions. A new LR will be created 
+    // only for defs in the machine instr since, we assume that all Values are
+    // defined before they are used. However, there can be multiple defs for
+    // the same Value in machine instructions.
+
     // get the iterator for machine instructions
     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
     MachineCodeForBasicBlock::const_iterator 
@@ -87,12 +107,20 @@ void LiveRangeInfo::constructLiveRanges()
     for( ; MInstIterator != MIVec.end(); MInstIterator++) {  
       
       const MachineInstr * MInst = *MInstIterator; 
+
+      // Now if the machine instruction has special operands that must be
+      // set with a "suggested color", do it here.
+
+
+      if(  MRI.handleSpecialMInstr(MInst, *this, RegClassList) )
+	continue;
+       
       
       // iterate over  MI operands to find defs
-      for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); OpI++) {
+      for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) {
 	
 
-	// delete later from here ************
+      	// delete later from here ************
 	MachineOperand::MachineOperandType OpTyp = 
 	  OpI.getMachineOperand().getOperandType();
 
@@ -104,11 +132,21 @@ void LiveRangeInfo::constructLiveRanges()
 	// ************* to here
 
 
-
 	// create a new LR iff this operand is a def
 	if( OpI.isDef() ) {     
 	  
 	  const Value *const Def = *OpI;
+
+
+	  // Only instruction values are accepted for live ranges here
+
+	  if( Def->getValueType() != Value::InstructionVal ) {
+	    cout << "\n**%%Error: Def is not an instruction val. Def=";
+	    printValue( Def ); cout << endl;
+	    continue;
+	  }
+
+
 	  LiveRange *DefRange = LiveRangeMap[Def]; 
 
 	  // see LR already there (because of multiple defs)
@@ -130,7 +168,7 @@ void LiveRangeInfo::constructLiveRanges()
 	      OpI.getMachineOperand().getOperandType();
 
 	    bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
-	    unsigned rcid = (TM.getRegInfo()).getRegClassIDOfValue( 
+	    unsigned rcid = MRI.getRegClassIDOfValue( 
 			    OpI.getMachineOperand().getVRegValue(), isCC );
 
 
@@ -163,6 +201,42 @@ void LiveRangeInfo::constructLiveRanges()
 
     } // for all machine instructions in the BB
 
+
+  } // for all BBs in method
+  
+  // go thru LLVM instructions in the basic block and suggest colors
+  // for their args. Also  record all CALL 
+  // instructions and Return instructions in the CallRetInstrList
+  // This is done because since there are no reverse pointers in machine
+  // instructions to find the llvm instruction, when we encounter a call
+  // or a return whose args must be specailly colored (e.g., %o's for args)
+  // We have to makes sure that all LRs of call/ret args are added before 
+  // doing this. But return value of call will not have a LR.
+
+  BBI = Meth->begin();                  // random iterator for BBs   
+
+  for( ; BBI != Meth->end(); ++BBI) {   // go thru BBs in random order
+
+    BasicBlock::const_iterator InstIt = (*BBI)->begin();
+
+    for( ; InstIt != (*BBI)->end() ; ++InstIt) {
+
+      const Instruction *const CallRetI = *InstIt;
+      unsigned OpCode =  (CallRetI)->getOpcode();
+      
+      if( (OpCode == Instruction::Call) ) {
+	CallRetInstrList.push_back(CallRetI );      
+	MRI.suggestRegs4CallArgs( (CallInst *) CallRetI, *this, RegClassList );
+      }
+
+      else if (OpCode == Instruction::Ret ) {
+	CallRetInstrList.push_back( CallRetI );  
+	MRI.suggestReg4RetValue( (ReturnInst *) CallRetI, *this);
+      }
+
+
+    } // for each llvm instr in BB
+
   } // for all BBs in method
 
   if( DEBUG_RA) 
@@ -183,7 +257,8 @@ void LiveRangeInfo::coalesceLRs()
            if the def and op are of the same type
 	     if the def and op do not interfere //i.e., not simultaneously live
 	       if (degree(LR of def) + degree(LR of op)) <= # avail regs
-		 merge2IGNodes(def, op) // i.e., merge 2 LRs 
+	         if both LRs do not have suggested colors
+		    merge2IGNodes(def, op) // i.e., merge 2 LRs 
 
 */
 
@@ -253,8 +328,14 @@ void LiveRangeInfo::coalesceLRs()
 
 		if( CombinedDegree <= RCOfDef->getNumOfAvailRegs() ) {
 
-		  RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
-		  unionAndUpdateLRs(LROfDef, LROfUse);
+		  // if both LRs do not have suggested colors
+		  if( ! (LROfDef->hasSuggestedColor() &&  
+		         LROfUse->hasSuggestedColor() ) ) {
+		    
+		    RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
+		    unionAndUpdateLRs(LROfDef, LROfUse);
+		  }
+
 
 		} // if combined degree is less than # of regs
 
@@ -289,7 +370,7 @@ void LiveRangeInfo::printLiveRanges()
   LiveRangeMapType::iterator HMI = LiveRangeMap.begin();   // hash map iterator
   cout << endl << "Printing Live Ranges from Hash Map:" << endl;
   for( ; HMI != LiveRangeMap.end() ; HMI ++ ) {
-    if( (*HMI).first ) {
+    if( (*HMI).first && (*HMI).second ) {
       cout <<" "; printValue((*HMI).first);  cout  << "\t: "; 
       ((*HMI).second)->printSet(); cout << endl;
     }
diff --git a/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp
index 1cb1809..832e482 100644
--- a/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp
+++ b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp
@@ -17,8 +17,6 @@ PhyRegAlloc::PhyRegAlloc(const Method *const M,
 			  Meth(M), TM(tm), LVI(Lvi), LRI(M, tm, RegClassList), 
 			  MRI( tm.getRegInfo() ),
                           NumOfRegClasses(MRI.getNumOfRegClasses()),
-			  CallInstrList(),
-			  RetInstrList(),
 			  AddedInstrMap()
 
 {
@@ -47,10 +45,18 @@ void PhyRegAlloc::createIGNodeListsAndIGs()
   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();   
 
     for(  ; HMI != HMIEnd ; ++HMI ) {
+      
+      if( (*HMI).first ) { 
 
-     LiveRange *L = (*HMI).second;      // get the LiveRange
+	LiveRange *L = (*HMI).second;      // get the LiveRange
 
-     if( (*HMI).first ) { 
+	if( !L) { 
+	  if( DEBUG_RA) {
+	    cout << "\n*?!?Warning: Null liver range found for: ";
+	    printValue( (*HMI).first) ; cout << endl;
+	  }
+	  continue;
+	}
                                         // if the Value * is not null, and LR  
                                         // is not yet written to the IGNodeList
        if( !(L->getUserIGNode())  ) {  
@@ -155,7 +161,7 @@ void PhyRegAlloc::buildInterferenceGraphs()
 
     // iterate over all the machine instructions in BB
     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {  
-      
+
       const MachineInstr *const MInst = *MInstIterator; 
 
       // get the LV set after the instruction
@@ -178,6 +184,8 @@ void PhyRegAlloc::buildInterferenceGraphs()
     } // for all machine instructions in BB
 
 
+#if 0
+
     // go thru LLVM instructions in the basic block and record all CALL
     // instructions and Return instructions in the CallInstrList
     // This is done because since there are no reverse pointers in machine
@@ -194,6 +202,9 @@ void PhyRegAlloc::buildInterferenceGraphs()
       else if( OpCode == Instruction::Ret )
 	RetInstrList.push_back( *InstIt );
    }
+
+#endif
+
     
   } // for all BBs in method
 
@@ -257,7 +268,38 @@ void PhyRegAlloc::updateMachineCode()
     // iterate over all the machine instructions in BB
     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {  
       
-      MachineInstr *const MInst = *MInstIterator; 
+      MachineInstr *MInst = *MInstIterator; 
+
+
+      // If there are instructions before to be added, add them now
+      // ***TODO: Add InstrnsAfter as well
+      if( AddedInstrMap[ MInst ] ) {
+
+	vector<MachineInstr *> &IBef =
+	  (AddedInstrMap[MInst])->InstrnsBefore;
+
+	if( ! IBef.empty() ) {
+
+	  vector<MachineInstr *>::iterator AdIt; 
+
+	  for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) {
+
+	    cout << "*ADDED instr opcode: ";
+	    cout << TargetInstrDescriptors[(*AdIt)->getOpCode()].opCodeString;
+	    cout << endl;
+	    
+	    MInstIterator = MIVec.insert( MInstIterator, *AdIt );
+	    ++MInstIterator;
+	  }
+
+	}
+
+	// restart from the topmost instruction added
+	//MInst = *MInstIterator;
+
+      }
+
+
 
       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 
@@ -289,8 +331,9 @@ void PhyRegAlloc::updateMachineCode()
               cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
             }
 
-	    Op.setRegForValue( -1 );  // mark register as invalid
+	    Op.setRegForValue( 1000 ); // mark register as invalid
 	    
+#if 0
 	    if(  ((Val->getType())->isLabelType()) || 
 		 (Val->getValueType() == Value::ConstantVal)  )
 	      ;                         // do nothing
@@ -308,14 +351,16 @@ void PhyRegAlloc::updateMachineCode()
  	      Op.setRegForValue( MRI.getReturnAddressReg() );
 
 	    }
-	    
-	    else
+
+	    if (Val->getValueType() == Value::InstructionVal)
 	    {
 	      cout << "!Warning: No LiveRange for: ";
 	      printValue( Val); cout << " Type: " << Val->getValueType();
 	      cout << " RegVal=" <<  Op.getAllocatedRegNum() << endl;
 	    }
 
+#endif
+
 	    continue;
 	  }
 	
@@ -376,8 +421,6 @@ void PhyRegAlloc::printMachineCode()
 	    Op.getOperandType() ==  MachineOperand::MO_CCRegister || 
 	    Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp ) {
 
-
-
 	  const Value *const Val = Op.getVRegValue () ;
 	  // ****this code is temporary till NULL Values are fixed
 	  if( ! Val ) {
@@ -386,8 +429,7 @@ void PhyRegAlloc::printMachineCode()
 	  }
 
 	  // if a label or a constant
-	  if( (Val->getValueType() == Value::BasicBlockVal) || 
-	      (Val->getValueType() == Value::ConstantVal) ) {
+	  if( (Val->getValueType() == Value::BasicBlockVal)  ) {
 
 	    cout << "\t"; printLabel(	Op.getVRegValue	() );
 	  }
@@ -395,7 +437,10 @@ void PhyRegAlloc::printMachineCode()
 	    // else it must be a register value
 	    const int RegNum = Op.getAllocatedRegNum();
 
+	    //if( RegNum != 1000)
+
 	      cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
+	    // else cout << "\t<*NoReg*>";
 
 	  }
 
@@ -418,6 +463,67 @@ void PhyRegAlloc::printMachineCode()
 }
 
 
+//----------------------------------------------------------------------------
+//
+//----------------------------------------------------------------------------
+
+void PhyRegAlloc::colorCallRetArgs()
+{
+
+  CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList();
+  CallRetInstrListType::const_iterator It = CallRetInstList.begin();
+
+  for( ; It != CallRetInstList.end(); ++It ) {
+
+    const Instruction *const CallRetI = *It;
+    unsigned OpCode =  (CallRetI)->getOpcode();
+ 
+    const MachineInstr *CRMI = *((CallRetI->getMachineInstrVec()).begin());
+
+    
+    assert( (TM.getInstrInfo().isReturn(CRMI->getOpCode()) ||  
+	     TM.getInstrInfo().isCall(CRMI->getOpCode()) )
+	    && "First Machine Instruction is not a Call/Retrunr" );
+    
+    // get the added instructions for this Call/Ret instruciton
+    AddedInstrns *AI = AddedInstrMap[ CRMI ];
+    if ( !AI ) { 
+      AI = new AddedInstrns();
+      AddedInstrMap[ CRMI ] = AI;
+    }
+
+    if( (OpCode == Instruction::Call) )
+        MRI.colorCallArgs( (CallInst *) CallRetI, LRI, AI );
+    
+
+    else if (OpCode == Instruction::Ret ) 
+      MRI.colorRetValue( (ReturnInst *) CallRetI, LRI, AI	);
+    
+
+    else assert( 0 && "Non Call/Ret instrn in CallRetInstrList\n" );
+
+  }
+
+}
+
+//----------------------------------------------------------------------------
+
+//----------------------------------------------------------------------------
+void PhyRegAlloc::colorIncomingArgs()
+{
+  const BasicBlock *const FirstBB = Meth->front();
+  const MachineInstr *FirstMI = *((FirstBB->getMachineInstrVec()).begin());
+  assert( FirstMI && "No machine instruction in entry BB");
+
+  AddedInstrns *AI = AddedInstrMap[ FirstMI ];
+  if ( !AI ) { 
+    AI = new AddedInstrns();
+    AddedInstrMap[ FirstMI  ] = AI;
+  }
+
+  MRI.colorMethodArgs(Meth, LRI, AI );
+}
+
 
 //----------------------------------------------------------------------------
 // Used to generate a label for a basic block
@@ -437,56 +543,56 @@ void PhyRegAlloc::printLabel(const Value *const Val)
 
 void PhyRegAlloc::allocateRegisters()
 {
+
+  // make sure that we put all register classes into the RegClassList 
+  // before we call constructLiveRanges (now done in the constructor of 
+  // PhyRegAlloc class).
+
   constructLiveRanges();                // create LR info
 
-  if( DEBUG_RA)
+  if( DEBUG_RA )
     LRI.printLiveRanges();
-
+  
   createIGNodeListsAndIGs();            // create IGNode list and IGs
 
   buildInterferenceGraphs();            // build IGs in all reg classes
-
   
-  if( DEBUG_RA) {
+  
+  if( DEBUG_RA ) {
     // print all LRs in all reg classes
     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)  
       RegClassList[ rc ]->printIGNodeList(); 
-
+    
     // print IGs in all register classes
     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)  
       RegClassList[ rc ]->printIG();       
   }
-
+  
   LRI.coalesceLRs();                    // coalesce all live ranges
-
+  
   if( DEBUG_RA) {
     // print all LRs in all reg classes
     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)  
       RegClassList[ rc ]->printIGNodeList(); 
-
+    
     // print IGs in all register classes
     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)  
       RegClassList[ rc ]->printIG();       
   }
 
+  // color all register classes
+  for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)  
+    RegClassList[ rc ]->colorAllRegs();    
 
-  // the following three calls must be made in that order since
-  // coloring or definitions must come before their uses
-  MRI.colorArgs(Meth, LRI);             // color method args
-                                        // color call args of call instrns
-  MRI.colorCallArgs(CallInstrList, LRI, AddedInstrMap); 
-                                        // color return args
-  MRI.colorRetArg(CallInstrList, LRI, AddedInstrMap);
 
-  
+  // color incoming args and call args
+  colorIncomingArgs();
+  colorCallRetArgs();
 
-                                        // color all register classes
-  for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)  
-    RegClassList[ rc ]->colorAllRegs();    
 
   updateMachineCode(); 
   if (DEBUG_RA) {
-    PrintMachineInstructions(Meth);
+    // PrintMachineInstructions(Meth);
     printMachineCode();                   // only for DEBUGGING
   }
 }