LLVM 20.0.0git
Classes | Namespaces | Macros | Functions | Variables
LoopUnroll.cpp File Reference
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopedHashTable.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/ADT/ilist_iterator.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/ValueMap.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GenericDomTree.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <assert.h>
#include <numeric>
#include <type_traits>
#include <vector>

Go to the source code of this file.

Classes

struct  LoadValue
 
class  StackNode
 

Namespaces

namespace  llvm
 This is an optimization pass for GlobalISel generic memory operations.
 

Macros

#define DEBUG_TYPE   "loop-unroll"
 

Functions

 STATISTIC (NumCompletelyUnrolled, "Number of loops completely unrolled")
 
 STATISTIC (NumUnrolled, "Number of loops unrolled (completely or otherwise)")
 
 STATISTIC (NumUnrolledNotLatch, "Number of loops unrolled without a conditional " "latch (completely or otherwise)")
 
static bool needToInsertPhisForLCSSA (Loop *L, const std::vector< BasicBlock * > &Blocks, LoopInfo *LI)
 Check if unrolling created a situation where we need to insert phi nodes to preserve LCSSA form.
 
static bool isEpilogProfitable (Loop *L)
 The function chooses which type of unroll (epilog or prolog) is more profitabale.
 
ValuegetMatchingValue (LoadValue LV, LoadInst *LI, unsigned CurrentGeneration, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)
 
void loadCSE (Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)
 
static LLVM_ATTRIBUTE_USED bool canHaveUnrollRemainder (const Loop *L)
 

Variables

static cl::opt< boolUnrollRuntimeEpilog ("unroll-runtime-epilog", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog."))
 
static cl::opt< boolUnrollVerifyDomtree ("unroll-verify-domtree", cl::Hidden, cl::desc("Verify domtree after unrolling"), cl::init(false))
 
static cl::opt< boolUnrollVerifyLoopInfo ("unroll-verify-loopinfo", cl::Hidden, cl::desc("Verify loopinfo after unrolling"), cl::init(false))
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-unroll"

Definition at line 82 of file LoopUnroll.cpp.

Function Documentation

◆ canHaveUnrollRemainder()

static LLVM_ATTRIBUTE_USED bool canHaveUnrollRemainder ( const Loop L)
static

Definition at line 425 of file LoopUnroll.cpp.

References llvm::getLoopConvergenceHeart(), and I.

Referenced by llvm::UnrollLoop().

◆ getMatchingValue()

Value * getMatchingValue ( LoadValue  LV,
LoadInst LI,
unsigned  CurrentGeneration,
BatchAAResults BAA,
function_ref< MemorySSA *()>  GetMSSA 
)

◆ isEpilogProfitable()

static bool isEpilogProfitable ( Loop L)
static

The function chooses which type of unroll (epilog or prolog) is more profitabale.

Epilog unroll is more profitable when there is PHI that starts from constant. In this case epilog will leave PHI start from constant, but prolog will convert it to non-constant.

loop: PN = PHI [I, Latch], [CI, PreHeader] I = foo(PN) ...

Epilog unroll case. loop: PN = PHI [I2, Latch], [CI, PreHeader] I1 = foo(PN) I2 = foo(I1) ... Prolog unroll case. NewPN = PHI [PrologI, Prolog], [CI, PreHeader] loop: PN = PHI [I2, Latch], [NewPN, PreHeader] I1 = foo(PN) I2 = foo(I1) ...

Definition at line 204 of file LoopUnroll.cpp.

References assert().

Referenced by llvm::UnrollLoop().

◆ loadCSE()

void loadCSE ( Loop L,
DominatorTree DT,
ScalarEvolution SE,
LoopInfo LI,
BatchAAResults BAA,
function_ref< MemorySSA *()>  GetMSSA 
)

◆ needToInsertPhisForLCSSA()

static bool needToInsertPhisForLCSSA ( Loop L,
const std::vector< BasicBlock * > &  Blocks,
LoopInfo LI 
)
static

Check if unrolling created a situation where we need to insert phi nodes to preserve LCSSA form.

Parameters
Blocksis a vector of basic blocks representing unrolled loop.
Lis the outer loop. It's possible that some of the blocks are in L, and some are not. In this case, if there is a use is outside L, and definition is inside L, we need to insert a phi-node, otherwise LCSSA will be broken. The function is just a helper function for llvm::UnrollLoop that returns true if this situation occurs, indicating that LCSSA needs to be fixed.

Definition at line 125 of file LoopUnroll.cpp.

References Blocks, llvm::LoopBase< BlockT, LoopT >::contains(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), and I.

Referenced by llvm::UnrollLoop().

◆ STATISTIC() [1/3]

STATISTIC ( NumCompletelyUnrolled  ,
"Number of loops completely unrolled"   
)

◆ STATISTIC() [2/3]

STATISTIC ( NumUnrolled  ,
"Number of loops unrolled (completely or otherwise)"   
)

◆ STATISTIC() [3/3]

STATISTIC ( NumUnrolledNotLatch  ,
"Number of loops unrolled without a conditional " "latch (completely or otherwise)"   
)

Variable Documentation

◆ UnrollRuntimeEpilog

cl::opt< bool > UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog.")) ( "unroll-runtime-epilog"  ,
cl::init(false)  ,
cl::Hidden  ,
cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog.")   
)
static

Referenced by llvm::UnrollLoop().

◆ UnrollVerifyDomtree

cl::opt< bool > UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden, cl::desc("Verify domtree after unrolling"), cl::init(false)) ( "unroll-verify-domtree"  ,
cl::Hidden  ,
cl::desc("Verify domtree after unrolling")  ,
cl::init(false)   
)
static

Referenced by llvm::UnrollLoop().

◆ UnrollVerifyLoopInfo

cl::opt< bool > UnrollVerifyLoopInfo("unroll-verify-loopinfo", cl::Hidden, cl::desc("Verify loopinfo after unrolling"), cl::init(false)) ( "unroll-verify-loopinfo"  ,
cl::Hidden  ,
cl::desc("Verify loopinfo after unrolling")  ,
cl::init(false)   
)
static

Referenced by llvm::UnrollLoop().