Loop peeling for inner loops....

src/ast.h

 // Copyright 2010 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 102 matching lines @@
 // Please do appreciate the required space in "> >".
 typedef ZoneList<Handle<String> > ZoneStringList;
 typedef ZoneList<Handle<Object> > ZoneObjectList;
 
 
 class AstNode: public ZoneObject {
  public:
   static const int kNoNumber = -1;
 
   AstNode() : num_(kNoNumber) {}
+
+  explicit AstNode(AstNode* other);
+
   virtual ~AstNode() { }
   virtual void Accept(AstVisitor* v) = 0;
 
   // Type testing & conversion.
   virtual Statement* AsStatement() { return NULL; }
+  virtual Block* AsBlock() { return NULL; }
   virtual ExpressionStatement* AsExpressionStatement() { return NULL; }
   virtual EmptyStatement* AsEmptyStatement() { return NULL; }
   virtual Expression* AsExpression() { return NULL; }
   virtual Literal* AsLiteral() { return NULL; }
   virtual Slot* AsSlot() { return NULL; }
   virtual VariableProxy* AsVariableProxy() { return NULL; }
   virtual Property* AsProperty() { return NULL; }
   virtual Call* AsCall() { return NULL; }
   virtual TargetCollector* AsTargetCollector() { return NULL; }
   virtual BreakableStatement* AsBreakableStatement() { return NULL; }
   virtual IterationStatement* AsIterationStatement() { return NULL; }
+  virtual ForStatement* AsForStatement() { return NULL; }
   virtual UnaryOperation* AsUnaryOperation() { return NULL; }
   virtual CountOperation* AsCountOperation() { return NULL; }
   virtual BinaryOperation* AsBinaryOperation() { return NULL; }
   virtual Assignment* AsAssignment() { return NULL; }
   virtual FunctionLiteral* AsFunctionLiteral() { return NULL; }
   virtual MaterializedLiteral* AsMaterializedLiteral() { return NULL; }
   virtual ObjectLiteral* AsObjectLiteral() { return NULL; }
   virtual ArrayLiteral* AsArrayLiteral() { return NULL; }
   virtual CompareOperation* AsCompareOperation() { return NULL; }
 
   int num() { return num_; }
   void set_num(int n) { num_ = n; }
 
  private:
   // Support for ast node numbering.
   int num_;
 };
 
 
 class Statement: public AstNode {
  public:
   Statement() : statement_pos_(RelocInfo::kNoPosition) {}
 
+  explicit Statement(Statement* other);
+
   virtual Statement* AsStatement()  { return this; }
   virtual ReturnStatement* AsReturnStatement() { return NULL; }
 
   virtual Assignment* StatementAsSimpleAssignment() { return NULL; }
   virtual CountOperation* StatementAsCountOperation() { return NULL; }
 
   bool IsEmpty() { return AsEmptyStatement() != NULL; }
 
   void set_statement_pos(int statement_pos) { statement_pos_ = statement_pos; }
   int statement_pos() const { return statement_pos_; }
@@ skipping 21 matching lines @@
     // Evaluated for control flow and side effects.  Value is also
     // needed if false.
     kTestValue
   };
 
   Expression()
       : bitfields_(0),
         def_(NULL),
         defined_vars_(NULL) {}
 
+  explicit Expression(Expression* other);
+
   virtual Expression* AsExpression()  { return this; }
 
   virtual bool IsValidLeftHandSide() { return false; }
 
   virtual Variable* AssignedVar() { return NULL; }
 
   // Symbols that cannot be parsed as array indices are considered property
   // names.  We do not treat symbols that can be array indexes as property
   // names because [] for string objects is handled only by keyed ICs.
   virtual bool IsPropertyName() { return false; }
@@ skipping 48 matching lines @@
 
   // Will ToInt32 (ECMA 262-3 9.5) or ToUint32 (ECMA 262-3 9.6)
   // be applied to the value of this expression?
   // If so, we may be able to optimize the calculation of the value.
   bool to_int32() { return ToInt32Field::decode(bitfields_); }
   void set_to_int32(bool to_int32) {
     bitfields_ &= ~ToInt32Field::mask();
     bitfields_ |= ToInt32Field::encode(to_int32);
   }
 
-
  private:
   uint32_t bitfields_;
   StaticType type_;
 
   DefinitionInfo* def_;
   ZoneList<DefinitionInfo*>* defined_vars_;
 
   // Using template BitField<type, start, size>.
   class SideEffectFreeField : public BitField<bool, 0, 1> {};
   class NoNegativeZeroField : public BitField<bool, 1, 1> {};
