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 21 static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { 22 return first_loop == second_loop; 23 } 24 25 static bool IsLoop(HLoopInformation* info) { 26 return info != nullptr; 27 } 28 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. 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. 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 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
