blob: 37e735251fdfae54168d8e61f9775bbc0eacc74e [file] [log] [blame]
Chris Lattnerd43023a2002-08-02 16:43:03 +00001//===- Dominators.cpp - Dominator Calculation -----------------------------===//
Misha Brukmanb1c93172005-04-21 23:48:37 +00002//
John Criswell482202a2003-10-20 19:43:21 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukmanb1c93172005-04-21 23:48:37 +00007//
John Criswell482202a2003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Chris Lattner081aabc2001-07-02 05:46:38 +00009//
Chris Lattnerd43023a2002-08-02 16:43:03 +000010// 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.
Chris Lattner081aabc2001-07-02 05:46:38 +000014//
15//===----------------------------------------------------------------------===//
16
Chandler Carruth5ad5f152014-01-13 09:26:24 +000017#include "llvm/IR/Dominators.h"
Reid Spencer7c16caa2004-09-01 22:55:40 +000018#include "llvm/ADT/DepthFirstIterator.h"
Devang Patel5a1bd402007-03-27 20:50:46 +000019#include "llvm/ADT/SmallPtrSet.h"
Chandler Carruth1305dc32014-03-04 11:45:46 +000020#include "llvm/IR/CFG.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000021#include "llvm/IR/Instructions.h"
Chandler Carruth64764b42015-01-14 10:19:28 +000022#include "llvm/IR/PassManager.h"
Dan Gohman4dbb3012009-09-28 00:27:48 +000023#include "llvm/Support/CommandLine.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000024#include "llvm/Support/Debug.h"
Chandler Carruthe509db42014-01-13 10:52:56 +000025#include "llvm/Support/GenericDomTreeConstruction.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000026#include "llvm/Support/raw_ostream.h"
Chris Lattnerc5e0be62004-06-05 00:24:59 +000027#include <algorithm>
Chris Lattner189d19f2003-11-21 20:23:48 +000028using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000029
Dan Gohman4dbb3012009-09-28 00:27:48 +000030// Always verify dominfo if expensive checking is enabled.
Filipe Cabecinhas0da99372016-04-29 15:22:48 +000031#ifdef EXPENSIVE_CHECKS
Serge Pavlov69b3ff92017-01-24 05:52:07 +000032bool llvm::VerifyDomInfo = true;
Dan Gohman4dbb3012009-09-28 00:27:48 +000033#else
Serge Pavlov69b3ff92017-01-24 05:52:07 +000034bool llvm::VerifyDomInfo = false;
Dan Gohman4dbb3012009-09-28 00:27:48 +000035#endif
36static cl::opt<bool,true>
37VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo),
38 cl::desc("Verify dominator info (time consuming)"));
39
Rafael Espindolacc80cde2012-08-16 15:09:43 +000040bool 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;
Rafael Espindola11870772012-08-10 14:05:55 +000051}
52
Chris Lattnerc385beb2001-07-06 16:58:22 +000053//===----------------------------------------------------------------------===//
Owen Andersonf35a1db2007-04-15 08:47:27 +000054// DominatorTree Implementation
Chris Lattner00f51672003-12-07 00:38:08 +000055//===----------------------------------------------------------------------===//
56//
Owen Anderson84c357f2007-09-23 21:31:44 +000057// Provide public access to DominatorTree information. Implementation details
Chandler Carruthe509db42014-01-13 10:52:56 +000058// can be found in Dominators.h, GenericDomTree.h, and
59// GenericDomTreeConstruction.h.
Chris Lattner00f51672003-12-07 00:38:08 +000060//
61//===----------------------------------------------------------------------===//
62
Benjamin Kramera667d1a2015-07-13 17:21:31 +000063template class llvm::DomTreeNodeBase<BasicBlock>;
64template class llvm::DominatorTreeBase<BasicBlock>;
Owen Anderson41878012007-10-16 19:59:25 +000065
Benjamin Kramera667d1a2015-07-13 17:21:31 +000066template void llvm::Calculate<Function, BasicBlock *>(
Tim Shen8b58bdf2016-08-17 20:01:58 +000067 DominatorTreeBase<
68 typename std::remove_pointer<GraphTraits<BasicBlock *>::NodeRef>::type>
69 &DT,
70 Function &F);
Benjamin Kramera667d1a2015-07-13 17:21:31 +000071template void llvm::Calculate<Function, Inverse<BasicBlock *>>(
Tim Shen8b58bdf2016-08-17 20:01:58 +000072 DominatorTreeBase<typename std::remove_pointer<
73 GraphTraits<Inverse<BasicBlock *>>::NodeRef>::type> &DT,
Benjamin Kramera667d1a2015-07-13 17:21:31 +000074 Function &F);
Rafael Espindola30616362014-02-14 22:36:16 +000075
Chandler Carruthca68a3e2017-01-15 06:32:49 +000076bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
77 FunctionAnalysisManager::Invalidator &) {
78 // Check whether the analysis, all analyses on functions, or the function's
79 // CFG have been preserved.
80 auto PAC = PA.getChecker<DominatorTreeAnalysis>();
81 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
82 PAC.preservedSet<CFGAnalyses>());
83}
84
Rafael Espindola94df2672012-02-26 02:19:19 +000085// dominates - Return true if Def dominates a use in User. This performs
86// the special checks necessary if Def and User are in the same basic block.
87// Note that Def doesn't dominate a use in Def itself!
88bool DominatorTree::dominates(const Instruction *Def,
89 const Instruction *User) const {
90 const BasicBlock *UseBB = User->getParent();
91 const BasicBlock *DefBB = Def->getParent();
Rafael Espindola082d4822012-02-18 19:46:02 +000092
Rafael Espindolaa53c46a2012-03-30 16:46:21 +000093 // Any unreachable use is dominated, even if Def == User.
94 if (!isReachableFromEntry(UseBB))
95 return true;
96
97 // Unreachable definitions don't dominate anything.
98 if (!isReachableFromEntry(DefBB))
99 return false;
Rafael Espindola082d4822012-02-18 19:46:02 +0000100
Rafael Espindola94df2672012-02-26 02:19:19 +0000101 // An instruction doesn't dominate a use in itself.
102 if (Def == User)
Chris Lattner22151ce2009-09-21 22:30:50 +0000103 return false;
Rafael Espindola082d4822012-02-18 19:46:02 +0000104
David Majnemer8a1c45d2015-12-12 05:38:55 +0000105 // The value defined by an invoke dominates an instruction only if it
106 // dominates every instruction in UseBB.
107 // A PHI is dominated only if the instruction dominates every possible use in
108 // the UseBB.
109 if (isa<InvokeInst>(Def) || isa<PHINode>(User))
Rafael Espindola94df2672012-02-26 02:19:19 +0000110 return dominates(Def, UseBB);
111
112 if (DefBB != UseBB)
113 return dominates(DefBB, UseBB);
114
115 // Loop through the basic block until we find Def or User.
116 BasicBlock::const_iterator I = DefBB->begin();
117 for (; &*I != Def && &*I != User; ++I)
Chris Lattner22151ce2009-09-21 22:30:50 +0000118 /*empty*/;
Rafael Espindola082d4822012-02-18 19:46:02 +0000119
Rafael Espindola94df2672012-02-26 02:19:19 +0000120 return &*I == Def;
121}
122
123// true if Def would dominate a use in any instruction in UseBB.
124// note that dominates(Def, Def->getParent()) is false.
125bool DominatorTree::dominates(const Instruction *Def,
126 const BasicBlock *UseBB) const {
127 const BasicBlock *DefBB = Def->getParent();
128
Rafael Espindolaa53c46a2012-03-30 16:46:21 +0000129 // Any unreachable use is dominated, even if DefBB == UseBB.
130 if (!isReachableFromEntry(UseBB))
131 return true;
132
133 // Unreachable definitions don't dominate anything.
134 if (!isReachableFromEntry(DefBB))
135 return false;
Rafael Espindola94df2672012-02-26 02:19:19 +0000136
137 if (DefBB == UseBB)
138 return false;
139
David Majnemer8a1c45d2015-12-12 05:38:55 +0000140 // Invoke results are only usable in the normal destination, not in the
141 // exceptional destination.
David Majnemer0bc0eef2015-08-15 02:46:08 +0000142 if (const auto *II = dyn_cast<InvokeInst>(Def)) {
143 BasicBlock *NormalDest = II->getNormalDest();
144 BasicBlockEdge E(DefBB, NormalDest);
145 return dominates(E, UseBB);
146 }
Rafael Espindola94df2672012-02-26 02:19:19 +0000147
David Majnemer0bc0eef2015-08-15 02:46:08 +0000148 return dominates(DefBB, UseBB);
Rafael Espindola59564072012-08-07 17:30:46 +0000149}
150
151bool DominatorTree::dominates(const BasicBlockEdge &BBE,
152 const BasicBlock *UseBB) const {
153 // If the BB the edge ends in doesn't dominate the use BB, then the
154 // edge also doesn't.
155 const BasicBlock *Start = BBE.getStart();
156 const BasicBlock *End = BBE.getEnd();
157 if (!dominates(End, UseBB))
Rafael Espindola94df2672012-02-26 02:19:19 +0000158 return false;
159
Rafael Espindola59564072012-08-07 17:30:46 +0000160 // Simple case: if the end BB has a single predecessor, the fact that it
161 // dominates the use block implies that the edge also does.
162 if (End->getSinglePredecessor())
Rafael Espindola94df2672012-02-26 02:19:19 +0000163 return true;
164
165 // The normal edge from the invoke is critical. Conceptually, what we would
166 // like to do is split it and check if the new block dominates the use.
167 // With X being the new block, the graph would look like:
168 //
169 // DefBB
170 // /\ . .
171 // / \ . .
172 // / \ . .
173 // / \ | |
174 // A X B C
175 // | \ | /
176 // . \|/
177 // . NormalDest
178 // .
179 //
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +0000180 // Given the definition of dominance, NormalDest is dominated by X iff X
Rafael Espindola94df2672012-02-26 02:19:19 +0000181 // dominates all of NormalDest's predecessors (X, B, C in the example). X
182 // trivially dominates itself, so we only have to find if it dominates the
183 // other predecessors. Since the only way out of X is via NormalDest, X can
184 // only properly dominate a node if NormalDest dominates that node too.
Adam Nemet4ef096b2017-06-05 16:27:09 +0000185 int IsDuplicateEdge = 0;
Duncan P. N. Exon Smith6c990152014-07-21 17:06:51 +0000186 for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
187 PI != E; ++PI) {
188 const BasicBlock *BB = *PI;
Adam Nemet4ef096b2017-06-05 16:27:09 +0000189 if (BB == Start) {
190 // If there are multiple edges between Start and End, by definition they
191 // can't dominate anything.
192 if (IsDuplicateEdge++)
193 return false;
Rafael Espindola94df2672012-02-26 02:19:19 +0000194 continue;
Adam Nemet4ef096b2017-06-05 16:27:09 +0000195 }
Rafael Espindola94df2672012-02-26 02:19:19 +0000196
Rafael Espindola59564072012-08-07 17:30:46 +0000197 if (!dominates(End, BB))
Rafael Espindola94df2672012-02-26 02:19:19 +0000198 return false;
199 }
200 return true;
Chris Lattner22151ce2009-09-21 22:30:50 +0000201}
Dan Gohman73273272012-04-12 23:31:46 +0000202
Chandler Carruth73523022014-01-13 13:07:17 +0000203bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
Rafael Espindola59564072012-08-07 17:30:46 +0000204 Instruction *UserInst = cast<Instruction>(U.getUser());
205 // A PHI in the end of the edge is dominated by it.
206 PHINode *PN = dyn_cast<PHINode>(UserInst);
207 if (PN && PN->getParent() == BBE.getEnd() &&
208 PN->getIncomingBlock(U) == BBE.getStart())
209 return true;
210
211 // Otherwise use the edge-dominates-block query, which
212 // handles the crazy critical edge cases properly.
213 const BasicBlock *UseBB;
214 if (PN)
215 UseBB = PN->getIncomingBlock(U);
216 else
217 UseBB = UserInst->getParent();
218 return dominates(BBE, UseBB);
219}
220
Chandler Carruth73523022014-01-13 13:07:17 +0000221bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
Rafael Espindola59564072012-08-07 17:30:46 +0000222 Instruction *UserInst = cast<Instruction>(U.getUser());
Dan Gohman73273272012-04-12 23:31:46 +0000223 const BasicBlock *DefBB = Def->getParent();
224
225 // Determine the block in which the use happens. PHI nodes use
226 // their operands on edges; simulate this by thinking of the use
227 // happening at the end of the predecessor block.
228 const BasicBlock *UseBB;
229 if (PHINode *PN = dyn_cast<PHINode>(UserInst))
230 UseBB = PN->getIncomingBlock(U);
231 else
232 UseBB = UserInst->getParent();
233
234 // Any unreachable use is dominated, even if Def == User.
235 if (!isReachableFromEntry(UseBB))
236 return true;
237
238 // Unreachable definitions don't dominate anything.
239 if (!isReachableFromEntry(DefBB))
240 return false;
241
David Majnemer8a1c45d2015-12-12 05:38:55 +0000242 // Invoke instructions define their return values on the edges to their normal
243 // successors, so we have to handle them specially.
Dan Gohman73273272012-04-12 23:31:46 +0000244 // Among other things, this means they don't dominate anything in
245 // their own block, except possibly a phi, so we don't need to
246 // walk the block in any case.
247 if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
Rafael Espindola59564072012-08-07 17:30:46 +0000248 BasicBlock *NormalDest = II->getNormalDest();
249 BasicBlockEdge E(DefBB, NormalDest);
250 return dominates(E, U);
Dan Gohman73273272012-04-12 23:31:46 +0000251 }
252
253 // If the def and use are in different blocks, do a simple CFG dominator
254 // tree query.
255 if (DefBB != UseBB)
256 return dominates(DefBB, UseBB);
257
258 // Ok, def and use are in the same block. If the def is an invoke, it
259 // doesn't dominate anything in the block. If it's a PHI, it dominates
260 // everything in the block.
261 if (isa<PHINode>(UserInst))
262 return true;
263
264 // Otherwise, just loop through the basic block until we find Def or User.
265 BasicBlock::const_iterator I = DefBB->begin();
266 for (; &*I != Def && &*I != UserInst; ++I)
267 /*empty*/;
268
269 return &*I != UserInst;
270}
271
272bool DominatorTree::isReachableFromEntry(const Use &U) const {
273 Instruction *I = dyn_cast<Instruction>(U.getUser());
274
275 // ConstantExprs aren't really reachable from the entry block, but they
276 // don't need to be treated like unreachable code either.
277 if (!I) return true;
278
279 // PHI nodes use their operands on their incoming edges.
280 if (PHINode *PN = dyn_cast<PHINode>(I))
281 return isReachableFromEntry(PN->getIncomingBlock(U));
282
283 // Everything else uses their operands in their own block.
284 return isReachableFromEntry(I->getParent());
285}
Chandler Carruth73523022014-01-13 13:07:17 +0000286
287void DominatorTree::verifyDomTree() const {
Chandler Carruth73523022014-01-13 13:07:17 +0000288 Function &F = *getRoot()->getParent();
289
290 DominatorTree OtherDT;
291 OtherDT.recalculate(F);
292 if (compare(OtherDT)) {
293 errs() << "DominatorTree is not up to date!\nComputed:\n";
294 print(errs());
295 errs() << "\nActual:\n";
296 OtherDT.print(errs());
297 abort();
298 }
299}
300
301//===----------------------------------------------------------------------===//
Chandler Carruth64764b42015-01-14 10:19:28 +0000302// DominatorTreeAnalysis and related pass implementations
303//===----------------------------------------------------------------------===//
304//
305// This implements the DominatorTreeAnalysis which is used with the new pass
306// manager. It also implements some methods from utility passes.
307//
308//===----------------------------------------------------------------------===//
309
Chandler Carruth164a2aa62016-06-17 00:11:01 +0000310DominatorTree DominatorTreeAnalysis::run(Function &F,
Sean Silva36e0d012016-08-09 00:28:15 +0000311 FunctionAnalysisManager &) {
Chandler Carruth64764b42015-01-14 10:19:28 +0000312 DominatorTree DT;
313 DT.recalculate(F);
314 return DT;
315}
316
Chandler Carruthdab4eae2016-11-23 17:53:26 +0000317AnalysisKey DominatorTreeAnalysis::Key;
NAKAMURA Takumidf0cd722016-02-28 17:17:00 +0000318
Chandler Carruth64764b42015-01-14 10:19:28 +0000319DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
320
321PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
Chandler Carruthb47f8012016-03-11 11:05:24 +0000322 FunctionAnalysisManager &AM) {
Chandler Carruth64764b42015-01-14 10:19:28 +0000323 OS << "DominatorTree for function: " << F.getName() << "\n";
Chandler Carruthb47f8012016-03-11 11:05:24 +0000324 AM.getResult<DominatorTreeAnalysis>(F).print(OS);
Chandler Carruth64764b42015-01-14 10:19:28 +0000325
326 return PreservedAnalyses::all();
327}
328
329PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
Chandler Carruthb47f8012016-03-11 11:05:24 +0000330 FunctionAnalysisManager &AM) {
331 AM.getResult<DominatorTreeAnalysis>(F).verifyDomTree();
Chandler Carruth64764b42015-01-14 10:19:28 +0000332
333 return PreservedAnalyses::all();
334}
335
336//===----------------------------------------------------------------------===//
Chandler Carruth73523022014-01-13 13:07:17 +0000337// DominatorTreeWrapperPass Implementation
338//===----------------------------------------------------------------------===//
339//
Chandler Carruth64764b42015-01-14 10:19:28 +0000340// The implementation details of the wrapper pass that holds a DominatorTree
341// suitable for use with the legacy pass manager.
Chandler Carruth73523022014-01-13 13:07:17 +0000342//
343//===----------------------------------------------------------------------===//
344
345char DominatorTreeWrapperPass::ID = 0;
346INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
347 "Dominator Tree Construction", true, true)
348
349bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
350 DT.recalculate(F);
351 return false;
352}
353
Adam Nemete340f852015-05-06 08:18:41 +0000354void DominatorTreeWrapperPass::verifyAnalysis() const {
355 if (VerifyDomInfo)
356 DT.verifyDomTree();
357}
Chandler Carruth73523022014-01-13 13:07:17 +0000358
359void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
360 DT.print(OS);
361}
362