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
15namespace v8 {
16namespace internal {
17namespace compiler {
18
19class Node;
20
21// A common base class for anything that creates nodes in a graph.
22class 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).
80class 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.
163class 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__
231