Fix the computation of linear ordering.
The register allocator makes assumptions on the order, and
we ended up not computing the right one. The algorithm worked
fine when the loop header is the block branching to the exit,
but in the presence of breaks or do/while, it was incorrect.
Change-Id: Iad0a89872cd3f7b7a8b2bdf560f0d03493f93ba5
diff --git a/compiler/optimizing/linearize_test.cc b/compiler/optimizing/linearize_test.cc
index 6dd4207..c49cf7e 100644
--- a/compiler/optimizing/linearize_test.cc
+++ b/compiler/optimizing/linearize_test.cc
@@ -50,10 +50,9 @@
SsaLivenessAnalysis liveness(*graph, &codegen);
liveness.Analyze();
- ASSERT_EQ(liveness.GetLinearPostOrder().Size(), number_of_blocks);
+ ASSERT_EQ(liveness.GetLinearOrder().Size(), number_of_blocks);
for (size_t i = 0; i < number_of_blocks; ++i) {
- ASSERT_EQ(liveness.GetLinearPostOrder().Get(number_of_blocks - i - 1)->GetBlockId(),
- expected_order[i]);
+ ASSERT_EQ(liveness.GetLinearOrder().Get(i)->GetBlockId(), expected_order[i]);
}
}
@@ -194,4 +193,58 @@
TestCode(data, blocks, 12);
}
+TEST(LinearizeTest, CFG6) {
+ // Block0
+ // |
+ // Block1
+ // |
+ // Block2 ++++++++++++++
+ // | +
+ // Block3 +
+ // / \ +
+ // Block8 Block4 +
+ // | / \ +
+ // Block5 <- Block9 Block6 +
+ // |
+ // Block7
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::GOTO | 0x0100,
+ Instruction::IF_EQ, 0x0004,
+ Instruction::IF_EQ, 0x0003,
+ Instruction::RETURN_VOID,
+ Instruction::GOTO | 0xFA00);
+
+ const int blocks[] = {0, 1, 2, 3, 4, 6, 9, 8, 5, 7};
+ TestCode(data, blocks, arraysize(blocks));
+}
+
+TEST(LinearizeTest, CFG7) {
+ // Structure of this graph (+ are back edges)
+ // Block0
+ // |
+ // Block1
+ // |
+ // Block2 ++++++++
+ // | +
+ // Block3 +
+ // / \ +
+ // Block4 Block8 +
+ // / \ | +
+ // Block5 Block9 - Block6 +
+ // |
+ // Block7
+ //
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::GOTO | 0x0100,
+ Instruction::IF_EQ, 0x0005,
+ Instruction::IF_EQ, 0x0003,
+ Instruction::RETURN_VOID,
+ Instruction::GOTO | 0xFA00);
+
+ const int blocks[] = {0, 1, 2, 3, 4, 9, 8, 6, 5, 7};
+ TestCode(data, blocks, arraysize(blocks));
+}
+
} // namespace art
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 7d52d7d..19cd120 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -233,7 +233,7 @@
return false;
}
- int NumberOfBackEdges() const {
+ size_t NumberOfBackEdges() const {
return back_edges_.Size();
}
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 0085b27..54eb581 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -28,11 +28,6 @@
ComputeLiveness();
}
-static bool IsLoopExit(HLoopInformation* current, HLoopInformation* to) {
- // `to` is either not part of a loop, or `current` is an inner loop of `to`.
- return to == nullptr || (current != to && current->IsIn(*to));
-}
-
static bool IsLoop(HLoopInformation* info) {
return info != nullptr;
}
@@ -48,46 +43,65 @@
&& inner->IsIn(*outer);
}
-static void VisitBlockForLinearization(HBasicBlock* block,
- GrowableArray<HBasicBlock*>* order,
- ArenaBitVector* visited) {
- if (visited->IsBitSet(block->GetBlockId())) {
- return;
- }
- visited->SetBit(block->GetBlockId());
- size_t number_of_successors = block->GetSuccessors().Size();
- if (number_of_successors == 0) {
- // Nothing to do.
- } else if (number_of_successors == 1) {
- VisitBlockForLinearization(block->GetSuccessors().Get(0), order, visited);
- } else {
- DCHECK_EQ(number_of_successors, 2u);
- HBasicBlock* first_successor = block->GetSuccessors().Get(0);
- HBasicBlock* second_successor = block->GetSuccessors().Get(1);
- HLoopInformation* my_loop = block->GetLoopInformation();
- HLoopInformation* first_loop = first_successor->GetLoopInformation();
- HLoopInformation* second_loop = second_successor->GetLoopInformation();
-
- if (!IsLoop(my_loop)) {
- // Nothing to do. Current order is fine.
- } else if (IsLoopExit(my_loop, second_loop) && InSameLoop(my_loop, first_loop)) {
- // Visit the loop exit first in post order.
- std::swap(first_successor, second_successor);
- } else if (IsInnerLoop(my_loop, first_loop) && !IsInnerLoop(my_loop, second_loop)) {
- // Visit the inner loop last in post order.
- std::swap(first_successor, second_successor);
+static void AddToListForLinearization(GrowableArray<HBasicBlock*>* worklist, HBasicBlock* block) {
+ size_t insert_at = worklist->Size();
+ HLoopInformation* block_loop = block->GetLoopInformation();
+ for (; insert_at > 0; --insert_at) {
+ HBasicBlock* current = worklist->Get(insert_at - 1);
+ HLoopInformation* current_loop = current->GetLoopInformation();
+ if (InSameLoop(block_loop, current_loop)
+ || !IsLoop(current_loop)
+ || IsInnerLoop(current_loop, block_loop)) {
+ // The block can be processed immediately.
+ break;
}
- VisitBlockForLinearization(first_successor, order, visited);
- VisitBlockForLinearization(second_successor, order, visited);
}
- order->Add(block);
+ worklist->InsertAt(insert_at, block);
}
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.
- ArenaBitVector visited(graph_.GetArena(), graph_.GetBlocks().Size(), false);
- VisitBlockForLinearization(graph_.GetEntryBlock(), &linear_post_order_, &visited);
+ // Create a reverse post ordering with the following properties:
+ // - Blocks in a loop are consecutive,
+ // - Back-edge is the last block before loop exits.
+
+ // (1): Record the number of forward predecessors for each block. This is to
+ // ensure the resulting order is reverse post order. We could use the
+ // current reverse post order in the graph, but it would require making
+ // order queries to a GrowableArray, which is not the best data structure
+ // for it.
+ GrowableArray<uint32_t> forward_predecessors(graph_.GetArena(), graph_.GetBlocks().Size());
+ forward_predecessors.SetSize(graph_.GetBlocks().Size());
+ for (size_t i = 0, e = graph_.GetBlocks().Size(); i < e; ++i) {
+ HBasicBlock* block = graph_.GetBlocks().Get(i);
+ size_t number_of_forward_predecessors = block->GetPredecessors().Size();
+ if (block->IsLoopHeader()) {
+ // We rely on having simplified the CFG.
+ DCHECK_EQ(1u, block->GetLoopInformation()->NumberOfBackEdges());
+ number_of_forward_predecessors--;
+ }
+ forward_predecessors.Put(block->GetBlockId(), number_of_foward_predecessors);
+ }
+
+ // (2): Following a worklist approach, first start with the entry block, and
+ // iterate over the successors. When all non-back edge predecessors of a
+ // successor block are visited, the successor block is added in the worklist
+ // following an order that satisfies the requirements to build our linear graph.
+ GrowableArray<HBasicBlock*> worklist(graph_.GetArena(), 1);
+ worklist.Add(graph_.GetEntryBlock());
+ do {
+ HBasicBlock* current = worklist.Pop();
+ linear_order_.Add(current);
+ for (size_t i = 0, e = current->GetSuccessors().Size(); i < e; ++i) {
+ HBasicBlock* successor = current->GetSuccessors().Get(i);
+ int block_id = successor->GetBlockId();
+ size_t number_of_remaining_predecessors = forward_predecessors.Get(block_id);
+ if (number_of_remaining_predecessors == 1) {
+ AddToListForLinearization(&worklist, successor);
+ } else {
+ forward_predecessors.Put(block_id, number_of_remaining_predecessors - 1);
+ }
+ }
+ } while (!worklist.IsEmpty());
}
void SsaLivenessAnalysis::NumberInstructions() {
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index ca08d5b..46cea6d 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -582,7 +582,7 @@
SsaLivenessAnalysis(const HGraph& graph, CodeGenerator* codegen)
: graph_(graph),
codegen_(codegen),
- linear_post_order_(graph.GetArena(), graph.GetBlocks().Size()),
+ linear_order_(graph.GetArena(), graph.GetBlocks().Size()),
block_infos_(graph.GetArena(), graph.GetBlocks().Size()),
instructions_from_ssa_index_(graph.GetArena(), 0),
instructions_from_lifetime_position_(graph.GetArena(), 0),
@@ -604,8 +604,8 @@
return &block_infos_.Get(block.GetBlockId())->kill_;
}
- const GrowableArray<HBasicBlock*>& GetLinearPostOrder() const {
- return linear_post_order_;
+ const GrowableArray<HBasicBlock*>& GetLinearOrder() const {
+ return linear_order_;
}
HInstruction* GetInstructionFromSsaIndex(size_t index) const {
@@ -661,7 +661,7 @@
const HGraph& graph_;
CodeGenerator* const codegen_;
- GrowableArray<HBasicBlock*> linear_post_order_;
+ GrowableArray<HBasicBlock*> linear_order_;
GrowableArray<BlockInfo*> block_infos_;
// Temporary array used when computing live_in, live_out, and kill sets.
@@ -674,38 +674,38 @@
DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);
};
-class HLinearOrderIterator : public ValueObject {
- public:
- explicit HLinearOrderIterator(const SsaLivenessAnalysis& liveness)
- : post_order_(liveness.GetLinearPostOrder()), index_(liveness.GetLinearPostOrder().Size()) {}
-
- bool Done() const { return index_ == 0; }
- HBasicBlock* Current() const { return post_order_.Get(index_ -1); }
- void Advance() { --index_; DCHECK_GE(index_, 0U); }
-
- private:
- const GrowableArray<HBasicBlock*>& post_order_;
- size_t index_;
-
- DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator);
-};
-
class HLinearPostOrderIterator : public ValueObject {
public:
explicit HLinearPostOrderIterator(const SsaLivenessAnalysis& liveness)
- : post_order_(liveness.GetLinearPostOrder()), index_(0) {}
+ : order_(liveness.GetLinearOrder()), index_(liveness.GetLinearOrder().Size()) {}
- bool Done() const { return index_ == post_order_.Size(); }
- HBasicBlock* Current() const { return post_order_.Get(index_); }
- void Advance() { ++index_; }
+ bool Done() const { return index_ == 0; }
+ HBasicBlock* Current() const { return order_.Get(index_ -1); }
+ void Advance() { --index_; DCHECK_GE(index_, 0U); }
private:
- const GrowableArray<HBasicBlock*>& post_order_;
+ const GrowableArray<HBasicBlock*>& order_;
size_t index_;
DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator);
};
+class HLinearOrderIterator : public ValueObject {
+ public:
+ explicit HLinearOrderIterator(const SsaLivenessAnalysis& liveness)
+ : order_(liveness.GetLinearOrder()), index_(0) {}
+
+ bool Done() const { return index_ == order_.Size(); }
+ HBasicBlock* Current() const { return order_.Get(index_); }
+ void Advance() { ++index_; }
+
+ private:
+ const GrowableArray<HBasicBlock*>& order_;
+ size_t index_;
+
+ DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator);
+};
+
} // namespace art
#endif // ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_