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