//===-- PhyRegAlloc.cpp ---------------------------------------------------===//
//
-// Register allocation for LLVM.
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Traditional graph-coloring global register allocator currently used
+// by the SPARC back-end.
+//
+// NOTE: This register allocator has some special support
+// for the Reoptimizer, such as not saving some registers on calls to
+// the first-level instrumentation function.
+//
+// NOTE 2: This register allocator can save its state in a global
+// variable in the module it's working on. This feature is not
+// thread-safe; if you have doubts, leave it turned off.
//
//===----------------------------------------------------------------------===//
+#include "AllocInfo.h"
+#include "IGNode.h"
#include "PhyRegAlloc.h"
#include "RegAllocCommon.h"
#include "RegClass.h"
-#include "IGNode.h"
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/iOther.h"
+#include "llvm/Module.h"
+#include "llvm/Type.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/CodeGen/FunctionLiveVarInfo.h"
+#include "llvm/CodeGen/InstrSelection.h"
+#include "llvm/CodeGen/MachineCodeForInstruction.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineInstrAnnot.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/CodeGen/MachineFunctionInfo.h"
-#include "llvm/CodeGen/FunctionLiveVarInfo.h"
-#include "llvm/CodeGen/InstrSelection.h"
-#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/Support/InstIterator.h"
#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Function.h"
-#include "llvm/Type.h"
-#include "llvm/iOther.h"
-#include "Support/STLExtras.h"
-#include "Support/SetOperations.h"
#include "Support/CommandLine.h"
+#include "Support/SetOperations.h"
+#include "Support/STLExtras.h"
#include <cmath>
+namespace llvm {
+
RegAllocDebugLevel_t DEBUG_RA;
+/// The reoptimizer wants to be able to grovel through the register
+/// allocator's state after it has done its job. This is a hack.
+///
+PhyRegAlloc::SavedStateMapTy ExportedFnAllocState;
+const bool SaveStateToModule = true;
+
static cl::opt<RegAllocDebugLevel_t, true>
DRA_opt("dregalloc", cl::Hidden, cl::location(DEBUG_RA),
cl::desc("enable register allocation debugging information"),
}
-
-//----------------------------------------------------------------------------
-// This method initially creates interference graphs (one in each reg class)
-// and IGNodeList (one in each IG). The actual nodes will be pushed later.
-//----------------------------------------------------------------------------
+/// Initialize interference graphs (one in each reg class) and IGNodeLists
+/// (one in each IG). The actual nodes will be pushed later.
+///
void PhyRegAlloc::createIGNodeListsAndIGs() {
if (DEBUG_RA >= RA_DEBUG_LiveRanges) std::cerr << "Creating LR lists ...\n";
- // hash map iterator
LiveRangeMapType::const_iterator HMI = LRI->getLiveRangeMap()->begin();
-
- // hash map end
LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap()->end();
for (; HMI != HMIEnd ; ++HMI ) {
}
-//----------------------------------------------------------------------------
-// This method will add all interferences at for a given instruction.
-// Interference 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,
+/// Add all interferences for a given instruction. Interference 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) {
ValueSet::const_iterator LIt = LVSet->begin();
}
-//----------------------------------------------------------------------------
-// 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
-// call instruction (except the return value of the call instruction - since
-// the return value does not interfere with that call itself).
-//----------------------------------------------------------------------------
-
+/// For a call instruction, this method sets the CallInterference flag in
+/// the LR of each variable live in the Live Variable Set live after the
+/// call instruction (except the return value of the call instruction - since
+/// the return value does not interfere with that call itself).
+///
void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst,
const ValueSet *LVSetAft) {
if (DEBUG_RA >= RA_DEBUG_Interference)
}
-//----------------------------------------------------------------------------
-// This method will walk thru code and create interferences in the IG of
-// 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()
-{
+/// Create interferences in the IG of each RegClass, and calculate 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 >= RA_DEBUG_Interference)
std::cerr << "Creating interference graphs ...\n";
// get the LV set after the instruction
const ValueSet &LVSetAI = LVI->getLiveVarSetAfterMInst(MInst, BB);
- bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
+ bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpcode());
- if (isCallInst ) {
+ if (isCallInst) {
// set the isCallInterference flag of each live range which extends
// across this call instruction. This information is used by graph
// coloring algorithm to avoid allocating volatile colors to live ranges
// 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.isDefOnly() || OpI.isDefAndUse()) // create a new LR since def
+ if (OpI.isDef()) // create a new LR since def
addInterference(*OpI, &LVSetAI, isCallInst);
// Calculate the spill cost of each live range
if (LR) LR->addSpillCost(BBLoopDepthCost);
}
- // if there are multiple defs in this instruction e.g. in SETX
- if (TM.getInstrInfo().isPseudoInstr(MInst->getOpCode()))
+ // Mark all operands of pseudo-instructions as interfering with one
+ // another. This must be done because pseudo-instructions may be
+ // expanded to multiple instructions by the assembler, so all the
+ // operands must get distinct registers.
+ 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();
for (unsigned z=0; z < NumOfImpRefs; z++)
- if (MInst->getImplicitOp(z).opIsDefOnly() ||
- MInst->getImplicitOp(z).opIsDefAndUse())
+ if (MInst->getImplicitOp(z).isDef())
addInterference( MInst->getImplicitRef(z), &LVSetAI, isCallInst );
} // for all machine instructions in BB
}
-//--------------------------------------------------------------------------
-// Pseudo-instructions may be expanded to multiple instructions by the
-// assembler. Consequently, all the operands must get distinct registers.
-// Therefore, we mark all operands of a pseudo-instruction as interfering
-// with one another.
-//--------------------------------------------------------------------------
-
+/// Mark all operands of the given MachineInstr as interfering with one
+/// another.
+///
void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) {
bool setInterf = false;
for (MachineInstr::const_val_op_iterator It1 = MInst->begin(),
ItE = MInst->end(); It1 != ItE; ++It1) {
const LiveRange *LROfOp1 = LRI->getLiveRangeForValue(*It1);
- assert((LROfOp1 || !It1.isUseOnly())&&"No LR for Def in PSEUDO insruction");
+ assert((LROfOp1 || It1.isDef()) && "No LR for Def in PSEUDO insruction");
MachineInstr::const_val_op_iterator It2 = It1;
for (++It2; It2 != ItE; ++It2) {
}
-//----------------------------------------------------------------------------
-// This method adds interferences for incoming arguments to a function.
-//----------------------------------------------------------------------------
-
+/// Add interferences for incoming arguments to a function.
+///
void PhyRegAlloc::addInterferencesForArgs() {
// get the InSet of root BB
const ValueSet &InSet = LVI->getInSetOfBB(&Fn->front());
addInterference(AI, &InSet, false);
if (DEBUG_RA >= RA_DEBUG_Interference)
- std::cerr << " - %% adding interference for argument " << RAV(AI) << "\n";
+ std::cerr << " - %% adding interference for argument " << RAV(AI) << "\n";
}
}
-//----------------------------------------------------------------------------
-// This method is called after register allocation is complete to set the
-// allocated registers in the machine code. This code will add register numbers
-// 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.
-//----------------------------------------------------------------------------
-
-//-----------------------------
-// Utility functions used below
-//-----------------------------
-inline void
-InsertBefore(MachineInstr* newMI,
- MachineBasicBlock& MBB,
- MachineBasicBlock::iterator& MII)
-{
+/// The following are utility functions used solely by updateMachineCode and
+/// the functions that it calls. They should probably be folded back into
+/// updateMachineCode at some point.
+///
+
+// used by: updateMachineCode (1 time), PrependInstructions (1 time)
+inline void InsertBefore(MachineInstr* newMI, MachineBasicBlock& MBB,
+ MachineBasicBlock::iterator& MII) {
MII = MBB.insert(MII, newMI);
++MII;
}
-inline void
-InsertAfter(MachineInstr* newMI,
- MachineBasicBlock& MBB,
- MachineBasicBlock::iterator& MII)
-{
+// used by: AppendInstructions (1 time)
+inline void InsertAfter(MachineInstr* newMI, MachineBasicBlock& MBB,
+ MachineBasicBlock::iterator& MII) {
++MII; // insert before the next instruction
MII = MBB.insert(MII, newMI);
}
-inline void
-DeleteInstruction(MachineBasicBlock& MBB,
- MachineBasicBlock::iterator& MII)
-{
+// used by: updateMachineCode (1 time)
+inline void DeleteInstruction(MachineBasicBlock& MBB,
+ MachineBasicBlock::iterator& MII) {
MII = MBB.erase(MII);
}
-inline void
-SubstituteInPlace(MachineInstr* newMI,
- MachineBasicBlock& MBB,
- MachineBasicBlock::iterator MII)
-{
+// used by: updateMachineCode (1 time)
+inline void SubstituteInPlace(MachineInstr* newMI, MachineBasicBlock& MBB,
+ MachineBasicBlock::iterator MII) {
*MII = newMI;
}
-inline void
-PrependInstructions(std::vector<MachineInstr *> &IBef,
- MachineBasicBlock& MBB,
- MachineBasicBlock::iterator& MII,
- const std::string& msg)
-{
- if (!IBef.empty())
- {
+// used by: updateMachineCode (2 times)
+inline void PrependInstructions(std::vector<MachineInstr *> &IBef,
+ MachineBasicBlock& MBB,
+ MachineBasicBlock::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)
- {
+ for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt) {
if (DEBUG_RA) {
if (OrigMI) std::cerr << "For MInst:\n " << *OrigMI;
std::cerr << msg << "PREPENDed instr:\n " << **AdIt << "\n";
}
}
-inline void
-AppendInstructions(std::vector<MachineInstr *> &IAft,
- MachineBasicBlock& MBB,
- MachineBasicBlock::iterator& MII,
- const std::string& msg)
-{
- if (!IAft.empty())
- {
+// used by: updateMachineCode (1 time)
+inline void AppendInstructions(std::vector<MachineInstr *> &IAft,
+ MachineBasicBlock& MBB,
+ MachineBasicBlock::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 )
- {
+ for ( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) {
if (DEBUG_RA) {
if (OrigMI) std::cerr << "For MInst:\n " << *OrigMI;
std::cerr << msg << "APPENDed instr:\n " << **AdIt << "\n";
}
}
+/// Set the registers for operands in the given MachineInstr, if a register was
+/// successfully allocated. Return true if any of its operands has been marked
+/// for spill.
+///
bool PhyRegAlloc::markAllocatedRegs(MachineInstr* MInst)
{
bool instrNeedsSpills = false;
// First, set the registers for operands in the machine instruction
// if a register was successfully allocated. Do this first because we
// will need to know which registers are already used by this instr'n.
- for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
- {
+ for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
MachineOperand& Op = MInst->getOperand(OpNum);
if (Op.getType() == MachineOperand::MO_VirtualRegister ||
- Op.getType() == MachineOperand::MO_CCRegister)
- {
+ Op.getType() == MachineOperand::MO_CCRegister) {
const Value *const Val = Op.getVRegValue();
if (const LiveRange* LR = LRI->getLiveRangeForValue(Val)) {
// Remember if any operand needs spilling
return instrNeedsSpills;
}
+/// Mark allocated registers (using markAllocatedRegs()) on the instruction
+/// that MII points to. Then, if it's a call instruction, insert caller-saving
+/// code before and after it. Finally, insert spill code before and after it,
+/// using insertCode4SpilledLR().
+///
void PhyRegAlloc::updateInstruction(MachineBasicBlock::iterator& MII,
- MachineBasicBlock &MBB)
-{
+ MachineBasicBlock &MBB) {
MachineInstr* MInst = *MII;
- unsigned Opcode = MInst->getOpCode();
+ unsigned Opcode = MInst->getOpcode();
// Reset tmp stack positions so they can be reused for each machine instr.
MF->getInfo()->popAllTempValues();
// registers. This must be done even for call return instructions
// since those are not handled by the special code above.
if (instrNeedsSpills)
- for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
- {
+ for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
MachineOperand& Op = MInst->getOperand(OpNum);
if (Op.getType() == MachineOperand::MO_VirtualRegister ||
- Op.getType() == MachineOperand::MO_CCRegister)
- {
+ Op.getType() == MachineOperand::MO_CCRegister) {
const Value* Val = Op.getVRegValue();
if (const LiveRange *LR = LRI->getLiveRangeForValue(Val))
if (LR->isMarkedForSpill())
} // for each operand
}
+/// Iterate over all the MachineBasicBlocks in the current function and set
+/// the allocated registers for each instruction (using updateInstruction()),
+/// after register allocation is complete. Then move code out of delay slots.
+///
void PhyRegAlloc::updateMachineCode()
{
// Insert any instructions needed at method entry
for (MachineFunction::iterator BBI = MF->begin(), BBE = MF->end();
BBI != BBE; ++BBI) {
-
MachineBasicBlock &MBB = *BBI;
// Iterate over all machine instructions in BB and mark operands with
// their assigned registers or insert spill code, as appropriate.
// Also, fix operands of call/return instructions.
for (MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII)
- if (! TM.getInstrInfo().isDummyPhiInstr((*MII)->getOpCode()))
+ if (! TM.getInstrInfo().isDummyPhiInstr((*MII)->getOpcode()))
updateInstruction(MII, MBB);
// Now, move code out of delay slots of branches and returns if needed.
for (MachineBasicBlock::iterator MII = MBB.begin();
MII != MBB.end(); ++MII)
if (unsigned delaySlots =
- TM.getInstrInfo().getNumDelaySlots((*MII)->getOpCode()))
- {
+ TM.getInstrInfo().getNumDelaySlots((*MII)->getOpcode())) {
MachineInstr *MInst = *MII, *DelaySlotMI = *(MII+1);
// Check the 2 conditions above:
// (1) Does a branch need instructions added after it?
// (2) O/w does delay slot instr. need instrns before or after?
- bool isBranch = (TM.getInstrInfo().isBranch(MInst->getOpCode()) ||
- TM.getInstrInfo().isReturn(MInst->getOpCode()));
+ bool isBranch = (TM.getInstrInfo().isBranch(MInst->getOpcode()) ||
+ TM.getInstrInfo().isReturn(MInst->getOpcode()));
bool cond1 = (isBranch &&
AddedInstrMap.count(MInst) &&
AddedInstrMap[MInst].InstrnsAfter.size() > 0);
(AddedInstrMap[DelaySlotMI].InstrnsBefore.size() > 0 ||
AddedInstrMap[DelaySlotMI].InstrnsAfter.size() > 0));
- if (cond1 || cond2)
- {
+ if (cond1 || cond2) {
assert((MInst->getOpCodeFlags() & AnnulFlag) == 0 &&
"FIXME: Moving an annulled delay slot instruction!");
assert(delaySlots==1 &&
MachineInstr *MInst = *MII;
// do not process Phis
- if (TM.getInstrInfo().isDummyPhiInstr(MInst->getOpCode()))
+ if (TM.getInstrInfo().isDummyPhiInstr(MInst->getOpcode()))
continue;
// if there are any added instructions...
AddedInstrns &CallAI = AddedInstrMap[MInst];
#ifndef NDEBUG
- bool isBranch = (TM.getInstrInfo().isBranch(MInst->getOpCode()) ||
- TM.getInstrInfo().isReturn(MInst->getOpCode()));
+ bool isBranch = (TM.getInstrInfo().isBranch(MInst->getOpcode()) ||
+ TM.getInstrInfo().isReturn(MInst->getOpcode()));
assert((!isBranch ||
AddedInstrMap[MInst].InstrnsAfter.size() <=
- TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) &&
+ TM.getInstrInfo().getNumDelaySlots(MInst->getOpcode())) &&
"Cannot put more than #delaySlots instrns after "
"branch or return! Need to handle temps differently.");
#endif
}
-//----------------------------------------------------------------------------
-// This method inserts spill code for AN operand whose LR was spilled.
-// This method may be called several times for a single machine instruction
-// if it contains many spilled operands. Each time it is called, it finds
-// a register which is not live at that instruction and also which is not
-// used by other spilled operands of the same instruction. Then it uses
-// this register temporarily to accommodate the spilled value.
-//----------------------------------------------------------------------------
-
+/// Insert spill code for AN operand whose LR was spilled. May be called
+/// repeatedly for a single MachineInstr if it has many spilled operands. On
+/// each call, it finds a register which is not live at that instruction and
+/// also which is not used by other spilled operands of the same
+/// instruction. Then it uses this register temporarily to accommodate the
+/// spilled value.
+///
void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
MachineBasicBlock::iterator& MII,
MachineBasicBlock &MBB,
MachineInstr *MInst = *MII;
const BasicBlock *BB = MBB.getBasicBlock();
- assert((! TM.getInstrInfo().isCall(MInst->getOpCode()) || OpNum == 0) &&
+ assert((! TM.getInstrInfo().isCall(MInst->getOpcode()) || OpNum == 0) &&
"Outgoing arg of a call must be handled elsewhere (func arg ok)");
- assert(! TM.getInstrInfo().isReturn(MInst->getOpCode()) &&
+ assert(! TM.getInstrInfo().isReturn(MInst->getOpcode()) &&
"Return value of a ret must be handled elsewhere");
MachineOperand& Op = MInst->getOperand(OpNum);
- bool isDef = Op.opIsDefOnly();
- bool isDefAndUse = Op.opIsDefAndUse();
+ bool isDef = Op.isDef();
+ bool isUse = Op.isUse();
unsigned RegType = MRI.getRegTypeForLR(LR);
int SpillOff = LR->getSpillOffFromFP();
RegClass *RC = LR->getRegClass();
// trample those! Verify that the set is included in the LV set before MInst.
if (MII != MBB.begin()) {
MachineInstr *PredMI = *(MII-1);
- if (unsigned DS = TM.getInstrInfo().getNumDelaySlots(PredMI->getOpCode()))
+ if (unsigned DS = TM.getInstrInfo().getNumDelaySlots(PredMI->getOpcode()))
assert(set_difference(LVI->getLiveVarSetBeforeMInst(PredMI), LVSetBef)
.empty() && "Live-var set before branch should be included in "
"live-var set of each delay slot instruction!");
}
#endif
- MF->getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType) );
+ MF->getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType));
std::vector<MachineInstr*> MIBef, MIAft;
std::vector<MachineInstr*> AdIMid;
// for the copy and not used across MInst.
int scratchRegType = -1;
int scratchReg = -1;
- if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
- {
+ if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) {
scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef,
MInst, MIBef, MIAft);
assert(scratchReg != MRI.getInvalidRegNum());
}
- if (!isDef || isDefAndUse) {
+ if (isUse) {
// 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
AdIMid.clear();
}
- if (isDef || isDefAndUse) { // if this is a Def
+ 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
}
-//----------------------------------------------------------------------------
-// This method inserts caller saving/restoring instructions before/after
-// a call machine instruction. The caller saving/restoring instructions are
-// inserted like:
-// ** caller saving instructions
-// other instructions inserted for the call by ColorCallArg
-// CALL instruction
-// other instructions inserted for the call ColorCallArg
-// ** caller restoring instructions
-//----------------------------------------------------------------------------
-
+/// Insert caller saving/restoring instructions before/after a call machine
+/// instruction (before or after any other instructions that were inserted for
+/// the call).
+///
void
PhyRegAlloc::insertCallerSavingCode(std::vector<MachineInstr*> &instrnsBefore,
std::vector<MachineInstr*> &instrnsAfter,
MachineInstr *CallMI,
- const BasicBlock *BB)
-{
- assert(TM.getInstrInfo().isCall(CallMI->getOpCode()));
+ const BasicBlock *BB) {
+ assert(TM.getInstrInfo().isCall(CallMI->getOpcode()));
// hash set to record which registers were saved/restored
hash_set<unsigned> PushedRegSet;
// LR can be null if it is a const since a const
// doesn't have a dominating def - see Assumptions above
- if( LR ) {
- if(! LR->isMarkedForSpill()) {
+ if (LR) {
+ if (! LR->isMarkedForSpill()) {
assert(LR->hasColor() && "LR is neither spilled nor colored?");
unsigned RCID = LR->getRegClassID();
unsigned Color = LR->getColor();
}
-//----------------------------------------------------------------------------
-// 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,
-// this method will simply return that register and set MIBef = MIAft = NULL.
-// Otherwise, it will return a register and MIAft and MIBef will contain
-// two instructions used to free up this returned register.
-// Returned register number is the UNIFIED register number
-//----------------------------------------------------------------------------
-
+/// Returns the unified register number of a temporary register to be used
+/// BEFORE MInst. If no register is available, it will pick one and modify
+/// MIBef and MIAft to contain instructions used to free up this returned
+/// register.
+///
int PhyRegAlloc::getUsableUniRegAtMI(const int RegType,
const ValueSet *LVSetBef,
MachineInstr *MInst,
std::vector<MachineInstr*>& MIAft) {
RegClass* RC = getRegClassByID(MRI.getRegClassIDOfRegType(RegType));
- int RegU = getUnusedUniRegAtMI(RC, RegType, MInst, LVSetBef);
+ int RegU = getUnusedUniRegAtMI(RC, RegType, MInst, LVSetBef);
if (RegU == -1) {
// we couldn't find an unused register. Generate code to free up a reg by
// Check if we need a scratch register to copy this register to memory.
int scratchRegType = -1;
- if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
- {
+ if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) {
int scratchReg = getUsableUniRegAtMI(scratchRegType, LVSetBef,
MInst, MIBef, MIAft);
assert(scratchReg != MRI.getInvalidRegNum());
ScratchRegsUsed.insert(std::make_pair(MInst, 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.
+ } 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 RegU;
}
-//----------------------------------------------------------------------------
-// This method is called to get a new unused register that can be used
-// to accommodate a temporary value. This method may be called several times
-// for a single machine instruction. Each time it is called, it finds a
-// register which is not live at that instruction and also which is not used
-// by other spilled operands of the same instruction. Return register number
-// is relative to the register class, NOT the unified number.
-//----------------------------------------------------------------------------
-
-int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC,
- const int RegType,
+/// Returns the register-class register number of a new unused register that
+/// can be used to accommodate a temporary value. May be called repeatedly
+/// for a single MachineInstr. On each call, it finds a register which is not
+/// live at that instruction and which is not used by any spilled operands of
+/// that instruction.
+///
+int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC, const int RegType,
const MachineInstr *MInst,
const ValueSet* LVSetBef) {
RC->clearColorsUsed(); // Reset array
}
-//----------------------------------------------------------------------------
-// Get any other register in a register class, other than what is used
-// by operands of a machine instruction. Returns the unified reg number.
-//----------------------------------------------------------------------------
-
+/// Return the unified register number of a register in class RC which is not
+/// used by any operands of MInst.
+///
int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
const int RegType,
const MachineInstr *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. Both explicit and implicit operands are set.
-//----------------------------------------------------------------------------
-
+/// Modify the IsColorUsedArr of register class RC, by setting the bits
+/// corresponding to register RegNo. This is a helper method of
+/// setRelRegsUsedByThisInst().
+///
static void markRegisterUsed(int RegNo, RegClass *RC, int RegType,
const TargetRegInfo &TRI) {
unsigned classId = 0;
}
void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC, int RegType,
- const MachineInstr *MI)
-{
+ const MachineInstr *MI) {
assert(OperandsColoredMap[MI] == true &&
"Illegal to call setRelRegsUsedByThisInst() until colored operands "
"are marked for an instruction.");
- // Add the registers already marked as used by the instruction.
+ // Add the registers already marked as used by the instruction. Both
+ // explicit and implicit operands are set.
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
if (MI->getOperand(i).hasAllocatedReg())
markRegisterUsed(MI->getOperand(i).getAllocatedRegNum(), RC, RegType,MRI);
}
-//----------------------------------------------------------------------------
-// If there are delay slots for an instruction, the instructions
-// added after it must really go after the delayed instruction(s).
-// So, we move the InstrAfter of that instruction to the
-// corresponding delayed instruction using the following method.
-//----------------------------------------------------------------------------
-
+/// If there are delay slots for an instruction, the instructions added after
+/// it must really go after the delayed instruction(s). So, we Move the
+/// InstrAfter of that instruction to the corresponding delayed instruction
+/// using the following method.
+///
void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI,
const MachineInstr *DelayedMI)
{
}
-//----------------------------------------------------------------------------
-// This method determines whether the suggested color of each live range
-// is really usable, and then calls its setSuggestedColorUsable() method to
-// record the answer. A suggested color is NOT usable when the suggested color
-// is volatile AND when there are call interferences.
-//----------------------------------------------------------------------------
-
+/// Determine whether the suggested color of each live range is really usable,
+/// and then call its setSuggestedColorUsable() method to record the answer. A
+/// suggested color is NOT usable when the suggested color is volatile AND
+/// when there are call interferences.
+///
void PhyRegAlloc::markUnusableSugColors()
{
LiveRangeMapType::const_iterator HMI = (LRI->getLiveRangeMap())->begin();
if (HMI->first) {
LiveRange *L = HMI->second; // get the LiveRange
if (L && L->hasSuggestedColor ())
- L->setSuggestedColorUsable
- (!(MRI.isRegVolatile (L->getRegClassID (), L->getSuggestedColor ())
- && L->isCallInterference ()));
+ L->setSuggestedColorUsable
+ (!(MRI.isRegVolatile (L->getRegClassID (), L->getSuggestedColor ())
+ && L->isCallInterference ()));
}
} // for all LR's in hash map
}
-//----------------------------------------------------------------------------
-// The following method will set the stack offsets of the live ranges that
-// are decided to be spilled. This must be called just after coloring the
-// LRs using the graph coloring algo. For each live range that is spilled,
-// this method allocate a new spill position on the stack.
-//----------------------------------------------------------------------------
-
+/// For each live range that is spilled, allocates a new spill position on the
+/// stack, and set the stack offsets of the live range that will be spilled to
+/// that position. This must be called just after coloring the LRs.
+///
void PhyRegAlloc::allocateStackSpace4SpilledLRs() {
if (DEBUG_RA) std::cerr << "\nSetting LR stack offsets for spills...\n";
}
-//----------------------------------------------------------------------------
-// The entry point to Register Allocation
-//----------------------------------------------------------------------------
+void PhyRegAlloc::saveStateForValue (std::vector<AllocInfo> &state,
+ const Value *V, unsigned Insn, int Opnd) {
+ LiveRangeMapType::const_iterator HMI = LRI->getLiveRangeMap ()->find (V);
+ LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap ()->end ();
+ AllocInfo::AllocStateTy AllocState = AllocInfo::NotAllocated;
+ int Placement = -1;
+ if ((HMI != HMIEnd) && HMI->second) {
+ LiveRange *L = HMI->second;
+ assert ((L->hasColor () || L->isMarkedForSpill ())
+ && "Live range exists but not colored or spilled");
+ if (L->hasColor ()) {
+ AllocState = AllocInfo::Allocated;
+ Placement = MRI.getUnifiedRegNum (L->getRegClassID (),
+ L->getColor ());
+ } else if (L->isMarkedForSpill ()) {
+ AllocState = AllocInfo::Spilled;
+ assert (L->hasSpillOffset ()
+ && "Live range marked for spill but has no spill offset");
+ Placement = L->getSpillOffFromFP ();
+ }
+ }
+ state.push_back (AllocInfo (Insn, Opnd, AllocState, Placement));
+}
+
+/// Save the global register allocation decisions made by the register
+/// allocator so that they can be accessed later (sort of like "poor man's
+/// debug info").
+///
+void PhyRegAlloc::saveState () {
+ std::vector<AllocInfo> &state = FnAllocState[Fn];
+ unsigned Insn = 0;
+ for (const_inst_iterator II=inst_begin (Fn), IE=inst_end (Fn); II!=IE; ++II){
+ saveStateForValue (state, (*II), Insn, -1);
+ for (unsigned i = 0; i < (*II)->getNumOperands (); ++i) {
+ const Value *V = (*II)->getOperand (i);
+ // Don't worry about it unless it's something whose reg. we'll need.
+ if (!isa<Argument> (V) && !isa<Instruction> (V))
+ continue;
+ saveStateForValue (state, V, Insn, i);
+ }
+ ++Insn;
+ }
+}
+
+
+/// Check the saved state filled in by saveState(), and abort if it looks
+/// wrong. Only used when debugging. FIXME: Currently it just prints out
+/// the state, which isn't quite as useful.
+///
+void PhyRegAlloc::verifySavedState () {
+ std::vector<AllocInfo> &state = FnAllocState[Fn];
+ unsigned Insn = 0;
+ for (const_inst_iterator II=inst_begin (Fn), IE=inst_end (Fn); II!=IE; ++II) {
+ const Instruction *I = *II;
+ MachineCodeForInstruction &Instrs = MachineCodeForInstruction::get (I);
+ std::cerr << "Instruction:\n" << " " << *I << "\n"
+ << "MachineCodeForInstruction:\n";
+ for (unsigned i = 0, n = Instrs.size (); i != n; ++i)
+ std::cerr << " " << *Instrs[i] << "\n";
+ std::cerr << "FnAllocState:\n";
+ for (unsigned i = 0; i < state.size (); ++i) {
+ AllocInfo &S = state[i];
+ if (Insn == S.Instruction)
+ std::cerr << " " << S << "\n";
+ }
+ std::cerr << "----------\n";
+ ++Insn;
+ }
+}
+
+
+/// Finish the job of saveState(), by collapsing FnAllocState into an LLVM
+/// Constant and stuffing it inside the Module. (NOTE: Soon, there will be
+/// other, better ways of storing the saved state; this one is cumbersome and
+/// does not work well with the JIT.)
+///
+bool PhyRegAlloc::doFinalization (Module &M) {
+ if (!SaveRegAllocState)
+ return false; // Nothing to do here, unless we're saving state.
+
+ // If saving state into the module, just copy new elements to the
+ // correct global.
+ if (!SaveStateToModule) {
+ ExportedFnAllocState = FnAllocState;
+ // FIXME: should ONLY copy new elements in FnAllocState
+ return false;
+ }
+
+ // Convert FnAllocState to a single Constant array and add it
+ // to the Module.
+ ArrayType *AT = ArrayType::get (AllocInfo::getConstantType (), 0);
+ std::vector<const Type *> TV;
+ TV.push_back (Type::UIntTy);
+ TV.push_back (AT);
+ PointerType *PT = PointerType::get (StructType::get (TV));
+
+ std::vector<Constant *> allstate;
+ for (Module::iterator I = M.begin (), E = M.end (); I != E; ++I) {
+ Function *F = I;
+ if (F->isExternal ()) continue;
+ if (FnAllocState.find (F) == FnAllocState.end ()) {
+ allstate.push_back (ConstantPointerNull::get (PT));
+ } else {
+ std::vector<AllocInfo> &state = FnAllocState[F];
+
+ // Convert state into an LLVM ConstantArray, and put it in a
+ // ConstantStruct (named S) along with its size.
+ std::vector<Constant *> stateConstants;
+ for (unsigned i = 0, s = state.size (); i != s; ++i)
+ stateConstants.push_back (state[i].toConstant ());
+ unsigned Size = stateConstants.size ();
+ ArrayType *AT = ArrayType::get (AllocInfo::getConstantType (), Size);
+ std::vector<const Type *> TV;
+ TV.push_back (Type::UIntTy);
+ TV.push_back (AT);
+ StructType *ST = StructType::get (TV);
+ std::vector<Constant *> CV;
+ CV.push_back (ConstantUInt::get (Type::UIntTy, Size));
+ CV.push_back (ConstantArray::get (AT, stateConstants));
+ Constant *S = ConstantStruct::get (ST, CV);
+
+ GlobalVariable *GV =
+ new GlobalVariable (ST, true,
+ GlobalValue::InternalLinkage, S,
+ F->getName () + ".regAllocState", &M);
+
+ // Have: { uint, [Size x { uint, int, uint, int }] } *
+ // Cast it to: { uint, [0 x { uint, int, uint, int }] } *
+ Constant *CE = ConstantExpr::getCast (ConstantPointerRef::get (GV), PT);
+ allstate.push_back (CE);
+ }
+ }
+
+ unsigned Size = allstate.size ();
+ // Final structure type is:
+ // { uint, [Size x { uint, [0 x { uint, int, uint, int }] } *] }
+ std::vector<const Type *> TV2;
+ TV2.push_back (Type::UIntTy);
+ ArrayType *AT2 = ArrayType::get (PT, Size);
+ TV2.push_back (AT2);
+ StructType *ST2 = StructType::get (TV2);
+ std::vector<Constant *> CV2;
+ CV2.push_back (ConstantUInt::get (Type::UIntTy, Size));
+ CV2.push_back (ConstantArray::get (AT2, allstate));
+ new GlobalVariable (ST2, true, GlobalValue::ExternalLinkage,
+ ConstantStruct::get (ST2, CV2), "_llvm_regAllocState",
+ &M);
+ return false; // No error.
+}
+
+
+/// Allocate registers for the machine code previously generated for F using
+/// the graph-coloring algorithm.
+///
bool PhyRegAlloc::runOnFunction (Function &F) {
if (DEBUG_RA)
std::cerr << "\n********* Function "<< F.getName () << " ***********\n";
// insert code to copy to the correct register
colorIncomingArgs();
- // Now update the machine code with register names and add any
- // additional code inserted by the register allocator to the instruction
- // stream
+ // Save register allocation state for this function in a Constant.
+ if (SaveRegAllocState)
+ saveState();
+ if (DEBUG_RA) { // Check our work.
+ verifySavedState ();
+ }
+
+ // 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) {
if (DEBUG_RA) std::cerr << "\nRegister allocation complete!\n";
return false; // Function was not modified
}
+
+} // End llvm namespace
projects / oota-llvm.git / blobdiff