src/v8/src/compiler/graph-builder.h

   1 // Copyright 2013 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_GRAPH_BUILDER_H_
   6 #define V8_COMPILER_GRAPH_BUILDER_H_
   7
   8 #include "src/v8.h"
   9
  10 #include "src/allocation.h"
  11 #include "src/compiler/common-operator.h"
  12 #include "src/compiler/graph.h"
  13 #include "src/unique.h"
  14
  15 namespace v8 {
  16 namespace internal {
  17
  18 class BitVector;
  19
  20 namespace compiler {
  21
  22 class Node;
  23
  24 // A common base class for anything that creates nodes in a graph.
  25 class GraphBuilder {
  26  public:
  27   explicit GraphBuilder(Graph* graph) : graph_(graph) {}
  28   virtual ~GraphBuilder() {}
  29
  30   Node* NewNode(const Operator* op, bool incomplete = false) {
  31     return MakeNode(op, 0, static_cast<Node**>(NULL), incomplete);
  32   }
  33
  34   Node* NewNode(const Operator* op, Node* n1) {
  35     return MakeNode(op, 1, &n1, false);
  36   }
  37
  38   Node* NewNode(const Operator* op, Node* n1, Node* n2) {
  39     Node* buffer[] = {n1, n2};
  40     return MakeNode(op, arraysize(buffer), buffer, false);
  41   }
  42
  43   Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3) {
  44     Node* buffer[] = {n1, n2, n3};
  45     return MakeNode(op, arraysize(buffer), buffer, false);
  46   }
  47
  48   Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4) {
  49     Node* buffer[] = {n1, n2, n3, n4};
  50     return MakeNode(op, arraysize(buffer), buffer, false);
  51   }
  52
  53   Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
  54                 Node* n5) {
  55     Node* buffer[] = {n1, n2, n3, n4, n5};
  56     return MakeNode(op, arraysize(buffer), buffer, false);
  57   }
  58
  59   Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
  60                 Node* n5, Node* n6) {
  61     Node* nodes[] = {n1, n2, n3, n4, n5, n6};
  62     return MakeNode(op, arraysize(nodes), nodes, false);
  63   }
  64
  65   Node* NewNode(const Operator* op, int value_input_count, Node** value_inputs,
  66                 bool incomplete = false) {
  67     return MakeNode(op, value_input_count, value_inputs, incomplete);
  68   }
  69
  70   Graph* graph() const { return graph_; }
  71
  72  protected:
  73   // Base implementation used by all factory methods.
  74   virtual Node* MakeNode(const Operator* op, int value_input_count,
  75                          Node** value_inputs, bool incomplete) = 0;
  76
  77  private:
  78   Graph* graph_;
  79 };
  80
  81
  82 // The StructuredGraphBuilder produces a high-level IR graph. It is used as the
  83 // base class for concrete implementations (e.g the AstGraphBuilder or the
  84 // StubGraphBuilder).
  85 class StructuredGraphBuilder : public GraphBuilder {
  86  public:
  87   StructuredGraphBuilder(Zone* zone, Graph* graph,
  88                          CommonOperatorBuilder* common);
  89   virtual ~StructuredGraphBuilder() {}
  90
  91   // Creates a new Phi node having {count} input values.
  92   Node* NewPhi(int count, Node* input, Node* control);
  93   Node* NewEffectPhi(int count, Node* input, Node* control);
  94
  95   // Helpers for merging control, effect or value dependencies.
  96   Node* MergeControl(Node* control, Node* other);
  97   Node* MergeEffect(Node* value, Node* other, Node* control);
  98   Node* MergeValue(Node* value, Node* other, Node* control);
  99
 100   // Helpers to create new control nodes.
 101   Node* NewIfTrue() { return NewNode(common()->IfTrue()); }
 102   Node* NewIfFalse() { return NewNode(common()->IfFalse()); }
 103   Node* NewMerge() { return NewNode(common()->Merge(1), true); }
 104   Node* NewLoop() { return NewNode(common()->Loop(1), true); }
 105   Node* NewBranch(Node* condition, BranchHint hint = BranchHint::kNone) {
 106     return NewNode(common()->Branch(hint), condition);
 107   }
 108
 109  protected:
 110   class Environment;
 111   friend class Environment;
 112   friend class ControlBuilder;
 113
 114   // The following method creates a new node having the specified operator and
 115   // ensures effect and control dependencies are wired up. The dependencies
 116   // tracked by the environment might be mutated.
 117   virtual Node* MakeNode(const Operator* op, int value_input_count,
 118                          Node** value_inputs, bool incomplete) FINAL;
 119
 120   Environment* environment() const { return environment_; }
 121   void set_environment(Environment* env) { environment_ = env; }
 122
 123   Node* current_context() const { return current_context_; }
 124   void set_current_context(Node* context) { current_context_ = context; }
 125
 126   Node* exit_control() const { return exit_control_; }
 127   void set_exit_control(Node* node) { exit_control_ = node; }
 128
 129   Node* dead_control();
 130
 131   Zone* graph_zone() const { return graph()->zone(); }
 132   Zone* local_zone() const { return local_zone_; }
 133   Isolate* isolate() const { return graph_zone()->isolate(); }
 134   CommonOperatorBuilder* common() const { return common_; }
 135
 136   // Helper to wrap a Handle<T> into a Unique<T>.
 137   template <class T>
 138   Unique<T> MakeUnique(Handle<T> object) {
 139     return Unique<T>::CreateUninitialized(object);
 140   }
 141
 142   // Support for control flow builders. The concrete type of the environment
 143   // depends on the graph builder, but environments themselves are not virtual.
 144   virtual Environment* CopyEnvironment(Environment* env);
 145
 146   // Helper to indicate a node exits the function body.
 147   void UpdateControlDependencyToLeaveFunction(Node* exit);
 148
 149  private:
 150   CommonOperatorBuilder* common_;
 151   Environment* environment_;
 152
 153   // Zone local to the builder for data not leaking into the graph.
 154   Zone* local_zone_;
 155
 156   // Temporary storage for building node input lists.
 157   int input_buffer_size_;
 158   Node** input_buffer_;
 159
 160   // Node representing the control dependency for dead code.
 161   SetOncePointer<Node> dead_control_;
 162
 163   // Node representing the current context within the function body.
 164   Node* current_context_;
 165
 166   // Merge of all control nodes that exit the function body.
 167   Node* exit_control_;
 168
 169   // Growth increment for the temporary buffer used to construct input lists to
 170   // new nodes.
 171   static const int kInputBufferSizeIncrement = 64;
 172
 173   Node** EnsureInputBufferSize(int size);
 174
 175   DISALLOW_COPY_AND_ASSIGN(StructuredGraphBuilder);
 176 };
 177
 178
 179 // The abstract execution environment contains static knowledge about
 180 // execution state at arbitrary control-flow points. It allows for
 181 // simulation of the control-flow at compile time.
 182 class StructuredGraphBuilder::Environment : public ZoneObject {
 183  public:
 184   Environment(StructuredGraphBuilder* builder, Node* control_dependency);
 185   Environment(const Environment& copy);
 186
 187   // Control dependency tracked by this environment.
 188   Node* GetControlDependency() { return control_dependency_; }
 189   void UpdateControlDependency(Node* dependency) {
 190     control_dependency_ = dependency;
 191   }
 192
 193   // Effect dependency tracked by this environment.
 194   Node* GetEffectDependency() { return effect_dependency_; }
 195   void UpdateEffectDependency(Node* dependency) {
 196     effect_dependency_ = dependency;
 197   }
 198
 199   // Mark this environment as being unreachable.
 200   void MarkAsUnreachable() {
 201     UpdateControlDependency(builder()->dead_control());
 202   }
 203   bool IsMarkedAsUnreachable() {
 204     return GetControlDependency()->opcode() == IrOpcode::kDead;
 205   }
 206
 207   // Merge another environment into this one.
 208   void Merge(Environment* other);
 209
 210   // Copies this environment at a control-flow split point.
 211   Environment* CopyForConditional() { return builder()->CopyEnvironment(this); }
 212
 213   // Copies this environment to a potentially unreachable control-flow point.
 214   Environment* CopyAsUnreachable() {
 215     Environment* env = builder()->CopyEnvironment(this);
 216     env->MarkAsUnreachable();
 217     return env;
 218   }
 219
 220   // Copies this environment at a loop header control-flow point.
 221   Environment* CopyForLoop(BitVector* assigned) {
 222     PrepareForLoop(assigned);
 223     return builder()->CopyEnvironment(this);
 224   }
 225
 226   Node* GetContext() { return builder_->current_context(); }
 227
 228  protected:
 229   Zone* zone() const { return builder_->local_zone(); }
 230   Graph* graph() const { return builder_->graph(); }
 231   StructuredGraphBuilder* builder() const { return builder_; }
 232   CommonOperatorBuilder* common() { return builder_->common(); }
 233   NodeVector* values() { return &values_; }
 234
 235   // Prepare environment to be used as loop header.
 236   void PrepareForLoop(BitVector* assigned);
 237
 238  private:
 239   StructuredGraphBuilder* builder_;
 240   Node* control_dependency_;
 241   Node* effect_dependency_;
 242   NodeVector values_;
 243 };
 244 }
 245 }
 246 }  // namespace v8::internal::compiler
 247
 248 #endif  // V8_COMPILER_GRAPH_BUILDER_H__