#include "InstCombineInternal.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/AlignOf.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"
#include <cassert>
#include <utility>

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.

Macros
#define	DEBUG_TYPE "instcombine"

Functions
static Value *	checkForNegativeOperand (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
static Instruction *	foldNoWrapAdd (BinaryOperator &Add, InstCombiner::BuilderTy &Builder)
	Wrapping flags may allow combining constants separated by an extend.
template<bool FP, typename Mul2Rhs>
static bool	matchesSquareSum (BinaryOperator &I, Mul2Rhs M2Rhs, Value &A, Value &B)
static bool	MatchMul (Value E, Value &Op, APInt &C)
static bool	MatchRem (Value E, Value &Op, APInt &C, bool &IsSigned)
static bool	MatchDiv (Value E, Value &Op, APInt &C, bool IsSigned)
static bool	MulWillOverflow (APInt &C0, APInt &C1, bool IsSigned)
static Instruction *	canonicalizeLowbitMask (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
	Fold (1 << NBits) - 1 Into: ~(-(1 << NBits)) Because a 'not' is better for bit-tracking analysis and other transforms than an 'add'.
static Instruction *	foldToUnsignedSaturatedAdd (BinaryOperator &I)
static Instruction *	combineAddSubWithShlAddSub (InstCombiner::BuilderTy &Builder, const BinaryOperator &I)
static Instruction *	foldAddToAshr (BinaryOperator &Add)
	Try to reduce signed division by power-of-2 to an arithmetic shift right.
static Instruction *	factorizeMathWithShlOps (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
	This is a specialization of a more general transform from foldUsingDistributiveLaws.
static Instruction *	foldBoxMultiply (BinaryOperator &I)
	Reduce a sequence of masked half-width multiplies to a single multiply.
static bool	checkDivCeilNUW (Value X, Value Y, const SimplifyQuery &SQ)
	Return true if X + (Y-1) is provably non-wrapping in X's type.
static Instruction *	factorizeLerp (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
	Eliminate an op from a linear interpolation (lerp) pattern.
static Instruction *	factorizeFAddFSub (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
	Factor a common operand out of fadd/fsub of fmul/fdiv.
static Instruction *	foldSubOfMinMax (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
static Instruction *	foldSubNUWOfMaskAndZExt (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
	sub nuw (and X, LowMask), (zext Y) --> zext (sub nuw (trunc X), Y) sub nuw (zext Y), (and X, LowMask) --> zext (sub nuw Y, (trunc X)) where LowMask has exactly as many low bits set as Y's width, so the 'and' is zext(trunc X) and the wide nuw implies the narrow sub does not wrap.
static Instruction *	foldFNegIntoConstant (Instruction &I, const DataLayout &DL)
	This eliminates floating-point negation in either 'fneg(X)' or 'fsub(-0.0, X)' form by combining into a constant operand.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "instcombine"

Definition at line 40 of file InstCombineAddSub.cpp.

Function Documentation

◆ canonicalizeLowbitMask()

Instruction * canonicalizeLowbitMask	(	BinaryOperator &	I,
		InstCombiner::BuilderTy &	Builder )

static

Fold (1 << NBits) - 1 Into: ~(-(1 << NBits)) Because a 'not' is better for bit-tracking analysis and other transforms than an 'add'.

The new shl is always nsw, and is nuw if old and was.

Definition at line 1232 of file InstCombineAddSub.cpp.

References llvm::BinaryOperator::CreateNot(), llvm::dyn_cast(), llvm::Constant::getAllOnesValue(), llvm::Value::getType(), I, llvm::PatternMatch::m_Add(), llvm::MIPatternMatch::m_AllOnes(), llvm::PatternMatch::m_One(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

Referenced by llvm::InstCombinerImpl::visitAdd().

◆ checkDivCeilNUW()

bool checkDivCeilNUW	(	Value *	X,
		Value *	Y,
		const SimplifyQuery &	SQ )

static

Return true if X + (Y-1) is provably non-wrapping in X's type.

Definition at line 1550 of file InstCombineAddSub.cpp.

References llvm::computeConstantRange(), llvm::ConstantRange::getUnsignedMax(), llvm::ConstantRange::getUnsignedMin(), llvm::APInt::isZero(), llvm::APInt::ugt(), X, and Y.

Referenced by llvm::InstCombinerImpl::foldDivCeil().

◆ checkForNegativeOperand()

Value * checkForNegativeOperand	(	BinaryOperator &	I,
		InstCombiner::BuilderTy &	Builder )

static

Definition at line 757 of file InstCombineAddSub.cpp.

References C1, I, LHS, llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Xor(), llvm::PatternMatch::match(), RHS, std::swap(), X, and Y.

Referenced by llvm::InstCombinerImpl::visitAdd().

◆ combineAddSubWithShlAddSub()

Instruction * combineAddSubWithShlAddSub	(	InstCombiner::BuilderTy &	Builder,
		const BinaryOperator &	I )

static

Definition at line 1276 of file InstCombineAddSub.cpp.

References A(), B(), I, llvm::PatternMatch::m_c_Add(), llvm::MIPatternMatch::m_Neg(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

Referenced by llvm::InstCombinerImpl::visitAdd().

◆ factorizeFAddFSub()

Instruction * factorizeFAddFSub	(	BinaryOperator &	I,
		InstCombiner::BuilderTy &	Builder )

static

Factor a common operand out of fadd/fsub of fmul/fdiv.

Definition at line 2073 of file InstCombineAddSub.cpp.

References assert(), C(), llvm::BinaryOperator::CreateFDivFMF(), llvm::BinaryOperator::CreateFMulFMF(), factorizeLerp(), llvm::Value::hasOneUse(), I, llvm::PatternMatch::m_APFloat(), llvm::PatternMatch::m_c_FMul(), llvm::PatternMatch::m_FDiv(), llvm::PatternMatch::m_FMul(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), X, and Y.

Referenced by llvm::InstCombinerImpl::visitFAdd(), and llvm::InstCombinerImpl::visitFSub().

◆ factorizeLerp()

Instruction * factorizeLerp	(	BinaryOperator &	I,
		InstCombiner::BuilderTy &	Builder )

static

Eliminate an op from a linear interpolation (lerp) pattern.

Definition at line 2057 of file InstCombineAddSub.cpp.

References llvm::BinaryOperator::CreateFAddFMF(), I, llvm::PatternMatch::m_c_FAdd(), llvm::PatternMatch::m_c_FMul(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_FPOne(), llvm::PatternMatch::m_FSub(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), X, and Y.

Referenced by factorizeFAddFSub().

◆ factorizeMathWithShlOps()

Instruction * factorizeMathWithShlOps	(	BinaryOperator &	I,
		InstCombiner::BuilderTy &	Builder )

static

This is a specialization of a more general transform from foldUsingDistributiveLaws.

If that code can be made to work optimally for multi-use cases or propagating nsw/nuw, then we would not need this.

Definition at line 1474 of file InstCombineAddSub.cpp.

References assert(), llvm::dyn_cast(), I, llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), X, and Y.

Referenced by llvm::InstCombinerImpl::visitAdd(), and llvm::InstCombinerImpl::visitSub().

◆ foldAddToAshr()

Instruction * foldAddToAshr ( BinaryOperator & Add )

static

Try to reduce signed division by power-of-2 to an arithmetic shift right.

Definition at line 1289 of file InstCombineAddSub.cpp.

References llvm::Add, llvm::APInt::exactLogBase2(), llvm::APInt::getSignedMinValue(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_UGT, llvm::APInt::isNegative(), llvm::APInt::isSignMask(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Power2(), llvm::PatternMatch::m_SDiv(), llvm::PatternMatch::m_SExt(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::SMin, and X.

Referenced by llvm::InstCombinerImpl::visitAdd().

◆ foldBoxMultiply()

Instruction * foldBoxMultiply ( BinaryOperator & I )

static

Reduce a sequence of masked half-width multiplies to a single multiply.

((XLow * YHigh) + (YLow * XHigh)) << HalfBits) + (XLow * YLow) --> X * Y

Definition at line 1510 of file InstCombineAddSub.cpp.

References llvm::BitWidth, llvm::APInt::getMaxValue(), I, llvm::PatternMatch::m_And(), llvm::PatternMatch::m_c_Add(), llvm::PatternMatch::m_c_Mul(), llvm::PatternMatchHelpers::m_CombineOr(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_Mul(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), X, and Y.

Referenced by llvm::InstCombinerImpl::visitAdd().

◆ foldFNegIntoConstant()

Instruction * foldFNegIntoConstant	(	Instruction &	I,
		const DataLayout &	DL )

static

This eliminates floating-point negation in either 'fneg(X)' or 'fsub(-0.0, X)' form by combining into a constant operand.

Definition at line 3144 of file InstCombineAddSub.cpp.

Referenced by llvm::InstCombinerImpl::visitFNeg(), and llvm::InstCombinerImpl::visitFSub().

◆ foldNoWrapAdd()

Instruction * foldNoWrapAdd	(	BinaryOperator &	Add,
		InstCombiner::BuilderTy &	Builder )

static

Wrapping flags may allow combining constants separated by an extend.

Definition at line 814 of file InstCombineAddSub.cpp.

References llvm::Add, C1, llvm::APInt::getBitWidth(), llvm::Value::hasOneUse(), llvm::APInt::isZero(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_NSWAddLike(), llvm::PatternMatch::m_NUWAddLike(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_SExtLike(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::PatternMatch::match(), llvm::APInt::sext(), and X.

Referenced by llvm::InstCombinerImpl::visitAdd().

◆ foldSubNUWOfMaskAndZExt()

Instruction * foldSubNUWOfMaskAndZExt	(	BinaryOperator &	I,
		InstCombiner::BuilderTy &	Builder )

static

sub nuw (and X, LowMask), (zext Y) --> zext (sub nuw (trunc X), Y) sub nuw (zext Y), (and X, LowMask) --> zext (sub nuw Y, (trunc X)) where LowMask has exactly as many low bits set as Y's width, so the 'and' is zext(trunc X) and the wide nuw implies the narrow sub does not wrap.

Definition at line 2421 of file InstCombineAddSub.cpp.

References I, llvm::PatternMatch::m_And(), llvm::PatternMatch::m_LowBitMask(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::PatternMatch::match(), X, and Y.

Referenced by llvm::InstCombinerImpl::visitSub().