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