#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/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(Function *F) {
+ bool runOnFunction(Function *F) {
if (DEBUG_RA)
- cerr << "\n******************** Method "<< F->getName()
+ cerr << "\n******************** Function "<< F->getName()
<< " ********************\n";
- PhyRegAlloc PRA(F, 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(Function *F,
- const TargetMachine& tm,
- MethodLiveVarInfo *Lvi,
- cfg::LoopInfo *LDC)
+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),
// 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();
// 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
//
}
-
-
//----------------------------------------------------------------------------
// 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()
+
+//-----------------------------
+// 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;
+ }
+ }
+}
+
+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);
+ }
+ }
+}
+
+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) {
- // 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) {
+ MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
+ for(MachineCodeForBasicBlock::iterator MII = MIVec.begin();
+ MII != MIVec.end(); ++MII) {
- MachineInstr *MInst = *MInstIterator;
+ MachineInstr *MInst = *MII;
unsigned Opcode = MInst->getOpCode();
// instruction, add them now.
//
if(AddedInstrMap.count(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;
- }
-
- }
-
+ PrependInstructions(AddedInstrMap[MInst].InstrnsBefore, MIVec, MII,"");
}
-
+
// If there are instructions to be added *after* this machine
// instruction, add them now
//
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()) {
- ++MInstIterator; // advance to the next instruction
-
- std::deque<MachineInstr *>::iterator AdIt;
- 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);
// 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);
-
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.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
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];
// "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
// 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;
const MachineInstr *FirstMI = FirstBB->getMachineInstrVec().front();
assert(FirstMI && "No machine instruction in entry BB");
- MRI.colorMethodArgs(Meth, LRI, &AddedInstrMap[FirstMI]);
+ MRI.colorMethodArgs(Meth, LRI, &AddedInstrAtEntry);
}
projects / oota-llvm.git / blobdiff