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/compiler/graph.h" 10 #include "src/compiler/node.h" 11 #include "src/globals.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 typedef enum { kInputDirection, kUseDirection } DFSDirection; 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 typedef ZoneLinkedList<Bracket> BracketList; 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 typedef ZoneStack<DFSStackEntry> DFSStack; 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 typedef ZoneVector<NodeData*> Data; 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