Compute reaching definitions.

src/data-flow.cc

Index: src/data-flow.cc
diff --git a/src/data-flow.cc b/src/data-flow.cc
index 434991c8dd34ece0251677f5bee159d32a5a74f2..7cdc46f3ca143e1249b08b1341905efee6d54b15 100644
--- a/src/data-flow.cc
+++ b/src/data-flow.cc
@@ -1902,13 +1902,21 @@ int ReachingDefinitions::IndexFor(Variable* var, int variable_count) {
 
 
 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();
 
@@ -1931,6 +1939,114 @@ void BlockNode::InitializeReachingDefinitions(int definition_count,
     // 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_);
+  }
 }
 
 
@@ -1939,7 +2055,7 @@ void ReachingDefinitions::Compute() {
 
   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.
@@ -1971,10 +2087,25 @@ void ReachingDefinitions::Compute() {
     }
   }
 
-  // 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);
   }
 }