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