#include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cassert>
#include <utility>

Include dependency graph for CorrelatedValuePropagation.cpp:

Macros
#define	DEBUG_TYPE "correlated-value-propagation"

Enumerations
enum	Domain { Domain::NonNegative, Domain::NonPositive, Domain::Unknown }

Functions
	STATISTIC (NumPhis, "Number of phis propagated")

	STATISTIC (NumPhiCommon, "Number of phis deleted via common incoming value")

	STATISTIC (NumSelects, "Number of selects propagated")

	STATISTIC (NumMemAccess, "Number of memory access targets propagated")

	STATISTIC (NumCmps, "Number of comparisons propagated")

	STATISTIC (NumReturns, "Number of return values propagated")

	STATISTIC (NumDeadCases, "Number of switch cases removed")

	STATISTIC (NumSDivSRemsNarrowed, "Number of sdivs/srems whose width was decreased")

	STATISTIC (NumSDivs, "Number of sdiv converted to udiv")

	STATISTIC (NumUDivURemsNarrowed, "Number of udivs/urems whose width was decreased")

	STATISTIC (NumAShrsConverted, "Number of ashr converted to lshr")

	STATISTIC (NumAShrsRemoved, "Number of ashr removed")

	STATISTIC (NumSRems, "Number of srem converted to urem")

	STATISTIC (NumSExt, "Number of sext converted to zext")

	STATISTIC (NumSICmps, "Number of signed icmp preds simplified to unsigned")

	STATISTIC (NumAnd, "Number of ands removed")

	STATISTIC (NumNW, "Number of no-wrap deductions")

	STATISTIC (NumNSW, "Number of no-signed-wrap deductions")

	STATISTIC (NumNUW, "Number of no-unsigned-wrap deductions")

	STATISTIC (NumAddNW, "Number of no-wrap deductions for add")

	STATISTIC (NumAddNSW, "Number of no-signed-wrap deductions for add")

	STATISTIC (NumAddNUW, "Number of no-unsigned-wrap deductions for add")

	STATISTIC (NumSubNW, "Number of no-wrap deductions for sub")

	STATISTIC (NumSubNSW, "Number of no-signed-wrap deductions for sub")

	STATISTIC (NumSubNUW, "Number of no-unsigned-wrap deductions for sub")

	STATISTIC (NumMulNW, "Number of no-wrap deductions for mul")

	STATISTIC (NumMulNSW, "Number of no-signed-wrap deductions for mul")

	STATISTIC (NumMulNUW, "Number of no-unsigned-wrap deductions for mul")

	STATISTIC (NumShlNW, "Number of no-wrap deductions for shl")

	STATISTIC (NumShlNSW, "Number of no-signed-wrap deductions for shl")

	STATISTIC (NumShlNUW, "Number of no-unsigned-wrap deductions for shl")

	STATISTIC (NumAbs, "Number of llvm.abs intrinsics removed")

	STATISTIC (NumOverflows, "Number of overflow checks removed")

	STATISTIC (NumSaturating, "Number of saturating arithmetics converted to normal arithmetics")

	STATISTIC (NumNonNull, "Number of function pointer arguments marked non-null")

	STATISTIC (NumMinMax, "Number of llvm.[us]{min,max} intrinsics removed")

	INITIALIZE_PASS_BEGIN (CorrelatedValuePropagation, "correlated-propagation", "Value Propagation", false, false) INITIALIZE_PASS_END(CorrelatedValuePropagation

static bool	processSelect (SelectInst S, LazyValueInfo LVI)

static bool	simplifyCommonValuePhi (PHINode P, LazyValueInfo LVI, DominatorTree *DT)
	Try to simplify a phi with constant incoming values that match the edge values of a non-constant value on all other edges: bb0: isnull = icmp eq i8* x, null br i1 isnull, label bb2, label bb1 bb1: br label bb2 bb2: r = phi i8* [ x, bb1 ], [ null, bb0 ] --> r = x. More...

static Value *	getValueOnEdge (LazyValueInfo LVI, Value Incoming, BasicBlock From, BasicBlock To, Instruction *CxtI)

static bool	processPHI (PHINode P, LazyValueInfo LVI, DominatorTree *DT, const SimplifyQuery &SQ)

static bool	processMemAccess (Instruction I, LazyValueInfo LVI)

static bool	processICmp (ICmpInst Cmp, LazyValueInfo LVI)

static bool	constantFoldCmp (CmpInst Cmp, LazyValueInfo LVI)
	See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove this comparison. More...

static bool	processCmp (CmpInst Cmp, LazyValueInfo LVI)

static bool	processSwitch (SwitchInst I, LazyValueInfo LVI, DominatorTree *DT)
	Simplify a switch instruction by removing cases which can never fire. More...

static bool	willNotOverflow (BinaryOpIntrinsic BO, LazyValueInfo LVI)

static void	setDeducedOverflowingFlags (Value *V, Instruction::BinaryOps Opcode, bool NewNSW, bool NewNUW)

static bool	processBinOp (BinaryOperator BinOp, LazyValueInfo LVI)

static bool	processAbsIntrinsic (IntrinsicInst II, LazyValueInfo LVI)

static bool	processMinMaxIntrinsic (MinMaxIntrinsic MM, LazyValueInfo LVI)

static bool	processOverflowIntrinsic (WithOverflowInst WO, LazyValueInfo LVI)

static bool	processSaturatingInst (SaturatingInst SI, LazyValueInfo LVI)

static bool	processCallSite (CallBase &CB, LazyValueInfo *LVI)
	Infer nonnull attributes for the arguments at the specified callsite. More...

static bool	isNonNegative (Value V, LazyValueInfo LVI, Instruction *CxtI)

static bool	isNonPositive (Value V, LazyValueInfo LVI, Instruction *CxtI)

Domain	getDomain (Value V, LazyValueInfo LVI, Instruction *CxtI)

static bool	narrowSDivOrSRem (BinaryOperator Instr, LazyValueInfo LVI)
	Try to shrink a sdiv/srem's width down to the smallest power of two that's sufficient to contain its operands. More...

static bool	processUDivOrURem (BinaryOperator Instr, LazyValueInfo LVI)
	Try to shrink a udiv/urem's width down to the smallest power of two that's sufficient to contain its operands. More...

static bool	processSRem (BinaryOperator SDI, LazyValueInfo LVI)

static bool	processSDiv (BinaryOperator SDI, LazyValueInfo LVI)
	See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove the signs of both operands of this SDiv. More...

static bool	processSDivOrSRem (BinaryOperator Instr, LazyValueInfo LVI)

static bool	processAShr (BinaryOperator SDI, LazyValueInfo LVI)

static bool	processSExt (SExtInst SDI, LazyValueInfo LVI)

static bool	processAnd (BinaryOperator BinOp, LazyValueInfo LVI)

static Constant *	getConstantAt (Value V, Instruction At, LazyValueInfo *LVI)

static bool	runImpl (Function &F, LazyValueInfo LVI, DominatorTree DT, const SimplifyQuery &SQ)

Variables
static cl::opt< bool >	CanonicalizeICmpPredicatesToUnsigned ("canonicalize-icmp-predicates-to-unsigned", cl::init(true), cl::Hidden, cl::desc("Enables canonicalization of signed relational predicates to " "unsigned (e.g. sgt => ugt)"))

correlated	propagation

correlated Value	Propagation

correlated Value	false

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "correlated-value-propagation"

Definition at line 51 of file CorrelatedValuePropagation.cpp.

Enumeration Type Documentation

◆ Domain

enum Domain

strong

Enumerator
NonNegative
NonPositive
Unknown

Definition at line 710 of file CorrelatedValuePropagation.cpp.

Function Documentation

◆ constantFoldCmp()

static bool constantFoldCmp	(	CmpInst *	Cmp,
		LazyValueInfo *	LVI
	)

static

See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove this comparison.

Even for local conditions, this can sometimes prove conditions instcombine can't by exploiting range information.

Definition at line 341 of file CorrelatedValuePropagation.cpp.

References llvm::ConstantInt::get(), llvm::Type::getInt1Ty(), llvm::LazyValueInfo::getPredicateAt(), and llvm::LazyValueInfo::Unknown.

Referenced by processCmp().

◆ getConstantAt()

static Constant* getConstantAt	(	Value *	V,
		Instruction *	At,
		LazyValueInfo *	LVI
	)

static

Definition at line 1057 of file CorrelatedValuePropagation.cpp.

References llvm::LazyValueInfo::getConstant(), llvm::ConstantInt::getFalse(), llvm::LazyValueInfo::getPredicateAt(), llvm::ConstantInt::getTrue(), llvm::LazyValueInfo::True, and llvm::LazyValueInfo::Unknown.

Referenced by runImpl().

◆ getDomain()

Domain getDomain	(	Value *	V,
		LazyValueInfo *	LVI,
		Instruction *	CxtI
	)

Definition at line 712 of file CorrelatedValuePropagation.cpp.

References isNonNegative(), isNonPositive(), NonNegative, NonPositive, and Unknown.

Referenced by collectMDInDomain(), llvm::MDNode::getMostGenericAliasScope(), processSDiv(), and processSRem().

◆ getValueOnEdge()

static Value* getValueOnEdge	(	LazyValueInfo *	LVI,
		Value *	Incoming,
		BasicBlock *	From,
		BasicBlock *	To,
		Instruction *	CxtI
	)

static

Definition at line 216 of file CorrelatedValuePropagation.cpp.

References llvm::LazyValueInfo::False, From, llvm::LazyValueInfo::getConstantOnEdge(), llvm::LazyValueInfo::getPredicateOnEdge(), llvm::Value::getType(), llvm::CmpInst::ICMP_EQ, llvm::Type::isVectorTy(), and SI.

Referenced by processPHI().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	CorrelatedValuePropagation	,
		"correlated-propagation"	,
		"Value Propagation"	,
		false	,
		false
	)

