OLD | NEW |
(Empty) | |
| 1 // Copyright 2014 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_STRUCTURED_MACHINE_ASSEMBLER_H_ |
| 6 #define V8_COMPILER_STRUCTURED_MACHINE_ASSEMBLER_H_ |
| 7 |
| 8 #include "src/v8.h" |
| 9 |
| 10 #include "src/compiler/common-operator.h" |
| 11 #include "src/compiler/graph-builder.h" |
| 12 #include "src/compiler/machine-node-factory.h" |
| 13 #include "src/compiler/machine-operator.h" |
| 14 #include "src/compiler/node.h" |
| 15 #include "src/compiler/operator.h" |
| 16 |
| 17 |
| 18 namespace v8 { |
| 19 namespace internal { |
| 20 namespace compiler { |
| 21 |
| 22 class BasicBlock; |
| 23 class Schedule; |
| 24 class StructuredMachineAssembler; |
| 25 |
| 26 |
| 27 class Variable : public ZoneObject { |
| 28 public: |
| 29 Node* Get() const; |
| 30 void Set(Node* value) const; |
| 31 |
| 32 private: |
| 33 Variable(StructuredMachineAssembler* smasm, int offset) |
| 34 : smasm_(smasm), offset_(offset) {} |
| 35 |
| 36 friend class StructuredMachineAssembler; |
| 37 friend class StructuredMachineAssemblerFriend; |
| 38 StructuredMachineAssembler* const smasm_; |
| 39 const int offset_; |
| 40 }; |
| 41 |
| 42 |
| 43 class StructuredMachineAssembler |
| 44 : public GraphBuilder, |
| 45 public MachineNodeFactory<StructuredMachineAssembler> { |
| 46 public: |
| 47 class Environment : public ZoneObject { |
| 48 public: |
| 49 Environment(Zone* zone, BasicBlock* block, bool is_dead_); |
| 50 |
| 51 private: |
| 52 BasicBlock* block_; |
| 53 NodeVector variables_; |
| 54 bool is_dead_; |
| 55 friend class StructuredMachineAssembler; |
| 56 DISALLOW_COPY_AND_ASSIGN(Environment); |
| 57 }; |
| 58 |
| 59 class IfBuilder; |
| 60 friend class IfBuilder; |
| 61 class LoopBuilder; |
| 62 friend class LoopBuilder; |
| 63 |
| 64 StructuredMachineAssembler( |
| 65 Graph* graph, MachineCallDescriptorBuilder* call_descriptor_builder, |
| 66 MachineRepresentation word = MachineOperatorBuilder::pointer_rep()); |
| 67 virtual ~StructuredMachineAssembler() {} |
| 68 |
| 69 Isolate* isolate() const { return zone()->isolate(); } |
| 70 Zone* zone() const { return graph()->zone(); } |
| 71 MachineOperatorBuilder* machine() { return &machine_; } |
| 72 CommonOperatorBuilder* common() { return &common_; } |
| 73 CallDescriptor* call_descriptor() const { |
| 74 return call_descriptor_builder_->BuildCallDescriptor(zone()); |
| 75 } |
| 76 int parameter_count() const { |
| 77 return call_descriptor_builder_->parameter_count(); |
| 78 } |
| 79 const MachineRepresentation* parameter_types() const { |
| 80 return call_descriptor_builder_->parameter_types(); |
| 81 } |
| 82 |
| 83 // Parameters. |
| 84 Node* Parameter(int index); |
| 85 // Variables. |
| 86 Variable NewVariable(Node* initial_value); |
| 87 // Control flow. |
| 88 void Return(Node* value); |
| 89 |
| 90 // MachineAssembler is invalid after export. |
| 91 Schedule* Export(); |
| 92 |
| 93 protected: |
| 94 virtual Node* MakeNode(Operator* op, int input_count, Node** inputs); |
| 95 |
| 96 Schedule* schedule() { |
| 97 ASSERT(ScheduleValid()); |
| 98 return schedule_; |
| 99 } |
| 100 |
| 101 private: |
| 102 bool ScheduleValid() { return schedule_ != NULL; } |
| 103 |
| 104 typedef std::vector<Environment*, zone_allocator<Environment*> > |
| 105 EnvironmentVector; |
| 106 |
| 107 NodeVector* CurrentVars() { return ¤t_environment_->variables_; } |
| 108 Node*& VariableAt(Environment* environment, int offset); |
| 109 Node* GetVariable(int offset); |
| 110 void SetVariable(int offset, Node* value); |
| 111 |
| 112 void AddBranch(Environment* environment, Node* condition, |
| 113 Environment* true_val, Environment* false_val); |
| 114 void AddGoto(Environment* from, Environment* to); |
| 115 BasicBlock* TrampolineFor(BasicBlock* block); |
| 116 |
| 117 void CopyCurrentAsDead(); |
| 118 Environment* Copy(Environment* environment) { |
| 119 return Copy(environment, static_cast<int>(environment->variables_.size())); |
| 120 } |
| 121 Environment* Copy(Environment* environment, int truncate_at); |
| 122 void Merge(EnvironmentVector* environments, int truncate_at); |
| 123 Environment* CopyForLoopHeader(Environment* environment); |
| 124 void MergeBackEdgesToLoopHeader(Environment* header, |
| 125 EnvironmentVector* environments); |
| 126 |
| 127 typedef std::vector<MachineRepresentation, |
| 128 zone_allocator<MachineRepresentation> > |
| 129 RepresentationVector; |
| 130 |
| 131 Schedule* schedule_; |
| 132 MachineOperatorBuilder machine_; |
| 133 CommonOperatorBuilder common_; |
| 134 MachineCallDescriptorBuilder* call_descriptor_builder_; |
| 135 Node** parameters_; |
| 136 Environment* current_environment_; |
| 137 int number_of_variables_; |
| 138 |
| 139 friend class Variable; |
| 140 // For testing only. |
| 141 friend class StructuredMachineAssemblerFriend; |
| 142 DISALLOW_COPY_AND_ASSIGN(StructuredMachineAssembler); |
| 143 }; |
| 144 |
| 145 // IfBuilder constructs of nested if-else expressions which more or less follow |
| 146 // C semantics. Foe example: |
| 147 // |
| 148 // if (x) {do_x} else if (y) {do_y} else {do_z} |
| 149 // |
| 150 // would look like this: |
| 151 // |
| 152 // IfBuilder b; |
| 153 // b.If(x).Then(); |
| 154 // do_x |
| 155 // b.Else(); |
| 156 // b.If().Then(); |
| 157 // do_y |
| 158 // b.Else(); |
| 159 // do_z |
| 160 // b.End(); |
| 161 // |
| 162 // Then() and Else() can be skipped, representing an empty block in C. |
| 163 // Combinations like If(x).Then().If(x).Then() are legitimate, but |
| 164 // Else().Else() is not. That is, once you've nested an If(), you can't get to a |
| 165 // higher level If() branch. |
| 166 // TODO(dcarney): describe expressions once the api is finalized. |
| 167 class StructuredMachineAssembler::IfBuilder { |
| 168 public: |
| 169 explicit IfBuilder(StructuredMachineAssembler* smasm); |
| 170 ~IfBuilder() { |
| 171 if (!IsDone()) End(); |
| 172 } |
| 173 |
| 174 IfBuilder& If(); // TODO(dcarney): this should take an expression. |
| 175 IfBuilder& If(Node* condition); |
| 176 void Then(); |
| 177 void Else(); |
| 178 void End(); |
| 179 |
| 180 // The next 4 functions are exposed for expression support. |
| 181 // They will be private once I have a nice expression api. |
| 182 void And(); |
| 183 void Or(); |
| 184 IfBuilder& OpenParen() { |
| 185 ASSERT(smasm_->current_environment_ != NULL); |
| 186 CurrentClause()->PushNewExpressionState(); |
| 187 return *this; |
| 188 } |
| 189 IfBuilder& CloseParen() { |
| 190 ASSERT(smasm_->current_environment_ == NULL); |
| 191 CurrentClause()->PopExpressionState(); |
| 192 return *this; |
| 193 } |
| 194 |
| 195 private: |
| 196 // UnresolvedBranch represents the chain of environments created while |
| 197 // generating an expression. At this point, a branch Node |
| 198 // cannot be created, as the target environments of the branch are not yet |
| 199 // available, so everything required to create the branch Node is |
| 200 // stored in this structure until the target environments are resolved. |
| 201 struct UnresolvedBranch : public ZoneObject { |
| 202 UnresolvedBranch(Environment* environment, Node* condition, |
| 203 UnresolvedBranch* next) |
| 204 : environment_(environment), condition_(condition), next_(next) {} |
| 205 // environment_ will eventually be terminated by a branch on condition_. |
| 206 Environment* environment_; |
| 207 Node* condition_; |
| 208 // next_ is the next link in the UnresolvedBranch chain, and will be |
| 209 // either the true or false branch jumped to from environment_. |
| 210 UnresolvedBranch* next_; |
| 211 }; |
| 212 |
| 213 struct ExpressionState { |
| 214 int pending_then_size_; |
| 215 int pending_else_size_; |
| 216 }; |
| 217 |
| 218 typedef std::vector<ExpressionState, zone_allocator<ExpressionState> > |
| 219 ExpressionStates; |
| 220 typedef std::vector<UnresolvedBranch*, zone_allocator<UnresolvedBranch*> > |
| 221 PendingMergeStack; |
| 222 struct IfClause; |
| 223 typedef std::vector<IfClause*, zone_allocator<IfClause*> > IfClauses; |
| 224 |
| 225 struct PendingMergeStackRange { |
| 226 PendingMergeStack* merge_stack_; |
| 227 int start_; |
| 228 int size_; |
| 229 }; |
| 230 |
| 231 enum CombineType { kCombineThen, kCombineElse }; |
| 232 enum ResolutionType { kExpressionTerm, kExpressionDone }; |
| 233 |
| 234 // IfClause represents one level of if-then-else nesting plus the associated |
| 235 // expression. |
| 236 // A call to If() triggers creation of a new nesting level after expression |
| 237 // creation is complete - ie Then() or Else() has been called. |
| 238 struct IfClause : public ZoneObject { |
| 239 IfClause(Zone* zone, int initial_environment_size); |
| 240 void CopyEnvironments(const PendingMergeStackRange& data, |
| 241 EnvironmentVector* environments); |
| 242 void ResolvePendingMerges(StructuredMachineAssembler* smasm, |
| 243 CombineType combine_type, |
| 244 ResolutionType resolution_type); |
| 245 PendingMergeStackRange ComputeRelevantMerges(CombineType combine_type); |
| 246 void FinalizeBranches(StructuredMachineAssembler* smasm, |
| 247 const PendingMergeStackRange& offset_data, |
| 248 CombineType combine_type, |
| 249 Environment* then_environment, |
| 250 Environment* else_environment); |
| 251 void PushNewExpressionState(); |
| 252 void PopExpressionState(); |
| 253 |
| 254 // Each invocation of And or Or creates a new UnresolvedBranch. |
| 255 // These form a singly-linked list, of which we only need to keep track of |
| 256 // the tail. On creation of an UnresolvedBranch, pending_then_merges_ and |
| 257 // pending_else_merges_ each push a copy, which are removed on merges to the |
| 258 // respective environment. |
| 259 UnresolvedBranch* unresolved_list_tail_; |
| 260 int initial_environment_size_; |
| 261 // expression_states_ keeps track of the state of pending_*_merges_, |
| 262 // pushing and popping the lengths of these on |
| 263 // OpenParend() and CloseParend() respectively. |
| 264 ExpressionStates expression_states_; |
| 265 PendingMergeStack pending_then_merges_; |
| 266 PendingMergeStack pending_else_merges_; |
| 267 // then_environment_ is created iff there is a call to Then(), otherwise |
| 268 // branches which would merge to it merge to the exit environment instead. |
| 269 // Likewise for else_environment_. |
| 270 Environment* then_environment_; |
| 271 Environment* else_environment_; |
| 272 }; |
| 273 |
| 274 IfClause* CurrentClause() { return if_clauses_.back(); } |
| 275 void AddCurrentToPending(); |
| 276 void PushNewIfClause(); |
| 277 bool IsDone() { return if_clauses_.empty(); } |
| 278 |
| 279 StructuredMachineAssembler* smasm_; |
| 280 IfClauses if_clauses_; |
| 281 EnvironmentVector pending_exit_merges_; |
| 282 DISALLOW_COPY_AND_ASSIGN(IfBuilder); |
| 283 }; |
| 284 |
| 285 |
| 286 class StructuredMachineAssembler::LoopBuilder { |
| 287 public: |
| 288 explicit LoopBuilder(StructuredMachineAssembler* smasm); |
| 289 ~LoopBuilder() { |
| 290 if (!IsDone()) End(); |
| 291 } |
| 292 |
| 293 void Break(); |
| 294 void Continue(); |
| 295 void End(); |
| 296 |
| 297 private: |
| 298 friend class StructuredMachineAssembler; |
| 299 bool IsDone() { return header_environment_ == NULL; } |
| 300 |
| 301 StructuredMachineAssembler* smasm_; |
| 302 Environment* header_environment_; |
| 303 EnvironmentVector pending_header_merges_; |
| 304 EnvironmentVector pending_exit_merges_; |
| 305 DISALLOW_COPY_AND_ASSIGN(LoopBuilder); |
| 306 }; |
| 307 |
| 308 } // namespace compiler |
| 309 } // namespace internal |
| 310 } // namespace v8 |
| 311 |
| 312 #endif // V8_COMPILER_STRUCTURED_MACHINE_ASSEMBLER_H_ |
OLD | NEW |