Revert "Fix the computation of linear ordering."
Build is broken.
This reverts commit 3054a90063d379ab8c9e5a42a7daf0d644b48b07.
Change-Id: I259bc2bd6a58e30391b8176f3db5fdb5c07e4d6d
diff --git a/compiler/optimizing/linearize_test.cc b/compiler/optimizing/linearize_test.cc
index c49cf7e..6dd4207 100644
--- a/compiler/optimizing/linearize_test.cc
+++ b/compiler/optimizing/linearize_test.cc
@@ -50,9 +50,10 @@
SsaLivenessAnalysis liveness(*graph, &codegen);
liveness.Analyze();
- ASSERT_EQ(liveness.GetLinearOrder().Size(), number_of_blocks);
+ ASSERT_EQ(liveness.GetLinearPostOrder().Size(), number_of_blocks);
for (size_t i = 0; i < number_of_blocks; ++i) {
- ASSERT_EQ(liveness.GetLinearOrder().Get(i)->GetBlockId(), expected_order[i]);
+ ASSERT_EQ(liveness.GetLinearPostOrder().Get(number_of_blocks - i - 1)->GetBlockId(),
+ expected_order[i]);
}
}
@@ -193,58 +194,4 @@
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 19cd120..7d52d7d 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -233,7 +233,7 @@
return false;
}
- size_t NumberOfBackEdges() const {
+ int NumberOfBackEdges() const {
return back_edges_.Size();
}
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 54eb581..0085b27 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -28,6 +28,11 @@
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;
}
@@ -43,65 +48,46 @@
&& inner->IsIn(*outer);
}
-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;
- }
+static void VisitBlockForLinearization(HBasicBlock* block,
+ GrowableArray<HBasicBlock*>* order,
+ ArenaBitVector* visited) {
+ if (visited->IsBitSet(block->GetBlockId())) {
+ return;
}
- worklist->InsertAt(insert_at, block);
+ 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);
+ }
+ VisitBlockForLinearization(first_successor, order, visited);
+ VisitBlockForLinearization(second_successor, order, visited);
+ }
+ order->Add(block);
}
void SsaLivenessAnalysis::LinearizeGraph() {
- // 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());
+ // 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);
}
void SsaLivenessAnalysis::NumberInstructions() {
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 46cea6d..ca08d5b 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_order_(graph.GetArena(), graph.GetBlocks().Size()),
+ linear_post_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*>& GetLinearOrder() const {
- return linear_order_;
+ const GrowableArray<HBasicBlock*>& GetLinearPostOrder() const {
+ return linear_post_order_;
}
HInstruction* GetInstructionFromSsaIndex(size_t index) const {
@@ -661,7 +661,7 @@
const HGraph& graph_;
CodeGenerator* const codegen_;
- GrowableArray<HBasicBlock*> linear_order_;
+ GrowableArray<HBasicBlock*> linear_post_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 HLinearPostOrderIterator : public ValueObject {
- public:
- explicit HLinearPostOrderIterator(const SsaLivenessAnalysis& liveness)
- : order_(liveness.GetLinearOrder()), index_(liveness.GetLinearOrder().Size()) {}
-
- 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*>& order_;
- size_t index_;
-
- DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator);
-};
-
class HLinearOrderIterator : public ValueObject {
public:
explicit HLinearOrderIterator(const SsaLivenessAnalysis& liveness)
- : order_(liveness.GetLinearOrder()), index_(0) {}
+ : post_order_(liveness.GetLinearPostOrder()), index_(liveness.GetLinearPostOrder().Size()) {}
- bool Done() const { return index_ == order_.Size(); }
- HBasicBlock* Current() const { return order_.Get(index_); }
- void Advance() { ++index_; }
+ 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*>& order_;
+ 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) {}
+
+ 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);
+};
+
} // namespace art
#endif // ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
