Initial support for marking live code.

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 134 matching lines @@
   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; }
 
+  // True if the AST node is critical (its execution is needed or externally
+  // visible in some way).
+  virtual bool IsCritical() { UNREACHABLE(); return true; }
+
   int num() { return num_; }
   void set_num(int n) { num_ = n; }
 
  private:
   // Support for ast node numbering.
   int num_;
 };
 
 
 class Statement: public AstNode {
@@ skipping 39 matching lines @@
   };
 
   Expression() : bitfields_(0) {}
 
   explicit Expression(Expression* other);
 
   virtual Expression* AsExpression()  { return this; }
 
   virtual bool IsValidLeftHandSide() { return false; }
 
-  virtual Variable* AssignedVar() { return NULL; }
+  virtual Variable* AssignedVariable() { 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; }
 
   // True if the expression does not have (evaluated) subexpressions.
   // Function literals are leaves because their subexpressions are not
   // evaluated.
   virtual bool IsLeaf() { return false; }
@@ skipping 51 matching lines @@
   }
 
   // How many bitwise logical or shift operators are used in this expression?
   int num_bit_ops() { return NumBitOpsField::decode(bitfields_); }
   void set_num_bit_ops(int num_bit_ops) {
     bitfields_ &= ~NumBitOpsField::mask();
     num_bit_ops = Min(num_bit_ops, kMaxNumBitOps);
     bitfields_ |= NumBitOpsField::encode(num_bit_ops);
   }
 
+  // Functions used for dead-code elimination.  Predicate is true if the
+  // expression is not dead code.
+  int is_live() const { return LiveField::decode(bitfields_); }
+  void mark_as_live() { bitfields_ |= LiveField::encode(true); }
+
+  // Mark non-live children as live and push them on a stack for further
+  // processing.
+  virtual void ProcessNonLiveChildren(
+      List<AstNode*>* stack,
+      ZoneList<Expression*>* body_definitions,
+      int variable_count) {
+  }
+
  private:
   static const int kMaxNumBitOps = (1 << 5) - 1;
 
   uint32_t bitfields_;
   StaticType type_;
 
   // Using template BitField<type, start, size>.
   class SideEffectFreeField : public BitField<bool, 0, 1> {};
   class NoNegativeZeroField : public BitField<bool, 1, 1> {};
   class ToInt32Field : public BitField<bool, 2, 1> {};
   class NumBitOpsField : public BitField<int, 3, 5> {};
   class LoopConditionField: public BitField<bool, 8, 1> {};
+  class LiveField: public BitField<bool, 9, 1> {};
 };
 
 
 /**
  * A sentinel used during pre parsing that represents some expression
  * that is a valid left hand side without having to actually build
  * the expression.
  */
 class ValidLeftHandSideSentinel: public Expression {
  public:
@@ skipping 566 matching lines @@
     if (handle_->IsSymbol()) {
       uint32_t ignored;
       return !String::cast(*handle_)->AsArrayIndex(&ignored);
     }
     return false;
   }
 
   virtual bool IsLeaf() { return true; }
   virtual bool IsTrivial() { return true; }
   virtual bool IsPrimitive();
+  virtual bool IsCritical();
+  virtual void ProcessNonLiveChildren(
+      List<AstNode*>* stack,
+      ZoneList<Expression*>* body_definitions,
+      int variable_count);
 
   // Identity testers.
   bool IsNull() const { return handle_.is_identical_to(Factory::null_value()); }
   bool IsTrue() const { return handle_.is_identical_to(Factory::true_value()); }
   bool IsFalse() const {
     return handle_.is_identical_to(Factory::false_value());
   }
 
   Handle<Object> handle() const { return handle_; }
 
@@ skipping 186 matching lines @@
   virtual bool IsLeaf() {
     ASSERT(var_ != NULL);  // Variable must be resolved.
     return var()->is_global() || var()->rewrite()->IsLeaf();
   }
 
   // Reading from a mutable variable is a side effect, but 'this' is
   // immutable.
   virtual bool IsTrivial() { return is_trivial_; }
 
   virtual bool IsPrimitive();
