#include "InstCombineInternal.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CmpInstAnalysis.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/OverflowInstAnalysis.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/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/Intrinsics.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"
#include <cassert>
#include <utility>

Include dependency graph for InstCombineSelect.cpp:

Macros
#define	DEBUG_TYPE "instcombine"

Functions
static Value *	createMinMax (InstCombiner::BuilderTy &Builder, SelectPatternFlavor SPF, Value A, Value B)

static Instruction *	foldSelectBinOpIdentity (SelectInst &Sel, const TargetLibraryInfo &TLI, InstCombinerImpl &IC)
	Replace a select operand based on an equality comparison with the identity constant of a binop. More...

static Value *	foldSelectICmpAnd (SelectInst &Sel, ICmpInst *Cmp, InstCombiner::BuilderTy &Builder)
	This folds: select (icmp eq (and X, C1)), TC, FC iff C1 is a power 2 and the difference between TC and FC is a power-of-2. More...

static unsigned	getSelectFoldableOperands (BinaryOperator *I)
	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. More...

static bool	isSelect01 (const APInt &C1I, const APInt &C2I)

static Instruction *	foldSelectICmpAndAnd (Type SelType, const ICmpInst Cmp, Value TVal, Value FVal, InstCombiner::BuilderTy &Builder)
	We want to turn: (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1) into: zext (icmp ne i32 (and X, (or Y, (shl 1, Z))), 0) Note: Z may be 0 if lshr is missing. More...

static Value *	foldSelectICmpLshrAshr (const ICmpInst IC, Value TrueVal, Value *FalseVal, InstCombiner::BuilderTy &Builder)
	We want to turn: (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1 (select (icmp slt x, C), ashr (X, Y), lshr (X, Y)); iff C s>= 0 into: ashr (X, Y) More...

static Value *	foldSelectICmpAndOr (const ICmpInst IC, Value TrueVal, Value *FalseVal, InstCombiner::BuilderTy &Builder)
	We want to turn: (select (icmp eq (and X, C1), 0), Y, (or Y, C2)) into: (or (shl (and X, C1), C3), Y) iff: C1 and C2 are both powers of 2 where: C3 = Log(C2) - Log(C1) More...

static Instruction *	foldSetClearBits (SelectInst &Sel, InstCombiner::BuilderTy &Builder)
	Canonicalize a set or clear of a masked set of constant bits to select-of-constants form. More...

static Instruction *	foldSelectZeroOrMul (SelectInst &SI, InstCombinerImpl &IC)

static Value *	canonicalizeSaturatedSubtract (const ICmpInst ICI, const Value TrueVal, const Value *FalseVal, InstCombiner::BuilderTy &Builder)
	Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b). More...

static Value *	canonicalizeSaturatedAdd (ICmpInst Cmp, Value TVal, Value *FVal, InstCombiner::BuilderTy &Builder)

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "instcombine"

Definition at line 49 of file InstCombineSelect.cpp.

Function Documentation

◆ canonicalizeSaturatedAdd()

static Value* canonicalizeSaturatedAdd	(	ICmpInst *	Cmp,
		Value *	TVal,
		Value *	FVal,
		InstCombiner::BuilderTy &	Builder
	)

static

◆ canonicalizeSaturatedSubtract()

static Value* canonicalizeSaturatedSubtract	(	const ICmpInst *	ICI,
		const Value *	TrueVal,
		const Value *	FalseVal,
		InstCombiner::BuilderTy &	Builder
	)

static

Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b).

There are 8 commuted/swapped variants of this pattern. TODO: Also support a - UMIN(a,b) patterns.

Definition at line 781 of file InstCombineSelect.cpp.

