From d6f29790687f697ee3cb0bf105e365dba5faf384 Mon Sep 17 00:00:00 2001 From: Greg Fischer Date: Mon, 8 May 2017 18:32:12 -0600 Subject: [PATCH] CFA: Pull in CalculateDominators --- source/cfa.h | 92 +++++++++++++++++++++++++++++++++++++++++++++++++ source/validate.h | 24 ------------- source/validate_cfg.cpp | 72 ++------------------------------------ 3 files changed, 94 insertions(+), 94 deletions(-) diff --git a/source/cfa.h b/source/cfa.h index c08799e..8733478 100644 --- a/source/cfa.h +++ b/source/cfa.h @@ -82,6 +82,29 @@ public: std::function preorder, std::function postorder, std::function backedge); + + /// @brief Calculates dominator edges for a set of blocks + /// + /// Computes dominators using the algorithm of Cooper, Harvey, and Kennedy + /// "A Simple, Fast Dominance Algorithm", 2001. + /// + /// The algorithm assumes there is a unique root node (a node without + /// predecessors), and it is therefore at the end of the postorder vector. + /// + /// This function calculates the dominator edges for a set of blocks in the CFG. + /// Uses the dominator algorithm by Cooper et al. + /// + /// @param[in] postorder A vector of blocks in post order traversal order + /// in a CFG + /// @param[in] predecessor_func Function used to get the predecessor nodes of a + /// block + /// + /// @return the dominator tree of the graph, as a vector of pairs of nodes. + /// The first node in the pair is a node in the graph. The second node in the + /// pair is its immediate dominator in the sense of Cooper et.al., where a block + /// without predecessors (such as the root node) is its own immediate dominator. + static vector> CalculateDominators( + const vector& postorder, get_blocks_func predecessor_func); }; template bool CFA::FindInWorkList(const vector& work_list, @@ -130,6 +153,75 @@ template void CFA::DepthFirstTraversal(const BB* entry, } } +template +vector> CFA::CalculateDominators( + const vector& postorder, get_blocks_func predecessor_func) { + struct block_detail { + size_t dominator; ///< The index of blocks's dominator in post order array + size_t postorder_index; ///< The index of the block in the post order array + }; + const size_t undefined_dom = postorder.size(); + + unordered_map idoms; + for (size_t i = 0; i < postorder.size(); i++) { + idoms[postorder[i]] = { undefined_dom, i }; + } + idoms[postorder.back()].dominator = idoms[postorder.back()].postorder_index; + + bool changed = true; + while (changed) { + changed = false; + for (auto b = postorder.rbegin() + 1; b != postorder.rend(); ++b) { + const vector& predecessors = *predecessor_func(*b); + // Find the first processed/reachable predecessor that is reachable + // in the forward traversal. + auto res = find_if(begin(predecessors), end(predecessors), + [&idoms, undefined_dom](BB* pred) { + return idoms.count(pred) && + idoms[pred].dominator != undefined_dom; + }); + if (res == end(predecessors)) continue; + const BB* idom = *res; + size_t idom_idx = idoms[idom].postorder_index; + + // all other predecessors + for (const auto* p : predecessors) { + if (idom == p) continue; + // Only consider nodes reachable in the forward traversal. + // Otherwise the intersection doesn't make sense and will never + // terminate. + if (!idoms.count(p)) continue; + if (idoms[p].dominator != undefined_dom) { + size_t finger1 = idoms[p].postorder_index; + size_t finger2 = idom_idx; + while (finger1 != finger2) { + while (finger1 < finger2) { + finger1 = idoms[postorder[finger1]].dominator; + } + while (finger2 < finger1) { + finger2 = idoms[postorder[finger2]].dominator; + } + } + idom_idx = finger1; + } + } + if (idoms[*b].dominator != idom_idx) { + idoms[*b].dominator = idom_idx; + changed = true; + } + } + } + + vector> out; + for (auto idom : idoms) { + // NOTE: performing a const cast for convenient usage with + // UpdateImmediateDominators + out.push_back({ const_cast(get<0>(idom)), + const_cast(postorder[get<1>(idom).dominator]) }); + } + return out; +} + } // namespace spvtools #endif // SPVTOOLS_CFA_H_ diff --git a/source/validate.h b/source/validate.h index f24e75d..34d1ffe 100644 --- a/source/validate.h +++ b/source/validate.h @@ -34,30 +34,6 @@ class BasicBlock; using get_blocks_func = std::function*(const BasicBlock*)>; -/// @brief Calculates dominator edges for a set of blocks -/// -/// Computes dominators using the algorithm of Cooper, Harvey, and Kennedy -/// "A Simple, Fast Dominance Algorithm", 2001. -/// -/// The algorithm assumes there is a unique root node (a node without -/// predecessors), and it is therefore at the end of the postorder vector. -/// -/// This function calculates the dominator edges for a set of blocks in the CFG. -/// Uses the dominator algorithm by Cooper et al. -/// -/// @param[in] postorder A vector of blocks in post order traversal order -/// in a CFG -/// @param[in] predecessor_func Function used to get the predecessor nodes of a -/// block -/// -/// @return the dominator tree of the graph, as a vector of pairs of nodes. -/// The first node in the pair is a node in the graph. The second node in the -/// pair is its immediate dominator in the sense of Cooper et.al., where a block -/// without predecessors (such as the root node) is its own immediate dominator. -std::vector> CalculateDominators( - const std::vector& postorder, - get_blocks_func predecessor_func); - /// @brief Performs the Control Flow Graph checks /// /// @param[in] _ the validation state of the module diff --git a/source/validate_cfg.cpp b/source/validate_cfg.cpp index 85638f3..9234542 100644 --- a/source/validate_cfg.cpp +++ b/source/validate_cfg.cpp @@ -61,74 +61,6 @@ using bb_iter = vector::const_iterator; } // namespace -vector> CalculateDominators( - const vector& postorder, get_blocks_func predecessor_func) { - struct block_detail { - size_t dominator; ///< The index of blocks's dominator in post order array - size_t postorder_index; ///< The index of the block in the post order array - }; - const size_t undefined_dom = postorder.size(); - - unordered_map idoms; - for (size_t i = 0; i < postorder.size(); i++) { - idoms[postorder[i]] = {undefined_dom, i}; - } - idoms[postorder.back()].dominator = idoms[postorder.back()].postorder_index; - - bool changed = true; - while (changed) { - changed = false; - for (auto b = postorder.rbegin() + 1; b != postorder.rend(); ++b) { - const vector& predecessors = *predecessor_func(*b); - // Find the first processed/reachable predecessor that is reachable - // in the forward traversal. - auto res = find_if(begin(predecessors), end(predecessors), - [&idoms, undefined_dom](BasicBlock* pred) { - return idoms.count(pred) && - idoms[pred].dominator != undefined_dom; - }); - if (res == end(predecessors)) continue; - const BasicBlock* idom = *res; - size_t idom_idx = idoms[idom].postorder_index; - - // all other predecessors - for (const auto* p : predecessors) { - if (idom == p) continue; - // Only consider nodes reachable in the forward traversal. - // Otherwise the intersection doesn't make sense and will never - // terminate. - if (!idoms.count(p)) continue; - if (idoms[p].dominator != undefined_dom) { - size_t finger1 = idoms[p].postorder_index; - size_t finger2 = idom_idx; - while (finger1 != finger2) { - while (finger1 < finger2) { - finger1 = idoms[postorder[finger1]].dominator; - } - while (finger2 < finger1) { - finger2 = idoms[postorder[finger2]].dominator; - } - } - idom_idx = finger1; - } - } - if (idoms[*b].dominator != idom_idx) { - idoms[*b].dominator = idom_idx; - changed = true; - } - } - } - - vector> out; - for (auto idom : idoms) { - // NOTE: performing a const cast for convenient usage with - // UpdateImmediateDominators - out.push_back({const_cast(get<0>(idom)), - const_cast(postorder[get<1>(idom).dominator])}); - } - return out; -} - void printDominatorList(const BasicBlock& b) { std::cout << b.id() << " is dominated by: "; const BasicBlock* bb = &b; @@ -355,7 +287,7 @@ spv_result_t PerformCfgChecks(ValidationState_t& _) { function.first_block(), function.AugmentedCFGSuccessorsFunction(), ignore_block, [&](cbb_ptr b) { postorder.push_back(b); }, ignore_edge); - auto edges = libspirv::CalculateDominators( + auto edges = spvtools::CFA::CalculateDominators( postorder, function.AugmentedCFGPredecessorsFunction()); for (auto edge : edges) { edge.first->SetImmediateDominator(edge.second); @@ -366,7 +298,7 @@ spv_result_t PerformCfgChecks(ValidationState_t& _) { function.pseudo_exit_block(), function.AugmentedCFGPredecessorsFunction(), ignore_block, [&](cbb_ptr b) { postdom_postorder.push_back(b); }, ignore_edge); - auto postdom_edges = libspirv::CalculateDominators( + auto postdom_edges = spvtools::CFA::CalculateDominators( postdom_postorder, function.AugmentedCFGSuccessorsFunction()); for (auto edge : postdom_edges) { edge.first->SetImmediatePostDominator(edge.second); -- 2.7.4