1/*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include "linear_order.h"
18
19#include "base/scoped_arena_allocator.h"
20#include "base/scoped_arena_containers.h"
21
22namespace art {
23
24static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) {
25  return first_loop == second_loop;
26}
27
28static bool IsLoop(HLoopInformation* info) {
29  return info != nullptr;
30}
31
32static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) {
33  return (inner != outer)
34      && (inner != nullptr)
35      && (outer != nullptr)
36      && inner->IsIn(*outer);
37}
38
39// Helper method to update work list for linear order.
40static void AddToListForLinearization(ScopedArenaVector<HBasicBlock*>* worklist,
41                                      HBasicBlock* block) {
42  HLoopInformation* block_loop = block->GetLoopInformation();
43  auto insert_pos = worklist->rbegin();  // insert_pos.base() will be the actual position.
44  for (auto end = worklist->rend(); insert_pos != end; ++insert_pos) {
45    HBasicBlock* current = *insert_pos;
46    HLoopInformation* current_loop = current->GetLoopInformation();
47    if (InSameLoop(block_loop, current_loop)
48        || !IsLoop(current_loop)
49        || IsInnerLoop(current_loop, block_loop)) {
50      // The block can be processed immediately.
51      break;
52    }
53  }
54  worklist->insert(insert_pos.base(), block);
55}
56
57// Helper method to validate linear order.
58static bool IsLinearOrderWellFormed(const HGraph* graph, ArrayRef<HBasicBlock*> linear_order) {
59  for (HBasicBlock* header : graph->GetBlocks()) {
60    if (header == nullptr || !header->IsLoopHeader()) {
61      continue;
62    }
63    HLoopInformation* loop = header->GetLoopInformation();
64    size_t num_blocks = loop->GetBlocks().NumSetBits();
65    size_t found_blocks = 0u;
66    for (HBasicBlock* block : linear_order) {
67      if (loop->Contains(*block)) {
68        found_blocks++;
69        if (found_blocks == 1u && block != header) {
70          // First block is not the header.
71          return false;
72        } else if (found_blocks == num_blocks && !loop->IsBackEdge(*block)) {
73          // Last block is not a back edge.
74          return false;
75        }
76      } else if (found_blocks != 0u && found_blocks != num_blocks) {
77        // Blocks are not adjacent.
78        return false;
79      }
80    }
81    DCHECK_EQ(found_blocks, num_blocks);
82  }
83  return true;
84}
85
86void LinearizeGraphInternal(const HGraph* graph, ArrayRef<HBasicBlock*> linear_order) {
87  DCHECK_EQ(linear_order.size(), graph->GetReversePostOrder().size());
88  // Create a reverse post ordering with the following properties:
89  // - Blocks in a loop are consecutive,
90  // - Back-edge is the last block before loop exits.
91  //
92  // (1): Record the number of forward predecessors for each block. This is to
93  //      ensure the resulting order is reverse post order. We could use the
94  //      current reverse post order in the graph, but it would require making
95  //      order queries to a GrowableArray, which is not the best data structure
96  //      for it.
97  ScopedArenaAllocator allocator(graph->GetArenaStack());
98  ScopedArenaVector<uint32_t> forward_predecessors(graph->GetBlocks().size(),
99                                                   allocator.Adapter(kArenaAllocLinearOrder));
100  for (HBasicBlock* block : graph->GetReversePostOrder()) {
101    size_t number_of_forward_predecessors = block->GetPredecessors().size();
102    if (block->IsLoopHeader()) {
103      number_of_forward_predecessors -= block->GetLoopInformation()->NumberOfBackEdges();
104    }
105    forward_predecessors[block->GetBlockId()] = number_of_forward_predecessors;
106  }
107  // (2): Following a worklist approach, first start with the entry block, and
108  //      iterate over the successors. When all non-back edge predecessors of a
109  //      successor block are visited, the successor block is added in the worklist
110  //      following an order that satisfies the requirements to build our linear graph.
111  ScopedArenaVector<HBasicBlock*> worklist(allocator.Adapter(kArenaAllocLinearOrder));
112  worklist.push_back(graph->GetEntryBlock());
113  size_t num_added = 0u;
114  do {
115    HBasicBlock* current = worklist.back();
116    worklist.pop_back();
117    linear_order[num_added] = current;
118    ++num_added;
119    for (HBasicBlock* successor : current->GetSuccessors()) {
120      int block_id = successor->GetBlockId();
121      size_t number_of_remaining_predecessors = forward_predecessors[block_id];
122      if (number_of_remaining_predecessors == 1) {
123        AddToListForLinearization(&worklist, successor);
124      }
125      forward_predecessors[block_id] = number_of_remaining_predecessors - 1;
126    }
127  } while (!worklist.empty());
128  DCHECK_EQ(num_added, linear_order.size());
129
130  DCHECK(graph->HasIrreducibleLoops() || IsLinearOrderWellFormed(graph, linear_order));
131}
132
133}  // namespace art
134