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