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