1 | //===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===// |
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 declares a GenericLoopInfo instantiation for LLVM IR. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_ANALYSIS_LOOPINFO_H |
14 | #define LLVM_ANALYSIS_LOOPINFO_H |
15 | |
16 | #include "llvm/ADT/GraphTraits.h" |
17 | #include "llvm/ADT/SmallVector.h" |
18 | #include "llvm/IR/CFG.h" |
19 | #include "llvm/IR/Instructions.h" |
20 | #include "llvm/IR/PassManager.h" |
21 | #include "llvm/Pass.h" |
22 | #include "llvm/Support/GenericLoopInfo.h" |
23 | #include <algorithm> |
24 | #include <optional> |
25 | #include <utility> |
26 | |
27 | namespace llvm { |
28 | |
29 | class DominatorTree; |
30 | class InductionDescriptor; |
31 | class Instruction; |
32 | class LoopInfo; |
33 | class Loop; |
34 | class MDNode; |
35 | class MemorySSAUpdater; |
36 | class ScalarEvolution; |
37 | class raw_ostream; |
38 | |
39 | // Implementation in Support/GenericLoopInfoImpl.h |
40 | extern template class LoopBase<BasicBlock, Loop>; |
41 | |
42 | /// Represents a single loop in the control flow graph. Note that not all SCCs |
43 | /// in the CFG are necessarily loops. |
44 | class LLVM_EXTERNAL_VISIBILITY Loop : public LoopBase<BasicBlock, Loop> { |
45 | public: |
46 | /// A range representing the start and end location of a loop. |
47 | class LocRange { |
48 | DebugLoc Start; |
49 | DebugLoc End; |
50 | |
51 | public: |
52 | LocRange() = default; |
53 | LocRange(DebugLoc Start) : Start(Start), End(Start) {} |
54 | LocRange(DebugLoc Start, DebugLoc End) |
55 | : Start(std::move(Start)), End(std::move(End)) {} |
56 | |
57 | const DebugLoc &getStart() const { return Start; } |
58 | const DebugLoc &getEnd() const { return End; } |
59 | |
60 | /// Check for null. |
61 | /// |
62 | explicit operator bool() const { return Start && End; } |
63 | }; |
64 | |
65 | /// Return true if the specified value is loop invariant. |
66 | bool isLoopInvariant(const Value *V) const; |
67 | |
68 | /// Return true if all the operands of the specified instruction are loop |
69 | /// invariant. |
70 | bool hasLoopInvariantOperands(const Instruction *I) const; |
71 | |
72 | /// If the given value is an instruction inside of the loop and it can be |
73 | /// hoisted, do so to make it trivially loop-invariant. |
74 | /// Return true if \c V is already loop-invariant, and false if \c V can't |
75 | /// be made loop-invariant. If \c V is made loop-invariant, \c Changed is |
76 | /// set to true. This function can be used as a slightly more aggressive |
77 | /// replacement for isLoopInvariant. |
78 | /// |
79 | /// If InsertPt is specified, it is the point to hoist instructions to. |
80 | /// If null, the terminator of the loop preheader is used. |
81 | /// |
82 | bool makeLoopInvariant(Value *V, bool &Changed, |
83 | Instruction *InsertPt = nullptr, |
84 | MemorySSAUpdater *MSSAU = nullptr, |
85 | ScalarEvolution *SE = nullptr) const; |
86 | |
87 | /// If the given instruction is inside of the loop and it can be hoisted, do |
88 | /// so to make it trivially loop-invariant. |
89 | /// Return true if \c I is already loop-invariant, and false if \c I can't |
90 | /// be made loop-invariant. If \c I is made loop-invariant, \c Changed is |
91 | /// set to true. This function can be used as a slightly more aggressive |
92 | /// replacement for isLoopInvariant. |
93 | /// |
94 | /// If InsertPt is specified, it is the point to hoist instructions to. |
95 | /// If null, the terminator of the loop preheader is used. |
96 | /// |
97 | bool makeLoopInvariant(Instruction *I, bool &Changed, |
98 | Instruction *InsertPt = nullptr, |
99 | MemorySSAUpdater *MSSAU = nullptr, |
100 | ScalarEvolution *SE = nullptr) const; |
101 | |
102 | /// Check to see if the loop has a canonical induction variable: an integer |
103 | /// recurrence that starts at 0 and increments by one each time through the |
104 | /// loop. If so, return the phi node that corresponds to it. |
105 | /// |
106 | /// The IndVarSimplify pass transforms loops to have a canonical induction |
107 | /// variable. |
108 | /// |
109 | PHINode *getCanonicalInductionVariable() const; |
110 | |
111 | /// Get the latch condition instruction. |
112 | ICmpInst *getLatchCmpInst() const; |
113 | |
114 | /// Obtain the unique incoming and back edge. Return false if they are |
115 | /// non-unique or the loop is dead; otherwise, return true. |
116 | bool getIncomingAndBackEdge(BasicBlock *&Incoming, |
117 | BasicBlock *&Backedge) const; |
118 | |
119 | /// Below are some utilities to get the loop guard, loop bounds and induction |
120 | /// variable, and to check if a given phinode is an auxiliary induction |
121 | /// variable, if the loop is guarded, and if the loop is canonical. |
122 | /// |
123 | /// Here is an example: |
124 | /// \code |
125 | /// for (int i = lb; i < ub; i+=step) |
126 | /// <loop body> |
127 | /// --- pseudo LLVMIR --- |
128 | /// beforeloop: |
129 | /// guardcmp = (lb < ub) |
130 | /// if (guardcmp) goto preheader; else goto afterloop |
131 | /// preheader: |
132 | /// loop: |
133 | /// i_1 = phi[{lb, preheader}, {i_2, latch}] |
134 | /// <loop body> |
135 | /// i_2 = i_1 + step |
136 | /// latch: |
137 | /// cmp = (i_2 < ub) |
138 | /// if (cmp) goto loop |
139 | /// exit: |
140 | /// afterloop: |
141 | /// \endcode |
142 | /// |
143 | /// - getBounds |
144 | /// - getInitialIVValue --> lb |
145 | /// - getStepInst --> i_2 = i_1 + step |
146 | /// - getStepValue --> step |
147 | /// - getFinalIVValue --> ub |
148 | /// - getCanonicalPredicate --> '<' |
149 | /// - getDirection --> Increasing |
150 | /// |
151 | /// - getInductionVariable --> i_1 |
152 | /// - isAuxiliaryInductionVariable(x) --> true if x == i_1 |
153 | /// - getLoopGuardBranch() |
154 | /// --> `if (guardcmp) goto preheader; else goto afterloop` |
155 | /// - isGuarded() --> true |
156 | /// - isCanonical --> false |
157 | struct LoopBounds { |
158 | /// Return the LoopBounds object if |
159 | /// - the given \p IndVar is an induction variable |
160 | /// - the initial value of the induction variable can be found |
161 | /// - the step instruction of the induction variable can be found |
162 | /// - the final value of the induction variable can be found |
163 | /// |
164 | /// Else std::nullopt. |
165 | static std::optional<Loop::LoopBounds> |
166 | getBounds(const Loop &L, PHINode &IndVar, ScalarEvolution &SE); |
167 | |
168 | /// Get the initial value of the loop induction variable. |
169 | Value &getInitialIVValue() const { return InitialIVValue; } |
170 | |
171 | /// Get the instruction that updates the loop induction variable. |
172 | Instruction &getStepInst() const { return StepInst; } |
173 | |
174 | /// Get the step that the loop induction variable gets updated by in each |
175 | /// loop iteration. Return nullptr if not found. |
176 | Value *getStepValue() const { return StepValue; } |
177 | |
178 | /// Get the final value of the loop induction variable. |
179 | Value &getFinalIVValue() const { return FinalIVValue; } |
180 | |
181 | /// Return the canonical predicate for the latch compare instruction, if |
182 | /// able to be calcuated. Else BAD_ICMP_PREDICATE. |
183 | /// |
184 | /// A predicate is considered as canonical if requirements below are all |
185 | /// satisfied: |
186 | /// 1. The first successor of the latch branch is the loop header |
187 | /// If not, inverse the predicate. |
188 | /// 2. One of the operands of the latch comparison is StepInst |
189 | /// If not, and |
190 | /// - if the current calcuated predicate is not ne or eq, flip the |
191 | /// predicate. |
192 | /// - else if the loop is increasing, return slt |
193 | /// (notice that it is safe to change from ne or eq to sign compare) |
194 | /// - else if the loop is decreasing, return sgt |
195 | /// (notice that it is safe to change from ne or eq to sign compare) |
196 | /// |
197 | /// Here is an example when both (1) and (2) are not satisfied: |
198 | /// \code |
199 | /// loop.header: |
200 | /// %iv = phi [%initialiv, %loop.preheader], [%inc, %loop.header] |
201 | /// %inc = add %iv, %step |
202 | /// %cmp = slt %iv, %finaliv |
203 | /// br %cmp, %loop.exit, %loop.header |
204 | /// loop.exit: |
205 | /// \endcode |
206 | /// - The second successor of the latch branch is the loop header instead |
207 | /// of the first successor (slt -> sge) |
208 | /// - The first operand of the latch comparison (%cmp) is the IndVar (%iv) |
209 | /// instead of the StepInst (%inc) (sge -> sgt) |
210 | /// |
211 | /// The predicate would be sgt if both (1) and (2) are satisfied. |
212 | /// getCanonicalPredicate() returns sgt for this example. |
213 | /// Note: The IR is not changed. |
214 | ICmpInst::Predicate getCanonicalPredicate() const; |
215 | |
216 | /// An enum for the direction of the loop |
217 | /// - for (int i = 0; i < ub; ++i) --> Increasing |
218 | /// - for (int i = ub; i > 0; --i) --> Descresing |
219 | /// - for (int i = x; i != y; i+=z) --> Unknown |
220 | enum class Direction { Increasing, Decreasing, Unknown }; |
221 | |
222 | /// Get the direction of the loop. |
223 | Direction getDirection() const; |
224 | |
225 | private: |
226 | LoopBounds(const Loop &Loop, Value &I, Instruction &SI, Value *SV, Value &F, |
227 | ScalarEvolution &SE) |
228 | : L(Loop), InitialIVValue(I), StepInst(SI), StepValue(SV), |
229 | FinalIVValue(F), SE(SE) {} |
230 | |
231 | const Loop &L; |
232 | |
233 | // The initial value of the loop induction variable |
234 | Value &InitialIVValue; |
235 | |
236 | // The instruction that updates the loop induction variable |
237 | Instruction &StepInst; |
238 | |
239 | // The value that the loop induction variable gets updated by in each loop |
240 | // iteration |
241 | Value *StepValue; |
242 | |
243 | // The final value of the loop induction variable |
244 | Value &FinalIVValue; |
245 | |
246 | ScalarEvolution &SE; |
247 | }; |
248 | |
249 | /// Return the struct LoopBounds collected if all struct members are found, |
250 | /// else std::nullopt. |
251 | std::optional<LoopBounds> getBounds(ScalarEvolution &SE) const; |
252 | |
253 | /// Return the loop induction variable if found, else return nullptr. |
254 | /// An instruction is considered as the loop induction variable if |
255 | /// - it is an induction variable of the loop; and |
256 | /// - it is used to determine the condition of the branch in the loop latch |
257 | /// |
258 | /// Note: the induction variable doesn't need to be canonical, i.e. starts at |
259 | /// zero and increments by one each time through the loop (but it can be). |
260 | PHINode *getInductionVariable(ScalarEvolution &SE) const; |
261 | |
262 | /// Get the loop induction descriptor for the loop induction variable. Return |
263 | /// true if the loop induction variable is found. |
264 | bool getInductionDescriptor(ScalarEvolution &SE, |
265 | InductionDescriptor &IndDesc) const; |
266 | |
267 | /// Return true if the given PHINode \p AuxIndVar is |
268 | /// - in the loop header |
269 | /// - not used outside of the loop |
270 | /// - incremented by a loop invariant step for each loop iteration |
271 | /// - step instruction opcode should be add or sub |
272 | /// Note: auxiliary induction variable is not required to be used in the |
273 | /// conditional branch in the loop latch. (but it can be) |
274 | bool isAuxiliaryInductionVariable(PHINode &AuxIndVar, |
275 | ScalarEvolution &SE) const; |
276 | |
277 | /// Return the loop guard branch, if it exists. |
278 | /// |
279 | /// This currently only works on simplified loop, as it requires a preheader |
280 | /// and a latch to identify the guard. It will work on loops of the form: |
281 | /// \code |
282 | /// GuardBB: |
283 | /// br cond1, Preheader, ExitSucc <== GuardBranch |
284 | /// Preheader: |
285 | /// br Header |
286 | /// Header: |
287 | /// ... |
288 | /// br Latch |
289 | /// Latch: |
290 | /// br cond2, Header, ExitBlock |
291 | /// ExitBlock: |
292 | /// br ExitSucc |
293 | /// ExitSucc: |
294 | /// \endcode |
295 | BranchInst *getLoopGuardBranch() const; |
296 | |
297 | /// Return true iff the loop is |
298 | /// - in simplify rotated form, and |
299 | /// - guarded by a loop guard branch. |
300 | bool isGuarded() const { return (getLoopGuardBranch() != nullptr); } |
301 | |
302 | /// Return true if the loop is in rotated form. |
303 | /// |
304 | /// This does not check if the loop was rotated by loop rotation, instead it |
305 | /// only checks if the loop is in rotated form (has a valid latch that exists |
306 | /// the loop). |
307 | bool isRotatedForm() const { |
308 | assert(!isInvalid() && "Loop not in a valid state!" ); |
309 | BasicBlock *Latch = getLoopLatch(); |
310 | return Latch && isLoopExiting(BB: Latch); |
311 | } |
312 | |
313 | /// Return true if the loop induction variable starts at zero and increments |
314 | /// by one each time through the loop. |
315 | bool isCanonical(ScalarEvolution &SE) const; |
316 | |
317 | /// Return true if the Loop is in LCSSA form. If \p IgnoreTokens is set to |
318 | /// true, token values defined inside loop are allowed to violate LCSSA form. |
319 | bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens = true) const; |
320 | |
321 | /// Return true if this Loop and all inner subloops are in LCSSA form. If \p |
322 | /// IgnoreTokens is set to true, token values defined inside loop are allowed |
323 | /// to violate LCSSA form. |
324 | bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI, |
325 | bool IgnoreTokens = true) const; |
326 | |
327 | /// Return true if the Loop is in the form that the LoopSimplify form |
328 | /// transforms loops to, which is sometimes called normal form. |
329 | bool isLoopSimplifyForm() const; |
330 | |
331 | /// Return true if the loop body is safe to clone in practice. |
332 | bool isSafeToClone() const; |
333 | |
334 | /// Returns true if the loop is annotated parallel. |
335 | /// |
336 | /// A parallel loop can be assumed to not contain any dependencies between |
337 | /// iterations by the compiler. That is, any loop-carried dependency checking |
338 | /// can be skipped completely when parallelizing the loop on the target |
339 | /// machine. Thus, if the parallel loop information originates from the |
340 | /// programmer, e.g. via the OpenMP parallel for pragma, it is the |
341 | /// programmer's responsibility to ensure there are no loop-carried |
342 | /// dependencies. The final execution order of the instructions across |
343 | /// iterations is not guaranteed, thus, the end result might or might not |
344 | /// implement actual concurrent execution of instructions across multiple |
345 | /// iterations. |
346 | bool isAnnotatedParallel() const; |
347 | |
348 | /// Return the llvm.loop loop id metadata node for this loop if it is present. |
349 | /// |
350 | /// If this loop contains the same llvm.loop metadata on each branch to the |
351 | /// header then the node is returned. If any latch instruction does not |
352 | /// contain llvm.loop or if multiple latches contain different nodes then |
353 | /// 0 is returned. |
354 | MDNode *getLoopID() const; |
355 | /// Set the llvm.loop loop id metadata for this loop. |
356 | /// |
357 | /// The LoopID metadata node will be added to each terminator instruction in |
358 | /// the loop that branches to the loop header. |
359 | /// |
360 | /// The LoopID metadata node should have one or more operands and the first |
361 | /// operand should be the node itself. |
362 | void setLoopID(MDNode *LoopID) const; |
363 | |
364 | /// Add llvm.loop.unroll.disable to this loop's loop id metadata. |
365 | /// |
366 | /// Remove existing unroll metadata and add unroll disable metadata to |
367 | /// indicate the loop has already been unrolled. This prevents a loop |
368 | /// from being unrolled more than is directed by a pragma if the loop |
369 | /// unrolling pass is run more than once (which it generally is). |
370 | void setLoopAlreadyUnrolled(); |
371 | |
372 | /// Add llvm.loop.mustprogress to this loop's loop id metadata. |
373 | void setLoopMustProgress(); |
374 | |
375 | void dump() const; |
376 | void dumpVerbose() const; |
377 | |
378 | /// Return the debug location of the start of this loop. |
379 | /// This looks for a BB terminating instruction with a known debug |
380 | /// location by looking at the preheader and header blocks. If it |
381 | /// cannot find a terminating instruction with location information, |
382 | /// it returns an unknown location. |
383 | DebugLoc getStartLoc() const; |
384 | |
385 | /// Return the source code span of the loop. |
386 | LocRange getLocRange() const; |
387 | |
388 | StringRef getName() const { |
389 | if (BasicBlock * = getHeader()) |
390 | if (Header->hasName()) |
391 | return Header->getName(); |
392 | return "<unnamed loop>" ; |
393 | } |
394 | |
395 | private: |
396 | Loop() = default; |
397 | |
398 | friend class LoopInfoBase<BasicBlock, Loop>; |
399 | friend class LoopBase<BasicBlock, Loop>; |
400 | explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {} |
401 | ~Loop() = default; |
402 | }; |
403 | |
404 | // Implementation in Support/GenericLoopInfoImpl.h |
405 | extern template class LoopInfoBase<BasicBlock, Loop>; |
406 | |
407 | class LoopInfo : public LoopInfoBase<BasicBlock, Loop> { |
408 | typedef LoopInfoBase<BasicBlock, Loop> BaseT; |
409 | |
410 | friend class LoopBase<BasicBlock, Loop>; |
411 | |
412 | void operator=(const LoopInfo &) = delete; |
413 | LoopInfo(const LoopInfo &) = delete; |
414 | |
415 | public: |
416 | LoopInfo() = default; |
417 | explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree); |
418 | |
419 | LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {} |
420 | LoopInfo &operator=(LoopInfo &&RHS) { |
421 | BaseT::operator=(RHS: std::move(static_cast<BaseT &>(RHS))); |
422 | return *this; |
423 | } |
424 | |
425 | /// Handle invalidation explicitly. |
426 | bool invalidate(Function &F, const PreservedAnalyses &PA, |
427 | FunctionAnalysisManager::Invalidator &); |
428 | |
429 | // Most of the public interface is provided via LoopInfoBase. |
430 | |
431 | /// Update LoopInfo after removing the last backedge from a loop. This updates |
432 | /// the loop forest and parent loops for each block so that \c L is no longer |
433 | /// referenced, but does not actually delete \c L immediately. The pointer |
434 | /// will remain valid until this LoopInfo's memory is released. |
435 | void erase(Loop *L); |
436 | |
437 | /// Returns true if replacing From with To everywhere is guaranteed to |
438 | /// preserve LCSSA form. |
439 | bool replacementPreservesLCSSAForm(Instruction *From, Value *To) { |
440 | // Preserving LCSSA form is only problematic if the replacing value is an |
441 | // instruction. |
442 | Instruction *I = dyn_cast<Instruction>(Val: To); |
443 | if (!I) |
444 | return true; |
445 | // If both instructions are defined in the same basic block then replacement |
446 | // cannot break LCSSA form. |
447 | if (I->getParent() == From->getParent()) |
448 | return true; |
449 | // If the instruction is not defined in a loop then it can safely replace |
450 | // anything. |
451 | Loop *ToLoop = getLoopFor(BB: I->getParent()); |
452 | if (!ToLoop) |
453 | return true; |
454 | // If the replacing instruction is defined in the same loop as the original |
455 | // instruction, or in a loop that contains it as an inner loop, then using |
456 | // it as a replacement will not break LCSSA form. |
457 | return ToLoop->contains(L: getLoopFor(BB: From->getParent())); |
458 | } |
459 | |
460 | /// Checks if moving a specific instruction can break LCSSA in any loop. |
461 | /// |
462 | /// Return true if moving \p Inst to before \p NewLoc will break LCSSA, |
463 | /// assuming that the function containing \p Inst and \p NewLoc is currently |
464 | /// in LCSSA form. |
465 | bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) { |
466 | assert(Inst->getFunction() == NewLoc->getFunction() && |
467 | "Can't reason about IPO!" ); |
468 | |
469 | auto *OldBB = Inst->getParent(); |
470 | auto *NewBB = NewLoc->getParent(); |
471 | |
472 | // Movement within the same loop does not break LCSSA (the equality check is |
473 | // to avoid doing a hashtable lookup in case of intra-block movement). |
474 | if (OldBB == NewBB) |
475 | return true; |
476 | |
477 | auto *OldLoop = getLoopFor(BB: OldBB); |
478 | auto *NewLoop = getLoopFor(BB: NewBB); |
479 | |
480 | if (OldLoop == NewLoop) |
481 | return true; |
482 | |
483 | // Check if Outer contains Inner; with the null loop counting as the |
484 | // "outermost" loop. |
485 | auto Contains = [](const Loop *Outer, const Loop *Inner) { |
486 | return !Outer || Outer->contains(L: Inner); |
487 | }; |
488 | |
489 | // To check that the movement of Inst to before NewLoc does not break LCSSA, |
490 | // we need to check two sets of uses for possible LCSSA violations at |
491 | // NewLoc: the users of NewInst, and the operands of NewInst. |
492 | |
493 | // If we know we're hoisting Inst out of an inner loop to an outer loop, |
494 | // then the uses *of* Inst don't need to be checked. |
495 | |
496 | if (!Contains(NewLoop, OldLoop)) { |
497 | for (Use &U : Inst->uses()) { |
498 | auto *UI = cast<Instruction>(Val: U.getUser()); |
499 | auto *UBB = isa<PHINode>(Val: UI) ? cast<PHINode>(Val: UI)->getIncomingBlock(U) |
500 | : UI->getParent(); |
501 | if (UBB != NewBB && getLoopFor(BB: UBB) != NewLoop) |
502 | return false; |
503 | } |
504 | } |
505 | |
506 | // If we know we're sinking Inst from an outer loop into an inner loop, then |
507 | // the *operands* of Inst don't need to be checked. |
508 | |
509 | if (!Contains(OldLoop, NewLoop)) { |
510 | // See below on why we can't handle phi nodes here. |
511 | if (isa<PHINode>(Val: Inst)) |
512 | return false; |
513 | |
514 | for (Use &U : Inst->operands()) { |
515 | auto *DefI = dyn_cast<Instruction>(Val: U.get()); |
516 | if (!DefI) |
517 | return false; |
518 | |
519 | // This would need adjustment if we allow Inst to be a phi node -- the |
520 | // new use block won't simply be NewBB. |
521 | |
522 | auto *DefBlock = DefI->getParent(); |
523 | if (DefBlock != NewBB && getLoopFor(BB: DefBlock) != NewLoop) |
524 | return false; |
525 | } |
526 | } |
527 | |
528 | return true; |
529 | } |
530 | |
531 | // Return true if a new use of V added in ExitBB would require an LCSSA PHI |
532 | // to be inserted at the begining of the block. Note that V is assumed to |
533 | // dominate ExitBB, and ExitBB must be the exit block of some loop. The |
534 | // IR is assumed to be in LCSSA form before the planned insertion. |
535 | bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, |
536 | const BasicBlock *ExitBB) const; |
537 | }; |
538 | |
539 | /// Enable verification of loop info. |
540 | /// |
541 | /// The flag enables checks which are expensive and are disabled by default |
542 | /// unless the `EXPENSIVE_CHECKS` macro is defined. The `-verify-loop-info` |
543 | /// flag allows the checks to be enabled selectively without re-compilation. |
544 | extern bool VerifyLoopInfo; |
545 | |
546 | // Allow clients to walk the list of nested loops... |
547 | template <> struct GraphTraits<const Loop *> { |
548 | typedef const Loop *NodeRef; |
549 | typedef LoopInfo::iterator ChildIteratorType; |
550 | |
551 | static NodeRef getEntryNode(const Loop *L) { return L; } |
552 | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
553 | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
554 | }; |
555 | |
556 | template <> struct GraphTraits<Loop *> { |
557 | typedef Loop *NodeRef; |
558 | typedef LoopInfo::iterator ChildIteratorType; |
559 | |
560 | static NodeRef getEntryNode(Loop *L) { return L; } |
561 | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
562 | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
563 | }; |
564 | |
565 | /// Analysis pass that exposes the \c LoopInfo for a function. |
566 | class LoopAnalysis : public AnalysisInfoMixin<LoopAnalysis> { |
567 | friend AnalysisInfoMixin<LoopAnalysis>; |
568 | static AnalysisKey Key; |
569 | |
570 | public: |
571 | typedef LoopInfo Result; |
572 | |
573 | LoopInfo run(Function &F, FunctionAnalysisManager &AM); |
574 | }; |
575 | |
576 | /// Printer pass for the \c LoopAnalysis results. |
577 | class LoopPrinterPass : public PassInfoMixin<LoopPrinterPass> { |
578 | raw_ostream &OS; |
579 | |
580 | public: |
581 | explicit LoopPrinterPass(raw_ostream &OS) : OS(OS) {} |
582 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
583 | static bool isRequired() { return true; } |
584 | }; |
585 | |
586 | /// Verifier pass for the \c LoopAnalysis results. |
587 | struct LoopVerifierPass : public PassInfoMixin<LoopVerifierPass> { |
588 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
589 | static bool isRequired() { return true; } |
590 | }; |
591 | |
592 | /// The legacy pass manager's analysis pass to compute loop information. |
593 | class LoopInfoWrapperPass : public FunctionPass { |
594 | LoopInfo LI; |
595 | |
596 | public: |
597 | static char ID; // Pass identification, replacement for typeid |
598 | |
599 | LoopInfoWrapperPass(); |
600 | |
601 | LoopInfo &getLoopInfo() { return LI; } |
602 | const LoopInfo &getLoopInfo() const { return LI; } |
603 | |
604 | /// Calculate the natural loop information for a given function. |
605 | bool runOnFunction(Function &F) override; |
606 | |
607 | void verifyAnalysis() const override; |
608 | |
609 | void releaseMemory() override { LI.releaseMemory(); } |
610 | |
611 | void print(raw_ostream &O, const Module *M = nullptr) const override; |
612 | |
613 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
614 | }; |
615 | |
616 | /// Function to print a loop's contents as LLVM's text IR assembly. |
617 | void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = "" ); |
618 | |
619 | /// Find and return the loop attribute node for the attribute @p Name in |
620 | /// @p LoopID. Return nullptr if there is no such attribute. |
621 | MDNode *findOptionMDForLoopID(MDNode *LoopID, StringRef Name); |
622 | |
623 | /// Find string metadata for a loop. |
624 | /// |
625 | /// Returns the MDNode where the first operand is the metadata's name. The |
626 | /// following operands are the metadata's values. If no metadata with @p Name is |
627 | /// found, return nullptr. |
628 | MDNode *findOptionMDForLoop(const Loop *TheLoop, StringRef Name); |
629 | |
630 | std::optional<bool> getOptionalBoolLoopAttribute(const Loop *TheLoop, |
631 | StringRef Name); |
632 | |
633 | /// Returns true if Name is applied to TheLoop and enabled. |
634 | bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name); |
635 | |
636 | /// Find named metadata for a loop with an integer value. |
637 | std::optional<int> getOptionalIntLoopAttribute(const Loop *TheLoop, |
638 | StringRef Name); |
639 | |
640 | /// Find named metadata for a loop with an integer value. Return \p Default if |
641 | /// not set. |
642 | int getIntLoopAttribute(const Loop *TheLoop, StringRef Name, int Default = 0); |
643 | |
644 | /// Find string metadata for loop |
645 | /// |
646 | /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an |
647 | /// operand or null otherwise. If the string metadata is not found return |
648 | /// Optional's not-a-value. |
649 | std::optional<const MDOperand *> findStringMetadataForLoop(const Loop *TheLoop, |
650 | StringRef Name); |
651 | |
652 | /// Look for the loop attribute that requires progress within the loop. |
653 | /// Note: Most consumers probably want "isMustProgress" which checks |
654 | /// the containing function attribute too. |
655 | bool hasMustProgress(const Loop *L); |
656 | |
657 | /// Return true if this loop can be assumed to make progress. (i.e. can't |
658 | /// be infinite without side effects without also being undefined) |
659 | bool isMustProgress(const Loop *L); |
660 | |
661 | /// Return true if this loop can be assumed to run for a finite number of |
662 | /// iterations. |
663 | bool isFinite(const Loop *L); |
664 | |
665 | /// Return whether an MDNode might represent an access group. |
666 | /// |
667 | /// Access group metadata nodes have to be distinct and empty. Being |
668 | /// always-empty ensures that it never needs to be changed (which -- because |
669 | /// MDNodes are designed immutable -- would require creating a new MDNode). Note |
670 | /// that this is not a sufficient condition: not every distinct and empty NDNode |
671 | /// is representing an access group. |
672 | bool isValidAsAccessGroup(MDNode *AccGroup); |
673 | |
674 | /// Create a new LoopID after the loop has been transformed. |
675 | /// |
676 | /// This can be used when no follow-up loop attributes are defined |
677 | /// (llvm::makeFollowupLoopID returning None) to stop transformations to be |
678 | /// applied again. |
679 | /// |
680 | /// @param Context The LLVMContext in which to create the new LoopID. |
681 | /// @param OrigLoopID The original LoopID; can be nullptr if the original |
682 | /// loop has no LoopID. |
683 | /// @param RemovePrefixes Remove all loop attributes that have these prefixes. |
684 | /// Use to remove metadata of the transformation that has |
685 | /// been applied. |
686 | /// @param AddAttrs Add these loop attributes to the new LoopID. |
687 | /// |
688 | /// @return A new LoopID that can be applied using Loop::setLoopID(). |
689 | llvm::MDNode * |
690 | makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID, |
691 | llvm::ArrayRef<llvm::StringRef> RemovePrefixes, |
692 | llvm::ArrayRef<llvm::MDNode *> AddAttrs); |
693 | |
694 | } // namespace llvm |
695 | |
696 | #endif |
697 | |