#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Allocator.h"
#include <cmath>
-#include <map>
namespace llvm {
+ class AliasAnalysis;
class LiveVariables;
class MachineLoopInfo;
class TargetRegisterInfo;
return LHS.first < RHS.first;
}
};
+
+ // Provide DenseMapInfo for unsigned.
+ template<>
+ struct DenseMapInfo<unsigned> {
+ static inline unsigned getEmptyKey() { return (unsigned)-1; }
+ static inline unsigned getTombstoneKey() { return (unsigned)-2; }
+ static unsigned getHashValue(const unsigned Val) {
+ return Val * 37;
+ }
+ static bool isEqual(const unsigned LHS, const unsigned RHS) {
+ return LHS == RHS;
+ }
+ static bool isPod() { return true; }
+ };
class LiveIntervals : public MachineFunctionPass {
MachineFunction* mf_;
const TargetMachine* tm_;
const TargetRegisterInfo* tri_;
const TargetInstrInfo* tii_;
+ AliasAnalysis *aa_;
LiveVariables* lv_;
/// Special pool allocator for VNInfo's (LiveInterval val#).
/// and MBB id.
std::vector<IdxMBBPair> Idx2MBBMap;
- typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
+ /// FunctionSize - The number of instructions present in the function
+ uint64_t FunctionSize;
+
+ typedef DenseMap<MachineInstr*, unsigned> Mi2IndexMap;
Mi2IndexMap mi2iMap_;
typedef std::vector<MachineInstr*> Index2MiMap;
Index2MiMap i2miMap_;
- typedef std::map<unsigned, LiveInterval> Reg2IntervalMap;
+ typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
Reg2IntervalMap r2iMap_;
BitVector allocatableRegs_;
LiveInterval &getInterval(unsigned reg) {
Reg2IntervalMap::iterator I = r2iMap_.find(reg);
assert(I != r2iMap_.end() && "Interval does not exist for register");
- return I->second;
+ return *I->second;
}
const LiveInterval &getInterval(unsigned reg) const {
Reg2IntervalMap::const_iterator I = r2iMap_.find(reg);
assert(I != r2iMap_.end() && "Interval does not exist for register");
- return I->second;
+ return *I->second;
}
bool hasInterval(unsigned reg) const {
return MBB2IdxMap[MBBNo].second;
}
- /// getIntervalSize - get the size of an interval in "units,"
+ /// 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.
- unsigned getScaledIntervalSize(LiveInterval& I) const {
- return (1000 / InstrSlots::NUM * I.getSize()) / i2miMap_.size();
+ double getScaledIntervalSize(LiveInterval& I) {
+ return (1000.0 / InstrSlots::NUM * I.getSize()) / i2miMap_.size();
+ }
+
+ /// getApproximateInstructionCount - computes an estimate of the number
+ /// of instructions in a given LiveInterval.
+ unsigned getApproximateInstructionCount(LiveInterval& I) {
+ double IntervalPercentage = getScaledIntervalSize(I) / 1000.0;
+ return (unsigned)(IntervalPercentage * FunctionSize);
}
/// getMBBFromIndex - given an index in any instruction of an
/// findLiveInMBBs - Given a live range, if the value of the range
/// is live in any MBB returns true as well as the list of basic blocks
- /// where the value is live in.
+ /// in which the value is live.
bool findLiveInMBBs(const LiveRange &LR,
SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
LiveInterval &getOrCreateInterval(unsigned reg) {
Reg2IntervalMap::iterator I = r2iMap_.find(reg);
if (I == r2iMap_.end())
- I = r2iMap_.insert(I, std::make_pair(reg, createInterval(reg)));
- return I->second;
+ I = r2iMap_.insert(std::make_pair(reg, createInterval(reg))).first;
+ return *I->second;
}
/// addLiveRangeToEndOfBlock - Given a register and an instruction,
// Interval removal
void removeInterval(unsigned Reg) {
- r2iMap_.erase(Reg);
+ DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.find(Reg);
+ delete I->second;
+ r2iMap_.erase(I);
}
/// isRemoved - returns true if the specified machine instr has been
/// handleVirtualRegisterDef)
void handleRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator MI, unsigned MIIdx,
- unsigned reg);
+ MachineOperand& MO, unsigned MOIdx);
/// handleVirtualRegisterDef - update intervals for a virtual
/// register def
void handleVirtualRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator MI,
- unsigned MIIdx,
- LiveInterval& interval);
+ unsigned MIIdx, MachineOperand& MO,
+ unsigned MOIdx, LiveInterval& interval);
/// handlePhysicalRegisterDef - update intervals for a physical register
/// def.
void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
MachineBasicBlock::iterator mi,
- unsigned MIIdx,
+ unsigned MIIdx, MachineOperand& MO,
LiveInterval &interval,
MachineInstr *CopyMI);
bool alsoFoldARestore(int Id, int index, unsigned vr,
BitVector &RestoreMBBs,
- std::map<unsigned,std::vector<SRInfo> >&RestoreIdxes);
+ DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
void eraseRestoreInfo(int Id, int index, unsigned vr,
BitVector &RestoreMBBs,
- std::map<unsigned,std::vector<SRInfo> >&RestoreIdxes);
+ DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
/// spilled and create empty intervals for their uses.
VirtRegMap &vrm, const TargetRegisterClass* rc,
SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
- std::map<unsigned,unsigned> &MBBVRegsMap,
+ DenseMap<unsigned,unsigned> &MBBVRegsMap,
std::vector<LiveInterval*> &NewLIs, float &SSWeight);
void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
LiveInterval::Ranges::const_iterator &I,
VirtRegMap &vrm, const TargetRegisterClass* rc,
SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
BitVector &SpillMBBs,
- std::map<unsigned,std::vector<SRInfo> > &SpillIdxes,
+ DenseMap<unsigned,std::vector<SRInfo> > &SpillIdxes,
BitVector &RestoreMBBs,
- std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes,
- std::map<unsigned,unsigned> &MBBVRegsMap,
+ DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes,
+ DenseMap<unsigned,unsigned> &MBBVRegsMap,
std::vector<LiveInterval*> &NewLIs, float &SSWeight);
- static LiveInterval createInterval(unsigned Reg);
+ static LiveInterval* createInterval(unsigned Reg);
void printRegName(unsigned reg) const;
};