1 //===- IteratedDominanceFrontier.cpp - Compute IDF ------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Compute iterated dominance frontiers using a linear time algorithm.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/IteratedDominanceFrontier.h"
15 #include "llvm/IR/CFG.h"
16 #include "llvm/IR/Dominators.h"
20 template <class NodeTy>
21 void IDFCalculator<NodeTy>::calculate(
22 SmallVectorImpl<BasicBlock *> &PHIBlocks) {
23 // If we haven't computed dominator tree levels, do so now.
24 if (DomLevels.empty()) {
25 for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode());
27 DomLevels[*DFI] = DFI.getPathLength() - 1;
31 // Use a priority queue keyed on dominator tree level so that inserted nodes
32 // are handled from the bottom of the dominator tree upwards.
33 typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
34 typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
35 less_second> IDFPriorityQueue;
38 for (BasicBlock *BB : *DefBlocks) {
39 if (DomTreeNode *Node = DT.getNode(BB))
40 PQ.push(std::make_pair(Node, DomLevels.lookup(Node)));
43 SmallVector<DomTreeNode *, 32> Worklist;
44 SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
45 SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
48 DomTreeNodePair RootPair = PQ.top();
50 DomTreeNode *Root = RootPair.first;
51 unsigned RootLevel = RootPair.second;
53 // Walk all dominator tree children of Root, inspecting their CFG edges with
54 // targets elsewhere on the dominator tree. Only targets whose level is at
55 // most Root's level are added to the iterated dominance frontier of the
59 Worklist.push_back(Root);
60 VisitedWorklist.insert(Root);
62 while (!Worklist.empty()) {
63 DomTreeNode *Node = Worklist.pop_back_val();
64 BasicBlock *BB = Node->getBlock();
65 // Succ is the successor in the direction we are calculating IDF, so it is
66 // successor for IDF, and predecessor for Reverse IDF.
67 for (auto SuccIter = GraphTraits<NodeTy>::child_begin(BB),
68 End = GraphTraits<NodeTy>::child_end(BB);
69 SuccIter != End; ++SuccIter) {
70 BasicBlock *Succ = *SuccIter;
71 DomTreeNode *SuccNode = DT.getNode(Succ);
73 // Quickly skip all CFG edges that are also dominator tree edges instead
74 // of catching them below.
75 if (SuccNode->getIDom() == Node)
78 unsigned SuccLevel = DomLevels.lookup(SuccNode);
79 if (SuccLevel > RootLevel)
82 if (!VisitedPQ.insert(SuccNode).second)
85 BasicBlock *SuccBB = SuccNode->getBlock();
86 if (useLiveIn && !LiveInBlocks->count(SuccBB))
89 PHIBlocks.emplace_back(SuccBB);
90 if (!DefBlocks->count(SuccBB))
91 PQ.push(std::make_pair(SuccNode, SuccLevel));
94 for (auto DomChild : *Node) {
95 if (VisitedWorklist.insert(DomChild).second)
96 Worklist.push_back(DomChild);
102 template class IDFCalculator<BasicBlock *>;
103 template class IDFCalculator<Inverse<BasicBlock *>>;