LoopFlatten.cpp File Reference

#include "llvm/Transforms/Scalar/LoopFlatten.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopNestAnalysis.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include <optional>

Include dependency graph for LoopFlatten.cpp:

Go to the source code of this file.

Classes
struct	FlattenInfo

Macros
#define	DEBUG_TYPE   "loop-flatten"

Functions
	STATISTIC (NumFlattened, "Number of loops flattened")
static bool	setLoopComponents (Value *&TC, Value *&TripCount, BinaryOperator *&Increment, SmallPtrSetImpl< Instruction * > &IterationInstructions)
static bool	verifyTripCount (Value *RHS, Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment, BranchInst *&BackBranch, ScalarEvolution *SE, bool IsWidened)
static bool	findLoopComponents (Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment, BranchInst *&BackBranch, ScalarEvolution *SE, bool IsWidened)
static bool	checkPHIs (FlattenInfo &FI, const TargetTransformInfo *TTI)
static bool	checkOuterLoopInsts (FlattenInfo &FI, SmallPtrSetImpl< Instruction * > &IterationInstructions, const TargetTransformInfo *TTI)
static bool	checkIVUsers (FlattenInfo &FI)
static OverflowResult	checkOverflow (FlattenInfo &FI, DominatorTree *DT, AssumptionCache *AC)
static bool	CanFlattenLoopPair (FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
static bool	DoFlattenLoopPair (FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI, LPMUpdater *U, MemorySSAUpdater *MSSAU)
static bool	CanWidenIV (FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
static bool	FlattenLoopPair (FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI, LPMUpdater *U, MemorySSAUpdater *MSSAU)
bool	Flatten (LoopNest &LN, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, TargetTransformInfo *TTI, LPMUpdater *U, MemorySSAUpdater *MSSAU)
	INITIALIZE_PASS_BEGIN (LoopFlattenLegacyPass, "loop-flatten", "Flattens loops", false, false) INITIALIZE_PASS_END(LoopFlattenLegacyPass

Variables
static cl::opt< unsigned >	RepeatedInstructionThreshold ("loop-flatten-cost-threshold", cl::Hidden, cl::init(2), cl::desc("Limit on the cost of instructions that can be repeated due to " "loop flattening"))
static cl::opt< bool >	AssumeNoOverflow ("loop-flatten-assume-no-overflow", cl::Hidden, cl::init(false), cl::desc("Assume that the product of the two iteration " "trip counts will never overflow"))
static cl::opt< bool >	WidenIV ("loop-flatten-widen-iv", cl::Hidden, cl::init(true), cl::desc("Widen the loop induction variables, if possible, so " "overflow checks won't reject flattening"))
loop	flatten
loop Flattens	loops
loop Flattens	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-flatten"

Definition at line 83 of file LoopFlatten.cpp.

Function Documentation

CanFlattenLoopPair()

static bool CanFlattenLoopPair ( FlattenInfo &  FI, DominatorTree *  DT, LoopInfo *  LI, ScalarEvolution *  SE, AssumptionCache *  AC, const TargetTransformInfo *  TTI  )

static

Definition at line 658 of file LoopFlatten.cpp.

References checkIVUsers(), checkOuterLoopInsts(), checkPHIs(), llvm::dbgs(), findLoopComponents(), llvm::Value::getType(), FlattenInfo::InnerBranch, FlattenInfo::InnerIncrement, FlattenInfo::InnerInductionPHI, FlattenInfo::InnerLoop, FlattenInfo::InnerTripCount, llvm::Loop::isLoopInvariant(), LLVM_DEBUG, FlattenInfo::OuterBranch, FlattenInfo::OuterIncrement, FlattenInfo::OuterInductionPHI, FlattenInfo::OuterLoop, FlattenInfo::OuterTripCount, and FlattenInfo::Widened.

Referenced by CanWidenIV(), and FlattenLoopPair().

CanWidenIV()

static bool CanWidenIV ( FlattenInfo &  FI, DominatorTree *  DT, LoopInfo *  LI, ScalarEvolution *  SE, AssumptionCache *  AC, const TargetTransformInfo *  TTI  )

static

Definition at line 778 of file LoopFlatten.cpp.

References assert(), CanFlattenLoopPair(), llvm::createWideIV(), llvm::dbgs(), Deleted, DL, llvm::Value::dump(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::Value::getType(), FlattenInfo::InnerInductionPHI, FlattenInfo::InnerLoop, FlattenInfo::InnerPHIsToTransform, llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, M, FlattenInfo::NarrowInnerInductionPHI, llvm::WideIVInfo::NarrowIV, FlattenInfo::NarrowOuterInductionPHI, FlattenInfo::OuterInductionPHI, llvm::RecursivelyDeleteDeadPHINode(), Rewriter, FlattenInfo::Widened, and WidenIV.

Referenced by FlattenLoopPair().

checkIVUsers()

static bool checkIVUsers ( FlattenInfo &  FI )

static

Definition at line 585 of file LoopFlatten.cpp.

References FlattenInfo::checkInnerInductionPhiUsers(), FlattenInfo::checkOuterInductionPhiUsers(), llvm::dbgs(), llvm::Value::dump(), FlattenInfo::LinearIVUses, LLVM_DEBUG, and llvm::SmallPtrSetImplBase::size().

Referenced by CanFlattenLoopPair().

checkOuterLoopInsts()

static bool checkOuterLoopInsts ( FlattenInfo &  FI, SmallPtrSetImpl< Instruction * > &  IterationInstructions, const TargetTransformInfo *  TTI  )

static

Definition at line 518 of file LoopFlatten.cpp.

References B, llvm::LoopBase< BlockT, LoopT >::contains(), Cost, llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::getBlocks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::TargetTransformInfo::getInstructionCost(), llvm::BranchInst::getSuccessor(), I, FlattenInfo::InnerLoop, FlattenInfo::InnerTripCount, llvm::isSafeToSpeculativelyExecute(), llvm::BranchInst::isUnconditional(), LLVM_DEBUG, llvm::PatternMatch::m_c_Mul(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::match(), FlattenInfo::OuterInductionPHI, FlattenInfo::OuterLoop, RepeatedInstructionThreshold, and llvm::TargetTransformInfo::TCK_SizeAndLatency.

Referenced by CanFlattenLoopPair().

checkOverflow()

static OverflowResult checkOverflow ( FlattenInfo &  FI, DominatorTree *  DT, AssumptionCache *  AC  )

static

Definition at line 609 of file LoopFlatten.cpp.

References AssumeNoOverflow, llvm::computeOverflowForUnsignedMul(), llvm::dbgs(), DL, F, GEP, llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Type::getIntegerBitWidth(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), FlattenInfo::InnerLoop, FlattenInfo::InnerTripCount, llvm::isGuaranteedToExecuteForEveryIteration(), FlattenInfo::LinearIVUses, LLVM_DEBUG, llvm::MayOverflow, llvm::NeverOverflows, llvm::ISD::OR, FlattenInfo::OuterLoop, FlattenInfo::OuterTripCount, and llvm::Value::users().

Referenced by FlattenLoopPair().

checkPHIs()

static bool checkPHIs ( FlattenInfo &  FI, const TargetTransformInfo *  TTI  )

static

Definition at line 433 of file LoopFlatten.cpp.

References assert(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::Value::dump(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Instruction::getParent(), llvm::PHINode::hasConstantValue(), FlattenInfo::InnerInductionPHI, FlattenInfo::InnerLoop, FlattenInfo::InnerPHIsToTransform, llvm::SmallPtrSetImpl< PtrType >::insert(), FlattenInfo::isNarrowInductionPhi(), LLVM_DEBUG, FlattenInfo::OuterInductionPHI, FlattenInfo::OuterLoop, and llvm::BasicBlock::phis().

Referenced by CanFlattenLoopPair().

DoFlattenLoopPair()

static bool DoFlattenLoopPair ( FlattenInfo &  FI, DominatorTree *  DT, LoopInfo *  LI, ScalarEvolution *  SE, AssumptionCache *  AC, const TargetTransformInfo *  TTI, LPMUpdater *  U, MemorySSAUpdater *  MSSAU  )

static

Definition at line 704 of file LoopFlatten.cpp.

References Builder, llvm::BranchInst::Create(), CreateMul(), llvm::dbgs(), DEBUG_TYPE, llvm::DominatorTreeBase< NodeT, IsPostDom >::deleteEdge(), llvm::Value::dump(), llvm::OptimizationRemarkEmitter::emit(), llvm::LoopInfo::erase(), llvm::Instruction::eraseFromParent(), F, llvm::ScalarEvolution::forgetBlockAndLoopDispositions(), llvm::ScalarEvolution::forgetLoop(), llvm::BranchInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Loop::getName(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::Loop::getStartLoc(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), FlattenInfo::InnerInductionPHI, FlattenInfo::InnerLoop, FlattenInfo::InnerPHIsToTransform, FlattenInfo::InnerTripCount, FlattenInfo::LinearIVUses, LLVM_DEBUG, llvm::LPMUpdater::markLoopAsDeleted(), FlattenInfo::OuterBranch, FlattenInfo::OuterInductionPHI, FlattenInfo::OuterLoop, FlattenInfo::OuterTripCount, PHI, llvm::Remark, llvm::MemorySSAUpdater::removeEdge(), llvm::PHINode::removeIncomingValue(), llvm::Value::replaceAllUsesWith(), and FlattenInfo::Widened.

Referenced by FlattenLoopPair().

findLoopComponents()

static bool findLoopComponents ( Loop *  L, SmallPtrSetImpl< Instruction * > &  IterationInstructions, PHINode *&  InductionPHI, Value *&  TripCount, BinaryOperator *&  Increment, BranchInst *&  BackBranch, ScalarEvolution *  SE, bool  IsWidened  )

static

Definition at line 353 of file LoopFlatten.cpp.

References Compare, llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dbgs(), llvm::Value::dump(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::PHINode::getIncomingValueForBlock(), llvm::Loop::getInductionVariable(), llvm::Loop::getLatchCmpInst(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Loop::getName(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_ULT, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Loop::isCanonical(), llvm::Loop::isLoopSimplifyForm(), LLVM_DEBUG, RHS, and verifyTripCount().

Referenced by CanFlattenLoopPair().

Flatten()

bool Flatten	(	LoopNest &	LN,
		DominatorTree *	DT,
		LoopInfo *	LI,
		ScalarEvolution *	SE,
		AssumptionCache *	AC,
		TargetTransformInfo *	TTI,
		LPMUpdater *	U,
		MemorySSAUpdater *	MSSAU
	)

Definition at line 897 of file LoopFlatten.cpp.

References FlattenLoopPair(), and llvm::LoopNest::getLoops().

Referenced by llvm::LoopFlattenPass::run().

FlattenLoopPair()

static bool FlattenLoopPair ( FlattenInfo &  FI, DominatorTree *  DT, LoopInfo *  LI, ScalarEvolution *  SE, AssumptionCache *  AC, const TargetTransformInfo *  TTI, LPMUpdater *  U, MemorySSAUpdater *  MSSAU  )

static

Definition at line 844 of file LoopFlatten.cpp.

References llvm::AlwaysOverflowsHigh, llvm::AlwaysOverflowsLow, CanFlattenLoopPair(), CanWidenIV(), checkOverflow(), llvm::dbgs(), DoFlattenLoopPair(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Value::getName(), llvm::BasicBlock::getParent(), FlattenInfo::InnerLoop, LLVM_DEBUG, llvm::MayOverflow, llvm::ISD::OR, FlattenInfo::OuterLoop, and FlattenInfo::Widened.

Referenced by Flatten().

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	LoopFlattenLegacyPass	,
		"loop-flatten"	,
		"Flattens loops"	,
		false	,
		false
	)

setLoopComponents()

static bool setLoopComponents ( Value *&  TC, Value *&  TripCount, BinaryOperator *&  Increment, SmallPtrSetImpl< Instruction * > &  IterationInstructions  )

static

Definition at line 270 of file LoopFlatten.cpp.

References llvm::dbgs(), llvm::Value::dump(), llvm::SmallPtrSetImpl< PtrType >::insert(), and LLVM_DEBUG.

Referenced by verifyTripCount().

STATISTIC()

STATISTIC	(	NumFlattened	,
		"Number of loops flattened"
	)

verifyTripCount()

static bool verifyTripCount ( Value *  RHS, Loop *  L, SmallPtrSetImpl< Instruction * > &  IterationInstructions, PHINode *&  InductionPHI, Value *&  TripCount, BinaryOperator *&  Increment, BranchInst *&  BackBranch, ScalarEvolution *  SE, bool  IsWidened  )

static

Definition at line 286 of file LoopFlatten.cpp.

References llvm::dbgs(), llvm::ConstantInt::get(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::Value::getContext(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::getTripCountFromExitCount(), llvm::ConstantInt::getType(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::ScalarEvolution::getZeroExtendExpr(), LLVM_DEBUG, RHS, and setLoopComponents().

Referenced by findLoopComponents().

Variable Documentation

AssumeNoOverflow

cl::opt<bool> AssumeNoOverflow("loop-flatten-assume-no-overflow", cl::Hidden, cl::init(false), cl::desc("Assume that the product of the two iteration " "trip counts will never overflow"))

static

Referenced by checkOverflow().

false

loop Flattens false

Definition at line 971 of file LoopFlatten.cpp.

flatten

loop flatten

Definition at line 970 of file LoopFlatten.cpp.

loops

loop Flattens loops

Definition at line 970 of file LoopFlatten.cpp.

RepeatedInstructionThreshold

cl::opt<unsigned> RepeatedInstructionThreshold("loop-flatten-cost-threshold", cl::Hidden, cl::init(2), cl::desc("Limit on the cost of instructions that can be repeated due to " "loop flattening"))

static

Referenced by checkOuterLoopInsts().

WidenIV

WidenIV::WidenIV

static

Definition at line 1174 of file SimplifyIndVar.cpp.

Referenced by CanWidenIV(), and llvm::createWideIV().