InstCombineSelect.cpp revision c6334b97e1de7c7c67c7279bdc44eb99ea65c78c
1//===- InstCombineLoadStoreAlloca.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 visit functions for load, store and alloca. 11// 12//===----------------------------------------------------------------------===// 13 14#include "InstCombine.h" 15//#include "llvm/IntrinsicInst.h" 16//#include "llvm/Target/TargetData.h" 17//#include "llvm/Transforms/Utils/BasicBlockUtils.h" 18//#include "llvm/Transforms/Utils/Local.h" 19//#include "llvm/ADT/Statistic.h" 20#include "llvm/Support/PatternMatch.h" 21using namespace llvm; 22using namespace PatternMatch; 23 24/// MatchSelectPattern - Pattern match integer [SU]MIN, [SU]MAX, and ABS idioms, 25/// returning the kind and providing the out parameter results if we 26/// successfully match. 27static SelectPatternFlavor 28MatchSelectPattern(Value *V, Value *&LHS, Value *&RHS) { 29 SelectInst *SI = dyn_cast<SelectInst>(V); 30 if (SI == 0) return SPF_UNKNOWN; 31 32 ICmpInst *ICI = dyn_cast<ICmpInst>(SI->getCondition()); 33 if (ICI == 0) return SPF_UNKNOWN; 34 35 LHS = ICI->getOperand(0); 36 RHS = ICI->getOperand(1); 37 38 // (icmp X, Y) ? X : Y 39 if (SI->getTrueValue() == ICI->getOperand(0) && 40 SI->getFalseValue() == ICI->getOperand(1)) { 41 switch (ICI->getPredicate()) { 42 default: return SPF_UNKNOWN; // Equality. 43 case ICmpInst::ICMP_UGT: 44 case ICmpInst::ICMP_UGE: return SPF_UMAX; 45 case ICmpInst::ICMP_SGT: 46 case ICmpInst::ICMP_SGE: return SPF_SMAX; 47 case ICmpInst::ICMP_ULT: 48 case ICmpInst::ICMP_ULE: return SPF_UMIN; 49 case ICmpInst::ICMP_SLT: 50 case ICmpInst::ICMP_SLE: return SPF_SMIN; 51 } 52 } 53 54 // (icmp X, Y) ? Y : X 55 if (SI->getTrueValue() == ICI->getOperand(1) && 56 SI->getFalseValue() == ICI->getOperand(0)) { 57 switch (ICI->getPredicate()) { 58 default: return SPF_UNKNOWN; // Equality. 59 case ICmpInst::ICMP_UGT: 60 case ICmpInst::ICMP_UGE: return SPF_UMIN; 61 case ICmpInst::ICMP_SGT: 62 case ICmpInst::ICMP_SGE: return SPF_SMIN; 63 case ICmpInst::ICMP_ULT: 64 case ICmpInst::ICMP_ULE: return SPF_UMAX; 65 case ICmpInst::ICMP_SLT: 66 case ICmpInst::ICMP_SLE: return SPF_SMAX; 67 } 68 } 69 70 // TODO: (X > 4) ? X : 5 --> (X >= 5) ? X : 5 --> MAX(X, 5) 71 72 return SPF_UNKNOWN; 73} 74 75 76/// GetSelectFoldableOperands - We want to turn code that looks like this: 77/// %C = or %A, %B 78/// %D = select %cond, %C, %A 79/// into: 80/// %C = select %cond, %B, 0 81/// %D = or %A, %C 82/// 83/// Assuming that the specified instruction is an operand to the select, return 84/// a bitmask indicating which operands of this instruction are foldable if they 85/// equal the other incoming value of the select. 86/// 87static unsigned GetSelectFoldableOperands(Instruction *I) { 88 switch (I->getOpcode()) { 89 case Instruction::Add: 90 case Instruction::Mul: 91 case Instruction::And: 92 case Instruction::Or: 93 case Instruction::Xor: 94 return 3; // Can fold through either operand. 95 case Instruction::Sub: // Can only fold on the amount subtracted. 96 case Instruction::Shl: // Can only fold on the shift amount. 97 case Instruction::LShr: 98 case Instruction::AShr: 99 return 1; 100 default: 101 return 0; // Cannot fold 102 } 103} 104 105/// GetSelectFoldableConstant - For the same transformation as the previous 106/// function, return the identity constant that goes into the select. 107static Constant *GetSelectFoldableConstant(Instruction *I) { 108 switch (I->getOpcode()) { 109 default: llvm_unreachable("This cannot happen!"); 110 case Instruction::Add: 111 case Instruction::Sub: 112 case Instruction::Or: 113 case Instruction::Xor: 114 case Instruction::Shl: 115 case Instruction::LShr: 116 case Instruction::AShr: 117 return Constant::getNullValue(I->getType()); 118 case Instruction::And: 119 return Constant::getAllOnesValue(I->getType()); 120 case Instruction::Mul: 121 return ConstantInt::get(I->getType(), 1); 122 } 123} 124 125/// FoldSelectOpOp - Here we have (select c, TI, FI), and we know that TI and FI 126/// have the same opcode and only one use each. Try to simplify this. 127Instruction *InstCombiner::FoldSelectOpOp(SelectInst &SI, Instruction *TI, 128 Instruction *FI) { 129 if (TI->getNumOperands() == 1) { 130 // If this is a non-volatile load or a cast from the same type, 131 // merge. 132 if (TI->isCast()) { 133 if (TI->getOperand(0)->getType() != FI->getOperand(0)->getType()) 134 return 0; 135 } else { 136 return 0; // unknown unary op. 137 } 138 139 // Fold this by inserting a select from the input values. 140 SelectInst *NewSI = SelectInst::Create(SI.getCondition(), TI->getOperand(0), 141 FI->getOperand(0), SI.getName()+".v"); 142 InsertNewInstBefore(NewSI, SI); 143 return CastInst::Create(Instruction::CastOps(TI->getOpcode()), NewSI, 144 TI->getType()); 145 } 146 147 // Only handle binary operators here. 148 if (!isa<BinaryOperator>(TI)) 149 return 0; 150 151 // Figure out if the operations have any operands in common. 152 Value *MatchOp, *OtherOpT, *OtherOpF; 153 bool MatchIsOpZero; 154 if (TI->getOperand(0) == FI->getOperand(0)) { 155 MatchOp = TI->getOperand(0); 156 OtherOpT = TI->getOperand(1); 157 OtherOpF = FI->getOperand(1); 158 MatchIsOpZero = true; 159 } else if (TI->getOperand(1) == FI->getOperand(1)) { 160 MatchOp = TI->getOperand(1); 161 OtherOpT = TI->getOperand(0); 162 OtherOpF = FI->getOperand(0); 163 MatchIsOpZero = false; 164 } else if (!TI->isCommutative()) { 165 return 0; 166 } else if (TI->getOperand(0) == FI->getOperand(1)) { 167 MatchOp = TI->getOperand(0); 168 OtherOpT = TI->getOperand(1); 169 OtherOpF = FI->getOperand(0); 170 MatchIsOpZero = true; 171 } else if (TI->getOperand(1) == FI->getOperand(0)) { 172 MatchOp = TI->getOperand(1); 173 OtherOpT = TI->getOperand(0); 174 OtherOpF = FI->getOperand(1); 175 MatchIsOpZero = true; 176 } else { 177 return 0; 178 } 179 180 // If we reach here, they do have operations in common. 181 SelectInst *NewSI = SelectInst::Create(SI.getCondition(), OtherOpT, 182 OtherOpF, SI.getName()+".v"); 183 InsertNewInstBefore(NewSI, SI); 184 185 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TI)) { 186 if (MatchIsOpZero) 187 return BinaryOperator::Create(BO->getOpcode(), MatchOp, NewSI); 188 else 189 return BinaryOperator::Create(BO->getOpcode(), NewSI, MatchOp); 190 } 191 llvm_unreachable("Shouldn't get here"); 192 return 0; 193} 194 195static bool isSelect01(Constant *C1, Constant *C2) { 196 ConstantInt *C1I = dyn_cast<ConstantInt>(C1); 197 if (!C1I) 198 return false; 199 ConstantInt *C2I = dyn_cast<ConstantInt>(C2); 200 if (!C2I) 201 return false; 202 return (C1I->isZero() || C1I->isOne()) && (C2I->isZero() || C2I->isOne()); 203} 204 205/// FoldSelectIntoOp - Try fold the select into one of the operands to 206/// facilitate further optimization. 207Instruction *InstCombiner::FoldSelectIntoOp(SelectInst &SI, Value *TrueVal, 208 Value *FalseVal) { 209 // See the comment above GetSelectFoldableOperands for a description of the 210 // transformation we are doing here. 211 if (Instruction *TVI = dyn_cast<Instruction>(TrueVal)) { 212 if (TVI->hasOneUse() && TVI->getNumOperands() == 2 && 213 !isa<Constant>(FalseVal)) { 214 if (unsigned SFO = GetSelectFoldableOperands(TVI)) { 215 unsigned OpToFold = 0; 216 if ((SFO & 1) && FalseVal == TVI->getOperand(0)) { 217 OpToFold = 1; 218 } else if ((SFO & 2) && FalseVal == TVI->getOperand(1)) { 219 OpToFold = 2; 220 } 221 222 if (OpToFold) { 223 Constant *C = GetSelectFoldableConstant(TVI); 224 Value *OOp = TVI->getOperand(2-OpToFold); 225 // Avoid creating select between 2 constants unless it's selecting 226 // between 0 and 1. 227 if (!isa<Constant>(OOp) || isSelect01(C, cast<Constant>(OOp))) { 228 Instruction *NewSel = SelectInst::Create(SI.getCondition(), OOp, C); 229 InsertNewInstBefore(NewSel, SI); 230 NewSel->takeName(TVI); 231 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TVI)) 232 return BinaryOperator::Create(BO->getOpcode(), FalseVal, NewSel); 233 llvm_unreachable("Unknown instruction!!"); 234 } 235 } 236 } 237 } 238 } 239 240 if (Instruction *FVI = dyn_cast<Instruction>(FalseVal)) { 241 if (FVI->hasOneUse() && FVI->getNumOperands() == 2 && 242 !isa<Constant>(TrueVal)) { 243 if (unsigned SFO = GetSelectFoldableOperands(FVI)) { 244 unsigned OpToFold = 0; 245 if ((SFO & 1) && TrueVal == FVI->getOperand(0)) { 246 OpToFold = 1; 247 } else if ((SFO & 2) && TrueVal == FVI->getOperand(1)) { 248 OpToFold = 2; 249 } 250 251 if (OpToFold) { 252 Constant *C = GetSelectFoldableConstant(FVI); 253 Value *OOp = FVI->getOperand(2-OpToFold); 254 // Avoid creating select between 2 constants unless it's selecting 255 // between 0 and 1. 256 if (!isa<Constant>(OOp) || isSelect01(C, cast<Constant>(OOp))) { 257 Instruction *NewSel = SelectInst::Create(SI.getCondition(), C, OOp); 258 InsertNewInstBefore(NewSel, SI); 259 NewSel->takeName(FVI); 260 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FVI)) 261 return BinaryOperator::Create(BO->getOpcode(), TrueVal, NewSel); 262 llvm_unreachable("Unknown instruction!!"); 263 } 264 } 265 } 266 } 267 } 268 269 return 0; 270} 271 272/// visitSelectInstWithICmp - Visit a SelectInst that has an 273/// ICmpInst as its first operand. 274/// 275Instruction *InstCombiner::visitSelectInstWithICmp(SelectInst &SI, 276 ICmpInst *ICI) { 277 bool Changed = false; 278 ICmpInst::Predicate Pred = ICI->getPredicate(); 279 Value *CmpLHS = ICI->getOperand(0); 280 Value *CmpRHS = ICI->getOperand(1); 281 Value *TrueVal = SI.getTrueValue(); 282 Value *FalseVal = SI.getFalseValue(); 283 284 // Check cases where the comparison is with a constant that 285 // can be adjusted to fit the min/max idiom. We may edit ICI in 286 // place here, so make sure the select is the only user. 287 if (ICI->hasOneUse()) 288 if (ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS)) { 289 switch (Pred) { 290 default: break; 291 case ICmpInst::ICMP_ULT: 292 case ICmpInst::ICMP_SLT: { 293 // X < MIN ? T : F --> F 294 if (CI->isMinValue(Pred == ICmpInst::ICMP_SLT)) 295 return ReplaceInstUsesWith(SI, FalseVal); 296 // X < C ? X : C-1 --> X > C-1 ? C-1 : X 297 Constant *AdjustedRHS = 298 ConstantInt::get(CI->getContext(), CI->getValue()-1); 299 if ((CmpLHS == TrueVal && AdjustedRHS == FalseVal) || 300 (CmpLHS == FalseVal && AdjustedRHS == TrueVal)) { 301 Pred = ICmpInst::getSwappedPredicate(Pred); 302 CmpRHS = AdjustedRHS; 303 std::swap(FalseVal, TrueVal); 304 ICI->setPredicate(Pred); 305 ICI->setOperand(1, CmpRHS); 306 SI.setOperand(1, TrueVal); 307 SI.setOperand(2, FalseVal); 308 Changed = true; 309 } 310 break; 311 } 312 case ICmpInst::ICMP_UGT: 313 case ICmpInst::ICMP_SGT: { 314 // X > MAX ? T : F --> F 315 if (CI->isMaxValue(Pred == ICmpInst::ICMP_SGT)) 316 return ReplaceInstUsesWith(SI, FalseVal); 317 // X > C ? X : C+1 --> X < C+1 ? C+1 : X 318 Constant *AdjustedRHS = 319 ConstantInt::get(CI->getContext(), CI->getValue()+1); 320 if ((CmpLHS == TrueVal && AdjustedRHS == FalseVal) || 321 (CmpLHS == FalseVal && AdjustedRHS == TrueVal)) { 322 Pred = ICmpInst::getSwappedPredicate(Pred); 323 CmpRHS = AdjustedRHS; 324 std::swap(FalseVal, TrueVal); 325 ICI->setPredicate(Pred); 326 ICI->setOperand(1, CmpRHS); 327 SI.setOperand(1, TrueVal); 328 SI.setOperand(2, FalseVal); 329 Changed = true; 330 } 331 break; 332 } 333 } 334 335 // (x <s 0) ? -1 : 0 -> ashr x, 31 -> all ones if signed 336 // (x >s -1) ? -1 : 0 -> ashr x, 31 -> all ones if not signed 337 CmpInst::Predicate Pred = CmpInst::BAD_ICMP_PREDICATE; 338 if (match(TrueVal, m_ConstantInt<-1>()) && 339 match(FalseVal, m_ConstantInt<0>())) 340 Pred = ICI->getPredicate(); 341 else if (match(TrueVal, m_ConstantInt<0>()) && 342 match(FalseVal, m_ConstantInt<-1>())) 343 Pred = CmpInst::getInversePredicate(ICI->getPredicate()); 344 345 if (Pred != CmpInst::BAD_ICMP_PREDICATE) { 346 // If we are just checking for a icmp eq of a single bit and zext'ing it 347 // to an integer, then shift the bit to the appropriate place and then 348 // cast to integer to avoid the comparison. 349 const APInt &Op1CV = CI->getValue(); 350 351 // sext (x <s 0) to i32 --> x>>s31 true if signbit set. 352 // sext (x >s -1) to i32 --> (x>>s31)^-1 true if signbit clear. 353 if ((Pred == ICmpInst::ICMP_SLT && Op1CV == 0) || 354 (Pred == ICmpInst::ICMP_SGT && Op1CV.isAllOnesValue())) { 355 Value *In = ICI->getOperand(0); 356 Value *Sh = ConstantInt::get(In->getType(), 357 In->getType()->getScalarSizeInBits()-1); 358 In = InsertNewInstBefore(BinaryOperator::CreateAShr(In, Sh, 359 In->getName()+".lobit"), 360 *ICI); 361 if (In->getType() != SI.getType()) 362 In = CastInst::CreateIntegerCast(In, SI.getType(), 363 true/*SExt*/, "tmp", ICI); 364 365 if (Pred == ICmpInst::ICMP_SGT) 366 In = InsertNewInstBefore(BinaryOperator::CreateNot(In, 367 In->getName()+".not"), *ICI); 368 369 return ReplaceInstUsesWith(SI, In); 370 } 371 } 372 } 373 374 if (CmpLHS == TrueVal && CmpRHS == FalseVal) { 375 // Transform (X == Y) ? X : Y -> Y 376 if (Pred == ICmpInst::ICMP_EQ) 377 return ReplaceInstUsesWith(SI, FalseVal); 378 // Transform (X != Y) ? X : Y -> X 379 if (Pred == ICmpInst::ICMP_NE) 380 return ReplaceInstUsesWith(SI, TrueVal); 381 /// NOTE: if we wanted to, this is where to detect integer MIN/MAX 382 383 } else if (CmpLHS == FalseVal && CmpRHS == TrueVal) { 384 // Transform (X == Y) ? Y : X -> X 385 if (Pred == ICmpInst::ICMP_EQ) 386 return ReplaceInstUsesWith(SI, FalseVal); 387 // Transform (X != Y) ? Y : X -> Y 388 if (Pred == ICmpInst::ICMP_NE) 389 return ReplaceInstUsesWith(SI, TrueVal); 390 /// NOTE: if we wanted to, this is where to detect integer MIN/MAX 391 } 392 return Changed ? &SI : 0; 393} 394 395 396/// CanSelectOperandBeMappingIntoPredBlock - SI is a select whose condition is a 397/// PHI node (but the two may be in different blocks). See if the true/false 398/// values (V) are live in all of the predecessor blocks of the PHI. For 399/// example, cases like this cannot be mapped: 400/// 401/// X = phi [ C1, BB1], [C2, BB2] 402/// Y = add 403/// Z = select X, Y, 0 404/// 405/// because Y is not live in BB1/BB2. 406/// 407static bool CanSelectOperandBeMappingIntoPredBlock(const Value *V, 408 const SelectInst &SI) { 409 // If the value is a non-instruction value like a constant or argument, it 410 // can always be mapped. 411 const Instruction *I = dyn_cast<Instruction>(V); 412 if (I == 0) return true; 413 414 // If V is a PHI node defined in the same block as the condition PHI, we can 415 // map the arguments. 416 const PHINode *CondPHI = cast<PHINode>(SI.getCondition()); 417 418 if (const PHINode *VP = dyn_cast<PHINode>(I)) 419 if (VP->getParent() == CondPHI->getParent()) 420 return true; 421 422 // Otherwise, if the PHI and select are defined in the same block and if V is 423 // defined in a different block, then we can transform it. 424 if (SI.getParent() == CondPHI->getParent() && 425 I->getParent() != CondPHI->getParent()) 426 return true; 427 428 // Otherwise we have a 'hard' case and we can't tell without doing more 429 // detailed dominator based analysis, punt. 430 return false; 431} 432 433/// FoldSPFofSPF - We have an SPF (e.g. a min or max) of an SPF of the form: 434/// SPF2(SPF1(A, B), C) 435Instruction *InstCombiner::FoldSPFofSPF(Instruction *Inner, 436 SelectPatternFlavor SPF1, 437 Value *A, Value *B, 438 Instruction &Outer, 439 SelectPatternFlavor SPF2, Value *C) { 440 if (C == A || C == B) { 441 // MAX(MAX(A, B), B) -> MAX(A, B) 442 // MIN(MIN(a, b), a) -> MIN(a, b) 443 if (SPF1 == SPF2) 444 return ReplaceInstUsesWith(Outer, Inner); 445 446 // MAX(MIN(a, b), a) -> a 447 // MIN(MAX(a, b), a) -> a 448 if ((SPF1 == SPF_SMIN && SPF2 == SPF_SMAX) || 449 (SPF1 == SPF_SMAX && SPF2 == SPF_SMIN) || 450 (SPF1 == SPF_UMIN && SPF2 == SPF_UMAX) || 451 (SPF1 == SPF_UMAX && SPF2 == SPF_UMIN)) 452 return ReplaceInstUsesWith(Outer, C); 453 } 454 455 // TODO: MIN(MIN(A, 23), 97) 456 return 0; 457} 458 459 460 461 462Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { 463 Value *CondVal = SI.getCondition(); 464 Value *TrueVal = SI.getTrueValue(); 465 Value *FalseVal = SI.getFalseValue(); 466 467 // select true, X, Y -> X 468 // select false, X, Y -> Y 469 if (ConstantInt *C = dyn_cast<ConstantInt>(CondVal)) 470 return ReplaceInstUsesWith(SI, C->getZExtValue() ? TrueVal : FalseVal); 471 472 // select C, X, X -> X 473 if (TrueVal == FalseVal) 474 return ReplaceInstUsesWith(SI, TrueVal); 475 476 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 477 return ReplaceInstUsesWith(SI, FalseVal); 478 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 479 return ReplaceInstUsesWith(SI, TrueVal); 480 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 481 if (isa<Constant>(TrueVal)) 482 return ReplaceInstUsesWith(SI, TrueVal); 483 else 484 return ReplaceInstUsesWith(SI, FalseVal); 485 } 486 487 if (SI.getType() == Type::getInt1Ty(SI.getContext())) { 488 if (ConstantInt *C = dyn_cast<ConstantInt>(TrueVal)) { 489 if (C->getZExtValue()) { 490 // Change: A = select B, true, C --> A = or B, C 491 return BinaryOperator::CreateOr(CondVal, FalseVal); 492 } else { 493 // Change: A = select B, false, C --> A = and !B, C 494 Value *NotCond = 495 InsertNewInstBefore(BinaryOperator::CreateNot(CondVal, 496 "not."+CondVal->getName()), SI); 497 return BinaryOperator::CreateAnd(NotCond, FalseVal); 498 } 499 } else if (ConstantInt *C = dyn_cast<ConstantInt>(FalseVal)) { 500 if (C->getZExtValue() == false) { 501 // Change: A = select B, C, false --> A = and B, C 502 return BinaryOperator::CreateAnd(CondVal, TrueVal); 503 } else { 504 // Change: A = select B, C, true --> A = or !B, C 505 Value *NotCond = 506 InsertNewInstBefore(BinaryOperator::CreateNot(CondVal, 507 "not."+CondVal->getName()), SI); 508 return BinaryOperator::CreateOr(NotCond, TrueVal); 509 } 510 } 511 512 // select a, b, a -> a&b 513 // select a, a, b -> a|b 514 if (CondVal == TrueVal) 515 return BinaryOperator::CreateOr(CondVal, FalseVal); 516 else if (CondVal == FalseVal) 517 return BinaryOperator::CreateAnd(CondVal, TrueVal); 518 } 519 520 // Selecting between two integer constants? 521 if (ConstantInt *TrueValC = dyn_cast<ConstantInt>(TrueVal)) 522 if (ConstantInt *FalseValC = dyn_cast<ConstantInt>(FalseVal)) { 523 // select C, 1, 0 -> zext C to int 524 if (FalseValC->isZero() && TrueValC->getValue() == 1) { 525 return CastInst::Create(Instruction::ZExt, CondVal, SI.getType()); 526 } else if (TrueValC->isZero() && FalseValC->getValue() == 1) { 527 // select C, 0, 1 -> zext !C to int 528 Value *NotCond = 529 InsertNewInstBefore(BinaryOperator::CreateNot(CondVal, 530 "not."+CondVal->getName()), SI); 531 return CastInst::Create(Instruction::ZExt, NotCond, SI.getType()); 532 } 533 534 if (ICmpInst *IC = dyn_cast<ICmpInst>(SI.getCondition())) { 535 // If one of the constants is zero (we know they can't both be) and we 536 // have an icmp instruction with zero, and we have an 'and' with the 537 // non-constant value, eliminate this whole mess. This corresponds to 538 // cases like this: ((X & 27) ? 27 : 0) 539 if (TrueValC->isZero() || FalseValC->isZero()) 540 if (IC->isEquality() && isa<ConstantInt>(IC->getOperand(1)) && 541 cast<Constant>(IC->getOperand(1))->isNullValue()) 542 if (Instruction *ICA = dyn_cast<Instruction>(IC->getOperand(0))) 543 if (ICA->getOpcode() == Instruction::And && 544 isa<ConstantInt>(ICA->getOperand(1)) && 545 (ICA->getOperand(1) == TrueValC || 546 ICA->getOperand(1) == FalseValC) && 547 cast<ConstantInt>(ICA->getOperand(1))->getValue().isPowerOf2()) { 548 // Okay, now we know that everything is set up, we just don't 549 // know whether we have a icmp_ne or icmp_eq and whether the 550 // true or false val is the zero. 551 bool ShouldNotVal = !TrueValC->isZero(); 552 ShouldNotVal ^= IC->getPredicate() == ICmpInst::ICMP_NE; 553 Value *V = ICA; 554 if (ShouldNotVal) 555 V = InsertNewInstBefore(BinaryOperator::Create( 556 Instruction::Xor, V, ICA->getOperand(1)), SI); 557 return ReplaceInstUsesWith(SI, V); 558 } 559 } 560 } 561 562 // See if we are selecting two values based on a comparison of the two values. 563 if (FCmpInst *FCI = dyn_cast<FCmpInst>(CondVal)) { 564 if (FCI->getOperand(0) == TrueVal && FCI->getOperand(1) == FalseVal) { 565 // Transform (X == Y) ? X : Y -> Y 566 if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) { 567 // This is not safe in general for floating point: 568 // consider X== -0, Y== +0. 569 // It becomes safe if either operand is a nonzero constant. 570 ConstantFP *CFPt, *CFPf; 571 if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && 572 !CFPt->getValueAPF().isZero()) || 573 ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && 574 !CFPf->getValueAPF().isZero())) 575 return ReplaceInstUsesWith(SI, FalseVal); 576 } 577 // Transform (X != Y) ? X : Y -> X 578 if (FCI->getPredicate() == FCmpInst::FCMP_ONE) 579 return ReplaceInstUsesWith(SI, TrueVal); 580 // NOTE: if we wanted to, this is where to detect MIN/MAX 581 582 } else if (FCI->getOperand(0) == FalseVal && FCI->getOperand(1) == TrueVal){ 583 // Transform (X == Y) ? Y : X -> X 584 if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) { 585 // This is not safe in general for floating point: 586 // consider X== -0, Y== +0. 587 // It becomes safe if either operand is a nonzero constant. 588 ConstantFP *CFPt, *CFPf; 589 if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && 590 !CFPt->getValueAPF().isZero()) || 591 ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && 592 !CFPf->getValueAPF().isZero())) 593 return ReplaceInstUsesWith(SI, FalseVal); 594 } 595 // Transform (X != Y) ? Y : X -> Y 596 if (FCI->getPredicate() == FCmpInst::FCMP_ONE) 597 return ReplaceInstUsesWith(SI, TrueVal); 598 // NOTE: if we wanted to, this is where to detect MIN/MAX 599 } 600 // NOTE: if we wanted to, this is where to detect ABS 601 } 602 603 // See if we are selecting two values based on a comparison of the two values. 604 if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal)) 605 if (Instruction *Result = visitSelectInstWithICmp(SI, ICI)) 606 return Result; 607 608 if (Instruction *TI = dyn_cast<Instruction>(TrueVal)) 609 if (Instruction *FI = dyn_cast<Instruction>(FalseVal)) 610 if (TI->hasOneUse() && FI->hasOneUse()) { 611 Instruction *AddOp = 0, *SubOp = 0; 612 613 // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z)) 614 if (TI->getOpcode() == FI->getOpcode()) 615 if (Instruction *IV = FoldSelectOpOp(SI, TI, FI)) 616 return IV; 617 618 // Turn select C, (X+Y), (X-Y) --> (X+(select C, Y, (-Y))). This is 619 // even legal for FP. 620 if ((TI->getOpcode() == Instruction::Sub && 621 FI->getOpcode() == Instruction::Add) || 622 (TI->getOpcode() == Instruction::FSub && 623 FI->getOpcode() == Instruction::FAdd)) { 624 AddOp = FI; SubOp = TI; 625 } else if ((FI->getOpcode() == Instruction::Sub && 626 TI->getOpcode() == Instruction::Add) || 627 (FI->getOpcode() == Instruction::FSub && 628 TI->getOpcode() == Instruction::FAdd)) { 629 AddOp = TI; SubOp = FI; 630 } 631 632 if (AddOp) { 633 Value *OtherAddOp = 0; 634 if (SubOp->getOperand(0) == AddOp->getOperand(0)) { 635 OtherAddOp = AddOp->getOperand(1); 636 } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) { 637 OtherAddOp = AddOp->getOperand(0); 638 } 639 640 if (OtherAddOp) { 641 // So at this point we know we have (Y -> OtherAddOp): 642 // select C, (add X, Y), (sub X, Z) 643 Value *NegVal; // Compute -Z 644 if (Constant *C = dyn_cast<Constant>(SubOp->getOperand(1))) { 645 NegVal = ConstantExpr::getNeg(C); 646 } else { 647 NegVal = InsertNewInstBefore( 648 BinaryOperator::CreateNeg(SubOp->getOperand(1), 649 "tmp"), SI); 650 } 651 652 Value *NewTrueOp = OtherAddOp; 653 Value *NewFalseOp = NegVal; 654 if (AddOp != TI) 655 std::swap(NewTrueOp, NewFalseOp); 656 Instruction *NewSel = 657 SelectInst::Create(CondVal, NewTrueOp, 658 NewFalseOp, SI.getName() + ".p"); 659 660 NewSel = InsertNewInstBefore(NewSel, SI); 661 return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel); 662 } 663 } 664 } 665 666 // See if we can fold the select into one of our operands. 667 if (SI.getType()->isInteger()) { 668 if (Instruction *FoldI = FoldSelectIntoOp(SI, TrueVal, FalseVal)) 669 return FoldI; 670 671 // MAX(MAX(a, b), a) -> MAX(a, b) 672 // MIN(MIN(a, b), a) -> MIN(a, b) 673 // MAX(MIN(a, b), a) -> a 674 // MIN(MAX(a, b), a) -> a 675 Value *LHS, *RHS, *LHS2, *RHS2; 676 if (SelectPatternFlavor SPF = MatchSelectPattern(&SI, LHS, RHS)) { 677 if (SelectPatternFlavor SPF2 = MatchSelectPattern(LHS, LHS2, RHS2)) 678 if (Instruction *R = FoldSPFofSPF(cast<Instruction>(LHS),SPF2,LHS2,RHS2, 679 SI, SPF, RHS)) 680 return R; 681 if (SelectPatternFlavor SPF2 = MatchSelectPattern(RHS, LHS2, RHS2)) 682 if (Instruction *R = FoldSPFofSPF(cast<Instruction>(RHS),SPF2,LHS2,RHS2, 683 SI, SPF, LHS)) 684 return R; 685 } 686 687 // TODO. 688 // ABS(-X) -> ABS(X) 689 // ABS(ABS(X)) -> ABS(X) 690 } 691 692 // See if we can fold the select into a phi node if the condition is a select. 693 if (isa<PHINode>(SI.getCondition())) 694 // The true/false values have to be live in the PHI predecessor's blocks. 695 if (CanSelectOperandBeMappingIntoPredBlock(TrueVal, SI) && 696 CanSelectOperandBeMappingIntoPredBlock(FalseVal, SI)) 697 if (Instruction *NV = FoldOpIntoPhi(SI)) 698 return NV; 699 700 if (BinaryOperator::isNot(CondVal)) { 701 SI.setOperand(0, BinaryOperator::getNotArgument(CondVal)); 702 SI.setOperand(1, FalseVal); 703 SI.setOperand(2, TrueVal); 704 return &SI; 705 } 706 707 return 0; 708} 709