//
// This file implements the LiveInterval analysis pass. Given some
// numbering of each the machine instructions (in this implemention
-// depth-first order) an interval [i, j] is said to be a live interval
+// depth-first order) an interval [i, j) is said to be a live interval
// for register v if there is no instruction with number j' > j such
// that v is live at j' abd there is no instruction with number i' < i
// such that v is live at i'. In this implementation intervals can
-// have holes, i.e. an interval might look like [1,20], [50,65],
-// [1000,1001]
+// have holes, i.e. an interval might look like [1,20), [50,65),
+// [1000,1001)
//
//===----------------------------------------------------------------------===//
#define LLVM_CODEGEN_LIVEINTERVALS_H
#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/MachineBasicBlock.h"
-#include <iostream>
-#include <map>
+#include <list>
namespace llvm {
class LiveVariables;
class MRegisterInfo;
+ class VirtRegMap;
class LiveIntervals : public MachineFunctionPass
{
unsigned reg; // the register of this interval
float weight; // weight of this interval (number of uses
// * 10^loopDepth)
- Ranges ranges; // the ranges this register is valid
+ Ranges ranges; // the ranges in which this register is live
Interval(unsigned r);
+ bool empty() const { return ranges.empty(); }
+
+ bool spilled() const;
+
unsigned start() const {
- assert(!ranges.empty() && "empty interval for register");
+ assert(!empty() && "empty interval for register");
return ranges.front().first;
}
unsigned end() const {
- assert(!ranges.empty() && "empty interval for register");
+ assert(!empty() && "empty interval for register");
return ranges.back().second;
}
bool expiredAt(unsigned index) const {
- return end() <= index;
+ return end() <= (index + 1);
}
bool liveAt(unsigned index) const;
void addRange(unsigned start, unsigned end);
+ void join(const Interval& other);
+
private:
- void mergeRangesForward(Ranges::iterator it);
+ Ranges::iterator mergeRangesForward(Ranges::iterator it);
- void mergeRangesBackward(Ranges::iterator it);
+ Ranges::iterator mergeRangesBackward(Ranges::iterator it);
};
struct StartPointComp {
}
};
- typedef std::vector<Interval> Intervals;
- typedef std::vector<MachineBasicBlock*> MachineBasicBlockPtrs;
+ typedef std::list<Interval> Intervals;
private:
MachineFunction* mf_;
MachineBasicBlock::iterator currentInstr_;
LiveVariables* lv_;
- std::vector<bool> allocatableRegisters_;
-
typedef std::map<unsigned, MachineBasicBlock*> MbbIndex2MbbMap;
MbbIndex2MbbMap mbbi2mbbMap_;
typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
Mi2IndexMap mi2iMap_;
- typedef std::map<unsigned, unsigned> Reg2IntervalMap;
+ typedef std::vector<MachineInstr*> Index2MiMap;
+ Index2MiMap i2miMap_;
+
+ typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
Reg2IntervalMap r2iMap_;
+ typedef std::map<unsigned, unsigned> Reg2RegMap;
+ Reg2RegMap r2rMap_;
+
Intervals intervals_;
public:
- virtual void getAnalysisUsage(AnalysisUsage &AU) const;
- Intervals& getIntervals() { return intervals_; }
- MachineBasicBlockPtrs getOrderedMachineBasicBlockPtrs() const {
- MachineBasicBlockPtrs result;
- for (MbbIndex2MbbMap::const_iterator
- it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
- it != itEnd; ++it) {
- result.push_back(it->second);
- }
- return result;
+ struct InstrSlots
+ {
+ enum {
+ LOAD = 0,
+ USE = 1,
+ DEF = 2,
+ STORE = 3,
+ NUM = 4,
+ };
+ };
+
+ static unsigned getBaseIndex(unsigned index) {
+ return index - (index % InstrSlots::NUM);
+ }
+ static unsigned getBoundaryIndex(unsigned index) {
+ return getBaseIndex(index + InstrSlots::NUM - 1);
+ }
+ static unsigned getLoadIndex(unsigned index) {
+ return getBaseIndex(index) + InstrSlots::LOAD;
+ }
+ static unsigned getUseIndex(unsigned index) {
+ return getBaseIndex(index) + InstrSlots::USE;
+ }
+ static unsigned getDefIndex(unsigned index) {
+ return getBaseIndex(index) + InstrSlots::DEF;
+ }
+ static unsigned getStoreIndex(unsigned index) {
+ return getBaseIndex(index) + InstrSlots::STORE;
}
- private:
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+ virtual void releaseMemory();
+
/// runOnMachineFunction - pass entry point
- bool runOnMachineFunction(MachineFunction&);
+ virtual bool runOnMachineFunction(MachineFunction&);
+
+ Interval& getInterval(unsigned reg) {
+ assert(r2iMap_.count(reg)&& "Interval does not exist for register");
+ return *r2iMap_.find(reg)->second;
+ }
+
+ /// getInstructionIndex - returns the base index of instr
+ unsigned getInstructionIndex(MachineInstr* instr) const;
+ /// getInstructionFromIndex - given an index in any slot of an
+ /// instruction return a pointer the instruction
+ MachineInstr* getInstructionFromIndex(unsigned index) const;
+
+ Intervals& getIntervals() { return intervals_; }
+
+ void updateSpilledInterval(Interval& i, VirtRegMap& vrm, int slot);
+
+ private:
/// computeIntervals - compute live intervals
void computeIntervals();
+ /// joinIntervals - join compatible live intervals
+ void joinIntervals();
/// handleRegisterDef - update intervals for a register def
/// (calls handlePhysicalRegisterDef and
MachineBasicBlock::iterator mi,
unsigned reg);
- unsigned getInstructionIndex(MachineInstr* instr) const;
+ bool overlapsAliases(const Interval& lhs, const Interval& rhs) const;
+
+ /// rep - returns the representative of this register
+ unsigned rep(unsigned reg);
void printRegName(unsigned reg) const;
};
projects / oota-llvm.git / blobdiff