diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/IteratedDominanceFrontier.h | 151 | ||||
| -rw-r--r-- | llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h | 210 | ||||
| -rw-r--r-- | llvm/lib/Analysis/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | llvm/lib/Analysis/IteratedDominanceFrontier.cpp | 104 |
4 files changed, 282 insertions, 184 deletions
diff --git a/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h b/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h index e7d19d1a815..90e096f8c71 100644 --- a/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h +++ b/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h @@ -5,96 +5,89 @@ // 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_ANALYSIS_IDF_H #define LLVM_ANALYSIS_IDF_H -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFGDiff.h" -#include "llvm/IR/Dominators.h" +#include "llvm/Support/GenericIteratedDominanceFrontier.h" namespace llvm { -/// 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 either BasicBlock* or Inverse<BasicBlock -/// *>, depending on if you want the forward or reverse IDF. -template <class NodeTy, bool IsPostDom> -class IDFCalculator { - public: - IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT) - : DT(DT), GD(nullptr), useLiveIn(false) {} - - IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT, - const GraphDiff<BasicBlock *, IsPostDom> *GD) - : DT(DT), GD(GD), useLiveIn(false) {} - - /// Give the IDF calculator the set of blocks in which the value is - /// defined. This is equivalent to the set of starting blocks it should be - /// calculating the IDF for (though later gets pruned based on liveness). - /// - /// Note: This set *must* live for the entire lifetime of the IDF calculator. - void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) { - DefBlocks = &Blocks; - } - - /// Give the IDF calculator the set of blocks in which the value is - /// live on entry to the block. This is used to prune the IDF calculation to - /// not include blocks where any phi insertion would be dead. - /// - /// Note: This set *must* live for the entire lifetime of the IDF calculator. - - void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) { - LiveInBlocks = &Blocks; - useLiveIn = true; - } +class BasicBlock; + +namespace IDFCalculatorDetail { - /// Reset the live-in block set to be empty, and tell the IDF - /// calculator to not use liveness anymore. - void resetLiveInBlocks() { - LiveInBlocks = nullptr; - useLiveIn = false; +/// Specialization for BasicBlock for the optional use of GraphDiff. +template <bool IsPostDom> struct ChildrenGetterTy<BasicBlock, IsPostDom> { + using NodeRef = BasicBlock *; + using ChildrenTy = SmallVector<BasicBlock *, 8>; + + ChildrenGetterTy() = default; + ChildrenGetterTy(const GraphDiff<BasicBlock *, IsPostDom> *GD) : GD(GD) { + assert(GD); } - /// Calculate iterated dominance frontiers - /// - /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in - /// the file-level comment. It performs DF->IDF pruning using the live-in - /// set, to avoid computing the IDF for blocks where an inserted PHI node - /// would be dead. - void calculate(SmallVectorImpl<BasicBlock *> &IDFBlocks); - -private: - DominatorTreeBase<BasicBlock, IsPostDom> &DT; - const GraphDiff<BasicBlock *, IsPostDom> *GD; - bool useLiveIn; - const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks; - const SmallPtrSetImpl<BasicBlock *> *DefBlocks; + ChildrenTy get(const NodeRef &N); + + const GraphDiff<BasicBlock *, IsPostDom> *GD = nullptr; +}; + +} // end of namespace IDFCalculatorDetail + +template <bool IsPostDom> +class IDFCalculator final : public IDFCalculatorBase<BasicBlock, IsPostDom> { +public: + using IDFCalculatorBase = + typename llvm::IDFCalculatorBase<BasicBlock, IsPostDom>; + using ChildrenGetterTy = typename IDFCalculatorBase::ChildrenGetterTy; + + IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT) + : IDFCalculatorBase(DT) {} + + IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT, + const GraphDiff<BasicBlock *, IsPostDom> *GD) + : IDFCalculatorBase(DT, ChildrenGetterTy(GD)) { + assert(GD); + } }; -typedef IDFCalculator<BasicBlock *, false> ForwardIDFCalculator; -typedef IDFCalculator<Inverse<BasicBlock *>, true> ReverseIDFCalculator; + +using ForwardIDFCalculator = IDFCalculator<false>; +using ReverseIDFCalculator = IDFCalculator<true>; + +//===----------------------------------------------------------------------===// +// Implementation. +//===----------------------------------------------------------------------===// + +namespace IDFCalculatorDetail { + +template <bool IsPostDom> +using BBChildrenGetterTy = ChildrenGetterTy<BasicBlock, IsPostDom>; + +template <bool IsPostDom> +typename BBChildrenGetterTy<IsPostDom>::ChildrenTy +BBChildrenGetterTy<IsPostDom>::get( + const BBChildrenGetterTy<IsPostDom>::NodeRef &N) { + + using OrderedNodeTy = + typename IDFCalculatorBase<BasicBlock, IsPostDom>::OrderedNodeTy; + + if (!GD) { + auto Children = children<OrderedNodeTy>(N); + return {Children.begin(), Children.end()}; + } + + using SnapShotBBPairTy = + std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, OrderedNodeTy>; + + ChildrenTy Ret; + for (const auto &SnapShotBBPair : children<SnapShotBBPairTy>({GD, N})) + Ret.emplace_back(SnapShotBBPair.second); + return Ret; } + +} // end of namespace IDFCalculatorDetail + +} // end of namespace llvm + #endif diff --git a/llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h b/llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h new file mode 100644 index 00000000000..975ebafa063 --- /dev/null +++ b/llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h @@ -0,0 +1,210 @@ +//===- 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_GENERIC_IDF_H +#define LLVM_SUPPORT_GENERIC_IDF_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.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 { + using NodeRef = typename GraphTraits<NodeTy>::NodeRef; + using ChildrenTy = SmallVector<NodeRef, 8>; + + ChildrenTy get(const NodeRef &N); +}; + +} // 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 { +public: + using OrderedNodeTy = + typename std::conditional<IsPostDom, Inverse<NodeTy *>, NodeTy *>::type; + using ChildrenGetterTy = + IDFCalculatorDetail::ChildrenGetterTy<NodeTy, IsPostDom>; + + IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {} + + IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT, + const ChildrenGetterTy &C) + : DT(DT), ChildrenGetter(C) {} + + /// Give the IDF calculator the set of blocks in which the value is + /// defined. This is equivalent to the set of starting blocks it should be + /// calculating the IDF for (though later gets pruned based on liveness). + /// + /// Note: This set *must* live for the entire lifetime of the IDF calculator. + void setDefiningBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) { + DefBlocks = &Blocks; + } + + /// Give the IDF calculator the set of blocks in which the value is + /// live on entry to the block. This is used to prune the IDF calculation to + /// not include blocks where any phi insertion would be dead. + /// + /// Note: This set *must* live for the entire lifetime of the IDF calculator. + void setLiveInBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) { + LiveInBlocks = &Blocks; + useLiveIn = true; + } + + /// Reset the live-in block set to be empty, and tell the IDF + /// calculator to not use liveness anymore. + void resetLiveInBlocks() { + LiveInBlocks = nullptr; + useLiveIn = false; + } + + /// Calculate iterated dominance frontiers + /// + /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in + /// the file-level comment. It performs DF->IDF pruning using the live-in + /// set, to avoid computing the IDF for blocks where an inserted PHI node + /// would be dead. + void calculate(SmallVectorImpl<NodeTy *> &IDFBlocks); + +private: + DominatorTreeBase<NodeTy, IsPostDom> &DT; + ChildrenGetterTy ChildrenGetter; + bool useLiveIn = false; + const SmallPtrSetImpl<NodeTy *> *LiveInBlocks; + const SmallPtrSetImpl<NodeTy *> *DefBlocks; +}; + +//===----------------------------------------------------------------------===// +// Implementation. +//===----------------------------------------------------------------------===// + +namespace IDFCalculatorDetail { + +template <class NodeTy, bool IsPostDom> +typename ChildrenGetterTy<NodeTy, IsPostDom>::ChildrenTy +ChildrenGetterTy<NodeTy, IsPostDom>::get( + const ChildrenGetterTy<NodeTy, IsPostDom>::NodeRef &N) { + using OrderedNodeTy = + typename IDFCalculatorBase<NodeTy, IsPostDom>::OrderedNodeTy; + + auto Children = children<OrderedNodeTy>(N); + return {Children.begin(), Children.end()}; +}; + +} // end of namespace IDFCalculatorDetail + +template <class NodeTy, bool IsPostDom> +void IDFCalculatorBase<NodeTy, IsPostDom>::calculate( + SmallVectorImpl<NodeTy *> &PHIBlocks) { + // Use a priority queue keyed on dominator tree level so that inserted nodes + // are handled from the bottom of the dominator tree upwards. We also augment + // the level with a DFS number to ensure that the blocks are ordered in a + // deterministic way. + using DomTreeNodePair = + std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>; + using IDFPriorityQueue = + std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>, + less_second>; + + IDFPriorityQueue PQ; + + DT.updateDFSNumbers(); + + for (NodeTy *BB : *DefBlocks) { + if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB)) + PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())}); + } + + SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist; + SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedPQ; + SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedWorklist; + + while (!PQ.empty()) { + DomTreeNodePair RootPair = PQ.top(); + PQ.pop(); + DomTreeNodeBase<NodeTy> *Root = RootPair.first; + unsigned RootLevel = RootPair.second.first; + + // Walk all dominator tree children of Root, inspecting their CFG edges with + // targets elsewhere on the dominator tree. Only targets whose level is at + // most Root's level are added to the iterated dominance frontier of the + // definition set. + + Worklist.clear(); + Worklist.push_back(Root); + VisitedWorklist.insert(Root); + + while (!Worklist.empty()) { + DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val(); + NodeTy *BB = Node->getBlock(); + // Succ is the successor in the direction we are calculating IDF, so it is + // successor for IDF, and predecessor for Reverse IDF. + auto DoWork = [&](NodeTy *Succ) { + DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ); + + const unsigned SuccLevel = SuccNode->getLevel(); + if (SuccLevel > RootLevel) + return; + + if (!VisitedPQ.insert(SuccNode).second) + return; + + NodeTy *SuccBB = SuccNode->getBlock(); + if (useLiveIn && !LiveInBlocks->count(SuccBB)) + return; + + PHIBlocks.emplace_back(SuccBB); + if (!DefBlocks->count(SuccBB)) + PQ.push(std::make_pair( + SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn()))); + }; + + for (auto Succ : ChildrenGetter.get(BB)) + DoWork(Succ); + + for (auto DomChild : *Node) { + if (VisitedWorklist.insert(DomChild).second) + Worklist.push_back(DomChild); + } + } + } +} + +} // end of namespace llvm + +#endif diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt index 3cc9fe3c171..dd5d6251414 100644 --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -41,7 +41,6 @@ add_llvm_library(LLVMAnalysis InstructionSimplify.cpp Interval.cpp IntervalPartition.cpp - IteratedDominanceFrontier.cpp LazyBranchProbabilityInfo.cpp LazyBlockFrequencyInfo.cpp LazyCallGraph.cpp diff --git a/llvm/lib/Analysis/IteratedDominanceFrontier.cpp b/llvm/lib/Analysis/IteratedDominanceFrontier.cpp deleted file mode 100644 index 89257121c6a..00000000000 --- a/llvm/lib/Analysis/IteratedDominanceFrontier.cpp +++ /dev/null @@ -1,104 +0,0 @@ -//===- IteratedDominanceFrontier.cpp - Compute IDF ------------------------===// -// -// 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 -// -//===----------------------------------------------------------------------===// -// -// Compute iterated dominance frontiers using a linear time algorithm. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/IteratedDominanceFrontier.h" -#include "llvm/IR/CFG.h" -#include "llvm/IR/Dominators.h" -#include <queue> - -namespace llvm { - -template <class NodeTy, bool IsPostDom> -void IDFCalculator<NodeTy, IsPostDom>::calculate( - SmallVectorImpl<BasicBlock *> &PHIBlocks) { - // Use a priority queue keyed on dominator tree level so that inserted nodes - // are handled from the bottom of the dominator tree upwards. We also augment - // the level with a DFS number to ensure that the blocks are ordered in a - // deterministic way. - typedef std::pair<DomTreeNode *, std::pair<unsigned, unsigned>> - DomTreeNodePair; - typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>, - less_second> IDFPriorityQueue; - IDFPriorityQueue PQ; - - DT.updateDFSNumbers(); - - for (BasicBlock *BB : *DefBlocks) { - if (DomTreeNode *Node = DT.getNode(BB)) - PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())}); - } - - SmallVector<DomTreeNode *, 32> Worklist; - SmallPtrSet<DomTreeNode *, 32> VisitedPQ; - SmallPtrSet<DomTreeNode *, 32> VisitedWorklist; - - while (!PQ.empty()) { - DomTreeNodePair RootPair = PQ.top(); - PQ.pop(); - DomTreeNode *Root = RootPair.first; - unsigned RootLevel = RootPair.second.first; - - // Walk all dominator tree children of Root, inspecting their CFG edges with - // targets elsewhere on the dominator tree. Only targets whose level is at - // most Root's level are added to the iterated dominance frontier of the - // definition set. - - Worklist.clear(); - Worklist.push_back(Root); - VisitedWorklist.insert(Root); - - while (!Worklist.empty()) { - DomTreeNode *Node = Worklist.pop_back_val(); - BasicBlock *BB = Node->getBlock(); - // Succ is the successor in the direction we are calculating IDF, so it is - // successor for IDF, and predecessor for Reverse IDF. - auto DoWork = [&](BasicBlock *Succ) { - DomTreeNode *SuccNode = DT.getNode(Succ); - - const unsigned SuccLevel = SuccNode->getLevel(); - if (SuccLevel > RootLevel) - return; - - if (!VisitedPQ.insert(SuccNode).second) - return; - - BasicBlock *SuccBB = SuccNode->getBlock(); - if (useLiveIn && !LiveInBlocks->count(SuccBB)) - return; - - PHIBlocks.emplace_back(SuccBB); - if (!DefBlocks->count(SuccBB)) - PQ.push(std::make_pair( - SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn()))); - }; - - if (GD) { - for (auto Pair : children< - std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, NodeTy>>( - {GD, BB})) - DoWork(Pair.second); - } else { - for (auto *Succ : children<NodeTy>(BB)) - DoWork(Succ); - } - - for (auto DomChild : *Node) { - if (VisitedWorklist.insert(DomChild).second) - Worklist.push_back(DomChild); - } - } - } -} - -template class IDFCalculator<BasicBlock *, false>; -template class IDFCalculator<Inverse<BasicBlock *>, true>; -} |
