//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "regalloc"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "LiveRangeCalc.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveVariables.h"
+#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/VirtRegMap.h"
#include "llvm/IR/Value.h"
+#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.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/TargetRegisterInfo.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
#include <algorithm>
#include <cmath>
#include <limits>
using namespace llvm;
+#define DEBUG_TYPE "regalloc"
+
char LiveIntervals::ID = 0;
char &llvm::LiveIntervalsID = LiveIntervals::ID;
INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
"Live Interval Analysis", false, false)
+#ifndef NDEBUG
+static cl::opt<bool> EnablePrecomputePhysRegs(
+ "precompute-phys-liveness", cl::Hidden,
+ cl::desc("Eagerly compute live intervals for all physreg units."));
+#else
+static bool EnablePrecomputePhysRegs = false;
+#endif // NDEBUG
+
void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<AliasAnalysis>();
}
LiveIntervals::LiveIntervals() : MachineFunctionPass(ID),
- DomTree(0), LRCalc(0) {
+ DomTree(nullptr), LRCalc(nullptr) {
initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
}
RegMaskBits.clear();
RegMaskBlocks.clear();
- for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
- delete RegUnitIntervals[i];
- RegUnitIntervals.clear();
+ for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i)
+ delete RegUnitRanges[i];
+ RegUnitRanges.clear();
// Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
VNInfoAllocator.Reset();
}
-/// runOnMachineFunction - Register allocate the whole function
+/// runOnMachineFunction - calculates LiveIntervals
///
bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
MF = &fn;
MRI = &MF->getRegInfo();
- TM = &fn.getTarget();
- TRI = TM->getRegisterInfo();
- TII = TM->getInstrInfo();
+ TRI = MF->getSubtarget().getRegisterInfo();
+ TII = MF->getSubtarget().getInstrInfo();
AA = &getAnalysis<AliasAnalysis>();
Indexes = &getAnalysis<SlotIndexes>();
DomTree = &getAnalysis<MachineDominatorTree>();
computeRegMasks();
computeLiveInRegUnits();
+ if (EnablePrecomputePhysRegs) {
+ // For stress testing, precompute live ranges of all physical register
+ // units, including reserved registers.
+ for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
+ getRegUnit(i);
+ }
DEBUG(dump());
return true;
}
OS << "********** INTERVALS **********\n";
// Dump the regunits.
- for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
- if (LiveInterval *LI = RegUnitIntervals[i])
- OS << PrintRegUnit(i, TRI) << " = " << *LI << '\n';
+ for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i)
+ if (LiveRange *LR = RegUnitRanges[i])
+ OS << PrintRegUnit(i, TRI) << ' ' << *LR << '\n';
// Dump the virtregs.
for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
if (hasInterval(Reg))
- OS << PrintReg(Reg) << " = " << getInterval(Reg) << '\n';
+ OS << getInterval(Reg) << '\n';
}
OS << "RegMasks:";
#endif
LiveInterval* LiveIntervals::createInterval(unsigned reg) {
- float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
+ float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ?
+ llvm::huge_valf : 0.0F;
return new LiveInterval(reg, Weight);
}
/// computeVirtRegInterval - Compute the live interval of a virtual register,
/// based on defs and uses.
-void LiveIntervals::computeVirtRegInterval(LiveInterval *LI) {
+void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
assert(LRCalc && "LRCalc not initialized.");
- assert(LI->empty() && "Should only compute empty intervals.");
+ assert(LI.empty() && "Should only compute empty intervals.");
LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
LRCalc->createDeadDefs(LI);
LRCalc->extendToUses(LI);
+ computeDeadValues(LI, LI);
}
void LiveIntervals::computeVirtRegs() {
unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
if (MRI->reg_nodbg_empty(Reg))
continue;
- LiveInterval *LI = createInterval(Reg);
- VirtRegIntervals[Reg] = LI;
- computeVirtRegInterval(LI);
+ createAndComputeVirtRegInterval(Reg);
}
}
// interference.
//
-/// computeRegUnitInterval - Compute the live interval of a register unit, based
-/// on the uses and defs of aliasing registers. The interval should be empty,
+/// computeRegUnitInterval - Compute the live range of a register unit, based
+/// on the uses and defs of aliasing registers. The range should be empty,
/// or contain only dead phi-defs from ABI blocks.
-void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) {
- unsigned Unit = LI->reg;
-
+void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {
assert(LRCalc && "LRCalc not initialized.");
LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
// idempotent. It is very rare for a register unit to have multiple roots, so
// uniquing super-registers is probably not worthwhile.
for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
- unsigned Root = *Roots;
- if (!MRI->reg_empty(Root))
- LRCalc->createDeadDefs(LI, Root);
- for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) {
+ for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
+ Supers.isValid(); ++Supers) {
if (!MRI->reg_empty(*Supers))
- LRCalc->createDeadDefs(LI, *Supers);
+ LRCalc->createDeadDefs(LR, *Supers);
}
}
- // Now extend LI to reach all uses.
+ // Now extend LR to reach all uses.
// Ignore uses of reserved registers. We only track defs of those.
for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
- unsigned Root = *Roots;
- if (!MRI->isReserved(Root) && !MRI->reg_empty(Root))
- LRCalc->extendToUses(LI, Root);
- for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) {
+ for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
+ Supers.isValid(); ++Supers) {
unsigned Reg = *Supers;
if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg))
- LRCalc->extendToUses(LI, Reg);
+ LRCalc->extendToUses(LR, Reg);
}
}
}
/// without a corresponding def when entering the entry block or a landing pad.
///
void LiveIntervals::computeLiveInRegUnits() {
- RegUnitIntervals.resize(TRI->getNumRegUnits());
+ RegUnitRanges.resize(TRI->getNumRegUnits());
DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
- // Keep track of the intervals allocated.
- SmallVector<LiveInterval*, 8> NewIntvs;
+ // Keep track of the live range sets allocated.
+ SmallVector<unsigned, 8> NewRanges;
// Check all basic blocks for live-ins.
for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
LIE = MBB->livein_end(); LII != LIE; ++LII) {
for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) {
unsigned Unit = *Units;
- LiveInterval *Intv = RegUnitIntervals[Unit];
- if (!Intv) {
- Intv = RegUnitIntervals[Unit] = new LiveInterval(Unit, HUGE_VALF);
- NewIntvs.push_back(Intv);
+ LiveRange *LR = RegUnitRanges[Unit];
+ if (!LR) {
+ LR = RegUnitRanges[Unit] = new LiveRange();
+ NewRanges.push_back(Unit);
}
- VNInfo *VNI = Intv->createDeadDef(Begin, getVNInfoAllocator());
+ VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
(void)VNI;
DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id);
}
}
DEBUG(dbgs() << '\n');
}
- DEBUG(dbgs() << "Created " << NewIntvs.size() << " new intervals.\n");
+ DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
- // Compute the 'normal' part of the intervals.
- for (unsigned i = 0, e = NewIntvs.size(); i != e; ++i)
- computeRegUnitInterval(NewIntvs[i]);
+ // Compute the 'normal' part of the ranges.
+ for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) {
+ unsigned Unit = NewRanges[i];
+ computeRegUnitRange(*RegUnitRanges[Unit], Unit);
+ }
}
-/// shrinkToUses - After removing some uses of a register, shrink its live
-/// range to just the remaining uses. This method does not compute reaching
-/// defs for new uses, and it doesn't remove dead defs.
-bool LiveIntervals::shrinkToUses(LiveInterval *li,
- SmallVectorImpl<MachineInstr*> *dead) {
- DEBUG(dbgs() << "Shrink: " << *li << '\n');
- assert(TargetRegisterInfo::isVirtualRegister(li->reg)
- && "Can only shrink virtual registers");
- // Find all the values used, including PHI kills.
- SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
-
- // Blocks that have already been added to WorkList as live-out.
- SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
-
- // Visit all instructions reading li->reg.
- for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(li->reg);
- MachineInstr *UseMI = I.skipInstruction();) {
- if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
- continue;
- SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
- LiveRangeQuery LRQ(*li, Idx);
- VNInfo *VNI = LRQ.valueIn();
- if (!VNI) {
- // This shouldn't happen: readsVirtualRegister returns true, but there is
- // no live value. It is likely caused by a target getting <undef> flags
- // wrong.
- DEBUG(dbgs() << Idx << '\t' << *UseMI
- << "Warning: Instr claims to read non-existent value in "
- << *li << '\n');
- continue;
- }
- // Special case: An early-clobber tied operand reads and writes the
- // register one slot early.
- if (VNInfo *DefVNI = LRQ.valueDefined())
- Idx = DefVNI->def;
-
- WorkList.push_back(std::make_pair(Idx, VNI));
- }
-
- // Create a new live interval with only minimal live segments per def.
- LiveInterval NewLI(li->reg, 0);
- for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
- I != E; ++I) {
- VNInfo *VNI = *I;
+static void createSegmentsForValues(LiveRange &LR,
+ iterator_range<LiveInterval::vni_iterator> VNIs) {
+ for (auto VNI : VNIs) {
if (VNI->isUnused())
continue;
- NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI));
+ SlotIndex Def = VNI->def;
+ LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
}
+}
+
+typedef SmallVector<std::pair<SlotIndex, VNInfo*>, 16> ShrinkToUsesWorkList;
+static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
+ ShrinkToUsesWorkList &WorkList,
+ const LiveRange &OldRange) {
// Keep track of the PHIs that are in use.
SmallPtrSet<VNInfo*, 8> UsedPHIs;
+ // Blocks that have already been added to WorkList as live-out.
+ SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
// Extend intervals to reach all uses in WorkList.
while (!WorkList.empty()) {
SlotIndex Idx = WorkList.back().first;
VNInfo *VNI = WorkList.back().second;
WorkList.pop_back();
- const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot());
- SlotIndex BlockStart = getMBBStartIdx(MBB);
+ const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot());
+ SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB);
// Extend the live range for VNI to be live at Idx.
- if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) {
- (void)ExtVNI;
+ if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) {
assert(ExtVNI == VNI && "Unexpected existing value number");
+ (void)ExtVNI;
// Is this a PHIDef we haven't seen before?
- if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
+ if (!VNI->isPHIDef() || VNI->def != BlockStart ||
+ !UsedPHIs.insert(VNI).second)
continue;
// The PHI is live, make sure the predecessors are live-out.
- for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
- PE = MBB->pred_end(); PI != PE; ++PI) {
- if (!LiveOut.insert(*PI))
+ for (auto &Pred : MBB->predecessors()) {
+ if (!LiveOut.insert(Pred).second)
continue;
- SlotIndex Stop = getMBBEndIdx(*PI);
+ SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
// A predecessor is not required to have a live-out value for a PHI.
- if (VNInfo *PVNI = li->getVNInfoBefore(Stop))
+ if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
WorkList.push_back(std::make_pair(Stop, PVNI));
}
continue;
// VNI is live-in to MBB.
DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
- NewLI.addRange(LiveRange(BlockStart, Idx, VNI));
+ LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
// Make sure VNI is live-out from the predecessors.
- for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
- PE = MBB->pred_end(); PI != PE; ++PI) {
- if (!LiveOut.insert(*PI))
+ for (auto &Pred : MBB->predecessors()) {
+ if (!LiveOut.insert(Pred).second)
continue;
- SlotIndex Stop = getMBBEndIdx(*PI);
- assert(li->getVNInfoBefore(Stop) == VNI &&
+ SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
+ assert(OldRange.getVNInfoBefore(Stop) == VNI &&
"Wrong value out of predecessor");
WorkList.push_back(std::make_pair(Stop, VNI));
}
}
+}
+
+/// shrinkToUses - After removing some uses of a register, shrink its live
+/// range to just the remaining uses. This method does not compute reaching
+/// defs for new uses, and it doesn't remove dead defs.
+bool LiveIntervals::shrinkToUses(LiveInterval *li,
+ SmallVectorImpl<MachineInstr*> *dead) {
+ DEBUG(dbgs() << "Shrink: " << *li << '\n');
+ assert(TargetRegisterInfo::isVirtualRegister(li->reg)
+ && "Can only shrink virtual registers");
+
+ // Shrink subregister live ranges.
+ for (LiveInterval::subrange_iterator I = li->subrange_begin(),
+ E = li->subrange_end(); I != E; ++I) {
+ shrinkToUses(*I, li->reg);
+ }
+
+ // Find all the values used, including PHI kills.
+ ShrinkToUsesWorkList WorkList;
+
+ // Visit all instructions reading li->reg.
+ for (MachineRegisterInfo::reg_instr_iterator
+ I = MRI->reg_instr_begin(li->reg), E = MRI->reg_instr_end();
+ I != E; ) {
+ MachineInstr *UseMI = &*(I++);
+ if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
+ continue;
+ SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
+ LiveQueryResult LRQ = li->Query(Idx);
+ VNInfo *VNI = LRQ.valueIn();
+ if (!VNI) {
+ // This shouldn't happen: readsVirtualRegister returns true, but there is
+ // no live value. It is likely caused by a target getting <undef> flags
+ // wrong.
+ DEBUG(dbgs() << Idx << '\t' << *UseMI
+ << "Warning: Instr claims to read non-existent value in "
+ << *li << '\n');
+ continue;
+ }
+ // Special case: An early-clobber tied operand reads and writes the
+ // register one slot early.
+ if (VNInfo *DefVNI = LRQ.valueDefined())
+ Idx = DefVNI->def;
+
+ WorkList.push_back(std::make_pair(Idx, VNI));
+ }
+
+ // Create new live ranges with only minimal live segments per def.
+ LiveRange NewLR;
+ createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end()));
+ extendSegmentsToUses(NewLR, *Indexes, WorkList, *li);
// Handle dead values.
+ bool CanSeparate;
+ computeDeadValues(NewLR, *li, &CanSeparate, li->reg, dead);
+
+ // Move the trimmed segments back.
+ li->segments.swap(NewLR.segments);
+ DEBUG(dbgs() << "Shrunk: " << *li << '\n');
+ return CanSeparate;
+}
+
+void LiveIntervals::computeDeadValues(LiveRange &Segments, LiveRange &LR,
+ bool *CanSeparateRes, unsigned Reg,
+ SmallVectorImpl<MachineInstr*> *dead) {
bool CanSeparate = false;
- for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
- I != E; ++I) {
- VNInfo *VNI = *I;
+ for (auto VNI : make_range(LR.vni_begin(), LR.vni_end())) {
if (VNI->isUnused())
continue;
- LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
- assert(LII != NewLI.end() && "Missing live range for PHI");
- if (LII->end != VNI->def.getDeadSlot())
+ LiveRange::iterator LRI = Segments.FindSegmentContaining(VNI->def);
+ assert(LRI != Segments.end() && "Missing segment for PHI");
+ if (LRI->end != VNI->def.getDeadSlot())
continue;
if (VNI->isPHIDef()) {
// This is a dead PHI. Remove it.
VNI->markUnused();
- NewLI.removeRange(*LII);
+ Segments.removeSegment(LRI->start, LRI->end);
DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
CanSeparate = true;
- } else {
+ } else if (dead != nullptr) {
// This is a dead def. Make sure the instruction knows.
MachineInstr *MI = getInstructionFromIndex(VNI->def);
assert(MI && "No instruction defining live value");
- MI->addRegisterDead(li->reg, TRI);
+ MI->addRegisterDead(Reg, TRI);
if (dead && MI->allDefsAreDead()) {
DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
dead->push_back(MI);
}
}
}
+ if (CanSeparateRes != nullptr)
+ *CanSeparateRes = CanSeparate;
+}
+
+bool LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg)
+{
+ DEBUG(dbgs() << "Shrink: " << SR << '\n');
+ assert(TargetRegisterInfo::isVirtualRegister(Reg)
+ && "Can only shrink virtual registers");
+ // Find all the values used, including PHI kills.
+ ShrinkToUsesWorkList WorkList;
+
+ // Visit all instructions reading Reg.
+ SlotIndex LastIdx;
+ for (MachineOperand &MO : MRI->reg_operands(Reg)) {
+ MachineInstr *UseMI = MO.getParent();
+ if (UseMI->isDebugValue())
+ continue;
+ // Maybe the operand is for a subregister we don't care about.
+ unsigned SubReg = MO.getSubReg();
+ if (SubReg != 0) {
+ unsigned SubRegMask = TRI->getSubRegIndexLaneMask(SubReg);
+ if ((SubRegMask & SR.LaneMask) == 0)
+ continue;
+ }
+ // We only need to visit each instruction once.
+ SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
+ if (Idx == LastIdx)
+ continue;
+ LastIdx = Idx;
+
+ LiveQueryResult LRQ = SR.Query(Idx);
+ VNInfo *VNI = LRQ.valueIn();
+ // For Subranges it is possible that only undef values are left in that
+ // part of the subregister, so there is no real liverange at the use
+ if (!VNI)
+ continue;
+
+ // Special case: An early-clobber tied operand reads and writes the
+ // register one slot early.
+ if (VNInfo *DefVNI = LRQ.valueDefined())
+ Idx = DefVNI->def;
+
+ WorkList.push_back(std::make_pair(Idx, VNI));
+ }
+
+ // Create a new live ranges with only minimal live segments per def.
+ LiveRange NewLR;
+ createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end()));
+ extendSegmentsToUses(NewLR, *Indexes, WorkList, SR);
+
+ // Handle dead values.
+ bool CanSeparate;
+ computeDeadValues(NewLR, SR, &CanSeparate);
// Move the trimmed ranges back.
- li->ranges.swap(NewLI.ranges);
- DEBUG(dbgs() << "Shrunk: " << *li << '\n');
+ SR.segments.swap(NewLR.segments);
+ DEBUG(dbgs() << "Shrunk: " << SR << '\n');
return CanSeparate;
}
-void LiveIntervals::extendToIndices(LiveInterval *LI,
+void LiveIntervals::extendToIndices(LiveRange &LR,
ArrayRef<SlotIndex> Indices) {
assert(LRCalc && "LRCalc not initialized.");
LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
for (unsigned i = 0, e = Indices.size(); i != e; ++i)
- LRCalc->extend(LI, Indices[i]);
+ LRCalc->extend(LR, Indices[i]);
}
void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill,
SmallVectorImpl<SlotIndex> *EndPoints) {
- LiveRangeQuery LRQ(*LI, Kill);
+ LiveQueryResult LRQ = LI->Query(Kill);
VNInfo *VNI = LRQ.valueOut();
if (!VNI)
return;
MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);
SlotIndex MBBStart, MBBEnd;
- tie(MBBStart, MBBEnd) = Indexes->getMBBRange(KillMBB);
+ std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(KillMBB);
// If VNI isn't live out from KillMBB, the value is trivially pruned.
if (LRQ.endPoint() < MBBEnd) {
- LI->removeRange(Kill, LRQ.endPoint());
+ LI->removeSegment(Kill, LRQ.endPoint());
if (EndPoints) EndPoints->push_back(LRQ.endPoint());
return;
}
// VNI is live out of KillMBB.
- LI->removeRange(Kill, MBBEnd);
+ LI->removeSegment(Kill, MBBEnd);
if (EndPoints) EndPoints->push_back(MBBEnd);
// Find all blocks that are reachable from KillMBB without leaving VNI's live
MachineBasicBlock *MBB = *I;
// Check if VNI is live in to MBB.
- tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
- LiveRangeQuery LRQ(*LI, MBBStart);
+ std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
+ LiveQueryResult LRQ = LI->Query(MBBStart);
if (LRQ.valueIn() != VNI) {
- // This block isn't part of the VNI live range. Prune the search.
+ // This block isn't part of the VNI segment. Prune the search.
I.skipChildren();
continue;
}
// Prune the search if VNI is killed in MBB.
if (LRQ.endPoint() < MBBEnd) {
- LI->removeRange(MBBStart, LRQ.endPoint());
+ LI->removeSegment(MBBStart, LRQ.endPoint());
if (EndPoints) EndPoints->push_back(LRQ.endPoint());
I.skipChildren();
continue;
}
// VNI is live through MBB.
- LI->removeRange(MBBStart, MBBEnd);
+ LI->removeSegment(MBBStart, MBBEnd);
if (EndPoints) EndPoints->push_back(MBBEnd);
++I;
}
void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {
// Keep track of regunit ranges.
- SmallVector<std::pair<LiveInterval*, LiveInterval::iterator>, 8> RU;
+ SmallVector<std::pair<LiveRange*, LiveRange::iterator>, 8> RU;
for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
RU.clear();
for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid();
++Units) {
- LiveInterval *RUInt = &getRegUnit(*Units);
- if (RUInt->empty())
+ LiveRange &RURanges = getRegUnit(*Units);
+ if (RURanges.empty())
continue;
- RU.push_back(std::make_pair(RUInt, RUInt->find(LI->begin()->end)));
+ RU.push_back(std::make_pair(&RURanges, RURanges.find(LI->begin()->end)));
}
- // Every instruction that kills Reg corresponds to a live range end point.
+ // Every instruction that kills Reg corresponds to a segment range end
+ // point.
for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
++RI) {
// A block index indicates an MBB edge.
if (!MI)
continue;
- // Check if any of the reguints are live beyond the end of RI. That could
+ // Check if any of the regunits are live beyond the end of RI. That could
// happen when a physreg is defined as a copy of a virtreg:
//
// %EAX = COPY %vreg5
// There should be no kill flag on FOO when %vreg5 is rewritten as %EAX.
bool CancelKill = false;
for (unsigned u = 0, e = RU.size(); u != e; ++u) {
- LiveInterval *RInt = RU[u].first;
- LiveInterval::iterator &I = RU[u].second;
- if (I == RInt->end())
+ LiveRange &RRanges = *RU[u].first;
+ LiveRange::iterator &I = RU[u].second;
+ if (I == RRanges.end())
continue;
- I = RInt->advanceTo(I, RI->end);
- if (I == RInt->end() || I->start >= RI->end)
+ I = RRanges.advanceTo(I, RI->end);
+ if (I == RRanges.end() || I->start >= RI->end)
continue;
// I is overlapping RI.
CancelKill = true;
break;
}
if (CancelKill)
- MI->clearRegisterKills(Reg, NULL);
+ MI->clearRegisterKills(Reg, nullptr);
else
- MI->addRegisterKilled(Reg, NULL);
+ MI->addRegisterKilled(Reg, nullptr);
}
}
}
SlotIndex Start = LI.beginIndex();
if (Start.isBlock())
- return NULL;
+ return nullptr;
SlotIndex Stop = LI.endIndex();
if (Stop.isBlock())
- return NULL;
+ return nullptr;
// getMBBFromIndex doesn't need to search the MBB table when both indexes
// belong to proper instructions.
MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
- return MBB1 == MBB2 ? MBB1 : NULL;
+ return MBB1 == MBB2 ? MBB1 : nullptr;
}
bool
}
float
-LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
- // Limit the loop depth ridiculousness.
- if (loopDepth > 200)
- loopDepth = 200;
-
- // The loop depth is used to roughly estimate the number of times the
- // instruction is executed. Something like 10^d is simple, but will quickly
- // overflow a float. This expression behaves like 10^d for small d, but is
- // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
- // headroom before overflow.
- // By the way, powf() might be unavailable here. For consistency,
- // We may take pow(double,double).
- float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth);
-
- return (isDef + isUse) * lc;
+LiveIntervals::getSpillWeight(bool isDef, bool isUse,
+ const MachineBlockFrequencyInfo *MBFI,
+ const MachineInstr *MI) {
+ BlockFrequency Freq = MBFI->getBlockFreq(MI->getParent());
+ const float Scale = 1.0f / MBFI->getEntryFreq();
+ return (isDef + isUse) * (Freq.getFrequency() * Scale);
}
-LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
- MachineInstr* startInst) {
- LiveInterval& Interval = getOrCreateInterval(reg);
+LiveRange::Segment
+LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr* startInst) {
+ LiveInterval& Interval = createEmptyInterval(reg);
VNInfo* VN = Interval.getNextValue(
SlotIndex(getInstructionIndex(startInst).getRegSlot()),
getVNInfoAllocator());
- LiveRange LR(
+ LiveRange::Segment S(
SlotIndex(getInstructionIndex(startInst).getRegSlot()),
getMBBEndIdx(startInst->getParent()), VN);
- Interval.addRange(LR);
+ Interval.addSegment(S);
- return LR;
+ return S;
}
const TargetRegisterInfo& TRI;
SlotIndex OldIdx;
SlotIndex NewIdx;
- SmallPtrSet<LiveInterval*, 8> Updated;
+ SmallPtrSet<LiveRange*, 8> Updated;
bool UpdateFlags;
public:
// physregs, even those that aren't needed for regalloc, in order to update
// kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
// flags, and postRA passes will use a live register utility instead.
- LiveInterval *getRegUnitLI(unsigned Unit) {
+ LiveRange *getRegUnitLI(unsigned Unit) {
if (UpdateFlags)
return &LIS.getRegUnit(Unit);
return LIS.getCachedRegUnit(Unit);
if (!Reg)
continue;
if (TargetRegisterInfo::isVirtualRegister(Reg)) {
- updateRange(LIS.getInterval(Reg));
+ LiveInterval &LI = LIS.getInterval(Reg);
+ // TODO: handle subranges instead of dropping them
+ LI.clearSubRanges();
+ updateRange(LI, Reg);
continue;
}
// For physregs, only update the regunits that actually have a
// precomputed live range.
for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
- if (LiveInterval *LI = getRegUnitLI(*Units))
- updateRange(*LI);
+ if (LiveRange *LR = getRegUnitLI(*Units))
+ updateRange(*LR, *Units);
}
if (hasRegMask)
updateRegMaskSlots();
private:
/// Update a single live range, assuming an instruction has been moved from
/// OldIdx to NewIdx.
- void updateRange(LiveInterval &LI) {
- if (!Updated.insert(&LI))
+ void updateRange(LiveRange &LR, unsigned Reg) {
+ if (!Updated.insert(&LR).second)
return;
DEBUG({
dbgs() << " ";
- if (TargetRegisterInfo::isVirtualRegister(LI.reg))
- dbgs() << PrintReg(LI.reg);
+ if (TargetRegisterInfo::isVirtualRegister(Reg))
+ dbgs() << PrintReg(Reg);
else
- dbgs() << PrintRegUnit(LI.reg, &TRI);
- dbgs() << ":\t" << LI << '\n';
+ dbgs() << PrintRegUnit(Reg, &TRI);
+ dbgs() << ":\t" << LR << '\n';
});
if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))
- handleMoveDown(LI);
+ handleMoveDown(LR);
else
- handleMoveUp(LI);
- DEBUG(dbgs() << " -->\t" << LI << '\n');
- LI.verify();
+ handleMoveUp(LR, Reg);
+ DEBUG(dbgs() << " -->\t" << LR << '\n');
+ LR.verify();
}
- /// Update LI to reflect an instruction has been moved downwards from OldIdx
+ /// Update LR to reflect an instruction has been moved downwards from OldIdx
/// to NewIdx.
///
/// 1. Live def at OldIdx:
/// Move def to NewIdx, possibly across another live value.
///
/// 4. Def at OldIdx AND at NewIdx:
- /// Remove live range [OldIdx;NewIdx) and value defined at OldIdx.
+ /// Remove segment [OldIdx;NewIdx) and value defined at OldIdx.
/// (Happens when bundling multiple defs together).
///
/// 5. Value read at OldIdx, killed before NewIdx:
/// Extend kill to NewIdx.
///
- void handleMoveDown(LiveInterval &LI) {
+ void handleMoveDown(LiveRange &LR) {
// First look for a kill at OldIdx.
- LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex());
- LiveInterval::iterator E = LI.end();
- // Is LI even live at OldIdx?
+ LiveRange::iterator I = LR.find(OldIdx.getBaseIndex());
+ LiveRange::iterator E = LR.end();
+ // Is LR even live at OldIdx?
if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start))
return;
for (MIBundleOperands MO(KillMI); MO.isValid(); ++MO)
if (MO->isReg() && MO->isUse())
MO->setIsKill(false);
- // Adjust I->end to reach NewIdx. This may temporarily make LI invalid by
+ // Adjust I->end to reach NewIdx. This may temporarily make LR invalid by
// overlapping ranges. Case 5 above.
I->end = NewIdx.getRegSlot(I->end.isEarlyClobber());
// If this was a kill, there may also be a def. Otherwise we're done.
assert((I->end == OldIdx.getDeadSlot() ||
SlotIndex::isSameInstr(I->end, NewIdx)) &&
"Cannot move def below kill");
- LiveInterval::iterator NewI = LI.advanceTo(I, NewIdx.getRegSlot());
+ LiveRange::iterator NewI = LR.advanceTo(I, NewIdx.getRegSlot());
if (NewI != E && SlotIndex::isSameInstr(NewI->start, NewIdx)) {
// There is an existing def at NewIdx, case 4 above. The def at OldIdx is
// coalesced into that value.
assert(NewI->valno != DefVNI && "Multiple defs of value?");
- LI.removeValNo(DefVNI);
+ LR.removeValNo(DefVNI);
return;
}
// There was no existing def at NewIdx. Turn *I into a dead def at NewIdx.
- // If the def at OldIdx was dead, we allow it to be moved across other LI
+ // If the def at OldIdx was dead, we allow it to be moved across other LR
// values. The new range should be placed immediately before NewI, move any
// intermediate ranges up.
assert(NewI != I && "Inconsistent iterators");
- std::copy(llvm::next(I), NewI, I);
- *llvm::prior(NewI) = LiveRange(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
+ std::copy(std::next(I), NewI, I);
+ *std::prev(NewI)
+ = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
}
- /// Update LI to reflect an instruction has been moved upwards from OldIdx
+ /// Update LR to reflect an instruction has been moved upwards from OldIdx
/// to NewIdx.
///
/// 1. Live def at OldIdx:
/// Hoist kill to NewIdx, then scan for last kill between NewIdx and
/// OldIdx.
///
- void handleMoveUp(LiveInterval &LI) {
+ void handleMoveUp(LiveRange &LR, unsigned Reg) {
// First look for a kill at OldIdx.
- LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex());
- LiveInterval::iterator E = LI.end();
- // Is LI even live at OldIdx?
+ LiveRange::iterator I = LR.find(OldIdx.getBaseIndex());
+ LiveRange::iterator E = LR.end();
+ // Is LR even live at OldIdx?
if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start))
return;
if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) {
// No def, search for the new kill.
// This can never be an early clobber kill since there is no def.
- llvm::prior(I)->end = findLastUseBefore(LI.reg).getRegSlot();
+ std::prev(I)->end = findLastUseBefore(Reg).getRegSlot();
return;
}
}
DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber());
// Check for an existing def at NewIdx.
- LiveInterval::iterator NewI = LI.find(NewIdx.getRegSlot());
+ LiveRange::iterator NewI = LR.find(NewIdx.getRegSlot());
if (SlotIndex::isSameInstr(NewI->start, NewIdx)) {
assert(NewI->valno != DefVNI && "Same value defined more than once?");
// There is an existing def at NewIdx.
if (I->end.isDead()) {
// Case 3: Remove the dead def at OldIdx.
- LI.removeValNo(DefVNI);
+ LR.removeValNo(DefVNI);
return;
}
// Case 4: Replace def at NewIdx with live def at OldIdx.
I->start = DefVNI->def;
- LI.removeValNo(NewI->valno);
+ LR.removeValNo(NewI->valno);
return;
}
return;
}
- // DefVNI is a dead def. It may have been moved across other values in LI,
+ // DefVNI is a dead def. It may have been moved across other values in LR,
// so move I up to NewI. Slide [NewI;I) down one position.
- std::copy_backward(NewI, I, llvm::next(I));
- *NewI = LiveRange(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
+ std::copy_backward(NewI, I, std::next(I));
+ *NewI = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
}
void updateRegMaskSlots() {
"No RegMask at OldIdx.");
*RI = NewIdx.getRegSlot();
assert((RI == LIS.RegMaskSlots.begin() ||
- SlotIndex::isEarlierInstr(*llvm::prior(RI), *RI)) &&
- "Cannot move regmask instruction above another call");
- assert((llvm::next(RI) == LIS.RegMaskSlots.end() ||
- SlotIndex::isEarlierInstr(*RI, *llvm::next(RI))) &&
- "Cannot move regmask instruction below another call");
+ SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) &&
+ "Cannot move regmask instruction above another call");
+ assert((std::next(RI) == LIS.RegMaskSlots.end() ||
+ SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&
+ "Cannot move regmask instruction below another call");
}
// Return the last use of reg between NewIdx and OldIdx.
if (TargetRegisterInfo::isVirtualRegister(Reg)) {
SlotIndex LastUse = NewIdx;
- for (MachineRegisterInfo::use_nodbg_iterator
- UI = MRI.use_nodbg_begin(Reg),
- UE = MRI.use_nodbg_end();
- UI != UE; UI.skipInstruction()) {
+ for (MachineRegisterInfo::use_instr_nodbg_iterator
+ UI = MRI.use_instr_nodbg_begin(Reg),
+ UE = MRI.use_instr_nodbg_end();
+ UI != UE; ++UI) {
const MachineInstr* MI = &*UI;
SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
if (InstSlot > LastUse && InstSlot < OldIdx)
if (MOI->isReg() &&
TargetRegisterInfo::isVirtualRegister(MOI->getReg()) &&
!hasInterval(MOI->getReg())) {
- LiveInterval &LI = getOrCreateInterval(MOI->getReg());
- computeVirtRegInterval(&LI);
+ createAndComputeVirtRegInterval(MOI->getReg());
}
}
}
if (LII->end.isDead()) {
SlotIndex prevStart;
if (LII != LI.begin())
- prevStart = llvm::prior(LII)->start;
+ prevStart = std::prev(LII)->start;
- // FIXME: This could be more efficient if there was a removeRange
- // method that returned an iterator.
- LI.removeRange(*LII, true);
+ // FIXME: This could be more efficient if there was a
+ // removeSegment method that returned an iterator.
+ LI.removeSegment(*LII, true);
if (prevStart.isValid())
LII = LI.find(prevStart);
else
if (!lastUseIdx.isValid()) {
VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(),
VNInfoAllocator);
- LiveRange LR(instrIdx.getRegSlot(), instrIdx.getDeadSlot(), VNI);
- LII = LI.addRange(LR);
+ LiveRange::Segment S(instrIdx.getRegSlot(),
+ instrIdx.getDeadSlot(), VNI);
+ LII = LI.addSegment(S);
} else if (LII->start != instrIdx.getRegSlot()) {
VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(),
VNInfoAllocator);
- LiveRange LR(instrIdx.getRegSlot(), lastUseIdx, VNI);
- LII = LI.addRange(LR);
+ LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);
+ LII = LI.addSegment(S);
}
if (MO.getSubReg() && !MO.isUndef())
projects / oota-llvm.git / blobdiff