Add support for (some) assignment expressions to the CFG builder and...

src/cfg.h

 // Copyright 2009 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 25 matching lines @@
 class ExitNode;
 class Location;
 
 // Translate a source AST into a control-flow graph (CFG).  The CFG contains
 // single-entry, single-exit blocks of straight-line instructions and
 // administrative nodes.
 //
 // Instructions are described by the following grammar.
 //
 // <Instruction> ::=
-//     BinaryOpInstr <Location> Token::Value <Value> <Value>
-//   | ReturnInstr Effect <Value>
+//     MoveInstr <Location> <Value>
+//   | BinaryOpInstr <Location> Token::Value <Value> <Value>
+//   | ReturnInstr Nowhere <Value>
+//   | PositionInstr <Int>
 //
 // Values are trivial expressions:
 //
 // <Value> ::= Constant | <Location>
 //
 // Locations are storable values ('lvalues').  They can be slots,
-// compiler-generated temporaries, or the special location 'Effect'
+// compiler-generated temporaries, or the special location 'Nowhere'
 // indicating that no value is needed.
 //
 // <Location> ::=
 //     SlotLocation Slot::Type <Index>
 //   | TempLocation
-//   | Effect
+//   | Nowhere
 
 
 // Administrative nodes: There are several types of 'administrative' nodes
 // that do not contain instructions and do not necessarily have a single
 // predecessor and a single successor.
 //
 // EntryNode: there is a distinguished entry node that has no predecessors
 // and a single successor.
 //
 // ExitNode: there is a distinguished exit node that has arbitrarily many
@@ skipping 17 matching lines @@
     ASSERT(top_ != NULL);
     return top_;
   }
 
   // The function currently being compiled.
   FunctionLiteral* fun() { return global_fun_; }
 
   // The shared global exit node for all exits from the function.
   ExitNode* exit() { return global_exit_; }
 
-  // A singleton effect location.
-  Location* effect_location() { return effect_; }
+  // A singleton.
+  Location* nowhere() { return nowhere_; }
 
 #ifdef DEBUG
   int next_node_number() { return node_counter_++; }
   int next_temp_number() { return temp_counter_++; }
 #endif
 
  private:
   static CfgGlobals* top_;
   FunctionLiteral* global_fun_;
   ExitNode* global_exit_;
-  Location* effect_;
+  Location* nowhere_;
 
 #ifdef DEBUG
   // Used to number nodes and temporaries when printing.
   int node_counter_;
   int temp_counter_;
 #endif
 
   CfgGlobals* previous_;
 };
 
 
