Compute reaching definitions.

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 1884 matching lines @@
   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) {
+                                         List<BitVector*>* variables,
+                                         WorkList<Node>* worklist,
+                                         bool mark) {
+  ASSERT(!IsMarkedWith(mark));
   rd_.Initialize(definition_count);
+  MarkWith(mark);
+  worklist->Insert(this);
 }
 
 
 void BlockNode::InitializeReachingDefinitions(int definition_count,
-                                              List<BitVector*>* variables) {
+                                              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);
 
   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());
   }
+
+  if (predecessor_ != NULL) {
+    MarkWith(mark);
+    worklist->Insert(this);
+  }
 }
 
 
+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());
+  // ... 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());
+}
+
+
+void JoinNode::ComputeRDOut(BitVector* result) {
+  // Join nodes don't kill or generate definitions.
+  result->CopyFrom(*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();
+  for (int i = 0, len = predecessors_.length(); i < len; i++) {
+    BitVector temp(definition_count);
+    predecessors_[i]->ComputeRDOut(&temp);
+    rd_.rd_in()->Union(temp);
+  }
+}
+
+
+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);
+  // 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);
+  // 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.
+  for (int i = 0, len = predecessors_.length(); i < len; i++) {
+    BitVector temp(definition_count);
+    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);
+  // Add the successor to the worklist if not already present.
+  if (!successor_->IsMarkedWith(mark)) {
+    successor_->MarkWith(mark);
+    worklist->Insert(successor_);
+  }
+}
+
+
 void ReachingDefinitions::Compute() {
   if (definitions_->is_empty()) return;
 
   int variable_count = variables_.length();
   int definition_count = definitions_->length();
-  int block_count = postorder_->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++) {
@@ skipping 11 matching lines @@
             } 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--) {
+  // 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);
   }
 }
 
 
 } }  // namespace v8::internal