LoopFlatten.cpp File Reference

#include "llvm/Transforms/Scalar/LoopFlatten.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/LoopInfo.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/IR/Verifier.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/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
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)
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)
bool	Flatten (LoopNest &LN, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, TargetTransformInfo *TTI)
	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 52 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 493 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 601 of file LoopFlatten.cpp.

References assert(), CanFlattenLoopPair(), llvm::createWideIV(), llvm::dbgs(), DL, llvm::Value::dump(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::Value::getType(), FlattenInfo::InnerInductionPHI, FlattenInfo::InnerLoop, LLVM_DEBUG, M, FlattenInfo::OuterInductionPHI, llvm::RecursivelyDeleteDeadPHINode(), Rewriter, and FlattenInfo::Widened.

Referenced by FlattenLoopPair().

checkIVUsers()

static bool checkIVUsers ( FlattenInfo &  FI )

static

Definition at line 351 of file LoopFlatten.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::Value::dump(), llvm::BranchInst::getCondition(), FlattenInfo::InnerBranch, FlattenInfo::InnerIncrement, FlattenInfo::InnerInductionPHI, FlattenInfo::InnerTripCount, llvm::SmallPtrSetImpl< PtrType >::insert(), FlattenInfo::LinearIVUses, LLVM_DEBUG, llvm::PatternMatch::m_c_Add(), llvm::PatternMatch::m_c_Mul(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), FlattenInfo::OuterIncrement, FlattenInfo::OuterInductionPHI, llvm::SmallPtrSetImplBase::size(), llvm::Value::users(), and FlattenInfo::Widened.

Referenced by CanFlattenLoopPair().

checkOuterLoopInsts()

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

static

Definition at line 293 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 454 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::InnerTripCount, 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 212 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(), 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  )

static

Definition at line 539 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::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, FlattenInfo::OuterBranch, FlattenInfo::OuterInductionPHI, FlattenInfo::OuterLoop, FlattenInfo::OuterTripCount, llvm::Remark, 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 98 of file LoopFlatten.cpp.

References assert(), Compare, llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dbgs(), llvm::Value::dump(), llvm::ConstantInt::get(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::Value::getContext(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::PHINode::getIncomingValueForBlock(), llvm::Loop::getInductionVariable(), llvm::Loop::getLatchCmpInst(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Loop::getName(), llvm::ScalarEvolution::getSCEV(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::ScalarEvolution::getTripCountFromExitCount(), llvm::ConstantInt::getType(), llvm::ConstantInt::getValue(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_ULT, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Loop::isCanonical(), llvm::Loop::isLoopSimplifyForm(), and LLVM_DEBUG.

Referenced by CanFlattenLoopPair().

Flatten()

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

Definition at line 685 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  )

static

Definition at line 651 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, and FlattenInfo::OuterLoop.

Referenced by Flatten().

INITIALIZE_PASS_BEGIN()

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

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 743 of file LoopFlatten.cpp.

flatten

loop flatten

Definition at line 742 of file LoopFlatten.cpp.

loops

loop Flattens loops

Definition at line 742 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

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"))

static