InstructionCombining.cpp File Reference

#include "llvm/Transforms/Scalar.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Pass.h"
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/PatternMatch.h"
#include "llvm/Support/Compiler.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
#include <climits>
#include <sstream>

Include dependency graph for InstructionCombining.cpp:

Go to the source code of this file.

Defines
#define	DEBUG_TYPE   "instcombine"
Functions
	STATISTIC (NumCombined,"Number of insts combined")
	STATISTIC (NumConstProp,"Number of constant folds")
	STATISTIC (NumDeadInst,"Number of dead inst eliminated")
	STATISTIC (NumDeadStore,"Number of dead stores eliminated")
	STATISTIC (NumSunkInst,"Number of instructions sunk")
static unsigned	getComplexity (Value *V)
static bool	isOnlyUse (Value *V)
static const Type *	getPromotedType (const Type *Ty)
static Value *	getBitCastOperand (Value *V)
static Instruction::CastOps	isEliminableCastPair (const CastInst *CI, unsigned opcode, const Type *DstTy, TargetData *TD)
static bool	ValueRequiresCast (Instruction::CastOps opcode, const Value *V, const Type *Ty, TargetData *TD)
static Value *	dyn_castNegVal (Value *V)
static Value *	dyn_castNotVal (Value *V)
static Value *	dyn_castFoldableMul (Value *V, ConstantInt *&CST)
static User *	dyn_castGetElementPtr (Value *V)
static unsigned	getOpcode (const Value *V)
static ConstantInt *	AddOne (ConstantInt *C)
	AddOne - Add one to a ConstantInt.
static ConstantInt *	SubOne (ConstantInt *C)
	SubOne - Subtract one from a ConstantInt.
static ConstantInt *	Add (ConstantInt *C1, ConstantInt *C2)
	Add - Add two ConstantInts together.
static ConstantInt *	And (ConstantInt *C1, ConstantInt *C2)
	And - Bitwise AND two ConstantInts together.
static ConstantInt *	Subtract (ConstantInt *C1, ConstantInt *C2)
	Subtract - Subtract one ConstantInt from another.
static ConstantInt *	Multiply (ConstantInt *C1, ConstantInt *C2)
	Multiply - Multiply two ConstantInts together.
static bool	MultiplyOverflows (ConstantInt *C1, ConstantInt *C2, bool sign)
static bool	ShrinkDemandedConstant (Instruction *I, unsigned OpNo, APInt Demanded)
static void	ComputeSignedMinMaxValuesFromKnownBits (const Type *Ty, const APInt &KnownZero, const APInt &KnownOne, APInt &Min, APInt &Max)
static void	ComputeUnsignedMinMaxValuesFromKnownBits (const Type *Ty, const APInt &KnownZero, const APInt &KnownOne, APInt &Min, APInt &Max)
template<typename Functor>
static Instruction *	AssociativeOpt (BinaryOperator &Root, const Functor &F)
static Value *	FoldOperationIntoSelectOperand (Instruction &I, Value *SO, InstCombiner *IC)
static Instruction *	FoldOpIntoSelect (Instruction &Op, SelectInst *SI, InstCombiner *IC)
static bool	isSignBitCheck (ICmpInst::Predicate pred, ConstantInt *RHS, bool &TrueIfSigned)
static bool	isOneBitSet (const ConstantInt *CI)
static bool	isHighOnes (const ConstantInt *CI)
static unsigned	getICmpCode (const ICmpInst *ICI)
static unsigned	getFCmpCode (FCmpInst::Predicate CC, bool &isOrdered)
static Value *	getICmpValue (bool sign, unsigned code, Value *LHS, Value *RHS)
static Value *	getFCmpValue (bool isordered, unsigned code, Value *LHS, Value *RHS)
static bool	PredicatesFoldable (ICmpInst::Predicate p1, ICmpInst::Predicate p2)
static bool	isRunOfOnes (ConstantInt *Val, uint32_t &MB, uint32_t &ME)
static bool	CollectBSwapParts (Value *V, int OverallLeftShift, uint32_t ByteMask, SmallVector< Value *, 8 > &ByteValues)
static Instruction *	MatchSelectFromAndOr (Value *A, Value *B, Value *C, Value *D)
static bool	AddWithOverflow (ConstantInt *&Result, ConstantInt *In1, ConstantInt *In2, bool IsSigned=false)
static bool	SubWithOverflow (ConstantInt *&Result, ConstantInt *In1, ConstantInt *In2, bool IsSigned=false)
static Value *	EmitGEPOffset (User *GEP, Instruction &I, InstCombiner &IC)
static Value *	EvaluateGEPOffsetExpression (User *GEP, Instruction &I, InstCombiner &IC)
static Value *	DecomposeSimpleLinearExpr (Value *Val, unsigned &Scale, int &Offset)
static const Type *	FindElementAtOffset (const Type *Ty, int64_t Offset, SmallVectorImpl< Value * > &NewIndices, const TargetData *TD)
static Constant *	FitsInFPType (ConstantFP *CFP, const fltSemantics &Sem)
static Value *	LookThroughFPExtensions (Value *V)
static unsigned	GetSelectFoldableOperands (Instruction *I)
static Constant *	GetSelectFoldableConstant (Instruction *I)
static unsigned	EnforceKnownAlignment (Value *V, unsigned Align, unsigned PrefAlign)
static bool	isSafeToEliminateVarargsCast (const CallSite CS, const CastInst *const CI, const TargetData *const TD, const int ix)
static bool	isSafeToSinkLoad (LoadInst *L)
static bool	DeadPHICycle (PHINode *PN, SmallPtrSet< PHINode *, 16 > &PotentiallyDeadPHIs)
static bool	PHIsEqualValue (PHINode *PN, Value *NonPhiInVal, SmallPtrSet< PHINode *, 16 > &ValueEqualPHIs)
static Value *	InsertCastToIntPtrTy (Value *V, const Type *DTy, Instruction *InsertPoint, InstCombiner *IC)
static Instruction *	InstCombineLoadCast (InstCombiner &IC, LoadInst &LI, const TargetData *TD)
	InstCombineLoadCast - Fold 'load (cast P)' -> cast (load P)' when possible.
