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
11namespace v8 {
12namespace internal {
13namespace compiler {
14
15namespace {
16
17const SimpleOperator kOp0(0, Operator::kNoProperties, 0, 1, "op0");
18const SimpleOperator kOp1(1, Operator::kNoProperties, 1, 1, "op1");
19
20}  // namespace
21
22
23class 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
38TEST_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
48TEST_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
57TEST_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
85TEST_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
112TEST_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