Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame^] | 1 | // Copyright 2014 the V8 project authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | #include <limits> |
| 6 | |
| 7 | #include "src/compiler/graph.h" |
| 8 | #include "src/compiler/value-numbering-reducer.h" |
| 9 | #include "src/test/test-utils.h" |
| 10 | |
| 11 | namespace v8 { |
| 12 | namespace internal { |
| 13 | namespace compiler { |
| 14 | |
| 15 | namespace { |
| 16 | |
| 17 | const SimpleOperator kOp0(0, Operator::kNoProperties, 0, 1, "op0"); |
| 18 | const SimpleOperator kOp1(1, Operator::kNoProperties, 1, 1, "op1"); |
| 19 | |
| 20 | } // namespace |
| 21 | |
| 22 | |
| 23 | class ValueNumberingReducerTest : public TestWithZone { |
| 24 | public: |
| 25 | ValueNumberingReducerTest() : graph_(zone()), reducer_(zone()) {} |
| 26 | |
| 27 | protected: |
| 28 | Reduction Reduce(Node* node) { return reducer_.Reduce(node); } |
| 29 | |
| 30 | Graph* graph() { return &graph_; } |
| 31 | |
| 32 | private: |
| 33 | Graph graph_; |
| 34 | ValueNumberingReducer reducer_; |
| 35 | }; |
| 36 | |
| 37 | |
| 38 | TEST_F(ValueNumberingReducerTest, AllInputsAreChecked) { |
| 39 | Node* na = graph()->NewNode(&kOp0); |
| 40 | Node* nb = graph()->NewNode(&kOp0); |
| 41 | Node* n1 = graph()->NewNode(&kOp0, na); |
| 42 | Node* n2 = graph()->NewNode(&kOp0, nb); |
| 43 | EXPECT_FALSE(Reduce(n1).Changed()); |
| 44 | EXPECT_FALSE(Reduce(n2).Changed()); |
| 45 | } |
| 46 | |
| 47 | |
| 48 | TEST_F(ValueNumberingReducerTest, DeadNodesAreNeverReturned) { |
| 49 | Node* n0 = graph()->NewNode(&kOp0); |
| 50 | Node* n1 = graph()->NewNode(&kOp1, n0); |
| 51 | EXPECT_FALSE(Reduce(n1).Changed()); |
| 52 | n1->Kill(); |
| 53 | EXPECT_FALSE(Reduce(graph()->NewNode(&kOp1, n0)).Changed()); |
| 54 | } |
| 55 | |
| 56 | |
| 57 | TEST_F(ValueNumberingReducerTest, OperatorEqualityNotIdentity) { |
| 58 | static const size_t kMaxInputCount = 16; |
| 59 | Node* inputs[kMaxInputCount]; |
| 60 | for (size_t i = 0; i < arraysize(inputs); ++i) { |
| 61 | Operator::Opcode opcode = static_cast<Operator::Opcode>( |
| 62 | std::numeric_limits<Operator::Opcode>::max() - i); |
| 63 | inputs[i] = graph()->NewNode(new (zone()) SimpleOperator( |
| 64 | opcode, Operator::kNoProperties, 0, 1, "Operator")); |
| 65 | } |
| 66 | TRACED_FORRANGE(size_t, input_count, 0, arraysize(inputs)) { |
| 67 | const SimpleOperator op1(static_cast<Operator::Opcode>(input_count), |
| 68 | Operator::kNoProperties, |
| 69 | static_cast<int>(input_count), 1, "op"); |
| 70 | Node* n1 = graph()->NewNode(&op1, static_cast<int>(input_count), inputs); |
| 71 | Reduction r1 = Reduce(n1); |
| 72 | EXPECT_FALSE(r1.Changed()); |
| 73 | |
| 74 | const SimpleOperator op2(static_cast<Operator::Opcode>(input_count), |
| 75 | Operator::kNoProperties, |
| 76 | static_cast<int>(input_count), 1, "op"); |
| 77 | Node* n2 = graph()->NewNode(&op2, static_cast<int>(input_count), inputs); |
| 78 | Reduction r2 = Reduce(n2); |
| 79 | EXPECT_TRUE(r2.Changed()); |
| 80 | EXPECT_EQ(n1, r2.replacement()); |
| 81 | } |
| 82 | } |
| 83 | |
| 84 | |
| 85 | TEST_F(ValueNumberingReducerTest, SubsequentReductionsYieldTheSameNode) { |
| 86 | static const size_t kMaxInputCount = 16; |
| 87 | Node* inputs[kMaxInputCount]; |
| 88 | for (size_t i = 0; i < arraysize(inputs); ++i) { |
| 89 | Operator::Opcode opcode = static_cast<Operator::Opcode>( |
| 90 | std::numeric_limits<Operator::Opcode>::max() - i); |
| 91 | inputs[i] = graph()->NewNode(new (zone()) SimpleOperator( |
| 92 | opcode, Operator::kNoProperties, 0, 1, "Operator")); |
| 93 | } |
| 94 | TRACED_FORRANGE(size_t, input_count, 0, arraysize(inputs)) { |
| 95 | const SimpleOperator op1(1, Operator::kNoProperties, |
| 96 | static_cast<int>(input_count), 1, "op1"); |
| 97 | Node* n = graph()->NewNode(&op1, static_cast<int>(input_count), inputs); |
| 98 | Reduction r = Reduce(n); |
| 99 | EXPECT_FALSE(r.Changed()); |
| 100 | |
| 101 | r = Reduce(graph()->NewNode(&op1, static_cast<int>(input_count), inputs)); |
| 102 | ASSERT_TRUE(r.Changed()); |
| 103 | EXPECT_EQ(n, r.replacement()); |
| 104 | |
| 105 | r = Reduce(graph()->NewNode(&op1, static_cast<int>(input_count), inputs)); |
| 106 | ASSERT_TRUE(r.Changed()); |
| 107 | EXPECT_EQ(n, r.replacement()); |
| 108 | } |
| 109 | } |
| 110 | |
| 111 | |
| 112 | TEST_F(ValueNumberingReducerTest, WontReplaceNodeWithItself) { |
| 113 | Node* n = graph()->NewNode(&kOp0); |
| 114 | EXPECT_FALSE(Reduce(n).Changed()); |
| 115 | EXPECT_FALSE(Reduce(n).Changed()); |
| 116 | } |
| 117 | |
| 118 | } // namespace compiler |
| 119 | } // namespace internal |
| 120 | } // namespace v8 |