static bool	isSafeToLoadUnconditionally (Value *V, Instruction *ScanFrom)
static Instruction *	InstCombineStoreToCast (InstCombiner &IC, StoreInst &SI)
static bool	equivalentAddressValues (Value *A, Value *B)
static bool	CheapToScalarize (Value *V, bool isConstant)
static std::vector< unsigned >	getShuffleMask (const ShuffleVectorInst *SVI)
static Value *	FindScalarElement (Value *V, unsigned EltNo)
static bool	CollectSingleShuffleElements (Value *V, Value *LHS, Value *RHS, std::vector< Constant * > &Mask)
static Value *	CollectShuffleElements (Value *V, std::vector< Constant * > &Mask, Value *&RHS)
static bool	TryToSinkInstruction (Instruction *I, BasicBlock *DestBlock)
static void	AddReachableCodeToWorklist (BasicBlock *BB, SmallPtrSet< BasicBlock *, 64 > &Visited, InstCombiner &IC, const TargetData *TD)
FunctionPass *	llvm::createInstructionCombiningPass ()
Variables
static RegisterPass< InstCombiner >	X ("instcombine","Combine redundant instructions")

---

Define Documentation

#define DEBUG_TYPE   "instcombine"

Definition at line 36 of file InstructionCombining.cpp.

---

Function Documentation

static ConstantInt* Add	(	ConstantInt *	C1,
		ConstantInt *	C2
	)			[static]

Add - Add two ConstantInts together.

Definition at line 634 of file InstructionCombining.cpp.

References llvm::ConstantInt::getValue().

Referenced by AddWithOverflow(), llvm::CannotBeNegativeZero(), llvm::ComputeMaskedBits(), llvm::ComputeNumSignBits(), llvm::ConstantFoldBinaryInstruction(), llvm::ConstantFoldGetElementPtr(), ConvertShiftToMul(), DecomposeSimpleLinearExpr(), DominatesMergePoint(), llvm::AsmPrinter::EmitConstantValueOnly(), llvm::ConstantExpr::get(), llvm::ConstantExpr::getAdd(), llvm::ScalarEvolution::getAddExpr(), llvm::LoopBase< BlockT >::getCanonicalInductionVariable(), llvm::ExecutionEngine::getConstantValue(), GetDecodedBinaryOpcode(), GetEncodedBinaryOpcode(), llvm::ScalarEvolution::getMulExpr(), llvm::Instruction::getOpcodeName(), GetSelectFoldableConstant(), GetSelectFoldableOperands(), getUnderlyingObjectFromInt(), llvm::IncrementCounterInBlock(), llvm::BinaryOperator::init(), llvm::MachOWriter::InitMem(), llvm::Instruction::isAssociative(), llvm::Instruction::isCommutative(), MightBeFoldableInst(), NegateValue(), llvm::FastISel::SelectOperator(), ShouldBreakUpSubtract(), SpeculativelyExecuteBB(), llvm::SCEVExpander::visitAddExpr(), llvm::SCEVExpander::visitAddRecExpr(), and llvm::Interpreter::visitBinaryOperator().

static ConstantInt* AddOne

(

ConstantInt *

C

)

[static]

AddOne - Add one to a ConstantInt.

Definition at line 624 of file InstructionCombining.cpp.

References llvm::ConstantInt::getValue(), and Val.

Referenced by llvm::ScalarEvolution::getAddExpr().

static void AddReachableCodeToWorklist	(	BasicBlock *	BB,
		SmallPtrSet< BasicBlock *, 64 > &	Visited,
		InstCombiner &	IC,
		const TargetData *	TD
	)			[static]

AddReachableCodeToWorklist - Walk the function in depth-first order, adding all reachable code to the worklist.

This has a couple of tricks to make the code faster and more powerful. In particular, we constant fold and DCE instructions as we go, to avoid adding them to the worklist (this significantly speeds up instcombine on code where many instructions are dead or constant). Additionally, if we find a branch whose condition is a known constant, we only visit the reachable successors.

Definition at line 12323 of file InstructionCombining.cpp.

References llvm::SmallVectorImpl< T >::back(), llvm::BasicBlock::begin(), llvm::ConstantFoldInstruction(), llvm::Intrinsic::dbg_stoppoint, DOUT, llvm::dyn_cast(), E, llvm::SmallVectorImpl< T >::empty(), llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), llvm::SwitchInst::getCaseValue(), llvm::SwitchInst::getCondition(), llvm::BranchInst::getCondition(), llvm::IntrinsicInst::getIntrinsicID(), llvm::TerminatorInst::getNumSuccessors(), llvm::SwitchInst::getNumSuccessors(), llvm::TerminatorInst::getSuccessor(), llvm::SwitchInst::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::SmallPtrSet< PtrType, SmallSize >::insert(), llvm::BranchInst::isConditional(), llvm::isInstructionTriviallyDead(), llvm::SmallVectorImpl< T >::pop_back(), llvm::SmallVectorImpl< T >::push_back(), llvm::Value::replaceAllUsesWith(), and Worklist.

static bool AddWithOverflow	(	ConstantInt *&	Result,
		ConstantInt *	In1,
		ConstantInt *	In2,
		bool	IsSigned = false
	)			[static]

