state-values-utils-unittest.cc 6.99 KB
Newer Older
1 2 3 4 5
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/state-values-utils.h"
6
#include "src/utils/bit-vector.h"
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
#include "test/unittests/compiler/graph-unittest.h"
#include "test/unittests/compiler/node-test-utils.h"
#include "test/unittests/test-utils.h"
#include "testing/gmock/include/gmock/gmock.h"

namespace v8 {
namespace internal {
namespace compiler {

class StateValuesIteratorTest : public GraphTest {
 public:
  StateValuesIteratorTest() : GraphTest(3) {}

  Node* StateValuesFromVector(NodeVector* nodes) {
    int count = static_cast<int>(nodes->size());
22 23 24
    return graph()->NewNode(
        common()->StateValues(count, SparseInputMask::Dense()), count,
        count == 0 ? nullptr : &(nodes->front()));
25 26 27 28 29 30 31 32 33 34 35 36
  }
};


TEST_F(StateValuesIteratorTest, SimpleIteration) {
  NodeVector inputs(zone());
  const int count = 10;
  for (int i = 0; i < count; i++) {
    inputs.push_back(Int32Constant(i));
  }
  Node* state_values = StateValuesFromVector(&inputs);
  int i = 0;
37 38
  for (StateValuesAccess::TypedNode node : StateValuesAccess(state_values)) {
    EXPECT_THAT(node.node, IsInt32Constant(i));
39 40 41 42 43 44 45 46 47
    i++;
  }
  EXPECT_EQ(count, i);
}


TEST_F(StateValuesIteratorTest, EmptyIteration) {
  NodeVector inputs(zone());
  Node* state_values = StateValuesFromVector(&inputs);
48
  bool empty = true;
49
  for (auto node : StateValuesAccess(state_values)) {
50
    USE(node);
51
    empty = false;
52
  }
53
  EXPECT_TRUE(empty);
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
}


TEST_F(StateValuesIteratorTest, NestedIteration) {
  NodeVector inputs(zone());
  int count = 0;
  for (int i = 0; i < 8; i++) {
    if (i == 2) {
      // Single nested in index 2.
      NodeVector nested_inputs(zone());
      for (int j = 0; j < 8; j++) {
        nested_inputs.push_back(Int32Constant(count++));
      }
      inputs.push_back(StateValuesFromVector(&nested_inputs));
    } else if (i == 5) {
      // Double nested at index 5.
      NodeVector nested_inputs(zone());
      for (int j = 0; j < 8; j++) {
        if (j == 7) {
          NodeVector doubly_nested_inputs(zone());
          for (int k = 0; k < 2; k++) {
            doubly_nested_inputs.push_back(Int32Constant(count++));
          }
          nested_inputs.push_back(StateValuesFromVector(&doubly_nested_inputs));
        } else {
          nested_inputs.push_back(Int32Constant(count++));
        }
      }
      inputs.push_back(StateValuesFromVector(&nested_inputs));
    } else {
      inputs.push_back(Int32Constant(count++));
    }
  }
  Node* state_values = StateValuesFromVector(&inputs);
  int i = 0;
89 90
  for (StateValuesAccess::TypedNode node : StateValuesAccess(state_values)) {
    EXPECT_THAT(node.node, IsInt32Constant(i));
91 92 93 94 95 96 97 98 99 100 101
    i++;
  }
  EXPECT_EQ(count, i);
}


TEST_F(StateValuesIteratorTest, TreeFromVector) {
  int sizes[] = {0, 1, 2, 100, 5000, 30000};
  TRACED_FOREACH(int, count, sizes) {
    JSOperatorBuilder javascript(zone());
    MachineOperatorBuilder machine(zone());
102 103
    JSGraph jsgraph(isolate(), graph(), common(), &javascript, nullptr,
                    &machine);
104 105 106 107 108 109 110 111 112 113

    // Generate the input vector.
    NodeVector inputs(zone());
    for (int i = 0; i < count; i++) {
      inputs.push_back(Int32Constant(i));
    }

    // Build the tree.
    StateValuesCache builder(&jsgraph);
    Node* values_node = builder.GetNodeForValues(
114 115
        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size(),
        nullptr);
116 117 118

    // Check the tree contents with vector.
    int i = 0;
119 120
    for (StateValuesAccess::TypedNode node : StateValuesAccess(values_node)) {
      EXPECT_THAT(node.node, IsInt32Constant(i));
121 122 123 124 125 126
      i++;
    }
    EXPECT_EQ(inputs.size(), static_cast<size_t>(i));
  }
}

127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
TEST_F(StateValuesIteratorTest, TreeFromVectorWithLiveness) {
  int sizes[] = {0, 1, 2, 100, 5000, 30000};
  TRACED_FOREACH(int, count, sizes) {
    JSOperatorBuilder javascript(zone());
    MachineOperatorBuilder machine(zone());
    JSGraph jsgraph(isolate(), graph(), common(), &javascript, nullptr,
                    &machine);

    // Generate the input vector.
    NodeVector inputs(zone());
    for (int i = 0; i < count; i++) {
      inputs.push_back(Int32Constant(i));
    }
    // Generate the input liveness.
    BitVector liveness(count, zone());
    for (int i = 0; i < count; i++) {
      if (i % 3 == 0) {
        liveness.Add(i);
      }
    }

    // Build the tree.
    StateValuesCache builder(&jsgraph);
    Node* values_node = builder.GetNodeForValues(
        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size(),
        &liveness);

    // Check the tree contents with vector.
    int i = 0;
156 157 158
    for (StateValuesAccess::iterator it =
             StateValuesAccess(values_node).begin();
         !it.done(); ++it) {
159
      if (liveness.Contains(i)) {
160
        EXPECT_THAT(it.node(), IsInt32Constant(i));
161
      } else {
162
        EXPECT_EQ(it.node(), nullptr);
163 164 165 166 167 168
      }
      i++;
    }
    EXPECT_EQ(inputs.size(), static_cast<size_t>(i));
  }
}
169 170 171 172 173 174

TEST_F(StateValuesIteratorTest, BuildTreeIdentical) {
  int sizes[] = {0, 1, 2, 100, 5000, 30000};
  TRACED_FOREACH(int, count, sizes) {
    JSOperatorBuilder javascript(zone());
    MachineOperatorBuilder machine(zone());
175 176
    JSGraph jsgraph(isolate(), graph(), common(), &javascript, nullptr,
                    &machine);
177 178 179 180 181 182 183 184 185 186

    // Generate the input vector.
    NodeVector inputs(zone());
    for (int i = 0; i < count; i++) {
      inputs.push_back(Int32Constant(i));
    }

    // Build two trees from the same data.
    StateValuesCache builder(&jsgraph);
    Node* node1 = builder.GetNodeForValues(
187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size(),
        nullptr);
    Node* node2 = builder.GetNodeForValues(
        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size(),
        nullptr);

    // The trees should be equal since the data was the same.
    EXPECT_EQ(node1, node2);
  }
}

TEST_F(StateValuesIteratorTest, BuildTreeWithLivenessIdentical) {
  int sizes[] = {0, 1, 2, 100, 5000, 30000};
  TRACED_FOREACH(int, count, sizes) {
    JSOperatorBuilder javascript(zone());
    MachineOperatorBuilder machine(zone());
    JSGraph jsgraph(isolate(), graph(), common(), &javascript, nullptr,
                    &machine);

    // Generate the input vector.
    NodeVector inputs(zone());
    for (int i = 0; i < count; i++) {
      inputs.push_back(Int32Constant(i));
    }
    // Generate the input liveness.
    BitVector liveness(count, zone());
    for (int i = 0; i < count; i++) {
      if (i % 3 == 0) {
        liveness.Add(i);
      }
    }

    // Build two trees from the same data.
    StateValuesCache builder(&jsgraph);
    Node* node1 = builder.GetNodeForValues(
        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size(),
        &liveness);
224
    Node* node2 = builder.GetNodeForValues(
225 226
        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size(),
        &liveness);
227 228 229 230 231 232 233 234 235

    // The trees should be equal since the data was the same.
    EXPECT_EQ(node1, node2);
  }
}

}  // namespace compiler
}  // namespace internal
}  // namespace v8