diff options
Diffstat (limited to 'compiler')
| -rw-r--r-- | compiler/Android.mk | 2 | ||||
| -rw-r--r-- | compiler/optimizing/boolean_simplifier.cc | 136 | ||||
| -rw-r--r-- | compiler/optimizing/boolean_simplifier.h | 81 | ||||
| -rw-r--r-- | compiler/optimizing/code_generator_arm.cc | 50 | ||||
| -rw-r--r-- | compiler/optimizing/code_generator_arm64.cc | 26 | ||||
| -rw-r--r-- | compiler/optimizing/code_generator_mips.cc | 26 | ||||
| -rw-r--r-- | compiler/optimizing/code_generator_mips64.cc | 26 | ||||
| -rw-r--r-- | compiler/optimizing/code_generator_x86.cc | 69 | ||||
| -rw-r--r-- | compiler/optimizing/code_generator_x86_64.cc | 34 | ||||
| -rw-r--r-- | compiler/optimizing/graph_checker.cc | 13 | ||||
| -rw-r--r-- | compiler/optimizing/graph_checker.h | 1 | ||||
| -rw-r--r-- | compiler/optimizing/instruction_simplifier.cc | 88 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.cc | 16 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.h | 37 | ||||
| -rw-r--r-- | compiler/optimizing/optimizing_compiler.cc | 8 | ||||
| -rw-r--r-- | compiler/optimizing/prepare_for_register_allocation.cc | 12 | ||||
| -rw-r--r-- | compiler/optimizing/select_generator.cc | 152 | ||||
| -rw-r--r-- | compiler/optimizing/select_generator.h | 63 |
18 files changed, 589 insertions, 251 deletions
diff --git a/compiler/Android.mk b/compiler/Android.mk index 6f32e07ce1..87eff82982 100644 --- a/compiler/Android.mk +++ b/compiler/Android.mk @@ -66,7 +66,6 @@ LIBART_COMPILER_SRC_FILES := \ jit/jit_compiler.cc \ jni/quick/calling_convention.cc \ jni/quick/jni_compiler.cc \ - optimizing/boolean_simplifier.cc \ optimizing/bounds_check_elimination.cc \ optimizing/builder.cc \ optimizing/code_generator.cc \ @@ -94,6 +93,7 @@ LIBART_COMPILER_SRC_FILES := \ optimizing/prepare_for_register_allocation.cc \ optimizing/reference_type_propagation.cc \ optimizing/register_allocator.cc \ + optimizing/select_generator.cc \ optimizing/sharpening.cc \ optimizing/side_effects_analysis.cc \ optimizing/ssa_builder.cc \ diff --git a/compiler/optimizing/boolean_simplifier.cc b/compiler/optimizing/boolean_simplifier.cc deleted file mode 100644 index f0cafc847f..0000000000 --- a/compiler/optimizing/boolean_simplifier.cc +++ /dev/null @@ -1,136 +0,0 @@ -/* - * Copyright (C) 2015 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "boolean_simplifier.h" - -namespace art { - -void HBooleanSimplifier::TryRemovingNegatedCondition(HBasicBlock* block) { - DCHECK(block->EndsWithIf()); - - // Check if the condition is a Boolean negation. - HIf* if_instruction = block->GetLastInstruction()->AsIf(); - HInstruction* boolean_not = if_instruction->InputAt(0); - if (!boolean_not->IsBooleanNot()) { - return; - } - - // Make BooleanNot's input the condition of the If and swap branches. - if_instruction->ReplaceInput(boolean_not->InputAt(0), 0); - block->SwapSuccessors(); - - // Remove the BooleanNot if it is now unused. - if (!boolean_not->HasUses()) { - boolean_not->GetBlock()->RemoveInstruction(boolean_not); - } -} - -// Returns true if 'block1' and 'block2' are empty, merge into the same single -// successor and the successor can only be reached from them. -static bool BlocksDoMergeTogether(HBasicBlock* block1, HBasicBlock* block2) { - if (!block1->IsSingleGoto() || !block2->IsSingleGoto()) return false; - HBasicBlock* succ1 = block1->GetSuccessors()[0]; - HBasicBlock* succ2 = block2->GetSuccessors()[0]; - return succ1 == succ2 && succ1->GetPredecessors().size() == 2u; -} - -// Returns true if the outcome of the branching matches the boolean value of -// the branching condition. -static bool PreservesCondition(HInstruction* input_true, HInstruction* input_false) { - return input_true->IsIntConstant() && input_true->AsIntConstant()->IsOne() - && input_false->IsIntConstant() && input_false->AsIntConstant()->IsZero(); -} - -// Returns true if the outcome of the branching is exactly opposite of the -// boolean value of the branching condition. -static bool NegatesCondition(HInstruction* input_true, HInstruction* input_false) { - return input_true->IsIntConstant() && input_true->AsIntConstant()->IsZero() - && input_false->IsIntConstant() && input_false->AsIntConstant()->IsOne(); -} - -void HBooleanSimplifier::TryRemovingBooleanSelection(HBasicBlock* block) { - DCHECK(block->EndsWithIf()); - - // Find elements of the pattern. - HIf* if_instruction = block->GetLastInstruction()->AsIf(); - HBasicBlock* true_block = if_instruction->IfTrueSuccessor(); - HBasicBlock* false_block = if_instruction->IfFalseSuccessor(); - if (!BlocksDoMergeTogether(true_block, false_block)) { - return; - } - HBasicBlock* merge_block = true_block->GetSuccessors()[0]; - if (!merge_block->HasSinglePhi()) { - return; - } - HPhi* phi = merge_block->GetFirstPhi()->AsPhi(); - HInstruction* true_value = phi->InputAt(merge_block->GetPredecessorIndexOf(true_block)); - HInstruction* false_value = phi->InputAt(merge_block->GetPredecessorIndexOf(false_block)); - - // Check if the selection negates/preserves the value of the condition and - // if so, generate a suitable replacement instruction. - HInstruction* if_condition = if_instruction->InputAt(0); - - // Don't change FP compares. The definition of compares involving NaNs forces - // the compares to be done as written by the user. - if (if_condition->IsCondition() && - Primitive::IsFloatingPointType(if_condition->InputAt(0)->GetType())) { - return; - } - - HInstruction* replacement; - if (NegatesCondition(true_value, false_value)) { - replacement = graph_->InsertOppositeCondition(if_condition, if_instruction); - } else if (PreservesCondition(true_value, false_value)) { - replacement = if_condition; - } else { - return; - } - - // Replace the selection outcome with the new instruction. - phi->ReplaceWith(replacement); - merge_block->RemovePhi(phi); - - // Delete the true branch and merge the resulting chain of blocks - // 'block->false_block->merge_block' into one. - true_block->DisconnectAndDelete(); - block->MergeWith(false_block); - block->MergeWith(merge_block); - - // No need to update any dominance information, as we are simplifying - // a simple diamond shape, where the join block is merged with the - // entry block. Any following blocks would have had the join block - // as a dominator, and `MergeWith` handles changing that to the - // entry block. -} - -void HBooleanSimplifier::Run() { - // Iterate in post order in the unlikely case that removing one occurrence of - // the selection pattern empties a branch block of another occurrence. - // Otherwise the order does not matter. - for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); - if (!block->EndsWithIf()) continue; - - // If condition is negated, remove the negation and swap the branches. - TryRemovingNegatedCondition(block); - - // If this is a boolean-selection diamond pattern, replace its result with - // the condition value (or its negation) and simplify the graph. - TryRemovingBooleanSelection(block); - } -} - -} // namespace art diff --git a/compiler/optimizing/boolean_simplifier.h b/compiler/optimizing/boolean_simplifier.h deleted file mode 100644 index e12a12c95b..0000000000 --- a/compiler/optimizing/boolean_simplifier.h +++ /dev/null @@ -1,81 +0,0 @@ -/* - * Copyright (C) 2015 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -// This optimization recognizes two common patterns: -// (a) Boolean selection: Casting a boolean to an integer or negating it is -// carried out with an If statement selecting from zero/one integer -// constants. Because Boolean values are represented as zero/one, the -// pattern can be replaced with the condition instruction itself or its -// negation, depending on the layout. -// (b) Negated condition: Instruction simplifier may replace an If's condition -// with a boolean value. If this value is the result of a Boolean negation, -// the true/false branches can be swapped and negation removed. - -// Example: Negating a boolean value -// B1: -// z1 ParameterValue -// i2 IntConstant 0 -// i3 IntConstant 1 -// v4 Goto B2 -// B2: -// z5 NotEquals [ z1 i2 ] -// v6 If [ z5 ] then B3 else B4 -// B3: -// v7 Goto B5 -// B4: -// v8 Goto B5 -// B5: -// i9 Phi [ i3 i2 ] -// v10 Return [ i9 ] -// turns into -// B1: -// z1 ParameterValue -// i2 IntConstant 0 -// v4 Goto B2 -// B2: -// z11 Equals [ z1 i2 ] -// v10 Return [ z11 ] -// B3, B4, B5: removed - -// Note: in order to recognize empty blocks, this optimization must be run -// after the instruction simplifier has removed redundant suspend checks. - -#ifndef ART_COMPILER_OPTIMIZING_BOOLEAN_SIMPLIFIER_H_ -#define ART_COMPILER_OPTIMIZING_BOOLEAN_SIMPLIFIER_H_ - -#include "optimization.h" - -namespace art { - -class HBooleanSimplifier : public HOptimization { - public: - explicit HBooleanSimplifier(HGraph* graph) - : HOptimization(graph, kBooleanSimplifierPassName) {} - - void Run() OVERRIDE; - - static constexpr const char* kBooleanSimplifierPassName = "boolean_simplifier"; - - private: - void TryRemovingNegatedCondition(HBasicBlock* block); - void TryRemovingBooleanSelection(HBasicBlock* block); - - DISALLOW_COPY_AND_ASSIGN(HBooleanSimplifier); -}; - -} // namespace art - -#endif // ART_COMPILER_OPTIMIZING_BOOLEAN_SIMPLIFIER_H_ diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc index 2b81dba0f9..894ee07222 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -1285,11 +1285,9 @@ void CodeGeneratorARM::MoveConstant(Location location, int32_t value) { } void CodeGeneratorARM::MoveLocation(Location dst, Location src, Primitive::Type dst_type) { - if (Primitive::Is64BitType(dst_type)) { - Move64(dst, src); - } else { - Move32(dst, src); - } + HParallelMove move(GetGraph()->GetArena()); + move.AddMove(src, dst, dst_type, nullptr); + GetMoveResolver()->EmitNativeCode(&move); } void CodeGeneratorARM::AddLocationAsTemp(Location location, LocationSummary* locations) { @@ -1612,6 +1610,32 @@ void InstructionCodeGeneratorARM::VisitDeoptimize(HDeoptimize* deoptimize) { /* false_target */ nullptr); } +void LocationsBuilderARM::VisitSelect(HSelect* select) { + LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(select); + if (Primitive::IsFloatingPointType(select->GetType())) { + locations->SetInAt(0, Location::RequiresFpuRegister()); + locations->SetInAt(1, Location::RequiresFpuRegister()); + } else { + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RequiresRegister()); + } + if (IsBooleanValueOrMaterializedCondition(select->GetCondition())) { + locations->SetInAt(2, Location::RequiresRegister()); + } + locations->SetOut(Location::SameAsFirstInput()); +} + +void InstructionCodeGeneratorARM::VisitSelect(HSelect* select) { + LocationSummary* locations = select->GetLocations(); + Label false_target; + GenerateTestAndBranch(select, + /* condition_input_index */ 2, + /* true_target */ nullptr, + &false_target); + codegen_->MoveLocation(locations->Out(), locations->InAt(1), select->GetType()); + __ Bind(&false_target); +} + void LocationsBuilderARM::VisitNativeDebugInfo(HNativeDebugInfo* info) { new (GetGraph()->GetArena()) LocationSummary(info); } @@ -4973,6 +4997,8 @@ void ParallelMoveResolverARM::EmitMove(size_t index) { if (source.IsRegister()) { if (destination.IsRegister()) { __ Mov(destination.AsRegister<Register>(), source.AsRegister<Register>()); + } else if (destination.IsFpuRegister()) { + __ vmovsr(destination.AsFpuRegister<SRegister>(), source.AsRegister<Register>()); } else { DCHECK(destination.IsStackSlot()); __ StoreToOffset(kStoreWord, source.AsRegister<Register>(), @@ -4990,7 +5016,9 @@ void ParallelMoveResolverARM::EmitMove(size_t index) { __ StoreToOffset(kStoreWord, IP, SP, destination.GetStackIndex()); } } else if (source.IsFpuRegister()) { - if (destination.IsFpuRegister()) { + if (destination.IsRegister()) { + __ vmovrs(destination.AsRegister<Register>(), source.AsFpuRegister<SRegister>()); + } else if (destination.IsFpuRegister()) { __ vmovs(destination.AsFpuRegister<SRegister>(), source.AsFpuRegister<SRegister>()); } else { DCHECK(destination.IsStackSlot()); @@ -5014,6 +5042,10 @@ void ParallelMoveResolverARM::EmitMove(size_t index) { if (destination.IsRegisterPair()) { __ Mov(destination.AsRegisterPairLow<Register>(), source.AsRegisterPairLow<Register>()); __ Mov(destination.AsRegisterPairHigh<Register>(), source.AsRegisterPairHigh<Register>()); + } else if (destination.IsFpuRegisterPair()) { + __ vmovdrr(FromLowSToD(destination.AsFpuRegisterPairLow<SRegister>()), + source.AsRegisterPairLow<Register>(), + source.AsRegisterPairHigh<Register>()); } else { DCHECK(destination.IsDoubleStackSlot()) << destination; DCHECK(ExpectedPairLayout(source)); @@ -5021,7 +5053,11 @@ void ParallelMoveResolverARM::EmitMove(size_t index) { kStoreWordPair, source.AsRegisterPairLow<Register>(), SP, destination.GetStackIndex()); } } else if (source.IsFpuRegisterPair()) { - if (destination.IsFpuRegisterPair()) { + if (destination.IsRegisterPair()) { + __ vmovrrd(destination.AsRegisterPairLow<Register>(), + destination.AsRegisterPairHigh<Register>(), + FromLowSToD(source.AsFpuRegisterPairLow<SRegister>())); + } else if (destination.IsFpuRegisterPair()) { __ vmovd(FromLowSToD(destination.AsFpuRegisterPairLow<SRegister>()), FromLowSToD(source.AsFpuRegisterPairLow<SRegister>())); } else { diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc index 788c3a62d5..ec5ca3d83b 100644 --- a/compiler/optimizing/code_generator_arm64.cc +++ b/compiler/optimizing/code_generator_arm64.cc @@ -3004,6 +3004,32 @@ void InstructionCodeGeneratorARM64::VisitDeoptimize(HDeoptimize* deoptimize) { /* false_target */ nullptr); } +void LocationsBuilderARM64::VisitSelect(HSelect* select) { + LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(select); + if (Primitive::IsFloatingPointType(select->GetType())) { + locations->SetInAt(0, Location::RequiresFpuRegister()); + locations->SetInAt(1, Location::RequiresFpuRegister()); + } else { + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RequiresRegister()); + } + if (IsBooleanValueOrMaterializedCondition(select->GetCondition())) { + locations->SetInAt(2, Location::RequiresRegister()); + } + locations->SetOut(Location::SameAsFirstInput()); +} + +void InstructionCodeGeneratorARM64::VisitSelect(HSelect* select) { + LocationSummary* locations = select->GetLocations(); + vixl::Label false_target; + GenerateTestAndBranch(select, + /* condition_input_index */ 2, + /* true_target */ nullptr, + &false_target); + codegen_->MoveLocation(locations->Out(), locations->InAt(1), select->GetType()); + __ Bind(&false_target); +} + void LocationsBuilderARM64::VisitNativeDebugInfo(HNativeDebugInfo* info) { new (GetGraph()->GetArena()) LocationSummary(info); } diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc index fec5811082..a2f85fe05c 100644 --- a/compiler/optimizing/code_generator_mips.cc +++ b/compiler/optimizing/code_generator_mips.cc @@ -3381,6 +3381,32 @@ void InstructionCodeGeneratorMIPS::VisitDeoptimize(HDeoptimize* deoptimize) { /* false_target */ nullptr); } +void LocationsBuilderMIPS::VisitSelect(HSelect* select) { + LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(select); + if (Primitive::IsFloatingPointType(select->GetType())) { + locations->SetInAt(0, Location::RequiresFpuRegister()); + locations->SetInAt(1, Location::RequiresFpuRegister()); + } else { + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RequiresRegister()); + } + if (IsBooleanValueOrMaterializedCondition(select->GetCondition())) { + locations->SetInAt(2, Location::RequiresRegister()); + } + locations->SetOut(Location::SameAsFirstInput()); +} + +void InstructionCodeGeneratorMIPS::VisitSelect(HSelect* select) { + LocationSummary* locations = select->GetLocations(); + MipsLabel false_target; + GenerateTestAndBranch(select, + /* condition_input_index */ 2, + /* true_target */ nullptr, + &false_target); + codegen_->MoveLocation(locations->Out(), locations->InAt(1), select->GetType()); + __ Bind(&false_target); +} + void LocationsBuilderMIPS::VisitNativeDebugInfo(HNativeDebugInfo* info) { new (GetGraph()->GetArena()) LocationSummary(info); } diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc index e5a5fd4096..930a3ecdee 100644 --- a/compiler/optimizing/code_generator_mips64.cc +++ b/compiler/optimizing/code_generator_mips64.cc @@ -2748,6 +2748,32 @@ void InstructionCodeGeneratorMIPS64::VisitDeoptimize(HDeoptimize* deoptimize) { /* false_target */ nullptr); } +void LocationsBuilderMIPS64::VisitSelect(HSelect* select) { + LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(select); + if (Primitive::IsFloatingPointType(select->GetType())) { + locations->SetInAt(0, Location::RequiresFpuRegister()); + locations->SetInAt(1, Location::RequiresFpuRegister()); + } else { + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RequiresRegister()); + } + if (IsBooleanValueOrMaterializedCondition(select->GetCondition())) { + locations->SetInAt(2, Location::RequiresRegister()); + } + locations->SetOut(Location::SameAsFirstInput()); +} + +void InstructionCodeGeneratorMIPS64::VisitSelect(HSelect* select) { + LocationSummary* locations = select->GetLocations(); + Mips64Label false_target; + GenerateTestAndBranch(select, + /* condition_input_index */ 2, + /* true_target */ nullptr, + &false_target); + codegen_->MoveLocation(locations->Out(), locations->InAt(1), select->GetType()); + __ Bind(&false_target); +} + void LocationsBuilderMIPS64::VisitNativeDebugInfo(HNativeDebugInfo* info) { new (GetGraph()->GetArena()) LocationSummary(info); } diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index a4a8c7c103..6a4f9243f5 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -1218,11 +1218,14 @@ void CodeGeneratorX86::MoveConstant(Location location, int32_t value) { } void CodeGeneratorX86::MoveLocation(Location dst, Location src, Primitive::Type dst_type) { - if (Primitive::Is64BitType(dst_type)) { - Move64(dst, src); + HParallelMove move(GetGraph()->GetArena()); + if (dst_type == Primitive::kPrimLong && !src.IsConstant() && !src.IsFpuRegister()) { + move.AddMove(src.ToLow(), dst.ToLow(), Primitive::kPrimInt, nullptr); + move.AddMove(src.ToHigh(), dst.ToHigh(), Primitive::kPrimInt, nullptr); } else { - Move32(dst, src); + move.AddMove(src, dst, dst_type, nullptr); } + GetMoveResolver()->EmitNativeCode(&move); } void CodeGeneratorX86::AddLocationAsTemp(Location location, LocationSummary* locations) { @@ -1559,10 +1562,36 @@ void LocationsBuilderX86::VisitDeoptimize(HDeoptimize* deoptimize) { void InstructionCodeGeneratorX86::VisitDeoptimize(HDeoptimize* deoptimize) { SlowPathCode* slow_path = deopt_slow_paths_.NewSlowPath<DeoptimizationSlowPathX86>(deoptimize); - GenerateTestAndBranch(deoptimize, - /* condition_input_index */ 0, - slow_path->GetEntryLabel(), - /* false_target */ static_cast<Label*>(nullptr)); + GenerateTestAndBranch<Label>(deoptimize, + /* condition_input_index */ 0, + slow_path->GetEntryLabel(), + /* false_target */ nullptr); +} + +void LocationsBuilderX86::VisitSelect(HSelect* select) { + LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(select); + Primitive::Type select_type = select->GetType(); + HInstruction* cond = select->GetCondition(); + + if (Primitive::IsFloatingPointType(select_type)) { + locations->SetInAt(0, Location::RequiresFpuRegister()); + } else { + locations->SetInAt(0, Location::RequiresRegister()); + } + locations->SetInAt(1, Location::Any()); + if (IsBooleanValueOrMaterializedCondition(cond)) { + locations->SetInAt(2, Location::Any()); + } + locations->SetOut(Location::SameAsFirstInput()); +} + +void InstructionCodeGeneratorX86::VisitSelect(HSelect* select) { + LocationSummary* locations = select->GetLocations(); + NearLabel false_target; + GenerateTestAndBranch<NearLabel>( + select, /* condition_input_index */ 2, /* true_target */ nullptr, &false_target); + codegen_->MoveLocation(locations->Out(), locations->InAt(1), select->GetType()); + __ Bind(&false_target); } void LocationsBuilderX86::VisitNativeDebugInfo(HNativeDebugInfo* info) { @@ -5481,13 +5510,31 @@ void ParallelMoveResolverX86::EmitMove(size_t index) { if (source.IsRegister()) { if (destination.IsRegister()) { __ movl(destination.AsRegister<Register>(), source.AsRegister<Register>()); + } else if (destination.IsFpuRegister()) { + __ movd(destination.AsFpuRegister<XmmRegister>(), source.AsRegister<Register>()); } else { DCHECK(destination.IsStackSlot()); __ movl(Address(ESP, destination.GetStackIndex()), source.AsRegister<Register>()); } + } else if (source.IsRegisterPair()) { + size_t elem_size = Primitive::ComponentSize(Primitive::kPrimInt); + // Create stack space for 2 elements. + __ subl(ESP, Immediate(2 * elem_size)); + __ movl(Address(ESP, 0), source.AsRegisterPairLow<Register>()); + __ movl(Address(ESP, elem_size), source.AsRegisterPairHigh<Register>()); + __ movsd(destination.AsFpuRegister<XmmRegister>(), Address(ESP, 0)); + // And remove the temporary stack space we allocated. + __ addl(ESP, Immediate(2 * elem_size)); } else if (source.IsFpuRegister()) { - if (destination.IsFpuRegister()) { + if (destination.IsRegister()) { + __ movd(destination.AsRegister<Register>(), source.AsFpuRegister<XmmRegister>()); + } else if (destination.IsFpuRegister()) { __ movaps(destination.AsFpuRegister<XmmRegister>(), source.AsFpuRegister<XmmRegister>()); + } else if (destination.IsRegisterPair()) { + XmmRegister src_reg = source.AsFpuRegister<XmmRegister>(); + __ movd(destination.AsRegisterPairLow<Register>(), src_reg); + __ psrlq(src_reg, Immediate(32)); + __ movd(destination.AsRegisterPairHigh<Register>(), src_reg); } else if (destination.IsStackSlot()) { __ movss(Address(ESP, destination.GetStackIndex()), source.AsFpuRegister<XmmRegister>()); } else { @@ -5504,7 +5551,11 @@ void ParallelMoveResolverX86::EmitMove(size_t index) { MoveMemoryToMemory32(destination.GetStackIndex(), source.GetStackIndex()); } } else if (source.IsDoubleStackSlot()) { - if (destination.IsFpuRegister()) { + if (destination.IsRegisterPair()) { + __ movl(destination.AsRegisterPairLow<Register>(), Address(ESP, source.GetStackIndex())); + __ movl(destination.AsRegisterPairHigh<Register>(), + Address(ESP, source.GetHighStackIndex(kX86WordSize))); + } else if (destination.IsFpuRegister()) { __ movsd(destination.AsFpuRegister<XmmRegister>(), Address(ESP, source.GetStackIndex())); } else { DCHECK(destination.IsDoubleStackSlot()) << destination; diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc index 1781f419f1..895e7c343e 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -1558,10 +1558,36 @@ void LocationsBuilderX86_64::VisitDeoptimize(HDeoptimize* deoptimize) { void InstructionCodeGeneratorX86_64::VisitDeoptimize(HDeoptimize* deoptimize) { SlowPathCode* slow_path = deopt_slow_paths_.NewSlowPath<DeoptimizationSlowPathX86_64>(deoptimize); - GenerateTestAndBranch(deoptimize, - /* condition_input_index */ 0, - slow_path->GetEntryLabel(), - /* false_target */ static_cast<Label*>(nullptr)); + GenerateTestAndBranch<Label>(deoptimize, + /* condition_input_index */ 0, + slow_path->GetEntryLabel(), + /* false_target */ nullptr); +} + +void LocationsBuilderX86_64::VisitSelect(HSelect* select) { + LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(select); + if (Primitive::IsFloatingPointType(select->GetType())) { + locations->SetInAt(0, Location::RequiresFpuRegister()); + locations->SetInAt(1, Location::RequiresFpuRegister()); + } else { + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RequiresRegister()); + } + if (IsBooleanValueOrMaterializedCondition(select->GetCondition())) { + locations->SetInAt(2, Location::RequiresRegister()); + } + locations->SetOut(Location::SameAsFirstInput()); +} + +void InstructionCodeGeneratorX86_64::VisitSelect(HSelect* select) { + LocationSummary* locations = select->GetLocations(); + NearLabel false_target; + GenerateTestAndBranch<NearLabel>(select, + /* condition_input_index */ 2, + /* true_target */ nullptr, + &false_target); + codegen_->MoveLocation(locations->Out(), locations->InAt(1), select->GetType()); + __ Bind(&false_target); } void LocationsBuilderX86_64::VisitNativeDebugInfo(HNativeDebugInfo* info) { diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc index 31136772c7..962e77dfc9 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -859,8 +859,12 @@ void SSAChecker::HandleBooleanInput(HInstruction* instruction, size_t input_inde value)); } } else if (input->GetType() == Primitive::kPrimInt - && (input->IsPhi() || input->IsAnd() || input->IsOr() || input->IsXor())) { - // TODO: We need a data-flow analysis to determine if the Phi or + && (input->IsPhi() || + input->IsAnd() || + input->IsOr() || + input->IsXor() || + input->IsSelect())) { + // TODO: We need a data-flow analysis to determine if the Phi or Select or // binary operation is actually Boolean. Allow for now. } else if (input->GetType() != Primitive::kPrimBoolean) { AddError(StringPrintf( @@ -893,6 +897,11 @@ void SSAChecker::VisitIf(HIf* instruction) { HandleBooleanInput(instruction, 0); } +void SSAChecker::VisitSelect(HSelect* instruction) { + VisitInstruction(instruction); + HandleBooleanInput(instruction, 2); +} + void SSAChecker::VisitBooleanNot(HBooleanNot* instruction) { VisitInstruction(instruction); HandleBooleanInput(instruction, 0); diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h index 2e16bfe245..8724cde5dd 100644 --- a/compiler/optimizing/graph_checker.h +++ b/compiler/optimizing/graph_checker.h @@ -126,6 +126,7 @@ class SSAChecker : public GraphChecker { void VisitCondition(HCondition* op) OVERRIDE; void VisitIf(HIf* instruction) OVERRIDE; void VisitPackedSwitch(HPackedSwitch* instruction) OVERRIDE; + void VisitSelect(HSelect* instruction) OVERRIDE; void VisitBooleanNot(HBooleanNot* instruction) OVERRIDE; void VisitConstant(HConstant* instruction) OVERRIDE; void VisitBoundType(HBoundType* instruction) OVERRIDE; diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc index 49fc8c71b3..7d3a7238dc 100644 --- a/compiler/optimizing/instruction_simplifier.cc +++ b/compiler/optimizing/instruction_simplifier.cc @@ -76,6 +76,8 @@ class InstructionSimplifierVisitor : public HGraphDelegateVisitor { void VisitSub(HSub* instruction) OVERRIDE; void VisitUShr(HUShr* instruction) OVERRIDE; void VisitXor(HXor* instruction) OVERRIDE; + void VisitSelect(HSelect* select) OVERRIDE; + void VisitIf(HIf* instruction) OVERRIDE; void VisitInstanceOf(HInstanceOf* instruction) OVERRIDE; void VisitInvoke(HInvoke* invoke) OVERRIDE; void VisitDeoptimize(HDeoptimize* deoptimize) OVERRIDE; @@ -559,14 +561,86 @@ void InstructionSimplifierVisitor::VisitNotEqual(HNotEqual* not_equal) { } void InstructionSimplifierVisitor::VisitBooleanNot(HBooleanNot* bool_not) { - HInstruction* parent = bool_not->InputAt(0); - if (parent->IsBooleanNot()) { - HInstruction* value = parent->InputAt(0); - // Replace (!(!bool_value)) with bool_value - bool_not->ReplaceWith(value); + HInstruction* input = bool_not->InputAt(0); + HInstruction* replace_with = nullptr; + + if (input->IsIntConstant()) { + // Replace !(true/false) with false/true. + if (input->AsIntConstant()->IsOne()) { + replace_with = GetGraph()->GetIntConstant(0); + } else { + DCHECK(input->AsIntConstant()->IsZero()); + replace_with = GetGraph()->GetIntConstant(1); + } + } else if (input->IsBooleanNot()) { + // Replace (!(!bool_value)) with bool_value. + replace_with = input->InputAt(0); + } else if (input->IsCondition() && + // Don't change FP compares. The definition of compares involving + // NaNs forces the compares to be done as written by the user. + !Primitive::IsFloatingPointType(input->InputAt(0)->GetType())) { + // Replace condition with its opposite. + replace_with = GetGraph()->InsertOppositeCondition(input->AsCondition(), bool_not); + } + + if (replace_with != nullptr) { + bool_not->ReplaceWith(replace_with); bool_not->GetBlock()->RemoveInstruction(bool_not); - // It is possible that `parent` is dead at this point but we leave - // its removal to DCE for simplicity. + RecordSimplification(); + } +} + +void InstructionSimplifierVisitor::VisitSelect(HSelect* select) { + HInstruction* replace_with = nullptr; + HInstruction* condition = select->GetCondition(); + HInstruction* true_value = select->GetTrueValue(); + HInstruction* false_value = select->GetFalseValue(); + + if (condition->IsBooleanNot()) { + // Change ((!cond) ? x : y) to (cond ? y : x). + condition = condition->InputAt(0); + std::swap(true_value, false_value); + select->ReplaceInput(false_value, 0); + select->ReplaceInput(true_value, 1); + select->ReplaceInput(condition, 2); + RecordSimplification(); + } + + if (true_value == false_value) { + // Replace (cond ? x : x) with (x). + replace_with = true_value; + } else if (condition->IsIntConstant()) { + if (condition->AsIntConstant()->IsOne()) { + // Replace (true ? x : y) with (x). + replace_with = true_value; + } else { + // Replace (false ? x : y) with (y). + DCHECK(condition->AsIntConstant()->IsZero()); + replace_with = false_value; + } + } else if (true_value->IsIntConstant() && false_value->IsIntConstant()) { + if (true_value->AsIntConstant()->IsOne() && false_value->AsIntConstant()->IsZero()) { + // Replace (cond ? true : false) with (cond). + replace_with = condition; + } else if (true_value->AsIntConstant()->IsZero() && false_value->AsIntConstant()->IsOne()) { + // Replace (cond ? false : true) with (!cond). + replace_with = GetGraph()->InsertOppositeCondition(condition, select); + } + } + + if (replace_with != nullptr) { + select->ReplaceWith(replace_with); + select->GetBlock()->RemoveInstruction(select); + RecordSimplification(); + } +} + +void InstructionSimplifierVisitor::VisitIf(HIf* instruction) { + HInstruction* condition = instruction->InputAt(0); + if (condition->IsBooleanNot()) { + // Swap successors if input is negated. + instruction->ReplaceInput(condition->InputAt(0), 0); + instruction->GetBlock()->SwapSuccessors(); RecordSimplification(); } } diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 92f758d61d..c057eca434 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -722,6 +722,22 @@ void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial, RemoveInstruction(initial); } +void HBasicBlock::MoveInstructionBefore(HInstruction* insn, HInstruction* cursor) { + DCHECK(!cursor->IsPhi()); + DCHECK(!insn->IsPhi()); + DCHECK(!insn->IsControlFlow()); + DCHECK(insn->CanBeMoved()); + DCHECK(!insn->HasSideEffects()); + + HBasicBlock* from_block = insn->GetBlock(); + HBasicBlock* to_block = cursor->GetBlock(); + DCHECK(from_block != to_block); + + from_block->RemoveInstruction(insn, /* ensure_safety */ false); + insn->SetBlock(to_block); + to_block->instructions_.InsertInstructionBefore(insn, cursor); +} + static void Add(HInstructionList* instruction_list, HBasicBlock* block, HInstruction* instruction) { diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 922696bb5d..4de3f8abb5 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -1011,6 +1011,7 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { // Replace instruction `initial` with `replacement` within this block. void ReplaceAndRemoveInstructionWith(HInstruction* initial, HInstruction* replacement); + void MoveInstructionBefore(HInstruction* insn, HInstruction* cursor); void AddPhi(HPhi* phi); void InsertPhiAfter(HPhi* instruction, HPhi* cursor); // RemoveInstruction and RemovePhi delete a given instruction from the respective @@ -1220,6 +1221,7 @@ class HLoopInformationOutwardIterator : public ValueObject { M(UnresolvedInstanceFieldSet, Instruction) \ M(UnresolvedStaticFieldGet, Instruction) \ M(UnresolvedStaticFieldSet, Instruction) \ + M(Select, Instruction) \ M(StoreLocal, Instruction) \ M(Sub, BinaryOperation) \ M(SuspendCheck, Instruction) \ @@ -5586,6 +5588,41 @@ class HMonitorOperation : public HTemplateInstruction<1> { DISALLOW_COPY_AND_ASSIGN(HMonitorOperation); }; +class HSelect : public HExpression<3> { + public: + HSelect(HInstruction* condition, + HInstruction* true_value, + HInstruction* false_value, + uint32_t dex_pc) + : HExpression(HPhi::ToPhiType(true_value->GetType()), SideEffects::None(), dex_pc) { + DCHECK_EQ(HPhi::ToPhiType(true_value->GetType()), HPhi::ToPhiType(false_value->GetType())); + + // First input must be `true_value` or `false_value` to allow codegens to + // use the SameAsFirstInput allocation policy. We make it `false_value`, so + // that architectures which implement HSelect as a conditional move also + // will not need to invert the condition. + SetRawInputAt(0, false_value); + SetRawInputAt(1, true_value); + SetRawInputAt(2, condition); + } + + HInstruction* GetFalseValue() const { return InputAt(0); } + HInstruction* GetTrueValue() const { return InputAt(1); } + HInstruction* GetCondition() const { return InputAt(2); } + + bool CanBeMoved() const OVERRIDE { return true; } + bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; } + + bool CanBeNull() const OVERRIDE { + return GetTrueValue()->CanBeNull() || GetFalseValue()->CanBeNull(); + } + + DECLARE_INSTRUCTION(Select); + + private: + DISALLOW_COPY_AND_ASSIGN(HSelect); +}; + class MoveOperands : public ArenaObject<kArenaAllocMoveOperands> { public: MoveOperands(Location source, diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 3fac914017..bdc664b3eb 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -38,7 +38,6 @@ #include "base/dumpable.h" #include "base/macros.h" #include "base/timing_logger.h" -#include "boolean_simplifier.h" #include "bounds_check_elimination.h" #include "builder.h" #include "code_generator.h" @@ -73,6 +72,7 @@ #include "reference_type_propagation.h" #include "register_allocator.h" #include "oat_quick_method_header.h" +#include "select_generator.h" #include "sharpening.h" #include "side_effects_analysis.h" #include "ssa_builder.h" @@ -512,7 +512,7 @@ static void RunOptimizations(HGraph* graph, graph, stats, HDeadCodeElimination::kFinalDeadCodeEliminationPassName); HConstantFolding* fold1 = new (arena) HConstantFolding(graph); InstructionSimplifier* simplify1 = new (arena) InstructionSimplifier(graph, stats); - HBooleanSimplifier* boolean_simplify = new (arena) HBooleanSimplifier(graph); + HSelectGenerator* select_generator = new (arena) HSelectGenerator(graph); HConstantFolding* fold2 = new (arena) HConstantFolding(graph, "constant_folding_after_inlining"); HConstantFolding* fold3 = new (arena) HConstantFolding(graph, "constant_folding_after_bce"); SideEffectsAnalysis* side_effects = new (arena) SideEffectsAnalysis(graph); @@ -540,9 +540,9 @@ static void RunOptimizations(HGraph* graph, MaybeRunInliner(graph, codegen, driver, stats, dex_compilation_unit, pass_observer, handles); HOptimization* optimizations2[] = { - // BooleanSimplifier depends on the InstructionSimplifier removing + // SelectGenerator depends on the InstructionSimplifier removing // redundant suspend checks to recognize empty blocks. - boolean_simplify, + select_generator, fold2, // TODO: if we don't inline we can also skip fold2. side_effects, gvn, diff --git a/compiler/optimizing/prepare_for_register_allocation.cc b/compiler/optimizing/prepare_for_register_allocation.cc index ec0fc3a814..324d84f3db 100644 --- a/compiler/optimizing/prepare_for_register_allocation.cc +++ b/compiler/optimizing/prepare_for_register_allocation.cc @@ -137,6 +137,18 @@ bool PrepareForRegisterAllocation::CanEmitConditionAt(HCondition* condition, return true; } + if (user->IsSelect() && user->AsSelect()->GetCondition() == condition) { + if (GetGraph()->GetInstructionSet() == kX86) { + // Long values and long condition inputs result in 8 required core registers. + // We don't have that many on x86. Materialize the condition in such case. + return user->GetType() != Primitive::kPrimLong || + condition->InputAt(1)->GetType() != Primitive::kPrimLong || + condition->InputAt(1)->IsConstant(); + } else { + return true; + } + } + return false; } diff --git a/compiler/optimizing/select_generator.cc b/compiler/optimizing/select_generator.cc new file mode 100644 index 0000000000..105b30ae5d --- /dev/null +++ b/compiler/optimizing/select_generator.cc @@ -0,0 +1,152 @@ +/* + * Copyright (C) 2016 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "select_generator.h" + +namespace art { + +static constexpr size_t kMaxInstructionsInBranch = 1u; + +// Returns true if `block` has only one predecessor, ends with a Goto and +// contains at most `kMaxInstructionsInBranch` other movable instruction with +// no side-effects. +static bool IsSimpleBlock(HBasicBlock* block) { + if (block->GetPredecessors().size() != 1u) { + return false; + } + DCHECK(block->GetPhis().IsEmpty()); + + size_t num_instructions = 0u; + for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { + HInstruction* instruction = it.Current(); + if (instruction->IsControlFlow()) { + return instruction->IsGoto() && num_instructions <= kMaxInstructionsInBranch; + } else if (instruction->CanBeMoved() && !instruction->HasSideEffects()) { + num_instructions++; + } else { + return false; + } + } + + LOG(FATAL) << "Unreachable"; + UNREACHABLE(); +} + +// Returns true if 'block1' and 'block2' are empty, merge into the same single +// successor and the successor can only be reached from them. +static bool BlocksMergeTogether(HBasicBlock* block1, HBasicBlock* block2) { + return block1->GetSingleSuccessor() == block2->GetSingleSuccessor(); +} + +// Returns nullptr if `block` has either no phis or there is more than one phi +// with different inputs at `index1` and `index2`. Otherwise returns that phi. +static HPhi* GetSingleChangedPhi(HBasicBlock* block, size_t index1, size_t index2) { + DCHECK_NE(index1, index2); + + HPhi* select_phi = nullptr; + for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { + HPhi* phi = it.Current()->AsPhi(); + if (phi->InputAt(index1) != phi->InputAt(index2)) { + if (select_phi == nullptr) { + // First phi with different inputs for the two indices found. + select_phi = phi; + } else { + // More than one phis has different inputs for the two indices. + return nullptr; + } + } + } + return select_phi; +} + +void HSelectGenerator::Run() { + // Iterate in post order in the unlikely case that removing one occurrence of + // the selection pattern empties a branch block of another occurrence. + // Otherwise the order does not matter. + for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + if (!block->EndsWithIf()) continue; + + // Find elements of the diamond pattern. + HIf* if_instruction = block->GetLastInstruction()->AsIf(); + HBasicBlock* true_block = if_instruction->IfTrueSuccessor(); + HBasicBlock* false_block = if_instruction->IfFalseSuccessor(); + DCHECK_NE(true_block, false_block); + if (!IsSimpleBlock(true_block) || + !IsSimpleBlock(false_block) || + !BlocksMergeTogether(true_block, false_block)) { + continue; + } + HBasicBlock* merge_block = true_block->GetSingleSuccessor(); + + // If the branches are not empty, move instructions in front of the If. + // TODO(dbrazdil): This puts an instruction between If and its condition. + // Implement moving of conditions to first users if possible. + if (!true_block->IsSingleGoto()) { + true_block->MoveInstructionBefore(true_block->GetFirstInstruction(), if_instruction); + } + if (!false_block->IsSingleGoto()) { + false_block->MoveInstructionBefore(false_block->GetFirstInstruction(), if_instruction); + } + DCHECK(true_block->IsSingleGoto()); + DCHECK(false_block->IsSingleGoto()); + + // Find the resulting true/false values. + size_t predecessor_index_true = merge_block->GetPredecessorIndexOf(true_block); + size_t predecessor_index_false = merge_block->GetPredecessorIndexOf(false_block); + DCHECK_NE(predecessor_index_true, predecessor_index_false); + + HPhi* phi = GetSingleChangedPhi(merge_block, predecessor_index_true, predecessor_index_false); + if (phi == nullptr) { + continue; + } + HInstruction* true_value = phi->InputAt(predecessor_index_true); + HInstruction* false_value = phi->InputAt(predecessor_index_false); + + // Create the Select instruction and insert it in front of the If. + HSelect* select = new (graph_->GetArena()) HSelect(if_instruction->InputAt(0), + true_value, + false_value, + if_instruction->GetDexPc()); + if (phi->GetType() == Primitive::kPrimNot) { + select->SetReferenceTypeInfo(phi->GetReferenceTypeInfo()); + } + block->InsertInstructionBefore(select, if_instruction); + + // Remove the true branch which removes the corresponding Phi input. + // If left only with the false branch, the Phi is automatically removed. + phi->ReplaceInput(select, predecessor_index_false); + bool only_two_predecessors = (merge_block->GetPredecessors().size() == 2u); + true_block->DisconnectAndDelete(); + DCHECK_EQ(only_two_predecessors, phi->GetBlock() == nullptr); + + // Merge remaining blocks which are now connected with Goto. + DCHECK_EQ(block->GetSingleSuccessor(), false_block); + block->MergeWith(false_block); + if (only_two_predecessors) { + DCHECK_EQ(block->GetSingleSuccessor(), merge_block); + block->MergeWith(merge_block); + } + + // No need to update dominance information, as we are simplifying + // a simple diamond shape, where the join block is merged with the + // entry block. Any following blocks would have had the join block + // as a dominator, and `MergeWith` handles changing that to the + // entry block. + } +} + +} // namespace art diff --git a/compiler/optimizing/select_generator.h b/compiler/optimizing/select_generator.h new file mode 100644 index 0000000000..f9d6d4d8de --- /dev/null +++ b/compiler/optimizing/select_generator.h @@ -0,0 +1,63 @@ +/* + * Copyright (C) 2016 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/* + * This optimization recognizes the common diamond selection pattern and + * replaces it with an instance of the HSelect instruction. + * + * Recognized pattern: + * + * If [ Condition ] + * / \ + * false branch true branch + * \ / + * Phi [FalseValue, TrueValue] + * + * The pattern will be simplified if `true_branch` and `false_branch` each + * contain at most one instruction without any side effects. + * + * Blocks are merged into one and Select replaces the If and the Phi: + * true branch + * false branch + * Select [FalseValue, TrueValue, Condition] + * + * Note: In order to recognize no side-effect blocks, this optimization must be + * run after the instruction simplifier has removed redundant suspend checks. + */ + +#ifndef ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_ +#define ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_ + +#include "optimization.h" + +namespace art { + +class HSelectGenerator : public HOptimization { + public: + explicit HSelectGenerator(HGraph* graph) + : HOptimization(graph, kSelectGeneratorPassName) {} + + void Run() OVERRIDE; + + static constexpr const char* kSelectGeneratorPassName = "select_generator"; + + private: + DISALLOW_COPY_AND_ASSIGN(HSelectGenerator); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_ |