LLVM  15.0.0git
DominanceFrontierImpl.h
Go to the documentation of this file.
1 //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//
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 // This is the generic implementation of the DominanceFrontier class, which
10 // calculate and holds the dominance frontier for a function for.
11 //
12 // This should be considered deprecated, don't add any more uses of this data
13 // structure.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
18 #define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
19 
20 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/Config/llvm-config.h"
23 #include "llvm/Support/Debug.h"
26 #include <cassert>
27 #include <set>
28 #include <utility>
29 #include <vector>
30 
31 namespace llvm {
32 
33 template <class BlockT>
35 public:
37 
38  DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
39  const DomTreeNodeT *PN)
40  : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
41 
42  BlockT *currentBB;
43  BlockT *parentBB;
46 };
47 
48 template <class BlockT, bool IsPostDom>
50  assert(find(BB) != end() && "Block is not in DominanceFrontier!");
51  for (iterator I = begin(), E = end(); I != E; ++I)
52  I->second.erase(BB);
53  Frontiers.erase(BB);
54 }
55 
56 template <class BlockT, bool IsPostDom>
58  BlockT *Node) {
59  assert(I != end() && "BB is not in DominanceFrontier!");
60  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
61  I->second.erase(Node);
62 }
63 
64 template <class BlockT, bool IsPostDom>
66  iterator I, BlockT *Node) {
67  assert(I != end() && "BB is not in DominanceFrontier!");
68  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
69  I->second.erase(Node);
70 }
71 
72 template <class BlockT, bool IsPostDom>
74  DomSetType &DS1, const DomSetType &DS2) const {
75  std::set<BlockT *> tmpSet;
76  for (BlockT *BB : DS2)
77  tmpSet.insert(BB);
78 
79  for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end();
80  I != E;) {
81  BlockT *Node = *I++;
82 
83  if (tmpSet.erase(Node) == 0)
84  // Node is in DS1 but tnot in DS2.
85  return true;
86  }
87 
88  if (!tmpSet.empty()) {
89  // There are nodes that are in DS2 but not in DS1.
90  return true;
91  }
92 
93  // DS1 and DS2 matches.
94  return false;
95 }
96 
97 template <class BlockT, bool IsPostDom>
100  DomSetMapType tmpFrontiers;
101  for (typename DomSetMapType::const_iterator I = Other.begin(),
102  E = Other.end();
103  I != E; ++I)
104  tmpFrontiers.insert(std::make_pair(I->first, I->second));
105 
106  for (typename DomSetMapType::iterator I = tmpFrontiers.begin(),
107  E = tmpFrontiers.end();
108  I != E;) {
109  BlockT *Node = I->first;
110  const_iterator DFI = find(Node);
111  if (DFI == end())
112  return true;
113 
114  if (compareDomSet(I->second, DFI->second))
115  return true;
116 
117  ++I;
118  tmpFrontiers.erase(Node);
119  }
120 
121  if (!tmpFrontiers.empty())
122  return true;
123 
124  return false;
125 }
126 
127 template <class BlockT, bool IsPostDom>
129  for (const_iterator I = begin(), E = end(); I != E; ++I) {
130  OS << " DomFrontier for BB ";
131  if (I->first)
132  I->first->printAsOperand(OS, false);
133  else
134  OS << " <<exit node>>";
135  OS << " is:\t";
136 
137  const std::set<BlockT *> &BBs = I->second;
138 
139  for (const BlockT *BB : BBs) {
140  OS << ' ';
141  if (BB)
142  BB->printAsOperand(OS, false);
143  else
144  OS << "<<exit node>>";
145  }
146  OS << '\n';
147  }
148 }
149 
150 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
151 template <class BlockT, bool IsPostDom>
153  print(dbgs());
154 }
155 #endif
156 
157 template <class BlockT>
160  const DomTreeNodeT *Node) {
161  BlockT *BB = Node->getBlock();
162  DomSetType *Result = nullptr;
163 
164  std::vector<DFCalculateWorkObject<BlockT>> workList;
166 
167  workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
168  do {
169  DFCalculateWorkObject<BlockT> *currentW = &workList.back();
170  assert(currentW && "Missing work object.");
171 
172  BlockT *currentBB = currentW->currentBB;
173  BlockT *parentBB = currentW->parentBB;
174  const DomTreeNodeT *currentNode = currentW->Node;
175  const DomTreeNodeT *parentNode = currentW->parentNode;
176  assert(currentBB && "Invalid work object. Missing current Basic Block");
177  assert(currentNode && "Invalid work object. Missing current Node");
178  DomSetType &S = this->Frontiers[currentBB];
179 
180  // Visit each block only once.
181  if (visited.insert(currentBB).second) {
182  // Loop over CFG successors to calculate DFlocal[currentNode]
183  for (const auto Succ : children<BlockT *>(currentBB)) {
184  // Does Node immediately dominate this successor?
185  if (DT[Succ]->getIDom() != currentNode)
186  S.insert(Succ);
187  }
188  }
189 
190  // At this point, S is DFlocal. Now we union in DFup's of our children...
191  // Loop through and visit the nodes that Node immediately dominates (Node's
192  // children in the IDomTree)
193  bool visitChild = false;
194  for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
195  NE = currentNode->end();
196  NI != NE; ++NI) {
197  DomTreeNodeT *IDominee = *NI;
198  BlockT *childBB = IDominee->getBlock();
199  if (visited.count(childBB) == 0) {
200  workList.push_back(DFCalculateWorkObject<BlockT>(
201  childBB, currentBB, IDominee, currentNode));
202  visitChild = true;
203  }
204  }
205 
206  // If all children are visited or there is any child then pop this block
207  // from the workList.
208  if (!visitChild) {
209  if (!parentBB) {
210  Result = &S;
211  break;
212  }
213 
214  typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
215  DomSetType &parentSet = this->Frontiers[parentBB];
216  for (; CDFI != CDFE; ++CDFI) {
217  if (!DT.properlyDominates(parentNode, DT[*CDFI]))
218  parentSet.insert(*CDFI);
219  }
220  workList.pop_back();
221  }
222 
223  } while (!workList.empty());
224 
225  return *Result;
226 }
227 
228 } // end namespace llvm
229 
230 #endif // LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
DominanceFrontier.h
llvm::DFCalculateWorkObject::Node
const DomTreeNodeT * Node
Definition: DominanceFrontierImpl.h:44
llvm::AArch64CC::NE
@ NE
Definition: AArch64BaseInfo.h:256
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
llvm::DFCalculateWorkObject::parentBB
BlockT * parentBB
Definition: DominanceFrontierImpl.h:43
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::ForwardDominanceFrontierBase::DomSetType
typename DominanceFrontierBase< BlockT, false >::DomSetType DomSetType
Definition: DominanceFrontier.h:129
llvm::DominanceFrontierBase::dump
void dump() const
dump - Dump the dominance frontier to dbgs().
Definition: DominanceFrontierImpl.h:152
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::DominanceFrontierBase::compareDomSet
bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const
compareDomSet - Return false if two domsets match.
Definition: DominanceFrontierImpl.h:73
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::DFCalculateWorkObject::DFCalculateWorkObject
DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N, const DomTreeNodeT *PN)
Definition: DominanceFrontierImpl.h:38
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominanceFrontierBase< BasicBlock, false >::iterator
typename DomSetMapType::iterator iterator
Definition: DominanceFrontier.h:76
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
SmallPtrSet.h
llvm::DFCalculateWorkObject
Definition: DominanceFrontierImpl.h:34
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1637
llvm::DominanceFrontierBase::removeBlock
void removeBlock(BlockT *BB)
removeBlock - Remove basic block BB's frontier.
Definition: DominanceFrontierImpl.h:49
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::DFCalculateWorkObject::parentNode
const DomTreeNodeT * parentNode
Definition: DominanceFrontierImpl.h:45
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DominanceFrontierBase< BasicBlock, false >::const_iterator
typename DomSetMapType::const_iterator const_iterator
Definition: DominanceFrontier.h:77
llvm::DominanceFrontierBase
DominanceFrontierBase - Common base class for computing forward and inverse dominance frontiers for a...
Definition: DominanceFrontier.h:40
llvm::DominanceFrontierBase::print
void print(raw_ostream &OS) const
print - Convert to human readable form
Definition: DominanceFrontierImpl.h:128
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::DominanceFrontierBase::compare
bool compare(DominanceFrontierBase &Other) const
compare - Return true if the other dominance frontier base matches this dominance frontier base.
Definition: DominanceFrontierImpl.h:98
llvm::DomTreeNodeBase::begin
iterator begin()
Definition: GenericDomTree.h:75
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
llvm::DominatorTreeBase::properlyDominates
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Definition: GenericDomTree.h:392
Node
Definition: ItaniumDemangle.h:155
llvm::DomTreeNodeBase
Base class for the actual dominator tree node.
Definition: LiveIntervalCalc.h:24
GenericDomTree.h
llvm::DomTreeNodeBase::end
iterator end()
Definition: GenericDomTree.h:76
llvm::DominanceFrontierBase< BasicBlock, false >::DomSetType
std::set< BasicBlock * > DomSetType
Definition: DominanceFrontier.h:42
llvm::DomTreeNodeBase< BasicBlock >::const_iterator
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
Definition: GenericDomTree.h:73
llvm::ForwardDominanceFrontierBase::calculate
const DomSetType & calculate(const DomTreeT &DT, const DomTreeNodeT *Node)
Definition: DominanceFrontierImpl.h:159
N
#define N
llvm::DFCalculateWorkObject::currentBB
BlockT * currentBB
Definition: DominanceFrontierImpl.h:42
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::DominanceFrontierBase::removeFromFrontier
void removeFromFrontier(iterator I, BlockT *Node)
Definition: DominanceFrontierImpl.h:65
llvm::DominanceFrontierBase< BasicBlock, false >::DomSetMapType
std::map< BasicBlock *, DomSetType > DomSetMapType
Definition: DominanceFrontier.h:43
raw_ostream.h
Debug.h
llvm::DominanceFrontierBase::addToFrontier
void addToFrontier(iterator I, BlockT *Node)
Definition: DominanceFrontierImpl.h:57
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1236
llvm::SmallPtrSetImpl::insert
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:365