From 82a673b8bfbcaafb117eafb99584282c9cf5c395 Mon Sep 17 00:00:00 2001 From: "kmillikin@chromium.org" Date: Mon, 22 Mar 2010 14:07:18 +0000 Subject: [PATCH] Include initial definitions in reaching definitions analysis. Include the initial definitions for parameters on input to the function, and the initial definition of stack-allocated locals as undefined. Review URL: http://codereview.chromium.org/1155006 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4206 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/compiler.cc | 20 ++++++++--------- src/data-flow.cc | 68 ++++++++++++++++++++++++++------------------------------ src/data-flow.h | 35 ++++++++++++++--------------- 3 files changed, 58 insertions(+), 65 deletions(-) diff --git a/src/compiler.cc b/src/compiler.cc index 3cdf1de..249580c 100755 --- a/src/compiler.cc +++ b/src/compiler.cc @@ -89,15 +89,15 @@ static Handle MakeCode(Handle context, CompilationInfo* info) { } if (FLAG_use_flow_graph) { - FlowGraphBuilder builder; + int variable_count = + function->num_parameters() + function->scope()->num_stack_slots(); + FlowGraphBuilder builder(variable_count); builder.Build(function); if (!builder.HasStackOverflow()) { - int variable_count = - function->num_parameters() + function->scope()->num_stack_slots(); - if (variable_count > 0 && builder.definitions()->length() > 0) { + if (variable_count > 0) { ReachingDefinitions rd(builder.postorder(), - builder.definitions(), + builder.body_definitions(), variable_count); rd.Compute(); } @@ -497,15 +497,15 @@ Handle Compiler::BuildBoilerplate(FunctionLiteral* literal, } if (FLAG_use_flow_graph) { - FlowGraphBuilder builder; + int variable_count = + literal->num_parameters() + literal->scope()->num_stack_slots(); + FlowGraphBuilder builder(variable_count); builder.Build(literal); if (!builder.HasStackOverflow()) { - int variable_count = - literal->num_parameters() + literal->scope()->num_stack_slots(); - if (variable_count > 0 && builder.definitions()->length() > 0) { + if (variable_count > 0) { ReachingDefinitions rd(builder.postorder(), - builder.definitions(), + builder.body_definitions(), variable_count); rd.Compute(); } diff --git a/src/data-flow.cc b/src/data-flow.cc index bf131f4..00a8013 100644 --- a/src/data-flow.cc +++ b/src/data-flow.cc @@ -451,8 +451,10 @@ void FlowGraphBuilder::VisitAssignment(Assignment* expr) { if (expr->is_compound()) Visit(expr->target()); Visit(expr->value()); if (var->IsStackAllocated()) { - expr->set_num(definitions_.length()); - definitions_.Add(expr); + // 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) { @@ -529,8 +531,10 @@ void FlowGraphBuilder::VisitCountOperation(CountOperation* expr) { Visit(expr->expression()); Variable* var = expr->expression()->AsVariableProxy()->AsVariable(); if (var != NULL && var->IsStackAllocated()) { - expr->set_num(definitions_.length()); - definitions_.Add(expr); + // 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; @@ -1740,6 +1744,11 @@ void BlockNode::InitializeReachingDefinitions(int definition_count, 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(); @@ -1935,40 +1944,25 @@ void BlockNode::PropagateReachingDefinitions(List* variables) { void ReachingDefinitions::Compute() { - ASSERT(!definitions_->is_empty()); - - int variable_count = variables_.length(); - int definition_count = definitions_->length(); + // 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 variable, identify the set of all its definitions in - // the body. - for (int i = 0; i < definition_count; i++) { - Variable* var = definitions_->at(i)->AssignedVar(); - variables_[IndexFor(var, variable_count)]->Add(i); + // Step 1: For each stack-allocated variable, identify the set of all its + // definitions. + List 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); } - - if (FLAG_print_graph_text) { - for (int i = 0; i < variable_count; i++) { - BitVector* def_set = variables_[i]; - if (!def_set->IsEmpty()) { - // At least one definition. - bool first = true; - for (int j = 0; j < definition_count; j++) { - if (def_set->Contains(j)) { - if (first) { - Variable* var = definitions_->at(j)->AssignedVar(); - ASSERT(var != NULL); - PrintF("Def[%s] = {%d", *var->name()->ToCString(), j); - first = false; - } else { - PrintF(",%d", j); - } - } - } - PrintF("}\n"); - } - } + 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)->AssignedVar(); + variables[IndexFor(var, variable_count_)]->Add(i + variable_count_); } // Step 2: Compute KILL and GEN for each block node, initialize RD_in for @@ -1978,7 +1972,7 @@ void ReachingDefinitions::Compute() { WorkList worklist(node_count); for (int i = node_count - 1; i >= 0; i--) { postorder_->at(i)->InitializeReachingDefinitions(definition_count, - &variables_, + &variables, &worklist, mark); } @@ -1995,7 +1989,7 @@ void ReachingDefinitions::Compute() { // 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_); + postorder_->at(i)->PropagateReachingDefinitions(&variables); } } diff --git a/src/data-flow.h b/src/data-flow.h index b175ed0..874b418 100644 --- a/src/data-flow.h +++ b/src/data-flow.h @@ -485,18 +485,20 @@ class FlowGraph BASE_EMBEDDED { // traversal orders as a byproduct. class FlowGraphBuilder: public AstVisitor { public: - FlowGraphBuilder() + explicit FlowGraphBuilder(int variable_count) : graph_(FlowGraph::Empty()), global_exit_(NULL), preorder_(4), postorder_(4), - definitions_(4) {} + variable_count_(variable_count), + body_definitions_(4) { + } void Build(FunctionLiteral* lit); FlowGraph* graph() { return &graph_; } ZoneList* postorder() { return &postorder_; } - ZoneList* definitions() { return &definitions_; } + ZoneList* body_definitions() { return &body_definitions_; } private: ExitNode* global_exit() { return global_exit_; } @@ -515,11 +517,13 @@ class FlowGraphBuilder: public AstVisitor { ZoneList preorder_; ZoneList postorder_; - // The flow graph builder collects a list of definitions (assignments and - // count operations) to stack-allocated variables to use for reaching - // definitions analysis. AST node numbers in the AST are used to refer - // into this list. - ZoneList definitions_; + // The flow graph builder collects a list of explicit definitions + // (assignments and count operations) to stack-allocated variables to use + // for reaching definitions analysis. It does not count the implicit + // definition at function entry. AST node numbers in the AST are used to + // refer into this list. + int variable_count_; + ZoneList body_definitions_; DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder); }; @@ -592,15 +596,11 @@ class AssignedVariablesAnalyzer : public AstVisitor { class ReachingDefinitions BASE_EMBEDDED { public: ReachingDefinitions(ZoneList* postorder, - ZoneList* definitions, + ZoneList* body_definitions, int variable_count) : postorder_(postorder), - definitions_(definitions), - variables_(variable_count) { - int definition_count = definitions->length(); - for (int i = 0; i < variable_count; i++) { - variables_.Add(new BitVector(definition_count)); - } + body_definitions_(body_definitions), + variable_count_(variable_count) { } static int IndexFor(Variable* var, int variable_count); @@ -612,10 +612,9 @@ class ReachingDefinitions BASE_EMBEDDED { ZoneList* postorder_; // A list of all the definitions in the body. - ZoneList* definitions_; + ZoneList* body_definitions_; - // For each variable, the set of all its definitions. - List variables_; + int variable_count_; DISALLOW_COPY_AND_ASSIGN(ReachingDefinitions); }; -- 2.7.4