#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "LiveInterval.h"
+#include "llvm/CodeGen/LiveInterval.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/IndexedMap.h"
namespace llvm {
class LiveVariables;
class MRegisterInfo;
+ class TargetInstrInfo;
class VirtRegMap;
class LiveIntervals : public MachineFunctionPass {
MachineFunction* mf_;
const TargetMachine* tm_;
const MRegisterInfo* mri_;
+ const TargetInstrInfo* tii_;
LiveVariables* lv_;
+ /// MBB2IdxMap - The index of the first instruction in the specified basic
+ /// block.
+ std::vector<unsigned> MBB2IdxMap;
+
typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
Mi2IndexMap mi2iMap_;
typedef std::map<unsigned, LiveInterval> Reg2IntervalMap;
Reg2IntervalMap r2iMap_;
- typedef std::map<unsigned, unsigned> Reg2RegMap;
+ typedef IndexedMap<unsigned> Reg2RegMap;
Reg2RegMap r2rMap_;
- std::vector<bool> allocatableRegs_;
+ BitVector allocatableRegs_;
+
+ /// JoinedLIs - Keep track which register intervals have been coalesced
+ /// with other intervals.
+ BitVector JoinedLIs;
public:
- struct InstrSlots
- {
+ struct CopyRec {
+ MachineInstr *MI;
+ unsigned SrcReg, DstReg;
+ };
+ CopyRec getCopyRec(MachineInstr *MI, unsigned SrcReg, unsigned DstReg) {
+ CopyRec R;
+ R.MI = MI;
+ R.SrcReg = SrcReg;
+ R.DstReg = DstReg;
+ return R;
+ }
+ struct InstrSlots {
enum {
LOAD = 0,
USE = 1,
DEF = 2,
STORE = 3,
- NUM = 4,
+ NUM = 4
};
};
return getBaseIndex(index) + InstrSlots::STORE;
}
- // FIXME: this should really be a const_iterator
typedef Reg2IntervalMap::iterator iterator;
+ typedef Reg2IntervalMap::const_iterator const_iterator;
+ const_iterator begin() const { return r2iMap_.begin(); }
+ const_iterator end() const { return r2iMap_.end(); }
iterator begin() { return r2iMap_.begin(); }
iterator end() { return r2iMap_.end(); }
unsigned getNumIntervals() const { return r2iMap_.size(); }
return I->second;
}
+ bool hasInterval(unsigned reg) const {
+ return r2iMap_.count(reg);
+ }
+
+ /// getMBBStartIdx - Return the base index of the first instruction in the
+ /// specified MachineBasicBlock.
+ unsigned getMBBStartIdx(MachineBasicBlock *MBB) const {
+ return getMBBStartIdx(MBB->getNumber());
+ }
+
+ unsigned getMBBStartIdx(unsigned MBBNo) const {
+ assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
+ return MBB2IdxMap[MBBNo];
+ }
+
/// getInstructionIndex - returns the base index of instr
unsigned getInstructionIndex(MachineInstr* instr) const {
Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
"index does not correspond to an instruction");
return i2miMap_[index];
}
-
+
std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
VirtRegMap& vrm,
int slot);
+ /// CreateNewLiveInterval - Create a new live interval with the given live
+ /// ranges. The new live interval will have an infinite spill weight.
+ LiveInterval &CreateNewLiveInterval(const LiveInterval *LI,
+ const std::vector<LiveRange> &LRs);
+
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
virtual void releaseMemory();
/// runOnMachineFunction - pass entry point
virtual bool runOnMachineFunction(MachineFunction&);
+ /// print - Implement the dump method.
+ virtual void print(std::ostream &O, const Module* = 0) const;
+ void print(std::ostream *O, const Module* M = 0) const {
+ if (O) print(*O, M);
+ }
+
private:
- /// computeIntervals - compute live intervals
+ /// isRemoved - returns true if the specified machine instr has been
+ /// removed.
+ bool isRemoved(MachineInstr* instr) const {
+ return !mi2iMap_.count(instr);
+ }
+
+ /// RemoveMachineInstrFromMaps - This marks the specified machine instr as
+ /// deleted.
+ void RemoveMachineInstrFromMaps(MachineInstr *MI) {
+ // remove index -> MachineInstr and
+ // MachineInstr -> index mappings
+ Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
+ if (mi2i != mi2iMap_.end()) {
+ i2miMap_[mi2i->second/InstrSlots::NUM] = 0;
+ mi2iMap_.erase(mi2i);
+ }
+ }
+
+ /// computeIntervals - Compute live intervals.
void computeIntervals();
/// joinIntervals - join compatible live intervals
void joinIntervals();
- /// joinIntervalsInMachineBB - Join intervals based on move
- /// instructions in the specified basic block.
- void joinIntervalsInMachineBB(MachineBasicBlock *MBB);
-
+ /// CopyCoallesceInMBB - Coallsece copies in the specified MBB, putting
+ /// copies that cannot yet be coallesced into the "TryAgain" list.
+ void CopyCoallesceInMBB(MachineBasicBlock *MBB,
+ std::vector<CopyRec> &TryAgain);
+
+ /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
+ /// which are the src/dst of the copy instruction CopyMI. This returns true
+ /// if the copy was successfully coallesced away, or if it is never possible
+ /// to coallesce these this copy, due to register constraints. It returns
+ /// false if it is not currently possible to coallesce this interval, but
+ /// it may be possible if other things get coallesced.
+ bool JoinCopy(MachineInstr *CopyMI, unsigned SrcReg, unsigned DstReg);
+
+ /// JoinIntervals - Attempt to join these two intervals. On failure, this
+ /// returns false. Otherwise, if one of the intervals being joined is a
+ /// physreg, this method always canonicalizes DestInt to be it. The output
+ /// "SrcInt" will not have been modified, so we can use this information
+ /// below to update aliases.
+ bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS);
+
+ /// SimpleJoin - Attempt to join the specified interval into this one. The
+ /// caller of this method must guarantee that the RHS only contains a single
+ /// value number and that the RHS is not defined by a copy from this
+ /// interval. This returns false if the intervals are not joinable, or it
+ /// joins them and returns true.
+ bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS);
+
/// handleRegisterDef - update intervals for a register def
/// (calls handlePhysicalRegisterDef and
/// handleVirtualRegisterDef)
- void handleRegisterDef(MachineBasicBlock* mbb,
- MachineBasicBlock::iterator mi,
+ void handleRegisterDef(MachineBasicBlock *MBB,
+ MachineBasicBlock::iterator MI, unsigned MIIdx,
unsigned reg);
/// handleVirtualRegisterDef - update intervals for a virtual
/// register def
- void handleVirtualRegisterDef(MachineBasicBlock* mbb,
- MachineBasicBlock::iterator mi,
+ void handleVirtualRegisterDef(MachineBasicBlock *MBB,
+ MachineBasicBlock::iterator MI,
+ unsigned MIIdx,
LiveInterval& interval);
- /// handlePhysicalRegisterDef - update intervals for a
- /// physical register def
+ /// handlePhysicalRegisterDef - update intervals for a physical register
+ /// def.
void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
MachineBasicBlock::iterator mi,
- LiveInterval& interval);
+ unsigned MIIdx,
+ LiveInterval &interval,
+ unsigned SrcReg);
+
+ /// handleLiveInRegister - Create interval for a livein register.
+ void handleLiveInRegister(MachineBasicBlock* mbb,
+ unsigned MIIdx,
+ LiveInterval &interval);
/// Return true if the two specified registers belong to different
/// register classes. The registers may be either phys or virt regs.
bool differingRegisterClasses(unsigned RegA, unsigned RegB) const;
- bool overlapsAliases(const LiveInterval *lhs,
- const LiveInterval *rhs) const;
+
+ bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
+ MachineInstr *CopyMI);
+
+ /// lastRegisterUse - Returns the last use of the specific register between
+ /// cycles Start and End. It also returns the use operand by reference. It
+ /// returns NULL if there are no uses.
+ MachineInstr *lastRegisterUse(unsigned Reg, unsigned Start, unsigned End,
+ MachineOperand *&MOU);
+
+ /// unsetRegisterKill - Unset IsKill property of all uses of the specific
+ /// register of the specific instruction.
+ void unsetRegisterKill(MachineInstr *MI, unsigned Reg);
+
+ /// hasRegisterDef - True if the instruction defines the specific register.
+ ///
+ bool hasRegisterDef(MachineInstr *MI, unsigned Reg);
static LiveInterval createInterval(unsigned Reg);
+ void removeInterval(unsigned Reg) {
+ r2iMap_.erase(Reg);
+ }
+
LiveInterval &getOrCreateInterval(unsigned reg) {
Reg2IntervalMap::iterator I = r2iMap_.find(reg);
if (I == r2iMap_.end())
}
/// rep - returns the representative of this register
- unsigned rep(unsigned reg) {
- Reg2RegMap::iterator it = r2rMap_.find(reg);
- if (it != r2rMap_.end())
- return it->second = rep(it->second);
- return reg;
+ unsigned rep(unsigned Reg) {
+ unsigned Rep = r2rMap_[Reg];
+ if (Rep)
+ return r2rMap_[Reg] = rep(Rep);
+ return Reg;
}
void printRegName(unsigned reg) const;