lib/Transforms/InstCombine/InstCombineSelect.cpp

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