lib/Analysis/InstructionSimplify.cpp

   1 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
   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 routines for folding instructions into simpler forms
  11 // that do not require creating new instructions.  For example, this does
  12 // constant folding, and can handle identities like (X&0)->0.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Analysis/InstructionSimplify.h"
  17 #include "llvm/Analysis/ConstantFolding.h"
  18 #include "llvm/Support/ValueHandle.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Support/PatternMatch.h"
  21 using namespace llvm;
  22 using namespace llvm::PatternMatch;
  23
  24 #define MaxRecursionDepth 3
  25
  26 static Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *,
  27                             unsigned);
  28 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *,
  29                               unsigned);
  30
  31 /// ThreadBinOpOverSelect - In the case of a binary operation with a select
  32 /// instruction as an operand, try to simplify the binop by seeing whether
  33 /// evaluating it on both branches of the select results in the same value.
  34 /// Returns the common value if so, otherwise returns null.
  35 static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
  36                                     const TargetData *TD, unsigned MaxRecurse) {
  37   SelectInst *SI;
  38   if (isa<SelectInst>(LHS)) {
  39     SI = cast<SelectInst>(LHS);
  40   } else {
  41     assert(isa<SelectInst>(RHS) && "No select instruction operand!");
  42     SI = cast<SelectInst>(RHS);
  43   }
  44
  45   // Evaluate the BinOp on the true and false branches of the select.
  46   Value *TV;
  47   Value *FV;
  48   if (SI == LHS) {
  49     TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, MaxRecurse);
  50     FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, MaxRecurse);
  51   } else {
  52     TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, MaxRecurse);
  53     FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, MaxRecurse);
  54   }
  55
  56   // If they simplified to the same value, then return the common value.
  57   // If they both failed to simplify then return null.
  58   if (TV == FV)
  59     return TV;
  60
  61   // If one branch simplified to undef, return the other one.
  62   if (TV && isa<UndefValue>(TV))
  63     return FV;
  64   if (FV && isa<UndefValue>(FV))
  65     return TV;
  66
  67   // If applying the operation did not change the true and false select values,
  68   // then the result of the binop is the select itself.
  69   if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
  70     return SI;
  71
  72   // If one branch simplified and the other did not, and the simplified
  73   // value is equal to the unsimplified one, return the simplified value.
  74   // For example, select (cond, X, X & Z) & Z -> X & Z.
  75   if ((FV && !TV) || (TV && !FV)) {
  76     // Check that the simplified value has the form "X op Y" where "op" is the
  77     // same as the original operation.
  78     Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
  79     if (Simplified && Simplified->getOpcode() == Opcode) {
  80       // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
  81       // We already know that "op" is the same as for the simplified value.  See
  82       // if the operands match too.  If so, return the simplified value.
  83       Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
  84       Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
  85       Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
  86       if (Simplified->getOperand(0) == UnsimplifiedLHS &&
  87           Simplified->getOperand(1) == UnsimplifiedRHS)
  88         return Simplified;
  89       if (Simplified->isCommutative() &&
  90           Simplified->getOperand(1) == UnsimplifiedLHS &&
  91           Simplified->getOperand(0) == UnsimplifiedRHS)
  92         return Simplified;
  93     }
  94   }
  95
  96   return 0;
  97 }
  98
  99 /// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
 100 /// try to simplify the comparison by seeing whether both branches of the select
 101 /// result in the same value.  Returns the common value if so, otherwise returns
 102 /// null.
 103 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
 104                                   Value *RHS, const TargetData *TD,
 105                                   unsigned MaxRecurse) {
 106   // Make sure the select is on the LHS.
 107   if (!isa<SelectInst>(LHS)) {
 108     std::swap(LHS, RHS);
 109     Pred = CmpInst::getSwappedPredicate(Pred);
 110   }
 111   assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
 112   SelectInst *SI = cast<SelectInst>(LHS);
 113
 114   // Now that we have "cmp select(cond, TV, FV), RHS", analyse it.
 115   // Does "cmp TV, RHS" simplify?
 116   if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD,
 117                                     MaxRecurse))
 118     // It does!  Does "cmp FV, RHS" simplify?
 119     if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD,
 120                                       MaxRecurse))
 121       // It does!  If they simplified to the same value, then use it as the
 122       // result of the original comparison.
 123       if (TCmp == FCmp)
 124         return TCmp;
 125   return 0;
 126 }
 127
 128 /// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
 129 /// is a PHI instruction, try to simplify the binop by seeing whether evaluating
 130 /// it on the incoming phi values yields the same result for every value.  If so
 131 /// returns the common value, otherwise returns null.
 132 static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
 133                                  const TargetData *TD, unsigned MaxRecurse) {
 134   PHINode *PI;
 135   if (isa<PHINode>(LHS)) {
 136     PI = cast<PHINode>(LHS);
 137   } else {
 138     assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
 139     PI = cast<PHINode>(RHS);
 140   }
 141
 142   // Evaluate the BinOp on the incoming phi values.
 143   Value *CommonValue = 0;
 144   for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
 145     Value *Incoming = PI->getIncomingValue(i);
 146     // If the incoming value is the phi node itself, it can be safely skipped.
 147     if (Incoming == PI) continue;
 148     Value *V = PI == LHS ?
 149       SimplifyBinOp(Opcode, Incoming, RHS, TD, MaxRecurse) :
 150       SimplifyBinOp(Opcode, LHS, Incoming, TD, MaxRecurse);
 151     // If the operation failed to simplify, or simplified to a different value
 152     // to previously, then give up.
 153     if (!V || (CommonValue && V != CommonValue))
 154       return 0;
 155     CommonValue = V;
 156   }
 157
 158   return CommonValue;
 159 }
 160
 161 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
 162 /// try to simplify the comparison by seeing whether comparing with all of the
 163 /// incoming phi values yields the same result every time.  If so returns the
 164 /// common result, otherwise returns null.
 165 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
 166                                const TargetData *TD, unsigned MaxRecurse) {
 167   // Make sure the phi is on the LHS.
 168   if (!isa<PHINode>(LHS)) {
 169     std::swap(LHS, RHS);
 170     Pred = CmpInst::getSwappedPredicate(Pred);
 171   }
 172   assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
 173   PHINode *PI = cast<PHINode>(LHS);
 174
 175   // Evaluate the BinOp on the incoming phi values.
 176   Value *CommonValue = 0;
 177   for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
 178     Value *Incoming = PI->getIncomingValue(i);
 179     // If the incoming value is the phi node itself, it can be safely skipped.
 180     if (Incoming == PI) continue;
 181     Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, MaxRecurse);
 182     // If the operation failed to simplify, or simplified to a different value
 183     // to previously, then give up.
 184     if (!V || (CommonValue && V != CommonValue))
 185       return 0;
 186     CommonValue = V;
 187   }
 188
 189   return CommonValue;
 190 }
 191
 192 /// SimplifyAddInst - Given operands for an Add, see if we can
 193 /// fold the result.  If not, this returns null.
 194 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 195                              const TargetData *TD) {
 196   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 197     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 198       Constant *Ops[] = { CLHS, CRHS };
 199       return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
 200                                       Ops, 2, TD);
 201     }
 202
 203     // Canonicalize the constant to the RHS.
 204     std::swap(Op0, Op1);
 205   }
 206
 207   if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
 208     // X + undef -> undef
 209     if (isa<UndefValue>(Op1C))
 210       return Op1C;
 211
 212     // X + 0 --> X
 213     if (Op1C->isNullValue())
 214       return Op0;
 215   }
 216
 217   // FIXME: Could pull several more out of instcombine.
 218   return 0;
 219 }
 220
 221 /// SimplifyAndInst - Given operands for an And, see if we can
 222 /// fold the result.  If not, this returns null.
 223 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
 224                               unsigned MaxRecurse) {
 225   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 226     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 227       Constant *Ops[] = { CLHS, CRHS };
 228       return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
 229                                       Ops, 2, TD);
 230     }
 231
 232     // Canonicalize the constant to the RHS.
 233     std::swap(Op0, Op1);
 234   }
 235
 236   // X & undef -> 0
 237   if (isa<UndefValue>(Op1))
 238     return Constant::getNullValue(Op0->getType());
 239
 240   // X & X = X
 241   if (Op0 == Op1)
 242     return Op0;
 243
 244   // X & <0,0> = <0,0>
 245   if (isa<ConstantAggregateZero>(Op1))
 246     return Op1;
 247
 248   // X & <-1,-1> = X
 249   if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
 250     if (CP->isAllOnesValue())
 251       return Op0;
 252
 253   if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
 254     // X & 0 = 0
 255     if (Op1CI->isZero())
 256       return Op1CI;
 257     // X & -1 = X
 258     if (Op1CI->isAllOnesValue())
 259       return Op0;
 260   }
 261
 262   // A & ~A  =  ~A & A  =  0
 263   Value *A, *B;
 264   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
 265       (match(Op1, m_Not(m_Value(A))) && A == Op0))
 266     return Constant::getNullValue(Op0->getType());
 267
 268   // (A | ?) & A = A
 269   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
 270       (A == Op1 || B == Op1))
 271     return Op1;
 272
 273   // A & (A | ?) = A
 274   if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
 275       (A == Op0 || B == Op0))
 276     return Op0;
 277
 278   // (A & B) & A -> A & B
 279   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
 280       (A == Op1 || B == Op1))
 281     return Op0;
 282
 283   // A & (A & B) -> A & B
 284   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
 285       (A == Op0 || B == Op0))
 286     return Op1;
 287
 288   // If the operation is with the result of a select instruction, check whether
 289   // operating on either branch of the select always yields the same value.
 290   if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
 291     if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD,
 292                                          MaxRecurse-1))
 293       return V;
 294
 295   // If the operation is with the result of a phi instruction, check whether
 296   // operating on all incoming values of the phi always yields the same value.
 297   if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
 298     if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD,
 299                                       MaxRecurse-1))
 300       return V;
 301
 302   return 0;
 303 }
 304
 305 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD) {
 306   return ::SimplifyAndInst(Op0, Op1, TD, MaxRecursionDepth);
 307 }
 308
 309 /// SimplifyOrInst - Given operands for an Or, see if we can
 310 /// fold the result.  If not, this returns null.
 311 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
 312                              unsigned MaxRecurse) {
 313   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 314     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 315       Constant *Ops[] = { CLHS, CRHS };
 316       return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
 317                                       Ops, 2, TD);
 318     }
 319
 320     // Canonicalize the constant to the RHS.
 321     std::swap(Op0, Op1);
 322   }
 323
 324   // X | undef -> -1
 325   if (isa<UndefValue>(Op1))
 326     return Constant::getAllOnesValue(Op0->getType());
 327
 328   // X | X = X
 329   if (Op0 == Op1)
 330     return Op0;
 331
 332   // X | <0,0> = X
 333   if (isa<ConstantAggregateZero>(Op1))
 334     return Op0;
 335
 336   // X | <-1,-1> = <-1,-1>
 337   if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
 338     if (CP->isAllOnesValue())
 339       return Op1;
 340
 341   if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
 342     // X | 0 = X
 343     if (Op1CI->isZero())
 344       return Op0;
 345     // X | -1 = -1
 346     if (Op1CI->isAllOnesValue())
 347       return Op1CI;
 348   }
 349
 350   // A | ~A  =  ~A | A  =  -1
 351   Value *A, *B;
 352   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
 353       (match(Op1, m_Not(m_Value(A))) && A == Op0))
 354     return Constant::getAllOnesValue(Op0->getType());
 355
 356   // (A & ?) | A = A
 357   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
 358       (A == Op1 || B == Op1))
 359     return Op1;
 360
 361   // A | (A & ?) = A
 362   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
 363       (A == Op0 || B == Op0))
 364     return Op0;
 365
 366   // (A | B) | A -> A | B
 367   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
 368       (A == Op1 || B == Op1))
 369     return Op0;
 370
 371   // A | (A | B) -> A | B
 372   if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
 373       (A == Op0 || B == Op0))
 374     return Op1;
 375
 376   // If the operation is with the result of a select instruction, check whether
 377   // operating on either branch of the select always yields the same value.
 378   if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
 379     if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD,
 380                                          MaxRecurse-1))
 381       return V;
 382
 383   // If the operation is with the result of a phi instruction, check whether
 384   // operating on all incoming values of the phi always yields the same value.
 385   if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
 386     if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD,
 387                                       MaxRecurse-1))
 388       return V;
 389
 390   return 0;
 391 }
 392
 393 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD) {
 394   return ::SimplifyOrInst(Op0, Op1, TD, MaxRecursionDepth);
 395 }
 396
 397 static const Type *GetCompareTy(Value *Op) {
 398   return CmpInst::makeCmpResultType(Op->getType());
 399 }
 400
 401 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
 402 /// fold the result.  If not, this returns null.
 403 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 404                                const TargetData *TD, unsigned MaxRecurse) {
 405   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
 406   assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
 407
 408   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
 409     if (Constant *CRHS = dyn_cast<Constant>(RHS))
 410       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
 411
 412     // If we have a constant, make sure it is on the RHS.
 413     std::swap(LHS, RHS);
 414     Pred = CmpInst::getSwappedPredicate(Pred);
 415   }
 416
 417   // ITy - This is the return type of the compare we're considering.
 418   const Type *ITy = GetCompareTy(LHS);
 419
 420   // icmp X, X -> true/false
 421   // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
 422   // because X could be 0.
 423   if (LHS == RHS || isa<UndefValue>(RHS))
 424     return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
 425
 426   // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
 427   // addresses never equal each other!  We already know that Op0 != Op1.
 428   if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
 429        isa<ConstantPointerNull>(LHS)) &&
 430       (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
 431        isa<ConstantPointerNull>(RHS)))
 432     return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
 433
 434   // See if we are doing a comparison with a constant.
 435   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
 436     // If we have an icmp le or icmp ge instruction, turn it into the
 437     // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
 438     // them being folded in the code below.
 439     switch (Pred) {
 440     default: break;
 441     case ICmpInst::ICMP_ULE:
 442       if (CI->isMaxValue(false))                 // A <=u MAX -> TRUE
 443         return ConstantInt::getTrue(CI->getContext());
 444       break;
 445     case ICmpInst::ICMP_SLE:
 446       if (CI->isMaxValue(true))                  // A <=s MAX -> TRUE
 447         return ConstantInt::getTrue(CI->getContext());
 448       break;
 449     case ICmpInst::ICMP_UGE:
 450       if (CI->isMinValue(false))                 // A >=u MIN -> TRUE
 451         return ConstantInt::getTrue(CI->getContext());
 452       break;
 453     case ICmpInst::ICMP_SGE:
 454       if (CI->isMinValue(true))                  // A >=s MIN -> TRUE
 455         return ConstantInt::getTrue(CI->getContext());
 456       break;
 457     }
 458   }
 459
 460   // If the comparison is with the result of a select instruction, check whether
 461   // comparing with either branch of the select always yields the same value.
 462   if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
 463     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, MaxRecurse-1))
 464       return V;
 465
 466   // If the comparison is with the result of a phi instruction, check whether
 467   // doing the compare with each incoming phi value yields a common result.
 468   if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
 469     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, MaxRecurse-1))
 470       return V;
 471
 472   return 0;
 473 }
 474
 475 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 476                               const TargetData *TD) {
 477   return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth);
 478 }
 479
 480 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
 481 /// fold the result.  If not, this returns null.
 482 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 483                                const TargetData *TD, unsigned MaxRecurse) {
 484   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
 485   assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
 486
 487   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
 488     if (Constant *CRHS = dyn_cast<Constant>(RHS))
 489       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
 490
 491     // If we have a constant, make sure it is on the RHS.
 492     std::swap(LHS, RHS);
 493     Pred = CmpInst::getSwappedPredicate(Pred);
 494   }
 495
 496   // Fold trivial predicates.
 497   if (Pred == FCmpInst::FCMP_FALSE)
 498     return ConstantInt::get(GetCompareTy(LHS), 0);
 499   if (Pred == FCmpInst::FCMP_TRUE)
 500     return ConstantInt::get(GetCompareTy(LHS), 1);
 501
 502   if (isa<UndefValue>(RHS))                  // fcmp pred X, undef -> undef
 503     return UndefValue::get(GetCompareTy(LHS));
 504
 505   // fcmp x,x -> true/false.  Not all compares are foldable.
 506   if (LHS == RHS) {
 507     if (CmpInst::isTrueWhenEqual(Pred))
 508       return ConstantInt::get(GetCompareTy(LHS), 1);
 509     if (CmpInst::isFalseWhenEqual(Pred))
 510       return ConstantInt::get(GetCompareTy(LHS), 0);
 511   }
 512
 513   // Handle fcmp with constant RHS
 514   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
 515     // If the constant is a nan, see if we can fold the comparison based on it.
 516     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
 517       if (CFP->getValueAPF().isNaN()) {
 518         if (FCmpInst::isOrdered(Pred))   // True "if ordered and foo"
 519           return ConstantInt::getFalse(CFP->getContext());
 520         assert(FCmpInst::isUnordered(Pred) &&
 521                "Comparison must be either ordered or unordered!");
 522         // True if unordered.
 523         return ConstantInt::getTrue(CFP->getContext());
 524       }
 525       // Check whether the constant is an infinity.
 526       if (CFP->getValueAPF().isInfinity()) {
 527         if (CFP->getValueAPF().isNegative()) {
 528           switch (Pred) {
 529           case FCmpInst::FCMP_OLT:
 530             // No value is ordered and less than negative infinity.
 531             return ConstantInt::getFalse(CFP->getContext());
 532           case FCmpInst::FCMP_UGE:
 533             // All values are unordered with or at least negative infinity.
 534             return ConstantInt::getTrue(CFP->getContext());
 535           default:
 536             break;
 537           }
 538         } else {
 539           switch (Pred) {
 540           case FCmpInst::FCMP_OGT:
 541             // No value is ordered and greater than infinity.
 542             return ConstantInt::getFalse(CFP->getContext());
 543           case FCmpInst::FCMP_ULE:
 544             // All values are unordered with and at most infinity.
 545             return ConstantInt::getTrue(CFP->getContext());
 546           default:
 547             break;
 548           }
 549         }
 550       }
 551     }
 552   }
 553
 554   // If the comparison is with the result of a select instruction, check whether
 555   // comparing with either branch of the select always yields the same value.
 556   if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
 557     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, MaxRecurse-1))
 558       return V;
 559
 560   // If the comparison is with the result of a phi instruction, check whether
 561   // doing the compare with each incoming phi value yields a common result.
 562   if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
 563     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, MaxRecurse-1))
 564       return V;
 565
 566   return 0;
 567 }
 568
 569 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 570                               const TargetData *TD) {
 571   return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth);
 572 }
 573
 574 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
 575 /// the result.  If not, this returns null.
 576 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
 577                                 const TargetData *TD) {
 578   // select true, X, Y  -> X
 579   // select false, X, Y -> Y
 580   if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
 581     return CB->getZExtValue() ? TrueVal : FalseVal;
 582
 583   // select C, X, X -> X
 584   if (TrueVal == FalseVal)
 585     return TrueVal;
 586
 587   if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
 588     return FalseVal;
 589   if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
 590     return TrueVal;
 591   if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
 592     if (isa<Constant>(TrueVal))
 593       return TrueVal;
 594     return FalseVal;
 595   }
 596
 597   return 0;
 598 }
 599
 600
 601 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
 602 /// fold the result.  If not, this returns null.
 603 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
 604                              const TargetData *TD) {
 605   // getelementptr P -> P.
 606   if (NumOps == 1)
 607     return Ops[0];
 608
 609   // TODO.
 610   //if (isa<UndefValue>(Ops[0]))
 611   //  return UndefValue::get(GEP.getType());
 612
 613   // getelementptr P, 0 -> P.
 614   if (NumOps == 2)
 615     if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
 616       if (C->isZero())
 617         return Ops[0];
 618
 619   // Check to see if this is constant foldable.
 620   for (unsigned i = 0; i != NumOps; ++i)
 621     if (!isa<Constant>(Ops[i]))
 622       return 0;
 623
 624   return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
 625                                         (Constant *const*)Ops+1, NumOps-1);
 626 }
 627
 628
 629 //=== Helper functions for higher up the class hierarchy.
 630
 631 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
 632 /// fold the result.  If not, this returns null.
 633 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 634                             const TargetData *TD, unsigned MaxRecurse) {
 635   switch (Opcode) {
 636   case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, MaxRecurse);
 637   case Instruction::Or:  return SimplifyOrInst(LHS, RHS, TD, MaxRecurse);
 638   default:
 639     if (Constant *CLHS = dyn_cast<Constant>(LHS))
 640       if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
 641         Constant *COps[] = {CLHS, CRHS};
 642         return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
 643       }
 644
 645     // If the operation is with the result of a select instruction, check whether
 646     // operating on either branch of the select always yields the same value.
 647     if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
 648       if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, MaxRecurse-1))
 649         return V;
 650
 651     // If the operation is with the result of a phi instruction, check whether
 652     // operating on all incoming values of the phi always yields the same value.
 653     if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
 654       if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, MaxRecurse-1))
 655         return V;
 656
 657     return 0;
 658   }
 659 }
 660
 661 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 662                            const TargetData *TD) {
 663   return ::SimplifyBinOp(Opcode, LHS, RHS, TD, MaxRecursionDepth);
 664 }
 665
 666 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
 667 /// fold the result.
 668 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 669                               const TargetData *TD, unsigned MaxRecurse) {
 670   if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
 671     return SimplifyICmpInst(Predicate, LHS, RHS, TD, MaxRecurse);
 672   return SimplifyFCmpInst(Predicate, LHS, RHS, TD, MaxRecurse);
 673 }
 674
 675 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 676                              const TargetData *TD) {
 677   return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth);
 678 }
 679
 680 /// SimplifyInstruction - See if we can compute a simplified version of this
 681 /// instruction.  If not, this returns null.
 682 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
 683                                  const DominatorTree *DT) {
 684   switch (I->getOpcode()) {
 685   default:
 686     return ConstantFoldInstruction(I, TD);
 687   case Instruction::Add:
 688     return SimplifyAddInst(I->getOperand(0), I->getOperand(1),
 689                            cast<BinaryOperator>(I)->hasNoSignedWrap(),
 690                            cast<BinaryOperator>(I)->hasNoUnsignedWrap(), TD);
 691   case Instruction::And:
 692     return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD);
 693   case Instruction::Or:
 694     return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD);
 695   case Instruction::ICmp:
 696     return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
 697                             I->getOperand(0), I->getOperand(1), TD);
 698   case Instruction::FCmp:
 699     return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
 700                             I->getOperand(0), I->getOperand(1), TD);
 701   case Instruction::Select:
 702     return SimplifySelectInst(I->getOperand(0), I->getOperand(1),
 703                               I->getOperand(2), TD);
 704   case Instruction::GetElementPtr: {
 705     SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
 706     return SimplifyGEPInst(&Ops[0], Ops.size(), TD);
 707   }
 708   case Instruction::PHI:
 709     return cast<PHINode>(I)->hasConstantValue(DT);
 710   }
 711 }
 712
 713 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
 714 /// delete the From instruction.  In addition to a basic RAUW, this does a
 715 /// recursive simplification of the newly formed instructions.  This catches
 716 /// things where one simplification exposes other opportunities.  This only
 717 /// simplifies and deletes scalar operations, it does not change the CFG.
 718 ///
 719 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
 720                                      const TargetData *TD,
 721                                      const DominatorTree *DT) {
 722   assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
 723
 724   // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
 725   // we can know if it gets deleted out from under us or replaced in a
 726   // recursive simplification.
 727   WeakVH FromHandle(From);
 728   WeakVH ToHandle(To);
 729
 730   while (!From->use_empty()) {
 731     // Update the instruction to use the new value.
 732     Use &TheUse = From->use_begin().getUse();
 733     Instruction *User = cast<Instruction>(TheUse.getUser());
 734     TheUse = To;
 735
 736     // Check to see if the instruction can be folded due to the operand
 737     // replacement.  For example changing (or X, Y) into (or X, -1) can replace
 738     // the 'or' with -1.
 739     Value *SimplifiedVal;
 740     {
 741       // Sanity check to make sure 'User' doesn't dangle across
 742       // SimplifyInstruction.
 743       AssertingVH<> UserHandle(User);
 744
 745       SimplifiedVal = SimplifyInstruction(User, TD, DT);
 746       if (SimplifiedVal == 0) continue;
 747     }
 748
 749     // Recursively simplify this user to the new value.
 750     ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
 751     From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
 752     To = ToHandle;
 753
 754     assert(ToHandle && "To value deleted by recursive simplification?");
 755
 756     // If the recursive simplification ended up revisiting and deleting
 757     // 'From' then we're done.
 758     if (From == 0)
 759       return;
 760   }
 761
 762   // If 'From' has value handles referring to it, do a real RAUW to update them.
 763   From->replaceAllUsesWith(To);
 764
 765   From->eraseFromParent();
 766 }