#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionTracker.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Type.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"

Include dependency graph for LoopSimplify.cpp:

Defines
#define	DEBUG_TYPE "loop-simplify"
Functions
	STATISTIC (NumInserted,"Number of pre-header or exit blocks inserted")
	STATISTIC (NumNested,"Number of nested loops split out")
static void	placeSplitBlockCarefully (BasicBlock NewBB, SmallVectorImpl< BasicBlock > &SplitPreds, Loop *L)
static BasicBlock *	rewriteLoopExitBlock (Loop L, BasicBlock Exit, Pass *PP)
	Ensure that the loop preheader dominates all exit blocks.
static void	addBlockAndPredsToSet (BasicBlock InputBB, BasicBlock StopBlock, std::set< BasicBlock * > &Blocks)
static PHINode *	findPHIToPartitionLoops (Loop L, AliasAnalysis AA, DominatorTree DT, AssumptionTracker AT)
	The first part of loop-nestification is to find a PHI node that tells us how to partition the loops.
static Loop *	separateNestedLoop (Loop L, BasicBlock Preheader, AliasAnalysis AA, DominatorTree DT, LoopInfo LI, ScalarEvolution SE, Pass PP, AssumptionTracker AT)
	If this loop has multiple backedges, try to pull one of them out into a nested loop.
static BasicBlock *	insertUniqueBackedgeBlock (Loop L, BasicBlock Preheader, AliasAnalysis AA, DominatorTree DT, LoopInfo *LI)
	This method is called when the specified loop has more than one backedge in it.