@@ skipping 41 matching lines @@
 
   // Testers.
   bool is_target_for_anonymous() const { return type_ == TARGET_FOR_ANONYMOUS; }
 
  protected:
   BreakableStatement(ZoneStringList* labels, Type type)
       : labels_(labels), type_(type) {
     ASSERT(labels == NULL || labels->length() > 0);
   }
 
+  explicit BreakableStatement(BreakableStatement* other);
+
  private:
   ZoneStringList* labels_;
   Type type_;
   BreakTarget break_target_;
 };
 
 
 class Block: public BreakableStatement {
  public:
   Block(ZoneStringList* labels, int capacity, bool is_initializer_block)
       : BreakableStatement(labels, TARGET_FOR_NAMED_ONLY),
         statements_(capacity),
         is_initializer_block_(is_initializer_block) { }
 
+  // Construct a clone initialized from the original block and
+  // a deep copy of all statements of the original block.
+  Block(Block* other, ZoneList<Statement*>* statements);
+
   virtual void Accept(AstVisitor* v);
 
+  virtual Block* AsBlock() { return this; }
+
   virtual Assignment* StatementAsSimpleAssignment() {
     if (statements_.length() != 1) return NULL;
     return statements_[0]->StatementAsSimpleAssignment();
   }
 
   virtual CountOperation* StatementAsCountOperation() {
     if (statements_.length() != 1) return NULL;
     return statements_[0]->StatementAsCountOperation();
   }
 
@@ skipping 31 matching lines @@
   FunctionLiteral* fun_;
 };
 
 
 class IterationStatement: public BreakableStatement {
  public:
   // Type testing & conversion.
   virtual IterationStatement* AsIterationStatement() { return this; }
 
   Statement* body() const { return body_; }
+  void set_body(Statement* stmt) { body_ = stmt; }
 
   // Code generation
   BreakTarget* continue_target()  { return &continue_target_; }
 
  protected:
   explicit IterationStatement(ZoneStringList* labels)
       : BreakableStatement(labels, TARGET_FOR_ANONYMOUS), body_(NULL) { }
 
+  // Construct a clone initialized from  original and
+  // a deep copy of the original body.
+  IterationStatement(IterationStatement* other, Statement* body);
+
   void Initialize(Statement* body) {
     body_ = body;
   }
 
  private:
   Statement* body_;
   BreakTarget continue_target_;
 };
 
 
