Initial support for marking live code.

src/ast.cc

Index: src/ast.cc
diff --git a/src/ast.cc b/src/ast.cc
index 7dd991fd4261cb2929a950a8e0ff24017e71cd3e..7d26cd92cec93923e5bfdb19cdf15e48d6ac2f85 100644
--- a/src/ast.cc
+++ b/src/ast.cc
@@ -28,6 +28,7 @@
 #include "v8.h"
 
 #include "ast.h"
+#include "data-flow.h"
 #include "parser.h"
 #include "scopes.h"
 #include "string-stream.h"
@@ -600,6 +601,199 @@ bool BinaryOperation::IsPrimitive() {
 bool CompareOperation::IsPrimitive() { return true; }
 
 
+// Overridden IsCritical member functions.  IsCritical is true for AST nodes
+// whose evaluation is absolutely required (they are never dead) because
+// they are externally visible.
+
+// References to global variables or lookup slots are critical because they
+// may have getters.  All others, including parameters rewritten to explicit
+// property references, are not critical.
+bool VariableProxy::IsCritical() {
+  Variable* var = AsVariable();
+  return var != NULL &&
+      (var->slot() == NULL || var->slot()->type() == Slot::LOOKUP);
+}
+
+
+// Literals are never critical.
+bool Literal::IsCritical() { return false; }
+
+
+// Property assignments and throwing of reference errors are always
+// critical.  Assignments to escaping variables are also critical.  In
+// addition the operation of compound assignments is critical if either of
+// its operands is non-primitive (the arithmetic operations all use one of
+// ToPrimitive, ToNumber, ToInt32, or ToUint32 on each of their operands).
+// In this case, we mark the entire AST node as critical because there is
+// no binary operation node to mark.
+bool Assignment::IsCritical() {
+  Variable* var = AssignedVariable();
+  return var == NULL ||
+      !var->IsStackAllocated() ||
+      (is_compound() && (!target()->IsPrimitive() || !value()->IsPrimitive()));
+}
+
+
+// Property references are always critical, because they may have getters.
+bool Property::IsCritical() { return true; }
+
+
+// Calls are always critical.
+bool Call::IsCritical() { return true; }
+
+
+// +,- use ToNumber on the value of their operand.
+bool UnaryOperation::IsCritical() {
+  ASSERT(op() == Token::ADD || op() == Token::SUB);
+  return !expression()->IsPrimitive();
+}
+
+
+// Count operations targeting properties and reference errors are always
+// critical.  Count operations on escaping variables are critical.  Count
+// operations targeting non-primitives are also critical because they use
+// ToNumber.
+bool CountOperation::IsCritical() {
+  Variable* var = AssignedVariable();
+  return var == NULL ||
+      !var->IsStackAllocated() ||
+      !expression()->IsPrimitive();
+}
+
+
+// Arithmetic operations all use one of ToPrimitive, ToNumber, ToInt32, or
+// ToUint32 on each of their operands.
+bool BinaryOperation::IsCritical() {
+  ASSERT(op() != Token::COMMA);
+  ASSERT(op() != Token::OR);
+  ASSERT(op() != Token::AND);
+  return !left()->IsPrimitive() || !right()->IsPrimitive();
+}
+
+
+// <, >, <=, and >= all use ToPrimitive on both their operands.
+bool CompareOperation::IsCritical() {
+  ASSERT(op() != Token::EQ);
+  ASSERT(op() != Token::NE);
+  ASSERT(op() != Token::EQ_STRICT);
+  ASSERT(op() != Token::NE_STRICT);
+  ASSERT(op() != Token::INSTANCEOF);
+  ASSERT(op() != Token::IN);
+  return !left()->IsPrimitive() || !right()->IsPrimitive();
+}
+
+
+static inline void MarkIfNotLive(Expression* expr, List<AstNode*>* stack) {
+  if (!expr->is_live()) {
+    expr->mark_as_live();
+    stack->Add(expr);
+  }
+}
+
+
+// Overloaded functions for marking children of live code as live.
+void VariableProxy::ProcessNonLiveChildren(
+    List<AstNode*>* stack,
+    ZoneList<Expression*>* body_definitions,
+    int variable_count) {
+  // A reference to a stack-allocated variable depends on all the
+  // definitions reaching it.
+  BitVector* defs = reaching_definitions();
+  if (defs != NULL) {
+    ASSERT(var()->IsStackAllocated());
+    // The first variable_count definitions are the initial parameter and
+    // local declarations.
+    for (int i = variable_count; i < defs->length(); i++) {
+      if (defs->Contains(i)) {
+        MarkIfNotLive(body_definitions->at(i - variable_count), stack);
+      }
+    }
+  }
+}
+
+
+void Literal::ProcessNonLiveChildren(List<AstNode*>* stack,
+                                     ZoneList<Expression*>* body_definitions,
+                                     int variable_count) {
+  // Leaf node, no children.
+}
+
+
+void Assignment::ProcessNonLiveChildren(
+    List<AstNode*>* stack,
+    ZoneList<Expression*>* body_definitions,
+    int variable_count) {
+  Property* prop = target()->AsProperty();
+  VariableProxy* proxy = target()->AsVariableProxy();
+
+  if (prop != NULL) {
+    if (!prop->key()->IsPropertyName()) MarkIfNotLive(prop->key(), stack);
+    MarkIfNotLive(prop->obj(), stack);
+  } else if (proxy == NULL) {
+    // Must be a reference error.
+    ASSERT(!target()->IsValidLeftHandSide());
+    MarkIfNotLive(target(), stack);
+  } else if (is_compound()) {
+    // A variable assignment so lhs is an operand to the operation.
+    MarkIfNotLive(target(), stack);
+  }
+  MarkIfNotLive(value(), stack);
+}
+
+
+void Property::ProcessNonLiveChildren(List<AstNode*>* stack,
+                                      ZoneList<Expression*>* body_definitions,
+                                      int variable_count) {
+  if (!key()->IsPropertyName()) MarkIfNotLive(key(), stack);
+  MarkIfNotLive(obj(), stack);
+}
+
+
+void Call::ProcessNonLiveChildren(List<AstNode*>* stack,
+                                  ZoneList<Expression*>* body_definitions,
+                                  int variable_count) {
+  ZoneList<Expression*>* args = arguments();
+  for (int i = args->length() - 1; i >= 0; i--) {
+    MarkIfNotLive(args->at(i), stack);
+  }
+  MarkIfNotLive(expression(), stack);
+}
+
+
+void UnaryOperation::ProcessNonLiveChildren(
+    List<AstNode*>* stack,
+    ZoneList<Expression*>* body_definitions,
+    int variable_count) {
+  MarkIfNotLive(expression(), stack);
+}
+
+
+void CountOperation::ProcessNonLiveChildren(
+    List<AstNode*>* stack,
+    ZoneList<Expression*>* body_definitions,
+    int variable_count) {
+  MarkIfNotLive(expression(), stack);
+}
+
+
+void BinaryOperation::ProcessNonLiveChildren(
+    List<AstNode*>* stack,
+    ZoneList<Expression*>* body_definitions,
+    int variable_count) {
+  MarkIfNotLive(right(), stack);
+  MarkIfNotLive(left(), stack);
+}
+
+
+void CompareOperation::ProcessNonLiveChildren(
+    List<AstNode*>* stack,
+    ZoneList<Expression*>* body_definitions,
+    int variable_count) {
+  MarkIfNotLive(right(), stack);
+  MarkIfNotLive(left(), stack);
+}
+
+
 // Implementation of a copy visitor. The visitor create a deep copy
 // of ast nodes. Nodes that do not require a deep copy are copied
 // with the default copy constructor.