SCCP.cpp File Reference

#include "llvm/Transforms/Scalar/SCCP.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueLattice.h"
#include "llvm/Analysis/ValueLatticeUtils.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SCCPSolver.h"
#include <cassert>
#include <utility>
#include <vector>

Include dependency graph for SCCP.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "sccp"

Functions
	STATISTIC (NumInstRemoved, "Number of instructions removed")
	STATISTIC (NumDeadBlocks, "Number of basic blocks unreachable")
	STATISTIC (NumInstReplaced, "Number of instructions replaced with (simpler) instruction")
	STATISTIC (IPNumInstRemoved, "Number of instructions removed by IPSCCP")
	STATISTIC (IPNumArgsElimed,"Number of arguments constant propagated by IPSCCP")
	STATISTIC (IPNumGlobalConst, "Number of globals found to be constant by IPSCCP")
	STATISTIC (IPNumInstReplaced, "Number of instructions replaced with (simpler) instruction by IPSCCP")
static bool	isConstant (const ValueLatticeElement &LV)
static bool	isOverdefined (const ValueLatticeElement &LV)
static bool	canRemoveInstruction (Instruction *I)
static bool	tryToReplaceWithConstant (SCCPSolver &Solver, Value *V)
static bool	replaceSignedInst (SCCPSolver &Solver, SmallPtrSetImpl< Value * > &InsertedValues, Instruction &Inst)
	Try to replace signed instructions with their unsigned equivalent. More...
static bool	simplifyInstsInBlock (SCCPSolver &Solver, BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)
static bool	removeNonFeasibleEdges (const SCCPSolver &Solver, BasicBlock *BB, DomTreeUpdater &DTU, BasicBlock *&NewUnreachableBB)
static bool	runSCCP (Function &F, const DataLayout &DL, const TargetLibraryInfo *TLI, DomTreeUpdater &DTU)
	INITIALIZE_PASS_BEGIN (SCCPLegacyPass, "sccp", "Sparse Conditional Constant Propagation", false, false) INITIALIZE_PASS_END(SCCPLegacyPass
static void	findReturnsToZap (Function &F, SmallVector< ReturnInst *, 8 > &ReturnsToZap, SCCPSolver &Solver)

Variables
	sccp
Sparse Conditional Constant	Propagation
Sparse Conditional Constant	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "sccp"

Definition at line 63 of file SCCP.cpp.

Function Documentation

canRemoveInstruction()

static bool canRemoveInstruction ( Instruction *  I )

static

Definition at line 94 of file SCCP.cpp.

References I, and llvm::wouldInstructionBeTriviallyDead().

Referenced by simplifyInstsInBlock(), and tryToReplaceWithConstant().

findReturnsToZap()

static void findReturnsToZap ( Function &  F, SmallVector< ReturnInst *, 8 > &  ReturnsToZap, SCCPSolver &  Solver  )

static

Definition at line 370 of file SCCP.cpp.

References llvm::all_of(), assert(), llvm::dbgs(), F, llvm::SCCPSolver::getLatticeValueFor(), llvm::SCCPSolver::isArgumentTrackedFunction(), isOverdefined(), LLVM_DEBUG, and llvm::SCCPSolver::mustPreserveReturn().

Referenced by llvm::runIPSCCP().

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	SCCPLegacyPass	,
		"sccp"	,
		"Sparse Conditional Constant Propagation"	,
		false	,
		false
	)

isConstant()

static bool isConstant ( const ValueLatticeElement &  LV )

static

Definition at line 81 of file SCCP.cpp.

References llvm::ValueLatticeElement::getConstantRange(), llvm::ValueLatticeElement::isConstant(), llvm::ValueLatticeElement::isConstantRange(), and llvm::ConstantRange::isSingleElement().

Referenced by isOverdefined(), llvm::runIPSCCP(), and tryToReplaceWithConstant().

isOverdefined()

static bool isOverdefined ( const ValueLatticeElement &  LV )

static

Definition at line 90 of file SCCP.cpp.

References isConstant(), and llvm::ValueLatticeElement::isUnknownOrUndef().

Referenced by findReturnsToZap(), llvm::runIPSCCP(), and tryToReplaceWithConstant().

removeNonFeasibleEdges()

static bool removeNonFeasibleEdges ( const SCCPSolver &  Solver, BasicBlock *  BB, DomTreeUpdater &  DTU, BasicBlock *&  NewUnreachableBB  )

static

Definition at line 422 of file SCCP.cpp.

