Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame^] | 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__ |