1 // Copyright 2015 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_BYTECODE_GRAPH_BUILDER_H_ 6 #define V8_COMPILER_BYTECODE_GRAPH_BUILDER_H_ 7 8 #include "src/compiler/bytecode-analysis.h" 9 #include "src/compiler/js-graph.h" 10 #include "src/compiler/liveness-analyzer.h" 11 #include "src/compiler/state-values-utils.h" 12 #include "src/interpreter/bytecode-array-iterator.h" 13 #include "src/interpreter/bytecode-flags.h" 14 #include "src/interpreter/bytecodes.h" 15 #include "src/source-position-table.h" 16 17 namespace v8 { 18 namespace internal { 19 namespace compiler { 20 21 class SourcePositionTable; 22 23 // The BytecodeGraphBuilder produces a high-level IR graph based on 24 // interpreter bytecodes. 25 class BytecodeGraphBuilder { 26 public: 27 BytecodeGraphBuilder(Zone* local_zone, Handle<SharedFunctionInfo> shared, 28 Handle<FeedbackVector> feedback_vector, 29 BailoutId osr_ast_id, JSGraph* jsgraph, 30 float invocation_frequency, 31 SourcePositionTable* source_positions, 32 int inlining_id = SourcePosition::kNotInlined); 33 34 // Creates a graph by visiting bytecodes. 35 bool CreateGraph(bool stack_check = true); 36 37 private: 38 class Environment; 39 40 void VisitBytecodes(bool stack_check); 41 42 // Get or create the node that represents the outer function closure. 43 Node* GetFunctionClosure(); 44 45 // Get or create the node that represents the outer function context. 46 Node* GetFunctionContext(); 47 48 // Get or create the node that represents the incoming new target value. 49 Node* GetNewTarget(); 50 51 // Builder for loading the a native context field. 52 Node* BuildLoadNativeContextField(int index); 53 54 // Helper function for creating a pair containing type feedback vector and 55 // a feedback slot. 56 VectorSlotPair CreateVectorSlotPair(int slot_id); 57 58 void set_environment(Environment* env) { environment_ = env; } 59 const Environment* environment() const { return environment_; } 60 Environment* environment() { return environment_; } 61 62 // Node creation helpers 63 Node* NewNode(const Operator* op, bool incomplete = false) { 64 return MakeNode(op, 0, static_cast<Node**>(nullptr), incomplete); 65 } 66 67 Node* NewNode(const Operator* op, Node* n1) { 68 Node* buffer[] = {n1}; 69 return MakeNode(op, arraysize(buffer), buffer, false); 70 } 71 72 Node* NewNode(const Operator* op, Node* n1, Node* n2) { 73 Node* buffer[] = {n1, n2}; 74 return MakeNode(op, arraysize(buffer), buffer, false); 75 } 76 77 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3) { 78 Node* buffer[] = {n1, n2, n3}; 79 return MakeNode(op, arraysize(buffer), buffer, false); 80 } 81 82 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4) { 83 Node* buffer[] = {n1, n2, n3, n4}; 84 return MakeNode(op, arraysize(buffer), buffer, false); 85 } 86 87 // Helpers to create new control nodes. 88 Node* NewIfTrue() { return NewNode(common()->IfTrue()); } 89 Node* NewIfFalse() { return NewNode(common()->IfFalse()); } 90 Node* NewMerge() { return NewNode(common()->Merge(1), true); } 91 Node* NewLoop() { return NewNode(common()->Loop(1), true); } 92 Node* NewBranch(Node* condition, BranchHint hint = BranchHint::kNone) { 93 return NewNode(common()->Branch(hint), condition); 94 } 95 96 // Creates a new Phi node having {count} input values. 97 Node* NewPhi(int count, Node* input, Node* control); 98 Node* NewEffectPhi(int count, Node* input, Node* control); 99 100 // Helpers for merging control, effect or value dependencies. 101 Node* MergeControl(Node* control, Node* other); 102 Node* MergeEffect(Node* effect, Node* other_effect, Node* control); 103 Node* MergeValue(Node* value, Node* other_value, Node* control); 104 105 // The main node creation chokepoint. Adds context, frame state, effect, 106 // and control dependencies depending on the operator. 107 Node* MakeNode(const Operator* op, int value_input_count, Node** value_inputs, 108 bool incomplete); 109 110 Node** EnsureInputBufferSize(int size); 111 112 Node* ProcessCallArguments(const Operator* call_op, Node* callee, 113 interpreter::Register receiver, size_t arity); 114 Node* ProcessConstructArguments(const Operator* call_new_op, Node* callee, 115 Node* new_target, 116 interpreter::Register first_arg, 117 size_t arity); 118 Node* ProcessConstructWithSpreadArguments(const Operator* op, Node* callee, 119 Node* new_target, 120 interpreter::Register first_arg, 121 size_t arity); 122 Node* ProcessCallRuntimeArguments(const Operator* call_runtime_op, 123 interpreter::Register first_arg, 124 size_t arity); 125 126 // Prepare information for eager deoptimization. This information is carried 127 // by dedicated {Checkpoint} nodes that are wired into the effect chain. 128 // Conceptually this frame state is "before" a given operation. 129 void PrepareEagerCheckpoint(); 130 131 // Prepare information for lazy deoptimization. This information is attached 132 // to the given node and the output value produced by the node is combined. 133 // Conceptually this frame state is "after" a given operation. 134 void PrepareFrameState(Node* node, OutputFrameStateCombine combine); 135 136 void BuildCreateArguments(CreateArgumentsType type); 137 Node* BuildLoadGlobal(Handle<Name> name, uint32_t feedback_slot_index, 138 TypeofMode typeof_mode); 139 void BuildStoreGlobal(LanguageMode language_mode); 140 141 enum class StoreMode { 142 // Check the prototype chain before storing. 143 kNormal, 144 // Store value to the receiver without checking the prototype chain. 145 kOwn, 146 }; 147 void BuildNamedStore(LanguageMode language_mode, StoreMode store_mode); 148 void BuildKeyedStore(LanguageMode language_mode); 149 void BuildLdaLookupSlot(TypeofMode typeof_mode); 150 void BuildLdaLookupContextSlot(TypeofMode typeof_mode); 151 void BuildLdaLookupGlobalSlot(TypeofMode typeof_mode); 152 void BuildStaLookupSlot(LanguageMode language_mode); 153 void BuildCall(TailCallMode tail_call_mode, 154 ConvertReceiverMode receiver_hint); 155 void BuildBinaryOp(const Operator* op); 156 void BuildBinaryOpWithImmediate(const Operator* op); 157 void BuildCompareOp(const Operator* op); 158 void BuildDelete(LanguageMode language_mode); 159 void BuildCastOperator(const Operator* op); 160 void BuildForInPrepare(); 161 void BuildForInNext(); 162 void BuildInvokeIntrinsic(); 163 164 // Optional early lowering to the simplified operator level. Returns the node 165 // representing the lowered operation or {nullptr} if no lowering available. 166 // Note that the result has already been wired into the environment just like 167 // any other invocation of {NewNode} would do. 168 Node* TryBuildSimplifiedBinaryOp(const Operator* op, Node* left, Node* right, 169 FeedbackSlot slot); 170 171 // Check the context chain for extensions, for lookup fast paths. 172 Environment* CheckContextExtensions(uint32_t depth); 173 174 // Helper function to create binary operation hint from the recorded 175 // type feedback. 176 BinaryOperationHint GetBinaryOperationHint(int operand_index); 177 178 // Helper function to create compare operation hint from the recorded 179 // type feedback. 180 CompareOperationHint GetCompareOperationHint(); 181 182 // Helper function to compute call frequency from the recorded type 183 // feedback. 184 float ComputeCallFrequency(int slot_id) const; 185 186 // Control flow plumbing. 187 void BuildJump(); 188 void BuildJumpIf(Node* condition); 189 void BuildJumpIfNot(Node* condition); 190 void BuildJumpIfEqual(Node* comperand); 191 void BuildJumpIfTrue(); 192 void BuildJumpIfFalse(); 193 void BuildJumpIfToBooleanTrue(); 194 void BuildJumpIfToBooleanFalse(); 195 void BuildJumpIfNotHole(); 196 void BuildJumpIfJSReceiver(); 197 198 // Simulates control flow by forward-propagating environments. 199 void MergeIntoSuccessorEnvironment(int target_offset); 200 void BuildLoopHeaderEnvironment(int current_offset); 201 void SwitchToMergeEnvironment(int current_offset); 202 203 // Simulates control flow that exits the function body. 204 void MergeControlToLeaveFunction(Node* exit); 205 206 // Builds entry points that are used by OSR deconstruction. 207 void BuildOSRLoopEntryPoint(int current_offset); 208 void BuildOSRNormalEntryPoint(); 209 210 // Builds loop exit nodes for every exited loop between the current bytecode 211 // offset and {target_offset}. 212 void BuildLoopExitsForBranch(int target_offset); 213 void BuildLoopExitsForFunctionExit(); 214 void BuildLoopExitsUntilLoop(int loop_offset); 215 216 // Simulates entry and exit of exception handlers. 217 void EnterAndExitExceptionHandlers(int current_offset); 218 219 // Update the current position of the {SourcePositionTable} to that of the 220 // bytecode at {offset}, if any. 221 void UpdateCurrentSourcePosition(SourcePositionTableIterator* it, int offset); 222 223 // Growth increment for the temporary buffer used to construct input lists to 224 // new nodes. 225 static const int kInputBufferSizeIncrement = 64; 226 227 // An abstract representation for an exception handler that is being 228 // entered and exited while the graph builder is iterating over the 229 // underlying bytecode. The exception handlers within the bytecode are 230 // well scoped, hence will form a stack during iteration. 231 struct ExceptionHandler { 232 int start_offset_; // Start offset of the handled area in the bytecode. 233 int end_offset_; // End offset of the handled area in the bytecode. 234 int handler_offset_; // Handler entry offset within the bytecode. 235 int context_register_; // Index of register holding handler context. 236 }; 237 238 // Field accessors 239 Graph* graph() const { return jsgraph_->graph(); } 240 CommonOperatorBuilder* common() const { return jsgraph_->common(); } 241 Zone* graph_zone() const { return graph()->zone(); } 242 JSGraph* jsgraph() const { return jsgraph_; } 243 JSOperatorBuilder* javascript() const { return jsgraph_->javascript(); } 244 SimplifiedOperatorBuilder* simplified() const { 245 return jsgraph_->simplified(); 246 } 247 Zone* local_zone() const { return local_zone_; } 248 const Handle<BytecodeArray>& bytecode_array() const { 249 return bytecode_array_; 250 } 251 const Handle<HandlerTable>& exception_handler_table() const { 252 return exception_handler_table_; 253 } 254 const Handle<FeedbackVector>& feedback_vector() const { 255 return feedback_vector_; 256 } 257 const FrameStateFunctionInfo* frame_state_function_info() const { 258 return frame_state_function_info_; 259 } 260 261 const interpreter::BytecodeArrayIterator& bytecode_iterator() const { 262 return *bytecode_iterator_; 263 } 264 265 void set_bytecode_iterator( 266 const interpreter::BytecodeArrayIterator* bytecode_iterator) { 267 bytecode_iterator_ = bytecode_iterator; 268 } 269 270 const BytecodeAnalysis* bytecode_analysis() const { 271 return bytecode_analysis_; 272 } 273 274 void set_bytecode_analysis(const BytecodeAnalysis* bytecode_analysis) { 275 bytecode_analysis_ = bytecode_analysis; 276 } 277 278 bool needs_eager_checkpoint() const { return needs_eager_checkpoint_; } 279 void mark_as_needing_eager_checkpoint(bool value) { 280 needs_eager_checkpoint_ = value; 281 } 282 283 #define DECLARE_VISIT_BYTECODE(name, ...) void Visit##name(); 284 BYTECODE_LIST(DECLARE_VISIT_BYTECODE) 285 #undef DECLARE_VISIT_BYTECODE 286 287 Zone* local_zone_; 288 JSGraph* jsgraph_; 289 float const invocation_frequency_; 290 Handle<BytecodeArray> bytecode_array_; 291 Handle<HandlerTable> exception_handler_table_; 292 Handle<FeedbackVector> feedback_vector_; 293 const FrameStateFunctionInfo* frame_state_function_info_; 294 const interpreter::BytecodeArrayIterator* bytecode_iterator_; 295 const BytecodeAnalysis* bytecode_analysis_; 296 Environment* environment_; 297 BailoutId osr_ast_id_; 298 int osr_loop_offset_; 299 300 // Merge environments are snapshots of the environment at points where the 301 // control flow merges. This models a forward data flow propagation of all 302 // values from all predecessors of the merge in question. 303 ZoneMap<int, Environment*> merge_environments_; 304 305 // Exception handlers currently entered by the iteration. 306 ZoneStack<ExceptionHandler> exception_handlers_; 307 int current_exception_handler_; 308 309 // Temporary storage for building node input lists. 310 int input_buffer_size_; 311 Node** input_buffer_; 312 313 // Optimization to only create checkpoints when the current position in the 314 // control-flow is not effect-dominated by another checkpoint already. All 315 // operations that do not have observable side-effects can be re-evaluated. 316 bool needs_eager_checkpoint_; 317 318 // Nodes representing values in the activation record. 319 SetOncePointer<Node> function_context_; 320 SetOncePointer<Node> function_closure_; 321 SetOncePointer<Node> new_target_; 322 323 // Control nodes that exit the function body. 324 ZoneVector<Node*> exit_controls_; 325 326 StateValuesCache state_values_cache_; 327 328 // The source position table, to be populated. 329 SourcePositionTable* source_positions_; 330 331 SourcePosition const start_position_; 332 333 static int const kBinaryOperationHintIndex = 1; 334 static int const kCountOperationHintIndex = 0; 335 static int const kBinaryOperationSmiHintIndex = 2; 336 337 DISALLOW_COPY_AND_ASSIGN(BytecodeGraphBuilder); 338 }; 339 340 } // namespace compiler 341 } // namespace internal 342 } // namespace v8 343 344 #endif // V8_COMPILER_BYTECODE_GRAPH_BUILDER_H_ 345
