• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- Dominators.cpp - Dominator Calculation -----------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements simple dominator construction algorithms for finding
11 // forward dominators.  Postdominators are available in libanalysis, but are not
12 // included in libvmcore, because it's not needed.  Forward dominators are
13 // needed to support the Verifier pass.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/IR/Dominators.h"
18 #include "llvm/ADT/DepthFirstIterator.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/Config/llvm-config.h"
21 #include "llvm/IR/CFG.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/PassManager.h"
25 #include "llvm/Support/CommandLine.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/GenericDomTreeConstruction.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include <algorithm>
30 using namespace llvm;
31 
32 bool llvm::VerifyDomInfo = false;
33 static cl::opt<bool, true>
34     VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden,
35                    cl::desc("Verify dominator info (time consuming)"));
36 
37 #ifdef EXPENSIVE_CHECKS
38 static constexpr bool ExpensiveChecksEnabled = true;
39 #else
40 static constexpr bool ExpensiveChecksEnabled = false;
41 #endif
42 
isSingleEdge() const43 bool BasicBlockEdge::isSingleEdge() const {
44   const TerminatorInst *TI = Start->getTerminator();
45   unsigned NumEdgesToEnd = 0;
46   for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
47     if (TI->getSuccessor(i) == End)
48       ++NumEdgesToEnd;
49     if (NumEdgesToEnd >= 2)
50       return false;
51   }
52   assert(NumEdgesToEnd == 1);
53   return true;
54 }
55 
56 //===----------------------------------------------------------------------===//
57 //  DominatorTree Implementation
58 //===----------------------------------------------------------------------===//
59 //
60 // Provide public access to DominatorTree information.  Implementation details
61 // can be found in Dominators.h, GenericDomTree.h, and
62 // GenericDomTreeConstruction.h.
63 //
64 //===----------------------------------------------------------------------===//
65 
66 template class llvm::DomTreeNodeBase<BasicBlock>;
67 template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
68 template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
69 
70 template struct llvm::DomTreeBuilder::Update<BasicBlock *>;
71 
72 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
73     DomTreeBuilder::BBDomTree &DT);
74 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
75     DomTreeBuilder::BBPostDomTree &DT);
76 
77 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
78     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
79 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
80     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
81 
82 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
83     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
84 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
85     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
86 
87 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
88     DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates);
89 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
90     DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
91 
92 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
93     const DomTreeBuilder::BBDomTree &DT,
94     DomTreeBuilder::BBDomTree::VerificationLevel VL);
95 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
96     const DomTreeBuilder::BBPostDomTree &DT,
97     DomTreeBuilder::BBPostDomTree::VerificationLevel VL);
98 
invalidate(Function & F,const PreservedAnalyses & PA,FunctionAnalysisManager::Invalidator &)99 bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
100                                FunctionAnalysisManager::Invalidator &) {
101   // Check whether the analysis, all analyses on functions, or the function's
102   // CFG have been preserved.
103   auto PAC = PA.getChecker<DominatorTreeAnalysis>();
104   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
105            PAC.preservedSet<CFGAnalyses>());
106 }
107 
108 // dominates - Return true if Def dominates a use in User. This performs
109 // the special checks necessary if Def and User are in the same basic block.
110 // Note that Def doesn't dominate a use in Def itself!
dominates(const Instruction * Def,const Instruction * User) const111 bool DominatorTree::dominates(const Instruction *Def,
112                               const Instruction *User) const {
113   const BasicBlock *UseBB = User->getParent();
114   const BasicBlock *DefBB = Def->getParent();
115 
116   // Any unreachable use is dominated, even if Def == User.
117   if (!isReachableFromEntry(UseBB))
118     return true;
119 
120   // Unreachable definitions don't dominate anything.
121   if (!isReachableFromEntry(DefBB))
122     return false;
123 
124   // An instruction doesn't dominate a use in itself.
125   if (Def == User)
126     return false;
127 
128   // The value defined by an invoke dominates an instruction only if it
129   // dominates every instruction in UseBB.
130   // A PHI is dominated only if the instruction dominates every possible use in
131   // the UseBB.
132   if (isa<InvokeInst>(Def) || isa<PHINode>(User))
133     return dominates(Def, UseBB);
134 
135   if (DefBB != UseBB)
136     return dominates(DefBB, UseBB);
137 
138   // Loop through the basic block until we find Def or User.
139   BasicBlock::const_iterator I = DefBB->begin();
140   for (; &*I != Def && &*I != User; ++I)
141     /*empty*/;
142 
143   return &*I == Def;
144 }
145 
146 // true if Def would dominate a use in any instruction in UseBB.
147 // note that dominates(Def, Def->getParent()) is false.
dominates(const Instruction * Def,const BasicBlock * UseBB) const148 bool DominatorTree::dominates(const Instruction *Def,
149                               const BasicBlock *UseBB) const {
150   const BasicBlock *DefBB = Def->getParent();
151 
152   // Any unreachable use is dominated, even if DefBB == UseBB.
153   if (!isReachableFromEntry(UseBB))
154     return true;
155 
156   // Unreachable definitions don't dominate anything.
157   if (!isReachableFromEntry(DefBB))
158     return false;
159 
160   if (DefBB == UseBB)
161     return false;
162 
163   // Invoke results are only usable in the normal destination, not in the
164   // exceptional destination.
165   if (const auto *II = dyn_cast<InvokeInst>(Def)) {
166     BasicBlock *NormalDest = II->getNormalDest();
167     BasicBlockEdge E(DefBB, NormalDest);
168     return dominates(E, UseBB);
169   }
170 
171   return dominates(DefBB, UseBB);
172 }
173 
dominates(const BasicBlockEdge & BBE,const BasicBlock * UseBB) const174 bool DominatorTree::dominates(const BasicBlockEdge &BBE,
175                               const BasicBlock *UseBB) const {
176   // If the BB the edge ends in doesn't dominate the use BB, then the
177   // edge also doesn't.
178   const BasicBlock *Start = BBE.getStart();
179   const BasicBlock *End = BBE.getEnd();
180   if (!dominates(End, UseBB))
181     return false;
182 
183   // Simple case: if the end BB has a single predecessor, the fact that it
184   // dominates the use block implies that the edge also does.
185   if (End->getSinglePredecessor())
186     return true;
187 
188   // The normal edge from the invoke is critical. Conceptually, what we would
189   // like to do is split it and check if the new block dominates the use.
190   // With X being the new block, the graph would look like:
191   //
192   //        DefBB
193   //          /\      .  .
194   //         /  \     .  .
195   //        /    \    .  .
196   //       /      \   |  |
197   //      A        X  B  C
198   //      |         \ | /
199   //      .          \|/
200   //      .      NormalDest
201   //      .
202   //
203   // Given the definition of dominance, NormalDest is dominated by X iff X
204   // dominates all of NormalDest's predecessors (X, B, C in the example). X
205   // trivially dominates itself, so we only have to find if it dominates the
206   // other predecessors. Since the only way out of X is via NormalDest, X can
207   // only properly dominate a node if NormalDest dominates that node too.
208   int IsDuplicateEdge = 0;
209   for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
210        PI != E; ++PI) {
211     const BasicBlock *BB = *PI;
212     if (BB == Start) {
213       // If there are multiple edges between Start and End, by definition they
214       // can't dominate anything.
215       if (IsDuplicateEdge++)
216         return false;
217       continue;
218     }
219 
220     if (!dominates(End, BB))
221       return false;
222   }
223   return true;
224 }
225 
dominates(const BasicBlockEdge & BBE,const Use & U) const226 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
227   Instruction *UserInst = cast<Instruction>(U.getUser());
228   // A PHI in the end of the edge is dominated by it.
229   PHINode *PN = dyn_cast<PHINode>(UserInst);
230   if (PN && PN->getParent() == BBE.getEnd() &&
231       PN->getIncomingBlock(U) == BBE.getStart())
232     return true;
233 
234   // Otherwise use the edge-dominates-block query, which
235   // handles the crazy critical edge cases properly.
236   const BasicBlock *UseBB;
237   if (PN)
238     UseBB = PN->getIncomingBlock(U);
239   else
240     UseBB = UserInst->getParent();
241   return dominates(BBE, UseBB);
242 }
243 
dominates(const Instruction * Def,const Use & U) const244 bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
245   Instruction *UserInst = cast<Instruction>(U.getUser());
246   const BasicBlock *DefBB = Def->getParent();
247 
248   // Determine the block in which the use happens. PHI nodes use
249   // their operands on edges; simulate this by thinking of the use
250   // happening at the end of the predecessor block.
251   const BasicBlock *UseBB;
252   if (PHINode *PN = dyn_cast<PHINode>(UserInst))
253     UseBB = PN->getIncomingBlock(U);
254   else
255     UseBB = UserInst->getParent();
256 
257   // Any unreachable use is dominated, even if Def == User.
258   if (!isReachableFromEntry(UseBB))
259     return true;
260 
261   // Unreachable definitions don't dominate anything.
262   if (!isReachableFromEntry(DefBB))
263     return false;
264 
265   // Invoke instructions define their return values on the edges to their normal
266   // successors, so we have to handle them specially.
267   // Among other things, this means they don't dominate anything in
268   // their own block, except possibly a phi, so we don't need to
269   // walk the block in any case.
270   if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
271     BasicBlock *NormalDest = II->getNormalDest();
272     BasicBlockEdge E(DefBB, NormalDest);
273     return dominates(E, U);
274   }
275 
276   // If the def and use are in different blocks, do a simple CFG dominator
277   // tree query.
278   if (DefBB != UseBB)
279     return dominates(DefBB, UseBB);
280 
281   // Ok, def and use are in the same block. If the def is an invoke, it
282   // doesn't dominate anything in the block. If it's a PHI, it dominates
283   // everything in the block.
284   if (isa<PHINode>(UserInst))
285     return true;
286 
287   // Otherwise, just loop through the basic block until we find Def or User.
288   BasicBlock::const_iterator I = DefBB->begin();
289   for (; &*I != Def && &*I != UserInst; ++I)
290     /*empty*/;
291 
292   return &*I != UserInst;
293 }
294 
isReachableFromEntry(const Use & U) const295 bool DominatorTree::isReachableFromEntry(const Use &U) const {
296   Instruction *I = dyn_cast<Instruction>(U.getUser());
297 
298   // ConstantExprs aren't really reachable from the entry block, but they
299   // don't need to be treated like unreachable code either.
300   if (!I) return true;
301 
302   // PHI nodes use their operands on their incoming edges.
303   if (PHINode *PN = dyn_cast<PHINode>(I))
304     return isReachableFromEntry(PN->getIncomingBlock(U));
305 
306   // Everything else uses their operands in their own block.
307   return isReachableFromEntry(I->getParent());
308 }
309 
310 //===----------------------------------------------------------------------===//
311 //  DominatorTreeAnalysis and related pass implementations
312 //===----------------------------------------------------------------------===//
313 //
314 // This implements the DominatorTreeAnalysis which is used with the new pass
315 // manager. It also implements some methods from utility passes.
316 //
317 //===----------------------------------------------------------------------===//
318 
run(Function & F,FunctionAnalysisManager &)319 DominatorTree DominatorTreeAnalysis::run(Function &F,
320                                          FunctionAnalysisManager &) {
321   DominatorTree DT;
322   DT.recalculate(F);
323   return DT;
324 }
325 
326 AnalysisKey DominatorTreeAnalysis::Key;
327 
DominatorTreePrinterPass(raw_ostream & OS)328 DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
329 
run(Function & F,FunctionAnalysisManager & AM)330 PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
331                                                 FunctionAnalysisManager &AM) {
332   OS << "DominatorTree for function: " << F.getName() << "\n";
333   AM.getResult<DominatorTreeAnalysis>(F).print(OS);
334 
335   return PreservedAnalyses::all();
336 }
337 
run(Function & F,FunctionAnalysisManager & AM)338 PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
339                                                  FunctionAnalysisManager &AM) {
340   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
341   assert(DT.verify());
342   (void)DT;
343   return PreservedAnalyses::all();
344 }
345 
346 //===----------------------------------------------------------------------===//
347 //  DominatorTreeWrapperPass Implementation
348 //===----------------------------------------------------------------------===//
349 //
350 // The implementation details of the wrapper pass that holds a DominatorTree
351 // suitable for use with the legacy pass manager.
352 //
353 //===----------------------------------------------------------------------===//
354 
355 char DominatorTreeWrapperPass::ID = 0;
356 INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
357                 "Dominator Tree Construction", true, true)
358 
runOnFunction(Function & F)359 bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
360   DT.recalculate(F);
361   return false;
362 }
363 
verifyAnalysis() const364 void DominatorTreeWrapperPass::verifyAnalysis() const {
365   if (VerifyDomInfo)
366     assert(DT.verify(DominatorTree::VerificationLevel::Full));
367   else if (ExpensiveChecksEnabled)
368     assert(DT.verify(DominatorTree::VerificationLevel::Basic));
369 }
370 
print(raw_ostream & OS,const Module *) const371 void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
372   DT.print(OS);
373 }
374 
375 //===----------------------------------------------------------------------===//
376 //  DeferredDominance Implementation
377 //===----------------------------------------------------------------------===//
378 //
379 // The implementation details of the DeferredDominance class which allows
380 // one to queue updates to a DominatorTree.
381 //
382 //===----------------------------------------------------------------------===//
383 
384 /// Queues multiple updates and discards duplicates.
applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates)385 void DeferredDominance::applyUpdates(
386     ArrayRef<DominatorTree::UpdateType> Updates) {
387   SmallVector<DominatorTree::UpdateType, 8> Seen;
388   for (auto U : Updates)
389     // Avoid duplicates to applyUpdate() to save on analysis.
390     if (std::none_of(Seen.begin(), Seen.end(),
391                      [U](DominatorTree::UpdateType S) { return S == U; })) {
392       Seen.push_back(U);
393       applyUpdate(U.getKind(), U.getFrom(), U.getTo());
394     }
395 }
396 
397 /// Helper method for a single edge insertion. It's almost always better
398 /// to batch updates and call applyUpdates to quickly remove duplicate edges.
399 /// This is best used when there is only a single insertion needed to update
400 /// Dominators.
insertEdge(BasicBlock * From,BasicBlock * To)401 void DeferredDominance::insertEdge(BasicBlock *From, BasicBlock *To) {
402   applyUpdate(DominatorTree::Insert, From, To);
403 }
404 
405 /// Helper method for a single edge deletion. It's almost always better
406 /// to batch updates and call applyUpdates to quickly remove duplicate edges.
407 /// This is best used when there is only a single deletion needed to update
408 /// Dominators.
deleteEdge(BasicBlock * From,BasicBlock * To)409 void DeferredDominance::deleteEdge(BasicBlock *From, BasicBlock *To) {
410   applyUpdate(DominatorTree::Delete, From, To);
411 }
412 
413 /// Delays the deletion of a basic block until a flush() event.
deleteBB(BasicBlock * DelBB)414 void DeferredDominance::deleteBB(BasicBlock *DelBB) {
415   assert(DelBB && "Invalid push_back of nullptr DelBB.");
416   assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
417   // DelBB is unreachable and all its instructions are dead.
418   while (!DelBB->empty()) {
419     Instruction &I = DelBB->back();
420     // Replace used instructions with an arbitrary value (undef).
421     if (!I.use_empty())
422       I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
423     DelBB->getInstList().pop_back();
424   }
425   // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
426   // Child of Function F it must contain valid IR.
427   new UnreachableInst(DelBB->getContext(), DelBB);
428   DeletedBBs.insert(DelBB);
429 }
430 
431 /// Returns true if DelBB is awaiting deletion at a flush() event.
pendingDeletedBB(BasicBlock * DelBB)432 bool DeferredDominance::pendingDeletedBB(BasicBlock *DelBB) {
433   if (DeletedBBs.empty())
434     return false;
435   return DeletedBBs.count(DelBB) != 0;
436 }
437 
438 /// Returns true if pending DT updates are queued for a flush() event.
pending()439 bool DeferredDominance::pending() { return !PendUpdates.empty(); }
440 
441 /// Flushes all pending updates and block deletions. Returns a
442 /// correct DominatorTree reference to be used by the caller for analysis.
flush()443 DominatorTree &DeferredDominance::flush() {
444   // Updates to DT must happen before blocks are deleted below. Otherwise the
445   // DT traversal will encounter badref blocks and assert.
446   if (!PendUpdates.empty()) {
447     DT.applyUpdates(PendUpdates);
448     PendUpdates.clear();
449   }
450   flushDelBB();
451   return DT;
452 }
453 
454 /// Drops all internal state and forces a (slow) recalculation of the
455 /// DominatorTree based on the current state of the LLVM IR in F. This should
456 /// only be used in corner cases such as the Entry block of F being deleted.
recalculate(Function & F)457 void DeferredDominance::recalculate(Function &F) {
458   // flushDelBB must be flushed before the recalculation. The state of the IR
459   // must be consistent before the DT traversal algorithm determines the
460   // actual DT.
461   if (flushDelBB() || !PendUpdates.empty()) {
462     DT.recalculate(F);
463     PendUpdates.clear();
464   }
465 }
466 
467 /// Debug method to help view the state of pending updates.
468 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const469 LLVM_DUMP_METHOD void DeferredDominance::dump() const {
470   raw_ostream &OS = llvm::dbgs();
471   OS << "PendUpdates:\n";
472   int I = 0;
473   for (auto U : PendUpdates) {
474     OS << "  " << I << " : ";
475     ++I;
476     if (U.getKind() == DominatorTree::Insert)
477       OS << "Insert, ";
478     else
479       OS << "Delete, ";
480     BasicBlock *From = U.getFrom();
481     if (From) {
482       auto S = From->getName();
483       if (!From->hasName())
484         S = "(no name)";
485       OS << S << "(" << From << "), ";
486     } else {
487       OS << "(badref), ";
488     }
489     BasicBlock *To = U.getTo();
490     if (To) {
491       auto S = To->getName();
492       if (!To->hasName())
493         S = "(no_name)";
494       OS << S << "(" << To << ")\n";
495     } else {
496       OS << "(badref)\n";
497     }
498   }
499   OS << "DeletedBBs:\n";
500   I = 0;
501   for (auto BB : DeletedBBs) {
502     OS << "  " << I << " : ";
503     ++I;
504     if (BB->hasName())
505       OS << BB->getName() << "(";
506     else
507       OS << "(no_name)(";
508     OS << BB << ")\n";
509   }
510 }
511 #endif
512 
513 /// Apply an update (Kind, From, To) to the internal queued updates. The
514 /// update is only added when determined to be necessary. Checks for
515 /// self-domination, unnecessary updates, duplicate requests, and balanced
516 /// pairs of requests are all performed. Returns true if the update is
517 /// queued and false if it is discarded.
applyUpdate(DominatorTree::UpdateKind Kind,BasicBlock * From,BasicBlock * To)518 bool DeferredDominance::applyUpdate(DominatorTree::UpdateKind Kind,
519                                     BasicBlock *From, BasicBlock *To) {
520   if (From == To)
521     return false; // Cannot dominate self; discard update.
522 
523   // Discard updates by inspecting the current state of successors of From.
524   // Since applyUpdate() must be called *after* the Terminator of From is
525   // altered we can determine if the update is unnecessary.
526   bool HasEdge = std::any_of(succ_begin(From), succ_end(From),
527                              [To](BasicBlock *B) { return B == To; });
528   if (Kind == DominatorTree::Insert && !HasEdge)
529     return false; // Unnecessary Insert: edge does not exist in IR.
530   if (Kind == DominatorTree::Delete && HasEdge)
531     return false; // Unnecessary Delete: edge still exists in IR.
532 
533   // Analyze pending updates to determine if the update is unnecessary.
534   DominatorTree::UpdateType Update = {Kind, From, To};
535   DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
536                                           ? DominatorTree::Insert
537                                           : DominatorTree::Delete,
538                                       From, To};
539   for (auto I = PendUpdates.begin(), E = PendUpdates.end(); I != E; ++I) {
540     if (Update == *I)
541       return false; // Discard duplicate updates.
542     if (Invert == *I) {
543       // Update and Invert are both valid (equivalent to a no-op). Remove
544       // Invert from PendUpdates and discard the Update.
545       PendUpdates.erase(I);
546       return false;
547     }
548   }
549   PendUpdates.push_back(Update); // Save the valid update.
550   return true;
551 }
552 
553 /// Performs all pending basic block deletions. We have to defer the deletion
554 /// of these blocks until after the DominatorTree updates are applied. The
555 /// internal workings of the DominatorTree code expect every update's From
556 /// and To blocks to exist and to be a member of the same Function.
flushDelBB()557 bool DeferredDominance::flushDelBB() {
558   if (DeletedBBs.empty())
559     return false;
560   for (auto *BB : DeletedBBs)
561     BB->eraseFromParent();
562   DeletedBBs.clear();
563   return true;
564 }
565