1 //===- InstCombineSelect.cpp ----------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the visitSelect function. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "InstCombineInternal.h" 15 #include "llvm/ADT/APInt.h" 16 #include "llvm/ADT/Optional.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/Analysis/AssumptionCache.h" 20 #include "llvm/Analysis/CmpInstAnalysis.h" 21 #include "llvm/Analysis/InstructionSimplify.h" 22 #include "llvm/Analysis/ValueTracking.h" 23 #include "llvm/IR/BasicBlock.h" 24 #include "llvm/IR/Constant.h" 25 #include "llvm/IR/Constants.h" 26 #include "llvm/IR/DerivedTypes.h" 27 #include "llvm/IR/IRBuilder.h" 28 #include "llvm/IR/InstrTypes.h" 29 #include "llvm/IR/Instruction.h" 30 #include "llvm/IR/Instructions.h" 31 #include "llvm/IR/IntrinsicInst.h" 32 #include "llvm/IR/Intrinsics.h" 33 #include "llvm/IR/Operator.h" 34 #include "llvm/IR/PatternMatch.h" 35 #include "llvm/IR/Type.h" 36 #include "llvm/IR/User.h" 37 #include "llvm/IR/Value.h" 38 #include "llvm/Support/Casting.h" 39 #include "llvm/Support/ErrorHandling.h" 40 #include "llvm/Support/KnownBits.h" 41 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h" 42 #include <cassert> 43 #include <utility> 44 45 using namespace llvm; 46 using namespace PatternMatch; 47 48 #define DEBUG_TYPE "instcombine" 49 50 static Value *createMinMax(InstCombiner::BuilderTy &Builder, 51 SelectPatternFlavor SPF, Value *A, Value *B) { 52 CmpInst::Predicate Pred = getMinMaxPred(SPF); 53 assert(CmpInst::isIntPredicate(Pred) && "Expected integer predicate"); 54 return Builder.CreateSelect(Builder.CreateICmp(Pred, A, B), A, B); 55 } 56 57 /// Fold 58 /// %A = icmp eq/ne i8 %x, 0 59 /// %B = op i8 %x, %z 60 /// %C = select i1 %A, i8 %B, i8 %y 61 /// To 62 /// %C = select i1 %A, i8 %z, i8 %y 63 /// OP: binop with an identity constant 64 /// TODO: support for non-commutative and FP opcodes 65 static Instruction *foldSelectBinOpIdentity(SelectInst &Sel) { 66 67 Value *Cond = Sel.getCondition(); 68 Value *X, *Z; 69 Constant *C; 70 CmpInst::Predicate Pred; 71 if (!match(Cond, m_ICmp(Pred, m_Value(X), m_Constant(C))) || 72 !ICmpInst::isEquality(Pred)) 73 return nullptr; 74 75 bool IsEq = Pred == ICmpInst::ICMP_EQ; 76 auto *BO = 77 dyn_cast<BinaryOperator>(IsEq ? Sel.getTrueValue() : Sel.getFalseValue()); 78 // TODO: support for undefs 79 if (BO && match(BO, m_c_BinOp(m_Specific(X), m_Value(Z))) && 80 ConstantExpr::getBinOpIdentity(BO->getOpcode(), X->getType()) == C) { 81 Sel.setOperand(IsEq ? 1 : 2, Z); 82 return &Sel; 83 } 84 return nullptr; 85 } 86 87 /// This folds: 88 /// select (icmp eq (and X, C1)), TC, FC 89 /// iff C1 is a power 2 and the difference between TC and FC is a power-of-2. 90 /// To something like: 91 /// (shr (and (X, C1)), (log2(C1) - log2(TC-FC))) + FC 92 /// Or: 93 /// (shl (and (X, C1)), (log2(TC-FC) - log2(C1))) + FC 94 /// With some variations depending if FC is larger than TC, or the shift 95 /// isn't needed, or the bit widths don't match. 96 static Value *foldSelectICmpAnd(SelectInst &Sel, ICmpInst *Cmp, 97 InstCombiner::BuilderTy &Builder) { 98 const APInt *SelTC, *SelFC; 99 if (!match(Sel.getTrueValue(), m_APInt(SelTC)) || 100 !match(Sel.getFalseValue(), m_APInt(SelFC))) 101 return nullptr; 102 103 // If this is a vector select, we need a vector compare. 104 Type *SelType = Sel.getType(); 105 if (SelType->isVectorTy() != Cmp->getType()->isVectorTy()) 106 return nullptr; 107 108 Value *V; 109 APInt AndMask; 110 bool CreateAnd = false; 111 ICmpInst::Predicate Pred = Cmp->getPredicate(); 112 if (ICmpInst::isEquality(Pred)) { 113 if (!match(Cmp->getOperand(1), m_Zero())) 114 return nullptr; 115 116 V = Cmp->getOperand(0); 117 const APInt *AndRHS; 118 if (!match(V, m_And(m_Value(), m_Power2(AndRHS)))) 119 return nullptr; 120 121 AndMask = *AndRHS; 122 } else if (decomposeBitTestICmp(Cmp->getOperand(0), Cmp->getOperand(1), 123 Pred, V, AndMask)) { 124 assert(ICmpInst::isEquality(Pred) && "Not equality test?"); 125 if (!AndMask.isPowerOf2()) 126 return nullptr; 127 128 CreateAnd = true; 129 } else { 130 return nullptr; 131 } 132 133 // In general, when both constants are non-zero, we would need an offset to 134 // replace the select. This would require more instructions than we started 135 // with. But there's one special-case that we handle here because it can 136 // simplify/reduce the instructions. 137 APInt TC = *SelTC; 138 APInt FC = *SelFC; 139 if (!TC.isNullValue() && !FC.isNullValue()) { 140 // If the select constants differ by exactly one bit and that's the same 141 // bit that is masked and checked by the select condition, the select can 142 // be replaced by bitwise logic to set/clear one bit of the constant result. 143 if (TC.getBitWidth() != AndMask.getBitWidth() || (TC ^ FC) != AndMask) 144 return nullptr; 145 if (CreateAnd) { 146 // If we have to create an 'and', then we must kill the cmp to not 147 // increase the instruction count. 148 if (!Cmp->hasOneUse()) 149 return nullptr; 150 V = Builder.CreateAnd(V, ConstantInt::get(SelType, AndMask)); 151 } 152 bool ExtraBitInTC = TC.ugt(FC); 153 if (Pred == ICmpInst::ICMP_EQ) { 154 // If the masked bit in V is clear, clear or set the bit in the result: 155 // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) ^ TC 156 // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) | TC 157 Constant *C = ConstantInt::get(SelType, TC); 158 return ExtraBitInTC ? Builder.CreateXor(V, C) : Builder.CreateOr(V, C); 159 } 160 if (Pred == ICmpInst::ICMP_NE) { 161 // If the masked bit in V is set, set or clear the bit in the result: 162 // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) | FC 163 // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) ^ FC 164 Constant *C = ConstantInt::get(SelType, FC); 165 return ExtraBitInTC ? Builder.CreateOr(V, C) : Builder.CreateXor(V, C); 166 } 167 llvm_unreachable("Only expecting equality predicates"); 168 } 169 170 // Make sure one of the select arms is a power-of-2. 171 if (!TC.isPowerOf2() && !FC.isPowerOf2()) 172 return nullptr; 173 174 // Determine which shift is needed to transform result of the 'and' into the 175 // desired result. 176 const APInt &ValC = !TC.isNullValue() ? TC : FC; 177 unsigned ValZeros = ValC.logBase2(); 178 unsigned AndZeros = AndMask.logBase2(); 179 180 // Insert the 'and' instruction on the input to the truncate. 181 if (CreateAnd) 182 V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), AndMask)); 183 184 // If types don't match, we can still convert the select by introducing a zext 185 // or a trunc of the 'and'. 186 if (ValZeros > AndZeros) { 187 V = Builder.CreateZExtOrTrunc(V, SelType); 188 V = Builder.CreateShl(V, ValZeros - AndZeros); 189 } else if (ValZeros < AndZeros) { 190 V = Builder.CreateLShr(V, AndZeros - ValZeros); 191 V = Builder.CreateZExtOrTrunc(V, SelType); 192 } else { 193 V = Builder.CreateZExtOrTrunc(V, SelType); 194 } 195 196 // Okay, now we know that everything is set up, we just don't know whether we 197 // have a icmp_ne or icmp_eq and whether the true or false val is the zero. 198 bool ShouldNotVal = !TC.isNullValue(); 199 ShouldNotVal ^= Pred == ICmpInst::ICMP_NE; 200 if (ShouldNotVal) 201 V = Builder.CreateXor(V, ValC); 202 203 return V; 204 } 205 206 /// We want to turn code that looks like this: 207 /// %C = or %A, %B 208 /// %D = select %cond, %C, %A 209 /// into: 210 /// %C = select %cond, %B, 0 211 /// %D = or %A, %C 212 /// 213 /// Assuming that the specified instruction is an operand to the select, return 214 /// a bitmask indicating which operands of this instruction are foldable if they 215 /// equal the other incoming value of the select. 216 static unsigned getSelectFoldableOperands(BinaryOperator *I) { 217 switch (I->getOpcode()) { 218 case Instruction::Add: 219 case Instruction::Mul: 220 case Instruction::And: 221 case Instruction::Or: 222 case Instruction::Xor: 223 return 3; // Can fold through either operand. 224 case Instruction::Sub: // Can only fold on the amount subtracted. 225 case Instruction::Shl: // Can only fold on the shift amount. 226 case Instruction::LShr: 227 case Instruction::AShr: 228 return 1; 229 default: 230 return 0; // Cannot fold 231 } 232 } 233 234 /// For the same transformation as the previous function, return the identity 235 /// constant that goes into the select. 236 static APInt getSelectFoldableConstant(BinaryOperator *I) { 237 switch (I->getOpcode()) { 238 default: llvm_unreachable("This cannot happen!"); 239 case Instruction::Add: 240 case Instruction::Sub: 241 case Instruction::Or: 242 case Instruction::Xor: 243 case Instruction::Shl: 244 case Instruction::LShr: 245 case Instruction::AShr: 246 return APInt::getNullValue(I->getType()->getScalarSizeInBits()); 247 case Instruction::And: 248 return APInt::getAllOnesValue(I->getType()->getScalarSizeInBits()); 249 case Instruction::Mul: 250 return APInt(I->getType()->getScalarSizeInBits(), 1); 251 } 252 } 253 254 /// We have (select c, TI, FI), and we know that TI and FI have the same opcode. 255 Instruction *InstCombiner::foldSelectOpOp(SelectInst &SI, Instruction *TI, 256 Instruction *FI) { 257 // Don't break up min/max patterns. The hasOneUse checks below prevent that 258 // for most cases, but vector min/max with bitcasts can be transformed. If the 259 // one-use restrictions are eased for other patterns, we still don't want to 260 // obfuscate min/max. 261 if ((match(&SI, m_SMin(m_Value(), m_Value())) || 262 match(&SI, m_SMax(m_Value(), m_Value())) || 263 match(&SI, m_UMin(m_Value(), m_Value())) || 264 match(&SI, m_UMax(m_Value(), m_Value())))) 265 return nullptr; 266 267 // If this is a cast from the same type, merge. 268 if (TI->getNumOperands() == 1 && TI->isCast()) { 269 Type *FIOpndTy = FI->getOperand(0)->getType(); 270 if (TI->getOperand(0)->getType() != FIOpndTy) 271 return nullptr; 272 273 // The select condition may be a vector. We may only change the operand 274 // type if the vector width remains the same (and matches the condition). 275 Type *CondTy = SI.getCondition()->getType(); 276 if (CondTy->isVectorTy()) { 277 if (!FIOpndTy->isVectorTy()) 278 return nullptr; 279 if (CondTy->getVectorNumElements() != FIOpndTy->getVectorNumElements()) 280 return nullptr; 281 282 // TODO: If the backend knew how to deal with casts better, we could 283 // remove this limitation. For now, there's too much potential to create 284 // worse codegen by promoting the select ahead of size-altering casts 285 // (PR28160). 286 // 287 // Note that ValueTracking's matchSelectPattern() looks through casts 288 // without checking 'hasOneUse' when it matches min/max patterns, so this 289 // transform may end up happening anyway. 290 if (TI->getOpcode() != Instruction::BitCast && 291 (!TI->hasOneUse() || !FI->hasOneUse())) 292 return nullptr; 293 } else if (!TI->hasOneUse() || !FI->hasOneUse()) { 294 // TODO: The one-use restrictions for a scalar select could be eased if 295 // the fold of a select in visitLoadInst() was enhanced to match a pattern 296 // that includes a cast. 297 return nullptr; 298 } 299 300 // Fold this by inserting a select from the input values. 301 Value *NewSI = 302 Builder.CreateSelect(SI.getCondition(), TI->getOperand(0), 303 FI->getOperand(0), SI.getName() + ".v", &SI); 304 return CastInst::Create(Instruction::CastOps(TI->getOpcode()), NewSI, 305 TI->getType()); 306 } 307 308 // Only handle binary operators (including two-operand getelementptr) with 309 // one-use here. As with the cast case above, it may be possible to relax the 310 // one-use constraint, but that needs be examined carefully since it may not 311 // reduce the total number of instructions. 312 if (TI->getNumOperands() != 2 || FI->getNumOperands() != 2 || 313 (!isa<BinaryOperator>(TI) && !isa<GetElementPtrInst>(TI)) || 314 !TI->hasOneUse() || !FI->hasOneUse()) 315 return nullptr; 316 317 // Figure out if the operations have any operands in common. 318 Value *MatchOp, *OtherOpT, *OtherOpF; 319 bool MatchIsOpZero; 320 if (TI->getOperand(0) == FI->getOperand(0)) { 321 MatchOp = TI->getOperand(0); 322 OtherOpT = TI->getOperand(1); 323 OtherOpF = FI->getOperand(1); 324 MatchIsOpZero = true; 325 } else if (TI->getOperand(1) == FI->getOperand(1)) { 326 MatchOp = TI->getOperand(1); 327 OtherOpT = TI->getOperand(0); 328 OtherOpF = FI->getOperand(0); 329 MatchIsOpZero = false; 330 } else if (!TI->isCommutative()) { 331 return nullptr; 332 } else if (TI->getOperand(0) == FI->getOperand(1)) { 333 MatchOp = TI->getOperand(0); 334 OtherOpT = TI->getOperand(1); 335 OtherOpF = FI->getOperand(0); 336 MatchIsOpZero = true; 337 } else if (TI->getOperand(1) == FI->getOperand(0)) { 338 MatchOp = TI->getOperand(1); 339 OtherOpT = TI->getOperand(0); 340 OtherOpF = FI->getOperand(1); 341 MatchIsOpZero = true; 342 } else { 343 return nullptr; 344 } 345 346 // If we reach here, they do have operations in common. 347 Value *NewSI = Builder.CreateSelect(SI.getCondition(), OtherOpT, OtherOpF, 348 SI.getName() + ".v", &SI); 349 Value *Op0 = MatchIsOpZero ? MatchOp : NewSI; 350 Value *Op1 = MatchIsOpZero ? NewSI : MatchOp; 351 if (auto *BO = dyn_cast<BinaryOperator>(TI)) { 352 return BinaryOperator::Create(BO->getOpcode(), Op0, Op1); 353 } 354 if (auto *TGEP = dyn_cast<GetElementPtrInst>(TI)) { 355 auto *FGEP = cast<GetElementPtrInst>(FI); 356 Type *ElementType = TGEP->getResultElementType(); 357 return TGEP->isInBounds() && FGEP->isInBounds() 358 ? GetElementPtrInst::CreateInBounds(ElementType, Op0, {Op1}) 359 : GetElementPtrInst::Create(ElementType, Op0, {Op1}); 360 } 361 llvm_unreachable("Expected BinaryOperator or GEP"); 362 return nullptr; 363 } 364 365 static bool isSelect01(const APInt &C1I, const APInt &C2I) { 366 if (!C1I.isNullValue() && !C2I.isNullValue()) // One side must be zero. 367 return false; 368 return C1I.isOneValue() || C1I.isAllOnesValue() || 369 C2I.isOneValue() || C2I.isAllOnesValue(); 370 } 371 372 /// Try to fold the select into one of the operands to allow further 373 /// optimization. 374 Instruction *InstCombiner::foldSelectIntoOp(SelectInst &SI, Value *TrueVal, 375 Value *FalseVal) { 376 // See the comment above GetSelectFoldableOperands for a description of the 377 // transformation we are doing here. 378 if (auto *TVI = dyn_cast<BinaryOperator>(TrueVal)) { 379 if (TVI->hasOneUse() && !isa<Constant>(FalseVal)) { 380 if (unsigned SFO = getSelectFoldableOperands(TVI)) { 381 unsigned OpToFold = 0; 382 if ((SFO & 1) && FalseVal == TVI->getOperand(0)) { 383 OpToFold = 1; 384 } else if ((SFO & 2) && FalseVal == TVI->getOperand(1)) { 385 OpToFold = 2; 386 } 387 388 if (OpToFold) { 389 APInt CI = getSelectFoldableConstant(TVI); 390 Value *OOp = TVI->getOperand(2-OpToFold); 391 // Avoid creating select between 2 constants unless it's selecting 392 // between 0, 1 and -1. 393 const APInt *OOpC; 394 bool OOpIsAPInt = match(OOp, m_APInt(OOpC)); 395 if (!isa<Constant>(OOp) || (OOpIsAPInt && isSelect01(CI, *OOpC))) { 396 Value *C = ConstantInt::get(OOp->getType(), CI); 397 Value *NewSel = Builder.CreateSelect(SI.getCondition(), OOp, C); 398 NewSel->takeName(TVI); 399 BinaryOperator *BO = BinaryOperator::Create(TVI->getOpcode(), 400 FalseVal, NewSel); 401 BO->copyIRFlags(TVI); 402 return BO; 403 } 404 } 405 } 406 } 407 } 408 409 if (auto *FVI = dyn_cast<BinaryOperator>(FalseVal)) { 410 if (FVI->hasOneUse() && !isa<Constant>(TrueVal)) { 411 if (unsigned SFO = getSelectFoldableOperands(FVI)) { 412 unsigned OpToFold = 0; 413 if ((SFO & 1) && TrueVal == FVI->getOperand(0)) { 414 OpToFold = 1; 415 } else if ((SFO & 2) && TrueVal == FVI->getOperand(1)) { 416 OpToFold = 2; 417 } 418 419 if (OpToFold) { 420 APInt CI = getSelectFoldableConstant(FVI); 421 Value *OOp = FVI->getOperand(2-OpToFold); 422 // Avoid creating select between 2 constants unless it's selecting 423 // between 0, 1 and -1. 424 const APInt *OOpC; 425 bool OOpIsAPInt = match(OOp, m_APInt(OOpC)); 426 if (!isa<Constant>(OOp) || (OOpIsAPInt && isSelect01(CI, *OOpC))) { 427 Value *C = ConstantInt::get(OOp->getType(), CI); 428 Value *NewSel = Builder.CreateSelect(SI.getCondition(), C, OOp); 429 NewSel->takeName(FVI); 430 BinaryOperator *BO = BinaryOperator::Create(FVI->getOpcode(), 431 TrueVal, NewSel); 432 BO->copyIRFlags(FVI); 433 return BO; 434 } 435 } 436 } 437 } 438 } 439 440 return nullptr; 441 } 442 443 /// We want to turn: 444 /// (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1) 445 /// into: 446 /// zext (icmp ne i32 (and X, (or Y, (shl 1, Z))), 0) 447 /// Note: 448 /// Z may be 0 if lshr is missing. 449 /// Worst-case scenario is that we will replace 5 instructions with 5 different 450 /// instructions, but we got rid of select. 451 static Instruction *foldSelectICmpAndAnd(Type *SelType, const ICmpInst *Cmp, 452 Value *TVal, Value *FVal, 453 InstCombiner::BuilderTy &Builder) { 454 if (!(Cmp->hasOneUse() && Cmp->getOperand(0)->hasOneUse() && 455 Cmp->getPredicate() == ICmpInst::ICMP_EQ && 456 match(Cmp->getOperand(1), m_Zero()) && match(FVal, m_One()))) 457 return nullptr; 458 459 // The TrueVal has general form of: and %B, 1 460 Value *B; 461 if (!match(TVal, m_OneUse(m_And(m_Value(B), m_One())))) 462 return nullptr; 463 464 // Where %B may be optionally shifted: lshr %X, %Z. 465 Value *X, *Z; 466 const bool HasShift = match(B, m_OneUse(m_LShr(m_Value(X), m_Value(Z)))); 467 if (!HasShift) 468 X = B; 469 470 Value *Y; 471 if (!match(Cmp->getOperand(0), m_c_And(m_Specific(X), m_Value(Y)))) 472 return nullptr; 473 474 // ((X & Y) == 0) ? ((X >> Z) & 1) : 1 --> (X & (Y | (1 << Z))) != 0 475 // ((X & Y) == 0) ? (X & 1) : 1 --> (X & (Y | 1)) != 0 476 Constant *One = ConstantInt::get(SelType, 1); 477 Value *MaskB = HasShift ? Builder.CreateShl(One, Z) : One; 478 Value *FullMask = Builder.CreateOr(Y, MaskB); 479 Value *MaskedX = Builder.CreateAnd(X, FullMask); 480 Value *ICmpNeZero = Builder.CreateIsNotNull(MaskedX); 481 return new ZExtInst(ICmpNeZero, SelType); 482 } 483 484 /// We want to turn: 485 /// (select (icmp eq (and X, C1), 0), Y, (or Y, C2)) 486 /// into: 487 /// (or (shl (and X, C1), C3), Y) 488 /// iff: 489 /// C1 and C2 are both powers of 2 490 /// where: 491 /// C3 = Log(C2) - Log(C1) 492 /// 493 /// This transform handles cases where: 494 /// 1. The icmp predicate is inverted 495 /// 2. The select operands are reversed 496 /// 3. The magnitude of C2 and C1 are flipped 497 static Value *foldSelectICmpAndOr(const ICmpInst *IC, Value *TrueVal, 498 Value *FalseVal, 499 InstCombiner::BuilderTy &Builder) { 500 // Only handle integer compares. Also, if this is a vector select, we need a 501 // vector compare. 502 if (!TrueVal->getType()->isIntOrIntVectorTy() || 503 TrueVal->getType()->isVectorTy() != IC->getType()->isVectorTy()) 504 return nullptr; 505 506 Value *CmpLHS = IC->getOperand(0); 507 Value *CmpRHS = IC->getOperand(1); 508 509 Value *V; 510 unsigned C1Log; 511 bool IsEqualZero; 512 bool NeedAnd = false; 513 if (IC->isEquality()) { 514 if (!match(CmpRHS, m_Zero())) 515 return nullptr; 516 517 const APInt *C1; 518 if (!match(CmpLHS, m_And(m_Value(), m_Power2(C1)))) 519 return nullptr; 520 521 V = CmpLHS; 522 C1Log = C1->logBase2(); 523 IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_EQ; 524 } else if (IC->getPredicate() == ICmpInst::ICMP_SLT || 525 IC->getPredicate() == ICmpInst::ICMP_SGT) { 526 // We also need to recognize (icmp slt (trunc (X)), 0) and 527 // (icmp sgt (trunc (X)), -1). 528 IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_SGT; 529 if ((IsEqualZero && !match(CmpRHS, m_AllOnes())) || 530 (!IsEqualZero && !match(CmpRHS, m_Zero()))) 531 return nullptr; 532 533 if (!match(CmpLHS, m_OneUse(m_Trunc(m_Value(V))))) 534 return nullptr; 535 536 C1Log = CmpLHS->getType()->getScalarSizeInBits() - 1; 537 NeedAnd = true; 538 } else { 539 return nullptr; 540 } 541 542 const APInt *C2; 543 bool OrOnTrueVal = false; 544 bool OrOnFalseVal = match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2))); 545 if (!OrOnFalseVal) 546 OrOnTrueVal = match(TrueVal, m_Or(m_Specific(FalseVal), m_Power2(C2))); 547 548 if (!OrOnFalseVal && !OrOnTrueVal) 549 return nullptr; 550 551 Value *Y = OrOnFalseVal ? TrueVal : FalseVal; 552 553 unsigned C2Log = C2->logBase2(); 554 555 bool NeedXor = (!IsEqualZero && OrOnFalseVal) || (IsEqualZero && OrOnTrueVal); 556 bool NeedShift = C1Log != C2Log; 557 bool NeedZExtTrunc = Y->getType()->getScalarSizeInBits() != 558 V->getType()->getScalarSizeInBits(); 559 560 // Make sure we don't create more instructions than we save. 561 Value *Or = OrOnFalseVal ? FalseVal : TrueVal; 562 if ((NeedShift + NeedXor + NeedZExtTrunc) > 563 (IC->hasOneUse() + Or->hasOneUse())) 564 return nullptr; 565 566 if (NeedAnd) { 567 // Insert the AND instruction on the input to the truncate. 568 APInt C1 = APInt::getOneBitSet(V->getType()->getScalarSizeInBits(), C1Log); 569 V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), C1)); 570 } 571 572 if (C2Log > C1Log) { 573 V = Builder.CreateZExtOrTrunc(V, Y->getType()); 574 V = Builder.CreateShl(V, C2Log - C1Log); 575 } else if (C1Log > C2Log) { 576 V = Builder.CreateLShr(V, C1Log - C2Log); 577 V = Builder.CreateZExtOrTrunc(V, Y->getType()); 578 } else 579 V = Builder.CreateZExtOrTrunc(V, Y->getType()); 580 581 if (NeedXor) 582 V = Builder.CreateXor(V, *C2); 583 584 return Builder.CreateOr(V, Y); 585 } 586 587 /// Transform patterns such as: (a > b) ? a - b : 0 588 /// into: ((a > b) ? a : b) - b) 589 /// This produces a canonical max pattern that is more easily recognized by the 590 /// backend and converted into saturated subtraction instructions if those 591 /// exist. 592 /// There are 8 commuted/swapped variants of this pattern. 593 /// TODO: Also support a - UMIN(a,b) patterns. 594 static Value *canonicalizeSaturatedSubtract(const ICmpInst *ICI, 595 const Value *TrueVal, 596 const Value *FalseVal, 597 InstCombiner::BuilderTy &Builder) { 598 ICmpInst::Predicate Pred = ICI->getPredicate(); 599 if (!ICmpInst::isUnsigned(Pred)) 600 return nullptr; 601 602 // (b > a) ? 0 : a - b -> (b <= a) ? a - b : 0 603 if (match(TrueVal, m_Zero())) { 604 Pred = ICmpInst::getInversePredicate(Pred); 605 std::swap(TrueVal, FalseVal); 606 } 607 if (!match(FalseVal, m_Zero())) 608 return nullptr; 609 610 Value *A = ICI->getOperand(0); 611 Value *B = ICI->getOperand(1); 612 if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_ULT) { 613 // (b < a) ? a - b : 0 -> (a > b) ? a - b : 0 614 std::swap(A, B); 615 Pred = ICmpInst::getSwappedPredicate(Pred); 616 } 617 618 assert((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_UGT) && 619 "Unexpected isUnsigned predicate!"); 620 621 // Account for swapped form of subtraction: ((a > b) ? b - a : 0). 622 bool IsNegative = false; 623 if (match(TrueVal, m_Sub(m_Specific(B), m_Specific(A)))) 624 IsNegative = true; 625 else if (!match(TrueVal, m_Sub(m_Specific(A), m_Specific(B)))) 626 return nullptr; 627 628 // If sub is used anywhere else, we wouldn't be able to eliminate it 629 // afterwards. 630 if (!TrueVal->hasOneUse()) 631 return nullptr; 632 633 // All checks passed, convert to canonical unsigned saturated subtraction 634 // form: sub(max()). 635 // (a > b) ? a - b : 0 -> ((a > b) ? a : b) - b) 636 Value *Max = Builder.CreateSelect(Builder.CreateICmp(Pred, A, B), A, B); 637 return IsNegative ? Builder.CreateSub(B, Max) : Builder.CreateSub(Max, B); 638 } 639 640 /// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single 641 /// call to cttz/ctlz with flag 'is_zero_undef' cleared. 642 /// 643 /// For example, we can fold the following code sequence: 644 /// \code 645 /// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true) 646 /// %1 = icmp ne i32 %x, 0 647 /// %2 = select i1 %1, i32 %0, i32 32 648 /// \code 649 /// 650 /// into: 651 /// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 false) 652 static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal, 653 InstCombiner::BuilderTy &Builder) { 654 ICmpInst::Predicate Pred = ICI->getPredicate(); 655 Value *CmpLHS = ICI->getOperand(0); 656 Value *CmpRHS = ICI->getOperand(1); 657 658 // Check if the condition value compares a value for equality against zero. 659 if (!ICI->isEquality() || !match(CmpRHS, m_Zero())) 660 return nullptr; 661 662 Value *Count = FalseVal; 663 Value *ValueOnZero = TrueVal; 664 if (Pred == ICmpInst::ICMP_NE) 665 std::swap(Count, ValueOnZero); 666 667 // Skip zero extend/truncate. 668 Value *V = nullptr; 669 if (match(Count, m_ZExt(m_Value(V))) || 670 match(Count, m_Trunc(m_Value(V)))) 671 Count = V; 672 673 // Check if the value propagated on zero is a constant number equal to the 674 // sizeof in bits of 'Count'. 675 unsigned SizeOfInBits = Count->getType()->getScalarSizeInBits(); 676 if (!match(ValueOnZero, m_SpecificInt(SizeOfInBits))) 677 return nullptr; 678 679 // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the 680 // input to the cttz/ctlz is used as LHS for the compare instruction. 681 if (match(Count, m_Intrinsic<Intrinsic::cttz>(m_Specific(CmpLHS))) || 682 match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Specific(CmpLHS)))) { 683 IntrinsicInst *II = cast<IntrinsicInst>(Count); 684 // Explicitly clear the 'undef_on_zero' flag. 685 IntrinsicInst *NewI = cast<IntrinsicInst>(II->clone()); 686 NewI->setArgOperand(1, ConstantInt::getFalse(NewI->getContext())); 687 Builder.Insert(NewI); 688 return Builder.CreateZExtOrTrunc(NewI, ValueOnZero->getType()); 689 } 690 691 return nullptr; 692 } 693 694 /// Return true if we find and adjust an icmp+select pattern where the compare 695 /// is with a constant that can be incremented or decremented to match the 696 /// minimum or maximum idiom. 697 static bool adjustMinMax(SelectInst &Sel, ICmpInst &Cmp) { 698 ICmpInst::Predicate Pred = Cmp.getPredicate(); 699 Value *CmpLHS = Cmp.getOperand(0); 700 Value *CmpRHS = Cmp.getOperand(1); 701 Value *TrueVal = Sel.getTrueValue(); 702 Value *FalseVal = Sel.getFalseValue(); 703 704 // We may move or edit the compare, so make sure the select is the only user. 705 const APInt *CmpC; 706 if (!Cmp.hasOneUse() || !match(CmpRHS, m_APInt(CmpC))) 707 return false; 708 709 // These transforms only work for selects of integers or vector selects of 710 // integer vectors. 711 Type *SelTy = Sel.getType(); 712 auto *SelEltTy = dyn_cast<IntegerType>(SelTy->getScalarType()); 713 if (!SelEltTy || SelTy->isVectorTy() != Cmp.getType()->isVectorTy()) 714 return false; 715 716 Constant *AdjustedRHS; 717 if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_SGT) 718 AdjustedRHS = ConstantInt::get(CmpRHS->getType(), *CmpC + 1); 719 else if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_SLT) 720 AdjustedRHS = ConstantInt::get(CmpRHS->getType(), *CmpC - 1); 721 else 722 return false; 723 724 // X > C ? X : C+1 --> X < C+1 ? C+1 : X 725 // X < C ? X : C-1 --> X > C-1 ? C-1 : X 726 if ((CmpLHS == TrueVal && AdjustedRHS == FalseVal) || 727 (CmpLHS == FalseVal && AdjustedRHS == TrueVal)) { 728 ; // Nothing to do here. Values match without any sign/zero extension. 729 } 730 // Types do not match. Instead of calculating this with mixed types, promote 731 // all to the larger type. This enables scalar evolution to analyze this 732 // expression. 733 else if (CmpRHS->getType()->getScalarSizeInBits() < SelEltTy->getBitWidth()) { 734 Constant *SextRHS = ConstantExpr::getSExt(AdjustedRHS, SelTy); 735 736 // X = sext x; x >s c ? X : C+1 --> X = sext x; X <s C+1 ? C+1 : X 737 // X = sext x; x <s c ? X : C-1 --> X = sext x; X >s C-1 ? C-1 : X 738 // X = sext x; x >u c ? X : C+1 --> X = sext x; X <u C+1 ? C+1 : X 739 // X = sext x; x <u c ? X : C-1 --> X = sext x; X >u C-1 ? C-1 : X 740 if (match(TrueVal, m_SExt(m_Specific(CmpLHS))) && SextRHS == FalseVal) { 741 CmpLHS = TrueVal; 742 AdjustedRHS = SextRHS; 743 } else if (match(FalseVal, m_SExt(m_Specific(CmpLHS))) && 744 SextRHS == TrueVal) { 745 CmpLHS = FalseVal; 746 AdjustedRHS = SextRHS; 747 } else if (Cmp.isUnsigned()) { 748 Constant *ZextRHS = ConstantExpr::getZExt(AdjustedRHS, SelTy); 749 // X = zext x; x >u c ? X : C+1 --> X = zext x; X <u C+1 ? C+1 : X 750 // X = zext x; x <u c ? X : C-1 --> X = zext x; X >u C-1 ? C-1 : X 751 // zext + signed compare cannot be changed: 752 // 0xff <s 0x00, but 0x00ff >s 0x0000 753 if (match(TrueVal, m_ZExt(m_Specific(CmpLHS))) && ZextRHS == FalseVal) { 754 CmpLHS = TrueVal; 755 AdjustedRHS = ZextRHS; 756 } else if (match(FalseVal, m_ZExt(m_Specific(CmpLHS))) && 757 ZextRHS == TrueVal) { 758 CmpLHS = FalseVal; 759 AdjustedRHS = ZextRHS; 760 } else { 761 return false; 762 } 763 } else { 764 return false; 765 } 766 } else { 767 return false; 768 } 769 770 Pred = ICmpInst::getSwappedPredicate(Pred); 771 CmpRHS = AdjustedRHS; 772 std::swap(FalseVal, TrueVal); 773 Cmp.setPredicate(Pred); 774 Cmp.setOperand(0, CmpLHS); 775 Cmp.setOperand(1, CmpRHS); 776 Sel.setOperand(1, TrueVal); 777 Sel.setOperand(2, FalseVal); 778 Sel.swapProfMetadata(); 779 780 // Move the compare instruction right before the select instruction. Otherwise 781 // the sext/zext value may be defined after the compare instruction uses it. 782 Cmp.moveBefore(&Sel); 783 784 return true; 785 } 786 787 /// If this is an integer min/max (icmp + select) with a constant operand, 788 /// create the canonical icmp for the min/max operation and canonicalize the 789 /// constant to the 'false' operand of the select: 790 /// select (icmp Pred X, C1), C2, X --> select (icmp Pred' X, C2), X, C2 791 /// Note: if C1 != C2, this will change the icmp constant to the existing 792 /// constant operand of the select. 793 static Instruction * 794 canonicalizeMinMaxWithConstant(SelectInst &Sel, ICmpInst &Cmp, 795 InstCombiner::BuilderTy &Builder) { 796 if (!Cmp.hasOneUse() || !isa<Constant>(Cmp.getOperand(1))) 797 return nullptr; 798 799 // Canonicalize the compare predicate based on whether we have min or max. 800 Value *LHS, *RHS; 801 SelectPatternResult SPR = matchSelectPattern(&Sel, LHS, RHS); 802 if (!SelectPatternResult::isMinOrMax(SPR.Flavor)) 803 return nullptr; 804 805 // Is this already canonical? 806 ICmpInst::Predicate CanonicalPred = getMinMaxPred(SPR.Flavor); 807 if (Cmp.getOperand(0) == LHS && Cmp.getOperand(1) == RHS && 808 Cmp.getPredicate() == CanonicalPred) 809 return nullptr; 810 811 // Create the canonical compare and plug it into the select. 812 Sel.setCondition(Builder.CreateICmp(CanonicalPred, LHS, RHS)); 813 814 // If the select operands did not change, we're done. 815 if (Sel.getTrueValue() == LHS && Sel.getFalseValue() == RHS) 816 return &Sel; 817 818 // If we are swapping the select operands, swap the metadata too. 819 assert(Sel.getTrueValue() == RHS && Sel.getFalseValue() == LHS && 820 "Unexpected results from matchSelectPattern"); 821 Sel.setTrueValue(LHS); 822 Sel.setFalseValue(RHS); 823 Sel.swapProfMetadata(); 824 return &Sel; 825 } 826 827 /// There are many select variants for each of ABS/NABS. 828 /// In matchSelectPattern(), there are different compare constants, compare 829 /// predicates/operands and select operands. 830 /// In isKnownNegation(), there are different formats of negated operands. 831 /// Canonicalize all these variants to 1 pattern. 832 /// This makes CSE more likely. 833 static Instruction *canonicalizeAbsNabs(SelectInst &Sel, ICmpInst &Cmp, 834 InstCombiner::BuilderTy &Builder) { 835 if (!Cmp.hasOneUse() || !isa<Constant>(Cmp.getOperand(1))) 836 return nullptr; 837 838 // Choose a sign-bit check for the compare (likely simpler for codegen). 839 // ABS: (X <s 0) ? -X : X 840 // NABS: (X <s 0) ? X : -X 841 Value *LHS, *RHS; 842 SelectPatternFlavor SPF = matchSelectPattern(&Sel, LHS, RHS).Flavor; 843 if (SPF != SelectPatternFlavor::SPF_ABS && 844 SPF != SelectPatternFlavor::SPF_NABS) 845 return nullptr; 846 847 Value *TVal = Sel.getTrueValue(); 848 Value *FVal = Sel.getFalseValue(); 849 assert(isKnownNegation(TVal, FVal) && 850 "Unexpected result from matchSelectPattern"); 851 852 // The compare may use the negated abs()/nabs() operand, or it may use 853 // negation in non-canonical form such as: sub A, B. 854 bool CmpUsesNegatedOp = match(Cmp.getOperand(0), m_Neg(m_Specific(TVal))) || 855 match(Cmp.getOperand(0), m_Neg(m_Specific(FVal))); 856 857 bool CmpCanonicalized = !CmpUsesNegatedOp && 858 match(Cmp.getOperand(1), m_ZeroInt()) && 859 Cmp.getPredicate() == ICmpInst::ICMP_SLT; 860 bool RHSCanonicalized = match(RHS, m_Neg(m_Specific(LHS))); 861 862 // Is this already canonical? 863 if (CmpCanonicalized && RHSCanonicalized) 864 return nullptr; 865 866 // If RHS is used by other instructions except compare and select, don't 867 // canonicalize it to not increase the instruction count. 868 if (!(RHS->hasOneUse() || (RHS->hasNUses(2) && CmpUsesNegatedOp))) 869 return nullptr; 870 871 // Create the canonical compare: icmp slt LHS 0. 872 if (!CmpCanonicalized) { 873 Cmp.setPredicate(ICmpInst::ICMP_SLT); 874 Cmp.setOperand(1, ConstantInt::getNullValue(Cmp.getOperand(0)->getType())); 875 if (CmpUsesNegatedOp) 876 Cmp.setOperand(0, LHS); 877 } 878 879 // Create the canonical RHS: RHS = sub (0, LHS). 880 if (!RHSCanonicalized) { 881 assert(RHS->hasOneUse() && "RHS use number is not right"); 882 RHS = Builder.CreateNeg(LHS); 883 if (TVal == LHS) { 884 Sel.setFalseValue(RHS); 885 FVal = RHS; 886 } else { 887 Sel.setTrueValue(RHS); 888 TVal = RHS; 889 } 890 } 891 892 // If the select operands do not change, we're done. 893 if (SPF == SelectPatternFlavor::SPF_NABS) { 894 if (TVal == LHS) 895 return &Sel; 896 assert(FVal == LHS && "Unexpected results from matchSelectPattern"); 897 } else { 898 if (FVal == LHS) 899 return &Sel; 900 assert(TVal == LHS && "Unexpected results from matchSelectPattern"); 901 } 902 903 // We are swapping the select operands, so swap the metadata too. 904 Sel.setTrueValue(FVal); 905 Sel.setFalseValue(TVal); 906 Sel.swapProfMetadata(); 907 return &Sel; 908 } 909 910 /// Visit a SelectInst that has an ICmpInst as its first operand. 911 Instruction *InstCombiner::foldSelectInstWithICmp(SelectInst &SI, 912 ICmpInst *ICI) { 913 Value *TrueVal = SI.getTrueValue(); 914 Value *FalseVal = SI.getFalseValue(); 915 916 if (Instruction *NewSel = canonicalizeMinMaxWithConstant(SI, *ICI, Builder)) 917 return NewSel; 918 919 if (Instruction *NewAbs = canonicalizeAbsNabs(SI, *ICI, Builder)) 920 return NewAbs; 921 922 bool Changed = adjustMinMax(SI, *ICI); 923 924 if (Value *V = foldSelectICmpAnd(SI, ICI, Builder)) 925 return replaceInstUsesWith(SI, V); 926 927 // NOTE: if we wanted to, this is where to detect integer MIN/MAX 928 ICmpInst::Predicate Pred = ICI->getPredicate(); 929 Value *CmpLHS = ICI->getOperand(0); 930 Value *CmpRHS = ICI->getOperand(1); 931 if (CmpRHS != CmpLHS && isa<Constant>(CmpRHS)) { 932 if (CmpLHS == TrueVal && Pred == ICmpInst::ICMP_EQ) { 933 // Transform (X == C) ? X : Y -> (X == C) ? C : Y 934 SI.setOperand(1, CmpRHS); 935 Changed = true; 936 } else if (CmpLHS == FalseVal && Pred == ICmpInst::ICMP_NE) { 937 // Transform (X != C) ? Y : X -> (X != C) ? Y : C 938 SI.setOperand(2, CmpRHS); 939 Changed = true; 940 } 941 } 942 943 // FIXME: This code is nearly duplicated in InstSimplify. Using/refactoring 944 // decomposeBitTestICmp() might help. 945 { 946 unsigned BitWidth = 947 DL.getTypeSizeInBits(TrueVal->getType()->getScalarType()); 948 APInt MinSignedValue = APInt::getSignedMinValue(BitWidth); 949 Value *X; 950 const APInt *Y, *C; 951 bool TrueWhenUnset; 952 bool IsBitTest = false; 953 if (ICmpInst::isEquality(Pred) && 954 match(CmpLHS, m_And(m_Value(X), m_Power2(Y))) && 955 match(CmpRHS, m_Zero())) { 956 IsBitTest = true; 957 TrueWhenUnset = Pred == ICmpInst::ICMP_EQ; 958 } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) { 959 X = CmpLHS; 960 Y = &MinSignedValue; 961 IsBitTest = true; 962 TrueWhenUnset = false; 963 } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) { 964 X = CmpLHS; 965 Y = &MinSignedValue; 966 IsBitTest = true; 967 TrueWhenUnset = true; 968 } 969 if (IsBitTest) { 970 Value *V = nullptr; 971 // (X & Y) == 0 ? X : X ^ Y --> X & ~Y 972 if (TrueWhenUnset && TrueVal == X && 973 match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C) 974 V = Builder.CreateAnd(X, ~(*Y)); 975 // (X & Y) != 0 ? X ^ Y : X --> X & ~Y 976 else if (!TrueWhenUnset && FalseVal == X && 977 match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C) 978 V = Builder.CreateAnd(X, ~(*Y)); 979 // (X & Y) == 0 ? X ^ Y : X --> X | Y 980 else if (TrueWhenUnset && FalseVal == X && 981 match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C) 982 V = Builder.CreateOr(X, *Y); 983 // (X & Y) != 0 ? X : X ^ Y --> X | Y 984 else if (!TrueWhenUnset && TrueVal == X && 985 match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C) 986 V = Builder.CreateOr(X, *Y); 987 988 if (V) 989 return replaceInstUsesWith(SI, V); 990 } 991 } 992 993 if (Instruction *V = 994 foldSelectICmpAndAnd(SI.getType(), ICI, TrueVal, FalseVal, Builder)) 995 return V; 996 997 if (Value *V = foldSelectICmpAndOr(ICI, TrueVal, FalseVal, Builder)) 998 return replaceInstUsesWith(SI, V); 999 1000 if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder)) 1001 return replaceInstUsesWith(SI, V); 1002 1003 if (Value *V = canonicalizeSaturatedSubtract(ICI, TrueVal, FalseVal, Builder)) 1004 return replaceInstUsesWith(SI, V); 1005 1006 return Changed ? &SI : nullptr; 1007 } 1008 1009 /// SI is a select whose condition is a PHI node (but the two may be in 1010 /// different blocks). See if the true/false values (V) are live in all of the 1011 /// predecessor blocks of the PHI. For example, cases like this can't be mapped: 1012 /// 1013 /// X = phi [ C1, BB1], [C2, BB2] 1014 /// Y = add 1015 /// Z = select X, Y, 0 1016 /// 1017 /// because Y is not live in BB1/BB2. 1018 static bool canSelectOperandBeMappingIntoPredBlock(const Value *V, 1019 const SelectInst &SI) { 1020 // If the value is a non-instruction value like a constant or argument, it 1021 // can always be mapped. 1022 const Instruction *I = dyn_cast<Instruction>(V); 1023 if (!I) return true; 1024 1025 // If V is a PHI node defined in the same block as the condition PHI, we can 1026 // map the arguments. 1027 const PHINode *CondPHI = cast<PHINode>(SI.getCondition()); 1028 1029 if (const PHINode *VP = dyn_cast<PHINode>(I)) 1030 if (VP->getParent() == CondPHI->getParent()) 1031 return true; 1032 1033 // Otherwise, if the PHI and select are defined in the same block and if V is 1034 // defined in a different block, then we can transform it. 1035 if (SI.getParent() == CondPHI->getParent() && 1036 I->getParent() != CondPHI->getParent()) 1037 return true; 1038 1039 // Otherwise we have a 'hard' case and we can't tell without doing more 1040 // detailed dominator based analysis, punt. 1041 return false; 1042 } 1043 1044 /// We have an SPF (e.g. a min or max) of an SPF of the form: 1045 /// SPF2(SPF1(A, B), C) 1046 Instruction *InstCombiner::foldSPFofSPF(Instruction *Inner, 1047 SelectPatternFlavor SPF1, 1048 Value *A, Value *B, 1049 Instruction &Outer, 1050 SelectPatternFlavor SPF2, Value *C) { 1051 if (Outer.getType() != Inner->getType()) 1052 return nullptr; 1053 1054 if (C == A || C == B) { 1055 // MAX(MAX(A, B), B) -> MAX(A, B) 1056 // MIN(MIN(a, b), a) -> MIN(a, b) 1057 if (SPF1 == SPF2 && SelectPatternResult::isMinOrMax(SPF1)) 1058 return replaceInstUsesWith(Outer, Inner); 1059 1060 // MAX(MIN(a, b), a) -> a 1061 // MIN(MAX(a, b), a) -> a 1062 if ((SPF1 == SPF_SMIN && SPF2 == SPF_SMAX) || 1063 (SPF1 == SPF_SMAX && SPF2 == SPF_SMIN) || 1064 (SPF1 == SPF_UMIN && SPF2 == SPF_UMAX) || 1065 (SPF1 == SPF_UMAX && SPF2 == SPF_UMIN)) 1066 return replaceInstUsesWith(Outer, C); 1067 } 1068 1069 if (SPF1 == SPF2) { 1070 const APInt *CB, *CC; 1071 if (match(B, m_APInt(CB)) && match(C, m_APInt(CC))) { 1072 // MIN(MIN(A, 23), 97) -> MIN(A, 23) 1073 // MAX(MAX(A, 97), 23) -> MAX(A, 97) 1074 if ((SPF1 == SPF_UMIN && CB->ule(*CC)) || 1075 (SPF1 == SPF_SMIN && CB->sle(*CC)) || 1076 (SPF1 == SPF_UMAX && CB->uge(*CC)) || 1077 (SPF1 == SPF_SMAX && CB->sge(*CC))) 1078 return replaceInstUsesWith(Outer, Inner); 1079 1080 // MIN(MIN(A, 97), 23) -> MIN(A, 23) 1081 // MAX(MAX(A, 23), 97) -> MAX(A, 97) 1082 if ((SPF1 == SPF_UMIN && CB->ugt(*CC)) || 1083 (SPF1 == SPF_SMIN && CB->sgt(*CC)) || 1084 (SPF1 == SPF_UMAX && CB->ult(*CC)) || 1085 (SPF1 == SPF_SMAX && CB->slt(*CC))) { 1086 Outer.replaceUsesOfWith(Inner, A); 1087 return &Outer; 1088 } 1089 } 1090 } 1091 1092 // ABS(ABS(X)) -> ABS(X) 1093 // NABS(NABS(X)) -> NABS(X) 1094 if (SPF1 == SPF2 && (SPF1 == SPF_ABS || SPF1 == SPF_NABS)) { 1095 return replaceInstUsesWith(Outer, Inner); 1096 } 1097 1098 // ABS(NABS(X)) -> ABS(X) 1099 // NABS(ABS(X)) -> NABS(X) 1100 if ((SPF1 == SPF_ABS && SPF2 == SPF_NABS) || 1101 (SPF1 == SPF_NABS && SPF2 == SPF_ABS)) { 1102 SelectInst *SI = cast<SelectInst>(Inner); 1103 Value *NewSI = 1104 Builder.CreateSelect(SI->getCondition(), SI->getFalseValue(), 1105 SI->getTrueValue(), SI->getName(), SI); 1106 return replaceInstUsesWith(Outer, NewSI); 1107 } 1108 1109 auto IsFreeOrProfitableToInvert = 1110 [&](Value *V, Value *&NotV, bool &ElidesXor) { 1111 if (match(V, m_Not(m_Value(NotV)))) { 1112 // If V has at most 2 uses then we can get rid of the xor operation 1113 // entirely. 1114 ElidesXor |= !V->hasNUsesOrMore(3); 1115 return true; 1116 } 1117 1118 if (IsFreeToInvert(V, !V->hasNUsesOrMore(3))) { 1119 NotV = nullptr; 1120 return true; 1121 } 1122 1123 return false; 1124 }; 1125 1126 Value *NotA, *NotB, *NotC; 1127 bool ElidesXor = false; 1128 1129 // MIN(MIN(~A, ~B), ~C) == ~MAX(MAX(A, B), C) 1130 // MIN(MAX(~A, ~B), ~C) == ~MAX(MIN(A, B), C) 1131 // MAX(MIN(~A, ~B), ~C) == ~MIN(MAX(A, B), C) 1132 // MAX(MAX(~A, ~B), ~C) == ~MIN(MIN(A, B), C) 1133 // 1134 // This transform is performance neutral if we can elide at least one xor from 1135 // the set of three operands, since we'll be tacking on an xor at the very 1136 // end. 1137 if (SelectPatternResult::isMinOrMax(SPF1) && 1138 SelectPatternResult::isMinOrMax(SPF2) && 1139 IsFreeOrProfitableToInvert(A, NotA, ElidesXor) && 1140 IsFreeOrProfitableToInvert(B, NotB, ElidesXor) && 1141 IsFreeOrProfitableToInvert(C, NotC, ElidesXor) && ElidesXor) { 1142 if (!NotA) 1143 NotA = Builder.CreateNot(A); 1144 if (!NotB) 1145 NotB = Builder.CreateNot(B); 1146 if (!NotC) 1147 NotC = Builder.CreateNot(C); 1148 1149 Value *NewInner = createMinMax(Builder, getInverseMinMaxFlavor(SPF1), NotA, 1150 NotB); 1151 Value *NewOuter = Builder.CreateNot( 1152 createMinMax(Builder, getInverseMinMaxFlavor(SPF2), NewInner, NotC)); 1153 return replaceInstUsesWith(Outer, NewOuter); 1154 } 1155 1156 return nullptr; 1157 } 1158 1159 /// Turn select C, (X + Y), (X - Y) --> (X + (select C, Y, (-Y))). 1160 /// This is even legal for FP. 1161 static Instruction *foldAddSubSelect(SelectInst &SI, 1162 InstCombiner::BuilderTy &Builder) { 1163 Value *CondVal = SI.getCondition(); 1164 Value *TrueVal = SI.getTrueValue(); 1165 Value *FalseVal = SI.getFalseValue(); 1166 auto *TI = dyn_cast<Instruction>(TrueVal); 1167 auto *FI = dyn_cast<Instruction>(FalseVal); 1168 if (!TI || !FI || !TI->hasOneUse() || !FI->hasOneUse()) 1169 return nullptr; 1170 1171 Instruction *AddOp = nullptr, *SubOp = nullptr; 1172 if ((TI->getOpcode() == Instruction::Sub && 1173 FI->getOpcode() == Instruction::Add) || 1174 (TI->getOpcode() == Instruction::FSub && 1175 FI->getOpcode() == Instruction::FAdd)) { 1176 AddOp = FI; 1177 SubOp = TI; 1178 } else if ((FI->getOpcode() == Instruction::Sub && 1179 TI->getOpcode() == Instruction::Add) || 1180 (FI->getOpcode() == Instruction::FSub && 1181 TI->getOpcode() == Instruction::FAdd)) { 1182 AddOp = TI; 1183 SubOp = FI; 1184 } 1185 1186 if (AddOp) { 1187 Value *OtherAddOp = nullptr; 1188 if (SubOp->getOperand(0) == AddOp->getOperand(0)) { 1189 OtherAddOp = AddOp->getOperand(1); 1190 } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) { 1191 OtherAddOp = AddOp->getOperand(0); 1192 } 1193 1194 if (OtherAddOp) { 1195 // So at this point we know we have (Y -> OtherAddOp): 1196 // select C, (add X, Y), (sub X, Z) 1197 Value *NegVal; // Compute -Z 1198 if (SI.getType()->isFPOrFPVectorTy()) { 1199 NegVal = Builder.CreateFNeg(SubOp->getOperand(1)); 1200 if (Instruction *NegInst = dyn_cast<Instruction>(NegVal)) { 1201 FastMathFlags Flags = AddOp->getFastMathFlags(); 1202 Flags &= SubOp->getFastMathFlags(); 1203 NegInst->setFastMathFlags(Flags); 1204 } 1205 } else { 1206 NegVal = Builder.CreateNeg(SubOp->getOperand(1)); 1207 } 1208 1209 Value *NewTrueOp = OtherAddOp; 1210 Value *NewFalseOp = NegVal; 1211 if (AddOp != TI) 1212 std::swap(NewTrueOp, NewFalseOp); 1213 Value *NewSel = Builder.CreateSelect(CondVal, NewTrueOp, NewFalseOp, 1214 SI.getName() + ".p", &SI); 1215 1216 if (SI.getType()->isFPOrFPVectorTy()) { 1217 Instruction *RI = 1218 BinaryOperator::CreateFAdd(SubOp->getOperand(0), NewSel); 1219 1220 FastMathFlags Flags = AddOp->getFastMathFlags(); 1221 Flags &= SubOp->getFastMathFlags(); 1222 RI->setFastMathFlags(Flags); 1223 return RI; 1224 } else 1225 return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel); 1226 } 1227 } 1228 return nullptr; 1229 } 1230 1231 Instruction *InstCombiner::foldSelectExtConst(SelectInst &Sel) { 1232 Constant *C; 1233 if (!match(Sel.getTrueValue(), m_Constant(C)) && 1234 !match(Sel.getFalseValue(), m_Constant(C))) 1235 return nullptr; 1236 1237 Instruction *ExtInst; 1238 if (!match(Sel.getTrueValue(), m_Instruction(ExtInst)) && 1239 !match(Sel.getFalseValue(), m_Instruction(ExtInst))) 1240 return nullptr; 1241 1242 auto ExtOpcode = ExtInst->getOpcode(); 1243 if (ExtOpcode != Instruction::ZExt && ExtOpcode != Instruction::SExt) 1244 return nullptr; 1245 1246 // If we are extending from a boolean type or if we can create a select that 1247 // has the same size operands as its condition, try to narrow the select. 1248 Value *X = ExtInst->getOperand(0); 1249 Type *SmallType = X->getType(); 1250 Value *Cond = Sel.getCondition(); 1251 auto *Cmp = dyn_cast<CmpInst>(Cond); 1252 if (!SmallType->isIntOrIntVectorTy(1) && 1253 (!Cmp || Cmp->getOperand(0)->getType() != SmallType)) 1254 return nullptr; 1255 1256 // If the constant is the same after truncation to the smaller type and 1257 // extension to the original type, we can narrow the select. 1258 Type *SelType = Sel.getType(); 1259 Constant *TruncC = ConstantExpr::getTrunc(C, SmallType); 1260 Constant *ExtC = ConstantExpr::getCast(ExtOpcode, TruncC, SelType); 1261 if (ExtC == C) { 1262 Value *TruncCVal = cast<Value>(TruncC); 1263 if (ExtInst == Sel.getFalseValue()) 1264 std::swap(X, TruncCVal); 1265 1266 // select Cond, (ext X), C --> ext(select Cond, X, C') 1267 // select Cond, C, (ext X) --> ext(select Cond, C', X) 1268 Value *NewSel = Builder.CreateSelect(Cond, X, TruncCVal, "narrow", &Sel); 1269 return CastInst::Create(Instruction::CastOps(ExtOpcode), NewSel, SelType); 1270 } 1271 1272 // If one arm of the select is the extend of the condition, replace that arm 1273 // with the extension of the appropriate known bool value. 1274 if (Cond == X) { 1275 if (ExtInst == Sel.getTrueValue()) { 1276 // select X, (sext X), C --> select X, -1, C 1277 // select X, (zext X), C --> select X, 1, C 1278 Constant *One = ConstantInt::getTrue(SmallType); 1279 Constant *AllOnesOrOne = ConstantExpr::getCast(ExtOpcode, One, SelType); 1280 return SelectInst::Create(Cond, AllOnesOrOne, C, "", nullptr, &Sel); 1281 } else { 1282 // select X, C, (sext X) --> select X, C, 0 1283 // select X, C, (zext X) --> select X, C, 0 1284 Constant *Zero = ConstantInt::getNullValue(SelType); 1285 return SelectInst::Create(Cond, C, Zero, "", nullptr, &Sel); 1286 } 1287 } 1288 1289 return nullptr; 1290 } 1291 1292 /// Try to transform a vector select with a constant condition vector into a 1293 /// shuffle for easier combining with other shuffles and insert/extract. 1294 static Instruction *canonicalizeSelectToShuffle(SelectInst &SI) { 1295 Value *CondVal = SI.getCondition(); 1296 Constant *CondC; 1297 if (!CondVal->getType()->isVectorTy() || !match(CondVal, m_Constant(CondC))) 1298 return nullptr; 1299 1300 unsigned NumElts = CondVal->getType()->getVectorNumElements(); 1301 SmallVector<Constant *, 16> Mask; 1302 Mask.reserve(NumElts); 1303 Type *Int32Ty = Type::getInt32Ty(CondVal->getContext()); 1304 for (unsigned i = 0; i != NumElts; ++i) { 1305 Constant *Elt = CondC->getAggregateElement(i); 1306 if (!Elt) 1307 return nullptr; 1308 1309 if (Elt->isOneValue()) { 1310 // If the select condition element is true, choose from the 1st vector. 1311 Mask.push_back(ConstantInt::get(Int32Ty, i)); 1312 } else if (Elt->isNullValue()) { 1313 // If the select condition element is false, choose from the 2nd vector. 1314 Mask.push_back(ConstantInt::get(Int32Ty, i + NumElts)); 1315 } else if (isa<UndefValue>(Elt)) { 1316 // Undef in a select condition (choose one of the operands) does not mean 1317 // the same thing as undef in a shuffle mask (any value is acceptable), so 1318 // give up. 1319 return nullptr; 1320 } else { 1321 // Bail out on a constant expression. 1322 return nullptr; 1323 } 1324 } 1325 1326 return new ShuffleVectorInst(SI.getTrueValue(), SI.getFalseValue(), 1327 ConstantVector::get(Mask)); 1328 } 1329 1330 /// Reuse bitcasted operands between a compare and select: 1331 /// select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) --> 1332 /// bitcast (select (cmp (bitcast C), (bitcast D)), (bitcast C), (bitcast D)) 1333 static Instruction *foldSelectCmpBitcasts(SelectInst &Sel, 1334 InstCombiner::BuilderTy &Builder) { 1335 Value *Cond = Sel.getCondition(); 1336 Value *TVal = Sel.getTrueValue(); 1337 Value *FVal = Sel.getFalseValue(); 1338 1339 CmpInst::Predicate Pred; 1340 Value *A, *B; 1341 if (!match(Cond, m_Cmp(Pred, m_Value(A), m_Value(B)))) 1342 return nullptr; 1343 1344 // The select condition is a compare instruction. If the select's true/false 1345 // values are already the same as the compare operands, there's nothing to do. 1346 if (TVal == A || TVal == B || FVal == A || FVal == B) 1347 return nullptr; 1348 1349 Value *C, *D; 1350 if (!match(A, m_BitCast(m_Value(C))) || !match(B, m_BitCast(m_Value(D)))) 1351 return nullptr; 1352 1353 // select (cmp (bitcast C), (bitcast D)), (bitcast TSrc), (bitcast FSrc) 1354 Value *TSrc, *FSrc; 1355 if (!match(TVal, m_BitCast(m_Value(TSrc))) || 1356 !match(FVal, m_BitCast(m_Value(FSrc)))) 1357 return nullptr; 1358 1359 // If the select true/false values are *different bitcasts* of the same source 1360 // operands, make the select operands the same as the compare operands and 1361 // cast the result. This is the canonical select form for min/max. 1362 Value *NewSel; 1363 if (TSrc == C && FSrc == D) { 1364 // select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) --> 1365 // bitcast (select (cmp A, B), A, B) 1366 NewSel = Builder.CreateSelect(Cond, A, B, "", &Sel); 1367 } else if (TSrc == D && FSrc == C) { 1368 // select (cmp (bitcast C), (bitcast D)), (bitcast' D), (bitcast' C) --> 1369 // bitcast (select (cmp A, B), B, A) 1370 NewSel = Builder.CreateSelect(Cond, B, A, "", &Sel); 1371 } else { 1372 return nullptr; 1373 } 1374 return CastInst::CreateBitOrPointerCast(NewSel, Sel.getType()); 1375 } 1376 1377 /// Try to eliminate select instructions that test the returned flag of cmpxchg 1378 /// instructions. 1379 /// 1380 /// If a select instruction tests the returned flag of a cmpxchg instruction and 1381 /// selects between the returned value of the cmpxchg instruction its compare 1382 /// operand, the result of the select will always be equal to its false value. 1383 /// For example: 1384 /// 1385 /// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst 1386 /// %1 = extractvalue { i64, i1 } %0, 1 1387 /// %2 = extractvalue { i64, i1 } %0, 0 1388 /// %3 = select i1 %1, i64 %compare, i64 %2 1389 /// ret i64 %3 1390 /// 1391 /// The returned value of the cmpxchg instruction (%2) is the original value 1392 /// located at %ptr prior to any update. If the cmpxchg operation succeeds, %2 1393 /// must have been equal to %compare. Thus, the result of the select is always 1394 /// equal to %2, and the code can be simplified to: 1395 /// 1396 /// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst 1397 /// %1 = extractvalue { i64, i1 } %0, 0 1398 /// ret i64 %1 1399 /// 1400 static Instruction *foldSelectCmpXchg(SelectInst &SI) { 1401 // A helper that determines if V is an extractvalue instruction whose 1402 // aggregate operand is a cmpxchg instruction and whose single index is equal 1403 // to I. If such conditions are true, the helper returns the cmpxchg 1404 // instruction; otherwise, a nullptr is returned. 1405 auto isExtractFromCmpXchg = [](Value *V, unsigned I) -> AtomicCmpXchgInst * { 1406 auto *Extract = dyn_cast<ExtractValueInst>(V); 1407 if (!Extract) 1408 return nullptr; 1409 if (Extract->getIndices()[0] != I) 1410 return nullptr; 1411 return dyn_cast<AtomicCmpXchgInst>(Extract->getAggregateOperand()); 1412 }; 1413 1414 // If the select has a single user, and this user is a select instruction that 1415 // we can simplify, skip the cmpxchg simplification for now. 1416 if (SI.hasOneUse()) 1417 if (auto *Select = dyn_cast<SelectInst>(SI.user_back())) 1418 if (Select->getCondition() == SI.getCondition()) 1419 if (Select->getFalseValue() == SI.getTrueValue() || 1420 Select->getTrueValue() == SI.getFalseValue()) 1421 return nullptr; 1422 1423 // Ensure the select condition is the returned flag of a cmpxchg instruction. 1424 auto *CmpXchg = isExtractFromCmpXchg(SI.getCondition(), 1); 1425 if (!CmpXchg) 1426 return nullptr; 1427 1428 // Check the true value case: The true value of the select is the returned 1429 // value of the same cmpxchg used by the condition, and the false value is the 1430 // cmpxchg instruction's compare operand. 1431 if (auto *X = isExtractFromCmpXchg(SI.getTrueValue(), 0)) 1432 if (X == CmpXchg && X->getCompareOperand() == SI.getFalseValue()) { 1433 SI.setTrueValue(SI.getFalseValue()); 1434 return &SI; 1435 } 1436 1437 // Check the false value case: The false value of the select is the returned 1438 // value of the same cmpxchg used by the condition, and the true value is the 1439 // cmpxchg instruction's compare operand. 1440 if (auto *X = isExtractFromCmpXchg(SI.getFalseValue(), 0)) 1441 if (X == CmpXchg && X->getCompareOperand() == SI.getTrueValue()) { 1442 SI.setTrueValue(SI.getFalseValue()); 1443 return &SI; 1444 } 1445 1446 return nullptr; 1447 } 1448 1449 /// Reduce a sequence of min/max with a common operand. 1450 static Instruction *factorizeMinMaxTree(SelectPatternFlavor SPF, Value *LHS, 1451 Value *RHS, 1452 InstCombiner::BuilderTy &Builder) { 1453 assert(SelectPatternResult::isMinOrMax(SPF) && "Expected a min/max"); 1454 // TODO: Allow FP min/max with nnan/nsz. 1455 if (!LHS->getType()->isIntOrIntVectorTy()) 1456 return nullptr; 1457 1458 // Match 3 of the same min/max ops. Example: umin(umin(), umin()). 1459 Value *A, *B, *C, *D; 1460 SelectPatternResult L = matchSelectPattern(LHS, A, B); 1461 SelectPatternResult R = matchSelectPattern(RHS, C, D); 1462 if (SPF != L.Flavor || L.Flavor != R.Flavor) 1463 return nullptr; 1464 1465 // Look for a common operand. The use checks are different than usual because 1466 // a min/max pattern typically has 2 uses of each op: 1 by the cmp and 1 by 1467 // the select. 1468 Value *MinMaxOp = nullptr; 1469 Value *ThirdOp = nullptr; 1470 if (!LHS->hasNUsesOrMore(3) && RHS->hasNUsesOrMore(3)) { 1471 // If the LHS is only used in this chain and the RHS is used outside of it, 1472 // reuse the RHS min/max because that will eliminate the LHS. 1473 if (D == A || C == A) { 1474 // min(min(a, b), min(c, a)) --> min(min(c, a), b) 1475 // min(min(a, b), min(a, d)) --> min(min(a, d), b) 1476 MinMaxOp = RHS; 1477 ThirdOp = B; 1478 } else if (D == B || C == B) { 1479 // min(min(a, b), min(c, b)) --> min(min(c, b), a) 1480 // min(min(a, b), min(b, d)) --> min(min(b, d), a) 1481 MinMaxOp = RHS; 1482 ThirdOp = A; 1483 } 1484 } else if (!RHS->hasNUsesOrMore(3)) { 1485 // Reuse the LHS. This will eliminate the RHS. 1486 if (D == A || D == B) { 1487 // min(min(a, b), min(c, a)) --> min(min(a, b), c) 1488 // min(min(a, b), min(c, b)) --> min(min(a, b), c) 1489 MinMaxOp = LHS; 1490 ThirdOp = C; 1491 } else if (C == A || C == B) { 1492 // min(min(a, b), min(b, d)) --> min(min(a, b), d) 1493 // min(min(a, b), min(c, b)) --> min(min(a, b), d) 1494 MinMaxOp = LHS; 1495 ThirdOp = D; 1496 } 1497 } 1498 if (!MinMaxOp || !ThirdOp) 1499 return nullptr; 1500 1501 CmpInst::Predicate P = getMinMaxPred(SPF); 1502 Value *CmpABC = Builder.CreateICmp(P, MinMaxOp, ThirdOp); 1503 return SelectInst::Create(CmpABC, MinMaxOp, ThirdOp); 1504 } 1505 1506 Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { 1507 Value *CondVal = SI.getCondition(); 1508 Value *TrueVal = SI.getTrueValue(); 1509 Value *FalseVal = SI.getFalseValue(); 1510 Type *SelType = SI.getType(); 1511 1512 // FIXME: Remove this workaround when freeze related patches are done. 1513 // For select with undef operand which feeds into an equality comparison, 1514 // don't simplify it so loop unswitch can know the equality comparison 1515 // may have an undef operand. This is a workaround for PR31652 caused by 1516 // descrepancy about branch on undef between LoopUnswitch and GVN. 1517 if (isa<UndefValue>(TrueVal) || isa<UndefValue>(FalseVal)) { 1518 if (llvm::any_of(SI.users(), [&](User *U) { 1519 ICmpInst *CI = dyn_cast<ICmpInst>(U); 1520 if (CI && CI->isEquality()) 1521 return true; 1522 return false; 1523 })) { 1524 return nullptr; 1525 } 1526 } 1527 1528 if (Value *V = SimplifySelectInst(CondVal, TrueVal, FalseVal, 1529 SQ.getWithInstruction(&SI))) 1530 return replaceInstUsesWith(SI, V); 1531 1532 if (Instruction *I = canonicalizeSelectToShuffle(SI)) 1533 return I; 1534 1535 // Canonicalize a one-use integer compare with a non-canonical predicate by 1536 // inverting the predicate and swapping the select operands. This matches a 1537 // compare canonicalization for conditional branches. 1538 // TODO: Should we do the same for FP compares? 1539 CmpInst::Predicate Pred; 1540 if (match(CondVal, m_OneUse(m_ICmp(Pred, m_Value(), m_Value()))) && 1541 !isCanonicalPredicate(Pred)) { 1542 // Swap true/false values and condition. 1543 CmpInst *Cond = cast<CmpInst>(CondVal); 1544 Cond->setPredicate(CmpInst::getInversePredicate(Pred)); 1545 SI.setOperand(1, FalseVal); 1546 SI.setOperand(2, TrueVal); 1547 SI.swapProfMetadata(); 1548 Worklist.Add(Cond); 1549 return &SI; 1550 } 1551 1552 if (SelType->isIntOrIntVectorTy(1) && 1553 TrueVal->getType() == CondVal->getType()) { 1554 if (match(TrueVal, m_One())) { 1555 // Change: A = select B, true, C --> A = or B, C 1556 return BinaryOperator::CreateOr(CondVal, FalseVal); 1557 } 1558 if (match(TrueVal, m_Zero())) { 1559 // Change: A = select B, false, C --> A = and !B, C 1560 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName()); 1561 return BinaryOperator::CreateAnd(NotCond, FalseVal); 1562 } 1563 if (match(FalseVal, m_Zero())) { 1564 // Change: A = select B, C, false --> A = and B, C 1565 return BinaryOperator::CreateAnd(CondVal, TrueVal); 1566 } 1567 if (match(FalseVal, m_One())) { 1568 // Change: A = select B, C, true --> A = or !B, C 1569 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName()); 1570 return BinaryOperator::CreateOr(NotCond, TrueVal); 1571 } 1572 1573 // select a, a, b -> a | b 1574 // select a, b, a -> a & b 1575 if (CondVal == TrueVal) 1576 return BinaryOperator::CreateOr(CondVal, FalseVal); 1577 if (CondVal == FalseVal) 1578 return BinaryOperator::CreateAnd(CondVal, TrueVal); 1579 1580 // select a, ~a, b -> (~a) & b 1581 // select a, b, ~a -> (~a) | b 1582 if (match(TrueVal, m_Not(m_Specific(CondVal)))) 1583 return BinaryOperator::CreateAnd(TrueVal, FalseVal); 1584 if (match(FalseVal, m_Not(m_Specific(CondVal)))) 1585 return BinaryOperator::CreateOr(TrueVal, FalseVal); 1586 } 1587 1588 // Selecting between two integer or vector splat integer constants? 1589 // 1590 // Note that we don't handle a scalar select of vectors: 1591 // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0> 1592 // because that may need 3 instructions to splat the condition value: 1593 // extend, insertelement, shufflevector. 1594 if (SelType->isIntOrIntVectorTy() && 1595 CondVal->getType()->isVectorTy() == SelType->isVectorTy()) { 1596 // select C, 1, 0 -> zext C to int 1597 if (match(TrueVal, m_One()) && match(FalseVal, m_Zero())) 1598 return new ZExtInst(CondVal, SelType); 1599 1600 // select C, -1, 0 -> sext C to int 1601 if (match(TrueVal, m_AllOnes()) && match(FalseVal, m_Zero())) 1602 return new SExtInst(CondVal, SelType); 1603 1604 // select C, 0, 1 -> zext !C to int 1605 if (match(TrueVal, m_Zero()) && match(FalseVal, m_One())) { 1606 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName()); 1607 return new ZExtInst(NotCond, SelType); 1608 } 1609 1610 // select C, 0, -1 -> sext !C to int 1611 if (match(TrueVal, m_Zero()) && match(FalseVal, m_AllOnes())) { 1612 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName()); 1613 return new SExtInst(NotCond, SelType); 1614 } 1615 } 1616 1617 // See if we are selecting two values based on a comparison of the two values. 1618 if (FCmpInst *FCI = dyn_cast<FCmpInst>(CondVal)) { 1619 if (FCI->getOperand(0) == TrueVal && FCI->getOperand(1) == FalseVal) { 1620 // Transform (X == Y) ? X : Y -> Y 1621 if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) { 1622 // This is not safe in general for floating point: 1623 // consider X== -0, Y== +0. 1624 // It becomes safe if either operand is a nonzero constant. 1625 ConstantFP *CFPt, *CFPf; 1626 if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && 1627 !CFPt->getValueAPF().isZero()) || 1628 ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && 1629 !CFPf->getValueAPF().isZero())) 1630 return replaceInstUsesWith(SI, FalseVal); 1631 } 1632 // Transform (X une Y) ? X : Y -> X 1633 if (FCI->getPredicate() == FCmpInst::FCMP_UNE) { 1634 // This is not safe in general for floating point: 1635 // consider X== -0, Y== +0. 1636 // It becomes safe if either operand is a nonzero constant. 1637 ConstantFP *CFPt, *CFPf; 1638 if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && 1639 !CFPt->getValueAPF().isZero()) || 1640 ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && 1641 !CFPf->getValueAPF().isZero())) 1642 return replaceInstUsesWith(SI, TrueVal); 1643 } 1644 1645 // Canonicalize to use ordered comparisons by swapping the select 1646 // operands. 1647 // 1648 // e.g. 1649 // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X 1650 if (FCI->hasOneUse() && FCmpInst::isUnordered(FCI->getPredicate())) { 1651 FCmpInst::Predicate InvPred = FCI->getInversePredicate(); 1652 IRBuilder<>::FastMathFlagGuard FMFG(Builder); 1653 Builder.setFastMathFlags(FCI->getFastMathFlags()); 1654 Value *NewCond = Builder.CreateFCmp(InvPred, TrueVal, FalseVal, 1655 FCI->getName() + ".inv"); 1656 1657 return SelectInst::Create(NewCond, FalseVal, TrueVal, 1658 SI.getName() + ".p"); 1659 } 1660 1661 // NOTE: if we wanted to, this is where to detect MIN/MAX 1662 } else if (FCI->getOperand(0) == FalseVal && FCI->getOperand(1) == TrueVal){ 1663 // Transform (X == Y) ? Y : X -> X 1664 if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) { 1665 // This is not safe in general for floating point: 1666 // consider X== -0, Y== +0. 1667 // It becomes safe if either operand is a nonzero constant. 1668 ConstantFP *CFPt, *CFPf; 1669 if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && 1670 !CFPt->getValueAPF().isZero()) || 1671 ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && 1672 !CFPf->getValueAPF().isZero())) 1673 return replaceInstUsesWith(SI, FalseVal); 1674 } 1675 // Transform (X une Y) ? Y : X -> Y 1676 if (FCI->getPredicate() == FCmpInst::FCMP_UNE) { 1677 // This is not safe in general for floating point: 1678 // consider X== -0, Y== +0. 1679 // It becomes safe if either operand is a nonzero constant. 1680 ConstantFP *CFPt, *CFPf; 1681 if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && 1682 !CFPt->getValueAPF().isZero()) || 1683 ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && 1684 !CFPf->getValueAPF().isZero())) 1685 return replaceInstUsesWith(SI, TrueVal); 1686 } 1687 1688 // Canonicalize to use ordered comparisons by swapping the select 1689 // operands. 1690 // 1691 // e.g. 1692 // (X ugt Y) ? X : Y -> (X ole Y) ? X : Y 1693 if (FCI->hasOneUse() && FCmpInst::isUnordered(FCI->getPredicate())) { 1694 FCmpInst::Predicate InvPred = FCI->getInversePredicate(); 1695 IRBuilder<>::FastMathFlagGuard FMFG(Builder); 1696 Builder.setFastMathFlags(FCI->getFastMathFlags()); 1697 Value *NewCond = Builder.CreateFCmp(InvPred, FalseVal, TrueVal, 1698 FCI->getName() + ".inv"); 1699 1700 return SelectInst::Create(NewCond, FalseVal, TrueVal, 1701 SI.getName() + ".p"); 1702 } 1703 1704 // NOTE: if we wanted to, this is where to detect MIN/MAX 1705 } 1706 1707 // Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need 1708 // fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work. We 1709 // also require nnan because we do not want to unintentionally change the 1710 // sign of a NaN value. 1711 Value *X = FCI->getOperand(0); 1712 FCmpInst::Predicate Pred = FCI->getPredicate(); 1713 if (match(FCI->getOperand(1), m_AnyZeroFP()) && FCI->hasNoNaNs()) { 1714 // (X <= +/-0.0) ? (0.0 - X) : X --> fabs(X) 1715 // (X > +/-0.0) ? X : (0.0 - X) --> fabs(X) 1716 if ((X == FalseVal && Pred == FCmpInst::FCMP_OLE && 1717 match(TrueVal, m_FSub(m_PosZeroFP(), m_Specific(X)))) || 1718 (X == TrueVal && Pred == FCmpInst::FCMP_OGT && 1719 match(FalseVal, m_FSub(m_PosZeroFP(), m_Specific(X))))) { 1720 Value *Fabs = Builder.CreateIntrinsic(Intrinsic::fabs, { X }, FCI); 1721 return replaceInstUsesWith(SI, Fabs); 1722 } 1723 // With nsz: 1724 // (X < +/-0.0) ? -X : X --> fabs(X) 1725 // (X <= +/-0.0) ? -X : X --> fabs(X) 1726 // (X > +/-0.0) ? X : -X --> fabs(X) 1727 // (X >= +/-0.0) ? X : -X --> fabs(X) 1728 if (FCI->hasNoSignedZeros() && 1729 ((X == FalseVal && match(TrueVal, m_FNeg(m_Specific(X))) && 1730 (Pred == FCmpInst::FCMP_OLT || Pred == FCmpInst::FCMP_OLE)) || 1731 (X == TrueVal && match(FalseVal, m_FNeg(m_Specific(X))) && 1732 (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_OGE)))) { 1733 Value *Fabs = Builder.CreateIntrinsic(Intrinsic::fabs, { X }, FCI); 1734 return replaceInstUsesWith(SI, Fabs); 1735 } 1736 } 1737 } 1738 1739 // See if we are selecting two values based on a comparison of the two values. 1740 if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal)) 1741 if (Instruction *Result = foldSelectInstWithICmp(SI, ICI)) 1742 return Result; 1743 1744 if (Instruction *Add = foldAddSubSelect(SI, Builder)) 1745 return Add; 1746 1747 // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z)) 1748 auto *TI = dyn_cast<Instruction>(TrueVal); 1749 auto *FI = dyn_cast<Instruction>(FalseVal); 1750 if (TI && FI && TI->getOpcode() == FI->getOpcode()) 1751 if (Instruction *IV = foldSelectOpOp(SI, TI, FI)) 1752 return IV; 1753 1754 if (Instruction *I = foldSelectExtConst(SI)) 1755 return I; 1756 1757 // See if we can fold the select into one of our operands. 1758 if (SelType->isIntOrIntVectorTy() || SelType->isFPOrFPVectorTy()) { 1759 if (Instruction *FoldI = foldSelectIntoOp(SI, TrueVal, FalseVal)) 1760 return FoldI; 1761 1762 Value *LHS, *RHS, *LHS2, *RHS2; 1763 Instruction::CastOps CastOp; 1764 SelectPatternResult SPR = matchSelectPattern(&SI, LHS, RHS, &CastOp); 1765 auto SPF = SPR.Flavor; 1766 1767 if (SelectPatternResult::isMinOrMax(SPF)) { 1768 // Canonicalize so that 1769 // - type casts are outside select patterns. 1770 // - float clamp is transformed to min/max pattern 1771 1772 bool IsCastNeeded = LHS->getType() != SelType; 1773 Value *CmpLHS = cast<CmpInst>(CondVal)->getOperand(0); 1774 Value *CmpRHS = cast<CmpInst>(CondVal)->getOperand(1); 1775 if (IsCastNeeded || 1776 (LHS->getType()->isFPOrFPVectorTy() && 1777 ((CmpLHS != LHS && CmpLHS != RHS) || 1778 (CmpRHS != LHS && CmpRHS != RHS)))) { 1779 CmpInst::Predicate Pred = getMinMaxPred(SPF, SPR.Ordered); 1780 1781 Value *Cmp; 1782 if (CmpInst::isIntPredicate(Pred)) { 1783 Cmp = Builder.CreateICmp(Pred, LHS, RHS); 1784 } else { 1785 IRBuilder<>::FastMathFlagGuard FMFG(Builder); 1786 auto FMF = cast<FPMathOperator>(SI.getCondition())->getFastMathFlags(); 1787 Builder.setFastMathFlags(FMF); 1788 Cmp = Builder.CreateFCmp(Pred, LHS, RHS); 1789 } 1790 1791 Value *NewSI = Builder.CreateSelect(Cmp, LHS, RHS, SI.getName(), &SI); 1792 if (!IsCastNeeded) 1793 return replaceInstUsesWith(SI, NewSI); 1794 1795 Value *NewCast = Builder.CreateCast(CastOp, NewSI, SelType); 1796 return replaceInstUsesWith(SI, NewCast); 1797 } 1798 1799 // MAX(~a, ~b) -> ~MIN(a, b) 1800 // MIN(~a, ~b) -> ~MAX(a, b) 1801 Value *A, *B; 1802 if (match(LHS, m_Not(m_Value(A))) && match(RHS, m_Not(m_Value(B))) && 1803 (LHS->getNumUses() <= 2 || RHS->getNumUses() <= 2)) { 1804 CmpInst::Predicate InvertedPred = getInverseMinMaxPred(SPF); 1805 Value *InvertedCmp = Builder.CreateICmp(InvertedPred, A, B); 1806 Value *NewSel = Builder.CreateSelect(InvertedCmp, A, B); 1807 return BinaryOperator::CreateNot(NewSel); 1808 } 1809 1810 if (Instruction *I = factorizeMinMaxTree(SPF, LHS, RHS, Builder)) 1811 return I; 1812 } 1813 1814 if (SPF) { 1815 // MAX(MAX(a, b), a) -> MAX(a, b) 1816 // MIN(MIN(a, b), a) -> MIN(a, b) 1817 // MAX(MIN(a, b), a) -> a 1818 // MIN(MAX(a, b), a) -> a 1819 // ABS(ABS(a)) -> ABS(a) 1820 // NABS(NABS(a)) -> NABS(a) 1821 if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor) 1822 if (Instruction *R = foldSPFofSPF(cast<Instruction>(LHS),SPF2,LHS2,RHS2, 1823 SI, SPF, RHS)) 1824 return R; 1825 if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor) 1826 if (Instruction *R = foldSPFofSPF(cast<Instruction>(RHS),SPF2,LHS2,RHS2, 1827 SI, SPF, LHS)) 1828 return R; 1829 } 1830 1831 // TODO. 1832 // ABS(-X) -> ABS(X) 1833 } 1834 1835 // See if we can fold the select into a phi node if the condition is a select. 1836 if (auto *PN = dyn_cast<PHINode>(SI.getCondition())) 1837 // The true/false values have to be live in the PHI predecessor's blocks. 1838 if (canSelectOperandBeMappingIntoPredBlock(TrueVal, SI) && 1839 canSelectOperandBeMappingIntoPredBlock(FalseVal, SI)) 1840 if (Instruction *NV = foldOpIntoPhi(SI, PN)) 1841 return NV; 1842 1843 if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) { 1844 if (TrueSI->getCondition()->getType() == CondVal->getType()) { 1845 // select(C, select(C, a, b), c) -> select(C, a, c) 1846 if (TrueSI->getCondition() == CondVal) { 1847 if (SI.getTrueValue() == TrueSI->getTrueValue()) 1848 return nullptr; 1849 SI.setOperand(1, TrueSI->getTrueValue()); 1850 return &SI; 1851 } 1852 // select(C0, select(C1, a, b), b) -> select(C0&C1, a, b) 1853 // We choose this as normal form to enable folding on the And and shortening 1854 // paths for the values (this helps GetUnderlyingObjects() for example). 1855 if (TrueSI->getFalseValue() == FalseVal && TrueSI->hasOneUse()) { 1856 Value *And = Builder.CreateAnd(CondVal, TrueSI->getCondition()); 1857 SI.setOperand(0, And); 1858 SI.setOperand(1, TrueSI->getTrueValue()); 1859 return &SI; 1860 } 1861 } 1862 } 1863 if (SelectInst *FalseSI = dyn_cast<SelectInst>(FalseVal)) { 1864 if (FalseSI->getCondition()->getType() == CondVal->getType()) { 1865 // select(C, a, select(C, b, c)) -> select(C, a, c) 1866 if (FalseSI->getCondition() == CondVal) { 1867 if (SI.getFalseValue() == FalseSI->getFalseValue()) 1868 return nullptr; 1869 SI.setOperand(2, FalseSI->getFalseValue()); 1870 return &SI; 1871 } 1872 // select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b) 1873 if (FalseSI->getTrueValue() == TrueVal && FalseSI->hasOneUse()) { 1874 Value *Or = Builder.CreateOr(CondVal, FalseSI->getCondition()); 1875 SI.setOperand(0, Or); 1876 SI.setOperand(2, FalseSI->getFalseValue()); 1877 return &SI; 1878 } 1879 } 1880 } 1881 1882 auto canMergeSelectThroughBinop = [](BinaryOperator *BO) { 1883 // The select might be preventing a division by 0. 1884 switch (BO->getOpcode()) { 1885 default: 1886 return true; 1887 case Instruction::SRem: 1888 case Instruction::URem: 1889 case Instruction::SDiv: 1890 case Instruction::UDiv: 1891 return false; 1892 } 1893 }; 1894 1895 // Try to simplify a binop sandwiched between 2 selects with the same 1896 // condition. 1897 // select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z) 1898 BinaryOperator *TrueBO; 1899 if (match(TrueVal, m_OneUse(m_BinOp(TrueBO))) && 1900 canMergeSelectThroughBinop(TrueBO)) { 1901 if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(0))) { 1902 if (TrueBOSI->getCondition() == CondVal) { 1903 TrueBO->setOperand(0, TrueBOSI->getTrueValue()); 1904 Worklist.Add(TrueBO); 1905 return &SI; 1906 } 1907 } 1908 if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(1))) { 1909 if (TrueBOSI->getCondition() == CondVal) { 1910 TrueBO->setOperand(1, TrueBOSI->getTrueValue()); 1911 Worklist.Add(TrueBO); 1912 return &SI; 1913 } 1914 } 1915 } 1916 1917 // select(C, Z, binop(select(C, X, Y), W)) -> select(C, Z, binop(Y, W)) 1918 BinaryOperator *FalseBO; 1919 if (match(FalseVal, m_OneUse(m_BinOp(FalseBO))) && 1920 canMergeSelectThroughBinop(FalseBO)) { 1921 if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(0))) { 1922 if (FalseBOSI->getCondition() == CondVal) { 1923 FalseBO->setOperand(0, FalseBOSI->getFalseValue()); 1924 Worklist.Add(FalseBO); 1925 return &SI; 1926 } 1927 } 1928 if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(1))) { 1929 if (FalseBOSI->getCondition() == CondVal) { 1930 FalseBO->setOperand(1, FalseBOSI->getFalseValue()); 1931 Worklist.Add(FalseBO); 1932 return &SI; 1933 } 1934 } 1935 } 1936 1937 if (BinaryOperator::isNot(CondVal)) { 1938 SI.setOperand(0, BinaryOperator::getNotArgument(CondVal)); 1939 SI.setOperand(1, FalseVal); 1940 SI.setOperand(2, TrueVal); 1941 return &SI; 1942 } 1943 1944 if (VectorType *VecTy = dyn_cast<VectorType>(SelType)) { 1945 unsigned VWidth = VecTy->getNumElements(); 1946 APInt UndefElts(VWidth, 0); 1947 APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); 1948 if (Value *V = SimplifyDemandedVectorElts(&SI, AllOnesEltMask, UndefElts)) { 1949 if (V != &SI) 1950 return replaceInstUsesWith(SI, V); 1951 return &SI; 1952 } 1953 } 1954 1955 // See if we can determine the result of this select based on a dominating 1956 // condition. 1957 BasicBlock *Parent = SI.getParent(); 1958 if (BasicBlock *Dom = Parent->getSinglePredecessor()) { 1959 auto *PBI = dyn_cast_or_null<BranchInst>(Dom->getTerminator()); 1960 if (PBI && PBI->isConditional() && 1961 PBI->getSuccessor(0) != PBI->getSuccessor(1) && 1962 (PBI->getSuccessor(0) == Parent || PBI->getSuccessor(1) == Parent)) { 1963 bool CondIsTrue = PBI->getSuccessor(0) == Parent; 1964 Optional<bool> Implication = isImpliedCondition( 1965 PBI->getCondition(), SI.getCondition(), DL, CondIsTrue); 1966 if (Implication) { 1967 Value *V = *Implication ? TrueVal : FalseVal; 1968 return replaceInstUsesWith(SI, V); 1969 } 1970 } 1971 } 1972 1973 // If we can compute the condition, there's no need for a select. 1974 // Like the above fold, we are attempting to reduce compile-time cost by 1975 // putting this fold here with limitations rather than in InstSimplify. 1976 // The motivation for this call into value tracking is to take advantage of 1977 // the assumption cache, so make sure that is populated. 1978 if (!CondVal->getType()->isVectorTy() && !AC.assumptions().empty()) { 1979 KnownBits Known(1); 1980 computeKnownBits(CondVal, Known, 0, &SI); 1981 if (Known.One.isOneValue()) 1982 return replaceInstUsesWith(SI, TrueVal); 1983 if (Known.Zero.isOneValue()) 1984 return replaceInstUsesWith(SI, FalseVal); 1985 } 1986 1987 if (Instruction *BitCastSel = foldSelectCmpBitcasts(SI, Builder)) 1988 return BitCastSel; 1989 1990 // Simplify selects that test the returned flag of cmpxchg instructions. 1991 if (Instruction *Select = foldSelectCmpXchg(SI)) 1992 return Select; 1993 1994 if (Instruction *Select = foldSelectBinOpIdentity(SI)) 1995 return Select; 1996 1997 return nullptr; 1998 } 1999