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