LLVM  8.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 
21 template <class NodeTy, bool IsPostDom>
23  SmallVectorImpl<BasicBlock *> &PHIBlocks) {
24  // Use a priority queue keyed on dominator tree level so that inserted nodes
25  // are handled from the bottom of the dominator tree upwards. We also augment
26  // the level with a DFS number to ensure that the blocks are ordered in a
27  // deterministic way.
28  typedef std::pair<DomTreeNode *, std::pair<unsigned, unsigned>>
29  DomTreeNodePair;
30  typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
31  less_second> IDFPriorityQueue;
32  IDFPriorityQueue PQ;
33 
34  DT.updateDFSNumbers();
35 
36  for (BasicBlock *BB : *DefBlocks) {
37  if (DomTreeNode *Node = DT.getNode(BB))
38  PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
39  }
40 
43  SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
44 
45  while (!PQ.empty()) {
46  DomTreeNodePair RootPair = PQ.top();
47  PQ.pop();
48  DomTreeNode *Root = RootPair.first;
49  unsigned RootLevel = RootPair.second.first;
50 
51  // Walk all dominator tree children of Root, inspecting their CFG edges with
52  // targets elsewhere on the dominator tree. Only targets whose level is at
53  // most Root's level are added to the iterated dominance frontier of the
54  // definition set.
55 
56  Worklist.clear();
57  Worklist.push_back(Root);
58  VisitedWorklist.insert(Root);
59 
60  while (!Worklist.empty()) {
61  DomTreeNode *Node = Worklist.pop_back_val();
62  BasicBlock *BB = Node->getBlock();
63  // Succ is the successor in the direction we are calculating IDF, so it is
64  // successor for IDF, and predecessor for Reverse IDF.
65  auto DoWork = [&](BasicBlock *Succ) {
66  DomTreeNode *SuccNode = DT.getNode(Succ);
67 
68  // Quickly skip all CFG edges that are also dominator tree edges instead
69  // of catching them below.
70  if (SuccNode->getIDom() == Node)
71  return;
72 
73  const unsigned SuccLevel = SuccNode->getLevel();
74  if (SuccLevel > RootLevel)
75  return;
76 
77  if (!VisitedPQ.insert(SuccNode).second)
78  return;
79 
80  BasicBlock *SuccBB = SuccNode->getBlock();
81  if (useLiveIn && !LiveInBlocks->count(SuccBB))
82  return;
83 
84  PHIBlocks.emplace_back(SuccBB);
85  if (!DefBlocks->count(SuccBB))
86  PQ.push(std::make_pair(
87  SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
88  };
89 
90  if (GD) {
91  for (auto Pair : children<
92  std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, NodeTy>>(
93  {GD, BB}))
94  DoWork(Pair.second);
95  } else {
96  for (auto *Succ : children<NodeTy>(BB))
97  DoWork(Succ);
98  }
99 
100  for (auto DomChild : *Node) {
101  if (VisitedWorklist.insert(DomChild).second)
102  Worklist.push_back(DomChild);
103  }
104  }
105  }
106 }
107 
109 template class IDFCalculator<Inverse<BasicBlock *>, true>;
110 }
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:122
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:824
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:58
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:847
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:652
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
Determine the iterated dominance frontier, given a set of defining blocks, and optionally, a set of live-in blocks.
unsigned getLevel() const