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 /// \brief 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>
calculate(SmallVectorImpl<BasicBlock * > & PHIBlocks)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());
26 DFI != DFE; ++DFI) {
27 DomLevels[*DFI] = DFI.getPathLength() - 1;
28 }
29 }
30
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;
36 IDFPriorityQueue PQ;
37
38 for (BasicBlock *BB : *DefBlocks) {
39 if (DomTreeNode *Node = DT.getNode(BB))
40 PQ.push(std::make_pair(Node, DomLevels.lookup(Node)));
41 }
42
43 SmallVector<DomTreeNode *, 32> Worklist;
44 SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
45 SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
46
47 while (!PQ.empty()) {
48 DomTreeNodePair RootPair = PQ.top();
49 PQ.pop();
50 DomTreeNode *Root = RootPair.first;
51 unsigned RootLevel = RootPair.second;
52
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
56 // definition set.
57
58 Worklist.clear();
59 Worklist.push_back(Root);
60 VisitedWorklist.insert(Root);
61
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);
72
73 // Quickly skip all CFG edges that are also dominator tree edges instead
74 // of catching them below.
75 if (SuccNode->getIDom() == Node)
76 continue;
77
78 unsigned SuccLevel = DomLevels.lookup(SuccNode);
79 if (SuccLevel > RootLevel)
80 continue;
81
82 if (!VisitedPQ.insert(SuccNode).second)
83 continue;
84
85 BasicBlock *SuccBB = SuccNode->getBlock();
86 if (useLiveIn && !LiveInBlocks->count(SuccBB))
87 continue;
88
89 PHIBlocks.emplace_back(SuccBB);
90 if (!DefBlocks->count(SuccBB))
91 PQ.push(std::make_pair(SuccNode, SuccLevel));
92 }
93
94 for (auto DomChild : *Node) {
95 if (VisitedWorklist.insert(DomChild).second)
96 Worklist.push_back(DomChild);
97 }
98 }
99 }
100 }
101
102 template class IDFCalculator<BasicBlock *>;
103 template class IDFCalculator<Inverse<BasicBlock *>>;
104 }
105