--added suggesting colors; call/ret arg handling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@670 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/RegAlloc/LiveRangeInfo.cpp b/lib/CodeGen/RegAlloc/LiveRangeInfo.cpp
index 658f3d2..4d3e925 100644
--- a/lib/CodeGen/RegAlloc/LiveRangeInfo.cpp
+++ b/lib/CodeGen/RegAlloc/LiveRangeInfo.cpp
@@ -4,12 +4,15 @@
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 @@
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 @@
// 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 @@
}
}
+ // Now suggest hardware registers for these method args
+ MRI.suggestRegs4MethodArgs(Meth, *this);
- // 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.
+
+
+ // Now find speical LLVM instructions (CALL, RET) and LRs 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 @@
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 @@
// ************* 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 @@
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 @@
} // 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 @@
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 @@
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 @@
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/CodeGen/RegAlloc/PhyRegAlloc.cpp b/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp
index 1cb1809..832e482 100644
--- a/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp
+++ b/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp
@@ -17,8 +17,6 @@
Meth(M), TM(tm), LVI(Lvi), LRI(M, tm, RegClassList),
MRI( tm.getRegInfo() ),
NumOfRegClasses(MRI.getNumOfRegClasses()),
- CallInstrList(),
- RetInstrList(),
AddedInstrMap()
{
@@ -47,10 +45,18 @@
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 @@
// 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 @@
} // 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 @@
else if( OpCode == Instruction::Ret )
RetInstrList.push_back( *InstIt );
}
+
+#endif
+
} // for all BBs in method
@@ -257,7 +268,38 @@
// 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 @@
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 @@
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 @@
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 @@
}
// 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 @@
// 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::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::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();
}
-
- // 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 all register classes
+ // color all register classes
for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
RegClassList[ rc ]->colorAllRegs();
+
+ // color incoming args and call args
+ colorIncomingArgs();
+ colorCallRetArgs();
+
+
updateMachineCode();
if (DEBUG_RA) {
- PrintMachineInstructions(Meth);
+ // PrintMachineInstructions(Meth);
printMachineCode(); // only for DEBUGGING
}
}