LoopFlatten.cpp File Reference

#include "llvm/Transforms/Scalar/LoopFlatten.h"
#include "ScalarOptions.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/LoopAccessAnalysis.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/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/LoopVersioning.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include <optional>

Go to the source code of this file.

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, CondBrInst *&BackBranch, ScalarEvolution *SE, bool IsWidened)
static bool	findLoopComponents (Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment, CondBrInst *&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, const LoopAccessInfo &LAI)

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-flatten"

Definition at line 83 of file LoopFlatten.cpp.

Function Documentation

CanFlattenLoopPair()

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

static

Definition at line 685 of file LoopFlatten.cpp.

References checkIVUsers(), checkOuterLoopInsts(), checkPHIs(), llvm::dbgs(), findLoopComponents(), llvm::Value::getType(), llvm::Loop::isLoopInvariant(), and LLVM_DEBUG.

Referenced by CanWidenIV(), and FlattenLoopPair().

CanWidenIV()

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

static

Definition at line 822 of file LoopFlatten.cpp.

References assert(), CanFlattenLoopPair(), llvm::createWideIV(), llvm::dbgs(), Deleted, DL, llvm::Value::dump(), llvm::ScalarEvolution::forgetLoop(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::Value::getType(), LLVM_DEBUG, llvm::WideIVInfo::NarrowIV, llvm::RecursivelyDeleteDeadPHINode(), and Rewriter.

Referenced by FlattenLoopPair().

checkIVUsers()

bool checkIVUsers ( FlattenInfo & FI )

static

Definition at line 604 of file LoopFlatten.cpp.

References llvm::dbgs(), LLVM_DEBUG, and llvm::SmallPtrSetImplBase::size().

Referenced by CanFlattenLoopPair().

checkOuterLoopInsts()

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

static

Definition at line 538 of file LoopFlatten.cpp.

References B(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getBlocks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::UncondBrInst::getSuccessor(), I, llvm::isa(), llvm::isSafeToSpeculativelyExecute(), LLVM_DEBUG, llvm::PatternMatch::m_c_Mul(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::match(), and llvm::TargetTransformInfo::TCK_SizeAndLatency.

Referenced by CanFlattenLoopPair().

checkOverflow()

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

static

Definition at line 628 of file LoopFlatten.cpp.

References llvm::cast(), llvm::computeOverflowForUnsignedMul(), llvm::dbgs(), DL, llvm::dyn_cast(), F, GEP, llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), llvm::isa(), llvm::isGuaranteedToExecuteForEveryIteration(), LLVM_DEBUG, llvm::MayOverflow, llvm::NeverOverflows, and llvm::Value::users().

Referenced by FlattenLoopPair().

checkPHIs()

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

static

Definition at line 453 of file LoopFlatten.cpp.

References assert(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::Value::dump(), llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::PHINode::hasConstantValue(), llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, and llvm::BasicBlock::phis().

Referenced by CanFlattenLoopPair().

DoFlattenLoopPair()

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

static

Definition at line 731 of file LoopFlatten.cpp.

References llvm::sampleprof::Base, llvm::cast(), llvm::UncondBrInst::Create(), llvm::dbgs(), DEBUG_TYPE, llvm::DominatorTreeBase< NodeT, IsPostDom >::deleteEdge(), llvm::DominatorTree::dominates(), llvm::Value::dump(), llvm::dyn_cast(), llvm::OptimizationRemarkEmitter::emit(), llvm::LoopInfo::erase(), F, llvm::ScalarEvolution::forgetBlockAndLoopDispositions(), llvm::ScalarEvolution::forgetLoop(), GEP, llvm::CondBrInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Loop::getName(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::Loop::getStartLoc(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), LLVM_DEBUG, PHI, llvm::Remark, llvm::MemorySSAUpdater::removeEdge(), llvm::PHINode::removeIncomingValue(), llvm::Value::replaceAllUsesWith(), and llvm::Instruction::setDebugLoc().

Referenced by FlattenLoopPair().

findLoopComponents()

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

static

Definition at line 373 of file LoopFlatten.cpp.

References llvm::cast(), llvm::dbgs(), llvm::Value::dump(), llvm::PHINode::getIncomingValueForBlock(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_ULT, llvm::Increment, llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, RHS, and verifyTripCount().

Referenced by CanFlattenLoopPair().

FlattenLoopPair()

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

static

Definition at line 889 of file LoopFlatten.cpp.

References llvm::AlwaysOverflowsHigh, llvm::AlwaysOverflowsLow, assert(), Call, CanFlattenLoopPair(), CanWidenIV(), llvm::cast(), checkOverflow(), llvm::dbgs(), DL, DoFlattenLoopPair(), llvm::CondBrInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::Type::getScalarSizeInBits(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), LLVM_DEBUG, llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), llvm::MayOverflow, llvm::CondBrInst::setCondition(), and llvm::LoopVersioning::versionLoop().

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

setLoopComponents()

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

static

Definition at line 289 of file LoopFlatten.cpp.

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

Referenced by verifyTripCount().

STATISTIC()

STATISTIC	(	NumFlattened	,
		"Number of loops flattened"	)

References llvm::Global.

verifyTripCount()

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

static

Definition at line 305 of file LoopFlatten.cpp.

References llvm::dbgs(), llvm::dyn_cast(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::Value::getContext(), llvm::ScalarEvolution::getNoopOrZeroExtend(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::getTripCountFromExitCount(), llvm::SCEV::getType(), llvm::ConstantInt::getValue(), llvm::Increment, llvm::isa(), LLVM_DEBUG, RHS, and setLoopComponents().

Referenced by findLoopComponents().