From 8528d650d8a21ba4a20c2fa6838d0ce9cae3e0a5 Mon Sep 17 00:00:00 2001 From: "kmillikin@chromium.org" Date: Mon, 8 Mar 2010 12:53:11 +0000 Subject: [PATCH] Initial implementation of an edge-labeled instruction flow graph. The flow graph is built by walking the AST. Edges are labeled with instructions (AST nodes). Normal nodes have a single predecessor edge and a single (labeled) successor edge. Branch nodes are explicit, they have a single predecessor edge and a pair of (unlabeled) successor edges. Merge nodes are explicit, they have a pair of predecessor edges and a single (unlabeled) successor edge. There is a distinguished (normal) entry node and a distinguished (special) exit node with arbitrarily many predecessor edges and no successor edges. The graph is intended to support graph-based analysis and transformation. Review URL: http://codereview.chromium.org/660449 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4051 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/ast.h | 19 +- src/compiler.cc | 23 ++ src/data-flow.cc | 899 +++++++++++++++++++++++++++++++++++++++++++++++++ src/data-flow.h | 293 ++++++++++++++++ src/flag-definitions.h | 3 + src/prettyprinter.cc | 8 +- 6 files changed, 1232 insertions(+), 13 deletions(-) diff --git a/src/ast.h b/src/ast.h index ba8b980..2f2a0bb 100644 --- a/src/ast.h +++ b/src/ast.h @@ -117,6 +117,9 @@ typedef ZoneList > ZoneObjectList; class AstNode: public ZoneObject { public: + static const int kNoNumber = -1; + + AstNode() : num_(kNoNumber) {} virtual ~AstNode() { } virtual void Accept(AstVisitor* v) = 0; @@ -141,6 +144,13 @@ class AstNode: public ZoneObject { virtual ObjectLiteral* AsObjectLiteral() { return NULL; } virtual ArrayLiteral* AsArrayLiteral() { return NULL; } virtual CompareOperation* AsCompareOperation() { return NULL; } + + int num() { return num_; } + void set_num(int n) { num_ = n; } + + private: + // Support for ast node numbering. + int num_; }; @@ -181,11 +191,8 @@ class Expression: public AstNode { kTestValue }; - static const int kNoLabel = -1; - Expression() : bitfields_(0), - num_(kNoLabel), def_(NULL), defined_vars_(NULL) {} @@ -215,11 +222,6 @@ class Expression: public AstNode { // Static type information for this expression. StaticType* type() { return &type_; } - int num() { return num_; } - - // AST node numbering ordered by evaluation order. - void set_num(int n) { num_ = n; } - // Data flow information. DefinitionInfo* var_def() { return def_; } void set_var_def(DefinitionInfo* def) { def_ = def; } @@ -261,7 +263,6 @@ class Expression: public AstNode { uint32_t bitfields_; StaticType type_; - int num_; DefinitionInfo* def_; ZoneList* defined_vars_; diff --git a/src/compiler.cc b/src/compiler.cc index 3fea3a3..50e16a0 100755 --- a/src/compiler.cc +++ b/src/compiler.cc @@ -31,6 +31,7 @@ #include "codegen-inl.h" #include "compilation-cache.h" #include "compiler.h" +#include "data-flow.h" #include "debug.h" #include "fast-codegen.h" #include "full-codegen.h" @@ -79,6 +80,17 @@ static Handle MakeCode(Handle context, CompilationInfo* info) { return Handle::null(); } + if (FLAG_use_flow_graph) { + FlowGraphBuilder builder; + builder.Build(function); + +#ifdef DEBUG + if (FLAG_print_graph_text) { + builder.graph()->PrintText(builder.postorder()); + } +#endif + } + // Generate code and return it. Code generator selection is governed by // which backends are enabled and whether the function is considered // run-once code or not: @@ -452,6 +464,17 @@ Handle Compiler::BuildBoilerplate(FunctionLiteral* literal, return Handle::null(); } + if (FLAG_use_flow_graph) { + FlowGraphBuilder builder; + builder.Build(literal); + +#ifdef DEBUG + if (FLAG_print_graph_text) { + builder.graph()->PrintText(builder.postorder()); + } +#endif + } + // Generate code and return it. The way that the compilation mode // is controlled by the command-line flags is described in // the static helper function MakeCode. diff --git a/src/data-flow.cc b/src/data-flow.cc index 5e9d217..722db9c 100644 --- a/src/data-flow.cc +++ b/src/data-flow.cc @@ -33,6 +33,534 @@ 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* preorder, + ZoneList* 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* preorder, + ZoneList* postorder) { + preorder->Add(this); + postorder->Add(this); +} + + +void BlockNode::Traverse(bool mark, + ZoneList* preorder, + ZoneList* 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* preorder, + ZoneList* 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* preorder, + ZoneList* 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* 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* 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 (prop != NULL) { + Visit(prop->obj()); + if (!prop->key()->IsPropertyName()) Visit(prop->key()); + } + if (var != NULL || prop != NULL) { + 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* 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* 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* 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()); + 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()); @@ -204,6 +732,9 @@ void AstLabeler::VisitAssignment(Assignment* expr) { 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_++); } @@ -220,6 +751,9 @@ void AstLabeler::VisitProperty(Property* expr) { 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_++); } @@ -558,4 +1092,369 @@ void LivenessAnalyzer::VisitThisFunction(ThisFunction* expr) { } +#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 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 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* 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* 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 name = expr->name()->ToCString(); + PrintF("%s(", *name); + ZoneList* 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* 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 diff --git a/src/data-flow.h b/src/data-flow.h index f6767e0..30c0336 100644 --- a/src/data-flow.h +++ b/src/data-flow.h @@ -95,6 +95,299 @@ class BitVector { }; +// Forward declarations of Node types. +class Node; +class BranchNode; +class JoinNode; + +// Flow graphs have a single entry and single exit. The empty flowgraph is +// represented by both entry and exit being NULL. +class FlowGraph BASE_EMBEDDED { + public: + FlowGraph() : entry_(NULL), exit_(NULL) {} + + static FlowGraph Empty() { return FlowGraph(); } + + bool is_empty() const { return entry_ == NULL; } + Node* entry() const { return entry_; } + Node* exit() const { return exit_; } + + // Add a single instruction to the end of this flowgraph. + void AppendInstruction(AstNode* instruction); + + // Add a single node to the end of this flow graph. + void AppendNode(Node* node); + + // Add a flow graph fragment to the end of this one. + void AppendGraph(FlowGraph* graph); + + // Concatenate an if-then-else flow-graph to this one. Control is split + // and merged, so the graph remains single-entry, single-exit. + void Split(BranchNode* branch, + FlowGraph* left, + FlowGraph* right, + JoinNode* merge); + + // Concatenate a forward loop (e.g., while or for loop) flow-graph to this + // one. Control is split by the condition and merged back from the back + // edge at end of the body to the beginning of the condition. The single + // (free) exit of the result graph is the right (false) arm of the branch + // node. + void Loop(JoinNode* merge, + FlowGraph* condition, + BranchNode* branch, + FlowGraph* body); + +#ifdef DEBUG + void PrintText(ZoneList* postorder); +#endif + + private: + Node* entry_; + Node* exit_; +}; + + +// Flow-graph nodes. +class Node: public ZoneObject { + public: + Node() : number_(-1), mark_(false) {} + + virtual ~Node() {} + + virtual bool IsBlockNode() { return false; } + virtual bool IsJoinNode() { return false; } + + virtual void AddPredecessor(Node* predecessor) = 0; + virtual void AddSuccessor(Node* successor) = 0; + + bool IsMarkedWith(bool mark) { return mark_ == mark; } + void MarkWith(bool mark) { mark_ = mark; } + + // Perform a depth first search and record preorder and postorder + // traversal orders. + virtual void Traverse(bool mark, + ZoneList* preorder, + ZoneList* postorder) = 0; + + int number() { return number_; } + void set_number(int number) { number_ = number; } + +#ifdef DEBUG + virtual void AssignNumbers(); + virtual void PrintText() = 0; +#endif + + private: + int number_; + bool mark_; + + DISALLOW_COPY_AND_ASSIGN(Node); +}; + + +// An entry node has no predecessors and a single successor. +class EntryNode: public Node { + public: + EntryNode() : successor_(NULL) {} + + void AddPredecessor(Node* predecessor) { UNREACHABLE(); } + + void AddSuccessor(Node* successor) { + ASSERT(successor_ == NULL && successor != NULL); + successor_ = successor; + } + + void Traverse(bool mark, + ZoneList* preorder, + ZoneList* postorder); + +#ifdef DEBUG + void PrintText(); +#endif + + private: + Node* successor_; + + DISALLOW_COPY_AND_ASSIGN(EntryNode); +}; + + +// An exit node has a arbitrarily many predecessors and no successors. +class ExitNode: public Node { + public: + ExitNode() : predecessors_(4) {} + + void AddPredecessor(Node* predecessor) { + ASSERT(predecessor != NULL); + predecessors_.Add(predecessor); + } + + void AddSuccessor(Node* successor) { /* Do nothing. */ } + + void Traverse(bool mark, + ZoneList* preorder, + ZoneList* postorder); + +#ifdef DEBUG + void PrintText(); +#endif + + private: + ZoneList predecessors_; + + DISALLOW_COPY_AND_ASSIGN(ExitNode); +}; + + +// Block nodes have a single successor and predecessor and a list of +// instructions. +class BlockNode: public Node { + public: + BlockNode() : predecessor_(NULL), successor_(NULL), instructions_(4) {} + + static BlockNode* cast(Node* node) { + ASSERT(node->IsBlockNode()); + return reinterpret_cast(node); + } + + bool IsBlockNode() { return true; } + + void AddPredecessor(Node* predecessor) { + ASSERT(predecessor_ == NULL && predecessor != NULL); + predecessor_ = predecessor; + } + + void AddSuccessor(Node* successor) { + ASSERT(successor_ == NULL && successor != NULL); + successor_ = successor; + } + + void AddInstruction(AstNode* instruction) { + instructions_.Add(instruction); + } + + void Traverse(bool mark, + ZoneList* preorder, + ZoneList* postorder); + +#ifdef DEBUG + void AssignNumbers(); + void PrintText(); +#endif + + private: + Node* predecessor_; + Node* successor_; + ZoneList instructions_; + + DISALLOW_COPY_AND_ASSIGN(BlockNode); +}; + + +// Branch nodes have a single predecessor and a pair of successors. +class BranchNode: public Node { + public: + BranchNode() : predecessor_(NULL), successor0_(NULL), successor1_(NULL) {} + + void AddPredecessor(Node* predecessor) { + ASSERT(predecessor_ == NULL && predecessor != NULL); + predecessor_ = predecessor; + } + + void AddSuccessor(Node* successor) { + ASSERT(successor1_ == NULL && successor != NULL); + if (successor0_ == NULL) { + successor0_ = successor; + } else { + successor1_ = successor; + } + } + + void Traverse(bool mark, + ZoneList* preorder, + ZoneList* postorder); + +#ifdef DEBUG + void PrintText(); +#endif + + private: + Node* predecessor_; + Node* successor0_; + Node* successor1_; + + DISALLOW_COPY_AND_ASSIGN(BranchNode); +}; + + +// Join nodes have arbitrarily many predecessors and a single successor. +class JoinNode: public Node { + public: + JoinNode() : predecessors_(2), successor_(NULL) {} + + static JoinNode* cast(Node* node) { + ASSERT(node->IsJoinNode()); + return reinterpret_cast(node); + } + + bool IsJoinNode() { return true; } + + void AddPredecessor(Node* predecessor) { + ASSERT(predecessor != NULL); + predecessors_.Add(predecessor); + } + + void AddSuccessor(Node* successor) { + ASSERT(successor_ == NULL && successor != NULL); + successor_ = successor; + } + + void Traverse(bool mark, + ZoneList* preorder, + ZoneList* postorder); + +#ifdef DEBUG + void PrintText(); +#endif + + private: + ZoneList predecessors_; + Node* successor_; + + DISALLOW_COPY_AND_ASSIGN(JoinNode); +}; + + +// Construct a flow graph from a function literal. Build pre- and postorder +// traversal orders as a byproduct. +class FlowGraphBuilder: public AstVisitor { + public: + FlowGraphBuilder() : global_exit_(NULL), preorder_(4), postorder_(4) {} + + void Build(FunctionLiteral* lit); + + FlowGraph* graph() { return &graph_; } + + ZoneList* postorder() { return &postorder_; } + + private: + ExitNode* global_exit() { return global_exit_; } + + // AST node visit functions. +#define DECLARE_VISIT(type) virtual void Visit##type(type* node); + AST_NODE_LIST(DECLARE_VISIT) +#undef DECLARE_VISIT + + FlowGraph graph_; + ExitNode* global_exit_; + ZoneList preorder_; + ZoneList postorder_; + + DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder); +}; + + // This class is used to number all expressions in the AST according to // their evaluation order (post-order left-to-right traversal). class AstLabeler: public AstVisitor { diff --git a/src/flag-definitions.h b/src/flag-definitions.h index a6a3b22..5f5e981 100644 --- a/src/flag-definitions.h +++ b/src/flag-definitions.h @@ -153,6 +153,7 @@ DEFINE_bool(always_fast_compiler, false, "try to use the speculative optimizing backend for all code") DEFINE_bool(trace_bailout, false, "print reasons for falling back to using the classic V8 backend") +DEFINE_bool(use_flow_graph, false, "perform flow-graph based optimizations") // compilation-cache.cc DEFINE_bool(compilation_cache, true, "enable compilation cache") @@ -305,6 +306,8 @@ DEFINE_string(stop_at, "", "function name where to insert a breakpoint") DEFINE_bool(print_builtin_scopes, false, "print scopes for builtins") DEFINE_bool(print_scopes, false, "print scopes") DEFINE_bool(print_ir, false, "print the AST as seen by the backend") +DEFINE_bool(print_graph_text, false, + "print a text representation of the flow graph") // contexts.cc DEFINE_bool(trace_contexts, false, "trace contexts operations") diff --git a/src/prettyprinter.cc b/src/prettyprinter.cc index ca570a6..6e2a60e 100644 --- a/src/prettyprinter.cc +++ b/src/prettyprinter.cc @@ -604,7 +604,7 @@ class IndentedScope BASE_EMBEDDED { ast_printer_->Print(StaticType::Type2String(expr->type())); printed_first = true; } - if (expr->num() != Expression::kNoLabel) { + if (expr->num() != AstNode::kNoNumber) { ast_printer_->Print(printed_first ? ", num = " : " (num = "); ast_printer_->Print("%d", expr->num()); printed_first = true; @@ -679,7 +679,7 @@ void AstPrinter::PrintLiteralWithModeIndented(const char* info, pos += OS::SNPrintF(buf + pos, ", type = %s", StaticType::Type2String(type)); } - if (num != Expression::kNoLabel) { + if (num != AstNode::kNoNumber) { pos += OS::SNPrintF(buf + pos, ", num = %d", num); } OS::SNPrintF(buf + pos, ")"); @@ -740,7 +740,7 @@ void AstPrinter::PrintParameters(Scope* scope) { PrintLiteralWithModeIndented("VAR", scope->parameter(i), scope->parameter(i)->name(), scope->parameter(i)->type(), - Expression::kNoLabel); + AstNode::kNoNumber); } } } @@ -786,7 +786,7 @@ void AstPrinter::VisitDeclaration(Declaration* node) { node->proxy()->AsVariable(), node->proxy()->name(), node->proxy()->AsVariable()->type(), - Expression::kNoLabel); + AstNode::kNoNumber); } else { // function declarations PrintIndented("FUNCTION "); -- 2.7.4