◆ isNonNegative()

static bool isNonNegative	(	Value *	V,
		LazyValueInfo *	LVI,
		Instruction *	CxtI
	)

static

Definition at line 696 of file CorrelatedValuePropagation.cpp.

References llvm::ConstantInt::get(), llvm::LazyValueInfo::getPredicateAt(), llvm::Value::getType(), llvm::CmpInst::ICMP_SGE, and llvm::LazyValueInfo::True.

Referenced by llvm::ConstantRange::ashr(), getDomain(), llvm::APInt::isNegatedPowerOf2(), llvm::APSInt::isStrictlyPositive(), llvm::APInt::isStrictlyPositive(), processAShr(), processSExt(), and replaceSignedInst().

◆ isNonPositive()

static bool isNonPositive	(	Value *	V,
		LazyValueInfo *	LVI,
		Instruction *	CxtI
	)

static

Definition at line 703 of file CorrelatedValuePropagation.cpp.

References llvm::ConstantInt::get(), llvm::LazyValueInfo::getPredicateAt(), llvm::Value::getType(), llvm::CmpInst::ICMP_SLE, and llvm::LazyValueInfo::True.

Referenced by getDomain().

◆ narrowSDivOrSRem()

static bool narrowSDivOrSRem	(	BinaryOperator *	Instr,
		LazyValueInfo *	LVI
	)

