Initial support for marking live code.

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 223 matching lines @@
 
   // Functions used by data-flow analyses.
   virtual void InitializeReachingDefinitions(int definition_count,
                                              List<BitVector*>* variables,
                                              WorkList<Node>* worklist,
                                              bool mark);
   virtual void ComputeRDOut(BitVector* result) = 0;
   virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark) = 0;
   virtual void PropagateReachingDefinitions(List<BitVector*>* variables);
 
+  // Functions used by dead-code elimination.
+  virtual void MarkCriticalInstructions(
+      List<AstNode*>* stack,
+      ZoneList<Expression*>* body_definitions,
+      int variable_count);
+
 #ifdef DEBUG
   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 {
  public:
   ExitNode() : predecessors_(4) {}
 
-  bool IsExitNode() { return true; }
+  virtual bool IsExitNode() { return true; }
 
-  void AddPredecessor(Node* predecessor) {
+  virtual void AddPredecessor(Node* predecessor) {
     ASSERT(predecessor != NULL);
     predecessors_.Add(predecessor);
   }
 
-  void AddSuccessor(Node* successor) { UNREACHABLE(); }
+  virtual void AddSuccessor(Node* successor) { UNREACHABLE(); }
 
-  void Traverse(bool mark,
-                ZoneList<Node*>* preorder,
-                ZoneList<Node*>* postorder);
+  virtual void Traverse(bool mark,
+                        ZoneList<Node*>* preorder,
+                        ZoneList<Node*>* postorder);
 
-  void ComputeRDOut(BitVector* result);
-  void UpdateRDIn(WorkList<Node>* worklist, bool mark);
+  virtual void ComputeRDOut(BitVector* result);
+  virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark);
 
 #ifdef DEBUG
-  void PrintText();
+  virtual void PrintText();
 #endif
 
  private:
   ZoneList<Node*> predecessors_;
 
   DISALLOW_COPY_AND_ASSIGN(ExitNode);
 };
 
 
 // Block nodes have a single successor and predecessor and a list of
 // instructions.
 class BlockNode: public Node {
  public:
   BlockNode() : predecessor_(NULL), successor_(NULL), instructions_(4) {}
 
   static BlockNode* cast(Node* node) {
     ASSERT(node->IsBlockNode());
     return reinterpret_cast<BlockNode*>(node);
   }
 
-  bool IsBlockNode() { return true; }
+  virtual bool IsBlockNode() { return true; }
 
   bool is_empty() { return instructions_.is_empty(); }
 
   ZoneList<AstNode*>* instructions() { return &instructions_; }
 
-  void AddPredecessor(Node* predecessor) {
+  virtual void AddPredecessor(Node* predecessor) {
     ASSERT(predecessor_ == NULL && predecessor != NULL);
     predecessor_ = predecessor;
   }
 
-  void AddSuccessor(Node* successor) {
+  virtual void AddSuccessor(Node* successor) {
     ASSERT(successor_ == NULL && successor != NULL);
     successor_ = successor;
   }
 
   void AddInstruction(AstNode* instruction) {
     instructions_.Add(instruction);
   }
 
-  void Traverse(bool mark,
-                ZoneList<Node*>* preorder,
-                ZoneList<Node*>* postorder);
+  virtual void Traverse(bool mark,
+                        ZoneList<Node*>* preorder,
+                        ZoneList<Node*>* postorder);
 
-  void InitializeReachingDefinitions(int definition_count,
-                                     List<BitVector*>* variables,
-                                     WorkList<Node>* worklist,
-                                     bool mark);
-  void ComputeRDOut(BitVector* result);
-  void UpdateRDIn(WorkList<Node>* worklist, bool mark);
-  void PropagateReachingDefinitions(List<BitVector*>* variables);
+  virtual void InitializeReachingDefinitions(int definition_count,
+                                             List<BitVector*>* variables,
+                                             WorkList<Node>* worklist,
+                                             bool mark);
+  virtual void ComputeRDOut(BitVector* result);
+  virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark);
+  virtual void PropagateReachingDefinitions(List<BitVector*>* variables);
+
+  virtual void MarkCriticalInstructions(
+      List<AstNode*>* stack,
+      ZoneList<Expression*>* body_definitions,
+      int variable_count);
 
 #ifdef DEBUG
-  void PrintText();
+  virtual void PrintText();
 #endif
 
  private:
   Node* predecessor_;
   Node* successor_;
   ZoneList<AstNode*> instructions_;
 
   DISALLOW_COPY_AND_ASSIGN(BlockNode);
 };
 
 
 // Branch nodes have a single predecessor and a pair of successors.
 class BranchNode: public Node {
  public:
   BranchNode() : predecessor_(NULL), successor0_(NULL), successor1_(NULL) {}
 
-  bool IsBranchNode() { return true; }
+  virtual bool IsBranchNode() { return true; }
 
-  void AddPredecessor(Node* predecessor) {
+  virtual void AddPredecessor(Node* predecessor) {
     ASSERT(predecessor_ == NULL && predecessor != NULL);
     predecessor_ = predecessor;
   }
 
-  void AddSuccessor(Node* successor) {
+  virtual void AddSuccessor(Node* successor) {
     ASSERT(successor1_ == NULL && successor != NULL);
     if (successor0_ == NULL) {
       successor0_ = successor;
     } else {
       successor1_ = successor;
     }
   }
 
-  void Traverse(bool mark,
-                ZoneList<Node*>* preorder,
-                ZoneList<Node*>* postorder);
+  virtual void Traverse(bool mark,
+                        ZoneList<Node*>* preorder,
+                        ZoneList<Node*>* postorder);
 
-  void ComputeRDOut(BitVector* result);
-  void UpdateRDIn(WorkList<Node>* worklist, bool mark);
+  virtual void ComputeRDOut(BitVector* result);
+  virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark);
 
 #ifdef DEBUG
-  void PrintText();
+  virtual void PrintText();
 #endif
 
  private:
   Node* predecessor_;
   Node* successor0_;
   Node* successor1_;
 
   DISALLOW_COPY_AND_ASSIGN(BranchNode);
 };
 
 
 // Join nodes have arbitrarily many predecessors and a single successor.
 class JoinNode: public Node {
  public:
   JoinNode() : predecessors_(2), successor_(NULL) {}
 
   static JoinNode* cast(Node* node) {
     ASSERT(node->IsJoinNode());
     return reinterpret_cast<JoinNode*>(node);
   }
 
-  bool IsJoinNode() { return true; }
+  virtual bool IsJoinNode() { return true; }
 
-  void AddPredecessor(Node* predecessor) {
+  virtual void AddPredecessor(Node* predecessor) {
     ASSERT(predecessor != NULL);
     predecessors_.Add(predecessor);
   }
 
-  void AddSuccessor(Node* successor) {
+  virtual void AddSuccessor(Node* successor) {
     ASSERT(successor_ == NULL && successor != NULL);
     successor_ = successor;
   }
 
-  void Traverse(bool mark,
-                ZoneList<Node*>* preorder,
-                ZoneList<Node*>* postorder);
+  virtual void Traverse(bool mark,
+                        ZoneList<Node*>* preorder,
+                        ZoneList<Node*>* postorder);
 
-  void ComputeRDOut(BitVector* result);
-  void UpdateRDIn(WorkList<Node>* worklist, bool mark);
+  virtual void ComputeRDOut(BitVector* result);
+  virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark);
 
 #ifdef DEBUG
-  void PrintText();
+  virtual void PrintText();
 #endif
 
  private:
   ZoneList<Node*> predecessors_;
   Node* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(JoinNode);
 };
 
 
@@ skipping 61 matching lines @@
         global_exit_(NULL),
         preorder_(4),
         postorder_(4),
         variable_count_(variable_count),
         body_definitions_(4) {
   }
 
   void Build(FunctionLiteral* lit);
 
   FlowGraph* graph() { return &graph_; }
+  ZoneList<Node*>* preorder() { return &preorder_; }
   ZoneList<Node*>* postorder() { return &postorder_; }
   ZoneList<Expression*>* body_definitions() { return &body_definitions_; }
 
  private:
   ExitNode* global_exit() { return global_exit_; }
 
   // Helpers to allow tranforming the ast during flow graph construction.
   void VisitStatements(ZoneList<Statement*>* stmts);
   Statement* ProcessStatement(Statement* stmt);
 
@@ skipping 103 matching lines @@
 
   // A list of all the definitions in the body.
   ZoneList<Expression*>* body_definitions_;
 
   int variable_count_;
 
   DISALLOW_COPY_AND_ASSIGN(ReachingDefinitions);
 };
 
 
-
 class TypeAnalyzer BASE_EMBEDDED {
  public:
   TypeAnalyzer(ZoneList<Node*>* postorder,
               ZoneList<Expression*>* body_definitions,
                int variable_count,
                int param_count)
       : postorder_(postorder),
         body_definitions_(body_definitions),
         variable_count_(variable_count),
         param_count_(param_count) {}
 
   void Compute();
 
  private:
   // Get the primitity of definition number i. Definitions are numbered
   // by the flow graph builder.
   bool IsPrimitiveDef(int def_num);
 
   ZoneList<Node*>* postorder_;
   ZoneList<Expression*>* body_definitions_;
   int variable_count_;
   int param_count_;
+
+  DISALLOW_COPY_AND_ASSIGN(TypeAnalyzer);
 };
 
+
+void MarkLiveCode(ZoneList<Node*>* nodes,
+                  ZoneList<Expression*>* body_definitions,
+                  int variable_count);
+
+
 } }  // namespace v8::internal
 
 
 #endif  // V8_DATAFLOW_H_