LLVM  14.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/GraphTraits.h"
21 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/Config/llvm-config.h"
24 #include "llvm/Support/Debug.h"
27 #include <cassert>
28 #include <set>
29 #include <utility>
30 #include <vector>
31 
32 namespace llvm {
33 
34 template <class BlockT>
36 public:
38 
39  DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
40  const DomTreeNodeT *PN)
41  : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
42 
43  BlockT *currentBB;
44  BlockT *parentBB;
47 };
48 
49 template <class BlockT, bool IsPostDom>
51  assert(find(BB) != end() && "Block is not in DominanceFrontier!");
52  for (iterator I = begin(), E = end(); I != E; ++I)
53  I->second.erase(BB);
54  Frontiers.erase(BB);
55 }
56 
57 template <class BlockT, bool IsPostDom>
59  BlockT *Node) {
60  assert(I != end() && "BB is not in DominanceFrontier!");
61  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
62  I->second.erase(Node);
63 }
64 
65 template <class BlockT, bool IsPostDom>
67  iterator I, BlockT *Node) {
68  assert(I != end() && "BB is not in DominanceFrontier!");
69  assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
70  I->second.erase(Node);
71 }
72 
73 template <class BlockT, bool IsPostDom>
75  DomSetType &DS1, const DomSetType &DS2) const {
76  std::set<BlockT *> tmpSet;
77  for (BlockT *BB : DS2)
78  tmpSet.insert(BB);
79 
80  for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end();
81  I != E;) {
82  BlockT *Node = *I++;
83 
84  if (tmpSet.erase(Node) == 0)
85  // Node is in DS1 but tnot in DS2.
86  return true;
87  }
88 
89  if (!tmpSet.empty()) {
90  // There are nodes that are in DS2 but not in DS1.
91  return true;
92  }
93 
94  // DS1 and DS2 matches.
95  return false;
96 }
97 
98 template <class BlockT, bool IsPostDom>
101  DomSetMapType tmpFrontiers;
102  for (typename DomSetMapType::const_iterator I = Other.begin(),
103  E = Other.end();
104  I != E; ++I)
105  tmpFrontiers.insert(std::make_pair(I->first, I->second));
106 
107  for (typename DomSetMapType::iterator I = tmpFrontiers.begin(),
108  E = tmpFrontiers.end();
109  I != E;) {
110  BlockT *Node = I->first;
111  const_iterator DFI = find(Node);
112  if (DFI == end())
113  return true;
114 
115  if (compareDomSet(I->second, DFI->second))
116  return true;
117 
118  ++I;
119  tmpFrontiers.erase(Node);
120  }
121 
122  if (!tmpFrontiers.empty())
123  return true;
124 
125  return false;
126 }
127 
128 template <class BlockT, bool IsPostDom>
130  for (const_iterator I = begin(), E = end(); I != E; ++I) {
131  OS << " DomFrontier for BB ";
132  if (I->first)
133  I->first->printAsOperand(OS, false);
134  else
135  OS << " <<exit node>>";
136  OS << " is:\t";
137 
138  const std::set<BlockT *> &BBs = I->second;
139 
140  for (const BlockT *BB : BBs) {
141  OS << ' ';
142  if (BB)
143  BB->printAsOperand(OS, false);
144  else
145  OS << "<<exit node>>";
146  }
147  OS << '\n';
148  }
149 }
150 
151 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
152 template <class BlockT, bool IsPostDom>
154  print(dbgs());
155 }
156 #endif
157 
158 template <class BlockT>
161  const DomTreeNodeT *Node) {
162  BlockT *BB = Node->getBlock();
163  DomSetType *Result = nullptr;
164 
165  std::vector<DFCalculateWorkObject<BlockT>> workList;
167 
168  workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
169  do {
170  DFCalculateWorkObject<BlockT> *currentW = &workList.back();
171  assert(currentW && "Missing work object.");
172 
173  BlockT *currentBB = currentW->currentBB;
174  BlockT *parentBB = currentW->parentBB;
175  const DomTreeNodeT *currentNode = currentW->Node;
176  const DomTreeNodeT *parentNode = currentW->parentNode;
177  assert(currentBB && "Invalid work object. Missing current Basic Block");
178  assert(currentNode && "Invalid work object. Missing current Node");
179  DomSetType &S = this->Frontiers[currentBB];
180 
181  // Visit each block only once.
182  if (visited.insert(currentBB).second) {
183  // Loop over CFG successors to calculate DFlocal[currentNode]
184  for (const auto Succ : children<BlockT *>(currentBB)) {
185  // Does Node immediately dominate this successor?
186  if (DT[Succ]->getIDom() != currentNode)
187  S.insert(Succ);
188  }
189  }
190 
191  // At this point, S is DFlocal. Now we union in DFup's of our children...
192  // Loop through and visit the nodes that Node immediately dominates (Node's
193  // children in the IDomTree)
194  bool visitChild = false;
195  for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
196  NE = currentNode->end();
197  NI != NE; ++NI) {
198  DomTreeNodeT *IDominee = *NI;
199  BlockT *childBB = IDominee->getBlock();
200  if (visited.count(childBB) == 0) {
201  workList.push_back(DFCalculateWorkObject<BlockT>(
202  childBB, currentBB, IDominee, currentNode));
203  visitChild = true;
204  }
205  }
206 
207  // If all children are visited or there is any child then pop this block
208  // from the workList.
209  if (!visitChild) {
210  if (!parentBB) {
211  Result = &S;
212  break;
213  }
214 
215  typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
216  DomSetType &parentSet = this->Frontiers[parentBB];
217  for (; CDFI != CDFE; ++CDFI) {
218  if (!DT.properlyDominates(parentNode, DT[*CDFI]))
219  parentSet.insert(*CDFI);
220  }
221  workList.pop_back();
222  }
223 
224  } while (!workList.empty());
225 
226  return *Result;
227 }
228 
229 } // end namespace llvm
230 
231 #endif // LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
DominanceFrontier.h
llvm::DFCalculateWorkObject::Node
const DomTreeNodeT * Node
Definition: DominanceFrontierImpl.h:45
llvm::AArch64CC::NE
@ NE
Definition: AArch64BaseInfo.h:256
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
llvm::DFCalculateWorkObject::parentBB
BlockT * parentBB
Definition: DominanceFrontierImpl.h:44
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:153
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
llvm::DominanceFrontierBase::compareDomSet
bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const
compareDomSet - Return false if two domsets match.
Definition: DominanceFrontierImpl.h:74
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::DFCalculateWorkObject::DFCalculateWorkObject
DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N, const DomTreeNodeT *PN)
Definition: DominanceFrontierImpl.h:39
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
GraphTraits.h
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:53
SmallPtrSet.h
llvm::DFCalculateWorkObject
Definition: DominanceFrontierImpl.h:35
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:1567
llvm::DominanceFrontierBase::removeBlock
void removeBlock(BlockT *BB)
removeBlock - Remove basic block BB's frontier.
Definition: DominanceFrontierImpl.h:50
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::DFCalculateWorkObject::parentNode
const DomTreeNodeT * parentNode
Definition: DominanceFrontierImpl.h:46
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:129
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:382
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:99
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:234
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:160
N
#define N
llvm::DFCalculateWorkObject::currentBB
BlockT * currentBB
Definition: DominanceFrontierImpl.h:43
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:66
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:58
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1172
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:364