+  virtual bool IsCritical();
+  virtual void ProcessNonLiveChildren(
+      List<AstNode*>* stack,
+      ZoneList<Expression*>* body_definitions,
+      int variable_count);
 
   void SetIsPrimitive(bool value) { is_primitive_ = value; }
 
   bool IsVariable(Handle<String> n) {
     return !is_this() && name().is_identical_to(n);
   }
 
   bool IsArguments() {
     Variable* variable = AsVariable();
     return (variable == NULL) ? false : variable->is_arguments();
@@ skipping 117 matching lines @@
   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();
+  virtual bool IsCritical();
+  virtual void ProcessNonLiveChildren(
+      List<AstNode*>* stack,
+      ZoneList<Expression*>* body_definitions,
+      int variable_count);
 
   Expression* obj() const { return obj_; }
   Expression* key() const { return key_; }
   int position() const { return pos_; }
   bool is_synthetic() const { return type_ == SYNTHETIC; }
 
   // Returns a property singleton property access on 'this'.  Used
   // during preparsing.
   static Property* this_property() { return &this_property_; }
 
@@ skipping 14 matching lines @@
       : 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();
+  virtual bool IsCritical();
+  virtual void ProcessNonLiveChildren(
+      List<AstNode*>* stack,
+      ZoneList<Expression*>* body_definitions,
+      int variable_count);
 
   Expression* expression() const { return expression_; }
   ZoneList<Expression*>* arguments() const { return arguments_; }
   int position() { return pos_; }
 
   static Call* sentinel() { return &sentinel_; }
 
  private:
   Expression* expression_;
   ZoneList<Expression*>* arguments_;
@@ skipping 58 matching lines @@
   }
 
   UnaryOperation(UnaryOperation* other, Expression* expression);
 
   virtual void Accept(AstVisitor* v);
 
   // Type testing & conversion
   virtual UnaryOperation* AsUnaryOperation() { return this; }
 
   virtual bool IsPrimitive();
+  virtual bool IsCritical();
+  virtual void ProcessNonLiveChildren(
+      List<AstNode*>* stack,
+      ZoneList<Expression*>* body_definitions,
+      int variable_count);
 
   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();
+  virtual bool IsCritical();
+  virtual void ProcessNonLiveChildren(
+      List<AstNode*>* stack,
+      ZoneList<Expression*>* body_definitions,
+      int variable_count);
 
   // True iff the result can be safely overwritten (to avoid allocation).
   // False for operations that can return one of their operands.
   bool ResultOverwriteAllowed() {
     switch (op_) {
       case Token::COMMA:
       case Token::OR:
       case Token::AND:
         return false;
       case Token::BIT_OR:
@@ skipping 31 matching lines @@
       : 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() {
+  virtual Variable* AssignedVariable() {
     return expression()->AsVariableProxy()->AsVariable();
   }
 
   virtual bool IsPrimitive();
+  virtual bool IsCritical();
+  virtual void ProcessNonLiveChildren(
+      List<AstNode*>* stack,
+      ZoneList<Expression*>* body_definitions,
+      int variable_count);
 
   bool is_prefix() const { return is_prefix_; }
   bool is_postfix() const { return !is_prefix_; }
   Token::Value op() const { return op_; }
   Token::Value binary_op() {
     return op_ == Token::INC ? Token::ADD : Token::SUB;
   }
   Expression* expression() const { return expression_; }
 
   virtual void MarkAsStatement() { is_prefix_ = true; }
@@ skipping 12 matching lines @@
     ASSERT(Token::IsCompareOp(op));
   }
 
   CompareOperation(CompareOperation* other,
                    Expression* left,
                    Expression* right);
 
   virtual void Accept(AstVisitor* v);
 
   virtual bool IsPrimitive();
+  virtual bool IsCritical();
+  virtual void ProcessNonLiveChildren(
+      List<AstNode*>* stack,
+      ZoneList<Expression*>* body_definitions,
+      int variable_count);
 
   Token::Value op() const { return op_; }
   Expression* left() const { return left_; }
   Expression* right() const { return right_; }
 
   // Type testing & conversion
   virtual CompareOperation* AsCompareOperation() { return this; }
 
  private:
   Token::Value op_;
@@ skipping 33 matching lines @@
         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();
+  virtual bool IsCritical();
+  virtual void ProcessNonLiveChildren(
+      List<AstNode*>* stack,
+      ZoneList<Expression*>* body_definitions,
+      int variable_count);
 
   Assignment* AsSimpleAssignment() { return !is_compound() ? this : NULL; }
 
-  virtual Variable* AssignedVar() {
+  virtual Variable* AssignedVariable() {
     return target()->AsVariableProxy()->AsVariable();
   }
 
   Token::Value binary_op() const;
 
   Token::Value op() const { return op_; }
   Expression* target() const { return target_; }
   Expression* value() const { return value_; }
   int position() { return pos_; }
   // This check relies on the definition order of token in token.h.
@@ skipping 573 matching lines @@
 
   // 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_