#include "llvm/CodeGen/RegisterAllocation.h"
#include "llvm/CodeGen/PhyRegAlloc.h"
#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineInstrAnnot.h"
#include "llvm/CodeGen/MachineCodeForMethod.h"
-#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
+#include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/MachineFrameInfo.h"
#include "llvm/BasicBlock.h"
-#include "llvm/Method.h"
+#include "llvm/Function.h"
#include "llvm/Type.h"
+#include "llvm/iOther.h"
+#include "llvm/CodeGen/RegAllocCommon.h"
#include <iostream>
#include <math.h>
using std::cerr;
// ***TODO: There are several places we add instructions. Validate the order
// of adding these instructions.
-cl::Enum<RegAllocDebugLevel_t> DEBUG_RA("dregalloc", cl::NoFlags,
+cl::Enum<RegAllocDebugLevel_t> 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"),
// RegisterAllocation pass front end...
//----------------------------------------------------------------------------
namespace {
- class RegisterAllocator : public MethodPass {
+ class RegisterAllocator : public FunctionPass {
TargetMachine &Target;
public:
inline RegisterAllocator(TargetMachine &T) : Target(T) {}
+
+ const char *getPassName() const { return "Register Allocation"; }
- bool runOnMethod(Method *M) {
+ bool runOnFunction(Function *F) {
if (DEBUG_RA)
- cerr << "\n******************** Method "<< M->getName()
+ cerr << "\n******************** Function "<< F->getName()
<< " ********************\n";
- PhyRegAlloc PRA(M, Target, &getAnalysis<MethodLiveVarInfo>(),
- &getAnalysis<cfg::LoopInfo>());
+ PhyRegAlloc PRA(F, Target, &getAnalysis<FunctionLiveVarInfo>(),
+ &getAnalysis<LoopInfo>());
PRA.allocateRegisters();
if (DEBUG_RA) cerr << "\nRegister allocation complete!\n";
return false;
}
- virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
- Pass::AnalysisSet &Destroyed,
- Pass::AnalysisSet &Provided) {
- Requires.push_back(cfg::LoopInfo::ID);
- Requires.push_back(MethodLiveVarInfo::ID);
- Destroyed.push_back(MethodLiveVarInfo::ID);
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired(LoopInfo::ID);
+ AU.addRequired(FunctionLiveVarInfo::ID);
}
};
}
-MethodPass *getRegisterAllocator(TargetMachine &T) {
+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 *Lvi,
- cfg::LoopInfo *LDC)
- : 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()),
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),
- &ResColList) );
+ RegClassList.push_back(new RegClass(F, MRI.getMachineRegClass(rc),
+ &ResColList));
}
PhyRegAlloc::~PhyRegAlloc() {
for( unsigned int rc=0; rc < NumOfRegClasses; rc++)
delete RegClassList[rc];
+
+ AddedInstrMap.clear();
}
//----------------------------------------------------------------------------
// 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)
//
- if( const Value *RetVal = MRI.getCallInstRetVal( MInst )) {
+ 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 = MRI.getCallInstIndirectAddrVal( MInst )) {
+ if( const Value *AddrVal = argDesc->getIndirectFuncPtr()) {
LiveRange *AddrValLR = LRI.getLiveRangeForValue( AddrVal );
assert( AddrValLR && "No LR for indirect addr val of call");
AddrValLR->setCallInterference();
if(DEBUG_RA) cerr << "Creating interference graphs ...\n";
unsigned BBLoopDepthCost;
- Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
-
- for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
+ for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
+ BBI != BBE; ++BBI) {
// find the 10^(loop_depth) of this BB
//
- BBLoopDepthCost = (unsigned) pow( 10.0, LoopDepthCalc->getLoopDepth(*BBI));
+ 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();
+ 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
//
} // 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
+ // add interferences for function arguments. Since there are no explict
+ // defs in the function for args, we have to add them manually
//
addInterferencesForArgs();
//----------------------------------------------------------------------------
-// This method will add interferences for incoming arguments to a method.
+// 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());
// get the argument list
- const Method::ArgumentListType& ArgList = Meth->getArgumentList();
+ const Function::ArgumentListType &ArgList = Meth->getArgumentList();
// get an iterator to arg list
- Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
+ Function::ArgumentListType::const_iterator ArgIt = ArgList.begin();
for( ; ArgIt != ArgList.end() ; ++ArgIt) { // for each argument
}
-
-
//----------------------------------------------------------------------------
// This method is called after register allocation is complete to set the
// allocated reisters in the machine code. This code will add register numbers
// additional instructions produced by the register allocator to the
// instruction stream.
//----------------------------------------------------------------------------
-void PhyRegAlloc::updateMachineCode()
-{
- Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
+//-----------------------------
+// Utility functions used below
+//-----------------------------
+inline void
+PrependInstructions(vector<MachineInstr *> &IBef,
+ MachineCodeForBasicBlock& MIVec,
+ MachineCodeForBasicBlock::iterator& MII,
+ const std::string& msg)
+{
+ if (!IBef.empty())
+ {
+ MachineInstr* OrigMI = *MII;
+ std::vector<MachineInstr *>::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;
+ }
+ }
+}
- for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
+inline void
+AppendInstructions(std::vector<MachineInstr *> &IAft,
+ MachineCodeForBasicBlock& MIVec,
+ MachineCodeForBasicBlock::iterator& MII,
+ const std::string& msg)
+{
+ if (!IAft.empty())
+ {
+ MachineInstr* OrigMI = *MII;
+ std::vector<MachineInstr *>::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()
+{
+ const BasicBlock* entryBB = Meth->getEntryNode();
+ if (entryBB) {
+ MachineCodeForBasicBlock& MIVec = entryBB->getMachineInstrVec();
+ MachineCodeForBasicBlock::iterator MII = MIVec.begin();
+
+ // Insert any instructions needed at method entry
+ 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 = (*BBI)->getMachineInstrVec();
+ for(MachineCodeForBasicBlock::iterator MII = MIVec.begin();
+ MII != MIVec.end(); ++MII) {
- MachineInstr *MInst = *MInstIterator;
+ MachineInstr *MInst = *MII;
unsigned Opcode = MInst->getOpCode();
if (TM.getInstrInfo().isCall(Opcode) ||
TM.getInstrInfo().isReturn(Opcode)) {
- AddedInstrns *AI = AddedInstrMap[ MInst];
- if ( !AI ) {
- AI = new AddedInstrns();
- AddedInstrMap[ MInst ] = AI;
- }
+ AddedInstrns &AI = AddedInstrMap[MInst];
// 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(MInst, LRI, AI, *this, *BBI);
+ MRI.colorCallArgs(MInst, LRI, &AI, *this, *BBI);
else if (TM.getInstrInfo().isReturn(Opcode))
- MRI.colorRetValue(MInst, LRI, AI);
+ MRI.colorRetValue(MInst, LRI, &AI);
}
// If there are instructions to be added, *before* this machine
// instruction, add them now.
//
- if( AddedInstrMap[ MInst ] ) {
- std::deque<MachineInstr *> &IBef = AddedInstrMap[MInst]->InstrnsBefore;
-
- if( ! IBef.empty() ) {
- std::deque<MachineInstr *>::iterator AdIt;
-
- for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) {
-
- if( DEBUG_RA) {
- cerr << "For inst " << *MInst;
- cerr << " PREPENDed instr: " << **AdIt << "\n";
- }
-
- 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)
unsigned delay;
if ((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){
- move2DelayedInstr(MInst, *(MInstIterator+delay) );
+ move2DelayedInstr(MInst, *(MII+delay) );
if(DEBUG_RA) cerr<< "\nMoved an added instr after the delay slot";
}
else {
-
-
// Here we can add the "instructions after" to the current
// instruction since there are no delay slots for this instruction
-
- std::deque<MachineInstr *> &IAft = AddedInstrMap[MInst]->InstrnsAfter;
-
- if( ! IAft.empty() ) {
-
- std::deque<MachineInstr *>::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 << "\n";
- }
-
- 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
}
mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
- MachineInstr *MIBef=NULL, *AdIMid=NULL, *MIAft=NULL;
+ MachineInstr *MIBef=NULL, *MIAft=NULL;
+ vector<MachineInstr*> AdIMid;
int TmpRegU = getUsableUniRegAtMI(RC, RegType, MInst,&LVSetBef, MIBef, MIAft);
// get the added instructions for this instruciton
- AddedInstrns *AI = AddedInstrMap[ MInst ];
- if ( !AI ) {
- AI = new AddedInstrns();
- AddedInstrMap[ MInst ] = AI;
- }
-
+ AddedInstrns &AI = AddedInstrMap[MInst];
- if( !isDef ) {
-
+ if (!isDef) {
// 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, TmpRegU,RegType);
-
+ MRI.cpMem2RegMI(MRI.getFramePointer(), SpillOff, TmpRegU,RegType, AdIMid);
+ AI.InstrnsBefore.insert(AI.InstrnsBefore.end(),
+ AdIMid.begin(), AdIMid.end());
+
if(MIBef)
- AI->InstrnsBefore.push_back(MIBef);
-
- AI->InstrnsBefore.push_back(AdIMid);
+ AI.InstrnsBefore.push_back(MIBef);
if(MIAft)
- AI->InstrnsAfter.push_front(MIAft);
+ AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft);
} else { // 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(TmpRegU, MRI.getFramePointer(), SpillOff,RegType);
-
+ MRI.cpReg2MemMI(TmpRegU, MRI.getFramePointer(), SpillOff,RegType, AdIMid);
+
if (MIBef)
- AI->InstrnsBefore.push_back(MIBef);
-
- AI->InstrnsAfter.push_front(AdIMid);
-
+ AI.InstrnsBefore.push_back(MIBef);
+
+ AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(),
+ AdIMid.begin(), AdIMid.end());
+
if (MIAft)
- AI->InstrnsAfter.push_front(MIAft);
+ AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft);
} // if !DEF
-
+
cerr << "\nFor Inst " << *MInst;
cerr << " - SPILLED LR: "; printSet(*LR);
cerr << "\n - Added Instructions:";
if (MIBef) cerr << *MIBef;
- cerr << *AdIMid;
+ for (vector<MachineInstr*>::const_iterator II=AdIMid.begin();
+ II != AdIMid.end(); ++II)
+ cerr << **II;
if (MIAft) cerr << *MIAft;
Op.setRegForValue(TmpRegU); // set the opearnd
int TmpOff = mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
RegU = getUniRegNotUsedByThisInst(RC, MInst);
- MIBef = MRI.cpReg2MemMI(RegU, MRI.getFramePointer(), TmpOff, RegType );
- MIAft = MRI.cpMem2RegMI(MRI.getFramePointer(), TmpOff, RegU, RegType );
+
+ vector<MachineInstr*> mvec;
+
+ MRI.cpReg2MemMI(RegU, MRI.getFramePointer(), TmpOff, RegType, mvec);
+ assert(mvec.size() == 1 && "Need to return a vector here too");
+ MIBef = * mvec.begin();
+
+ MRI.cpMem2RegMI(MRI.getFramePointer(), TmpOff, RegU, RegType, mvec);
+ assert(mvec.size() == 1 && "Need to return a vector here too");
+ MIAft = * mvec.begin();
}
return RegU;
// 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
// 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
- std::deque<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI]->InstrnsAfter;
+ std::vector<MachineInstr *> &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
- std::deque<MachineInstr *> &DelayedAft = DelayAdI->InstrnsAfter;
+ std::vector<MachineInstr *> &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
void PhyRegAlloc::printMachineCode()
{
- cerr << "\n;************** Method " << Meth->getName()
+ cerr << "\n;************** Function " << Meth->getName()
<< " *****************\n";
- Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
-
- for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
-
- cerr << "\n"; printLabel( *BBI); cerr << ": ";
+ 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::iterator MII = MIVec.begin();
// iterate over all the machine instructions in BB
- for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
-
- MachineInstr *const MInst = *MInstIterator;
-
+ for( ; MII != MIVec.end(); ++MII) {
+ MachineInstr *const MInst = *MII;
cerr << "\n\t";
cerr << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
-
-
- //for(MachineInstr::val_const_op_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 ||
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;
- }
+ AddedInstrns &AI = AddedInstrMap[CRMI];
- // Tmp stack poistions are needed by some calls that have spilled args
+ // Tmp stack positions 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);
+ MRI.colorCallArgs(CRMI, LRI, &AI, *this);
else if (TM.getInstrInfo().isReturn(OpCode))
- MRI.colorRetValue( CRMI, LRI, AI );
+ MRI.colorRetValue(CRMI, LRI, &AI);
else
assert(0 && "Non Call/Ret instrn in CallRetInstrList\n");
}
const MachineInstr *FirstMI = FirstBB->getMachineInstrVec().front();
assert(FirstMI && "No machine instruction in entry BB");
- AddedInstrns *AI = AddedInstrMap[FirstMI];
- if (!AI)
- AddedInstrMap[FirstMI] = AI = new AddedInstrns();
-
- MRI.colorMethodArgs(Meth, LRI, AI);
+ MRI.colorMethodArgs(Meth, LRI, &AddedInstrAtEntry);
}
projects / oota-llvm.git / blobdiff