1 | //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===// |
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 defines the LoopInfo class that is used to identify natural loops |
10 | // and determine the loop depth of various nodes of the CFG. Note that the |
11 | // loops identified may actually be several natural loops that share the same |
12 | // header node... not just a single natural loop. |
13 | // |
14 | //===----------------------------------------------------------------------===// |
15 | |
16 | #include "llvm/Analysis/LoopInfo.h" |
17 | #include "llvm/ADT/ScopeExit.h" |
18 | #include "llvm/ADT/SmallPtrSet.h" |
19 | #include "llvm/Analysis/IVDescriptors.h" |
20 | #include "llvm/Analysis/LoopIterator.h" |
21 | #include "llvm/Analysis/LoopNestAnalysis.h" |
22 | #include "llvm/Analysis/MemorySSA.h" |
23 | #include "llvm/Analysis/MemorySSAUpdater.h" |
24 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
25 | #include "llvm/Analysis/ValueTracking.h" |
26 | #include "llvm/Config/llvm-config.h" |
27 | #include "llvm/IR/CFG.h" |
28 | #include "llvm/IR/Constants.h" |
29 | #include "llvm/IR/DebugLoc.h" |
30 | #include "llvm/IR/Dominators.h" |
31 | #include "llvm/IR/Instructions.h" |
32 | #include "llvm/IR/LLVMContext.h" |
33 | #include "llvm/IR/Metadata.h" |
34 | #include "llvm/IR/PassManager.h" |
35 | #include "llvm/IR/PrintPasses.h" |
36 | #include "llvm/InitializePasses.h" |
37 | #include "llvm/Support/CommandLine.h" |
38 | #include "llvm/Support/GenericLoopInfoImpl.h" |
39 | #include "llvm/Support/raw_ostream.h" |
40 | using namespace llvm; |
41 | |
42 | // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops. |
43 | template class llvm::LoopBase<BasicBlock, Loop>; |
44 | template class llvm::LoopInfoBase<BasicBlock, Loop>; |
45 | |
46 | // Always verify loopinfo if expensive checking is enabled. |
47 | #ifdef EXPENSIVE_CHECKS |
48 | bool llvm::VerifyLoopInfo = true; |
49 | #else |
50 | bool llvm::VerifyLoopInfo = false; |
51 | #endif |
52 | static cl::opt<bool, true> |
53 | VerifyLoopInfoX("verify-loop-info" , cl::location(L&: VerifyLoopInfo), |
54 | cl::Hidden, cl::desc("Verify loop info (time consuming)" )); |
55 | |
56 | //===----------------------------------------------------------------------===// |
57 | // Loop implementation |
58 | // |
59 | |
60 | bool Loop::isLoopInvariant(const Value *V) const { |
61 | if (const Instruction *I = dyn_cast<Instruction>(Val: V)) |
62 | return !contains(Inst: I); |
63 | return true; // All non-instructions are loop invariant |
64 | } |
65 | |
66 | bool Loop::hasLoopInvariantOperands(const Instruction *I) const { |
67 | return all_of(Range: I->operands(), P: [this](Value *V) { return isLoopInvariant(V); }); |
68 | } |
69 | |
70 | bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt, |
71 | MemorySSAUpdater *MSSAU, |
72 | ScalarEvolution *SE) const { |
73 | if (Instruction *I = dyn_cast<Instruction>(Val: V)) |
74 | return makeLoopInvariant(I, Changed, InsertPt, MSSAU, SE); |
75 | return true; // All non-instructions are loop-invariant. |
76 | } |
77 | |
78 | bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, |
79 | Instruction *InsertPt, MemorySSAUpdater *MSSAU, |
80 | ScalarEvolution *SE) const { |
81 | // Test if the value is already loop-invariant. |
82 | if (isLoopInvariant(V: I)) |
83 | return true; |
84 | if (!isSafeToSpeculativelyExecute(I)) |
85 | return false; |
86 | if (I->mayReadFromMemory()) |
87 | return false; |
88 | // EH block instructions are immobile. |
89 | if (I->isEHPad()) |
90 | return false; |
91 | // Determine the insertion point, unless one was given. |
92 | if (!InsertPt) { |
93 | BasicBlock * = getLoopPreheader(); |
94 | // Without a preheader, hoisting is not feasible. |
95 | if (!Preheader) |
96 | return false; |
97 | InsertPt = Preheader->getTerminator(); |
98 | } |
99 | // Don't hoist instructions with loop-variant operands. |
100 | for (Value *Operand : I->operands()) |
101 | if (!makeLoopInvariant(V: Operand, Changed, InsertPt, MSSAU, SE)) |
102 | return false; |
103 | |
104 | // Hoist. |
105 | I->moveBefore(MovePos: InsertPt); |
106 | if (MSSAU) |
107 | if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I)) |
108 | MSSAU->moveToPlace(What: MUD, BB: InsertPt->getParent(), |
109 | Where: MemorySSA::BeforeTerminator); |
110 | |
111 | // There is possibility of hoisting this instruction above some arbitrary |
112 | // condition. Any metadata defined on it can be control dependent on this |
113 | // condition. Conservatively strip it here so that we don't give any wrong |
114 | // information to the optimizer. |
115 | I->dropUnknownNonDebugMetadata(); |
116 | |
117 | if (SE) |
118 | SE->forgetBlockAndLoopDispositions(V: I); |
119 | |
120 | Changed = true; |
121 | return true; |
122 | } |
123 | |
124 | bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming, |
125 | BasicBlock *&Backedge) const { |
126 | BasicBlock *H = getHeader(); |
127 | |
128 | Incoming = nullptr; |
129 | Backedge = nullptr; |
130 | pred_iterator PI = pred_begin(BB: H); |
131 | assert(PI != pred_end(H) && "Loop must have at least one backedge!" ); |
132 | Backedge = *PI++; |
133 | if (PI == pred_end(BB: H)) |
134 | return false; // dead loop |
135 | Incoming = *PI++; |
136 | if (PI != pred_end(BB: H)) |
137 | return false; // multiple backedges? |
138 | |
139 | if (contains(BB: Incoming)) { |
140 | if (contains(BB: Backedge)) |
141 | return false; |
142 | std::swap(a&: Incoming, b&: Backedge); |
143 | } else if (!contains(BB: Backedge)) |
144 | return false; |
145 | |
146 | assert(Incoming && Backedge && "expected non-null incoming and backedges" ); |
147 | return true; |
148 | } |
149 | |
150 | PHINode *Loop::getCanonicalInductionVariable() const { |
151 | BasicBlock *H = getHeader(); |
152 | |
153 | BasicBlock *Incoming = nullptr, *Backedge = nullptr; |
154 | if (!getIncomingAndBackEdge(Incoming, Backedge)) |
155 | return nullptr; |
156 | |
157 | // Loop over all of the PHI nodes, looking for a canonical indvar. |
158 | for (BasicBlock::iterator I = H->begin(); isa<PHINode>(Val: I); ++I) { |
159 | PHINode *PN = cast<PHINode>(Val&: I); |
160 | if (ConstantInt *CI = |
161 | dyn_cast<ConstantInt>(Val: PN->getIncomingValueForBlock(BB: Incoming))) |
162 | if (CI->isZero()) |
163 | if (Instruction *Inc = |
164 | dyn_cast<Instruction>(Val: PN->getIncomingValueForBlock(BB: Backedge))) |
165 | if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(i: 0) == PN) |
166 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: Inc->getOperand(i: 1))) |
167 | if (CI->isOne()) |
168 | return PN; |
169 | } |
170 | return nullptr; |
171 | } |
172 | |
173 | /// Get the latch condition instruction. |
174 | ICmpInst *Loop::getLatchCmpInst() const { |
175 | if (BasicBlock *Latch = getLoopLatch()) |
176 | if (BranchInst *BI = dyn_cast_or_null<BranchInst>(Val: Latch->getTerminator())) |
177 | if (BI->isConditional()) |
178 | return dyn_cast<ICmpInst>(Val: BI->getCondition()); |
179 | |
180 | return nullptr; |
181 | } |
182 | |
183 | /// Return the final value of the loop induction variable if found. |
184 | static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar, |
185 | const Instruction &StepInst) { |
186 | ICmpInst *LatchCmpInst = L.getLatchCmpInst(); |
187 | if (!LatchCmpInst) |
188 | return nullptr; |
189 | |
190 | Value *Op0 = LatchCmpInst->getOperand(i_nocapture: 0); |
191 | Value *Op1 = LatchCmpInst->getOperand(i_nocapture: 1); |
192 | if (Op0 == &IndVar || Op0 == &StepInst) |
193 | return Op1; |
194 | |
195 | if (Op1 == &IndVar || Op1 == &StepInst) |
196 | return Op0; |
197 | |
198 | return nullptr; |
199 | } |
200 | |
201 | std::optional<Loop::LoopBounds> |
202 | Loop::LoopBounds::getBounds(const Loop &L, PHINode &IndVar, |
203 | ScalarEvolution &SE) { |
204 | InductionDescriptor IndDesc; |
205 | if (!InductionDescriptor::isInductionPHI(Phi: &IndVar, L: &L, SE: &SE, D&: IndDesc)) |
206 | return std::nullopt; |
207 | |
208 | Value *InitialIVValue = IndDesc.getStartValue(); |
209 | Instruction *StepInst = IndDesc.getInductionBinOp(); |
210 | if (!InitialIVValue || !StepInst) |
211 | return std::nullopt; |
212 | |
213 | const SCEV *Step = IndDesc.getStep(); |
214 | Value *StepInstOp1 = StepInst->getOperand(i: 1); |
215 | Value *StepInstOp0 = StepInst->getOperand(i: 0); |
216 | Value *StepValue = nullptr; |
217 | if (SE.getSCEV(V: StepInstOp1) == Step) |
218 | StepValue = StepInstOp1; |
219 | else if (SE.getSCEV(V: StepInstOp0) == Step) |
220 | StepValue = StepInstOp0; |
221 | |
222 | Value *FinalIVValue = findFinalIVValue(L, IndVar, StepInst: *StepInst); |
223 | if (!FinalIVValue) |
224 | return std::nullopt; |
225 | |
226 | return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue, |
227 | SE); |
228 | } |
229 | |
230 | using Direction = Loop::LoopBounds::Direction; |
231 | |
232 | ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const { |
233 | BasicBlock *Latch = L.getLoopLatch(); |
234 | assert(Latch && "Expecting valid latch" ); |
235 | |
236 | BranchInst *BI = dyn_cast_or_null<BranchInst>(Val: Latch->getTerminator()); |
237 | assert(BI && BI->isConditional() && "Expecting conditional latch branch" ); |
238 | |
239 | ICmpInst *LatchCmpInst = dyn_cast<ICmpInst>(Val: BI->getCondition()); |
240 | assert(LatchCmpInst && |
241 | "Expecting the latch compare instruction to be a CmpInst" ); |
242 | |
243 | // Need to inverse the predicate when first successor is not the loop |
244 | // header |
245 | ICmpInst::Predicate Pred = (BI->getSuccessor(i: 0) == L.getHeader()) |
246 | ? LatchCmpInst->getPredicate() |
247 | : LatchCmpInst->getInversePredicate(); |
248 | |
249 | if (LatchCmpInst->getOperand(i_nocapture: 0) == &getFinalIVValue()) |
250 | Pred = ICmpInst::getSwappedPredicate(pred: Pred); |
251 | |
252 | // Need to flip strictness of the predicate when the latch compare instruction |
253 | // is not using StepInst |
254 | if (LatchCmpInst->getOperand(i_nocapture: 0) == &getStepInst() || |
255 | LatchCmpInst->getOperand(i_nocapture: 1) == &getStepInst()) |
256 | return Pred; |
257 | |
258 | // Cannot flip strictness of NE and EQ |
259 | if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ) |
260 | return ICmpInst::getFlippedStrictnessPredicate(pred: Pred); |
261 | |
262 | Direction D = getDirection(); |
263 | if (D == Direction::Increasing) |
264 | return ICmpInst::ICMP_SLT; |
265 | |
266 | if (D == Direction::Decreasing) |
267 | return ICmpInst::ICMP_SGT; |
268 | |
269 | // If cannot determine the direction, then unable to find the canonical |
270 | // predicate |
271 | return ICmpInst::BAD_ICMP_PREDICATE; |
272 | } |
273 | |
274 | Direction Loop::LoopBounds::getDirection() const { |
275 | if (const SCEVAddRecExpr *StepAddRecExpr = |
276 | dyn_cast<SCEVAddRecExpr>(Val: SE.getSCEV(V: &getStepInst()))) |
277 | if (const SCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) { |
278 | if (SE.isKnownPositive(S: StepRecur)) |
279 | return Direction::Increasing; |
280 | if (SE.isKnownNegative(S: StepRecur)) |
281 | return Direction::Decreasing; |
282 | } |
283 | |
284 | return Direction::Unknown; |
285 | } |
286 | |
287 | std::optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const { |
288 | if (PHINode *IndVar = getInductionVariable(SE)) |
289 | return LoopBounds::getBounds(L: *this, IndVar&: *IndVar, SE); |
290 | |
291 | return std::nullopt; |
292 | } |
293 | |
294 | PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const { |
295 | if (!isLoopSimplifyForm()) |
296 | return nullptr; |
297 | |
298 | BasicBlock * = getHeader(); |
299 | assert(Header && "Expected a valid loop header" ); |
300 | ICmpInst *CmpInst = getLatchCmpInst(); |
301 | if (!CmpInst) |
302 | return nullptr; |
303 | |
304 | Value *LatchCmpOp0 = CmpInst->getOperand(i_nocapture: 0); |
305 | Value *LatchCmpOp1 = CmpInst->getOperand(i_nocapture: 1); |
306 | |
307 | for (PHINode &IndVar : Header->phis()) { |
308 | InductionDescriptor IndDesc; |
309 | if (!InductionDescriptor::isInductionPHI(Phi: &IndVar, L: this, SE: &SE, D&: IndDesc)) |
310 | continue; |
311 | |
312 | BasicBlock *Latch = getLoopLatch(); |
313 | Value *StepInst = IndVar.getIncomingValueForBlock(BB: Latch); |
314 | |
315 | // case 1: |
316 | // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}] |
317 | // StepInst = IndVar + step |
318 | // cmp = StepInst < FinalValue |
319 | if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1) |
320 | return &IndVar; |
321 | |
322 | // case 2: |
323 | // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}] |
324 | // StepInst = IndVar + step |
325 | // cmp = IndVar < FinalValue |
326 | if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1) |
327 | return &IndVar; |
328 | } |
329 | |
330 | return nullptr; |
331 | } |
332 | |
333 | bool Loop::getInductionDescriptor(ScalarEvolution &SE, |
334 | InductionDescriptor &IndDesc) const { |
335 | if (PHINode *IndVar = getInductionVariable(SE)) |
336 | return InductionDescriptor::isInductionPHI(Phi: IndVar, L: this, SE: &SE, D&: IndDesc); |
337 | |
338 | return false; |
339 | } |
340 | |
341 | bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar, |
342 | ScalarEvolution &SE) const { |
343 | // Located in the loop header |
344 | BasicBlock * = getHeader(); |
345 | if (AuxIndVar.getParent() != Header) |
346 | return false; |
347 | |
348 | // No uses outside of the loop |
349 | for (User *U : AuxIndVar.users()) |
350 | if (const Instruction *I = dyn_cast<Instruction>(Val: U)) |
351 | if (!contains(Inst: I)) |
352 | return false; |
353 | |
354 | InductionDescriptor IndDesc; |
355 | if (!InductionDescriptor::isInductionPHI(Phi: &AuxIndVar, L: this, SE: &SE, D&: IndDesc)) |
356 | return false; |
357 | |
358 | // The step instruction opcode should be add or sub. |
359 | if (IndDesc.getInductionOpcode() != Instruction::Add && |
360 | IndDesc.getInductionOpcode() != Instruction::Sub) |
361 | return false; |
362 | |
363 | // Incremented by a loop invariant step for each loop iteration |
364 | return SE.isLoopInvariant(S: IndDesc.getStep(), L: this); |
365 | } |
366 | |
367 | BranchInst *Loop::getLoopGuardBranch() const { |
368 | if (!isLoopSimplifyForm()) |
369 | return nullptr; |
370 | |
371 | BasicBlock * = getLoopPreheader(); |
372 | assert(Preheader && getLoopLatch() && |
373 | "Expecting a loop with valid preheader and latch" ); |
374 | |
375 | // Loop should be in rotate form. |
376 | if (!isRotatedForm()) |
377 | return nullptr; |
378 | |
379 | // Disallow loops with more than one unique exit block, as we do not verify |
380 | // that GuardOtherSucc post dominates all exit blocks. |
381 | BasicBlock *ExitFromLatch = getUniqueExitBlock(); |
382 | if (!ExitFromLatch) |
383 | return nullptr; |
384 | |
385 | BasicBlock *GuardBB = Preheader->getUniquePredecessor(); |
386 | if (!GuardBB) |
387 | return nullptr; |
388 | |
389 | assert(GuardBB->getTerminator() && "Expecting valid guard terminator" ); |
390 | |
391 | BranchInst *GuardBI = dyn_cast<BranchInst>(Val: GuardBB->getTerminator()); |
392 | if (!GuardBI || GuardBI->isUnconditional()) |
393 | return nullptr; |
394 | |
395 | BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(i: 0) == Preheader) |
396 | ? GuardBI->getSuccessor(i: 1) |
397 | : GuardBI->getSuccessor(i: 0); |
398 | |
399 | // Check if ExitFromLatch (or any BasicBlock which is an empty unique |
400 | // successor of ExitFromLatch) is equal to GuardOtherSucc. If |
401 | // skipEmptyBlockUntil returns GuardOtherSucc, then the guard branch for the |
402 | // loop is GuardBI (return GuardBI), otherwise return nullptr. |
403 | if (&LoopNest::skipEmptyBlockUntil(From: ExitFromLatch, End: GuardOtherSucc, |
404 | /*CheckUniquePred=*/true) == |
405 | GuardOtherSucc) |
406 | return GuardBI; |
407 | else |
408 | return nullptr; |
409 | } |
410 | |
411 | bool Loop::isCanonical(ScalarEvolution &SE) const { |
412 | InductionDescriptor IndDesc; |
413 | if (!getInductionDescriptor(SE, IndDesc)) |
414 | return false; |
415 | |
416 | ConstantInt *Init = dyn_cast_or_null<ConstantInt>(Val: IndDesc.getStartValue()); |
417 | if (!Init || !Init->isZero()) |
418 | return false; |
419 | |
420 | if (IndDesc.getInductionOpcode() != Instruction::Add) |
421 | return false; |
422 | |
423 | ConstantInt *Step = IndDesc.getConstIntStepValue(); |
424 | if (!Step || !Step->isOne()) |
425 | return false; |
426 | |
427 | return true; |
428 | } |
429 | |
430 | // Check that 'BB' doesn't have any uses outside of the 'L' |
431 | static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, |
432 | const DominatorTree &DT, bool IgnoreTokens) { |
433 | for (const Instruction &I : BB) { |
434 | // Tokens can't be used in PHI nodes and live-out tokens prevent loop |
435 | // optimizations, so for the purposes of considered LCSSA form, we |
436 | // can ignore them. |
437 | if (IgnoreTokens && I.getType()->isTokenTy()) |
438 | continue; |
439 | |
440 | for (const Use &U : I.uses()) { |
441 | const Instruction *UI = cast<Instruction>(Val: U.getUser()); |
442 | const BasicBlock *UserBB = UI->getParent(); |
443 | |
444 | // For practical purposes, we consider that the use in a PHI |
445 | // occurs in the respective predecessor block. For more info, |
446 | // see the `phi` doc in LangRef and the LCSSA doc. |
447 | if (const PHINode *P = dyn_cast<PHINode>(Val: UI)) |
448 | UserBB = P->getIncomingBlock(U); |
449 | |
450 | // Check the current block, as a fast-path, before checking whether |
451 | // the use is anywhere in the loop. Most values are used in the same |
452 | // block they are defined in. Also, blocks not reachable from the |
453 | // entry are special; uses in them don't need to go through PHIs. |
454 | if (UserBB != &BB && !L.contains(BB: UserBB) && |
455 | DT.isReachableFromEntry(A: UserBB)) |
456 | return false; |
457 | } |
458 | } |
459 | return true; |
460 | } |
461 | |
462 | bool Loop::isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens) const { |
463 | // For each block we check that it doesn't have any uses outside of this loop. |
464 | return all_of(Range: this->blocks(), P: [&](const BasicBlock *BB) { |
465 | return isBlockInLCSSAForm(L: *this, BB: *BB, DT, IgnoreTokens); |
466 | }); |
467 | } |
468 | |
469 | bool Loop::isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI, |
470 | bool IgnoreTokens) const { |
471 | // For each block we check that it doesn't have any uses outside of its |
472 | // innermost loop. This process will transitively guarantee that the current |
473 | // loop and all of the nested loops are in LCSSA form. |
474 | return all_of(Range: this->blocks(), P: [&](const BasicBlock *BB) { |
475 | return isBlockInLCSSAForm(L: *LI.getLoopFor(BB), BB: *BB, DT, IgnoreTokens); |
476 | }); |
477 | } |
478 | |
479 | bool Loop::isLoopSimplifyForm() const { |
480 | // Normal-form loops have a preheader, a single backedge, and all of their |
481 | // exits have all their predecessors inside the loop. |
482 | return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); |
483 | } |
484 | |
485 | // Routines that reform the loop CFG and split edges often fail on indirectbr. |
486 | bool Loop::isSafeToClone() const { |
487 | // Return false if any loop blocks contain indirectbrs, or there are any calls |
488 | // to noduplicate functions. |
489 | for (BasicBlock *BB : this->blocks()) { |
490 | if (isa<IndirectBrInst>(Val: BB->getTerminator())) |
491 | return false; |
492 | |
493 | for (Instruction &I : *BB) |
494 | if (auto *CB = dyn_cast<CallBase>(Val: &I)) |
495 | if (CB->cannotDuplicate()) |
496 | return false; |
497 | } |
498 | return true; |
499 | } |
500 | |
501 | MDNode *Loop::getLoopID() const { |
502 | MDNode *LoopID = nullptr; |
503 | |
504 | // Go through the latch blocks and check the terminator for the metadata. |
505 | SmallVector<BasicBlock *, 4> LatchesBlocks; |
506 | getLoopLatches(LoopLatches&: LatchesBlocks); |
507 | for (BasicBlock *BB : LatchesBlocks) { |
508 | Instruction *TI = BB->getTerminator(); |
509 | MDNode *MD = TI->getMetadata(KindID: LLVMContext::MD_loop); |
510 | |
511 | if (!MD) |
512 | return nullptr; |
513 | |
514 | if (!LoopID) |
515 | LoopID = MD; |
516 | else if (MD != LoopID) |
517 | return nullptr; |
518 | } |
519 | if (!LoopID || LoopID->getNumOperands() == 0 || |
520 | LoopID->getOperand(I: 0) != LoopID) |
521 | return nullptr; |
522 | return LoopID; |
523 | } |
524 | |
525 | void Loop::setLoopID(MDNode *LoopID) const { |
526 | assert((!LoopID || LoopID->getNumOperands() > 0) && |
527 | "Loop ID needs at least one operand" ); |
528 | assert((!LoopID || LoopID->getOperand(0) == LoopID) && |
529 | "Loop ID should refer to itself" ); |
530 | |
531 | SmallVector<BasicBlock *, 4> LoopLatches; |
532 | getLoopLatches(LoopLatches); |
533 | for (BasicBlock *BB : LoopLatches) |
534 | BB->getTerminator()->setMetadata(KindID: LLVMContext::MD_loop, Node: LoopID); |
535 | } |
536 | |
537 | void Loop::setLoopAlreadyUnrolled() { |
538 | LLVMContext &Context = getHeader()->getContext(); |
539 | |
540 | MDNode *DisableUnrollMD = |
541 | MDNode::get(Context, MDs: MDString::get(Context, Str: "llvm.loop.unroll.disable" )); |
542 | MDNode *LoopID = getLoopID(); |
543 | MDNode *NewLoopID = makePostTransformationMetadata( |
544 | Context, OrigLoopID: LoopID, RemovePrefixes: {"llvm.loop.unroll." }, AddAttrs: {DisableUnrollMD}); |
545 | setLoopID(NewLoopID); |
546 | } |
547 | |
548 | void Loop::setLoopMustProgress() { |
549 | LLVMContext &Context = getHeader()->getContext(); |
550 | |
551 | MDNode *MustProgress = findOptionMDForLoop(TheLoop: this, Name: "llvm.loop.mustprogress" ); |
552 | |
553 | if (MustProgress) |
554 | return; |
555 | |
556 | MDNode *MustProgressMD = |
557 | MDNode::get(Context, MDs: MDString::get(Context, Str: "llvm.loop.mustprogress" )); |
558 | MDNode *LoopID = getLoopID(); |
559 | MDNode *NewLoopID = |
560 | makePostTransformationMetadata(Context, OrigLoopID: LoopID, RemovePrefixes: {}, AddAttrs: {MustProgressMD}); |
561 | setLoopID(NewLoopID); |
562 | } |
563 | |
564 | bool Loop::isAnnotatedParallel() const { |
565 | MDNode *DesiredLoopIdMetadata = getLoopID(); |
566 | |
567 | if (!DesiredLoopIdMetadata) |
568 | return false; |
569 | |
570 | MDNode *ParallelAccesses = |
571 | findOptionMDForLoop(TheLoop: this, Name: "llvm.loop.parallel_accesses" ); |
572 | SmallPtrSet<MDNode *, 4> |
573 | ParallelAccessGroups; // For scalable 'contains' check. |
574 | if (ParallelAccesses) { |
575 | for (const MDOperand &MD : drop_begin(RangeOrContainer: ParallelAccesses->operands())) { |
576 | MDNode *AccGroup = cast<MDNode>(Val: MD.get()); |
577 | assert(isValidAsAccessGroup(AccGroup) && |
578 | "List item must be an access group" ); |
579 | ParallelAccessGroups.insert(Ptr: AccGroup); |
580 | } |
581 | } |
582 | |
583 | // The loop branch contains the parallel loop metadata. In order to ensure |
584 | // that any parallel-loop-unaware optimization pass hasn't added loop-carried |
585 | // dependencies (thus converted the loop back to a sequential loop), check |
586 | // that all the memory instructions in the loop belong to an access group that |
587 | // is parallel to this loop. |
588 | for (BasicBlock *BB : this->blocks()) { |
589 | for (Instruction &I : *BB) { |
590 | if (!I.mayReadOrWriteMemory()) |
591 | continue; |
592 | |
593 | if (MDNode *AccessGroup = I.getMetadata(KindID: LLVMContext::MD_access_group)) { |
594 | auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool { |
595 | if (AG->getNumOperands() == 0) { |
596 | assert(isValidAsAccessGroup(AG) && "Item must be an access group" ); |
597 | return ParallelAccessGroups.count(Ptr: AG); |
598 | } |
599 | |
600 | for (const MDOperand &AccessListItem : AG->operands()) { |
601 | MDNode *AccGroup = cast<MDNode>(Val: AccessListItem.get()); |
602 | assert(isValidAsAccessGroup(AccGroup) && |
603 | "List item must be an access group" ); |
604 | if (ParallelAccessGroups.count(Ptr: AccGroup)) |
605 | return true; |
606 | } |
607 | return false; |
608 | }; |
609 | |
610 | if (ContainsAccessGroup(AccessGroup)) |
611 | continue; |
612 | } |
613 | |
614 | // The memory instruction can refer to the loop identifier metadata |
615 | // directly or indirectly through another list metadata (in case of |
616 | // nested parallel loops). The loop identifier metadata refers to |
617 | // itself so we can check both cases with the same routine. |
618 | MDNode *LoopIdMD = |
619 | I.getMetadata(KindID: LLVMContext::MD_mem_parallel_loop_access); |
620 | |
621 | if (!LoopIdMD) |
622 | return false; |
623 | |
624 | if (!llvm::is_contained(Range: LoopIdMD->operands(), Element: DesiredLoopIdMetadata)) |
625 | return false; |
626 | } |
627 | } |
628 | return true; |
629 | } |
630 | |
631 | DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); } |
632 | |
633 | Loop::LocRange Loop::getLocRange() const { |
634 | // If we have a debug location in the loop ID, then use it. |
635 | if (MDNode *LoopID = getLoopID()) { |
636 | DebugLoc Start; |
637 | // We use the first DebugLoc in the header as the start location of the loop |
638 | // and if there is a second DebugLoc in the header we use it as end location |
639 | // of the loop. |
640 | for (const MDOperand &MDO : llvm::drop_begin(RangeOrContainer: LoopID->operands())) { |
641 | if (DILocation *L = dyn_cast<DILocation>(Val: MDO)) { |
642 | if (!Start) |
643 | Start = DebugLoc(L); |
644 | else |
645 | return LocRange(Start, DebugLoc(L)); |
646 | } |
647 | } |
648 | |
649 | if (Start) |
650 | return LocRange(Start); |
651 | } |
652 | |
653 | // Try the pre-header first. |
654 | if (BasicBlock *PHeadBB = getLoopPreheader()) |
655 | if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc()) |
656 | return LocRange(DL); |
657 | |
658 | // If we have no pre-header or there are no instructions with debug |
659 | // info in it, try the header. |
660 | if (BasicBlock *HeadBB = getHeader()) |
661 | return LocRange(HeadBB->getTerminator()->getDebugLoc()); |
662 | |
663 | return LocRange(); |
664 | } |
665 | |
666 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
667 | LLVM_DUMP_METHOD void Loop::dump() const { print(OS&: dbgs()); } |
668 | |
669 | LLVM_DUMP_METHOD void Loop::dumpVerbose() const { |
670 | print(OS&: dbgs(), /*Verbose=*/true); |
671 | } |
672 | #endif |
673 | |
674 | //===----------------------------------------------------------------------===// |
675 | // UnloopUpdater implementation |
676 | // |
677 | |
678 | namespace { |
679 | /// Find the new parent loop for all blocks within the "unloop" whose last |
680 | /// backedges has just been removed. |
681 | class UnloopUpdater { |
682 | Loop &Unloop; |
683 | LoopInfo *LI; |
684 | |
685 | LoopBlocksDFS DFS; |
686 | |
687 | // Map unloop's immediate subloops to their nearest reachable parents. Nested |
688 | // loops within these subloops will not change parents. However, an immediate |
689 | // subloop's new parent will be the nearest loop reachable from either its own |
690 | // exits *or* any of its nested loop's exits. |
691 | DenseMap<Loop *, Loop *> SubloopParents; |
692 | |
693 | // Flag the presence of an irreducible backedge whose destination is a block |
694 | // directly contained by the original unloop. |
695 | bool FoundIB = false; |
696 | |
697 | public: |
698 | UnloopUpdater(Loop *UL, LoopInfo *LInfo) : Unloop(*UL), LI(LInfo), DFS(UL) {} |
699 | |
700 | void updateBlockParents(); |
701 | |
702 | void removeBlocksFromAncestors(); |
703 | |
704 | void updateSubloopParents(); |
705 | |
706 | protected: |
707 | Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop); |
708 | }; |
709 | } // end anonymous namespace |
710 | |
711 | /// Update the parent loop for all blocks that are directly contained within the |
712 | /// original "unloop". |
713 | void UnloopUpdater::updateBlockParents() { |
714 | if (Unloop.getNumBlocks()) { |
715 | // Perform a post order CFG traversal of all blocks within this loop, |
716 | // propagating the nearest loop from successors to predecessors. |
717 | LoopBlocksTraversal Traversal(DFS, LI); |
718 | for (BasicBlock *POI : Traversal) { |
719 | |
720 | Loop *L = LI->getLoopFor(BB: POI); |
721 | Loop *NL = getNearestLoop(BB: POI, BBLoop: L); |
722 | |
723 | if (NL != L) { |
724 | // For reducible loops, NL is now an ancestor of Unloop. |
725 | assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) && |
726 | "uninitialized successor" ); |
727 | LI->changeLoopFor(BB: POI, L: NL); |
728 | } else { |
729 | // Or the current block is part of a subloop, in which case its parent |
730 | // is unchanged. |
731 | assert((FoundIB || Unloop.contains(L)) && "uninitialized successor" ); |
732 | } |
733 | } |
734 | } |
735 | // Each irreducible loop within the unloop induces a round of iteration using |
736 | // the DFS result cached by Traversal. |
737 | bool Changed = FoundIB; |
738 | for (unsigned NIters = 0; Changed; ++NIters) { |
739 | assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm" ); |
740 | (void)NIters; |
741 | |
742 | // Iterate over the postorder list of blocks, propagating the nearest loop |
743 | // from successors to predecessors as before. |
744 | Changed = false; |
745 | for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(), |
746 | POE = DFS.endPostorder(); |
747 | POI != POE; ++POI) { |
748 | |
749 | Loop *L = LI->getLoopFor(BB: *POI); |
750 | Loop *NL = getNearestLoop(BB: *POI, BBLoop: L); |
751 | if (NL != L) { |
752 | assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) && |
753 | "uninitialized successor" ); |
754 | LI->changeLoopFor(BB: *POI, L: NL); |
755 | Changed = true; |
756 | } |
757 | } |
758 | } |
759 | } |
760 | |
761 | /// Remove unloop's blocks from all ancestors below their new parents. |
762 | void UnloopUpdater::removeBlocksFromAncestors() { |
763 | // Remove all unloop's blocks (including those in nested subloops) from |
764 | // ancestors below the new parent loop. |
765 | for (BasicBlock *BB : Unloop.blocks()) { |
766 | Loop *OuterParent = LI->getLoopFor(BB); |
767 | if (Unloop.contains(L: OuterParent)) { |
768 | while (OuterParent->getParentLoop() != &Unloop) |
769 | OuterParent = OuterParent->getParentLoop(); |
770 | OuterParent = SubloopParents[OuterParent]; |
771 | } |
772 | // Remove blocks from former Ancestors except Unloop itself which will be |
773 | // deleted. |
774 | for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent; |
775 | OldParent = OldParent->getParentLoop()) { |
776 | assert(OldParent && "new loop is not an ancestor of the original" ); |
777 | OldParent->removeBlockFromLoop(BB); |
778 | } |
779 | } |
780 | } |
781 | |
782 | /// Update the parent loop for all subloops directly nested within unloop. |
783 | void UnloopUpdater::updateSubloopParents() { |
784 | while (!Unloop.isInnermost()) { |
785 | Loop *Subloop = *std::prev(x: Unloop.end()); |
786 | Unloop.removeChildLoop(I: std::prev(x: Unloop.end())); |
787 | |
788 | assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop" ); |
789 | if (Loop *Parent = SubloopParents[Subloop]) |
790 | Parent->addChildLoop(NewChild: Subloop); |
791 | else |
792 | LI->addTopLevelLoop(New: Subloop); |
793 | } |
794 | } |
795 | |
796 | /// Return the nearest parent loop among this block's successors. If a successor |
797 | /// is a subloop header, consider its parent to be the nearest parent of the |
798 | /// subloop's exits. |
799 | /// |
800 | /// For subloop blocks, simply update SubloopParents and return NULL. |
801 | Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { |
802 | |
803 | // Initially for blocks directly contained by Unloop, NearLoop == Unloop and |
804 | // is considered uninitialized. |
805 | Loop *NearLoop = BBLoop; |
806 | |
807 | Loop *Subloop = nullptr; |
808 | if (NearLoop != &Unloop && Unloop.contains(L: NearLoop)) { |
809 | Subloop = NearLoop; |
810 | // Find the subloop ancestor that is directly contained within Unloop. |
811 | while (Subloop->getParentLoop() != &Unloop) { |
812 | Subloop = Subloop->getParentLoop(); |
813 | assert(Subloop && "subloop is not an ancestor of the original loop" ); |
814 | } |
815 | // Get the current nearest parent of the Subloop exits, initially Unloop. |
816 | NearLoop = SubloopParents.insert(KV: {Subloop, &Unloop}).first->second; |
817 | } |
818 | |
819 | if (succ_empty(BB)) { |
820 | assert(!Subloop && "subloop blocks must have a successor" ); |
821 | NearLoop = nullptr; // unloop blocks may now exit the function. |
822 | } |
823 | for (BasicBlock *Succ : successors(BB)) { |
824 | if (Succ == BB) |
825 | continue; // self loops are uninteresting |
826 | |
827 | Loop *L = LI->getLoopFor(BB: Succ); |
828 | if (L == &Unloop) { |
829 | // This successor has not been processed. This path must lead to an |
830 | // irreducible backedge. |
831 | assert((FoundIB || !DFS.hasPostorder(Succ)) && "should have seen IB" ); |
832 | FoundIB = true; |
833 | } |
834 | if (L != &Unloop && Unloop.contains(L)) { |
835 | // Successor is in a subloop. |
836 | if (Subloop) |
837 | continue; // Branching within subloops. Ignore it. |
838 | |
839 | // BB branches from the original into a subloop header. |
840 | assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops" ); |
841 | |
842 | // Get the current nearest parent of the Subloop's exits. |
843 | L = SubloopParents[L]; |
844 | // L could be Unloop if the only exit was an irreducible backedge. |
845 | } |
846 | if (L == &Unloop) { |
847 | continue; |
848 | } |
849 | // Handle critical edges from Unloop into a sibling loop. |
850 | if (L && !L->contains(L: &Unloop)) { |
851 | L = L->getParentLoop(); |
852 | } |
853 | // Remember the nearest parent loop among successors or subloop exits. |
854 | if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L)) |
855 | NearLoop = L; |
856 | } |
857 | if (Subloop) { |
858 | SubloopParents[Subloop] = NearLoop; |
859 | return BBLoop; |
860 | } |
861 | return NearLoop; |
862 | } |
863 | |
864 | LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); } |
865 | |
866 | bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA, |
867 | FunctionAnalysisManager::Invalidator &) { |
868 | // Check whether the analysis, all analyses on functions, or the function's |
869 | // CFG have been preserved. |
870 | auto PAC = PA.getChecker<LoopAnalysis>(); |
871 | return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() || |
872 | PAC.preservedSet<CFGAnalyses>()); |
873 | } |
874 | |
875 | void LoopInfo::erase(Loop *Unloop) { |
876 | assert(!Unloop->isInvalid() && "Loop has already been erased!" ); |
877 | |
878 | auto InvalidateOnExit = make_scope_exit(F: [&]() { destroy(L: Unloop); }); |
879 | |
880 | // First handle the special case of no parent loop to simplify the algorithm. |
881 | if (Unloop->isOutermost()) { |
882 | // Since BBLoop had no parent, Unloop blocks are no longer in a loop. |
883 | for (BasicBlock *BB : Unloop->blocks()) { |
884 | // Don't reparent blocks in subloops. |
885 | if (getLoopFor(BB) != Unloop) |
886 | continue; |
887 | |
888 | // Blocks no longer have a parent but are still referenced by Unloop until |
889 | // the Unloop object is deleted. |
890 | changeLoopFor(BB, L: nullptr); |
891 | } |
892 | |
893 | // Remove the loop from the top-level LoopInfo object. |
894 | for (iterator I = begin();; ++I) { |
895 | assert(I != end() && "Couldn't find loop" ); |
896 | if (*I == Unloop) { |
897 | removeLoop(I); |
898 | break; |
899 | } |
900 | } |
901 | |
902 | // Move all of the subloops to the top-level. |
903 | while (!Unloop->isInnermost()) |
904 | addTopLevelLoop(New: Unloop->removeChildLoop(I: std::prev(x: Unloop->end()))); |
905 | |
906 | return; |
907 | } |
908 | |
909 | // Update the parent loop for all blocks within the loop. Blocks within |
910 | // subloops will not change parents. |
911 | UnloopUpdater Updater(Unloop, this); |
912 | Updater.updateBlockParents(); |
913 | |
914 | // Remove blocks from former ancestor loops. |
915 | Updater.removeBlocksFromAncestors(); |
916 | |
917 | // Add direct subloops as children in their new parent loop. |
918 | Updater.updateSubloopParents(); |
919 | |
920 | // Remove unloop from its parent loop. |
921 | Loop *ParentLoop = Unloop->getParentLoop(); |
922 | for (Loop::iterator I = ParentLoop->begin();; ++I) { |
923 | assert(I != ParentLoop->end() && "Couldn't find loop" ); |
924 | if (*I == Unloop) { |
925 | ParentLoop->removeChildLoop(I); |
926 | break; |
927 | } |
928 | } |
929 | } |
930 | |
931 | bool LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA( |
932 | const Value *V, const BasicBlock *ExitBB) const { |
933 | if (V->getType()->isTokenTy()) |
934 | // We can't form PHIs of token type, so the definition of LCSSA excludes |
935 | // values of that type. |
936 | return false; |
937 | |
938 | const Instruction *I = dyn_cast<Instruction>(Val: V); |
939 | if (!I) |
940 | return false; |
941 | const Loop *L = getLoopFor(BB: I->getParent()); |
942 | if (!L) |
943 | return false; |
944 | if (L->contains(BB: ExitBB)) |
945 | // Could be an exit bb of a subloop and contained in defining loop |
946 | return false; |
947 | |
948 | // We found a (new) out-of-loop use location, for a value defined in-loop. |
949 | // (Note that because of LCSSA, we don't have to account for values defined |
950 | // in sibling loops. Such values will have LCSSA phis of their own in the |
951 | // common parent loop.) |
952 | return true; |
953 | } |
954 | |
955 | AnalysisKey LoopAnalysis::Key; |
956 | |
957 | LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) { |
958 | // FIXME: Currently we create a LoopInfo from scratch for every function. |
959 | // This may prove to be too wasteful due to deallocating and re-allocating |
960 | // memory each time for the underlying map and vector datastructures. At some |
961 | // point it may prove worthwhile to use a freelist and recycle LoopInfo |
962 | // objects. I don't want to add that kind of complexity until the scope of |
963 | // the problem is better understood. |
964 | LoopInfo LI; |
965 | LI.analyze(DomTree: AM.getResult<DominatorTreeAnalysis>(IR&: F)); |
966 | return LI; |
967 | } |
968 | |
969 | PreservedAnalyses LoopPrinterPass::run(Function &F, |
970 | FunctionAnalysisManager &AM) { |
971 | auto &LI = AM.getResult<LoopAnalysis>(IR&: F); |
972 | OS << "Loop info for function '" << F.getName() << "':\n" ; |
973 | LI.print(OS); |
974 | return PreservedAnalyses::all(); |
975 | } |
976 | |
977 | void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) { |
978 | |
979 | if (forcePrintModuleIR()) { |
980 | // handling -print-module-scope |
981 | OS << Banner << " (loop: " ; |
982 | L.getHeader()->printAsOperand(O&: OS, PrintType: false); |
983 | OS << ")\n" ; |
984 | |
985 | // printing whole module |
986 | OS << *L.getHeader()->getModule(); |
987 | return; |
988 | } |
989 | |
990 | OS << Banner; |
991 | |
992 | auto * = L.getLoopPreheader(); |
993 | if (PreHeader) { |
994 | OS << "\n; Preheader:" ; |
995 | PreHeader->print(OS); |
996 | OS << "\n; Loop:" ; |
997 | } |
998 | |
999 | for (auto *Block : L.blocks()) |
1000 | if (Block) |
1001 | Block->print(OS); |
1002 | else |
1003 | OS << "Printing <null> block" ; |
1004 | |
1005 | SmallVector<BasicBlock *, 8> ExitBlocks; |
1006 | L.getExitBlocks(ExitBlocks); |
1007 | if (!ExitBlocks.empty()) { |
1008 | OS << "\n; Exit blocks" ; |
1009 | for (auto *Block : ExitBlocks) |
1010 | if (Block) |
1011 | Block->print(OS); |
1012 | else |
1013 | OS << "Printing <null> block" ; |
1014 | } |
1015 | } |
1016 | |
1017 | MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) { |
1018 | // No loop metadata node, no loop properties. |
1019 | if (!LoopID) |
1020 | return nullptr; |
1021 | |
1022 | // First operand should refer to the metadata node itself, for legacy reasons. |
1023 | assert(LoopID->getNumOperands() > 0 && "requires at least one operand" ); |
1024 | assert(LoopID->getOperand(0) == LoopID && "invalid loop id" ); |
1025 | |
1026 | // Iterate over the metdata node operands and look for MDString metadata. |
1027 | for (const MDOperand &MDO : llvm::drop_begin(RangeOrContainer: LoopID->operands())) { |
1028 | MDNode *MD = dyn_cast<MDNode>(Val: MDO); |
1029 | if (!MD || MD->getNumOperands() < 1) |
1030 | continue; |
1031 | MDString *S = dyn_cast<MDString>(Val: MD->getOperand(I: 0)); |
1032 | if (!S) |
1033 | continue; |
1034 | // Return the operand node if MDString holds expected metadata. |
1035 | if (Name.equals(RHS: S->getString())) |
1036 | return MD; |
1037 | } |
1038 | |
1039 | // Loop property not found. |
1040 | return nullptr; |
1041 | } |
1042 | |
1043 | MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) { |
1044 | return findOptionMDForLoopID(LoopID: TheLoop->getLoopID(), Name); |
1045 | } |
1046 | |
1047 | /// Find string metadata for loop |
1048 | /// |
1049 | /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an |
1050 | /// operand or null otherwise. If the string metadata is not found return |
1051 | /// Optional's not-a-value. |
1052 | std::optional<const MDOperand *> |
1053 | llvm::findStringMetadataForLoop(const Loop *TheLoop, StringRef Name) { |
1054 | MDNode *MD = findOptionMDForLoop(TheLoop, Name); |
1055 | if (!MD) |
1056 | return std::nullopt; |
1057 | switch (MD->getNumOperands()) { |
1058 | case 1: |
1059 | return nullptr; |
1060 | case 2: |
1061 | return &MD->getOperand(I: 1); |
1062 | default: |
1063 | llvm_unreachable("loop metadata has 0 or 1 operand" ); |
1064 | } |
1065 | } |
1066 | |
1067 | std::optional<bool> llvm::getOptionalBoolLoopAttribute(const Loop *TheLoop, |
1068 | StringRef Name) { |
1069 | MDNode *MD = findOptionMDForLoop(TheLoop, Name); |
1070 | if (!MD) |
1071 | return std::nullopt; |
1072 | switch (MD->getNumOperands()) { |
1073 | case 1: |
1074 | // When the value is absent it is interpreted as 'attribute set'. |
1075 | return true; |
1076 | case 2: |
1077 | if (ConstantInt *IntMD = |
1078 | mdconst::extract_or_null<ConstantInt>(MD: MD->getOperand(I: 1).get())) |
1079 | return IntMD->getZExtValue(); |
1080 | return true; |
1081 | } |
1082 | llvm_unreachable("unexpected number of options" ); |
1083 | } |
1084 | |
1085 | bool llvm::getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) { |
1086 | return getOptionalBoolLoopAttribute(TheLoop, Name).value_or(u: false); |
1087 | } |
1088 | |
1089 | std::optional<int> llvm::getOptionalIntLoopAttribute(const Loop *TheLoop, |
1090 | StringRef Name) { |
1091 | const MDOperand *AttrMD = |
1092 | findStringMetadataForLoop(TheLoop, Name).value_or(u: nullptr); |
1093 | if (!AttrMD) |
1094 | return std::nullopt; |
1095 | |
1096 | ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(MD: AttrMD->get()); |
1097 | if (!IntMD) |
1098 | return std::nullopt; |
1099 | |
1100 | return IntMD->getSExtValue(); |
1101 | } |
1102 | |
1103 | int llvm::getIntLoopAttribute(const Loop *TheLoop, StringRef Name, |
1104 | int Default) { |
1105 | return getOptionalIntLoopAttribute(TheLoop, Name).value_or(u&: Default); |
1106 | } |
1107 | |
1108 | bool llvm::isFinite(const Loop *L) { |
1109 | return L->getHeader()->getParent()->willReturn(); |
1110 | } |
1111 | |
1112 | static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress" ; |
1113 | |
1114 | bool llvm::hasMustProgress(const Loop *L) { |
1115 | return getBooleanLoopAttribute(TheLoop: L, Name: LLVMLoopMustProgress); |
1116 | } |
1117 | |
1118 | bool llvm::isMustProgress(const Loop *L) { |
1119 | return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L); |
1120 | } |
1121 | |
1122 | bool llvm::isValidAsAccessGroup(MDNode *Node) { |
1123 | return Node->getNumOperands() == 0 && Node->isDistinct(); |
1124 | } |
1125 | |
1126 | MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context, |
1127 | MDNode *OrigLoopID, |
1128 | ArrayRef<StringRef> RemovePrefixes, |
1129 | ArrayRef<MDNode *> AddAttrs) { |
1130 | // First remove any existing loop metadata related to this transformation. |
1131 | SmallVector<Metadata *, 4> MDs; |
1132 | |
1133 | // Reserve first location for self reference to the LoopID metadata node. |
1134 | MDs.push_back(Elt: nullptr); |
1135 | |
1136 | // Remove metadata for the transformation that has been applied or that became |
1137 | // outdated. |
1138 | if (OrigLoopID) { |
1139 | for (const MDOperand &MDO : llvm::drop_begin(RangeOrContainer: OrigLoopID->operands())) { |
1140 | bool IsVectorMetadata = false; |
1141 | Metadata *Op = MDO; |
1142 | if (MDNode *MD = dyn_cast<MDNode>(Val: Op)) { |
1143 | const MDString *S = dyn_cast<MDString>(Val: MD->getOperand(I: 0)); |
1144 | if (S) |
1145 | IsVectorMetadata = |
1146 | llvm::any_of(Range&: RemovePrefixes, P: [S](StringRef Prefix) -> bool { |
1147 | return S->getString().starts_with(Prefix); |
1148 | }); |
1149 | } |
1150 | if (!IsVectorMetadata) |
1151 | MDs.push_back(Elt: Op); |
1152 | } |
1153 | } |
1154 | |
1155 | // Add metadata to avoid reapplying a transformation, such as |
1156 | // llvm.loop.unroll.disable and llvm.loop.isvectorized. |
1157 | MDs.append(in_start: AddAttrs.begin(), in_end: AddAttrs.end()); |
1158 | |
1159 | MDNode *NewLoopID = MDNode::getDistinct(Context, MDs); |
1160 | // Replace the temporary node with a self-reference. |
1161 | NewLoopID->replaceOperandWith(I: 0, New: NewLoopID); |
1162 | return NewLoopID; |
1163 | } |
1164 | |
1165 | //===----------------------------------------------------------------------===// |
1166 | // LoopInfo implementation |
1167 | // |
1168 | |
1169 | LoopInfoWrapperPass::LoopInfoWrapperPass() : FunctionPass(ID) { |
1170 | initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); |
1171 | } |
1172 | |
1173 | char LoopInfoWrapperPass::ID = 0; |
1174 | INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops" , "Natural Loop Information" , |
1175 | true, true) |
1176 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
1177 | INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops" , "Natural Loop Information" , |
1178 | true, true) |
1179 | |
1180 | bool LoopInfoWrapperPass::runOnFunction(Function &) { |
1181 | releaseMemory(); |
1182 | LI.analyze(DomTree: getAnalysis<DominatorTreeWrapperPass>().getDomTree()); |
1183 | return false; |
1184 | } |
1185 | |
1186 | void LoopInfoWrapperPass::verifyAnalysis() const { |
1187 | // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the |
1188 | // function each time verifyAnalysis is called is very expensive. The |
1189 | // -verify-loop-info option can enable this. In order to perform some |
1190 | // checking by default, LoopPass has been taught to call verifyLoop manually |
1191 | // during loop pass sequences. |
1192 | if (VerifyLoopInfo) { |
1193 | auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
1194 | LI.verify(DomTree: DT); |
1195 | } |
1196 | } |
1197 | |
1198 | void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { |
1199 | AU.setPreservesAll(); |
1200 | AU.addRequiredTransitive<DominatorTreeWrapperPass>(); |
1201 | } |
1202 | |
1203 | void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const { |
1204 | LI.print(OS); |
1205 | } |
1206 | |
1207 | PreservedAnalyses LoopVerifierPass::run(Function &F, |
1208 | FunctionAnalysisManager &AM) { |
1209 | LoopInfo &LI = AM.getResult<LoopAnalysis>(IR&: F); |
1210 | auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F); |
1211 | LI.verify(DomTree: DT); |
1212 | return PreservedAnalyses::all(); |
1213 | } |
1214 | |
1215 | //===----------------------------------------------------------------------===// |
1216 | // LoopBlocksDFS implementation |
1217 | // |
1218 | |
1219 | /// Traverse the loop blocks and store the DFS result. |
1220 | /// Useful for clients that just want the final DFS result and don't need to |
1221 | /// visit blocks during the initial traversal. |
1222 | void LoopBlocksDFS::perform(const LoopInfo *LI) { |
1223 | LoopBlocksTraversal Traversal(*this, LI); |
1224 | for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), |
1225 | POE = Traversal.end(); |
1226 | POI != POE; ++POI) |
1227 | ; |
1228 | } |
1229 | |