From ae7d781d8b940b3e0079ee046751802c73c27e87 Mon Sep 17 00:00:00 2001 From: "bmeurer@chromium.org" Date: Thu, 14 Aug 2014 09:07:58 +0000 Subject: [PATCH] [turbofan] Introduce WordRor machine operator. Move recognition of rotate-right operations to the MachineOperatorReducer, so we don't need to repeat that in the InstructionSelector for every backend. TEST=base-unittests,compiler-unittests,cctests R=jarin@chromium.org Review URL: https://codereview.chromium.org/469213002 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23121 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- BUILD.gn | 1 + src/base/bits.h | 29 ++++ src/compiler/arm/instruction-selector-arm.cc | 60 ++------ src/compiler/arm64/code-generator-arm64.cc | 6 + src/compiler/arm64/instruction-codes-arm64.h | 2 + .../arm64/instruction-selector-arm64.cc | 10 ++ src/compiler/ia32/code-generator-ia32.cc | 7 + src/compiler/ia32/instruction-codes-ia32.h | 1 + .../ia32/instruction-selector-ia32.cc | 5 + src/compiler/instruction-selector.cc | 7 + src/compiler/machine-node-factory.h | 12 +- src/compiler/machine-operator-reducer.cc | 60 ++++++++ src/compiler/machine-operator.h | 3 + src/compiler/opcodes.h | 2 + src/compiler/x64/code-generator-x64.cc | 6 + src/compiler/x64/instruction-codes-x64.h | 2 + src/compiler/x64/instruction-selector-x64.cc | 10 ++ test/base-unittests/DEPS | 1 + test/base-unittests/base-unittests.gyp | 1 + test/base-unittests/bits-unittest.cc | 34 +++++ test/cctest/compiler/test-run-machops.cc | 94 +++++------- .../compiler-unittests/compiler-unittests.gyp | 1 + .../machine-operator-reducer-unittest.cc | 139 ++++++++++++++++++ test/compiler-unittests/node-matchers.cc | 1 + test/compiler-unittests/node-matchers.h | 2 + tools/gyp/v8.gyp | 1 + 26 files changed, 384 insertions(+), 113 deletions(-) create mode 100644 src/base/bits.h create mode 100644 test/base-unittests/bits-unittest.cc create mode 100644 test/compiler-unittests/machine-operator-reducer-unittest.cc diff --git a/BUILD.gn b/BUILD.gn index efa4b717c..2c924f6ee 100644 --- a/BUILD.gn +++ b/BUILD.gn @@ -1089,6 +1089,7 @@ source_set("v8_libbase") { "src/base/atomicops_internals_x86_gcc.cc", "src/base/atomicops_internals_x86_gcc.h", "src/base/atomicops_internals_x86_msvc.h", + "src/base/bits.h", "src/base/build_config.h", "src/base/cpu.cc", "src/base/cpu.h", diff --git a/src/base/bits.h b/src/base/bits.h new file mode 100644 index 000000000..e16eed1b6 --- /dev/null +++ b/src/base/bits.h @@ -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. + +#ifndef V8_BASE_BITS_H_ +#define V8_BASE_BITS_H_ + +#include "include/v8stdint.h" + +namespace v8 { +namespace base { +namespace bits { + +inline uint32_t RotateRight32(uint32_t value, uint32_t shift) { + if (shift == 0) return value; + return (value >> shift) | (value << (32 - shift)); +} + + +inline uint64_t RotateRight64(uint64_t value, uint64_t shift) { + if (shift == 0) return value; + return (value >> shift) | (value << (64 - shift)); +} + +} // namespace bits +} // namespace base +} // namespace v8 + +#endif // V8_BASE_BITS_H_ diff --git a/src/compiler/arm/instruction-selector-arm.cc b/src/compiler/arm/instruction-selector-arm.cc index 22af55fae..a1f9d4eb3 100644 --- a/src/compiler/arm/instruction-selector-arm.cc +++ b/src/compiler/arm/instruction-selector-arm.cc @@ -126,48 +126,17 @@ static bool TryMatchROR(InstructionSelector* selector, InstructionOperand** value_return, InstructionOperand** shift_return) { ArmOperandGenerator g(selector); - if (node->opcode() != IrOpcode::kWord32Or) return false; + if (node->opcode() != IrOpcode::kWord32Ror) return false; Int32BinopMatcher m(node); - Node* shl = m.left().node(); - Node* shr = m.right().node(); - if (m.left().IsWord32Shr() && m.right().IsWord32Shl()) { - std::swap(shl, shr); - } else if (!m.left().IsWord32Shl() || !m.right().IsWord32Shr()) { - return false; - } - Int32BinopMatcher mshr(shr); - Int32BinopMatcher mshl(shl); - Node* value = mshr.left().node(); - if (value != mshl.left().node()) return false; - Node* shift = mshr.right().node(); - Int32Matcher mshift(shift); - if (mshift.IsInRange(1, 31)) { - if (mshl.right().Is(32 - mshift.Value())) { - *opcode_return |= AddressingModeField::encode(kMode_Operand2_R_ROR_I); - *value_return = g.UseRegister(value); - *shift_return = g.UseImmediate(shift); - return true; - } - if (mshl.right().IsInt32Sub()) { - Int32BinopMatcher mshlright(mshl.right().node()); - if (mshlright.left().Is(32) && mshlright.right().Is(mshift.Value())) { - *opcode_return |= AddressingModeField::encode(kMode_Operand2_R_ROR_I); - *value_return = g.UseRegister(value); - *shift_return = g.UseImmediate(shift); - return true; - } - } - } - if (mshl.right().IsInt32Sub()) { - Int32BinopMatcher mshlright(mshl.right().node()); - if (!mshlright.left().Is(32)) return false; - if (mshlright.right().node() != shift) return false; + *value_return = g.UseRegister(m.left().node()); + if (m.right().IsInRange(1, 31)) { + *opcode_return |= AddressingModeField::encode(kMode_Operand2_R_ROR_I); + *shift_return = g.UseImmediate(m.right().node()); + } else { *opcode_return |= AddressingModeField::encode(kMode_Operand2_R_ROR_R); - *value_return = g.UseRegister(value); - *shift_return = g.UseRegister(shift); - return true; + *shift_return = g.UseRegister(m.right().node()); } - return false; + return true; } @@ -482,14 +451,6 @@ void InstructionSelector::VisitWord32And(Node* node) { void InstructionSelector::VisitWord32Or(Node* node) { - ArmOperandGenerator g(this); - InstructionCode opcode = kArmMov; - InstructionOperand* value_operand; - InstructionOperand* shift_operand; - if (TryMatchROR(this, &opcode, node, &value_operand, &shift_operand)) { - Emit(opcode, g.DefineAsRegister(node), value_operand, shift_operand); - return; - } VisitBinop(this, node, kArmOrr, kArmOrr); } @@ -562,6 +523,11 @@ void InstructionSelector::VisitWord32Sar(Node* node) { } +void InstructionSelector::VisitWord32Ror(Node* node) { + VisitShift(this, node, TryMatchROR); +} + + 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 43b1c7e91..f21462e27 100644 --- a/src/compiler/arm64/code-generator-arm64.cc +++ b/src/compiler/arm64/code-generator-arm64.cc @@ -268,6 +268,12 @@ void CodeGenerator::AssembleArchInstruction(Instruction* instr) { case kArm64Sar32: ASSEMBLE_SHIFT(Asr, 32); break; + case kArm64Ror: + ASSEMBLE_SHIFT(Ror, 64); + break; + case kArm64Ror32: + ASSEMBLE_SHIFT(Ror, 32); + break; case kArm64CallCodeObject: { if (instr->InputAt(0)->IsImmediate()) { Handle code = Handle::cast(i.InputHeapObject(0)); diff --git a/src/compiler/arm64/instruction-codes-arm64.h b/src/compiler/arm64/instruction-codes-arm64.h index 2d71c02ef..c13c4d429 100644 --- a/src/compiler/arm64/instruction-codes-arm64.h +++ b/src/compiler/arm64/instruction-codes-arm64.h @@ -46,6 +46,8 @@ namespace compiler { V(Arm64Shr32) \ V(Arm64Sar) \ V(Arm64Sar32) \ + V(Arm64Ror) \ + V(Arm64Ror32) \ V(Arm64CallCodeObject) \ V(Arm64CallJSFunction) \ V(Arm64CallAddress) \ diff --git a/src/compiler/arm64/instruction-selector-arm64.cc b/src/compiler/arm64/instruction-selector-arm64.cc index 111ca2d95..0d7dbb669 100644 --- a/src/compiler/arm64/instruction-selector-arm64.cc +++ b/src/compiler/arm64/instruction-selector-arm64.cc @@ -329,6 +329,16 @@ void InstructionSelector::VisitWord64Sar(Node* node) { } +void InstructionSelector::VisitWord32Ror(Node* node) { + VisitRRO(this, kArm64Ror32, node, kShift32Imm); +} + + +void InstructionSelector::VisitWord64Ror(Node* node) { + VisitRRO(this, kArm64Ror, node, kShift64Imm); +} + + void InstructionSelector::VisitInt32Add(Node* node) { VisitBinop(this, node, kArm64Add32, kArithimeticImm); } diff --git a/src/compiler/ia32/code-generator-ia32.cc b/src/compiler/ia32/code-generator-ia32.cc index 9fef74081..ad80e49e0 100644 --- a/src/compiler/ia32/code-generator-ia32.cc +++ b/src/compiler/ia32/code-generator-ia32.cc @@ -220,6 +220,13 @@ void CodeGenerator::AssembleArchInstruction(Instruction* instr) { __ sar_cl(i.OutputRegister()); } break; + case kIA32Ror: + if (HasImmediateInput(instr, 1)) { + __ ror(i.OutputRegister(), i.InputInt5(1)); + } else { + __ ror_cl(i.OutputRegister()); + } + break; case kIA32Push: if (HasImmediateInput(instr, 0)) { __ push(i.InputImmediate(0)); diff --git a/src/compiler/ia32/instruction-codes-ia32.h b/src/compiler/ia32/instruction-codes-ia32.h index f175ebb55..0b0944e4c 100644 --- a/src/compiler/ia32/instruction-codes-ia32.h +++ b/src/compiler/ia32/instruction-codes-ia32.h @@ -27,6 +27,7 @@ namespace compiler { V(IA32Shl) \ V(IA32Shr) \ V(IA32Sar) \ + V(IA32Ror) \ V(IA32Push) \ V(IA32CallCodeObject) \ V(IA32CallAddress) \ diff --git a/src/compiler/ia32/instruction-selector-ia32.cc b/src/compiler/ia32/instruction-selector-ia32.cc index a057a1e71..1e22aa638 100644 --- a/src/compiler/ia32/instruction-selector-ia32.cc +++ b/src/compiler/ia32/instruction-selector-ia32.cc @@ -271,6 +271,11 @@ void InstructionSelector::VisitWord32Sar(Node* node) { } +void InstructionSelector::VisitWord32Ror(Node* node) { + VisitShift(this, node, kIA32Ror); +} + + void InstructionSelector::VisitInt32Add(Node* node) { VisitBinop(this, node, kIA32Add); } diff --git a/src/compiler/instruction-selector.cc b/src/compiler/instruction-selector.cc index 541e0452f..35a7e5c3b 100644 --- a/src/compiler/instruction-selector.cc +++ b/src/compiler/instruction-selector.cc @@ -511,6 +511,8 @@ void InstructionSelector::VisitNode(Node* node) { return VisitWord32Shr(node); case IrOpcode::kWord32Sar: return VisitWord32Sar(node); + case IrOpcode::kWord32Ror: + return VisitWord32Ror(node); case IrOpcode::kWord32Equal: return VisitWord32Equal(node); case IrOpcode::kWord64And: @@ -525,6 +527,8 @@ void InstructionSelector::VisitNode(Node* node) { return VisitWord64Shr(node); case IrOpcode::kWord64Sar: return VisitWord64Sar(node); + case IrOpcode::kWord64Ror: + return VisitWord64Ror(node); case IrOpcode::kWord64Equal: return VisitWord64Equal(node); case IrOpcode::kInt32Add: @@ -724,6 +728,9 @@ void InstructionSelector::VisitWord64Shr(Node* node) { UNIMPLEMENTED(); } void InstructionSelector::VisitWord64Sar(Node* node) { UNIMPLEMENTED(); } +void InstructionSelector::VisitWord64Ror(Node* node) { UNIMPLEMENTED(); } + + void InstructionSelector::VisitInt64Add(Node* node) { UNIMPLEMENTED(); } diff --git a/src/compiler/machine-node-factory.h b/src/compiler/machine-node-factory.h index 721b1ff75..cc9d5d903 100644 --- a/src/compiler/machine-node-factory.h +++ b/src/compiler/machine-node-factory.h @@ -119,11 +119,7 @@ class MachineNodeFactory { return NEW_NODE_2(MACHINE()->WordSar(), a, b); } Node* WordRor(Node* a, Node* b) { - if (MACHINE()->is32()) { - return Word32Ror(a, b); - } else { - return Word64Ror(a, b); - } + return NEW_NODE_2(MACHINE()->WordRor(), a, b); } Node* WordEqual(Node* a, Node* b) { return NEW_NODE_2(MACHINE()->WordEqual(), a, b); @@ -165,8 +161,7 @@ class MachineNodeFactory { return NEW_NODE_2(MACHINE()->Word32Sar(), a, b); } Node* Word32Ror(Node* a, Node* b) { - return Word32Or(Word32Shl(a, Int32Sub(Int32Constant(32), b)), - Word32Shr(a, b)); + return NEW_NODE_2(MACHINE()->Word32Ror(), a, b); } Node* Word32Equal(Node* a, Node* b) { return NEW_NODE_2(MACHINE()->Word32Equal(), a, b); @@ -196,8 +191,7 @@ class MachineNodeFactory { return NEW_NODE_2(MACHINE()->Word64Sar(), a, b); } Node* Word64Ror(Node* a, Node* b) { - return Word64Or(Word64Shl(a, Int64Sub(Int64Constant(64), b)), - Word64Shr(a, b)); + return NEW_NODE_2(MACHINE()->Word64Ror(), a, b); } Node* Word64Equal(Node* a, Node* b) { return NEW_NODE_2(MACHINE()->Word64Equal(), a, b); diff --git a/src/compiler/machine-operator-reducer.cc b/src/compiler/machine-operator-reducer.cc index 4a4057646..8466cbbf4 100644 --- a/src/compiler/machine-operator-reducer.cc +++ b/src/compiler/machine-operator-reducer.cc @@ -4,6 +4,7 @@ #include "src/compiler/machine-operator-reducer.h" +#include "src/base/bits.h" #include "src/compiler/common-node-cache.h" #include "src/compiler/generic-node-inl.h" #include "src/compiler/graph.h" @@ -67,6 +68,56 @@ Reduction MachineOperatorReducer::Reduce(Node* node) { return ReplaceInt32(m.left().Value() | m.right().Value()); } if (m.LeftEqualsRight()) return Replace(m.left().node()); // x | x => x + if (m.left().IsWord32Shl() && m.right().IsWord32Shr()) { + Int32BinopMatcher mleft(m.left().node()); + Int32BinopMatcher mright(m.right().node()); + if (mleft.left().node() == mright.left().node()) { + // (x << y) | (x >> (32 - y)) => x ror y + if (mright.right().IsInt32Sub()) { + Int32BinopMatcher mrightright(mright.right().node()); + if (mrightright.left().Is(32) && + mrightright.right().node() == mleft.right().node()) { + graph_->ChangeOperator(node, machine_.Word32Ror()); + node->ReplaceInput(0, mleft.left().node()); + node->ReplaceInput(1, mleft.right().node()); + return Changed(node); + } + } + // (x << K) | (x >> (32 - K)) => x ror K + if (mleft.right().IsInRange(0, 31) && + mright.right().Is(32 - mleft.right().Value())) { + graph_->ChangeOperator(node, machine_.Word32Ror()); + node->ReplaceInput(0, mleft.left().node()); + node->ReplaceInput(1, mleft.right().node()); + return Changed(node); + } + } + } + if (m.left().IsWord32Shr() && m.right().IsWord32Shl()) { + // (x >> (32 - y)) | (x << y) => x ror y + Int32BinopMatcher mleft(m.left().node()); + Int32BinopMatcher mright(m.right().node()); + if (mleft.left().node() == mright.left().node()) { + if (mleft.right().IsInt32Sub()) { + Int32BinopMatcher mleftright(mleft.right().node()); + if (mleftright.left().Is(32) && + mleftright.right().node() == mright.right().node()) { + graph_->ChangeOperator(node, machine_.Word32Ror()); + node->ReplaceInput(0, mright.left().node()); + node->ReplaceInput(1, mright.right().node()); + return Changed(node); + } + } + // (x >> (32 - K)) | (x << K) => x ror K + if (mright.right().IsInRange(0, 31) && + mleft.right().Is(32 - mright.right().Value())) { + graph_->ChangeOperator(node, machine_.Word32Ror()); + node->ReplaceInput(0, mright.left().node()); + node->ReplaceInput(1, mright.right().node()); + return Changed(node); + } + } + } break; } case IrOpcode::kWord32Xor: { @@ -102,6 +153,15 @@ Reduction MachineOperatorReducer::Reduce(Node* node) { } break; } + case IrOpcode::kWord32Ror: { + Int32BinopMatcher m(node); + if (m.right().Is(0)) return Replace(m.left().node()); // x ror 0 => x + if (m.IsFoldable()) { // K ror K => K + return ReplaceInt32( + base::bits::RotateRight32(m.left().Value(), m.right().Value())); + } + break; + } case IrOpcode::kWord32Equal: { Int32BinopMatcher m(node); if (m.IsFoldable()) { // K == K => K diff --git a/src/compiler/machine-operator.h b/src/compiler/machine-operator.h index 93ccedc2c..25bbf2955 100644 --- a/src/compiler/machine-operator.h +++ b/src/compiler/machine-operator.h @@ -76,6 +76,7 @@ class MachineOperatorBuilder { Operator* WordShl() { WORD_SIZE(Shl); } Operator* WordShr() { WORD_SIZE(Shr); } Operator* WordSar() { WORD_SIZE(Sar); } + Operator* WordRor() { WORD_SIZE(Ror); } Operator* WordEqual() { WORD_SIZE(Equal); } Operator* Word32And() { BINOP_AC(Word32And); } @@ -84,6 +85,7 @@ class MachineOperatorBuilder { Operator* Word32Shl() { BINOP(Word32Shl); } Operator* Word32Shr() { BINOP(Word32Shr); } Operator* Word32Sar() { BINOP(Word32Sar); } + Operator* Word32Ror() { BINOP(Word32Ror); } Operator* Word32Equal() { BINOP_C(Word32Equal); } Operator* Word64And() { BINOP_AC(Word64And); } @@ -92,6 +94,7 @@ class MachineOperatorBuilder { Operator* Word64Shl() { BINOP(Word64Shl); } Operator* Word64Shr() { BINOP(Word64Shr); } Operator* Word64Sar() { BINOP(Word64Sar); } + Operator* Word64Ror() { BINOP(Word64Ror); } Operator* Word64Equal() { BINOP_C(Word64Equal); } Operator* Int32Add() { BINOP_AC(Int32Add); } diff --git a/src/compiler/opcodes.h b/src/compiler/opcodes.h index 1371bfd16..df150592f 100644 --- a/src/compiler/opcodes.h +++ b/src/compiler/opcodes.h @@ -165,6 +165,7 @@ V(Word32Shl) \ V(Word32Shr) \ V(Word32Sar) \ + V(Word32Ror) \ V(Word32Equal) \ V(Word64And) \ V(Word64Or) \ @@ -172,6 +173,7 @@ V(Word64Shl) \ V(Word64Shr) \ V(Word64Sar) \ + V(Word64Ror) \ V(Word64Equal) \ V(Int32Add) \ V(Int32AddWithOverflow) \ diff --git a/src/compiler/x64/code-generator-x64.cc b/src/compiler/x64/code-generator-x64.cc index f407fa538..c501b5cd2 100644 --- a/src/compiler/x64/code-generator-x64.cc +++ b/src/compiler/x64/code-generator-x64.cc @@ -370,6 +370,12 @@ void CodeGenerator::AssembleArchInstruction(Instruction* instr) { case kX64Sar: ASSEMBLE_SHIFT(sarq, 6); break; + case kX64Ror32: + ASSEMBLE_SHIFT(rorl, 5); + break; + case kX64Ror: + ASSEMBLE_SHIFT(rorq, 6); + break; case kX64Push: { RegisterOrOperand input = i.InputRegisterOrOperand(0); if (input.type == kRegister) { diff --git a/src/compiler/x64/instruction-codes-x64.h b/src/compiler/x64/instruction-codes-x64.h index 8ba33ab10..10d9ad0dc 100644 --- a/src/compiler/x64/instruction-codes-x64.h +++ b/src/compiler/x64/instruction-codes-x64.h @@ -42,6 +42,8 @@ namespace compiler { V(X64Shr32) \ V(X64Sar) \ V(X64Sar32) \ + V(X64Ror) \ + V(X64Ror32) \ V(X64Push) \ V(X64PushI) \ V(X64CallCodeObject) \ diff --git a/src/compiler/x64/instruction-selector-x64.cc b/src/compiler/x64/instruction-selector-x64.cc index 965e612e2..5f185b13d 100644 --- a/src/compiler/x64/instruction-selector-x64.cc +++ b/src/compiler/x64/instruction-selector-x64.cc @@ -348,6 +348,16 @@ void InstructionSelector::VisitWord64Sar(Node* node) { } +void InstructionSelector::VisitWord32Ror(Node* node) { + VisitWord32Shift(this, node, kX64Ror32); +} + + +void InstructionSelector::VisitWord64Ror(Node* node) { + VisitWord64Shift(this, node, kX64Ror); +} + + void InstructionSelector::VisitInt32Add(Node* node) { VisitBinop(this, node, kX64Add32); } diff --git a/test/base-unittests/DEPS b/test/base-unittests/DEPS index 90b080063..5c0cadf9f 100644 --- a/test/base-unittests/DEPS +++ b/test/base-unittests/DEPS @@ -5,4 +5,5 @@ include_rules = [ "-src", "+src/base", "+testing/gtest", + "+testing/gtest-support.h", ] diff --git a/test/base-unittests/base-unittests.gyp b/test/base-unittests/base-unittests.gyp index 339269db1..2a2321f64 100644 --- a/test/base-unittests/base-unittests.gyp +++ b/test/base-unittests/base-unittests.gyp @@ -20,6 +20,7 @@ '../..', ], 'sources': [ ### gcmole(all) ### + 'bits-unittest.cc', 'cpu-unittest.cc', 'platform/condition-variable-unittest.cc', 'platform/mutex-unittest.cc', diff --git a/test/base-unittests/bits-unittest.cc b/test/base-unittests/bits-unittest.cc new file mode 100644 index 000000000..689fb41da --- /dev/null +++ b/test/base-unittests/bits-unittest.cc @@ -0,0 +1,34 @@ +// 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. + +#include "src/base/bits.h" +#include "src/base/macros.h" +#include "testing/gtest-support.h" + +namespace v8 { +namespace base { +namespace bits { + +TEST(BitsTest, RotateRight32) { + TRACED_FORRANGE(uint32_t, shift, 0, 31) { + EXPECT_EQ(0u, RotateRight32(0u, shift)); + } + EXPECT_EQ(1u, RotateRight32(1, 0)); + EXPECT_EQ(1u, RotateRight32(2, 1)); + EXPECT_EQ(0x80000000u, RotateRight32(1, 1)); +} + + +TEST(BitsTest, RotateRight64) { + TRACED_FORRANGE(uint64_t, shift, 0, 63) { + EXPECT_EQ(0u, RotateRight64(0u, shift)); + } + EXPECT_EQ(1u, RotateRight64(1, 0)); + EXPECT_EQ(1u, RotateRight64(2, 1)); + EXPECT_EQ(V8_UINT64_C(0x8000000000000000), RotateRight64(1, 1)); +} + +} // namespace bits +} // namespace base +} // namespace v8 diff --git a/test/cctest/compiler/test-run-machops.cc b/test/cctest/compiler/test-run-machops.cc index edac97504..fdda63a1c 100644 --- a/test/cctest/compiler/test-run-machops.cc +++ b/test/cctest/compiler/test-run-machops.cc @@ -5,12 +5,14 @@ #include #include +#include "src/base/bits.h" #include "test/cctest/cctest.h" #include "test/cctest/compiler/codegen-tester.h" #include "test/cctest/compiler/value-helper.h" #if V8_TURBOFAN_TARGET +using namespace v8::base; using namespace v8::internal; using namespace v8::internal::compiler; @@ -2282,6 +2284,31 @@ TEST(RunWord32SarP) { } +TEST(RunWord32RorP) { + { + FOR_UINT32_SHIFTS(shift) { + RawMachineAssemblerTester m(kMachineWord32); + m.Return(m.Word32Ror(m.Parameter(0), m.Int32Constant(shift))); + FOR_UINT32_INPUTS(j) { + int32_t expected = bits::RotateRight32(*j, shift); + CHECK_EQ(expected, m.Call(*j)); + } + } + } + { + RawMachineAssemblerTester m; + Int32BinopTester bt(&m); + bt.AddReturn(m.Word32Ror(bt.param0, bt.param1)); + FOR_UINT32_INPUTS(i) { + FOR_UINT32_SHIFTS(shift) { + int32_t expected = bits::RotateRight32(*i, shift); + CHECK_EQ(expected, bt.call(*i, shift)); + } + } + } +} + + TEST(RunWord32NotP) { RawMachineAssemblerTester m(kMachineWord32); m.Return(m.Word32Not(m.Parameter(0))); @@ -2439,16 +2466,16 @@ TEST(RunDeadInt32Binops) { RawMachineAssemblerTester m; Operator* ops[] = { - m.machine()->Word32And(), m.machine()->Word32Or(), - m.machine()->Word32Xor(), m.machine()->Word32Shl(), - m.machine()->Word32Shr(), m.machine()->Word32Sar(), - m.machine()->Word32Equal(), m.machine()->Int32Add(), - m.machine()->Int32Sub(), m.machine()->Int32Mul(), - m.machine()->Int32Div(), m.machine()->Int32UDiv(), - m.machine()->Int32Mod(), m.machine()->Int32UMod(), - m.machine()->Int32LessThan(), m.machine()->Int32LessThanOrEqual(), - m.machine()->Uint32LessThan(), m.machine()->Uint32LessThanOrEqual(), - NULL}; + m.machine()->Word32And(), m.machine()->Word32Or(), + m.machine()->Word32Xor(), m.machine()->Word32Shl(), + m.machine()->Word32Shr(), m.machine()->Word32Sar(), + m.machine()->Word32Ror(), m.machine()->Word32Equal(), + m.machine()->Int32Add(), m.machine()->Int32Sub(), + m.machine()->Int32Mul(), m.machine()->Int32Div(), + m.machine()->Int32UDiv(), m.machine()->Int32Mod(), + m.machine()->Int32UMod(), m.machine()->Int32LessThan(), + m.machine()->Int32LessThanOrEqual(), m.machine()->Uint32LessThan(), + m.machine()->Uint32LessThanOrEqual(), NULL}; for (int i = 0; ops[i] != NULL; i++) { RawMachineAssemblerTester m(kMachineWord32, kMachineWord32); @@ -3689,53 +3716,6 @@ TEST(RunTestIntPtrArithmetic) { } -static inline uint32_t rotr32(uint32_t i, uint32_t j) { - return (i >> j) | (i << (32 - j)); -} - - -TEST(RunTestInt32RotateRightP) { - { - RawMachineAssemblerTester m; - Int32BinopTester bt(&m); - bt.AddReturn(m.Word32Or( - m.Word32Shr(bt.param0, bt.param1), - m.Word32Shl(bt.param0, m.Int32Sub(m.Int32Constant(32), bt.param1)))); - bt.Run(ValueHelper::uint32_vector(), ValueHelper::ror_vector(), rotr32); - } - { - RawMachineAssemblerTester m; - Int32BinopTester bt(&m); - bt.AddReturn(m.Word32Or( - m.Word32Shl(bt.param0, m.Int32Sub(m.Int32Constant(32), bt.param1)), - m.Word32Shr(bt.param0, bt.param1))); - bt.Run(ValueHelper::uint32_vector(), ValueHelper::ror_vector(), rotr32); - } -} - - -TEST(RunTestInt32RotateRightImm) { - FOR_INPUTS(uint32_t, ror, i) { - { - RawMachineAssemblerTester m(kMachineWord32); - Node* value = m.Parameter(0); - m.Return(m.Word32Or(m.Word32Shr(value, m.Int32Constant(*i)), - m.Word32Shl(value, m.Int32Constant(32 - *i)))); - m.Run(ValueHelper::uint32_vector(), - std::bind2nd(std::ptr_fun(&rotr32), *i)); - } - { - RawMachineAssemblerTester m(kMachineWord32); - Node* value = m.Parameter(0); - m.Return(m.Word32Or(m.Word32Shl(value, m.Int32Constant(32 - *i)), - m.Word32Shr(value, m.Int32Constant(*i)))); - m.Run(ValueHelper::uint32_vector(), - std::bind2nd(std::ptr_fun(&rotr32), *i)); - } - } -} - - TEST(RunSpillLotsOfThings) { static const int kInputSize = 1000; RawMachineAssemblerTester m; diff --git a/test/compiler-unittests/compiler-unittests.gyp b/test/compiler-unittests/compiler-unittests.gyp index f257e5451..f2c4facfd 100644 --- a/test/compiler-unittests/compiler-unittests.gyp +++ b/test/compiler-unittests/compiler-unittests.gyp @@ -23,6 +23,7 @@ 'change-lowering-unittest.cc', 'compiler-unittests.cc', 'instruction-selector-unittest.cc', + 'machine-operator-reducer-unittest.cc', 'node-matchers.cc', 'node-matchers.h', ], diff --git a/test/compiler-unittests/machine-operator-reducer-unittest.cc b/test/compiler-unittests/machine-operator-reducer-unittest.cc new file mode 100644 index 000000000..0edab127f --- /dev/null +++ b/test/compiler-unittests/machine-operator-reducer-unittest.cc @@ -0,0 +1,139 @@ +// 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. + +#include "src/base/bits.h" +#include "src/compiler/common-operator.h" +#include "src/compiler/graph.h" +#include "src/compiler/machine-operator-reducer.h" +#include "test/compiler-unittests/compiler-unittests.h" +#include "test/compiler-unittests/node-matchers.h" + +namespace v8 { +namespace internal { +namespace compiler { + +class MachineOperatorReducerTest : public CompilerTest { + public: + explicit MachineOperatorReducerTest(int num_parameters = 2) + : graph_(zone()), common_(zone()), machine_(zone()) { + graph()->SetStart(graph()->NewNode(common()->Start(num_parameters))); + } + virtual ~MachineOperatorReducerTest() {} + + protected: + Node* Parameter(int32_t index) { + return graph()->NewNode(common()->Parameter(index), graph()->start()); + } + Node* Int32Constant(int32_t value) { + return graph()->NewNode(common()->Int32Constant(value)); + } + + Reduction Reduce(Node* node) { + MachineOperatorReducer reducer(graph()); + return reducer.Reduce(node); + } + + Graph* graph() { return &graph_; } + CommonOperatorBuilder* common() { return &common_; } + MachineOperatorBuilder* machine() { return &machine_; } + + private: + Graph graph_; + CommonOperatorBuilder common_; + MachineOperatorBuilder machine_; +}; + + +namespace { + +static const uint32_t kConstants[] = { + 0x00000000, 0x00000001, 0xffffffff, 0x1b09788b, 0x04c5fce8, 0xcc0de5bf, + 0x273a798e, 0x187937a3, 0xece3af83, 0x5495a16b, 0x0b668ecc, 0x11223344, + 0x0000009e, 0x00000043, 0x0000af73, 0x0000116b, 0x00658ecc, 0x002b3b4c, + 0x88776655, 0x70000000, 0x07200000, 0x7fffffff, 0x56123761, 0x7fffff00, + 0x761c4761, 0x80000000, 0x88888888, 0xa0000000, 0xdddddddd, 0xe0000000, + 0xeeeeeeee, 0xfffffffd, 0xf0000000, 0x007fffff, 0x003fffff, 0x001fffff, + 0x000fffff, 0x0007ffff, 0x0003ffff, 0x0001ffff, 0x0000ffff, 0x00007fff, + 0x00003fff, 0x00001fff, 0x00000fff, 0x000007ff, 0x000003ff, 0x000001ff}; + +} // namespace + + +TEST_F(MachineOperatorReducerTest, ReduceToWord32RorWithParameters) { + Node* value = Parameter(0); + Node* shift = Parameter(1); + Node* shl = graph()->NewNode(machine()->Word32Shl(), value, shift); + Node* shr = graph()->NewNode( + machine()->Word32Shr(), value, + graph()->NewNode(machine()->Int32Sub(), Int32Constant(32), shift)); + + // (x << y) | (x >> (32 - y)) => x ror y + Node* node1 = graph()->NewNode(machine()->Word32Or(), shl, shr); + Reduction reduction1 = Reduce(node1); + EXPECT_TRUE(reduction1.Changed()); + EXPECT_EQ(reduction1.replacement(), node1); + EXPECT_THAT(reduction1.replacement(), IsWord32Ror(value, shift)); + + // (x >> (32 - y)) | (x << y) => x ror y + Node* node2 = graph()->NewNode(machine()->Word32Or(), shr, shl); + Reduction reduction2 = Reduce(node2); + EXPECT_TRUE(reduction2.Changed()); + EXPECT_EQ(reduction2.replacement(), node2); + EXPECT_THAT(reduction2.replacement(), IsWord32Ror(value, shift)); +} + + +TEST_F(MachineOperatorReducerTest, ReduceToWord32RorWithConstant) { + Node* value = Parameter(0); + TRACED_FORRANGE(int32_t, k, 0, 31) { + Node* shl = + graph()->NewNode(machine()->Word32Shl(), value, Int32Constant(k)); + Node* shr = + graph()->NewNode(machine()->Word32Shr(), value, Int32Constant(32 - k)); + + // (x << K) | (x >> ((32 - K) - y)) => x ror K + Node* node1 = graph()->NewNode(machine()->Word32Or(), shl, shr); + Reduction reduction1 = Reduce(node1); + EXPECT_TRUE(reduction1.Changed()); + EXPECT_EQ(reduction1.replacement(), node1); + EXPECT_THAT(reduction1.replacement(), + IsWord32Ror(value, IsInt32Constant(k))); + + // (x >> (32 - K)) | (x << K) => x ror K + Node* node2 = graph()->NewNode(machine()->Word32Or(), shr, shl); + Reduction reduction2 = Reduce(node2); + EXPECT_TRUE(reduction2.Changed()); + EXPECT_EQ(reduction2.replacement(), node2); + EXPECT_THAT(reduction2.replacement(), + IsWord32Ror(value, IsInt32Constant(k))); + } +} + + +TEST_F(MachineOperatorReducerTest, Word32RorWithZeroShift) { + Node* value = Parameter(0); + Node* node = + graph()->NewNode(machine()->Word32Ror(), value, Int32Constant(0)); + Reduction reduction = Reduce(node); + EXPECT_TRUE(reduction.Changed()); + EXPECT_EQ(reduction.replacement(), value); +} + + +TEST_F(MachineOperatorReducerTest, Word32RorWithConstants) { + TRACED_FOREACH(int32_t, x, kConstants) { + TRACED_FORRANGE(int32_t, y, 0, 31) { + Node* node = graph()->NewNode(machine()->Word32Ror(), Int32Constant(x), + Int32Constant(y)); + Reduction reduction = Reduce(node); + EXPECT_TRUE(reduction.Changed()); + EXPECT_THAT(reduction.replacement(), + IsInt32Constant(base::bits::RotateRight32(x, y))); + } + } +} + +} // namespace compiler +} // namespace internal +} // namespace v8 diff --git a/test/compiler-unittests/node-matchers.cc b/test/compiler-unittests/node-matchers.cc index d58083411..5d8fba99b 100644 --- a/test/compiler-unittests/node-matchers.cc +++ b/test/compiler-unittests/node-matchers.cc @@ -432,6 +432,7 @@ Matcher IsStore(const Matcher& type_matcher, } IS_BINOP_MATCHER(Word32And) IS_BINOP_MATCHER(Word32Sar) +IS_BINOP_MATCHER(Word32Ror) IS_BINOP_MATCHER(Word32Equal) IS_BINOP_MATCHER(Word64And) IS_BINOP_MATCHER(Word64Sar) diff --git a/test/compiler-unittests/node-matchers.h b/test/compiler-unittests/node-matchers.h index 09da07a7f..f51e3af52 100644 --- a/test/compiler-unittests/node-matchers.h +++ b/test/compiler-unittests/node-matchers.h @@ -49,6 +49,8 @@ Matcher IsWord32And(const Matcher& lhs_matcher, const Matcher& rhs_matcher); Matcher IsWord32Sar(const Matcher& lhs_matcher, const Matcher& rhs_matcher); +Matcher IsWord32Ror(const Matcher& lhs_matcher, + const Matcher& rhs_matcher); Matcher IsWord32Equal(const Matcher& lhs_matcher, const Matcher& rhs_matcher); Matcher IsWord64And(const Matcher& lhs_matcher, diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index d90772523..492aee830 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -1085,6 +1085,7 @@ '../../src/base/atomicops_internals_x86_gcc.cc', '../../src/base/atomicops_internals_x86_gcc.h', '../../src/base/atomicops_internals_x86_msvc.h', + '../../src/base/bits.h', '../../src/base/build_config.h', '../../src/base/cpu.cc', '../../src/base/cpu.h', -- 2.34.1