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 "select_generator.h"
     18 
     19 #include "reference_type_propagation.h"
     20 
     21 namespace art {
     22 
     23 static constexpr size_t kMaxInstructionsInBranch = 1u;
     24 
     25 HSelectGenerator::HSelectGenerator(HGraph* graph,
     26                                    VariableSizedHandleScope* handles,
     27                                    OptimizingCompilerStats* stats,
     28                                    const char* name)
     29     : HOptimization(graph, name, stats),
     30       handle_scope_(handles) {
     31 }
     32 
     33 // Returns true if `block` has only one predecessor, ends with a Goto
     34 // or a Return and contains at most `kMaxInstructionsInBranch` other
     35 // movable instruction with no side-effects.
     36 static bool IsSimpleBlock(HBasicBlock* block) {
     37   if (block->GetPredecessors().size() != 1u) {
     38     return false;
     39   }
     40   DCHECK(block->GetPhis().IsEmpty());
     41 
     42   size_t num_instructions = 0u;
     43   for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
     44     HInstruction* instruction = it.Current();
     45     if (instruction->IsControlFlow()) {
     46       if (num_instructions > kMaxInstructionsInBranch) {
     47         return false;
     48       }
     49       return instruction->IsGoto() || instruction->IsReturn();
     50     } else if (instruction->CanBeMoved() && !instruction->HasSideEffects()) {
     51       num_instructions++;
     52     } else {
     53       return false;
     54     }
     55   }
     56 
     57   LOG(FATAL) << "Unreachable";
     58   UNREACHABLE();
     59 }
     60 
     61 // Returns true if 'block1' and 'block2' are empty and merge into the
     62 // same single successor.
     63 static bool BlocksMergeTogether(HBasicBlock* block1, HBasicBlock* block2) {
     64   return block1->GetSingleSuccessor() == block2->GetSingleSuccessor();
     65 }
     66 
     67 // Returns nullptr if `block` has either no phis or there is more than one phi
     68 // with different inputs at `index1` and `index2`. Otherwise returns that phi.
     69 static HPhi* GetSingleChangedPhi(HBasicBlock* block, size_t index1, size_t index2) {
     70   DCHECK_NE(index1, index2);
     71 
     72   HPhi* select_phi = nullptr;
     73   for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
     74     HPhi* phi = it.Current()->AsPhi();
     75     if (phi->InputAt(index1) != phi->InputAt(index2)) {
     76       if (select_phi == nullptr) {
     77         // First phi with different inputs for the two indices found.
     78         select_phi = phi;
     79       } else {
     80         // More than one phis has different inputs for the two indices.
     81         return nullptr;
     82       }
     83     }
     84   }
     85   return select_phi;
     86 }
     87 
     88 void HSelectGenerator::Run() {
     89   // Iterate in post order in the unlikely case that removing one occurrence of
     90   // the selection pattern empties a branch block of another occurrence.
     91   // Otherwise the order does not matter.
     92   for (HBasicBlock* block : graph_->GetPostOrder()) {
     93     if (!block->EndsWithIf()) continue;
     94 
     95     // Find elements of the diamond pattern.
     96     HIf* if_instruction = block->GetLastInstruction()->AsIf();
     97     HBasicBlock* true_block = if_instruction->IfTrueSuccessor();
     98     HBasicBlock* false_block = if_instruction->IfFalseSuccessor();
     99     DCHECK_NE(true_block, false_block);
    100     if (!IsSimpleBlock(true_block) ||
    101         !IsSimpleBlock(false_block) ||
    102         !BlocksMergeTogether(true_block, false_block)) {
    103       continue;
    104     }
    105     HBasicBlock* merge_block = true_block->GetSingleSuccessor();
    106 
    107     // If the branches are not empty, move instructions in front of the If.
    108     // TODO(dbrazdil): This puts an instruction between If and its condition.
    109     //                 Implement moving of conditions to first users if possible.
    110     if (!true_block->IsSingleGoto() && !true_block->IsSingleReturn()) {
    111       true_block->GetFirstInstruction()->MoveBefore(if_instruction);
    112     }
    113     if (!false_block->IsSingleGoto() && !false_block->IsSingleReturn()) {
    114       false_block->GetFirstInstruction()->MoveBefore(if_instruction);
    115     }
    116     DCHECK(true_block->IsSingleGoto() || true_block->IsSingleReturn());
    117     DCHECK(false_block->IsSingleGoto() || false_block->IsSingleReturn());
    118 
    119     // Find the resulting true/false values.
    120     size_t predecessor_index_true = merge_block->GetPredecessorIndexOf(true_block);
    121     size_t predecessor_index_false = merge_block->GetPredecessorIndexOf(false_block);
    122     DCHECK_NE(predecessor_index_true, predecessor_index_false);
    123 
    124     bool both_successors_return = true_block->IsSingleReturn() && false_block->IsSingleReturn();
    125     HPhi* phi = GetSingleChangedPhi(merge_block, predecessor_index_true, predecessor_index_false);
    126 
    127     HInstruction* true_value = nullptr;
    128     HInstruction* false_value = nullptr;
    129     if (both_successors_return) {
    130       true_value = true_block->GetFirstInstruction()->InputAt(0);
    131       false_value = false_block->GetFirstInstruction()->InputAt(0);
    132     } else if (phi != nullptr) {
    133       true_value = phi->InputAt(predecessor_index_true);
    134       false_value = phi->InputAt(predecessor_index_false);
    135     } else {
    136       continue;
    137     }
    138     DCHECK(both_successors_return || phi != nullptr);
    139 
    140     // Create the Select instruction and insert it in front of the If.
    141     HSelect* select = new (graph_->GetAllocator()) HSelect(if_instruction->InputAt(0),
    142                                                            true_value,
    143                                                            false_value,
    144                                                            if_instruction->GetDexPc());
    145     if (both_successors_return) {
    146       if (true_value->GetType() == DataType::Type::kReference) {
    147         DCHECK(false_value->GetType() == DataType::Type::kReference);
    148         ReferenceTypePropagation::FixUpInstructionType(select, handle_scope_);
    149       }
    150     } else if (phi->GetType() == DataType::Type::kReference) {
    151       select->SetReferenceTypeInfo(phi->GetReferenceTypeInfo());
    152     }
    153     block->InsertInstructionBefore(select, if_instruction);
    154 
    155     // Remove the true branch which removes the corresponding Phi
    156     // input if needed. If left only with the false branch, the Phi is
    157     // automatically removed.
    158     if (both_successors_return) {
    159       false_block->GetFirstInstruction()->ReplaceInput(select, 0);
    160     } else {
    161       phi->ReplaceInput(select, predecessor_index_false);
    162     }
    163 
    164     bool only_two_predecessors = (merge_block->GetPredecessors().size() == 2u);
    165     true_block->DisconnectAndDelete();
    166 
    167     // Merge remaining blocks which are now connected with Goto.
    168     DCHECK_EQ(block->GetSingleSuccessor(), false_block);
    169     block->MergeWith(false_block);
    170     if (!both_successors_return && only_two_predecessors) {
    171       DCHECK_EQ(only_two_predecessors, phi->GetBlock() == nullptr);
    172       DCHECK_EQ(block->GetSingleSuccessor(), merge_block);
    173       block->MergeWith(merge_block);
    174     }
    175 
    176     MaybeRecordStat(stats_, MethodCompilationStat::kSelectGenerated);
    177 
    178     // No need to update dominance information, as we are simplifying
    179     // a simple diamond shape, where the join block is merged with the
    180     // entry block. Any following blocks would have had the join block
    181     // as a dominator, and `MergeWith` handles changing that to the
    182     // entry block.
    183   }
    184 }
    185 
    186 }  // namespace art
    187