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