1 | //===-- UnrollLoop.cpp - Loop unrolling utilities -------------------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file implements some loop unrolling utilities. It does not define any |
10 | // actual pass or policy, but provides a single function to perform loop |
11 | // unrolling. |
12 | // |
13 | // The process of unrolling can produce extraneous basic blocks linked with |
14 | // unconditional branches. This will be corrected in the future. |
15 | // |
16 | //===----------------------------------------------------------------------===// |
17 | |
18 | #include "llvm/ADT/ArrayRef.h" |
19 | #include "llvm/ADT/DenseMap.h" |
20 | #include "llvm/ADT/STLExtras.h" |
21 | #include "llvm/ADT/SetVector.h" |
22 | #include "llvm/ADT/SmallVector.h" |
23 | #include "llvm/ADT/Statistic.h" |
24 | #include "llvm/ADT/StringRef.h" |
25 | #include "llvm/ADT/Twine.h" |
26 | #include "llvm/ADT/ilist_iterator.h" |
27 | #include "llvm/Analysis/AssumptionCache.h" |
28 | #include "llvm/Analysis/DomTreeUpdater.h" |
29 | #include "llvm/Analysis/InstructionSimplify.h" |
30 | #include "llvm/Analysis/LoopInfo.h" |
31 | #include "llvm/Analysis/LoopIterator.h" |
32 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" |
33 | #include "llvm/Analysis/ScalarEvolution.h" |
34 | #include "llvm/IR/BasicBlock.h" |
35 | #include "llvm/IR/CFG.h" |
36 | #include "llvm/IR/Constants.h" |
37 | #include "llvm/IR/DebugInfoMetadata.h" |
38 | #include "llvm/IR/DebugLoc.h" |
39 | #include "llvm/IR/DiagnosticInfo.h" |
40 | #include "llvm/IR/Dominators.h" |
41 | #include "llvm/IR/Function.h" |
42 | #include "llvm/IR/Instruction.h" |
43 | #include "llvm/IR/Instructions.h" |
44 | #include "llvm/IR/IntrinsicInst.h" |
45 | #include "llvm/IR/Metadata.h" |
46 | #include "llvm/IR/Module.h" |
47 | #include "llvm/IR/PatternMatch.h" |
48 | #include "llvm/IR/Use.h" |
49 | #include "llvm/IR/User.h" |
50 | #include "llvm/IR/ValueHandle.h" |
51 | #include "llvm/IR/ValueMap.h" |
52 | #include "llvm/Support/Casting.h" |
53 | #include "llvm/Support/CommandLine.h" |
54 | #include "llvm/Support/Debug.h" |
55 | #include "llvm/Support/GenericDomTree.h" |
56 | #include "llvm/Support/MathExtras.h" |
57 | #include "llvm/Support/raw_ostream.h" |
58 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
59 | #include "llvm/Transforms/Utils/Cloning.h" |
60 | #include "llvm/Transforms/Utils/Local.h" |
61 | #include "llvm/Transforms/Utils/LoopSimplify.h" |
62 | #include "llvm/Transforms/Utils/LoopUtils.h" |
63 | #include "llvm/Transforms/Utils/SimplifyIndVar.h" |
64 | #include "llvm/Transforms/Utils/UnrollLoop.h" |
65 | #include "llvm/Transforms/Utils/ValueMapper.h" |
66 | #include <algorithm> |
67 | #include <assert.h> |
68 | #include <numeric> |
69 | #include <type_traits> |
70 | #include <vector> |
71 | |
72 | namespace llvm { |
73 | class DataLayout; |
74 | class Value; |
75 | } // namespace llvm |
76 | |
77 | using namespace llvm; |
78 | |
79 | #define DEBUG_TYPE "loop-unroll" |
80 | |
81 | // TODO: Should these be here or in LoopUnroll? |
82 | STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled" ); |
83 | STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)" ); |
84 | STATISTIC(NumUnrolledNotLatch, "Number of loops unrolled without a conditional " |
85 | "latch (completely or otherwise)" ); |
86 | |
87 | static cl::opt<bool> |
88 | UnrollRuntimeEpilog("unroll-runtime-epilog" , cl::init(Val: false), cl::Hidden, |
89 | cl::desc("Allow runtime unrolled loops to be unrolled " |
90 | "with epilog instead of prolog." )); |
91 | |
92 | static cl::opt<bool> |
93 | UnrollVerifyDomtree("unroll-verify-domtree" , cl::Hidden, |
94 | cl::desc("Verify domtree after unrolling" ), |
95 | #ifdef EXPENSIVE_CHECKS |
96 | cl::init(true) |
97 | #else |
98 | cl::init(Val: false) |
99 | #endif |
100 | ); |
101 | |
102 | static cl::opt<bool> |
103 | UnrollVerifyLoopInfo("unroll-verify-loopinfo" , cl::Hidden, |
104 | cl::desc("Verify loopinfo after unrolling" ), |
105 | #ifdef EXPENSIVE_CHECKS |
106 | cl::init(true) |
107 | #else |
108 | cl::init(Val: false) |
109 | #endif |
110 | ); |
111 | |
112 | |
113 | /// Check if unrolling created a situation where we need to insert phi nodes to |
114 | /// preserve LCSSA form. |
115 | /// \param Blocks is a vector of basic blocks representing unrolled loop. |
116 | /// \param L is the outer loop. |
117 | /// It's possible that some of the blocks are in L, and some are not. In this |
118 | /// case, if there is a use is outside L, and definition is inside L, we need to |
119 | /// insert a phi-node, otherwise LCSSA will be broken. |
120 | /// The function is just a helper function for llvm::UnrollLoop that returns |
121 | /// true if this situation occurs, indicating that LCSSA needs to be fixed. |
122 | static bool needToInsertPhisForLCSSA(Loop *L, |
123 | const std::vector<BasicBlock *> &Blocks, |
124 | LoopInfo *LI) { |
125 | for (BasicBlock *BB : Blocks) { |
126 | if (LI->getLoopFor(BB) == L) |
127 | continue; |
128 | for (Instruction &I : *BB) { |
129 | for (Use &U : I.operands()) { |
130 | if (const auto *Def = dyn_cast<Instruction>(Val&: U)) { |
131 | Loop *DefLoop = LI->getLoopFor(BB: Def->getParent()); |
132 | if (!DefLoop) |
133 | continue; |
134 | if (DefLoop->contains(L)) |
135 | return true; |
136 | } |
137 | } |
138 | } |
139 | } |
140 | return false; |
141 | } |
142 | |
143 | /// Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary |
144 | /// and adds a mapping from the original loop to the new loop to NewLoops. |
145 | /// Returns nullptr if no new loop was created and a pointer to the |
146 | /// original loop OriginalBB was part of otherwise. |
147 | const Loop* llvm::addClonedBlockToLoopInfo(BasicBlock *OriginalBB, |
148 | BasicBlock *ClonedBB, LoopInfo *LI, |
149 | NewLoopsMap &NewLoops) { |
150 | // Figure out which loop New is in. |
151 | const Loop *OldLoop = LI->getLoopFor(BB: OriginalBB); |
152 | assert(OldLoop && "Should (at least) be in the loop being unrolled!" ); |
153 | |
154 | Loop *&NewLoop = NewLoops[OldLoop]; |
155 | if (!NewLoop) { |
156 | // Found a new sub-loop. |
157 | assert(OriginalBB == OldLoop->getHeader() && |
158 | "Header should be first in RPO" ); |
159 | |
160 | NewLoop = LI->AllocateLoop(); |
161 | Loop *NewLoopParent = NewLoops.lookup(Val: OldLoop->getParentLoop()); |
162 | |
163 | if (NewLoopParent) |
164 | NewLoopParent->addChildLoop(NewChild: NewLoop); |
165 | else |
166 | LI->addTopLevelLoop(New: NewLoop); |
167 | |
168 | NewLoop->addBasicBlockToLoop(NewBB: ClonedBB, LI&: *LI); |
169 | return OldLoop; |
170 | } else { |
171 | NewLoop->addBasicBlockToLoop(NewBB: ClonedBB, LI&: *LI); |
172 | return nullptr; |
173 | } |
174 | } |
175 | |
176 | /// The function chooses which type of unroll (epilog or prolog) is more |
177 | /// profitabale. |
178 | /// Epilog unroll is more profitable when there is PHI that starts from |
179 | /// constant. In this case epilog will leave PHI start from constant, |
180 | /// but prolog will convert it to non-constant. |
181 | /// |
182 | /// loop: |
183 | /// PN = PHI [I, Latch], [CI, PreHeader] |
184 | /// I = foo(PN) |
185 | /// ... |
186 | /// |
187 | /// Epilog unroll case. |
188 | /// loop: |
189 | /// PN = PHI [I2, Latch], [CI, PreHeader] |
190 | /// I1 = foo(PN) |
191 | /// I2 = foo(I1) |
192 | /// ... |
193 | /// Prolog unroll case. |
194 | /// NewPN = PHI [PrologI, Prolog], [CI, PreHeader] |
195 | /// loop: |
196 | /// PN = PHI [I2, Latch], [NewPN, PreHeader] |
197 | /// I1 = foo(PN) |
198 | /// I2 = foo(I1) |
199 | /// ... |
200 | /// |
201 | static bool isEpilogProfitable(Loop *L) { |
202 | BasicBlock * = L->getLoopPreheader(); |
203 | BasicBlock * = L->getHeader(); |
204 | assert(PreHeader && Header); |
205 | for (const PHINode &PN : Header->phis()) { |
206 | if (isa<ConstantInt>(Val: PN.getIncomingValueForBlock(BB: PreHeader))) |
207 | return true; |
208 | } |
209 | return false; |
210 | } |
211 | |
212 | /// Perform some cleanup and simplifications on loops after unrolling. It is |
213 | /// useful to simplify the IV's in the new loop, as well as do a quick |
214 | /// simplify/dce pass of the instructions. |
215 | void llvm::simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, |
216 | ScalarEvolution *SE, DominatorTree *DT, |
217 | AssumptionCache *AC, |
218 | const TargetTransformInfo *TTI) { |
219 | using namespace llvm::PatternMatch; |
220 | |
221 | // Simplify any new induction variables in the partially unrolled loop. |
222 | if (SE && SimplifyIVs) { |
223 | SmallVector<WeakTrackingVH, 16> DeadInsts; |
224 | simplifyLoopIVs(L, SE, DT, LI, TTI, Dead&: DeadInsts); |
225 | |
226 | // Aggressively clean up dead instructions that simplifyLoopIVs already |
227 | // identified. Any remaining should be cleaned up below. |
228 | while (!DeadInsts.empty()) { |
229 | Value *V = DeadInsts.pop_back_val(); |
230 | if (Instruction *Inst = dyn_cast_or_null<Instruction>(Val: V)) |
231 | RecursivelyDeleteTriviallyDeadInstructions(V: Inst); |
232 | } |
233 | } |
234 | |
235 | // At this point, the code is well formed. Perform constprop, instsimplify, |
236 | // and dce. |
237 | const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); |
238 | SmallVector<WeakTrackingVH, 16> DeadInsts; |
239 | for (BasicBlock *BB : L->getBlocks()) { |
240 | for (Instruction &Inst : llvm::make_early_inc_range(Range&: *BB)) { |
241 | if (Value *V = simplifyInstruction(I: &Inst, Q: {DL, nullptr, DT, AC})) |
242 | if (LI->replacementPreservesLCSSAForm(From: &Inst, To: V)) |
243 | Inst.replaceAllUsesWith(V); |
244 | if (isInstructionTriviallyDead(I: &Inst)) |
245 | DeadInsts.emplace_back(Args: &Inst); |
246 | |
247 | // Fold ((add X, C1), C2) to (add X, C1+C2). This is very common in |
248 | // unrolled loops, and handling this early allows following code to |
249 | // identify the IV as a "simple recurrence" without first folding away |
250 | // a long chain of adds. |
251 | { |
252 | Value *X; |
253 | const APInt *C1, *C2; |
254 | if (match(V: &Inst, P: m_Add(L: m_Add(L: m_Value(V&: X), R: m_APInt(Res&: C1)), R: m_APInt(Res&: C2)))) { |
255 | auto *InnerI = dyn_cast<Instruction>(Val: Inst.getOperand(i: 0)); |
256 | auto *InnerOBO = cast<OverflowingBinaryOperator>(Val: Inst.getOperand(i: 0)); |
257 | bool SignedOverflow; |
258 | APInt NewC = C1->sadd_ov(RHS: *C2, Overflow&: SignedOverflow); |
259 | Inst.setOperand(i: 0, Val: X); |
260 | Inst.setOperand(i: 1, Val: ConstantInt::get(Ty: Inst.getType(), V: NewC)); |
261 | Inst.setHasNoUnsignedWrap(Inst.hasNoUnsignedWrap() && |
262 | InnerOBO->hasNoUnsignedWrap()); |
263 | Inst.setHasNoSignedWrap(Inst.hasNoSignedWrap() && |
264 | InnerOBO->hasNoSignedWrap() && |
265 | !SignedOverflow); |
266 | if (InnerI && isInstructionTriviallyDead(I: InnerI)) |
267 | DeadInsts.emplace_back(Args&: InnerI); |
268 | } |
269 | } |
270 | } |
271 | // We can't do recursive deletion until we're done iterating, as we might |
272 | // have a phi which (potentially indirectly) uses instructions later in |
273 | // the block we're iterating through. |
274 | RecursivelyDeleteTriviallyDeadInstructions(DeadInsts); |
275 | } |
276 | } |
277 | |
278 | /// Unroll the given loop by Count. The loop must be in LCSSA form. Unrolling |
279 | /// can only fail when the loop's latch block is not terminated by a conditional |
280 | /// branch instruction. However, if the trip count (and multiple) are not known, |
281 | /// loop unrolling will mostly produce more code that is no faster. |
282 | /// |
283 | /// If Runtime is true then UnrollLoop will try to insert a prologue or |
284 | /// epilogue that ensures the latch has a trip multiple of Count. UnrollLoop |
285 | /// will not runtime-unroll the loop if computing the run-time trip count will |
286 | /// be expensive and AllowExpensiveTripCount is false. |
287 | /// |
288 | /// The LoopInfo Analysis that is passed will be kept consistent. |
289 | /// |
290 | /// This utility preserves LoopInfo. It will also preserve ScalarEvolution and |
291 | /// DominatorTree if they are non-null. |
292 | /// |
293 | /// If RemainderLoop is non-null, it will receive the remainder loop (if |
294 | /// required and not fully unrolled). |
295 | LoopUnrollResult llvm::UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, |
296 | ScalarEvolution *SE, DominatorTree *DT, |
297 | AssumptionCache *AC, |
298 | const TargetTransformInfo *TTI, |
299 | OptimizationRemarkEmitter *ORE, |
300 | bool PreserveLCSSA, Loop **RemainderLoop) { |
301 | assert(DT && "DomTree is required" ); |
302 | |
303 | if (!L->getLoopPreheader()) { |
304 | LLVM_DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n" ); |
305 | return LoopUnrollResult::Unmodified; |
306 | } |
307 | |
308 | if (!L->getLoopLatch()) { |
309 | LLVM_DEBUG(dbgs() << " Can't unroll; loop exit-block-insertion failed.\n" ); |
310 | return LoopUnrollResult::Unmodified; |
311 | } |
312 | |
313 | // Loops with indirectbr cannot be cloned. |
314 | if (!L->isSafeToClone()) { |
315 | LLVM_DEBUG(dbgs() << " Can't unroll; Loop body cannot be cloned.\n" ); |
316 | return LoopUnrollResult::Unmodified; |
317 | } |
318 | |
319 | if (L->getHeader()->hasAddressTaken()) { |
320 | // The loop-rotate pass can be helpful to avoid this in many cases. |
321 | LLVM_DEBUG( |
322 | dbgs() << " Won't unroll loop: address of header block is taken.\n" ); |
323 | return LoopUnrollResult::Unmodified; |
324 | } |
325 | |
326 | assert(ULO.Count > 0); |
327 | |
328 | // All these values should be taken only after peeling because they might have |
329 | // changed. |
330 | BasicBlock * = L->getLoopPreheader(); |
331 | BasicBlock * = L->getHeader(); |
332 | BasicBlock *LatchBlock = L->getLoopLatch(); |
333 | SmallVector<BasicBlock *, 4> ExitBlocks; |
334 | L->getExitBlocks(ExitBlocks); |
335 | std::vector<BasicBlock *> OriginalLoopBlocks = L->getBlocks(); |
336 | |
337 | const unsigned MaxTripCount = SE->getSmallConstantMaxTripCount(L); |
338 | const bool MaxOrZero = SE->isBackedgeTakenCountMaxOrZero(L); |
339 | unsigned EstimatedLoopInvocationWeight = 0; |
340 | std::optional<unsigned> OriginalTripCount = |
341 | llvm::getLoopEstimatedTripCount(L, EstimatedLoopInvocationWeight: &EstimatedLoopInvocationWeight); |
342 | |
343 | // Effectively "DCE" unrolled iterations that are beyond the max tripcount |
344 | // and will never be executed. |
345 | if (MaxTripCount && ULO.Count > MaxTripCount) |
346 | ULO.Count = MaxTripCount; |
347 | |
348 | struct ExitInfo { |
349 | unsigned TripCount; |
350 | unsigned TripMultiple; |
351 | unsigned BreakoutTrip; |
352 | bool ExitOnTrue; |
353 | BasicBlock *FirstExitingBlock = nullptr; |
354 | SmallVector<BasicBlock *> ExitingBlocks; |
355 | }; |
356 | DenseMap<BasicBlock *, ExitInfo> ExitInfos; |
357 | SmallVector<BasicBlock *, 4> ExitingBlocks; |
358 | L->getExitingBlocks(ExitingBlocks); |
359 | for (auto *ExitingBlock : ExitingBlocks) { |
360 | // The folding code is not prepared to deal with non-branch instructions |
361 | // right now. |
362 | auto *BI = dyn_cast<BranchInst>(Val: ExitingBlock->getTerminator()); |
363 | if (!BI) |
364 | continue; |
365 | |
366 | ExitInfo &Info = ExitInfos.try_emplace(Key: ExitingBlock).first->second; |
367 | Info.TripCount = SE->getSmallConstantTripCount(L, ExitingBlock); |
368 | Info.TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock); |
369 | if (Info.TripCount != 0) { |
370 | Info.BreakoutTrip = Info.TripCount % ULO.Count; |
371 | Info.TripMultiple = 0; |
372 | } else { |
373 | Info.BreakoutTrip = Info.TripMultiple = |
374 | (unsigned)std::gcd(m: ULO.Count, n: Info.TripMultiple); |
375 | } |
376 | Info.ExitOnTrue = !L->contains(BB: BI->getSuccessor(i: 0)); |
377 | Info.ExitingBlocks.push_back(Elt: ExitingBlock); |
378 | LLVM_DEBUG(dbgs() << " Exiting block %" << ExitingBlock->getName() |
379 | << ": TripCount=" << Info.TripCount |
380 | << ", TripMultiple=" << Info.TripMultiple |
381 | << ", BreakoutTrip=" << Info.BreakoutTrip << "\n" ); |
382 | } |
383 | |
384 | // Are we eliminating the loop control altogether? Note that we can know |
385 | // we're eliminating the backedge without knowing exactly which iteration |
386 | // of the unrolled body exits. |
387 | const bool CompletelyUnroll = ULO.Count == MaxTripCount; |
388 | |
389 | const bool PreserveOnlyFirst = CompletelyUnroll && MaxOrZero; |
390 | |
391 | // There's no point in performing runtime unrolling if this unroll count |
392 | // results in a full unroll. |
393 | if (CompletelyUnroll) |
394 | ULO.Runtime = false; |
395 | |
396 | // Go through all exits of L and see if there are any phi-nodes there. We just |
397 | // conservatively assume that they're inserted to preserve LCSSA form, which |
398 | // means that complete unrolling might break this form. We need to either fix |
399 | // it in-place after the transformation, or entirely rebuild LCSSA. TODO: For |
400 | // now we just recompute LCSSA for the outer loop, but it should be possible |
401 | // to fix it in-place. |
402 | bool NeedToFixLCSSA = |
403 | PreserveLCSSA && CompletelyUnroll && |
404 | any_of(Range&: ExitBlocks, |
405 | P: [](const BasicBlock *BB) { return isa<PHINode>(Val: BB->begin()); }); |
406 | |
407 | // The current loop unroll pass can unroll loops that have |
408 | // (1) single latch; and |
409 | // (2a) latch is unconditional; or |
410 | // (2b) latch is conditional and is an exiting block |
411 | // FIXME: The implementation can be extended to work with more complicated |
412 | // cases, e.g. loops with multiple latches. |
413 | BranchInst *LatchBI = dyn_cast<BranchInst>(Val: LatchBlock->getTerminator()); |
414 | |
415 | // A conditional branch which exits the loop, which can be optimized to an |
416 | // unconditional branch in the unrolled loop in some cases. |
417 | bool LatchIsExiting = L->isLoopExiting(BB: LatchBlock); |
418 | if (!LatchBI || (LatchBI->isConditional() && !LatchIsExiting)) { |
419 | LLVM_DEBUG( |
420 | dbgs() << "Can't unroll; a conditional latch must exit the loop" ); |
421 | return LoopUnrollResult::Unmodified; |
422 | } |
423 | |
424 | // Loops containing convergent instructions cannot use runtime unrolling, |
425 | // as the prologue/epilogue may add additional control-dependencies to |
426 | // convergent operations. |
427 | LLVM_DEBUG( |
428 | { |
429 | bool HasConvergent = false; |
430 | for (auto &BB : L->blocks()) |
431 | for (auto &I : *BB) |
432 | if (auto *CB = dyn_cast<CallBase>(&I)) |
433 | HasConvergent |= CB->isConvergent(); |
434 | assert((!HasConvergent || !ULO.Runtime) && |
435 | "Can't runtime unroll if loop contains a convergent operation." ); |
436 | }); |
437 | |
438 | bool EpilogProfitability = |
439 | UnrollRuntimeEpilog.getNumOccurrences() ? UnrollRuntimeEpilog |
440 | : isEpilogProfitable(L); |
441 | |
442 | if (ULO.Runtime && |
443 | !UnrollRuntimeLoopRemainder(L, Count: ULO.Count, AllowExpensiveTripCount: ULO.AllowExpensiveTripCount, |
444 | UseEpilogRemainder: EpilogProfitability, UnrollRemainder: ULO.UnrollRemainder, |
445 | ForgetAllSCEV: ULO.ForgetAllSCEV, LI, SE, DT, AC, TTI, |
446 | PreserveLCSSA, ResultLoop: RemainderLoop)) { |
447 | if (ULO.Force) |
448 | ULO.Runtime = false; |
449 | else { |
450 | LLVM_DEBUG(dbgs() << "Won't unroll; remainder loop could not be " |
451 | "generated when assuming runtime trip count\n" ); |
452 | return LoopUnrollResult::Unmodified; |
453 | } |
454 | } |
455 | |
456 | using namespace ore; |
457 | // Report the unrolling decision. |
458 | if (CompletelyUnroll) { |
459 | LLVM_DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName() |
460 | << " with trip count " << ULO.Count << "!\n" ); |
461 | if (ORE) |
462 | ORE->emit(RemarkBuilder: [&]() { |
463 | return OptimizationRemark(DEBUG_TYPE, "FullyUnrolled" , L->getStartLoc(), |
464 | L->getHeader()) |
465 | << "completely unrolled loop with " |
466 | << NV("UnrollCount" , ULO.Count) << " iterations" ; |
467 | }); |
468 | } else { |
469 | LLVM_DEBUG(dbgs() << "UNROLLING loop %" << Header->getName() << " by " |
470 | << ULO.Count); |
471 | if (ULO.Runtime) |
472 | LLVM_DEBUG(dbgs() << " with run-time trip count" ); |
473 | LLVM_DEBUG(dbgs() << "!\n" ); |
474 | |
475 | if (ORE) |
476 | ORE->emit(RemarkBuilder: [&]() { |
477 | OptimizationRemark Diag(DEBUG_TYPE, "PartialUnrolled" , L->getStartLoc(), |
478 | L->getHeader()); |
479 | Diag << "unrolled loop by a factor of " << NV("UnrollCount" , ULO.Count); |
480 | if (ULO.Runtime) |
481 | Diag << " with run-time trip count" ; |
482 | return Diag; |
483 | }); |
484 | } |
485 | |
486 | // We are going to make changes to this loop. SCEV may be keeping cached info |
487 | // about it, in particular about backedge taken count. The changes we make |
488 | // are guaranteed to invalidate this information for our loop. It is tempting |
489 | // to only invalidate the loop being unrolled, but it is incorrect as long as |
490 | // all exiting branches from all inner loops have impact on the outer loops, |
491 | // and if something changes inside them then any of outer loops may also |
492 | // change. When we forget outermost loop, we also forget all contained loops |
493 | // and this is what we need here. |
494 | if (SE) { |
495 | if (ULO.ForgetAllSCEV) |
496 | SE->forgetAllLoops(); |
497 | else { |
498 | SE->forgetTopmostLoop(L); |
499 | SE->forgetBlockAndLoopDispositions(); |
500 | } |
501 | } |
502 | |
503 | if (!LatchIsExiting) |
504 | ++NumUnrolledNotLatch; |
505 | |
506 | // For the first iteration of the loop, we should use the precloned values for |
507 | // PHI nodes. Insert associations now. |
508 | ValueToValueMapTy LastValueMap; |
509 | std::vector<PHINode*> OrigPHINode; |
510 | for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(Val: I); ++I) { |
511 | OrigPHINode.push_back(x: cast<PHINode>(Val&: I)); |
512 | } |
513 | |
514 | std::vector<BasicBlock *> ; |
515 | std::vector<BasicBlock *> Latches; |
516 | Headers.push_back(x: Header); |
517 | Latches.push_back(x: LatchBlock); |
518 | |
519 | // The current on-the-fly SSA update requires blocks to be processed in |
520 | // reverse postorder so that LastValueMap contains the correct value at each |
521 | // exit. |
522 | LoopBlocksDFS DFS(L); |
523 | DFS.perform(LI); |
524 | |
525 | // Stash the DFS iterators before adding blocks to the loop. |
526 | LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO(); |
527 | LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO(); |
528 | |
529 | std::vector<BasicBlock*> UnrolledLoopBlocks = L->getBlocks(); |
530 | |
531 | // Loop Unrolling might create new loops. While we do preserve LoopInfo, we |
532 | // might break loop-simplified form for these loops (as they, e.g., would |
533 | // share the same exit blocks). We'll keep track of loops for which we can |
534 | // break this so that later we can re-simplify them. |
535 | SmallSetVector<Loop *, 4> LoopsToSimplify; |
536 | for (Loop *SubLoop : *L) |
537 | LoopsToSimplify.insert(X: SubLoop); |
538 | |
539 | // When a FSDiscriminator is enabled, we don't need to add the multiply |
540 | // factors to the discriminators. |
541 | if (Header->getParent()->shouldEmitDebugInfoForProfiling() && |
542 | !EnableFSDiscriminator) |
543 | for (BasicBlock *BB : L->getBlocks()) |
544 | for (Instruction &I : *BB) |
545 | if (!I.isDebugOrPseudoInst()) |
546 | if (const DILocation *DIL = I.getDebugLoc()) { |
547 | auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(DF: ULO.Count); |
548 | if (NewDIL) |
549 | I.setDebugLoc(*NewDIL); |
550 | else |
551 | LLVM_DEBUG(dbgs() |
552 | << "Failed to create new discriminator: " |
553 | << DIL->getFilename() << " Line: " << DIL->getLine()); |
554 | } |
555 | |
556 | // Identify what noalias metadata is inside the loop: if it is inside the |
557 | // loop, the associated metadata must be cloned for each iteration. |
558 | SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes; |
559 | identifyNoAliasScopesToClone(BBs: L->getBlocks(), NoAliasDeclScopes&: LoopLocalNoAliasDeclScopes); |
560 | |
561 | // We place the unrolled iterations immediately after the original loop |
562 | // latch. This is a reasonable default placement if we don't have block |
563 | // frequencies, and if we do, well the layout will be adjusted later. |
564 | auto BlockInsertPt = std::next(x: LatchBlock->getIterator()); |
565 | for (unsigned It = 1; It != ULO.Count; ++It) { |
566 | SmallVector<BasicBlock *, 8> NewBlocks; |
567 | SmallDenseMap<const Loop *, Loop *, 4> NewLoops; |
568 | NewLoops[L] = L; |
569 | |
570 | for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) { |
571 | ValueToValueMapTy VMap; |
572 | BasicBlock *New = CloneBasicBlock(BB: *BB, VMap, NameSuffix: "." + Twine(It)); |
573 | Header->getParent()->insert(Position: BlockInsertPt, BB: New); |
574 | |
575 | assert((*BB != Header || LI->getLoopFor(*BB) == L) && |
576 | "Header should not be in a sub-loop" ); |
577 | // Tell LI about New. |
578 | const Loop *OldLoop = addClonedBlockToLoopInfo(OriginalBB: *BB, ClonedBB: New, LI, NewLoops); |
579 | if (OldLoop) |
580 | LoopsToSimplify.insert(X: NewLoops[OldLoop]); |
581 | |
582 | if (*BB == Header) |
583 | // Loop over all of the PHI nodes in the block, changing them to use |
584 | // the incoming values from the previous block. |
585 | for (PHINode *OrigPHI : OrigPHINode) { |
586 | PHINode *NewPHI = cast<PHINode>(Val&: VMap[OrigPHI]); |
587 | Value *InVal = NewPHI->getIncomingValueForBlock(BB: LatchBlock); |
588 | if (Instruction *InValI = dyn_cast<Instruction>(Val: InVal)) |
589 | if (It > 1 && L->contains(Inst: InValI)) |
590 | InVal = LastValueMap[InValI]; |
591 | VMap[OrigPHI] = InVal; |
592 | NewPHI->eraseFromParent(); |
593 | } |
594 | |
595 | // Update our running map of newest clones |
596 | LastValueMap[*BB] = New; |
597 | for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end(); |
598 | VI != VE; ++VI) |
599 | LastValueMap[VI->first] = VI->second; |
600 | |
601 | // Add phi entries for newly created values to all exit blocks. |
602 | for (BasicBlock *Succ : successors(BB: *BB)) { |
603 | if (L->contains(BB: Succ)) |
604 | continue; |
605 | for (PHINode &PHI : Succ->phis()) { |
606 | Value *Incoming = PHI.getIncomingValueForBlock(BB: *BB); |
607 | ValueToValueMapTy::iterator It = LastValueMap.find(Val: Incoming); |
608 | if (It != LastValueMap.end()) |
609 | Incoming = It->second; |
610 | PHI.addIncoming(V: Incoming, BB: New); |
611 | SE->forgetValue(V: &PHI); |
612 | } |
613 | } |
614 | // Keep track of new headers and latches as we create them, so that |
615 | // we can insert the proper branches later. |
616 | if (*BB == Header) |
617 | Headers.push_back(x: New); |
618 | if (*BB == LatchBlock) |
619 | Latches.push_back(x: New); |
620 | |
621 | // Keep track of the exiting block and its successor block contained in |
622 | // the loop for the current iteration. |
623 | auto ExitInfoIt = ExitInfos.find(Val: *BB); |
624 | if (ExitInfoIt != ExitInfos.end()) |
625 | ExitInfoIt->second.ExitingBlocks.push_back(Elt: New); |
626 | |
627 | NewBlocks.push_back(Elt: New); |
628 | UnrolledLoopBlocks.push_back(x: New); |
629 | |
630 | // Update DomTree: since we just copy the loop body, and each copy has a |
631 | // dedicated entry block (copy of the header block), this header's copy |
632 | // dominates all copied blocks. That means, dominance relations in the |
633 | // copied body are the same as in the original body. |
634 | if (*BB == Header) |
635 | DT->addNewBlock(BB: New, DomBB: Latches[It - 1]); |
636 | else { |
637 | auto BBDomNode = DT->getNode(BB: *BB); |
638 | auto BBIDom = BBDomNode->getIDom(); |
639 | BasicBlock *OriginalBBIDom = BBIDom->getBlock(); |
640 | DT->addNewBlock( |
641 | BB: New, DomBB: cast<BasicBlock>(Val&: LastValueMap[cast<Value>(Val: OriginalBBIDom)])); |
642 | } |
643 | } |
644 | |
645 | // Remap all instructions in the most recent iteration |
646 | remapInstructionsInBlocks(Blocks: NewBlocks, VMap&: LastValueMap); |
647 | for (BasicBlock *NewBlock : NewBlocks) |
648 | for (Instruction &I : *NewBlock) |
649 | if (auto *II = dyn_cast<AssumeInst>(Val: &I)) |
650 | AC->registerAssumption(CI: II); |
651 | |
652 | { |
653 | // Identify what other metadata depends on the cloned version. After |
654 | // cloning, replace the metadata with the corrected version for both |
655 | // memory instructions and noalias intrinsics. |
656 | std::string ext = (Twine("It" ) + Twine(It)).str(); |
657 | cloneAndAdaptNoAliasScopes(NoAliasDeclScopes: LoopLocalNoAliasDeclScopes, NewBlocks, |
658 | Context&: Header->getContext(), Ext: ext); |
659 | } |
660 | } |
661 | |
662 | // Loop over the PHI nodes in the original block, setting incoming values. |
663 | for (PHINode *PN : OrigPHINode) { |
664 | if (CompletelyUnroll) { |
665 | PN->replaceAllUsesWith(V: PN->getIncomingValueForBlock(BB: Preheader)); |
666 | PN->eraseFromParent(); |
667 | } else if (ULO.Count > 1) { |
668 | Value *InVal = PN->removeIncomingValue(BB: LatchBlock, DeletePHIIfEmpty: false); |
669 | // If this value was defined in the loop, take the value defined by the |
670 | // last iteration of the loop. |
671 | if (Instruction *InValI = dyn_cast<Instruction>(Val: InVal)) { |
672 | if (L->contains(Inst: InValI)) |
673 | InVal = LastValueMap[InVal]; |
674 | } |
675 | assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch" ); |
676 | PN->addIncoming(V: InVal, BB: Latches.back()); |
677 | } |
678 | } |
679 | |
680 | // Connect latches of the unrolled iterations to the headers of the next |
681 | // iteration. Currently they point to the header of the same iteration. |
682 | for (unsigned i = 0, e = Latches.size(); i != e; ++i) { |
683 | unsigned j = (i + 1) % e; |
684 | Latches[i]->getTerminator()->replaceSuccessorWith(OldBB: Headers[i], NewBB: Headers[j]); |
685 | } |
686 | |
687 | // Update dominators of blocks we might reach through exits. |
688 | // Immediate dominator of such block might change, because we add more |
689 | // routes which can lead to the exit: we can now reach it from the copied |
690 | // iterations too. |
691 | if (ULO.Count > 1) { |
692 | for (auto *BB : OriginalLoopBlocks) { |
693 | auto *BBDomNode = DT->getNode(BB); |
694 | SmallVector<BasicBlock *, 16> ChildrenToUpdate; |
695 | for (auto *ChildDomNode : BBDomNode->children()) { |
696 | auto *ChildBB = ChildDomNode->getBlock(); |
697 | if (!L->contains(BB: ChildBB)) |
698 | ChildrenToUpdate.push_back(Elt: ChildBB); |
699 | } |
700 | // The new idom of the block will be the nearest common dominator |
701 | // of all copies of the previous idom. This is equivalent to the |
702 | // nearest common dominator of the previous idom and the first latch, |
703 | // which dominates all copies of the previous idom. |
704 | BasicBlock *NewIDom = DT->findNearestCommonDominator(A: BB, B: LatchBlock); |
705 | for (auto *ChildBB : ChildrenToUpdate) |
706 | DT->changeImmediateDominator(BB: ChildBB, NewBB: NewIDom); |
707 | } |
708 | } |
709 | |
710 | assert(!UnrollVerifyDomtree || |
711 | DT->verify(DominatorTree::VerificationLevel::Fast)); |
712 | |
713 | SmallVector<DominatorTree::UpdateType> DTUpdates; |
714 | auto SetDest = [&](BasicBlock *Src, bool WillExit, bool ExitOnTrue) { |
715 | auto *Term = cast<BranchInst>(Val: Src->getTerminator()); |
716 | const unsigned Idx = ExitOnTrue ^ WillExit; |
717 | BasicBlock *Dest = Term->getSuccessor(i: Idx); |
718 | BasicBlock *DeadSucc = Term->getSuccessor(i: 1-Idx); |
719 | |
720 | // Remove predecessors from all non-Dest successors. |
721 | DeadSucc->removePredecessor(Pred: Src, /* KeepOneInputPHIs */ true); |
722 | |
723 | // Replace the conditional branch with an unconditional one. |
724 | BranchInst::Create(IfTrue: Dest, InsertBefore: Term->getIterator()); |
725 | Term->eraseFromParent(); |
726 | |
727 | DTUpdates.emplace_back(Args: DominatorTree::Delete, Args&: Src, Args&: DeadSucc); |
728 | }; |
729 | |
730 | auto WillExit = [&](const ExitInfo &Info, unsigned i, unsigned j, |
731 | bool IsLatch) -> std::optional<bool> { |
732 | if (CompletelyUnroll) { |
733 | if (PreserveOnlyFirst) { |
734 | if (i == 0) |
735 | return std::nullopt; |
736 | return j == 0; |
737 | } |
738 | // Complete (but possibly inexact) unrolling |
739 | if (j == 0) |
740 | return true; |
741 | if (Info.TripCount && j != Info.TripCount) |
742 | return false; |
743 | return std::nullopt; |
744 | } |
745 | |
746 | if (ULO.Runtime) { |
747 | // If runtime unrolling inserts a prologue, information about non-latch |
748 | // exits may be stale. |
749 | if (IsLatch && j != 0) |
750 | return false; |
751 | return std::nullopt; |
752 | } |
753 | |
754 | if (j != Info.BreakoutTrip && |
755 | (Info.TripMultiple == 0 || j % Info.TripMultiple != 0)) { |
756 | // If we know the trip count or a multiple of it, we can safely use an |
757 | // unconditional branch for some iterations. |
758 | return false; |
759 | } |
760 | return std::nullopt; |
761 | }; |
762 | |
763 | // Fold branches for iterations where we know that they will exit or not |
764 | // exit. |
765 | for (auto &Pair : ExitInfos) { |
766 | ExitInfo &Info = Pair.second; |
767 | for (unsigned i = 0, e = Info.ExitingBlocks.size(); i != e; ++i) { |
768 | // The branch destination. |
769 | unsigned j = (i + 1) % e; |
770 | bool IsLatch = Pair.first == LatchBlock; |
771 | std::optional<bool> KnownWillExit = WillExit(Info, i, j, IsLatch); |
772 | if (!KnownWillExit) { |
773 | if (!Info.FirstExitingBlock) |
774 | Info.FirstExitingBlock = Info.ExitingBlocks[i]; |
775 | continue; |
776 | } |
777 | |
778 | // We don't fold known-exiting branches for non-latch exits here, |
779 | // because this ensures that both all loop blocks and all exit blocks |
780 | // remain reachable in the CFG. |
781 | // TODO: We could fold these branches, but it would require much more |
782 | // sophisticated updates to LoopInfo. |
783 | if (*KnownWillExit && !IsLatch) { |
784 | if (!Info.FirstExitingBlock) |
785 | Info.FirstExitingBlock = Info.ExitingBlocks[i]; |
786 | continue; |
787 | } |
788 | |
789 | SetDest(Info.ExitingBlocks[i], *KnownWillExit, Info.ExitOnTrue); |
790 | } |
791 | } |
792 | |
793 | DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); |
794 | DomTreeUpdater *DTUToUse = &DTU; |
795 | if (ExitingBlocks.size() == 1 && ExitInfos.size() == 1) { |
796 | // Manually update the DT if there's a single exiting node. In that case |
797 | // there's a single exit node and it is sufficient to update the nodes |
798 | // immediately dominated by the original exiting block. They will become |
799 | // dominated by the first exiting block that leaves the loop after |
800 | // unrolling. Note that the CFG inside the loop does not change, so there's |
801 | // no need to update the DT inside the unrolled loop. |
802 | DTUToUse = nullptr; |
803 | auto &[OriginalExit, Info] = *ExitInfos.begin(); |
804 | if (!Info.FirstExitingBlock) |
805 | Info.FirstExitingBlock = Info.ExitingBlocks.back(); |
806 | for (auto *C : to_vector(Range: DT->getNode(BB: OriginalExit)->children())) { |
807 | if (L->contains(BB: C->getBlock())) |
808 | continue; |
809 | C->setIDom(DT->getNode(BB: Info.FirstExitingBlock)); |
810 | } |
811 | } else { |
812 | DTU.applyUpdates(Updates: DTUpdates); |
813 | } |
814 | |
815 | // When completely unrolling, the last latch becomes unreachable. |
816 | if (!LatchIsExiting && CompletelyUnroll) { |
817 | // There is no need to update the DT here, because there must be a unique |
818 | // latch. Hence if the latch is not exiting it must directly branch back to |
819 | // the original loop header and does not dominate any nodes. |
820 | assert(LatchBlock->getSingleSuccessor() && "Loop with multiple latches?" ); |
821 | changeToUnreachable(I: Latches.back()->getTerminator(), PreserveLCSSA); |
822 | } |
823 | |
824 | // Merge adjacent basic blocks, if possible. |
825 | for (BasicBlock *Latch : Latches) { |
826 | BranchInst *Term = dyn_cast<BranchInst>(Val: Latch->getTerminator()); |
827 | assert((Term || |
828 | (CompletelyUnroll && !LatchIsExiting && Latch == Latches.back())) && |
829 | "Need a branch as terminator, except when fully unrolling with " |
830 | "unconditional latch" ); |
831 | if (Term && Term->isUnconditional()) { |
832 | BasicBlock *Dest = Term->getSuccessor(i: 0); |
833 | BasicBlock *Fold = Dest->getUniquePredecessor(); |
834 | if (MergeBlockIntoPredecessor(BB: Dest, /*DTU=*/DTUToUse, LI, |
835 | /*MSSAU=*/nullptr, /*MemDep=*/nullptr, |
836 | /*PredecessorWithTwoSuccessors=*/false, |
837 | DT: DTUToUse ? nullptr : DT)) { |
838 | // Dest has been folded into Fold. Update our worklists accordingly. |
839 | std::replace(first: Latches.begin(), last: Latches.end(), old_value: Dest, new_value: Fold); |
840 | llvm::erase(C&: UnrolledLoopBlocks, V: Dest); |
841 | } |
842 | } |
843 | } |
844 | |
845 | if (DTUToUse) { |
846 | // Apply updates to the DomTree. |
847 | DT = &DTU.getDomTree(); |
848 | } |
849 | assert(!UnrollVerifyDomtree || |
850 | DT->verify(DominatorTree::VerificationLevel::Fast)); |
851 | |
852 | // At this point, the code is well formed. We now simplify the unrolled loop, |
853 | // doing constant propagation and dead code elimination as we go. |
854 | simplifyLoopAfterUnroll(L, SimplifyIVs: !CompletelyUnroll && ULO.Count > 1, LI, SE, DT, AC, |
855 | TTI); |
856 | |
857 | NumCompletelyUnrolled += CompletelyUnroll; |
858 | ++NumUnrolled; |
859 | |
860 | Loop *OuterL = L->getParentLoop(); |
861 | // Update LoopInfo if the loop is completely removed. |
862 | if (CompletelyUnroll) { |
863 | LI->erase(L); |
864 | // We shouldn't try to use `L` anymore. |
865 | L = nullptr; |
866 | } else if (OriginalTripCount) { |
867 | // Update the trip count. Note that the remainder has already logic |
868 | // computing it in `UnrollRuntimeLoopRemainder`. |
869 | setLoopEstimatedTripCount(L, EstimatedTripCount: *OriginalTripCount / ULO.Count, |
870 | EstimatedLoopInvocationWeight); |
871 | } |
872 | |
873 | // LoopInfo should not be valid, confirm that. |
874 | if (UnrollVerifyLoopInfo) |
875 | LI->verify(DomTree: *DT); |
876 | |
877 | // After complete unrolling most of the blocks should be contained in OuterL. |
878 | // However, some of them might happen to be out of OuterL (e.g. if they |
879 | // precede a loop exit). In this case we might need to insert PHI nodes in |
880 | // order to preserve LCSSA form. |
881 | // We don't need to check this if we already know that we need to fix LCSSA |
882 | // form. |
883 | // TODO: For now we just recompute LCSSA for the outer loop in this case, but |
884 | // it should be possible to fix it in-place. |
885 | if (PreserveLCSSA && OuterL && CompletelyUnroll && !NeedToFixLCSSA) |
886 | NeedToFixLCSSA |= ::needToInsertPhisForLCSSA(L: OuterL, Blocks: UnrolledLoopBlocks, LI); |
887 | |
888 | // Make sure that loop-simplify form is preserved. We want to simplify |
889 | // at least one layer outside of the loop that was unrolled so that any |
890 | // changes to the parent loop exposed by the unrolling are considered. |
891 | if (OuterL) { |
892 | // OuterL includes all loops for which we can break loop-simplify, so |
893 | // it's sufficient to simplify only it (it'll recursively simplify inner |
894 | // loops too). |
895 | if (NeedToFixLCSSA) { |
896 | // LCSSA must be performed on the outermost affected loop. The unrolled |
897 | // loop's last loop latch is guaranteed to be in the outermost loop |
898 | // after LoopInfo's been updated by LoopInfo::erase. |
899 | Loop *LatchLoop = LI->getLoopFor(BB: Latches.back()); |
900 | Loop *FixLCSSALoop = OuterL; |
901 | if (!FixLCSSALoop->contains(L: LatchLoop)) |
902 | while (FixLCSSALoop->getParentLoop() != LatchLoop) |
903 | FixLCSSALoop = FixLCSSALoop->getParentLoop(); |
904 | |
905 | formLCSSARecursively(L&: *FixLCSSALoop, DT: *DT, LI, SE); |
906 | } else if (PreserveLCSSA) { |
907 | assert(OuterL->isLCSSAForm(*DT) && |
908 | "Loops should be in LCSSA form after loop-unroll." ); |
909 | } |
910 | |
911 | // TODO: That potentially might be compile-time expensive. We should try |
912 | // to fix the loop-simplified form incrementally. |
913 | simplifyLoop(L: OuterL, DT, LI, SE, AC, MSSAU: nullptr, PreserveLCSSA); |
914 | } else { |
915 | // Simplify loops for which we might've broken loop-simplify form. |
916 | for (Loop *SubLoop : LoopsToSimplify) |
917 | simplifyLoop(L: SubLoop, DT, LI, SE, AC, MSSAU: nullptr, PreserveLCSSA); |
918 | } |
919 | |
920 | return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled |
921 | : LoopUnrollResult::PartiallyUnrolled; |
922 | } |
923 | |
924 | /// Given an llvm.loop loop id metadata node, returns the loop hint metadata |
925 | /// node with the given name (for example, "llvm.loop.unroll.count"). If no |
926 | /// such metadata node exists, then nullptr is returned. |
927 | MDNode *llvm::GetUnrollMetadata(MDNode *LoopID, StringRef Name) { |
928 | // First operand should refer to the loop id itself. |
929 | assert(LoopID->getNumOperands() > 0 && "requires at least one operand" ); |
930 | assert(LoopID->getOperand(0) == LoopID && "invalid loop id" ); |
931 | |
932 | for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) { |
933 | MDNode *MD = dyn_cast<MDNode>(Val: LoopID->getOperand(I: i)); |
934 | if (!MD) |
935 | continue; |
936 | |
937 | MDString *S = dyn_cast<MDString>(Val: MD->getOperand(I: 0)); |
938 | if (!S) |
939 | continue; |
940 | |
941 | if (Name.equals(RHS: S->getString())) |
942 | return MD; |
943 | } |
944 | return nullptr; |
945 | } |
946 | |