Restrict floating control to minimal control-connected component.

src/compiler/control-equivalence.h

+// Copyright 2014 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef V8_COMPILER_CONTROL_EQUIVALENCE_H_
+#define V8_COMPILER_CONTROL_EQUIVALENCE_H_
+
+#include "src/v8.h"
+
+#include "src/compiler/graph.h"
+#include "src/compiler/node.h"
+#include "src/compiler/node-properties.h"
+#include "src/zone-containers.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+// Determines control dependence equivalence classes for control nodes. Any two
+// nodes having the same set of control dependences land in one class. These
+// classes can in turn be used to:
+//  - Build a program structure tree (PST) for controls in the graph.
+//  - Determine single-entry single-exit (SESE) regions within the graph.
+//
+// Note that this implementation actually uses cycle equivalence to establish
+// class numbers. Any two nodes are cycle equivalent if they occur in the same
+// set of cycles. It can be shown that control dependence equivalence reduces
+// down cycle equivalence for strongly connected control flow graphs.

[Jarin, 2014/12/01 20:56:24]

Did not quite understand the last sentence, perhaps you could to say "...
reduces to undirected cycle equivalence for..."?

[Michael Starzinger, 2014/12/02 12:20:34]

Done.

+//
+// The algorithm is based on research by Johnson, Pearson & Pingali which also

[Jarin, 2014/12/01 20:56:24]

Could you give a more complete citation? (At least the name of the article.)

[Michael Starzinger, 2014/12/02 12:20:34]

Done.

