#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/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 <cassert>#include <utility>
Go to the source code of this file.
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) |
| 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 APInt | getSelectFoldableConstant (BinaryOperator *I) |
| For the same transformation as the previous function, return the identity constant that goes into the select. 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 * | 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 Value * | canonicalizeSaturatedSubtract (const ICmpInst *ICI, const Value *TrueVal, const Value *FalseVal, InstCombiner::BuilderTy &Builder) |
| Transform patterns such as: (a > b) ? a - b : 0 into: ((a > b) ? a : b) - b) This produces a canonical max pattern that is more easily recognized by the backend and converted into saturated subtraction instructions if those exist. More... | |
Macro Definition Documentation
◆ DEBUG_TYPE
| #define DEBUG_TYPE "instcombine" |
Definition at line 48 of file InstCombineSelect.cpp.
Function Documentation
◆ canonicalizeSaturatedSubtract()
|
static |
Transform patterns such as: (a > b) ? a - b : 0 into: ((a > b) ? a : b) - b) This produces a canonical max pattern that is more easily recognized by the backend and converted into saturated subtraction instructions if those exist.
There are 8 commuted/swapped variants of this pattern. TODO: Also support a - UMIN(a,b) patterns.
Definition at line 633 of file InstCombineSelect.cpp.
References llvm::MCID::Add, llvm::any_of(), assert(), B, C, llvm::Instruction::clone(), llvm::computeKnownBits(), llvm::CastInst::Create(), llvm::CallInst::Create(), llvm::SelectInst::Create(), CreateAdd(), llvm::IRBuilder< T, Inserter >::CreateAnd(), llvm::CastInst::CreateBitOrPointerCast(), llvm::IRBuilder< T, Inserter >::CreateCast(), llvm::IRBuilder< T, Inserter >::CreateFCmp(), llvm::IRBuilder< T, Inserter >::CreateFNeg(), llvm::IRBuilder< T, Inserter >::CreateICmp(), createMinMax(), llvm::IRBuilder< T, Inserter >::CreateNeg(), llvm::BinaryOperator::CreateNot(), llvm::IRBuilder< T, Inserter >::CreateNot(), llvm::IRBuilder< T, Inserter >::CreateOr(), llvm::IRBuilder< T, Inserter >::CreateSelect(), llvm::IRBuilder< T, Inserter >::CreateSub(), llvm::IRBuilderBase::CreateUnaryIntrinsic(), llvm::IRBuilder< T, Inserter >::CreateZExtOrTrunc(), D, llvm::dyn_cast(), F(), llvm::Intrinsic::fabs, llvm::CmpInst::FCMP_OGE, llvm::CmpInst::FCMP_OGT, llvm::CmpInst::FCMP_OLE, llvm::CmpInst::FCMP_OLT, llvm::SelectPatternResult::Flavor, foldSelectBinOpIdentity(), foldSelectICmpAnd(), foldSelectICmpAndAnd(), foldSelectICmpAndOr(), llvm::Intrinsic::fshl, llvm::Intrinsic::fshr, llvm::ConstantInt::get(), llvm::ConstantVector::get(), llvm::Constant::getAggregateElement(), llvm::APInt::getAllOnesValue(), llvm::CallBase::getArgOperand(), llvm::ConstantExpr::getCast(), llvm::SelectInst::getCondition(), llvm::Value::getContext(), llvm::Intrinsic::getDeclaration(), llvm::ConstantInt::getFalse(), llvm::SelectInst::getFalseValue(), llvm::Instruction::getFastMathFlags(), llvm::Type::getInt32Ty(), llvm::getInverseMinMaxFlavor(), llvm::CmpInst::getInversePredicate(), llvm::Instruction::getMetadata(), llvm::getMinMaxPred(), llvm::Instruction::getModule(), llvm::Value::getName(), llvm::Constant::getNullValue(), llvm::Instruction::getOpcode(), getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::CmpInst::getPredicate(), llvm::Type::getScalarSizeInBits(), llvm::Type::getScalarType(), llvm::ConstantExpr::getSExt(), llvm::APInt::getSignedMinValue(), llvm::CmpInst::getSwappedPredicate(), llvm::ConstantInt::getTrue(), llvm::SelectInst::getTrueValue(), llvm::ConstantExpr::getTrunc(), llvm::Value::getType(), llvm::Type::getVectorNumElements(), llvm::ConstantExpr::getZExt(), llvm::Value::hasNUses(), llvm::Value::hasNUsesOrMore(), llvm::Value::hasOneUse(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::IRBuilder< T, Inserter >::Insert(), Int32Ty, llvm::isCanonicalPredicate(), llvm::ICmpInst::isEquality(), llvm::Type::isFPOrFPVectorTy(), llvm::IsFreeToInvert(), llvm::Type::isIntOrIntVectorTy(), llvm::CmpInst::isIntPredicate(), llvm::isKnownNegation(), llvm::SelectPatternResult::isMinOrMax(), llvm::Constant::isNullValue(), llvm::Constant::isOneValue(), llvm::APInt::isOneValue(), llvm::isPowerOf2_32(), llvm::CmpInst::isUnordered(), llvm::CmpInst::isUnsigned(), llvm::Type::isVectorTy(), llvm::PatternMatch::m_AllOnes(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_AnyZeroFP(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_BinOp(), llvm::PatternMatch::m_BitCast(), llvm::PatternMatch::m_Cmp(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_FNeg(), llvm::PatternMatch::m_FSub(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::m_LogicalShift(), llvm::PatternMatch::m_Neg(), llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_PosZeroFP(), llvm::PatternMatch::m_Power2(), llvm::PatternMatch::m_SExt(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Xor(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::m_ZeroInt(), llvm::PatternMatch::m_ZExt(), llvm::BitmaskEnumDetail::Mask(), llvm::PatternMatch::match(), llvm::matchSelectPattern(), llvm::LLVMContext::MD_prof, llvm::Instruction::moveBefore(), llvm::KnownBits::One, llvm::SelectPatternResult::Ordered, P, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::User::replaceUsesOfWith(), llvm::SmallVectorImpl< T >::reserve(), llvm::MCID::Select, llvm::CallBase::setArgOperand(), llvm::SelectInst::setCondition(), llvm::SelectInst::setFalseValue(), llvm::IRBuilderBase::setFastMathFlags(), llvm::Instruction::setFastMathFlags(), setMetadata(), llvm::User::setOperand(), llvm::CmpInst::setPredicate(), llvm::SelectInst::setTrueValue(), llvm::APInt::sge(), llvm::APInt::sgt(), SI, llvm::SimplifySelectInst(), llvm::APInt::sle(), llvm::APInt::slt(), llvm::SPF_ABS, llvm::SPF_NABS, llvm::SPF_SMAX, llvm::SPF_SMIN, llvm::SPF_UMAX, llvm::SPF_UMIN, std::swap(), llvm::Instruction::swapProfMetadata(), llvm::APInt::uge(), llvm::APInt::ugt(), llvm::APInt::ule(), llvm::APInt::ult(), llvm::Instruction::user_back(), llvm::Value::users(), llvm::InstCombiner::visitSelectInst(), X, Y, and llvm::KnownBits::Zero.
◆ createMinMax()
|
static |
Definition at line 50 of file InstCombineSelect.cpp.
References assert(), B, llvm::IRBuilder< T, Inserter >::CreateICmp(), llvm::IRBuilder< T, Inserter >::CreateSelect(), llvm::getMinMaxPred(), and llvm::CmpInst::isIntPredicate().
Referenced by canonicalizeSaturatedSubtract().
◆ foldSelectBinOpIdentity()
|
static |
Replace a select operand based on an equality comparison with the identity constant of a binop.
Definition at line 59 of file InstCombineSelect.cpp.
References C, 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::User::setOperand(), X, and Y.
Referenced by canonicalizeSaturatedSubtract().
◆ foldSelectICmpAnd()
|
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 124 of file InstCombineSelect.cpp.
References assert(), C, llvm::IRBuilder< T, Inserter >::CreateAnd(), llvm::IRBuilder< T, Inserter >::CreateLShr(), llvm::IRBuilder< T, Inserter >::CreateOr(), llvm::IRBuilder< T, Inserter >::CreateShl(), llvm::IRBuilder< T, Inserter >::CreateXor(), llvm::IRBuilder< T, Inserter >::CreateZExtOrTrunc(), llvm::decomposeBitTestICmp(), R600_InstFlag::FC, llvm::ConstantInt::get(), llvm::APInt::getBitWidth(), llvm::SelectInst::getFalseValue(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::SelectInst::getTrueValue(), llvm::Value::getType(), llvm::Value::hasOneUse(), 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().
Referenced by canonicalizeSaturatedSubtract().
◆ foldSelectICmpAndAnd()
|
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 490 of file InstCombineSelect.cpp.
References B, llvm::IRBuilder< T, Inserter >::CreateAnd(), llvm::IRBuilder< T, Inserter >::CreateIsNotNull(), llvm::IRBuilder< T, Inserter >::CreateOr(), llvm::IRBuilder< T, Inserter >::CreateShl(), llvm::ConstantInt::get(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::Value::hasOneUse(), 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.
Referenced by canonicalizeSaturatedSubtract().
◆ foldSelectICmpAndOr()
|
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 536 of file InstCombineSelect.cpp.
References llvm::IRBuilder< T, Inserter >::CreateAnd(), llvm::IRBuilder< T, Inserter >::CreateLShr(), llvm::IRBuilder< T, Inserter >::CreateOr(), llvm::IRBuilder< T, Inserter >::CreateShl(), llvm::IRBuilder< T, Inserter >::CreateXor(), llvm::IRBuilder< T, Inserter >::CreateZExtOrTrunc(), llvm::ConstantInt::get(), llvm::APInt::getOneBitSet(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), llvm::Value::hasOneUse(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::ICmpInst::isEquality(), llvm::Type::isIntOrIntVectorTy(), llvm::Type::isVectorTy(), llvm::APInt::logBase2(), llvm::PatternMatch::m_AllOnes(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Power2(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), NeedAnd, and Y.
Referenced by canonicalizeSaturatedSubtract().
◆ getSelectFoldableConstant()
|
static |
For the same transformation as the previous function, return the identity constant that goes into the select.
Definition at line 264 of file InstCombineSelect.cpp.
References llvm::MCID::Add, llvm::Instruction::andIRFlags(), llvm::Instruction::copyIRFlags(), llvm::BinaryOperator::Create(), llvm::CastInst::Create(), llvm::GetElementPtrInst::Create(), llvm::GetElementPtrInst::CreateInBounds(), llvm::APInt::getAllOnesValue(), llvm::SelectInst::getCondition(), llvm::Value::getName(), llvm::APInt::getNullValue(), llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), llvm::Type::getVectorNumElements(), llvm::Value::hasOneUse(), llvm::Instruction::isCast(), llvm::Instruction::isCommutative(), llvm::Type::isVectorTy(), llvm_unreachable, llvm::PatternMatch::m_SMax(), llvm::PatternMatch::m_SMin(), llvm::PatternMatch::m_UMax(), llvm::PatternMatch::m_UMin(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and SI.
Referenced by isSelect01().
◆ getSelectFoldableOperands()
|
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 244 of file InstCombineSelect.cpp.
References llvm::MCID::Add, and llvm::BinaryOperator::getOpcode().
Referenced by isSelect01().
◆ isSelect01()
Definition at line 404 of file InstCombineSelect.cpp.
References C, llvm::Instruction::copyIRFlags(), llvm::BinaryOperator::Create(), llvm::ConstantInt::get(), llvm::SelectInst::getCondition(), getSelectFoldableConstant(), getSelectFoldableOperands(), llvm::Value::getType(), llvm::APInt::isAllOnesValue(), llvm::APInt::isNullValue(), llvm::APInt::isOneValue(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::match(), and llvm::Value::takeName().
