Revision: 4143
Author: [email protected]
Date: Tue Mar 16 03:54:02 2010
Log: Propagate reaching definitions to the instuctions of a block.
After computing RD_in for all flow graph nodes, push the reaching
definitions through the basic blocks to annotate all variable
references in the AST.
Review URL: http://codereview.chromium.org/889003
http://code.google.com/p/v8/source/detail?r=4143
Modified:
/branches/bleeding_edge/src/ast.cc
/branches/bleeding_edge/src/ast.h
/branches/bleeding_edge/src/data-flow.cc
/branches/bleeding_edge/src/data-flow.h
=======================================
--- /branches/bleeding_edge/src/ast.cc Fri Mar 12 05:10:42 2010
+++ /branches/bleeding_edge/src/ast.cc Tue Mar 16 03:54:02 2010
@@ -78,14 +78,16 @@
var_(NULL),
is_this_(is_this),
inside_with_(inside_with),
- is_trivial_(false) {
+ is_trivial_(false),
+ reaching_definitions_(NULL) {
// names must be canonicalized for fast equality checks
ASSERT(name->IsSymbol());
}
VariableProxy::VariableProxy(bool is_this)
- : is_this_(is_this) {
+ : is_this_(is_this),
+ reaching_definitions_(NULL) {
}
=======================================
--- /branches/bleeding_edge/src/ast.h Mon Mar 15 07:03:36 2010
+++ /branches/bleeding_edge/src/ast.h Tue Mar 16 03:54:02 2010
@@ -103,6 +103,7 @@
class TargetCollector;
class MaterializedLiteral;
class DefinitionInfo;
+class BitVector;
#define DEF_FORWARD_DECLARATION(type) class type;
AST_NODE_LIST(DEF_FORWARD_DECLARATION)
@@ -1040,6 +1041,9 @@
bool inside_with() const { return inside_with_; }
bool is_trivial() { return is_trivial_; }
void set_is_trivial(bool b) { is_trivial_ = b; }
+
+ BitVector* reaching_definitions() { return reaching_definitions_; }
+ void set_reaching_definitions(BitVector* rd) { reaching_definitions_ =
rd; }
// Bind this proxy to the variable var.
void BindTo(Variable* var);
@@ -1050,6 +1054,7 @@
bool is_this_;
bool inside_with_;
bool is_trivial_;
+ BitVector* reaching_definitions_;
VariableProxy(Handle<String> name, bool is_this, bool inside_with);
explicit VariableProxy(bool is_this);
=======================================
--- /branches/bleeding_edge/src/data-flow.cc Fri Mar 12 07:01:05 2010
+++ /branches/bleeding_edge/src/data-flow.cc Tue Mar 16 03:54:02 2010
@@ -34,6 +34,22 @@
namespace internal {
+#ifdef DEBUG
+void BitVector::Print() {
+ bool first = true;
+ PrintF("{");
+ for (int i = 0; i < length(); i++) {
+ if (Contains(i)) {
+ if (!first) PrintF(",");
+ first = false;
+ PrintF("%d");
+ }
+ }
+ PrintF("}");
+}
+#endif
+
+
void FlowGraph::AppendInstruction(AstNode* instruction) {
// Add a (non-null) AstNode to the end of the graph fragment.
ASSERT(instruction != NULL);
@@ -357,6 +373,7 @@
// not both.
ASSERT(var == NULL || prop == NULL);
if (var != NULL) {
+ if (expr->is_compound()) Visit(expr->target());
Visit(expr->value());
if (var->IsStackAllocated()) {
expr->set_num(definitions_.length());
@@ -1333,7 +1350,7 @@
result.Union(av_);
av_.Clear();
}
- av_.CopyFrom(result);
+ av_ = result;
}
@@ -1345,7 +1362,7 @@
result.Union(av_);
av_.Clear();
}
- av_.CopyFrom(result);
+ av_ = result;
}
@@ -1405,7 +1422,7 @@
Visit(expr->arguments()->at(i));
result.Union(av_);
}
- av_.CopyFrom(result);
+ av_ = result;
}
@@ -1418,7 +1435,7 @@
Visit(expr->arguments()->at(i));
result.Union(av_);
}
- av_.CopyFrom(result);
+ av_ = result;
}
@@ -1430,7 +1447,7 @@
Visit(expr->arguments()->at(i));
result.Union(av_);
}
- av_.CopyFrom(result);
+ av_ = result;
}
@@ -1626,6 +1643,9 @@
Variable* var = expr->AsVariable();
if (var != NULL) {
PrintF("%s", *var->name()->ToCString());
+ if (var->IsStackAllocated() && expr->reaching_definitions() != NULL) {
+ expr->reaching_definitions()->Print();
+ }
} else {
ASSERT(expr->AsProperty() != NULL);
VisitProperty(expr->AsProperty());
@@ -1663,30 +1683,50 @@
Variable* var = expr->target()->AsVariableProxy()->AsVariable();
Property* prop = expr->target()->AsProperty();
+ if (var == NULL && prop == NULL) {
+ // Throw reference error.
+ Visit(expr->target());
+ return;
+ }
+
+ // Print the left-hand side.
if (var != NULL) {
- PrintF("%s %s @%d",
- *var->name()->ToCString(),
- Token::String(expr->op()),
- expr->value()->num());
+ PrintF("%s", *var->name()->ToCString());
} else if (prop != NULL) {
+ PrintF("@%d", prop->obj()->num());
if (prop->key()->IsPropertyName()) {
- PrintF("@%d.", prop->obj()->num());
+ PrintF(".");
ASSERT(prop->key()->AsLiteral() != NULL);
prop->key()->AsLiteral()->handle()->Print();
- PrintF(" %s @%d",
- Token::String(expr->op()),
- expr->value()->num());
} else {
- PrintF("@%...@%d] %s @%d",
- prop->obj()->num(),
- prop->key()->num(),
- Token::String(expr->op()),
- expr->value()->num());
- }
+ PrintF("[...@%d]", prop->key()->num());
+ }
+ }
+
+ // Print the operation.
+ if (expr->is_compound()) {
+ PrintF(" = ");
+ // Print the left-hand side again when compound.
+ if (var != NULL) {
+ PrintF("@%d", expr->target()->num());
+ } else {
+ PrintF("@%d", prop->obj()->num());
+ if (prop->key()->IsPropertyName()) {
+ PrintF(".");
+ ASSERT(prop->key()->AsLiteral() != NULL);
+ prop->key()->AsLiteral()->handle()->Print();
+ } else {
+ PrintF("[...@%d]", prop->key()->num());
+ }
+ }
+ // Print the corresponding binary operator.
+ PrintF(" %s ", Token::String(expr->binary_op()));
} else {
- // Throw reference error.
- Visit(expr->target());
- }
+ PrintF(" %s ", Token::String(expr->op()));
+ }
+
+ // Print the right-hand side.
+ PrintF("@%d", expr->value()->num());
if (expr->num() != AstNode::kNoNumber) {
PrintF(" ;; D%d", expr->num());
@@ -1798,38 +1838,17 @@
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");
+ PrintF("RD_in = ");
+ rd_.rd_in()->Print();
+ PrintF("\n");
+
+ PrintF("RD_kill = ");
+ rd_.kill()->Print();
+ PrintF("\n");
+
+ PrintF("RD_gen = ");
+ rd_.gen()->Print();
+ PrintF("\n");
}
}
@@ -1961,7 +1980,7 @@
void BlockNode::ComputeRDOut(BitVector* result) {
// All definitions reaching this block ...
- result->CopyFrom(*rd_.rd_in());
+ *result = *rd_.rd_in();
// ... except those killed by the block ...
result->Subtract(*rd_.kill());
// ... but including those generated by the block.
@@ -1971,13 +1990,13 @@
void BranchNode::ComputeRDOut(BitVector* result) {
// Branch nodes don't kill or generate definitions.
- result->CopyFrom(*rd_.rd_in());
+ *result = *rd_.rd_in();
}
void JoinNode::ComputeRDOut(BitVector* result) {
// Join nodes don't kill or generate definitions.
- result->CopyFrom(*rd_.rd_in());
+ *result = *rd_.rd_in();
}
@@ -2008,7 +2027,7 @@
if (rd_.rd_in()->Equals(new_rd_in)) return;
// Update RD_in.
- rd_.rd_in()->CopyFrom(new_rd_in);
+ *rd_.rd_in() = new_rd_in;
// Add the successor to the worklist if not already present.
if (!successor_->IsMarkedWith(mark)) {
successor_->MarkWith(mark);
@@ -2024,7 +2043,7 @@
if (rd_.rd_in()->Equals(new_rd_in)) return;
// Update RD_in.
- rd_.rd_in()->CopyFrom(new_rd_in);
+ *rd_.rd_in() = new_rd_in;
// Add the successors to the worklist if not already present.
if (!successor0_->IsMarkedWith(mark)) {
successor0_->MarkWith(mark);
@@ -2051,13 +2070,73 @@
if (rd_.rd_in()->Equals(new_rd_in)) return;
// Update RD_in.
- rd_.rd_in()->CopyFrom(new_rd_in);
+ *rd_.rd_in() = new_rd_in;
// Add the successor to the worklist if not already present.
if (!successor_->IsMarkedWith(mark)) {
successor_->MarkWith(mark);
worklist->Insert(successor_);
}
}
+
+
+void Node::PropagateReachingDefinitions(List<BitVector*>* variables) {
+ // Nothing to do.
+}
+
+
+void BlockNode::PropagateReachingDefinitions(List<BitVector*>* variables) {
+ // Propagate RD_in from the start of the block to all the variable
+ // references.
+ int variable_count = variables->length();
+ BitVector rd = *rd_.rd_in();
+ for (int i = 0, len = instructions_.length(); i < len; i++) {
+ Expression* expr = instructions_[i]->AsExpression();
+ if (expr == NULL) continue;
+
+ // Look for a variable reference to record its reaching definitions.
+ VariableProxy* proxy = expr->AsVariableProxy();
+ if (proxy == NULL) {
+ // Not a VariableProxy? Maybe it's a count operation.
+ CountOperation* count_operation = expr->AsCountOperation();
+ if (count_operation != NULL) {
+ proxy = count_operation->expression()->AsVariableProxy();
+ }
+ }
+ if (proxy == NULL) {
+ // OK, Maybe it's a compound assignment.
+ Assignment* assignment = expr->AsAssignment();
+ if (assignment != NULL && assignment->is_compound()) {
+ proxy = assignment->target()->AsVariableProxy();
+ }
+ }
+
+ if (proxy != NULL &&
+ proxy->var()->IsStackAllocated() &&
+ !proxy->var()->is_this()) {
+ // All definitions for this variable.
+ BitVector* definitions =
+ variables->at(ReachingDefinitions::IndexFor(proxy->var(),
+ variable_count));
+ BitVector* reaching_definitions = new BitVector(*definitions);
+ // Intersected with all definitions (of any variable) reaching this
+ // instruction.
+ reaching_definitions->Intersect(rd);
+ proxy->set_reaching_definitions(reaching_definitions);
+ }
+
+ // It may instead (or also) be a definition. If so update the running
+ // value of reaching definitions for the block.
+ Variable* var = expr->AssignedVar();
+ if (var == NULL || !var->IsStackAllocated()) continue;
+
+ // All definitions of this variable are killed.
+ BitVector* def_set =
+ variables->at(ReachingDefinitions::IndexFor(var, variable_count));
+ rd.Subtract(*def_set);
+ // This definition is generated.
+ rd.Add(expr->num());
+ }
+}
void ReachingDefinitions::Compute() {
@@ -2088,7 +2167,7 @@
PrintF("Def[%s] = {%d", *var->name()->ToCString(), j);
first = false;
} else {
- PrintF(", %d", j);
+ PrintF(",%d", j);
}
}
}
@@ -2117,6 +2196,12 @@
node->MarkWith(!mark);
node->UpdateRDIn(&worklist, mark);
}
+
+ // 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_);
+ }
}
=======================================
--- /branches/bleeding_edge/src/data-flow.h Fri Mar 12 02:39:31 2010
+++ /branches/bleeding_edge/src/data-flow.h Tue Mar 16 03:54:02 2010
@@ -128,6 +128,10 @@
}
int length() const { return length_; }
+
+#ifdef DEBUG
+ void Print();
+#endif
private:
int length_;
@@ -235,6 +239,7 @@
bool mark);
virtual void ComputeRDOut(BitVector* result) = 0;
virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark) = 0;
+ virtual void PropagateReachingDefinitions(List<BitVector*>* variables);
#ifdef DEBUG
void AssignNodeNumber();
@@ -324,6 +329,7 @@
bool mark);
void ComputeRDOut(BitVector* result);
void UpdateRDIn(WorkList<Node>* worklist, bool mark);
+ void PropagateReachingDefinitions(List<BitVector*>* variables);
#ifdef DEBUG
void PrintText();
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
