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