LoopSimplify.cpp File Reference

#include "llvm/Transforms/Utils/LoopSimplify.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/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/Transforms/Utils/Local.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/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/LoopUtils.h"

Include dependency graph for LoopSimplify.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "loop-simplify"

Functions
	STATISTIC (NumNested, "Number of nested loops split out")
static void	placeSplitBlockCarefully (BasicBlock *NewBB, SmallVectorImpl< BasicBlock *> &SplitPreds, Loop *L)
static void	addBlockAndPredsToSet (BasicBlock *InputBB, BasicBlock *StopBlock, std::set< BasicBlock *> &Blocks)
	Add the specified block, and all of its predecessors, to the specified set, if it's not already in there. More...
static PHINode *	findPHIToPartitionLoops (Loop *L, DominatorTree *DT, AssumptionCache *AC)
	The first part of loop-nestification is to find a PHI node that tells us how to partition the loops. More...
static Loop *	separateNestedLoop (Loop *L, BasicBlock *Preheader, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, bool PreserveLCSSA, AssumptionCache *AC)
	If this loop has multiple backedges, try to pull one of them out into a nested loop. More...
static BasicBlock *	insertUniqueBackedgeBlock (Loop *L, BasicBlock *Preheader, DominatorTree *DT, LoopInfo *LI)
	This method is called when the specified loop has more than one backedge in it. More...
