4845 lines · cpp
1//===- InstCombineSelect.cpp ----------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the visitSelect function.10//11//===----------------------------------------------------------------------===//12 13#include "InstCombineInternal.h"14#include "llvm/ADT/APInt.h"15#include "llvm/ADT/STLExtras.h"16#include "llvm/ADT/SmallVector.h"17#include "llvm/Analysis/AssumptionCache.h"18#include "llvm/Analysis/CmpInstAnalysis.h"19#include "llvm/Analysis/InstructionSimplify.h"20#include "llvm/Analysis/Loads.h"21#include "llvm/Analysis/OverflowInstAnalysis.h"22#include "llvm/Analysis/ValueTracking.h"23#include "llvm/Analysis/VectorUtils.h"24#include "llvm/IR/BasicBlock.h"25#include "llvm/IR/Constant.h"26#include "llvm/IR/ConstantRange.h"27#include "llvm/IR/Constants.h"28#include "llvm/IR/DerivedTypes.h"29#include "llvm/IR/FMF.h"30#include "llvm/IR/IRBuilder.h"31#include "llvm/IR/InstrTypes.h"32#include "llvm/IR/Instruction.h"33#include "llvm/IR/Instructions.h"34#include "llvm/IR/IntrinsicInst.h"35#include "llvm/IR/Intrinsics.h"36#include "llvm/IR/Operator.h"37#include "llvm/IR/PatternMatch.h"38#include "llvm/IR/Type.h"39#include "llvm/IR/User.h"40#include "llvm/IR/Value.h"41#include "llvm/Support/Casting.h"42#include "llvm/Support/ErrorHandling.h"43#include "llvm/Support/KnownBits.h"44#include "llvm/Transforms/InstCombine/InstCombiner.h"45#include <cassert>46#include <optional>47#include <utility>48 49#define DEBUG_TYPE "instcombine"50#include "llvm/Transforms/Utils/InstructionWorklist.h"51 52using namespace llvm;53using namespace PatternMatch;54 55namespace llvm {56extern cl::opt<bool> ProfcheckDisableMetadataFixes;57}58 59/// Replace a select operand based on an equality comparison with the identity60/// constant of a binop.61static Instruction *foldSelectBinOpIdentity(SelectInst &Sel,62 const TargetLibraryInfo &TLI,63 InstCombinerImpl &IC) {64 // The select condition must be an equality compare with a constant operand.65 Value *X;66 Constant *C;67 CmpPredicate Pred;68 if (!match(Sel.getCondition(), m_Cmp(Pred, m_Value(X), m_Constant(C))))69 return nullptr;70 71 bool IsEq;72 if (ICmpInst::isEquality(Pred))73 IsEq = Pred == ICmpInst::ICMP_EQ;74 else if (Pred == FCmpInst::FCMP_OEQ)75 IsEq = true;76 else if (Pred == FCmpInst::FCMP_UNE)77 IsEq = false;78 else79 return nullptr;80 81 // A select operand must be a binop.82 BinaryOperator *BO;83 if (!match(Sel.getOperand(IsEq ? 1 : 2), m_BinOp(BO)))84 return nullptr;85 86 // The compare constant must be the identity constant for that binop.87 // If this a floating-point compare with 0.0, any zero constant will do.88 Type *Ty = BO->getType();89 Constant *IdC = ConstantExpr::getBinOpIdentity(BO->getOpcode(), Ty, true);90 if (IdC != C) {91 if (!IdC || !CmpInst::isFPPredicate(Pred))92 return nullptr;93 if (!match(IdC, m_AnyZeroFP()) || !match(C, m_AnyZeroFP()))94 return nullptr;95 }96 97 // Last, match the compare variable operand with a binop operand.98 Value *Y;99 if (!BO->isCommutative() && !match(BO, m_BinOp(m_Value(Y), m_Specific(X))))100 return nullptr;101 if (!match(BO, m_c_BinOp(m_Value(Y), m_Specific(X))))102 return nullptr;103 104 // +0.0 compares equal to -0.0, and so it does not behave as required for this105 // transform. Bail out if we can not exclude that possibility.106 if (isa<FPMathOperator>(BO))107 if (!BO->hasNoSignedZeros() &&108 !cannotBeNegativeZero(Y,109 IC.getSimplifyQuery().getWithInstruction(&Sel)))110 return nullptr;111 112 // BO = binop Y, X113 // S = { select (cmp eq X, C), BO, ? } or { select (cmp ne X, C), ?, BO }114 // =>115 // S = { select (cmp eq X, C), Y, ? } or { select (cmp ne X, C), ?, Y }116 return IC.replaceOperand(Sel, IsEq ? 1 : 2, Y);117}118 119/// This folds:120/// select (icmp eq (and X, C1)), TC, FC121/// iff C1 is a power 2 and the difference between TC and FC is a power-of-2.122/// To something like:123/// (shr (and (X, C1)), (log2(C1) - log2(TC-FC))) + FC124/// Or:125/// (shl (and (X, C1)), (log2(TC-FC) - log2(C1))) + FC126/// With some variations depending if FC is larger than TC, or the shift127/// isn't needed, or the bit widths don't match.128static Value *foldSelectICmpAnd(SelectInst &Sel, Value *CondVal, Value *TrueVal,129 Value *FalseVal, Value *V, const APInt &AndMask,130 bool CreateAnd,131 InstCombiner::BuilderTy &Builder) {132 const APInt *SelTC, *SelFC;133 if (!match(TrueVal, m_APInt(SelTC)) || !match(FalseVal, m_APInt(SelFC)))134 return nullptr;135 136 Type *SelType = Sel.getType();137 // In general, when both constants are non-zero, we would need an offset to138 // replace the select. This would require more instructions than we started139 // with. But there's one special-case that we handle here because it can140 // simplify/reduce the instructions.141 const APInt &TC = *SelTC;142 const APInt &FC = *SelFC;143 if (!TC.isZero() && !FC.isZero()) {144 if (TC.getBitWidth() != AndMask.getBitWidth())145 return nullptr;146 // If we have to create an 'and', then we must kill the cmp to not147 // increase the instruction count.148 if (CreateAnd && !CondVal->hasOneUse())149 return nullptr;150 151 // (V & AndMaskC) == 0 ? TC : FC --> TC | (V & AndMaskC)152 // (V & AndMaskC) == 0 ? TC : FC --> TC ^ (V & AndMaskC)153 // (V & AndMaskC) == 0 ? TC : FC --> TC + (V & AndMaskC)154 // (V & AndMaskC) == 0 ? TC : FC --> TC - (V & AndMaskC)155 Constant *TCC = ConstantInt::get(SelType, TC);156 Constant *FCC = ConstantInt::get(SelType, FC);157 Constant *MaskC = ConstantInt::get(SelType, AndMask);158 for (auto Opc : {Instruction::Or, Instruction::Xor, Instruction::Add,159 Instruction::Sub}) {160 if (ConstantFoldBinaryOpOperands(Opc, TCC, MaskC, Sel.getDataLayout()) ==161 FCC) {162 if (CreateAnd)163 V = Builder.CreateAnd(V, MaskC);164 return Builder.CreateBinOp(Opc, TCC, V);165 }166 }167 168 return nullptr;169 }170 171 // Make sure one of the select arms is a power-of-2.172 if (!TC.isPowerOf2() && !FC.isPowerOf2())173 return nullptr;174 175 // Determine which shift is needed to transform result of the 'and' into the176 // desired result.177 const APInt &ValC = !TC.isZero() ? TC : FC;178 unsigned ValZeros = ValC.logBase2();179 unsigned AndZeros = AndMask.logBase2();180 bool ShouldNotVal = !TC.isZero();181 bool NeedShift = ValZeros != AndZeros;182 bool NeedZExtTrunc =183 SelType->getScalarSizeInBits() != V->getType()->getScalarSizeInBits();184 185 // If we would need to create an 'and' + 'shift' + 'xor' + cast to replace186 // a 'select' + 'icmp', then this transformation would result in more187 // instructions and potentially interfere with other folding.188 if (CreateAnd + ShouldNotVal + NeedShift + NeedZExtTrunc >189 1 + CondVal->hasOneUse())190 return nullptr;191 192 // Insert the 'and' instruction on the input to the truncate.193 if (CreateAnd)194 V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), AndMask));195 196 // If types don't match, we can still convert the select by introducing a zext197 // or a trunc of the 'and'.198 if (ValZeros > AndZeros) {199 V = Builder.CreateZExtOrTrunc(V, SelType);200 V = Builder.CreateShl(V, ValZeros - AndZeros);201 } else if (ValZeros < AndZeros) {202 V = Builder.CreateLShr(V, AndZeros - ValZeros);203 V = Builder.CreateZExtOrTrunc(V, SelType);204 } else {205 V = Builder.CreateZExtOrTrunc(V, SelType);206 }207 208 // Okay, now we know that everything is set up, we just don't know whether we209 // have a icmp_ne or icmp_eq and whether the true or false val is the zero.210 if (ShouldNotVal)211 V = Builder.CreateXor(V, ValC);212 213 return V;214}215 216/// We want to turn code that looks like this:217/// %C = or %A, %B218/// %D = select %cond, %C, %A219/// into:220/// %C = select %cond, %B, 0221/// %D = or %A, %C222///223/// Assuming that the specified instruction is an operand to the select, return224/// a bitmask indicating which operands of this instruction are foldable if they225/// equal the other incoming value of the select.226static unsigned getSelectFoldableOperands(BinaryOperator *I) {227 switch (I->getOpcode()) {228 case Instruction::Add:229 case Instruction::FAdd:230 case Instruction::Mul:231 case Instruction::FMul:232 case Instruction::And:233 case Instruction::Or:234 case Instruction::Xor:235 return 3; // Can fold through either operand.236 case Instruction::Sub: // Can only fold on the amount subtracted.237 case Instruction::FSub:238 case Instruction::FDiv: // Can only fold on the divisor amount.239 case Instruction::Shl: // Can only fold on the shift amount.240 case Instruction::LShr:241 case Instruction::AShr:242 return 1;243 default:244 return 0; // Cannot fold245 }246}247 248/// We have (select c, TI, FI), and we know that TI and FI have the same opcode.249Instruction *InstCombinerImpl::foldSelectOpOp(SelectInst &SI, Instruction *TI,250 Instruction *FI) {251 // Don't break up min/max patterns. The hasOneUse checks below prevent that252 // for most cases, but vector min/max with bitcasts can be transformed. If the253 // one-use restrictions are eased for other patterns, we still don't want to254 // obfuscate min/max.255 if ((match(&SI, m_SMin(m_Value(), m_Value())) ||256 match(&SI, m_SMax(m_Value(), m_Value())) ||257 match(&SI, m_UMin(m_Value(), m_Value())) ||258 match(&SI, m_UMax(m_Value(), m_Value()))))259 return nullptr;260 261 // If this is a cast from the same type, merge.262 Value *Cond = SI.getCondition();263 Type *CondTy = Cond->getType();264 if (TI->getNumOperands() == 1 && TI->isCast()) {265 Type *FIOpndTy = FI->getOperand(0)->getType();266 if (TI->getOperand(0)->getType() != FIOpndTy)267 return nullptr;268 269 // The select condition may be a vector. We may only change the operand270 // type if the vector width remains the same (and matches the condition).271 if (auto *CondVTy = dyn_cast<VectorType>(CondTy)) {272 if (!FIOpndTy->isVectorTy() ||273 CondVTy->getElementCount() !=274 cast<VectorType>(FIOpndTy)->getElementCount())275 return nullptr;276 277 // TODO: If the backend knew how to deal with casts better, we could278 // remove this limitation. For now, there's too much potential to create279 // worse codegen by promoting the select ahead of size-altering casts280 // (PR28160).281 //282 // Note that ValueTracking's matchSelectPattern() looks through casts283 // without checking 'hasOneUse' when it matches min/max patterns, so this284 // transform may end up happening anyway.285 if (TI->getOpcode() != Instruction::BitCast &&286 (!TI->hasOneUse() || !FI->hasOneUse()))287 return nullptr;288 } else if (!TI->hasOneUse() || !FI->hasOneUse()) {289 // TODO: The one-use restrictions for a scalar select could be eased if290 // the fold of a select in visitLoadInst() was enhanced to match a pattern291 // that includes a cast.292 return nullptr;293 }294 295 // Fold this by inserting a select from the input values.296 Value *NewSI =297 Builder.CreateSelect(Cond, TI->getOperand(0), FI->getOperand(0),298 SI.getName() + ".v", &SI);299 return CastInst::Create(Instruction::CastOps(TI->getOpcode()), NewSI,300 TI->getType());301 }302 303 Value *OtherOpT, *OtherOpF;304 bool MatchIsOpZero;305 auto getCommonOp = [&](Instruction *TI, Instruction *FI, bool Commute,306 bool Swapped = false) -> Value * {307 assert(!(Commute && Swapped) &&308 "Commute and Swapped can't set at the same time");309 if (!Swapped) {310 if (TI->getOperand(0) == FI->getOperand(0)) {311 OtherOpT = TI->getOperand(1);312 OtherOpF = FI->getOperand(1);313 MatchIsOpZero = true;314 return TI->getOperand(0);315 } else if (TI->getOperand(1) == FI->getOperand(1)) {316 OtherOpT = TI->getOperand(0);317 OtherOpF = FI->getOperand(0);318 MatchIsOpZero = false;319 return TI->getOperand(1);320 }321 }322 323 if (!Commute && !Swapped)324 return nullptr;325 326 // If we are allowing commute or swap of operands, then327 // allow a cross-operand match. In that case, MatchIsOpZero328 // means that TI's operand 0 (FI's operand 1) is the common op.329 if (TI->getOperand(0) == FI->getOperand(1)) {330 OtherOpT = TI->getOperand(1);331 OtherOpF = FI->getOperand(0);332 MatchIsOpZero = true;333 return TI->getOperand(0);334 } else if (TI->getOperand(1) == FI->getOperand(0)) {335 OtherOpT = TI->getOperand(0);336 OtherOpF = FI->getOperand(1);337 MatchIsOpZero = false;338 return TI->getOperand(1);339 }340 return nullptr;341 };342 343 if (TI->hasOneUse() || FI->hasOneUse()) {344 // Cond ? -X : -Y --> -(Cond ? X : Y)345 Value *X, *Y;346 if (match(TI, m_FNeg(m_Value(X))) && match(FI, m_FNeg(m_Value(Y)))) {347 // Intersect FMF from the fneg instructions and union those with the348 // select.349 FastMathFlags FMF = TI->getFastMathFlags();350 FMF &= FI->getFastMathFlags();351 FMF |= SI.getFastMathFlags();352 Value *NewSel =353 Builder.CreateSelect(Cond, X, Y, SI.getName() + ".v", &SI);354 if (auto *NewSelI = dyn_cast<Instruction>(NewSel))355 NewSelI->setFastMathFlags(FMF);356 Instruction *NewFNeg = UnaryOperator::CreateFNeg(NewSel);357 NewFNeg->setFastMathFlags(FMF);358 return NewFNeg;359 }360 361 // Min/max intrinsic with a common operand can have the common operand362 // pulled after the select. This is the same transform as below for binops,363 // but specialized for intrinsic matching and without the restrictive uses364 // clause.365 auto *TII = dyn_cast<IntrinsicInst>(TI);366 auto *FII = dyn_cast<IntrinsicInst>(FI);367 if (TII && FII && TII->getIntrinsicID() == FII->getIntrinsicID()) {368 if (match(TII, m_MaxOrMin(m_Value(), m_Value()))) {369 if (Value *MatchOp = getCommonOp(TI, FI, true)) {370 Value *NewSel =371 Builder.CreateSelect(Cond, OtherOpT, OtherOpF, "minmaxop", &SI);372 return CallInst::Create(TII->getCalledFunction(), {NewSel, MatchOp});373 }374 }375 376 // select c, (ldexp v, e0), (ldexp v, e1) -> ldexp v, (select c, e0, e1)377 // select c, (ldexp v0, e), (ldexp v1, e) -> ldexp (select c, v0, v1), e378 //379 // select c, (ldexp v0, e0), (ldexp v1, e1) ->380 // ldexp (select c, v0, v1), (select c, e0, e1)381 if (TII->getIntrinsicID() == Intrinsic::ldexp) {382 Value *LdexpVal0 = TII->getArgOperand(0);383 Value *LdexpExp0 = TII->getArgOperand(1);384 Value *LdexpVal1 = FII->getArgOperand(0);385 Value *LdexpExp1 = FII->getArgOperand(1);386 if (LdexpExp0->getType() == LdexpExp1->getType()) {387 FPMathOperator *SelectFPOp = cast<FPMathOperator>(&SI);388 FastMathFlags FMF = cast<FPMathOperator>(TII)->getFastMathFlags();389 FMF &= cast<FPMathOperator>(FII)->getFastMathFlags();390 FMF |= SelectFPOp->getFastMathFlags();391 392 Value *SelectVal = Builder.CreateSelect(Cond, LdexpVal0, LdexpVal1);393 Value *SelectExp = Builder.CreateSelect(Cond, LdexpExp0, LdexpExp1);394 395 CallInst *NewLdexp = Builder.CreateIntrinsic(396 TII->getType(), Intrinsic::ldexp, {SelectVal, SelectExp});397 NewLdexp->setFastMathFlags(FMF);398 return replaceInstUsesWith(SI, NewLdexp);399 }400 }401 }402 403 auto CreateCmpSel = [&](std::optional<CmpPredicate> P,404 bool Swapped) -> CmpInst * {405 if (!P)406 return nullptr;407 auto *MatchOp = getCommonOp(TI, FI, ICmpInst::isEquality(*P),408 ICmpInst::isRelational(*P) && Swapped);409 if (!MatchOp)410 return nullptr;411 Value *NewSel = Builder.CreateSelect(Cond, OtherOpT, OtherOpF,412 SI.getName() + ".v", &SI);413 return new ICmpInst(MatchIsOpZero ? *P414 : ICmpInst::getSwappedCmpPredicate(*P),415 MatchOp, NewSel);416 };417 418 // icmp with a common operand also can have the common operand419 // pulled after the select.420 CmpPredicate TPred, FPred;421 if (match(TI, m_ICmp(TPred, m_Value(), m_Value())) &&422 match(FI, m_ICmp(FPred, m_Value(), m_Value()))) {423 if (auto *R =424 CreateCmpSel(CmpPredicate::getMatching(TPred, FPred), false))425 return R;426 if (auto *R =427 CreateCmpSel(CmpPredicate::getMatching(428 TPred, ICmpInst::getSwappedCmpPredicate(FPred)),429 true))430 return R;431 }432 }433 434 // Only handle binary operators (including two-operand getelementptr) with435 // one-use here. As with the cast case above, it may be possible to relax the436 // one-use constraint, but that needs be examined carefully since it may not437 // reduce the total number of instructions.438 if (TI->getNumOperands() != 2 || FI->getNumOperands() != 2 ||439 !TI->isSameOperationAs(FI) ||440 (!isa<BinaryOperator>(TI) && !isa<GetElementPtrInst>(TI)) ||441 !TI->hasOneUse() || !FI->hasOneUse())442 return nullptr;443 444 // Figure out if the operations have any operands in common.445 Value *MatchOp = getCommonOp(TI, FI, TI->isCommutative());446 if (!MatchOp)447 return nullptr;448 449 // If the select condition is a vector, the operands of the original select's450 // operands also must be vectors. This may not be the case for getelementptr451 // for example.452 if (CondTy->isVectorTy() && (!OtherOpT->getType()->isVectorTy() ||453 !OtherOpF->getType()->isVectorTy()))454 return nullptr;455 456 // If we are sinking div/rem after a select, we may need to freeze the457 // condition because div/rem may induce immediate UB with a poison operand.458 // For example, the following transform is not safe if Cond can ever be poison459 // because we can replace poison with zero and then we have div-by-zero that460 // didn't exist in the original code:461 // Cond ? x/y : x/z --> x / (Cond ? y : z)462 auto *BO = dyn_cast<BinaryOperator>(TI);463 if (BO && BO->isIntDivRem() && !isGuaranteedNotToBePoison(Cond)) {464 // A udiv/urem with a common divisor is safe because UB can only occur with465 // div-by-zero, and that would be present in the original code.466 if (BO->getOpcode() == Instruction::SDiv ||467 BO->getOpcode() == Instruction::SRem || MatchIsOpZero)468 Cond = Builder.CreateFreeze(Cond);469 }470 471 // If we reach here, they do have operations in common.472 Value *NewSI = Builder.CreateSelect(Cond, OtherOpT, OtherOpF,473 SI.getName() + ".v", &SI);474 Value *Op0 = MatchIsOpZero ? MatchOp : NewSI;475 Value *Op1 = MatchIsOpZero ? NewSI : MatchOp;476 if (auto *BO = dyn_cast<BinaryOperator>(TI)) {477 BinaryOperator *NewBO = BinaryOperator::Create(BO->getOpcode(), Op0, Op1);478 NewBO->copyIRFlags(TI);479 NewBO->andIRFlags(FI);480 return NewBO;481 }482 if (auto *TGEP = dyn_cast<GetElementPtrInst>(TI)) {483 auto *FGEP = cast<GetElementPtrInst>(FI);484 Type *ElementType = TGEP->getSourceElementType();485 return GetElementPtrInst::Create(486 ElementType, Op0, Op1, TGEP->getNoWrapFlags() & FGEP->getNoWrapFlags());487 }488 llvm_unreachable("Expected BinaryOperator or GEP");489 return nullptr;490}491 492static bool isSelect01(const APInt &C1I, const APInt &C2I) {493 if (!C1I.isZero() && !C2I.isZero()) // One side must be zero.494 return false;495 return C1I.isOne() || C1I.isAllOnes() || C2I.isOne() || C2I.isAllOnes();496}497 498/// Try to fold the select into one of the operands to allow further499/// optimization.500Instruction *InstCombinerImpl::foldSelectIntoOp(SelectInst &SI, Value *TrueVal,501 Value *FalseVal) {502 // See the comment above getSelectFoldableOperands for a description of the503 // transformation we are doing here.504 auto TryFoldSelectIntoOp = [&](SelectInst &SI, Value *TrueVal,505 Value *FalseVal,506 bool Swapped) -> Instruction * {507 auto *TVI = dyn_cast<BinaryOperator>(TrueVal);508 if (!TVI || !TVI->hasOneUse() || isa<Constant>(FalseVal))509 return nullptr;510 511 unsigned SFO = getSelectFoldableOperands(TVI);512 unsigned OpToFold = 0;513 if ((SFO & 1) && FalseVal == TVI->getOperand(0))514 OpToFold = 1;515 else if ((SFO & 2) && FalseVal == TVI->getOperand(1))516 OpToFold = 2;517 518 if (!OpToFold)519 return nullptr;520 521 FastMathFlags FMF;522 if (isa<FPMathOperator>(&SI))523 FMF = SI.getFastMathFlags();524 Constant *C = ConstantExpr::getBinOpIdentity(525 TVI->getOpcode(), TVI->getType(), true, FMF.noSignedZeros());526 Value *OOp = TVI->getOperand(2 - OpToFold);527 // Avoid creating select between 2 constants unless it's selecting528 // between 0, 1 and -1.529 const APInt *OOpC;530 bool OOpIsAPInt = match(OOp, m_APInt(OOpC));531 if (isa<Constant>(OOp) &&532 (!OOpIsAPInt || !isSelect01(C->getUniqueInteger(), *OOpC)))533 return nullptr;534 535 // If the false value is a NaN then we have that the floating point math536 // operation in the transformed code may not preserve the exact NaN537 // bit-pattern -- e.g. `fadd sNaN, 0.0 -> qNaN`.538 // This makes the transformation incorrect since the original program would539 // have preserved the exact NaN bit-pattern.540 // Avoid the folding if the false value might be a NaN.541 if (isa<FPMathOperator>(&SI) &&542 !computeKnownFPClass(FalseVal, FMF, fcNan, &SI).isKnownNeverNaN())543 return nullptr;544 545 Value *NewSel = Builder.CreateSelect(SI.getCondition(), Swapped ? C : OOp,546 Swapped ? OOp : C, "", &SI);547 if (isa<FPMathOperator>(&SI)) {548 FastMathFlags NewSelFMF = FMF;549 // We cannot propagate ninf from the original select, because OOp may be550 // inf and the flag only guarantees that FalseVal (op OOp) is never551 // infinity.552 // Examples: -inf + +inf = NaN, -inf - -inf = NaN, 0 * inf = NaN553 // Specifically, if the original select has both ninf and nnan, we can554 // safely propagate the flag.555 NewSelFMF.setNoInfs(TVI->hasNoInfs() ||556 (NewSelFMF.noInfs() && NewSelFMF.noNaNs()));557 cast<Instruction>(NewSel)->setFastMathFlags(NewSelFMF);558 }559 NewSel->takeName(TVI);560 BinaryOperator *BO =561 BinaryOperator::Create(TVI->getOpcode(), FalseVal, NewSel);562 BO->copyIRFlags(TVI);563 if (isa<FPMathOperator>(&SI)) {564 // Merge poison generating flags from the select.565 BO->setHasNoNaNs(BO->hasNoNaNs() && FMF.noNaNs());566 BO->setHasNoInfs(BO->hasNoInfs() && FMF.noInfs());567 // Merge no-signed-zeros flag from the select.568 // Otherwise we may produce zeros with different sign.569 BO->setHasNoSignedZeros(BO->hasNoSignedZeros() && FMF.noSignedZeros());570 }571 return BO;572 };573 574 if (Instruction *R = TryFoldSelectIntoOp(SI, TrueVal, FalseVal, false))575 return R;576 577 if (Instruction *R = TryFoldSelectIntoOp(SI, FalseVal, TrueVal, true))578 return R;579 580 return nullptr;581}582 583/// Try to fold a select to a min/max intrinsic. Many cases are already handled584/// by matchDecomposedSelectPattern but here we handle the cases where more585/// extensive modification of the IR is required.586static Value *foldSelectICmpMinMax(const ICmpInst *Cmp, Value *TVal,587 Value *FVal,588 InstCombiner::BuilderTy &Builder,589 const SimplifyQuery &SQ) {590 const Value *CmpLHS = Cmp->getOperand(0);591 const Value *CmpRHS = Cmp->getOperand(1);592 ICmpInst::Predicate Pred = Cmp->getPredicate();593 594 // (X > Y) ? X : (Y - 1) ==> MIN(X, Y - 1)595 // (X < Y) ? X : (Y + 1) ==> MAX(X, Y + 1)596 // This transformation is valid when overflow corresponding to the sign of597 // the comparison is poison and we must drop the non-matching overflow flag.598 if (CmpRHS == TVal) {599 std::swap(CmpLHS, CmpRHS);600 Pred = CmpInst::getSwappedPredicate(Pred);601 }602 603 // TODO: consider handling 'or disjoint' as well, though these would need to604 // be converted to 'add' instructions.605 if (!(CmpLHS == TVal && isa<Instruction>(FVal)))606 return nullptr;607 608 if (Pred == CmpInst::ICMP_SGT &&609 match(FVal, m_NSWAdd(m_Specific(CmpRHS), m_One()))) {610 cast<Instruction>(FVal)->setHasNoUnsignedWrap(false);611 return Builder.CreateBinaryIntrinsic(Intrinsic::smax, TVal, FVal);612 }613 614 if (Pred == CmpInst::ICMP_SLT &&615 match(FVal, m_NSWAdd(m_Specific(CmpRHS), m_AllOnes()))) {616 cast<Instruction>(FVal)->setHasNoUnsignedWrap(false);617 return Builder.CreateBinaryIntrinsic(Intrinsic::smin, TVal, FVal);618 }619 620 if (Pred == CmpInst::ICMP_UGT &&621 match(FVal, m_NUWAdd(m_Specific(CmpRHS), m_One()))) {622 cast<Instruction>(FVal)->setHasNoSignedWrap(false);623 return Builder.CreateBinaryIntrinsic(Intrinsic::umax, TVal, FVal);624 }625 626 // Note: We must use isKnownNonZero here because "sub nuw %x, 1" will be627 // canonicalized to "add %x, -1" discarding the nuw flag.628 if (Pred == CmpInst::ICMP_ULT &&629 match(FVal, m_Add(m_Specific(CmpRHS), m_AllOnes())) &&630 isKnownNonZero(CmpRHS, SQ)) {631 cast<Instruction>(FVal)->setHasNoSignedWrap(false);632 cast<Instruction>(FVal)->setHasNoUnsignedWrap(false);633 return Builder.CreateBinaryIntrinsic(Intrinsic::umin, TVal, FVal);634 }635 636 return nullptr;637}638 639/// We want to turn:640/// (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1)641/// into:642/// zext (icmp ne i32 (and X, (or Y, (shl 1, Z))), 0)643/// Note:644/// Z may be 0 if lshr is missing.645/// Worst-case scenario is that we will replace 5 instructions with 5 different646/// instructions, but we got rid of select.647static Instruction *foldSelectICmpAndAnd(Type *SelType, const ICmpInst *Cmp,648 Value *TVal, Value *FVal,649 InstCombiner::BuilderTy &Builder) {650 if (!(Cmp->hasOneUse() && Cmp->getOperand(0)->hasOneUse() &&651 Cmp->getPredicate() == ICmpInst::ICMP_EQ &&652 match(Cmp->getOperand(1), m_Zero()) && match(FVal, m_One())))653 return nullptr;654 655 // The TrueVal has general form of: and %B, 1656 Value *B;657 if (!match(TVal, m_OneUse(m_And(m_Value(B), m_One()))))658 return nullptr;659 660 // Where %B may be optionally shifted: lshr %X, %Z.661 Value *X, *Z;662 const bool HasShift = match(B, m_OneUse(m_LShr(m_Value(X), m_Value(Z))));663 664 // The shift must be valid.665 // TODO: This restricts the fold to constant shift amounts. Is there a way to666 // handle variable shifts safely? PR47012667 if (HasShift &&668 !match(Z, m_SpecificInt_ICMP(CmpInst::ICMP_ULT,669 APInt(SelType->getScalarSizeInBits(),670 SelType->getScalarSizeInBits()))))671 return nullptr;672 673 if (!HasShift)674 X = B;675 676 Value *Y;677 if (!match(Cmp->getOperand(0), m_c_And(m_Specific(X), m_Value(Y))))678 return nullptr;679 680 // ((X & Y) == 0) ? ((X >> Z) & 1) : 1 --> (X & (Y | (1 << Z))) != 0681 // ((X & Y) == 0) ? (X & 1) : 1 --> (X & (Y | 1)) != 0682 Constant *One = ConstantInt::get(SelType, 1);683 Value *MaskB = HasShift ? Builder.CreateShl(One, Z) : One;684 Value *FullMask = Builder.CreateOr(Y, MaskB);685 Value *MaskedX = Builder.CreateAnd(X, FullMask);686 Value *ICmpNeZero = Builder.CreateIsNotNull(MaskedX);687 return new ZExtInst(ICmpNeZero, SelType);688}689 690/// We want to turn:691/// (select (icmp eq (and X, C1), 0), 0, (shl [nsw/nuw] X, C2));692/// iff C1 is a mask and the number of its leading zeros is equal to C2693/// into:694/// shl X, C2695static Value *foldSelectICmpAndZeroShl(const ICmpInst *Cmp, Value *TVal,696 Value *FVal,697 InstCombiner::BuilderTy &Builder) {698 CmpPredicate Pred;699 Value *AndVal;700 if (!match(Cmp, m_ICmp(Pred, m_Value(AndVal), m_Zero())))701 return nullptr;702 703 if (Pred == ICmpInst::ICMP_NE) {704 Pred = ICmpInst::ICMP_EQ;705 std::swap(TVal, FVal);706 }707 708 Value *X;709 const APInt *C2, *C1;710 if (Pred != ICmpInst::ICMP_EQ ||711 !match(AndVal, m_And(m_Value(X), m_APInt(C1))) ||712 !match(TVal, m_Zero()) || !match(FVal, m_Shl(m_Specific(X), m_APInt(C2))))713 return nullptr;714 715 if (!C1->isMask() ||716 C1->countLeadingZeros() != static_cast<unsigned>(C2->getZExtValue()))717 return nullptr;718 719 auto *FI = dyn_cast<Instruction>(FVal);720 if (!FI)721 return nullptr;722 723 FI->setHasNoSignedWrap(false);724 FI->setHasNoUnsignedWrap(false);725 return FVal;726}727 728/// We want to turn:729/// (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1730/// (select (icmp slt x, C), ashr (X, Y), lshr (X, Y)); iff C s>= 0731/// into:732/// ashr (X, Y)733static Value *foldSelectICmpLshrAshr(const ICmpInst *IC, Value *TrueVal,734 Value *FalseVal,735 InstCombiner::BuilderTy &Builder) {736 ICmpInst::Predicate Pred = IC->getPredicate();737 Value *CmpLHS = IC->getOperand(0);738 Value *CmpRHS = IC->getOperand(1);739 if (!CmpRHS->getType()->isIntOrIntVectorTy())740 return nullptr;741 742 Value *X, *Y;743 unsigned Bitwidth = CmpRHS->getType()->getScalarSizeInBits();744 if ((Pred != ICmpInst::ICMP_SGT ||745 !match(CmpRHS, m_SpecificInt_ICMP(ICmpInst::ICMP_SGE,746 APInt::getAllOnes(Bitwidth)))) &&747 (Pred != ICmpInst::ICMP_SLT ||748 !match(CmpRHS, m_SpecificInt_ICMP(ICmpInst::ICMP_SGE,749 APInt::getZero(Bitwidth)))))750 return nullptr;751 752 // Canonicalize so that ashr is in FalseVal.753 if (Pred == ICmpInst::ICMP_SLT)754 std::swap(TrueVal, FalseVal);755 756 if (match(TrueVal, m_LShr(m_Value(X), m_Value(Y))) &&757 match(FalseVal, m_AShr(m_Specific(X), m_Specific(Y))) &&758 match(CmpLHS, m_Specific(X))) {759 const auto *Ashr = cast<Instruction>(FalseVal);760 // if lshr is not exact and ashr is, this new ashr must not be exact.761 bool IsExact = Ashr->isExact() && cast<Instruction>(TrueVal)->isExact();762 return Builder.CreateAShr(X, Y, IC->getName(), IsExact);763 }764 765 return nullptr;766}767 768/// We want to turn:769/// (select (icmp eq (and X, C1), 0), Y, (BinOp Y, C2))770/// into:771/// IF C2 u>= C1772/// (BinOp Y, (shl (and X, C1), C3))773/// ELSE774/// (BinOp Y, (lshr (and X, C1), C3))775/// iff:776/// 0 on the RHS is the identity value (i.e add, xor, shl, etc...)777/// C1 and C2 are both powers of 2778/// where:779/// IF C2 u>= C1780/// C3 = Log(C2) - Log(C1)781/// ELSE782/// C3 = Log(C1) - Log(C2)783///784/// This transform handles cases where:785/// 1. The icmp predicate is inverted786/// 2. The select operands are reversed787/// 3. The magnitude of C2 and C1 are flipped788static Value *foldSelectICmpAndBinOp(Value *CondVal, Value *TrueVal,789 Value *FalseVal, Value *V,790 const APInt &AndMask, bool CreateAnd,791 InstCombiner::BuilderTy &Builder) {792 // Only handle integer compares.793 if (!TrueVal->getType()->isIntOrIntVectorTy())794 return nullptr;795 796 unsigned C1Log = AndMask.logBase2();797 Value *Y;798 BinaryOperator *BinOp;799 const APInt *C2;800 bool NeedXor;801 if (match(FalseVal, m_BinOp(m_Specific(TrueVal), m_Power2(C2)))) {802 Y = TrueVal;803 BinOp = cast<BinaryOperator>(FalseVal);804 NeedXor = false;805 } else if (match(TrueVal, m_BinOp(m_Specific(FalseVal), m_Power2(C2)))) {806 Y = FalseVal;807 BinOp = cast<BinaryOperator>(TrueVal);808 NeedXor = true;809 } else {810 return nullptr;811 }812 813 // Check that 0 on RHS is identity value for this binop.814 auto *IdentityC =815 ConstantExpr::getBinOpIdentity(BinOp->getOpcode(), BinOp->getType(),816 /*AllowRHSConstant*/ true);817 if (IdentityC == nullptr || !IdentityC->isNullValue())818 return nullptr;819 820 unsigned C2Log = C2->logBase2();821 822 bool NeedShift = C1Log != C2Log;823 bool NeedZExtTrunc = Y->getType()->getScalarSizeInBits() !=824 V->getType()->getScalarSizeInBits();825 826 // Make sure we don't create more instructions than we save.827 if ((NeedShift + NeedXor + NeedZExtTrunc + CreateAnd) >828 (CondVal->hasOneUse() + BinOp->hasOneUse()))829 return nullptr;830 831 if (CreateAnd) {832 // Insert the AND instruction on the input to the truncate.833 V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), AndMask));834 }835 836 if (C2Log > C1Log) {837 V = Builder.CreateZExtOrTrunc(V, Y->getType());838 V = Builder.CreateShl(V, C2Log - C1Log);839 } else if (C1Log > C2Log) {840 V = Builder.CreateLShr(V, C1Log - C2Log);841 V = Builder.CreateZExtOrTrunc(V, Y->getType());842 } else843 V = Builder.CreateZExtOrTrunc(V, Y->getType());844 845 if (NeedXor)846 V = Builder.CreateXor(V, *C2);847 848 auto *Res = Builder.CreateBinOp(BinOp->getOpcode(), Y, V);849 if (auto *BO = dyn_cast<BinaryOperator>(Res))850 BO->copyIRFlags(BinOp);851 return Res;852}853 854/// Canonicalize a set or clear of a masked set of constant bits to855/// select-of-constants form.856static Instruction *foldSetClearBits(SelectInst &Sel,857 InstCombiner::BuilderTy &Builder) {858 Value *Cond = Sel.getCondition();859 Value *T = Sel.getTrueValue();860 Value *F = Sel.getFalseValue();861 Type *Ty = Sel.getType();862 Value *X;863 const APInt *NotC, *C;864 865 // Cond ? (X & ~C) : (X | C) --> (X & ~C) | (Cond ? 0 : C)866 if (match(T, m_And(m_Value(X), m_APInt(NotC))) &&867 match(F, m_OneUse(m_Or(m_Specific(X), m_APInt(C)))) && *NotC == ~(*C)) {868 Constant *Zero = ConstantInt::getNullValue(Ty);869 Constant *OrC = ConstantInt::get(Ty, *C);870 Value *NewSel = Builder.CreateSelect(Cond, Zero, OrC, "masksel", &Sel);871 return BinaryOperator::CreateOr(T, NewSel);872 }873 874 // Cond ? (X | C) : (X & ~C) --> (X & ~C) | (Cond ? C : 0)875 if (match(F, m_And(m_Value(X), m_APInt(NotC))) &&876 match(T, m_OneUse(m_Or(m_Specific(X), m_APInt(C)))) && *NotC == ~(*C)) {877 Constant *Zero = ConstantInt::getNullValue(Ty);878 Constant *OrC = ConstantInt::get(Ty, *C);879 Value *NewSel = Builder.CreateSelect(Cond, OrC, Zero, "masksel", &Sel);880 return BinaryOperator::CreateOr(F, NewSel);881 }882 883 return nullptr;884}885 886// select (x == 0), 0, x * y --> freeze(y) * x887// select (y == 0), 0, x * y --> freeze(x) * y888// select (x == 0), undef, x * y --> freeze(y) * x889// select (x == undef), 0, x * y --> freeze(y) * x890// Usage of mul instead of 0 will make the result more poisonous,891// so the operand that was not checked in the condition should be frozen.892// The latter folding is applied only when a constant compared with x is893// is a vector consisting of 0 and undefs. If a constant compared with x894// is a scalar undefined value or undefined vector then an expression895// should be already folded into a constant.896//897// This also holds all operations such that Op(0) == 0898// e.g. Shl, Umin, etc899static Instruction *foldSelectZeroOrFixedOp(SelectInst &SI,900 InstCombinerImpl &IC) {901 auto *CondVal = SI.getCondition();902 auto *TrueVal = SI.getTrueValue();903 auto *FalseVal = SI.getFalseValue();904 Value *X, *Y;905 CmpPredicate Predicate;906 907 // Assuming that constant compared with zero is not undef (but it may be908 // a vector with some undef elements). Otherwise (when a constant is undef)909 // the select expression should be already simplified.910 if (!match(CondVal, m_ICmp(Predicate, m_Value(X), m_Zero())) ||911 !ICmpInst::isEquality(Predicate))912 return nullptr;913 914 if (Predicate == ICmpInst::ICMP_NE)915 std::swap(TrueVal, FalseVal);916 917 // Check that TrueVal is a constant instead of matching it with m_Zero()918 // to handle the case when it is a scalar undef value or a vector containing919 // non-zero elements that are masked by undef elements in the compare920 // constant.921 auto *TrueValC = dyn_cast<Constant>(TrueVal);922 if (TrueValC == nullptr || !isa<Instruction>(FalseVal))923 return nullptr;924 925 bool FreezeY;926 if (match(FalseVal, m_c_Mul(m_Specific(X), m_Value(Y))) ||927 match(FalseVal, m_c_And(m_Specific(X), m_Value(Y))) ||928 match(FalseVal, m_FShl(m_Specific(X), m_Specific(X), m_Value(Y))) ||929 match(FalseVal, m_FShr(m_Specific(X), m_Specific(X), m_Value(Y))) ||930 match(FalseVal,931 m_c_Intrinsic<Intrinsic::umin>(m_Specific(X), m_Value(Y)))) {932 FreezeY = true;933 } else if (match(FalseVal, m_IDiv(m_Specific(X), m_Value(Y))) ||934 match(FalseVal, m_IRem(m_Specific(X), m_Value(Y)))) {935 FreezeY = false;936 } else {937 return nullptr;938 }939 940 auto *ZeroC = cast<Constant>(cast<Instruction>(CondVal)->getOperand(1));941 auto *MergedC = Constant::mergeUndefsWith(TrueValC, ZeroC);942 // If X is compared with 0 then TrueVal could be either zero or undef.943 // m_Zero match vectors containing some undef elements, but for scalars944 // m_Undef should be used explicitly.945 if (!match(MergedC, m_Zero()) && !match(MergedC, m_Undef()))946 return nullptr;947 948 auto *FalseValI = cast<Instruction>(FalseVal);949 if (FreezeY) {950 auto *FrY = IC.InsertNewInstBefore(new FreezeInst(Y, Y->getName() + ".fr"),951 FalseValI->getIterator());952 IC.replaceOperand(*FalseValI,953 FalseValI->getOperand(0) == Y954 ? 0955 : (FalseValI->getOperand(1) == Y ? 1 : 2),956 FrY);957 }958 return IC.replaceInstUsesWith(SI, FalseValI);959}960 961/// Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b).962/// There are 8 commuted/swapped variants of this pattern.963static Value *canonicalizeSaturatedSubtract(const ICmpInst *ICI,964 const Value *TrueVal,965 const Value *FalseVal,966 InstCombiner::BuilderTy &Builder) {967 ICmpInst::Predicate Pred = ICI->getPredicate();968 Value *A = ICI->getOperand(0);969 Value *B = ICI->getOperand(1);970 971 // (b > a) ? 0 : a - b -> (b <= a) ? a - b : 0972 // (a == 0) ? 0 : a - 1 -> (a != 0) ? a - 1 : 0973 if (match(TrueVal, m_Zero())) {974 Pred = ICmpInst::getInversePredicate(Pred);975 std::swap(TrueVal, FalseVal);976 }977 978 if (!match(FalseVal, m_Zero()))979 return nullptr;980 981 // ugt 0 is canonicalized to ne 0 and requires special handling982 // (a != 0) ? a + -1 : 0 -> usub.sat(a, 1)983 if (Pred == ICmpInst::ICMP_NE) {984 if (match(B, m_Zero()) && match(TrueVal, m_Add(m_Specific(A), m_AllOnes())))985 return Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, A,986 ConstantInt::get(A->getType(), 1));987 return nullptr;988 }989 990 if (!ICmpInst::isUnsigned(Pred))991 return nullptr;992 993 if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_ULT) {994 // (b < a) ? a - b : 0 -> (a > b) ? a - b : 0995 std::swap(A, B);996 Pred = ICmpInst::getSwappedPredicate(Pred);997 }998 999 assert((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_UGT) &&1000 "Unexpected isUnsigned predicate!");1001 1002 // Ensure the sub is of the form:1003 // (a > b) ? a - b : 0 -> usub.sat(a, b)1004 // (a > b) ? b - a : 0 -> -usub.sat(a, b)1005 // Checking for both a-b and a+(-b) as a constant.1006 bool IsNegative = false;1007 const APInt *C;1008 if (match(TrueVal, m_Sub(m_Specific(B), m_Specific(A))) ||1009 (match(A, m_APInt(C)) &&1010 match(TrueVal, m_Add(m_Specific(B), m_SpecificInt(-*C)))))1011 IsNegative = true;1012 else if (!match(TrueVal, m_Sub(m_Specific(A), m_Specific(B))) &&1013 !(match(B, m_APInt(C)) &&1014 match(TrueVal, m_Add(m_Specific(A), m_SpecificInt(-*C)))))1015 return nullptr;1016 1017 // If we are adding a negate and the sub and icmp are used anywhere else, we1018 // would end up with more instructions.1019 if (IsNegative && !TrueVal->hasOneUse() && !ICI->hasOneUse())1020 return nullptr;1021 1022 // (a > b) ? a - b : 0 -> usub.sat(a, b)1023 // (a > b) ? b - a : 0 -> -usub.sat(a, b)1024 Value *Result = Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, A, B);1025 if (IsNegative)1026 Result = Builder.CreateNeg(Result);1027 return Result;1028}1029 1030static Value *1031canonicalizeSaturatedAddUnsigned(ICmpInst *Cmp, Value *TVal, Value *FVal,1032 InstCombiner::BuilderTy &Builder) {1033 1034 // Match unsigned saturated add with constant.1035 Value *Cmp0 = Cmp->getOperand(0);1036 Value *Cmp1 = Cmp->getOperand(1);1037 ICmpInst::Predicate Pred = Cmp->getPredicate();1038 Value *X;1039 const APInt *C;1040 1041 // Match unsigned saturated add of 2 variables with an unnecessary 'not'.1042 // There are 8 commuted variants.1043 // Canonicalize -1 (saturated result) to true value of the select.1044 if (match(FVal, m_AllOnes())) {1045 std::swap(TVal, FVal);1046 Pred = CmpInst::getInversePredicate(Pred);1047 }1048 if (!match(TVal, m_AllOnes()))1049 return nullptr;1050 1051 // uge -1 is canonicalized to eq -1 and requires special handling1052 // (a == -1) ? -1 : a + 1 -> uadd.sat(a, 1)1053 if (Pred == ICmpInst::ICMP_EQ) {1054 if (match(FVal, m_Add(m_Specific(Cmp0), m_One())) &&1055 match(Cmp1, m_AllOnes())) {1056 return Builder.CreateBinaryIntrinsic(1057 Intrinsic::uadd_sat, Cmp0, ConstantInt::get(Cmp0->getType(), 1));1058 }1059 return nullptr;1060 }1061 1062 if ((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_UGT) &&1063 match(FVal, m_Add(m_Specific(Cmp0), m_APIntAllowPoison(C))) &&1064 match(Cmp1, m_SpecificIntAllowPoison(~*C))) {1065 // (X u> ~C) ? -1 : (X + C) --> uadd.sat(X, C)1066 // (X u>= ~C)? -1 : (X + C) --> uadd.sat(X, C)1067 return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, Cmp0,1068 ConstantInt::get(Cmp0->getType(), *C));1069 }1070 1071 // Negative one does not work here because X u> -1 ? -1, X + -1 is not a1072 // saturated add.1073 if (Pred == ICmpInst::ICMP_UGT &&1074 match(FVal, m_Add(m_Specific(Cmp0), m_APIntAllowPoison(C))) &&1075 match(Cmp1, m_SpecificIntAllowPoison(~*C - 1)) && !C->isAllOnes()) {1076 // (X u> ~C - 1) ? -1 : (X + C) --> uadd.sat(X, C)1077 return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, Cmp0,1078 ConstantInt::get(Cmp0->getType(), *C));1079 }1080 1081 // Zero does not work here because X u>= 0 ? -1 : X -> is always -1, which is1082 // not a saturated add.1083 if (Pred == ICmpInst::ICMP_UGE &&1084 match(FVal, m_Add(m_Specific(Cmp0), m_APIntAllowPoison(C))) &&1085 match(Cmp1, m_SpecificIntAllowPoison(-*C)) && !C->isZero()) {1086 // (X u >= -C) ? -1 : (X + C) --> uadd.sat(X, C)1087 return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, Cmp0,1088 ConstantInt::get(Cmp0->getType(), *C));1089 }1090 1091 // Canonicalize predicate to less-than or less-or-equal-than.1092 if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) {1093 std::swap(Cmp0, Cmp1);1094 Pred = CmpInst::getSwappedPredicate(Pred);1095 }1096 if (Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_ULE)1097 return nullptr;1098 1099 // Match unsigned saturated add of 2 variables with an unnecessary 'not'.1100 // Strictness of the comparison is irrelevant.1101 Value *Y;1102 if (match(Cmp0, m_Not(m_Value(X))) &&1103 match(FVal, m_c_Add(m_Specific(X), m_Value(Y))) && Y == Cmp1) {1104 // (~X u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)1105 // (~X u< Y) ? -1 : (Y + X) --> uadd.sat(X, Y)1106 return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, X, Y);1107 }1108 // The 'not' op may be included in the sum but not the compare.1109 // Strictness of the comparison is irrelevant.1110 X = Cmp0;1111 Y = Cmp1;1112 if (match(FVal, m_c_Add(m_NotForbidPoison(m_Specific(X)), m_Specific(Y)))) {1113 // (X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y)1114 // (X u< Y) ? -1 : (Y + ~X) --> uadd.sat(Y, ~X)1115 BinaryOperator *BO = cast<BinaryOperator>(FVal);1116 return Builder.CreateBinaryIntrinsic(1117 Intrinsic::uadd_sat, BO->getOperand(0), BO->getOperand(1));1118 }1119 // The overflow may be detected via the add wrapping round.1120 // This is only valid for strict comparison!1121 if (Pred == ICmpInst::ICMP_ULT &&1122 match(Cmp0, m_c_Add(m_Specific(Cmp1), m_Value(Y))) &&1123 match(FVal, m_c_Add(m_Specific(Cmp1), m_Specific(Y)))) {1124 // ((X + Y) u< X) ? -1 : (X + Y) --> uadd.sat(X, Y)1125 // ((X + Y) u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)1126 return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, Cmp1, Y);1127 }1128 1129 return nullptr;1130}1131 1132static Value *canonicalizeSaturatedAddSigned(ICmpInst *Cmp, Value *TVal,1133 Value *FVal,1134 InstCombiner::BuilderTy &Builder) {1135 // Match saturated add with constant.1136 Value *Cmp0 = Cmp->getOperand(0);1137 Value *Cmp1 = Cmp->getOperand(1);1138 ICmpInst::Predicate Pred = Cmp->getPredicate();1139 Value *X;1140 const APInt *C;1141 1142 // Canonicalize INT_MAX to true value of the select.1143 if (match(FVal, m_MaxSignedValue())) {1144 std::swap(TVal, FVal);1145 Pred = CmpInst::getInversePredicate(Pred);1146 }1147 1148 if (!match(TVal, m_MaxSignedValue()))1149 return nullptr;1150 1151 // sge maximum signed value is canonicalized to eq maximum signed value and1152 // requires special handling (a == INT_MAX) ? INT_MAX : a + 1 -> sadd.sat(a,1153 // 1)1154 if (Pred == ICmpInst::ICMP_EQ) {1155 if (match(FVal, m_Add(m_Specific(Cmp0), m_One())) && Cmp1 == TVal) {1156 return Builder.CreateBinaryIntrinsic(1157 Intrinsic::sadd_sat, Cmp0, ConstantInt::get(Cmp0->getType(), 1));1158 }1159 return nullptr;1160 }1161 1162 // (X > Y) ? INT_MAX : (X + C) --> sadd.sat(X, C)1163 // (X >= Y) ? INT_MAX : (X + C) --> sadd.sat(X, C)1164 // where Y is INT_MAX - C or INT_MAX - C - 1, and C > 01165 if ((Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE) &&1166 isa<Constant>(Cmp1) &&1167 match(FVal, m_Add(m_Specific(Cmp0), m_StrictlyPositive(C)))) {1168 APInt IntMax =1169 APInt::getSignedMaxValue(Cmp1->getType()->getScalarSizeInBits());1170 1171 // For SGE, try to flip to SGT to normalize the comparison constant.1172 if (Pred == ICmpInst::ICMP_SGE) {1173 if (auto Flipped = getFlippedStrictnessPredicateAndConstant(1174 Pred, cast<Constant>(Cmp1))) {1175 Pred = Flipped->first;1176 Cmp1 = Flipped->second;1177 }1178 }1179 1180 // Check the pattern: X > INT_MAX - C or X > INT_MAX - C - 11181 if (Pred == ICmpInst::ICMP_SGT &&1182 (match(Cmp1, m_SpecificIntAllowPoison(IntMax - *C)) ||1183 match(Cmp1, m_SpecificIntAllowPoison(IntMax - *C - 1))))1184 return Builder.CreateBinaryIntrinsic(1185 Intrinsic::sadd_sat, Cmp0, ConstantInt::get(Cmp0->getType(), *C));1186 }1187 1188 // Canonicalize predicate to less-than or less-or-equal-than.1189 if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE) {1190 std::swap(Cmp0, Cmp1);1191 Pred = CmpInst::getSwappedPredicate(Pred);1192 }1193 1194 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SLE)1195 return nullptr;1196 1197 if (match(Cmp0, m_NSWSub(m_MaxSignedValue(), m_Value(X))) &&1198 match(FVal, m_c_Add(m_Specific(X), m_Specific(Cmp1)))) {1199 // (INT_MAX - X s< Y) ? INT_MAX : (X + Y) --> sadd.sat(X, Y)1200 // (INT_MAX - X s< Y) ? INT_MAX : (Y + X) --> sadd.sat(X, Y)1201 return Builder.CreateBinaryIntrinsic(Intrinsic::sadd_sat, X, Cmp1);1202 }1203 1204 return nullptr;1205}1206 1207static Value *canonicalizeSaturatedAdd(ICmpInst *Cmp, Value *TVal, Value *FVal,1208 InstCombiner::BuilderTy &Builder) {1209 if (!Cmp->hasOneUse())1210 return nullptr;1211 1212 if (Value *V = canonicalizeSaturatedAddUnsigned(Cmp, TVal, FVal, Builder))1213 return V;1214 1215 if (Value *V = canonicalizeSaturatedAddSigned(Cmp, TVal, FVal, Builder))1216 return V;1217 1218 return nullptr;1219}1220 1221/// Try to match patterns with select and subtract as absolute difference.1222static Value *foldAbsDiff(ICmpInst *Cmp, Value *TVal, Value *FVal,1223 InstCombiner::BuilderTy &Builder) {1224 auto *TI = dyn_cast<Instruction>(TVal);1225 auto *FI = dyn_cast<Instruction>(FVal);1226 if (!TI || !FI)1227 return nullptr;1228 1229 // Normalize predicate to gt/lt rather than ge/le.1230 ICmpInst::Predicate Pred = Cmp->getStrictPredicate();1231 Value *A = Cmp->getOperand(0);1232 Value *B = Cmp->getOperand(1);1233 1234 // Normalize "A - B" as the true value of the select.1235 if (match(FI, m_Sub(m_Specific(A), m_Specific(B)))) {1236 std::swap(FI, TI);1237 Pred = ICmpInst::getSwappedPredicate(Pred);1238 }1239 1240 // With any pair of no-wrap subtracts:1241 // (A > B) ? (A - B) : (B - A) --> abs(A - B)1242 if (Pred == CmpInst::ICMP_SGT &&1243 match(TI, m_Sub(m_Specific(A), m_Specific(B))) &&1244 match(FI, m_Sub(m_Specific(B), m_Specific(A))) &&1245 (TI->hasNoSignedWrap() || TI->hasNoUnsignedWrap()) &&1246 (FI->hasNoSignedWrap() || FI->hasNoUnsignedWrap())) {1247 // The remaining subtract is not "nuw" any more.1248 // If there's one use of the subtract (no other use than the use we are1249 // about to replace), then we know that the sub is "nsw" in this context1250 // even if it was only "nuw" before. If there's another use, then we can't1251 // add "nsw" to the existing instruction because it may not be safe in the1252 // other user's context.1253 TI->setHasNoUnsignedWrap(false);1254 if (!TI->hasNoSignedWrap())1255 TI->setHasNoSignedWrap(TI->hasOneUse());1256 return Builder.CreateBinaryIntrinsic(Intrinsic::abs, TI, Builder.getTrue());1257 }1258 1259 // Match: (A > B) ? (A - B) : (0 - (A - B)) --> abs(A - B)1260 if (Pred == CmpInst::ICMP_SGT &&1261 match(TI, m_NSWSub(m_Specific(A), m_Specific(B))) &&1262 match(FI, m_Neg(m_Specific(TI)))) {1263 return Builder.CreateBinaryIntrinsic(Intrinsic::abs, TI,1264 Builder.getFalse());1265 }1266 1267 // Match: (A < B) ? (0 - (A - B)) : (A - B) --> abs(A - B)1268 if (Pred == CmpInst::ICMP_SLT &&1269 match(FI, m_NSWSub(m_Specific(A), m_Specific(B))) &&1270 match(TI, m_Neg(m_Specific(FI)))) {1271 return Builder.CreateBinaryIntrinsic(Intrinsic::abs, FI,1272 Builder.getFalse());1273 }1274 1275 // Match: (A > B) ? (0 - (B - A)) : (B - A) --> abs(B - A)1276 if (Pred == CmpInst::ICMP_SGT &&1277 match(FI, m_NSWSub(m_Specific(B), m_Specific(A))) &&1278 match(TI, m_Neg(m_Specific(FI)))) {1279 return Builder.CreateBinaryIntrinsic(Intrinsic::abs, FI,1280 Builder.getFalse());1281 }1282 1283 // Match: (A < B) ? (B - A) : (0 - (B - A)) --> abs(B - A)1284 if (Pred == CmpInst::ICMP_SLT &&1285 match(TI, m_NSWSub(m_Specific(B), m_Specific(A))) &&1286 match(FI, m_Neg(m_Specific(TI)))) {1287 return Builder.CreateBinaryIntrinsic(Intrinsic::abs, TI,1288 Builder.getFalse());1289 }1290 1291 return nullptr;1292}1293 1294/// Fold the following code sequence:1295/// \code1296/// int a = ctlz(x & -x);1297// x ? 31 - a : a;1298// // or1299// x ? 31 - a : 32;1300/// \code1301///1302/// into:1303/// cttz(x)1304static Instruction *foldSelectCtlzToCttz(ICmpInst *ICI, Value *TrueVal,1305 Value *FalseVal,1306 InstCombiner::BuilderTy &Builder) {1307 unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits();1308 if (!ICI->isEquality() || !match(ICI->getOperand(1), m_Zero()))1309 return nullptr;1310 1311 if (ICI->getPredicate() == ICmpInst::ICMP_NE)1312 std::swap(TrueVal, FalseVal);1313 1314 Value *Ctlz;1315 if (!match(FalseVal,1316 m_Xor(m_Value(Ctlz), m_SpecificInt(BitWidth - 1))))1317 return nullptr;1318 1319 if (!match(Ctlz, m_Intrinsic<Intrinsic::ctlz>()))1320 return nullptr;1321 1322 if (TrueVal != Ctlz && !match(TrueVal, m_SpecificInt(BitWidth)))1323 return nullptr;1324 1325 Value *X = ICI->getOperand(0);1326 auto *II = cast<IntrinsicInst>(Ctlz);1327 if (!match(II->getOperand(0), m_c_And(m_Specific(X), m_Neg(m_Specific(X)))))1328 return nullptr;1329 1330 Function *F = Intrinsic::getOrInsertDeclaration(1331 II->getModule(), Intrinsic::cttz, II->getType());1332 return CallInst::Create(F, {X, II->getArgOperand(1)});1333}1334 1335/// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single1336/// call to cttz/ctlz with flag 'is_zero_poison' cleared.1337///1338/// For example, we can fold the following code sequence:1339/// \code1340/// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)1341/// %1 = icmp ne i32 %x, 01342/// %2 = select i1 %1, i32 %0, i32 321343/// \code1344///1345/// into:1346/// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)1347static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal,1348 InstCombinerImpl &IC) {1349 ICmpInst::Predicate Pred = ICI->getPredicate();1350 Value *CmpLHS = ICI->getOperand(0);1351 Value *CmpRHS = ICI->getOperand(1);1352 1353 // Check if the select condition compares a value for equality.1354 if (!ICI->isEquality())1355 return nullptr;1356 1357 Value *SelectArg = FalseVal;1358 Value *ValueOnZero = TrueVal;1359 if (Pred == ICmpInst::ICMP_NE)1360 std::swap(SelectArg, ValueOnZero);1361 1362 // Skip zero extend/truncate.1363 Value *Count = nullptr;1364 if (!match(SelectArg, m_ZExt(m_Value(Count))) &&1365 !match(SelectArg, m_Trunc(m_Value(Count))))1366 Count = SelectArg;1367 1368 // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the1369 // input to the cttz/ctlz is used as LHS for the compare instruction.1370 Value *X;1371 if (!match(Count, m_Intrinsic<Intrinsic::cttz>(m_Value(X))) &&1372 !match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Value(X))))1373 return nullptr;1374 1375 // (X == 0) ? BitWidth : ctz(X)1376 // (X == -1) ? BitWidth : ctz(~X)1377 // (X == Y) ? BitWidth : ctz(X ^ Y)1378 if ((X != CmpLHS || !match(CmpRHS, m_Zero())) &&1379 (!match(X, m_Not(m_Specific(CmpLHS))) || !match(CmpRHS, m_AllOnes())) &&1380 !match(X, m_c_Xor(m_Specific(CmpLHS), m_Specific(CmpRHS))))1381 return nullptr;1382 1383 IntrinsicInst *II = cast<IntrinsicInst>(Count);1384 1385 // Check if the value propagated on zero is a constant number equal to the1386 // sizeof in bits of 'Count'.1387 unsigned SizeOfInBits = Count->getType()->getScalarSizeInBits();1388 if (match(ValueOnZero, m_SpecificInt(SizeOfInBits))) {1389 // Explicitly clear the 'is_zero_poison' flag. It's always valid to go from1390 // true to false on this flag, so we can replace it for all users.1391 II->setArgOperand(1, ConstantInt::getFalse(II->getContext()));1392 // A range annotation on the intrinsic may no longer be valid.1393 II->dropPoisonGeneratingAnnotations();1394 IC.addToWorklist(II);1395 return SelectArg;1396 }1397 1398 // The ValueOnZero is not the bitwidth. But if the cttz/ctlz (and optional1399 // zext/trunc) have one use (ending at the select), the cttz/ctlz result will1400 // not be used if the input is zero. Relax to 'zero is poison' for that case.1401 if (II->hasOneUse() && SelectArg->hasOneUse() &&1402 !match(II->getArgOperand(1), m_One())) {1403 II->setArgOperand(1, ConstantInt::getTrue(II->getContext()));1404 // noundef attribute on the intrinsic may no longer be valid.1405 II->dropUBImplyingAttrsAndMetadata();1406 IC.addToWorklist(II);1407 }1408 1409 return nullptr;1410}1411 1412static Value *canonicalizeSPF(ICmpInst &Cmp, Value *TrueVal, Value *FalseVal,1413 InstCombinerImpl &IC) {1414 Value *LHS, *RHS;1415 // TODO: What to do with pointer min/max patterns?1416 if (!TrueVal->getType()->isIntOrIntVectorTy())1417 return nullptr;1418 1419 SelectPatternFlavor SPF =1420 matchDecomposedSelectPattern(&Cmp, TrueVal, FalseVal, LHS, RHS).Flavor;1421 if (SPF == SelectPatternFlavor::SPF_ABS ||1422 SPF == SelectPatternFlavor::SPF_NABS) {1423 if (!Cmp.hasOneUse() && !RHS->hasOneUse())1424 return nullptr; // TODO: Relax this restriction.1425 1426 // Note that NSW flag can only be propagated for normal, non-negated abs!1427 bool IntMinIsPoison = SPF == SelectPatternFlavor::SPF_ABS &&1428 match(RHS, m_NSWNeg(m_Specific(LHS)));1429 Constant *IntMinIsPoisonC =1430 ConstantInt::get(Type::getInt1Ty(Cmp.getContext()), IntMinIsPoison);1431 Value *Abs =1432 IC.Builder.CreateBinaryIntrinsic(Intrinsic::abs, LHS, IntMinIsPoisonC);1433 1434 if (SPF == SelectPatternFlavor::SPF_NABS)1435 return IC.Builder.CreateNeg(Abs); // Always without NSW flag!1436 return Abs;1437 }1438 1439 if (SelectPatternResult::isMinOrMax(SPF)) {1440 Intrinsic::ID IntrinsicID = getMinMaxIntrinsic(SPF);1441 return IC.Builder.CreateBinaryIntrinsic(IntrinsicID, LHS, RHS);1442 }1443 1444 return nullptr;1445}1446 1447bool InstCombinerImpl::replaceInInstruction(Value *V, Value *Old, Value *New,1448 unsigned Depth) {1449 // Conservatively limit replacement to two instructions upwards.1450 if (Depth == 2)1451 return false;1452 1453 assert(!isa<Constant>(Old) && "Only replace non-constant values");1454 1455 auto *I = dyn_cast<Instruction>(V);1456 if (!I || !I->hasOneUse() ||1457 !isSafeToSpeculativelyExecuteWithVariableReplaced(I))1458 return false;1459 1460 // Forbid potentially lane-crossing instructions.1461 if (Old->getType()->isVectorTy() && !isNotCrossLaneOperation(I))1462 return false;1463 1464 bool Changed = false;1465 for (Use &U : I->operands()) {1466 if (U == Old) {1467 replaceUse(U, New);1468 Worklist.add(I);1469 Changed = true;1470 } else {1471 Changed |= replaceInInstruction(U, Old, New, Depth + 1);1472 }1473 }1474 return Changed;1475}1476 1477/// If we have a select with an equality comparison, then we know the value in1478/// one of the arms of the select. See if substituting this value into an arm1479/// and simplifying the result yields the same value as the other arm.1480///1481/// To make this transform safe, we must drop poison-generating flags1482/// (nsw, etc) if we simplified to a binop because the select may be guarding1483/// that poison from propagating. If the existing binop already had no1484/// poison-generating flags, then this transform can be done by instsimplify.1485///1486/// Consider:1487/// %cmp = icmp eq i32 %x, 21474836471488/// %add = add nsw i32 %x, 11489/// %sel = select i1 %cmp, i32 -2147483648, i32 %add1490///1491/// We can't replace %sel with %add unless we strip away the flags.1492/// TODO: Wrapping flags could be preserved in some cases with better analysis.1493Instruction *InstCombinerImpl::foldSelectValueEquivalence(SelectInst &Sel,1494 CmpInst &Cmp) {1495 // Canonicalize the pattern to an equivalence on the predicate by swapping the1496 // select operands.1497 Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();1498 bool Swapped = false;1499 if (Cmp.isEquivalence(/*Invert=*/true)) {1500 std::swap(TrueVal, FalseVal);1501 Swapped = true;1502 } else if (!Cmp.isEquivalence()) {1503 return nullptr;1504 }1505 1506 Value *CmpLHS = Cmp.getOperand(0), *CmpRHS = Cmp.getOperand(1);1507 auto ReplaceOldOpWithNewOp = [&](Value *OldOp,1508 Value *NewOp) -> Instruction * {1509 // In X == Y ? f(X) : Z, try to evaluate f(Y) and replace the operand.1510 // Take care to avoid replacing X == Y ? X : Z with X == Y ? Y : Z, as that1511 // would lead to an infinite replacement cycle.1512 // If we will be able to evaluate f(Y) to a constant, we can allow undef,1513 // otherwise Y cannot be undef as we might pick different values for undef1514 // in the cmp and in f(Y).1515 if (TrueVal == OldOp && (isa<Constant>(OldOp) || !isa<Constant>(NewOp)))1516 return nullptr;1517 1518 if (Value *V = simplifyWithOpReplaced(TrueVal, OldOp, NewOp, SQ,1519 /* AllowRefinement=*/true)) {1520 // Need some guarantees about the new simplified op to ensure we don't inf1521 // loop.1522 // If we simplify to a constant, replace if we aren't creating new undef.1523 if (match(V, m_ImmConstant()) &&1524 isGuaranteedNotToBeUndef(V, SQ.AC, &Sel, &DT))1525 return replaceOperand(Sel, Swapped ? 2 : 1, V);1526 1527 // If NewOp is a constant and OldOp is not replace iff NewOp doesn't1528 // contain and undef elements.1529 // Make sure that V is always simpler than TrueVal, otherwise we might1530 // end up in an infinite loop.1531 if (match(NewOp, m_ImmConstant()) ||1532 (isa<Instruction>(TrueVal) &&1533 is_contained(cast<Instruction>(TrueVal)->operands(), V))) {1534 if (isGuaranteedNotToBeUndef(NewOp, SQ.AC, &Sel, &DT))1535 return replaceOperand(Sel, Swapped ? 2 : 1, V);1536 return nullptr;1537 }1538 }1539 1540 // Even if TrueVal does not simplify, we can directly replace a use of1541 // CmpLHS with CmpRHS, as long as the instruction is not used anywhere1542 // else and is safe to speculatively execute (we may end up executing it1543 // with different operands, which should not cause side-effects or trigger1544 // undefined behavior). Only do this if CmpRHS is a constant, as1545 // profitability is not clear for other cases.1546 if (OldOp == CmpLHS && match(NewOp, m_ImmConstant()) &&1547 !match(OldOp, m_Constant()) &&1548 isGuaranteedNotToBeUndef(NewOp, SQ.AC, &Sel, &DT))1549 if (replaceInInstruction(TrueVal, OldOp, NewOp))1550 return &Sel;1551 return nullptr;1552 };1553 1554 bool CanReplaceCmpLHSWithRHS = canReplacePointersIfEqual(CmpLHS, CmpRHS, DL);1555 if (CanReplaceCmpLHSWithRHS) {1556 if (Instruction *R = ReplaceOldOpWithNewOp(CmpLHS, CmpRHS))1557 return R;1558 }1559 bool CanReplaceCmpRHSWithLHS = canReplacePointersIfEqual(CmpRHS, CmpLHS, DL);1560 if (CanReplaceCmpRHSWithLHS) {1561 if (Instruction *R = ReplaceOldOpWithNewOp(CmpRHS, CmpLHS))1562 return R;1563 }1564 1565 auto *FalseInst = dyn_cast<Instruction>(FalseVal);1566 if (!FalseInst)1567 return nullptr;1568 1569 // InstSimplify already performed this fold if it was possible subject to1570 // current poison-generating flags. Check whether dropping poison-generating1571 // flags enables the transform.1572 1573 // Try each equivalence substitution possibility.1574 // We have an 'EQ' comparison, so the select's false value will propagate.1575 // Example:1576 // (X == 42) ? 43 : (X + 1) --> (X == 42) ? (X + 1) : (X + 1) --> X + 11577 SmallVector<Instruction *> DropFlags;1578 if ((CanReplaceCmpLHSWithRHS &&1579 simplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, SQ,1580 /* AllowRefinement */ false,1581 &DropFlags) == TrueVal) ||1582 (CanReplaceCmpRHSWithLHS &&1583 simplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, SQ,1584 /* AllowRefinement */ false,1585 &DropFlags) == TrueVal)) {1586 for (Instruction *I : DropFlags) {1587 I->dropPoisonGeneratingAnnotations();1588 Worklist.add(I);1589 }1590 1591 return replaceInstUsesWith(Sel, FalseVal);1592 }1593 1594 return nullptr;1595}1596 1597/// Fold the following code sequence:1598/// \code1599/// %XeqZ = icmp eq i64 %X, %Z1600/// %YeqZ = icmp eq i64 %Y, %Z1601/// %XeqY = icmp eq i64 %X, %Y1602/// %not.YeqZ = xor i1 %YeqZ, true1603/// %and = select i1 %not.YeqZ, i1 %XeqY, i1 false1604/// %equal = select i1 %XeqZ, i1 %YeqZ, i1 %and1605/// \code1606///1607/// into:1608/// %equal = icmp eq i64 %X, %Y1609Instruction *InstCombinerImpl::foldSelectEqualityTest(SelectInst &Sel) {1610 Value *X, *Y, *Z;1611 Value *XeqY, *XeqZ = Sel.getCondition(), *YeqZ = Sel.getTrueValue();1612 1613 if (!match(XeqZ, m_SpecificICmp(ICmpInst::ICMP_EQ, m_Value(X), m_Value(Z))))1614 return nullptr;1615 1616 if (!match(YeqZ,1617 m_c_SpecificICmp(ICmpInst::ICMP_EQ, m_Value(Y), m_Specific(Z))))1618 std::swap(X, Z);1619 1620 if (!match(YeqZ,1621 m_c_SpecificICmp(ICmpInst::ICMP_EQ, m_Value(Y), m_Specific(Z))))1622 return nullptr;1623 1624 if (!match(Sel.getFalseValue(),1625 m_c_LogicalAnd(m_Not(m_Specific(YeqZ)), m_Value(XeqY))))1626 return nullptr;1627 1628 if (!match(XeqY,1629 m_c_SpecificICmp(ICmpInst::ICMP_EQ, m_Specific(X), m_Specific(Y))))1630 return nullptr;1631 1632 cast<ICmpInst>(XeqY)->setSameSign(false);1633 return replaceInstUsesWith(Sel, XeqY);1634}1635 1636// See if this is a pattern like:1637// %old_cmp1 = icmp slt i32 %x, C21638// %old_replacement = select i1 %old_cmp1, i32 %target_low, i32 %target_high1639// %old_x_offseted = add i32 %x, C11640// %old_cmp0 = icmp ult i32 %old_x_offseted, C01641// %r = select i1 %old_cmp0, i32 %x, i32 %old_replacement1642// This can be rewritten as more canonical pattern:1643// %new_cmp1 = icmp slt i32 %x, -C11644// %new_cmp2 = icmp sge i32 %x, C0-C11645// %new_clamped_low = select i1 %new_cmp1, i32 %target_low, i32 %x1646// %r = select i1 %new_cmp2, i32 %target_high, i32 %new_clamped_low1647// Iff -C1 s<= C2 s<= C0-C11648// Also ULT predicate can also be UGT iff C0 != -1 (+invert result)1649// SLT predicate can also be SGT iff C2 != INT_MAX (+invert res.)1650static Value *canonicalizeClampLike(SelectInst &Sel0, ICmpInst &Cmp0,1651 InstCombiner::BuilderTy &Builder,1652 InstCombiner &IC) {1653 Value *X = Sel0.getTrueValue();1654 Value *Sel1 = Sel0.getFalseValue();1655 1656 // First match the condition of the outermost select.1657 // Said condition must be one-use.1658 if (!Cmp0.hasOneUse())1659 return nullptr;1660 ICmpInst::Predicate Pred0 = Cmp0.getPredicate();1661 Value *Cmp00 = Cmp0.getOperand(0);1662 Constant *C0;1663 if (!match(Cmp0.getOperand(1),1664 m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C0))))1665 return nullptr;1666 1667 if (!isa<SelectInst>(Sel1)) {1668 Pred0 = ICmpInst::getInversePredicate(Pred0);1669 std::swap(X, Sel1);1670 }1671 1672 // Canonicalize Cmp0 into ult or uge.1673 // FIXME: we shouldn't care about lanes that are 'undef' in the end?1674 switch (Pred0) {1675 case ICmpInst::Predicate::ICMP_ULT:1676 case ICmpInst::Predicate::ICMP_UGE:1677 // Although icmp ult %x, 0 is an unusual thing to try and should generally1678 // have been simplified, it does not verify with undef inputs so ensure we1679 // are not in a strange state.1680 if (!match(C0, m_SpecificInt_ICMP(1681 ICmpInst::Predicate::ICMP_NE,1682 APInt::getZero(C0->getType()->getScalarSizeInBits()))))1683 return nullptr;1684 break; // Great!1685 case ICmpInst::Predicate::ICMP_ULE:1686 case ICmpInst::Predicate::ICMP_UGT:1687 // We want to canonicalize it to 'ult' or 'uge', so we'll need to increment1688 // C0, which again means it must not have any all-ones elements.1689 if (!match(C0,1690 m_SpecificInt_ICMP(1691 ICmpInst::Predicate::ICMP_NE,1692 APInt::getAllOnes(C0->getType()->getScalarSizeInBits()))))1693 return nullptr; // Can't do, have all-ones element[s].1694 Pred0 = ICmpInst::getFlippedStrictnessPredicate(Pred0);1695 C0 = InstCombiner::AddOne(C0);1696 break;1697 default:1698 return nullptr; // Unknown predicate.1699 }1700 1701 // Now that we've canonicalized the ICmp, we know the X we expect;1702 // the select in other hand should be one-use.1703 if (!Sel1->hasOneUse())1704 return nullptr;1705 1706 // If the types do not match, look through any truncs to the underlying1707 // instruction.1708 if (Cmp00->getType() != X->getType() && X->hasOneUse())1709 match(X, m_TruncOrSelf(m_Value(X)));1710 1711 // We now can finish matching the condition of the outermost select:1712 // it should either be the X itself, or an addition of some constant to X.1713 Constant *C1;1714 if (Cmp00 == X)1715 C1 = ConstantInt::getNullValue(X->getType());1716 else if (!match(Cmp00,1717 m_Add(m_Specific(X),1718 m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C1)))))1719 return nullptr;1720 1721 Value *Cmp1;1722 CmpPredicate Pred1;1723 Constant *C2;1724 Value *ReplacementLow, *ReplacementHigh;1725 if (!match(Sel1, m_Select(m_Value(Cmp1), m_Value(ReplacementLow),1726 m_Value(ReplacementHigh))) ||1727 !match(Cmp1,1728 m_ICmp(Pred1, m_Specific(X),1729 m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C2)))))1730 return nullptr;1731 1732 if (!Cmp1->hasOneUse() && (Cmp00 == X || !Cmp00->hasOneUse()))1733 return nullptr; // Not enough one-use instructions for the fold.1734 // FIXME: this restriction could be relaxed if Cmp1 can be reused as one of1735 // two comparisons we'll need to build.1736 1737 // Canonicalize Cmp1 into the form we expect.1738 // FIXME: we shouldn't care about lanes that are 'undef' in the end?1739 switch (Pred1) {1740 case ICmpInst::Predicate::ICMP_SLT:1741 break;1742 case ICmpInst::Predicate::ICMP_SLE:1743 // We'd have to increment C2 by one, and for that it must not have signed1744 // max element, but then it would have been canonicalized to 'slt' before1745 // we get here. So we can't do anything useful with 'sle'.1746 return nullptr;1747 case ICmpInst::Predicate::ICMP_SGT:1748 // We want to canonicalize it to 'slt', so we'll need to increment C2,1749 // which again means it must not have any signed max elements.1750 if (!match(C2,1751 m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE,1752 APInt::getSignedMaxValue(1753 C2->getType()->getScalarSizeInBits()))))1754 return nullptr; // Can't do, have signed max element[s].1755 C2 = InstCombiner::AddOne(C2);1756 [[fallthrough]];1757 case ICmpInst::Predicate::ICMP_SGE:1758 // Also non-canonical, but here we don't need to change C2,1759 // so we don't have any restrictions on C2, so we can just handle it.1760 Pred1 = ICmpInst::Predicate::ICMP_SLT;1761 std::swap(ReplacementLow, ReplacementHigh);1762 break;1763 default:1764 return nullptr; // Unknown predicate.1765 }1766 assert(Pred1 == ICmpInst::Predicate::ICMP_SLT &&1767 "Unexpected predicate type.");1768 1769 // The thresholds of this clamp-like pattern.1770 auto *ThresholdLowIncl = ConstantExpr::getNeg(C1);1771 auto *ThresholdHighExcl = ConstantExpr::getSub(C0, C1);1772 1773 assert((Pred0 == ICmpInst::Predicate::ICMP_ULT ||1774 Pred0 == ICmpInst::Predicate::ICMP_UGE) &&1775 "Unexpected predicate type.");1776 if (Pred0 == ICmpInst::Predicate::ICMP_UGE)1777 std::swap(ThresholdLowIncl, ThresholdHighExcl);1778 1779 // The fold has a precondition 1: C2 s>= ThresholdLow1780 auto *Precond1 = ConstantFoldCompareInstOperands(1781 ICmpInst::Predicate::ICMP_SGE, C2, ThresholdLowIncl, IC.getDataLayout());1782 if (!Precond1 || !match(Precond1, m_One()))1783 return nullptr;1784 // The fold has a precondition 2: C2 s<= ThresholdHigh1785 auto *Precond2 = ConstantFoldCompareInstOperands(1786 ICmpInst::Predicate::ICMP_SLE, C2, ThresholdHighExcl, IC.getDataLayout());1787 if (!Precond2 || !match(Precond2, m_One()))1788 return nullptr;1789 1790 // If we are matching from a truncated input, we need to sext the1791 // ReplacementLow and ReplacementHigh values. Only do the transform if they1792 // are free to extend due to being constants.1793 if (X->getType() != Sel0.getType()) {1794 Constant *LowC, *HighC;1795 if (!match(ReplacementLow, m_ImmConstant(LowC)) ||1796 !match(ReplacementHigh, m_ImmConstant(HighC)))1797 return nullptr;1798 const DataLayout &DL = Sel0.getDataLayout();1799 ReplacementLow =1800 ConstantFoldCastOperand(Instruction::SExt, LowC, X->getType(), DL);1801 ReplacementHigh =1802 ConstantFoldCastOperand(Instruction::SExt, HighC, X->getType(), DL);1803 assert(ReplacementLow && ReplacementHigh &&1804 "Constant folding of ImmConstant cannot fail");1805 }1806 1807 // All good, finally emit the new pattern.1808 Value *ShouldReplaceLow = Builder.CreateICmpSLT(X, ThresholdLowIncl);1809 Value *ShouldReplaceHigh = Builder.CreateICmpSGE(X, ThresholdHighExcl);1810 Value *MaybeReplacedLow =1811 Builder.CreateSelect(ShouldReplaceLow, ReplacementLow, X);1812 1813 // Create the final select. If we looked through a truncate above, we will1814 // need to retruncate the result.1815 Value *MaybeReplacedHigh = Builder.CreateSelect(1816 ShouldReplaceHigh, ReplacementHigh, MaybeReplacedLow);1817 return Builder.CreateTrunc(MaybeReplacedHigh, Sel0.getType());1818}1819 1820// If we have1821// %cmp = icmp [canonical predicate] i32 %x, C01822// %r = select i1 %cmp, i32 %y, i32 C11823// Where C0 != C1 and %x may be different from %y, see if the constant that we1824// will have if we flip the strictness of the predicate (i.e. without changing1825// the result) is identical to the C1 in select. If it matches we can change1826// original comparison to one with swapped predicate, reuse the constant,1827// and swap the hands of select.1828static Instruction *1829tryToReuseConstantFromSelectInComparison(SelectInst &Sel, ICmpInst &Cmp,1830 InstCombinerImpl &IC) {1831 CmpPredicate Pred;1832 Value *X;1833 Constant *C0;1834 if (!match(&Cmp, m_OneUse(m_ICmp(1835 Pred, m_Value(X),1836 m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C0))))))1837 return nullptr;1838 1839 // If comparison predicate is non-relational, we won't be able to do anything.1840 if (ICmpInst::isEquality(Pred))1841 return nullptr;1842 1843 // If comparison predicate is non-canonical, then we certainly won't be able1844 // to make it canonical; canonicalizeCmpWithConstant() already tried.1845 if (!InstCombiner::isCanonicalPredicate(Pred))1846 return nullptr;1847 1848 // If the [input] type of comparison and select type are different, lets abort1849 // for now. We could try to compare constants with trunc/[zs]ext though.1850 if (C0->getType() != Sel.getType())1851 return nullptr;1852 1853 // ULT with 'add' of a constant is canonical. See foldICmpAddConstant().1854 // FIXME: Are there more magic icmp predicate+constant pairs we must avoid?1855 // Or should we just abandon this transform entirely?1856 if (Pred == CmpInst::ICMP_ULT && match(X, m_Add(m_Value(), m_Constant())))1857 return nullptr;1858 1859 1860 Value *SelVal0, *SelVal1; // We do not care which one is from where.1861 match(&Sel, m_Select(m_Value(), m_Value(SelVal0), m_Value(SelVal1)));1862 // At least one of these values we are selecting between must be a constant1863 // else we'll never succeed.1864 if (!match(SelVal0, m_AnyIntegralConstant()) &&1865 !match(SelVal1, m_AnyIntegralConstant()))1866 return nullptr;1867 1868 // Does this constant C match any of the `select` values?1869 auto MatchesSelectValue = [SelVal0, SelVal1](Constant *C) {1870 return C->isElementWiseEqual(SelVal0) || C->isElementWiseEqual(SelVal1);1871 };1872 1873 // If C0 *already* matches true/false value of select, we are done.1874 if (MatchesSelectValue(C0))1875 return nullptr;1876 1877 // Check the constant we'd have with flipped-strictness predicate.1878 auto FlippedStrictness = getFlippedStrictnessPredicateAndConstant(Pred, C0);1879 if (!FlippedStrictness)1880 return nullptr;1881 1882 // If said constant doesn't match either, then there is no hope,1883 if (!MatchesSelectValue(FlippedStrictness->second))1884 return nullptr;1885 1886 // It matched! Lets insert the new comparison just before select.1887 InstCombiner::BuilderTy::InsertPointGuard Guard(IC.Builder);1888 IC.Builder.SetInsertPoint(&Sel);1889 1890 Pred = ICmpInst::getSwappedPredicate(Pred); // Yes, swapped.1891 Value *NewCmp = IC.Builder.CreateICmp(Pred, X, FlippedStrictness->second,1892 Cmp.getName() + ".inv");1893 IC.replaceOperand(Sel, 0, NewCmp);1894 Sel.swapValues();1895 Sel.swapProfMetadata();1896 1897 return &Sel;1898}1899 1900static Instruction *foldSelectZeroOrOnes(ICmpInst *Cmp, Value *TVal,1901 Value *FVal,1902 InstCombiner::BuilderTy &Builder) {1903 if (!Cmp->hasOneUse())1904 return nullptr;1905 1906 const APInt *CmpC;1907 if (!match(Cmp->getOperand(1), m_APIntAllowPoison(CmpC)))1908 return nullptr;1909 1910 // (X u< 2) ? -X : -1 --> sext (X != 0)1911 Value *X = Cmp->getOperand(0);1912 if (Cmp->getPredicate() == ICmpInst::ICMP_ULT && *CmpC == 2 &&1913 match(TVal, m_Neg(m_Specific(X))) && match(FVal, m_AllOnes()))1914 return new SExtInst(Builder.CreateIsNotNull(X), TVal->getType());1915 1916 // (X u> 1) ? -1 : -X --> sext (X != 0)1917 if (Cmp->getPredicate() == ICmpInst::ICMP_UGT && *CmpC == 1 &&1918 match(FVal, m_Neg(m_Specific(X))) && match(TVal, m_AllOnes()))1919 return new SExtInst(Builder.CreateIsNotNull(X), TVal->getType());1920 1921 return nullptr;1922}1923 1924static Value *foldSelectInstWithICmpConst(SelectInst &SI, ICmpInst *ICI,1925 InstCombiner::BuilderTy &Builder) {1926 const APInt *CmpC;1927 Value *V;1928 CmpPredicate Pred;1929 if (!match(ICI, m_ICmp(Pred, m_Value(V), m_APInt(CmpC))))1930 return nullptr;1931 1932 // Match clamp away from min/max value as a max/min operation.1933 Value *TVal = SI.getTrueValue();1934 Value *FVal = SI.getFalseValue();1935 if (Pred == ICmpInst::ICMP_EQ && V == FVal) {1936 // (V == UMIN) ? UMIN+1 : V --> umax(V, UMIN+1)1937 if (CmpC->isMinValue() && match(TVal, m_SpecificInt(*CmpC + 1)))1938 return Builder.CreateBinaryIntrinsic(Intrinsic::umax, V, TVal);1939 // (V == UMAX) ? UMAX-1 : V --> umin(V, UMAX-1)1940 if (CmpC->isMaxValue() && match(TVal, m_SpecificInt(*CmpC - 1)))1941 return Builder.CreateBinaryIntrinsic(Intrinsic::umin, V, TVal);1942 // (V == SMIN) ? SMIN+1 : V --> smax(V, SMIN+1)1943 if (CmpC->isMinSignedValue() && match(TVal, m_SpecificInt(*CmpC + 1)))1944 return Builder.CreateBinaryIntrinsic(Intrinsic::smax, V, TVal);1945 // (V == SMAX) ? SMAX-1 : V --> smin(V, SMAX-1)1946 if (CmpC->isMaxSignedValue() && match(TVal, m_SpecificInt(*CmpC - 1)))1947 return Builder.CreateBinaryIntrinsic(Intrinsic::smin, V, TVal);1948 }1949 1950 // Fold icmp(X) ? f(X) : C to f(X) when f(X) is guaranteed to be equal to C1951 // for all X in the exact range of the inverse predicate.1952 Instruction *Op;1953 const APInt *C;1954 CmpInst::Predicate CPred;1955 if (match(&SI, m_Select(m_Specific(ICI), m_APInt(C), m_Instruction(Op))))1956 CPred = ICI->getPredicate();1957 else if (match(&SI, m_Select(m_Specific(ICI), m_Instruction(Op), m_APInt(C))))1958 CPred = ICI->getInversePredicate();1959 else1960 return nullptr;1961 1962 ConstantRange InvDomCR = ConstantRange::makeExactICmpRegion(CPred, *CmpC);1963 const APInt *OpC;1964 if (match(Op, m_BinOp(m_Specific(V), m_APInt(OpC)))) {1965 ConstantRange R = InvDomCR.binaryOp(1966 static_cast<Instruction::BinaryOps>(Op->getOpcode()), *OpC);1967 if (R == *C) {1968 Op->dropPoisonGeneratingFlags();1969 return Op;1970 }1971 }1972 if (auto *MMI = dyn_cast<MinMaxIntrinsic>(Op);1973 MMI && MMI->getLHS() == V && match(MMI->getRHS(), m_APInt(OpC))) {1974 ConstantRange R = ConstantRange::intrinsic(MMI->getIntrinsicID(),1975 {InvDomCR, ConstantRange(*OpC)});1976 if (R == *C) {1977 MMI->dropPoisonGeneratingAnnotations();1978 return MMI;1979 }1980 }1981 1982 return nullptr;1983}1984 1985/// `A == MIN_INT ? B != MIN_INT : A < B` --> `A < B`1986/// `A == MAX_INT ? B != MAX_INT : A > B` --> `A > B`1987static Instruction *foldSelectWithExtremeEqCond(Value *CmpLHS, Value *CmpRHS,1988 Value *TrueVal,1989 Value *FalseVal) {1990 Type *Ty = CmpLHS->getType();1991 1992 if (Ty->isPtrOrPtrVectorTy())1993 return nullptr;1994 1995 CmpPredicate Pred;1996 Value *B;1997 1998 if (!match(FalseVal, m_c_ICmp(Pred, m_Specific(CmpLHS), m_Value(B))))1999 return nullptr;2000 2001 Value *TValRHS;2002 if (!match(TrueVal, m_SpecificICmp(ICmpInst::ICMP_NE, m_Specific(B),2003 m_Value(TValRHS))))2004 return nullptr;2005 2006 APInt C;2007 unsigned BitWidth = Ty->getScalarSizeInBits();2008 2009 if (ICmpInst::isLT(Pred)) {2010 C = CmpInst::isSigned(Pred) ? APInt::getSignedMinValue(BitWidth)2011 : APInt::getMinValue(BitWidth);2012 } else if (ICmpInst::isGT(Pred)) {2013 C = CmpInst::isSigned(Pred) ? APInt::getSignedMaxValue(BitWidth)2014 : APInt::getMaxValue(BitWidth);2015 } else {2016 return nullptr;2017 }2018 2019 if (!match(CmpRHS, m_SpecificInt(C)) || !match(TValRHS, m_SpecificInt(C)))2020 return nullptr;2021 2022 return new ICmpInst(Pred, CmpLHS, B);2023}2024 2025static Instruction *foldSelectICmpEq(SelectInst &SI, ICmpInst *ICI,2026 InstCombinerImpl &IC) {2027 ICmpInst::Predicate Pred = ICI->getPredicate();2028 if (!ICmpInst::isEquality(Pred))2029 return nullptr;2030 2031 Value *TrueVal = SI.getTrueValue();2032 Value *FalseVal = SI.getFalseValue();2033 Value *CmpLHS = ICI->getOperand(0);2034 Value *CmpRHS = ICI->getOperand(1);2035 2036 if (Pred == ICmpInst::ICMP_NE)2037 std::swap(TrueVal, FalseVal);2038 2039 if (Instruction *Res =2040 foldSelectWithExtremeEqCond(CmpLHS, CmpRHS, TrueVal, FalseVal))2041 return Res;2042 2043 return nullptr;2044}2045 2046/// Fold `X Pred C1 ? X BOp C2 : C1 BOp C2` to `min/max(X, C1) BOp C2`.2047/// This allows for better canonicalization.2048Value *InstCombinerImpl::foldSelectWithConstOpToBinOp(ICmpInst *Cmp,2049 Value *TrueVal,2050 Value *FalseVal) {2051 Constant *C1, *C2, *C3;2052 Value *X;2053 CmpPredicate Predicate;2054 2055 if (!match(Cmp, m_ICmp(Predicate, m_Value(X), m_Constant(C1))))2056 return nullptr;2057 2058 if (!ICmpInst::isRelational(Predicate))2059 return nullptr;2060 2061 if (match(TrueVal, m_Constant())) {2062 std::swap(FalseVal, TrueVal);2063 Predicate = ICmpInst::getInversePredicate(Predicate);2064 }2065 2066 if (!match(FalseVal, m_Constant(C3)) || !TrueVal->hasOneUse())2067 return nullptr;2068 2069 bool IsIntrinsic;2070 unsigned Opcode;2071 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(TrueVal)) {2072 Opcode = BOp->getOpcode();2073 IsIntrinsic = false;2074 2075 // This fold causes some regressions and is primarily intended for2076 // add and sub. So we early exit for div and rem to minimize the2077 // regressions.2078 if (Instruction::isIntDivRem(Opcode))2079 return nullptr;2080 2081 if (!match(BOp, m_BinOp(m_Specific(X), m_Constant(C2))))2082 return nullptr;2083 2084 } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(TrueVal)) {2085 if (!match(II, m_MaxOrMin(m_Specific(X), m_Constant(C2))))2086 return nullptr;2087 Opcode = II->getIntrinsicID();2088 IsIntrinsic = true;2089 } else {2090 return nullptr;2091 }2092 2093 Value *RHS;2094 SelectPatternFlavor SPF;2095 const DataLayout &DL = Cmp->getDataLayout();2096 auto Flipped = getFlippedStrictnessPredicateAndConstant(Predicate, C1);2097 2098 auto FoldBinaryOpOrIntrinsic = [&](Constant *LHS, Constant *RHS) {2099 return IsIntrinsic ? ConstantFoldBinaryIntrinsic(Opcode, LHS, RHS,2100 LHS->getType(), nullptr)2101 : ConstantFoldBinaryOpOperands(Opcode, LHS, RHS, DL);2102 };2103 2104 if (C3 == FoldBinaryOpOrIntrinsic(C1, C2)) {2105 SPF = getSelectPattern(Predicate).Flavor;2106 RHS = C1;2107 } else if (Flipped && C3 == FoldBinaryOpOrIntrinsic(Flipped->second, C2)) {2108 SPF = getSelectPattern(Flipped->first).Flavor;2109 RHS = Flipped->second;2110 } else {2111 return nullptr;2112 }2113 2114 Intrinsic::ID MinMaxID = getMinMaxIntrinsic(SPF);2115 Value *MinMax = Builder.CreateBinaryIntrinsic(MinMaxID, X, RHS);2116 if (IsIntrinsic)2117 return Builder.CreateBinaryIntrinsic(Opcode, MinMax, C2);2118 2119 const auto BinOpc = Instruction::BinaryOps(Opcode);2120 Value *BinOp = Builder.CreateBinOp(BinOpc, MinMax, C2);2121 2122 // If we can attach no-wrap flags to the new instruction, do so if the2123 // old instruction had them and C1 BinOp C2 does not overflow.2124 if (Instruction *BinOpInst = dyn_cast<Instruction>(BinOp)) {2125 if (BinOpc == Instruction::Add || BinOpc == Instruction::Sub ||2126 BinOpc == Instruction::Mul) {2127 Instruction *OldBinOp = cast<BinaryOperator>(TrueVal);2128 if (OldBinOp->hasNoSignedWrap() &&2129 willNotOverflow(BinOpc, RHS, C2, *BinOpInst, /*IsSigned=*/true))2130 BinOpInst->setHasNoSignedWrap();2131 if (OldBinOp->hasNoUnsignedWrap() &&2132 willNotOverflow(BinOpc, RHS, C2, *BinOpInst, /*IsSigned=*/false))2133 BinOpInst->setHasNoUnsignedWrap();2134 }2135 }2136 return BinOp;2137}2138 2139/// Folds:2140/// %a_sub = call @llvm.usub.sat(x, IntConst1)2141/// %b_sub = call @llvm.usub.sat(y, IntConst2)2142/// %or = or %a_sub, %b_sub2143/// %cmp = icmp eq %or, 02144/// %sel = select %cmp, 0, MostSignificantBit2145/// into:2146/// %a_sub' = usub.sat(x, IntConst1 - MostSignificantBit)2147/// %b_sub' = usub.sat(y, IntConst2 - MostSignificantBit)2148/// %or = or %a_sub', %b_sub'2149/// %and = and %or, MostSignificantBit2150/// Likewise, for vector arguments as well.2151static Instruction *foldICmpUSubSatWithAndForMostSignificantBitCmp(2152 SelectInst &SI, ICmpInst *ICI, InstCombiner::BuilderTy &Builder) {2153 if (!SI.hasOneUse() || !ICI->hasOneUse())2154 return nullptr;2155 CmpPredicate Pred;2156 Value *A, *B;2157 const APInt *Constant1, *Constant2;2158 if (!match(SI.getCondition(),2159 m_ICmp(Pred,2160 m_OneUse(m_Or(m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(2161 m_Value(A), m_APInt(Constant1))),2162 m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(2163 m_Value(B), m_APInt(Constant2))))),2164 m_Zero())))2165 return nullptr;2166 2167 Value *TrueVal = SI.getTrueValue();2168 Value *FalseVal = SI.getFalseValue();2169 if (!(Pred == ICmpInst::ICMP_EQ &&2170 (match(TrueVal, m_Zero()) && match(FalseVal, m_SignMask()))) ||2171 (Pred == ICmpInst::ICMP_NE &&2172 (match(TrueVal, m_SignMask()) && match(FalseVal, m_Zero()))))2173 return nullptr;2174 2175 auto *Ty = A->getType();2176 unsigned BW = Constant1->getBitWidth();2177 APInt MostSignificantBit = APInt::getSignMask(BW);2178 2179 // Anything over MSB is negative2180 if (Constant1->isNonNegative() || Constant2->isNonNegative())2181 return nullptr;2182 2183 APInt AdjAP1 = *Constant1 - MostSignificantBit + 1;2184 APInt AdjAP2 = *Constant2 - MostSignificantBit + 1;2185 2186 auto *Adj1 = ConstantInt::get(Ty, AdjAP1);2187 auto *Adj2 = ConstantInt::get(Ty, AdjAP2);2188 2189 Value *NewA = Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, A, Adj1);2190 Value *NewB = Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, B, Adj2);2191 Value *Or = Builder.CreateOr(NewA, NewB);2192 Constant *MSBConst = ConstantInt::get(Ty, MostSignificantBit);2193 return BinaryOperator::CreateAnd(Or, MSBConst);2194}2195 2196/// Visit a SelectInst that has an ICmpInst as its first operand.2197Instruction *InstCombinerImpl::foldSelectInstWithICmp(SelectInst &SI,2198 ICmpInst *ICI) {2199 if (Value *V =2200 canonicalizeSPF(*ICI, SI.getTrueValue(), SI.getFalseValue(), *this))2201 return replaceInstUsesWith(SI, V);2202 2203 if (Value *V = foldSelectInstWithICmpConst(SI, ICI, Builder))2204 return replaceInstUsesWith(SI, V);2205 2206 if (Value *V = canonicalizeClampLike(SI, *ICI, Builder, *this))2207 return replaceInstUsesWith(SI, V);2208 2209 if (Instruction *NewSel =2210 tryToReuseConstantFromSelectInComparison(SI, *ICI, *this))2211 return NewSel;2212 if (Instruction *Folded =2213 foldICmpUSubSatWithAndForMostSignificantBitCmp(SI, ICI, Builder))2214 return Folded;2215 2216 // NOTE: if we wanted to, this is where to detect integer MIN/MAX2217 bool Changed = false;2218 Value *TrueVal = SI.getTrueValue();2219 Value *FalseVal = SI.getFalseValue();2220 ICmpInst::Predicate Pred = ICI->getPredicate();2221 Value *CmpLHS = ICI->getOperand(0);2222 Value *CmpRHS = ICI->getOperand(1);2223 2224 if (Instruction *NewSel = foldSelectICmpEq(SI, ICI, *this))2225 return NewSel;2226 2227 // Canonicalize a signbit condition to use zero constant by swapping:2228 // (CmpLHS > -1) ? TV : FV --> (CmpLHS < 0) ? FV : TV2229 // To avoid conflicts (infinite loops) with other canonicalizations, this is2230 // not applied with any constant select arm.2231 if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes()) &&2232 !match(TrueVal, m_Constant()) && !match(FalseVal, m_Constant()) &&2233 ICI->hasOneUse()) {2234 InstCombiner::BuilderTy::InsertPointGuard Guard(Builder);2235 Builder.SetInsertPoint(&SI);2236 Value *IsNeg = Builder.CreateIsNeg(CmpLHS, ICI->getName());2237 replaceOperand(SI, 0, IsNeg);2238 SI.swapValues();2239 SI.swapProfMetadata();2240 return &SI;2241 }2242 2243 if (Value *V = foldSelectICmpMinMax(ICI, TrueVal, FalseVal, Builder, SQ))2244 return replaceInstUsesWith(SI, V);2245 2246 if (Instruction *V =2247 foldSelectICmpAndAnd(SI.getType(), ICI, TrueVal, FalseVal, Builder))2248 return V;2249 2250 if (Value *V = foldSelectICmpAndZeroShl(ICI, TrueVal, FalseVal, Builder))2251 return replaceInstUsesWith(SI, V);2252 2253 if (Instruction *V = foldSelectCtlzToCttz(ICI, TrueVal, FalseVal, Builder))2254 return V;2255 2256 if (Instruction *V = foldSelectZeroOrOnes(ICI, TrueVal, FalseVal, Builder))2257 return V;2258 2259 if (Value *V = foldSelectICmpLshrAshr(ICI, TrueVal, FalseVal, Builder))2260 return replaceInstUsesWith(SI, V);2261 2262 if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, *this))2263 return replaceInstUsesWith(SI, V);2264 2265 if (Value *V = canonicalizeSaturatedSubtract(ICI, TrueVal, FalseVal, Builder))2266 return replaceInstUsesWith(SI, V);2267 2268 if (Value *V = canonicalizeSaturatedAdd(ICI, TrueVal, FalseVal, Builder))2269 return replaceInstUsesWith(SI, V);2270 2271 if (Value *V = foldAbsDiff(ICI, TrueVal, FalseVal, Builder))2272 return replaceInstUsesWith(SI, V);2273 2274 if (Value *V = foldSelectWithConstOpToBinOp(ICI, TrueVal, FalseVal))2275 return replaceInstUsesWith(SI, V);2276 2277 return Changed ? &SI : nullptr;2278}2279 2280/// We have an SPF (e.g. a min or max) of an SPF of the form:2281/// SPF2(SPF1(A, B), C)2282Instruction *InstCombinerImpl::foldSPFofSPF(Instruction *Inner,2283 SelectPatternFlavor SPF1, Value *A,2284 Value *B, Instruction &Outer,2285 SelectPatternFlavor SPF2,2286 Value *C) {2287 if (Outer.getType() != Inner->getType())2288 return nullptr;2289 2290 if (C == A || C == B) {2291 // MAX(MAX(A, B), B) -> MAX(A, B)2292 // MIN(MIN(a, b), a) -> MIN(a, b)2293 // TODO: This could be done in instsimplify.2294 if (SPF1 == SPF2 && SelectPatternResult::isMinOrMax(SPF1))2295 return replaceInstUsesWith(Outer, Inner);2296 }2297 2298 return nullptr;2299}2300 2301/// Turn select C, (X + Y), (X - Y) --> (X + (select C, Y, (-Y))).2302/// This is even legal for FP.2303static Instruction *foldAddSubSelect(SelectInst &SI,2304 InstCombiner::BuilderTy &Builder) {2305 Value *CondVal = SI.getCondition();2306 Value *TrueVal = SI.getTrueValue();2307 Value *FalseVal = SI.getFalseValue();2308 auto *TI = dyn_cast<Instruction>(TrueVal);2309 auto *FI = dyn_cast<Instruction>(FalseVal);2310 if (!TI || !FI || !TI->hasOneUse() || !FI->hasOneUse())2311 return nullptr;2312 2313 Instruction *AddOp = nullptr, *SubOp = nullptr;2314 if ((TI->getOpcode() == Instruction::Sub &&2315 FI->getOpcode() == Instruction::Add) ||2316 (TI->getOpcode() == Instruction::FSub &&2317 FI->getOpcode() == Instruction::FAdd)) {2318 AddOp = FI;2319 SubOp = TI;2320 } else if ((FI->getOpcode() == Instruction::Sub &&2321 TI->getOpcode() == Instruction::Add) ||2322 (FI->getOpcode() == Instruction::FSub &&2323 TI->getOpcode() == Instruction::FAdd)) {2324 AddOp = TI;2325 SubOp = FI;2326 }2327 2328 if (AddOp) {2329 Value *OtherAddOp = nullptr;2330 if (SubOp->getOperand(0) == AddOp->getOperand(0)) {2331 OtherAddOp = AddOp->getOperand(1);2332 } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) {2333 OtherAddOp = AddOp->getOperand(0);2334 }2335 2336 if (OtherAddOp) {2337 // So at this point we know we have (Y -> OtherAddOp):2338 // select C, (add X, Y), (sub X, Z)2339 Value *NegVal; // Compute -Z2340 if (SI.getType()->isFPOrFPVectorTy()) {2341 NegVal = Builder.CreateFNeg(SubOp->getOperand(1));2342 if (Instruction *NegInst = dyn_cast<Instruction>(NegVal)) {2343 FastMathFlags Flags = AddOp->getFastMathFlags();2344 Flags &= SubOp->getFastMathFlags();2345 NegInst->setFastMathFlags(Flags);2346 }2347 } else {2348 NegVal = Builder.CreateNeg(SubOp->getOperand(1));2349 }2350 2351 Value *NewTrueOp = OtherAddOp;2352 Value *NewFalseOp = NegVal;2353 if (AddOp != TI)2354 std::swap(NewTrueOp, NewFalseOp);2355 Value *NewSel = Builder.CreateSelect(CondVal, NewTrueOp, NewFalseOp,2356 SI.getName() + ".p", &SI);2357 2358 if (SI.getType()->isFPOrFPVectorTy()) {2359 Instruction *RI =2360 BinaryOperator::CreateFAdd(SubOp->getOperand(0), NewSel);2361 2362 FastMathFlags Flags = AddOp->getFastMathFlags();2363 Flags &= SubOp->getFastMathFlags();2364 RI->setFastMathFlags(Flags);2365 return RI;2366 } else2367 return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel);2368 }2369 }2370 return nullptr;2371}2372 2373/// Turn X + Y overflows ? -1 : X + Y -> uadd_sat X, Y2374/// And X - Y overflows ? 0 : X - Y -> usub_sat X, Y2375/// Along with a number of patterns similar to:2376/// X + Y overflows ? (X < 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y2377/// X - Y overflows ? (X > 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y2378static Instruction *2379foldOverflowingAddSubSelect(SelectInst &SI, InstCombiner::BuilderTy &Builder) {2380 Value *CondVal = SI.getCondition();2381 Value *TrueVal = SI.getTrueValue();2382 Value *FalseVal = SI.getFalseValue();2383 2384 WithOverflowInst *II;2385 if (!match(CondVal, m_ExtractValue<1>(m_WithOverflowInst(II))) ||2386 !match(FalseVal, m_ExtractValue<0>(m_Specific(II))))2387 return nullptr;2388 2389 Value *X = II->getLHS();2390 Value *Y = II->getRHS();2391 2392 auto IsSignedSaturateLimit = [&](Value *Limit, bool IsAdd) {2393 Type *Ty = Limit->getType();2394 2395 CmpPredicate Pred;2396 Value *TrueVal, *FalseVal, *Op;2397 const APInt *C;2398 if (!match(Limit, m_Select(m_ICmp(Pred, m_Value(Op), m_APInt(C)),2399 m_Value(TrueVal), m_Value(FalseVal))))2400 return false;2401 2402 auto IsZeroOrOne = [](const APInt &C) { return C.isZero() || C.isOne(); };2403 auto IsMinMax = [&](Value *Min, Value *Max) {2404 APInt MinVal = APInt::getSignedMinValue(Ty->getScalarSizeInBits());2405 APInt MaxVal = APInt::getSignedMaxValue(Ty->getScalarSizeInBits());2406 return match(Min, m_SpecificInt(MinVal)) &&2407 match(Max, m_SpecificInt(MaxVal));2408 };2409 2410 if (Op != X && Op != Y)2411 return false;2412 2413 if (IsAdd) {2414 // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y2415 // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y2416 // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y2417 // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y2418 if (Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&2419 IsMinMax(TrueVal, FalseVal))2420 return true;2421 // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y2422 // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y2423 // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y2424 // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y2425 if (Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&2426 IsMinMax(FalseVal, TrueVal))2427 return true;2428 } else {2429 // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y2430 // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y2431 if (Op == X && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C + 1) &&2432 IsMinMax(TrueVal, FalseVal))2433 return true;2434 // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y2435 // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y2436 if (Op == X && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 2) &&2437 IsMinMax(FalseVal, TrueVal))2438 return true;2439 // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y2440 // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y2441 if (Op == Y && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&2442 IsMinMax(FalseVal, TrueVal))2443 return true;2444 // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y2445 // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y2446 if (Op == Y && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&2447 IsMinMax(TrueVal, FalseVal))2448 return true;2449 }2450 2451 return false;2452 };2453 2454 Intrinsic::ID NewIntrinsicID;2455 if (II->getIntrinsicID() == Intrinsic::uadd_with_overflow &&2456 match(TrueVal, m_AllOnes()))2457 // X + Y overflows ? -1 : X + Y -> uadd_sat X, Y2458 NewIntrinsicID = Intrinsic::uadd_sat;2459 else if (II->getIntrinsicID() == Intrinsic::usub_with_overflow &&2460 match(TrueVal, m_Zero()))2461 // X - Y overflows ? 0 : X - Y -> usub_sat X, Y2462 NewIntrinsicID = Intrinsic::usub_sat;2463 else if (II->getIntrinsicID() == Intrinsic::sadd_with_overflow &&2464 IsSignedSaturateLimit(TrueVal, /*IsAdd=*/true))2465 // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y2466 // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y2467 // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y2468 // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y2469 // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y2470 // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y2471 // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y2472 // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y2473 NewIntrinsicID = Intrinsic::sadd_sat;2474 else if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow &&2475 IsSignedSaturateLimit(TrueVal, /*IsAdd=*/false))2476 // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y2477 // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y2478 // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y2479 // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y2480 // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y2481 // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y2482 // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y2483 // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y2484 NewIntrinsicID = Intrinsic::ssub_sat;2485 else2486 return nullptr;2487 2488 Function *F = Intrinsic::getOrInsertDeclaration(SI.getModule(),2489 NewIntrinsicID, SI.getType());2490 return CallInst::Create(F, {X, Y});2491}2492 2493Instruction *InstCombinerImpl::foldSelectExtConst(SelectInst &Sel) {2494 Constant *C;2495 if (!match(Sel.getTrueValue(), m_Constant(C)) &&2496 !match(Sel.getFalseValue(), m_Constant(C)))2497 return nullptr;2498 2499 Instruction *ExtInst;2500 if (!match(Sel.getTrueValue(), m_Instruction(ExtInst)) &&2501 !match(Sel.getFalseValue(), m_Instruction(ExtInst)))2502 return nullptr;2503 2504 auto ExtOpcode = ExtInst->getOpcode();2505 if (ExtOpcode != Instruction::ZExt && ExtOpcode != Instruction::SExt)2506 return nullptr;2507 2508 // If we are extending from a boolean type or if we can create a select that2509 // has the same size operands as its condition, try to narrow the select.2510 Value *X = ExtInst->getOperand(0);2511 Type *SmallType = X->getType();2512 Value *Cond = Sel.getCondition();2513 auto *Cmp = dyn_cast<CmpInst>(Cond);2514 if (!SmallType->isIntOrIntVectorTy(1) &&2515 (!Cmp || Cmp->getOperand(0)->getType() != SmallType))2516 return nullptr;2517 2518 // If the constant is the same after truncation to the smaller type and2519 // extension to the original type, we can narrow the select.2520 Type *SelType = Sel.getType();2521 Constant *TruncC = getLosslessInvCast(C, SmallType, ExtOpcode, DL);2522 if (TruncC && ExtInst->hasOneUse()) {2523 Value *TruncCVal = cast<Value>(TruncC);2524 if (ExtInst == Sel.getFalseValue())2525 std::swap(X, TruncCVal);2526 2527 // select Cond, (ext X), C --> ext(select Cond, X, C')2528 // select Cond, C, (ext X) --> ext(select Cond, C', X)2529 Value *NewSel = Builder.CreateSelect(Cond, X, TruncCVal, "narrow", &Sel);2530 return CastInst::Create(Instruction::CastOps(ExtOpcode), NewSel, SelType);2531 }2532 2533 return nullptr;2534}2535 2536/// Try to transform a vector select with a constant condition vector into a2537/// shuffle for easier combining with other shuffles and insert/extract.2538static Instruction *canonicalizeSelectToShuffle(SelectInst &SI) {2539 Value *CondVal = SI.getCondition();2540 Constant *CondC;2541 auto *CondValTy = dyn_cast<FixedVectorType>(CondVal->getType());2542 if (!CondValTy || !match(CondVal, m_Constant(CondC)))2543 return nullptr;2544 2545 unsigned NumElts = CondValTy->getNumElements();2546 SmallVector<int, 16> Mask;2547 Mask.reserve(NumElts);2548 for (unsigned i = 0; i != NumElts; ++i) {2549 Constant *Elt = CondC->getAggregateElement(i);2550 if (!Elt)2551 return nullptr;2552 2553 if (Elt->isOneValue()) {2554 // If the select condition element is true, choose from the 1st vector.2555 Mask.push_back(i);2556 } else if (Elt->isNullValue()) {2557 // If the select condition element is false, choose from the 2nd vector.2558 Mask.push_back(i + NumElts);2559 } else if (isa<UndefValue>(Elt)) {2560 // Undef in a select condition (choose one of the operands) does not mean2561 // the same thing as undef in a shuffle mask (any value is acceptable), so2562 // give up.2563 return nullptr;2564 } else {2565 // Bail out on a constant expression.2566 return nullptr;2567 }2568 }2569 2570 return new ShuffleVectorInst(SI.getTrueValue(), SI.getFalseValue(), Mask);2571}2572 2573/// If we have a select of vectors with a scalar condition, try to convert that2574/// to a vector select by splatting the condition. A splat may get folded with2575/// other operations in IR and having all operands of a select be vector types2576/// is likely better for vector codegen.2577static Instruction *canonicalizeScalarSelectOfVecs(SelectInst &Sel,2578 InstCombinerImpl &IC) {2579 auto *Ty = dyn_cast<VectorType>(Sel.getType());2580 if (!Ty)2581 return nullptr;2582 2583 // We can replace a single-use extract with constant index.2584 Value *Cond = Sel.getCondition();2585 if (!match(Cond, m_OneUse(m_ExtractElt(m_Value(), m_ConstantInt()))))2586 return nullptr;2587 2588 // select (extelt V, Index), T, F --> select (splat V, Index), T, F2589 // Splatting the extracted condition reduces code (we could directly create a2590 // splat shuffle of the source vector to eliminate the intermediate step).2591 return IC.replaceOperand(2592 Sel, 0, IC.Builder.CreateVectorSplat(Ty->getElementCount(), Cond));2593}2594 2595/// Reuse bitcasted operands between a compare and select:2596/// select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->2597/// bitcast (select (cmp (bitcast C), (bitcast D)), (bitcast C), (bitcast D))2598static Instruction *foldSelectCmpBitcasts(SelectInst &Sel,2599 InstCombiner::BuilderTy &Builder) {2600 Value *Cond = Sel.getCondition();2601 Value *TVal = Sel.getTrueValue();2602 Value *FVal = Sel.getFalseValue();2603 2604 CmpPredicate Pred;2605 Value *A, *B;2606 if (!match(Cond, m_Cmp(Pred, m_Value(A), m_Value(B))))2607 return nullptr;2608 2609 // The select condition is a compare instruction. If the select's true/false2610 // values are already the same as the compare operands, there's nothing to do.2611 if (TVal == A || TVal == B || FVal == A || FVal == B)2612 return nullptr;2613 2614 Value *C, *D;2615 if (!match(A, m_BitCast(m_Value(C))) || !match(B, m_BitCast(m_Value(D))))2616 return nullptr;2617 2618 // select (cmp (bitcast C), (bitcast D)), (bitcast TSrc), (bitcast FSrc)2619 Value *TSrc, *FSrc;2620 if (!match(TVal, m_BitCast(m_Value(TSrc))) ||2621 !match(FVal, m_BitCast(m_Value(FSrc))))2622 return nullptr;2623 2624 // If the select true/false values are *different bitcasts* of the same source2625 // operands, make the select operands the same as the compare operands and2626 // cast the result. This is the canonical select form for min/max.2627 Value *NewSel;2628 if (TSrc == C && FSrc == D) {2629 // select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->2630 // bitcast (select (cmp A, B), A, B)2631 NewSel = Builder.CreateSelect(Cond, A, B, "", &Sel);2632 } else if (TSrc == D && FSrc == C) {2633 // select (cmp (bitcast C), (bitcast D)), (bitcast' D), (bitcast' C) -->2634 // bitcast (select (cmp A, B), B, A)2635 NewSel = Builder.CreateSelect(Cond, B, A, "", &Sel);2636 } else {2637 return nullptr;2638 }2639 return new BitCastInst(NewSel, Sel.getType());2640}2641 2642/// Try to eliminate select instructions that test the returned flag of cmpxchg2643/// instructions.2644///2645/// If a select instruction tests the returned flag of a cmpxchg instruction and2646/// selects between the returned value of the cmpxchg instruction its compare2647/// operand, the result of the select will always be equal to its false value.2648/// For example:2649///2650/// %cmpxchg = cmpxchg ptr %ptr, i64 %compare, i64 %new_value seq_cst seq_cst2651/// %val = extractvalue { i64, i1 } %cmpxchg, 02652/// %success = extractvalue { i64, i1 } %cmpxchg, 12653/// %sel = select i1 %success, i64 %compare, i64 %val2654/// ret i64 %sel2655///2656/// The returned value of the cmpxchg instruction (%val) is the original value2657/// located at %ptr prior to any update. If the cmpxchg operation succeeds, %val2658/// must have been equal to %compare. Thus, the result of the select is always2659/// equal to %val, and the code can be simplified to:2660///2661/// %cmpxchg = cmpxchg ptr %ptr, i64 %compare, i64 %new_value seq_cst seq_cst2662/// %val = extractvalue { i64, i1 } %cmpxchg, 02663/// ret i64 %val2664///2665static Value *foldSelectCmpXchg(SelectInst &SI) {2666 // A helper that determines if V is an extractvalue instruction whose2667 // aggregate operand is a cmpxchg instruction and whose single index is equal2668 // to I. If such conditions are true, the helper returns the cmpxchg2669 // instruction; otherwise, a nullptr is returned.2670 auto isExtractFromCmpXchg = [](Value *V, unsigned I) -> AtomicCmpXchgInst * {2671 auto *Extract = dyn_cast<ExtractValueInst>(V);2672 if (!Extract)2673 return nullptr;2674 if (Extract->getIndices()[0] != I)2675 return nullptr;2676 return dyn_cast<AtomicCmpXchgInst>(Extract->getAggregateOperand());2677 };2678 2679 // If the select has a single user, and this user is a select instruction that2680 // we can simplify, skip the cmpxchg simplification for now.2681 if (SI.hasOneUse())2682 if (auto *Select = dyn_cast<SelectInst>(SI.user_back()))2683 if (Select->getCondition() == SI.getCondition())2684 if (Select->getFalseValue() == SI.getTrueValue() ||2685 Select->getTrueValue() == SI.getFalseValue())2686 return nullptr;2687 2688 // Ensure the select condition is the returned flag of a cmpxchg instruction.2689 auto *CmpXchg = isExtractFromCmpXchg(SI.getCondition(), 1);2690 if (!CmpXchg)2691 return nullptr;2692 2693 // Check the true value case: The true value of the select is the returned2694 // value of the same cmpxchg used by the condition, and the false value is the2695 // cmpxchg instruction's compare operand.2696 if (auto *X = isExtractFromCmpXchg(SI.getTrueValue(), 0))2697 if (X == CmpXchg && X->getCompareOperand() == SI.getFalseValue())2698 return SI.getFalseValue();2699 2700 // Check the false value case: The false value of the select is the returned2701 // value of the same cmpxchg used by the condition, and the true value is the2702 // cmpxchg instruction's compare operand.2703 if (auto *X = isExtractFromCmpXchg(SI.getFalseValue(), 0))2704 if (X == CmpXchg && X->getCompareOperand() == SI.getTrueValue())2705 return SI.getFalseValue();2706 2707 return nullptr;2708}2709 2710/// Try to reduce a funnel/rotate pattern that includes a compare and select2711/// into a funnel shift intrinsic. Example:2712/// rotl32(a, b) --> (b == 0 ? a : ((a >> (32 - b)) | (a << b)))2713/// --> call llvm.fshl.i32(a, a, b)2714/// fshl32(a, b, c) --> (c == 0 ? a : ((b >> (32 - c)) | (a << c)))2715/// --> call llvm.fshl.i32(a, b, c)2716/// fshr32(a, b, c) --> (c == 0 ? b : ((a >> (32 - c)) | (b << c)))2717/// --> call llvm.fshr.i32(a, b, c)2718static Instruction *foldSelectFunnelShift(SelectInst &Sel,2719 InstCombiner::BuilderTy &Builder) {2720 // This must be a power-of-2 type for a bitmasking transform to be valid.2721 unsigned Width = Sel.getType()->getScalarSizeInBits();2722 if (!isPowerOf2_32(Width))2723 return nullptr;2724 2725 BinaryOperator *Or0, *Or1;2726 if (!match(Sel.getFalseValue(), m_OneUse(m_Or(m_BinOp(Or0), m_BinOp(Or1)))))2727 return nullptr;2728 2729 Value *SV0, *SV1, *SA0, *SA1;2730 if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(SV0),2731 m_ZExtOrSelf(m_Value(SA0))))) ||2732 !match(Or1, m_OneUse(m_LogicalShift(m_Value(SV1),2733 m_ZExtOrSelf(m_Value(SA1))))) ||2734 Or0->getOpcode() == Or1->getOpcode())2735 return nullptr;2736 2737 // Canonicalize to or(shl(SV0, SA0), lshr(SV1, SA1)).2738 if (Or0->getOpcode() == BinaryOperator::LShr) {2739 std::swap(Or0, Or1);2740 std::swap(SV0, SV1);2741 std::swap(SA0, SA1);2742 }2743 assert(Or0->getOpcode() == BinaryOperator::Shl &&2744 Or1->getOpcode() == BinaryOperator::LShr &&2745 "Illegal or(shift,shift) pair");2746 2747 // Check the shift amounts to see if they are an opposite pair.2748 Value *ShAmt;2749 if (match(SA1, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA0)))))2750 ShAmt = SA0;2751 else if (match(SA0, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA1)))))2752 ShAmt = SA1;2753 else2754 return nullptr;2755 2756 // We should now have this pattern:2757 // select ?, TVal, (or (shl SV0, SA0), (lshr SV1, SA1))2758 // The false value of the select must be a funnel-shift of the true value:2759 // IsFShl -> TVal must be SV0 else TVal must be SV1.2760 bool IsFshl = (ShAmt == SA0);2761 Value *TVal = Sel.getTrueValue();2762 if ((IsFshl && TVal != SV0) || (!IsFshl && TVal != SV1))2763 return nullptr;2764 2765 // Finally, see if the select is filtering out a shift-by-zero.2766 Value *Cond = Sel.getCondition();2767 if (!match(Cond, m_OneUse(m_SpecificICmp(ICmpInst::ICMP_EQ, m_Specific(ShAmt),2768 m_ZeroInt()))))2769 return nullptr;2770 2771 // If this is not a rotate then the select was blocking poison from the2772 // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.2773 if (SV0 != SV1) {2774 if (IsFshl && !llvm::isGuaranteedNotToBePoison(SV1))2775 SV1 = Builder.CreateFreeze(SV1);2776 else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(SV0))2777 SV0 = Builder.CreateFreeze(SV0);2778 }2779 2780 // This is a funnel/rotate that avoids shift-by-bitwidth UB in a suboptimal way.2781 // Convert to funnel shift intrinsic.2782 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;2783 Function *F =2784 Intrinsic::getOrInsertDeclaration(Sel.getModule(), IID, Sel.getType());2785 ShAmt = Builder.CreateZExt(ShAmt, Sel.getType());2786 return CallInst::Create(F, { SV0, SV1, ShAmt });2787}2788 2789static Instruction *foldSelectToCopysign(SelectInst &Sel,2790 InstCombiner::BuilderTy &Builder) {2791 Value *Cond = Sel.getCondition();2792 Value *TVal = Sel.getTrueValue();2793 Value *FVal = Sel.getFalseValue();2794 Type *SelType = Sel.getType();2795 2796 // Match select ?, TC, FC where the constants are equal but negated.2797 // TODO: Generalize to handle a negated variable operand?2798 const APFloat *TC, *FC;2799 if (!match(TVal, m_APFloatAllowPoison(TC)) ||2800 !match(FVal, m_APFloatAllowPoison(FC)) ||2801 !abs(*TC).bitwiseIsEqual(abs(*FC)))2802 return nullptr;2803 2804 assert(TC != FC && "Expected equal select arms to simplify");2805 2806 Value *X;2807 const APInt *C;2808 bool IsTrueIfSignSet;2809 CmpPredicate Pred;2810 if (!match(Cond, m_OneUse(m_ICmp(Pred, m_ElementWiseBitCast(m_Value(X)),2811 m_APInt(C)))) ||2812 !isSignBitCheck(Pred, *C, IsTrueIfSignSet) || X->getType() != SelType)2813 return nullptr;2814 2815 // If needed, negate the value that will be the sign argument of the copysign:2816 // (bitcast X) < 0 ? -TC : TC --> copysign(TC, X)2817 // (bitcast X) < 0 ? TC : -TC --> copysign(TC, -X)2818 // (bitcast X) >= 0 ? -TC : TC --> copysign(TC, -X)2819 // (bitcast X) >= 0 ? TC : -TC --> copysign(TC, X)2820 // Note: FMF from the select can not be propagated to the new instructions.2821 if (IsTrueIfSignSet ^ TC->isNegative())2822 X = Builder.CreateFNeg(X);2823 2824 // Canonicalize the magnitude argument as the positive constant since we do2825 // not care about its sign.2826 Value *MagArg = ConstantFP::get(SelType, abs(*TC));2827 Function *F = Intrinsic::getOrInsertDeclaration(2828 Sel.getModule(), Intrinsic::copysign, Sel.getType());2829 return CallInst::Create(F, { MagArg, X });2830}2831 2832Instruction *InstCombinerImpl::foldVectorSelect(SelectInst &Sel) {2833 if (!isa<VectorType>(Sel.getType()))2834 return nullptr;2835 2836 Value *Cond = Sel.getCondition();2837 Value *TVal = Sel.getTrueValue();2838 Value *FVal = Sel.getFalseValue();2839 Value *C, *X, *Y;2840 2841 if (match(Cond, m_VecReverse(m_Value(C)))) {2842 auto createSelReverse = [&](Value *C, Value *X, Value *Y) {2843 Value *V = Builder.CreateSelect(C, X, Y, Sel.getName(), &Sel);2844 if (auto *I = dyn_cast<Instruction>(V))2845 I->copyIRFlags(&Sel);2846 Module *M = Sel.getModule();2847 Function *F = Intrinsic::getOrInsertDeclaration(2848 M, Intrinsic::vector_reverse, V->getType());2849 return CallInst::Create(F, V);2850 };2851 2852 if (match(TVal, m_VecReverse(m_Value(X)))) {2853 // select rev(C), rev(X), rev(Y) --> rev(select C, X, Y)2854 if (match(FVal, m_VecReverse(m_Value(Y))) &&2855 (Cond->hasOneUse() || TVal->hasOneUse() || FVal->hasOneUse()))2856 return createSelReverse(C, X, Y);2857 2858 // select rev(C), rev(X), FValSplat --> rev(select C, X, FValSplat)2859 if ((Cond->hasOneUse() || TVal->hasOneUse()) && isSplatValue(FVal))2860 return createSelReverse(C, X, FVal);2861 }2862 // select rev(C), TValSplat, rev(Y) --> rev(select C, TValSplat, Y)2863 else if (isSplatValue(TVal) && match(FVal, m_VecReverse(m_Value(Y))) &&2864 (Cond->hasOneUse() || FVal->hasOneUse()))2865 return createSelReverse(C, TVal, Y);2866 }2867 2868 auto *VecTy = dyn_cast<FixedVectorType>(Sel.getType());2869 if (!VecTy)2870 return nullptr;2871 2872 unsigned NumElts = VecTy->getNumElements();2873 APInt PoisonElts(NumElts, 0);2874 APInt AllOnesEltMask(APInt::getAllOnes(NumElts));2875 if (Value *V = SimplifyDemandedVectorElts(&Sel, AllOnesEltMask, PoisonElts)) {2876 if (V != &Sel)2877 return replaceInstUsesWith(Sel, V);2878 return &Sel;2879 }2880 2881 // A select of a "select shuffle" with a common operand can be rearranged2882 // to select followed by "select shuffle". Because of poison, this only works2883 // in the case of a shuffle with no undefined mask elements.2884 ArrayRef<int> Mask;2885 if (match(TVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&2886 !is_contained(Mask, PoisonMaskElem) &&2887 cast<ShuffleVectorInst>(TVal)->isSelect()) {2888 if (X == FVal) {2889 // select Cond, (shuf_sel X, Y), X --> shuf_sel X, (select Cond, Y, X)2890 Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);2891 return new ShuffleVectorInst(X, NewSel, Mask);2892 }2893 if (Y == FVal) {2894 // select Cond, (shuf_sel X, Y), Y --> shuf_sel (select Cond, X, Y), Y2895 Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);2896 return new ShuffleVectorInst(NewSel, Y, Mask);2897 }2898 }2899 if (match(FVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&2900 !is_contained(Mask, PoisonMaskElem) &&2901 cast<ShuffleVectorInst>(FVal)->isSelect()) {2902 if (X == TVal) {2903 // select Cond, X, (shuf_sel X, Y) --> shuf_sel X, (select Cond, X, Y)2904 Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);2905 return new ShuffleVectorInst(X, NewSel, Mask);2906 }2907 if (Y == TVal) {2908 // select Cond, Y, (shuf_sel X, Y) --> shuf_sel (select Cond, Y, X), Y2909 Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);2910 return new ShuffleVectorInst(NewSel, Y, Mask);2911 }2912 }2913 2914 return nullptr;2915}2916 2917static Instruction *foldSelectToPhiImpl(SelectInst &Sel, BasicBlock *BB,2918 const DominatorTree &DT,2919 InstCombiner::BuilderTy &Builder) {2920 // Find the block's immediate dominator that ends with a conditional branch2921 // that matches select's condition (maybe inverted).2922 auto *IDomNode = DT[BB]->getIDom();2923 if (!IDomNode)2924 return nullptr;2925 BasicBlock *IDom = IDomNode->getBlock();2926 2927 Value *Cond = Sel.getCondition();2928 Value *IfTrue, *IfFalse;2929 BasicBlock *TrueSucc, *FalseSucc;2930 if (match(IDom->getTerminator(),2931 m_Br(m_Specific(Cond), m_BasicBlock(TrueSucc),2932 m_BasicBlock(FalseSucc)))) {2933 IfTrue = Sel.getTrueValue();2934 IfFalse = Sel.getFalseValue();2935 } else if (match(IDom->getTerminator(),2936 m_Br(m_Not(m_Specific(Cond)), m_BasicBlock(TrueSucc),2937 m_BasicBlock(FalseSucc)))) {2938 IfTrue = Sel.getFalseValue();2939 IfFalse = Sel.getTrueValue();2940 } else2941 return nullptr;2942 2943 // Make sure the branches are actually different.2944 if (TrueSucc == FalseSucc)2945 return nullptr;2946 2947 // We want to replace select %cond, %a, %b with a phi that takes value %a2948 // for all incoming edges that are dominated by condition `%cond == true`,2949 // and value %b for edges dominated by condition `%cond == false`. If %a2950 // or %b are also phis from the same basic block, we can go further and take2951 // their incoming values from the corresponding blocks.2952 BasicBlockEdge TrueEdge(IDom, TrueSucc);2953 BasicBlockEdge FalseEdge(IDom, FalseSucc);2954 DenseMap<BasicBlock *, Value *> Inputs;2955 for (auto *Pred : predecessors(BB)) {2956 // Check implication.2957 BasicBlockEdge Incoming(Pred, BB);2958 if (DT.dominates(TrueEdge, Incoming))2959 Inputs[Pred] = IfTrue->DoPHITranslation(BB, Pred);2960 else if (DT.dominates(FalseEdge, Incoming))2961 Inputs[Pred] = IfFalse->DoPHITranslation(BB, Pred);2962 else2963 return nullptr;2964 // Check availability.2965 if (auto *Insn = dyn_cast<Instruction>(Inputs[Pred]))2966 if (!DT.dominates(Insn, Pred->getTerminator()))2967 return nullptr;2968 }2969 2970 Builder.SetInsertPoint(BB, BB->begin());2971 auto *PN = Builder.CreatePHI(Sel.getType(), Inputs.size());2972 for (auto *Pred : predecessors(BB))2973 PN->addIncoming(Inputs[Pred], Pred);2974 PN->takeName(&Sel);2975 return PN;2976}2977 2978static Instruction *foldSelectToPhi(SelectInst &Sel, const DominatorTree &DT,2979 InstCombiner::BuilderTy &Builder) {2980 // Try to replace this select with Phi in one of these blocks.2981 SmallSetVector<BasicBlock *, 4> CandidateBlocks;2982 CandidateBlocks.insert(Sel.getParent());2983 for (Value *V : Sel.operands())2984 if (auto *I = dyn_cast<Instruction>(V))2985 CandidateBlocks.insert(I->getParent());2986 2987 for (BasicBlock *BB : CandidateBlocks)2988 if (auto *PN = foldSelectToPhiImpl(Sel, BB, DT, Builder))2989 return PN;2990 return nullptr;2991}2992 2993/// Tries to reduce a pattern that arises when calculating the remainder of the2994/// Euclidean division. When the divisor is a power of two and is guaranteed not2995/// to be negative, a signed remainder can be folded with a bitwise and.2996///2997/// (x % n) < 0 ? (x % n) + n : (x % n)2998/// -> x & (n - 1)2999static Instruction *foldSelectWithSRem(SelectInst &SI, InstCombinerImpl &IC,3000 IRBuilderBase &Builder) {3001 Value *CondVal = SI.getCondition();3002 Value *TrueVal = SI.getTrueValue();3003 Value *FalseVal = SI.getFalseValue();3004 3005 CmpPredicate Pred;3006 Value *Op, *RemRes, *Remainder;3007 const APInt *C;3008 bool TrueIfSigned = false;3009 3010 if (!(match(CondVal, m_ICmp(Pred, m_Value(RemRes), m_APInt(C))) &&3011 isSignBitCheck(Pred, *C, TrueIfSigned)))3012 return nullptr;3013 3014 // If the sign bit is not set, we have a SGE/SGT comparison, and the operands3015 // of the select are inverted.3016 if (!TrueIfSigned)3017 std::swap(TrueVal, FalseVal);3018 3019 auto FoldToBitwiseAnd = [&](Value *Remainder) -> Instruction * {3020 Value *Add = Builder.CreateAdd(3021 Remainder, Constant::getAllOnesValue(RemRes->getType()));3022 return BinaryOperator::CreateAnd(Op, Add);3023 };3024 3025 // Match the general case:3026 // %rem = srem i32 %x, %n3027 // %cnd = icmp slt i32 %rem, 03028 // %add = add i32 %rem, %n3029 // %sel = select i1 %cnd, i32 %add, i32 %rem3030 if (match(TrueVal, m_c_Add(m_Specific(RemRes), m_Value(Remainder))) &&3031 match(RemRes, m_SRem(m_Value(Op), m_Specific(Remainder))) &&3032 IC.isKnownToBeAPowerOfTwo(Remainder, /*OrZero=*/true) &&3033 FalseVal == RemRes)3034 return FoldToBitwiseAnd(Remainder);3035 3036 // Match the case where the one arm has been replaced by constant 1:3037 // %rem = srem i32 %n, 23038 // %cnd = icmp slt i32 %rem, 03039 // %sel = select i1 %cnd, i32 1, i32 %rem3040 if (match(TrueVal, m_One()) &&3041 match(RemRes, m_SRem(m_Value(Op), m_SpecificInt(2))) &&3042 FalseVal == RemRes)3043 return FoldToBitwiseAnd(ConstantInt::get(RemRes->getType(), 2));3044 3045 return nullptr;3046}3047 3048/// Given that \p CondVal is known to be \p CondIsTrue, try to simplify \p SI.3049static Value *simplifyNestedSelectsUsingImpliedCond(SelectInst &SI,3050 Value *CondVal,3051 bool CondIsTrue,3052 const DataLayout &DL) {3053 Value *InnerCondVal = SI.getCondition();3054 Value *InnerTrueVal = SI.getTrueValue();3055 Value *InnerFalseVal = SI.getFalseValue();3056 assert(CondVal->getType() == InnerCondVal->getType() &&3057 "The type of inner condition must match with the outer.");3058 if (auto Implied = isImpliedCondition(CondVal, InnerCondVal, DL, CondIsTrue))3059 return *Implied ? InnerTrueVal : InnerFalseVal;3060 return nullptr;3061}3062 3063Instruction *InstCombinerImpl::foldAndOrOfSelectUsingImpliedCond(Value *Op,3064 SelectInst &SI,3065 bool IsAnd) {3066 assert(Op->getType()->isIntOrIntVectorTy(1) &&3067 "Op must be either i1 or vector of i1.");3068 if (SI.getCondition()->getType() != Op->getType())3069 return nullptr;3070 if (Value *V = simplifyNestedSelectsUsingImpliedCond(SI, Op, IsAnd, DL)) {3071 Instruction *MDFrom = nullptr;3072 if (!ProfcheckDisableMetadataFixes)3073 MDFrom = &SI;3074 return SelectInst::Create(3075 Op, IsAnd ? V : ConstantInt::getTrue(Op->getType()),3076 IsAnd ? ConstantInt::getFalse(Op->getType()) : V, "", nullptr, MDFrom);3077 }3078 return nullptr;3079}3080 3081// Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need3082// fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work.3083static Instruction *foldSelectWithFCmpToFabs(SelectInst &SI,3084 InstCombinerImpl &IC) {3085 Value *CondVal = SI.getCondition();3086 3087 bool ChangedFMF = false;3088 for (bool Swap : {false, true}) {3089 Value *TrueVal = SI.getTrueValue();3090 Value *X = SI.getFalseValue();3091 CmpPredicate Pred;3092 3093 if (Swap)3094 std::swap(TrueVal, X);3095 3096 if (!match(CondVal, m_FCmp(Pred, m_Specific(X), m_AnyZeroFP())))3097 continue;3098 3099 // fold (X <= +/-0.0) ? (0.0 - X) : X to fabs(X), when 'Swap' is false3100 // fold (X > +/-0.0) ? X : (0.0 - X) to fabs(X), when 'Swap' is true3101 // Note: We require "nnan" for this fold because fcmp ignores the signbit3102 // of NAN, but IEEE-754 specifies the signbit of NAN values with3103 // fneg/fabs operations.3104 if (match(TrueVal, m_FSub(m_PosZeroFP(), m_Specific(X))) &&3105 (cast<FPMathOperator>(CondVal)->hasNoNaNs() || SI.hasNoNaNs() ||3106 (SI.hasOneUse() && canIgnoreSignBitOfNaN(*SI.use_begin())) ||3107 isKnownNeverNaN(X, IC.getSimplifyQuery().getWithInstruction(3108 cast<Instruction>(CondVal))))) {3109 if (!Swap && (Pred == FCmpInst::FCMP_OLE || Pred == FCmpInst::FCMP_ULE)) {3110 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);3111 return IC.replaceInstUsesWith(SI, Fabs);3112 }3113 if (Swap && (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_UGT)) {3114 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);3115 return IC.replaceInstUsesWith(SI, Fabs);3116 }3117 }3118 3119 if (!match(TrueVal, m_FNeg(m_Specific(X))))3120 return nullptr;3121 3122 // Forward-propagate nnan and ninf from the fcmp to the select.3123 // If all inputs are not those values, then the select is not either.3124 // Note: nsz is defined differently, so it may not be correct to propagate.3125 FastMathFlags FMF = cast<FPMathOperator>(CondVal)->getFastMathFlags();3126 if (FMF.noNaNs() && !SI.hasNoNaNs()) {3127 SI.setHasNoNaNs(true);3128 ChangedFMF = true;3129 }3130 if (FMF.noInfs() && !SI.hasNoInfs()) {3131 SI.setHasNoInfs(true);3132 ChangedFMF = true;3133 }3134 // Forward-propagate nnan from the fneg to the select.3135 // The nnan flag can be propagated iff fneg is selected when X is NaN.3136 if (!SI.hasNoNaNs() && cast<FPMathOperator>(TrueVal)->hasNoNaNs() &&3137 (Swap ? FCmpInst::isOrdered(Pred) : FCmpInst::isUnordered(Pred))) {3138 SI.setHasNoNaNs(true);3139 ChangedFMF = true;3140 }3141 3142 // With nsz, when 'Swap' is false:3143 // fold (X < +/-0.0) ? -X : X or (X <= +/-0.0) ? -X : X to fabs(X)3144 // fold (X > +/-0.0) ? -X : X or (X >= +/-0.0) ? -X : X to -fabs(x)3145 // when 'Swap' is true:3146 // fold (X > +/-0.0) ? X : -X or (X >= +/-0.0) ? X : -X to fabs(X)3147 // fold (X < +/-0.0) ? X : -X or (X <= +/-0.0) ? X : -X to -fabs(X)3148 //3149 // Note: We require "nnan" for this fold because fcmp ignores the signbit3150 // of NAN, but IEEE-754 specifies the signbit of NAN values with3151 // fneg/fabs operations.3152 if (!SI.hasNoSignedZeros() &&3153 (!SI.hasOneUse() || !canIgnoreSignBitOfZero(*SI.use_begin())))3154 return nullptr;3155 if (!SI.hasNoNaNs() &&3156 (!SI.hasOneUse() || !canIgnoreSignBitOfNaN(*SI.use_begin())))3157 return nullptr;3158 3159 if (Swap)3160 Pred = FCmpInst::getSwappedPredicate(Pred);3161 3162 bool IsLTOrLE = Pred == FCmpInst::FCMP_OLT || Pred == FCmpInst::FCMP_OLE ||3163 Pred == FCmpInst::FCMP_ULT || Pred == FCmpInst::FCMP_ULE;3164 bool IsGTOrGE = Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_OGE ||3165 Pred == FCmpInst::FCMP_UGT || Pred == FCmpInst::FCMP_UGE;3166 3167 if (IsLTOrLE) {3168 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);3169 return IC.replaceInstUsesWith(SI, Fabs);3170 }3171 if (IsGTOrGE) {3172 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);3173 Instruction *NewFNeg = UnaryOperator::CreateFNeg(Fabs);3174 NewFNeg->setFastMathFlags(SI.getFastMathFlags());3175 return NewFNeg;3176 }3177 }3178 3179 // Match select with (icmp slt (bitcast X to int), 0)3180 // or (icmp sgt (bitcast X to int), -1)3181 3182 for (bool Swap : {false, true}) {3183 Value *TrueVal = SI.getTrueValue();3184 Value *X = SI.getFalseValue();3185 3186 if (Swap)3187 std::swap(TrueVal, X);3188 3189 CmpPredicate Pred;3190 const APInt *C;3191 bool TrueIfSigned;3192 if (!match(CondVal,3193 m_ICmp(Pred, m_ElementWiseBitCast(m_Specific(X)), m_APInt(C))) ||3194 !isSignBitCheck(Pred, *C, TrueIfSigned))3195 continue;3196 if (!match(TrueVal, m_FNeg(m_Specific(X))))3197 return nullptr;3198 if (Swap == TrueIfSigned && !CondVal->hasOneUse() && !TrueVal->hasOneUse())3199 return nullptr;3200 3201 // Fold (IsNeg ? -X : X) or (!IsNeg ? X : -X) to fabs(X)3202 // Fold (IsNeg ? X : -X) or (!IsNeg ? -X : X) to -fabs(X)3203 Value *Fabs = IC.Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, &SI);3204 if (Swap != TrueIfSigned)3205 return IC.replaceInstUsesWith(SI, Fabs);3206 return UnaryOperator::CreateFNegFMF(Fabs, &SI);3207 }3208 3209 return ChangedFMF ? &SI : nullptr;3210}3211 3212// Match the following IR pattern:3213// %x.lowbits = and i8 %x, %lowbitmask3214// %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 03215// %x.biased = add i8 %x, %bias3216// %x.biased.highbits = and i8 %x.biased, %highbitmask3217// %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits3218// Define:3219// %alignment = add i8 %lowbitmask, 13220// Iff 1. an %alignment is a power-of-two (aka, %lowbitmask is a low bit mask)3221// and 2. %bias is equal to either %lowbitmask or %alignment,3222// and 3. %highbitmask is equal to ~%lowbitmask (aka, to -%alignment)3223// then this pattern can be transformed into:3224// %x.offset = add i8 %x, %lowbitmask3225// %x.roundedup = and i8 %x.offset, %highbitmask3226static Value *3227foldRoundUpIntegerWithPow2Alignment(SelectInst &SI,3228 InstCombiner::BuilderTy &Builder) {3229 Value *Cond = SI.getCondition();3230 Value *X = SI.getTrueValue();3231 Value *XBiasedHighBits = SI.getFalseValue();3232 3233 CmpPredicate Pred;3234 Value *XLowBits;3235 if (!match(Cond, m_ICmp(Pred, m_Value(XLowBits), m_ZeroInt())) ||3236 !ICmpInst::isEquality(Pred))3237 return nullptr;3238 3239 if (Pred == ICmpInst::Predicate::ICMP_NE)3240 std::swap(X, XBiasedHighBits);3241 3242 // FIXME: we could support non non-splats here.3243 3244 const APInt *LowBitMaskCst;3245 if (!match(XLowBits, m_And(m_Specific(X), m_APIntAllowPoison(LowBitMaskCst))))3246 return nullptr;3247 3248 // Match even if the AND and ADD are swapped.3249 const APInt *BiasCst, *HighBitMaskCst;3250 if (!match(XBiasedHighBits,3251 m_And(m_Add(m_Specific(X), m_APIntAllowPoison(BiasCst)),3252 m_APIntAllowPoison(HighBitMaskCst))) &&3253 !match(XBiasedHighBits,3254 m_Add(m_And(m_Specific(X), m_APIntAllowPoison(HighBitMaskCst)),3255 m_APIntAllowPoison(BiasCst))))3256 return nullptr;3257 3258 if (!LowBitMaskCst->isMask())3259 return nullptr;3260 3261 APInt InvertedLowBitMaskCst = ~*LowBitMaskCst;3262 if (InvertedLowBitMaskCst != *HighBitMaskCst)3263 return nullptr;3264 3265 APInt AlignmentCst = *LowBitMaskCst + 1;3266 3267 if (*BiasCst != AlignmentCst && *BiasCst != *LowBitMaskCst)3268 return nullptr;3269 3270 if (!XBiasedHighBits->hasOneUse()) {3271 // We can't directly return XBiasedHighBits if it is more poisonous.3272 if (*BiasCst == *LowBitMaskCst && impliesPoison(XBiasedHighBits, X))3273 return XBiasedHighBits;3274 return nullptr;3275 }3276 3277 // FIXME: could we preserve undef's here?3278 Type *Ty = X->getType();3279 Value *XOffset = Builder.CreateAdd(X, ConstantInt::get(Ty, *LowBitMaskCst),3280 X->getName() + ".biased");3281 Value *R = Builder.CreateAnd(XOffset, ConstantInt::get(Ty, *HighBitMaskCst));3282 R->takeName(&SI);3283 return R;3284}3285 3286namespace {3287struct DecomposedSelect {3288 Value *Cond = nullptr;3289 Value *TrueVal = nullptr;3290 Value *FalseVal = nullptr;3291};3292} // namespace3293 3294/// Folds patterns like:3295/// select c2 (select c1 a b) (select c1 b a)3296/// into:3297/// select (xor c1 c2) b a3298static Instruction *3299foldSelectOfSymmetricSelect(SelectInst &OuterSelVal,3300 InstCombiner::BuilderTy &Builder) {3301 3302 Value *OuterCond, *InnerCond, *InnerTrueVal, *InnerFalseVal;3303 if (!match(3304 &OuterSelVal,3305 m_Select(m_Value(OuterCond),3306 m_OneUse(m_Select(m_Value(InnerCond), m_Value(InnerTrueVal),3307 m_Value(InnerFalseVal))),3308 m_OneUse(m_Select(m_Deferred(InnerCond),3309 m_Deferred(InnerFalseVal),3310 m_Deferred(InnerTrueVal))))))3311 return nullptr;3312 3313 if (OuterCond->getType() != InnerCond->getType())3314 return nullptr;3315 3316 Value *Xor = Builder.CreateXor(InnerCond, OuterCond);3317 return SelectInst::Create(Xor, InnerFalseVal, InnerTrueVal);3318}3319 3320/// Look for patterns like3321/// %outer.cond = select i1 %inner.cond, i1 %alt.cond, i1 false3322/// %inner.sel = select i1 %inner.cond, i8 %inner.sel.t, i8 %inner.sel.f3323/// %outer.sel = select i1 %outer.cond, i8 %outer.sel.t, i8 %inner.sel3324/// and rewrite it as3325/// %inner.sel = select i1 %cond.alternative, i8 %sel.outer.t, i8 %sel.inner.t3326/// %sel.outer = select i1 %cond.inner, i8 %inner.sel, i8 %sel.inner.f3327static Instruction *foldNestedSelects(SelectInst &OuterSelVal,3328 InstCombiner::BuilderTy &Builder) {3329 // We must start with a `select`.3330 DecomposedSelect OuterSel;3331 match(&OuterSelVal,3332 m_Select(m_Value(OuterSel.Cond), m_Value(OuterSel.TrueVal),3333 m_Value(OuterSel.FalseVal)));3334 3335 // Canonicalize inversion of the outermost `select`'s condition.3336 if (match(OuterSel.Cond, m_Not(m_Value(OuterSel.Cond))))3337 std::swap(OuterSel.TrueVal, OuterSel.FalseVal);3338 3339 // The condition of the outermost select must be an `and`/`or`.3340 if (!match(OuterSel.Cond, m_c_LogicalOp(m_Value(), m_Value())))3341 return nullptr;3342 3343 // Depending on the logical op, inner select might be in different hand.3344 bool IsAndVariant = match(OuterSel.Cond, m_LogicalAnd());3345 Value *InnerSelVal = IsAndVariant ? OuterSel.FalseVal : OuterSel.TrueVal;3346 3347 // Profitability check - avoid increasing instruction count.3348 if (none_of(ArrayRef<Value *>({OuterSelVal.getCondition(), InnerSelVal}),3349 match_fn(m_OneUse(m_Value()))))3350 return nullptr;3351 3352 // The appropriate hand of the outermost `select` must be a select itself.3353 DecomposedSelect InnerSel;3354 if (!match(InnerSelVal,3355 m_Select(m_Value(InnerSel.Cond), m_Value(InnerSel.TrueVal),3356 m_Value(InnerSel.FalseVal))))3357 return nullptr;3358 3359 // Canonicalize inversion of the innermost `select`'s condition.3360 if (match(InnerSel.Cond, m_Not(m_Value(InnerSel.Cond))))3361 std::swap(InnerSel.TrueVal, InnerSel.FalseVal);3362 3363 Value *AltCond = nullptr;3364 auto matchOuterCond = [OuterSel, IsAndVariant, &AltCond](auto m_InnerCond) {3365 // An unsimplified select condition can match both LogicalAnd and LogicalOr3366 // (select true, true, false). Since below we assume that LogicalAnd implies3367 // InnerSel match the FVal and vice versa for LogicalOr, we can't match the3368 // alternative pattern here.3369 return IsAndVariant ? match(OuterSel.Cond,3370 m_c_LogicalAnd(m_InnerCond, m_Value(AltCond)))3371 : match(OuterSel.Cond,3372 m_c_LogicalOr(m_InnerCond, m_Value(AltCond)));3373 };3374 3375 // Finally, match the condition that was driving the outermost `select`,3376 // it should be a logical operation between the condition that was driving3377 // the innermost `select` (after accounting for the possible inversions3378 // of the condition), and some other condition.3379 if (matchOuterCond(m_Specific(InnerSel.Cond))) {3380 // Done!3381 } else if (Value * NotInnerCond; matchOuterCond(m_CombineAnd(3382 m_Not(m_Specific(InnerSel.Cond)), m_Value(NotInnerCond)))) {3383 // Done!3384 std::swap(InnerSel.TrueVal, InnerSel.FalseVal);3385 InnerSel.Cond = NotInnerCond;3386 } else // Not the pattern we were looking for.3387 return nullptr;3388 3389 Value *SelInner = Builder.CreateSelect(3390 AltCond, IsAndVariant ? OuterSel.TrueVal : InnerSel.FalseVal,3391 IsAndVariant ? InnerSel.TrueVal : OuterSel.FalseVal);3392 SelInner->takeName(InnerSelVal);3393 return SelectInst::Create(InnerSel.Cond,3394 IsAndVariant ? SelInner : InnerSel.TrueVal,3395 !IsAndVariant ? SelInner : InnerSel.FalseVal);3396}3397 3398/// Return true if V is poison or \p Expected given that ValAssumedPoison is3399/// already poison. For example, if ValAssumedPoison is `icmp samesign X, 10`3400/// and V is `icmp ne X, 5`, impliesPoisonOrCond returns true.3401static bool impliesPoisonOrCond(const Value *ValAssumedPoison, const Value *V,3402 bool Expected) {3403 if (impliesPoison(ValAssumedPoison, V))3404 return true;3405 3406 // Handle the case that ValAssumedPoison is `icmp samesign pred X, C1` and V3407 // is `icmp pred X, C2`, where C1 is well-defined.3408 if (auto *ICmp = dyn_cast<ICmpInst>(ValAssumedPoison)) {3409 Value *LHS = ICmp->getOperand(0);3410 const APInt *RHSC1;3411 const APInt *RHSC2;3412 CmpPredicate Pred;3413 if (ICmp->hasSameSign() &&3414 match(ICmp->getOperand(1), m_APIntForbidPoison(RHSC1)) &&3415 match(V, m_ICmp(Pred, m_Specific(LHS), m_APIntAllowPoison(RHSC2)))) {3416 unsigned BitWidth = RHSC1->getBitWidth();3417 ConstantRange CRX =3418 RHSC1->isNonNegative()3419 ? ConstantRange(APInt::getSignedMinValue(BitWidth),3420 APInt::getZero(BitWidth))3421 : ConstantRange(APInt::getZero(BitWidth),3422 APInt::getSignedMinValue(BitWidth));3423 return CRX.icmp(Expected ? Pred : ICmpInst::getInverseCmpPredicate(Pred),3424 *RHSC2);3425 }3426 }3427 3428 return false;3429}3430 3431Instruction *InstCombinerImpl::foldSelectOfBools(SelectInst &SI) {3432 Value *CondVal = SI.getCondition();3433 Value *TrueVal = SI.getTrueValue();3434 Value *FalseVal = SI.getFalseValue();3435 Type *SelType = SI.getType();3436 3437 // Avoid potential infinite loops by checking for non-constant condition.3438 // TODO: Can we assert instead by improving canonicalizeSelectToShuffle()?3439 // Scalar select must have simplified?3440 if (!SelType->isIntOrIntVectorTy(1) || isa<Constant>(CondVal) ||3441 TrueVal->getType() != CondVal->getType())3442 return nullptr;3443 3444 auto *One = ConstantInt::getTrue(SelType);3445 auto *Zero = ConstantInt::getFalse(SelType);3446 Value *A, *B, *C, *D;3447 3448 // Folding select to and/or i1 isn't poison safe in general. impliesPoison3449 // checks whether folding it does not convert a well-defined value into3450 // poison.3451 if (match(TrueVal, m_One())) {3452 if (impliesPoisonOrCond(FalseVal, CondVal, /*Expected=*/false)) {3453 // Change: A = select B, true, C --> A = or B, C3454 return BinaryOperator::CreateOr(CondVal, FalseVal);3455 }3456 3457 if (match(CondVal, m_OneUse(m_Select(m_Value(A), m_One(), m_Value(B)))) &&3458 impliesPoisonOrCond(FalseVal, B, /*Expected=*/false)) {3459 // (A || B) || C --> A || (B | C)3460 return replaceInstUsesWith(3461 SI, Builder.CreateLogicalOr(A, Builder.CreateOr(B, FalseVal), "",3462 ProfcheckDisableMetadataFixes3463 ? nullptr3464 : cast<SelectInst>(CondVal)));3465 }3466 3467 // (A && B) || (C && B) --> (A || C) && B3468 if (match(CondVal, m_LogicalAnd(m_Value(A), m_Value(B))) &&3469 match(FalseVal, m_LogicalAnd(m_Value(C), m_Value(D))) &&3470 (CondVal->hasOneUse() || FalseVal->hasOneUse())) {3471 bool CondLogicAnd = isa<SelectInst>(CondVal);3472 bool FalseLogicAnd = isa<SelectInst>(FalseVal);3473 auto AndFactorization = [&](Value *Common, Value *InnerCond,3474 Value *InnerVal,3475 bool SelFirst = false) -> Instruction * {3476 Value *InnerSel = Builder.CreateSelect(InnerCond, One, InnerVal);3477 if (SelFirst)3478 std::swap(Common, InnerSel);3479 if (FalseLogicAnd || (CondLogicAnd && Common == A))3480 return SelectInst::Create(Common, InnerSel, Zero);3481 else3482 return BinaryOperator::CreateAnd(Common, InnerSel);3483 };3484 3485 if (A == C)3486 return AndFactorization(A, B, D);3487 if (A == D)3488 return AndFactorization(A, B, C);3489 if (B == C)3490 return AndFactorization(B, A, D);3491 if (B == D)3492 return AndFactorization(B, A, C, CondLogicAnd && FalseLogicAnd);3493 }3494 }3495 3496 if (match(FalseVal, m_Zero())) {3497 if (impliesPoisonOrCond(TrueVal, CondVal, /*Expected=*/true)) {3498 // Change: A = select B, C, false --> A = and B, C3499 return BinaryOperator::CreateAnd(CondVal, TrueVal);3500 }3501 3502 if (match(CondVal, m_OneUse(m_Select(m_Value(A), m_Value(B), m_Zero()))) &&3503 impliesPoisonOrCond(TrueVal, B, /*Expected=*/true)) {3504 // (A && B) && C --> A && (B & C)3505 return replaceInstUsesWith(3506 SI, Builder.CreateLogicalAnd(A, Builder.CreateAnd(B, TrueVal), "",3507 ProfcheckDisableMetadataFixes3508 ? nullptr3509 : cast<SelectInst>(CondVal)));3510 }3511 3512 // (A || B) && (C || B) --> (A && C) || B3513 if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&3514 match(TrueVal, m_LogicalOr(m_Value(C), m_Value(D))) &&3515 (CondVal->hasOneUse() || TrueVal->hasOneUse())) {3516 bool CondLogicOr = isa<SelectInst>(CondVal);3517 bool TrueLogicOr = isa<SelectInst>(TrueVal);3518 auto OrFactorization = [&](Value *Common, Value *InnerCond,3519 Value *InnerVal,3520 bool SelFirst = false) -> Instruction * {3521 Value *InnerSel = Builder.CreateSelect(InnerCond, InnerVal, Zero);3522 if (SelFirst)3523 std::swap(Common, InnerSel);3524 if (TrueLogicOr || (CondLogicOr && Common == A))3525 return SelectInst::Create(Common, One, InnerSel);3526 else3527 return BinaryOperator::CreateOr(Common, InnerSel);3528 };3529 3530 if (A == C)3531 return OrFactorization(A, B, D);3532 if (A == D)3533 return OrFactorization(A, B, C);3534 if (B == C)3535 return OrFactorization(B, A, D);3536 if (B == D)3537 return OrFactorization(B, A, C, CondLogicOr && TrueLogicOr);3538 }3539 }3540 3541 // We match the "full" 0 or 1 constant here to avoid a potential infinite3542 // loop with vectors that may have undefined/poison elements.3543 // select a, false, b -> select !a, b, false3544 if (match(TrueVal, m_Specific(Zero))) {3545 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());3546 Instruction *MDFrom = ProfcheckDisableMetadataFixes ? nullptr : &SI;3547 SelectInst *NewSI =3548 SelectInst::Create(NotCond, FalseVal, Zero, "", nullptr, MDFrom);3549 NewSI->swapProfMetadata();3550 return NewSI;3551 }3552 // select a, b, true -> select !a, true, b3553 if (match(FalseVal, m_Specific(One))) {3554 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());3555 Instruction *MDFrom = ProfcheckDisableMetadataFixes ? nullptr : &SI;3556 SelectInst *NewSI =3557 SelectInst::Create(NotCond, One, TrueVal, "", nullptr, MDFrom);3558 NewSI->swapProfMetadata();3559 return NewSI;3560 }3561 3562 // DeMorgan in select form: !a && !b --> !(a || b)3563 // select !a, !b, false --> not (select a, true, b)3564 if (match(&SI, m_LogicalAnd(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&3565 (CondVal->hasOneUse() || TrueVal->hasOneUse()) &&3566 !match(A, m_ConstantExpr()) && !match(B, m_ConstantExpr())) {3567 Instruction *MDFrom = ProfcheckDisableMetadataFixes ? nullptr : &SI;3568 SelectInst *NewSI =3569 cast<SelectInst>(Builder.CreateSelect(A, One, B, "", MDFrom));3570 NewSI->swapProfMetadata();3571 return BinaryOperator::CreateNot(NewSI);3572 }3573 3574 // DeMorgan in select form: !a || !b --> !(a && b)3575 // select !a, true, !b --> not (select a, b, false)3576 if (match(&SI, m_LogicalOr(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&3577 (CondVal->hasOneUse() || FalseVal->hasOneUse()) &&3578 !match(A, m_ConstantExpr()) && !match(B, m_ConstantExpr())) {3579 Instruction *MDFrom = ProfcheckDisableMetadataFixes ? nullptr : &SI;3580 SelectInst *NewSI =3581 cast<SelectInst>(Builder.CreateSelect(A, B, Zero, "", MDFrom));3582 NewSI->swapProfMetadata();3583 return BinaryOperator::CreateNot(NewSI);3584 }3585 3586 // select (select a, true, b), true, b -> select a, true, b3587 if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&3588 match(TrueVal, m_One()) && match(FalseVal, m_Specific(B)))3589 return replaceOperand(SI, 0, A);3590 // select (select a, b, false), b, false -> select a, b, false3591 if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&3592 match(TrueVal, m_Specific(B)) && match(FalseVal, m_Zero()))3593 return replaceOperand(SI, 0, A);3594 3595 // ~(A & B) & (A | B) --> A ^ B3596 if (match(&SI, m_c_LogicalAnd(m_Not(m_LogicalAnd(m_Value(A), m_Value(B))),3597 m_c_LogicalOr(m_Deferred(A), m_Deferred(B)))))3598 return BinaryOperator::CreateXor(A, B);3599 3600 // select (~a | c), a, b -> select a, (select c, true, b), false3601 if (match(CondVal,3602 m_OneUse(m_c_Or(m_Not(m_Specific(TrueVal)), m_Value(C))))) {3603 Value *OrV = Builder.CreateSelect(C, One, FalseVal);3604 return SelectInst::Create(TrueVal, OrV, Zero);3605 }3606 // select (c & b), a, b -> select b, (select ~c, true, a), false3607 if (match(CondVal, m_OneUse(m_c_And(m_Value(C), m_Specific(FalseVal))))) {3608 if (Value *NotC = getFreelyInverted(C, C->hasOneUse(), &Builder)) {3609 Value *OrV = Builder.CreateSelect(NotC, One, TrueVal);3610 return SelectInst::Create(FalseVal, OrV, Zero);3611 }3612 }3613 // select (a | c), a, b -> select a, true, (select ~c, b, false)3614 if (match(CondVal, m_OneUse(m_c_Or(m_Specific(TrueVal), m_Value(C))))) {3615 if (Value *NotC = getFreelyInverted(C, C->hasOneUse(), &Builder)) {3616 Value *AndV = Builder.CreateSelect(NotC, FalseVal, Zero);3617 return SelectInst::Create(TrueVal, One, AndV);3618 }3619 }3620 // select (c & ~b), a, b -> select b, true, (select c, a, false)3621 if (match(CondVal,3622 m_OneUse(m_c_And(m_Value(C), m_Not(m_Specific(FalseVal)))))) {3623 Value *AndV = Builder.CreateSelect(C, TrueVal, Zero);3624 return SelectInst::Create(FalseVal, One, AndV);3625 }3626 3627 if (match(FalseVal, m_Zero()) || match(TrueVal, m_One())) {3628 Use *Y = nullptr;3629 bool IsAnd = match(FalseVal, m_Zero()) ? true : false;3630 Value *Op1 = IsAnd ? TrueVal : FalseVal;3631 if (isCheckForZeroAndMulWithOverflow(CondVal, Op1, IsAnd, Y)) {3632 auto *FI = new FreezeInst(*Y, (*Y)->getName() + ".fr");3633 InsertNewInstBefore(FI, cast<Instruction>(Y->getUser())->getIterator());3634 replaceUse(*Y, FI);3635 return replaceInstUsesWith(SI, Op1);3636 }3637 3638 if (auto *V = foldBooleanAndOr(CondVal, Op1, SI, IsAnd,3639 /*IsLogical=*/true))3640 return replaceInstUsesWith(SI, V);3641 }3642 3643 // select (a || b), c, false -> select a, c, false3644 // select c, (a || b), false -> select c, a, false3645 // if c implies that b is false.3646 if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&3647 match(FalseVal, m_Zero())) {3648 std::optional<bool> Res = isImpliedCondition(TrueVal, B, DL);3649 if (Res && *Res == false)3650 return replaceOperand(SI, 0, A);3651 }3652 if (match(TrueVal, m_LogicalOr(m_Value(A), m_Value(B))) &&3653 match(FalseVal, m_Zero())) {3654 std::optional<bool> Res = isImpliedCondition(CondVal, B, DL);3655 if (Res && *Res == false)3656 return replaceOperand(SI, 1, A);3657 }3658 // select c, true, (a && b) -> select c, true, a3659 // select (a && b), true, c -> select a, true, c3660 // if c = false implies that b = true3661 if (match(TrueVal, m_One()) &&3662 match(FalseVal, m_LogicalAnd(m_Value(A), m_Value(B)))) {3663 std::optional<bool> Res = isImpliedCondition(CondVal, B, DL, false);3664 if (Res && *Res == true)3665 return replaceOperand(SI, 2, A);3666 }3667 if (match(CondVal, m_LogicalAnd(m_Value(A), m_Value(B))) &&3668 match(TrueVal, m_One())) {3669 std::optional<bool> Res = isImpliedCondition(FalseVal, B, DL, false);3670 if (Res && *Res == true)3671 return replaceOperand(SI, 0, A);3672 }3673 3674 if (match(TrueVal, m_One())) {3675 Value *C;3676 3677 // (C && A) || (!C && B) --> sel C, A, B3678 // (A && C) || (!C && B) --> sel C, A, B3679 // (C && A) || (B && !C) --> sel C, A, B3680 // (A && C) || (B && !C) --> sel C, A, B (may require freeze)3681 if (match(FalseVal, m_c_LogicalAnd(m_Not(m_Value(C)), m_Value(B))) &&3682 match(CondVal, m_c_LogicalAnd(m_Specific(C), m_Value(A)))) {3683 auto *SelCond = dyn_cast<SelectInst>(CondVal);3684 auto *SelFVal = dyn_cast<SelectInst>(FalseVal);3685 bool MayNeedFreeze = SelCond && SelFVal &&3686 match(SelFVal->getTrueValue(),3687 m_Not(m_Specific(SelCond->getTrueValue())));3688 if (MayNeedFreeze)3689 C = Builder.CreateFreeze(C);3690 if (!ProfcheckDisableMetadataFixes) {3691 Value *C2 = nullptr, *A2 = nullptr, *B2 = nullptr;3692 if (match(CondVal, m_LogicalAnd(m_Specific(C), m_Value(A2))) &&3693 SelCond) {3694 return SelectInst::Create(C, A, B, "", nullptr, SelCond);3695 } else if (match(FalseVal,3696 m_LogicalAnd(m_Not(m_Value(C2)), m_Value(B2))) &&3697 SelFVal) {3698 SelectInst *NewSI = SelectInst::Create(C, A, B, "", nullptr, SelFVal);3699 NewSI->swapProfMetadata();3700 return NewSI;3701 } else {3702 return createSelectInstWithUnknownProfile(C, A, B);3703 }3704 }3705 return SelectInst::Create(C, A, B);3706 }3707 3708 // (!C && A) || (C && B) --> sel C, B, A3709 // (A && !C) || (C && B) --> sel C, B, A3710 // (!C && A) || (B && C) --> sel C, B, A3711 // (A && !C) || (B && C) --> sel C, B, A (may require freeze)3712 if (match(CondVal, m_c_LogicalAnd(m_Not(m_Value(C)), m_Value(A))) &&3713 match(FalseVal, m_c_LogicalAnd(m_Specific(C), m_Value(B)))) {3714 auto *SelCond = dyn_cast<SelectInst>(CondVal);3715 auto *SelFVal = dyn_cast<SelectInst>(FalseVal);3716 bool MayNeedFreeze = SelCond && SelFVal &&3717 match(SelCond->getTrueValue(),3718 m_Not(m_Specific(SelFVal->getTrueValue())));3719 if (MayNeedFreeze)3720 C = Builder.CreateFreeze(C);3721 if (!ProfcheckDisableMetadataFixes) {3722 Value *C2 = nullptr, *A2 = nullptr, *B2 = nullptr;3723 if (match(CondVal, m_LogicalAnd(m_Not(m_Value(C2)), m_Value(A2))) &&3724 SelCond) {3725 SelectInst *NewSI = SelectInst::Create(C, B, A, "", nullptr, SelCond);3726 NewSI->swapProfMetadata();3727 return NewSI;3728 } else if (match(FalseVal, m_LogicalAnd(m_Specific(C), m_Value(B2))) &&3729 SelFVal) {3730 return SelectInst::Create(C, B, A, "", nullptr, SelFVal);3731 } else {3732 return createSelectInstWithUnknownProfile(C, B, A);3733 }3734 }3735 return SelectInst::Create(C, B, A);3736 }3737 }3738 3739 return nullptr;3740}3741 3742// Return true if we can safely remove the select instruction for std::bit_ceil3743// pattern.3744static bool isSafeToRemoveBitCeilSelect(ICmpInst::Predicate Pred, Value *Cond0,3745 const APInt *Cond1, Value *CtlzOp,3746 unsigned BitWidth,3747 bool &ShouldDropNoWrap) {3748 // The challenge in recognizing std::bit_ceil(X) is that the operand is used3749 // for the CTLZ proper and select condition, each possibly with some3750 // operation like add and sub.3751 //3752 // Our aim is to make sure that -ctlz & (BitWidth - 1) == 0 even when the3753 // select instruction would select 1, which allows us to get rid of the select3754 // instruction.3755 //3756 // To see if we can do so, we do some symbolic execution with ConstantRange.3757 // Specifically, we compute the range of values that Cond0 could take when3758 // Cond == false. Then we successively transform the range until we obtain3759 // the range of values that CtlzOp could take.3760 //3761 // Conceptually, we follow the def-use chain backward from Cond0 while3762 // transforming the range for Cond0 until we meet the common ancestor of Cond03763 // and CtlzOp. Then we follow the def-use chain forward until we obtain the3764 // range for CtlzOp. That said, we only follow at most one ancestor from3765 // Cond0. Likewise, we only follow at most one ancestor from CtrlOp.3766 3767 ConstantRange CR = ConstantRange::makeExactICmpRegion(3768 CmpInst::getInversePredicate(Pred), *Cond1);3769 3770 ShouldDropNoWrap = false;3771 3772 // Match the operation that's used to compute CtlzOp from CommonAncestor. If3773 // CtlzOp == CommonAncestor, return true as no operation is needed. If a3774 // match is found, execute the operation on CR, update CR, and return true.3775 // Otherwise, return false.3776 auto MatchForward = [&](Value *CommonAncestor) {3777 const APInt *C = nullptr;3778 if (CtlzOp == CommonAncestor)3779 return true;3780 if (match(CtlzOp, m_Add(m_Specific(CommonAncestor), m_APInt(C)))) {3781 ShouldDropNoWrap = true;3782 CR = CR.add(*C);3783 return true;3784 }3785 if (match(CtlzOp, m_Sub(m_APInt(C), m_Specific(CommonAncestor)))) {3786 ShouldDropNoWrap = true;3787 CR = ConstantRange(*C).sub(CR);3788 return true;3789 }3790 if (match(CtlzOp, m_Not(m_Specific(CommonAncestor)))) {3791 CR = CR.binaryNot();3792 return true;3793 }3794 return false;3795 };3796 3797 const APInt *C = nullptr;3798 Value *CommonAncestor;3799 if (MatchForward(Cond0)) {3800 // Cond0 is either CtlzOp or CtlzOp's parent. CR has been updated.3801 } else if (match(Cond0, m_Add(m_Value(CommonAncestor), m_APInt(C)))) {3802 CR = CR.sub(*C);3803 if (!MatchForward(CommonAncestor))3804 return false;3805 // Cond0's parent is either CtlzOp or CtlzOp's parent. CR has been updated.3806 } else {3807 return false;3808 }3809 3810 // Return true if all the values in the range are either 0 or negative (if3811 // treated as signed). We do so by evaluating:3812 //3813 // CR - 1 u>= (1 << BitWidth) - 1.3814 APInt IntMax = APInt::getSignMask(BitWidth) - 1;3815 CR = CR.sub(APInt(BitWidth, 1));3816 return CR.icmp(ICmpInst::ICMP_UGE, IntMax);3817}3818 3819// Transform the std::bit_ceil(X) pattern like:3820//3821// %dec = add i32 %x, -13822// %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)3823// %sub = sub i32 32, %ctlz3824// %shl = shl i32 1, %sub3825// %ugt = icmp ugt i32 %x, 13826// %sel = select i1 %ugt, i32 %shl, i32 13827//3828// into:3829//3830// %dec = add i32 %x, -13831// %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)3832// %neg = sub i32 0, %ctlz3833// %masked = and i32 %ctlz, 313834// %shl = shl i32 1, %sub3835//3836// Note that the select is optimized away while the shift count is masked with3837// 31. We handle some variations of the input operand like std::bit_ceil(X +3838// 1).3839static Instruction *foldBitCeil(SelectInst &SI, IRBuilderBase &Builder,3840 InstCombinerImpl &IC) {3841 Type *SelType = SI.getType();3842 unsigned BitWidth = SelType->getScalarSizeInBits();3843 3844 Value *FalseVal = SI.getFalseValue();3845 Value *TrueVal = SI.getTrueValue();3846 CmpPredicate Pred;3847 const APInt *Cond1;3848 Value *Cond0, *Ctlz, *CtlzOp;3849 if (!match(SI.getCondition(), m_ICmp(Pred, m_Value(Cond0), m_APInt(Cond1))))3850 return nullptr;3851 3852 if (match(TrueVal, m_One())) {3853 std::swap(FalseVal, TrueVal);3854 Pred = CmpInst::getInversePredicate(Pred);3855 }3856 3857 bool ShouldDropNoWrap;3858 3859 if (!match(FalseVal, m_One()) ||3860 !match(TrueVal,3861 m_OneUse(m_Shl(m_One(), m_OneUse(m_Sub(m_SpecificInt(BitWidth),3862 m_Value(Ctlz)))))) ||3863 !match(Ctlz, m_Intrinsic<Intrinsic::ctlz>(m_Value(CtlzOp), m_Value())) ||3864 !isSafeToRemoveBitCeilSelect(Pred, Cond0, Cond1, CtlzOp, BitWidth,3865 ShouldDropNoWrap))3866 return nullptr;3867 3868 if (ShouldDropNoWrap) {3869 cast<Instruction>(CtlzOp)->setHasNoUnsignedWrap(false);3870 cast<Instruction>(CtlzOp)->setHasNoSignedWrap(false);3871 }3872 3873 // Build 1 << (-CTLZ & (BitWidth-1)). The negation likely corresponds to a3874 // single hardware instruction as opposed to BitWidth - CTLZ, where BitWidth3875 // is an integer constant. Masking with BitWidth-1 comes free on some3876 // hardware as part of the shift instruction.3877 3878 // Drop range attributes and re-infer them in the next iteration.3879 cast<Instruction>(Ctlz)->dropPoisonGeneratingAnnotations();3880 // Set is_zero_poison to false and re-infer them in the next iteration.3881 cast<Instruction>(Ctlz)->setOperand(1, Builder.getFalse());3882 IC.addToWorklist(cast<Instruction>(Ctlz));3883 Value *Neg = Builder.CreateNeg(Ctlz);3884 Value *Masked =3885 Builder.CreateAnd(Neg, ConstantInt::get(SelType, BitWidth - 1));3886 return BinaryOperator::Create(Instruction::Shl, ConstantInt::get(SelType, 1),3887 Masked);3888}3889 3890// This function tries to fold the following operations:3891// (x < y) ? -1 : zext(x != y)3892// (x < y) ? -1 : zext(x > y)3893// (x > y) ? 1 : sext(x != y)3894// (x > y) ? 1 : sext(x < y)3895// (x == y) ? 0 : (x > y ? 1 : -1)3896// (x == y) ? 0 : (x < y ? -1 : 1)3897// Special case: x == C ? 0 : (x > C - 1 ? 1 : -1)3898// Special case: x == C ? 0 : (x < C + 1 ? -1 : 1)3899// Into ucmp/scmp(x, y), where signedness is determined by the signedness3900// of the comparison in the original sequence.3901Instruction *InstCombinerImpl::foldSelectToCmp(SelectInst &SI) {3902 Value *TV = SI.getTrueValue();3903 Value *FV = SI.getFalseValue();3904 3905 CmpPredicate Pred;3906 Value *LHS, *RHS;3907 if (!match(SI.getCondition(), m_ICmp(Pred, m_Value(LHS), m_Value(RHS))))3908 return nullptr;3909 3910 if (!LHS->getType()->isIntOrIntVectorTy())3911 return nullptr;3912 3913 // If there is no -1, 0 or 1 at TV, then invert the select statement and try3914 // to canonicalize to one of the forms above3915 if (!isa<Constant>(TV)) {3916 if (!isa<Constant>(FV))3917 return nullptr;3918 Pred = ICmpInst::getInverseCmpPredicate(Pred);3919 std::swap(TV, FV);3920 }3921 3922 if (ICmpInst::isNonStrictPredicate(Pred)) {3923 if (Constant *C = dyn_cast<Constant>(RHS)) {3924 auto FlippedPredAndConst =3925 getFlippedStrictnessPredicateAndConstant(Pred, C);3926 if (!FlippedPredAndConst)3927 return nullptr;3928 Pred = FlippedPredAndConst->first;3929 RHS = FlippedPredAndConst->second;3930 } else {3931 return nullptr;3932 }3933 }3934 3935 // Try to swap operands and the predicate. We need to be careful when doing3936 // so because two of the patterns have opposite predicates, so use the3937 // constant inside select to determine if swapping operands would be3938 // beneficial to us.3939 if ((ICmpInst::isGT(Pred) && match(TV, m_AllOnes())) ||3940 (ICmpInst::isLT(Pred) && match(TV, m_One()))) {3941 Pred = ICmpInst::getSwappedPredicate(Pred);3942 std::swap(LHS, RHS);3943 }3944 bool IsSigned = ICmpInst::isSigned(Pred);3945 3946 bool Replace = false;3947 CmpPredicate ExtendedCmpPredicate;3948 // (x < y) ? -1 : zext(x != y)3949 // (x < y) ? -1 : zext(x > y)3950 if (ICmpInst::isLT(Pred) && match(TV, m_AllOnes()) &&3951 match(FV, m_ZExt(m_c_ICmp(ExtendedCmpPredicate, m_Specific(LHS),3952 m_Specific(RHS)))) &&3953 (ExtendedCmpPredicate == ICmpInst::ICMP_NE ||3954 ICmpInst::getSwappedPredicate(ExtendedCmpPredicate) == Pred))3955 Replace = true;3956 3957 // (x > y) ? 1 : sext(x != y)3958 // (x > y) ? 1 : sext(x < y)3959 if (ICmpInst::isGT(Pred) && match(TV, m_One()) &&3960 match(FV, m_SExt(m_c_ICmp(ExtendedCmpPredicate, m_Specific(LHS),3961 m_Specific(RHS)))) &&3962 (ExtendedCmpPredicate == ICmpInst::ICMP_NE ||3963 ICmpInst::getSwappedPredicate(ExtendedCmpPredicate) == Pred))3964 Replace = true;3965 3966 // (x == y) ? 0 : (x > y ? 1 : -1)3967 CmpPredicate FalseBranchSelectPredicate;3968 const APInt *InnerTV, *InnerFV;3969 if (Pred == ICmpInst::ICMP_EQ && match(TV, m_Zero()) &&3970 match(FV, m_Select(m_c_ICmp(FalseBranchSelectPredicate, m_Specific(LHS),3971 m_Specific(RHS)),3972 m_APInt(InnerTV), m_APInt(InnerFV)))) {3973 if (!ICmpInst::isGT(FalseBranchSelectPredicate)) {3974 FalseBranchSelectPredicate =3975 ICmpInst::getSwappedPredicate(FalseBranchSelectPredicate);3976 std::swap(LHS, RHS);3977 }3978 3979 if (!InnerTV->isOne()) {3980 std::swap(InnerTV, InnerFV);3981 std::swap(LHS, RHS);3982 }3983 3984 if (ICmpInst::isGT(FalseBranchSelectPredicate) && InnerTV->isOne() &&3985 InnerFV->isAllOnes()) {3986 IsSigned = ICmpInst::isSigned(FalseBranchSelectPredicate);3987 Replace = true;3988 }3989 }3990 3991 // Special cases with constants: x == C ? 0 : (x > C-1 ? 1 : -1)3992 if (Pred == ICmpInst::ICMP_EQ && match(TV, m_Zero())) {3993 const APInt *C;3994 if (match(RHS, m_APInt(C))) {3995 CmpPredicate InnerPred;3996 Value *InnerRHS;3997 const APInt *InnerTV, *InnerFV;3998 if (match(FV,3999 m_Select(m_ICmp(InnerPred, m_Specific(LHS), m_Value(InnerRHS)),4000 m_APInt(InnerTV), m_APInt(InnerFV)))) {4001 4002 // x == C ? 0 : (x > C-1 ? 1 : -1)4003 if (ICmpInst::isGT(InnerPred) && InnerTV->isOne() &&4004 InnerFV->isAllOnes()) {4005 IsSigned = ICmpInst::isSigned(InnerPred);4006 bool CanSubOne = IsSigned ? !C->isMinSignedValue() : !C->isMinValue();4007 if (CanSubOne) {4008 APInt Cminus1 = *C - 1;4009 if (match(InnerRHS, m_SpecificInt(Cminus1)))4010 Replace = true;4011 }4012 }4013 4014 // x == C ? 0 : (x < C+1 ? -1 : 1)4015 if (ICmpInst::isLT(InnerPred) && InnerTV->isAllOnes() &&4016 InnerFV->isOne()) {4017 IsSigned = ICmpInst::isSigned(InnerPred);4018 bool CanAddOne = IsSigned ? !C->isMaxSignedValue() : !C->isMaxValue();4019 if (CanAddOne) {4020 APInt Cplus1 = *C + 1;4021 if (match(InnerRHS, m_SpecificInt(Cplus1)))4022 Replace = true;4023 }4024 }4025 }4026 }4027 }4028 4029 Intrinsic::ID IID = IsSigned ? Intrinsic::scmp : Intrinsic::ucmp;4030 if (Replace)4031 return replaceInstUsesWith(4032 SI, Builder.CreateIntrinsic(SI.getType(), IID, {LHS, RHS}));4033 return nullptr;4034}4035 4036bool InstCombinerImpl::fmulByZeroIsZero(Value *MulVal, FastMathFlags FMF,4037 const Instruction *CtxI) const {4038 KnownFPClass Known = computeKnownFPClass(MulVal, FMF, fcNegative, CtxI);4039 4040 return Known.isKnownNeverNaN() && Known.isKnownNeverInfinity() &&4041 (FMF.noSignedZeros() || Known.signBitIsZeroOrNaN());4042}4043 4044static bool matchFMulByZeroIfResultEqZero(InstCombinerImpl &IC, Value *Cmp0,4045 Value *Cmp1, Value *TrueVal,4046 Value *FalseVal, Instruction &CtxI,4047 bool SelectIsNSZ) {4048 Value *MulRHS;4049 if (match(Cmp1, m_PosZeroFP()) &&4050 match(TrueVal, m_c_FMul(m_Specific(Cmp0), m_Value(MulRHS)))) {4051 FastMathFlags FMF = cast<FPMathOperator>(TrueVal)->getFastMathFlags();4052 // nsz must be on the select, it must be ignored on the multiply. We4053 // need nnan and ninf on the multiply for the other value.4054 FMF.setNoSignedZeros(SelectIsNSZ);4055 return IC.fmulByZeroIsZero(MulRHS, FMF, &CtxI);4056 }4057 4058 return false;4059}4060 4061/// Check whether the KnownBits of a select arm may be affected by the4062/// select condition.4063static bool hasAffectedValue(Value *V, SmallPtrSetImpl<Value *> &Affected,4064 unsigned Depth) {4065 if (Depth == MaxAnalysisRecursionDepth)4066 return false;4067 4068 // Ignore the case where the select arm itself is affected. These cases4069 // are handled more efficiently by other optimizations.4070 if (Depth != 0 && Affected.contains(V))4071 return true;4072 4073 if (auto *I = dyn_cast<Instruction>(V)) {4074 if (isa<PHINode>(I)) {4075 if (Depth == MaxAnalysisRecursionDepth - 1)4076 return false;4077 Depth = MaxAnalysisRecursionDepth - 2;4078 }4079 return any_of(I->operands(), [&](Value *Op) {4080 return Op->getType()->isIntOrIntVectorTy() &&4081 hasAffectedValue(Op, Affected, Depth + 1);4082 });4083 }4084 4085 return false;4086}4087 4088// This transformation enables the possibility of transforming fcmp + sel into4089// a fmaxnum/fminnum intrinsic.4090static Value *foldSelectIntoAddConstant(SelectInst &SI,4091 InstCombiner::BuilderTy &Builder) {4092 // Do this transformation only when select instruction gives NaN and NSZ4093 // guarantee.4094 auto *SIFOp = dyn_cast<FPMathOperator>(&SI);4095 if (!SIFOp || !SIFOp->hasNoSignedZeros() || !SIFOp->hasNoNaNs())4096 return nullptr;4097 4098 auto TryFoldIntoAddConstant =4099 [&Builder, &SI](CmpInst::Predicate Pred, Value *X, Value *Z,4100 Instruction *FAdd, Constant *C, bool Swapped) -> Value * {4101 // Only these relational predicates can be transformed into maxnum/minnum4102 // intrinsic.4103 if (!CmpInst::isRelational(Pred) || !match(Z, m_AnyZeroFP()))4104 return nullptr;4105 4106 if (!match(FAdd, m_FAdd(m_Specific(X), m_Specific(C))))4107 return nullptr;4108 4109 Value *NewSelect = Builder.CreateSelect(SI.getCondition(), Swapped ? Z : X,4110 Swapped ? X : Z, "", &SI);4111 NewSelect->takeName(&SI);4112 4113 Value *NewFAdd = Builder.CreateFAdd(NewSelect, C);4114 NewFAdd->takeName(FAdd);4115 4116 // Propagate FastMath flags4117 FastMathFlags SelectFMF = SI.getFastMathFlags();4118 FastMathFlags FAddFMF = FAdd->getFastMathFlags();4119 FastMathFlags NewFMF = FastMathFlags::intersectRewrite(SelectFMF, FAddFMF) |4120 FastMathFlags::unionValue(SelectFMF, FAddFMF);4121 cast<Instruction>(NewFAdd)->setFastMathFlags(NewFMF);4122 cast<Instruction>(NewSelect)->setFastMathFlags(NewFMF);4123 4124 return NewFAdd;4125 };4126 4127 // select((fcmp Pred, X, 0), (fadd X, C), C)4128 // => fadd((select (fcmp Pred, X, 0), X, 0), C)4129 //4130 // Pred := OGT, OGE, OLT, OLE, UGT, UGE, ULT, and ULE4131 Instruction *FAdd;4132 Constant *C;4133 Value *X, *Z;4134 CmpPredicate Pred;4135 4136 // Note: OneUse check for `Cmp` is necessary because it makes sure that other4137 // InstCombine folds don't undo this transformation and cause an infinite4138 // loop. Furthermore, it could also increase the operation count.4139 if (match(&SI, m_Select(m_OneUse(m_FCmp(Pred, m_Value(X), m_Value(Z))),4140 m_OneUse(m_Instruction(FAdd)), m_Constant(C))))4141 return TryFoldIntoAddConstant(Pred, X, Z, FAdd, C, /*Swapped=*/false);4142 4143 if (match(&SI, m_Select(m_OneUse(m_FCmp(Pred, m_Value(X), m_Value(Z))),4144 m_Constant(C), m_OneUse(m_Instruction(FAdd)))))4145 return TryFoldIntoAddConstant(Pred, X, Z, FAdd, C, /*Swapped=*/true);4146 4147 return nullptr;4148}4149 4150static Value *foldSelectBitTest(SelectInst &Sel, Value *CondVal, Value *TrueVal,4151 Value *FalseVal,4152 InstCombiner::BuilderTy &Builder,4153 const SimplifyQuery &SQ) {4154 // If this is a vector select, we need a vector compare.4155 Type *SelType = Sel.getType();4156 if (SelType->isVectorTy() != CondVal->getType()->isVectorTy())4157 return nullptr;4158 4159 Value *V;4160 APInt AndMask;4161 bool CreateAnd = false;4162 CmpPredicate Pred;4163 Value *CmpLHS, *CmpRHS;4164 4165 if (match(CondVal, m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS)))) {4166 if (ICmpInst::isEquality(Pred)) {4167 if (!match(CmpRHS, m_Zero()))4168 return nullptr;4169 4170 V = CmpLHS;4171 const APInt *AndRHS;4172 if (!match(CmpLHS, m_And(m_Value(), m_Power2(AndRHS))))4173 return nullptr;4174 4175 AndMask = *AndRHS;4176 } else if (auto Res = decomposeBitTestICmp(CmpLHS, CmpRHS, Pred)) {4177 assert(ICmpInst::isEquality(Res->Pred) && "Not equality test?");4178 AndMask = Res->Mask;4179 V = Res->X;4180 KnownBits Known = computeKnownBits(V, SQ.getWithInstruction(&Sel));4181 AndMask &= Known.getMaxValue();4182 if (!AndMask.isPowerOf2())4183 return nullptr;4184 4185 Pred = Res->Pred;4186 CreateAnd = true;4187 } else {4188 return nullptr;4189 }4190 } else if (auto *Trunc = dyn_cast<TruncInst>(CondVal)) {4191 V = Trunc->getOperand(0);4192 AndMask = APInt(V->getType()->getScalarSizeInBits(), 1);4193 Pred = ICmpInst::ICMP_NE;4194 CreateAnd = !Trunc->hasNoUnsignedWrap();4195 } else {4196 return nullptr;4197 }4198 4199 if (Pred == ICmpInst::ICMP_NE)4200 std::swap(TrueVal, FalseVal);4201 4202 if (Value *X = foldSelectICmpAnd(Sel, CondVal, TrueVal, FalseVal, V, AndMask,4203 CreateAnd, Builder))4204 return X;4205 4206 if (Value *X = foldSelectICmpAndBinOp(CondVal, TrueVal, FalseVal, V, AndMask,4207 CreateAnd, Builder))4208 return X;4209 4210 return nullptr;4211}4212 4213Instruction *InstCombinerImpl::visitSelectInst(SelectInst &SI) {4214 Value *CondVal = SI.getCondition();4215 Value *TrueVal = SI.getTrueValue();4216 Value *FalseVal = SI.getFalseValue();4217 Type *SelType = SI.getType();4218 4219 if (Value *V = simplifySelectInst(CondVal, TrueVal, FalseVal,4220 SQ.getWithInstruction(&SI)))4221 return replaceInstUsesWith(SI, V);4222 4223 if (Instruction *I = canonicalizeSelectToShuffle(SI))4224 return I;4225 4226 if (Instruction *I = canonicalizeScalarSelectOfVecs(SI, *this))4227 return I;4228 4229 // If the type of select is not an integer type or if the condition and4230 // the selection type are not both scalar nor both vector types, there is no4231 // point in attempting to match these patterns.4232 Type *CondType = CondVal->getType();4233 if (!isa<Constant>(CondVal) && SelType->isIntOrIntVectorTy() &&4234 CondType->isVectorTy() == SelType->isVectorTy()) {4235 if (Value *S = simplifyWithOpReplaced(TrueVal, CondVal,4236 ConstantInt::getTrue(CondType), SQ,4237 /* AllowRefinement */ true))4238 return replaceOperand(SI, 1, S);4239 4240 if (Value *S = simplifyWithOpReplaced(FalseVal, CondVal,4241 ConstantInt::getFalse(CondType), SQ,4242 /* AllowRefinement */ true))4243 return replaceOperand(SI, 2, S);4244 4245 if (replaceInInstruction(TrueVal, CondVal,4246 ConstantInt::getTrue(CondType)) ||4247 replaceInInstruction(FalseVal, CondVal,4248 ConstantInt::getFalse(CondType)))4249 return &SI;4250 }4251 4252 if (Instruction *R = foldSelectOfBools(SI))4253 return R;4254 4255 // Selecting between two integer or vector splat integer constants?4256 //4257 // Note that we don't handle a scalar select of vectors:4258 // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>4259 // because that may need 3 instructions to splat the condition value:4260 // extend, insertelement, shufflevector.4261 //4262 // Do not handle i1 TrueVal and FalseVal otherwise would result in4263 // zext/sext i1 to i1.4264 if (SelType->isIntOrIntVectorTy() && !SelType->isIntOrIntVectorTy(1) &&4265 CondVal->getType()->isVectorTy() == SelType->isVectorTy()) {4266 // select C, 1, 0 -> zext C to int4267 if (match(TrueVal, m_One()) && match(FalseVal, m_Zero()))4268 return new ZExtInst(CondVal, SelType);4269 4270 // select C, -1, 0 -> sext C to int4271 if (match(TrueVal, m_AllOnes()) && match(FalseVal, m_Zero()))4272 return new SExtInst(CondVal, SelType);4273 4274 // select C, 0, 1 -> zext !C to int4275 if (match(TrueVal, m_Zero()) && match(FalseVal, m_One())) {4276 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());4277 return new ZExtInst(NotCond, SelType);4278 }4279 4280 // select C, 0, -1 -> sext !C to int4281 if (match(TrueVal, m_Zero()) && match(FalseVal, m_AllOnes())) {4282 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());4283 return new SExtInst(NotCond, SelType);4284 }4285 }4286 4287 auto *SIFPOp = dyn_cast<FPMathOperator>(&SI);4288 4289 if (auto *FCmp = dyn_cast<FCmpInst>(CondVal)) {4290 FCmpInst::Predicate Pred = FCmp->getPredicate();4291 Value *Cmp0 = FCmp->getOperand(0), *Cmp1 = FCmp->getOperand(1);4292 // Are we selecting a value based on a comparison of the two values?4293 if ((Cmp0 == TrueVal && Cmp1 == FalseVal) ||4294 (Cmp0 == FalseVal && Cmp1 == TrueVal)) {4295 // Canonicalize to use ordered comparisons by swapping the select4296 // operands.4297 //4298 // e.g.4299 // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X4300 if (FCmp->hasOneUse() && FCmpInst::isUnordered(Pred)) {4301 FCmpInst::Predicate InvPred = FCmp->getInversePredicate();4302 Value *NewCond = Builder.CreateFCmpFMF(InvPred, Cmp0, Cmp1, FCmp,4303 FCmp->getName() + ".inv");4304 // Propagate ninf/nnan from fcmp to select.4305 FastMathFlags FMF = SI.getFastMathFlags();4306 if (FCmp->hasNoNaNs())4307 FMF.setNoNaNs(true);4308 if (FCmp->hasNoInfs())4309 FMF.setNoInfs(true);4310 Value *NewSel =4311 Builder.CreateSelectFMF(NewCond, FalseVal, TrueVal, FMF);4312 return replaceInstUsesWith(SI, NewSel);4313 }4314 }4315 4316 if (SIFPOp) {4317 // Fold out scale-if-equals-zero pattern.4318 //4319 // This pattern appears in code with denormal range checks after it's4320 // assumed denormals are treated as zero. This drops a canonicalization.4321 4322 // TODO: Could relax the signed zero logic. We just need to know the sign4323 // of the result matches (fmul x, y has the same sign as x).4324 //4325 // TODO: Handle always-canonicalizing variant that selects some value or 14326 // scaling factor in the fmul visitor.4327 4328 // TODO: Handle ldexp too4329 4330 Value *MatchCmp0 = nullptr;4331 Value *MatchCmp1 = nullptr;4332 4333 // (select (fcmp [ou]eq x, 0.0), (fmul x, K), x => x4334 // (select (fcmp [ou]ne x, 0.0), x, (fmul x, K) => x4335 if (Pred == CmpInst::FCMP_OEQ || Pred == CmpInst::FCMP_UEQ) {4336 MatchCmp0 = FalseVal;4337 MatchCmp1 = TrueVal;4338 } else if (Pred == CmpInst::FCMP_ONE || Pred == CmpInst::FCMP_UNE) {4339 MatchCmp0 = TrueVal;4340 MatchCmp1 = FalseVal;4341 }4342 4343 if (Cmp0 == MatchCmp0 &&4344 matchFMulByZeroIfResultEqZero(*this, Cmp0, Cmp1, MatchCmp1, MatchCmp0,4345 SI, SIFPOp->hasNoSignedZeros()))4346 return replaceInstUsesWith(SI, Cmp0);4347 }4348 }4349 4350 if (SIFPOp) {4351 // TODO: Try to forward-propagate FMF from select arms to the select.4352 4353 auto *FCmp = dyn_cast<FCmpInst>(CondVal);4354 4355 // Canonicalize select of FP values where NaN and -0.0 are not valid as4356 // minnum/maxnum intrinsics.4357 if (SIFPOp->hasNoNaNs() &&4358 (SIFPOp->hasNoSignedZeros() ||4359 (SIFPOp->hasOneUse() &&4360 canIgnoreSignBitOfZero(*SIFPOp->use_begin())))) {4361 Value *X, *Y;4362 if (match(&SI, m_OrdOrUnordFMax(m_Value(X), m_Value(Y)))) {4363 Value *BinIntr =4364 Builder.CreateBinaryIntrinsic(Intrinsic::maxnum, X, Y, &SI);4365 if (auto *BinIntrInst = dyn_cast<Instruction>(BinIntr)) {4366 BinIntrInst->setHasNoNaNs(FCmp->hasNoNaNs());4367 BinIntrInst->setHasNoInfs(FCmp->hasNoInfs());4368 }4369 return replaceInstUsesWith(SI, BinIntr);4370 }4371 4372 if (match(&SI, m_OrdOrUnordFMin(m_Value(X), m_Value(Y)))) {4373 Value *BinIntr =4374 Builder.CreateBinaryIntrinsic(Intrinsic::minnum, X, Y, &SI);4375 if (auto *BinIntrInst = dyn_cast<Instruction>(BinIntr)) {4376 BinIntrInst->setHasNoNaNs(FCmp->hasNoNaNs());4377 BinIntrInst->setHasNoInfs(FCmp->hasNoInfs());4378 }4379 return replaceInstUsesWith(SI, BinIntr);4380 }4381 }4382 }4383 4384 // Fold selecting to fabs.4385 if (Instruction *Fabs = foldSelectWithFCmpToFabs(SI, *this))4386 return Fabs;4387 4388 // See if we are selecting two values based on a comparison of the two values.4389 if (CmpInst *CI = dyn_cast<CmpInst>(CondVal))4390 if (Instruction *NewSel = foldSelectValueEquivalence(SI, *CI))4391 return NewSel;4392 4393 if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal))4394 if (Instruction *Result = foldSelectInstWithICmp(SI, ICI))4395 return Result;4396 4397 if (Value *V = foldSelectBitTest(SI, CondVal, TrueVal, FalseVal, Builder, SQ))4398 return replaceInstUsesWith(SI, V);4399 4400 if (Instruction *Add = foldAddSubSelect(SI, Builder))4401 return Add;4402 if (Instruction *Add = foldOverflowingAddSubSelect(SI, Builder))4403 return Add;4404 if (Instruction *Or = foldSetClearBits(SI, Builder))4405 return Or;4406 if (Instruction *Mul = foldSelectZeroOrFixedOp(SI, *this))4407 return Mul;4408 4409 // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))4410 auto *TI = dyn_cast<Instruction>(TrueVal);4411 auto *FI = dyn_cast<Instruction>(FalseVal);4412 if (TI && FI && TI->getOpcode() == FI->getOpcode())4413 if (Instruction *IV = foldSelectOpOp(SI, TI, FI))4414 return IV;4415 4416 if (Instruction *I = foldSelectExtConst(SI))4417 return I;4418 4419 if (Instruction *I = foldSelectWithSRem(SI, *this, Builder))4420 return I;4421 4422 // Fold (select C, (gep Ptr, Idx), Ptr) -> (gep Ptr, (select C, Idx, 0))4423 // Fold (select C, Ptr, (gep Ptr, Idx)) -> (gep Ptr, (select C, 0, Idx))4424 auto SelectGepWithBase = [&](GetElementPtrInst *Gep, Value *Base,4425 bool Swap) -> GetElementPtrInst * {4426 Value *Ptr = Gep->getPointerOperand();4427 if (Gep->getNumOperands() != 2 || Gep->getPointerOperand() != Base ||4428 !Gep->hasOneUse())4429 return nullptr;4430 Value *Idx = Gep->getOperand(1);4431 if (isa<VectorType>(CondVal->getType()) && !isa<VectorType>(Idx->getType()))4432 return nullptr;4433 Type *ElementType = Gep->getSourceElementType();4434 Value *NewT = Idx;4435 Value *NewF = Constant::getNullValue(Idx->getType());4436 if (Swap)4437 std::swap(NewT, NewF);4438 Value *NewSI =4439 Builder.CreateSelect(CondVal, NewT, NewF, SI.getName() + ".idx", &SI);4440 return GetElementPtrInst::Create(ElementType, Ptr, NewSI,4441 Gep->getNoWrapFlags());4442 };4443 if (auto *TrueGep = dyn_cast<GetElementPtrInst>(TrueVal))4444 if (auto *NewGep = SelectGepWithBase(TrueGep, FalseVal, false))4445 return NewGep;4446 if (auto *FalseGep = dyn_cast<GetElementPtrInst>(FalseVal))4447 if (auto *NewGep = SelectGepWithBase(FalseGep, TrueVal, true))4448 return NewGep;4449 4450 // See if we can fold the select into one of our operands.4451 if (SelType->isIntOrIntVectorTy() || SelType->isFPOrFPVectorTy()) {4452 if (Instruction *FoldI = foldSelectIntoOp(SI, TrueVal, FalseVal))4453 return FoldI;4454 4455 Value *LHS, *RHS;4456 Instruction::CastOps CastOp;4457 SelectPatternResult SPR = matchSelectPattern(&SI, LHS, RHS, &CastOp);4458 auto SPF = SPR.Flavor;4459 if (SPF) {4460 Value *LHS2, *RHS2;4461 if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor)4462 if (Instruction *R = foldSPFofSPF(cast<Instruction>(LHS), SPF2, LHS2,4463 RHS2, SI, SPF, RHS))4464 return R;4465 if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor)4466 if (Instruction *R = foldSPFofSPF(cast<Instruction>(RHS), SPF2, LHS2,4467 RHS2, SI, SPF, LHS))4468 return R;4469 }4470 4471 if (SelectPatternResult::isMinOrMax(SPF)) {4472 // Canonicalize so that4473 // - type casts are outside select patterns.4474 // - float clamp is transformed to min/max pattern4475 4476 bool IsCastNeeded = LHS->getType() != SelType;4477 Value *CmpLHS = cast<CmpInst>(CondVal)->getOperand(0);4478 Value *CmpRHS = cast<CmpInst>(CondVal)->getOperand(1);4479 if (IsCastNeeded ||4480 (LHS->getType()->isFPOrFPVectorTy() &&4481 ((CmpLHS != LHS && CmpLHS != RHS) ||4482 (CmpRHS != LHS && CmpRHS != RHS)))) {4483 CmpInst::Predicate MinMaxPred = getMinMaxPred(SPF, SPR.Ordered);4484 4485 Value *Cmp;4486 if (CmpInst::isIntPredicate(MinMaxPred))4487 Cmp = Builder.CreateICmp(MinMaxPred, LHS, RHS);4488 else4489 Cmp = Builder.CreateFCmpFMF(MinMaxPred, LHS, RHS,4490 cast<Instruction>(SI.getCondition()));4491 4492 Value *NewSI = Builder.CreateSelect(Cmp, LHS, RHS, SI.getName(), &SI);4493 if (!IsCastNeeded)4494 return replaceInstUsesWith(SI, NewSI);4495 4496 Value *NewCast = Builder.CreateCast(CastOp, NewSI, SelType);4497 return replaceInstUsesWith(SI, NewCast);4498 }4499 }4500 }4501 4502 // See if we can fold the select into a phi node if the condition is a select.4503 if (auto *PN = dyn_cast<PHINode>(SI.getCondition()))4504 if (Instruction *NV = foldOpIntoPhi(SI, PN))4505 return NV;4506 4507 if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) {4508 if (TrueSI->getCondition()->getType() == CondVal->getType()) {4509 // Fold nested selects if the inner condition can be implied by the outer4510 // condition.4511 if (Value *V = simplifyNestedSelectsUsingImpliedCond(4512 *TrueSI, CondVal, /*CondIsTrue=*/true, DL))4513 return replaceOperand(SI, 1, V);4514 4515 // select(C0, select(C1, a, b), b) -> select(C0&C1, a, b)4516 // We choose this as normal form to enable folding on the And and4517 // shortening paths for the values (this helps getUnderlyingObjects() for4518 // example).4519 if (TrueSI->getFalseValue() == FalseVal && TrueSI->hasOneUse()) {4520 Value *And = Builder.CreateLogicalAnd(CondVal, TrueSI->getCondition());4521 replaceOperand(SI, 0, And);4522 replaceOperand(SI, 1, TrueSI->getTrueValue());4523 return &SI;4524 }4525 }4526 }4527 if (SelectInst *FalseSI = dyn_cast<SelectInst>(FalseVal)) {4528 if (FalseSI->getCondition()->getType() == CondVal->getType()) {4529 // Fold nested selects if the inner condition can be implied by the outer4530 // condition.4531 if (Value *V = simplifyNestedSelectsUsingImpliedCond(4532 *FalseSI, CondVal, /*CondIsTrue=*/false, DL))4533 return replaceOperand(SI, 2, V);4534 4535 // select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b)4536 if (FalseSI->getTrueValue() == TrueVal && FalseSI->hasOneUse()) {4537 Value *Or = Builder.CreateLogicalOr(CondVal, FalseSI->getCondition());4538 replaceOperand(SI, 0, Or);4539 replaceOperand(SI, 2, FalseSI->getFalseValue());4540 return &SI;4541 }4542 }4543 }4544 4545 // Try to simplify a binop sandwiched between 2 selects with the same4546 // condition. This is not valid for div/rem because the select might be4547 // preventing a division-by-zero.4548 // TODO: A div/rem restriction is conservative; use something like4549 // isSafeToSpeculativelyExecute().4550 // select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z)4551 BinaryOperator *TrueBO;4552 if (match(TrueVal, m_OneUse(m_BinOp(TrueBO))) && !TrueBO->isIntDivRem()) {4553 if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(0))) {4554 if (TrueBOSI->getCondition() == CondVal) {4555 replaceOperand(*TrueBO, 0, TrueBOSI->getTrueValue());4556 Worklist.push(TrueBO);4557 return &SI;4558 }4559 }4560 if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(1))) {4561 if (TrueBOSI->getCondition() == CondVal) {4562 replaceOperand(*TrueBO, 1, TrueBOSI->getTrueValue());4563 Worklist.push(TrueBO);4564 return &SI;4565 }4566 }4567 }4568 4569 // select(C, Z, binop(select(C, X, Y), W)) -> select(C, Z, binop(Y, W))4570 BinaryOperator *FalseBO;4571 if (match(FalseVal, m_OneUse(m_BinOp(FalseBO))) && !FalseBO->isIntDivRem()) {4572 if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(0))) {4573 if (FalseBOSI->getCondition() == CondVal) {4574 replaceOperand(*FalseBO, 0, FalseBOSI->getFalseValue());4575 Worklist.push(FalseBO);4576 return &SI;4577 }4578 }4579 if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(1))) {4580 if (FalseBOSI->getCondition() == CondVal) {4581 replaceOperand(*FalseBO, 1, FalseBOSI->getFalseValue());4582 Worklist.push(FalseBO);4583 return &SI;4584 }4585 }4586 }4587 4588 Value *NotCond;4589 if (match(CondVal, m_Not(m_Value(NotCond))) &&4590 !InstCombiner::shouldAvoidAbsorbingNotIntoSelect(SI)) {4591 replaceOperand(SI, 0, NotCond);4592 SI.swapValues();4593 SI.swapProfMetadata();4594 return &SI;4595 }4596 4597 if (Instruction *I = foldVectorSelect(SI))4598 return I;4599 4600 // If we can compute the condition, there's no need for a select.4601 // Like the above fold, we are attempting to reduce compile-time cost by4602 // putting this fold here with limitations rather than in InstSimplify.4603 // The motivation for this call into value tracking is to take advantage of4604 // the assumption cache, so make sure that is populated.4605 if (!CondVal->getType()->isVectorTy() && !AC.assumptions().empty()) {4606 KnownBits Known(1);4607 computeKnownBits(CondVal, Known, &SI);4608 if (Known.One.isOne())4609 return replaceInstUsesWith(SI, TrueVal);4610 if (Known.Zero.isOne())4611 return replaceInstUsesWith(SI, FalseVal);4612 }4613 4614 if (Instruction *BitCastSel = foldSelectCmpBitcasts(SI, Builder))4615 return BitCastSel;4616 4617 // Simplify selects that test the returned flag of cmpxchg instructions.4618 if (Value *V = foldSelectCmpXchg(SI))4619 return replaceInstUsesWith(SI, V);4620 4621 if (Instruction *Select = foldSelectBinOpIdentity(SI, TLI, *this))4622 return Select;4623 4624 if (Instruction *Funnel = foldSelectFunnelShift(SI, Builder))4625 return Funnel;4626 4627 if (Instruction *Copysign = foldSelectToCopysign(SI, Builder))4628 return Copysign;4629 4630 if (Instruction *PN = foldSelectToPhi(SI, DT, Builder))4631 return replaceInstUsesWith(SI, PN);4632 4633 if (Value *V = foldRoundUpIntegerWithPow2Alignment(SI, Builder))4634 return replaceInstUsesWith(SI, V);4635 4636 if (Value *V = foldSelectIntoAddConstant(SI, Builder))4637 return replaceInstUsesWith(SI, V);4638 4639 // select(mask, mload(ptr,mask,0), 0) -> mload(ptr,mask,0)4640 // Load inst is intentionally not checked for hasOneUse()4641 if (match(FalseVal, m_Zero()) &&4642 (match(TrueVal, m_MaskedLoad(m_Value(), m_Specific(CondVal),4643 m_CombineOr(m_Undef(), m_Zero()))) ||4644 match(TrueVal, m_MaskedGather(m_Value(), m_Specific(CondVal),4645 m_CombineOr(m_Undef(), m_Zero()))))) {4646 auto *MaskedInst = cast<IntrinsicInst>(TrueVal);4647 if (isa<UndefValue>(MaskedInst->getArgOperand(2)))4648 MaskedInst->setArgOperand(2, FalseVal /* Zero */);4649 return replaceInstUsesWith(SI, MaskedInst);4650 }4651 4652 Value *Mask;4653 if (match(TrueVal, m_Zero()) &&4654 (match(FalseVal, m_MaskedLoad(m_Value(), m_Value(Mask),4655 m_CombineOr(m_Undef(), m_Zero()))) ||4656 match(FalseVal, m_MaskedGather(m_Value(), m_Value(Mask),4657 m_CombineOr(m_Undef(), m_Zero())))) &&4658 (CondVal->getType() == Mask->getType())) {4659 // We can remove the select by ensuring the load zeros all lanes the4660 // select would have. We determine this by proving there is no overlap4661 // between the load and select masks.4662 // (i.e (load_mask & select_mask) == 0 == no overlap)4663 bool CanMergeSelectIntoLoad = false;4664 if (Value *V = simplifyAndInst(CondVal, Mask, SQ.getWithInstruction(&SI)))4665 CanMergeSelectIntoLoad = match(V, m_Zero());4666 4667 if (CanMergeSelectIntoLoad) {4668 auto *MaskedInst = cast<IntrinsicInst>(FalseVal);4669 if (isa<UndefValue>(MaskedInst->getArgOperand(2)))4670 MaskedInst->setArgOperand(2, TrueVal /* Zero */);4671 return replaceInstUsesWith(SI, MaskedInst);4672 }4673 }4674 4675 if (Instruction *I = foldSelectOfSymmetricSelect(SI, Builder))4676 return I;4677 4678 if (Instruction *I = foldNestedSelects(SI, Builder))4679 return I;4680 4681 // Match logical variants of the pattern,4682 // and transform them iff that gets rid of inversions.4683 // (~x) | y --> ~(x & (~y))4684 // (~x) & y --> ~(x | (~y))4685 if (sinkNotIntoOtherHandOfLogicalOp(SI))4686 return &SI;4687 4688 if (Instruction *I = foldBitCeil(SI, Builder, *this))4689 return I;4690 4691 if (Instruction *I = foldSelectToCmp(SI))4692 return I;4693 4694 if (Instruction *I = foldSelectEqualityTest(SI))4695 return I;4696 4697 // Fold:4698 // (select A && B, T, F) -> (select A, (select B, T, F), F)4699 // (select A || B, T, F) -> (select A, T, (select B, T, F))4700 // if (select B, T, F) is foldable.4701 // TODO: preserve FMF flags4702 auto FoldSelectWithAndOrCond = [&](bool IsAnd, Value *A,4703 Value *B) -> Instruction * {4704 if (Value *V = simplifySelectInst(B, TrueVal, FalseVal,4705 SQ.getWithInstruction(&SI))) {4706 Value *NewTrueVal = IsAnd ? V : TrueVal;4707 Value *NewFalseVal = IsAnd ? FalseVal : V;4708 4709 // If the True and False values don't change, then preserve the branch4710 // metadata of the original select as the net effect of this change is to4711 // simplify the conditional.4712 Instruction *MDFrom = nullptr;4713 if (NewTrueVal == TrueVal && NewFalseVal == FalseVal &&4714 !ProfcheckDisableMetadataFixes) {4715 MDFrom = &SI;4716 }4717 return SelectInst::Create(A, NewTrueVal, NewFalseVal, "", nullptr,4718 MDFrom);4719 }4720 4721 // Is (select B, T, F) a SPF?4722 if (CondVal->hasOneUse() && SelType->isIntOrIntVectorTy()) {4723 if (ICmpInst *Cmp = dyn_cast<ICmpInst>(B))4724 if (Value *V = canonicalizeSPF(*Cmp, TrueVal, FalseVal, *this))4725 return SelectInst::Create(A, IsAnd ? V : TrueVal,4726 IsAnd ? FalseVal : V);4727 }4728 4729 return nullptr;4730 };4731 4732 Value *LHS, *RHS;4733 if (match(CondVal, m_And(m_Value(LHS), m_Value(RHS)))) {4734 if (Instruction *I = FoldSelectWithAndOrCond(/*IsAnd*/ true, LHS, RHS))4735 return I;4736 if (Instruction *I = FoldSelectWithAndOrCond(/*IsAnd*/ true, RHS, LHS))4737 return I;4738 } else if (match(CondVal, m_Or(m_Value(LHS), m_Value(RHS)))) {4739 if (Instruction *I = FoldSelectWithAndOrCond(/*IsAnd*/ false, LHS, RHS))4740 return I;4741 if (Instruction *I = FoldSelectWithAndOrCond(/*IsAnd*/ false, RHS, LHS))4742 return I;4743 } else {4744 // We cannot swap the operands of logical and/or.4745 // TODO: Can we swap the operands by inserting a freeze?4746 if (match(CondVal, m_LogicalAnd(m_Value(LHS), m_Value(RHS)))) {4747 if (Instruction *I = FoldSelectWithAndOrCond(/*IsAnd*/ true, LHS, RHS))4748 return I;4749 } else if (match(CondVal, m_LogicalOr(m_Value(LHS), m_Value(RHS)))) {4750 if (Instruction *I = FoldSelectWithAndOrCond(/*IsAnd*/ false, LHS, RHS))4751 return I;4752 }4753 }4754 4755 // select Cond, !X, X -> xor Cond, X4756 if (CondVal->getType() == SI.getType() && isKnownInversion(FalseVal, TrueVal))4757 return BinaryOperator::CreateXor(CondVal, FalseVal);4758 4759 // For vectors, this transform is only safe if the simplification does not4760 // look through any lane-crossing operations. For now, limit to scalars only.4761 if (SelType->isIntegerTy() &&4762 (!isa<Constant>(TrueVal) || !isa<Constant>(FalseVal))) {4763 // Try to simplify select arms based on KnownBits implied by the condition.4764 CondContext CC(CondVal);4765 findValuesAffectedByCondition(CondVal, /*IsAssume=*/false, [&](Value *V) {4766 CC.AffectedValues.insert(V);4767 });4768 SimplifyQuery Q = SQ.getWithInstruction(&SI).getWithCondContext(CC);4769 if (!CC.AffectedValues.empty()) {4770 if (!isa<Constant>(TrueVal) &&4771 hasAffectedValue(TrueVal, CC.AffectedValues, /*Depth=*/0)) {4772 KnownBits Known = llvm::computeKnownBits(TrueVal, Q);4773 if (Known.isConstant())4774 return replaceOperand(SI, 1,4775 ConstantInt::get(SelType, Known.getConstant()));4776 }4777 4778 CC.Invert = true;4779 if (!isa<Constant>(FalseVal) &&4780 hasAffectedValue(FalseVal, CC.AffectedValues, /*Depth=*/0)) {4781 KnownBits Known = llvm::computeKnownBits(FalseVal, Q);4782 if (Known.isConstant())4783 return replaceOperand(SI, 2,4784 ConstantInt::get(SelType, Known.getConstant()));4785 }4786 }4787 }4788 4789 // select (trunc nuw X to i1), X, Y --> select (trunc nuw X to i1), 1, Y4790 // select (trunc nuw X to i1), Y, X --> select (trunc nuw X to i1), Y, 04791 // select (trunc nsw X to i1), X, Y --> select (trunc nsw X to i1), -1, Y4792 // select (trunc nsw X to i1), Y, X --> select (trunc nsw X to i1), Y, 04793 Value *Trunc;4794 if (match(CondVal, m_NUWTrunc(m_Value(Trunc)))) {4795 if (TrueVal == Trunc)4796 return replaceOperand(SI, 1, ConstantInt::get(TrueVal->getType(), 1));4797 if (FalseVal == Trunc)4798 return replaceOperand(SI, 2, ConstantInt::get(FalseVal->getType(), 0));4799 }4800 if (match(CondVal, m_NSWTrunc(m_Value(Trunc)))) {4801 if (TrueVal == Trunc)4802 return replaceOperand(SI, 1,4803 Constant::getAllOnesValue(TrueVal->getType()));4804 if (FalseVal == Trunc)4805 return replaceOperand(SI, 2, ConstantInt::get(FalseVal->getType(), 0));4806 }4807 4808 Value *MaskedLoadPtr;4809 if (match(TrueVal, m_OneUse(m_MaskedLoad(m_Value(MaskedLoadPtr),4810 m_Specific(CondVal), m_Value()))))4811 return replaceInstUsesWith(4812 SI, Builder.CreateMaskedLoad(4813 TrueVal->getType(), MaskedLoadPtr,4814 cast<IntrinsicInst>(TrueVal)->getParamAlign(0).valueOrOne(),4815 CondVal, FalseVal));4816 4817 // Canonicalize sign function ashr pattern: select (icmp slt X, 1), ashr X,4818 // bitwidth-1, 1 -> scmp(X, 0)4819 // Also handles: select (icmp sgt X, 0), 1, ashr X, bitwidth-1 -> scmp(X, 0)4820 unsigned BitWidth = SI.getType()->getScalarSizeInBits();4821 CmpPredicate Pred;4822 Value *CmpLHS, *CmpRHS;4823 4824 // Canonicalize sign function ashr patterns:4825 // select (icmp slt X, 1), ashr X, bitwidth-1, 1 -> scmp(X, 0)4826 // select (icmp sgt X, 0), 1, ashr X, bitwidth-1 -> scmp(X, 0)4827 if (match(&SI, m_Select(m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS)),4828 m_Value(TrueVal), m_Value(FalseVal))) &&4829 ((Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_One()) &&4830 match(TrueVal,4831 m_AShr(m_Specific(CmpLHS), m_SpecificInt(BitWidth - 1))) &&4832 match(FalseVal, m_One())) ||4833 (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_Zero()) &&4834 match(TrueVal, m_One()) &&4835 match(FalseVal,4836 m_AShr(m_Specific(CmpLHS), m_SpecificInt(BitWidth - 1)))))) {4837 4838 Function *Scmp = Intrinsic::getOrInsertDeclaration(4839 SI.getModule(), Intrinsic::scmp, {SI.getType(), SI.getType()});4840 return CallInst::Create(Scmp, {CmpLHS, ConstantInt::get(SI.getType(), 0)});4841 }4842 4843 return nullptr;4844}4845