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/node-properties.h" 6 #include "src/compiler/common-operator.h" 7 #include "src/compiler/graph.h" 8 #include "src/compiler/js-operator.h" 9 #include "src/compiler/linkage.h" 10 #include "src/compiler/node-matchers.h" 11 #include "src/compiler/operator-properties.h" 12 #include "src/compiler/simplified-operator.h" 13 #include "src/compiler/verifier.h" 14 #include "src/handles-inl.h" 15 #include "src/objects-inl.h" 16 17 namespace v8 { 18 namespace internal { 19 namespace compiler { 20 21 // static 22 int NodeProperties::PastValueIndex(Node* node) { 23 return FirstValueIndex(node) + node->op()->ValueInputCount(); 24 } 25 26 27 // static 28 int NodeProperties::PastContextIndex(Node* node) { 29 return FirstContextIndex(node) + 30 OperatorProperties::GetContextInputCount(node->op()); 31 } 32 33 34 // static 35 int NodeProperties::PastFrameStateIndex(Node* node) { 36 return FirstFrameStateIndex(node) + 37 OperatorProperties::GetFrameStateInputCount(node->op()); 38 } 39 40 41 // static 42 int NodeProperties::PastEffectIndex(Node* node) { 43 return FirstEffectIndex(node) + node->op()->EffectInputCount(); 44 } 45 46 47 // static 48 int NodeProperties::PastControlIndex(Node* node) { 49 return FirstControlIndex(node) + node->op()->ControlInputCount(); 50 } 51 52 53 // static 54 Node* NodeProperties::GetValueInput(Node* node, int index) { 55 DCHECK(0 <= index && index < node->op()->ValueInputCount()); 56 return node->InputAt(FirstValueIndex(node) + index); 57 } 58 59 60 // static 61 Node* NodeProperties::GetContextInput(Node* node) { 62 DCHECK(OperatorProperties::HasContextInput(node->op())); 63 return node->InputAt(FirstContextIndex(node)); 64 } 65 66 67 // static 68 Node* NodeProperties::GetFrameStateInput(Node* node) { 69 DCHECK_EQ(1, OperatorProperties::GetFrameStateInputCount(node->op())); 70 return node->InputAt(FirstFrameStateIndex(node)); 71 } 72 73 74 // static 75 Node* NodeProperties::GetEffectInput(Node* node, int index) { 76 DCHECK(0 <= index && index < node->op()->EffectInputCount()); 77 return node->InputAt(FirstEffectIndex(node) + index); 78 } 79 80 81 // static 82 Node* NodeProperties::GetControlInput(Node* node, int index) { 83 DCHECK(0 <= index && index < node->op()->ControlInputCount()); 84 return node->InputAt(FirstControlIndex(node) + index); 85 } 86 87 88 // static 89 bool NodeProperties::IsValueEdge(Edge edge) { 90 Node* const node = edge.from(); 91 return IsInputRange(edge, FirstValueIndex(node), 92 node->op()->ValueInputCount()); 93 } 94 95 96 // static 97 bool NodeProperties::IsContextEdge(Edge edge) { 98 Node* const node = edge.from(); 99 return IsInputRange(edge, FirstContextIndex(node), 100 OperatorProperties::GetContextInputCount(node->op())); 101 } 102 103 104 // static 105 bool NodeProperties::IsFrameStateEdge(Edge edge) { 106 Node* const node = edge.from(); 107 return IsInputRange(edge, FirstFrameStateIndex(node), 108 OperatorProperties::GetFrameStateInputCount(node->op())); 109 } 110 111 112 // static 113 bool NodeProperties::IsEffectEdge(Edge edge) { 114 Node* const node = edge.from(); 115 return IsInputRange(edge, FirstEffectIndex(node), 116 node->op()->EffectInputCount()); 117 } 118 119 120 // static 121 bool NodeProperties::IsControlEdge(Edge edge) { 122 Node* const node = edge.from(); 123 return IsInputRange(edge, FirstControlIndex(node), 124 node->op()->ControlInputCount()); 125 } 126 127 128 // static 129 bool NodeProperties::IsExceptionalCall(Node* node) { 130 if (node->op()->HasProperty(Operator::kNoThrow)) return false; 131 for (Edge const edge : node->use_edges()) { 132 if (!NodeProperties::IsControlEdge(edge)) continue; 133 if (edge.from()->opcode() == IrOpcode::kIfException) return true; 134 } 135 return false; 136 } 137 138 139 // static 140 void NodeProperties::ReplaceValueInput(Node* node, Node* value, int index) { 141 DCHECK(index < node->op()->ValueInputCount()); 142 node->ReplaceInput(FirstValueIndex(node) + index, value); 143 } 144 145 146 // static 147 void NodeProperties::ReplaceValueInputs(Node* node, Node* value) { 148 int value_input_count = node->op()->ValueInputCount(); 149 DCHECK_LE(1, value_input_count); 150 node->ReplaceInput(0, value); 151 while (--value_input_count > 0) { 152 node->RemoveInput(value_input_count); 153 } 154 } 155 156 157 // static 158 void NodeProperties::ReplaceContextInput(Node* node, Node* context) { 159 node->ReplaceInput(FirstContextIndex(node), context); 160 } 161 162 163 // static 164 void NodeProperties::ReplaceControlInput(Node* node, Node* control, int index) { 165 DCHECK(index < node->op()->ControlInputCount()); 166 node->ReplaceInput(FirstControlIndex(node) + index, control); 167 } 168 169 170 // static 171 void NodeProperties::ReplaceEffectInput(Node* node, Node* effect, int index) { 172 DCHECK(index < node->op()->EffectInputCount()); 173 return node->ReplaceInput(FirstEffectIndex(node) + index, effect); 174 } 175 176 177 // static 178 void NodeProperties::ReplaceFrameStateInput(Node* node, Node* frame_state) { 179 DCHECK_EQ(1, OperatorProperties::GetFrameStateInputCount(node->op())); 180 node->ReplaceInput(FirstFrameStateIndex(node), frame_state); 181 } 182 183 184 // static 185 void NodeProperties::RemoveNonValueInputs(Node* node) { 186 node->TrimInputCount(node->op()->ValueInputCount()); 187 } 188 189 190 // static 191 void NodeProperties::RemoveValueInputs(Node* node) { 192 int value_input_count = node->op()->ValueInputCount(); 193 while (--value_input_count >= 0) { 194 node->RemoveInput(value_input_count); 195 } 196 } 197 198 199 void NodeProperties::MergeControlToEnd(Graph* graph, 200 CommonOperatorBuilder* common, 201 Node* node) { 202 graph->end()->AppendInput(graph->zone(), node); 203 graph->end()->set_op(common->End(graph->end()->InputCount())); 204 } 205 206 207 // static 208 void NodeProperties::ReplaceUses(Node* node, Node* value, Node* effect, 209 Node* success, Node* exception) { 210 // Requires distinguishing between value, effect and control edges. 211 for (Edge edge : node->use_edges()) { 212 if (IsControlEdge(edge)) { 213 if (edge.from()->opcode() == IrOpcode::kIfSuccess) { 214 DCHECK_NOT_NULL(success); 215 edge.UpdateTo(success); 216 } else if (edge.from()->opcode() == IrOpcode::kIfException) { 217 DCHECK_NOT_NULL(exception); 218 edge.UpdateTo(exception); 219 } else { 220 DCHECK_NOT_NULL(success); 221 edge.UpdateTo(success); 222 } 223 } else if (IsEffectEdge(edge)) { 224 DCHECK_NOT_NULL(effect); 225 edge.UpdateTo(effect); 226 } else { 227 DCHECK_NOT_NULL(value); 228 edge.UpdateTo(value); 229 } 230 } 231 } 232 233 234 // static 235 void NodeProperties::ChangeOp(Node* node, const Operator* new_op) { 236 node->set_op(new_op); 237 Verifier::VerifyNode(node); 238 } 239 240 241 // static 242 Node* NodeProperties::FindFrameStateBefore(Node* node) { 243 Node* effect = NodeProperties::GetEffectInput(node); 244 while (effect->opcode() != IrOpcode::kCheckpoint) { 245 if (effect->opcode() == IrOpcode::kDead) return effect; 246 DCHECK_EQ(1, effect->op()->EffectInputCount()); 247 effect = NodeProperties::GetEffectInput(effect); 248 } 249 Node* frame_state = GetFrameStateInput(effect); 250 return frame_state; 251 } 252 253 // static 254 Node* NodeProperties::FindProjection(Node* node, size_t projection_index) { 255 for (auto use : node->uses()) { 256 if (use->opcode() == IrOpcode::kProjection && 257 ProjectionIndexOf(use->op()) == projection_index) { 258 return use; 259 } 260 } 261 return nullptr; 262 } 263 264 265 // static 266 void NodeProperties::CollectControlProjections(Node* node, Node** projections, 267 size_t projection_count) { 268 #ifdef DEBUG 269 DCHECK_LE(static_cast<int>(projection_count), node->UseCount()); 270 std::memset(projections, 0, sizeof(*projections) * projection_count); 271 #endif 272 size_t if_value_index = 0; 273 for (Edge const edge : node->use_edges()) { 274 if (!IsControlEdge(edge)) continue; 275 Node* use = edge.from(); 276 size_t index; 277 switch (use->opcode()) { 278 case IrOpcode::kIfTrue: 279 DCHECK_EQ(IrOpcode::kBranch, node->opcode()); 280 index = 0; 281 break; 282 case IrOpcode::kIfFalse: 283 DCHECK_EQ(IrOpcode::kBranch, node->opcode()); 284 index = 1; 285 break; 286 case IrOpcode::kIfSuccess: 287 DCHECK(!node->op()->HasProperty(Operator::kNoThrow)); 288 index = 0; 289 break; 290 case IrOpcode::kIfException: 291 DCHECK(!node->op()->HasProperty(Operator::kNoThrow)); 292 index = 1; 293 break; 294 case IrOpcode::kIfValue: 295 DCHECK_EQ(IrOpcode::kSwitch, node->opcode()); 296 index = if_value_index++; 297 break; 298 case IrOpcode::kIfDefault: 299 DCHECK_EQ(IrOpcode::kSwitch, node->opcode()); 300 index = projection_count - 1; 301 break; 302 default: 303 continue; 304 } 305 DCHECK_LT(if_value_index, projection_count); 306 DCHECK_LT(index, projection_count); 307 DCHECK_NULL(projections[index]); 308 projections[index] = use; 309 } 310 #ifdef DEBUG 311 for (size_t index = 0; index < projection_count; ++index) { 312 DCHECK_NOT_NULL(projections[index]); 313 } 314 #endif 315 } 316 317 // static 318 bool NodeProperties::IsSame(Node* a, Node* b) { 319 for (;;) { 320 if (a->opcode() == IrOpcode::kCheckHeapObject) { 321 a = GetValueInput(a, 0); 322 continue; 323 } 324 if (b->opcode() == IrOpcode::kCheckHeapObject) { 325 b = GetValueInput(b, 0); 326 continue; 327 } 328 return a == b; 329 } 330 } 331 332 // static 333 NodeProperties::InferReceiverMapsResult NodeProperties::InferReceiverMaps( 334 Node* receiver, Node* effect, ZoneHandleSet<Map>* maps_return) { 335 HeapObjectMatcher m(receiver); 336 if (m.HasValue()) { 337 Handle<Map> receiver_map(m.Value()->map()); 338 if (receiver_map->is_stable()) { 339 // The {receiver_map} is only reliable when we install a stability 340 // code dependency. 341 *maps_return = ZoneHandleSet<Map>(receiver_map); 342 return kUnreliableReceiverMaps; 343 } 344 } 345 InferReceiverMapsResult result = kReliableReceiverMaps; 346 while (true) { 347 switch (effect->opcode()) { 348 case IrOpcode::kCheckMaps: { 349 Node* const object = GetValueInput(effect, 0); 350 if (IsSame(receiver, object)) { 351 *maps_return = CheckMapsParametersOf(effect->op()).maps(); 352 return result; 353 } 354 break; 355 } 356 case IrOpcode::kJSCreate: { 357 if (IsSame(receiver, effect)) { 358 HeapObjectMatcher mtarget(GetValueInput(effect, 0)); 359 HeapObjectMatcher mnewtarget(GetValueInput(effect, 1)); 360 if (mtarget.HasValue() && mnewtarget.HasValue()) { 361 Handle<JSFunction> original_constructor = 362 Handle<JSFunction>::cast(mnewtarget.Value()); 363 if (original_constructor->has_initial_map()) { 364 Handle<Map> initial_map(original_constructor->initial_map()); 365 if (initial_map->constructor_or_backpointer() == 366 *mtarget.Value()) { 367 *maps_return = ZoneHandleSet<Map>(initial_map); 368 return result; 369 } 370 } 371 } 372 // We reached the allocation of the {receiver}. 373 return kNoReceiverMaps; 374 } 375 break; 376 } 377 case IrOpcode::kStoreField: { 378 // We only care about StoreField of maps. 379 Node* const object = GetValueInput(effect, 0); 380 FieldAccess const& access = FieldAccessOf(effect->op()); 381 if (access.base_is_tagged == kTaggedBase && 382 access.offset == HeapObject::kMapOffset) { 383 if (IsSame(receiver, object)) { 384 Node* const value = GetValueInput(effect, 1); 385 HeapObjectMatcher m(value); 386 if (m.HasValue()) { 387 *maps_return = ZoneHandleSet<Map>(Handle<Map>::cast(m.Value())); 388 return result; 389 } 390 } 391 // Without alias analysis we cannot tell whether this 392 // StoreField[map] affects {receiver} or not. 393 result = kUnreliableReceiverMaps; 394 } 395 break; 396 } 397 case IrOpcode::kJSStoreMessage: 398 case IrOpcode::kJSStoreModule: 399 case IrOpcode::kStoreElement: 400 case IrOpcode::kStoreTypedElement: { 401 // These never change the map of objects. 402 break; 403 } 404 default: { 405 DCHECK_EQ(1, effect->op()->EffectOutputCount()); 406 if (effect->op()->EffectInputCount() != 1) { 407 // Didn't find any appropriate CheckMaps node. 408 return kNoReceiverMaps; 409 } 410 if (!effect->op()->HasProperty(Operator::kNoWrite)) { 411 // Without alias/escape analysis we cannot tell whether this 412 // {effect} affects {receiver} or not. 413 result = kUnreliableReceiverMaps; 414 } 415 break; 416 } 417 } 418 DCHECK_EQ(1, effect->op()->EffectInputCount()); 419 effect = NodeProperties::GetEffectInput(effect); 420 } 421 } 422 423 // static 424 MaybeHandle<Context> NodeProperties::GetSpecializationContext( 425 Node* node, MaybeHandle<Context> context) { 426 switch (node->opcode()) { 427 case IrOpcode::kHeapConstant: 428 return Handle<Context>::cast(OpParameter<Handle<HeapObject>>(node)); 429 case IrOpcode::kParameter: { 430 Node* const start = NodeProperties::GetValueInput(node, 0); 431 DCHECK_EQ(IrOpcode::kStart, start->opcode()); 432 int const index = ParameterIndexOf(node->op()); 433 // The context is always the last parameter to a JavaScript function, and 434 // {Parameter} indices start at -1, so value outputs of {Start} look like 435 // this: closure, receiver, param0, ..., paramN, context. 436 if (index == start->op()->ValueOutputCount() - 2) { 437 return context; 438 } 439 break; 440 } 441 default: 442 break; 443 } 444 return MaybeHandle<Context>(); 445 } 446 447 448 // static 449 Node* NodeProperties::GetOuterContext(Node* node, size_t* depth) { 450 Node* context = NodeProperties::GetContextInput(node); 451 while (*depth > 0 && 452 IrOpcode::IsContextChainExtendingOpcode(context->opcode())) { 453 context = NodeProperties::GetContextInput(context); 454 (*depth)--; 455 } 456 return context; 457 } 458 459 // static 460 Type* NodeProperties::GetTypeOrAny(Node* node) { 461 return IsTyped(node) ? node->type() : Type::Any(); 462 } 463 464 465 // static 466 bool NodeProperties::AllValueInputsAreTyped(Node* node) { 467 int input_count = node->op()->ValueInputCount(); 468 for (int index = 0; index < input_count; ++index) { 469 if (!IsTyped(GetValueInput(node, index))) return false; 470 } 471 return true; 472 } 473 474 475 // static 476 bool NodeProperties::IsInputRange(Edge edge, int first, int num) { 477 if (num == 0) return false; 478 int const index = edge.index(); 479 return first <= index && index < first + num; 480 } 481 482 } // namespace compiler 483 } // namespace internal 484 } // namespace v8 485