src/v8/src/compiler/structured-machine-assembler.h

   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       MachineType 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 MachineType* 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     DCHECK(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 &current_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<MachineType, zone_allocator<MachineType> >
 128       RepresentationVector;
 129
 130   Schedule* schedule_;
 131   MachineOperatorBuilder machine_;
 132   CommonOperatorBuilder common_;
 133   MachineCallDescriptorBuilder* call_descriptor_builder_;
 134   Node** parameters_;
 135   Environment* current_environment_;
 136   int number_of_variables_;
 137
 138   friend class Variable;
 139   // For testing only.
 140   friend class StructuredMachineAssemblerFriend;
 141   DISALLOW_COPY_AND_ASSIGN(StructuredMachineAssembler);
 142 };
 143
 144 // IfBuilder constructs of nested if-else expressions which more or less follow
 145 // C semantics.  Foe example:
 146 //
 147 //  if (x) {do_x} else if (y) {do_y} else {do_z}
 148 //
 149 // would look like this:
 150 //
 151 //  IfBuilder b;
 152 //  b.If(x).Then();
 153 //  do_x
 154 //  b.Else();
 155 //  b.If().Then();
 156 //  do_y
 157 //  b.Else();
 158 //  do_z
 159 //  b.End();
 160 //
 161 // Then() and Else() can be skipped, representing an empty block in C.
 162 // Combinations like If(x).Then().If(x).Then() are legitimate, but
 163 // Else().Else() is not. That is, once you've nested an If(), you can't get to a
 164 // higher level If() branch.
 165 // TODO(dcarney): describe expressions once the api is finalized.
 166 class StructuredMachineAssembler::IfBuilder {
 167  public:
 168   explicit IfBuilder(StructuredMachineAssembler* smasm);
 169   ~IfBuilder() {
 170     if (!IsDone()) End();
 171   }
 172
 173   IfBuilder& If();  // TODO(dcarney): this should take an expression.
 174   IfBuilder& If(Node* condition);
 175   void Then();
 176   void Else();
 177   void End();
 178
 179   // The next 4 functions are exposed for expression support.
 180   // They will be private once I have a nice expression api.
 181   void And();
 182   void Or();
 183   IfBuilder& OpenParen() {
 184     DCHECK(smasm_->current_environment_ != NULL);
 185     CurrentClause()->PushNewExpressionState();
 186     return *this;
 187   }
 188   IfBuilder& CloseParen() {
 189     DCHECK(smasm_->current_environment_ == NULL);
 190     CurrentClause()->PopExpressionState();
 191     return *this;
 192   }
 193
 194  private:
 195   // UnresolvedBranch represents the chain of environments created while
 196   // generating an expression.  At this point, a branch Node
 197   // cannot be created, as the target environments of the branch are not yet
 198   // available, so everything required to create the branch Node is
 199   // stored in this structure until the target environments are resolved.
 200   struct UnresolvedBranch : public ZoneObject {
 201     UnresolvedBranch(Environment* environment, Node* condition,
 202                      UnresolvedBranch* next)
 203         : environment_(environment), condition_(condition), next_(next) {}
 204     // environment_ will eventually be terminated by a branch on condition_.
 205     Environment* environment_;
 206     Node* condition_;
 207     // next_ is the next link in the UnresolvedBranch chain, and will be
 208     // either the true or false branch jumped to from environment_.
 209     UnresolvedBranch* next_;
 210   };
 211
 212   struct ExpressionState {
 213     int pending_then_size_;
 214     int pending_else_size_;
 215   };
 216
 217   typedef std::vector<ExpressionState, zone_allocator<ExpressionState> >
 218       ExpressionStates;
 219   typedef std::vector<UnresolvedBranch*, zone_allocator<UnresolvedBranch*> >
 220       PendingMergeStack;
 221   struct IfClause;
 222   typedef std::vector<IfClause*, zone_allocator<IfClause*> > IfClauses;
 223
 224   struct PendingMergeStackRange {
 225     PendingMergeStack* merge_stack_;
 226     int start_;
 227     int size_;
 228   };
 229
 230   enum CombineType { kCombineThen, kCombineElse };
 231   enum ResolutionType { kExpressionTerm, kExpressionDone };
 232
 233   // IfClause represents one level of if-then-else nesting plus the associated
 234   // expression.
 235   // A call to If() triggers creation of a new nesting level after expression
 236   // creation is complete - ie Then() or Else() has been called.
 237   struct IfClause : public ZoneObject {
 238     IfClause(Zone* zone, int initial_environment_size);
 239     void CopyEnvironments(const PendingMergeStackRange& data,
 240                           EnvironmentVector* environments);
 241     void ResolvePendingMerges(StructuredMachineAssembler* smasm,
 242                               CombineType combine_type,
 243                               ResolutionType resolution_type);
 244     PendingMergeStackRange ComputeRelevantMerges(CombineType combine_type);
 245     void FinalizeBranches(StructuredMachineAssembler* smasm,
 246                           const PendingMergeStackRange& offset_data,
 247                           CombineType combine_type,
 248                           Environment* then_environment,
 249                           Environment* else_environment);
 250     void PushNewExpressionState();
 251     void PopExpressionState();
 252
 253     // Each invocation of And or Or creates a new UnresolvedBranch.
 254     // These form a singly-linked list, of which we only need to keep track of
 255     // the tail.  On creation of an UnresolvedBranch, pending_then_merges_ and
 256     // pending_else_merges_ each push a copy, which are removed on merges to the
 257     // respective environment.
 258     UnresolvedBranch* unresolved_list_tail_;
 259     int initial_environment_size_;
 260     // expression_states_ keeps track of the state of pending_*_merges_,
 261     // pushing and popping the lengths of these on
 262     // OpenParend() and CloseParend() respectively.
 263     ExpressionStates expression_states_;
 264     PendingMergeStack pending_then_merges_;
 265     PendingMergeStack pending_else_merges_;
 266     // then_environment_ is created iff there is a call to Then(), otherwise
 267     // branches which would merge to it merge to the exit environment instead.
 268     // Likewise for else_environment_.
 269     Environment* then_environment_;
 270     Environment* else_environment_;
 271   };
 272
 273   IfClause* CurrentClause() { return if_clauses_.back(); }
 274   void AddCurrentToPending();
 275   void PushNewIfClause();
 276   bool IsDone() { return if_clauses_.empty(); }
 277
 278   StructuredMachineAssembler* smasm_;
 279   IfClauses if_clauses_;
 280   EnvironmentVector pending_exit_merges_;
 281   DISALLOW_COPY_AND_ASSIGN(IfBuilder);
 282 };
 283
 284
 285 class StructuredMachineAssembler::LoopBuilder {
 286  public:
 287   explicit LoopBuilder(StructuredMachineAssembler* smasm);
 288   ~LoopBuilder() {
 289     if (!IsDone()) End();
 290   }
 291
 292   void Break();
 293   void Continue();
 294   void End();
 295
 296  private:
 297   friend class StructuredMachineAssembler;
 298   bool IsDone() { return header_environment_ == NULL; }
 299
 300   StructuredMachineAssembler* smasm_;
 301   Environment* header_environment_;
 302   EnvironmentVector pending_header_merges_;
 303   EnvironmentVector pending_exit_merges_;
 304   DISALLOW_COPY_AND_ASSIGN(LoopBuilder);
 305 };
 306
 307 }  // namespace compiler
 308 }  // namespace internal
 309 }  // namespace v8
 310
 311 #endif  // V8_COMPILER_STRUCTURED_MACHINE_ASSEMBLER_H_