From 43fd945eee0f6ce38450c92d9a0aaab25127bceb Mon Sep 17 00:00:00 2001 From: "fschneider@chromium.org" Date: Mon, 22 Mar 2010 13:21:32 +0000 Subject: [PATCH] Loop peeling for inner loops. This change adds the option to peel off the first iteration of inner loops. Loop peeling is off by default and can enabled by a flag. It also requires building a flow graph. As part of this I added the possibility to clone AST nodes. Review URL: http://codereview.chromium.org/998001 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4205 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/ast.cc | 384 +++++++++++++++++++++++++++++++++++++++++ src/ast.h | 98 ++++++++++- src/compiler.cc | 4 +- src/data-flow.cc | 88 +++++++++- src/data-flow.h | 9 +- src/flag-definitions.h | 3 + src/parser.cc | 32 +++- src/variables.h | 2 - 8 files changed, 604 insertions(+), 16 deletions(-) diff --git a/src/ast.cc b/src/ast.cc index 9fc4af0db..f87f86591 100644 --- a/src/ast.cc +++ b/src/ast.cc @@ -592,4 +592,388 @@ bool BinaryOperation::IsPrimitive() { bool CompareOperation::IsPrimitive() { return true; } +// Implementation of a copy visitor. The visitor create a deep copy +// of ast nodes. Nodes that do not require a deep copy are copied +// with the default copy constructor. + +AstNode::AstNode(AstNode* other) : num_(kNoNumber) { + // AST node number should be unique. Assert that we only copy AstNodes + // before node numbers are assigned. + ASSERT(other->num_ == kNoNumber); +} + + +Statement::Statement(Statement* other) + : AstNode(other), statement_pos_(other->statement_pos_) {} + + +Expression::Expression(Expression* other) + : AstNode(other), + bitfields_(other->bitfields_), + type_(other->type_) {} + + +BreakableStatement::BreakableStatement(BreakableStatement* other) + : Statement(other), labels_(other->labels_), type_(other->type_) {} + + +Block::Block(Block* other, ZoneList* statements) + : BreakableStatement(other), + statements_(statements->length()), + is_initializer_block_(other->is_initializer_block_) { + statements_.AddAll(*statements); +} + + +ExpressionStatement::ExpressionStatement(ExpressionStatement* other, + Expression* expression) + : Statement(other), expression_(expression) {} + + +IfStatement::IfStatement(IfStatement* other, + Expression* condition, + Statement* then_statement, + Statement* else_statement) + : Statement(other), + condition_(condition), + then_statement_(then_statement), + else_statement_(else_statement) {} + + +EmptyStatement::EmptyStatement(EmptyStatement* other) : Statement(other) {} + + +IterationStatement::IterationStatement(IterationStatement* other, + Statement* body) + : BreakableStatement(other), body_(body) {} + + +ForStatement::ForStatement(ForStatement* other, + Statement* init, + Expression* cond, + Statement* next, + Statement* body) + : IterationStatement(other, body), + init_(init), + cond_(cond), + next_(next), + may_have_function_literal_(other->may_have_function_literal_), + loop_variable_(other->loop_variable_), + peel_this_loop_(other->peel_this_loop_) {} + + +Assignment::Assignment(Assignment* other, + Expression* target, + Expression* value) + : Expression(other), + op_(other->op_), + target_(target), + value_(value), + pos_(other->pos_), + block_start_(other->block_start_), + block_end_(other->block_end_) {} + + +Property::Property(Property* other, Expression* obj, Expression* key) + : Expression(other), + obj_(obj), + key_(key), + pos_(other->pos_), + type_(other->type_) {} + + +Call::Call(Call* other, + Expression* expression, + ZoneList* arguments) + : Expression(other), + expression_(expression), + arguments_(arguments), + pos_(other->pos_) {} + + +UnaryOperation::UnaryOperation(UnaryOperation* other, Expression* expression) + : Expression(other), op_(other->op_), expression_(expression) {} + + +BinaryOperation::BinaryOperation(BinaryOperation* other, + Expression* left, + Expression* right) + : Expression(other), + op_(other->op_), + left_(left), + right_(right) {} + + +CountOperation::CountOperation(CountOperation* other, Expression* expression) + : Expression(other), + is_prefix_(other->is_prefix_), + op_(other->op_), + expression_(expression) {} + + +CompareOperation::CompareOperation(CompareOperation* other, + Expression* left, + Expression* right) + : Expression(other), + op_(other->op_), + left_(left), + right_(right), + is_for_loop_condition_(other->is_for_loop_condition_) {} + + +Expression* CopyAstVisitor::DeepCopyExpr(Expression* expr) { + expr_ = NULL; + if (expr != NULL) Visit(expr); + return expr_; +} + + +Statement* CopyAstVisitor::DeepCopyStmt(Statement* stmt) { + stmt_ = NULL; + if (stmt != NULL) Visit(stmt); + return stmt_; +} + + +ZoneList* CopyAstVisitor::DeepCopyExprList( + ZoneList* expressions) { + ZoneList* copy = + new ZoneList(expressions->length()); + for (int i = 0; i < expressions->length(); i++) { + copy->Add(DeepCopyExpr(expressions->at(i))); + } + return copy; +} + + +ZoneList* CopyAstVisitor::DeepCopyStmtList( + ZoneList* statements) { + ZoneList* copy = new ZoneList(statements->length()); + for (int i = 0; i < statements->length(); i++) { + copy->Add(DeepCopyStmt(statements->at(i))); + } + return copy; +} + + +void CopyAstVisitor::VisitBlock(Block* stmt) { + stmt_ = new Block(stmt, + DeepCopyStmtList(stmt->statements())); +} + + +void CopyAstVisitor::VisitExpressionStatement( + ExpressionStatement* stmt) { + stmt_ = new ExpressionStatement(stmt, DeepCopyExpr(stmt->expression())); +} + + +void CopyAstVisitor::VisitEmptyStatement(EmptyStatement* stmt) { + stmt_ = new EmptyStatement(stmt); +} + + +void CopyAstVisitor::VisitIfStatement(IfStatement* stmt) { + stmt_ = new IfStatement(stmt, + DeepCopyExpr(stmt->condition()), + DeepCopyStmt(stmt->then_statement()), + DeepCopyStmt(stmt->else_statement())); +} + + +void CopyAstVisitor::VisitContinueStatement(ContinueStatement* stmt) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitBreakStatement(BreakStatement* stmt) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitReturnStatement(ReturnStatement* stmt) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitWithEnterStatement( + WithEnterStatement* stmt) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitWithExitStatement(WithExitStatement* stmt) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitSwitchStatement(SwitchStatement* stmt) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitDoWhileStatement(DoWhileStatement* stmt) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitWhileStatement(WhileStatement* stmt) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitForStatement(ForStatement* stmt) { + stmt_ = new ForStatement(stmt, + DeepCopyStmt(stmt->init()), + DeepCopyExpr(stmt->cond()), + DeepCopyStmt(stmt->next()), + DeepCopyStmt(stmt->body())); +} + + +void CopyAstVisitor::VisitForInStatement(ForInStatement* stmt) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitTryCatchStatement(TryCatchStatement* stmt) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitTryFinallyStatement( + TryFinallyStatement* stmt) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitDebuggerStatement( + DebuggerStatement* stmt) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitFunctionLiteral(FunctionLiteral* expr) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitFunctionBoilerplateLiteral( + FunctionBoilerplateLiteral* expr) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitConditional(Conditional* expr) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitSlot(Slot* expr) { + UNREACHABLE(); +} + + +void CopyAstVisitor::VisitVariableProxy(VariableProxy* expr) { + expr_ = new VariableProxy(*expr); +} + + +void CopyAstVisitor::VisitLiteral(Literal* expr) { + expr_ = new Literal(*expr); +} + + +void CopyAstVisitor::VisitRegExpLiteral(RegExpLiteral* expr) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitObjectLiteral(ObjectLiteral* expr) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitArrayLiteral(ArrayLiteral* expr) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitCatchExtensionObject( + CatchExtensionObject* expr) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitAssignment(Assignment* expr) { + expr_ = new Assignment(expr, + DeepCopyExpr(expr->target()), + DeepCopyExpr(expr->value())); +} + + +void CopyAstVisitor::VisitThrow(Throw* expr) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitProperty(Property* expr) { + expr_ = new Property(expr, + DeepCopyExpr(expr->obj()), + DeepCopyExpr(expr->key())); +} + + +void CopyAstVisitor::VisitCall(Call* expr) { + expr_ = new Call(expr, + DeepCopyExpr(expr->expression()), + DeepCopyExprList(expr->arguments())); +} + + +void CopyAstVisitor::VisitCallNew(CallNew* expr) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitCallRuntime(CallRuntime* expr) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitUnaryOperation(UnaryOperation* expr) { + expr_ = new UnaryOperation(expr, DeepCopyExpr(expr->expression())); +} + + +void CopyAstVisitor::VisitCountOperation(CountOperation* expr) { + expr_ = new CountOperation(expr, + DeepCopyExpr(expr->expression())); +} + + +void CopyAstVisitor::VisitBinaryOperation(BinaryOperation* expr) { + expr_ = new BinaryOperation(expr, + DeepCopyExpr(expr->left()), + DeepCopyExpr(expr->right())); +} + + +void CopyAstVisitor::VisitCompareOperation(CompareOperation* expr) { + expr_ = new CompareOperation(expr, + DeepCopyExpr(expr->left()), + DeepCopyExpr(expr->right())); +} + + +void CopyAstVisitor::VisitThisFunction(ThisFunction* expr) { + SetStackOverflow(); +} + + +void CopyAstVisitor::VisitDeclaration(Declaration* decl) { + UNREACHABLE(); +} + + } } // namespace v8::internal diff --git a/src/ast.h b/src/ast.h index 8248f62a8..e9d0d61e7 100644 --- a/src/ast.h +++ b/src/ast.h @@ -121,11 +121,15 @@ class AstNode: public ZoneObject { static const int kNoNumber = -1; AstNode() : num_(kNoNumber) {} + + explicit AstNode(AstNode* other); + virtual ~AstNode() { } virtual void Accept(AstVisitor* v) = 0; // Type testing & conversion. virtual Statement* AsStatement() { return NULL; } + virtual Block* AsBlock() { return NULL; } virtual ExpressionStatement* AsExpressionStatement() { return NULL; } virtual EmptyStatement* AsEmptyStatement() { return NULL; } virtual Expression* AsExpression() { return NULL; } @@ -137,6 +141,7 @@ class AstNode: public ZoneObject { virtual TargetCollector* AsTargetCollector() { return NULL; } virtual BreakableStatement* AsBreakableStatement() { return NULL; } virtual IterationStatement* AsIterationStatement() { return NULL; } + virtual ForStatement* AsForStatement() { return NULL; } virtual UnaryOperation* AsUnaryOperation() { return NULL; } virtual CountOperation* AsCountOperation() { return NULL; } virtual BinaryOperation* AsBinaryOperation() { return NULL; } @@ -160,6 +165,8 @@ class Statement: public AstNode { public: Statement() : statement_pos_(RelocInfo::kNoPosition) {} + explicit Statement(Statement* other); + virtual Statement* AsStatement() { return this; } virtual ReturnStatement* AsReturnStatement() { return NULL; } @@ -198,6 +205,8 @@ class Expression: public AstNode { Expression() : bitfields_(0) {} + explicit Expression(Expression* other); + virtual Expression* AsExpression() { return this; } virtual bool IsValidLeftHandSide() { return false; } @@ -265,7 +274,6 @@ class Expression: public AstNode { bitfields_ |= NumBitOpsField::encode(num_bit_ops); } - private: static const int kMaxNumBitOps = (1 << 5) - 1; @@ -327,6 +335,8 @@ class BreakableStatement: public Statement { ASSERT(labels == NULL || labels->length() > 0); } + explicit BreakableStatement(BreakableStatement* other); + private: ZoneStringList* labels_; Type type_; @@ -341,8 +351,14 @@ class Block: public BreakableStatement { statements_(capacity), is_initializer_block_(is_initializer_block) { } + // Construct a clone initialized from the original block and + // a deep copy of all statements of the original block. + Block(Block* other, ZoneList* statements); + virtual void Accept(AstVisitor* v); + virtual Block* AsBlock() { return this; } + virtual Assignment* StatementAsSimpleAssignment() { if (statements_.length() != 1) return NULL; return statements_[0]->StatementAsSimpleAssignment(); @@ -394,6 +410,7 @@ class IterationStatement: public BreakableStatement { virtual IterationStatement* AsIterationStatement() { return this; } Statement* body() const { return body_; } + void set_body(Statement* stmt) { body_ = stmt; } // Code generation BreakTarget* continue_target() { return &continue_target_; } @@ -402,6 +419,10 @@ class IterationStatement: public BreakableStatement { explicit IterationStatement(ZoneStringList* labels) : BreakableStatement(labels, TARGET_FOR_ANONYMOUS), body_(NULL) { } + // Construct a clone initialized from original and + // a deep copy of the original body. + IterationStatement(IterationStatement* other, Statement* body); + void Initialize(Statement* body) { body_ = body; } @@ -475,7 +496,18 @@ class ForStatement: public IterationStatement { cond_(NULL), next_(NULL), may_have_function_literal_(true), - loop_variable_(NULL) {} + loop_variable_(NULL), + peel_this_loop_(false) {} + + // Construct a for-statement initialized from another for-statement + // and deep copies of all parts of the original statement. + ForStatement(ForStatement* other, + Statement* init, + Expression* cond, + Statement* next, + Statement* body); + + virtual ForStatement* AsForStatement() { return this; } void Initialize(Statement* init, Expression* cond, @@ -490,8 +522,11 @@ class ForStatement: public IterationStatement { virtual void Accept(AstVisitor* v); Statement* init() const { return init_; } + void set_init(Statement* stmt) { init_ = stmt; } Expression* cond() const { return cond_; } + void set_cond(Expression* expr) { cond_ = expr; } Statement* next() const { return next_; } + void set_next(Statement* stmt) { next_ = stmt; } bool may_have_function_literal() const { return may_have_function_literal_; } @@ -500,6 +535,9 @@ class ForStatement: public IterationStatement { Variable* loop_variable() { return loop_variable_; } void set_loop_variable(Variable* var) { loop_variable_ = var; } + bool peel_this_loop() { return peel_this_loop_; } + void set_peel_this_loop(bool b) { peel_this_loop_ = b; } + private: Statement* init_; Expression* cond_; @@ -507,6 +545,7 @@ class ForStatement: public IterationStatement { // True if there is a function literal subexpression in the condition. bool may_have_function_literal_; Variable* loop_variable_; + bool peel_this_loop_; friend class AstOptimizer; }; @@ -539,6 +578,10 @@ class ExpressionStatement: public Statement { explicit ExpressionStatement(Expression* expression) : expression_(expression) { } + // Construct an expression statement initialized from another + // expression statement and a deep copy of the original expression. + ExpressionStatement(ExpressionStatement* other, Expression* expression); + virtual void Accept(AstVisitor* v); // Type testing & conversion. @@ -681,6 +724,13 @@ class IfStatement: public Statement { then_statement_(then_statement), else_statement_(else_statement) { } + // Construct an if-statement initialized from another if-statement + // and deep copies of all parts of the original. + IfStatement(IfStatement* other, + Expression* condition, + Statement* then_statement, + Statement* else_statement); + virtual void Accept(AstVisitor* v); bool HasThenStatement() const { return !then_statement()->IsEmpty(); } @@ -688,7 +738,9 @@ class IfStatement: public Statement { Expression* condition() const { return condition_; } Statement* then_statement() const { return then_statement_; } + void set_then_statement(Statement* stmt) { then_statement_ = stmt; } Statement* else_statement() const { return else_statement_; } + void set_else_statement(Statement* stmt) { else_statement_ = stmt; } private: Expression* condition_; @@ -783,6 +835,10 @@ class DebuggerStatement: public Statement { class EmptyStatement: public Statement { public: + EmptyStatement() {} + + explicit EmptyStatement(EmptyStatement* other); + virtual void Accept(AstVisitor* v); // Type testing & conversion. @@ -1145,6 +1201,8 @@ class Property: public Expression { Property(Expression* obj, Expression* key, int pos, Type type = NORMAL) : obj_(obj), key_(key), pos_(pos), type_(type) { } + Property(Property* other, Expression* obj, Expression* key); + virtual void Accept(AstVisitor* v); // Type testing & conversion @@ -1179,6 +1237,8 @@ class Call: public Expression { Call(Expression* expression, ZoneList* arguments, int pos) : expression_(expression), arguments_(arguments), pos_(pos) { } + Call(Call* other, Expression* expression, ZoneList* arguments); + virtual void Accept(AstVisitor* v); // Type testing and conversion. @@ -1255,6 +1315,8 @@ class UnaryOperation: public Expression { ASSERT(Token::IsUnaryOp(op)); } + UnaryOperation(UnaryOperation* other, Expression* expression); + virtual void Accept(AstVisitor* v); // Type testing & conversion @@ -1278,6 +1340,8 @@ class BinaryOperation: public Expression { ASSERT(Token::IsBinaryOp(op)); } + BinaryOperation(BinaryOperation* other, Expression* left, Expression* right); + virtual void Accept(AstVisitor* v); // Type testing & conversion @@ -1329,6 +1393,8 @@ class CountOperation: public Expression { ASSERT(Token::IsCountOp(op)); } + CountOperation(CountOperation* other, Expression* expression); + virtual void Accept(AstVisitor* v); virtual CountOperation* AsCountOperation() { return this; } @@ -1363,6 +1429,10 @@ class CompareOperation: public Expression { ASSERT(Token::IsCompareOp(op)); } + CompareOperation(CompareOperation* other, + Expression* left, + Expression* right); + virtual void Accept(AstVisitor* v); virtual bool IsPrimitive(); @@ -1418,6 +1488,8 @@ class Assignment: public Expression { ASSERT(Token::IsAssignmentOp(op)); } + Assignment(Assignment* other, Expression* target, Expression* value); + virtual void Accept(AstVisitor* v); virtual Assignment* AsAssignment() { return this; } @@ -1993,6 +2065,28 @@ class AstVisitor BASE_EMBEDDED { }; +class CopyAstVisitor : public AstVisitor { + public: + Expression* DeepCopyExpr(Expression* expr); + + Statement* DeepCopyStmt(Statement* stmt); + + private: + ZoneList* DeepCopyExprList(ZoneList* expressions); + + ZoneList* DeepCopyStmtList(ZoneList* statements); + + // AST node visit functions. +#define DECLARE_VISIT(type) virtual void Visit##type(type* node); + AST_NODE_LIST(DECLARE_VISIT) +#undef DECLARE_VISIT + + // Holds the result of copying an expression. + Expression* expr_; + // Holds the result of copying a statement. + Statement* stmt_; +}; + } } // namespace v8::internal #endif // V8_AST_H_ diff --git a/src/compiler.cc b/src/compiler.cc index 11098bae9..3cdf1de49 100755 --- a/src/compiler.cc +++ b/src/compiler.cc @@ -105,7 +105,7 @@ static Handle MakeCode(Handle context, CompilationInfo* info) { #ifdef DEBUG if (FLAG_print_graph_text && !builder.HasStackOverflow()) { - builder.graph()->PrintText(builder.postorder()); + builder.graph()->PrintText(function, builder.postorder()); } #endif } @@ -513,7 +513,7 @@ Handle Compiler::BuildBoilerplate(FunctionLiteral* literal, #ifdef DEBUG if (FLAG_print_graph_text && !builder.HasStackOverflow()) { - builder.graph()->PrintText(builder.postorder()); + builder.graph()->PrintText(literal, builder.postorder()); } #endif } diff --git a/src/data-flow.cc b/src/data-flow.cc index 141718dc8..bf131f48e 100644 --- a/src/data-flow.cc +++ b/src/data-flow.cc @@ -195,6 +195,81 @@ void FlowGraphBuilder::Build(FunctionLiteral* lit) { } +// 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* 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(); } @@ -221,11 +296,11 @@ void FlowGraphBuilder::VisitIfStatement(IfStatement* stmt) { 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(); @@ -275,7 +350,7 @@ void FlowGraphBuilder::VisitWhileStatement(WhileStatement* stmt) { 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_; @@ -285,9 +360,9 @@ void FlowGraphBuilder::VisitForStatement(ForStatement* stmt) { 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_); @@ -1611,8 +1686,9 @@ void JoinNode::PrintText() { } -void FlowGraph::PrintText(ZoneList* postorder) { +void FlowGraph::PrintText(FunctionLiteral* fun, ZoneList* postorder) { PrintF("\n========\n"); + PrintF("name = %s\n", *fun->name()->ToCString()); // Number nodes and instructions in reverse postorder. node_count = 0; diff --git a/src/data-flow.h b/src/data-flow.h index 74a370c0d..b175ed048 100644 --- a/src/data-flow.h +++ b/src/data-flow.h @@ -470,7 +470,7 @@ class FlowGraph BASE_EMBEDDED { FlowGraph* body); #ifdef DEBUG - void PrintText(ZoneList* postorder); + void PrintText(FunctionLiteral* fun, ZoneList* postorder); #endif private: @@ -490,8 +490,7 @@ class FlowGraphBuilder: public AstVisitor { global_exit_(NULL), preorder_(4), postorder_(4), - definitions_(4) { - } + definitions_(4) {} void Build(FunctionLiteral* lit); @@ -502,6 +501,10 @@ class FlowGraphBuilder: public AstVisitor { private: ExitNode* global_exit() { return global_exit_; } + // Helpers to allow tranforming the ast during flow graph construction. + void VisitStatements(ZoneList* stmts); + Statement* ProcessStatement(Statement* stmt); + // AST node visit functions. #define DECLARE_VISIT(type) virtual void Visit##type(type* node); AST_NODE_LIST(DECLARE_VISIT) diff --git a/src/flag-definitions.h b/src/flag-definitions.h index 021362dea..6d0b9580c 100644 --- a/src/flag-definitions.h +++ b/src/flag-definitions.h @@ -160,6 +160,9 @@ DEFINE_bool(use_flow_graph, false, "perform flow-graph based optimizations") // compilation-cache.cc DEFINE_bool(compilation_cache, true, "enable compilation cache") +// data-flow.cc +DEFINE_bool(loop_peeling, false, "Peel off the first iteration of loops.") + // debug.cc DEFINE_bool(remote_debugging, false, "enable remote debugging") DEFINE_bool(trace_debug_json, false, "trace debugging JSON request/response") diff --git a/src/parser.cc b/src/parser.cc index cff56a395..c15a604be 100644 --- a/src/parser.cc +++ b/src/parser.cc @@ -148,6 +148,7 @@ class Parser { ParserLog* log_; bool is_pre_parsing_; ScriptDataImpl* pre_data_; + bool seen_loop_stmt_; // Used for inner loop detection. bool inside_with() const { return with_nesting_level_ > 0; } ParserFactory* factory() const { return factory_; } @@ -1205,7 +1206,8 @@ Parser::Parser(Handle