Loop peeling for inner loops....

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 161 matching lines @@
 
   // 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();
-  Visit(stmt->then_statement());
+  stmt->set_then_statement(ProcessStatement(stmt->then_statement()));
 
   FlowGraph left = graph_;
   graph_ = FlowGraph::Empty();
-  Visit(stmt->else_statement());
+  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();
@@ skipping 29 matching lines @@
   SetStackOverflow();
 }
 
 
 void FlowGraphBuilder::VisitWhileStatement(WhileStatement* stmt) {
   SetStackOverflow();
 }
 
 
 void FlowGraphBuilder::VisitForStatement(ForStatement* stmt) {
-  if (stmt->init() != NULL) Visit(stmt->init());
+  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();
-  Visit(stmt->body());
+  stmt->set_body(ProcessStatement(stmt->body()));
 
-  if (stmt->next() != NULL) Visit(stmt->next());
+  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();
 }
@@ skipping 1581 matching lines @@
   PrintReachingDefinitions();
   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) {
+void FlowGraph::PrintText(FunctionLiteral* fun, ZoneList<Node*>* postorder) {
   PrintF("\n========\n");
+  PrintF("name = %s\n", *fun->name()->ToCString());
 
   // 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)->AssignNodeNumber();
   }
 
   // Print basic blocks in reverse postorder.
   for (int i = postorder->length() - 1; i >= 0; i--) {
@@ skipping 226 matching lines @@
   // all necessary successors to the worklist.
   while (!worklist.is_empty()) {
     Node* node = worklist.Remove();
     node->MarkWith(!mark);
     node->UpdateRDIn(&worklist, mark);
   }
 }
 
 
 } }  // namespace v8::internal