From 3aa206b86560da94f895625186295bf07a0301d8 Mon Sep 17 00:00:00 2001 From: Benedikt Meurer Date: Fri, 20 Mar 2015 09:37:20 +0100 Subject: [PATCH] [turbofan] Turn Math.clz32 into an inlinable builtin. R=dcarney@chromium.org, yangguo@chromium.org BUG=v8:3952 LOG=n Review URL: https://codereview.chromium.org/1021183002 Cr-Commit-Position: refs/heads/master@{#27329} --- src/compiler/arm/code-generator-arm.cc | 4 +++ src/compiler/arm/instruction-codes-arm.h | 1 + src/compiler/arm/instruction-selector-arm.cc | 6 ++++ src/compiler/arm64/code-generator-arm64.cc | 3 ++ src/compiler/arm64/instruction-codes-arm64.h | 1 + .../arm64/instruction-selector-arm64.cc | 6 ++++ src/compiler/ia32/code-generator-ia32.cc | 3 ++ src/compiler/ia32/instruction-codes-ia32.h | 1 + .../ia32/instruction-selector-ia32.cc | 6 ++++ src/compiler/instruction-selector.cc | 2 ++ src/compiler/js-intrinsic-lowering.cc | 7 ++++ src/compiler/js-intrinsic-lowering.h | 1 + src/compiler/machine-operator.cc | 1 + src/compiler/machine-operator.h | 1 + src/compiler/opcodes.h | 1 + src/compiler/raw-machine-assembler.h | 1 + src/compiler/simplified-lowering.cc | 3 ++ src/compiler/typer.cc | 7 ++++ src/compiler/verifier.cc | 1 + src/compiler/x64/code-generator-x64.cc | 7 ++++ src/compiler/x64/instruction-codes-x64.h | 1 + src/compiler/x64/instruction-selector-x64.cc | 6 ++++ src/counters.h | 1 + src/hydrogen.cc | 9 +++++ src/hydrogen.h | 1 + src/ia32/lithium-codegen-ia32.cc | 8 +---- src/ia32/macro-assembler-ia32.cc | 11 ++++++ src/ia32/macro-assembler-ia32.h | 3 ++ src/math.js | 16 +++------ src/runtime/runtime-maths.cc | 11 ++++++ src/runtime/runtime.h | 1 + src/x64/assembler-x64.cc | 9 +++++ src/x64/assembler-x64.h | 1 + src/x64/lithium-codegen-x64.cc | 8 +---- src/x64/macro-assembler-x64.cc | 22 ++++++++++++ src/x64/macro-assembler-x64.h | 3 ++ test/cctest/test-disasm-x64.cc | 3 ++ test/mjsunit/asm/math-clz32.js | 31 ++++++++++++++++ .../arm/instruction-selector-arm-unittest.cc | 15 ++++++++ .../instruction-selector-arm64-unittest.cc | 15 ++++++++ .../instruction-selector-ia32-unittest.cc | 21 +++++++++-- .../js-intrinsic-lowering-unittest.cc | 17 +++++++++ .../compiler/machine-operator-unittest.cc | 36 +++++++++---------- test/unittests/compiler/node-test-utils.cc | 1 + test/unittests/compiler/node-test-utils.h | 1 + .../x64/instruction-selector-x64-unittest.cc | 15 ++++++++ 46 files changed, 282 insertions(+), 47 deletions(-) create mode 100644 test/mjsunit/asm/math-clz32.js diff --git a/src/compiler/arm/code-generator-arm.cc b/src/compiler/arm/code-generator-arm.cc index b9c347612..26ad5b031 100644 --- a/src/compiler/arm/code-generator-arm.cc +++ b/src/compiler/arm/code-generator-arm.cc @@ -489,6 +489,10 @@ void CodeGenerator::AssembleArchInstruction(Instruction* instr) { i.InputInt32(2)); DCHECK_EQ(LeaveCC, i.OutputSBit()); break; + case kArmClz: + __ clz(i.OutputRegister(), i.InputRegister(0)); + DCHECK_EQ(LeaveCC, i.OutputSBit()); + break; case kArmCmp: __ cmp(i.InputRegister(0), i.InputOperand2(1)); DCHECK_EQ(SetCC, i.OutputSBit()); diff --git a/src/compiler/arm/instruction-codes-arm.h b/src/compiler/arm/instruction-codes-arm.h index 5cb08e4f7..404b1e0ac 100644 --- a/src/compiler/arm/instruction-codes-arm.h +++ b/src/compiler/arm/instruction-codes-arm.h @@ -15,6 +15,7 @@ namespace compiler { V(ArmAdd) \ V(ArmAnd) \ V(ArmBic) \ + V(ArmClz) \ V(ArmCmp) \ V(ArmCmn) \ V(ArmTst) \ diff --git a/src/compiler/arm/instruction-selector-arm.cc b/src/compiler/arm/instruction-selector-arm.cc index 20276ede7..9f788a5bf 100644 --- a/src/compiler/arm/instruction-selector-arm.cc +++ b/src/compiler/arm/instruction-selector-arm.cc @@ -645,6 +645,12 @@ void InstructionSelector::VisitWord32Ror(Node* node) { } +void InstructionSelector::VisitWord32Clz(Node* node) { + ArmOperandGenerator g(this); + Emit(kArmClz, g.DefineAsRegister(node), g.UseRegister(node->InputAt(0))); +} + + void InstructionSelector::VisitInt32Add(Node* node) { ArmOperandGenerator g(this); Int32BinopMatcher m(node); diff --git a/src/compiler/arm64/code-generator-arm64.cc b/src/compiler/arm64/code-generator-arm64.cc index b494090c4..312222508 100644 --- a/src/compiler/arm64/code-generator-arm64.cc +++ b/src/compiler/arm64/code-generator-arm64.cc @@ -631,6 +631,9 @@ void CodeGenerator::AssembleArchInstruction(Instruction* instr) { __ PokePair(i.InputRegister(1), i.InputRegister(0), slot * kPointerSize); break; } + case kArm64Clz32: + __ Clz(i.OutputRegister32(), i.InputRegister32(0)); + break; case kArm64Cmp: __ Cmp(i.InputRegister(0), i.InputOperand(1)); break; diff --git a/src/compiler/arm64/instruction-codes-arm64.h b/src/compiler/arm64/instruction-codes-arm64.h index dfd90da44..3e3f5c37d 100644 --- a/src/compiler/arm64/instruction-codes-arm64.h +++ b/src/compiler/arm64/instruction-codes-arm64.h @@ -18,6 +18,7 @@ namespace compiler { V(Arm64And32) \ V(Arm64Bic) \ V(Arm64Bic32) \ + V(Arm64Clz32) \ V(Arm64Cmp) \ V(Arm64Cmp32) \ V(Arm64Cmn) \ diff --git a/src/compiler/arm64/instruction-selector-arm64.cc b/src/compiler/arm64/instruction-selector-arm64.cc index edef43837..97099e225 100644 --- a/src/compiler/arm64/instruction-selector-arm64.cc +++ b/src/compiler/arm64/instruction-selector-arm64.cc @@ -738,6 +738,12 @@ void InstructionSelector::VisitWord64Ror(Node* node) { } +void InstructionSelector::VisitWord32Clz(Node* node) { + Arm64OperandGenerator g(this); + Emit(kArm64Clz32, g.DefineAsRegister(node), g.UseRegister(node->InputAt(0))); +} + + void InstructionSelector::VisitInt32Add(Node* node) { Arm64OperandGenerator g(this); Int32BinopMatcher m(node); diff --git a/src/compiler/ia32/code-generator-ia32.cc b/src/compiler/ia32/code-generator-ia32.cc index fe86e3aaa..25bf0331c 100644 --- a/src/compiler/ia32/code-generator-ia32.cc +++ b/src/compiler/ia32/code-generator-ia32.cc @@ -447,6 +447,9 @@ void CodeGenerator::AssembleArchInstruction(Instruction* instr) { __ ror_cl(i.OutputOperand()); } break; + case kIA32Lzcnt: + __ Lzcnt(i.OutputRegister(), i.InputOperand(0)); + break; case kSSEFloat64Cmp: __ ucomisd(i.InputDoubleRegister(0), i.InputOperand(1)); break; diff --git a/src/compiler/ia32/instruction-codes-ia32.h b/src/compiler/ia32/instruction-codes-ia32.h index e3a7ac1f8..b7a9e82f6 100644 --- a/src/compiler/ia32/instruction-codes-ia32.h +++ b/src/compiler/ia32/instruction-codes-ia32.h @@ -30,6 +30,7 @@ namespace compiler { V(IA32Shr) \ V(IA32Sar) \ V(IA32Ror) \ + V(IA32Lzcnt) \ V(SSEFloat64Cmp) \ V(SSEFloat64Add) \ V(SSEFloat64Sub) \ diff --git a/src/compiler/ia32/instruction-selector-ia32.cc b/src/compiler/ia32/instruction-selector-ia32.cc index 8ec091a0f..ba21921db 100644 --- a/src/compiler/ia32/instruction-selector-ia32.cc +++ b/src/compiler/ia32/instruction-selector-ia32.cc @@ -503,6 +503,12 @@ void InstructionSelector::VisitWord32Ror(Node* node) { } +void InstructionSelector::VisitWord32Clz(Node* node) { + IA32OperandGenerator g(this); + Emit(kIA32Lzcnt, g.DefineAsRegister(node), g.Use(node->InputAt(0))); +} + + void InstructionSelector::VisitInt32Add(Node* node) { IA32OperandGenerator g(this); diff --git a/src/compiler/instruction-selector.cc b/src/compiler/instruction-selector.cc index 0d0314dda..c3837ad8b 100644 --- a/src/compiler/instruction-selector.cc +++ b/src/compiler/instruction-selector.cc @@ -658,6 +658,8 @@ void InstructionSelector::VisitNode(Node* node) { return VisitWord32Ror(node); case IrOpcode::kWord32Equal: return VisitWord32Equal(node); + case IrOpcode::kWord32Clz: + return VisitWord32Clz(node); case IrOpcode::kWord64And: return VisitWord64And(node); case IrOpcode::kWord64Or: diff --git a/src/compiler/js-intrinsic-lowering.cc b/src/compiler/js-intrinsic-lowering.cc index a3d27ee1a..8879ebc8d 100644 --- a/src/compiler/js-intrinsic-lowering.cc +++ b/src/compiler/js-intrinsic-lowering.cc @@ -42,6 +42,8 @@ Reduction JSIntrinsicLowering::Reduce(Node* node) { return ReduceInlineDoubleHi(node); case Runtime::kInlineIsRegExp: return ReduceInlineIsInstanceType(node, JS_REGEXP_TYPE); + case Runtime::kInlineMathClz32: + return ReduceInlineMathClz32(node); case Runtime::kInlineMathFloor: return ReduceInlineMathFloor(node); case Runtime::kInlineMathSqrt: @@ -179,6 +181,11 @@ Reduction JSIntrinsicLowering::ReduceInlineIsInstanceType( } +Reduction JSIntrinsicLowering::ReduceInlineMathClz32(Node* node) { + return Change(node, machine()->Word32Clz()); +} + + Reduction JSIntrinsicLowering::ReduceInlineMathFloor(Node* node) { if (!machine()->HasFloat64RoundDown()) return NoChange(); return Change(node, machine()->Float64RoundDown()); diff --git a/src/compiler/js-intrinsic-lowering.h b/src/compiler/js-intrinsic-lowering.h index 21982ac70..6bc0c7d26 100644 --- a/src/compiler/js-intrinsic-lowering.h +++ b/src/compiler/js-intrinsic-lowering.h @@ -35,6 +35,7 @@ class JSIntrinsicLowering FINAL : public Reducer { Reduction ReduceInlineConstructDouble(Node* node); Reduction ReduceInlineDoubleLo(Node* node); Reduction ReduceInlineDoubleHi(Node* node); + Reduction ReduceInlineMathClz32(Node* node); Reduction ReduceInlineMathFloor(Node* node); Reduction ReduceInlineMathSqrt(Node* node); Reduction ReduceInlineStringGetLength(Node* node); diff --git a/src/compiler/machine-operator.cc b/src/compiler/machine-operator.cc index 235122389..fa8979c2f 100644 --- a/src/compiler/machine-operator.cc +++ b/src/compiler/machine-operator.cc @@ -73,6 +73,7 @@ CheckedStoreRepresentation CheckedStoreRepresentationOf(Operator const* op) { V(Word32Sar, Operator::kNoProperties, 2, 0, 1) \ V(Word32Ror, Operator::kNoProperties, 2, 0, 1) \ V(Word32Equal, Operator::kCommutative, 2, 0, 1) \ + V(Word32Clz, Operator::kNoProperties, 1, 0, 1) \ V(Word64And, Operator::kAssociative | Operator::kCommutative, 2, 0, 1) \ V(Word64Or, Operator::kAssociative | Operator::kCommutative, 2, 0, 1) \ V(Word64Xor, Operator::kAssociative | Operator::kCommutative, 2, 0, 1) \ diff --git a/src/compiler/machine-operator.h b/src/compiler/machine-operator.h index 409f033cc..d42856251 100644 --- a/src/compiler/machine-operator.h +++ b/src/compiler/machine-operator.h @@ -96,6 +96,7 @@ class MachineOperatorBuilder FINAL : public ZoneObject { const Operator* Word32Sar(); const Operator* Word32Ror(); const Operator* Word32Equal(); + const Operator* Word32Clz(); bool Word32ShiftIsSafe() const { return flags_ & kWord32ShiftIsSafe; } const Operator* Word64And(); diff --git a/src/compiler/opcodes.h b/src/compiler/opcodes.h index 9114c8d13..8426fd8c1 100644 --- a/src/compiler/opcodes.h +++ b/src/compiler/opcodes.h @@ -208,6 +208,7 @@ V(Word32Shr) \ V(Word32Sar) \ V(Word32Ror) \ + V(Word32Clz) \ V(Word64And) \ V(Word64Or) \ V(Word64Xor) \ diff --git a/src/compiler/raw-machine-assembler.h b/src/compiler/raw-machine-assembler.h index 82ef3fabf..bcc96803f 100644 --- a/src/compiler/raw-machine-assembler.h +++ b/src/compiler/raw-machine-assembler.h @@ -175,6 +175,7 @@ class RawMachineAssembler : public GraphBuilder { Node* Word32Ror(Node* a, Node* b) { return NewNode(machine()->Word32Ror(), a, b); } + Node* Word32Clz(Node* a) { return NewNode(machine()->Word32Clz(), a); } Node* Word32Equal(Node* a, Node* b) { return NewNode(machine()->Word32Equal(), a, b); } diff --git a/src/compiler/simplified-lowering.cc b/src/compiler/simplified-lowering.cc index ef65c9bc7..939cd38d1 100644 --- a/src/compiler/simplified-lowering.cc +++ b/src/compiler/simplified-lowering.cc @@ -939,6 +939,9 @@ class RepresentationSelector { case IrOpcode::kWord32Equal: return VisitBinop(node, kRepWord32, kRepBit); + case IrOpcode::kWord32Clz: + return VisitUnop(node, kMachUint32, kMachUint32); + case IrOpcode::kInt32Add: case IrOpcode::kInt32Sub: case IrOpcode::kInt32Mul: diff --git a/src/compiler/typer.cc b/src/compiler/typer.cc index 67e2c55b2..e044450b3 100644 --- a/src/compiler/typer.cc +++ b/src/compiler/typer.cc @@ -1518,6 +1518,8 @@ Bounds Typer::Visitor::TypeJSCallRuntime(Node* node) { case Runtime::kInlineMathFloor: case Runtime::kInlineMathSqrt: return Bounds(Type::None(zone()), Type::Number()); + case Runtime::kInlineMathClz32: + return Bounds(Type::None(), Type::Range(0, 32, zone())); default: break; } @@ -1819,6 +1821,11 @@ Bounds Typer::Visitor::TypeWord32Equal(Node* node) { } +Bounds Typer::Visitor::TypeWord32Clz(Node* node) { + return Bounds(Type::Integral32()); +} + + Bounds Typer::Visitor::TypeWord64And(Node* node) { return Bounds(Type::Internal()); } diff --git a/src/compiler/verifier.cc b/src/compiler/verifier.cc index 3cc6424c6..bd8b971df 100644 --- a/src/compiler/verifier.cc +++ b/src/compiler/verifier.cc @@ -751,6 +751,7 @@ void Verifier::Visitor::Check(Node* node) { case IrOpcode::kWord32Sar: case IrOpcode::kWord32Ror: case IrOpcode::kWord32Equal: + case IrOpcode::kWord32Clz: case IrOpcode::kWord64And: case IrOpcode::kWord64Or: case IrOpcode::kWord64Xor: diff --git a/src/compiler/x64/code-generator-x64.cc b/src/compiler/x64/code-generator-x64.cc index 0027d49be..b3285dea9 100644 --- a/src/compiler/x64/code-generator-x64.cc +++ b/src/compiler/x64/code-generator-x64.cc @@ -694,6 +694,13 @@ void CodeGenerator::AssembleArchInstruction(Instruction* instr) { case kX64Ror: ASSEMBLE_SHIFT(rorq, 6); break; + case kX64Lzcnt32: + if (instr->InputAt(0)->IsRegister()) { + __ Lzcntl(i.OutputRegister(), i.InputRegister(0)); + } else { + __ Lzcntl(i.OutputRegister(), i.InputOperand(0)); + } + break; case kSSEFloat64Cmp: ASSEMBLE_DOUBLE_BINOP(ucomisd); break; diff --git a/src/compiler/x64/instruction-codes-x64.h b/src/compiler/x64/instruction-codes-x64.h index 4c9d33535..9416017af 100644 --- a/src/compiler/x64/instruction-codes-x64.h +++ b/src/compiler/x64/instruction-codes-x64.h @@ -46,6 +46,7 @@ namespace compiler { V(X64Sar32) \ V(X64Ror) \ V(X64Ror32) \ + V(X64Lzcnt32) \ V(SSEFloat64Cmp) \ V(SSEFloat64Add) \ V(SSEFloat64Sub) \ diff --git a/src/compiler/x64/instruction-selector-x64.cc b/src/compiler/x64/instruction-selector-x64.cc index ac06da397..f5f1264aa 100644 --- a/src/compiler/x64/instruction-selector-x64.cc +++ b/src/compiler/x64/instruction-selector-x64.cc @@ -555,6 +555,12 @@ void InstructionSelector::VisitWord64Ror(Node* node) { } +void InstructionSelector::VisitWord32Clz(Node* node) { + X64OperandGenerator g(this); + Emit(kX64Lzcnt32, g.DefineAsRegister(node), g.Use(node->InputAt(0))); +} + + void InstructionSelector::VisitInt32Add(Node* node) { X64OperandGenerator g(this); diff --git a/src/counters.h b/src/counters.h index e20a49fa3..af8e8b455 100644 --- a/src/counters.h +++ b/src/counters.h @@ -570,6 +570,7 @@ class AggregatedHistogramTimerScope { SC(math_asin, V8.MathAsin) \ SC(math_atan, V8.MathAtan) \ SC(math_atan2, V8.MathAtan2) \ + SC(math_clz32, V8.MathClz32) \ SC(math_exp, V8.MathExp) \ SC(math_floor, V8.MathFloor) \ SC(math_log, V8.MathLog) \ diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 5153897fb..6f349b79c 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -12030,6 +12030,15 @@ void HOptimizedGraphBuilder::GenerateMathPow(CallRuntime* call) { } +void HOptimizedGraphBuilder::GenerateMathClz32(CallRuntime* call) { + DCHECK(call->arguments()->length() == 1); + CHECK_ALIVE(VisitForValue(call->arguments()->at(0))); + HValue* value = Pop(); + HInstruction* result = NewUncasted(value, kMathClz32); + return ast_context()->ReturnInstruction(result, call->id()); +} + + void HOptimizedGraphBuilder::GenerateMathFloor(CallRuntime* call) { DCHECK(call->arguments()->length() == 1); CHECK_ALIVE(VisitForValue(call->arguments()->at(0))); diff --git a/src/hydrogen.h b/src/hydrogen.h index 483c721e7..b253d600c 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -2212,6 +2212,7 @@ class HOptimizedGraphBuilder : public HGraphBuilder, public AstVisitor { F(ConstructDouble) \ F(DoubleHi) \ F(DoubleLo) \ + F(MathClz32) \ F(MathFloor) \ F(MathSqrt) \ F(MathLogRT) \ diff --git a/src/ia32/lithium-codegen-ia32.cc b/src/ia32/lithium-codegen-ia32.cc index bc0859aef..8dde18d25 100644 --- a/src/ia32/lithium-codegen-ia32.cc +++ b/src/ia32/lithium-codegen-ia32.cc @@ -3914,14 +3914,8 @@ void LCodeGen::DoMathLog(LMathLog* instr) { void LCodeGen::DoMathClz32(LMathClz32* instr) { Register input = ToRegister(instr->value()); Register result = ToRegister(instr->result()); - Label not_zero_input; - __ bsr(result, input); - __ j(not_zero, ¬_zero_input); - __ Move(result, Immediate(63)); // 63^31 == 32 - - __ bind(¬_zero_input); - __ xor_(result, Immediate(31)); // for x in [0..31], 31^x == 31-x. + __ Lzcnt(result, input); } diff --git a/src/ia32/macro-assembler-ia32.cc b/src/ia32/macro-assembler-ia32.cc index 52e674f9d..365ad3cc0 100644 --- a/src/ia32/macro-assembler-ia32.cc +++ b/src/ia32/macro-assembler-ia32.cc @@ -2466,6 +2466,17 @@ void MacroAssembler::Pinsrd(XMMRegister dst, const Operand& src, int8_t imm8) { } +void MacroAssembler::Lzcnt(Register dst, const Operand& src) { + // TODO(intel): Add support for LZCNT (with ABM/BMI1). + Label not_zero_src; + bsr(dst, src); + j(not_zero, ¬_zero_src, Label::kNear); + Move(dst, Immediate(63)); // 63^31 == 32 + bind(¬_zero_src); + xor_(dst, Immediate(31)); // for x in [0..31], 31^x == 31-x. +} + + void MacroAssembler::SetCounter(StatsCounter* counter, int value) { if (FLAG_native_code_counters && counter->Enabled()) { mov(Operand::StaticVariable(ExternalReference(counter)), Immediate(value)); diff --git a/src/ia32/macro-assembler-ia32.h b/src/ia32/macro-assembler-ia32.h index 8c135f2b6..8a8ee2a30 100644 --- a/src/ia32/macro-assembler-ia32.h +++ b/src/ia32/macro-assembler-ia32.h @@ -820,6 +820,9 @@ class MacroAssembler: public Assembler { } void Pinsrd(XMMRegister dst, const Operand& src, int8_t imm8); + void Lzcnt(Register dst, Register src) { Lzcnt(dst, Operand(src)); } + void Lzcnt(Register dst, const Operand& src); + // Emit call to the code we are currently generating. void CallSelf() { Handle self(reinterpret_cast(CodeObject().location())); diff --git a/src/math.js b/src/math.js index dff9390de..f2eaa14bf 100644 --- a/src/math.js +++ b/src/math.js @@ -252,17 +252,8 @@ function MathFroundJS(x) { } // ES6 draft 07-18-14, section 20.2.2.11 -function MathClz32(x) { - x = ToUint32(TO_NUMBER_INLINE(x)); - if (x == 0) return 32; - var result = 0; - // Binary search. - if ((x & 0xFFFF0000) === 0) { x <<= 16; result += 16; }; - if ((x & 0xFF000000) === 0) { x <<= 8; result += 8; }; - if ((x & 0xF0000000) === 0) { x <<= 4; result += 4; }; - if ((x & 0xC0000000) === 0) { x <<= 2; result += 2; }; - if ((x & 0x80000000) === 0) { x <<= 1; result += 1; }; - return result; +function MathClz32JS(x) { + return %_MathClz32(x >>> 0); } // ES6 draft 09-27-13, section 20.2.2.9. @@ -345,12 +336,13 @@ InstallFunctions(Math, DONT_ENUM, GlobalArray( "atanh", MathAtanh, "hypot", MathHypot, "fround", MathFroundJS, - "clz32", MathClz32, + "clz32", MathClz32JS, "cbrt", MathCbrt )); %SetInlineBuiltinFlag(MathAbs); %SetInlineBuiltinFlag(MathCeil); +%SetInlineBuiltinFlag(MathClz32JS); %SetInlineBuiltinFlag(MathFloorJS); %SetInlineBuiltinFlag(MathRandom); %SetInlineBuiltinFlag(MathSqrtJS); diff --git a/src/runtime/runtime-maths.cc b/src/runtime/runtime-maths.cc index a4435e09e..2941b580f 100644 --- a/src/runtime/runtime-maths.cc +++ b/src/runtime/runtime-maths.cc @@ -112,6 +112,17 @@ RUNTIME_FUNCTION(Runtime_MathExpRT) { } +RUNTIME_FUNCTION(Runtime_MathClz32) { + HandleScope scope(isolate); + DCHECK(args.length() == 1); + isolate->counters()->math_clz32()->Increment(); + + CONVERT_NUMBER_CHECKED(uint32_t, x, Uint32, args[0]); + return *isolate->factory()->NewNumberFromUint( + base::bits::CountLeadingZeros32(x)); +} + + RUNTIME_FUNCTION(Runtime_MathFloor) { HandleScope scope(isolate); DCHECK(args.length() == 1); diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h index d4c5c6b22..9604a2a79 100644 --- a/src/runtime/runtime.h +++ b/src/runtime/runtime.h @@ -694,6 +694,7 @@ namespace internal { F(ConstructDouble, 2, 1) \ F(DoubleHi, 1, 1) \ F(DoubleLo, 1, 1) \ + F(MathClz32, 1, 1) \ F(MathFloor, 1, 1) \ F(MathSqrt, 1, 1) \ F(MathLogRT, 1, 1) \ diff --git a/src/x64/assembler-x64.cc b/src/x64/assembler-x64.cc index 1eb054772..abdf7a5d9 100644 --- a/src/x64/assembler-x64.cc +++ b/src/x64/assembler-x64.cc @@ -742,6 +742,15 @@ void Assembler::bsrl(Register dst, Register src) { } +void Assembler::bsrl(Register dst, const Operand& src) { + EnsureSpace ensure_space(this); + emit_optional_rex_32(dst, src); + emit(0x0F); + emit(0xBD); + emit_operand(dst, src); +} + + void Assembler::call(Label* L) { positions_recorder()->WriteRecordedPositions(); EnsureSpace ensure_space(this); diff --git a/src/x64/assembler-x64.h b/src/x64/assembler-x64.h index 56c99fd43..a83c5518b 100644 --- a/src/x64/assembler-x64.h +++ b/src/x64/assembler-x64.h @@ -899,6 +899,7 @@ class Assembler : public AssemblerBase { void bt(const Operand& dst, Register src); void bts(const Operand& dst, Register src); void bsrl(Register dst, Register src); + void bsrl(Register dst, const Operand& src); // Miscellaneous void clc(); diff --git a/src/x64/lithium-codegen-x64.cc b/src/x64/lithium-codegen-x64.cc index 98a76ad58..d1683e6ae 100644 --- a/src/x64/lithium-codegen-x64.cc +++ b/src/x64/lithium-codegen-x64.cc @@ -4001,14 +4001,8 @@ void LCodeGen::DoMathLog(LMathLog* instr) { void LCodeGen::DoMathClz32(LMathClz32* instr) { Register input = ToRegister(instr->value()); Register result = ToRegister(instr->result()); - Label not_zero_input; - __ bsrl(result, input); - __ j(not_zero, ¬_zero_input); - __ Set(result, 63); // 63^31 == 32 - - __ bind(¬_zero_input); - __ xorl(result, Immediate(31)); // for x in [0..31], 31^x == 31-x. + __ Lzcntl(result, input); } diff --git a/src/x64/macro-assembler-x64.cc b/src/x64/macro-assembler-x64.cc index 293b064a4..12c471c2f 100644 --- a/src/x64/macro-assembler-x64.cc +++ b/src/x64/macro-assembler-x64.cc @@ -2886,6 +2886,28 @@ void MacroAssembler::Pinsrd(XMMRegister dst, const Operand& src, int8_t imm8) { } +void MacroAssembler::Lzcntl(Register dst, Register src) { + // TODO(intel): Add support for LZCNT (BMI1/ABM). + Label not_zero_src; + bsrl(dst, src); + j(not_zero, ¬_zero_src, Label::kNear); + Set(dst, 63); // 63^31 == 32 + bind(¬_zero_src); + xorl(dst, Immediate(31)); // for x in [0..31], 31^x == 31 - x +} + + +void MacroAssembler::Lzcntl(Register dst, const Operand& src) { + // TODO(intel): Add support for LZCNT (BMI1/ABM). + Label not_zero_src; + bsrl(dst, src); + j(not_zero, ¬_zero_src, Label::kNear); + Set(dst, 63); // 63^31 == 32 + bind(¬_zero_src); + xorl(dst, Immediate(31)); // for x in [0..31], 31^x == 31 - x +} + + void MacroAssembler::Pushad() { Push(rax); Push(rcx); diff --git a/src/x64/macro-assembler-x64.h b/src/x64/macro-assembler-x64.h index 1eb7f6eff..8db4df346 100644 --- a/src/x64/macro-assembler-x64.h +++ b/src/x64/macro-assembler-x64.h @@ -927,6 +927,9 @@ class MacroAssembler: public Assembler { void Pinsrd(XMMRegister dst, Register src, int8_t imm8); void Pinsrd(XMMRegister dst, const Operand& src, int8_t imm8); + void Lzcntl(Register dst, Register src); + void Lzcntl(Register dst, const Operand& src); + // Non-x64 instructions. // Push/pop all general purpose registers. // Does not push rsp/rbp nor any of the assembler's special purpose registers diff --git a/test/cctest/test-disasm-x64.cc b/test/cctest/test-disasm-x64.cc index 8986ba76a..0eb934829 100644 --- a/test/cctest/test-disasm-x64.cc +++ b/test/cctest/test-disasm-x64.cc @@ -89,6 +89,9 @@ TEST(DisasmX64) { __ addq(rdi, Operand(rbp, rcx, times_4, -3999)); __ addq(Operand(rbp, rcx, times_4, 12), Immediate(12)); + __ bsrl(rax, r15); + __ bsrl(r9, Operand(rcx, times_8, 91919)); + __ nop(); __ addq(rbx, Immediate(12)); __ nop(); diff --git a/test/mjsunit/asm/math-clz32.js b/test/mjsunit/asm/math-clz32.js new file mode 100644 index 000000000..004aa65b4 --- /dev/null +++ b/test/mjsunit/asm/math-clz32.js @@ -0,0 +1,31 @@ +// Copyright 2015 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// Flags: --allow-natives-syntax + +var stdlib = { Math: Math }; + +var f = (function Module(stdlib) { + "use asm"; + + var clz32 = stdlib.Math.clz32; + + function f(a) { + a = a >>> 0; + return clz32(a)|0; + } + + return f; +})(stdlib); + +assertEquals(32, f(0)); +assertEquals(32, f(NaN)); +assertEquals(32, f(undefined)); +for (var i = 0; i < 32; ++i) { + assertEquals(i, f((-1) >>> i)); +} +for (var i = -2147483648; i < 2147483648; i += 3999773) { + assertEquals(%MathClz32(i), f(i)); + assertEquals(%_MathClz32(i), f(i)); +} diff --git a/test/unittests/compiler/arm/instruction-selector-arm-unittest.cc b/test/unittests/compiler/arm/instruction-selector-arm-unittest.cc index 1fa0b1084..85e52488b 100644 --- a/test/unittests/compiler/arm/instruction-selector-arm-unittest.cc +++ b/test/unittests/compiler/arm/instruction-selector-arm-unittest.cc @@ -2426,6 +2426,21 @@ TEST_F(InstructionSelectorTest, Word32AndWithWord32ShrWithImmediateForARMv7) { } } + +TEST_F(InstructionSelectorTest, Word32Clz) { + StreamBuilder m(this, kMachUint32, kMachUint32); + Node* const p0 = m.Parameter(0); + Node* const n = m.Word32Clz(p0); + m.Return(n); + Stream s = m.Build(); + ASSERT_EQ(1U, s.size()); + EXPECT_EQ(kArmClz, s[0]->arch_opcode()); + ASSERT_EQ(1U, s[0]->InputCount()); + EXPECT_EQ(s.ToVreg(p0), s.ToVreg(s[0]->InputAt(0))); + ASSERT_EQ(1U, s[0]->OutputCount()); + EXPECT_EQ(s.ToVreg(n), s.ToVreg(s[0]->Output())); +} + } // namespace compiler } // namespace internal } // namespace v8 diff --git a/test/unittests/compiler/arm64/instruction-selector-arm64-unittest.cc b/test/unittests/compiler/arm64/instruction-selector-arm64-unittest.cc index 163175bcb..02c8d2e06 100644 --- a/test/unittests/compiler/arm64/instruction-selector-arm64-unittest.cc +++ b/test/unittests/compiler/arm64/instruction-selector-arm64-unittest.cc @@ -2242,6 +2242,21 @@ TEST_F(InstructionSelectorTest, Word32SarWithWord32Shl) { } } + +TEST_F(InstructionSelectorTest, Word32Clz) { + StreamBuilder m(this, kMachUint32, kMachUint32); + Node* const p0 = m.Parameter(0); + Node* const n = m.Word32Clz(p0); + m.Return(n); + Stream s = m.Build(); + ASSERT_EQ(1U, s.size()); + EXPECT_EQ(kArm64Clz32, s[0]->arch_opcode()); + ASSERT_EQ(1U, s[0]->InputCount()); + EXPECT_EQ(s.ToVreg(p0), s.ToVreg(s[0]->InputAt(0))); + ASSERT_EQ(1U, s[0]->OutputCount()); + EXPECT_EQ(s.ToVreg(n), s.ToVreg(s[0]->Output())); +} + } // namespace compiler } // namespace internal } // namespace v8 diff --git a/test/unittests/compiler/ia32/instruction-selector-ia32-unittest.cc b/test/unittests/compiler/ia32/instruction-selector-ia32-unittest.cc index a93b3fcaf..9138ab2ca 100644 --- a/test/unittests/compiler/ia32/instruction-selector-ia32-unittest.cc +++ b/test/unittests/compiler/ia32/instruction-selector-ia32-unittest.cc @@ -11,9 +11,9 @@ namespace compiler { namespace { // Immediates (random subset). -static const int32_t kImmediates[] = { - kMinInt, -42, -1, 0, 1, 2, 3, 4, 5, - 6, 7, 8, 16, 42, 0xff, 0xffff, 0x0f0f0f0f, kMaxInt}; +const int32_t kImmediates[] = {kMinInt, -42, -1, 0, 1, 2, + 3, 4, 5, 6, 7, 8, + 16, 42, 0xff, 0xffff, 0x0f0f0f0f, kMaxInt}; } // namespace @@ -689,6 +689,21 @@ TEST_F(InstructionSelectorTest, Uint32LessThanWithLoadAndLoadStackPointer) { EXPECT_EQ(kUnsignedGreaterThan, s[0]->flags_condition()); } + +TEST_F(InstructionSelectorTest, Word32Clz) { + StreamBuilder m(this, kMachUint32, kMachUint32); + Node* const p0 = m.Parameter(0); + Node* const n = m.Word32Clz(p0); + m.Return(n); + Stream s = m.Build(); + ASSERT_EQ(1U, s.size()); + EXPECT_EQ(kIA32Lzcnt, s[0]->arch_opcode()); + ASSERT_EQ(1U, s[0]->InputCount()); + EXPECT_EQ(s.ToVreg(p0), s.ToVreg(s[0]->InputAt(0))); + ASSERT_EQ(1U, s[0]->OutputCount()); + EXPECT_EQ(s.ToVreg(n), s.ToVreg(s[0]->Output())); +} + } // namespace compiler } // namespace internal } // namespace v8 diff --git a/test/unittests/compiler/js-intrinsic-lowering-unittest.cc b/test/unittests/compiler/js-intrinsic-lowering-unittest.cc index 96331b509..8adbc54ac 100644 --- a/test/unittests/compiler/js-intrinsic-lowering-unittest.cc +++ b/test/unittests/compiler/js-intrinsic-lowering-unittest.cc @@ -295,6 +295,23 @@ TEST_F(JSIntrinsicLoweringTest, InlineStringGetLength) { } +// ----------------------------------------------------------------------------- +// %_MathClz32 + + +TEST_F(JSIntrinsicLoweringTest, InlineMathClz32) { + Node* const input = Parameter(0); + Node* const context = Parameter(1); + Node* const effect = graph()->start(); + Node* const control = graph()->start(); + Reduction const r = Reduce( + graph()->NewNode(javascript()->CallRuntime(Runtime::kInlineMathClz32, 1), + input, context, effect, control)); + ASSERT_TRUE(r.Changed()); + EXPECT_THAT(r.replacement(), IsWord32Clz(input)); +} + + // ----------------------------------------------------------------------------- // %_ValueOf diff --git a/test/unittests/compiler/machine-operator-unittest.cc b/test/unittests/compiler/machine-operator-unittest.cc index 8244c3791..71b3c0edd 100644 --- a/test/unittests/compiler/machine-operator-unittest.cc +++ b/test/unittests/compiler/machine-operator-unittest.cc @@ -180,24 +180,24 @@ const PureOperator kPureOperators[] = { PURE(Word32And, 2, 0, 1), PURE(Word32Or, 2, 0, 1), PURE(Word32Xor, 2, 0, 1), PURE(Word32Shl, 2, 0, 1), PURE(Word32Shr, 2, 0, 1), PURE(Word32Sar, 2, 0, 1), PURE(Word32Ror, 2, 0, 1), - PURE(Word32Equal, 2, 0, 1), PURE(Word64And, 2, 0, 1), - PURE(Word64Or, 2, 0, 1), PURE(Word64Xor, 2, 0, 1), PURE(Word64Shl, 2, 0, 1), - PURE(Word64Shr, 2, 0, 1), PURE(Word64Sar, 2, 0, 1), - PURE(Word64Ror, 2, 0, 1), PURE(Word64Equal, 2, 0, 1), - PURE(Int32Add, 2, 0, 1), PURE(Int32AddWithOverflow, 2, 0, 2), - PURE(Int32Sub, 2, 0, 1), PURE(Int32SubWithOverflow, 2, 0, 2), - PURE(Int32Mul, 2, 0, 1), PURE(Int32MulHigh, 2, 0, 1), - PURE(Int32Div, 2, 1, 1), PURE(Uint32Div, 2, 1, 1), PURE(Int32Mod, 2, 1, 1), - PURE(Uint32Mod, 2, 1, 1), PURE(Int32LessThan, 2, 0, 1), - PURE(Int32LessThanOrEqual, 2, 0, 1), PURE(Uint32LessThan, 2, 0, 1), - PURE(Uint32LessThanOrEqual, 2, 0, 1), PURE(Int64Add, 2, 0, 1), - PURE(Int64Sub, 2, 0, 1), PURE(Int64Mul, 2, 0, 1), PURE(Int64Div, 2, 0, 1), - PURE(Uint64Div, 2, 0, 1), PURE(Int64Mod, 2, 0, 1), PURE(Uint64Mod, 2, 0, 1), - PURE(Int64LessThan, 2, 0, 1), PURE(Int64LessThanOrEqual, 2, 0, 1), - PURE(Uint64LessThan, 2, 0, 1), PURE(ChangeFloat32ToFloat64, 1, 0, 1), - PURE(ChangeFloat64ToInt32, 1, 0, 1), PURE(ChangeFloat64ToUint32, 1, 0, 1), - PURE(ChangeInt32ToInt64, 1, 0, 1), PURE(ChangeUint32ToFloat64, 1, 0, 1), - PURE(ChangeUint32ToUint64, 1, 0, 1), + PURE(Word32Equal, 2, 0, 1), PURE(Word32Clz, 1, 0, 1), + PURE(Word64And, 2, 0, 1), PURE(Word64Or, 2, 0, 1), PURE(Word64Xor, 2, 0, 1), + PURE(Word64Shl, 2, 0, 1), PURE(Word64Shr, 2, 0, 1), + PURE(Word64Sar, 2, 0, 1), PURE(Word64Ror, 2, 0, 1), + PURE(Word64Equal, 2, 0, 1), PURE(Int32Add, 2, 0, 1), + PURE(Int32AddWithOverflow, 2, 0, 2), PURE(Int32Sub, 2, 0, 1), + PURE(Int32SubWithOverflow, 2, 0, 2), PURE(Int32Mul, 2, 0, 1), + PURE(Int32MulHigh, 2, 0, 1), PURE(Int32Div, 2, 1, 1), + PURE(Uint32Div, 2, 1, 1), PURE(Int32Mod, 2, 1, 1), PURE(Uint32Mod, 2, 1, 1), + PURE(Int32LessThan, 2, 0, 1), PURE(Int32LessThanOrEqual, 2, 0, 1), + PURE(Uint32LessThan, 2, 0, 1), PURE(Uint32LessThanOrEqual, 2, 0, 1), + PURE(Int64Add, 2, 0, 1), PURE(Int64Sub, 2, 0, 1), PURE(Int64Mul, 2, 0, 1), + PURE(Int64Div, 2, 0, 1), PURE(Uint64Div, 2, 0, 1), PURE(Int64Mod, 2, 0, 1), + PURE(Uint64Mod, 2, 0, 1), PURE(Int64LessThan, 2, 0, 1), + PURE(Int64LessThanOrEqual, 2, 0, 1), PURE(Uint64LessThan, 2, 0, 1), + PURE(ChangeFloat32ToFloat64, 1, 0, 1), PURE(ChangeFloat64ToInt32, 1, 0, 1), + PURE(ChangeFloat64ToUint32, 1, 0, 1), PURE(ChangeInt32ToInt64, 1, 0, 1), + PURE(ChangeUint32ToFloat64, 1, 0, 1), PURE(ChangeUint32ToUint64, 1, 0, 1), PURE(TruncateFloat64ToFloat32, 1, 0, 1), PURE(TruncateFloat64ToInt32, 1, 0, 1), PURE(TruncateInt64ToInt32, 1, 0, 1), PURE(Float64Add, 2, 0, 1), PURE(Float64Sub, 2, 0, 1), diff --git a/test/unittests/compiler/node-test-utils.cc b/test/unittests/compiler/node-test-utils.cc index 5c4f81dd6..5890b49b0 100644 --- a/test/unittests/compiler/node-test-utils.cc +++ b/test/unittests/compiler/node-test-utils.cc @@ -1634,6 +1634,7 @@ IS_UNOP_MATCHER(NumberToInt32) IS_UNOP_MATCHER(NumberToUint32) IS_UNOP_MATCHER(ObjectIsSmi) IS_UNOP_MATCHER(ObjectIsNonNegativeSmi) +IS_UNOP_MATCHER(Word32Clz) #undef IS_UNOP_MATCHER } // namespace compiler diff --git a/test/unittests/compiler/node-test-utils.h b/test/unittests/compiler/node-test-utils.h index b10e358bb..7c306a2c9 100644 --- a/test/unittests/compiler/node-test-utils.h +++ b/test/unittests/compiler/node-test-utils.h @@ -169,6 +169,7 @@ Matcher IsWord32Ror(const Matcher& lhs_matcher, const Matcher& rhs_matcher); Matcher IsWord32Equal(const Matcher& lhs_matcher, const Matcher& rhs_matcher); +Matcher IsWord32Clz(const Matcher& value_matcher); Matcher IsWord64And(const Matcher& lhs_matcher, const Matcher& rhs_matcher); Matcher IsWord64Shl(const Matcher& lhs_matcher, diff --git a/test/unittests/compiler/x64/instruction-selector-x64-unittest.cc b/test/unittests/compiler/x64/instruction-selector-x64-unittest.cc index 13899c5c3..a83deafe7 100644 --- a/test/unittests/compiler/x64/instruction-selector-x64-unittest.cc +++ b/test/unittests/compiler/x64/instruction-selector-x64-unittest.cc @@ -1146,6 +1146,21 @@ TEST_F(InstructionSelectorTest, Word32AndWith0xffff) { } } + +TEST_F(InstructionSelectorTest, Word32Clz) { + StreamBuilder m(this, kMachUint32, kMachUint32); + Node* const p0 = m.Parameter(0); + Node* const n = m.Word32Clz(p0); + m.Return(n); + Stream s = m.Build(); + ASSERT_EQ(1U, s.size()); + EXPECT_EQ(kX64Lzcnt32, s[0]->arch_opcode()); + ASSERT_EQ(1U, s[0]->InputCount()); + EXPECT_EQ(s.ToVreg(p0), s.ToVreg(s[0]->InputAt(0))); + ASSERT_EQ(1U, s[0]->OutputCount()); + EXPECT_EQ(s.ToVreg(n), s.ToVreg(s[0]->Output())); +} + } // namespace compiler } // namespace internal } // namespace v8 -- 2.34.1