Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1 | // Copyright 2014 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_AST_GRAPH_BUILDER_H_ |
| 6 | #define V8_COMPILER_AST_GRAPH_BUILDER_H_ |
| 7 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 8 | #include "src/ast/ast.h" |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 9 | #include "src/compiler/js-graph.h" |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 10 | #include "src/compiler/liveness-analyzer.h" |
| 11 | #include "src/compiler/state-values-utils.h" |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 12 | |
| 13 | namespace v8 { |
| 14 | namespace internal { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 15 | |
| 16 | // Forward declarations. |
| 17 | class BitVector; |
| 18 | |
| 19 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 20 | namespace compiler { |
| 21 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 22 | // Forward declarations. |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 23 | class ControlBuilder; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 24 | class Graph; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 25 | class LoopAssignmentAnalysis; |
| 26 | class LoopBuilder; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 27 | class Node; |
| 28 | class TypeHintAnalysis; |
| 29 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 30 | |
| 31 | // The AstGraphBuilder produces a high-level IR graph, based on an |
| 32 | // underlying AST. The produced graph can either be compiled into a |
| 33 | // stand-alone function or be wired into another graph for the purposes |
| 34 | // of function inlining. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 35 | class AstGraphBuilder : public AstVisitor { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 36 | public: |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 37 | AstGraphBuilder(Zone* local_zone, CompilationInfo* info, JSGraph* jsgraph, |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 38 | LoopAssignmentAnalysis* loop_assignment = nullptr, |
| 39 | TypeHintAnalysis* type_hint_analysis = nullptr); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 40 | |
| 41 | // Creates a graph by visiting the entire AST. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 42 | bool CreateGraph(bool stack_check = true); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 43 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 44 | // Helpers to create new control nodes. |
| 45 | Node* NewIfTrue() { return NewNode(common()->IfTrue()); } |
| 46 | Node* NewIfFalse() { return NewNode(common()->IfFalse()); } |
| 47 | Node* NewMerge() { return NewNode(common()->Merge(1), true); } |
| 48 | Node* NewLoop() { return NewNode(common()->Loop(1), true); } |
| 49 | Node* NewBranch(Node* condition, BranchHint hint = BranchHint::kNone) { |
| 50 | return NewNode(common()->Branch(hint), condition); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 51 | } |
| 52 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 53 | protected: |
| 54 | #define DECLARE_VISIT(type) void Visit##type(type* node) override; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 55 | // Visiting functions for AST nodes make this an AstVisitor. |
| 56 | AST_NODE_LIST(DECLARE_VISIT) |
| 57 | #undef DECLARE_VISIT |
| 58 | |
| 59 | // Visiting function for declarations list is overridden. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 60 | void VisitDeclarations(ZoneList<Declaration*>* declarations) override; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 61 | |
| 62 | private: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 63 | class AstContext; |
| 64 | class AstEffectContext; |
| 65 | class AstValueContext; |
| 66 | class AstTestContext; |
| 67 | class ContextScope; |
| 68 | class ControlScope; |
| 69 | class ControlScopeForBreakable; |
| 70 | class ControlScopeForIteration; |
| 71 | class ControlScopeForCatch; |
| 72 | class ControlScopeForFinally; |
| 73 | class Environment; |
| 74 | class FrameStateBeforeAndAfter; |
| 75 | friend class ControlBuilder; |
| 76 | |
| 77 | Isolate* isolate_; |
| 78 | Zone* local_zone_; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 79 | CompilationInfo* info_; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 80 | JSGraph* jsgraph_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 81 | Environment* environment_; |
| 82 | AstContext* ast_context_; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 83 | |
| 84 | // List of global declarations for functions and variables. |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 85 | ZoneVector<Handle<Object>> globals_; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 86 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 87 | // Stack of control scopes currently entered by the visitor. |
| 88 | ControlScope* execution_control_; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 89 | |
| 90 | // Stack of context objects pushed onto the chain by the visitor. |
| 91 | ContextScope* execution_context_; |
| 92 | |
| 93 | // Nodes representing values in the activation record. |
| 94 | SetOncePointer<Node> function_closure_; |
| 95 | SetOncePointer<Node> function_context_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 96 | SetOncePointer<Node> new_target_; |
| 97 | |
| 98 | // Tracks how many try-blocks are currently entered. |
| 99 | int try_catch_nesting_level_; |
| 100 | int try_nesting_level_; |
| 101 | |
| 102 | // Temporary storage for building node input lists. |
| 103 | int input_buffer_size_; |
| 104 | Node** input_buffer_; |
| 105 | |
| 106 | // Optimization to cache loaded feedback vector. |
| 107 | SetOncePointer<Node> feedback_vector_; |
| 108 | |
| 109 | // Control nodes that exit the function body. |
| 110 | ZoneVector<Node*> exit_controls_; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 111 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 112 | // Result of loop assignment analysis performed before graph creation. |
| 113 | LoopAssignmentAnalysis* loop_assignment_analysis_; |
| 114 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 115 | // Result of type hint analysis performed before graph creation. |
| 116 | TypeHintAnalysis* type_hint_analysis_; |
| 117 | |
| 118 | // Cache for StateValues nodes for frame states. |
| 119 | StateValuesCache state_values_cache_; |
| 120 | |
| 121 | // Analyzer of local variable liveness. |
| 122 | LivenessAnalyzer liveness_analyzer_; |
| 123 | |
| 124 | // Function info for frame state construction. |
| 125 | const FrameStateFunctionInfo* const frame_state_function_info_; |
| 126 | |
| 127 | // Growth increment for the temporary buffer used to construct input lists to |
| 128 | // new nodes. |
| 129 | static const int kInputBufferSizeIncrement = 64; |
| 130 | |
| 131 | Zone* local_zone() const { return local_zone_; } |
| 132 | Environment* environment() const { return environment_; } |
| 133 | AstContext* ast_context() const { return ast_context_; } |
| 134 | ControlScope* execution_control() const { return execution_control_; } |
| 135 | ContextScope* execution_context() const { return execution_context_; } |
| 136 | CommonOperatorBuilder* common() const { return jsgraph_->common(); } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 137 | CompilationInfo* info() const { return info_; } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 138 | Isolate* isolate() const { return isolate_; } |
| 139 | LanguageMode language_mode() const; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 140 | JSGraph* jsgraph() { return jsgraph_; } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 141 | Graph* graph() { return jsgraph_->graph(); } |
| 142 | Zone* graph_zone() { return graph()->zone(); } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 143 | JSOperatorBuilder* javascript() { return jsgraph_->javascript(); } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 144 | ZoneVector<Handle<Object>>* globals() { return &globals_; } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 145 | Scope* current_scope() const; |
| 146 | Node* current_context() const; |
| 147 | LivenessAnalyzer* liveness_analyzer() { return &liveness_analyzer_; } |
| 148 | const FrameStateFunctionInfo* frame_state_function_info() const { |
| 149 | return frame_state_function_info_; |
| 150 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 151 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 152 | void set_environment(Environment* env) { environment_ = env; } |
| 153 | void set_ast_context(AstContext* ctx) { ast_context_ = ctx; } |
| 154 | void set_execution_control(ControlScope* ctrl) { execution_control_ = ctrl; } |
| 155 | void set_execution_context(ContextScope* ctx) { execution_context_ = ctx; } |
| 156 | |
| 157 | // Create the main graph body by visiting the AST. |
| 158 | void CreateGraphBody(bool stack_check); |
| 159 | |
| 160 | // Get or create the node that represents the incoming function closure. |
| 161 | Node* GetFunctionClosureForContext(); |
| 162 | Node* GetFunctionClosure(); |
| 163 | |
| 164 | // Get or create the node that represents the incoming function context. |
| 165 | Node* GetFunctionContext(); |
| 166 | |
| 167 | // Get or create the node that represents the incoming new target value. |
| 168 | Node* GetNewTarget(); |
| 169 | |
| 170 | // Node creation helpers. |
| 171 | Node* NewNode(const Operator* op, bool incomplete = false) { |
| 172 | return MakeNode(op, 0, static_cast<Node**>(nullptr), incomplete); |
| 173 | } |
| 174 | |
| 175 | Node* NewNode(const Operator* op, Node* n1) { |
| 176 | return MakeNode(op, 1, &n1, false); |
| 177 | } |
| 178 | |
| 179 | Node* NewNode(const Operator* op, Node* n1, Node* n2) { |
| 180 | Node* buffer[] = {n1, n2}; |
| 181 | return MakeNode(op, arraysize(buffer), buffer, false); |
| 182 | } |
| 183 | |
| 184 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3) { |
| 185 | Node* buffer[] = {n1, n2, n3}; |
| 186 | return MakeNode(op, arraysize(buffer), buffer, false); |
| 187 | } |
| 188 | |
| 189 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4) { |
| 190 | Node* buffer[] = {n1, n2, n3, n4}; |
| 191 | return MakeNode(op, arraysize(buffer), buffer, false); |
| 192 | } |
| 193 | |
| 194 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4, |
| 195 | Node* n5) { |
| 196 | Node* buffer[] = {n1, n2, n3, n4, n5}; |
| 197 | return MakeNode(op, arraysize(buffer), buffer, false); |
| 198 | } |
| 199 | |
| 200 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4, |
| 201 | Node* n5, Node* n6) { |
| 202 | Node* nodes[] = {n1, n2, n3, n4, n5, n6}; |
| 203 | return MakeNode(op, arraysize(nodes), nodes, false); |
| 204 | } |
| 205 | |
| 206 | Node* NewNode(const Operator* op, int value_input_count, Node** value_inputs, |
| 207 | bool incomplete = false) { |
| 208 | return MakeNode(op, value_input_count, value_inputs, incomplete); |
| 209 | } |
| 210 | |
| 211 | // Creates a new Phi node having {count} input values. |
| 212 | Node* NewPhi(int count, Node* input, Node* control); |
| 213 | Node* NewEffectPhi(int count, Node* input, Node* control); |
| 214 | |
| 215 | // Helpers for merging control, effect or value dependencies. |
| 216 | Node* MergeControl(Node* control, Node* other); |
| 217 | Node* MergeEffect(Node* value, Node* other, Node* control); |
| 218 | Node* MergeValue(Node* value, Node* other, Node* control); |
| 219 | |
| 220 | // The main node creation chokepoint. Adds context, frame state, effect, |
| 221 | // and control dependencies depending on the operator. |
| 222 | Node* MakeNode(const Operator* op, int value_input_count, Node** value_inputs, |
| 223 | bool incomplete); |
| 224 | |
| 225 | // Helper to indicate a node exits the function body. |
| 226 | void UpdateControlDependencyToLeaveFunction(Node* exit); |
| 227 | |
| 228 | // Builds deoptimization for a given node. |
| 229 | void PrepareFrameState(Node* node, BailoutId ast_id, |
| 230 | OutputFrameStateCombine framestate_combine = |
| 231 | OutputFrameStateCombine::Ignore()); |
| 232 | |
| 233 | BitVector* GetVariablesAssignedInLoop(IterationStatement* stmt); |
| 234 | |
| 235 | // Check if the given statement is an OSR entry. |
| 236 | // If so, record the stack height into the compilation and return {true}. |
| 237 | bool CheckOsrEntry(IterationStatement* stmt); |
| 238 | |
| 239 | // Computes local variable liveness and replaces dead variables in |
| 240 | // frame states with the undefined values. |
| 241 | void ClearNonLiveSlotsInFrameStates(); |
| 242 | |
| 243 | Node** EnsureInputBufferSize(int size); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 244 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 245 | // Named and keyed loads require a VectorSlotPair for successful lowering. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 246 | VectorSlotPair CreateVectorSlotPair(FeedbackVectorSlot slot) const; |
| 247 | |
| 248 | // Determine which contexts need to be checked for extension objects that |
| 249 | // might shadow the optimistic declaration of dynamic lookup variables. |
| 250 | uint32_t ComputeBitsetForDynamicGlobal(Variable* variable); |
| 251 | uint32_t ComputeBitsetForDynamicContext(Variable* variable); |
| 252 | |
| 253 | // =========================================================================== |
| 254 | // The following build methods all generate graph fragments and return one |
| 255 | // resulting node. The operand stack height remains the same, variables and |
| 256 | // other dependencies tracked by the environment might be mutated though. |
| 257 | |
| 258 | // Builders to create local function, script and block contexts. |
| 259 | Node* BuildLocalActivationContext(Node* context); |
| 260 | Node* BuildLocalFunctionContext(Scope* scope); |
| 261 | Node* BuildLocalScriptContext(Scope* scope); |
| 262 | Node* BuildLocalBlockContext(Scope* scope); |
| 263 | |
| 264 | // Builder to create an arguments object if it is used. |
| 265 | Node* BuildArgumentsObject(Variable* arguments); |
| 266 | |
| 267 | // Builder to create an array of rest parameters if used |
| 268 | Node* BuildRestArgumentsArray(Variable* rest, int index); |
| 269 | |
| 270 | // Builder that assigns to the {.this_function} internal variable if needed. |
| 271 | Node* BuildThisFunctionVariable(Variable* this_function_var); |
| 272 | |
| 273 | // Builder that assigns to the {new.target} internal variable if needed. |
| 274 | Node* BuildNewTargetVariable(Variable* new_target_var); |
| 275 | |
| 276 | // Builders for variable load and assignment. |
| 277 | Node* BuildVariableAssignment(Variable* variable, Node* value, |
| 278 | Token::Value op, const VectorSlotPair& slot, |
| 279 | BailoutId bailout_id, |
| 280 | FrameStateBeforeAndAfter& states, |
| 281 | OutputFrameStateCombine framestate_combine = |
| 282 | OutputFrameStateCombine::Ignore()); |
| 283 | Node* BuildVariableDelete(Variable* variable, BailoutId bailout_id, |
| 284 | OutputFrameStateCombine framestate_combine); |
| 285 | Node* BuildVariableLoad(Variable* variable, BailoutId bailout_id, |
| 286 | FrameStateBeforeAndAfter& states, |
| 287 | const VectorSlotPair& feedback, |
| 288 | OutputFrameStateCombine framestate_combine, |
| 289 | TypeofMode typeof_mode = NOT_INSIDE_TYPEOF); |
| 290 | |
| 291 | // Builders for property loads and stores. |
| 292 | Node* BuildKeyedLoad(Node* receiver, Node* key, |
| 293 | const VectorSlotPair& feedback); |
| 294 | Node* BuildNamedLoad(Node* receiver, Handle<Name> name, |
| 295 | const VectorSlotPair& feedback); |
| 296 | Node* BuildKeyedStore(Node* receiver, Node* key, Node* value, |
| 297 | const VectorSlotPair& feedback); |
| 298 | Node* BuildNamedStore(Node* receiver, Handle<Name> name, Node* value, |
| 299 | const VectorSlotPair& feedback); |
| 300 | |
| 301 | // Builders for super property loads and stores. |
| 302 | Node* BuildKeyedSuperStore(Node* receiver, Node* home_object, Node* key, |
| 303 | Node* value); |
| 304 | Node* BuildNamedSuperStore(Node* receiver, Node* home_object, |
| 305 | Handle<Name> name, Node* value); |
| 306 | Node* BuildNamedSuperLoad(Node* receiver, Node* home_object, |
| 307 | Handle<Name> name, const VectorSlotPair& feedback); |
| 308 | Node* BuildKeyedSuperLoad(Node* receiver, Node* home_object, Node* key, |
| 309 | const VectorSlotPair& feedback); |
| 310 | |
| 311 | // Builders for global variable loads and stores. |
| 312 | Node* BuildGlobalLoad(Handle<Name> name, const VectorSlotPair& feedback, |
| 313 | TypeofMode typeof_mode); |
| 314 | Node* BuildGlobalStore(Handle<Name> name, Node* value, |
| 315 | const VectorSlotPair& feedback); |
| 316 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 317 | // Builders for dynamic variable loads and stores. |
| 318 | Node* BuildDynamicLoad(Handle<Name> name, TypeofMode typeof_mode); |
| 319 | Node* BuildDynamicStore(Handle<Name> name, Node* value); |
| 320 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 321 | // Builders for accessing the function context. |
| 322 | Node* BuildLoadGlobalObject(); |
| 323 | Node* BuildLoadNativeContextField(int index); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 324 | |
| 325 | // Builders for automatic type conversion. |
| 326 | Node* BuildToBoolean(Node* input, TypeFeedbackId feedback_id); |
| 327 | Node* BuildToName(Node* input, BailoutId bailout_id); |
| 328 | Node* BuildToObject(Node* input, BailoutId bailout_id); |
| 329 | |
| 330 | // Builder for adding the [[HomeObject]] to a value if the value came from a |
| 331 | // function literal and needs a home object. Do nothing otherwise. |
| 332 | Node* BuildSetHomeObject(Node* value, Node* home_object, |
| 333 | ObjectLiteralProperty* property, |
| 334 | int slot_number = 0); |
| 335 | |
| 336 | // Builders for error reporting at runtime. |
| 337 | Node* BuildThrowError(Node* exception, BailoutId bailout_id); |
| 338 | Node* BuildThrowReferenceError(Variable* var, BailoutId bailout_id); |
| 339 | Node* BuildThrowConstAssignError(BailoutId bailout_id); |
| 340 | Node* BuildThrowStaticPrototypeError(BailoutId bailout_id); |
| 341 | Node* BuildThrowUnsupportedSuperError(BailoutId bailout_id); |
| 342 | |
| 343 | // Builders for dynamic hole-checks at runtime. |
| 344 | Node* BuildHoleCheckSilent(Node* value, Node* for_hole, Node* not_hole); |
| 345 | Node* BuildHoleCheckThenThrow(Node* value, Variable* var, Node* not_hole, |
| 346 | BailoutId bailout_id); |
| 347 | Node* BuildHoleCheckElseThrow(Node* value, Variable* var, Node* for_hole, |
| 348 | BailoutId bailout_id); |
| 349 | |
| 350 | // Builders for conditional errors. |
| 351 | Node* BuildThrowIfStaticPrototype(Node* name, BailoutId bailout_id); |
| 352 | |
| 353 | // Builders for non-local control flow. |
| 354 | Node* BuildReturn(Node* return_value); |
| 355 | Node* BuildThrow(Node* exception_value); |
| 356 | |
| 357 | // Builders for binary operations. |
| 358 | Node* BuildBinaryOp(Node* left, Node* right, Token::Value op, |
| 359 | TypeFeedbackId feedback_id); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 360 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 361 | // Process arguments to a call by popping {arity} elements off the operand |
| 362 | // stack and build a call node using the given call operator. |
| 363 | Node* ProcessArguments(const Operator* op, int arity); |
| 364 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 365 | // =========================================================================== |
| 366 | // The following build methods have the same contract as the above ones, but |
| 367 | // they can also return {nullptr} to indicate that no fragment was built. Note |
| 368 | // that these are optimizations, disabling any of them should still produce |
| 369 | // correct graphs. |
| 370 | |
| 371 | // Optimization for variable load from global object. |
| 372 | Node* TryLoadGlobalConstant(Handle<Name> name); |
| 373 | |
| 374 | // Optimization for variable load of dynamic lookup slot that is most likely |
| 375 | // to resolve to a global slot or context slot (inferred from scope chain). |
| 376 | Node* TryLoadDynamicVariable(Variable* variable, Handle<String> name, |
| 377 | BailoutId bailout_id, |
| 378 | FrameStateBeforeAndAfter& states, |
| 379 | const VectorSlotPair& feedback, |
| 380 | OutputFrameStateCombine combine, |
| 381 | TypeofMode typeof_mode); |
| 382 | |
| 383 | // Optimizations for automatic type conversion. |
| 384 | Node* TryFastToBoolean(Node* input); |
| 385 | Node* TryFastToName(Node* input); |
| 386 | |
| 387 | // =========================================================================== |
| 388 | // The following visitation methods all recursively visit a subtree of the |
| 389 | // underlying AST and extent the graph. The operand stack is mutated in a way |
| 390 | // consistent with other compilers: |
| 391 | // - Expressions pop operands and push result, depending on {AstContext}. |
| 392 | // - Statements keep the operand stack balanced. |
| 393 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 394 | // Visit statements. |
| 395 | void VisitIfNotNull(Statement* stmt); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 396 | void VisitInScope(Statement* stmt, Scope* scope, Node* context); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 397 | |
| 398 | // Visit expressions. |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 399 | void Visit(Expression* expr); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 400 | void VisitForTest(Expression* expr); |
| 401 | void VisitForEffect(Expression* expr); |
| 402 | void VisitForValue(Expression* expr); |
| 403 | void VisitForValueOrNull(Expression* expr); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 404 | void VisitForValueOrTheHole(Expression* expr); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 405 | void VisitForValues(ZoneList<Expression*>* exprs); |
| 406 | |
| 407 | // Common for all IterationStatement bodies. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 408 | void VisitIterationBody(IterationStatement* stmt, LoopBuilder* loop); |
| 409 | |
| 410 | // Dispatched from VisitCall. |
| 411 | void VisitCallSuper(Call* expr); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 412 | |
| 413 | // Dispatched from VisitCallRuntime. |
| 414 | void VisitCallJSRuntime(CallRuntime* expr); |
| 415 | |
| 416 | // Dispatched from VisitUnaryOperation. |
| 417 | void VisitDelete(UnaryOperation* expr); |
| 418 | void VisitVoid(UnaryOperation* expr); |
| 419 | void VisitTypeof(UnaryOperation* expr); |
| 420 | void VisitNot(UnaryOperation* expr); |
| 421 | |
| 422 | // Dispatched from VisitBinaryOperation. |
| 423 | void VisitComma(BinaryOperation* expr); |
| 424 | void VisitLogicalExpression(BinaryOperation* expr); |
| 425 | void VisitArithmeticExpression(BinaryOperation* expr); |
| 426 | |
| 427 | // Dispatched from VisitForInStatement. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 428 | void VisitForInAssignment(Expression* expr, Node* value, |
| 429 | const VectorSlotPair& feedback, |
| 430 | BailoutId bailout_id_before, |
| 431 | BailoutId bailout_id_after); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 432 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 433 | // Dispatched from VisitObjectLiteral. |
| 434 | void VisitObjectLiteralAccessor(Node* home_object, |
| 435 | ObjectLiteralProperty* property); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 436 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 437 | // Dispatched from VisitClassLiteral. |
| 438 | void VisitClassLiteralContents(ClassLiteral* expr); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 439 | |
| 440 | DEFINE_AST_VISITOR_SUBCLASS_MEMBERS(); |
| 441 | DISALLOW_COPY_AND_ASSIGN(AstGraphBuilder); |
| 442 | }; |
| 443 | |
| 444 | |
| 445 | // The abstract execution environment for generated code consists of |
| 446 | // parameter variables, local variables and the operand stack. The |
| 447 | // environment will perform proper SSA-renaming of all tracked nodes |
| 448 | // at split and merge points in the control flow. Internally all the |
| 449 | // values are stored in one list using the following layout: |
| 450 | // |
| 451 | // [parameters (+receiver)] [locals] [operand stack] |
| 452 | // |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 453 | class AstGraphBuilder::Environment : public ZoneObject { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 454 | public: |
| 455 | Environment(AstGraphBuilder* builder, Scope* scope, Node* control_dependency); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 456 | |
| 457 | int parameters_count() const { return parameters_count_; } |
| 458 | int locals_count() const { return locals_count_; } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 459 | int context_chain_length() { return static_cast<int>(contexts_.size()); } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 460 | int stack_height() { |
| 461 | return static_cast<int>(values()->size()) - parameters_count_ - |
| 462 | locals_count_; |
| 463 | } |
| 464 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 465 | // Operations on parameter or local variables. |
| 466 | void Bind(Variable* variable, Node* node); |
| 467 | Node* Lookup(Variable* variable); |
| 468 | void MarkAllLocalsLive(); |
| 469 | |
| 470 | // Raw operations on parameter variables. |
| 471 | void RawParameterBind(int index, Node* node); |
| 472 | Node* RawParameterLookup(int index); |
| 473 | |
| 474 | // Operations on the context chain. |
| 475 | Node* Context() const { return contexts_.back(); } |
| 476 | void PushContext(Node* context) { contexts()->push_back(context); } |
| 477 | void PopContext() { contexts()->pop_back(); } |
| 478 | void TrimContextChain(int trim_to_length) { |
| 479 | contexts()->resize(trim_to_length); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 480 | } |
| 481 | |
| 482 | // Operations on the operand stack. |
| 483 | void Push(Node* node) { |
| 484 | values()->push_back(node); |
| 485 | } |
| 486 | Node* Top() { |
| 487 | DCHECK(stack_height() > 0); |
| 488 | return values()->back(); |
| 489 | } |
| 490 | Node* Pop() { |
| 491 | DCHECK(stack_height() > 0); |
| 492 | Node* back = values()->back(); |
| 493 | values()->pop_back(); |
| 494 | return back; |
| 495 | } |
| 496 | |
| 497 | // Direct mutations of the operand stack. |
| 498 | void Poke(int depth, Node* node) { |
| 499 | DCHECK(depth >= 0 && depth < stack_height()); |
| 500 | int index = static_cast<int>(values()->size()) - depth - 1; |
| 501 | values()->at(index) = node; |
| 502 | } |
| 503 | Node* Peek(int depth) { |
| 504 | DCHECK(depth >= 0 && depth < stack_height()); |
| 505 | int index = static_cast<int>(values()->size()) - depth - 1; |
| 506 | return values()->at(index); |
| 507 | } |
| 508 | void Drop(int depth) { |
| 509 | DCHECK(depth >= 0 && depth <= stack_height()); |
| 510 | values()->erase(values()->end() - depth, values()->end()); |
| 511 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 512 | void TrimStack(int trim_to_height) { |
| 513 | int depth = stack_height() - trim_to_height; |
| 514 | DCHECK(depth >= 0 && depth <= stack_height()); |
| 515 | values()->erase(values()->end() - depth, values()->end()); |
| 516 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 517 | |
| 518 | // Preserve a checkpoint of the environment for the IR graph. Any |
| 519 | // further mutation of the environment will not affect checkpoints. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 520 | Node* Checkpoint(BailoutId ast_id, OutputFrameStateCombine combine = |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 521 | OutputFrameStateCombine::Ignore(), |
| 522 | bool node_has_exception = false); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 523 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 524 | // Control dependency tracked by this environment. |
| 525 | Node* GetControlDependency() { return control_dependency_; } |
| 526 | void UpdateControlDependency(Node* dependency) { |
| 527 | control_dependency_ = dependency; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 528 | } |
| 529 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 530 | // Effect dependency tracked by this environment. |
| 531 | Node* GetEffectDependency() { return effect_dependency_; } |
| 532 | void UpdateEffectDependency(Node* dependency) { |
| 533 | effect_dependency_ = dependency; |
| 534 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 535 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 536 | // Mark this environment as being unreachable. |
| 537 | void MarkAsUnreachable() { |
| 538 | UpdateControlDependency(builder()->jsgraph()->Dead()); |
| 539 | liveness_block_ = nullptr; |
| 540 | } |
| 541 | bool IsMarkedAsUnreachable() { |
| 542 | return GetControlDependency()->opcode() == IrOpcode::kDead; |
| 543 | } |
| 544 | |
| 545 | // Merge another environment into this one. |
| 546 | void Merge(Environment* other); |
| 547 | |
| 548 | // Copies this environment at a control-flow split point. |
| 549 | Environment* CopyForConditional(); |
| 550 | |
| 551 | // Copies this environment to a potentially unreachable control-flow point. |
| 552 | Environment* CopyAsUnreachable(); |
| 553 | |
| 554 | // Copies this environment at a loop header control-flow point. |
| 555 | Environment* CopyForLoop(BitVector* assigned, bool is_osr = false); |
| 556 | |
| 557 | private: |
| 558 | AstGraphBuilder* builder_; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 559 | int parameters_count_; |
| 560 | int locals_count_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 561 | LivenessAnalyzerBlock* liveness_block_; |
| 562 | NodeVector values_; |
| 563 | NodeVector contexts_; |
| 564 | Node* control_dependency_; |
| 565 | Node* effect_dependency_; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 566 | Node* parameters_node_; |
| 567 | Node* locals_node_; |
| 568 | Node* stack_node_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 569 | |
| 570 | explicit Environment(Environment* copy, |
| 571 | LivenessAnalyzerBlock* liveness_block); |
| 572 | Environment* CopyAndShareLiveness(); |
| 573 | void UpdateStateValues(Node** state_values, int offset, int count); |
| 574 | void UpdateStateValuesWithCache(Node** state_values, int offset, int count); |
| 575 | Zone* zone() const { return builder_->local_zone(); } |
| 576 | Graph* graph() const { return builder_->graph(); } |
| 577 | AstGraphBuilder* builder() const { return builder_; } |
| 578 | CommonOperatorBuilder* common() { return builder_->common(); } |
| 579 | NodeVector* values() { return &values_; } |
| 580 | NodeVector* contexts() { return &contexts_; } |
| 581 | LivenessAnalyzerBlock* liveness_block() { return liveness_block_; } |
| 582 | bool IsLivenessAnalysisEnabled(); |
| 583 | bool IsLivenessBlockConsistent(); |
| 584 | |
| 585 | // Prepare environment to be used as loop header. |
| 586 | void PrepareForLoop(BitVector* assigned, bool is_osr = false); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 587 | }; |
| 588 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 589 | } // namespace compiler |
| 590 | } // namespace internal |
| 591 | } // namespace v8 |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 592 | |
| 593 | #endif // V8_COMPILER_AST_GRAPH_BUILDER_H_ |