Line data Source code
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/node.h"
9 : #include "src/compiler/operator.h"
10 : #include "src/compiler/value-numbering-reducer.h"
11 : #include "test/unittests/test-utils.h"
12 :
13 : namespace v8 {
14 : namespace internal {
15 : namespace compiler {
16 : namespace value_numbering_reducer_unittest {
17 :
18 12199 : struct TestOperator : public Operator {
19 6158 : TestOperator(Operator::Opcode opcode, Operator::Properties properties,
20 : size_t value_in, size_t value_out)
21 : : Operator(opcode, properties, "TestOp", value_in, 0, 0, value_out, 0,
22 6158 : 0) {}
23 : };
24 :
25 :
26 3037 : static const TestOperator kOp0(0, Operator::kIdempotent, 0, 1);
27 3037 : static const TestOperator kOp1(1, Operator::kIdempotent, 1, 1);
28 :
29 :
30 6 : class ValueNumberingReducerTest : public TestWithZone {
31 : public:
32 6 : ValueNumberingReducerTest()
33 6 : : graph_(zone()), reducer_(zone(), graph()->zone()) {}
34 :
35 : protected:
36 93 : Reduction Reduce(Node* node) { return reducer_.Reduce(node); }
37 :
38 : Graph* graph() { return &graph_; }
39 :
40 : private:
41 : Graph graph_;
42 : ValueNumberingReducer reducer_;
43 : };
44 :
45 :
46 15189 : TEST_F(ValueNumberingReducerTest, AllInputsAreChecked) {
47 1 : Node* na = graph()->NewNode(&kOp0);
48 : Node* nb = graph()->NewNode(&kOp0);
49 : Node* n1 = graph()->NewNode(&kOp1, na);
50 : Node* n2 = graph()->NewNode(&kOp1, nb);
51 2 : EXPECT_FALSE(Reduce(n1).Changed());
52 2 : EXPECT_FALSE(Reduce(n2).Changed());
53 1 : }
54 :
55 :
56 15189 : TEST_F(ValueNumberingReducerTest, DeadNodesAreNeverReturned) {
57 1 : Node* n0 = graph()->NewNode(&kOp0);
58 : Node* n1 = graph()->NewNode(&kOp1, n0);
59 2 : EXPECT_FALSE(Reduce(n1).Changed());
60 1 : n1->Kill();
61 2 : EXPECT_FALSE(Reduce(graph()->NewNode(&kOp1, n0)).Changed());
62 1 : }
63 :
64 :
65 15189 : TEST_F(ValueNumberingReducerTest, OnlyEliminatableNodesAreReduced) {
66 1 : TestOperator op(0, Operator::kNoProperties, 0, 1);
67 1 : Node* n0 = graph()->NewNode(&op);
68 : Node* n1 = graph()->NewNode(&op);
69 2 : EXPECT_FALSE(Reduce(n0).Changed());
70 2 : EXPECT_FALSE(Reduce(n1).Changed());
71 1 : }
72 :
73 :
74 15189 : TEST_F(ValueNumberingReducerTest, OperatorEqualityNotIdentity) {
75 : static const size_t kMaxInputCount = 16;
76 : Node* inputs[kMaxInputCount];
77 17 : for (size_t i = 0; i < arraysize(inputs); ++i) {
78 16 : Operator::Opcode opcode = static_cast<Operator::Opcode>(kMaxInputCount + i);
79 : inputs[i] = graph()->NewNode(
80 48 : new (zone()) TestOperator(opcode, Operator::kIdempotent, 0, 1));
81 : }
82 119 : TRACED_FORRANGE(size_t, input_count, 0, arraysize(inputs)) {
83 : const TestOperator op1(static_cast<Operator::Opcode>(input_count),
84 17 : Operator::kIdempotent, input_count, 1);
85 17 : Node* n1 = graph()->NewNode(&op1, static_cast<int>(input_count), inputs);
86 : Reduction r1 = Reduce(n1);
87 34 : EXPECT_FALSE(r1.Changed());
88 :
89 : const TestOperator op2(static_cast<Operator::Opcode>(input_count),
90 17 : Operator::kIdempotent, input_count, 1);
91 17 : Node* n2 = graph()->NewNode(&op2, static_cast<int>(input_count), inputs);
92 : Reduction r2 = Reduce(n2);
93 17 : EXPECT_TRUE(r2.Changed());
94 34 : EXPECT_EQ(n1, r2.replacement());
95 17 : }
96 1 : }
97 :
98 :
99 15189 : TEST_F(ValueNumberingReducerTest, SubsequentReductionsYieldTheSameNode) {
100 : static const size_t kMaxInputCount = 16;
101 : Node* inputs[kMaxInputCount];
102 17 : for (size_t i = 0; i < arraysize(inputs); ++i) {
103 16 : Operator::Opcode opcode = static_cast<Operator::Opcode>(2 + i);
104 : inputs[i] = graph()->NewNode(
105 48 : new (zone()) TestOperator(opcode, Operator::kIdempotent, 0, 1));
106 : }
107 119 : TRACED_FORRANGE(size_t, input_count, 0, arraysize(inputs)) {
108 17 : const TestOperator op1(1, Operator::kIdempotent, input_count, 1);
109 17 : Node* n = graph()->NewNode(&op1, static_cast<int>(input_count), inputs);
110 : Reduction r = Reduce(n);
111 34 : EXPECT_FALSE(r.Changed());
112 :
113 17 : r = Reduce(graph()->NewNode(&op1, static_cast<int>(input_count), inputs));
114 17 : ASSERT_TRUE(r.Changed());
115 34 : EXPECT_EQ(n, r.replacement());
116 :
117 17 : r = Reduce(graph()->NewNode(&op1, static_cast<int>(input_count), inputs));
118 17 : ASSERT_TRUE(r.Changed());
119 34 : EXPECT_EQ(n, r.replacement());
120 17 : }
121 : }
122 :
123 :
124 15189 : TEST_F(ValueNumberingReducerTest, WontReplaceNodeWithItself) {
125 1 : Node* n = graph()->NewNode(&kOp0);
126 2 : EXPECT_FALSE(Reduce(n).Changed());
127 2 : EXPECT_FALSE(Reduce(n).Changed());
128 1 : }
129 :
130 : } // namespace value_numbering_reducer_unittest
131 : } // namespace compiler
132 : } // namespace internal
133 9111 : } // namespace v8
|