static

Try to shrink a sdiv/srem's width down to the smallest power of two that's sufficient to contain its operands.

Definition at line 722 of file CorrelatedValuePropagation.cpp.

References assert(), B, contains(), llvm::Instruction::eraseFromParent(), llvm::APInt::getAllOnes(), llvm::LazyValueInfo::getConstantRange(), llvm::Value::getContext(), llvm::Type::getIntegerBitWidth(), llvm::Type::getIntNTy(), llvm::Value::getName(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::APInt::getSignedMinValue(), llvm::Value::getType(), I, llvm::Instruction::isExact(), llvm::Type::isVectorTy(), LHS, llvm::max(), llvm::User::operands(), llvm::PowerOf2Ceil(), llvm::Value::replaceAllUsesWith(), RHS, and llvm::zip().

Referenced by processSDivOrSRem().

◆ processAbsIntrinsic()

static bool processAbsIntrinsic	(	IntrinsicInst *	II,
		LazyValueInfo *	LVI
	)

static

◆ processAnd()

static bool processAnd	(	BinaryOperator *	BinOp,
		LazyValueInfo *	LVI
	)

static

Definition at line 1032 of file CorrelatedValuePropagation.cpp.

References llvm::Instruction::eraseFromParent(), llvm::LazyValueInfo::getConstantRange(), llvm::User::getOperand(), llvm::Value::getType(), llvm::ConstantRange::getUnsignedMax(), llvm::Type::isVectorTy(), LHS, llvm::Value::replaceAllUsesWith(), RHS, and llvm::APInt::ule().

Referenced by runImpl().

◆ processAShr()

static bool processAShr	(	BinaryOperator *	SDI,
		LazyValueInfo *	LVI
	)

static

Definition at line 944 of file CorrelatedValuePropagation.cpp.

References llvm::ConstantRange::contains(), llvm::Instruction::eraseFromParent(), llvm::LazyValueInfo::getConstantRange(), llvm::Instruction::getDebugLoc(), llvm::Type::getIntegerBitWidth(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Instruction::isExact(), isNonNegative(), llvm::Type::isVectorTy(), and llvm::Value::replaceAllUsesWith().

Referenced by runImpl().

◆ processBinOp()

static bool processBinOp	(	BinaryOperator *	BinOp,
		LazyValueInfo *	LVI
	)

static

Definition at line 994 of file CorrelatedValuePropagation.cpp.

References llvm::ConstantRange::contains(), llvm::LazyValueInfo::getConstantRange(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Instruction::hasNoSignedWrap(), llvm::Instruction::hasNoUnsignedWrap(), llvm::Type::isVectorTy(), LHS, llvm::ConstantRange::makeGuaranteedNoWrapRegion(), RHS, and setDeducedOverflowingFlags().

Referenced by processAbsIntrinsic(), processOverflowIntrinsic(), processSaturatingInst(), and runImpl().

◆ processCallSite()

static bool processCallSite	(	CallBase &	CB,
		LazyValueInfo *	LVI
	)

static

Infer nonnull attributes for the arguments at the specified callsite.

Definition at line 619 of file CorrelatedValuePropagation.cpp.

References llvm::abs(), llvm::AttributeList::addParamAttribute(), llvm::CallBase::arg_size(), llvm::CallBase::args(), assert(), llvm::LazyValueInfo::False, llvm::Use::get(), llvm::Attribute::get(), llvm::ConstantPointerNull::get(), llvm::CallBase::getAttributes(), llvm::LazyValueInfo::getConstant(), llvm::Value::getContext(), llvm::CallBase::getIntrinsicID(), llvm::CallBase::getOperandBundle(), llvm::LazyValueInfo::getPredicateAt(), llvm::Value::getType(), llvm::CmpInst::ICMP_EQ, llvm::Type::isVectorTy(), llvm::LLVMContext::OB_deopt, llvm::CallBase::paramHasAttr(), processAbsIntrinsic(), processMinMaxIntrinsic(), processOverflowIntrinsic(), processSaturatingInst(), llvm::Use::set(), llvm::CallBase::setAttributes(), SI, and willNotOverflow().

Referenced by runImpl().

◆ processCmp()

static bool processCmp	(	CmpInst *	Cmp,
		LazyValueInfo *	LVI
	)

static

Definition at line 360 of file CorrelatedValuePropagation.cpp.

References constantFoldCmp(), and processICmp().

Referenced by runImpl().

◆ processICmp()

static bool processICmp	(	ICmpInst *	Cmp,
		LazyValueInfo *	LVI
	)

static

Definition at line 311 of file CorrelatedValuePropagation.cpp.

References CanonicalizeICmpPredicatesToUnsigned, llvm::LazyValueInfo::getConstantRange(), and llvm::ConstantRange::getEquivalentPredWithFlippedSignedness().

Referenced by processCmp().

◆ processMemAccess()

static bool processMemAccess	(	Instruction *	I,
		LazyValueInfo *	LVI
	)

static

Definition at line 294 of file CorrelatedValuePropagation.cpp.

References llvm::LazyValueInfo::getConstant(), and I.

Referenced by runImpl().

◆ processMinMaxIntrinsic()

static bool processMinMaxIntrinsic	(	MinMaxIntrinsic *	MM,
		LazyValueInfo *	LVI
	)

static

Definition at line 558 of file CorrelatedValuePropagation.cpp.

References llvm::Instruction::eraseFromParent(), llvm::MinMaxIntrinsic::getLHS(), llvm::CmpInst::getNonStrictPredicate(), llvm::User::getOperand(), llvm::MinMaxIntrinsic::getPredicate(), llvm::LazyValueInfo::getPredicateAt(), llvm::MinMaxIntrinsic::getRHS(), llvm::Value::replaceAllUsesWith(), and llvm::LazyValueInfo::Unknown.

Referenced by processCallSite().

◆ processOverflowIntrinsic()

static bool processOverflowIntrinsic	(	WithOverflowInst *	WO,
		LazyValueInfo *	LVI
	)

static

Definition at line 572 of file CorrelatedValuePropagation.cpp.

References B, llvm::Instruction::eraseFromParent(), llvm::ConstantStruct::get(), llvm::PoisonValue::get(), llvm::BinaryOpIntrinsic::getBinaryOp(), llvm::ConstantInt::getFalse(), llvm::BinaryOpIntrinsic::getLHS(), llvm::Value::getName(), llvm::BinaryOpIntrinsic::getRHS(), llvm::Value::getType(), llvm::BinaryOpIntrinsic::isSigned(), processBinOp(), llvm::Value::replaceAllUsesWith(), setDeducedOverflowingFlags(), llvm::ARM_MB::ST, and Struct.

Referenced by processCallSite().

◆ processPHI()

static bool processPHI	(	PHINode *	P,
		LazyValueInfo *	LVI,
		DominatorTree *	DT,
		const SimplifyQuery &	SQ
	)

static

Definition at line 263 of file CorrelatedValuePropagation.cpp.

References BB, llvm::numbers::e, getValueOnEdge(), i, P, simplifyCommonValuePhi(), and llvm::simplifyInstruction().

Referenced by runImpl().

◆ processSaturatingInst()

static bool processSaturatingInst	(	SaturatingInst *	SI,
		LazyValueInfo *	LVI
	)

static

Definition at line 598 of file CorrelatedValuePropagation.cpp.

References llvm::BinaryOperator::Create(), processBinOp(), llvm::Instruction::setDebugLoc(), setDeducedOverflowingFlags(), and SI.

Referenced by processCallSite().

◆ processSDiv()

static bool processSDiv	(	BinaryOperator *	SDI,
		LazyValueInfo *	LVI
	)

static

See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove the signs of both operands of this SDiv.

If this is the case, replace the SDiv with a UDiv. Even for local conditions, this can sometimes prove conditions instcombine can't by exploiting range information.

Definition at line 875 of file CorrelatedValuePropagation.cpp.

References assert(), llvm::BinaryOperator::CreateNeg(), D, llvm::Instruction::eraseFromParent(), llvm::Instruction::getDebugLoc(), getDomain(), llvm::Value::getName(), llvm::BinaryOperator::getOpcode(), llvm::Value::getType(), I, llvm::Instruction::isExact(), llvm::Type::isVectorTy(), NonNegative, llvm::User::operands(), processUDivOrURem(), llvm::Value::replaceAllUsesWith(), Unknown, and llvm::zip().

Referenced by processSDivOrSRem().

◆ processSDivOrSRem()

static bool processSDivOrSRem	(	BinaryOperator *	Instr,
		LazyValueInfo *	LVI
	)

static

Definition at line 927 of file CorrelatedValuePropagation.cpp.

References assert(), llvm::BinaryOperator::getOpcode(), llvm::Value::getType(), llvm::Type::isVectorTy(), narrowSDivOrSRem(), processSDiv(), and processSRem().

Referenced by runImpl().

◆ processSelect()

static bool processSelect	(	SelectInst *	S,
		LazyValueInfo *	LVI
	)

static

Definition at line 135 of file CorrelatedValuePropagation.cpp.

References llvm::LazyValueInfo::getConstant(), llvm::ConstantInt::isOne(), and S.

Referenced by runImpl().

◆ processSExt()

static bool processSExt	(	SExtInst *	SDI,
		LazyValueInfo *	LVI
	)

static

Definition at line 975 of file CorrelatedValuePropagation.cpp.

References llvm::sampleprof::Base, llvm::CastInst::CreateZExtOrBitCast(), llvm::Instruction::eraseFromParent(), llvm::Instruction::getDebugLoc(), llvm::User::getOperand(), llvm::Value::getType(), isNonNegative(), llvm::Type::isVectorTy(), and llvm::Value::replaceAllUsesWith().

Referenced by runImpl().

◆ processSRem()

static bool processSRem	(	BinaryOperator *	SDI,
		LazyValueInfo *	LVI
	)

static

Definition at line 817 of file CorrelatedValuePropagation.cpp.

References assert(), llvm::BinaryOperator::CreateNeg(), D, llvm::Instruction::eraseFromParent(), llvm::Instruction::getDebugLoc(), getDomain(), llvm::Value::getName(), llvm::BinaryOperator::getOpcode(), llvm::Value::getType(), I, llvm::Type::isVectorTy(), NonNegative, NonPositive, llvm::User::operands(), processUDivOrURem(), llvm::Value::replaceAllUsesWith(), Unknown, and llvm::zip().

Referenced by processSDivOrSRem().

◆ processSwitch()

static bool processSwitch	(	SwitchInst *	I,
		LazyValueInfo *	LVI,
		DominatorTree *	DT
	)

static

Simplify a switch instruction by removing cases which can never fire.

If the uselessness of a case could be determined locally then constant propagation would already have figured it out. Instead, walk the predecessors and statically evaluate cases based on information available on that edge. Cases that cannot fire no matter what the incoming edge can safely be removed. If a case fires on every incoming edge then the entire switch can be removed and replaced with a branch to the case destination.

Definition at line 378 of file CorrelatedValuePropagation.cpp.

References llvm::DomTreeUpdater::applyUpdatesPermissive(), BB, Cond, llvm::ConstantFoldTerminator(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::LazyValueInfo::False, llvm::LazyValueInfo::getPredicateAt(), I, llvm::CmpInst::ICMP_EQ, llvm::DomTreeUpdater::Lazy, llvm::BasicBlock::removePredecessor(), SI, llvm::successors(), and llvm::LazyValueInfo::True.

Referenced by llvm::PredicateInfoBuilder::buildPredicateInfo(), and runImpl().

◆ processUDivOrURem()

static bool processUDivOrURem	(	BinaryOperator *	Instr,
		LazyValueInfo *	LVI
	)

static

Try to shrink a udiv/urem's width down to the smallest power of two that's sufficient to contain its operands.

Definition at line 775 of file CorrelatedValuePropagation.cpp.

References assert(), B, llvm::Instruction::eraseFromParent(), llvm::ConstantRange::getActiveBits(), llvm::LazyValueInfo::getConstantRange(), llvm::Value::getContext(), llvm::Type::getIntegerBitWidth(), llvm::Type::getIntNTy(), llvm::Value::getName(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Instruction::isExact(), llvm::Type::isVectorTy(), LHS, llvm::max(), llvm::User::operands(), llvm::PowerOf2Ceil(), llvm::Value::replaceAllUsesWith(), and RHS.

Referenced by processSDiv(), processSRem(), and runImpl().

◆ runImpl()

static bool runImpl	(	Function &	F,
		LazyValueInfo *	LVI,
		DominatorTree *	DT,
		const SimplifyQuery &	SQ
	)

static

Definition at line 1080 of file CorrelatedValuePropagation.cpp.

References llvm::MCID::Add, BB, llvm::MCID::Call, llvm::depth_first(), F, getConstantAt(), llvm::SPII::Load, llvm::make_early_inc_range(), Mul, PHI, processAnd(), processAShr(), processBinOp(), processCallSite(), processCmp(), processMemAccess(), processPHI(), processSDivOrSRem(), processSelect(), processSExt(), processSwitch(), processUDivOrURem(), llvm::MipsISD::Ret, llvm::MCID::Select, llvm::SPII::Store, and llvm::M68kBeads::Term.

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

◆ setDeducedOverflowingFlags()

static void setDeducedOverflowingFlags	(	Value *	V,
		Instruction::BinaryOps	Opcode,
		bool	NewNSW,
		bool	NewNUW
	)

static

Definition at line 449 of file CorrelatedValuePropagation.cpp.

References llvm::MCID::Add, llvm_unreachable, and Mul.

Referenced by processBinOp(), processOverflowIntrinsic(), and processSaturatingInst().

◆ simplifyCommonValuePhi()

static bool simplifyCommonValuePhi	(	PHINode *	P,
		LazyValueInfo *	LVI,
		DominatorTree *	DT
	)

static

Try to simplify a phi with constant incoming values that match the edge values of a non-constant value on all other edges: bb0: isnull = icmp eq i8* x, null br i1 isnull, label bb2, label bb1 bb1: br label bb2 bb2: r = phi i8* [ x, bb1 ], [ null, bb0 ] --> r = x.

Definition at line 165 of file CorrelatedValuePropagation.cpp.

References llvm::DominatorTree::dominates(), llvm::numbers::e, llvm::LazyValueInfo::getConstantOnEdge(), i, llvm::isGuaranteedNotToBePoison(), and P.

Referenced by processPHI().

◆ STATISTIC() [1/36]

STATISTIC	(	NumAbs	,
		"Number of llvm.abs intrinsics removed"
	)

◆ STATISTIC() [2/36]

STATISTIC	(	NumAddNSW	,
		"Number of no-signed-wrap deductions for add"
	)

◆ STATISTIC() [3/36]

STATISTIC	(	NumAddNUW	,
		"Number of no-unsigned-wrap deductions for add"
	)

◆ STATISTIC() [4/36]

STATISTIC	(	NumAddNW	,
		"Number of no-wrap deductions for add"
	)

◆ STATISTIC() [5/36]

STATISTIC	(	NumAnd	,
		"Number of ands removed"
	)

◆ STATISTIC() [6/36]

STATISTIC	(	NumAShrsConverted	,
		"Number of ashr converted to lshr"
	)

◆ STATISTIC() [7/36]

STATISTIC	(	NumAShrsRemoved	,
		"Number of ashr removed"
	)

◆ STATISTIC() [8/36]

STATISTIC	(	NumCmps	,
		"Number of comparisons propagated"
	)

◆ STATISTIC() [9/36]

STATISTIC	(	NumDeadCases	,
		"Number of switch cases removed"
	)

◆ STATISTIC() [10/36]

STATISTIC	(	NumMemAccess	,
		"Number of memory access targets propagated"
	)

◆ STATISTIC() [11/36]

STATISTIC	(	NumMinMax	,
		"Number of llvm.{min,max} intrinsics removed"	[us]
	)

◆ STATISTIC() [12/36]

STATISTIC	(	NumMulNSW	,
		"Number of no-signed-wrap deductions for mul"
	)

◆ STATISTIC() [13/36]

STATISTIC	(	NumMulNUW	,
		"Number of no-unsigned-wrap deductions for mul"
	)

◆ STATISTIC() [14/36]

STATISTIC	(	NumMulNW	,
		"Number of no-wrap deductions for mul"
	)

◆ STATISTIC() [15/36]

STATISTIC	(	NumNonNull	,
		"Number of function pointer arguments marked non-null"
	)

◆ STATISTIC() [16/36]

STATISTIC	(	NumNSW	,
		"Number of no-signed-wrap deductions"
	)

◆ STATISTIC() [17/36]

STATISTIC	(	NumNUW	,
		"Number of no-unsigned-wrap deductions"
	)

◆ STATISTIC() [18/36]

STATISTIC	(	NumNW	,
		"Number of no-wrap deductions"
	)

◆ STATISTIC() [19/36]

STATISTIC	(	NumOverflows	,
		"Number of overflow checks removed"
	)

◆ STATISTIC() [20/36]

STATISTIC	(	NumPhiCommon	,
		"Number of phis deleted via common incoming value"
	)

◆ STATISTIC() [21/36]

STATISTIC	(	NumPhis	,
		"Number of phis propagated"
	)

◆ STATISTIC() [22/36]

STATISTIC	(	NumReturns	,
		"Number of return values propagated"
	)

◆ STATISTIC() [23/36]

STATISTIC	(	NumSaturating	,
		"Number of saturating arithmetics converted to normal arithmetics"
	)

◆ STATISTIC() [24/36]

STATISTIC	(	NumSDivs	,
		"Number of sdiv converted to udiv"
	)

◆ STATISTIC() [25/36]

STATISTIC	(	NumSDivSRemsNarrowed	,
		"Number of sdivs/srems whose width was decreased"
	)

◆ STATISTIC() [26/36]

STATISTIC	(	NumSelects	,
		"Number of selects propagated"
	)

◆ STATISTIC() [27/36]

STATISTIC	(	NumSExt	,
		"Number of sext converted to zext"
	)

◆ STATISTIC() [28/36]

STATISTIC	(	NumShlNSW	,
		"Number of no-signed-wrap deductions for shl"
	)

◆ STATISTIC() [29/36]

STATISTIC	(	NumShlNUW	,
		"Number of no-unsigned-wrap deductions for shl"
	)

◆ STATISTIC() [30/36]

STATISTIC	(	NumShlNW	,
		"Number of no-wrap deductions for shl"
	)

◆ STATISTIC() [31/36]

STATISTIC	(	NumSICmps	,
		"Number of signed icmp preds simplified to unsigned"
	)

◆ STATISTIC() [32/36]

STATISTIC	(	NumSRems	,
		"Number of srem converted to urem"
	)

◆ STATISTIC() [33/36]

STATISTIC	(	NumSubNSW	,
		"Number of no-signed-wrap deductions for sub"
	)

◆ STATISTIC() [34/36]

STATISTIC	(	NumSubNUW	,
		"Number of no-unsigned-wrap deductions for sub"
	)

◆ STATISTIC() [35/36]

STATISTIC	(	NumSubNW	,
		"Number of no-wrap deductions for sub"
	)

◆ STATISTIC() [36/36]

STATISTIC	(	NumUDivURemsNarrowed	,
		"Number of udivs/urems whose width was decreased"
	)

◆ willNotOverflow()

static bool willNotOverflow	(	BinaryOpIntrinsic *	BO,
		LazyValueInfo *	LVI
	)

static

Definition at line 441 of file CorrelatedValuePropagation.cpp.

References llvm::ConstantRange::contains(), llvm::BinaryOpIntrinsic::getBinaryOp(), llvm::LazyValueInfo::getConstantRange(), llvm::BinaryOpIntrinsic::getLHS(), llvm::BinaryOpIntrinsic::getNoWrapKind(), llvm::BinaryOpIntrinsic::getRHS(), and llvm::ConstantRange::makeGuaranteedNoWrapRegion().

Referenced by processCallSite().

Variable Documentation

◆ CanonicalizeICmpPredicatesToUnsigned

cl::opt<bool> CanonicalizeICmpPredicatesToUnsigned("canonicalize-icmp-predicates-to-unsigned", cl::init(true), cl::Hidden, cl::desc("Enables canonicalization of signed relational predicates to " "unsigned (e.g. sgt => ugt)"))

static

Referenced by processICmp().

◆ false

correlated Value false

Definition at line 128 of file CorrelatedValuePropagation.cpp.

◆ propagation

correlated propagation

Definition at line 127 of file CorrelatedValuePropagation.cpp.

◆ Propagation

correlated Value Propagation

Definition at line 128 of file CorrelatedValuePropagation.cpp.

Macros

Enumerations

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Enumeration Type Documentation

◆ Domain

Function Documentation

◆ constantFoldCmp()

◆ getConstantAt()

◆ getDomain()

◆ getValueOnEdge()

◆ INITIALIZE_PASS_BEGIN()

◆ isNonNegative()

◆ isNonPositive()

◆ narrowSDivOrSRem()

◆ processAbsIntrinsic()

◆ processAnd()

◆ processAShr()

◆ processBinOp()

◆ processCallSite()

◆ processCmp()

◆ processICmp()

◆ processMemAccess()

◆ processMinMaxIntrinsic()

◆ processOverflowIntrinsic()

◆ processPHI()

◆ processSaturatingInst()

◆ processSDiv()

◆ processSDivOrSRem()

◆ processSelect()

◆ processSExt()

◆ processSRem()

◆ processSwitch()

◆ processUDivOrURem()

◆ runImpl()

◆ setDeducedOverflowingFlags()

◆ simplifyCommonValuePhi()

◆ STATISTIC() [1/36]

◆ STATISTIC() [2/36]

◆ STATISTIC() [3/36]

◆ STATISTIC() [4/36]

◆ STATISTIC() [5/36]

◆ STATISTIC() [6/36]

◆ STATISTIC() [7/36]

◆ STATISTIC() [8/36]

◆ STATISTIC() [9/36]

◆ STATISTIC() [10/36]

◆ STATISTIC() [11/36]

◆ STATISTIC() [12/36]

◆ STATISTIC() [13/36]

◆ STATISTIC() [14/36]

◆ STATISTIC() [15/36]

◆ STATISTIC() [16/36]

◆ STATISTIC() [17/36]

◆ STATISTIC() [18/36]

◆ STATISTIC() [19/36]

◆ STATISTIC() [20/36]

◆ STATISTIC() [21/36]

◆ STATISTIC() [22/36]

◆ STATISTIC() [23/36]

◆ STATISTIC() [24/36]

◆ STATISTIC() [25/36]

◆ STATISTIC() [26/36]

◆ STATISTIC() [27/36]

◆ STATISTIC() [28/36]

◆ STATISTIC() [29/36]

◆ STATISTIC() [30/36]

◆ STATISTIC() [31/36]

◆ STATISTIC() [32/36]

◆ STATISTIC() [33/36]

◆ STATISTIC() [34/36]

◆ STATISTIC() [35/36]

◆ STATISTIC() [36/36]

◆ willNotOverflow()

Variable Documentation

◆ CanonicalizeICmpPredicatesToUnsigned

◆ false

◆ propagation