//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "regalloc"
-#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "PhysRegTracker.h"
#include "VirtRegMap.h"
#include "llvm/Function.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
MachineRegisterInfo *reginfo_;
BitVector allocatableRegs_;
LiveIntervals* li_;
+ LiveStacks* ls_;
const MachineLoopInfo *loopInfo;
/// handled_ - Intervals are added to the handled_ set in the order of their
// Make sure PassManager knows which analyses to make available
// to coalescing and which analyses coalescing invalidates.
AU.addRequiredTransitive<RegisterCoalescer>();
+ AU.addRequired<LiveStacks>();
+ AU.addPreserved<LiveStacks>();
AU.addRequired<MachineLoopInfo>();
AU.addPreserved<MachineLoopInfo>();
AU.addPreservedID(MachineDominatorsID);
char RALinScan::ID = 0;
}
+static RegisterPass<RALinScan>
+X("linearscan-regalloc", "Linear Scan Register Allocator");
+
void RALinScan::ComputeRelatedRegClasses() {
const TargetRegisterInfo &TRI = *tri_;
unsigned SrcReg, DstReg;
if (!CopyMI || !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg))
return Reg;
- if (TargetRegisterInfo::isVirtualRegister(SrcReg))
+ if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
if (!vrm_->isAssignedReg(SrcReg))
return Reg;
else
SrcReg = vrm_->getPhys(SrcReg);
+ }
if (Reg == SrcReg)
return Reg;
// Try to coalesce.
if (!li_->conflictsWithPhysRegDef(cur, *vrm_, SrcReg)) {
- DOUT << "Coalescing: " << cur << " -> " << tri_->getName(SrcReg) << '\n';
+ DOUT << "Coalescing: " << cur << " -> " << tri_->getName(SrcReg)
+ << '\n';
vrm_->clearVirt(cur.reg);
vrm_->assignVirt2Phys(cur.reg, SrcReg);
++NumCoalesce;
reginfo_ = &mf_->getRegInfo();
allocatableRegs_ = tri_->getAllocatableSet(fn);
li_ = &getAnalysis<LiveIntervals>();
+ ls_ = &getAnalysis<LiveStacks>();
loopInfo = &getAnalysis<MachineLoopInfo>();
// We don't run the coalescer here because we have no reason to
++NumIters;
DOUT << "\n*** CURRENT ***: " << *cur << '\n';
- processActiveIntervals(cur->beginNumber());
- processInactiveIntervals(cur->beginNumber());
+ if (!cur->empty()) {
+ processActiveIntervals(cur->beginNumber());
+ processInactiveIntervals(cur->beginNumber());
- assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
- "Can only allocate virtual registers!");
+ assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
+ "Can only allocate virtual registers!");
+ }
// Allocating a virtual register. try to find a free
// physical register or spill an interval (possibly this one) in order to
}
}
+/// addStackInterval - Create a LiveInterval for stack if the specified live
+/// interval has been spilled.
+static void addStackInterval(LiveInterval *cur, LiveStacks *ls_,
+ LiveIntervals *li_, float &Weight,
+ VirtRegMap &vrm_) {
+ int SS = vrm_.getStackSlot(cur->reg);
+ if (SS == VirtRegMap::NO_STACK_SLOT)
+ return;
+ LiveInterval &SI = ls_->getOrCreateInterval(SS);
+ SI.weight += Weight;
+
+ VNInfo *VNI;
+ if (SI.getNumValNums())
+ VNI = SI.getValNumInfo(0);
+ else
+ VNI = SI.getNextValue(~0U, 0, ls_->getVNInfoAllocator());
+
+ LiveInterval &RI = li_->getInterval(cur->reg);
+ // FIXME: This may be overly conservative.
+ SI.MergeRangesInAsValue(RI, VNI);
+}
+
/// assignRegOrStackSlotAtInterval - assign a register if one is available, or
/// spill.
void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
{
DOUT << "\tallocating current interval: ";
+ // This is an implicitly defined live interval, just assign any register.
+ const TargetRegisterClass *RC = reginfo_->getRegClass(cur->reg);
+ if (cur->empty()) {
+ unsigned physReg = cur->preference;
+ if (!physReg)
+ physReg = *RC->allocation_order_begin(*mf_);
+ DOUT << tri_->getName(physReg) << '\n';
+ // Note the register is not really in use.
+ vrm_->assignVirt2Phys(cur->reg, physReg);
+ return;
+ }
+
PhysRegTracker backupPrt = *prt_;
std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
unsigned StartPosition = cur->beginNumber();
- const TargetRegisterClass *RC = reginfo_->getRegClass(cur->reg);
const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
// If this live interval is defined by a move instruction and its source is
if (vni->def && vni->def != ~1U && vni->def != ~0U) {
MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
unsigned SrcReg, DstReg;
- if (tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) {
+ if (CopyMI && tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) {
unsigned Reg = 0;
if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
Reg = SrcReg;
// is very bad (it contains all callee clobbered registers for any functions
// with a call), so we want to avoid doing that if possible.
unsigned physReg = getFreePhysReg(cur);
+ unsigned BestPhysReg = physReg;
if (physReg) {
// We got a register. However, if it's in the fixed_ list, we might
// conflict with it. Check to see if we conflict with it or any of its
}
// All registers must have inf weight. Just grab one!
- if (!minReg)
- minReg = *RC->allocation_order_begin(*mf_);
+ if (!minReg) {
+ minReg = BestPhysReg ? BestPhysReg : *RC->allocation_order_begin(*mf_);
+ if (cur->weight == HUGE_VALF || cur->getSize() == 1)
+ // Spill a physical register around defs and uses.
+ li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_);
+ }
}
DOUT << "\t\tregister with min weight: "
// linearscan.
if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
DOUT << "\t\t\tspilling(c): " << *cur << '\n';
+ float SSWeight;
std::vector<LiveInterval*> added =
- li_->addIntervalsForSpills(*cur, loopInfo, *vrm_);
+ li_->addIntervalsForSpills(*cur, loopInfo, *vrm_, SSWeight);
+ addStackInterval(cur, ls_, li_, SSWeight, *vrm_);
if (added.empty())
return; // Early exit if all spills were folded.
cur->overlapsFrom(*i->first, i->second)) {
DOUT << "\t\t\tspilling(a): " << *i->first << '\n';
earliestStart = std::min(earliestStart, i->first->beginNumber());
+ float SSWeight;
std::vector<LiveInterval*> newIs =
- li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_);
+ li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_, SSWeight);
+ addStackInterval(i->first, ls_, li_, SSWeight, *vrm_);
std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
spilled.insert(reg);
}
cur->overlapsFrom(*i->first, i->second-1)) {
DOUT << "\t\t\tspilling(i): " << *i->first << '\n';
earliestStart = std::min(earliestStart, i->first->beginNumber());
+ float SSWeight;
std::vector<LiveInterval*> newIs =
- li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_);
+ li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_, SSWeight);
+ addStackInterval(i->first, ls_, li_, SSWeight, *vrm_);
std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
spilled.insert(reg);
}
/// getFreePhysReg - return a free physical register for this virtual register
/// interval if we have one, otherwise return 0.
unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
- std::vector<unsigned> inactiveCounts(tri_->getNumRegs(), 0);
+ SmallVector<unsigned, 256> inactiveCounts;
unsigned MaxInactiveCount = 0;
const TargetRegisterClass *RC = reginfo_->getRegClass(cur->reg);
const TargetRegisterClass *RegRC = reginfo_->getRegClass(reg);
if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
reg = vrm_->getPhys(reg);
+ if (inactiveCounts.size() <= reg)
+ inactiveCounts.resize(reg+1);
++inactiveCounts[reg];
MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]);
}
// If copy coalescer has assigned a "preferred" register, check if it's
// available first.
- if (cur->preference)
+ if (cur->preference) {
if (prt_->isRegAvail(cur->preference)) {
DOUT << "\t\tassigned the preferred register: "
<< tri_->getName(cur->preference) << "\n";
} else
DOUT << "\t\tunable to assign the preferred register: "
<< tri_->getName(cur->preference) << "\n";
+ }
// Scan for the first available register.
TargetRegisterClass::iterator I = RC->allocation_order_begin(*mf_);
TargetRegisterClass::iterator E = RC->allocation_order_end(*mf_);
+ assert(I != E && "No allocatable register in this register class!");
for (; I != E; ++I)
if (prt_->isRegAvail(*I)) {
FreeReg = *I;
- FreeRegInactiveCount = inactiveCounts[FreeReg];
+ if (FreeReg < inactiveCounts.size())
+ FreeRegInactiveCount = inactiveCounts[FreeReg];
+ else
+ FreeRegInactiveCount = 0;
break;
}
-
+
// If there are no free regs, or if this reg has the max inactive count,
// return this register.
if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) return FreeReg;
// reevaluated now.
for (; I != E; ++I) {
unsigned Reg = *I;
- if (prt_->isRegAvail(Reg) && FreeRegInactiveCount < inactiveCounts[Reg]) {
+ if (prt_->isRegAvail(Reg) && Reg < inactiveCounts.size() &&
+ FreeRegInactiveCount < inactiveCounts[Reg]) {
FreeReg = Reg;
FreeRegInactiveCount = inactiveCounts[Reg];
if (FreeRegInactiveCount == MaxInactiveCount)
projects / oota-llvm.git / blobdiff