CFA: Move TraversalRoots and ComputeAugmentedCFG into CFA

1 files changed, 8 insertions, 86 deletions

diff --git a/source/val/function.cpp b/source/val/function.cpp
index 7b3caaa3..42f7ec15 100644
--- a/source/val/function.cpp
+++ b/source/val/function.cpp
@@ -33,56 +33,6 @@ using std::pair;
 using std::tie;
 using std::vector;
 
-namespace {
-
-using libspirv::BasicBlock;
-
-// Computes a minimal set of root nodes required to traverse, in the forward
-// direction, the CFG represented by the given vector of blocks, and successor
-// and predecessor functions.  When considering adding two nodes, each having
-// predecessors, favour using the one that appears earlier on the input blocks
-// list.
-std::vector<BasicBlock*> TraversalRoots(const std::vector<BasicBlock*>& blocks,
-                                        libspirv::get_blocks_func succ_func,
-                                        libspirv::get_blocks_func pred_func) {
-  // The set of nodes which have been visited from any of the roots so far.
-  std::unordered_set<const BasicBlock*> visited;
-
-  auto mark_visited = [&visited](const BasicBlock* b) { visited.insert(b); };
-  auto ignore_block = [](const BasicBlock*) {};
-  auto ignore_blocks = [](const BasicBlock*, const BasicBlock*) {};
-
-
-  auto traverse_from_root = [&mark_visited, &succ_func, &ignore_block,
-                             &ignore_blocks](const BasicBlock* entry) {
-    spvtools::CFA<libspirv::BasicBlock>::DepthFirstTraversal(
-        entry, succ_func, mark_visited, ignore_block, ignore_blocks);
-  };
-
-  std::vector<BasicBlock*> result;
-
-  // First collect nodes without predecessors.
-  for (auto block : blocks) {
-    if (pred_func(block)->empty()) {
-      assert(visited.count(block) == 0 && "Malformed graph!");
-      result.push_back(block);
-      traverse_from_root(block);
-    }
-  }
-
-  // Now collect other stranded nodes.  These must be in unreachable cycles.
-  for (auto block : blocks) {
-    if (visited.count(block) == 0) {
-      result.push_back(block);
-      traverse_from_root(block);
-    }
-  }
-
-  return result;
-}
-
-} // anonymous namespace
-
 namespace libspirv {
 
 // Universal Limit of ResultID + 1
@@ -324,42 +274,14 @@ void Function::ComputeAugmentedCFG() {
   // the predecessors of the pseudo exit block.
   auto succ_func = [](const BasicBlock* b) { return b->successors(); };
   auto pred_func = [](const BasicBlock* b) { return b->predecessors(); };
-  auto sources = TraversalRoots(ordered_blocks_, succ_func, pred_func);
-
-  // For the predecessor traversals, reverse the order of blocks.  This
-  // will affect the post-dominance calculation as follows:
-  //  - Suppose you have blocks A and B, with A appearing before B in
-  //    the list of blocks.
-  //  - Also, A branches only to B, and B branches only to A.
-  //  - We want to compute A as dominating B, and B as post-dominating B.
-  // By using reversed blocks for predecessor traversal roots discovery,
-  // we'll add an edge from B to the pseudo-exit node, rather than from A.
-  // All this is needed to correctly process the dominance/post-dominance
-  // constraint when A is a loop header that points to itself as its
-  // own continue target, and B is the latch block for the loop.
-  std::vector<BasicBlock*> reversed_blocks(ordered_blocks_.rbegin(),
-                                           ordered_blocks_.rend());
-  auto sinks = TraversalRoots(reversed_blocks, pred_func, succ_func);
-
-  // Wire up the pseudo entry block.
-  augmented_successors_map_[&pseudo_entry_block_] = sources;
-  for (auto block : sources) {
-    auto& augmented_preds = augmented_predecessors_map_[block];
-    const auto& preds = *block->predecessors();
-    augmented_preds.reserve(1 + preds.size());
-    augmented_preds.push_back(&pseudo_entry_block_);
-    augmented_preds.insert(augmented_preds.end(), preds.begin(), preds.end());
-  }
-
-  // Wire up the pseudo exit block.
-  augmented_predecessors_map_[&pseudo_exit_block_] = sinks;
-  for (auto block : sinks) {
-    auto& augmented_succ = augmented_successors_map_[block];
-    const auto& succ = *block->successors();
-    augmented_succ.reserve(1 + succ.size());
-    augmented_succ.push_back(&pseudo_exit_block_);
-    augmented_succ.insert(augmented_succ.end(), succ.begin(), succ.end());
-  }
+  spvtools::CFA<BasicBlock>::ComputeAugmentedCFG(
+    ordered_blocks_,
+    &pseudo_entry_block_,
+    &pseudo_exit_block_,
+    &augmented_successors_map_,
+    &augmented_predecessors_map_,
+    succ_func,
+    pred_func);
 };
 
 Construct& Function::AddConstruct(const Construct& new_construct) {