Home | History | Annotate | Download | only in optimizing 
      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 
     24 static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) {
     25   return first_loop == second_loop;
     26 }
     27 
     28 static bool IsLoop(HLoopInformation* info) {
     29   return info != nullptr;
     30 }
     31 
     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.
     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.
     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 
     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