Initialize reaching definitions state for all flow graph nodes.

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 82 matching lines @@
     }
   }
 
   void Intersect(const BitVector& other) {
     ASSERT(other.length() == length());
     for (int i = 0; i < data_length_; i++) {
       data_[i] &= other.data_[i];
     }
   }
 
+  void Subtract(const BitVector& other) {
+    ASSERT(other.length() == length());
+    for (int i = 0; i < data_length_; i++) {
+      data_[i] &= ~other.data_[i];
+    }
+  }
+
   void Clear() {
     for (int i = 0; i < data_length_; i++) {
       data_[i] = 0;
     }
   }
 
   bool IsEmpty() const {
     for (int i = 0; i < data_length_; i++) {
       if (data_[i] != 0) return false;
     }
     return true;
   }
 
   int length() const { return length_; }
 
  private:
   int length_;
   int data_length_;
   uint32_t* data_;
 };
 
 
+class 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_; }
+  BitVector* kill() { return kill_; }
+  BitVector* gen() { return gen_; }
+
+ private:
+  BitVector* rd_in_;
+  BitVector* kill_;
+  BitVector* gen_;
+};
+
+
 // Flow-graph nodes.
 class Node: public ZoneObject {
  public:
   Node() : number_(-1), mark_(false) {}
 
   virtual ~Node() {}
 
   virtual bool IsExitNode() { return false; }
   virtual bool IsBlockNode() { return false; }
   virtual bool IsBranchNode() { return false; }
   virtual bool IsJoinNode() { return false; }
 
   virtual void AddPredecessor(Node* predecessor) = 0;
   virtual void AddSuccessor(Node* successor) = 0;
 
   bool IsMarkedWith(bool mark) { return mark_ == mark; }
   void MarkWith(bool mark) { mark_ = mark; }
 
   // Perform a depth first search and record preorder and postorder
   // 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);
+
 #ifdef DEBUG
-  virtual void AssignNumbers();
+  void AssignNodeNumber();
+  void PrintReachingDefinitions();
   virtual void PrintText() = 0;
 #endif
 
+ protected:
+  ReachingDefinitionsData rd_;
+
  private:
   int number_;
   bool mark_;
 
   DISALLOW_COPY_AND_ASSIGN(Node);
 };
 
 
 // An exit node has a arbitrarily many predecessors and no successors.
 class ExitNode: public Node {
@@ skipping 50 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);
+
 #ifdef DEBUG
-  void AssignNumbers();
   void PrintText();
 #endif
 
  private:
   Node* predecessor_;
   Node* successor_;
   ZoneList<AstNode*> instructions_;
 
   DISALLOW_COPY_AND_ASSIGN(BlockNode);
 };
@@ skipping 138 matching lines @@
       : graph_(FlowGraph::Empty()),
         global_exit_(NULL),
         preorder_(4),
         postorder_(4),
         definitions_(4) {
   }
 
   void Build(FunctionLiteral* lit);
 
   FlowGraph* graph() { return &graph_; }
-
   ZoneList<Node*>* postorder() { return &postorder_; }
+  ZoneList<Expression*>* definitions() { return &definitions_; }
 
  private:
   ExitNode* global_exit() { return global_exit_; }
 
   // AST node visit functions.
 #define DECLARE_VISIT(type) virtual void Visit##type(type* node);
   AST_NODE_LIST(DECLARE_VISIT)
 #undef DECLARE_VISIT
 
   FlowGraph graph_;
   ExitNode* global_exit_;
   ZoneList<Node*> preorder_;
   ZoneList<Node*> postorder_;
 
   // The flow graph builder collects a list of definitions (assignments and
   // count operations) to stack-allocated variables to use for reaching
-  // definitions analysis.
-  ZoneList<AstNode*> definitions_;
+  // definitions analysis.  AST node numbers in the AST are used to refer
+  // into this list.
+  ZoneList<Expression*> definitions_;
 
   DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder);
 };
 
 
 // This class is used to number all expressions in the AST according to
 // their evaluation order (post-order left-to-right traversal).
 class AstLabeler: public AstVisitor {
  public:
   AstLabeler() : next_number_(0) {}
@@ skipping 97 matching lines @@
 #undef DECLARE_VISIT
 
   FunctionLiteral* fun_;
 
   // Accumulator for assigned variables set.
   BitVector av_;
 
   DISALLOW_COPY_AND_ASSIGN(AssignedVariablesAnalyzer);
 };
 
+
+class ReachingDefinitions BASE_EMBEDDED {
+ public:
+  ReachingDefinitions(ZoneList<Node*>* postorder,
+                      ZoneList<Expression*>* definitions,
+                      int variable_count)
+      : postorder_(postorder),
+        definitions_(definitions),
+        variables_(variable_count) {
+    int definition_count = definitions->length();
+    for (int i = 0; i < variable_count; i++) {
+      variables_.Add(new BitVector(definition_count));
+    }
+  }
+
+  static int IndexFor(Variable* var, int variable_count);
+
+  void Compute();
+
+ private:
+  // A (postorder) list of flow-graph nodes in the body.
+  ZoneList<Node*>* postorder_;
+
+  // A list of all the definitions in the body.
+  ZoneList<Expression*>* definitions_;
+
+  // For each variable, the set of all its definitions.
+  List<BitVector*> variables_;
+
+  DISALLOW_COPY_AND_ASSIGN(ReachingDefinitions);
+};
+
+
 } }  // namespace v8::internal
 
 
 #endif  // V8_DATAFLOW_H_