#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 {
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>();
void ComputeRelatedRegClasses();
- bool noEarlyClobberConflict(LiveInterval *cur, unsigned RegNo);
- unsigned findPhysReg(MachineOperand &MO);
-
template <typename ItTy>
void printIntervals(const char* const str, ItTy i, ItTy e) const {
if (str) DOUT << str << " intervals:\n";
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))
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());
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;
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);
unhandled_.push(added[i]);
}
-/// findPhysReg - get the physical register, if any, assigned to this operand.
-/// This may be an original physical register, or the physical register which
-/// has been assigned to a virtual register.
-unsigned RALinScan::findPhysReg(MachineOperand &MO) {
- unsigned PhysReg = MO.getReg();
- if (PhysReg && TargetRegisterInfo::isVirtualRegister(PhysReg)) {
- if (!vrm_->hasPhys(PhysReg))
- return 0;
- PhysReg = vrm_->getPhys(PhysReg);
- }
- return PhysReg;
-}
-
-/// noEarlyClobberConflict - see whether LiveInternal cur has a conflict with
-/// hard reg HReg because of earlyclobbers.
-///
-/// Earlyclobber operands may not be assigned the same register as
-/// each other, or as earlyclobber-conflict operands (i.e. those that
-/// are non-earlyclobbered inputs to an asm that also has earlyclobbers).
-///
-/// Thus there are two cases to check for:
-/// 1. cur->reg is an earlyclobber-conflict register and HReg is an
-/// earlyclobber register in some asm that also has cur->reg as an input.
-/// 2. cur->reg is an earlyclobber register and HReg is an
-/// earlyclobber-conflict input, or a different earlyclobber register,
-/// elsewhere in some asm.
-/// In both cases HReg can be assigned by the user, or assigned early in
-/// register allocation.
-///
-/// Dropping the distinction between earlyclobber and earlyclobber-conflict,
-/// keeping only one bit, looks promising, but two earlyclobber-conflict
-/// operands may be assigned the same register if they happen to contain the
-/// same value, and that implementation would prevent this.
-///
-bool RALinScan::noEarlyClobberConflict(LiveInterval *cur, unsigned HReg) {
- if (cur->overlapsEarlyClobber) {
- for (MachineRegisterInfo::use_iterator I = mri_->use_begin(cur->reg),
- E = mri_->use_end(); I!=E; ++I) {
- MachineInstr *MI = I.getOperand().getParent();
- if (MI->getOpcode()==TargetInstrInfo::INLINEASM) {
- for (int i = MI->getNumOperands()-1; i>=0; --i) {
- MachineOperand &MO = MI->getOperand(i);
- if (MO.isRegister() && MO.isEarlyClobber()) {
- unsigned PhysReg = findPhysReg(MO);
- if (HReg==PhysReg) {
- DOUT << " earlyclobber conflict: " <<
- "%reg" << cur->reg << ", " << tri_->getName(HReg) << "\n\t";
- return false;
- }
- }
- }
- }
- }
- }
- if (cur->isEarlyClobber) {
- for (MachineRegisterInfo::def_iterator I = mri_->def_begin(cur->reg),
- E = mri_->def_end(); I!=E; ++I) {
- MachineInstr *MI = I.getOperand().getParent();
- if (MI->getOpcode()==TargetInstrInfo::INLINEASM) {
- // make sure cur->reg is really clobbered in this instruction.
- bool earlyClobberFound = false, overlapFound = false;
- for (int i = MI->getNumOperands()-1; i>=0; --i) {
- MachineOperand &MO = MI->getOperand(i);
- if (MO.isRegister()) {
- if ((MO.overlapsEarlyClobber() || MO.isEarlyClobber())) {
- unsigned PhysReg = findPhysReg(MO);
- if (HReg==PhysReg)
- overlapFound = true;
- }
- if (MO.isEarlyClobber() && cur->reg==MO.getReg())
- earlyClobberFound = true;
- }
- }
- if (earlyClobberFound && overlapFound) {
- DOUT << " earlyclobber conflict: " <<
- "%reg" << cur->reg << ", " << tri_->getName(HReg) << "\n\t";
- return false;
- }
- }
- }
- }
- return true;
-}
-
/// getFreePhysReg - return a free physical register for this virtual register
/// interval if we have one, otherwise return 0.
unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
unsigned FreeRegInactiveCount = 0;
// If copy coalescer has assigned a "preferred" register, check if it's
- // available first. Coalescer can create new earlyclobber interferences,
- // so we need to check that.
+ // available first.
if (cur->preference) {
if (prt_->isRegAvail(cur->preference) &&
- RC->contains(cur->preference) &&
- noEarlyClobberConflict(cur, cur->preference)) {
+ RC->contains(cur->preference)) {
DOUT << "\t\tassigned the preferred register: "
<< tri_->getName(cur->preference) << "\n";
return cur->preference;
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) &&
- noEarlyClobberConflict(cur, *I)) {
+ if (prt_->isRegAvail(*I)) {
FreeReg = *I;
if (FreeReg < inactiveCounts.size())
FreeRegInactiveCount = inactiveCounts[FreeReg];
for (; I != E; ++I) {
unsigned Reg = *I;
if (prt_->isRegAvail(Reg) && Reg < inactiveCounts.size() &&
- FreeRegInactiveCount < inactiveCounts[Reg] &&
- noEarlyClobberConflict(cur, *I)) {
+ FreeRegInactiveCount < inactiveCounts[Reg]) {
FreeReg = Reg;
FreeRegInactiveCount = inactiveCounts[Reg];
if (FreeRegInactiveCount == MaxInactiveCount)