AddWithOverflow - Compute Result = In1+In2, returning true if the result overflowed for this type.

Definition at line 5134 of file InstructionCombining.cpp.

References Add(), llvm::ConstantInt::getValue(), llvm::APInt::isNegative(), llvm::APInt::sgt(), llvm::APInt::slt(), and llvm::APInt::ult().

static ConstantInt* And	(	ConstantInt *	C1,
		ConstantInt *	C2
	)			[static]

And - Bitwise AND two ConstantInts together.

Definition at line 638 of file InstructionCombining.cpp.

References llvm::ConstantInt::getValue().

Referenced by CollectBSwapParts(), llvm::ComputeMaskedBits(), llvm::ComputeNumSignBits(), llvm::ConstantFoldBinaryInstruction(), DominatesMergePoint(), llvm::AsmPrinter::EmitConstantValueOnly(), FindLIVLoopCondition(), llvm::SelectionDAGLowering::FindMergedConditions(), FoldBranchToCommonDest(), GatherConstantSetNEs(), GatherValueComparisons(), llvm::ConstantExpr::get(), llvm::ConstantExpr::getAnd(), llvm::ExecutionEngine::getConstantValue(), GetDecodedBinaryOpcode(), GetEncodedBinaryOpcode(), llvm::Instruction::getOpcodeName(), GetSelectFoldableConstant(), GetSelectFoldableOperands(), llvm::BinaryOperator::init(), llvm::Instruction::isAssociative(), llvm::Instruction::isCommutative(), llvm::FastISel::SelectOperator(), SpeculativelyExecuteBB(), and llvm::Interpreter::visitBinaryOperator().

template<typename Functor>

static Instruction* AssociativeOpt	(	BinaryOperator &	Root,
		const Functor &	F
	)			[inline, static]

AssociativeOpt - Perform an optimization on an associative operator. This function is designed to check a chain of associative operators for a potential to apply a certain optimization. Since the optimization may be applicable if the expression was reassociated, this checks the chain, then reassociates the expression as necessary to expose the optimization opportunity. This makes use of a special Functor, which must define 'shouldApply' and 'apply' methods.

Definition at line 1749 of file InstructionCombining.cpp.

