Merge "Revert "Fix the computation of linear ordering.""

4 files changed, 61 insertions, 128 deletions

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 @@ 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 f562113..b47549a 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -236,7 +236,7 @@ class HLoopInformation : public ArenaObject<kArenaAllocMisc> {
     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 @@ 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<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;
+  }
+  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<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 @@ 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<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 @@ class SsaLivenessAnalysis : public ValueObject {
 
   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,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<HBasicBlock*>& order_;
+  const GrowableArray<HBasicBlock*>& 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<HBasicBlock*>& order_;
+  const GrowableArray<HBasicBlock*>& post_order_;
   size_t index_;
 
-  DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator);
+  DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator);
 };
 
 }  // namespace art