#include <cmath>
using namespace llvm;
-namespace {
- // Hidden options for help debugging.
- cl::opt<bool> DisableReMat("disable-rematerialization",
- cl::init(false), cl::Hidden);
-
- cl::opt<bool> SplitAtBB("split-intervals-at-bb",
- cl::init(true), cl::Hidden);
- cl::opt<int> SplitLimit("split-limit",
- cl::init(-1), cl::Hidden);
-}
+// Hidden options for help debugging.
+static cl::opt<bool> DisableReMat("disable-rematerialization",
+ cl::init(false), cl::Hidden);
+
+static cl::opt<bool> SplitAtBB("split-intervals-at-bb",
+ cl::init(true), cl::Hidden);
+static cl::opt<int> SplitLimit("split-limit",
+ cl::init(-1), cl::Hidden);
STATISTIC(numIntervals, "Number of original intervals");
STATISTIC(numIntervalsAfter, "Number of intervals after coalescing");
STATISTIC(numSplits , "Number of intervals split");
char LiveIntervals::ID = 0;
-namespace {
- RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
-}
+static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addPreserved<LiveVariables>();
}
void LiveIntervals::releaseMemory() {
+ MBB2IdxMap.clear();
Idx2MBBMap.clear();
mi2iMap_.clear();
i2miMap_.clear();
delete ClonedMIs[i];
}
-namespace llvm {
- inline bool operator<(unsigned V, const IdxMBBPair &IM) {
- return V < IM.first;
- }
-
- inline bool operator<(const IdxMBBPair &IM, unsigned V) {
- return IM.first < V;
- }
-
- struct Idx2MBBCompare {
- bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
- return LHS.first < RHS.first;
- }
- };
-}
-
-/// runOnMachineFunction - Register allocate the whole function
-///
-bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
- mf_ = &fn;
- tm_ = &fn.getTarget();
- tri_ = tm_->getRegisterInfo();
- tii_ = tm_->getInstrInfo();
- lv_ = &getAnalysis<LiveVariables>();
- allocatableRegs_ = tri_->getAllocatableSet(fn);
-
+void LiveIntervals::computeNumbering() {
+ Index2MiMap OldI2MI = i2miMap_;
+
+ Idx2MBBMap.clear();
+ MBB2IdxMap.clear();
+ mi2iMap_.clear();
+ i2miMap_.clear();
+
// Number MachineInstrs and MachineBasicBlocks.
// Initialize MBB indexes to a sentinal.
MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
i2miMap_.push_back(I);
MIIndex += InstrSlots::NUM;
}
-
+
+ if (StartIdx == MIIndex) {
+ // Empty MBB
+ MIIndex += InstrSlots::NUM;
+ i2miMap_.push_back(0);
+ }
// Set the MBB2IdxMap entry for this MBB.
MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
}
std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
+
+ if (!OldI2MI.empty())
+ for (iterator I = begin(), E = end(); I != E; ++I)
+ for (LiveInterval::iterator LI = I->second.begin(), LE = I->second.end();
+ LI != LE; ++LI) {
+
+ // Remap the start index of the live range to the corresponding new
+ // number, or our best guess at what it _should_ correspond to if the
+ // original instruction has been erased. This is either the following
+ // instruction or its predecessor.
+ unsigned offset = LI->start % InstrSlots::NUM;
+ if (OldI2MI[LI->start / InstrSlots::NUM])
+ LI->start = mi2iMap_[OldI2MI[LI->start / InstrSlots::NUM]] + offset;
+ else {
+ unsigned i = 0;
+ MachineInstr* newInstr = 0;
+ do {
+ newInstr = OldI2MI[LI->start / InstrSlots::NUM + i];
+ i++;
+ } while (!newInstr);
+
+ if (mi2iMap_[newInstr] ==
+ MBB2IdxMap[newInstr->getParent()->getNumber()].first)
+ LI->start = mi2iMap_[newInstr];
+ else
+ LI->start = mi2iMap_[newInstr] - InstrSlots::NUM + offset;
+ }
+
+ // Remap the ending index in the same way that we remapped the start,
+ // except for the final step where we always map to the immediately
+ // following instruction.
+ if (LI->end / InstrSlots::NUM < OldI2MI.size()) {
+ offset = LI->end % InstrSlots::NUM;
+ if (OldI2MI[LI->end / InstrSlots::NUM])
+ LI->end = mi2iMap_[OldI2MI[LI->end / InstrSlots::NUM]] + offset;
+ else {
+ unsigned i = 0;
+ MachineInstr* newInstr = 0;
+ do {
+ newInstr = OldI2MI[LI->end / InstrSlots::NUM + i];
+ i++;
+ } while (!newInstr);
+
+ LI->end = mi2iMap_[newInstr];
+ }
+ } else {
+ LI->end = i2miMap_.size() * InstrSlots::NUM;
+ }
+
+ // Remap the VNInfo def index, which works the same as the
+ // start indices above.
+ VNInfo* vni = LI->valno;
+ offset = vni->def % InstrSlots::NUM;
+ if (OldI2MI[vni->def / InstrSlots::NUM])
+ vni->def = mi2iMap_[OldI2MI[vni->def / InstrSlots::NUM]] + offset;
+ else {
+ unsigned i = 0;
+ MachineInstr* newInstr = 0;
+ do {
+ newInstr = OldI2MI[vni->def / InstrSlots::NUM + i];
+ i++;
+ } while (!newInstr);
+
+ if (mi2iMap_[newInstr] ==
+ MBB2IdxMap[newInstr->getParent()->getNumber()].first)
+ vni->def = mi2iMap_[newInstr];
+ else
+ vni->def = mi2iMap_[newInstr] - InstrSlots::NUM + offset;
+ }
+
+ // Remap the VNInfo kill indices, which works the same as
+ // the end indices above.
+ for (size_t i = 0; i < vni->kills.size(); ++i) {
+ offset = vni->kills[i] % InstrSlots::NUM;
+ if (OldI2MI[vni->kills[i] / InstrSlots::NUM])
+ vni->kills[i] = mi2iMap_[OldI2MI[vni->kills[i] / InstrSlots::NUM]] +
+ offset;
+ else {
+ unsigned e = 0;
+ MachineInstr* newInstr = 0;
+ do {
+ newInstr = OldI2MI[vni->kills[i] / InstrSlots::NUM + e];
+ e++;
+ } while (!newInstr);
+
+ vni->kills[i] = mi2iMap_[newInstr];
+ }
+ }
+ }
+}
+/// runOnMachineFunction - Register allocate the whole function
+///
+bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
+ mf_ = &fn;
+ mri_ = &mf_->getRegInfo();
+ tm_ = &fn.getTarget();
+ tri_ = tm_->getRegisterInfo();
+ tii_ = tm_->getInstrInfo();
+ lv_ = &getAnalysis<LiveVariables>();
+ allocatableRegs_ = tri_->getAllocatableSet(fn);
+
+ computeNumbering();
computeIntervals();
numIntervals += getNumIntervals();
void LiveIntervals::print(std::ostream &O, const Module* ) const {
O << "********** INTERVALS **********\n";
for (const_iterator I = begin(), E = end(); I != E; ++I) {
- I->second.print(DOUT, tri_);
- DOUT << "\n";
+ I->second.print(O, tri_);
+ O << "\n";
}
O << "********** MACHINEINSTRS **********\n";
DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
+ if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
+ DOUT << "is a implicit_def\n";
+ return;
+ }
+
// Virtual registers may be defined multiple times (due to phi
// elimination and 2-addr elimination). Much of what we do only has to be
// done once for the vreg. We use an empty interval to detect the first
MachineInstr *CopyMI = NULL;
unsigned SrcReg, DstReg;
if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
+ mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
tii_->isMoveInstr(*mi, SrcReg, DstReg))
CopyMI = mi;
ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
// live interval.
for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
if (vi.AliveBlocks[i]) {
- MachineBasicBlock *MBB = mf_->getBlockNumbered(i);
- if (!MBB->empty()) {
- LiveRange LR(getMBBStartIdx(i),
- getInstructionIndex(&MBB->back()) + InstrSlots::NUM,
- ValNo);
- interval.addRange(LR);
- DOUT << " +" << LR;
- }
+ LiveRange LR(getMBBStartIdx(i),
+ getMBBEndIdx(i),
+ ValNo);
+ interval.addRange(LR);
+ DOUT << " +" << LR;
}
}
// If this redefinition is dead, we need to add a dummy unit live
// range covering the def slot.
- if (lv_->RegisterDefIsDead(mi, interval.reg))
+ if (mi->registerDefIsDead(interval.reg, tri_))
interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
DOUT << " RESULT: ";
MachineInstr *CopyMI = NULL;
unsigned SrcReg, DstReg;
if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
+ mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
tii_->isMoveInstr(*mi, SrcReg, DstReg))
CopyMI = mi;
ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
// If it is not used after definition, it is considered dead at
// the instruction defining it. Hence its interval is:
// [defSlot(def), defSlot(def)+1)
- if (lv_->RegisterDefIsDead(mi, interval.reg)) {
+ if (mi->registerDefIsDead(interval.reg, tri_)) {
DOUT << " dead";
end = getDefIndex(start) + 1;
goto exit;
// [defSlot(def), useSlot(kill)+1)
while (++mi != MBB->end()) {
baseIndex += InstrSlots::NUM;
- if (lv_->KillsRegister(mi, interval.reg)) {
+ if (mi->killsRegister(interval.reg, tri_)) {
DOUT << " killed";
end = getUseIndex(baseIndex) + 1;
goto exit;
- } else if (lv_->ModifiesRegister(mi, interval.reg)) {
+ } else if (mi->modifiesRegister(interval.reg, tri_)) {
// Another instruction redefines the register before it is ever read.
// Then the register is essentially dead at the instruction that defines
// it. Hence its interval is:
MachineInstr *CopyMI = NULL;
unsigned SrcReg, DstReg;
if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
+ MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
tii_->isMoveInstr(*MI, SrcReg, DstReg))
CopyMI = MI;
handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), CopyMI);
// Def of a register also defines its sub-registers.
for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++AS)
- // Avoid processing some defs more than once.
- if (!MI->findRegisterDefOperand(*AS))
+ // If MI also modifies the sub-register explicitly, avoid processing it
+ // more than once. Do not pass in TRI here so it checks for exact match.
+ if (!MI->modifiesRegister(*AS))
handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
}
}
unsigned start = baseIndex;
unsigned end = start;
while (mi != MBB->end()) {
- if (lv_->KillsRegister(mi, interval.reg)) {
+ if (mi->killsRegister(interval.reg, tri_)) {
DOUT << " killed";
end = getUseIndex(baseIndex) + 1;
goto exit;
- } else if (lv_->ModifiesRegister(mi, interval.reg)) {
+ } else if (mi->modifiesRegister(interval.reg, tri_)) {
// Another instruction redefines the register before it is ever read.
// Then the register is essentially dead at the instruction that defines
// it. Hence its interval is:
MIIndex += InstrSlots::NUM;
}
+
+ if (MBB->begin() == miEnd) MIIndex += InstrSlots::NUM; // Empty MBB
}
}
if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
return VNI->copy->getOperand(1).getReg();
+ if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG)
+ return VNI->copy->getOperand(2).getReg();
unsigned SrcReg, DstReg;
if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg))
return SrcReg;
// Register allocator hooks.
//
+/// getReMatImplicitUse - If the remat definition MI has one (for now, we only
+/// allow one) virtual register operand, then its uses are implicitly using
+/// the register. Returns the virtual register.
+unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
+ MachineInstr *MI) const {
+ unsigned RegOp = 0;
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ MachineOperand &MO = MI->getOperand(i);
+ if (!MO.isRegister() || !MO.isUse())
+ continue;
+ unsigned Reg = MO.getReg();
+ if (Reg == 0 || Reg == li.reg)
+ continue;
+ // FIXME: For now, only remat MI with at most one register operand.
+ assert(!RegOp &&
+ "Can't rematerialize instruction with multiple register operand!");
+ RegOp = MO.getReg();
+ break;
+ }
+ return RegOp;
+}
+
+/// isValNoAvailableAt - Return true if the val# of the specified interval
+/// which reaches the given instruction also reaches the specified use index.
+bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
+ unsigned UseIdx) const {
+ unsigned Index = getInstructionIndex(MI);
+ VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno;
+ LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx);
+ return UI != li.end() && UI->valno == ValNo;
+}
+
/// isReMaterializable - Returns true if the definition MI of the specified
/// val# of the specified interval is re-materializable.
bool LiveIntervals::isReMaterializable(const LiveInterval &li,
return false;
isLoad = false;
- const TargetInstrDesc &TID = MI->getDesc();
- if (TID.isImplicitDef() || tii_->isTriviallyReMaterializable(MI)) {
- isLoad = TID.isSimpleLoad();
+ if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
return true;
- }
int FrameIdx = 0;
- if (!tii_->isLoadFromStackSlot(MI, FrameIdx) ||
- !mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx))
- return false;
+ if (tii_->isLoadFromStackSlot(MI, FrameIdx) &&
+ mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx))
+ // FIXME: Let target specific isReallyTriviallyReMaterializable determines
+ // this but remember this is not safe to fold into a two-address
+ // instruction.
+ // This is a load from fixed stack slot. It can be rematerialized.
+ return true;
- // This is a load from fixed stack slot. It can be rematerialized unless it's
- // re-defined by a two-address instruction.
- isLoad = true;
- for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
- i != e; ++i) {
- const VNInfo *VNI = *i;
- if (VNI == ValNo)
- continue;
- unsigned DefIdx = VNI->def;
- if (DefIdx == ~1U)
- continue; // Dead val#.
- MachineInstr *DefMI = (DefIdx == ~0u)
- ? NULL : getInstructionFromIndex(DefIdx);
- if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg)) {
- isLoad = false;
- return false;
+ if (tii_->isTriviallyReMaterializable(MI)) {
+ const TargetInstrDesc &TID = MI->getDesc();
+ isLoad = TID.isSimpleLoad();
+
+ unsigned ImpUse = getReMatImplicitUse(li, MI);
+ if (ImpUse) {
+ const LiveInterval &ImpLi = getInterval(ImpUse);
+ for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg),
+ re = mri_->use_end(); ri != re; ++ri) {
+ MachineInstr *UseMI = &*ri;
+ unsigned UseIdx = getInstructionIndex(UseMI);
+ if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
+ continue;
+ if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
+ return false;
+ }
}
+ return true;
}
- return true;
+
+ return false;
}
/// isReMaterializable - Returns true if every definition of MI of every
return false;
MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx);
bool DefIsLoad = false;
- if (!ReMatDefMI || !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad))
+ if (!ReMatDefMI ||
+ !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad))
return false;
isLoad |= DefIsLoad;
}
return true;
}
+/// FilterFoldedOps - Filter out two-address use operands. Return
+/// true if it finds any issue with the operands that ought to prevent
+/// folding.
+static bool FilterFoldedOps(MachineInstr *MI,
+ SmallVector<unsigned, 2> &Ops,
+ unsigned &MRInfo,
+ SmallVector<unsigned, 2> &FoldOps) {
+ const TargetInstrDesc &TID = MI->getDesc();
+
+ MRInfo = 0;
+ for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
+ unsigned OpIdx = Ops[i];
+ MachineOperand &MO = MI->getOperand(OpIdx);
+ // FIXME: fold subreg use.
+ if (MO.getSubReg())
+ return true;
+ if (MO.isDef())
+ MRInfo |= (unsigned)VirtRegMap::isMod;
+ else {
+ // Filter out two-address use operand(s).
+ if (!MO.isImplicit() &&
+ TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) {
+ MRInfo = VirtRegMap::isModRef;
+ continue;
+ }
+ MRInfo |= (unsigned)VirtRegMap::isRef;
+ }
+ FoldOps.push_back(OpIdx);
+ }
+ return false;
+}
+
+
/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
/// slot / to reg or any rematerialized load into ith operand of specified
/// MI. If it is successul, MI is updated with the newly created MI and
unsigned InstrIdx,
SmallVector<unsigned, 2> &Ops,
bool isSS, int Slot, unsigned Reg) {
- unsigned MRInfo = 0;
- const TargetInstrDesc &TID = MI->getDesc();
// If it is an implicit def instruction, just delete it.
- if (TID.isImplicitDef()) {
+ if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
RemoveMachineInstrFromMaps(MI);
vrm.RemoveMachineInstrFromMaps(MI);
MI->eraseFromParent();
return true;
}
+ // Filter the list of operand indexes that are to be folded. Abort if
+ // any operand will prevent folding.
+ unsigned MRInfo = 0;
SmallVector<unsigned, 2> FoldOps;
- for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
- unsigned OpIdx = Ops[i];
- // FIXME: fold subreg use.
- if (MI->getOperand(OpIdx).getSubReg())
- return false;
- if (MI->getOperand(OpIdx).isDef())
- MRInfo |= (unsigned)VirtRegMap::isMod;
- else {
- // Filter out two-address use operand(s).
- if (TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) {
- MRInfo = VirtRegMap::isModRef;
- continue;
- }
- MRInfo |= (unsigned)VirtRegMap::isRef;
- }
- FoldOps.push_back(OpIdx);
- }
+ if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
+ return false;
+
+ // The only time it's safe to fold into a two address instruction is when
+ // it's folding reload and spill from / into a spill stack slot.
+ if (DefMI && (MRInfo & VirtRegMap::isMod))
+ return false;
MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
: tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI);
if (fmi) {
+ // Remember this instruction uses the spill slot.
+ if (isSS) vrm.addSpillSlotUse(Slot, fmi);
+
// Attempt to fold the memory reference into the instruction. If
// we can do this, we don't need to insert spill code.
if (lv_)
vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
vrm.transferSpillPts(MI, fmi);
vrm.transferRestorePts(MI, fmi);
+ vrm.transferEmergencySpills(MI, fmi);
mi2iMap_.erase(MI);
i2miMap_[InstrIdx /InstrSlots::NUM] = fmi;
mi2iMap_[fmi] = InstrIdx;
/// canFoldMemoryOperand - Returns true if the specified load / store
/// folding is possible.
bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
- SmallVector<unsigned, 2> &Ops) const {
+ SmallVector<unsigned, 2> &Ops,
+ bool ReMat) const {
+ // Filter the list of operand indexes that are to be folded. Abort if
+ // any operand will prevent folding.
+ unsigned MRInfo = 0;
SmallVector<unsigned, 2> FoldOps;
- for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
- unsigned OpIdx = Ops[i];
- // FIXME: fold subreg use.
- if (MI->getOperand(OpIdx).getSubReg())
- return false;
- FoldOps.push_back(OpIdx);
- }
+ if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
+ return false;
+
+ // It's only legal to remat for a use, not a def.
+ if (ReMat && (MRInfo & VirtRegMap::isMod))
+ return false;
return tii_->canFoldMemoryOperand(MI, FoldOps);
}
return true;
}
+/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
+/// interval on to-be re-materialized operands of MI) with new register.
+void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
+ MachineInstr *MI, unsigned NewVReg,
+ VirtRegMap &vrm) {
+ // There is an implicit use. That means one of the other operand is
+ // being remat'ed and the remat'ed instruction has li.reg as an
+ // use operand. Make sure we rewrite that as well.
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ MachineOperand &MO = MI->getOperand(i);
+ if (!MO.isRegister())
+ continue;
+ unsigned Reg = MO.getReg();
+ if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
+ continue;
+ if (!vrm.isReMaterialized(Reg))
+ continue;
+ MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
+ MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
+ if (UseMO)
+ UseMO->setReg(NewVReg);
+ }
+}
+
/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
/// for addIntervalsForSpills to rewrite uses / defs for the given live range.
bool LiveIntervals::
-rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit,
- unsigned id, unsigned index, unsigned end, MachineInstr *MI,
+rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
+ bool TrySplit, unsigned index, unsigned end, MachineInstr *MI,
MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
unsigned Slot, int LdSlot,
bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
- VirtRegMap &vrm, MachineRegisterInfo &RegInfo,
+ VirtRegMap &vrm,
const TargetRegisterClass* rc,
SmallVector<int, 4> &ReMatIds,
- unsigned &NewVReg, bool &HasDef, bool &HasUse,
const MachineLoopInfo *loopInfo,
+ unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
std::map<unsigned,unsigned> &MBBVRegsMap,
- std::vector<LiveInterval*> &NewLIs) {
+ std::vector<LiveInterval*> &NewLIs, float &SSWeight) {
+ MachineBasicBlock *MBB = MI->getParent();
+ unsigned loopDepth = loopInfo->getLoopDepth(MBB);
bool CanFold = false;
RestartInstruction:
for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
}
}
- if (TryFold) {
+ // Update stack slot spill weight if we are splitting.
+ float Weight = getSpillWeight(HasDef, HasUse, loopDepth);
+ if (!TrySplit)
+ SSWeight += Weight;
+
+ if (!TryFold)
+ CanFold = false;
+ else {
// Do not fold load / store here if we are splitting. We'll find an
// optimal point to insert a load / store later.
if (!TrySplit) {
HasUse = false;
HasDef = false;
CanFold = false;
+ if (isRemoved(MI)) {
+ SSWeight -= Weight;
+ break;
+ }
goto RestartInstruction;
}
} else {
- CanFold = canFoldMemoryOperand(MI, Ops);
+ // We'll try to fold it later if it's profitable.
+ CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
}
- } else
- CanFold = false;
+ }
// Create a new virtual register for the spill interval.
bool CreatedNewVReg = false;
if (NewVReg == 0) {
- NewVReg = RegInfo.createVirtualRegister(rc);
+ NewVReg = mri_->createVirtualRegister(rc);
vrm.grow();
CreatedNewVReg = true;
}
mop.setReg(NewVReg);
+ if (mop.isImplicit())
+ rewriteImplicitOps(li, MI, NewVReg, vrm);
// Reuse NewVReg for other reads.
- for (unsigned j = 0, e = Ops.size(); j != e; ++j)
- MI->getOperand(Ops[j]).setReg(NewVReg);
+ for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
+ MachineOperand &mopj = MI->getOperand(Ops[j]);
+ mopj.setReg(NewVReg);
+ if (mopj.isImplicit())
+ rewriteImplicitOps(li, MI, NewVReg, vrm);
+ }
if (CreatedNewVReg) {
if (DefIsReMat) {
vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/);
- if (ReMatIds[id] == VirtRegMap::MAX_STACK_SLOT) {
+ if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
// Each valnum may have its own remat id.
- ReMatIds[id] = vrm.assignVirtReMatId(NewVReg);
+ ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
} else {
- vrm.assignVirtReMatId(NewVReg, ReMatIds[id]);
+ vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
}
if (!CanDelete || (HasUse && HasDef)) {
// If this is a two-addr instruction then its use operands are
vrm.assignVirt2StackSlot(NewVReg, Slot);
}
+ // Re-matting an instruction with virtual register use. Add the
+ // register as an implicit use on the use MI.
+ if (DefIsReMat && ImpUse)
+ MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
+
// create a new register interval for this spill / remat.
LiveInterval &nI = getOrCreateInterval(NewVReg);
if (CreatedNewVReg) {
return false;
}
-static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) {
- const VNInfo *VNI = NULL;
- for (LiveInterval::const_vni_iterator i = li.vni_begin(),
- e = li.vni_end(); i != e; ++i)
- if ((*i)->def == DefIdx) {
- VNI = *i;
- break;
+/// RewriteInfo - Keep track of machine instrs that will be rewritten
+/// during spilling.
+namespace {
+ struct RewriteInfo {
+ unsigned Index;
+ MachineInstr *MI;
+ bool HasUse;
+ bool HasDef;
+ RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d)
+ : Index(i), MI(mi), HasUse(u), HasDef(d) {}
+ };
+
+ struct RewriteInfoCompare {
+ bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
+ return LHS.Index < RHS.Index;
}
- return VNI;
+ };
}
void LiveIntervals::
MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
unsigned Slot, int LdSlot,
bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
- VirtRegMap &vrm, MachineRegisterInfo &RegInfo,
+ VirtRegMap &vrm,
const TargetRegisterClass* rc,
SmallVector<int, 4> &ReMatIds,
const MachineLoopInfo *loopInfo,
BitVector &RestoreMBBs,
std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes,
std::map<unsigned,unsigned> &MBBVRegsMap,
- std::vector<LiveInterval*> &NewLIs) {
+ std::vector<LiveInterval*> &NewLIs, float &SSWeight) {
bool AllCanFold = true;
unsigned NewVReg = 0;
- unsigned index = getBaseIndex(I->start);
+ unsigned start = getBaseIndex(I->start);
unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
- for (; index != end; index += InstrSlots::NUM) {
- // skip deleted instructions
- while (index != end && !getInstructionFromIndex(index))
- index += InstrSlots::NUM;
- if (index == end) break;
- MachineInstr *MI = getInstructionFromIndex(index);
+ // First collect all the def / use in this live range that will be rewritten.
+ // Make sure they are sorted according to instruction index.
+ std::vector<RewriteInfo> RewriteMIs;
+ for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
+ re = mri_->reg_end(); ri != re; ) {
+ MachineInstr *MI = &*ri;
+ MachineOperand &O = ri.getOperand();
+ ++ri;
+ assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
+ unsigned index = getInstructionIndex(MI);
+ if (index < start || index >= end)
+ continue;
+ RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef()));
+ }
+ std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
+
+ unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
+ // Now rewrite the defs and uses.
+ for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
+ RewriteInfo &rwi = RewriteMIs[i];
+ ++i;
+ unsigned index = rwi.Index;
+ bool MIHasUse = rwi.HasUse;
+ bool MIHasDef = rwi.HasDef;
+ MachineInstr *MI = rwi.MI;
+ // If MI def and/or use the same register multiple times, then there
+ // are multiple entries.
+ unsigned NumUses = MIHasUse;
+ while (i != e && RewriteMIs[i].MI == MI) {
+ assert(RewriteMIs[i].Index == index);
+ bool isUse = RewriteMIs[i].HasUse;
+ if (isUse) ++NumUses;
+ MIHasUse |= isUse;
+ MIHasDef |= RewriteMIs[i].HasDef;
+ ++i;
+ }
MachineBasicBlock *MBB = MI->getParent();
+
+ if (ImpUse && MI != ReMatDefMI) {
+ // Re-matting an instruction with virtual register use. Update the
+ // register interval's spill weight to HUGE_VALF to prevent it from
+ // being spilled.
+ LiveInterval &ImpLi = getInterval(ImpUse);
+ ImpLi.weight = HUGE_VALF;
+ }
+
+ unsigned MBBId = MBB->getNumber();
unsigned ThisVReg = 0;
if (TrySplit) {
- std::map<unsigned,unsigned>::const_iterator NVI =
- MBBVRegsMap.find(MBB->getNumber());
+ std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId);
if (NVI != MBBVRegsMap.end()) {
ThisVReg = NVI->second;
// One common case:
// = use
// It's better to start a new interval to avoid artifically
// extend the new interval.
- // FIXME: Too slow? Can we fix it after rewriteInstructionsForSpills?
- bool MIHasUse = false;
- bool MIHasDef = false;
- for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
- MachineOperand& mop = MI->getOperand(i);
- if (!mop.isRegister() || mop.getReg() != li.reg)
- continue;
- if (mop.isUse())
- MIHasUse = true;
- else
- MIHasDef = true;
- }
if (MIHasDef && !MIHasUse) {
MBBVRegsMap.erase(MBB->getNumber());
ThisVReg = 0;
bool HasDef = false;
bool HasUse = false;
- bool CanFold = rewriteInstructionForSpills(li, TrySplit, I->valno->id,
- index, end, MI, ReMatOrigDefMI, ReMatDefMI,
- Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
- CanDelete, vrm, RegInfo, rc, ReMatIds, NewVReg,
- HasDef, HasUse, loopInfo, MBBVRegsMap, NewLIs);
+ bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
+ index, end, MI, ReMatOrigDefMI, ReMatDefMI,
+ Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
+ CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
+ ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs, SSWeight);
if (!HasDef && !HasUse)
continue;
}
// Keep track of the last def and first use in each MBB.
- unsigned MBBId = MBB->getNumber();
if (HasDef) {
if (MI != ReMatOrigDefMI || !CanDelete) {
bool HasKill = false;
HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
else {
// If this is a two-address code, then this index starts a new VNInfo.
- const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index));
+ const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index));
if (VNI)
HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
}
Restores[i].index = -1;
}
+/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
+/// spilled and create empty intervals for their uses.
+void
+LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
+ const TargetRegisterClass* rc,
+ std::vector<LiveInterval*> &NewLIs) {
+ for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
+ re = mri_->reg_end(); ri != re; ) {
+ MachineOperand &O = ri.getOperand();
+ MachineInstr *MI = &*ri;
+ ++ri;
+ if (O.isDef()) {
+ assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF &&
+ "Register def was not rewritten?");
+ RemoveMachineInstrFromMaps(MI);
+ vrm.RemoveMachineInstrFromMaps(MI);
+ MI->eraseFromParent();
+ } else {
+ // This must be an use of an implicit_def so it's not part of the live
+ // interval. Create a new empty live interval for it.
+ // FIXME: Can we simply erase some of the instructions? e.g. Stores?
+ unsigned NewVReg = mri_->createVirtualRegister(rc);
+ vrm.grow();
+ vrm.setIsImplicitlyDefined(NewVReg);
+ NewLIs.push_back(&getOrCreateInterval(NewVReg));
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ MachineOperand &MO = MI->getOperand(i);
+ if (MO.isReg() && MO.getReg() == li.reg)
+ MO.setReg(NewVReg);
+ }
+ }
+ }
+}
+
std::vector<LiveInterval*> LiveIntervals::
addIntervalsForSpills(const LiveInterval &li,
- const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
+ const MachineLoopInfo *loopInfo, VirtRegMap &vrm,
+ float &SSWeight) {
// Since this is called after the analysis is done we don't know if
// LiveVariables is available
lv_ = getAnalysisToUpdate<LiveVariables>();
li.print(DOUT, tri_);
DOUT << '\n';
+ // Spill slot weight.
+ SSWeight = 0.0f;
+
// Each bit specify whether it a spill is required in the MBB.
BitVector SpillMBBs(mf_->getNumBlockIDs());
std::map<unsigned, std::vector<SRInfo> > SpillIdxes;
std::map<unsigned, std::vector<SRInfo> > RestoreIdxes;
std::map<unsigned,unsigned> MBBVRegsMap;
std::vector<LiveInterval*> NewLIs;
- MachineRegisterInfo &RegInfo = mf_->getRegInfo();
- const TargetRegisterClass* rc = RegInfo.getRegClass(li.reg);
+ const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
unsigned NumValNums = li.getNumValNums();
SmallVector<MachineInstr*, 4> ReMatDefs;
// Note ReMatOrigDefMI has already been deleted.
rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
- false, vrm, RegInfo, rc, ReMatIds, loopInfo,
+ false, vrm, rc, ReMatIds, loopInfo,
SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
- MBBVRegsMap, NewLIs);
+ MBBVRegsMap, NewLIs, SSWeight);
} else {
rewriteInstructionsForSpills(li, false, I, NULL, 0,
Slot, 0, false, false, false,
- false, vrm, RegInfo, rc, ReMatIds, loopInfo,
+ false, vrm, rc, ReMatIds, loopInfo,
SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
- MBBVRegsMap, NewLIs);
+ MBBVRegsMap, NewLIs, SSWeight);
}
IsFirstRange = false;
}
+
+ SSWeight = 0.0f; // Already accounted for when split.
+ handleSpilledImpDefs(li, vrm, rc, NewLIs);
return NewLIs;
}
(DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad());
rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
- CanDelete, vrm, RegInfo, rc, ReMatIds, loopInfo,
+ CanDelete, vrm, rc, ReMatIds, loopInfo,
SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
- MBBVRegsMap, NewLIs);
+ MBBVRegsMap, NewLIs, SSWeight);
}
// Insert spills / restores if we are splitting.
- if (!TrySplit)
+ if (!TrySplit) {
+ handleSpilledImpDefs(li, vrm, rc, NewLIs);
return NewLIs;
+ }
SmallPtrSet<LiveInterval*, 4> AddedKill;
SmallVector<unsigned, 2> Ops;
if (NeedStackSlot) {
int Id = SpillMBBs.find_first();
while (Id != -1) {
+ MachineBasicBlock *MBB = mf_->getBlockNumbered(Id);
+ unsigned loopDepth = loopInfo->getLoopDepth(MBB);
std::vector<SRInfo> &spills = SpillIdxes[Id];
for (unsigned i = 0, e = spills.size(); i != e; ++i) {
int index = spills[i].index;
}
}
- // Else tell the spiller to issue a spill.
+ // Otherwise tell the spiller to issue a spill.
if (!Folded) {
LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
bool isKill = LR->end == getStoreIndex(index);
- vrm.addSpillPoint(VReg, isKill, MI);
+ if (!MI->registerDefIsDead(nI.reg))
+ // No need to spill a dead def.
+ vrm.addSpillPoint(VReg, isKill, MI);
if (isKill)
AddedKill.insert(&nI);
}
+
+ // Update spill slot weight.
+ if (!isReMat)
+ SSWeight += getSpillWeight(true, false, loopDepth);
}
Id = SpillMBBs.find_next(Id);
}
int Id = RestoreMBBs.find_first();
while (Id != -1) {
+ MachineBasicBlock *MBB = mf_->getBlockNumbered(Id);
+ unsigned loopDepth = loopInfo->getLoopDepth(MBB);
+
std::vector<SRInfo> &restores = RestoreIdxes[Id];
for (unsigned i = 0, e = restores.size(); i != e; ++i) {
int index = restores[i].index;
continue;
unsigned VReg = restores[i].vreg;
LiveInterval &nI = getOrCreateInterval(VReg);
+ bool isReMat = vrm.isReMaterialized(VReg);
MachineInstr *MI = getInstructionFromIndex(index);
bool CanFold = false;
Ops.clear();
// Fold the load into the use if possible.
bool Folded = false;
if (CanFold && !Ops.empty()) {
- if (!vrm.isReMaterialized(VReg))
+ if (!isReMat)
Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
else {
MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad())
Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
Ops, isLoadSS, LdSlot, VReg);
+ unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
+ if (ImpUse) {
+ // Re-matting an instruction with virtual register use. Add the
+ // register as an implicit use on the use MI and update the register
+ // interval's spill weight to HUGE_VALF to prevent it from being
+ // spilled.
+ LiveInterval &ImpLi = getInterval(ImpUse);
+ ImpLi.weight = HUGE_VALF;
+ MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
+ }
}
}
// If folding is not possible / failed, then tell the spiller to issue a
nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
else
vrm.addRestorePoint(VReg, MI);
+
+ // Update spill slot weight.
+ if (!isReMat)
+ SSWeight += getSpillWeight(false, true, loopDepth);
}
Id = RestoreMBBs.find_next(Id);
}
LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
unsigned LastUseIdx = getBaseIndex(LR->end);
MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
- int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg);
+ int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
assert(UseIdx != -1);
- if (LastUse->getDesc().getOperandConstraint(UseIdx, TOI::TIED_TO) ==
- -1) {
+ if (LastUse->getOperand(UseIdx).isImplicit() ||
+ LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){
LastUse->getOperand(UseIdx).setIsKill();
vrm.addKillPoint(LI->reg, LastUseIdx);
}
}
}
+ handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
return RetNewLIs;
}
+
+/// hasAllocatableSuperReg - Return true if the specified physical register has
+/// any super register that's allocatable.
+bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
+ for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
+ if (allocatableRegs_[*AS] && hasInterval(*AS))
+ return true;
+ return false;
+}
+
+/// getRepresentativeReg - Find the largest super register of the specified
+/// physical register.
+unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
+ // Find the largest super-register that is allocatable.
+ unsigned BestReg = Reg;
+ for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
+ unsigned SuperReg = *AS;
+ if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
+ BestReg = SuperReg;
+ break;
+ }
+ }
+ return BestReg;
+}
+
+/// getNumConflictsWithPhysReg - Return the number of uses and defs of the
+/// specified interval that conflicts with the specified physical register.
+unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
+ unsigned PhysReg) const {
+ unsigned NumConflicts = 0;
+ const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
+ for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
+ E = mri_->reg_end(); I != E; ++I) {
+ MachineOperand &O = I.getOperand();
+ MachineInstr *MI = O.getParent();
+ unsigned Index = getInstructionIndex(MI);
+ if (pli.liveAt(Index))
+ ++NumConflicts;
+ }
+ return NumConflicts;
+}
+
+/// spillPhysRegAroundRegDefsUses - Spill the specified physical register
+/// around all defs and uses of the specified interval.
+void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
+ unsigned PhysReg, VirtRegMap &vrm) {
+ unsigned SpillReg = getRepresentativeReg(PhysReg);
+
+ for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
+ // If there are registers which alias PhysReg, but which are not a
+ // sub-register of the chosen representative super register. Assert
+ // since we can't handle it yet.
+ assert(*AS == SpillReg || !allocatableRegs_[*AS] ||
+ tri_->isSuperRegister(*AS, SpillReg));
+
+ LiveInterval &pli = getInterval(SpillReg);
+ SmallPtrSet<MachineInstr*, 8> SeenMIs;
+ for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
+ E = mri_->reg_end(); I != E; ++I) {
+ MachineOperand &O = I.getOperand();
+ MachineInstr *MI = O.getParent();
+ if (SeenMIs.count(MI))
+ continue;
+ SeenMIs.insert(MI);
+ unsigned Index = getInstructionIndex(MI);
+ if (pli.liveAt(Index)) {
+ vrm.addEmergencySpill(SpillReg, MI);
+ pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
+ for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) {
+ if (!hasInterval(*AS))
+ continue;
+ LiveInterval &spli = getInterval(*AS);
+ if (spli.liveAt(Index))
+ spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
+ }
+ }
+ }
+}
+
+LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
+ MachineInstr* startInst) {
+ LiveInterval& Interval = getOrCreateInterval(reg);
+ VNInfo* VN = Interval.getNextValue(
+ getInstructionIndex(startInst) + InstrSlots::DEF,
+ startInst, getVNInfoAllocator());
+ VN->hasPHIKill = true;
+ VN->kills.push_back(getMBBEndIdx(startInst->getParent()));
+ LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF,
+ getMBBEndIdx(startInst->getParent()) + 1, VN);
+ Interval.addRange(LR);
+
+ return LR;
+}