Home | History | Annotate | Download | only in compiler 
      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:
     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 
     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 
     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 
     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 
     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 
    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