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

1 files changed, 20 insertions, 4 deletions

diff --git a/lib/CodeGen/LiveIntervalAnalysis.h b/lib/CodeGen/LiveIntervalAnalysis.h
index dd521a40c0..292c511120 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 @@ namespace llvm {
             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 @@ namespace llvm {
 
             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 {
@@ -85,6 +87,7 @@ namespace llvm {
         };
 
         typedef std::list<Interval> Intervals;
+        typedef std::map<unsigned, unsigned> Reg2RegMap;
         typedef std::vector<MachineBasicBlock*> MachineBasicBlockPtrs;
 
     private:
@@ -104,11 +107,15 @@ namespace llvm {
         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 @@ namespace llvm {
             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 @@ namespace llvm {
         /// computeIntervals - compute live intervals
         void computeIntervals();
 
+        /// joinIntervals - join compatible live intervals
+        void joinIntervals();
 
         /// handleRegisterDef - update intervals for a register def
         /// (calls handlePhysicalRegisterDef and