Propagate reaching definitions to the instuctions of a block.

src/data-flow.cc

 // Copyright 2010 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 16 matching lines @@
 
 #include "v8.h"
 
 #include "data-flow.h"
 #include "scopes.h"
 
 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);
   if (exit()->IsExitNode()) return;
   if (!exit()->IsBlockNode()) AppendNode(new BlockNode());
   BlockNode::cast(exit())->AddInstruction(instruction);
 }
 
 
 void FlowGraph::AppendNode(Node* node) {
@@ skipping 303 matching lines @@
 }
 
 
 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 (var != NULL) {
+    if (expr->is_compound()) Visit(expr->target());
     Visit(expr->value());
     if (var->IsStackAllocated()) {
       expr->set_num(definitions_.length());
       definitions_.Add(expr);
     }
 
   } else if (prop != NULL) {
     Visit(prop->obj());
     if (!prop->key()->IsPropertyName()) Visit(prop->key());
     Visit(expr->value());
@@ skipping 956 matching lines @@
 
 
 void AssignedVariablesAnalyzer::VisitObjectLiteral(ObjectLiteral* expr) {
   ASSERT(av_.IsEmpty());
   BitVector result(av_.length());
   for (int i = 0; i < expr->properties()->length(); i++) {
     Visit(expr->properties()->at(i)->value());
     result.Union(av_);
     av_.Clear();
   }
-  av_.CopyFrom(result);
+  av_ = result;
 }
 
 
 void AssignedVariablesAnalyzer::VisitArrayLiteral(ArrayLiteral* expr) {
   ASSERT(av_.IsEmpty());
   BitVector result(av_.length());
   for (int i = 0; i < expr->values()->length(); i++) {
     Visit(expr->values()->at(i));
     result.Union(av_);
     av_.Clear();
   }
-  av_.CopyFrom(result);
+  av_ = result;
 }
 
 
 void AssignedVariablesAnalyzer::VisitCatchExtensionObject(
     CatchExtensionObject* expr) {
   ASSERT(av_.IsEmpty());
   Visit(expr->key());
   ProcessExpression(expr->value());
 }
 
@@ skipping 39 matching lines @@
 
 void AssignedVariablesAnalyzer::VisitCall(Call* expr) {
   ASSERT(av_.IsEmpty());
   Visit(expr->expression());
   BitVector result(av_);
   for (int i = 0; i < expr->arguments()->length(); i++) {
     av_.Clear();
     Visit(expr->arguments()->at(i));
     result.Union(av_);
   }
-  av_.CopyFrom(result);
+  av_ = result;
 }
 
 
 void AssignedVariablesAnalyzer::VisitCallNew(CallNew* expr) {
   ASSERT(av_.IsEmpty());
   Visit(expr->expression());
   BitVector result(av_);
   for (int i = 0; i < expr->arguments()->length(); i++) {
     av_.Clear();
     Visit(expr->arguments()->at(i));
     result.Union(av_);
   }
-  av_.CopyFrom(result);
+  av_ = result;
 }
 
 
 void AssignedVariablesAnalyzer::VisitCallRuntime(CallRuntime* expr) {
   ASSERT(av_.IsEmpty());
   BitVector result(av_);
   for (int i = 0; i < expr->arguments()->length(); i++) {
     av_.Clear();
     Visit(expr->arguments()->at(i));
     result.Union(av_);
   }
-  av_.CopyFrom(result);
+  av_ = result;
 }
 
 
 void AssignedVariablesAnalyzer::VisitUnaryOperation(UnaryOperation* expr) {
   ASSERT(av_.IsEmpty());
   Visit(expr->expression());
 }
 
 
 void AssignedVariablesAnalyzer::VisitCountOperation(CountOperation* expr) {
@@ skipping 175 matching lines @@
 
 void TextInstructionPrinter::VisitSlot(Slot* expr) {
   UNREACHABLE();
 }
 
 
 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());
   }
 }
 
 
 void TextInstructionPrinter::VisitLiteral(Literal* expr) {
   expr->handle()->ShortPrint();
 }
@@ skipping 17 matching lines @@
 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 && 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());
   }
 }
 
 
 void TextInstructionPrinter::VisitThrow(Throw* expr) {
   PrintF("throw @%d", expr->exception()->num());
 }
 
@@ skipping 90 matching lines @@
 
 void Node::AssignNodeNumber() {
   set_number(node_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_in = ");
+    rd_.rd_in()->Print();
+    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_kill = ");
+    rd_.kill()->Print();
+    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_gen = ");
+    rd_.gen()->Print();
+    PrintF("\n");
   }
 }
 
 
 void ExitNode::PrintText() {
   PrintReachingDefinitions();
   PrintF("L%d: Exit\n\n", number());
 }
 
 
@@ skipping 111 matching lines @@
 
 
 void ExitNode::ComputeRDOut(BitVector* result) {
   // Should not be the predecessor of any node.
   UNREACHABLE();
 }
 
 
 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.
   result->Union(*rd_.gen());
 }
 
 
 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();
 }
 
 
 void ExitNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
   // The exit node has no successors so we can just update in place.  New
   // RD_in is the union over all predecessors.
   int definition_count = rd_.rd_in()->length();
   rd_.rd_in()->Clear();
 
   BitVector temp(definition_count);
@@ skipping 10 matching lines @@
 void BlockNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
   // The entry block has no predecessor.  Its RD_in does not change.
   if (predecessor_ == NULL) return;
 
   BitVector new_rd_in(rd_.rd_in()->length());
   predecessor_->ComputeRDOut(&new_rd_in);
 
   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 BranchNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
   BitVector new_rd_in(rd_.rd_in()->length());
   predecessor_->ComputeRDOut(&new_rd_in);
 
   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);
     worklist->Insert(successor0_);
   }
   if (!successor1_->IsMarkedWith(mark)) {
     successor1_->MarkWith(mark);
     worklist->Insert(successor1_);
   }
 }
 
 
 void JoinNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) {
   int definition_count = rd_.rd_in()->length();
   BitVector new_rd_in(definition_count);
 
   // New RD_in is the union over all predecessors.
   BitVector temp(definition_count);
   for (int i = 0, len = predecessors_.length(); i < len; i++) {
     predecessors_[i]->ComputeRDOut(&temp);
     new_rd_in.Union(temp);
   }
 
   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()) {
+      // 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;
 
   int variable_count = variables_.length();
   int definition_count = definitions_->length();
   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);
   }
 
   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(",%d", j);
             }
           }
         }
         PrintF("}\n");
       }
     }
   }
 
   // Step 2: Compute KILL and GEN for each block node, initialize RD_in for
   // all nodes, and mark and add all nodes to the worklist in reverse
   // postorder.  All nodes should currently have the same mark.
   bool mark = postorder_->at(0)->IsMarkedWith(false);  // Negation of current.
   WorkList<Node> worklist(node_count);
   for (int i = node_count - 1; i >= 0; i--) {
     postorder_->at(i)->InitializeReachingDefinitions(definition_count,
                                                      &variables_,
                                                      &worklist,
                                                      mark);
   }
 
   // Step 3: Until the worklist is empty, remove an item compute and update
   // its rd_in based on its predecessor's rd_out.  If rd_in has changed, add
   // all necessary successors to the worklist.
   while (!worklist.is_empty()) {
     Node* node = worklist.Remove();
     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_);
+  }
 }
 
 
 } }  // namespace v8::internal