lib/Analysis/IteratedDominanceFrontier.cpp

   1 //===- IteratedDominanceFrontier.cpp - Compute IDF ------------------------===//
   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 //
   9 // Compute iterated dominance frontiers using a linear time algorithm.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Analysis/IteratedDominanceFrontier.h"
  14 #include "llvm/IR/CFG.h"
  15 #include "llvm/IR/Dominators.h"
  16 #include <queue>
  17
  18 namespace llvm {
  19
  20 template <class NodeTy, bool IsPostDom>
  21 void IDFCalculator<NodeTy, IsPostDom>::calculate(
  22     SmallVectorImpl<BasicBlock *> &PHIBlocks) {
  23   // Use a priority queue keyed on dominator tree level so that inserted nodes
  24   // are handled from the bottom of the dominator tree upwards. We also augment
  25   // the level with a DFS number to ensure that the blocks are ordered in a
  26   // deterministic way.
  27   typedef std::pair<DomTreeNode *, std::pair<unsigned, unsigned>>
  28       DomTreeNodePair;
  29   typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
  30                               less_second> IDFPriorityQueue;
  31   IDFPriorityQueue PQ;
  32
  33   DT.updateDFSNumbers();
  34
  35   for (BasicBlock *BB : *DefBlocks) {
  36     if (DomTreeNode *Node = DT.getNode(BB))
  37       PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
  38   }
  39
  40   SmallVector<DomTreeNode *, 32> Worklist;
  41   SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
  42   SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
  43
  44   while (!PQ.empty()) {
  45     DomTreeNodePair RootPair = PQ.top();
  46     PQ.pop();
  47     DomTreeNode *Root = RootPair.first;
  48     unsigned RootLevel = RootPair.second.first;
  49
  50     // Walk all dominator tree children of Root, inspecting their CFG edges with
  51     // targets elsewhere on the dominator tree. Only targets whose level is at
  52     // most Root's level are added to the iterated dominance frontier of the
  53     // definition set.
  54
  55     Worklist.clear();
  56     Worklist.push_back(Root);
  57     VisitedWorklist.insert(Root);
  58
  59     while (!Worklist.empty()) {
  60       DomTreeNode *Node = Worklist.pop_back_val();
  61       BasicBlock *BB = Node->getBlock();
  62       // Succ is the successor in the direction we are calculating IDF, so it is
  63       // successor for IDF, and predecessor for Reverse IDF.
  64       auto DoWork = [&](BasicBlock *Succ) {
  65         DomTreeNode *SuccNode = DT.getNode(Succ);
  66
  67         // Quickly skip all CFG edges that are also dominator tree edges instead
  68         // of catching them below.
  69         if (SuccNode->getIDom() == Node)
  70           return;
  71
  72         const unsigned SuccLevel = SuccNode->getLevel();
  73         if (SuccLevel > RootLevel)
  74           return;
  75
  76         if (!VisitedPQ.insert(SuccNode).second)
  77           return;
  78
  79         BasicBlock *SuccBB = SuccNode->getBlock();
  80         if (useLiveIn && !LiveInBlocks->count(SuccBB))
  81           return;
  82
  83         PHIBlocks.emplace_back(SuccBB);
  84         if (!DefBlocks->count(SuccBB))
  85           PQ.push(std::make_pair(
  86               SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
  87       };
  88
  89       if (GD) {
  90         for (auto Pair : children<
  91                  std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, NodeTy>>(
  92                  {GD, BB}))
  93           DoWork(Pair.second);
  94       } else {
  95         for (auto *Succ : children<NodeTy>(BB))
  96           DoWork(Succ);
  97       }
  98
  99       for (auto DomChild : *Node) {
 100         if (VisitedWorklist.insert(DomChild).second)
 101           Worklist.push_back(DomChild);
 102       }
 103     }
 104   }
 105 }
 106
 107 template class IDFCalculator<BasicBlock *, false>;
 108 template class IDFCalculator<Inverse<BasicBlock *>, true>;
 109 }