LLVM 19.0.0git
Macros | Functions | Variables
LoopSimplify.cpp File Reference
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "loop-simplify"
 

Functions

 STATISTIC (NumNested, "Number of nested loops split out")
 
static void placeSplitBlockCarefully (BasicBlock *NewBB, SmallVectorImpl< BasicBlock * > &SplitPreds, Loop *L)
 
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 there.
 
static PHINodefindPHIToPartitionLoops (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 LoopseparateNestedLoop (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 BasicBlockinsertUniqueBackedgeBlock (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.
 
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.
 
 INITIALIZE_PASS_BEGIN (LoopSimplify, "loop-simplify", "Canonicalize natural loops", false, false) INITIALIZE_PASS_END(LoopSimplify
 

Variables

loop simplify
 
loop Canonicalize natural loops
 
loop Canonicalize natural false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-simplify"

Definition at line 74 of file LoopSimplify.cpp.

Function Documentation

◆ addBlockAndPredsToSet()

static void addBlockAndPredsToSet ( BasicBlock InputBB,
BasicBlock StopBlock,
SmallPtrSetImpl< BasicBlock * > &  Blocks 
)
static

Add the specified block, and all of its predecessors, to the specified set, if it's not already in there.

Stop predecessor traversal when we reach StopBlock.

Definition at line 158 of file LoopSimplify.cpp.

References llvm::append_range(), Blocks, llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::predecessors(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by separateNestedLoop().

◆ findPHIToPartitionLoops()

static PHINode * findPHIToPartitionLoops ( Loop L,
DominatorTree DT,
AssumptionCache AC 
)
static

The first part of loop-nestification is to find a PHI node that tells us how to partition the loops.

Definition at line 173 of file LoopSimplify.cpp.

References DL, llvm::Instruction::eraseFromParent(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), I, llvm::Value::replaceAllUsesWith(), and llvm::simplifyInstruction().

Referenced by separateNestedLoop().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( LoopSimplify  ,
"loop-simplify"  ,
"Canonicalize natural loops"  ,
false  ,
false   
)

◆ insertUniqueBackedgeBlock()

static BasicBlock * insertUniqueBackedgeBlock ( Loop L,
BasicBlock Preheader,
DominatorTree DT,
LoopInfo LI,
MemorySSAUpdater MSSAU 
)
static

◆ placeSplitBlockCarefully()

static void placeSplitBlockCarefully ( BasicBlock NewBB,
SmallVectorImpl< BasicBlock * > &  SplitPreds,
Loop L 
)
static

◆ separateNestedLoop()

static Loop * separateNestedLoop ( Loop L,
BasicBlock Preheader,
DominatorTree DT,
LoopInfo LI,
ScalarEvolution SE,
bool  PreserveLCSSA,
AssumptionCache AC,
MemorySSAUpdater MSSAU 
)
static

If this loop has multiple backedges, try to pull one of them out into a nested loop.

This is important for code that looks like this:

Loop: ... br cond, Loop, Next ... br cond2, Loop, Out

To identify this common case, we look at the PHI nodes in the header of the loop. PHI nodes with unchanging values on one backedge correspond to values that change in the "outer" loop, but not in the "inner" loop.

If we are able to separate out a loop, return the new outer loop that was created.

Definition at line 215 of file LoopSimplify.cpp.

References addBlockAndPredsToSet(), llvm::LoopBase< BlockT, LoopT >::addBlockEntry(), llvm::LoopBase< BlockT, LoopT >::addChildLoop(), llvm::LoopInfoBase< BlockT, LoopT >::AllocateLoop(), assert(), llvm::LoopInfoBase< BlockT, LoopT >::changeLoopFor(), llvm::LoopInfoBase< BlockT, LoopT >::changeTopLevelLoop(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::DominatorTree::dominates(), findPHIToPartitionLoops(), llvm::ScalarEvolution::forgetLoop(), llvm::formDedicatedExitBlocks(), llvm::formLCSSA(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::BasicBlock::getTerminator(), I, llvm::Loop::isRecursivelyLCSSAForm(), LLVM_DEBUG, P, placeSplitBlockCarefully(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::LoopBase< BlockT, LoopT >::replaceChildLoopWith(), llvm::size(), and llvm::SplitBlockPredecessors().

Referenced by simplifyOneLoop().

◆ simplifyOneLoop()

static bool simplifyOneLoop ( Loop L,
SmallVectorImpl< Loop * > &  Worklist,
DominatorTree DT,
LoopInfo LI,
ScalarEvolution SE,
AssumptionCache AC,
MemorySSAUpdater MSSAU,
bool  PreserveLCSSA 
)
static

Simplify one loop and queue further loops for simplification.

Definition at line 478 of file LoopSimplify.cpp.

References assert(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::changeToUnreachable(), Cond, llvm::dbgs(), DL, llvm::BasicBlock::eraseFromParent(), llvm::Instruction::eraseFromParent(), llvm::DominatorTreeBase< NodeT, IsPostDom >::eraseNode(), llvm::FoldBranchToCommonDest(), llvm::ScalarEvolution::forgetValue(), llvm::formDedicatedExitBlocks(), llvm::BranchInst::getCondition(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::Value::getName(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Instruction::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), I, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::InsertPreheaderForLoop(), insertUniqueBackedgeBlock(), llvm::BasicBlock::instructionsWithoutDebug(), llvm::BranchInst::isConditional(), LLVM_DEBUG, P, llvm::pred_empty(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::LoopInfoBase< BlockT, LoopT >::removeBlock(), llvm::MemorySSAUpdater::removeBlocks(), llvm::BasicBlock::removePredecessor(), llvm::Value::replaceAllUsesWith(), llvm::LoopInfo::replacementPreservesLCSSAForm(), separateNestedLoop(), llvm::simplifyInstruction(), llvm::SmallVectorBase< Size_T >::size(), llvm::successors(), llvm::MemorySSA::verifyMemorySSA(), and llvm::VerifyMemorySSA.

Referenced by llvm::simplifyLoop().

◆ STATISTIC()

STATISTIC ( NumNested  ,
"Number of nested loops split out"   
)

Variable Documentation

◆ false

loop Canonicalize natural false

Definition at line 786 of file LoopSimplify.cpp.

◆ loops

loop Canonicalize natural loops

Definition at line 786 of file LoopSimplify.cpp.

◆ simplify

loop simplify

Definition at line 785 of file LoopSimplify.cpp.