LiveRangeCalc: Rewrite subrange calculation

This changes subrange calculation to calculate subranges sequentially
instead of in parallel. The code is easier to understand that way and
addresses the code review issues raised about LiveOutData being
hard to understand/needing more comments by removing them :)

llvm-svn: 224272

1 files changed, 44 insertions, 79 deletions

diff --git a/llvm/lib/CodeGen/LiveRangeCalc.h b/llvm/lib/CodeGen/LiveRangeCalc.h
index fd494797918..913d09edbdd 100644
--- a/llvm/lib/CodeGen/LiveRangeCalc.h
+++ b/llvm/lib/CodeGen/LiveRangeCalc.h
@@ -47,44 +47,30 @@ class LiveRangeCalc {
   /// LiveOutMap - Map basic blocks to the value leaving the block.
   typedef IndexedMap<LiveOutPair, MBB2NumberFunctor> LiveOutMap;
 
-  struct LiveOutData {
-    /// Seen - Bit vector of active entries in LiveOut, also used as a visited
-    /// set by findReachingDefs.  One entry per basic block, indexed by block
-    /// number.  This is kept as a separate bit vector because it can be cleared
-    /// quickly when switching live ranges.
-    BitVector Seen;
-
-    /// LiveOut - Map each basic block where a live range is live out to the
-    /// live-out value and its defining block.
-    ///
-    /// For every basic block, MBB, one of these conditions shall be true:
-    ///
-    ///  1. !Seen.count(MBB->getNumber())
-    ///     Blocks without a Seen bit are ignored.
-    ///  2. LiveOut[MBB].second.getNode() == MBB
-    ///     The live-out value is defined in MBB.
-    ///  3. forall P in preds(MBB): LiveOut[P] == LiveOut[MBB]
-    ///     The live-out value passses through MBB. All predecessors must carry
-    ///     the same value.
-    ///
-    /// The domtree node may be null, it can be computed.
-    ///
-    /// The map can be shared by multiple live ranges as long as no two are
-    /// live-out of the same block.
-    LiveOutMap Map;
-
-    void reset(unsigned NumBlocks) {
-      Seen.clear();
-      Seen.resize(NumBlocks);
-      Map.resize(NumBlocks);
-    }
-
-    void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI) {
-      Seen.set(MBB->getNumber());
-      Map[MBB] = LiveOutPair(VNI, nullptr);
-    }
-  };
-  LiveOutData MainLiveOutData;
+  /// Seen - Bit vector of active entries in LiveOut, also used as a visited
+  /// set by findReachingDefs.  One entry per basic block, indexed by block
+  /// number.  This is kept as a separate bit vector because it can be cleared
+  /// quickly when switching live ranges.
+  BitVector Seen;
+
+  /// LiveOut - Map each basic block where a live range is live out to the
+  /// live-out value and its defining block.
+  ///
+  /// For every basic block, MBB, one of these conditions shall be true:
+  ///
+  ///  1. !Seen.count(MBB->getNumber())
+  ///     Blocks without a Seen bit are ignored.
+  ///  2. LiveOut[MBB].second.getNode() == MBB
+  ///     The live-out value is defined in MBB.
+  ///  3. forall P in preds(MBB): LiveOut[P] == LiveOut[MBB]
+  ///     The live-out value passses through MBB. All predecessors must carry
+  ///     the same value.
+  ///
+  /// The domtree node may be null, it can be computed.
+  ///
+  /// The map can be shared by multiple live ranges as long as no two are
+  /// live-out of the same block.
+  LiveOutMap Map;
 
   /// LiveInBlock - Information about a basic block where a live range is known
   /// to be live-in, but the value has not yet been determined.
@@ -126,19 +112,24 @@ class LiveRangeCalc {
   ///
   /// PhysReg, when set, is used to verify live-in lists on basic blocks.
   bool findReachingDefs(LiveRange &LR, MachineBasicBlock &KillMBB,
-                        SlotIndex Kill, unsigned PhysReg,
-                        LiveOutData &LiveOuts);
+                        SlotIndex Kill, unsigned PhysReg);
 
   /// updateSSA - Compute the values that will be live in to all requested
   /// blocks in LiveIn.  Create PHI-def values as required to preserve SSA form.
   ///
   /// Every live-in block must be jointly dominated by the added live-out
   /// blocks.  No values are read from the live ranges.
