Revision: 4113
Author: [email protected]
Date: Fri Mar 12 02:35:45 2010
Log: Compute reaching definitions.
Use the classical worklist algorithm to compute reaching definitions.
All nodes are initially put on the worklist. Until the worklist is
empty, nodes are removed, their RD_in is recomputed, and if it changes
their successors are added to the worklist.
Review URL: http://codereview.chromium.org/853004
http://code.google.com/p/v8/source/detail?r=4113
Modified:
/branches/bleeding_edge/src/data-flow.cc
/branches/bleeding_edge/src/data-flow.h
=======================================
--- /branches/bleeding_edge/src/data-flow.cc Fri Mar 12 02:20:31 2010
+++ /branches/bleeding_edge/src/data-flow.cc Fri Mar 12 02:35:45 2010
@@ -1903,13 +1903,21 @@
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();
@@ -1932,6 +1940,119 @@
// This one is generated.
rd_.gen()->Add(expr->num());
}
+
+ // Add all blocks except the entry node to the worklist.
+ 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();
+
+ BitVector temp(definition_count);
+ for (int i = 0, len = predecessors_.length(); i < len; i++) {
+ // Because ComputeRDOut always overwrites temp and its value is
+ // always read out before calling ComputeRDOut again, we do not
+ // have to clear it on each iteration of the loop.
+ 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.
+ 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);
+ // Add the successor to the worklist if not already present.
+ if (!successor_->IsMarkedWith(mark)) {
+ successor_->MarkWith(mark);
+ worklist->Insert(successor_);
+ }
}
@@ -1940,7 +2061,7 @@
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.
@@ -1972,10 +2093,25 @@
}
}
- // 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);
}
}
=======================================
--- /branches/bleeding_edge/src/data-flow.h Thu Mar 11 08:24:05 2010
+++ /branches/bleeding_edge/src/data-flow.h Fri Mar 12 02:35:45 2010
@@ -119,6 +119,13 @@
}
return true;
}
+
+ bool Equals(const BitVector& other) {
+ for (int i = 0; i < data_length_; i++) {
+ if (data_[i] != other.data_[i]) return false;
+ }
+ return true;
+ }
int length() const { return length_; }
@@ -129,7 +136,51 @@
};
-class ReachingDefinitionsData BASE_EMBEDDED {
+// Simple fixed-capacity list-based worklist (managed as a queue) of
+// pointers to T.
+template<typename T>
+class WorkList BASE_EMBEDDED {
+ public:
+ // The worklist cannot grow bigger than size. We keep one item empty to
+ // distinguish between empty and full.
+ WorkList(int size)
+ : capacity_(size + 1), head_(0), tail_(0), queue_(capacity_) {
+ for (int i = 0; i < capacity_; i++) queue_.Add(NULL);
+ }
+
+ bool is_empty() { return head_ == tail_; }
+
+ bool is_full() {
+ // The worklist is full if head is at 0 and tail is at capacity - 1:
+ // head == 0 && tail == capacity-1 ==> tail - head == capacity - 1
+ // or if tail is immediately to the left of head:
+ // tail+1 == head ==> tail - head == -1
+ int diff = tail_ - head_;
+ return (diff == -1 || diff == capacity_ - 1);
+ }
+
+ void Insert(T* item) {
+ ASSERT(!is_full());
+ queue_[tail_++] = item;
+ if (tail_ == capacity_) tail_ = 0;
+ }
+
+ T* Remove() {
+ ASSERT(!is_empty());
+ T* item = queue_[head_++];
+ if (head_ == capacity_) head_ = 0;
+ return item;
+ }
+
+ private:
+ int capacity_; // Including one empty slot.
+ int head_; // Where the first item is.
+ int tail_; // Where the next inserted item will go.
+ List<T*> queue_;
+};
+
+
+struct ReachingDefinitionsData BASE_EMBEDDED {
public:
ReachingDefinitionsData() : rd_in_(NULL), kill_(NULL), gen_(NULL) {}
@@ -179,7 +230,11 @@
// Functions used by data-flow analyses.
virtual void InitializeReachingDefinitions(int definition_count,
- List<BitVector*>* variables);
+ List<BitVector*>* variables,
+ WorkList<Node>* worklist,
+ bool mark);
+ virtual void ComputeRDOut(BitVector* result) = 0;
+ virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark) = 0;
#ifdef DEBUG
void AssignNodeNumber();
@@ -216,6 +271,9 @@
ZoneList<Node*>* preorder,
ZoneList<Node*>* postorder);
+ void ComputeRDOut(BitVector* result);
+ void UpdateRDIn(WorkList<Node>* worklist, bool mark);
+
#ifdef DEBUG
void PrintText();
#endif
@@ -261,7 +319,11 @@
ZoneList<Node*>* postorder);
void InitializeReachingDefinitions(int definition_count,
- List<BitVector*>* variables);
+ List<BitVector*>* variables,
+ WorkList<Node>* worklist,
+ bool mark);
+ void ComputeRDOut(BitVector* result);
+ void UpdateRDIn(WorkList<Node>* worklist, bool mark);
#ifdef DEBUG
void PrintText();
@@ -301,6 +363,9 @@
ZoneList<Node*>* preorder,
ZoneList<Node*>* postorder);
+ void ComputeRDOut(BitVector* result);
+ void UpdateRDIn(WorkList<Node>* worklist, bool mark);
+
#ifdef DEBUG
void PrintText();
#endif
@@ -340,6 +405,9 @@
ZoneList<Node*>* preorder,
ZoneList<Node*>* postorder);
+ void ComputeRDOut(BitVector* result);
+ void UpdateRDIn(WorkList<Node>* worklist, bool mark);
+
#ifdef DEBUG
void PrintText();
#endif
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
