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_.LookupOrInsert(&key, hash, 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 MachineType::AnyTagged(); 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 318