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