1 // Copyright 2014 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef V8_COMPILER_CONTROL_EQUIVALENCE_H_
6 #define V8_COMPILER_CONTROL_EQUIVALENCE_H_
7 
8 #include "src/base/compiler-specific.h"
9 #include "src/common/globals.h"
10 #include "src/compiler/graph.h"
11 #include "src/compiler/node.h"
12 #include "src/zone/zone-containers.h"
13 
14 namespace v8 {
15 namespace internal {
16 namespace compiler {
17 
18 // Determines control dependence equivalence classes for control nodes. Any two
19 // nodes having the same set of control dependences land in one class. These
20 // classes can in turn be used to:
21 //  - Build a program structure tree (PST) for controls in the graph.
22 //  - Determine single-entry single-exit (SESE) regions within the graph.
23 //
24 // Note that this implementation actually uses cycle equivalence to establish
25 // class numbers. Any two nodes are cycle equivalent if they occur in the same
26 // set of cycles. It can be shown that control dependence equivalence reduces
27 // to undirected cycle equivalence for strongly connected control flow graphs.
28 //
29 // The algorithm is based on the paper, "The program structure tree: computing
30 // control regions in linear time" by Johnson, Pearson & Pingali (PLDI94) which
31 // also contains proofs for the aforementioned equivalence. References to line
32 // numbers in the algorithm from figure 4 have been added [line:x].
33 class V8_EXPORT_PRIVATE ControlEquivalence final
NON_EXPORTED_BASE(ZoneObject)34     : public NON_EXPORTED_BASE(ZoneObject) {
35  public:
36   ControlEquivalence(Zone* zone, Graph* graph)
37       : zone_(zone),
38         graph_(graph),
39         dfs_number_(0),
40         class_number_(1),
41         node_data_(graph->NodeCount(), zone) {}
42 
43   // Run the main algorithm starting from the {exit} control node. This causes
44   // the following iterations over control edges of the graph:
45   //  1) A breadth-first backwards traversal to determine the set of nodes that
46   //     participate in the next step. Takes O(E) time and O(N) space.
47   //  2) An undirected depth-first backwards traversal that determines class
48   //     numbers for all participating nodes. Takes O(E) time and O(N) space.
49   void Run(Node* exit);
50 
51   // Retrieves a previously computed class number.
52   size_t ClassOf(Node* node) {
53     DCHECK_NE(kInvalidClass, GetClass(node));
54     return GetClass(node);
55   }
56 
57  private:
58   static const size_t kInvalidClass = static_cast<size_t>(-1);
59   enum DFSDirection { kInputDirection, kUseDirection };
60 
61   struct Bracket {
62     DFSDirection direction;  // Direction in which this bracket was added.
63     size_t recent_class;     // Cached class when bracket was topmost.
64     size_t recent_size;      // Cached set-size when bracket was topmost.
65     Node* from;              // Node that this bracket originates from.
66     Node* to;                // Node that this bracket points to.
67   };
68 
69   // The set of brackets for each node during the DFS walk.
70   using BracketList = ZoneLinkedList<Bracket>;
71 
72   struct DFSStackEntry {
73     DFSDirection direction;            // Direction currently used in DFS walk.
74     Node::InputEdges::iterator input;  // Iterator used for "input" direction.
75     Node::UseEdges::iterator use;      // Iterator used for "use" direction.
76     Node* parent_node;                 // Parent node of entry during DFS walk.
77     Node* node;                        // Node that this stack entry belongs to.
78   };
79 
80   // The stack is used during the undirected DFS walk.
81   using DFSStack = ZoneStack<DFSStackEntry>;
82 
83   struct NodeData : ZoneObject {
84     explicit NodeData(Zone* zone)
85         : class_number(kInvalidClass),
86           blist(BracketList(zone)),
87           visited(false),
88           on_stack(false) {}
89 
90     size_t class_number;  // Equivalence class number assigned to node.
91     BracketList blist;    // List of brackets per node.
92     bool visited : 1;     // Indicates node has already been visited.
93     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   // Performs and undirected DFS walk of the graph. Conceptually all nodes are
112   // expanded, splitting "input" and "use" out into separate nodes. During the
113   // traversal, edges towards the representative nodes are preferred.
114   //
115   //   \ /        - Pre-visit: When N1 is visited in direction D the preferred
116   //    x   N1      edge towards N is taken next, calling VisitPre(N).
117   //    |         - Mid-visit: After all edges out of N2 in direction D have
118   //    |   N       been visited, we switch the direction and start considering
119   //    |           edges out of N1 now, and we call VisitMid(N).
120   //    x   N2    - Post-visit: After all edges out of N1 in direction opposite
121   //   / \          to D have been visited, we pop N and call VisitPost(N).
122   //
123   // This will yield a true spanning tree (without cross or forward edges) and
124   // also discover proper back edges in both directions.
125   void RunUndirectedDFS(Node* exit);
126 
127   void DetermineParticipationEnqueue(ZoneQueue<Node*>& queue, Node* node);
128   void DetermineParticipation(Node* exit);
129 
130  private:
131   NodeData* GetData(Node* node) {
132     size_t const index = node->id();
133     if (index >= node_data_.size()) node_data_.resize(index + 1);
134     return node_data_[index];
135   }
136   void AllocateData(Node* node) {
137     size_t const index = node->id();
138     if (index >= node_data_.size()) node_data_.resize(index + 1);
139     node_data_[index] = new (zone_) NodeData(zone_);
140   }
141 
142   int NewClassNumber() { return class_number_++; }
143   int NewDFSNumber() { return dfs_number_++; }
144 
145   bool Participates(Node* node) { return GetData(node) != nullptr; }
146 
147   // Accessors for the equivalence class stored within the per-node data.
148   size_t GetClass(Node* node) { return GetData(node)->class_number; }
149   void SetClass(Node* node, size_t number) {
150     DCHECK(Participates(node));
151     GetData(node)->class_number = number;
152   }
153 
154   // Accessors for the bracket list stored within the per-node data.
155   BracketList& GetBracketList(Node* node) {
156     DCHECK(Participates(node));
157     return GetData(node)->blist;
158   }
159   void SetBracketList(Node* node, BracketList& list) {
160     DCHECK(Participates(node));
161     GetData(node)->blist = list;
162   }
163 
164   // 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   void BracketListDelete(BracketList& blist, Node* to, DFSDirection direction);
171   void BracketListTRACE(BracketList& blist);
172 
173   Zone* const zone_;
174   Graph* const graph_;
175   int dfs_number_;    // Generates new DFS pre-order numbers on demand.
176   int class_number_;  // Generates new equivalence class numbers on demand.
177   Data node_data_;    // Per-node data stored as a side-table.
178 };
179 
180 }  // namespace compiler
181 }  // namespace internal
182 }  // namespace v8
183 
184 #endif  // V8_COMPILER_CONTROL_EQUIVALENCE_H_
185