control-equivalence.h 7.22 KB
Newer Older
1 2 3 4 5 6 7
// 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_

8
#include "src/base/compiler-specific.h"
9 10
#include "src/compiler/graph.h"
#include "src/compiler/node.h"
11
#include "src/globals.h"
12
#include "src/zone/zone-containers.h"
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

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].
33 34
class V8_EXPORT_PRIVATE ControlEquivalence final
    : public NON_EXPORTED_BASE(ZoneObject) {
35 36 37 38 39 40
 public:
  ControlEquivalence(Zone* zone, Graph* graph)
      : zone_(zone),
        graph_(graph),
        dfs_number_(0),
        class_number_(1),
41
        node_data_(graph->NodeCount(), zone) {}
42 43 44 45 46 47 48

  // 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.
49
  void Run(Node* exit);
50 51 52

  // Retrieves a previously computed class number.
  size_t ClassOf(Node* node) {
53
    DCHECK_NE(kInvalidClass, GetClass(node));
54 55 56 57 58
    return GetClass(node);
  }

 private:
  static const size_t kInvalidClass = static_cast<size_t>(-1);
59
  enum DFSDirection { kInputDirection, kUseDirection };
60 61 62 63 64 65 66 67 68 69

  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.
70
  using BracketList = ZoneLinkedList<Bracket>;
71 72 73 74 75 76 77 78 79 80

  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.
81
  using DFSStack = ZoneStack<DFSStackEntry>;
82

83 84 85 86 87 88 89
  struct NodeData : ZoneObject {
    explicit NodeData(Zone* zone)
        : class_number(kInvalidClass),
          blist(BracketList(zone)),
          visited(false),
          on_stack(false) {}

90 91
    size_t class_number;  // Equivalence class number assigned to node.
    BracketList blist;    // List of brackets per node.
92 93
    bool visited : 1;     // Indicates node has already been visited.
    bool on_stack : 1;    // Indicates node is on DFS stack during walk.
94 95 96
  };

  // The per-node data computed during the DFS walk.
97
  using Data = ZoneVector<NodeData*>;
98 99

  // Called at pre-visit during DFS walk.
100
  void VisitPre(Node* node);
101 102

  // Called at mid-visit during DFS walk.
103
  void VisitMid(Node* node, DFSDirection direction);
104 105

  // Called at post-visit during DFS walk.
106
  void VisitPost(Node* node, Node* parent_node, DFSDirection direction);
107 108

  // Called when hitting a back edge in the DFS walk.
109
  void VisitBackedge(Node* from, Node* to, DFSDirection direction);
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124

  // 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.
125
  void RunUndirectedDFS(Node* exit);
126

127 128
  void DetermineParticipationEnqueue(ZoneQueue<Node*>& queue, Node* node);
  void DetermineParticipation(Node* exit);
129 130

 private:
131 132
  NodeData* GetData(Node* node) {
    size_t const index = node->id();
133 134 135 136 137 138 139
    if (index >= node_data_.size()) node_data_.resize(index + 1);
    return node_data_[index];
  }
  void AllocateData(Node* node) {
    size_t const index = node->id();
    if (index >= node_data_.size()) node_data_.resize(index + 1);
    node_data_[index] = new (zone_) NodeData(zone_);
140
  }
141

142 143 144
  int NewClassNumber() { return class_number_++; }
  int NewDFSNumber() { return dfs_number_++; }

145
  bool Participates(Node* node) { return GetData(node) != nullptr; }
146 147 148 149

  // 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) {
150
    DCHECK(Participates(node));
151 152 153 154
    GetData(node)->class_number = number;
  }

  // Accessors for the bracket list stored within the per-node data.
155 156 157 158
  BracketList& GetBracketList(Node* node) {
    DCHECK(Participates(node));
    return GetData(node)->blist;
  }
159
  void SetBracketList(Node* node, BracketList& list) {
160
    DCHECK(Participates(node));
161 162 163 164
    GetData(node)->blist = list;
  }

  // Mutates the DFS stack by pushing an entry.
165
  void DFSPush(DFSStack& stack, Node* node, Node* from, DFSDirection dir);
166 167

  // Mutates the DFS stack by popping an entry.
168
  void DFSPop(DFSStack& stack, Node* node);
169

170 171
  void BracketListDelete(BracketList& blist, Node* to, DFSDirection direction);
  void BracketListTRACE(BracketList& blist);
172

173 174
  Zone* const zone_;
  Graph* const graph_;
175 176 177 178 179 180 181 182 183 184
  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_