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