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
PastValueIndex(Node * node)22 int NodeProperties::PastValueIndex(Node* node) {
23 return FirstValueIndex(node) + node->op()->ValueInputCount();
24 }
25
26
27 // static
PastContextIndex(Node * node)28 int NodeProperties::PastContextIndex(Node* node) {
29 return FirstContextIndex(node) +
30 OperatorProperties::GetContextInputCount(node->op());
31 }
32
33
34 // static
PastFrameStateIndex(Node * node)35 int NodeProperties::PastFrameStateIndex(Node* node) {
36 return FirstFrameStateIndex(node) +
37 OperatorProperties::GetFrameStateInputCount(node->op());
38 }
39
40
41 // static
PastEffectIndex(Node * node)42 int NodeProperties::PastEffectIndex(Node* node) {
43 return FirstEffectIndex(node) + node->op()->EffectInputCount();
44 }
45
46
47 // static
PastControlIndex(Node * node)48 int NodeProperties::PastControlIndex(Node* node) {
49 return FirstControlIndex(node) + node->op()->ControlInputCount();
50 }
51
52
53 // static
GetValueInput(Node * node,int index)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
GetContextInput(Node * node)61 Node* NodeProperties::GetContextInput(Node* node) {
62 DCHECK(OperatorProperties::HasContextInput(node->op()));
63 return node->InputAt(FirstContextIndex(node));
64 }
65
66
67 // static
GetFrameStateInput(Node * node)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
GetEffectInput(Node * node,int index)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
GetControlInput(Node * node,int index)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
IsValueEdge(Edge edge)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
IsContextEdge(Edge edge)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
IsFrameStateEdge(Edge edge)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
IsEffectEdge(Edge edge)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
IsControlEdge(Edge edge)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
IsExceptionalCall(Node * node)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
ReplaceValueInput(Node * node,Node * value,int index)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
ReplaceValueInputs(Node * node,Node * value)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
ReplaceContextInput(Node * node,Node * context)158 void NodeProperties::ReplaceContextInput(Node* node, Node* context) {
159 node->ReplaceInput(FirstContextIndex(node), context);
160 }
161
162
163 // static
ReplaceControlInput(Node * node,Node * control,int index)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
ReplaceEffectInput(Node * node,Node * effect,int index)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
ReplaceFrameStateInput(Node * node,Node * frame_state)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
RemoveNonValueInputs(Node * node)185 void NodeProperties::RemoveNonValueInputs(Node* node) {
186 node->TrimInputCount(node->op()->ValueInputCount());
187 }
188
189
190 // static
RemoveValueInputs(Node * node)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
MergeControlToEnd(Graph * graph,CommonOperatorBuilder * common,Node * node)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
ReplaceUses(Node * node,Node * value,Node * effect,Node * success,Node * exception)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
ChangeOp(Node * node,const Operator * new_op)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
FindFrameStateBefore(Node * node)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
FindProjection(Node * node,size_t projection_index)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
CollectControlProjections(Node * node,Node ** projections,size_t projection_count)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
IsSame(Node * a,Node * b)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
InferReceiverMaps(Node * receiver,Node * effect,ZoneHandleSet<Map> * maps_return)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
GetSpecializationContext(Node * node,MaybeHandle<Context> context)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
GetOuterContext(Node * node,size_t * depth)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
GetTypeOrAny(Node * node)460 Type* NodeProperties::GetTypeOrAny(Node* node) {
461 return IsTyped(node) ? node->type() : Type::Any();
462 }
463
464
465 // static
AllValueInputsAreTyped(Node * node)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
IsInputRange(Edge edge,int first,int num)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