namespace llvm {
class AliasAnalysis;
+ class LiveRangeCalc;
class LiveVariables;
+ class MachineDominatorTree;
class MachineLoopInfo;
class TargetRegisterInfo;
class MachineRegisterInfo;
AliasAnalysis *AA;
LiveVariables* LV;
SlotIndexes* Indexes;
+ MachineDominatorTree *DomTree;
+ LiveRangeCalc *LRCalc;
/// Special pool allocator for VNInfo's (LiveInterval val#).
///
/// block.
SmallVector<std::pair<unsigned, unsigned>, 8> RegMaskBlocks;
+ /// RegUnitIntervals - Keep a live interval for each register unit as a way
+ /// of tracking fixed physreg interference.
+ SmallVector<LiveInterval*, 0> RegUnitIntervals;
+
public:
static char ID; // Pass identification, replacement for typeid
- LiveIntervals() : MachineFunctionPass(ID) {
- initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
- }
+ LiveIntervals();
+ virtual ~LiveIntervals();
// Calculate the spill weight to assign to a single instruction.
static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth);
bool checkRegMaskInterference(LiveInterval &LI,
BitVector &UsableRegs);
+ // Register unit functions.
+ //
+ // Fixed interference occurs when MachineInstrs use physregs directly
+ // instead of virtual registers. This typically happens when passing
+ // arguments to a function call, or when instructions require operands in
+ // fixed registers.
+ //
+ // Each physreg has one or more register units, see MCRegisterInfo. We
+ // track liveness per register unit to handle aliasing registers more
+ // efficiently.
+
+ /// getRegUnit - Return the live range for Unit.
+ /// It will be computed if it doesn't exist.
+ LiveInterval &getRegUnit(unsigned Unit) {
+ LiveInterval *LI = RegUnitIntervals[Unit];
+ if (!LI) {
+ // Compute missing ranges on demand.
+ RegUnitIntervals[Unit] = LI = new LiveInterval(Unit, HUGE_VALF);
+ computeRegUnitInterval(LI);
+ }
+ return *LI;
+ }
+
+ /// trackingRegUnits - Does LiveIntervals curently track register units?
+ /// This function will be removed when regunit tracking is permanently
+ /// enabled.
+ bool trackingRegUnits() const { return !RegUnitIntervals.empty(); }
+
private:
/// computeIntervals - Compute live intervals.
void computeIntervals();
void printInstrs(raw_ostream &O) const;
void dumpInstrs() const;
+ void computeLiveInRegUnits();
+ void computeRegUnitInterval(LiveInterval*);
+
class HMEditor;
};
} // End llvm namespace
#include "llvm/Value.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveVariables.h"
+#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
+#include "LiveRangeCalc.h"
#include <algorithm>
#include <limits>
#include <cmath>
static cl::opt<bool> DisableReMat("disable-rematerialization",
cl::init(false), cl::Hidden);
+// Temporary option to enable regunit liveness.
+static cl::opt<bool> LiveRegUnits("live-regunits", cl::Hidden);
+
STATISTIC(numIntervals , "Number of original intervals");
char LiveIntervals::ID = 0;
AU.addRequired<LiveVariables>();
AU.addPreserved<LiveVariables>();
AU.addPreservedID(MachineLoopInfoID);
+ if (LiveRegUnits)
+ AU.addRequiredTransitiveID(MachineDominatorsID);
AU.addPreservedID(MachineDominatorsID);
AU.addPreserved<SlotIndexes>();
AU.addRequiredTransitive<SlotIndexes>();
MachineFunctionPass::getAnalysisUsage(AU);
}
+LiveIntervals::LiveIntervals() : MachineFunctionPass(ID),
+ DomTree(0), LRCalc(0) {
+ initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
+}
+
+LiveIntervals::~LiveIntervals() {
+ delete LRCalc;
+}
+
void LiveIntervals::releaseMemory() {
// Free the live intervals themselves.
for (DenseMap<unsigned, LiveInterval*>::iterator I = R2IMap.begin(),
RegMaskBits.clear();
RegMaskBlocks.clear();
+ for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
+ delete RegUnitIntervals[i];
+ RegUnitIntervals.clear();
+
// Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
VNInfoAllocator.Reset();
}
AA = &getAnalysis<AliasAnalysis>();
LV = &getAnalysis<LiveVariables>();
Indexes = &getAnalysis<SlotIndexes>();
+ if (LiveRegUnits)
+ DomTree = &getAnalysis<MachineDominatorTree>();
+ if (LiveRegUnits && !LRCalc)
+ LRCalc = new LiveRangeCalc();
AllocatableRegs = TRI->getAllocatableSet(fn);
ReservedRegs = TRI->getReservedRegs(fn);
numIntervals += getNumIntervals();
+ if (LiveRegUnits) {
+ computeLiveInRegUnits();
+ }
+
DEBUG(dump());
return true;
}
OS << '\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';
+
// Dump the virtregs.
for (unsigned Reg = 0, RegE = MRI->getNumVirtRegs(); Reg != RegE; ++Reg)
if (const LiveInterval *LI =
return new LiveInterval(reg, Weight);
}
+
+//===----------------------------------------------------------------------===//
+// Register Unit Liveness
+//===----------------------------------------------------------------------===//
+//
+// Fixed interference typically comes from ABI boundaries: Function arguments
+// and return values are passed in fixed registers, and so are exception
+// pointers entering landing pads. Certain instructions require values to be
+// present in specific registers. That is also represented through fixed
+// interference.
+//
+
+/// computeRegUnitInterval - Compute the live interval of a register unit, based
+/// on the uses and defs of aliasing registers. The interval should be empty,
+/// or contain only dead phi-defs from ABI blocks.
+void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) {
+ unsigned Unit = LI->reg;
+
+ assert(LRCalc && "LRCalc not initialized.");
+ LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
+
+ // The physregs aliasing Unit are the roots and their super-registers.
+ // Create all values as dead defs before extending to uses. Note that roots
+ // may share super-registers. That's OK because createDeadDefs() is
+ // 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) {
+ if (!MRI->reg_empty(*Supers))
+ LRCalc->createDeadDefs(LI, *Supers);
+ }
+ }
+
+ // Now extend LI 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 (!isReserved(Root) && !MRI->reg_empty(Root))
+ LRCalc->extendToUses(LI, Root);
+ for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) {
+ unsigned Reg = *Supers;
+ if (!isReserved(Reg) && !MRI->reg_empty(Reg))
+ LRCalc->extendToUses(LI, Reg);
+ }
+ }
+}
+
+
+/// computeLiveInRegUnits - Precompute the live ranges of any register units
+/// that are live-in to an ABI block somewhere. Register values can appear
+/// without a corresponding def when entering the entry block or a landing pad.
+///
+void LiveIntervals::computeLiveInRegUnits() {
+ RegUnitIntervals.resize(TRI->getNumRegUnits());
+ DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
+
+ // Keep track of the intervals allocated.
+ SmallVector<LiveInterval*, 8> NewIntvs;
+
+ // Check all basic blocks for live-ins.
+ for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
+ MFI != MFE; ++MFI) {
+ const MachineBasicBlock *MBB = MFI;
+
+ // We only care about ABI blocks: Entry + landing pads.
+ if ((MFI != MF->begin() && !MBB->isLandingPad()) || MBB->livein_empty())
+ continue;
+
+ // Create phi-defs at Begin for all live-in registers.
+ SlotIndex Begin = Indexes->getMBBStartIdx(MBB);
+ DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber());
+ for (MachineBasicBlock::livein_iterator LII = MBB->livein_begin(),
+ 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);
+ }
+ VNInfo *VNI = Intv->createDeadDef(Begin, getVNInfoAllocator());
+ DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id);
+ }
+ }
+ DEBUG(dbgs() << '\n');
+ }
+ DEBUG(dbgs() << "Created " << NewIntvs.size() << " new intervals.\n");
+
+ // Compute the 'normal' part of the intervals.
+ for (unsigned i = 0, e = NewIntvs.size(); i != e; ++i)
+ computeRegUnitInterval(NewIntvs[i]);
+}
+
+
/// 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.