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, bool IsPostDom>
calculate(SmallVectorImpl<BasicBlock * > & PHIBlocks)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 for (auto *Succ : children<NodeTy>(BB)) {
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 continue;
71
72 const unsigned SuccLevel = SuccNode->getLevel();
73 if (SuccLevel > RootLevel)
74 continue;
75
76 if (!VisitedPQ.insert(SuccNode).second)
77 continue;
78
79 BasicBlock *SuccBB = SuccNode->getBlock();
80 if (useLiveIn && !LiveInBlocks->count(SuccBB))
81 continue;
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 for (auto DomChild : *Node) {
90 if (VisitedWorklist.insert(DomChild).second)
91 Worklist.push_back(DomChild);
92 }
93 }
94 }
95 }
96
97 template class IDFCalculator<BasicBlock *, false>;
98 template class IDFCalculator<Inverse<BasicBlock *>, true>;
99 }
100