Build live ranges in preparation for register allocation.

Change-Id: I7ae24afaa4e49276136bf34f4ba7d62db7f28c01

1 files changed, 104 insertions, 6 deletions

diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index b8695ba..2d91436 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -44,12 +44,104 @@ class BlockInfo : public ArenaObject {
   DISALLOW_COPY_AND_ASSIGN(BlockInfo);
 };
 
+/**
+ * A live range contains the start and end of a range where an instruction
+ * is live.
+ */
+class LiveRange : public ValueObject {
+ public:
+  LiveRange(size_t start, size_t end) : start_(start), end_(end) {
+    DCHECK_LT(start, end);
+  }
+
+  size_t GetStart() const { return start_; }
+  size_t GetEnd() const { return end_; }
+
+ private:
+  size_t start_;
+  size_t end_;
+};
+
+static constexpr int kDefaultNumberOfRanges = 3;
+
+/**
+ * An interval is a list of disjoint live ranges where an instruction is live.
+ * Each instruction that has uses gets an interval.
+ */
+class LiveInterval : public ArenaObject {
+ public:
+  explicit LiveInterval(ArenaAllocator* allocator) : ranges_(allocator, kDefaultNumberOfRanges) {}
+
+  void AddUse(HInstruction* instruction) {
+    size_t position = instruction->GetLifetimePosition();
+    size_t start_block_position = instruction->GetBlock()->GetLifetimeStart();
+    size_t end_block_position = instruction->GetBlock()->GetLifetimeEnd();
+    if (ranges_.IsEmpty()) {
+      // First time we see a use of that interval.
+      ranges_.Add(LiveRange(start_block_position, position));
+    } else if (ranges_.Peek().GetStart() == start_block_position) {
+      // There is a use later in the same block.
+      DCHECK_LE(position, ranges_.Peek().GetEnd());
+    } else if (ranges_.Peek().GetStart() == end_block_position + 1) {
+      // Last use is in a following block.
+      LiveRange existing = ranges_.Pop();
+      ranges_.Add(LiveRange(start_block_position, existing.GetEnd()));
+    } else {
+      // There is a hole in the interval. Create a new range.
+      ranges_.Add(LiveRange(start_block_position, position));
+    }
+  }
+
+  void AddRange(size_t start, size_t end) {
+    if (ranges_.IsEmpty()) {
+      ranges_.Add(LiveRange(start, end));
+    } else if (ranges_.Peek().GetStart() == end + 1) {
+      // There is a use in the following block.
+      LiveRange existing = ranges_.Pop();
+      ranges_.Add(LiveRange(start, existing.GetEnd()));
+    } else {
+      // There is a hole in the interval. Create a new range.
+      ranges_.Add(LiveRange(start, end));
+    }
+  }
+
+  void AddLoopRange(size_t start, size_t end) {
+    DCHECK(!ranges_.IsEmpty());
+    while (!ranges_.IsEmpty() && ranges_.Peek().GetEnd() < end) {
+      DCHECK_LE(start, ranges_.Peek().GetStart());
+      ranges_.Pop();
+    }
+    if (ranges_.IsEmpty()) {
+      // Uses are only in the loop.
+      ranges_.Add(LiveRange(start, end));
+    } else {
+      // There are uses after the loop.
+      LiveRange range = ranges_.Pop();
+      ranges_.Add(LiveRange(start, range.GetEnd()));
+    }
+  }
+
+  void SetFrom(size_t from) {
+    DCHECK(!ranges_.IsEmpty());
+    LiveRange existing = ranges_.Pop();
+    ranges_.Add(LiveRange(from, existing.GetEnd()));
+  }
+
+  const GrowableArray<LiveRange>& GetRanges() const { return ranges_; }
+
+ private:
+  GrowableArray<LiveRange> ranges_;
+
+  DISALLOW_COPY_AND_ASSIGN(LiveInterval);
+};
+
 class SsaLivenessAnalysis : public ValueObject {
  public:
   explicit SsaLivenessAnalysis(const HGraph& graph)
       : graph_(graph),
         linear_post_order_(graph.GetArena(), graph.GetBlocks().Size()),
         block_infos_(graph.GetArena(), graph.GetBlocks().Size()),
+        instructions_from_ssa_index_(graph.GetArena(), 0),
         number_of_ssa_values_(0) {
     block_infos_.SetSize(graph.GetBlocks().Size());
   }
@@ -72,6 +164,10 @@ class SsaLivenessAnalysis : public ValueObject {
     return linear_post_order_;
   }
 
+  HInstruction* GetInstructionFromSsaIndex(size_t index) {
+    return instructions_from_ssa_index_.Get(index);
+  }
+
  private:
   // Linearize the graph so that:
   // (1): a block is always after its dominator,
@@ -79,15 +175,16 @@ class SsaLivenessAnalysis : public ValueObject {
   // This creates a natural and efficient ordering when visualizing live ranges.
   void LinearizeGraph();
 
-  // Give an SSA number to each instruction that defines a value used by another instruction.
+  // Give an SSA number to each instruction that defines a value used by another instruction,
+  // and setup the lifetime information of each instruction and block.
   void NumberInstructions();
 
-  // Compute live_in, live_out and kill sets.
-  void ComputeSets();
+  // Compute live ranges of instructions, as well as live_in, live_out and kill sets.
+  void ComputeLiveness();
 
-  // Compute the initial live_in, live_out and kill sets, without analyzing
-  // backward branches.
-  void ComputeInitialSets();
+  // Compute the live ranges of instructions, as well as the initial live_in, live_out and
+  // kill sets, that do not take into account backward branches.
+  void ComputeLiveRanges();
 
   // After computing the initial sets, this method does a fixed point
   // calculation over the live_in and live_out set to take into account
@@ -103,6 +200,7 @@ class SsaLivenessAnalysis : public ValueObject {
   const HGraph& graph_;
   GrowableArray<HBasicBlock*> linear_post_order_;
   GrowableArray<BlockInfo*> block_infos_;
+  GrowableArray<HInstruction*> instructions_from_ssa_index_;
   size_t number_of_ssa_values_;
 
   DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);