1//===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
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 common loop utility functions.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Transforms/Utils/LoopUtils.h"
14#include "llvm/ADT/DenseSet.h"
15#include "llvm/ADT/PriorityWorklist.h"
16#include "llvm/ADT/ScopeExit.h"
17#include "llvm/ADT/SetVector.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/Analysis/AliasAnalysis.h"
21#include "llvm/Analysis/BasicAliasAnalysis.h"
22#include "llvm/Analysis/DomTreeUpdater.h"
23#include "llvm/Analysis/GlobalsModRef.h"
24#include "llvm/Analysis/InstSimplifyFolder.h"
25#include "llvm/Analysis/LoopAccessAnalysis.h"
26#include "llvm/Analysis/LoopInfo.h"
27#include "llvm/Analysis/LoopPass.h"
28#include "llvm/Analysis/MemorySSA.h"
29#include "llvm/Analysis/MemorySSAUpdater.h"
30#include "llvm/Analysis/ScalarEvolution.h"
31#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
32#include "llvm/Analysis/ScalarEvolutionExpressions.h"
33#include "llvm/IR/DIBuilder.h"
34#include "llvm/IR/Dominators.h"
35#include "llvm/IR/Instructions.h"
36#include "llvm/IR/IntrinsicInst.h"
37#include "llvm/IR/MDBuilder.h"
38#include "llvm/IR/Module.h"
39#include "llvm/IR/PatternMatch.h"
40#include "llvm/IR/ProfDataUtils.h"
41#include "llvm/IR/ValueHandle.h"
42#include "llvm/InitializePasses.h"
43#include "llvm/Pass.h"
44#include "llvm/Support/Compiler.h"
45#include "llvm/Support/Debug.h"
46#include "llvm/Transforms/Utils/BasicBlockUtils.h"
47#include "llvm/Transforms/Utils/Local.h"
48#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
49
50using namespace llvm;
51using namespace llvm::PatternMatch;
52
53#define DEBUG_TYPE "loop-utils"
54
55static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced";
56static const char *LLVMLoopDisableLICM = "llvm.licm.disable";
57
58bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
59 MemorySSAUpdater *MSSAU,
60 bool PreserveLCSSA) {
61 bool Changed = false;
62
63 // We re-use a vector for the in-loop predecesosrs.
64 SmallVector<BasicBlock *, 4> InLoopPredecessors;
65
66 auto RewriteExit = [&](BasicBlock *BB) {
67 assert(InLoopPredecessors.empty() &&
68 "Must start with an empty predecessors list!");
69 llvm::scope_exit Cleanup([&] { InLoopPredecessors.clear(); });
70
71 // See if there are any non-loop predecessors of this exit block and
72 // keep track of the in-loop predecessors.
73 bool IsDedicatedExit = true;
74 for (auto *PredBB : predecessors(BB))
75 if (L->contains(BB: PredBB)) {
76 if (isa<IndirectBrInst>(Val: PredBB->getTerminator()))
77 // We cannot rewrite exiting edges from an indirectbr.
78 return false;
79
80 InLoopPredecessors.push_back(Elt: PredBB);
81 } else {
82 IsDedicatedExit = false;
83 }
84
85 assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
86
87 // Nothing to do if this is already a dedicated exit.
88 if (IsDedicatedExit)
89 return false;
90
91 auto *NewExitBB = SplitBlockPredecessors(
92 BB, Preds: InLoopPredecessors, Suffix: ".loopexit", DT, LI, MSSAU, PreserveLCSSA);
93
94 if (!NewExitBB)
95 LLVM_DEBUG(
96 dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
97 << *L << "\n");
98 else
99 LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
100 << NewExitBB->getName() << "\n");
101 return true;
102 };
103
104 // Walk the exit blocks directly rather than building up a data structure for
105 // them, but only visit each one once.
106 SmallPtrSet<BasicBlock *, 4> Visited;
107 for (auto *BB : L->blocks())
108 for (auto *SuccBB : successors(BB)) {
109 // We're looking for exit blocks so skip in-loop successors.
110 if (L->contains(BB: SuccBB))
111 continue;
112
113 // Visit each exit block exactly once.
114 if (!Visited.insert(Ptr: SuccBB).second)
115 continue;
116
117 Changed |= RewriteExit(SuccBB);
118 }
119
120 return Changed;
121}
122
123/// Returns the instructions that use values defined in the loop.
124SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
125 SmallVector<Instruction *, 8> UsedOutside;
126
127 for (auto *Block : L->getBlocks())
128 // FIXME: I believe that this could use copy_if if the Inst reference could
129 // be adapted into a pointer.
130 for (auto &Inst : *Block) {
131 auto Users = Inst.users();
132 if (any_of(Range&: Users, P: [&](User *U) {
133 auto *Use = cast<Instruction>(Val: U);
134 return !L->contains(BB: Use->getParent());
135 }))
136 UsedOutside.push_back(Elt: &Inst);
137 }
138
139 return UsedOutside;
140}
141
142void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
143 // By definition, all loop passes need the LoopInfo analysis and the
144 // Dominator tree it depends on. Because they all participate in the loop
145 // pass manager, they must also preserve these.
146 AU.addRequired<DominatorTreeWrapperPass>();
147 AU.addPreserved<DominatorTreeWrapperPass>();
148 AU.addRequired<LoopInfoWrapperPass>();
149 AU.addPreserved<LoopInfoWrapperPass>();
150
151 // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
152 // here because users shouldn't directly get them from this header.
153 extern char &LoopSimplifyID;
154 extern char &LCSSAID;
155 AU.addRequiredID(ID&: LoopSimplifyID);
156 AU.addPreservedID(ID&: LoopSimplifyID);
157 AU.addRequiredID(ID&: LCSSAID);
158 AU.addPreservedID(ID&: LCSSAID);
159 // This is used in the LPPassManager to perform LCSSA verification on passes
160 // which preserve lcssa form
161 AU.addRequired<LCSSAVerificationPass>();
162 AU.addPreserved<LCSSAVerificationPass>();
163
164 // Loop passes are designed to run inside of a loop pass manager which means
165 // that any function analyses they require must be required by the first loop
166 // pass in the manager (so that it is computed before the loop pass manager
167 // runs) and preserved by all loop pasess in the manager. To make this
168 // reasonably robust, the set needed for most loop passes is maintained here.
169 // If your loop pass requires an analysis not listed here, you will need to
170 // carefully audit the loop pass manager nesting structure that results.
171 AU.addRequired<AAResultsWrapperPass>();
172 AU.addPreserved<AAResultsWrapperPass>();
173 AU.addPreserved<BasicAAWrapperPass>();
174 AU.addPreserved<GlobalsAAWrapperPass>();
175 AU.addPreserved<SCEVAAWrapperPass>();
176 AU.addRequired<ScalarEvolutionWrapperPass>();
177 AU.addPreserved<ScalarEvolutionWrapperPass>();
178 // FIXME: When all loop passes preserve MemorySSA, it can be required and
179 // preserved here instead of the individual handling in each pass.
180}
181
182/// Manually defined generic "LoopPass" dependency initialization. This is used
183/// to initialize the exact set of passes from above in \c
184/// getLoopAnalysisUsage. It can be used within a loop pass's initialization
185/// with:
186///
187/// INITIALIZE_PASS_DEPENDENCY(LoopPass)
188///
189/// As-if "LoopPass" were a pass.
190void llvm::initializeLoopPassPass(PassRegistry &Registry) {
191 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
192 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
193 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
194 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
195 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
196 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
197 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
198 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
199 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
200 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
201}
202
203/// Create MDNode for input string.
204static MDNode *createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V) {
205 LLVMContext &Context = TheLoop->getHeader()->getContext();
206 Metadata *MDs[] = {
207 MDString::get(Context, Str: Name),
208 ConstantAsMetadata::get(C: ConstantInt::get(Ty: Type::getInt32Ty(C&: Context), V))};
209 return MDNode::get(Context, MDs);
210}
211
212/// Set input string into loop metadata by keeping other values intact.
213/// If the string is already in loop metadata update value if it is
214/// different.
215void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *StringMD,
216 unsigned V) {
217 SmallVector<Metadata *, 4> MDs(1);
218 // If the loop already has metadata, retain it.
219 MDNode *LoopID = TheLoop->getLoopID();
220 if (LoopID) {
221 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
222 MDNode *Node = cast<MDNode>(Val: LoopID->getOperand(I: i));
223 // If it is of form key = value, try to parse it.
224 if (Node->getNumOperands() == 2) {
225 MDString *S = dyn_cast<MDString>(Val: Node->getOperand(I: 0));
226 if (S && S->getString() == StringMD) {
227 ConstantInt *IntMD =
228 mdconst::extract_or_null<ConstantInt>(MD: Node->getOperand(I: 1));
229 if (IntMD && IntMD->getSExtValue() == V)
230 // It is already in place. Do nothing.
231 return;
232 // We need to update the value, so just skip it here and it will
233 // be added after copying other existed nodes.
234 continue;
235 }
236 }
237 MDs.push_back(Elt: Node);
238 }
239 }
240 // Add new metadata.
241 MDs.push_back(Elt: createStringMetadata(TheLoop, Name: StringMD, V));
242 // Replace current metadata node with new one.
243 LLVMContext &Context = TheLoop->getHeader()->getContext();
244 MDNode *NewLoopID = MDNode::get(Context, MDs);
245 // Set operand 0 to refer to the loop id itself.
246 NewLoopID->replaceOperandWith(I: 0, New: NewLoopID);
247 TheLoop->setLoopID(NewLoopID);
248}
249
250void llvm::addStringMetadataToLoop(Loop *TheLoop, StringRef StringMD) {
251 LLVMContext &Context = TheLoop->getHeader()->getContext();
252 SmallVector<Metadata *, 4> MDs(1);
253 // Retain existing metadata, skipping a name-only node with the same string.
254 if (MDNode *LoopID = TheLoop->getLoopID())
255 for (const MDOperand &Op : drop_begin(RangeOrContainer: LoopID->operands())) {
256 MDNode *Node = cast<MDNode>(Val: Op);
257 if (Node->getNumOperands() == 1)
258 if (auto *S = dyn_cast<MDString>(Val: Node->getOperand(I: 0)))
259 if (S->getString() == StringMD)
260 return;
261 MDs.push_back(Elt: Node);
262 }
263 MDs.push_back(Elt: MDNode::get(Context, MDs: {MDString::get(Context, Str: StringMD)}));
264 MDNode *NewLoopID = MDNode::get(Context, MDs);
265 // Set operand 0 to refer to the loop id itself.
266 NewLoopID->replaceOperandWith(I: 0, New: NewLoopID);
267 TheLoop->setLoopID(NewLoopID);
268}
269
270std::optional<ElementCount>
271llvm::getOptionalElementCountLoopAttribute(const Loop *TheLoop) {
272 std::optional<int> Width =
273 getOptionalIntLoopAttribute(TheLoop, Name: "llvm.loop.vectorize.width");
274
275 if (Width) {
276 // Presence of the scalable.enable unit node means a scalable ElementCount;
277 // disable or absence both mean fixed-width.
278 bool IsScalable =
279 getBooleanLoopAttribute(TheLoop, Name: "llvm.loop.vectorize.scalable.enable");
280 return ElementCount::get(MinVal: *Width, Scalable: IsScalable);
281 }
282
283 return std::nullopt;
284}
285
286std::optional<MDNode *> llvm::makeFollowupLoopID(
287 MDNode *OrigLoopID, ArrayRef<StringRef> FollowupOptions,
288 const char *InheritOptionsExceptPrefix, bool AlwaysNew) {
289 if (!OrigLoopID) {
290 if (AlwaysNew)
291 return nullptr;
292 return std::nullopt;
293 }
294
295 assert(OrigLoopID->getOperand(0) == OrigLoopID);
296
297 bool InheritAllAttrs = !InheritOptionsExceptPrefix;
298 bool InheritSomeAttrs =
299 InheritOptionsExceptPrefix && InheritOptionsExceptPrefix[0] != '\0';
300 SmallVector<Metadata *, 8> MDs;
301 MDs.push_back(Elt: nullptr);
302
303 bool Changed = false;
304 if (InheritAllAttrs || InheritSomeAttrs) {
305 for (const MDOperand &Existing : drop_begin(RangeOrContainer: OrigLoopID->operands())) {
306 MDNode *Op = cast<MDNode>(Val: Existing.get());
307
308 auto InheritThisAttribute = [InheritSomeAttrs,
309 InheritOptionsExceptPrefix](MDNode *Op) {
310 if (!InheritSomeAttrs)
311 return false;
312
313 // Skip malformatted attribute metadata nodes.
314 if (Op->getNumOperands() == 0)
315 return true;
316 Metadata *NameMD = Op->getOperand(I: 0).get();
317 if (!isa<MDString>(Val: NameMD))
318 return true;
319 StringRef AttrName = cast<MDString>(Val: NameMD)->getString();
320
321 // Do not inherit excluded attributes.
322 return !AttrName.starts_with(Prefix: InheritOptionsExceptPrefix);
323 };
324
325 if (InheritThisAttribute(Op))
326 MDs.push_back(Elt: Op);
327 else
328 Changed = true;
329 }
330 } else {
331 // Modified if we dropped at least one attribute.
332 Changed = OrigLoopID->getNumOperands() > 1;
333 }
334
335 bool HasAnyFollowup = false;
336 for (StringRef OptionName : FollowupOptions) {
337 MDNode *FollowupNode = findOptionMDForLoopID(LoopID: OrigLoopID, Name: OptionName);
338 if (!FollowupNode)
339 continue;
340
341 HasAnyFollowup = true;
342 for (const MDOperand &Option : drop_begin(RangeOrContainer: FollowupNode->operands())) {
343 MDs.push_back(Elt: Option.get());
344 Changed = true;
345 }
346 }
347
348 // Attributes of the followup loop not specified explicity, so signal to the
349 // transformation pass to add suitable attributes.
350 if (!AlwaysNew && !HasAnyFollowup)
351 return std::nullopt;
352
353 // If no attributes were added or remove, the previous loop Id can be reused.
354 if (!AlwaysNew && !Changed)
355 return OrigLoopID;
356
357 // No attributes is equivalent to having no !llvm.loop metadata at all.
358 if (MDs.size() == 1)
359 return nullptr;
360
361 // Build the new loop ID.
362 MDTuple *FollowupLoopID = MDNode::get(Context&: OrigLoopID->getContext(), MDs);
363 FollowupLoopID->replaceOperandWith(I: 0, New: FollowupLoopID);
364 return FollowupLoopID;
365}
366
367bool llvm::hasDisableAllTransformsHint(const Loop *L) {
368 return getBooleanLoopAttribute(TheLoop: L, Name: LLVMLoopDisableNonforced);
369}
370
371bool llvm::hasDisableLICMTransformsHint(const Loop *L) {
372 return getBooleanLoopAttribute(TheLoop: L, Name: LLVMLoopDisableLICM);
373}
374
375StringRef llvm::getLoopVectorizeKindPrefix(const Loop *L) {
376 bool IsVectorBody = getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.vectorize.body");
377 bool IsEpilogue = getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.vectorize.epilogue");
378 if (IsVectorBody && IsEpilogue)
379 return "vectorized epilogue ";
380 if (IsVectorBody)
381 return "vectorized ";
382 if (IsEpilogue)
383 return "epilogue ";
384 return "";
385}
386
387TransformationMode llvm::hasUnrollTransformation(const Loop *L) {
388 if (getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.unroll.disable"))
389 return TM_SuppressedByUser;
390
391 std::optional<int> Count =
392 getOptionalIntLoopAttribute(TheLoop: L, Name: "llvm.loop.unroll.count");
393 if (Count)
394 return *Count == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
395
396 if (getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.unroll.enable"))
397 return TM_ForcedByUser;
398
399 if (getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.unroll.full"))
400 return TM_ForcedByUser;
401
402 if (hasDisableAllTransformsHint(L))
403 return TM_Disable;
404
405 return TM_Unspecified;
406}
407
408TransformationMode llvm::hasUnrollAndJamTransformation(const Loop *L) {
409 if (getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.unroll_and_jam.disable"))
410 return TM_SuppressedByUser;
411
412 std::optional<int> Count =
413 getOptionalIntLoopAttribute(TheLoop: L, Name: "llvm.loop.unroll_and_jam.count");
414 if (Count)
415 return *Count == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
416
417 if (getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.unroll_and_jam.enable"))
418 return TM_ForcedByUser;
419
420 if (hasDisableAllTransformsHint(L))
421 return TM_Disable;
422
423 return TM_Unspecified;
424}
425
426TransformationMode llvm::hasVectorizeTransformation(const Loop *L) {
427 if (getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.vectorize.disable"))
428 return TM_SuppressedByUser;
429
430 bool Enable = getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.vectorize.enable");
431
432 std::optional<ElementCount> VectorizeWidth =
433 getOptionalElementCountLoopAttribute(TheLoop: L);
434 std::optional<int> InterleaveCount =
435 getOptionalIntLoopAttribute(TheLoop: L, Name: "llvm.loop.interleave.count");
436
437 // 'Forcing' vector width and interleave count to one effectively disables
438 // this tranformation.
439 if (Enable && VectorizeWidth && VectorizeWidth->isScalar() &&
440 InterleaveCount == 1)
441 return TM_SuppressedByUser;
442
443 if (getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.isvectorized"))
444 return TM_Disable;
445
446 if (Enable)
447 return TM_ForcedByUser;
448
449 if ((VectorizeWidth && VectorizeWidth->isScalar()) && InterleaveCount == 1)
450 return TM_Disable;
451
452 if ((VectorizeWidth && VectorizeWidth->isVector()) || InterleaveCount > 1)
453 return TM_Enable;
454
455 if (hasDisableAllTransformsHint(L))
456 return TM_Disable;
457
458 return TM_Unspecified;
459}
460
461TransformationMode llvm::hasDistributeTransformation(const Loop *L) {
462 if (getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.distribute.disable"))
463 return TM_SuppressedByUser;
464
465 if (getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.distribute.enable"))
466 return TM_ForcedByUser;
467
468 if (hasDisableAllTransformsHint(L))
469 return TM_Disable;
470
471 return TM_Unspecified;
472}
473
474TransformationMode llvm::hasLICMVersioningTransformation(const Loop *L) {
475 if (getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.licm_versioning.disable"))
476 return TM_SuppressedByUser;
477
478 if (hasDisableAllTransformsHint(L))
479 return TM_Disable;
480
481 return TM_Unspecified;
482}
483
484/// Does a BFS from a given node to all of its children inside a given loop.
485/// The returned vector of basic blocks includes the starting point.
486SmallVector<BasicBlock *, 16> llvm::collectChildrenInLoop(DominatorTree *DT,
487 DomTreeNode *N,
488 const Loop *CurLoop) {
489 SmallVector<BasicBlock *, 16> Worklist;
490 auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
491 // Only include subregions in the top level loop.
492 BasicBlock *BB = DTN->getBlock();
493 if (CurLoop->contains(BB))
494 Worklist.push_back(Elt: DTN->getBlock());
495 };
496
497 AddRegionToWorklist(N);
498
499 for (size_t I = 0; I < Worklist.size(); I++) {
500 for (DomTreeNode *Child : DT->getNode(BB: Worklist[I])->children())
501 AddRegionToWorklist(Child);
502 }
503
504 return Worklist;
505}
506
507bool llvm::isAlmostDeadIV(PHINode *PN, BasicBlock *LatchBlock, Value *Cond) {
508 int LatchIdx = PN->getBasicBlockIndex(BB: LatchBlock);
509 assert(LatchIdx != -1 && "LatchBlock is not a case in this PHINode");
510 Value *IncV = PN->getIncomingValue(i: LatchIdx);
511
512 for (User *U : PN->users())
513 if (U != Cond && U != IncV) return false;
514
515 for (User *U : IncV->users())
516 if (U != Cond && U != PN) return false;
517 return true;
518}
519
520
521void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
522 LoopInfo *LI, MemorySSA *MSSA) {
523 assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
524 auto *Preheader = L->getLoopPreheader();
525 assert(Preheader && "Preheader should exist!");
526
527 std::unique_ptr<MemorySSAUpdater> MSSAU;
528 if (MSSA)
529 MSSAU = std::make_unique<MemorySSAUpdater>(args&: MSSA);
530
531 // Now that we know the removal is safe, remove the loop by changing the
532 // branch from the preheader to go to the single exit block.
533 //
534 // Because we're deleting a large chunk of code at once, the sequence in which
535 // we remove things is very important to avoid invalidation issues.
536
537 // Tell ScalarEvolution that the loop is deleted. Do this before
538 // deleting the loop so that ScalarEvolution can look at the loop
539 // to determine what it needs to clean up.
540 if (SE) {
541 SE->forgetLoop(L);
542 SE->forgetBlockAndLoopDispositions();
543 }
544
545 Instruction *OldTerm = Preheader->getTerminator();
546 assert(!OldTerm->mayHaveSideEffects() &&
547 "Preheader must end with a side-effect-free terminator");
548 assert(OldTerm->getNumSuccessors() == 1 &&
549 "Preheader must have a single successor");
550 // Connect the preheader to the exit block. Keep the old edge to the header
551 // around to perform the dominator tree update in two separate steps
552 // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
553 // preheader -> header.
554 //
555 //
556 // 0. Preheader 1. Preheader 2. Preheader
557 // | | | |
558 // V | V |
559 // Header <--\ | Header <--\ | Header <--\
560 // | | | | | | | | | | |
561 // | V | | | V | | | V |
562 // | Body --/ | | Body --/ | | Body --/
563 // V V V V V
564 // Exit Exit Exit
565 //
566 // By doing this is two separate steps we can perform the dominator tree
567 // update without using the batch update API.
568 //
569 // Even when the loop is never executed, we cannot remove the edge from the
570 // source block to the exit block. Consider the case where the unexecuted loop
571 // branches back to an outer loop. If we deleted the loop and removed the edge
572 // coming to this inner loop, this will break the outer loop structure (by
573 // deleting the backedge of the outer loop). If the outer loop is indeed a
574 // non-loop, it will be deleted in a future iteration of loop deletion pass.
575 IRBuilder<> Builder(OldTerm);
576
577 auto *ExitBlock = L->getUniqueExitBlock();
578 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
579 if (ExitBlock) {
580 assert(ExitBlock && "Should have a unique exit block!");
581 assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
582
583 Builder.CreateCondBr(Cond: Builder.getFalse(), True: L->getHeader(), False: ExitBlock);
584 // Remove the old branch. The conditional branch becomes a new terminator.
585 OldTerm->eraseFromParent();
586
587 // Rewrite phis in the exit block to get their inputs from the Preheader
588 // instead of the exiting block.
589 for (PHINode &P : ExitBlock->phis()) {
590 // Set the zero'th element of Phi to be from the preheader and remove all
591 // other incoming values. Given the loop has dedicated exits, all other
592 // incoming values must be from the exiting blocks.
593 int PredIndex = 0;
594 P.setIncomingBlock(i: PredIndex, BB: Preheader);
595 // Removes all incoming values from all other exiting blocks (including
596 // duplicate values from an exiting block).
597 // Nuke all entries except the zero'th entry which is the preheader entry.
598 P.removeIncomingValueIf(Predicate: [](unsigned Idx) { return Idx != 0; },
599 /* DeletePHIIfEmpty */ false);
600
601 assert((P.getNumIncomingValues() == 1 &&
602 P.getIncomingBlock(PredIndex) == Preheader) &&
603 "Should have exactly one value and that's from the preheader!");
604 }
605
606 if (DT) {
607 DTU.applyUpdates(Updates: {{DominatorTree::Insert, Preheader, ExitBlock}});
608 if (MSSA) {
609 MSSAU->applyUpdates(Updates: {{DominatorTree::Insert, Preheader, ExitBlock}},
610 DT&: *DT);
611 if (VerifyMemorySSA)
612 MSSA->verifyMemorySSA();
613 }
614 }
615
616 // Disconnect the loop body by branching directly to its exit.
617 Builder.SetInsertPoint(Preheader->getTerminator());
618 Builder.CreateBr(Dest: ExitBlock);
619 // Remove the old branch.
620 Preheader->getTerminator()->eraseFromParent();
621 } else {
622 assert((!LI || LI->hasNoExitBlocks(*L)) &&
623 "Loop should have either zero or one exit blocks.");
624
625 Builder.SetInsertPoint(OldTerm);
626 Builder.CreateUnreachable();
627 Preheader->getTerminator()->eraseFromParent();
628 }
629
630 if (DT) {
631 DTU.applyUpdates(Updates: {{DominatorTree::Delete, Preheader, L->getHeader()}});
632 if (MSSA) {
633 MSSAU->applyUpdates(Updates: {{DominatorTree::Delete, Preheader, L->getHeader()}},
634 DT&: *DT);
635 SmallSetVector<BasicBlock *, 8> DeadBlockSet(L->block_begin(),
636 L->block_end());
637 MSSAU->removeBlocks(DeadBlocks: DeadBlockSet);
638 if (VerifyMemorySSA)
639 MSSA->verifyMemorySSA();
640 }
641 }
642
643 // Use a map to unique and a vector to guarantee deterministic ordering.
644 llvm::SmallDenseSet<DebugVariable, 4> DeadDebugSet;
645 llvm::SmallVector<DbgVariableRecord *, 4> DeadDbgVariableRecords;
646
647 // Given LCSSA form is satisfied, we should not have users of instructions
648 // within the dead loop outside of the loop. However, LCSSA doesn't take
649 // unreachable uses into account. We handle them here.
650 // We could do it after drop all references (in this case all users in the
651 // loop will be already eliminated and we have less work to do but according
652 // to API doc of User::dropAllReferences only valid operation after dropping
653 // references, is deletion. So let's substitute all usages of
654 // instruction from the loop with poison value of corresponding type first.
655 for (auto *Block : L->blocks())
656 for (Instruction &I : *Block) {
657 auto *Poison = PoisonValue::get(T: I.getType());
658 for (Use &U : llvm::make_early_inc_range(Range: I.uses())) {
659 if (auto *Usr = dyn_cast<Instruction>(Val: U.getUser()))
660 if (L->contains(BB: Usr->getParent()))
661 continue;
662 // If we have a DT then we can check that uses outside a loop only in
663 // unreachable block.
664 if (DT)
665 assert(!DT->isReachableFromEntry(U) &&
666 "Unexpected user in reachable block");
667 U.set(Poison);
668 }
669
670 if (ExitBlock) {
671 // For one of each variable encountered, preserve a debug record (set
672 // to Poison) and transfer it to the loop exit. This terminates any
673 // variable locations that were set during the loop.
674 for (DbgVariableRecord &DVR :
675 llvm::make_early_inc_range(Range: filterDbgVars(R: I.getDbgRecordRange()))) {
676 DebugVariable Key(DVR.getVariable(), DVR.getExpression(),
677 DVR.getDebugLoc().get());
678 if (!DeadDebugSet.insert(V: Key).second)
679 continue;
680 // Unlinks the DVR from it's container, for later insertion.
681 DVR.removeFromParent();
682 DeadDbgVariableRecords.push_back(Elt: &DVR);
683 }
684 }
685 }
686
687 if (ExitBlock) {
688 // After the loop has been deleted all the values defined and modified
689 // inside the loop are going to be unavailable. Values computed in the
690 // loop will have been deleted, automatically causing their debug uses
691 // be be replaced with undef. Loop invariant values will still be available.
692 // Move dbg.values out the loop so that earlier location ranges are still
693 // terminated and loop invariant assignments are preserved.
694 DIBuilder DIB(*ExitBlock->getModule());
695 BasicBlock::iterator InsertDbgValueBefore =
696 ExitBlock->getFirstInsertionPt();
697 assert(InsertDbgValueBefore != ExitBlock->end() &&
698 "There should be a non-PHI instruction in exit block, else these "
699 "instructions will have no parent.");
700
701 // Due to the "head" bit in BasicBlock::iterator, we're going to insert
702 // each DbgVariableRecord right at the start of the block, wheras dbg.values
703 // would be repeatedly inserted before the first instruction. To replicate
704 // this behaviour, do it backwards.
705 for (DbgVariableRecord *DVR : llvm::reverse(C&: DeadDbgVariableRecords))
706 ExitBlock->insertDbgRecordBefore(DR: DVR, Here: InsertDbgValueBefore);
707 }
708
709 // Remove the block from the reference counting scheme, so that we can
710 // delete it freely later.
711 for (auto *Block : L->blocks())
712 Block->dropAllReferences();
713
714 if (MSSA && VerifyMemorySSA)
715 MSSA->verifyMemorySSA();
716
717 if (LI) {
718 SmallPtrSet<BasicBlock *, 8> Blocks(llvm::from_range, L->blocks());
719
720 // Erase the instructions and the blocks without having to worry
721 // about ordering because we already dropped the references.
722 // Remove blocks from loopinfo before erasing them, otherwise the loopinfo
723 // cannot find the loop using block numbers.
724 for (BasicBlock *BB : Blocks) {
725 LI->removeBlock(BB);
726 BB->eraseFromParent();
727 }
728
729 // The last step is to update LoopInfo now that we've eliminated this loop.
730 // Note: LoopInfo::erase remove the given loop and relink its subloops with
731 // its parent. While removeLoop/removeChildLoop remove the given loop but
732 // not relink its subloops, which is what we want.
733 if (Loop *ParentLoop = L->getParentLoop()) {
734 Loop::iterator I = find(Range&: *ParentLoop, Val: L);
735 assert(I != ParentLoop->end() && "Couldn't find loop");
736 ParentLoop->removeChildLoop(I);
737 } else {
738 Loop::iterator I = find(Range&: *LI, Val: L);
739 assert(I != LI->end() && "Couldn't find loop");
740 LI->removeLoop(I);
741 }
742 LI->destroy(L);
743 }
744}
745
746void llvm::breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
747 LoopInfo &LI, MemorySSA *MSSA) {
748 auto *Latch = L->getLoopLatch();
749 assert(Latch && "multiple latches not yet supported");
750 auto *Header = L->getHeader();
751 Loop *OutermostLoop = L->getOutermostLoop();
752
753 SE.forgetLoop(L);
754 SE.forgetBlockAndLoopDispositions();
755
756 std::unique_ptr<MemorySSAUpdater> MSSAU;
757 if (MSSA)
758 MSSAU = std::make_unique<MemorySSAUpdater>(args&: MSSA);
759
760 // Update the CFG and domtree. We chose to special case a couple of
761 // of common cases for code quality and test readability reasons.
762 [&]() -> void {
763 if (auto *BI = dyn_cast<UncondBrInst>(Val: Latch->getTerminator())) {
764 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Eager);
765 (void)changeToUnreachable(I: BI, /*PreserveLCSSA*/ true, DTU: &DTU, MSSAU: MSSAU.get());
766 return;
767 }
768 if (auto *BI = dyn_cast<CondBrInst>(Val: Latch->getTerminator())) {
769 // Conditional latch/exit - note that latch can be shared by inner
770 // and outer loop so the other target doesn't need to an exit
771 if (L->isLoopExiting(BB: Latch)) {
772 // TODO: Generalize ConstantFoldTerminator so that it can be used
773 // here without invalidating LCSSA or MemorySSA. (Tricky case for
774 // LCSSA: header is an exit block of a preceeding sibling loop w/o
775 // dedicated exits.)
776 const unsigned ExitIdx = L->contains(BB: BI->getSuccessor(i: 0)) ? 1 : 0;
777 BasicBlock *ExitBB = BI->getSuccessor(i: ExitIdx);
778
779 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Eager);
780 Header->removePredecessor(Pred: Latch, KeepOneInputPHIs: true);
781
782 IRBuilder<> Builder(BI);
783 auto *NewBI = Builder.CreateBr(Dest: ExitBB);
784 // Transfer the metadata to the new branch instruction (minus the
785 // loop info since this is no longer a loop)
786 NewBI->copyMetadata(SrcInst: *BI, WL: {LLVMContext::MD_dbg,
787 LLVMContext::MD_annotation});
788
789 BI->eraseFromParent();
790 DTU.applyUpdates(Updates: {{DominatorTree::Delete, Latch, Header}});
791 if (MSSA)
792 MSSAU->applyUpdates(Updates: {{DominatorTree::Delete, Latch, Header}}, DT);
793 return;
794 }
795 }
796
797 // General case. By splitting the backedge, and then explicitly making it
798 // unreachable we gracefully handle corner cases such as switch and invoke
799 // termiantors.
800 auto *BackedgeBB = SplitEdge(From: Latch, To: Header, DT: &DT, LI: &LI, MSSAU: MSSAU.get());
801
802 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Eager);
803 (void)changeToUnreachable(I: BackedgeBB->getTerminator(),
804 /*PreserveLCSSA*/ true, DTU: &DTU, MSSAU: MSSAU.get());
805 }();
806
807 // Erase (and destroy) this loop instance. Handles relinking sub-loops
808 // and blocks within the loop as needed.
809 LI.erase(L);
810
811 // If the loop we broke had a parent, then changeToUnreachable might have
812 // caused a block to be removed from the parent loop (see loop_nest_lcssa
813 // test case in zero-btc.ll for an example), thus changing the parent's
814 // exit blocks. If that happened, we need to rebuild LCSSA on the outermost
815 // loop which might have a had a block removed.
816 if (OutermostLoop != L)
817 formLCSSARecursively(L&: *OutermostLoop, DT, LI: &LI, SE: &SE);
818}
819
820
821/// Checks if \p L has an exiting latch branch. There may also be other
822/// exiting blocks. Returns branch instruction terminating the loop
823/// latch if above check is successful, nullptr otherwise.
824static CondBrInst *getExpectedExitLoopLatchBranch(Loop *L) {
825 BasicBlock *Latch = L->getLoopLatch();
826 if (!Latch)
827 return nullptr;
828
829 CondBrInst *LatchBR = dyn_cast<CondBrInst>(Val: Latch->getTerminator());
830 if (!LatchBR || !L->isLoopExiting(BB: Latch))
831 return nullptr;
832
833 assert((LatchBR->getSuccessor(0) == L->getHeader() ||
834 LatchBR->getSuccessor(1) == L->getHeader()) &&
835 "At least one edge out of the latch must go to the header");
836
837 return LatchBR;
838}
839
840struct DbgLoop {
841 const Loop *L;
842 explicit DbgLoop(const Loop *L) : L(L) {}
843};
844
845#ifndef NDEBUG
846static inline raw_ostream &operator<<(raw_ostream &OS, DbgLoop D) {
847 OS << "function ";
848 D.L->getHeader()->getParent()->printAsOperand(OS, /*PrintType=*/false);
849 return OS << " " << *D.L;
850}
851#endif // NDEBUG
852
853static std::optional<unsigned> estimateLoopTripCount(Loop *L) {
854 // Currently we take the estimate exit count only from the loop latch,
855 // ignoring other exiting blocks. This can overestimate the trip count
856 // if we exit through another exit, but can never underestimate it.
857 // TODO: incorporate information from other exits
858 CondBrInst *ExitingBranch = getExpectedExitLoopLatchBranch(L);
859 if (!ExitingBranch) {
860 LLVM_DEBUG(dbgs() << "estimateLoopTripCount: Failed to find exiting "
861 << "latch branch of required form in " << DbgLoop(L)
862 << "\n");
863 return std::nullopt;
864 }
865
866 // To estimate the number of times the loop body was executed, we want to
867 // know the number of times the backedge was taken, vs. the number of times
868 // we exited the loop.
869 uint64_t LoopWeight, ExitWeight;
870 if (!extractBranchWeights(I: *ExitingBranch, TrueVal&: LoopWeight, FalseVal&: ExitWeight)) {
871 LLVM_DEBUG(dbgs() << "estimateLoopTripCount: Failed to extract branch "
872 << "weights for " << DbgLoop(L) << "\n");
873 return std::nullopt;
874 }
875
876 if (L->contains(BB: ExitingBranch->getSuccessor(i: 1)))
877 std::swap(a&: LoopWeight, b&: ExitWeight);
878
879 if (!ExitWeight) {
880 // Don't have a way to return predicated infinite
881 LLVM_DEBUG(dbgs() << "estimateLoopTripCount: Failed because of zero exit "
882 << "probability for " << DbgLoop(L) << "\n");
883 return std::nullopt;
884 }
885
886 // Estimated exit count is a ratio of the loop weight by the weight of the
887 // edge exiting the loop, rounded to nearest.
888 uint64_t ExitCount = llvm::divideNearest(Numerator: LoopWeight, Denominator: ExitWeight);
889
890 // When ExitCount + 1 would wrap in unsigned, saturate at UINT_MAX.
891 if (ExitCount >= std::numeric_limits<unsigned>::max())
892 return std::numeric_limits<unsigned>::max();
893
894 // Estimated trip count is one plus estimated exit count.
895 uint64_t TC = ExitCount + 1;
896 LLVM_DEBUG(dbgs() << "estimateLoopTripCount: Estimated trip count of " << TC
897 << " for " << DbgLoop(L) << "\n");
898 return TC;
899}
900
901std::optional<unsigned>
902llvm::getLoopEstimatedTripCount(Loop *L,
903 unsigned *EstimatedLoopInvocationWeight) {
904 // If EstimatedLoopInvocationWeight, we do not support this loop if
905 // getExpectedExitLoopLatchBranch returns nullptr.
906 //
907 // FIXME: Also, this is a stop-gap solution for nested loops. It avoids
908 // mistaking LLVMLoopEstimatedTripCount metadata to be for an outer loop when
909 // it was created for an inner loop. The problem is that loop metadata is
910 // attached to the branch instruction in the loop latch block, but that can be
911 // shared by the loops. A solution is to attach loop metadata to loop headers
912 // instead, but that would be a large change to LLVM.
913 //
914 // Until that happens, we work around the problem as follows.
915 // getExpectedExitLoopLatchBranch (which also guards
916 // setLoopEstimatedTripCount) returns nullptr for a loop unless the loop has
917 // one latch and that latch has exactly two successors one of which is an exit
918 // from the loop. If the latch is shared by nested loops, then that condition
919 // might hold for the inner loop but cannot hold for the outer loop:
920 // - Because the latch is shared, it must have at least two successors: the
921 // inner loop header and the outer loop header, which is also an exit for
922 // the inner loop. That satisifies the condition for the inner loop.
923 // - To satsify the condition for the outer loop, the latch must have a third
924 // successor that is an exit for the outer loop. But that violates the
925 // condition for both loops.
926 CondBrInst *ExitingBranch = getExpectedExitLoopLatchBranch(L);
927 if (!ExitingBranch)
928 return std::nullopt;
929
930 // If requested, either compute *EstimatedLoopInvocationWeight or return
931 // nullopt if cannot.
932 //
933 // TODO: Eventually, once all passes have migrated away from setting branch
934 // weights to indicate estimated trip counts, this function will drop the
935 // EstimatedLoopInvocationWeight parameter.
936 if (EstimatedLoopInvocationWeight) {
937 uint64_t LoopWeight = 0, ExitWeight = 0; // Inits expected to be unused.
938 if (!extractBranchWeights(I: *ExitingBranch, TrueVal&: LoopWeight, FalseVal&: ExitWeight))
939 return std::nullopt;
940 if (L->contains(BB: ExitingBranch->getSuccessor(i: 1)))
941 std::swap(a&: LoopWeight, b&: ExitWeight);
942 if (!ExitWeight)
943 return std::nullopt;
944 *EstimatedLoopInvocationWeight = ExitWeight;
945 }
946
947 // Return the estimated trip count from metadata unless the metadata is
948 // missing or has no value.
949 //
950 // Some passes set llvm.loop.estimated_trip_count to 0. For example, after
951 // peeling 10 or more iterations from a loop with an estimated trip count of
952 // 10, llvm.loop.estimated_trip_count becomes 0 on the remaining loop. It
953 // indicates that, each time execution reaches the peeled iterations,
954 // execution is estimated to exit them without reaching the remaining loop's
955 // header.
956 if (std::optional<unsigned> TC =
957 getOptionalIntLoopAttribute(TheLoop: L, Name: LLVMLoopEstimatedTripCount)) {
958 LLVM_DEBUG(dbgs() << "getLoopEstimatedTripCount: "
959 << LLVMLoopEstimatedTripCount << " metadata has trip "
960 << "count of " << *TC << " for " << DbgLoop(L) << "\n");
961 return TC;
962 }
963
964 // Estimate the trip count from latch branch weights.
965 return estimateLoopTripCount(L);
966}
967
968bool llvm::setLoopEstimatedTripCount(
969 Loop *L, unsigned EstimatedTripCount,
970 std::optional<unsigned> EstimatedloopInvocationWeight) {
971 // If EstimatedLoopInvocationWeight, we do not support this loop if
972 // getExpectedExitLoopLatchBranch returns nullptr.
973 //
974 // FIXME: See comments in getLoopEstimatedTripCount for why this is required
975 // here regardless of EstimatedLoopInvocationWeight.
976 CondBrInst *LatchBranch = getExpectedExitLoopLatchBranch(L);
977 if (!LatchBranch)
978 return false;
979
980 // Set the metadata.
981 addStringMetadataToLoop(TheLoop: L, StringMD: LLVMLoopEstimatedTripCount, V: EstimatedTripCount);
982
983 // At the moment, we currently support changing the estimated trip count in
984 // the latch branch's branch weights only. We could extend this API to
985 // manipulate estimated trip counts for any exit.
986 //
987 // TODO: Eventually, once all passes have migrated away from setting branch
988 // weights to indicate estimated trip counts, we will not set branch weights
989 // here at all.
990 if (!EstimatedloopInvocationWeight)
991 return true;
992
993 // Calculate taken and exit weights.
994 unsigned LatchExitWeight = 1;
995 unsigned BackedgeTakenWeight = 0;
996
997 if (EstimatedTripCount != 0) {
998 LatchExitWeight = *EstimatedloopInvocationWeight;
999 BackedgeTakenWeight = (EstimatedTripCount - 1) * LatchExitWeight;
1000 }
1001
1002 // Make a swap if back edge is taken when condition is "false".
1003 if (LatchBranch->getSuccessor(i: 0) != L->getHeader())
1004 std::swap(a&: BackedgeTakenWeight, b&: LatchExitWeight);
1005
1006 // Set/Update profile metadata.
1007 setBranchWeights(I&: *LatchBranch, Weights: {BackedgeTakenWeight, LatchExitWeight},
1008 /*IsExpected=*/false);
1009
1010 return true;
1011}
1012
1013BranchProbability llvm::getLoopProbability(Loop *L) {
1014 CondBrInst *LatchBranch = getExpectedExitLoopLatchBranch(L);
1015 if (!LatchBranch)
1016 return BranchProbability::getUnknown();
1017 bool FirstTargetIsLoop = LatchBranch->getSuccessor(i: 0) == L->getHeader();
1018 return getBranchProbability(B: LatchBranch, ForFirstTarget: FirstTargetIsLoop);
1019}
1020
1021bool llvm::setLoopProbability(Loop *L, BranchProbability P) {
1022 CondBrInst *LatchBranch = getExpectedExitLoopLatchBranch(L);
1023 if (!LatchBranch)
1024 return false;
1025 bool FirstTargetIsLoop = LatchBranch->getSuccessor(i: 0) == L->getHeader();
1026 setBranchProbability(B: LatchBranch, P, ForFirstTarget: FirstTargetIsLoop);
1027 return true;
1028}
1029
1030BranchProbability llvm::getBranchProbability(CondBrInst *B,
1031 bool ForFirstTarget) {
1032 uint64_t Weight0, Weight1;
1033 if (!extractBranchWeights(I: *B, TrueVal&: Weight0, FalseVal&: Weight1))
1034 return BranchProbability::getUnknown();
1035 uint64_t Denominator = Weight0 + Weight1;
1036 if (Denominator == 0)
1037 return BranchProbability::getUnknown();
1038 if (!ForFirstTarget)
1039 std::swap(a&: Weight0, b&: Weight1);
1040 return BranchProbability::getBranchProbability(Numerator: Weight0, Denominator);
1041}
1042
1043BranchProbability llvm::getBranchProbability(BasicBlock *Src, BasicBlock *Dst) {
1044 assert(Src != Dst && "Passed in same source as destination");
1045
1046 Instruction *TI = Src->getTerminator();
1047 if (!TI || TI->getNumSuccessors() == 0)
1048 return BranchProbability::getZero();
1049
1050 SmallVector<uint32_t, 4> Weights;
1051
1052 if (!extractBranchWeights(I: *TI, Weights)) {
1053 // No metadata
1054 return BranchProbability::getUnknown();
1055 }
1056 assert(TI->getNumSuccessors() == Weights.size() &&
1057 "Missing weights in branch_weights");
1058
1059 uint64_t Total = 0;
1060 uint32_t Numerator = 0;
1061 for (auto [i, Weight] : llvm::enumerate(First&: Weights)) {
1062 if (TI->getSuccessor(Idx: i) == Dst)
1063 Numerator += Weight;
1064 Total += Weight;
1065 }
1066
1067 // Total of edges might be 0 if the metadata is incorrect/set by hand
1068 // or missing. In such case return here to avoid division by 0 later on.
1069 // There might also be a case where the value of Total cannot fit into
1070 // uint32_t, in such case, just bail out.
1071 if (Total == 0 || Total > std::numeric_limits<uint32_t>::max())
1072 return BranchProbability::getUnknown();
1073
1074 return BranchProbability(Numerator, Total);
1075}
1076
1077void llvm::setBranchProbability(CondBrInst *B, BranchProbability P,
1078 bool ForFirstTarget) {
1079 BranchProbability Prob0 = P;
1080 BranchProbability Prob1 = P.getCompl();
1081 if (!ForFirstTarget)
1082 std::swap(a&: Prob0, b&: Prob1);
1083 setBranchWeights(I&: *B, Weights: {Prob0.getNumerator(), Prob1.getNumerator()},
1084 /*IsExpected=*/false);
1085}
1086
1087bool llvm::hasIterationCountInvariantInParent(Loop *InnerLoop,
1088 ScalarEvolution &SE) {
1089 Loop *OuterL = InnerLoop->getParentLoop();
1090 if (!OuterL)
1091 return true;
1092
1093 // Get the backedge taken count for the inner loop
1094 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1095 const SCEV *InnerLoopBECountSC = SE.getExitCount(L: InnerLoop, ExitingBlock: InnerLoopLatch);
1096 if (isa<SCEVCouldNotCompute>(Val: InnerLoopBECountSC) ||
1097 !InnerLoopBECountSC->getType()->isIntegerTy())
1098 return false;
1099
1100 // Get whether count is invariant to the outer loop
1101 ScalarEvolution::LoopDisposition LD =
1102 SE.getLoopDisposition(S: InnerLoopBECountSC, L: OuterL);
1103 if (LD != ScalarEvolution::LoopInvariant)
1104 return false;
1105
1106 return true;
1107}
1108
1109constexpr Intrinsic::ID llvm::getReductionIntrinsicID(RecurKind RK) {
1110 switch (RK) {
1111 default:
1112 llvm_unreachable("Unexpected recurrence kind");
1113 case RecurKind::AddChainWithSubs:
1114 case RecurKind::Sub:
1115 case RecurKind::Add:
1116 return Intrinsic::vector_reduce_add;
1117 case RecurKind::Mul:
1118 return Intrinsic::vector_reduce_mul;
1119 case RecurKind::And:
1120 return Intrinsic::vector_reduce_and;
1121 case RecurKind::Or:
1122 return Intrinsic::vector_reduce_or;
1123 case RecurKind::Xor:
1124 return Intrinsic::vector_reduce_xor;
1125 case RecurKind::FMulAdd:
1126 case RecurKind::FAddChainWithSubs:
1127 case RecurKind::FSub:
1128 case RecurKind::FAdd:
1129 return Intrinsic::vector_reduce_fadd;
1130 case RecurKind::FMul:
1131 return Intrinsic::vector_reduce_fmul;
1132 case RecurKind::SMax:
1133 return Intrinsic::vector_reduce_smax;
1134 case RecurKind::SMin:
1135 return Intrinsic::vector_reduce_smin;
1136 case RecurKind::UMax:
1137 return Intrinsic::vector_reduce_umax;
1138 case RecurKind::UMin:
1139 return Intrinsic::vector_reduce_umin;
1140 case RecurKind::FMax:
1141 case RecurKind::FMaxNum:
1142 return Intrinsic::vector_reduce_fmax;
1143 case RecurKind::FMin:
1144 case RecurKind::FMinNum:
1145 return Intrinsic::vector_reduce_fmin;
1146 case RecurKind::FMaximum:
1147 return Intrinsic::vector_reduce_fmaximum;
1148 case RecurKind::FMinimum:
1149 return Intrinsic::vector_reduce_fminimum;
1150 case RecurKind::FMaximumNum:
1151 return Intrinsic::vector_reduce_fmax;
1152 case RecurKind::FMinimumNum:
1153 return Intrinsic::vector_reduce_fmin;
1154 }
1155}
1156
1157Intrinsic::ID llvm::getMinMaxReductionIntrinsicID(Intrinsic::ID IID) {
1158 switch (IID) {
1159 default:
1160 llvm_unreachable("Unexpected intrinsic id");
1161 case Intrinsic::umin:
1162 return Intrinsic::vector_reduce_umin;
1163 case Intrinsic::umax:
1164 return Intrinsic::vector_reduce_umax;
1165 case Intrinsic::smin:
1166 return Intrinsic::vector_reduce_smin;
1167 case Intrinsic::smax:
1168 return Intrinsic::vector_reduce_smax;
1169 }
1170}
1171
1172// This is the inverse to getReductionForBinop
1173unsigned llvm::getArithmeticReductionInstruction(Intrinsic::ID RdxID) {
1174 switch (RdxID) {
1175 case Intrinsic::vector_reduce_fadd:
1176 return Instruction::FAdd;
1177 case Intrinsic::vector_reduce_fmul:
1178 return Instruction::FMul;
1179 case Intrinsic::vector_reduce_add:
1180 return Instruction::Add;
1181 case Intrinsic::vector_reduce_mul:
1182 return Instruction::Mul;
1183 case Intrinsic::vector_reduce_and:
1184 return Instruction::And;
1185 case Intrinsic::vector_reduce_or:
1186 return Instruction::Or;
1187 case Intrinsic::vector_reduce_xor:
1188 return Instruction::Xor;
1189 case Intrinsic::vector_reduce_smax:
1190 case Intrinsic::vector_reduce_smin:
1191 case Intrinsic::vector_reduce_umax:
1192 case Intrinsic::vector_reduce_umin:
1193 return Instruction::ICmp;
1194 case Intrinsic::vector_reduce_fmax:
1195 case Intrinsic::vector_reduce_fmin:
1196 case Intrinsic::vector_reduce_fmaximum:
1197 case Intrinsic::vector_reduce_fminimum:
1198 case Intrinsic::vector_reduce_fmaximumnum:
1199 case Intrinsic::vector_reduce_fminimumnum:
1200 return Instruction::FCmp;
1201 default:
1202 llvm_unreachable("Unexpected ID");
1203 }
1204}
1205
1206// This is the inverse to getArithmeticReductionInstruction
1207Intrinsic::ID llvm::getReductionForBinop(Instruction::BinaryOps Opc) {
1208 switch (Opc) {
1209 default:
1210 break;
1211 case Instruction::Add:
1212 return Intrinsic::vector_reduce_add;
1213 case Instruction::Mul:
1214 return Intrinsic::vector_reduce_mul;
1215 case Instruction::And:
1216 return Intrinsic::vector_reduce_and;
1217 case Instruction::Or:
1218 return Intrinsic::vector_reduce_or;
1219 case Instruction::Xor:
1220 return Intrinsic::vector_reduce_xor;
1221 case Instruction::FAdd:
1222 return Intrinsic::vector_reduce_fadd;
1223 case Instruction::FMul:
1224 return Intrinsic::vector_reduce_fmul;
1225 }
1226 return Intrinsic::not_intrinsic;
1227}
1228
1229Intrinsic::ID llvm::getMinMaxReductionIntrinsicOp(Intrinsic::ID RdxID) {
1230 switch (RdxID) {
1231 default:
1232 llvm_unreachable("Unknown min/max recurrence kind");
1233 case Intrinsic::vector_reduce_umin:
1234 return Intrinsic::umin;
1235 case Intrinsic::vector_reduce_umax:
1236 return Intrinsic::umax;
1237 case Intrinsic::vector_reduce_smin:
1238 return Intrinsic::smin;
1239 case Intrinsic::vector_reduce_smax:
1240 return Intrinsic::smax;
1241 case Intrinsic::vector_reduce_fmin:
1242 return Intrinsic::minnum;
1243 case Intrinsic::vector_reduce_fmax:
1244 return Intrinsic::maxnum;
1245 case Intrinsic::vector_reduce_fminimum:
1246 return Intrinsic::minimum;
1247 case Intrinsic::vector_reduce_fmaximum:
1248 return Intrinsic::maximum;
1249 case Intrinsic::vector_reduce_fminimumnum:
1250 return Intrinsic::minimumnum;
1251 case Intrinsic::vector_reduce_fmaximumnum:
1252 return Intrinsic::maximumnum;
1253 }
1254}
1255
1256Intrinsic::ID llvm::getMinMaxReductionIntrinsicOp(RecurKind RK) {
1257 switch (RK) {
1258 default:
1259 llvm_unreachable("Unknown min/max recurrence kind");
1260 case RecurKind::UMin:
1261 return Intrinsic::umin;
1262 case RecurKind::UMax:
1263 return Intrinsic::umax;
1264 case RecurKind::SMin:
1265 return Intrinsic::smin;
1266 case RecurKind::SMax:
1267 return Intrinsic::smax;
1268 case RecurKind::FMin:
1269 case RecurKind::FMinNum:
1270 return Intrinsic::minnum;
1271 case RecurKind::FMax:
1272 case RecurKind::FMaxNum:
1273 return Intrinsic::maxnum;
1274 case RecurKind::FMinimum:
1275 return Intrinsic::minimum;
1276 case RecurKind::FMaximum:
1277 return Intrinsic::maximum;
1278 case RecurKind::FMinimumNum:
1279 return Intrinsic::minimumnum;
1280 case RecurKind::FMaximumNum:
1281 return Intrinsic::maximumnum;
1282 }
1283}
1284
1285RecurKind llvm::getMinMaxReductionRecurKind(Intrinsic::ID RdxID) {
1286 switch (RdxID) {
1287 case Intrinsic::vector_reduce_smax:
1288 return RecurKind::SMax;
1289 case Intrinsic::vector_reduce_smin:
1290 return RecurKind::SMin;
1291 case Intrinsic::vector_reduce_umax:
1292 return RecurKind::UMax;
1293 case Intrinsic::vector_reduce_umin:
1294 return RecurKind::UMin;
1295 case Intrinsic::vector_reduce_fmax:
1296 return RecurKind::FMax;
1297 case Intrinsic::vector_reduce_fmin:
1298 return RecurKind::FMin;
1299 case Intrinsic::vector_reduce_fmaximum:
1300 return RecurKind::FMaximum;
1301 case Intrinsic::vector_reduce_fminimum:
1302 return RecurKind::FMinimum;
1303 case Intrinsic::vector_reduce_fmaximumnum:
1304 return RecurKind::FMaximumNum;
1305 case Intrinsic::vector_reduce_fminimumnum:
1306 return RecurKind::FMinimumNum;
1307 default:
1308 return RecurKind::None;
1309 }
1310}
1311
1312CmpInst::Predicate llvm::getMinMaxReductionPredicate(RecurKind RK) {
1313 switch (RK) {
1314 default:
1315 llvm_unreachable("Unknown min/max recurrence kind");
1316 case RecurKind::UMin:
1317 return CmpInst::ICMP_ULT;
1318 case RecurKind::UMax:
1319 return CmpInst::ICMP_UGT;
1320 case RecurKind::SMin:
1321 return CmpInst::ICMP_SLT;
1322 case RecurKind::SMax:
1323 return CmpInst::ICMP_SGT;
1324 case RecurKind::FMin:
1325 return CmpInst::FCMP_OLT;
1326 case RecurKind::FMax:
1327 return CmpInst::FCMP_OGT;
1328 // We do not add FMinimum/FMaximum recurrence kind here since there is no
1329 // equivalent predicate which compares signed zeroes according to the
1330 // semantics of the intrinsics (llvm.minimum/maximum).
1331 }
1332}
1333
1334Value *llvm::createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
1335 Value *Right) {
1336 Type *Ty = Left->getType();
1337 if (Ty->isIntOrIntVectorTy() ||
1338 (RK == RecurKind::FMinNum || RK == RecurKind::FMaxNum ||
1339 RK == RecurKind::FMinimum || RK == RecurKind::FMaximum ||
1340 RK == RecurKind::FMinimumNum || RK == RecurKind::FMaximumNum)) {
1341 Intrinsic::ID Id = getMinMaxReductionIntrinsicOp(RK);
1342 return Builder.CreateIntrinsic(RetTy: Ty, ID: Id, Args: {Left, Right}, FMFSource: nullptr,
1343 Name: "rdx.minmax");
1344 }
1345 CmpInst::Predicate Pred = getMinMaxReductionPredicate(RK);
1346 Value *Cmp = Builder.CreateCmp(Pred, LHS: Left, RHS: Right, Name: "rdx.minmax.cmp");
1347 Value *Select = Builder.CreateSelect(C: Cmp, True: Left, False: Right, Name: "rdx.minmax.select");
1348 // This select is synthesized fresh, not lowered from an existing branch, so
1349 // it carries no real profile. Mark its weights as explicitly unknown.
1350 if (auto *SI = dyn_cast<SelectInst>(Val: Select))
1351 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *SI, DEBUG_TYPE);
1352 return Select;
1353}
1354
1355// Helper to generate an ordered reduction.
1356Value *llvm::getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,
1357 unsigned Op, RecurKind RdxKind) {
1358 unsigned VF = cast<FixedVectorType>(Val: Src->getType())->getNumElements();
1359
1360 // Extract and apply reduction ops in ascending order:
1361 // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
1362 Value *Result = Acc;
1363 for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
1364 Value *Ext =
1365 Builder.CreateExtractElement(Vec: Src, Idx: Builder.getInt32(C: ExtractIdx));
1366
1367 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1368 Result = Builder.CreateBinOp(Opc: (Instruction::BinaryOps)Op, LHS: Result, RHS: Ext,
1369 Name: "bin.rdx");
1370 } else {
1371 assert(RecurrenceDescriptor::isMinMaxRecurrenceKind(RdxKind) &&
1372 "Invalid min/max");
1373 Result = createMinMaxOp(Builder, RK: RdxKind, Left: Result, Right: Ext);
1374 }
1375 }
1376
1377 return Result;
1378}
1379
1380Value *llvm::expandReductionViaLoop(IRBuilderBase &Builder, Value *Vec,
1381 unsigned RdxOpcode, Value *Acc,
1382 DominatorTree *DT, LoopInfo *LI) {
1383 auto *VTy = cast<VectorType>(Val: Vec->getType());
1384 Type *EltTy = VTy->getElementType();
1385 Function *F = Builder.GetInsertBlock()->getParent();
1386
1387 const DataLayout &DL = F->getDataLayout();
1388 Type *IdxTy = DL.getIndexType(C&: EltTy->getContext(), AddressSpace: 0);
1389 unsigned MinElts = VTy->getElementCount().getKnownMinValue();
1390 Value *NumElts = Builder.CreateVScale(Ty: IdxTy);
1391 NumElts = Builder.CreateMul(LHS: NumElts, RHS: ConstantInt::get(Ty: IdxTy, V: MinElts));
1392
1393 BasicBlock *EntryBB = Builder.GetInsertBlock();
1394 BasicBlock *LoopBB = BasicBlock::Create(Context&: F->getContext(), Name: "rdx.loop", Parent: F);
1395 BasicBlock *ExitBB = SplitBlock(Old: EntryBB, SplitPt: Builder.GetInsertPoint(), DT, LI,
1396 MSSAU: nullptr, BBName: "rdx.exit");
1397
1398 EntryBB->getTerminator()->eraseFromParent();
1399 Builder.SetInsertPoint(EntryBB);
1400 Builder.CreateBr(Dest: LoopBB);
1401
1402 Builder.SetInsertPoint(LoopBB);
1403 PHINode *IV = Builder.CreatePHI(Ty: IdxTy, NumReservedValues: 2, Name: "rdx.iv");
1404 PHINode *AccPhi = Builder.CreatePHI(Ty: EltTy, NumReservedValues: 2, Name: "rdx.acc");
1405 IV->addIncoming(V: ConstantInt::get(Ty: IdxTy, V: 0), BB: EntryBB);
1406 AccPhi->addIncoming(V: Acc, BB: EntryBB);
1407
1408 Value *Elt = Builder.CreateExtractElement(Vec, Idx: IV);
1409 Value *Res = Builder.CreateBinOp(Opc: (Instruction::BinaryOps)RdxOpcode, LHS: AccPhi,
1410 RHS: Elt, Name: "rdx.op");
1411
1412 Value *NextIV =
1413 Builder.CreateNUWAdd(LHS: IV, RHS: ConstantInt::get(Ty: IdxTy, V: 1), Name: "rdx.next");
1414 IV->addIncoming(V: NextIV, BB: LoopBB);
1415 AccPhi->addIncoming(V: Res, BB: LoopBB);
1416
1417 Value *Done = Builder.CreateICmpEQ(LHS: NextIV, RHS: NumElts, Name: "rdx.done");
1418 Builder.CreateCondBr(Cond: Done, True: ExitBB, False: LoopBB);
1419
1420 // SplitBlock above updated DT/LI for EntryBB -> ExitBB. Now update
1421 // for replacing that edge with EntryBB -> LoopBB -> {ExitBB, LoopBB}.
1422 if (DT)
1423 DT->applyUpdates(Updates: {{DominatorTree::Insert, EntryBB, LoopBB},
1424 {DominatorTree::Insert, LoopBB, LoopBB},
1425 {DominatorTree::Insert, LoopBB, ExitBB},
1426 {DominatorTree::Delete, EntryBB, ExitBB}});
1427
1428 if (LI) {
1429 Loop *NewLoop = LI->AllocateLoop();
1430 if (Loop *ParentLoop = LI->getLoopFor(BB: EntryBB))
1431 ParentLoop->addChildLoop(NewChild: NewLoop);
1432 else
1433 LI->addTopLevelLoop(New: NewLoop);
1434 NewLoop->addBasicBlockToLoop(NewBB: LoopBB, LI&: *LI);
1435 }
1436
1437 Builder.SetInsertPoint(TheBB: ExitBB, IP: ExitBB->begin());
1438 return Res;
1439}
1440
1441// Helper to generate a log2 shuffle reduction.
1442Value *llvm::getShuffleReduction(IRBuilderBase &Builder, Value *Src,
1443 unsigned Op,
1444 TargetTransformInfo::ReductionShuffle RS,
1445 RecurKind RdxKind) {
1446 unsigned VF = cast<FixedVectorType>(Val: Src->getType())->getNumElements();
1447 // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
1448 // and vector ops, reducing the set of values being computed by half each
1449 // round.
1450 assert(isPowerOf2_32(VF) &&
1451 "Reduction emission only supported for pow2 vectors!");
1452 // Note: fast-math-flags flags are controlled by the builder configuration
1453 // and are assumed to apply to all generated arithmetic instructions. Other
1454 // poison generating flags (nsw/nuw/inbounds/inrange/exact) are not part
1455 // of the builder configuration, and since they're not passed explicitly,
1456 // will never be relevant here. Note that it would be generally unsound to
1457 // propagate these from an intrinsic call to the expansion anyways as we/
1458 // change the order of operations.
1459 auto BuildShuffledOp = [&Builder, &Op,
1460 &RdxKind](SmallVectorImpl<int> &ShuffleMask,
1461 Value *&TmpVec) -> void {
1462 Value *Shuf = Builder.CreateShuffleVector(V: TmpVec, Mask: ShuffleMask, Name: "rdx.shuf");
1463 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1464 TmpVec = Builder.CreateBinOp(Opc: (Instruction::BinaryOps)Op, LHS: TmpVec, RHS: Shuf,
1465 Name: "bin.rdx");
1466 } else {
1467 assert(RecurrenceDescriptor::isMinMaxRecurrenceKind(RdxKind) &&
1468 "Invalid min/max");
1469 TmpVec = createMinMaxOp(Builder, RK: RdxKind, Left: TmpVec, Right: Shuf);
1470 }
1471 };
1472
1473 Value *TmpVec = Src;
1474 if (TargetTransformInfo::ReductionShuffle::Pairwise == RS) {
1475 SmallVector<int, 32> ShuffleMask(VF);
1476 for (unsigned stride = 1; stride < VF; stride <<= 1) {
1477 // Initialise the mask with undef.
1478 llvm::fill(Range&: ShuffleMask, Value: -1);
1479 for (unsigned j = 0; j < VF; j += stride << 1) {
1480 ShuffleMask[j] = j + stride;
1481 }
1482 BuildShuffledOp(ShuffleMask, TmpVec);
1483 }
1484 } else {
1485 SmallVector<int, 32> ShuffleMask(VF);
1486 for (unsigned i = VF; i != 1; i >>= 1) {
1487 // Move the upper half of the vector to the lower half.
1488 for (unsigned j = 0; j != i / 2; ++j)
1489 ShuffleMask[j] = i / 2 + j;
1490
1491 // Fill the rest of the mask with undef.
1492 std::fill(first: &ShuffleMask[i / 2], last: ShuffleMask.end(), value: -1);
1493 BuildShuffledOp(ShuffleMask, TmpVec);
1494 }
1495 }
1496 // The result is in the first element of the vector.
1497 return Builder.CreateExtractElement(Vec: TmpVec, Idx: Builder.getInt32(C: 0));
1498}
1499
1500Value *llvm::createAnyOfReduction(IRBuilderBase &Builder, Value *Src,
1501 Value *InitVal, PHINode *OrigPhi) {
1502 Value *NewVal = nullptr;
1503
1504 // First use the original phi to determine the new value we're trying to
1505 // select from in the loop.
1506 SelectInst *SI = nullptr;
1507 for (auto *U : OrigPhi->users()) {
1508 if ((SI = dyn_cast<SelectInst>(Val: U)))
1509 break;
1510 }
1511 assert(SI && "One user of the original phi should be a select");
1512
1513 if (SI->getTrueValue() == OrigPhi)
1514 NewVal = SI->getFalseValue();
1515 else {
1516 assert(SI->getFalseValue() == OrigPhi &&
1517 "At least one input to the select should be the original Phi");
1518 NewVal = SI->getTrueValue();
1519 }
1520
1521 // If any predicate is true it means that we want to select the new value.
1522 Value *AnyOf =
1523 Src->getType()->isVectorTy() ? Builder.CreateOrReduce(Src) : Src;
1524 // The compares in the loop may yield poison, which propagates through the
1525 // bitwise ORs. Freeze it here before the condition is used.
1526 AnyOf = Builder.CreateFreeze(V: AnyOf);
1527 return Builder.CreateSelect(C: AnyOf, True: NewVal, False: InitVal, Name: "rdx.select");
1528}
1529
1530Value *llvm::getReductionIdentity(Intrinsic::ID RdxID, Type *Ty,
1531 FastMathFlags Flags) {
1532 bool Negative = false;
1533 switch (RdxID) {
1534 default:
1535 llvm_unreachable("Expecting a reduction intrinsic");
1536 case Intrinsic::vector_reduce_add:
1537 case Intrinsic::vector_reduce_mul:
1538 case Intrinsic::vector_reduce_or:
1539 case Intrinsic::vector_reduce_xor:
1540 case Intrinsic::vector_reduce_and:
1541 case Intrinsic::vector_reduce_fadd:
1542 case Intrinsic::vector_reduce_fmul: {
1543 unsigned Opc = getArithmeticReductionInstruction(RdxID);
1544 return ConstantExpr::getBinOpIdentity(Opcode: Opc, Ty, AllowRHSConstant: false,
1545 NSZ: Flags.noSignedZeros());
1546 }
1547 case Intrinsic::vector_reduce_umax:
1548 case Intrinsic::vector_reduce_umin:
1549 case Intrinsic::vector_reduce_smin:
1550 case Intrinsic::vector_reduce_smax: {
1551 Intrinsic::ID ScalarID = getMinMaxReductionIntrinsicOp(RdxID);
1552 return ConstantExpr::getIntrinsicIdentity(ScalarID, Ty);
1553 }
1554 case Intrinsic::vector_reduce_fmax:
1555 case Intrinsic::vector_reduce_fmaximum:
1556 Negative = true;
1557 [[fallthrough]];
1558 case Intrinsic::vector_reduce_fmin:
1559 case Intrinsic::vector_reduce_fminimum: {
1560 bool PropagatesNaN = RdxID == Intrinsic::vector_reduce_fminimum ||
1561 RdxID == Intrinsic::vector_reduce_fmaximum;
1562 const fltSemantics &Semantics = Ty->getScalarType()->getFltSemantics();
1563 return (!Flags.noNaNs() && !PropagatesNaN)
1564 ? ConstantFP::getQNaN(Ty, Negative)
1565 : !Flags.noInfs()
1566 ? ConstantFP::getInfinity(Ty, Negative)
1567 : ConstantFP::get(Ty, V: APFloat::getLargest(Sem: Semantics, Negative));
1568 }
1569 }
1570}
1571
1572Value *llvm::getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF) {
1573 assert((!(K == RecurKind::FMin || K == RecurKind::FMax) ||
1574 (FMF.noNaNs() && FMF.noSignedZeros())) &&
1575 "nnan, nsz is expected to be set for FP min/max reduction.");
1576 Intrinsic::ID RdxID = getReductionIntrinsicID(RK: K);
1577 return getReductionIdentity(RdxID, Ty: Tp, Flags: FMF);
1578}
1579
1580Value *llvm::createSimpleReduction(IRBuilderBase &Builder, Value *Src,
1581 RecurKind RdxKind) {
1582 auto *SrcVecEltTy = cast<VectorType>(Val: Src->getType())->getElementType();
1583 auto getIdentity = [&]() {
1584 return getRecurrenceIdentity(K: RdxKind, Tp: SrcVecEltTy,
1585 FMF: Builder.getFastMathFlags());
1586 };
1587 switch (RdxKind) {
1588 case RecurKind::AddChainWithSubs:
1589 case RecurKind::Sub:
1590 case RecurKind::Add:
1591 case RecurKind::Mul:
1592 case RecurKind::And:
1593 case RecurKind::Or:
1594 case RecurKind::Xor:
1595 case RecurKind::SMax:
1596 case RecurKind::SMin:
1597 case RecurKind::UMax:
1598 case RecurKind::UMin:
1599 case RecurKind::FMax:
1600 case RecurKind::FMin:
1601 case RecurKind::FMinNum:
1602 case RecurKind::FMaxNum:
1603 case RecurKind::FMinimum:
1604 case RecurKind::FMaximum:
1605 case RecurKind::FMinimumNum:
1606 case RecurKind::FMaximumNum:
1607 return Builder.CreateUnaryIntrinsic(ID: getReductionIntrinsicID(RK: RdxKind), Op: Src);
1608 case RecurKind::FMulAdd:
1609 case RecurKind::FAddChainWithSubs:
1610 case RecurKind::FSub:
1611 case RecurKind::FAdd:
1612 return Builder.CreateFAddReduce(Acc: getIdentity(), Src);
1613 case RecurKind::FMul:
1614 return Builder.CreateFMulReduce(Acc: getIdentity(), Src);
1615 default:
1616 llvm_unreachable("Unhandled opcode");
1617 }
1618}
1619
1620static Intrinsic::ID getVPReductionIntrinsicID(Intrinsic::ID Id) {
1621 switch (Id) {
1622 default:
1623 llvm_unreachable("Unexpected reduction intrinsic");
1624 case Intrinsic::vector_reduce_add:
1625 return Intrinsic::vp_reduce_add;
1626 case Intrinsic::vector_reduce_mul:
1627 return Intrinsic::vp_reduce_mul;
1628 case Intrinsic::vector_reduce_and:
1629 return Intrinsic::vp_reduce_and;
1630 case Intrinsic::vector_reduce_or:
1631 return Intrinsic::vp_reduce_or;
1632 case Intrinsic::vector_reduce_xor:
1633 return Intrinsic::vp_reduce_xor;
1634 case Intrinsic::vector_reduce_smax:
1635 return Intrinsic::vp_reduce_smax;
1636 case Intrinsic::vector_reduce_smin:
1637 return Intrinsic::vp_reduce_smin;
1638 case Intrinsic::vector_reduce_umax:
1639 return Intrinsic::vp_reduce_umax;
1640 case Intrinsic::vector_reduce_umin:
1641 return Intrinsic::vp_reduce_umin;
1642 case Intrinsic::vector_reduce_fmax:
1643 return Intrinsic::vp_reduce_fmax;
1644 case Intrinsic::vector_reduce_fmin:
1645 return Intrinsic::vp_reduce_fmin;
1646 case Intrinsic::vector_reduce_fmaximum:
1647 return Intrinsic::vp_reduce_fmaximum;
1648 case Intrinsic::vector_reduce_fminimum:
1649 return Intrinsic::vp_reduce_fminimum;
1650 case Intrinsic::vector_reduce_fadd:
1651 return Intrinsic::vp_reduce_fadd;
1652 case Intrinsic::vector_reduce_fmul:
1653 return Intrinsic::vp_reduce_fmul;
1654 }
1655}
1656
1657Value *llvm::createSimpleReduction(IRBuilderBase &Builder, Value *Src,
1658 RecurKind Kind, Value *Mask, Value *EVL) {
1659 assert(!RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind) &&
1660 !RecurrenceDescriptor::isFindRecurrenceKind(Kind) &&
1661 "AnyOf and FindIV reductions are not supported.");
1662 Intrinsic::ID Id = getReductionIntrinsicID(RK: Kind);
1663 Intrinsic::ID VPID = getVPReductionIntrinsicID(Id);
1664 auto *EltTy = cast<VectorType>(Val: Src->getType())->getElementType();
1665 Value *Iden = getRecurrenceIdentity(K: Kind, Tp: EltTy, FMF: Builder.getFastMathFlags());
1666 Value *Ops[] = {Iden, Src, Mask, EVL};
1667 return Builder.CreateIntrinsic(RetTy: EltTy, ID: VPID, Args: Ops);
1668}
1669
1670Value *llvm::createOrderedReduction(IRBuilderBase &B, RecurKind Kind,
1671 Value *Src, Value *Start) {
1672 assert((Kind == RecurKind::FAdd || Kind == RecurKind::FMulAdd) &&
1673 "Unexpected reduction kind");
1674 assert(Src->getType()->isVectorTy() && "Expected a vector type");
1675 assert(!Start->getType()->isVectorTy() && "Expected a scalar type");
1676
1677 return B.CreateFAddReduce(Acc: Start, Src);
1678}
1679
1680Value *llvm::createOrderedReduction(IRBuilderBase &Builder, RecurKind Kind,
1681 Value *Src, Value *Start, Value *Mask,
1682 Value *EVL) {
1683 assert((Kind == RecurKind::FAdd || Kind == RecurKind::FMulAdd) &&
1684 "Unexpected reduction kind");
1685 assert(Src->getType()->isVectorTy() && "Expected a vector type");
1686 assert(!Start->getType()->isVectorTy() && "Expected a scalar type");
1687
1688 Intrinsic::ID Id = getReductionIntrinsicID(RK: RecurKind::FAdd);
1689 Intrinsic::ID VPID = getVPReductionIntrinsicID(Id);
1690 auto *EltTy = cast<VectorType>(Val: Src->getType())->getElementType();
1691 Value *Ops[] = {Start, Src, Mask, EVL};
1692 return Builder.CreateIntrinsic(RetTy: EltTy, ID: VPID, Args: Ops);
1693}
1694
1695void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue,
1696 bool IncludeWrapFlags) {
1697 auto *VecOp = dyn_cast<Instruction>(Val: I);
1698 if (!VecOp)
1699 return;
1700 auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(Val: VL[0])
1701 : dyn_cast<Instruction>(Val: OpValue);
1702 if (!Intersection)
1703 return;
1704 const unsigned Opcode = Intersection->getOpcode();
1705 VecOp->copyIRFlags(V: Intersection, IncludeWrapFlags);
1706 for (auto *V : VL) {
1707 auto *Instr = dyn_cast<Instruction>(Val: V);
1708 if (!Instr)
1709 continue;
1710 if (OpValue == nullptr || Opcode == Instr->getOpcode())
1711 VecOp->andIRFlags(V);
1712 }
1713}
1714
1715bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L,
1716 ScalarEvolution &SE) {
1717 const SCEV *Zero = SE.getZero(Ty: S->getType());
1718 return SE.isAvailableAtLoopEntry(S, L) &&
1719 SE.isLoopEntryGuardedByCond(L, Pred: ICmpInst::ICMP_SLT, LHS: S, RHS: Zero);
1720}
1721
1722bool llvm::isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
1723 ScalarEvolution &SE) {
1724 const SCEV *Zero = SE.getZero(Ty: S->getType());
1725 return SE.isAvailableAtLoopEntry(S, L) &&
1726 SE.isLoopEntryGuardedByCond(L, Pred: ICmpInst::ICMP_SGE, LHS: S, RHS: Zero);
1727}
1728
1729bool llvm::isKnownPositiveInLoop(const SCEV *S, const Loop *L,
1730 ScalarEvolution &SE) {
1731 const SCEV *Zero = SE.getZero(Ty: S->getType());
1732 return SE.isAvailableAtLoopEntry(S, L) &&
1733 SE.isLoopEntryGuardedByCond(L, Pred: ICmpInst::ICMP_SGT, LHS: S, RHS: Zero);
1734}
1735
1736bool llvm::isKnownNonPositiveInLoop(const SCEV *S, const Loop *L,
1737 ScalarEvolution &SE) {
1738 const SCEV *Zero = SE.getZero(Ty: S->getType());
1739 return SE.isAvailableAtLoopEntry(S, L) &&
1740 SE.isLoopEntryGuardedByCond(L, Pred: ICmpInst::ICMP_SLE, LHS: S, RHS: Zero);
1741}
1742
1743bool llvm::cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
1744 bool Signed) {
1745 unsigned BitWidth = cast<IntegerType>(Val: S->getType())->getBitWidth();
1746 APInt Min = Signed ? APInt::getSignedMinValue(numBits: BitWidth) :
1747 APInt::getMinValue(numBits: BitWidth);
1748 auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1749 return SE.isAvailableAtLoopEntry(S, L) &&
1750 SE.isLoopEntryGuardedByCond(L, Pred: Predicate, LHS: S,
1751 RHS: SE.getConstant(Val: Min));
1752}
1753
1754bool llvm::cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
1755 bool Signed) {
1756 unsigned BitWidth = cast<IntegerType>(Val: S->getType())->getBitWidth();
1757 APInt Max = Signed ? APInt::getSignedMaxValue(numBits: BitWidth) :
1758 APInt::getMaxValue(numBits: BitWidth);
1759 auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1760 return SE.isAvailableAtLoopEntry(S, L) &&
1761 SE.isLoopEntryGuardedByCond(L, Pred: Predicate, LHS: S,
1762 RHS: SE.getConstant(Val: Max));
1763}
1764
1765//===----------------------------------------------------------------------===//
1766// rewriteLoopExitValues - Optimize IV users outside the loop.
1767// As a side effect, reduces the amount of IV processing within the loop.
1768//===----------------------------------------------------------------------===//
1769
1770static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) {
1771 SmallPtrSet<const Instruction *, 8> Visited;
1772 SmallVector<const Instruction *, 8> WorkList;
1773 Visited.insert(Ptr: I);
1774 WorkList.push_back(Elt: I);
1775 while (!WorkList.empty()) {
1776 const Instruction *Curr = WorkList.pop_back_val();
1777 // This use is outside the loop, nothing to do.
1778 if (!L->contains(Inst: Curr))
1779 continue;
1780 // Do we assume it is a "hard" use which will not be eliminated easily?
1781 if (Curr->mayHaveSideEffects())
1782 return true;
1783 // Otherwise, add all its users to worklist.
1784 for (const auto *U : Curr->users()) {
1785 auto *UI = cast<Instruction>(Val: U);
1786 if (Visited.insert(Ptr: UI).second)
1787 WorkList.push_back(Elt: UI);
1788 }
1789 }
1790 return false;
1791}
1792
1793// Collect information about PHI nodes which can be transformed in
1794// rewriteLoopExitValues.
1795struct RewritePhi {
1796 PHINode *PN; // For which PHI node is this replacement?
1797 unsigned Ith; // For which incoming value?
1798 SCEVUse ExpansionSCEV; // The SCEV of the incoming value we are rewriting.
1799 Instruction *ExpansionPoint; // Where we'd like to expand that SCEV?
1800 bool HighCost; // Is this expansion a high-cost?
1801
1802 RewritePhi(PHINode *P, unsigned I, SCEVUse Val, Instruction *ExpansionPt,
1803 bool H)
1804 : PN(P), Ith(I), ExpansionSCEV(Val), ExpansionPoint(ExpansionPt),
1805 HighCost(H) {}
1806};
1807
1808// Check whether it is possible to delete the loop after rewriting exit
1809// value. If it is possible, ignore ReplaceExitValue and do rewriting
1810// aggressively.
1811static bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
1812 BasicBlock *Preheader = L->getLoopPreheader();
1813 // If there is no preheader, the loop will not be deleted.
1814 if (!Preheader)
1815 return false;
1816
1817 // In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
1818 // We obviate multiple ExitingBlocks case for simplicity.
1819 // TODO: If we see testcase with multiple ExitingBlocks can be deleted
1820 // after exit value rewriting, we can enhance the logic here.
1821 SmallVector<BasicBlock *, 4> ExitingBlocks;
1822 L->getExitingBlocks(ExitingBlocks);
1823 SmallVector<BasicBlock *, 8> ExitBlocks;
1824 L->getUniqueExitBlocks(ExitBlocks);
1825 if (ExitBlocks.size() != 1 || ExitingBlocks.size() != 1)
1826 return false;
1827
1828 BasicBlock *ExitBlock = ExitBlocks[0];
1829 BasicBlock::iterator BI = ExitBlock->begin();
1830 while (PHINode *P = dyn_cast<PHINode>(Val&: BI)) {
1831 Value *Incoming = P->getIncomingValueForBlock(BB: ExitingBlocks[0]);
1832
1833 // If the Incoming value of P is found in RewritePhiSet, we know it
1834 // could be rewritten to use a loop invariant value in transformation
1835 // phase later. Skip it in the loop invariant check below.
1836 bool found = false;
1837 for (const RewritePhi &Phi : RewritePhiSet) {
1838 unsigned i = Phi.Ith;
1839 if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
1840 found = true;
1841 break;
1842 }
1843 }
1844
1845 Instruction *I;
1846 if (!found && (I = dyn_cast<Instruction>(Val: Incoming)))
1847 if (!L->hasLoopInvariantOperands(I))
1848 return false;
1849
1850 ++BI;
1851 }
1852
1853 for (auto *BB : L->blocks())
1854 if (llvm::any_of(Range&: *BB, P: [](Instruction &I) {
1855 return I.mayHaveSideEffects();
1856 }))
1857 return false;
1858
1859 return true;
1860}
1861
1862/// Checks if it is safe to call InductionDescriptor::isInductionPHI for \p Phi,
1863/// and returns true if this Phi is an induction phi in the loop. When
1864/// isInductionPHI returns true, \p ID will be also be set by isInductionPHI.
1865static bool checkIsIndPhi(PHINode *Phi, Loop *L, ScalarEvolution *SE,
1866 InductionDescriptor &ID) {
1867 if (!Phi)
1868 return false;
1869 if (!L->getLoopPreheader())
1870 return false;
1871 if (Phi->getParent() != L->getHeader())
1872 return false;
1873 return InductionDescriptor::isInductionPHI(Phi, L, SE, D&: ID);
1874}
1875
1876int llvm::rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
1877 ScalarEvolution *SE,
1878 const TargetTransformInfo *TTI,
1879 SCEVExpander &Rewriter, DominatorTree *DT,
1880 ReplaceExitVal ReplaceExitValue,
1881 SmallVector<WeakTrackingVH, 16> &DeadInsts) {
1882 // Check a pre-condition.
1883 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
1884 "Caller did not preserve LCSSA!");
1885
1886 SmallVector<BasicBlock*, 8> ExitBlocks;
1887 L->getUniqueExitBlocks(ExitBlocks);
1888
1889 SmallVector<RewritePhi, 8> RewritePhiSet;
1890 // Find all values that are computed inside the loop, but used outside of it.
1891 // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
1892 // the exit blocks of the loop to find them.
1893 for (BasicBlock *ExitBB : ExitBlocks) {
1894 // If there are no PHI nodes in this exit block, then no values defined
1895 // inside the loop are used on this path, skip it.
1896 PHINode *PN = dyn_cast<PHINode>(Val: ExitBB->begin());
1897 if (!PN) continue;
1898
1899 unsigned NumPreds = PN->getNumIncomingValues();
1900
1901 // Iterate over all of the PHI nodes.
1902 BasicBlock::iterator BBI = ExitBB->begin();
1903 while ((PN = dyn_cast<PHINode>(Val: BBI++))) {
1904 if (PN->use_empty())
1905 continue; // dead use, don't replace it
1906
1907 if (!SE->isSCEVable(Ty: PN->getType()))
1908 continue;
1909
1910 // Iterate over all of the values in all the PHI nodes.
1911 for (unsigned i = 0; i != NumPreds; ++i) {
1912 // If the value being merged in is not integer or is not defined
1913 // in the loop, skip it.
1914 Value *InVal = PN->getIncomingValue(i);
1915 if (!isa<Instruction>(Val: InVal))
1916 continue;
1917
1918 // If this pred is for a subloop, not L itself, skip it.
1919 if (LI->getLoopFor(BB: PN->getIncomingBlock(i)) != L)
1920 continue; // The Block is in a subloop, skip it.
1921
1922 // Check that InVal is defined in the loop.
1923 Instruction *Inst = cast<Instruction>(Val: InVal);
1924 if (!L->contains(Inst))
1925 continue;
1926
1927 // Find exit values which are induction variables in the loop, and are
1928 // unused in the loop, with the only use being the exit block PhiNode,
1929 // and the induction variable update binary operator.
1930 // The exit value can be replaced with the final value when it is cheap
1931 // to do so.
1932 if (ReplaceExitValue == UnusedIndVarInLoop) {
1933 InductionDescriptor ID;
1934 PHINode *IndPhi = dyn_cast<PHINode>(Val: Inst);
1935 if (IndPhi) {
1936 if (!checkIsIndPhi(Phi: IndPhi, L, SE, ID))
1937 continue;
1938 // This is an induction PHI. Check that the only users are PHI
1939 // nodes, and induction variable update binary operators.
1940 if (llvm::any_of(Range: Inst->users(), P: [&](User *U) {
1941 if (!isa<PHINode>(Val: U) && !isa<BinaryOperator>(Val: U))
1942 return true;
1943 BinaryOperator *B = dyn_cast<BinaryOperator>(Val: U);
1944 if (B && B != ID.getInductionBinOp())
1945 return true;
1946 return false;
1947 }))
1948 continue;
1949 } else {
1950 // If it is not an induction phi, it must be an induction update
1951 // binary operator with an induction phi user.
1952 BinaryOperator *B = dyn_cast<BinaryOperator>(Val: Inst);
1953 if (!B)
1954 continue;
1955 if (llvm::any_of(Range: Inst->users(), P: [&](User *U) {
1956 PHINode *Phi = dyn_cast<PHINode>(Val: U);
1957 if (Phi != PN && !checkIsIndPhi(Phi, L, SE, ID))
1958 return true;
1959 return false;
1960 }))
1961 continue;
1962 if (B != ID.getInductionBinOp())
1963 continue;
1964 }
1965 }
1966
1967 // Okay, this instruction has a user outside of the current loop
1968 // and varies predictably *inside* the loop. Evaluate the value it
1969 // contains when the loop exits, if possible. We prefer to start with
1970 // expressions which are true for all exits (so as to maximize
1971 // expression reuse by the SCEVExpander), but resort to per-exit
1972 // evaluation if that fails.
1973 SCEVUse ExitValue = SE->getSCEVAtScope(V: Inst, L: L->getParentLoop());
1974 if (isa<SCEVCouldNotCompute>(Val: ExitValue) ||
1975 !SE->isLoopInvariant(S: ExitValue, L) ||
1976 !Rewriter.isSafeToExpand(S: ExitValue)) {
1977 // TODO: This should probably be sunk into SCEV in some way; maybe a
1978 // getSCEVForExit(SCEV*, L, ExitingBB)? It can be generalized for
1979 // most SCEV expressions and other recurrence types (e.g. shift
1980 // recurrences). Is there existing code we can reuse?
1981 const SCEV *ExitCount = SE->getExitCount(L, ExitingBlock: PN->getIncomingBlock(i));
1982 if (isa<SCEVCouldNotCompute>(Val: ExitCount))
1983 continue;
1984 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: Inst)))
1985 if (AddRec->getLoop() == L)
1986 ExitValue = AddRec->evaluateAtIteration(It: ExitCount, SE&: *SE);
1987 if (isa<SCEVCouldNotCompute>(Val: ExitValue) ||
1988 !SE->isLoopInvariant(S: ExitValue, L) ||
1989 !Rewriter.isSafeToExpand(S: ExitValue))
1990 continue;
1991 }
1992
1993 // Computing the value outside of the loop brings no benefit if it is
1994 // definitely used inside the loop in a way which can not be optimized
1995 // away. Avoid doing so unless we know we have a value which computes
1996 // the ExitValue already. TODO: This should be merged into SCEV
1997 // expander to leverage its knowledge of existing expressions.
1998 if (ReplaceExitValue != AlwaysRepl && !isa<SCEVConstant>(Val: ExitValue) &&
1999 !isa<SCEVUnknown>(Val: ExitValue) && hasHardUserWithinLoop(L, I: Inst))
2000 continue;
2001
2002 // Check if expansions of this SCEV would count as being high cost.
2003 bool HighCost = Rewriter.isHighCostExpansion(
2004 Exprs: ExitValue.getPointer(), L, Budget: SCEVCheapExpansionBudget, TTI, At: Inst);
2005
2006 // Note that we must not perform expansions until after
2007 // we query *all* the costs, because if we perform temporary expansion
2008 // inbetween, one that we might not intend to keep, said expansion
2009 // *may* affect cost calculation of the next SCEV's we'll query,
2010 // and next SCEV may errneously get smaller cost.
2011
2012 // Collect all the candidate PHINodes to be rewritten.
2013 Instruction *InsertPt =
2014 (isa<PHINode>(Val: Inst) || isa<LandingPadInst>(Val: Inst)) ?
2015 &*Inst->getParent()->getFirstInsertionPt() : Inst;
2016 RewritePhiSet.emplace_back(Args&: PN, Args&: i, Args&: ExitValue, Args&: InsertPt, Args&: HighCost);
2017 }
2018 }
2019 }
2020
2021 // TODO: evaluate whether it is beneficial to change how we calculate
2022 // high-cost: if we have SCEV 'A' which we know we will expand, should we
2023 // calculate the cost of other SCEV's after expanding SCEV 'A', thus
2024 // potentially giving cost bonus to those other SCEV's?
2025
2026 bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
2027 int NumReplaced = 0;
2028
2029 // Transformation.
2030 for (const RewritePhi &Phi : RewritePhiSet) {
2031 PHINode *PN = Phi.PN;
2032
2033 // Only do the rewrite when the ExitValue can be expanded cheaply.
2034 // If LoopCanBeDel is true, rewrite exit value aggressively.
2035 if ((ReplaceExitValue == OnlyCheapRepl ||
2036 ReplaceExitValue == UnusedIndVarInLoop) &&
2037 !LoopCanBeDel && Phi.HighCost)
2038 continue;
2039
2040 Value *ExitVal = Rewriter.expandCodeFor(
2041 SH: Phi.ExpansionSCEV, Ty: Phi.PN->getType(), I: Phi.ExpansionPoint);
2042
2043 LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = " << *ExitVal
2044 << '\n'
2045 << " LoopVal = " << *(Phi.ExpansionPoint) << "\n");
2046
2047#ifndef NDEBUG
2048 // If we reuse an instruction from a loop which is neither L nor one of
2049 // its containing loops, we end up breaking LCSSA form for this loop by
2050 // creating a new use of its instruction.
2051 if (auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
2052 if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
2053 if (EVL != L)
2054 assert(EVL->contains(L) && "LCSSA breach detected!");
2055#endif
2056
2057 NumReplaced++;
2058 Instruction *Inst = cast<Instruction>(Val: PN->getIncomingValue(i: Phi.Ith));
2059 PN->setIncomingValue(i: Phi.Ith, V: ExitVal);
2060 // It's necessary to tell ScalarEvolution about this explicitly so that
2061 // it can walk the def-use list and forget all SCEVs, as it may not be
2062 // watching the PHI itself. Once the new exit value is in place, there
2063 // may not be a def-use connection between the loop and every instruction
2064 // which got a SCEVAddRecExpr for that loop.
2065 SE->forgetValue(V: PN);
2066
2067 // If this instruction is dead now, delete it. Don't do it now to avoid
2068 // invalidating iterators.
2069 if (isInstructionTriviallyDead(I: Inst, TLI))
2070 DeadInsts.push_back(Elt: Inst);
2071
2072 // Replace PN with ExitVal if that is legal and does not break LCSSA.
2073 if (PN->getNumIncomingValues() == 1 &&
2074 LI->replacementPreservesLCSSAForm(From: PN, To: ExitVal)) {
2075 PN->replaceAllUsesWith(V: ExitVal);
2076 PN->eraseFromParent();
2077 }
2078 }
2079
2080 // The insertion point instruction may have been deleted; clear it out
2081 // so that the rewriter doesn't trip over it later.
2082 Rewriter.clearInsertPoint();
2083 return NumReplaced;
2084}
2085
2086/// Utility that implements appending of loops onto a worklist.
2087/// Loops are added in preorder (analogous for reverse postorder for trees),
2088/// and the worklist is processed LIFO.
2089template <typename RangeT>
2090void llvm::appendReversedLoopsToWorklist(
2091 RangeT &&Loops, SmallPriorityWorklist<Loop *, 4> &Worklist) {
2092 // We use an internal worklist to build up the preorder traversal without
2093 // recursion.
2094 SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
2095
2096 // We walk the initial sequence of loops in reverse because we generally want
2097 // to visit defs before uses and the worklist is LIFO.
2098 for (Loop *RootL : Loops) {
2099 assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
2100 assert(PreOrderWorklist.empty() &&
2101 "Must start with an empty preorder walk worklist.");
2102 PreOrderWorklist.push_back(Elt: RootL);
2103 do {
2104 Loop *L = PreOrderWorklist.pop_back_val();
2105 PreOrderWorklist.append(in_start: L->begin(), in_end: L->end());
2106 PreOrderLoops.push_back(Elt: L);
2107 } while (!PreOrderWorklist.empty());
2108
2109 Worklist.insert(Input: std::move(PreOrderLoops));
2110 PreOrderLoops.clear();
2111 }
2112}
2113
2114template <typename RangeT>
2115void llvm::appendLoopsToWorklist(RangeT &&Loops,
2116 SmallPriorityWorklist<Loop *, 4> &Worklist) {
2117 appendReversedLoopsToWorklist(reverse(Loops), Worklist);
2118}
2119
2120template LLVM_EXPORT_TEMPLATE void
2121llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>(
2122 ArrayRef<Loop *> &Loops, SmallPriorityWorklist<Loop *, 4> &Worklist);
2123
2124template LLVM_EXPORT_TEMPLATE void
2125llvm::appendLoopsToWorklist<Loop &>(Loop &L,
2126 SmallPriorityWorklist<Loop *, 4> &Worklist);
2127
2128void llvm::appendLoopsToWorklist(LoopInfo &LI,
2129 SmallPriorityWorklist<Loop *, 4> &Worklist) {
2130 appendReversedLoopsToWorklist(Loops&: LI, Worklist);
2131}
2132
2133Loop *llvm::cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
2134 LoopInfo *LI, LPPassManager *LPM) {
2135 Loop &New = *LI->AllocateLoop();
2136 if (PL)
2137 PL->addChildLoop(NewChild: &New);
2138 else
2139 LI->addTopLevelLoop(New: &New);
2140
2141 if (LPM)
2142 LPM->addLoop(L&: New);
2143
2144 // Add all of the blocks in L to the new loop.
2145 for (BasicBlock *BB : L->blocks())
2146 if (LI->getLoopFor(BB) == L)
2147 New.addBasicBlockToLoop(NewBB: cast<BasicBlock>(Val&: VM[BB]), LI&: *LI);
2148
2149 // Add all of the subloops to the new loop.
2150 for (Loop *I : *L)
2151 cloneLoop(L: I, PL: &New, VM, LI, LPM);
2152
2153 return &New;
2154}
2155
2156/// IR Values for the lower and upper bounds of a pointer evolution. We
2157/// need to use value-handles because SCEV expansion can invalidate previously
2158/// expanded values. Thus expansion of a pointer can invalidate the bounds for
2159/// a previous one.
2160struct PointerBounds {
2161 TrackingVH<Value> Start;
2162 TrackingVH<Value> End;
2163 Value *StrideToCheck;
2164};
2165
2166/// Expand code for the lower and upper bound of the pointer group \p CG
2167/// in \p TheLoop. \return the values for the bounds.
2168static PointerBounds expandBounds(const RuntimeCheckingPtrGroup *CG,
2169 Loop *TheLoop, Instruction *Loc,
2170 SCEVExpander &Exp, bool HoistRuntimeChecks) {
2171 LLVMContext &Ctx = Loc->getContext();
2172 Type *PtrArithTy = PointerType::get(C&: Ctx, AddressSpace: CG->AddressSpace);
2173
2174 Value *Start = nullptr, *End = nullptr;
2175 LLVM_DEBUG(dbgs() << "LAA: Adding RT check for range:\n");
2176 const SCEV *Low = CG->Low, *High = CG->High, *Stride = nullptr;
2177
2178 // If the Low and High values are themselves loop-variant, then we may want
2179 // to expand the range to include those covered by the outer loop as well.
2180 // There is a trade-off here with the advantage being that creating checks
2181 // using the expanded range permits the runtime memory checks to be hoisted
2182 // out of the outer loop. This reduces the cost of entering the inner loop,
2183 // which can be significant for low trip counts. The disadvantage is that
2184 // there is a chance we may now never enter the vectorized inner loop,
2185 // whereas using a restricted range check could have allowed us to enter at
2186 // least once. This is why the behaviour is not currently the default and is
2187 // controlled by the parameter 'HoistRuntimeChecks'.
2188 if (HoistRuntimeChecks && TheLoop->getParentLoop() &&
2189 isa<SCEVAddRecExpr>(Val: High) && isa<SCEVAddRecExpr>(Val: Low)) {
2190 auto *HighAR = cast<SCEVAddRecExpr>(Val: High);
2191 auto *LowAR = cast<SCEVAddRecExpr>(Val: Low);
2192 const Loop *OuterLoop = TheLoop->getParentLoop();
2193 ScalarEvolution &SE = *Exp.getSE();
2194 const SCEV *Recur = LowAR->getStepRecurrence(SE);
2195 if (Recur == HighAR->getStepRecurrence(SE) &&
2196 HighAR->getLoop() == OuterLoop && LowAR->getLoop() == OuterLoop) {
2197 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
2198 const SCEV *OuterExitCount = SE.getExitCount(L: OuterLoop, ExitingBlock: OuterLoopLatch);
2199 if (!isa<SCEVCouldNotCompute>(Val: OuterExitCount) &&
2200 OuterExitCount->getType()->isIntegerTy()) {
2201 const SCEV *NewHigh =
2202 cast<SCEVAddRecExpr>(Val: High)->evaluateAtIteration(It: OuterExitCount, SE);
2203 if (!isa<SCEVCouldNotCompute>(Val: NewHigh)) {
2204 LLVM_DEBUG(dbgs() << "LAA: Expanded RT check for range to include "
2205 "outer loop in order to permit hoisting\n");
2206 High = NewHigh;
2207 Low = cast<SCEVAddRecExpr>(Val: Low)->getStart();
2208 // If there is a possibility that the stride is negative then we have
2209 // to generate extra checks to ensure the stride is positive.
2210 if (!SE.isKnownNonNegative(
2211 S: SE.applyLoopGuards(Expr: Recur, L: HighAR->getLoop()))) {
2212 Stride = Recur;
2213 LLVM_DEBUG(dbgs() << "LAA: ... but need to check stride is "
2214 "positive: "
2215 << *Stride << '\n');
2216 }
2217 }
2218 }
2219 }
2220 }
2221
2222 Start = Exp.expandCodeFor(SH: Low, Ty: PtrArithTy, I: Loc);
2223 End = Exp.expandCodeFor(SH: High, Ty: PtrArithTy, I: Loc);
2224 if (CG->NeedsFreeze) {
2225 IRBuilder<> Builder(Loc);
2226 Start = Builder.CreateFreeze(V: Start, Name: Start->getName() + ".fr");
2227 End = Builder.CreateFreeze(V: End, Name: End->getName() + ".fr");
2228 }
2229 Value *StrideVal =
2230 Stride ? Exp.expandCodeFor(SH: Stride, Ty: Stride->getType(), I: Loc) : nullptr;
2231 LLVM_DEBUG(dbgs() << "Start: " << *Low << " End: " << *High << "\n");
2232 return {.Start: Start, .End: End, .StrideToCheck: StrideVal};
2233}
2234
2235/// Turns a collection of checks into a collection of expanded upper and
2236/// lower bounds for both pointers in the check.
2237static SmallVector<std::pair<PointerBounds, PointerBounds>, 4>
2238expandBounds(const SmallVectorImpl<RuntimePointerCheck> &PointerChecks, Loop *L,
2239 Instruction *Loc, SCEVExpander &Exp, bool HoistRuntimeChecks) {
2240 SmallVector<std::pair<PointerBounds, PointerBounds>, 4> ChecksWithBounds;
2241
2242 // Here we're relying on the SCEV Expander's cache to only emit code for the
2243 // same bounds once.
2244 transform(Range: PointerChecks, d_first: std::back_inserter(x&: ChecksWithBounds),
2245 F: [&](const RuntimePointerCheck &Check) {
2246 PointerBounds First = expandBounds(CG: Check.first, TheLoop: L, Loc, Exp,
2247 HoistRuntimeChecks),
2248 Second = expandBounds(CG: Check.second, TheLoop: L, Loc, Exp,
2249 HoistRuntimeChecks);
2250 return std::make_pair(x&: First, y&: Second);
2251 });
2252
2253 return ChecksWithBounds;
2254}
2255
2256Value *llvm::addRuntimeChecks(
2257 Instruction *Loc, Loop *TheLoop,
2258 const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
2259 SCEVExpander &Exp, bool HoistRuntimeChecks) {
2260 // TODO: Move noalias annotation code from LoopVersioning here and share with LV if possible.
2261 // TODO: Pass RtPtrChecking instead of PointerChecks and SE separately, if possible
2262 auto ExpandedChecks =
2263 expandBounds(PointerChecks, L: TheLoop, Loc, Exp, HoistRuntimeChecks);
2264
2265 LLVMContext &Ctx = Loc->getContext();
2266 IRBuilder ChkBuilder(Ctx, InstSimplifyFolder(Loc->getDataLayout()));
2267 ChkBuilder.SetInsertPoint(Loc);
2268 // Our instructions might fold to a constant.
2269 Value *MemoryRuntimeCheck = nullptr;
2270
2271 for (const auto &[A, B] : ExpandedChecks) {
2272 // Check if two pointers (A and B) conflict where conflict is computed as:
2273 // start(A) <= end(B) && start(B) <= end(A)
2274
2275 assert((A.Start->getType()->getPointerAddressSpace() ==
2276 B.End->getType()->getPointerAddressSpace()) &&
2277 (B.Start->getType()->getPointerAddressSpace() ==
2278 A.End->getType()->getPointerAddressSpace()) &&
2279 "Trying to bounds check pointers with different address spaces");
2280
2281 // [A|B].Start points to the first accessed byte under base [A|B].
2282 // [A|B].End points to the last accessed byte, plus one.
2283 // There is no conflict when the intervals are disjoint:
2284 // NoConflict = (B.Start >= A.End) || (A.Start >= B.End)
2285 //
2286 // bound0 = (B.Start < A.End)
2287 // bound1 = (A.Start < B.End)
2288 // IsConflict = bound0 & bound1
2289 Value *Cmp0 = ChkBuilder.CreateICmpULT(LHS: A.Start, RHS: B.End, Name: "bound0");
2290 Value *Cmp1 = ChkBuilder.CreateICmpULT(LHS: B.Start, RHS: A.End, Name: "bound1");
2291 Value *IsConflict = ChkBuilder.CreateAnd(LHS: Cmp0, RHS: Cmp1, Name: "found.conflict");
2292 if (A.StrideToCheck) {
2293 Value *IsNegativeStride = ChkBuilder.CreateICmpSLT(
2294 LHS: A.StrideToCheck, RHS: ConstantInt::get(Ty: A.StrideToCheck->getType(), V: 0),
2295 Name: "stride.check");
2296 IsConflict = ChkBuilder.CreateOr(LHS: IsConflict, RHS: IsNegativeStride);
2297 }
2298 if (B.StrideToCheck) {
2299 Value *IsNegativeStride = ChkBuilder.CreateICmpSLT(
2300 LHS: B.StrideToCheck, RHS: ConstantInt::get(Ty: B.StrideToCheck->getType(), V: 0),
2301 Name: "stride.check");
2302 IsConflict = ChkBuilder.CreateOr(LHS: IsConflict, RHS: IsNegativeStride);
2303 }
2304 if (MemoryRuntimeCheck) {
2305 IsConflict =
2306 ChkBuilder.CreateOr(LHS: MemoryRuntimeCheck, RHS: IsConflict, Name: "conflict.rdx");
2307 }
2308 MemoryRuntimeCheck = IsConflict;
2309 }
2310
2311 Exp.eraseDeadInstructions(Root: MemoryRuntimeCheck);
2312 return MemoryRuntimeCheck;
2313}
2314
2315Value *llvm::addDiffRuntimeChecks(Instruction *Loc,
2316 ArrayRef<PointerDiffInfo> Checks,
2317 SCEVExpander &Expander, ElementCount VF,
2318 unsigned IC) {
2319
2320 LLVMContext &Ctx = Loc->getContext();
2321 IRBuilder ChkBuilder(Ctx, InstSimplifyFolder(Loc->getDataLayout()));
2322 ChkBuilder.SetInsertPoint(Loc);
2323 // Our instructions might fold to a constant.
2324 Value *MemoryRuntimeCheck = nullptr;
2325
2326 auto &SE = *Expander.getSE();
2327 // Map to keep track of created compares, The key is the pair of operands for
2328 // the compare, to allow detecting and re-using redundant compares.
2329 DenseMap<std::pair<Value *, Value *>, Value *> SeenCompares;
2330 for (const auto &[SrcStart, SinkStart, AccessSize, NeedsFreeze] : Checks) {
2331 assert(IC * AccessSize > 0 &&
2332 "Threshold must be non-zero to use diff-check");
2333 Type *Ty = SinkStart->getType();
2334 const SCEV *TotalAccessSize = SE.getElementCount(Ty, EC: VF * IC * AccessSize);
2335 Value *ThresholdMinusOne = Expander.expandCodeFor(
2336 SH: SE.getMinusSCEV(LHS: TotalAccessSize, RHS: SE.getConstant(Ty, V: 1)), Ty, I: Loc);
2337 Value *Diff =
2338 Expander.expandCodeFor(SH: SE.getMinusSCEV(LHS: SinkStart, RHS: SrcStart), Ty, I: Loc);
2339
2340 // Check if the same compare has already been created earlier. In that case,
2341 // there is no need to check it again.
2342 Value *IsConflict = SeenCompares.lookup(Val: {Diff, ThresholdMinusOne});
2343 if (IsConflict)
2344 continue;
2345
2346 // Use (Diff - 1) <u (Threshold - 1), equivalent to 0 < Diff <u Threshold,
2347 // to exclude Diff == 0 (equal pointers are safe).
2348 IsConflict = ChkBuilder.CreateICmpULT(
2349 LHS: ChkBuilder.CreateSub(LHS: Diff, RHS: ConstantInt::get(Ty, V: 1)), RHS: ThresholdMinusOne,
2350 Name: "diff.check");
2351 SeenCompares.insert(KV: {{Diff, ThresholdMinusOne}, IsConflict});
2352 if (NeedsFreeze)
2353 IsConflict =
2354 ChkBuilder.CreateFreeze(V: IsConflict, Name: IsConflict->getName() + ".fr");
2355 if (MemoryRuntimeCheck) {
2356 IsConflict =
2357 ChkBuilder.CreateOr(LHS: MemoryRuntimeCheck, RHS: IsConflict, Name: "conflict.rdx");
2358 }
2359 MemoryRuntimeCheck = IsConflict;
2360 }
2361
2362 Expander.eraseDeadInstructions(Root: MemoryRuntimeCheck);
2363 return MemoryRuntimeCheck;
2364}
2365
2366std::optional<IVConditionInfo>
2367llvm::hasPartialIVCondition(const Loop &L, unsigned MSSAThreshold,
2368 const MemorySSA &MSSA, AAResults &AA) {
2369 auto *TI = dyn_cast<CondBrInst>(Val: L.getHeader()->getTerminator());
2370 if (!TI)
2371 return {};
2372
2373 auto *CondI = dyn_cast<Instruction>(Val: TI->getCondition());
2374 // The case with the condition outside the loop should already be handled
2375 // earlier.
2376 // Allow CmpInst and TruncInsts as they may be users of load instructions
2377 // and have potential for partial unswitching
2378 if (!CondI || !isa<CmpInst, TruncInst>(Val: CondI) || !L.contains(Inst: CondI))
2379 return {};
2380
2381 SmallVector<Instruction *> InstToDuplicate;
2382 InstToDuplicate.push_back(Elt: CondI);
2383
2384 SmallVector<Value *, 4> WorkList;
2385 WorkList.append(in_start: CondI->op_begin(), in_end: CondI->op_end());
2386
2387 SmallVector<MemoryAccess *, 4> AccessesToCheck;
2388 SmallVector<MemoryLocation, 4> AccessedLocs;
2389 while (!WorkList.empty()) {
2390 Instruction *I = dyn_cast<Instruction>(Val: WorkList.pop_back_val());
2391 if (!I || !L.contains(Inst: I))
2392 continue;
2393
2394 // TODO: support additional instructions.
2395 if (!isa<LoadInst>(Val: I) && !isa<GetElementPtrInst>(Val: I))
2396 return {};
2397
2398 // Do not duplicate volatile and atomic loads.
2399 if (auto *LI = dyn_cast<LoadInst>(Val: I))
2400 if (LI->isVolatile() || LI->isAtomic())
2401 return {};
2402
2403 InstToDuplicate.push_back(Elt: I);
2404 if (MemoryAccess *MA = MSSA.getMemoryAccess(I)) {
2405 if (auto *MemUse = dyn_cast_or_null<MemoryUse>(Val: MA)) {
2406 // Queue the defining access to check for alias checks.
2407 AccessesToCheck.push_back(Elt: MemUse->getDefiningAccess());
2408 AccessedLocs.push_back(Elt: MemoryLocation::get(Inst: I));
2409 } else {
2410 // MemoryDefs may clobber the location or may be atomic memory
2411 // operations. Bail out.
2412 return {};
2413 }
2414 }
2415 WorkList.append(in_start: I->op_begin(), in_end: I->op_end());
2416 }
2417
2418 if (InstToDuplicate.empty())
2419 return {};
2420
2421 SmallVector<BasicBlock *, 4> ExitingBlocks;
2422 L.getExitingBlocks(ExitingBlocks);
2423 auto HasNoClobbersOnPath =
2424 [&L, &AA, &AccessedLocs, &ExitingBlocks, &InstToDuplicate,
2425 MSSAThreshold](BasicBlock *Succ, BasicBlock *Header,
2426 SmallVector<MemoryAccess *, 4> AccessesToCheck)
2427 -> std::optional<IVConditionInfo> {
2428 IVConditionInfo Info;
2429 // First, collect all blocks in the loop that are on a patch from Succ
2430 // to the header.
2431 SmallVector<BasicBlock *, 4> WorkList;
2432 WorkList.push_back(Elt: Succ);
2433 WorkList.push_back(Elt: Header);
2434 SmallPtrSet<BasicBlock *, 4> Seen;
2435 Seen.insert(Ptr: Header);
2436 Info.PathIsNoop &=
2437 all_of(Range&: *Header, P: [](Instruction &I) { return !I.mayHaveSideEffects(); });
2438
2439 while (!WorkList.empty()) {
2440 BasicBlock *Current = WorkList.pop_back_val();
2441 if (!L.contains(BB: Current))
2442 continue;
2443 const auto &SeenIns = Seen.insert(Ptr: Current);
2444 if (!SeenIns.second)
2445 continue;
2446
2447 Info.PathIsNoop &= all_of(
2448 Range&: *Current, P: [](Instruction &I) { return !I.mayHaveSideEffects(); });
2449 WorkList.append(in_start: succ_begin(BB: Current), in_end: succ_end(BB: Current));
2450 }
2451
2452 // Require at least 2 blocks on a path through the loop. This skips
2453 // paths that directly exit the loop.
2454 if (Seen.size() < 2)
2455 return {};
2456
2457 // Next, check if there are any MemoryDefs that are on the path through
2458 // the loop (in the Seen set) and they may-alias any of the locations in
2459 // AccessedLocs. If that is the case, they may modify the condition and
2460 // partial unswitching is not possible.
2461 SmallPtrSet<MemoryAccess *, 4> SeenAccesses;
2462 while (!AccessesToCheck.empty()) {
2463 MemoryAccess *Current = AccessesToCheck.pop_back_val();
2464 auto SeenI = SeenAccesses.insert(Ptr: Current);
2465 if (!SeenI.second || !Seen.contains(Ptr: Current->getBlock()))
2466 continue;
2467
2468 // Bail out if exceeded the threshold.
2469 if (SeenAccesses.size() >= MSSAThreshold)
2470 return {};
2471
2472 // MemoryUse are read-only accesses.
2473 if (isa<MemoryUse>(Val: Current))
2474 continue;
2475
2476 // For a MemoryDef, check if is aliases any of the location feeding
2477 // the original condition.
2478 if (auto *CurrentDef = dyn_cast<MemoryDef>(Val: Current)) {
2479 if (any_of(Range&: AccessedLocs, P: [&AA, CurrentDef](MemoryLocation &Loc) {
2480 return isModSet(
2481 MRI: AA.getModRefInfo(I: CurrentDef->getMemoryInst(), OptLoc: Loc));
2482 }))
2483 return {};
2484 }
2485
2486 for (Use &U : Current->uses())
2487 AccessesToCheck.push_back(Elt: cast<MemoryAccess>(Val: U.getUser()));
2488 }
2489
2490 // We could also allow loops with known trip counts without mustprogress,
2491 // but ScalarEvolution may not be available.
2492 Info.PathIsNoop &= isMustProgress(L: &L);
2493
2494 // If the path is considered a no-op so far, check if it reaches a
2495 // single exit block without any phis. This ensures no values from the
2496 // loop are used outside of the loop.
2497 if (Info.PathIsNoop) {
2498 for (auto *Exiting : ExitingBlocks) {
2499 if (!Seen.contains(Ptr: Exiting))
2500 continue;
2501 for (auto *Succ : successors(BB: Exiting)) {
2502 if (L.contains(BB: Succ))
2503 continue;
2504
2505 Info.PathIsNoop &= Succ->phis().empty() &&
2506 (!Info.ExitForPath || Info.ExitForPath == Succ);
2507 if (!Info.PathIsNoop)
2508 break;
2509 assert((!Info.ExitForPath || Info.ExitForPath == Succ) &&
2510 "cannot have multiple exit blocks");
2511 Info.ExitForPath = Succ;
2512 }
2513 }
2514 }
2515 if (!Info.ExitForPath)
2516 Info.PathIsNoop = false;
2517
2518 Info.InstToDuplicate = std::move(InstToDuplicate);
2519 return Info;
2520 };
2521
2522 // If we branch to the same successor, partial unswitching will not be
2523 // beneficial.
2524 if (TI->getSuccessor(i: 0) == TI->getSuccessor(i: 1))
2525 return {};
2526
2527 if (auto Info = HasNoClobbersOnPath(TI->getSuccessor(i: 0), L.getHeader(),
2528 AccessesToCheck)) {
2529 Info->KnownValue = ConstantInt::getTrue(Context&: TI->getContext());
2530 return Info;
2531 }
2532 if (auto Info = HasNoClobbersOnPath(TI->getSuccessor(i: 1), L.getHeader(),
2533 AccessesToCheck)) {
2534 Info->KnownValue = ConstantInt::getFalse(Context&: TI->getContext());
2535 return Info;
2536 }
2537
2538 return {};
2539}
2540