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