+class SlotLocation;
+
 // Values represent trivial source expressions: ones with no side effects
 // and that do not require code to be generated.
 class Value : public ZoneObject {
  public:
   virtual ~Value() {}
 
   // Predicates:
 
   // True if the value is a temporary allocated to the stack in
   // fast-compilation mode.
   virtual bool is_on_stack() { return false; }
 
   // True if the value is a compiler-generated temporary location.
   virtual bool is_temporary() { return false; }
 
+  // True if the value is a slot location.
+  virtual bool is_slot() { return false; }
+
   // Support for fast-compilation mode:
 
   // Move the value into a register.
   virtual void Get(MacroAssembler* masm, Register reg) = 0;
 
   // Push the value on the stack.
   virtual void Push(MacroAssembler* masm) = 0;
 
+  // Move the value into a slot location.
+  virtual void MoveToSlot(MacroAssembler* masm, SlotLocation* loc) = 0;
+
 #ifdef DEBUG
   virtual void Print() = 0;
 #endif
 };
 
 
 // A compile-time constant that appeared as a literal in the source AST.
 class Constant : public Value {
  public:
   explicit Constant(Handle<Object> handle) : handle_(handle) {}
 
   virtual ~Constant() {}
 
   // Support for fast-compilation mode.
   void Get(MacroAssembler* masm, Register reg);
   void Push(MacroAssembler* masm);
+  void MoveToSlot(MacroAssembler* masm, SlotLocation* loc);
 
 #ifdef DEBUG
   void Print();
 #endif
 
  private:
   Handle<Object> handle_;
 };
 
 
 // Locations are values that can be stored into ('lvalues').
 class Location : public Value {
  public:
   virtual ~Location() {}
 
-  // Static factory function returning the singleton effect location.
-  static Location* Effect() {
-    return CfgGlobals::current()->effect_location();
+  // Static factory function returning the singleton nowhere location.
+  static Location* Nowhere() {
+    return CfgGlobals::current()->nowhere();
   }
 
   // Support for fast-compilation mode:
 
   // Assumes temporaries have been allocated.
   virtual void Get(MacroAssembler* masm, Register reg) = 0;
 
   // Store the value in a register to the location.  Assumes temporaries
   // have been allocated.
   virtual void Set(MacroAssembler* masm, Register reg) = 0;
 
   // Assumes temporaries have been allocated, and if the value is a
   // temporary it was not allocated to the stack.
   virtual void Push(MacroAssembler* masm) = 0;
 
+  // Emit code to move a value into this location.
+  virtual void Move(MacroAssembler* masm, Value* value) = 0;
+
 #ifdef DEBUG
   virtual void Print() = 0;
 #endif
 };
 
 
-// Effect is a special (singleton) location that indicates the value of a
+// Nowhere is a special (singleton) location that indicates the value of a
 // computation is not needed (though its side effects are).
-class Effect : public Location {
+class Nowhere : public Location {
  public:
-  // We should not try to emit code to read Effect.
+  // We should not try to emit code to read Nowhere.
   void Get(MacroAssembler* masm, Register reg) { UNREACHABLE(); }
   void Push(MacroAssembler* masm) { UNREACHABLE(); }
+  void MoveToSlot(MacroAssembler* masm, SlotLocation* loc) { UNREACHABLE(); }
 
-  // Setting Effect is ignored.
+  // Setting Nowhere is ignored.
   void Set(MacroAssembler* masm, Register reg) {}
+  void Move(MacroAssembler* masm, Value* value) {}
 
 #ifdef DEBUG
   void Print();
 #endif
 
  private:
-  Effect() {}
+  Nowhere() {}
 
   friend class CfgGlobals;
 };
 
 
 // SlotLocations represent parameters and stack-allocated (i.e.,
 // non-context) local variables.
 class SlotLocation : public Location {
  public:
   SlotLocation(Slot::Type type, int index) : type_(type), index_(index) {}
 
+  // Cast accessor.
+  static SlotLocation* cast(Value* value) {
+    ASSERT(value->is_slot());
+    return reinterpret_cast<SlotLocation*>(value);
+  }
+
   // Accessors.
   Slot::Type type() { return type_; }
   int index() { return index_; }
 
+  // Predicates.
+  bool is_slot() { return true; }
+
   // Support for fast-compilation mode.
   void Get(MacroAssembler* masm, Register reg);
   void Set(MacroAssembler* masm, Register reg);
   void Push(MacroAssembler* masm);
+  void Move(MacroAssembler* masm, Value* value);
+  void MoveToSlot(MacroAssembler* masm, SlotLocation* loc);
 
 #ifdef DEBUG
   void Print();
 #endif
 
  private:
   Slot::Type type_;
   int index_;
 };
 
 
 // TempLocations represent compiler generated temporaries.  They are
 // allocated to registers or memory either before code generation (in the
 // optimized-for-speed compiler) or on the fly during code generation (in
 // the optimized-for-space compiler).
 class TempLocation : public Location {
  public:
   // Fast-compilation mode allocation decisions.
   enum Where {
-    NOWHERE,      // Not yet allocated.
-    ACCUMULATOR,  // Allocated to the dedicated accumulator register.
-    STACK         //   "   "   "   "  stack.
+    NOT_ALLOCATED,  // Not yet allocated.
+    ACCUMULATOR,    // Allocated to the dedicated accumulator register.
+    STACK           //   "   "   "   "  stack.
   };
 
-  TempLocation() : where_(NOWHERE) {
+  TempLocation() : where_(NOT_ALLOCATED) {
 #ifdef DEBUG
     number_ = -1;
 #endif
   }
 
   // Cast accessor.
-  static TempLocation* cast(Location* loc) {
-    ASSERT(loc->is_temporary());
-    return reinterpret_cast<TempLocation*>(loc);
+  static TempLocation* cast(Value* value) {
+    ASSERT(value->is_temporary());
+    return reinterpret_cast<TempLocation*>(value);
   }
 
   // Accessors.
   Where where() { return where_; }
   void set_where(Where where) { where_ = where; }
 
   // Predicates.
   bool is_on_stack() { return where_ == STACK; }
   bool is_temporary() { return true; }
 
   // Support for fast-compilation mode.  Assume the temp has been allocated.
   void Get(MacroAssembler* masm, Register reg);
   void Set(MacroAssembler* masm, Register reg);
   void Push(MacroAssembler* masm);
+  void Move(MacroAssembler* masm, Value* value);
+  void MoveToSlot(MacroAssembler* masm, SlotLocation* loc);
 
 #ifdef DEBUG
   int number() {
     if (number_ == -1) number_ = CfgGlobals::current()->next_temp_number();
     return number_;
   }
 
   void Print();
 #endif
 
  private:
   Where where_;
 
 #ifdef DEBUG
   int number_;
 #endif
 };
 
 
 // Instructions are computations.  The represent non-trivial source
 // expressions: typically ones that have side effects and require code to
 // be generated.
 class Instruction : public ZoneObject {
  public:
   // Every instruction has a location where its result is stored (which may
-  // be Effect, the default).
-  Instruction() : loc_(CfgGlobals::current()->effect_location()) {}
+  // be Nowhere, the default).
+  Instruction() : location_(CfgGlobals::current()->nowhere()) {}
 
-  explicit Instruction(Location* loc) : loc_(loc) {}
+  explicit Instruction(Location* location) : location_(location) {}
 
   virtual ~Instruction() {}
 
   // Accessors.
-  Location* location() { return loc_; }
-  void set_location(Location* loc) { loc_ = loc; }
+  Location* location() { return location_; }
+  void set_location(Location* location) { location_ = location; }
 
   // Support for fast-compilation mode:
 
   // Emit code to perform the instruction.
   virtual void Compile(MacroAssembler* masm) = 0;
 
   // Allocate a temporary which is the result of the immediate predecessor
   // instruction.  It is allocated to the accumulator register if it is used
   // as an operand to this instruction, otherwise to the stack.
   virtual void FastAllocate(TempLocation* temp) = 0;
 
 #ifdef DEBUG
   virtual void Print() = 0;
 #endif
 
  protected:
-  Location* loc_;
+  Location* location_;
 };
 
 
 // A phantom instruction that indicates the start of a statement.  It
 // causes the statement position to be recorded in the relocation
 // information but generates no code.
 class PositionInstr : public Instruction {
  public:
   explicit PositionInstr(int pos) : pos_(pos) {}
 
   // Support for fast-compilation mode.
   void Compile(MacroAssembler* masm);
 
   // This should not be called.  The last instruction of the previous
   // statement should not have a temporary as its location.
   void FastAllocate(TempLocation* temp) { UNREACHABLE(); }
 
 #ifdef DEBUG
   // Printing support.  Print nothing.
   void Print() {}
 #endif
 
  private:
   int pos_;
 };
 
 
+// Move a value to a location.
+class MoveInstr : public Instruction {
+ public:
+  MoveInstr(Location* loc, Value* value) : Instruction(loc), value_(value) {}
+
+  // Accessors.
+  Value* value() { return value_; }
+
+  // Support for fast-compilation mode.
+  void Compile(MacroAssembler* masm);
+  void FastAllocate(TempLocation* temp);
+
+#ifdef DEBUG
+  void Print();
+#endif
+
+ private:
+  Value* value_;
+};
+
+
 // Perform a (non-short-circuited) binary operation on a pair of values,
 // leaving the result in a location.
 class BinaryOpInstr : public Instruction {
  public:
-  BinaryOpInstr(Location* loc, Token::Value op, Value* val0, Value* val1)
-      : Instruction(loc), op_(op), val0_(val0), val1_(val1) {
+  BinaryOpInstr(Location* loc, Token::Value op, Value* value0, Value* value1)
+      : Instruction(loc), op_(op), value0_(value0), value1_(value1) {
   }
 
+  // Accessors.
+  Token::Value op() { return op_; }
+  Value* value0() { return value0_; }
+  Value* value1() { return value1_; }
+
   // Support for fast-compilation mode.
   void Compile(MacroAssembler* masm);
   void FastAllocate(TempLocation* temp);
 
 #ifdef DEBUG
   void Print();
 #endif
 
  private:
   Token::Value op_;
-  Value* val0_;
-  Value* val1_;
+  Value* value0_;
+  Value* value1_;
 };
 
 
 // Return a value.  Has the side effect of moving its value into the return
 // value register.  Can only occur as the last instruction in an instruction
 // block, and implies that the block is closed (cannot have instructions
 // appended or graph fragments concatenated to the end) and that the block's
 // successor is the global exit node for the current function.
 class ReturnInstr : public Instruction {
  public:
-  // Location is always Effect.
   explicit ReturnInstr(Value* value) : value_(value) {}
 
   virtual ~ReturnInstr() {}
 
   // Support for fast-compilation mode.
   void Compile(MacroAssembler* masm);
   void FastAllocate(TempLocation* temp);
 
 #ifdef DEBUG
   void Print();
@@ skipping 194 matching lines @@
   void Print();
 #endif
 
  private:
   // Entry and exit nodes.
   CfgNode* entry_;
   CfgNode* exit_;
 };
 
 
+// An implementation of a set of locations (currently slot locations).
+class LocationSet BASE_EMBEDDED {
+ public:
+  // Construct an empty location set.
+  LocationSet() : parameters_(0), locals_(0) {}
+
+  // Raw accessors.
+  uintptr_t parameters() { return parameters_; }
+  uintptr_t locals() { return locals_; }
+
+  // Insert an element.
+  void AddElement(SlotLocation* location) {
+    if (location->type() == Slot::PARAMETER) {
+      // Parameter indexes begin with -1 ('this').
+      ASSERT(location->index() < kPointerSize - 1);
+      parameters_ |= (1 << (location->index() + 1));
+    } else {
+      ASSERT(location->type() == Slot::LOCAL);
+      ASSERT(location->index() < kPointerSize);
+      locals_ |= (1 << location->index());
+    }
+  }
+
+  // (Destructively) compute the union with another set.
+  void Union(LocationSet* other) {
+    parameters_ |= other->parameters();
+    locals_ |= other->locals();
+  }
+
+  bool Contains(SlotLocation* location) {
+    if (location->type() == Slot::PARAMETER) {
+      ASSERT(location->index() < kPointerSize - 1);
+      return (parameters_ & (1 << (location->index() + 1)));
+    } else {
+      ASSERT(location->type() == Slot::LOCAL);
+      ASSERT(location->index() < kPointerSize);
+      return (locals_ & (1 << location->index()));
+    }
+  }
+
+ private:
+  uintptr_t parameters_;
+  uintptr_t locals_;
+};
+
+
 // An ExpressionBuilder traverses an expression and returns an open CFG
 // fragment (currently a possibly empty list of instructions represented by
 // a singleton instruction block) and the expression's value.
 //
 // Failure is to build the CFG is indicated by a NULL CFG.
 class ExpressionBuilder : public AstVisitor {
  public:
-  ExpressionBuilder() : value_(NULL), cfg_(NULL) {}
+  ExpressionBuilder() : value_(NULL), graph_(NULL), destination_(NULL) {}
 
   // Result accessors.
   Value* value() { return value_; }
-  Cfg* cfg() { return cfg_; }
+  Cfg* graph() { return graph_; }
+  LocationSet* assigned_vars() { return &assigned_vars_; }
 
-  void Build(Expression* expr) {
+  // Build the cfg for an expression and remember its value.  The
+  // destination is a 'hint' where the value should go which may be ignored.
+  // NULL is used to indicate no preference.
+  //
+  // Concretely, if the expression needs to generate a temporary for its
+  // value, it should use the passed destination or generate one if NULL.
+  void Build(Expression* expr, Location* destination) {
     value_ = NULL;
-    cfg_ = new Cfg();
+    graph_ = new Cfg();
+    destination_ = destination;
     Visit(expr);
   }
 
   // AST node visitors.
 #define DECLARE_VISIT(type) void Visit##type(type* node);
   AST_NODE_LIST(DECLARE_VISIT)
 #undef DECLARE_VISIT
 
  private:
+  // State for the visitor.  Output parameters.
   Value* value_;
-  Cfg* cfg_;
+  Cfg* graph_;
+  LocationSet assigned_vars_;
+
+  // Input parameters.
+  Location* destination_;
 };
 
 
 // A StatementBuilder maintains a CFG fragment accumulator.  When it visits
 // a statement, it concatenates the CFG for the statement to the end of the
 // accumulator.
 class StatementBuilder : public AstVisitor {
  public:
-  StatementBuilder() : cfg_(new Cfg()) {}
+  StatementBuilder() : graph_(new Cfg()) {}
 
-  Cfg* cfg() { return cfg_; }
+  Cfg* graph() { return graph_; }
 
   void VisitStatements(ZoneList<Statement*>* stmts);
 
   // AST node visitors.
 #define DECLARE_VISIT(type) void Visit##type(type* node);
   AST_NODE_LIST(DECLARE_VISIT)
 #undef DECLARE_VISIT
 
  private:
-  Cfg* cfg_;
+  Cfg* graph_;
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_CFG_H_