From 8e6047920dbf22a1edcbd98e65a8bc57a56c0e17 Mon Sep 17 00:00:00 2001 From: Ruchira Sasanka Date: Fri, 14 Sep 2001 21:18:34 +0000 Subject: *** empty log message *** git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@580 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/RegAlloc/PhyRegAloc.cpp | 343 ++++++++++++++++++++++++++++++++++++ 1 file changed, 343 insertions(+) create mode 100644 lib/CodeGen/RegAlloc/PhyRegAloc.cpp (limited to 'lib/CodeGen/RegAlloc/PhyRegAloc.cpp') diff --git a/lib/CodeGen/RegAlloc/PhyRegAloc.cpp b/lib/CodeGen/RegAlloc/PhyRegAloc.cpp new file mode 100644 index 0000000000..c2c7c64ec9 --- /dev/null +++ b/lib/CodeGen/RegAlloc/PhyRegAloc.cpp @@ -0,0 +1,343 @@ +#include "llvm/CodeGen/PhyRegAlloc.h" + + +PhyRegAlloc::PhyRegAlloc(const Method *const M, + const TargetMachine& tm, + MethodLiveVarInfo *const Lvi) + : RegClassList(), + Meth(M), TM(tm), LVI(Lvi), LRI(M, tm, RegClassList), + MRI( tm.getRegInfo() ), + NumOfRegClasses(MRI.getNumOfRegClasses()), + CallInstrList(), + AddedInstrMap() + +{ + // **TODO: use an actual reserved color list + ReservedColorListType *RCL = new ReservedColorListType(); + + // create each RegisterClass and put in RegClassList + for( unsigned int rc=0; rc < NumOfRegClasses; rc++) + RegClassList.push_back( new RegClass(M, MRI.getMachineRegClass(rc), RCL) ); + +} + + + + + + +void PhyRegAlloc::createIGNodeListsAndIGs() +{ + cout << "Creating LR lists ..." << endl; + + // hash map iterator + LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin(); + + // hash map end + LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end(); + + for( ; HMI != HMIEnd ; ++HMI ) { + + LiveRange *L = (*HMI).second; // get the LiveRange + + if( (*HMI).first ) { + // if the Value * is not null, and LR + // is not yet written to the IGNodeList + if( !(L->getUserIGNode()) ) { + + RegClass *const RC = // RegClass of first value in the LR + //RegClassList [MRI.getRegClassIDOfValue(*(L->begin()))]; + RegClassList[ L->getRegClass()->getID() ]; + + RC-> addLRToIG( L ); // add this LR to an IG + } + } + } + + // init RegClassList + for( unsigned int rc=0; rc < NumOfRegClasses ; rc++) + RegClassList[ rc ]->createInterferenceGraph(); + + if( DEBUG_RA) + cout << "LRLists Created!" << endl; +} + + + + +// Interence occurs only if the LR of Def (Inst or Arg) is of the same reg +// class as that of live var. The live var passed to this function is the +// LVset AFTER the instruction + + +void PhyRegAlloc::addInterference(const Value *const Def, + const LiveVarSet *const LVSet, + const bool isCallInst) { + + LiveVarSet::const_iterator LIt = LVSet->begin(); + + // get the live range of instruction + const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def ); + + IGNode *const IGNodeOfDef = LROfDef->getUserIGNode(); + assert( IGNodeOfDef ); + + RegClass *const RCOfDef = LROfDef->getRegClass(); + + // for each live var in live variable set + for( ; LIt != LVSet->end(); ++LIt) { + + if( DEBUG_RA > 1) { + cout << "< Def="; printValue(Def); + cout << ", Lvar="; printValue( *LIt); cout << "> "; + } + + // get the live range corresponding to live var + LiveRange *const LROfVar = LRI.getLiveRangeForValue(*LIt ); + + // LROfVar can be null if it is a const since a const + // doesn't have a dominating def - see Assumptions above + if( LROfVar) { + + if(LROfDef == LROfVar) // do not set interf for same LR + continue; + + // if 2 reg classes are the same set interference + if( RCOfDef == LROfVar->getRegClass() ){ + RCOfDef->setInterference( LROfDef, LROfVar); + + } + + //the live range of this var interferes with this call + if( isCallInst ) + LROfVar->addCallInterference( (const Instruction *const) Def ); + + } + else if(DEBUG_RA) { + // we will not have LRs for values not explicitly allocated in the + // instruction stream (e.g., constants) + cout << " warning: no live range for " ; + printValue( *LIt); cout << endl; } + + } + +} + + + +void PhyRegAlloc::buildInterferenceGraphs() +{ + + if(DEBUG_RA) cout << "Creating interference graphs ..." << endl; + + Method::const_iterator BBI = Meth->begin(); // random iterator for BBs + + for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order + + // get the iterator for machine instructions + const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec(); + MachineCodeForBasicBlock::const_iterator + MInstIterator = MIVec.begin(); + + // 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 + const LiveVarSet *const LVSetAI = + LVI->getLiveVarSetAfterMInst(MInst, *BBI); + + const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode()); + + // iterate over MI operands to find defs + for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) { + + if( OpI.isDef() ) { + // create a new LR iff this operand is a def + addInterference(*OpI, LVSetAI, isCallInst ); + + } //if this is a def + + } // for all operands + + } // for all machine instructions in BB + + + // go thru LLVM instructions in the basic block and record all CALL + // instructions in the CallInstrList + BasicBlock::const_iterator InstIt = (*BBI)->begin(); + + for( ; InstIt != (*BBI)->end() ; ++ InstIt) { + + if( (*InstIt)->getOpcode() == Instruction::Call ) + CallInstrList.push_back( *InstIt ); + } + + } // for all BBs in method + + + // add interferences for method arguments. Since there are no explict + // defs in method for args, we have to add them manually + + addInterferencesForArgs(); // add interference for method args + + if( DEBUG_RA) + cout << "Interference graphs calculted!" << endl; + +} + + + + +void PhyRegAlloc::addInterferencesForArgs() +{ + // get the InSet of root BB + const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() ); + + // get the argument list + const Method::ArgumentListType& ArgList = Meth->getArgumentList(); + + // get an iterator to arg list + Method::ArgumentListType::const_iterator ArgIt = ArgList.begin(); + + + for( ; ArgIt != ArgList.end() ; ++ArgIt) { // for each argument + addInterference( *ArgIt, InSet, false ); // add interferences between + // args and LVars at start + if( DEBUG_RA > 1) { + cout << " - %% adding interference for argument "; + printValue( (const Value *) *ArgIt); cout << endl; + } + } +} + + + +void PhyRegAlloc::updateMachineCode() +{ + + Method::const_iterator BBI = Meth->begin(); // random iterator for BBs + + for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order + + cout << endl << "BB "; printValue( *BBI); cout << ": "; + + // get the iterator for machine instructions + MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec(); + MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin(); + + // iterate over all the machine instructions in BB + for( ; MInstIterator != MIVec.end(); ++MInstIterator) { + + MachineInstr *const MInst = *MInstIterator; + + cout << endl << "\t"; + cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString; + + //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) { + + for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) { + + MachineOperand& Op = MInst->getOperand(OpNum); + + if( Op.getOperandType() == MachineOperand::MO_VirtualRegister || + Op.getOperandType() == MachineOperand::MO_CCRegister) { + + const Value *const Val = Op.getVRegValue(); + + if( !Val ) { + cout << "\t<** Value is NULL!!!**>"; + continue; + } + assert( Val && "Value is NULL"); + + const LiveRange *const LR = LRI.getLiveRangeForValue(Val); + + if ( !LR ) { + if( ! ( (Val->getType())->isLabelType() || + (Val->getValueType() == Value::ConstantVal) ) ) { + cout << "\t" << "<*No LiveRange for: "; + printValue( Val); cout << "*>"; + } + + + //assert( LR && "No LR found for Value"); + continue; + } + + unsigned RCID = (LR->getRegClass())->getID(); + + //cout << "Setting reg for value: "; printValue( Val ); + //cout << endl; + + //Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) ); + + int RegNum = MRI.getUnifiedRegNum(RCID, LR->getColor()); + + cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum ); + + } + else + cout << "\t" << Op; // use dump field + + } + + } + } +} + + + + + + + +void PhyRegAlloc::allocateRegisters() +{ + constructLiveRanges(); // create LR info + + if( DEBUG_RA) + LRI.printLiveRanges(); + + createIGNodeListsAndIGs(); // create IGNode list and IGs + + buildInterferenceGraphs(); // build IGs in all reg classes + + + 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(); + } + + MRI.colorArgs(Meth, LRI); // color method args + MRI.colorCallArgs(CallInstrList, LRI, AddedInstrMap); // color call args of call instrns + + // color all register classes + for( unsigned int rc=0; rc < NumOfRegClasses ; rc++) + RegClassList[ rc ]->colorAllRegs(); + + updateMachineCode(); + //PrintMachineInstructions(Meth); +} + + + + -- cgit v1.2.3-18-g5258