diff options
56 files changed, 1579 insertions, 2095 deletions
diff --git a/compiler/Android.mk b/compiler/Android.mk index f0bf4997c6..bdd9a84433 100644 --- a/compiler/Android.mk +++ b/compiler/Android.mk @@ -92,6 +92,7 @@ LIBART_COMPILER_SRC_FILES := \ optimizing/parallel_move_resolver.cc \ optimizing/pc_relative_fixups_x86.cc \ optimizing/prepare_for_register_allocation.cc \ + optimizing/primitive_type_propagation.cc \ optimizing/reference_type_propagation.cc \ optimizing/register_allocator.cc \ optimizing/sharpening.cc \ diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc index dc75ff1abc..4c3f66aa4f 100644 --- a/compiler/optimizing/bounds_check_elimination.cc +++ b/compiler/optimizing/bounds_check_elimination.cc @@ -1590,18 +1590,15 @@ class BCEVisitor : public HGraphVisitor { HGraph* graph = GetGraph(); HInstruction* zero; switch (type) { - case Primitive::kPrimNot: zero = graph->GetNullConstant(); break; - case Primitive::kPrimFloat: zero = graph->GetFloatConstant(0); break; - case Primitive::kPrimDouble: zero = graph->GetDoubleConstant(0); break; + case Primitive::Type::kPrimNot: zero = graph->GetNullConstant(); break; + case Primitive::Type::kPrimFloat: zero = graph->GetFloatConstant(0); break; + case Primitive::Type::kPrimDouble: zero = graph->GetDoubleConstant(0); break; default: zero = graph->GetConstant(type, 0); break; } HPhi* phi = new (graph->GetArena()) HPhi(graph->GetArena(), kNoRegNumber, /*number_of_inputs*/ 2, HPhi::ToPhiType(type)); phi->SetRawInputAt(0, instruction); phi->SetRawInputAt(1, zero); - if (type == Primitive::kPrimNot) { - phi->SetReferenceTypeInfo(instruction->GetReferenceTypeInfo()); - } new_preheader->AddPhi(phi); return phi; } diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h index ca71c32802..c3979f3dd1 100644 --- a/compiler/optimizing/builder.h +++ b/compiler/optimizing/builder.h @@ -90,9 +90,8 @@ class HGraphBuilder : public ValueObject { static constexpr const char* kBuilderPassName = "builder"; - // The number of entries in a packed switch before we use a jump table or specified - // compare/jump series. - static constexpr uint16_t kSmallSwitchThreshold = 3; + // The number of entries in a packed switch before we use a jump table. + static constexpr uint16_t kSmallSwitchThreshold = 5; private: // Analyzes the dex instruction and adds HInstruction to the graph diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc index 9fda83840c..3630dbec24 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -59,7 +59,7 @@ static constexpr SRegister kFpuCalleeSaves[] = // S registers. Therefore there is no need to block it. static constexpr DRegister DTMP = D31; -static constexpr uint32_t kPackedSwitchCompareJumpThreshold = 7; +static constexpr uint32_t kPackedSwitchJumpTableThreshold = 6; #define __ down_cast<ArmAssembler*>(codegen->GetAssembler())-> #define QUICK_ENTRY_POINT(x) QUICK_ENTRYPOINT_OFFSET(kArmWordSize, x).Int32Value() @@ -6250,7 +6250,7 @@ void LocationsBuilderARM::VisitPackedSwitch(HPackedSwitch* switch_instr) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(switch_instr, LocationSummary::kNoCall); locations->SetInAt(0, Location::RequiresRegister()); - if (switch_instr->GetNumEntries() > kPackedSwitchCompareJumpThreshold && + if (switch_instr->GetNumEntries() >= kPackedSwitchJumpTableThreshold && codegen_->GetAssembler()->IsThumb()) { locations->AddTemp(Location::RequiresRegister()); // We need a temp for the table base. if (switch_instr->GetStartValue() != 0) { @@ -6266,30 +6266,12 @@ void InstructionCodeGeneratorARM::VisitPackedSwitch(HPackedSwitch* switch_instr) Register value_reg = locations->InAt(0).AsRegister<Register>(); HBasicBlock* default_block = switch_instr->GetDefaultBlock(); - if (num_entries <= kPackedSwitchCompareJumpThreshold || !codegen_->GetAssembler()->IsThumb()) { + if (num_entries < kPackedSwitchJumpTableThreshold || !codegen_->GetAssembler()->IsThumb()) { // Create a series of compare/jumps. - Register temp_reg = IP; - // Note: It is fine for the below AddConstantSetFlags() using IP register to temporarily store - // the immediate, because IP is used as the destination register. For the other - // AddConstantSetFlags() and GenerateCompareWithImmediate(), the immediate values are constant, - // and they can be encoded in the instruction without making use of IP register. - __ AddConstantSetFlags(temp_reg, value_reg, -lower_bound); - const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors(); - // Jump to successors[0] if value == lower_bound. - __ b(codegen_->GetLabelOf(successors[0]), EQ); - int32_t last_index = 0; - for (; num_entries - last_index > 2; last_index += 2) { - __ AddConstantSetFlags(temp_reg, temp_reg, -2); - // Jump to successors[last_index + 1] if value < case_value[last_index + 2]. - __ b(codegen_->GetLabelOf(successors[last_index + 1]), LO); - // Jump to successors[last_index + 2] if value == case_value[last_index + 2]. - __ b(codegen_->GetLabelOf(successors[last_index + 2]), EQ); - } - if (num_entries - last_index == 2) { - // The last missing case_value. - GenerateCompareWithImmediate(temp_reg, 1); - __ b(codegen_->GetLabelOf(successors[last_index + 1]), EQ); + for (uint32_t i = 0; i < num_entries; i++) { + GenerateCompareWithImmediate(value_reg, lower_bound + i); + __ b(codegen_->GetLabelOf(successors[i]), EQ); } // And the default for any other value. diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc index 52058302be..451470f271 100644 --- a/compiler/optimizing/code_generator_arm64.cc +++ b/compiler/optimizing/code_generator_arm64.cc @@ -71,10 +71,10 @@ using helpers::ARM64EncodableConstantOrRegister; using helpers::ArtVixlRegCodeCoherentForRegSet; static constexpr int kCurrentMethodStackOffset = 0; -// The compare/jump sequence will generate about (1.5 * num_entries + 3) instructions. While jump +// The compare/jump sequence will generate about (2 * num_entries + 1) instructions. While jump // table version generates 7 instructions and num_entries literals. Compare/jump sequence will // generates less code/data with a small num_entries. -static constexpr uint32_t kPackedSwitchCompareJumpThreshold = 7; +static constexpr uint32_t kPackedSwitchJumpTableThreshold = 6; inline Condition ARM64Condition(IfCondition cond) { switch (cond) { @@ -546,7 +546,7 @@ class ArraySetSlowPathARM64 : public SlowPathCodeARM64 { void JumpTableARM64::EmitTable(CodeGeneratorARM64* codegen) { uint32_t num_entries = switch_instr_->GetNumEntries(); - DCHECK_GE(num_entries, kPackedSwitchCompareJumpThreshold); + DCHECK_GE(num_entries, kPackedSwitchJumpTableThreshold); // We are about to use the assembler to place literals directly. Make sure we have enough // underlying code buffer and we have generated the jump table with right size. @@ -4582,29 +4582,20 @@ void InstructionCodeGeneratorARM64::VisitPackedSwitch(HPackedSwitch* switch_inst // ranges and emit the tables only as required. static constexpr int32_t kJumpTableInstructionThreshold = 1* MB / kMaxExpectedSizePerHInstruction; - if (num_entries <= kPackedSwitchCompareJumpThreshold || + if (num_entries < kPackedSwitchJumpTableThreshold || // Current instruction id is an upper bound of the number of HIRs in the graph. GetGraph()->GetCurrentInstructionId() > kJumpTableInstructionThreshold) { // Create a series of compare/jumps. - UseScratchRegisterScope temps(codegen_->GetVIXLAssembler()); - Register temp = temps.AcquireW(); - __ Subs(temp, value_reg, Operand(lower_bound)); - const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors(); - // Jump to successors[0] if value == lower_bound. - __ B(eq, codegen_->GetLabelOf(successors[0])); - int32_t last_index = 0; - for (; num_entries - last_index > 2; last_index += 2) { - __ Subs(temp, temp, Operand(2)); - // Jump to successors[last_index + 1] if value < case_value[last_index + 2]. - __ B(lo, codegen_->GetLabelOf(successors[last_index + 1])); - // Jump to successors[last_index + 2] if value == case_value[last_index + 2]. - __ B(eq, codegen_->GetLabelOf(successors[last_index + 2])); - } - if (num_entries - last_index == 2) { - // The last missing case_value. - __ Cmp(temp, Operand(1)); - __ B(eq, codegen_->GetLabelOf(successors[last_index + 1])); + for (uint32_t i = 0; i < num_entries; i++) { + int32_t case_value = lower_bound + i; + vixl::Label* succ = codegen_->GetLabelOf(successors[i]); + if (case_value == 0) { + __ Cbz(value_reg, succ); + } else { + __ Cmp(value_reg, Operand(case_value)); + __ B(eq, succ); + } } // And the default for any other value. diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc index ce7cbcd9d6..a23e5ef332 100644 --- a/compiler/optimizing/code_generator_mips.cc +++ b/compiler/optimizing/code_generator_mips.cc @@ -4408,31 +4408,19 @@ void InstructionCodeGeneratorMIPS::VisitPackedSwitch(HPackedSwitch* switch_instr HBasicBlock* default_block = switch_instr->GetDefaultBlock(); // Create a set of compare/jumps. - Register temp_reg = TMP; - __ Addiu32(temp_reg, value_reg, -lower_bound); - // Jump to default if index is negative - // Note: We don't check the case that index is positive while value < lower_bound, because in - // this case, index >= num_entries must be true. So that we can save one branch instruction. - __ Bltz(temp_reg, codegen_->GetLabelOf(default_block)); - const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors(); - // Jump to successors[0] if value == lower_bound. - __ Beqz(temp_reg, codegen_->GetLabelOf(successors[0])); - int32_t last_index = 0; - for (; num_entries - last_index > 2; last_index += 2) { - __ Addiu(temp_reg, temp_reg, -2); - // Jump to successors[last_index + 1] if value < case_value[last_index + 2]. - __ Bltz(temp_reg, codegen_->GetLabelOf(successors[last_index + 1])); - // Jump to successors[last_index + 2] if value == case_value[last_index + 2]. - __ Beqz(temp_reg, codegen_->GetLabelOf(successors[last_index + 2])); - } - if (num_entries - last_index == 2) { - // The last missing case_value. - __ Addiu(temp_reg, temp_reg, -1); - __ Beqz(temp_reg, codegen_->GetLabelOf(successors[last_index + 1])); + for (int32_t i = 0; i < num_entries; ++i) { + int32_t case_value = lower_bound + i; + MipsLabel* successor_label = codegen_->GetLabelOf(successors[i]); + if (case_value == 0) { + __ Beqz(value_reg, successor_label); + } else { + __ LoadConst32(TMP, case_value); + __ Beq(value_reg, TMP, successor_label); + } } - // And the default for any other value. + // Insert the default branch for every other value. if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) { __ B(codegen_->GetLabelOf(default_block)); } diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc index 1a9de15c6f..fd18527c8c 100644 --- a/compiler/optimizing/code_generator_mips64.cc +++ b/compiler/optimizing/code_generator_mips64.cc @@ -3989,34 +3989,17 @@ void InstructionCodeGeneratorMIPS64::VisitPackedSwitch(HPackedSwitch* switch_ins GpuRegister value_reg = locations->InAt(0).AsRegister<GpuRegister>(); HBasicBlock* default_block = switch_instr->GetDefaultBlock(); - // Create a set of compare/jumps. - GpuRegister temp_reg = TMP; - if (IsInt<16>(-lower_bound)) { - __ Addiu(temp_reg, value_reg, -lower_bound); - } else { - __ LoadConst32(AT, -lower_bound); - __ Addu(temp_reg, value_reg, AT); - } - // Jump to default if index is negative - // Note: We don't check the case that index is positive while value < lower_bound, because in - // this case, index >= num_entries must be true. So that we can save one branch instruction. - __ Bltzc(temp_reg, codegen_->GetLabelOf(default_block)); - + // Create a series of compare/jumps. const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors(); - // Jump to successors[0] if value == lower_bound. - __ Beqzc(temp_reg, codegen_->GetLabelOf(successors[0])); - int32_t last_index = 0; - for (; num_entries - last_index > 2; last_index += 2) { - __ Addiu(temp_reg, temp_reg, -2); - // Jump to successors[last_index + 1] if value < case_value[last_index + 2]. - __ Bltzc(temp_reg, codegen_->GetLabelOf(successors[last_index + 1])); - // Jump to successors[last_index + 2] if value == case_value[last_index + 2]. - __ Beqzc(temp_reg, codegen_->GetLabelOf(successors[last_index + 2])); - } - if (num_entries - last_index == 2) { - // The last missing case_value. - __ Addiu(temp_reg, temp_reg, -1); - __ Beqzc(temp_reg, codegen_->GetLabelOf(successors[last_index + 1])); + for (int32_t i = 0; i < num_entries; i++) { + int32_t case_value = lower_bound + i; + Mips64Label* succ = codegen_->GetLabelOf(successors[i]); + if (case_value == 0) { + __ Beqzc(value_reg, succ); + } else { + __ LoadConst32(TMP, case_value); + __ Beqc(value_reg, TMP, succ); + } } // And the default for any other value. diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index 469dd49a8e..bc3256ec8c 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -42,6 +42,7 @@ namespace x86 { static constexpr int kCurrentMethodStackOffset = 0; static constexpr Register kMethodRegisterArgument = EAX; + static constexpr Register kCoreCalleeSaves[] = { EBP, ESI, EDI }; static constexpr int kC2ConditionMask = 0x400; @@ -6751,65 +6752,29 @@ void LocationsBuilderX86::VisitPackedSwitch(HPackedSwitch* switch_instr) { locations->SetInAt(0, Location::RequiresRegister()); } -void InstructionCodeGeneratorX86::GenPackedSwitchWithCompares(Register value_reg, - int32_t lower_bound, - uint32_t num_entries, - HBasicBlock* switch_block, - HBasicBlock* default_block) { - // Figure out the correct compare values and jump conditions. - // Handle the first compare/branch as a special case because it might - // jump to the default case. - DCHECK_GT(num_entries, 2u); - Condition first_condition; - uint32_t index; - const ArenaVector<HBasicBlock*>& successors = switch_block->GetSuccessors(); - if (lower_bound != 0) { - first_condition = kLess; - __ cmpl(value_reg, Immediate(lower_bound)); - __ j(first_condition, codegen_->GetLabelOf(default_block)); - __ j(kEqual, codegen_->GetLabelOf(successors[0])); - - index = 1; - } else { - // Handle all the compare/jumps below. - first_condition = kBelow; - index = 0; - } - - // Handle the rest of the compare/jumps. - for (; index + 1 < num_entries; index += 2) { - int32_t compare_to_value = lower_bound + index + 1; - __ cmpl(value_reg, Immediate(compare_to_value)); - // Jump to successors[index] if value < case_value[index]. - __ j(first_condition, codegen_->GetLabelOf(successors[index])); - // Jump to successors[index + 1] if value == case_value[index + 1]. - __ j(kEqual, codegen_->GetLabelOf(successors[index + 1])); - } - - if (index != num_entries) { - // There are an odd number of entries. Handle the last one. - DCHECK_EQ(index + 1, num_entries); - __ cmpl(value_reg, Immediate(lower_bound + index)); - __ j(kEqual, codegen_->GetLabelOf(successors[index])); - } - - // And the default for any other value. - if (!codegen_->GoesToNextBlock(switch_block, default_block)) { - __ jmp(codegen_->GetLabelOf(default_block)); - } -} - void InstructionCodeGeneratorX86::VisitPackedSwitch(HPackedSwitch* switch_instr) { int32_t lower_bound = switch_instr->GetStartValue(); - uint32_t num_entries = switch_instr->GetNumEntries(); + int32_t num_entries = switch_instr->GetNumEntries(); LocationSummary* locations = switch_instr->GetLocations(); Register value_reg = locations->InAt(0).AsRegister<Register>(); + HBasicBlock* default_block = switch_instr->GetDefaultBlock(); + + // Create a series of compare/jumps. + const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors(); + for (int i = 0; i < num_entries; i++) { + int32_t case_value = lower_bound + i; + if (case_value == 0) { + __ testl(value_reg, value_reg); + } else { + __ cmpl(value_reg, Immediate(case_value)); + } + __ j(kEqual, codegen_->GetLabelOf(successors[i])); + } - GenPackedSwitchWithCompares(value_reg, - lower_bound, - num_entries, - switch_instr->GetBlock(), - switch_instr->GetDefaultBlock()); + // And the default for any other value. + if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) { + __ jmp(codegen_->GetLabelOf(default_block)); + } } void LocationsBuilderX86::VisitX86PackedSwitch(HX86PackedSwitch* switch_instr) { @@ -6826,20 +6791,11 @@ void LocationsBuilderX86::VisitX86PackedSwitch(HX86PackedSwitch* switch_instr) { void InstructionCodeGeneratorX86::VisitX86PackedSwitch(HX86PackedSwitch* switch_instr) { int32_t lower_bound = switch_instr->GetStartValue(); - uint32_t num_entries = switch_instr->GetNumEntries(); + int32_t num_entries = switch_instr->GetNumEntries(); LocationSummary* locations = switch_instr->GetLocations(); Register value_reg = locations->InAt(0).AsRegister<Register>(); HBasicBlock* default_block = switch_instr->GetDefaultBlock(); - if (num_entries <= kPackedSwitchJumpTableThreshold) { - GenPackedSwitchWithCompares(value_reg, - lower_bound, - num_entries, - switch_instr->GetBlock(), - default_block); - return; - } - // Optimizing has a jump area. Register temp_reg = locations->GetTemp(0).AsRegister<Register>(); Register constant_area = locations->InAt(1).AsRegister<Register>(); @@ -6851,7 +6807,7 @@ void InstructionCodeGeneratorX86::VisitX86PackedSwitch(HX86PackedSwitch* switch_ } // Is the value in range? - DCHECK_GE(num_entries, 1u); + DCHECK_GE(num_entries, 1); __ cmpl(value_reg, Immediate(num_entries - 1)); __ j(kAbove, codegen_->GetLabelOf(default_block)); diff --git a/compiler/optimizing/code_generator_x86.h b/compiler/optimizing/code_generator_x86.h index 712179920b..7c292fa103 100644 --- a/compiler/optimizing/code_generator_x86.h +++ b/compiler/optimizing/code_generator_x86.h @@ -195,11 +195,6 @@ class InstructionCodeGeneratorX86 : public HGraphVisitor { X86Assembler* GetAssembler() const { return assembler_; } - // The compare/jump sequence will generate about (1.5 * num_entries) instructions. A jump - // table version generates 7 instructions and num_entries literals. Compare/jump sequence will - // generates less code/data with a small num_entries. - static constexpr uint32_t kPackedSwitchJumpTableThreshold = 5; - private: // Generate code for the given suspend check. If not null, `successor` // is the block to branch to if the suspend check is not needed, and after @@ -274,11 +269,6 @@ class InstructionCodeGeneratorX86 : public HGraphVisitor { void GenerateFPJumps(HCondition* cond, Label* true_label, Label* false_label); void GenerateLongComparesAndJumps(HCondition* cond, Label* true_label, Label* false_label); void HandleGoto(HInstruction* got, HBasicBlock* successor); - void GenPackedSwitchWithCompares(Register value_reg, - int32_t lower_bound, - uint32_t num_entries, - HBasicBlock* switch_block, - HBasicBlock* default_block); X86Assembler* const assembler_; CodeGeneratorX86* const codegen_; diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc index 2c5fbc78bf..92cef5f226 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -41,10 +41,6 @@ namespace x86_64 { static constexpr int kCurrentMethodStackOffset = 0; static constexpr Register kMethodRegisterArgument = RDI; -// The compare/jump sequence will generate about (1.5 * num_entries) instructions. A jump -// table version generates 7 instructions and num_entries literals. Compare/jump sequence will -// generates less code/data with a small num_entries. -static constexpr uint32_t kPackedSwitchJumpTableThreshold = 5; static constexpr Register kCoreCalleeSaves[] = { RBX, RBP, R12, R13, R14, R15 }; static constexpr FloatRegister kFpuCalleeSaves[] = { XMM12, XMM13, XMM14, XMM15 }; @@ -6335,58 +6331,11 @@ void LocationsBuilderX86_64::VisitPackedSwitch(HPackedSwitch* switch_instr) { void InstructionCodeGeneratorX86_64::VisitPackedSwitch(HPackedSwitch* switch_instr) { int32_t lower_bound = switch_instr->GetStartValue(); - uint32_t num_entries = switch_instr->GetNumEntries(); + int32_t num_entries = switch_instr->GetNumEntries(); LocationSummary* locations = switch_instr->GetLocations(); CpuRegister value_reg_in = locations->InAt(0).AsRegister<CpuRegister>(); CpuRegister temp_reg = locations->GetTemp(0).AsRegister<CpuRegister>(); CpuRegister base_reg = locations->GetTemp(1).AsRegister<CpuRegister>(); - HBasicBlock* default_block = switch_instr->GetDefaultBlock(); - - // Should we generate smaller inline compare/jumps? - if (num_entries <= kPackedSwitchJumpTableThreshold) { - // Figure out the correct compare values and jump conditions. - // Handle the first compare/branch as a special case because it might - // jump to the default case. - DCHECK_GT(num_entries, 2u); - Condition first_condition; - uint32_t index; - const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors(); - if (lower_bound != 0) { - first_condition = kLess; - __ cmpl(value_reg_in, Immediate(lower_bound)); - __ j(first_condition, codegen_->GetLabelOf(default_block)); - __ j(kEqual, codegen_->GetLabelOf(successors[0])); - - index = 1; - } else { - // Handle all the compare/jumps below. - first_condition = kBelow; - index = 0; - } - - // Handle the rest of the compare/jumps. - for (; index + 1 < num_entries; index += 2) { - int32_t compare_to_value = lower_bound + index + 1; - __ cmpl(value_reg_in, Immediate(compare_to_value)); - // Jump to successors[index] if value < case_value[index]. - __ j(first_condition, codegen_->GetLabelOf(successors[index])); - // Jump to successors[index + 1] if value == case_value[index + 1]. - __ j(kEqual, codegen_->GetLabelOf(successors[index + 1])); - } - - if (index != num_entries) { - // There are an odd number of entries. Handle the last one. - DCHECK_EQ(index + 1, num_entries); - __ cmpl(value_reg_in, Immediate(lower_bound + index)); - __ j(kEqual, codegen_->GetLabelOf(successors[index])); - } - - // And the default for any other value. - if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) { - __ jmp(codegen_->GetLabelOf(default_block)); - } - return; - } // Remove the bias, if needed. Register value_reg_out = value_reg_in.AsRegister(); @@ -6397,6 +6346,7 @@ void InstructionCodeGeneratorX86_64::VisitPackedSwitch(HPackedSwitch* switch_ins CpuRegister value_reg(value_reg_out); // Is the value in range? + HBasicBlock* default_block = switch_instr->GetDefaultBlock(); __ cmpl(value_reg, Immediate(num_entries - 1)); __ j(kAbove, codegen_->GetLabelOf(default_block)); diff --git a/compiler/optimizing/constant_folding_test.cc b/compiler/optimizing/constant_folding_test.cc index a8f65bf516..e469c8d6d0 100644 --- a/compiler/optimizing/constant_folding_test.cc +++ b/compiler/optimizing/constant_folding_test.cc @@ -32,7 +32,7 @@ namespace art { /** * Fixture class for the constant folding and dce tests. */ -class ConstantFoldingTest : public CommonCompilerTest { +class ConstantFoldingTest : public testing::Test { public: ConstantFoldingTest() : pool_(), allocator_(&pool_) { graph_ = CreateGraph(&allocator_); @@ -56,7 +56,7 @@ class ConstantFoldingTest : public CommonCompilerTest { const std::string& expected_after_dce, std::function<void(HGraph*)> check_after_cf) { ASSERT_NE(graph_, nullptr); - TransformToSsa(graph_); + graph_->TryBuildingSsa(); StringPrettyPrinter printer_before(graph_); printer_before.VisitInsertionOrder(); diff --git a/compiler/optimizing/dead_code_elimination_test.cc b/compiler/optimizing/dead_code_elimination_test.cc index f0f98efadb..2c6a1ef63d 100644 --- a/compiler/optimizing/dead_code_elimination_test.cc +++ b/compiler/optimizing/dead_code_elimination_test.cc @@ -26,8 +26,6 @@ namespace art { -class DeadCodeEliminationTest : public CommonCompilerTest {}; - static void TestCode(const uint16_t* data, const std::string& expected_before, const std::string& expected_after) { @@ -36,7 +34,7 @@ static void TestCode(const uint16_t* data, HGraph* graph = CreateCFG(&allocator, data); ASSERT_NE(graph, nullptr); - TransformToSsa(graph); + graph->TryBuildingSsa(); StringPrettyPrinter printer_before(graph); printer_before.VisitInsertionOrder(); @@ -57,6 +55,7 @@ static void TestCode(const uint16_t* data, ASSERT_EQ(actual_after, expected_after); } + /** * Small three-register program. * @@ -70,7 +69,7 @@ static void TestCode(const uint16_t* data, * L1: v2 <- v0 + v1 5. add-int v2, v0, v1 * return-void 7. return */ -TEST_F(DeadCodeEliminationTest, AdditionAndConditionalJump) { +TEST(DeadCodeElimination, AdditionAndConditionalJump) { const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 1 << 8 | 1 << 12, Instruction::CONST_4 | 0 << 8 | 0 << 12, @@ -132,7 +131,7 @@ TEST_F(DeadCodeEliminationTest, AdditionAndConditionalJump) { * L3: v2 <- v1 + 4 11. add-int/lit16 v2, v1, #+4 * return 13. return-void */ -TEST_F(DeadCodeEliminationTest, AdditionsAndInconditionalJumps) { +TEST(DeadCodeElimination, AdditionsAndInconditionalJumps) { const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 << 8 | 0 << 12, Instruction::CONST_4 | 1 << 8 | 1 << 12, diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc index f3c1dbe3f5..dfc363f9fd 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -24,7 +24,6 @@ #include "base/arena_containers.h" #include "base/bit_vector-inl.h" #include "base/stringprintf.h" -#include "handle_scope-inl.h" namespace art { @@ -595,17 +594,6 @@ void SSAChecker::VisitInstruction(HInstruction* instruction) { } } } - - // Ensure that reference type instructions have reference type info. - if (instruction->GetType() == Primitive::kPrimNot) { - ScopedObjectAccess soa(Thread::Current()); - if (!instruction->GetReferenceTypeInfo().IsValid()) { - AddError(StringPrintf("Reference type instruction %s:%d does not have " - "valid reference type information.", - instruction->DebugName(), - instruction->GetId())); - } - } } static Primitive::Type PrimitiveKind(Primitive::Type type) { diff --git a/compiler/optimizing/graph_checker_test.cc b/compiler/optimizing/graph_checker_test.cc index d10df4ce3f..fee56c7f9e 100644 --- a/compiler/optimizing/graph_checker_test.cc +++ b/compiler/optimizing/graph_checker_test.cc @@ -17,6 +17,8 @@ #include "graph_checker.h" #include "optimizing_unit_test.h" +#include "gtest/gtest.h" + namespace art { /** @@ -41,6 +43,7 @@ HGraph* CreateSimpleCFG(ArenaAllocator* allocator) { return graph; } + static void TestCode(const uint16_t* data) { ArenaPool pool; ArenaAllocator allocator(&pool); @@ -58,7 +61,8 @@ static void TestCodeSSA(const uint16_t* data) { HGraph* graph = CreateCFG(&allocator, data); ASSERT_NE(graph, nullptr); - TransformToSsa(graph); + graph->BuildDominatorTree(); + graph->TransformToSsa(); SSAChecker ssa_checker(graph); ssa_checker.Run(); @@ -141,9 +145,7 @@ TEST(GraphChecker, BlockEndingWithNonBranchInstruction) { ASSERT_FALSE(graph_checker.IsValid()); } -class SSACheckerTest : public CommonCompilerTest {}; - -TEST_F(SSACheckerTest, SSAPhi) { +TEST(SSAChecker, SSAPhi) { // This code creates one Phi function during the conversion to SSA form. const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc index 5f1328f545..e9fdb84d1e 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -30,7 +30,6 @@ #include "optimization.h" #include "reference_type_propagation.h" #include "register_allocator.h" -#include "ssa_builder.h" #include "ssa_liveness_analysis.h" #include "utils/assembler.h" @@ -506,7 +505,7 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { } else { StartAttributeStream("loop") << "B" << info->GetHeader()->GetBlockId(); } - } else if ((IsPass(SsaBuilder::kSsaBuilderPassName) + } else if ((IsPass(ReferenceTypePropagation::kReferenceTypePropagationPassName) || IsPass(HInliner::kInlinerPassName)) && (instruction->GetType() == Primitive::kPrimNot)) { ReferenceTypeInfo info = instruction->IsLoadClass() @@ -520,15 +519,21 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { StartAttributeStream("exact") << std::boolalpha << info.IsExact() << std::noboolalpha; } else if (instruction->IsLoadClass()) { StartAttributeStream("klass") << "unresolved"; - } else { + } else if (instruction->IsNullConstant()) { // The NullConstant may be added to the graph during other passes that happen between // ReferenceTypePropagation and Inliner (e.g. InstructionSimplifier). If the inliner // doesn't run or doesn't inline anything, the NullConstant remains untyped. // So we should check NullConstants for validity only after reference type propagation. - DCHECK(graph_in_bad_state_ || - (!is_after_pass_ && IsPass(SsaBuilder::kSsaBuilderPassName))) - << instruction->DebugName() << instruction->GetId() << " has invalid rti " - << (is_after_pass_ ? "after" : "before") << " pass " << pass_name_; + // + // Note: The infrastructure to properly type NullConstants everywhere is to complex to add + // for the benefits. + StartAttributeStream("klass") << "not_set"; + DCHECK(!is_after_pass_ + || !IsPass(ReferenceTypePropagation::kReferenceTypePropagationPassName)) + << " Expected a valid rti after reference type propagation"; + } else { + DCHECK(!is_after_pass_) + << "Expected a valid rti after reference type propagation"; } } if (disasm_info_ != nullptr) { diff --git a/compiler/optimizing/gvn_test.cc b/compiler/optimizing/gvn_test.cc index 9929696ded..de60cf21aa 100644 --- a/compiler/optimizing/gvn_test.cc +++ b/compiler/optimizing/gvn_test.cc @@ -21,11 +21,11 @@ #include "optimizing_unit_test.h" #include "side_effects_analysis.h" -namespace art { +#include "gtest/gtest.h" -class GVNTest : public CommonCompilerTest {}; +namespace art { -TEST_F(GVNTest, LocalFieldElimination) { +TEST(GVNTest, LocalFieldElimination) { ArenaPool pool; ArenaAllocator allocator(&pool); NullHandle<mirror::DexCache> dex_cache; @@ -100,7 +100,7 @@ TEST_F(GVNTest, LocalFieldElimination) { ASSERT_EQ(different_offset->GetBlock(), block); ASSERT_EQ(use_after_kill->GetBlock(), block); - TransformToSsa(graph); + graph->TryBuildingSsa(); SideEffectsAnalysis side_effects(graph); side_effects.Run(); GVNOptimization(graph, side_effects).Run(); @@ -110,7 +110,7 @@ TEST_F(GVNTest, LocalFieldElimination) { ASSERT_EQ(use_after_kill->GetBlock(), block); } -TEST_F(GVNTest, GlobalFieldElimination) { +TEST(GVNTest, GlobalFieldElimination) { ArenaPool pool; ArenaAllocator allocator(&pool); NullHandle<mirror::DexCache> dex_cache; @@ -182,7 +182,7 @@ TEST_F(GVNTest, GlobalFieldElimination) { 0)); join->AddInstruction(new (&allocator) HExit()); - TransformToSsa(graph); + graph->TryBuildingSsa(); SideEffectsAnalysis side_effects(graph); side_effects.Run(); GVNOptimization(graph, side_effects).Run(); @@ -193,7 +193,7 @@ TEST_F(GVNTest, GlobalFieldElimination) { ASSERT_TRUE(join->GetFirstInstruction()->IsExit()); } -TEST_F(GVNTest, LoopFieldElimination) { +TEST(GVNTest, LoopFieldElimination) { ArenaPool pool; ArenaAllocator allocator(&pool); NullHandle<mirror::DexCache> dex_cache; @@ -288,7 +288,7 @@ TEST_F(GVNTest, LoopFieldElimination) { ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body); ASSERT_EQ(field_get_in_exit->GetBlock(), exit); - TransformToSsa(graph); + graph->TryBuildingSsa(); { SideEffectsAnalysis side_effects(graph); side_effects.Run(); @@ -316,7 +316,7 @@ TEST_F(GVNTest, LoopFieldElimination) { } // Test that inner loops affect the side effects of the outer loop. -TEST_F(GVNTest, LoopSideEffects) { +TEST(GVNTest, LoopSideEffects) { ArenaPool pool; ArenaAllocator allocator(&pool); NullHandle<mirror::DexCache> dex_cache; @@ -364,7 +364,7 @@ TEST_F(GVNTest, LoopSideEffects) { inner_loop_exit->AddInstruction(new (&allocator) HGoto()); outer_loop_exit->AddInstruction(new (&allocator) HExit()); - TransformToSsa(graph); + graph->TryBuildingSsa(); ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn( *outer_loop_header->GetLoopInformation())); diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc index 0b7fdf85ea..19e6cbd314 100644 --- a/compiler/optimizing/induction_var_analysis.cc +++ b/compiler/optimizing/induction_var_analysis.cc @@ -71,10 +71,10 @@ HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph) } void HInductionVarAnalysis::Run() { - // Detects sequence variables (generalized induction variables) during an inner-loop-first - // traversal of all loops using Gerlek's algorithm. The order is only relevant if outer - // loops would use induction information of inner loops (not currently done). - for (HPostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) { + // Detects sequence variables (generalized induction variables) during an outer to inner + // traversal of all loops using Gerlek's algorithm. The order is important to enable + // range analysis on outer loop while visiting inner loops. + for (HReversePostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) { HBasicBlock* graph_block = it_graph.Current(); if (graph_block->IsLoopHeader()) { VisitLoop(graph_block->GetLoopInformation()); @@ -745,8 +745,7 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv if (value == 1) { return b; } else if (value == -1) { - op = kNeg; - a = nullptr; + return CreateSimplifiedInvariant(kNeg, nullptr, b); } } } @@ -763,41 +762,27 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv if (value == 1) { return a; } else if (value == -1) { - op = kNeg; - b = a; - a = nullptr; + return CreateSimplifiedInvariant(kNeg, nullptr, a); } } } else if (b->operation == kNeg) { // Simplify a + (-b) = a - b, a - (-b) = a + b, -(-b) = b. if (op == kAdd) { - op = kSub; - b = b->op_b; + return CreateSimplifiedInvariant(kSub, a, b->op_b); } else if (op == kSub) { - op = kAdd; - b = b->op_b; + return CreateSimplifiedInvariant(kAdd, a, b->op_b); } else if (op == kNeg) { return b->op_b; } + } else if (b->operation == kSub) { + // Simplify - (a - b) = b - a. + if (op == kNeg) { + return CreateSimplifiedInvariant(kSub, b->op_b, b->op_a); + } } return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr); } -bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1, - InductionInfo* info2) { - // Test structural equality only, without accounting for simplifications. - if (info1 != nullptr && info2 != nullptr) { - return - info1->induction_class == info2->induction_class && - info1->operation == info2->operation && - info1->fetch == info2->fetch && - InductionEqual(info1->op_a, info2->op_a) && - InductionEqual(info1->op_b, info2->op_b); - } - // Otherwise only two nullptrs are considered equal. - return info1 == info2; -} - bool HInductionVarAnalysis::IsIntAndGet(InductionInfo* info, int64_t* value) { if (info != nullptr && info->induction_class == kInvariant) { // A direct constant fetch. @@ -812,19 +797,35 @@ bool HInductionVarAnalysis::IsIntAndGet(InductionInfo* info, int64_t* value) { } } // Use range analysis to resolve compound values. - int32_t range_value; - if (InductionVarRange::GetConstant(info, &range_value)) { - *value = range_value; + InductionVarRange range(this); + int32_t min_val = 0; + int32_t max_val = 0; + if (range.IsConstantRange(info, &min_val, &max_val) && min_val == max_val) { + *value = min_val; return true; } } return false; } +bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1, + InductionInfo* info2) { + // Test structural equality only, without accounting for simplifications. + if (info1 != nullptr && info2 != nullptr) { + return + info1->induction_class == info2->induction_class && + info1->operation == info2->operation && + info1->fetch == info2->fetch && + InductionEqual(info1->op_a, info2->op_a) && + InductionEqual(info1->op_b, info2->op_b); + } + // Otherwise only two nullptrs are considered equal. + return info1 == info2; +} + std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) { if (info != nullptr) { if (info->induction_class == kInvariant) { - int64_t value = -1; std::string inv = "("; inv += InductionToString(info->op_a); switch (info->operation) { @@ -840,8 +841,10 @@ std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) { case kGE: inv += " >= "; break; case kFetch: DCHECK(info->fetch); - if (IsIntAndGet(info, &value)) { - inv += std::to_string(value); + if (info->fetch->IsIntConstant()) { + inv += std::to_string(info->fetch->AsIntConstant()->GetValue()); + } else if (info->fetch->IsLongConstant()) { + inv += std::to_string(info->fetch->AsLongConstant()->GetValue()); } else { inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName(); } diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h index cf354093f2..84d5d82568 100644 --- a/compiler/optimizing/induction_var_analysis.h +++ b/compiler/optimizing/induction_var_analysis.h @@ -188,9 +188,11 @@ class HInductionVarAnalysis : public HOptimization { InductionInfo* CreateConstant(int64_t value, Primitive::Type type); InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b); + // Constants. + bool IsIntAndGet(InductionInfo* info, int64_t* value); + // Helpers. static bool InductionEqual(InductionInfo* info1, InductionInfo* info2); - static bool IsIntAndGet(InductionInfo* info, int64_t* value); static std::string InductionToString(InductionInfo* info); // TODO: fine tune the following data structures, only keep relevant data. diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc index 776c115e9d..5de94f43c9 100644 --- a/compiler/optimizing/induction_var_analysis_test.cc +++ b/compiler/optimizing/induction_var_analysis_test.cc @@ -18,6 +18,7 @@ #include "base/arena_allocator.h" #include "builder.h" +#include "gtest/gtest.h" #include "induction_var_analysis.h" #include "nodes.h" #include "optimizing_unit_test.h" @@ -27,7 +28,7 @@ namespace art { /** * Fixture class for the InductionVarAnalysis tests. */ -class InductionVarAnalysisTest : public CommonCompilerTest { +class InductionVarAnalysisTest : public testing::Test { public: InductionVarAnalysisTest() : pool_(), allocator_(&pool_) { graph_ = CreateGraph(&allocator_); @@ -101,7 +102,6 @@ class InductionVarAnalysisTest : public CommonCompilerTest { basic_[d] = new (&allocator_) HLocal(d); entry_->AddInstruction(basic_[d]); loop_preheader_[d]->AddInstruction(new (&allocator_) HStoreLocal(basic_[d], constant0_)); - loop_preheader_[d]->AddInstruction(new (&allocator_) HGoto()); HInstruction* load = new (&allocator_) HLoadLocal(basic_[d], Primitive::kPrimInt); loop_header_[d]->AddInstruction(load); HInstruction* compare = new (&allocator_) HLessThan(load, constant100_); @@ -168,7 +168,7 @@ class InductionVarAnalysisTest : public CommonCompilerTest { // Performs InductionVarAnalysis (after proper set up). void PerformInductionVarAnalysis() { - TransformToSsa(graph_); + ASSERT_TRUE(graph_->TryBuildingSsa()); iva_ = new (&allocator_) HInductionVarAnalysis(graph_); iva_->Run(); } @@ -212,7 +212,7 @@ TEST_F(InductionVarAnalysisTest, ProperLoopSetup) { // .. // } BuildLoopNest(10); - TransformToSsa(graph_); + ASSERT_TRUE(graph_->TryBuildingSsa()); ASSERT_EQ(entry_->GetLoopInformation(), nullptr); for (int d = 0; d < 1; d++) { ASSERT_EQ(loop_preheader_[d]->GetLoopInformation(), diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc index 9d0cde7c9f..ae15fcf381 100644 --- a/compiler/optimizing/induction_var_range.cc +++ b/compiler/optimizing/induction_var_range.cc @@ -119,7 +119,7 @@ void InductionVarRange::GetInductionRange(HInstruction* context, } } -bool InductionVarRange::RefineOuter(/*in-out*/Value* min_val, /*in-out*/Value* max_val) { +bool InductionVarRange::RefineOuter(/*in-out*/Value* min_val, /*in-out*/Value* max_val) const { Value v1 = RefineOuter(*min_val, /* is_min */ true); Value v2 = RefineOuter(*max_val, /* is_min */ false); if (v1.instruction != min_val->instruction || v2.instruction != max_val->instruction) { @@ -167,7 +167,7 @@ void InductionVarRange::GenerateTakenTest(HInstruction* context, // Private class methods. // -bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) { +bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const { if (info != nullptr) { if (info->induction_class == HInductionVarAnalysis::kLinear) { return true; @@ -178,7 +178,7 @@ bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* inf return false; } -bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) { +bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const { if (trip != nullptr) { if (trip->induction_class == HInductionVarAnalysis::kInvariant) { return trip->operation == HInductionVarAnalysis::kTripCountInBody || @@ -188,7 +188,7 @@ bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* tr return false; } -bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) { +bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const { if (trip != nullptr) { if (trip->induction_class == HInductionVarAnalysis::kInvariant) { return trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe || @@ -198,10 +198,57 @@ bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* return false; } +InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* trip, + bool in_body, + bool is_min) const { + // Detect common situation where an offset inside the trip count cancels out during range + // analysis (finding max a * (TC - 1) + OFFSET for a == 1 and TC = UPPER - OFFSET or finding + // min a * (TC - 1) + OFFSET for a == -1 and TC = OFFSET - UPPER) to avoid losing information + // with intermediate results that only incorporate single instructions. + if (trip != nullptr) { + HInductionVarAnalysis::InductionInfo* trip_expr = trip->op_a; + if (trip_expr->operation == HInductionVarAnalysis::kSub) { + int32_t min_value = 0; + int32_t stride_value = 0; + if (IsConstantRange(info->op_a, &min_value, &stride_value) && min_value == stride_value) { + if (!is_min && stride_value == 1) { + // Test original trip's negative operand (trip_expr->op_b) against + // the offset of the linear induction. + if (HInductionVarAnalysis::InductionEqual(trip_expr->op_b, info->op_b)) { + // Analyze cancelled trip with just the positive operand (trip_expr->op_a). + HInductionVarAnalysis::InductionInfo cancelled_trip( + trip->induction_class, trip->operation, trip_expr->op_a, trip->op_b, nullptr); + return GetVal(&cancelled_trip, trip, in_body, is_min); + } + } else if (is_min && stride_value == -1) { + // Test original trip's positive operand (trip_expr->op_a) against + // the offset of the linear induction. + if (HInductionVarAnalysis::InductionEqual(trip_expr->op_a, info->op_b)) { + // Analyze cancelled trip with just the negative operand (trip_expr->op_b). + HInductionVarAnalysis::InductionInfo neg( + HInductionVarAnalysis::kInvariant, + HInductionVarAnalysis::kNeg, + nullptr, + trip_expr->op_b, + nullptr); + HInductionVarAnalysis::InductionInfo cancelled_trip( + trip->induction_class, trip->operation, &neg, trip->op_b, nullptr); + return SubValue(Value(0), GetVal(&cancelled_trip, trip, in_body, !is_min)); + } + } + } + } + } + // General rule of linear induction a * i + b, for normalized 0 <= i < TC. + return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min), + GetVal(info->op_b, trip, in_body, is_min)); +} + InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, HInductionVarAnalysis::InductionInfo* trip, bool in_body, - bool is_min) { + bool is_min) const { // Detect constants and chase the fetch a bit deeper into the HIR tree, so that it becomes // more likely range analysis will compare the same instructions as terminal nodes. int32_t value; @@ -227,7 +274,7 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, bool in_body, - bool is_min) { + bool is_min) const { if (info != nullptr) { switch (info->induction_class) { case HInductionVarAnalysis::kInvariant: @@ -266,13 +313,11 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct break; } break; - case HInductionVarAnalysis::kLinear: - // Linear induction a * i + b, for normalized 0 <= i < TC. - return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min), - GetVal(info->op_b, trip, in_body, is_min)); + case HInductionVarAnalysis::kLinear: { + return GetLinear(info, trip, in_body, is_min); + } case HInductionVarAnalysis::kWrapAround: case HInductionVarAnalysis::kPeriodic: - // Merge values in the wrap-around/periodic. return MergeVal(GetVal(info->op_a, trip, in_body, is_min), GetVal(info->op_b, trip, in_body, is_min), is_min); } @@ -284,11 +329,17 @@ InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::Induct HInductionVarAnalysis::InductionInfo* info2, HInductionVarAnalysis::InductionInfo* trip, bool in_body, - bool is_min) { + bool is_min) const { Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true); Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false); Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true); Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false); + // Try to refine certain failure. + if (v1_min.a_constant && v1_max.a_constant) { + v1_min = RefineOuter(v1_min, /* is_min */ true); + v1_max = RefineOuter(v1_max, /* is_min */ false); + } + // Positive or negative range? if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant >= 0) { // Positive range vs. positive or negative range. if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) { @@ -298,7 +349,7 @@ InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::Induct return is_min ? MulValue(v1_max, v2_min) : MulValue(v1_min, v2_max); } - } else if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant <= 0) { + } else if (v1_max.is_known && v1_max.a_constant == 0 && v1_max.b_constant <= 0) { // Negative range vs. positive or negative range. if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) { return is_min ? MulValue(v1_min, v2_max) @@ -315,11 +366,12 @@ InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::Induct HInductionVarAnalysis::InductionInfo* info2, HInductionVarAnalysis::InductionInfo* trip, bool in_body, - bool is_min) { + bool is_min) const { Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true); Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false); Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true); Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false); + // Positive or negative range? if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant >= 0) { // Positive range vs. positive or negative range. if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) { @@ -329,7 +381,7 @@ InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::Induct return is_min ? DivValue(v1_max, v2_max) : DivValue(v1_min, v2_min); } - } else if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant <= 0) { + } else if (v1_max.is_known && v1_max.a_constant == 0 && v1_max.b_constant <= 0) { // Negative range vs. positive or negative range. if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) { return is_min ? DivValue(v1_min, v2_min) @@ -342,19 +394,23 @@ InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::Induct return Value(); } -bool InductionVarRange::GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t *value) { - Value v_min = GetVal(info, nullptr, false, /* is_min */ true); - Value v_max = GetVal(info, nullptr, false, /* is_min */ false); - if (v_min.is_known && v_max.is_known) { - if (v_min.a_constant == 0 && v_max.a_constant == 0 && v_min.b_constant == v_max.b_constant) { - *value = v_min.b_constant; +bool InductionVarRange::IsConstantRange(HInductionVarAnalysis::InductionInfo* info, + int32_t *min_value, + int32_t *max_value) const { + bool in_body = true; // no known trip count + Value v_min = GetVal(info, nullptr, in_body, /* is_min */ true); + Value v_max = GetVal(info, nullptr, in_body, /* is_min */ false); + do { + if (v_min.is_known && v_min.a_constant == 0 && v_max.is_known && v_max.a_constant == 0) { + *min_value = v_min.b_constant; + *max_value = v_max.b_constant; return true; } - } + } while (RefineOuter(&v_min, &v_max)); return false; } -InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) { +InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const { if (v1.is_known && v2.is_known && IsSafeAdd(v1.b_constant, v2.b_constant)) { const int32_t b = v1.b_constant + v2.b_constant; if (v1.a_constant == 0) { @@ -368,7 +424,7 @@ InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) { return Value(); } -InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) { +InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) const { if (v1.is_known && v2.is_known && IsSafeSub(v1.b_constant, v2.b_constant)) { const int32_t b = v1.b_constant - v2.b_constant; if (v1.a_constant == 0 && IsSafeSub(0, v2.a_constant)) { @@ -382,7 +438,7 @@ InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) { return Value(); } -InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) { +InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) const { if (v1.is_known && v2.is_known) { if (v1.a_constant == 0) { if (IsSafeMul(v1.b_constant, v2.a_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) { @@ -397,7 +453,7 @@ InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) { return Value(); } -InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) { +InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) const { if (v1.is_known && v2.is_known && v1.a_constant == 0 && v2.a_constant == 0) { if (IsSafeDiv(v1.b_constant, v2.b_constant)) { return Value(v1.b_constant / v2.b_constant); @@ -406,7 +462,7 @@ InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) { return Value(); } -InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is_min) { +InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is_min) const { if (v1.is_known && v2.is_known) { if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) { return Value(v1.instruction, v1.a_constant, @@ -417,7 +473,7 @@ InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is return Value(); } -InductionVarRange::Value InductionVarRange::RefineOuter(Value v, bool is_min) { +InductionVarRange::Value InductionVarRange::RefineOuter(Value v, bool is_min) const { if (v.instruction != nullptr) { HLoopInformation* loop = v.instruction->GetBlock()->GetLoopInformation(); // closest enveloping loop @@ -444,7 +500,7 @@ bool InductionVarRange::GenerateCode(HInstruction* context, /*out*/HInstruction** upper, /*out*/HInstruction** taken_test, /*out*/bool* needs_finite_test, - /*out*/bool* needs_taken_test) { + /*out*/bool* needs_taken_test) const { HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop if (loop != nullptr) { // Set up loop information. @@ -492,7 +548,7 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, HBasicBlock* block, /*out*/HInstruction** result, bool in_body, - bool is_min) { + bool is_min) const { if (info != nullptr) { // Handle current operation. Primitive::Type type = Primitive::kPrimInt; @@ -586,8 +642,9 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, case HInductionVarAnalysis::kLinear: { // Linear induction a * i + b, for normalized 0 <= i < TC. Restrict to unit stride only // to avoid arithmetic wrap-around situations that are hard to guard against. + int32_t min_value = 0; int32_t stride_value = 0; - if (GetConstant(info->op_a, &stride_value)) { + if (IsConstantRange(info->op_a, &min_value, &stride_value) && min_value == stride_value) { if (stride_value == 1 || stride_value == -1) { const bool is_min_a = stride_value == 1 ? is_min : !is_min; if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) && diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h index 71b0b1b4c3..974b8fba06 100644 --- a/compiler/optimizing/induction_var_range.h +++ b/compiler/optimizing/induction_var_range.h @@ -69,7 +69,7 @@ class InductionVarRange { /*out*/bool* needs_finite_test); /** Refines the values with induction of next outer loop. Returns true on change. */ - bool RefineOuter(/*in-out*/Value* min_val, /*in-out*/Value* max_val); + bool RefineOuter(/*in-out*/Value* min_val, /*in-out*/Value* max_val) const; /** * Returns true if range analysis is able to generate code for the lower and upper @@ -116,46 +116,48 @@ class InductionVarRange { /*out*/HInstruction** taken_test); private: - // - // Private helper methods. - // - - static bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info); - static bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip); - static bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip); - - static Value GetFetch(HInstruction* instruction, - HInductionVarAnalysis::InductionInfo* trip, - bool in_body, - bool is_min); - static Value GetVal(HInductionVarAnalysis::InductionInfo* info, - HInductionVarAnalysis::InductionInfo* trip, - bool in_body, - bool is_min); - static Value GetMul(HInductionVarAnalysis::InductionInfo* info1, - HInductionVarAnalysis::InductionInfo* info2, - HInductionVarAnalysis::InductionInfo* trip, - bool in_body, - bool is_min); - static Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, - HInductionVarAnalysis::InductionInfo* info2, - HInductionVarAnalysis::InductionInfo* trip, - bool in_body, - bool is_min); - - static bool GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t *value); - - static Value AddValue(Value v1, Value v2); - static Value SubValue(Value v1, Value v2); - static Value MulValue(Value v1, Value v2); - static Value DivValue(Value v1, Value v2); - static Value MergeVal(Value v1, Value v2, bool is_min); + bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const; + bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const; + bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const; + + Value GetLinear(HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* trip, + bool in_body, + bool is_min) const; + Value GetFetch(HInstruction* instruction, + HInductionVarAnalysis::InductionInfo* trip, + bool in_body, + bool is_min) const; + Value GetVal(HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* trip, + bool in_body, + bool is_min) const; + Value GetMul(HInductionVarAnalysis::InductionInfo* info1, + HInductionVarAnalysis::InductionInfo* info2, + HInductionVarAnalysis::InductionInfo* trip, + bool in_body, + bool is_min) const; + Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, + HInductionVarAnalysis::InductionInfo* info2, + HInductionVarAnalysis::InductionInfo* trip, + bool in_body, + bool is_min) const; + + bool IsConstantRange(HInductionVarAnalysis::InductionInfo* info, + int32_t *min_value, + int32_t *max_value) const; + + Value AddValue(Value v1, Value v2) const; + Value SubValue(Value v1, Value v2) const; + Value MulValue(Value v1, Value v2) const; + Value DivValue(Value v1, Value v2) const; + Value MergeVal(Value v1, Value v2, bool is_min) const; /** * Returns refined value using induction of next outer loop or the input value if no * further refinement is possible. */ - Value RefineOuter(Value val, bool is_min); + Value RefineOuter(Value val, bool is_min) const; /** * Generates code for lower/upper/taken-test in the HIR. Returns true on success. @@ -170,15 +172,15 @@ class InductionVarRange { /*out*/HInstruction** upper, /*out*/HInstruction** taken_test, /*out*/bool* needs_finite_test, - /*out*/bool* needs_taken_test); - - static bool GenerateCode(HInductionVarAnalysis::InductionInfo* info, - HInductionVarAnalysis::InductionInfo* trip, - HGraph* graph, - HBasicBlock* block, - /*out*/HInstruction** result, - bool in_body, - bool is_min); + /*out*/bool* needs_taken_test) const; + + bool GenerateCode(HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* trip, + HGraph* graph, + HBasicBlock* block, + /*out*/HInstruction** result, + bool in_body, + bool is_min) const; /** Results of prior induction variable analysis. */ HInductionVarAnalysis *induction_analysis_; diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc index a1c797a80a..5c0bdd7c4c 100644 --- a/compiler/optimizing/induction_var_range_test.cc +++ b/compiler/optimizing/induction_var_range_test.cc @@ -16,6 +16,7 @@ #include "base/arena_allocator.h" #include "builder.h" +#include "gtest/gtest.h" #include "induction_var_analysis.h" #include "induction_var_range.h" #include "nodes.h" @@ -28,11 +29,14 @@ using Value = InductionVarRange::Value; /** * Fixture class for the InductionVarRange tests. */ -class InductionVarRangeTest : public CommonCompilerTest { +class InductionVarRangeTest : public testing::Test { public: - InductionVarRangeTest() : pool_(), allocator_(&pool_) { - graph_ = CreateGraph(&allocator_); - iva_ = new (&allocator_) HInductionVarAnalysis(graph_); + InductionVarRangeTest() + : pool_(), + allocator_(&pool_), + graph_(CreateGraph(&allocator_)), + iva_(new (&allocator_) HInductionVarAnalysis(graph_)), + range_(iva_) { BuildGraph(); } @@ -58,6 +62,11 @@ class InductionVarRangeTest : public CommonCompilerTest { graph_->AddBlock(exit_block_); graph_->SetEntryBlock(entry_block_); graph_->SetExitBlock(exit_block_); + // Two parameters. + x_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); + entry_block_->AddInstruction(x_); + y_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); + entry_block_->AddInstruction(y_); } /** Constructs loop with given upper bound. */ @@ -102,9 +111,9 @@ class InductionVarRangeTest : public CommonCompilerTest { exit_block_->AddInstruction(new (&allocator_) HExit()); } - /** Performs induction variable analysis. */ + /** Constructs SSA and performs induction variable analysis. */ void PerformInductionVarAnalysis() { - TransformToSsa(graph_); + ASSERT_TRUE(graph_->TryBuildingSsa()); iva_->Run(); } @@ -179,49 +188,51 @@ class InductionVarRangeTest : public CommonCompilerTest { // bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) { - return InductionVarRange::NeedsTripCount(info); + return range_.NeedsTripCount(info); } bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) { - return InductionVarRange::IsBodyTripCount(trip); + return range_.IsBodyTripCount(trip); } bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) { - return InductionVarRange::IsUnsafeTripCount(trip); + return range_.IsUnsafeTripCount(trip); } Value GetMin(HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* induc) { - return InductionVarRange::GetVal(info, induc, /* in_body */ true, /* is_min */ true); + return range_.GetVal(info, induc, /* in_body */ true, /* is_min */ true); } Value GetMax(HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* induc) { - return InductionVarRange::GetVal(info, induc, /* in_body */ true, /* is_min */ false); + return range_.GetVal(info, induc, /* in_body */ true, /* is_min */ false); } Value GetMul(HInductionVarAnalysis::InductionInfo* info1, HInductionVarAnalysis::InductionInfo* info2, bool is_min) { - return InductionVarRange::GetMul(info1, info2, nullptr, /* in_body */ true, is_min); + return range_.GetMul(info1, info2, nullptr, /* in_body */ true, is_min); } Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, HInductionVarAnalysis::InductionInfo* info2, bool is_min) { - return InductionVarRange::GetDiv(info1, info2, nullptr, /* in_body */ true, is_min); + return range_.GetDiv(info1, info2, nullptr, /* in_body */ true, is_min); } - bool GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t* value) { - return InductionVarRange::GetConstant(info, value); + bool IsConstantRange(HInductionVarAnalysis::InductionInfo* info, + int32_t* min_value, + int32_t* max_value) { + return range_.IsConstantRange(info, min_value, max_value); } - Value AddValue(Value v1, Value v2) { return InductionVarRange::AddValue(v1, v2); } - Value SubValue(Value v1, Value v2) { return InductionVarRange::SubValue(v1, v2); } - Value MulValue(Value v1, Value v2) { return InductionVarRange::MulValue(v1, v2); } - Value DivValue(Value v1, Value v2) { return InductionVarRange::DivValue(v1, v2); } - Value MinValue(Value v1, Value v2) { return InductionVarRange::MergeVal(v1, v2, true); } - Value MaxValue(Value v1, Value v2) { return InductionVarRange::MergeVal(v1, v2, false); } + Value AddValue(Value v1, Value v2) { return range_.AddValue(v1, v2); } + Value SubValue(Value v1, Value v2) { return range_.SubValue(v1, v2); } + Value MulValue(Value v1, Value v2) { return range_.MulValue(v1, v2); } + Value DivValue(Value v1, Value v2) { return range_.DivValue(v1, v2); } + Value MinValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, true); } + Value MaxValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, false); } // General building fields. ArenaPool pool_; @@ -231,16 +242,17 @@ class InductionVarRangeTest : public CommonCompilerTest { HBasicBlock* exit_block_; HBasicBlock* loop_preheader_; HInductionVarAnalysis* iva_; + InductionVarRange range_; // Instructions. HInstruction* condition_; HInstruction* increment_; - HReturnVoid x_; - HReturnVoid y_; + HInstruction* x_; + HInstruction* y_; }; // -// Tests on static methods. +// Tests on private methods. // TEST_F(InductionVarRangeTest, TripCountProperties) { @@ -273,14 +285,14 @@ TEST_F(InductionVarRangeTest, GetMinMaxAdd) { GetMin(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr)); ExpectEqual(Value(22), GetMax(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr)); - ExpectEqual(Value(&x_, 1, -20), - GetMin(CreateInvariant('+', CreateFetch(&x_), CreateRange(-20, -10)), nullptr)); - ExpectEqual(Value(&x_, 1, -10), - GetMax(CreateInvariant('+', CreateFetch(&x_), CreateRange(-20, -10)), nullptr)); - ExpectEqual(Value(&x_, 1, 10), - GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(&x_)), nullptr)); - ExpectEqual(Value(&x_, 1, 20), - GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(&x_)), nullptr)); + ExpectEqual(Value(x_, 1, -20), + GetMin(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); + ExpectEqual(Value(x_, 1, -10), + GetMax(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); + ExpectEqual(Value(x_, 1, 10), + GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr)); + ExpectEqual(Value(x_, 1, 20), + GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr)); ExpectEqual(Value(5), GetMin(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); ExpectEqual(Value(19), @@ -292,14 +304,14 @@ TEST_F(InductionVarRangeTest, GetMinMaxSub) { GetMin(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr)); ExpectEqual(Value(-8), GetMax(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr)); - ExpectEqual(Value(&x_, 1, 10), - GetMin(CreateInvariant('-', CreateFetch(&x_), CreateRange(-20, -10)), nullptr)); - ExpectEqual(Value(&x_, 1, 20), - GetMax(CreateInvariant('-', CreateFetch(&x_), CreateRange(-20, -10)), nullptr)); - ExpectEqual(Value(&x_, -1, 10), - GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(&x_)), nullptr)); - ExpectEqual(Value(&x_, -1, 20), - GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(&x_)), nullptr)); + ExpectEqual(Value(x_, 1, 10), + GetMin(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); + ExpectEqual(Value(x_, 1, 20), + GetMax(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); + ExpectEqual(Value(x_, -1, 10), + GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr)); + ExpectEqual(Value(x_, -1, 20), + GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr)); ExpectEqual(Value(-25), GetMin(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); ExpectEqual(Value(-11), @@ -311,8 +323,8 @@ TEST_F(InductionVarRangeTest, GetMinMaxNeg) { ExpectEqual(Value(-10), GetMax(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr)); ExpectEqual(Value(10), GetMin(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr)); ExpectEqual(Value(20), GetMax(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr)); - ExpectEqual(Value(&x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(&x_)), nullptr)); - ExpectEqual(Value(&x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(&x_)), nullptr)); + ExpectEqual(Value(x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr)); + ExpectEqual(Value(x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr)); } TEST_F(InductionVarRangeTest, GetMinMaxMul) { @@ -335,8 +347,8 @@ TEST_F(InductionVarRangeTest, GetMinMaxConstant) { } TEST_F(InductionVarRangeTest, GetMinMaxFetch) { - ExpectEqual(Value(&x_, 1, 0), GetMin(CreateFetch(&x_), nullptr)); - ExpectEqual(Value(&x_, 1, 0), GetMax(CreateFetch(&x_), nullptr)); + ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(x_), nullptr)); + ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(x_), nullptr)); } TEST_F(InductionVarRangeTest, GetMinMaxLinear) { @@ -363,45 +375,70 @@ TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) { TEST_F(InductionVarRangeTest, GetMulMin) { ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), true)); ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), true)); + ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), true)); ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), true)); ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), true)); + ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), true)); + ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), true)); + ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), true)); + ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), true)); } TEST_F(InductionVarRangeTest, GetMulMax) { ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), false)); ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), false)); + ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), false)); ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), false)); ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), false)); + ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), false)); + ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), false)); + ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), false)); + ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), false)); } TEST_F(InductionVarRangeTest, GetDivMin) { ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), true)); ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), true)); + ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), true)); ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), true)); ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), true)); + ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), true)); + ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), true)); + ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, -40), true)); + ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), true)); } TEST_F(InductionVarRangeTest, GetDivMax) { ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), false)); ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), false)); + ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), false)); ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), false)); ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false)); + ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), false)); + ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), false)); + ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, 40), false)); + ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), false)); } -TEST_F(InductionVarRangeTest, GetConstant) { - int32_t value; - ASSERT_TRUE(GetConstant(CreateConst(12345), &value)); - EXPECT_EQ(12345, value); - EXPECT_FALSE(GetConstant(CreateRange(1, 2), &value)); +TEST_F(InductionVarRangeTest, IsConstantRange) { + int32_t min_value; + int32_t max_value; + ASSERT_TRUE(IsConstantRange(CreateConst(12345), &min_value, &max_value)); + EXPECT_EQ(12345, min_value); + EXPECT_EQ(12345, max_value); + ASSERT_TRUE(IsConstantRange(CreateRange(1, 2), &min_value, &max_value)); + EXPECT_EQ(1, min_value); + EXPECT_EQ(2, max_value); + EXPECT_FALSE(IsConstantRange(CreateFetch(x_), &min_value, &max_value)); } TEST_F(InductionVarRangeTest, AddValue) { ExpectEqual(Value(110), AddValue(Value(10), Value(100))); - ExpectEqual(Value(-5), AddValue(Value(&x_, 1, -4), Value(&x_, -1, -1))); - ExpectEqual(Value(&x_, 3, -5), AddValue(Value(&x_, 2, -4), Value(&x_, 1, -1))); - ExpectEqual(Value(), AddValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); - ExpectEqual(Value(&x_, 1, 23), AddValue(Value(&x_, 1, 20), Value(3))); - ExpectEqual(Value(&y_, 1, 5), AddValue(Value(55), Value(&y_, 1, -50))); + ExpectEqual(Value(-5), AddValue(Value(x_, 1, -4), Value(x_, -1, -1))); + ExpectEqual(Value(x_, 3, -5), AddValue(Value(x_, 2, -4), Value(x_, 1, -1))); + ExpectEqual(Value(), AddValue(Value(x_, 1, 5), Value(y_, 1, -7))); + ExpectEqual(Value(x_, 1, 23), AddValue(Value(x_, 1, 20), Value(3))); + ExpectEqual(Value(y_, 1, 5), AddValue(Value(55), Value(y_, 1, -50))); const int32_t max_value = std::numeric_limits<int32_t>::max(); ExpectEqual(Value(max_value), AddValue(Value(max_value - 5), Value(5))); ExpectEqual(Value(), AddValue(Value(max_value - 5), Value(6))); // unsafe @@ -409,11 +446,11 @@ TEST_F(InductionVarRangeTest, AddValue) { TEST_F(InductionVarRangeTest, SubValue) { ExpectEqual(Value(-90), SubValue(Value(10), Value(100))); - ExpectEqual(Value(-3), SubValue(Value(&x_, 1, -4), Value(&x_, 1, -1))); - ExpectEqual(Value(&x_, 2, -3), SubValue(Value(&x_, 3, -4), Value(&x_, 1, -1))); - ExpectEqual(Value(), SubValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); - ExpectEqual(Value(&x_, 1, 17), SubValue(Value(&x_, 1, 20), Value(3))); - ExpectEqual(Value(&y_, -4, 105), SubValue(Value(55), Value(&y_, 4, -50))); + ExpectEqual(Value(-3), SubValue(Value(x_, 1, -4), Value(x_, 1, -1))); + ExpectEqual(Value(x_, 2, -3), SubValue(Value(x_, 3, -4), Value(x_, 1, -1))); + ExpectEqual(Value(), SubValue(Value(x_, 1, 5), Value(y_, 1, -7))); + ExpectEqual(Value(x_, 1, 17), SubValue(Value(x_, 1, 20), Value(3))); + ExpectEqual(Value(y_, -4, 105), SubValue(Value(55), Value(y_, 4, -50))); const int32_t min_value = std::numeric_limits<int32_t>::min(); ExpectEqual(Value(min_value), SubValue(Value(min_value + 5), Value(5))); ExpectEqual(Value(), SubValue(Value(min_value + 5), Value(6))); // unsafe @@ -421,145 +458,140 @@ TEST_F(InductionVarRangeTest, SubValue) { TEST_F(InductionVarRangeTest, MulValue) { ExpectEqual(Value(1000), MulValue(Value(10), Value(100))); - ExpectEqual(Value(), MulValue(Value(&x_, 1, -4), Value(&x_, 1, -1))); - ExpectEqual(Value(), MulValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); - ExpectEqual(Value(&x_, 9, 60), MulValue(Value(&x_, 3, 20), Value(3))); - ExpectEqual(Value(&y_, 55, -110), MulValue(Value(55), Value(&y_, 1, -2))); + ExpectEqual(Value(), MulValue(Value(x_, 1, -4), Value(x_, 1, -1))); + ExpectEqual(Value(), MulValue(Value(x_, 1, 5), Value(y_, 1, -7))); + ExpectEqual(Value(x_, 9, 60), MulValue(Value(x_, 3, 20), Value(3))); + ExpectEqual(Value(y_, 55, -110), MulValue(Value(55), Value(y_, 1, -2))); ExpectEqual(Value(), MulValue(Value(90000), Value(-90000))); // unsafe } TEST_F(InductionVarRangeTest, DivValue) { ExpectEqual(Value(25), DivValue(Value(100), Value(4))); - ExpectEqual(Value(), DivValue(Value(&x_, 1, -4), Value(&x_, 1, -1))); - ExpectEqual(Value(), DivValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); - ExpectEqual(Value(), DivValue(Value(&x_, 12, 24), Value(3))); - ExpectEqual(Value(), DivValue(Value(55), Value(&y_, 1, -50))); + ExpectEqual(Value(), DivValue(Value(x_, 1, -4), Value(x_, 1, -1))); + ExpectEqual(Value(), DivValue(Value(x_, 1, 5), Value(y_, 1, -7))); + ExpectEqual(Value(), DivValue(Value(x_, 12, 24), Value(3))); + ExpectEqual(Value(), DivValue(Value(55), Value(y_, 1, -50))); ExpectEqual(Value(), DivValue(Value(1), Value(0))); // unsafe } TEST_F(InductionVarRangeTest, MinValue) { ExpectEqual(Value(10), MinValue(Value(10), Value(100))); - ExpectEqual(Value(&x_, 1, -4), MinValue(Value(&x_, 1, -4), Value(&x_, 1, -1))); - ExpectEqual(Value(&x_, 4, -4), MinValue(Value(&x_, 4, -4), Value(&x_, 4, -1))); - ExpectEqual(Value(), MinValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); - ExpectEqual(Value(), MinValue(Value(&x_, 1, 20), Value(3))); - ExpectEqual(Value(), MinValue(Value(55), Value(&y_, 1, -50))); + ExpectEqual(Value(x_, 1, -4), MinValue(Value(x_, 1, -4), Value(x_, 1, -1))); + ExpectEqual(Value(x_, 4, -4), MinValue(Value(x_, 4, -4), Value(x_, 4, -1))); + ExpectEqual(Value(), MinValue(Value(x_, 1, 5), Value(y_, 1, -7))); + ExpectEqual(Value(), MinValue(Value(x_, 1, 20), Value(3))); + ExpectEqual(Value(), MinValue(Value(55), Value(y_, 1, -50))); } TEST_F(InductionVarRangeTest, MaxValue) { ExpectEqual(Value(100), MaxValue(Value(10), Value(100))); - ExpectEqual(Value(&x_, 1, -1), MaxValue(Value(&x_, 1, -4), Value(&x_, 1, -1))); - ExpectEqual(Value(&x_, 4, -1), MaxValue(Value(&x_, 4, -4), Value(&x_, 4, -1))); - ExpectEqual(Value(), MaxValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); - ExpectEqual(Value(), MaxValue(Value(&x_, 1, 20), Value(3))); - ExpectEqual(Value(), MaxValue(Value(55), Value(&y_, 1, -50))); + ExpectEqual(Value(x_, 1, -1), MaxValue(Value(x_, 1, -4), Value(x_, 1, -1))); + ExpectEqual(Value(x_, 4, -1), MaxValue(Value(x_, 4, -4), Value(x_, 4, -1))); + ExpectEqual(Value(), MaxValue(Value(x_, 1, 5), Value(y_, 1, -7))); + ExpectEqual(Value(), MaxValue(Value(x_, 1, 20), Value(3))); + ExpectEqual(Value(), MaxValue(Value(55), Value(y_, 1, -50))); } // -// Tests on instance methods. +// Tests on public methods. // TEST_F(InductionVarRangeTest, ConstantTripCountUp) { BuildLoop(0, graph_->GetIntConstant(1000), 1); PerformInductionVarAnalysis(); - InductionVarRange range(iva_); Value v1, v2; bool needs_finite_test = true; // In context of header: known. - range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); + range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); EXPECT_FALSE(needs_finite_test); ExpectEqual(Value(0), v1); ExpectEqual(Value(1000), v2); - EXPECT_FALSE(range.RefineOuter(&v1, &v2)); + EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); // In context of loop-body: known. - range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); + range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); EXPECT_FALSE(needs_finite_test); ExpectEqual(Value(0), v1); ExpectEqual(Value(999), v2); - EXPECT_FALSE(range.RefineOuter(&v1, &v2)); - range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); + EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); + range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); EXPECT_FALSE(needs_finite_test); ExpectEqual(Value(1), v1); ExpectEqual(Value(1000), v2); - EXPECT_FALSE(range.RefineOuter(&v1, &v2)); + EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); } TEST_F(InductionVarRangeTest, ConstantTripCountDown) { BuildLoop(1000, graph_->GetIntConstant(0), -1); PerformInductionVarAnalysis(); - InductionVarRange range(iva_); Value v1, v2; bool needs_finite_test = true; // In context of header: known. - range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); + range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); EXPECT_FALSE(needs_finite_test); ExpectEqual(Value(0), v1); ExpectEqual(Value(1000), v2); - EXPECT_FALSE(range.RefineOuter(&v1, &v2)); + EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); // In context of loop-body: known. - range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); + range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); EXPECT_FALSE(needs_finite_test); ExpectEqual(Value(1), v1); ExpectEqual(Value(1000), v2); - EXPECT_FALSE(range.RefineOuter(&v1, &v2)); - range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); + EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); + range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); EXPECT_FALSE(needs_finite_test); ExpectEqual(Value(0), v1); ExpectEqual(Value(999), v2); - EXPECT_FALSE(range.RefineOuter(&v1, &v2)); + EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); } TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { - HInstruction* parameter = new (&allocator_) HParameterValue( - graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); - entry_block_->AddInstruction(parameter); - BuildLoop(0, parameter, 1); + BuildLoop(0, x_, 1); PerformInductionVarAnalysis(); - InductionVarRange range(iva_); Value v1, v2; bool needs_finite_test = true; bool needs_taken_test = true; // In context of header: upper unknown. - range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); + range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); EXPECT_FALSE(needs_finite_test); ExpectEqual(Value(0), v1); ExpectEqual(Value(), v2); - EXPECT_FALSE(range.RefineOuter(&v1, &v2)); + EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); // In context of loop-body: known. - range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); + range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); EXPECT_FALSE(needs_finite_test); ExpectEqual(Value(0), v1); - ExpectEqual(Value(parameter, 1, -1), v2); - EXPECT_FALSE(range.RefineOuter(&v1, &v2)); - range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); + ExpectEqual(Value(x_, 1, -1), v2); + EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); + range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); EXPECT_FALSE(needs_finite_test); ExpectEqual(Value(1), v1); - ExpectEqual(Value(parameter, 1, 0), v2); - EXPECT_FALSE(range.RefineOuter(&v1, &v2)); + ExpectEqual(Value(x_, 1, 0), v2); + EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); HInstruction* lower = nullptr; HInstruction* upper = nullptr; HInstruction* taken = nullptr; // Can generate code in context of loop-body only. - EXPECT_FALSE(range.CanGenerateCode( + EXPECT_FALSE(range_.CanGenerateCode( condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test)); - ASSERT_TRUE(range.CanGenerateCode( + ASSERT_TRUE(range_.CanGenerateCode( increment_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test)); EXPECT_FALSE(needs_finite_test); EXPECT_TRUE(needs_taken_test); // Generates code. - range.GenerateRangeCode(increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper); + range_.GenerateRangeCode( + increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper); // Verify lower is 0+0. ASSERT_TRUE(lower != nullptr); @@ -580,7 +612,7 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue()); // Verify taken-test is 0<V. - range.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken); + range_.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken); ASSERT_TRUE(taken != nullptr); ASSERT_TRUE(taken->IsLessThan()); ASSERT_TRUE(taken->InputAt(0)->IsIntConstant()); @@ -589,52 +621,49 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { } TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { - HInstruction* parameter = new (&allocator_) HParameterValue( - graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); - entry_block_->AddInstruction(parameter); - BuildLoop(1000, parameter, -1); + BuildLoop(1000, x_, -1); PerformInductionVarAnalysis(); - InductionVarRange range(iva_); Value v1, v2; bool needs_finite_test = true; bool needs_taken_test = true; // In context of header: lower unknown. - range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); + range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); EXPECT_FALSE(needs_finite_test); ExpectEqual(Value(), v1); ExpectEqual(Value(1000), v2); - EXPECT_FALSE(range.RefineOuter(&v1, &v2)); + EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); // In context of loop-body: known. - range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); + range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); EXPECT_FALSE(needs_finite_test); - ExpectEqual(Value(parameter, 1, 1), v1); + ExpectEqual(Value(x_, 1, 1), v1); ExpectEqual(Value(1000), v2); - EXPECT_FALSE(range.RefineOuter(&v1, &v2)); - range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); + EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); + range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); EXPECT_FALSE(needs_finite_test); - ExpectEqual(Value(parameter, 1, 0), v1); + ExpectEqual(Value(x_, 1, 0), v1); ExpectEqual(Value(999), v2); - EXPECT_FALSE(range.RefineOuter(&v1, &v2)); + EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); HInstruction* lower = nullptr; HInstruction* upper = nullptr; HInstruction* taken = nullptr; // Can generate code in context of loop-body only. - EXPECT_FALSE(range.CanGenerateCode( + EXPECT_FALSE(range_.CanGenerateCode( condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test)); - ASSERT_TRUE(range.CanGenerateCode( + ASSERT_TRUE(range_.CanGenerateCode( increment_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test)); EXPECT_FALSE(needs_finite_test); EXPECT_TRUE(needs_taken_test); // Generates code. - range.GenerateRangeCode(increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper); + range_.GenerateRangeCode( + increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper); - // Verify lower is 1000-(-(V-1000)-1). + // Verify lower is 1000-((1000-V)-1). ASSERT_TRUE(lower != nullptr); ASSERT_TRUE(lower->IsSub()); ASSERT_TRUE(lower->InputAt(0)->IsIntConstant()); @@ -644,12 +673,10 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { ASSERT_TRUE(lower->InputAt(1)->IsIntConstant()); EXPECT_EQ(1, lower->InputAt(1)->AsIntConstant()->GetValue()); lower = lower->InputAt(0); - ASSERT_TRUE(lower->IsNeg()); - lower = lower->InputAt(0); ASSERT_TRUE(lower->IsSub()); - EXPECT_TRUE(lower->InputAt(0)->IsParameterValue()); - ASSERT_TRUE(lower->InputAt(1)->IsIntConstant()); - EXPECT_EQ(1000, lower->InputAt(1)->AsIntConstant()->GetValue()); + ASSERT_TRUE(lower->InputAt(0)->IsIntConstant()); + EXPECT_EQ(1000, lower->InputAt(0)->AsIntConstant()->GetValue()); + EXPECT_TRUE(lower->InputAt(1)->IsParameterValue()); // Verify upper is 1000-0. ASSERT_TRUE(upper != nullptr); @@ -660,7 +687,7 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue()); // Verify taken-test is 1000>V. - range.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken); + range_.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken); ASSERT_TRUE(taken != nullptr); ASSERT_TRUE(taken->IsGreaterThan()); ASSERT_TRUE(taken->InputAt(0)->IsIntConstant()); diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc index db1170909f..a4dcb3aeba 100644 --- a/compiler/optimizing/inliner.cc +++ b/compiler/optimizing/inliner.cc @@ -33,7 +33,6 @@ #include "reference_type_propagation.h" #include "register_allocator.h" #include "sharpening.h" -#include "ssa_builder.h" #include "ssa_phi_elimination.h" #include "scoped_thread_state_change.h" #include "thread.h" @@ -515,7 +514,7 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, return false; } - if (callee_graph->TryBuildingSsa(handles_) != kBuildSsaSuccess) { + if (!callee_graph->TryBuildingSsa()) { VLOG(compiler) << "Method " << PrettyMethod(method_index, callee_dex_file) << " could not be transformed to SSA"; return false; @@ -550,12 +549,14 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, // Run simple optimizations on the graph. HDeadCodeElimination dce(callee_graph, stats_); HConstantFolding fold(callee_graph); + ReferenceTypePropagation type_propagation(callee_graph, handles_); HSharpening sharpening(callee_graph, codegen_, dex_compilation_unit, compiler_driver_); InstructionSimplifier simplify(callee_graph, stats_); IntrinsicsRecognizer intrinsics(callee_graph, compiler_driver_); HOptimization* optimizations[] = { &intrinsics, + &type_propagation, &sharpening, &simplify, &fold, @@ -676,36 +677,42 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, DCHECK_EQ(graph_, return_replacement->GetBlock()->GetGraph()); } + // When merging the graph we might create a new NullConstant in the caller graph which does + // not have the chance to be typed. We assign the correct type here so that we can keep the + // assertion that every reference has a valid type. This also simplifies checks along the way. + HNullConstant* null_constant = graph_->GetNullConstant(); + if (!null_constant->GetReferenceTypeInfo().IsValid()) { + ReferenceTypeInfo::TypeHandle obj_handle = + handles_->NewHandle(class_linker->GetClassRoot(ClassLinker::kJavaLangObject)); + null_constant->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(obj_handle, false /* is_exact */)); + } + // Check the integrity of reference types and run another type propagation if needed. - if (return_replacement != nullptr) { - if (return_replacement->GetType() == Primitive::kPrimNot) { - if (!return_replacement->GetReferenceTypeInfo().IsValid()) { - // Make sure that we have a valid type for the return. We may get an invalid one when - // we inline invokes with multiple branches and create a Phi for the result. - // TODO: we could be more precise by merging the phi inputs but that requires - // some functionality from the reference type propagation. - DCHECK(return_replacement->IsPhi()); - size_t pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize(); - ReferenceTypeInfo::TypeHandle return_handle = - handles_->NewHandle(resolved_method->GetReturnType(true /* resolve */, pointer_size)); - return_replacement->SetReferenceTypeInfo(ReferenceTypeInfo::Create( - return_handle, return_handle->CannotBeAssignedFromOtherTypes() /* is_exact */)); - } + if ((return_replacement != nullptr) + && (return_replacement->GetType() == Primitive::kPrimNot)) { + if (!return_replacement->GetReferenceTypeInfo().IsValid()) { + // Make sure that we have a valid type for the return. We may get an invalid one when + // we inline invokes with multiple branches and create a Phi for the result. + // TODO: we could be more precise by merging the phi inputs but that requires + // some functionality from the reference type propagation. + DCHECK(return_replacement->IsPhi()); + size_t pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize(); + ReferenceTypeInfo::TypeHandle return_handle = + handles_->NewHandle(resolved_method->GetReturnType(true /* resolve */, pointer_size)); + return_replacement->SetReferenceTypeInfo(ReferenceTypeInfo::Create( + return_handle, return_handle->CannotBeAssignedFromOtherTypes() /* is_exact */)); + } - if (do_rtp) { - // If the return type is a refinement of the declared type run the type propagation again. - ReferenceTypeInfo return_rti = return_replacement->GetReferenceTypeInfo(); - ReferenceTypeInfo invoke_rti = invoke_instruction->GetReferenceTypeInfo(); - if (invoke_rti.IsStrictSupertypeOf(return_rti) - || (return_rti.IsExact() && !invoke_rti.IsExact()) - || !return_replacement->CanBeNull()) { - ReferenceTypePropagation(graph_, handles_).Run(); - } - } - } else if (return_replacement->IsInstanceOf()) { - if (do_rtp) { - // Inlining InstanceOf into an If may put a tighter bound on reference types. - ReferenceTypePropagation(graph_, handles_).Run(); + if (do_rtp) { + // If the return type is a refinement of the declared type run the type propagation again. + ReferenceTypeInfo return_rti = return_replacement->GetReferenceTypeInfo(); + ReferenceTypeInfo invoke_rti = invoke_instruction->GetReferenceTypeInfo(); + if (invoke_rti.IsStrictSupertypeOf(return_rti) + || (return_rti.IsExact() && !invoke_rti.IsExact()) + || !return_replacement->CanBeNull()) { + ReferenceTypePropagation rtp_fixup(graph_, handles_); + rtp_fixup.Run(); } } } diff --git a/compiler/optimizing/instruction_simplifier_arm64.cc b/compiler/optimizing/instruction_simplifier_arm64.cc index 6bbc751bee..6a34b13320 100644 --- a/compiler/optimizing/instruction_simplifier_arm64.cc +++ b/compiler/optimizing/instruction_simplifier_arm64.cc @@ -49,7 +49,6 @@ void InstructionSimplifierArm64Visitor::TryExtractArrayAccessAddress(HInstructio GetGraph()->GetIntConstant(mirror::Array::DataOffset(access_size).Uint32Value()); HArm64IntermediateAddress* address = new (arena) HArm64IntermediateAddress(array, offset, kNoDexPc); - address->SetReferenceTypeInfo(array->GetReferenceTypeInfo()); access->GetBlock()->InsertInstructionBefore(address, access); access->ReplaceInput(address, 0); // Both instructions must depend on GC to prevent any instruction that can diff --git a/compiler/optimizing/licm_test.cc b/compiler/optimizing/licm_test.cc index 956de2cb8a..2bb769a430 100644 --- a/compiler/optimizing/licm_test.cc +++ b/compiler/optimizing/licm_test.cc @@ -16,6 +16,7 @@ #include "base/arena_allocator.h" #include "builder.h" +#include "gtest/gtest.h" #include "licm.h" #include "nodes.h" #include "optimizing_unit_test.h" @@ -26,7 +27,7 @@ namespace art { /** * Fixture class for the LICM tests. */ -class LICMTest : public CommonCompilerTest { +class LICMTest : public testing::Test { public: LICMTest() : pool_(), allocator_(&pool_) { graph_ = CreateGraph(&allocator_); @@ -69,16 +70,16 @@ class LICMTest : public CommonCompilerTest { loop_preheader_->AddInstruction(new (&allocator_) HGoto()); loop_header_->AddInstruction(new (&allocator_) HIf(parameter_)); loop_body_->AddInstruction(new (&allocator_) HGoto()); - return_->AddInstruction(new (&allocator_) HReturnVoid()); exit_->AddInstruction(new (&allocator_) HExit()); } // Performs LICM optimizations (after proper set up). void PerformLICM() { - TransformToSsa(graph_); + ASSERT_TRUE(graph_->TryBuildingSsa()); SideEffectsAnalysis side_effects(graph_); side_effects.Run(); - LICM(graph_, side_effects).Run(); + LICM licm(graph_, side_effects); + licm.Run(); } // General building fields. @@ -168,10 +169,10 @@ TEST_F(LICMTest, ArrayHoisting) { // Populate the loop with instructions: set/get array with different types. HInstruction* get_array = new (&allocator_) HArrayGet( - parameter_, constant_, Primitive::kPrimByte, 0); + parameter_, constant_, Primitive::kPrimLong, 0); loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction()); HInstruction* set_array = new (&allocator_) HArraySet( - parameter_, constant_, constant_, Primitive::kPrimShort, 0); + parameter_, constant_, constant_, Primitive::kPrimInt, 0); loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction()); EXPECT_EQ(get_array->GetBlock(), loop_body_); @@ -186,10 +187,10 @@ TEST_F(LICMTest, NoArrayHoisting) { // Populate the loop with instructions: set/get array with same types. HInstruction* get_array = new (&allocator_) HArrayGet( - parameter_, constant_, Primitive::kPrimByte, 0); + parameter_, constant_, Primitive::kPrimLong, 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, constant_, Primitive::kPrimLong, 0); loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction()); EXPECT_EQ(get_array->GetBlock(), loop_body_); diff --git a/compiler/optimizing/linearize_test.cc b/compiler/optimizing/linearize_test.cc index ed275b1544..a059766e00 100644 --- a/compiler/optimizing/linearize_test.cc +++ b/compiler/optimizing/linearize_test.cc @@ -29,11 +29,12 @@ #include "nodes.h" #include "optimizing_unit_test.h" #include "pretty_printer.h" +#include "ssa_builder.h" #include "ssa_liveness_analysis.h" -namespace art { +#include "gtest/gtest.h" -class LinearizeTest : public CommonCompilerTest {}; +namespace art { template <size_t number_of_blocks> static void TestCode(const uint16_t* data, const uint32_t (&expected_order)[number_of_blocks]) { @@ -45,7 +46,7 @@ static void TestCode(const uint16_t* data, const uint32_t (&expected_order)[numb bool graph_built = builder.BuildGraph(*item); ASSERT_TRUE(graph_built); - TransformToSsa(graph); + graph->TryBuildingSsa(); std::unique_ptr<const X86InstructionSetFeatures> features_x86( X86InstructionSetFeatures::FromCppDefines()); @@ -59,7 +60,7 @@ static void TestCode(const uint16_t* data, const uint32_t (&expected_order)[numb } } -TEST_F(LinearizeTest, CFG1) { +TEST(LinearizeTest, CFG1) { // Structure of this graph (+ are back edges) // Block0 // | @@ -84,7 +85,7 @@ TEST_F(LinearizeTest, CFG1) { TestCode(data, blocks); } -TEST_F(LinearizeTest, CFG2) { +TEST(LinearizeTest, CFG2) { // Structure of this graph (+ are back edges) // Block0 // | @@ -109,7 +110,7 @@ TEST_F(LinearizeTest, CFG2) { TestCode(data, blocks); } -TEST_F(LinearizeTest, CFG3) { +TEST(LinearizeTest, CFG3) { // Structure of this graph (+ are back edges) // Block0 // | @@ -136,7 +137,7 @@ TEST_F(LinearizeTest, CFG3) { TestCode(data, blocks); } -TEST_F(LinearizeTest, CFG4) { +TEST(LinearizeTest, CFG4) { /* Structure of this graph (+ are back edges) // Block0 // | @@ -166,7 +167,7 @@ TEST_F(LinearizeTest, CFG4) { TestCode(data, blocks); } -TEST_F(LinearizeTest, CFG5) { +TEST(LinearizeTest, CFG5) { /* Structure of this graph (+ are back edges) // Block0 // | @@ -196,7 +197,7 @@ TEST_F(LinearizeTest, CFG5) { TestCode(data, blocks); } -TEST_F(LinearizeTest, CFG6) { +TEST(LinearizeTest, CFG6) { // Block0 // | // Block1 @@ -222,7 +223,7 @@ TEST_F(LinearizeTest, CFG6) { TestCode(data, blocks); } -TEST_F(LinearizeTest, CFG7) { +TEST(LinearizeTest, CFG7) { // Structure of this graph (+ are back edges) // Block0 // | diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc index 926f9399a5..7f67560692 100644 --- a/compiler/optimizing/live_ranges_test.cc +++ b/compiler/optimizing/live_ranges_test.cc @@ -27,9 +27,9 @@ #include "prepare_for_register_allocation.h" #include "ssa_liveness_analysis.h" -namespace art { +#include "gtest/gtest.h" -class LiveRangesTest : public CommonCompilerTest {}; +namespace art { static HGraph* BuildGraph(const uint16_t* data, ArenaAllocator* allocator) { HGraph* graph = CreateGraph(allocator); @@ -39,13 +39,13 @@ static HGraph* BuildGraph(const uint16_t* data, ArenaAllocator* allocator) { // Suspend checks implementation may change in the future, and this test relies // on how instructions are ordered. RemoveSuspendChecks(graph); - TransformToSsa(graph); + graph->TryBuildingSsa(); // `Inline` conditions into ifs. PrepareForRegisterAllocation(graph).Run(); return graph; } -TEST_F(LiveRangesTest, CFG1) { +TEST(LiveRangesTest, CFG1) { /* * Test the following snippet: * return 0; @@ -83,7 +83,7 @@ TEST_F(LiveRangesTest, CFG1) { ASSERT_TRUE(range->GetNext() == nullptr); } -TEST_F(LiveRangesTest, CFG2) { +TEST(LiveRangesTest, CFG2) { /* * Test the following snippet: * var a = 0; @@ -131,7 +131,7 @@ TEST_F(LiveRangesTest, CFG2) { ASSERT_TRUE(range->GetNext() == nullptr); } -TEST_F(LiveRangesTest, CFG3) { +TEST(LiveRangesTest, CFG3) { /* * Test the following snippet: * var a = 0; @@ -204,7 +204,7 @@ TEST_F(LiveRangesTest, CFG3) { ASSERT_TRUE(range->GetNext() == nullptr); } -TEST_F(LiveRangesTest, Loop1) { +TEST(LiveRangesTest, Loop1) { /* * Test the following snippet: * var a = 0; @@ -284,7 +284,7 @@ TEST_F(LiveRangesTest, Loop1) { ASSERT_TRUE(range->GetNext() == nullptr); } -TEST_F(LiveRangesTest, Loop2) { +TEST(LiveRangesTest, Loop2) { /* * Test the following snippet: * var a = 0; @@ -360,7 +360,7 @@ TEST_F(LiveRangesTest, Loop2) { ASSERT_TRUE(range->GetNext() == nullptr); } -TEST_F(LiveRangesTest, CFG4) { +TEST(LiveRangesTest, CFG4) { /* * Test the following snippet: * var a = 0; diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc index 7736eedae1..9d7d0b6c67 100644 --- a/compiler/optimizing/liveness_test.cc +++ b/compiler/optimizing/liveness_test.cc @@ -27,9 +27,9 @@ #include "prepare_for_register_allocation.h" #include "ssa_liveness_analysis.h" -namespace art { +#include "gtest/gtest.h" -class LivenessTest : public CommonCompilerTest {}; +namespace art { static void DumpBitVector(BitVector* vector, std::ostream& buffer, @@ -51,7 +51,7 @@ static void TestCode(const uint16_t* data, const char* expected) { const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); bool graph_built = builder.BuildGraph(*item); ASSERT_TRUE(graph_built); - TransformToSsa(graph); + graph->TryBuildingSsa(); // `Inline` conditions into ifs. PrepareForRegisterAllocation(graph).Run(); std::unique_ptr<const X86InstructionSetFeatures> features_x86( @@ -75,7 +75,7 @@ static void TestCode(const uint16_t* data, const char* expected) { ASSERT_STREQ(expected, buffer.str().c_str()); } -TEST_F(LivenessTest, CFG1) { +TEST(LivenessTest, CFG1) { const char* expected = "Block 0\n" " live in: (0)\n" @@ -98,7 +98,7 @@ TEST_F(LivenessTest, CFG1) { TestCode(data, expected); } -TEST_F(LivenessTest, CFG2) { +TEST(LivenessTest, CFG2) { const char* expected = "Block 0\n" " live in: (0)\n" @@ -120,7 +120,7 @@ TEST_F(LivenessTest, CFG2) { TestCode(data, expected); } -TEST_F(LivenessTest, CFG3) { +TEST(LivenessTest, CFG3) { const char* expected = "Block 0\n" // entry block " live in: (000)\n" @@ -149,7 +149,7 @@ TEST_F(LivenessTest, CFG3) { TestCode(data, expected); } -TEST_F(LivenessTest, CFG4) { +TEST(LivenessTest, CFG4) { // var a; // if (0 == 0) { // a = 5; @@ -197,7 +197,7 @@ TEST_F(LivenessTest, CFG4) { TestCode(data, expected); } -TEST_F(LivenessTest, CFG5) { +TEST(LivenessTest, CFG5) { // var a = 0; // if (0 == 0) { // } else { @@ -242,7 +242,7 @@ TEST_F(LivenessTest, CFG5) { TestCode(data, expected); } -TEST_F(LivenessTest, Loop1) { +TEST(LivenessTest, Loop1) { // Simple loop with one preheader and one back edge. // var a = 0; // while (a == a) { @@ -288,7 +288,7 @@ TEST_F(LivenessTest, Loop1) { TestCode(data, expected); } -TEST_F(LivenessTest, Loop3) { +TEST(LivenessTest, Loop3) { // Test that the returned value stays live in a preceding loop. // var a = 0; // while (a == a) { @@ -335,7 +335,7 @@ TEST_F(LivenessTest, Loop3) { } -TEST_F(LivenessTest, Loop4) { +TEST(LivenessTest, Loop4) { // Make sure we support a preheader of a loop not being the first predecessor // in the predecessor list of the header. // var a = 0; @@ -387,7 +387,7 @@ TEST_F(LivenessTest, Loop4) { TestCode(data, expected); } -TEST_F(LivenessTest, Loop5) { +TEST(LivenessTest, Loop5) { // Make sure we create a preheader of a loop when a header originally has two // incoming blocks and one back edge. // Bitsets are made of: @@ -443,7 +443,7 @@ TEST_F(LivenessTest, Loop5) { TestCode(data, expected); } -TEST_F(LivenessTest, Loop6) { +TEST(LivenessTest, Loop6) { // Bitsets are made of: // (constant0, constant4, constant5, phi in block 2) const char* expected = @@ -494,7 +494,7 @@ TEST_F(LivenessTest, Loop6) { } -TEST_F(LivenessTest, Loop7) { +TEST(LivenessTest, Loop7) { // Bitsets are made of: // (constant0, constant4, constant5, phi in block 2, phi in block 6) const char* expected = @@ -548,7 +548,7 @@ TEST_F(LivenessTest, Loop7) { TestCode(data, expected); } -TEST_F(LivenessTest, Loop8) { +TEST(LivenessTest, Loop8) { // var a = 0; // while (a == a) { // a = a + a; diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index bb0b545c1e..926bc156cf 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -198,38 +198,10 @@ void HGraph::ComputeDominanceInformation() { } } -BuildSsaResult HGraph::TryBuildingSsa(StackHandleScopeCollection* handles) { - BuildDominatorTree(); - - // The SSA builder requires loops to all be natural. Specifically, the dead phi - // elimination phase checks the consistency of the graph when doing a post-order - // visit for eliminating dead phis: a dead phi can only have loop header phi - // users remaining when being visited. - BuildSsaResult result = AnalyzeNaturalLoops(); - if (result != kBuildSsaSuccess) { - return result; - } - - // Precompute per-block try membership before entering the SSA builder, - // which needs the information to build catch block phis from values of - // locals at throwing instructions inside try blocks. - ComputeTryBlockInformation(); - - // Create the inexact Object reference type and store it in the HGraph. - ScopedObjectAccess soa(Thread::Current()); - ClassLinker* linker = Runtime::Current()->GetClassLinker(); - inexact_object_rti_ = ReferenceTypeInfo::Create( - handles->NewHandle(linker->GetClassRoot(ClassLinker::kJavaLangObject)), - /* is_exact */ false); - - // Tranforms graph to SSA form. - result = SsaBuilder(this, handles).BuildSsa(); - if (result != kBuildSsaSuccess) { - return result; - } - - in_ssa_form_ = true; - return kBuildSsaSuccess; +void HGraph::TransformToSsa() { + DCHECK(!reverse_post_order_.empty()); + SsaBuilder ssa_builder(this); + ssa_builder.BuildSsa(); } HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) { @@ -438,7 +410,7 @@ void HGraph::SimplifyCFG() { } } -BuildSsaResult HGraph::AnalyzeNaturalLoops() const { +bool HGraph::AnalyzeNaturalLoops() const { // Order does not matter. for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); @@ -446,16 +418,16 @@ BuildSsaResult HGraph::AnalyzeNaturalLoops() const { if (block->IsCatchBlock()) { // TODO: Dealing with exceptional back edges could be tricky because // they only approximate the real control flow. Bail out for now. - return kBuildSsaFailThrowCatchLoop; + return false; } HLoopInformation* info = block->GetLoopInformation(); if (!info->Populate()) { // Abort if the loop is non natural. We currently bailout in such cases. - return kBuildSsaFailNonNaturalLoop; + return false; } } } - return kBuildSsaSuccess; + return true; } void HGraph::InsertConstant(HConstant* constant) { @@ -474,13 +446,8 @@ HNullConstant* HGraph::GetNullConstant(uint32_t dex_pc) { // id and/or any invariants the graph is assuming when adding new instructions. if ((cached_null_constant_ == nullptr) || (cached_null_constant_->GetBlock() == nullptr)) { cached_null_constant_ = new (arena_) HNullConstant(dex_pc); - cached_null_constant_->SetReferenceTypeInfo(inexact_object_rti_); InsertConstant(cached_null_constant_); } - if (kIsDebugBuild) { - ScopedObjectAccess soa(Thread::Current()); - DCHECK(cached_null_constant_->GetReferenceTypeInfo().IsValid()); - } return cached_null_constant_; } diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 55e436f0b7..1f8ef4717c 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -98,13 +98,6 @@ enum IfCondition { kCondAE, // >= }; -enum BuildSsaResult { - kBuildSsaFailNonNaturalLoop, - kBuildSsaFailThrowCatchLoop, - kBuildSsaFailAmbiguousArrayGet, - kBuildSsaSuccess, -}; - class HInstructionList : public ValueObject { public: HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {} @@ -150,122 +143,6 @@ class HInstructionList : public ValueObject { DISALLOW_COPY_AND_ASSIGN(HInstructionList); }; -class ReferenceTypeInfo : ValueObject { - public: - typedef Handle<mirror::Class> TypeHandle; - - static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) { - // The constructor will check that the type_handle is valid. - return ReferenceTypeInfo(type_handle, is_exact); - } - - static ReferenceTypeInfo CreateInvalid() { return ReferenceTypeInfo(); } - - static bool IsValidHandle(TypeHandle handle) SHARED_REQUIRES(Locks::mutator_lock_) { - return handle.GetReference() != nullptr; - } - - bool IsValid() const SHARED_REQUIRES(Locks::mutator_lock_) { - return IsValidHandle(type_handle_); - } - - bool IsExact() const { return is_exact_; } - - bool IsObjectClass() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return GetTypeHandle()->IsObjectClass(); - } - - bool IsStringClass() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return GetTypeHandle()->IsStringClass(); - } - - bool IsObjectArray() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return IsArrayClass() && GetTypeHandle()->GetComponentType()->IsObjectClass(); - } - - bool IsInterface() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return GetTypeHandle()->IsInterface(); - } - - bool IsArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return GetTypeHandle()->IsArrayClass(); - } - - bool IsPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return GetTypeHandle()->IsPrimitiveArray(); - } - - bool IsNonPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return GetTypeHandle()->IsArrayClass() && !GetTypeHandle()->IsPrimitiveArray(); - } - - bool CanArrayHold(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - if (!IsExact()) return false; - if (!IsArrayClass()) return false; - return GetTypeHandle()->GetComponentType()->IsAssignableFrom(rti.GetTypeHandle().Get()); - } - - bool CanArrayHoldValuesOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - if (!IsExact()) return false; - if (!IsArrayClass()) return false; - if (!rti.IsArrayClass()) return false; - return GetTypeHandle()->GetComponentType()->IsAssignableFrom( - rti.GetTypeHandle()->GetComponentType()); - } - - Handle<mirror::Class> GetTypeHandle() const { return type_handle_; } - - bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - DCHECK(rti.IsValid()); - return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); - } - - bool IsStrictSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - DCHECK(rti.IsValid()); - return GetTypeHandle().Get() != rti.GetTypeHandle().Get() && - GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); - } - - // 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_) { - if (!IsValid() && !rti.IsValid()) { - // Invalid types are equal. - return true; - } - if (!IsValid() || !rti.IsValid()) { - // One is valid, the other not. - return false; - } - return IsExact() == rti.IsExact() - && GetTypeHandle().Get() == rti.GetTypeHandle().Get(); - } - - private: - ReferenceTypeInfo(); - ReferenceTypeInfo(TypeHandle type_handle, bool is_exact); - - // The class of the object. - TypeHandle type_handle_; - // Whether or not the type is exact or a superclass of the actual type. - // Whether or not we have any information about this type. - bool is_exact_; -}; - -std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs); - // Control-flow graph of a method. Contains a list of basic blocks. class HGraph : public ArenaObject<kArenaAllocGraph> { public: @@ -302,8 +179,7 @@ class HGraph : public ArenaObject<kArenaAllocGraph> { cached_float_constants_(std::less<int32_t>(), arena->Adapter(kArenaAllocConstantsMap)), cached_long_constants_(std::less<int64_t>(), arena->Adapter(kArenaAllocConstantsMap)), cached_double_constants_(std::less<int64_t>(), arena->Adapter(kArenaAllocConstantsMap)), - cached_current_method_(nullptr), - inexact_object_rti_(ReferenceTypeInfo::CreateInvalid()) { + cached_current_method_(nullptr) { blocks_.reserve(kDefaultNumberOfBlocks); } @@ -321,23 +197,36 @@ class HGraph : public ArenaObject<kArenaAllocGraph> { void AddBlock(HBasicBlock* block); - // Try building the SSA form of this graph, with dominance computation and - // loop recognition. Returns a code specifying that it was successful or the - // reason for failure. - BuildSsaResult TryBuildingSsa(StackHandleScopeCollection* handles); + // Try building the SSA form of this graph, with dominance computation and loop + // recognition. Returns whether it was successful in doing all these steps. + bool TryBuildingSsa() { + BuildDominatorTree(); + // The SSA builder requires loops to all be natural. Specifically, the dead phi + // elimination phase checks the consistency of the graph when doing a post-order + // visit for eliminating dead phis: a dead phi can only have loop header phi + // users remaining when being visited. + if (!AnalyzeNaturalLoops()) return false; + // Precompute per-block try membership before entering the SSA builder, + // which needs the information to build catch block phis from values of + // locals at throwing instructions inside try blocks. + ComputeTryBlockInformation(); + TransformToSsa(); + in_ssa_form_ = true; + return true; + } void ComputeDominanceInformation(); void ClearDominanceInformation(); void BuildDominatorTree(); + void TransformToSsa(); void SimplifyCFG(); void SimplifyCatchBlocks(); - // Analyze all natural loops in this graph. Returns a code specifying that it - // was successful or the reason for failure. The method will fail if a loop - // is not natural, that is the header does not dominate a back edge, or if it - // is a throw-catch loop, i.e. the header is a catch block. - BuildSsaResult AnalyzeNaturalLoops() const; + // Analyze all natural loops in this graph. Returns false if one + // loop is not natural, that is the header does not dominate the + // back edge. + bool AnalyzeNaturalLoops() const; // Iterate over blocks to compute try block membership. Needs reverse post // order and loop information. @@ -598,10 +487,6 @@ class HGraph : public ArenaObject<kArenaAllocGraph> { // (such as when the superclass could not be found). ArtMethod* art_method_; - // Keep the RTI of inexact Object to avoid having to pass stack handle - // collection pointer to passes which may create NullConstant. - ReferenceTypeInfo inexact_object_rti_; - friend class SsaBuilder; // For caching constants. friend class SsaLivenessAnalysis; // For the linear order. ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1); @@ -1789,6 +1674,122 @@ class HEnvironment : public ArenaObject<kArenaAllocEnvironment> { DISALLOW_COPY_AND_ASSIGN(HEnvironment); }; +class ReferenceTypeInfo : ValueObject { + public: + typedef Handle<mirror::Class> TypeHandle; + + static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) { + // The constructor will check that the type_handle is valid. + return ReferenceTypeInfo(type_handle, is_exact); + } + + static ReferenceTypeInfo CreateInvalid() { return ReferenceTypeInfo(); } + + static bool IsValidHandle(TypeHandle handle) SHARED_REQUIRES(Locks::mutator_lock_) { + return handle.GetReference() != nullptr; + } + + bool IsValid() const SHARED_REQUIRES(Locks::mutator_lock_) { + return IsValidHandle(type_handle_); + } + + bool IsExact() const { return is_exact_; } + + bool IsObjectClass() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsObjectClass(); + } + + bool IsStringClass() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsStringClass(); + } + + bool IsObjectArray() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return IsArrayClass() && GetTypeHandle()->GetComponentType()->IsObjectClass(); + } + + bool IsInterface() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsInterface(); + } + + bool IsArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsArrayClass(); + } + + bool IsPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsPrimitiveArray(); + } + + bool IsNonPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsArrayClass() && !GetTypeHandle()->IsPrimitiveArray(); + } + + bool CanArrayHold(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + if (!IsExact()) return false; + if (!IsArrayClass()) return false; + return GetTypeHandle()->GetComponentType()->IsAssignableFrom(rti.GetTypeHandle().Get()); + } + + bool CanArrayHoldValuesOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + if (!IsExact()) return false; + if (!IsArrayClass()) return false; + if (!rti.IsArrayClass()) return false; + return GetTypeHandle()->GetComponentType()->IsAssignableFrom( + rti.GetTypeHandle()->GetComponentType()); + } + + Handle<mirror::Class> GetTypeHandle() const { return type_handle_; } + + bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + DCHECK(rti.IsValid()); + return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); + } + + bool IsStrictSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + DCHECK(rti.IsValid()); + return GetTypeHandle().Get() != rti.GetTypeHandle().Get() && + GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); + } + + // 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_) { + if (!IsValid() && !rti.IsValid()) { + // Invalid types are equal. + return true; + } + if (!IsValid() || !rti.IsValid()) { + // One is valid, the other not. + return false; + } + return IsExact() == rti.IsExact() + && GetTypeHandle().Get() == rti.GetTypeHandle().Get(); + } + + private: + ReferenceTypeInfo(); + ReferenceTypeInfo(TypeHandle type_handle, bool is_exact); + + // The class of the object. + TypeHandle type_handle_; + // Whether or not the type is exact or a superclass of the actual type. + // Whether or not we have any information about this type. + bool is_exact_; +}; + +std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs); + class HInstruction : public ArenaObject<kArenaAllocInstruction> { public: HInstruction(SideEffects side_effects, uint32_t dex_pc) @@ -4416,16 +4417,7 @@ class HPhi : public HInstruction { void RemoveInputAt(size_t index); Primitive::Type GetType() const OVERRIDE { return type_; } - void SetType(Primitive::Type new_type) { - // Make sure that only valid type changes occur. The following are allowed: - // (1) int -> float/ref (primitive type propagation), - // (2) long -> double (primitive type propagation). - DCHECK(type_ == new_type || - (type_ == Primitive::kPrimInt && new_type == Primitive::kPrimFloat) || - (type_ == Primitive::kPrimInt && new_type == Primitive::kPrimNot) || - (type_ == Primitive::kPrimLong && new_type == Primitive::kPrimDouble)); - type_ = new_type; - } + void SetType(Primitive::Type type) { type_ = type; } bool CanBeNull() const OVERRIDE { return can_be_null_; } void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; } @@ -4665,21 +4657,7 @@ class HArrayGet : public HExpression<2> { return false; } - bool IsEquivalentOf(HArrayGet* other) const { - bool result = (GetDexPc() == other->GetDexPc()); - if (kIsDebugBuild && result) { - DCHECK_EQ(GetBlock(), other->GetBlock()); - DCHECK_EQ(GetArray(), other->GetArray()); - DCHECK_EQ(GetIndex(), other->GetIndex()); - if (Primitive::IsIntOrLongType(GetType())) { - DCHECK(Primitive::IsFloatingPointType(other->GetType())); - } else { - DCHECK(Primitive::IsFloatingPointType(GetType())); - DCHECK(Primitive::IsIntOrLongType(other->GetType())); - } - } - return result; - } + void SetType(Primitive::Type type) { type_ = type; } HInstruction* GetArray() const { return InputAt(0); } HInstruction* GetIndex() const { return InputAt(1); } diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index ba435180e5..831b626c4f 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -501,8 +501,11 @@ static void RunOptimizations(HGraph* graph, CompilerDriver* driver, OptimizingCompilerStats* stats, const DexCompilationUnit& dex_compilation_unit, - PassObserver* pass_observer, - StackHandleScopeCollection* handles) { + PassObserver* pass_observer) { + ScopedObjectAccess soa(Thread::Current()); + StackHandleScopeCollection handles(soa.Self()); + ScopedThreadSuspension sts(soa.Self(), kNative); + ArenaAllocator* arena = graph->GetArena(); HDeadCodeElimination* dce1 = new (arena) HDeadCodeElimination( graph, stats, HDeadCodeElimination::kInitialDeadCodeEliminationPassName); @@ -519,23 +522,29 @@ static void RunOptimizations(HGraph* graph, LoadStoreElimination* lse = new (arena) LoadStoreElimination(graph, *side_effects); HInductionVarAnalysis* induction = new (arena) HInductionVarAnalysis(graph); BoundsCheckElimination* bce = new (arena) BoundsCheckElimination(graph, *side_effects, induction); + ReferenceTypePropagation* type_propagation = + new (arena) ReferenceTypePropagation(graph, &handles); HSharpening* sharpening = new (arena) HSharpening(graph, codegen, dex_compilation_unit, driver); InstructionSimplifier* simplify2 = new (arena) InstructionSimplifier( - graph, stats, "instruction_simplifier_after_bce"); + graph, stats, "instruction_simplifier_after_types"); InstructionSimplifier* simplify3 = new (arena) InstructionSimplifier( + graph, stats, "instruction_simplifier_after_bce"); + InstructionSimplifier* simplify4 = new (arena) InstructionSimplifier( graph, stats, "instruction_simplifier_before_codegen"); IntrinsicsRecognizer* intrinsics = new (arena) IntrinsicsRecognizer(graph, driver); HOptimization* optimizations1[] = { intrinsics, - sharpening, fold1, simplify1, + type_propagation, + sharpening, dce1, + simplify2 }; RunOptimizations(optimizations1, arraysize(optimizations1), pass_observer); - MaybeRunInliner(graph, codegen, driver, stats, dex_compilation_unit, pass_observer, handles); + MaybeRunInliner(graph, codegen, driver, stats, dex_compilation_unit, pass_observer, &handles); HOptimization* optimizations2[] = { // BooleanSimplifier depends on the InstructionSimplifier removing @@ -548,13 +557,13 @@ static void RunOptimizations(HGraph* graph, induction, bce, fold3, // evaluates code generated by dynamic bce - simplify2, + simplify3, lse, dce2, // The codegen has a few assumptions that only the instruction simplifier // can satisfy. For example, the code generator does not expect to see a // HTypeConversion from a type to the same type. - simplify3, + simplify4, }; RunOptimizations(optimizations2, arraysize(optimizations2), pass_observer); @@ -759,29 +768,14 @@ CodeGenerator* OptimizingCompiler::TryCompile(ArenaAllocator* arena, } VLOG(compiler) << "Optimizing " << pass_observer.GetMethodName(); - if (run_optimizations_) { - ScopedObjectAccess soa(Thread::Current()); - StackHandleScopeCollection handles(soa.Self()); - ScopedThreadSuspension sts(soa.Self(), kNative); - { PassScope scope(SsaBuilder::kSsaBuilderPassName, &pass_observer); - BuildSsaResult result = graph->TryBuildingSsa(&handles); - if (result != kBuildSsaSuccess) { - switch (result) { - case kBuildSsaFailNonNaturalLoop: - MaybeRecordStat(MethodCompilationStat::kNotCompiledNonNaturalLoop); - break; - case kBuildSsaFailThrowCatchLoop: - MaybeRecordStat(MethodCompilationStat::kNotCompiledThrowCatchLoop); - break; - case kBuildSsaFailAmbiguousArrayGet: - MaybeRecordStat(MethodCompilationStat::kNotCompiledAmbiguousArrayGet); - break; - case kBuildSsaSuccess: - UNREACHABLE(); - } + if (!graph->TryBuildingSsa()) { + // We could not transform the graph to SSA, bailout. + LOG(INFO) << "Skipping compilation of " << pass_observer.GetMethodName() + << ": it contains a non natural loop"; + MaybeRecordStat(MethodCompilationStat::kNotCompiledCannotBuildSSA); pass_observer.SetGraphInBadState(); return nullptr; } @@ -792,8 +786,7 @@ CodeGenerator* OptimizingCompiler::TryCompile(ArenaAllocator* arena, compiler_driver, compilation_stats_.get(), dex_compilation_unit, - &pass_observer, - &handles); + &pass_observer); codegen->CompileOptimized(code_allocator); } else { codegen->CompileBaseline(code_allocator); diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h index 4713514bb2..6296eedfb0 100644 --- a/compiler/optimizing/optimizing_compiler_stats.h +++ b/compiler/optimizing/optimizing_compiler_stats.h @@ -38,9 +38,7 @@ enum MethodCompilationStat { kRemovedDeadInstruction, kRemovedNullCheck, kNotCompiledBranchOutsideMethodCode, - kNotCompiledNonNaturalLoop, - kNotCompiledThrowCatchLoop, - kNotCompiledAmbiguousArrayGet, + kNotCompiledCannotBuildSSA, kNotCompiledHugeMethod, kNotCompiledLargeMethodNoBranches, kNotCompiledMalformedOpcode, @@ -106,9 +104,7 @@ class OptimizingCompilerStats { case kRemovedDeadInstruction: name = "RemovedDeadInstruction"; break; case kRemovedNullCheck: name = "RemovedNullCheck"; break; case kNotCompiledBranchOutsideMethodCode: name = "NotCompiledBranchOutsideMethodCode"; break; - case kNotCompiledNonNaturalLoop : name = "NotCompiledNonNaturalLoop"; break; - case kNotCompiledThrowCatchLoop : name = "NotCompiledThrowCatchLoop"; break; - case kNotCompiledAmbiguousArrayGet : name = "NotCompiledAmbiguousArrayGet"; break; + case kNotCompiledCannotBuildSSA : name = "NotCompiledCannotBuildSSA"; break; case kNotCompiledHugeMethod : name = "NotCompiledHugeMethod"; break; case kNotCompiledLargeMethodNoBranches : name = "NotCompiledLargeMethodNoBranches"; break; case kNotCompiledMalformedOpcode : name = "NotCompiledMalformedOpcode"; break; diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h index af3a005304..350f0b14ab 100644 --- a/compiler/optimizing/optimizing_unit_test.h +++ b/compiler/optimizing/optimizing_unit_test.h @@ -19,13 +19,9 @@ #include "nodes.h" #include "builder.h" -#include "common_compiler_test.h" #include "compiler/dex/pass_manager.h" #include "dex_file.h" #include "dex_instruction.h" -#include "handle_scope-inl.h" -#include "scoped_thread_state_change.h" -#include "ssa_builder.h" #include "ssa_liveness_analysis.h" #include "gtest/gtest.h" @@ -46,6 +42,7 @@ namespace art { #define FIVE_REGISTERS_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(5, __VA_ARGS__) #define SIX_REGISTERS_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(6, __VA_ARGS__) + LiveInterval* BuildInterval(const size_t ranges[][2], size_t number_of_ranges, ArenaAllocator* allocator, @@ -114,12 +111,6 @@ inline bool IsRemoved(HInstruction* instruction) { return instruction->GetBlock() == nullptr; } -inline void TransformToSsa(HGraph* graph) { - ScopedObjectAccess soa(Thread::Current()); - StackHandleScopeCollection handles(soa.Self()); - EXPECT_EQ(graph->TryBuildingSsa(&handles), kBuildSsaSuccess); -} - } // namespace art #endif // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_ diff --git a/compiler/optimizing/pc_relative_fixups_x86.cc b/compiler/optimizing/pc_relative_fixups_x86.cc index a385448104..b383f1e1ad 100644 --- a/compiler/optimizing/pc_relative_fixups_x86.cc +++ b/compiler/optimizing/pc_relative_fixups_x86.cc @@ -15,7 +15,6 @@ */ #include "pc_relative_fixups_x86.h" -#include "code_generator_x86.h" namespace art { namespace x86 { @@ -80,10 +79,6 @@ class PCRelativeHandlerVisitor : public HGraphVisitor { } void VisitPackedSwitch(HPackedSwitch* switch_insn) OVERRIDE { - if (switch_insn->GetNumEntries() <= - InstructionCodeGeneratorX86::kPackedSwitchJumpTableThreshold) { - return; - } // We need to replace the HPackedSwitch with a HX86PackedSwitch in order to // address the constant area. InitializePCRelativeBasePointer(); diff --git a/compiler/optimizing/primitive_type_propagation.cc b/compiler/optimizing/primitive_type_propagation.cc new file mode 100644 index 0000000000..bde54ee977 --- /dev/null +++ b/compiler/optimizing/primitive_type_propagation.cc @@ -0,0 +1,133 @@ +/* + * Copyright (C) 2014 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 "primitive_type_propagation.h" + +#include "nodes.h" +#include "ssa_builder.h" + +namespace art { + +static Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_type) { + // We trust the verifier has already done the necessary checking. + switch (existing) { + case Primitive::kPrimFloat: + case Primitive::kPrimDouble: + case Primitive::kPrimNot: + return existing; + default: + // Phis are initialized with a void type, so if we are asked + // to merge with a void type, we should use the existing one. + return new_type == Primitive::kPrimVoid + ? existing + : HPhi::ToPhiType(new_type); + } +} + +// Re-compute and update the type of the instruction. Returns +// whether or not the type was changed. +bool PrimitiveTypePropagation::UpdateType(HPhi* phi) { + DCHECK(phi->IsLive()); + Primitive::Type existing = phi->GetType(); + + Primitive::Type new_type = existing; + for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { + Primitive::Type input_type = phi->InputAt(i)->GetType(); + new_type = MergeTypes(new_type, input_type); + } + phi->SetType(new_type); + + if (new_type == Primitive::kPrimDouble + || new_type == Primitive::kPrimFloat + || new_type == Primitive::kPrimNot) { + // If the phi is of floating point type, we need to update its inputs to that + // type. For inputs that are phis, we need to recompute their types. + for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { + HInstruction* input = phi->InputAt(i); + if (input->GetType() != new_type) { + HInstruction* equivalent = (new_type == Primitive::kPrimNot) + ? SsaBuilder::GetReferenceTypeEquivalent(input) + : SsaBuilder::GetFloatOrDoubleEquivalent(phi, input, new_type); + phi->ReplaceInput(equivalent, i); + if (equivalent->IsPhi()) { + AddToWorklist(equivalent->AsPhi()); + } else if (equivalent == input) { + // The input has changed its type. It can be an input of other phis, + // so we need to put phi users in the work list. + AddDependentInstructionsToWorklist(equivalent); + } + } + } + } + + return existing != new_type; +} + +void PrimitiveTypePropagation::Run() { + for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { + VisitBasicBlock(it.Current()); + } + ProcessWorklist(); +} + +void PrimitiveTypePropagation::VisitBasicBlock(HBasicBlock* block) { + if (block->IsLoopHeader()) { + for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { + HPhi* phi = it.Current()->AsPhi(); + if (phi->IsLive()) { + AddToWorklist(phi); + } + } + } else { + for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { + // Eagerly compute the type of the phi, for quicker convergence. Note + // that we don't need to add users to the worklist because we are + // doing a reverse post-order visit, therefore either the phi users are + // non-loop phi and will be visited later in the visit, or are loop-phis, + // and they are already in the work list. + HPhi* phi = it.Current()->AsPhi(); + if (phi->IsLive()) { + UpdateType(phi); + } + } + } +} + +void PrimitiveTypePropagation::ProcessWorklist() { + while (!worklist_.empty()) { + HPhi* instruction = worklist_.back(); + worklist_.pop_back(); + if (UpdateType(instruction)) { + AddDependentInstructionsToWorklist(instruction); + } + } +} + +void PrimitiveTypePropagation::AddToWorklist(HPhi* instruction) { + DCHECK(instruction->IsLive()); + worklist_.push_back(instruction); +} + +void PrimitiveTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) { + for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { + HPhi* phi = it.Current()->GetUser()->AsPhi(); + if (phi != nullptr && phi->IsLive() && phi->GetType() != instruction->GetType()) { + AddToWorklist(phi); + } + } +} + +} // namespace art diff --git a/compiler/optimizing/primitive_type_propagation.h b/compiler/optimizing/primitive_type_propagation.h new file mode 100644 index 0000000000..212fcfc69f --- /dev/null +++ b/compiler/optimizing/primitive_type_propagation.h @@ -0,0 +1,52 @@ +/* + * Copyright (C) 2014 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. + */ + +#ifndef ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_ +#define ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_ + +#include "base/arena_containers.h" +#include "nodes.h" + +namespace art { + +// Compute and propagate primitive types of phis in the graph. +class PrimitiveTypePropagation : public ValueObject { + public: + explicit PrimitiveTypePropagation(HGraph* graph) + : graph_(graph), worklist_(graph->GetArena()->Adapter(kArenaAllocPrimitiveTypePropagation)) { + worklist_.reserve(kDefaultWorklistSize); + } + + void Run(); + + private: + void VisitBasicBlock(HBasicBlock* block); + void ProcessWorklist(); + void AddToWorklist(HPhi* phi); + void AddDependentInstructionsToWorklist(HInstruction* instruction); + bool UpdateType(HPhi* phi); + + HGraph* const graph_; + ArenaVector<HPhi*> worklist_; + + static constexpr size_t kDefaultWorklistSize = 8; + + DISALLOW_COPY_AND_ASSIGN(PrimitiveTypePropagation); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_ diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc index 94a297c9e6..fea903d9cf 100644 --- a/compiler/optimizing/reference_type_propagation.cc +++ b/compiler/optimizing/reference_type_propagation.cc @@ -40,6 +40,7 @@ class RTPVisitor : public HGraphDelegateVisitor { throwable_class_handle_(throwable_class_handle), worklist_(worklist) {} + void VisitNullConstant(HNullConstant* null_constant) OVERRIDE; void VisitNewInstance(HNewInstance* new_instance) OVERRIDE; void VisitLoadClass(HLoadClass* load_class) OVERRIDE; void VisitClinitCheck(HClinitCheck* clinit_check) OVERRIDE; @@ -70,6 +71,8 @@ class RTPVisitor : public HGraphDelegateVisitor { ReferenceTypeInfo::TypeHandle string_class_handle_; ReferenceTypeInfo::TypeHandle throwable_class_handle_; ArenaVector<HInstruction*>* worklist_; + + static constexpr size_t kDefaultWorklistSize = 8; }; ReferenceTypePropagation::ReferenceTypePropagation(HGraph* graph, @@ -168,13 +171,9 @@ 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); + HInstruction* instr = it.Current(); + if (instr->GetType() == Primitive::kPrimNot && !instr->GetReferenceTypeInfo().IsValid()) { + fn(instr); } } for (HInstructionIterator it(block_it.Current()->GetInstructions()); !it.Done(); it.Advance()) { @@ -377,75 +376,6 @@ void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) { } } -// Returns true if one of the patterns below has been recognized. If so, the -// InstanceOf instruction together with the true branch of `ifInstruction` will -// be returned using the out parameters. -// Recognized patterns: -// (1) patterns equivalent to `if (obj instanceof X)` -// (a) InstanceOf -> Equal to 1 -> If -// (b) InstanceOf -> NotEqual to 0 -> If -// (c) InstanceOf -> If -// (2) patterns equivalent to `if (!(obj instanceof X))` -// (a) InstanceOf -> Equal to 0 -> If -// (b) InstanceOf -> NotEqual to 1 -> If -// (c) InstanceOf -> BooleanNot -> If -static bool MatchIfInstanceOf(HIf* ifInstruction, - /* out */ HInstanceOf** instanceOf, - /* out */ HBasicBlock** trueBranch) { - HInstruction* input = ifInstruction->InputAt(0); - - if (input->IsEqual()) { - HInstruction* rhs = input->AsEqual()->GetConstantRight(); - if (rhs != nullptr) { - HInstruction* lhs = input->AsEqual()->GetLeastConstantLeft(); - if (lhs->IsInstanceOf() && rhs->IsIntConstant()) { - if (rhs->AsIntConstant()->IsOne()) { - // Case (1a) - *trueBranch = ifInstruction->IfTrueSuccessor(); - } else { - // Case (2a) - DCHECK(rhs->AsIntConstant()->IsZero()); - *trueBranch = ifInstruction->IfFalseSuccessor(); - } - *instanceOf = lhs->AsInstanceOf(); - return true; - } - } - } else if (input->IsNotEqual()) { - HInstruction* rhs = input->AsNotEqual()->GetConstantRight(); - if (rhs != nullptr) { - HInstruction* lhs = input->AsNotEqual()->GetLeastConstantLeft(); - if (lhs->IsInstanceOf() && rhs->IsIntConstant()) { - if (rhs->AsIntConstant()->IsZero()) { - // Case (1b) - *trueBranch = ifInstruction->IfTrueSuccessor(); - } else { - // Case (2b) - DCHECK(rhs->AsIntConstant()->IsOne()); - *trueBranch = ifInstruction->IfFalseSuccessor(); - } - *instanceOf = lhs->AsInstanceOf(); - return true; - } - } - } else if (input->IsInstanceOf()) { - // Case (1c) - *instanceOf = input->AsInstanceOf(); - *trueBranch = ifInstruction->IfTrueSuccessor(); - return true; - } else if (input->IsBooleanNot()) { - HInstruction* not_input = input->InputAt(0); - if (not_input->IsInstanceOf()) { - // Case (2c) - *instanceOf = not_input->AsInstanceOf(); - *trueBranch = ifInstruction->IfFalseSuccessor(); - return true; - } - } - - return false; -} - // Detects if `block` is the True block for the pattern // `if (x instanceof ClassX) { }` // If that's the case insert an HBoundType instruction to bound the type of `x` @@ -455,11 +385,22 @@ void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) { if (ifInstruction == nullptr) { return; } - - // Try to recognize common `if (instanceof)` and `if (!instanceof)` patterns. - HInstanceOf* instanceOf = nullptr; + HInstruction* ifInput = ifInstruction->InputAt(0); + HInstruction* instanceOf = nullptr; HBasicBlock* instanceOfTrueBlock = nullptr; - if (!MatchIfInstanceOf(ifInstruction, &instanceOf, &instanceOfTrueBlock)) { + + // The instruction simplifier has transformed: + // - `if (a instanceof A)` into an HIf with an HInstanceOf input + // - `if (!(a instanceof A)` into an HIf with an HBooleanNot input (which in turn + // has an HInstanceOf input) + // So we should not see the usual HEqual here. + if (ifInput->IsInstanceOf()) { + instanceOf = ifInput; + instanceOfTrueBlock = ifInstruction->IfTrueSuccessor(); + } else if (ifInput->IsBooleanNot() && ifInput->InputAt(0)->IsInstanceOf()) { + instanceOf = ifInput->InputAt(0); + instanceOfTrueBlock = ifInstruction->IfFalseSuccessor(); + } else { return; } @@ -564,6 +505,13 @@ void RTPVisitor::UpdateReferenceTypeInfo(HInstruction* instr, SetClassAsTypeInfo(instr, dex_cache->GetResolvedType(type_idx), is_exact); } +void RTPVisitor::VisitNullConstant(HNullConstant* instr) { + // TODO: The null constant could be bound contextually (e.g. based on return statements) + // to a more precise type. + instr->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(object_class_handle_, /* is_exact */ false)); +} + void RTPVisitor::VisitNewInstance(HNewInstance* instr) { UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true); } @@ -575,11 +523,7 @@ void RTPVisitor::VisitNewArray(HNewArray* instr) { static mirror::Class* GetClassFromDexCache(Thread* self, const DexFile& dex_file, uint16_t type_idx) SHARED_REQUIRES(Locks::mutator_lock_) { mirror::DexCache* dex_cache = - Runtime::Current()->GetClassLinker()->FindDexCache(self, dex_file, /* allow_failure */ true); - if (dex_cache == nullptr) { - // Dex cache could not be found. This should only happen during gtests. - return nullptr; - } + Runtime::Current()->GetClassLinker()->FindDexCache(self, dex_file, false); // Get type from dex cache assuming it was populated by the verifier. return dex_cache->GetResolvedType(type_idx); } @@ -596,24 +540,17 @@ void RTPVisitor::VisitParameterValue(HParameterValue* instr) { void RTPVisitor::UpdateFieldAccessTypeInfo(HInstruction* instr, const FieldInfo& info) { - if (instr->GetType() != Primitive::kPrimNot) { + // The field index is unknown only during tests. + if (instr->GetType() != Primitive::kPrimNot || info.GetFieldIndex() == kUnknownFieldIndex) { return; } ScopedObjectAccess soa(Thread::Current()); - mirror::Class* klass = nullptr; - - // The field index is unknown only during tests. - if (info.GetFieldIndex() != kUnknownFieldIndex) { - ClassLinker* cl = Runtime::Current()->GetClassLinker(); - ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), info.GetDexCache().Get()); - // TODO: There are certain cases where we can't resolve the field. - // b/21914925 is open to keep track of a repro case for this issue. - if (field != nullptr) { - klass = field->GetType<false>(); - } - } - + ClassLinker* cl = Runtime::Current()->GetClassLinker(); + ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), info.GetDexCache().Get()); + // TODO: There are certain cases where we can't resolve the field. + // b/21914925 is open to keep track of a repro case for this issue. + mirror::Class* klass = (field == nullptr) ? nullptr : field->GetType<false>(); SetClassAsTypeInfo(instr, klass, /* is_exact */ false); } @@ -729,7 +666,7 @@ void RTPVisitor::VisitCheckCast(HCheckCast* check_cast) { } void ReferenceTypePropagation::VisitPhi(HPhi* phi) { - if (phi->IsDead() || phi->GetType() != Primitive::kPrimNot) { + if (phi->GetType() != Primitive::kPrimNot) { return; } @@ -887,8 +824,6 @@ void ReferenceTypePropagation::UpdateBoundType(HBoundType* instr) { // NullConstant inputs are ignored during merging as they do not provide any useful information. // If all the inputs are NullConstants then the type of the phi will be set to Object. void ReferenceTypePropagation::UpdatePhi(HPhi* instr) { - DCHECK(instr->IsLive()); - size_t input_count = instr->InputCount(); size_t first_input_index_not_null = 0; while (first_input_index_not_null < input_count && @@ -933,7 +868,7 @@ void ReferenceTypePropagation::UpdatePhi(HPhi* instr) { // Re-computes and updates the nullability of the instruction. Returns whether or // not the nullability was changed. bool ReferenceTypePropagation::UpdateNullability(HInstruction* instr) { - DCHECK((instr->IsPhi() && instr->AsPhi()->IsLive()) + DCHECK(instr->IsPhi() || instr->IsBoundType() || instr->IsNullCheck() || instr->IsArrayGet()); @@ -981,7 +916,7 @@ void ReferenceTypePropagation::AddToWorklist(HInstruction* instruction) { void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) { for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { HInstruction* user = it.Current()->GetUser(); - if ((user->IsPhi() && user->AsPhi()->IsLive()) + if (user->IsPhi() || user->IsBoundType() || user->IsNullCheck() || (user->IsArrayGet() && (user->GetType() == Primitive::kPrimNot))) { diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc index b900ed0966..080f970756 100644 --- a/compiler/optimizing/register_allocator_test.cc +++ b/compiler/optimizing/register_allocator_test.cc @@ -28,13 +28,13 @@ #include "ssa_liveness_analysis.h" #include "ssa_phi_elimination.h" +#include "gtest/gtest.h" + namespace art { // Note: the register allocator tests rely on the fact that constants have live // intervals and registers get allocated to them. -class RegisterAllocatorTest : public CommonCompilerTest {}; - static bool Check(const uint16_t* data) { ArenaPool pool; ArenaAllocator allocator(&pool); @@ -42,7 +42,7 @@ static bool Check(const uint16_t* data) { HGraphBuilder builder(graph); const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); builder.BuildGraph(*item); - TransformToSsa(graph); + graph->TryBuildingSsa(); std::unique_ptr<const X86InstructionSetFeatures> features_x86( X86InstructionSetFeatures::FromCppDefines()); x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); @@ -57,7 +57,7 @@ static bool Check(const uint16_t* data) { * Unit testing of RegisterAllocator::ValidateIntervals. Register allocator * tests are based on this validation method. */ -TEST_F(RegisterAllocatorTest, ValidateIntervals) { +TEST(RegisterAllocatorTest, ValidateIntervals) { ArenaPool pool; ArenaAllocator allocator(&pool); HGraph* graph = CreateGraph(&allocator); @@ -146,7 +146,7 @@ TEST_F(RegisterAllocatorTest, ValidateIntervals) { } } -TEST_F(RegisterAllocatorTest, CFG1) { +TEST(RegisterAllocatorTest, CFG1) { /* * Test the following snippet: * return 0; @@ -166,7 +166,7 @@ TEST_F(RegisterAllocatorTest, CFG1) { ASSERT_TRUE(Check(data)); } -TEST_F(RegisterAllocatorTest, Loop1) { +TEST(RegisterAllocatorTest, Loop1) { /* * Test the following snippet: * int a = 0; @@ -205,7 +205,7 @@ TEST_F(RegisterAllocatorTest, Loop1) { ASSERT_TRUE(Check(data)); } -TEST_F(RegisterAllocatorTest, Loop2) { +TEST(RegisterAllocatorTest, Loop2) { /* * Test the following snippet: * int a = 0; @@ -259,11 +259,11 @@ static HGraph* BuildSSAGraph(const uint16_t* data, ArenaAllocator* allocator) { HGraphBuilder builder(graph); const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); builder.BuildGraph(*item); - TransformToSsa(graph); + graph->TryBuildingSsa(); return graph; } -TEST_F(RegisterAllocatorTest, Loop3) { +TEST(RegisterAllocatorTest, Loop3) { /* * Test the following snippet: * int a = 0 @@ -326,7 +326,7 @@ TEST_F(RegisterAllocatorTest, Loop3) { ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister()); } -TEST_F(RegisterAllocatorTest, FirstRegisterUse) { +TEST(RegisterAllocatorTest, FirstRegisterUse) { const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 | 0, Instruction::XOR_INT_LIT8 | 1 << 8, 1 << 8, @@ -366,7 +366,7 @@ TEST_F(RegisterAllocatorTest, FirstRegisterUse) { ASSERT_EQ(new_interval->FirstRegisterUse(), last_xor->GetLifetimePosition()); } -TEST_F(RegisterAllocatorTest, DeadPhi) { +TEST(RegisterAllocatorTest, DeadPhi) { /* Test for a dead loop phi taking as back-edge input a phi that also has * this loop phi as input. Walking backwards in SsaDeadPhiElimination * does not solve the problem because the loop phi will be visited last. @@ -407,7 +407,7 @@ TEST_F(RegisterAllocatorTest, DeadPhi) { * that share the same register. It should split the interval it is currently * allocating for at the minimum lifetime position between the two inactive intervals. */ -TEST_F(RegisterAllocatorTest, FreeUntil) { +TEST(RegisterAllocatorTest, FreeUntil) { const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 | 0, Instruction::RETURN); @@ -539,7 +539,7 @@ static HGraph* BuildIfElseWithPhi(ArenaAllocator* allocator, return graph; } -TEST_F(RegisterAllocatorTest, PhiHint) { +TEST(RegisterAllocatorTest, PhiHint) { ArenaPool pool; ArenaAllocator allocator(&pool); HPhi *phi; @@ -658,7 +658,7 @@ static HGraph* BuildFieldReturn(ArenaAllocator* allocator, return graph; } -TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint) { +TEST(RegisterAllocatorTest, ExpectedInRegisterHint) { ArenaPool pool; ArenaAllocator allocator(&pool); HInstruction *field, *ret; @@ -726,7 +726,7 @@ static HGraph* BuildTwoSubs(ArenaAllocator* allocator, return graph; } -TEST_F(RegisterAllocatorTest, SameAsFirstInputHint) { +TEST(RegisterAllocatorTest, SameAsFirstInputHint) { ArenaPool pool; ArenaAllocator allocator(&pool); HInstruction *first_sub, *second_sub; @@ -795,7 +795,7 @@ static HGraph* BuildDiv(ArenaAllocator* allocator, return graph; } -TEST_F(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) { +TEST(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) { ArenaPool pool; ArenaAllocator allocator(&pool); HInstruction *div; @@ -819,7 +819,7 @@ TEST_F(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) { // Test a bug in the register allocator, where allocating a blocked // register would lead to spilling an inactive interval at the wrong // position. -TEST_F(RegisterAllocatorTest, SpillInactive) { +TEST(RegisterAllocatorTest, SpillInactive) { ArenaPool pool; // Create a synthesized graph to please the register_allocator and diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc index 9e869e18e9..9e6cfbe653 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -17,11 +17,214 @@ #include "ssa_builder.h" #include "nodes.h" -#include "reference_type_propagation.h" +#include "primitive_type_propagation.h" #include "ssa_phi_elimination.h" namespace art { +// Returns whether this is a loop header phi which was eagerly created but later +// found inconsistent due to the vreg being undefined in one of its predecessors. +// Such phi is marked dead and should be ignored until its removal in SsaPhiElimination. +static bool IsUndefinedLoopHeaderPhi(HPhi* phi) { + return phi->IsLoopHeaderPhi() && phi->InputCount() != phi->GetBlock()->GetPredecessors().size(); +} + +/** + * A debuggable application may require to reviving phis, to ensure their + * associated DEX register is available to a debugger. This class implements + * the logic for statement (c) of the SsaBuilder (see ssa_builder.h). It + * also makes sure that phis with incompatible input types are not revived + * (statement (b) of the SsaBuilder). + * + * This phase must be run after detecting dead phis through the + * DeadPhiElimination phase, and before deleting the dead phis. + */ +class DeadPhiHandling : public ValueObject { + public: + explicit DeadPhiHandling(HGraph* graph) + : graph_(graph), worklist_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) { + worklist_.reserve(kDefaultWorklistSize); + } + + void Run(); + + private: + void VisitBasicBlock(HBasicBlock* block); + void ProcessWorklist(); + void AddToWorklist(HPhi* phi); + void AddDependentInstructionsToWorklist(HPhi* phi); + bool UpdateType(HPhi* phi); + + HGraph* const graph_; + ArenaVector<HPhi*> worklist_; + + static constexpr size_t kDefaultWorklistSize = 8; + + DISALLOW_COPY_AND_ASSIGN(DeadPhiHandling); +}; + +static bool HasConflictingEquivalent(HPhi* phi) { + if (phi->GetNext() == nullptr) { + return false; + } + HPhi* next = phi->GetNext()->AsPhi(); + if (next->GetRegNumber() == phi->GetRegNumber()) { + if (next->GetType() == Primitive::kPrimVoid) { + // We only get a void type for an equivalent phi we processed and found out + // it was conflicting. + return true; + } else { + // Go to the next phi, in case it is also an equivalent. + return HasConflictingEquivalent(next); + } + } + return false; +} + +bool DeadPhiHandling::UpdateType(HPhi* phi) { + if (phi->IsDead()) { + // Phi was rendered dead while waiting in the worklist because it was replaced + // with an equivalent. + return false; + } + + Primitive::Type existing = phi->GetType(); + + bool conflict = false; + Primitive::Type new_type = existing; + for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { + HInstruction* input = phi->InputAt(i); + if (input->IsPhi() && input->AsPhi()->IsDead()) { + // We are doing a reverse post order visit of the graph, reviving + // phis that have environment uses and updating their types. If an + // input is a phi, and it is dead (because its input types are + // conflicting), this phi must be marked dead as well. + conflict = true; + break; + } + Primitive::Type input_type = HPhi::ToPhiType(input->GetType()); + + // The only acceptable transitions are: + // - From void to typed: first time we update the type of this phi. + // - From int to reference (or reference to int): the phi has to change + // to reference type. If the integer input cannot be converted to a + // reference input, the phi will remain dead. + if (new_type == Primitive::kPrimVoid) { + new_type = input_type; + } else if (new_type == Primitive::kPrimNot && input_type == Primitive::kPrimInt) { + if (input->IsPhi() && HasConflictingEquivalent(input->AsPhi())) { + // If we already asked for an equivalent of the input phi, but that equivalent + // ended up conflicting, make this phi conflicting too. + conflict = true; + break; + } + HInstruction* equivalent = SsaBuilder::GetReferenceTypeEquivalent(input); + if (equivalent == nullptr) { + conflict = true; + break; + } + phi->ReplaceInput(equivalent, i); + if (equivalent->IsPhi()) { + DCHECK_EQ(equivalent->GetType(), Primitive::kPrimNot); + // We created a new phi, but that phi has the same inputs as the old phi. We + // add it to the worklist to ensure its inputs can also be converted to reference. + // If not, it will remain dead, and the algorithm will make the current phi dead + // as well. + equivalent->AsPhi()->SetLive(); + AddToWorklist(equivalent->AsPhi()); + } + } else if (new_type == Primitive::kPrimInt && input_type == Primitive::kPrimNot) { + new_type = Primitive::kPrimNot; + // Start over, we may request reference equivalents for the inputs of the phi. + i = -1; + } else if (new_type != input_type) { + conflict = true; + break; + } + } + + if (conflict) { + phi->SetType(Primitive::kPrimVoid); + phi->SetDead(); + return true; + } else if (existing == new_type) { + return false; + } + + DCHECK(phi->IsLive()); + phi->SetType(new_type); + + // There might exist a `new_type` equivalent of `phi` already. In that case, + // we replace the equivalent with the, now live, `phi`. + HPhi* equivalent = phi->GetNextEquivalentPhiWithSameType(); + if (equivalent != nullptr) { + // There cannot be more than two equivalents with the same type. + DCHECK(equivalent->GetNextEquivalentPhiWithSameType() == nullptr); + // If doing fix-point iteration, the equivalent might be in `worklist_`. + // Setting it dead will make UpdateType skip it. + equivalent->SetDead(); + equivalent->ReplaceWith(phi); + } + + return true; +} + +void DeadPhiHandling::VisitBasicBlock(HBasicBlock* block) { + for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { + HPhi* phi = it.Current()->AsPhi(); + if (IsUndefinedLoopHeaderPhi(phi)) { + DCHECK(phi->IsDead()); + continue; + } + if (phi->IsDead() && phi->HasEnvironmentUses()) { + phi->SetLive(); + if (block->IsLoopHeader()) { + // Loop phis must have a type to guarantee convergence of the algorithm. + DCHECK_NE(phi->GetType(), Primitive::kPrimVoid); + AddToWorklist(phi); + } else { + // Because we are doing a reverse post order visit, all inputs of + // this phi have been visited and therefore had their (initial) type set. + UpdateType(phi); + } + } + } +} + +void DeadPhiHandling::ProcessWorklist() { + while (!worklist_.empty()) { + HPhi* instruction = worklist_.back(); + worklist_.pop_back(); + // Note that the same equivalent phi can be added multiple times in the work list, if + // used by multiple phis. The first call to `UpdateType` will know whether the phi is + // dead or live. + if (instruction->IsLive() && UpdateType(instruction)) { + AddDependentInstructionsToWorklist(instruction); + } + } +} + +void DeadPhiHandling::AddToWorklist(HPhi* instruction) { + DCHECK(instruction->IsLive()); + worklist_.push_back(instruction); +} + +void DeadPhiHandling::AddDependentInstructionsToWorklist(HPhi* instruction) { + for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { + HPhi* phi = it.Current()->GetUser()->AsPhi(); + if (phi != nullptr && !phi->IsDead()) { + AddToWorklist(phi); + } + } +} + +void DeadPhiHandling::Run() { + for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { + VisitBasicBlock(it.Current()); + } + ProcessWorklist(); +} + void SsaBuilder::SetLoopHeaderPhiInputs() { for (size_t i = loop_headers_.size(); i > 0; --i) { HBasicBlock* block = loop_headers_[i - 1]; @@ -82,11 +285,10 @@ void SsaBuilder::EquivalentPhisCleanup() { HPhi* phi = it.Current()->AsPhi(); HPhi* next = phi->GetNextEquivalentPhiWithSameType(); if (next != nullptr) { - // Make sure we do not replace a live phi with a dead phi. A live phi - // has been handled by the type propagation phase, unlike a dead phi. + // Make sure we do not replace a live phi with a dead phi. A live phi has been + // handled by the type propagation phase, unlike a dead phi. if (next->IsLive()) { phi->ReplaceWith(next); - phi->SetDead(); } else { next->ReplaceWith(phi); } @@ -98,7 +300,64 @@ void SsaBuilder::EquivalentPhisCleanup() { } } -void SsaBuilder::FixEnvironmentPhis() { +void SsaBuilder::BuildSsa() { + // 1) Visit in reverse post order. We need to have all predecessors of a block visited + // (with the exception of loops) in order to create the right environment for that + // block. For loops, we create phis whose inputs will be set in 2). + for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { + VisitBasicBlock(it.Current()); + } + + // 2) Set inputs of loop phis. + SetLoopHeaderPhiInputs(); + + // 3) Mark dead phis. This will mark phis that are only used by environments: + // at the DEX level, the type of these phis does not need to be consistent, but + // our code generator will complain if the inputs of a phi do not have the same + // type. The marking allows the type propagation to know which phis it needs + // to handle. We mark but do not eliminate: the elimination will be done in + // step 9). + SsaDeadPhiElimination dead_phis_for_type_propagation(GetGraph()); + dead_phis_for_type_propagation.MarkDeadPhis(); + + // 4) Propagate types of phis. At this point, phis are typed void in the general + // case, or float/double/reference when we created an equivalent phi. So we + // need to propagate the types across phis to give them a correct type. + PrimitiveTypePropagation type_propagation(GetGraph()); + type_propagation.Run(); + + // 5) When creating equivalent phis we copy the inputs of the original phi which + // may be improperly typed. This was fixed during the type propagation in 4) but + // as a result we may end up with two equivalent phis with the same type for + // the same dex register. This pass cleans them up. + EquivalentPhisCleanup(); + + // 6) Mark dead phis again. Step 4) may have introduced new phis. + // Step 5) might enable the death of new phis. + SsaDeadPhiElimination dead_phis(GetGraph()); + dead_phis.MarkDeadPhis(); + + // 7) Now that the graph is correctly typed, we can get rid of redundant phis. + // Note that we cannot do this phase before type propagation, otherwise + // we could get rid of phi equivalents, whose presence is a requirement for the + // type propagation phase. Note that this is to satisfy statement (a) of the + // SsaBuilder (see ssa_builder.h). + SsaRedundantPhiElimination redundant_phi(GetGraph()); + redundant_phi.Run(); + + // 8) Fix the type for null constants which are part of an equality comparison. + // We need to do this after redundant phi elimination, to ensure the only cases + // that we can see are reference comparison against 0. The redundant phi + // elimination ensures we do not see a phi taking two 0 constants in a HEqual + // or HNotEqual. + FixNullConstantType(); + + // 9) Make sure environments use the right phi "equivalent": a phi marked dead + // can have a phi equivalent that is not dead. We must therefore update + // all environment uses of the dead phi to use its equivalent. Note that there + // can be multiple phis for the same Dex register that are live (for example + // when merging constants), in which case it is OK for the environments + // to just reference one. for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) { @@ -119,345 +378,24 @@ void SsaBuilder::FixEnvironmentPhis() { phi->ReplaceWith(next); } } -} -static void AddDependentInstructionsToWorklist(HInstruction* instruction, - ArenaVector<HPhi*>* worklist) { - // If `instruction` is a dead phi, type conflict was just identified. All its - // live phi users, and transitively users of those users, therefore need to be - // marked dead/conflicting too, so we add them to the worklist. Otherwise we - // add users whose type does not match and needs to be updated. - bool add_all_live_phis = instruction->IsPhi() && instruction->AsPhi()->IsDead(); - for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { - HInstruction* user = it.Current()->GetUser(); - if (user->IsPhi() && user->AsPhi()->IsLive()) { - if (add_all_live_phis || user->GetType() != instruction->GetType()) { - worklist->push_back(user->AsPhi()); - } - } + // 10) Deal with phis to guarantee liveness of phis in case of a debuggable + // application. This is for satisfying statement (c) of the SsaBuilder + // (see ssa_builder.h). + if (GetGraph()->IsDebuggable()) { + DeadPhiHandling dead_phi_handler(GetGraph()); + dead_phi_handler.Run(); } -} - -// Find a candidate primitive type for `phi` by merging the type of its inputs. -// Return false if conflict is identified. -static bool TypePhiFromInputs(HPhi* phi) { - Primitive::Type common_type = phi->GetType(); - for (HInputIterator it(phi); !it.Done(); it.Advance()) { - HInstruction* input = it.Current(); - if (input->IsPhi() && input->AsPhi()->IsDead()) { - // Phis are constructed live so if an input is a dead phi, it must have - // been made dead due to type conflict. Mark this phi conflicting too. - return false; - } - - 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)) { - // Types are of different sizes, e.g. int vs. long. Must be a conflict. - return false; - } else if (Primitive::IsIntegralType(common_type)) { - // Previous inputs were integral, this one is not but is of the same size. - // This does not imply conflict since some bytecode instruction types are - // ambiguous. TypeInputsOfPhi will either type them or detect a conflict. - DCHECK(Primitive::IsFloatingPointType(input_type) || input_type == Primitive::kPrimNot); - common_type = input_type; - } else if (Primitive::IsIntegralType(input_type)) { - // Input is integral, common type is not. Same as in the previous case, if - // there is a conflict, it will be detected during TypeInputsOfPhi. - DCHECK(Primitive::IsFloatingPointType(common_type) || common_type == Primitive::kPrimNot); - } else { - // Combining float and reference types. Clearly a conflict. - DCHECK((common_type == Primitive::kPrimFloat && input_type == Primitive::kPrimNot) || - (common_type == Primitive::kPrimNot && input_type == Primitive::kPrimFloat)); - return false; - } - } - - // We have found a candidate type for the phi. Set it and return true. We may - // still discover conflict whilst typing the individual inputs in TypeInputsOfPhi. - phi->SetType(common_type); - return true; -} - -// Replace inputs of `phi` to match its type. Return false if conflict is identified. -bool SsaBuilder::TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist) { - Primitive::Type common_type = phi->GetType(); - if (common_type == Primitive::kPrimVoid || Primitive::IsIntegralType(common_type)) { - // Phi either contains only other untyped phis (common_type == kPrimVoid), - // or `common_type` is integral and we do not need to retype ambiguous inputs - // because they are always constructed with the integral type candidate. - if (kIsDebugBuild) { - for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { - HInstruction* input = phi->InputAt(i); - if (common_type == Primitive::kPrimVoid) { - DCHECK(input->IsPhi() && input->GetType() == Primitive::kPrimVoid); - } else { - DCHECK((input->IsPhi() && input->GetType() == Primitive::kPrimVoid) || - HPhi::ToPhiType(input->GetType()) == common_type); - } - } - } - // Inputs did not need to be replaced, hence no conflict. Report success. - return true; - } else { - DCHECK(common_type == Primitive::kPrimNot || Primitive::IsFloatingPointType(common_type)); - for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { - HInstruction* input = phi->InputAt(i); - if (input->GetType() != common_type) { - // Input type does not match phi's type. Try to retype the input or - // generate a suitably typed equivalent. - HInstruction* equivalent = (common_type == Primitive::kPrimNot) - ? GetReferenceTypeEquivalent(input) - : GetFloatOrDoubleEquivalent(input, common_type); - if (equivalent == nullptr) { - // Input could not be typed. Report conflict. - return false; - } - // Make sure the input did not change its type and we do not need to - // update its users. - DCHECK_NE(input, equivalent); - - phi->ReplaceInput(equivalent, i); - if (equivalent->IsPhi()) { - worklist->push_back(equivalent->AsPhi()); - } - } - } - // All inputs either matched the type of the phi or we successfully replaced - // them with a suitable equivalent. Report success. - return true; - } -} - -// Attempt to set the primitive type of `phi` to match its inputs. Return whether -// it was changed by the algorithm or not. -bool SsaBuilder::UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist) { - DCHECK(phi->IsLive()); - Primitive::Type original_type = phi->GetType(); - - // Try to type the phi in two stages: - // (1) find a candidate type for the phi by merging types of all its inputs, - // (2) try to type the phi's inputs to that candidate type. - // Either of these stages may detect a type conflict and fail, in which case - // we immediately abort. - if (!TypePhiFromInputs(phi) || !TypeInputsOfPhi(phi, worklist)) { - // Conflict detected. Mark the phi dead and return true because it changed. - phi->SetDead(); - return true; - } - - // Return true if the type of the phi has changed. - return phi->GetType() != original_type; -} - -void SsaBuilder::RunPrimitiveTypePropagation() { - ArenaVector<HPhi*> worklist(GetGraph()->GetArena()->Adapter()); - - for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); - if (block->IsLoopHeader()) { - for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { - HPhi* phi = phi_it.Current()->AsPhi(); - if (phi->IsLive()) { - worklist.push_back(phi); - } - } - } else { - for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { - // Eagerly compute the type of the phi, for quicker convergence. Note - // that we don't need to add users to the worklist because we are - // doing a reverse post-order visit, therefore either the phi users are - // non-loop phi and will be visited later in the visit, or are loop-phis, - // and they are already in the work list. - HPhi* phi = phi_it.Current()->AsPhi(); - if (phi->IsLive()) { - UpdatePrimitiveType(phi, &worklist); - } - } - } - } - - ProcessPrimitiveTypePropagationWorklist(&worklist); - EquivalentPhisCleanup(); -} - -void SsaBuilder::ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* worklist) { - // Process worklist - while (!worklist->empty()) { - HPhi* phi = worklist->back(); - worklist->pop_back(); - // The phi could have been made dead as a result of conflicts while in the - // worklist. If it is now dead, there is no point in updating its type. - if (phi->IsLive() && UpdatePrimitiveType(phi, worklist)) { - AddDependentInstructionsToWorklist(phi, worklist); - } - } -} - -static HArrayGet* FindFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { - Primitive::Type type = aget->GetType(); - DCHECK(Primitive::IsIntOrLongType(type)); - HArrayGet* next = aget->GetNext()->AsArrayGet(); - return (next != nullptr && next->IsEquivalentOf(aget)) ? next : nullptr; -} - -static HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { - Primitive::Type type = aget->GetType(); - DCHECK(Primitive::IsIntOrLongType(type)); - DCHECK(FindFloatOrDoubleEquivalentOfArrayGet(aget) == nullptr); - - HArrayGet* equivalent = new (aget->GetBlock()->GetGraph()->GetArena()) HArrayGet( - aget->GetArray(), - aget->GetIndex(), - type == Primitive::kPrimInt ? Primitive::kPrimFloat : Primitive::kPrimDouble, - aget->GetDexPc()); - aget->GetBlock()->InsertInstructionAfter(equivalent, 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(); - 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; -} - -bool SsaBuilder::FixAmbiguousArrayGets() { - if (ambiguous_agets_.empty()) { - return true; - } - - // The wrong ArrayGet equivalent may still have Phi uses coming from ArraySet - // uses (because they are untyped) and environment uses (if --debuggable). - // After resolving all ambiguous ArrayGets, we will re-run primitive type - // propagation on the Phis which need to be updated. - ArenaVector<HPhi*> worklist(GetGraph()->GetArena()->Adapter()); - - { - ScopedObjectAccess soa(Thread::Current()); - - for (HArrayGet* aget_int : ambiguous_agets_) { - if (!aget_int->GetArray()->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { - // RTP did not type the input array. Bail. - return false; - } - - HArrayGet* aget_float = FindFloatOrDoubleEquivalentOfArrayGet(aget_int); - if (IsArrayGetOnIntegralArray(aget_int)) { - if (aget_float != nullptr) { - // There is a float/double equivalent. We must replace it and re-run - // primitive type propagation on all dependent instructions. - aget_float->ReplaceWith(aget_int); - aget_float->GetBlock()->RemoveInstruction(aget_float); - AddDependentInstructionsToWorklist(aget_int, &worklist); - } - } else { - 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. - aget_float = CreateFloatOrDoubleEquivalentOfArrayGet(aget_int); - } - // Replace the original int/long instruction. Note that it may have phi - // uses, environment uses, as well as real uses (from untyped ArraySets). - // We need to re-run primitive type propagation on its dependent instructions. - aget_int->ReplaceWith(aget_float); - aget_int->GetBlock()->RemoveInstruction(aget_int); - 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; - - if (!worklist.empty()) { - ProcessPrimitiveTypePropagationWorklist(&worklist); - EquivalentPhisCleanup(); - } - - return true; -} - -BuildSsaResult SsaBuilder::BuildSsa() { - // 1) Visit in reverse post order. We need to have all predecessors of a block - // visited (with the exception of loops) in order to create the right environment - // for that block. For loops, we create phis whose inputs will be set in 2). - for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { - VisitBasicBlock(it.Current()); - } - - // 2) Set inputs of loop header phis. - SetLoopHeaderPhiInputs(); - - // 3) Propagate types of phis. At this point, phis are typed void in the general - // case, or float/double/reference if we created an equivalent phi. So we need - // to propagate the types across phis to give them a correct type. If a type - // conflict is detected in this stage, the phi is marked dead. - RunPrimitiveTypePropagation(); - - // 4) Now that the correct primitive types have been assigned, we can get rid - // of redundant phis. Note that we cannot do this phase before type propagation, - // otherwise we could get rid of phi equivalents, whose presence is a requirement - // for the type propagation phase. Note that this is to satisfy statement (a) - // of the SsaBuilder (see ssa_builder.h). - SsaRedundantPhiElimination(GetGraph()).Run(); - - // 5) Fix the type for null constants which are part of an equality comparison. - // We need to do this after redundant phi elimination, to ensure the only cases - // that we can see are reference comparison against 0. The redundant phi - // elimination ensures we do not see a phi taking two 0 constants in a HEqual - // or HNotEqual. - FixNullConstantType(); - - // 6) Compute type of reference type instructions. The pass assumes that - // NullConstant has been fixed up. - 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; - } - - // 8) Mark dead phis. This will mark phis which are not used by instructions - // or other live phis. If compiling as debuggable code, phis will also be kept - // live if they have an environment use. - SsaDeadPhiElimination dead_phi_elimimation(GetGraph()); - dead_phi_elimimation.MarkDeadPhis(); - - // 9) Make sure environments use the right phi equivalent: a phi marked dead - // can have a phi equivalent that is not dead. In that case we have to replace - // it with the live equivalent because deoptimization and try/catch rely on - // environments containing values of all live vregs at that point. Note that - // there can be multiple phis for the same Dex register that are live - // (for example when merging constants), in which case it is okay for the - // environments to just reference one. - FixEnvironmentPhis(); - - // 10) Now that the right phis are used for the environments, we can eliminate - // phis we do not need. Regardless of the debuggable status, this phase is - /// necessary for statement (b) of the SsaBuilder (see ssa_builder.h), as well - // as for the code generation, which does not deal with phis of conflicting + // 11) Now that the right phis are used for the environments, and we + // have potentially revive dead phis in case of a debuggable application, + // we can eliminate phis we do not need. Regardless of the debuggable status, + // this phase is necessary for statement (b) of the SsaBuilder (see ssa_builder.h), + // as well as for the code generation, which does not deal with phis of conflicting // input types. - dead_phi_elimimation.EliminateDeadPhis(); + dead_phis.EliminateDeadPhis(); - // 11) Clear locals. + // 12) Clear locals. for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions()); !it.Done(); it.Advance()) { @@ -466,8 +404,6 @@ BuildSsaResult SsaBuilder::BuildSsa() { current->GetBlock()->RemoveInstruction(current); } } - - return kBuildSsaSuccess; } ArenaVector<HInstruction*>* SsaBuilder::GetLocalsFor(HBasicBlock* block) { @@ -655,8 +591,6 @@ HDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) { * phi with a floating point / reference type. */ HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) { - DCHECK(phi->IsLive()) << "Cannot get equivalent of a dead phi since it would create a live one."; - // We place the floating point /reference phi next to this phi. HInstruction* next = phi->GetNext(); if (next != nullptr @@ -672,50 +606,35 @@ HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive: ArenaAllocator* allocator = phi->GetBlock()->GetGraph()->GetArena(); HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), phi->InputCount(), type); for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { - // Copy the inputs. Note that the graph may not be correctly typed - // by doing this copy, but the type propagation phase will fix it. + // Copy the inputs. Note that the graph may not be correctly typed by doing this copy, + // but the type propagation phase will fix it. new_phi->SetRawInputAt(i, phi->InputAt(i)); } phi->GetBlock()->InsertPhiAfter(new_phi, phi); - DCHECK(new_phi->IsLive()); return new_phi; } else { - // An existing equivalent was found. If it is dead, conflict was previously - // identified and we return nullptr instead. HPhi* next_phi = next->AsPhi(); DCHECK_EQ(next_phi->GetType(), type); - return next_phi->IsLive() ? next_phi : nullptr; - } -} - -HArrayGet* SsaBuilder::GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { - DCHECK(Primitive::IsIntegralType(aget->GetType())); - - if (!Primitive::IsIntOrLongType(aget->GetType())) { - // Cannot type boolean, char, byte, short to float/double. - return nullptr; - } - - DCHECK(ContainsElement(ambiguous_agets_, aget)); - if (agets_fixed_) { - // This used to be an ambiguous ArrayGet but its type has been resolved to - // int/long. Requesting a float/double equivalent should lead to a conflict. - if (kIsDebugBuild) { - ScopedObjectAccess soa(Thread::Current()); - DCHECK(IsArrayGetOnIntegralArray(aget)); + if (next_phi->IsDead()) { + // TODO(dbrazdil): Remove this SetLive (we should not need to revive phis) + // once we stop running MarkDeadPhis before PrimitiveTypePropagation. This + // cannot revive undefined loop header phis because they cannot have uses. + DCHECK(!IsUndefinedLoopHeaderPhi(next_phi)); + next_phi->SetLive(); } - return nullptr; - } else { - // This is an ambiguous ArrayGet which has not been resolved yet. Return an - // equivalent float/double instruction to use until it is resolved. - HArrayGet* equivalent = FindFloatOrDoubleEquivalentOfArrayGet(aget); - return (equivalent == nullptr) ? CreateFloatOrDoubleEquivalentOfArrayGet(aget) : equivalent; + return next_phi; } } -HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* value, Primitive::Type type) { +HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* user, + HInstruction* value, + Primitive::Type type) { if (value->IsArrayGet()) { - return GetFloatOrDoubleEquivalentOfArrayGet(value->AsArrayGet()); + // The verifier has checked that values in arrays cannot be used for both + // floating point and non-floating point operations. It is therefore safe to just + // change the type of the operation. + value->AsArrayGet()->SetType(type); + return value; } else if (value->IsLongConstant()) { return GetDoubleEquivalent(value->AsLongConstant()); } else if (value->IsIntConstant()) { @@ -723,7 +642,12 @@ HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* value, Primit } else if (value->IsPhi()) { return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type); } else { - return nullptr; + // For other instructions, we assume the verifier has checked that the dex format is correctly + // typed and the value in a dex register will not be used for both floating point and + // non-floating point operations. So the only reason an instruction would want a floating + // point equivalent is for an unused phi that will be removed by the dead phi elimination phase. + DCHECK(user->IsPhi()) << "is actually " << user->DebugName() << " (" << user->GetId() << ")"; + return value; } } @@ -738,17 +662,15 @@ HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) { } void SsaBuilder::VisitLoadLocal(HLoadLocal* load) { - Primitive::Type load_type = load->GetType(); HInstruction* value = (*current_locals_)[load->GetLocal()->GetRegNumber()]; // If the operation requests a specific type, we make sure its input is of that type. - if (load_type != value->GetType()) { - if (load_type == Primitive::kPrimFloat || load_type == Primitive::kPrimDouble) { - value = GetFloatOrDoubleEquivalent(value, load_type); - } else if (load_type == Primitive::kPrimNot) { + if (load->GetType() != value->GetType()) { + if (load->GetType() == Primitive::kPrimFloat || load->GetType() == Primitive::kPrimDouble) { + value = GetFloatOrDoubleEquivalent(load, value, load->GetType()); + } else if (load->GetType() == Primitive::kPrimNot) { value = GetReferenceTypeEquivalent(value); } } - load->ReplaceWith(value); load->GetBlock()->RemoveInstruction(load); } @@ -838,13 +760,4 @@ void SsaBuilder::VisitTemporary(HTemporary* temp) { temp->GetBlock()->RemoveInstruction(temp); } -void SsaBuilder::VisitArrayGet(HArrayGet* aget) { - Primitive::Type type = aget->GetType(); - DCHECK(!Primitive::IsFloatingPointType(type)); - if (Primitive::IsIntOrLongType(type)) { - ambiguous_agets_.push_back(aget); - } - VisitInstruction(aget); -} - } // namespace art diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h index ed6f5cab51..dcce5e4c2c 100644 --- a/compiler/optimizing/ssa_builder.h +++ b/compiler/optimizing/ssa_builder.h @@ -49,20 +49,17 @@ static constexpr int kDefaultNumberOfLoops = 2; */ class SsaBuilder : public HGraphVisitor { public: - explicit SsaBuilder(HGraph* graph, StackHandleScopeCollection* handles) + explicit SsaBuilder(HGraph* graph) : HGraphVisitor(graph), - handles_(handles), - agets_fixed_(false), current_locals_(nullptr), loop_headers_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), - ambiguous_agets_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), locals_for_(graph->GetBlocks().size(), ArenaVector<HInstruction*>(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) { loop_headers_.reserve(kDefaultNumberOfLoops); } - BuildSsaResult BuildSsa(); + void BuildSsa(); // Returns locals vector for `block`. If it is a catch block, the vector will be // prepopulated with catch phis for vregs which are defined in `current_locals_`. @@ -74,38 +71,23 @@ class SsaBuilder : public HGraphVisitor { void VisitStoreLocal(HStoreLocal* store); void VisitInstruction(HInstruction* instruction); void VisitTemporary(HTemporary* instruction); - void VisitArrayGet(HArrayGet* aget); + + static HInstruction* GetFloatOrDoubleEquivalent(HInstruction* user, + HInstruction* instruction, + Primitive::Type type); + + static HInstruction* GetReferenceTypeEquivalent(HInstruction* instruction); static constexpr const char* kSsaBuilderPassName = "ssa_builder"; private: void SetLoopHeaderPhiInputs(); - void FixEnvironmentPhis(); void FixNullConstantType(); 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(); - - bool TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist); - bool UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist); - void ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* worklist); - HInstruction* GetFloatOrDoubleEquivalent(HInstruction* instruction, Primitive::Type type); - HInstruction* GetReferenceTypeEquivalent(HInstruction* instruction); - - HFloatConstant* GetFloatEquivalent(HIntConstant* constant); - HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant); - HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type); - HArrayGet* GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget); - - StackHandleScopeCollection* const handles_; - - // True if types of ambiguous ArrayGets have been resolved. - bool agets_fixed_; + static HFloatConstant* GetFloatEquivalent(HIntConstant* constant); + static HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant); + static HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type); // Locals for the current block being visited. ArenaVector<HInstruction*>* current_locals_; @@ -114,8 +96,6 @@ class SsaBuilder : public HGraphVisitor { // over these blocks to set the inputs of their phis. ArenaVector<HBasicBlock*> loop_headers_; - ArenaVector<HArrayGet*> ambiguous_agets_; - // 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..a3219dcc38 100644 --- a/compiler/optimizing/ssa_phi_elimination.cc +++ b/compiler/optimizing/ssa_phi_elimination.cc @@ -40,17 +40,15 @@ void SsaDeadPhiElimination::MarkDeadPhis() { continue; } - bool keep_alive = (graph_->IsDebuggable() && phi->HasEnvironmentUses()); - if (!keep_alive) { - for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { - if (!use_it.Current()->GetUser()->IsPhi()) { - keep_alive = true; - break; - } + bool has_non_phi_use = false; + for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { + if (!use_it.Current()->GetUser()->IsPhi()) { + has_non_phi_use = true; + break; } } - if (keep_alive) { + if (has_non_phi_use) { worklist_.push_back(phi); } else { phi->SetDead(); @@ -96,8 +94,8 @@ void SsaDeadPhiElimination::EliminateDeadPhis() { for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { HInstruction* user = use_it.Current()->GetUser(); - DCHECK(user->IsLoopHeaderPhi()); - DCHECK(user->AsPhi()->IsDead()); + DCHECK(user->IsLoopHeaderPhi()) << user->GetId(); + DCHECK(user->AsPhi()->IsDead()) << user->GetId(); } } // Remove the phi from use lists of its inputs. diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc index d2885a8fd7..024278f4b2 100644 --- a/compiler/optimizing/ssa_test.cc +++ b/compiler/optimizing/ssa_test.cc @@ -28,8 +28,6 @@ namespace art { -class SsaTest : public CommonCompilerTest {}; - class SsaPrettyPrinter : public HPrettyPrinter { public: explicit SsaPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {} @@ -85,10 +83,11 @@ static void TestCode(const uint16_t* data, const char* expected) { bool graph_built = builder.BuildGraph(*item); ASSERT_TRUE(graph_built); - TransformToSsa(graph); + graph->BuildDominatorTree(); // Suspend checks implementation may change in the future, and this test relies // on how instructions are ordered. RemoveSuspendChecks(graph); + graph->TransformToSsa(); ReNumberInstructions(graph); // Test that phis had their type set. @@ -104,7 +103,7 @@ static void TestCode(const uint16_t* data, const char* expected) { ASSERT_STREQ(expected, printer.str().c_str()); } -TEST_F(SsaTest, CFG1) { +TEST(SsaTest, CFG1) { // Test that we get rid of loads and stores. const char* expected = "BasicBlock 0, succ: 1\n" @@ -132,7 +131,7 @@ TEST_F(SsaTest, CFG1) { TestCode(data, expected); } -TEST_F(SsaTest, CFG2) { +TEST(SsaTest, CFG2) { // Test that we create a phi for the join block of an if control flow instruction // when there is only code in the else branch. const char* expected = @@ -163,7 +162,7 @@ TEST_F(SsaTest, CFG2) { TestCode(data, expected); } -TEST_F(SsaTest, CFG3) { +TEST(SsaTest, CFG3) { // Test that we create a phi for the join block of an if control flow instruction // when both branches update a local. const char* expected = @@ -196,7 +195,7 @@ TEST_F(SsaTest, CFG3) { TestCode(data, expected); } -TEST_F(SsaTest, Loop1) { +TEST(SsaTest, Loop1) { // Test that we create a phi for an initialized local at entry of a loop. const char* expected = "BasicBlock 0, succ: 1\n" @@ -229,7 +228,7 @@ TEST_F(SsaTest, Loop1) { TestCode(data, expected); } -TEST_F(SsaTest, Loop2) { +TEST(SsaTest, Loop2) { // Simple loop with one preheader and one back edge. const char* expected = "BasicBlock 0, succ: 1\n" @@ -259,7 +258,7 @@ TEST_F(SsaTest, Loop2) { TestCode(data, expected); } -TEST_F(SsaTest, Loop3) { +TEST(SsaTest, Loop3) { // Test that a local not yet defined at the entry of a loop is handled properly. const char* expected = "BasicBlock 0, succ: 1\n" @@ -291,7 +290,7 @@ TEST_F(SsaTest, Loop3) { TestCode(data, expected); } -TEST_F(SsaTest, Loop4) { +TEST(SsaTest, Loop4) { // Make sure we support a preheader of a loop not being the first predecessor // in the predecessor list of the header. const char* expected = @@ -326,7 +325,7 @@ TEST_F(SsaTest, Loop4) { TestCode(data, expected); } -TEST_F(SsaTest, Loop5) { +TEST(SsaTest, Loop5) { // Make sure we create a preheader of a loop when a header originally has two // incoming blocks and one back edge. const char* expected = @@ -368,7 +367,7 @@ TEST_F(SsaTest, Loop5) { TestCode(data, expected); } -TEST_F(SsaTest, Loop6) { +TEST(SsaTest, Loop6) { // Test a loop with one preheader and two back edges (e.g. continue). const char* expected = "BasicBlock 0, succ: 1\n" @@ -407,7 +406,7 @@ TEST_F(SsaTest, Loop6) { TestCode(data, expected); } -TEST_F(SsaTest, Loop7) { +TEST(SsaTest, Loop7) { // Test a loop with one preheader, one back edge, and two exit edges (e.g. break). const char* expected = "BasicBlock 0, succ: 1\n" @@ -449,7 +448,7 @@ TEST_F(SsaTest, Loop7) { TestCode(data, expected); } -TEST_F(SsaTest, DeadLocal) { +TEST(SsaTest, DeadLocal) { // Test that we correctly handle a local not being used. const char* expected = "BasicBlock 0, succ: 1\n" @@ -467,7 +466,7 @@ TEST_F(SsaTest, DeadLocal) { TestCode(data, expected); } -TEST_F(SsaTest, LocalInIf) { +TEST(SsaTest, LocalInIf) { // Test that we do not create a phi in the join block when one predecessor // does not update the local. const char* expected = @@ -497,7 +496,7 @@ TEST_F(SsaTest, LocalInIf) { TestCode(data, expected); } -TEST_F(SsaTest, MultiplePredecessors) { +TEST(SsaTest, MultiplePredecessors) { // Test that we do not create a phi when one predecessor // does not update the local. const char* expected = diff --git a/test/444-checker-nce/src/Main.java b/test/444-checker-nce/src/Main.java index 865355ce97..32122e4dcd 100644 --- a/test/444-checker-nce/src/Main.java +++ b/test/444-checker-nce/src/Main.java @@ -16,11 +16,11 @@ public class Main { - /// CHECK-START: Main Main.keepTest(Main) instruction_simplifier (before) + /// CHECK-START: Main Main.keepTest(Main) instruction_simplifier_after_types (before) /// CHECK: NullCheck /// CHECK: InvokeStaticOrDirect - /// CHECK-START: Main Main.keepTest(Main) instruction_simplifier (after) + /// CHECK-START: Main Main.keepTest(Main) instruction_simplifier_after_types (after) /// CHECK: NullCheck /// CHECK: InvokeStaticOrDirect public Main keepTest(Main m) { @@ -31,7 +31,7 @@ public class Main { /// CHECK: NullCheck /// CHECK: InvokeStaticOrDirect - /// CHECK-START: Main Main.thisTest() instruction_simplifier (after) + /// CHECK-START: Main Main.thisTest() instruction_simplifier_after_types (after) /// CHECK-NOT: NullCheck /// CHECK: InvokeStaticOrDirect public Main thisTest() { @@ -45,7 +45,7 @@ public class Main { /// CHECK: NullCheck /// CHECK: InvokeStaticOrDirect - /// CHECK-START: Main Main.newInstanceRemoveTest() instruction_simplifier (after) + /// CHECK-START: Main Main.newInstanceRemoveTest() instruction_simplifier_after_types (after) /// CHECK-NOT: NullCheck public Main newInstanceRemoveTest() { Main m = new Main(); @@ -57,7 +57,7 @@ public class Main { /// CHECK: NullCheck /// CHECK: ArrayGet - /// CHECK-START: Main Main.newArrayRemoveTest() instruction_simplifier (after) + /// CHECK-START: Main Main.newArrayRemoveTest() instruction_simplifier_after_types (after) /// CHECK: NewArray /// CHECK-NOT: NullCheck /// CHECK: ArrayGet @@ -66,11 +66,11 @@ public class Main { return ms[0]; } - /// CHECK-START: Main Main.ifRemoveTest(boolean) instruction_simplifier (before) + /// CHECK-START: Main Main.ifRemoveTest(boolean) instruction_simplifier_after_types (before) /// CHECK: NewInstance /// CHECK: NullCheck - /// CHECK-START: Main Main.ifRemoveTest(boolean) instruction_simplifier (after) + /// CHECK-START: Main Main.ifRemoveTest(boolean) instruction_simplifier_after_types (after) /// CHECK: NewInstance /// CHECK-NOT: NullCheck public Main ifRemoveTest(boolean flag) { @@ -83,11 +83,11 @@ public class Main { return m.g(); } - /// CHECK-START: Main Main.ifKeepTest(boolean) instruction_simplifier (before) + /// CHECK-START: Main Main.ifKeepTest(boolean) instruction_simplifier_after_types (before) /// CHECK: NewInstance /// CHECK: NullCheck - /// CHECK-START: Main Main.ifKeepTest(boolean) instruction_simplifier (after) + /// CHECK-START: Main Main.ifKeepTest(boolean) instruction_simplifier_after_types (after) /// CHECK: NewInstance /// CHECK: NullCheck public Main ifKeepTest(boolean flag) { @@ -98,10 +98,10 @@ public class Main { return m.g(); } - /// CHECK-START: Main Main.forRemoveTest(int) instruction_simplifier (before) + /// CHECK-START: Main Main.forRemoveTest(int) instruction_simplifier_after_types (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.forRemoveTest(int) instruction_simplifier (after) + /// CHECK-START: Main Main.forRemoveTest(int) instruction_simplifier_after_types (after) /// CHECK-NOT: NullCheck public Main forRemoveTest(int count) { Main a = new Main(); @@ -114,10 +114,10 @@ public class Main { return m.g(); } - /// CHECK-START: Main Main.forKeepTest(int) instruction_simplifier (before) + /// CHECK-START: Main Main.forKeepTest(int) instruction_simplifier_after_types (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.forKeepTest(int) instruction_simplifier (after) + /// CHECK-START: Main Main.forKeepTest(int) instruction_simplifier_after_types (after) /// CHECK: NullCheck public Main forKeepTest(int count) { Main a = new Main(); @@ -132,10 +132,10 @@ public class Main { return m.g(); } - /// CHECK-START: Main Main.phiFlowRemoveTest(int) instruction_simplifier (before) + /// CHECK-START: Main Main.phiFlowRemoveTest(int) instruction_simplifier_after_types (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.phiFlowRemoveTest(int) instruction_simplifier (after) + /// CHECK-START: Main Main.phiFlowRemoveTest(int) instruction_simplifier_after_types (after) /// CHECK-NOT: NullCheck public Main phiFlowRemoveTest(int count) { Main a = new Main(); @@ -154,10 +154,10 @@ public class Main { return n.g(); } - /// CHECK-START: Main Main.phiFlowKeepTest(int) instruction_simplifier (before) + /// CHECK-START: Main Main.phiFlowKeepTest(int) instruction_simplifier_after_types (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.phiFlowKeepTest(int) instruction_simplifier (after) + /// CHECK-START: Main Main.phiFlowKeepTest(int) instruction_simplifier_after_types (after) /// CHECK: NullCheck public Main phiFlowKeepTest(int count) { Main a = new Main(); @@ -181,7 +181,7 @@ public class Main { /// CHECK-START: Main Main.scopeRemoveTest(int, Main) ssa_builder (after) /// CHECK: NullCheck - /// CHECK-START: Main Main.scopeRemoveTest(int, Main) instruction_simplifier (after) + /// CHECK-START: Main Main.scopeRemoveTest(int, Main) instruction_simplifier_after_types (after) /// CHECK-NOT: NullCheck public Main scopeRemoveTest(int count, Main a) { Main m = null; @@ -196,10 +196,10 @@ public class Main { return m; } - /// CHECK-START: Main Main.scopeKeepTest(int, Main) instruction_simplifier (before) + /// CHECK-START: Main Main.scopeKeepTest(int, Main) instruction_simplifier_after_types (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.scopeKeepTest(int, Main) instruction_simplifier (after) + /// CHECK-START: Main Main.scopeKeepTest(int, Main) instruction_simplifier_after_types (after) /// CHECK: NullCheck public Main scopeKeepTest(int count, Main a) { Main m = new Main(); @@ -214,10 +214,10 @@ public class Main { return m; } - /// CHECK-START: Main Main.scopeIfNotNullRemove(Main) instruction_simplifier (before) + /// CHECK-START: Main Main.scopeIfNotNullRemove(Main) instruction_simplifier_after_types (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.scopeIfNotNullRemove(Main) instruction_simplifier (after) + /// CHECK-START: Main Main.scopeIfNotNullRemove(Main) instruction_simplifier_after_types (after) /// CHECK-NOT: NullCheck public Main scopeIfNotNullRemove(Main m) { if (m != null) { @@ -226,10 +226,10 @@ public class Main { return m; } - /// CHECK-START: Main Main.scopeIfKeep(Main) instruction_simplifier (before) + /// CHECK-START: Main Main.scopeIfKeep(Main) instruction_simplifier_after_types (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.scopeIfKeep(Main) instruction_simplifier (after) + /// CHECK-START: Main Main.scopeIfKeep(Main) instruction_simplifier_after_types (after) /// CHECK: NullCheck public Main scopeIfKeep(Main m) { if (m == null) { @@ -258,11 +258,11 @@ public class Main { class ListElement { private ListElement next; - /// CHECK-START: boolean ListElement.isShorter(ListElement, ListElement) instruction_simplifier (before) + /// CHECK-START: boolean ListElement.isShorter(ListElement, ListElement) instruction_simplifier_after_types (before) /// CHECK: NullCheck /// CHECK: NullCheck - /// CHECK-START: boolean ListElement.isShorter(ListElement, ListElement) instruction_simplifier (after) + /// CHECK-START: boolean ListElement.isShorter(ListElement, ListElement) instruction_simplifier_after_types (after) /// CHECK-NOT: NullCheck static boolean isShorter(ListElement x, ListElement y) { ListElement xTail = x; diff --git a/test/450-checker-types/src/Main.java b/test/450-checker-types/src/Main.java index fd4dd5ecbf..f1f80caff0 100644 --- a/test/450-checker-types/src/Main.java +++ b/test/450-checker-types/src/Main.java @@ -72,49 +72,49 @@ final class FinalException extends Exception {} public class Main { - /// CHECK-START: void Main.testSimpleRemove() instruction_simplifier (before) + /// CHECK-START: void Main.testSimpleRemove() instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testSimpleRemove() instruction_simplifier (after) + /// CHECK-START: void Main.testSimpleRemove() instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testSimpleRemove() { Super s = new SubclassA(); ((SubclassA)s).$noinline$g(); } - /// CHECK-START: void Main.testSimpleKeep(Super) instruction_simplifier (before) + /// CHECK-START: void Main.testSimpleKeep(Super) instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testSimpleKeep(Super) instruction_simplifier (after) + /// CHECK-START: void Main.testSimpleKeep(Super) instruction_simplifier_after_types (after) /// CHECK: CheckCast public void testSimpleKeep(Super s) { ((SubclassA)s).$noinline$f(); } - /// CHECK-START: java.lang.String Main.testClassRemove() instruction_simplifier (before) + /// CHECK-START: java.lang.String Main.testClassRemove() instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: java.lang.String Main.testClassRemove() instruction_simplifier (after) + /// CHECK-START: java.lang.String Main.testClassRemove() instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public String testClassRemove() { Object s = SubclassA.class; return ((Class)s).getName(); } - /// CHECK-START: java.lang.String Main.testClassKeep() instruction_simplifier (before) + /// CHECK-START: java.lang.String Main.testClassKeep() instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: java.lang.String Main.testClassKeep() instruction_simplifier (after) + /// CHECK-START: java.lang.String Main.testClassKeep() instruction_simplifier_after_types (after) /// CHECK: CheckCast public String testClassKeep() { Object s = SubclassA.class; return ((SubclassA)s).$noinline$h(); } - /// CHECK-START: void Main.testIfRemove(int) instruction_simplifier (before) + /// CHECK-START: void Main.testIfRemove(int) instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testIfRemove(int) instruction_simplifier (after) + /// CHECK-START: void Main.testIfRemove(int) instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testIfRemove(int x) { Super s; @@ -126,10 +126,10 @@ public class Main { ((SubclassA)s).$noinline$g(); } - /// CHECK-START: void Main.testIfKeep(int) instruction_simplifier (before) + /// CHECK-START: void Main.testIfKeep(int) instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testIfKeep(int) instruction_simplifier (after) + /// CHECK-START: void Main.testIfKeep(int) instruction_simplifier_after_types (after) /// CHECK: CheckCast public void testIfKeep(int x) { Super s; @@ -141,10 +141,10 @@ public class Main { ((SubclassA)s).$noinline$g(); } - /// CHECK-START: void Main.testForRemove(int) instruction_simplifier (before) + /// CHECK-START: void Main.testForRemove(int) instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testForRemove(int) instruction_simplifier (after) + /// CHECK-START: void Main.testForRemove(int) instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testForRemove(int x) { Super s = new SubclassA(); @@ -156,10 +156,10 @@ public class Main { ((SubclassA)s).$noinline$g(); } - /// CHECK-START: void Main.testForKeep(int) instruction_simplifier (before) + /// CHECK-START: void Main.testForKeep(int) instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testForKeep(int) instruction_simplifier (after) + /// CHECK-START: void Main.testForKeep(int) instruction_simplifier_after_types (after) /// CHECK: CheckCast public void testForKeep(int x) { Super s = new SubclassA(); @@ -171,10 +171,10 @@ public class Main { ((SubclassC)s).$noinline$g(); } - /// CHECK-START: void Main.testPhiFromCall(int) instruction_simplifier (before) + /// CHECK-START: void Main.testPhiFromCall(int) instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testPhiFromCall(int) instruction_simplifier (after) + /// CHECK-START: void Main.testPhiFromCall(int) instruction_simplifier_after_types (after) /// CHECK: CheckCast public void testPhiFromCall(int i) { Object x; @@ -186,12 +186,11 @@ public class Main { ((SubclassC)x).$noinline$g(); } - /// CHECK-START: void Main.testInstanceOf(java.lang.Object) instruction_simplifier (before) + /// CHECK-START: void Main.testInstanceOf(java.lang.Object) instruction_simplifier_after_types (before) /// CHECK: CheckCast /// CHECK: CheckCast - /// CHECK-NOT: CheckCast - /// CHECK-START: void Main.testInstanceOf(java.lang.Object) instruction_simplifier (after) + /// CHECK-START: void Main.testInstanceOf(java.lang.Object) instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testInstanceOf(Object o) { if (o instanceof SubclassC) { @@ -202,101 +201,11 @@ public class Main { } } - public static boolean $inline$InstanceofSubclassB(Object o) { return o instanceof SubclassB; } - public static boolean $inline$InstanceofSubclassC(Object o) { return o instanceof SubclassC; } - - /// CHECK-START: void Main.testInstanceOf_NotInlined(java.lang.Object) ssa_builder (after) - /// CHECK-DAG: <<Cst0:i\d+>> IntConstant 0 - /// CHECK-DAG: <<Cst1:i\d+>> IntConstant 1 - /// CHECK-DAG: <<IOf1:z\d+>> InstanceOf - /// CHECK-DAG: NotEqual [<<IOf1>>,<<Cst1>>] - /// CHECK-DAG: <<IOf2:z\d+>> InstanceOf - /// CHECK-DAG: Equal [<<IOf2>>,<<Cst0>>] - - /// CHECK-START: void Main.testInstanceOf_NotInlined(java.lang.Object) instruction_simplifier (before) - /// CHECK: CheckCast - /// CHECK: CheckCast - /// CHECK-NOT: CheckCast - - /// CHECK-START: void Main.testInstanceOf_NotInlined(java.lang.Object) instruction_simplifier (after) - /// CHECK-NOT: CheckCast - public void testInstanceOf_NotInlined(Object o) { - if ((o instanceof SubclassC) == true) { - ((SubclassC)o).$noinline$g(); - } - if ((o instanceof SubclassB) != false) { - ((SubclassB)o).$noinline$g(); - } - } - - /// CHECK-START: void Main.testNotInstanceOf_NotInlined(java.lang.Object) ssa_builder (after) - /// CHECK-DAG: <<Cst0:i\d+>> IntConstant 0 - /// CHECK-DAG: <<Cst1:i\d+>> IntConstant 1 - /// CHECK-DAG: <<IOf1:z\d+>> InstanceOf - /// CHECK-DAG: Equal [<<IOf1>>,<<Cst1>>] - /// CHECK-DAG: <<IOf2:z\d+>> InstanceOf - /// CHECK-DAG: NotEqual [<<IOf2>>,<<Cst0>>] - - /// CHECK-START: void Main.testNotInstanceOf_NotInlined(java.lang.Object) instruction_simplifier (before) - /// CHECK: CheckCast - /// CHECK: CheckCast - /// CHECK-NOT: CheckCast - - /// CHECK-START: void Main.testNotInstanceOf_NotInlined(java.lang.Object) instruction_simplifier (after) - /// CHECK-NOT: CheckCast - public void testNotInstanceOf_NotInlined(Object o) { - if ((o instanceof SubclassC) != true) { - // Empty branch to flip the condition. - } else { - ((SubclassC)o).$noinline$g(); - } - if ((o instanceof SubclassB) == false) { - // Empty branch to flip the condition. - } else { - ((SubclassB)o).$noinline$g(); - } - } - - /// CHECK-START: void Main.testInstanceOf_Inlined(java.lang.Object) inliner (after) - /// CHECK-DAG: <<IOf:z\d+>> InstanceOf - /// CHECK-DAG: If [<<IOf>>] - - /// CHECK-START: void Main.testInstanceOf_Inlined(java.lang.Object) instruction_simplifier_after_bce (before) - /// CHECK: CheckCast - /// CHECK-NOT: CheckCast - - /// CHECK-START: void Main.testInstanceOf_Inlined(java.lang.Object) instruction_simplifier_after_bce (after) - /// CHECK-NOT: CheckCast - public void testInstanceOf_Inlined(Object o) { - if (!$inline$InstanceofSubclassC(o)) { - // Empty branch to flip the condition. - } else { - ((SubclassC)o).$noinline$g(); - } - } - - /// CHECK-START: void Main.testNotInstanceOf_Inlined(java.lang.Object) inliner (after) - /// CHECK-DAG: <<IOf:z\d+>> InstanceOf - /// CHECK-DAG: <<Not:z\d+>> BooleanNot [<<IOf>>] - /// CHECK-DAG: If [<<Not>>] - - /// CHECK-START: void Main.testNotInstanceOf_Inlined(java.lang.Object) instruction_simplifier_after_bce (before) - /// CHECK: CheckCast - /// CHECK-NOT: CheckCast - - /// CHECK-START: void Main.testNotInstanceOf_Inlined(java.lang.Object) instruction_simplifier_after_bce (after) - /// CHECK-NOT: CheckCast - public void testNotInstanceOf_Inlined(Object o) { - if ($inline$InstanceofSubclassC(o)) { - ((SubclassC)o).$noinline$g(); - } - } - - /// CHECK-START: void Main.testInstanceOfKeep(java.lang.Object) instruction_simplifier (before) + /// CHECK-START: void Main.testInstanceOfKeep(java.lang.Object) instruction_simplifier_after_types (before) /// CHECK: CheckCast /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfKeep(java.lang.Object) instruction_simplifier (after) + /// CHECK-START: void Main.testInstanceOfKeep(java.lang.Object) instruction_simplifier_after_types (after) /// CHECK: CheckCast /// CHECK: CheckCast public void testInstanceOfKeep(Object o) { @@ -308,11 +217,11 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfNested(java.lang.Object) instruction_simplifier (before) + /// CHECK-START: void Main.testInstanceOfNested(java.lang.Object) instruction_simplifier_after_types (before) /// CHECK: CheckCast /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfNested(java.lang.Object) instruction_simplifier (after) + /// CHECK-START: void Main.testInstanceOfNested(java.lang.Object) instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testInstanceOfNested(Object o) { if (o instanceof SubclassC) { @@ -324,10 +233,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfWithPhi(int) instruction_simplifier (before) + /// CHECK-START: void Main.testInstanceOfWithPhi(int) instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfWithPhi(int) instruction_simplifier (after) + /// CHECK-START: void Main.testInstanceOfWithPhi(int) instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testInstanceOfWithPhi(int i) { Object o; @@ -342,10 +251,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfInFor(int) instruction_simplifier (before) + /// CHECK-START: void Main.testInstanceOfInFor(int) instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfInFor(int) instruction_simplifier (after) + /// CHECK-START: void Main.testInstanceOfInFor(int) instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testInstanceOfInFor(int n) { Object o = new SubclassA(); @@ -359,10 +268,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfSubclass() instruction_simplifier (before) + /// CHECK-START: void Main.testInstanceOfSubclass() instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfSubclass() instruction_simplifier (after) + /// CHECK-START: void Main.testInstanceOfSubclass() instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testInstanceOfSubclass() { Object o = new SubclassA(); @@ -371,10 +280,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfWithPhiSubclass(int) instruction_simplifier (before) + /// CHECK-START: void Main.testInstanceOfWithPhiSubclass(int) instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfWithPhiSubclass(int) instruction_simplifier (after) + /// CHECK-START: void Main.testInstanceOfWithPhiSubclass(int) instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testInstanceOfWithPhiSubclass(int i) { Object o; @@ -389,10 +298,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfWithPhiTop(int) instruction_simplifier (before) + /// CHECK-START: void Main.testInstanceOfWithPhiTop(int) instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfWithPhiTop(int) instruction_simplifier (after) + /// CHECK-START: void Main.testInstanceOfWithPhiTop(int) instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testInstanceOfWithPhiTop(int i) { Object o; @@ -407,10 +316,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfSubclassInFor(int) instruction_simplifier (before) + /// CHECK-START: void Main.testInstanceOfSubclassInFor(int) instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfSubclassInFor(int) instruction_simplifier (after) + /// CHECK-START: void Main.testInstanceOfSubclassInFor(int) instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testInstanceOfSubclassInFor(int n) { Object o = new SubclassA(); @@ -424,10 +333,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfTopInFor(int) instruction_simplifier (before) + /// CHECK-START: void Main.testInstanceOfTopInFor(int) instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfTopInFor(int) instruction_simplifier (after) + /// CHECK-START: void Main.testInstanceOfTopInFor(int) instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testInstanceOfTopInFor(int n) { Object o = new SubclassA(); @@ -452,10 +361,10 @@ public class Main { public SubclassA a = new SubclassA(); public static SubclassA b = new SubclassA(); - /// CHECK-START: void Main.testInstanceFieldGetSimpleRemove() instruction_simplifier (before) + /// CHECK-START: void Main.testInstanceFieldGetSimpleRemove() instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceFieldGetSimpleRemove() instruction_simplifier (after) + /// CHECK-START: void Main.testInstanceFieldGetSimpleRemove() instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testInstanceFieldGetSimpleRemove() { Main m = new Main(); @@ -463,10 +372,10 @@ public class Main { ((SubclassA)a).$noinline$g(); } - /// CHECK-START: void Main.testStaticFieldGetSimpleRemove() instruction_simplifier (before) + /// CHECK-START: void Main.testStaticFieldGetSimpleRemove() instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testStaticFieldGetSimpleRemove() instruction_simplifier (after) + /// CHECK-START: void Main.testStaticFieldGetSimpleRemove() instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testStaticFieldGetSimpleRemove() { Super b = Main.b; @@ -475,36 +384,36 @@ public class Main { public SubclassA $noinline$getSubclass() { throw new RuntimeException(); } - /// CHECK-START: void Main.testArraySimpleRemove() instruction_simplifier (before) + /// CHECK-START: void Main.testArraySimpleRemove() instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testArraySimpleRemove() instruction_simplifier (after) + /// CHECK-START: void Main.testArraySimpleRemove() instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testArraySimpleRemove() { Super[] b = new SubclassA[10]; SubclassA[] c = (SubclassA[])b; } - /// CHECK-START: void Main.testInvokeSimpleRemove() instruction_simplifier (before) + /// CHECK-START: void Main.testInvokeSimpleRemove() instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInvokeSimpleRemove() instruction_simplifier (after) + /// CHECK-START: void Main.testInvokeSimpleRemove() instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testInvokeSimpleRemove() { Super b = $noinline$getSubclass(); ((SubclassA)b).$noinline$g(); } - /// CHECK-START: void Main.testArrayGetSimpleRemove() instruction_simplifier (before) + /// CHECK-START: void Main.testArrayGetSimpleRemove() instruction_simplifier_after_types (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testArrayGetSimpleRemove() instruction_simplifier (after) + /// CHECK-START: void Main.testArrayGetSimpleRemove() instruction_simplifier_after_types (after) /// CHECK-NOT: CheckCast public void testArrayGetSimpleRemove() { Super[] a = new SubclassA[10]; ((SubclassA)a[0]).$noinline$g(); } - /// CHECK-START: int Main.testLoadExceptionInCatchNonExact(int, int) ssa_builder (after) + /// CHECK-START: int Main.testLoadExceptionInCatchNonExact(int, int) reference_type_propagation (after) /// CHECK: LoadException klass:java.lang.ArithmeticException can_be_null:false exact:false public int testLoadExceptionInCatchNonExact(int x, int y) { try { @@ -514,7 +423,7 @@ public class Main { } } - /// CHECK-START: int Main.testLoadExceptionInCatchExact(int) ssa_builder (after) + /// CHECK-START: int Main.testLoadExceptionInCatchExact(int) reference_type_propagation (after) /// CHECK: LoadException klass:FinalException can_be_null:false exact:true public int testLoadExceptionInCatchExact(int x) { try { @@ -528,7 +437,7 @@ public class Main { } } - /// CHECK-START: int Main.testLoadExceptionInCatchAll(int, int) ssa_builder (after) + /// CHECK-START: int Main.testLoadExceptionInCatchAll(int, int) reference_type_propagation (after) /// CHECK: LoadException klass:java.lang.Throwable can_be_null:false exact:false public int testLoadExceptionInCatchAll(int x, int y) { try { @@ -549,7 +458,7 @@ public class Main { return genericFinal.get(); } - /// CHECK-START: SubclassC Main.inlineGenerics() ssa_builder (after) + /// CHECK-START: SubclassC Main.inlineGenerics() reference_type_propagation (after) /// CHECK: <<Invoke:l\d+>> InvokeStaticOrDirect klass:SubclassC exact:false /// CHECK-NEXT: Return [<<Invoke>>] @@ -561,7 +470,7 @@ public class Main { return c; } - /// CHECK-START: Final Main.inlineGenericsFinal() ssa_builder (after) + /// CHECK-START: Final Main.inlineGenericsFinal() reference_type_propagation (after) /// CHECK: <<Invoke:l\d+>> InvokeStaticOrDirect klass:Final exact:true /// CHECK-NEXT: Return [<<Invoke>>] @@ -603,7 +512,7 @@ public class Main { return new SubclassA(); } - /// CHECK-START: void Main.updateNodesInTheSameBlockAsPhi(boolean) ssa_builder (after) + /// CHECK-START: void Main.updateNodesInTheSameBlockAsPhi(boolean) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:Super /// CHECK: NullCheck [<<Phi>>] klass:Super @@ -625,7 +534,7 @@ public class Main { /// CHECK: CheckCast [<<Param>>,<<Clazz>>] /// CHECK: BoundType [<<Param>>] can_be_null:true - /// CHECK-START: java.lang.String Main.checkcastPreserveNullCheck(java.lang.Object) instruction_simplifier (after) + /// CHECK-START: java.lang.String Main.checkcastPreserveNullCheck(java.lang.Object) instruction_simplifier_after_types (after) /// CHECK: <<This:l\d+>> ParameterValue /// CHECK: <<Param:l\d+>> ParameterValue /// CHECK: <<Clazz:l\d+>> LoadClass @@ -637,7 +546,7 @@ public class Main { } - /// CHECK-START: void Main.argumentCheck(Super, double, SubclassA, Final) ssa_builder (after) + /// CHECK-START: void Main.argumentCheck(Super, double, SubclassA, Final) reference_type_propagation (after) /// CHECK: ParameterValue klass:Main can_be_null:false exact:false /// CHECK: ParameterValue klass:Super can_be_null:true exact:false /// CHECK: ParameterValue @@ -653,7 +562,7 @@ public class Main { private int mainField = 0; - /// CHECK-START: SuperInterface Main.getWiderType(boolean, Interface, OtherInterface) ssa_builder (after) + /// CHECK-START: SuperInterface Main.getWiderType(boolean, Interface, OtherInterface) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:java.lang.Object /// CHECK: Return [<<Phi>>] private SuperInterface getWiderType(boolean cond, Interface a, OtherInterface b) { @@ -709,7 +618,7 @@ public class Main { getSuper(); } - /// CHECK-START: void Main.testLoopPhiWithNullFirstInput(boolean) ssa_builder (after) + /// CHECK-START: void Main.testLoopPhiWithNullFirstInput(boolean) reference_type_propagation (after) /// CHECK-DAG: <<Null:l\d+>> NullConstant /// CHECK-DAG: <<Main:l\d+>> NewInstance klass:Main exact:true /// CHECK-DAG: <<LoopPhi:l\d+>> Phi [<<Null>>,<<LoopPhi>>,<<Main>>] klass:Main exact:true @@ -722,7 +631,7 @@ public class Main { } } - /// CHECK-START: void Main.testLoopPhisWithNullAndCrossUses(boolean) ssa_builder (after) + /// CHECK-START: void Main.testLoopPhisWithNullAndCrossUses(boolean) reference_type_propagation (after) /// CHECK-DAG: <<Null:l\d+>> NullConstant /// CHECK-DAG: <<PhiA:l\d+>> Phi [<<Null>>,<<PhiB:l\d+>>,<<PhiA>>] klass:java.lang.Object exact:false /// CHECK-DAG: <<PhiB>> Phi [<<Null>>,<<PhiB>>,<<PhiA>>] klass:java.lang.Object exact:false @@ -738,7 +647,7 @@ public class Main { } } - /// CHECK-START: java.lang.Object[] Main.testInstructionsWithUntypedParent() ssa_builder (after) + /// CHECK-START: java.lang.Object[] Main.testInstructionsWithUntypedParent() reference_type_propagation (after) /// CHECK-DAG: <<Null:l\d+>> NullConstant /// CHECK-DAG: <<LoopPhi:l\d+>> Phi [<<Null>>,<<Phi:l\d+>>] klass:java.lang.Object[] exact:true /// CHECK-DAG: <<Array:l\d+>> NewArray klass:java.lang.Object[] exact:true diff --git a/test/477-checker-bound-type/src/Main.java b/test/477-checker-bound-type/src/Main.java index 0f65e44678..c873702408 100644 --- a/test/477-checker-bound-type/src/Main.java +++ b/test/477-checker-bound-type/src/Main.java @@ -17,7 +17,7 @@ public class Main { - /// CHECK-START: java.lang.Object Main.boundTypeForIf(java.lang.Object) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.boundTypeForIf(java.lang.Object) reference_type_propagation (after) /// CHECK: BoundType public static Object boundTypeForIf(Object a) { if (a != null) { @@ -27,7 +27,7 @@ public class Main { } } - /// CHECK-START: java.lang.Object Main.boundTypeForInstanceOf(java.lang.Object) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.boundTypeForInstanceOf(java.lang.Object) reference_type_propagation (after) /// CHECK: BoundType public static Object boundTypeForInstanceOf(Object a) { if (a instanceof Main) { @@ -37,7 +37,7 @@ public class Main { } } - /// CHECK-START: java.lang.Object Main.noBoundTypeForIf(java.lang.Object) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.noBoundTypeForIf(java.lang.Object) reference_type_propagation (after) /// CHECK-NOT: BoundType public static Object noBoundTypeForIf(Object a) { if (a == null) { @@ -47,7 +47,7 @@ public class Main { } } - /// CHECK-START: java.lang.Object Main.noBoundTypeForInstanceOf(java.lang.Object) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.noBoundTypeForInstanceOf(java.lang.Object) reference_type_propagation (after) /// CHECK-NOT: BoundType public static Object noBoundTypeForInstanceOf(Object a) { if (a instanceof Main) { diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java index 3f6e48bbae..e827b1ed78 100644 --- a/test/530-checker-loops/src/Main.java +++ b/test/530-checker-loops/src/Main.java @@ -27,6 +27,7 @@ public class Main { /// CHECK-START: int Main.linear(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linear(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -40,6 +41,7 @@ public class Main { /// CHECK-START: int Main.linearDown(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearDown(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -53,6 +55,7 @@ public class Main { /// CHECK-START: int Main.linearObscure(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearObscure(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -67,6 +70,7 @@ public class Main { /// CHECK-START: int Main.linearVeryObscure(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearVeryObscure(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -79,8 +83,26 @@ public class Main { return result; } + /// CHECK-START: int Main.hiddenStride(int[]) BCE (before) + /// CHECK-DAG: BoundsCheck + // + /// CHECK-START: int Main.hiddenStride(int[]) BCE (after) + /// CHECK-NOT: BoundsCheck + /// CHECK-NOT: Deoptimize + static int hiddenStride(int[] a) { + int result = 0; + for (int i = 1; i <= 1; i++) { + // Obscured unit stride. + for (int j = 0; j < a.length; j += i) { + result += a[j]; + } + } + return result; + } + /// CHECK-START: int Main.linearWhile(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearWhile(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -95,6 +117,7 @@ public class Main { /// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -112,6 +135,7 @@ public class Main { /// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -133,6 +157,7 @@ public class Main { /// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -149,6 +174,7 @@ public class Main { /// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -169,6 +195,7 @@ public class Main { /// CHECK-START: int[] Main.linearWithParameter(int) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int[] Main.linearWithParameter(int) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -182,6 +209,7 @@ public class Main { /// CHECK-START: int[] Main.linearCopy(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int[] Main.linearCopy(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -197,6 +225,7 @@ public class Main { /// CHECK-START: int Main.linearByTwo(int[]) BCE (before) /// CHECK-DAG: BoundsCheck /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearByTwo(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -213,6 +242,7 @@ public class Main { /// CHECK-START: int Main.linearByTwoSkip1(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearByTwoSkip1(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -226,6 +256,7 @@ public class Main { /// CHECK-START: int Main.linearByTwoSkip2(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearByTwoSkip2(int[]) BCE (after) /// CHECK-DAG: BoundsCheck /// CHECK-NOT: Deoptimize @@ -240,6 +271,7 @@ public class Main { /// CHECK-START: int Main.linearWithCompoundStride() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearWithCompoundStride() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -256,6 +288,7 @@ public class Main { /// CHECK-START: int Main.linearWithLargePositiveStride() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearWithLargePositiveStride() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -273,6 +306,7 @@ public class Main { /// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (after) /// CHECK-DAG: BoundsCheck /// CHECK-NOT: Deoptimize @@ -290,6 +324,7 @@ public class Main { /// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -307,6 +342,7 @@ public class Main { /// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (after) /// CHECK-DAG: BoundsCheck /// CHECK-NOT: Deoptimize @@ -324,6 +360,7 @@ public class Main { /// CHECK-START: int Main.linearForNEUp() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearForNEUp() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -338,6 +375,7 @@ public class Main { /// CHECK-START: int Main.linearForNEDown() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearForNEDown() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -352,6 +390,7 @@ public class Main { /// CHECK-START: int Main.linearDoWhileUp() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearDoWhileUp() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -367,6 +406,7 @@ public class Main { /// CHECK-START: int Main.linearDoWhileDown() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearDoWhileDown() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -382,6 +422,7 @@ public class Main { /// CHECK-START: int Main.linearShort() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.linearShort() BCE (after) /// CHECK-DAG: BoundsCheck /// CHECK-NOT: Deoptimize @@ -397,6 +438,7 @@ public class Main { /// CHECK-START: int Main.invariantFromPreLoop(int[], int) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.invariantFromPreLoop(int[], int) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -422,6 +464,7 @@ public class Main { /// CHECK-DAG: BoundsCheck /// CHECK-DAG: ArrayGet /// CHECK-DAG: ArraySet + // /// CHECK-START: void Main.linearTriangularOnTwoArrayLengths(int) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-DAG: ArrayGet @@ -451,6 +494,7 @@ public class Main { /// CHECK-DAG: BoundsCheck /// CHECK-DAG: ArrayGet /// CHECK-DAG: ArraySet + // /// CHECK-START: void Main.linearTriangularOnOneArrayLength(int) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-DAG: ArrayGet @@ -480,6 +524,7 @@ public class Main { /// CHECK-DAG: BoundsCheck /// CHECK-DAG: ArrayGet /// CHECK-DAG: ArraySet + // /// CHECK-START: void Main.linearTriangularOnParameter(int) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-DAG: ArrayGet @@ -502,7 +547,54 @@ public class Main { } } - // Verifier for triangular methods. + /// CHECK-START: void Main.linearTriangularVariations(int) BCE (before) + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: ArrayGet + /// CHECK-DAG: ArraySet + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: ArrayGet + /// CHECK-DAG: ArraySet + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: ArrayGet + /// CHECK-DAG: ArraySet + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: ArrayGet + /// CHECK-DAG: ArraySet + // + /// CHECK-START: void Main.linearTriangularVariations(int) BCE (after) + /// CHECK-NOT: BoundsCheck + /// CHECK-DAG: ArrayGet + /// CHECK-DAG: ArraySet + /// CHECK-NOT: BoundsCheck + /// CHECK-DAG: ArrayGet + /// CHECK-DAG: ArraySet + /// CHECK-NOT: BoundsCheck + /// CHECK-DAG: ArrayGet + /// CHECK-DAG: ArraySet + /// CHECK-NOT: BoundsCheck + /// CHECK-DAG: ArrayGet + /// CHECK-DAG: ArraySet + /// CHECK-NOT: Deoptimize + private static void linearTriangularVariations(int n) { + int[] a = new int[n]; + for (int i = 0; i < n; i++) { + for (int j = 0; j < i; j++) { + a[j] += 1; + } + for (int j = i - 1; j >= 0; j--) { + a[j] += 1; + } + for (int j = i; j < n; j++) { + a[j] += 1; + } + for (int j = n - 1; j > i - 1; j--) { + a[j] += 1; + } + } + verifyTriangular(a); + } + + // Verifier for triangular loops. private static void verifyTriangular(int[] a, int[] b, int m, int n) { expectEquals(n, a.length); for (int i = 0, k = m; i < n; i++) { @@ -515,6 +607,14 @@ public class Main { } } + // Verifier for triangular loops. + private static void verifyTriangular(int[] a) { + int n = a.length; + for (int i = 0; i < n; i++) { + expectEquals(a[i], n + n); + } + } + /// CHECK-START: void Main.bubble(int[]) BCE (before) /// CHECK-DAG: BoundsCheck /// CHECK-DAG: ArrayGet @@ -523,6 +623,7 @@ public class Main { /// CHECK-DAG: If /// CHECK-DAG: ArraySet /// CHECK-DAG: ArraySet + // /// CHECK-START: void Main.bubble(int[]) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-DAG: ArrayGet @@ -546,6 +647,7 @@ public class Main { /// CHECK-START: int Main.periodicIdiom(int) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.periodicIdiom(int) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -563,6 +665,7 @@ public class Main { /// CHECK-START: int Main.periodicSequence2(int) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.periodicSequence2(int) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -586,6 +689,7 @@ public class Main { /// CHECK-DAG: BoundsCheck /// CHECK-DAG: BoundsCheck /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.periodicSequence4(int) BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -610,6 +714,7 @@ public class Main { /// CHECK-START: int Main.justRightUp1() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.justRightUp1() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -624,6 +729,7 @@ public class Main { /// CHECK-START: int Main.justRightUp2() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.justRightUp2() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -638,6 +744,7 @@ public class Main { /// CHECK-START: int Main.justRightUp3() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.justRightUp3() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -652,6 +759,7 @@ public class Main { /// CHECK-START: int Main.justOOBUp() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.justOOBUp() BCE (after) /// CHECK-DAG: BoundsCheck /// CHECK-NOT: Deoptimize @@ -667,6 +775,7 @@ public class Main { /// CHECK-START: int Main.justRightDown1() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.justRightDown1() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -681,6 +790,7 @@ public class Main { /// CHECK-START: int Main.justRightDown2() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.justRightDown2() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -695,6 +805,7 @@ public class Main { /// CHECK-START: int Main.justRightDown3() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.justRightDown3() BCE (after) /// CHECK-NOT: BoundsCheck /// CHECK-NOT: Deoptimize @@ -709,6 +820,7 @@ public class Main { /// CHECK-START: int Main.justOOBDown() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.justOOBDown() BCE (after) /// CHECK-DAG: BoundsCheck /// CHECK-NOT: Deoptimize @@ -724,6 +836,7 @@ public class Main { /// CHECK-START: void Main.lowerOOB(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: void Main.lowerOOB(int[]) BCE (after) /// CHECK-DAG: BoundsCheck /// CHECK-NOT: Deoptimize @@ -735,6 +848,7 @@ public class Main { /// CHECK-START: void Main.upperOOB(int[]) BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: void Main.upperOOB(int[]) BCE (after) /// CHECK-DAG: BoundsCheck /// CHECK-NOT: Deoptimize @@ -746,6 +860,7 @@ public class Main { /// CHECK-START: void Main.doWhileUpOOB() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: void Main.doWhileUpOOB() BCE (after) /// CHECK-DAG: BoundsCheck /// CHECK-NOT: Deoptimize @@ -759,6 +874,7 @@ public class Main { /// CHECK-START: void Main.doWhileDownOOB() BCE (before) /// CHECK-DAG: BoundsCheck + // /// CHECK-START: void Main.doWhileDownOOB() BCE (after) /// CHECK-DAG: BoundsCheck /// CHECK-NOT: Deoptimize @@ -770,6 +886,55 @@ public class Main { } while (-1 <= i); } + /// CHECK-START: int[] Main.multiply1() BCE (before) + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: ArrayGet + /// CHECK-DAG: ArraySet + // + /// CHECK-START: int[] Main.multiply1() BCE (after) + /// CHECK-NOT: BoundsCheck + /// CHECK-DAG: ArrayGet + /// CHECK-DAG: ArraySet + /// CHECK-NOT: Deoptimize + private static int[] multiply1() { + int[] a = new int[10]; + try { + for (int i = 0; i <= 3; i++) { + for (int j = 0; j <= 3; j++) { + // Range [0,9]: safe. + a[i * j] += 1; + } + } + } catch (Exception e) { + a[0] += 1000; + } + return a; + } + + /// CHECK-START: int[] Main.multiply2() BCE (before) + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: ArrayGet + /// CHECK-DAG: ArraySet + // + /// CHECK-START: int[] Main.multiply2() BCE (after) + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: ArrayGet + /// CHECK-DAG: ArraySet + static int[] multiply2() { + int[] a = new int[10]; + try { + for (int i = -3; i <= 3; i++) { + for (int j = -3; j <= 3; j++) { + // Range [-9,9]: unsafe. + a[i * j] += 1; + } + } + } catch (Exception e) { + a[0] += 1000; + } + return a; + } + /// CHECK-START: int Main.linearDynamicBCE1(int[], int, int) BCE (before) /// CHECK-DAG: StaticFieldGet /// CHECK-DAG: NullCheck @@ -777,6 +942,7 @@ public class Main { /// CHECK-DAG: BoundsCheck /// CHECK-DAG: ArrayGet /// CHECK-DAG: StaticFieldSet + // /// CHECK-START: int Main.linearDynamicBCE1(int[], int, int) BCE (after) /// CHECK-DAG: StaticFieldGet /// CHECK-NOT: NullCheck @@ -803,6 +969,7 @@ public class Main { /// CHECK-DAG: BoundsCheck /// CHECK-DAG: ArrayGet /// CHECK-DAG: StaticFieldSet + // /// CHECK-START: int Main.linearDynamicBCE2(int[], int, int, int) BCE (after) /// CHECK-DAG: StaticFieldGet /// CHECK-NOT: NullCheck @@ -827,6 +994,7 @@ public class Main { /// CHECK-DAG: ArrayLength /// CHECK-DAG: BoundsCheck /// CHECK-DAG: ArrayGet + // /// CHECK-START: int Main.wrapAroundDynamicBCE(int[]) BCE (after) /// CHECK-DAG: Deoptimize /// CHECK-DAG: Deoptimize @@ -850,6 +1018,7 @@ public class Main { /// CHECK-DAG: ArrayLength /// CHECK-DAG: BoundsCheck /// CHECK-DAG: ArrayGet + // /// CHECK-START: int Main.periodicDynamicBCE(int[]) BCE (after) /// CHECK-DAG: Deoptimize /// CHECK-DAG: Deoptimize @@ -873,6 +1042,7 @@ public class Main { /// CHECK-DAG: ArrayLength /// CHECK-DAG: BoundsCheck /// CHECK-DAG: ArrayGet + // /// CHECK-START: int Main.dynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (after) /// CHECK-NOT: NullCheck /// CHECK-NOT: ArrayLength @@ -897,6 +1067,7 @@ public class Main { /// CHECK-DAG: ArrayLength /// CHECK-DAG: BoundsCheck /// CHECK-DAG: ArrayGet + // /// CHECK-START: int Main.noDynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (after) /// CHECK-DAG: NullCheck /// CHECK-DAG: ArrayLength @@ -918,6 +1089,7 @@ public class Main { /// CHECK-DAG: ArrayLength /// CHECK-DAG: BoundsCheck /// CHECK-DAG: ArrayGet + // /// CHECK-START: int Main.noDynamicBCEMixedInductionTypes(int[], long, long) BCE (after) /// CHECK-DAG: NullCheck /// CHECK-DAG: ArrayLength @@ -951,6 +1123,7 @@ public class Main { /// CHECK-DAG: BoundsCheck /// CHECK-DAG: BoundsCheck /// CHECK-DAG: BoundsCheck + // /// CHECK-START: int Main.dynamicBCEAndConstantIndices(int[], int[][], int, int) BCE (after) /// CHECK-DAG: NullCheck /// CHECK-DAG: ArrayLength @@ -1015,6 +1188,7 @@ public class Main { /// CHECK-DAG: ArrayGet /// CHECK-DAG: BoundsCheck /// CHECK-DAG: ArrayGet + // /// CHECK-START: int Main.dynamicBCEAndConstantIndicesAllTypes(int[], boolean[], byte[], char[], short[], int[], long[], float[], double[], java.lang.Integer[], int, int) BCE (after) /// CHECK-DAG: If /// CHECK-NOT: BoundsCheck @@ -1087,6 +1261,8 @@ public class Main { expectEquals(55, linearObscure(x)); expectEquals(0, linearVeryObscure(empty)); expectEquals(55, linearVeryObscure(x)); + expectEquals(0, hiddenStride(empty)); + expectEquals(55, hiddenStride(x)); expectEquals(0, linearWhile(empty)); expectEquals(55, linearWhile(x)); expectEquals(0, linearThreeWayPhi(empty)); @@ -1144,6 +1320,7 @@ public class Main { linearTriangularOnTwoArrayLengths(10); linearTriangularOnOneArrayLength(10); linearTriangularOnParameter(10); + linearTriangularVariations(10); // Sorting. int[] sort = { 5, 4, 1, 9, 10, 2, 7, 6, 3, 8 }; @@ -1234,6 +1411,20 @@ public class Main { } expectEquals(1055, sResult); + // Multiplication. + { + int[] e1 = { 7, 1, 2, 2, 1, 0, 2, 0, 0, 1 }; + int[] a1 = multiply1(); + for (int i = 0; i < 10; i++) { + expectEquals(a1[i], e1[i]); + } + int[] e2 = { 1001, 0, 0, 1, 0, 0, 1, 0, 0, 1 }; + int[] a2 = multiply2(); + for (int i = 0; i < 10; i++) { + expectEquals(a2[i], e2[i]); + } + } + // Dynamic BCE. sResult = 0; try { diff --git a/test/530-checker-lse/src/Main.java b/test/530-checker-lse/src/Main.java index ced3e50d41..98251e4af3 100644 --- a/test/530-checker-lse/src/Main.java +++ b/test/530-checker-lse/src/Main.java @@ -453,14 +453,16 @@ public class Main { } /// CHECK-START: float Main.test19(float[], float[]) load_store_elimination (before) - /// CHECK: {{f\d+}} ArrayGet - /// CHECK: {{f\d+}} ArrayGet + /// CHECK: <<IntTypeValue:i\d+>> ArrayGet + /// CHECK: ArraySet + /// CHECK: <<FloatTypeValue:f\d+>> ArrayGet /// CHECK-START: float Main.test19(float[], float[]) load_store_elimination (after) - /// CHECK: {{f\d+}} ArrayGet - /// CHECK-NOT: {{f\d+}} ArrayGet + /// CHECK: <<IntTypeValue:i\d+>> ArrayGet + /// CHECK: ArraySet + /// CHECK: <<FloatTypeValue:f\d+>> ArrayGet - // I/F, J/D aliasing should not happen any more and LSE should eliminate the load. + // I/F, J/D aliasing should keep the load/store. static float test19(float[] fa1, float[] fa2) { fa1[0] = fa2[0]; return fa1[0]; diff --git a/test/540-checker-rtp-bug/src/Main.java b/test/540-checker-rtp-bug/src/Main.java index 9a9f0b6048..e9f16c04d9 100644 --- a/test/540-checker-rtp-bug/src/Main.java +++ b/test/540-checker-rtp-bug/src/Main.java @@ -21,14 +21,14 @@ final class Final { } public class Main { - /// CHECK-START: Final Main.testKeepCheckCast(java.lang.Object, boolean) ssa_builder (after) + /// CHECK-START: Final Main.testKeepCheckCast(java.lang.Object, boolean) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:java.lang.Object /// CHECK: <<Class:l\d+>> LoadClass /// CHECK: CheckCast [<<Phi>>,<<Class>>] /// CHECK: <<Ret:l\d+>> BoundType [<<Phi>>] klass:Final /// CHECK: Return [<<Ret>>] - /// CHECK-START: Final Main.testKeepCheckCast(java.lang.Object, boolean) instruction_simplifier (after) + /// CHECK-START: Final Main.testKeepCheckCast(java.lang.Object, boolean) instruction_simplifier_after_types (after) /// CHECK: <<Phi:l\d+>> Phi /// CHECK: <<Class:l\d+>> LoadClass /// CHECK: CheckCast [<<Phi>>,<<Class>>] @@ -43,7 +43,7 @@ public class Main { return (Final) x; } - /// CHECK-START: void Main.testKeepInstanceOf(java.lang.Object, boolean) ssa_builder (after) + /// CHECK-START: void Main.testKeepInstanceOf(java.lang.Object, boolean) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:java.lang.Object /// CHECK: <<Class:l\d+>> LoadClass /// CHECK: InstanceOf [<<Phi>>,<<Class>>] @@ -65,7 +65,7 @@ public class Main { } } - /// CHECK-START: java.lang.String Main.testNoInline(java.lang.Object, boolean) ssa_builder (after) + /// CHECK-START: java.lang.String Main.testNoInline(java.lang.Object, boolean) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:java.lang.Object /// CHECK: <<NC:l\d+>> NullCheck [<<Phi>>] /// CHECK: <<Ret:l\d+>> InvokeVirtual [<<NC>>] method_name:java.lang.Object.toString diff --git a/test/549-checker-types-merge/src/Main.java b/test/549-checker-types-merge/src/Main.java index 917073b1c9..dc27f10427 100644 --- a/test/549-checker-types-merge/src/Main.java +++ b/test/549-checker-types-merge/src/Main.java @@ -38,14 +38,14 @@ class ClassImplementsInterfaceA extends ClassSuper implements InterfaceA {} public class Main { - /// CHECK-START: java.lang.Object Main.testMergeNullContant(boolean) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.testMergeNullContant(boolean) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:Main /// CHECK: Return [<<Phi>>] private Object testMergeNullContant(boolean cond) { return cond ? null : new Main(); } - /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassExtendsA, ClassExtendsB) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassExtendsA, ClassExtendsB) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:ClassSuper /// CHECK: Return [<<Phi>>] private Object testMergeClasses(boolean cond, ClassExtendsA a, ClassExtendsB b) { @@ -53,7 +53,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassExtendsA, ClassSuper) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassExtendsA, ClassSuper) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:ClassSuper /// CHECK: Return [<<Phi>>] private Object testMergeClasses(boolean cond, ClassExtendsA a, ClassSuper b) { @@ -61,7 +61,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassSuper, ClassSuper) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassSuper, ClassSuper) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:ClassSuper /// CHECK: Return [<<Phi>>] private Object testMergeClasses(boolean cond, ClassSuper a, ClassSuper b) { @@ -69,7 +69,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassOtherSuper, ClassSuper) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassOtherSuper, ClassSuper) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:java.lang.Object /// CHECK: Return [<<Phi>>] private Object testMergeClasses(boolean cond, ClassOtherSuper a, ClassSuper b) { @@ -77,7 +77,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeClassWithInterface(boolean, ClassImplementsInterfaceA, InterfaceSuper) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.testMergeClassWithInterface(boolean, ClassImplementsInterfaceA, InterfaceSuper) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:InterfaceSuper /// CHECK: Return [<<Phi>>] private Object testMergeClassWithInterface(boolean cond, ClassImplementsInterfaceA a, InterfaceSuper b) { @@ -85,7 +85,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeClassWithInterface(boolean, ClassSuper, InterfaceSuper) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.testMergeClassWithInterface(boolean, ClassSuper, InterfaceSuper) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:java.lang.Object /// CHECK: Return [<<Phi>>] private Object testMergeClassWithInterface(boolean cond, ClassSuper a, InterfaceSuper b) { @@ -93,7 +93,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceExtendsA, InterfaceSuper) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceExtendsA, InterfaceSuper) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:InterfaceSuper /// CHECK: Return [<<Phi>>] private Object testMergeInterfaces(boolean cond, InterfaceExtendsA a, InterfaceSuper b) { @@ -101,7 +101,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceSuper, InterfaceSuper) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceSuper, InterfaceSuper) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:InterfaceSuper /// CHECK: Return [<<Phi>>] private Object testMergeInterfaces(boolean cond, InterfaceSuper a, InterfaceSuper b) { @@ -109,7 +109,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceExtendsA, InterfaceExtendsB) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceExtendsA, InterfaceExtendsB) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:java.lang.Object /// CHECK: Return [<<Phi>>] private Object testMergeInterfaces(boolean cond, InterfaceExtendsA a, InterfaceExtendsB b) { @@ -117,7 +117,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceSuper, InterfaceOtherSuper) ssa_builder (after) + /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceSuper, InterfaceOtherSuper) reference_type_propagation (after) /// CHECK: <<Phi:l\d+>> Phi klass:java.lang.Object /// CHECK: Return [<<Phi>>] private Object testMergeInterfaces(boolean cond, InterfaceSuper a, InterfaceOtherSuper b) { diff --git a/test/552-checker-primitive-typeprop/expected.txt b/test/552-checker-primitive-typeprop/expected.txt deleted file mode 100644 index e69de29bb2..0000000000 --- a/test/552-checker-primitive-typeprop/expected.txt +++ /dev/null diff --git a/test/552-checker-primitive-typeprop/info.txt b/test/552-checker-primitive-typeprop/info.txt deleted file mode 100644 index 9d69056915..0000000000 --- a/test/552-checker-primitive-typeprop/info.txt +++ /dev/null @@ -1,2 +0,0 @@ -Test that phis with environment uses which can be properly typed are kept -in --debuggable mode.
\ No newline at end of file diff --git a/test/552-checker-primitive-typeprop/smali/ArrayGet.smali b/test/552-checker-primitive-typeprop/smali/ArrayGet.smali deleted file mode 100644 index 042fa0c80c..0000000000 --- a/test/552-checker-primitive-typeprop/smali/ArrayGet.smali +++ /dev/null @@ -1,245 +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. - -.class public LArrayGet; -.super Ljava/lang/Object; - - -# Test phi with fixed-type ArrayGet as an input and a matching second input. -# The phi should be typed accordingly. - -## CHECK-START: void ArrayGet.matchingFixedType(float[], float) ssa_builder (after) -## CHECK-NOT: Phi - -## CHECK-START-DEBUGGABLE: void ArrayGet.matchingFixedType(float[], float) ssa_builder (after) -## CHECK-DAG: <<Arg1:f\d+>> ParameterValue -## CHECK-DAG: <<Aget:f\d+>> ArrayGet -## CHECK-DAG: {{f\d+}} Phi [<<Aget>>,<<Arg1>>] reg:0 -.method public static matchingFixedType([FF)V - .registers 8 - - const v0, 0x0 - const v1, 0x1 - - aget v0, p0, v0 # read value - add-float v2, v0, v1 # float use fixes type - - float-to-int v2, p1 - if-eqz v2, :after - move v0, p1 - :after - # v0 = Phi [ArrayGet, Arg1] => float - - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method - - -# Test phi with fixed-type ArrayGet as an input and a conflicting second input. -# The phi should be eliminated due to the conflict. - -## CHECK-START: void ArrayGet.conflictingFixedType(float[], int) ssa_builder (after) -## CHECK-NOT: Phi - -## CHECK-START-DEBUGGABLE: void ArrayGet.conflictingFixedType(float[], int) ssa_builder (after) -## CHECK-NOT: Phi -.method public static conflictingFixedType([FI)V - .registers 8 - - const v0, 0x0 - const v1, 0x1 - - aget v0, p0, v0 # read value - add-float v2, v0, v1 # float use fixes type - - if-eqz p1, :after - move v0, p1 - :after - # v0 = Phi [ArrayGet, Arg1] => conflict - - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method - - -# Same test as the one above, only this time tests that type of ArrayGet is not -# changed. - -## CHECK-START: void ArrayGet.conflictingFixedType2(int[], float) ssa_builder (after) -## CHECK-NOT: Phi - -## CHECK-START-DEBUGGABLE: void ArrayGet.conflictingFixedType2(int[], float) ssa_builder (after) -## CHECK-NOT: Phi - -## CHECK-START-DEBUGGABLE: void ArrayGet.conflictingFixedType2(int[], float) ssa_builder (after) -## CHECK: {{i\d+}} ArrayGet -.method public static conflictingFixedType2([IF)V - .registers 8 - - const v0, 0x0 - const v1, 0x1 - - aget v0, p0, v0 # read value - add-int v2, v0, v1 # int use fixes type - - float-to-int v2, p1 - if-eqz v2, :after - move v0, p1 - :after - # v0 = Phi [ArrayGet, Arg1] => conflict - - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method - - -# Test phi with free-type ArrayGet as an input and a matching second input. -# The phi should be typed accordingly. - -## CHECK-START: void ArrayGet.matchingFreeType(float[], float) ssa_builder (after) -## CHECK-NOT: Phi - -## CHECK-START-DEBUGGABLE: void ArrayGet.matchingFreeType(float[], float) ssa_builder (after) -## CHECK-DAG: <<Arg1:f\d+>> ParameterValue -## CHECK-DAG: <<Aget:f\d+>> ArrayGet -## CHECK-DAG: ArraySet [{{l\d+}},{{i\d+}},<<Aget>>] -## CHECK-DAG: {{f\d+}} Phi [<<Aget>>,<<Arg1>>] reg:0 -.method public static matchingFreeType([FF)V - .registers 8 - - const v0, 0x0 - const v1, 0x1 - - aget v0, p0, v0 # read value, should be float but has no typed use - aput v0, p0, v1 # aput does not disambiguate the type - - float-to-int v2, p1 - if-eqz v2, :after - move v0, p1 - :after - # v0 = Phi [ArrayGet, Arg1] => float - - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method - - -# Test phi with free-type ArrayGet as an input and a conflicting second input. -# The phi will be kept and typed according to the second input despite the -# conflict. - -## CHECK-START: void ArrayGet.conflictingFreeType(int[], float) ssa_builder (after) -## CHECK-NOT: Phi - -## CHECK-START-DEBUGGABLE: void ArrayGet.conflictingFreeType(int[], float) ssa_builder (after) -## CHECK-NOT: Phi - -.method public static conflictingFreeType([IF)V - .registers 8 - - const v0, 0x0 - const v1, 0x1 - - aget v0, p0, v0 # read value, should be int but has no typed use - aput v0, p0, v1 - - float-to-int v2, p1 - if-eqz v2, :after - move v0, p1 - :after - # v0 = Phi [ArrayGet, Arg1] => float - - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method - - -# Test that real use of ArrayGet is propagated through phis. The following test -# case uses ArrayGet indirectly through two phis. It also creates an unused -# conflicting phi which should not be preserved. - -## CHECK-START: void ArrayGet.conflictingPhiUses(int[], float, boolean, boolean, boolean) ssa_builder (after) -## CHECK: InvokeStaticOrDirect env:[[{{i\d+}},{{i\d+}},_,{{i\d+}},{{.*}} - -.method public static conflictingPhiUses([IFZZZ)V - .registers 10 - - const v0, 0x0 - - # Create v1 = Phi [0x0, int ArrayGet] - move v1, v0 - if-eqz p2, :else1 - aget v1, p0, v0 - :else1 - - # Create v2 = Phi [v1, float] - move v2, v1 - if-eqz p3, :else2 - move v2, p1 - :else2 - - # Create v3 = Phi [v1, int] - move v3, v1 - if-eqz p4, :else3 - move v3, v0 - :else3 - - # Use v3 as int. - add-int/lit8 v4, v3, 0x2a - - # Create env uses. - invoke-static {}, Ljava/lang/System;->nanoTime()J - - return-void -.end method - -# Test that the right ArrayGet equivalent is always selected. The following test -# case uses ArrayGet as float through one phi and as an indeterminate type through -# another. The situation needs to be resolved so that only one instruction -# remains. - -## CHECK-START: void ArrayGet.typedVsUntypedPhiUse(float[], float, boolean, boolean) ssa_builder (after) -## CHECK: {{f\d+}} ArrayGet - -## CHECK-START: void ArrayGet.typedVsUntypedPhiUse(float[], float, boolean, boolean) ssa_builder (after) -## CHECK-NOT: {{i\d+}} ArrayGet - -.method public static typedVsUntypedPhiUse([FFZZ)V - .registers 10 - - const v0, 0x0 - - # v1 = float ArrayGet - aget v1, p0, v0 - - # Create v2 = Phi [v1, 0.0f] - move v2, v1 - if-eqz p2, :else1 - move v2, v0 - :else1 - - # Use v2 as float - cmpl-float v2, v2, p1 - - # Create v3 = Phi [v1, 0.0f] - move v3, v1 - if-eqz p3, :else2 - move v3, v0 - :else2 - - # Use v3 without a determinate type. - aput v3, p0, v0 - - return-void -.end method diff --git a/test/552-checker-primitive-typeprop/smali/SsaBuilder.smali b/test/552-checker-primitive-typeprop/smali/SsaBuilder.smali deleted file mode 100644 index 395feaaf61..0000000000 --- a/test/552-checker-primitive-typeprop/smali/SsaBuilder.smali +++ /dev/null @@ -1,52 +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. - -.class public LSsaBuilder; -.super Ljava/lang/Object; - -# Check that a dead phi with a live equivalent is replaced in an environment. The -# following test case throws an exception and uses v0 afterwards. However, v0 -# contains a phi that is interpreted as int for the environment, and as float for -# instruction use. SsaBuilder must substitute the int variant before removing it, -# otherwise running the code with an array short enough to throw will crash at -# runtime because v0 is undefined. - -## CHECK-START: int SsaBuilder.environmentPhi(boolean, int[]) ssa_builder (after) -## CHECK-DAG: <<Cst0:f\d+>> FloatConstant 0 -## CHECK-DAG: <<Cst2:f\d+>> FloatConstant 2 -## CHECK-DAG: <<Phi:f\d+>> Phi [<<Cst0>>,<<Cst2>>] -## CHECK-DAG: BoundsCheck env:[[<<Phi>>,{{i\d+}},{{z\d+}},{{l\d+}}]] - -.method public static environmentPhi(Z[I)I - .registers 4 - - const v0, 0x0 - if-eqz p0, :else - const v0, 0x40000000 - :else - # v0 = phi that can be both int and float - - :try_start - const v1, 0x3 - aput v1, p1, v1 - const v0, 0x1 # generate catch phi for v0 - const v1, 0x4 - aput v1, p1, v1 - :try_end - .catchall {:try_start .. :try_end} :use_as_float - - :use_as_float - float-to-int v0, v0 - return v0 -.end method
\ No newline at end of file diff --git a/test/552-checker-primitive-typeprop/smali/TypePropagation.smali b/test/552-checker-primitive-typeprop/smali/TypePropagation.smali deleted file mode 100644 index 58682a1923..0000000000 --- a/test/552-checker-primitive-typeprop/smali/TypePropagation.smali +++ /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. - -.class public LTypePropagation; -.super Ljava/lang/Object; - -## CHECK-START-DEBUGGABLE: void TypePropagation.mergeDeadPhi(boolean, boolean, int, float, float) ssa_builder (after) -## CHECK-NOT: Phi -.method public static mergeDeadPhi(ZZIFF)V - .registers 8 - - if-eqz p0, :after1 - move p2, p3 - :after1 - # p2 = merge(int,float) = conflict - - if-eqz p1, :after2 - move p2, p4 - :after2 - # p2 = merge(conflict,float) = conflict - - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method - -## CHECK-START-DEBUGGABLE: void TypePropagation.mergeSameType(boolean, int, int) ssa_builder (after) -## CHECK: {{i\d+}} Phi -## CHECK-NOT: Phi -.method public static mergeSameType(ZII)V - .registers 8 - if-eqz p0, :after - move p1, p2 - :after - # p1 = merge(int,int) = int - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method - -## CHECK-START-DEBUGGABLE: void TypePropagation.mergeVoidInput(boolean, boolean, int, int) ssa_builder (after) -## CHECK: {{i\d+}} Phi -## CHECK: {{i\d+}} Phi -## CHECK-NOT: Phi -.method public static mergeVoidInput(ZZII)V - .registers 8 - :loop - # p2 = void (loop phi) => p2 = merge(int,int) = int - if-eqz p0, :after - move p2, p3 - :after - # p2 = merge(void,int) = int - if-eqz p1, :loop - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method - -## CHECK-START-DEBUGGABLE: void TypePropagation.mergeDifferentSize(boolean, int, long) ssa_builder (after) -## CHECK-NOT: Phi -.method public static mergeDifferentSize(ZIJ)V - .registers 8 - if-eqz p0, :after - move-wide p1, p2 - :after - # p1 = merge(int,long) = conflict - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method - -## CHECK-START-DEBUGGABLE: void TypePropagation.mergeRefFloat(boolean, float, java.lang.Object) ssa_builder (after) -## CHECK-NOT: Phi -.method public static mergeRefFloat(ZFLjava/lang/Object;)V - .registers 8 - if-eqz p0, :after - move-object p1, p2 - :after - # p1 = merge(float,reference) = conflict - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method - -## CHECK-START-DEBUGGABLE: void TypePropagation.mergeIntFloat_Success(boolean, float) ssa_builder (after) -## CHECK: {{f\d+}} Phi -## CHECK-NOT: Phi -.method public static mergeIntFloat_Success(ZF)V - .registers 8 - if-eqz p0, :after - const/4 p1, 0x0 - :after - # p1 = merge(float,0x0) = float - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method - -## CHECK-START-DEBUGGABLE: void TypePropagation.mergeIntFloat_Fail(boolean, int, float) ssa_builder (after) -## CHECK-NOT: Phi -.method public static mergeIntFloat_Fail(ZIF)V - .registers 8 - if-eqz p0, :after - move p1, p2 - :after - # p1 = merge(int,float) = conflict - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method - -## CHECK-START-DEBUGGABLE: void TypePropagation.updateAllUsersOnConflict(boolean, boolean, int, float, int) ssa_builder (after) -## CHECK-NOT: Phi -.method public static updateAllUsersOnConflict(ZZIFI)V - .registers 8 - - :loop1 - # loop phis for all args - # p2 = merge(int,float) = float? => conflict - move p2, p3 - if-eqz p0, :loop1 - - :loop2 - # loop phis for all args - # requests float equivalent of p4 phi in loop1 => conflict - # propagates conflict to loop2's phis - move p2, p4 - if-eqz p1, :loop2 - - invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use - return-void -.end method diff --git a/test/552-checker-primitive-typeprop/src/Main.java b/test/552-checker-primitive-typeprop/src/Main.java deleted file mode 100644 index fe2343e48a..0000000000 --- a/test/552-checker-primitive-typeprop/src/Main.java +++ /dev/null @@ -1,43 +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. - */ - -import java.lang.reflect.Method; - -public class Main { - - // Workaround for b/18051191. - class InnerClass {} - - private static void assertEquals(int expected, int actual) { - if (expected != actual) { - throw new Error("Wrong result, expected=" + expected + ", actual=" + actual); - } - } - - public static void main(String[] args) throws Exception { - Class<?> c = Class.forName("SsaBuilder"); - Method m = c.getMethod("environmentPhi", new Class[] { boolean.class, int[].class }); - - int[] array = new int[3]; - int result; - - result = (Integer) m.invoke(null, new Object[] { true, array } ); - assertEquals(2, result); - - result = (Integer) m.invoke(null, new Object[] { false, array } ); - assertEquals(0, result); - } -} diff --git a/test/run-test b/test/run-test index 6e13b8a976..60e008c8bb 100755 --- a/test/run-test +++ b/test/run-test @@ -41,7 +41,7 @@ else fi checker="${progdir}/../tools/checker/checker.py" export JAVA="java" -export JAVAC="javac -g" +export JAVAC="javac -g -source 1.7 -target 1.7 -Xlint:-options" export RUN="${progdir}/etc/run-test-jar" export DEX_LOCATION=/data/run-test/${test_dir} export NEED_DEX="true" |