llvm/Support/GenericIteratedDominanceFrontier.h

0001 //===- IteratedDominanceFrontier.h - Calculate IDF --------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 /// \file
0009 /// Compute iterated dominance frontiers using a linear time algorithm.
0010 ///
0011 /// The algorithm used here is based on:
0012 ///
0013 ///   Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
0014 ///   In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of
0015 ///   Programming Languages
0016 ///   POPL '95. ACM, New York, NY, 62-73.
0017 ///
0018 /// It has been modified to not explicitly use the DJ graph data structure and
0019 /// to directly compute pruned SSA using per-variable liveness information.
0020 //
0021 //===----------------------------------------------------------------------===//
0022
0023 #ifndef LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H
0024 #define LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H
0025
0026 #include "llvm/ADT/SmallPtrSet.h"
0027 #include "llvm/ADT/SmallVector.h"
0028 #include "llvm/ADT/iterator_range.h"
0029 #include "llvm/Support/GenericDomTree.h"
0030 #include <queue>
0031
0032 namespace llvm {
0033
0034 namespace IDFCalculatorDetail {
0035
0036 /// Generic utility class used for getting the children of a basic block.
0037 /// May be specialized if, for example, one wouldn't like to return nullpointer
0038 /// successors.
0039 template <class NodeTy, bool IsPostDom> struct ChildrenGetterTy {
0040   using NodeRef = typename GraphTraits<NodeTy *>::NodeRef;
0041   using ChildIteratorType = typename GraphTraits<NodeTy *>::ChildIteratorType;
0042   using range = iterator_range<ChildIteratorType>;
0043
0044   range get(const NodeRef &N);
0045 };
0046
0047 } // end of namespace IDFCalculatorDetail
0048
0049 /// Determine the iterated dominance frontier, given a set of defining
0050 /// blocks, and optionally, a set of live-in blocks.
0051 ///
0052 /// In turn, the results can be used to place phi nodes.
0053 ///
0054 /// This algorithm is a linear time computation of Iterated Dominance Frontiers,
0055 /// pruned using the live-in set.
0056 /// By default, liveness is not used to prune the IDF computation.
0057 /// The template parameters should be of a CFG block type.
0058 template <class NodeTy, bool IsPostDom> class IDFCalculatorBase {
0059 public:
0060   using OrderedNodeTy =
0061       std::conditional_t<IsPostDom, Inverse<NodeTy *>, NodeTy *>;
0062   using ChildrenGetterTy =
0063       IDFCalculatorDetail::ChildrenGetterTy<NodeTy, IsPostDom>;
0064
0065   IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {}
0066
0067   IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT,
0068                     const ChildrenGetterTy &C)
0069       : DT(DT), ChildrenGetter(C) {}
0070
0071   /// Give the IDF calculator the set of blocks in which the value is
0072   /// defined.  This is equivalent to the set of starting blocks it should be
0073   /// calculating the IDF for (though later gets pruned based on liveness).
0074   ///
0075   /// Note: This set *must* live for the entire lifetime of the IDF calculator.
0076   void setDefiningBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
0077     DefBlocks = &Blocks;
0078   }
0079
0080   /// Give the IDF calculator the set of blocks in which the value is
0081   /// live on entry to the block.   This is used to prune the IDF calculation to
0082   /// not include blocks where any phi insertion would be dead.
0083   ///
0084   /// Note: This set *must* live for the entire lifetime of the IDF calculator.
0085   void setLiveInBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
0086     LiveInBlocks = &Blocks;
0087     useLiveIn = true;
0088   }
0089
0090   /// Reset the live-in block set to be empty, and tell the IDF
0091   /// calculator to not use liveness anymore.
0092   void resetLiveInBlocks() {
0093     LiveInBlocks = nullptr;
0094     useLiveIn = false;
0095   }
0096
0097   /// Calculate iterated dominance frontiers
0098   ///
0099   /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in
0100   /// the file-level comment.  It performs DF->IDF pruning using the live-in
0101   /// set, to avoid computing the IDF for blocks where an inserted PHI node
0102   /// would be dead.
0103   void calculate(SmallVectorImpl<NodeTy *> &IDFBlocks);
0104
0105 private:
0106   DominatorTreeBase<NodeTy, IsPostDom> &DT;
0107   ChildrenGetterTy ChildrenGetter;
0108   bool useLiveIn = false;
0109   const SmallPtrSetImpl<NodeTy *> *LiveInBlocks;
0110   const SmallPtrSetImpl<NodeTy *> *DefBlocks;
0111 };
0112
0113 //===----------------------------------------------------------------------===//
0114 // Implementation.
0115 //===----------------------------------------------------------------------===//
0116
0117 namespace IDFCalculatorDetail {
0118
0119 template <class NodeTy, bool IsPostDom>
0120 typename ChildrenGetterTy<NodeTy, IsPostDom>::range
0121 ChildrenGetterTy<NodeTy, IsPostDom>::get(const NodeRef &N) {
0122   using OrderedNodeTy =
0123       typename IDFCalculatorBase<NodeTy, IsPostDom>::OrderedNodeTy;
0124
0125   return children<OrderedNodeTy>(N);
0126 }
0127
0128 } // end of namespace IDFCalculatorDetail
0129
0130 template <class NodeTy, bool IsPostDom>
0131 void IDFCalculatorBase<NodeTy, IsPostDom>::calculate(
0132     SmallVectorImpl<NodeTy *> &IDFBlocks) {
0133   // Use a priority queue keyed on dominator tree level so that inserted nodes
0134   // are handled from the bottom of the dominator tree upwards. We also augment
0135   // the level with a DFS number to ensure that the blocks are ordered in a
0136   // deterministic way.
0137   using DomTreeNodePair =
0138       std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>;
0139   using IDFPriorityQueue =
0140       std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
0141                           less_second>;
0142
0143   IDFPriorityQueue PQ;
0144
0145   DT.updateDFSNumbers();
0146
0147   SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist;
0148   SmallPtrSet<DomTreeNodeBase<NodeTy> *, 16> VisitedPQ;
0149   SmallPtrSet<DomTreeNodeBase<NodeTy> *, 16> VisitedWorklist;
0150   if (useLiveIn) {
0151     VisitedPQ.reserve(LiveInBlocks->size());
0152     VisitedWorklist.reserve(LiveInBlocks->size());
0153   }
0154
0155   for (NodeTy *BB : *DefBlocks)
0156     if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB)) {
0157       PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
0158       VisitedWorklist.insert(Node);
0159     }
0160
0161   while (!PQ.empty()) {
0162     DomTreeNodePair RootPair = PQ.top();
0163     PQ.pop();
0164     DomTreeNodeBase<NodeTy> *Root = RootPair.first;
0165     unsigned RootLevel = RootPair.second.first;
0166
0167     // Walk all dominator tree children of Root, inspecting their CFG edges with
0168     // targets elsewhere on the dominator tree. Only targets whose level is at
0169     // most Root's level are added to the iterated dominance frontier of the
0170     // definition set.
0171
0172     assert(Worklist.empty());
0173     Worklist.push_back(Root);
0174
0175     while (!Worklist.empty()) {
0176       DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val();
0177       NodeTy *BB = Node->getBlock();
0178       // Succ is the successor in the direction we are calculating IDF, so it is
0179       // successor for IDF, and predecessor for Reverse IDF.
0180       auto DoWork = [&](NodeTy *Succ) {
0181         DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ);
0182
0183         const unsigned SuccLevel = SuccNode->getLevel();
0184         if (SuccLevel > RootLevel)
0185           return;
0186
0187         if (!VisitedPQ.insert(SuccNode).second)
0188           return;
0189
0190         NodeTy *SuccBB = SuccNode->getBlock();
0191         if (useLiveIn && !LiveInBlocks->count(SuccBB))
0192           return;
0193
0194         IDFBlocks.emplace_back(SuccBB);
0195         if (!DefBlocks->count(SuccBB))
0196           PQ.push(std::make_pair(
0197               SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
0198       };
0199
0200       for (auto *Succ : ChildrenGetter.get(BB))
0201         DoWork(Succ);
0202
0203       for (auto DomChild : *Node) {
0204         if (VisitedWorklist.insert(DomChild).second)
0205           Worklist.push_back(DomChild);
0206       }
0207     }
0208   }
0209 }
0210
0211 } // end of namespace llvm
0212
0213 #endif