contrib/llvm/lib/IR/Dominators.cpp

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