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