Move flow graph and helper classes to their own file.

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
@@ skipping 10 matching lines @@
 // 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"
+#include "flow-graph.h"
 #include "scopes.h"
 
 namespace v8 {
 namespace internal {
 
 
 #ifdef DEBUG
 void BitVector::Print() {
   bool first = true;
   PrintF("{");
   for (int i = 0; i < length(); i++) {
     if (Contains(i)) {
       if (!first) PrintF(",");
       first = false;
       PrintF("%d");
     }
   }
   PrintF("}");
 }
 #endif
 
 
-void FlowGraph::AppendInstruction(AstNode* instruction) {
-  // Add a (non-null) AstNode to the end of the graph fragment.
-  ASSERT(instruction != NULL);
-  if (exit()->IsExitNode()) return;
-  if (!exit()->IsBlockNode()) AppendNode(new BlockNode());
-  BlockNode::cast(exit())->AddInstruction(instruction);
-}
-
-
-void FlowGraph::AppendNode(Node* node) {
-  // Add a node to the end of the graph.  An empty block is added to
-  // maintain edge-split form (that no join nodes or exit nodes as
-  // successors to branch nodes).
-  ASSERT(node != NULL);
-  if (exit()->IsExitNode()) return;
-  if (exit()->IsBranchNode() && (node->IsJoinNode() || node->IsExitNode())) {
-    AppendNode(new BlockNode());
-  }
-  exit()->AddSuccessor(node);
-  node->AddPredecessor(exit());
-  exit_ = node;
-}
-
-
-void FlowGraph::AppendGraph(FlowGraph* graph) {
-  // Add a flow graph fragment to the end of this one.  An empty block is
-  // added to maintain edge-split form (that no join nodes or exit nodes as
-  // successors to branch nodes).
-  ASSERT(graph != NULL);
-  if (exit()->IsExitNode()) return;
-  Node* node = graph->entry();
-  if (exit()->IsBranchNode() && (node->IsJoinNode() || node->IsExitNode())) {
-    AppendNode(new BlockNode());
-  }
-  exit()->AddSuccessor(node);
-  node->AddPredecessor(exit());
-  exit_ = graph->exit();
-}
-
-
-void FlowGraph::Split(BranchNode* branch,
-                      FlowGraph* left,
-                      FlowGraph* right,
-                      JoinNode* join) {
-  // Add the branch node, left flowgraph, join node.
-  AppendNode(branch);
-  AppendGraph(left);
-  AppendNode(join);
-
-  // Splice in the right flowgraph.
-  right->AppendNode(join);
-  branch->AddSuccessor(right->entry());
-  right->entry()->AddPredecessor(branch);
-}
-
-
-void FlowGraph::Loop(JoinNode* join,
-                     FlowGraph* condition,
-                     BranchNode* branch,
-                     FlowGraph* body) {
-  // Add the join, condition and branch.  Add join's predecessors in
-  // left-to-right order.
-  AppendNode(join);
-  body->AppendNode(join);
-  AppendGraph(condition);
-  AppendNode(branch);
-
-  // Splice in the body flowgraph.
-  branch->AddSuccessor(body->entry());
-  body->entry()->AddPredecessor(branch);
-}
-
-
-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 (!successor1_->IsMarkedWith(mark)) {
-    successor1_->MarkWith(mark);
-    successor1_->Traverse(mark, preorder, postorder);
-  }
-  if (!successor0_->IsMarkedWith(mark)) {
-    successor0_->MarkWith(mark);
-    successor0_->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) {
-  global_exit_ = new ExitNode();
-  VisitStatements(lit->body());
-
-  if (HasStackOverflow()) return;
-
-  // The graph can end with a branch node (if the function ended with a
-  // loop).  Maintain edge-split form (no join nodes or exit nodes as
-  // successors to branch nodes).
-  if (graph_.exit()->IsBranchNode()) graph_.AppendNode(new BlockNode());
-  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_);
-}
-
-
-// This function peels off one iteration of a for-loop. The return value
-// is either a block statement containing the peeled loop or NULL in case
-// there is a stack overflow.
-static Statement* PeelForLoop(ForStatement* stmt) {
-  // Mark this for-statement as processed.
-  stmt->set_peel_this_loop(false);
-
-  // Create new block containing the init statement of the for-loop and
-  // an if-statement containing the peeled iteration and the original
-  // loop without the init-statement.
-  Block* block = new Block(NULL, 2, false);
-  if (stmt->init() != NULL) {
-    Statement* init = stmt->init();
-    // The init statement gets the statement position of the for-loop
-    // to make debugging of peeled loops possible.
-    init->set_statement_pos(stmt->statement_pos());
-    block->AddStatement(init);
-  }
-
-  // Copy the condition.
-  CopyAstVisitor copy_visitor;
-  Expression* cond_copy = stmt->cond() != NULL
-      ? copy_visitor.DeepCopyExpr(stmt->cond())
-      : new Literal(Factory::true_value());
-  if (copy_visitor.HasStackOverflow()) return NULL;
-
-  // Construct a block with the peeled body and the rest of the for-loop.
-  Statement* body_copy = copy_visitor.DeepCopyStmt(stmt->body());
-  if (copy_visitor.HasStackOverflow()) return NULL;
-
-  Statement* next_copy = stmt->next() != NULL
-      ? copy_visitor.DeepCopyStmt(stmt->next())
-      : new EmptyStatement();
-  if (copy_visitor.HasStackOverflow()) return NULL;
-
-  Block* peeled_body = new Block(NULL, 3, false);
-  peeled_body->AddStatement(body_copy);
-  peeled_body->AddStatement(next_copy);
-  peeled_body->AddStatement(stmt);
-
-  // Remove the duplicated init statement from the for-statement.
-  stmt->set_init(NULL);
-
-  // Create new test at the top and add it to the newly created block.
-  IfStatement* test = new IfStatement(cond_copy,
-                                      peeled_body,
-                                      new EmptyStatement());
-  block->AddStatement(test);
-  return block;
-}
-
-
-void FlowGraphBuilder::VisitStatements(ZoneList<Statement*>* stmts) {
-  for (int i = 0, len = stmts->length(); i < len; i++) {
-    stmts->at(i) = ProcessStatement(stmts->at(i));
-  }
-}
-
-
-Statement* FlowGraphBuilder::ProcessStatement(Statement* stmt) {
-  if (FLAG_loop_peeling &&
-      stmt->AsForStatement() != NULL &&
-      stmt->AsForStatement()->peel_this_loop()) {
-    Statement* tmp_stmt = PeelForLoop(stmt->AsForStatement());
-    if (tmp_stmt == NULL) {
-      SetStackOverflow();
-    } else {
-      stmt = tmp_stmt;
-    }
-  }
-  Visit(stmt);
-  return stmt;
-}
-
-
-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();
-  stmt->set_then_statement(ProcessStatement(stmt->then_statement()));
-
-  FlowGraph left = graph_;
-  graph_ = FlowGraph::Empty();
-  stmt->set_else_statement(ProcessStatement(stmt->else_statement()));
-
-  if (HasStackOverflow()) return;
-  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) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitWithEnterStatement(WithEnterStatement* stmt) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitWithExitStatement(WithExitStatement* stmt) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitSwitchStatement(SwitchStatement* stmt) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitDoWhileStatement(DoWhileStatement* stmt) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitWhileStatement(WhileStatement* stmt) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitForStatement(ForStatement* stmt) {
-  if (stmt->init() != NULL) stmt->set_init(ProcessStatement(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();
-  stmt->set_body(ProcessStatement(stmt->body()));
-
-  if (stmt->next() != NULL) stmt->set_next(ProcessStatement(stmt->next()));
-
-  if (HasStackOverflow()) return;
-  original.Loop(join, &condition, branch, &graph_);
-  graph_ = original;
-}
-
-
-void FlowGraphBuilder::VisitForInStatement(ForInStatement* stmt) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitTryCatchStatement(TryCatchStatement* stmt) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitTryFinallyStatement(TryFinallyStatement* stmt) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitDebuggerStatement(DebuggerStatement* stmt) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitFunctionLiteral(FunctionLiteral* expr) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitSharedFunctionInfoLiteral(
-    SharedFunctionInfoLiteral* expr) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitConditional(Conditional* expr) {
-  SetStackOverflow();
-}
-
-
-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) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitObjectLiteral(ObjectLiteral* expr) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitArrayLiteral(ArrayLiteral* expr) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitCatchExtensionObject(CatchExtensionObject* expr) {
-  SetStackOverflow();
-}
-
-
-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) {
-    if (expr->is_compound()) Visit(expr->target());
-    Visit(expr->value());
-    if (var->IsStackAllocated()) {
-      // The first definition in the body is numbered n, where n is the
-      // number of parameters and stack-allocated locals.
-      expr->set_num(body_definitions_.length() + variable_count_);
-      body_definitions_.Add(expr);
-    }
-
-  } else if (prop != NULL) {
-    Visit(prop->obj());
-    if (!prop->key()->IsPropertyName()) Visit(prop->key());
-    Visit(expr->value());
-  }
-
-  if (HasStackOverflow()) return;
-  graph_.AppendInstruction(expr);
-}
-
-
-void FlowGraphBuilder::VisitThrow(Throw* expr) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitProperty(Property* expr) {
-  Visit(expr->obj());
-  if (!expr->key()->IsPropertyName()) Visit(expr->key());
-
-  if (HasStackOverflow()) return;
-  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));
-  }
-
-  if (HasStackOverflow()) return;
-  graph_.AppendInstruction(expr);
-}
-
-
-void FlowGraphBuilder::VisitCallNew(CallNew* expr) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitCallRuntime(CallRuntime* expr) {
-  SetStackOverflow();
-}
-
-
-void FlowGraphBuilder::VisitUnaryOperation(UnaryOperation* expr) {
-  switch (expr->op()) {
-    case Token::NOT:
-    case Token::BIT_NOT:
-    case Token::DELETE:
-    case Token::TYPEOF:
-    case Token::VOID:
-      SetStackOverflow();
-      break;
-
-    case Token::ADD:
-    case Token::SUB:
-      Visit(expr->expression());
-      if (HasStackOverflow()) return;
-      graph_.AppendInstruction(expr);
-      break;
-
-    default:
-      UNREACHABLE();
-  }
-}
-
-
-void FlowGraphBuilder::VisitCountOperation(CountOperation* expr) {
-  Visit(expr->expression());
-  Variable* var = expr->expression()->AsVariableProxy()->AsVariable();
-  if (var != NULL && var->IsStackAllocated()) {
-    // The first definition in the body is numbered n, where n is the number
-    // of parameters and stack-allocated locals.
-    expr->set_num(body_definitions_.length() + variable_count_);
-    body_definitions_.Add(expr);
-  }
-
-  if (HasStackOverflow()) return;
-  graph_.AppendInstruction(expr);
-}
-
-
-void FlowGraphBuilder::VisitBinaryOperation(BinaryOperation* expr) {
-  switch (expr->op()) {
-    case Token::COMMA:
-    case Token::OR:
-    case Token::AND:
-      SetStackOverflow();
-      break;
-
-    case Token::BIT_OR:
-    case Token::BIT_XOR:
-    case Token::BIT_AND:
-    case Token::SHL:
-    case Token::SHR:
-    case Token::ADD:
-    case Token::SUB:
-    case Token::MUL:
-    case Token::DIV:
-    case Token::MOD:
-    case Token::SAR:
-      Visit(expr->left());
-      Visit(expr->right());
-      if (HasStackOverflow()) return;
-      graph_.AppendInstruction(expr);
-      break;
-
-    default:
-      UNREACHABLE();
-  }
-}
-
-
-void FlowGraphBuilder::VisitCompareOperation(CompareOperation* expr) {
-  switch (expr->op()) {
-    case Token::EQ:
-    case Token::NE:
-    case Token::EQ_STRICT:
-    case Token::NE_STRICT:
-    case Token::INSTANCEOF:
-    case Token::IN:
-      SetStackOverflow();
-      break;
-
-    case Token::LT:
-    case Token::GT:
-    case Token::LTE:
-    case Token::GTE:
-      Visit(expr->left());
-      Visit(expr->right());
-      if (HasStackOverflow()) return;
-      graph_.AppendInstruction(expr);
-      break;
-
-    default:
-      UNREACHABLE();
-  }
-}
-
-
-void FlowGraphBuilder::VisitThisFunction(ThisFunction* expr) {
-  SetStackOverflow();
-}
-
-
 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));
   }
