class TargetInstrInfo;
class TargetRegisterClass;
class VirtRegMap;
-
+
class LiveIntervals : public MachineFunctionPass {
MachineFunction* mf_;
MachineRegisterInfo* mri_;
/// Special pool allocator for VNInfo's (LiveInterval val#).
///
- BumpPtrAllocator VNInfoAllocator;
+ VNInfo::Allocator VNInfoAllocator;
typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
Reg2IntervalMap r2iMap_;
- /// phiJoinCopies - Copy instructions which are PHI joins.
- SmallVector<MachineInstr*, 16> phiJoinCopies;
-
/// allocatableRegs_ - A bit vector of allocatable registers.
BitVector allocatableRegs_;
public:
static char ID; // Pass identification, replacement for typeid
- LiveIntervals() : MachineFunctionPass(&ID) {}
+ LiveIntervals() : MachineFunctionPass(ID) {
+ initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
+ }
+
+ // Calculate the spill weight to assign to a single instruction.
+ static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth);
- static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
- return (isDef + isUse) * powf(10.0F, (float)loopDepth);
+ // After summing the spill weights of all defs and uses, the final weight
+ // should be normalized, dividing the weight of the interval by its size.
+ // This encourages spilling of intervals that are large and have few uses,
+ // and discourages spilling of small intervals with many uses.
+ void normalizeSpillWeight(LiveInterval &li) {
+ li.weight /= getApproximateInstructionCount(li) + 25;
}
typedef Reg2IntervalMap::iterator iterator;
return r2iMap_.count(reg);
}
+ /// isAllocatable - is the physical register reg allocatable in the current
+ /// function?
+ bool isAllocatable(unsigned reg) const {
+ return allocatableRegs_.test(reg);
+ }
+
/// getScaledIntervalSize - get the size of an interval in "units,"
/// where every function is composed of one thousand units. This
/// measure scales properly with empty index slots in the function.
double getScaledIntervalSize(LiveInterval& I) {
return (1000.0 * I.getSize()) / indexes_->getIndexesLength();
}
-
+
+ /// getFuncInstructionCount - Return the number of instructions in the
+ /// current function.
+ unsigned getFuncInstructionCount() {
+ return indexes_->getFunctionSize();
+ }
+
/// getApproximateInstructionCount - computes an estimate of the number
/// of instructions in a given LiveInterval.
unsigned getApproximateInstructionCount(LiveInterval& I) {
return (unsigned)(IntervalPercentage * indexes_->getFunctionSize());
}
- /// conflictsWithPhysRegDef - Returns true if the specified register
- /// is defined during the duration of the specified interval.
- bool conflictsWithPhysRegDef(const LiveInterval &li, VirtRegMap &vrm,
- unsigned reg);
+ /// conflictsWithPhysReg - Returns true if the specified register is used or
+ /// defined during the duration of the specified interval. Copies to and
+ /// from li.reg are allowed. This method is only able to analyze simple
+ /// ranges that stay within a single basic block. Anything else is
+ /// considered a conflict.
+ bool conflictsWithPhysReg(const LiveInterval &li, VirtRegMap &vrm,
+ unsigned reg);
- /// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except
- /// it can check use as well.
- bool conflictsWithPhysRegRef(LiveInterval &li, unsigned Reg,
- bool CheckUse,
- SmallPtrSet<MachineInstr*,32> &JoinedCopies);
+ /// conflictsWithAliasRef - Similar to conflictsWithPhysRegRef except
+ /// it checks for alias uses and defs.
+ bool conflictsWithAliasRef(LiveInterval &li, unsigned Reg,
+ SmallPtrSet<MachineInstr*,32> &JoinedCopies);
// Interval creation
LiveInterval &getOrCreateInterval(unsigned reg) {
/// dupInterval - Duplicate a live interval. The caller is responsible for
/// managing the allocated memory.
LiveInterval *dupInterval(LiveInterval *li);
-
+
/// addLiveRangeToEndOfBlock - Given a register and an instruction,
/// adds a live range from that instruction to the end of its MBB.
LiveRange addLiveRangeToEndOfBlock(unsigned reg,
SlotIndex getInstructionIndex(const MachineInstr *instr) const {
return indexes_->getInstructionIndex(instr);
}
-
+
/// Returns the instruction associated with the given index.
MachineInstr* getInstructionFromIndex(SlotIndex index) const {
return indexes_->getInstructionFromIndex(index);
/// Return the first index in the given basic block.
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
return indexes_->getMBBStartIdx(mbb);
- }
+ }
/// Return the last index in the given basic block.
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
return indexes_->getMBBEndIdx(mbb);
- }
+ }
- MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
- return indexes_->getMBBFromIndex(index);
+ bool isLiveInToMBB(const LiveInterval &li,
+ const MachineBasicBlock *mbb) const {
+ return li.liveAt(getMBBStartIdx(mbb));
}
- bool hasGapBeforeInstr(SlotIndex index) {
- return indexes_->hasGapBeforeInstr(index);
+ LiveRange* findEnteringRange(LiveInterval &li,
+ const MachineBasicBlock *mbb) {
+ return li.getLiveRangeContaining(getMBBStartIdx(mbb));
}
- bool hasGapAfterInstr(SlotIndex index) {
- return indexes_->hasGapAfterInstr(index);
+ bool isLiveOutOfMBB(const LiveInterval &li,
+ const MachineBasicBlock *mbb) const {
+ return li.liveAt(getMBBEndIdx(mbb).getPrevSlot());
}
- SlotIndex findGapBeforeInstr(SlotIndex index, bool furthest = false) {
- return indexes_->findGapBeforeInstr(index, furthest);
+ LiveRange* findExitingRange(LiveInterval &li,
+ const MachineBasicBlock *mbb) {
+ return li.getLiveRangeContaining(getMBBEndIdx(mbb).getPrevSlot());
}
- void InsertMachineInstrInMaps(MachineInstr *MI, SlotIndex Index) {
- indexes_->insertMachineInstrInMaps(MI, Index);
+ MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
+ return indexes_->getMBBFromIndex(index);
+ }
+
+ SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) {
+ return indexes_->insertMachineInstrInMaps(MI);
}
void RemoveMachineInstrFromMaps(MachineInstr *MI) {
indexes_->replaceMachineInstrInMaps(MI, NewMI);
}
+ void InsertMBBInMaps(MachineBasicBlock *MBB) {
+ indexes_->insertMBBInMaps(MBB);
+ }
+
bool findLiveInMBBs(SlotIndex Start, SlotIndex End,
SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
return indexes_->findLiveInMBBs(Start, End, MBBs);
}
void renumber() {
- indexes_->renumber();
+ indexes_->renumberIndexes();
}
- BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; }
-
- /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
- /// copy field and returns the source register that defines it.
- unsigned getVNInfoSourceReg(const VNInfo *VNI) const;
+ VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; }
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
virtual void releaseMemory();
addIntervalsForSpills(const LiveInterval& i,
SmallVectorImpl<LiveInterval*> &SpillIs,
const MachineLoopInfo *loopInfo, VirtRegMap& vrm);
-
- /// addIntervalsForSpillsFast - Quickly create new intervals for spilled
- /// defs / uses without remat or splitting.
- std::vector<LiveInterval*>
- addIntervalsForSpillsFast(const LiveInterval &li,
- const MachineLoopInfo *loopInfo, VirtRegMap &vrm);
/// spillPhysRegAroundRegDefsUses - Spill the specified physical register
/// around all defs and uses of the specified interval. Return true if it
unsigned getNumConflictsWithPhysReg(const LiveInterval &li,
unsigned PhysReg) const;
- /// processImplicitDefs - Process IMPLICIT_DEF instructions. Add isUndef
- /// marker to implicit_def defs and their uses.
- void processImplicitDefs();
-
/// intervalIsInOneMBB - Returns true if the specified interval is entirely
/// within a single basic block.
bool intervalIsInOneMBB(const LiveInterval &li) const;
- private:
+ private:
/// computeIntervals - Compute live intervals.
void computeIntervals();
- bool isProfitableToCoalesce(LiveInterval &DstInt, LiveInterval &SrcInt,
- SmallVector<MachineInstr*,16> &IdentCopies,
- SmallVector<MachineInstr*,16> &OtherCopies);
-
- void performEarlyCoalescing();
-
/// handleRegisterDef - update intervals for a register def
/// (calls handlePhysicalRegisterDef and
/// handleVirtualRegisterDef)
SlotIndex MIIdx,
MachineOperand& MO, unsigned MOIdx);
+ /// isPartialRedef - Return true if the specified def at the specific index
+ /// is partially re-defining the specified live interval. A common case of
+ /// this is a definition of the sub-register.
+ bool isPartialRedef(SlotIndex MIIdx, MachineOperand &MO,
+ LiveInterval &interval);
+
/// handleVirtualRegisterDef - update intervals for a virtual
/// register def
void handleVirtualRegisterDef(MachineBasicBlock *MBB,
DenseMap<unsigned,unsigned> &MBBVRegsMap,
std::vector<LiveInterval*> &NewLIs);
+ // Normalize the spill weight of all the intervals in NewLIs.
+ void normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs);
+
static LiveInterval* createInterval(unsigned Reg);
void printInstrs(raw_ostream &O) const;
projects / oota-llvm.git / blobdiff