Go to the documentation of this file.
95 #define DEBUG_TYPE "loop-versioning-licm"
103 cl::desc(
"LoopVersioningLICM's minimum allowed percentage"
104 "of possible invariant instructions per loop"),
109 "licm-versioning-max-depth-threshold",
111 "LoopVersioningLICM's threshold for maximum allowed loop nest/depth"),
116 struct LoopVersioningLICMLegacyPass :
public LoopPass {
119 LoopVersioningLICMLegacyPass() :
LoopPass(
ID) {
126 StringRef getPassName()
const override {
return "Loop Versioning for LICM"; }
143 struct LoopVersioningLICM {
151 :
AA(
AA), SE(SE), GetLAI(GetLAI),
161 LoadAndStoreCounter = 0;
162 InvariantCounter = 0;
163 IsReadOnlyLoop =
true;
170 AutoResetter(LoopVersioningLICM &LVLICM) : LVLICM(LVLICM) {}
171 ~AutoResetter() { LVLICM.reset(); }
174 LoopVersioningLICM &LVLICM;
191 Loop *CurLoop =
nullptr;
194 std::unique_ptr<AliasSetTracker> CurAST;
197 unsigned LoopDepthThreshold;
200 float InvariantThreshold;
203 unsigned LoadAndStoreCounter = 0;
206 unsigned InvariantCounter = 0;
209 bool IsReadOnlyLoop =
true;
214 bool isLegalForVersioning();
215 bool legalLoopStructure();
216 bool legalLoopInstructions();
217 bool legalLoopMemoryAccesses();
218 bool isLoopAlreadyVisited();
219 void setNoAliasToLoop(
Loop *VerLoop);
226 bool LoopVersioningLICM::legalLoopStructure() {
228 if (!CurLoop->isLoopSimplifyForm()) {
233 if (!CurLoop->getSubLoops().empty()) {
238 if (CurLoop->getNumBackEdges() != 1) {
243 if (!CurLoop->getExitingBlock()) {
250 if (CurLoop->getExitingBlock() != CurLoop->getLoopLatch()) {
256 if (CurLoop->isAnnotatedParallel()) {
261 if (CurLoop->getLoopDepth() > LoopDepthThreshold) {
268 if (isa<SCEVCouldNotCompute>(ExitCount)) {
277 bool LoopVersioningLICM::legalLoopMemoryAccesses() {
278 bool HasMayAlias =
false;
279 bool TypeSafety =
false;
293 for (
const auto &
I : *CurAST) {
303 bool TypeCheck =
true;
306 HasMod |= AS.
isMod();
307 for (
const auto &A : AS) {
308 Value *Ptr =
A.getValue();
310 TypeCheck = (TypeCheck && (SomePtr->
getType() == Ptr->
getType()));
313 TypeSafety |= TypeCheck;
341 bool LoopVersioningLICM::instructionSafeForVersioning(
Instruction *
I) {
342 assert(
I !=
nullptr &&
"Null instruction found!");
344 if (
auto *Call = dyn_cast<CallBase>(
I)) {
345 if (
Call->isConvergent() ||
Call->cannotDuplicate()) {
350 if (!
AA->doesNotAccessMemory(Call)) {
358 LLVM_DEBUG(
dbgs() <<
" May throw instruction found in loop body\n");
363 if (
I->mayReadFromMemory()) {
369 LoadAndStoreCounter++;
377 else if (
I->mayWriteToMemory()) {
383 LoadAndStoreCounter++;
389 IsReadOnlyLoop =
false;
396 bool LoopVersioningLICM::legalLoopInstructions() {
398 LoadAndStoreCounter = 0;
399 InvariantCounter = 0;
400 IsReadOnlyLoop =
true;
404 for (
auto *Block : CurLoop->getBlocks())
405 for (
auto &Inst : *Block) {
407 if (!instructionSafeForVersioning(&Inst)) {
410 <<
" Unsafe Loop Instruction";
416 LAI = &GetLAI(CurLoop);
418 if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
423 if (LAI->getNumRuntimePointerChecks() >
426 dbgs() <<
" LAA: Runtime checks are more than threshold !!\n");
429 CurLoop->getStartLoc(),
430 CurLoop->getHeader())
431 <<
"Number of runtime checks "
432 <<
NV(
"RuntimeChecks", LAI->getNumRuntimePointerChecks())
433 <<
" exceeds threshold "
439 if (!InvariantCounter) {
444 if (IsReadOnlyLoop) {
450 if (InvariantCounter * 100 < InvariantThreshold * LoadAndStoreCounter) {
453 <<
" Invariant load & store are less then defined threshold\n");
455 << ((InvariantCounter * 100) / LoadAndStoreCounter)
458 << InvariantThreshold <<
"%\n");
461 CurLoop->getStartLoc(),
462 CurLoop->getHeader())
463 <<
"Invariant load & store "
464 <<
NV(
"LoadAndStoreCounter",
465 ((InvariantCounter * 100) / LoadAndStoreCounter))
466 <<
" are less then defined threshold "
467 <<
NV(
"Threshold", InvariantThreshold);
477 bool LoopVersioningLICM::isLoopAlreadyVisited() {
489 bool LoopVersioningLICM::isLegalForVersioning() {
493 if (isLoopAlreadyVisited()) {
495 dbgs() <<
" Revisiting loop in LoopVersioningLICM not allowed.\n\n");
499 if (!legalLoopStructure()) {
501 dbgs() <<
" Loop structure not suitable for LoopVersioningLICM\n\n");
504 CurLoop->getStartLoc(),
505 CurLoop->getHeader())
506 <<
" Unsafe Loop structure";
511 if (!legalLoopInstructions()) {
514 <<
" Loop instructions not suitable for LoopVersioningLICM\n\n");
518 if (!legalLoopMemoryAccesses()) {
521 <<
" Loop memory access not suitable for LoopVersioningLICM\n\n");
524 CurLoop->getStartLoc(),
525 CurLoop->getHeader())
526 <<
" Unsafe Loop memory access";
531 LLVM_DEBUG(
dbgs() <<
" Loop Versioning found to be beneficial\n\n");
534 CurLoop->getStartLoc(), CurLoop->getHeader())
535 <<
" Versioned loop for LICM."
536 <<
" Number of runtime checks we had to insert "
537 <<
NV(
"RuntimeChecks", LAI->getNumRuntimePointerChecks());
547 void LoopVersioningLICM::setNoAliasToLoop(
Loop *VerLoop) {
552 MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain(
"LVDomain");
554 MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain,
Name);
558 for (
auto *Block : CurLoop->getBlocks()) {
559 for (
auto &Inst : *Block) {
561 if (!Inst.mayReadFromMemory() && !Inst.mayWriteToMemory())
565 LLVMContext::MD_noalias,
570 LLVMContext::MD_alias_scope,
581 AliasAnalysis *
AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
582 ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
584 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
585 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
586 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
589 return getAnalysis<LoopAccessLegacyAnalysis>().getInfo(L);
592 return LoopVersioningLICM(
AA, SE, ORE, GetLAI).runOnLoop(L, LI, DT);
598 AutoResetter Resetter(*
this);
614 bool Changed =
false;
619 if (isLegalForVersioning()) {
623 LoopVersioning LVer(*LAI, LAI->getRuntimePointerChecking()->getChecks(),
624 CurLoop, LI, DT, SE);
634 "llvm.mem.parallel_loop_access");
636 setNoAliasToLoop(LVer.getVersionedLoop());
645 "Loop Versioning For LICM",
false,
false)
659 return new LoopVersioningLICMLegacyPass();
678 if (!LoopVersioningLICM(
AA, SE, &ORE, GetLAI).runOnLoop(&L, LI, DT))
A set of analyses that are preserved following a run of a transformation pass.
This analysis provides dependence information for the memory accesses of a loop.
This is an optimization pass for GlobalISel generic memory operations.
INITIALIZE_PASS_BEGIN(LoopVersioningLICMLegacyPass, "loop-versioning-licm", "Loop Versioning For LICM", false, false) INITIALIZE_PASS_END(LoopVersioningLICMLegacyPass
const Function * getParent() const
Return the enclosing method, or null if none.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represents a single loop in the control flow graph.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
The main scalar evolution driver.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
This analysis provides dependence information for the memory accesses of a loop.
The legacy pass manager's analysis pass to compute loop information.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
DiagnosticInfoOptimizationBase::Argument NV
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &LAR, LPMUpdater &U)
Value * getPointerOperand()
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass * createLoopVersioningLICMPass()
static cl::opt< unsigned > LVLoopDepthThreshold("licm-versioning-max-depth-threshold", cl::desc("LoopVersioningLICM's threshold for maximum allowed loop nest/depth"), cl::init(2), cl::Hidden)
Threshold for maximum allowed loop nest/depth.
Represent the analysis usage information of a pass.
bool isForwardingAliasSet() const
Return true if this alias set should be ignored as part of the AliasSetTracker object.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Legacy analysis pass which computes a DominatorTree.
void initializeLoopVersioningLICMLegacyPassPass(PassRegistry &)
TransformationMode hasLICMVersioningTransformation(const Loop *L)
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
An efficient, type-erasing, non-owning reference to a callable.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for loop.
This class represents an analyzed expression in the program.
An instruction for storing to memory.
loop versioning Loop Versioning For LICM
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
initializer< Ty > init(const Ty &Val)
Drive the analysis of memory accesses in the loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
@ TM_Disable
The transformation should not be applied.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static unsigned RuntimeMemoryCheckThreshold
\When performing memory disambiguation checks at runtime do not make more than this number of compari...
static const char * LICMVersioningMetaData
void setPreservesCFG()
This function should be called by the pass, iff they do not:
StringRef - Represent a constant reference to a string, i.e.
Type * getType() const
All values are typed, get the type of this value.
static MDNode * concatenate(MDNode *A, MDNode *B)
Methods for metadata merging.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
An instruction for reading from memory.
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
BlockT * getHeader() const
Pass interface - Implemented by all 'passes'.
Value * getPointerOperand()
static cl::opt< bool > NoAliases("csky-no-aliases", cl::desc("Disable the emission of assembler pseudo instructions"), cl::init(false), cl::Hidden)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Legacy wrapper pass to provide the GlobalsAAResult object.
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...
A container for analyses that lazily runs them and caches their results.
AnalysisUsage & addRequiredID(const void *ID)
AnalysisUsage & addRequired()
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM Value Representation.
static cl::opt< float > LVInvarThreshold("licm-versioning-invariant-threshold", cl::desc("LoopVersioningLICM's minimum allowed percentage" "of possible invariant instructions per loop"), cl::init(25), cl::Hidden)
Threshold minimum allowed percentage for possible invariant instructions in a loop.