From 611d3395e9efc0ab8dbfa4a197fa022fbd8c7204 Mon Sep 17 00:00:00 2001 From: Scott Wakeling Date: Fri, 10 Jul 2015 11:42:06 +0100 Subject: [PATCH] ARM/ARM64: Implement numberOfLeadingZeros intrinsic. Change-Id: I4042fb7a0b75140475dcfca23e8f79d310f5333b --- compiler/dex/quick/dex_file_method_inliner.cc | 9 ++++++ compiler/dex/quick/dex_file_method_inliner.h | 1 + compiler/optimizing/intrinsics.cc | 10 +++++++ compiler/optimizing/intrinsics_arm.cc | 42 +++++++++++++++++++++++++++ compiler/optimizing/intrinsics_arm64.cc | 27 +++++++++++++++++ compiler/optimizing/intrinsics_list.h | 2 ++ compiler/optimizing/intrinsics_x86.cc | 2 ++ compiler/optimizing/intrinsics_x86_64.cc | 2 ++ compiler/utils/arm/assembler_thumb2_test.cc | 8 +++++ disassembler/disassembler_arm.cc | 14 +++++++++ runtime/quick/inline_method_analyser.h | 1 + test/082-inline-execute/src/Main.java | 20 +++++++++++++ 12 files changed, 138 insertions(+) diff --git a/compiler/dex/quick/dex_file_method_inliner.cc b/compiler/dex/quick/dex_file_method_inliner.cc index 2568ee306..7fc6fa29c 100644 --- a/compiler/dex/quick/dex_file_method_inliner.cc +++ b/compiler/dex/quick/dex_file_method_inliner.cc @@ -38,6 +38,7 @@ static constexpr bool kIntrinsicIsStatic[] = { true, // kIntrinsicFloatCvt true, // kIntrinsicReverseBits true, // kIntrinsicReverseBytes + true, // kIntrinsicNumberOfLeadingZeros true, // kIntrinsicAbsInt true, // kIntrinsicAbsLong true, // kIntrinsicAbsFloat @@ -75,6 +76,8 @@ static_assert(kIntrinsicIsStatic[kIntrinsicDoubleCvt], "DoubleCvt must be static static_assert(kIntrinsicIsStatic[kIntrinsicFloatCvt], "FloatCvt must be static"); static_assert(kIntrinsicIsStatic[kIntrinsicReverseBits], "ReverseBits must be static"); static_assert(kIntrinsicIsStatic[kIntrinsicReverseBytes], "ReverseBytes must be static"); +static_assert(kIntrinsicIsStatic[kIntrinsicNumberOfLeadingZeros], + "NumberOfLeadingZeros must be static"); static_assert(kIntrinsicIsStatic[kIntrinsicAbsInt], "AbsInt must be static"); static_assert(kIntrinsicIsStatic[kIntrinsicAbsLong], "AbsLong must be static"); static_assert(kIntrinsicIsStatic[kIntrinsicAbsFloat], "AbsFloat must be static"); @@ -225,6 +228,7 @@ const char* const DexFileMethodInliner::kNameCacheNames[] = { "putObjectVolatile", // kNameCachePutObjectVolatile "putOrderedObject", // kNameCachePutOrderedObject "arraycopy", // kNameCacheArrayCopy + "numberOfLeadingZeros", // kNameCacheNumberOfLeadingZeros }; const DexFileMethodInliner::ProtoDef DexFileMethodInliner::kProtoCacheDefs[] = { @@ -368,6 +372,9 @@ const DexFileMethodInliner::IntrinsicDef DexFileMethodInliner::kIntrinsicMethods INTRINSIC(JavaLangInteger, Reverse, I_I, kIntrinsicReverseBits, k32), INTRINSIC(JavaLangLong, Reverse, J_J, kIntrinsicReverseBits, k64), + INTRINSIC(JavaLangInteger, NumberOfLeadingZeros, I_I, kIntrinsicNumberOfLeadingZeros, k32), + INTRINSIC(JavaLangLong, NumberOfLeadingZeros, J_I, kIntrinsicNumberOfLeadingZeros, k64), + INTRINSIC(JavaLangMath, Abs, I_I, kIntrinsicAbsInt, 0), INTRINSIC(JavaLangStrictMath, Abs, I_I, kIntrinsicAbsInt, 0), INTRINSIC(JavaLangMath, Abs, J_J, kIntrinsicAbsLong, 0), @@ -614,6 +621,8 @@ bool DexFileMethodInliner::GenIntrinsic(Mir2Lir* backend, CallInfo* info) { intrinsic.d.data & kIntrinsicFlagIsOrdered); case kIntrinsicSystemArrayCopyCharArray: return backend->GenInlinedArrayCopyCharArray(info); + case kIntrinsicNumberOfLeadingZeros: + return false; // not implemented in quick default: LOG(FATAL) << "Unexpected intrinsic opcode: " << intrinsic.opcode; return false; // avoid warning "control reaches end of non-void function" diff --git a/compiler/dex/quick/dex_file_method_inliner.h b/compiler/dex/quick/dex_file_method_inliner.h index a8cb9f0c3..bcb9ee5b5 100644 --- a/compiler/dex/quick/dex_file_method_inliner.h +++ b/compiler/dex/quick/dex_file_method_inliner.h @@ -206,6 +206,7 @@ class DexFileMethodInliner { kNameCachePutObjectVolatile, kNameCachePutOrderedObject, kNameCacheArrayCopy, + kNameCacheNumberOfLeadingZeros, kNameCacheLast }; diff --git a/compiler/optimizing/intrinsics.cc b/compiler/optimizing/intrinsics.cc index bc7da802b..55e964ea8 100644 --- a/compiler/optimizing/intrinsics.cc +++ b/compiler/optimizing/intrinsics.cc @@ -103,6 +103,16 @@ static Intrinsics GetIntrinsic(InlineMethod method) { LOG(FATAL) << "Unknown/unsupported op size " << method.d.data; UNREACHABLE(); } + case kIntrinsicNumberOfLeadingZeros: + switch (GetType(method.d.data, true)) { + case Primitive::kPrimInt: + return Intrinsics::kIntegerNumberOfLeadingZeros; + case Primitive::kPrimLong: + return Intrinsics::kLongNumberOfLeadingZeros; + default: + LOG(FATAL) << "Unknown/unsupported op size " << method.d.data; + UNREACHABLE(); + } // Abs. case kIntrinsicAbsDouble: diff --git a/compiler/optimizing/intrinsics_arm.cc b/compiler/optimizing/intrinsics_arm.cc index b4dbf75f0..a79765426 100644 --- a/compiler/optimizing/intrinsics_arm.cc +++ b/compiler/optimizing/intrinsics_arm.cc @@ -224,6 +224,48 @@ static void CreateFPToFPLocations(ArenaAllocator* arena, HInvoke* invoke) { locations->SetOut(Location::RequiresFpuRegister(), Location::kNoOutputOverlap); } +static void GenNumberOfLeadingZeros(LocationSummary* locations, + Primitive::Type type, + ArmAssembler* assembler) { + Location in = locations->InAt(0); + Register out = locations->Out().AsRegister(); + + DCHECK((type == Primitive::kPrimInt) || (type == Primitive::kPrimLong)); + + if (type == Primitive::kPrimLong) { + Register in_reg_lo = in.AsRegisterPairLow(); + Register in_reg_hi = in.AsRegisterPairHigh(); + Label end; + __ clz(out, in_reg_hi); + __ CompareAndBranchIfNonZero(in_reg_hi, &end); + __ clz(out, in_reg_lo); + __ AddConstant(out, 32); + __ Bind(&end); + } else { + __ clz(out, in.AsRegister()); + } +} + +void IntrinsicLocationsBuilderARM::VisitIntegerNumberOfLeadingZeros(HInvoke* invoke) { + CreateIntToIntLocations(arena_, invoke); +} + +void IntrinsicCodeGeneratorARM::VisitIntegerNumberOfLeadingZeros(HInvoke* invoke) { + GenNumberOfLeadingZeros(invoke->GetLocations(), Primitive::kPrimInt, GetAssembler()); +} + +void IntrinsicLocationsBuilderARM::VisitLongNumberOfLeadingZeros(HInvoke* invoke) { + LocationSummary* locations = new (arena_) LocationSummary(invoke, + LocationSummary::kNoCall, + kIntrinsified); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetOut(Location::RequiresRegister(), Location::kOutputOverlap); +} + +void IntrinsicCodeGeneratorARM::VisitLongNumberOfLeadingZeros(HInvoke* invoke) { + GenNumberOfLeadingZeros(invoke->GetLocations(), Primitive::kPrimLong, GetAssembler()); +} + static void MathAbsFP(LocationSummary* locations, bool is64bit, ArmAssembler* assembler) { Location in = locations->InAt(0); Location out = locations->Out(); diff --git a/compiler/optimizing/intrinsics_arm64.cc b/compiler/optimizing/intrinsics_arm64.cc index 78ac167a8..2c93feaaa 100644 --- a/compiler/optimizing/intrinsics_arm64.cc +++ b/compiler/optimizing/intrinsics_arm64.cc @@ -260,6 +260,33 @@ void IntrinsicCodeGeneratorARM64::VisitShortReverseBytes(HInvoke* invoke) { GenReverseBytes(invoke->GetLocations(), Primitive::kPrimShort, GetVIXLAssembler()); } +static void GenNumberOfLeadingZeros(LocationSummary* locations, + Primitive::Type type, + vixl::MacroAssembler* masm) { + DCHECK(type == Primitive::kPrimInt || type == Primitive::kPrimLong); + + Location in = locations->InAt(0); + Location out = locations->Out(); + + __ Clz(RegisterFrom(out, type), RegisterFrom(in, type)); +} + +void IntrinsicLocationsBuilderARM64::VisitIntegerNumberOfLeadingZeros(HInvoke* invoke) { + CreateIntToIntLocations(arena_, invoke); +} + +void IntrinsicCodeGeneratorARM64::VisitIntegerNumberOfLeadingZeros(HInvoke* invoke) { + GenNumberOfLeadingZeros(invoke->GetLocations(), Primitive::kPrimInt, GetVIXLAssembler()); +} + +void IntrinsicLocationsBuilderARM64::VisitLongNumberOfLeadingZeros(HInvoke* invoke) { + CreateIntToIntLocations(arena_, invoke); +} + +void IntrinsicCodeGeneratorARM64::VisitLongNumberOfLeadingZeros(HInvoke* invoke) { + GenNumberOfLeadingZeros(invoke->GetLocations(), Primitive::kPrimLong, GetVIXLAssembler()); +} + static void GenReverse(LocationSummary* locations, Primitive::Type type, vixl::MacroAssembler* masm) { diff --git a/compiler/optimizing/intrinsics_list.h b/compiler/optimizing/intrinsics_list.h index 2c9248f52..d28c5a3f2 100644 --- a/compiler/optimizing/intrinsics_list.h +++ b/compiler/optimizing/intrinsics_list.h @@ -27,8 +27,10 @@ V(FloatIntBitsToFloat, kStatic) \ V(IntegerReverse, kStatic) \ V(IntegerReverseBytes, kStatic) \ + V(IntegerNumberOfLeadingZeros, kStatic) \ V(LongReverse, kStatic) \ V(LongReverseBytes, kStatic) \ + V(LongNumberOfLeadingZeros, kStatic) \ V(ShortReverseBytes, kStatic) \ V(MathAbsDouble, kStatic) \ V(MathAbsFloat, kStatic) \ diff --git a/compiler/optimizing/intrinsics_x86.cc b/compiler/optimizing/intrinsics_x86.cc index 0d6ca09f3..993c005d5 100644 --- a/compiler/optimizing/intrinsics_x86.cc +++ b/compiler/optimizing/intrinsics_x86.cc @@ -1756,6 +1756,8 @@ UNIMPLEMENTED_INTRINSIC(MathRoundDouble) UNIMPLEMENTED_INTRINSIC(StringGetCharsNoCheck) UNIMPLEMENTED_INTRINSIC(SystemArrayCopyChar) UNIMPLEMENTED_INTRINSIC(ReferenceGetReferent) +UNIMPLEMENTED_INTRINSIC(IntegerNumberOfLeadingZeros) +UNIMPLEMENTED_INTRINSIC(LongNumberOfLeadingZeros) #undef UNIMPLEMENTED_INTRINSIC diff --git a/compiler/optimizing/intrinsics_x86_64.cc b/compiler/optimizing/intrinsics_x86_64.cc index ea342e938..8ab0b771f 100644 --- a/compiler/optimizing/intrinsics_x86_64.cc +++ b/compiler/optimizing/intrinsics_x86_64.cc @@ -1615,6 +1615,8 @@ void IntrinsicCodeGeneratorX86_64::Visit ## Name(HInvoke* invoke ATTRIBUTE_UNUSE UNIMPLEMENTED_INTRINSIC(StringGetCharsNoCheck) UNIMPLEMENTED_INTRINSIC(SystemArrayCopyChar) UNIMPLEMENTED_INTRINSIC(ReferenceGetReferent) +UNIMPLEMENTED_INTRINSIC(IntegerNumberOfLeadingZeros) +UNIMPLEMENTED_INTRINSIC(LongNumberOfLeadingZeros) #undef UNIMPLEMENTED_INTRINSIC diff --git a/compiler/utils/arm/assembler_thumb2_test.cc b/compiler/utils/arm/assembler_thumb2_test.cc index 004853f22..84f5cb16f 100644 --- a/compiler/utils/arm/assembler_thumb2_test.cc +++ b/compiler/utils/arm/assembler_thumb2_test.cc @@ -1011,4 +1011,12 @@ TEST_F(AssemblerThumb2Test, LoadLiteralBeyondMax1KiBDueToAlignmentOnSecondPass) __ GetAdjustedPosition(label.Position())); } +TEST_F(AssemblerThumb2Test, Clz) { + __ clz(arm::R0, arm::R1); + + const char* expected = "clz r0, r1\n"; + + DriverStr(expected, "clz"); +} + } // namespace art diff --git a/disassembler/disassembler_arm.cc b/disassembler/disassembler_arm.cc index 31e653bf9..d1d3481b9 100644 --- a/disassembler/disassembler_arm.cc +++ b/disassembler/disassembler_arm.cc @@ -1455,6 +1455,20 @@ size_t DisassemblerArm::DumpThumb32(std::ostream& os, const uint8_t* instr_ptr) } // else unknown instruction break; } + case 0x2B: { // 0101011 + // CLZ - 111 11 0101011 mmmm 1111 dddd 1000 mmmm + if ((instr & 0xf0f0) == 0xf080) { + opcode << "clz"; + ArmRegister Rm(instr, 0); + ArmRegister Rd(instr, 8); + args << Rd << ", " << Rm; + ArmRegister Rm2(instr, 16); + if (Rm.r != Rm2.r || Rm.r == 13 || Rm.r == 15 || Rd.r == 13 || Rd.r == 15) { + args << " (UNPREDICTABLE)"; + } + } + break; + } default: // more formats if ((op2 >> 4) == 2) { // 010xxxx // data processing (register) diff --git a/runtime/quick/inline_method_analyser.h b/runtime/quick/inline_method_analyser.h index 65bbcbebe..75ff27f98 100644 --- a/runtime/quick/inline_method_analyser.h +++ b/runtime/quick/inline_method_analyser.h @@ -39,6 +39,7 @@ enum InlineMethodOpcode : uint16_t { kIntrinsicFloatCvt, kIntrinsicReverseBits, kIntrinsicReverseBytes, + kIntrinsicNumberOfLeadingZeros, kIntrinsicAbsInt, kIntrinsicAbsLong, kIntrinsicAbsFloat, diff --git a/test/082-inline-execute/src/Main.java b/test/082-inline-execute/src/Main.java index 177c5a470..77c1a9972 100644 --- a/test/082-inline-execute/src/Main.java +++ b/test/082-inline-execute/src/Main.java @@ -45,6 +45,8 @@ public class Main { test_Long_reverseBytes(); test_Integer_reverse(); test_Long_reverse(); + test_Integer_numberOfLeadingZeros(); + test_Long_numberOfLeadingZeros(); test_StrictMath_abs_I(); test_StrictMath_abs_J(); test_StrictMath_min_I(); @@ -1041,6 +1043,24 @@ public class Main { return (r1 / i1) + (r2 / i2) + i3 + i4 + i5 + i6 + i7 + i8; } + public static void test_Integer_numberOfLeadingZeros() { + Assert.assertEquals(Integer.numberOfLeadingZeros(0), Integer.SIZE); + for (int i = 0; i < Integer.SIZE; i++) { + Assert.assertEquals(Integer.numberOfLeadingZeros(1 << i), Integer.SIZE - 1 - i); + Assert.assertEquals(Integer.numberOfLeadingZeros((1 << i) | 1), Integer.SIZE - 1 - i); + Assert.assertEquals(Integer.numberOfLeadingZeros(0xFFFFFFFF >>> i), i); + } + } + + public static void test_Long_numberOfLeadingZeros() { + Assert.assertEquals(Long.numberOfLeadingZeros(0L), Long.SIZE); + for (int i = 0; i < Long.SIZE; i++) { + Assert.assertEquals(Long.numberOfLeadingZeros(1L << i), Long.SIZE - 1 - i); + Assert.assertEquals(Long.numberOfLeadingZeros((1L << i) | 1L), Long.SIZE - 1 - i); + Assert.assertEquals(Long.numberOfLeadingZeros(0xFFFFFFFFFFFFFFFFL >>> i), i); + } + } + static Object runtime; static Method address_of; static Method new_non_movable_array; -- 2.11.0