From 45ff9d53c5c3fe4f6c9d58a7e3d200abc555a9d8 Mon Sep 17 00:00:00 2001 From: Benedikt Meurer Date: Fri, 14 Nov 2014 09:21:04 +0100 Subject: [PATCH] [turbofan] Optimize remainder of integer division by unknown power of two. Drive-by-Fix: minint % 0 was broken on ARM, but we didn't notice because there was no test covering that case... TEST=msjunit R=svenpanne@chromium.org Review URL: https://codereview.chromium.org/727673002 Cr-Commit-Position: refs/heads/master@{#25347} --- src/compiler/arm/instruction-selector-arm.cc | 4 +- src/compiler/machine-operator.h | 6 +- src/compiler/simplified-lowering.cc | 144 +++++++++++++++++++++++---- test/mjsunit/asm/int32mod-constant.js | 33 ++++++ test/mjsunit/asm/int32mod.js | 27 ++--- test/mjsunit/asm/uint32mod-constant.js | 29 ++++++ test/mjsunit/asm/uint32mod.js | 24 ++--- 7 files changed, 211 insertions(+), 56 deletions(-) create mode 100644 test/mjsunit/asm/int32mod-constant.js create mode 100644 test/mjsunit/asm/uint32mod-constant.js diff --git a/src/compiler/arm/instruction-selector-arm.cc b/src/compiler/arm/instruction-selector-arm.cc index 24168cc..146aede 100644 --- a/src/compiler/arm/instruction-selector-arm.cc +++ b/src/compiler/arm/instruction-selector-arm.cc @@ -1255,9 +1255,7 @@ MachineOperatorBuilder::Flags InstructionSelector::SupportedMachineOperatorFlags() { MachineOperatorBuilder::Flags flags = MachineOperatorBuilder::kInt32DivIsSafe | - MachineOperatorBuilder::kInt32ModIsSafe | - MachineOperatorBuilder::kUint32DivIsSafe | - MachineOperatorBuilder::kUint32ModIsSafe; + MachineOperatorBuilder::kUint32DivIsSafe; if (CpuFeatures::IsSupported(ARMv8)) { flags |= MachineOperatorBuilder::kFloat64Floor | diff --git a/src/compiler/machine-operator.h b/src/compiler/machine-operator.h index 8c0d11a..82d2e89 100644 --- a/src/compiler/machine-operator.h +++ b/src/compiler/machine-operator.h @@ -67,9 +67,7 @@ class MachineOperatorBuilder FINAL : public ZoneObject { kFloat64RoundTruncate = 1u << 2, kFloat64RoundTiesAway = 1u << 3, kInt32DivIsSafe = 1u << 4, - kInt32ModIsSafe = 1u << 5, - kUint32DivIsSafe = 1u << 6, - kUint32ModIsSafe = 1u << 7 + kUint32DivIsSafe = 1u << 5 }; typedef base::Flags Flags; @@ -110,9 +108,7 @@ class MachineOperatorBuilder FINAL : public ZoneObject { const Operator* Uint32Mod(); const Operator* Uint32MulHigh(); bool Int32DivIsSafe() const { return flags_ & kInt32DivIsSafe; } - bool Int32ModIsSafe() const { return flags_ & kInt32ModIsSafe; } bool Uint32DivIsSafe() const { return flags_ & kUint32DivIsSafe; } - bool Uint32ModIsSafe() const { return flags_ & kUint32ModIsSafe; } const Operator* Int64Add(); const Operator* Int64Sub(); diff --git a/src/compiler/simplified-lowering.cc b/src/compiler/simplified-lowering.cc index 33a3077..8d770c0 100644 --- a/src/compiler/simplified-lowering.cc +++ b/src/compiler/simplified-lowering.cc @@ -1325,28 +1325,98 @@ Node* SimplifiedLowering::Int32Div(Node* const node) { Node* SimplifiedLowering::Int32Mod(Node* const node) { Int32BinopMatcher m(node); Node* const zero = jsgraph()->Int32Constant(0); + Node* const minus_one = jsgraph()->Int32Constant(-1); Node* const lhs = m.left().node(); Node* const rhs = m.right().node(); if (m.right().Is(-1) || m.right().Is(0)) { return zero; - } else if (machine()->Int32ModIsSafe() || m.right().HasValue()) { + } else if (m.right().HasValue()) { return graph()->NewNode(machine()->Int32Mod(), lhs, rhs, graph()->start()); } - Diamond if_zero(graph(), common(), - graph()->NewNode(machine()->Word32Equal(), rhs, zero), - BranchHint::kFalse); + // General case for signed integer modulus, with optimization for (unknown) + // power of 2 right hand side. + // + // if 0 < rhs then + // msk = rhs - 1 + // if rhs & msk != 0 then + // lhs % rhs + // else + // if lhs < 0 then + // -(-lhs & msk) + // else + // lhs & msk + // else + // if rhs < -1 then + // lhs % rhs + // else + // zero + // + // Note: We do not use the Diamond helper class here, because it really hurts + // readability with nested diamonds. + const Operator* const merge_op = common()->Merge(2); + const Operator* const phi_op = common()->Phi(kMachInt32, 2); + + Node* check0 = graph()->NewNode(machine()->Int32LessThan(), zero, rhs); + Node* branch0 = graph()->NewNode(common()->Branch(BranchHint::kTrue), check0, + graph()->start()); + + Node* if_true0 = graph()->NewNode(common()->IfTrue(), branch0); + Node* true0; + { + Node* msk = graph()->NewNode(machine()->Int32Add(), rhs, minus_one); + + Node* check1 = graph()->NewNode(machine()->Word32And(), rhs, msk); + Node* branch1 = graph()->NewNode(common()->Branch(), check1, if_true0); + + Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1); + Node* true1 = graph()->NewNode(machine()->Int32Mod(), lhs, rhs, if_true1); + + Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1); + Node* false1; + { + Node* check2 = graph()->NewNode(machine()->Int32LessThan(), lhs, zero); + Node* branch2 = graph()->NewNode(common()->Branch(BranchHint::kFalse), + check2, if_false1); + + Node* if_true2 = graph()->NewNode(common()->IfTrue(), branch2); + Node* true2 = graph()->NewNode( + machine()->Int32Sub(), zero, + graph()->NewNode(machine()->Word32And(), + graph()->NewNode(machine()->Int32Sub(), zero, lhs), + msk)); + + Node* if_false2 = graph()->NewNode(common()->IfFalse(), branch2); + Node* false2 = graph()->NewNode(machine()->Word32And(), lhs, msk); + + if_false1 = graph()->NewNode(merge_op, if_true2, if_false2); + false1 = graph()->NewNode(phi_op, true2, false2, if_false1); + } - Diamond if_minus_one(graph(), common(), - graph()->NewNode(machine()->Word32Equal(), rhs, - jsgraph()->Int32Constant(-1)), - BranchHint::kFalse); - if_minus_one.Nest(if_zero, false); - Node* mod = - graph()->NewNode(machine()->Int32Mod(), lhs, rhs, if_minus_one.if_false); + if_true0 = graph()->NewNode(merge_op, if_true1, if_false1); + true0 = graph()->NewNode(phi_op, true1, false1, if_true0); + } - return if_zero.Phi(kMachInt32, zero, if_minus_one.Phi(kMachInt32, zero, mod)); + Node* if_false0 = graph()->NewNode(common()->IfFalse(), branch0); + Node* false0; + { + Node* check1 = graph()->NewNode(machine()->Int32LessThan(), rhs, minus_one); + Node* branch1 = graph()->NewNode(common()->Branch(BranchHint::kTrue), + check1, if_false0); + + Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1); + Node* true1 = graph()->NewNode(machine()->Int32Mod(), lhs, rhs, if_true1); + + Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1); + Node* false1 = zero; + + if_false0 = graph()->NewNode(merge_op, if_true1, if_false1); + false0 = graph()->NewNode(phi_op, true1, false1, if_false0); + } + + Node* merge0 = graph()->NewNode(merge_op, if_true0, if_false0); + return graph()->NewNode(phi_op, true0, false0, merge0); } @@ -1371,20 +1441,60 @@ Node* SimplifiedLowering::Uint32Div(Node* const node) { Node* SimplifiedLowering::Uint32Mod(Node* const node) { Uint32BinopMatcher m(node); + Node* const minus_one = jsgraph()->Int32Constant(-1); Node* const zero = jsgraph()->Uint32Constant(0); Node* const lhs = m.left().node(); Node* const rhs = m.right().node(); if (m.right().Is(0)) { return zero; - } else if (machine()->Uint32ModIsSafe() || m.right().HasValue()) { + } else if (m.right().HasValue()) { return graph()->NewNode(machine()->Uint32Mod(), lhs, rhs, graph()->start()); } - Node* check = graph()->NewNode(machine()->Word32Equal(), rhs, zero); - Diamond d(graph(), common(), check, BranchHint::kFalse); - Node* mod = graph()->NewNode(machine()->Uint32Mod(), lhs, rhs, d.if_false); - return d.Phi(kMachUint32, zero, mod); + // General case for unsigned integer modulus, with optimization for (unknown) + // power of 2 right hand side. + // + // if rhs then + // msk = rhs - 1 + // if rhs & msk != 0 then + // lhs % rhs + // else + // lhs & msk + // else + // zero + // + // Note: We do not use the Diamond helper class here, because it really hurts + // readability with nested diamonds. + const Operator* const merge_op = common()->Merge(2); + const Operator* const phi_op = common()->Phi(kMachInt32, 2); + + Node* branch0 = graph()->NewNode(common()->Branch(BranchHint::kTrue), rhs, + graph()->start()); + + Node* if_true0 = graph()->NewNode(common()->IfTrue(), branch0); + Node* true0; + { + Node* msk = graph()->NewNode(machine()->Int32Add(), rhs, minus_one); + + Node* check1 = graph()->NewNode(machine()->Word32And(), rhs, msk); + Node* branch1 = graph()->NewNode(common()->Branch(), check1, if_true0); + + Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1); + Node* true1 = graph()->NewNode(machine()->Uint32Mod(), lhs, rhs, if_true1); + + Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1); + Node* false1 = graph()->NewNode(machine()->Word32And(), lhs, msk); + + if_true0 = graph()->NewNode(merge_op, if_true1, if_false1); + true0 = graph()->NewNode(phi_op, true1, false1, if_true0); + } + + Node* if_false0 = graph()->NewNode(common()->IfFalse(), branch0); + Node* false0 = zero; + + Node* merge0 = graph()->NewNode(merge_op, if_true0, if_false0); + return graph()->NewNode(phi_op, true0, false0, merge0); } diff --git a/test/mjsunit/asm/int32mod-constant.js b/test/mjsunit/asm/int32mod-constant.js new file mode 100644 index 0000000..fdbdc5d --- /dev/null +++ b/test/mjsunit/asm/int32mod-constant.js @@ -0,0 +1,33 @@ +// Copyright 2014 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. + +var stdlib = {}; +var foreign = {}; +var heap = new ArrayBuffer(64 * 1024); + +function Int32Mod(divisor) { + var name = "mod_"; + if (divisor < 0) { + name += "minus_"; + } + name += Math.abs(divisor); + var m = eval("function Module(stdlib, foreign, heap) {\n" + + " \"use asm\";\n" + + " function " + name + "(dividend) {\n" + + " return ((dividend | 0) % " + divisor + ") | 0;\n" + + " }\n" + + " return { f: " + name + "}\n" + + "}; Module"); + return m(stdlib, foreign, heap).f; +} + +var divisors = [-2147483648, -32 * 1024, -1000, -16, -7, -2, -1, 0, + 1, 3, 4, 10, 64, 100, 1024, 2147483647]; +for (var i in divisors) { + var divisor = divisors[i]; + var mod = Int32Mod(divisor); + for (var dividend = -2147483648; dividend < 2147483648; dividend += 3999773) { + assertEquals((dividend % divisor) | 0, mod(dividend)); + } +} diff --git a/test/mjsunit/asm/int32mod.js b/test/mjsunit/asm/int32mod.js index ec3e887..22fa813 100644 --- a/test/mjsunit/asm/int32mod.js +++ b/test/mjsunit/asm/int32mod.js @@ -6,28 +6,21 @@ var stdlib = {}; var foreign = {}; var heap = new ArrayBuffer(64 * 1024); -function Int32Mod(divisor) { - var name = "mod_"; - if (divisor < 0) { - name += "minus_"; +var mod = (function Module(stdlib, foreign, heap) { + "use asm"; + function mod(dividend, divisor) { + dividend = dividend|0; + divisor = divisor|0; + return (dividend % divisor) | 0; } - name += Math.abs(divisor); - var m = eval("function Module(stdlib, foreign, heap) {\n" - + " \"use asm\";\n" - + " function " + name + "(dividend) {\n" - + " return ((dividend | 0) % " + divisor + ") | 0;\n" - + " }\n" - + " return { f: " + name + "}\n" - + "}; Module"); - return m(stdlib, foreign, heap).f; -} + return { mod: mod }; +})(stdlib, foreign, heap).mod; -var divisors = [-2147483648, -32 * 1024, -1000, -16, -7, -2, -1, +var divisors = [-2147483648, -32 * 1024, -1000, -16, -7, -2, -1, 0, 1, 3, 4, 10, 64, 100, 1024, 2147483647]; for (var i in divisors) { var divisor = divisors[i]; - var mod = Int32Mod(divisor); for (var dividend = -2147483648; dividend < 2147483648; dividend += 3999773) { - assertEquals((dividend % divisor) | 0, mod(dividend)); + assertEquals((dividend % divisor) | 0, mod(dividend, divisor)); } } diff --git a/test/mjsunit/asm/uint32mod-constant.js b/test/mjsunit/asm/uint32mod-constant.js new file mode 100644 index 0000000..4ba94da --- /dev/null +++ b/test/mjsunit/asm/uint32mod-constant.js @@ -0,0 +1,29 @@ +// Copyright 2014 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. + +var stdlib = {}; +var foreign = {}; +var heap = new ArrayBuffer(64 * 1024); + +function Uint32Mod(divisor) { + var name = "mod_"; + name += divisor; + var m = eval("function Module(stdlib, foreign, heap) {\n" + + " \"use asm\";\n" + + " function " + name + "(dividend) {\n" + + " return ((dividend >>> 0) % " + divisor + ") >>> 0;\n" + + " }\n" + + " return { f: " + name + "}\n" + + "}; Module"); + return m(stdlib, foreign, heap).f; +} + +var divisors = [0, 1, 3, 4, 10, 42, 64, 100, 1024, 2147483647, 4294967295]; +for (var i in divisors) { + var divisor = divisors[i]; + var mod = Uint32Mod(divisor); + for (var dividend = 0; dividend < 4294967296; dividend += 3999773) { + assertEquals((dividend % divisor) >>> 0, mod(dividend)); + } +} diff --git a/test/mjsunit/asm/uint32mod.js b/test/mjsunit/asm/uint32mod.js index 4ba94da..fa40507 100644 --- a/test/mjsunit/asm/uint32mod.js +++ b/test/mjsunit/asm/uint32mod.js @@ -6,24 +6,20 @@ var stdlib = {}; var foreign = {}; var heap = new ArrayBuffer(64 * 1024); -function Uint32Mod(divisor) { - var name = "mod_"; - name += divisor; - var m = eval("function Module(stdlib, foreign, heap) {\n" - + " \"use asm\";\n" - + " function " + name + "(dividend) {\n" - + " return ((dividend >>> 0) % " + divisor + ") >>> 0;\n" - + " }\n" - + " return { f: " + name + "}\n" - + "}; Module"); - return m(stdlib, foreign, heap).f; -} +var mod = (function Module(stdlib, foreign, heap) { + "use asm"; + function mod(dividend, divisor) { + dividend = dividend >>> 0; + divisor = divisor >>> 0; + return (dividend % divisor) >>> 0; + } + return { mod: mod }; +})(stdlib, foreign, heap).mod; var divisors = [0, 1, 3, 4, 10, 42, 64, 100, 1024, 2147483647, 4294967295]; for (var i in divisors) { var divisor = divisors[i]; - var mod = Uint32Mod(divisor); for (var dividend = 0; dividend < 4294967296; dividend += 3999773) { - assertEquals((dividend % divisor) >>> 0, mod(dividend)); + assertEquals((dividend % divisor) >>> 0, mod(dividend, divisor)); } } -- 2.7.4