LLVM 20.0.0git
LoopSimplify.cpp
Go to the documentation of this file.
1//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
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 pass performs several transformations to transform natural loops into a
10// simpler form, which makes subsequent analyses and transformations simpler and
11// more effective.
12//
13// Loop pre-header insertion guarantees that there is a single, non-critical
14// entry edge from outside of the loop to the loop header. This simplifies a
15// number of analyses and transformations, such as LICM.
16//
17// Loop exit-block insertion guarantees that all exit blocks from the loop
18// (blocks which are outside of the loop that have predecessors inside of the
19// loop) only have predecessors from inside of the loop (and are thus dominated
20// by the loop header). This simplifies transformations such as store-sinking
21// that are built into LICM.
22//
23// This pass also guarantees that loops will have exactly one backedge.
24//
25// Indirectbr instructions introduce several complications. If the loop
26// contains or is entered by an indirectbr instruction, it may not be possible
27// to transform the loop and make these guarantees. Client code should check
28// that these conditions are true before relying on them.
29//
30// Similar complications arise from callbr instructions, particularly in
31// asm-goto where blockaddress expressions are used.
32//
33// Note that the simplifycfg pass will clean up blocks which are split out but
34// end up being unnecessary, so usage of this pass should not pessimize
35// generated code.
36//
37// This pass obviously modifies the CFG, but updates loop information and
38// dominator information.
39//
40//===----------------------------------------------------------------------===//
41
43#include "llvm/ADT/SetVector.h"
45#include "llvm/ADT/Statistic.h"
58#include "llvm/IR/CFG.h"
59#include "llvm/IR/Constants.h"
60#include "llvm/IR/Dominators.h"
61#include "llvm/IR/Function.h"
63#include "llvm/IR/LLVMContext.h"
64#include "llvm/IR/Module.h"
66#include "llvm/Support/Debug.h"
72using namespace llvm;
73
74#define DEBUG_TYPE "loop-simplify"
75
76STATISTIC(NumNested , "Number of nested loops split out");
77
78// If the block isn't already, move the new block to right after some 'outside
79// block' block. This prevents the preheader from being placed inside the loop
80// body, e.g. when the loop hasn't been rotated.
83 Loop *L) {
84 // Check to see if NewBB is already well placed.
85 Function::iterator BBI = --NewBB->getIterator();
86 if (llvm::is_contained(SplitPreds, &*BBI))
87 return;
88
89 // If it isn't already after an outside block, move it after one. This is
90 // always good as it makes the uncond branch from the outside block into a
91 // fall-through.
92
93 // Figure out *which* outside block to put this after. Prefer an outside
94 // block that neighbors a BB actually in the loop.
95 BasicBlock *FoundBB = nullptr;
96 for (BasicBlock *Pred : SplitPreds) {
97 Function::iterator BBI = Pred->getIterator();
98 if (++BBI != NewBB->getParent()->end() && L->contains(&*BBI)) {
99 FoundBB = Pred;
100 break;
101 }
102 }
103
104 // If our heuristic for a *good* bb to place this after doesn't find
105 // anything, just pick something. It's likely better than leaving it within
106 // the loop.
107 if (!FoundBB)
108 FoundBB = SplitPreds[0];
109 NewBB->moveAfter(FoundBB);
110}
111
112/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
113/// preheader, this method is called to insert one. This method has two phases:
114/// preheader insertion and analysis updating.
115///
117 LoopInfo *LI, MemorySSAUpdater *MSSAU,
118 bool PreserveLCSSA) {
119 BasicBlock *Header = L->getHeader();
120
121 // Compute the set of predecessors of the loop that are not in the loop.
122 SmallVector<BasicBlock*, 8> OutsideBlocks;
123 for (BasicBlock *P : predecessors(Header)) {
124 if (!L->contains(P)) { // Coming in from outside the loop?
125 // If the loop is branched to from an indirect terminator, we won't
126 // be able to fully transform the loop, because it prohibits
127 // edge splitting.
128 if (isa<IndirectBrInst>(P->getTerminator()))
129 return nullptr;
130
131 // Keep track of it.
132 OutsideBlocks.push_back(P);
133 }
134 }
135
136 // Split out the loop pre-header.
137 BasicBlock *PreheaderBB;
138 PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DT,
139 LI, MSSAU, PreserveLCSSA);
140 if (!PreheaderBB)
141 return nullptr;
142
143 LLVM_DEBUG(dbgs() << "LoopSimplify: Creating pre-header "
144 << PreheaderBB->getName() << "\n");
145
146 // Make sure that NewBB is put someplace intelligent, which doesn't mess up
147 // code layout too horribly.
148 placeSplitBlockCarefully(PreheaderBB, OutsideBlocks, L);
149
150 return PreheaderBB;
151}
152
153/// Add the specified block, and all of its predecessors, to the specified set,
154/// if it's not already in there. Stop predecessor traversal when we reach
155/// StopBlock.
156static void addBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock,
159 Worklist.push_back(InputBB);
160 do {
161 BasicBlock *BB = Worklist.pop_back_val();
162 if (Blocks.insert(BB).second && BB != StopBlock)
163 // If BB is not already processed and it is not a stop block then
164 // insert its predecessor in the work list
165 append_range(Worklist, predecessors(BB));
166 } while (!Worklist.empty());
167}
168
169/// The first part of loop-nestification is to find a PHI node that tells
170/// us how to partition the loops.
172 AssumptionCache *AC) {
173 const DataLayout &DL = L->getHeader()->getDataLayout();
174 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
175 PHINode *PN = cast<PHINode>(I);
176 ++I;
177 if (Value *V = simplifyInstruction(PN, {DL, nullptr, DT, AC})) {
178 // This is a degenerate PHI already, don't modify it!
179 PN->replaceAllUsesWith(V);
180 PN->eraseFromParent();
181 continue;
182 }
183
184 // Scan this PHI node looking for a use of the PHI node by itself.
185 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
186 if (PN->getIncomingValue(i) == PN &&
187 L->contains(PN->getIncomingBlock(i)))
188 // We found something tasty to remove.
189 return PN;
190 }
191 return nullptr;
192}
193
194/// If this loop has multiple backedges, try to pull one of them out into
195/// a nested loop.
196///
197/// This is important for code that looks like
198/// this:
199///
200/// Loop:
201/// ...
202/// br cond, Loop, Next
203/// ...
204/// br cond2, Loop, Out
205///
206/// To identify this common case, we look at the PHI nodes in the header of the
207/// loop. PHI nodes with unchanging values on one backedge correspond to values
208/// that change in the "outer" loop, but not in the "inner" loop.
209///
210/// If we are able to separate out a loop, return the new outer loop that was
211/// created.
212///
213static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
214 DominatorTree *DT, LoopInfo *LI,
215 ScalarEvolution *SE, bool PreserveLCSSA,
216 AssumptionCache *AC, MemorySSAUpdater *MSSAU) {
217 // Don't try to separate loops without a preheader.
218 if (!Preheader)
219 return nullptr;
220
221 // Treat the presence of convergent functions conservatively. The
222 // transformation is invalid if calls to certain convergent
223 // functions (like an AMDGPU barrier) get included in the resulting
224 // inner loop. But blocks meant for the inner loop will be
225 // identified later at a point where it's too late to abort the
226 // transformation. Also, the convergent attribute is not really
227 // sufficient to express the semantics of functions that are
228 // affected by this transformation. So we choose to back off if such
229 // a function call is present until a better alternative becomes
230 // available. This is similar to the conservative treatment of
231 // convergent function calls in GVNHoist and JumpThreading.
232 for (auto *BB : L->blocks()) {
233 for (auto &II : *BB) {
234 if (auto CI = dyn_cast<CallBase>(&II)) {
235 if (CI->isConvergent()) {
236 return nullptr;
237 }
238 }
239 }
240 }
241
242 // The header is not a landing pad; preheader insertion should ensure this.
243 BasicBlock *Header = L->getHeader();
244 assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
245
246 PHINode *PN = findPHIToPartitionLoops(L, DT, AC);
247 if (!PN) return nullptr; // No known way to partition.
248
249 // Pull out all predecessors that have varying values in the loop. This
250 // handles the case when a PHI node has multiple instances of itself as
251 // arguments.
252 SmallVector<BasicBlock*, 8> OuterLoopPreds;
253 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
254 if (PN->getIncomingValue(i) != PN ||
255 !L->contains(PN->getIncomingBlock(i))) {
256 // We can't split indirect control flow edges.
257 if (isa<IndirectBrInst>(PN->getIncomingBlock(i)->getTerminator()))
258 return nullptr;
259 OuterLoopPreds.push_back(PN->getIncomingBlock(i));
260 }
261 }
262 LLVM_DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n");
263
264 // If ScalarEvolution is around and knows anything about values in
265 // this loop, tell it to forget them, because we're about to
266 // substantially change it.
267 if (SE)
268 SE->forgetLoop(L);
269
270 BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer",
271 DT, LI, MSSAU, PreserveLCSSA);
272
273 // Make sure that NewBB is put someplace intelligent, which doesn't mess up
274 // code layout too horribly.
275 placeSplitBlockCarefully(NewBB, OuterLoopPreds, L);
276
277 // Create the new outer loop.
278 Loop *NewOuter = LI->AllocateLoop();
279
280 // Change the parent loop to use the outer loop as its child now.
281 if (Loop *Parent = L->getParentLoop())
282 Parent->replaceChildLoopWith(L, NewOuter);
283 else
284 LI->changeTopLevelLoop(L, NewOuter);
285
286 // L is now a subloop of our outer loop.
287 NewOuter->addChildLoop(L);
288
289 for (BasicBlock *BB : L->blocks())
290 NewOuter->addBlockEntry(BB);
291
292 // Now reset the header in L, which had been moved by
293 // SplitBlockPredecessors for the outer loop.
294 L->moveToHeader(Header);
295
296 // Determine which blocks should stay in L and which should be moved out to
297 // the Outer loop now.
299 for (BasicBlock *P : predecessors(Header)) {
300 if (DT->dominates(Header, P))
301 addBlockAndPredsToSet(P, Header, BlocksInL);
302 }
303
304 // Scan all of the loop children of L, moving them to OuterLoop if they are
305 // not part of the inner loop.
306 const std::vector<Loop*> &SubLoops = L->getSubLoops();
307 for (size_t I = 0; I != SubLoops.size(); )
308 if (BlocksInL.count(SubLoops[I]->getHeader()))
309 ++I; // Loop remains in L
310 else
311 NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I));
312
313 SmallVector<BasicBlock *, 8> OuterLoopBlocks;
314 OuterLoopBlocks.push_back(NewBB);
315 // Now that we know which blocks are in L and which need to be moved to
316 // OuterLoop, move any blocks that need it.
317 for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
318 BasicBlock *BB = L->getBlocks()[i];
319 if (!BlocksInL.count(BB)) {
320 // Move this block to the parent, updating the exit blocks sets
321 L->removeBlockFromLoop(BB);
322 if ((*LI)[BB] == L) {
323 LI->changeLoopFor(BB, NewOuter);
324 OuterLoopBlocks.push_back(BB);
325 }
326 --i;
327 }
328 }
329
330 // Split edges to exit blocks from the inner loop, if they emerged in the
331 // process of separating the outer one.
332 formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA);
333
334 if (PreserveLCSSA) {
335 // Fix LCSSA form for L. Some values, which previously were only used inside
336 // L, can now be used in NewOuter loop. We need to insert phi-nodes for them
337 // in corresponding exit blocks.
338 // We don't need to form LCSSA recursively, because there cannot be uses
339 // inside a newly created loop of defs from inner loops as those would
340 // already be a use of an LCSSA phi node.
341 formLCSSA(*L, *DT, LI, SE);
342
343 assert(NewOuter->isRecursivelyLCSSAForm(*DT, *LI) &&
344 "LCSSA is broken after separating nested loops!");
345 }
346
347 return NewOuter;
348}
349
350/// This method is called when the specified loop has more than one
351/// backedge in it.
352///
353/// If this occurs, revector all of these backedges to target a new basic block
354/// and have that block branch to the loop header. This ensures that loops
355/// have exactly one backedge.
357 DominatorTree *DT, LoopInfo *LI,
358 MemorySSAUpdater *MSSAU) {
359 assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
360
361 // Get information about the loop
362 BasicBlock *Header = L->getHeader();
363 Function *F = Header->getParent();
364
365 // Unique backedge insertion currently depends on having a preheader.
366 if (!Preheader)
367 return nullptr;
368
369 // The header is not an EH pad; preheader insertion should ensure this.
370 assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
371
372 // Figure out which basic blocks contain back-edges to the loop header.
373 std::vector<BasicBlock*> BackedgeBlocks;
374 for (BasicBlock *P : predecessors(Header)) {
375 // Indirect edges cannot be split, so we must fail if we find one.
376 if (isa<IndirectBrInst>(P->getTerminator()))
377 return nullptr;
378
379 if (P != Preheader) BackedgeBlocks.push_back(P);
380 }
381
382 // Create and insert the new backedge block...
383 BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(),
384 Header->getName() + ".backedge", F);
385 BranchInst *BETerminator = BranchInst::Create(Header, BEBlock);
386 BETerminator->setDebugLoc(Header->getFirstNonPHI()->getDebugLoc());
387
388 LLVM_DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block "
389 << BEBlock->getName() << "\n");
390
391 // Move the new backedge block to right after the last backedge block.
392 Function::iterator InsertPos = ++BackedgeBlocks.back()->getIterator();
393 F->splice(InsertPos, F, BEBlock->getIterator());
394
395 // Now that the block has been inserted into the function, create PHI nodes in
396 // the backedge block which correspond to any PHI nodes in the header block.
397 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
398 PHINode *PN = cast<PHINode>(I);
399 PHINode *NewPN = PHINode::Create(PN->getType(), BackedgeBlocks.size(),
400 PN->getName()+".be", BETerminator->getIterator());
401
402 // Loop over the PHI node, moving all entries except the one for the
403 // preheader over to the new PHI node.
404 unsigned PreheaderIdx = ~0U;
405 bool HasUniqueIncomingValue = true;
406 Value *UniqueValue = nullptr;
407 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
408 BasicBlock *IBB = PN->getIncomingBlock(i);
409 Value *IV = PN->getIncomingValue(i);
410 if (IBB == Preheader) {
411 PreheaderIdx = i;
412 } else {
413 NewPN->addIncoming(IV, IBB);
414 if (HasUniqueIncomingValue) {
415 if (!UniqueValue)
416 UniqueValue = IV;
417 else if (UniqueValue != IV)
418 HasUniqueIncomingValue = false;
419 }
420 }
421 }
422
423 // Delete all of the incoming values from the old PN except the preheader's
424 assert(PreheaderIdx != ~0U && "PHI has no preheader entry??");
425 if (PreheaderIdx != 0) {
426 PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx));
427 PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx));
428 }
429 // Nuke all entries except the zero'th.
430 PN->removeIncomingValueIf([](unsigned Idx) { return Idx != 0; },
431 /* DeletePHIIfEmpty */ false);
432
433 // Finally, add the newly constructed PHI node as the entry for the BEBlock.
434 PN->addIncoming(NewPN, BEBlock);
435
436 // As an optimization, if all incoming values in the new PhiNode (which is a
437 // subset of the incoming values of the old PHI node) have the same value,
438 // eliminate the PHI Node.
439 if (HasUniqueIncomingValue) {
440 NewPN->replaceAllUsesWith(UniqueValue);
441 NewPN->eraseFromParent();
442 }
443 }
444
445 // Now that all of the PHI nodes have been inserted and adjusted, modify the
446 // backedge blocks to jump to the BEBlock instead of the header.
447 // If one of the backedges has llvm.loop metadata attached, we remove
448 // it from the backedge and add it to BEBlock.
449 MDNode *LoopMD = nullptr;
450 for (BasicBlock *BB : BackedgeBlocks) {
451 Instruction *TI = BB->getTerminator();
452 if (!LoopMD)
453 LoopMD = TI->getMetadata(LLVMContext::MD_loop);
454 TI->setMetadata(LLVMContext::MD_loop, nullptr);
455 TI->replaceSuccessorWith(Header, BEBlock);
456 }
457 BEBlock->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopMD);
458
459 //===--- Update all analyses which we must preserve now -----------------===//
460
461 // Update Loop Information - we know that this block is now in the current
462 // loop and all parent loops.
463 L->addBasicBlockToLoop(BEBlock, *LI);
464
465 // Update dominator information
466 DT->splitBlock(BEBlock);
467
468 if (MSSAU)
469 MSSAU->updatePhisWhenInsertingUniqueBackedgeBlock(Header, Preheader,
470 BEBlock);
471
472 return BEBlock;
473}
474
475/// Simplify one loop and queue further loops for simplification.
477 DominatorTree *DT, LoopInfo *LI,
479 MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
480 bool Changed = false;
481 if (MSSAU && VerifyMemorySSA)
482 MSSAU->getMemorySSA()->verifyMemorySSA();
483
484ReprocessLoop:
485
486 // Check to see that no blocks (other than the header) in this loop have
487 // predecessors that are not in the loop. This is not valid for natural
488 // loops, but can occur if the blocks are unreachable. Since they are
489 // unreachable we can just shamelessly delete those CFG edges!
490 for (BasicBlock *BB : L->blocks()) {
491 if (BB == L->getHeader())
492 continue;
493
495 for (BasicBlock *P : predecessors(BB))
496 if (!L->contains(P))
497 BadPreds.insert(P);
498
499 // Delete each unique out-of-loop (and thus dead) predecessor.
500 for (BasicBlock *P : BadPreds) {
501
502 LLVM_DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor "
503 << P->getName() << "\n");
504
505 // Zap the dead pred's terminator and replace it with unreachable.
506 Instruction *TI = P->getTerminator();
507 changeToUnreachable(TI, PreserveLCSSA,
508 /*DTU=*/nullptr, MSSAU);
509 Changed = true;
510 }
511 }
512
513 if (MSSAU && VerifyMemorySSA)
514 MSSAU->getMemorySSA()->verifyMemorySSA();
515
516 // If there are exiting blocks with branches on undef, resolve the undef in
517 // the direction which will exit the loop. This will help simplify loop
518 // trip count computations.
519 SmallVector<BasicBlock*, 8> ExitingBlocks;
520 L->getExitingBlocks(ExitingBlocks);
521 for (BasicBlock *ExitingBlock : ExitingBlocks)
522 if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
523 if (BI->isConditional()) {
524 if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) {
525
527 << "LoopSimplify: Resolving \"br i1 undef\" to exit in "
528 << ExitingBlock->getName() << "\n");
529
530 BI->setCondition(ConstantInt::get(Cond->getType(),
531 !L->contains(BI->getSuccessor(0))));
532
533 Changed = true;
534 }
535 }
536
537 // Does the loop already have a preheader? If so, don't insert one.
538 BasicBlock *Preheader = L->getLoopPreheader();
539 if (!Preheader) {
540 Preheader = InsertPreheaderForLoop(L, DT, LI, MSSAU, PreserveLCSSA);
541 if (Preheader)
542 Changed = true;
543 }
544
545 // Next, check to make sure that all exit nodes of the loop only have
546 // predecessors that are inside of the loop. This check guarantees that the
547 // loop preheader/header will dominate the exit blocks. If the exit block has
548 // predecessors from outside of the loop, split the edge now.
549 if (formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA))
550 Changed = true;
551
552 if (MSSAU && VerifyMemorySSA)
553 MSSAU->getMemorySSA()->verifyMemorySSA();
554
555 // If the header has more than two predecessors at this point (from the
556 // preheader and from multiple backedges), we must adjust the loop.
557 BasicBlock *LoopLatch = L->getLoopLatch();
558 if (!LoopLatch) {
559 // If this is really a nested loop, rip it out into a child loop. Don't do
560 // this for loops with a giant number of backedges, just factor them into a
561 // common backedge instead.
562 if (L->getNumBackEdges() < 8) {
563 if (Loop *OuterL = separateNestedLoop(L, Preheader, DT, LI, SE,
564 PreserveLCSSA, AC, MSSAU)) {
565 ++NumNested;
566 // Enqueue the outer loop as it should be processed next in our
567 // depth-first nest walk.
568 Worklist.push_back(OuterL);
569
570 // This is a big restructuring change, reprocess the whole loop.
571 Changed = true;
572 // GCC doesn't tail recursion eliminate this.
573 // FIXME: It isn't clear we can't rely on LLVM to TRE this.
574 goto ReprocessLoop;
575 }
576 }
577
578 // If we either couldn't, or didn't want to, identify nesting of the loops,
579 // insert a new block that all backedges target, then make it jump to the
580 // loop header.
581 LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI, MSSAU);
582 if (LoopLatch)
583 Changed = true;
584 }
585
586 if (MSSAU && VerifyMemorySSA)
587 MSSAU->getMemorySSA()->verifyMemorySSA();
588
589 const DataLayout &DL = L->getHeader()->getDataLayout();
590
591 // Scan over the PHI nodes in the loop header. Since they now have only two
592 // incoming values (the loop is canonicalized), we may have simplified the PHI
593 // down to 'X = phi [X, Y]', which should be replaced with 'Y'.
594 PHINode *PN;
595 for (BasicBlock::iterator I = L->getHeader()->begin();
596 (PN = dyn_cast<PHINode>(I++)); )
597 if (Value *V = simplifyInstruction(PN, {DL, nullptr, DT, AC})) {
598 if (SE) SE->forgetValue(PN);
599 if (!PreserveLCSSA || LI->replacementPreservesLCSSAForm(PN, V)) {
600 PN->replaceAllUsesWith(V);
601 PN->eraseFromParent();
602 Changed = true;
603 }
604 }
605
606 // If this loop has multiple exits and the exits all go to the same
607 // block, attempt to merge the exits. This helps several passes, such
608 // as LoopRotation, which do not support loops with multiple exits.
609 // SimplifyCFG also does this (and this code uses the same utility
610 // function), however this code is loop-aware, where SimplifyCFG is
611 // not. That gives it the advantage of being able to hoist
612 // loop-invariant instructions out of the way to open up more
613 // opportunities, and the disadvantage of having the responsibility
614 // to preserve dominator information.
615 auto HasUniqueExitBlock = [&]() {
616 BasicBlock *UniqueExit = nullptr;
617 for (auto *ExitingBB : ExitingBlocks)
618 for (auto *SuccBB : successors(ExitingBB)) {
619 if (L->contains(SuccBB))
620 continue;
621
622 if (!UniqueExit)
623 UniqueExit = SuccBB;
624 else if (UniqueExit != SuccBB)
625 return false;
626 }
627
628 return true;
629 };
630 if (HasUniqueExitBlock()) {
631 for (BasicBlock *ExitingBlock : ExitingBlocks) {
632 if (!ExitingBlock->getSinglePredecessor()) continue;
633 BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
634 if (!BI || !BI->isConditional()) continue;
635 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
636 if (!CI || CI->getParent() != ExitingBlock) continue;
637
638 // Attempt to hoist out all instructions except for the
639 // comparison and the branch.
640 bool AllInvariant = true;
641 bool AnyInvariant = false;
642 for (auto I = ExitingBlock->instructionsWithoutDebug().begin(); &*I != BI; ) {
643 Instruction *Inst = &*I++;
644 if (Inst == CI)
645 continue;
646 if (!L->makeLoopInvariant(
647 Inst, AnyInvariant,
648 Preheader ? Preheader->getTerminator() : nullptr, MSSAU, SE)) {
649 AllInvariant = false;
650 break;
651 }
652 }
653 if (AnyInvariant)
654 Changed = true;
655 if (!AllInvariant) continue;
656
657 // The block has now been cleared of all instructions except for
658 // a comparison and a conditional branch. SimplifyCFG may be able
659 // to fold it now.
660 if (!foldBranchToCommonDest(BI, /*DTU=*/nullptr, MSSAU))
661 continue;
662
663 // Success. The block is now dead, so remove it from the loop,
664 // update the dominator tree and delete it.
665 LLVM_DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block "
666 << ExitingBlock->getName() << "\n");
667
668 assert(pred_empty(ExitingBlock));
669 Changed = true;
670 LI->removeBlock(ExitingBlock);
671
672 DomTreeNode *Node = DT->getNode(ExitingBlock);
673 while (!Node->isLeaf()) {
674 DomTreeNode *Child = Node->back();
675 DT->changeImmediateDominator(Child, Node->getIDom());
676 }
677 DT->eraseNode(ExitingBlock);
678 if (MSSAU) {
680 ExitBlockSet.insert(ExitingBlock);
681 MSSAU->removeBlocks(ExitBlockSet);
682 }
683
685 ExitingBlock, /* KeepOneInputPHIs */ PreserveLCSSA);
687 ExitingBlock, /* KeepOneInputPHIs */ PreserveLCSSA);
688 ExitingBlock->eraseFromParent();
689 }
690 }
691
692 if (MSSAU && VerifyMemorySSA)
693 MSSAU->getMemorySSA()->verifyMemorySSA();
694
695 return Changed;
696}
697
700 MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
701 bool Changed = false;
702
703#ifndef NDEBUG
704 // If we're asked to preserve LCSSA, the loop nest needs to start in LCSSA
705 // form.
706 if (PreserveLCSSA) {
707 assert(DT && "DT not available.");
708 assert(LI && "LI not available.");
709 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
710 "Requested to preserve LCSSA, but it's already broken.");
711 }
712#endif
713
714 // Worklist maintains our depth-first queue of loops in this nest to process.
715 SmallVector<Loop *, 4> Worklist;
716 Worklist.push_back(L);
717
718 // Walk the worklist from front to back, pushing newly found sub loops onto
719 // the back. This will let us process loops from back to front in depth-first
720 // order. We can use this simple process because loops form a tree.
721 for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
722 Loop *L2 = Worklist[Idx];
723 Worklist.append(L2->begin(), L2->end());
724 }
725
726 while (!Worklist.empty())
727 Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, LI, SE,
728 AC, MSSAU, PreserveLCSSA);
729
730 // Changing exit conditions for blocks may affect exit counts of this loop and
731 // any of its parents, so we must invalidate the entire subtree if we've made
732 // any changes. Do this here rather than in simplifyOneLoop() as the top-most
733 // loop is going to be the same for all child loops.
734 if (Changed && SE)
735 SE->forgetTopmostLoop(L);
736
737 return Changed;
738}
739
740namespace {
741 struct LoopSimplify : public FunctionPass {
742 static char ID; // Pass identification, replacement for typeid
743 LoopSimplify() : FunctionPass(ID) {
745 }
746
747 bool runOnFunction(Function &F) override;
748
749 void getAnalysisUsage(AnalysisUsage &AU) const override {
751
752 // We need loop information to identify the loops...
755
758
766 AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added.
769 }
770
771 /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
772 void verifyAnalysis() const override;
773 };
774}
775
776char LoopSimplify::ID = 0;
777INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
778 "Canonicalize natural loops", false, false)
782INITIALIZE_PASS_END(LoopSimplify, "loop-simplify",
783 "Canonicalize natural loops", false, false)
784
785// Publicly exposed interface to pass...
786char &llvm::LoopSimplifyID = LoopSimplify::ID;
787Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
788
789/// runOnFunction - Run down all loops in the CFG (recursively, but we could do
790/// it in any convenient order) inserting preheaders...
791///
792bool LoopSimplify::runOnFunction(Function &F) {
793 bool Changed = false;
794 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
795 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
796 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
797 ScalarEvolution *SE = SEWP ? &SEWP->getSE() : nullptr;
798 AssumptionCache *AC =
799 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
800 MemorySSA *MSSA = nullptr;
801 std::unique_ptr<MemorySSAUpdater> MSSAU;
802 auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
803 if (MSSAAnalysis) {
804 MSSA = &MSSAAnalysis->getMSSA();
805 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
806 }
807
808 bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
809
810 // Simplify each loop nest in the function.
811 for (auto *L : *LI)
812 Changed |= simplifyLoop(L, DT, LI, SE, AC, MSSAU.get(), PreserveLCSSA);
813
814#ifndef NDEBUG
815 if (PreserveLCSSA) {
816 bool InLCSSA = all_of(
817 *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, *LI); });
818 assert(InLCSSA && "LCSSA is broken after loop-simplify.");
819 }
820#endif
821 return Changed;
822}
823
826 bool Changed = false;
827 LoopInfo *LI = &AM.getResult<LoopAnalysis>(F);
831 auto *MSSAAnalysis = AM.getCachedResult<MemorySSAAnalysis>(F);
832 std::unique_ptr<MemorySSAUpdater> MSSAU;
833 if (MSSAAnalysis) {
834 auto *MSSA = &MSSAAnalysis->getMSSA();
835 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
836 }
837
838
839 // Note that we don't preserve LCSSA in the new PM, if you need it run LCSSA
840 // after simplifying the loops. MemorySSA is preserved if it exists.
841 for (auto *L : *LI)
842 Changed |=
843 simplifyLoop(L, DT, LI, SE, AC, MSSAU.get(), /*PreserveLCSSA*/ false);
844
845 if (!Changed)
846 return PreservedAnalyses::all();
847
853 if (MSSAAnalysis)
855 // BPI maps conditional terminators to probabilities, LoopSimplify can insert
856 // blocks, but it does so only by splitting existing blocks and edges. This
857 // results in the interesting property that all new terminators inserted are
858 // unconditional branches which do not appear in BPI. All deletions are
859 // handled via ValueHandle callbacks w/in BPI.
861 return PA;
862}
863
864// FIXME: Restore this code when we re-enable verification in verifyAnalysis
865// below.
866#if 0
867static void verifyLoop(Loop *L) {
868 // Verify subloops.
869 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
870 verifyLoop(*I);
871
872 // It used to be possible to just assert L->isLoopSimplifyForm(), however
873 // with the introduction of indirectbr, there are now cases where it's
874 // not possible to transform a loop as necessary. We can at least check
875 // that there is an indirectbr near any time there's trouble.
876
877 // Indirectbr can interfere with preheader and unique backedge insertion.
878 if (!L->getLoopPreheader() || !L->getLoopLatch()) {
879 bool HasIndBrPred = false;
880 for (BasicBlock *Pred : predecessors(L->getHeader()))
881 if (isa<IndirectBrInst>(Pred->getTerminator())) {
882 HasIndBrPred = true;
883 break;
884 }
885 assert(HasIndBrPred &&
886 "LoopSimplify has no excuse for missing loop header info!");
887 (void)HasIndBrPred;
888 }
889
890 // Indirectbr can interfere with exit block canonicalization.
891 if (!L->hasDedicatedExits()) {
892 bool HasIndBrExiting = false;
893 SmallVector<BasicBlock*, 8> ExitingBlocks;
894 L->getExitingBlocks(ExitingBlocks);
895 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
896 if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) {
897 HasIndBrExiting = true;
898 break;
899 }
900 }
901
902 assert(HasIndBrExiting &&
903 "LoopSimplify has no excuse for missing exit block info!");
904 (void)HasIndBrExiting;
905 }
906}
907#endif
908
909void LoopSimplify::verifyAnalysis() const {
910 // FIXME: This routine is being called mid-way through the loop pass manager
911 // as loop passes destroy this analysis. That's actually fine, but we have no
912 // way of expressing that here. Once all of the passes that destroy this are
913 // hoisted out of the loop pass manager we can add back verification here.
914#if 0
915 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
916 verifyLoop(*I);
917#endif
918}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This is the interface for LLVM's primary stateless and local alias analysis.
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
DenseMap< Block *, BlockRelaxAux > Blocks
Definition: ELF_riscv.cpp:507
This is the interface for a simple mod/ref and alias analysis over globals.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static void placeSplitBlockCarefully(BasicBlock *NewBB, SmallVectorImpl< BasicBlock * > &SplitPreds, Loop *L)
static PHINode * findPHIToPartitionLoops(Loop *L, DominatorTree *DT, AssumptionCache *AC)
The first part of loop-nestification is to find a PHI node that tells us how to partition the loops.
static void addBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, SmallPtrSetImpl< BasicBlock * > &Blocks)
Add the specified block, and all of its predecessors, to the specified set, if it's not already in th...
loop Canonicalize natural loops
static bool simplifyOneLoop(Loop *L, SmallVectorImpl< Loop * > &Worklist, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify one loop and queue further loops for simplification.
loop simplify
static Loop * separateNestedLoop(Loop *L, BasicBlock *Preheader, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, bool PreserveLCSSA, AssumptionCache *AC, MemorySSAUpdater *MSSAU)
If this loop has multiple backedges, try to pull one of them out into a nested loop.
static BasicBlock * insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU)
This method is called when the specified loop has more than one backedge in it.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
uint64_t IntrinsicInst * II
#define P(N)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:57
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This is the interface for a SCEV-based alias analysis.
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:166
static const uint32_t IV[8]
Definition: blake3_impl.h:78
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:424
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
Represent the analysis usage information of a pass.
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
Legacy wrapper pass to provide the BasicAAResult object.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:212
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
Definition: BasicBlock.cpp:287
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:219
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:177
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:239
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:516
Conditional or Unconditional Branch instruction.
bool isConditional() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
Value * getCondition() const
Analysis pass which computes BranchProbabilityInfo.
Legacy analysis pass which computes BranchProbabilityInfo.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:747
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
Legacy pass manager pass to access dependence information.
AnalysisPass to compute dependence information in a function.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:317
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:310
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
BasicBlockListType::iterator iterator
Definition: Function.h:69
iterator end()
Definition: Function.h:853
Legacy wrapper pass to provide the GlobalsAAResult object.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:92
void replaceSuccessorWith(BasicBlock *OldBB, BasicBlock *NewBB)
Replace specified successor OldBB to point at the provided block.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:381
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1642
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:463
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:566
std::vector< Loop * >::const_iterator iterator
iterator end() const
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
void addBlockEntry(BlockT *BB)
This adds a basic block directly to the basic block list.
void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild)
This is used when splitting loops up.
iterator begin() const
void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop)
Replace the specified loop in the top-level loops list with the indicated loop.
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
LoopT * AllocateLoop(ArgsTy &&...Args)
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
std::vector< Loop * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:593
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Definition: LoopInfo.h:439
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:39
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI, bool IgnoreTokens=true) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:470
Metadata node.
Definition: Metadata.h:1069
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:924
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
void updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader, BasicBlock *LoopPreheader, BasicBlock *BackedgeBlock)
Update MemorySSA when inserting a unique backedge block for a loop.
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:981
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:697
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1905
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
void removeIncomingValueIf(function_ref< bool(unsigned)> Predicate, bool DeletePHIIfEmpty=true)
Remove all incoming values for which the predicate returns true.
void setIncomingBlock(unsigned i, BasicBlock *BB)
void setIncomingValue(unsigned i, Value *V)
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
virtual void verifyAnalysis() const
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: Pass.cpp:106
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:131
Legacy wrapper pass to provide the SCEVAAResult object.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
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...
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:346
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:435
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:367
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:502
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:696
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
'undef' values are things that do not have specified contents.
Definition: Constants.h:1398
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
const ParentTy * getParent() const
Definition: ilist_node.h:32
self_iterator getIterator()
Definition: ilist_node.h:132
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
constexpr double e
Definition: MathExtras.h:47
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.
BasicBlock * InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
InsertPreheaderForLoop - Once we discover that a loop doesn't have a preheader, this method is called...
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1722
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1680
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2098
char & LCSSAID
Definition: LCSSA.cpp:542
char & LoopSimplifyID
void initializeLoopSimplifyPass(PassRegistry &)
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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:2871
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:84
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:57
char & BreakCriticalEdgesID
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1886
bool foldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:443
Pass * createLoopSimplifyPass()