@@ skipping 675 matching lines @@
   // Nothing to do.
   ASSERT(av_.IsEmpty());
 }
 
 
 void AssignedVariablesAnalyzer::VisitDeclaration(Declaration* decl) {
   UNREACHABLE();
 }
 
 
+int ReachingDefinitions::IndexFor(Variable* var, int variable_count) {
+  // Parameters are numbered left-to-right from the beginning of the bit
+  // set.  Stack-allocated locals are allocated right-to-left from the end.
+  ASSERT(var != NULL && var->IsStackAllocated());
+  Slot* slot = var->slot();
+  if (slot->type() == Slot::PARAMETER) {
+    return slot->index();
+  } else {
+    return (variable_count - 1) - slot->index();
+  }
+}
+
+
+void Node::InitializeReachingDefinitions(int definition_count,
+                                         List<BitVector*>* variables,
+                                         WorkList<Node>* worklist,
+                                         bool mark) {
+  ASSERT(!IsMarkedWith(mark));
+  rd_.Initialize(definition_count);
+  MarkWith(mark);
+  worklist->Insert(this);
+}
+
+
+void BlockNode::InitializeReachingDefinitions(int definition_count,
+                                              List<BitVector*>* variables,
+                                              WorkList<Node>* worklist,
+                                              bool mark) {
+  ASSERT(!IsMarkedWith(mark));
+  int instruction_count = instructions_.length();
+  int variable_count = variables->length();
+
+  rd_.Initialize(definition_count);
+  // The RD_in set for the entry node has a definition for each parameter
+  // and local.
+  if (predecessor_ == NULL) {
+    for (int i = 0; i < variable_count; i++) rd_.rd_in()->Add(i);
+  }
+
+  for (int i = 0; i < instruction_count; i++) {
+    Expression* expr = instructions_[i]->AsExpression();
+    if (expr == NULL) continue;
+    Variable* var = expr->AssignedVariable();
+    if (var == NULL || !var->IsStackAllocated()) continue;
+
+    // All definitions of this variable are killed.
+    BitVector* def_set =
+        variables->at(ReachingDefinitions::IndexFor(var, variable_count));
+    rd_.kill()->Union(*def_set);
+
+    // All previously generated definitions are not generated.
+    rd_.gen()->Subtract(*def_set);
+
+    // This one is generated.
+    rd_.gen()->Add(expr->num());
+  }
+
+  // Add all blocks except the entry node to the worklist.
+  if (predecessor_ != NULL) {
+    MarkWith(mark);
+    worklist->Insert(this);
+  }
+}
+
+
+void ExitNode::ComputeRDOut(BitVector* result) {
+  // Should not be the predecessor of any node.
+  UNREACHABLE();
+}
+
+
+void BlockNode::ComputeRDOut(BitVector* result) {
+  // All definitions reaching this block ...
+  *result = *rd_.rd_in();
+  // ... except those killed by the block ...
+  result->Subtract(*rd_.kill());
+  // ... but including those generated by the block.
+  result->Union(*rd_.gen());
+}
+
+
+void BranchNode::ComputeRDOut(BitVector* result) {
+  // Branch nodes don't kill or generate definitions.
+  *result = *rd_.rd_in();
+}
+
+
+void JoinNode::ComputeRDOut(BitVector* result) {
+  // Join nodes don't kill or generate definitions.
+  *result = *rd_.rd_in();
+}
+
+
+void ExitNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
+  // The exit node has no successors so we can just update in place.  New
+  // RD_in is the union over all predecessors.
+  int definition_count = rd_.rd_in()->length();
+  rd_.rd_in()->Clear();
+
+  BitVector temp(definition_count);
+  for (int i = 0, len = predecessors_.length(); i < len; i++) {
+    // Because ComputeRDOut always overwrites temp and its value is
+    // always read out before calling ComputeRDOut again, we do not
+    // have to clear it on each iteration of the loop.
+    predecessors_[i]->ComputeRDOut(&temp);
+    rd_.rd_in()->Union(temp);
+  }
+}
+
+
+void BlockNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
+  // The entry block has no predecessor.  Its RD_in does not change.
+  if (predecessor_ == NULL) return;
+
+  BitVector new_rd_in(rd_.rd_in()->length());
+  predecessor_->ComputeRDOut(&new_rd_in);
+
+  if (rd_.rd_in()->Equals(new_rd_in)) return;
+
+  // Update RD_in.
+  *rd_.rd_in() = new_rd_in;
+  // Add the successor to the worklist if not already present.
+  if (!successor_->IsMarkedWith(mark)) {
+    successor_->MarkWith(mark);
+    worklist->Insert(successor_);
+  }
+}
+
+
+void BranchNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
+  BitVector new_rd_in(rd_.rd_in()->length());
+  predecessor_->ComputeRDOut(&new_rd_in);
+
+  if (rd_.rd_in()->Equals(new_rd_in)) return;
+
+  // Update RD_in.
+  *rd_.rd_in() = new_rd_in;
+  // Add the successors to the worklist if not already present.
+  if (!successor0_->IsMarkedWith(mark)) {
+    successor0_->MarkWith(mark);
+    worklist->Insert(successor0_);
+  }
+  if (!successor1_->IsMarkedWith(mark)) {
+    successor1_->MarkWith(mark);
+    worklist->Insert(successor1_);
+  }
+}
+
+
+void JoinNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
+  int definition_count = rd_.rd_in()->length();
+  BitVector new_rd_in(definition_count);
+
+  // New RD_in is the union over all predecessors.
+  BitVector temp(definition_count);
+  for (int i = 0, len = predecessors_.length(); i < len; i++) {
+    predecessors_[i]->ComputeRDOut(&temp);
+    new_rd_in.Union(temp);
+  }
+
+  if (rd_.rd_in()->Equals(new_rd_in)) return;
+
+  // Update RD_in.
+  *rd_.rd_in() = new_rd_in;
+  // Add the successor to the worklist if not already present.
+  if (!successor_->IsMarkedWith(mark)) {
+    successor_->MarkWith(mark);
+    worklist->Insert(successor_);
+  }
+}
+
+
+void Node::PropagateReachingDefinitions(List<BitVector*>* variables) {
+  // Nothing to do.
+}
+
+
+void BlockNode::PropagateReachingDefinitions(List<BitVector*>* variables) {
+  // Propagate RD_in from the start of the block to all the variable
+  // references.
+  int variable_count = variables->length();
+  BitVector rd = *rd_.rd_in();
+  for (int i = 0, len = instructions_.length(); i < len; i++) {
+    Expression* expr = instructions_[i]->AsExpression();
+    if (expr == NULL) continue;
+
+    // Look for a variable reference to record its reaching definitions.
+    VariableProxy* proxy = expr->AsVariableProxy();
+    if (proxy == NULL) {
+      // Not a VariableProxy?  Maybe it's a count operation.
+      CountOperation* count_operation = expr->AsCountOperation();
+      if (count_operation != NULL) {
+        proxy = count_operation->expression()->AsVariableProxy();
+      }
+    }
+    if (proxy == NULL) {
+      // OK, Maybe it's a compound assignment.
+      Assignment* assignment = expr->AsAssignment();
+      if (assignment != NULL && assignment->is_compound()) {
+        proxy = assignment->target()->AsVariableProxy();
+      }
+    }
+
+    if (proxy != NULL &&
+        proxy->var()->IsStackAllocated() &&
+        !proxy->var()->is_this()) {
+      // All definitions for this variable.
+      BitVector* definitions =
+          variables->at(ReachingDefinitions::IndexFor(proxy->var(),
+                                                      variable_count));
+      BitVector* reaching_definitions = new BitVector(*definitions);
+      // Intersected with all definitions (of any variable) reaching this
+      // instruction.
+      reaching_definitions->Intersect(rd);
+      proxy->set_reaching_definitions(reaching_definitions);
+    }
+
+    // It may instead (or also) be a definition.  If so update the running
+    // value of reaching definitions for the block.
+    Variable* var = expr->AssignedVariable();
+    if (var == NULL || !var->IsStackAllocated()) continue;
+
+    // All definitions of this variable are killed.
+    BitVector* def_set =
+        variables->at(ReachingDefinitions::IndexFor(var, variable_count));
+    rd.Subtract(*def_set);
+    // This definition is generated.
+    rd.Add(expr->num());
+  }
+}
+
+
+void ReachingDefinitions::Compute() {
+  // The definitions in the body plus an implicit definition for each
+  // variable at function entry.
+  int definition_count = body_definitions_->length() + variable_count_;
+  int node_count = postorder_->length();
+
+  // Step 1: For each stack-allocated variable, identify the set of all its
+  // definitions.
+  List<BitVector*> variables;
+  for (int i = 0; i < variable_count_; i++) {
+    // Add the initial definition for each variable.
+    BitVector* initial = new BitVector(definition_count);
+    initial->Add(i);
+    variables.Add(initial);
+  }
+  for (int i = 0, len = body_definitions_->length(); i < len; i++) {
+    // Account for each definition in the body as a definition of the
+    // defined variable.
+    Variable* var = body_definitions_->at(i)->AssignedVariable();
+    variables[IndexFor(var, variable_count_)]->Add(i + variable_count_);
+  }
+
+  // Step 2: Compute KILL and GEN for each block node, initialize RD_in for
+  // all nodes, and mark and add all nodes to the worklist in reverse
+  // postorder.  All nodes should currently have the same mark.
+  bool mark = postorder_->at(0)->IsMarkedWith(false);  // Negation of current.
+  WorkList<Node> worklist(node_count);
+  for (int i = node_count - 1; i >= 0; i--) {
+    postorder_->at(i)->InitializeReachingDefinitions(definition_count,
+                                                     &variables,
+                                                     &worklist,
+                                                     mark);
+  }
+
+  // Step 3: Until the worklist is empty, remove an item compute and update
+  // its rd_in based on its predecessor's rd_out.  If rd_in has changed, add
+  // all necessary successors to the worklist.
+  while (!worklist.is_empty()) {
+    Node* node = worklist.Remove();
+    node->MarkWith(!mark);
+    node->UpdateRDIn(&worklist, mark);
+  }
+
+  // Step 4: Based on RD_in for block nodes, propagate reaching definitions
+  // to all variable uses in the block.
+  for (int i = 0; i < node_count; i++) {
+    postorder_->at(i)->PropagateReachingDefinitions(&variables);
+  }
+}
+
+
+bool TypeAnalyzer::IsPrimitiveDef(int def_num) {
+  if (def_num < param_count_) return false;
+  if (def_num < variable_count_) return true;
+  return body_definitions_->at(def_num - variable_count_)->IsPrimitive();
+}
+
+
+void TypeAnalyzer::Compute() {
+  bool changed;
+  int count = 0;
+
+  do {
+    changed = false;
+
+    if (FLAG_print_graph_text) {
+      PrintF("TypeAnalyzer::Compute - iteration %d\n", count++);
+    }
+
+    for (int i = postorder_->length() - 1; i >= 0; --i) {
+      Node* node = postorder_->at(i);
+      if (node->IsBlockNode()) {
+        BlockNode* block = BlockNode::cast(node);
+        for (int j = 0; j < block->instructions()->length(); j++) {
+          Expression* expr = block->instructions()->at(j)->AsExpression();
+          if (expr != NULL) {
+            // For variable uses: Compute new type from reaching definitions.
+            VariableProxy* proxy = expr->AsVariableProxy();
+            if (proxy != NULL && proxy->reaching_definitions() != NULL) {
+              BitVector* rd = proxy->reaching_definitions();
+              bool prim_type = true;
+              // TODO(fsc): A sparse set representation of reaching
+              // definitions would speed up iterating here.
+              for (int k = 0; k < rd->length(); k++) {
+                if (rd->Contains(k) && !IsPrimitiveDef(k)) {
+                  prim_type = false;
+                  break;
+                }
+              }
+              // Reset changed flag if new type information was computed.
+              if (prim_type != proxy->IsPrimitive()) {
+                changed = true;
+                proxy->SetIsPrimitive(prim_type);
+              }
+            }
+          }
+        }
+      }
+    }
+  } while (changed);
+}
+
+
+void Node::MarkCriticalInstructions(
+    List<AstNode*>* stack,
+    ZoneList<Expression*>* body_definitions,
+    int variable_count) {
+}
+
+
+void BlockNode::MarkCriticalInstructions(
+    List<AstNode*>* stack,
+    ZoneList<Expression*>* body_definitions,
+    int variable_count) {
+  for (int i = instructions_.length() - 1; i >= 0; i--) {
+    // Only expressions can appear in the flow graph for now.
+    Expression* expr = instructions_[i]->AsExpression();
+    if (expr != NULL && !expr->is_live() &&
+        (expr->is_loop_condition() || expr->IsCritical())) {
+      expr->mark_as_live();
+      expr->ProcessNonLiveChildren(stack, body_definitions, variable_count);
+    }
+  }
+}
+
+
+void MarkLiveCode(ZoneList<Node*>* nodes,
+                  ZoneList<Expression*>* body_definitions,
+                  int variable_count) {
+  List<AstNode*> stack(20);
+
+  // Mark the critical AST nodes as live; mark their dependencies and
+  // add them to the marking stack.
+  for (int i = nodes->length() - 1; i >= 0; i--) {
+    nodes->at(i)->MarkCriticalInstructions(&stack, body_definitions,
+                                           variable_count);
+  }
+
+  // Continue marking dependencies until no more.
+  while (!stack.is_empty()) {
+  // Only expressions can appear in the flow graph for now.
+    Expression* expr = stack.RemoveLast()->AsExpression();
+    if (expr != NULL) {
+      expr->ProcessNonLiveChildren(&stack, body_definitions, variable_count);
+    }
+  }
+}
+
+
 #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() : number_(0) {}
 
   int NextNumber() { return number_; }
