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