//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "regalloc"
#include "llvm/CodeGen/Passes.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/IndexedMap.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
#include <algorithm>
using namespace llvm;
+#define DEBUG_TYPE "regalloc"
+
STATISTIC(NumStores, "Number of stores added");
STATISTIC(NumLoads , "Number of loads added");
STATISTIC(NumCopies, "Number of copies coalesced");
RAFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1),
isBulkSpilling(false) {}
private:
- const TargetMachine *TM;
MachineFunction *MF;
MachineRegisterInfo *MRI;
const TargetRegisterInfo *TRI;
bool Dirty; // Register needs spill.
explicit LiveReg(unsigned v)
- : LastUse(0), VirtReg(v), PhysReg(0), LastOpNum(0), Dirty(false) {}
+ : LastUse(nullptr), VirtReg(v), PhysReg(0), LastOpNum(0), Dirty(false){}
unsigned getSparseSetIndex() const {
return TargetRegisterInfo::virtReg2Index(VirtReg);
// not be erased.
bool isBulkSpilling;
- enum {
+ enum : unsigned {
spillClean = 1,
spillDirty = 100,
spillImpossible = ~0u
};
public:
- virtual const char *getPassName() const {
+ const char *getPassName() const override {
return "Fast Register Allocator";
}
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
MachineFunctionPass::getAnalysisUsage(AU);
}
private:
- bool runOnMachineFunction(MachineFunction &Fn);
+ bool runOnMachineFunction(MachineFunction &Fn) override;
void AllocateBasicBlock();
void handleThroughOperands(MachineInstr *MI,
SmallVectorImpl<unsigned> &VirtDead);
// Check that the use/def chain has exactly one operand - MO.
MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(MO.getReg());
- if (&I.getOperand() != &MO)
+ if (&*I != &MO)
return false;
return ++I == MRI->reg_nodbg_end();
}
// 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();
- 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
- 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);
- }
+ const MDNode *Var = DBG->getDebugVariable();
+ const MDNode *Expr = DBG->getDebugExpression();
+ bool IsIndirect = DBG->isIndirectDebugValue();
+ uint64_t Offset = IsIndirect ? DBG->getOperand(1).getImm() : 0;
+ DebugLoc DL = DBG->getDebugLoc();
+ assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
+ "Expected inlined-at fields to agree");
+ MachineInstr *NewDV =
+ BuildMI(*MBB, MI, DL, TII->get(TargetOpcode::DBG_VALUE))
+ .addFrameIndex(FI)
+ .addImm(Offset)
+ .addMetadata(Var)
+ .addMetadata(Expr);
+ assert(NewDV->getParent() == MBB && "dangling parent pointer");
+ (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
// now.
LRIDbgValues.clear();
if (SpillKill)
- LR.LastUse = 0; // Don't kill register again
+ LR.LastUse = nullptr; // Don't kill register again
}
killVirtReg(LRI);
}
case regDisabled:
break;
case regReserved:
- assert(TRI->isSuperRegister(PhysReg, Alias) &&
+ // Either PhysReg is a subregister of Alias and we mark the
+ // whole register as free, or PhysReg is the superregister of
+ // Alias and we mark all the aliases as disabled before freeing
+ // PhysReg.
+ // In the latter case, since PhysReg was disabled, this means that
+ // its value is defined only by physical sub-registers. This check
+ // is performed by the assert of the default case in this loop.
+ // Note: The value of the superregister may only be partial
+ // defined, that is why regDisabled is a valid state for aliases.
+ assert((TRI->isSuperRegister(PhysReg, Alias) ||
+ TRI->isSuperRegister(Alias, PhysReg)) &&
"Instruction is not using a subregister of a reserved register");
- // Leave the superregister in the working set.
- PhysRegState[Alias] = regFree;
- MO.getParent()->addRegisterKilled(Alias, TRI, true);
- return;
+ // Fall through.
case regFree:
if (TRI->isSuperRegister(PhysReg, Alias)) {
// Leave the superregister in the working set.
+ PhysRegState[Alias] = regFree;
MO.getParent()->addRegisterKilled(Alias, TRI, true);
return;
}
}
DEBUG(dbgs() << "Allocating " << PrintReg(VirtReg) << " from "
- << RC->getName() << "\n");
+ << TRI->getRegClassName(RC) << "\n");
unsigned BestReg = 0, BestCost = spillImpossible;
for (ArrayRef<MCPhysReg>::iterator I = AO.begin(), E = AO.end(); I != E; ++I){
}
// 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());
}
"Not a virtual register");
LiveRegMap::iterator LRI;
bool New;
- tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
+ std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
if (New) {
// If there is no hint, peek at the only use of this register.
if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) &&
MRI->hasOneNonDBGUse(VirtReg)) {
- const MachineInstr &UseMI = *MRI->use_nodbg_begin(VirtReg);
+ const MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(VirtReg);
// It's a copy, use the destination register as a hint.
if (UseMI.isCopyLike())
Hint = UseMI.getOperand(0).getReg();
"Not a virtual register");
LiveRegMap::iterator LRI;
bool New;
- tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
+ std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
MachineOperand &MO = MI->getOperand(OpNum);
if (New) {
LRI = allocVirtReg(MI, LRI, Hint);
continue;
if (MO.isEarlyClobber() || MI->isRegTiedToDefOperand(i) ||
(MO.getSubReg() && MI->readsVirtualRegister(Reg))) {
- if (ThroughRegs.insert(Reg))
+ if (ThroughRegs.insert(Reg).second)
DEBUG(dbgs() << ' ' << PrintReg(Reg));
}
}
}
else {
// Modify DBG_VALUE now that the value is in a spill slot.
- int64_t Offset = MI->getOperand(1).getImm();
- const MDNode *MDPtr =
- MI->getOperand(MI->getNumOperands()-1).getMetadata();
+ bool IsIndirect = MI->isIndirectDebugValue();
+ uint64_t Offset = IsIndirect ? MI->getOperand(1).getImm() : 0;
+ const MDNode *Var = MI->getDebugVariable();
+ const MDNode *Expr = MI->getDebugExpression();
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();
+ assert(
+ cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
+ "Expected inlined-at fields to agree");
+ MachineInstr *NewDV = BuildMI(*MBB, MBB->erase(MI), DL,
+ TII->get(TargetOpcode::DBG_VALUE))
+ .addFrameIndex(SS)
+ .addImm(Offset)
+ .addMetadata(Var)
+ .addMetadata(Expr);
+ 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);
if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
if (!MRI->isAllocatable(Reg)) continue;
- definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ?
- regFree : regReserved);
+ definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved);
continue;
}
LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc);
<< "********** Function: " << Fn.getName() << '\n');
MF = &Fn;
MRI = &MF->getRegInfo();
- TM = &Fn.getTarget();
- TRI = TM->getRegisterInfo();
- TII = TM->getInstrInfo();
+ TRI = MF->getSubtarget().getRegisterInfo();
+ TII = MF->getSubtarget().getInstrInfo();
MRI->freezeReservedRegs(Fn);
RegClassInfo.runOnMachineFunction(Fn);
UsedInInstr.clear();
}
// Add the clobber lists for all the instructions we skipped earlier.
- for (SmallPtrSet<const MCInstrDesc*, 4>::const_iterator
- I = SkippedInstrs.begin(), E = SkippedInstrs.end(); I != E; ++I)
- if (const uint16_t *Defs = (*I)->getImplicitDefs())
+ for (const MCInstrDesc *Desc : SkippedInstrs)
+ if (const uint16_t *Defs = Desc->getImplicitDefs())
while (*Defs)
MRI->setPhysRegUsed(*Defs++);