include/llvm/Support/GenericIteratedDominanceFrontier.h

   1 //===- IteratedDominanceFrontier.h - Calculate IDF --------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 /// \file
   9 /// Compute iterated dominance frontiers using a linear time algorithm.
  10 ///
  11 /// The algorithm used here is based on:
  12 ///
  13 ///   Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
  14 ///   In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of
  15 ///   Programming Languages
  16 ///   POPL '95. ACM, New York, NY, 62-73.
  17 ///
  18 /// It has been modified to not explicitly use the DJ graph data structure and
  19 /// to directly compute pruned SSA using per-variable liveness information.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #ifndef LLVM_SUPPORT_GENERIC_IDF_H
  24 #define LLVM_SUPPORT_GENERIC_IDF_H
  25
  26 #include "llvm/ADT/DenseMap.h"
  27 #include "llvm/ADT/SmallPtrSet.h"
  28 #include "llvm/ADT/SmallVector.h"
  29 #include "llvm/Support/GenericDomTree.h"
  30 #include <queue>
  31
  32 namespace llvm {
  33
  34 namespace IDFCalculatorDetail {
  35
  36 /// Generic utility class used for getting the children of a basic block.
  37 /// May be specialized if, for example, one wouldn't like to return nullpointer
  38 /// successors.
  39 template <class NodeTy, bool IsPostDom> struct ChildrenGetterTy {
  40   using NodeRef = typename GraphTraits<NodeTy>::NodeRef;
  41   using ChildrenTy = SmallVector<NodeRef, 8>;
  42
  43   ChildrenTy get(const NodeRef &N);
  44 };
  45
  46 } // end of namespace IDFCalculatorDetail
  47
  48 /// Determine the iterated dominance frontier, given a set of defining
  49 /// blocks, and optionally, a set of live-in blocks.
  50 ///
  51 /// In turn, the results can be used to place phi nodes.
  52 ///
  53 /// This algorithm is a linear time computation of Iterated Dominance Frontiers,
  54 /// pruned using the live-in set.
  55 /// By default, liveness is not used to prune the IDF computation.
  56 /// The template parameters should be of a CFG block type.
  57 template <class NodeTy, bool IsPostDom> class IDFCalculatorBase {
  58 public:
  59   using OrderedNodeTy =
  60       typename std::conditional<IsPostDom, Inverse<NodeTy *>, NodeTy *>::type;
  61   using ChildrenGetterTy =
  62       IDFCalculatorDetail::ChildrenGetterTy<NodeTy, IsPostDom>;
  63
  64   IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {}
  65
  66   IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT,
  67                     const ChildrenGetterTy &C)
  68       : DT(DT), ChildrenGetter(C) {}
  69
  70   /// Give the IDF calculator the set of blocks in which the value is
  71   /// defined.  This is equivalent to the set of starting blocks it should be
  72   /// calculating the IDF for (though later gets pruned based on liveness).
  73   ///
  74   /// Note: This set *must* live for the entire lifetime of the IDF calculator.
  75   void setDefiningBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
  76     DefBlocks = &Blocks;
  77   }
  78
  79   /// Give the IDF calculator the set of blocks in which the value is
  80   /// live on entry to the block.   This is used to prune the IDF calculation to
  81   /// not include blocks where any phi insertion would be dead.
  82   ///
  83   /// Note: This set *must* live for the entire lifetime of the IDF calculator.
  84   void setLiveInBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
  85     LiveInBlocks = &Blocks;
  86     useLiveIn = true;
  87   }
  88
  89   /// Reset the live-in block set to be empty, and tell the IDF
  90   /// calculator to not use liveness anymore.
  91   void resetLiveInBlocks() {
  92     LiveInBlocks = nullptr;
  93     useLiveIn = false;
  94   }
  95
  96   /// Calculate iterated dominance frontiers
  97   ///
  98   /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in
  99   /// the file-level comment.  It performs DF->IDF pruning using the live-in
 100   /// set, to avoid computing the IDF for blocks where an inserted PHI node
 101   /// would be dead.
 102   void calculate(SmallVectorImpl<NodeTy *> &IDFBlocks);
 103
 104 private:
 105   DominatorTreeBase<NodeTy, IsPostDom> &DT;
 106   ChildrenGetterTy ChildrenGetter;
 107   bool useLiveIn = false;
 108   const SmallPtrSetImpl<NodeTy *> *LiveInBlocks;
 109   const SmallPtrSetImpl<NodeTy *> *DefBlocks;
 110 };
 111
 112 //===----------------------------------------------------------------------===//
 113 // Implementation.
 114 //===----------------------------------------------------------------------===//
 115
 116 namespace IDFCalculatorDetail {
 117
 118 template <class NodeTy, bool IsPostDom>
 119 typename ChildrenGetterTy<NodeTy, IsPostDom>::ChildrenTy
 120 ChildrenGetterTy<NodeTy, IsPostDom>::get(const NodeRef &N) {
 121   using OrderedNodeTy =
 122       typename IDFCalculatorBase<NodeTy, IsPostDom>::OrderedNodeTy;
 123
 124   auto Children = children<OrderedNodeTy>(N);
 125   return {Children.begin(), Children.end()};
 126 }
 127
 128 } // end of namespace IDFCalculatorDetail
 129
 130 template <class NodeTy, bool IsPostDom>
 131 void IDFCalculatorBase<NodeTy, IsPostDom>::calculate(
 132     SmallVectorImpl<NodeTy *> &PHIBlocks) {
 133   // Use a priority queue keyed on dominator tree level so that inserted nodes
 134   // are handled from the bottom of the dominator tree upwards. We also augment
 135   // the level with a DFS number to ensure that the blocks are ordered in a
 136   // deterministic way.
 137   using DomTreeNodePair =
 138       std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>;
 139   using IDFPriorityQueue =
 140       std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
 141                           less_second>;
 142
 143   IDFPriorityQueue PQ;
 144
 145   DT.updateDFSNumbers();
 146
 147   for (NodeTy *BB : *DefBlocks) {
 148     if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB))
 149       PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
 150   }
 151
 152   SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist;
 153   SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedPQ;
 154   SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedWorklist;
 155
 156   while (!PQ.empty()) {
 157     DomTreeNodePair RootPair = PQ.top();
 158     PQ.pop();
 159     DomTreeNodeBase<NodeTy> *Root = RootPair.first;
 160     unsigned RootLevel = RootPair.second.first;
 161
 162     // Walk all dominator tree children of Root, inspecting their CFG edges with
 163     // targets elsewhere on the dominator tree. Only targets whose level is at
 164     // most Root's level are added to the iterated dominance frontier of the
 165     // definition set.
 166
 167     Worklist.clear();
 168     Worklist.push_back(Root);
 169     VisitedWorklist.insert(Root);
 170
 171     while (!Worklist.empty()) {
 172       DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val();
 173       NodeTy *BB = Node->getBlock();
 174       // Succ is the successor in the direction we are calculating IDF, so it is
 175       // successor for IDF, and predecessor for Reverse IDF.
 176       auto DoWork = [&](NodeTy *Succ) {
 177         DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ);
 178
 179         const unsigned SuccLevel = SuccNode->getLevel();
 180         if (SuccLevel > RootLevel)
 181           return;
 182
 183         if (!VisitedPQ.insert(SuccNode).second)
 184           return;
 185
 186         NodeTy *SuccBB = SuccNode->getBlock();
 187         if (useLiveIn && !LiveInBlocks->count(SuccBB))
 188           return;
 189
 190         PHIBlocks.emplace_back(SuccBB);
 191         if (!DefBlocks->count(SuccBB))
 192           PQ.push(std::make_pair(
 193               SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
 194       };
 195
 196       for (auto Succ : ChildrenGetter.get(BB))
 197         DoWork(Succ);
 198
 199       for (auto DomChild : *Node) {
 200         if (VisitedWorklist.insert(DomChild).second)
 201           Worklist.push_back(DomChild);
 202       }
 203     }
 204   }
 205 }
 206
 207 } // end of namespace llvm
 208
 209 #endif