LLVM  6.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.
25  typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
26  typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
27  less_second> IDFPriorityQueue;
28  IDFPriorityQueue PQ;
29 
30  for (BasicBlock *BB : *DefBlocks) {
31  if (DomTreeNode *Node = DT.getNode(BB))
32  PQ.push({Node, Node->getLevel()});
33  }
34 
37  SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
38 
39  while (!PQ.empty()) {
40  DomTreeNodePair RootPair = PQ.top();
41  PQ.pop();
42  DomTreeNode *Root = RootPair.first;
43  unsigned RootLevel = RootPair.second;
44 
45  // Walk all dominator tree children of Root, inspecting their CFG edges with
46  // targets elsewhere on the dominator tree. Only targets whose level is at
47  // most Root's level are added to the iterated dominance frontier of the
48  // definition set.
49 
50  Worklist.clear();
51  Worklist.push_back(Root);
52  VisitedWorklist.insert(Root);
53 
54  while (!Worklist.empty()) {
55  DomTreeNode *Node = Worklist.pop_back_val();
56  BasicBlock *BB = Node->getBlock();
57  // Succ is the successor in the direction we are calculating IDF, so it is
58  // successor for IDF, and predecessor for Reverse IDF.
59  for (auto *Succ : children<NodeTy>(BB)) {
60  DomTreeNode *SuccNode = DT.getNode(Succ);
61 
62  // Quickly skip all CFG edges that are also dominator tree edges instead
63  // of catching them below.
64  if (SuccNode->getIDom() == Node)
65  continue;
66 
67  const unsigned SuccLevel = SuccNode->getLevel();
68  if (SuccLevel > RootLevel)
69  continue;
70 
71  if (!VisitedPQ.insert(SuccNode).second)
72  continue;
73 
74  BasicBlock *SuccBB = SuccNode->getBlock();
75  if (useLiveIn && !LiveInBlocks->count(SuccBB))
76  continue;
77 
78  PHIBlocks.emplace_back(SuccBB);
79  if (!DefBlocks->count(SuccBB))
80  PQ.push(std::make_pair(SuccNode, SuccLevel));
81  }
82 
83  for (auto DomChild : *Node) {
84  if (VisitedWorklist.insert(DomChild).second)
85  Worklist.push_back(DomChild);
86  }
87  }
88  }
89 }
90 
92 template class IDFCalculator<Inverse<BasicBlock *>, true>;
93 }
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:611
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:864
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:656
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
Determine the iterated dominance frontier, given a set of defining blocks, and optionally, a set of live-in blocks.
unsigned getLevel() const