Revision: 4107
Author: [email protected]
Date: Thu Mar 11 08:24:05 2010
Log: Initialize reaching definitions state for all flow graph nodes.
Reaching definitions in (RD_in) is initially empty for all nodes. Gen
and kill sets are computed. AST node numbers are used for nodes to
refer to their definition number.
Also: two small changes to flow graph printing. Children of branch
nodes are visited in right-to-left order when performing depth first
search. Instructions are numbered locally within blocks so as to not
destroy AST node number before printing (it's useful to print the
definition).
Review URL: http://codereview.chromium.org/876001
http://code.google.com/p/v8/source/detail?r=4107
Modified:
/branches/bleeding_edge/src/ast.h
/branches/bleeding_edge/src/compiler.cc
/branches/bleeding_edge/src/data-flow.cc
/branches/bleeding_edge/src/data-flow.h
=======================================
--- /branches/bleeding_edge/src/ast.h Thu Mar 11 02:34:29 2010
+++ /branches/bleeding_edge/src/ast.h Thu Mar 11 08:24:05 2010
@@ -203,6 +203,8 @@
virtual Expression* AsExpression() { return this; }
virtual bool IsValidLeftHandSide() { return false; }
+
+ virtual Variable* AssignedVar() { return NULL; }
// Symbols that cannot be parsed as array indices are considered property
// names. We do not treat symbols that can be array indexes as property
@@ -1277,6 +1279,10 @@
virtual void Accept(AstVisitor* v);
virtual CountOperation* AsCountOperation() { return this; }
+
+ virtual Variable* AssignedVar() {
+ return expression()->AsVariableProxy()->AsVariable();
+ }
bool is_prefix() const { return is_prefix_; }
bool is_postfix() const { return !is_prefix_; }
@@ -1357,6 +1363,10 @@
virtual Assignment* AsAssignment() { return this; }
Assignment* AsSimpleAssignment() { return !is_compound() ? this : NULL; }
+
+ virtual Variable* AssignedVar() {
+ return target()->AsVariableProxy()->AsVariable();
+ }
Token::Value binary_op() const;
=======================================
--- /branches/bleeding_edge/src/compiler.cc Thu Mar 11 02:28:40 2010
+++ /branches/bleeding_edge/src/compiler.cc Thu Mar 11 08:24:05 2010
@@ -92,6 +92,15 @@
FlowGraphBuilder builder;
builder.Build(function);
+ if (!builder.HasStackOverflow()) {
+ int variable_count =
+ function->num_parameters() +
function->scope()->num_stack_slots();
+ ReachingDefinitions rd(builder.postorder(),
+ builder.definitions(),
+ variable_count);
+ rd.Compute();
+ }
+
#ifdef DEBUG
if (FLAG_print_graph_text && !builder.HasStackOverflow()) {
builder.graph()->PrintText(builder.postorder());
@@ -485,6 +494,15 @@
FlowGraphBuilder builder;
builder.Build(literal);
+ if (!builder.HasStackOverflow()) {
+ int variable_count =
+ literal->num_parameters() + literal->scope()->num_stack_slots();
+ ReachingDefinitions rd(builder.postorder(),
+ builder.definitions(),
+ variable_count);
+ rd.Compute();
+ }
+
#ifdef DEBUG
if (FLAG_print_graph_text && !builder.HasStackOverflow()) {
builder.graph()->PrintText(builder.postorder());
=======================================
--- /branches/bleeding_edge/src/data-flow.cc Thu Mar 11 02:37:29 2010
+++ /branches/bleeding_edge/src/data-flow.cc Thu Mar 11 08:24:05 2010
@@ -133,14 +133,14 @@
ZoneList<Node*>* 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);
}
+ if (!successor0_->IsMarkedWith(mark)) {
+ successor0_->MarkWith(mark);
+ successor0_->Traverse(mark, preorder, postorder);
+ }
postorder->Add(this);
}
@@ -358,7 +358,10 @@
ASSERT(var == NULL || prop == NULL);
if (var != NULL) {
Visit(expr->value());
- if (var->IsStackAllocated()) definitions_.Add(expr);
+ if (var->IsStackAllocated()) {
+ expr->set_num(definitions_.length());
+ definitions_.Add(expr);
+ }
} else if (prop != NULL) {
Visit(prop->obj());
@@ -434,6 +437,7 @@
Visit(expr->expression());
Variable* var = expr->expression()->AsVariableProxy()->AsVariable();
if (var != NULL && var->IsStackAllocated()) {
+ expr->set_num(definitions_.length());
definitions_.Add(expr);
}
@@ -1483,7 +1487,10 @@
// only used for printing in debug mode.
class TextInstructionPrinter: public AstVisitor {
public:
- TextInstructionPrinter() {}
+ TextInstructionPrinter() : number_(0) {}
+
+ int NextNumber() { return number_; }
+ void AssignNumber(AstNode* node) { node->set_num(number_++); }
private:
// AST node visit functions.
@@ -1491,6 +1498,8 @@
AST_NODE_LIST(DECLARE_VISIT)
#undef DECLARE_VISIT
+ int number_;
+
DISALLOW_COPY_AND_ASSIGN(TextInstructionPrinter);
};
@@ -1611,8 +1620,7 @@
void TextInstructionPrinter::VisitVariableProxy(VariableProxy* expr) {
Variable* var = expr->AsVariable();
if (var != NULL) {
- SmartPointer<char> name = var->name()->ToCString();
- PrintF("%s", *name);
+ PrintF("%s", *var->name()->ToCString());
} else {
ASSERT(expr->AsProperty() != NULL);
VisitProperty(expr->AsProperty());
@@ -1651,9 +1659,8 @@
Property* prop = expr->target()->AsProperty();
if (var != NULL) {
- SmartPointer<char> name = var->name()->ToCString();
PrintF("%s %s @%d",
- *name,
+ *var->name()->ToCString(),
Token::String(expr->op()),
expr->value()->num());
} else if (prop != NULL) {
@@ -1675,6 +1682,10 @@
// Throw reference error.
Visit(expr->target());
}
+
+ if (expr->num() != AstNode::kNoNumber) {
+ PrintF(" ;; D%d", expr->num());
+ }
}
@@ -1717,8 +1728,7 @@
void TextInstructionPrinter::VisitCallRuntime(CallRuntime* expr) {
- SmartPointer<char> name = expr->name()->ToCString();
- PrintF("%s(", *name);
+ PrintF("%s(", *expr->name()->ToCString());
ZoneList<Expression*>* arguments = expr->arguments();
for (int i = 0, len = arguments->length(); i < len; i++) {
if (i != 0) PrintF(", ");
@@ -1739,6 +1749,10 @@
} else {
PrintF("@%d%s", expr->expression()->num(), Token::String(expr->op()));
}
+
+ if (expr->num() != AstNode::kNoNumber) {
+ PrintF(" ;; D%d", expr->num());
+ }
}
@@ -1770,31 +1784,66 @@
static int instruction_count = 0;
-void Node::AssignNumbers() {
+void Node::AssignNodeNumber() {
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 Node::PrintReachingDefinitions() {
+ if (rd_.rd_in() != NULL) {
+ ASSERT(rd_.kill() != NULL && rd_.gen() != NULL);
+
+ PrintF("RD_in = {");
+ bool first = true;
+ for (int i = 0; i < rd_.rd_in()->length(); i++) {
+ if (rd_.rd_in()->Contains(i)) {
+ if (!first) PrintF(",");
+ PrintF("%d");
+ first = false;
+ }
+ }
+ PrintF("}\n");
+
+ PrintF("RD_kill = {");
+ first = true;
+ for (int i = 0; i < rd_.kill()->length(); i++) {
+ if (rd_.kill()->Contains(i)) {
+ if (!first) PrintF(",");
+ PrintF("%d");
+ first = false;
+ }
+ }
+ PrintF("}\n");
+
+ PrintF("RD_gen = {");
+ first = true;
+ for (int i = 0; i < rd_.gen()->length(); i++) {
+ if (rd_.gen()->Contains(i)) {
+ if (!first) PrintF(",");
+ PrintF("%d");
+ first = false;
+ }
+ }
+ PrintF("}\n");
}
}
void ExitNode::PrintText() {
+ PrintReachingDefinitions();
PrintF("L%d: Exit\n\n", number());
}
void BlockNode::PrintText() {
+ PrintReachingDefinitions();
// 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());
+ PrintF("%d ", printer.NextNumber());
printer.Visit(instructions_[i]);
+ printer.AssignNumber(instructions_[i]);
PrintF("\n");
}
PrintF("goto L%d\n\n", successor_->number());
@@ -1802,12 +1851,14 @@
void BranchNode::PrintText() {
+ PrintReachingDefinitions();
PrintF("L%d: Branch\n", number());
PrintF("goto (L%d, L%d)\n\n", successor0_->number(),
successor1_->number());
}
void JoinNode::PrintText() {
+ PrintReachingDefinitions();
PrintF("L%d: Join(", number());
for (int i = 0, len = predecessors_.length(); i < len; i++) {
if (i != 0) PrintF(", ");
@@ -1824,7 +1875,7 @@
node_count = 0;
instruction_count = 0;
for (int i = postorder->length() - 1; i >= 0; i--) {
- postorder->at(i)->AssignNumbers();
+ postorder->at(i)->AssignNodeNumber();
}
// Print basic blocks in reverse postorder.
@@ -1837,4 +1888,95 @@
#endif // defined(DEBUG)
+int ReachingDefinitions::IndexFor(Variable* var, int variable_count) {
+ // Parameters are numbered left-to-right from the beginning of the bit
+ // set. Stack-allocated locals are allocated right-to-left from the end.
+ ASSERT(var != NULL && var->IsStackAllocated());
+ Slot* slot = var->slot();
+ if (slot->type() == Slot::PARAMETER) {
+ return slot->index();
+ } else {
+ return (variable_count - 1) - slot->index();
+ }
+}
+
+
+void Node::InitializeReachingDefinitions(int definition_count,
+ List<BitVector*>* variables) {
+ rd_.Initialize(definition_count);
+}
+
+
+void BlockNode::InitializeReachingDefinitions(int definition_count,
+ List<BitVector*>* variables)
{
+ int instruction_count = instructions_.length();
+ int variable_count = variables->length();
+
+ rd_.Initialize(definition_count);
+
+ for (int i = 0; i < instruction_count; i++) {
+ Expression* expr = instructions_[i]->AsExpression();
+ if (expr == NULL) continue;
+ Variable* var = expr->AssignedVar();
+ if (var == NULL) continue;
+
+ // All definitions of this variable are killed.
+ BitVector* def_set =
+ variables->at(ReachingDefinitions::IndexFor(var, variable_count));
+ rd_.kill()->Union(*def_set);
+
+ // All previously generated definitions are not generated.
+ rd_.gen()->Subtract(*def_set);
+
+ // This one is generated.
+ rd_.gen()->Add(expr->num());
+ }
+}
+
+
+void ReachingDefinitions::Compute() {
+ if (definitions_->is_empty()) return;
+
+ int variable_count = variables_.length();
+ int definition_count = definitions_->length();
+ int block_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);
+ }
+
+ 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");
+ }
+ }
+ }
+
+ // Step 2: Compute KILL and GEN for each block node, initialize RD.
+ for (int i = block_count - 1; i >= 0; i--) {
+ postorder_->at(i)->InitializeReachingDefinitions(definition_count,
+ &variables_);
+ }
+}
+
+
} } // namespace v8::internal
=======================================
--- /branches/bleeding_edge/src/data-flow.h Thu Mar 11 02:28:40 2010
+++ /branches/bleeding_edge/src/data-flow.h Thu Mar 11 08:24:05 2010
@@ -99,6 +99,13 @@
data_[i] &= other.data_[i];
}
}
+
+ void Subtract(const BitVector& other) {
+ ASSERT(other.length() == length());
+ for (int i = 0; i < data_length_; i++) {
+ data_[i] &= ~other.data_[i];
+ }
+ }
void Clear() {
for (int i = 0; i < data_length_; i++) {
@@ -122,6 +129,27 @@
};
+class ReachingDefinitionsData BASE_EMBEDDED {
+ public:
+ ReachingDefinitionsData() : rd_in_(NULL), kill_(NULL), gen_(NULL) {}
+
+ void Initialize(int definition_count) {
+ rd_in_ = new BitVector(definition_count);
+ kill_ = new BitVector(definition_count);
+ gen_ = new BitVector(definition_count);
+ }
+
+ BitVector* rd_in() { return rd_in_; }
+ BitVector* kill() { return kill_; }
+ BitVector* gen() { return gen_; }
+
+ private:
+ BitVector* rd_in_;
+ BitVector* kill_;
+ BitVector* gen_;
+};
+
+
// Flow-graph nodes.
class Node: public ZoneObject {
public:
@@ -148,12 +176,20 @@
int number() { return number_; }
void set_number(int number) { number_ = number; }
+
+ // Functions used by data-flow analyses.
+ virtual void InitializeReachingDefinitions(int definition_count,
+ List<BitVector*>* variables);
#ifdef DEBUG
- virtual void AssignNumbers();
+ void AssignNodeNumber();
+ void PrintReachingDefinitions();
virtual void PrintText() = 0;
#endif
+ protected:
+ ReachingDefinitionsData rd_;
+
private:
int number_;
bool mark_;
@@ -224,8 +260,10 @@
ZoneList<Node*>* preorder,
ZoneList<Node*>* postorder);
+ void InitializeReachingDefinitions(int definition_count,
+ List<BitVector*>* variables);
+
#ifdef DEBUG
- void AssignNumbers();
void PrintText();
#endif
@@ -384,8 +422,8 @@
void Build(FunctionLiteral* lit);
FlowGraph* graph() { return &graph_; }
-
ZoneList<Node*>* postorder() { return &postorder_; }
+ ZoneList<Expression*>* definitions() { return &definitions_; }
private:
ExitNode* global_exit() { return global_exit_; }
@@ -402,8 +440,9 @@
// The flow graph builder collects a list of definitions (assignments and
// count operations) to stack-allocated variables to use for reaching
- // definitions analysis.
- ZoneList<AstNode*> definitions_;
+ // definitions analysis. AST node numbers in the AST are used to refer
+ // into this list.
+ ZoneList<Expression*> definitions_;
DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder);
};
@@ -521,6 +560,39 @@
DISALLOW_COPY_AND_ASSIGN(AssignedVariablesAnalyzer);
};
+
+class ReachingDefinitions BASE_EMBEDDED {
+ public:
+ ReachingDefinitions(ZoneList<Node*>* postorder,
+ ZoneList<Expression*>* 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));
+ }
+ }
+
+ static int IndexFor(Variable* var, int variable_count);
+
+ void Compute();
+
+ private:
+ // A (postorder) list of flow-graph nodes in the body.
+ ZoneList<Node*>* postorder_;
+
+ // A list of all the definitions in the body.
+ ZoneList<Expression*>* definitions_;
+
+ // For each variable, the set of all its definitions.
+ List<BitVector*> variables_;
+
+ DISALLOW_COPY_AND_ASSIGN(ReachingDefinitions);
+};
+
+
} } // namespace v8::internal
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
