1//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 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 7//===----------------------------------------------------------------------===// 9// This pass performs several transformations to transform natural loops into a 10// simpler form, which makes subsequent analyses and transformations simpler and 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. 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. 23// This pass also guarantees that loops will have exactly one backedge. 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. 30// Similar complications arise from callbr instructions, particularly in 31// asm-goto where blockaddress expressions are used. 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 37// This pass obviously modifies the CFG, but updates loop information and 38// dominator information. 40//===----------------------------------------------------------------------===// 73#define DEBUG_TYPE "loop-simplify" 75STATISTIC(NumNested ,
"Number of nested loops split out");
77// If the block isn't already, move the new block to right after some 'outside 78// block' block. This prevents the preheader from being placed inside the loop 79// body, e.g. when the loop hasn't been rotated. 83// Check to see if NewBB is already well placed. 88// If it isn't already after an outside block, move it after one. This is 89// always good as it makes the uncond branch from the outside block into a 92// Figure out *which* outside block to put this after. Prefer an outside 93// block that neighbors a BB actually in the loop. 97if (++BBI != NewBB->
getParent()->
end() && L->contains(&*BBI)) {
103// If our heuristic for a *good* bb to place this after doesn't find 104// anything, just pick something. It's likely better than leaving it within 107 FoundBB = SplitPreds[0];
111/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 112/// preheader, this method is called to insert one. This method has two phases: 113/// preheader insertion and analysis updating. 120// Compute the set of predecessors of the loop that are not in the loop. 123if (!L->contains(
P)) {
// Coming in from outside the loop? 124// If the loop is branched to from an indirect terminator, we won't 125// be able to fully transform the loop, because it prohibits 127if (isa<IndirectBrInst>(
P->getTerminator()))
135// Split out the loop pre-header. 138 LI, MSSAU, PreserveLCSSA);
143 << PreheaderBB->
getName() <<
"\n");
145// Make sure that NewBB is put someplace intelligent, which doesn't mess up 146// code layout too horribly. 152/// Add the specified block, and all of its predecessors, to the specified set, 153/// if it's not already in there. Stop predecessor traversal when we reach 161if (
Blocks.insert(BB).second && BB != StopBlock)
162// If BB is not already processed and it is not a stop block then 163// insert its predecessor in the work list 165 }
while (!Worklist.
empty());
168/// The first part of loop-nestification is to find a PHI node that tells 169/// us how to partition the loops. 177// This is a degenerate PHI already, don't modify it! 183// Scan this PHI node looking for a use of the PHI node by itself. 187// We found something tasty to remove. 193/// If this loop has multiple backedges, try to pull one of them out into 196/// This is important for code that looks like 201/// br cond, Loop, Next 203/// br cond2, Loop, Out 205/// To identify this common case, we look at the PHI nodes in the header of the 206/// loop. PHI nodes with unchanging values on one backedge correspond to values 207/// that change in the "outer" loop, but not in the "inner" loop. 209/// If we are able to separate out a loop, return the new outer loop that was 216// Don't try to separate loops without a preheader. 220// Treat the presence of convergent functions conservatively. The 221// transformation is invalid if calls to certain convergent 222// functions (like an AMDGPU barrier) get included in the resulting 223// inner loop. But blocks meant for the inner loop will be 224// identified later at a point where it's too late to abort the 225// transformation. Also, the convergent attribute is not really 226// sufficient to express the semantics of functions that are 227// affected by this transformation. So we choose to back off if such 228// a function call is present until a better alternative becomes 229// available. This is similar to the conservative treatment of 230// convergent function calls in GVNHoist and JumpThreading. 231for (
auto *BB : L->blocks()) {
232for (
auto &
II : *BB) {
233if (
auto CI = dyn_cast<CallBase>(&
II)) {
234if (CI->isConvergent()) {
241// The header is not a landing pad; preheader insertion should ensure this. 243assert(!Header->isEHPad() &&
"Can't insert backedge to EH pad");
246if (!PN)
returnnullptr;
// No known way to partition. 248// Pull out all predecessors that have varying values in the loop. This 249// handles the case when a PHI node has multiple instances of itself as 255// We can't split indirect control flow edges. 261LLVM_DEBUG(
dbgs() <<
"LoopSimplify: Splitting out a new outer loop\n");
263// If ScalarEvolution is around and knows anything about values in 264// this loop, tell it to forget them, because we're about to 265// substantially change it. 270 DT, LI, MSSAU, PreserveLCSSA);
272// Make sure that NewBB is put someplace intelligent, which doesn't mess up 273// code layout too horribly. 276// Create the new outer loop. 279// Change the parent loop to use the outer loop as its child now. 280if (
Loop *Parent = L->getParentLoop())
285// L is now a subloop of our outer loop. 291// Now reset the header in L, which had been moved by 292// SplitBlockPredecessors for the outer loop. 293 L->moveToHeader(Header);
295// Determine which blocks should stay in L and which should be moved out to 296// the Outer loop now. 303// Scan all of the loop children of L, moving them to OuterLoop if they are 304// not part of the inner loop. 305const std::vector<Loop*> &SubLoops = L->getSubLoops();
306for (
size_tI = 0;
I != SubLoops.size(); )
307if (BlocksInL.
count(SubLoops[
I]->getHeader()))
308 ++
I;
// Loop remains in L 310 NewOuter->
addChildLoop(L->removeChildLoop(SubLoops.begin() +
I));
314// Now that we know which blocks are in L and which need to be moved to 315// OuterLoop, move any blocks that need it. 316for (
unsigned i = 0; i != L->getBlocks().
size(); ++i) {
318if (!BlocksInL.
count(BB)) {
319// Move this block to the parent, updating the exit blocks sets 320 L->removeBlockFromLoop(BB);
329// Split edges to exit blocks from the inner loop, if they emerged in the 330// process of separating the outer one. 334// Fix LCSSA form for L. Some values, which previously were only used inside 335// L, can now be used in NewOuter loop. We need to insert phi-nodes for them 336// in corresponding exit blocks. 337// We don't need to form LCSSA recursively, because there cannot be uses 338// inside a newly created loop of defs from inner loops as those would 339// already be a use of an LCSSA phi node. 343"LCSSA is broken after separating nested loops!");
349/// This method is called when the specified loop has more than one 352/// If this occurs, revector all of these backedges to target a new basic block 353/// and have that block branch to the loop header. This ensures that loops 354/// have exactly one backedge. 358assert(L->getNumBackEdges() > 1 &&
"Must have > 1 backedge!");
360// Get information about the loop 364// Unique backedge insertion currently depends on having a preheader. 368// The header is not an EH pad; preheader insertion should ensure this. 369assert(!Header->isEHPad() &&
"Can't insert backedge to EH pad");
371// Figure out which basic blocks contain back-edges to the loop header. 372 std::vector<BasicBlock*> BackedgeBlocks;
374// Indirect edges cannot be split, so we must fail if we find one. 375if (isa<IndirectBrInst>(
P->getTerminator()))
378if (
P != Preheader) BackedgeBlocks.push_back(
P);
381// Create and insert the new backedge block... 383 Header->getName() +
".backedge",
F);
385 BETerminator->
setDebugLoc(Header->getFirstNonPHIIt()->getDebugLoc());
387LLVM_DEBUG(
dbgs() <<
"LoopSimplify: Inserting unique backedge block " 390// Move the new backedge block to right after the last backedge block. 394// Now that the block has been inserted into the function, create PHI nodes in 395// the backedge block which correspond to any PHI nodes in the header block. 401// Loop over the PHI node, moving all entries except the one for the 402// preheader over to the new PHI node. 403unsigned PreheaderIdx = ~0U;
404bool HasUniqueIncomingValue =
true;
405Value *UniqueValue =
nullptr;
409if (IBB == Preheader) {
413if (HasUniqueIncomingValue) {
416elseif (UniqueValue !=
IV)
417 HasUniqueIncomingValue =
false;
422// Delete all of the incoming values from the old PN except the preheader's 423assert(PreheaderIdx != ~0U &&
"PHI has no preheader entry??");
424if (PreheaderIdx != 0) {
428// Nuke all entries except the zero'th. 430/* DeletePHIIfEmpty */false);
432// Finally, add the newly constructed PHI node as the entry for the BEBlock. 435// As an optimization, if all incoming values in the new PhiNode (which is a 436// subset of the incoming values of the old PHI node) have the same value, 437// eliminate the PHI Node. 438if (HasUniqueIncomingValue) {
444// Now that all of the PHI nodes have been inserted and adjusted, modify the 445// backedge blocks to jump to the BEBlock instead of the header. 446// If one of the backedges has llvm.loop metadata attached, we remove 447// it from the backedge and add it to BEBlock. 458//===--- Update all analyses which we must preserve now -----------------===// 460// Update Loop Information - we know that this block is now in the current 461// loop and all parent loops. 462 L->addBasicBlockToLoop(BEBlock, *LI);
464// Update dominator information 474/// Simplify one loop and queue further loops for simplification. 485// Check to see that no blocks (other than the header) in this loop have 486// predecessors that are not in the loop. This is not valid for natural 487// loops, but can occur if the blocks are unreachable. Since they are 488// unreachable we can just shamelessly delete those CFG edges! 490if (BB == L->getHeader())
498// Delete each unique out-of-loop (and thus dead) predecessor. 501LLVM_DEBUG(
dbgs() <<
"LoopSimplify: Deleting edge from dead predecessor " 502 <<
P->getName() <<
"\n");
504// Zap the dead pred's terminator and replace it with unreachable. 507/*DTU=*/nullptr, MSSAU);
515// If there are exiting blocks with branches on undef, resolve the undef in 516// the direction which will exit the loop. This will help simplify loop 517// trip count computations. 519 L->getExitingBlocks(ExitingBlocks);
521if (
BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
522if (BI->isConditional()) {
526 <<
"LoopSimplify: Resolving \"br i1 undef\" to exit in " 527 << ExitingBlock->getName() <<
"\n");
529 BI->setCondition(ConstantInt::get(
Cond->getType(),
530 !L->contains(BI->getSuccessor(0))));
536// Does the loop already have a preheader? If so, don't insert one. 544// Next, check to make sure that all exit nodes of the loop only have 545// predecessors that are inside of the loop. This check guarantees that the 546// loop preheader/header will dominate the exit blocks. If the exit block has 547// predecessors from outside of the loop, split the edge now. 554// If the header has more than two predecessors at this point (from the 555// preheader and from multiple backedges), we must adjust the loop. 558// If this is really a nested loop, rip it out into a child loop. Don't do 559// this for loops with a giant number of backedges, just factor them into a 560// common backedge instead. 561if (L->getNumBackEdges() < 8) {
563 PreserveLCSSA, AC, MSSAU)) {
565// Enqueue the outer loop as it should be processed next in our 566// depth-first nest walk. 569// This is a big restructuring change, reprocess the whole loop. 571// GCC doesn't tail recursion eliminate this. 572// FIXME: It isn't clear we can't rely on LLVM to TRE this. 577// If we either couldn't, or didn't want to, identify nesting of the loops, 578// insert a new block that all backedges target, then make it jump to the 590// Scan over the PHI nodes in the loop header. Since they now have only two 591// incoming values (the loop is canonicalized), we may have simplified the PHI 592// down to 'X = phi [X, Y]', which should be replaced with 'Y'. 595 (PN = dyn_cast<PHINode>(
I++)); )
605// If this loop has multiple exits and the exits all go to the same 606// block, attempt to merge the exits. This helps several passes, such 607// as LoopRotation, which do not support loops with multiple exits. 608// SimplifyCFG also does this (and this code uses the same utility 609// function), however this code is loop-aware, where SimplifyCFG is 610// not. That gives it the advantage of being able to hoist 611// loop-invariant instructions out of the way to open up more 612// opportunities, and the disadvantage of having the responsibility 613// to preserve dominator information. 614auto HasUniqueExitBlock = [&]() {
616for (
auto *ExitingBB : ExitingBlocks)
618if (L->contains(SuccBB))
623elseif (UniqueExit != SuccBB)
629if (HasUniqueExitBlock()) {
630for (
BasicBlock *ExitingBlock : ExitingBlocks) {
631if (!ExitingBlock->getSinglePredecessor())
continue;
632BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
635if (!CI || CI->
getParent() != ExitingBlock)
continue;
637// Attempt to hoist out all instructions except for the 638// comparison and the branch. 639bool AllInvariant =
true;
640bool AnyInvariant =
false;
641for (
autoI = ExitingBlock->instructionsWithoutDebug().begin(); &*
I != BI; ) {
645if (!L->makeLoopInvariant(
647 Preheader ? Preheader->
getTerminator() :
nullptr, MSSAU, SE)) {
654if (!AllInvariant)
continue;
656// The block has now been cleared of all instructions except for 657// a comparison and a conditional branch. SimplifyCFG may be able 662// Success. The block is now dead, so remove it from the loop, 663// update the dominator tree and delete it. 665 << ExitingBlock->getName() <<
"\n");
672while (!
Node->isLeaf()) {
679 ExitBlockSet.
insert(ExitingBlock);
684 ExitingBlock,
/* KeepOneInputPHIs */ PreserveLCSSA);
686 ExitingBlock,
/* KeepOneInputPHIs */ PreserveLCSSA);
687 ExitingBlock->eraseFromParent();
703// If we're asked to preserve LCSSA, the loop nest needs to start in LCSSA 706assert(DT &&
"DT not available.");
707assert(LI &&
"LI not available.");
708assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
709"Requested to preserve LCSSA, but it's already broken.");
713// Worklist maintains our depth-first queue of loops in this nest to process. 717// Walk the worklist from front to back, pushing newly found sub loops onto 718// the back. This will let us process loops from back to front in depth-first 719// order. We can use this simple process because loops form a tree. 725while (!Worklist.
empty())
727 AC, MSSAU, PreserveLCSSA);
729// Changing exit conditions for blocks may affect exit counts of this loop and 730// any of its parents, so we must invalidate the entire subtree if we've made 731// any changes. Do this here rather than in simplifyOneLoop() as the top-most 732// loop is going to be the same for all child loops. 741staticcharID;
// Pass identification, replacement for typeid 751// We need loop information to identify the loops... 769 /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees. 774char LoopSimplify::ID = 0;
776"Canonicalize natural loops",
false,
false)
783// Publicly exposed interface to pass... 787/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 788/// it in any convenient order) inserting preheaders... 790bool LoopSimplify::runOnFunction(
Function &
F) {
792LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
793DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
794auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
797 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
799 std::unique_ptr<MemorySSAUpdater> MSSAU;
800auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
802 MSSA = &MSSAAnalysis->getMSSA();
803 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
806bool PreserveLCSSA = mustPreserveAnalysisID(
LCSSAID);
808// Simplify each loop nest in the function. 810 Changed |=
simplifyLoop(L, DT, LI, SE, AC, MSSAU.get(), PreserveLCSSA);
815 *LI, [&](
Loop *L) {
returnL->isRecursivelyLCSSAForm(*DT, *LI); });
816assert(InLCSSA &&
"LCSSA is broken after loop-simplify.");
830 std::unique_ptr<MemorySSAUpdater> MSSAU;
832auto *MSSA = &MSSAAnalysis->getMSSA();
833 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
837// Note that we don't preserve LCSSA in the new PM, if you need it run LCSSA 838// after simplifying the loops. MemorySSA is preserved if it exists. 841simplifyLoop(L, DT, LI, SE, AC, MSSAU.get(),
/*PreserveLCSSA*/false);
852// BPI maps conditional terminators to probabilities, LoopSimplify can insert 853// blocks, but it does so only by splitting existing blocks and edges. This 854// results in the interesting property that all new terminators inserted are 855// unconditional branches which do not appear in BPI. All deletions are 856// handled via ValueHandle callbacks w/in BPI. 861// FIXME: Restore this code when we re-enable verification in verifyAnalysis 864staticvoid verifyLoop(
Loop *L) {
869// It used to be possible to just assert L->isLoopSimplifyForm(), however 870// with the introduction of indirectbr, there are now cases where it's 871// not possible to transform a loop as necessary. We can at least check 872// that there is an indirectbr near any time there's trouble. 874// Indirectbr can interfere with preheader and unique backedge insertion. 875if (!L->getLoopPreheader() || !L->getLoopLatch()) {
876bool HasIndBrPred =
false;
878if (isa<IndirectBrInst>(Pred->getTerminator())) {
883"LoopSimplify has no excuse for missing loop header info!");
887// Indirectbr can interfere with exit block canonicalization. 888if (!
L->hasDedicatedExits()) {
889bool HasIndBrExiting =
false;
891L->getExitingBlocks(ExitingBlocks);
892for (
unsigned i = 0, e = ExitingBlocks.
size(); i !=
e; ++i) {
893if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) {
894 HasIndBrExiting =
true;
900"LoopSimplify has no excuse for missing exit block info!");
901 (void)HasIndBrExiting;
906void LoopSimplify::verifyAnalysis()
const{
907// FIXME: This routine is being called mid-way through the loop pass manager 908// as loop passes destroy this analysis. That's actually fine, but we have no 909// way of expressing that here. Once all of the passes that destroy this are 910// hoisted out of the loop pass manager we can add back verification here. 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
DenseMap< Block *, BlockRelaxAux > Blocks
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...
Module.h This file contains the declarations for the Module class.
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.
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.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
uint64_t IntrinsicInst * II
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
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)
static const uint32_t IV[8]
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.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
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.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
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...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
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.
A parsed version of the target data layout string in and methods for querying it.
Analysis pass which computes a DominatorTree.
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.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
FunctionPass class - This class is used to implement most global optimizations.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
BasicBlockListType::iterator iterator
Legacy wrapper pass to provide the GlobalsAAResult object.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
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.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Analysis pass that exposes the LoopInfo for a function.
std::vector< Loop * >::const_iterator iterator
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.
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.
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Represents a single loop in the control flow graph.
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.
An analysis that produces MemorySSA for a function.
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.
Encapsulates MemorySSA, including all data associated with memory accesses.
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
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'.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
virtual void verifyAnalysis() const
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserve()
Mark an analysis as preserved.
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.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
'undef' values are things that do not have specified contents.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
StringRef getName() const
Return a constant reference to the value's name.
const ParentTy * getParent() const
self_iterator getIterator()
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
This is an optimization pass for GlobalISel generic memory operations.
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.
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.
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
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.
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...
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.
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
char & BreakCriticalEdgesID
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
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)
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Pass * createLoopSimplifyPass()