References assert(), B, Builder, llvm::tgtok::FalseVal, llvm::CmpInst::getInversePredicate(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::CmpInst::getSwappedPredicate(), llvm::Value::hasOneUse(), llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::CmpInst::isUnsigned(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), std::swap(), and llvm::tgtok::TrueVal.

◆ createMinMax()

static Value* createMinMax	(	InstCombiner::BuilderTy &	Builder,
		SelectPatternFlavor	SPF,
		Value *	A,
		Value *	B
	)

static

Definition at line 51 of file InstCombineSelect.cpp.

References assert(), B, Builder, llvm::getMinMaxPred(), and llvm::CmpInst::isIntPredicate().

◆ foldSelectBinOpIdentity()

static Instruction* foldSelectBinOpIdentity	(	SelectInst &	Sel,
		const TargetLibraryInfo &	TLI,
		InstCombinerImpl &	IC
	)

static

Replace a select operand based on an equality comparison with the identity constant of a binop.

Definition at line 60 of file InstCombineSelect.cpp.

References llvm::CannotBeNegativeZero(), llvm::CmpInst::FCMP_OEQ, llvm::CmpInst::FCMP_UNE, llvm::ConstantExpr::getBinOpIdentity(), llvm::SelectInst::getCondition(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Instruction::hasNoSignedZeros(), llvm::CmpInst::ICMP_EQ, llvm::Instruction::isCommutative(), llvm::ICmpInst::isEquality(), llvm::CmpInst::isFPPredicate(), llvm::PatternMatch::m_AnyZeroFP(), llvm::PatternMatch::m_BinOp(), llvm::PatternMatch::m_c_BinOp(), llvm::PatternMatch::m_Cmp(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::InstCombinerImpl::replaceOperand(), X, and Y.

◆ foldSelectICmpAnd()

static Value* foldSelectICmpAnd	(	SelectInst &	Sel,
		ICmpInst *	Cmp,
		InstCombiner::BuilderTy &	Builder
	)

static

This folds: select (icmp eq (and X, C1)), TC, FC iff C1 is a power 2 and the difference between TC and FC is a power-of-2.

To something like: (shr (and (X, C1)), (log2(C1) - log2(TC-FC))) + FC Or: (shl (and (X, C1)), (log2(TC-FC) - log2(C1))) + FC With some variations depending if FC is larger than TC, or the shift isn't needed, or the bit widths don't match.

Definition at line 125 of file InstCombineSelect.cpp.

References assert(), Builder, llvm::decomposeBitTestICmp(), R600_InstFlag::FC, llvm::ConstantInt::get(), llvm::APInt::getBitWidth(), llvm::SelectInst::getFalseValue(), llvm::SelectInst::getTrueValue(), llvm::Value::getType(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::ICmpInst::isEquality(), llvm::APInt::isNullValue(), llvm::APInt::isPowerOf2(), llvm::Type::isVectorTy(), llvm_unreachable, llvm::APInt::logBase2(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_Power2(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), and llvm::APInt::ugt().

◆ foldSelectICmpAndAnd()

static Instruction* foldSelectICmpAndAnd	(	Type *	SelType,
		const ICmpInst *	Cmp,
		Value *	TVal,
		Value *	FVal,
		InstCombiner::BuilderTy &	Builder
	)

static

We want to turn: (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1) into: zext (icmp ne i32 (and X, (or Y, (shl 1, Z))), 0) Note: Z may be 0 if lshr is missing.

Worst-case scenario is that we will replace 5 instructions with 5 different instructions, but we got rid of select.

Definition at line 518 of file InstCombineSelect.cpp.

References B, Builder, llvm::ConstantInt::get(), llvm::CmpInst::ICMP_EQ, llvm::PatternMatch::m_And(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), X, and Y.

◆ foldSelectICmpAndOr()

static Value* foldSelectICmpAndOr	(	const ICmpInst *	IC,
		Value *	TrueVal,
		Value *	FalseVal,
		InstCombiner::BuilderTy &	Builder
	)

static

We want to turn: (select (icmp eq (and X, C1), 0), Y, (or Y, C2)) into: (or (shl (and X, C1), C3), Y) iff: C1 and C2 are both powers of 2 where: C3 = Log(C2) - Log(C1)

This transform handles cases where:

The icmp predicate is inverted
The select operands are reversed
The magnitude of C2 and C1 are flipped

Definition at line 604 of file InstCombineSelect.cpp.

◆ foldSelectICmpLshrAshr()

static Value* foldSelectICmpLshrAshr	(	const ICmpInst *	IC,
		Value *	TrueVal,
		Value *	FalseVal,
		InstCombiner::BuilderTy &	Builder
	)

static

We want to turn: (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1 (select (icmp slt x, C), ashr (X, Y), lshr (X, Y)); iff C s>= 0 into: ashr (X, Y)

Definition at line 556 of file InstCombineSelect.cpp.

References Builder, llvm::tgtok::FalseVal, llvm::Value::getName(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::Type::isIntOrIntVectorTy(), llvm::PatternMatch::m_AShr(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificInt_ICMP(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), std::swap(), llvm::tgtok::TrueVal, X, and Y.

◆ foldSelectZeroOrMul()

static Instruction* foldSelectZeroOrMul	(	SelectInst &	SI,
		InstCombinerImpl &	IC
	)

static

◆ foldSetClearBits()

static Instruction* foldSetClearBits	(	SelectInst &	Sel,
		InstCombiner::BuilderTy &	Builder
	)

static

Canonicalize a set or clear of a masked set of constant bits to select-of-constants form.

Definition at line 696 of file InstCombineSelect.cpp.

References Builder, Cond, F, llvm::ConstantInt::get(), llvm::SelectInst::getCondition(), llvm::SelectInst::getFalseValue(), llvm::Constant::getNullValue(), llvm::SelectInst::getTrueValue(), llvm::Value::getType(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), T, and X.

◆ getSelectFoldableOperands()

static unsigned getSelectFoldableOperands ( BinaryOperator * I )

static

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 245 of file InstCombineSelect.cpp.

References llvm::MCID::Add, and I.

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

◆ isSelect01()

static bool isSelect01	(	const APInt &	C1I,
		const APInt &	C2I
	)

static

Definition at line 430 of file InstCombineSelect.cpp.

References llvm::APInt::isAllOnesValue(), llvm::APInt::isNullValue(), and llvm::APInt::isOneValue().

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

Macros

Functions

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ canonicalizeSaturatedAdd()

◆ canonicalizeSaturatedSubtract()

◆ createMinMax()

◆ foldSelectBinOpIdentity()

◆ foldSelectICmpAnd()

◆ foldSelectICmpAndAnd()

◆ foldSelectICmpAndOr()

◆ foldSelectICmpLshrAshr()

◆ foldSelectZeroOrMul()

◆ foldSetClearBits()

◆ getSelectFoldableOperands()

◆ isSelect01()