Add defensive checks to the flow graph builder.

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 16 matching lines @@
 
 #include "v8.h"
 
 #include "data-flow.h"
 
 namespace v8 {
 namespace internal {
 
 
 void FlowGraph::AppendInstruction(AstNode* instruction) {
+  // Add a (non-null) AstNode to the end of the graph fragment.
   ASSERT(instruction != NULL);
-  if (is_empty() || !exit()->IsBlockNode()) {
-    AppendNode(new BlockNode());
-  }
+  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 (is_empty()) {
-    entry_ = exit_ = node;
-  } else {
-    exit()->AddSuccessor(node);
-    node->AddPredecessor(exit());
-    exit_ = node;
+  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) {
-  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();
+  // 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).

[fschneider, 2010/03/10 16:51:09]

Maybe ASSERT(graph != NULL) for consistency with the other AppendX functions,

+  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* 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.
+                      JoinNode* join) {
+  // Add the branch node, left flowgraph, join node.
   AppendNode(branch);
   AppendGraph(left);
-  AppendNode(merge);
+  AppendNode(join);
 
   // Splice in the right flowgraph.
-  right->AppendNode(merge);
+  right->AppendNode(join);
   branch->AddSuccessor(right->entry());
   right->entry()->AddPredecessor(branch);
 }
 
 
-void FlowGraph::Loop(JoinNode* merge,
+void FlowGraph::Loop(JoinNode* join,
                      FlowGraph* condition,
                      BranchNode* branch,
                      FlowGraph* body) {
-  // Add the merge, condition and branch.  Add merge's predecessors in
+  // Add the join, condition and branch.  Add join's predecessors in
   // left-to-right order.
-  AppendNode(merge);
-  body->AppendNode(merge);
+  AppendNode(join);
+  body->AppendNode(join);
   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,
@@ skipping 32 matching lines @@
   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;
-  }
+  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_);
 }
 
@@ skipping 23 matching lines @@
 
   BranchNode* branch = new BranchNode();
   FlowGraph original = graph_;
   graph_ = FlowGraph::Empty();
   Visit(stmt->then_statement());
 
   FlowGraph left = graph_;
   graph_ = FlowGraph::Empty();
   Visit(stmt->else_statement());
 
+  if (HasStackOverflow()) return;
   JoinNode* join = new JoinNode();
   original.Split(branch, &left, &graph_, join);
   graph_ = original;
 }
 
 
 void FlowGraphBuilder::VisitContinueStatement(ContinueStatement* stmt) {
   SetStackOverflow();
 }
 
@@ skipping 41 matching lines @@
   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());
 
+  if (HasStackOverflow()) return;
   original.Loop(join, &condition, branch, &graph_);
   graph_ = original;
 }
 
 
 void FlowGraphBuilder::VisitForInStatement(ForInStatement* stmt) {
   SetStackOverflow();
 }
 
 
@@ skipping 71 matching lines @@
   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());
   }
+
+  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()) {
     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) {
@@ skipping 832 matching lines @@
 
 
 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++) {
@@ skipping 35 matching lines @@
   for (int i = postorder->length() - 1; i >= 0; i--) {
     postorder->at(i)->PrintText();
   }
 }
 
 
 #endif  // defined(DEBUG)
 
 
 } }  // namespace v8::internal