Compute reaching definitions.

src/data-flow.h

 // 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 102 matching lines @@
     }
   }
 
   bool IsEmpty() const {
     for (int i = 0; i < data_length_; i++) {
       if (data_[i] != 0) return false;
     }
     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_; }
 
  private:
   int length_;
   int data_length_;
   uint32_t* data_;
 };
 
 
-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) {}
 
   void Initialize(int definition_count) {
     rd_in_ = new BitVector(definition_count);
     kill_ = new BitVector(definition_count);
     gen_ = new BitVector(definition_count);
   }
 
   BitVector* rd_in() { return rd_in_; }
@@ skipping 29 matching lines @@
   // traversal orders.
   virtual void Traverse(bool mark,
                         ZoneList<Node*>* preorder,
                         ZoneList<Node*>* postorder) = 0;
 
   int number() { return number_; }
   void set_number(int number) { number_ = number; }
 
   // 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();
   void PrintReachingDefinitions();
   virtual void PrintText() = 0;
 #endif
 
  protected:
   ReachingDefinitionsData rd_;
 
@@ skipping 16 matching lines @@
     ASSERT(predecessor != NULL);
     predecessors_.Add(predecessor);
   }
 
   void AddSuccessor(Node* successor) { UNREACHABLE(); }
 
   void Traverse(bool mark,
                 ZoneList<Node*>* preorder,
                 ZoneList<Node*>* postorder);
 
+  void ComputeRDOut(BitVector* result);
+  void UpdateRDIn(WorkList<Node>* worklist, bool mark);
+
 #ifdef DEBUG
   void PrintText();
 #endif
 
  private:
   ZoneList<Node*> predecessors_;
 
   DISALLOW_COPY_AND_ASSIGN(ExitNode);
 };
 
@@ skipping 25 matching lines @@
 
   void AddInstruction(AstNode* instruction) {
     instructions_.Add(instruction);
   }
 
   void Traverse(bool mark,
                 ZoneList<Node*>* preorder,
                 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();
 #endif
 
  private:
   Node* predecessor_;
   Node* successor_;
   ZoneList<AstNode*> instructions_;
 
@@ skipping 19 matching lines @@
       successor0_ = successor;
     } else {
       successor1_ = successor;
     }
   }
 
   void Traverse(bool mark,
                 ZoneList<Node*>* preorder,
                 ZoneList<Node*>* postorder);
 
+  void ComputeRDOut(BitVector* result);
+  void UpdateRDIn(WorkList<Node>* worklist, bool mark);
+
 #ifdef DEBUG
   void PrintText();
 #endif
 
  private:
   Node* predecessor_;
   Node* successor0_;
   Node* successor1_;
 
   DISALLOW_COPY_AND_ASSIGN(BranchNode);
@@ skipping 19 matching lines @@
 
   void AddSuccessor(Node* successor) {
     ASSERT(successor_ == NULL && successor != NULL);
     successor_ = successor;
   }
 
   void Traverse(bool mark,
                 ZoneList<Node*>* preorder,
                 ZoneList<Node*>* postorder);
 
+  void ComputeRDOut(BitVector* result);
+  void UpdateRDIn(WorkList<Node>* worklist, bool mark);
+
 #ifdef DEBUG
   void PrintText();
 #endif
 
  private:
   ZoneList<Node*> predecessors_;
   Node* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(JoinNode);
 };
@@ skipping 237 matching lines @@
   List<BitVector*> variables_;
 
   DISALLOW_COPY_AND_ASSIGN(ReachingDefinitions);
 };
 
 
 } }  // namespace v8::internal
 
 
 #endif  // V8_DATAFLOW_H_