14c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner//===- Dominators.cpp - Dominator Calculation -----------------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 91715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 104c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// This file implements simple dominator construction algorithms for finding 114c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// forward dominators. Postdominators are available in libanalysis, but are not 124c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// included in libvmcore, because it's not needed. Forward dominators are 134c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// needed to support the Verifier pass. 141715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 151715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 161715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 174676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich#include "llvm/Analysis/Dominators.h" 18221d688a5ef21a22c2368c9fff0e92d7966c95e5Chris Lattner#include "llvm/Support/CFG.h" 1949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson#include "llvm/Support/Compiler.h" 209a7b37b8a35e60494cde8b2bb6b6cab587836c7aTobias Grosser#include "llvm/Support/Debug.h" 21551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h" 222ad28e6c486f91d83b2d5bcd30612049a686ad64Devang Patel#include "llvm/ADT/SmallPtrSet.h" 233e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattner#include "llvm/ADT/SmallVector.h" 249cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson#include "llvm/Analysis/DominatorInternals.h" 259fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#include "llvm/Assembly/Writer.h" 26b9dbc4deccefc062a29bce49dc60bf9d5627e603Devang Patel#include "llvm/Instructions.h" 27791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner#include "llvm/Support/raw_ostream.h" 289450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman#include "llvm/Support/CommandLine.h" 298e72749fc0b44ac8b7a5ffbb275f2ad60f2fa41eChris Lattner#include <algorithm> 3031f8499e83dc4dccbb57ea7e76d1fd49b7010d0cChris Lattnerusing namespace llvm; 31d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 329450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman// Always verify dominfo if expensive checking is enabled. 339450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman#ifdef XDEBUG 34b35798347ea87b8b6d36155b211016a7769f01abDan Gohmanstatic bool VerifyDomInfo = true; 359450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman#else 36b35798347ea87b8b6d36155b211016a7769f01abDan Gohmanstatic bool VerifyDomInfo = false; 379450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman#endif 389450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohmanstatic cl::opt<bool,true> 399450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan GohmanVerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), 409450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman cl::desc("Verify dominator info (time consuming)")); 419450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman 4205130597262f3ed00dc4881d64795d117c76e3fcRafael Espindolabool BasicBlockEdge::isSingleEdge() const { 4305130597262f3ed00dc4881d64795d117c76e3fcRafael Espindola const TerminatorInst *TI = Start->getTerminator(); 4405130597262f3ed00dc4881d64795d117c76e3fcRafael Espindola unsigned NumEdgesToEnd = 0; 4505130597262f3ed00dc4881d64795d117c76e3fcRafael Espindola for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) { 4605130597262f3ed00dc4881d64795d117c76e3fcRafael Espindola if (TI->getSuccessor(i) == End) 4705130597262f3ed00dc4881d64795d117c76e3fcRafael Espindola ++NumEdgesToEnd; 4805130597262f3ed00dc4881d64795d117c76e3fcRafael Espindola if (NumEdgesToEnd >= 2) 4905130597262f3ed00dc4881d64795d117c76e3fcRafael Espindola return false; 5005130597262f3ed00dc4881d64795d117c76e3fcRafael Espindola } 5105130597262f3ed00dc4881d64795d117c76e3fcRafael Espindola assert(NumEdgesToEnd == 1); 5205130597262f3ed00dc4881d64795d117c76e3fcRafael Espindola return true; 5325ac7518ffda5f4256e8333dde4801270bb26418Rafael Espindola} 5425ac7518ffda5f4256e8333dde4801270bb26418Rafael Espindola 5594108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner//===----------------------------------------------------------------------===// 563dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson// DominatorTree Implementation 5716addf87bf331645de63575aa15627c74b9cab66Chris Lattner//===----------------------------------------------------------------------===// 5816addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 59d20c824b201b1408d7ea7a4e2d601aee14db5cecOwen Anderson// Provide public access to DominatorTree information. Implementation details 60a9ba456b7cfc0d202acdb22aa2ddfdc00aa0d63eCameron Zwarich// can be found in DominatorInternals.h. 6116addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 6216addf87bf331645de63575aa15627c74b9cab66Chris Lattner//===----------------------------------------------------------------------===// 6316addf87bf331645de63575aa15627c74b9cab66Chris Lattner 64c63ca0a71b299ee0b8fc7dc8405d7f3c856ecfa3John McCallTEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase<BasicBlock>); 65c63ca0a71b299ee0b8fc7dc8405d7f3c856ecfa3John McCallTEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase<BasicBlock>); 6649b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 671997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar DominatorTree::ID = 0; 68d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(DominatorTree, "domtree", 69ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Dominator Tree Construction", true, true) 7016addf87bf331645de63575aa15627c74b9cab66Chris Lattner 713dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonbool DominatorTree::runOnFunction(Function &F) { 72d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson DT->recalculate(F); 733dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson return false; 743dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson} 751715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 769450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohmanvoid DominatorTree::verifyAnalysis() const { 77a9245d63f64dc8af8ddd877b94523fcc52c1d702Dan Gohman if (!VerifyDomInfo) return; 789450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman 799450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman Function &F = *getRoot()->getParent(); 809450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman 819450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman DominatorTree OtherDT; 829450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman OtherDT.getBase().recalculate(F); 8357863b8ee0d3adaaed60344bd6c63bace0436d60Chris Lattner if (compare(OtherDT)) { 840f4158790916352a52f105dbfb638c9a0db00321Bill Wendling errs() << "DominatorTree is not up to date!\nComputed:\n"; 8557863b8ee0d3adaaed60344bd6c63bace0436d60Chris Lattner print(errs()); 8657863b8ee0d3adaaed60344bd6c63bace0436d60Chris Lattner errs() << "\nActual:\n"; 8757863b8ee0d3adaaed60344bd6c63bace0436d60Chris Lattner OtherDT.print(errs()); 8857863b8ee0d3adaaed60344bd6c63bace0436d60Chris Lattner abort(); 8957863b8ee0d3adaaed60344bd6c63bace0436d60Chris Lattner } 909450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman} 919450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman 9245cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattnervoid DominatorTree::print(raw_ostream &OS, const Module *) const { 9345cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner DT->print(OS); 94791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner} 95791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner 96c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola// dominates - Return true if Def dominates a use in User. This performs 97c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola// the special checks necessary if Def and User are in the same basic block. 98c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola// Note that Def doesn't dominate a use in Def itself! 99c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindolabool DominatorTree::dominates(const Instruction *Def, 100c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola const Instruction *User) const { 101c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola const BasicBlock *UseBB = User->getParent(); 102c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola const BasicBlock *DefBB = Def->getParent(); 103c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola 104092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // Any unreachable use is dominated, even if Def == User. 105092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola if (!isReachableFromEntry(UseBB)) 106092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return true; 107092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola 108092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // Unreachable definitions don't dominate anything. 109092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola if (!isReachableFromEntry(DefBB)) 110092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return false; 111c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola 112c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // An instruction doesn't dominate a use in itself. 113c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola if (Def == User) 114c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola return false; 115c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola 116c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // The value defined by an invoke dominates an instruction only if 117c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // it dominates every instruction in UseBB. 118c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // A PHI is dominated only if the instruction dominates every possible use 119c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // in the UseBB. 120c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola if (isa<InvokeInst>(Def) || isa<PHINode>(User)) 121c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola return dominates(Def, UseBB); 122c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola 123c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola if (DefBB != UseBB) 124c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola return dominates(DefBB, UseBB); 125b155c23f98e45bf5a1f5e6329b46e8138dfef9ceRafael Espindola 126c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // Loop through the basic block until we find Def or User. 127c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola BasicBlock::const_iterator I = DefBB->begin(); 128c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola for (; &*I != Def && &*I != User; ++I) 129c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola /*empty*/; 130c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola 131c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola return &*I == Def; 132c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola} 133b155c23f98e45bf5a1f5e6329b46e8138dfef9ceRafael Espindola 134c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola// true if Def would dominate a use in any instruction in UseBB. 135c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola// note that dominates(Def, Def->getParent()) is false. 136c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindolabool DominatorTree::dominates(const Instruction *Def, 137c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola const BasicBlock *UseBB) const { 138c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola const BasicBlock *DefBB = Def->getParent(); 139b155c23f98e45bf5a1f5e6329b46e8138dfef9ceRafael Espindola 140092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // Any unreachable use is dominated, even if DefBB == UseBB. 141092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola if (!isReachableFromEntry(UseBB)) 142092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return true; 143092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola 144092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola // Unreachable definitions don't dominate anything. 145092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola if (!isReachableFromEntry(DefBB)) 146092c5ccf5bdcaa53151645e5628cec77fcf4062bRafael Espindola return false; 147c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola 148c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola if (DefBB == UseBB) 14975c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner return false; 150b155c23f98e45bf5a1f5e6329b46e8138dfef9ceRafael Espindola 151c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola const InvokeInst *II = dyn_cast<InvokeInst>(Def); 152c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola if (!II) 153c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola return dominates(DefBB, UseBB); 154b155c23f98e45bf5a1f5e6329b46e8138dfef9ceRafael Espindola 155c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // Invoke results are only usable in the normal destination, not in the 156c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // exceptional destination. 157c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola BasicBlock *NormalDest = II->getNormalDest(); 158702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola BasicBlockEdge E(DefBB, NormalDest); 159702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola return dominates(E, UseBB); 160702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola} 161702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola 162702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindolabool DominatorTree::dominates(const BasicBlockEdge &BBE, 163702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola const BasicBlock *UseBB) const { 164d5118c8f78a05ad0b426b6032138d1d934b77c8dRafael Espindola // Assert that we have a single edge. We could handle them by simply 165d5118c8f78a05ad0b426b6032138d1d934b77c8dRafael Espindola // returning false, but since isSingleEdge is linear on the number of 166d5118c8f78a05ad0b426b6032138d1d934b77c8dRafael Espindola // edges, the callers can normally handle them more efficiently. 167d5118c8f78a05ad0b426b6032138d1d934b77c8dRafael Espindola assert(BBE.isSingleEdge()); 168d5118c8f78a05ad0b426b6032138d1d934b77c8dRafael Espindola 169702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola // If the BB the edge ends in doesn't dominate the use BB, then the 170702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola // edge also doesn't. 171702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola const BasicBlock *Start = BBE.getStart(); 172702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola const BasicBlock *End = BBE.getEnd(); 173702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola if (!dominates(End, UseBB)) 174c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola return false; 175c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola 176702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola // Simple case: if the end BB has a single predecessor, the fact that it 177702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola // dominates the use block implies that the edge also does. 178702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola if (End->getSinglePredecessor()) 179c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola return true; 180c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola 181c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // The normal edge from the invoke is critical. Conceptually, what we would 182c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // like to do is split it and check if the new block dominates the use. 183c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // With X being the new block, the graph would look like: 184c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // 185c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // DefBB 186c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // /\ . . 187c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // / \ . . 188c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // / \ . . 189c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // / \ | | 190c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // A X B C 191c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // | \ | / 192c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // . \|/ 193c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // . NormalDest 194c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // . 195c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // 196c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // Given the definition of dominance, NormalDest is dominated by X iff X 197c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // dominates all of NormalDest's predecessors (X, B, C in the example). X 198c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // trivially dominates itself, so we only have to find if it dominates the 199c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // other predecessors. Since the only way out of X is via NormalDest, X can 200c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola // only properly dominate a node if NormalDest dominates that node too. 201702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola for (const_pred_iterator PI = pred_begin(End), E = pred_end(End); 202702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola PI != E; ++PI) { 203c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola const BasicBlock *BB = *PI; 204702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola if (BB == Start) 205c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola continue; 206c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola 207702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola if (!dominates(End, BB)) 208c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola return false; 209c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola } 210c9ae8cc24c70dda33b68cacf01d2feeeb836f6f2Rafael Espindola return true; 21175c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner} 212558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 213702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindolabool DominatorTree::dominates(const BasicBlockEdge &BBE, 214558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman const Use &U) const { 215d5118c8f78a05ad0b426b6032138d1d934b77c8dRafael Espindola // Assert that we have a single edge. We could handle them by simply 216d5118c8f78a05ad0b426b6032138d1d934b77c8dRafael Espindola // returning false, but since isSingleEdge is linear on the number of 217d5118c8f78a05ad0b426b6032138d1d934b77c8dRafael Espindola // edges, the callers can normally handle them more efficiently. 218d5118c8f78a05ad0b426b6032138d1d934b77c8dRafael Espindola assert(BBE.isSingleEdge()); 219d5118c8f78a05ad0b426b6032138d1d934b77c8dRafael Espindola 220702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola Instruction *UserInst = cast<Instruction>(U.getUser()); 221702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola // A PHI in the end of the edge is dominated by it. 222702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola PHINode *PN = dyn_cast<PHINode>(UserInst); 223702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola if (PN && PN->getParent() == BBE.getEnd() && 224702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola PN->getIncomingBlock(U) == BBE.getStart()) 225702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola return true; 226558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 227702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola // Otherwise use the edge-dominates-block query, which 228702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola // handles the crazy critical edge cases properly. 229702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola const BasicBlock *UseBB; 230702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola if (PN) 231702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola UseBB = PN->getIncomingBlock(U); 232702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola else 233702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola UseBB = UserInst->getParent(); 234702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola return dominates(BBE, UseBB); 235702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola} 236558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 237702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindolabool DominatorTree::dominates(const Instruction *Def, 238702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola const Use &U) const { 239702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola Instruction *UserInst = cast<Instruction>(U.getUser()); 240558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman const BasicBlock *DefBB = Def->getParent(); 241558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 242558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // Determine the block in which the use happens. PHI nodes use 243558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // their operands on edges; simulate this by thinking of the use 244558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // happening at the end of the predecessor block. 245558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman const BasicBlock *UseBB; 246558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman if (PHINode *PN = dyn_cast<PHINode>(UserInst)) 247558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman UseBB = PN->getIncomingBlock(U); 248558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman else 249558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman UseBB = UserInst->getParent(); 250558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 251558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // Any unreachable use is dominated, even if Def == User. 252558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman if (!isReachableFromEntry(UseBB)) 253558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman return true; 254558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 255558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // Unreachable definitions don't dominate anything. 256558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman if (!isReachableFromEntry(DefBB)) 257558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman return false; 258558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 259558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // Invoke instructions define their return values on the edges 260558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // to their normal successors, so we have to handle them specially. 261558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // Among other things, this means they don't dominate anything in 262558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // their own block, except possibly a phi, so we don't need to 263558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // walk the block in any case. 264558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) { 265702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola BasicBlock *NormalDest = II->getNormalDest(); 266702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola BasicBlockEdge E(DefBB, NormalDest); 267702bcce747cd3fd89049b16d37c9c88952b5af81Rafael Espindola return dominates(E, U); 268558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman } 269558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 270558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // If the def and use are in different blocks, do a simple CFG dominator 271558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // tree query. 272558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman if (DefBB != UseBB) 273558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman return dominates(DefBB, UseBB); 274558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 275558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // Ok, def and use are in the same block. If the def is an invoke, it 276558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // doesn't dominate anything in the block. If it's a PHI, it dominates 277558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // everything in the block. 278558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman if (isa<PHINode>(UserInst)) 279558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman return true; 280558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 281558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // Otherwise, just loop through the basic block until we find Def or User. 282558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman BasicBlock::const_iterator I = DefBB->begin(); 283558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman for (; &*I != Def && &*I != UserInst; ++I) 284558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman /*empty*/; 285558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 286558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman return &*I != UserInst; 287558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman} 288558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 289558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohmanbool DominatorTree::isReachableFromEntry(const Use &U) const { 290558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman Instruction *I = dyn_cast<Instruction>(U.getUser()); 291558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 292558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // ConstantExprs aren't really reachable from the entry block, but they 293558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // don't need to be treated like unreachable code either. 294558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman if (!I) return true; 295558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 296558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // PHI nodes use their operands on their incoming edges. 297558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman if (PHINode *PN = dyn_cast<PHINode>(I)) 298558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman return isReachableFromEntry(PN->getIncomingBlock(U)); 299558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman 300558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman // Everything else uses their operands in their own block. 301558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman return isReachableFromEntry(I->getParent()); 302558ece284cef9d42a96577f3943cb3efee8904e0Dan Gohman} 303