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 "InstCombine.h" 15 #include "llvm/Analysis/ConstantFolding.h" 16 #include "llvm/Analysis/InstructionSimplify.h" 17 #include "llvm/IR/PatternMatch.h" 18 using namespace llvm; 19 using namespace PatternMatch; 20 21 #define DEBUG_TYPE "instcombine" 22 23 /// MatchSelectPattern - Pattern match integer [SU]MIN, [SU]MAX, and ABS idioms, 24 /// returning the kind and providing the out parameter results if we 25 /// successfully match. 26 static SelectPatternFlavor 27 MatchSelectPattern(Value *V, Value *&LHS, Value *&RHS) { 28 SelectInst *SI = dyn_cast<SelectInst>(V); 29 if (!SI) return SPF_UNKNOWN; 30 31 ICmpInst *ICI = dyn_cast<ICmpInst>(SI->getCondition()); 32 if (!ICI) return SPF_UNKNOWN; 33 34 ICmpInst::Predicate Pred = ICI->getPredicate(); 35 Value *CmpLHS = ICI->getOperand(0); 36 Value *CmpRHS = ICI->getOperand(1); 37 Value *TrueVal = SI->getTrueValue(); 38 Value *FalseVal = SI->getFalseValue(); 39 40 LHS = CmpLHS; 41 RHS = CmpRHS; 42 43 // (icmp X, Y) ? X : Y 44 if (TrueVal == CmpLHS && FalseVal == CmpRHS) { 45 switch (Pred) { 46 default: return SPF_UNKNOWN; // Equality. 47 case ICmpInst::ICMP_UGT: 48 case ICmpInst::ICMP_UGE: return SPF_UMAX; 49 case ICmpInst::ICMP_SGT: 50 case ICmpInst::ICMP_SGE: return SPF_SMAX; 51 case ICmpInst::ICMP_ULT: 52 case ICmpInst::ICMP_ULE: return SPF_UMIN; 53 case ICmpInst::ICMP_SLT: 54 case ICmpInst::ICMP_SLE: return SPF_SMIN; 55 } 56 } 57 58 // (icmp X, Y) ? Y : X 59 if (TrueVal == CmpRHS && FalseVal == CmpLHS) { 60 switch (Pred) { 61 default: return SPF_UNKNOWN; // Equality. 62 case ICmpInst::ICMP_UGT: 63 case ICmpInst::ICMP_UGE: return SPF_UMIN; 64 case ICmpInst::ICMP_SGT: 65 case ICmpInst::ICMP_SGE: return SPF_SMIN; 66 case ICmpInst::ICMP_ULT: 67 case ICmpInst::ICMP_ULE: return SPF_UMAX; 68 case ICmpInst::ICMP_SLT: 69 case ICmpInst::ICMP_SLE: return SPF_SMAX; 70 } 71 } 72 73 if (ConstantInt *C1 = dyn_cast<ConstantInt>(CmpRHS)) { 74 if ((CmpLHS == TrueVal && match(FalseVal, m_Neg(m_Specific(CmpLHS)))) || 75 (CmpLHS == FalseVal && match(TrueVal, m_Neg(m_Specific(CmpLHS))))) { 76 77 // ABS(X) ==> (X >s 0) ? X : -X and (X >s -1) ? X : -X 78 // NABS(X) ==> (X >s 0) ? -X : X and (X >s -1) ? -X : X 79 if (Pred == ICmpInst::ICMP_SGT && (C1->isZero() || C1->isMinusOne())) { 80 return (CmpLHS == TrueVal) ? SPF_ABS : SPF_NABS; 81 } 82 83 // ABS(X) ==> (X <s 0) ? -X : X and (X <s 1) ? -X : X 84 // NABS(X) ==> (X <s 0) ? X : -X and (X <s 1) ? X : -X 85 if (Pred == ICmpInst::ICMP_SLT && (C1->isZero() || C1->isOne())) { 86 return (CmpLHS == FalseVal) ? SPF_ABS : SPF_NABS; 87 } 88 } 89 } 90 91 // TODO: (X > 4) ? X : 5 --> (X >= 5) ? X : 5 --> MAX(X, 5) 92 93 return SPF_UNKNOWN; 94 } 95 96 97 /// GetSelectFoldableOperands - We want to turn code that looks like this: 98 /// %C = or %A, %B 99 /// %D = select %cond, %C, %A 100 /// into: 101 /// %C = select %cond, %B, 0 102 /// %D = or %A, %C 103 /// 104 /// Assuming that the specified instruction is an operand to the select, return 105 /// a bitmask indicating which operands of this instruction are foldable if they 106 /// equal the other incoming value of the select. 107 /// 108 static unsigned GetSelectFoldableOperands(Instruction *I) { 109 switch (I->getOpcode()) { 110 case Instruction::Add: 111 case Instruction::Mul: 112 case Instruction::And: 113 case Instruction::Or: 114 case Instruction::Xor: 115 return 3; // Can fold through either operand. 116 case Instruction::Sub: // Can only fold on the amount subtracted. 117 case Instruction::Shl: // Can only fold on the shift amount. 118 case Instruction::LShr: 119 case Instruction::AShr: 120 return 1; 121 default: 122 return 0; // Cannot fold 123 } 124 } 125 126 /// GetSelectFoldableConstant - For the same transformation as the previous 127 /// function, return the identity constant that goes into the select. 128 static Constant *GetSelectFoldableConstant(Instruction *I) { 129 switch (I->getOpcode()) { 130 default: llvm_unreachable("This cannot happen!"); 131 case Instruction::Add: 132 case Instruction::Sub: 133 case Instruction::Or: 134 case Instruction::Xor: 135 case Instruction::Shl: 136 case Instruction::LShr: 137 case Instruction::AShr: 138 return Constant::getNullValue(I->getType()); 139 case Instruction::And: 140 return Constant::getAllOnesValue(I->getType()); 141 case Instruction::Mul: 142 return ConstantInt::get(I->getType(), 1); 143 } 144 } 145 146 /// FoldSelectOpOp - Here we have (select c, TI, FI), and we know that TI and FI 147 /// have the same opcode and only one use each. Try to simplify this. 148 Instruction *InstCombiner::FoldSelectOpOp(SelectInst &SI, Instruction *TI, 149 Instruction *FI) { 150 if (TI->getNumOperands() == 1) { 151 // If this is a non-volatile load or a cast from the same type, 152 // merge. 153 if (TI->isCast()) { 154 Type *FIOpndTy = FI->getOperand(0)->getType(); 155 if (TI->getOperand(0)->getType() != FIOpndTy) 156 return nullptr; 157 // The select condition may be a vector. We may only change the operand 158 // type if the vector width remains the same (and matches the condition). 159 Type *CondTy = SI.getCondition()->getType(); 160 if (CondTy->isVectorTy() && (!FIOpndTy->isVectorTy() || 161 CondTy->getVectorNumElements() != FIOpndTy->getVectorNumElements())) 162 return nullptr; 163 } else { 164 return nullptr; // unknown unary op. 165 } 166 167 // Fold this by inserting a select from the input values. 168 Value *NewSI = Builder->CreateSelect(SI.getCondition(), TI->getOperand(0), 169 FI->getOperand(0), SI.getName()+".v"); 170 return CastInst::Create(Instruction::CastOps(TI->getOpcode()), NewSI, 171 TI->getType()); 172 } 173 174 // Only handle binary operators here. 175 if (!isa<BinaryOperator>(TI)) 176 return nullptr; 177 178 // Figure out if the operations have any operands in common. 179 Value *MatchOp, *OtherOpT, *OtherOpF; 180 bool MatchIsOpZero; 181 if (TI->getOperand(0) == FI->getOperand(0)) { 182 MatchOp = TI->getOperand(0); 183 OtherOpT = TI->getOperand(1); 184 OtherOpF = FI->getOperand(1); 185 MatchIsOpZero = true; 186 } else if (TI->getOperand(1) == FI->getOperand(1)) { 187 MatchOp = TI->getOperand(1); 188 OtherOpT = TI->getOperand(0); 189 OtherOpF = FI->getOperand(0); 190 MatchIsOpZero = false; 191 } else if (!TI->isCommutative()) { 192 return nullptr; 193 } else if (TI->getOperand(0) == FI->getOperand(1)) { 194 MatchOp = TI->getOperand(0); 195 OtherOpT = TI->getOperand(1); 196 OtherOpF = FI->getOperand(0); 197 MatchIsOpZero = true; 198 } else if (TI->getOperand(1) == FI->getOperand(0)) { 199 MatchOp = TI->getOperand(1); 200 OtherOpT = TI->getOperand(0); 201 OtherOpF = FI->getOperand(1); 202 MatchIsOpZero = true; 203 } else { 204 return nullptr; 205 } 206 207 // If we reach here, they do have operations in common. 208 Value *NewSI = Builder->CreateSelect(SI.getCondition(), OtherOpT, 209 OtherOpF, SI.getName()+".v"); 210 211 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TI)) { 212 if (MatchIsOpZero) 213 return BinaryOperator::Create(BO->getOpcode(), MatchOp, NewSI); 214 else 215 return BinaryOperator::Create(BO->getOpcode(), NewSI, MatchOp); 216 } 217 llvm_unreachable("Shouldn't get here"); 218 } 219 220 static bool isSelect01(Constant *C1, Constant *C2) { 221 ConstantInt *C1I = dyn_cast<ConstantInt>(C1); 222 if (!C1I) 223 return false; 224 ConstantInt *C2I = dyn_cast<ConstantInt>(C2); 225 if (!C2I) 226 return false; 227 if (!C1I->isZero() && !C2I->isZero()) // One side must be zero. 228 return false; 229 return C1I->isOne() || C1I->isAllOnesValue() || 230 C2I->isOne() || C2I->isAllOnesValue(); 231 } 232 233 /// FoldSelectIntoOp - Try fold the select into one of the operands to 234 /// facilitate further optimization. 235 Instruction *InstCombiner::FoldSelectIntoOp(SelectInst &SI, Value *TrueVal, 236 Value *FalseVal) { 237 // See the comment above GetSelectFoldableOperands for a description of the 238 // transformation we are doing here. 239 if (Instruction *TVI = dyn_cast<Instruction>(TrueVal)) { 240 if (TVI->hasOneUse() && TVI->getNumOperands() == 2 && 241 !isa<Constant>(FalseVal)) { 242 if (unsigned SFO = GetSelectFoldableOperands(TVI)) { 243 unsigned OpToFold = 0; 244 if ((SFO & 1) && FalseVal == TVI->getOperand(0)) { 245 OpToFold = 1; 246 } else if ((SFO & 2) && FalseVal == TVI->getOperand(1)) { 247 OpToFold = 2; 248 } 249 250 if (OpToFold) { 251 Constant *C = GetSelectFoldableConstant(TVI); 252 Value *OOp = TVI->getOperand(2-OpToFold); 253 // Avoid creating select between 2 constants unless it's selecting 254 // between 0, 1 and -1. 255 if (!isa<Constant>(OOp) || isSelect01(C, cast<Constant>(OOp))) { 256 Value *NewSel = Builder->CreateSelect(SI.getCondition(), OOp, C); 257 NewSel->takeName(TVI); 258 BinaryOperator *TVI_BO = cast<BinaryOperator>(TVI); 259 BinaryOperator *BO = BinaryOperator::Create(TVI_BO->getOpcode(), 260 FalseVal, NewSel); 261 if (isa<PossiblyExactOperator>(BO)) 262 BO->setIsExact(TVI_BO->isExact()); 263 if (isa<OverflowingBinaryOperator>(BO)) { 264 BO->setHasNoUnsignedWrap(TVI_BO->hasNoUnsignedWrap()); 265 BO->setHasNoSignedWrap(TVI_BO->hasNoSignedWrap()); 266 } 267 return BO; 268 } 269 } 270 } 271 } 272 } 273 274 if (Instruction *FVI = dyn_cast<Instruction>(FalseVal)) { 275 if (FVI->hasOneUse() && FVI->getNumOperands() == 2 && 276 !isa<Constant>(TrueVal)) { 277 if (unsigned SFO = GetSelectFoldableOperands(FVI)) { 278 unsigned OpToFold = 0; 279 if ((SFO & 1) && TrueVal == FVI->getOperand(0)) { 280 OpToFold = 1; 281 } else if ((SFO & 2) && TrueVal == FVI->getOperand(1)) { 282 OpToFold = 2; 283 } 284 285 if (OpToFold) { 286 Constant *C = GetSelectFoldableConstant(FVI); 287 Value *OOp = FVI->getOperand(2-OpToFold); 288 // Avoid creating select between 2 constants unless it's selecting 289 // between 0, 1 and -1. 290 if (!isa<Constant>(OOp) || isSelect01(C, cast<Constant>(OOp))) { 291 Value *NewSel = Builder->CreateSelect(SI.getCondition(), C, OOp); 292 NewSel->takeName(FVI); 293 BinaryOperator *FVI_BO = cast<BinaryOperator>(FVI); 294 BinaryOperator *BO = BinaryOperator::Create(FVI_BO->getOpcode(), 295 TrueVal, NewSel); 296 if (isa<PossiblyExactOperator>(BO)) 297 BO->setIsExact(FVI_BO->isExact()); 298 if (isa<OverflowingBinaryOperator>(BO)) { 299 BO->setHasNoUnsignedWrap(FVI_BO->hasNoUnsignedWrap()); 300 BO->setHasNoSignedWrap(FVI_BO->hasNoSignedWrap()); 301 } 302 return BO; 303 } 304 } 305 } 306 } 307 } 308 309 return nullptr; 310 } 311 312 /// SimplifyWithOpReplaced - See if V simplifies when its operand Op is 313 /// replaced with RepOp. 314 static Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp, 315 const DataLayout *TD, 316 const TargetLibraryInfo *TLI) { 317 // Trivial replacement. 318 if (V == Op) 319 return RepOp; 320 321 Instruction *I = dyn_cast<Instruction>(V); 322 if (!I) 323 return nullptr; 324 325 // If this is a binary operator, try to simplify it with the replaced op. 326 if (BinaryOperator *B = dyn_cast<BinaryOperator>(I)) { 327 if (B->getOperand(0) == Op) 328 return SimplifyBinOp(B->getOpcode(), RepOp, B->getOperand(1), TD, TLI); 329 if (B->getOperand(1) == Op) 330 return SimplifyBinOp(B->getOpcode(), B->getOperand(0), RepOp, TD, TLI); 331 } 332 333 // Same for CmpInsts. 334 if (CmpInst *C = dyn_cast<CmpInst>(I)) { 335 if (C->getOperand(0) == Op) 336 return SimplifyCmpInst(C->getPredicate(), RepOp, C->getOperand(1), TD, 337 TLI); 338 if (C->getOperand(1) == Op) 339 return SimplifyCmpInst(C->getPredicate(), C->getOperand(0), RepOp, TD, 340 TLI); 341 } 342 343 // TODO: We could hand off more cases to instsimplify here. 344 345 // If all operands are constant after substituting Op for RepOp then we can 346 // constant fold the instruction. 347 if (Constant *CRepOp = dyn_cast<Constant>(RepOp)) { 348 // Build a list of all constant operands. 349 SmallVector<Constant*, 8> ConstOps; 350 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 351 if (I->getOperand(i) == Op) 352 ConstOps.push_back(CRepOp); 353 else if (Constant *COp = dyn_cast<Constant>(I->getOperand(i))) 354 ConstOps.push_back(COp); 355 else 356 break; 357 } 358 359 // All operands were constants, fold it. 360 if (ConstOps.size() == I->getNumOperands()) { 361 if (CmpInst *C = dyn_cast<CmpInst>(I)) 362 return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0], 363 ConstOps[1], TD, TLI); 364 365 if (LoadInst *LI = dyn_cast<LoadInst>(I)) 366 if (!LI->isVolatile()) 367 return ConstantFoldLoadFromConstPtr(ConstOps[0], TD); 368 369 return ConstantFoldInstOperands(I->getOpcode(), I->getType(), 370 ConstOps, TD, TLI); 371 } 372 } 373 374 return nullptr; 375 } 376 377 /// foldSelectICmpAndOr - We want to turn: 378 /// (select (icmp eq (and X, C1), 0), Y, (or Y, C2)) 379 /// into: 380 /// (or (shl (and X, C1), C3), y) 381 /// iff: 382 /// C1 and C2 are both powers of 2 383 /// where: 384 /// C3 = Log(C2) - Log(C1) 385 /// 386 /// This transform handles cases where: 387 /// 1. The icmp predicate is inverted 388 /// 2. The select operands are reversed 389 /// 3. The magnitude of C2 and C1 are flipped 390 /// 391 /// This also tries to turn 392 /// --- Single bit tests: 393 /// if ((x & C) == 0) x |= C to x |= C 394 /// if ((x & C) != 0) x ^= C to x &= ~C 395 /// if ((x & C) == 0) x ^= C to x |= C 396 /// if ((x & C) != 0) x &= ~C to x &= ~C 397 /// if ((x & C) == 0) x &= ~C to nothing 398 static Value *foldSelectICmpAndOr(SelectInst &SI, Value *TrueVal, 399 Value *FalseVal, 400 InstCombiner::BuilderTy *Builder) { 401 const ICmpInst *IC = dyn_cast<ICmpInst>(SI.getCondition()); 402 if (!IC || !IC->isEquality() || !SI.getType()->isIntegerTy()) 403 return nullptr; 404 405 Value *CmpLHS = IC->getOperand(0); 406 Value *CmpRHS = IC->getOperand(1); 407 408 if (!match(CmpRHS, m_Zero())) 409 return nullptr; 410 411 Value *X; 412 const APInt *C1; 413 if (!match(CmpLHS, m_And(m_Value(X), m_Power2(C1)))) 414 return nullptr; 415 416 const APInt *C2; 417 if (match(TrueVal, m_Specific(X))) { 418 // if ((X & C) != 0) X ^= C becomes X &= ~C 419 if (match(FalseVal, m_Xor(m_Specific(X), m_APInt(C2))) && C1 == C2) 420 return Builder->CreateAnd(X, ~(*C1)); 421 // if ((X & C) != 0) X &= ~C becomes X &= ~C 422 if (match(FalseVal, m_And(m_Specific(X), m_APInt(C2))) && *C1 == ~(*C2)) 423 return FalseVal; 424 } else if (match(FalseVal, m_Specific(X))) { 425 // if ((X & C) == 0) X ^= C becomes X |= C 426 if (match(TrueVal, m_Xor(m_Specific(X), m_APInt(C2))) && C1 == C2) 427 return Builder->CreateOr(X, *C1); 428 // if ((X & C) == 0) X &= ~C becomes nothing 429 if (match(TrueVal, m_And(m_Specific(X), m_APInt(C2))) && *C1 == ~(*C2)) 430 return X; 431 // if ((X & C) == 0) X |= C becomes X |= C 432 if (match(TrueVal, m_Or(m_Specific(X), m_APInt(C2))) && C1 == C2) 433 return TrueVal; 434 } 435 436 bool OrOnTrueVal = false; 437 bool OrOnFalseVal = match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2))); 438 if (!OrOnFalseVal) 439 OrOnTrueVal = match(TrueVal, m_Or(m_Specific(FalseVal), m_Power2(C2))); 440 441 if (!OrOnFalseVal && !OrOnTrueVal) 442 return nullptr; 443 444 Value *V = CmpLHS; 445 Value *Y = OrOnFalseVal ? TrueVal : FalseVal; 446 447 unsigned C1Log = C1->logBase2(); 448 unsigned C2Log = C2->logBase2(); 449 if (C2Log > C1Log) { 450 V = Builder->CreateZExtOrTrunc(V, Y->getType()); 451 V = Builder->CreateShl(V, C2Log - C1Log); 452 } else if (C1Log > C2Log) { 453 V = Builder->CreateLShr(V, C1Log - C2Log); 454 V = Builder->CreateZExtOrTrunc(V, Y->getType()); 455 } else 456 V = Builder->CreateZExtOrTrunc(V, Y->getType()); 457 458 ICmpInst::Predicate Pred = IC->getPredicate(); 459 if ((Pred == ICmpInst::ICMP_NE && OrOnFalseVal) || 460 (Pred == ICmpInst::ICMP_EQ && OrOnTrueVal)) 461 V = Builder->CreateXor(V, *C2); 462 463 return Builder->CreateOr(V, Y); 464 } 465 466 /// visitSelectInstWithICmp - Visit a SelectInst that has an 467 /// ICmpInst as its first operand. 468 /// 469 Instruction *InstCombiner::visitSelectInstWithICmp(SelectInst &SI, 470 ICmpInst *ICI) { 471 bool Changed = false; 472 ICmpInst::Predicate Pred = ICI->getPredicate(); 473 Value *CmpLHS = ICI->getOperand(0); 474 Value *CmpRHS = ICI->getOperand(1); 475 Value *TrueVal = SI.getTrueValue(); 476 Value *FalseVal = SI.getFalseValue(); 477 478 // Check cases where the comparison is with a constant that 479 // can be adjusted to fit the min/max idiom. We may move or edit ICI 480 // here, so make sure the select is the only user. 481 if (ICI->hasOneUse()) 482 if (ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS)) { 483 // X < MIN ? T : F --> F 484 if ((Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT) 485 && CI->isMinValue(Pred == ICmpInst::ICMP_SLT)) 486 return ReplaceInstUsesWith(SI, FalseVal); 487 // X > MAX ? T : F --> F 488 else if ((Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT) 489 && CI->isMaxValue(Pred == ICmpInst::ICMP_SGT)) 490 return ReplaceInstUsesWith(SI, FalseVal); 491 switch (Pred) { 492 default: break; 493 case ICmpInst::ICMP_ULT: 494 case ICmpInst::ICMP_SLT: 495 case ICmpInst::ICMP_UGT: 496 case ICmpInst::ICMP_SGT: { 497 // These transformations only work for selects over integers. 498 IntegerType *SelectTy = dyn_cast<IntegerType>(SI.getType()); 499 if (!SelectTy) 500 break; 501 502 Constant *AdjustedRHS; 503 if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_SGT) 504 AdjustedRHS = ConstantInt::get(CI->getContext(), CI->getValue() + 1); 505 else // (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_SLT) 506 AdjustedRHS = ConstantInt::get(CI->getContext(), CI->getValue() - 1); 507 508 // X > C ? X : C+1 --> X < C+1 ? C+1 : X 509 // X < C ? X : C-1 --> X > C-1 ? C-1 : X 510 if ((CmpLHS == TrueVal && AdjustedRHS == FalseVal) || 511 (CmpLHS == FalseVal && AdjustedRHS == TrueVal)) 512 ; // Nothing to do here. Values match without any sign/zero extension. 513 514 // Types do not match. Instead of calculating this with mixed types 515 // promote all to the larger type. This enables scalar evolution to 516 // analyze this expression. 517 else if (CmpRHS->getType()->getScalarSizeInBits() 518 < SelectTy->getBitWidth()) { 519 Constant *sextRHS = ConstantExpr::getSExt(AdjustedRHS, SelectTy); 520 521 // X = sext x; x >s c ? X : C+1 --> X = sext x; X <s C+1 ? C+1 : X 522 // X = sext x; x <s c ? X : C-1 --> X = sext x; X >s C-1 ? C-1 : X 523 // X = sext x; x >u c ? X : C+1 --> X = sext x; X <u C+1 ? C+1 : X 524 // X = sext x; x <u c ? X : C-1 --> X = sext x; X >u C-1 ? C-1 : X 525 if (match(TrueVal, m_SExt(m_Specific(CmpLHS))) && 526 sextRHS == FalseVal) { 527 CmpLHS = TrueVal; 528 AdjustedRHS = sextRHS; 529 } else if (match(FalseVal, m_SExt(m_Specific(CmpLHS))) && 530 sextRHS == TrueVal) { 531 CmpLHS = FalseVal; 532 AdjustedRHS = sextRHS; 533 } else if (ICI->isUnsigned()) { 534 Constant *zextRHS = ConstantExpr::getZExt(AdjustedRHS, SelectTy); 535 // X = zext x; x >u c ? X : C+1 --> X = zext x; X <u C+1 ? C+1 : X 536 // X = zext x; x <u c ? X : C-1 --> X = zext x; X >u C-1 ? C-1 : X 537 // zext + signed compare cannot be changed: 538 // 0xff <s 0x00, but 0x00ff >s 0x0000 539 if (match(TrueVal, m_ZExt(m_Specific(CmpLHS))) && 540 zextRHS == FalseVal) { 541 CmpLHS = TrueVal; 542 AdjustedRHS = zextRHS; 543 } else if (match(FalseVal, m_ZExt(m_Specific(CmpLHS))) && 544 zextRHS == TrueVal) { 545 CmpLHS = FalseVal; 546 AdjustedRHS = zextRHS; 547 } else 548 break; 549 } else 550 break; 551 } else 552 break; 553 554 Pred = ICmpInst::getSwappedPredicate(Pred); 555 CmpRHS = AdjustedRHS; 556 std::swap(FalseVal, TrueVal); 557 ICI->setPredicate(Pred); 558 ICI->setOperand(0, CmpLHS); 559 ICI->setOperand(1, CmpRHS); 560 SI.setOperand(1, TrueVal); 561 SI.setOperand(2, FalseVal); 562 563 // Move ICI instruction right before the select instruction. Otherwise 564 // the sext/zext value may be defined after the ICI instruction uses it. 565 ICI->moveBefore(&SI); 566 567 Changed = true; 568 break; 569 } 570 } 571 } 572 573 // Transform (X >s -1) ? C1 : C2 --> ((X >>s 31) & (C2 - C1)) + C1 574 // and (X <s 0) ? C2 : C1 --> ((X >>s 31) & (C2 - C1)) + C1 575 // FIXME: Type and constness constraints could be lifted, but we have to 576 // watch code size carefully. We should consider xor instead of 577 // sub/add when we decide to do that. 578 if (IntegerType *Ty = dyn_cast<IntegerType>(CmpLHS->getType())) { 579 if (TrueVal->getType() == Ty) { 580 if (ConstantInt *Cmp = dyn_cast<ConstantInt>(CmpRHS)) { 581 ConstantInt *C1 = nullptr, *C2 = nullptr; 582 if (Pred == ICmpInst::ICMP_SGT && Cmp->isAllOnesValue()) { 583 C1 = dyn_cast<ConstantInt>(TrueVal); 584 C2 = dyn_cast<ConstantInt>(FalseVal); 585 } else if (Pred == ICmpInst::ICMP_SLT && Cmp->isNullValue()) { 586 C1 = dyn_cast<ConstantInt>(FalseVal); 587 C2 = dyn_cast<ConstantInt>(TrueVal); 588 } 589 if (C1 && C2) { 590 // This shift results in either -1 or 0. 591 Value *AShr = Builder->CreateAShr(CmpLHS, Ty->getBitWidth()-1); 592 593 // Check if we can express the operation with a single or. 594 if (C2->isAllOnesValue()) 595 return ReplaceInstUsesWith(SI, Builder->CreateOr(AShr, C1)); 596 597 Value *And = Builder->CreateAnd(AShr, C2->getValue()-C1->getValue()); 598 return ReplaceInstUsesWith(SI, Builder->CreateAdd(And, C1)); 599 } 600 } 601 } 602 } 603 604 // If we have an equality comparison then we know the value in one of the 605 // arms of the select. See if substituting this value into the arm and 606 // simplifying the result yields the same value as the other arm. 607 if (Pred == ICmpInst::ICMP_EQ) { 608 if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, DL, TLI) == TrueVal || 609 SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, DL, TLI) == TrueVal) 610 return ReplaceInstUsesWith(SI, FalseVal); 611 if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, DL, TLI) == FalseVal || 612 SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, DL, TLI) == FalseVal) 613 return ReplaceInstUsesWith(SI, FalseVal); 614 } else if (Pred == ICmpInst::ICMP_NE) { 615 if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, DL, TLI) == FalseVal || 616 SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, DL, TLI) == FalseVal) 617 return ReplaceInstUsesWith(SI, TrueVal); 618 if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, DL, TLI) == TrueVal || 619 SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, DL, TLI) == TrueVal) 620 return ReplaceInstUsesWith(SI, TrueVal); 621 } 622 623 // NOTE: if we wanted to, this is where to detect integer MIN/MAX 624 625 if (CmpRHS != CmpLHS && isa<Constant>(CmpRHS)) { 626 if (CmpLHS == TrueVal && Pred == ICmpInst::ICMP_EQ) { 627 // Transform (X == C) ? X : Y -> (X == C) ? C : Y 628 SI.setOperand(1, CmpRHS); 629 Changed = true; 630 } else if (CmpLHS == FalseVal && Pred == ICmpInst::ICMP_NE) { 631 // Transform (X != C) ? Y : X -> (X != C) ? Y : C 632 SI.setOperand(2, CmpRHS); 633 Changed = true; 634 } 635 } 636 637 if (Value *V = foldSelectICmpAndOr(SI, TrueVal, FalseVal, Builder)) 638 return ReplaceInstUsesWith(SI, V); 639 640 return Changed ? &SI : nullptr; 641 } 642 643 644 /// CanSelectOperandBeMappingIntoPredBlock - SI is a select whose condition is a 645 /// PHI node (but the two may be in different blocks). See if the true/false 646 /// values (V) are live in all of the predecessor blocks of the PHI. For 647 /// example, cases like this cannot be mapped: 648 /// 649 /// X = phi [ C1, BB1], [C2, BB2] 650 /// Y = add 651 /// Z = select X, Y, 0 652 /// 653 /// because Y is not live in BB1/BB2. 654 /// 655 static bool CanSelectOperandBeMappingIntoPredBlock(const Value *V, 656 const SelectInst &SI) { 657 // If the value is a non-instruction value like a constant or argument, it 658 // can always be mapped. 659 const Instruction *I = dyn_cast<Instruction>(V); 660 if (!I) return true; 661 662 // If V is a PHI node defined in the same block as the condition PHI, we can 663 // map the arguments. 664 const PHINode *CondPHI = cast<PHINode>(SI.getCondition()); 665 666 if (const PHINode *VP = dyn_cast<PHINode>(I)) 667 if (VP->getParent() == CondPHI->getParent()) 668 return true; 669 670 // Otherwise, if the PHI and select are defined in the same block and if V is 671 // defined in a different block, then we can transform it. 672 if (SI.getParent() == CondPHI->getParent() && 673 I->getParent() != CondPHI->getParent()) 674 return true; 675 676 // Otherwise we have a 'hard' case and we can't tell without doing more 677 // detailed dominator based analysis, punt. 678 return false; 679 } 680 681 /// FoldSPFofSPF - We have an SPF (e.g. a min or max) of an SPF of the form: 682 /// SPF2(SPF1(A, B), C) 683 Instruction *InstCombiner::FoldSPFofSPF(Instruction *Inner, 684 SelectPatternFlavor SPF1, 685 Value *A, Value *B, 686 Instruction &Outer, 687 SelectPatternFlavor SPF2, Value *C) { 688 if (C == A || C == B) { 689 // MAX(MAX(A, B), B) -> MAX(A, B) 690 // MIN(MIN(a, b), a) -> MIN(a, b) 691 if (SPF1 == SPF2) 692 return ReplaceInstUsesWith(Outer, Inner); 693 694 // MAX(MIN(a, b), a) -> a 695 // MIN(MAX(a, b), a) -> a 696 if ((SPF1 == SPF_SMIN && SPF2 == SPF_SMAX) || 697 (SPF1 == SPF_SMAX && SPF2 == SPF_SMIN) || 698 (SPF1 == SPF_UMIN && SPF2 == SPF_UMAX) || 699 (SPF1 == SPF_UMAX && SPF2 == SPF_UMIN)) 700 return ReplaceInstUsesWith(Outer, C); 701 } 702 703 if (SPF1 == SPF2) { 704 if (ConstantInt *CB = dyn_cast<ConstantInt>(B)) { 705 if (ConstantInt *CC = dyn_cast<ConstantInt>(C)) { 706 APInt ACB = CB->getValue(); 707 APInt ACC = CC->getValue(); 708 709 // MIN(MIN(A, 23), 97) -> MIN(A, 23) 710 // MAX(MAX(A, 97), 23) -> MAX(A, 97) 711 if ((SPF1 == SPF_UMIN && ACB.ule(ACC)) || 712 (SPF1 == SPF_SMIN && ACB.sle(ACC)) || 713 (SPF1 == SPF_UMAX && ACB.uge(ACC)) || 714 (SPF1 == SPF_SMAX && ACB.sge(ACC))) 715 return ReplaceInstUsesWith(Outer, Inner); 716 717 // MIN(MIN(A, 97), 23) -> MIN(A, 23) 718 // MAX(MAX(A, 23), 97) -> MAX(A, 97) 719 if ((SPF1 == SPF_UMIN && ACB.ugt(ACC)) || 720 (SPF1 == SPF_SMIN && ACB.sgt(ACC)) || 721 (SPF1 == SPF_UMAX && ACB.ult(ACC)) || 722 (SPF1 == SPF_SMAX && ACB.slt(ACC))) { 723 Outer.replaceUsesOfWith(Inner, A); 724 return &Outer; 725 } 726 } 727 } 728 } 729 730 // ABS(ABS(X)) -> ABS(X) 731 // NABS(NABS(X)) -> NABS(X) 732 if (SPF1 == SPF2 && (SPF1 == SPF_ABS || SPF1 == SPF_NABS)) { 733 return ReplaceInstUsesWith(Outer, Inner); 734 } 735 736 // ABS(NABS(X)) -> ABS(X) 737 // NABS(ABS(X)) -> NABS(X) 738 if ((SPF1 == SPF_ABS && SPF2 == SPF_NABS) || 739 (SPF1 == SPF_NABS && SPF2 == SPF_ABS)) { 740 SelectInst *SI = cast<SelectInst>(Inner); 741 Value *NewSI = Builder->CreateSelect( 742 SI->getCondition(), SI->getFalseValue(), SI->getTrueValue()); 743 return ReplaceInstUsesWith(Outer, NewSI); 744 } 745 return nullptr; 746 } 747 748 /// foldSelectICmpAnd - If one of the constants is zero (we know they can't 749 /// both be) and we have an icmp instruction with zero, and we have an 'and' 750 /// with the non-constant value and a power of two we can turn the select 751 /// into a shift on the result of the 'and'. 752 static Value *foldSelectICmpAnd(const SelectInst &SI, ConstantInt *TrueVal, 753 ConstantInt *FalseVal, 754 InstCombiner::BuilderTy *Builder) { 755 const ICmpInst *IC = dyn_cast<ICmpInst>(SI.getCondition()); 756 if (!IC || !IC->isEquality() || !SI.getType()->isIntegerTy()) 757 return nullptr; 758 759 if (!match(IC->getOperand(1), m_Zero())) 760 return nullptr; 761 762 ConstantInt *AndRHS; 763 Value *LHS = IC->getOperand(0); 764 if (!match(LHS, m_And(m_Value(), m_ConstantInt(AndRHS)))) 765 return nullptr; 766 767 // If both select arms are non-zero see if we have a select of the form 768 // 'x ? 2^n + C : C'. Then we can offset both arms by C, use the logic 769 // for 'x ? 2^n : 0' and fix the thing up at the end. 770 ConstantInt *Offset = nullptr; 771 if (!TrueVal->isZero() && !FalseVal->isZero()) { 772 if ((TrueVal->getValue() - FalseVal->getValue()).isPowerOf2()) 773 Offset = FalseVal; 774 else if ((FalseVal->getValue() - TrueVal->getValue()).isPowerOf2()) 775 Offset = TrueVal; 776 else 777 return nullptr; 778 779 // Adjust TrueVal and FalseVal to the offset. 780 TrueVal = ConstantInt::get(Builder->getContext(), 781 TrueVal->getValue() - Offset->getValue()); 782 FalseVal = ConstantInt::get(Builder->getContext(), 783 FalseVal->getValue() - Offset->getValue()); 784 } 785 786 // Make sure the mask in the 'and' and one of the select arms is a power of 2. 787 if (!AndRHS->getValue().isPowerOf2() || 788 (!TrueVal->getValue().isPowerOf2() && 789 !FalseVal->getValue().isPowerOf2())) 790 return nullptr; 791 792 // Determine which shift is needed to transform result of the 'and' into the 793 // desired result. 794 ConstantInt *ValC = !TrueVal->isZero() ? TrueVal : FalseVal; 795 unsigned ValZeros = ValC->getValue().logBase2(); 796 unsigned AndZeros = AndRHS->getValue().logBase2(); 797 798 // If types don't match we can still convert the select by introducing a zext 799 // or a trunc of the 'and'. The trunc case requires that all of the truncated 800 // bits are zero, we can figure that out by looking at the 'and' mask. 801 if (AndZeros >= ValC->getBitWidth()) 802 return nullptr; 803 804 Value *V = Builder->CreateZExtOrTrunc(LHS, SI.getType()); 805 if (ValZeros > AndZeros) 806 V = Builder->CreateShl(V, ValZeros - AndZeros); 807 else if (ValZeros < AndZeros) 808 V = Builder->CreateLShr(V, AndZeros - ValZeros); 809 810 // Okay, now we know that everything is set up, we just don't know whether we 811 // have a icmp_ne or icmp_eq and whether the true or false val is the zero. 812 bool ShouldNotVal = !TrueVal->isZero(); 813 ShouldNotVal ^= IC->getPredicate() == ICmpInst::ICMP_NE; 814 if (ShouldNotVal) 815 V = Builder->CreateXor(V, ValC); 816 817 // Apply an offset if needed. 818 if (Offset) 819 V = Builder->CreateAdd(V, Offset); 820 return V; 821 } 822 823 Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { 824 Value *CondVal = SI.getCondition(); 825 Value *TrueVal = SI.getTrueValue(); 826 Value *FalseVal = SI.getFalseValue(); 827 828 if (Value *V = SimplifySelectInst(CondVal, TrueVal, FalseVal, DL)) 829 return ReplaceInstUsesWith(SI, V); 830 831 if (SI.getType()->isIntegerTy(1)) { 832 if (ConstantInt *C = dyn_cast<ConstantInt>(TrueVal)) { 833 if (C->getZExtValue()) { 834 // Change: A = select B, true, C --> A = or B, C 835 return BinaryOperator::CreateOr(CondVal, FalseVal); 836 } 837 // Change: A = select B, false, C --> A = and !B, C 838 Value *NotCond = Builder->CreateNot(CondVal, "not."+CondVal->getName()); 839 return BinaryOperator::CreateAnd(NotCond, FalseVal); 840 } 841 if (ConstantInt *C = dyn_cast<ConstantInt>(FalseVal)) { 842 if (C->getZExtValue() == false) { 843 // Change: A = select B, C, false --> A = and B, C 844 return BinaryOperator::CreateAnd(CondVal, TrueVal); 845 } 846 // Change: A = select B, C, true --> A = or !B, C 847 Value *NotCond = Builder->CreateNot(CondVal, "not."+CondVal->getName()); 848 return BinaryOperator::CreateOr(NotCond, TrueVal); 849 } 850 851 // select a, b, a -> a&b 852 // select a, a, b -> a|b 853 if (CondVal == TrueVal) 854 return BinaryOperator::CreateOr(CondVal, FalseVal); 855 if (CondVal == FalseVal) 856 return BinaryOperator::CreateAnd(CondVal, TrueVal); 857 858 // select a, ~a, b -> (~a)&b 859 // select a, b, ~a -> (~a)|b 860 if (match(TrueVal, m_Not(m_Specific(CondVal)))) 861 return BinaryOperator::CreateAnd(TrueVal, FalseVal); 862 if (match(FalseVal, m_Not(m_Specific(CondVal)))) 863 return BinaryOperator::CreateOr(TrueVal, FalseVal); 864 } 865 866 // Selecting between two integer constants? 867 if (ConstantInt *TrueValC = dyn_cast<ConstantInt>(TrueVal)) 868 if (ConstantInt *FalseValC = dyn_cast<ConstantInt>(FalseVal)) { 869 // select C, 1, 0 -> zext C to int 870 if (FalseValC->isZero() && TrueValC->getValue() == 1) 871 return new ZExtInst(CondVal, SI.getType()); 872 873 // select C, -1, 0 -> sext C to int 874 if (FalseValC->isZero() && TrueValC->isAllOnesValue()) 875 return new SExtInst(CondVal, SI.getType()); 876 877 // select C, 0, 1 -> zext !C to int 878 if (TrueValC->isZero() && FalseValC->getValue() == 1) { 879 Value *NotCond = Builder->CreateNot(CondVal, "not."+CondVal->getName()); 880 return new ZExtInst(NotCond, SI.getType()); 881 } 882 883 // select C, 0, -1 -> sext !C to int 884 if (TrueValC->isZero() && FalseValC->isAllOnesValue()) { 885 Value *NotCond = Builder->CreateNot(CondVal, "not."+CondVal->getName()); 886 return new SExtInst(NotCond, SI.getType()); 887 } 888 889 if (Value *V = foldSelectICmpAnd(SI, TrueValC, FalseValC, Builder)) 890 return ReplaceInstUsesWith(SI, V); 891 } 892 893 // See if we are selecting two values based on a comparison of the two values. 894 if (FCmpInst *FCI = dyn_cast<FCmpInst>(CondVal)) { 895 if (FCI->getOperand(0) == TrueVal && FCI->getOperand(1) == FalseVal) { 896 // Transform (X == Y) ? X : Y -> Y 897 if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) { 898 // This is not safe in general for floating point: 899 // consider X== -0, Y== +0. 900 // It becomes safe if either operand is a nonzero constant. 901 ConstantFP *CFPt, *CFPf; 902 if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && 903 !CFPt->getValueAPF().isZero()) || 904 ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && 905 !CFPf->getValueAPF().isZero())) 906 return ReplaceInstUsesWith(SI, FalseVal); 907 } 908 // Transform (X une Y) ? X : Y -> X 909 if (FCI->getPredicate() == FCmpInst::FCMP_UNE) { 910 // This is not safe in general for floating point: 911 // consider X== -0, Y== +0. 912 // It becomes safe if either operand is a nonzero constant. 913 ConstantFP *CFPt, *CFPf; 914 if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && 915 !CFPt->getValueAPF().isZero()) || 916 ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && 917 !CFPf->getValueAPF().isZero())) 918 return ReplaceInstUsesWith(SI, TrueVal); 919 } 920 // NOTE: if we wanted to, this is where to detect MIN/MAX 921 922 } else if (FCI->getOperand(0) == FalseVal && FCI->getOperand(1) == TrueVal){ 923 // Transform (X == Y) ? Y : X -> X 924 if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) { 925 // This is not safe in general for floating point: 926 // consider X== -0, Y== +0. 927 // It becomes safe if either operand is a nonzero constant. 928 ConstantFP *CFPt, *CFPf; 929 if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && 930 !CFPt->getValueAPF().isZero()) || 931 ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && 932 !CFPf->getValueAPF().isZero())) 933 return ReplaceInstUsesWith(SI, FalseVal); 934 } 935 // Transform (X une Y) ? Y : X -> Y 936 if (FCI->getPredicate() == FCmpInst::FCMP_UNE) { 937 // This is not safe in general for floating point: 938 // consider X== -0, Y== +0. 939 // It becomes safe if either operand is a nonzero constant. 940 ConstantFP *CFPt, *CFPf; 941 if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && 942 !CFPt->getValueAPF().isZero()) || 943 ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && 944 !CFPf->getValueAPF().isZero())) 945 return ReplaceInstUsesWith(SI, TrueVal); 946 } 947 // NOTE: if we wanted to, this is where to detect MIN/MAX 948 } 949 // NOTE: if we wanted to, this is where to detect ABS 950 } 951 952 // See if we are selecting two values based on a comparison of the two values. 953 if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal)) 954 if (Instruction *Result = visitSelectInstWithICmp(SI, ICI)) 955 return Result; 956 957 if (Instruction *TI = dyn_cast<Instruction>(TrueVal)) 958 if (Instruction *FI = dyn_cast<Instruction>(FalseVal)) 959 if (TI->hasOneUse() && FI->hasOneUse()) { 960 Instruction *AddOp = nullptr, *SubOp = nullptr; 961 962 // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z)) 963 if (TI->getOpcode() == FI->getOpcode()) 964 if (Instruction *IV = FoldSelectOpOp(SI, TI, FI)) 965 return IV; 966 967 // Turn select C, (X+Y), (X-Y) --> (X+(select C, Y, (-Y))). This is 968 // even legal for FP. 969 if ((TI->getOpcode() == Instruction::Sub && 970 FI->getOpcode() == Instruction::Add) || 971 (TI->getOpcode() == Instruction::FSub && 972 FI->getOpcode() == Instruction::FAdd)) { 973 AddOp = FI; SubOp = TI; 974 } else if ((FI->getOpcode() == Instruction::Sub && 975 TI->getOpcode() == Instruction::Add) || 976 (FI->getOpcode() == Instruction::FSub && 977 TI->getOpcode() == Instruction::FAdd)) { 978 AddOp = TI; SubOp = FI; 979 } 980 981 if (AddOp) { 982 Value *OtherAddOp = nullptr; 983 if (SubOp->getOperand(0) == AddOp->getOperand(0)) { 984 OtherAddOp = AddOp->getOperand(1); 985 } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) { 986 OtherAddOp = AddOp->getOperand(0); 987 } 988 989 if (OtherAddOp) { 990 // So at this point we know we have (Y -> OtherAddOp): 991 // select C, (add X, Y), (sub X, Z) 992 Value *NegVal; // Compute -Z 993 if (SI.getType()->isFPOrFPVectorTy()) { 994 NegVal = Builder->CreateFNeg(SubOp->getOperand(1)); 995 if (Instruction *NegInst = dyn_cast<Instruction>(NegVal)) { 996 FastMathFlags Flags = AddOp->getFastMathFlags(); 997 Flags &= SubOp->getFastMathFlags(); 998 NegInst->setFastMathFlags(Flags); 999 } 1000 } else { 1001 NegVal = Builder->CreateNeg(SubOp->getOperand(1)); 1002 } 1003 1004 Value *NewTrueOp = OtherAddOp; 1005 Value *NewFalseOp = NegVal; 1006 if (AddOp != TI) 1007 std::swap(NewTrueOp, NewFalseOp); 1008 Value *NewSel = 1009 Builder->CreateSelect(CondVal, NewTrueOp, 1010 NewFalseOp, SI.getName() + ".p"); 1011 1012 if (SI.getType()->isFPOrFPVectorTy()) { 1013 Instruction *RI = 1014 BinaryOperator::CreateFAdd(SubOp->getOperand(0), NewSel); 1015 1016 FastMathFlags Flags = AddOp->getFastMathFlags(); 1017 Flags &= SubOp->getFastMathFlags(); 1018 RI->setFastMathFlags(Flags); 1019 return RI; 1020 } else 1021 return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel); 1022 } 1023 } 1024 } 1025 1026 // See if we can fold the select into one of our operands. 1027 if (SI.getType()->isIntegerTy()) { 1028 if (Instruction *FoldI = FoldSelectIntoOp(SI, TrueVal, FalseVal)) 1029 return FoldI; 1030 1031 // MAX(MAX(a, b), a) -> MAX(a, b) 1032 // MIN(MIN(a, b), a) -> MIN(a, b) 1033 // MAX(MIN(a, b), a) -> a 1034 // MIN(MAX(a, b), a) -> a 1035 Value *LHS, *RHS, *LHS2, *RHS2; 1036 if (SelectPatternFlavor SPF = MatchSelectPattern(&SI, LHS, RHS)) { 1037 if (SelectPatternFlavor SPF2 = MatchSelectPattern(LHS, LHS2, RHS2)) 1038 if (Instruction *R = FoldSPFofSPF(cast<Instruction>(LHS),SPF2,LHS2,RHS2, 1039 SI, SPF, RHS)) 1040 return R; 1041 if (SelectPatternFlavor SPF2 = MatchSelectPattern(RHS, LHS2, RHS2)) 1042 if (Instruction *R = FoldSPFofSPF(cast<Instruction>(RHS),SPF2,LHS2,RHS2, 1043 SI, SPF, LHS)) 1044 return R; 1045 } 1046 1047 // TODO. 1048 // ABS(-X) -> ABS(X) 1049 } 1050 1051 // See if we can fold the select into a phi node if the condition is a select. 1052 if (isa<PHINode>(SI.getCondition())) 1053 // The true/false values have to be live in the PHI predecessor's blocks. 1054 if (CanSelectOperandBeMappingIntoPredBlock(TrueVal, SI) && 1055 CanSelectOperandBeMappingIntoPredBlock(FalseVal, SI)) 1056 if (Instruction *NV = FoldOpIntoPhi(SI)) 1057 return NV; 1058 1059 if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) { 1060 if (TrueSI->getCondition() == CondVal) { 1061 if (SI.getTrueValue() == TrueSI->getTrueValue()) 1062 return nullptr; 1063 SI.setOperand(1, TrueSI->getTrueValue()); 1064 return &SI; 1065 } 1066 } 1067 if (SelectInst *FalseSI = dyn_cast<SelectInst>(FalseVal)) { 1068 if (FalseSI->getCondition() == CondVal) { 1069 if (SI.getFalseValue() == FalseSI->getFalseValue()) 1070 return nullptr; 1071 SI.setOperand(2, FalseSI->getFalseValue()); 1072 return &SI; 1073 } 1074 } 1075 1076 if (BinaryOperator::isNot(CondVal)) { 1077 SI.setOperand(0, BinaryOperator::getNotArgument(CondVal)); 1078 SI.setOperand(1, FalseVal); 1079 SI.setOperand(2, TrueVal); 1080 return &SI; 1081 } 1082 1083 if (VectorType* VecTy = dyn_cast<VectorType>(SI.getType())) { 1084 unsigned VWidth = VecTy->getNumElements(); 1085 APInt UndefElts(VWidth, 0); 1086 APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); 1087 if (Value *V = SimplifyDemandedVectorElts(&SI, AllOnesEltMask, UndefElts)) { 1088 if (V != &SI) 1089 return ReplaceInstUsesWith(SI, V); 1090 return &SI; 1091 } 1092 1093 if (isa<ConstantAggregateZero>(CondVal)) { 1094 return ReplaceInstUsesWith(SI, FalseVal); 1095 } 1096 } 1097 1098 return nullptr; 1099 } 1100
