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  const unsigned SuccLevel = SuccNode->getLevel();
68  if (SuccLevel > RootLevel)
69  return;
70 
71  if (!VisitedPQ.insert(SuccNode).second)
72  return;
73 
74  BasicBlock *SuccBB = SuccNode->getBlock();
75  if (useLiveIn && !LiveInBlocks->count(SuccBB))
76  return;
77 
78  PHIBlocks.emplace_back(SuccBB);
79  if (!DefBlocks->count(SuccBB))
80  PQ.push(std::make_pair(
81  SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
82  };
83 
84  if (GD) {
85  for (auto Pair : children<
86  std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, NodeTy>>(
87  {GD, BB}))
88  DoWork(Pair.second);
89  } else {
90  for (auto *Succ : children<NodeTy>(BB))
91  DoWork(Succ);
92  }
93 
94  for (auto DomChild : *Node) {
95  if (VisitedWorklist.insert(DomChild).second)
96  Worklist.push_back(DomChild);
97  }
98  }
99  }
100 }
101 
103 template class IDFCalculator<Inverse<BasicBlock *>, true>;
104 }
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
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:974
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
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:837
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
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