LLVM  7.0.0svn
IteratedDominanceFrontier.cpp
Go to the documentation of this file.
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 
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>
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 
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 
98 template class IDFCalculator<Inverse<BasicBlock *>, true>;
99 }
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Function object to check whether the second component of a std::pair compares less than the second co...
Definition: STLExtras.h:724
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree...
NodeT * getBlock() const
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
DomTreeNodeBase * getIDom() const
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
void calculate(SmallVectorImpl< BasicBlock *> &IDFBlocks)
Calculate iterated dominance frontiers.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:382
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:653
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:62
Determine the iterated dominance frontier, given a set of defining blocks, and optionally, a set of live-in blocks.
unsigned getLevel() const