LoopUtils.cpp File Reference

#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/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"

Go to the source code of this file.

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 BranchInst *	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 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 53 of file LoopUtils.cpp.

Function Documentation

canLoopBeDeleted()

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

static

Definition at line 1593 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 1647 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 204 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 820 of file LoopUtils.cpp.

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

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

References llvm::RuntimeCheckingPtrGroup::AddressSpace, llvm::ScalarEvolution::applyLoopGuards(), llvm::cast(), llvm::dbgs(), 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 )

static

Turns a collection of checks into a collection of expanded upper and lower bounds for both pointers in the check.

Definition at line 2046 of file LoopUtils.cpp.

References Check, expandBounds(), llvm::First, HoistRuntimeChecks, and llvm::transform().

getExpectedExitLoopLatchBranch()

BranchInst * getExpectedExitLoopLatchBranch ( Loop * L )

static

Checks if L has an exiting latch branch.

There may also be other exiting blocks. Returns branch instruction terminating the loop latch if above check is successful, nullptr otherwise.

Definition at line 791 of file LoopUtils.cpp.

References assert(), llvm::dyn_cast(), llvm::BranchInst::getNumSuccessors(), llvm::BranchInst::getSuccessor(), and llvm::BasicBlock::getTerminator().

Referenced by estimateLoopTripCount(), llvm::getLoopEstimatedTripCount(), and llvm::setLoopEstimatedTripCount().

hasHardUserWithinLoop()

bool hasHardUserWithinLoop ( const Loop * L, const Instruction * I )

static

Definition at line 1552 of file LoopUtils.cpp.

References llvm::cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Instruction::mayHaveSideEffects(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::Value::users().

Referenced by llvm::rewriteLoopExitValues().

operator<<()

raw_ostream & operator<< ( raw_ostream & OS, DbgLoop D )

inlinestatic

Definition at line 813 of file LoopUtils.cpp.

References D().

Variable Documentation

LLVMLoopDisableLICM

const char* LLVMLoopDisableLICM = "llvm.licm.disable"

static

Definition at line 56 of file LoopUtils.cpp.

Referenced by llvm::hasDisableLICMTransformsHint().

LLVMLoopDisableNonforced

const char* LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced"

static

Definition at line 55 of file LoopUtils.cpp.

Referenced by llvm::hasDisableAllTransformsHint().