Home | History | Annotate | Download | only in compiler 
      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_
    345