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 namespace art {
20
InSameLoop(HLoopInformation * first_loop,HLoopInformation * second_loop)21 static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) {
22 return first_loop == second_loop;
23 }
24
IsLoop(HLoopInformation * info)25 static bool IsLoop(HLoopInformation* info) {
26 return info != nullptr;
27 }
28
IsInnerLoop(HLoopInformation * outer,HLoopInformation * inner)29 static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) {
30 return (inner != outer)
31 && (inner != nullptr)
32 && (outer != nullptr)
33 && inner->IsIn(*outer);
34 }
35
36 // Helper method to update work list for linear order.
AddToListForLinearization(ArenaVector<HBasicBlock * > * worklist,HBasicBlock * block)37 static void AddToListForLinearization(ArenaVector<HBasicBlock*>* worklist, HBasicBlock* block) {
38 HLoopInformation* block_loop = block->GetLoopInformation();
39 auto insert_pos = worklist->rbegin(); // insert_pos.base() will be the actual position.
40 for (auto end = worklist->rend(); insert_pos != end; ++insert_pos) {
41 HBasicBlock* current = *insert_pos;
42 HLoopInformation* current_loop = current->GetLoopInformation();
43 if (InSameLoop(block_loop, current_loop)
44 || !IsLoop(current_loop)
45 || IsInnerLoop(current_loop, block_loop)) {
46 // The block can be processed immediately.
47 break;
48 }
49 }
50 worklist->insert(insert_pos.base(), block);
51 }
52
53 // Helper method to validate linear order.
IsLinearOrderWellFormed(const HGraph * graph,ArenaVector<HBasicBlock * > * linear_order)54 static bool IsLinearOrderWellFormed(const HGraph* graph, ArenaVector<HBasicBlock*>* linear_order) {
55 for (HBasicBlock* header : graph->GetBlocks()) {
56 if (header == nullptr || !header->IsLoopHeader()) {
57 continue;
58 }
59 HLoopInformation* loop = header->GetLoopInformation();
60 size_t num_blocks = loop->GetBlocks().NumSetBits();
61 size_t found_blocks = 0u;
62 for (HBasicBlock* block : *linear_order) {
63 if (loop->Contains(*block)) {
64 found_blocks++;
65 if (found_blocks == 1u && block != header) {
66 // First block is not the header.
67 return false;
68 } else if (found_blocks == num_blocks && !loop->IsBackEdge(*block)) {
69 // Last block is not a back edge.
70 return false;
71 }
72 } else if (found_blocks != 0u && found_blocks != num_blocks) {
73 // Blocks are not adjacent.
74 return false;
75 }
76 }
77 DCHECK_EQ(found_blocks, num_blocks);
78 }
79 return true;
80 }
81
LinearizeGraph(const HGraph * graph,ArenaAllocator * allocator,ArenaVector<HBasicBlock * > * linear_order)82 void LinearizeGraph(const HGraph* graph,
83 ArenaAllocator* allocator,
84 ArenaVector<HBasicBlock*>* linear_order) {
85 DCHECK(linear_order->empty());
86 // Create a reverse post ordering with the following properties:
87 // - Blocks in a loop are consecutive,
88 // - Back-edge is the last block before loop exits.
89 //
90 // (1): Record the number of forward predecessors for each block. This is to
91 // ensure the resulting order is reverse post order. We could use the
92 // current reverse post order in the graph, but it would require making
93 // order queries to a GrowableArray, which is not the best data structure
94 // for it.
95 ArenaVector<uint32_t> forward_predecessors(graph->GetBlocks().size(),
96 allocator->Adapter(kArenaAllocLinearOrder));
97 for (HBasicBlock* block : graph->GetReversePostOrder()) {
98 size_t number_of_forward_predecessors = block->GetPredecessors().size();
99 if (block->IsLoopHeader()) {
100 number_of_forward_predecessors -= block->GetLoopInformation()->NumberOfBackEdges();
101 }
102 forward_predecessors[block->GetBlockId()] = number_of_forward_predecessors;
103 }
104 // (2): Following a worklist approach, first start with the entry block, and
105 // iterate over the successors. When all non-back edge predecessors of a
106 // successor block are visited, the successor block is added in the worklist
107 // following an order that satisfies the requirements to build our linear graph.
108 linear_order->reserve(graph->GetReversePostOrder().size());
109 ArenaVector<HBasicBlock*> worklist(allocator->Adapter(kArenaAllocLinearOrder));
110 worklist.push_back(graph->GetEntryBlock());
111 do {
112 HBasicBlock* current = worklist.back();
113 worklist.pop_back();
114 linear_order->push_back(current);
115 for (HBasicBlock* successor : current->GetSuccessors()) {
116 int block_id = successor->GetBlockId();
117 size_t number_of_remaining_predecessors = forward_predecessors[block_id];
118 if (number_of_remaining_predecessors == 1) {
119 AddToListForLinearization(&worklist, successor);
120 }
121 forward_predecessors[block_id] = number_of_remaining_predecessors - 1;
122 }
123 } while (!worklist.empty());
124
125 DCHECK(graph->HasIrreducibleLoops() || IsLinearOrderWellFormed(graph, linear_order));
126 }
127
128 } // namespace art
129