X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTarget%2FSparcV9%2FRegAlloc%2FPhyRegAlloc.cpp;h=ef4156147cb1ccc95cb393331a1f612282d56db7;hb=d58290ed3b0bba30954a16db47a932d2e9716083;hp=28999d2149c631f0c7ff4c41c57e014e7b6790b1;hpb=f221a2e0a8a37e8ee91ef9c98cac8eb5f8c3cbce;p=oota-llvm.git diff --git a/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp index 28999d2149c..ef4156147cb 100644 --- a/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp +++ b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp @@ -1,4 +1,3 @@ -// $Id$ //*************************************************************************** // File: // PhyRegAlloc.cpp @@ -10,113 +9,160 @@ // 9/10/01 - Ruchira Sasanka - created. //**************************************************************************/ +#include "llvm/CodeGen/RegisterAllocation.h" #include "llvm/CodeGen/PhyRegAlloc.h" #include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineInstrAnnot.h" +#include "llvm/CodeGen/MachineCodeForBasicBlock.h" +#include "llvm/CodeGen/MachineCodeForMethod.h" +#include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/MachineFrameInfo.h" - - -// ***TODO: There are several places we add instructions. Validate the order -// of adding these instructions. - - - -cl::Enum DEBUG_RA("dregalloc", cl::NoFlags, +#include "llvm/BasicBlock.h" +#include "llvm/Function.h" +#include "llvm/Type.h" +#include "llvm/iOther.h" +#include "llvm/CodeGen/RegAllocCommon.h" +#include "Support/CommandLine.h" +#include "Support/STLExtras.h" +#include +#include +using std::cerr; +using std::vector; + +RegAllocDebugLevel_t DEBUG_RA; +static cl::Enum DEBUG_RA_c(DEBUG_RA, "dregalloc", + cl::Hidden, "enable register allocation debugging information", clEnumValN(RA_DEBUG_None , "n", "disable debug output"), clEnumValN(RA_DEBUG_Normal , "y", "enable debug output"), clEnumValN(RA_DEBUG_Verbose, "v", "enable extra debug output"), 0); +//---------------------------------------------------------------------------- +// RegisterAllocation pass front end... +//---------------------------------------------------------------------------- +namespace { + class RegisterAllocator : public FunctionPass { + TargetMachine &Target; + public: + inline RegisterAllocator(TargetMachine &T) : Target(T) {} + + const char *getPassName() const { return "Register Allocation"; } + + bool runOnFunction(Function &F) { + if (DEBUG_RA) + cerr << "\n********* Function "<< F.getName() << " ***********\n"; + + PhyRegAlloc PRA(&F, Target, &getAnalysis(), + &getAnalysis()); + PRA.allocateRegisters(); + + if (DEBUG_RA) cerr << "\nRegister allocation complete!\n"; + return false; + } + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(LoopInfo::ID); + AU.addRequired(FunctionLiveVarInfo::ID); + } + }; +} + +Pass *getRegisterAllocator(TargetMachine &T) { + return new RegisterAllocator(T); +} + //---------------------------------------------------------------------------- // Constructor: Init local composite objects and create register classes. //---------------------------------------------------------------------------- -PhyRegAlloc::PhyRegAlloc(Method *M, - const TargetMachine& tm, - MethodLiveVarInfo *const Lvi) - : RegClassList(), - TM(tm), - Meth(M), - mcInfo(MachineCodeForMethod::get(M)), - LVI(Lvi), LRI(M, tm, RegClassList), - MRI( tm.getRegInfo() ), +PhyRegAlloc::PhyRegAlloc(Function *F, const TargetMachine& tm, + FunctionLiveVarInfo *Lvi, LoopInfo *LDC) + : TM(tm), Meth(F), + mcInfo(MachineCodeForMethod::get(F)), + LVI(Lvi), LRI(F, tm, RegClassList), + MRI(tm.getRegInfo()), NumOfRegClasses(MRI.getNumOfRegClasses()), - AddedInstrMap() - -{ - // **TODO: use an actual reserved color list - ReservedColorListType *RCL = new ReservedColorListType(); + LoopDepthCalc(LDC) { // 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) ); + // + for (unsigned rc=0; rc < NumOfRegClasses; rc++) + RegClassList.push_back(new RegClass(F, MRI.getMachineRegClass(rc), + &ResColList)); } + +//---------------------------------------------------------------------------- +// Destructor: Deletes register classes +//---------------------------------------------------------------------------- +PhyRegAlloc::~PhyRegAlloc() { + for ( unsigned rc=0; rc < NumOfRegClasses; rc++) + delete RegClassList[rc]; + + AddedInstrMap.clear(); +} + //---------------------------------------------------------------------------- // This method initally creates interference graphs (one in each reg class) // and IGNodeList (one in each IG). The actual nodes will be pushed later. //---------------------------------------------------------------------------- - -void PhyRegAlloc::createIGNodeListsAndIGs() -{ - if(DEBUG_RA ) cout << "Creating LR lists ..." << endl; +void PhyRegAlloc::createIGNodeListsAndIGs() { + if (DEBUG_RA) cerr << "Creating LR lists ...\n"; // hash map iterator - LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin(); + LiveRangeMapType::const_iterator HMI = LRI.getLiveRangeMap()->begin(); // hash map end - LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end(); - - for( ; HMI != HMIEnd ; ++HMI ) { - - if( (*HMI).first ) { - - LiveRange *L = (*HMI).second; // get the LiveRange - - if( !L) { - if( DEBUG_RA) { - cout << "\n*?!?Warning: Null liver range found for: "; - printValue( (*HMI).first) ; cout << endl; - } - continue; - } + LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end(); + + for (; HMI != HMIEnd ; ++HMI ) { + if (HMI->first) { + LiveRange *L = HMI->second; // get the LiveRange + if (!L) { + if (DEBUG_RA) { + cerr << "\n*?!?Warning: Null liver range found for: " + << RAV(HMI->first) << "\n"; + } + continue; + } // 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 - } + if (!(L->getUserIGNode()) ) { + RegClass *const RC = // RegClass of first value in the LR + RegClassList[ L->getRegClass()->getID() ]; + + RC->addLRToIG(L); // add this LR to an IG + } } } + + // init RegClassList + for ( unsigned rc=0; rc < NumOfRegClasses ; rc++) + RegClassList[rc]->createInterferenceGraph(); - // init RegClassList - for( unsigned int rc=0; rc < NumOfRegClasses ; rc++) - RegClassList[ rc ]->createInterferenceGraph(); - - if( DEBUG_RA) - cout << "LRLists Created!" << endl; + if (DEBUG_RA) + cerr << "LRLists Created!\n"; } + //---------------------------------------------------------------------------- // This method will add all interferences at for a given instruction. // 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 *Def, + const ValueSet *LVSet, + bool isCallInst) { -void PhyRegAlloc::addInterference(const Value *const Def, - const LiveVarSet *const LVSet, - const bool isCallInst) { - - LiveVarSet::const_iterator LIt = LVSet->begin(); + ValueSet::const_iterator LIt = LVSet->begin(); // get the live range of instruction + // const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def ); IGNode *const IGNodeOfDef = LROfDef->getUserIGNode(); @@ -125,42 +171,38 @@ void PhyRegAlloc::addInterference(const Value *const Def, RegClass *const RCOfDef = LROfDef->getRegClass(); // for each live var in live variable set - for( ; LIt != LVSet->end(); ++LIt) { + // + for ( ; LIt != LVSet->end(); ++LIt) { - if( DEBUG_RA > 1) { - cout << "< Def="; printValue(Def); - cout << ", Lvar="; printValue( *LIt); cout << "> "; - } + if (DEBUG_RA >= RA_DEBUG_Verbose) + cerr << "< Def=" << RAV(Def) << ", Lvar=" << RAV(*LIt) << "> "; // get the live range corresponding to live var - LiveRange *const LROfVar = LRI.getLiveRangeForValue(*LIt ); + // + LiveRange *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 + // + 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() ){ + // + if (RCOfDef == LROfVar->getRegClass()) { RCOfDef->setInterference( LROfDef, LROfVar); - + } else if (DEBUG_RA >= RA_DEBUG_Verbose) { + // we will not have LRs for values not explicitly allocated in the + // instruction stream (e.g., constants) + cerr << " warning: no live range for " << RAV(*LIt) << "\n"; } - - else if(DEBUG_RA > 1) { - // 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; } - } - } - } + //---------------------------------------------------------------------------- // For a call instruction, this method sets the CallInterference flag in // the LR of each variable live int the Live Variable Set live after the @@ -169,166 +211,213 @@ void PhyRegAlloc::addInterference(const Value *const Def, //---------------------------------------------------------------------------- void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst, - const LiveVarSet *const LVSetAft ) -{ - // Now find the LR of the return value of the call + const ValueSet *LVSetAft) { + if (DEBUG_RA) + cerr << "\n For call inst: " << *MInst; - // 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 it does not interfere with call - // (i.e., we can allocate a volatile register to the return value) - - LiveRange *RetValLR = NULL; - - const Value *RetVal = MRI.getCallInstRetVal( MInst ); - - if( RetVal ) { - RetValLR = LRI.getLiveRangeForValue( RetVal ); - assert( RetValLR && "No LR for RetValue of call"); - } - - if( DEBUG_RA) - cout << "\n For call inst: " << *MInst; - - LiveVarSet::const_iterator LIt = LVSetAft->begin(); + ValueSet::const_iterator LIt = LVSetAft->begin(); // for each live var in live variable set after machine inst - for( ; LIt != LVSetAft->end(); ++LIt) { + // + for ( ; LIt != LVSetAft->end(); ++LIt) { - // get the live range corresponding to live var + // get the live range corresponding to live var + // LiveRange *const LR = LRI.getLiveRangeForValue(*LIt ); - if( LR && DEBUG_RA) { - cout << "\n\tLR Aft Call: "; - LR->printSet(); + if (LR && DEBUG_RA) { + cerr << "\n\tLR Aft Call: "; + printSet(*LR); } - // LR can be null if it is a const since a const // doesn't have a dominating def - see Assumptions above - if( LR && (LR != RetValLR) ) { + // + if (LR ) { LR->setCallInterference(); - if( DEBUG_RA) { - cout << "\n ++Added call interf for LR: " ; - LR->printSet(); + if (DEBUG_RA) { + cerr << "\n ++Added call interf for LR: " ; + printSet(*LR); } } } + // Now find the LR of the return value of 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 it does not interfere with call + // (i.e., we can allocate a volatile register to the return value) + // + CallArgsDescriptor* argDesc = CallArgsDescriptor::get(MInst); + + if (const Value *RetVal = argDesc->getReturnValue()) { + LiveRange *RetValLR = LRI.getLiveRangeForValue( RetVal ); + assert( RetValLR && "No LR for RetValue of call"); + RetValLR->clearCallInterference(); + } + + // If the CALL is an indirect call, find the LR of the function pointer. + // That has a call interference because it conflicts with outgoing args. + if (const Value *AddrVal = argDesc->getIndirectFuncPtr()) { + LiveRange *AddrValLR = LRI.getLiveRangeForValue( AddrVal ); + assert( AddrValLR && "No LR for indirect addr val of call"); + AddrValLR->setCallInterference(); + } + } + + //---------------------------------------------------------------------------- // This method will walk thru code and create interferences in the IG of -// each RegClass. +// each RegClass. Also, this method calculates the spill cost of each +// Live Range (it is done in this method to save another pass over the code). //---------------------------------------------------------------------------- - void PhyRegAlloc::buildInterferenceGraphs() { - if(DEBUG_RA) cout << "Creating interference graphs ..." << endl; + if (DEBUG_RA) cerr << "Creating interference graphs ...\n"; - Method::const_iterator BBI = Meth->begin(); // random iterator for BBs + unsigned BBLoopDepthCost; + for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end(); + BBI != BBE; ++BBI) { - for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order + // find the 10^(loop_depth) of this BB + // + BBLoopDepthCost = (unsigned)pow(10.0, LoopDepthCalc->getLoopDepth(BBI)); // get the iterator for machine instructions - const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec(); - MachineCodeForBasicBlock::const_iterator - MInstIterator = MIVec.begin(); + // + const MachineCodeForBasicBlock& MIVec = MachineCodeForBasicBlock::get(BBI); + MachineCodeForBasicBlock::const_iterator MII = MIVec.begin(); // iterate over all the machine instructions in BB - for( ; MInstIterator != MIVec.end(); ++MInstIterator) { + // + for ( ; MII != MIVec.end(); ++MII) { - const MachineInstr * MInst = *MInstIterator; + const MachineInstr *MInst = *MII; // get the LV set after the instruction - const LiveVarSet *const LVSetAI = - LVI->getLiveVarSetAfterMInst(MInst, *BBI); + // + const ValueSet &LVSetAI = LVI->getLiveVarSetAfterMInst(MInst, BBI); const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode()); - if( isCallInst ) { - //cout << "\nFor call inst: " << *MInst; - + if (isCallInst ) { // set the isCallInterference flag of each live range wich extends // accross this call instruction. This information is used by graph // coloring algo to avoid allocating volatile colors to live ranges // that span across calls (since they have to be saved/restored) - setCallInterferences( MInst, LVSetAI); + // + setCallInterferences(MInst, &LVSetAI); } - // 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 ); + // iterate over all MI operands to find defs + // + for (MachineInstr::const_val_op_iterator OpI = MInst->begin(), + OpE = MInst->end(); OpI != OpE; ++OpI) { + if (OpI.isDef()) // create a new LR iff this operand is a def + addInterference(*OpI, &LVSetAI, isCallInst); - } //if this is a def + // Calculate the spill cost of each live range + // + LiveRange *LR = LRI.getLiveRangeForValue(*OpI); + if (LR) LR->addSpillCost(BBLoopDepthCost); + } - } // for all operands + + // if there are multiple defs in this instruction e.g. in SETX + // + if (TM.getInstrInfo().isPseudoInstr(MInst->getOpCode())) + addInterf4PseudoInstr(MInst); // Also add interference for any implicit definitions in a machine // instr (currently, only calls have this). - + // unsigned NumOfImpRefs = MInst->getNumImplicitRefs(); - if( NumOfImpRefs > 0 ) { - for(unsigned z=0; z < NumOfImpRefs; z++) - if( MInst->implicitRefIsDefined(z) ) - addInterference( MInst->getImplicitRef(z), LVSetAI, isCallInst ); + if ( NumOfImpRefs > 0 ) { + for (unsigned z=0; z < NumOfImpRefs; z++) + if (MInst->implicitRefIsDefined(z) ) + addInterference( MInst->getImplicitRef(z), &LVSetAI, isCallInst ); } - /* - // record phi instrns in PhiInstList - if( TM.getInstrInfo().isDummyPhiInstr(MInst->getOpCode()) ) - PhiInstList.push_back( MInst ); - */ } // for all machine instructions in BB - - } // for all BBs in method + } // for all BBs in function - // 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 + // add interferences for function arguments. Since there are no explict + // defs in the function for args, we have to add them manually + // + addInterferencesForArgs(); - if( DEBUG_RA) - cout << "Interference graphs calculted!" << endl; + if (DEBUG_RA) + cerr << "Interference graphs calculted!\n"; } +//-------------------------------------------------------------------------- +// Pseudo instructions will be exapnded to multiple instructions by the +// assembler. Consequently, all the opernds must get distinct registers. +// Therefore, we mark all operands of a pseudo instruction as they interfere +// with one another. +//-------------------------------------------------------------------------- +void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) { -//---------------------------------------------------------------------------- -// This method will add interferences for incoming arguments to a method. -//---------------------------------------------------------------------------- -void PhyRegAlloc::addInterferencesForArgs() -{ - // get the InSet of root BB - const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() ); + bool setInterf = false; - // get the argument list - const Method::ArgumentListType& ArgList = Meth->getArgumentList(); + // iterate over MI operands to find defs + // + for (MachineInstr::const_val_op_iterator It1 = MInst->begin(), + ItE = MInst->end(); It1 != ItE; ++It1) { + const LiveRange *LROfOp1 = LRI.getLiveRangeForValue(*It1); + assert((LROfOp1 || !It1.isDef()) && "No LR for Def in PSEUDO insruction"); - // get an iterator to arg list - Method::ArgumentListType::const_iterator ArgIt = ArgList.begin(); + MachineInstr::const_val_op_iterator It2 = It1; + for (++It2; It2 != ItE; ++It2) { + const LiveRange *LROfOp2 = LRI.getLiveRangeForValue(*It2); + if (LROfOp2) { + RegClass *RCOfOp1 = LROfOp1->getRegClass(); + RegClass *RCOfOp2 = LROfOp2->getRegClass(); + + if (RCOfOp1 == RCOfOp2 ){ + RCOfOp1->setInterference( LROfOp1, LROfOp2 ); + setInterf = true; + } + } // if Op2 has a LR + } // for all other defs in machine instr + } // for all operands in an instruction + + if (!setInterf && MInst->getNumOperands() > 2) { + cerr << "\nInterf not set for any operand in pseudo instr:\n"; + cerr << *MInst; + assert(0 && "Interf not set for pseudo instr with > 2 operands" ); + } +} - 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; - } + + +//---------------------------------------------------------------------------- +// This method will add interferences for incoming arguments to a function. +//---------------------------------------------------------------------------- +void PhyRegAlloc::addInterferencesForArgs() { + // get the InSet of root BB + const ValueSet &InSet = LVI->getInSetOfBB(&Meth->front()); + + for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI) { + // add interferences between args and LVars at start + addInterference(AI, &InSet, false); + + if (DEBUG_RA >= RA_DEBUG_Verbose) + cerr << " - %% adding interference for argument " << RAV(AI) << "\n"; } } @@ -336,132 +425,153 @@ void PhyRegAlloc::addInterferencesForArgs() //---------------------------------------------------------------------------- // This method is called after register allocation is complete to set the // allocated reisters in the machine code. This code will add register numbers -// to MachineOperands that contain a Value. +// to MachineOperands that contain a Value. Also it calls target specific +// methods to produce caller saving instructions. At the end, it adds all +// additional instructions produced by the register allocator to the +// instruction stream. //---------------------------------------------------------------------------- -void PhyRegAlloc::updateMachineCode() +//----------------------------- +// Utility functions used below +//----------------------------- +inline void +PrependInstructions(vector &IBef, + MachineCodeForBasicBlock& MIVec, + MachineCodeForBasicBlock::iterator& MII, + const std::string& msg) { + if (!IBef.empty()) + { + MachineInstr* OrigMI = *MII; + std::vector::iterator AdIt; + for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt) + { + if (DEBUG_RA) { + if (OrigMI) cerr << "For MInst: " << *OrigMI; + cerr << msg << " PREPENDed instr: " << **AdIt << "\n"; + } + MII = MIVec.insert(MII, *AdIt); + ++MII; + } + } +} - Method::const_iterator BBI = Meth->begin(); // random iterator for BBs - - for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order +inline void +AppendInstructions(std::vector &IAft, + MachineCodeForBasicBlock& MIVec, + MachineCodeForBasicBlock::iterator& MII, + const std::string& msg) +{ + if (!IAft.empty()) + { + MachineInstr* OrigMI = *MII; + std::vector::iterator AdIt; + for ( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) + { + if (DEBUG_RA) { + if (OrigMI) cerr << "For MInst: " << *OrigMI; + cerr << msg << " APPENDed instr: " << **AdIt << "\n"; + } + ++MII; // insert before the next instruction + MII = MIVec.insert(MII, *AdIt); + } + } +} - // get the iterator for machine instructions - MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec(); - MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin(); +void PhyRegAlloc::updateMachineCode() +{ + MachineCodeForBasicBlock& MIVec = MachineCodeForBasicBlock::get(&Meth->getEntryNode()); + + // Insert any instructions needed at method entry + MachineCodeForBasicBlock::iterator MII = MIVec.begin(); + PrependInstructions(AddedInstrAtEntry.InstrnsBefore, MIVec, MII, + "At function entry: \n"); + assert(AddedInstrAtEntry.InstrnsAfter.empty() && + "InstrsAfter should be unnecessary since we are just inserting at " + "the function entry point here."); + + for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end(); + BBI != BBE; ++BBI) { + // iterate over all the machine instructions in BB - for( ; MInstIterator != MIVec.end(); ++MInstIterator) { + MachineCodeForBasicBlock &MIVec = MachineCodeForBasicBlock::get(BBI); + for (MachineCodeForBasicBlock::iterator MII = MIVec.begin(); + MII != MIVec.end(); ++MII) { - MachineInstr *MInst = *MInstIterator; - + MachineInstr *MInst = *MII; + + unsigned Opcode = MInst->getOpCode(); + // do not process Phis - if( (TM.getInstrInfo()).isPhi( MInst->getOpCode()) ) + if (TM.getInstrInfo().isDummyPhiInstr(Opcode)) continue; + // Reset tmp stack positions so they can be reused for each machine instr. + mcInfo.popAllTempValues(TM); + + // Now insert speical instructions (if necessary) for call/return + // instructions. + // + if (TM.getInstrInfo().isCall(Opcode) || + TM.getInstrInfo().isReturn(Opcode)) { - // if this machine instr is call, insert caller saving code - - if( (TM.getInstrInfo()).isCall( MInst->getOpCode()) ) - MRI.insertCallerSavingCode(MInst, *BBI, *this ); - - - // reset the stack offset for temporary variables since we may - // need that to spill - mcInfo.popAllTempValues(TM); + AddedInstrns &AI = AddedInstrMap[MInst]; + + if (TM.getInstrInfo().isCall(Opcode)) + MRI.colorCallArgs(MInst, LRI, &AI, *this, BBI); + else if (TM.getInstrInfo().isReturn(Opcode)) + MRI.colorRetValue(MInst, LRI, &AI); + } - //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) { - - - // Now replace set the registers for operands in the machine instruction - - 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(); - - // delete this condition checking later (must assert if Val is null) - if( !Val) { - if (DEBUG_RA) - cout << "Warning: NULL Value found for operand" << endl; - continue; - } - assert( Val && "Value is NULL"); - - LiveRange *const LR = LRI.getLiveRangeForValue(Val); - - if ( !LR ) { - - // nothing to worry if it's a const or a label - - if (DEBUG_RA) { - cout << "*NO LR for operand : " << Op ; - cout << " [reg:" << Op.getAllocatedRegNum() << "]"; - cout << " in inst:\t" << *MInst << endl; + // Set the registers for operands in the machine instruction + // if a register was successfully allocated. If not, insert + // code to spill the register value. + // + 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(); + + LiveRange *const LR = LRI.getLiveRangeForValue(Val); + if (!LR) // consts or labels will have no live range + { + // if register is not allocated, mark register as invalid + if (Op.getAllocatedRegNum() == -1) + MInst->SetRegForOperand(OpNum, MRI.getInvalidRegNum()); + continue; + } + + if (LR->hasColor() ) + MInst->SetRegForOperand(OpNum, + MRI.getUnifiedRegNum(LR->getRegClass()->getID(), + LR->getColor())); + else + // LR did NOT receive a color (register). Insert spill code. + insertCode4SpilledLR(LR, MInst, BBI, OpNum ); } - - // if register is not allocated, mark register as invalid - if( Op.getAllocatedRegNum() == -1) - Op.setRegForValue( MRI.getInvalidRegNum()); - - - continue; - } - - unsigned RCID = (LR->getRegClass())->getID(); - - if( LR->hasColor() ) { - Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) ); - } - else { - - // LR did NOT receive a color (register). Now, insert spill code - // for spilled opeands in this machine instruction - - //assert(0 && "LR must be spilled"); - insertCode4SpilledLR(LR, MInst, *BBI, OpNum ); - - } - } - - } // for each operand - - + } // for each operand + + + // Now add instructions that the register allocator inserts before/after + // this machine instructions (done only for calls/rets/incoming args) + // We do this here, to ensure that spill for an instruction is inserted + // closest as possible to an instruction (see above insertCode4Spill...) + // // If there are instructions to be added, *before* this machine // instruction, add them now. - - if( AddedInstrMap[ MInst ] ) { - - deque &IBef = (AddedInstrMap[MInst])->InstrnsBefore; - - if( ! IBef.empty() ) { - - deque::iterator AdIt; - - for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) { - - if( DEBUG_RA) { - cerr << "For inst " << *MInst; - cerr << " PREPENDed instr: " << **AdIt << endl; - } - - MInstIterator = MIVec.insert( MInstIterator, *AdIt ); - ++MInstIterator; - } - - } - + // + if (AddedInstrMap.count(MInst)) { + PrependInstructions(AddedInstrMap[MInst].InstrnsBefore, MIVec, MII,""); } - + // If there are instructions to be added *after* this machine // instruction, add them now - - if( AddedInstrMap[ MInst ] && - ! (AddedInstrMap[ MInst ]->InstrnsAfter).empty() ) { + // + if (!AddedInstrMap[MInst].InstrnsAfter.empty()) { // if there are delay slots for this instruction, the instructions // added after it must really go after the delayed instruction(s) @@ -469,46 +579,14 @@ void PhyRegAlloc::updateMachineCode() // corresponding delayed instruction unsigned delay; - if((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){ - move2DelayedInstr(MInst, *(MInstIterator+delay) ); - - if(DEBUG_RA) cout<< "\nMoved an added instr after the delay slot"; + if ((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){ + move2DelayedInstr(MInst, *(MII+delay) ); } - else { - - // Here we can add the "instructions after" to the current // instruction since there are no delay slots for this instruction - - deque &IAft = (AddedInstrMap[MInst])->InstrnsAfter; - - if( ! IAft.empty() ) { - - deque::iterator AdIt; - - ++MInstIterator; // advance to the next instruction - - for( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) { - - if(DEBUG_RA) { - cerr << "For inst " << *MInst; - cerr << " APPENDed instr: " << **AdIt << endl; - } - - MInstIterator = MIVec.insert( MInstIterator, *AdIt ); - ++MInstIterator; - } - - // MInsterator already points to the next instr. Since the - // for loop also increments it, decrement it to point to the - // instruction added last - --MInstIterator; - - } - + AppendInstructions(AddedInstrMap[MInst].InstrnsAfter, MIVec, MII,""); } // if not delay - } } // for each machine instruction @@ -530,86 +608,86 @@ void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR, const BasicBlock *BB, const unsigned OpNum) { + assert(! TM.getInstrInfo().isCall(MInst->getOpCode()) && + (! TM.getInstrInfo().isReturn(MInst->getOpCode())) && + "Arg of a call/ret must be handled elsewhere"); + MachineOperand& Op = MInst->getOperand(OpNum); bool isDef = MInst->operandIsDefined(OpNum); + bool isDefAndUse = MInst->operandIsDefinedAndUsed(OpNum); unsigned RegType = MRI.getRegType( LR ); int SpillOff = LR->getSpillOffFromFP(); RegClass *RC = LR->getRegClass(); - const LiveVarSet *LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB); + const ValueSet &LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB); - /**** NOTE: THIS SHOULD USE THE RIGHT SIZE FOR THE REG BEING PUSHED ****/ - int TmpOff = - mcInfo.pushTempValue(TM, 8 /* TM.findOptimalStorageSize(LR->getType()) */); + mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) ); - MachineInstr *MIBef=NULL, *AdIMid=NULL, *MIAft=NULL; - int TmpReg; - - TmpReg = getUsableRegAtMI(RC, RegType, MInst,LVSetBef, MIBef, MIAft); - TmpReg = MRI.getUnifiedRegNum( RC->getID(), TmpReg ); - - - // get the added instructions for this instruciton - AddedInstrns *AI = AddedInstrMap[ MInst ]; - if ( !AI ) { - AI = new AddedInstrns(); - AddedInstrMap[ MInst ] = AI; - } - + vector MIBef, MIAft; + vector AdIMid; + // Choose a register to hold the spilled value. This may insert code + // before and after MInst to free up the value. If so, this code should + // be first and last in the spill sequence before/after MInst. + int TmpRegU = getUsableUniRegAtMI(RegType, &LVSetBef, MInst, MIBef, MIAft); - if( !isDef ) { - + // Set the operand first so that it this register does not get used + // as a scratch register for later calls to getUsableUniRegAtMI below + MInst->SetRegForOperand(OpNum, TmpRegU); + + // get the added instructions for this instruction + AddedInstrns &AI = AddedInstrMap[MInst]; + + // We may need a scratch register to copy the spilled value to/from memory. + // This may itself have to insert code to free up a scratch register. + // Any such code should go before (after) the spill code for a load (store). + int scratchRegType = -1; + int scratchReg = -1; + if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) + { + scratchReg = this->getUsableUniRegAtMI(scratchRegType, &LVSetBef, + MInst, MIBef, MIAft); + assert(scratchReg != MRI.getInvalidRegNum()); + MInst->getRegsUsed().insert(scratchReg); + } + + if (!isDef || isDefAndUse) { // for a USE, we have to load the value of LR from stack to a TmpReg // and use the TmpReg as one operand of instruction - - // actual loading instruction - AdIMid = MRI.cpMem2RegMI(MRI.getFramePointer(), SpillOff, TmpReg, RegType); - - if( MIBef ) - (AI->InstrnsBefore).push_back(MIBef); - - (AI->InstrnsBefore).push_back(AdIMid); - - if( MIAft) - (AI->InstrnsAfter).push_front(MIAft); + // actual loading instruction(s) + MRI.cpMem2RegMI(AdIMid, MRI.getFramePointer(), SpillOff, TmpRegU, RegType, + scratchReg); - } - else { // if this is a Def - + // the actual load should be after the instructions to free up TmpRegU + MIBef.insert(MIBef.end(), AdIMid.begin(), AdIMid.end()); + AdIMid.clear(); + } + + if (isDef) { // if this is a Def // for a DEF, we have to store the value produced by this instruction // on the stack position allocated for this LR - - // actual storing instruction - AdIMid = MRI.cpReg2MemMI(TmpReg, MRI.getFramePointer(), SpillOff, RegType); - - if( MIBef ) - (AI->InstrnsBefore).push_back(MIBef); - - (AI->InstrnsAfter).push_front(AdIMid); - - if( MIAft) - (AI->InstrnsAfter).push_front(MIAft); - + + // actual storing instruction(s) + MRI.cpReg2MemMI(AdIMid, TmpRegU, MRI.getFramePointer(), SpillOff, RegType, + scratchReg); + + MIAft.insert(MIAft.begin(), AdIMid.begin(), AdIMid.end()); } // if !DEF - - cerr << "\nFor Inst " << *MInst; - cerr << " - SPILLED LR: "; LR->printSet(); - cerr << "\n - Added Instructions:"; - if( MIBef ) cerr << *MIBef; - cerr << *AdIMid; - if( MIAft ) cerr << *MIAft; - - Op.setRegForValue( TmpReg ); // set the opearnd - - + + // Finally, insert the entire spill code sequences before/after MInst + AI.InstrnsBefore.insert(AI.InstrnsBefore.end(), MIBef.begin(), MIBef.end()); + AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft.begin(), MIAft.end()); + + if (DEBUG_RA) { + cerr << "\nFor Inst " << *MInst; + cerr << " - SPILLED LR: "; printSet(*LR); + cerr << "\n - Added Instructions:"; + for_each(MIBef.begin(), MIBef.end(), std::mem_fun(&MachineInstr::dump)); + for_each(MIAft.begin(), MIAft.end(), std::mem_fun(&MachineInstr::dump)); + } } - - - - //---------------------------------------------------------------------------- // We can use the following method to get a temporary register to be used // BEFORE any given machine instruction. If there is a register available, @@ -619,33 +697,48 @@ void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR, // Returned register number is the UNIFIED register number //---------------------------------------------------------------------------- -int PhyRegAlloc::getUsableRegAtMI(RegClass *RC, - const int RegType, - const MachineInstr *MInst, - const LiveVarSet *LVSetBef, - MachineInstr *MIBef, - MachineInstr *MIAft) { - - int Reg = getUnusedRegAtMI(RC, MInst, LVSetBef); - Reg = MRI.getUnifiedRegNum(RC->getID(), Reg); - - if( Reg != -1) { - // we found an unused register, so we can simply used - MIBef = MIAft = NULL; - } - else { +int PhyRegAlloc::getUsableUniRegAtMI(const int RegType, + const ValueSet *LVSetBef, + MachineInstr *MInst, + std::vector& MIBef, + std::vector& MIAft) { + + RegClass* RC = this->getRegClassByID(MRI.getRegClassIDOfRegType(RegType)); + + int RegU = getUnusedUniRegAtMI(RC, MInst, LVSetBef); + + if (RegU == -1) { // we couldn't find an unused register. Generate code to free up a reg by // saving it on stack and restoring after the instruction - - /**** NOTE: THIS SHOULD USE THE RIGHT SIZE FOR THE REG BEING PUSHED ****/ - int TmpOff = mcInfo.pushTempValue(TM, /*size*/ 8); - Reg = getRegNotUsedByThisInst(RC, MInst); - MIBef = MRI.cpReg2MemMI(Reg, MRI.getFramePointer(), TmpOff, RegType ); - MIAft = MRI.cpMem2RegMI(MRI.getFramePointer(), TmpOff, Reg, RegType ); + int TmpOff = mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) ); + + RegU = getUniRegNotUsedByThisInst(RC, MInst); + + // Check if we need a scratch register to copy this register to memory. + int scratchRegType = -1; + if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) + { + int scratchReg = this->getUsableUniRegAtMI(scratchRegType, LVSetBef, + MInst, MIBef, MIAft); + assert(scratchReg != MRI.getInvalidRegNum()); + + // We may as well hold the value in the scratch register instead + // of copying it to memory and back. But we have to mark the + // register as used by this instruction, so it does not get used + // as a scratch reg. by another operand or anyone else. + MInst->getRegsUsed().insert(scratchReg); + MRI.cpReg2RegMI(MIBef, RegU, scratchReg, RegType); + MRI.cpReg2RegMI(MIAft, scratchReg, RegU, RegType); + } + else + { // the register can be copied directly to/from memory so do it. + MRI.cpReg2MemMI(MIBef, RegU, MRI.getFramePointer(), TmpOff, RegType); + MRI.cpMem2RegMI(MIAft, MRI.getFramePointer(), TmpOff, RegU, RegType); + } } - - return Reg; + + return RegU; } //---------------------------------------------------------------------------- @@ -658,128 +751,122 @@ int PhyRegAlloc::getUsableRegAtMI(RegClass *RC, // Return register number is relative to the register class. NOT // unified number //---------------------------------------------------------------------------- -int PhyRegAlloc::getUnusedRegAtMI(RegClass *RC, +int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC, const MachineInstr *MInst, - const LiveVarSet *LVSetBef) { + const ValueSet *LVSetBef) { unsigned NumAvailRegs = RC->getNumOfAvailRegs(); - bool *IsColorUsedArr = RC->getIsColorUsedArr(); + std::vector &IsColorUsedArr = RC->getIsColorUsedArr(); - for(unsigned i=0; i < NumAvailRegs; i++) + for (unsigned i=0; i < NumAvailRegs; i++) // Reset array IsColorUsedArr[i] = false; - LiveVarSet::const_iterator LIt = LVSetBef->begin(); + ValueSet::const_iterator LIt = LVSetBef->begin(); // for each live var in live variable set after machine inst - for( ; LIt != LVSetBef->end(); ++LIt) { + for ( ; LIt != LVSetBef->end(); ++LIt) { // get the live range corresponding to live var LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt ); // LR can be null if it is a const since a const // doesn't have a dominating def - see Assumptions above - if( LRofLV ) - if( LRofLV->hasColor() ) - IsColorUsedArr[ LRofLV->getColor() ] = true; + if (LRofLV && LRofLV->getRegClass() == RC && LRofLV->hasColor() ) + IsColorUsedArr[ LRofLV->getColor() ] = true; } // It is possible that one operand of this MInst was already spilled // and it received some register temporarily. If that's the case, // it is recorded in machine operand. We must skip such registers. - setRegsUsedByThisInst(RC, MInst); - - unsigned c; // find first unused color - for( c=0; c < NumAvailRegs; c++) - if( ! IsColorUsedArr[ c ] ) break; - - if(c < NumAvailRegs) - return c; - else - return -1; - - -} + setRelRegsUsedByThisInst(RC, MInst); - - -//---------------------------------------------------------------------------- -// This method modifies the IsColorUsedArr of the register class passed to it. -// It sets the bits corresponding to the registers used by this machine -// instructions. Explicit operands are set. -//---------------------------------------------------------------------------- -void PhyRegAlloc::setRegsUsedByThisInst(RegClass *RC, - const MachineInstr *MInst ) { - - bool *IsColorUsedArr = RC->getIsColorUsedArr(); + for (unsigned c=0; c < NumAvailRegs; c++) // find first unused color + if (!IsColorUsedArr[c]) + return MRI.getUnifiedRegNum(RC->getID(), c); - for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) { - - const MachineOperand& Op = MInst->getOperand(OpNum); - - if( Op.getOperandType() == MachineOperand::MO_VirtualRegister || - Op.getOperandType() == MachineOperand::MO_CCRegister) { - - const Value *const Val = Op.getVRegValue(); - - if( !Val ) - if( MRI.getRegClassIDOfValue( Val )== RC->getID() ) { - int Reg; - if( (Reg=Op.getAllocatedRegNum()) != -1) - IsColorUsedArr[ Reg ] = true; - - } - } - } - - // If there are implicit references, mark them as well - - for(unsigned z=0; z < MInst->getNumImplicitRefs(); z++) { - - LiveRange *const LRofImpRef = - LRI.getLiveRangeForValue( MInst->getImplicitRef(z) ); - - if( LRofImpRef ) - if( LRofImpRef->hasColor() ) - IsColorUsedArr[ LRofImpRef->getColor() ] = true; - } - - - + return -1; } - //---------------------------------------------------------------------------- // Get any other register in a register class, other than what is used -// by operands of a machine instruction. +// by operands of a machine instruction. Returns the unified reg number. //---------------------------------------------------------------------------- -int PhyRegAlloc::getRegNotUsedByThisInst(RegClass *RC, - const MachineInstr *MInst) { +int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC, + const MachineInstr *MInst) { - bool *IsColorUsedArr = RC->getIsColorUsedArr(); + vector &IsColorUsedArr = RC->getIsColorUsedArr(); unsigned NumAvailRegs = RC->getNumOfAvailRegs(); - - for(unsigned i=0; i < NumAvailRegs ; i++) + for (unsigned i=0; i < NumAvailRegs ; i++) // Reset array IsColorUsedArr[i] = false; - setRegsUsedByThisInst(RC, MInst); + setRelRegsUsedByThisInst(RC, MInst); - unsigned c; // find first unused color - for( c=0; c < RC->getNumOfAvailRegs(); c++) - if( ! IsColorUsedArr[ c ] ) break; - - if(c < NumAvailRegs) - return c; - else - assert( 0 && "FATAL: No free register could be found in reg class!!"); + for (unsigned c=0; c < RC->getNumOfAvailRegs(); c++)// find first unused color + if (!IsColorUsedArr[c]) + return MRI.getUnifiedRegNum(RC->getID(), c); + assert(0 && "FATAL: No free register could be found in reg class!!"); + return 0; } +//---------------------------------------------------------------------------- +// This method modifies the IsColorUsedArr of the register class passed to it. +// It sets the bits corresponding to the registers used by this machine +// instructions. Both explicit and implicit operands are set. +//---------------------------------------------------------------------------- +void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC, + const MachineInstr *MInst ) { + vector &IsColorUsedArr = RC->getIsColorUsedArr(); + + // Add the registers already marked as used by the instruction. + // This should include any scratch registers that are used to save + // values across the instruction (e.g., for saving state register values). + const hash_set& regsUsed = MInst->getRegsUsed(); + for (hash_set::const_iterator SI=regsUsed.begin(), SE=regsUsed.end(); + SI != SE; ++SI) + { + unsigned classId = 0; + int classRegNum = MRI.getClassRegNum(*SI, classId); + if (RC->getID() == classId) + { + assert(classRegNum < (int) IsColorUsedArr.size() && + "Illegal register number for this reg class?"); + IsColorUsedArr[classRegNum] = true; + } + } + + // Now add registers allocated to the live ranges of values used in + // the instruction. These are not yet recorded in the instruction. + for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) + { + const MachineOperand& Op = MInst->getOperand(OpNum); + + if (Op.getOperandType() == MachineOperand::MO_VirtualRegister || + Op.getOperandType() == MachineOperand::MO_CCRegister) + if (const Value* Val = Op.getVRegValue()) + if (MRI.getRegClassIDOfValue(Val) == RC->getID()) + if (Op.getAllocatedRegNum() == -1) + if (LiveRange *LROfVal = LRI.getLiveRangeForValue(Val)) + if (LROfVal->hasColor() ) + // this operand is in a LR that received a color + IsColorUsedArr[LROfVal->getColor()] = true; + } + + // If there are implicit references, mark their allocated regs as well + // + for (unsigned z=0; z < MInst->getNumImplicitRefs(); z++) + if (const LiveRange* + LRofImpRef = LRI.getLiveRangeForValue(MInst->getImplicitRef(z))) + if (LRofImpRef->hasColor()) + // this implicit reference is in a LR that received a color + IsColorUsedArr[LRofImpRef->getColor()] = true; +} //---------------------------------------------------------------------------- @@ -789,37 +876,25 @@ int PhyRegAlloc::getRegNotUsedByThisInst(RegClass *RC, // corresponding delayed instruction using the following method. //---------------------------------------------------------------------------- -void PhyRegAlloc:: move2DelayedInstr(const MachineInstr *OrigMI, - const MachineInstr *DelayedMI) { - +void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI, + const MachineInstr *DelayedMI) { // "added after" instructions of the original instr - deque &OrigAft = (AddedInstrMap[OrigMI])->InstrnsAfter; + std::vector &OrigAft = AddedInstrMap[OrigMI].InstrnsAfter; // "added instructions" of the delayed instr - AddedInstrns *DelayAdI = AddedInstrMap[DelayedMI]; - - if(! DelayAdI ) { // create a new "added after" if necessary - DelayAdI = new AddedInstrns(); - AddedInstrMap[DelayedMI] = DelayAdI; - } + AddedInstrns &DelayAdI = AddedInstrMap[DelayedMI]; // "added after" instructions of the delayed instr - deque &DelayedAft = DelayAdI->InstrnsAfter; + std::vector &DelayedAft = DelayAdI.InstrnsAfter; // go thru all the "added after instructions" of the original instruction // and append them to the "addded after instructions" of the delayed // instructions - - deque::iterator OrigAdIt; - - for( OrigAdIt = OrigAft.begin(); OrigAdIt != OrigAft.end() ; ++OrigAdIt ) { - DelayedAft.push_back( *OrigAdIt ); - } + DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end()); // empty the "added after instructions" of the original instruction OrigAft.clear(); - } //---------------------------------------------------------------------------- @@ -829,160 +904,110 @@ void PhyRegAlloc:: move2DelayedInstr(const MachineInstr *OrigMI, void PhyRegAlloc::printMachineCode() { - cout << endl << ";************** Method "; - cout << Meth->getName() << " *****************" << endl; - - Method::const_iterator BBI = Meth->begin(); // random iterator for BBs + cerr << "\n;************** Function " << Meth->getName() + << " *****************\n"; - for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order - - cout << endl ; printLabel( *BBI); cout << ": "; + for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end(); + BBI != BBE; ++BBI) { + cerr << "\n"; printLabel(BBI); cerr << ": "; // get the iterator for machine instructions - MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec(); - MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin(); + MachineCodeForBasicBlock& MIVec = MachineCodeForBasicBlock::get(BBI); + MachineCodeForBasicBlock::iterator MII = 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 ( ; MII != MIVec.end(); ++MII) { + MachineInstr *const MInst = *MII; - //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) { - - for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) { + cerr << "\n\t"; + cerr << TargetInstrDescriptors[MInst->getOpCode()].opCodeString; + for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) { MachineOperand& Op = MInst->getOperand(OpNum); - if( Op.getOperandType() == MachineOperand::MO_VirtualRegister || + if (Op.getOperandType() == MachineOperand::MO_VirtualRegister || 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 ) { - cout << "\t<*NULL*>"; + if (! Val ) { + cerr << "\t<*NULL*>"; continue; } // if a label or a constant - if( (Val->getValueType() == Value::BasicBlockVal) ) { - - cout << "\t"; printLabel( Op.getVRegValue () ); - } - else { + if (isa(Val)) { + cerr << "\t"; printLabel( Op.getVRegValue () ); + } else { // else it must be a register value const int RegNum = Op.getAllocatedRegNum(); - cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum ); + cerr << "\t" << "%" << MRI.getUnifiedRegName( RegNum ); + if (Val->hasName() ) + cerr << "(" << Val->getName() << ")"; + else + cerr << "(" << Val << ")"; + + if (Op.opIsDef() ) + cerr << "*"; + + const LiveRange *LROfVal = LRI.getLiveRangeForValue(Val); + if (LROfVal ) + if (LROfVal->hasSpillOffset() ) + cerr << "$"; } } - else if(Op.getOperandType() == MachineOperand::MO_MachineRegister) { - cout << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum()); + else if (Op.getOperandType() == MachineOperand::MO_MachineRegister) { + cerr << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum()); } else - cout << "\t" << Op; // use dump field + cerr << "\t" << Op; // use dump field } unsigned NumOfImpRefs = MInst->getNumImplicitRefs(); - if( NumOfImpRefs > 0 ) { - - cout << "\tImplicit:"; + if (NumOfImpRefs > 0) { + cerr << "\tImplicit:"; - for(unsigned z=0; z < NumOfImpRefs; z++) { - printValue( MInst->getImplicitRef(z) ); - cout << "\t"; - } - + for (unsigned z=0; z < NumOfImpRefs; z++) + cerr << RAV(MInst->getImplicitRef(z)) << "\t"; } } // for all machine instructions - - cout << endl; + cerr << "\n"; } // for all BBs - cout << endl; -} - - -//---------------------------------------------------------------------------- -// -//---------------------------------------------------------------------------- - -void PhyRegAlloc::colorCallRetArgs() -{ - - CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList(); - CallRetInstrListType::const_iterator It = CallRetInstList.begin(); - - for( ; It != CallRetInstList.end(); ++It ) { - - const MachineInstr *const CRMI = *It; - unsigned OpCode = CRMI->getOpCode(); - - // get the added instructions for this Call/Ret instruciton - AddedInstrns *AI = AddedInstrMap[ CRMI ]; - if ( !AI ) { - AI = new AddedInstrns(); - AddedInstrMap[ CRMI ] = AI; - } - - // Tmp stack poistions are needed by some calls that have spilled args - // So reset it before we call each such method - mcInfo.popAllTempValues(TM); - - if( (TM.getInstrInfo()).isCall( OpCode ) ) - MRI.colorCallArgs( CRMI, LRI, AI, *this ); - - else if ( (TM.getInstrInfo()).isReturn(OpCode) ) - MRI.colorRetValue( CRMI, LRI, AI ); - - else assert( 0 && "Non Call/Ret instrn in CallRetInstrList\n" ); - - } - + cerr << "\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; - } + const BasicBlock &FirstBB = Meth->front(); + const MachineInstr *FirstMI = MachineCodeForBasicBlock::get(&FirstBB).front(); + assert(FirstMI && "No machine instruction in entry BB"); - MRI.colorMethodArgs(Meth, LRI, AI ); + MRI.colorMethodArgs(Meth, LRI, &AddedInstrAtEntry); } //---------------------------------------------------------------------------- // Used to generate a label for a basic block //---------------------------------------------------------------------------- -void PhyRegAlloc::printLabel(const Value *const Val) -{ - if( Val->hasName() ) - cout << Val->getName(); +void PhyRegAlloc::printLabel(const Value *const Val) { + if (Val->hasName()) + cerr << Val->getName(); else - cout << "Label" << Val; + cerr << "Label" << Val; } @@ -995,23 +1020,19 @@ void PhyRegAlloc::printLabel(const Value *const Val) void PhyRegAlloc::markUnusableSugColors() { - if(DEBUG_RA ) cout << "\nmarking unusable suggested colors ..." << endl; + if (DEBUG_RA ) cerr << "\nmarking unusable suggested colors ...\n"; // hash map iterator LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin(); LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end(); - for( ; HMI != HMIEnd ; ++HMI ) { - - if( (*HMI).first ) { - - LiveRange *L = (*HMI).second; // get the LiveRange - - if(L) { - if( L->hasSuggestedColor() ) { - - int RCID = (L->getRegClass())->getID(); - if( MRI.isRegVolatile( RCID, L->getSuggestedColor()) && + for (; HMI != HMIEnd ; ++HMI ) { + if (HMI->first) { + LiveRange *L = HMI->second; // get the LiveRange + if (L) { + if (L->hasSuggestedColor()) { + int RCID = L->getRegClass()->getID(); + if (MRI.isRegVolatile( RCID, L->getSuggestedColor()) && L->isCallInterference() ) L->setSuggestedColorUsable( false ); else @@ -1031,23 +1052,19 @@ void PhyRegAlloc::markUnusableSugColors() // this method allocate a new spill position on the stack. //---------------------------------------------------------------------------- -void PhyRegAlloc::allocateStackSpace4SpilledLRs() -{ - if(DEBUG_RA ) cout << "\nsetting LR stack offsets ..." << endl; +void PhyRegAlloc::allocateStackSpace4SpilledLRs() { + if (DEBUG_RA) cerr << "\nsetting LR stack offsets ...\n"; - // hash map iterator - LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin(); - LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end(); + LiveRangeMapType::const_iterator HMI = LRI.getLiveRangeMap()->begin(); + LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end(); - for( ; HMI != HMIEnd ; ++HMI ) { - if( (*HMI).first ) { - LiveRange *L = (*HMI).second; // get the LiveRange - if(L) - if( ! L->hasColor() ) - /**** NOTE: THIS SHOULD USE THE RIGHT SIZE FOR THE REG BEING PUSHED ****/ - L->setSpillOffFromFP(mcInfo.allocateSpilledValue(TM, Type::LongTy /*L->getType()*/ )); - } - } // for all LR's in hash map + for ( ; HMI != HMIEnd ; ++HMI) { + if (HMI->first && HMI->second) { + LiveRange *L = HMI->second; // get the LiveRange + if (!L->hasColor()) // NOTE: ** allocating the size of long Type ** + L->setSpillOffFromFP(mcInfo.allocateSpilledValue(TM, Type::LongTy)); + } + } // for all LR's in hash map } @@ -1062,14 +1079,10 @@ 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). + // + LRI.constructLiveRanges(); // create LR info - cout << "\n\n ******** AFTER SCHEDULING **********"; - MachineCodeForMethod::get(Meth).dump(); - - - constructLiveRanges(); // create LR info - - if( DEBUG_RA ) + if (DEBUG_RA) LRI.printLiveRanges(); createIGNodeListsAndIGs(); // create IGNode list and IGs @@ -1077,29 +1090,27 @@ void PhyRegAlloc::allocateRegisters() 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(); + for ( unsigned 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(); + for ( unsigned rc=0; rc < NumOfRegClasses ; rc++) + RegClassList[rc]->printIG(); } + LRI.coalesceLRs(); // coalesce all live ranges - // coalscing could not get rid of all phi's, add phi elimination - // instructions - // insertPhiEleminateInstrns(); - if( DEBUG_RA) { + if (DEBUG_RA) { // print all LRs in all reg classes - for( unsigned int rc=0; rc < NumOfRegClasses ; rc++) + for ( unsigned rc=0; rc < NumOfRegClasses ; rc++) RegClassList[ rc ]->printIGNodeList(); // print IGs in all register classes - for( unsigned int rc=0; rc < NumOfRegClasses ; rc++) + for ( unsigned rc=0; rc < NumOfRegClasses ; rc++) RegClassList[ rc ]->printIG(); } @@ -1107,30 +1118,35 @@ void PhyRegAlloc::allocateRegisters() // mark un-usable suggested color before graph coloring algorithm. // When this is done, the graph coloring algo will not reserve // suggested color unnecessarily - they can be used by another LR + // markUnusableSugColors(); // color all register classes using the graph coloring algo - for( unsigned int rc=0; rc < NumOfRegClasses ; rc++) + for (unsigned rc=0; rc < NumOfRegClasses ; rc++) RegClassList[ rc ]->colorAllRegs(); // Atter grpah coloring, if some LRs did not receive a color (i.e, spilled) // a poistion for such spilled LRs + // allocateStackSpace4SpilledLRs(); - // color incoming args and call args + mcInfo.popAllTempValues(TM); // TODO **Check + + // color incoming args - if the correct color was not received + // insert code to copy to the correct register + // colorIncomingArgs(); - colorCallRetArgs(); - + // Now update the machine code with register names and add any + // additional code inserted by the register allocator to the instruction + // stream + // updateMachineCode(); + if (DEBUG_RA) { MachineCodeForMethod::get(Meth).dump(); printMachineCode(); // only for DEBUGGING } - - // char ch; - //cin >> ch; - }