contrib/llvm/lib/Analysis/IteratedDominanceFrontier.cpp

   1 //===- IteratedDominanceFrontier.cpp - Compute IDF ------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Compute iterated dominance frontiers using a linear time algorithm.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/IteratedDominanceFrontier.h"
  15 #include "llvm/IR/CFG.h"
  16 #include "llvm/IR/Dominators.h"
  17 #include <queue>
  18
  19 namespace llvm {
  20 template <class NodeTy>
  21 void IDFCalculator<NodeTy>::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.
  25   typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
  26   typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
  27                               less_second> IDFPriorityQueue;
  28   IDFPriorityQueue PQ;
  29
  30   for (BasicBlock *BB : *DefBlocks) {
  31     if (DomTreeNode *Node = DT.getNode(BB))
  32       PQ.push({Node, Node->getLevel()});
  33   }
  34
  35   SmallVector<DomTreeNode *, 32> Worklist;
  36   SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
  37   SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
  38
  39   while (!PQ.empty()) {
  40     DomTreeNodePair RootPair = PQ.top();
  41     PQ.pop();
  42     DomTreeNode *Root = RootPair.first;
  43     unsigned RootLevel = RootPair.second;
  44
  45     // Walk all dominator tree children of Root, inspecting their CFG edges with
  46     // targets elsewhere on the dominator tree. Only targets whose level is at
  47     // most Root's level are added to the iterated dominance frontier of the
  48     // definition set.
  49
  50     Worklist.clear();
  51     Worklist.push_back(Root);
  52     VisitedWorklist.insert(Root);
  53
  54     while (!Worklist.empty()) {
  55       DomTreeNode *Node = Worklist.pop_back_val();
  56       BasicBlock *BB = Node->getBlock();
  57       // Succ is the successor in the direction we are calculating IDF, so it is
  58       // successor for IDF, and predecessor for Reverse IDF.
  59       for (auto *Succ : children<NodeTy>(BB)) {
  60         DomTreeNode *SuccNode = DT.getNode(Succ);
  61
  62         // Quickly skip all CFG edges that are also dominator tree edges instead
  63         // of catching them below.
  64         if (SuccNode->getIDom() == Node)
  65           continue;
  66
  67         const unsigned SuccLevel = SuccNode->getLevel();
  68         if (SuccLevel > RootLevel)
  69           continue;
  70
  71         if (!VisitedPQ.insert(SuccNode).second)
  72           continue;
  73
  74         BasicBlock *SuccBB = SuccNode->getBlock();
  75         if (useLiveIn && !LiveInBlocks->count(SuccBB))
  76           continue;
  77
  78         PHIBlocks.emplace_back(SuccBB);
  79         if (!DefBlocks->count(SuccBB))
  80           PQ.push(std::make_pair(SuccNode, SuccLevel));
  81       }
  82
  83       for (auto DomChild : *Node) {
  84         if (VisitedWorklist.insert(DomChild).second)
  85           Worklist.push_back(DomChild);
  86       }
  87     }
  88   }
  89 }
  90
  91 template class IDFCalculator<BasicBlock *>;
  92 template class IDFCalculator<Inverse<BasicBlock *>>;
  93 }