xref: /freebsd/contrib/llvm-project/llvm/lib/IR/Dominators.cpp (revision 6966ac055c3b7a39266fb982493330df7a097997)
1 //===- Dominators.cpp - Dominator Calculation -----------------------------===//
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 file implements simple dominator construction algorithms for finding
10 // forward dominators.  Postdominators are available in libanalysis, but are not
11 // included in libvmcore, because it's not needed.  Forward dominators are
12 // needed to support the Verifier pass.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/IR/Dominators.h"
17 #include "llvm/ADT/DepthFirstIterator.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/Config/llvm-config.h"
20 #include "llvm/IR/CFG.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/PassManager.h"
24 #include "llvm/Support/CommandLine.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/GenericDomTreeConstruction.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include <algorithm>
29 using namespace llvm;
30 
31 bool llvm::VerifyDomInfo = false;
32 static cl::opt<bool, true>
33     VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden,
34                    cl::desc("Verify dominator info (time consuming)"));
35 
36 #ifdef EXPENSIVE_CHECKS
37 static constexpr bool ExpensiveChecksEnabled = true;
38 #else
39 static constexpr bool ExpensiveChecksEnabled = false;
40 #endif
41 
42 bool BasicBlockEdge::isSingleEdge() const {
43   const Instruction *TI = Start->getTerminator();
44   unsigned NumEdgesToEnd = 0;
45   for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
46     if (TI->getSuccessor(i) == End)
47       ++NumEdgesToEnd;
48     if (NumEdgesToEnd >= 2)
49       return false;
50   }
51   assert(NumEdgesToEnd == 1);
52   return true;
53 }
54 
55 //===----------------------------------------------------------------------===//
56 //  DominatorTree Implementation
57 //===----------------------------------------------------------------------===//
58 //
59 // Provide public access to DominatorTree information.  Implementation details
60 // can be found in Dominators.h, GenericDomTree.h, and
61 // GenericDomTreeConstruction.h.
62 //
63 //===----------------------------------------------------------------------===//
64 
65 template class llvm::DomTreeNodeBase<BasicBlock>;
66 template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
67 template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
68 
69 template class llvm::cfg::Update<BasicBlock *>;
70 
71 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
72     DomTreeBuilder::BBDomTree &DT);
73 template void
74 llvm::DomTreeBuilder::CalculateWithUpdates<DomTreeBuilder::BBDomTree>(
75     DomTreeBuilder::BBDomTree &DT, BBUpdates U);
76 
77 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
78     DomTreeBuilder::BBPostDomTree &DT);
79 // No CalculateWithUpdates<PostDomTree> instantiation, unless a usecase arises.
80 
81 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
82     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
83 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
84     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
85 
86 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
87     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
88 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
89     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
90 
91 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
92     DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates);
93 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
94     DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
95 
96 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
97     const DomTreeBuilder::BBDomTree &DT,
98     DomTreeBuilder::BBDomTree::VerificationLevel VL);
99 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
100     const DomTreeBuilder::BBPostDomTree &DT,
101     DomTreeBuilder::BBPostDomTree::VerificationLevel VL);
102 
103 bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
104                                FunctionAnalysisManager::Invalidator &) {
105   // Check whether the analysis, all analyses on functions, or the function's
106   // CFG have been preserved.
107   auto PAC = PA.getChecker<DominatorTreeAnalysis>();
108   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
109            PAC.preservedSet<CFGAnalyses>());
110 }
111 
112 // dominates - Return true if Def dominates a use in User. This performs
113 // the special checks necessary if Def and User are in the same basic block.
114 // Note that Def doesn't dominate a use in Def itself!
115 bool DominatorTree::dominates(const Instruction *Def,
116                               const Instruction *User) const {
117   const BasicBlock *UseBB = User->getParent();
118   const BasicBlock *DefBB = Def->getParent();
119 
120   // Any unreachable use is dominated, even if Def == User.
121   if (!isReachableFromEntry(UseBB))
122     return true;
123 
124   // Unreachable definitions don't dominate anything.
125   if (!isReachableFromEntry(DefBB))
126     return false;
127 
128   // An instruction doesn't dominate a use in itself.
129   if (Def == User)
130     return false;
131 
132   // The value defined by an invoke dominates an instruction only if it
133   // dominates every instruction in UseBB.
134   // A PHI is dominated only if the instruction dominates every possible use in
135   // the UseBB.
136   if (isa<InvokeInst>(Def) || isa<PHINode>(User))
137     return dominates(Def, UseBB);
138 
139   if (DefBB != UseBB)
140     return dominates(DefBB, UseBB);
141 
142   // Loop through the basic block until we find Def or User.
143   BasicBlock::const_iterator I = DefBB->begin();
144   for (; &*I != Def && &*I != User; ++I)
145     /*empty*/;
146 
147   return &*I == Def;
148 }
149 
150 // true if Def would dominate a use in any instruction in UseBB.
151 // note that dominates(Def, Def->getParent()) is false.
152 bool DominatorTree::dominates(const Instruction *Def,
153                               const BasicBlock *UseBB) const {
154   const BasicBlock *DefBB = Def->getParent();
155 
156   // Any unreachable use is dominated, even if DefBB == UseBB.
157   if (!isReachableFromEntry(UseBB))
158     return true;
159 
160   // Unreachable definitions don't dominate anything.
161   if (!isReachableFromEntry(DefBB))
162     return false;
163 
164   if (DefBB == UseBB)
165     return false;
166 
167   // Invoke results are only usable in the normal destination, not in the
168   // exceptional destination.
169   if (const auto *II = dyn_cast<InvokeInst>(Def)) {
170     BasicBlock *NormalDest = II->getNormalDest();
171     BasicBlockEdge E(DefBB, NormalDest);
172     return dominates(E, UseBB);
173   }
174 
175   return dominates(DefBB, UseBB);
176 }
177 
178 bool DominatorTree::dominates(const BasicBlockEdge &BBE,
179                               const BasicBlock *UseBB) const {
180   // If the BB the edge ends in doesn't dominate the use BB, then the
181   // edge also doesn't.
182   const BasicBlock *Start = BBE.getStart();
183   const BasicBlock *End = BBE.getEnd();
184   if (!dominates(End, UseBB))
185     return false;
186 
187   // Simple case: if the end BB has a single predecessor, the fact that it
188   // dominates the use block implies that the edge also does.
189   if (End->getSinglePredecessor())
190     return true;
191 
192   // The normal edge from the invoke is critical. Conceptually, what we would
193   // like to do is split it and check if the new block dominates the use.
194   // With X being the new block, the graph would look like:
195   //
196   //        DefBB
197   //          /\      .  .
198   //         /  \     .  .
199   //        /    \    .  .
200   //       /      \   |  |
201   //      A        X  B  C
202   //      |         \ | /
203   //      .          \|/
204   //      .      NormalDest
205   //      .
206   //
207   // Given the definition of dominance, NormalDest is dominated by X iff X
208   // dominates all of NormalDest's predecessors (X, B, C in the example). X
209   // trivially dominates itself, so we only have to find if it dominates the
210   // other predecessors. Since the only way out of X is via NormalDest, X can
211   // only properly dominate a node if NormalDest dominates that node too.
212   int IsDuplicateEdge = 0;
213   for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
214        PI != E; ++PI) {
215     const BasicBlock *BB = *PI;
216     if (BB == Start) {
217       // If there are multiple edges between Start and End, by definition they
218       // can't dominate anything.
219       if (IsDuplicateEdge++)
220         return false;
221       continue;
222     }
223 
224     if (!dominates(End, BB))
225       return false;
226   }
227   return true;
228 }
229 
230 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
231   Instruction *UserInst = cast<Instruction>(U.getUser());
232   // A PHI in the end of the edge is dominated by it.
233   PHINode *PN = dyn_cast<PHINode>(UserInst);
234   if (PN && PN->getParent() == BBE.getEnd() &&
235       PN->getIncomingBlock(U) == BBE.getStart())
236     return true;
237 
238   // Otherwise use the edge-dominates-block query, which
239   // handles the crazy critical edge cases properly.
240   const BasicBlock *UseBB;
241   if (PN)
242     UseBB = PN->getIncomingBlock(U);
243   else
244     UseBB = UserInst->getParent();
245   return dominates(BBE, UseBB);
246 }
247 
248 bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
249   Instruction *UserInst = cast<Instruction>(U.getUser());
250   const BasicBlock *DefBB = Def->getParent();
251 
252   // Determine the block in which the use happens. PHI nodes use
253   // their operands on edges; simulate this by thinking of the use
254   // happening at the end of the predecessor block.
255   const BasicBlock *UseBB;
256   if (PHINode *PN = dyn_cast<PHINode>(UserInst))
257     UseBB = PN->getIncomingBlock(U);
258   else
259     UseBB = UserInst->getParent();
260 
261   // Any unreachable use is dominated, even if Def == User.
262   if (!isReachableFromEntry(UseBB))
263     return true;
264 
265   // Unreachable definitions don't dominate anything.
266   if (!isReachableFromEntry(DefBB))
267     return false;
268 
269   // Invoke instructions define their return values on the edges to their normal
270   // successors, so we have to handle them specially.
271   // Among other things, this means they don't dominate anything in
272   // their own block, except possibly a phi, so we don't need to
273   // walk the block in any case.
274   if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
275     BasicBlock *NormalDest = II->getNormalDest();
276     BasicBlockEdge E(DefBB, NormalDest);
277     return dominates(E, U);
278   }
279 
280   // If the def and use are in different blocks, do a simple CFG dominator
281   // tree query.
282   if (DefBB != UseBB)
283     return dominates(DefBB, UseBB);
284 
285   // Ok, def and use are in the same block. If the def is an invoke, it
286   // doesn't dominate anything in the block. If it's a PHI, it dominates
287   // everything in the block.
288   if (isa<PHINode>(UserInst))
289     return true;
290 
291   // Otherwise, just loop through the basic block until we find Def or User.
292   BasicBlock::const_iterator I = DefBB->begin();
293   for (; &*I != Def && &*I != UserInst; ++I)
294     /*empty*/;
295 
296   return &*I != UserInst;
297 }
298 
299 bool DominatorTree::isReachableFromEntry(const Use &U) const {
300   Instruction *I = dyn_cast<Instruction>(U.getUser());
301 
302   // ConstantExprs aren't really reachable from the entry block, but they
303   // don't need to be treated like unreachable code either.
304   if (!I) return true;
305 
306   // PHI nodes use their operands on their incoming edges.
307   if (PHINode *PN = dyn_cast<PHINode>(I))
308     return isReachableFromEntry(PN->getIncomingBlock(U));
309 
310   // Everything else uses their operands in their own block.
311   return isReachableFromEntry(I->getParent());
312 }
313 
314 //===----------------------------------------------------------------------===//
315 //  DominatorTreeAnalysis and related pass implementations
316 //===----------------------------------------------------------------------===//
317 //
318 // This implements the DominatorTreeAnalysis which is used with the new pass
319 // manager. It also implements some methods from utility passes.
320 //
321 //===----------------------------------------------------------------------===//
322 
323 DominatorTree DominatorTreeAnalysis::run(Function &F,
324                                          FunctionAnalysisManager &) {
325   DominatorTree DT;
326   DT.recalculate(F);
327   return DT;
328 }
329 
330 AnalysisKey DominatorTreeAnalysis::Key;
331 
332 DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
333 
334 PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
335                                                 FunctionAnalysisManager &AM) {
336   OS << "DominatorTree for function: " << F.getName() << "\n";
337   AM.getResult<DominatorTreeAnalysis>(F).print(OS);
338 
339   return PreservedAnalyses::all();
340 }
341 
342 PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
343                                                  FunctionAnalysisManager &AM) {
344   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
345   assert(DT.verify());
346   (void)DT;
347   return PreservedAnalyses::all();
348 }
349 
350 //===----------------------------------------------------------------------===//
351 //  DominatorTreeWrapperPass Implementation
352 //===----------------------------------------------------------------------===//
353 //
354 // The implementation details of the wrapper pass that holds a DominatorTree
355 // suitable for use with the legacy pass manager.
356 //
357 //===----------------------------------------------------------------------===//
358 
359 char DominatorTreeWrapperPass::ID = 0;
360 INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
361                 "Dominator Tree Construction", true, true)
362 
363 bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
364   DT.recalculate(F);
365   return false;
366 }
367 
368 void DominatorTreeWrapperPass::verifyAnalysis() const {
369   if (VerifyDomInfo)
370     assert(DT.verify(DominatorTree::VerificationLevel::Full));
371   else if (ExpensiveChecksEnabled)
372     assert(DT.verify(DominatorTree::VerificationLevel::Basic));
373 }
374 
375 void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
376   DT.print(OS);
377 }
378 
379