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