#include "llvm/CodeGen/RegisterCoalescer.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetOptions.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/ADT/EquivalenceClasses.h"
+#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Debug.h"
cl::desc("Use new spilling heuristic"),
cl::init(false), cl::Hidden);
+static cl::opt<bool>
+PreSplitIntervals("pre-alloc-split",
+ cl::desc("Pre-register allocation live interval splitting"),
+ cl::init(false), cl::Hidden);
+
static RegisterRegAlloc
-linearscanRegAlloc("linearscan", " linear scan register allocator",
+linearscanRegAlloc("linearscan", "linear scan register allocator",
createLinearScanRegisterAllocator);
namespace {
struct VISIBILITY_HIDDEN RALinScan : public MachineFunctionPass {
static char ID;
- RALinScan() : MachineFunctionPass((intptr_t)&ID) {}
+ RALinScan() : MachineFunctionPass(&ID) {}
typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
- typedef std::vector<IntervalPtr> IntervalPtrs;
+ typedef SmallVector<IntervalPtr, 32> IntervalPtrs;
private:
/// RelatedRegClasses - This structure is built the first time a function is
/// compiled, and keeps track of which register classes have registers that
/// belong to multiple classes or have aliases that are in other classes.
EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses;
- std::map<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg;
+ DenseMap<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg;
MachineFunction* mf_;
MachineRegisterInfo* mri_;
const TargetMachine* tm_;
const TargetRegisterInfo* tri_;
const TargetInstrInfo* tii_;
- MachineRegisterInfo *reginfo_;
BitVector allocatableRegs_;
LiveIntervals* li_;
LiveStacks* ls_;
IntervalPtrs inactive_;
typedef std::priority_queue<LiveInterval*,
- std::vector<LiveInterval*>,
+ SmallVector<LiveInterval*, 64>,
greater_ptr<LiveInterval> > IntervalHeap;
IntervalHeap unhandled_;
std::auto_ptr<PhysRegTracker> prt_;
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<LiveIntervals>();
+ if (StrongPHIElim)
+ AU.addRequiredID(StrongPHIEliminationID);
// Make sure PassManager knows which analyses to make available
// to coalescing and which analyses coalescing invalidates.
AU.addRequiredTransitive<RegisterCoalescer>();
+ if (PreSplitIntervals)
+ AU.addRequiredID(PreAllocSplittingID);
AU.addRequired<LiveStacks>();
AU.addPreserved<LiveStacks>();
AU.addRequired<MachineLoopInfo>();
// belongs to, add info about aliases. We don't need to do this for targets
// without register aliases.
if (HasAliases)
- for (std::map<unsigned, const TargetRegisterClass*>::iterator
+ for (DenseMap<unsigned, const TargetRegisterClass*>::iterator
I = OneClassForEachPhysReg.begin(), E = OneClassForEachPhysReg.end();
I != E; ++I)
for (const unsigned *AS = TRI.getAliasSet(I->first); *AS; ++AS)
if ((cur.preference && cur.preference == Reg) || !cur.containsOneValue())
return Reg;
- VNInfo *vni = cur.getValNumInfo(0);
+ VNInfo *vni = cur.begin()->valno;
if (!vni->def || vni->def == ~1U || vni->def == ~0U)
return Reg;
MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
- unsigned SrcReg, DstReg;
- if (!CopyMI || !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg))
+ unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+ if (!CopyMI ||
+ !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg))
return Reg;
if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
if (!vrm_->isAssignedReg(SrcReg))
if (Reg == SrcReg)
return Reg;
- const TargetRegisterClass *RC = reginfo_->getRegClass(cur.reg);
+ const TargetRegisterClass *RC = mri_->getRegClass(cur.reg);
if (!RC->contains(SrcReg))
return Reg;
tm_ = &fn.getTarget();
tri_ = tm_->getRegisterInfo();
tii_ = tm_->getInstrInfo();
- reginfo_ = &mf_->getRegInfo();
allocatableRegs_ = tri_->getAllocatableSet(fn);
li_ = &getAnalysis<LiveIntervals>();
ls_ = &getAnalysis<LiveStacks>();
active_.empty() && inactive_.empty() &&
"interval sets should be empty on initialization");
+ handled_.reserve(li_->getNumIntervals());
+
for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
- if (TargetRegisterInfo::isPhysicalRegister(i->second.reg)) {
- reginfo_->setPhysRegUsed(i->second.reg);
- fixed_.push_back(std::make_pair(&i->second, i->second.begin()));
+ if (TargetRegisterInfo::isPhysicalRegister(i->second->reg)) {
+ mri_->setPhysRegUsed(i->second->reg);
+ fixed_.push_back(std::make_pair(i->second, i->second->begin()));
} else
- unhandled_.push(&i->second);
+ unhandled_.push(i->second);
}
}
MachineFunction::iterator EntryMBB = mf_->begin();
SmallVector<MachineBasicBlock*, 8> LiveInMBBs;
for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
- LiveInterval &cur = i->second;
+ LiveInterval &cur = *i->second;
unsigned Reg = 0;
bool isPhys = TargetRegisterInfo::isPhysicalRegister(cur.reg);
if (isPhys)
- Reg = i->second.reg;
+ Reg = cur.reg;
else if (vrm_->isAssignedReg(cur.reg))
Reg = attemptTrivialCoalescing(cur, vrm_->getPhys(cur.reg));
if (!Reg)
for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end();
I != E; ++I) {
const LiveRange &LR = *I;
- if (li_->findLiveInMBBs(LR, LiveInMBBs)) {
+ if (li_->findLiveInMBBs(LR.start, LR.end, LiveInMBBs)) {
for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i)
if (LiveInMBBs[i] != EntryMBB)
LiveInMBBs[i]->addLiveIn(Reg);
SI.weight += Weight;
VNInfo *VNI;
- if (SI.getNumValNums())
+ if (SI.hasAtLeastOneValue())
VNI = SI.getValNumInfo(0);
else
VNI = SI.getNextValue(~0U, 0, ls_->getVNInfoAllocator());
DOUT << "\tallocating current interval: ";
// This is an implicitly defined live interval, just assign any register.
- const TargetRegisterClass *RC = reginfo_->getRegClass(cur->reg);
+ const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
if (cur->empty()) {
unsigned physReg = cur->preference;
if (!physReg)
unsigned StartPosition = cur->beginNumber();
const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
- // If this live interval is defined by a move instruction and its source is
- // assigned a physical register that is compatible with the target register
- // class, then we should try to assign it the same register.
+ // If start of this live interval is defined by a move instruction and its
+ // source is assigned a physical register that is compatible with the target
+ // register class, then we should try to assign it the same register.
// This can happen when the move is from a larger register class to a smaller
// one, e.g. X86::mov32to32_. These move instructions are not coalescable.
- if (!cur->preference && cur->containsOneValue()) {
- VNInfo *vni = cur->getValNumInfo(0);
+ if (!cur->preference && cur->hasAtLeastOneValue()) {
+ VNInfo *vni = cur->begin()->valno;
if (vni->def && vni->def != ~1U && vni->def != ~0U) {
MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
- unsigned SrcReg, DstReg;
- if (CopyMI && tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) {
+ unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+ if (CopyMI &&
+ tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg)) {
unsigned Reg = 0;
if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
Reg = SrcReg;
unsigned Reg = i->first->reg;
assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
"Can only allocate virtual registers!");
- const TargetRegisterClass *RegRC = reginfo_->getRegClass(Reg);
+ const TargetRegisterClass *RegRC = mri_->getRegClass(Reg);
// If this is not in a related reg class to the register we're allocating,
// don't check it.
if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
if (minWeight == HUGE_VALF) {
// All registers must have inf weight. Just grab one!
minReg = BestPhysReg ? BestPhysReg : *RC->allocation_order_begin(*mf_);
- if (cur->weight == HUGE_VALF || cur->getSize() == 1)
+ if (cur->weight == HUGE_VALF ||
+ li_->getApproximateInstructionCount(*cur) == 0) {
// Spill a physical register around defs and uses.
li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_);
+ assignRegOrStackSlotAtInterval(cur);
+ return;
+ }
}
// Find up to 3 registers to consider as spill candidates.
if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
DOUT << "\t\t\tspilling(c): " << *cur << '\n';
float SSWeight;
+ SmallVector<LiveInterval*, 8> spillIs;
std::vector<LiveInterval*> added =
- li_->addIntervalsForSpills(*cur, loopInfo, *vrm_, SSWeight);
+ li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_, SSWeight);
addStackInterval(cur, ls_, li_, SSWeight, *vrm_);
if (added.empty())
return; // Early exit if all spills were folded.
earliestStart = std::min(earliestStart, sli->beginNumber());
float SSWeight;
std::vector<LiveInterval*> newIs =
- li_->addIntervalsForSpills(*sli, loopInfo, *vrm_, SSWeight);
+ li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_, SSWeight);
addStackInterval(sli, ls_, li_, SSWeight, *vrm_);
std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
spilled.insert(sli->reg);
SmallVector<unsigned, 256> inactiveCounts;
unsigned MaxInactiveCount = 0;
- const TargetRegisterClass *RC = reginfo_->getRegClass(cur->reg);
+ const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
// If this is not in a related reg class to the register we're allocating,
// don't check it.
- const TargetRegisterClass *RegRC = reginfo_->getRegClass(reg);
+ const TargetRegisterClass *RegRC = mri_->getRegClass(reg);
if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
reg = vrm_->getPhys(reg);
if (inactiveCounts.size() <= reg)
// If copy coalescer has assigned a "preferred" register, check if it's
// available first.
if (cur->preference) {
- if (prt_->isRegAvail(cur->preference)) {
+ if (prt_->isRegAvail(cur->preference) &&
+ RC->contains(cur->preference)) {
DOUT << "\t\tassigned the preferred register: "
<< tri_->getName(cur->preference) << "\n";
return cur->preference;
projects / oota-llvm.git / blobdiff