diff options
Diffstat (limited to 'compiler/optimizing')
23 files changed, 570 insertions, 371 deletions
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc index 4dd0d26b89..1af684683b 100644 --- a/compiler/optimizing/builder.cc +++ b/compiler/optimizing/builder.cc @@ -1817,7 +1817,12 @@ void HGraphBuilder::BuildTypeCheck(const Instruction& instruction, UpdateLocal(destination, current_block_->GetLastInstruction(), dex_pc); } else { DCHECK_EQ(instruction.Opcode(), Instruction::CHECK_CAST); + // We emit a CheckCast followed by a BoundType. CheckCast is a statement + // which may throw. If it succeeds BoundType sets the new type of `object` + // for all subsequent uses. current_block_->AddInstruction(new (arena_) HCheckCast(object, cls, check_kind, dex_pc)); + current_block_->AddInstruction(new (arena_) HBoundType(object, dex_pc)); + UpdateLocal(reference, current_block_->GetLastInstruction(), dex_pc); } } diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc index 07efdee22d..4648606da8 100644 --- a/compiler/optimizing/code_generator_mips.cc +++ b/compiler/optimizing/code_generator_mips.cc @@ -1191,17 +1191,16 @@ void CodeGeneratorMIPS::InvokeRuntime(int32_t entry_point_offset, uint32_t dex_pc, SlowPathCode* slow_path, bool is_direct_entrypoint) { + __ LoadFromOffset(kLoadWord, T9, TR, entry_point_offset); + __ Jalr(T9); if (is_direct_entrypoint) { // Reserve argument space on stack (for $a0-$a3) for // entrypoints that directly reference native implementations. // Called function may use this space to store $a0-$a3 regs. - __ IncreaseFrameSize(kMipsDirectEntrypointRuntimeOffset); - } - __ LoadFromOffset(kLoadWord, T9, TR, entry_point_offset); - __ Jalr(T9); - __ Nop(); - if (is_direct_entrypoint) { + __ IncreaseFrameSize(kMipsDirectEntrypointRuntimeOffset); // Single instruction in delay slot. __ DecreaseFrameSize(kMipsDirectEntrypointRuntimeOffset); + } else { + __ Nop(); // In delay slot. } RecordPcInfo(instruction, dex_pc, slow_path); } @@ -1275,15 +1274,9 @@ void LocationsBuilderMIPS::HandleBinaryOp(HBinaryOperation* instruction) { } case Primitive::kPrimLong: { - // TODO: can 2nd param be const? locations->SetInAt(0, Location::RequiresRegister()); - locations->SetInAt(1, Location::RequiresRegister()); - if (instruction->IsAdd() || instruction->IsSub()) { - locations->SetOut(Location::RequiresRegister(), Location::kOutputOverlap); - } else { - DCHECK(instruction->IsAnd() || instruction->IsOr() || instruction->IsXor()); - locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); - } + locations->SetInAt(1, Location::RegisterOrConstant(instruction->InputAt(1))); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); break; } @@ -1350,34 +1343,142 @@ void InstructionCodeGeneratorMIPS::HandleBinaryOp(HBinaryOperation* instruction) } case Primitive::kPrimLong: { - // TODO: can 2nd param be const? Register dst_high = locations->Out().AsRegisterPairHigh<Register>(); Register dst_low = locations->Out().AsRegisterPairLow<Register>(); Register lhs_high = locations->InAt(0).AsRegisterPairHigh<Register>(); Register lhs_low = locations->InAt(0).AsRegisterPairLow<Register>(); - Register rhs_high = locations->InAt(1).AsRegisterPairHigh<Register>(); - Register rhs_low = locations->InAt(1).AsRegisterPairLow<Register>(); - - if (instruction->IsAnd()) { - __ And(dst_low, lhs_low, rhs_low); - __ And(dst_high, lhs_high, rhs_high); - } else if (instruction->IsOr()) { - __ Or(dst_low, lhs_low, rhs_low); - __ Or(dst_high, lhs_high, rhs_high); - } else if (instruction->IsXor()) { - __ Xor(dst_low, lhs_low, rhs_low); - __ Xor(dst_high, lhs_high, rhs_high); - } else if (instruction->IsAdd()) { - __ Addu(dst_low, lhs_low, rhs_low); - __ Sltu(TMP, dst_low, lhs_low); - __ Addu(dst_high, lhs_high, rhs_high); - __ Addu(dst_high, dst_high, TMP); + Location rhs_location = locations->InAt(1); + bool use_imm = rhs_location.IsConstant(); + if (!use_imm) { + Register rhs_high = rhs_location.AsRegisterPairHigh<Register>(); + Register rhs_low = rhs_location.AsRegisterPairLow<Register>(); + if (instruction->IsAnd()) { + __ And(dst_low, lhs_low, rhs_low); + __ And(dst_high, lhs_high, rhs_high); + } else if (instruction->IsOr()) { + __ Or(dst_low, lhs_low, rhs_low); + __ Or(dst_high, lhs_high, rhs_high); + } else if (instruction->IsXor()) { + __ Xor(dst_low, lhs_low, rhs_low); + __ Xor(dst_high, lhs_high, rhs_high); + } else if (instruction->IsAdd()) { + if (lhs_low == rhs_low) { + // Special case for lhs = rhs and the sum potentially overwriting both lhs and rhs. + __ Slt(TMP, lhs_low, ZERO); + __ Addu(dst_low, lhs_low, rhs_low); + } else { + __ Addu(dst_low, lhs_low, rhs_low); + // If the sum overwrites rhs, lhs remains unchanged, otherwise rhs remains unchanged. + __ Sltu(TMP, dst_low, (dst_low == rhs_low) ? lhs_low : rhs_low); + } + __ Addu(dst_high, lhs_high, rhs_high); + __ Addu(dst_high, dst_high, TMP); + } else { + DCHECK(instruction->IsSub()); + __ Sltu(TMP, lhs_low, rhs_low); + __ Subu(dst_low, lhs_low, rhs_low); + __ Subu(dst_high, lhs_high, rhs_high); + __ Subu(dst_high, dst_high, TMP); + } } else { - DCHECK(instruction->IsSub()); - __ Subu(dst_low, lhs_low, rhs_low); - __ Sltu(TMP, lhs_low, dst_low); - __ Subu(dst_high, lhs_high, rhs_high); - __ Subu(dst_high, dst_high, TMP); + int64_t value = CodeGenerator::GetInt64ValueOf(rhs_location.GetConstant()->AsConstant()); + if (instruction->IsOr()) { + uint32_t low = Low32Bits(value); + uint32_t high = High32Bits(value); + if (IsUint<16>(low)) { + if (dst_low != lhs_low || low != 0) { + __ Ori(dst_low, lhs_low, low); + } + } else { + __ LoadConst32(TMP, low); + __ Or(dst_low, lhs_low, TMP); + } + if (IsUint<16>(high)) { + if (dst_high != lhs_high || high != 0) { + __ Ori(dst_high, lhs_high, high); + } + } else { + if (high != low) { + __ LoadConst32(TMP, high); + } + __ Or(dst_high, lhs_high, TMP); + } + } else if (instruction->IsXor()) { + uint32_t low = Low32Bits(value); + uint32_t high = High32Bits(value); + if (IsUint<16>(low)) { + if (dst_low != lhs_low || low != 0) { + __ Xori(dst_low, lhs_low, low); + } + } else { + __ LoadConst32(TMP, low); + __ Xor(dst_low, lhs_low, TMP); + } + if (IsUint<16>(high)) { + if (dst_high != lhs_high || high != 0) { + __ Xori(dst_high, lhs_high, high); + } + } else { + if (high != low) { + __ LoadConst32(TMP, high); + } + __ Xor(dst_high, lhs_high, TMP); + } + } else if (instruction->IsAnd()) { + uint32_t low = Low32Bits(value); + uint32_t high = High32Bits(value); + if (IsUint<16>(low)) { + __ Andi(dst_low, lhs_low, low); + } else if (low != 0xFFFFFFFF) { + __ LoadConst32(TMP, low); + __ And(dst_low, lhs_low, TMP); + } else if (dst_low != lhs_low) { + __ Move(dst_low, lhs_low); + } + if (IsUint<16>(high)) { + __ Andi(dst_high, lhs_high, high); + } else if (high != 0xFFFFFFFF) { + if (high != low) { + __ LoadConst32(TMP, high); + } + __ And(dst_high, lhs_high, TMP); + } else if (dst_high != lhs_high) { + __ Move(dst_high, lhs_high); + } + } else { + if (instruction->IsSub()) { + value = -value; + } else { + DCHECK(instruction->IsAdd()); + } + int32_t low = Low32Bits(value); + int32_t high = High32Bits(value); + if (IsInt<16>(low)) { + if (dst_low != lhs_low || low != 0) { + __ Addiu(dst_low, lhs_low, low); + } + if (low != 0) { + __ Sltiu(AT, dst_low, low); + } + } else { + __ LoadConst32(TMP, low); + __ Addu(dst_low, lhs_low, TMP); + __ Sltu(AT, dst_low, TMP); + } + if (IsInt<16>(high)) { + if (dst_high != lhs_high || high != 0) { + __ Addiu(dst_high, lhs_high, high); + } + } else { + if (high != low) { + __ LoadConst32(TMP, high); + } + __ Addu(dst_high, lhs_high, TMP); + } + if (low != 0) { + __ Addu(dst_high, dst_high, AT); + } + } } break; } @@ -1416,12 +1517,15 @@ void LocationsBuilderMIPS::HandleShift(HBinaryOperation* instr) { Primitive::Type type = instr->GetResultType(); switch (type) { case Primitive::kPrimInt: - case Primitive::kPrimLong: { + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RegisterOrConstant(instr->InputAt(1))); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); + break; + case Primitive::kPrimLong: locations->SetInAt(0, Location::RequiresRegister()); locations->SetInAt(1, Location::RegisterOrConstant(instr->InputAt(1))); locations->SetOut(Location::RequiresRegister()); break; - } default: LOG(FATAL) << "Unexpected shift type " << type; } @@ -1440,6 +1544,8 @@ void InstructionCodeGeneratorMIPS::HandleShift(HBinaryOperation* instr) { int64_t rhs_imm = use_imm ? CodeGenerator::GetInt64ValueOf(rhs_location.GetConstant()) : 0; uint32_t shift_mask = (type == Primitive::kPrimInt) ? kMaxIntShiftValue : kMaxLongShiftValue; uint32_t shift_value = rhs_imm & shift_mask; + // Is the INS (Insert Bit Field) instruction supported? + bool has_ins = codegen_->GetInstructionSetFeatures().IsMipsIsaRevGreaterThanEqual2(); switch (type) { case Primitive::kPrimInt: { @@ -1474,21 +1580,37 @@ void InstructionCodeGeneratorMIPS::HandleShift(HBinaryOperation* instr) { if (shift_value == 0) { codegen_->Move64(locations->Out(), locations->InAt(0)); } else if (shift_value < kMipsBitsPerWord) { - if (instr->IsShl()) { - __ Sll(dst_low, lhs_low, shift_value); - __ Srl(TMP, lhs_low, kMipsBitsPerWord - shift_value); - __ Sll(dst_high, lhs_high, shift_value); - __ Or(dst_high, dst_high, TMP); - } else if (instr->IsShr()) { - __ Sra(dst_high, lhs_high, shift_value); - __ Sll(TMP, lhs_high, kMipsBitsPerWord - shift_value); - __ Srl(dst_low, lhs_low, shift_value); - __ Or(dst_low, dst_low, TMP); + if (has_ins) { + if (instr->IsShl()) { + __ Srl(dst_high, lhs_low, kMipsBitsPerWord - shift_value); + __ Ins(dst_high, lhs_high, shift_value, kMipsBitsPerWord - shift_value); + __ Sll(dst_low, lhs_low, shift_value); + } else if (instr->IsShr()) { + __ Srl(dst_low, lhs_low, shift_value); + __ Ins(dst_low, lhs_high, kMipsBitsPerWord - shift_value, shift_value); + __ Sra(dst_high, lhs_high, shift_value); + } else { + __ Srl(dst_low, lhs_low, shift_value); + __ Ins(dst_low, lhs_high, kMipsBitsPerWord - shift_value, shift_value); + __ Srl(dst_high, lhs_high, shift_value); + } } else { - __ Srl(dst_high, lhs_high, shift_value); - __ Sll(TMP, lhs_high, kMipsBitsPerWord - shift_value); - __ Srl(dst_low, lhs_low, shift_value); - __ Or(dst_low, dst_low, TMP); + if (instr->IsShl()) { + __ Sll(dst_low, lhs_low, shift_value); + __ Srl(TMP, lhs_low, kMipsBitsPerWord - shift_value); + __ Sll(dst_high, lhs_high, shift_value); + __ Or(dst_high, dst_high, TMP); + } else if (instr->IsShr()) { + __ Sra(dst_high, lhs_high, shift_value); + __ Sll(TMP, lhs_high, kMipsBitsPerWord - shift_value); + __ Srl(dst_low, lhs_low, shift_value); + __ Or(dst_low, dst_low, TMP); + } else { + __ Srl(dst_high, lhs_high, shift_value); + __ Sll(TMP, lhs_high, kMipsBitsPerWord - shift_value); + __ Srl(dst_low, lhs_low, shift_value); + __ Or(dst_low, dst_low, TMP); + } } } else { shift_value -= kMipsBitsPerWord; diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index fd18917842..a808c27313 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -1335,9 +1335,10 @@ void LocationsBuilderX86::VisitExit(HExit* exit) { void InstructionCodeGeneratorX86::VisitExit(HExit* exit ATTRIBUTE_UNUSED) { } +template<class LabelType> void InstructionCodeGeneratorX86::GenerateFPJumps(HCondition* cond, - Label* true_label, - Label* false_label) { + LabelType* true_label, + LabelType* false_label) { if (cond->IsFPConditionTrueIfNaN()) { __ j(kUnordered, true_label); } else if (cond->IsFPConditionFalseIfNaN()) { @@ -1346,9 +1347,10 @@ void InstructionCodeGeneratorX86::GenerateFPJumps(HCondition* cond, __ j(X86UnsignedOrFPCondition(cond->GetCondition()), true_label); } +template<class LabelType> void InstructionCodeGeneratorX86::GenerateLongComparesAndJumps(HCondition* cond, - Label* true_label, - Label* false_label) { + LabelType* true_label, + LabelType* false_label) { LocationSummary* locations = cond->GetLocations(); Location left = locations->InAt(0); Location right = locations->InAt(1); @@ -1437,14 +1439,15 @@ void InstructionCodeGeneratorX86::GenerateLongComparesAndJumps(HCondition* cond, __ j(final_condition, true_label); } +template<class LabelType> void InstructionCodeGeneratorX86::GenerateCompareTestAndBranch(HCondition* condition, - Label* true_target_in, - Label* false_target_in) { + LabelType* true_target_in, + LabelType* false_target_in) { // Generated branching requires both targets to be explicit. If either of the // targets is nullptr (fallthrough) use and bind `fallthrough_target` instead. - Label fallthrough_target; - Label* true_target = true_target_in == nullptr ? &fallthrough_target : true_target_in; - Label* false_target = false_target_in == nullptr ? &fallthrough_target : false_target_in; + LabelType fallthrough_target; + LabelType* true_target = true_target_in == nullptr ? &fallthrough_target : true_target_in; + LabelType* false_target = false_target_in == nullptr ? &fallthrough_target : false_target_in; LocationSummary* locations = condition->GetLocations(); Location left = locations->InAt(0); @@ -1486,10 +1489,11 @@ static bool AreEflagsSetFrom(HInstruction* cond, HInstruction* branch) { !Primitive::IsFloatingPointType(cond->InputAt(0)->GetType()); } +template<class LabelType> void InstructionCodeGeneratorX86::GenerateTestAndBranch(HInstruction* instruction, size_t condition_input_index, - Label* true_target, - Label* false_target) { + LabelType* true_target, + LabelType* false_target) { HInstruction* cond = instruction->InputAt(condition_input_index); if (true_target == nullptr && false_target == nullptr) { @@ -1613,7 +1617,7 @@ void InstructionCodeGeneratorX86::VisitDeoptimize(HDeoptimize* deoptimize) { GenerateTestAndBranch(deoptimize, /* condition_input_index */ 0, slow_path->GetEntryLabel(), - /* false_target */ nullptr); + /* false_target */ static_cast<Label*>(nullptr)); } void LocationsBuilderX86::VisitNativeDebugInfo(HNativeDebugInfo* info) { @@ -1709,7 +1713,7 @@ void InstructionCodeGeneratorX86::HandleCondition(HCondition* cond) { Location lhs = locations->InAt(0); Location rhs = locations->InAt(1); Register reg = locations->Out().AsRegister<Register>(); - Label true_label, false_label; + NearLabel true_label, false_label; switch (cond->InputAt(0)->GetType()) { default: { diff --git a/compiler/optimizing/code_generator_x86.h b/compiler/optimizing/code_generator_x86.h index 3d343177d0..df7347658b 100644 --- a/compiler/optimizing/code_generator_x86.h +++ b/compiler/optimizing/code_generator_x86.h @@ -267,15 +267,22 @@ class InstructionCodeGeneratorX86 : public HGraphVisitor { void GenerateImplicitNullCheck(HNullCheck* instruction); void GenerateExplicitNullCheck(HNullCheck* instruction); + template<class LabelType> void GenerateTestAndBranch(HInstruction* instruction, size_t condition_input_index, - Label* true_target, - Label* false_target); + LabelType* true_target, + LabelType* false_target); + template<class LabelType> void GenerateCompareTestAndBranch(HCondition* condition, - Label* true_target, - Label* false_target); - void GenerateFPJumps(HCondition* cond, Label* true_label, Label* false_label); - void GenerateLongComparesAndJumps(HCondition* cond, Label* true_label, Label* false_label); + LabelType* true_target, + LabelType* false_target); + template<class LabelType> + void GenerateFPJumps(HCondition* cond, LabelType* true_label, LabelType* false_label); + template<class LabelType> + void GenerateLongComparesAndJumps(HCondition* cond, + LabelType* true_label, + LabelType* false_label); + void HandleGoto(HInstruction* got, HBasicBlock* successor); void GenPackedSwitchWithCompares(Register value_reg, int32_t lower_bound, diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc index 7c94a8cc71..76a4ce2e93 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -1370,9 +1370,10 @@ void LocationsBuilderX86_64::VisitExit(HExit* exit) { void InstructionCodeGeneratorX86_64::VisitExit(HExit* exit ATTRIBUTE_UNUSED) { } +template<class LabelType> void InstructionCodeGeneratorX86_64::GenerateFPJumps(HCondition* cond, - Label* true_label, - Label* false_label) { + LabelType* true_label, + LabelType* false_label) { if (cond->IsFPConditionTrueIfNaN()) { __ j(kUnordered, true_label); } else if (cond->IsFPConditionFalseIfNaN()) { @@ -1381,14 +1382,15 @@ void InstructionCodeGeneratorX86_64::GenerateFPJumps(HCondition* cond, __ j(X86_64FPCondition(cond->GetCondition()), true_label); } +template<class LabelType> void InstructionCodeGeneratorX86_64::GenerateCompareTestAndBranch(HCondition* condition, - Label* true_target_in, - Label* false_target_in) { + LabelType* true_target_in, + LabelType* false_target_in) { // Generated branching requires both targets to be explicit. If either of the // targets is nullptr (fallthrough) use and bind `fallthrough_target` instead. - Label fallthrough_target; - Label* true_target = true_target_in == nullptr ? &fallthrough_target : true_target_in; - Label* false_target = false_target_in == nullptr ? &fallthrough_target : false_target_in; + LabelType fallthrough_target; + LabelType* true_target = true_target_in == nullptr ? &fallthrough_target : true_target_in; + LabelType* false_target = false_target_in == nullptr ? &fallthrough_target : false_target_in; LocationSummary* locations = condition->GetLocations(); Location left = locations->InAt(0); @@ -1470,10 +1472,11 @@ static bool AreEflagsSetFrom(HInstruction* cond, HInstruction* branch) { !Primitive::IsFloatingPointType(cond->InputAt(0)->GetType()); } +template<class LabelType> void InstructionCodeGeneratorX86_64::GenerateTestAndBranch(HInstruction* instruction, size_t condition_input_index, - Label* true_target, - Label* false_target) { + LabelType* true_target, + LabelType* false_target) { HInstruction* cond = instruction->InputAt(condition_input_index); if (true_target == nullptr && false_target == nullptr) { @@ -1597,7 +1600,7 @@ void InstructionCodeGeneratorX86_64::VisitDeoptimize(HDeoptimize* deoptimize) { GenerateTestAndBranch(deoptimize, /* condition_input_index */ 0, slow_path->GetEntryLabel(), - /* false_target */ nullptr); + /* false_target */ static_cast<Label*>(nullptr)); } void LocationsBuilderX86_64::VisitNativeDebugInfo(HNativeDebugInfo* info) { @@ -1684,7 +1687,7 @@ void InstructionCodeGeneratorX86_64::HandleCondition(HCondition* cond) { Location lhs = locations->InAt(0); Location rhs = locations->InAt(1); CpuRegister reg = locations->Out().AsRegister<CpuRegister>(); - Label true_label, false_label; + NearLabel true_label, false_label; switch (cond->InputAt(0)->GetType()) { default: @@ -5747,7 +5750,7 @@ void InstructionCodeGeneratorX86_64::VisitCheckCast(HCheckCast* instruction) { is_type_check_slow_path_fatal); codegen_->AddSlowPath(type_check_slow_path); - Label done; + NearLabel done; // Avoid null check if we know obj is not null. if (instruction->MustDoNullCheck()) { __ testl(obj, obj); diff --git a/compiler/optimizing/code_generator_x86_64.h b/compiler/optimizing/code_generator_x86_64.h index 9995416138..c5e8a04da6 100644 --- a/compiler/optimizing/code_generator_x86_64.h +++ b/compiler/optimizing/code_generator_x86_64.h @@ -258,14 +258,18 @@ class InstructionCodeGeneratorX86_64 : public HGraphVisitor { void GenerateExplicitNullCheck(HNullCheck* instruction); void PushOntoFPStack(Location source, uint32_t temp_offset, uint32_t stack_adjustment, bool is_float); + template<class LabelType> void GenerateTestAndBranch(HInstruction* instruction, size_t condition_input_index, - Label* true_target, - Label* false_target); + LabelType* true_target, + LabelType* false_target); + template<class LabelType> void GenerateCompareTestAndBranch(HCondition* condition, - Label* true_target, - Label* false_target); - void GenerateFPJumps(HCondition* cond, Label* true_label, Label* false_label); + LabelType* true_target, + LabelType* false_target); + template<class LabelType> + void GenerateFPJumps(HCondition* cond, LabelType* true_label, LabelType* false_label); + void HandleGoto(HInstruction* got, HBasicBlock* successor); X86_64Assembler* const assembler_; diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc index f3c1dbe3f5..6d0bdbe19b 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -763,6 +763,14 @@ void SSAChecker::VisitPhi(HPhi* phi) { phi->GetId(), phi->GetRegNumber(), type_str.str().c_str())); + } else if (phi->GetType() == Primitive::kPrimNot) { + std::stringstream type_str; + type_str << other_phi->GetType(); + AddError(StringPrintf( + "Equivalent non-reference phi (%d) found for VReg %d with type: %s.", + phi->GetId(), + phi->GetRegNumber(), + type_str.str().c_str())); } else { ArenaBitVector visited(GetGraph()->GetArena(), 0, /* expandable */ true); if (!IsConstantEquivalent(phi, other_phi, &visited)) { @@ -913,4 +921,16 @@ void SSAChecker::VisitConstant(HConstant* instruction) { } } +void SSAChecker::VisitBoundType(HBoundType* instruction) { + VisitInstruction(instruction); + + ScopedObjectAccess soa(Thread::Current()); + if (!instruction->GetUpperBound().IsValid()) { + AddError(StringPrintf( + "%s %d does not have a valid upper bound RTI.", + instruction->DebugName(), + instruction->GetId())); + } +} + } // namespace art diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h index d5ddbabc8c..2e16bfe245 100644 --- a/compiler/optimizing/graph_checker.h +++ b/compiler/optimizing/graph_checker.h @@ -128,6 +128,7 @@ class SSAChecker : public GraphChecker { void VisitPackedSwitch(HPackedSwitch* instruction) OVERRIDE; void VisitBooleanNot(HBooleanNot* instruction) OVERRIDE; void VisitConstant(HConstant* instruction) OVERRIDE; + void VisitBoundType(HBoundType* instruction) OVERRIDE; void HandleBooleanInput(HInstruction* instruction, size_t input_index); diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc index 776c115e9d..29a1845658 100644 --- a/compiler/optimizing/induction_var_analysis_test.cc +++ b/compiler/optimizing/induction_var_analysis_test.cc @@ -85,6 +85,7 @@ class InductionVarAnalysisTest : public CommonCompilerTest { constant0_ = graph_->GetIntConstant(0); constant1_ = graph_->GetIntConstant(1); constant100_ = graph_->GetIntConstant(100); + float_constant0_ = graph_->GetFloatConstant(0.0f); induc_ = new (&allocator_) HLocal(n); entry_->AddInstruction(induc_); entry_->AddInstruction(new (&allocator_) HStoreLocal(induc_, constant0_)); @@ -156,8 +157,10 @@ class InductionVarAnalysisTest : public CommonCompilerTest { HInstruction* InsertArrayStore(HLocal* subscript, int d) { HInstruction* load = InsertInstruction( new (&allocator_) HLoadLocal(subscript, Primitive::kPrimInt), d); + // ArraySet is given a float value in order to avoid SsaBuilder typing + // it from the array's non-existent reference type info. return InsertInstruction(new (&allocator_) HArraySet( - parameter_, load, constant0_, Primitive::kPrimInt, 0), d); + parameter_, load, float_constant0_, Primitive::kPrimFloat, 0), d); } // Returns induction information of instruction in loop at depth d. @@ -187,6 +190,7 @@ class InductionVarAnalysisTest : public CommonCompilerTest { HInstruction* constant0_; HInstruction* constant1_; HInstruction* constant100_; + HInstruction* float_constant0_; HLocal* induc_; // "vreg_n", the "k" HLocal* tmp_; // "vreg_n+1" HLocal* dum_; // "vreg_n+2" diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc index 0e50416a9e..48d32999b7 100644 --- a/compiler/optimizing/inliner.cc +++ b/compiler/optimizing/inliner.cc @@ -42,7 +42,14 @@ namespace art { -static constexpr size_t kMaximumNumberOfHInstructions = 12; +static constexpr size_t kMaximumNumberOfHInstructions = 32; + +// Limit the number of dex registers that we accumulate while inlining +// to avoid creating large amount of nested environments. +static constexpr size_t kMaximumNumberOfCumulatedDexRegisters = 64; + +// Avoid inlining within a huge method due to memory pressure. +static constexpr size_t kMaximumCodeUnitSize = 4096; void HInliner::Run() { const CompilerOptions& compiler_options = compiler_driver_->GetCompilerOptions(); @@ -50,6 +57,9 @@ void HInliner::Run() { || (compiler_options.GetInlineMaxCodeUnits() == 0)) { return; } + if (caller_compilation_unit_.GetCodeItem()->insns_size_in_code_units_ > kMaximumCodeUnitSize) { + return; + } if (graph_->IsDebuggable()) { // For simplicity, we currently never inline when the graph is debuggable. This avoids // doing some logic in the runtime to discover if a method could have been inlined. @@ -216,6 +226,7 @@ bool HInliner::TryInline(HInvoke* invoke_instruction) { ClassLinker* class_linker = caller_compilation_unit_.GetClassLinker(); // We can query the dex cache directly. The verifier has populated it already. ArtMethod* resolved_method; + ArtMethod* actual_method = nullptr; if (invoke_instruction->IsInvokeStaticOrDirect()) { if (invoke_instruction->AsInvokeStaticOrDirect()->IsStringInit()) { VLOG(compiler) << "Not inlining a String.<init> method"; @@ -227,9 +238,15 @@ bool HInliner::TryInline(HInvoke* invoke_instruction) { : class_linker->FindDexCache(soa.Self(), *ref.dex_file); resolved_method = dex_cache->GetResolvedMethod( ref.dex_method_index, class_linker->GetImagePointerSize()); + // actual_method == resolved_method for direct or static calls. + actual_method = resolved_method; } else { resolved_method = caller_compilation_unit_.GetDexCache().Get()->GetResolvedMethod( method_index, class_linker->GetImagePointerSize()); + if (resolved_method != nullptr) { + // Check if we can statically find the method. + actual_method = FindVirtualOrInterfaceTarget(invoke_instruction, resolved_method); + } } if (resolved_method == nullptr) { @@ -239,15 +256,10 @@ bool HInliner::TryInline(HInvoke* invoke_instruction) { return false; } - if (invoke_instruction->IsInvokeStaticOrDirect()) { - return TryInline(invoke_instruction, resolved_method); - } - - // Check if we can statically find the method. - ArtMethod* actual_method = FindVirtualOrInterfaceTarget(invoke_instruction, resolved_method); if (actual_method != nullptr) { return TryInline(invoke_instruction, actual_method); } + DCHECK(!invoke_instruction->IsInvokeStaticOrDirect()); // Check if we can use an inline cache. ArtMethod* caller = graph_->GetArtMethod(); @@ -589,6 +601,7 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, compiler_driver_, handles_, stats_, + total_number_of_dex_registers_ + code_item->registers_size_, depth_ + 1); inliner.Run(); number_of_instructions_budget += inliner.number_of_inlined_instructions_; @@ -620,6 +633,10 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, HReversePostOrderIterator it(*callee_graph); it.Advance(); // Past the entry block, it does not contain instructions that prevent inlining. size_t number_of_instructions = 0; + + bool can_inline_environment = + total_number_of_dex_registers_ < kMaximumNumberOfCumulatedDexRegisters; + for (; !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); if (block->IsLoopHeader()) { @@ -633,10 +650,17 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, instr_it.Advance()) { if (number_of_instructions++ == number_of_instructions_budget) { VLOG(compiler) << "Method " << PrettyMethod(method_index, callee_dex_file) - << " could not be inlined because it is too big."; + << " is not inlined because its caller has reached" + << " its instruction budget limit."; return false; } HInstruction* current = instr_it.Current(); + if (!can_inline_environment && current->NeedsEnvironment()) { + VLOG(compiler) << "Method " << PrettyMethod(method_index, callee_dex_file) + << " is not inlined because its caller has reached" + << " its environment budget limit."; + return false; + } if (current->IsInvokeInterface()) { // Disable inlining of interface calls. The cost in case of entering the diff --git a/compiler/optimizing/inliner.h b/compiler/optimizing/inliner.h index 7b9fb73ccf..8de510ea37 100644 --- a/compiler/optimizing/inliner.h +++ b/compiler/optimizing/inliner.h @@ -40,13 +40,15 @@ class HInliner : public HOptimization { CompilerDriver* compiler_driver, StackHandleScopeCollection* handles, OptimizingCompilerStats* stats, - size_t depth = 0) + size_t total_number_of_dex_registers, + size_t depth) : HOptimization(outer_graph, kInlinerPassName, stats), outermost_graph_(outermost_graph), outer_compilation_unit_(outer_compilation_unit), caller_compilation_unit_(caller_compilation_unit), codegen_(codegen), compiler_driver_(compiler_driver), + total_number_of_dex_registers_(total_number_of_dex_registers), depth_(depth), number_of_inlined_instructions_(0), handles_(handles) {} @@ -88,6 +90,7 @@ class HInliner : public HOptimization { const DexCompilationUnit& caller_compilation_unit_; CodeGenerator* const codegen_; CompilerDriver* const compiler_driver_; + const size_t total_number_of_dex_registers_; const size_t depth_; size_t number_of_inlined_instructions_; StackHandleScopeCollection* const handles_; diff --git a/compiler/optimizing/licm_test.cc b/compiler/optimizing/licm_test.cc index aa60fd646d..2b63ec8971 100644 --- a/compiler/optimizing/licm_test.cc +++ b/compiler/optimizing/licm_test.cc @@ -65,7 +65,8 @@ class LICMTest : public CommonCompilerTest { // Provide boiler-plate instructions. parameter_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); entry_->AddInstruction(parameter_); - constant_ = graph_->GetIntConstant(42); + int_constant_ = graph_->GetIntConstant(42); + float_constant_ = graph_->GetFloatConstant(42.0f); loop_preheader_->AddInstruction(new (&allocator_) HGoto()); loop_header_->AddInstruction(new (&allocator_) HIf(parameter_)); loop_body_->AddInstruction(new (&allocator_) HGoto()); @@ -95,7 +96,8 @@ class LICMTest : public CommonCompilerTest { HBasicBlock* exit_; HInstruction* parameter_; // "this" - HInstruction* constant_; + HInstruction* int_constant_; + HInstruction* float_constant_; }; // @@ -118,7 +120,7 @@ TEST_F(LICMTest, FieldHoisting) { 0); loop_body_->InsertInstructionBefore(get_field, loop_body_->GetLastInstruction()); HInstruction* set_field = new (&allocator_) HInstanceFieldSet( - parameter_, constant_, Primitive::kPrimInt, MemberOffset(20), + parameter_, int_constant_, Primitive::kPrimInt, MemberOffset(20), false, kUnknownFieldIndex, kUnknownClassDefIndex, graph_->GetDexFile(), dex_cache, 0); loop_body_->InsertInstructionBefore(set_field, loop_body_->GetLastInstruction()); @@ -167,11 +169,13 @@ TEST_F(LICMTest, ArrayHoisting) { BuildLoop(); // Populate the loop with instructions: set/get array with different types. + // ArrayGet is typed as kPrimByte and ArraySet given a float value in order to + // avoid SsaBuilder's typing of ambiguous array operations from reference type info. HInstruction* get_array = new (&allocator_) HArrayGet( - parameter_, constant_, Primitive::kPrimByte, 0); + parameter_, int_constant_, Primitive::kPrimByte, 0); loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction()); HInstruction* set_array = new (&allocator_) HArraySet( - parameter_, constant_, constant_, Primitive::kPrimShort, 0); + parameter_, int_constant_, float_constant_, Primitive::kPrimShort, 0); loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction()); EXPECT_EQ(get_array->GetBlock(), loop_body_); @@ -185,11 +189,13 @@ TEST_F(LICMTest, NoArrayHoisting) { BuildLoop(); // Populate the loop with instructions: set/get array with same types. + // ArrayGet is typed as kPrimByte and ArraySet given a float value in order to + // avoid SsaBuilder's typing of ambiguous array operations from reference type info. HInstruction* get_array = new (&allocator_) HArrayGet( - parameter_, constant_, Primitive::kPrimByte, 0); + parameter_, int_constant_, Primitive::kPrimByte, 0); loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction()); HInstruction* set_array = new (&allocator_) HArraySet( - parameter_, get_array, constant_, Primitive::kPrimByte, 0); + parameter_, get_array, float_constant_, Primitive::kPrimByte, 0); loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction()); EXPECT_EQ(get_array->GetBlock(), loop_body_); diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc index 727f2bb717..2b313f6b81 100644 --- a/compiler/optimizing/load_store_elimination.cc +++ b/compiler/optimizing/load_store_elimination.cc @@ -678,16 +678,6 @@ class LSEVisitor : public HGraphVisitor { } } - static bool IsIntFloatAlias(Primitive::Type type1, Primitive::Type type2) { - return (type1 == Primitive::kPrimFloat && type2 == Primitive::kPrimInt) || - (type2 == Primitive::kPrimFloat && type1 == Primitive::kPrimInt); - } - - static bool IsLongDoubleAlias(Primitive::Type type1, Primitive::Type type2) { - return (type1 == Primitive::kPrimDouble && type2 == Primitive::kPrimLong) || - (type2 == Primitive::kPrimDouble && type1 == Primitive::kPrimLong); - } - void VisitGetLocation(HInstruction* instruction, HInstruction* ref, size_t offset, @@ -716,22 +706,14 @@ class LSEVisitor : public HGraphVisitor { // Get the real heap value of the store. heap_value = store->InputAt(1); } - if ((heap_value != kUnknownHeapValue) && - // Keep the load due to possible I/F, J/D array aliasing. - // See b/22538329 for details. - !IsIntFloatAlias(heap_value->GetType(), instruction->GetType()) && - !IsLongDoubleAlias(heap_value->GetType(), instruction->GetType())) { - removed_loads_.push_back(instruction); - substitute_instructions_for_loads_.push_back(heap_value); - TryRemovingNullCheck(instruction); - return; - } - - // Load isn't eliminated. if (heap_value == kUnknownHeapValue) { - // Put the load as the value into the HeapLocation. + // Load isn't eliminated. Put the load as the value into the HeapLocation. // This acts like GVN but with better aliasing analysis. heap_values[idx] = instruction; + } else { + removed_loads_.push_back(instruction); + substitute_instructions_for_loads_.push_back(heap_value); + TryRemovingNullCheck(instruction); } } diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index fc12224783..c85e573557 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -2060,6 +2060,16 @@ void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) { new_pre_header->SetTryCatchInformation(try_catch_info); } +static void CheckAgainstUpperBound(ReferenceTypeInfo rti, ReferenceTypeInfo upper_bound_rti) + SHARED_REQUIRES(Locks::mutator_lock_) { + if (rti.IsValid()) { + DCHECK(upper_bound_rti.IsSupertypeOf(rti)) + << " upper_bound_rti: " << upper_bound_rti + << " rti: " << rti; + DCHECK(!upper_bound_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes() || rti.IsExact()); + } +} + void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) { if (kIsDebugBuild) { DCHECK_EQ(GetType(), Primitive::kPrimNot); @@ -2068,16 +2078,23 @@ void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) { if (IsBoundType()) { // Having the test here spares us from making the method virtual just for // the sake of a DCHECK. - ReferenceTypeInfo upper_bound_rti = AsBoundType()->GetUpperBound(); - DCHECK(upper_bound_rti.IsSupertypeOf(rti)) - << " upper_bound_rti: " << upper_bound_rti - << " rti: " << rti; - DCHECK(!upper_bound_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes() || rti.IsExact()); + CheckAgainstUpperBound(rti, AsBoundType()->GetUpperBound()); } } reference_type_info_ = rti; } +void HBoundType::SetUpperBound(const ReferenceTypeInfo& upper_bound, bool can_be_null) { + if (kIsDebugBuild) { + ScopedObjectAccess soa(Thread::Current()); + DCHECK(upper_bound.IsValid()); + DCHECK(!upper_bound_.IsValid()) << "Upper bound should only be set once."; + CheckAgainstUpperBound(GetReferenceTypeInfo(), upper_bound); + } + upper_bound_ = upper_bound; + upper_can_be_null_ = can_be_null; +} + ReferenceTypeInfo::ReferenceTypeInfo() : type_handle_(TypeHandle()), is_exact_(false) {} ReferenceTypeInfo::ReferenceTypeInfo(TypeHandle type_handle, bool is_exact) diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 5b072cf71c..1a7cbdeb5a 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -101,7 +101,7 @@ enum IfCondition { enum BuildSsaResult { kBuildSsaFailNonNaturalLoop, kBuildSsaFailThrowCatchLoop, - kBuildSsaFailAmbiguousArrayGet, + kBuildSsaFailAmbiguousArrayOp, kBuildSsaSuccess, }; @@ -240,7 +240,7 @@ class ReferenceTypeInfo : ValueObject { // Returns true if the type information provide the same amount of details. // Note that it does not mean that the instructions have the same actual type // (because the type can be the result of a merge). - bool IsEqual(ReferenceTypeInfo rti) SHARED_REQUIRES(Locks::mutator_lock_) { + bool IsEqual(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { if (!IsValid() && !rti.IsValid()) { // Invalid types are equal. return true; @@ -5431,24 +5431,19 @@ class HInstanceOf : public HExpression<2> { class HBoundType : public HExpression<1> { public: - // Constructs an HBoundType with the given upper_bound. - // Ensures that the upper_bound is valid. - HBoundType(HInstruction* input, - ReferenceTypeInfo upper_bound, - bool upper_can_be_null, - uint32_t dex_pc = kNoDexPc) + HBoundType(HInstruction* input, uint32_t dex_pc = kNoDexPc) : HExpression(Primitive::kPrimNot, SideEffects::None(), dex_pc), - upper_bound_(upper_bound), - upper_can_be_null_(upper_can_be_null), - can_be_null_(upper_can_be_null) { + upper_bound_(ReferenceTypeInfo::CreateInvalid()), + upper_can_be_null_(true), + can_be_null_(true) { DCHECK_EQ(input->GetType(), Primitive::kPrimNot); SetRawInputAt(0, input); - SetReferenceTypeInfo(upper_bound_); } - // GetUpper* should only be used in reference type propagation. + // {Get,Set}Upper* should only be used in reference type propagation. const ReferenceTypeInfo& GetUpperBound() const { return upper_bound_; } bool GetUpperCanBeNull() const { return upper_can_be_null_; } + void SetUpperBound(const ReferenceTypeInfo& upper_bound, bool can_be_null); void SetCanBeNull(bool can_be_null) { DCHECK(upper_can_be_null_ || !can_be_null); @@ -5466,10 +5461,10 @@ class HBoundType : public HExpression<1> { // if (x instanceof ClassX) { // // uper_bound_ will be ClassX // } - const ReferenceTypeInfo upper_bound_; + ReferenceTypeInfo upper_bound_; // Represents the top constraint that can_be_null_ cannot exceed (i.e. if this // is false then can_be_null_ cannot be true). - const bool upper_can_be_null_; + bool upper_can_be_null_; bool can_be_null_; DISALLOW_COPY_AND_ASSIGN(HBoundType); diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 3de870e95e..3eb72744ee 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -426,8 +426,18 @@ static void MaybeRunInliner(HGraph* graph, if (!should_inline) { return; } + size_t number_of_dex_registers = dex_compilation_unit.GetCodeItem()->registers_size_; HInliner* inliner = new (graph->GetArena()) HInliner( - graph, graph, codegen, dex_compilation_unit, dex_compilation_unit, driver, handles, stats); + graph, + graph, + codegen, + dex_compilation_unit, + dex_compilation_unit, + driver, + handles, + stats, + number_of_dex_registers, + /* depth */ 0); HOptimization* optimizations[] = { inliner }; RunOptimizations(optimizations, arraysize(optimizations), pass_observer); @@ -776,8 +786,8 @@ CodeGenerator* OptimizingCompiler::TryCompile(ArenaAllocator* arena, case kBuildSsaFailThrowCatchLoop: MaybeRecordStat(MethodCompilationStat::kNotCompiledThrowCatchLoop); break; - case kBuildSsaFailAmbiguousArrayGet: - MaybeRecordStat(MethodCompilationStat::kNotCompiledAmbiguousArrayGet); + case kBuildSsaFailAmbiguousArrayOp: + MaybeRecordStat(MethodCompilationStat::kNotCompiledAmbiguousArrayOp); break; case kBuildSsaSuccess: UNREACHABLE(); diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h index 4713514bb2..bca1632e31 100644 --- a/compiler/optimizing/optimizing_compiler_stats.h +++ b/compiler/optimizing/optimizing_compiler_stats.h @@ -40,7 +40,7 @@ enum MethodCompilationStat { kNotCompiledBranchOutsideMethodCode, kNotCompiledNonNaturalLoop, kNotCompiledThrowCatchLoop, - kNotCompiledAmbiguousArrayGet, + kNotCompiledAmbiguousArrayOp, kNotCompiledHugeMethod, kNotCompiledLargeMethodNoBranches, kNotCompiledMalformedOpcode, @@ -108,7 +108,7 @@ class OptimizingCompilerStats { case kNotCompiledBranchOutsideMethodCode: name = "NotCompiledBranchOutsideMethodCode"; break; case kNotCompiledNonNaturalLoop : name = "NotCompiledNonNaturalLoop"; break; case kNotCompiledThrowCatchLoop : name = "NotCompiledThrowCatchLoop"; break; - case kNotCompiledAmbiguousArrayGet : name = "NotCompiledAmbiguousArrayGet"; break; + case kNotCompiledAmbiguousArrayOp : name = "NotCompiledAmbiguousArrayOp"; break; case kNotCompiledHugeMethod : name = "NotCompiledHugeMethod"; break; case kNotCompiledLargeMethodNoBranches : name = "NotCompiledLargeMethodNoBranches"; break; case kNotCompiledMalformedOpcode : name = "NotCompiledMalformedOpcode"; break; diff --git a/compiler/optimizing/prepare_for_register_allocation.cc b/compiler/optimizing/prepare_for_register_allocation.cc index d1770b75ab..63ef600756 100644 --- a/compiler/optimizing/prepare_for_register_allocation.cc +++ b/compiler/optimizing/prepare_for_register_allocation.cc @@ -96,7 +96,7 @@ void PrepareForRegisterAllocation::VisitClinitCheck(HClinitCheck* check) { if (can_merge_with_load_class && !load_class->HasUses()) { load_class->GetBlock()->RemoveInstruction(load_class); } - } else if (can_merge_with_load_class) { + } else if (can_merge_with_load_class && !load_class->NeedsAccessCheck()) { // Pass the initialization duty to the `HLoadClass` instruction, // and remove the instruction from the graph. load_class->SetMustGenerateClinitCheck(true); diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc index 94a297c9e6..1c25e4824c 100644 --- a/compiler/optimizing/reference_type_propagation.cc +++ b/compiler/optimizing/reference_type_propagation.cc @@ -56,6 +56,7 @@ class RTPVisitor : public HGraphDelegateVisitor { void VisitInvoke(HInvoke* instr) OVERRIDE; void VisitArrayGet(HArrayGet* instr) OVERRIDE; void VisitCheckCast(HCheckCast* instr) OVERRIDE; + void VisitBoundType(HBoundType* instr) OVERRIDE; void VisitNullCheck(HNullCheck* instr) OVERRIDE; void VisitFakeString(HFakeString* instr) OVERRIDE; void UpdateReferenceTypeInfo(HInstruction* instr, @@ -124,91 +125,6 @@ void ReferenceTypePropagation::ValidateTypes() { } } -static void CheckHasNoTypedInputs(HInstruction* root_instr) { - ArenaAllocatorAdapter<void> adapter = - root_instr->GetBlock()->GetGraph()->GetArena()->Adapter(kArenaAllocReferenceTypePropagation); - - ArenaVector<HPhi*> visited_phis(adapter); - ArenaVector<HInstruction*> worklist(adapter); - worklist.push_back(root_instr); - - while (!worklist.empty()) { - HInstruction* instr = worklist.back(); - worklist.pop_back(); - - if (instr->IsPhi() || instr->IsBoundType() || instr->IsNullCheck()) { - // Expect that both `root_instr` and its inputs have invalid RTI. - ScopedObjectAccess soa(Thread::Current()); - DCHECK(!instr->GetReferenceTypeInfo().IsValid()) << "Instruction should not have valid RTI."; - - // Insert all unvisited inputs to the worklist. - for (HInputIterator it(instr); !it.Done(); it.Advance()) { - HInstruction* input = it.Current(); - if (input->IsPhi()) { - if (ContainsElement(visited_phis, input->AsPhi())) { - continue; - } else { - visited_phis.push_back(input->AsPhi()); - } - } - worklist.push_back(input); - } - } else if (instr->IsNullConstant()) { - // The only input of `root_instr` allowed to have valid RTI because it is ignored. - } else { - LOG(FATAL) << "Unexpected input " << instr->DebugName() << instr->GetId() << " with RTI " - << instr->GetReferenceTypeInfo(); - UNREACHABLE(); - } - } -} - -template<typename Functor> -static void ForEachUntypedInstruction(HGraph* graph, Functor fn) { - ScopedObjectAccess soa(Thread::Current()); - for (HReversePostOrderIterator block_it(*graph); !block_it.Done(); block_it.Advance()) { - for (HInstructionIterator it(block_it.Current()->GetPhis()); !it.Done(); it.Advance()) { - HPhi* phi = it.Current()->AsPhi(); - // Note that the graph may contain dead phis when run from the SsaBuilder. - // Skip those as they might have a type conflict and will be removed anyway. - if (phi->IsLive() && - phi->GetType() == Primitive::kPrimNot && - !phi->GetReferenceTypeInfo().IsValid()) { - fn(phi); - } - } - for (HInstructionIterator it(block_it.Current()->GetInstructions()); !it.Done(); it.Advance()) { - HInstruction* instr = it.Current(); - if (instr->GetType() == Primitive::kPrimNot && !instr->GetReferenceTypeInfo().IsValid()) { - fn(instr); - } - } - } -} - -void ReferenceTypePropagation::SetUntypedInstructionsToObject() { - // In some cases, the fix-point iteration will leave kPrimNot instructions with - // invalid RTI because bytecode does not provide enough typing information. - // Set the RTI of such instructions to Object. - // Example: - // MyClass a = null, b = null; - // while (a == null) { - // if (cond) { a = b; } else { b = a; } - // } - - if (kIsDebugBuild) { - // Test that if we are going to set RTI from invalid to Object, that - // instruction did not have any typed instructions in its def-use chain - // and therefore its type could not be inferred. - ForEachUntypedInstruction(graph_, [](HInstruction* instr) { CheckHasNoTypedInputs(instr); }); - } - - ReferenceTypeInfo obj_rti = ReferenceTypeInfo::Create(object_class_handle_, /* is_exact */ false); - ForEachUntypedInstruction(graph_, [obj_rti](HInstruction* instr) { - instr->SetReferenceTypeInfo(obj_rti); - }); -} - void ReferenceTypePropagation::Run() { // To properly propagate type info we need to visit in the dominator-based order. // Reverse post order guarantees a node's dominators are visited first. @@ -218,7 +134,6 @@ void ReferenceTypePropagation::Run() { } ProcessWorklist(); - SetUntypedInstructionsToObject(); ValidateTypes(); } @@ -246,34 +161,6 @@ void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) { BoundTypeForIfInstanceOf(block); } -// Create a bound type for the given object narrowing the type as much as possible. -// The BoundType upper values for the super type and can_be_null will be taken from -// load_class.GetLoadedClassRTI() and upper_can_be_null. -static HBoundType* CreateBoundType(ArenaAllocator* arena, - HInstruction* obj, - HLoadClass* load_class, - bool upper_can_be_null) - SHARED_REQUIRES(Locks::mutator_lock_) { - ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo(); - ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); - DCHECK(class_rti.IsValid()); - HBoundType* bound_type = new (arena) HBoundType(obj, class_rti, upper_can_be_null); - // Narrow the type as much as possible. - if (class_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes()) { - bound_type->SetReferenceTypeInfo( - ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ true)); - } else if (obj_rti.IsValid() && class_rti.IsSupertypeOf(obj_rti)) { - bound_type->SetReferenceTypeInfo(obj_rti); - } else { - bound_type->SetReferenceTypeInfo( - ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false)); - } - if (upper_can_be_null) { - bound_type->SetCanBeNull(obj->CanBeNull()); - } - return bound_type; -} - // Check if we should create a bound type for the given object at the specified // position. Because of inlining and the fact we run RTP more than once and we // might have a HBoundType already. If we do, we should not create a new one. @@ -359,8 +246,8 @@ void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) { ReferenceTypeInfo object_rti = ReferenceTypeInfo::Create( object_class_handle_, /* is_exact */ true); if (ShouldCreateBoundType(insert_point, obj, object_rti, nullptr, notNullBlock)) { - bound_type = new (graph_->GetArena()) HBoundType( - obj, object_rti, /* bound_can_be_null */ false); + bound_type = new (graph_->GetArena()) HBoundType(obj); + bound_type->SetUpperBound(object_rti, /* bound_can_be_null */ false); if (obj->GetReferenceTypeInfo().IsValid()) { bound_type->SetReferenceTypeInfo(obj->GetReferenceTypeInfo()); } @@ -494,11 +381,8 @@ void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) { ScopedObjectAccess soa(Thread::Current()); HInstruction* insert_point = instanceOfTrueBlock->GetFirstInstruction(); if (ShouldCreateBoundType(insert_point, obj, class_rti, nullptr, instanceOfTrueBlock)) { - bound_type = CreateBoundType( - graph_->GetArena(), - obj, - load_class, - false /* InstanceOf ensures the object is not null. */); + bound_type = new (graph_->GetArena()) HBoundType(obj); + bound_type->SetUpperBound(class_rti, /* InstanceOf fails for null. */ false); instanceOfTrueBlock->InsertInstructionBefore(bound_type, insert_point); } else { // We already have a bound type on the position we would need to insert @@ -688,43 +572,61 @@ void RTPVisitor::VisitFakeString(HFakeString* instr) { instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(string_class_handle_, /* is_exact */ true)); } +void RTPVisitor::VisitBoundType(HBoundType* instr) { + ScopedObjectAccess soa(Thread::Current()); + + ReferenceTypeInfo class_rti = instr->GetUpperBound(); + if (class_rti.IsValid()) { + // Narrow the type as much as possible. + HInstruction* obj = instr->InputAt(0); + ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo(); + if (class_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes()) { + instr->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ true)); + } else if (obj_rti.IsValid()) { + if (class_rti.IsSupertypeOf(obj_rti)) { + // Object type is more specific. + instr->SetReferenceTypeInfo(obj_rti); + } else { + // Upper bound is more specific. + instr->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false)); + } + } else { + // Object not typed yet. Leave BoundType untyped for now rather than + // assign the type conservatively. + } + instr->SetCanBeNull(obj->CanBeNull() && instr->GetUpperCanBeNull()); + } else { + // The owner of the BoundType was already visited. If the class is unresolved, + // the BoundType should have been removed from the data flow and this method + // should remove it from the graph. + DCHECK(!instr->HasUses()); + instr->GetBlock()->RemoveInstruction(instr); + } +} + void RTPVisitor::VisitCheckCast(HCheckCast* check_cast) { + ScopedObjectAccess soa(Thread::Current()); + HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass(); ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); - { - ScopedObjectAccess soa(Thread::Current()); - if (!class_rti.IsValid()) { - // He have loaded an unresolved class. Don't bother bounding the type. - return; - } + HBoundType* bound_type = check_cast->GetNext()->AsBoundType(); + if (bound_type == nullptr || bound_type->GetUpperBound().IsValid()) { + // The next instruction is not an uninitialized BoundType. This must be + // an RTP pass after SsaBuilder and we do not need to do anything. + return; } - HInstruction* obj = check_cast->InputAt(0); - HBoundType* bound_type = nullptr; - for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) { - HInstruction* user = it.Current()->GetUser(); - if (check_cast->StrictlyDominates(user)) { - if (bound_type == nullptr) { - ScopedObjectAccess soa(Thread::Current()); - if (ShouldCreateBoundType(check_cast->GetNext(), obj, class_rti, check_cast, nullptr)) { - bound_type = CreateBoundType( - GetGraph()->GetArena(), - obj, - load_class, - true /* CheckCast succeeds for nulls. */); - check_cast->GetBlock()->InsertInstructionAfter(bound_type, check_cast); - } else { - // Update nullability of the existing bound type, which may not have known - // that its input was not null when it was being created. - bound_type = check_cast->GetNext()->AsBoundType(); - bound_type->SetCanBeNull(obj->CanBeNull()); - // We already have a bound type on the position we would need to insert - // the new one. The existing bound type should dominate all the users - // (dchecked) so there's no need to continue. - break; - } - } - user->ReplaceInput(bound_type, it.Current()->GetIndex()); - } + DCHECK_EQ(bound_type->InputAt(0), check_cast->InputAt(0)); + + if (class_rti.IsValid()) { + // This is the first run of RTP and class is resolved. + bound_type->SetUpperBound(class_rti, /* CheckCast succeeds for nulls. */ true); + } else { + // This is the first run of RTP and class is unresolved. Remove the binding. + // The instruction itself is removed in VisitBoundType so as to not + // invalidate HInstructionIterator. + bound_type->ReplaceWith(bound_type->InputAt(0)); } } diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h index 21789e1331..5c05592726 100644 --- a/compiler/optimizing/reference_type_propagation.h +++ b/compiler/optimizing/reference_type_propagation.h @@ -57,7 +57,6 @@ class ReferenceTypePropagation : public HOptimization { SHARED_REQUIRES(Locks::mutator_lock_); void ValidateTypes(); - void SetUntypedInstructionsToObject(); StackHandleScopeCollection* handles_; diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc index 9e869e18e9..f6bab8efcb 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -154,7 +154,7 @@ static bool TypePhiFromInputs(HPhi* phi) { Primitive::Type input_type = HPhi::ToPhiType(input->GetType()); if (common_type == input_type) { // No change in type. - } else if (Primitive::ComponentSize(common_type) != Primitive::ComponentSize(input_type)) { + } else if (Primitive::Is64BitType(common_type) != Primitive::Is64BitType(input_type)) { // Types are of different sizes, e.g. int vs. long. Must be a conflict. return false; } else if (Primitive::IsIntegralType(common_type)) { @@ -317,27 +317,15 @@ static HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { return equivalent; } -// Returns true if the array input of `aget` is either of type int[] or long[]. -// Should only be called on ArrayGets with ambiguous type (int/float, long/double) -// on arrays which were typed to an array class by RTP. -static bool IsArrayGetOnIntegralArray(HArrayGet* aget) SHARED_REQUIRES(Locks::mutator_lock_) { - ReferenceTypeInfo array_type = aget->GetArray()->GetReferenceTypeInfo(); +static Primitive::Type GetPrimitiveArrayComponentType(HInstruction* array) + SHARED_REQUIRES(Locks::mutator_lock_) { + ReferenceTypeInfo array_type = array->GetReferenceTypeInfo(); DCHECK(array_type.IsPrimitiveArrayClass()); - ReferenceTypeInfo::TypeHandle array_type_handle = array_type.GetTypeHandle(); - - bool is_integral_type; - if (Primitive::Is64BitType(aget->GetType())) { - is_integral_type = array_type_handle->GetComponentType()->IsPrimitiveLong(); - DCHECK(is_integral_type || array_type_handle->GetComponentType()->IsPrimitiveDouble()); - } else { - is_integral_type = array_type_handle->GetComponentType()->IsPrimitiveInt(); - DCHECK(is_integral_type || array_type_handle->GetComponentType()->IsPrimitiveFloat()); - } - return is_integral_type; + return array_type.GetTypeHandle()->GetComponentType()->GetPrimitiveType(); } -bool SsaBuilder::FixAmbiguousArrayGets() { - if (ambiguous_agets_.empty()) { +bool SsaBuilder::FixAmbiguousArrayOps() { + if (ambiguous_agets_.empty() && ambiguous_asets_.empty()) { return true; } @@ -351,13 +339,17 @@ bool SsaBuilder::FixAmbiguousArrayGets() { ScopedObjectAccess soa(Thread::Current()); for (HArrayGet* aget_int : ambiguous_agets_) { - if (!aget_int->GetArray()->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { + HInstruction* array = aget_int->GetArray(); + if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { // RTP did not type the input array. Bail. return false; } HArrayGet* aget_float = FindFloatOrDoubleEquivalentOfArrayGet(aget_int); - if (IsArrayGetOnIntegralArray(aget_int)) { + Primitive::Type array_type = GetPrimitiveArrayComponentType(array); + DCHECK_EQ(Primitive::Is64BitType(aget_int->GetType()), Primitive::Is64BitType(array_type)); + + if (Primitive::IsIntOrLongType(array_type)) { if (aget_float != nullptr) { // There is a float/double equivalent. We must replace it and re-run // primitive type propagation on all dependent instructions. @@ -366,6 +358,7 @@ bool SsaBuilder::FixAmbiguousArrayGets() { AddDependentInstructionsToWorklist(aget_int, &worklist); } } else { + DCHECK(Primitive::IsFloatingPointType(array_type)); if (aget_float == nullptr) { // This is a float/double ArrayGet but there were no typed uses which // would create the typed equivalent. Create it now. @@ -379,11 +372,47 @@ bool SsaBuilder::FixAmbiguousArrayGets() { AddDependentInstructionsToWorklist(aget_float, &worklist); } } - } - // Set a flag stating that types of ArrayGets have been resolved. This is used - // by GetFloatOrDoubleEquivalentOfArrayGet to report conflict. - agets_fixed_ = true; + // Set a flag stating that types of ArrayGets have been resolved. Requesting + // equivalent of the wrong type with GetFloatOrDoubleEquivalentOfArrayGet + // will fail from now on. + agets_fixed_ = true; + + for (HArraySet* aset : ambiguous_asets_) { + HInstruction* array = aset->GetArray(); + if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { + // RTP did not type the input array. Bail. + return false; + } + + HInstruction* value = aset->GetValue(); + Primitive::Type value_type = value->GetType(); + Primitive::Type array_type = GetPrimitiveArrayComponentType(array); + DCHECK_EQ(Primitive::Is64BitType(value_type), Primitive::Is64BitType(array_type)); + + if (Primitive::IsFloatingPointType(array_type)) { + if (!Primitive::IsFloatingPointType(value_type)) { + DCHECK(Primitive::IsIntegralType(value_type)); + // Array elements are floating-point but the value has not been replaced + // with its floating-point equivalent. The replacement must always + // succeed in code validated by the verifier. + HInstruction* equivalent = GetFloatOrDoubleEquivalent(value, array_type); + DCHECK(equivalent != nullptr); + aset->ReplaceInput(equivalent, /* input_index */ 2); + if (equivalent->IsPhi()) { + // Returned equivalent is a phi which may not have had its inputs + // replaced yet. We need to run primitive type propagation on it. + worklist.push_back(equivalent->AsPhi()); + } + } + } else { + // Array elements are integral and the value assigned to it initially + // was integral too. Nothing to do. + DCHECK(Primitive::IsIntegralType(array_type)); + DCHECK(Primitive::IsIntegralType(value_type)); + } + } + } if (!worklist.empty()) { ProcessPrimitiveTypePropagationWorklist(&worklist); @@ -429,10 +458,11 @@ BuildSsaResult SsaBuilder::BuildSsa() { ReferenceTypePropagation(GetGraph(), handles_).Run(); // 7) Step 1) duplicated ArrayGet instructions with ambiguous type (int/float - // or long/double). Now that RTP computed the type of the array input, the - // ambiguity can be resolved and the correct equivalent kept. - if (!FixAmbiguousArrayGets()) { - return kBuildSsaFailAmbiguousArrayGet; + // or long/double) and marked ArraySets with ambiguous input type. Now that RTP + // computed the type of the array input, the ambiguity can be resolved and the + // correct equivalents kept. + if (!FixAmbiguousArrayOps()) { + return kBuildSsaFailAmbiguousArrayOp; } // 8) Mark dead phis. This will mark phis which are not used by instructions @@ -702,7 +732,7 @@ HArrayGet* SsaBuilder::GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { // int/long. Requesting a float/double equivalent should lead to a conflict. if (kIsDebugBuild) { ScopedObjectAccess soa(Thread::Current()); - DCHECK(IsArrayGetOnIntegralArray(aget)); + DCHECK(Primitive::IsIntOrLongType(GetPrimitiveArrayComponentType(aget->GetArray()))); } return nullptr; } else { @@ -847,4 +877,12 @@ void SsaBuilder::VisitArrayGet(HArrayGet* aget) { VisitInstruction(aget); } +void SsaBuilder::VisitArraySet(HArraySet* aset) { + Primitive::Type type = aset->GetValue()->GetType(); + if (Primitive::IsIntOrLongType(type)) { + ambiguous_asets_.push_back(aset); + } + VisitInstruction(aset); +} + } // namespace art diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h index ed6f5cab51..0fcc3a1306 100644 --- a/compiler/optimizing/ssa_builder.h +++ b/compiler/optimizing/ssa_builder.h @@ -56,6 +56,7 @@ class SsaBuilder : public HGraphVisitor { current_locals_(nullptr), loop_headers_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), ambiguous_agets_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), + ambiguous_asets_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), locals_for_(graph->GetBlocks().size(), ArenaVector<HInstruction*>(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) { @@ -75,6 +76,7 @@ class SsaBuilder : public HGraphVisitor { void VisitInstruction(HInstruction* instruction); void VisitTemporary(HTemporary* instruction); void VisitArrayGet(HArrayGet* aget); + void VisitArraySet(HArraySet* aset); static constexpr const char* kSsaBuilderPassName = "ssa_builder"; @@ -85,10 +87,10 @@ class SsaBuilder : public HGraphVisitor { void EquivalentPhisCleanup(); void RunPrimitiveTypePropagation(); - // Attempts to resolve types of aget and aget-wide instructions from reference - // type information on the input array. Returns false if the type of the array - // is unknown. - bool FixAmbiguousArrayGets(); + // Attempts to resolve types of aget(-wide) instructions and type values passed + // to aput(-wide) instructions from reference type information on the array + // input. Returns false if the type of an array is unknown. + bool FixAmbiguousArrayOps(); bool TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist); bool UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist); @@ -115,6 +117,7 @@ class SsaBuilder : public HGraphVisitor { ArenaVector<HBasicBlock*> loop_headers_; ArenaVector<HArrayGet*> ambiguous_agets_; + ArenaVector<HArraySet*> ambiguous_asets_; // HEnvironment for each block. ArenaVector<ArenaVector<HInstruction*>> locals_for_; diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc index 63aba88c2b..2eef307295 100644 --- a/compiler/optimizing/ssa_phi_elimination.cc +++ b/compiler/optimizing/ssa_phi_elimination.cc @@ -17,6 +17,7 @@ #include "ssa_phi_elimination.h" #include "base/arena_containers.h" +#include "base/bit_vector-inl.h" namespace art { @@ -129,6 +130,9 @@ void SsaRedundantPhiElimination::Run() { } } + ArenaSet<uint32_t> visited_phis_in_cycle(graph_->GetArena()->Adapter()); + ArenaVector<HPhi*> cycle_worklist(graph_->GetArena()->Adapter()); + while (!worklist_.empty()) { HPhi* phi = worklist_.back(); worklist_.pop_back(); @@ -143,46 +147,92 @@ void SsaRedundantPhiElimination::Run() { continue; } - // Find if the inputs of the phi are the same instruction. - HInstruction* candidate = phi->InputAt(0); - // A loop phi cannot have itself as the first phi. Note that this - // check relies on our simplification pass ensuring the pre-header - // block is first in the list of predecessors of the loop header. - DCHECK(!phi->IsLoopHeaderPhi() || phi->GetBlock()->IsLoopPreHeaderFirstPredecessor()); - DCHECK_NE(phi, candidate); - - for (size_t i = 1; i < phi->InputCount(); ++i) { - HInstruction* input = phi->InputAt(i); - // For a loop phi, if the input is the phi, the phi is still candidate for - // elimination. - if (input != candidate && input != phi) { + HInstruction* candidate = nullptr; + visited_phis_in_cycle.clear(); + cycle_worklist.clear(); + + cycle_worklist.push_back(phi); + visited_phis_in_cycle.insert(phi->GetId()); + bool catch_phi_in_cycle = phi->IsCatchPhi(); + + // First do a simple loop over inputs and check if they are all the same. + for (size_t j = 0; j < phi->InputCount(); ++j) { + HInstruction* input = phi->InputAt(j); + if (input == phi) { + continue; + } else if (candidate == nullptr) { + candidate = input; + } else if (candidate != input) { candidate = nullptr; break; } } - // If the inputs are not the same, continue. + // If we haven't found a candidate, check for a phi cycle. Note that we need to detect + // such cycles to avoid having reference and non-reference equivalents. We check this + // invariant in the graph checker. if (candidate == nullptr) { - continue; + // We iterate over the array as long as it grows. + for (size_t i = 0; i < cycle_worklist.size(); ++i) { + HPhi* current = cycle_worklist[i]; + DCHECK(!current->IsLoopHeaderPhi() || + current->GetBlock()->IsLoopPreHeaderFirstPredecessor()); + + for (size_t j = 0; j < current->InputCount(); ++j) { + HInstruction* input = current->InputAt(j); + if (input == current) { + continue; + } else if (input->IsPhi()) { + if (!ContainsElement(visited_phis_in_cycle, input->GetId())) { + cycle_worklist.push_back(input->AsPhi()); + visited_phis_in_cycle.insert(input->GetId()); + catch_phi_in_cycle |= input->AsPhi()->IsCatchPhi(); + } else { + // Already visited, nothing to do. + } + } else if (candidate == nullptr) { + candidate = input; + } else if (candidate != input) { + candidate = nullptr; + // Clear the cycle worklist to break out of the outer loop. + cycle_worklist.clear(); + break; + } + } + } } - // The candidate may not dominate a phi in a catch block. - if (phi->IsCatchPhi() && !candidate->StrictlyDominates(phi)) { + if (candidate == nullptr) { continue; } - // Because we're updating the users of this phi, we may have new candidates - // for elimination. Add phis that use this phi to the worklist. - for (HUseIterator<HInstruction*> it(phi->GetUses()); !it.Done(); it.Advance()) { - HUseListNode<HInstruction*>* current = it.Current(); - HInstruction* user = current->GetUser(); - if (user->IsPhi()) { - worklist_.push_back(user->AsPhi()); + for (HPhi* current : cycle_worklist) { + // The candidate may not dominate a phi in a catch block: there may be non-throwing + // instructions at the beginning of a try range, that may be the first input of + // catch phis. + // TODO(dbrazdil): Remove this situation by moving those non-throwing instructions + // before the try entry. + if (catch_phi_in_cycle) { + if (!candidate->StrictlyDominates(current)) { + continue; + } + } else { + DCHECK(candidate->StrictlyDominates(current)); + } + + // Because we're updating the users of this phi, we may have new candidates + // for elimination. Add phis that use this phi to the worklist. + for (HUseIterator<HInstruction*> it(current->GetUses()); !it.Done(); it.Advance()) { + HUseListNode<HInstruction*>* use = it.Current(); + HInstruction* user = use->GetUser(); + if (user->IsPhi() && !ContainsElement(visited_phis_in_cycle, user->GetId())) { + worklist_.push_back(user->AsPhi()); + } } + DCHECK(candidate->StrictlyDominates(current)); + current->ReplaceWith(candidate); + current->GetBlock()->RemovePhi(current); } - - phi->ReplaceWith(candidate); - phi->GetBlock()->RemovePhi(phi); } } |