Propagate reaching definitions to the instuctions of a block.

src/data-flow.cc

Index: src/data-flow.cc
diff --git a/src/data-flow.cc b/src/data-flow.cc
index ac12502c071b5dea3a50423805feb88579c4a39f..b0f6255adcef934e310c0cf85ec6eb30a5fad369 100644
--- a/src/data-flow.cc
+++ b/src/data-flow.cc
@@ -34,6 +34,22 @@ namespace v8 {
 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 @@ void FlowGraphBuilder::VisitAssignment(Assignment* expr) {
   // 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 @@ void AssignedVariablesAnalyzer::VisitObjectLiteral(ObjectLiteral* expr) {
     result.Union(av_);
     av_.Clear();
   }
-  av_.CopyFrom(result);
+  av_ = result;
 }
 
 
@@ -1345,7 +1362,7 @@ void AssignedVariablesAnalyzer::VisitArrayLiteral(ArrayLiteral* expr) {
     result.Union(av_);
     av_.Clear();
   }
-  av_.CopyFrom(result);
+  av_ = result;
 }
 
 
@@ -1405,7 +1422,7 @@ void AssignedVariablesAnalyzer::VisitCall(Call* expr) {
     Visit(expr->arguments()->at(i));
     result.Union(av_);
   }
-  av_.CopyFrom(result);
+  av_ = result;
 }
 
 
@@ -1418,7 +1435,7 @@ void AssignedVariablesAnalyzer::VisitCallNew(CallNew* expr) {
     Visit(expr->arguments()->at(i));
     result.Union(av_);
   }
-  av_.CopyFrom(result);
+  av_ = result;
 }
 
 
@@ -1430,7 +1447,7 @@ void AssignedVariablesAnalyzer::VisitCallRuntime(CallRuntime* expr) {
     Visit(expr->arguments()->at(i));
     result.Union(av_);
   }
-  av_.CopyFrom(result);
+  av_ = result;
 }
 
 
@@ -1626,6 +1643,9 @@ void TextInstructionPrinter::VisitVariableProxy(VariableProxy* expr) {
   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,31 +1683,51 @@ void TextInstructionPrinter::VisitAssignment(Assignment* expr) {
   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[@%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 @@ 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");
+    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 ExitNode::ComputeRDOut(BitVector* result) {
 
 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 BlockNode::ComputeRDOut(BitVector* result) {
 
 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 @@ void BlockNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
   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 @@ void BranchNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
   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,7 +2070,7 @@ void JoinNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
   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);
@@ -2060,6 +2079,69 @@ void JoinNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
 }
 
 
+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()) {
+      // 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);
+      continue;
+    }
+
+    Assignment* assignment = expr->AsAssignment();
+    if (assignment != NULL) {
+    }

[fschneider, 2010/03/15 10:11:15]

Misplaced brackets?

+
+    // For an assignment, 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() {
   if (definitions_->is_empty()) return;
 
@@ -2088,7 +2170,7 @@ void ReachingDefinitions::Compute() {
               PrintF("Def[%s] = {%d", *var->name()->ToCString(), j);
               first = false;
             } else {
-              PrintF(", %d", j);
+              PrintF(",%d", j);
             }
           }
         }
@@ -2117,6 +2199,12 @@ void ReachingDefinitions::Compute() {
     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_);
+  }
 }