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 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 82 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 655 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 774 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 582 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 515 of file LoopFlatten.cpp.

References B, llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::getBlocks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BranchInst::getSuccessor(), llvm::TargetTransformInfo::getUserCost(), 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 606 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 430 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 701 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::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, 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 351 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 893 of file LoopFlatten.cpp.

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

Referenced by Flatten(), and 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 840 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 268 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 284 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 967 of file LoopFlatten.cpp.

flatten

loop flatten

Definition at line 966 of file LoopFlatten.cpp.

loops

loop Flattens loops

Definition at line 966 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 1129 of file SimplifyIndVar.cpp.

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