#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/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/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/Debug.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"

Classes
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 BranchInst *	getExpectedExitLoopLatchBranch (Loop *L)
	Checks if `L` has an exiting latch branch.

static std::optional< uint64_t >	getEstimatedTripCount (BranchInst ExitingBranch, Loop L, uint64_t &OrigExitWeight)
	Return the estimated trip count for any exiting branch which dominates the loop latch.

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 52 of file LoopUtils.cpp.

Function Documentation

◆ canLoopBeDeleted()

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

static

Definition at line 1424 of file LoopUtils.cpp.

References llvm::any_of(), llvm::BasicBlock::begin(), I, P, and llvm::SmallVectorBase< Size_T >::size().

Referenced by llvm::rewriteLoopExitValues().

◆ checkIsIndPhi()

static 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 1478 of file LoopUtils.cpp.

References llvm::InductionDescriptor::isInductionPHI().

Referenced by llvm::rewriteLoopExitValues().

◆ createStringMetadata()

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

static

Create MDNode for input string.

Definition at line 203 of file LoopUtils.cpp.

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

Referenced by llvm::addStringMetadataToLoop().

◆ expandBounds() [1/2]

static 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 1806 of file LoopUtils.cpp.

References llvm::RuntimeCheckingPtrGroup::AddressSpace, llvm::ScalarEvolution::applyLoopGuards(), llvm::IRBuilderBase::CreateFreeze(), llvm::dbgs(), End, llvm::Value::getContext(), llvm::ScalarEvolution::getExitCount(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::SCEV::getType(), llvm::RuntimeCheckingPtrGroup::High, High, HoistRuntimeChecks, 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]

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