#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
-#include "llvm/ADT/DenseMap.h"
#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;
+ typedef std::pair<unsigned, MachineBasicBlock*> IdxMBBPair;
class LiveIntervals : public MachineFunctionPass {
MachineFunction* mf_;
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;
+
+ /// Idx2MBBMap - Sorted list of pairs of index of first instruction
+ /// and MBB id.
+ std::vector<IdxMBBPair> Idx2MBBMap;
+
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:
+ 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].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];
}
+ /// 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.
+ bool findLiveInMBBs(const LiveRange &LR,
+ SmallVector<MachineBasicBlock*, 4> &MBBs) const;
+
+ // 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);
- virtual void getAnalysisUsage(AnalysisUsage &AU) const;
- virtual void releaseMemory();
+ // Interval removal
- /// runOnMachineFunction - pass entry point
- virtual bool runOnMachineFunction(MachineFunction&);
+ void removeInterval(unsigned Reg) {
+ r2iMap_.erase(Reg);
+ }
- /// print - Implement the dump method.
- virtual void print(std::ostream &O, const Module* = 0) const;
+ /// 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);
}
}
-
- /// computeIntervals - compute live intervals
- void computeIntervals();
- /// joinIntervals - join compatible live intervals
- void joinIntervals();
+ BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+ virtual void releaseMemory();
- /// CopyCoallesceInMBB - Coallsece copies in the specified MBB.
- void CopyCoallesceInMBB(MachineBasicBlock *MBB);
+ /// runOnMachineFunction - pass entry point
+ virtual bool runOnMachineFunction(MachineFunction&);
- /// 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 joint 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);
+ /// 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();
/// 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.
void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
MachineBasicBlock::iterator mi,
+ unsigned MIIdx,
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