References llvm::dyn_cast(), llvm::Instruction::getOpcode(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Value::hasOneUse(), llvm::Instruction::moveBefore(), llvm::Value::replaceAllUsesWith(), and llvm::User::setOperand().

static bool CheapToScalarize	(	Value *	V,
		bool	isConstant
	)			[static]

CheapToScalarize - Return true if the value is cheaper to scalarize than it is to leave as a vector operation.

Definition at line 11729 of file InstructionCombining.cpp.

References llvm::dyn_cast(), llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Constant::getOperand(), llvm::Value::hasOneUse(), InsertElement, and Load.

static bool CollectBSwapParts	(	Value *	V,
		int	OverallLeftShift,
		uint32_t	ByteMask,
		SmallVector< Value *, 8 > &	ByteValues
	)			[static]

CollectBSwapParts - Analyze the specified subexpression and see if it is capable of providing pieces of a bswap. The subexpression provides pieces of a bswap if it is proven that each of the non-zero bytes in the output of the expression came from the corresponding "byte swapped" byte in some other value. For example, if the current subexpression is "(shl i32 %X, 24)" then we know that the expression deposits the low byte of X into the high byte of the bswap result and that all other bytes are zero. This expression is accepted, the high byte of ByteValues is set to X to indicate a correct match.

This function returns true if the match was unsuccessful and false if so. On entry to the function the "OverallLeftShift" is a signed integer value indicating the number of bytes that the subexpression is later shifted. For example, if the expression is later right shifted by 16 bits, the OverallLeftShift value would be -2 on entry. This is used to specify which byte of ByteValues is actually being set.

Similarly, ByteMask is a bitmask where a bit is clear if its corresponding byte is masked to zero by a user. For example, in (X & 255), X will be processed with a bytemask of 1. Because bytemask is 32-bits, this limits this function to working on up to 32-byte (256 bit) values. ByteMask is always in the local (OverallLeftShift) coordinate space.

Definition at line 4174 of file InstructionCombining.cpp.

References And(), llvm::CountTrailingZeros_32(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::Instruction::isLogicalShift(), llvm::isPowerOf2_32(), llvm::APIntOps::Or(), and llvm::SmallVectorImpl< T >::size().

static Value* CollectShuffleElements	(	Value *	V,
		std::vector< Constant * > &	Mask,
		Value *&	RHS
	)			[static]

CollectShuffleElements - We are building a shuffle of V, using RHS as the RHS of the shuffle instruction, if it is not null. Return a shuffle mask that computes V and the LHS value of the shuffle.

Definition at line 12032 of file InstructionCombining.cpp.

References CollectSingleShuffleElements(), llvm::User::getOperand(), and llvm::Value::getType().

static bool CollectSingleShuffleElements	(	Value *	V,
		Value *	LHS,
		Value *	RHS,
		std::vector< Constant * > &	Mask
	)			[static]

CollectSingleShuffleElements - If V is a shuffle of values that ONLY returns elements from either LHS or RHS, return the shuffle mask and true. Otherwise, return false.

Definition at line 11962 of file InstructionCombining.cpp.

References llvm::User::getOperand(), and llvm::Value::getType().

Referenced by CollectShuffleElements().

static void ComputeSignedMinMaxValuesFromKnownBits	(	const Type *	Ty,
		const APInt &	KnownZero,
		const APInt &	KnownOne,
		APInt &	Min,
		APInt &	Max
	)			[static]

Definition at line 701 of file InstructionCombining.cpp.

References llvm::APInt::clear(), llvm::APInt::getBitWidth(), and llvm::APInt::set().

static void ComputeUnsignedMinMaxValuesFromKnownBits	(	const Type *	Ty,
		const APInt &	KnownZero,
		const APInt &	KnownOne,
		APInt &	Min,
		APInt &	Max
	)			[static]

Definition at line 727 of file InstructionCombining.cpp.

References llvm::APInt::getBitWidth().

static bool DeadPHICycle	(	PHINode *	PN,
		SmallPtrSet< PHINode *, 16 > &	PotentiallyDeadPHIs
	)			[static]

DeadPHICycle - Return true if this PHI node is only used by a PHI node cycle that is dead.

Definition at line 10392 of file InstructionCombining.cpp.

References llvm::Value::hasOneUse(), llvm::SmallPtrSet< PtrType, SmallSize >::insert(), llvm::SmallPtrSetImpl::size(), llvm::Instruction::use_back(), and llvm::Value::use_empty().

static Value* DecomposeSimpleLinearExpr	(	Value *	Val,
		unsigned &	Scale,
		int &	Offset
	)			[static]

DecomposeSimpleLinearExpr - Analyze 'Val', seeing if it is a simple linear expression. If so, decompose it, returning some value X, such that Val is X*Scale+Offset.

Definition at line 7423 of file InstructionCombining.cpp.

References Add(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), and llvm::ConstantInt::getZExtValue().

static Value* dyn_castFoldableMul	(	Value *	V,
		ConstantInt *&	CST
	)			[inline, static]

Definition at line 584 of file InstructionCombining.cpp.

References llvm::ConstantInt::getLimitedValue(), llvm::CmpInst::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Value::hasOneUse(), llvm::Type::isInteger(), and llvm::APIntOps::shl().

static User* dyn_castGetElementPtr

(

Value *

V

)

[static]

dyn_castGetElementPtr - If this is a getelementptr instruction or constant expression, return it.

Definition at line 604 of file InstructionCombining.cpp.

static Value* dyn_castNegVal

(

Value *

V

)

[inline, static]

Definition at line 554 of file InstructionCombining.cpp.

References llvm::Value::getType(), and llvm::Type::isInteger().

static Value* dyn_castNotVal

(

Value *

V

)

[inline, static]

Definition at line 569 of file InstructionCombining.cpp.

static Value* EmitGEPOffset	(	User *	GEP,
		Instruction &	I,
		InstCombiner &	IC
	)			[static]

EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from the base pointer (without adding in the base pointer). Return the result as a signed integer of intptr size.

Definition at line 5165 of file InstructionCombining.cpp.

References llvm::gep_type_begin(), llvm::StructLayout::getElementOffset(), llvm::generic_gep_type_iterator< ItTy >::getIndexedType(), llvm::TargetData::getIntPtrType(), llvm::Value::getName(), llvm::TargetData::getPointerSizeInBits(), llvm::TargetData::getStructLayout(), llvm::Value::getType(), llvm::TargetData::getTypePaddedSize(), llvm::User::op_begin(), llvm::User::op_end(), Scale, and TD.

static unsigned EnforceKnownAlignment	(	Value *	V,
		unsigned	Align,
		unsigned	PrefAlign
	)			[static]

EnforceKnownAlignment - If the specified pointer points to an object that we control, modify the object's alignment to PrefAlign. This isn't often possible though. If alignment is important, a more reliable approach is to simply align all global variables and allocation instructions to their preferred alignment from the beginning.

Definition at line 9204 of file InstructionCombining.cpp.

References BitCast, llvm::dyn_cast(), getOpcode(), llvm::User::getOperand(), GV, llvm::GlobalValue::isDeclaration(), llvm::User::op_begin(), llvm::User::op_end(), llvm::AllocationInst::setAlignment(), and llvm::GlobalValue::setAlignment().

static bool equivalentAddressValues	(	Value *	A,
		Value *	B
	)			[static]

equivalentAddressValues - Test if A and B will obviously have the same value. This includes recognizing that t0 and t1 will have the same value in code like this: t0 = getelementptr , 0, 3 store i32 0, i32* t0 t1 = getelementptr , 0, 3 t2 = load i32* t1

Definition at line 11320 of file InstructionCombining.cpp.

static Value* EvaluateGEPOffsetExpression	(	User *	GEP,
		Instruction &	I,
		InstCombiner &	IC
	)			[static]

EvaluateGEPOffsetExpression - Return an value that can be used to compare of the *offset* implied by GEP to zero. For example, if we have &A[i], we want to return 'i' for "icmp ne i, 0". Note that, in general, indices can be complex, and scales are involved. The above expression would also be legal to codegen as "icmp ne (i*4), 0" (assuming A is a pointer to i32). This later form is less amenable to optimization though, and we are allowed to generate the first by knowing that pointer arithmetic doesn't overflow.

If we can't emit an optimized form for this expression, this returns null.

Definition at line 5248 of file InstructionCombining.cpp.

References llvm::dyn_cast(), llvm::gep_type_begin(), llvm::StructLayout::getElementOffset(), llvm::generic_gep_type_iterator< ItTy >::getIndexedType(), llvm::TargetData::getIntPtrType(), llvm::Value::getNameStart(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::TargetData::getPointerSizeInBits(), llvm::Type::getPrimitiveSizeInBits(), llvm::ConstantInt::getSExtValue(), llvm::TargetData::getStructLayout(), llvm::Value::getType(), llvm::TargetData::getTypePaddedSize(), llvm::ConstantInt::getZExtValue(), llvm::ConstantInt::isZero(), Offset, and TD.

static const Type* FindElementAtOffset	(	const Type *	Ty,
		int64_t	Offset,
		SmallVectorImpl< Value * > &	NewIndices,
		const TargetData *	TD
	)			[static]

FindElementAtOffset - Given a type and a constant offset, determine whether or not there is a sequence of GEP indices into the type that will land us at the specified offset. If so, fill them into NewIndices and return the resultant element type, otherwise return null.

Definition at line 7781 of file InstructionCombining.cpp.

References llvm::StructLayout::getElementContainingOffset(), llvm::StructLayout::getElementOffset(), llvm::TargetData::getIntPtrType(), llvm::StructLayout::getSizeInBytes(), llvm::TargetData::getStructLayout(), llvm::TargetData::getTypePaddedSize(), llvm::TargetData::getTypeSizeInBits(), llvm::Type::isSized(), and llvm::SmallVectorImpl< T >::push_back().

static Value* FindScalarElement	(	Value *	V,
		unsigned	EltNo
	)			[static]

FindScalarElement - Given a vector and an element number, see if the scalar value is already around as a register, for example if it were inserted then extracted from the vector.

Definition at line 11789 of file InstructionCombining.cpp.

References CP, llvm::SequentialType::getElementType(), llvm::VectorType::getNumElements(), llvm::Constant::getOperand(), getShuffleMask(), and llvm::Value::getType().

static Constant* FitsInFPType	(	ConstantFP *	CFP,
		const fltSemantics &	Sem
	)			[static]

FitsInFPType - Return a Constant* for the specified FP constant if it fits in the specified FP type without changing its value.

Definition at line 8394 of file InstructionCombining.cpp.

References llvm::APFloat::convert(), F, and llvm::ConstantFP::getValueAPF().

Referenced by LookThroughFPExtensions().

static Value* FoldOperationIntoSelectOperand	(	Instruction &	I,
		Value *	SO,
		InstCombiner *	IC
	)			[static]

Definition at line 1846 of file InstructionCombining.cpp.

References llvm::Value::getName(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), and std::swap().

Referenced by FoldOpIntoSelect().

static Instruction* FoldOpIntoSelect	(	Instruction &	Op,
		SelectInst *	SI,
		InstCombiner *	IC
	)			[static]

Definition at line 1882 of file InstructionCombining.cpp.

References FoldOperationIntoSelectOperand(), llvm::SelectInst::getCondition(), llvm::User::getOperand(), llvm::Value::getType(), and llvm::Value::hasOneUse().

static Value* getBitCastOperand

(

Value *

V

)

[static]

getBitCastOperand - If the specified operand is a CastInst, a constant expression bitcast, or a GetElementPtrInst with all zero indices, return the operand value, otherwise return null.

Definition at line 430 of file InstructionCombining.cpp.

References BitCast, llvm::dyn_cast(), E, llvm::User::getOperand(), llvm::ConstantInt::isZero(), and llvm::User::op_begin().

static unsigned getComplexity

(

Value *

V

)

[static]

Definition at line 401 of file InstructionCombining.cpp.

static unsigned getFCmpCode	(	FCmpInst::Predicate	CC,
		bool &	isOrdered
	)			[static]

getFCmpCode - Similar to getICmpCode but for FCmpInst. This encodes a fcmp predicate into a three bit mask. It also returns whether it is an ordered predicate by reference.

Definition at line 3229 of file InstructionCombining.cpp.

static Value* getFCmpValue	(	bool	isordered,
		unsigned	code,
		Value *	LHS,
		Value *	RHS
	)			[static]

getFCmpValue - This is the complement of getFCmpCode, which turns an opcode and two operands into either a FCmp instruction. isordered is passed in to determine which kind of predicate to use in the new fcmp instruction.

Definition at line 3291 of file InstructionCombining.cpp.

static unsigned getICmpCode

(

const ICmpInst *

ICI

)

[static]

getICmpCode - Encode a icmp predicate into a three bit mask. These bits are carefully arranged to allow folding of expressions such as:

(A < B) | (A > B) --> (A != B)

Note that this is only valid if the first and second predicates have the same sign. Is illegal to do: (A u< B) | (A s> B)

Three bits are used to represent the condition, as follows: 0 A > B 1 A == B 2 A < B

<=> Value Definition 000 0 Always false 001 1 A > B 010 2 A == B 011 3 A >= B 100 4 A < B 101 5 A != B 110 6 A <= B 111 7 Always true

Definition at line 3206 of file InstructionCombining.cpp.

References llvm::CmpInst::getPredicate().

static Value* getICmpValue	(	bool	sign,
		unsigned	code,
		Value *	LHS,
		Value *	RHS
	)			[static]

getICmpValue - This is the complement of getICmpCode, which turns an opcode and two operands into either a constant true or false, or a brand new ICmp instruction. The sign is passed in to determine which kind of predicate to use in the new icmp instruction.

Definition at line 3258 of file InstructionCombining.cpp.

static unsigned getOpcode

(

const Value *

V

)

[static]

getOpcode - If this is an Instruction or a ConstantExpr, return the opcode value. Otherwise return UserOp1.

Definition at line 614 of file InstructionCombining.cpp.

References llvm::CmpInst::getOpcode(), and UserOp1.

static const Type* getPromotedType

(

const Type *

Ty

)

[static]

Definition at line 419 of file InstructionCombining.cpp.

static Constant* GetSelectFoldableConstant

(

Instruction *

I

)

[static]

GetSelectFoldableConstant - For the same transformation as the previous function, return the identity constant that goes into the select.

Definition at line 8701 of file InstructionCombining.cpp.

References Add(), And(), llvm::Instruction::getOpcode(), llvm::Value::getType(), LShr, llvm::APIntOps::Or(), and llvm::APIntOps::Xor().

static unsigned GetSelectFoldableOperands

(

Instruction *

I

)

[static]

GetSelectFoldableOperands - We want to turn code that looks like this: C = or A, B D = select cond, C, A into: C = select cond, B, 0 D = or A, C

Assuming that the specified instruction is an operand to the select, return a bitmask indicating which operands of this instruction are foldable if they equal the other incoming value of the select.

Definition at line 8681 of file InstructionCombining.cpp.

References Add(), And(), llvm::Instruction::getOpcode(), LShr, llvm::APIntOps::Or(), and llvm::APIntOps::Xor().

static std::vector<unsigned> getShuffleMask

(

const ShuffleVectorInst *

SVI

)

[static]

Read and decode a shufflevector mask.

It turns undef elements into values that are larger than the number of elements in the input.

Definition at line 11769 of file InstructionCombining.cpp.

References CP, llvm::VectorType::getNumElements(), llvm::User::getOperand(), llvm::ShuffleVectorInst::getType(), llvm::User::op_begin(), and llvm::User::op_end().

Referenced by FindScalarElement().

static Value* InsertCastToIntPtrTy	(	Value *	V,
		const Type *	DTy,
		Instruction *	InsertPoint,
		InstCombiner *	IC
	)			[static]

Definition at line 10522 of file InstructionCombining.cpp.

References BitCast, llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), and llvm::Attribute::SExt.

static Instruction* InstCombineLoadCast	(	InstCombiner &	IC,
		LoadInst &	LI,
		const TargetData *	TD
	)			[static]

InstCombineLoadCast - Fold 'load (cast P)' -> cast (load P)' when possible.

Definition at line 10967 of file InstructionCombining.cpp.

References llvm::GetConstantStringInfo(), llvm::Value::getName(), llvm::Constant::getOperand(), llvm::User::getOperand(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::Type::isInteger(), llvm::TargetData::isLittleEndian(), and llvm::LoadInst::isVolatile().

static Instruction* InstCombineStoreToCast	(	InstCombiner &	IC,
		StoreInst &	SI
	)			[static]

InstCombineStoreToCast - Fold store V, (cast P) -> store (cast V), P when possible. This makes it generally easy to do alias analysis and/or SROA/mem2reg of the memory object.

NewGEPIndices - If SrcPTy is an aggregate type, we can emit a "noop gep" to its first element. This allows us to handle things like: store i32 xxx, (bitcast {foo*, float}* P to i32*) on 32-bit hosts.

Definition at line 11220 of file InstructionCombining.cpp.

References llvm::SmallVectorImpl< T >::begin(), BitCast, llvm::dyn_cast(), llvm::SmallVectorImpl< T >::empty(), llvm::SmallVectorImpl< T >::end(), llvm::PointerType::getAddressSpace(), llvm::SequentialType::getElementType(), llvm::Value::getName(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Type::isInteger(), PtrToInt, llvm::SmallVectorImpl< T >::push_back(), and llvm::SmallVectorImpl< T >::size().

static Instruction::CastOps isEliminableCastPair	(	const CastInst *	CI,
		unsigned	opcode,
		const Type *	DstTy,
		TargetData *	TD
	)			[static]

This function is a wrapper around CastInst::isEliminableCastPair. It simply extracts arguments and returns what that function returns.

Parameters:

CI	The first cast instruction
opcode	The opcode of the second cast instruction
DstTy	The target type for the second cast instruction
TD	The target data for pointer size

Definition at line 461 of file InstructionCombining.cpp.

References llvm::TargetData::getIntPtrType(), llvm::CastInst::getOpcode(), llvm::User::getOperand(), and llvm::Value::getType().

Referenced by foldConstantCastPair(), and ValueRequiresCast().

static bool isHighOnes

(

const ConstantInt *

CI

)

[static]

Definition at line 3179 of file InstructionCombining.cpp.

References llvm::ConstantInt::getValue().

static bool isOneBitSet

(

const ConstantInt *

CI

)

[static]

Definition at line 3173 of file InstructionCombining.cpp.

References llvm::ConstantInt::getValue(), and llvm::APInt::isPowerOf2().

static bool isOnlyUse

(

Value *

V

)

[static]

Definition at line 413 of file InstructionCombining.cpp.

References llvm::Value::hasOneUse().

static bool isRunOfOnes	(	ConstantInt *	Val,
		uint32_t &	MB,
		uint32_t &	ME
	)			[static]

Definition at line 3575 of file InstructionCombining.cpp.

References llvm::APInt::getActiveBits(), llvm::IntegerType::getBitWidth(), llvm::ConstantInt::getType(), llvm::ConstantInt::getValue(), and llvm::APIntOps::isShiftedMask().

static bool isSafeToEliminateVarargsCast	(	const CallSite	CS,
		const CastInst *const	CI,
		const TargetData *const	TD,
		const int	ix
	)			[static]

isSafeToEliminateVarargsCast - If this cast does not affect the value passed through the varargs area, we can eliminate the use of the cast.

Definition at line 9608 of file InstructionCombining.cpp.

References llvm::Attribute::ByVal, llvm::User::getOperand(), llvm::Value::getType(), llvm::TargetData::getTypePaddedSize(), llvm::CastInst::isLosslessCast(), llvm::Type::isSized(), and llvm::CallSite::paramHasAttr().

static bool isSafeToLoadUnconditionally	(	Value *	V,
		Instruction *	ScanFrom
	)			[static]

isSafeToLoadUnconditionally - Return true if we know that executing a load from this value cannot trap. If it is not obviously safe to load from the specified pointer, we do a quick local scan of the basic block containing ScanFrom, to determine if the address is already accessed.

Definition at line 11049 of file InstructionCombining.cpp.

References llvm::BasicBlock::begin(), E, llvm::User::getOperand(), llvm::Instruction::getParent(), GV, llvm::GlobalValue::hasExternalWeakLinkage(), and LI.

static bool isSafeToSinkLoad

(

LoadInst *

L

)

[static]

isSafeToSinkLoad - Return true if we know that it is safe sink the load out of the block that defines it. This means that it must be obvious the value of the load is not changed from the point of the load to the end of the block it is in.

Finally, it is safe, but not profitable, to sink a load targetting a non-address-taken alloca. Doing so will cause us to not promote the alloca to a register.

Definition at line 10240 of file InstructionCombining.cpp.

References E, llvm::BasicBlock::end(), llvm::User::getOperand(), and llvm::Instruction::getParent().

static bool isSignBitCheck	(	ICmpInst::Predicate	pred,
		ConstantInt *	RHS,
		bool &	TrueIfSigned
	)			[static]

isSignBitCheck - Given an exploded icmp instruction, return true if the comparison only checks the sign bit. If it only checks the sign bit, set TrueIfSigned if the result of the comparison is true when the input value is signed.

Definition at line 2531 of file InstructionCombining.cpp.

References llvm::Type::getPrimitiveSizeInBits(), llvm::ConstantInt::getType(), llvm::ConstantInt::getValue(), llvm::ConstantInt::isAllOnesValue(), llvm::APInt::isSignBit(), and llvm::ConstantInt::isZero().

static Value* LookThroughFPExtensions

(

Value *

V

)

[static]

LookThroughFPExtensions - If this is an fp extension instruction, look through it until we get the source value.

Definition at line 8405 of file InstructionCombining.cpp.

References FitsInFPType().

static Instruction* MatchSelectFromAndOr	(	Value *	A,
		Value *	B,
		Value *	C,
		Value *	D
	)			[static]

MatchSelectFromAndOr - We have an expression of the form (A&C)|(B&D). Check If A is (cond?-1:0) and either B or D is ~(cond?-1,0) or (cond?0,-1), then we can simplify this expression to "cond ? C : D or B".

Definition at line 4314 of file InstructionCombining.cpp.

References llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

static ConstantInt* Multiply	(	ConstantInt *	C1,
		ConstantInt *	C2
	)			[static]

Multiply - Multiply two ConstantInts together.

Definition at line 646 of file InstructionCombining.cpp.

References llvm::ConstantInt::getValue().

static bool MultiplyOverflows	(	ConstantInt *	C1,
		ConstantInt *	C2,
		bool	sign
	)			[static]

MultiplyOverflows - True if the multiply can not be expressed in an int this size.

Definition at line 651 of file InstructionCombining.cpp.

References llvm::ConstantInt::getBitWidth(), llvm::ConstantInt::getValue(), llvm::APInt::sext(), llvm::APInt::sgt(), llvm::APInt::slt(), llvm::APInt::ugt(), and llvm::APInt::zext().

static bool PHIsEqualValue	(	PHINode *	PN,
		Value *	NonPhiInVal,
		SmallPtrSet< PHINode *, 16 > &	ValueEqualPHIs
	)			[static]

PHIsEqualValue - Return true if this phi node is always equal to NonPhiInVal. This happens with mutually cyclic phi nodes like: z = some value; x = phi (y, z); y = phi (x, z)

Definition at line 10414 of file InstructionCombining.cpp.

References llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::SmallPtrSet< PtrType, SmallSize >::insert(), and llvm::SmallPtrSetImpl::size().

static bool PredicatesFoldable	(	ICmpInst::Predicate	p1,
		ICmpInst::Predicate	p2
	)			[static]

PredicatesFoldable - Return true if both predicates match sign or if at least one of them is an equality comparison (which is signless).

Definition at line 3336 of file InstructionCombining.cpp.

static bool ShrinkDemandedConstant	(	Instruction *	I,
		unsigned	OpNo,
		APInt	Demanded
	)			[static]

ShrinkDemandedConstant - Check to see if the specified operand of the specified instruction is a constant integer. If so, check to see if there are any bits set in the constant that are not demanded. If so, shrink the constant and return true.

Definition at line 677 of file InstructionCombining.cpp.

References llvm::dyn_cast(), llvm::APInt::getBitWidth(), llvm::User::getOperand(), llvm::ConstantInt::getValue(), llvm::User::setOperand(), and llvm::APInt::zextOrTrunc().

STATISTIC	(	NumSunkInst	,
		"Number of instructions sunk"
	)

STATISTIC	(	NumDeadStore	,
		"Number of dead stores eliminated"
	)

STATISTIC	(	NumDeadInst	,
		"Number of dead inst eliminated"
	)

STATISTIC	(	NumConstProp	,
		"Number of constant folds"
	)

STATISTIC	(	NumCombined	,
		"Number of insts combined"
	)

static ConstantInt* SubOne

(

ConstantInt *

C

)

[static]

SubOne - Subtract one from a ConstantInt.

Definition at line 629 of file InstructionCombining.cpp.

References llvm::ConstantInt::getValue(), and Val.

static ConstantInt* Subtract	(	ConstantInt *	C1,
		ConstantInt *	C2
	)			[static]

Subtract - Subtract one ConstantInt from another.

Definition at line 642 of file InstructionCombining.cpp.

References llvm::ConstantInt::getValue().

Referenced by SubWithOverflow().

static bool SubWithOverflow	(	ConstantInt *&	Result,
		ConstantInt *	In1,
		ConstantInt *	In2,
		bool	IsSigned = false
	)			[static]

SubWithOverflow - Compute Result = In1-In2, returning true if the result overflowed for this type.

Definition at line 5149 of file InstructionCombining.cpp.

References llvm::ConstantInt::getValue(), llvm::APInt::isNegative(), llvm::APInt::sgt(), llvm::APInt::slt(), Subtract(), and llvm::APInt::ugt().

static bool TryToSinkInstruction	(	Instruction *	I,
		BasicBlock *	DestBlock
	)			[static]

TryToSinkInstruction - Try to move the specified instruction from its current block into the beginning of DestBlock, which can only happen if it's safe to move the instruction past all of the instructions between it and the end of its block.

Definition at line 12285 of file InstructionCombining.cpp.

References E, llvm::BasicBlock::end(), llvm::Function::getEntryBlock(), llvm::BasicBlock::getFirstNonPHI(), llvm::BasicBlock::getParent(), llvm::Instruction::getParent(), llvm::Value::hasOneUse(), InsertPos, llvm::Instruction::mayReadFromMemory(), llvm::Instruction::mayWriteToMemory(), and llvm::Instruction::moveBefore().

static bool ValueRequiresCast	(	Instruction::CastOps	opcode,
		const Value *	V,
		const Type *	Ty,
		TargetData *	TD
	)			[static]

ValueRequiresCast - Return true if the cast from "V to Ty" actually results in any code being generated. It does not require codegen if V is simple enough or if the cast can be folded into other casts.

Definition at line 483 of file InstructionCombining.cpp.

References llvm::Value::getType(), and isEliminableCastPair().

---

Variable Documentation

Constant* C2

Definition at line 1832 of file InstructionCombining.cpp.

Referenced by llvm::ConstantFoldGetElementPtr(), evaluateFCmpRelation(), evaluateICmpRelation(), EvalVectorOp(), llvm::SelectionDAG::FoldConstantArithmetic(), llvm::SelectionDAG::FoldSetCC(), IndexOperandsEqual(), llvm::ConstantExpr::replaceUsesOfWithOnConstant(), and ValuesOverlap().

InstCombiner& IC

Definition at line 3345 of file InstructionCombining.cpp.

Referenced by llvm::IRBuilder< preserveNames, T >::CreateExtractElement(), llvm::IRBuilder< preserveNames, T >::CreateGEP(), llvm::IRBuilder< preserveNames, T >::CreateInsertElement(), llvm::SelectionDAGLowering::EmitBranchForMergedCondition(), llvm::BasicInlinerImpl::inlineFunctions(), llvm::CmpInst::isCommutative(), llvm::CmpInst::isEquality(), IsOnlyUsedInZeroEqualityComparison(), and llvm::CmpInst::swapOperands().

char ID [static]

Definition at line 82 of file InstructionCombining.cpp.

Value* LHS

Definition at line 3346 of file InstructionCombining.cpp.

Referenced by llvm::APIntOps::add(), combineSelectAndUse(), FindLIVLoopCondition(), GatherConstantSetEQs(), GatherConstantSetNEs(), llvm::ExecutionEngine::getConstantValue(), llvm::SCEVUDivExpr::getLHS(), llvm::SCEVUDivExpr::getType(), llvm::SCEVUDivExpr::hasComputableLoopEvolution(), llvm::BinaryOperator::init(), llvm::SCEVUDivExpr::isLoopInvariant(), llvm::PIC16TargetLowering::LowerBR_CC(), LowerBR_CC(), LowerCTPOP(), llvm::PIC16TargetLowering::LowerSELECT_CC(), LowerSELECT_CC(), llvm::PatternMatch::m_FCmp(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Shift(), llvm::SCEVUDivExpr::print(), llvm::SCEVUDivExpr::replaceSymbolicValuesWithConcrete(), llvm::SCEVExpander::visitSMaxExpr(), llvm::SCEVExpander::visitUDivExpr(), and llvm::SCEVExpander::visitUMaxExpr().

bool MustPreserveLCSSA

Definition at line 80 of file InstructionCombining.cpp.

ICmpInst::Predicate pred

Definition at line 3347 of file InstructionCombining.cpp.

Referenced by llvm::CloneAndPruneFunctionInto(), llvm::iplist< llvm::Instruction >::erase_if(), evaluateICmpRelation(), getPredicateText(), llvm::iplist< llvm::Instruction >::merge(), and llvm::iplist< llvm::Instruction >::unique().

Value* RHS

Definition at line 1820 of file InstructionCombining.cpp.

Referenced by llvm::APIntOps::add(), combineSelectAndUse(), FindLIVLoopCondition(), GatherConstantSetEQs(), GatherConstantSetNEs(), llvm::ExecutionEngine::getConstantValue(), getIndexedAddressParts(), llvm::SCEVUDivExpr::getRHS(), llvm::SCEVUDivExpr::hasComputableLoopEvolution(), llvm::BinaryOperator::init(), isIdentityMask(), llvm::SCEVUDivExpr::isLoopInvariant(), LinkTypes(), llvm::PIC16TargetLowering::LowerBR_CC(), LowerBR_CC(), LowerCTPOP(), llvm::PIC16TargetLowering::LowerSELECT_CC(), LowerSELECT_CC(), llvm::PatternMatch::m_FCmp(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Shift(), llvm::SCEVUDivExpr::print(), llvm::SCEVUDivExpr::replaceSymbolicValuesWithConcrete(), llvm::SCEVExpander::visitSMaxExpr(), llvm::SCEVExpander::visitUDivExpr(), and llvm::SCEVExpander::visitUMaxExpr().

TargetData* TD

Definition at line 79 of file InstructionCombining.cpp.

SmallVector<Instruction*, 256> Worklist

Definition at line 77 of file InstructionCombining.cpp.

Referenced by AddReachableCodeToWorklist(), llvm::DFSPass(), MarkAliveBlocks(), and llvm::PointerMayBeCaptured().

DenseMap<Instruction*, unsigned> WorklistMap

Definition at line 78 of file InstructionCombining.cpp.

RegisterPass<InstCombiner> X("instcombine","Combine redundant instructions") [static]