-  void updateSSA(LiveOutData &LiveOuts);
+  void updateSSA();
 
   /// Transfer information from the LiveIn vector to the live ranges and update
   /// the given @p LiveOuts.
-  void updateFromLiveIns(LiveOutData &LiveOuts);
+  void updateFromLiveIns();
+
+  /// Extend the live range of @p LR to reach all uses of Reg.
+  ///
+  /// All uses must be jointly dominated by existing liveness.  PHI-defs are
+  /// inserted as needed to preserve SSA form.
+  void extendToUses(LiveRange &LR, unsigned Reg, unsigned LaneMask = ~0u);
 
 public:
   LiveRangeCalc() : MF(nullptr), MRI(nullptr), Indexes(nullptr),
@@ -176,39 +167,16 @@ public:
   /// single existing value, Alloc may be null.
   ///
   /// PhysReg, when set, is used to verify live-in lists on basic blocks.
-  void extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg,
-              LiveOutData &LiveOuts);
+  void extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg = 0);
 
-  void extend(LiveRange &LR, SlotIndex Kill) {
-    extend(LR, Kill, 0, MainLiveOutData);
-  }
-
-  /// createDeadDefs - Create a dead def in LI for every def operand of Reg.
-  /// Each instruction defining Reg gets a new VNInfo with a corresponding
-  /// minimal live range.
-  void createDeadDefs(LiveRange &LR, unsigned Reg);
+  /// Calculates liveness for the uses/defs of a given registers.  The results
+  /// are written to @p LR.
+  void calculate(LiveRange &LR, unsigned Reg, bool IgnoreUses);
 
-  /// Subregister aware version of createDeadDefs(LiveRange &LR, unsigned Reg).
-  /// If subregister liveness tracking is enabled new subranges are created as
-  /// necessary when subregister defs are found. As with
-  /// createDeadDefs(LiveRange &LR, unsigned Reg) new short live segments are
-  /// created for every def of LI.reg. The new segments start and end at the
-  /// defining instruction (hence the name "DeadDef").
-  void createDeadDefs(LiveInterval &LI);
-
-  /// extendToUses - Extend the live range of LI to reach all uses of Reg.
-  ///
-  /// All uses must be jointly dominated by existing liveness.  PHI-defs are
-  /// inserted as needed to preserve SSA form.
-  void extendToUses(LiveRange &LR, unsigned Reg);
-
-  /// Subregister aware version of extendToUses(LiveRange &LR, unsigned Reg).
-  /// If subregister liveness tracking is enabled new subranges are created
-  /// as necessary when subregister uses are found. As with
-  /// extendToUses(LiveRange &LR, unsigned Reg) the segments existing at the
-  /// defs are extend until they reach all uses. New value numbers are created
-  /// at CFG joins as necessary (SSA construction).
-  void extendToUses(LiveInterval &LI);
+  /// Calculates liveness for the register specified in live interval @p LI.
+  /// Creates subregister live ranges as needed if subreg liveness tracking is
+  /// enabled.
+  void calculate(LiveInterval &LI);
 
   //===--------------------------------------------------------------------===//
   // Low-level interface.
@@ -230,7 +198,8 @@ public:
   /// VNI may be null only if MBB is a live-through block also passed to
   /// addLiveInBlock().
   void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI) {
-    MainLiveOutData.setLiveOutValue(MBB, VNI);
+    Seen.set(MBB->getNumber());
+    Map[MBB] = LiveOutPair(VNI, nullptr);
   }
 
   /// addLiveInBlock - Add a block with an unknown live-in value.  This
@@ -255,11 +224,7 @@ public:
   ///
   /// Every predecessor of a live-in block must have been given a value with
   /// setLiveOutValue, the value may be null for live-trough blocks.
-  void calculateValues(LiveOutData &LiveOuts);
-
-  void calculateValues() {
-    calculateValues(MainLiveOutData);
-  }
+  void calculateValues();
 };
 
 } // end namespace llvm