From 3bea99d378af1dd2fc0baca3e0d38ec0d8169d1b Mon Sep 17 00:00:00 2001 From: Greg Fischer Date: Tue, 23 May 2017 11:31:56 -0600 Subject: [PATCH] CFA: Move TraversalRoots and ComputeAugmentedCFG into CFA --- source/cfa.h | 109 ++++++++++++++++++++++++++++++++++++++++++++++++ source/val/function.cpp | 94 ++++------------------------------------- 2 files changed, 117 insertions(+), 86 deletions(-) diff --git a/source/cfa.h b/source/cfa.h index 8733478..70c241a 100644 --- a/source/cfa.h +++ b/source/cfa.h @@ -105,6 +105,25 @@ public: /// without predecessors (such as the root node) is its own immediate dominator. static vector> CalculateDominators( const vector& postorder, get_blocks_func predecessor_func); + + // 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. + static std::vector TraversalRoots( + const std::vector& blocks, + get_blocks_func succ_func, + get_blocks_func pred_func); + + static void ComputeAugmentedCFG( + std::vector& ordered_blocks, + BB* pseudo_entry_block, + BB* pseudo_exit_block, + std::unordered_map>* augmented_successors_map, + std::unordered_map>* augmented_predecessors_map, + get_blocks_func succ_func, + get_blocks_func pred_func); }; template bool CFA::FindInWorkList(const vector& work_list, @@ -222,6 +241,96 @@ vector> CFA::CalculateDominators( return out; } +template +std::vector CFA::TraversalRoots( + const std::vector& blocks, + get_blocks_func succ_func, + get_blocks_func pred_func) { + // The set of nodes which have been visited from any of the roots so far. + std::unordered_set visited; + + auto mark_visited = [&visited](const BB* b) { visited.insert(b); }; + auto ignore_block = [](const BB*) {}; + auto ignore_blocks = [](const BB*, const BB*) {}; + + + auto traverse_from_root = [&mark_visited, &succ_func, &ignore_block, + &ignore_blocks](const BB* entry) { + DepthFirstTraversal( + entry, succ_func, mark_visited, ignore_block, ignore_blocks); + }; + + std::vector 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; +} + +template +void CFA::ComputeAugmentedCFG( + std::vector& ordered_blocks, + BB* pseudo_entry_block, BB* pseudo_exit_block, + std::unordered_map>* augmented_successors_map, + std::unordered_map>* augmented_predecessors_map, + get_blocks_func succ_func, + get_blocks_func pred_func) { + + // Compute the successors of the pseudo-entry block, and + // the predecessors of the pseudo exit block. + 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 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 = pred_func(block); + 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 = succ_func(block); + augmented_succ.reserve(1 + succ->size()); + augmented_succ.push_back(pseudo_exit_block); + augmented_succ.insert(augmented_succ.end(), succ->begin(), succ->end()); + } +}; + } // namespace spvtools #endif // SPVTOOLS_CFA_H_ diff --git a/source/val/function.cpp b/source/val/function.cpp index 7b3caaa..42f7ec1 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 TraversalRoots(const std::vector& 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 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::DepthFirstTraversal( - entry, succ_func, mark_visited, ignore_block, ignore_blocks); - }; - - std::vector 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 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::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) { -- 2.7.4