src/data-flow.cc

// 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
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "v8.h"

#include "data-flow.h"

namespace v8 {
namespace internal {


void FlowGraph::AppendInstruction(AstNode* instruction) {
  ASSERT(instruction != NULL);
  if (is_empty() || !exit()->IsBlockNode()) {
    AppendNode(new BlockNode());
  }
  BlockNode::cast(exit())->AddInstruction(instruction);
}


void FlowGraph::AppendNode(Node* node) {
  ASSERT(node != NULL);
  if (is_empty()) {
    entry_ = exit_ = node;
  } else {
    exit()->AddSuccessor(node);
    node->AddPredecessor(exit());
    exit_ = node;
  }
}


void FlowGraph::AppendGraph(FlowGraph* graph) {
  ASSERT(!graph->is_empty());
  if (is_empty()) {
    entry_ = graph->entry();
    exit_ = graph->exit();
  } else {
    exit()->AddSuccessor(graph->entry());
    graph->entry()->AddPredecessor(exit());
    exit_ = graph->exit();
  }
}


void FlowGraph::Split(BranchNode* branch,
                      FlowGraph* left,
                      FlowGraph* right,
                      JoinNode* merge) {
  // Graphs are in edge split form.  Add empty blocks if necessary.
  if (left->is_empty()) left->AppendNode(new BlockNode());
  if (right->is_empty()) right->AppendNode(new BlockNode());

  // Add the branch, left flowgraph and merge.
  AppendNode(branch);
  AppendGraph(left);
  AppendNode(merge);

  // Splice in the right flowgraph.
  right->AppendNode(merge);
  branch->AddSuccessor(right->entry());
  right->entry()->AddPredecessor(branch);
}


void FlowGraph::Loop(JoinNode* merge,
                     FlowGraph* condition,
                     BranchNode* branch,
                     FlowGraph* body) {
  // Add the merge, condition and branch.  Add merge's predecessors in
  // left-to-right order.
  AppendNode(merge);
  body->AppendNode(merge);
  AppendGraph(condition);
  AppendNode(branch);

  // Splice in the body flowgraph.
  branch->AddSuccessor(body->entry());
  body->entry()->AddPredecessor(branch);
}


void EntryNode::Traverse(bool mark,
                         ZoneList<Node*>* preorder,
                         ZoneList<Node*>* postorder) {
  ASSERT(successor_ != NULL);
  preorder->Add(this);
  if (!successor_->IsMarkedWith(mark)) {
    successor_->MarkWith(mark);
    successor_->Traverse(mark, preorder, postorder);
  }
  postorder->Add(this);
}


void ExitNode::Traverse(bool mark,
                        ZoneList<Node*>* preorder,
                        ZoneList<Node*>* postorder) {
  preorder->Add(this);
  postorder->Add(this);
}


void BlockNode::Traverse(bool mark,
                         ZoneList<Node*>* preorder,
                         ZoneList<Node*>* postorder) {
  ASSERT(successor_ != NULL);
  preorder->Add(this);
  if (!successor_->IsMarkedWith(mark)) {
    successor_->MarkWith(mark);
    successor_->Traverse(mark, preorder, postorder);
  }
  postorder->Add(this);
}


void BranchNode::Traverse(bool mark,
                          ZoneList<Node*>* preorder,
                          ZoneList<Node*>* postorder) {
  ASSERT(successor0_ != NULL && successor1_ != NULL);
  preorder->Add(this);
  if (!successor0_->IsMarkedWith(mark)) {
    successor0_->MarkWith(mark);
    successor0_->Traverse(mark, preorder, postorder);
  }
  if (!successor1_->IsMarkedWith(mark)) {
    successor1_->MarkWith(mark);
    successor1_->Traverse(mark, preorder, postorder);
  }
  postorder->Add(this);
}


void JoinNode::Traverse(bool mark,
                        ZoneList<Node*>* preorder,
                        ZoneList<Node*>* postorder) {
  ASSERT(successor_ != NULL);
  preorder->Add(this);
  if (!successor_->IsMarkedWith(mark)) {
    successor_->MarkWith(mark);
    successor_->Traverse(mark, preorder, postorder);
  }
  postorder->Add(this);
}


void FlowGraphBuilder::Build(FunctionLiteral* lit) {
  graph_ = FlowGraph::Empty();
  graph_.AppendNode(new EntryNode());
  global_exit_ = new ExitNode();
  VisitStatements(lit->body());

  if (HasStackOverflow()) {
    graph_ = FlowGraph::Empty();
    return;
  }

  graph_.AppendNode(global_exit_);

  // Build preorder and postorder traversal orders.  All the nodes in
  // the graph have the same mark flag.  For the traversal, use that
  // flag's negation.  Traversal will flip all the flags.
  bool mark = graph_.entry()->IsMarkedWith(false);
  graph_.entry()->MarkWith(mark);
  graph_.entry()->Traverse(mark, &preorder_, &postorder_);
}


void FlowGraphBuilder::VisitDeclaration(Declaration* decl) {
  UNREACHABLE();
}


void FlowGraphBuilder::VisitBlock(Block* stmt) {
  VisitStatements(stmt->statements());
}


void FlowGraphBuilder::VisitExpressionStatement(ExpressionStatement* stmt) {
  Visit(stmt->expression());
}


void FlowGraphBuilder::VisitEmptyStatement(EmptyStatement* stmt) {
  // Nothing to do.
}


void FlowGraphBuilder::VisitIfStatement(IfStatement* stmt) {
  Visit(stmt->condition());

  BranchNode* branch = new BranchNode();
  FlowGraph original = graph_;
  graph_ = FlowGraph::Empty();
  Visit(stmt->then_statement());

  FlowGraph left = graph_;
  graph_ = FlowGraph::Empty();
  Visit(stmt->else_statement());

  JoinNode* join = new JoinNode();
  original.Split(branch, &left, &graph_, join);
  graph_ = original;
}


void FlowGraphBuilder::VisitContinueStatement(ContinueStatement* stmt) {
  SetStackOverflow();
}


void FlowGraphBuilder::VisitBreakStatement(BreakStatement* stmt) {
  SetStackOverflow();
}


void FlowGraphBuilder::VisitReturnStatement(ReturnStatement* stmt) {
  Visit(stmt->expression());
  graph_.AppendInstruction(stmt);
  graph_.AppendNode(global_exit());
}


void FlowGraphBuilder::VisitWithEnterStatement(WithEnterStatement* stmt) {
  Visit(stmt->expression());
  graph_.AppendInstruction(stmt);
}


void FlowGraphBuilder::VisitWithExitStatement(WithExitStatement* stmt) {
  graph_.AppendInstruction(stmt);
}


void FlowGraphBuilder::VisitSwitchStatement(SwitchStatement* stmt) {
  SetStackOverflow();
}


void FlowGraphBuilder::VisitDoWhileStatement(DoWhileStatement* stmt) {
  JoinNode* join = new JoinNode();
  FlowGraph original = graph_;
  graph_ = FlowGraph::Empty();
  Visit(stmt->body());

  FlowGraph body = graph_;
  graph_ = FlowGraph::Empty();
  Visit(stmt->cond());

  BranchNode* branch = new BranchNode();

  // Add body, condition and branch.
  original.AppendNode(join);
  original.AppendGraph(&body);
  original.AppendGraph(&graph_);  // The condition.
  original.AppendNode(branch);

  // Tie the knot.
  branch->AddSuccessor(join);
  join->AddPredecessor(branch);

  graph_ = original;
}


void FlowGraphBuilder::VisitWhileStatement(WhileStatement* stmt) {
  JoinNode* join = new JoinNode();
  FlowGraph original = graph_;
  graph_ = FlowGraph::Empty();
  Visit(stmt->cond());

  BranchNode* branch = new BranchNode();
  FlowGraph condition = graph_;
  graph_ = FlowGraph::Empty();
  Visit(stmt->body());

  original.Loop(join, &condition, branch, &graph_);
  graph_ = original;
}


void FlowGraphBuilder::VisitForStatement(ForStatement* stmt) {
  if (stmt->init() != NULL) Visit(stmt->init());

  JoinNode* join = new JoinNode();
  FlowGraph original = graph_;
  graph_ = FlowGraph::Empty();
  if (stmt->cond() != NULL) Visit(stmt->cond());

  BranchNode* branch = new BranchNode();
  FlowGraph condition = graph_;
  graph_ = FlowGraph::Empty();
  Visit(stmt->body());

  if (stmt->next() != NULL) Visit(stmt->next());

  original.Loop(join, &condition, branch, &graph_);
  graph_ = original;
}


void FlowGraphBuilder::VisitForInStatement(ForInStatement* stmt) {
  Visit(stmt->enumerable());

  JoinNode* join = new JoinNode();
  FlowGraph empty;
  BranchNode* branch = new BranchNode();
  FlowGraph original = graph_;
  graph_ = FlowGraph::Empty();
  Visit(stmt->body());

  original.Loop(join, &empty, branch, &graph_);
  graph_ = original;
}


void FlowGraphBuilder::VisitTryCatchStatement(TryCatchStatement* stmt) {
  SetStackOverflow();
}


void FlowGraphBuilder::VisitTryFinallyStatement(TryFinallyStatement* stmt) {
  SetStackOverflow();
}


void FlowGraphBuilder::VisitDebuggerStatement(DebuggerStatement* stmt) {
  graph_.AppendInstruction(stmt);
}


void FlowGraphBuilder::VisitFunctionLiteral(FunctionLiteral* expr) {
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitFunctionBoilerplateLiteral(
    FunctionBoilerplateLiteral* expr) {
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitConditional(Conditional* expr) {
  Visit(expr->condition());

  BranchNode* branch = new BranchNode();
  FlowGraph original = graph_;
  graph_ = FlowGraph::Empty();
  Visit(expr->then_expression());

  FlowGraph left = graph_;
  graph_ = FlowGraph::Empty();
  Visit(expr->else_expression());

  JoinNode* join = new JoinNode();
  original.Split(branch, &left, &graph_, join);
  graph_ = original;
}


void FlowGraphBuilder::VisitSlot(Slot* expr) {
  UNREACHABLE();
}


void FlowGraphBuilder::VisitVariableProxy(VariableProxy* expr) {
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitLiteral(Literal* expr) {
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitRegExpLiteral(RegExpLiteral* expr) {
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitObjectLiteral(ObjectLiteral* expr) {
  ZoneList<ObjectLiteral::Property*>* properties = expr->properties();
  for (int i = 0, len = properties->length(); i < len; i++) {
    Visit(properties->at(i)->value());
  }
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitArrayLiteral(ArrayLiteral* expr) {
  ZoneList<Expression*>* values = expr->values();
  for (int i = 0, len = values->length(); i < len; i++) {
    Visit(values->at(i));
  }
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitCatchExtensionObject(CatchExtensionObject* expr) {
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitAssignment(Assignment* expr) {
  Variable* var = expr->target()->AsVariableProxy()->AsVariable();
  Property* prop = expr->target()->AsProperty();
  // Left-hand side can be a variable or property (or reference error) but
  // not both.
  ASSERT(var == NULL || prop == NULL);
  if (var != NULL) {
    Visit(expr->value());
    if (var->IsStackAllocated()) definitions_.Add(expr);

  } else if (prop != NULL) {
    Visit(prop->obj());
    if (!prop->key()->IsPropertyName()) Visit(prop->key());
    Visit(expr->value());
  }
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitThrow(Throw* expr) {
  Visit(expr->exception());
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitProperty(Property* expr) {
  Visit(expr->obj());
  if (!expr->key()->IsPropertyName()) Visit(expr->key());
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitCall(Call* expr) {
  Visit(expr->expression());
  ZoneList<Expression*>* arguments = expr->arguments();
  for (int i = 0, len = arguments->length(); i < len; i++) {
    Visit(arguments->at(i));
  }
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitCallNew(CallNew* expr) {
  Visit(expr->expression());
  ZoneList<Expression*>* arguments = expr->arguments();
  for (int i = 0, len = arguments->length(); i < len; i++) {
    Visit(arguments->at(i));
  }
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitCallRuntime(CallRuntime* expr) {
  ZoneList<Expression*>* arguments = expr->arguments();
  for (int i = 0, len = arguments->length(); i < len; i++) {
    Visit(arguments->at(i));
  }
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitUnaryOperation(UnaryOperation* expr) {
  Visit(expr->expression());
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitCountOperation(CountOperation* expr) {
  Visit(expr->expression());
  Variable* var = expr->expression()->AsVariableProxy()->AsVariable();
  if (var != NULL && var->IsStackAllocated()) {
    definitions_.Add(expr);
  }
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitBinaryOperation(BinaryOperation* expr) {
  Visit(expr->left());

  switch (expr->op()) {
    case Token::COMMA:
      Visit(expr->right());
      break;

    case Token::OR: {
      BranchNode* branch = new BranchNode();
      FlowGraph original = graph_;
      graph_ = FlowGraph::Empty();
      Visit(expr->right());
      FlowGraph empty;
      JoinNode* join = new JoinNode();
      original.Split(branch, &empty, &graph_, join);
      graph_ = original;
      break;
    }

    case Token::AND: {
      BranchNode* branch = new BranchNode();
      FlowGraph original = graph_;
      graph_ = FlowGraph::Empty();
      Visit(expr->right());
      FlowGraph empty;
      JoinNode* join = new JoinNode();
      original.Split(branch, &graph_, &empty, join);
      graph_ = original;
      break;
    }

    case Token::BIT_OR:
    case Token::BIT_XOR:
    case Token::BIT_AND:
    case Token::SHL:
    case Token::SAR:
    case Token::SHR:
    case Token::ADD:
    case Token::SUB:
    case Token::MUL:
    case Token::DIV:
    case Token::MOD:
      Visit(expr->right());
      graph_.AppendInstruction(expr);
      break;

    default:
      UNREACHABLE();
  }
}


void FlowGraphBuilder::VisitCompareOperation(CompareOperation* expr) {
  Visit(expr->left());
  Visit(expr->right());
  graph_.AppendInstruction(expr);
}


void FlowGraphBuilder::VisitThisFunction(ThisFunction* expr) {
  graph_.AppendInstruction(expr);
}


void AstLabeler::Label(CompilationInfo* info) {
  info_ = info;
  VisitStatements(info_->function()->body());
}


void AstLabeler::VisitStatements(ZoneList<Statement*>* stmts) {
  for (int i = 0, len = stmts->length(); i < len; i++) {
    Visit(stmts->at(i));
  }
}


void AstLabeler::VisitDeclarations(ZoneList<Declaration*>* decls) {
  UNREACHABLE();
}


void AstLabeler::VisitBlock(Block* stmt) {
  VisitStatements(stmt->statements());
}


void AstLabeler::VisitExpressionStatement(
    ExpressionStatement* stmt) {
  Visit(stmt->expression());
}


void AstLabeler::VisitEmptyStatement(EmptyStatement* stmt) {
  // Do nothing.
}


void AstLabeler::VisitIfStatement(IfStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitContinueStatement(ContinueStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitBreakStatement(BreakStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitReturnStatement(ReturnStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitWithEnterStatement(
    WithEnterStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitWithExitStatement(WithExitStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitSwitchStatement(SwitchStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitDoWhileStatement(DoWhileStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitWhileStatement(WhileStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitForStatement(ForStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitForInStatement(ForInStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitTryCatchStatement(TryCatchStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitTryFinallyStatement(
    TryFinallyStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitDebuggerStatement(
    DebuggerStatement* stmt) {
  UNREACHABLE();
}


void AstLabeler::VisitFunctionLiteral(FunctionLiteral* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitFunctionBoilerplateLiteral(
    FunctionBoilerplateLiteral* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitConditional(Conditional* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitSlot(Slot* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitVariableProxy(VariableProxy* expr) {
  expr->set_num(next_number_++);
  Variable* var = expr->var();
  if (var->is_global() && !var->is_this()) {
    info_->set_has_globals(true);
  }
}


void AstLabeler::VisitLiteral(Literal* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitRegExpLiteral(RegExpLiteral* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitObjectLiteral(ObjectLiteral* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitArrayLiteral(ArrayLiteral* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitCatchExtensionObject(
    CatchExtensionObject* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitAssignment(Assignment* expr) {
  Property* prop = expr->target()->AsProperty();
  ASSERT(prop != NULL);
  ASSERT(prop->key()->IsPropertyName());
  VariableProxy* proxy = prop->obj()->AsVariableProxy();
  USE(proxy);
  ASSERT(proxy != NULL && proxy->var()->is_this());
  info()->set_has_this_properties(true);

  prop->obj()->set_num(AstNode::kNoNumber);
  prop->key()->set_num(AstNode::kNoNumber);
  Visit(expr->value());
  expr->set_num(next_number_++);
}


void AstLabeler::VisitThrow(Throw* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitProperty(Property* expr) {
  ASSERT(expr->key()->IsPropertyName());
  VariableProxy* proxy = expr->obj()->AsVariableProxy();
  USE(proxy);
  ASSERT(proxy != NULL && proxy->var()->is_this());
  info()->set_has_this_properties(true);

  expr->obj()->set_num(AstNode::kNoNumber);
  expr->key()->set_num(AstNode::kNoNumber);
  expr->set_num(next_number_++);
}


void AstLabeler::VisitCall(Call* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitCallNew(CallNew* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitCallRuntime(CallRuntime* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitUnaryOperation(UnaryOperation* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitCountOperation(CountOperation* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitBinaryOperation(BinaryOperation* expr) {
  Visit(expr->left());
  Visit(expr->right());
  expr->set_num(next_number_++);
}


void AstLabeler::VisitCompareOperation(CompareOperation* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitThisFunction(ThisFunction* expr) {
  UNREACHABLE();
}


void AstLabeler::VisitDeclaration(Declaration* decl) {
  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();
}


#ifdef DEBUG

// Print a textual representation of an instruction in a flow graph.  Using
// the AstVisitor is overkill because there is no recursion here.  It is
// only used for printing in debug mode.
class TextInstructionPrinter: public AstVisitor {
 public:
  TextInstructionPrinter() {}

 private:
  // AST node visit functions.
#define DECLARE_VISIT(type) virtual void Visit##type(type* node);
  AST_NODE_LIST(DECLARE_VISIT)
#undef DECLARE_VISIT

  DISALLOW_COPY_AND_ASSIGN(TextInstructionPrinter);
};


void TextInstructionPrinter::VisitDeclaration(Declaration* decl) {
  UNREACHABLE();
}


void TextInstructionPrinter::VisitBlock(Block* stmt) {
  PrintF("Block");
}


void TextInstructionPrinter::VisitExpressionStatement(
    ExpressionStatement* stmt) {
  PrintF("ExpressionStatement");
}


void TextInstructionPrinter::VisitEmptyStatement(EmptyStatement* stmt) {
  PrintF("EmptyStatement");
}


void TextInstructionPrinter::VisitIfStatement(IfStatement* stmt) {
  PrintF("IfStatement");
}


void TextInstructionPrinter::VisitContinueStatement(ContinueStatement* stmt) {
  UNREACHABLE();
}


void TextInstructionPrinter::VisitBreakStatement(BreakStatement* stmt) {
  UNREACHABLE();
}


void TextInstructionPrinter::VisitReturnStatement(ReturnStatement* stmt) {
  PrintF("return @%d", stmt->expression()->num());
}


void TextInstructionPrinter::VisitWithEnterStatement(WithEnterStatement* stmt) {
  PrintF("WithEnterStatement");
}


void TextInstructionPrinter::VisitWithExitStatement(WithExitStatement* stmt) {
  PrintF("WithExitStatement");
}


void TextInstructionPrinter::VisitSwitchStatement(SwitchStatement* stmt) {
  UNREACHABLE();
}


void TextInstructionPrinter::VisitDoWhileStatement(DoWhileStatement* stmt) {
  PrintF("DoWhileStatement");
}


void TextInstructionPrinter::VisitWhileStatement(WhileStatement* stmt) {
  PrintF("WhileStatement");
}


void TextInstructionPrinter::VisitForStatement(ForStatement* stmt) {
  PrintF("ForStatement");
}


void TextInstructionPrinter::VisitForInStatement(ForInStatement* stmt) {
  PrintF("ForInStatement");
}


void TextInstructionPrinter::VisitTryCatchStatement(TryCatchStatement* stmt) {
  UNREACHABLE();
}


void TextInstructionPrinter::VisitTryFinallyStatement(
    TryFinallyStatement* stmt) {
  UNREACHABLE();
}


void TextInstructionPrinter::VisitDebuggerStatement(DebuggerStatement* stmt) {
  PrintF("DebuggerStatement");
}


void TextInstructionPrinter::VisitFunctionLiteral(FunctionLiteral* expr) {
  PrintF("FunctionLiteral");
}


void TextInstructionPrinter::VisitFunctionBoilerplateLiteral(
    FunctionBoilerplateLiteral* expr) {
  PrintF("FunctionBoilerplateLiteral");
}


void TextInstructionPrinter::VisitConditional(Conditional* expr) {
  PrintF("Conditional");
}


void TextInstructionPrinter::VisitSlot(Slot* expr) {
  UNREACHABLE();
}


void TextInstructionPrinter::VisitVariableProxy(VariableProxy* expr) {
  Variable* var = expr->AsVariable();
  if (var != NULL) {
    SmartPointer<char> name = var->name()->ToCString();
    PrintF("%s", *name);
  } else {
    ASSERT(expr->AsProperty() != NULL);
    VisitProperty(expr->AsProperty());
  }
}


void TextInstructionPrinter::VisitLiteral(Literal* expr) {
  expr->handle()->ShortPrint();
}


void TextInstructionPrinter::VisitRegExpLiteral(RegExpLiteral* expr) {
  PrintF("RegExpLiteral");
}


void TextInstructionPrinter::VisitObjectLiteral(ObjectLiteral* expr) {
  PrintF("ObjectLiteral");
}


void TextInstructionPrinter::VisitArrayLiteral(ArrayLiteral* expr) {
  PrintF("ArrayLiteral");
}


void TextInstructionPrinter::VisitCatchExtensionObject(
    CatchExtensionObject* expr) {
  PrintF("CatchExtensionObject");
}


void TextInstructionPrinter::VisitAssignment(Assignment* expr) {
  Variable* var = expr->target()->AsVariableProxy()->AsVariable();
  Property* prop = expr->target()->AsProperty();

  if (var != NULL) {
    SmartPointer<char> name = var->name()->ToCString();
    PrintF("%s %s @%d",
           *name,
           Token::String(expr->op()),
           expr->value()->num());
  } else if (prop != NULL) {
    if (prop->key()->IsPropertyName()) {
      PrintF("@%d.", prop->obj()->num());
      ASSERT(prop->key()->AsLiteral() != NULL);
      prop->key()->AsLiteral()->handle()->Print();
      PrintF(" %s @%d",
             Token::String(expr->op()),
             expr->value()->num());
    } else {
      PrintF("@%d[@%d] %s @%d",
             prop->obj()->num(),
             prop->key()->num(),
             Token::String(expr->op()),
             expr->value()->num());
    }
  } else {
    // Throw reference error.
    Visit(expr->target());
  }
}


void TextInstructionPrinter::VisitThrow(Throw* expr) {
  PrintF("throw @%d", expr->exception()->num());
}


void TextInstructionPrinter::VisitProperty(Property* expr) {
  if (expr->key()->IsPropertyName()) {
    PrintF("@%d.", expr->obj()->num());
    ASSERT(expr->key()->AsLiteral() != NULL);
    expr->key()->AsLiteral()->handle()->Print();
  } else {
    PrintF("@%d[@%d]", expr->obj()->num(), expr->key()->num());
  }
}


void TextInstructionPrinter::VisitCall(Call* expr) {
  PrintF("@%d(", expr->expression()->num());
  ZoneList<Expression*>* arguments = expr->arguments();
  for (int i = 0, len = arguments->length(); i < len; i++) {
    if (i != 0) PrintF(", ");
    PrintF("@%d", arguments->at(i)->num());
  }
  PrintF(")");
}


void TextInstructionPrinter::VisitCallNew(CallNew* expr) {
  PrintF("new @%d(", expr->expression()->num());
  ZoneList<Expression*>* arguments = expr->arguments();
  for (int i = 0, len = arguments->length(); i < len; i++) {
    if (i != 0) PrintF(", ");
    PrintF("@%d", arguments->at(i)->num());
  }
  PrintF(")");
}


void TextInstructionPrinter::VisitCallRuntime(CallRuntime* expr) {
  SmartPointer<char> name = expr->name()->ToCString();
  PrintF("%s(", *name);
  ZoneList<Expression*>* arguments = expr->arguments();
  for (int i = 0, len = arguments->length(); i < len; i++) {
    if (i != 0) PrintF(", ");
    PrintF("@%d", arguments->at(i)->num());
  }
  PrintF(")");
}


void TextInstructionPrinter::VisitUnaryOperation(UnaryOperation* expr) {
  PrintF("%s(@%d)", Token::String(expr->op()), expr->expression()->num());
}


void TextInstructionPrinter::VisitCountOperation(CountOperation* expr) {
  if (expr->is_prefix()) {
    PrintF("%s@%d", Token::String(expr->op()), expr->expression()->num());
  } else {
    PrintF("@%d%s", expr->expression()->num(), Token::String(expr->op()));
  }
}


void TextInstructionPrinter::VisitBinaryOperation(BinaryOperation* expr) {
  ASSERT(expr->op() != Token::COMMA);
  ASSERT(expr->op() != Token::OR);
  ASSERT(expr->op() != Token::AND);
  PrintF("@%d %s @%d",
         expr->left()->num(),
         Token::String(expr->op()),
         expr->right()->num());
}


void TextInstructionPrinter::VisitCompareOperation(CompareOperation* expr) {
  PrintF("@%d %s @%d",
         expr->left()->num(),
         Token::String(expr->op()),
         expr->right()->num());
}


void TextInstructionPrinter::VisitThisFunction(ThisFunction* expr) {
  PrintF("ThisFunction");
}


static int node_count = 0;
static int instruction_count = 0;


void Node::AssignNumbers() {
  set_number(node_count++);
}


void BlockNode::AssignNumbers() {
  set_number(node_count++);
  for (int i = 0, len = instructions_.length(); i < len; i++) {
    instructions_[i]->set_num(instruction_count++);
  }
}


void EntryNode::PrintText() {
  PrintF("L%d: Entry\n", number());
  PrintF("goto L%d\n\n", successor_->number());
}

void ExitNode::PrintText() {
  PrintF("L%d: Exit\n\n", number());
}


void BlockNode::PrintText() {
  // Print the instructions in the block.
  PrintF("L%d: Block\n", number());
  TextInstructionPrinter printer;
  for (int i = 0, len = instructions_.length(); i < len; i++) {
    PrintF("%d ", instructions_[i]->num());
    printer.Visit(instructions_[i]);
    PrintF("\n");
  }
  PrintF("goto L%d\n\n", successor_->number());
}


void BranchNode::PrintText() {
  PrintF("L%d: Branch\n", number());
  PrintF("goto (L%d, L%d)\n\n", successor0_->number(), successor1_->number());
}


void JoinNode::PrintText() {
  PrintF("L%d: Join(", number());
  for (int i = 0, len = predecessors_.length(); i < len; i++) {
    if (i != 0) PrintF(", ");
    PrintF("L%d", predecessors_[i]->number());
  }
  PrintF(")\ngoto L%d\n\n", successor_->number());
}


void FlowGraph::PrintText(ZoneList<Node*>* postorder) {
  PrintF("\n========\n");

  // Number nodes and instructions in reverse postorder.
  node_count = 0;
  instruction_count = 0;
  for (int i = postorder->length() - 1; i >= 0; i--) {
    postorder->at(i)->AssignNumbers();
  }

  // Print basic blocks in reverse postorder.
  for (int i = postorder->length() - 1; i >= 0; i--) {
    postorder->at(i)->PrintText();
  }
}


#endif  // defined(DEBUG)


} }  // namespace v8::internal