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/IntrinsicInst.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 54 of file LCSSA.cpp.

Typedef Documentation

LoopExitBlocksTy

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

Definition at line 77 of file LCSSA.cpp.

Function Documentation

computeBlocksDominatingExits()

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

static

Definition at line 337 of file LCSSA.cpp.

References llvm::SmallVectorBase< Size_T >::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()

static 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 83 of file LCSSA.cpp.

References llvm::SSAUpdater::AddAvailableValue(), llvm::PHINode::addIncoming(), llvm::SmallVectorImpl< T >::append(), assert(), llvm::SetVector< T, Vector, Set, N >::begin(), llvm::BasicBlock::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::PHINode::Create(), llvm::DominatorTree::dominates(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SetVector< T, Vector, Set, N >::end(), llvm::findDbgValues(), llvm::SSAUpdater::FindValueForBlock(), llvm::BasicBlock::front(), llvm::PredIteratorCache::get(), llvm::PoisonValue::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::BasicBlock::getParent(), llvm::DbgMarker::getParent(), llvm::ScalarEvolution::getSCEV(), llvm::SSAUpdater::HasValueForBlock(), I, llvm::SSAUpdater::Initialize(), llvm::SetVector< T, Vector, Set, N >::insert(), llvm::Instruction::insertBefore(), 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::SmallVectorBase< Size_T >::size(), and llvm::PredIteratorCache::size().

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

formLCSSAImpl()

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

static

Definition at line 379 of file LCSSA.cpp.

References assert(), computeBlocksDominatingExits(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::SmallVectorBase< Size_T >::empty(), formLCSSAForInstructionsImpl(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), I, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

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

formLCSSAOnAllLoops()

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

static

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

Definition at line 473 of file LCSSA.cpp.

References llvm::formLCSSARecursively().

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

formLCSSARecursivelyImpl()

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

static

Process a loop nest depth first.

Definition at line 451 of file LCSSA.cpp.

References formLCSSAImpl(), and formLCSSARecursivelyImpl().

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

INITIALIZE_PASS_BEGIN()

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

isExitBlock()

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

static

Return true if the specified block is in the list.

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

Variable Documentation

false

Loop Closed SSA Form false

Definition at line 539 of file LCSSA.cpp.

lcssa

lcssa

Definition at line 538 of file LCSSA.cpp.

Pass

Loop Closed SSA Form Pass

Definition at line 538 of file LCSSA.cpp.

VerifyLoopLCSSA

bool VerifyLoopLCSSA = false

static

Definition at line 61 of file LCSSA.cpp.

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