text: // Copyright 2014 the V8 project authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  
  #ifndef V8_COMPILER_CONTROL_EQUIVALENCE_H_
  #define V8_COMPILER_CONTROL_EQUIVALENCE_H_
  
  #include "src/base/compiler-specific.h"
  #include "src/compiler/graph.h"
  #include "src/compiler/node.h"
  #include "src/globals.h"
  #include "src/zone/zone-containers.h"
  
  namespace v8 {
  namespace internal {
  namespace compiler {
  
  // Determines control dependence equivalence classes for control nodes. Any two
  // nodes having the same set of control dependences land in one class. These
  // classes can in turn be used to:
  //  - Build a program structure tree (PST) for controls in the graph.
  //  - Determine single-entry single-exit (SESE) regions within the graph.
  //
  // Note that this implementation actually uses cycle equivalence to establish
  // class numbers. Any two nodes are cycle equivalent if they occur in the same
  // set of cycles. It can be shown that control dependence equivalence reduces
  // to undirected cycle equivalence for strongly connected control flow graphs.
  //
  // The algorithm is based on the paper, "The program structure tree: computing
  // control regions in linear time" by Johnson, Pearson & Pingali (PLDI94) which
  // also contains proofs for the aforementioned equivalence. References to line
  // numbers in the algorithm from figure 4 have been added [line:x].
  class V8_EXPORT_PRIVATE ControlEquivalence final
      : public NON_EXPORTED_BASE(ZoneObject) {
   public:
    ControlEquivalence(Zone* zone, Graph* graph)
        : zone_(zone),
          graph_(graph),
          dfs_number_(0),
          class_number_(1),
          node_data_(graph->NodeCount(), EmptyData(), zone) {}
  
    // Run the main algorithm starting from the {exit} control node. This causes
    // the following iterations over control edges of the graph:
    //  1) A breadth-first backwards traversal to determine the set of nodes that
    //     participate in the next step. Takes O(E) time and O(N) space.
    //  2) An undirected depth-first backwards traversal that determines class
    //     numbers for all participating nodes. Takes O(E) time and O(N) space.
    void Run(Node* exit);
  
    // Retrieves a previously computed class number.
    size_t ClassOf(Node* node) {
      DCHECK_NE(kInvalidClass, GetClass(node));
      return GetClass(node);
    }
  
   private:
    static const size_t kInvalidClass = static_cast<size_t>(-1);
    typedef enum { kInputDirection, kUseDirection } DFSDirection;
  
    struct Bracket {
      DFSDirection direction;  // Direction in which this bracket was added.
      size_t recent_class;     // Cached class when bracket was topmost.
      size_t recent_size;      // Cached set-size when bracket was topmost.
      Node* from;              // Node that this bracket originates from.
      Node* to;                // Node that this bracket points to.
    };
  
    // The set of brackets for each node during the DFS walk.
    typedef ZoneLinkedList<Bracket> BracketList;
  
    struct DFSStackEntry {
      DFSDirection direction;            // Direction currently used in DFS walk.
      Node::InputEdges::iterator input;  // Iterator used for "input" direction.
      Node::UseEdges::iterator use;      // Iterator used for "use" direction.
      Node* parent_node;                 // Parent node of entry during DFS walk.
      Node* node;                        // Node that this stack entry belongs to.
    };
  
    // The stack is used during the undirected DFS walk.
    typedef ZoneStack<DFSStackEntry> DFSStack;
  
    struct NodeData {
      size_t class_number;  // Equivalence class number assigned to node.
      size_t dfs_number;    // Pre-order DFS number assigned to node.
      bool visited;         // Indicates node has already been visited.
      bool on_stack;        // Indicates node is on DFS stack during walk.
      bool participates;    // Indicates node participates in DFS walk.
      BracketList blist;    // List of brackets per node.
    };
  
    // The per-node data computed during the DFS walk.
    typedef ZoneVector<NodeData> Data;
  
    // Called at pre-visit during DFS walk.
    void VisitPre(Node* node);
  
    // Called at mid-visit during DFS walk.
    void VisitMid(Node* node, DFSDirection direction);
  
    // Called at post-visit during DFS walk.
    void VisitPost(Node* node, Node* parent_node, DFSDirection direction);
  
    // Called when hitting a back edge in the DFS walk.
    void VisitBackedge(Node* from, Node* to, DFSDirection direction);
  
    // Performs and undirected DFS walk of the graph. Conceptually all nodes are
    // expanded, splitting "input" and "use" out into separate nodes. During the
    // traversal, edges towards the representative nodes are preferred.
    //
    //   \ /        - Pre-visit: When N1 is visited in direction D the preferred
    //    x   N1      edge towards N is taken next, calling VisitPre(N).
    //    |         - Mid-visit: After all edges out of N2 in direction D have
    //    |   N       been visited, we switch the direction and start considering
    //    |           edges out of N1 now, and we call VisitMid(N).
    //    x   N2    - Post-visit: After all edges out of N1 in direction opposite
    //   / \          to D have been visited, we pop N and call VisitPost(N).
    //
    // This will yield a true spanning tree (without cross or forward edges) and
    // also discover proper back edges in both directions.
    void RunUndirectedDFS(Node* exit);
  
    void DetermineParticipationEnqueue(ZoneQueue<Node*>& queue, Node* node);
    void DetermineParticipation(Node* exit);
  
   private:
    NodeData* GetData(Node* node) {
      size_t const index = node->id();
      if (index >= node_data_.size()) node_data_.resize(index + 1, EmptyData());
      return &node_data_[index];
    }
    int NewClassNumber() { return class_number_++; }
    int NewDFSNumber() { return dfs_number_++; }
  
    // Template used to initialize per-node data.
    NodeData EmptyData() {
      return {kInvalidClass, 0, false, false, false, BracketList(zone_)};
    }
  
    // Accessors for the DFS number stored within the per-node data.
    size_t GetNumber(Node* node) { return GetData(node)->dfs_number; }
    void SetNumber(Node* node, size_t number) {
      GetData(node)->dfs_number = number;
    }
  
    // Accessors for the equivalence class stored within the per-node data.
    size_t GetClass(Node* node) { return GetData(node)->class_number; }
    void SetClass(Node* node, size_t number) {
      GetData(node)->class_number = number;
    }
  
    // Accessors for the bracket list stored within the per-node data.
    BracketList& GetBracketList(Node* node) { return GetData(node)->blist; }
    void SetBracketList(Node* node, BracketList& list) {
      GetData(node)->blist = list;
    }
  
    // Mutates the DFS stack by pushing an entry.
    void DFSPush(DFSStack& stack, Node* node, Node* from, DFSDirection dir);
  
    // Mutates the DFS stack by popping an entry.
    void DFSPop(DFSStack& stack, Node* node);
  
    void BracketListDelete(BracketList& blist, Node* to, DFSDirection direction);
    void BracketListTRACE(BracketList& blist);
  
    Zone* const zone_;
    Graph* const graph_;
    int dfs_number_;    // Generates new DFS pre-order numbers on demand.
    int class_number_;  // Generates new equivalence class numbers on demand.
    Data node_data_;    // Per-node data stored as a side-table.
  };
  
  }  // namespace compiler
  }  // namespace internal
  }  // namespace v8
  
  #endif  // V8_COMPILER_CONTROL_EQUIVALENCE_H_
  