Add last use data flow information to the fast code generator....

src/data-flow.cc

Index: src/data-flow.cc
===================================================================
--- src/data-flow.cc	(revision 3827)
+++ src/data-flow.cc	(working copy)
@@ -270,4 +270,292 @@
   UNREACHABLE();
 }
 
+
+ZoneList<Expression*>* VarUseMap::Lookup(Variable* var) {
+  HashMap::Entry* entry = HashMap::Lookup(var, var->name()->Hash(), true);
+  if (entry->value == NULL) {
+    entry->value = new ZoneList<Expression*>(1);
+  }
+  return reinterpret_cast<ZoneList<Expression*>*>(entry->value);
+}
+
+
+void LivenessAnalyzer::Analyze(FunctionLiteral* fun) {
+  // Process the function body.
+  VisitStatements(fun->body());
+
+  // All variables are implicitly defined at the function start.
+  // Record a definition of all variables live at function entry.
+  for (HashMap::Entry* p = live_vars_.Start();
+       p != NULL;
+       p = live_vars_.Next(p)) {
+    Variable* var = reinterpret_cast<Variable*>(p->key);
+    RecordDef(var, fun);
+  }
+}
+
+
+void LivenessAnalyzer::VisitStatements(ZoneList<Statement*>* stmts) {
+  // Visit statements right-to-left.
+  for (int i = stmts->length() - 1; i >= 0; i--) {
+    Visit(stmts->at(i));
+  }
+}
+
+
+void LivenessAnalyzer::RecordUse(Variable* var, Expression* expr) {
+  ASSERT(var->is_global() || var->is_this());
+  ZoneList<Expression*>* uses = live_vars_.Lookup(var);
+  uses->Add(expr);
+}
+
+
+void LivenessAnalyzer::RecordDef(Variable* var, Expression* expr) {
+  ASSERT(var->is_global() || var->is_this());
+
+  // We do not support other expressions that can define variables.
+  ASSERT(expr->AsFunctionLiteral() != NULL);
+
+  // Add the variable to the list of defined variables.
+  if (expr->defined_vars() == NULL) {
+    expr->set_defined_vars(new ZoneList<DefinitionInfo*>(1));
+  }
+  DefinitionInfo* def = new DefinitionInfo();
+  expr->AsFunctionLiteral()->defined_vars()->Add(def);
+
+  // Compute the last use of the definition. The variable uses are
+  // inserted in reversed evaluation order. The first element
+  // in the list of live uses is the last use.
+  ZoneList<Expression*>* uses = live_vars_.Lookup(var);
+  while (uses->length() > 0) {
+    Expression* use_site = uses->RemoveLast();
+    use_site->set_var_def(def);
+    if (uses->length() == 0) {
+      def->set_last_use(use_site);
+    }
+  }
+}
+
+
+// Visitor functions for live variable analysis.
+void LivenessAnalyzer::VisitDeclaration(Declaration* decl) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitBlock(Block* stmt) {
+  VisitStatements(stmt->statements());
+}
+
+
+void LivenessAnalyzer::VisitExpressionStatement(
+    ExpressionStatement* stmt) {
+  Visit(stmt->expression());
+}
+
+
+void LivenessAnalyzer::VisitEmptyStatement(EmptyStatement* stmt) {
+  // Do nothing.
+}
+
+
+void LivenessAnalyzer::VisitIfStatement(IfStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitContinueStatement(ContinueStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitBreakStatement(BreakStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitReturnStatement(ReturnStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitWithEnterStatement(
+    WithEnterStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitWithExitStatement(WithExitStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitSwitchStatement(SwitchStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitDoWhileStatement(DoWhileStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitWhileStatement(WhileStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitForStatement(ForStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitForInStatement(ForInStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitTryCatchStatement(TryCatchStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitTryFinallyStatement(
+    TryFinallyStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitDebuggerStatement(
+    DebuggerStatement* stmt) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitFunctionLiteral(FunctionLiteral* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitFunctionBoilerplateLiteral(
+    FunctionBoilerplateLiteral* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitConditional(Conditional* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitSlot(Slot* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitVariableProxy(VariableProxy* expr) {
+  Variable* var = expr->var();
+  ASSERT(var->is_global());
+  ASSERT(!var->is_this());
+  RecordUse(var, expr);
+}
+
+
+void LivenessAnalyzer::VisitLiteral(Literal* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitRegExpLiteral(RegExpLiteral* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitObjectLiteral(ObjectLiteral* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitArrayLiteral(ArrayLiteral* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitCatchExtensionObject(
+    CatchExtensionObject* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitAssignment(Assignment* expr) {
+  Property* prop = expr->target()->AsProperty();
+  ASSERT(prop != NULL);
+  ASSERT(prop->key()->IsPropertyName());
+  VariableProxy* proxy = prop->obj()->AsVariableProxy();
+  ASSERT(proxy != NULL && proxy->var()->is_this());
+
+  // Record use of this at the assignment node. Assignments to
+  // this-properties are treated like unary operations.
+  RecordUse(proxy->var(), expr);
+
+  // Visit right-hand side.
+  Visit(expr->value());
+}
+
+
+void LivenessAnalyzer::VisitThrow(Throw* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitProperty(Property* expr) {
+  ASSERT(expr->key()->IsPropertyName());
+  VariableProxy* proxy = expr->obj()->AsVariableProxy();
+  ASSERT(proxy != NULL && proxy->var()->is_this());
+  RecordUse(proxy->var(), expr);
+}
+
+
+void LivenessAnalyzer::VisitCall(Call* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitCallNew(CallNew* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitCallRuntime(CallRuntime* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitUnaryOperation(UnaryOperation* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitCountOperation(CountOperation* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitBinaryOperation(BinaryOperation* expr) {
+  // Visit child nodes in reverse evaluation order.
+  Visit(expr->right());
+  Visit(expr->left());
+}
+
+
+void LivenessAnalyzer::VisitCompareOperation(CompareOperation* expr) {
+  UNREACHABLE();
+}
+
+
+void LivenessAnalyzer::VisitThisFunction(ThisFunction* expr) {
+  UNREACHABLE();
+}
+
+
 } }  // namespace v8::internal