LLVM 19.0.0git
LoopUtils.cpp
Go to the documentation of this file.
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
14#include "llvm/ADT/DenseSet.h"
16#include "llvm/ADT/ScopeExit.h"
17#include "llvm/ADT/SetVector.h"
33#include "llvm/IR/DIBuilder.h"
34#include "llvm/IR/Dominators.h"
37#include "llvm/IR/MDBuilder.h"
38#include "llvm/IR/Module.h"
41#include "llvm/IR/ValueHandle.h"
43#include "llvm/Pass.h"
44#include "llvm/Support/Debug.h"
48
49using namespace llvm;
50using namespace llvm::PatternMatch;
51
52#define DEBUG_TYPE "loop-utils"
53
54static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced";
55static const char *LLVMLoopDisableLICM = "llvm.licm.disable";
56
58 MemorySSAUpdater *MSSAU,
59 bool PreserveLCSSA) {
60 bool Changed = false;
61
62 // We re-use a vector for the in-loop predecesosrs.
63 SmallVector<BasicBlock *, 4> InLoopPredecessors;
64
65 auto RewriteExit = [&](BasicBlock *BB) {
66 assert(InLoopPredecessors.empty() &&
67 "Must start with an empty predecessors list!");
68 auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });
69
70 // See if there are any non-loop predecessors of this exit block and
71 // keep track of the in-loop predecessors.
72 bool IsDedicatedExit = true;
73 for (auto *PredBB : predecessors(BB))
74 if (L->contains(PredBB)) {
75 if (isa<IndirectBrInst>(PredBB->getTerminator()))
76 // We cannot rewrite exiting edges from an indirectbr.
77 return false;
78
79 InLoopPredecessors.push_back(PredBB);
80 } else {
81 IsDedicatedExit = false;
82 }
83
84 assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
85
86 // Nothing to do if this is already a dedicated exit.
87 if (IsDedicatedExit)
88 return false;
89
90 auto *NewExitBB = SplitBlockPredecessors(
91 BB, InLoopPredecessors, ".loopexit", DT, LI, MSSAU, PreserveLCSSA);
92
93 if (!NewExitBB)
95 dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
96 << *L << "\n");
97 else
98 LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
99 << NewExitBB->getName() << "\n");
100 return true;
101 };
102
103 // Walk the exit blocks directly rather than building up a data structure for
104 // them, but only visit each one once.
106 for (auto *BB : L->blocks())
107 for (auto *SuccBB : successors(BB)) {
108 // We're looking for exit blocks so skip in-loop successors.
109 if (L->contains(SuccBB))
110 continue;
111
112 // Visit each exit block exactly once.
113 if (!Visited.insert(SuccBB).second)
114 continue;
115
116 Changed |= RewriteExit(SuccBB);
117 }
118
119 return Changed;
120}
121
122/// Returns the instructions that use values defined in the loop.
125
126 for (auto *Block : L->getBlocks())
127 // FIXME: I believe that this could use copy_if if the Inst reference could
128 // be adapted into a pointer.
129 for (auto &Inst : *Block) {
130 auto Users = Inst.users();
131 if (any_of(Users, [&](User *U) {
132 auto *Use = cast<Instruction>(U);
133 return !L->contains(Use->getParent());
134 }))
135 UsedOutside.push_back(&Inst);
136 }
137
138 return UsedOutside;
139}
140
142 // By definition, all loop passes need the LoopInfo analysis and the
143 // Dominator tree it depends on. Because they all participate in the loop
144 // pass manager, they must also preserve these.
149
150 // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
151 // here because users shouldn't directly get them from this header.
152 extern char &LoopSimplifyID;
153 extern char &LCSSAID;
158 // This is used in the LPPassManager to perform LCSSA verification on passes
159 // which preserve lcssa form
162
163 // Loop passes are designed to run inside of a loop pass manager which means
164 // that any function analyses they require must be required by the first loop
165 // pass in the manager (so that it is computed before the loop pass manager
166 // runs) and preserved by all loop pasess in the manager. To make this
167 // reasonably robust, the set needed for most loop passes is maintained here.
168 // If your loop pass requires an analysis not listed here, you will need to
169 // carefully audit the loop pass manager nesting structure that results.
177 // FIXME: When all loop passes preserve MemorySSA, it can be required and
178 // preserved here instead of the individual handling in each pass.
179}
180
181/// Manually defined generic "LoopPass" dependency initialization. This is used
182/// to initialize the exact set of passes from above in \c
183/// getLoopAnalysisUsage. It can be used within a loop pass's initialization
184/// with:
185///
186/// INITIALIZE_PASS_DEPENDENCY(LoopPass)
187///
188/// As-if "LoopPass" were a pass.
192 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
193 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
200}
201
202/// Create MDNode for input string.
203static MDNode *createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V) {
204 LLVMContext &Context = TheLoop->getHeader()->getContext();
205 Metadata *MDs[] = {
207 ConstantAsMetadata::get(ConstantInt::get(Type::getInt32Ty(Context), V))};
208 return MDNode::get(Context, MDs);
209}
210
211/// Set input string into loop metadata by keeping other values intact.
212/// If the string is already in loop metadata update value if it is
213/// different.
214void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *StringMD,
215 unsigned V) {
217 // If the loop already has metadata, retain it.
218 MDNode *LoopID = TheLoop->getLoopID();
219 if (LoopID) {
220 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
221 MDNode *Node = cast<MDNode>(LoopID->getOperand(i));
222 // If it is of form key = value, try to parse it.
223 if (Node->getNumOperands() == 2) {
224 MDString *S = dyn_cast<MDString>(Node->getOperand(0));
225 if (S && S->getString().equals(StringMD)) {
226 ConstantInt *IntMD =
227 mdconst::extract_or_null<ConstantInt>(Node->getOperand(1));
228 if (IntMD && IntMD->getSExtValue() == V)
229 // It is already in place. Do nothing.
230 return;
231 // We need to update the value, so just skip it here and it will
232 // be added after copying other existed nodes.
233 continue;
234 }
235 }
236 MDs.push_back(Node);
237 }
238 }
239 // Add new metadata.
240 MDs.push_back(createStringMetadata(TheLoop, StringMD, V));
241 // Replace current metadata node with new one.
242 LLVMContext &Context = TheLoop->getHeader()->getContext();
243 MDNode *NewLoopID = MDNode::get(Context, MDs);
244 // Set operand 0 to refer to the loop id itself.
245 NewLoopID->replaceOperandWith(0, NewLoopID);
246 TheLoop->setLoopID(NewLoopID);
247}
248
249std::optional<ElementCount>
251 std::optional<int> Width =
252 getOptionalIntLoopAttribute(TheLoop, "llvm.loop.vectorize.width");
253
254 if (Width) {
255 std::optional<int> IsScalable = getOptionalIntLoopAttribute(
256 TheLoop, "llvm.loop.vectorize.scalable.enable");
257 return ElementCount::get(*Width, IsScalable.value_or(false));
258 }
259
260 return std::nullopt;
261}
262
263std::optional<MDNode *> llvm::makeFollowupLoopID(
264 MDNode *OrigLoopID, ArrayRef<StringRef> FollowupOptions,
265 const char *InheritOptionsExceptPrefix, bool AlwaysNew) {
266 if (!OrigLoopID) {
267 if (AlwaysNew)
268 return nullptr;
269 return std::nullopt;
270 }
271
272 assert(OrigLoopID->getOperand(0) == OrigLoopID);
273
274 bool InheritAllAttrs = !InheritOptionsExceptPrefix;
275 bool InheritSomeAttrs =
276 InheritOptionsExceptPrefix && InheritOptionsExceptPrefix[0] != '\0';
278 MDs.push_back(nullptr);
279
280 bool Changed = false;
281 if (InheritAllAttrs || InheritSomeAttrs) {
282 for (const MDOperand &Existing : drop_begin(OrigLoopID->operands())) {
283 MDNode *Op = cast<MDNode>(Existing.get());
284
285 auto InheritThisAttribute = [InheritSomeAttrs,
286 InheritOptionsExceptPrefix](MDNode *Op) {
287 if (!InheritSomeAttrs)
288 return false;
289
290 // Skip malformatted attribute metadata nodes.
291 if (Op->getNumOperands() == 0)
292 return true;
293 Metadata *NameMD = Op->getOperand(0).get();
294 if (!isa<MDString>(NameMD))
295 return true;
296 StringRef AttrName = cast<MDString>(NameMD)->getString();
297
298 // Do not inherit excluded attributes.
299 return !AttrName.starts_with(InheritOptionsExceptPrefix);
300 };
301
302 if (InheritThisAttribute(Op))
303 MDs.push_back(Op);
304 else
305 Changed = true;
306 }
307 } else {
308 // Modified if we dropped at least one attribute.
309 Changed = OrigLoopID->getNumOperands() > 1;
310 }
311
312 bool HasAnyFollowup = false;
313 for (StringRef OptionName : FollowupOptions) {
314 MDNode *FollowupNode = findOptionMDForLoopID(OrigLoopID, OptionName);
315 if (!FollowupNode)
316 continue;
317
318 HasAnyFollowup = true;
319 for (const MDOperand &Option : drop_begin(FollowupNode->operands())) {
320 MDs.push_back(Option.get());
321 Changed = true;
322 }
323 }
324
325 // Attributes of the followup loop not specified explicity, so signal to the
326 // transformation pass to add suitable attributes.
327 if (!AlwaysNew && !HasAnyFollowup)
328 return std::nullopt;
329
330 // If no attributes were added or remove, the previous loop Id can be reused.
331 if (!AlwaysNew && !Changed)
332 return OrigLoopID;
333
334 // No attributes is equivalent to having no !llvm.loop metadata at all.
335 if (MDs.size() == 1)
336 return nullptr;
337
338 // Build the new loop ID.
339 MDTuple *FollowupLoopID = MDNode::get(OrigLoopID->getContext(), MDs);
340 FollowupLoopID->replaceOperandWith(0, FollowupLoopID);
341 return FollowupLoopID;
342}
343
346}
347
350}
351
353 if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable"))
354 return TM_SuppressedByUser;
355
356 std::optional<int> Count =
357 getOptionalIntLoopAttribute(L, "llvm.loop.unroll.count");
358 if (Count)
359 return *Count == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
360
361 if (getBooleanLoopAttribute(L, "llvm.loop.unroll.enable"))
362 return TM_ForcedByUser;
363
364 if (getBooleanLoopAttribute(L, "llvm.loop.unroll.full"))
365 return TM_ForcedByUser;
366
368 return TM_Disable;
369
370 return TM_Unspecified;
371}
372
374 if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.disable"))
375 return TM_SuppressedByUser;
376
377 std::optional<int> Count =
378 getOptionalIntLoopAttribute(L, "llvm.loop.unroll_and_jam.count");
379 if (Count)
380 return *Count == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
381
382 if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.enable"))
383 return TM_ForcedByUser;
384
386 return TM_Disable;
387
388 return TM_Unspecified;
389}
390
392 std::optional<bool> Enable =
393 getOptionalBoolLoopAttribute(L, "llvm.loop.vectorize.enable");
394
395 if (Enable == false)
396 return TM_SuppressedByUser;
397
398 std::optional<ElementCount> VectorizeWidth =
400 std::optional<int> InterleaveCount =
401 getOptionalIntLoopAttribute(L, "llvm.loop.interleave.count");
402
403 // 'Forcing' vector width and interleave count to one effectively disables
404 // this tranformation.
405 if (Enable == true && VectorizeWidth && VectorizeWidth->isScalar() &&
406 InterleaveCount == 1)
407 return TM_SuppressedByUser;
408
409 if (getBooleanLoopAttribute(L, "llvm.loop.isvectorized"))
410 return TM_Disable;
411
412 if (Enable == true)
413 return TM_ForcedByUser;
414
415 if ((VectorizeWidth && VectorizeWidth->isScalar()) && InterleaveCount == 1)
416 return TM_Disable;
417
418 if ((VectorizeWidth && VectorizeWidth->isVector()) || InterleaveCount > 1)
419 return TM_Enable;
420
422 return TM_Disable;
423
424 return TM_Unspecified;
425}
426
428 if (getBooleanLoopAttribute(L, "llvm.loop.distribute.enable"))
429 return TM_ForcedByUser;
430
432 return TM_Disable;
433
434 return TM_Unspecified;
435}
436
438 if (getBooleanLoopAttribute(L, "llvm.loop.licm_versioning.disable"))
439 return TM_SuppressedByUser;
440
442 return TM_Disable;
443
444 return TM_Unspecified;
445}
446
447/// Does a BFS from a given node to all of its children inside a given loop.
448/// The returned vector of nodes includes the starting point.
452 auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
453 // Only include subregions in the top level loop.
454 BasicBlock *BB = DTN->getBlock();
455 if (CurLoop->contains(BB))
456 Worklist.push_back(DTN);
457 };
458
459 AddRegionToWorklist(N);
460
461 for (size_t I = 0; I < Worklist.size(); I++) {
462 for (DomTreeNode *Child : Worklist[I]->children())
463 AddRegionToWorklist(Child);
464 }
465
466 return Worklist;
467}
468
470 int LatchIdx = PN->getBasicBlockIndex(LatchBlock);
471 assert(LatchIdx != -1 && "LatchBlock is not a case in this PHINode");
472 Value *IncV = PN->getIncomingValue(LatchIdx);
473
474 for (User *U : PN->users())
475 if (U != Cond && U != IncV) return false;
476
477 for (User *U : IncV->users())
478 if (U != Cond && U != PN) return false;
479 return true;
480}
481
482
484 LoopInfo *LI, MemorySSA *MSSA) {
485 assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
486 auto *Preheader = L->getLoopPreheader();
487 assert(Preheader && "Preheader should exist!");
488
489 std::unique_ptr<MemorySSAUpdater> MSSAU;
490 if (MSSA)
491 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
492
493 // Now that we know the removal is safe, remove the loop by changing the
494 // branch from the preheader to go to the single exit block.
495 //
496 // Because we're deleting a large chunk of code at once, the sequence in which
497 // we remove things is very important to avoid invalidation issues.
498
499 // Tell ScalarEvolution that the loop is deleted. Do this before
500 // deleting the loop so that ScalarEvolution can look at the loop
501 // to determine what it needs to clean up.
502 if (SE) {
503 SE->forgetLoop(L);
505 }
506
507 Instruction *OldTerm = Preheader->getTerminator();
508 assert(!OldTerm->mayHaveSideEffects() &&
509 "Preheader must end with a side-effect-free terminator");
510 assert(OldTerm->getNumSuccessors() == 1 &&
511 "Preheader must have a single successor");
512 // Connect the preheader to the exit block. Keep the old edge to the header
513 // around to perform the dominator tree update in two separate steps
514 // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
515 // preheader -> header.
516 //
517 //
518 // 0. Preheader 1. Preheader 2. Preheader
519 // | | | |
520 // V | V |
521 // Header <--\ | Header <--\ | Header <--\
522 // | | | | | | | | | | |
523 // | V | | | V | | | V |
524 // | Body --/ | | Body --/ | | Body --/
525 // V V V V V
526 // Exit Exit Exit
527 //
528 // By doing this is two separate steps we can perform the dominator tree
529 // update without using the batch update API.
530 //
531 // Even when the loop is never executed, we cannot remove the edge from the
532 // source block to the exit block. Consider the case where the unexecuted loop
533 // branches back to an outer loop. If we deleted the loop and removed the edge
534 // coming to this inner loop, this will break the outer loop structure (by
535 // deleting the backedge of the outer loop). If the outer loop is indeed a
536 // non-loop, it will be deleted in a future iteration of loop deletion pass.
537 IRBuilder<> Builder(OldTerm);
538
539 auto *ExitBlock = L->getUniqueExitBlock();
540 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
541 if (ExitBlock) {
542 assert(ExitBlock && "Should have a unique exit block!");
543 assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
544
545 Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
546 // Remove the old branch. The conditional branch becomes a new terminator.
547 OldTerm->eraseFromParent();
548
549 // Rewrite phis in the exit block to get their inputs from the Preheader
550 // instead of the exiting block.
551 for (PHINode &P : ExitBlock->phis()) {
552 // Set the zero'th element of Phi to be from the preheader and remove all
553 // other incoming values. Given the loop has dedicated exits, all other
554 // incoming values must be from the exiting blocks.
555 int PredIndex = 0;
556 P.setIncomingBlock(PredIndex, Preheader);
557 // Removes all incoming values from all other exiting blocks (including
558 // duplicate values from an exiting block).
559 // Nuke all entries except the zero'th entry which is the preheader entry.
560 P.removeIncomingValueIf([](unsigned Idx) { return Idx != 0; },
561 /* DeletePHIIfEmpty */ false);
562
563 assert((P.getNumIncomingValues() == 1 &&
564 P.getIncomingBlock(PredIndex) == Preheader) &&
565 "Should have exactly one value and that's from the preheader!");
566 }
567
568 if (DT) {
569 DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}});
570 if (MSSA) {
571 MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}},
572 *DT);
573 if (VerifyMemorySSA)
574 MSSA->verifyMemorySSA();
575 }
576 }
577
578 // Disconnect the loop body by branching directly to its exit.
579 Builder.SetInsertPoint(Preheader->getTerminator());
580 Builder.CreateBr(ExitBlock);
581 // Remove the old branch.
582 Preheader->getTerminator()->eraseFromParent();
583 } else {
584 assert(L->hasNoExitBlocks() &&
585 "Loop should have either zero or one exit blocks.");
586
587 Builder.SetInsertPoint(OldTerm);
588 Builder.CreateUnreachable();
589 Preheader->getTerminator()->eraseFromParent();
590 }
591
592 if (DT) {
593 DTU.applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}});
594 if (MSSA) {
595 MSSAU->applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}},
596 *DT);
597 SmallSetVector<BasicBlock *, 8> DeadBlockSet(L->block_begin(),
598 L->block_end());
599 MSSAU->removeBlocks(DeadBlockSet);
600 if (VerifyMemorySSA)
601 MSSA->verifyMemorySSA();
602 }
603 }
604
605 // Use a map to unique and a vector to guarantee deterministic ordering.
608 llvm::SmallVector<DbgVariableRecord *, 4> DeadDbgVariableRecords;
609
610 if (ExitBlock) {
611 // Given LCSSA form is satisfied, we should not have users of instructions
612 // within the dead loop outside of the loop. However, LCSSA doesn't take
613 // unreachable uses into account. We handle them here.
614 // We could do it after drop all references (in this case all users in the
615 // loop will be already eliminated and we have less work to do but according
616 // to API doc of User::dropAllReferences only valid operation after dropping
617 // references, is deletion. So let's substitute all usages of
618 // instruction from the loop with poison value of corresponding type first.
619 for (auto *Block : L->blocks())
620 for (Instruction &I : *Block) {
621 auto *Poison = PoisonValue::get(I.getType());
622 for (Use &U : llvm::make_early_inc_range(I.uses())) {
623 if (auto *Usr = dyn_cast<Instruction>(U.getUser()))
624 if (L->contains(Usr->getParent()))
625 continue;
626 // If we have a DT then we can check that uses outside a loop only in
627 // unreachable block.
628 if (DT)
630 "Unexpected user in reachable block");
631 U.set(Poison);
632 }
633
634 // RemoveDIs: do the same as below for DbgVariableRecords.
635 if (Block->IsNewDbgInfoFormat) {
637 filterDbgVars(I.getDbgRecordRange()))) {
638 DebugVariable Key(DVR.getVariable(), DVR.getExpression(),
639 DVR.getDebugLoc().get());
640 if (!DeadDebugSet.insert(Key).second)
641 continue;
642 // Unlinks the DVR from it's container, for later insertion.
643 DVR.removeFromParent();
644 DeadDbgVariableRecords.push_back(&DVR);
645 }
646 }
647
648 // For one of each variable encountered, preserve a debug intrinsic (set
649 // to Poison) and transfer it to the loop exit. This terminates any
650 // variable locations that were set during the loop.
651 auto *DVI = dyn_cast<DbgVariableIntrinsic>(&I);
652 if (!DVI)
653 continue;
654 if (!DeadDebugSet.insert(DebugVariable(DVI)).second)
655 continue;
656 DeadDebugInst.push_back(DVI);
657 }
658
659 // After the loop has been deleted all the values defined and modified
660 // inside the loop are going to be unavailable. Values computed in the
661 // loop will have been deleted, automatically causing their debug uses
662 // be be replaced with undef. Loop invariant values will still be available.
663 // Move dbg.values out the loop so that earlier location ranges are still
664 // terminated and loop invariant assignments are preserved.
665 DIBuilder DIB(*ExitBlock->getModule());
666 BasicBlock::iterator InsertDbgValueBefore =
667 ExitBlock->getFirstInsertionPt();
668 assert(InsertDbgValueBefore != ExitBlock->end() &&
669 "There should be a non-PHI instruction in exit block, else these "
670 "instructions will have no parent.");
671
672 for (auto *DVI : DeadDebugInst)
673 DVI->moveBefore(*ExitBlock, InsertDbgValueBefore);
674
675 // Due to the "head" bit in BasicBlock::iterator, we're going to insert
676 // each DbgVariableRecord right at the start of the block, wheras dbg.values
677 // would be repeatedly inserted before the first instruction. To replicate
678 // this behaviour, do it backwards.
679 for (DbgVariableRecord *DVR : llvm::reverse(DeadDbgVariableRecords))
680 ExitBlock->insertDbgRecordBefore(DVR, InsertDbgValueBefore);
681 }
682
683 // Remove the block from the reference counting scheme, so that we can
684 // delete it freely later.
685 for (auto *Block : L->blocks())
686 Block->dropAllReferences();
687
688 if (MSSA && VerifyMemorySSA)
689 MSSA->verifyMemorySSA();
690
691 if (LI) {
692 // Erase the instructions and the blocks without having to worry
693 // about ordering because we already dropped the references.
694 // NOTE: This iteration is safe because erasing the block does not remove
695 // its entry from the loop's block list. We do that in the next section.
696 for (BasicBlock *BB : L->blocks())
697 BB->eraseFromParent();
698
699 // Finally, the blocks from loopinfo. This has to happen late because
700 // otherwise our loop iterators won't work.
701
703 blocks.insert(L->block_begin(), L->block_end());
704 for (BasicBlock *BB : blocks)
705 LI->removeBlock(BB);
706
707 // The last step is to update LoopInfo now that we've eliminated this loop.
708 // Note: LoopInfo::erase remove the given loop and relink its subloops with
709 // its parent. While removeLoop/removeChildLoop remove the given loop but
710 // not relink its subloops, which is what we want.
711 if (Loop *ParentLoop = L->getParentLoop()) {
712 Loop::iterator I = find(*ParentLoop, L);
713 assert(I != ParentLoop->end() && "Couldn't find loop");
714 ParentLoop->removeChildLoop(I);
715 } else {
716 Loop::iterator I = find(*LI, L);
717 assert(I != LI->end() && "Couldn't find loop");
718 LI->removeLoop(I);
719 }
720 LI->destroy(L);
721 }
722}
723
725 LoopInfo &LI, MemorySSA *MSSA) {
726 auto *Latch = L->getLoopLatch();
727 assert(Latch && "multiple latches not yet supported");
728 auto *Header = L->getHeader();
729 Loop *OutermostLoop = L->getOutermostLoop();
730
731 SE.forgetLoop(L);
733
734 std::unique_ptr<MemorySSAUpdater> MSSAU;
735 if (MSSA)
736 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
737
738 // Update the CFG and domtree. We chose to special case a couple of
739 // of common cases for code quality and test readability reasons.
740 [&]() -> void {
741 if (auto *BI = dyn_cast<BranchInst>(Latch->getTerminator())) {
742 if (!BI->isConditional()) {
743 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Eager);
744 (void)changeToUnreachable(BI, /*PreserveLCSSA*/ true, &DTU,
745 MSSAU.get());
746 return;
747 }
748
749 // Conditional latch/exit - note that latch can be shared by inner
750 // and outer loop so the other target doesn't need to an exit
751 if (L->isLoopExiting(Latch)) {
752 // TODO: Generalize ConstantFoldTerminator so that it can be used
753 // here without invalidating LCSSA or MemorySSA. (Tricky case for
754 // LCSSA: header is an exit block of a preceeding sibling loop w/o
755 // dedicated exits.)
756 const unsigned ExitIdx = L->contains(BI->getSuccessor(0)) ? 1 : 0;
757 BasicBlock *ExitBB = BI->getSuccessor(ExitIdx);
758
759 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Eager);
760 Header->removePredecessor(Latch, true);
761
762 IRBuilder<> Builder(BI);
763 auto *NewBI = Builder.CreateBr(ExitBB);
764 // Transfer the metadata to the new branch instruction (minus the
765 // loop info since this is no longer a loop)
766 NewBI->copyMetadata(*BI, {LLVMContext::MD_dbg,
767 LLVMContext::MD_annotation});
768
769 BI->eraseFromParent();
770 DTU.applyUpdates({{DominatorTree::Delete, Latch, Header}});
771 if (MSSA)
772 MSSAU->applyUpdates({{DominatorTree::Delete, Latch, Header}}, DT);
773 return;
774 }
775 }
776
777 // General case. By splitting the backedge, and then explicitly making it
778 // unreachable we gracefully handle corner cases such as switch and invoke
779 // termiantors.
780 auto *BackedgeBB = SplitEdge(Latch, Header, &DT, &LI, MSSAU.get());
781
782 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Eager);
783 (void)changeToUnreachable(BackedgeBB->getTerminator(),
784 /*PreserveLCSSA*/ true, &DTU, MSSAU.get());
785 }();
786
787 // Erase (and destroy) this loop instance. Handles relinking sub-loops
788 // and blocks within the loop as needed.
789 LI.erase(L);
790
791 // If the loop we broke had a parent, then changeToUnreachable might have
792 // caused a block to be removed from the parent loop (see loop_nest_lcssa
793 // test case in zero-btc.ll for an example), thus changing the parent's
794 // exit blocks. If that happened, we need to rebuild LCSSA on the outermost
795 // loop which might have a had a block removed.
796 if (OutermostLoop != L)
797 formLCSSARecursively(*OutermostLoop, DT, &LI, &SE);
798}
799
800
801/// Checks if \p L has an exiting latch branch. There may also be other
802/// exiting blocks. Returns branch instruction terminating the loop
803/// latch if above check is successful, nullptr otherwise.
805 BasicBlock *Latch = L->getLoopLatch();
806 if (!Latch)
807 return nullptr;
808
809 BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator());
810 if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
811 return nullptr;
812
813 assert((LatchBR->getSuccessor(0) == L->getHeader() ||
814 LatchBR->getSuccessor(1) == L->getHeader()) &&
815 "At least one edge out of the latch must go to the header");
816
817 return LatchBR;
818}
819
820/// Return the estimated trip count for any exiting branch which dominates
821/// the loop latch.
822static std::optional<uint64_t> getEstimatedTripCount(BranchInst *ExitingBranch,
823 Loop *L,
824 uint64_t &OrigExitWeight) {
825 // To estimate the number of times the loop body was executed, we want to
826 // know the number of times the backedge was taken, vs. the number of times
827 // we exited the loop.
828 uint64_t LoopWeight, ExitWeight;
829 if (!extractBranchWeights(*ExitingBranch, LoopWeight, ExitWeight))
830 return std::nullopt;
831
832 if (L->contains(ExitingBranch->getSuccessor(1)))
833 std::swap(LoopWeight, ExitWeight);
834
835 if (!ExitWeight)
836 // Don't have a way to return predicated infinite
837 return std::nullopt;
838
839 OrigExitWeight = ExitWeight;
840
841 // Estimated exit count is a ratio of the loop weight by the weight of the
842 // edge exiting the loop, rounded to nearest.
843 uint64_t ExitCount = llvm::divideNearest(LoopWeight, ExitWeight);
844 // Estimated trip count is one plus estimated exit count.
845 return ExitCount + 1;
846}
847
848std::optional<unsigned>
850 unsigned *EstimatedLoopInvocationWeight) {
851 // Currently we take the estimate exit count only from the loop latch,
852 // ignoring other exiting blocks. This can overestimate the trip count
853 // if we exit through another exit, but can never underestimate it.
854 // TODO: incorporate information from other exits
855 if (BranchInst *LatchBranch = getExpectedExitLoopLatchBranch(L)) {
856 uint64_t ExitWeight;
857 if (std::optional<uint64_t> EstTripCount =
858 getEstimatedTripCount(LatchBranch, L, ExitWeight)) {
859 if (EstimatedLoopInvocationWeight)
860 *EstimatedLoopInvocationWeight = ExitWeight;
861 return *EstTripCount;
862 }
863 }
864 return std::nullopt;
865}
866
867bool llvm::setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount,
868 unsigned EstimatedloopInvocationWeight) {
869 // At the moment, we currently support changing the estimate trip count of
870 // the latch branch only. We could extend this API to manipulate estimated
871 // trip counts for any exit.
873 if (!LatchBranch)
874 return false;
875
876 // Calculate taken and exit weights.
877 unsigned LatchExitWeight = 0;
878 unsigned BackedgeTakenWeight = 0;
879
880 if (EstimatedTripCount > 0) {
881 LatchExitWeight = EstimatedloopInvocationWeight;
882 BackedgeTakenWeight = (EstimatedTripCount - 1) * LatchExitWeight;
883 }
884
885 // Make a swap if back edge is taken when condition is "false".
886 if (LatchBranch->getSuccessor(0) != L->getHeader())
887 std::swap(BackedgeTakenWeight, LatchExitWeight);
888
889 MDBuilder MDB(LatchBranch->getContext());
890
891 // Set/Update profile metadata.
892 LatchBranch->setMetadata(
893 LLVMContext::MD_prof,
894 MDB.createBranchWeights(BackedgeTakenWeight, LatchExitWeight));
895
896 return true;
897}
898
900 ScalarEvolution &SE) {
901 Loop *OuterL = InnerLoop->getParentLoop();
902 if (!OuterL)
903 return true;
904
905 // Get the backedge taken count for the inner loop
906 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
907 const SCEV *InnerLoopBECountSC = SE.getExitCount(InnerLoop, InnerLoopLatch);
908 if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
909 !InnerLoopBECountSC->getType()->isIntegerTy())
910 return false;
911
912 // Get whether count is invariant to the outer loop
914 SE.getLoopDisposition(InnerLoopBECountSC, OuterL);
916 return false;
917
918 return true;
919}
920
922 switch (RdxID) {
923 case Intrinsic::vector_reduce_fadd:
924 return Instruction::FAdd;
925 case Intrinsic::vector_reduce_fmul:
926 return Instruction::FMul;
927 case Intrinsic::vector_reduce_add:
928 return Instruction::Add;
929 case Intrinsic::vector_reduce_mul:
930 return Instruction::Mul;
931 case Intrinsic::vector_reduce_and:
932 return Instruction::And;
933 case Intrinsic::vector_reduce_or:
934 return Instruction::Or;
935 case Intrinsic::vector_reduce_xor:
936 return Instruction::Xor;
937 case Intrinsic::vector_reduce_smax:
938 case Intrinsic::vector_reduce_smin:
939 case Intrinsic::vector_reduce_umax:
940 case Intrinsic::vector_reduce_umin:
941 return Instruction::ICmp;
942 case Intrinsic::vector_reduce_fmax:
943 case Intrinsic::vector_reduce_fmin:
944 return Instruction::FCmp;
945 default:
946 llvm_unreachable("Unexpected ID");
947 }
948}
949
951 switch (RdxID) {
952 default:
953 llvm_unreachable("Unknown min/max recurrence kind");
954 case Intrinsic::vector_reduce_umin:
955 return Intrinsic::umin;
956 case Intrinsic::vector_reduce_umax:
957 return Intrinsic::umax;
958 case Intrinsic::vector_reduce_smin:
959 return Intrinsic::smin;
960 case Intrinsic::vector_reduce_smax:
961 return Intrinsic::smax;
962 case Intrinsic::vector_reduce_fmin:
963 return Intrinsic::minnum;
964 case Intrinsic::vector_reduce_fmax:
965 return Intrinsic::maxnum;
966 case Intrinsic::vector_reduce_fminimum:
967 return Intrinsic::minimum;
968 case Intrinsic::vector_reduce_fmaximum:
969 return Intrinsic::maximum;
970 }
971}
972
974 switch (RK) {
975 default:
976 llvm_unreachable("Unknown min/max recurrence kind");
977 case RecurKind::UMin:
978 return Intrinsic::umin;
979 case RecurKind::UMax:
980 return Intrinsic::umax;
981 case RecurKind::SMin:
982 return Intrinsic::smin;
983 case RecurKind::SMax:
984 return Intrinsic::smax;
985 case RecurKind::FMin:
986 return Intrinsic::minnum;
987 case RecurKind::FMax:
988 return Intrinsic::maxnum;
989 case RecurKind::FMinimum:
990 return Intrinsic::minimum;
991 case RecurKind::FMaximum:
992 return Intrinsic::maximum;
993 }
994}
995
997 switch (RdxID) {
998 case Intrinsic::vector_reduce_smax:
999 return RecurKind::SMax;
1000 case Intrinsic::vector_reduce_smin:
1001 return RecurKind::SMin;
1002 case Intrinsic::vector_reduce_umax:
1003 return RecurKind::UMax;
1004 case Intrinsic::vector_reduce_umin:
1005 return RecurKind::UMin;
1006 case Intrinsic::vector_reduce_fmax:
1007 return RecurKind::FMax;
1008 case Intrinsic::vector_reduce_fmin:
1009 return RecurKind::FMin;
1010 default:
1011 return RecurKind::None;
1012 }
1013}
1014
1016 switch (RK) {
1017 default:
1018 llvm_unreachable("Unknown min/max recurrence kind");
1019 case RecurKind::UMin:
1020 return CmpInst::ICMP_ULT;
1021 case RecurKind::UMax:
1022 return CmpInst::ICMP_UGT;
1023 case RecurKind::SMin:
1024 return CmpInst::ICMP_SLT;
1025 case RecurKind::SMax:
1026 return CmpInst::ICMP_SGT;
1027 case RecurKind::FMin:
1028 return CmpInst::FCMP_OLT;
1029 case RecurKind::FMax:
1030 return CmpInst::FCMP_OGT;
1031 // We do not add FMinimum/FMaximum recurrence kind here since there is no
1032 // equivalent predicate which compares signed zeroes according to the
1033 // semantics of the intrinsics (llvm.minimum/maximum).
1034 }
1035}
1036
1038 RecurKind RK, Value *Left, Value *Right) {
1039 if (auto VTy = dyn_cast<VectorType>(Left->getType()))
1040 StartVal = Builder.CreateVectorSplat(VTy->getElementCount(), StartVal);
1041 Value *Cmp =
1042 Builder.CreateCmp(CmpInst::ICMP_NE, Left, StartVal, "rdx.select.cmp");
1043 return Builder.CreateSelect(Cmp, Left, Right, "rdx.select");
1044}
1045
1047 Value *Right) {
1048 Type *Ty = Left->getType();
1049 if (Ty->isIntOrIntVectorTy() ||
1050 (RK == RecurKind::FMinimum || RK == RecurKind::FMaximum)) {
1051 // TODO: Add float minnum/maxnum support when FMF nnan is set.
1053 return Builder.CreateIntrinsic(Ty, Id, {Left, Right}, nullptr,
1054 "rdx.minmax");
1055 }
1057 Value *Cmp = Builder.CreateCmp(Pred, Left, Right, "rdx.minmax.cmp");
1058 Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
1059 return Select;
1060}
1061
1062// Helper to generate an ordered reduction.
1064 unsigned Op, RecurKind RdxKind) {
1065 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
1066
1067 // Extract and apply reduction ops in ascending order:
1068 // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
1069 Value *Result = Acc;
1070 for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
1071 Value *Ext =
1072 Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx));
1073
1074 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1075 Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext,
1076 "bin.rdx");
1077 } else {
1079 "Invalid min/max");
1080 Result = createMinMaxOp(Builder, RdxKind, Result, Ext);
1081 }
1082 }
1083
1084 return Result;
1085}
1086
1087// Helper to generate a log2 shuffle reduction.
1089 unsigned Op, RecurKind RdxKind) {
1090 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
1091 // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
1092 // and vector ops, reducing the set of values being computed by half each
1093 // round.
1094 assert(isPowerOf2_32(VF) &&
1095 "Reduction emission only supported for pow2 vectors!");
1096 // Note: fast-math-flags flags are controlled by the builder configuration
1097 // and are assumed to apply to all generated arithmetic instructions. Other
1098 // poison generating flags (nsw/nuw/inbounds/inrange/exact) are not part
1099 // of the builder configuration, and since they're not passed explicitly,
1100 // will never be relevant here. Note that it would be generally unsound to
1101 // propagate these from an intrinsic call to the expansion anyways as we/
1102 // change the order of operations.
1103 Value *TmpVec = Src;
1104 SmallVector<int, 32> ShuffleMask(VF);
1105 for (unsigned i = VF; i != 1; i >>= 1) {
1106 // Move the upper half of the vector to the lower half.
1107 for (unsigned j = 0; j != i / 2; ++j)
1108 ShuffleMask[j] = i / 2 + j;
1109
1110 // Fill the rest of the mask with undef.
1111 std::fill(&ShuffleMask[i / 2], ShuffleMask.end(), -1);
1112
1113 Value *Shuf = Builder.CreateShuffleVector(TmpVec, ShuffleMask, "rdx.shuf");
1114
1115 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1116 TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf,
1117 "bin.rdx");
1118 } else {
1120 "Invalid min/max");
1121 TmpVec = createMinMaxOp(Builder, RdxKind, TmpVec, Shuf);
1122 }
1123 }
1124 // The result is in the first element of the vector.
1125 return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
1126}
1127
1130 PHINode *OrigPhi) {
1131 assert(
1133 "Unexpected reduction kind");
1134 Value *InitVal = Desc.getRecurrenceStartValue();
1135 Value *NewVal = nullptr;
1136
1137 // First use the original phi to determine the new value we're trying to
1138 // select from in the loop.
1139 SelectInst *SI = nullptr;
1140 for (auto *U : OrigPhi->users()) {
1141 if ((SI = dyn_cast<SelectInst>(U)))
1142 break;
1143 }
1144 assert(SI && "One user of the original phi should be a select");
1145
1146 if (SI->getTrueValue() == OrigPhi)
1147 NewVal = SI->getFalseValue();
1148 else {
1149 assert(SI->getFalseValue() == OrigPhi &&
1150 "At least one input to the select should be the original Phi");
1151 NewVal = SI->getTrueValue();
1152 }
1153
1154 // Create a splat vector with the new value and compare this to the vector
1155 // we want to reduce.
1156 ElementCount EC = cast<VectorType>(Src->getType())->getElementCount();
1157 Value *Right = Builder.CreateVectorSplat(EC, InitVal);
1158 Value *Cmp =
1159 Builder.CreateCmp(CmpInst::ICMP_NE, Src, Right, "rdx.select.cmp");
1160
1161 // If any predicate is true it means that we want to select the new value.
1162 Cmp = Builder.CreateOrReduce(Cmp);
1163 return Builder.CreateSelect(Cmp, NewVal, InitVal, "rdx.select");
1164}
1165
1167 RecurKind RdxKind) {
1168 auto *SrcVecEltTy = cast<VectorType>(Src->getType())->getElementType();
1169 switch (RdxKind) {
1170 case RecurKind::Add:
1171 return Builder.CreateAddReduce(Src);
1172 case RecurKind::Mul:
1173 return Builder.CreateMulReduce(Src);
1174 case RecurKind::And:
1175 return Builder.CreateAndReduce(Src);
1176 case RecurKind::Or:
1177 return Builder.CreateOrReduce(Src);
1178 case RecurKind::Xor:
1179 return Builder.CreateXorReduce(Src);
1180 case RecurKind::FMulAdd:
1181 case RecurKind::FAdd:
1182 return Builder.CreateFAddReduce(ConstantFP::getNegativeZero(SrcVecEltTy),
1183 Src);
1184 case RecurKind::FMul:
1185 return Builder.CreateFMulReduce(ConstantFP::get(SrcVecEltTy, 1.0), Src);
1186 case RecurKind::SMax:
1187 return Builder.CreateIntMaxReduce(Src, true);
1188 case RecurKind::SMin:
1189 return Builder.CreateIntMinReduce(Src, true);
1190 case RecurKind::UMax:
1191 return Builder.CreateIntMaxReduce(Src, false);
1192 case RecurKind::UMin:
1193 return Builder.CreateIntMinReduce(Src, false);
1194 case RecurKind::FMax:
1195 return Builder.CreateFPMaxReduce(Src);
1196 case RecurKind::FMin:
1197 return Builder.CreateFPMinReduce(Src);
1198 case RecurKind::FMinimum:
1199 return Builder.CreateFPMinimumReduce(Src);
1200 case RecurKind::FMaximum:
1201 return Builder.CreateFPMaximumReduce(Src);
1202 default:
1203 llvm_unreachable("Unhandled opcode");
1204 }
1205}
1206
1208 const RecurrenceDescriptor &Desc, Value *Src,
1209 PHINode *OrigPhi) {
1210 // TODO: Support in-order reductions based on the recurrence descriptor.
1211 // All ops in the reduction inherit fast-math-flags from the recurrence
1212 // descriptor.
1214 B.setFastMathFlags(Desc.getFastMathFlags());
1215
1216 RecurKind RK = Desc.getRecurrenceKind();
1218 return createAnyOfTargetReduction(B, Src, Desc, OrigPhi);
1219
1220 return createSimpleTargetReduction(B, Src, RK);
1221}
1222
1225 Value *Src, Value *Start) {
1226 assert((Desc.getRecurrenceKind() == RecurKind::FAdd ||
1227 Desc.getRecurrenceKind() == RecurKind::FMulAdd) &&
1228 "Unexpected reduction kind");
1229 assert(Src->getType()->isVectorTy() && "Expected a vector type");
1230 assert(!Start->getType()->isVectorTy() && "Expected a scalar type");
1231
1232 return B.CreateFAddReduce(Start, Src);
1233}
1234
1236 bool IncludeWrapFlags) {
1237 auto *VecOp = dyn_cast<Instruction>(I);
1238 if (!VecOp)
1239 return;
1240 auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
1241 : dyn_cast<Instruction>(OpValue);
1242 if (!Intersection)
1243 return;
1244 const unsigned Opcode = Intersection->getOpcode();
1245 VecOp->copyIRFlags(Intersection, IncludeWrapFlags);
1246 for (auto *V : VL) {
1247 auto *Instr = dyn_cast<Instruction>(V);
1248 if (!Instr)
1249 continue;
1250 if (OpValue == nullptr || Opcode == Instr->getOpcode())
1251 VecOp->andIRFlags(V);
1252 }
1253}
1254
1255bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L,
1256 ScalarEvolution &SE) {
1257 const SCEV *Zero = SE.getZero(S->getType());
1258 return SE.isAvailableAtLoopEntry(S, L) &&
1259 SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, S, Zero);
1260}
1261
1263 ScalarEvolution &SE) {
1264 const SCEV *Zero = SE.getZero(S->getType());
1265 return SE.isAvailableAtLoopEntry(S, L) &&
1266 SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, S, Zero);
1267}
1268
1269bool llvm::isKnownPositiveInLoop(const SCEV *S, const Loop *L,
1270 ScalarEvolution &SE) {
1271 const SCEV *Zero = SE.getZero(S->getType());
1272 return SE.isAvailableAtLoopEntry(S, L) &&
1273 SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGT, S, Zero);
1274}
1275
1277 ScalarEvolution &SE) {
1278 const SCEV *Zero = SE.getZero(S->getType());
1279 return SE.isAvailableAtLoopEntry(S, L) &&
1280 SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLE, S, Zero);
1281}
1282
1284 bool Signed) {
1285 unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1288 auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1289 return SE.isAvailableAtLoopEntry(S, L) &&
1290 SE.isLoopEntryGuardedByCond(L, Predicate, S,
1291 SE.getConstant(Min));
1292}
1293
1295 bool Signed) {
1296 unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1299 auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1300 return SE.isAvailableAtLoopEntry(S, L) &&
1301 SE.isLoopEntryGuardedByCond(L, Predicate, S,
1302 SE.getConstant(Max));
1303}
1304
1305//===----------------------------------------------------------------------===//
1306// rewriteLoopExitValues - Optimize IV users outside the loop.
1307// As a side effect, reduces the amount of IV processing within the loop.
1308//===----------------------------------------------------------------------===//
1309
1310static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) {
1313 Visited.insert(I);
1314 WorkList.push_back(I);
1315 while (!WorkList.empty()) {
1316 const Instruction *Curr = WorkList.pop_back_val();
1317 // This use is outside the loop, nothing to do.
1318 if (!L->contains(Curr))
1319 continue;
1320 // Do we assume it is a "hard" use which will not be eliminated easily?
1321 if (Curr->mayHaveSideEffects())
1322 return true;
1323 // Otherwise, add all its users to worklist.
1324 for (const auto *U : Curr->users()) {
1325 auto *UI = cast<Instruction>(U);
1326 if (Visited.insert(UI).second)
1327 WorkList.push_back(UI);
1328 }
1329 }
1330 return false;
1331}
1332
1333// Collect information about PHI nodes which can be transformed in
1334// rewriteLoopExitValues.
1336 PHINode *PN; // For which PHI node is this replacement?
1337 unsigned Ith; // For which incoming value?
1338 const SCEV *ExpansionSCEV; // The SCEV of the incoming value we are rewriting.
1339 Instruction *ExpansionPoint; // Where we'd like to expand that SCEV?
1340 bool HighCost; // Is this expansion a high-cost?
1341
1342 RewritePhi(PHINode *P, unsigned I, const SCEV *Val, Instruction *ExpansionPt,
1343 bool H)
1344 : PN(P), Ith(I), ExpansionSCEV(Val), ExpansionPoint(ExpansionPt),
1345 HighCost(H) {}
1346};
1347
1348// Check whether it is possible to delete the loop after rewriting exit
1349// value. If it is possible, ignore ReplaceExitValue and do rewriting
1350// aggressively.
1351static bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
1352 BasicBlock *Preheader = L->getLoopPreheader();
1353 // If there is no preheader, the loop will not be deleted.
1354 if (!Preheader)
1355 return false;
1356
1357 // In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
1358 // We obviate multiple ExitingBlocks case for simplicity.
1359 // TODO: If we see testcase with multiple ExitingBlocks can be deleted
1360 // after exit value rewriting, we can enhance the logic here.
1361 SmallVector<BasicBlock *, 4> ExitingBlocks;
1362 L->getExitingBlocks(ExitingBlocks);
1364 L->getUniqueExitBlocks(ExitBlocks);
1365 if (ExitBlocks.size() != 1 || ExitingBlocks.size() != 1)
1366 return false;
1367
1368 BasicBlock *ExitBlock = ExitBlocks[0];
1369 BasicBlock::iterator BI = ExitBlock->begin();
1370 while (PHINode *P = dyn_cast<PHINode>(BI)) {
1371 Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);
1372
1373 // If the Incoming value of P is found in RewritePhiSet, we know it
1374 // could be rewritten to use a loop invariant value in transformation
1375 // phase later. Skip it in the loop invariant check below.
1376 bool found = false;
1377 for (const RewritePhi &Phi : RewritePhiSet) {
1378 unsigned i = Phi.Ith;
1379 if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
1380 found = true;
1381 break;
1382 }
1383 }
1384
1385 Instruction *I;
1386 if (!found && (I = dyn_cast<Instruction>(Incoming)))
1387 if (!L->hasLoopInvariantOperands(I))
1388 return false;
1389
1390 ++BI;
1391 }
1392
1393 for (auto *BB : L->blocks())
1394 if (llvm::any_of(*BB, [](Instruction &I) {
1395 return I.mayHaveSideEffects();
1396 }))
1397 return false;
1398
1399 return true;
1400}
1401
1402/// Checks if it is safe to call InductionDescriptor::isInductionPHI for \p Phi,
1403/// and returns true if this Phi is an induction phi in the loop. When
1404/// isInductionPHI returns true, \p ID will be also be set by isInductionPHI.
1405static bool checkIsIndPhi(PHINode *Phi, Loop *L, ScalarEvolution *SE,
1407 if (!Phi)
1408 return false;
1409 if (!L->getLoopPreheader())
1410 return false;
1411 if (Phi->getParent() != L->getHeader())
1412 return false;
1413 return InductionDescriptor::isInductionPHI(Phi, L, SE, ID);
1414}
1415
1417 ScalarEvolution *SE,
1418 const TargetTransformInfo *TTI,
1419 SCEVExpander &Rewriter, DominatorTree *DT,
1422 // Check a pre-condition.
1423 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
1424 "Indvars did not preserve LCSSA!");
1425
1426 SmallVector<BasicBlock*, 8> ExitBlocks;
1427 L->getUniqueExitBlocks(ExitBlocks);
1428
1429 SmallVector<RewritePhi, 8> RewritePhiSet;
1430 // Find all values that are computed inside the loop, but used outside of it.
1431 // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
1432 // the exit blocks of the loop to find them.
1433 for (BasicBlock *ExitBB : ExitBlocks) {
1434 // If there are no PHI nodes in this exit block, then no values defined
1435 // inside the loop are used on this path, skip it.
1436 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
1437 if (!PN) continue;
1438
1439 unsigned NumPreds = PN->getNumIncomingValues();
1440
1441 // Iterate over all of the PHI nodes.
1442 BasicBlock::iterator BBI = ExitBB->begin();
1443 while ((PN = dyn_cast<PHINode>(BBI++))) {
1444 if (PN->use_empty())
1445 continue; // dead use, don't replace it
1446
1447 if (!SE->isSCEVable(PN->getType()))
1448 continue;
1449
1450 // Iterate over all of the values in all the PHI nodes.
1451 for (unsigned i = 0; i != NumPreds; ++i) {
1452 // If the value being merged in is not integer or is not defined
1453 // in the loop, skip it.
1454 Value *InVal = PN->getIncomingValue(i);
1455 if (!isa<Instruction>(InVal))
1456 continue;
1457
1458 // If this pred is for a subloop, not L itself, skip it.
1459 if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
1460 continue; // The Block is in a subloop, skip it.
1461
1462 // Check that InVal is defined in the loop.
1463 Instruction *Inst = cast<Instruction>(InVal);
1464 if (!L->contains(Inst))
1465 continue;
1466
1467 // Find exit values which are induction variables in the loop, and are
1468 // unused in the loop, with the only use being the exit block PhiNode,
1469 // and the induction variable update binary operator.
1470 // The exit value can be replaced with the final value when it is cheap
1471 // to do so.
1474 PHINode *IndPhi = dyn_cast<PHINode>(Inst);
1475 if (IndPhi) {
1476 if (!checkIsIndPhi(IndPhi, L, SE, ID))
1477 continue;
1478 // This is an induction PHI. Check that the only users are PHI
1479 // nodes, and induction variable update binary operators.
1480 if (llvm::any_of(Inst->users(), [&](User *U) {
1481 if (!isa<PHINode>(U) && !isa<BinaryOperator>(U))
1482 return true;
1483 BinaryOperator *B = dyn_cast<BinaryOperator>(U);
1484 if (B && B != ID.getInductionBinOp())
1485 return true;
1486 return false;
1487 }))
1488 continue;
1489 } else {
1490 // If it is not an induction phi, it must be an induction update
1491 // binary operator with an induction phi user.
1492 BinaryOperator *B = dyn_cast<BinaryOperator>(Inst);
1493 if (!B)
1494 continue;
1495 if (llvm::any_of(Inst->users(), [&](User *U) {
1496 PHINode *Phi = dyn_cast<PHINode>(U);
1497 if (Phi != PN && !checkIsIndPhi(Phi, L, SE, ID))
1498 return true;
1499 return false;
1500 }))
1501 continue;
1502 if (B != ID.getInductionBinOp())
1503 continue;
1504 }
1505 }
1506
1507 // Okay, this instruction has a user outside of the current loop
1508 // and varies predictably *inside* the loop. Evaluate the value it
1509 // contains when the loop exits, if possible. We prefer to start with
1510 // expressions which are true for all exits (so as to maximize
1511 // expression reuse by the SCEVExpander), but resort to per-exit
1512 // evaluation if that fails.
1513 const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
1514 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1515 !SE->isLoopInvariant(ExitValue, L) ||
1516 !Rewriter.isSafeToExpand(ExitValue)) {
1517 // TODO: This should probably be sunk into SCEV in some way; maybe a
1518 // getSCEVForExit(SCEV*, L, ExitingBB)? It can be generalized for
1519 // most SCEV expressions and other recurrence types (e.g. shift
1520 // recurrences). Is there existing code we can reuse?
1521 const SCEV *ExitCount = SE->getExitCount(L, PN->getIncomingBlock(i));
1522 if (isa<SCEVCouldNotCompute>(ExitCount))
1523 continue;
1524 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Inst)))
1525 if (AddRec->getLoop() == L)
1526 ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
1527 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1528 !SE->isLoopInvariant(ExitValue, L) ||
1529 !Rewriter.isSafeToExpand(ExitValue))
1530 continue;
1531 }
1532
1533 // Computing the value outside of the loop brings no benefit if it is
1534 // definitely used inside the loop in a way which can not be optimized
1535 // away. Avoid doing so unless we know we have a value which computes
1536 // the ExitValue already. TODO: This should be merged into SCEV
1537 // expander to leverage its knowledge of existing expressions.
1538 if (ReplaceExitValue != AlwaysRepl && !isa<SCEVConstant>(ExitValue) &&
1539 !isa<SCEVUnknown>(ExitValue) && hasHardUserWithinLoop(L, Inst))
1540 continue;
1541
1542 // Check if expansions of this SCEV would count as being high cost.
1543 bool HighCost = Rewriter.isHighCostExpansion(
1544 ExitValue, L, SCEVCheapExpansionBudget, TTI, Inst);
1545
1546 // Note that we must not perform expansions until after
1547 // we query *all* the costs, because if we perform temporary expansion
1548 // inbetween, one that we might not intend to keep, said expansion
1549 // *may* affect cost calculation of the next SCEV's we'll query,
1550 // and next SCEV may errneously get smaller cost.
1551
1552 // Collect all the candidate PHINodes to be rewritten.
1553 Instruction *InsertPt =
1554 (isa<PHINode>(Inst) || isa<LandingPadInst>(Inst)) ?
1555 &*Inst->getParent()->getFirstInsertionPt() : Inst;
1556 RewritePhiSet.emplace_back(PN, i, ExitValue, InsertPt, HighCost);
1557 }
1558 }
1559 }
1560
1561 // TODO: evaluate whether it is beneficial to change how we calculate
1562 // high-cost: if we have SCEV 'A' which we know we will expand, should we
1563 // calculate the cost of other SCEV's after expanding SCEV 'A', thus
1564 // potentially giving cost bonus to those other SCEV's?
1565
1566 bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
1567 int NumReplaced = 0;
1568
1569 // Transformation.
1570 for (const RewritePhi &Phi : RewritePhiSet) {
1571 PHINode *PN = Phi.PN;
1572
1573 // Only do the rewrite when the ExitValue can be expanded cheaply.
1574 // If LoopCanBeDel is true, rewrite exit value aggressively.
1577 !LoopCanBeDel && Phi.HighCost)
1578 continue;
1579
1580 Value *ExitVal = Rewriter.expandCodeFor(
1581 Phi.ExpansionSCEV, Phi.PN->getType(), Phi.ExpansionPoint);
1582
1583 LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = " << *ExitVal
1584 << '\n'
1585 << " LoopVal = " << *(Phi.ExpansionPoint) << "\n");
1586
1587#ifndef NDEBUG
1588 // If we reuse an instruction from a loop which is neither L nor one of
1589 // its containing loops, we end up breaking LCSSA form for this loop by
1590 // creating a new use of its instruction.
1591 if (auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
1592 if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
1593 if (EVL != L)
1594 assert(EVL->contains(L) && "LCSSA breach detected!");
1595#endif
1596
1597 NumReplaced++;
1598 Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
1599 PN->setIncomingValue(Phi.Ith, ExitVal);
1600 // It's necessary to tell ScalarEvolution about this explicitly so that
1601 // it can walk the def-use list and forget all SCEVs, as it may not be
1602 // watching the PHI itself. Once the new exit value is in place, there
1603 // may not be a def-use connection between the loop and every instruction
1604 // which got a SCEVAddRecExpr for that loop.
1605 SE->forgetValue(PN);
1606
1607 // If this instruction is dead now, delete it. Don't do it now to avoid
1608 // invalidating iterators.
1609 if (isInstructionTriviallyDead(Inst, TLI))
1610 DeadInsts.push_back(Inst);
1611
1612 // Replace PN with ExitVal if that is legal and does not break LCSSA.
1613 if (PN->getNumIncomingValues() == 1 &&
1614 LI->replacementPreservesLCSSAForm(PN, ExitVal)) {
1615 PN->replaceAllUsesWith(ExitVal);
1616 PN->eraseFromParent();
1617 }
1618 }
1619
1620 // The insertion point instruction may have been deleted; clear it out
1621 // so that the rewriter doesn't trip over it later.
1622 Rewriter.clearInsertPoint();
1623 return NumReplaced;
1624}
1625
1626/// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
1627/// \p OrigLoop.
1628void llvm::setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
1629 Loop *RemainderLoop, uint64_t UF) {
1630 assert(UF > 0 && "Zero unrolled factor is not supported");
1631 assert(UnrolledLoop != RemainderLoop &&
1632 "Unrolled and Remainder loops are expected to distinct");
1633
1634 // Get number of iterations in the original scalar loop.
1635 unsigned OrigLoopInvocationWeight = 0;
1636 std::optional<unsigned> OrigAverageTripCount =
1637 getLoopEstimatedTripCount(OrigLoop, &OrigLoopInvocationWeight);
1638 if (!OrigAverageTripCount)
1639 return;
1640
1641 // Calculate number of iterations in unrolled loop.
1642 unsigned UnrolledAverageTripCount = *OrigAverageTripCount / UF;
1643 // Calculate number of iterations for remainder loop.
1644 unsigned RemainderAverageTripCount = *OrigAverageTripCount % UF;
1645
1646 setLoopEstimatedTripCount(UnrolledLoop, UnrolledAverageTripCount,
1647 OrigLoopInvocationWeight);
1648 setLoopEstimatedTripCount(RemainderLoop, RemainderAverageTripCount,
1649 OrigLoopInvocationWeight);
1650}
1651
1652/// Utility that implements appending of loops onto a worklist.
1653/// Loops are added in preorder (analogous for reverse postorder for trees),
1654/// and the worklist is processed LIFO.
1655template <typename RangeT>
1657 RangeT &&Loops, SmallPriorityWorklist<Loop *, 4> &Worklist) {
1658 // We use an internal worklist to build up the preorder traversal without
1659 // recursion.
1660 SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
1661
1662 // We walk the initial sequence of loops in reverse because we generally want
1663 // to visit defs before uses and the worklist is LIFO.
1664 for (Loop *RootL : Loops) {
1665 assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
1666 assert(PreOrderWorklist.empty() &&
1667 "Must start with an empty preorder walk worklist.");
1668 PreOrderWorklist.push_back(RootL);
1669 do {
1670 Loop *L = PreOrderWorklist.pop_back_val();
1671 PreOrderWorklist.append(L->begin(), L->end());
1672 PreOrderLoops.push_back(L);
1673 } while (!PreOrderWorklist.empty());
1674
1675 Worklist.insert(std::move(PreOrderLoops));
1676 PreOrderLoops.clear();
1677 }
1678}
1679
1680template <typename RangeT>
1684}
1685
1686template void llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>(
1688
1689template void
1690llvm::appendLoopsToWorklist<Loop &>(Loop &L,
1692
1695 appendReversedLoopsToWorklist(LI, Worklist);
1696}
1697
1699 LoopInfo *LI, LPPassManager *LPM) {
1700 Loop &New = *LI->AllocateLoop();
1701 if (PL)
1702 PL->addChildLoop(&New);
1703 else
1704 LI->addTopLevelLoop(&New);
1705
1706 if (LPM)
1707 LPM->addLoop(New);
1708
1709 // Add all of the blocks in L to the new loop.
1710 for (BasicBlock *BB : L->blocks())
1711 if (LI->getLoopFor(BB) == L)
1712 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), *LI);
1713
1714 // Add all of the subloops to the new loop.
1715 for (Loop *I : *L)
1716 cloneLoop(I, &New, VM, LI, LPM);
1717
1718 return &New;
1719}
1720
1721/// IR Values for the lower and upper bounds of a pointer evolution. We
1722/// need to use value-handles because SCEV expansion can invalidate previously
1723/// expanded values. Thus expansion of a pointer can invalidate the bounds for
1724/// a previous one.
1729};
1730
1731/// Expand code for the lower and upper bound of the pointer group \p CG
1732/// in \p TheLoop. \return the values for the bounds.
1734 Loop *TheLoop, Instruction *Loc,
1735 SCEVExpander &Exp, bool HoistRuntimeChecks) {
1736 LLVMContext &Ctx = Loc->getContext();
1737 Type *PtrArithTy = PointerType::get(Ctx, CG->AddressSpace);
1738
1739 Value *Start = nullptr, *End = nullptr;
1740 LLVM_DEBUG(dbgs() << "LAA: Adding RT check for range:\n");
1741 const SCEV *Low = CG->Low, *High = CG->High, *Stride = nullptr;
1742
1743 // If the Low and High values are themselves loop-variant, then we may want
1744 // to expand the range to include those covered by the outer loop as well.
1745 // There is a trade-off here with the advantage being that creating checks
1746 // using the expanded range permits the runtime memory checks to be hoisted
1747 // out of the outer loop. This reduces the cost of entering the inner loop,
1748 // which can be significant for low trip counts. The disadvantage is that
1749 // there is a chance we may now never enter the vectorized inner loop,
1750 // whereas using a restricted range check could have allowed us to enter at
1751 // least once. This is why the behaviour is not currently the default and is
1752 // controlled by the parameter 'HoistRuntimeChecks'.
1753 if (HoistRuntimeChecks && TheLoop->getParentLoop() &&
1754 isa<SCEVAddRecExpr>(High) && isa<SCEVAddRecExpr>(Low)) {
1755 auto *HighAR = cast<SCEVAddRecExpr>(High);
1756 auto *LowAR = cast<SCEVAddRecExpr>(Low);
1757 const Loop *OuterLoop = TheLoop->getParentLoop();
1758 const SCEV *Recur = LowAR->getStepRecurrence(*Exp.getSE());
1759 if (Recur == HighAR->getStepRecurrence(*Exp.getSE()) &&
1760 HighAR->getLoop() == OuterLoop && LowAR->getLoop() == OuterLoop) {
1761 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1762 const SCEV *OuterExitCount =
1763 Exp.getSE()->getExitCount(OuterLoop, OuterLoopLatch);
1764 if (!isa<SCEVCouldNotCompute>(OuterExitCount) &&
1765 OuterExitCount->getType()->isIntegerTy()) {
1766 const SCEV *NewHigh = cast<SCEVAddRecExpr>(High)->evaluateAtIteration(
1767 OuterExitCount, *Exp.getSE());
1768 if (!isa<SCEVCouldNotCompute>(NewHigh)) {
1769 LLVM_DEBUG(dbgs() << "LAA: Expanded RT check for range to include "
1770 "outer loop in order to permit hoisting\n");
1771 High = NewHigh;
1772 Low = cast<SCEVAddRecExpr>(Low)->getStart();
1773 // If there is a possibility that the stride is negative then we have
1774 // to generate extra checks to ensure the stride is positive.
1775 if (!Exp.getSE()->isKnownNonNegative(Recur)) {
1776 Stride = Recur;
1777 LLVM_DEBUG(dbgs() << "LAA: ... but need to check stride is "
1778 "positive: "
1779 << *Stride << '\n');
1780 }
1781 }
1782 }
1783 }
1784 }
1785
1786 Start = Exp.expandCodeFor(Low, PtrArithTy, Loc);
1787 End = Exp.expandCodeFor(High, PtrArithTy, Loc);
1788 if (CG->NeedsFreeze) {
1789 IRBuilder<> Builder(Loc);
1790 Start = Builder.CreateFreeze(Start, Start->getName() + ".fr");
1791 End = Builder.CreateFreeze(End, End->getName() + ".fr");
1792 }
1793 Value *StrideVal =
1794 Stride ? Exp.expandCodeFor(Stride, Stride->getType(), Loc) : nullptr;
1795 LLVM_DEBUG(dbgs() << "Start: " << *Low << " End: " << *High << "\n");
1796 return {Start, End, StrideVal};
1797}
1798
1799/// Turns a collection of checks into a collection of expanded upper and
1800/// lower bounds for both pointers in the check.
1803 Instruction *Loc, SCEVExpander &Exp, bool HoistRuntimeChecks) {
1805
1806 // Here we're relying on the SCEV Expander's cache to only emit code for the
1807 // same bounds once.
1808 transform(PointerChecks, std::back_inserter(ChecksWithBounds),
1809 [&](const RuntimePointerCheck &Check) {
1810 PointerBounds First = expandBounds(Check.first, L, Loc, Exp,
1812 Second = expandBounds(Check.second, L, Loc, Exp,
1814 return std::make_pair(First, Second);
1815 });
1816
1817 return ChecksWithBounds;
1818}
1819
1821 Instruction *Loc, Loop *TheLoop,
1822 const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
1823 SCEVExpander &Exp, bool HoistRuntimeChecks) {
1824 // TODO: Move noalias annotation code from LoopVersioning here and share with LV if possible.
1825 // TODO: Pass RtPtrChecking instead of PointerChecks and SE separately, if possible
1826 auto ExpandedChecks =
1827 expandBounds(PointerChecks, TheLoop, Loc, Exp, HoistRuntimeChecks);
1828
1829 LLVMContext &Ctx = Loc->getContext();
1830 IRBuilder<InstSimplifyFolder> ChkBuilder(Ctx,
1831 Loc->getModule()->getDataLayout());
1832 ChkBuilder.SetInsertPoint(Loc);
1833 // Our instructions might fold to a constant.
1834 Value *MemoryRuntimeCheck = nullptr;
1835
1836 for (const auto &Check : ExpandedChecks) {
1837 const PointerBounds &A = Check.first, &B = Check.second;
1838 // Check if two pointers (A and B) conflict where conflict is computed as:
1839 // start(A) <= end(B) && start(B) <= end(A)
1840
1841 assert((A.Start->getType()->getPointerAddressSpace() ==
1842 B.End->getType()->getPointerAddressSpace()) &&
1843 (B.Start->getType()->getPointerAddressSpace() ==
1844 A.End->getType()->getPointerAddressSpace()) &&
1845 "Trying to bounds check pointers with different address spaces");
1846
1847 // [A|B].Start points to the first accessed byte under base [A|B].
1848 // [A|B].End points to the last accessed byte, plus one.
1849 // There is no conflict when the intervals are disjoint:
1850 // NoConflict = (B.Start >= A.End) || (A.Start >= B.End)
1851 //
1852 // bound0 = (B.Start < A.End)
1853 // bound1 = (A.Start < B.End)
1854 // IsConflict = bound0 & bound1
1855 Value *Cmp0 = ChkBuilder.CreateICmpULT(A.Start, B.End, "bound0");
1856 Value *Cmp1 = ChkBuilder.CreateICmpULT(B.Start, A.End, "bound1");
1857 Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
1858 if (A.StrideToCheck) {
1859 Value *IsNegativeStride = ChkBuilder.CreateICmpSLT(
1860 A.StrideToCheck, ConstantInt::get(A.StrideToCheck->getType(), 0),
1861 "stride.check");
1862 IsConflict = ChkBuilder.CreateOr(IsConflict, IsNegativeStride);
1863 }
1864 if (B.StrideToCheck) {
1865 Value *IsNegativeStride = ChkBuilder.CreateICmpSLT(
1866 B.StrideToCheck, ConstantInt::get(B.StrideToCheck->getType(), 0),
1867 "stride.check");
1868 IsConflict = ChkBuilder.CreateOr(IsConflict, IsNegativeStride);
1869 }
1870 if (MemoryRuntimeCheck) {
1871 IsConflict =
1872 ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx");
1873 }
1874 MemoryRuntimeCheck = IsConflict;
1875 }
1876
1877 return MemoryRuntimeCheck;
1878}
1879
1881 Instruction *Loc, ArrayRef<PointerDiffInfo> Checks, SCEVExpander &Expander,
1882 function_ref<Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC) {
1883
1884 LLVMContext &Ctx = Loc->getContext();
1885 IRBuilder<InstSimplifyFolder> ChkBuilder(Ctx,
1886 Loc->getModule()->getDataLayout());
1887 ChkBuilder.SetInsertPoint(Loc);
1888 // Our instructions might fold to a constant.
1889 Value *MemoryRuntimeCheck = nullptr;
1890
1891 auto &SE = *Expander.getSE();
1892 // Map to keep track of created compares, The key is the pair of operands for
1893 // the compare, to allow detecting and re-using redundant compares.
1895 for (const auto &C : Checks) {
1896 Type *Ty = C.SinkStart->getType();
1897 // Compute VF * IC * AccessSize.
1898 auto *VFTimesUFTimesSize =
1899 ChkBuilder.CreateMul(GetVF(ChkBuilder, Ty->getScalarSizeInBits()),
1900 ConstantInt::get(Ty, IC * C.AccessSize));
1901 Value *Diff = Expander.expandCodeFor(
1902 SE.getMinusSCEV(C.SinkStart, C.SrcStart), Ty, Loc);
1903
1904 // Check if the same compare has already been created earlier. In that case,
1905 // there is no need to check it again.
1906 Value *IsConflict = SeenCompares.lookup({Diff, VFTimesUFTimesSize});
1907 if (IsConflict)
1908 continue;
1909
1910 IsConflict =
1911 ChkBuilder.CreateICmpULT(Diff, VFTimesUFTimesSize, "diff.check");
1912 SeenCompares.insert({{Diff, VFTimesUFTimesSize}, IsConflict});
1913 if (C.NeedsFreeze)
1914 IsConflict =
1915 ChkBuilder.CreateFreeze(IsConflict, IsConflict->getName() + ".fr");
1916 if (MemoryRuntimeCheck) {
1917 IsConflict =
1918 ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx");
1919 }
1920 MemoryRuntimeCheck = IsConflict;
1921 }
1922
1923 return MemoryRuntimeCheck;
1924}
1925
1926std::optional<IVConditionInfo>
1928 const MemorySSA &MSSA, AAResults &AA) {
1929 auto *TI = dyn_cast<BranchInst>(L.getHeader()->getTerminator());
1930 if (!TI || !TI->isConditional())
1931 return {};
1932
1933 auto *CondI = dyn_cast<CmpInst>(TI->getCondition());
1934 // The case with the condition outside the loop should already be handled
1935 // earlier.
1936 if (!CondI || !L.contains(CondI))
1937 return {};
1938
1939 SmallVector<Instruction *> InstToDuplicate;
1940 InstToDuplicate.push_back(CondI);
1941
1942 SmallVector<Value *, 4> WorkList;
1943 WorkList.append(CondI->op_begin(), CondI->op_end());
1944
1945 SmallVector<MemoryAccess *, 4> AccessesToCheck;
1946 SmallVector<MemoryLocation, 4> AccessedLocs;
1947 while (!WorkList.empty()) {
1948 Instruction *I = dyn_cast<Instruction>(WorkList.pop_back_val());
1949 if (!I || !L.contains(I))
1950 continue;
1951
1952 // TODO: support additional instructions.
1953 if (!isa<LoadInst>(I) && !isa<GetElementPtrInst>(I))
1954 return {};
1955
1956 // Do not duplicate volatile and atomic loads.
1957 if (auto *LI = dyn_cast<LoadInst>(I))
1958 if (LI->isVolatile() || LI->isAtomic())
1959 return {};
1960
1961 InstToDuplicate.push_back(I);
1962 if (MemoryAccess *MA = MSSA.getMemoryAccess(I)) {
1963 if (auto *MemUse = dyn_cast_or_null<MemoryUse>(MA)) {
1964 // Queue the defining access to check for alias checks.
1965 AccessesToCheck.push_back(MemUse->getDefiningAccess());
1966 AccessedLocs.push_back(MemoryLocation::get(I));
1967 } else {
1968 // MemoryDefs may clobber the location or may be atomic memory
1969 // operations. Bail out.
1970 return {};
1971 }
1972 }
1973 WorkList.append(I->op_begin(), I->op_end());
1974 }
1975
1976 if (InstToDuplicate.empty())
1977 return {};
1978
1979 SmallVector<BasicBlock *, 4> ExitingBlocks;
1980 L.getExitingBlocks(ExitingBlocks);
1981 auto HasNoClobbersOnPath =
1982 [&L, &AA, &AccessedLocs, &ExitingBlocks, &InstToDuplicate,
1983 MSSAThreshold](BasicBlock *Succ, BasicBlock *Header,
1984 SmallVector<MemoryAccess *, 4> AccessesToCheck)
1985 -> std::optional<IVConditionInfo> {
1987 // First, collect all blocks in the loop that are on a patch from Succ
1988 // to the header.
1990 WorkList.push_back(Succ);
1991 WorkList.push_back(Header);
1993 Seen.insert(Header);
1994 Info.PathIsNoop &=
1995 all_of(*Header, [](Instruction &I) { return !I.mayHaveSideEffects(); });
1996
1997 while (!WorkList.empty()) {
1998 BasicBlock *Current = WorkList.pop_back_val();
1999 if (!L.contains(Current))
2000 continue;
2001 const auto &SeenIns = Seen.insert(Current);
2002 if (!SeenIns.second)
2003 continue;
2004
2005 Info.PathIsNoop &= all_of(
2006 *Current, [](Instruction &I) { return !I.mayHaveSideEffects(); });
2007 WorkList.append(succ_begin(Current), succ_end(Current));
2008 }
2009
2010 // Require at least 2 blocks on a path through the loop. This skips
2011 // paths that directly exit the loop.
2012 if (Seen.size() < 2)
2013 return {};
2014
2015 // Next, check if there are any MemoryDefs that are on the path through
2016 // the loop (in the Seen set) and they may-alias any of the locations in
2017 // AccessedLocs. If that is the case, they may modify the condition and
2018 // partial unswitching is not possible.
2019 SmallPtrSet<MemoryAccess *, 4> SeenAccesses;
2020 while (!AccessesToCheck.empty()) {
2021 MemoryAccess *Current = AccessesToCheck.pop_back_val();
2022 auto SeenI = SeenAccesses.insert(Current);
2023 if (!SeenI.second || !Seen.contains(Current->getBlock()))
2024 continue;
2025
2026 // Bail out if exceeded the threshold.
2027 if (SeenAccesses.size() >= MSSAThreshold)
2028 return {};
2029
2030 // MemoryUse are read-only accesses.
2031 if (isa<MemoryUse>(Current))
2032 continue;
2033
2034 // For a MemoryDef, check if is aliases any of the location feeding
2035 // the original condition.
2036 if (auto *CurrentDef = dyn_cast<MemoryDef>(Current)) {
2037 if (any_of(AccessedLocs, [&AA, CurrentDef](MemoryLocation &Loc) {
2038 return isModSet(
2039 AA.getModRefInfo(CurrentDef->getMemoryInst(), Loc));
2040 }))
2041 return {};
2042 }
2043
2044 for (Use &U : Current->uses())
2045 AccessesToCheck.push_back(cast<MemoryAccess>(U.getUser()));
2046 }
2047
2048 // We could also allow loops with known trip counts without mustprogress,
2049 // but ScalarEvolution may not be available.
2050 Info.PathIsNoop &= isMustProgress(&L);
2051
2052 // If the path is considered a no-op so far, check if it reaches a
2053 // single exit block without any phis. This ensures no values from the
2054 // loop are used outside of the loop.
2055 if (Info.PathIsNoop) {
2056 for (auto *Exiting : ExitingBlocks) {
2057 if (!Seen.contains(Exiting))
2058 continue;
2059 for (auto *Succ : successors(Exiting)) {
2060 if (L.contains(Succ))
2061 continue;
2062
2063 Info.PathIsNoop &= Succ->phis().empty() &&
2064 (!Info.ExitForPath || Info.ExitForPath == Succ);
2065 if (!Info.PathIsNoop)
2066 break;
2067 assert((!Info.ExitForPath || Info.ExitForPath == Succ) &&
2068 "cannot have multiple exit blocks");
2069 Info.ExitForPath = Succ;
2070 }
2071 }
2072 }
2073 if (!Info.ExitForPath)
2074 Info.PathIsNoop = false;
2075
2076 Info.InstToDuplicate = InstToDuplicate;
2077 return Info;
2078 };
2079
2080 // If we branch to the same successor, partial unswitching will not be
2081 // beneficial.
2082 if (TI->getSuccessor(0) == TI->getSuccessor(1))
2083 return {};
2084
2085 if (auto Info = HasNoClobbersOnPath(TI->getSuccessor(0), L.getHeader(),
2086 AccessesToCheck)) {
2087 Info->KnownValue = ConstantInt::getTrue(TI->getContext());
2088 return Info;
2089 }
2090 if (auto Info = HasNoClobbersOnPath(TI->getSuccessor(1), L.getHeader(),
2091 AccessesToCheck)) {
2092 Info->KnownValue = ConstantInt::getFalse(TI->getContext());
2093 return Info;
2094 }
2095
2096 return {};
2097}
amdgpu AMDGPU Register Bank Select
This is the interface for LLVM's primary stateless and local alias analysis.
bbsections Prepares for basic block by splitting functions into clusters of basic blocks
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseSet and SmallDenseSet classes.
@ Enable
Definition: DwarfDebug.cpp:87
std::string Name
bool End
Definition: ELF_riscv.cpp:480
#define Check(C,...)
This is the interface for a simple mod/ref and alias analysis over globals.
static const HTTPClientCleanup Cleanup
Definition: HTTPClient.cpp:42
Hexagon Hardware Loops
iv Induction Variable Users
Definition: IVUsers.cpp:48
static cl::opt< ReplaceExitVal > ReplaceExitValue("replexitval", cl::Hidden, cl::init(OnlyCheapRepl), cl::desc("Choose the strategy to replace exit value in IndVarSimplify"), cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"), clEnumValN(OnlyCheapRepl, "cheap", "only replace exit value when the cost is cheap"), clEnumValN(UnusedIndVarInLoop, "unusedindvarinloop", "only replace exit value when it is an unused " "induction variable in the loop and has cheap replacement cost"), clEnumValN(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))
static cl::opt< bool, true > HoistRuntimeChecks("hoist-runtime-checks", cl::Hidden, cl::desc("Hoist inner loop runtime memory checks to outer loop if possible"), cl::location(VectorizerParams::HoistRuntimeChecks), cl::init(true))
static std::optional< uint64_t > getEstimatedTripCount(BranchInst *ExitingBranch, Loop *L, uint64_t &OrigExitWeight)
Return the estimated trip count for any exiting branch which dominates the loop latch.
Definition: LoopUtils.cpp:822
static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I)
Definition: LoopUtils.cpp:1310
static const char * LLVMLoopDisableLICM
Definition: LoopUtils.cpp:55
static PointerBounds expandBounds(const RuntimeCheckingPtrGroup *CG, Loop *TheLoop, Instruction *Loc, SCEVExpander &Exp, bool HoistRuntimeChecks)
Expand code for the lower and upper bound of the pointer group CG in TheLoop.
Definition: LoopUtils.cpp:1733
static bool canLoopBeDeleted(Loop *L, SmallVector< RewritePhi, 8 > &RewritePhiSet)
Definition: LoopUtils.cpp:1351
static const char * LLVMLoopDisableNonforced
Definition: LoopUtils.cpp:54
static MDNode * createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V)
Create MDNode for input string.
Definition: LoopUtils.cpp:203
static BranchInst * getExpectedExitLoopLatchBranch(Loop *L)
Checks if L has an exiting latch branch.
Definition: LoopUtils.cpp:804
static bool checkIsIndPhi(PHINode *Phi, Loop *L, ScalarEvolution *SE, InductionDescriptor &ID)
Checks if it is safe to call InductionDescriptor::isInductionPHI for Phi, and returns true if this Ph...
Definition: LoopUtils.cpp:1405
#define I(x, y, z)
Definition: MD5.cpp:58
#define H(x, y, z)
Definition: MD5.cpp:57
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
uint64_t High
LLVMContext & Context
#define P(N)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
This file provides a priority worklist.
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This is the interface for a SCEV-based alias analysis.
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file implements a set that has insertion order iteration characteristics.
static cl::opt< unsigned > MSSAThreshold("simple-loop-unswitch-memoryssa-threshold", cl::desc("Max number of memory uses to explore during " "partial unswitching analysis"), cl::init(100), cl::Hidden)
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Virtual Register Rewriter
Definition: VirtRegMap.cpp:237
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
Class for arbitrary precision integers.
Definition: APInt.h:76
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:184
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:187
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:194
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:197
Represent the analysis usage information of a pass.
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:283
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Legacy wrapper pass to provide the BasicAAResult object.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:430
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:409
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:165
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:168
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:221
Conditional or Unconditional Branch instruction.
unsigned getNumSuccessors() const
BasicBlock * getSuccessor(unsigned i) const
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:993
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:1022
@ FCMP_OLT
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:999
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:997
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:1016
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:1020
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:1018
@ ICMP_NE
not equal
Definition: InstrTypes.h:1015
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:528
static Constant * getNegativeZero(Type *Ty)
Definition: Constants.h:306
This is the shared class of boolean and integer constants.
Definition: Constants.h:80
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:849
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:856
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:160
This class represents an Operation in the Expression.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
Identifies a unique instance of a variable.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:202
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:317
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
static constexpr ElementCount get(ScalarTy MinVal, bool Scalable)
Definition: TypeSize.h:302
Legacy wrapper pass to provide the GlobalsAAResult object.
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:94
CallInst * CreateMulReduce(Value *Src)
Create a vector int mul reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:437
CallInst * CreateFAddReduce(Value *Acc, Value *Src)
Create a sequential vector fadd reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:417
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2257
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2460
UnreachableInst * CreateUnreachable()
Definition: IRBuilder.h:1263
CallInst * CreateAndReduce(Value *Src)
Create a vector int AND reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:441
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Definition: IRBuilder.cpp:1214
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Definition: IRBuilder.cpp:932
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1110
CallInst * CreateAddReduce(Value *Src)
Create a vector int add reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:433
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2535
CallInst * CreateXorReduce(Value *Src)
Create a vector int XOR reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:449
CallInst * CreateOrReduce(Value *Src)
Create a vector int OR reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:445
CallInst * CreateFPMinReduce(Value *Src)
Create a vector float min reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:469
CallInst * CreateFPMaximumReduce(Value *Src)
Create a vector float maximum reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:473
CallInst * CreateFPMaxReduce(Value *Src)
Create a vector float max reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:465
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:486
Value * CreateCmp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2366
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
Definition: IRBuilder.h:1120
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition: IRBuilder.h:2494
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1475
CallInst * CreateIntMaxReduce(Value *Src, bool IsSigned=false)
Create a vector integer max reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:453
ConstantInt * getFalse()
Get the constant value for i1 false.
Definition: IRBuilder.h:471
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1497
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1666
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Definition: IRBuilder.h:1114
Value * CreateICmpSLT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2273
CallInst * CreateIntMinReduce(Value *Src, bool IsSigned=false)
Create a vector integer min reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:459
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
CallInst * CreateFMulReduce(Value *Acc, Value *Src)
Create a sequential vector fmul reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:425
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1361
CallInst * CreateFPMinimumReduce(Value *Src)
Create a vector float minimum reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:477
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2666
A struct for saving information about induction variables.
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:82
const BasicBlock * getParent() const
Definition: Instruction.h:152
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1636
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
void addLoop(Loop &L)
Definition: LoopPass.cpp:76
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
BlockT * getHeader() const
std::vector< Loop * >::const_iterator iterator
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
iterator end() const
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
LoopT * AllocateLoop(ArgsTy &&...Args)
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
void destroy(LoopT *L)
Destroy a loop that has been removed from the LoopInfo nest.
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:593
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Definition: LoopInfo.h:439
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:875
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:525
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:501
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
Definition: MDBuilder.cpp:37
Metadata node.
Definition: Metadata.h:1067
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:1071
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1428
ArrayRef< MDOperand > operands() const
Definition: Metadata.h:1426
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1541
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1434
LLVMContext & getContext() const
Definition: Metadata.h:1231
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:889
A single uniqued string.
Definition: Metadata.h:720
StringRef getString() const
Definition: Metadata.cpp:610
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:600
Tuple of metadata.
Definition: Metadata.h:1470
BasicBlock * getBlock() const
Definition: MemorySSA.h:164
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:980
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1861
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
Root of the metadata hierarchy.
Definition: Metadata.h:62
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:293
void setIncomingValue(unsigned i, Value *V)
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:37
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1827
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:71
static bool isAnyOfRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:44
Legacy wrapper pass to provide the SCEVAAResult object.
This class uses information about analyze scalars to rewrite expressions in canonical form.
ScalarEvolution * getSE()
Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopInvariant
The SCEV is loop-invariant.
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
This class represents the LLVM 'select' instruction.
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:290
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
size_type size() const
Definition: SmallPtrSet.h:94
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:696
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
bool starts_with(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:257
bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Definition: StringRef.h:164
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:331
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:234
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:228
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
iterator_range< user_iterator > users()
Definition: Value.h:421
bool use_empty() const
Definition: Value.h:344
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1074
iterator_range< use_iterator > uses()
Definition: Value.h:376
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
An efficient, type-erasing, non-owning reference to a callable.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
std::optional< ElementCount > getOptionalElementCountLoopAttribute(const Loop *TheLoop)
Find a combination of metadata ("llvm.loop.vectorize.width" and "llvm.loop.vectorize....
Definition: LoopUtils.cpp:250
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
SmallVector< DomTreeNode *, 16 > collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop)
Does a BFS from a given node to all of its children inside a given loop.
Definition: LoopUtils.cpp:450
Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, SCEVExpander &Expander, bool HoistRuntimeChecks=false)
Add code that checks at runtime if the accessed arrays in PointerChecks overlap.
Definition: LoopUtils.cpp:1820
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1742
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:849
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1722
Intrinsic::ID getMinMaxReductionIntrinsicOp(Intrinsic::ID RdxID)
Returns the min/max intrinsic used when expanding a min/max reduction.
Definition: LoopUtils.cpp:950
bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)
Returns true if Name is applied to TheLoop and enabled.
Definition: LoopInfo.cpp:1085
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
bool isKnownNonPositiveInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always non-positive in loop L.
Definition: LoopUtils.cpp:1276
Value * createSimpleTargetReduction(IRBuilderBase &B, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:1166
std::optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)
Definition: LoopInfo.cpp:1067
void appendReversedLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1656
auto successors(const MachineBasicBlock *BB)
void initializeLoopPassPass(PassRegistry &)
Manually defined generic "LoopPass" dependency initialization.
Definition: LoopUtils.cpp:189
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:425
std::optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)
Create a new loop identifier for a loop created from a loop transformation.
Definition: LoopUtils.cpp:263
unsigned getArithmeticReductionInstruction(Intrinsic::ID RdxID)
Returns the arithmetic instruction opcode used when expanding a reduction.
Definition: LoopUtils.cpp:921
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:656
char & LCSSAID
Definition: LCSSA.cpp:507
char & LoopSimplifyID
Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:1046
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
Definition: LoopUtils.cpp:214
bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)
Returns true if S is defined and never is equal to signed/unsigned max.
Definition: LoopUtils.cpp:1294
TransformationMode hasVectorizeTransformation(const Loop *L)
Definition: LoopUtils.cpp:391
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
Definition: STLExtras.h:1928
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:399
uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator)
Returns the integer nearest(Numerator / Denominator).
Definition: MathExtras.h:422
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:123
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
Definition: LoopInfo.cpp:1118
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:264
bool isModSet(const ModRefInfo MRI)
Definition: ModRef.h:48
TransformationMode hasUnrollAndJamTransformation(const Loop *L)
Definition: LoopUtils.cpp:373
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
Definition: LoopUtils.cpp:483
Value * getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op, RecurKind MinMaxKind=RecurKind::None)
Generates a vector reduction using shufflevectors to reduce the value.
Definition: LoopUtils.cpp:1088
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool hasDisableAllTransformsHint(const Loop *L)
Look for the loop attribute that disables all transformation heuristic.
Definition: LoopUtils.cpp:344
Value * createOrderedReduction(IRBuilderBase &B, const RecurrenceDescriptor &Desc, Value *Src, Value *Start)
Create an ordered reduction intrinsic using the given recurrence descriptor Desc.
Definition: LoopUtils.cpp:1223
cl::opt< unsigned > SCEVCheapExpansionBudget
TransformationMode hasUnrollTransformation(const Loop *L)
Definition: LoopUtils.cpp:352
TransformationMode hasDistributeTransformation(const Loop *L)
Definition: LoopUtils.cpp:427
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
Definition: LoopUtils.cpp:724
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:141
void propagateIRFlags(Value *I, ArrayRef< Value * > VL, Value *OpValue=nullptr, bool IncludeWrapFlags=true)
Get the intersection (logical and) of all of the potential IR flags of each scalar operation (VL) tha...
Definition: LoopUtils.cpp:1235
bool isKnownPositiveInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always positive in loop L.
Definition: LoopUtils.cpp:1269
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:2832
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
Definition: LoopInfo.cpp:1089
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)
Returns the comparison predicate used when expanding a min/max reduction.
Definition: LoopUtils.cpp:1015
TransformationMode hasLICMVersioningTransformation(const Loop *L)
Definition: LoopUtils.cpp:437
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:83
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:275
@ TM_Unspecified
The pass can use heuristics to determine whether a transformation should be applied.
Definition: LoopUtils.h:278
@ TM_SuppressedByUser
The transformation must not be applied.
Definition: LoopUtils.h:298
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Definition: LoopUtils.h:292
@ TM_Disable
The transformation should not be applied.
Definition: LoopUtils.h:284
@ TM_Enable
The transformation should be applied without considering a cost model.
Definition: LoopUtils.h:281
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
Definition: LoopUtils.cpp:348
RecurKind
These are the kinds of recurrences that we support.
Definition: IVDescriptors.h:34
bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, unsigned EstimatedLoopInvocationWeight)
Set a loop's branch weight metadata to reflect that loop has EstimatedTripCount iterations and Estima...
Definition: LoopUtils.cpp:867
Value * createAnyOfOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK, Value *Left, Value *Right)
See RecurrenceDescriptor::isAnyOfPattern for a description of the pattern we are trying to match.
Definition: LoopUtils.cpp:1037
void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, Loop *RemainderLoop, uint64_t UF)
Set weights for UnrolledLoop and RemainderLoop based on weights for OrigLoop and the following distri...
Definition: LoopUtils.cpp:1628
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:57
DWARFExpression::Operation Op
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1681
bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always negative in loop L.
Definition: LoopUtils.cpp:1255
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE)
Check inner loop (L) backedge count is known to be invariant on all iterations of its outer loop.
Definition: LoopUtils.cpp:899
bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond)
Return true if the induction variable IV in a Loop whose latch is LatchBlock would become dead if the...
Definition: LoopUtils.cpp:469
auto predecessors(const MachineBasicBlock *BB)
int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, ScalarEvolution *SE, const TargetTransformInfo *TTI, SCEVExpander &Rewriter, DominatorTree *DT, ReplaceExitVal ReplaceExitValue, SmallVector< WeakTrackingVH, 16 > &DeadInsts)
If the final value of any expressions that are recurrent in the loop can be computed,...
Definition: LoopUtils.cpp:1416
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:123
Value * addDiffRuntimeChecks(Instruction *Loc, ArrayRef< PointerDiffInfo > Checks, SCEVExpander &Expander, function_ref< Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC)
Definition: LoopUtils.cpp:1880
RecurKind getMinMaxReductionRecurKind(Intrinsic::ID RdxID)
Returns the recurence kind used when expanding a min/max reduction.
Definition: LoopUtils.cpp:996
ReplaceExitVal
Definition: LoopUtils.h:461
@ UnusedIndVarInLoop
Definition: LoopUtils.h:465
@ OnlyCheapRepl
Definition: LoopUtils.h:463
@ AlwaysRepl
Definition: LoopUtils.h:466
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
std::optional< IVConditionInfo > hasPartialIVCondition(const Loop &L, unsigned MSSAThreshold, const MemorySSA &MSSA, AAResults &AA)
Check if the loop header has a conditional branch that is not loop-invariant, because it involves loa...
Definition: LoopUtils.cpp:1927
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)
Returns true if S is defined and never is equal to signed/unsigned min.
Definition: LoopUtils.cpp:1283
bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always non-negative in loop L.
Definition: LoopUtils.cpp:1262
Value * getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src, unsigned Op, RecurKind MinMaxKind=RecurKind::None)
Generates an ordered vector reduction using extracts to reduce the value.
Definition: LoopUtils.cpp:1063
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Definition: LoopInfo.cpp:1017
Value * createTargetReduction(IRBuilderBase &B, const RecurrenceDescriptor &Desc, Value *Src, PHINode *OrigPhi=nullptr)
Create a generic target reduction using a recurrence descriptor Desc The target is queried to determi...
Definition: LoopUtils.cpp:1207
Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...
Definition: LoopUtils.cpp:1698
Value * createAnyOfTargetReduction(IRBuilderBase &B, Value *Src, const RecurrenceDescriptor &Desc, PHINode *OrigPhi)
Create a target reduction of the given vector Src for a reduction of the kind RecurKind::IAnyOf or Re...
Definition: LoopUtils.cpp:1128
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N
IR Values for the lower and upper bounds of a pointer evolution.
Definition: LoopUtils.cpp:1725
TrackingVH< Value > Start
Definition: LoopUtils.cpp:1726
TrackingVH< Value > End
Definition: LoopUtils.cpp:1727
Value * StrideToCheck
Definition: LoopUtils.cpp:1728
unsigned Ith
Definition: LoopUtils.cpp:1337
RewritePhi(PHINode *P, unsigned I, const SCEV *Val, Instruction *ExpansionPt, bool H)
Definition: LoopUtils.cpp:1342
const SCEV * ExpansionSCEV
Definition: LoopUtils.cpp:1338
PHINode * PN
Definition: LoopUtils.cpp:1336
Instruction * ExpansionPoint
Definition: LoopUtils.cpp:1339
Description of the encoding of one expression Op.
Struct to hold information about a partially invariant condition.
Definition: LoopUtils.h:539
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
unsigned AddressSpace
Address space of the involved pointers.
bool NeedsFreeze
Whether the pointer needs to be frozen after expansion, e.g.
const SCEV * High
The SCEV expression which represents the upper bound of all the pointers in this group.
const SCEV * Low
The SCEV expression which represents the lower bound of all the pointers in this group.