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 16 namespace v8 { 17 namespace internal { 18 namespace compiler { 19 20 class Graph; 21 class Operator; 22 class CommonOperatorBuilder; 23 24 // A facade that simplifies access to the different kinds of inputs to a node. 25 class 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 FirstValueIndex(const Node * node)32 static int FirstValueIndex(const Node* node) { return 0; } FirstContextIndex(Node * node)33 static int FirstContextIndex(Node* node) { return PastValueIndex(node); } FirstFrameStateIndex(Node * node)34 static int FirstFrameStateIndex(Node* node) { return PastContextIndex(node); } FirstEffectIndex(Node * node)35 static int FirstEffectIndex(Node* node) { return PastFrameStateIndex(node); } FirstControlIndex(Node * node)36 static int FirstControlIndex(Node* node) { return PastEffectIndex(node); } 37 PastValueIndex(Node * node)38 static int PastValueIndex(Node* node) { 39 return FirstValueIndex(node) + node->op()->ValueInputCount(); 40 } 41 PastContextIndex(Node * node)42 static int PastContextIndex(Node* node) { 43 return FirstContextIndex(node) + 44 OperatorProperties::GetContextInputCount(node->op()); 45 } 46 PastFrameStateIndex(Node * node)47 static int PastFrameStateIndex(Node* node) { 48 return FirstFrameStateIndex(node) + 49 OperatorProperties::GetFrameStateInputCount(node->op()); 50 } 51 PastEffectIndex(Node * node)52 static int PastEffectIndex(Node* node) { 53 return FirstEffectIndex(node) + node->op()->EffectInputCount(); 54 } 55 PastControlIndex(Node * node)56 static int PastControlIndex(Node* node) { 57 return FirstControlIndex(node) + node->op()->ControlInputCount(); 58 } 59 60 // --------------------------------------------------------------------------- 61 // Input accessors. 62 GetValueInput(Node * node,int index)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 GetValueInput(const Node * node,int index)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 GetContextInput(Node * node)75 static Node* GetContextInput(Node* node) { 76 CHECK(OperatorProperties::HasContextInput(node->op())); 77 return node->InputAt(FirstContextIndex(node)); 78 } 79 GetFrameStateInput(Node * node)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 IsCommon(Node * node)109 static bool IsCommon(Node* node) { 110 return IrOpcode::IsCommonOpcode(node->opcode()); 111 } IsControl(Node * node)112 static bool IsControl(Node* node) { 113 return IrOpcode::IsControlOpcode(node->opcode()); 114 } IsConstant(Node * node)115 static bool IsConstant(Node* node) { 116 return IrOpcode::IsConstantOpcode(node->opcode()); 117 } IsPhi(Node * node)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}. IsValueIdentity(Node * node,Node ** 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 IsTyped(const Node * node)258 static bool IsTyped(const Node* node) { return !node->type().IsInvalid(); } GetType(const Node * node)259 static Type GetType(const Node* node) { 260 DCHECK(IsTyped(node)); 261 return node->type(); 262 } 263 static Type GetTypeOrAny(const Node* node); SetType(Node * node,Type type)264 static void SetType(Node* node, Type type) { 265 DCHECK(!type.IsInvalid()); 266 node->set_type(type); 267 } RemoveType(Node * node)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