LCSSA.cpp File Reference

#include "llvm/Transforms/Utils/LCSSA.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PredIteratorCache.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "lcssa"

Typedefs
using	LoopExitBlocksTy = SmallDenseMap<Loop *, SmallVector<BasicBlock *, 1>>

Functions
	STATISTIC (NumLCSSA, "Number of live out of a loop variables")
static bool	isExitBlock (BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &ExitBlocks)
	Return true if the specified block is in the list.
static bool	formLCSSAForInstructionsImpl (SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove, SmallVectorImpl< PHINode * > *InsertedPHIs, LoopExitBlocksTy &LoopExitBlocks)
	For every instruction from the worklist, check to see if it has any uses that are outside the current loop.
static void	computeBlocksDominatingExits (Loop &L, const DominatorTree &DT, ArrayRef< BasicBlock * > ExitBlocks, SmallSetVector< BasicBlock *, 8 > &BlocksDominatingExits)
static bool	formLCSSAImpl (Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE, LoopExitBlocksTy &LoopExitBlocks)
static bool	formLCSSARecursivelyImpl (Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE, LoopExitBlocksTy &LoopExitBlocks)
	Process a loop nest depth first.
static bool	formLCSSAOnAllLoops (const LoopInfo *LI, const DominatorTree &DT, ScalarEvolution *SE)
	Process all loops in the function, inner-most out.
	INITIALIZE_PASS_BEGIN (LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass", false, false) INITIALIZE_PASS_END(LCSSAWrapperPass

Variables
static bool	VerifyLoopLCSSA = false
static cl::opt< bool, true >	VerifyLoopLCSSAFlag ("verify-loop-lcssa", cl::location(VerifyLoopLCSSA), cl::Hidden, cl::desc("Verify loop lcssa form (time consuming)"))
	lcssa
Loop Closed SSA Form	Pass
Loop Closed SSA Form	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "lcssa"

Definition at line 53 of file LCSSA.cpp.

Typedef Documentation

LoopExitBlocksTy

using LoopExitBlocksTy = SmallDenseMap<Loop *, SmallVector<BasicBlock *, 1>>

Definition at line 76 of file LCSSA.cpp.

Function Documentation

computeBlocksDominatingExits()

void computeBlocksDominatingExits ( Loop & L, const DominatorTree & DT, ArrayRef< BasicBlock * > ExitBlocks, SmallSetVector< BasicBlock *, 8 > & BlocksDominatingExits )

static

Definition at line 320 of file LCSSA.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::SetVector< T, Vector, Set, N >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by formLCSSAImpl().

formLCSSAForInstructionsImpl()

bool formLCSSAForInstructionsImpl ( SmallVectorImpl< Instruction * > & Worklist, const DominatorTree & DT, const LoopInfo & LI, ScalarEvolution * SE, SmallVectorImpl< PHINode * > * PHIsToRemove, SmallVectorImpl< PHINode * > * InsertedPHIs, LoopExitBlocksTy & LoopExitBlocks )

static

For every instruction from the worklist, check to see if it has any uses that are outside the current loop.

If so, insert LCSSA PHI nodes and rewrite the uses.

Definition at line 82 of file LCSSA.cpp.

References llvm::SSAUpdater::AddAvailableValue(), llvm::PHINode::addIncoming(), llvm::SmallVectorImpl< T >::append(), assert(), llvm::BasicBlock::begin(), llvm::SetVector< T, Vector, Set, N >::begin(), llvm::cast(), Changed, llvm::SmallVectorImpl< T >::clear(), llvm::PHINode::Create(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::SetVector< T, Vector, Set, N >::end(), llvm::findDbgValues(), llvm::SSAUpdater::FindValueForBlock(), llvm::BasicBlock::front(), llvm::PoisonValue::get(), llvm::PredIteratorCache::get(), llvm::ScalarEvolution::getExistingSCEV(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::BasicBlock::getMarker(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::PHINode::getNumIncomingValues(), llvm::PHINode::getOperandNumForIncomingValue(), llvm::User::getOperandUse(), llvm::DbgMarker::getParent(), llvm::ScalarEvolution::getSCEV(), llvm::SSAUpdater::HasValueForBlock(), I, llvm::SSAUpdater::Initialize(), llvm::SetVector< T, Vector, Set, N >::insert(), llvm::Instruction::insertBefore(), llvm::isa(), isExitBlock(), llvm::DominatorTree::isReachableFromEntry(), llvm::ScalarEvolution::isSCEVable(), llvm::make_early_inc_range(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SSAUpdater::RewriteUse(), llvm::Instruction::setDebugLoc(), llvm::PredIteratorCache::size(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

Referenced by llvm::formLCSSAForInstructions(), and formLCSSAImpl().

formLCSSAImpl()

bool formLCSSAImpl ( Loop & L, const DominatorTree & DT, const LoopInfo * LI, ScalarEvolution * SE, LoopExitBlocksTy & LoopExitBlocks )

static

Definition at line 362 of file LCSSA.cpp.

References assert(), Changed, computeBlocksDominatingExits(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), formLCSSAForInstructionsImpl(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), I, llvm::isa(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::formLCSSA(), and formLCSSARecursivelyImpl().

formLCSSAOnAllLoops()

bool formLCSSAOnAllLoops ( const LoopInfo * LI, const DominatorTree & DT, ScalarEvolution * SE )

static

Process all loops in the function, inner-most out.

Definition at line 457 of file LCSSA.cpp.

References Changed, and llvm::formLCSSARecursively().

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

formLCSSARecursivelyImpl()

bool formLCSSARecursivelyImpl ( Loop & L, const DominatorTree & DT, const LoopInfo * LI, ScalarEvolution * SE, LoopExitBlocksTy & LoopExitBlocks )

static

Process a loop nest depth first.

Definition at line 435 of file LCSSA.cpp.

References Changed, formLCSSAImpl(), and formLCSSARecursivelyImpl().

Referenced by llvm::formLCSSARecursively(), and formLCSSARecursivelyImpl().

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	LCSSAWrapperPass	,
		"lcssa"	,
		"Loop-Closed SSA Form Pass"	,
		false	,
		false	)

References INITIALIZE_PASS_DEPENDENCY.

isExitBlock()

bool isExitBlock ( BasicBlock * BB, const SmallVectorImpl< BasicBlock * > & ExitBlocks )

static

Return true if the specified block is in the list.

Definition at line 68 of file LCSSA.cpp.

References llvm::is_contained().

Referenced by formLCSSAForInstructionsImpl(), and llvm::LoopBase< BlockT, LoopT >::getExitingBlock().

STATISTIC()

STATISTIC	(	NumLCSSA	,
		"Number of live out of a loop variables"	)

References VerifyLoopLCSSA.

Variable Documentation

false

Loop Closed SSA Form false

Definition at line 523 of file LCSSA.cpp.

lcssa

lcssa

Definition at line 522 of file LCSSA.cpp.

Pass

Loop Closed SSA Form Pass

Definition at line 522 of file LCSSA.cpp.

VerifyLoopLCSSA

bool VerifyLoopLCSSA = false

static

Definition at line 60 of file LCSSA.cpp.

Referenced by STATISTIC().

VerifyLoopLCSSAFlag

cl::opt< bool, true > VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA), cl::Hidden, cl::desc("Verify loop lcssa form (time consuming)")) ( "verify-loop-lcssa" , cl::location(VerifyLoopLCSSA) , cl::Hidden , cl::desc("Verify loop lcssa form (time consuming)")  )

static