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
22 namespace art {
23
InSameLoop(HLoopInformation * first_loop,HLoopInformation * second_loop)24 static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) {
25 return first_loop == second_loop;
26 }
27
IsLoop(HLoopInformation * info)28 static bool IsLoop(HLoopInformation* info) {
29 return info != nullptr;
30 }
31
IsInnerLoop(HLoopInformation * outer,HLoopInformation * inner)32 static 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.
AddToListForLinearization(ScopedArenaVector<HBasicBlock * > * worklist,HBasicBlock * block)40 static 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.
IsLinearOrderWellFormed(const HGraph * graph,ArrayRef<HBasicBlock * > linear_order)58 static 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
LinearizeGraphInternal(const HGraph * graph,ArrayRef<HBasicBlock * > linear_order)86 void 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