Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 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.h" |
| 9 | #include "src/compiler/bytecode-branch-analysis.h" |
| 10 | #include "src/compiler/js-graph.h" |
| 11 | #include "src/interpreter/bytecode-array-iterator.h" |
| 12 | #include "src/interpreter/bytecodes.h" |
| 13 | |
| 14 | namespace v8 { |
| 15 | namespace internal { |
| 16 | namespace compiler { |
| 17 | |
| 18 | // The BytecodeGraphBuilder produces a high-level IR graph based on |
| 19 | // interpreter bytecodes. |
| 20 | class BytecodeGraphBuilder { |
| 21 | public: |
| 22 | BytecodeGraphBuilder(Zone* local_zone, CompilationInfo* info, |
| 23 | JSGraph* jsgraph); |
| 24 | |
| 25 | // Creates a graph by visiting bytecodes. |
| 26 | bool CreateGraph(bool stack_check = true); |
| 27 | |
| 28 | Graph* graph() const { return jsgraph_->graph(); } |
| 29 | |
| 30 | private: |
| 31 | class Environment; |
| 32 | class FrameStateBeforeAndAfter; |
| 33 | |
| 34 | void CreateGraphBody(bool stack_check); |
| 35 | void VisitBytecodes(); |
| 36 | |
| 37 | Node* LoadAccumulator(Node* value); |
| 38 | |
| 39 | // Get or create the node that represents the outer function closure. |
| 40 | Node* GetFunctionClosure(); |
| 41 | |
| 42 | // Get or create the node that represents the outer function context. |
| 43 | Node* GetFunctionContext(); |
| 44 | |
| 45 | // Get or create the node that represents the incoming new target value. |
| 46 | Node* GetNewTarget(); |
| 47 | |
| 48 | // Builder for accessing a (potentially immutable) object field. |
| 49 | Node* BuildLoadObjectField(Node* object, int offset); |
| 50 | Node* BuildLoadImmutableObjectField(Node* object, int offset); |
| 51 | |
| 52 | // Builder for accessing type feedback vector. |
| 53 | Node* BuildLoadFeedbackVector(); |
| 54 | |
| 55 | // Builder for loading the a native context field. |
| 56 | Node* BuildLoadNativeContextField(int index); |
| 57 | |
| 58 | // Helper function for creating a pair containing type feedback vector and |
| 59 | // a feedback slot. |
| 60 | VectorSlotPair CreateVectorSlotPair(int slot_id); |
| 61 | |
| 62 | void set_environment(Environment* env) { environment_ = env; } |
| 63 | const Environment* environment() const { return environment_; } |
| 64 | Environment* environment() { return environment_; } |
| 65 | |
| 66 | // Node creation helpers |
| 67 | Node* NewNode(const Operator* op, bool incomplete = false) { |
| 68 | return MakeNode(op, 0, static_cast<Node**>(nullptr), incomplete); |
| 69 | } |
| 70 | |
| 71 | Node* NewNode(const Operator* op, Node* n1) { |
| 72 | Node* buffer[] = {n1}; |
| 73 | return MakeNode(op, arraysize(buffer), buffer, false); |
| 74 | } |
| 75 | |
| 76 | Node* NewNode(const Operator* op, Node* n1, Node* n2) { |
| 77 | Node* buffer[] = {n1, n2}; |
| 78 | return MakeNode(op, arraysize(buffer), buffer, false); |
| 79 | } |
| 80 | |
| 81 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3) { |
| 82 | Node* buffer[] = {n1, n2, n3}; |
| 83 | return MakeNode(op, arraysize(buffer), buffer, false); |
| 84 | } |
| 85 | |
| 86 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4) { |
| 87 | Node* buffer[] = {n1, n2, n3, n4}; |
| 88 | return MakeNode(op, arraysize(buffer), buffer, false); |
| 89 | } |
| 90 | |
| 91 | // Helpers to create new control nodes. |
| 92 | Node* NewIfTrue() { return NewNode(common()->IfTrue()); } |
| 93 | Node* NewIfFalse() { return NewNode(common()->IfFalse()); } |
| 94 | Node* NewMerge() { return NewNode(common()->Merge(1), true); } |
| 95 | Node* NewLoop() { return NewNode(common()->Loop(1), true); } |
| 96 | Node* NewBranch(Node* condition, BranchHint hint = BranchHint::kNone) { |
| 97 | return NewNode(common()->Branch(hint), condition); |
| 98 | } |
| 99 | |
| 100 | // Creates a new Phi node having {count} input values. |
| 101 | Node* NewPhi(int count, Node* input, Node* control); |
| 102 | Node* NewEffectPhi(int count, Node* input, Node* control); |
| 103 | |
| 104 | // Helpers for merging control, effect or value dependencies. |
| 105 | Node* MergeControl(Node* control, Node* other); |
| 106 | Node* MergeEffect(Node* effect, Node* other_effect, Node* control); |
| 107 | Node* MergeValue(Node* value, Node* other_value, Node* control); |
| 108 | |
| 109 | // The main node creation chokepoint. Adds context, frame state, effect, |
| 110 | // and control dependencies depending on the operator. |
| 111 | Node* MakeNode(const Operator* op, int value_input_count, Node** value_inputs, |
| 112 | bool incomplete); |
| 113 | |
| 114 | // Helper to indicate a node exits the function body. |
| 115 | void UpdateControlDependencyToLeaveFunction(Node* exit); |
| 116 | |
| 117 | Node** EnsureInputBufferSize(int size); |
| 118 | |
| 119 | Node* ProcessCallArguments(const Operator* call_op, Node* callee, |
| 120 | interpreter::Register receiver, size_t arity); |
| 121 | Node* ProcessCallNewArguments(const Operator* call_new_op, |
| 122 | interpreter::Register callee, |
| 123 | interpreter::Register first_arg, size_t arity); |
| 124 | Node* ProcessCallRuntimeArguments(const Operator* call_runtime_op, |
| 125 | interpreter::Register first_arg, |
| 126 | size_t arity); |
| 127 | |
| 128 | void BuildCreateLiteral(const Operator* op, |
| 129 | const interpreter::BytecodeArrayIterator& iterator); |
| 130 | void BuildCreateRegExpLiteral( |
| 131 | const interpreter::BytecodeArrayIterator& iterator); |
| 132 | void BuildCreateArrayLiteral( |
| 133 | const interpreter::BytecodeArrayIterator& iterator); |
| 134 | void BuildCreateObjectLiteral( |
| 135 | const interpreter::BytecodeArrayIterator& iterator); |
| 136 | void BuildCreateArguments(CreateArgumentsParameters::Type type, |
| 137 | const interpreter::BytecodeArrayIterator& iterator); |
| 138 | void BuildLoadGlobal(const interpreter::BytecodeArrayIterator& iterator, |
| 139 | TypeofMode typeof_mode); |
| 140 | void BuildStoreGlobal(const interpreter::BytecodeArrayIterator& iterator); |
| 141 | void BuildNamedLoad(const interpreter::BytecodeArrayIterator& iterator); |
| 142 | void BuildKeyedLoad(const interpreter::BytecodeArrayIterator& iterator); |
| 143 | void BuildNamedStore(const interpreter::BytecodeArrayIterator& iterator); |
| 144 | void BuildKeyedStore(const interpreter::BytecodeArrayIterator& iterator); |
| 145 | void BuildLdaLookupSlot(TypeofMode typeof_mode, |
| 146 | const interpreter::BytecodeArrayIterator& iterator); |
| 147 | void BuildStaLookupSlot(LanguageMode language_mode, |
| 148 | const interpreter::BytecodeArrayIterator& iterator); |
| 149 | void BuildCall(const interpreter::BytecodeArrayIterator& iterator); |
| 150 | void BuildBinaryOp(const Operator* op, |
| 151 | const interpreter::BytecodeArrayIterator& iterator); |
| 152 | void BuildCompareOp(const Operator* op, |
| 153 | const interpreter::BytecodeArrayIterator& iterator); |
| 154 | void BuildDelete(const interpreter::BytecodeArrayIterator& iterator); |
| 155 | void BuildCastOperator(const Operator* js_op, |
| 156 | const interpreter::BytecodeArrayIterator& iterator); |
| 157 | |
| 158 | // Control flow plumbing. |
| 159 | void BuildJump(int source_offset, int target_offset); |
| 160 | void BuildJump(); |
| 161 | void BuildConditionalJump(Node* condition); |
| 162 | void BuildJumpIfEqual(Node* comperand); |
| 163 | void BuildJumpIfToBooleanEqual(Node* boolean_comperand); |
| 164 | |
| 165 | // Constructing merge and loop headers. |
| 166 | void MergeEnvironmentsOfBackwardBranches(int source_offset, |
| 167 | int target_offset); |
| 168 | void MergeEnvironmentsOfForwardBranches(int source_offset); |
| 169 | void BuildLoopHeaderForBackwardBranches(int source_offset); |
| 170 | |
| 171 | // Attaches a frame state to |node| for the entry to the function. |
| 172 | void PrepareEntryFrameState(Node* node); |
| 173 | |
| 174 | // Growth increment for the temporary buffer used to construct input lists to |
| 175 | // new nodes. |
| 176 | static const int kInputBufferSizeIncrement = 64; |
| 177 | |
| 178 | // Field accessors |
| 179 | CommonOperatorBuilder* common() const { return jsgraph_->common(); } |
| 180 | Zone* graph_zone() const { return graph()->zone(); } |
| 181 | CompilationInfo* info() const { return info_; } |
| 182 | JSGraph* jsgraph() const { return jsgraph_; } |
| 183 | JSOperatorBuilder* javascript() const { return jsgraph_->javascript(); } |
| 184 | Zone* local_zone() const { return local_zone_; } |
| 185 | const Handle<BytecodeArray>& bytecode_array() const { |
| 186 | return bytecode_array_; |
| 187 | } |
| 188 | const FrameStateFunctionInfo* frame_state_function_info() const { |
| 189 | return frame_state_function_info_; |
| 190 | } |
| 191 | |
| 192 | LanguageMode language_mode() const { |
| 193 | // TODO(mythria): Don't rely on parse information to get language mode. |
| 194 | return info()->language_mode(); |
| 195 | } |
| 196 | |
| 197 | const interpreter::BytecodeArrayIterator* bytecode_iterator() const { |
| 198 | return bytecode_iterator_; |
| 199 | } |
| 200 | |
| 201 | void set_bytecode_iterator( |
| 202 | const interpreter::BytecodeArrayIterator* bytecode_iterator) { |
| 203 | bytecode_iterator_ = bytecode_iterator; |
| 204 | } |
| 205 | |
| 206 | const BytecodeBranchAnalysis* branch_analysis() const { |
| 207 | return branch_analysis_; |
| 208 | } |
| 209 | |
| 210 | void set_branch_analysis(const BytecodeBranchAnalysis* branch_analysis) { |
| 211 | branch_analysis_ = branch_analysis; |
| 212 | } |
| 213 | |
| 214 | #define DECLARE_VISIT_BYTECODE(name, ...) \ |
| 215 | void Visit##name(const interpreter::BytecodeArrayIterator& iterator); |
| 216 | BYTECODE_LIST(DECLARE_VISIT_BYTECODE) |
| 217 | #undef DECLARE_VISIT_BYTECODE |
| 218 | |
| 219 | Zone* local_zone_; |
| 220 | CompilationInfo* info_; |
| 221 | JSGraph* jsgraph_; |
| 222 | Handle<BytecodeArray> bytecode_array_; |
| 223 | const FrameStateFunctionInfo* frame_state_function_info_; |
| 224 | const interpreter::BytecodeArrayIterator* bytecode_iterator_; |
| 225 | const BytecodeBranchAnalysis* branch_analysis_; |
| 226 | Environment* environment_; |
| 227 | |
| 228 | |
| 229 | // Merge environments are snapshots of the environment at a particular |
| 230 | // bytecode offset to be merged into a later environment. |
| 231 | ZoneMap<int, Environment*> merge_environments_; |
| 232 | |
| 233 | // Loop header environments are environments created for bytecodes |
| 234 | // where it is known there are back branches, ie a loop header. |
| 235 | ZoneMap<int, Environment*> loop_header_environments_; |
| 236 | |
| 237 | // Temporary storage for building node input lists. |
| 238 | int input_buffer_size_; |
| 239 | Node** input_buffer_; |
| 240 | |
| 241 | // Nodes representing values in the activation record. |
| 242 | SetOncePointer<Node> function_context_; |
| 243 | SetOncePointer<Node> function_closure_; |
| 244 | SetOncePointer<Node> new_target_; |
| 245 | |
| 246 | // Optimization to cache loaded feedback vector. |
| 247 | SetOncePointer<Node> feedback_vector_; |
| 248 | |
| 249 | // Control nodes that exit the function body. |
| 250 | ZoneVector<Node*> exit_controls_; |
| 251 | |
| 252 | DISALLOW_COPY_AND_ASSIGN(BytecodeGraphBuilder); |
| 253 | }; |
| 254 | |
| 255 | |
| 256 | class BytecodeGraphBuilder::Environment : public ZoneObject { |
| 257 | public: |
| 258 | Environment(BytecodeGraphBuilder* builder, int register_count, |
| 259 | int parameter_count, Node* control_dependency, Node* context); |
| 260 | |
| 261 | int parameter_count() const { return parameter_count_; } |
| 262 | int register_count() const { return register_count_; } |
| 263 | |
| 264 | Node* LookupAccumulator() const; |
| 265 | Node* LookupRegister(interpreter::Register the_register) const; |
| 266 | |
| 267 | void ExchangeRegisters(interpreter::Register reg0, |
| 268 | interpreter::Register reg1); |
| 269 | |
| 270 | void BindAccumulator(Node* node, FrameStateBeforeAndAfter* states = nullptr); |
| 271 | void BindRegister(interpreter::Register the_register, Node* node, |
| 272 | FrameStateBeforeAndAfter* states = nullptr); |
| 273 | void BindRegistersToProjections(interpreter::Register first_reg, Node* node, |
| 274 | FrameStateBeforeAndAfter* states = nullptr); |
| 275 | void RecordAfterState(Node* node, FrameStateBeforeAndAfter* states); |
| 276 | |
| 277 | bool IsMarkedAsUnreachable() const; |
| 278 | void MarkAsUnreachable(); |
| 279 | |
| 280 | // Effect dependency tracked by this environment. |
| 281 | Node* GetEffectDependency() { return effect_dependency_; } |
| 282 | void UpdateEffectDependency(Node* dependency) { |
| 283 | effect_dependency_ = dependency; |
| 284 | } |
| 285 | |
| 286 | // Preserve a checkpoint of the environment for the IR graph. Any |
| 287 | // further mutation of the environment will not affect checkpoints. |
| 288 | Node* Checkpoint(BailoutId bytecode_offset, OutputFrameStateCombine combine); |
| 289 | |
| 290 | // Returns true if the state values are up to date with the current |
| 291 | // environment. |
| 292 | bool StateValuesAreUpToDate(int output_poke_offset, int output_poke_count); |
| 293 | |
| 294 | // Control dependency tracked by this environment. |
| 295 | Node* GetControlDependency() const { return control_dependency_; } |
| 296 | void UpdateControlDependency(Node* dependency) { |
| 297 | control_dependency_ = dependency; |
| 298 | } |
| 299 | |
| 300 | Node* Context() const { return context_; } |
| 301 | void SetContext(Node* new_context) { context_ = new_context; } |
| 302 | |
| 303 | Environment* CopyForConditional() const; |
| 304 | Environment* CopyForLoop(); |
| 305 | void Merge(Environment* other); |
| 306 | |
| 307 | private: |
| 308 | explicit Environment(const Environment* copy); |
| 309 | void PrepareForLoop(); |
| 310 | bool StateValuesAreUpToDate(Node** state_values, int offset, int count, |
| 311 | int output_poke_start, int output_poke_end); |
| 312 | bool StateValuesRequireUpdate(Node** state_values, int offset, int count); |
| 313 | void UpdateStateValues(Node** state_values, int offset, int count); |
| 314 | |
| 315 | int RegisterToValuesIndex(interpreter::Register the_register) const; |
| 316 | |
| 317 | Zone* zone() const { return builder_->local_zone(); } |
| 318 | Graph* graph() const { return builder_->graph(); } |
| 319 | CommonOperatorBuilder* common() const { return builder_->common(); } |
| 320 | BytecodeGraphBuilder* builder() const { return builder_; } |
| 321 | const NodeVector* values() const { return &values_; } |
| 322 | NodeVector* values() { return &values_; } |
| 323 | int register_base() const { return register_base_; } |
| 324 | int accumulator_base() const { return accumulator_base_; } |
| 325 | |
| 326 | BytecodeGraphBuilder* builder_; |
| 327 | int register_count_; |
| 328 | int parameter_count_; |
| 329 | Node* context_; |
| 330 | Node* control_dependency_; |
| 331 | Node* effect_dependency_; |
| 332 | NodeVector values_; |
| 333 | Node* parameters_state_values_; |
| 334 | Node* registers_state_values_; |
| 335 | Node* accumulator_state_values_; |
| 336 | int register_base_; |
| 337 | int accumulator_base_; |
| 338 | }; |
| 339 | |
| 340 | } // namespace compiler |
| 341 | } // namespace internal |
| 342 | } // namespace v8 |
| 343 | |
| 344 | #endif // V8_COMPILER_BYTECODE_GRAPH_BUILDER_H_ |