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
314 // Effectively "DCE" unrolled iterations that are beyond the max tripcount
315 // and will never be executed.
316 if (MaxTripCount && ULO.Count > MaxTripCount)
317 ULO.Count = MaxTripCount;
318
319 struct ExitInfo {
320 unsigned TripCount;
321 unsigned TripMultiple;
322 unsigned BreakoutTrip;
323 bool ExitOnTrue;
324 BasicBlock *FirstExitingBlock = nullptr;
325 SmallVector<BasicBlock *> ExitingBlocks;
326 };
328 SmallVector<BasicBlock *, 4> ExitingBlocks;
329 L->getExitingBlocks(ExitingBlocks);
330 for (auto *ExitingBlock : ExitingBlocks) {
331 // The folding code is not prepared to deal with non-branch instructions
332 // right now.
333 auto *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
334 if (!BI)
335 continue;
336
337 ExitInfo &Info = ExitInfos.try_emplace(ExitingBlock).first->second;
338 Info.TripCount = SE->getSmallConstantTripCount(L, ExitingBlock);
339 Info.TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock);
340 if (Info.TripCount != 0) {
341 Info.BreakoutTrip = Info.TripCount % ULO.Count;
342 Info.TripMultiple = 0;
343 } else {
344 Info.BreakoutTrip = Info.TripMultiple =
345 (unsigned)std::gcd(ULO.Count, Info.TripMultiple);
346 }
347 Info.ExitOnTrue = !L->contains(BI->getSuccessor(0));
348 Info.ExitingBlocks.push_back(ExitingBlock);
349 LLVM_DEBUG(dbgs() << " Exiting block %" << ExitingBlock->getName()
350 << ": TripCount=" << Info.TripCount
351 << ", TripMultiple=" << Info.TripMultiple
352 << ", BreakoutTrip=" << Info.BreakoutTrip << "\n");
353 }
354
355 // Are we eliminating the loop control altogether? Note that we can know
356 // we're eliminating the backedge without knowing exactly which iteration
357 // of the unrolled body exits.
358 const bool CompletelyUnroll = ULO.Count == MaxTripCount;
359
360 const bool PreserveOnlyFirst = CompletelyUnroll && MaxOrZero;
361
362 // There's no point in performing runtime unrolling if this unroll count
363 // results in a full unroll.
364 if (CompletelyUnroll)
365 ULO.Runtime = false;
366
367 // Go through all exits of L and see if there are any phi-nodes there. We just
368 // conservatively assume that they're inserted to preserve LCSSA form, which
369 // means that complete unrolling might break this form. We need to either fix
370 // it in-place after the transformation, or entirely rebuild LCSSA. TODO: For
371 // now we just recompute LCSSA for the outer loop, but it should be possible
372 // to fix it in-place.
373 bool NeedToFixLCSSA =
374 PreserveLCSSA && CompletelyUnroll &&
375 any_of(ExitBlocks,
376 [](const BasicBlock *BB) { return isa<PHINode>(BB->begin()); });
377
378 // The current loop unroll pass can unroll loops that have
379 // (1) single latch; and
380 // (2a) latch is unconditional; or
381 // (2b) latch is conditional and is an exiting block
382 // FIXME: The implementation can be extended to work with more complicated
383 // cases, e.g. loops with multiple latches.
384 BranchInst *LatchBI = dyn_cast<BranchInst>(LatchBlock->getTerminator());
385
386 // A conditional branch which exits the loop, which can be optimized to an
387 // unconditional branch in the unrolled loop in some cases.
388 bool LatchIsExiting = L->isLoopExiting(LatchBlock);
389 if (!LatchBI || (LatchBI->isConditional() && !LatchIsExiting)) {
391 dbgs() << "Can't unroll; a conditional latch must exit the loop");
392 return LoopUnrollResult::Unmodified;
393 }
394
395 // Loops containing convergent instructions cannot use runtime unrolling,
396 // as the prologue/epilogue may add additional control-dependencies to
397 // convergent operations.
399 {
400 bool HasConvergent = false;
401 for (auto &BB : L->blocks())
402 for (auto &I : *BB)
403 if (auto *CB = dyn_cast<CallBase>(&I))
404 HasConvergent |= CB->isConvergent();
405 assert((!HasConvergent || !ULO.Runtime) &&
406 "Can't runtime unroll if loop contains a convergent operation.");
407 });
408
409 bool EpilogProfitability =
412
413 if (ULO.Runtime &&
415 EpilogProfitability, ULO.UnrollRemainder,
416 ULO.ForgetAllSCEV, LI, SE, DT, AC, TTI,
417 PreserveLCSSA, RemainderLoop)) {
418 if (ULO.Force)
419 ULO.Runtime = false;
420 else {
421 LLVM_DEBUG(dbgs() << "Won't unroll; remainder loop could not be "
422 "generated when assuming runtime trip count\n");
423 return LoopUnrollResult::Unmodified;
424 }
425 }
426
427 using namespace ore;
428 // Report the unrolling decision.
429 if (CompletelyUnroll) {
430 LLVM_DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName()
431 << " with trip count " << ULO.Count << "!\n");
432 if (ORE)
433 ORE->emit([&]() {
434 return OptimizationRemark(DEBUG_TYPE, "FullyUnrolled", L->getStartLoc(),
435 L->getHeader())
436 << "completely unrolled loop with "
437 << NV("UnrollCount", ULO.Count) << " iterations";
438 });
439 } else {
440 LLVM_DEBUG(dbgs() << "UNROLLING loop %" << Header->getName() << " by "
441 << ULO.Count);
442 if (ULO.Runtime)
443 LLVM_DEBUG(dbgs() << " with run-time trip count");
444 LLVM_DEBUG(dbgs() << "!\n");
445
446 if (ORE)
447 ORE->emit([&]() {
448 OptimizationRemark Diag(DEBUG_TYPE, "PartialUnrolled", L->getStartLoc(),
449 L->getHeader());
450 Diag << "unrolled loop by a factor of " << NV("UnrollCount", ULO.Count);
451 if (ULO.Runtime)
452 Diag << " with run-time trip count";
453 return Diag;
454 });
455 }
456
457 // We are going to make changes to this loop. SCEV may be keeping cached info
458 // about it, in particular about backedge taken count. The changes we make
459 // are guaranteed to invalidate this information for our loop. It is tempting
460 // to only invalidate the loop being unrolled, but it is incorrect as long as
461 // all exiting branches from all inner loops have impact on the outer loops,
462 // and if something changes inside them then any of outer loops may also
463 // change. When we forget outermost loop, we also forget all contained loops
464 // and this is what we need here.
465 if (SE) {
466 if (ULO.ForgetAllSCEV)
467 SE->forgetAllLoops();
468 else {
469 SE->forgetTopmostLoop(L);
471 }
472 }
473
474 if (!LatchIsExiting)
475 ++NumUnrolledNotLatch;
476
477 // For the first iteration of the loop, we should use the precloned values for
478 // PHI nodes. Insert associations now.
479 ValueToValueMapTy LastValueMap;
480 std::vector<PHINode*> OrigPHINode;
481 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
482 OrigPHINode.push_back(cast<PHINode>(I));
483 }
484
485 std::vector<BasicBlock *> Headers;
486 std::vector<BasicBlock *> Latches;
487 Headers.push_back(Header);
488 Latches.push_back(LatchBlock);
489
490 // The current on-the-fly SSA update requires blocks to be processed in
491 // reverse postorder so that LastValueMap contains the correct value at each
492 // exit.
493 LoopBlocksDFS DFS(L);
494 DFS.perform(LI);
495
496 // Stash the DFS iterators before adding blocks to the loop.
497 LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO();
498 LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO();
499
500 std::vector<BasicBlock*> UnrolledLoopBlocks = L->getBlocks();
501
502 // Loop Unrolling might create new loops. While we do preserve LoopInfo, we
503 // might break loop-simplified form for these loops (as they, e.g., would
504 // share the same exit blocks). We'll keep track of loops for which we can
505 // break this so that later we can re-simplify them.
506 SmallSetVector<Loop *, 4> LoopsToSimplify;
507 for (Loop *SubLoop : *L)
508 LoopsToSimplify.insert(SubLoop);
509
510 // When a FSDiscriminator is enabled, we don't need to add the multiply
511 // factors to the discriminators.
512 if (Header->getParent()->shouldEmitDebugInfoForProfiling() &&
514 for (BasicBlock *BB : L->getBlocks())
515 for (Instruction &I : *BB)
516 if (!isa<DbgInfoIntrinsic>(&I))
517 if (const DILocation *DIL = I.getDebugLoc()) {
518 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(ULO.Count);
519 if (NewDIL)
520 I.setDebugLoc(*NewDIL);
521 else
523 << "Failed to create new discriminator: "
524 << DIL->getFilename() << " Line: " << DIL->getLine());
525 }
526
527 // Identify what noalias metadata is inside the loop: if it is inside the
528 // loop, the associated metadata must be cloned for each iteration.
529 SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes;
530 identifyNoAliasScopesToClone(L->getBlocks(), LoopLocalNoAliasDeclScopes);
531
532 // We place the unrolled iterations immediately after the original loop
533 // latch. This is a reasonable default placement if we don't have block
534 // frequencies, and if we do, well the layout will be adjusted later.
535 auto BlockInsertPt = std::next(LatchBlock->getIterator());
536 for (unsigned It = 1; It != ULO.Count; ++It) {
539 NewLoops[L] = L;
540
541 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
543 BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It));
544 Header->getParent()->insert(BlockInsertPt, New);
545
546 assert((*BB != Header || LI->getLoopFor(*BB) == L) &&
547 "Header should not be in a sub-loop");
548 // Tell LI about New.
549 const Loop *OldLoop = addClonedBlockToLoopInfo(*BB, New, LI, NewLoops);
550 if (OldLoop)
551 LoopsToSimplify.insert(NewLoops[OldLoop]);
552
553 if (*BB == Header)
554 // Loop over all of the PHI nodes in the block, changing them to use
555 // the incoming values from the previous block.
556 for (PHINode *OrigPHI : OrigPHINode) {
557 PHINode *NewPHI = cast<PHINode>(VMap[OrigPHI]);
558 Value *InVal = NewPHI->getIncomingValueForBlock(LatchBlock);
559 if (Instruction *InValI = dyn_cast<Instruction>(InVal))
560 if (It > 1 && L->contains(InValI))
561 InVal = LastValueMap[InValI];
562 VMap[OrigPHI] = InVal;
563 NewPHI->eraseFromParent();
564 }
565
566 // Update our running map of newest clones
567 LastValueMap[*BB] = New;
568 for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();
569 VI != VE; ++VI)
570 LastValueMap[VI->first] = VI->second;
571
572 // Add phi entries for newly created values to all exit blocks.
573 for (BasicBlock *Succ : successors(*BB)) {
574 if (L->contains(Succ))
575 continue;
576 for (PHINode &PHI : Succ->phis()) {
577 Value *Incoming = PHI.getIncomingValueForBlock(*BB);
578 ValueToValueMapTy::iterator It = LastValueMap.find(Incoming);
579 if (It != LastValueMap.end())
580 Incoming = It->second;
581 PHI.addIncoming(Incoming, New);
582 SE->forgetValue(&PHI);
583 }
584 }
585 // Keep track of new headers and latches as we create them, so that
586 // we can insert the proper branches later.
587 if (*BB == Header)
588 Headers.push_back(New);
589 if (*BB == LatchBlock)
590 Latches.push_back(New);
591
592 // Keep track of the exiting block and its successor block contained in
593 // the loop for the current iteration.
594 auto ExitInfoIt = ExitInfos.find(*BB);
595 if (ExitInfoIt != ExitInfos.end())
596 ExitInfoIt->second.ExitingBlocks.push_back(New);
597
598 NewBlocks.push_back(New);
599 UnrolledLoopBlocks.push_back(New);
600
601 // Update DomTree: since we just copy the loop body, and each copy has a
602 // dedicated entry block (copy of the header block), this header's copy
603 // dominates all copied blocks. That means, dominance relations in the
604 // copied body are the same as in the original body.
605 if (*BB == Header)
606 DT->addNewBlock(New, Latches[It - 1]);
607 else {
608 auto BBDomNode = DT->getNode(*BB);
609 auto BBIDom = BBDomNode->getIDom();
610 BasicBlock *OriginalBBIDom = BBIDom->getBlock();
611 DT->addNewBlock(
612 New, cast<BasicBlock>(LastValueMap[cast<Value>(OriginalBBIDom)]));
613 }
614 }
615
616 // Remap all instructions in the most recent iteration
617 remapInstructionsInBlocks(NewBlocks, LastValueMap);
618 for (BasicBlock *NewBlock : NewBlocks)
619 for (Instruction &I : *NewBlock)
620 if (auto *II = dyn_cast<AssumeInst>(&I))
621 AC->registerAssumption(II);
622
623 {
624 // Identify what other metadata depends on the cloned version. After
625 // cloning, replace the metadata with the corrected version for both
626 // memory instructions and noalias intrinsics.
627 std::string ext = (Twine("It") + Twine(It)).str();
628 cloneAndAdaptNoAliasScopes(LoopLocalNoAliasDeclScopes, NewBlocks,
629 Header->getContext(), ext);
630 }
631 }
632
633 // Loop over the PHI nodes in the original block, setting incoming values.
634 for (PHINode *PN : OrigPHINode) {
635 if (CompletelyUnroll) {
636 PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));
637 PN->eraseFromParent();
638 } else if (ULO.Count > 1) {
639 Value *InVal = PN->removeIncomingValue(LatchBlock, false);
640 // If this value was defined in the loop, take the value defined by the
641 // last iteration of the loop.
642 if (Instruction *InValI = dyn_cast<Instruction>(InVal)) {
643 if (L->contains(InValI))
644 InVal = LastValueMap[InVal];
645 }
646 assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch");
647 PN->addIncoming(InVal, Latches.back());
648 }
649 }
650
651 // Connect latches of the unrolled iterations to the headers of the next
652 // iteration. Currently they point to the header of the same iteration.
653 for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
654 unsigned j = (i + 1) % e;
655 Latches[i]->getTerminator()->replaceSuccessorWith(Headers[i], Headers[j]);
656 }
657
658 // Update dominators of blocks we might reach through exits.
659 // Immediate dominator of such block might change, because we add more
660 // routes which can lead to the exit: we can now reach it from the copied
661 // iterations too.
662 if (ULO.Count > 1) {
663 for (auto *BB : OriginalLoopBlocks) {
664 auto *BBDomNode = DT->getNode(BB);
665 SmallVector<BasicBlock *, 16> ChildrenToUpdate;
666 for (auto *ChildDomNode : BBDomNode->children()) {
667 auto *ChildBB = ChildDomNode->getBlock();
668 if (!L->contains(ChildBB))
669 ChildrenToUpdate.push_back(ChildBB);
670 }
671 // The new idom of the block will be the nearest common dominator
672 // of all copies of the previous idom. This is equivalent to the
673 // nearest common dominator of the previous idom and the first latch,
674 // which dominates all copies of the previous idom.
675 BasicBlock *NewIDom = DT->findNearestCommonDominator(BB, LatchBlock);
676 for (auto *ChildBB : ChildrenToUpdate)
677 DT->changeImmediateDominator(ChildBB, NewIDom);
678 }
679 }
680
682 DT->verify(DominatorTree::VerificationLevel::Fast));
683
685 auto SetDest = [&](BasicBlock *Src, bool WillExit, bool ExitOnTrue) {
686 auto *Term = cast<BranchInst>(Src->getTerminator());
687 const unsigned Idx = ExitOnTrue ^ WillExit;
688 BasicBlock *Dest = Term->getSuccessor(Idx);
689 BasicBlock *DeadSucc = Term->getSuccessor(1-Idx);
690
691 // Remove predecessors from all non-Dest successors.
692 DeadSucc->removePredecessor(Src, /* KeepOneInputPHIs */ true);
693
694 // Replace the conditional branch with an unconditional one.
695 BranchInst::Create(Dest, Term);
696 Term->eraseFromParent();
697
698 DTUpdates.emplace_back(DominatorTree::Delete, Src, DeadSucc);
699 };
700
701 auto WillExit = [&](const ExitInfo &Info, unsigned i, unsigned j,
702 bool IsLatch) -> std::optional<bool> {
703 if (CompletelyUnroll) {
704 if (PreserveOnlyFirst) {
705 if (i == 0)
706 return std::nullopt;
707 return j == 0;
708 }
709 // Complete (but possibly inexact) unrolling
710 if (j == 0)
711 return true;
712 if (Info.TripCount && j != Info.TripCount)
713 return false;
714 return std::nullopt;
715 }
716
717 if (ULO.Runtime) {
718 // If runtime unrolling inserts a prologue, information about non-latch
719 // exits may be stale.
720 if (IsLatch && j != 0)
721 return false;
722 return std::nullopt;
723 }
724
725 if (j != Info.BreakoutTrip &&
726 (Info.TripMultiple == 0 || j % Info.TripMultiple != 0)) {
727 // If we know the trip count or a multiple of it, we can safely use an
728 // unconditional branch for some iterations.
729 return false;
730 }
731 return std::nullopt;
732 };
733
734 // Fold branches for iterations where we know that they will exit or not
735 // exit.
736 for (auto &Pair : ExitInfos) {
737 ExitInfo &Info = Pair.second;
738 for (unsigned i = 0, e = Info.ExitingBlocks.size(); i != e; ++i) {
739 // The branch destination.
740 unsigned j = (i + 1) % e;
741 bool IsLatch = Pair.first == LatchBlock;
742 std::optional<bool> KnownWillExit = WillExit(Info, i, j, IsLatch);
743 if (!KnownWillExit) {
744 if (!Info.FirstExitingBlock)
745 Info.FirstExitingBlock = Info.ExitingBlocks[i];
746 continue;
747 }
748
749 // We don't fold known-exiting branches for non-latch exits here,
750 // because this ensures that both all loop blocks and all exit blocks
751 // remain reachable in the CFG.
752 // TODO: We could fold these branches, but it would require much more
753 // sophisticated updates to LoopInfo.
754 if (*KnownWillExit && !IsLatch) {
755 if (!Info.FirstExitingBlock)
756 Info.FirstExitingBlock = Info.ExitingBlocks[i];
757 continue;
758 }
759
760 SetDest(Info.ExitingBlocks[i], *KnownWillExit, Info.ExitOnTrue);
761 }
762 }
763
764 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
765 DomTreeUpdater *DTUToUse = &DTU;
766 if (ExitingBlocks.size() == 1 && ExitInfos.size() == 1) {
767 // Manually update the DT if there's a single exiting node. In that case
768 // there's a single exit node and it is sufficient to update the nodes
769 // immediately dominated by the original exiting block. They will become
770 // dominated by the first exiting block that leaves the loop after
771 // unrolling. Note that the CFG inside the loop does not change, so there's
772 // no need to update the DT inside the unrolled loop.
773 DTUToUse = nullptr;
774 auto &[OriginalExit, Info] = *ExitInfos.begin();
775 if (!Info.FirstExitingBlock)
776 Info.FirstExitingBlock = Info.ExitingBlocks.back();
777 for (auto *C : to_vector(DT->getNode(OriginalExit)->children())) {
778 if (L->contains(C->getBlock()))
779 continue;
780 C->setIDom(DT->getNode(Info.FirstExitingBlock));
781 }
782 } else {
783 DTU.applyUpdates(DTUpdates);
784 }
785
786 // When completely unrolling, the last latch becomes unreachable.
787 if (!LatchIsExiting && CompletelyUnroll) {
788 // There is no need to update the DT here, because there must be a unique
789 // latch. Hence if the latch is not exiting it must directly branch back to
790 // the original loop header and does not dominate any nodes.
791 assert(LatchBlock->getSingleSuccessor() && "Loop with multiple latches?");
792 changeToUnreachable(Latches.back()->getTerminator(), PreserveLCSSA);
793 }
794
795 // Merge adjacent basic blocks, if possible.
796 for (BasicBlock *Latch : Latches) {
797 BranchInst *Term = dyn_cast<BranchInst>(Latch->getTerminator());
798 assert((Term ||
799 (CompletelyUnroll && !LatchIsExiting && Latch == Latches.back())) &&
800 "Need a branch as terminator, except when fully unrolling with "
801 "unconditional latch");
802 if (Term && Term->isUnconditional()) {
803 BasicBlock *Dest = Term->getSuccessor(0);
804 BasicBlock *Fold = Dest->getUniquePredecessor();
805 if (MergeBlockIntoPredecessor(Dest, /*DTU=*/DTUToUse, LI,
806 /*MSSAU=*/nullptr, /*MemDep=*/nullptr,
807 /*PredecessorWithTwoSuccessors=*/false,
808 DTUToUse ? nullptr : DT)) {
809 // Dest has been folded into Fold. Update our worklists accordingly.
810 std::replace(Latches.begin(), Latches.end(), Dest, Fold);
811 llvm::erase_value(UnrolledLoopBlocks, Dest);
812 }
813 }
814 }
815
816 if (DTUToUse) {
817 // Apply updates to the DomTree.
818 DT = &DTU.getDomTree();
819 }
821 DT->verify(DominatorTree::VerificationLevel::Fast));
822
823 // At this point, the code is well formed. We now simplify the unrolled loop,
824 // doing constant propagation and dead code elimination as we go.
825 simplifyLoopAfterUnroll(L, !CompletelyUnroll && ULO.Count > 1, LI, SE, DT, AC,
826 TTI);
827
828 NumCompletelyUnrolled += CompletelyUnroll;
829 ++NumUnrolled;
830
831 Loop *OuterL = L->getParentLoop();
832 // Update LoopInfo if the loop is completely removed.
833 if (CompletelyUnroll)
834 LI->erase(L);
835
836 // LoopInfo should not be valid, confirm that.
838 LI->verify(*DT);
839
840 // After complete unrolling most of the blocks should be contained in OuterL.
841 // However, some of them might happen to be out of OuterL (e.g. if they
842 // precede a loop exit). In this case we might need to insert PHI nodes in
843 // order to preserve LCSSA form.
844 // We don't need to check this if we already know that we need to fix LCSSA
845 // form.
846 // TODO: For now we just recompute LCSSA for the outer loop in this case, but
847 // it should be possible to fix it in-place.
848 if (PreserveLCSSA && OuterL && CompletelyUnroll && !NeedToFixLCSSA)
849 NeedToFixLCSSA |= ::needToInsertPhisForLCSSA(OuterL, UnrolledLoopBlocks, LI);
850
851 // Make sure that loop-simplify form is preserved. We want to simplify
852 // at least one layer outside of the loop that was unrolled so that any
853 // changes to the parent loop exposed by the unrolling are considered.
854 if (OuterL) {
855 // OuterL includes all loops for which we can break loop-simplify, so
856 // it's sufficient to simplify only it (it'll recursively simplify inner
857 // loops too).
858 if (NeedToFixLCSSA) {
859 // LCSSA must be performed on the outermost affected loop. The unrolled
860 // loop's last loop latch is guaranteed to be in the outermost loop
861 // after LoopInfo's been updated by LoopInfo::erase.
862 Loop *LatchLoop = LI->getLoopFor(Latches.back());
863 Loop *FixLCSSALoop = OuterL;
864 if (!FixLCSSALoop->contains(LatchLoop))
865 while (FixLCSSALoop->getParentLoop() != LatchLoop)
866 FixLCSSALoop = FixLCSSALoop->getParentLoop();
867
868 formLCSSARecursively(*FixLCSSALoop, *DT, LI, SE);
869 } else if (PreserveLCSSA) {
870 assert(OuterL->isLCSSAForm(*DT) &&
871 "Loops should be in LCSSA form after loop-unroll.");
872 }
873
874 // TODO: That potentially might be compile-time expensive. We should try
875 // to fix the loop-simplified form incrementally.
876 simplifyLoop(OuterL, DT, LI, SE, AC, nullptr, PreserveLCSSA);
877 } else {
878 // Simplify loops for which we might've broken loop-simplify form.
879 for (Loop *SubLoop : LoopsToSimplify)
880 simplifyLoop(SubLoop, DT, LI, SE, AC, nullptr, PreserveLCSSA);
881 }
882
883 return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled
884 : LoopUnrollResult::PartiallyUnrolled;
885}
886
887/// Given an llvm.loop loop id metadata node, returns the loop hint metadata
888/// node with the given name (for example, "llvm.loop.unroll.count"). If no
889/// such metadata node exists, then nullptr is returned.
891 // First operand should refer to the loop id itself.
892 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
893 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
894
895 for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
896 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
897 if (!MD)
898 continue;
899
900 MDString *S = dyn_cast<MDString>(MD->getOperand(0));
901 if (!S)
902 continue;
903
904 if (Name.equals(S->getString()))
905 return MD;
906 }
907 return nullptr;
908}
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
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(CondGuardInst *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:314
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:495
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:292
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:314
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
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:146
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:341
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:114
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:197
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:222
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:358
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.
Definition: LoopInfo.h:139
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:232
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:64
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:33
BlockT * getHeader() const
Definition: LoopInfo.h:105
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:258
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:195
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:412
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:188
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:114
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
Definition: LoopInfo.h:242
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:1222
RPOIterator endRPO() const
Definition: LoopIterator.h:140
LoopT * AllocateLoop(ArgsTy &&... Args)
Definition: LoopInfo.h:956
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:699
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:1049
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Definition: LoopInfo.h:1140
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:547
bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens=true) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:462
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:486
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:631
Metadata node.
Definition: Metadata.h:943
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1291
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1297
A single uniqued string.
Definition: Metadata.h:611
StringRef getString() const
Definition: Metadata.cpp:507
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
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:141
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:301
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
int getNumOccurrences() const
Definition: CommandLine.h:401
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.
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:537
auto successors(const MachineBasicBlock *BB)
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:410
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:721
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:1742
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:1298
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:2244
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:2006
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
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:890
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.