//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "regalloc"
-#include "llvm/BasicBlock.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/IndexedMap.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SparseSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
-#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetMachine.h"
+#include "llvm/IR/BasicBlock.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/IndexedMap.h"
-#include "llvm/ADT/SmallSet.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/SparseSet.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/STLExtras.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
#include <algorithm>
using namespace llvm;
// PhysRegState - One of the RegState enums, or a virtreg.
std::vector<unsigned> PhysRegState;
- // UsedInInstr - BitVector of physregs that are used in the current
- // instruction, and so cannot be allocated.
- BitVector UsedInInstr;
+ // Set of register units.
+ typedef SparseSet<unsigned> UsedInInstrSet;
+
+ // Set of register units that are used in the current instruction, and so
+ // cannot be allocated.
+ UsedInInstrSet UsedInInstr;
+
+ // Mark a physreg as used in this instruction.
+ void markRegUsedInInstr(unsigned PhysReg) {
+ for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
+ UsedInInstr.insert(*Units);
+ }
+
+ // Check if a physreg or any of its aliases are used in this instruction.
+ bool isRegUsedInInstr(unsigned PhysReg) const {
+ for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
+ if (UsedInInstr.count(*Units))
+ return true;
+ return false;
+ }
// SkippedInstrs - Descriptors of instructions whose clobber list was
// ignored because all registers were spilled. It is still necessary to
// not be erased.
bool isBulkSpilling;
- enum {
+ enum LLVM_ENUM_INT_TYPE(unsigned) {
spillClean = 1,
spillDirty = 100,
spillImpossible = ~0u
unsigned VirtReg, unsigned Hint);
LiveRegMap::iterator reloadVirtReg(MachineInstr *MI, unsigned OpNum,
unsigned VirtReg, unsigned Hint);
- void spillAll(MachineInstr *MI);
+ void spillAll(MachineBasicBlock::iterator MI);
bool setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg);
- void addRetOperands(MachineBasicBlock *MBB);
};
char RAFast::ID = 0;
}
/// its virtual register, and it is guaranteed to be a block-local register.
///
bool RAFast::isLastUseOfLocalReg(MachineOperand &MO) {
- // Check for non-debug uses or defs following MO.
- // This is the most likely way to fail - fast path it.
- MachineOperand *Next = &MO;
- while ((Next = Next->getNextOperandForReg()))
- if (!Next->isDebug())
- return false;
-
// If the register has ever been spilled or reloaded, we conservatively assume
// it is a global register used in multiple blocks.
if (StackSlotForVirtReg[MO.getReg()] != -1)
return false;
// Check that the use/def chain has exactly one operand - MO.
- return &MRI->reg_nodbg_begin(MO.getReg()).getOperand() == &MO;
+ MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(MO.getReg());
+ if (&I.getOperand() != &MO)
+ return false;
+ return ++I == MRI->reg_nodbg_end();
}
/// addKillFlag - Set kill flags on last use of a virtual register.
// If this register is used by DBG_VALUE then insert new DBG_VALUE to
// identify spilled location as the place to find corresponding variable's
// value.
- SmallVector<MachineInstr *, 4> &LRIDbgValues =
+ SmallVectorImpl<MachineInstr *> &LRIDbgValues =
LiveDbgValueMap[LRI->VirtReg];
for (unsigned li = 0, le = LRIDbgValues.size(); li != le; ++li) {
MachineInstr *DBG = LRIDbgValues[li];
- const MDNode *MDPtr =
- DBG->getOperand(DBG->getNumOperands()-1).getMetadata();
- int64_t Offset = 0;
- if (DBG->getOperand(1).isImm())
- Offset = DBG->getOperand(1).getImm();
+ const MDNode *MDPtr = DBG->getOperand(2).getMetadata();
+ bool IsIndirect = DBG->isIndirectDebugValue();
+ uint64_t Offset = IsIndirect ? DBG->getOperand(1).getImm() : 0;
DebugLoc DL;
if (MI == MBB->end()) {
// If MI is at basic block end then use last instruction's location.
MachineBasicBlock::iterator EI = MI;
DL = (--EI)->getDebugLoc();
- }
- else
+ } else
DL = MI->getDebugLoc();
- if (MachineInstr *NewDV =
- TII->emitFrameIndexDebugValue(*MF, FI, Offset, MDPtr, DL)) {
- MachineBasicBlock *MBB = DBG->getParent();
- MBB->insert(MI, NewDV);
- DEBUG(dbgs() << "Inserting debug info due to spill:" << "\n" << *NewDV);
- }
+ MachineBasicBlock *MBB = DBG->getParent();
+ MachineInstr *NewDV =
+ BuildMI(*MBB, MI, DL, TII->get(TargetOpcode::DBG_VALUE))
+ .addFrameIndex(FI).addImm(Offset).addMetadata(MDPtr);
+ (void)NewDV;
+ DEBUG(dbgs() << "Inserting debug info due to spill:" << "\n" << *NewDV);
}
// Now this register is spilled there is should not be any DBG_VALUE
// pointing to this register because they are all pointing to spilled value
}
/// spillAll - Spill all dirty virtregs without killing them.
-void RAFast::spillAll(MachineInstr *MI) {
+void RAFast::spillAll(MachineBasicBlock::iterator MI) {
if (LiveVirtRegs.empty()) return;
isBulkSpilling = true;
// The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
unsigned PhysReg = MO.getReg();
assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
"Bad usePhysReg operand");
-
+ markRegUsedInInstr(PhysReg);
switch (PhysRegState[PhysReg]) {
case regDisabled:
break;
PhysRegState[PhysReg] = regFree;
// Fall through
case regFree:
- UsedInInstr.set(PhysReg);
MO.setIsKill();
return;
default:
"Instruction is not using a subregister of a reserved register");
// Leave the superregister in the working set.
PhysRegState[Alias] = regFree;
- UsedInInstr.set(Alias);
MO.getParent()->addRegisterKilled(Alias, TRI, true);
return;
case regFree:
if (TRI->isSuperRegister(PhysReg, Alias)) {
// Leave the superregister in the working set.
- UsedInInstr.set(Alias);
MO.getParent()->addRegisterKilled(Alias, TRI, true);
return;
}
// All aliases are disabled, bring register into working set.
PhysRegState[PhysReg] = regFree;
- UsedInInstr.set(PhysReg);
MO.setIsKill();
}
/// reserved instead of allocated.
void RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg,
RegState NewState) {
- UsedInInstr.set(PhysReg);
+ markRegUsedInInstr(PhysReg);
switch (unsigned VirtReg = PhysRegState[PhysReg]) {
case regDisabled:
break;
// can be allocated directly.
// Returns spillImpossible when PhysReg or an alias can't be spilled.
unsigned RAFast::calcSpillCost(unsigned PhysReg) const {
- if (UsedInInstr.test(PhysReg)) {
+ if (isRegUsedInInstr(PhysReg)) {
DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is already used in instr.\n");
return spillImpossible;
}
unsigned Cost = 0;
for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
unsigned Alias = *AI;
- if (UsedInInstr.test(Alias))
- return spillImpossible;
switch (unsigned VirtReg = PhysRegState[Alias]) {
case regDisabled:
break;
// Ignore invalid hints.
if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) ||
- !RC->contains(Hint) || !RegClassInfo.isAllocatable(Hint)))
+ !RC->contains(Hint) || !MRI->isAllocatable(Hint)))
Hint = 0;
// Take hint when possible.
}
}
- ArrayRef<unsigned> AO = RegClassInfo.getOrder(RC);
+ ArrayRef<MCPhysReg> AO = RegClassInfo.getOrder(RC);
// First try to find a completely free register.
- for (ArrayRef<unsigned>::iterator I = AO.begin(), E = AO.end(); I != E; ++I) {
+ for (ArrayRef<MCPhysReg>::iterator I = AO.begin(), E = AO.end(); I != E; ++I){
unsigned PhysReg = *I;
- if (PhysRegState[PhysReg] == regFree && !UsedInInstr.test(PhysReg)) {
+ if (PhysRegState[PhysReg] == regFree && !isRegUsedInInstr(PhysReg)) {
assignVirtToPhysReg(*LRI, PhysReg);
return LRI;
}
<< RC->getName() << "\n");
unsigned BestReg = 0, BestCost = spillImpossible;
- for (ArrayRef<unsigned>::iterator I = AO.begin(), E = AO.end(); I != E; ++I) {
+ for (ArrayRef<MCPhysReg>::iterator I = AO.begin(), E = AO.end(); I != E; ++I){
unsigned Cost = calcSpillCost(*I);
DEBUG(dbgs() << "\tRegister: " << PrintReg(*I, TRI) << "\n");
DEBUG(dbgs() << "\tCost: " << Cost << "\n");
}
// Nothing we can do. Report an error and keep going with a bad allocation.
- MI->emitError("ran out of registers during register allocation");
+ if (MI->isInlineAsm())
+ MI->emitError("inline assembly requires more registers than available");
+ else
+ MI->emitError("ran out of registers during register allocation");
definePhysReg(MI, *AO.begin(), regFree);
return assignVirtToPhysReg(VirtReg, *AO.begin());
}
LRI->LastUse = MI;
LRI->LastOpNum = OpNum;
LRI->Dirty = true;
- UsedInInstr.set(LRI->PhysReg);
+ markRegUsedInInstr(LRI->PhysReg);
return LRI;
}
assert(LRI->PhysReg && "Register not assigned");
LRI->LastUse = MI;
LRI->LastOpNum = OpNum;
- UsedInInstr.set(LRI->PhysReg);
+ markRegUsedInInstr(LRI->PhysReg);
return LRI;
}
if (!MO.isReg() || !MO.isDef()) continue;
unsigned Reg = MO.getReg();
if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
+ markRegUsedInInstr(Reg);
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
- UsedInInstr.set(*AI);
if (ThroughRegs.count(PhysRegState[*AI]))
definePhysReg(MI, *AI, regFree);
}
}
// Restore UsedInInstr to a state usable for allocating normal virtual uses.
- UsedInInstr.reset();
+ UsedInInstr.clear();
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue;
if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
DEBUG(dbgs() << "\tSetting " << PrintReg(Reg, TRI)
<< " as used in instr\n");
- UsedInInstr.set(Reg);
+ markRegUsedInInstr(Reg);
}
// Also mark PartialDefs as used to avoid reallocation.
for (unsigned i = 0, e = PartialDefs.size(); i != e; ++i)
- UsedInInstr.set(PartialDefs[i]);
-}
-
-/// addRetOperand - ensure that a return instruction has an operand for each
-/// value live out of the function.
-///
-/// Things marked both call and return are tail calls; do not do this for them.
-/// The tail callee need not take the same registers as input that it produces
-/// as output, and there are dependencies for its input registers elsewhere.
-///
-/// FIXME: This should be done as part of instruction selection, and this helper
-/// should be deleted. Until then, we use custom logic here to create the proper
-/// operand under all circumstances. We can't use addRegisterKilled because that
-/// doesn't make sense for undefined values. We can't simply avoid calling it
-/// for undefined values, because we must ensure that the operand always exists.
-void RAFast::addRetOperands(MachineBasicBlock *MBB) {
- if (MBB->empty() || !MBB->back().isReturn() || MBB->back().isCall())
- return;
-
- MachineInstr *MI = &MBB->back();
-
- for (MachineRegisterInfo::liveout_iterator
- I = MBB->getParent()->getRegInfo().liveout_begin(),
- E = MBB->getParent()->getRegInfo().liveout_end(); I != E; ++I) {
- unsigned Reg = *I;
- assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
- "Cannot have a live-out virtual register.");
-
- bool hasDef = PhysRegState[Reg] == regReserved;
-
- // Check if this register already has an operand.
- bool Found = false;
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI->getOperand(i);
- if (!MO.isReg() || !MO.isUse())
- continue;
-
- unsigned OperReg = MO.getReg();
- if (!TargetRegisterInfo::isPhysicalRegister(OperReg))
- continue;
-
- if (OperReg == Reg || TRI->isSuperRegister(OperReg, Reg)) {
- // If the ret already has an operand for this physreg or a superset,
- // don't duplicate it. Set the kill flag if the value is defined.
- if (hasDef && !MO.isKill())
- MO.setIsKill();
- Found = true;
- break;
- }
- }
- if (!Found)
- MI->addOperand(MachineOperand::CreateReg(Reg,
- false /*IsDef*/,
- true /*IsImp*/,
- hasDef/*IsKill*/));
- }
+ markRegUsedInInstr(PartialDefs[i]);
}
void RAFast::AllocateBasicBlock() {
// Add live-in registers as live.
for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
E = MBB->livein_end(); I != E; ++I)
- if (RegClassInfo.isAllocatable(*I))
+ if (MRI->isAllocatable(*I))
definePhysReg(MII, *I, regReserved);
SmallVector<unsigned, 8> VirtDead;
}
else {
// Modify DBG_VALUE now that the value is in a spill slot.
- int64_t Offset = MI->getOperand(1).getImm();
+ bool IsIndirect = MI->isIndirectDebugValue();
+ uint64_t Offset = IsIndirect ? MI->getOperand(1).getImm() : 0;
const MDNode *MDPtr =
MI->getOperand(MI->getNumOperands()-1).getMetadata();
DebugLoc DL = MI->getDebugLoc();
- if (MachineInstr *NewDV =
- TII->emitFrameIndexDebugValue(*MF, SS, Offset, MDPtr, DL)) {
- DEBUG(dbgs() << "Modifying debug info due to spill:" <<
- "\t" << *MI);
- MachineBasicBlock *MBB = MI->getParent();
- MBB->insert(MBB->erase(MI), NewDV);
- // Scan NewDV operands from the beginning.
- MI = NewDV;
- ScanDbgValue = true;
- break;
- } else {
- // We can't allocate a physreg for a DebugValue; sorry!
- DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE");
- MO.setReg(0);
- }
+ MachineBasicBlock *MBB = MI->getParent();
+ MachineInstr *NewDV = BuildMI(*MBB, MBB->erase(MI), DL,
+ TII->get(TargetOpcode::DBG_VALUE))
+ .addFrameIndex(SS).addImm(Offset).addMetadata(MDPtr);
+ DEBUG(dbgs() << "Modifying debug info due to spill:"
+ << "\t" << *NewDV);
+ // Scan NewDV operands from the beginning.
+ MI = NewDV;
+ ScanDbgValue = true;
+ break;
}
}
LiveDbgValueMap[Reg].push_back(MI);
}
// Track registers used by instruction.
- UsedInInstr.reset();
+ UsedInInstr.clear();
// First scan.
// Mark physreg uses and early clobbers as used.
bool hasPhysDefs = false;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
+ // Make sure MRI knows about registers clobbered by regmasks.
+ if (MO.isRegMask()) {
+ MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());
+ continue;
+ }
if (!MO.isReg()) continue;
unsigned Reg = MO.getReg();
if (!Reg) continue;
}
continue;
}
- if (!RegClassInfo.isAllocatable(Reg)) continue;
+ if (!MRI->isAllocatable(Reg)) continue;
if (MO.isUse()) {
usePhysReg(MO);
} else if (MO.isEarlyClobber()) {
}
}
- MRI->addPhysRegsUsed(UsedInInstr);
+ for (UsedInInstrSet::iterator
+ I = UsedInInstr.begin(), E = UsedInInstr.end(); I != E; ++I)
+ MRI->setRegUnitUsed(*I);
// Track registers defined by instruction - early clobbers and tied uses at
// this point.
- UsedInInstr.reset();
+ UsedInInstr.clear();
if (hasEarlyClobbers) {
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
// Look for physreg defs and tied uses.
if (!MO.isDef() && !MI->isRegTiedToDefOperand(i)) continue;
- for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
- UsedInInstr.set(*AI);
+ markRegUsedInInstr(Reg);
}
}
unsigned Reg = MO.getReg();
if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
- if (!RegClassInfo.isAllocatable(Reg)) continue;
+ if (!MRI->isAllocatable(Reg)) continue;
definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ?
regFree : regReserved);
continue;
killVirtReg(VirtDead[i]);
VirtDead.clear();
- MRI->addPhysRegsUsed(UsedInInstr);
+ for (UsedInInstrSet::iterator
+ I = UsedInInstr.begin(), E = UsedInInstr.end(); I != E; ++I)
+ MRI->setRegUnitUsed(*I);
if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) {
DEBUG(dbgs() << "-- coalescing: " << *MI);
MBB->erase(Coalesced[i]);
NumCopies += Coalesced.size();
- // addRetOperands must run after we've seen all defs in this block.
- addRetOperands(MBB);
-
DEBUG(MBB->dump());
}
///
bool RAFast::runOnMachineFunction(MachineFunction &Fn) {
DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
- << "********** Function: "
- << ((Value*)Fn.getFunction())->getName() << '\n');
+ << "********** Function: " << Fn.getName() << '\n');
MF = &Fn;
MRI = &MF->getRegInfo();
TM = &Fn.getTarget();
TII = TM->getInstrInfo();
MRI->freezeReservedRegs(Fn);
RegClassInfo.runOnMachineFunction(Fn);
- UsedInInstr.resize(TRI->getNumRegs());
+ UsedInInstr.clear();
+ UsedInInstr.setUniverse(TRI->getNumRegUnits());
assert(!MRI->isSSA() && "regalloc requires leaving SSA");
projects / oota-llvm.git / blobdiff