Line data Source code
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 :
16 : namespace v8 {
17 : namespace internal {
18 : namespace compiler {
19 :
20 : // static
21 925079670 : int NodeProperties::PastValueIndex(Node* node) {
22 925136590 : return FirstValueIndex(node) + node->op()->ValueInputCount();
23 : }
24 :
25 :
26 : // static
27 18 : int NodeProperties::PastContextIndex(Node* node) {
28 : return FirstContextIndex(node) +
29 917139023 : OperatorProperties::GetContextInputCount(node->op());
30 : }
31 :
32 :
33 : // static
34 1810211352 : int NodeProperties::PastFrameStateIndex(Node* node) {
35 : return FirstFrameStateIndex(node) +
36 905013458 : OperatorProperties::GetFrameStateInputCount(node->op());
37 : }
38 :
39 :
40 : // static
41 678188250 : int NodeProperties::PastEffectIndex(Node* node) {
42 1193678440 : return FirstEffectIndex(node) + node->op()->EffectInputCount();
43 : }
44 :
45 :
46 : // static
47 55085748 : int NodeProperties::PastControlIndex(Node* node) {
48 110170100 : return FirstControlIndex(node) + node->op()->ControlInputCount();
49 : }
50 :
51 :
52 : // static
53 106737033 : Node* NodeProperties::GetValueInput(Node* node, int index) {
54 : DCHECK(0 <= index && index < node->op()->ValueInputCount());
55 106737033 : return node->InputAt(FirstValueIndex(node) + index);
56 : }
57 :
58 :
59 : // static
60 6313557 : Node* NodeProperties::GetContextInput(Node* node) {
61 : DCHECK(OperatorProperties::HasContextInput(node->op()));
62 6313557 : return node->InputAt(FirstContextIndex(node));
63 : }
64 :
65 :
66 : // static
67 4818859 : Node* NodeProperties::GetFrameStateInput(Node* node) {
68 : DCHECK_EQ(1, OperatorProperties::GetFrameStateInputCount(node->op()));
69 4818859 : return node->InputAt(FirstFrameStateIndex(node));
70 : }
71 :
72 :
73 : // static
74 112531744 : Node* NodeProperties::GetEffectInput(Node* node, int index) {
75 : DCHECK(0 <= index && index < node->op()->EffectInputCount());
76 225051908 : return node->InputAt(FirstEffectIndex(node) + index);
77 : }
78 :
79 :
80 : // static
81 248704390 : Node* NodeProperties::GetControlInput(Node* node, int index) {
82 : DCHECK(0 <= index && index < node->op()->ControlInputCount());
83 497360192 : return node->InputAt(FirstControlIndex(node) + index);
84 : }
85 :
86 :
87 : // static
88 1172546 : bool NodeProperties::IsValueEdge(Edge edge) {
89 1172546 : Node* const node = edge.from();
90 : return IsInputRange(edge, FirstValueIndex(node),
91 2345092 : node->op()->ValueInputCount());
92 : }
93 :
94 :
95 : // static
96 0 : bool NodeProperties::IsContextEdge(Edge edge) {
97 0 : Node* const node = edge.from();
98 : return IsInputRange(edge, FirstContextIndex(node),
99 0 : OperatorProperties::GetContextInputCount(node->op()));
100 : }
101 :
102 :
103 : // static
104 408874 : bool NodeProperties::IsFrameStateEdge(Edge edge) {
105 408874 : Node* const node = edge.from();
106 : return IsInputRange(edge, FirstFrameStateIndex(node),
107 408874 : OperatorProperties::GetFrameStateInputCount(node->op()));
108 : }
109 :
110 :
111 : // static
112 176732729 : bool NodeProperties::IsEffectEdge(Edge edge) {
113 176732729 : Node* const node = edge.from();
114 : return IsInputRange(edge, FirstEffectIndex(node),
115 353462705 : node->op()->EffectInputCount());
116 : }
117 :
118 :
119 : // static
120 202973670 : bool NodeProperties::IsControlEdge(Edge edge) {
121 202973670 : Node* const node = edge.from();
122 : return IsInputRange(edge, FirstControlIndex(node),
123 405937061 : node->op()->ControlInputCount());
124 : }
125 :
126 :
127 : // static
128 11016274 : bool NodeProperties::IsExceptionalCall(Node* node, Node** out_exception) {
129 11016274 : if (node->op()->HasProperty(Operator::kNoThrow)) return false;
130 120851368 : for (Edge const edge : node->use_edges()) {
131 55227676 : if (!NodeProperties::IsControlEdge(edge)) continue;
132 38832402 : if (edge.from()->opcode() == IrOpcode::kIfException) {
133 630482 : if (out_exception != nullptr) *out_exception = edge.from();
134 620289 : return true;
135 : }
136 : }
137 10396016 : return false;
138 : }
139 :
140 : // static
141 8246 : Node* NodeProperties::FindSuccessfulControlProjection(Node* node) {
142 : DCHECK_GT(node->op()->ControlOutputCount(), 0);
143 8246 : if (node->op()->HasProperty(Operator::kNoThrow)) return node;
144 245164 : for (Edge const edge : node->use_edges()) {
145 119023 : if (!NodeProperties::IsControlEdge(edge)) continue;
146 60648 : if (edge.from()->opcode() == IrOpcode::kIfSuccess) {
147 1128 : return edge.from();
148 : }
149 : }
150 7118 : return node;
151 : }
152 :
153 : // static
154 527341 : void NodeProperties::ReplaceValueInput(Node* node, Node* value, int index) {
155 : DCHECK(index < node->op()->ValueInputCount());
156 527341 : node->ReplaceInput(FirstValueIndex(node) + index, value);
157 527341 : }
158 :
159 :
160 : // static
161 239 : void NodeProperties::ReplaceValueInputs(Node* node, Node* value) {
162 239 : int value_input_count = node->op()->ValueInputCount();
163 : DCHECK_LE(1, value_input_count);
164 239 : node->ReplaceInput(0, value);
165 925 : while (--value_input_count > 0) {
166 447 : node->RemoveInput(value_input_count);
167 : }
168 239 : }
169 :
170 :
171 : // static
172 431912 : void NodeProperties::ReplaceContextInput(Node* node, Node* context) {
173 431912 : node->ReplaceInput(FirstContextIndex(node), context);
174 431912 : }
175 :
176 :
177 : // static
178 8763419 : void NodeProperties::ReplaceControlInput(Node* node, Node* control, int index) {
179 : DCHECK(index < node->op()->ControlInputCount());
180 8763418 : node->ReplaceInput(FirstControlIndex(node) + index, control);
181 8763411 : }
182 :
183 :
184 : // static
185 4432673 : void NodeProperties::ReplaceEffectInput(Node* node, Node* effect, int index) {
186 : DCHECK(index < node->op()->EffectInputCount());
187 4432672 : return node->ReplaceInput(FirstEffectIndex(node) + index, effect);
188 : }
189 :
190 :
191 : // static
192 6853311 : void NodeProperties::ReplaceFrameStateInput(Node* node, Node* frame_state) {
193 : DCHECK_EQ(1, OperatorProperties::GetFrameStateInputCount(node->op()));
194 6853314 : node->ReplaceInput(FirstFrameStateIndex(node), frame_state);
195 6853313 : }
196 :
197 :
198 : // static
199 234078 : void NodeProperties::RemoveNonValueInputs(Node* node) {
200 468156 : node->TrimInputCount(node->op()->ValueInputCount());
201 234078 : }
202 :
203 :
204 : // static
205 8 : void NodeProperties::RemoveValueInputs(Node* node) {
206 8 : int value_input_count = node->op()->ValueInputCount();
207 32 : while (--value_input_count >= 0) {
208 16 : node->RemoveInput(value_input_count);
209 : }
210 8 : }
211 :
212 :
213 1130637 : void NodeProperties::MergeControlToEnd(Graph* graph,
214 : CommonOperatorBuilder* common,
215 : Node* node) {
216 376878 : graph->end()->AppendInput(graph->zone(), node);
217 376880 : graph->end()->set_op(common->End(graph->end()->InputCount()));
218 376879 : }
219 :
220 :
221 : // static
222 1911952 : void NodeProperties::ReplaceUses(Node* node, Node* value, Node* effect,
223 : Node* success, Node* exception) {
224 : // Requires distinguishing between value, effect and control edges.
225 14347720 : for (Edge edge : node->use_edges()) {
226 6217879 : if (IsControlEdge(edge)) {
227 8599956 : if (edge.from()->opcode() == IrOpcode::kIfSuccess) {
228 : DCHECK_NOT_NULL(success);
229 28755 : edge.UpdateTo(success);
230 5675794 : } else if (edge.from()->opcode() == IrOpcode::kIfException) {
231 : DCHECK_NOT_NULL(exception);
232 7771 : edge.UpdateTo(exception);
233 : } else {
234 : DCHECK_NOT_NULL(success);
235 2830126 : edge.UpdateTo(success);
236 : }
237 3351249 : } else if (IsEffectEdge(edge)) {
238 : DCHECK_NOT_NULL(effect);
239 1888879 : edge.UpdateTo(effect);
240 : } else {
241 : DCHECK_NOT_NULL(value);
242 1462379 : edge.UpdateTo(value);
243 : }
244 : }
245 1911962 : }
246 :
247 :
248 : // static
249 23087496 : void NodeProperties::ChangeOp(Node* node, const Operator* new_op) {
250 : node->set_op(new_op);
251 : Verifier::VerifyNode(node);
252 23087496 : }
253 :
254 :
255 : // static
256 88823 : Node* NodeProperties::FindFrameStateBefore(Node* node) {
257 370291 : Node* effect = NodeProperties::GetEffectInput(node);
258 370291 : while (effect->opcode() != IrOpcode::kCheckpoint) {
259 192645 : if (effect->opcode() == IrOpcode::kDead) return effect;
260 : DCHECK_EQ(1, effect->op()->EffectInputCount());
261 192645 : effect = NodeProperties::GetEffectInput(effect);
262 : }
263 88823 : Node* frame_state = GetFrameStateInput(effect);
264 88823 : return frame_state;
265 : }
266 :
267 : // static
268 206070 : Node* NodeProperties::FindProjection(Node* node, size_t projection_index) {
269 412182 : for (auto use : node->uses()) {
270 412129 : if (use->opcode() == IrOpcode::kProjection &&
271 206055 : ProjectionIndexOf(use->op()) == projection_index) {
272 : return use;
273 : }
274 : }
275 : return nullptr;
276 : }
277 :
278 :
279 : // static
280 7814714 : void NodeProperties::CollectControlProjections(Node* node, Node** projections,
281 : size_t projection_count) {
282 : #ifdef DEBUG
283 : DCHECK_LE(static_cast<int>(projection_count), node->UseCount());
284 : std::memset(projections, 0, sizeof(*projections) * projection_count);
285 : #endif
286 : size_t if_value_index = 0;
287 45198005 : for (Edge const edge : node->use_edges()) {
288 18691654 : if (!IsControlEdge(edge)) continue;
289 16210707 : Node* use = edge.from();
290 : size_t index;
291 16210707 : switch (use->opcode()) {
292 : case IrOpcode::kIfTrue:
293 : DCHECK_EQ(IrOpcode::kBranch, node->opcode());
294 : index = 0;
295 : break;
296 : case IrOpcode::kIfFalse:
297 : DCHECK_EQ(IrOpcode::kBranch, node->opcode());
298 : index = 1;
299 7151200 : break;
300 : case IrOpcode::kIfSuccess:
301 : DCHECK(!node->op()->HasProperty(Operator::kNoThrow));
302 : index = 0;
303 : break;
304 : case IrOpcode::kIfException:
305 : DCHECK(!node->op()->HasProperty(Operator::kNoThrow));
306 : index = 1;
307 609609 : break;
308 : case IrOpcode::kIfValue:
309 : DCHECK_EQ(IrOpcode::kSwitch, node->opcode());
310 635398 : index = if_value_index++;
311 635398 : break;
312 : case IrOpcode::kIfDefault:
313 : DCHECK_EQ(IrOpcode::kSwitch, node->opcode());
314 53877 : index = projection_count - 1;
315 53877 : break;
316 : default:
317 : continue;
318 : }
319 : DCHECK_LT(if_value_index, projection_count);
320 : DCHECK_LT(index, projection_count);
321 : DCHECK_NULL(projections[index]);
322 16210678 : projections[index] = use;
323 : }
324 : #ifdef DEBUG
325 : for (size_t index = 0; index < projection_count; ++index) {
326 : DCHECK_NOT_NULL(projections[index]);
327 : }
328 : #endif
329 7814697 : }
330 :
331 : // static
332 3258278 : bool NodeProperties::IsSame(Node* a, Node* b) {
333 : for (;;) {
334 1650906 : if (a->opcode() == IrOpcode::kCheckHeapObject) {
335 : a = GetValueInput(a, 0);
336 2032 : continue;
337 : }
338 1648874 : if (b->opcode() == IrOpcode::kCheckHeapObject) {
339 : b = GetValueInput(b, 0);
340 39470 : continue;
341 : }
342 1609404 : return a == b;
343 : }
344 : }
345 :
346 : // static
347 239465 : NodeProperties::InferReceiverMapsResult NodeProperties::InferReceiverMaps(
348 1639342 : Node* receiver, Node* effect, ZoneHandleSet<Map>* maps_return) {
349 : HeapObjectMatcher m(receiver);
350 239465 : if (m.HasValue()) {
351 : Handle<Map> receiver_map(m.Value()->map());
352 117861 : if (receiver_map->is_stable()) {
353 : // The {receiver_map} is only reliable when we install a stability
354 : // code dependency.
355 112456 : *maps_return = ZoneHandleSet<Map>(receiver_map);
356 : return kUnreliableReceiverMaps;
357 : }
358 : }
359 : InferReceiverMapsResult result = kReliableReceiverMaps;
360 : while (true) {
361 1639342 : switch (effect->opcode()) {
362 : case IrOpcode::kMapGuard: {
363 : Node* const object = GetValueInput(effect, 0);
364 138 : if (IsSame(receiver, object)) {
365 96 : *maps_return = MapGuardMapsOf(effect->op()).maps();
366 96 : return result;
367 : }
368 : break;
369 : }
370 : case IrOpcode::kCheckMaps: {
371 : Node* const object = GetValueInput(effect, 0);
372 49062 : if (IsSame(receiver, object)) {
373 29221 : *maps_return = CheckMapsParametersOf(effect->op()).maps();
374 29221 : return result;
375 : }
376 : break;
377 : }
378 : case IrOpcode::kJSCreate: {
379 6752 : if (IsSame(receiver, effect)) {
380 : HeapObjectMatcher mtarget(GetValueInput(effect, 0));
381 : HeapObjectMatcher mnewtarget(GetValueInput(effect, 1));
382 5932 : if (mtarget.HasValue() && mnewtarget.HasValue()) {
383 : Handle<JSFunction> original_constructor =
384 : Handle<JSFunction>::cast(mnewtarget.Value());
385 3903 : if (original_constructor->has_initial_map()) {
386 : Handle<Map> initial_map(original_constructor->initial_map());
387 3903 : if (initial_map->constructor_or_backpointer() ==
388 : *mtarget.Value()) {
389 3903 : *maps_return = ZoneHandleSet<Map>(initial_map);
390 : return result;
391 : }
392 : }
393 : }
394 : // We reached the allocation of the {receiver}.
395 : return kNoReceiverMaps;
396 : }
397 : break;
398 : }
399 : case IrOpcode::kStoreField: {
400 : // We only care about StoreField of maps.
401 : Node* const object = GetValueInput(effect, 0);
402 30856 : FieldAccess const& access = FieldAccessOf(effect->op());
403 30856 : if (access.base_is_tagged == kTaggedBase &&
404 : access.offset == HeapObject::kMapOffset) {
405 4424 : if (IsSame(receiver, object)) {
406 : Node* const value = GetValueInput(effect, 1);
407 : HeapObjectMatcher m(value);
408 2923 : if (m.HasValue()) {
409 2923 : *maps_return = ZoneHandleSet<Map>(Handle<Map>::cast(m.Value()));
410 : return result;
411 : }
412 : }
413 : // Without alias analysis we cannot tell whether this
414 : // StoreField[map] affects {receiver} or not.
415 : result = kUnreliableReceiverMaps;
416 : }
417 : break;
418 : }
419 : case IrOpcode::kJSStoreMessage:
420 : case IrOpcode::kJSStoreModule:
421 : case IrOpcode::kStoreElement:
422 : case IrOpcode::kStoreTypedElement: {
423 : // These never change the map of objects.
424 : break;
425 : }
426 : case IrOpcode::kFinishRegion: {
427 : // FinishRegion renames the output of allocations, so we need
428 : // to update the {receiver} that we are looking for, if the
429 : // {receiver} matches the current {effect}.
430 4424 : if (IsSame(receiver, effect)) receiver = GetValueInput(effect, 0);
431 : break;
432 : }
433 : default: {
434 : DCHECK_EQ(1, effect->op()->EffectOutputCount());
435 1542054 : if (effect->op()->EffectInputCount() != 1) {
436 : // Didn't find any appropriate CheckMaps node.
437 : return kNoReceiverMaps;
438 : }
439 1485209 : if (!effect->op()->HasProperty(Operator::kNoWrite)) {
440 : // Without alias/escape analysis we cannot tell whether this
441 : // {effect} affects {receiver} or not.
442 : result = kUnreliableReceiverMaps;
443 : }
444 : break;
445 : }
446 : }
447 :
448 : // Stop walking the effect chain once we hit the definition of
449 : // the {receiver} along the {effect}s.
450 1544325 : if (IsSame(receiver, effect)) return kNoReceiverMaps;
451 :
452 : // Continue with the next {effect}.
453 : DCHECK_EQ(1, effect->op()->EffectInputCount());
454 1512333 : effect = NodeProperties::GetEffectInput(effect);
455 1512333 : }
456 : }
457 :
458 : // static
459 5091 : bool NodeProperties::NoObservableSideEffectBetween(Node* effect,
460 : Node* dominator) {
461 5500 : while (effect != dominator) {
462 7517 : if (effect->op()->EffectInputCount() == 1 &&
463 : effect->op()->properties() & Operator::kNoWrite) {
464 2922 : effect = NodeProperties::GetEffectInput(effect);
465 : } else {
466 : return false;
467 : }
468 : }
469 : return true;
470 : }
471 :
472 : // static
473 1035924 : Node* NodeProperties::GetOuterContext(Node* node, size_t* depth) {
474 15740 : Node* context = NodeProperties::GetContextInput(node);
475 2094489 : while (*depth > 0 &&
476 : IrOpcode::IsContextChainExtendingOpcode(context->opcode())) {
477 : context = NodeProperties::GetContextInput(context);
478 6901 : (*depth)--;
479 : }
480 1035924 : return context;
481 : }
482 :
483 : // static
484 0 : Type* NodeProperties::GetTypeOrAny(Node* node) {
485 0 : return IsTyped(node) ? node->type() : Type::Any();
486 : }
487 :
488 :
489 : // static
490 2610509 : bool NodeProperties::AllValueInputsAreTyped(Node* node) {
491 2610509 : int input_count = node->op()->ValueInputCount();
492 3623331 : for (int index = 0; index < input_count; ++index) {
493 1074787 : if (!IsTyped(GetValueInput(node, index))) return false;
494 : }
495 : return true;
496 : }
497 :
498 :
499 : // static
500 : bool NodeProperties::IsInputRange(Edge edge, int first, int num) {
501 381274787 : if (num == 0) return false;
502 : int const index = edge.index();
503 262370373 : return first <= index && index < first + num;
504 : }
505 :
506 : // static
507 220999184 : size_t NodeProperties::HashCode(Node* node) {
508 110499592 : size_t h = base::hash_combine(node->op()->HashCode(), node->InputCount());
509 618770493 : for (Node* input : node->inputs()) {
510 : h = base::hash_combine(h, input->id());
511 : }
512 110492989 : return h;
513 : }
514 :
515 : // static
516 150804324 : bool NodeProperties::Equals(Node* a, Node* b) {
517 : DCHECK_NOT_NULL(a);
518 : DCHECK_NOT_NULL(b);
519 : DCHECK_NOT_NULL(a->op());
520 : DCHECK_NOT_NULL(b->op());
521 150804324 : if (!a->op()->Equals(b->op())) return false;
522 3258353 : if (a->InputCount() != b->InputCount()) return false;
523 : Node::Inputs aInputs = a->inputs();
524 : Node::Inputs bInputs = b->inputs();
525 :
526 : auto aIt = aInputs.begin();
527 : auto bIt = bInputs.begin();
528 : auto aEnd = aInputs.end();
529 :
530 8189402 : for (; aIt != aEnd; ++aIt, ++bIt) {
531 : DCHECK_NOT_NULL(*aIt);
532 : DCHECK_NOT_NULL(*bIt);
533 19689144 : if ((*aIt)->id() != (*bIt)->id()) return false;
534 : }
535 : return true;
536 : }
537 :
538 : } // namespace compiler
539 : } // namespace internal
540 : } // namespace v8
|
