LLVM  15.0.0git
Dominators.cpp
Go to the documentation of this file.
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/StringRef.h"
18 #include "llvm/Config/llvm-config.h"
19 #include "llvm/IR/CFG.h"
20 #include "llvm/IR/Function.h"
21 #include "llvm/IR/Instruction.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/PassManager.h"
24 #include "llvm/InitializePasses.h"
25 #include "llvm/PassRegistry.h"
26 #include "llvm/Support/Casting.h"
29 
30 #include <cassert>
31 
32 namespace llvm {
33 class Argument;
34 class Constant;
35 class Value;
36 } // namespace llvm
37 using namespace llvm;
38 
39 bool llvm::VerifyDomInfo = false;
42  cl::desc("Verify dominator info (time consuming)"));
43 
44 #ifdef EXPENSIVE_CHECKS
45 static constexpr bool ExpensiveChecksEnabled = true;
46 #else
47 static constexpr bool ExpensiveChecksEnabled = false;
48 #endif
49 
51  const Instruction *TI = Start->getTerminator();
52  unsigned NumEdgesToEnd = 0;
53  for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
54  if (TI->getSuccessor(i) == End)
55  ++NumEdgesToEnd;
56  if (NumEdgesToEnd >= 2)
57  return false;
58  }
59  assert(NumEdgesToEnd == 1);
60  return true;
61 }
62 
63 //===----------------------------------------------------------------------===//
64 // DominatorTree Implementation
65 //===----------------------------------------------------------------------===//
66 //
67 // Provide public access to DominatorTree information. Implementation details
68 // can be found in Dominators.h, GenericDomTree.h, and
69 // GenericDomTreeConstruction.h.
70 //
71 //===----------------------------------------------------------------------===//
72 
74 template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
75 template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
76 
77 template class llvm::cfg::Update<BasicBlock *>;
78 
79 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
81 template void
82 llvm::DomTreeBuilder::CalculateWithUpdates<DomTreeBuilder::BBDomTree>(
84 
85 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
87 // No CalculateWithUpdates<PostDomTree> instantiation, unless a usecase arises.
88 
89 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
91 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
93 
94 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
96 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
98 
99 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
102 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
105 
106 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
107  const DomTreeBuilder::BBDomTree &DT,
109 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
112 
115  // Check whether the analysis, all analyses on functions, or the function's
116  // CFG have been preserved.
117  auto PAC = PA.getChecker<DominatorTreeAnalysis>();
118  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
119  PAC.preservedSet<CFGAnalyses>());
120 }
121 
122 bool DominatorTree::dominates(const BasicBlock *BB, const Use &U) const {
123  Instruction *UserInst = cast<Instruction>(U.getUser());
124  if (auto *PN = dyn_cast<PHINode>(UserInst))
125  // A phi use using a value from a block is dominated by the end of that
126  // block. Note that the phi's parent block may not be.
127  return dominates(BB, PN->getIncomingBlock(U));
128  else
129  return properlyDominates(BB, UserInst->getParent());
130 }
131 
132 // dominates - Return true if Def dominates a use in User. This performs
133 // the special checks necessary if Def and User are in the same basic block.
134 // Note that Def doesn't dominate a use in Def itself!
136  const Instruction *User) const {
137  const Instruction *Def = dyn_cast<Instruction>(DefV);
138  if (!Def) {
139  assert((isa<Argument>(DefV) || isa<Constant>(DefV)) &&
140  "Should be called with an instruction, argument or constant");
141  return true; // Arguments and constants dominate everything.
142  }
143 
144  const BasicBlock *UseBB = User->getParent();
145  const BasicBlock *DefBB = Def->getParent();
146 
147  // Any unreachable use is dominated, even if Def == User.
148  if (!isReachableFromEntry(UseBB))
149  return true;
150 
151  // Unreachable definitions don't dominate anything.
152  if (!isReachableFromEntry(DefBB))
153  return false;
154 
155  // An instruction doesn't dominate a use in itself.
156  if (Def == User)
157  return false;
158 
159  // The value defined by an invoke dominates an instruction only if it
160  // dominates every instruction in UseBB.
161  // A PHI is dominated only if the instruction dominates every possible use in
162  // the UseBB.
163  if (isa<InvokeInst>(Def) || isa<CallBrInst>(Def) || isa<PHINode>(User))
164  return dominates(Def, UseBB);
165 
166  if (DefBB != UseBB)
167  return dominates(DefBB, UseBB);
168 
169  return Def->comesBefore(User);
170 }
171 
172 // true if Def would dominate a use in any instruction in UseBB.
173 // note that dominates(Def, Def->getParent()) is false.
175  const BasicBlock *UseBB) const {
176  const BasicBlock *DefBB = Def->getParent();
177 
178  // Any unreachable use is dominated, even if DefBB == UseBB.
179  if (!isReachableFromEntry(UseBB))
180  return true;
181 
182  // Unreachable definitions don't dominate anything.
183  if (!isReachableFromEntry(DefBB))
184  return false;
185 
186  if (DefBB == UseBB)
187  return false;
188 
189  // Invoke results are only usable in the normal destination, not in the
190  // exceptional destination.
191  if (const auto *II = dyn_cast<InvokeInst>(Def)) {
192  BasicBlock *NormalDest = II->getNormalDest();
193  BasicBlockEdge E(DefBB, NormalDest);
194  return dominates(E, UseBB);
195  }
196 
197  // Callbr results are similarly only usable in the default destination.
198  if (const auto *CBI = dyn_cast<CallBrInst>(Def)) {
199  BasicBlock *NormalDest = CBI->getDefaultDest();
200  BasicBlockEdge E(DefBB, NormalDest);
201  return dominates(E, UseBB);
202  }
203 
204  return dominates(DefBB, UseBB);
205 }
206 
208  const BasicBlock *UseBB) const {
209  // If the BB the edge ends in doesn't dominate the use BB, then the
210  // edge also doesn't.
211  const BasicBlock *Start = BBE.getStart();
212  const BasicBlock *End = BBE.getEnd();
213  if (!dominates(End, UseBB))
214  return false;
215 
216  // Simple case: if the end BB has a single predecessor, the fact that it
217  // dominates the use block implies that the edge also does.
218  if (End->getSinglePredecessor())
219  return true;
220 
221  // The normal edge from the invoke is critical. Conceptually, what we would
222  // like to do is split it and check if the new block dominates the use.
223  // With X being the new block, the graph would look like:
224  //
225  // DefBB
226  // /\ . .
227  // / \ . .
228  // / \ . .
229  // / \ | |
230  // A X B C
231  // | \ | /
232  // . \|/
233  // . NormalDest
234  // .
235  //
236  // Given the definition of dominance, NormalDest is dominated by X iff X
237  // dominates all of NormalDest's predecessors (X, B, C in the example). X
238  // trivially dominates itself, so we only have to find if it dominates the
239  // other predecessors. Since the only way out of X is via NormalDest, X can
240  // only properly dominate a node if NormalDest dominates that node too.
241  int IsDuplicateEdge = 0;
242  for (const BasicBlock *BB : predecessors(End)) {
243  if (BB == Start) {
244  // If there are multiple edges between Start and End, by definition they
245  // can't dominate anything.
246  if (IsDuplicateEdge++)
247  return false;
248  continue;
249  }
250 
251  if (!dominates(End, BB))
252  return false;
253  }
254  return true;
255 }
256 
257 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
258  Instruction *UserInst = cast<Instruction>(U.getUser());
259  // A PHI in the end of the edge is dominated by it.
260  PHINode *PN = dyn_cast<PHINode>(UserInst);
261  if (PN && PN->getParent() == BBE.getEnd() &&
262  PN->getIncomingBlock(U) == BBE.getStart())
263  return true;
264 
265  // Otherwise use the edge-dominates-block query, which
266  // handles the crazy critical edge cases properly.
267  const BasicBlock *UseBB;
268  if (PN)
269  UseBB = PN->getIncomingBlock(U);
270  else
271  UseBB = UserInst->getParent();
272  return dominates(BBE, UseBB);
273 }
274 
275 bool DominatorTree::dominates(const Value *DefV, const Use &U) const {
276  const Instruction *Def = dyn_cast<Instruction>(DefV);
277  if (!Def) {
278  assert((isa<Argument>(DefV) || isa<Constant>(DefV)) &&
279  "Should be called with an instruction, argument or constant");
280  return true; // Arguments and constants dominate everything.
281  }
282 
283  Instruction *UserInst = cast<Instruction>(U.getUser());
284  const BasicBlock *DefBB = Def->getParent();
285 
286  // Determine the block in which the use happens. PHI nodes use
287  // their operands on edges; simulate this by thinking of the use
288  // happening at the end of the predecessor block.
289  const BasicBlock *UseBB;
290  if (PHINode *PN = dyn_cast<PHINode>(UserInst))
291  UseBB = PN->getIncomingBlock(U);
292  else
293  UseBB = UserInst->getParent();
294 
295  // Any unreachable use is dominated, even if Def == User.
296  if (!isReachableFromEntry(UseBB))
297  return true;
298 
299  // Unreachable definitions don't dominate anything.
300  if (!isReachableFromEntry(DefBB))
301  return false;
302 
303  // Invoke instructions define their return values on the edges to their normal
304  // successors, so we have to handle them specially.
305  // Among other things, this means they don't dominate anything in
306  // their own block, except possibly a phi, so we don't need to
307  // walk the block in any case.
308  if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
309  BasicBlock *NormalDest = II->getNormalDest();
310  BasicBlockEdge E(DefBB, NormalDest);
311  return dominates(E, U);
312  }
313 
314  // Callbr results are similarly only usable in the default destination.
315  if (const auto *CBI = dyn_cast<CallBrInst>(Def)) {
316  BasicBlock *NormalDest = CBI->getDefaultDest();
317  BasicBlockEdge E(DefBB, NormalDest);
318  return dominates(E, U);
319  }
320 
321  // If the def and use are in different blocks, do a simple CFG dominator
322  // tree query.
323  if (DefBB != UseBB)
324  return dominates(DefBB, UseBB);
325 
326  // Ok, def and use are in the same block. If the def is an invoke, it
327  // doesn't dominate anything in the block. If it's a PHI, it dominates
328  // everything in the block.
329  if (isa<PHINode>(UserInst))
330  return true;
331 
332  return Def->comesBefore(UserInst);
333 }
334 
336  Instruction *I = dyn_cast<Instruction>(U.getUser());
337 
338  // ConstantExprs aren't really reachable from the entry block, but they
339  // don't need to be treated like unreachable code either.
340  if (!I) return true;
341 
342  // PHI nodes use their operands on their incoming edges.
343  if (PHINode *PN = dyn_cast<PHINode>(I))
344  return isReachableFromEntry(PN->getIncomingBlock(U));
345 
346  // Everything else uses their operands in their own block.
347  return isReachableFromEntry(I->getParent());
348 }
349 
350 // Edge BBE1 dominates edge BBE2 if they match or BBE1 dominates start of BBE2.
352  const BasicBlockEdge &BBE2) const {
353  if (BBE1.getStart() == BBE2.getStart() && BBE1.getEnd() == BBE2.getEnd())
354  return true;
355  return dominates(BBE1, BBE2.getStart());
356 }
357 
358 //===----------------------------------------------------------------------===//
359 // DominatorTreeAnalysis and related pass implementations
360 //===----------------------------------------------------------------------===//
361 //
362 // This implements the DominatorTreeAnalysis which is used with the new pass
363 // manager. It also implements some methods from utility passes.
364 //
365 //===----------------------------------------------------------------------===//
366 
369  DominatorTree DT;
370  DT.recalculate(F);
371  return DT;
372 }
373 
375 
377 
380  OS << "DominatorTree for function: " << F.getName() << "\n";
382 
383  return PreservedAnalyses::all();
384 }
385 
388  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
389  assert(DT.verify());
390  (void)DT;
391  return PreservedAnalyses::all();
392 }
393 
394 //===----------------------------------------------------------------------===//
395 // DominatorTreeWrapperPass Implementation
396 //===----------------------------------------------------------------------===//
397 //
398 // The implementation details of the wrapper pass that holds a DominatorTree
399 // suitable for use with the legacy pass manager.
400 //
401 //===----------------------------------------------------------------------===//
402 
404 
407 }
408 
410  "Dominator Tree Construction", true, true)
411 
413  DT.recalculate(F);
414  return false;
415 }
416 
418  if (VerifyDomInfo)
420  else if (ExpensiveChecksEnabled)
422 }
423 
425  DT.print(OS);
426 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
INITIALIZE_PASS
INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree", "Dominator Tree Construction", true, true) bool DominatorTreeWrapperPass
Definition: Dominators.cpp:409
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
llvm::DominatorTreeWrapperPass::ID
static char ID
Definition: Dominators.h:306
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::DominatorTree::dominates
bool dominates(const Instruction *Def, const BasicBlock *BB) const
Definition: Dominators.cpp:174
llvm::DominatorTreeBase::print
void print(raw_ostream &O) const
print - Convert to human readable form
Definition: GenericDomTree.h:709
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
llvm::Function
Definition: Function.h:60
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:447
StringRef.h
llvm::DomTreeBuilder::BBUpdates
ArrayRef< llvm::cfg::Update< BasicBlock * > > BBUpdates
Definition: Dominators.h:60
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:90
llvm::DominatorTree::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: Dominators.cpp:113
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
VerifyDomInfoX
static cl::opt< bool, true > VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden, cl::desc("Verify dominator info (time consuming)"))
llvm::BasicBlockEdge
Definition: Dominators.h:98
llvm::JumpTable::Full
@ Full
Definition: TargetOptions.h:50
PassRegistry.h
llvm::DominatorTreeWrapperPass::print
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: Dominators.cpp:424
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::GraphDiff
Definition: CFGDiff.h:57
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
Instruction.h
CommandLine.h
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:777
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:789
llvm::BasicBlockEdge::getStart
const BasicBlock * getStart() const
Definition: Dominators.h:112
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:667
llvm::DominatorTreePrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:378
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
CFG.h
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3776
llvm::cl::opt
Definition: CommandLine.h:1392
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
I
#define I(x, y, z)
Definition: MD5.cpp:58
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::DominatorTreeAnalysis::run
DominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a dominator tree.
Definition: Dominators.cpp:367
llvm::DominatorTreeBase::recalculate
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
Definition: GenericDomTree.h:778
llvm::BasicBlockEdge::getEnd
const BasicBlock * getEnd() const
Definition: Dominators.h:116
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::DominatorTreeWrapperPass::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: Dominators.cpp:417
llvm::DominatorTreeBase< BasicBlock, false >
llvm::DominatorTreeBase< BasicBlock, false >::properlyDominates
bool properlyDominates(const DomTreeNodeBase< BasicBlock > *A, const DomTreeNodeBase< BasicBlock > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Definition: GenericDomTree.h:392
ExpensiveChecksEnabled
static constexpr bool ExpensiveChecksEnabled
Definition: Dominators.cpp:47
llvm::DomTreeNodeBase< BasicBlock >
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::BasicBlockEdge::isSingleEdge
bool isSingleEdge() const
Check if this is the only edge between Start and End.
Definition: Dominators.cpp:50
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
Casting.h
Function.h
PassManager.h
llvm::initializeDominatorTreeWrapperPassPass
void initializeDominatorTreeWrapperPassPass(PassRegistry &)
llvm::DominatorTreeBase::VerificationLevel
VerificationLevel
Definition: GenericDomTree.h:245
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
Instructions.h
llvm::DominatorTreePrinterPass::DominatorTreePrinterPass
DominatorTreePrinterPass(raw_ostream &OS)
Definition: Dominators.cpp:376
Dominators.h
llvm::codeview::Basic
@ Basic
Definition: CodeView.h:152
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2780
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
llvm::PHINode
Definition: Instructions.h:2664
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:119
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:310
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::cfg::Update
Definition: CFGUpdate.h:28
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::cl::desc
Definition: CommandLine.h:405
raw_ostream.h
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::DominatorTreeVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:386
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::VerifyDomInfo
bool VerifyDomInfo
Enables verification of dominator trees.
Definition: Dominators.cpp:39
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::DominatorTreeWrapperPass::DominatorTreeWrapperPass
DominatorTreeWrapperPass()
Definition: Dominators.cpp:405