//===- IteratedDominanceFrontier.h - Calculate IDF --------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// \file /// Compute iterated dominance frontiers using a linear time algorithm. /// /// The algorithm used here is based on: /// /// Sreedhar and Gao. A linear time algorithm for placing phi-nodes. /// In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of /// Programming Languages /// POPL '95. ACM, New York, NY, 62-73. /// /// It has been modified to not explicitly use the DJ graph data structure and /// to directly compute pruned SSA using per-variable liveness information. // //===----------------------------------------------------------------------===// #ifndef LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H #define LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Support/GenericDomTree.h" #include <queue> namespace llvm { namespace IDFCalculatorDetail { /// Generic utility class used for getting the children of a basic block. /// May be specialized if, for example, one wouldn't like to return nullpointer /// successors. template <class NodeTy, bool IsPostDom> struct ChildrenGetterTy { … }; } // end of namespace IDFCalculatorDetail /// Determine the iterated dominance frontier, given a set of defining /// blocks, and optionally, a set of live-in blocks. /// /// In turn, the results can be used to place phi nodes. /// /// This algorithm is a linear time computation of Iterated Dominance Frontiers, /// pruned using the live-in set. /// By default, liveness is not used to prune the IDF computation. /// The template parameters should be of a CFG block type. template <class NodeTy, bool IsPostDom> class IDFCalculatorBase { … }; //===----------------------------------------------------------------------===// // Implementation. //===----------------------------------------------------------------------===// namespace IDFCalculatorDetail { template <class NodeTy, bool IsPostDom> typename ChildrenGetterTy<NodeTy, IsPostDom>::range ChildrenGetterTy<NodeTy, IsPostDom>::get(const NodeRef &N) { … } } // end of namespace IDFCalculatorDetail template <class NodeTy, bool IsPostDom> void IDFCalculatorBase<NodeTy, IsPostDom>::calculate( SmallVectorImpl<NodeTy *> &IDFBlocks) { … } } // end of namespace llvm #endif