+// contains proofs for the aforementioned equivalence.
+class ControlEquivalence : public ZoneObject {
+ public:
+  ControlEquivalence(Zone* zone, Graph* graph)
+      : zone_(zone),
+        graph_(graph),
+        dfs_number_(0),
+        class_number_(1),
+        node_data_(graph->NodeCount(), EmptyData(), zone) {}
+
+  // Run the main algorithm starting from the {exit} control node. This causes
+  // the following iterations over control edges of the graph:
+  //  1) A breath-first backwards traversal to determine the set of nodes that

[Jarin, 2014/12/01 20:56:24]

typo: breadth

[Michael Starzinger, 2014/12/02 12:20:34]

Done.

+  //     participate in the next step. Takes O(E) time and O(N) space.
+  //  2) An undirected depth-first backwards traversal that determines class
+  //     numbers for all participating nodes. Takes O(E) time and O(N) space.
+  void Run(Node* exit) {
+    if (GetClass(exit) != kInvalidClass) return;
+    DetermineParticipation(exit);
+    RunUndirectedDFS(exit);
+  }
+
+  // Retrieves a previously computed class number.
+  size_t ClassOf(Node* node) {
+    DCHECK(GetClass(node) != kInvalidClass);
+    return GetClass(node);
+  }
+
+ private:
+  static const size_t kInvalidClass = static_cast<size_t>(-1);
+  typedef enum { kInputDirection, kUseDirection } DFSDirection;
+
+  struct Bracket {
+    DFSDirection direction;  // Direction in which this bracket was added.
+    size_t recent_class;     // Cached class when bracket was topmost.
+    size_t recent_size;      // Cached set-size when bracket was topmost.
+    Node* from;              // Node that this bracket originates from.
+    Node* to;                // Node that this bracket points to.
+  };
+
+  // The set of brackets for each node during the DFS walk.
+  typedef ZoneLinkedList<Bracket> BracketList;
+
+  struct DFSStackEntry {
+    DFSDirection direction;        // Direction currently used in DFS walk.
+    Node::Inputs::iterator input;  // Iterator used for the "input" direction.
+    Node::Uses::iterator use;      // Iterator used for the "use" direction.
+    Node* parent_node;             // Parent node of entry during DFS walk.
+    Node* node;                    // Node that this stack entry belongs to.
+  };
+
+  // The stack is used during the undirected DFS walk.
+  typedef ZoneStack<DFSStackEntry> DFSStack;
+
+  struct NodeData {
+    size_t class_number;  // Equivalence class number assigned to node.
+    size_t dfs_number;    // Pre-order DFS number assigned to node.
+    bool on_stack;        // Indicates node is on DFS stack during walk.
+    bool participates;    // Indicates node participates in DFS walk.
+    BracketList blist;    // List of brackets per node.
+  };
+
+  // The per-node data computed during the DFS walk.
+  typedef ZoneVector<NodeData> Data;
+
+  void VisitPre(Node* node) {
+    Trace("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
+
+    // Dispense a new pre-order number.
+    SetNumber(node, NewDFSNumber());
+    Trace("  Assigned DFS number is %d\n", GetNumber(node));
+  }
+
+  void VisitMid(Node* node, DFSDirection direction) {
+    Trace("CEQ: Mid-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
+    BracketList& blist = GetBracketList(node);
+
+    // Remove brackets pointing to this node.
+    BracketListDelete(blist, node, direction);
+
+    // Potentially introduce artificial dependency from start to end.
+    if (blist.empty()) {
+      DCHECK_EQ(graph_->start(), node);
+      DCHECK_EQ(kInputDirection, direction);
+      VisitBackedge(graph_->start(), graph_->end(), kInputDirection);
+    }
+
+    // Potentially start a new equivalence class.
+    BracketListTrace(blist);
+    Bracket* recent = &blist.back();
+    if (recent->recent_size != blist.size()) {
+      recent->recent_size = blist.size();
+      recent->recent_class = NewClassNumber();
+    }
+
+    // Assign equivalence class to node.
+    SetClass(node, recent->recent_class);

[Jarin, 2014/12/01 20:56:24]

I am quite confused here when trying to match the algorithm to the one described
in the paper. Could you make the connection more explicit?

Specifically, I do not see how you handle the capping backedge business here.
(Since you do not do the capping backedges, it appears that you do not even use
the DFS numbers.) Why do not we need it?

I am also missing the edge that is supposed to connect the input and output
version of the node. Could you explain where/how is it encoded?

[Michael Starzinger, 2014/12/02 12:20:34]

Acknowledged.

As discussed offline: The capping backedges are not added yet, I still need to
write test cases that proof that (and why) we need them. As for traversal, I
added a comment that try to explain the implementation. And also I added
references to the algorithm from the paper as hints. Let me know if these
comments improve the situation.

+    Trace("  Assigned class number is %d\n", GetClass(node));
+  }
+
+  void VisitPost(Node* node, Node* parent_node, DFSDirection direction) {
+    Trace("CEQ: Post-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
+    BracketList& blist = GetBracketList(node);
+
+    // Remove brackets pointing to this node.
+    BracketListDelete(blist, node, direction);
+
+    // Propagate bracket list up the DFS tree.
+    if (parent_node != NULL) {
+      BracketList& parent_blist = GetBracketList(parent_node);
+      parent_blist.splice(parent_blist.end(), blist);
+    }
+  }
+
+  void VisitBackedge(Node* from, Node* to, DFSDirection direction) {
+    Trace("CEQ: Backedge from #%d:%s to #%d:%s\n", from->id(),
+          from->op()->mnemonic(), to->id(), to->op()->mnemonic());
+
+    // Push backedge onto the bracket list.
+    Bracket bracket = {direction, kInvalidClass, 0, from, to};
+    GetBracketList(from).push_back(bracket);
+  }
+
+  void RunUndirectedDFS(Node* exit) {
+    ZoneStack<DFSStackEntry> stack(zone_);
+    DFSPush(stack, exit, NULL, kInputDirection);
+    VisitPre(exit);
+
+    while (!stack.empty()) {  // Undirected depth-first backwards traversal.
+      DFSStackEntry& entry = stack.top();
+      Node* node = entry.node;
+
+      if (entry.direction == kInputDirection) {
+        if (entry.input != node->inputs().end()) {
+          Node::Edge edge = entry.input.edge();
+          Node* input = *entry.input;
+          ++(entry.input);
+          if (NodeProperties::IsControlEdge(edge) &&
+              NodeProperties::IsControl(input)) {
+            // Visit next control input.
+            if (!GetData(input)->participates) continue;
+            if (GetData(input)->on_stack) {
+              // Found backedge if input is on stack.
+              if (input != entry.parent_node) {
+                VisitBackedge(node, input, kInputDirection);
+              }
+            } else {
+              // Push input onto stack.
+              DFSPush(stack, input, node, kInputDirection);
+              VisitPre(input);
+            }
+          }
+          continue;
+        }
+        if (entry.use != node->uses().end()) {
+          // Switch direction to uses.
+          entry.direction = kUseDirection;
+          VisitMid(node, kInputDirection);
+          continue;
+        }
+      }
+
+      if (entry.direction == kUseDirection) {
+        if (entry.use != node->uses().end()) {
+          Node::Edge edge = entry.use.edge();
+          Node* use = *(entry.use);
+          ++(entry.use);
+          if (NodeProperties::IsControlEdge(edge) &&
+              NodeProperties::IsControl(use)) {
+            // Visit next control use.
+            if (!GetData(use)->participates) continue;
+            if (GetData(use)->on_stack) {
+              // Found backedge if use is on stack.
+              if (use != entry.parent_node) {
+                VisitBackedge(node, use, kUseDirection);
+              }
+            } else {
+              // Push input onto stack.
+              DFSPush(stack, use, node, kUseDirection);
+              VisitPre(use);
+            }
+          }
+          continue;
+        }
+        if (entry.input != node->inputs().end()) {
+          // Switch direction to inputs.
+          entry.direction = kInputDirection;
+          VisitMid(node, kUseDirection);
+          continue;
+        }
+      }
+
+      // Pop node from stack when done with all inputs and uses.
+      DCHECK(entry.input == node->inputs().end());
+      DCHECK(entry.use == node->uses().end());
+      DFSPop(stack, node);
+      VisitPost(node, entry.parent_node, entry.direction);
+    }
+  }
+
+  void DetermineParticipationEnqueue(ZoneQueue<Node*>& queue, Node* node) {
+    if (!GetData(node)->participates) {
+      GetData(node)->participates = true;
+      queue.push(node);
+    }
+  }
+
+  void DetermineParticipation(Node* exit) {
+    ZoneQueue<Node*> queue(zone_);
+    DetermineParticipationEnqueue(queue, exit);
+    while (!queue.empty()) {  // Breadth-first backwards traversal.
+      Node* node = queue.front();
+      queue.pop();
+      int max = NodeProperties::PastControlIndex(node);
+      for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
+        DetermineParticipationEnqueue(queue, node->InputAt(i));
+      }
+    }
+  }
+
+ private:
+  NodeData* GetData(Node* node) { return &node_data_[node->id()]; }
+  int NewClassNumber() { return class_number_++; }
+  int NewDFSNumber() { return dfs_number_++; }
+
+  // Template used to initialize per-node data.
+  NodeData EmptyData() {
+    return {kInvalidClass, 0, false, false, BracketList(zone_)};
+  }
+
+  // Accessors for the DFS number stored within the per-node data.
+  size_t GetNumber(Node* node) { return GetData(node)->dfs_number; }
+  void SetNumber(Node* node, size_t number) {
+    GetData(node)->dfs_number = number;
+  }
+
+  // Accessors for the equivalence class stored within the per-node data.
+  size_t GetClass(Node* node) { return GetData(node)->class_number; }
+  void SetClass(Node* node, size_t number) {
+    GetData(node)->class_number = number;
+  }
+
+  // Accessors for the bracket list stored within the per-node data.
+  BracketList& GetBracketList(Node* node) { return GetData(node)->blist; }
+  void SetBracketList(Node* node, BracketList& list) {
+    GetData(node)->blist = list;
+  }
+
+  // Mutates the DFS stack by pushing an entry.
+  void DFSPush(DFSStack& stack, Node* node, Node* from, DFSDirection dir) {
+    DCHECK(GetData(node)->participates);
+    GetData(node)->on_stack = true;
+    Node::Inputs::iterator input = node->inputs().begin();
+    Node::Uses::iterator use = node->uses().begin();
+    stack.push({dir, input, use, from, node});
+  }
+
+  // Mutates the DFS stack by popping an entry.
+  void DFSPop(DFSStack& stack, Node* node) {
+    DCHECK_EQ(stack.top().node, node);
+    GetData(node)->on_stack = false;
+    GetData(node)->participates = false;
+    stack.pop();
+  }
+
+  // TODO(mstarzinger): Optimize this to avoid linear search.
+  void BracketListDelete(BracketList& blist, Node* to, DFSDirection direction) {
+    for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) {
+      if (i->to == to && i->direction != direction) {
+        Trace("  BList erased: {%d->%d}\n", i->from->id(), i->to->id());
+        i = blist.erase(i);
+      } else {
+        ++i;
+      }
+    }
+  }
+
+  void BracketListTrace(BracketList& blist) {
+    if (FLAG_trace_turbo_scheduler) {
+      Trace("  BList: ");
+      for (Bracket bracket : blist) {
+        Trace("{%d->%d} ", bracket.from->id(), bracket.to->id());
+      }
+      Trace("\n");
+    }
+  }
+
+  void Trace(const char* msg, ...) {
+    if (FLAG_trace_turbo_scheduler) {
+      va_list arguments;
+      va_start(arguments, msg);
+      base::OS::VPrint(msg, arguments);
+      va_end(arguments);
+    }
+  }
+
+  Zone* zone_;
+  Graph* graph_;
+  int dfs_number_;    // Generates new DFS pre-order numbers on demand.
+  int class_number_;  // Generates new equivalence class numbers on demand.
+  Data node_data_;    // Per-node data stored as a side-table.
+};
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_COMPILER_CONTROL_EQUIVALENCE_H_