#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/PriorityWorklist.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/InstSimplifyFolder.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
#include "llvm/IR/DIBuilder.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"

Classes
struct	DbgLoop
struct	RewritePhi
struct	PointerBounds
	IR Values for the lower and upper bounds of a pointer evolution. More...

Macros
#define	DEBUG_TYPE "loop-utils"

Functions
static MDNode *	createStringMetadata (Loop *TheLoop, StringRef Name, unsigned V)
	Create MDNode for input string.
static CondBrInst *	getExpectedExitLoopLatchBranch (Loop *L)
	Checks if `L` has an exiting latch branch.
static raw_ostream &	operator<< (raw_ostream &OS, DbgLoop D)
static std::optional< unsigned >	estimateLoopTripCount (Loop *L)
static Intrinsic::ID	getVPReductionIntrinsicID (Intrinsic::ID Id)
static bool	hasHardUserWithinLoop (const Loop L, const Instruction I)
static bool	canLoopBeDeleted (Loop *L, SmallVector< RewritePhi, 8 > &RewritePhiSet)
static bool	checkIsIndPhi (PHINode Phi, Loop L, ScalarEvolution *SE, InductionDescriptor &ID)
	Checks if it is safe to call InductionDescriptor::isInductionPHI for `Phi`, and returns true if this Phi is an induction phi in the loop.
static PointerBounds	expandBounds (const RuntimeCheckingPtrGroup CG, Loop TheLoop, Instruction *Loc, SCEVExpander &Exp, bool HoistRuntimeChecks)
	Expand code for the lower and upper bound of the pointer group `CG` in `TheLoop`.
static SmallVector< std::pair< PointerBounds, PointerBounds >, 4 >	expandBounds (const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, Loop L, Instruction Loc, SCEVExpander &Exp, bool HoistRuntimeChecks)
	Turns a collection of checks into a collection of expanded upper and lower bounds for both pointers in the check.

Variables
static const char *	LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced"
static const char *	LLVMLoopDisableLICM = "llvm.licm.disable"

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "loop-utils"

Definition at line 55 of file LoopUtils.cpp.

Function Documentation

◆ canLoopBeDeleted()

bool canLoopBeDeleted	(	Loop *	L,
		SmallVector< RewritePhi, 8 > &	RewritePhiSet )

static

Definition at line 1783 of file LoopUtils.cpp.

References llvm::any_of(), llvm::BasicBlock::begin(), llvm::dyn_cast(), I, P, and llvm::SmallVectorTemplateCommon< T, typename >::size().

Referenced by llvm::rewriteLoopExitValues().

◆ checkIsIndPhi()

bool checkIsIndPhi	(	PHINode *	Phi,
		Loop *	L,
		ScalarEvolution *	SE,
		InductionDescriptor &	ID )

static

Checks if it is safe to call InductionDescriptor::isInductionPHI for Phi, and returns true if this Phi is an induction phi in the loop.

When isInductionPHI returns true, ID will be also be set by isInductionPHI.

Definition at line 1837 of file LoopUtils.cpp.

References llvm::InductionDescriptor::isInductionPHI().

Referenced by llvm::rewriteLoopExitValues().

◆ createStringMetadata()

MDNode * createStringMetadata	(	Loop *	TheLoop,
		StringRef	Name,
		unsigned	V )

static

Create MDNode for input string.

Definition at line 206 of file LoopUtils.cpp.

References llvm::ConstantAsMetadata::get(), llvm::MDNode::get(), llvm::MDString::get(), llvm::BasicBlock::getContext(), llvm::LoopBase< BlockT, LoopT >::getHeader(), and llvm::Type::getInt32Ty().

Referenced by llvm::addStringMetadataToLoop().

◆ estimateLoopTripCount()

std::optional< unsigned > estimateLoopTripCount ( Loop * L )

static

Definition at line 855 of file LoopUtils.cpp.

References llvm::dbgs(), llvm::divideNearest(), llvm::extractBranchWeights(), getExpectedExitLoopLatchBranch(), llvm::CondBrInst::getSuccessor(), LLVM_DEBUG, std::swap(), and uint64_t.

Referenced by llvm::getLoopEstimatedTripCount().

◆ expandBounds() [1/2]

PointerBounds expandBounds	(	const RuntimeCheckingPtrGroup *	CG,
		Loop *	TheLoop,
		Instruction *	Loc,
		SCEVExpander &	Exp,
		bool	HoistRuntimeChecks )

static

Expand code for the lower and upper bound of the pointer group CG in TheLoop.

Returns: the values for the bounds.

Definition at line 2125 of file LoopUtils.cpp.

References llvm::RuntimeCheckingPtrGroup::AddressSpace, llvm::ScalarEvolution::applyLoopGuards(), llvm::cast(), llvm::dbgs(), llvm::End, llvm::PointerType::get(), llvm::ScalarEvolution::getExitCount(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::SCEV::getType(), High, llvm::RuntimeCheckingPtrGroup::High, HoistRuntimeChecks, llvm::isa(), llvm::Type::isIntegerTy(), llvm::ScalarEvolution::isKnownNonNegative(), LLVM_DEBUG, llvm::RuntimeCheckingPtrGroup::Low, llvm::Low, and llvm::RuntimeCheckingPtrGroup::NeedsFreeze.

Referenced by llvm::addRuntimeChecks(), and expandBounds().

◆ expandBounds() [2/2]

SmallVector< std::pair< PointerBounds, PointerBounds >, 4 > expandBounds	(	const SmallVectorImpl< RuntimePointerCheck > &	PointerChecks,
		Loop *	L,
		Instruction *	Loc,
		SCEVExpander &	Exp,
		bool	HoistRuntimeChecks )