Add option to join live intervals. Two intervals are joined if there
is a move between two registers, at least one of the registers is
virtual and the two live intervals do not overlap.
This results in about 40% reduction in intervals, 30% decrease in the
register allocators running time and a 20% increase in peephole
optimizations (mainly move eliminations).
The option can be enabled by passing -join-liveintervals where
appropriate.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10965 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/LiveIntervalAnalysis.h b/lib/CodeGen/LiveIntervalAnalysis.h
index dd521a4..292c511 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.h
+++ b/lib/CodeGen/LiveIntervalAnalysis.h
@@ -26,6 +26,7 @@
#include <iostream>
#include <list>
#include <map>
+#include <vector>
namespace llvm {
@@ -39,10 +40,9 @@
typedef std::pair<unsigned, unsigned> Range;
typedef std::vector<Range> Ranges;
unsigned reg; // the register of this interval
- unsigned hint;
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);
@@ -66,10 +66,12 @@
void addRange(unsigned start, unsigned end);
- private:
- void mergeRangesForward(Ranges::iterator it);
+ void join(const Interval& other);
- void mergeRangesBackward(Ranges::iterator it);
+ private:
+ Ranges::iterator mergeRangesForward(Ranges::iterator it);
+
+ Ranges::iterator mergeRangesBackward(Ranges::iterator it);
};
struct StartPointComp {
@@ -85,6 +87,7 @@
};
typedef std::list<Interval> Intervals;
+ typedef std::map<unsigned, unsigned> Reg2RegMap;
typedef std::vector<MachineBasicBlock*> MachineBasicBlockPtrs;
private:
@@ -104,11 +107,15 @@
typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
Reg2IntervalMap r2iMap_;
+ Reg2RegMap r2rMap_;
+
Intervals intervals_;
public:
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+
Intervals& getIntervals() { return intervals_; }
+
MachineBasicBlockPtrs getOrderedMachineBasicBlockPtrs() const {
MachineBasicBlockPtrs result;
for (MbbIndex2MbbMap::const_iterator
@@ -119,6 +126,13 @@
return result;
}
+ const Reg2RegMap& getJoinedRegMap() const {
+ return r2rMap_;
+ }
+
+ /// rep - returns the representative of this register
+ unsigned rep(unsigned reg);
+
private:
/// runOnMachineFunction - pass entry point
bool runOnMachineFunction(MachineFunction&);
@@ -126,6 +140,8 @@
/// computeIntervals - compute live intervals
void computeIntervals();
+ /// joinIntervals - join compatible live intervals
+ void joinIntervals();
/// handleRegisterDef - update intervals for a register def
/// (calls handlePhysicalRegisterDef and