Add early coalescing to liveintervals. This is work in progress and is known to miscompute some tests. Read it at your own rish, I have aged 10 year while writing this.

The gist of this is if source of some of the copies that feed into a phi join is defined by the phi join, we'd like to eliminate them. However, if any of the non-identity source overlaps the live interval of the phi join then the coalescer won't be able to coalesce them. The early coalescer's job is to eliminate the identity copies by partially-coalescing the two live intervals.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81796 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 16 insertions, 7 deletions

diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index f61a442a06..1878b2e634 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -584,7 +584,6 @@ namespace llvm {
     /// for the Value number.
     VNInfo *createValueCopy(const VNInfo *orig,
                             BumpPtrAllocator &VNInfoAllocator) {
-
       VNInfo *VNI =
         static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
                                                       alignof<VNInfo>()));
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 337ec1ce96..18c493823b 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -65,9 +65,6 @@ namespace llvm {
     AliasAnalysis *aa_;
     LiveVariables* lv_;
 
-
-    
-
     /// Special pool allocator for VNInfo's (LiveInterval val#).
     ///
     BumpPtrAllocator VNInfoAllocator;
@@ -94,9 +91,14 @@ namespace llvm {
 
     DenseMap<MachineBasicBlock*, MachineInstrIndex> terminatorGaps;
 
+    /// phiJoinCopies - Copy instructions which are PHI joins.
+    SmallVector<MachineInstr*, 16> phiJoinCopies;
+
+    /// allocatableRegs_ - A bit vector of allocatable registers.
     BitVector allocatableRegs_;
 
-    std::vector<MachineInstr*> ClonedMIs;
+    /// CloneMIs - A list of clones as result of re-materialization.
+    std::vector<MachineInstr*> CloneMIs;
 
     typedef LiveInterval::InstrSlots InstrSlots;
 
@@ -430,7 +432,14 @@ namespace llvm {
   private:      
     /// computeIntervals - Compute live intervals.
     void computeIntervals();
-    
+
+    bool isProfitableToCoalesce(LiveInterval &DstInt, LiveInterval &SrcInt,
+                                SmallVector<MachineInstr*,16> &IdentCopies,
+                                SmallVector<MachineInstr*,16> &OtherCopies,
+                                bool &HaveConflict);
+
+    void performEarlyCoalescing();
+
     /// handleRegisterDef - update intervals for a register def
     /// (calls handlePhysicalRegisterDef and
     /// handleVirtualRegisterDef)
@@ -560,7 +569,8 @@ namespace llvm {
 
     static LiveInterval* createInterval(unsigned Reg);
 
-    void printRegName(unsigned reg) const;
+    void printInstrs(raw_ostream &O) const;
+    void dumpInstrs() const;
   };
 } // End llvm namespace