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:
ValueNumberingReducerTest()25 ValueNumberingReducerTest() : graph_(zone()), reducer_(zone()) {}
26
27 protected:
Reduce(Node * node)28 Reduction Reduce(Node* node) { return reducer_.Reduce(node); }
29
graph()30 Graph* graph() { return &graph_; }
31
32 private:
33 Graph graph_;
34 ValueNumberingReducer reducer_;
35 };
36
37
TEST_F(ValueNumberingReducerTest,AllInputsAreChecked)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
TEST_F(ValueNumberingReducerTest,DeadNodesAreNeverReturned)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
TEST_F(ValueNumberingReducerTest,OperatorEqualityNotIdentity)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
TEST_F(ValueNumberingReducerTest,SubsequentReductionsYieldTheSameNode)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
TEST_F(ValueNumberingReducerTest,WontReplaceNodeWithItself)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
121