LLVM  9.0.0svn
IteratedDominanceFrontier.cpp
Go to the documentation of this file.
1 //===- IteratedDominanceFrontier.cpp - Compute IDF ------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Compute iterated dominance frontiers using a linear time algorithm.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/IR/CFG.h"
15 #include "llvm/IR/Dominators.h"
16 #include <queue>
17 
18 namespace llvm {
19 
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  auto DoWork = [&](BasicBlock *Succ) {
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  return;
71 
72  const unsigned SuccLevel = SuccNode->getLevel();
73  if (SuccLevel > RootLevel)
74  return;
75 
76  if (!VisitedPQ.insert(SuccNode).second)
77  return;
78 
79  BasicBlock *SuccBB = SuccNode->getBlock();
80  if (useLiveIn && !LiveInBlocks->count(SuccBB))
81  return;
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  if (GD) {
90  for (auto Pair : children<
91  std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, NodeTy>>(
92  {GD, BB}))
93  DoWork(Pair.second);
94  } else {
95  for (auto *Succ : children<NodeTy>(BB))
96  DoWork(Succ);
97  }
98 
99  for (auto DomChild : *Node) {
100  if (VisitedWorklist.insert(DomChild).second)
101  Worklist.push_back(DomChild);
102  }
103  }
104  }
105 }
106 
108 template class IDFCalculator<Inverse<BasicBlock *>, true>;
109 }
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:121
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Function object to check whether the second component of a std::pair compares less than the second co...
Definition: STLExtras.h:967
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:57
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:370
Compute iterated dominance frontiers using a linear time algorithm.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
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:839
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:373
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:644
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Determine the iterated dominance frontier, given a set of defining blocks, and optionally, a set of live-in blocks.
unsigned getLevel() const