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>
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