174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil/* 274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * Copyright (C) 2016 The Android Open Source Project 374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * 474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * Licensed under the Apache License, Version 2.0 (the "License"); 574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * you may not use this file except in compliance with the License. 674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * You may obtain a copy of the License at 774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * 874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * http://www.apache.org/licenses/LICENSE-2.0 974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * 1074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * Unless required by applicable law or agreed to in writing, software 1174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * distributed under the License is distributed on an "AS IS" BASIS, 1274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * See the License for the specific language governing permissions and 1474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * limitations under the License. 1574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil */ 1674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 1774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil#include "select_generator.h" 1874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 1974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdilnamespace art { 2074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 2174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdilstatic constexpr size_t kMaxInstructionsInBranch = 1u; 2274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 2374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil// Returns true if `block` has only one predecessor, ends with a Goto and 2474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil// contains at most `kMaxInstructionsInBranch` other movable instruction with 2574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil// no side-effects. 2674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdilstatic bool IsSimpleBlock(HBasicBlock* block) { 2774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil if (block->GetPredecessors().size() != 1u) { 2874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil return false; 2974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 3074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil DCHECK(block->GetPhis().IsEmpty()); 3174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 3274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil size_t num_instructions = 0u; 3374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 3474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil HInstruction* instruction = it.Current(); 3574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil if (instruction->IsControlFlow()) { 3674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil return instruction->IsGoto() && num_instructions <= kMaxInstructionsInBranch; 3774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } else if (instruction->CanBeMoved() && !instruction->HasSideEffects()) { 3874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil num_instructions++; 3974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } else { 4074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil return false; 4174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 4274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 4374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 4474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil LOG(FATAL) << "Unreachable"; 4574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil UNREACHABLE(); 4674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil} 4774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 4874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil// Returns true if 'block1' and 'block2' are empty, merge into the same single 4974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil// successor and the successor can only be reached from them. 5074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdilstatic bool BlocksMergeTogether(HBasicBlock* block1, HBasicBlock* block2) { 5174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil return block1->GetSingleSuccessor() == block2->GetSingleSuccessor(); 5274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil} 5374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 5474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil// Returns nullptr if `block` has either no phis or there is more than one phi 5574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil// with different inputs at `index1` and `index2`. Otherwise returns that phi. 5674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdilstatic HPhi* GetSingleChangedPhi(HBasicBlock* block, size_t index1, size_t index2) { 5774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil DCHECK_NE(index1, index2); 5874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 5974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil HPhi* select_phi = nullptr; 6074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 6174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil HPhi* phi = it.Current()->AsPhi(); 6274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil if (phi->InputAt(index1) != phi->InputAt(index2)) { 6374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil if (select_phi == nullptr) { 6474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // First phi with different inputs for the two indices found. 6574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil select_phi = phi; 6674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } else { 6774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // More than one phis has different inputs for the two indices. 6874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil return nullptr; 6974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 7074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 7174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 7274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil return select_phi; 7374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil} 7474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 7574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdilvoid HSelectGenerator::Run() { 7674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // Iterate in post order in the unlikely case that removing one occurrence of 7774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // the selection pattern empties a branch block of another occurrence. 7874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // Otherwise the order does not matter. 7974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 8074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil HBasicBlock* block = it.Current(); 8174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil if (!block->EndsWithIf()) continue; 8274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 8374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // Find elements of the diamond pattern. 8474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil HIf* if_instruction = block->GetLastInstruction()->AsIf(); 8574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil HBasicBlock* true_block = if_instruction->IfTrueSuccessor(); 8674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil HBasicBlock* false_block = if_instruction->IfFalseSuccessor(); 8774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil DCHECK_NE(true_block, false_block); 8874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil if (!IsSimpleBlock(true_block) || 8974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil !IsSimpleBlock(false_block) || 9074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil !BlocksMergeTogether(true_block, false_block)) { 9174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil continue; 9274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 9374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil HBasicBlock* merge_block = true_block->GetSingleSuccessor(); 9474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 9574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // If the branches are not empty, move instructions in front of the If. 9674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // TODO(dbrazdil): This puts an instruction between If and its condition. 9774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // Implement moving of conditions to first users if possible. 9874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil if (!true_block->IsSingleGoto()) { 9974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil true_block->MoveInstructionBefore(true_block->GetFirstInstruction(), if_instruction); 10074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 10174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil if (!false_block->IsSingleGoto()) { 10274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil false_block->MoveInstructionBefore(false_block->GetFirstInstruction(), if_instruction); 10374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 10474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil DCHECK(true_block->IsSingleGoto()); 10574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil DCHECK(false_block->IsSingleGoto()); 10674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 10774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // Find the resulting true/false values. 10874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil size_t predecessor_index_true = merge_block->GetPredecessorIndexOf(true_block); 10974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil size_t predecessor_index_false = merge_block->GetPredecessorIndexOf(false_block); 11074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil DCHECK_NE(predecessor_index_true, predecessor_index_false); 11174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 11274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil HPhi* phi = GetSingleChangedPhi(merge_block, predecessor_index_true, predecessor_index_false); 11374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil if (phi == nullptr) { 11474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil continue; 11574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 11674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil HInstruction* true_value = phi->InputAt(predecessor_index_true); 11774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil HInstruction* false_value = phi->InputAt(predecessor_index_false); 11874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 11974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // Create the Select instruction and insert it in front of the If. 12074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil HSelect* select = new (graph_->GetArena()) HSelect(if_instruction->InputAt(0), 12174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil true_value, 12274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil false_value, 12374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil if_instruction->GetDexPc()); 12474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil if (phi->GetType() == Primitive::kPrimNot) { 12574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil select->SetReferenceTypeInfo(phi->GetReferenceTypeInfo()); 12674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 12774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil block->InsertInstructionBefore(select, if_instruction); 12874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 12974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // Remove the true branch which removes the corresponding Phi input. 13074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // If left only with the false branch, the Phi is automatically removed. 13174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil phi->ReplaceInput(select, predecessor_index_false); 13274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil bool only_two_predecessors = (merge_block->GetPredecessors().size() == 2u); 13374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil true_block->DisconnectAndDelete(); 13474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil DCHECK_EQ(only_two_predecessors, phi->GetBlock() == nullptr); 13574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 13674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // Merge remaining blocks which are now connected with Goto. 13774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil DCHECK_EQ(block->GetSingleSuccessor(), false_block); 13874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil block->MergeWith(false_block); 13974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil if (only_two_predecessors) { 14074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil DCHECK_EQ(block->GetSingleSuccessor(), merge_block); 14174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil block->MergeWith(merge_block); 14274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 14374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 14438e9e8046ea2196284bdb4638771c31108a30a4aJean-Philippe Halimi MaybeRecordStat(MethodCompilationStat::kSelectGenerated); 14538e9e8046ea2196284bdb4638771c31108a30a4aJean-Philippe Halimi 14674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // No need to update dominance information, as we are simplifying 14774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // a simple diamond shape, where the join block is merged with the 14874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // entry block. Any following blocks would have had the join block 14974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // as a dominator, and `MergeWith` handles changing that to the 15074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil // entry block. 15174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil } 15274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil} 15374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil 15474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil} // namespace art 155