From e50fa5887b1342b845826197d81950e26753fc9c Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Mon, 24 Nov 2014 17:44:15 +0000 Subject: [PATCH] Revert "Fix the computation of linear ordering." Build is broken. This reverts commit 3054a90063d379ab8c9e5a42a7daf0d644b48b07. Change-Id: I259bc2bd6a58e30391b8176f3db5fdb5c07e4d6d --- compiler/optimizing/linearize_test.cc | 59 +---------------- compiler/optimizing/nodes.h | 2 +- compiler/optimizing/ssa_liveness_analysis.cc | 94 ++++++++++++---------------- compiler/optimizing/ssa_liveness_analysis.h | 34 +++++----- 4 files changed, 61 insertions(+), 128 deletions(-) diff --git a/compiler/optimizing/linearize_test.cc b/compiler/optimizing/linearize_test.cc index c49cf7e03..6dd420779 100644 --- a/compiler/optimizing/linearize_test.cc +++ b/compiler/optimizing/linearize_test.cc @@ -50,9 +50,10 @@ static void TestCode(const uint16_t* data, const int* expected_order, size_t num 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 @@ TEST(LinearizeTest, CFG5) { 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 19cd120c5..7d52d7d22 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -233,7 +233,7 @@ class HLoopInformation : public ArenaObject { 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 54eb5813b..0085b27c5 100644 --- a/compiler/optimizing/ssa_liveness_analysis.cc +++ b/compiler/optimizing/ssa_liveness_analysis.cc @@ -28,6 +28,11 @@ void SsaLivenessAnalysis::Analyze() { 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 @@ static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { && inner->IsIn(*outer); } -static void AddToListForLinearization(GrowableArray* 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* 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); } + VisitBlockForLinearization(first_successor, order, visited); + VisitBlockForLinearization(second_successor, order, visited); } - worklist->InsertAt(insert_at, block); + 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 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 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 46cea6de8..ca08d5b3e 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -582,7 +582,7 @@ class SsaLivenessAnalysis : public ValueObject { 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 @@ class SsaLivenessAnalysis : public ValueObject { return &block_infos_.Get(block.GetBlockId())->kill_; } - const GrowableArray& GetLinearOrder() const { - return linear_order_; + const GrowableArray& GetLinearPostOrder() const { + return linear_post_order_; } HInstruction* GetInstructionFromSsaIndex(size_t index) const { @@ -661,7 +661,7 @@ class SsaLivenessAnalysis : public ValueObject { const HGraph& graph_; CodeGenerator* const codegen_; - GrowableArray linear_order_; + GrowableArray linear_post_order_; GrowableArray block_infos_; // Temporary array used when computing live_in, live_out, and kill sets. @@ -674,36 +674,36 @@ class SsaLivenessAnalysis : public ValueObject { DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis); }; -class HLinearPostOrderIterator : public ValueObject { +class HLinearOrderIterator : public ValueObject { public: - explicit HLinearPostOrderIterator(const SsaLivenessAnalysis& liveness) - : order_(liveness.GetLinearOrder()), index_(liveness.GetLinearOrder().Size()) {} + explicit HLinearOrderIterator(const SsaLivenessAnalysis& liveness) + : post_order_(liveness.GetLinearPostOrder()), index_(liveness.GetLinearPostOrder().Size()) {} bool Done() const { return index_ == 0; } - HBasicBlock* Current() const { return order_.Get(index_ -1); } + HBasicBlock* Current() const { return post_order_.Get(index_ -1); } void Advance() { --index_; DCHECK_GE(index_, 0U); } private: - const GrowableArray& order_; + const GrowableArray& post_order_; size_t index_; - DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); + DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); }; -class HLinearOrderIterator : public ValueObject { +class HLinearPostOrderIterator : public ValueObject { public: - explicit HLinearOrderIterator(const SsaLivenessAnalysis& liveness) - : order_(liveness.GetLinearOrder()), index_(0) {} + explicit HLinearPostOrderIterator(const SsaLivenessAnalysis& liveness) + : post_order_(liveness.GetLinearPostOrder()), index_(0) {} - bool Done() const { return index_ == order_.Size(); } - HBasicBlock* Current() const { return order_.Get(index_); } + bool Done() const { return index_ == post_order_.Size(); } + HBasicBlock* Current() const { return post_order_.Get(index_); } void Advance() { ++index_; } private: - const GrowableArray& order_; + const GrowableArray& post_order_; size_t index_; - DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); + DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); }; } // namespace art -- 2.11.0