LLVM 18.0.0git
LoopNestAnalysis.cpp
Go to the documentation of this file.
1//===- LoopNestAnalysis.cpp - Loop Nest Analysis --------------------------==//
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/// \file
10/// The implementation for the loop nest analysis.
11///
12//===----------------------------------------------------------------------===//
13
18
19using namespace llvm;
20
21#define DEBUG_TYPE "loopnest"
22#ifndef NDEBUG
23static const char *VerboseDebug = DEBUG_TYPE "-verbose";
24#endif
25
26/// Determine whether the loops structure violates basic requirements for
27/// perfect nesting:
28/// - the inner loop should be the outer loop's only child
29/// - the outer loop header should 'flow' into the inner loop preheader
30/// or jump around the inner loop to the outer loop latch
31/// - if the inner loop latch exits the inner loop, it should 'flow' into
32/// the outer loop latch.
33/// Returns true if the loop structure satisfies the basic requirements and
34/// false otherwise.
35static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
36 ScalarEvolution &SE);
37
38//===----------------------------------------------------------------------===//
39// LoopNest implementation
40//
41
43 : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {
45}
46
47std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
48 ScalarEvolution &SE) {
49 return std::make_unique<LoopNest>(Root, SE);
50}
51
52static CmpInst *getOuterLoopLatchCmp(const Loop &OuterLoop) {
53
54 const BasicBlock *Latch = OuterLoop.getLoopLatch();
55 assert(Latch && "Expecting a valid loop latch");
56
57 const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
58 assert(BI && BI->isConditional() &&
59 "Expecting loop latch terminator to be a branch instruction");
60
61 CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition());
63 VerboseDebug, if (OuterLoopLatchCmp) {
64 dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp
65 << "\n";
66 });
67 return OuterLoopLatchCmp;
68}
69
70static CmpInst *getInnerLoopGuardCmp(const Loop &InnerLoop) {
71
72 BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch();
73 CmpInst *InnerLoopGuardCmp =
74 (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr;
75
77 VerboseDebug, if (InnerLoopGuardCmp) {
78 dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp
79 << "\n";
80 });
81 return InnerLoopGuardCmp;
82}
83
85 const CmpInst *InnerLoopGuardCmp,
86 const CmpInst *OuterLoopLatchCmp,
87 std::optional<Loop::LoopBounds> OuterLoopLB) {
88
89 bool IsAllowed =
90 isSafeToSpeculativelyExecute(&I) || isa<PHINode>(I) || isa<BranchInst>(I);
91 if (!IsAllowed)
92 return false;
93 // The only binary instruction allowed is the outer loop step instruction,
94 // the only comparison instructions allowed are the inner loop guard
95 // compare instruction and the outer loop latch compare instruction.
96 if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) ||
97 (isa<CmpInst>(I) && &I != OuterLoopLatchCmp && &I != InnerLoopGuardCmp)) {
98 return false;
99 }
100 return true;
101}
102
103bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
104 ScalarEvolution &SE) {
105 return (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE) ==
106 PerfectLoopNest);
107}
108
109LoopNest::LoopNestEnum LoopNest::analyzeLoopNestForPerfectNest(
110 const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {
111
112 assert(!OuterLoop.isInnermost() && "Outer loop should have subloops");
113 assert(!InnerLoop.isOutermost() && "Inner loop should have a parent");
114 LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName()
115 << "' and '" << InnerLoop.getName()
116 << "' are perfectly nested.\n");
117
118 // Determine whether the loops structure satisfies the following requirements:
119 // - the inner loop should be the outer loop's only child
120 // - the outer loop header should 'flow' into the inner loop preheader
121 // or jump around the inner loop to the outer loop latch
122 // - if the inner loop latch exits the inner loop, it should 'flow' into
123 // the outer loop latch.
124 if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) {
125 LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n");
126 return InvalidLoopStructure;
127 }
128
129 // Bail out if we cannot retrieve the outer loop bounds.
130 auto OuterLoopLB = OuterLoop.getBounds(SE);
131 if (OuterLoopLB == std::nullopt) {
132 LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "
133 << OuterLoop << "\n";);
134 return OuterLoopLowerBoundUnknown;
135 }
136
137 CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop);
138 CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop);
139
140 // Determine whether instructions in a basic block are one of:
141 // - the inner loop guard comparison
142 // - the outer loop latch comparison
143 // - the outer loop induction variable increment
144 // - a phi node, a cast or a branch
145 auto containsOnlySafeInstructions = [&](const BasicBlock &BB) {
146 return llvm::all_of(BB, [&](const Instruction &I) {
147 bool IsSafeInstr = checkSafeInstruction(I, InnerLoopGuardCmp,
148 OuterLoopLatchCmp, OuterLoopLB);
149 if (IsSafeInstr) {
151 dbgs() << "Instruction: " << I << "\nin basic block:" << BB
152 << "is unsafe.\n";
153 });
154 }
155 return IsSafeInstr;
156 });
157 };
158
159 // Check the code surrounding the inner loop for instructions that are deemed
160 // unsafe.
161 const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
162 const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
163 const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
164
165 if (!containsOnlySafeInstructions(*OuterLoopHeader) ||
166 !containsOnlySafeInstructions(*OuterLoopLatch) ||
167 (InnerLoopPreHeader != OuterLoopHeader &&
168 !containsOnlySafeInstructions(*InnerLoopPreHeader)) ||
169 !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) {
170 LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is "
171 "unsafe\n";);
172 return ImperfectLoopNest;
173 }
174
175 LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '"
176 << InnerLoop.getName() << "' are perfectly nested.\n");
177
178 return PerfectLoopNest;
179}
180
182 const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {
183 InstrVectorTy Instr;
184 switch (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE)) {
185 case PerfectLoopNest:
186 LLVM_DEBUG(dbgs() << "The loop Nest is Perfect, returning empty "
187 "instruction vector. \n";);
188 return Instr;
189
190 case InvalidLoopStructure:
191 LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure. "
192 "Instruction vector is empty.\n";);
193 return Instr;
194
195 case OuterLoopLowerBoundUnknown:
196 LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "
197 << OuterLoop << "\nInstruction vector is empty.\n";);
198 return Instr;
199
200 case ImperfectLoopNest:
201 break;
202 }
203
204 // Identify the outer loop latch comparison instruction.
205 auto OuterLoopLB = OuterLoop.getBounds(SE);
206
207 CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop);
208 CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop);
209
210 auto GetUnsafeInstructions = [&](const BasicBlock &BB) {
211 for (const Instruction &I : BB) {
212 if (!checkSafeInstruction(I, InnerLoopGuardCmp, OuterLoopLatchCmp,
213 OuterLoopLB)) {
214 Instr.push_back(&I);
216 dbgs() << "Instruction: " << I << "\nin basic block:" << BB
217 << "is unsafe.\n";
218 });
219 }
220 }
221 };
222
223 // Check the code surrounding the inner loop for instructions that are deemed
224 // unsafe.
225 const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
226 const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
227 const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
228 const BasicBlock *InnerLoopExitBlock = InnerLoop.getExitBlock();
229
230 GetUnsafeInstructions(*OuterLoopHeader);
231 GetUnsafeInstructions(*OuterLoopLatch);
232 GetUnsafeInstructions(*InnerLoopExitBlock);
233
234 if (InnerLoopPreHeader != OuterLoopHeader) {
235 GetUnsafeInstructions(*InnerLoopPreHeader);
236 }
237 return Instr;
238}
239
243 LoopVectorTy PerfectNest;
244
245 for (Loop *L : depth_first(const_cast<Loop *>(Loops.front()))) {
246 if (PerfectNest.empty())
247 PerfectNest.push_back(L);
248
249 auto &SubLoops = L->getSubLoops();
250 if (SubLoops.size() == 1 && arePerfectlyNested(*L, *SubLoops.front(), SE)) {
251 PerfectNest.push_back(SubLoops.front());
252 } else {
253 LV.push_back(PerfectNest);
254 PerfectNest.clear();
255 }
256 }
257
258 return LV;
259}
260
262 LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '"
263 << Root.getName() << "'\n");
264
265 const Loop *CurrentLoop = &Root;
266 const auto *SubLoops = &CurrentLoop->getSubLoops();
267 unsigned CurrentDepth = 1;
268
269 while (SubLoops->size() == 1) {
270 const Loop *InnerLoop = SubLoops->front();
271 if (!arePerfectlyNested(*CurrentLoop, *InnerLoop, SE)) {
272 LLVM_DEBUG({
273 dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName()
274 << "' is not perfectly nested with loop '"
275 << InnerLoop->getName() << "'\n";
276 });
277 break;
278 }
279
280 CurrentLoop = InnerLoop;
281 SubLoops = &CurrentLoop->getSubLoops();
282 ++CurrentDepth;
283 }
284
285 return CurrentDepth;
286}
287
289 const BasicBlock *End,
290 bool CheckUniquePred) {
291 assert(From && "Expecting valid From");
292 assert(End && "Expecting valid End");
293
294 if (From == End || !From->getUniqueSuccessor())
295 return *From;
296
297 auto IsEmpty = [](const BasicBlock *BB) {
298 return (BB->size() == 1);
299 };
300
301 // Visited is used to avoid running into an infinite loop.
303 const BasicBlock *BB = From->getUniqueSuccessor();
304 const BasicBlock *PredBB = From;
305 while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB) &&
306 (!CheckUniquePred || BB->getUniquePredecessor())) {
307 Visited.insert(BB);
308 PredBB = BB;
309 BB = BB->getUniqueSuccessor();
310 }
311
312 return (BB == End) ? *End : *PredBB;
313}
314
315static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
316 ScalarEvolution &SE) {
317 // The inner loop must be the only outer loop's child.
318 if ((OuterLoop.getSubLoops().size() != 1) ||
319 (InnerLoop.getParentLoop() != &OuterLoop))
320 return false;
321
322 // We expect loops in normal form which have a preheader, header, latch...
323 if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm())
324 return false;
325
326 const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
327 const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
328 const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
329 const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch();
330 const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock();
331
332 // We expect rotated loops. The inner loop should have a single exit block.
333 if (OuterLoop.getExitingBlock() != OuterLoopLatch ||
334 InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit)
335 return false;
336
337 // Returns whether the block `ExitBlock` contains at least one LCSSA Phi node.
338 auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) {
339 return any_of(ExitBlock.phis(), [](const PHINode &PN) {
340 return PN.getNumIncomingValues() == 1;
341 });
342 };
343
344 // Returns whether the block `BB` qualifies for being an extra Phi block. The
345 // extra Phi block is the additional block inserted after the exit block of an
346 // "guarded" inner loop which contains "only" Phi nodes corresponding to the
347 // LCSSA Phi nodes in the exit block.
348 auto IsExtraPhiBlock = [&](const BasicBlock &BB) {
349 return BB.getFirstNonPHI() == BB.getTerminator() &&
350 all_of(BB.phis(), [&](const PHINode &PN) {
351 return all_of(PN.blocks(), [&](const BasicBlock *IncomingBlock) {
352 return IncomingBlock == InnerLoopExit ||
353 IncomingBlock == OuterLoopHeader;
354 });
355 });
356 };
357
358 const BasicBlock *ExtraPhiBlock = nullptr;
359 // Ensure the only branch that may exist between the loops is the inner loop
360 // guard.
361 if (OuterLoopHeader != InnerLoopPreHeader) {
362 const BasicBlock &SingleSucc =
363 LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader);
364
365 // no conditional branch present
366 if (&SingleSucc != InnerLoopPreHeader) {
367 const BranchInst *BI = dyn_cast<BranchInst>(SingleSucc.getTerminator());
368
369 if (!BI || BI != InnerLoop.getLoopGuardBranch())
370 return false;
371
372 bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit);
373
374 // The successors of the inner loop guard should be the inner loop
375 // preheader or the outer loop latch possibly through empty blocks.
376 for (const BasicBlock *Succ : BI->successors()) {
377 const BasicBlock *PotentialInnerPreHeader = Succ;
378 const BasicBlock *PotentialOuterLatch = Succ;
379
380 // Ensure the inner loop guard successor is empty before skipping
381 // blocks.
382 if (Succ->size() == 1) {
383 PotentialInnerPreHeader =
384 &LoopNest::skipEmptyBlockUntil(Succ, InnerLoopPreHeader);
385 PotentialOuterLatch =
386 &LoopNest::skipEmptyBlockUntil(Succ, OuterLoopLatch);
387 }
388
389 if (PotentialInnerPreHeader == InnerLoopPreHeader)
390 continue;
391 if (PotentialOuterLatch == OuterLoopLatch)
392 continue;
393
394 // If `InnerLoopExit` contains LCSSA Phi instructions, additional block
395 // may be inserted before the `OuterLoopLatch` to which `BI` jumps. The
396 // loops are still considered perfectly nested if the extra block only
397 // contains Phi instructions from InnerLoopExit and OuterLoopHeader.
398 if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) &&
399 Succ->getSingleSuccessor() == OuterLoopLatch) {
400 // Points to the extra block so that we can reference it later in the
401 // final check. We can also conclude that the inner loop is
402 // guarded and there exists LCSSA Phi node in the exit block later if
403 // we see a non-null `ExtraPhiBlock`.
404 ExtraPhiBlock = Succ;
405 continue;
406 }
407
409 dbgs() << "Inner loop guard successor " << Succ->getName()
410 << " doesn't lead to inner loop preheader or "
411 "outer loop latch.\n";
412 });
413 return false;
414 }
415 }
416 }
417
418 // Ensure the inner loop exit block lead to the outer loop latch possibly
419 // through empty blocks.
420 if ((!ExtraPhiBlock ||
422 ExtraPhiBlock) != ExtraPhiBlock) &&
424 OuterLoopLatch) != OuterLoopLatch)) {
427 dbgs() << "Inner loop exit block " << *InnerLoopExit
428 << " does not directly lead to the outer loop latch.\n";);
429 return false;
430 }
431
432 return true;
433}
434
435AnalysisKey LoopNestAnalysis::Key;
436
438 OS << "IsPerfect=";
439 if (LN.getMaxPerfectDepth() == LN.getNestDepth())
440 OS << "true";
441 else
442 OS << "false";
443 OS << ", Depth=" << LN.getNestDepth();
444 OS << ", OutermostLoop: " << LN.getOutermostLoop().getName();
445 OS << ", Loops: ( ";
446 for (const Loop *L : LN.getLoops())
447 OS << L->getName() << " ";
448 OS << ")";
449
450 return OS;
451}
452
453//===----------------------------------------------------------------------===//
454// LoopNestPrinterPass implementation
455//
456
459 LPMUpdater &U) {
460 if (auto LN = LoopNest::getLoopNest(L, AR.SE))
461 OS << *LN << "\n";
462
463 return PreservedAnalyses::all();
464}
BlockVerifier::State From
This file builds on the ADT/GraphTraits.h file to build a generic breadth first graph iterator.
#define LLVM_DEBUG(X)
Definition: Debug.h:101
#define DEBUG_WITH_TYPE(TYPE, X)
DEBUG_WITH_TYPE macro - This macro should be used by passes to emit debug information.
Definition: Debug.h:64
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
bool End
Definition: ELF_riscv.cpp:469
static CmpInst * getOuterLoopLatchCmp(const Loop &OuterLoop)
static CmpInst * getInnerLoopGuardCmp(const Loop &InnerLoop)
static bool checkSafeInstruction(const Instruction &I, const CmpInst *InnerLoopGuardCmp, const CmpInst *OuterLoopLatchCmp, std::optional< Loop::LoopBounds > OuterLoopLB)
static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)
Determine whether the loops structure violates basic requirements for perfect nesting:
static const char * VerboseDebug
#define DEBUG_TYPE
This file defines the interface for the loop nest analysis.
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Definition: BasicBlock.cpp:334
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:304
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:127
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
bool isConditional() const
Value * getCondition() const
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:701
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
BlockT * getHeader() const
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
This class represents a loop nest and can be used to query its properties.
static const BasicBlock & skipEmptyBlockUntil(const BasicBlock *From, const BasicBlock *End, bool CheckUniquePred=false)
Recursivelly traverse all empty 'single successor' basic blocks of From (if there are any).
ArrayRef< Loop * > getLoops() const
Get the loops in the nest.
unsigned getNestDepth() const
Return the loop nest depth (i.e.
LoopVectorTy Loops
LoopNest()=delete
SmallVector< LoopVectorTy, 4 > getPerfectLoops(ScalarEvolution &SE) const
Retrieve a vector of perfect loop nests contained in the current loop nest.
static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)
Return true if the given loops OuterLoop and InnerLoop are perfectly nested with respect to each othe...
static InstrVectorTy getInterveningInstructions(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)
Return a vector of instructions that prevent the LoopNest given by loops OuterLoop and InnerLoop from...
static std::unique_ptr< LoopNest > getLoopNest(Loop &Root, ScalarEvolution &SE)
Construct a LoopNest object.
unsigned getMaxPerfectDepth() const
Return the maximum perfect nesting depth.
static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE)
Return the maximum nesting depth of the loop nest rooted by loop Root.
Loop & getOutermostLoop() const
Return the outermost loop in the loop nest.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
std::optional< LoopBounds > getBounds(ScalarEvolution &SE) const
Return the struct LoopBounds collected if all struct members are found, else std::nullopt.
Definition: LoopInfo.cpp:287
BranchInst * getLoopGuardBranch() const
Return the loop guard branch, if it exists.
Definition: LoopInfo.cpp:367
StringRef getName() const
Definition: LoopInfo.h:391
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:479
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
The main scalar evolution driver.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:384
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1727
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2037
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1734
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
iterator_range< bf_iterator< T > > breadth_first(const T &G)
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
iterator_range< df_iterator< T > > depth_first(const T &G)
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...