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       12438 : struct TestOperator : public Operator {
      19             :   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        6260 :                  0) {}
      23             : };
      24             : 
      25             : 
      26        3088 : static const TestOperator kOp0(0, Operator::kIdempotent, 0, 1);
      27        3088 : static const TestOperator kOp1(1, Operator::kIdempotent, 1, 1);
      28             : 
      29             : 
      30          12 : class ValueNumberingReducerTest : public TestWithZone {
      31             :  public:
      32           6 :   ValueNumberingReducerTest()
      33          12 :       : graph_(zone()), reducer_(zone(), graph()->zone()) {}
      34             : 
      35             :  protected:
      36          93 :   Reduction Reduce(Node* node) { return reducer_.Reduce(node); }
      37             : 
      38          70 :   Graph* graph() { return &graph_; }
      39             : 
      40             :  private:
      41             :   Graph graph_;
      42             :   ValueNumberingReducer reducer_;
      43             : };
      44             : 
      45             : 
      46       15444 : TEST_F(ValueNumberingReducerTest, AllInputsAreChecked) {
      47             :   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       15444 : TEST_F(ValueNumberingReducerTest, DeadNodesAreNeverReturned) {
      57             :   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       15444 : TEST_F(ValueNumberingReducerTest, OnlyEliminatableNodesAreReduced) {
      66             :   TestOperator op(0, Operator::kNoProperties, 0, 1);
      67             :   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       15444 : TEST_F(ValueNumberingReducerTest, OperatorEqualityNotIdentity) {
      75             :   static const size_t kMaxInputCount = 16;
      76             :   Node* inputs[kMaxInputCount];
      77          33 :   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          16 :         new (zone()) TestOperator(opcode, Operator::kIdempotent, 0, 1));
      81             :   }
      82          69 :   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          34 :     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             :                            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             :   }
      96           1 : }
      97             : 
      98             : 
      99       15444 : TEST_F(ValueNumberingReducerTest, SubsequentReductionsYieldTheSameNode) {
     100             :   static const size_t kMaxInputCount = 16;
     101             :   Node* inputs[kMaxInputCount];
     102          33 :   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          16 :         new (zone()) TestOperator(opcode, Operator::kIdempotent, 0, 1));
     106             :   }
     107          86 :   TRACED_FORRANGE(size_t, input_count, 0, arraysize(inputs)) {
     108             :     const TestOperator op1(1, Operator::kIdempotent, input_count, 1);
     109          34 :     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             :   }
     121             : }
     122             : 
     123             : 
     124       15444 : TEST_F(ValueNumberingReducerTest, WontReplaceNodeWithItself) {
     125             :   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        9264 : }  // namespace v8