@@ skipping 53 matching lines @@
 
 
 class ForStatement: public IterationStatement {
  public:
   explicit ForStatement(ZoneStringList* labels)
       : IterationStatement(labels),
         init_(NULL),
         cond_(NULL),
         next_(NULL),
         may_have_function_literal_(true),
-        loop_variable_(NULL) {}
+        loop_variable_(NULL),
+        peel_this_loop_(false) {}
+
+  // Construct a for-statement initialized from another for-statement
+  // and deep copies of all parts of the original statement.
+  ForStatement(ForStatement* other,
+               Statement* init,
+               Expression* cond,
+               Statement* next,
+               Statement* body);
+
+  virtual ForStatement* AsForStatement() { return this; }
 
   void Initialize(Statement* init,
                   Expression* cond,
                   Statement* next,
                   Statement* body) {
     IterationStatement::Initialize(body);
     init_ = init;
     cond_ = cond;
     next_ = next;
   }
 
   virtual void Accept(AstVisitor* v);
 
   Statement* init() const  { return init_; }
+  void set_init(Statement* stmt) { init_ = stmt; }
   Expression* cond() const  { return cond_; }
+  void set_cond(Expression* expr) { cond_ = expr; }
   Statement* next() const  { return next_; }
+  void set_next(Statement* stmt) { next_ = stmt; }
   bool may_have_function_literal() const {
     return may_have_function_literal_;
   }
 
   bool is_fast_smi_loop() { return loop_variable_ != NULL; }
   Variable* loop_variable() { return loop_variable_; }
   void set_loop_variable(Variable* var) { loop_variable_ = var; }
 
+  bool peel_this_loop() { return peel_this_loop_; }
+  void set_peel_this_loop(bool b) { peel_this_loop_ = b; }
+
  private:
   Statement* init_;
   Expression* cond_;
   Statement* next_;
   // True if there is a function literal subexpression in the condition.
   bool may_have_function_literal_;
   Variable* loop_variable_;
+  bool peel_this_loop_;
 
   friend class AstOptimizer;
 };
 
 
 class ForInStatement: public IterationStatement {
  public:
   explicit ForInStatement(ZoneStringList* labels)
       : IterationStatement(labels), each_(NULL), enumerable_(NULL) { }
 
@@ skipping 12 matching lines @@
   Expression* each_;
   Expression* enumerable_;
 };
 
 
 class ExpressionStatement: public Statement {
  public:
   explicit ExpressionStatement(Expression* expression)
       : expression_(expression) { }
 
+  // Construct an expression statement initialized from another
+  // expression statement and a deep copy of the original expression.
+  ExpressionStatement(ExpressionStatement* other, Expression* expression);
+
   virtual void Accept(AstVisitor* v);
 
   // Type testing & conversion.
   virtual ExpressionStatement* AsExpressionStatement() { return this; }
 
   virtual Assignment* StatementAsSimpleAssignment();
   virtual CountOperation* StatementAsCountOperation();
 
   void set_expression(Expression* e) { expression_ = e; }
   Expression* expression() { return expression_; }
@@ skipping 122 matching lines @@
 // given if-statement has a then- or an else-part containing code.
 class IfStatement: public Statement {
  public:
   IfStatement(Expression* condition,
               Statement* then_statement,
               Statement* else_statement)
       : condition_(condition),
         then_statement_(then_statement),
         else_statement_(else_statement) { }
 
+  // Construct an if-statement initialized from another if-statement
+  // and deep copies of all parts of the original.
+  IfStatement(IfStatement* other,
+              Expression* condition,
+              Statement* then_statement,
+              Statement* else_statement);
+
   virtual void Accept(AstVisitor* v);
 
   bool HasThenStatement() const { return !then_statement()->IsEmpty(); }
   bool HasElseStatement() const { return !else_statement()->IsEmpty(); }
 
   Expression* condition() const { return condition_; }
   Statement* then_statement() const { return then_statement_; }
+  void set_then_statement(Statement* stmt) { then_statement_ = stmt; }
   Statement* else_statement() const { return else_statement_; }
+  void set_else_statement(Statement* stmt) { else_statement_ = stmt; }
 
  private:
   Expression* condition_;
   Statement* then_statement_;
   Statement* else_statement_;
 };
 
 
 // NOTE: TargetCollectors are represented as nodes to fit in the target
 // stack in the compiler; this should probably be reworked.
@@ skipping 74 matching lines @@
 
 
 class DebuggerStatement: public Statement {
  public:
   virtual void Accept(AstVisitor* v);
 };
 
 
 class EmptyStatement: public Statement {
  public:
+  EmptyStatement() {}
+
+  explicit EmptyStatement(EmptyStatement* other);
+
   virtual void Accept(AstVisitor* v);
 
   // Type testing & conversion.
   virtual EmptyStatement* AsEmptyStatement() { return this; }
 };
 
 
 class Literal: public Expression {
  public:
   explicit Literal(Handle<Object> handle) : handle_(handle) { }
@@ skipping 338 matching lines @@
 class Property: public Expression {
  public:
   // Synthetic properties are property lookups introduced by the system,
   // to objects that aren't visible to the user. Function calls to synthetic
   // properties should use the global object as receiver, not the base object
   // of the resolved Reference.
   enum Type { NORMAL, SYNTHETIC };
   Property(Expression* obj, Expression* key, int pos, Type type = NORMAL)
       : obj_(obj), key_(key), pos_(pos), type_(type) { }
 
+  Property(Property* other, Expression* obj, Expression* key);
+
   virtual void Accept(AstVisitor* v);
 
   // Type testing & conversion
   virtual Property* AsProperty() { return this; }
 
   virtual bool IsValidLeftHandSide() { return true; }
 
   virtual bool IsPrimitive();
 
   Expression* obj() const { return obj_; }
@@ skipping 14 matching lines @@
   // Dummy property used during preparsing.
   static Property this_property_;
 };
 
 
 class Call: public Expression {
  public:
   Call(Expression* expression, ZoneList<Expression*>* arguments, int pos)
       : expression_(expression), arguments_(arguments), pos_(pos) { }
 
+  Call(Call* other, Expression* expression, ZoneList<Expression*>* arguments);
+
   virtual void Accept(AstVisitor* v);
 
   // Type testing and conversion.
   virtual Call* AsCall() { return this; }
 
   virtual bool IsPrimitive();
 
   Expression* expression() const { return expression_; }
   ZoneList<Expression*>* arguments() const { return arguments_; }
   int position() { return pos_; }
@@ skipping 56 matching lines @@
 };
 
 
 class UnaryOperation: public Expression {
  public:
   UnaryOperation(Token::Value op, Expression* expression)
       : op_(op), expression_(expression) {
     ASSERT(Token::IsUnaryOp(op));
   }
 
+  UnaryOperation(UnaryOperation* other, Expression* expression);
+
   virtual void Accept(AstVisitor* v);
 
   // Type testing & conversion
   virtual UnaryOperation* AsUnaryOperation() { return this; }
 
   virtual bool IsPrimitive();
 
   Token::Value op() const { return op_; }
   Expression* expression() const { return expression_; }
 
  private:
   Token::Value op_;
   Expression* expression_;
 };
 
 
 class BinaryOperation: public Expression {
  public:
   BinaryOperation(Token::Value op, Expression* left, Expression* right)
       : op_(op), left_(left), right_(right) {
     ASSERT(Token::IsBinaryOp(op));
   }
 
+  BinaryOperation(BinaryOperation* other, Expression* left, Expression* right);
+
   virtual void Accept(AstVisitor* v);
 
   // Type testing & conversion
   virtual BinaryOperation* AsBinaryOperation() { return this; }
 
   virtual bool IsPrimitive();
 
   // True iff the result can be safely overwritten (to avoid allocation).
   // False for operations that can return one of their operands.
   bool ResultOverwriteAllowed() {
@@ skipping 31 matching lines @@
 };
 
 
 class CountOperation: public Expression {
  public:
   CountOperation(bool is_prefix, Token::Value op, Expression* expression)
       : is_prefix_(is_prefix), op_(op), expression_(expression) {
     ASSERT(Token::IsCountOp(op));
   }
 
+  CountOperation(CountOperation* other, Expression* expression);
+
   virtual void Accept(AstVisitor* v);
 
   virtual CountOperation* AsCountOperation() { return this; }
 
   virtual Variable* AssignedVar() {
     return expression()->AsVariableProxy()->AsVariable();
   }
 
   virtual bool IsPrimitive();
 
@@ skipping 14 matching lines @@
 };
 
 
 class CompareOperation: public Expression {
  public:
   CompareOperation(Token::Value op, Expression* left, Expression* right)
       : op_(op), left_(left), right_(right), is_for_loop_condition_(false) {
     ASSERT(Token::IsCompareOp(op));
   }
 
+  CompareOperation(CompareOperation* other,
+                   Expression* left,
+                   Expression* right);
+
   virtual void Accept(AstVisitor* v);
 
   virtual bool IsPrimitive();
 
   Token::Value op() const { return op_; }
   Expression* left() const { return left_; }
   Expression* right() const { return right_; }
 
   // Accessors for flag whether this compare operation is hanging of a for loop.
   bool is_for_loop_condition() const { return is_for_loop_condition_; }
@@ skipping 35 matching lines @@
 
 
 class Assignment: public Expression {
  public:
   Assignment(Token::Value op, Expression* target, Expression* value, int pos)
       : op_(op), target_(target), value_(value), pos_(pos),
         block_start_(false), block_end_(false) {
     ASSERT(Token::IsAssignmentOp(op));
   }
 
+  Assignment(Assignment* other, Expression* target, Expression* value);
+
   virtual void Accept(AstVisitor* v);
   virtual Assignment* AsAssignment() { return this; }
 
   virtual bool IsPrimitive();
 
   Assignment* AsSimpleAssignment() { return !is_compound() ? this : NULL; }
 
   virtual Variable* AssignedVar() {
     return target()->AsVariableProxy()->AsVariable();
   }
@@ skipping 555 matching lines @@
 #define DEF_VISIT(type)                         \
   virtual void Visit##type(type* node) = 0;
   AST_NODE_LIST(DEF_VISIT)
 #undef DEF_VISIT
 
  private:
   bool stack_overflow_;
 };
 
 
+class CopyAstVisitor : public AstVisitor {
+ public:
+  Expression* DeepCopyExpr(Expression* expr);
+
+  Statement* DeepCopyStmt(Statement* stmt);
+
+ private:
+  ZoneList<Expression*>* DeepCopyExprList(ZoneList<Expression*>* expressions);
+
+  ZoneList<Statement*>* DeepCopyStmtList(ZoneList<Statement*>* statements);
+
+  // AST node visit functions.
+#define DECLARE_VISIT(type) virtual void Visit##type(type* node);
+  AST_NODE_LIST(DECLARE_VISIT)
+#undef DECLARE_VISIT
+
+  // Holds the result of copying an expression.
+  Expression* expr_;
+  // Holds the result of copying a statement.
+  Statement* stmt_;
+};
+
 } }  // namespace v8::internal
 
 #endif  // V8_AST_H_