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() == 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 Value *Right) {
1039 Type *Ty = Left->getType();
1040 if (Ty->isIntOrIntVectorTy() ||
1041 (RK == RecurKind::FMinimum || RK == RecurKind::FMaximum)) {
1042 // TODO: Add float minnum/maxnum support when FMF nnan is set.
1044 return Builder.CreateIntrinsic(Ty, Id, {Left, Right}, nullptr,
1045 "rdx.minmax");
1046 }
1048 Value *Cmp = Builder.CreateCmp(Pred, Left, Right, "rdx.minmax.cmp");
1049 Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
1050 return Select;
1051}
1052
1053// Helper to generate an ordered reduction.
1055 unsigned Op, RecurKind RdxKind) {
1056 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
1057
1058 // Extract and apply reduction ops in ascending order:
1059 // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
1060 Value *Result = Acc;
1061 for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
1062 Value *Ext =
1063 Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx));
1064
1065 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1066 Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext,
1067 "bin.rdx");
1068 } else {
1070 "Invalid min/max");
1071 Result = createMinMaxOp(Builder, RdxKind, Result, Ext);
1072 }
1073 }
1074
1075 return Result;
1076}
1077
1078// Helper to generate a log2 shuffle reduction.
1080 unsigned Op, RecurKind RdxKind) {
1081 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
1082 // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
1083 // and vector ops, reducing the set of values being computed by half each
1084 // round.
1085 assert(isPowerOf2_32(VF) &&
1086 "Reduction emission only supported for pow2 vectors!");
1087 // Note: fast-math-flags flags are controlled by the builder configuration
1088 // and are assumed to apply to all generated arithmetic instructions. Other
1089 // poison generating flags (nsw/nuw/inbounds/inrange/exact) are not part
1090 // of the builder configuration, and since they're not passed explicitly,
1091 // will never be relevant here. Note that it would be generally unsound to
1092 // propagate these from an intrinsic call to the expansion anyways as we/
1093 // change the order of operations.
1094 Value *TmpVec = Src;
1095 SmallVector<int, 32> ShuffleMask(VF);
1096 for (unsigned i = VF; i != 1; i >>= 1) {
1097 // Move the upper half of the vector to the lower half.
1098 for (unsigned j = 0; j != i / 2; ++j)
1099 ShuffleMask[j] = i / 2 + j;
1100
1101 // Fill the rest of the mask with undef.
1102 std::fill(&ShuffleMask[i / 2], ShuffleMask.end(), -1);
1103
1104 Value *Shuf = Builder.CreateShuffleVector(TmpVec, ShuffleMask, "rdx.shuf");
1105
1106 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1107 TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf,
1108 "bin.rdx");
1109 } else {
1111 "Invalid min/max");
1112 TmpVec = createMinMaxOp(Builder, RdxKind, TmpVec, Shuf);
1113 }
1114 }
1115 // The result is in the first element of the vector.
1116 return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
1117}
1118
1121 PHINode *OrigPhi) {
1122 assert(
1124 "Unexpected reduction kind");
1125 Value *InitVal = Desc.getRecurrenceStartValue();
1126 Value *NewVal = nullptr;
1127
1128 // First use the original phi to determine the new value we're trying to
1129 // select from in the loop.
1130 SelectInst *SI = nullptr;
1131 for (auto *U : OrigPhi->users()) {
1132 if ((SI = dyn_cast<SelectInst>(U)))
1133 break;
1134 }
1135 assert(SI && "One user of the original phi should be a select");
1136
1137 if (SI->getTrueValue() == OrigPhi)
1138 NewVal = SI->getFalseValue();
1139 else {
1140 assert(SI->getFalseValue() == OrigPhi &&
1141 "At least one input to the select should be the original Phi");
1142 NewVal = SI->getTrueValue();
1143 }
1144
1145 // If any predicate is true it means that we want to select the new value.
1146 Value *AnyOf =
1147 Src->getType()->isVectorTy() ? Builder.CreateOrReduce(Src) : Src;
1148 // The compares in the loop may yield poison, which propagates through the
1149 // bitwise ORs. Freeze it here before the condition is used.
1150 AnyOf = Builder.CreateFreeze(AnyOf);
1151 return Builder.CreateSelect(AnyOf, NewVal, InitVal, "rdx.select");
1152}
1153
1155 RecurKind RdxKind) {
1156 auto *SrcVecEltTy = cast<VectorType>(Src->getType())->getElementType();
1157 switch (RdxKind) {
1158 case RecurKind::Add:
1159 return Builder.CreateAddReduce(Src);
1160 case RecurKind::Mul:
1161 return Builder.CreateMulReduce(Src);
1162 case RecurKind::And:
1163 return Builder.CreateAndReduce(Src);
1164 case RecurKind::Or:
1165 return Builder.CreateOrReduce(Src);
1166 case RecurKind::Xor:
1167 return Builder.CreateXorReduce(Src);
1168 case RecurKind::FMulAdd:
1169 case RecurKind::FAdd:
1170 return Builder.CreateFAddReduce(ConstantFP::getNegativeZero(SrcVecEltTy),
1171 Src);
1172 case RecurKind::FMul:
1173 return Builder.CreateFMulReduce(ConstantFP::get(SrcVecEltTy, 1.0), Src);
1174 case RecurKind::SMax:
1175 return Builder.CreateIntMaxReduce(Src, true);
1176 case RecurKind::SMin:
1177 return Builder.CreateIntMinReduce(Src, true);
1178 case RecurKind::UMax:
1179 return Builder.CreateIntMaxReduce(Src, false);
1180 case RecurKind::UMin:
1181 return Builder.CreateIntMinReduce(Src, false);
1182 case RecurKind::FMax:
1183 return Builder.CreateFPMaxReduce(Src);
1184 case RecurKind::FMin:
1185 return Builder.CreateFPMinReduce(Src);
1186 case RecurKind::FMinimum:
1187 return Builder.CreateFPMinimumReduce(Src);
1188 case RecurKind::FMaximum:
1189 return Builder.CreateFPMaximumReduce(Src);
1190 default:
1191 llvm_unreachable("Unhandled opcode");
1192 }
1193}
1194
1196 const RecurrenceDescriptor &Desc, Value *Src,
1197 PHINode *OrigPhi) {
1198 // TODO: Support in-order reductions based on the recurrence descriptor.
1199 // All ops in the reduction inherit fast-math-flags from the recurrence
1200 // descriptor.
1202 B.setFastMathFlags(Desc.getFastMathFlags());
1203
1204 RecurKind RK = Desc.getRecurrenceKind();
1206 return createAnyOfTargetReduction(B, Src, Desc, OrigPhi);
1207
1208 return createSimpleTargetReduction(B, Src, RK);
1209}
1210
1213 Value *Src, Value *Start) {
1214 assert((Desc.getRecurrenceKind() == RecurKind::FAdd ||
1215 Desc.getRecurrenceKind() == RecurKind::FMulAdd) &&
1216 "Unexpected reduction kind");
1217 assert(Src->getType()->isVectorTy() && "Expected a vector type");
1218 assert(!Start->getType()->isVectorTy() && "Expected a scalar type");
1219
1220 return B.CreateFAddReduce(Start, Src);
1221}
1222
1224 bool IncludeWrapFlags) {
1225 auto *VecOp = dyn_cast<Instruction>(I);
1226 if (!VecOp)
1227 return;
1228 auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
1229 : dyn_cast<Instruction>(OpValue);
1230 if (!Intersection)
1231 return;
1232 const unsigned Opcode = Intersection->getOpcode();
1233 VecOp->copyIRFlags(Intersection, IncludeWrapFlags);
1234 for (auto *V : VL) {
1235 auto *Instr = dyn_cast<Instruction>(V);
1236 if (!Instr)
1237 continue;
1238 if (OpValue == nullptr || Opcode == Instr->getOpcode())
1239 VecOp->andIRFlags(V);
1240 }
1241}
1242
1243bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L,
1244 ScalarEvolution &SE) {
1245 const SCEV *Zero = SE.getZero(S->getType());
1246 return SE.isAvailableAtLoopEntry(S, L) &&
1247 SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, S, Zero);
1248}
1249
1251 ScalarEvolution &SE) {
1252 const SCEV *Zero = SE.getZero(S->getType());
1253 return SE.isAvailableAtLoopEntry(S, L) &&
1254 SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, S, Zero);
1255}
1256
1257bool llvm::isKnownPositiveInLoop(const SCEV *S, const Loop *L,
1258 ScalarEvolution &SE) {
1259 const SCEV *Zero = SE.getZero(S->getType());
1260 return SE.isAvailableAtLoopEntry(S, L) &&
1261 SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGT, S, Zero);
1262}
1263
1265 ScalarEvolution &SE) {
1266 const SCEV *Zero = SE.getZero(S->getType());
1267 return SE.isAvailableAtLoopEntry(S, L) &&
1268 SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLE, S, Zero);
1269}
1270
1272 bool Signed) {
1273 unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1276 auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1277 return SE.isAvailableAtLoopEntry(S, L) &&
1278 SE.isLoopEntryGuardedByCond(L, Predicate, S,
1279 SE.getConstant(Min));
1280}
1281
1283 bool Signed) {
1284 unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1287 auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1288 return SE.isAvailableAtLoopEntry(S, L) &&
1289 SE.isLoopEntryGuardedByCond(L, Predicate, S,
1290 SE.getConstant(Max));
1291}
1292
1293//===----------------------------------------------------------------------===//
1294// rewriteLoopExitValues - Optimize IV users outside the loop.
1295// As a side effect, reduces the amount of IV processing within the loop.
1296//===----------------------------------------------------------------------===//
1297
1298static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) {
1301 Visited.insert(I);
1302 WorkList.push_back(I);
1303 while (!WorkList.empty()) {
1304 const Instruction *Curr = WorkList.pop_back_val();
1305 // This use is outside the loop, nothing to do.
1306 if (!L->contains(Curr))
1307 continue;
1308 // Do we assume it is a "hard" use which will not be eliminated easily?
1309 if (Curr->mayHaveSideEffects())
1310 return true;
1311 // Otherwise, add all its users to worklist.
1312 for (const auto *U : Curr->users()) {
1313 auto *UI = cast<Instruction>(U);
1314 if (Visited.insert(UI).second)
1315 WorkList.push_back(UI);
1316 }
1317 }
1318 return false;
1319}
1320
1321// Collect information about PHI nodes which can be transformed in
1322// rewriteLoopExitValues.
1324 PHINode *PN; // For which PHI node is this replacement?
1325 unsigned Ith; // For which incoming value?
1326 const SCEV *ExpansionSCEV; // The SCEV of the incoming value we are rewriting.
1327 Instruction *ExpansionPoint; // Where we'd like to expand that SCEV?
1328 bool HighCost; // Is this expansion a high-cost?
1329
1330 RewritePhi(PHINode *P, unsigned I, const SCEV *Val, Instruction *ExpansionPt,
1331 bool H)
1332 : PN(P), Ith(I), ExpansionSCEV(Val), ExpansionPoint(ExpansionPt),
1333 HighCost(H) {}
1334};
1335
1336// Check whether it is possible to delete the loop after rewriting exit
1337// value. If it is possible, ignore ReplaceExitValue and do rewriting
1338// aggressively.
1339static bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
1340 BasicBlock *Preheader = L->getLoopPreheader();
1341 // If there is no preheader, the loop will not be deleted.
1342 if (!Preheader)
1343 return false;
1344
1345 // In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
1346 // We obviate multiple ExitingBlocks case for simplicity.
1347 // TODO: If we see testcase with multiple ExitingBlocks can be deleted
1348 // after exit value rewriting, we can enhance the logic here.
1349 SmallVector<BasicBlock *, 4> ExitingBlocks;
1350 L->getExitingBlocks(ExitingBlocks);
1352 L->getUniqueExitBlocks(ExitBlocks);
1353 if (ExitBlocks.size() != 1 || ExitingBlocks.size() != 1)
1354 return false;
1355
1356 BasicBlock *ExitBlock = ExitBlocks[0];
1357 BasicBlock::iterator BI = ExitBlock->begin();
1358 while (PHINode *P = dyn_cast<PHINode>(BI)) {
1359 Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);
1360
1361 // If the Incoming value of P is found in RewritePhiSet, we know it
1362 // could be rewritten to use a loop invariant value in transformation
1363 // phase later. Skip it in the loop invariant check below.
1364 bool found = false;
1365 for (const RewritePhi &Phi : RewritePhiSet) {
1366 unsigned i = Phi.Ith;
1367 if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
1368 found = true;
1369 break;
1370 }
1371 }
1372
1373 Instruction *I;
1374 if (!found && (I = dyn_cast<Instruction>(Incoming)))
1375 if (!L->hasLoopInvariantOperands(I))
1376 return false;
1377
1378 ++BI;
1379 }
1380
1381 for (auto *BB : L->blocks())
1382 if (llvm::any_of(*BB, [](Instruction &I) {
1383 return I.mayHaveSideEffects();
1384 }))
1385 return false;
1386
1387 return true;
1388}
1389
1390/// Checks if it is safe to call InductionDescriptor::isInductionPHI for \p Phi,
1391/// and returns true if this Phi is an induction phi in the loop. When
1392/// isInductionPHI returns true, \p ID will be also be set by isInductionPHI.
1393static bool checkIsIndPhi(PHINode *Phi, Loop *L, ScalarEvolution *SE,
1395 if (!Phi)
1396 return false;
1397 if (!L->getLoopPreheader())
1398 return false;
1399 if (Phi->getParent() != L->getHeader())
1400 return false;
1401 return InductionDescriptor::isInductionPHI(Phi, L, SE, ID);
1402}
1403
1405 ScalarEvolution *SE,
1406 const TargetTransformInfo *TTI,
1407 SCEVExpander &Rewriter, DominatorTree *DT,
1410 // Check a pre-condition.
1411 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
1412 "Indvars did not preserve LCSSA!");
1413
1414 SmallVector<BasicBlock*, 8> ExitBlocks;
1415 L->getUniqueExitBlocks(ExitBlocks);
1416
1417 SmallVector<RewritePhi, 8> RewritePhiSet;
1418 // Find all values that are computed inside the loop, but used outside of it.
1419 // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
1420 // the exit blocks of the loop to find them.
1421 for (BasicBlock *ExitBB : ExitBlocks) {
1422 // If there are no PHI nodes in this exit block, then no values defined
1423 // inside the loop are used on this path, skip it.
1424 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
1425 if (!PN) continue;
1426
1427 unsigned NumPreds = PN->getNumIncomingValues();
1428
1429 // Iterate over all of the PHI nodes.
1430 BasicBlock::iterator BBI = ExitBB->begin();
1431 while ((PN = dyn_cast<PHINode>(BBI++))) {
1432 if (PN->use_empty())
1433 continue; // dead use, don't replace it
1434
1435 if (!SE->isSCEVable(PN->getType()))
1436 continue;
1437
1438 // Iterate over all of the values in all the PHI nodes.
1439 for (unsigned i = 0; i != NumPreds; ++i) {
1440 // If the value being merged in is not integer or is not defined
1441 // in the loop, skip it.
1442 Value *InVal = PN->getIncomingValue(i);
1443 if (!isa<Instruction>(InVal))
1444 continue;
1445
1446 // If this pred is for a subloop, not L itself, skip it.
1447 if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
1448 continue; // The Block is in a subloop, skip it.
1449
1450 // Check that InVal is defined in the loop.
1451 Instruction *Inst = cast<Instruction>(InVal);
1452 if (!L->contains(Inst))
1453 continue;
1454
1455 // Find exit values which are induction variables in the loop, and are
1456 // unused in the loop, with the only use being the exit block PhiNode,
1457 // and the induction variable update binary operator.
1458 // The exit value can be replaced with the final value when it is cheap
1459 // to do so.
1462 PHINode *IndPhi = dyn_cast<PHINode>(Inst);
1463 if (IndPhi) {
1464 if (!checkIsIndPhi(IndPhi, L, SE, ID))
1465 continue;
1466 // This is an induction PHI. Check that the only users are PHI
1467 // nodes, and induction variable update binary operators.
1468 if (llvm::any_of(Inst->users(), [&](User *U) {
1469 if (!isa<PHINode>(U) && !isa<BinaryOperator>(U))
1470 return true;
1471 BinaryOperator *B = dyn_cast<BinaryOperator>(U);
1472 if (B && B != ID.getInductionBinOp())
1473 return true;
1474 return false;
1475 }))
1476 continue;
1477 } else {
1478 // If it is not an induction phi, it must be an induction update
1479 // binary operator with an induction phi user.
1480 BinaryOperator *B = dyn_cast<BinaryOperator>(Inst);
1481 if (!B)
1482 continue;
1483 if (llvm::any_of(Inst->users(), [&](User *U) {
1484 PHINode *Phi = dyn_cast<PHINode>(U);
1485 if (Phi != PN && !checkIsIndPhi(Phi, L, SE, ID))
1486 return true;
1487 return false;
1488 }))
1489 continue;
1490 if (B != ID.getInductionBinOp())
1491 continue;
1492 }
1493 }
1494
1495 // Okay, this instruction has a user outside of the current loop
1496 // and varies predictably *inside* the loop. Evaluate the value it
1497 // contains when the loop exits, if possible. We prefer to start with
1498 // expressions which are true for all exits (so as to maximize
1499 // expression reuse by the SCEVExpander), but resort to per-exit
1500 // evaluation if that fails.
1501 const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
1502 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1503 !SE->isLoopInvariant(ExitValue, L) ||
1504 !Rewriter.isSafeToExpand(ExitValue)) {
1505 // TODO: This should probably be sunk into SCEV in some way; maybe a
1506 // getSCEVForExit(SCEV*, L, ExitingBB)? It can be generalized for
1507 // most SCEV expressions and other recurrence types (e.g. shift
1508 // recurrences). Is there existing code we can reuse?
1509 const SCEV *ExitCount = SE->getExitCount(L, PN->getIncomingBlock(i));
1510 if (isa<SCEVCouldNotCompute>(ExitCount))
1511 continue;
1512 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Inst)))
1513 if (AddRec->getLoop() == L)
1514 ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
1515 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1516 !SE->isLoopInvariant(ExitValue, L) ||
1517 !Rewriter.isSafeToExpand(ExitValue))
1518 continue;
1519 }
1520
1521 // Computing the value outside of the loop brings no benefit if it is
1522 // definitely used inside the loop in a way which can not be optimized
1523 // away. Avoid doing so unless we know we have a value which computes
1524 // the ExitValue already. TODO: This should be merged into SCEV
1525 // expander to leverage its knowledge of existing expressions.
1526 if (ReplaceExitValue != AlwaysRepl && !isa<SCEVConstant>(ExitValue) &&
1527 !isa<SCEVUnknown>(ExitValue) && hasHardUserWithinLoop(L, Inst))
1528 continue;
1529
1530 // Check if expansions of this SCEV would count as being high cost.
1531 bool HighCost = Rewriter.isHighCostExpansion(
1532 ExitValue, L, SCEVCheapExpansionBudget, TTI, Inst);
1533
1534 // Note that we must not perform expansions until after
1535 // we query *all* the costs, because if we perform temporary expansion
1536 // inbetween, one that we might not intend to keep, said expansion
1537 // *may* affect cost calculation of the next SCEV's we'll query,
1538 // and next SCEV may errneously get smaller cost.
1539
1540 // Collect all the candidate PHINodes to be rewritten.
1541 Instruction *InsertPt =
1542 (isa<PHINode>(Inst) || isa<LandingPadInst>(Inst)) ?
1543 &*Inst->getParent()->getFirstInsertionPt() : Inst;
1544 RewritePhiSet.emplace_back(PN, i, ExitValue, InsertPt, HighCost);
1545 }
1546 }
1547 }
1548
1549 // TODO: evaluate whether it is beneficial to change how we calculate
1550 // high-cost: if we have SCEV 'A' which we know we will expand, should we
1551 // calculate the cost of other SCEV's after expanding SCEV 'A', thus
1552 // potentially giving cost bonus to those other SCEV's?
1553
1554 bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
1555 int NumReplaced = 0;
1556
1557 // Transformation.
1558 for (const RewritePhi &Phi : RewritePhiSet) {
1559 PHINode *PN = Phi.PN;
1560
1561 // Only do the rewrite when the ExitValue can be expanded cheaply.
1562 // If LoopCanBeDel is true, rewrite exit value aggressively.
1565 !LoopCanBeDel && Phi.HighCost)
1566 continue;
1567
1568 Value *ExitVal = Rewriter.expandCodeFor(
1569 Phi.ExpansionSCEV, Phi.PN->getType(), Phi.ExpansionPoint);
1570
1571 LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = " << *ExitVal
1572 << '\n'
1573 << " LoopVal = " << *(Phi.ExpansionPoint) << "\n");
1574
1575#ifndef NDEBUG
1576 // If we reuse an instruction from a loop which is neither L nor one of
1577 // its containing loops, we end up breaking LCSSA form for this loop by
1578 // creating a new use of its instruction.
1579 if (auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
1580 if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
1581 if (EVL != L)
1582 assert(EVL->contains(L) && "LCSSA breach detected!");
1583#endif
1584
1585 NumReplaced++;
1586 Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
1587 PN->setIncomingValue(Phi.Ith, ExitVal);
1588 // It's necessary to tell ScalarEvolution about this explicitly so that
1589 // it can walk the def-use list and forget all SCEVs, as it may not be
1590 // watching the PHI itself. Once the new exit value is in place, there
1591 // may not be a def-use connection between the loop and every instruction
1592 // which got a SCEVAddRecExpr for that loop.
1593 SE->forgetValue(PN);
1594
1595 // If this instruction is dead now, delete it. Don't do it now to avoid
1596 // invalidating iterators.
1597 if (isInstructionTriviallyDead(Inst, TLI))
1598 DeadInsts.push_back(Inst);
1599
1600 // Replace PN with ExitVal if that is legal and does not break LCSSA.
1601 if (PN->getNumIncomingValues() == 1 &&
1602 LI->replacementPreservesLCSSAForm(PN, ExitVal)) {
1603 PN->replaceAllUsesWith(ExitVal);
1604 PN->eraseFromParent();
1605 }
1606 }
1607
1608 // The insertion point instruction may have been deleted; clear it out
1609 // so that the rewriter doesn't trip over it later.
1610 Rewriter.clearInsertPoint();
1611 return NumReplaced;
1612}
1613
1614/// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
1615/// \p OrigLoop.
1616void llvm::setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
1617 Loop *RemainderLoop, uint64_t UF) {
1618 assert(UF > 0 && "Zero unrolled factor is not supported");
1619 assert(UnrolledLoop != RemainderLoop &&
1620 "Unrolled and Remainder loops are expected to distinct");
1621
1622 // Get number of iterations in the original scalar loop.
1623 unsigned OrigLoopInvocationWeight = 0;
1624 std::optional<unsigned> OrigAverageTripCount =
1625 getLoopEstimatedTripCount(OrigLoop, &OrigLoopInvocationWeight);
1626 if (!OrigAverageTripCount)
1627 return;
1628
1629 // Calculate number of iterations in unrolled loop.
1630 unsigned UnrolledAverageTripCount = *OrigAverageTripCount / UF;
1631 // Calculate number of iterations for remainder loop.
1632 unsigned RemainderAverageTripCount = *OrigAverageTripCount % UF;
1633
1634 setLoopEstimatedTripCount(UnrolledLoop, UnrolledAverageTripCount,
1635 OrigLoopInvocationWeight);
1636 setLoopEstimatedTripCount(RemainderLoop, RemainderAverageTripCount,
1637 OrigLoopInvocationWeight);
1638}
1639
1640/// Utility that implements appending of loops onto a worklist.
1641/// Loops are added in preorder (analogous for reverse postorder for trees),
1642/// and the worklist is processed LIFO.
1643template <typename RangeT>
1645 RangeT &&Loops, SmallPriorityWorklist<Loop *, 4> &Worklist) {
1646 // We use an internal worklist to build up the preorder traversal without
1647 // recursion.
1648 SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
1649
1650 // We walk the initial sequence of loops in reverse because we generally want
1651 // to visit defs before uses and the worklist is LIFO.
1652 for (Loop *RootL : Loops) {
1653 assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
1654 assert(PreOrderWorklist.empty() &&
1655 "Must start with an empty preorder walk worklist.");
1656 PreOrderWorklist.push_back(RootL);
1657 do {
1658 Loop *L = PreOrderWorklist.pop_back_val();
1659 PreOrderWorklist.append(L->begin(), L->end());
1660 PreOrderLoops.push_back(L);
1661 } while (!PreOrderWorklist.empty());
1662
1663 Worklist.insert(std::move(PreOrderLoops));
1664 PreOrderLoops.clear();
1665 }
1666}
1667
1668template <typename RangeT>
1672}
1673
1674template void llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>(
1676
1677template void
1678llvm::appendLoopsToWorklist<Loop &>(Loop &L,
1680
1683 appendReversedLoopsToWorklist(LI, Worklist);
1684}
1685
1687 LoopInfo *LI, LPPassManager *LPM) {
1688 Loop &New = *LI->AllocateLoop();
1689 if (PL)
1690 PL->addChildLoop(&New);
1691 else
1692 LI->addTopLevelLoop(&New);
1693
1694 if (LPM)
1695 LPM->addLoop(New);
1696
1697 // Add all of the blocks in L to the new loop.
1698 for (BasicBlock *BB : L->blocks())
1699 if (LI->getLoopFor(BB) == L)
1700 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), *LI);
1701
1702 // Add all of the subloops to the new loop.
1703 for (Loop *I : *L)
1704 cloneLoop(I, &New, VM, LI, LPM);
1705
1706 return &New;
1707}
1708
1709/// IR Values for the lower and upper bounds of a pointer evolution. We
1710/// need to use value-handles because SCEV expansion can invalidate previously
1711/// expanded values. Thus expansion of a pointer can invalidate the bounds for
1712/// a previous one.
1717};
1718
1719/// Expand code for the lower and upper bound of the pointer group \p CG
1720/// in \p TheLoop. \return the values for the bounds.
1722 Loop *TheLoop, Instruction *Loc,
1723 SCEVExpander &Exp, bool HoistRuntimeChecks) {
1724 LLVMContext &Ctx = Loc->getContext();
1725 Type *PtrArithTy = PointerType::get(Ctx, CG->AddressSpace);
1726
1727 Value *Start = nullptr, *End = nullptr;
1728 LLVM_DEBUG(dbgs() << "LAA: Adding RT check for range:\n");
1729 const SCEV *Low = CG->Low, *High = CG->High, *Stride = nullptr;
1730
1731 // If the Low and High values are themselves loop-variant, then we may want
1732 // to expand the range to include those covered by the outer loop as well.
1733 // There is a trade-off here with the advantage being that creating checks
1734 // using the expanded range permits the runtime memory checks to be hoisted
1735 // out of the outer loop. This reduces the cost of entering the inner loop,
1736 // which can be significant for low trip counts. The disadvantage is that
1737 // there is a chance we may now never enter the vectorized inner loop,
1738 // whereas using a restricted range check could have allowed us to enter at
1739 // least once. This is why the behaviour is not currently the default and is
1740 // controlled by the parameter 'HoistRuntimeChecks'.
1741 if (HoistRuntimeChecks && TheLoop->getParentLoop() &&
1742 isa<SCEVAddRecExpr>(High) && isa<SCEVAddRecExpr>(Low)) {
1743 auto *HighAR = cast<SCEVAddRecExpr>(High);
1744 auto *LowAR = cast<SCEVAddRecExpr>(Low);
1745 const Loop *OuterLoop = TheLoop->getParentLoop();
1746 const SCEV *Recur = LowAR->getStepRecurrence(*Exp.getSE());
1747 if (Recur == HighAR->getStepRecurrence(*Exp.getSE()) &&
1748 HighAR->getLoop() == OuterLoop && LowAR->getLoop() == OuterLoop) {
1749 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1750 const SCEV *OuterExitCount =
1751 Exp.getSE()->getExitCount(OuterLoop, OuterLoopLatch);
1752 if (!isa<SCEVCouldNotCompute>(OuterExitCount) &&
1753 OuterExitCount->getType()->isIntegerTy()) {
1754 const SCEV *NewHigh = cast<SCEVAddRecExpr>(High)->evaluateAtIteration(
1755 OuterExitCount, *Exp.getSE());
1756 if (!isa<SCEVCouldNotCompute>(NewHigh)) {
1757 LLVM_DEBUG(dbgs() << "LAA: Expanded RT check for range to include "
1758 "outer loop in order to permit hoisting\n");
1759 High = NewHigh;
1760 Low = cast<SCEVAddRecExpr>(Low)->getStart();
1761 // If there is a possibility that the stride is negative then we have
1762 // to generate extra checks to ensure the stride is positive.
1763 if (!Exp.getSE()->isKnownNonNegative(Recur)) {
1764 Stride = Recur;
1765 LLVM_DEBUG(dbgs() << "LAA: ... but need to check stride is "
1766 "positive: "
1767 << *Stride << '\n');
1768 }
1769 }
1770 }
1771 }
1772 }
1773
1774 Start = Exp.expandCodeFor(Low, PtrArithTy, Loc);
1775 End = Exp.expandCodeFor(High, PtrArithTy, Loc);
1776 if (CG->NeedsFreeze) {
1777 IRBuilder<> Builder(Loc);
1778 Start = Builder.CreateFreeze(Start, Start->getName() + ".fr");
1779 End = Builder.CreateFreeze(End, End->getName() + ".fr");
1780 }
1781 Value *StrideVal =
1782 Stride ? Exp.expandCodeFor(Stride, Stride->getType(), Loc) : nullptr;
1783 LLVM_DEBUG(dbgs() << "Start: " << *Low << " End: " << *High << "\n");
1784 return {Start, End, StrideVal};
1785}
1786
1787/// Turns a collection of checks into a collection of expanded upper and
1788/// lower bounds for both pointers in the check.
1791 Instruction *Loc, SCEVExpander &Exp, bool HoistRuntimeChecks) {
1793
1794 // Here we're relying on the SCEV Expander's cache to only emit code for the
1795 // same bounds once.
1796 transform(PointerChecks, std::back_inserter(ChecksWithBounds),
1797 [&](const RuntimePointerCheck &Check) {
1798 PointerBounds First = expandBounds(Check.first, L, Loc, Exp,
1800 Second = expandBounds(Check.second, L, Loc, Exp,
1802 return std::make_pair(First, Second);
1803 });
1804
1805 return ChecksWithBounds;
1806}
1807
1809 Instruction *Loc, Loop *TheLoop,
1810 const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
1811 SCEVExpander &Exp, bool HoistRuntimeChecks) {
1812 // TODO: Move noalias annotation code from LoopVersioning here and share with LV if possible.
1813 // TODO: Pass RtPtrChecking instead of PointerChecks and SE separately, if possible
1814 auto ExpandedChecks =
1815 expandBounds(PointerChecks, TheLoop, Loc, Exp, HoistRuntimeChecks);
1816
1817 LLVMContext &Ctx = Loc->getContext();
1818 IRBuilder<InstSimplifyFolder> ChkBuilder(Ctx,
1819 Loc->getModule()->getDataLayout());
1820 ChkBuilder.SetInsertPoint(Loc);
1821 // Our instructions might fold to a constant.
1822 Value *MemoryRuntimeCheck = nullptr;
1823
1824 for (const auto &Check : ExpandedChecks) {
1825 const PointerBounds &A = Check.first, &B = Check.second;
1826 // Check if two pointers (A and B) conflict where conflict is computed as:
1827 // start(A) <= end(B) && start(B) <= end(A)
1828
1829 assert((A.Start->getType()->getPointerAddressSpace() ==
1830 B.End->getType()->getPointerAddressSpace()) &&
1831 (B.Start->getType()->getPointerAddressSpace() ==
1832 A.End->getType()->getPointerAddressSpace()) &&
1833 "Trying to bounds check pointers with different address spaces");
1834
1835 // [A|B].Start points to the first accessed byte under base [A|B].
1836 // [A|B].End points to the last accessed byte, plus one.
1837 // There is no conflict when the intervals are disjoint:
1838 // NoConflict = (B.Start >= A.End) || (A.Start >= B.End)
1839 //
1840 // bound0 = (B.Start < A.End)
1841 // bound1 = (A.Start < B.End)
1842 // IsConflict = bound0 & bound1
1843 Value *Cmp0 = ChkBuilder.CreateICmpULT(A.Start, B.End, "bound0");
1844 Value *Cmp1 = ChkBuilder.CreateICmpULT(B.Start, A.End, "bound1");
1845 Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
1846 if (A.StrideToCheck) {
1847 Value *IsNegativeStride = ChkBuilder.CreateICmpSLT(
1848 A.StrideToCheck, ConstantInt::get(A.StrideToCheck->getType(), 0),
1849 "stride.check");
1850 IsConflict = ChkBuilder.CreateOr(IsConflict, IsNegativeStride);
1851 }
1852 if (B.StrideToCheck) {
1853 Value *IsNegativeStride = ChkBuilder.CreateICmpSLT(
1854 B.StrideToCheck, ConstantInt::get(B.StrideToCheck->getType(), 0),
1855 "stride.check");
1856 IsConflict = ChkBuilder.CreateOr(IsConflict, IsNegativeStride);
1857 }
1858 if (MemoryRuntimeCheck) {
1859 IsConflict =
1860 ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx");
1861 }
1862 MemoryRuntimeCheck = IsConflict;
1863 }
1864
1865 return MemoryRuntimeCheck;
1866}
1867
1869 Instruction *Loc, ArrayRef<PointerDiffInfo> Checks, SCEVExpander &Expander,
1870 function_ref<Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC) {
1871
1872 LLVMContext &Ctx = Loc->getContext();
1873 IRBuilder<InstSimplifyFolder> ChkBuilder(Ctx,
1874 Loc->getModule()->getDataLayout());
1875 ChkBuilder.SetInsertPoint(Loc);
1876 // Our instructions might fold to a constant.
1877 Value *MemoryRuntimeCheck = nullptr;
1878
1879 auto &SE = *Expander.getSE();
1880 // Map to keep track of created compares, The key is the pair of operands for
1881 // the compare, to allow detecting and re-using redundant compares.
1883 for (const auto &C : Checks) {
1884 Type *Ty = C.SinkStart->getType();
1885 // Compute VF * IC * AccessSize.
1886 auto *VFTimesUFTimesSize =
1887 ChkBuilder.CreateMul(GetVF(ChkBuilder, Ty->getScalarSizeInBits()),
1888 ConstantInt::get(Ty, IC * C.AccessSize));
1889 Value *Diff = Expander.expandCodeFor(
1890 SE.getMinusSCEV(C.SinkStart, C.SrcStart), Ty, Loc);
1891
1892 // Check if the same compare has already been created earlier. In that case,
1893 // there is no need to check it again.
1894 Value *IsConflict = SeenCompares.lookup({Diff, VFTimesUFTimesSize});
1895 if (IsConflict)
1896 continue;
1897
1898 IsConflict =
1899 ChkBuilder.CreateICmpULT(Diff, VFTimesUFTimesSize, "diff.check");
1900 SeenCompares.insert({{Diff, VFTimesUFTimesSize}, IsConflict});
1901 if (C.NeedsFreeze)
1902 IsConflict =
1903 ChkBuilder.CreateFreeze(IsConflict, IsConflict->getName() + ".fr");
1904 if (MemoryRuntimeCheck) {
1905 IsConflict =
1906 ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx");
1907 }
1908 MemoryRuntimeCheck = IsConflict;
1909 }
1910
1911 return MemoryRuntimeCheck;
1912}
1913
1914std::optional<IVConditionInfo>
1916 const MemorySSA &MSSA, AAResults &AA) {
1917 auto *TI = dyn_cast<BranchInst>(L.getHeader()->getTerminator());
1918 if (!TI || !TI->isConditional())
1919 return {};
1920
1921 auto *CondI = dyn_cast<Instruction>(TI->getCondition());
1922 // The case with the condition outside the loop should already be handled
1923 // earlier.
1924 // Allow CmpInst and TruncInsts as they may be users of load instructions
1925 // and have potential for partial unswitching
1926 if (!CondI || !isa<CmpInst, TruncInst>(CondI) || !L.contains(CondI))
1927 return {};
1928
1929 SmallVector<Instruction *> InstToDuplicate;
1930 InstToDuplicate.push_back(CondI);
1931
1932 SmallVector<Value *, 4> WorkList;
1933 WorkList.append(CondI->op_begin(), CondI->op_end());
1934
1935 SmallVector<MemoryAccess *, 4> AccessesToCheck;
1936 SmallVector<MemoryLocation, 4> AccessedLocs;
1937 while (!WorkList.empty()) {
1938 Instruction *I = dyn_cast<Instruction>(WorkList.pop_back_val());
1939 if (!I || !L.contains(I))
1940 continue;
1941
1942 // TODO: support additional instructions.
1943 if (!isa<LoadInst>(I) && !isa<GetElementPtrInst>(I))
1944 return {};
1945
1946 // Do not duplicate volatile and atomic loads.
1947 if (auto *LI = dyn_cast<LoadInst>(I))
1948 if (LI->isVolatile() || LI->isAtomic())
1949 return {};
1950
1951 InstToDuplicate.push_back(I);
1952 if (MemoryAccess *MA = MSSA.getMemoryAccess(I)) {
1953 if (auto *MemUse = dyn_cast_or_null<MemoryUse>(MA)) {
1954 // Queue the defining access to check for alias checks.
1955 AccessesToCheck.push_back(MemUse->getDefiningAccess());
1956 AccessedLocs.push_back(MemoryLocation::get(I));
1957 } else {
1958 // MemoryDefs may clobber the location or may be atomic memory
1959 // operations. Bail out.
1960 return {};
1961 }
1962 }
1963 WorkList.append(I->op_begin(), I->op_end());
1964 }
1965
1966 if (InstToDuplicate.empty())
1967 return {};
1968
1969 SmallVector<BasicBlock *, 4> ExitingBlocks;
1970 L.getExitingBlocks(ExitingBlocks);
1971 auto HasNoClobbersOnPath =
1972 [&L, &AA, &AccessedLocs, &ExitingBlocks, &InstToDuplicate,
1973 MSSAThreshold](BasicBlock *Succ, BasicBlock *Header,
1974 SmallVector<MemoryAccess *, 4> AccessesToCheck)
1975 -> std::optional<IVConditionInfo> {
1977 // First, collect all blocks in the loop that are on a patch from Succ
1978 // to the header.
1980 WorkList.push_back(Succ);
1981 WorkList.push_back(Header);
1983 Seen.insert(Header);
1984 Info.PathIsNoop &=
1985 all_of(*Header, [](Instruction &I) { return !I.mayHaveSideEffects(); });
1986
1987 while (!WorkList.empty()) {
1988 BasicBlock *Current = WorkList.pop_back_val();
1989 if (!L.contains(Current))
1990 continue;
1991 const auto &SeenIns = Seen.insert(Current);
1992 if (!SeenIns.second)
1993 continue;
1994
1995 Info.PathIsNoop &= all_of(
1996 *Current, [](Instruction &I) { return !I.mayHaveSideEffects(); });
1997 WorkList.append(succ_begin(Current), succ_end(Current));
1998 }
1999
2000 // Require at least 2 blocks on a path through the loop. This skips
2001 // paths that directly exit the loop.
2002 if (Seen.size() < 2)
2003 return {};
2004
2005 // Next, check if there are any MemoryDefs that are on the path through
2006 // the loop (in the Seen set) and they may-alias any of the locations in
2007 // AccessedLocs. If that is the case, they may modify the condition and
2008 // partial unswitching is not possible.
2009 SmallPtrSet<MemoryAccess *, 4> SeenAccesses;
2010 while (!AccessesToCheck.empty()) {
2011 MemoryAccess *Current = AccessesToCheck.pop_back_val();
2012 auto SeenI = SeenAccesses.insert(Current);
2013 if (!SeenI.second || !Seen.contains(Current->getBlock()))
2014 continue;
2015
2016 // Bail out if exceeded the threshold.
2017 if (SeenAccesses.size() >= MSSAThreshold)
2018 return {};
2019
2020 // MemoryUse are read-only accesses.
2021 if (isa<MemoryUse>(Current))
2022 continue;
2023
2024 // For a MemoryDef, check if is aliases any of the location feeding
2025 // the original condition.
2026 if (auto *CurrentDef = dyn_cast<MemoryDef>(Current)) {
2027 if (any_of(AccessedLocs, [&AA, CurrentDef](MemoryLocation &Loc) {
2028 return isModSet(
2029 AA.getModRefInfo(CurrentDef->getMemoryInst(), Loc));
2030 }))
2031 return {};
2032 }
2033
2034 for (Use &U : Current->uses())
2035 AccessesToCheck.push_back(cast<MemoryAccess>(U.getUser()));
2036 }
2037
2038 // We could also allow loops with known trip counts without mustprogress,
2039 // but ScalarEvolution may not be available.
2040 Info.PathIsNoop &= isMustProgress(&L);
2041
2042 // If the path is considered a no-op so far, check if it reaches a
2043 // single exit block without any phis. This ensures no values from the
2044 // loop are used outside of the loop.
2045 if (Info.PathIsNoop) {
2046 for (auto *Exiting : ExitingBlocks) {
2047 if (!Seen.contains(Exiting))
2048 continue;
2049 for (auto *Succ : successors(Exiting)) {
2050 if (L.contains(Succ))
2051 continue;
2052
2053 Info.PathIsNoop &= Succ->phis().empty() &&
2054 (!Info.ExitForPath || Info.ExitForPath == Succ);
2055 if (!Info.PathIsNoop)
2056 break;
2057 assert((!Info.ExitForPath || Info.ExitForPath == Succ) &&
2058 "cannot have multiple exit blocks");
2059 Info.ExitForPath = Succ;
2060 }
2061 }
2062 }
2063 if (!Info.ExitForPath)
2064 Info.PathIsNoop = false;
2065
2066 Info.InstToDuplicate = InstToDuplicate;
2067 return Info;
2068 };
2069
2070 // If we branch to the same successor, partial unswitching will not be
2071 // beneficial.
2072 if (TI->getSuccessor(0) == TI->getSuccessor(1))
2073 return {};
2074
2075 if (auto Info = HasNoClobbersOnPath(TI->getSuccessor(0), L.getHeader(),
2076 AccessesToCheck)) {
2077 Info->KnownValue = ConstantInt::getTrue(TI->getContext());
2078 return Info;
2079 }
2080 if (auto Info = HasNoClobbersOnPath(TI->getSuccessor(1), L.getHeader(),
2081 AccessesToCheck)) {
2082 Info->KnownValue = ConstantInt::getFalse(TI->getContext());
2083 return Info;
2084 }
2085
2086 return {};
2087}
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:1298
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:1721
static bool canLoopBeDeleted(Loop *L, SmallVector< RewritePhi, 8 > &RewritePhiSet)
Definition: LoopUtils.cpp:1339
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:1393
#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:77
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:185
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:188
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:195
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:198
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
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:528
static Constant * getNegativeZero(Type *Ty)
Definition: Constants.h:307
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:852
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:859
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:161
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:314
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:2258
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2461
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
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:1090
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:2536
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:2367
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:2495
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:2274
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:2667
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:83
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:1635
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:165
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:985
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:701
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:1905
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:719
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:1830
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:258
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:1808
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:1264
Value * createSimpleTargetReduction(IRBuilderBase &B, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:1154
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:1644
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:1037
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:1282
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:400
uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator)
Returns the integer nearest(Numerator / Denominator).
Definition: MathExtras.h:433
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:275
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:1079
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:1211
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:1223
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:1257
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:2833
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:84
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
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:1616
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:1669
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:1243
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:1404
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:1868
RecurKind getMinMaxReductionRecurKind(Intrinsic::ID RdxID)
Returns the recurence kind used when expanding a min/max reduction.
Definition: LoopUtils.cpp:996
ReplaceExitVal
Definition: LoopUtils.h:452
@ UnusedIndVarInLoop
Definition: LoopUtils.h:456
@ OnlyCheapRepl
Definition: LoopUtils.h:454
@ AlwaysRepl
Definition: LoopUtils.h:457
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:1915
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:1271
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:1250
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:1054
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:1195
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:1686
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:1119
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:1713
TrackingVH< Value > Start
Definition: LoopUtils.cpp:1714
TrackingVH< Value > End
Definition: LoopUtils.cpp:1715
Value * StrideToCheck
Definition: LoopUtils.cpp:1716
unsigned Ith
Definition: LoopUtils.cpp:1325
RewritePhi(PHINode *P, unsigned I, const SCEV *Val, Instruction *ExpansionPt, bool H)
Definition: LoopUtils.cpp:1330
const SCEV * ExpansionSCEV
Definition: LoopUtils.cpp:1326
PHINode * PN
Definition: LoopUtils.cpp:1324
Instruction * ExpansionPoint
Definition: LoopUtils.cpp:1327
Description of the encoding of one expression Op.
Struct to hold information about a partially invariant condition.
Definition: LoopUtils.h:530
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.