1// Copyright 2013 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#ifndef V8_COMPILER_NODE_PROPERTIES_H_
6#define V8_COMPILER_NODE_PROPERTIES_H_
7
8#include "src/common/globals.h"
9#include "src/compiler/heap-refs.h"
10#include "src/compiler/node.h"
11#include "src/compiler/operator-properties.h"
12#include "src/compiler/types.h"
13#include "src/objects/map.h"
14#include "src/zone/zone-handle-set.h"
15
16namespace v8 {
17namespace internal {
18namespace compiler {
19
20class Graph;
21class Operator;
22class CommonOperatorBuilder;
23
24// A facade that simplifies access to the different kinds of inputs to a node.
25class V8_EXPORT_PRIVATE NodeProperties {
26 public:
27  // ---------------------------------------------------------------------------
28  // Input layout.
29  // Inputs are always arranged in order as follows:
30  //     0 [ values, context, frame state, effects, control ] node->InputCount()
31
32  static int FirstValueIndex(const Node* node) { return 0; }
33  static int FirstContextIndex(Node* node) { return PastValueIndex(node); }
34  static int FirstFrameStateIndex(Node* node) { return PastContextIndex(node); }
35  static int FirstEffectIndex(Node* node) { return PastFrameStateIndex(node); }
36  static int FirstControlIndex(Node* node) { return PastEffectIndex(node); }
37
38  static int PastValueIndex(Node* node) {
39    return FirstValueIndex(node) + node->op()->ValueInputCount();
40  }
41
42  static int PastContextIndex(Node* node) {
43    return FirstContextIndex(node) +
44           OperatorProperties::GetContextInputCount(node->op());
45  }
46
47  static int PastFrameStateIndex(Node* node) {
48    return FirstFrameStateIndex(node) +
49           OperatorProperties::GetFrameStateInputCount(node->op());
50  }
51
52  static int PastEffectIndex(Node* node) {
53    return FirstEffectIndex(node) + node->op()->EffectInputCount();
54  }
55
56  static int PastControlIndex(Node* node) {
57    return FirstControlIndex(node) + node->op()->ControlInputCount();
58  }
59
60  // ---------------------------------------------------------------------------
61  // Input accessors.
62
63  static Node* GetValueInput(Node* node, int index) {
64    CHECK_LE(0, index);
65    CHECK_LT(index, node->op()->ValueInputCount());
66    return node->InputAt(FirstValueIndex(node) + index);
67  }
68
69  static const Node* GetValueInput(const Node* node, int index) {
70    CHECK_LE(0, index);
71    CHECK_LT(index, node->op()->ValueInputCount());
72    return node->InputAt(FirstValueIndex(node) + index);
73  }
74
75  static Node* GetContextInput(Node* node) {
76    CHECK(OperatorProperties::HasContextInput(node->op()));
77    return node->InputAt(FirstContextIndex(node));
78  }
79
80  static Node* GetFrameStateInput(Node* node) {
81    CHECK(OperatorProperties::HasFrameStateInput(node->op()));
82    return node->InputAt(FirstFrameStateIndex(node));
83  }
84
85  static Node* GetEffectInput(Node* node, int index = 0) {
86    CHECK_LE(0, index);
87    CHECK_LT(index, node->op()->EffectInputCount());
88    return node->InputAt(FirstEffectIndex(node) + index);
89  }
90
91  static Node* GetControlInput(Node* node, int index = 0) {
92    CHECK_LE(0, index);
93    CHECK_LT(index, node->op()->ControlInputCount());
94    return node->InputAt(FirstControlIndex(node) + index);
95  }
96
97  // ---------------------------------------------------------------------------
98  // Edge kinds.
99
100  static bool IsValueEdge(Edge edge);
101  static bool IsContextEdge(Edge edge);
102  static bool IsFrameStateEdge(Edge edge);
103  static bool IsEffectEdge(Edge edge);
104  static bool IsControlEdge(Edge edge);
105
106  // ---------------------------------------------------------------------------
107  // Miscellaneous predicates.
108
109  static bool IsCommon(Node* node) {
110    return IrOpcode::IsCommonOpcode(node->opcode());
111  }
112  static bool IsControl(Node* node) {
113    return IrOpcode::IsControlOpcode(node->opcode());
114  }
115  static bool IsConstant(Node* node) {
116    return IrOpcode::IsConstantOpcode(node->opcode());
117  }
118  static bool IsPhi(Node* node) {
119    return IrOpcode::IsPhiOpcode(node->opcode());
120  }
121
122  // Determines whether exceptions thrown by the given node are handled locally
123  // within the graph (i.e. an IfException projection is present). Optionally
124  // the present IfException projection is returned via {out_exception}.
125  static bool IsExceptionalCall(Node* node, Node** out_exception = nullptr);
126
127  // Returns the node producing the successful control output of {node}. This is
128  // the IfSuccess projection of {node} if present and {node} itself otherwise.
129  static Node* FindSuccessfulControlProjection(Node* node);
130
131  // Returns whether the node acts as the identity function on a value
132  // input. The input that is passed through is returned via {out_value}.
133  static bool IsValueIdentity(Node* node, Node** out_value) {
134    switch (node->opcode()) {
135      case IrOpcode::kTypeGuard:
136        *out_value = GetValueInput(node, 0);
137        return true;
138      case IrOpcode::kFoldConstant:
139        *out_value = GetValueInput(node, 1);
140        return true;
141      default:
142        return false;
143    }
144  }
145
146  // Determines if {node} has an allocating opcode, or is a builtin known to
147  // return a fresh object.
148  static bool IsFreshObject(Node* node);
149
150  // ---------------------------------------------------------------------------
151  // Miscellaneous mutators.
152
153  static void ReplaceValueInput(Node* node, Node* value, int index);
154  static void ReplaceContextInput(Node* node, Node* context);
155  static void ReplaceControlInput(Node* node, Node* control, int index = 0);
156  static void ReplaceEffectInput(Node* node, Node* effect, int index = 0);
157  static void ReplaceFrameStateInput(Node* node, Node* frame_state);
158  static void RemoveNonValueInputs(Node* node);
159  static void RemoveValueInputs(Node* node);
160
161  // Replaces all value inputs of {node} with the single input {value}.
162  static void ReplaceValueInputs(Node* node, Node* value);
163
164  // Merge the control node {node} into the end of the graph, introducing a
165  // merge node or expanding an existing merge node if necessary.
166  static void MergeControlToEnd(Graph* graph, CommonOperatorBuilder* common,
167                                Node* node);
168
169  // Removes the control node {node} from the end of the graph, reducing the
170  // existing merge node's input count.
171  static void RemoveControlFromEnd(Graph* graph, CommonOperatorBuilder* common,
172                                   Node* node);
173
174  // Replace all uses of {node} with the given replacement nodes. All occurring
175  // use kinds need to be replaced, {nullptr} is only valid if a use kind is
176  // guaranteed not to exist.
177  static void ReplaceUses(Node* node, Node* value, Node* effect = nullptr,
178                          Node* success = nullptr, Node* exception = nullptr);
179
180  // Safe wrapper to mutate the operator of a node. Checks that the node is
181  // currently in a state that satisfies constraints of the new operator.
182  static void ChangeOp(Node* node, const Operator* new_op);
183
184  // ---------------------------------------------------------------------------
185  // Miscellaneous utilities.
186
187  // Find the last frame state that is effect-wise before the given node. This
188  // assumes a linear effect-chain up to a {CheckPoint} node in the graph.
189  // Returns {unreachable_sentinel} if {node} is determined to be unreachable.
190  static Node* FindFrameStateBefore(Node* node, Node* unreachable_sentinel);
191
192  // Collect the output-value projection for the given output index.
193  static Node* FindProjection(Node* node, size_t projection_index);
194
195  // Collect the value projections from a node.
196  static void CollectValueProjections(Node* node, Node** proj, size_t count);
197
198  // Collect the branch-related projections from a node, such as IfTrue,
199  // IfFalse, IfSuccess, IfException, IfValue and IfDefault.
200  //  - Branch: [ IfTrue, IfFalse ]
201  //  - Call  : [ IfSuccess, IfException ]
202  //  - Switch: [ IfValue, ..., IfDefault ]
203  static void CollectControlProjections(Node* node, Node** proj, size_t count);
204
205  // Checks if two nodes are the same, looking past {CheckHeapObject}.
206  static bool IsSame(Node* a, Node* b);
207
208  // Check if two nodes have equal operators and reference-equal inputs. Used
209  // for value numbering/hash-consing.
210  static bool Equals(Node* a, Node* b);
211  // A corresponding hash function.
212  static size_t HashCode(Node* node);
213
214  // Walks up the {effect} chain to find a witness that provides map
215  // information about the {receiver}. Can look through potentially
216  // side effecting nodes.
217  enum InferMapsResult {
218    kNoMaps,         // No maps inferred.
219    kReliableMaps,   // Maps can be trusted.
220    kUnreliableMaps  // Maps might have changed (side-effect).
221  };
222  // DO NOT USE InferMapsUnsafe IN NEW CODE. Use MapInference instead.
223  static InferMapsResult InferMapsUnsafe(JSHeapBroker* broker, Node* receiver,
224                                         Effect effect,
225                                         ZoneRefUnorderedSet<MapRef>* maps_out);
226
227  // Return the initial map of the new-target if the allocation can be inlined.
228  static base::Optional<MapRef> GetJSCreateMap(JSHeapBroker* broker,
229                                               Node* receiver);
230
231  // Walks up the {effect} chain to check that there's no observable side-effect
232  // between the {effect} and it's {dominator}. Aborts the walk if there's join
233  // in the effect chain.
234  static bool NoObservableSideEffectBetween(Node* effect, Node* dominator);
235
236  // Returns true if the {receiver} can be a primitive value (i.e. is not
237  // definitely a JavaScript object); might walk up the {effect} chain to
238  // find map checks on {receiver}.
239  static bool CanBePrimitive(JSHeapBroker* broker, Node* receiver,
240                             Effect effect);
241
242  // Returns true if the {receiver} can be null or undefined. Might walk
243  // up the {effect} chain to find map checks for {receiver}.
244  static bool CanBeNullOrUndefined(JSHeapBroker* broker, Node* receiver,
245                                   Effect effect);
246
247  // ---------------------------------------------------------------------------
248  // Context.
249
250  // Walk up the context chain from the given {node} until we reduce the {depth}
251  // to 0 or hit a node that does not extend the context chain ({depth} will be
252  // updated accordingly).
253  static Node* GetOuterContext(Node* node, size_t* depth);
254
255  // ---------------------------------------------------------------------------
256  // Type.
257
258  static bool IsTyped(const Node* node) { return !node->type().IsInvalid(); }
259  static Type GetType(const Node* node) {
260    DCHECK(IsTyped(node));
261    return node->type();
262  }
263  static Type GetTypeOrAny(const Node* node);
264  static void SetType(Node* node, Type type) {
265    DCHECK(!type.IsInvalid());
266    node->set_type(type);
267  }
268  static void RemoveType(Node* node) { node->set_type(Type::Invalid()); }
269  static bool AllValueInputsAreTyped(Node* node);
270
271 private:
272  static inline bool IsInputRange(Edge edge, int first, int count);
273};
274
275}  // namespace compiler
276}  // namespace internal
277}  // namespace v8
278
279#endif  // V8_COMPILER_NODE_PROPERTIES_H_
280