References llvm::DomTreeUpdater::applyUpdatesPermissive(), assert(), BB, llvm::SmallPtrSetImpl< PtrType >::begin(), llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::Instruction::eraseFromParent(), llvm::BasicBlock::getContext(), llvm::BasicBlock::getParent(), Insert, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SCCPSolver::isEdgeFeasible(), llvm_unreachable, llvm::BasicBlock::removePredecessor(), SI, llvm::SmallPtrSetImplBase::size(), and llvm::successors().

Referenced by llvm::runIPSCCP(), and runSCCP().

replaceSignedInst()

static bool replaceSignedInst ( SCCPSolver &  Solver, SmallPtrSetImpl< Value * > &  InsertedValues, Instruction &  Inst  )

static

Try to replace signed instructions with their unsigned equivalent.

Definition at line 158 of file SCCP.cpp.

References assert(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::BinaryOperator::Create(), llvm::Instruction::eraseFromParent(), llvm::SCCPSolver::getLatticeValueFor(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::SmallPtrSetImpl< PtrType >::insert(), isNonNegative(), IV, llvm::SCCPSolver::removeLatticeValueFor(), llvm::Value::replaceAllUsesWith(), and llvm::Value::takeName().

Referenced by simplifyInstsInBlock().

runSCCP()

static bool runSCCP ( Function &  F, const DataLayout &  DL, const TargetLibraryInfo *  TLI, DomTreeUpdater &  DTU  )

static

Definition at line 248 of file SCCP.cpp.

References BB, llvm::changeToUnreachable(), llvm::dbgs(), llvm::DomTreeUpdater::deleteBB(), DL, F, llvm::SCCPSolver::isBlockExecutable(), LLVM_DEBUG, llvm::SCCPSolver::markBlockExecutable(), llvm::SCCPSolver::markOverdefined(), removeNonFeasibleEdges(), llvm::SCCPSolver::resolvedUndefsIn(), simplifyInstsInBlock(), and llvm::SCCPSolver::solve().

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

simplifyInstsInBlock()

static bool simplifyInstsInBlock ( SCCPSolver &  Solver, BasicBlock &  BB, SmallPtrSetImpl< Value * > &  InsertedValues, Statistic &  InstRemovedStat, Statistic &  InstReplacedStat  )

static

Definition at line 220 of file SCCP.cpp.

References BB, canRemoveInstruction(), llvm::make_early_inc_range(), replaceSignedInst(), and tryToReplaceWithConstant().

Referenced by llvm::runIPSCCP(), and runSCCP().

STATISTIC() [1/7]

STATISTIC	(	IPNumArgsElimed	,
		"Number of arguments constant propagated by IPSCCP"
	)

STATISTIC() [2/7]

STATISTIC	(	IPNumGlobalConst	,
		"Number of globals found to be constant by IPSCCP"
	)

STATISTIC() [3/7]

STATISTIC	(	IPNumInstRemoved	,
		"Number of instructions removed by IPSCCP"
	)

STATISTIC() [4/7]

STATISTIC	(	IPNumInstReplaced	,
		"Number of instructions replaced with (simpler) instruction by IPSCCP"
	)

STATISTIC() [5/7]

STATISTIC	(	NumDeadBlocks	,
		"Number of basic blocks unreachable"
	)

STATISTIC() [6/7]

STATISTIC	(	NumInstRemoved	,
		"Number of instructions removed"
	)

STATISTIC() [7/7]

STATISTIC	(	NumInstReplaced	,
		"Number of instructions replaced with (simpler) instruction"
	)

tryToReplaceWithConstant()

static bool tryToReplaceWithConstant ( SCCPSolver &  Solver, Value *  V  )

static

Definition at line 106 of file SCCP.cpp.

References llvm::SCCPSolver::addToMustPreserveReturnsInFunctions(), llvm::any_of(), assert(), canRemoveInstruction(), llvm::dbgs(), llvm::numbers::e, F, llvm::ConstantStruct::get(), llvm::UndefValue::get(), llvm::CallBase::getCalledFunction(), llvm::SCCPSolver::getConstant(), llvm::SCCPSolver::getLatticeValueFor(), llvm::CallBase::getOperandBundle(), llvm::SCCPSolver::getStructLatticeValueFor(), llvm::Value::getType(), i, isConstant(), llvm::CallBase::isMustTailCall(), isOverdefined(), llvm::Type::isStructTy(), IV, LLVM_DEBUG, llvm::LLVMContext::OB_clang_arc_attachedcall, llvm::Value::replaceAllUsesWith(), and llvm::ARM_MB::ST.

Referenced by llvm::runIPSCCP(), and simplifyInstsInBlock().

Variable Documentation

false

Sparse Conditional Constant false

Definition at line 365 of file SCCP.cpp.

Propagation

Sparse Conditional Constant Propagation

Definition at line 365 of file SCCP.cpp.

sccp

sccp

Definition at line 364 of file SCCP.cpp.