Index: llvm/trunk/include/llvm/Analysis/IteratedDominanceFrontier.h =================================================================== --- llvm/trunk/include/llvm/Analysis/IteratedDominanceFrontier.h +++ llvm/trunk/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, depending on if you want the forward or reverse IDF. -template -class IDFCalculator { - public: - IDFCalculator(DominatorTreeBase &DT) - : DT(DT), GD(nullptr), useLiveIn(false) {} - - IDFCalculator(DominatorTreeBase &DT, - const GraphDiff *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 &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 &Blocks) { - LiveInBlocks = &Blocks; - useLiveIn = true; - } +class BasicBlock; - /// 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; +namespace IDFCalculatorDetail { + +/// Specialization for BasicBlock for the optional use of GraphDiff. +template struct ChildrenGetterTy { + using NodeRef = BasicBlock *; + using ChildrenTy = SmallVector; + + ChildrenGetterTy() = default; + ChildrenGetterTy(const GraphDiff *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 &IDFBlocks); - -private: - DominatorTreeBase &DT; - const GraphDiff *GD; - bool useLiveIn; - const SmallPtrSetImpl *LiveInBlocks; - const SmallPtrSetImpl *DefBlocks; + ChildrenTy get(const NodeRef &N); + + const GraphDiff *GD = nullptr; }; -typedef IDFCalculator ForwardIDFCalculator; -typedef IDFCalculator, true> ReverseIDFCalculator; + +} // end of namespace IDFCalculatorDetail + +template +class IDFCalculator final : public IDFCalculatorBase { +public: + using IDFCalculatorBase = + typename llvm::IDFCalculatorBase; + using ChildrenGetterTy = typename IDFCalculatorBase::ChildrenGetterTy; + + IDFCalculator(DominatorTreeBase &DT) + : IDFCalculatorBase(DT) {} + + IDFCalculator(DominatorTreeBase &DT, + const GraphDiff *GD) + : IDFCalculatorBase(DT, ChildrenGetterTy(GD)) { + assert(GD); + } +}; + +using ForwardIDFCalculator = IDFCalculator; +using ReverseIDFCalculator = IDFCalculator; + +//===----------------------------------------------------------------------===// +// Implementation. +//===----------------------------------------------------------------------===// + +namespace IDFCalculatorDetail { + +template +using BBChildrenGetterTy = ChildrenGetterTy; + +template +typename BBChildrenGetterTy::ChildrenTy +BBChildrenGetterTy::get( + const BBChildrenGetterTy::NodeRef &N) { + + using OrderedNodeTy = + typename IDFCalculatorBase::OrderedNodeTy; + + if (!GD) { + auto Children = children(N); + return {Children.begin(), Children.end()}; + } + + using SnapShotBBPairTy = + std::pair *, OrderedNodeTy>; + + ChildrenTy Ret; + for (const auto &SnapShotBBPair : children({GD, N})) + Ret.emplace_back(SnapShotBBPair.second); + return Ret; } + +} // end of namespace IDFCalculatorDetail + +} // end of namespace llvm + #endif Index: llvm/trunk/include/llvm/Support/GenericIteratedDominanceFrontier.h =================================================================== --- llvm/trunk/include/llvm/Support/GenericIteratedDominanceFrontier.h +++ llvm/trunk/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 + +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 struct ChildrenGetterTy { + using NodeRef = typename GraphTraits::NodeRef; + using ChildrenTy = SmallVector; + + 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 IDFCalculatorBase { +public: + using OrderedNodeTy = + typename std::conditional, NodeTy *>::type; + using ChildrenGetterTy = + IDFCalculatorDetail::ChildrenGetterTy; + + IDFCalculatorBase(DominatorTreeBase &DT) : DT(DT) {} + + IDFCalculatorBase(DominatorTreeBase &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 &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 &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 &IDFBlocks); + +private: + DominatorTreeBase &DT; + ChildrenGetterTy ChildrenGetter; + bool useLiveIn = false; + const SmallPtrSetImpl *LiveInBlocks; + const SmallPtrSetImpl *DefBlocks; +}; + +//===----------------------------------------------------------------------===// +// Implementation. +//===----------------------------------------------------------------------===// + +namespace IDFCalculatorDetail { + +template +typename ChildrenGetterTy::ChildrenTy +ChildrenGetterTy::get( + const ChildrenGetterTy::NodeRef &N) { + using OrderedNodeTy = + typename IDFCalculatorBase::OrderedNodeTy; + + auto Children = children(N); + return {Children.begin(), Children.end()}; +}; + +} // end of namespace IDFCalculatorDetail + +template +void IDFCalculatorBase::calculate( + SmallVectorImpl &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 *, std::pair>; + using IDFPriorityQueue = + std::priority_queue, + less_second>; + + IDFPriorityQueue PQ; + + DT.updateDFSNumbers(); + + for (NodeTy *BB : *DefBlocks) { + if (DomTreeNodeBase *Node = DT.getNode(BB)) + PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())}); + } + + SmallVector *, 32> Worklist; + SmallPtrSet *, 32> VisitedPQ; + SmallPtrSet *, 32> VisitedWorklist; + + while (!PQ.empty()) { + DomTreeNodePair RootPair = PQ.top(); + PQ.pop(); + DomTreeNodeBase *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 *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 *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 Index: llvm/trunk/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Analysis/CMakeLists.txt +++ llvm/trunk/lib/Analysis/CMakeLists.txt @@ -41,7 +41,6 @@ InstructionSimplify.cpp Interval.cpp IntervalPartition.cpp - IteratedDominanceFrontier.cpp LazyBranchProbabilityInfo.cpp LazyBlockFrequencyInfo.cpp LazyCallGraph.cpp Index: llvm/trunk/lib/Analysis/IteratedDominanceFrontier.cpp =================================================================== --- llvm/trunk/lib/Analysis/IteratedDominanceFrontier.cpp +++ llvm/trunk/lib/Analysis/IteratedDominanceFrontier.cpp @@ -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 - -namespace llvm { - -template -void IDFCalculator::calculate( - SmallVectorImpl &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> - DomTreeNodePair; - typedef std::priority_queue, - 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 Worklist; - SmallPtrSet VisitedPQ; - SmallPtrSet 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 *, NodeTy>>( - {GD, BB})) - DoWork(Pair.second); - } else { - for (auto *Succ : children(BB)) - DoWork(Succ); - } - - for (auto DomChild : *Node) { - if (VisitedWorklist.insert(DomChild).second) - Worklist.push_back(DomChild); - } - } - } -} - -template class IDFCalculator; -template class IDFCalculator, true>; -}