diff options
Diffstat (limited to 'compiler/optimizing')
40 files changed, 1946 insertions, 362 deletions
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc index 4a4b98cc48..5152075499 100644 --- a/compiler/optimizing/code_generator.cc +++ b/compiler/optimizing/code_generator.cc @@ -765,16 +765,24 @@ void CodeGenerator::RecordPcInfo(HInstruction* instruction, LocationSummary* locations = instruction->GetLocations(); uint32_t register_mask = locations->GetRegisterMask(); - if (locations->OnlyCallsOnSlowPath()) { - // In case of slow path, we currently set the location of caller-save registers - // to register (instead of their stack location when pushed before the slow-path - // call). Therefore register_mask contains both callee-save and caller-save - // registers that hold objects. We must remove the caller-save from the mask, since - // they will be overwritten by the callee. - register_mask &= core_callee_save_mask_; + if (instruction->IsSuspendCheck()) { + // Suspend check has special ABI that saves the caller-save registers in callee, + // so we want to emit stack maps containing the registers. + // TODO: Register allocator still reserves space for the caller-save registers. + // We should add slow-path-specific caller-save information into LocationSummary + // and refactor the code here as well as in the register allocator to use it. + } else { + if (locations->OnlyCallsOnSlowPath()) { + // In case of slow path, we currently set the location of caller-save registers + // to register (instead of their stack location when pushed before the slow-path + // call). Therefore register_mask contains both callee-save and caller-save + // registers that hold objects. We must remove the caller-save from the mask, since + // they will be overwritten by the callee. + register_mask &= core_callee_save_mask_; + } + // The register mask must be a subset of callee-save registers. + DCHECK_EQ(register_mask & core_callee_save_mask_, register_mask); } - // The register mask must be a subset of callee-save registers. - DCHECK_EQ(register_mask & core_callee_save_mask_, register_mask); stack_map_stream_.BeginStackMapEntry(outer_dex_pc, native_pc, register_mask, @@ -1174,7 +1182,7 @@ void CodeGenerator::ValidateInvokeRuntime(HInstruction* instruction, SlowPathCod << "instruction->DebugName()=" << instruction->DebugName() << " instruction->GetSideEffects().ToString()=" << instruction->GetSideEffects().ToString(); } else { - DCHECK(instruction->GetLocations()->OnlyCallsOnSlowPath() || slow_path->IsFatal()) + DCHECK(instruction->GetLocations()->CallsOnSlowPath() || slow_path->IsFatal()) << "instruction->DebugName()=" << instruction->DebugName() << " slow_path->GetDescription()=" << slow_path->GetDescription(); DCHECK(instruction->GetSideEffects().Includes(SideEffects::CanTriggerGC()) || diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h index ad02ecf609..fd396c474c 100644 --- a/compiler/optimizing/code_generator.h +++ b/compiler/optimizing/code_generator.h @@ -340,6 +340,9 @@ class CodeGenerator : public DeletableArenaObject<kArenaAllocCodeGenerator> { bool* GetBlockedCoreRegisters() const { return blocked_core_registers_; } bool* GetBlockedFloatingPointRegisters() const { return blocked_fpu_registers_; } + bool IsBlockedCoreRegister(size_t i) { return blocked_core_registers_[i]; } + bool IsBlockedFloatingPointRegister(size_t i) { return blocked_fpu_registers_[i]; } + // Helper that returns the pointer offset of an index in an object array. // Note: this method assumes we always have the same pointer size, regardless // of the architecture. diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc index c18b79394c..ab85c12a1d 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -119,11 +119,9 @@ class SuspendCheckSlowPathARM : public SlowPathCode { void EmitNativeCode(CodeGenerator* codegen) OVERRIDE { CodeGeneratorARM* arm_codegen = down_cast<CodeGeneratorARM*>(codegen); __ Bind(GetEntryLabel()); - SaveLiveRegisters(codegen, instruction_->GetLocations()); arm_codegen->InvokeRuntime( QUICK_ENTRY_POINT(pTestSuspend), instruction_, instruction_->GetDexPc(), this); CheckEntrypointTypes<kQuickTestSuspend, void, void>(); - RestoreLiveRegisters(codegen, instruction_->GetLocations()); if (successor_ == nullptr) { __ b(GetReturnLabel()); } else { @@ -434,6 +432,11 @@ class ReadBarrierMarkSlowPathARM : public SlowPathCode { (instruction_->IsInvokeVirtual()) && instruction_->GetLocations()->Intrinsified()) << "Unexpected instruction in read barrier marking slow path: " << instruction_->DebugName(); + // The read barrier instrumentation of object ArrayGet + // instructions does not support the HIntermediateAddress + // instruction. + DCHECK(!(instruction_->IsArrayGet() && + instruction_->AsArrayGet()->GetArray()->IsIntermediateAddress())); __ Bind(GetEntryLabel()); // No need to save live registers; it's taken care of by the @@ -514,6 +517,11 @@ class ReadBarrierForHeapReferenceSlowPathARM : public SlowPathCode { (instruction_->IsInvokeVirtual()) && instruction_->GetLocations()->Intrinsified()) << "Unexpected instruction in read barrier for heap reference slow path: " << instruction_->DebugName(); + // The read barrier instrumentation of object ArrayGet + // instructions does not support the HIntermediateAddress + // instruction. + DCHECK(!(instruction_->IsArrayGet() && + instruction_->AsArrayGet()->GetArray()->IsIntermediateAddress())); __ Bind(GetEntryLabel()); SaveLiveRegisters(codegen, locations); @@ -1289,6 +1297,44 @@ void LocationsBuilderARM::VisitExit(HExit* exit) { void InstructionCodeGeneratorARM::VisitExit(HExit* exit ATTRIBUTE_UNUSED) { } +void InstructionCodeGeneratorARM::GenerateVcmp(HInstruction* instruction) { + Primitive::Type type = instruction->InputAt(0)->GetType(); + Location lhs_loc = instruction->GetLocations()->InAt(0); + Location rhs_loc = instruction->GetLocations()->InAt(1); + if (rhs_loc.IsConstant()) { + // 0.0 is the only immediate that can be encoded directly in + // a VCMP instruction. + // + // Both the JLS (section 15.20.1) and the JVMS (section 6.5) + // specify that in a floating-point comparison, positive zero + // and negative zero are considered equal, so we can use the + // literal 0.0 for both cases here. + // + // Note however that some methods (Float.equal, Float.compare, + // Float.compareTo, Double.equal, Double.compare, + // Double.compareTo, Math.max, Math.min, StrictMath.max, + // StrictMath.min) consider 0.0 to be (strictly) greater than + // -0.0. So if we ever translate calls to these methods into a + // HCompare instruction, we must handle the -0.0 case with + // care here. + DCHECK(rhs_loc.GetConstant()->IsArithmeticZero()); + if (type == Primitive::kPrimFloat) { + __ vcmpsz(lhs_loc.AsFpuRegister<SRegister>()); + } else { + DCHECK_EQ(type, Primitive::kPrimDouble); + __ vcmpdz(FromLowSToD(lhs_loc.AsFpuRegisterPairLow<SRegister>())); + } + } else { + if (type == Primitive::kPrimFloat) { + __ vcmps(lhs_loc.AsFpuRegister<SRegister>(), rhs_loc.AsFpuRegister<SRegister>()); + } else { + DCHECK_EQ(type, Primitive::kPrimDouble); + __ vcmpd(FromLowSToD(lhs_loc.AsFpuRegisterPairLow<SRegister>()), + FromLowSToD(rhs_loc.AsFpuRegisterPairLow<SRegister>())); + } + } +} + void InstructionCodeGeneratorARM::GenerateFPJumps(HCondition* cond, Label* true_label, Label* false_label ATTRIBUTE_UNUSED) { @@ -1389,22 +1435,14 @@ void InstructionCodeGeneratorARM::GenerateCompareTestAndBranch(HCondition* condi Label* true_target = true_target_in == nullptr ? &fallthrough_target : true_target_in; Label* false_target = false_target_in == nullptr ? &fallthrough_target : false_target_in; - LocationSummary* locations = condition->GetLocations(); - Location left = locations->InAt(0); - Location right = locations->InAt(1); - Primitive::Type type = condition->InputAt(0)->GetType(); switch (type) { case Primitive::kPrimLong: GenerateLongComparesAndJumps(condition, true_target, false_target); break; case Primitive::kPrimFloat: - __ vcmps(left.AsFpuRegister<SRegister>(), right.AsFpuRegister<SRegister>()); - GenerateFPJumps(condition, true_target, false_target); - break; case Primitive::kPrimDouble: - __ vcmpd(FromLowSToD(left.AsFpuRegisterPairLow<SRegister>()), - FromLowSToD(right.AsFpuRegisterPairLow<SRegister>())); + GenerateVcmp(condition); GenerateFPJumps(condition, true_target, false_target); break; default: @@ -1585,7 +1623,7 @@ void LocationsBuilderARM::HandleCondition(HCondition* cond) { case Primitive::kPrimFloat: case Primitive::kPrimDouble: locations->SetInAt(0, Location::RequiresFpuRegister()); - locations->SetInAt(1, Location::RequiresFpuRegister()); + locations->SetInAt(1, ArithmeticZeroOrFpuRegister(cond->InputAt(1))); if (!cond->IsEmittedAtUseSite()) { locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } @@ -1632,12 +1670,8 @@ void InstructionCodeGeneratorARM::HandleCondition(HCondition* cond) { GenerateLongComparesAndJumps(cond, &true_label, &false_label); break; case Primitive::kPrimFloat: - __ vcmps(left.AsFpuRegister<SRegister>(), right.AsFpuRegister<SRegister>()); - GenerateFPJumps(cond, &true_label, &false_label); - break; case Primitive::kPrimDouble: - __ vcmpd(FromLowSToD(left.AsFpuRegisterPairLow<SRegister>()), - FromLowSToD(right.AsFpuRegisterPairLow<SRegister>())); + GenerateVcmp(cond); GenerateFPJumps(cond, &true_label, &false_label); break; } @@ -2497,7 +2531,7 @@ void LocationsBuilderARM::VisitAdd(HAdd* add) { case Primitive::kPrimLong: { locations->SetInAt(0, Location::RequiresRegister()); - locations->SetInAt(1, Location::RequiresRegister()); + locations->SetInAt(1, ArmEncodableConstantOrRegister(add->InputAt(1), ADD)); locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); break; } @@ -2534,13 +2568,18 @@ void InstructionCodeGeneratorARM::VisitAdd(HAdd* add) { break; case Primitive::kPrimLong: { - DCHECK(second.IsRegisterPair()); - __ adds(out.AsRegisterPairLow<Register>(), - first.AsRegisterPairLow<Register>(), - ShifterOperand(second.AsRegisterPairLow<Register>())); - __ adc(out.AsRegisterPairHigh<Register>(), - first.AsRegisterPairHigh<Register>(), - ShifterOperand(second.AsRegisterPairHigh<Register>())); + if (second.IsConstant()) { + uint64_t value = static_cast<uint64_t>(Int64FromConstant(second.GetConstant())); + GenerateAddLongConst(out, first, value); + } else { + DCHECK(second.IsRegisterPair()); + __ adds(out.AsRegisterPairLow<Register>(), + first.AsRegisterPairLow<Register>(), + ShifterOperand(second.AsRegisterPairLow<Register>())); + __ adc(out.AsRegisterPairHigh<Register>(), + first.AsRegisterPairHigh<Register>(), + ShifterOperand(second.AsRegisterPairHigh<Register>())); + } break; } @@ -2574,7 +2613,7 @@ void LocationsBuilderARM::VisitSub(HSub* sub) { case Primitive::kPrimLong: { locations->SetInAt(0, Location::RequiresRegister()); - locations->SetInAt(1, Location::RequiresRegister()); + locations->SetInAt(1, ArmEncodableConstantOrRegister(sub->InputAt(1), SUB)); locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); break; } @@ -2610,13 +2649,18 @@ void InstructionCodeGeneratorARM::VisitSub(HSub* sub) { } case Primitive::kPrimLong: { - DCHECK(second.IsRegisterPair()); - __ subs(out.AsRegisterPairLow<Register>(), - first.AsRegisterPairLow<Register>(), - ShifterOperand(second.AsRegisterPairLow<Register>())); - __ sbc(out.AsRegisterPairHigh<Register>(), - first.AsRegisterPairHigh<Register>(), - ShifterOperand(second.AsRegisterPairHigh<Register>())); + if (second.IsConstant()) { + uint64_t value = static_cast<uint64_t>(Int64FromConstant(second.GetConstant())); + GenerateAddLongConst(out, first, -value); + } else { + DCHECK(second.IsRegisterPair()); + __ subs(out.AsRegisterPairLow<Register>(), + first.AsRegisterPairLow<Register>(), + ShifterOperand(second.AsRegisterPairLow<Register>())); + __ sbc(out.AsRegisterPairHigh<Register>(), + first.AsRegisterPairHigh<Register>(), + ShifterOperand(second.AsRegisterPairHigh<Register>())); + } break; } @@ -3654,7 +3698,7 @@ void LocationsBuilderARM::VisitCompare(HCompare* compare) { case Primitive::kPrimFloat: case Primitive::kPrimDouble: { locations->SetInAt(0, Location::RequiresFpuRegister()); - locations->SetInAt(1, Location::RequiresFpuRegister()); + locations->SetInAt(1, ArithmeticZeroOrFpuRegister(compare->InputAt(1))); locations->SetOut(Location::RequiresRegister()); break; } @@ -3699,12 +3743,7 @@ void InstructionCodeGeneratorARM::VisitCompare(HCompare* compare) { case Primitive::kPrimFloat: case Primitive::kPrimDouble: { __ LoadImmediate(out, 0); - if (type == Primitive::kPrimFloat) { - __ vcmps(left.AsFpuRegister<SRegister>(), right.AsFpuRegister<SRegister>()); - } else { - __ vcmpd(FromLowSToD(left.AsFpuRegisterPairLow<SRegister>()), - FromLowSToD(right.AsFpuRegisterPairLow<SRegister>())); - } + GenerateVcmp(compare); __ vmstat(); // transfer FP status register to ARM APSR. less_cond = ARMFPCondition(kCondLT, compare->IsGtBias()); break; @@ -3998,6 +4037,17 @@ void LocationsBuilderARM::HandleFieldGet(HInstruction* instruction, const FieldI } } +Location LocationsBuilderARM::ArithmeticZeroOrFpuRegister(HInstruction* input) { + DCHECK(input->GetType() == Primitive::kPrimDouble || input->GetType() == Primitive::kPrimFloat) + << input->GetType(); + if ((input->IsFloatConstant() && (input->AsFloatConstant()->IsArithmeticZero())) || + (input->IsDoubleConstant() && (input->AsDoubleConstant()->IsArithmeticZero()))) { + return Location::ConstantLocation(input->AsConstant()); + } else { + return Location::RequiresFpuRegister(); + } +} + Location LocationsBuilderARM::ArmEncodableConstantOrRegister(HInstruction* constant, Opcode opcode) { DCHECK(!Primitive::IsFloatingPointType(constant->GetType())); @@ -4012,31 +4062,51 @@ bool LocationsBuilderARM::CanEncodeConstantAsImmediate(HConstant* input_cst, Opcode opcode) { uint64_t value = static_cast<uint64_t>(Int64FromConstant(input_cst)); if (Primitive::Is64BitType(input_cst->GetType())) { - return CanEncodeConstantAsImmediate(Low32Bits(value), opcode) && - CanEncodeConstantAsImmediate(High32Bits(value), opcode); + Opcode high_opcode = opcode; + SetCc low_set_cc = kCcDontCare; + switch (opcode) { + case SUB: + // Flip the operation to an ADD. + value = -value; + opcode = ADD; + FALLTHROUGH_INTENDED; + case ADD: + if (Low32Bits(value) == 0u) { + return CanEncodeConstantAsImmediate(High32Bits(value), opcode, kCcDontCare); + } + high_opcode = ADC; + low_set_cc = kCcSet; + break; + default: + break; + } + return CanEncodeConstantAsImmediate(Low32Bits(value), opcode, low_set_cc) && + CanEncodeConstantAsImmediate(High32Bits(value), high_opcode, kCcDontCare); } else { return CanEncodeConstantAsImmediate(Low32Bits(value), opcode); } } -bool LocationsBuilderARM::CanEncodeConstantAsImmediate(uint32_t value, Opcode opcode) { +bool LocationsBuilderARM::CanEncodeConstantAsImmediate(uint32_t value, + Opcode opcode, + SetCc set_cc) { ShifterOperand so; ArmAssembler* assembler = codegen_->GetAssembler(); - if (assembler->ShifterOperandCanHold(kNoRegister, kNoRegister, opcode, value, &so)) { + if (assembler->ShifterOperandCanHold(kNoRegister, kNoRegister, opcode, value, set_cc, &so)) { return true; } Opcode neg_opcode = kNoOperand; switch (opcode) { - case AND: - neg_opcode = BIC; - break; - case ORR: - neg_opcode = ORN; - break; + case AND: neg_opcode = BIC; value = ~value; break; + case ORR: neg_opcode = ORN; value = ~value; break; + case ADD: neg_opcode = SUB; value = -value; break; + case ADC: neg_opcode = SBC; value = ~value; break; + case SUB: neg_opcode = ADD; value = -value; break; + case SBC: neg_opcode = ADC; value = ~value; break; default: return false; } - return assembler->ShifterOperandCanHold(kNoRegister, kNoRegister, neg_opcode, ~value, &so); + return assembler->ShifterOperandCanHold(kNoRegister, kNoRegister, neg_opcode, value, set_cc, &so); } void InstructionCodeGeneratorARM::HandleFieldGet(HInstruction* instruction, @@ -4437,8 +4507,6 @@ void InstructionCodeGeneratorARM::VisitArrayGet(HArrayGet* instruction) { Primitive::Type type = instruction->GetType(); HInstruction* array_instr = instruction->GetArray(); bool has_intermediate_address = array_instr->IsIntermediateAddress(); - // The read barrier instrumentation does not support the HIntermediateAddress instruction yet. - DCHECK(!(has_intermediate_address && kEmitCompilerReadBarrier)); switch (type) { case Primitive::kPrimBoolean: @@ -4473,6 +4541,11 @@ void InstructionCodeGeneratorARM::VisitArrayGet(HArrayGet* instruction) { } case Primitive::kPrimNot: { + // The read barrier instrumentation of object ArrayGet + // instructions does not support the HIntermediateAddress + // instruction. + DCHECK(!(has_intermediate_address && kEmitCompilerReadBarrier)); + static_assert( sizeof(mirror::HeapReference<mirror::Object>) == sizeof(int32_t), "art::mirror::HeapReference<art::mirror::Object> and int32_t have different sizes."); @@ -4615,8 +4688,6 @@ void InstructionCodeGeneratorARM::VisitArraySet(HArraySet* instruction) { Location value_loc = locations->InAt(2); HInstruction* array_instr = instruction->GetArray(); bool has_intermediate_address = array_instr->IsIntermediateAddress(); - // The read barrier instrumentation does not support the HIntermediateAddress instruction yet. - DCHECK(!(has_intermediate_address && kEmitCompilerReadBarrier)); switch (value_type) { case Primitive::kPrimBoolean: @@ -4881,8 +4952,6 @@ void InstructionCodeGeneratorARM::VisitArrayLength(HArrayLength* instruction) { } void LocationsBuilderARM::VisitIntermediateAddress(HIntermediateAddress* instruction) { - // The read barrier instrumentation does not support the HIntermediateAddress instruction yet. - DCHECK(!kEmitCompilerReadBarrier); LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); @@ -4897,9 +4966,6 @@ void InstructionCodeGeneratorARM::VisitIntermediateAddress(HIntermediateAddress* Location first = locations->InAt(0); Location second = locations->InAt(1); - // The read barrier instrumentation does not support the HIntermediateAddress instruction yet. - DCHECK(!kEmitCompilerReadBarrier); - if (second.IsRegister()) { __ add(out.AsRegister<Register>(), first.AsRegister<Register>(), @@ -6166,6 +6232,34 @@ void InstructionCodeGeneratorARM::GenerateEorConst(Register out, Register first, __ eor(out, first, ShifterOperand(value)); } +void InstructionCodeGeneratorARM::GenerateAddLongConst(Location out, + Location first, + uint64_t value) { + Register out_low = out.AsRegisterPairLow<Register>(); + Register out_high = out.AsRegisterPairHigh<Register>(); + Register first_low = first.AsRegisterPairLow<Register>(); + Register first_high = first.AsRegisterPairHigh<Register>(); + uint32_t value_low = Low32Bits(value); + uint32_t value_high = High32Bits(value); + if (value_low == 0u) { + if (out_low != first_low) { + __ mov(out_low, ShifterOperand(first_low)); + } + __ AddConstant(out_high, first_high, value_high); + return; + } + __ AddConstantSetFlags(out_low, first_low, value_low); + ShifterOperand so; + if (__ ShifterOperandCanHold(out_high, first_high, ADC, value_high, kCcDontCare, &so)) { + __ adc(out_high, first_high, so); + } else if (__ ShifterOperandCanHold(out_low, first_low, SBC, ~value_high, kCcDontCare, &so)) { + __ sbc(out_high, first_high, so); + } else { + LOG(FATAL) << "Unexpected constant " << value_high; + UNREACHABLE(); + } +} + void InstructionCodeGeneratorARM::HandleBitwiseOperation(HBinaryOperation* instruction) { LocationSummary* locations = instruction->GetLocations(); Location first = locations->InAt(0); diff --git a/compiler/optimizing/code_generator_arm.h b/compiler/optimizing/code_generator_arm.h index f9fcabd903..5d9b2dce1c 100644 --- a/compiler/optimizing/code_generator_arm.h +++ b/compiler/optimizing/code_generator_arm.h @@ -180,9 +180,10 @@ class LocationsBuilderARM : public HGraphVisitor { void HandleFieldSet(HInstruction* instruction, const FieldInfo& field_info); void HandleFieldGet(HInstruction* instruction, const FieldInfo& field_info); + Location ArithmeticZeroOrFpuRegister(HInstruction* input); Location ArmEncodableConstantOrRegister(HInstruction* constant, Opcode opcode); bool CanEncodeConstantAsImmediate(HConstant* input_cst, Opcode opcode); - bool CanEncodeConstantAsImmediate(uint32_t value, Opcode opcode); + bool CanEncodeConstantAsImmediate(uint32_t value, Opcode opcode, SetCc set_cc = kCcDontCare); CodeGeneratorARM* const codegen_; InvokeDexCallingConventionVisitorARM parameter_visitor_; @@ -219,6 +220,7 @@ class InstructionCodeGeneratorARM : public InstructionCodeGenerator { void GenerateAndConst(Register out, Register first, uint32_t value); void GenerateOrrConst(Register out, Register first, uint32_t value); void GenerateEorConst(Register out, Register first, uint32_t value); + void GenerateAddLongConst(Location out, Location first, uint64_t value); void HandleBitwiseOperation(HBinaryOperation* operation); void HandleCondition(HCondition* condition); void HandleIntegerRotate(LocationSummary* locations); @@ -281,6 +283,7 @@ class InstructionCodeGeneratorARM : public InstructionCodeGenerator { void GenerateCompareTestAndBranch(HCondition* condition, Label* true_target, Label* false_target); + void GenerateVcmp(HInstruction* instruction); void GenerateFPJumps(HCondition* cond, Label* true_label, Label* false_label); void GenerateLongComparesAndJumps(HCondition* cond, Label* true_label, Label* false_label); void DivRemOneOrMinusOne(HBinaryOperation* instruction); diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc index 115cee6492..9ceb3109cd 100644 --- a/compiler/optimizing/code_generator_arm64.cc +++ b/compiler/optimizing/code_generator_arm64.cc @@ -398,11 +398,9 @@ class SuspendCheckSlowPathARM64 : public SlowPathCodeARM64 { void EmitNativeCode(CodeGenerator* codegen) OVERRIDE { CodeGeneratorARM64* arm64_codegen = down_cast<CodeGeneratorARM64*>(codegen); __ Bind(GetEntryLabel()); - SaveLiveRegisters(codegen, instruction_->GetLocations()); arm64_codegen->InvokeRuntime( QUICK_ENTRY_POINT(pTestSuspend), instruction_, instruction_->GetDexPc(), this); CheckEntrypointTypes<kQuickTestSuspend, void, void>(); - RestoreLiveRegisters(codegen, instruction_->GetLocations()); if (successor_ == nullptr) { __ B(GetReturnLabel()); } else { @@ -600,6 +598,11 @@ class ReadBarrierMarkSlowPathARM64 : public SlowPathCodeARM64 { (instruction_->IsInvokeVirtual()) && instruction_->GetLocations()->Intrinsified()) << "Unexpected instruction in read barrier marking slow path: " << instruction_->DebugName(); + // The read barrier instrumentation of object ArrayGet + // instructions does not support the HIntermediateAddress + // instruction. + DCHECK(!(instruction_->IsArrayGet() && + instruction_->AsArrayGet()->GetArray()->IsIntermediateAddress())); __ Bind(GetEntryLabel()); // No need to save live registers; it's taken care of by the @@ -609,6 +612,8 @@ class ReadBarrierMarkSlowPathARM64 : public SlowPathCodeARM64 { DCHECK_NE(obj_.reg(), LR); DCHECK_NE(obj_.reg(), WSP); DCHECK_NE(obj_.reg(), WZR); + // WIP0 is used by the slow path as a temp, it can not be the object register. + DCHECK_NE(obj_.reg(), IP0); DCHECK(0 <= obj_.reg() && obj_.reg() < kNumberOfWRegisters) << obj_.reg(); // "Compact" slow path, saving two moves. // @@ -680,7 +685,9 @@ class ReadBarrierForHeapReferenceSlowPathARM64 : public SlowPathCodeARM64 { (instruction_->IsInvokeVirtual()) && instruction_->GetLocations()->Intrinsified()) << "Unexpected instruction in read barrier for heap reference slow path: " << instruction_->DebugName(); - // The read barrier instrumentation does not support the HIntermediateAddress instruction yet. + // The read barrier instrumentation of object ArrayGet + // instructions does not support the HIntermediateAddress + // instruction. DCHECK(!(instruction_->IsArrayGet() && instruction_->AsArrayGet()->GetArray()->IsIntermediateAddress())); @@ -751,10 +758,7 @@ class ReadBarrierForHeapReferenceSlowPathARM64 : public SlowPathCodeARM64 { (instruction_->AsInvoke()->GetIntrinsic() == Intrinsics::kUnsafeGetObjectVolatile)) << instruction_->AsInvoke()->GetIntrinsic(); DCHECK_EQ(offset_, 0U); - DCHECK(index_.IsRegisterPair()); - // UnsafeGet's offset location is a register pair, the low - // part contains the correct offset. - index = index_.ToLow(); + DCHECK(index_.IsRegister()); } } @@ -1284,17 +1288,21 @@ void CodeGeneratorARM64::MoveLocation(Location destination, UseScratchRegisterScope temps(GetVIXLAssembler()); HConstant* src_cst = source.GetConstant(); CPURegister temp; - if (src_cst->IsIntConstant() || src_cst->IsNullConstant()) { - temp = temps.AcquireW(); - } else if (src_cst->IsLongConstant()) { - temp = temps.AcquireX(); - } else if (src_cst->IsFloatConstant()) { - temp = temps.AcquireS(); + if (src_cst->IsZeroBitPattern()) { + temp = (src_cst->IsLongConstant() || src_cst->IsDoubleConstant()) ? xzr : wzr; } else { - DCHECK(src_cst->IsDoubleConstant()); - temp = temps.AcquireD(); + if (src_cst->IsIntConstant()) { + temp = temps.AcquireW(); + } else if (src_cst->IsLongConstant()) { + temp = temps.AcquireX(); + } else if (src_cst->IsFloatConstant()) { + temp = temps.AcquireS(); + } else { + DCHECK(src_cst->IsDoubleConstant()); + temp = temps.AcquireD(); + } + MoveConstant(temp, src_cst); } - MoveConstant(temp, src_cst); __ Str(temp, StackOperandFrom(destination)); } else { DCHECK(source.IsStackSlot() || source.IsDoubleStackSlot()); @@ -1982,8 +1990,6 @@ void InstructionCodeGeneratorARM64::VisitArm64DataProcWithShifterOp( } void LocationsBuilderARM64::VisitIntermediateAddress(HIntermediateAddress* instruction) { - // The read barrier instrumentation does not support the HIntermediateAddress instruction yet. - DCHECK(!kEmitCompilerReadBarrier); LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); locations->SetInAt(0, Location::RequiresRegister()); @@ -1991,10 +1997,7 @@ void LocationsBuilderARM64::VisitIntermediateAddress(HIntermediateAddress* instr locations->SetOut(Location::RequiresRegister()); } -void InstructionCodeGeneratorARM64::VisitIntermediateAddress( - HIntermediateAddress* instruction) { - // The read barrier instrumentation does not support the HIntermediateAddress instruction yet. - DCHECK(!kEmitCompilerReadBarrier); +void InstructionCodeGeneratorARM64::VisitIntermediateAddress(HIntermediateAddress* instruction) { __ Add(OutputRegister(instruction), InputRegisterAt(instruction, 0), Operand(InputOperandAt(instruction, 1))); @@ -2090,11 +2093,15 @@ void InstructionCodeGeneratorARM64::VisitArrayGet(HArrayGet* instruction) { // Block pools between `Load` and `MaybeRecordImplicitNullCheck`. BlockPoolsScope block_pools(masm); + // The read barrier instrumentation of object ArrayGet instructions + // does not support the HIntermediateAddress instruction. + DCHECK(!((type == Primitive::kPrimNot) && + instruction->GetArray()->IsIntermediateAddress() && + kEmitCompilerReadBarrier)); + if (type == Primitive::kPrimNot && kEmitCompilerReadBarrier && kUseBakerReadBarrier) { // Object ArrayGet with Baker's read barrier case. Register temp = temps.AcquireW(); - // The read barrier instrumentation does not support the HIntermediateAddress instruction yet. - DCHECK(!instruction->GetArray()->IsIntermediateAddress()); // Note that a potential implicit null check is handled in the // CodeGeneratorARM64::GenerateArrayLoadWithBakerReadBarrier call. codegen_->GenerateArrayLoadWithBakerReadBarrier( @@ -2108,9 +2115,6 @@ void InstructionCodeGeneratorARM64::VisitArrayGet(HArrayGet* instruction) { } else { Register temp = temps.AcquireSameSizeAs(obj); if (instruction->GetArray()->IsIntermediateAddress()) { - // The read barrier instrumentation does not support the - // HIntermediateAddress instruction yet. - DCHECK(!kEmitCompilerReadBarrier); // We do not need to compute the intermediate address from the array: the // input instruction has done it already. See the comment in // `TryExtractArrayAccessAddress()`. @@ -2200,9 +2204,6 @@ void InstructionCodeGeneratorARM64::VisitArraySet(HArraySet* instruction) { UseScratchRegisterScope temps(masm); Register temp = temps.AcquireSameSizeAs(array); if (instruction->GetArray()->IsIntermediateAddress()) { - // The read barrier instrumentation does not support the - // HIntermediateAddress instruction yet. - DCHECK(!kEmitCompilerReadBarrier); // We do not need to compute the intermediate address from the array: the // input instruction has done it already. See the comment in // `TryExtractArrayAccessAddress()`. @@ -2222,7 +2223,6 @@ void InstructionCodeGeneratorARM64::VisitArraySet(HArraySet* instruction) { codegen_->Store(value_type, value, destination); codegen_->MaybeRecordImplicitNullCheck(instruction); } else { - DCHECK(needs_write_barrier); DCHECK(!instruction->GetArray()->IsIntermediateAddress()); vixl::aarch64::Label done; SlowPathCodeARM64* slow_path = nullptr; diff --git a/compiler/optimizing/code_generator_arm64.h b/compiler/optimizing/code_generator_arm64.h index 240936c176..1b5fa857e7 100644 --- a/compiler/optimizing/code_generator_arm64.h +++ b/compiler/optimizing/code_generator_arm64.h @@ -243,7 +243,7 @@ class InstructionCodeGeneratorARM64 : public InstructionCodeGenerator { } Arm64Assembler* GetAssembler() const { return assembler_; } - vixl::aarch64::MacroAssembler* GetVIXLAssembler() { return GetAssembler()->vixl_masm_; } + vixl::aarch64::MacroAssembler* GetVIXLAssembler() { return GetAssembler()->GetVIXLAssembler(); } private: void GenerateClassInitializationCheck(SlowPathCodeARM64* slow_path, @@ -364,7 +364,7 @@ class ParallelMoveResolverARM64 : public ParallelMoveResolverNoSwap { private: Arm64Assembler* GetAssembler() const; vixl::aarch64::MacroAssembler* GetVIXLAssembler() const { - return GetAssembler()->vixl_masm_; + return GetAssembler()->GetVIXLAssembler(); } CodeGeneratorARM64* const codegen_; @@ -413,7 +413,7 @@ class CodeGeneratorARM64 : public CodeGenerator { HGraphVisitor* GetInstructionVisitor() OVERRIDE { return &instruction_visitor_; } Arm64Assembler* GetAssembler() OVERRIDE { return &assembler_; } const Arm64Assembler& GetAssembler() const OVERRIDE { return assembler_; } - vixl::aarch64::MacroAssembler* GetVIXLAssembler() { return GetAssembler()->vixl_masm_; } + vixl::aarch64::MacroAssembler* GetVIXLAssembler() { return GetAssembler()->GetVIXLAssembler(); } // Emit a write barrier. void MarkGCCard(vixl::aarch64::Register object, diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc index 8dd82ef9cb..59e103a3bd 100644 --- a/compiler/optimizing/code_generator_mips.cc +++ b/compiler/optimizing/code_generator_mips.cc @@ -351,14 +351,12 @@ class SuspendCheckSlowPathMIPS : public SlowPathCodeMIPS { void EmitNativeCode(CodeGenerator* codegen) OVERRIDE { CodeGeneratorMIPS* mips_codegen = down_cast<CodeGeneratorMIPS*>(codegen); __ Bind(GetEntryLabel()); - SaveLiveRegisters(codegen, instruction_->GetLocations()); mips_codegen->InvokeRuntime(QUICK_ENTRY_POINT(pTestSuspend), instruction_, instruction_->GetDexPc(), this, IsDirectEntrypoint(kQuickTestSuspend)); CheckEntrypointTypes<kQuickTestSuspend, void, void>(); - RestoreLiveRegisters(codegen, instruction_->GetLocations()); if (successor_ == nullptr) { __ B(GetReturnLabel()); } else { diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc index 3472830379..fe1fddc7bf 100644 --- a/compiler/optimizing/code_generator_mips64.cc +++ b/compiler/optimizing/code_generator_mips64.cc @@ -300,13 +300,11 @@ class SuspendCheckSlowPathMIPS64 : public SlowPathCodeMIPS64 { void EmitNativeCode(CodeGenerator* codegen) OVERRIDE { CodeGeneratorMIPS64* mips64_codegen = down_cast<CodeGeneratorMIPS64*>(codegen); __ Bind(GetEntryLabel()); - SaveLiveRegisters(codegen, instruction_->GetLocations()); mips64_codegen->InvokeRuntime(QUICK_ENTRY_POINT(pTestSuspend), instruction_, instruction_->GetDexPc(), this); CheckEntrypointTypes<kQuickTestSuspend, void, void>(); - RestoreLiveRegisters(codegen, instruction_->GetLocations()); if (successor_ == nullptr) { __ Bc(GetReturnLabel()); } else { diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index a2fa24542c..ade21174f4 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -192,13 +192,11 @@ class SuspendCheckSlowPathX86 : public SlowPathCode { void EmitNativeCode(CodeGenerator* codegen) OVERRIDE { CodeGeneratorX86* x86_codegen = down_cast<CodeGeneratorX86*>(codegen); __ Bind(GetEntryLabel()); - SaveLiveRegisters(codegen, instruction_->GetLocations()); x86_codegen->InvokeRuntime(QUICK_ENTRY_POINT(pTestSuspend), instruction_, instruction_->GetDexPc(), this); CheckEntrypointTypes<kQuickTestSuspend, void, void>(); - RestoreLiveRegisters(codegen, instruction_->GetLocations()); if (successor_ == nullptr) { __ jmp(GetReturnLabel()); } else { diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc index 5d5fa8504a..eadb431440 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -149,13 +149,11 @@ class SuspendCheckSlowPathX86_64 : public SlowPathCode { void EmitNativeCode(CodeGenerator* codegen) OVERRIDE { CodeGeneratorX86_64* x86_64_codegen = down_cast<CodeGeneratorX86_64*>(codegen); __ Bind(GetEntryLabel()); - SaveLiveRegisters(codegen, instruction_->GetLocations()); x86_64_codegen->InvokeRuntime(QUICK_ENTRY_POINT(pTestSuspend), instruction_, instruction_->GetDexPc(), this); CheckEntrypointTypes<kQuickTestSuspend, void, void>(); - RestoreLiveRegisters(codegen, instruction_->GetLocations()); if (successor_ == nullptr) { __ jmp(GetReturnLabel()); } else { diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h index 0ce0ec1402..58e700deba 100644 --- a/compiler/optimizing/dead_code_elimination.h +++ b/compiler/optimizing/dead_code_elimination.h @@ -31,13 +31,11 @@ class HDeadCodeElimination : public HOptimization { public: HDeadCodeElimination(HGraph* graph, OptimizingCompilerStats* stats = nullptr, - const char* name = kInitialDeadCodeEliminationPassName) + const char* name = kDeadCodeEliminationPassName) : HOptimization(graph, name, stats) {} void Run() OVERRIDE; - - static constexpr const char* kInitialDeadCodeEliminationPassName = "dead_code_elimination"; - static constexpr const char* kFinalDeadCodeEliminationPassName = "dead_code_elimination_final"; + static constexpr const char* kDeadCodeEliminationPassName = "dead_code_elimination"; private: void MaybeRecordDeadBlock(HBasicBlock* block); diff --git a/compiler/optimizing/dex_cache_array_fixups_arm.h b/compiler/optimizing/dex_cache_array_fixups_arm.h index 015f910328..9142e29eff 100644 --- a/compiler/optimizing/dex_cache_array_fixups_arm.h +++ b/compiler/optimizing/dex_cache_array_fixups_arm.h @@ -26,7 +26,9 @@ namespace arm { class DexCacheArrayFixups : public HOptimization { public: DexCacheArrayFixups(HGraph* graph, OptimizingCompilerStats* stats) - : HOptimization(graph, "dex_cache_array_fixups_arm", stats) {} + : HOptimization(graph, kDexCacheArrayFixupsArmPassName, stats) {} + + static constexpr const char* kDexCacheArrayFixupsArmPassName = "dex_cache_array_fixups_arm"; void Run() OVERRIDE; }; diff --git a/compiler/optimizing/dex_cache_array_fixups_mips.h b/compiler/optimizing/dex_cache_array_fixups_mips.h index 21056e130a..861a199d6c 100644 --- a/compiler/optimizing/dex_cache_array_fixups_mips.h +++ b/compiler/optimizing/dex_cache_array_fixups_mips.h @@ -29,9 +29,11 @@ namespace mips { class DexCacheArrayFixups : public HOptimization { public: DexCacheArrayFixups(HGraph* graph, CodeGenerator* codegen, OptimizingCompilerStats* stats) - : HOptimization(graph, "dex_cache_array_fixups_mips", stats), + : HOptimization(graph, kDexCacheArrayFixupsMipsPassName, stats), codegen_(codegen) {} + static constexpr const char* kDexCacheArrayFixupsMipsPassName = "dex_cache_array_fixups_mips"; + void Run() OVERRIDE; private: diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc index 0b4c569b05..89d80cc281 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -298,6 +298,12 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { stream << constant->AsIntConstant()->GetValue(); } else if (constant->IsLongConstant()) { stream << constant->AsLongConstant()->GetValue(); + } else if (constant->IsFloatConstant()) { + stream << constant->AsFloatConstant()->GetValue(); + } else if (constant->IsDoubleConstant()) { + stream << constant->AsDoubleConstant()->GetValue(); + } else if (constant->IsNullConstant()) { + stream << "null"; } } else if (location.IsInvalid()) { stream << "invalid"; diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h index 7c74816c26..cd4c830645 100644 --- a/compiler/optimizing/induction_var_analysis.h +++ b/compiler/optimizing/induction_var_analysis.h @@ -39,9 +39,9 @@ class HInductionVarAnalysis : public HOptimization { void Run() OVERRIDE; - private: static constexpr const char* kInductionPassName = "induction_var_analysis"; + private: struct NodeInfo { explicit NodeInfo(uint32_t d) : depth(d), done(false) {} uint32_t depth; diff --git a/compiler/optimizing/instruction_simplifier_arm.h b/compiler/optimizing/instruction_simplifier_arm.h index 3d297dacc0..782110c40a 100644 --- a/compiler/optimizing/instruction_simplifier_arm.h +++ b/compiler/optimizing/instruction_simplifier_arm.h @@ -48,7 +48,9 @@ class InstructionSimplifierArmVisitor : public HGraphVisitor { class InstructionSimplifierArm : public HOptimization { public: InstructionSimplifierArm(HGraph* graph, OptimizingCompilerStats* stats) - : HOptimization(graph, "instruction_simplifier_arm", stats) {} + : HOptimization(graph, kInstructionSimplifierArmPassName, stats) {} + + static constexpr const char* kInstructionSimplifierArmPassName = "instruction_simplifier_arm"; void Run() OVERRIDE { InstructionSimplifierArmVisitor visitor(graph_, stats_); diff --git a/compiler/optimizing/instruction_simplifier_arm64.h b/compiler/optimizing/instruction_simplifier_arm64.h index 28648b3bea..f71684efe9 100644 --- a/compiler/optimizing/instruction_simplifier_arm64.h +++ b/compiler/optimizing/instruction_simplifier_arm64.h @@ -82,8 +82,9 @@ class InstructionSimplifierArm64Visitor : public HGraphVisitor { class InstructionSimplifierArm64 : public HOptimization { public: InstructionSimplifierArm64(HGraph* graph, OptimizingCompilerStats* stats) - : HOptimization(graph, "instruction_simplifier_arm64", stats) {} - + : HOptimization(graph, kInstructionSimplifierArm64PassName, stats) {} + static constexpr const char* kInstructionSimplifierArm64PassName + = "instruction_simplifier_arm64"; void Run() OVERRIDE { InstructionSimplifierArm64Visitor visitor(graph_, stats_); visitor.VisitReversePostOrder(); diff --git a/compiler/optimizing/instruction_simplifier_shared.cc b/compiler/optimizing/instruction_simplifier_shared.cc index 8f7778fe68..6632cd9969 100644 --- a/compiler/optimizing/instruction_simplifier_shared.cc +++ b/compiler/optimizing/instruction_simplifier_shared.cc @@ -231,15 +231,6 @@ bool TryExtractArrayAccessAddress(HInstruction* access, HInstruction* array, HInstruction* index, size_t data_offset) { - if (kEmitCompilerReadBarrier) { - // The read barrier instrumentation does not support the - // HIntermediateAddress instruction yet. - // - // TODO: Handle this case properly in the ARM64 and ARM code generator and - // re-enable this optimization; otherwise, remove this TODO. - // b/26601270 - return false; - } if (index->IsConstant() || (index->IsBoundsCheck() && index->AsBoundsCheck()->GetIndex()->IsConstant())) { // When the index is a constant all the addressing can be fitted in the @@ -251,6 +242,13 @@ bool TryExtractArrayAccessAddress(HInstruction* access, // The access may require a runtime call or the original array pointer. return false; } + if (kEmitCompilerReadBarrier && + access->IsArrayGet() && + access->AsArrayGet()->GetType() == Primitive::kPrimNot) { + // For object arrays, the read barrier instrumentation requires + // the original array pointer. + return false; + } // Proceed to extract the base address computation. HGraph* graph = access->GetBlock()->GetGraph(); diff --git a/compiler/optimizing/intrinsics_arm.cc b/compiler/optimizing/intrinsics_arm.cc index be061f53f7..27d9d48560 100644 --- a/compiler/optimizing/intrinsics_arm.cc +++ b/compiler/optimizing/intrinsics_arm.cc @@ -1212,7 +1212,7 @@ static void GenerateVisitStringIndexOf(HInvoke* invoke, void IntrinsicLocationsBuilderARM::VisitStringIndexOf(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); // We have a hand-crafted assembly stub that follows the runtime calling convention. So it's // best to align the inputs accordingly. @@ -1232,7 +1232,7 @@ void IntrinsicCodeGeneratorARM::VisitStringIndexOf(HInvoke* invoke) { void IntrinsicLocationsBuilderARM::VisitStringIndexOfAfter(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); // We have a hand-crafted assembly stub that follows the runtime calling convention. So it's // best to align the inputs accordingly. @@ -1250,7 +1250,7 @@ void IntrinsicCodeGeneratorARM::VisitStringIndexOfAfter(HInvoke* invoke) { void IntrinsicLocationsBuilderARM::VisitStringNewStringFromBytes(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0))); @@ -1311,7 +1311,7 @@ void IntrinsicCodeGeneratorARM::VisitStringNewStringFromChars(HInvoke* invoke) { void IntrinsicLocationsBuilderARM::VisitStringNewStringFromString(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0))); diff --git a/compiler/optimizing/intrinsics_arm64.cc b/compiler/optimizing/intrinsics_arm64.cc index 06d1148652..e7c40e6600 100644 --- a/compiler/optimizing/intrinsics_arm64.cc +++ b/compiler/optimizing/intrinsics_arm64.cc @@ -26,7 +26,6 @@ #include "mirror/string.h" #include "thread.h" #include "utils/arm64/assembler_arm64.h" -#include "utils/arm64/constants_arm64.h" using namespace vixl::aarch64; // NOLINT(build/namespaces) @@ -62,14 +61,14 @@ ALWAYS_INLINE inline MemOperand AbsoluteHeapOperandFrom(Location location, size_ } // namespace MacroAssembler* IntrinsicCodeGeneratorARM64::GetVIXLAssembler() { - return codegen_->GetAssembler()->vixl_masm_; + return codegen_->GetVIXLAssembler(); } ArenaAllocator* IntrinsicCodeGeneratorARM64::GetAllocator() { return codegen_->GetGraph()->GetArena(); } -#define __ codegen->GetAssembler()->vixl_masm_-> +#define __ codegen->GetVIXLAssembler()-> static void MoveFromReturnRegister(Location trg, Primitive::Type type, @@ -782,7 +781,7 @@ static void GenUnsafeGet(HInvoke* invoke, DCHECK((type == Primitive::kPrimInt) || (type == Primitive::kPrimLong) || (type == Primitive::kPrimNot)); - MacroAssembler* masm = codegen->GetAssembler()->vixl_masm_; + MacroAssembler* masm = codegen->GetVIXLAssembler(); Location base_loc = locations->InAt(1); Register base = WRegisterFrom(base_loc); // Object pointer. Location offset_loc = locations->InAt(2); @@ -916,7 +915,7 @@ static void GenUnsafePut(LocationSummary* locations, bool is_volatile, bool is_ordered, CodeGeneratorARM64* codegen) { - MacroAssembler* masm = codegen->GetAssembler()->vixl_masm_; + MacroAssembler* masm = codegen->GetVIXLAssembler(); Register base = WRegisterFrom(locations->InAt(1)); // Object pointer. Register offset = XRegisterFrom(locations->InAt(2)); // Long offset. @@ -1035,7 +1034,7 @@ static void CreateIntIntIntIntIntToInt(ArenaAllocator* arena, } static void GenCas(LocationSummary* locations, Primitive::Type type, CodeGeneratorARM64* codegen) { - MacroAssembler* masm = codegen->GetAssembler()->vixl_masm_; + MacroAssembler* masm = codegen->GetVIXLAssembler(); Register out = WRegisterFrom(locations->Out()); // Boolean result. @@ -1409,7 +1408,7 @@ static void GenerateVisitStringIndexOf(HInvoke* invoke, void IntrinsicLocationsBuilderARM64::VisitStringIndexOf(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); // We have a hand-crafted assembly stub that follows the runtime calling convention. So it's // best to align the inputs accordingly. @@ -1429,7 +1428,7 @@ void IntrinsicCodeGeneratorARM64::VisitStringIndexOf(HInvoke* invoke) { void IntrinsicLocationsBuilderARM64::VisitStringIndexOfAfter(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); // We have a hand-crafted assembly stub that follows the runtime calling convention. So it's // best to align the inputs accordingly. @@ -1447,7 +1446,7 @@ void IntrinsicCodeGeneratorARM64::VisitStringIndexOfAfter(HInvoke* invoke) { void IntrinsicLocationsBuilderARM64::VisitStringNewStringFromBytes(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, LocationFrom(calling_convention.GetRegisterAt(0))); @@ -1506,7 +1505,7 @@ void IntrinsicCodeGeneratorARM64::VisitStringNewStringFromChars(HInvoke* invoke) void IntrinsicLocationsBuilderARM64::VisitStringNewStringFromString(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, LocationFrom(calling_convention.GetRegisterAt(0))); diff --git a/compiler/optimizing/intrinsics_mips.cc b/compiler/optimizing/intrinsics_mips.cc index 9449f79169..55e1ab2451 100644 --- a/compiler/optimizing/intrinsics_mips.cc +++ b/compiler/optimizing/intrinsics_mips.cc @@ -2070,7 +2070,7 @@ static void GenerateStringIndexOf(HInvoke* invoke, // int java.lang.String.indexOf(int ch) void IntrinsicLocationsBuilderMIPS::VisitStringIndexOf(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); // We have a hand-crafted assembly stub that follows the runtime // calling convention. So it's best to align the inputs accordingly. @@ -2095,7 +2095,7 @@ void IntrinsicCodeGeneratorMIPS::VisitStringIndexOf(HInvoke* invoke) { // int java.lang.String.indexOf(int ch, int fromIndex) void IntrinsicLocationsBuilderMIPS::VisitStringIndexOfAfter(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); // We have a hand-crafted assembly stub that follows the runtime // calling convention. So it's best to align the inputs accordingly. @@ -2121,7 +2121,7 @@ void IntrinsicCodeGeneratorMIPS::VisitStringIndexOfAfter(HInvoke* invoke) { // java.lang.StringFactory.newStringFromBytes(byte[] data, int high, int offset, int byteCount) void IntrinsicLocationsBuilderMIPS::VisitStringNewStringFromBytes(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0))); @@ -2186,7 +2186,7 @@ void IntrinsicCodeGeneratorMIPS::VisitStringNewStringFromChars(HInvoke* invoke) // java.lang.StringFactory.newStringFromString(String toCopy) void IntrinsicLocationsBuilderMIPS::VisitStringNewStringFromString(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0))); diff --git a/compiler/optimizing/intrinsics_mips64.cc b/compiler/optimizing/intrinsics_mips64.cc index 8d4d3e5e91..1e18540e1a 100644 --- a/compiler/optimizing/intrinsics_mips64.cc +++ b/compiler/optimizing/intrinsics_mips64.cc @@ -1707,7 +1707,7 @@ static void GenerateStringIndexOf(HInvoke* invoke, // int java.lang.String.indexOf(int ch) void IntrinsicLocationsBuilderMIPS64::VisitStringIndexOf(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); // We have a hand-crafted assembly stub that follows the runtime // calling convention. So it's best to align the inputs accordingly. @@ -1728,7 +1728,7 @@ void IntrinsicCodeGeneratorMIPS64::VisitStringIndexOf(HInvoke* invoke) { // int java.lang.String.indexOf(int ch, int fromIndex) void IntrinsicLocationsBuilderMIPS64::VisitStringIndexOfAfter(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); // We have a hand-crafted assembly stub that follows the runtime // calling convention. So it's best to align the inputs accordingly. @@ -1748,7 +1748,7 @@ void IntrinsicCodeGeneratorMIPS64::VisitStringIndexOfAfter(HInvoke* invoke) { // java.lang.StringFactory.newStringFromBytes(byte[] data, int high, int offset, int byteCount) void IntrinsicLocationsBuilderMIPS64::VisitStringNewStringFromBytes(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0))); @@ -1816,7 +1816,7 @@ void IntrinsicCodeGeneratorMIPS64::VisitStringNewStringFromChars(HInvoke* invoke // java.lang.StringFactory.newStringFromString(String toCopy) void IntrinsicLocationsBuilderMIPS64::VisitStringNewStringFromString(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0))); diff --git a/compiler/optimizing/intrinsics_x86.cc b/compiler/optimizing/intrinsics_x86.cc index 65f4def48b..dc409c92d6 100644 --- a/compiler/optimizing/intrinsics_x86.cc +++ b/compiler/optimizing/intrinsics_x86.cc @@ -752,8 +752,6 @@ void IntrinsicCodeGeneratorX86::VisitMathRint(HInvoke* invoke) { GenSSE41FPToFPIntrinsic(codegen_, invoke, GetAssembler(), 0); } -// Note that 32 bit x86 doesn't have the capability to inline MathRoundDouble, -// as it needs 64 bit instructions. void IntrinsicLocationsBuilderX86::VisitMathRoundFloat(HInvoke* invoke) { // See intrinsics.h. if (!kRoundIsPlusPointFive) { @@ -762,10 +760,17 @@ void IntrinsicLocationsBuilderX86::VisitMathRoundFloat(HInvoke* invoke) { // Do we have instruction support? if (codegen_->GetInstructionSetFeatures().HasSSE4_1()) { + HInvokeStaticOrDirect* static_or_direct = invoke->AsInvokeStaticOrDirect(); + DCHECK(static_or_direct != nullptr); LocationSummary* locations = new (arena_) LocationSummary(invoke, LocationSummary::kNoCall, kIntrinsified); locations->SetInAt(0, Location::RequiresFpuRegister()); + if (static_or_direct->HasSpecialInput() && + invoke->InputAt( + static_or_direct->GetSpecialInputIndex())->IsX86ComputeBaseMethodAddress()) { + locations->SetInAt(1, Location::RequiresRegister()); + } locations->SetOut(Location::RequiresRegister()); locations->AddTemp(Location::RequiresFpuRegister()); locations->AddTemp(Location::RequiresFpuRegister()); @@ -774,7 +779,7 @@ void IntrinsicLocationsBuilderX86::VisitMathRoundFloat(HInvoke* invoke) { // We have to fall back to a call to the intrinsic. LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly); + LocationSummary::kCallOnMainOnly); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetFpuRegisterAt(0))); locations->SetOut(Location::RegisterLocation(EAX)); @@ -784,47 +789,42 @@ void IntrinsicLocationsBuilderX86::VisitMathRoundFloat(HInvoke* invoke) { void IntrinsicCodeGeneratorX86::VisitMathRoundFloat(HInvoke* invoke) { LocationSummary* locations = invoke->GetLocations(); - if (locations->WillCall()) { + if (locations->WillCall()) { // TODO: can we reach this? InvokeOutOfLineIntrinsic(codegen_, invoke); return; } - // Implement RoundFloat as t1 = floor(input + 0.5f); convert to int. XmmRegister in = locations->InAt(0).AsFpuRegister<XmmRegister>(); + Register constant_area = locations->InAt(1).AsRegister<Register>(); + XmmRegister t1 = locations->GetTemp(0).AsFpuRegister<XmmRegister>(); + XmmRegister t2 = locations->GetTemp(1).AsFpuRegister<XmmRegister>(); Register out = locations->Out().AsRegister<Register>(); - XmmRegister maxInt = locations->GetTemp(0).AsFpuRegister<XmmRegister>(); - XmmRegister inPlusPointFive = locations->GetTemp(1).AsFpuRegister<XmmRegister>(); - NearLabel done, nan; + NearLabel skip_incr, done; X86Assembler* assembler = GetAssembler(); - // Generate 0.5 into inPlusPointFive. - __ movl(out, Immediate(bit_cast<int32_t, float>(0.5f))); - __ movd(inPlusPointFive, out); - - // Add in the input. - __ addss(inPlusPointFive, in); - - // And truncate to an integer. - __ roundss(inPlusPointFive, inPlusPointFive, Immediate(1)); - + // Since no direct x86 rounding instruction matches the required semantics, + // this intrinsic is implemented as follows: + // result = floor(in); + // if (in - result >= 0.5f) + // result = result + 1.0f; + __ movss(t2, in); + __ roundss(t1, in, Immediate(1)); + __ subss(t2, t1); + __ comiss(t2, codegen_->LiteralInt32Address(bit_cast<int32_t, float>(0.5f), constant_area)); + __ j(kBelow, &skip_incr); + __ addss(t1, codegen_->LiteralInt32Address(bit_cast<int32_t, float>(1.0f), constant_area)); + __ Bind(&skip_incr); + + // Final conversion to an integer. Unfortunately this also does not have a + // direct x86 instruction, since NaN should map to 0 and large positive + // values need to be clipped to the extreme value. __ movl(out, Immediate(kPrimIntMax)); - // maxInt = int-to-float(out) - __ cvtsi2ss(maxInt, out); - - // if inPlusPointFive >= maxInt goto done - __ comiss(inPlusPointFive, maxInt); - __ j(kAboveEqual, &done); - - // if input == NaN goto nan - __ j(kUnordered, &nan); - - // output = float-to-int-truncate(input) - __ cvttss2si(out, inPlusPointFive); - __ jmp(&done); - __ Bind(&nan); - - // output = 0 - __ xorl(out, out); + __ cvtsi2ss(t2, out); + __ comiss(t1, t2); + __ j(kAboveEqual, &done); // clipped to max (already in out), does not jump on unordered + __ movl(out, Immediate(0)); // does not change flags + __ j(kUnordered, &done); // NaN mapped to 0 (just moved in out) + __ cvttss2si(out, t1); __ Bind(&done); } @@ -1216,7 +1216,7 @@ void IntrinsicCodeGeneratorX86::VisitSystemArrayCopyChar(HInvoke* invoke) { void IntrinsicLocationsBuilderX86::VisitStringCompareTo(HInvoke* invoke) { // The inputs plus one temp. LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0))); @@ -1490,7 +1490,7 @@ void IntrinsicCodeGeneratorX86::VisitStringIndexOfAfter(HInvoke* invoke) { void IntrinsicLocationsBuilderX86::VisitStringNewStringFromBytes(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0))); @@ -1543,7 +1543,7 @@ void IntrinsicCodeGeneratorX86::VisitStringNewStringFromChars(HInvoke* invoke) { void IntrinsicLocationsBuilderX86::VisitStringNewStringFromString(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0))); diff --git a/compiler/optimizing/intrinsics_x86_64.cc b/compiler/optimizing/intrinsics_x86_64.cc index 7e0d72930c..7dfbfb09be 100644 --- a/compiler/optimizing/intrinsics_x86_64.cc +++ b/compiler/optimizing/intrinsics_x86_64.cc @@ -583,6 +583,7 @@ static void CreateSSE41FPToIntLocations(ArenaAllocator* arena, locations->SetInAt(0, Location::RequiresFpuRegister()); locations->SetOut(Location::RequiresRegister()); locations->AddTemp(Location::RequiresFpuRegister()); + locations->AddTemp(Location::RequiresFpuRegister()); return; } @@ -598,9 +599,10 @@ static void CreateSSE41FPToIntLocations(ArenaAllocator* arena, void IntrinsicLocationsBuilderX86_64::VisitMathRoundFloat(HInvoke* invoke) { // See intrinsics.h. - if (kRoundIsPlusPointFive) { - CreateSSE41FPToIntLocations(arena_, invoke, codegen_); + if (!kRoundIsPlusPointFive) { + return; } + CreateSSE41FPToIntLocations(arena_, invoke, codegen_); } void IntrinsicCodeGeneratorX86_64::VisitMathRoundFloat(HInvoke* invoke) { @@ -610,47 +612,45 @@ void IntrinsicCodeGeneratorX86_64::VisitMathRoundFloat(HInvoke* invoke) { return; } - // Implement RoundFloat as t1 = floor(input + 0.5f); convert to int. XmmRegister in = locations->InAt(0).AsFpuRegister<XmmRegister>(); CpuRegister out = locations->Out().AsRegister<CpuRegister>(); - XmmRegister inPlusPointFive = locations->GetTemp(0).AsFpuRegister<XmmRegister>(); - NearLabel done, nan; + XmmRegister t1 = locations->GetTemp(0).AsFpuRegister<XmmRegister>(); + XmmRegister t2 = locations->GetTemp(1).AsFpuRegister<XmmRegister>(); + NearLabel skip_incr, done; X86_64Assembler* assembler = GetAssembler(); - // Load 0.5 into inPlusPointFive. - __ movss(inPlusPointFive, codegen_->LiteralFloatAddress(0.5f)); - - // Add in the input. - __ addss(inPlusPointFive, in); - - // And truncate to an integer. - __ roundss(inPlusPointFive, inPlusPointFive, Immediate(1)); - - // Load maxInt into out. - codegen_->Load64BitValue(out, kPrimIntMax); - - // if inPlusPointFive >= maxInt goto done - __ comiss(inPlusPointFive, codegen_->LiteralFloatAddress(static_cast<float>(kPrimIntMax))); - __ j(kAboveEqual, &done); - - // if input == NaN goto nan - __ j(kUnordered, &nan); - - // output = float-to-int-truncate(input) - __ cvttss2si(out, inPlusPointFive); - __ jmp(&done); - __ Bind(&nan); - - // output = 0 - __ xorl(out, out); + // Since no direct x86 rounding instruction matches the required semantics, + // this intrinsic is implemented as follows: + // result = floor(in); + // if (in - result >= 0.5f) + // result = result + 1.0f; + __ movss(t2, in); + __ roundss(t1, in, Immediate(1)); + __ subss(t2, t1); + __ comiss(t2, codegen_->LiteralFloatAddress(0.5f)); + __ j(kBelow, &skip_incr); + __ addss(t1, codegen_->LiteralFloatAddress(1.0f)); + __ Bind(&skip_incr); + + // Final conversion to an integer. Unfortunately this also does not have a + // direct x86 instruction, since NaN should map to 0 and large positive + // values need to be clipped to the extreme value. + codegen_->Load32BitValue(out, kPrimIntMax); + __ cvtsi2ss(t2, out); + __ comiss(t1, t2); + __ j(kAboveEqual, &done); // clipped to max (already in out), does not jump on unordered + __ movl(out, Immediate(0)); // does not change flags + __ j(kUnordered, &done); // NaN mapped to 0 (just moved in out) + __ cvttss2si(out, t1); __ Bind(&done); } void IntrinsicLocationsBuilderX86_64::VisitMathRoundDouble(HInvoke* invoke) { // See intrinsics.h. - if (kRoundIsPlusPointFive) { - CreateSSE41FPToIntLocations(arena_, invoke, codegen_); + if (!kRoundIsPlusPointFive) { + return; } + CreateSSE41FPToIntLocations(arena_, invoke, codegen_); } void IntrinsicCodeGeneratorX86_64::VisitMathRoundDouble(HInvoke* invoke) { @@ -660,39 +660,36 @@ void IntrinsicCodeGeneratorX86_64::VisitMathRoundDouble(HInvoke* invoke) { return; } - // Implement RoundDouble as t1 = floor(input + 0.5); convert to long. XmmRegister in = locations->InAt(0).AsFpuRegister<XmmRegister>(); CpuRegister out = locations->Out().AsRegister<CpuRegister>(); - XmmRegister inPlusPointFive = locations->GetTemp(0).AsFpuRegister<XmmRegister>(); - NearLabel done, nan; + XmmRegister t1 = locations->GetTemp(0).AsFpuRegister<XmmRegister>(); + XmmRegister t2 = locations->GetTemp(1).AsFpuRegister<XmmRegister>(); + NearLabel skip_incr, done; X86_64Assembler* assembler = GetAssembler(); - // Load 0.5 into inPlusPointFive. - __ movsd(inPlusPointFive, codegen_->LiteralDoubleAddress(0.5)); - - // Add in the input. - __ addsd(inPlusPointFive, in); - - // And truncate to an integer. - __ roundsd(inPlusPointFive, inPlusPointFive, Immediate(1)); - - // Load maxLong into out. + // Since no direct x86 rounding instruction matches the required semantics, + // this intrinsic is implemented as follows: + // result = floor(in); + // if (in - result >= 0.5) + // result = result + 1.0f; + __ movsd(t2, in); + __ roundsd(t1, in, Immediate(1)); + __ subsd(t2, t1); + __ comisd(t2, codegen_->LiteralDoubleAddress(0.5)); + __ j(kBelow, &skip_incr); + __ addsd(t1, codegen_->LiteralDoubleAddress(1.0f)); + __ Bind(&skip_incr); + + // Final conversion to an integer. Unfortunately this also does not have a + // direct x86 instruction, since NaN should map to 0 and large positive + // values need to be clipped to the extreme value. codegen_->Load64BitValue(out, kPrimLongMax); - - // if inPlusPointFive >= maxLong goto done - __ comisd(inPlusPointFive, codegen_->LiteralDoubleAddress(static_cast<double>(kPrimLongMax))); - __ j(kAboveEqual, &done); - - // if input == NaN goto nan - __ j(kUnordered, &nan); - - // output = double-to-long-truncate(input) - __ cvttsd2si(out, inPlusPointFive, /* is64bit */ true); - __ jmp(&done); - __ Bind(&nan); - - // output = 0 - __ xorl(out, out); + __ cvtsi2sd(t2, out, /* is64bit */ true); + __ comisd(t1, t2); + __ j(kAboveEqual, &done); // clipped to max (already in out), does not jump on unordered + __ movl(out, Immediate(0)); // does not change flags, implicit zero extension to 64-bit + __ j(kUnordered, &done); // NaN mapped to 0 (just moved in out) + __ cvttsd2si(out, t1, /* is64bit */ true); __ Bind(&done); } @@ -1303,7 +1300,7 @@ void IntrinsicCodeGeneratorX86_64::VisitSystemArrayCopy(HInvoke* invoke) { void IntrinsicLocationsBuilderX86_64::VisitStringCompareTo(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0))); @@ -1577,7 +1574,7 @@ void IntrinsicCodeGeneratorX86_64::VisitStringIndexOfAfter(HInvoke* invoke) { void IntrinsicLocationsBuilderX86_64::VisitStringNewStringFromBytes(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0))); @@ -1634,7 +1631,7 @@ void IntrinsicCodeGeneratorX86_64::VisitStringNewStringFromChars(HInvoke* invoke void IntrinsicLocationsBuilderX86_64::VisitStringNewStringFromString(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, - LocationSummary::kCallOnMainOnly, + LocationSummary::kCallOnMainAndSlowPath, kIntrinsified); InvokeRuntimeCallingConvention calling_convention; locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0))); diff --git a/compiler/optimizing/locations.h b/compiler/optimizing/locations.h index 7a78bfdc8d..5fdfb9b6ca 100644 --- a/compiler/optimizing/locations.h +++ b/compiler/optimizing/locations.h @@ -376,6 +376,10 @@ class Location : public ValueObject { return PolicyField::Decode(GetPayload()); } + bool RequiresRegisterKind() const { + return GetPolicy() == kRequiresRegister || GetPolicy() == kRequiresFpuRegister; + } + uintptr_t GetEncoding() const { return GetPayload(); } @@ -480,6 +484,7 @@ class LocationSummary : public ArenaObject<kArenaAllocLocationSummary> { public: enum CallKind { kNoCall, + kCallOnMainAndSlowPath, kCallOnSlowPath, kCallOnMainOnly }; @@ -540,10 +545,29 @@ class LocationSummary : public ArenaObject<kArenaAllocLocationSummary> { Location Out() const { return output_; } - bool CanCall() const { return call_kind_ != kNoCall; } - bool WillCall() const { return call_kind_ == kCallOnMainOnly; } - bool OnlyCallsOnSlowPath() const { return call_kind_ == kCallOnSlowPath; } - bool NeedsSafepoint() const { return CanCall(); } + bool CanCall() const { + return call_kind_ != kNoCall; + } + + bool WillCall() const { + return call_kind_ == kCallOnMainOnly || call_kind_ == kCallOnMainAndSlowPath; + } + + bool CallsOnSlowPath() const { + return call_kind_ == kCallOnSlowPath || call_kind_ == kCallOnMainAndSlowPath; + } + + bool OnlyCallsOnSlowPath() const { + return call_kind_ == kCallOnSlowPath; + } + + bool CallsOnMainAndSlowPath() const { + return call_kind_ == kCallOnMainAndSlowPath; + } + + bool NeedsSafepoint() const { + return CanCall(); + } void SetStackBit(uint32_t index) { stack_mask_->SetBit(index); @@ -629,8 +653,7 @@ class LocationSummary : public ArenaObject<kArenaAllocLocationSummary> { // Whether these are locations for an intrinsified call. bool intrinsified_; - ART_FRIEND_TEST(RegisterAllocatorTest, ExpectedInRegisterHint); - ART_FRIEND_TEST(RegisterAllocatorTest, SameAsFirstInputHint); + friend class RegisterAllocatorTest; DISALLOW_COPY_AND_ASSIGN(LocationSummary); }; diff --git a/compiler/optimizing/optimization.h b/compiler/optimizing/optimization.h index 2f59d4cd5b..0819fb01ac 100644 --- a/compiler/optimizing/optimization.h +++ b/compiler/optimizing/optimization.h @@ -37,7 +37,10 @@ class HOptimization : public ArenaObject<kArenaAllocOptimization> { virtual ~HOptimization() {} - // Return the name of the pass. + // Return the name of the pass. Pass names for a single HOptimization should be of form + // <optimization_name> or <optimization_name>$<pass_name> for common <optimization_name> prefix. + // Example: 'instruction_simplifier', 'instruction_simplifier$after_bce', + // 'instruction_simplifier$before_codegen'. const char* GetPassName() const { return pass_name_; } // Perform the analysis itself. diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index d5b0d77fe5..f7c82d1987 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -95,6 +95,8 @@ namespace art { static constexpr size_t kArenaAllocatorMemoryReportThreshold = 8 * MB; +static constexpr const char* kPassNameSeparator = "$"; + /** * Used by the code generator, to allocate the code in a vector. */ @@ -266,7 +268,7 @@ class PassScope : public ValueObject { class OptimizingCompiler FINAL : public Compiler { public: explicit OptimizingCompiler(CompilerDriver* driver); - ~OptimizingCompiler(); + ~OptimizingCompiler() OVERRIDE; bool CanCompileMethod(uint32_t method_idx, const DexFile& dex_file) const OVERRIDE; @@ -305,17 +307,17 @@ class OptimizingCompiler FINAL : public Compiler { OVERRIDE SHARED_REQUIRES(Locks::mutator_lock_); - protected: - virtual void RunOptimizations(HGraph* graph, - CodeGenerator* codegen, - CompilerDriver* driver, - const DexCompilationUnit& dex_compilation_unit, - PassObserver* pass_observer, - StackHandleScopeCollection* handles) const; + private: + void RunOptimizations(HGraph* graph, + CodeGenerator* codegen, + CompilerDriver* driver, + const DexCompilationUnit& dex_compilation_unit, + PassObserver* pass_observer, + StackHandleScopeCollection* handles) const; - virtual void RunOptimizations(HOptimization* optimizations[], - size_t length, - PassObserver* pass_observer) const; + void RunOptimizations(HOptimization* optimizations[], + size_t length, + PassObserver* pass_observer) const; private: // Create a 'CompiledMethod' for an optimized graph. @@ -420,6 +422,117 @@ static bool InstructionSetSupportsReadBarrier(InstructionSet instruction_set) { || instruction_set == kX86_64; } +static HOptimization* BuildOptimization( + const std::string& opt_name, + ArenaAllocator* arena, + HGraph* graph, + OptimizingCompilerStats* stats, + CodeGenerator* codegen, + CompilerDriver* driver, + const DexCompilationUnit& dex_compilation_unit, + StackHandleScopeCollection* handles, + SideEffectsAnalysis* most_recent_side_effects, + HInductionVarAnalysis* most_recent_induction) { + if (opt_name == arm::InstructionSimplifierArm::kInstructionSimplifierArmPassName) { + return new (arena) arm::InstructionSimplifierArm(graph, stats); + } else if (opt_name == arm64::InstructionSimplifierArm64::kInstructionSimplifierArm64PassName) { + return new (arena) arm64::InstructionSimplifierArm64(graph, stats); + } else if (opt_name == BoundsCheckElimination::kBoundsCheckEliminationPassName) { + CHECK(most_recent_side_effects != nullptr && most_recent_induction != nullptr); + return new (arena) BoundsCheckElimination(graph, + *most_recent_side_effects, + most_recent_induction); + } else if (opt_name == GVNOptimization::kGlobalValueNumberingPassName) { + CHECK(most_recent_side_effects != nullptr); + return new (arena) GVNOptimization(graph, *most_recent_side_effects); + } else if (opt_name == HConstantFolding::kConstantFoldingPassName) { + return new (arena) HConstantFolding(graph); + } else if (opt_name == HDeadCodeElimination::kDeadCodeEliminationPassName) { + return new (arena) HDeadCodeElimination(graph, stats); + } else if (opt_name == HInliner::kInlinerPassName) { + size_t number_of_dex_registers = dex_compilation_unit.GetCodeItem()->registers_size_; + return new (arena) HInliner(graph, // outer_graph + graph, // outermost_graph + codegen, + dex_compilation_unit, // outer_compilation_unit + dex_compilation_unit, // outermost_compilation_unit + driver, + handles, + stats, + number_of_dex_registers, + /* depth */ 0); + } else if (opt_name == HSharpening::kSharpeningPassName) { + return new (arena) HSharpening(graph, codegen, dex_compilation_unit, driver); + } else if (opt_name == HSelectGenerator::kSelectGeneratorPassName) { + return new (arena) HSelectGenerator(graph, stats); + } else if (opt_name == HInductionVarAnalysis::kInductionPassName) { + return new (arena) HInductionVarAnalysis(graph); + } else if (opt_name == InstructionSimplifier::kInstructionSimplifierPassName) { + return new (arena) InstructionSimplifier(graph, stats); + } else if (opt_name == IntrinsicsRecognizer::kIntrinsicsRecognizerPassName) { + return new (arena) IntrinsicsRecognizer(graph, driver, stats); + } else if (opt_name == LICM::kLoopInvariantCodeMotionPassName) { + CHECK(most_recent_side_effects != nullptr); + return new (arena) LICM(graph, *most_recent_side_effects, stats); + } else if (opt_name == LoadStoreElimination::kLoadStoreEliminationPassName) { + CHECK(most_recent_side_effects != nullptr); + return new (arena) LoadStoreElimination(graph, *most_recent_side_effects); + } else if (opt_name == mips::DexCacheArrayFixups::kDexCacheArrayFixupsMipsPassName) { + return new (arena) mips::DexCacheArrayFixups(graph, codegen, stats); + } else if (opt_name == mips::PcRelativeFixups::kPcRelativeFixupsMipsPassName) { + return new (arena) mips::PcRelativeFixups(graph, codegen, stats); + } else if (opt_name == SideEffectsAnalysis::kSideEffectsAnalysisPassName) { + return new (arena) SideEffectsAnalysis(graph); + } else if (opt_name == x86::PcRelativeFixups::kPcRelativeFixupsX86PassName) { + return new (arena) x86::PcRelativeFixups(graph, codegen, stats); + } else if (opt_name == x86::X86MemoryOperandGeneration::kX86MemoryOperandGenerationPassName) { + return new (arena) x86::X86MemoryOperandGeneration(graph, codegen, stats); + } + return nullptr; +} + +static ArenaVector<HOptimization*> BuildOptimizations( + const std::vector<std::string>& pass_names, + ArenaAllocator* arena, + HGraph* graph, + OptimizingCompilerStats* stats, + CodeGenerator* codegen, + CompilerDriver* driver, + const DexCompilationUnit& dex_compilation_unit, + StackHandleScopeCollection* handles) { + // Few HOptimizations constructors require SideEffectsAnalysis or HInductionVarAnalysis + // instances. This method assumes that each of them expects the nearest instance preceeding it + // in the pass name list. + SideEffectsAnalysis* most_recent_side_effects = nullptr; + HInductionVarAnalysis* most_recent_induction = nullptr; + ArenaVector<HOptimization*> ret(arena->Adapter()); + for (std::string pass_name : pass_names) { + size_t pos = pass_name.find(kPassNameSeparator); // Strip suffix to get base pass name. + std::string opt_name = pos == std::string::npos ? pass_name : pass_name.substr(0, pos); + + HOptimization* opt = BuildOptimization( + opt_name, + arena, + graph, + stats, + codegen, + driver, + dex_compilation_unit, + handles, + most_recent_side_effects, + most_recent_induction); + CHECK(opt != nullptr) << "Couldn't build optimization: \"" << pass_name << "\""; + ret.push_back(opt); + + if (opt_name == SideEffectsAnalysis::kSideEffectsAnalysisPassName) { + most_recent_side_effects = down_cast<SideEffectsAnalysis*>(opt); + } else if (opt_name == HInductionVarAnalysis::kInductionPassName) { + most_recent_induction = down_cast<HInductionVarAnalysis*>(opt); + } + } + return ret; +} + void OptimizingCompiler::RunOptimizations(HOptimization* optimizations[], size_t length, PassObserver* pass_observer) const { @@ -444,11 +557,11 @@ void OptimizingCompiler::MaybeRunInliner(HGraph* graph, } size_t number_of_dex_registers = dex_compilation_unit.GetCodeItem()->registers_size_; HInliner* inliner = new (graph->GetArena()) HInliner( - graph, - graph, + graph, // outer_graph + graph, // outermost_graph codegen, - dex_compilation_unit, - dex_compilation_unit, + dex_compilation_unit, // outer_compilation_unit + dex_compilation_unit, // outermost_compilation_unit driver, handles, stats, @@ -473,7 +586,7 @@ void OptimizingCompiler::RunArchOptimizations(InstructionSet instruction_set, arm::InstructionSimplifierArm* simplifier = new (arena) arm::InstructionSimplifierArm(graph, stats); SideEffectsAnalysis* side_effects = new (arena) SideEffectsAnalysis(graph); - GVNOptimization* gvn = new (arena) GVNOptimization(graph, *side_effects, "GVN_after_arch"); + GVNOptimization* gvn = new (arena) GVNOptimization(graph, *side_effects, "GVN$after_arch"); HOptimization* arm_optimizations[] = { simplifier, side_effects, @@ -489,7 +602,7 @@ void OptimizingCompiler::RunArchOptimizations(InstructionSet instruction_set, arm64::InstructionSimplifierArm64* simplifier = new (arena) arm64::InstructionSimplifierArm64(graph, stats); SideEffectsAnalysis* side_effects = new (arena) SideEffectsAnalysis(graph); - GVNOptimization* gvn = new (arena) GVNOptimization(graph, *side_effects, "GVN_after_arch"); + GVNOptimization* gvn = new (arena) GVNOptimization(graph, *side_effects, "GVN$after_arch"); HOptimization* arm64_optimizations[] = { simplifier, side_effects, @@ -518,7 +631,7 @@ void OptimizingCompiler::RunArchOptimizations(InstructionSet instruction_set, x86::PcRelativeFixups* pc_relative_fixups = new (arena) x86::PcRelativeFixups(graph, codegen, stats); x86::X86MemoryOperandGeneration* memory_gen = - new(arena) x86::X86MemoryOperandGeneration(graph, stats, codegen); + new (arena) x86::X86MemoryOperandGeneration(graph, codegen, stats); HOptimization* x86_optimizations[] = { pc_relative_fixups, memory_gen @@ -530,7 +643,7 @@ void OptimizingCompiler::RunArchOptimizations(InstructionSet instruction_set, #ifdef ART_ENABLE_CODEGEN_x86_64 case kX86_64: { x86::X86MemoryOperandGeneration* memory_gen = - new(arena) x86::X86MemoryOperandGeneration(graph, stats, codegen); + new (arena) x86::X86MemoryOperandGeneration(graph, codegen, stats); HOptimization* x86_64_optimizations[] = { memory_gen }; @@ -546,7 +659,8 @@ void OptimizingCompiler::RunArchOptimizations(InstructionSet instruction_set, NO_INLINE // Avoid increasing caller's frame size by large stack-allocated objects. static void AllocateRegisters(HGraph* graph, CodeGenerator* codegen, - PassObserver* pass_observer) { + PassObserver* pass_observer, + RegisterAllocator::Strategy strategy) { { PassScope scope(PrepareForRegisterAllocation::kPrepareForRegisterAllocationPassName, pass_observer); @@ -559,7 +673,7 @@ static void AllocateRegisters(HGraph* graph, } { PassScope scope(RegisterAllocator::kRegisterAllocatorPassName, pass_observer); - RegisterAllocator::Create(graph->GetArena(), codegen, liveness)->AllocateRegisters(); + RegisterAllocator::Create(graph->GetArena(), codegen, liveness, strategy)->AllocateRegisters(); } } @@ -571,15 +685,30 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph, StackHandleScopeCollection* handles) const { OptimizingCompilerStats* stats = compilation_stats_.get(); ArenaAllocator* arena = graph->GetArena(); + if (driver->GetCompilerOptions().GetPassesToRun() != nullptr) { + ArenaVector<HOptimization*> optimizations = BuildOptimizations( + *driver->GetCompilerOptions().GetPassesToRun(), + arena, + graph, + stats, + codegen, + driver, + dex_compilation_unit, + handles); + RunOptimizations(&optimizations[0], optimizations.size(), pass_observer); + return; + } + HDeadCodeElimination* dce1 = new (arena) HDeadCodeElimination( - graph, stats, HDeadCodeElimination::kInitialDeadCodeEliminationPassName); + graph, stats, "dead_code_elimination$initial"); HDeadCodeElimination* dce2 = new (arena) HDeadCodeElimination( - graph, stats, HDeadCodeElimination::kFinalDeadCodeEliminationPassName); + graph, stats, "dead_code_elimination$final"); HConstantFolding* fold1 = new (arena) HConstantFolding(graph); InstructionSimplifier* simplify1 = new (arena) InstructionSimplifier(graph, stats); HSelectGenerator* select_generator = new (arena) HSelectGenerator(graph, stats); - HConstantFolding* fold2 = new (arena) HConstantFolding(graph, "constant_folding_after_inlining"); - HConstantFolding* fold3 = new (arena) HConstantFolding(graph, "constant_folding_after_bce"); + HConstantFolding* fold2 = new (arena) HConstantFolding( + graph, "constant_folding$after_inlining"); + HConstantFolding* fold3 = new (arena) HConstantFolding(graph, "constant_folding$after_bce"); SideEffectsAnalysis* side_effects = new (arena) SideEffectsAnalysis(graph); GVNOptimization* gvn = new (arena) GVNOptimization(graph, *side_effects); LICM* licm = new (arena) LICM(graph, *side_effects, stats); @@ -588,9 +717,9 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph, BoundsCheckElimination* bce = new (arena) BoundsCheckElimination(graph, *side_effects, induction); 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_bce"); InstructionSimplifier* simplify3 = new (arena) InstructionSimplifier( - graph, stats, "instruction_simplifier_before_codegen"); + graph, stats, "instruction_simplifier$before_codegen"); IntrinsicsRecognizer* intrinsics = new (arena) IntrinsicsRecognizer(graph, driver, stats); HOptimization* optimizations1[] = { @@ -626,7 +755,6 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph, RunOptimizations(optimizations2, arraysize(optimizations2), pass_observer); RunArchOptimizations(driver->GetInstructionSet(), graph, codegen, pass_observer); - AllocateRegisters(graph, codegen, pass_observer); } static ArenaVector<LinkerPatch> EmitAndSortLinkerPatches(CodeGenerator* codegen) { @@ -841,6 +969,10 @@ CodeGenerator* OptimizingCompiler::TryCompile(ArenaAllocator* arena, &pass_observer, &handles); + RegisterAllocator::Strategy regalloc_strategy = + compiler_options.GetRegisterAllocationStrategy(); + AllocateRegisters(graph, codegen.get(), &pass_observer, regalloc_strategy); + codegen->Compile(code_allocator); pass_observer.DumpDisassembly(); } diff --git a/compiler/optimizing/pc_relative_fixups_mips.h b/compiler/optimizing/pc_relative_fixups_mips.h index 1e8b071bb3..5a7397bf9d 100644 --- a/compiler/optimizing/pc_relative_fixups_mips.h +++ b/compiler/optimizing/pc_relative_fixups_mips.h @@ -32,6 +32,8 @@ class PcRelativeFixups : public HOptimization { : HOptimization(graph, "pc_relative_fixups_mips", stats), codegen_(codegen) {} + static constexpr const char* kPcRelativeFixupsMipsPassName = "pc_relative_fixups_mips"; + void Run() OVERRIDE; private: diff --git a/compiler/optimizing/pc_relative_fixups_x86.cc b/compiler/optimizing/pc_relative_fixups_x86.cc index 921f3dfff6..ad0921d7e6 100644 --- a/compiler/optimizing/pc_relative_fixups_x86.cc +++ b/compiler/optimizing/pc_relative_fixups_x86.cc @@ -227,6 +227,7 @@ class PCRelativeHandlerVisitor : public HGraphVisitor { case Intrinsics::kMathMaxFloatFloat: case Intrinsics::kMathMinDoubleDouble: case Intrinsics::kMathMinFloatFloat: + case Intrinsics::kMathRoundFloat: if (!base_added) { DCHECK(invoke_static_or_direct != nullptr); DCHECK(!invoke_static_or_direct->HasCurrentMethodInput()); diff --git a/compiler/optimizing/pc_relative_fixups_x86.h b/compiler/optimizing/pc_relative_fixups_x86.h index 03de2fcece..72fa71ea94 100644 --- a/compiler/optimizing/pc_relative_fixups_x86.h +++ b/compiler/optimizing/pc_relative_fixups_x86.h @@ -29,9 +29,11 @@ namespace x86 { class PcRelativeFixups : public HOptimization { public: PcRelativeFixups(HGraph* graph, CodeGenerator* codegen, OptimizingCompilerStats* stats) - : HOptimization(graph, "pc_relative_fixups_x86", stats), + : HOptimization(graph, kPcRelativeFixupsX86PassName, stats), codegen_(codegen) {} + static constexpr const char* kPcRelativeFixupsX86PassName = "pc_relative_fixups_x86"; + void Run() OVERRIDE; private: diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc index 2367ce1aeb..5b768d5d67 100644 --- a/compiler/optimizing/register_allocator.cc +++ b/compiler/optimizing/register_allocator.cc @@ -21,6 +21,7 @@ #include "base/bit_vector-inl.h" #include "code_generator.h" +#include "register_allocator_graph_color.h" #include "register_allocator_linear_scan.h" #include "ssa_liveness_analysis.h" @@ -41,6 +42,8 @@ RegisterAllocator* RegisterAllocator::Create(ArenaAllocator* allocator, switch (strategy) { case kRegisterAllocatorLinearScan: return new (allocator) RegisterAllocatorLinearScan(allocator, codegen, analysis); + case kRegisterAllocatorGraphColor: + return new (allocator) RegisterAllocatorGraphColor(allocator, codegen, analysis); default: LOG(FATAL) << "Invalid register allocation strategy: " << strategy; UNREACHABLE(); @@ -163,6 +166,19 @@ bool RegisterAllocator::ValidateIntervals(const ArenaVector<LiveInterval*>& inte } else { codegen.DumpFloatingPointRegister(message, current->GetRegister()); } + for (LiveInterval* interval : intervals) { + if (interval->HasRegister() + && interval->GetRegister() == current->GetRegister() + && interval->CoversSlow(j)) { + message << std::endl; + if (interval->GetDefinedBy() != nullptr) { + message << interval->GetDefinedBy()->GetKind() << " "; + } else { + message << "physical "; + } + interval->Dump(message); + } + } LOG(FATAL) << message.str(); } else { return false; diff --git a/compiler/optimizing/register_allocator.h b/compiler/optimizing/register_allocator.h index 729eede66e..7e1fff8e2b 100644 --- a/compiler/optimizing/register_allocator.h +++ b/compiler/optimizing/register_allocator.h @@ -40,7 +40,8 @@ class SsaLivenessAnalysis; class RegisterAllocator : public ArenaObject<kArenaAllocRegisterAllocator> { public: enum Strategy { - kRegisterAllocatorLinearScan + kRegisterAllocatorLinearScan, + kRegisterAllocatorGraphColor }; static constexpr Strategy kRegisterAllocatorDefault = kRegisterAllocatorLinearScan; diff --git a/compiler/optimizing/register_allocator_graph_color.cc b/compiler/optimizing/register_allocator_graph_color.cc new file mode 100644 index 0000000000..79ca5a0d86 --- /dev/null +++ b/compiler/optimizing/register_allocator_graph_color.cc @@ -0,0 +1,1012 @@ +/* + * Copyright (C) 2016 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "register_allocator_graph_color.h" + +#include "code_generator.h" +#include "register_allocation_resolver.h" +#include "ssa_liveness_analysis.h" +#include "thread-inl.h" + +namespace art { + +// Highest number of registers that we support for any platform. This can be used for std::bitset, +// for example, which needs to know its size at compile time. +static constexpr size_t kMaxNumRegs = 32; + +// The maximum number of graph coloring attempts before triggering a DCHECK. +// This is meant to catch changes to the graph coloring algorithm that undermine its forward +// progress guarantees. Forward progress for the algorithm means splitting live intervals on +// every graph coloring attempt so that eventually the interference graph will be sparse enough +// to color. The main threat to forward progress is trying to split short intervals which cannot be +// split further; this could cause infinite looping because the interference graph would never +// change. This is avoided by prioritizing short intervals before long ones, so that long +// intervals are split when coloring fails. +static constexpr size_t kMaxGraphColoringAttemptsDebug = 100; + +// Interference nodes make up the interference graph, which is the primary data structure in +// graph coloring register allocation. Each node represents a single live interval, and contains +// a set of adjacent nodes corresponding to intervals overlapping with its own. To save memory, +// pre-colored nodes never contain outgoing edges (only incoming ones). +// +// As nodes are pruned from the interference graph, incoming edges of the pruned node are removed, +// but outgoing edges remain in order to later color the node based on the colors of its neighbors. +// +// Note that a pair interval is represented by a single node in the interference graph, which +// essentially requires two colors. One consequence of this is that the degree of a node is not +// necessarily equal to the number of adjacent nodes--instead, the degree reflects the maximum +// number of colors with which a node could interfere. We model this by giving edges different +// weights (1 or 2) to control how much it increases the degree of adjacent nodes. +// For example, the edge between two single nodes will have weight 1. On the other hand, +// the edge between a single node and a pair node will have weight 2. This is because the pair +// node could block up to two colors for the single node, and because the single node could +// block an entire two-register aligned slot for the pair node. +// The degree is defined this way because we use it to decide whether a node is guaranteed a color, +// and thus whether it is safe to prune it from the interference graph early on. +class InterferenceNode : public ArenaObject<kArenaAllocRegisterAllocator> { + public: + InterferenceNode(ArenaAllocator* allocator, LiveInterval* interval, size_t id) + : interval_(interval), + adjacent_nodes_(CmpPtr, allocator->Adapter(kArenaAllocRegisterAllocator)), + out_degree_(0), + id_(id) {} + + // Used to maintain determinism when storing InterferenceNode pointers in sets. + static bool CmpPtr(const InterferenceNode* lhs, const InterferenceNode* rhs) { + return lhs->id_ < rhs->id_; + } + + void AddInterference(InterferenceNode* other) { + if (adjacent_nodes_.insert(other).second) { + out_degree_ += EdgeWeightWith(other); + } + } + + void RemoveInterference(InterferenceNode* other) { + if (adjacent_nodes_.erase(other) > 0) { + out_degree_ -= EdgeWeightWith(other); + } + } + + bool ContainsInterference(InterferenceNode* other) const { + return adjacent_nodes_.count(other) > 0; + } + + LiveInterval* GetInterval() const { + return interval_; + } + + const ArenaSet<InterferenceNode*, decltype(&CmpPtr)>& GetAdjacentNodes() const { + return adjacent_nodes_; + } + + size_t GetOutDegree() const { + return out_degree_; + } + + size_t GetId() const { + return id_; + } + + private: + // We give extra weight to edges adjacent to pair nodes. See the general comment on the + // interference graph above. + size_t EdgeWeightWith(InterferenceNode* other) const { + return (interval_->HasHighInterval() || other->interval_->HasHighInterval()) ? 2 : 1; + } + + // The live interval that this node represents. + LiveInterval* const interval_; + + // All nodes interfering with this one. + // TODO: There is potential to use a cheaper data structure here, especially since + // adjacency sets will usually be small. + ArenaSet<InterferenceNode*, decltype(&CmpPtr)> adjacent_nodes_; + + // The maximum number of colors with which this node could interfere. This could be more than + // the number of adjacent nodes if this is a pair node, or if some adjacent nodes are pair nodes. + // We use "out" degree because incoming edges come from nodes already pruned from the graph, + // and do not affect the coloring of this node. + size_t out_degree_; + + // A unique identifier for this node, used to maintain determinism when storing + // interference nodes in sets. + const size_t id_; + + // TODO: We could cache the result of interval_->RequiresRegister(), since it + // will not change for the lifetime of this node. (Currently, RequiresRegister() requires + // iterating through all uses of a live interval.) + + DISALLOW_COPY_AND_ASSIGN(InterferenceNode); +}; + +static bool IsCoreInterval(LiveInterval* interval) { + return interval->GetType() != Primitive::kPrimFloat + && interval->GetType() != Primitive::kPrimDouble; +} + +static size_t ComputeReservedArtMethodSlots(const CodeGenerator& codegen) { + return static_cast<size_t>(InstructionSetPointerSize(codegen.GetInstructionSet())) / kVRegSize; +} + +RegisterAllocatorGraphColor::RegisterAllocatorGraphColor(ArenaAllocator* allocator, + CodeGenerator* codegen, + const SsaLivenessAnalysis& liveness) + : RegisterAllocator(allocator, codegen, liveness), + core_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), + fp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), + temp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), + safepoints_(allocator->Adapter(kArenaAllocRegisterAllocator)), + physical_core_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), + physical_fp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), + int_spill_slot_counter_(0), + double_spill_slot_counter_(0), + float_spill_slot_counter_(0), + long_spill_slot_counter_(0), + catch_phi_spill_slot_counter_(0), + reserved_art_method_slots_(ComputeReservedArtMethodSlots(*codegen)), + reserved_out_slots_(codegen->GetGraph()->GetMaximumNumberOfOutVRegs()), + number_of_globally_blocked_core_regs_(0), + number_of_globally_blocked_fp_regs_(0), + max_safepoint_live_core_regs_(0), + max_safepoint_live_fp_regs_(0), + coloring_attempt_allocator_(nullptr) { + // Before we ask for blocked registers, set them up in the code generator. + codegen->SetupBlockedRegisters(); + + // Initialize physical core register live intervals and blocked registers. + // This includes globally blocked registers, such as the stack pointer. + physical_core_intervals_.resize(codegen->GetNumberOfCoreRegisters(), nullptr); + for (size_t i = 0; i < codegen->GetNumberOfCoreRegisters(); ++i) { + LiveInterval* interval = LiveInterval::MakeFixedInterval(allocator_, i, Primitive::kPrimInt); + physical_core_intervals_[i] = interval; + core_intervals_.push_back(interval); + if (codegen_->IsBlockedCoreRegister(i)) { + ++number_of_globally_blocked_core_regs_; + interval->AddRange(0, liveness.GetMaxLifetimePosition()); + } + } + // Initialize physical floating point register live intervals and blocked registers. + physical_fp_intervals_.resize(codegen->GetNumberOfFloatingPointRegisters(), nullptr); + for (size_t i = 0; i < codegen->GetNumberOfFloatingPointRegisters(); ++i) { + LiveInterval* interval = LiveInterval::MakeFixedInterval(allocator_, i, Primitive::kPrimFloat); + physical_fp_intervals_[i] = interval; + fp_intervals_.push_back(interval); + if (codegen_->IsBlockedFloatingPointRegister(i)) { + ++number_of_globally_blocked_fp_regs_; + interval->AddRange(0, liveness.GetMaxLifetimePosition()); + } + } +} + +void RegisterAllocatorGraphColor::AllocateRegisters() { + // (1) Collect and prepare live intervals. + ProcessInstructions(); + + for (bool processing_core_regs : {true, false}) { + ArenaVector<LiveInterval*>& intervals = processing_core_regs + ? core_intervals_ + : fp_intervals_; + size_t num_registers = processing_core_regs + ? codegen_->GetNumberOfCoreRegisters() + : codegen_->GetNumberOfFloatingPointRegisters(); + + size_t attempt = 0; + while (true) { + ++attempt; + DCHECK(attempt <= kMaxGraphColoringAttemptsDebug) + << "Exceeded debug max graph coloring register allocation attempts. " + << "This could indicate that the register allocator is not making forward progress, " + << "which could be caused by prioritizing the wrong live intervals. (Short intervals " + << "should be prioritized over long ones, because they cannot be split further.)"; + + // Reset the allocator for the next coloring attempt. + ArenaAllocator coloring_attempt_allocator(allocator_->GetArenaPool()); + coloring_attempt_allocator_ = &coloring_attempt_allocator; + + // (2) Build the interference graph. + ArenaVector<InterferenceNode*> prunable_nodes( + coloring_attempt_allocator_->Adapter(kArenaAllocRegisterAllocator)); + ArenaVector<InterferenceNode*> safepoints( + coloring_attempt_allocator_->Adapter(kArenaAllocRegisterAllocator)); + BuildInterferenceGraph(intervals, &prunable_nodes, &safepoints); + + // (3) Prune all uncolored nodes from interference graph. + ArenaStdStack<InterferenceNode*> pruned_nodes( + coloring_attempt_allocator_->Adapter(kArenaAllocRegisterAllocator)); + PruneInterferenceGraph(prunable_nodes, num_registers, &pruned_nodes); + + // (4) Color pruned nodes based on interferences. + bool successful = ColorInterferenceGraph(&pruned_nodes, num_registers); + + if (successful) { + // Compute the maximum number of live registers across safepoints. + // Notice that we do not count globally blocked registers, such as the stack pointer. + if (safepoints.size() > 0) { + size_t max_safepoint_live_regs = ComputeMaxSafepointLiveRegisters(safepoints); + if (processing_core_regs) { + max_safepoint_live_core_regs_ = + max_safepoint_live_regs - number_of_globally_blocked_core_regs_; + } else { + max_safepoint_live_fp_regs_= + max_safepoint_live_regs - number_of_globally_blocked_fp_regs_; + } + } + + // Tell the code generator which registers were allocated. + // We only look at prunable_nodes because we already told the code generator about + // fixed intervals while processing instructions. We also ignore the fixed intervals + // placed at the top of catch blocks. + for (InterferenceNode* node : prunable_nodes) { + LiveInterval* interval = node->GetInterval(); + if (interval->HasRegister()) { + Location low_reg = processing_core_regs + ? Location::RegisterLocation(interval->GetRegister()) + : Location::FpuRegisterLocation(interval->GetRegister()); + codegen_->AddAllocatedRegister(low_reg); + if (interval->HasHighInterval()) { + LiveInterval* high = interval->GetHighInterval(); + DCHECK(high->HasRegister()); + Location high_reg = processing_core_regs + ? Location::RegisterLocation(high->GetRegister()) + : Location::FpuRegisterLocation(high->GetRegister()); + codegen_->AddAllocatedRegister(high_reg); + } + } else { + DCHECK(!interval->HasHighInterval() || !interval->GetHighInterval()->HasRegister()); + } + } + + break; + } + } // while unsuccessful + } // for processing_core_instructions + + // (5) Resolve locations and deconstruct SSA form. + RegisterAllocationResolver(allocator_, codegen_, liveness_) + .Resolve(max_safepoint_live_core_regs_, + max_safepoint_live_fp_regs_, + reserved_art_method_slots_ + reserved_out_slots_, + int_spill_slot_counter_, + long_spill_slot_counter_, + float_spill_slot_counter_, + double_spill_slot_counter_, + catch_phi_spill_slot_counter_, + temp_intervals_); + + if (kIsDebugBuild) { + Validate(/*log_fatal_on_failure*/ true); + } +} + +bool RegisterAllocatorGraphColor::Validate(bool log_fatal_on_failure) { + for (bool processing_core_regs : {true, false}) { + ArenaVector<LiveInterval*> intervals( + allocator_->Adapter(kArenaAllocRegisterAllocatorValidate)); + for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { + HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); + LiveInterval* interval = instruction->GetLiveInterval(); + if (interval != nullptr && IsCoreInterval(interval) == processing_core_regs) { + intervals.push_back(instruction->GetLiveInterval()); + } + } + + ArenaVector<LiveInterval*>& physical_intervals = processing_core_regs + ? physical_core_intervals_ + : physical_fp_intervals_; + for (LiveInterval* fixed : physical_intervals) { + if (fixed->GetFirstRange() != nullptr) { + // Ideally we would check fixed ranges as well, but currently there are times when + // two fixed intervals for the same register will overlap. For example, a fixed input + // and a fixed output may sometimes share the same register, in which there will be two + // fixed intervals for the same place. + } + } + + for (LiveInterval* temp : temp_intervals_) { + if (IsCoreInterval(temp) == processing_core_regs) { + intervals.push_back(temp); + } + } + + size_t spill_slots = int_spill_slot_counter_ + + long_spill_slot_counter_ + + float_spill_slot_counter_ + + double_spill_slot_counter_ + + catch_phi_spill_slot_counter_; + bool ok = ValidateIntervals(intervals, + spill_slots, + reserved_art_method_slots_ + reserved_out_slots_, + *codegen_, + allocator_, + processing_core_regs, + log_fatal_on_failure); + if (!ok) { + return false; + } + } // for processing_core_regs + + return true; +} + +void RegisterAllocatorGraphColor::ProcessInstructions() { + for (HLinearPostOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + + // Note that we currently depend on this ordering, since some helper + // code is designed for linear scan register allocation. + for (HBackwardInstructionIterator instr_it(block->GetInstructions()); + !instr_it.Done(); + instr_it.Advance()) { + ProcessInstruction(instr_it.Current()); + } + + for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { + ProcessInstruction(phi_it.Current()); + } + + if (block->IsCatchBlock() || (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) { + // By blocking all registers at the top of each catch block or irreducible loop, we force + // intervals belonging to the live-in set of the catch/header block to be spilled. + // TODO(ngeoffray): Phis in this block could be allocated in register. + size_t position = block->GetLifetimeStart(); + BlockRegisters(position, position + 1); + } + } +} + +void RegisterAllocatorGraphColor::ProcessInstruction(HInstruction* instruction) { + LocationSummary* locations = instruction->GetLocations(); + if (locations == nullptr) { + return; + } + if (locations->NeedsSafepoint() && codegen_->IsLeafMethod()) { + // We do this here because we do not want the suspend check to artificially + // create live registers. + DCHECK(instruction->IsSuspendCheckEntry()); + DCHECK_EQ(locations->GetTempCount(), 0u); + instruction->GetBlock()->RemoveInstruction(instruction); + return; + } + + CheckForTempLiveIntervals(instruction); + CheckForSafepoint(instruction); + if (instruction->GetLocations()->WillCall()) { + // If a call will happen, create fixed intervals for caller-save registers. + // TODO: Note that it may be beneficial to later split intervals at this point, + // so that we allow last-minute moves from a caller-save register + // to a callee-save register. + BlockRegisters(instruction->GetLifetimePosition(), + instruction->GetLifetimePosition() + 1, + /*caller_save_only*/ true); + } + CheckForFixedInputs(instruction); + + LiveInterval* interval = instruction->GetLiveInterval(); + if (interval == nullptr) { + // Instructions lacking a valid output location do not have a live interval. + DCHECK(!locations->Out().IsValid()); + return; + } + + // Low intervals act as representatives for their corresponding high interval. + DCHECK(!interval->IsHighInterval()); + if (codegen_->NeedsTwoRegisters(interval->GetType())) { + interval->AddHighInterval(); + } + AddSafepointsFor(instruction); + CheckForFixedOutput(instruction); + AllocateSpillSlotForCatchPhi(instruction); + + ArenaVector<LiveInterval*>& intervals = IsCoreInterval(interval) + ? core_intervals_ + : fp_intervals_; + if (interval->HasSpillSlot() || instruction->IsConstant()) { + // Note that if an interval already has a spill slot, then its value currently resides + // in the stack (e.g., parameters). Thus we do not have to allocate a register until its first + // register use. This is also true for constants, which can be materialized at any point. + size_t first_register_use = interval->FirstRegisterUse(); + if (first_register_use != kNoLifetime) { + LiveInterval* split = SplitBetween(interval, interval->GetStart(), first_register_use - 1); + intervals.push_back(split); + } else { + // We won't allocate a register for this value. + } + } else { + intervals.push_back(interval); + } +} + +void RegisterAllocatorGraphColor::CheckForFixedInputs(HInstruction* instruction) { + // We simply block physical registers where necessary. + // TODO: Ideally we would coalesce the physical register with the register + // allocated to the input value, but this can be tricky if, e.g., there + // could be multiple physical register uses of the same value at the + // same instruction. Need to think about it more. + LocationSummary* locations = instruction->GetLocations(); + size_t position = instruction->GetLifetimePosition(); + for (size_t i = 0; i < locations->GetInputCount(); ++i) { + Location input = locations->InAt(i); + if (input.IsRegister() || input.IsFpuRegister()) { + BlockRegister(input, position, position + 1); + codegen_->AddAllocatedRegister(input); + } else if (input.IsPair()) { + BlockRegister(input.ToLow(), position, position + 1); + BlockRegister(input.ToHigh(), position, position + 1); + codegen_->AddAllocatedRegister(input.ToLow()); + codegen_->AddAllocatedRegister(input.ToHigh()); + } + } +} + +void RegisterAllocatorGraphColor::CheckForFixedOutput(HInstruction* instruction) { + // If an instruction has a fixed output location, we give the live interval a register and then + // proactively split it just after the definition point to avoid creating too many interferences + // with a fixed node. + LiveInterval* interval = instruction->GetLiveInterval(); + Location out = interval->GetDefinedBy()->GetLocations()->Out(); + size_t position = instruction->GetLifetimePosition(); + DCHECK_GE(interval->GetEnd() - position, 2u); + + if (out.IsUnallocated() && out.GetPolicy() == Location::kSameAsFirstInput) { + out = instruction->GetLocations()->InAt(0); + } + + if (out.IsRegister() || out.IsFpuRegister()) { + interval->SetRegister(out.reg()); + codegen_->AddAllocatedRegister(out); + Split(interval, position + 1); + } else if (out.IsPair()) { + interval->SetRegister(out.low()); + interval->GetHighInterval()->SetRegister(out.high()); + codegen_->AddAllocatedRegister(out.ToLow()); + codegen_->AddAllocatedRegister(out.ToHigh()); + Split(interval, position + 1); + } else if (out.IsStackSlot() || out.IsDoubleStackSlot()) { + interval->SetSpillSlot(out.GetStackIndex()); + } else { + DCHECK(out.IsUnallocated() || out.IsConstant()); + } +} + +void RegisterAllocatorGraphColor::AddSafepointsFor(HInstruction* instruction) { + LiveInterval* interval = instruction->GetLiveInterval(); + for (size_t safepoint_index = safepoints_.size(); safepoint_index > 0; --safepoint_index) { + HInstruction* safepoint = safepoints_[safepoint_index - 1u]; + size_t safepoint_position = safepoint->GetLifetimePosition(); + + // Test that safepoints_ are ordered in the optimal way. + DCHECK(safepoint_index == safepoints_.size() || + safepoints_[safepoint_index]->GetLifetimePosition() < safepoint_position); + + if (safepoint_position == interval->GetStart()) { + // The safepoint is for this instruction, so the location of the instruction + // does not need to be saved. + DCHECK_EQ(safepoint_index, safepoints_.size()); + DCHECK_EQ(safepoint, instruction); + continue; + } else if (interval->IsDeadAt(safepoint_position)) { + break; + } else if (!interval->Covers(safepoint_position)) { + // Hole in the interval. + continue; + } + interval->AddSafepoint(safepoint); + } +} + +void RegisterAllocatorGraphColor::CheckForTempLiveIntervals(HInstruction* instruction) { + LocationSummary* locations = instruction->GetLocations(); + size_t position = instruction->GetLifetimePosition(); + for (size_t i = 0; i < locations->GetTempCount(); ++i) { + Location temp = locations->GetTemp(i); + if (temp.IsRegister() || temp.IsFpuRegister()) { + BlockRegister(temp, position, position + 1); + codegen_->AddAllocatedRegister(temp); + } else { + DCHECK(temp.IsUnallocated()); + switch (temp.GetPolicy()) { + case Location::kRequiresRegister: { + LiveInterval* interval = + LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt); + interval->AddTempUse(instruction, i); + core_intervals_.push_back(interval); + temp_intervals_.push_back(interval); + break; + } + + case Location::kRequiresFpuRegister: { + LiveInterval* interval = + LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimDouble); + interval->AddTempUse(instruction, i); + fp_intervals_.push_back(interval); + temp_intervals_.push_back(interval); + if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { + interval->AddHighInterval(/*is_temp*/ true); + temp_intervals_.push_back(interval->GetHighInterval()); + } + break; + } + + default: + LOG(FATAL) << "Unexpected policy for temporary location " + << temp.GetPolicy(); + } + } + } +} + +void RegisterAllocatorGraphColor::CheckForSafepoint(HInstruction* instruction) { + LocationSummary* locations = instruction->GetLocations(); + size_t position = instruction->GetLifetimePosition(); + + if (locations->NeedsSafepoint()) { + safepoints_.push_back(instruction); + if (locations->OnlyCallsOnSlowPath()) { + // We add a synthesized range at this position to record the live registers + // at this position. Ideally, we could just update the safepoints when locations + // are updated, but we currently need to know the full stack size before updating + // locations (because of parameters and the fact that we don't have a frame pointer). + // And knowing the full stack size requires to know the maximum number of live + // registers at calls in slow paths. + // By adding the following interval in the algorithm, we can compute this + // maximum before updating locations. + LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction); + interval->AddRange(position, position + 1); + core_intervals_.push_back(interval); + fp_intervals_.push_back(interval); + } + } +} + +LiveInterval* RegisterAllocatorGraphColor::TrySplit(LiveInterval* interval, size_t position) { + if (interval->GetStart() < position && position < interval->GetEnd()) { + return Split(interval, position); + } else { + return interval; + } +} + +void RegisterAllocatorGraphColor::SplitAtRegisterUses(LiveInterval* interval) { + DCHECK(!interval->IsHighInterval()); + + // Split just after a register definition. + if (interval->IsParent() && interval->DefinitionRequiresRegister()) { + interval = TrySplit(interval, interval->GetStart() + 1); + } + + UsePosition* use = interval->GetFirstUse(); + while (use != nullptr && use->GetPosition() < interval->GetStart()) { + use = use->GetNext(); + } + + // Split around register uses. + size_t end = interval->GetEnd(); + while (use != nullptr && use->GetPosition() <= end) { + if (use->RequiresRegister()) { + size_t position = use->GetPosition(); + interval = TrySplit(interval, position - 1); + if (liveness_.GetInstructionFromPosition(position / 2)->IsControlFlow()) { + // If we are at the very end of a basic block, we cannot split right + // at the use. Split just after instead. + interval = TrySplit(interval, position + 1); + } else { + interval = TrySplit(interval, position); + } + } + use = use->GetNext(); + } +} + +void RegisterAllocatorGraphColor::AllocateSpillSlotForCatchPhi(HInstruction* instruction) { + if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) { + HPhi* phi = instruction->AsPhi(); + LiveInterval* interval = phi->GetLiveInterval(); + + HInstruction* previous_phi = phi->GetPrevious(); + DCHECK(previous_phi == nullptr || + previous_phi->AsPhi()->GetRegNumber() <= phi->GetRegNumber()) + << "Phis expected to be sorted by vreg number, " + << "so that equivalent phis are adjacent."; + + if (phi->IsVRegEquivalentOf(previous_phi)) { + // Assign the same spill slot. + DCHECK(previous_phi->GetLiveInterval()->HasSpillSlot()); + interval->SetSpillSlot(previous_phi->GetLiveInterval()->GetSpillSlot()); + } else { + interval->SetSpillSlot(catch_phi_spill_slot_counter_); + catch_phi_spill_slot_counter_ += interval->NeedsTwoSpillSlots() ? 2 : 1; + } + } +} + +void RegisterAllocatorGraphColor::BlockRegister(Location location, + size_t start, + size_t end) { + DCHECK(location.IsRegister() || location.IsFpuRegister()); + int reg = location.reg(); + LiveInterval* interval = location.IsRegister() + ? physical_core_intervals_[reg] + : physical_fp_intervals_[reg]; + DCHECK(interval->GetRegister() == reg); + bool blocked_by_codegen = location.IsRegister() + ? codegen_->IsBlockedCoreRegister(reg) + : codegen_->IsBlockedFloatingPointRegister(reg); + if (blocked_by_codegen) { + // We've already blocked this register for the entire method. (And adding a + // range inside another range violates the preconditions of AddRange). + } else { + interval->AddRange(start, end); + } +} + +void RegisterAllocatorGraphColor::BlockRegisters(size_t start, size_t end, bool caller_save_only) { + for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) { + if (!caller_save_only || !codegen_->IsCoreCalleeSaveRegister(i)) { + BlockRegister(Location::RegisterLocation(i), start, end); + } + } + for (size_t i = 0; i < codegen_->GetNumberOfFloatingPointRegisters(); ++i) { + if (!caller_save_only || !codegen_->IsFloatingPointCalleeSaveRegister(i)) { + BlockRegister(Location::FpuRegisterLocation(i), start, end); + } + } +} + +// Add an interference edge, but only if necessary. +static void AddPotentialInterference(InterferenceNode* from, InterferenceNode* to) { + if (from->GetInterval()->HasRegister()) { + // We save space by ignoring outgoing edges from fixed nodes. + } else if (to->GetInterval()->IsSlowPathSafepoint()) { + // Safepoint intervals are only there to count max live registers, + // so no need to give them incoming interference edges. + // This is also necessary for correctness, because we don't want nodes + // to remove themselves from safepoint adjacency sets when they're pruned. + } else { + from->AddInterference(to); + } +} + +// TODO: See locations->OutputCanOverlapWithInputs(); we may want to consider +// this when building the interference graph. +void RegisterAllocatorGraphColor::BuildInterferenceGraph( + const ArenaVector<LiveInterval*>& intervals, + ArenaVector<InterferenceNode*>* prunable_nodes, + ArenaVector<InterferenceNode*>* safepoints) { + size_t interval_id_counter = 0; + + // Build the interference graph efficiently by ordering range endpoints + // by position and doing a linear sweep to find interferences. (That is, we + // jump from endpoint to endpoint, maintaining a set of intervals live at each + // point. If two nodes are ever in the live set at the same time, then they + // interfere with each other.) + // + // We order by both position and (secondarily) by whether the endpoint + // begins or ends a range; we want to process range endings before range + // beginnings at the same position because they should not conflict. + // + // For simplicity, we create a tuple for each endpoint, and then sort the tuples. + // Tuple contents: (position, is_range_beginning, node). + ArenaVector<std::tuple<size_t, bool, InterferenceNode*>> range_endpoints( + coloring_attempt_allocator_->Adapter(kArenaAllocRegisterAllocator)); + for (LiveInterval* parent : intervals) { + for (LiveInterval* sibling = parent; sibling != nullptr; sibling = sibling->GetNextSibling()) { + LiveRange* range = sibling->GetFirstRange(); + if (range != nullptr) { + InterferenceNode* node = new (coloring_attempt_allocator_) InterferenceNode( + coloring_attempt_allocator_, sibling, interval_id_counter++); + if (sibling->HasRegister()) { + // Fixed nodes will never be pruned, so no need to keep track of them. + } else if (sibling->IsSlowPathSafepoint()) { + // Safepoint intervals are synthesized to count max live registers. + // They will be processed separately after coloring. + safepoints->push_back(node); + } else { + prunable_nodes->push_back(node); + } + + while (range != nullptr) { + range_endpoints.push_back(std::make_tuple(range->GetStart(), true, node)); + range_endpoints.push_back(std::make_tuple(range->GetEnd(), false, node)); + range = range->GetNext(); + } + } + } + } + + // Sort the endpoints. + std::sort(range_endpoints.begin(), range_endpoints.end()); + + // Nodes live at the current position in the linear sweep. + ArenaSet<InterferenceNode*, decltype(&InterferenceNode::CmpPtr)> live( + InterferenceNode::CmpPtr, coloring_attempt_allocator_->Adapter(kArenaAllocRegisterAllocator)); + + // Linear sweep. When we encounter the beginning of a range, we add the corresponding node to the + // live set. When we encounter the end of a range, we remove the corresponding node + // from the live set. Nodes interfere if they are in the live set at the same time. + for (auto it = range_endpoints.begin(); it != range_endpoints.end(); ++it) { + bool is_range_beginning; + InterferenceNode* node; + // Extract information from the tuple, including the node this tuple represents. + std::tie(std::ignore, is_range_beginning, node) = *it; + + if (is_range_beginning) { + for (InterferenceNode* conflicting : live) { + DCHECK_NE(node, conflicting); + AddPotentialInterference(node, conflicting); + AddPotentialInterference(conflicting, node); + } + DCHECK_EQ(live.count(node), 0u); + live.insert(node); + } else { + // End of range. + DCHECK_EQ(live.count(node), 1u); + live.erase(node); + } + } + DCHECK(live.empty()); +} + +// The order in which we color nodes is vital to both correctness (forward +// progress) and code quality. Specifically, we must prioritize intervals +// that require registers, and after that we must prioritize short intervals. +// That way, if we fail to color a node, it either won't require a register, +// or it will be a long interval that can be split in order to make the +// interference graph sparser. +// TODO: May also want to consider: +// - Loop depth +// - Constants (since they can be rematerialized) +// - Allocated spill slots +static bool GreaterNodePriority(const InterferenceNode* lhs, + const InterferenceNode* rhs) { + LiveInterval* lhs_interval = lhs->GetInterval(); + LiveInterval* rhs_interval = rhs->GetInterval(); + + // (1) Choose the interval that requires a register. + if (lhs_interval->RequiresRegister() != rhs_interval->RequiresRegister()) { + return lhs_interval->RequiresRegister(); + } + + // (2) Choose the interval that has a shorter life span. + if (lhs_interval->GetLength() != rhs_interval->GetLength()) { + return lhs_interval->GetLength() < rhs_interval->GetLength(); + } + + // (3) Just choose the interval based on a deterministic ordering. + return InterferenceNode::CmpPtr(lhs, rhs); +} + +void RegisterAllocatorGraphColor::PruneInterferenceGraph( + const ArenaVector<InterferenceNode*>& prunable_nodes, + size_t num_regs, + ArenaStdStack<InterferenceNode*>* pruned_nodes) { + // When pruning the graph, we refer to nodes with degree less than num_regs as low degree nodes, + // and all others as high degree nodes. The distinction is important: low degree nodes are + // guaranteed a color, while high degree nodes are not. + + // Low-degree nodes are guaranteed a color, so worklist order does not matter. + ArenaDeque<InterferenceNode*> low_degree_worklist( + coloring_attempt_allocator_->Adapter(kArenaAllocRegisterAllocator)); + + // If we have to prune from the high-degree worklist, we cannot guarantee + // the pruned node a color. So, we order the worklist by priority. + ArenaSet<InterferenceNode*, decltype(&GreaterNodePriority)> high_degree_worklist( + GreaterNodePriority, coloring_attempt_allocator_->Adapter(kArenaAllocRegisterAllocator)); + + // Build worklists. + for (InterferenceNode* node : prunable_nodes) { + DCHECK(!node->GetInterval()->HasRegister()) + << "Fixed nodes should never be pruned"; + DCHECK(!node->GetInterval()->IsSlowPathSafepoint()) + << "Safepoint nodes should never be pruned"; + if (node->GetOutDegree() < num_regs) { + low_degree_worklist.push_back(node); + } else { + high_degree_worklist.insert(node); + } + } + + // Helper function to prune an interval from the interference graph, + // which includes updating the worklists. + auto prune_node = [this, + num_regs, + &pruned_nodes, + &low_degree_worklist, + &high_degree_worklist] (InterferenceNode* node) { + DCHECK(!node->GetInterval()->HasRegister()); + pruned_nodes->push(node); + for (InterferenceNode* adjacent : node->GetAdjacentNodes()) { + DCHECK(!adjacent->GetInterval()->IsSlowPathSafepoint()) + << "Nodes should never interfere with synthesized safepoint nodes"; + if (adjacent->GetInterval()->HasRegister()) { + // No effect on pre-colored nodes; they're never pruned. + } else { + bool was_high_degree = adjacent->GetOutDegree() >= num_regs; + DCHECK(adjacent->ContainsInterference(node)) + << "Missing incoming interference edge from non-fixed node"; + adjacent->RemoveInterference(node); + if (was_high_degree && adjacent->GetOutDegree() < num_regs) { + // This is a transition from high degree to low degree. + DCHECK_EQ(high_degree_worklist.count(adjacent), 1u); + high_degree_worklist.erase(adjacent); + low_degree_worklist.push_back(adjacent); + } + } + } + }; + + // Prune graph. + while (!low_degree_worklist.empty() || !high_degree_worklist.empty()) { + while (!low_degree_worklist.empty()) { + InterferenceNode* node = low_degree_worklist.front(); + // TODO: pop_back() should work as well, but it doesn't; we get a + // failed check while pruning. We should look into this. + low_degree_worklist.pop_front(); + prune_node(node); + } + if (!high_degree_worklist.empty()) { + // We prune the lowest-priority node, because pruning a node earlier + // gives it a higher chance of being spilled. + InterferenceNode* node = *high_degree_worklist.rbegin(); + high_degree_worklist.erase(node); + prune_node(node); + } + } +} + +// Build a mask with a bit set for each register assigned to some +// interval in `intervals`. +template <typename Container> +static std::bitset<kMaxNumRegs> BuildConflictMask(Container& intervals) { + std::bitset<kMaxNumRegs> conflict_mask; + for (InterferenceNode* adjacent : intervals) { + LiveInterval* conflicting = adjacent->GetInterval(); + if (conflicting->HasRegister()) { + conflict_mask.set(conflicting->GetRegister()); + if (conflicting->HasHighInterval()) { + DCHECK(conflicting->GetHighInterval()->HasRegister()); + conflict_mask.set(conflicting->GetHighInterval()->GetRegister()); + } + } else { + DCHECK(!conflicting->HasHighInterval() + || !conflicting->GetHighInterval()->HasRegister()); + } + } + return conflict_mask; +} + +bool RegisterAllocatorGraphColor::ColorInterferenceGraph( + ArenaStdStack<InterferenceNode*>* pruned_nodes, + size_t num_regs) { + DCHECK_LE(num_regs, kMaxNumRegs) << "kMaxNumRegs is too small"; + ArenaVector<LiveInterval*> colored_intervals( + coloring_attempt_allocator_->Adapter(kArenaAllocRegisterAllocator)); + bool successful = true; + + while (!pruned_nodes->empty()) { + InterferenceNode* node = pruned_nodes->top(); + pruned_nodes->pop(); + LiveInterval* interval = node->GetInterval(); + + // Search for free register(s). + // Note that the graph coloring allocator assumes that pair intervals are aligned here, + // excluding pre-colored pair intervals (which can currently be unaligned on x86). + std::bitset<kMaxNumRegs> conflict_mask = BuildConflictMask(node->GetAdjacentNodes()); + size_t reg = 0; + if (interval->HasHighInterval()) { + while (reg < num_regs - 1 && (conflict_mask[reg] || conflict_mask[reg + 1])) { + reg += 2; + } + } else { + // We use CTZ (count trailing zeros) to quickly find the lowest available register. + // Note that CTZ is undefined for 0, so we special-case it. + reg = conflict_mask.all() ? conflict_mask.size() : CTZ(~conflict_mask.to_ulong()); + } + + if (reg < (interval->HasHighInterval() ? num_regs - 1 : num_regs)) { + // Assign register. + DCHECK(!interval->HasRegister()); + interval->SetRegister(reg); + colored_intervals.push_back(interval); + if (interval->HasHighInterval()) { + DCHECK(!interval->GetHighInterval()->HasRegister()); + interval->GetHighInterval()->SetRegister(reg + 1); + colored_intervals.push_back(interval->GetHighInterval()); + } + } else if (interval->RequiresRegister()) { + // The interference graph is too dense to color. Make it sparser by + // splitting this live interval. + successful = false; + SplitAtRegisterUses(interval); + // We continue coloring, because there may be additional intervals that cannot + // be colored, and that we should split. + } else { + // Spill. + AllocateSpillSlotFor(interval); + } + } + + // If unsuccessful, reset all register assignments. + if (!successful) { + for (LiveInterval* interval : colored_intervals) { + interval->ClearRegister(); + } + } + + return successful; +} + +size_t RegisterAllocatorGraphColor::ComputeMaxSafepointLiveRegisters( + const ArenaVector<InterferenceNode*>& safepoints) { + size_t max_safepoint_live_regs = 0; + for (InterferenceNode* safepoint : safepoints) { + DCHECK(safepoint->GetInterval()->IsSlowPathSafepoint()); + std::bitset<kMaxNumRegs> conflict_mask = BuildConflictMask(safepoint->GetAdjacentNodes()); + size_t live_regs = conflict_mask.count(); + max_safepoint_live_regs = std::max(max_safepoint_live_regs, live_regs); + } + return max_safepoint_live_regs; +} + +void RegisterAllocatorGraphColor::AllocateSpillSlotFor(LiveInterval* interval) { + LiveInterval* parent = interval->GetParent(); + HInstruction* defined_by = parent->GetDefinedBy(); + if (parent->HasSpillSlot()) { + // We already have a spill slot for this value that we can reuse. + } else if (defined_by->IsParameterValue()) { + // Parameters already have a stack slot. + parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); + } else if (defined_by->IsCurrentMethod()) { + // The current method is always at spill slot 0. + parent->SetSpillSlot(0); + } else if (defined_by->IsConstant()) { + // Constants don't need a spill slot. + } else { + // Allocate a spill slot based on type. + size_t* spill_slot_counter; + switch (interval->GetType()) { + case Primitive::kPrimDouble: + spill_slot_counter = &double_spill_slot_counter_; + break; + case Primitive::kPrimLong: + spill_slot_counter = &long_spill_slot_counter_; + break; + case Primitive::kPrimFloat: + spill_slot_counter = &float_spill_slot_counter_; + break; + case Primitive::kPrimNot: + case Primitive::kPrimInt: + case Primitive::kPrimChar: + case Primitive::kPrimByte: + case Primitive::kPrimBoolean: + case Primitive::kPrimShort: + spill_slot_counter = &int_spill_slot_counter_; + break; + case Primitive::kPrimVoid: + LOG(FATAL) << "Unexpected type for interval " << interval->GetType(); + UNREACHABLE(); + } + + parent->SetSpillSlot(*spill_slot_counter); + *spill_slot_counter += parent->NeedsTwoSpillSlots() ? 2 : 1; + // TODO: Could color stack slots if we wanted to, even if + // it's just a trivial coloring. See the linear scan implementation, + // which simply reuses spill slots for values whose live intervals + // have already ended. + } +} + +} // namespace art diff --git a/compiler/optimizing/register_allocator_graph_color.h b/compiler/optimizing/register_allocator_graph_color.h new file mode 100644 index 0000000000..0b5af96b40 --- /dev/null +++ b/compiler/optimizing/register_allocator_graph_color.h @@ -0,0 +1,197 @@ +/* + * Copyright (C) 2016 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_GRAPH_COLOR_H_ +#define ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_GRAPH_COLOR_H_ + +#include "arch/instruction_set.h" +#include "base/arena_containers.h" +#include "base/arena_object.h" +#include "base/macros.h" +#include "primitive.h" +#include "register_allocator.h" + +namespace art { + +class CodeGenerator; +class HBasicBlock; +class HGraph; +class HInstruction; +class HParallelMove; +class Location; +class SsaLivenessAnalysis; +class InterferenceNode; + +/** + * A graph coloring register allocator. + * + * The algorithm proceeds as follows: + * (1) Build an interference graph, where nodes represent live intervals, and edges represent + * interferences between two intervals. Coloring this graph with k colors is isomorphic to + * finding a valid register assignment with k registers. + * (2) To color the graph, first prune all nodes with degree less than k, since these nodes are + * guaranteed a color. (No matter how we color their adjacent nodes, we can give them a + * different color.) As we prune nodes from the graph, more nodes may drop below degree k, + * enabling further pruning. The key is to maintain the pruning order in a stack, so that we + * can color the nodes in the reverse order. + * When there are no more nodes with degree less than k, we start pruning alternate nodes based + * on heuristics. Since these nodes are not guaranteed a color, we are careful to + * prioritize nodes that require a register. We also prioritize short intervals, because + * short intervals cannot be split very much if coloring fails (see below). "Prioritizing" + * a node amounts to pruning it later, since it will have fewer interferences if we prune other + * nodes first. + * (3) We color nodes in the reverse order in which we pruned them. If we cannot assign + * a node a color, we do one of two things: + * - If the node requires a register, we consider the current coloring attempt a failure. + * However, we split the node's live interval in order to make the interference graph + * sparser, so that future coloring attempts may succeed. + * - If the node does not require a register, we simply assign it a location on the stack. + * + * A good reference for graph coloring register allocation is + * "Modern Compiler Implementation in Java" (Andrew W. Appel, 2nd Edition). + */ +class RegisterAllocatorGraphColor : public RegisterAllocator { + public: + RegisterAllocatorGraphColor(ArenaAllocator* allocator, + CodeGenerator* codegen, + const SsaLivenessAnalysis& analysis); + ~RegisterAllocatorGraphColor() OVERRIDE {} + + void AllocateRegisters() OVERRIDE; + + bool Validate(bool log_fatal_on_failure); + + private: + // Collect all intervals and prepare for register allocation. + void ProcessInstructions(); + void ProcessInstruction(HInstruction* instruction); + + // If any inputs require specific registers, block those registers + // at the position of this instruction. + void CheckForFixedInputs(HInstruction* instruction); + + // If the output of an instruction requires a specific register, split + // the interval and assign the register to the first part. + void CheckForFixedOutput(HInstruction* instruction); + + // Add all applicable safepoints to a live interval. + // Currently depends on instruction processing order. + void AddSafepointsFor(HInstruction* instruction); + + // Collect all live intervals associated with the temporary locations + // needed by an instruction. + void CheckForTempLiveIntervals(HInstruction* instruction); + + // If a safe point is needed, add a synthesized interval to later record + // the number of live registers at this point. + void CheckForSafepoint(HInstruction* instruction); + + // Split an interval, but only if `position` is inside of `interval`. + // Return either the new interval, or the original interval if not split. + static LiveInterval* TrySplit(LiveInterval* interval, size_t position); + + // To ensure every graph can be colored, split live intervals + // at their register defs and uses. This creates short intervals with low + // degree in the interference graph, which are prioritized during graph + // coloring. + void SplitAtRegisterUses(LiveInterval* interval); + + // If the given instruction is a catch phi, give it a spill slot. + void AllocateSpillSlotForCatchPhi(HInstruction* instruction); + + // Ensure that the given register cannot be allocated for a given range. + void BlockRegister(Location location, size_t start, size_t end); + void BlockRegisters(size_t start, size_t end, bool caller_save_only = false); + + // Use the intervals collected from instructions to construct an + // interference graph mapping intervals to adjacency lists. + // Also, collect synthesized safepoint nodes, used to keep + // track of live intervals across safepoints. + void BuildInterferenceGraph(const ArenaVector<LiveInterval*>& intervals, + ArenaVector<InterferenceNode*>* prunable_nodes, + ArenaVector<InterferenceNode*>* safepoints); + + // Prune nodes from the interference graph to be colored later. Build + // a stack (pruned_nodes) containing these intervals in an order determined + // by various heuristics. + void PruneInterferenceGraph(const ArenaVector<InterferenceNode*>& prunable_nodes, + size_t num_registers, + ArenaStdStack<InterferenceNode*>* pruned_nodes); + + // Process pruned_intervals to color the interference graph, spilling when + // necessary. Return true if successful. Else, split some intervals to make + // the interference graph sparser. + bool ColorInterferenceGraph(ArenaStdStack<InterferenceNode*>* pruned_nodes, + size_t num_registers); + + // Return the maximum number of registers live at safepoints, + // based on the outgoing interference edges of safepoint nodes. + size_t ComputeMaxSafepointLiveRegisters(const ArenaVector<InterferenceNode*>& safepoints); + + // If necessary, add the given interval to the list of spilled intervals, + // and make sure it's ready to be spilled to the stack. + void AllocateSpillSlotFor(LiveInterval* interval); + + // Live intervals, split by kind (core and floating point). + // These should not contain high intervals, as those are represented by + // the corresponding low interval throughout register allocation. + ArenaVector<LiveInterval*> core_intervals_; + ArenaVector<LiveInterval*> fp_intervals_; + + // Intervals for temporaries, saved for special handling in the resolution phase. + ArenaVector<LiveInterval*> temp_intervals_; + + // Safepoints, saved for special handling while processing instructions. + ArenaVector<HInstruction*> safepoints_; + + // Live intervals for specific registers. These become pre-colored nodes + // in the interference graph. + ArenaVector<LiveInterval*> physical_core_intervals_; + ArenaVector<LiveInterval*> physical_fp_intervals_; + + // Allocated stack slot counters. + size_t int_spill_slot_counter_; + size_t double_spill_slot_counter_; + size_t float_spill_slot_counter_; + size_t long_spill_slot_counter_; + size_t catch_phi_spill_slot_counter_; + + // Number of stack slots needed for the pointer to the current method. + // This is 1 for 32-bit architectures, and 2 for 64-bit architectures. + const size_t reserved_art_method_slots_; + + // Number of stack slots needed for outgoing arguments. + const size_t reserved_out_slots_; + + // The number of globally blocked core and floating point registers, such as the stack pointer. + size_t number_of_globally_blocked_core_regs_; + size_t number_of_globally_blocked_fp_regs_; + + // The maximum number of registers live at safe points. Needed by the code generator. + size_t max_safepoint_live_core_regs_; + size_t max_safepoint_live_fp_regs_; + + // An arena allocator used for a single graph coloring attempt. + // Many data structures are cleared between graph coloring attempts, so we reduce + // total memory usage by using a new arena allocator for each attempt. + ArenaAllocator* coloring_attempt_allocator_; + + DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorGraphColor); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_GRAPH_COLOR_H_ diff --git a/compiler/optimizing/register_allocator_linear_scan.h b/compiler/optimizing/register_allocator_linear_scan.h index b6e4f92e42..1a643a0d1a 100644 --- a/compiler/optimizing/register_allocator_linear_scan.h +++ b/compiler/optimizing/register_allocator_linear_scan.h @@ -43,6 +43,7 @@ class RegisterAllocatorLinearScan : public RegisterAllocator { RegisterAllocatorLinearScan(ArenaAllocator* allocator, CodeGenerator* codegen, const SsaLivenessAnalysis& analysis); + ~RegisterAllocatorLinearScan() OVERRIDE {} void AllocateRegisters() OVERRIDE; diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc index cbb7b2f1c5..55ea99e592 100644 --- a/compiler/optimizing/register_allocator_test.cc +++ b/compiler/optimizing/register_allocator_test.cc @@ -31,12 +31,29 @@ namespace art { +using Strategy = RegisterAllocator::Strategy; + // Note: the register allocator tests rely on the fact that constants have live // intervals and registers get allocated to them. -class RegisterAllocatorTest : public CommonCompilerTest {}; +class RegisterAllocatorTest : public CommonCompilerTest { + protected: + // These functions need to access private variables of LocationSummary, so we declare it + // as a member of RegisterAllocatorTest, which we make a friend class. + static void SameAsFirstInputHint(Strategy strategy); + static void ExpectedInRegisterHint(Strategy strategy); +}; + +// This macro should include all register allocation strategies that should be tested. +#define TEST_ALL_STRATEGIES(test_name)\ +TEST_F(RegisterAllocatorTest, test_name##_LinearScan) {\ + test_name(Strategy::kRegisterAllocatorLinearScan);\ +}\ +TEST_F(RegisterAllocatorTest, test_name##_GraphColor) {\ + test_name(Strategy::kRegisterAllocatorGraphColor);\ +} -static bool Check(const uint16_t* data) { +static bool Check(const uint16_t* data, Strategy strategy) { ArenaPool pool; ArenaAllocator allocator(&pool); HGraph* graph = CreateCFG(&allocator, data); @@ -45,7 +62,8 @@ static bool Check(const uint16_t* data) { x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); SsaLivenessAnalysis liveness(graph, &codegen); liveness.Analyze(); - RegisterAllocator* register_allocator = RegisterAllocator::Create(&allocator, &codegen, liveness); + RegisterAllocator* register_allocator = + RegisterAllocator::Create(&allocator, &codegen, liveness, strategy); register_allocator->AllocateRegisters(); return register_allocator->Validate(false); } @@ -143,7 +161,7 @@ TEST_F(RegisterAllocatorTest, ValidateIntervals) { } } -TEST_F(RegisterAllocatorTest, CFG1) { +static void CFG1(Strategy strategy) { /* * Test the following snippet: * return 0; @@ -160,10 +178,12 @@ TEST_F(RegisterAllocatorTest, CFG1) { Instruction::CONST_4 | 0 | 0, Instruction::RETURN); - ASSERT_TRUE(Check(data)); + ASSERT_TRUE(Check(data, strategy)); } -TEST_F(RegisterAllocatorTest, Loop1) { +TEST_ALL_STRATEGIES(CFG1); + +static void Loop1(Strategy strategy) { /* * Test the following snippet: * int a = 0; @@ -199,10 +219,12 @@ TEST_F(RegisterAllocatorTest, Loop1) { Instruction::CONST_4 | 5 << 12 | 1 << 8, Instruction::RETURN | 1 << 8); - ASSERT_TRUE(Check(data)); + ASSERT_TRUE(Check(data, strategy)); } -TEST_F(RegisterAllocatorTest, Loop2) { +TEST_ALL_STRATEGIES(Loop1); + +static void Loop2(Strategy strategy) { /* * Test the following snippet: * int a = 0; @@ -248,10 +270,12 @@ TEST_F(RegisterAllocatorTest, Loop2) { Instruction::ADD_INT, 1 << 8 | 0, Instruction::RETURN | 1 << 8); - ASSERT_TRUE(Check(data)); + ASSERT_TRUE(Check(data, strategy)); } -TEST_F(RegisterAllocatorTest, Loop3) { +TEST_ALL_STRATEGIES(Loop2); + +static void Loop3(Strategy strategy) { /* * Test the following snippet: * int a = 0 @@ -296,7 +320,8 @@ TEST_F(RegisterAllocatorTest, Loop3) { x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); SsaLivenessAnalysis liveness(graph, &codegen); liveness.Analyze(); - RegisterAllocator* register_allocator = RegisterAllocator::Create(&allocator, &codegen, liveness); + RegisterAllocator* register_allocator = + RegisterAllocator::Create(&allocator, &codegen, liveness, strategy); register_allocator->AllocateRegisters(); ASSERT_TRUE(register_allocator->Validate(false)); @@ -314,6 +339,8 @@ TEST_F(RegisterAllocatorTest, Loop3) { ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister()); } +TEST_ALL_STRATEGIES(Loop3); + TEST_F(RegisterAllocatorTest, FirstRegisterUse) { const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 | 0, @@ -354,7 +381,7 @@ TEST_F(RegisterAllocatorTest, FirstRegisterUse) { ASSERT_EQ(new_interval->FirstRegisterUse(), last_xor->GetLifetimePosition()); } -TEST_F(RegisterAllocatorTest, DeadPhi) { +static void DeadPhi(Strategy strategy) { /* 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. @@ -385,15 +412,19 @@ TEST_F(RegisterAllocatorTest, DeadPhi) { x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); SsaLivenessAnalysis liveness(graph, &codegen); liveness.Analyze(); - RegisterAllocator* register_allocator = RegisterAllocator::Create(&allocator, &codegen, liveness); + RegisterAllocator* register_allocator = + RegisterAllocator::Create(&allocator, &codegen, liveness, strategy); register_allocator->AllocateRegisters(); ASSERT_TRUE(register_allocator->Validate(false)); } +TEST_ALL_STRATEGIES(DeadPhi); + /** * Test that the TryAllocateFreeReg method works in the presence of inactive intervals * 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. + * This test only applies to the linear scan allocator. */ TEST_F(RegisterAllocatorTest, FreeUntil) { const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( @@ -507,15 +538,15 @@ static HGraph* BuildIfElseWithPhi(ArenaAllocator* allocator, graph->GetDexFile(), dex_cache, 0); -*input2 = new (allocator) HInstanceFieldGet(parameter, - Primitive::kPrimInt, - MemberOffset(42), - false, - kUnknownFieldIndex, - kUnknownClassDefIndex, - graph->GetDexFile(), - dex_cache, - 0); + *input2 = new (allocator) HInstanceFieldGet(parameter, + Primitive::kPrimInt, + MemberOffset(42), + false, + kUnknownFieldIndex, + kUnknownClassDefIndex, + graph->GetDexFile(), + dex_cache, + 0); then->AddInstruction(*input1); else_->AddInstruction(*input2); join->AddInstruction(new (allocator) HExit()); @@ -527,7 +558,7 @@ static HGraph* BuildIfElseWithPhi(ArenaAllocator* allocator, return graph; } -TEST_F(RegisterAllocatorTest, PhiHint) { +static void PhiHint(Strategy strategy) { ArenaPool pool; ArenaAllocator allocator(&pool); HPhi *phi; @@ -543,7 +574,7 @@ TEST_F(RegisterAllocatorTest, PhiHint) { // Check that the register allocator is deterministic. RegisterAllocator* register_allocator = - RegisterAllocator::Create(&allocator, &codegen, liveness); + RegisterAllocator::Create(&allocator, &codegen, liveness, strategy); register_allocator->AllocateRegisters(); ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 0); @@ -563,7 +594,7 @@ TEST_F(RegisterAllocatorTest, PhiHint) { // the same register. phi->GetLocations()->UpdateOut(Location::RegisterLocation(2)); RegisterAllocator* register_allocator = - RegisterAllocator::Create(&allocator, &codegen, liveness); + RegisterAllocator::Create(&allocator, &codegen, liveness, strategy); register_allocator->AllocateRegisters(); ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2); @@ -583,7 +614,7 @@ TEST_F(RegisterAllocatorTest, PhiHint) { // the same register. input1->GetLocations()->UpdateOut(Location::RegisterLocation(2)); RegisterAllocator* register_allocator = - RegisterAllocator::Create(&allocator, &codegen, liveness); + RegisterAllocator::Create(&allocator, &codegen, liveness, strategy); register_allocator->AllocateRegisters(); ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2); @@ -603,7 +634,7 @@ TEST_F(RegisterAllocatorTest, PhiHint) { // the same register. input2->GetLocations()->UpdateOut(Location::RegisterLocation(2)); RegisterAllocator* register_allocator = - RegisterAllocator::Create(&allocator, &codegen, liveness); + RegisterAllocator::Create(&allocator, &codegen, liveness, strategy); register_allocator->AllocateRegisters(); ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2); @@ -612,6 +643,12 @@ TEST_F(RegisterAllocatorTest, PhiHint) { } } +// TODO: Enable this test for graph coloring register allocation when iterative move +// coalescing is merged. +TEST_F(RegisterAllocatorTest, PhiHint_LinearScan) { + PhiHint(Strategy::kRegisterAllocatorLinearScan); +} + static HGraph* BuildFieldReturn(ArenaAllocator* allocator, HInstruction** field, HInstruction** ret) { @@ -650,7 +687,7 @@ static HGraph* BuildFieldReturn(ArenaAllocator* allocator, return graph; } -TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint) { +void RegisterAllocatorTest::ExpectedInRegisterHint(Strategy strategy) { ArenaPool pool; ArenaAllocator allocator(&pool); HInstruction *field, *ret; @@ -664,7 +701,7 @@ TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint) { liveness.Analyze(); RegisterAllocator* register_allocator = - RegisterAllocator::Create(&allocator, &codegen, liveness); + RegisterAllocator::Create(&allocator, &codegen, liveness, strategy); register_allocator->AllocateRegisters(); // Sanity check that in normal conditions, the register should be hinted to 0 (EAX). @@ -684,13 +721,19 @@ TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint) { ret->GetLocations()->inputs_[0] = Location::RegisterLocation(2); RegisterAllocator* register_allocator = - RegisterAllocator::Create(&allocator, &codegen, liveness); + RegisterAllocator::Create(&allocator, &codegen, liveness, strategy); register_allocator->AllocateRegisters(); ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 2); } } +// TODO: Enable this test for graph coloring register allocation when iterative move +// coalescing is merged. +TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint_LinearScan) { + ExpectedInRegisterHint(Strategy::kRegisterAllocatorLinearScan); +} + static HGraph* BuildTwoSubs(ArenaAllocator* allocator, HInstruction** first_sub, HInstruction** second_sub) { @@ -720,7 +763,7 @@ static HGraph* BuildTwoSubs(ArenaAllocator* allocator, return graph; } -TEST_F(RegisterAllocatorTest, SameAsFirstInputHint) { +void RegisterAllocatorTest::SameAsFirstInputHint(Strategy strategy) { ArenaPool pool; ArenaAllocator allocator(&pool); HInstruction *first_sub, *second_sub; @@ -734,7 +777,7 @@ TEST_F(RegisterAllocatorTest, SameAsFirstInputHint) { liveness.Analyze(); RegisterAllocator* register_allocator = - RegisterAllocator::Create(&allocator, &codegen, liveness); + RegisterAllocator::Create(&allocator, &codegen, liveness, strategy); register_allocator->AllocateRegisters(); // Sanity check that in normal conditions, the registers are the same. @@ -757,7 +800,7 @@ TEST_F(RegisterAllocatorTest, SameAsFirstInputHint) { ASSERT_EQ(second_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput); RegisterAllocator* register_allocator = - RegisterAllocator::Create(&allocator, &codegen, liveness); + RegisterAllocator::Create(&allocator, &codegen, liveness, strategy); register_allocator->AllocateRegisters(); ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 2); @@ -765,6 +808,12 @@ TEST_F(RegisterAllocatorTest, SameAsFirstInputHint) { } } +// TODO: Enable this test for graph coloring register allocation when iterative move +// coalescing is merged. +TEST_F(RegisterAllocatorTest, SameAsFirstInputHint_LinearScan) { + SameAsFirstInputHint(Strategy::kRegisterAllocatorLinearScan); +} + static HGraph* BuildDiv(ArenaAllocator* allocator, HInstruction** div) { HGraph* graph = CreateGraph(allocator); @@ -791,7 +840,7 @@ static HGraph* BuildDiv(ArenaAllocator* allocator, return graph; } -TEST_F(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) { +static void ExpectedExactInRegisterAndSameOutputHint(Strategy strategy) { ArenaPool pool; ArenaAllocator allocator(&pool); HInstruction *div; @@ -805,7 +854,7 @@ TEST_F(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) { liveness.Analyze(); RegisterAllocator* register_allocator = - RegisterAllocator::Create(&allocator, &codegen, liveness); + RegisterAllocator::Create(&allocator, &codegen, liveness, strategy); register_allocator->AllocateRegisters(); // div on x86 requires its first input in eax and the output be the same as the first input. @@ -813,9 +862,16 @@ TEST_F(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) { } } +// TODO: Enable this test for graph coloring register allocation when iterative move +// coalescing is merged. +TEST_F(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint_LinearScan) { + ExpectedExactInRegisterAndSameOutputHint(Strategy::kRegisterAllocatorLinearScan); +} + // Test a bug in the register allocator, where allocating a blocked // register would lead to spilling an inactive interval at the wrong // position. +// This test only applies to the linear scan allocator. TEST_F(RegisterAllocatorTest, SpillInactive) { ArenaPool pool; diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc index 7af4302884..a01e107e02 100644 --- a/compiler/optimizing/ssa_liveness_analysis.cc +++ b/compiler/optimizing/ssa_liveness_analysis.cc @@ -368,6 +368,27 @@ bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) { return live_in->UnionIfNotIn(live_out, kill); } +void LiveInterval::DumpWithContext(std::ostream& stream, + const CodeGenerator& codegen) const { + Dump(stream); + if (IsFixed()) { + stream << ", register:" << GetRegister() << "("; + if (IsFloatingPoint()) { + codegen.DumpFloatingPointRegister(stream, GetRegister()); + } else { + codegen.DumpCoreRegister(stream, GetRegister()); + } + stream << ")"; + } else { + stream << ", spill slot:" << GetSpillSlot(); + } + stream << ", requires_register:" << (GetDefinedBy() != nullptr && RequiresRegister()); + if (GetParent()->GetDefinedBy() != nullptr) { + stream << ", defined_by:" << GetParent()->GetDefinedBy()->GetKind(); + stream << "(" << GetParent()->GetDefinedBy()->GetLifetimePosition() << ")"; + } +} + static int RegisterOrLowRegister(Location location) { return location.IsPair() ? location.low() : location.reg(); } diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h index dc98864d9b..346753b775 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -150,9 +150,7 @@ class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> { if (GetIsEnvironment()) return false; if (IsSynthesized()) return false; Location location = GetUser()->GetLocations()->InAt(GetInputIndex()); - return location.IsUnallocated() - && (location.GetPolicy() == Location::kRequiresRegister - || location.GetPolicy() == Location::kRequiresFpuRegister); + return location.IsUnallocated() && location.RequiresRegisterKind(); } private: @@ -481,6 +479,10 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { return last_range_->GetEnd(); } + size_t GetLength() const { + return GetEnd() - GetStart(); + } + size_t FirstRegisterUseAfter(size_t position) const { if (is_temp_) { return position == GetStart() ? position : kNoLifetime; @@ -504,10 +506,16 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { return kNoLifetime; } + // Returns the location of the first register use for this live interval, + // including a register definition if applicable. size_t FirstRegisterUse() const { return FirstRegisterUseAfter(GetStart()); } + // Whether the interval requires a register rather than a stack location. + // If needed for performance, this could be cached. + bool RequiresRegister() const { return FirstRegisterUse() != kNoLifetime; } + size_t FirstUseAfter(size_t position) const { if (is_temp_) { return position == GetStart() ? position : kNoLifetime; @@ -693,6 +701,10 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { stream << " is_high: " << IsHighInterval(); } + // Same as Dump, but adds context such as the instruction defining this interval, and + // the register currently assigned to this interval. + void DumpWithContext(std::ostream& stream, const CodeGenerator& codegen) const; + LiveInterval* GetNextSibling() const { return next_sibling_; } LiveInterval* GetLastSibling() { LiveInterval* result = this; @@ -871,6 +883,33 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { range_search_start_ = first_range_; } + bool DefinitionRequiresRegister() const { + DCHECK(IsParent()); + LocationSummary* locations = defined_by_->GetLocations(); + Location location = locations->Out(); + // This interval is the first interval of the instruction. If the output + // of the instruction requires a register, we return the position of that instruction + // as the first register use. + if (location.IsUnallocated()) { + if ((location.GetPolicy() == Location::kRequiresRegister) + || (location.GetPolicy() == Location::kSameAsFirstInput + && (locations->InAt(0).IsRegister() + || locations->InAt(0).IsRegisterPair() + || locations->InAt(0).GetPolicy() == Location::kRequiresRegister))) { + return true; + } else if ((location.GetPolicy() == Location::kRequiresFpuRegister) + || (location.GetPolicy() == Location::kSameAsFirstInput + && (locations->InAt(0).IsFpuRegister() + || locations->InAt(0).IsFpuRegisterPair() + || locations->InAt(0).GetPolicy() == Location::kRequiresFpuRegister))) { + return true; + } + } else if (location.IsRegister() || location.IsRegisterPair()) { + return true; + } + return false; + } + private: LiveInterval(ArenaAllocator* allocator, Primitive::Type type, @@ -925,33 +964,6 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { return range; } - bool DefinitionRequiresRegister() const { - DCHECK(IsParent()); - LocationSummary* locations = defined_by_->GetLocations(); - Location location = locations->Out(); - // This interval is the first interval of the instruction. If the output - // of the instruction requires a register, we return the position of that instruction - // as the first register use. - if (location.IsUnallocated()) { - if ((location.GetPolicy() == Location::kRequiresRegister) - || (location.GetPolicy() == Location::kSameAsFirstInput - && (locations->InAt(0).IsRegister() - || locations->InAt(0).IsRegisterPair() - || locations->InAt(0).GetPolicy() == Location::kRequiresRegister))) { - return true; - } else if ((location.GetPolicy() == Location::kRequiresFpuRegister) - || (location.GetPolicy() == Location::kSameAsFirstInput - && (locations->InAt(0).IsFpuRegister() - || locations->InAt(0).IsFpuRegisterPair() - || locations->InAt(0).GetPolicy() == Location::kRequiresFpuRegister))) { - return true; - } - } else if (location.IsRegister() || location.IsRegisterPair()) { - return true; - } - return false; - } - bool IsDefiningPosition(size_t position) const { return IsParent() && (position == GetStart()); } diff --git a/compiler/optimizing/x86_memory_gen.cc b/compiler/optimizing/x86_memory_gen.cc index 195159f61b..8aa315a7e3 100644 --- a/compiler/optimizing/x86_memory_gen.cc +++ b/compiler/optimizing/x86_memory_gen.cc @@ -69,8 +69,8 @@ class MemoryOperandVisitor : public HGraphVisitor { }; X86MemoryOperandGeneration::X86MemoryOperandGeneration(HGraph* graph, - OptimizingCompilerStats* stats, - CodeGenerator* codegen) + CodeGenerator* codegen, + OptimizingCompilerStats* stats) : HOptimization(graph, kX86MemoryOperandGenerationPassName, stats), do_implicit_null_checks_(codegen->GetCompilerOptions().GetImplicitNullChecks()) { } diff --git a/compiler/optimizing/x86_memory_gen.h b/compiler/optimizing/x86_memory_gen.h index 7e886819bb..5f15d9f1e6 100644 --- a/compiler/optimizing/x86_memory_gen.h +++ b/compiler/optimizing/x86_memory_gen.h @@ -28,8 +28,8 @@ namespace x86 { class X86MemoryOperandGeneration : public HOptimization { public: X86MemoryOperandGeneration(HGraph* graph, - OptimizingCompilerStats* stats, - CodeGenerator* codegen); + CodeGenerator* codegen, + OptimizingCompilerStats* stats); void Run() OVERRIDE; |