#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
-#include "llvm/ADT/DenseMap.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "LiveInterval.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_;
+ /// 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 DenseMap<unsigned> Reg2RegMap;
- Reg2RegMap r2rMap_;
+ BitVector allocatableRegs_;
- std::vector<bool> allocatableRegs_;
+ std::vector<MachineInstr*> ClonedMIs;
public:
- struct InstrSlots
- {
+ static char ID; // Pass identification, replacement for typeid
+ LiveIntervals() : MachineFunctionPass((intptr_t)&ID) {}
+
+ struct InstrSlots {
enum {
LOAD = 0,
USE = 1,
DEF = 2,
STORE = 3,
- NUM = 4,
+ NUM = 4
};
};
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].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
unsigned getInstructionIndex(MachineInstr* instr) const {
Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
return i2miMap_[index];
}
+ // Interval creation
+
+ 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;
+ }
+
std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
- VirtRegMap& vrm,
- int slot);
+ VirtRegMap& vrm, unsigned reg);
+
+ // 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);
+ }
+
+ /// 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);
+ }
+ }
+
+ BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; }
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
virtual void releaseMemory();
/// 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
+ private:
+ /// 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);
-
+
/// 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. If the defining instruction is a move instruction, SrcReg will be
- /// the input register, and DestReg will be the result. Note that Interval
- /// may not match DestReg (it might be an alias instead).
- ///
+ /// def.
void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
MachineBasicBlock::iterator mi,
- LiveInterval& interval,
- unsigned SrcReg, unsigned DestReg);
-
- /// 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;
+ unsigned MIIdx,
+ LiveInterval &interval,
+ unsigned SrcReg);
+
+ /// handleLiveInRegister - Create interval for a livein register.
+ void handleLiveInRegister(MachineBasicBlock* mbb,
+ unsigned MIIdx,
+ LiveInterval &interval, bool isAlias = false);
+
+ /// 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);
+
+ /// 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