static bool	simplifyOneLoop (Loop *L, SmallVectorImpl< Loop *> &Worklist, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, bool PreserveLCSSA)
	Simplify one loop and queue further loops for simplification. More...
	INITIALIZE_PASS_BEGIN (LoopSimplify, "loop-simplify", "Canonicalize natural loops", false, false) INITIALIZE_PASS_END(LoopSimplify

Variables
loop	simplify
loop Canonicalize natural	loops
loop Canonicalize natural	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-simplify"

Definition at line 73 of file LoopSimplify.cpp.

Function Documentation

addBlockAndPredsToSet()

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 157 of file LoopSimplify.cpp.

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

Referenced by separateNestedLoop().

findPHIToPartitionLoops()

static PHINode* findPHIToPartitionLoops ( Loop *  L, DominatorTree *  DT, AssumptionCache *  AC  )

static

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

Definition at line 175 of file LoopSimplify.cpp.

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

Referenced by separateNestedLoop().

INITIALIZE_PASS_BEGIN()

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

Referenced by llvm::simplifyLoop().

insertUniqueBackedgeBlock()

static BasicBlock* insertUniqueBackedgeBlock ( Loop *  L, BasicBlock *  Preheader, 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 341 of file LoopSimplify.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::PHINode::addIncoming(), assert(), llvm::BasicBlock::Create(), llvm::PHINode::Create(), llvm::BranchInst::Create(), llvm::dbgs(), E, llvm::iplist_impl< IntrusiveListT, TraitsT >::erase(), F(), llvm::Function::getBasicBlockList(), llvm::BasicBlock::getContext(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::BasicBlock::getInstList(), llvm::LLVMContext::getMDKindID(), llvm::Instruction::getMetadata(), llvm::Value::getName(), llvm::LoopBase< BlockT, LoopT >::getNumBackEdges(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getNumSuccessors(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, LLVM_DEBUG, P, llvm::pred_begin(), llvm::pred_end(), llvm::PHINode::removeIncomingValue(), llvm::PHINode::setIncomingBlock(), llvm::PHINode::setIncomingValue(), llvm::Instruction::setMetadata(), llvm::Instruction::setSuccessor(), llvm::iplist_impl< IntrusiveListT, TraitsT >::splice(), and llvm::DominatorTreeBase< NodeT, IsPostDom >::splitBlock().

Referenced by simplifyOneLoop().

placeSplitBlockCarefully()

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

static

Definition at line 80 of file LoopSimplify.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::Function::end(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::BasicBlock::getParent(), llvm::BasicBlock::moveAfter(), and llvm::SmallVectorBase::size().

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

separateNestedLoop()

static Loop* separateNestedLoop ( Loop *  L, BasicBlock *  Preheader, DominatorTree *  DT, LoopInfo *  LI, ScalarEvolution *  SE, bool  PreserveLCSSA, AssumptionCache *  AC  )

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 217 of file LoopSimplify.cpp.

References addBlockAndPredsToSet(), llvm::LoopBase< BlockT, LoopT >::addBlockEntry(), llvm::LoopBase< BlockT, LoopT >::addChildLoop(), llvm::LoopInfoBase< BlockT, LoopT >::AllocateLoop(), assert(), llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::LoopBase< BlockT, LoopT >::block_end(), llvm::LoopInfoBase< BlockT, LoopT >::changeLoopFor(), llvm::LoopInfoBase< BlockT, LoopT >::changeTopLevelLoop(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dbgs(), llvm::DominatorTree::dominates(), E, findPHIToPartitionLoops(), llvm::ScalarEvolution::forgetLoop(), llvm::formDedicatedExitBlocks(), llvm::formLCSSA(), llvm::LoopBase< BlockT, LoopT >::getBlocks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), I, llvm::BasicBlock::isEHPad(), llvm::Loop::isRecursivelyLCSSAForm(), LLVM_DEBUG, llvm::LoopBase< BlockT, LoopT >::moveToHeader(), P, placeSplitBlockCarefully(), llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::LoopBase< BlockT, LoopT >::removeBlockFromLoop(), llvm::LoopBase< BlockT, LoopT >::removeChildLoop(), llvm::LoopBase< BlockT, LoopT >::replaceChildLoopWith(), and llvm::SplitBlockPredecessors().

Referenced by simplifyOneLoop().

simplifyOneLoop()

static bool simplifyOneLoop ( Loop *  L, SmallVectorImpl< Loop *> &  Worklist, DominatorTree *  DT, LoopInfo *  LI, ScalarEvolution *  SE, AssumptionCache *  AC, bool  PreserveLCSSA  )

static

Simplify one loop and queue further loops for simplification.

Definition at line 461 of file LoopSimplify.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::LoopBase< BlockT, LoopT >::block_end(), llvm::changeToUnreachable(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dbgs(), llvm::dyn_cast(), E, llvm::Instruction::eraseFromParent(), llvm::FoldBranchToCommonDest(), llvm::ScalarEvolution::forgetLoopDispositions(), llvm::ScalarEvolution::forgetValue(), llvm::formDedicatedExitBlocks(), llvm::ConstantInt::get(), llvm::BranchInst::getCondition(), llvm::Module::getDataLayout(), llvm::LoopBase< BlockT, LoopT >::getExitingBlocks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::BasicBlock::getModule(), llvm::Value::getName(), llvm::LoopBase< BlockT, LoopT >::getNumBackEdges(), llvm::Instruction::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlock::getTerminator(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::InsertPreheaderForLoop(), insertUniqueBackedgeBlock(), llvm::BasicBlock::instructionsWithoutDebug(), llvm::BranchInst::isConditional(), LLVM_DEBUG, llvm::Loop::makeLoopInvariant(), P, llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::LoopInfoBase< BlockT, LoopT >::removeBlock(), llvm::Value::replaceAllUsesWith(), llvm::LoopInfo::replacementPreservesLCSSAForm(), separateNestedLoop(), llvm::SimplifyInstruction(), and llvm::successors().

Referenced by llvm::simplifyLoop().

STATISTIC()

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

Variable Documentation

false

loop Canonicalize natural false

Definition at line 753 of file LoopSimplify.cpp.

loops

loop Canonicalize natural loops

Definition at line 753 of file LoopSimplify.cpp.

simplify

loop simplify

Definition at line 753 of file LoopSimplify.cpp.