Defer SplitKit value mapping until all defs are available.

The greedy register allocator revealed some problems with the value mapping in
SplitKit. We would sometimes start mapping values before all defs were known,
and that could change a value from a simple 1-1 mapping to a multi-def mapping
that requires ssa update.

The new approach collects all defs and register assignments first without
filling in any live intervals. Only when finish() is called, do we compute
liveness and mapped values. At this time we know with certainty which values map
to multiple values in a split range.

This also has the advantage that we can compute live ranges based on the
remaining uses after rematerializing at split points.

The current implementation has many opportunities for compile time optimization.

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

1 files changed, 36 insertions, 27 deletions

diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index bb4fca9084..5e9b96b629 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -13,11 +13,13 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/CodeGen/SlotIndexes.h"
 
 namespace llvm {
 
+class ConnectedVNInfoEqClasses;
 class LiveInterval;
 class LiveIntervals;
 class LiveRangeEdit;
@@ -263,6 +265,10 @@ public:
   /// with defValue.
   bool isComplexMapped(const VNInfo *ParentVNI) const;
 
+  /// markComplexMapped - Mark ParentVNI as complex mapped regardless of the
+  /// number of definitions.
+  void markComplexMapped(const VNInfo *ParentVNI) { Values[ParentVNI] = 0; }
+
   // addSimpleRange - Add a simple range from ParentLI to LI.
   // ParentVNI must be live in the [Start;End) interval.
   void addSimpleRange(SlotIndex Start, SlotIndex End, const VNInfo *ParentVNI);
@@ -290,49 +296,49 @@ class SplitEditor {
   LiveIntervals &LIS;
   VirtRegMap &VRM;
   MachineRegisterInfo &MRI;
+  MachineDominatorTree &MDT;
   const TargetInstrInfo &TII;
   const TargetRegisterInfo &TRI;
 
   /// Edit - The current parent register and new intervals created.
   LiveRangeEdit &Edit;
 
-  /// DupLI - Created as a copy of CurLI, ranges are carved out as new
-  /// intervals get added through openIntv / closeIntv. This is used to avoid
-  /// editing CurLI.
-  LiveIntervalMap DupLI;
+  /// Index into Edit of the currently open interval.
+  /// The index 0 is used for the complement, so the first interval started by
+  /// openIntv will be 1.
+  unsigned OpenIdx;
+
+  typedef IntervalMap<SlotIndex, unsigned> RegAssignMap;
+
+  /// Allocator for the interval map. This will eventually be shared with
+  /// SlotIndexes and LiveIntervals.
+  RegAssignMap::Allocator Allocator;
+
+  /// RegAssign - Map of the assigned register indexes.
+  /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at
+  /// Idx.
+  RegAssignMap RegAssign;
 
-  /// Currently open LiveInterval.
-  LiveIntervalMap OpenLI;
+  /// LIMappers - One LiveIntervalMap or each interval in Edit.
+  SmallVector<LiveIntervalMap, 4> LIMappers;
 
   /// defFromParent - Define Reg from ParentVNI at UseIdx using either
   /// rematerialization or a COPY from parent. Return the new value.
-  VNInfo *defFromParent(LiveIntervalMap &Reg,
+  VNInfo *defFromParent(unsigned RegIdx,
                         VNInfo *ParentVNI,
                         SlotIndex UseIdx,
                         MachineBasicBlock &MBB,
                         MachineBasicBlock::iterator I);
 
-  /// intervalsLiveAt - Return true if any member of intervals_ is live at Idx.
-  bool intervalsLiveAt(SlotIndex Idx) const;
+  /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers.
+  void rewriteAssigned();
 
-  /// Values in CurLI whose live range has been truncated when entering an open
-  /// li.
-  SmallPtrSet<const VNInfo*, 8> truncatedValues;
-
-  /// addTruncSimpleRange - Add the given simple range to DupLI after
-  /// truncating any overlap with intervals_.
-  void addTruncSimpleRange(SlotIndex Start, SlotIndex End, VNInfo *VNI);
-
-  /// criticalPreds_ - Set of basic blocks where both dupli and OpenLI should be
-  /// live out because of a critical edge.
-  SplitAnalysis::BlockPtrSet criticalPreds_;
-
-  /// computeRemainder - Compute the dupli liveness as the complement of all the
-  /// new intervals.
-  void computeRemainder();
-
-  /// rewrite - Rewrite all uses of reg to use the new registers.
-  void rewrite(unsigned reg);
+  /// rewriteComponents - Rewrite all uses of Intv[0] according to the eq
+  /// classes in ConEQ.
+  /// This must be done when Intvs[0] is styill live at all uses, before calling
+  /// ConEq.Distribute().
+  void rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs,
+                         const ConnectedVNInfoEqClasses &ConEq);
 
 public:
   /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
@@ -374,6 +380,9 @@ public:
   /// remaining live range, and rewrite instructions to use the new registers.
   void finish();
 
+  /// dump - print the current interval maping to dbgs().
+  void dump() const;
+
   // ===--- High level methods ---===
 
   /// splitAroundLoop - Split CurLI into a separate live interval inside