deps/v8/src/compiler/state-values-utils.cc

   1 // Copyright 2015 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 "src/compiler/state-values-utils.h"
   6
   7 namespace v8 {
   8 namespace internal {
   9 namespace compiler {
  10
  11 StateValuesCache::StateValuesCache(JSGraph* js_graph)
  12     : js_graph_(js_graph),
  13       hash_map_(AreKeysEqual, ZoneHashMap::kDefaultHashMapCapacity,
  14                 ZoneAllocationPolicy(zone())),
  15       working_space_(zone()),
  16       empty_state_values_(nullptr) {}
  17
  18
  19 // static
  20 bool StateValuesCache::AreKeysEqual(void* key1, void* key2) {
  21   NodeKey* node_key1 = reinterpret_cast<NodeKey*>(key1);
  22   NodeKey* node_key2 = reinterpret_cast<NodeKey*>(key2);
  23
  24   if (node_key1->node == nullptr) {
  25     if (node_key2->node == nullptr) {
  26       return AreValueKeysEqual(reinterpret_cast<StateValuesKey*>(key1),
  27                                reinterpret_cast<StateValuesKey*>(key2));
  28     } else {
  29       return IsKeysEqualToNode(reinterpret_cast<StateValuesKey*>(key1),
  30                                node_key2->node);
  31     }
  32   } else {
  33     if (node_key2->node == nullptr) {
  34       // If the nodes are already processed, they must be the same.
  35       return IsKeysEqualToNode(reinterpret_cast<StateValuesKey*>(key2),
  36                                node_key1->node);
  37     } else {
  38       return node_key1->node == node_key2->node;
  39     }
  40   }
  41   UNREACHABLE();
  42 }
  43
  44
  45 // static
  46 bool StateValuesCache::IsKeysEqualToNode(StateValuesKey* key, Node* node) {
  47   if (key->count != static_cast<size_t>(node->InputCount())) {
  48     return false;
  49   }
  50   for (size_t i = 0; i < key->count; i++) {
  51     if (key->values[i] != node->InputAt(static_cast<int>(i))) {
  52       return false;
  53     }
  54   }
  55   return true;
  56 }
  57
  58
  59 // static
  60 bool StateValuesCache::AreValueKeysEqual(StateValuesKey* key1,
  61                                          StateValuesKey* key2) {
  62   if (key1->count != key2->count) {
  63     return false;
  64   }
  65   for (size_t i = 0; i < key1->count; i++) {
  66     if (key1->values[i] != key2->values[i]) {
  67       return false;
  68     }
  69   }
  70   return true;
  71 }
  72
  73
  74 Node* StateValuesCache::GetEmptyStateValues() {
  75   if (empty_state_values_ == nullptr) {
  76     empty_state_values_ = graph()->NewNode(common()->StateValues(0));
  77   }
  78   return empty_state_values_;
  79 }
  80
  81
  82 NodeVector* StateValuesCache::GetWorkingSpace(size_t level) {
  83   while (working_space_.size() <= level) {
  84     void* space = zone()->New(sizeof(NodeVector));
  85     working_space_.push_back(new (space)
  86                                  NodeVector(kMaxInputCount, nullptr, zone()));
  87   }
  88   return working_space_[level];
  89 }
  90
  91 namespace {
  92
  93 int StateValuesHashKey(Node** nodes, size_t count) {
  94   size_t hash = count;
  95   for (size_t i = 0; i < count; i++) {
  96     hash = hash * 23 + nodes[i]->id();
  97   }
  98   return static_cast<int>(hash & 0x7fffffff);
  99 }
 100
 101 }  // namespace
 102
 103
 104 Node* StateValuesCache::GetValuesNodeFromCache(Node** nodes, size_t count) {
 105   StateValuesKey key(count, nodes);
 106   int hash = StateValuesHashKey(nodes, count);
 107   ZoneHashMap::Entry* lookup =
 108       hash_map_.Lookup(&key, hash, true, ZoneAllocationPolicy(zone()));
 109   DCHECK_NOT_NULL(lookup);
 110   Node* node;
 111   if (lookup->value == nullptr) {
 112     int input_count = static_cast<int>(count);
 113     node = graph()->NewNode(common()->StateValues(input_count), input_count,
 114                             nodes);
 115     NodeKey* new_key = new (zone()->New(sizeof(NodeKey))) NodeKey(node);
 116     lookup->key = new_key;
 117     lookup->value = node;
 118   } else {
 119     node = reinterpret_cast<Node*>(lookup->value);
 120   }
 121   return node;
 122 }
 123
 124
 125 class StateValuesCache::ValueArrayIterator {
 126  public:
 127   ValueArrayIterator(Node** values, size_t count)
 128       : values_(values), count_(count), current_(0) {}
 129
 130   void Advance() {
 131     if (!done()) {
 132       current_++;
 133     }
 134   }
 135
 136   bool done() { return current_ >= count_; }
 137
 138   Node* node() {
 139     DCHECK(!done());
 140     return values_[current_];
 141   }
 142
 143  private:
 144   Node** values_;
 145   size_t count_;
 146   size_t current_;
 147 };
 148
 149
 150 Node* StateValuesCache::BuildTree(ValueArrayIterator* it, size_t max_height) {
 151   if (max_height == 0) {
 152     Node* node = it->node();
 153     it->Advance();
 154     return node;
 155   }
 156   DCHECK(!it->done());
 157
 158   NodeVector* buffer = GetWorkingSpace(max_height);
 159   size_t count = 0;
 160   for (; count < kMaxInputCount; count++) {
 161     if (it->done()) break;
 162     (*buffer)[count] = BuildTree(it, max_height - 1);
 163   }
 164   if (count == 1) {
 165     return (*buffer)[0];
 166   } else {
 167     return GetValuesNodeFromCache(&(buffer->front()), count);
 168   }
 169 }
 170
 171
 172 Node* StateValuesCache::GetNodeForValues(Node** values, size_t count) {
 173 #if DEBUG
 174   for (size_t i = 0; i < count; i++) {
 175     DCHECK_NE(values[i]->opcode(), IrOpcode::kStateValues);
 176     DCHECK_NE(values[i]->opcode(), IrOpcode::kTypedStateValues);
 177   }
 178 #endif
 179   if (count == 0) {
 180     return GetEmptyStateValues();
 181   }
 182   size_t height = 0;
 183   size_t max_nodes = 1;
 184   while (count > max_nodes) {
 185     height++;
 186     max_nodes *= kMaxInputCount;
 187   }
 188
 189   ValueArrayIterator it(values, count);
 190
 191   Node* tree = BuildTree(&it, height);
 192
 193   // If the 'tree' is a single node, equip it with a StateValues wrapper.
 194   if (tree->opcode() != IrOpcode::kStateValues &&
 195       tree->opcode() != IrOpcode::kTypedStateValues) {
 196     tree = GetValuesNodeFromCache(&tree, 1);
 197   }
 198
 199   return tree;
 200 }
 201
 202
 203 StateValuesAccess::iterator::iterator(Node* node) : current_depth_(0) {
 204   // A hacky way initialize - just set the index before the node we want
 205   // to process and then advance to it.
 206   stack_[current_depth_].node = node;
 207   stack_[current_depth_].index = -1;
 208   Advance();
 209 }
 210
 211
 212 StateValuesAccess::iterator::StatePos* StateValuesAccess::iterator::Top() {
 213   DCHECK(current_depth_ >= 0);
 214   DCHECK(current_depth_ < kMaxInlineDepth);
 215   return &(stack_[current_depth_]);
 216 }
 217
 218
 219 void StateValuesAccess::iterator::Push(Node* node) {
 220   current_depth_++;
 221   CHECK(current_depth_ < kMaxInlineDepth);
 222   stack_[current_depth_].node = node;
 223   stack_[current_depth_].index = 0;
 224 }
 225
 226
 227 void StateValuesAccess::iterator::Pop() {
 228   DCHECK(current_depth_ >= 0);
 229   current_depth_--;
 230 }
 231
 232
 233 bool StateValuesAccess::iterator::done() { return current_depth_ < 0; }
 234
 235
 236 void StateValuesAccess::iterator::Advance() {
 237   // Advance the current index.
 238   Top()->index++;
 239
 240   // Fix up the position to point to a valid node.
 241   while (true) {
 242     // TODO(jarin): Factor to a separate method.
 243     Node* node = Top()->node;
 244     int index = Top()->index;
 245
 246     if (index >= node->InputCount()) {
 247       // Pop stack and move to the next sibling.
 248       Pop();
 249       if (done()) {
 250         // Stack is exhausted, we have reached the end.
 251         return;
 252       }
 253       Top()->index++;
 254     } else if (node->InputAt(index)->opcode() == IrOpcode::kStateValues ||
 255                node->InputAt(index)->opcode() == IrOpcode::kTypedStateValues) {
 256       // Nested state, we need to push to the stack.
 257       Push(node->InputAt(index));
 258     } else {
 259       // We are on a valid node, we can stop the iteration.
 260       return;
 261     }
 262   }
 263 }
 264
 265
 266 Node* StateValuesAccess::iterator::node() {
 267   return Top()->node->InputAt(Top()->index);
 268 }
 269
 270
 271 MachineType StateValuesAccess::iterator::type() {
 272   Node* state = Top()->node;
 273   if (state->opcode() == IrOpcode::kStateValues) {
 274     return kMachAnyTagged;
 275   } else {
 276     DCHECK_EQ(IrOpcode::kTypedStateValues, state->opcode());
 277     const ZoneVector<MachineType>* types =
 278         OpParameter<const ZoneVector<MachineType>*>(state);
 279     return (*types)[Top()->index];
 280   }
 281 }
 282
 283
 284 bool StateValuesAccess::iterator::operator!=(iterator& other) {
 285   // We only allow comparison with end().
 286   CHECK(other.done());
 287   return !done();
 288 }
 289
 290
 291 StateValuesAccess::iterator& StateValuesAccess::iterator::operator++() {
 292   Advance();
 293   return *this;
 294 }
 295
 296
 297 StateValuesAccess::TypedNode StateValuesAccess::iterator::operator*() {
 298   return TypedNode(node(), type());
 299 }
 300
 301
 302 size_t StateValuesAccess::size() {
 303   size_t count = 0;
 304   for (int i = 0; i < node_->InputCount(); i++) {
 305     if (node_->InputAt(i)->opcode() == IrOpcode::kStateValues ||
 306         node_->InputAt(i)->opcode() == IrOpcode::kTypedStateValues) {
 307       count += StateValuesAccess(node_->InputAt(i)).size();
 308     } else {
 309       count++;
 310     }
 311   }
 312   return count;
 313 }
 314
 315 }  // namespace compiler
 316 }  // namespace internal
 317 }  // namespace v8