#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/LiveInterval.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/IndexedMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Allocator.h"
namespace llvm {
class LiveVariables;
class MRegisterInfo;
class TargetInstrInfo;
+ class TargetRegisterClass;
class VirtRegMap;
class LiveIntervals : public MachineFunctionPass {
const TargetInstrInfo* tii_;
LiveVariables* lv_;
- /// MBB2IdxMap - The index of the first instruction in the specified basic
- /// block.
- std::vector<unsigned> MBB2IdxMap;
-
+ /// Special pool allocator for VNInfo's (LiveInterval val#).
+ ///
+ BumpPtrAllocator VNInfoAllocator;
+
+ /// MBB2IdxMap - The indexes of the first and last instructions in the
+ /// specified basic block.
+ std::vector<std::pair<unsigned, unsigned> > MBB2IdxMap;
+
typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
Mi2IndexMap mi2iMap_;
typedef std::map<unsigned, LiveInterval> Reg2IntervalMap;
Reg2IntervalMap r2iMap_;
- typedef IndexedMap<unsigned> Reg2RegMap;
- Reg2RegMap r2rMap_;
+ BitVector allocatableRegs_;
- std::vector<bool> allocatableRegs_;
+ std::vector<MachineInstr*> ClonedMIs;
public:
- 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;
- }
+ static char ID; // Pass identification, replacement for typeid
+ LiveIntervals() : MachineFunctionPass((intptr_t)&ID) {}
+
struct InstrSlots {
enum {
LOAD = 0,
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];
+ return MBB2IdxMap[MBBNo].first;
+ }
+
+ /// getMBBEndIdx - Return the store index of the last instruction in the
+ /// specified MachineBasicBlock.
+ unsigned getMBBEndIdx(MachineBasicBlock *MBB) const {
+ return getMBBEndIdx(MBB->getNumber());
+ }
+ unsigned getMBBEndIdx(unsigned MBBNo) const {
+ assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
+ return MBB2IdxMap[MBBNo].second;
}
/// getInstructionIndex - returns the base index of 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);
+ // Interval creation
- virtual void getAnalysisUsage(AnalysisUsage &AU) const;
- virtual void releaseMemory();
+ 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;
+ }
- /// runOnMachineFunction - pass entry point
- virtual bool runOnMachineFunction(MachineFunction&);
+ std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
+ VirtRegMap& vrm, unsigned reg);
- /// 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);
+ // Interval removal
+
+ void removeInterval(unsigned Reg) {
+ r2iMap_.erase(Reg);
+ }
+
+ /// isRemoved - returns true if the specified machine instr has been
+ /// removed.
+ bool isRemoved(MachineInstr* instr) const {
+ return !mi2iMap_.count(instr);
}
- private:
/// RemoveMachineInstrFromMaps - This marks the specified machine instr as
/// deleted.
void RemoveMachineInstrFromMaps(MachineInstr *MI) {
mi2iMap_.erase(mi2i);
}
}
-
+
+ BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; }
+
+ 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.
void computeIntervals();
-
- /// joinIntervals - join compatible live intervals
- void joinIntervals();
-
- /// 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
LiveInterval &interval,
unsigned SrcReg);
- /// 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;
-
+ /// handleLiveInRegister - Create interval for a livein register.
+ void handleLiveInRegister(MachineBasicBlock* mbb,
+ unsigned MIIdx,
+ LiveInterval &interval, bool isAlias = false);
- bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
- MachineInstr *CopyMI);
+ /// isReMaterializable - Returns true if the definition MI of the specified
+ /// val# of the specified interval is re-materializable.
+ bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo,
+ MachineInstr *MI);
- bool overlapsAliases(const LiveInterval *lhs,
- const LiveInterval *rhs) const;
+ /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
+ /// slot / to reg or any rematerialized load into ith operand of specified
+ /// MI. If it is successul, MI is updated with the newly created MI and
+ /// returns true.
+ bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
+ MachineInstr *DefMI, unsigned index, unsigned i,
+ bool isSS, int slot, unsigned reg);
static LiveInterval createInterval(unsigned Reg);
- 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;
- }
-
- /// rep - returns the representative of this register
- unsigned rep(unsigned Reg) {
- unsigned Rep = r2rMap_[Reg];
- if (Rep)
- return r2rMap_[Reg] = rep(Rep);
- return Reg;
- }
-
void printRegName(unsigned reg) const;
};
projects / oota-llvm.git / blobdiff