Refactoring of graph linearization and linear order.

Rationale:
Ownership of graph's linear order and iterators was
a bit unclear now that other phases are using it.
New approach allows phases to compute their own
order, while ssa_liveness is sole owner for graph
(since it is not mutated afterwards).

Also shortens lifetime of loop's arena.

Test: test-art-host
Change-Id: Ib7137d1203a1e0a12db49868f4117d48a4277f30

1 files changed, 0 insertions, 110 deletions

diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 1ff2252348..874c1edf35 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -460,116 +460,6 @@ GraphAnalysisResult HGraph::AnalyzeLoops() const {
   return kAnalysisSuccess;
 }
 
-static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) {
-  return first_loop == second_loop;
-}
-
-static bool IsLoop(HLoopInformation* info) {
-  return info != nullptr;
-}
-
-static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) {
-  return (inner != outer)
-      && (inner != nullptr)
-      && (outer != nullptr)
-      && inner->IsIn(*outer);
-}
-
-// Helper method to update work list for linear order.
-static void AddToListForLinearization(ArenaVector<HBasicBlock*>* worklist, HBasicBlock* block) {
-  HLoopInformation* block_loop = block->GetLoopInformation();
-  auto insert_pos = worklist->rbegin();  // insert_pos.base() will be the actual position.
-  for (auto end = worklist->rend(); insert_pos != end; ++insert_pos) {
-    HBasicBlock* current = *insert_pos;
-    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;
-    }
-  }
-  worklist->insert(insert_pos.base(), block);
-}
-
-// Helper method to validate linear order.
-static bool IsLinearOrderWellFormed(const HGraph& graph) {
-  for (HBasicBlock* header : graph.GetBlocks()) {
-    if (header == nullptr || !header->IsLoopHeader()) {
-      continue;
-    }
-    HLoopInformation* loop = header->GetLoopInformation();
-    size_t num_blocks = loop->GetBlocks().NumSetBits();
-    size_t found_blocks = 0u;
-    for (HLinearOrderIterator it(graph); !it.Done(); it.Advance()) {
-      HBasicBlock* current = it.Current();
-      if (loop->Contains(*current)) {
-        found_blocks++;
-        if (found_blocks == 1u && current != header) {
-          // First block is not the header.
-          return false;
-        } else if (found_blocks == num_blocks && !loop->IsBackEdge(*current)) {
-          // Last block is not a back edge.
-          return false;
-        }
-      } else if (found_blocks != 0u && found_blocks != num_blocks) {
-        // Blocks are not adjacent.
-        return false;
-      }
-    }
-    DCHECK_EQ(found_blocks, num_blocks);
-  }
-  return true;
-}
-
-// TODO: return order, and give only liveness analysis ownership of graph's linear_order_?
-void HGraph::Linearize() {
-  linear_order_.clear();
-
-  // 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.
-  ArenaVector<uint32_t> forward_predecessors(blocks_.size(),
-                                             arena_->Adapter(kArenaAllocSsaLiveness));
-  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
-    HBasicBlock* block = it.Current();
-    size_t number_of_forward_predecessors = block->GetPredecessors().size();
-    if (block->IsLoopHeader()) {
-      number_of_forward_predecessors -= block->GetLoopInformation()->NumberOfBackEdges();
-    }
-    forward_predecessors[block->GetBlockId()] = number_of_forward_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.
-  linear_order_.reserve(GetReversePostOrder().size());
-  ArenaVector<HBasicBlock*> worklist(arena_->Adapter(kArenaAllocSsaLiveness));
-  worklist.push_back(GetEntryBlock());
-  do {
-    HBasicBlock* current = worklist.back();
-    worklist.pop_back();
-    linear_order_.push_back(current);
-    for (HBasicBlock* successor : current->GetSuccessors()) {
-      int block_id = successor->GetBlockId();
-      size_t number_of_remaining_predecessors = forward_predecessors[block_id];
-      if (number_of_remaining_predecessors == 1) {
-        AddToListForLinearization(&worklist, successor);
-      }
-      forward_predecessors[block_id] = number_of_remaining_predecessors - 1;
-    }
-  } while (!worklist.empty());
-
-  DCHECK(HasIrreducibleLoops() || IsLinearOrderWellFormed(*this));
-}
-
 void HLoopInformation::Dump(std::ostream& os) {
   os << "header: " << header_->GetBlockId() << std::endl;
   os << "pre header: " << GetPreHeader()->GetBlockId() << std::endl;