deps/v8/src/compiler/control-equivalence.h

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