Merge "Build live ranges in preparation for register allocation."
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index e9db47e..226df98 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -81,6 +81,7 @@
compiler/optimizing/find_loops_test.cc \
compiler/optimizing/linearize_test.cc \
compiler/optimizing/liveness_test.cc \
+ compiler/optimizing/live_ranges_test.cc \
compiler/optimizing/pretty_printer_test.cc \
compiler/optimizing/ssa_test.cc \
compiler/output_stream_test.cc \
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index 2c2564d..521992a 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -499,6 +499,7 @@
break;
}
+ case Instruction::MOVE_RESULT:
case Instruction::MOVE_RESULT_WIDE: {
UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
break;
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index b9c1164..52e3e37 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -18,6 +18,7 @@
#include "driver/dex_compilation_unit.h"
#include "nodes.h"
+#include "ssa_liveness_analysis.h"
namespace art {
@@ -102,6 +103,24 @@
}
output_ << "]";
}
+ if (instruction->GetLifetimePosition() != kNoLifetime) {
+ output_ << " (liveness: " << instruction->GetLifetimePosition();
+ if (instruction->HasLiveInterval()) {
+ output_ << " ";
+ const GrowableArray<LiveRange>& ranges = instruction->GetLiveInterval()->GetRanges();
+ size_t i = ranges.Size() - 1;
+ do {
+ output_ << "[" << ranges.Get(i).GetStart() << "," << ranges.Get(i).GetEnd() << "[";
+ if (i == 0) {
+ break;
+ } else {
+ --i;
+ output_ << ",";
+ }
+ } while (true);
+ }
+ output_ << ")";
+ }
}
void PrintInstructions(const HInstructionList& list) {
@@ -126,8 +145,14 @@
void VisitBasicBlock(HBasicBlock* block) {
StartTag("block");
PrintProperty("name", "B", block->GetBlockId());
- PrintInt("from_bci", -1);
- PrintInt("to_bci", -1);
+ if (block->GetLifetimeStart() != kNoLifetime) {
+ // Piggy back on these fields to show the lifetime of the block.
+ PrintInt("from_bci", block->GetLifetimeStart());
+ PrintInt("to_bci", block->GetLifetimeEnd());
+ } else {
+ PrintInt("from_bci", -1);
+ PrintInt("to_bci", -1);
+ }
PrintPredecessors(block);
PrintSuccessors(block);
PrintEmptyProperty("xhandlers");
diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
new file mode 100644
index 0000000..9849388
--- /dev/null
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -0,0 +1,263 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "builder.h"
+#include "dex_file.h"
+#include "dex_instruction.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "ssa_liveness_analysis.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static HGraph* BuildGraph(const uint16_t* data, ArenaAllocator* allocator) {
+ HGraphBuilder builder(allocator);
+ const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
+ HGraph* graph = builder.BuildGraph(*item);
+ graph->BuildDominatorTree();
+ graph->TransformToSSA();
+ graph->FindNaturalLoops();
+ return graph;
+}
+
+TEST(LiveRangesTest, CFG1) {
+ /*
+ * Test the following snippet:
+ * return 0;
+ *
+ * Which becomes the following graph (numbered by lifetime position):
+ * 2: constant0
+ * 3: goto
+ * |
+ * 6: return
+ * |
+ * 9: exit
+ */
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::RETURN);
+
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HGraph* graph = BuildGraph(data, &allocator);
+ SsaLivenessAnalysis liveness(*graph);
+ liveness.Analyze();
+
+ LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
+ ASSERT_EQ(1u, interval->GetRanges().Size());
+ LiveRange range = interval->GetRanges().Get(0);
+ ASSERT_EQ(2u, range.GetStart());
+ // Last use is the return instruction.
+ ASSERT_EQ(6u, range.GetEnd());
+ HBasicBlock* block = graph->GetBlocks().Get(1);
+ ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr);
+ ASSERT_EQ(6u, block->GetLastInstruction()->GetLifetimePosition());
+}
+
+TEST(LiveRangesTest, CFG2) {
+ /*
+ * Test the following snippet:
+ * var a = 0;
+ * if (0 == 0) {
+ * } else {
+ * }
+ * return a;
+ *
+ * Which becomes the following graph (numbered by lifetime position):
+ * 2: constant0
+ * 3: goto
+ * |
+ * 6: equal
+ * 7: if
+ * / \
+ * 10: goto 13: goto
+ * \ /
+ * 16: return
+ * |
+ * 19: exit
+ */
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0x100,
+ Instruction::RETURN | 0 << 8);
+
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HGraph* graph = BuildGraph(data, &allocator);
+ SsaLivenessAnalysis liveness(*graph);
+ liveness.Analyze();
+
+ LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
+ ASSERT_EQ(1u, interval->GetRanges().Size());
+ LiveRange range = interval->GetRanges().Get(0);
+ ASSERT_EQ(2u, range.GetStart());
+ // Last use is the return instruction.
+ ASSERT_EQ(16u, range.GetEnd());
+ HBasicBlock* block = graph->GetBlocks().Get(3);
+ ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr);
+ ASSERT_EQ(16u, block->GetLastInstruction()->GetLifetimePosition());
+}
+
+TEST(LiveRangesTest, CFG3) {
+ /*
+ * Test the following snippet:
+ * var a = 0;
+ * if (0 == 0) {
+ * } else {
+ * a = 4;
+ * }
+ * return a;
+ *
+ * Which becomes the following graph (numbered by lifetime position):
+ * 2: constant0
+ * 3: constant4
+ * 4: goto
+ * |
+ * 7: equal
+ * 8: if
+ * / \
+ * 11: goto 14: goto
+ * \ /
+ * 16: phi
+ * 17: return
+ * |
+ * 20: exit
+ */
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::RETURN | 0 << 8);
+
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HGraph* graph = BuildGraph(data, &allocator);
+ SsaLivenessAnalysis liveness(*graph);
+ liveness.Analyze();
+
+ // Test for the 0 constant.
+ LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
+ ASSERT_EQ(1u, interval->GetRanges().Size());
+ LiveRange range = interval->GetRanges().Get(0);
+ ASSERT_EQ(2u, range.GetStart());
+ // Last use is the phi at the return block so instruction is live until
+ // the end of the then block.
+ ASSERT_EQ(12u, range.GetEnd());
+
+ // Test for the 4 constant.
+ interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
+ // The then branch is a hole for this constant, therefore its interval has 2 ranges.
+ ASSERT_EQ(2u, interval->GetRanges().Size());
+ // First range is the else block.
+ range = interval->GetRanges().Get(0);
+ ASSERT_EQ(13u, range.GetStart());
+ // Last use is the phi at the return block.
+ ASSERT_EQ(15u, range.GetEnd());
+ // Second range starts from the definition and ends at the if block.
+ range = interval->GetRanges().Get(1);
+ ASSERT_EQ(3u, range.GetStart());
+ // 9 is the end of the if block.
+ ASSERT_EQ(9u, range.GetEnd());
+
+ // Test for the phi.
+ interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
+ ASSERT_EQ(1u, interval->GetRanges().Size());
+ range = interval->GetRanges().Get(0);
+ ASSERT_EQ(16u, range.GetStart());
+ ASSERT_EQ(17u, range.GetEnd());
+}
+
+TEST(LiveRangesTest, Loop) {
+ /*
+ * Test the following snippet:
+ * var a = 0;
+ * while (a == a) {
+ * a = 4;
+ * }
+ * return 5;
+ *
+ * Which becomes the following graph (numbered by lifetime position):
+ * 2: constant0
+ * 3: constant4
+ * 4: constant5
+ * 5: goto
+ * |
+ * 8: goto
+ * |
+ * 10: phi
+ * 11: equal
+ * 12: if +++++
+ * | \ +
+ * | 15: goto
+ * |
+ * 18: return
+ * |
+ * 21: exit
+ */
+
+ const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::GOTO | 0xFD00,
+ Instruction::CONST_4 | 5 << 12 | 1 << 8,
+ Instruction::RETURN | 1 << 8);
+
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HGraph* graph = BuildGraph(data, &allocator);
+ SsaLivenessAnalysis liveness(*graph);
+ liveness.Analyze();
+
+ // Test for the 0 constant.
+ LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
+ ASSERT_EQ(1u, interval->GetRanges().Size());
+ LiveRange range = interval->GetRanges().Get(0);
+ ASSERT_EQ(2u, range.GetStart());
+ // Last use is the loop phi so instruction is live until
+ // the end of the pre loop header.
+ ASSERT_EQ(9u, range.GetEnd());
+
+ // Test for the 4 constant.
+ interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
+ // The instruction is live until the end of the loop.
+ ASSERT_EQ(1u, interval->GetRanges().Size());
+ range = interval->GetRanges().Get(0);
+ ASSERT_EQ(3u, range.GetStart());
+ ASSERT_EQ(16u, range.GetEnd());
+
+ // Test for the 5 constant.
+ interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval();
+ // The instruction is live until the return instruction of the loop.
+ ASSERT_EQ(1u, interval->GetRanges().Size());
+ range = interval->GetRanges().Get(0);
+ ASSERT_EQ(4u, range.GetStart());
+ ASSERT_EQ(18u, range.GetEnd());
+
+ // Test for the phi.
+ interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
+ ASSERT_EQ(1u, interval->GetRanges().Size());
+ range = interval->GetRanges().Get(0);
+ // Instruction is consumed by the if.
+ ASSERT_EQ(10u, range.GetStart());
+ ASSERT_EQ(11u, range.GetEnd());
+}
+
+} // namespace art
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 1085c10..a2cb1c4 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -29,6 +29,7 @@
class HIntConstant;
class HGraphVisitor;
class HPhi;
+class LiveInterval;
class LocationSummary;
static const int kDefaultNumberOfBlocks = 8;
@@ -223,6 +224,8 @@
DISALLOW_COPY_AND_ASSIGN(HLoopInformation);
};
+static constexpr size_t kNoLifetime = -1;
+
// A block in a method. Contains the list of instructions represented
// as a double linked list. Each block knows its predecessors and
// successors.
@@ -234,7 +237,9 @@
successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
loop_information_(nullptr),
dominator_(nullptr),
- block_id_(-1) { }
+ block_id_(-1),
+ lifetime_start_(kNoLifetime),
+ lifetime_end_(kNoLifetime) {}
const GrowableArray<HBasicBlock*>& GetPredecessors() const {
return predecessors_;
@@ -299,6 +304,15 @@
block->successors_.Add(this);
}
+ size_t GetPredecessorIndexOf(HBasicBlock* predecessor) {
+ for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) {
+ if (predecessors_.Get(i) == predecessor) {
+ return i;
+ }
+ }
+ return -1;
+ }
+
void AddInstruction(HInstruction* instruction);
void RemoveInstruction(HInstruction* instruction);
void AddPhi(HPhi* phi);
@@ -334,6 +348,12 @@
// Returns wheter this block dominates the blocked passed as parameter.
bool Dominates(HBasicBlock* block) const;
+ size_t GetLifetimeStart() const { return lifetime_start_; }
+ size_t GetLifetimeEnd() const { return lifetime_end_; }
+
+ void SetLifetimeStart(size_t start) { lifetime_start_ = start; }
+ void SetLifetimeEnd(size_t end) { lifetime_end_ = end; }
+
private:
HGraph* const graph_;
GrowableArray<HBasicBlock*> predecessors_;
@@ -343,6 +363,8 @@
HLoopInformation* loop_information_;
HBasicBlock* dominator_;
int block_id_;
+ size_t lifetime_start_;
+ size_t lifetime_end_;
DISALLOW_COPY_AND_ASSIGN(HBasicBlock);
};
@@ -407,7 +429,9 @@
uses_(nullptr),
env_uses_(nullptr),
environment_(nullptr),
- locations_(nullptr) { }
+ locations_(nullptr),
+ live_interval_(nullptr),
+ lifetime_position_(kNoLifetime) {}
virtual ~HInstruction() { }
@@ -477,6 +501,12 @@
FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
#undef INSTRUCTION_TYPE_CHECK
+ size_t GetLifetimePosition() const { return lifetime_position_; }
+ void SetLifetimePosition(size_t position) { lifetime_position_ = position; }
+ LiveInterval* GetLiveInterval() const { return live_interval_; }
+ void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; }
+ bool HasLiveInterval() const { return live_interval_ != nullptr; }
+
private:
HInstruction* previous_;
HInstruction* next_;
@@ -501,6 +531,13 @@
// Set by the code generator.
LocationSummary* locations_;
+ // Set by the liveness analysis.
+ LiveInterval* live_interval_;
+
+ // Set by the liveness analysis, this is the position in a linear
+ // order of blocks where this instruction's live interval start.
+ size_t lifetime_position_;
+
friend class HBasicBlock;
friend class HInstructionList;
@@ -596,6 +633,8 @@
private:
HInstruction* instruction_;
HInstruction* next_;
+
+ DISALLOW_COPY_AND_ASSIGN(HInstructionIterator);
};
class HBackwardInstructionIterator : public ValueObject {
@@ -615,6 +654,8 @@
private:
HInstruction* instruction_;
HInstruction* next_;
+
+ DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator);
};
// An embedded container with N elements of type T. Used (with partial
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index f435cb0..286f48a 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -129,6 +129,7 @@
graph->FindNaturalLoops();
SsaLivenessAnalysis(*graph).Analyze();
+ visualizer.DumpGraph("liveness");
return new CompiledMethod(GetCompilerDriver(),
instruction_set,
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 85171aa..0f16ad2 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -22,7 +22,7 @@
void SsaLivenessAnalysis::Analyze() {
LinearizeGraph();
NumberInstructions();
- ComputeSets();
+ ComputeLiveness();
}
static bool IsLoopExit(HLoopInformation* current, HLoopInformation* to) {
@@ -96,6 +96,22 @@
DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator);
};
+class HLinearPostOrderIterator : public ValueObject {
+ public:
+ explicit HLinearPostOrderIterator(const GrowableArray<HBasicBlock*>& post_order)
+ : post_order_(post_order), index_(0) {}
+
+ bool Done() const { return index_ == post_order_.Size(); }
+ HBasicBlock* Current() const { return post_order_.Get(index_); }
+ void Advance() { ++index_; }
+
+ private:
+ const GrowableArray<HBasicBlock*>& post_order_;
+ size_t index_;
+
+ DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator);
+};
+
void SsaLivenessAnalysis::LinearizeGraph() {
// For simplicity of the implementation, we create post linear order. The order for
// computing live ranges is the reverse of that order.
@@ -105,27 +121,41 @@
void SsaLivenessAnalysis::NumberInstructions() {
int ssa_index = 0;
+ size_t lifetime_position = 0;
+ // Each instruction gets an individual lifetime position, and a block gets a lifetime
+ // start and end position. Non-phi instructions have a distinct lifetime position than
+ // the block they are in. Phi instructions have the lifetime start of their block as
+ // lifetime position
for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
+ block->SetLifetimeStart(++lifetime_position);
for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
if (current->HasUses()) {
+ instructions_from_ssa_index_.Add(current);
current->SetSsaIndex(ssa_index++);
+ current->SetLiveInterval(new (graph_.GetArena()) LiveInterval(graph_.GetArena()));
}
+ current->SetLifetimePosition(lifetime_position);
}
for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
if (current->HasUses()) {
+ instructions_from_ssa_index_.Add(current);
current->SetSsaIndex(ssa_index++);
+ current->SetLiveInterval(new (graph_.GetArena()) LiveInterval(graph_.GetArena()));
}
+ current->SetLifetimePosition(++lifetime_position);
}
+
+ block->SetLifetimeEnd(++lifetime_position);
}
number_of_ssa_values_ = ssa_index;
}
-void SsaLivenessAnalysis::ComputeSets() {
+void SsaLivenessAnalysis::ComputeLiveness() {
for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
block_infos_.Put(
@@ -133,9 +163,10 @@
new (graph_.GetArena()) BlockInfo(graph_.GetArena(), *block, number_of_ssa_values_));
}
- // Compute the initial live_in, live_out, and kill sets. This method does not handle
- // backward branches, therefore live_in and live_out sets are not yet correct.
- ComputeInitialSets();
+ // Compute the live ranges, as well as the initial live_in, live_out, and kill sets.
+ // This method does not handle backward branches for the sets, therefore live_in
+ // and live_out sets are not yet correct.
+ ComputeLiveRanges();
// Do a fixed point calculation to take into account backward branches,
// that will update live_in of loop headers, and therefore live_out and live_in
@@ -143,26 +174,71 @@
ComputeLiveInAndLiveOutSets();
}
-void SsaLivenessAnalysis::ComputeInitialSets() {
- // Do a post orderr visit, adding inputs of instructions live in the block where
+class InstructionBitVectorIterator : public ValueObject {
+ public:
+ InstructionBitVectorIterator(const BitVector& vector,
+ const GrowableArray<HInstruction*>& instructions)
+ : instructions_(instructions),
+ iterator_(BitVector::Iterator(&vector)),
+ current_bit_index_(iterator_.Next()) {}
+
+ bool Done() const { return current_bit_index_ == -1; }
+ HInstruction* Current() const { return instructions_.Get(current_bit_index_); }
+ void Advance() {
+ current_bit_index_ = iterator_.Next();
+ }
+
+ private:
+ const GrowableArray<HInstruction*> instructions_;
+ BitVector::Iterator iterator_;
+ int32_t current_bit_index_;
+
+ DISALLOW_COPY_AND_ASSIGN(InstructionBitVectorIterator);
+};
+
+void SsaLivenessAnalysis::ComputeLiveRanges() {
+ // Do a post order visit, adding inputs of instructions live in the block where
// that instruction is defined, and killing instructions that are being visited.
- for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+ for (HLinearPostOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
BitVector* kill = GetKillSet(*block);
BitVector* live_in = GetLiveInSet(*block);
+ // Set phi inputs of successors of this block corresponding to this block
+ // as live_in.
+ for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
+ HBasicBlock* successor = block->GetSuccessors().Get(i);
+ live_in->Union(GetLiveInSet(*successor));
+ size_t phi_input_index = successor->GetPredecessorIndexOf(block);
+ for (HInstructionIterator it(successor->GetPhis()); !it.Done(); it.Advance()) {
+ HInstruction* input = it.Current()->InputAt(phi_input_index);
+ live_in->SetBit(input->GetSsaIndex());
+ }
+ }
+
+ // Add a range that covers this block to all instructions live_in because of successors.
+ for (InstructionBitVectorIterator it(*live_in, instructions_from_ssa_index_);
+ !it.Done();
+ it.Advance()) {
+ it.Current()->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd());
+ }
+
for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
if (current->HasSsaIndex()) {
+ // Kill the instruction and shorten its interval.
kill->SetBit(current->GetSsaIndex());
live_in->ClearBit(current->GetSsaIndex());
+ current->GetLiveInterval()->SetFrom(current->GetLifetimePosition());
}
// All inputs of an instruction must be live.
for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
- DCHECK(current->InputAt(i)->HasSsaIndex());
- live_in->SetBit(current->InputAt(i)->GetSsaIndex());
+ HInstruction* input = current->InputAt(i);
+ DCHECK(input->HasSsaIndex());
+ live_in->SetBit(input->GetSsaIndex());
+ input->GetLiveInterval()->AddUse(current);
}
if (current->HasEnvironment()) {
@@ -173,32 +249,30 @@
if (instruction != nullptr) {
DCHECK(instruction->HasSsaIndex());
live_in->SetBit(instruction->GetSsaIndex());
+ instruction->GetLiveInterval()->AddUse(current);
}
}
}
}
+ // Kill phis defined in this block.
for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
if (current->HasSsaIndex()) {
kill->SetBit(current->GetSsaIndex());
live_in->ClearBit(current->GetSsaIndex());
}
+ }
- // Mark a phi input live_in for its corresponding predecessor.
- for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
- HInstruction* input = current->InputAt(i);
-
- HBasicBlock* predecessor = block->GetPredecessors().Get(i);
- size_t ssa_index = input->GetSsaIndex();
- BitVector* predecessor_kill = GetKillSet(*predecessor);
- BitVector* predecessor_live_in = GetLiveInSet(*predecessor);
-
- // Phi inputs from a back edge have already been visited. If the back edge
- // block defines that input, we should not add it to its live_in.
- if (!predecessor_kill->IsBitSet(ssa_index)) {
- predecessor_live_in->SetBit(ssa_index);
- }
+ if (block->IsLoopHeader()) {
+ HBasicBlock* back_edge = block->GetLoopInformation()->GetBackEdges().Get(0);
+ // For all live_in instructions at the loop header, we need to create a range
+ // that covers the full loop.
+ for (InstructionBitVectorIterator it(*live_in, instructions_from_ssa_index_);
+ !it.Done();
+ it.Advance()) {
+ it.Current()->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(),
+ back_edge->GetLifetimeEnd());
}
}
}
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 @@
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 @@
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 @@
// 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 @@
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);