Include initial definitions in reaching definitions analysis.

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 358 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);
+      // 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) {
     Visit(prop->obj());
     if (!prop->key()->IsPropertyName()) Visit(prop->key());
     Visit(expr->value());
   }
 
   if (HasStackOverflow()) return;
   graph_.AppendInstruction(expr);
@@ skipping 56 matching lines @@
     default:
       UNREACHABLE();
   }
 }
 
 
 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;
   graph_.AppendInstruction(expr);
 }
 
 
 void FlowGraphBuilder::VisitBinaryOperation(BinaryOperation* expr) {
   switch (expr->op()) {
     case Token::COMMA:
@@ skipping 1188 matching lines @@
 
 void BlockNode::InitializeReachingDefinitions(int definition_count,
                                               List<BitVector*>* variables,
                                               WorkList<Node>* worklist,
                                               bool mark) {
   ASSERT(!IsMarkedWith(mark));
   int instruction_count = instructions_.length();
   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();
     if (expr == NULL) continue;
     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));
@@ skipping 175 matching lines @@
     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() {
-  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

[fschneider, 2010/03/22 13:49:29]

We don't handle any other variables? Maybe change comment:

(stack-allocated) -> stack-allocated

[Kevin Millikin (Chromium), 2010/03/22 14:06:40]

Done.

+  // its definitions.
+  List<BitVector*> 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_);

[fschneider, 2010/03/22 13:49:29]

variables->at(IndexFor(var, variable_count_))

for consistency with the rest?

[Kevin Millikin (Chromium), 2010/03/22 14:06:40]

It would be variables.at(...).  I'll leave it with [] for now.

   }
 
   // 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_,
+                                                     &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_);
+    postorder_->at(i)->PropagateReachingDefinitions(&variables);
   }
 }
 
 
 } }  // namespace v8::internal