@@ skipping 394 matching lines @@
   for (int i = postorder->length() - 1; i >= 0; i--) {
     postorder->at(i)->AssignNodeNumber();
   }
 
   // Print basic blocks in reverse postorder.
   for (int i = postorder->length() - 1; i >= 0; i--) {
     postorder->at(i)->PrintText();
   }
 }
 
-
-#endif  // defined(DEBUG)
-
-
-int ReachingDefinitions::IndexFor(Variable* var, int variable_count) {
-  // Parameters are numbered left-to-right from the beginning of the bit
-  // set.  Stack-allocated locals are allocated right-to-left from the end.
-  ASSERT(var != NULL && var->IsStackAllocated());
-  Slot* slot = var->slot();
-  if (slot->type() == Slot::PARAMETER) {
-    return slot->index();
-  } else {
-    return (variable_count - 1) - slot->index();
-  }
-}
-
-
-void Node::InitializeReachingDefinitions(int definition_count,
-                                         List<BitVector*>* variables,
-                                         WorkList<Node>* worklist,
-                                         bool mark) {
-  ASSERT(!IsMarkedWith(mark));
-  rd_.Initialize(definition_count);
-  MarkWith(mark);
-  worklist->Insert(this);
-}
-
-
-void BlockNode::InitializeReachingDefinitions(int definition_count,
-                                              List<BitVector*>* variables,
-                                              WorkList<Node>* worklist,
-                                              bool mark) {
-  ASSERT(!IsMarkedWith(mark));
-  int instruction_count = instructions_.length();
-  int variable_count = variables->length();
-
-  rd_.Initialize(definition_count);
-  // The RD_in set for the entry node has a definition for each parameter
-  // and local.
-  if (predecessor_ == NULL) {
-    for (int i = 0; i < variable_count; i++) rd_.rd_in()->Add(i);
-  }
-
-  for (int i = 0; i < instruction_count; i++) {
-    Expression* expr = instructions_[i]->AsExpression();
-    if (expr == NULL) continue;
-    Variable* var = expr->AssignedVariable();
-    if (var == NULL || !var->IsStackAllocated()) continue;
-
-    // All definitions of this variable are killed.
-    BitVector* def_set =
-        variables->at(ReachingDefinitions::IndexFor(var, variable_count));
-    rd_.kill()->Union(*def_set);
-
-    // All previously generated definitions are not generated.
-    rd_.gen()->Subtract(*def_set);
-
-    // This one is generated.
-    rd_.gen()->Add(expr->num());
-  }
-
-  // Add all blocks except the entry node to the worklist.
-  if (predecessor_ != NULL) {
-    MarkWith(mark);
-    worklist->Insert(this);
-  }
-}
-
-
-void ExitNode::ComputeRDOut(BitVector* result) {
-  // Should not be the predecessor of any node.
-  UNREACHABLE();
-}
-
-
-void BlockNode::ComputeRDOut(BitVector* result) {
-  // All definitions reaching this block ...
-  *result = *rd_.rd_in();
-  // ... except those killed by the block ...
-  result->Subtract(*rd_.kill());
-  // ... but including those generated by the block.
-  result->Union(*rd_.gen());
-}
-
-
-void BranchNode::ComputeRDOut(BitVector* result) {
-  // Branch nodes don't kill or generate definitions.
-  *result = *rd_.rd_in();
-}
-
-
-void JoinNode::ComputeRDOut(BitVector* result) {
-  // Join nodes don't kill or generate definitions.
-  *result = *rd_.rd_in();
-}
-
-
-void ExitNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
-  // The exit node has no successors so we can just update in place.  New
-  // RD_in is the union over all predecessors.
-  int definition_count = rd_.rd_in()->length();
-  rd_.rd_in()->Clear();
-
-  BitVector temp(definition_count);
-  for (int i = 0, len = predecessors_.length(); i < len; i++) {
-    // Because ComputeRDOut always overwrites temp and its value is
-    // always read out before calling ComputeRDOut again, we do not
-    // have to clear it on each iteration of the loop.
-    predecessors_[i]->ComputeRDOut(&temp);
-    rd_.rd_in()->Union(temp);
-  }
-}
-
-
-void BlockNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
-  // The entry block has no predecessor.  Its RD_in does not change.
-  if (predecessor_ == NULL) return;
-
-  BitVector new_rd_in(rd_.rd_in()->length());
-  predecessor_->ComputeRDOut(&new_rd_in);
-
-  if (rd_.rd_in()->Equals(new_rd_in)) return;
-
-  // Update RD_in.
-  *rd_.rd_in() = new_rd_in;
-  // Add the successor to the worklist if not already present.
-  if (!successor_->IsMarkedWith(mark)) {
-    successor_->MarkWith(mark);
-    worklist->Insert(successor_);
-  }
-}
-
-
-void BranchNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
-  BitVector new_rd_in(rd_.rd_in()->length());
-  predecessor_->ComputeRDOut(&new_rd_in);
-
-  if (rd_.rd_in()->Equals(new_rd_in)) return;
-
-  // Update RD_in.
-  *rd_.rd_in() = new_rd_in;
-  // Add the successors to the worklist if not already present.
-  if (!successor0_->IsMarkedWith(mark)) {
-    successor0_->MarkWith(mark);
-    worklist->Insert(successor0_);
-  }
-  if (!successor1_->IsMarkedWith(mark)) {
-    successor1_->MarkWith(mark);
-    worklist->Insert(successor1_);
-  }
-}
-
-
-void JoinNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
-  int definition_count = rd_.rd_in()->length();
-  BitVector new_rd_in(definition_count);
-
-  // New RD_in is the union over all predecessors.
-  BitVector temp(definition_count);
-  for (int i = 0, len = predecessors_.length(); i < len; i++) {
-    predecessors_[i]->ComputeRDOut(&temp);
-    new_rd_in.Union(temp);
-  }
-
-  if (rd_.rd_in()->Equals(new_rd_in)) return;
-
-  // Update RD_in.
-  *rd_.rd_in() = new_rd_in;
-  // Add the successor to the worklist if not already present.
-  if (!successor_->IsMarkedWith(mark)) {
-    successor_->MarkWith(mark);
-    worklist->Insert(successor_);
-  }
-}
-
-
-void Node::PropagateReachingDefinitions(List<BitVector*>* variables) {
-  // Nothing to do.
-}
-
-
-void BlockNode::PropagateReachingDefinitions(List<BitVector*>* variables) {
-  // Propagate RD_in from the start of the block to all the variable
-  // references.
-  int variable_count = variables->length();
-  BitVector rd = *rd_.rd_in();
-  for (int i = 0, len = instructions_.length(); i < len; i++) {
-    Expression* expr = instructions_[i]->AsExpression();
-    if (expr == NULL) continue;
-
-    // Look for a variable reference to record its reaching definitions.
-    VariableProxy* proxy = expr->AsVariableProxy();
-    if (proxy == NULL) {
-      // Not a VariableProxy?  Maybe it's a count operation.
-      CountOperation* count_operation = expr->AsCountOperation();
-      if (count_operation != NULL) {
-        proxy = count_operation->expression()->AsVariableProxy();
-      }
-    }
-    if (proxy == NULL) {
-      // OK, Maybe it's a compound assignment.
-      Assignment* assignment = expr->AsAssignment();
-      if (assignment != NULL && assignment->is_compound()) {
-        proxy = assignment->target()->AsVariableProxy();
-      }
-    }
-
-    if (proxy != NULL &&
-        proxy->var()->IsStackAllocated() &&
-        !proxy->var()->is_this()) {
-      // All definitions for this variable.
-      BitVector* definitions =
-          variables->at(ReachingDefinitions::IndexFor(proxy->var(),
-                                                      variable_count));
-      BitVector* reaching_definitions = new BitVector(*definitions);
-      // Intersected with all definitions (of any variable) reaching this
-      // instruction.
-      reaching_definitions->Intersect(rd);
-      proxy->set_reaching_definitions(reaching_definitions);
-    }
-
-    // It may instead (or also) be a definition.  If so update the running
-    // value of reaching definitions for the block.
-    Variable* var = expr->AssignedVariable();
-    if (var == NULL || !var->IsStackAllocated()) continue;
-
-    // All definitions of this variable are killed.
-    BitVector* def_set =
-        variables->at(ReachingDefinitions::IndexFor(var, variable_count));
-    rd.Subtract(*def_set);
-    // This definition is generated.
-    rd.Add(expr->num());
-  }
-}
-
-
-void ReachingDefinitions::Compute() {
-  // The definitions in the body plus an implicit definition for each
-  // variable at function entry.
-  int definition_count = body_definitions_->length() + variable_count_;
-  int node_count = postorder_->length();
-
-  // Step 1: For each stack-allocated variable, identify the set of all its
-  // definitions.
-  List<BitVector*> variables;
-  for (int i = 0; i < variable_count_; i++) {
-    // Add the initial definition for each variable.
-    BitVector* initial = new BitVector(definition_count);
-    initial->Add(i);
-    variables.Add(initial);
-  }
-  for (int i = 0, len = body_definitions_->length(); i < len; i++) {
-    // Account for each definition in the body as a definition of the
-    // defined variable.
-    Variable* var = body_definitions_->at(i)->AssignedVariable();
-    variables[IndexFor(var, variable_count_)]->Add(i + variable_count_);
-  }
-
-  // Step 2: Compute KILL and GEN for each block node, initialize RD_in for
-  // all nodes, and mark and add all nodes to the worklist in reverse
-  // postorder.  All nodes should currently have the same mark.
-  bool mark = postorder_->at(0)->IsMarkedWith(false);  // Negation of current.
-  WorkList<Node> worklist(node_count);
-  for (int i = node_count - 1; i >= 0; i--) {
-    postorder_->at(i)->InitializeReachingDefinitions(definition_count,
-                                                     &variables,
-                                                     &worklist,
-                                                     mark);
-  }
-
-  // Step 3: Until the worklist is empty, remove an item compute and update
-  // its rd_in based on its predecessor's rd_out.  If rd_in has changed, add
-  // all necessary successors to the worklist.
-  while (!worklist.is_empty()) {
-    Node* node = worklist.Remove();
-    node->MarkWith(!mark);
-    node->UpdateRDIn(&worklist, mark);
-  }
-
-  // Step 4: Based on RD_in for block nodes, propagate reaching definitions
-  // to all variable uses in the block.
-  for (int i = 0; i < node_count; i++) {
-    postorder_->at(i)->PropagateReachingDefinitions(&variables);
-  }
-}
-
-
-bool TypeAnalyzer::IsPrimitiveDef(int def_num) {
-  if (def_num < param_count_) return false;
-  if (def_num < variable_count_) return true;
-  return body_definitions_->at(def_num - variable_count_)->IsPrimitive();
-}
-
-
-void TypeAnalyzer::Compute() {
-  bool changed;
-  int count = 0;
-
-  do {
-    changed = false;
-
-    if (FLAG_print_graph_text) {
-      PrintF("TypeAnalyzer::Compute - iteration %d\n", count++);
-    }
-
-    for (int i = postorder_->length() - 1; i >= 0; --i) {
-      Node* node = postorder_->at(i);
-      if (node->IsBlockNode()) {
-        BlockNode* block = BlockNode::cast(node);
-        for (int j = 0; j < block->instructions()->length(); j++) {
-          Expression* expr = block->instructions()->at(j)->AsExpression();
-          if (expr != NULL) {
-            // For variable uses: Compute new type from reaching definitions.
-            VariableProxy* proxy = expr->AsVariableProxy();
-            if (proxy != NULL && proxy->reaching_definitions() != NULL) {
-              BitVector* rd = proxy->reaching_definitions();
-              bool prim_type = true;
-              // TODO(fsc): A sparse set representation of reaching
-              // definitions would speed up iterating here.
-              for (int k = 0; k < rd->length(); k++) {
-                if (rd->Contains(k) && !IsPrimitiveDef(k)) {
-                  prim_type = false;
-                  break;
-                }
-              }
-              // Reset changed flag if new type information was computed.
-              if (prim_type != proxy->IsPrimitive()) {
-                changed = true;
-                proxy->SetIsPrimitive(prim_type);
-              }
-            }
-          }
-        }
-      }
-    }
-  } while (changed);
-}
-
-
-void Node::MarkCriticalInstructions(
-    List<AstNode*>* stack,
-    ZoneList<Expression*>* body_definitions,
-    int variable_count) {
-}
-
-
-void BlockNode::MarkCriticalInstructions(
-    List<AstNode*>* stack,
-    ZoneList<Expression*>* body_definitions,
-    int variable_count) {
-  for (int i = instructions_.length() - 1; i >= 0; i--) {
-    // Only expressions can appear in the flow graph for now.
-    Expression* expr = instructions_[i]->AsExpression();
-    if (expr != NULL && !expr->is_live() &&
-        (expr->is_loop_condition() || expr->IsCritical())) {
-      expr->mark_as_live();
-      expr->ProcessNonLiveChildren(stack, body_definitions, variable_count);
-    }
-  }
-}
-
-
-void MarkLiveCode(ZoneList<Node*>* nodes,
-                  ZoneList<Expression*>* body_definitions,
-                  int variable_count) {
-  List<AstNode*> stack(20);
-
-  // Mark the critical AST nodes as live; mark their dependencies and
-  // add them to the marking stack.
-  for (int i = nodes->length() - 1; i >= 0; i--) {
-    nodes->at(i)->MarkCriticalInstructions(&stack, body_definitions,
-                                           variable_count);
-  }
-
-  // Continue marking dependencies until no more.
-  while (!stack.is_empty()) {
-  // Only expressions can appear in the flow graph for now.
-    Expression* expr = stack.RemoveLast()->AsExpression();
-    if (expr != NULL) {
-      expr->ProcessNonLiveChildren(&stack, body_definitions, variable_count);
-    }
-  }
-}
+#endif  // DEBUG
 
 
 } }  // namespace v8::internal