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 | |
| 8 | #include "src/v8.h" |
| 9 | |
| 10 | #include "src/compiler/graph.h" |
| 11 | #include "src/compiler/node.h" |
| 12 | #include "src/compiler/node-properties.h" |
| 13 | #include "src/zone-containers.h" |
| 14 | |
| 15 | namespace v8 { |
| 16 | namespace internal { |
| 17 | namespace compiler { |
| 18 | |
| 19 | // Determines control dependence equivalence classes for control nodes. Any two |
| 20 | // nodes having the same set of control dependences land in one class. These |
| 21 | // classes can in turn be used to: |
| 22 | // - Build a program structure tree (PST) for controls in the graph. |
| 23 | // - Determine single-entry single-exit (SESE) regions within the graph. |
| 24 | // |
| 25 | // Note that this implementation actually uses cycle equivalence to establish |
| 26 | // class numbers. Any two nodes are cycle equivalent if they occur in the same |
| 27 | // set of cycles. It can be shown that control dependence equivalence reduces |
| 28 | // to undirected cycle equivalence for strongly connected control flow graphs. |
| 29 | // |
| 30 | // The algorithm is based on the paper, "The program structure tree: computing |
| 31 | // control regions in linear time" by Johnson, Pearson & Pingali (PLDI94) which |
| 32 | // also contains proofs for the aforementioned equivalence. References to line |
| 33 | // numbers in the algorithm from figure 4 have been added [line:x]. |
| 34 | class ControlEquivalence : public 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(), EmptyData(), 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 | if (GetClass(exit) != kInvalidClass) return; |
| 51 | DetermineParticipation(exit); |
| 52 | RunUndirectedDFS(exit); |
| 53 | } |
| 54 | |
| 55 | // Retrieves a previously computed class number. |
| 56 | size_t ClassOf(Node* node) { |
| 57 | DCHECK(GetClass(node) != kInvalidClass); |
| 58 | return GetClass(node); |
| 59 | } |
| 60 | |
| 61 | private: |
| 62 | static const size_t kInvalidClass = static_cast<size_t>(-1); |
| 63 | typedef enum { kInputDirection, kUseDirection } DFSDirection; |
| 64 | |
| 65 | struct Bracket { |
| 66 | DFSDirection direction; // Direction in which this bracket was added. |
| 67 | size_t recent_class; // Cached class when bracket was topmost. |
| 68 | size_t recent_size; // Cached set-size when bracket was topmost. |
| 69 | Node* from; // Node that this bracket originates from. |
| 70 | Node* to; // Node that this bracket points to. |
| 71 | }; |
| 72 | |
| 73 | // The set of brackets for each node during the DFS walk. |
| 74 | typedef ZoneLinkedList<Bracket> BracketList; |
| 75 | |
| 76 | struct DFSStackEntry { |
| 77 | DFSDirection direction; // Direction currently used in DFS walk. |
| 78 | Node::InputEdges::iterator input; // Iterator used for "input" direction. |
| 79 | Node::UseEdges::iterator use; // Iterator used for "use" direction. |
| 80 | Node* parent_node; // Parent node of entry during DFS walk. |
| 81 | Node* node; // Node that this stack entry belongs to. |
| 82 | }; |
| 83 | |
| 84 | // The stack is used during the undirected DFS walk. |
| 85 | typedef ZoneStack<DFSStackEntry> DFSStack; |
| 86 | |
| 87 | struct NodeData { |
| 88 | size_t class_number; // Equivalence class number assigned to node. |
| 89 | size_t dfs_number; // Pre-order DFS number assigned to node. |
| 90 | bool visited; // Indicates node has already been visited. |
| 91 | bool on_stack; // Indicates node is on DFS stack during walk. |
| 92 | bool participates; // Indicates node participates in DFS walk. |
| 93 | BracketList blist; // List of brackets per node. |
| 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 | Trace("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic()); |
| 102 | |
| 103 | // Dispense a new pre-order number. |
| 104 | SetNumber(node, NewDFSNumber()); |
| 105 | Trace(" Assigned DFS number is %d\n", GetNumber(node)); |
| 106 | } |
| 107 | |
| 108 | // Called at mid-visit during DFS walk. |
| 109 | void VisitMid(Node* node, DFSDirection direction) { |
| 110 | Trace("CEQ: Mid-visit of #%d:%s\n", node->id(), node->op()->mnemonic()); |
| 111 | BracketList& blist = GetBracketList(node); |
| 112 | |
| 113 | // Remove brackets pointing to this node [line:19]. |
| 114 | BracketListDelete(blist, node, direction); |
| 115 | |
| 116 | // Potentially introduce artificial dependency from start to end. |
| 117 | if (blist.empty()) { |
| 118 | DCHECK_EQ(kInputDirection, direction); |
| 119 | VisitBackedge(node, graph_->end(), kInputDirection); |
| 120 | } |
| 121 | |
| 122 | // Potentially start a new equivalence class [line:37]. |
| 123 | BracketListTrace(blist); |
| 124 | Bracket* recent = &blist.back(); |
| 125 | if (recent->recent_size != blist.size()) { |
| 126 | recent->recent_size = blist.size(); |
| 127 | recent->recent_class = NewClassNumber(); |
| 128 | } |
| 129 | |
| 130 | // Assign equivalence class to node. |
| 131 | SetClass(node, recent->recent_class); |
| 132 | Trace(" Assigned class number is %d\n", GetClass(node)); |
| 133 | } |
| 134 | |
| 135 | // Called at post-visit during DFS walk. |
| 136 | void VisitPost(Node* node, Node* parent_node, DFSDirection direction) { |
| 137 | Trace("CEQ: Post-visit of #%d:%s\n", node->id(), node->op()->mnemonic()); |
| 138 | BracketList& blist = GetBracketList(node); |
| 139 | |
| 140 | // Remove brackets pointing to this node [line:19]. |
| 141 | BracketListDelete(blist, node, direction); |
| 142 | |
| 143 | // Propagate bracket list up the DFS tree [line:13]. |
| 144 | if (parent_node != NULL) { |
| 145 | BracketList& parent_blist = GetBracketList(parent_node); |
| 146 | parent_blist.splice(parent_blist.end(), blist); |
| 147 | } |
| 148 | } |
| 149 | |
| 150 | // Called when hitting a back edge in the DFS walk. |
| 151 | void VisitBackedge(Node* from, Node* to, DFSDirection direction) { |
| 152 | Trace("CEQ: Backedge from #%d:%s to #%d:%s\n", from->id(), |
| 153 | from->op()->mnemonic(), to->id(), to->op()->mnemonic()); |
| 154 | |
| 155 | // Push backedge onto the bracket list [line:25]. |
| 156 | Bracket bracket = {direction, kInvalidClass, 0, from, to}; |
| 157 | GetBracketList(from).push_back(bracket); |
| 158 | } |
| 159 | |
| 160 | // Performs and undirected DFS walk of the graph. Conceptually all nodes are |
| 161 | // expanded, splitting "input" and "use" out into separate nodes. During the |
| 162 | // traversal, edges towards the representative nodes are preferred. |
| 163 | // |
| 164 | // \ / - Pre-visit: When N1 is visited in direction D the preferred |
| 165 | // x N1 edge towards N is taken next, calling VisitPre(N). |
| 166 | // | - Mid-visit: After all edges out of N2 in direction D have |
| 167 | // | N been visited, we switch the direction and start considering |
| 168 | // | edges out of N1 now, and we call VisitMid(N). |
| 169 | // x N2 - Post-visit: After all edges out of N1 in direction opposite |
| 170 | // / \ to D have been visited, we pop N and call VisitPost(N). |
| 171 | // |
| 172 | // This will yield a true spanning tree (without cross or forward edges) and |
| 173 | // also discover proper back edges in both directions. |
| 174 | void RunUndirectedDFS(Node* exit) { |
| 175 | ZoneStack<DFSStackEntry> stack(zone_); |
| 176 | DFSPush(stack, exit, NULL, kInputDirection); |
| 177 | VisitPre(exit); |
| 178 | |
| 179 | while (!stack.empty()) { // Undirected depth-first backwards traversal. |
| 180 | DFSStackEntry& entry = stack.top(); |
| 181 | Node* node = entry.node; |
| 182 | |
| 183 | if (entry.direction == kInputDirection) { |
| 184 | if (entry.input != node->input_edges().end()) { |
| 185 | Edge edge = *entry.input; |
| 186 | Node* input = edge.to(); |
| 187 | ++(entry.input); |
| 188 | if (NodeProperties::IsControlEdge(edge) && |
| 189 | NodeProperties::IsControl(input)) { |
| 190 | // Visit next control input. |
| 191 | if (!GetData(input)->participates) continue; |
| 192 | if (GetData(input)->visited) continue; |
| 193 | if (GetData(input)->on_stack) { |
| 194 | // Found backedge if input is on stack. |
| 195 | if (input != entry.parent_node) { |
| 196 | VisitBackedge(node, input, kInputDirection); |
| 197 | } |
| 198 | } else { |
| 199 | // Push input onto stack. |
| 200 | DFSPush(stack, input, node, kInputDirection); |
| 201 | VisitPre(input); |
| 202 | } |
| 203 | } |
| 204 | continue; |
| 205 | } |
| 206 | if (entry.use != node->use_edges().end()) { |
| 207 | // Switch direction to uses. |
| 208 | entry.direction = kUseDirection; |
| 209 | VisitMid(node, kInputDirection); |
| 210 | continue; |
| 211 | } |
| 212 | } |
| 213 | |
| 214 | if (entry.direction == kUseDirection) { |
| 215 | if (entry.use != node->use_edges().end()) { |
| 216 | Edge edge = *entry.use; |
| 217 | Node* use = edge.from(); |
| 218 | ++(entry.use); |
| 219 | if (NodeProperties::IsControlEdge(edge) && |
| 220 | NodeProperties::IsControl(use)) { |
| 221 | // Visit next control use. |
| 222 | if (!GetData(use)->participates) continue; |
| 223 | if (GetData(use)->visited) continue; |
| 224 | if (GetData(use)->on_stack) { |
| 225 | // Found backedge if use is on stack. |
| 226 | if (use != entry.parent_node) { |
| 227 | VisitBackedge(node, use, kUseDirection); |
| 228 | } |
| 229 | } else { |
| 230 | // Push use onto stack. |
| 231 | DFSPush(stack, use, node, kUseDirection); |
| 232 | VisitPre(use); |
| 233 | } |
| 234 | } |
| 235 | continue; |
| 236 | } |
| 237 | if (entry.input != node->input_edges().end()) { |
| 238 | // Switch direction to inputs. |
| 239 | entry.direction = kInputDirection; |
| 240 | VisitMid(node, kUseDirection); |
| 241 | continue; |
| 242 | } |
| 243 | } |
| 244 | |
| 245 | // Pop node from stack when done with all inputs and uses. |
| 246 | DCHECK(entry.input == node->input_edges().end()); |
| 247 | DCHECK(entry.use == node->use_edges().end()); |
| 248 | DFSPop(stack, node); |
| 249 | VisitPost(node, entry.parent_node, entry.direction); |
| 250 | } |
| 251 | } |
| 252 | |
| 253 | void DetermineParticipationEnqueue(ZoneQueue<Node*>& queue, Node* node) { |
| 254 | if (!GetData(node)->participates) { |
| 255 | GetData(node)->participates = true; |
| 256 | queue.push(node); |
| 257 | } |
| 258 | } |
| 259 | |
| 260 | void DetermineParticipation(Node* exit) { |
| 261 | ZoneQueue<Node*> queue(zone_); |
| 262 | DetermineParticipationEnqueue(queue, exit); |
| 263 | while (!queue.empty()) { // Breadth-first backwards traversal. |
| 264 | Node* node = queue.front(); |
| 265 | queue.pop(); |
| 266 | int max = NodeProperties::PastControlIndex(node); |
| 267 | for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { |
| 268 | DetermineParticipationEnqueue(queue, node->InputAt(i)); |
| 269 | } |
| 270 | } |
| 271 | } |
| 272 | |
| 273 | private: |
| 274 | NodeData* GetData(Node* node) { return &node_data_[node->id()]; } |
| 275 | int NewClassNumber() { return class_number_++; } |
| 276 | int NewDFSNumber() { return dfs_number_++; } |
| 277 | |
| 278 | // Template used to initialize per-node data. |
| 279 | NodeData EmptyData() { |
| 280 | return {kInvalidClass, 0, false, false, false, BracketList(zone_)}; |
| 281 | } |
| 282 | |
| 283 | // Accessors for the DFS number stored within the per-node data. |
| 284 | size_t GetNumber(Node* node) { return GetData(node)->dfs_number; } |
| 285 | void SetNumber(Node* node, size_t number) { |
| 286 | GetData(node)->dfs_number = number; |
| 287 | } |
| 288 | |
| 289 | // Accessors for the equivalence class stored within the per-node data. |
| 290 | size_t GetClass(Node* node) { return GetData(node)->class_number; } |
| 291 | void SetClass(Node* node, size_t number) { |
| 292 | GetData(node)->class_number = number; |
| 293 | } |
| 294 | |
| 295 | // Accessors for the bracket list stored within the per-node data. |
| 296 | BracketList& GetBracketList(Node* node) { return GetData(node)->blist; } |
| 297 | void SetBracketList(Node* node, BracketList& list) { |
| 298 | GetData(node)->blist = list; |
| 299 | } |
| 300 | |
| 301 | // Mutates the DFS stack by pushing an entry. |
| 302 | void DFSPush(DFSStack& stack, Node* node, Node* from, DFSDirection dir) { |
| 303 | DCHECK(GetData(node)->participates); |
| 304 | DCHECK(!GetData(node)->visited); |
| 305 | GetData(node)->on_stack = true; |
| 306 | Node::InputEdges::iterator input = node->input_edges().begin(); |
| 307 | Node::UseEdges::iterator use = node->use_edges().begin(); |
| 308 | stack.push({dir, input, use, from, node}); |
| 309 | } |
| 310 | |
| 311 | // Mutates the DFS stack by popping an entry. |
| 312 | void DFSPop(DFSStack& stack, Node* node) { |
| 313 | DCHECK_EQ(stack.top().node, node); |
| 314 | GetData(node)->on_stack = false; |
| 315 | GetData(node)->visited = true; |
| 316 | stack.pop(); |
| 317 | } |
| 318 | |
| 319 | // TODO(mstarzinger): Optimize this to avoid linear search. |
| 320 | void BracketListDelete(BracketList& blist, Node* to, DFSDirection direction) { |
| 321 | for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) { |
| 322 | if (i->to == to && i->direction != direction) { |
| 323 | Trace(" BList erased: {%d->%d}\n", i->from->id(), i->to->id()); |
| 324 | i = blist.erase(i); |
| 325 | } else { |
| 326 | ++i; |
| 327 | } |
| 328 | } |
| 329 | } |
| 330 | |
| 331 | void BracketListTrace(BracketList& blist) { |
| 332 | if (FLAG_trace_turbo_scheduler) { |
| 333 | Trace(" BList: "); |
| 334 | for (Bracket bracket : blist) { |
| 335 | Trace("{%d->%d} ", bracket.from->id(), bracket.to->id()); |
| 336 | } |
| 337 | Trace("\n"); |
| 338 | } |
| 339 | } |
| 340 | |
| 341 | void Trace(const char* msg, ...) { |
| 342 | if (FLAG_trace_turbo_scheduler) { |
| 343 | va_list arguments; |
| 344 | va_start(arguments, msg); |
| 345 | base::OS::VPrint(msg, arguments); |
| 346 | va_end(arguments); |
| 347 | } |
| 348 | } |
| 349 | |
| 350 | Zone* zone_; |
| 351 | Graph* graph_; |
| 352 | int dfs_number_; // Generates new DFS pre-order numbers on demand. |
| 353 | int class_number_; // Generates new equivalence class numbers on demand. |
| 354 | Data node_data_; // Per-node data stored as a side-table. |
| 355 | }; |
| 356 | |
| 357 | } // namespace compiler |
| 358 | } // namespace internal |
| 359 | } // namespace v8 |
| 360 | |
| 361 | #endif // V8_COMPILER_CONTROL_EQUIVALENCE_H_ |