static bool	simplifyOneLoop (Loop L, SmallVectorImpl< Loop > &Worklist, AliasAnalysis AA, DominatorTree DT, LoopInfo LI, ScalarEvolution SE, Pass PP, const DataLayout DL, AssumptionTracker *AT)
	Simplify one loop and queue further loops for simplification.
	INITIALIZE_PASS_BEGIN (LoopSimplify,"loop-simplify","Canonicalize natural loops", true, false) INITIALIZE_PASS_END(LoopSimplify
Variables
loop	simplify
loop Canonicalize natural	loops
loop Canonicalize natural	true

Define Documentation

#define DEBUG_TYPE "loop-simplify"

Definition at line 67 of file LoopSimplify.cpp.

Function Documentation

static void addBlockAndPredsToSet	(	BasicBlock *	InputBB,
		BasicBlock *	StopBlock,
		std::set< BasicBlock * > &	Blocks
	)		`[static]`

Add the specified block, and all of its predecessors, to the specified set, if it's not already in there. Stop predecessor traversal when we reach StopBlock.

Definition at line 193 of file LoopSimplify.cpp.

References llvm::SmallVectorBase::empty(), I, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::pred_begin(), llvm::pred_end(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

Referenced by separateNestedLoop().

static PHINode* findPHIToPartitionLoops	(	Loop *	L,
		AliasAnalysis *	AA,
		DominatorTree *	DT,
		AssumptionTracker *	AT
	)		`[static]`

The first part of loop-nestification is to find a PHI node that tells us how to partition the loops.

Definition at line 211 of file LoopSimplify.cpp.

References llvm::BasicBlock::begin(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::AliasAnalysis::deleteValue(), llvm::Instruction::eraseFromParent(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), I, llvm::Value::replaceAllUsesWith(), and llvm::SimplifyInstruction().

Referenced by separateNestedLoop().

INITIALIZE_PASS_BEGIN	(	LoopSimplify	,
		"loop-simplify"	,
		"Canonicalize natural loops"	,
		true	,
		false
	)

static BasicBlock* insertUniqueBackedgeBlock	(	Loop *	L,
		BasicBlock *	Preheader,
		AliasAnalysis *	AA,
		DominatorTree *	DT,
		LoopInfo *	LI
	)		`[static]`

This method is called when the specified loop has more than one backedge in it.

If this occurs, revector all of these backedges to target a new basic block and have that block branch to the loop header. This ensures that loops have exactly one backedge.

Definition at line 358 of file LoopSimplify.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::PHINode::addIncoming(), llvm::AliasAnalysis::copyValue(), llvm::BasicBlock::Create(), llvm::PHINode::Create(), llvm::BranchInst::Create(), llvm::dbgs(), DEBUG, llvm::AliasAnalysis::deleteValue(), llvm::iplist< NodeTy, Traits >::erase(), F(), llvm::LoopInfo::getBase(), llvm::Function::getBasicBlockList(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::BasicBlock::getInstList(), llvm::Value::getName(), llvm::LoopBase< BlockT, LoopT >::getNumBackEdges(), llvm::PHINode::getNumIncomingValues(), llvm::TerminatorInst::getNumSuccessors(), llvm::TerminatorInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, P, llvm::pred_begin(), llvm::pred_end(), llvm::PHINode::removeIncomingValue(), llvm::PHINode::setIncomingBlock(), llvm::PHINode::setIncomingValue(), llvm::TerminatorInst::setSuccessor(), llvm::iplist< NodeTy, Traits >::splice(), and llvm::DominatorTreeBase< NodeT >::splitBlock().

Referenced by simplifyOneLoop().

static void placeSplitBlockCarefully	(	BasicBlock *	NewBB,
		SmallVectorImpl< BasicBlock * > &	SplitPreds,
		Loop *	L
	)		`[static]`

Definition at line 75 of file LoopSimplify.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::Function::end(), llvm::BasicBlock::getParent(), llvm::BasicBlock::moveAfter(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

Referenced by llvm::InsertPreheaderForLoop(), and separateNestedLoop().

static BasicBlock* rewriteLoopExitBlock	(	Loop *	L,
		BasicBlock *	Exit,
		Pass *	PP
	)		`[static]`

Ensure that the loop preheader dominates all exit blocks.

This method is used to split exit blocks that have predecessors outside of the loop.

Definition at line 160 of file LoopSimplify.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dbgs(), DEBUG, llvm::SmallVectorBase::empty(), llvm::BasicBlock::getTerminator(), I, llvm::BasicBlock::isLandingPad(), P, llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::SplitBlockPredecessors(), and llvm::SplitLandingPadPredecessors().

Referenced by simplifyOneLoop().

static Loop* separateNestedLoop	(	Loop *	L,
		BasicBlock *	Preheader,
		AliasAnalysis *	AA,
		DominatorTree *	DT,
		LoopInfo *	LI,
		ScalarEvolution *	SE,
		Pass *	PP,
		AssumptionTracker *	AT
	)		`[static]`

If this loop has multiple backedges, try to pull one of them out into a nested loop.

This is important for code that looks like this:

Loop: ... br cond, Loop, Next ... br cond2, Loop, Out

To identify this common case, we look at the PHI nodes in the header of the loop. PHI nodes with unchanging values on one backedge correspond to values that change in the "outer" loop, but not in the "inner" loop.

If we are able to separate out a loop, return the new outer loop that was created.

Definition at line 254 of file LoopSimplify.cpp.

Referenced by simplifyOneLoop().

static bool simplifyOneLoop	(	Loop *	L,
		SmallVectorImpl< Loop * > &	Worklist,
		AliasAnalysis *	AA,
		DominatorTree *	DT,
		LoopInfo *	LI,
		ScalarEvolution *	SE,
		Pass *	PP,
		const DataLayout *	DL,
		AssumptionTracker *	AT
	)		`[static]`

Simplify one loop and queue further loops for simplification.

FIXME: Currently this accepts both lots of analyses that it uses and a raw Pass pointer. The Pass pointer is used by numerous utilities to update specific analyses. Rather than a pass it would be much cleaner and more explicit if they accepted the analysis directly and then updated it.

Definition at line 477 of file LoopSimplify.cpp.

Referenced by llvm::simplifyLoop().

STATISTIC	(	NumInserted	,
		"Number of pre-header or exit blocks inserted"
	)

STATISTIC	(	NumNested	,
		"Number of nested loops split out"
	)

Variable Documentation

loop Canonicalize natural loops

Definition at line 785 of file LoopSimplify.cpp.

loop simplify

Definition at line 785 of file LoopSimplify.cpp.

loop Canonicalize natural true

Definition at line 785 of file LoopSimplify.cpp.

Defines

Functions

Variables

Define Documentation

Function Documentation

Variable Documentation