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.  This does constant folding
  12 // ("add i32 1, 1" -> "2") but can also handle non-constant operands, either
  13 // returning a constant ("and i32 %x, 0" -> "0") or an already existing value
  14 // ("and i32 %x, %x" -> "%x").  All operands are assumed to have already been
  15 // simplified: This is usually true and assuming it simplifies the logic (if
  16 // they have not been simplified then results are correct but maybe suboptimal).
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #define DEBUG_TYPE "instsimplify"
  21 #include "llvm/Operator.h"
  22 #include "llvm/ADT/Statistic.h"
  23 #include "llvm/Analysis/InstructionSimplify.h"
  24 #include "llvm/Analysis/ConstantFolding.h"
  25 #include "llvm/Analysis/Dominators.h"
  26 #include "llvm/Analysis/ValueTracking.h"
  27 #include "llvm/Support/ConstantRange.h"
  28 #include "llvm/Support/PatternMatch.h"
  29 #include "llvm/Support/ValueHandle.h"
  30 #include "llvm/Target/TargetData.h"
  31 using namespace llvm;
  32 using namespace llvm::PatternMatch;
  33
  34 enum { RecursionLimit = 3 };
  35
  36 STATISTIC(NumExpand,  "Number of expansions");
  37 STATISTIC(NumFactor , "Number of factorizations");
  38 STATISTIC(NumReassoc, "Number of reassociations");
  39
  40 static Value *SimplifyAndInst(Value *, Value *, const TargetData *,
  41                               const DominatorTree *, unsigned);
  42 static Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *,
  43                             const DominatorTree *, unsigned);
  44 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *,
  45                               const DominatorTree *, unsigned);
  46 static Value *SimplifyOrInst(Value *, Value *, const TargetData *,
  47                              const DominatorTree *, unsigned);
  48 static Value *SimplifyXorInst(Value *, Value *, const TargetData *,
  49                               const DominatorTree *, unsigned);
  50
  51 /// getFalse - For a boolean type, or a vector of boolean type, return false, or
  52 /// a vector with every element false, as appropriate for the type.
  53 static Constant *getFalse(Type *Ty) {
  54   assert(Ty->getScalarType()->isIntegerTy(1) &&
  55          "Expected i1 type or a vector of i1!");
  56   return Constant::getNullValue(Ty);
  57 }
  58
  59 /// getTrue - For a boolean type, or a vector of boolean type, return true, or
  60 /// a vector with every element true, as appropriate for the type.
  61 static Constant *getTrue(Type *Ty) {
  62   assert(Ty->getScalarType()->isIntegerTy(1) &&
  63          "Expected i1 type or a vector of i1!");
  64   return Constant::getAllOnesValue(Ty);
  65 }
  66
  67 /// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"?
  68 static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS,
  69                           Value *RHS) {
  70   CmpInst *Cmp = dyn_cast<CmpInst>(V);
  71   if (!Cmp)
  72     return false;
  73   CmpInst::Predicate CPred = Cmp->getPredicate();
  74   Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1);
  75   if (CPred == Pred && CLHS == LHS && CRHS == RHS)
  76     return true;
  77   return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS &&
  78     CRHS == LHS;
  79 }
  80
  81 /// ValueDominatesPHI - Does the given value dominate the specified phi node?
  82 static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
  83   Instruction *I = dyn_cast<Instruction>(V);
  84   if (!I)
  85     // Arguments and constants dominate all instructions.
  86     return true;
  87
  88   // If we have a DominatorTree then do a precise test.
  89   if (DT)
  90     return DT->dominates(I, P);
  91
  92   // Otherwise, if the instruction is in the entry block, and is not an invoke,
  93   // then it obviously dominates all phi nodes.
  94   if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() &&
  95       !isa<InvokeInst>(I))
  96     return true;
  97
  98   return false;
  99 }
 100
 101 /// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning
 102 /// it into "(A op B) op' (A op C)".  Here "op" is given by Opcode and "op'" is
 103 /// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.
 104 /// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
 105 /// Returns the simplified value, or null if no simplification was performed.
 106 static Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 107                           unsigned OpcToExpand, const TargetData *TD,
 108                           const DominatorTree *DT, unsigned MaxRecurse) {
 109   Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand;
 110   // Recursion is always used, so bail out at once if we already hit the limit.
 111   if (!MaxRecurse--)
 112     return 0;
 113
 114   // Check whether the expression has the form "(A op' B) op C".
 115   if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS))
 116     if (Op0->getOpcode() == OpcodeToExpand) {
 117       // It does!  Try turning it into "(A op C) op' (B op C)".
 118       Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
 119       // Do "A op C" and "B op C" both simplify?
 120       if (Value *L = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse))
 121         if (Value *R = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) {
 122           // They do! Return "L op' R" if it simplifies or is already available.
 123           // If "L op' R" equals "A op' B" then "L op' R" is just the LHS.
 124           if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand)
 125                                      && L == B && R == A)) {
 126             ++NumExpand;
 127             return LHS;
 128           }
 129           // Otherwise return "L op' R" if it simplifies.
 130           if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT,
 131                                        MaxRecurse)) {
 132             ++NumExpand;
 133             return V;
 134           }
 135         }
 136     }
 137
 138   // Check whether the expression has the form "A op (B op' C)".
 139   if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
 140     if (Op1->getOpcode() == OpcodeToExpand) {
 141       // It does!  Try turning it into "(A op B) op' (A op C)".
 142       Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
 143       // Do "A op B" and "A op C" both simplify?
 144       if (Value *L = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse))
 145         if (Value *R = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) {
 146           // They do! Return "L op' R" if it simplifies or is already available.
 147           // If "L op' R" equals "B op' C" then "L op' R" is just the RHS.
 148           if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand)
 149                                      && L == C && R == B)) {
 150             ++NumExpand;
 151             return RHS;
 152           }
 153           // Otherwise return "L op' R" if it simplifies.
 154           if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT,
 155                                        MaxRecurse)) {
 156             ++NumExpand;
 157             return V;
 158           }
 159         }
 160     }
 161
 162   return 0;
 163 }
 164
 165 /// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term
 166 /// using the operation OpCodeToExtract.  For example, when Opcode is Add and
 167 /// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)".
 168 /// Returns the simplified value, or null if no simplification was performed.
 169 static Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 170                              unsigned OpcToExtract, const TargetData *TD,
 171                              const DominatorTree *DT, unsigned MaxRecurse) {
 172   Instruction::BinaryOps OpcodeToExtract = (Instruction::BinaryOps)OpcToExtract;
 173   // Recursion is always used, so bail out at once if we already hit the limit.
 174   if (!MaxRecurse--)
 175     return 0;
 176
 177   BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
 178   BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
 179
 180   if (!Op0 || Op0->getOpcode() != OpcodeToExtract ||
 181       !Op1 || Op1->getOpcode() != OpcodeToExtract)
 182     return 0;
 183
 184   // The expression has the form "(A op' B) op (C op' D)".
 185   Value *A = Op0->getOperand(0), *B = Op0->getOperand(1);
 186   Value *C = Op1->getOperand(0), *D = Op1->getOperand(1);
 187
 188   // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)".
 189   // Does the instruction have the form "(A op' B) op (A op' D)" or, in the
 190   // commutative case, "(A op' B) op (C op' A)"?
 191   if (A == C || (Instruction::isCommutative(OpcodeToExtract) && A == D)) {
 192     Value *DD = A == C ? D : C;
 193     // Form "A op' (B op DD)" if it simplifies completely.
 194     // Does "B op DD" simplify?
 195     if (Value *V = SimplifyBinOp(Opcode, B, DD, TD, DT, MaxRecurse)) {
 196       // It does!  Return "A op' V" if it simplifies or is already available.
 197       // If V equals B then "A op' V" is just the LHS.  If V equals DD then
 198       // "A op' V" is just the RHS.
 199       if (V == B || V == DD) {
 200         ++NumFactor;
 201         return V == B ? LHS : RHS;
 202       }
 203       // Otherwise return "A op' V" if it simplifies.
 204       if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, TD, DT, MaxRecurse)) {
 205         ++NumFactor;
 206         return W;
 207       }
 208     }
 209   }
 210
 211   // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)".
 212   // Does the instruction have the form "(A op' B) op (C op' B)" or, in the
 213   // commutative case, "(A op' B) op (B op' D)"?
 214   if (B == D || (Instruction::isCommutative(OpcodeToExtract) && B == C)) {
 215     Value *CC = B == D ? C : D;
 216     // Form "(A op CC) op' B" if it simplifies completely..
 217     // Does "A op CC" simplify?
 218     if (Value *V = SimplifyBinOp(Opcode, A, CC, TD, DT, MaxRecurse)) {
 219       // It does!  Return "V op' B" if it simplifies or is already available.
 220       // If V equals A then "V op' B" is just the LHS.  If V equals CC then
 221       // "V op' B" is just the RHS.
 222       if (V == A || V == CC) {
 223         ++NumFactor;
 224         return V == A ? LHS : RHS;
 225       }
 226       // Otherwise return "V op' B" if it simplifies.
 227       if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, TD, DT, MaxRecurse)) {
 228         ++NumFactor;
 229         return W;
 230       }
 231     }
 232   }
 233
 234   return 0;
 235 }
 236
 237 /// SimplifyAssociativeBinOp - Generic simplifications for associative binary
 238 /// operations.  Returns the simpler value, or null if none was found.
 239 static Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS,
 240                                        const TargetData *TD,
 241                                        const DominatorTree *DT,
 242                                        unsigned MaxRecurse) {
 243   Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc;
 244   assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
 245
 246   // Recursion is always used, so bail out at once if we already hit the limit.
 247   if (!MaxRecurse--)
 248     return 0;
 249
 250   BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
 251   BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
 252
 253   // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely.
 254   if (Op0 && Op0->getOpcode() == Opcode) {
 255     Value *A = Op0->getOperand(0);
 256     Value *B = Op0->getOperand(1);
 257     Value *C = RHS;
 258
 259     // Does "B op C" simplify?
 260     if (Value *V = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) {
 261       // It does!  Return "A op V" if it simplifies or is already available.
 262       // If V equals B then "A op V" is just the LHS.
 263       if (V == B) return LHS;
 264       // Otherwise return "A op V" if it simplifies.
 265       if (Value *W = SimplifyBinOp(Opcode, A, V, TD, DT, MaxRecurse)) {
 266         ++NumReassoc;
 267         return W;
 268       }
 269     }
 270   }
 271
 272   // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely.
 273   if (Op1 && Op1->getOpcode() == Opcode) {
 274     Value *A = LHS;
 275     Value *B = Op1->getOperand(0);
 276     Value *C = Op1->getOperand(1);
 277
 278     // Does "A op B" simplify?
 279     if (Value *V = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) {
 280       // It does!  Return "V op C" if it simplifies or is already available.
 281       // If V equals B then "V op C" is just the RHS.
 282       if (V == B) return RHS;
 283       // Otherwise return "V op C" if it simplifies.
 284       if (Value *W = SimplifyBinOp(Opcode, V, C, TD, DT, MaxRecurse)) {
 285         ++NumReassoc;
 286         return W;
 287       }
 288     }
 289   }
 290
 291   // The remaining transforms require commutativity as well as associativity.
 292   if (!Instruction::isCommutative(Opcode))
 293     return 0;
 294
 295   // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely.
 296   if (Op0 && Op0->getOpcode() == Opcode) {
 297     Value *A = Op0->getOperand(0);
 298     Value *B = Op0->getOperand(1);
 299     Value *C = RHS;
 300
 301     // Does "C op A" simplify?
 302     if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) {
 303       // It does!  Return "V op B" if it simplifies or is already available.
 304       // If V equals A then "V op B" is just the LHS.
 305       if (V == A) return LHS;
 306       // Otherwise return "V op B" if it simplifies.
 307       if (Value *W = SimplifyBinOp(Opcode, V, B, TD, DT, MaxRecurse)) {
 308         ++NumReassoc;
 309         return W;
 310       }
 311     }
 312   }
 313
 314   // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely.
 315   if (Op1 && Op1->getOpcode() == Opcode) {
 316     Value *A = LHS;
 317     Value *B = Op1->getOperand(0);
 318     Value *C = Op1->getOperand(1);
 319
 320     // Does "C op A" simplify?
 321     if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) {
 322       // It does!  Return "B op V" if it simplifies or is already available.
 323       // If V equals C then "B op V" is just the RHS.
 324       if (V == C) return RHS;
 325       // Otherwise return "B op V" if it simplifies.
 326       if (Value *W = SimplifyBinOp(Opcode, B, V, TD, DT, MaxRecurse)) {
 327         ++NumReassoc;
 328         return W;
 329       }
 330     }
 331   }
 332
 333   return 0;
 334 }
 335
 336 /// ThreadBinOpOverSelect - In the case of a binary operation with a select
 337 /// instruction as an operand, try to simplify the binop by seeing whether
 338 /// evaluating it on both branches of the select results in the same value.
 339 /// Returns the common value if so, otherwise returns null.
 340 static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
 341                                     const TargetData *TD,
 342                                     const DominatorTree *DT,
 343                                     unsigned MaxRecurse) {
 344   // Recursion is always used, so bail out at once if we already hit the limit.
 345   if (!MaxRecurse--)
 346     return 0;
 347
 348   SelectInst *SI;
 349   if (isa<SelectInst>(LHS)) {
 350     SI = cast<SelectInst>(LHS);
 351   } else {
 352     assert(isa<SelectInst>(RHS) && "No select instruction operand!");
 353     SI = cast<SelectInst>(RHS);
 354   }
 355
 356   // Evaluate the BinOp on the true and false branches of the select.
 357   Value *TV;
 358   Value *FV;
 359   if (SI == LHS) {
 360     TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse);
 361     FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse);
 362   } else {
 363     TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse);
 364     FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse);
 365   }
 366
 367   // If they simplified to the same value, then return the common value.
 368   // If they both failed to simplify then return null.
 369   if (TV == FV)
 370     return TV;
 371
 372   // If one branch simplified to undef, return the other one.
 373   if (TV && isa<UndefValue>(TV))
 374     return FV;
 375   if (FV && isa<UndefValue>(FV))
 376     return TV;
 377
 378   // If applying the operation did not change the true and false select values,
 379   // then the result of the binop is the select itself.
 380   if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
 381     return SI;
 382
 383   // If one branch simplified and the other did not, and the simplified
 384   // value is equal to the unsimplified one, return the simplified value.
 385   // For example, select (cond, X, X & Z) & Z -> X & Z.
 386   if ((FV && !TV) || (TV && !FV)) {
 387     // Check that the simplified value has the form "X op Y" where "op" is the
 388     // same as the original operation.
 389     Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
 390     if (Simplified && Simplified->getOpcode() == Opcode) {
 391       // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
 392       // We already know that "op" is the same as for the simplified value.  See
 393       // if the operands match too.  If so, return the simplified value.
 394       Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
 395       Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
 396       Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
 397       if (Simplified->getOperand(0) == UnsimplifiedLHS &&
 398           Simplified->getOperand(1) == UnsimplifiedRHS)
 399         return Simplified;
 400       if (Simplified->isCommutative() &&
 401           Simplified->getOperand(1) == UnsimplifiedLHS &&
 402           Simplified->getOperand(0) == UnsimplifiedRHS)
 403         return Simplified;
 404     }
 405   }
 406
 407   return 0;
 408 }
 409
 410 /// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
 411 /// try to simplify the comparison by seeing whether both branches of the select
 412 /// result in the same value.  Returns the common value if so, otherwise returns
 413 /// null.
 414 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
 415                                   Value *RHS, const TargetData *TD,
 416                                   const DominatorTree *DT,
 417                                   unsigned MaxRecurse) {
 418   // Recursion is always used, so bail out at once if we already hit the limit.
 419   if (!MaxRecurse--)
 420     return 0;
 421
 422   // Make sure the select is on the LHS.
 423   if (!isa<SelectInst>(LHS)) {
 424     std::swap(LHS, RHS);
 425     Pred = CmpInst::getSwappedPredicate(Pred);
 426   }
 427   assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
 428   SelectInst *SI = cast<SelectInst>(LHS);
 429   Value *Cond = SI->getCondition();
 430   Value *TV = SI->getTrueValue();
 431   Value *FV = SI->getFalseValue();
 432
 433   // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it.
 434   // Does "cmp TV, RHS" simplify?
 435   Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, TD, DT, MaxRecurse);
 436   if (TCmp == Cond) {
 437     // It not only simplified, it simplified to the select condition.  Replace
 438     // it with 'true'.
 439     TCmp = getTrue(Cond->getType());
 440   } else if (!TCmp) {
 441     // It didn't simplify.  However if "cmp TV, RHS" is equal to the select
 442     // condition then we can replace it with 'true'.  Otherwise give up.
 443     if (!isSameCompare(Cond, Pred, TV, RHS))
 444       return 0;
 445     TCmp = getTrue(Cond->getType());
 446   }
 447
 448   // Does "cmp FV, RHS" simplify?
 449   Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, TD, DT, MaxRecurse);
 450   if (FCmp == Cond) {
 451     // It not only simplified, it simplified to the select condition.  Replace
 452     // it with 'false'.
 453     FCmp = getFalse(Cond->getType());
 454   } else if (!FCmp) {
 455     // It didn't simplify.  However if "cmp FV, RHS" is equal to the select
 456     // condition then we can replace it with 'false'.  Otherwise give up.
 457     if (!isSameCompare(Cond, Pred, FV, RHS))
 458       return 0;
 459     FCmp = getFalse(Cond->getType());
 460   }
 461
 462   // If both sides simplified to the same value, then use it as the result of
 463   // the original comparison.
 464   if (TCmp == FCmp)
 465     return TCmp;
 466   // If the false value simplified to false, then the result of the compare
 467   // is equal to "Cond && TCmp".  This also catches the case when the false
 468   // value simplified to false and the true value to true, returning "Cond".
 469   if (match(FCmp, m_Zero()))
 470     if (Value *V = SimplifyAndInst(Cond, TCmp, TD, DT, MaxRecurse))
 471       return V;
 472   // If the true value simplified to true, then the result of the compare
 473   // is equal to "Cond || FCmp".
 474   if (match(TCmp, m_One()))
 475     if (Value *V = SimplifyOrInst(Cond, FCmp, TD, DT, MaxRecurse))
 476       return V;
 477   // Finally, if the false value simplified to true and the true value to
 478   // false, then the result of the compare is equal to "!Cond".
 479   if (match(FCmp, m_One()) && match(TCmp, m_Zero()))
 480     if (Value *V =
 481         SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()),
 482                         TD, DT, MaxRecurse))
 483       return V;
 484
 485   return 0;
 486 }
 487
 488 /// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
 489 /// is a PHI instruction, try to simplify the binop by seeing whether evaluating
 490 /// it on the incoming phi values yields the same result for every value.  If so
 491 /// returns the common value, otherwise returns null.
 492 static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
 493                                  const TargetData *TD, const DominatorTree *DT,
 494                                  unsigned MaxRecurse) {
 495   // Recursion is always used, so bail out at once if we already hit the limit.
 496   if (!MaxRecurse--)
 497     return 0;
 498
 499   PHINode *PI;
 500   if (isa<PHINode>(LHS)) {
 501     PI = cast<PHINode>(LHS);
 502     // Bail out if RHS and the phi may be mutually interdependent due to a loop.
 503     if (!ValueDominatesPHI(RHS, PI, DT))
 504       return 0;
 505   } else {
 506     assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
 507     PI = cast<PHINode>(RHS);
 508     // Bail out if LHS and the phi may be mutually interdependent due to a loop.
 509     if (!ValueDominatesPHI(LHS, PI, DT))
 510       return 0;
 511   }
 512
 513   // Evaluate the BinOp on the incoming phi values.
 514   Value *CommonValue = 0;
 515   for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
 516     Value *Incoming = PI->getIncomingValue(i);
 517     // If the incoming value is the phi node itself, it can safely be skipped.
 518     if (Incoming == PI) continue;
 519     Value *V = PI == LHS ?
 520       SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) :
 521       SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse);
 522     // If the operation failed to simplify, or simplified to a different value
 523     // to previously, then give up.
 524     if (!V || (CommonValue && V != CommonValue))
 525       return 0;
 526     CommonValue = V;
 527   }
 528
 529   return CommonValue;
 530 }
 531
 532 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
 533 /// try to simplify the comparison by seeing whether comparing with all of the
 534 /// incoming phi values yields the same result every time.  If so returns the
 535 /// common result, otherwise returns null.
 536 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
 537                                const TargetData *TD, const DominatorTree *DT,
 538                                unsigned MaxRecurse) {
 539   // Recursion is always used, so bail out at once if we already hit the limit.
 540   if (!MaxRecurse--)
 541     return 0;
 542
 543   // Make sure the phi is on the LHS.
 544   if (!isa<PHINode>(LHS)) {
 545     std::swap(LHS, RHS);
 546     Pred = CmpInst::getSwappedPredicate(Pred);
 547   }
 548   assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
 549   PHINode *PI = cast<PHINode>(LHS);
 550
 551   // Bail out if RHS and the phi may be mutually interdependent due to a loop.
 552   if (!ValueDominatesPHI(RHS, PI, DT))
 553     return 0;
 554
 555   // Evaluate the BinOp on the incoming phi values.
 556   Value *CommonValue = 0;
 557   for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
 558     Value *Incoming = PI->getIncomingValue(i);
 559     // If the incoming value is the phi node itself, it can safely be skipped.
 560     if (Incoming == PI) continue;
 561     Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse);
 562     // If the operation failed to simplify, or simplified to a different value
 563     // to previously, then give up.
 564     if (!V || (CommonValue && V != CommonValue))
 565       return 0;
 566     CommonValue = V;
 567   }
 568
 569   return CommonValue;
 570 }
 571
 572 /// SimplifyAddInst - Given operands for an Add, see if we can
 573 /// fold the result.  If not, this returns null.
 574 static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 575                               const TargetData *TD, const DominatorTree *DT,
 576                               unsigned MaxRecurse) {
 577   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 578     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 579       Constant *Ops[] = { CLHS, CRHS };
 580       return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
 581                                       Ops, TD);
 582     }
 583
 584     // Canonicalize the constant to the RHS.
 585     std::swap(Op0, Op1);
 586   }
 587
 588   // X + undef -> undef
 589   if (match(Op1, m_Undef()))
 590     return Op1;
 591
 592   // X + 0 -> X
 593   if (match(Op1, m_Zero()))
 594     return Op0;
 595
 596   // X + (Y - X) -> Y
 597   // (Y - X) + X -> Y
 598   // Eg: X + -X -> 0
 599   Value *Y = 0;
 600   if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
 601       match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
 602     return Y;
 603
 604   // X + ~X -> -1   since   ~X = -X-1
 605   if (match(Op0, m_Not(m_Specific(Op1))) ||
 606       match(Op1, m_Not(m_Specific(Op0))))
 607     return Constant::getAllOnesValue(Op0->getType());
 608
 609   /// i1 add -> xor.
 610   if (MaxRecurse && Op0->getType()->isIntegerTy(1))
 611     if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1))
 612       return V;
 613
 614   // Try some generic simplifications for associative operations.
 615   if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, TD, DT,
 616                                           MaxRecurse))
 617     return V;
 618
 619   // Mul distributes over Add.  Try some generic simplifications based on this.
 620   if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul,
 621                                 TD, DT, MaxRecurse))
 622     return V;
 623
 624   // Threading Add over selects and phi nodes is pointless, so don't bother.
 625   // Threading over the select in "A + select(cond, B, C)" means evaluating
 626   // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
 627   // only if B and C are equal.  If B and C are equal then (since we assume
 628   // that operands have already been simplified) "select(cond, B, C)" should
 629   // have been simplified to the common value of B and C already.  Analysing
 630   // "A+B" and "A+C" thus gains nothing, but costs compile time.  Similarly
 631   // for threading over phi nodes.
 632
 633   return 0;
 634 }
 635
 636 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 637                              const TargetData *TD, const DominatorTree *DT) {
 638   return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit);
 639 }
 640
 641 /// SimplifySubInst - Given operands for a Sub, see if we can
 642 /// fold the result.  If not, this returns null.
 643 static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 644                               const TargetData *TD, const DominatorTree *DT,
 645                               unsigned MaxRecurse) {
 646   if (Constant *CLHS = dyn_cast<Constant>(Op0))
 647     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 648       Constant *Ops[] = { CLHS, CRHS };
 649       return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(),
 650                                       Ops, TD);
 651     }
 652
 653   // X - undef -> undef
 654   // undef - X -> undef
 655   if (match(Op0, m_Undef()) || match(Op1, m_Undef()))
 656     return UndefValue::get(Op0->getType());
 657
 658   // X - 0 -> X
 659   if (match(Op1, m_Zero()))
 660     return Op0;
 661
 662   // X - X -> 0
 663   if (Op0 == Op1)
 664     return Constant::getNullValue(Op0->getType());
 665
 666   // (X*2) - X -> X
 667   // (X<<1) - X -> X
 668   Value *X = 0;
 669   if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())) ||
 670       match(Op0, m_Shl(m_Specific(Op1), m_One())))
 671     return Op1;
 672
 673   // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
 674   // For example, (X + Y) - Y -> X; (Y + X) - Y -> X
 675   Value *Y = 0, *Z = Op1;
 676   if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z
 677     // See if "V === Y - Z" simplifies.
 678     if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, TD, DT, MaxRecurse-1))
 679       // It does!  Now see if "X + V" simplifies.
 680       if (Value *W = SimplifyBinOp(Instruction::Add, X, V, TD, DT,
 681                                    MaxRecurse-1)) {
 682         // It does, we successfully reassociated!
 683         ++NumReassoc;
 684         return W;
 685       }
 686     // See if "V === X - Z" simplifies.
 687     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, TD, DT, MaxRecurse-1))
 688       // It does!  Now see if "Y + V" simplifies.
 689       if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, TD, DT,
 690                                    MaxRecurse-1)) {
 691         // It does, we successfully reassociated!
 692         ++NumReassoc;
 693         return W;
 694       }
 695   }
 696
 697   // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies.
 698   // For example, X - (X + 1) -> -1
 699   X = Op0;
 700   if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z)
 701     // See if "V === X - Y" simplifies.
 702     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, TD, DT, MaxRecurse-1))
 703       // It does!  Now see if "V - Z" simplifies.
 704       if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, TD, DT,
 705                                    MaxRecurse-1)) {
 706         // It does, we successfully reassociated!
 707         ++NumReassoc;
 708         return W;
 709       }
 710     // See if "V === X - Z" simplifies.
 711     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, TD, DT, MaxRecurse-1))
 712       // It does!  Now see if "V - Y" simplifies.
 713       if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, TD, DT,
 714                                    MaxRecurse-1)) {
 715         // It does, we successfully reassociated!
 716         ++NumReassoc;
 717         return W;
 718       }
 719   }
 720
 721   // Z - (X - Y) -> (Z - X) + Y if everything simplifies.
 722   // For example, X - (X - Y) -> Y.
 723   Z = Op0;
 724   if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y)
 725     // See if "V === Z - X" simplifies.
 726     if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, TD, DT, MaxRecurse-1))
 727       // It does!  Now see if "V + Y" simplifies.
 728       if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, TD, DT,
 729                                    MaxRecurse-1)) {
 730         // It does, we successfully reassociated!
 731         ++NumReassoc;
 732         return W;
 733       }
 734
 735   // Mul distributes over Sub.  Try some generic simplifications based on this.
 736   if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul,
 737                                 TD, DT, MaxRecurse))
 738     return V;
 739
 740   // i1 sub -> xor.
 741   if (MaxRecurse && Op0->getType()->isIntegerTy(1))
 742     if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1))
 743       return V;
 744
 745   // Threading Sub over selects and phi nodes is pointless, so don't bother.
 746   // Threading over the select in "A - select(cond, B, C)" means evaluating
 747   // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
 748   // only if B and C are equal.  If B and C are equal then (since we assume
 749   // that operands have already been simplified) "select(cond, B, C)" should
 750   // have been simplified to the common value of B and C already.  Analysing
 751   // "A-B" and "A-C" thus gains nothing, but costs compile time.  Similarly
 752   // for threading over phi nodes.
 753
 754   return 0;
 755 }
 756
 757 Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 758                              const TargetData *TD, const DominatorTree *DT) {
 759   return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit);
 760 }
 761
 762 /// SimplifyMulInst - Given operands for a Mul, see if we can
 763 /// fold the result.  If not, this returns null.
 764 static Value *SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD,
 765                               const DominatorTree *DT, unsigned MaxRecurse) {
 766   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 767     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 768       Constant *Ops[] = { CLHS, CRHS };
 769       return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(),
 770                                       Ops, TD);
 771     }
 772
 773     // Canonicalize the constant to the RHS.
 774     std::swap(Op0, Op1);
 775   }
 776
 777   // X * undef -> 0
 778   if (match(Op1, m_Undef()))
 779     return Constant::getNullValue(Op0->getType());
 780
 781   // X * 0 -> 0
 782   if (match(Op1, m_Zero()))
 783     return Op1;
 784
 785   // X * 1 -> X
 786   if (match(Op1, m_One()))
 787     return Op0;
 788
 789   // (X / Y) * Y -> X if the division is exact.
 790   Value *X = 0, *Y = 0;
 791   if ((match(Op0, m_IDiv(m_Value(X), m_Value(Y))) && Y == Op1) || // (X / Y) * Y
 792       (match(Op1, m_IDiv(m_Value(X), m_Value(Y))) && Y == Op0)) { // Y * (X / Y)
 793     PossiblyExactOperator *Div =
 794       cast<PossiblyExactOperator>(Y == Op1 ? Op0 : Op1);
 795     if (Div->isExact())
 796       return X;
 797   }
 798
 799   // i1 mul -> and.
 800   if (MaxRecurse && Op0->getType()->isIntegerTy(1))
 801     if (Value *V = SimplifyAndInst(Op0, Op1, TD, DT, MaxRecurse-1))
 802       return V;
 803
 804   // Try some generic simplifications for associative operations.
 805   if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, TD, DT,
 806                                           MaxRecurse))
 807     return V;
 808
 809   // Mul distributes over Add.  Try some generic simplifications based on this.
 810   if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add,
 811                              TD, DT, MaxRecurse))
 812     return V;
 813
 814   // If the operation is with the result of a select instruction, check whether
 815   // operating on either branch of the select always yields the same value.
 816   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
 817     if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, TD, DT,
 818                                          MaxRecurse))
 819       return V;
 820
 821   // If the operation is with the result of a phi instruction, check whether
 822   // operating on all incoming values of the phi always yields the same value.
 823   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
 824     if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, TD, DT,
 825                                       MaxRecurse))
 826       return V;
 827
 828   return 0;
 829 }
 830
 831 Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD,
 832                              const DominatorTree *DT) {
 833   return ::SimplifyMulInst(Op0, Op1, TD, DT, RecursionLimit);
 834 }
 835
 836 /// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can
 837 /// fold the result.  If not, this returns null.
 838 static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
 839                           const TargetData *TD, const DominatorTree *DT,
 840                           unsigned MaxRecurse) {
 841   if (Constant *C0 = dyn_cast<Constant>(Op0)) {
 842     if (Constant *C1 = dyn_cast<Constant>(Op1)) {
 843       Constant *Ops[] = { C0, C1 };
 844       return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, TD);
 845     }
 846   }
 847
 848   bool isSigned = Opcode == Instruction::SDiv;
 849
 850   // X / undef -> undef
 851   if (match(Op1, m_Undef()))
 852     return Op1;
 853
 854   // undef / X -> 0
 855   if (match(Op0, m_Undef()))
 856     return Constant::getNullValue(Op0->getType());
 857
 858   // 0 / X -> 0, we don't need to preserve faults!
 859   if (match(Op0, m_Zero()))
 860     return Op0;
 861
 862   // X / 1 -> X
 863   if (match(Op1, m_One()))
 864     return Op0;
 865
 866   if (Op0->getType()->isIntegerTy(1))
 867     // It can't be division by zero, hence it must be division by one.
 868     return Op0;
 869
 870   // X / X -> 1
 871   if (Op0 == Op1)
 872     return ConstantInt::get(Op0->getType(), 1);
 873
 874   // (X * Y) / Y -> X if the multiplication does not overflow.
 875   Value *X = 0, *Y = 0;
 876   if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) {
 877     if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1
 878     OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0);
 879     // If the Mul knows it does not overflow, then we are good to go.
 880     if ((isSigned && Mul->hasNoSignedWrap()) ||
 881         (!isSigned && Mul->hasNoUnsignedWrap()))
 882       return X;
 883     // If X has the form X = A / Y then X * Y cannot overflow.
 884     if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X))
 885       if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y)
 886         return X;
 887   }
 888
 889   // (X rem Y) / Y -> 0
 890   if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
 891       (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
 892     return Constant::getNullValue(Op0->getType());
 893
 894   // If the operation is with the result of a select instruction, check whether
 895   // operating on either branch of the select always yields the same value.
 896   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
 897     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, DT, MaxRecurse))
 898       return V;
 899
 900   // If the operation is with the result of a phi instruction, check whether
 901   // operating on all incoming values of the phi always yields the same value.
 902   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
 903     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, DT, MaxRecurse))
 904       return V;
 905
 906   return 0;
 907 }
 908
 909 /// SimplifySDivInst - Given operands for an SDiv, see if we can
 910 /// fold the result.  If not, this returns null.
 911 static Value *SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD,
 912                                const DominatorTree *DT, unsigned MaxRecurse) {
 913   if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, TD, DT, MaxRecurse))
 914     return V;
 915
 916   return 0;
 917 }
 918
 919 Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD,
 920                               const DominatorTree *DT) {
 921   return ::SimplifySDivInst(Op0, Op1, TD, DT, RecursionLimit);
 922 }
 923
 924 /// SimplifyUDivInst - Given operands for a UDiv, see if we can
 925 /// fold the result.  If not, this returns null.
 926 static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD,
 927                                const DominatorTree *DT, unsigned MaxRecurse) {
 928   if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, TD, DT, MaxRecurse))
 929     return V;
 930
 931   return 0;
 932 }
 933
 934 Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD,
 935                               const DominatorTree *DT) {
 936   return ::SimplifyUDivInst(Op0, Op1, TD, DT, RecursionLimit);
 937 }
 938
 939 static Value *SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *,
 940                                const DominatorTree *, unsigned) {
 941   // undef / X -> undef    (the undef could be a snan).
 942   if (match(Op0, m_Undef()))
 943     return Op0;
 944
 945   // X / undef -> undef
 946   if (match(Op1, m_Undef()))
 947     return Op1;
 948
 949   return 0;
 950 }
 951
 952 Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *TD,
 953                               const DominatorTree *DT) {
 954   return ::SimplifyFDivInst(Op0, Op1, TD, DT, RecursionLimit);
 955 }
 956
 957 /// SimplifyRem - Given operands for an SRem or URem, see if we can
 958 /// fold the result.  If not, this returns null.
 959 static Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
 960                           const TargetData *TD, const DominatorTree *DT,
 961                           unsigned MaxRecurse) {
 962   if (Constant *C0 = dyn_cast<Constant>(Op0)) {
 963     if (Constant *C1 = dyn_cast<Constant>(Op1)) {
 964       Constant *Ops[] = { C0, C1 };
 965       return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, TD);
 966     }
 967   }
 968
 969   // X % undef -> undef
 970   if (match(Op1, m_Undef()))
 971     return Op1;
 972
 973   // undef % X -> 0
 974   if (match(Op0, m_Undef()))
 975     return Constant::getNullValue(Op0->getType());
 976
 977   // 0 % X -> 0, we don't need to preserve faults!
 978   if (match(Op0, m_Zero()))
 979     return Op0;
 980
 981   // X % 0 -> undef, we don't need to preserve faults!
 982   if (match(Op1, m_Zero()))
 983     return UndefValue::get(Op0->getType());
 984
 985   // X % 1 -> 0
 986   if (match(Op1, m_One()))
 987     return Constant::getNullValue(Op0->getType());
 988
 989   if (Op0->getType()->isIntegerTy(1))
 990     // It can't be remainder by zero, hence it must be remainder by one.
 991     return Constant::getNullValue(Op0->getType());
 992
 993   // X % X -> 0
 994   if (Op0 == Op1)
 995     return Constant::getNullValue(Op0->getType());
 996
 997   // If the operation is with the result of a select instruction, check whether
 998   // operating on either branch of the select always yields the same value.
 999   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1000     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, DT, MaxRecurse))
1001       return V;
1002
1003   // If the operation is with the result of a phi instruction, check whether
1004   // operating on all incoming values of the phi always yields the same value.
1005   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1006     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, DT, MaxRecurse))
1007       return V;
1008
1009   return 0;
1010 }
1011
1012 /// SimplifySRemInst - Given operands for an SRem, see if we can
1013 /// fold the result.  If not, this returns null.
1014 static Value *SimplifySRemInst(Value *Op0, Value *Op1, const TargetData *TD,
1015                                const DominatorTree *DT, unsigned MaxRecurse) {
1016   if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, TD, DT, MaxRecurse))
1017     return V;
1018
1019   return 0;
1020 }
1021
1022 Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const TargetData *TD,
1023                               const DominatorTree *DT) {
1024   return ::SimplifySRemInst(Op0, Op1, TD, DT, RecursionLimit);
1025 }
1026
1027 /// SimplifyURemInst - Given operands for a URem, see if we can
1028 /// fold the result.  If not, this returns null.
1029 static Value *SimplifyURemInst(Value *Op0, Value *Op1, const TargetData *TD,
1030                                const DominatorTree *DT, unsigned MaxRecurse) {
1031   if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, TD, DT, MaxRecurse))
1032     return V;
1033
1034   return 0;
1035 }
1036
1037 Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const TargetData *TD,
1038                               const DominatorTree *DT) {
1039   return ::SimplifyURemInst(Op0, Op1, TD, DT, RecursionLimit);
1040 }
1041
1042 static Value *SimplifyFRemInst(Value *Op0, Value *Op1, const TargetData *,
1043                                const DominatorTree *, unsigned) {
1044   // undef % X -> undef    (the undef could be a snan).
1045   if (match(Op0, m_Undef()))
1046     return Op0;
1047
1048   // X % undef -> undef
1049   if (match(Op1, m_Undef()))
1050     return Op1;
1051
1052   return 0;
1053 }
1054
1055 Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, const TargetData *TD,
1056                               const DominatorTree *DT) {
1057   return ::SimplifyFRemInst(Op0, Op1, TD, DT, RecursionLimit);
1058 }
1059
1060 /// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can
1061 /// fold the result.  If not, this returns null.
1062 static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1,
1063                             const TargetData *TD, const DominatorTree *DT,
1064                             unsigned MaxRecurse) {
1065   if (Constant *C0 = dyn_cast<Constant>(Op0)) {
1066     if (Constant *C1 = dyn_cast<Constant>(Op1)) {
1067       Constant *Ops[] = { C0, C1 };
1068       return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, TD);
1069     }
1070   }
1071
1072   // 0 shift by X -> 0
1073   if (match(Op0, m_Zero()))
1074     return Op0;
1075
1076   // X shift by 0 -> X
1077   if (match(Op1, m_Zero()))
1078     return Op0;
1079
1080   // X shift by undef -> undef because it may shift by the bitwidth.
1081   if (match(Op1, m_Undef()))
1082     return Op1;
1083
1084   // Shifting by the bitwidth or more is undefined.
1085   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1))
1086     if (CI->getValue().getLimitedValue() >=
1087         Op0->getType()->getScalarSizeInBits())
1088       return UndefValue::get(Op0->getType());
1089
1090   // If the operation is with the result of a select instruction, check whether
1091   // operating on either branch of the select always yields the same value.
1092   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1093     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, DT, MaxRecurse))
1094       return V;
1095
1096   // If the operation is with the result of a phi instruction, check whether
1097   // operating on all incoming values of the phi always yields the same value.
1098   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1099     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, DT, MaxRecurse))
1100       return V;
1101
1102   return 0;
1103 }
1104
1105 /// SimplifyShlInst - Given operands for an Shl, see if we can
1106 /// fold the result.  If not, this returns null.
1107 static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1108                               const TargetData *TD, const DominatorTree *DT,
1109                               unsigned MaxRecurse) {
1110   if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, TD, DT, MaxRecurse))
1111     return V;
1112
1113   // undef << X -> 0
1114   if (match(Op0, m_Undef()))
1115     return Constant::getNullValue(Op0->getType());
1116
1117   // (X >> A) << A -> X
1118   Value *X;
1119   if (match(Op0, m_Shr(m_Value(X), m_Specific(Op1))) &&
1120       cast<PossiblyExactOperator>(Op0)->isExact())
1121     return X;
1122   return 0;
1123 }
1124
1125 Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1126                              const TargetData *TD, const DominatorTree *DT) {
1127   return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit);
1128 }
1129
1130 /// SimplifyLShrInst - Given operands for an LShr, see if we can
1131 /// fold the result.  If not, this returns null.
1132 static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1133                                const TargetData *TD, const DominatorTree *DT,
1134                                unsigned MaxRecurse) {
1135   if (Value *V = SimplifyShift(Instruction::LShr, Op0, Op1, TD, DT, MaxRecurse))
1136     return V;
1137
1138   // undef >>l X -> 0
1139   if (match(Op0, m_Undef()))
1140     return Constant::getNullValue(Op0->getType());
1141
1142   // (X << A) >> A -> X
1143   Value *X;
1144   if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) &&
1145       cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap())
1146     return X;
1147
1148   return 0;
1149 }
1150
1151 Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1152                               const TargetData *TD, const DominatorTree *DT) {
1153   return ::SimplifyLShrInst(Op0, Op1, isExact, TD, DT, RecursionLimit);
1154 }
1155
1156 /// SimplifyAShrInst - Given operands for an AShr, see if we can
1157 /// fold the result.  If not, this returns null.
1158 static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1159                                const TargetData *TD, const DominatorTree *DT,
1160                                unsigned MaxRecurse) {
1161   if (Value *V = SimplifyShift(Instruction::AShr, Op0, Op1, TD, DT, MaxRecurse))
1162     return V;
1163
1164   // all ones >>a X -> all ones
1165   if (match(Op0, m_AllOnes()))
1166     return Op0;
1167
1168   // undef >>a X -> all ones
1169   if (match(Op0, m_Undef()))
1170     return Constant::getAllOnesValue(Op0->getType());
1171
1172   // (X << A) >> A -> X
1173   Value *X;
1174   if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) &&
1175       cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap())
1176     return X;
1177
1178   return 0;
1179 }
1180
1181 Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1182                               const TargetData *TD, const DominatorTree *DT) {
1183   return ::SimplifyAShrInst(Op0, Op1, isExact, TD, DT, RecursionLimit);
1184 }
1185
1186 /// SimplifyAndInst - Given operands for an And, see if we can
1187 /// fold the result.  If not, this returns null.
1188 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
1189                               const DominatorTree *DT, unsigned MaxRecurse) {
1190   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
1191     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
1192       Constant *Ops[] = { CLHS, CRHS };
1193       return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
1194                                       Ops, TD);
1195     }
1196
1197     // Canonicalize the constant to the RHS.
1198     std::swap(Op0, Op1);
1199   }
1200
1201   // X & undef -> 0
1202   if (match(Op1, m_Undef()))
1203     return Constant::getNullValue(Op0->getType());
1204
1205   // X & X = X
1206   if (Op0 == Op1)
1207     return Op0;
1208
1209   // X & 0 = 0
1210   if (match(Op1, m_Zero()))
1211     return Op1;
1212
1213   // X & -1 = X
1214   if (match(Op1, m_AllOnes()))
1215     return Op0;
1216
1217   // A & ~A  =  ~A & A  =  0
1218   if (match(Op0, m_Not(m_Specific(Op1))) ||
1219       match(Op1, m_Not(m_Specific(Op0))))
1220     return Constant::getNullValue(Op0->getType());
1221
1222   // (A | ?) & A = A
1223   Value *A = 0, *B = 0;
1224   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
1225       (A == Op1 || B == Op1))
1226     return Op1;
1227
1228   // A & (A | ?) = A
1229   if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
1230       (A == Op0 || B == Op0))
1231     return Op0;
1232
1233   // A & (-A) = A if A is a power of two or zero.
1234   if (match(Op0, m_Neg(m_Specific(Op1))) ||
1235       match(Op1, m_Neg(m_Specific(Op0)))) {
1236     if (isPowerOfTwo(Op0, TD, /*OrZero*/true))
1237       return Op0;
1238     if (isPowerOfTwo(Op1, TD, /*OrZero*/true))
1239       return Op1;
1240   }
1241
1242   // Try some generic simplifications for associative operations.
1243   if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, DT,
1244                                           MaxRecurse))
1245     return V;
1246
1247   // And distributes over Or.  Try some generic simplifications based on this.
1248   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
1249                              TD, DT, MaxRecurse))
1250     return V;
1251
1252   // And distributes over Xor.  Try some generic simplifications based on this.
1253   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor,
1254                              TD, DT, MaxRecurse))
1255     return V;
1256
1257   // Or distributes over And.  Try some generic simplifications based on this.
1258   if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or,
1259                                 TD, DT, MaxRecurse))
1260     return V;
1261
1262   // If the operation is with the result of a select instruction, check whether
1263   // operating on either branch of the select always yields the same value.
1264   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1265     if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT,
1266                                          MaxRecurse))
1267       return V;
1268
1269   // If the operation is with the result of a phi instruction, check whether
1270   // operating on all incoming values of the phi always yields the same value.
1271   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1272     if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT,
1273                                       MaxRecurse))
1274       return V;
1275
1276   return 0;
1277 }
1278
1279 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
1280                              const DominatorTree *DT) {
1281   return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit);
1282 }
1283
1284 /// SimplifyOrInst - Given operands for an Or, see if we can
1285 /// fold the result.  If not, this returns null.
1286 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
1287                              const DominatorTree *DT, unsigned MaxRecurse) {
1288   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
1289     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
1290       Constant *Ops[] = { CLHS, CRHS };
1291       return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
1292                                       Ops, TD);
1293     }
1294
1295     // Canonicalize the constant to the RHS.
1296     std::swap(Op0, Op1);
1297   }
1298
1299   // X | undef -> -1
1300   if (match(Op1, m_Undef()))
1301     return Constant::getAllOnesValue(Op0->getType());
1302
1303   // X | X = X
1304   if (Op0 == Op1)
1305     return Op0;
1306
1307   // X | 0 = X
1308   if (match(Op1, m_Zero()))
1309     return Op0;
1310
1311   // X | -1 = -1
1312   if (match(Op1, m_AllOnes()))
1313     return Op1;
1314
1315   // A | ~A  =  ~A | A  =  -1
1316   if (match(Op0, m_Not(m_Specific(Op1))) ||
1317       match(Op1, m_Not(m_Specific(Op0))))
1318     return Constant::getAllOnesValue(Op0->getType());
1319
1320   // (A & ?) | A = A
1321   Value *A = 0, *B = 0;
1322   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1323       (A == Op1 || B == Op1))
1324     return Op1;
1325
1326   // A | (A & ?) = A
1327   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
1328       (A == Op0 || B == Op0))
1329     return Op0;
1330
1331   // ~(A & ?) | A = -1
1332   if (match(Op0, m_Not(m_And(m_Value(A), m_Value(B)))) &&
1333       (A == Op1 || B == Op1))
1334     return Constant::getAllOnesValue(Op1->getType());
1335
1336   // A | ~(A & ?) = -1
1337   if (match(Op1, m_Not(m_And(m_Value(A), m_Value(B)))) &&
1338       (A == Op0 || B == Op0))
1339     return Constant::getAllOnesValue(Op0->getType());
1340
1341   // Try some generic simplifications for associative operations.
1342   if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, DT,
1343                                           MaxRecurse))
1344     return V;
1345
1346   // Or distributes over And.  Try some generic simplifications based on this.
1347   if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And,
1348                              TD, DT, MaxRecurse))
1349     return V;
1350
1351   // And distributes over Or.  Try some generic simplifications based on this.
1352   if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And,
1353                                 TD, DT, MaxRecurse))
1354     return V;
1355
1356   // If the operation is with the result of a select instruction, check whether
1357   // operating on either branch of the select always yields the same value.
1358   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1359     if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT,
1360                                          MaxRecurse))
1361       return V;
1362
1363   // If the operation is with the result of a phi instruction, check whether
1364   // operating on all incoming values of the phi always yields the same value.
1365   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1366     if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT,
1367                                       MaxRecurse))
1368       return V;
1369
1370   return 0;
1371 }
1372
1373 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
1374                             const DominatorTree *DT) {
1375   return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit);
1376 }
1377
1378 /// SimplifyXorInst - Given operands for a Xor, see if we can
1379 /// fold the result.  If not, this returns null.
1380 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
1381                               const DominatorTree *DT, unsigned MaxRecurse) {
1382   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
1383     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
1384       Constant *Ops[] = { CLHS, CRHS };
1385       return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
1386                                       Ops, TD);
1387     }
1388
1389     // Canonicalize the constant to the RHS.
1390     std::swap(Op0, Op1);
1391   }
1392
1393   // A ^ undef -> undef
1394   if (match(Op1, m_Undef()))
1395     return Op1;
1396
1397   // A ^ 0 = A
1398   if (match(Op1, m_Zero()))
1399     return Op0;
1400
1401   // A ^ A = 0
1402   if (Op0 == Op1)
1403     return Constant::getNullValue(Op0->getType());
1404
1405   // A ^ ~A  =  ~A ^ A  =  -1
1406   if (match(Op0, m_Not(m_Specific(Op1))) ||
1407       match(Op1, m_Not(m_Specific(Op0))))
1408     return Constant::getAllOnesValue(Op0->getType());
1409
1410   // Try some generic simplifications for associative operations.
1411   if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, DT,
1412                                           MaxRecurse))
1413     return V;
1414
1415   // And distributes over Xor.  Try some generic simplifications based on this.
1416   if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And,
1417                                 TD, DT, MaxRecurse))
1418     return V;
1419
1420   // Threading Xor over selects and phi nodes is pointless, so don't bother.
1421   // Threading over the select in "A ^ select(cond, B, C)" means evaluating
1422   // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
1423   // only if B and C are equal.  If B and C are equal then (since we assume
1424   // that operands have already been simplified) "select(cond, B, C)" should
1425   // have been simplified to the common value of B and C already.  Analysing
1426   // "A^B" and "A^C" thus gains nothing, but costs compile time.  Similarly
1427   // for threading over phi nodes.
1428
1429   return 0;
1430 }
1431
1432 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
1433                              const DominatorTree *DT) {
1434   return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit);
1435 }
1436
1437 static Type *GetCompareTy(Value *Op) {
1438   return CmpInst::makeCmpResultType(Op->getType());
1439 }
1440
1441 /// ExtractEquivalentCondition - Rummage around inside V looking for something
1442 /// equivalent to the comparison "LHS Pred RHS".  Return such a value if found,
1443 /// otherwise return null.  Helper function for analyzing max/min idioms.
1444 static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred,
1445                                          Value *LHS, Value *RHS) {
1446   SelectInst *SI = dyn_cast<SelectInst>(V);
1447   if (!SI)
1448     return 0;
1449   CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
1450   if (!Cmp)
1451     return 0;
1452   Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1);
1453   if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS)
1454     return Cmp;
1455   if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) &&
1456       LHS == CmpRHS && RHS == CmpLHS)
1457     return Cmp;
1458   return 0;
1459 }
1460
1461 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
1462 /// fold the result.  If not, this returns null.
1463 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1464                                const TargetData *TD, const DominatorTree *DT,
1465                                unsigned MaxRecurse) {
1466   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
1467   assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
1468
1469   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
1470     if (Constant *CRHS = dyn_cast<Constant>(RHS))
1471       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
1472
1473     // If we have a constant, make sure it is on the RHS.
1474     std::swap(LHS, RHS);
1475     Pred = CmpInst::getSwappedPredicate(Pred);
1476   }
1477
1478   Type *ITy = GetCompareTy(LHS); // The return type.
1479   Type *OpTy = LHS->getType();   // The operand type.
1480
1481   // icmp X, X -> true/false
1482   // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
1483   // because X could be 0.
1484   if (LHS == RHS || isa<UndefValue>(RHS))
1485     return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
1486
1487   // Special case logic when the operands have i1 type.
1488   if (OpTy->getScalarType()->isIntegerTy(1)) {
1489     switch (Pred) {
1490     default: break;
1491     case ICmpInst::ICMP_EQ:
1492       // X == 1 -> X
1493       if (match(RHS, m_One()))
1494         return LHS;
1495       break;
1496     case ICmpInst::ICMP_NE:
1497       // X != 0 -> X
1498       if (match(RHS, m_Zero()))
1499         return LHS;
1500       break;
1501     case ICmpInst::ICMP_UGT:
1502       // X >u 0 -> X
1503       if (match(RHS, m_Zero()))
1504         return LHS;
1505       break;
1506     case ICmpInst::ICMP_UGE:
1507       // X >=u 1 -> X
1508       if (match(RHS, m_One()))
1509         return LHS;
1510       break;
1511     case ICmpInst::ICMP_SLT:
1512       // X <s 0 -> X
1513       if (match(RHS, m_Zero()))
1514         return LHS;
1515       break;
1516     case ICmpInst::ICMP_SLE:
1517       // X <=s -1 -> X
1518       if (match(RHS, m_One()))
1519         return LHS;
1520       break;
1521     }
1522   }
1523
1524   // icmp <alloca*>, <global/alloca*/null> - Different stack variables have
1525   // different addresses, and what's more the address of a stack variable is
1526   // never null or equal to the address of a global.  Note that generalizing
1527   // to the case where LHS is a global variable address or null is pointless,
1528   // since if both LHS and RHS are constants then we already constant folded
1529   // the compare, and if only one of them is then we moved it to RHS already.
1530   if (isa<AllocaInst>(LHS) && (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
1531                                isa<ConstantPointerNull>(RHS)))
1532     // We already know that LHS != RHS.
1533     return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
1534
1535   // If we are comparing with zero then try hard since this is a common case.
1536   if (match(RHS, m_Zero())) {
1537     bool LHSKnownNonNegative, LHSKnownNegative;
1538     switch (Pred) {
1539     default:
1540       assert(false && "Unknown ICmp predicate!");
1541     case ICmpInst::ICMP_ULT:
1542       return getFalse(ITy);
1543     case ICmpInst::ICMP_UGE:
1544       return getTrue(ITy);
1545     case ICmpInst::ICMP_EQ:
1546     case ICmpInst::ICMP_ULE:
1547       if (isKnownNonZero(LHS, TD))
1548         return getFalse(ITy);
1549       break;
1550     case ICmpInst::ICMP_NE:
1551     case ICmpInst::ICMP_UGT:
1552       if (isKnownNonZero(LHS, TD))
1553         return getTrue(ITy);
1554       break;
1555     case ICmpInst::ICMP_SLT:
1556       ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD);
1557       if (LHSKnownNegative)
1558         return getTrue(ITy);
1559       if (LHSKnownNonNegative)
1560         return getFalse(ITy);
1561       break;
1562     case ICmpInst::ICMP_SLE:
1563       ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD);
1564       if (LHSKnownNegative)
1565         return getTrue(ITy);
1566       if (LHSKnownNonNegative && isKnownNonZero(LHS, TD))
1567         return getFalse(ITy);
1568       break;
1569     case ICmpInst::ICMP_SGE:
1570       ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD);
1571       if (LHSKnownNegative)
1572         return getFalse(ITy);
1573       if (LHSKnownNonNegative)
1574         return getTrue(ITy);
1575       break;
1576     case ICmpInst::ICMP_SGT:
1577       ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD);
1578       if (LHSKnownNegative)
1579         return getFalse(ITy);
1580       if (LHSKnownNonNegative && isKnownNonZero(LHS, TD))
1581         return getTrue(ITy);
1582       break;
1583     }
1584   }
1585
1586   // See if we are doing a comparison with a constant integer.
1587   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
1588     // Rule out tautological comparisons (eg., ult 0 or uge 0).
1589     ConstantRange RHS_CR = ICmpInst::makeConstantRange(Pred, CI->getValue());
1590     if (RHS_CR.isEmptySet())
1591       return ConstantInt::getFalse(CI->getContext());
1592     if (RHS_CR.isFullSet())
1593       return ConstantInt::getTrue(CI->getContext());
1594
1595     // Many binary operators with constant RHS have easy to compute constant
1596     // range.  Use them to check whether the comparison is a tautology.
1597     uint32_t Width = CI->getBitWidth();
1598     APInt Lower = APInt(Width, 0);
1599     APInt Upper = APInt(Width, 0);
1600     ConstantInt *CI2;
1601     if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) {
1602       // 'urem x, CI2' produces [0, CI2).
1603       Upper = CI2->getValue();
1604     } else if (match(LHS, m_SRem(m_Value(), m_ConstantInt(CI2)))) {
1605       // 'srem x, CI2' produces (-|CI2|, |CI2|).
1606       Upper = CI2->getValue().abs();
1607       Lower = (-Upper) + 1;
1608     } else if (match(LHS, m_UDiv(m_ConstantInt(CI2), m_Value()))) {
1609       // 'udiv CI2, x' produces [0, CI2].
1610       Upper = CI2->getValue() + 1;
1611     } else if (match(LHS, m_UDiv(m_Value(), m_ConstantInt(CI2)))) {
1612       // 'udiv x, CI2' produces [0, UINT_MAX / CI2].
1613       APInt NegOne = APInt::getAllOnesValue(Width);
1614       if (!CI2->isZero())
1615         Upper = NegOne.udiv(CI2->getValue()) + 1;
1616     } else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) {
1617       // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2].
1618       APInt IntMin = APInt::getSignedMinValue(Width);
1619       APInt IntMax = APInt::getSignedMaxValue(Width);
1620       APInt Val = CI2->getValue().abs();
1621       if (!Val.isMinValue()) {
1622         Lower = IntMin.sdiv(Val);
1623         Upper = IntMax.sdiv(Val) + 1;
1624       }
1625     } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) {
1626       // 'lshr x, CI2' produces [0, UINT_MAX >> CI2].
1627       APInt NegOne = APInt::getAllOnesValue(Width);
1628       if (CI2->getValue().ult(Width))
1629         Upper = NegOne.lshr(CI2->getValue()) + 1;
1630     } else if (match(LHS, m_AShr(m_Value(), m_ConstantInt(CI2)))) {
1631       // 'ashr x, CI2' produces [INT_MIN >> CI2, INT_MAX >> CI2].
1632       APInt IntMin = APInt::getSignedMinValue(Width);
1633       APInt IntMax = APInt::getSignedMaxValue(Width);
1634       if (CI2->getValue().ult(Width)) {
1635         Lower = IntMin.ashr(CI2->getValue());
1636         Upper = IntMax.ashr(CI2->getValue()) + 1;
1637       }
1638     } else if (match(LHS, m_Or(m_Value(), m_ConstantInt(CI2)))) {
1639       // 'or x, CI2' produces [CI2, UINT_MAX].
1640       Lower = CI2->getValue();
1641     } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) {
1642       // 'and x, CI2' produces [0, CI2].
1643       Upper = CI2->getValue() + 1;
1644     }
1645     if (Lower != Upper) {
1646       ConstantRange LHS_CR = ConstantRange(Lower, Upper);
1647       if (RHS_CR.contains(LHS_CR))
1648         return ConstantInt::getTrue(RHS->getContext());
1649       if (RHS_CR.inverse().contains(LHS_CR))
1650         return ConstantInt::getFalse(RHS->getContext());
1651     }
1652   }
1653
1654   // Compare of cast, for example (zext X) != 0 -> X != 0
1655   if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) {
1656     Instruction *LI = cast<CastInst>(LHS);
1657     Value *SrcOp = LI->getOperand(0);
1658     Type *SrcTy = SrcOp->getType();
1659     Type *DstTy = LI->getType();
1660
1661     // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input
1662     // if the integer type is the same size as the pointer type.
1663     if (MaxRecurse && TD && isa<PtrToIntInst>(LI) &&
1664         TD->getPointerSizeInBits() == DstTy->getPrimitiveSizeInBits()) {
1665       if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
1666         // Transfer the cast to the constant.
1667         if (Value *V = SimplifyICmpInst(Pred, SrcOp,
1668                                         ConstantExpr::getIntToPtr(RHSC, SrcTy),
1669                                         TD, DT, MaxRecurse-1))
1670           return V;
1671       } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) {
1672         if (RI->getOperand(0)->getType() == SrcTy)
1673           // Compare without the cast.
1674           if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
1675                                           TD, DT, MaxRecurse-1))
1676             return V;
1677       }
1678     }
1679
1680     if (isa<ZExtInst>(LHS)) {
1681       // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the
1682       // same type.
1683       if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
1684         if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
1685           // Compare X and Y.  Note that signed predicates become unsigned.
1686           if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
1687                                           SrcOp, RI->getOperand(0), TD, DT,
1688                                           MaxRecurse-1))
1689             return V;
1690       }
1691       // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended
1692       // too.  If not, then try to deduce the result of the comparison.
1693       else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
1694         // Compute the constant that would happen if we truncated to SrcTy then
1695         // reextended to DstTy.
1696         Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
1697         Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy);
1698
1699         // If the re-extended constant didn't change then this is effectively
1700         // also a case of comparing two zero-extended values.
1701         if (RExt == CI && MaxRecurse)
1702           if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
1703                                           SrcOp, Trunc, TD, DT, MaxRecurse-1))
1704             return V;
1705
1706         // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit
1707         // there.  Use this to work out the result of the comparison.
1708         if (RExt != CI) {
1709           switch (Pred) {
1710           default:
1711             assert(false && "Unknown ICmp predicate!");
1712           // LHS <u RHS.
1713           case ICmpInst::ICMP_EQ:
1714           case ICmpInst::ICMP_UGT:
1715           case ICmpInst::ICMP_UGE:
1716             return ConstantInt::getFalse(CI->getContext());
1717
1718           case ICmpInst::ICMP_NE:
1719           case ICmpInst::ICMP_ULT:
1720           case ICmpInst::ICMP_ULE:
1721             return ConstantInt::getTrue(CI->getContext());
1722
1723           // LHS is non-negative.  If RHS is negative then LHS >s LHS.  If RHS
1724           // is non-negative then LHS <s RHS.
1725           case ICmpInst::ICMP_SGT:
1726           case ICmpInst::ICMP_SGE:
1727             return CI->getValue().isNegative() ?
1728               ConstantInt::getTrue(CI->getContext()) :
1729               ConstantInt::getFalse(CI->getContext());
1730
1731           case ICmpInst::ICMP_SLT:
1732           case ICmpInst::ICMP_SLE:
1733             return CI->getValue().isNegative() ?
1734               ConstantInt::getFalse(CI->getContext()) :
1735               ConstantInt::getTrue(CI->getContext());
1736           }
1737         }
1738       }
1739     }
1740
1741     if (isa<SExtInst>(LHS)) {
1742       // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the
1743       // same type.
1744       if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
1745         if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
1746           // Compare X and Y.  Note that the predicate does not change.
1747           if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
1748                                           TD, DT, MaxRecurse-1))
1749             return V;
1750       }
1751       // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended
1752       // too.  If not, then try to deduce the result of the comparison.
1753       else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
1754         // Compute the constant that would happen if we truncated to SrcTy then
1755         // reextended to DstTy.
1756         Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
1757         Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy);
1758
1759         // If the re-extended constant didn't change then this is effectively
1760         // also a case of comparing two sign-extended values.
1761         if (RExt == CI && MaxRecurse)
1762           if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, TD, DT,
1763                                           MaxRecurse-1))
1764             return V;
1765
1766         // Otherwise the upper bits of LHS are all equal, while RHS has varying
1767         // bits there.  Use this to work out the result of the comparison.
1768         if (RExt != CI) {
1769           switch (Pred) {
1770           default:
1771             assert(false && "Unknown ICmp predicate!");
1772           case ICmpInst::ICMP_EQ:
1773             return ConstantInt::getFalse(CI->getContext());
1774           case ICmpInst::ICMP_NE:
1775             return ConstantInt::getTrue(CI->getContext());
1776
1777           // If RHS is non-negative then LHS <s RHS.  If RHS is negative then
1778           // LHS >s RHS.
1779           case ICmpInst::ICMP_SGT:
1780           case ICmpInst::ICMP_SGE:
1781             return CI->getValue().isNegative() ?
1782               ConstantInt::getTrue(CI->getContext()) :
1783               ConstantInt::getFalse(CI->getContext());
1784           case ICmpInst::ICMP_SLT:
1785           case ICmpInst::ICMP_SLE:
1786             return CI->getValue().isNegative() ?
1787               ConstantInt::getFalse(CI->getContext()) :
1788               ConstantInt::getTrue(CI->getContext());
1789
1790           // If LHS is non-negative then LHS <u RHS.  If LHS is negative then
1791           // LHS >u RHS.
1792           case ICmpInst::ICMP_UGT:
1793           case ICmpInst::ICMP_UGE:
1794             // Comparison is true iff the LHS <s 0.
1795             if (MaxRecurse)
1796               if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp,
1797                                               Constant::getNullValue(SrcTy),
1798                                               TD, DT, MaxRecurse-1))
1799                 return V;
1800             break;
1801           case ICmpInst::ICMP_ULT:
1802           case ICmpInst::ICMP_ULE:
1803             // Comparison is true iff the LHS >=s 0.
1804             if (MaxRecurse)
1805               if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp,
1806                                               Constant::getNullValue(SrcTy),
1807                                               TD, DT, MaxRecurse-1))
1808                 return V;
1809             break;
1810           }
1811         }
1812       }
1813     }
1814   }
1815
1816   // Special logic for binary operators.
1817   BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS);
1818   BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS);
1819   if (MaxRecurse && (LBO || RBO)) {
1820     // Analyze the case when either LHS or RHS is an add instruction.
1821     Value *A = 0, *B = 0, *C = 0, *D = 0;
1822     // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null).
1823     bool NoLHSWrapProblem = false, NoRHSWrapProblem = false;
1824     if (LBO && LBO->getOpcode() == Instruction::Add) {
1825       A = LBO->getOperand(0); B = LBO->getOperand(1);
1826       NoLHSWrapProblem = ICmpInst::isEquality(Pred) ||
1827         (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) ||
1828         (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap());
1829     }
1830     if (RBO && RBO->getOpcode() == Instruction::Add) {
1831       C = RBO->getOperand(0); D = RBO->getOperand(1);
1832       NoRHSWrapProblem = ICmpInst::isEquality(Pred) ||
1833         (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) ||
1834         (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap());
1835     }
1836
1837     // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow.
1838     if ((A == RHS || B == RHS) && NoLHSWrapProblem)
1839       if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A,
1840                                       Constant::getNullValue(RHS->getType()),
1841                                       TD, DT, MaxRecurse-1))
1842         return V;
1843
1844     // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow.
1845     if ((C == LHS || D == LHS) && NoRHSWrapProblem)
1846       if (Value *V = SimplifyICmpInst(Pred,
1847                                       Constant::getNullValue(LHS->getType()),
1848                                       C == LHS ? D : C, TD, DT, MaxRecurse-1))
1849         return V;
1850
1851     // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow.
1852     if (A && C && (A == C || A == D || B == C || B == D) &&
1853         NoLHSWrapProblem && NoRHSWrapProblem) {
1854       // Determine Y and Z in the form icmp (X+Y), (X+Z).
1855       Value *Y = (A == C || A == D) ? B : A;
1856       Value *Z = (C == A || C == B) ? D : C;
1857       if (Value *V = SimplifyICmpInst(Pred, Y, Z, TD, DT, MaxRecurse-1))
1858         return V;
1859     }
1860   }
1861
1862   if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) {
1863     bool KnownNonNegative, KnownNegative;
1864     switch (Pred) {
1865     default:
1866       break;
1867     case ICmpInst::ICMP_SGT:
1868     case ICmpInst::ICMP_SGE:
1869       ComputeSignBit(LHS, KnownNonNegative, KnownNegative, TD);
1870       if (!KnownNonNegative)
1871         break;
1872       // fall-through
1873     case ICmpInst::ICMP_EQ:
1874     case ICmpInst::ICMP_UGT:
1875     case ICmpInst::ICMP_UGE:
1876       return getFalse(ITy);
1877     case ICmpInst::ICMP_SLT:
1878     case ICmpInst::ICMP_SLE:
1879       ComputeSignBit(LHS, KnownNonNegative, KnownNegative, TD);
1880       if (!KnownNonNegative)
1881         break;
1882       // fall-through
1883     case ICmpInst::ICMP_NE:
1884     case ICmpInst::ICMP_ULT:
1885     case ICmpInst::ICMP_ULE:
1886       return getTrue(ITy);
1887     }
1888   }
1889   if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) {
1890     bool KnownNonNegative, KnownNegative;
1891     switch (Pred) {
1892     default:
1893       break;
1894     case ICmpInst::ICMP_SGT:
1895     case ICmpInst::ICMP_SGE:
1896       ComputeSignBit(RHS, KnownNonNegative, KnownNegative, TD);
1897       if (!KnownNonNegative)
1898         break;
1899       // fall-through
1900     case ICmpInst::ICMP_NE:
1901     case ICmpInst::ICMP_UGT:
1902     case ICmpInst::ICMP_UGE:
1903       return getTrue(ITy);
1904     case ICmpInst::ICMP_SLT:
1905     case ICmpInst::ICMP_SLE:
1906       ComputeSignBit(RHS, KnownNonNegative, KnownNegative, TD);
1907       if (!KnownNonNegative)
1908         break;
1909       // fall-through
1910     case ICmpInst::ICMP_EQ:
1911     case ICmpInst::ICMP_ULT:
1912     case ICmpInst::ICMP_ULE:
1913       return getFalse(ITy);
1914     }
1915   }
1916
1917   // x udiv y <=u x.
1918   if (LBO && match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) {
1919     // icmp pred (X /u Y), X
1920     if (Pred == ICmpInst::ICMP_UGT)
1921       return getFalse(ITy);
1922     if (Pred == ICmpInst::ICMP_ULE)
1923       return getTrue(ITy);
1924   }
1925
1926   if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() &&
1927       LBO->getOperand(1) == RBO->getOperand(1)) {
1928     switch (LBO->getOpcode()) {
1929     default: break;
1930     case Instruction::UDiv:
1931     case Instruction::LShr:
1932       if (ICmpInst::isSigned(Pred))
1933         break;
1934       // fall-through
1935     case Instruction::SDiv:
1936     case Instruction::AShr:
1937       if (!LBO->isExact() || !RBO->isExact())
1938         break;
1939       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
1940                                       RBO->getOperand(0), TD, DT, MaxRecurse-1))
1941         return V;
1942       break;
1943     case Instruction::Shl: {
1944       bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap();
1945       bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap();
1946       if (!NUW && !NSW)
1947         break;
1948       if (!NSW && ICmpInst::isSigned(Pred))
1949         break;
1950       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
1951                                       RBO->getOperand(0), TD, DT, MaxRecurse-1))
1952         return V;
1953       break;
1954     }
1955     }
1956   }
1957
1958   // Simplify comparisons involving max/min.
1959   Value *A, *B;
1960   CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE;
1961   CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B".
1962
1963   // Signed variants on "max(a,b)>=a -> true".
1964   if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
1965     if (A != RHS) std::swap(A, B); // smax(A, B) pred A.
1966     EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
1967     // We analyze this as smax(A, B) pred A.
1968     P = Pred;
1969   } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) &&
1970              (A == LHS || B == LHS)) {
1971     if (A != LHS) std::swap(A, B); // A pred smax(A, B).
1972     EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
1973     // We analyze this as smax(A, B) swapped-pred A.
1974     P = CmpInst::getSwappedPredicate(Pred);
1975   } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
1976              (A == RHS || B == RHS)) {
1977     if (A != RHS) std::swap(A, B); // smin(A, B) pred A.
1978     EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
1979     // We analyze this as smax(-A, -B) swapped-pred -A.
1980     // Note that we do not need to actually form -A or -B thanks to EqP.
1981     P = CmpInst::getSwappedPredicate(Pred);
1982   } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) &&
1983              (A == LHS || B == LHS)) {
1984     if (A != LHS) std::swap(A, B); // A pred smin(A, B).
1985     EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
1986     // We analyze this as smax(-A, -B) pred -A.
1987     // Note that we do not need to actually form -A or -B thanks to EqP.
1988     P = Pred;
1989   }
1990   if (P != CmpInst::BAD_ICMP_PREDICATE) {
1991     // Cases correspond to "max(A, B) p A".
1992     switch (P) {
1993     default:
1994       break;
1995     case CmpInst::ICMP_EQ:
1996     case CmpInst::ICMP_SLE:
1997       // Equivalent to "A EqP B".  This may be the same as the condition tested
1998       // in the max/min; if so, we can just return that.
1999       if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
2000         return V;
2001       if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
2002         return V;
2003       // Otherwise, see if "A EqP B" simplifies.
2004       if (MaxRecurse)
2005         if (Value *V = SimplifyICmpInst(EqP, A, B, TD, DT, MaxRecurse-1))
2006           return V;
2007       break;
2008     case CmpInst::ICMP_NE:
2009     case CmpInst::ICMP_SGT: {
2010       CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
2011       // Equivalent to "A InvEqP B".  This may be the same as the condition
2012       // tested in the max/min; if so, we can just return that.
2013       if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
2014         return V;
2015       if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
2016         return V;
2017       // Otherwise, see if "A InvEqP B" simplifies.
2018       if (MaxRecurse)
2019         if (Value *V = SimplifyICmpInst(InvEqP, A, B, TD, DT, MaxRecurse-1))
2020           return V;
2021       break;
2022     }
2023     case CmpInst::ICMP_SGE:
2024       // Always true.
2025       return getTrue(ITy);
2026     case CmpInst::ICMP_SLT:
2027       // Always false.
2028       return getFalse(ITy);
2029     }
2030   }
2031
2032   // Unsigned variants on "max(a,b)>=a -> true".
2033   P = CmpInst::BAD_ICMP_PREDICATE;
2034   if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
2035     if (A != RHS) std::swap(A, B); // umax(A, B) pred A.
2036     EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
2037     // We analyze this as umax(A, B) pred A.
2038     P = Pred;
2039   } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) &&
2040              (A == LHS || B == LHS)) {
2041     if (A != LHS) std::swap(A, B); // A pred umax(A, B).
2042     EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
2043     // We analyze this as umax(A, B) swapped-pred A.
2044     P = CmpInst::getSwappedPredicate(Pred);
2045   } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
2046              (A == RHS || B == RHS)) {
2047     if (A != RHS) std::swap(A, B); // umin(A, B) pred A.
2048     EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
2049     // We analyze this as umax(-A, -B) swapped-pred -A.
2050     // Note that we do not need to actually form -A or -B thanks to EqP.
2051     P = CmpInst::getSwappedPredicate(Pred);
2052   } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) &&
2053              (A == LHS || B == LHS)) {
2054     if (A != LHS) std::swap(A, B); // A pred umin(A, B).
2055     EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
2056     // We analyze this as umax(-A, -B) pred -A.
2057     // Note that we do not need to actually form -A or -B thanks to EqP.
2058     P = Pred;
2059   }
2060   if (P != CmpInst::BAD_ICMP_PREDICATE) {
2061     // Cases correspond to "max(A, B) p A".
2062     switch (P) {
2063     default:
2064       break;
2065     case CmpInst::ICMP_EQ:
2066     case CmpInst::ICMP_ULE:
2067       // Equivalent to "A EqP B".  This may be the same as the condition tested
2068       // in the max/min; if so, we can just return that.
2069       if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
2070         return V;
2071       if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
2072         return V;
2073       // Otherwise, see if "A EqP B" simplifies.
2074       if (MaxRecurse)
2075         if (Value *V = SimplifyICmpInst(EqP, A, B, TD, DT, MaxRecurse-1))
2076           return V;
2077       break;
2078     case CmpInst::ICMP_NE:
2079     case CmpInst::ICMP_UGT: {
2080       CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
2081       // Equivalent to "A InvEqP B".  This may be the same as the condition
2082       // tested in the max/min; if so, we can just return that.
2083       if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
2084         return V;
2085       if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
2086         return V;
2087       // Otherwise, see if "A InvEqP B" simplifies.
2088       if (MaxRecurse)
2089         if (Value *V = SimplifyICmpInst(InvEqP, A, B, TD, DT, MaxRecurse-1))
2090           return V;
2091       break;
2092     }
2093     case CmpInst::ICMP_UGE:
2094       // Always true.
2095       return getTrue(ITy);
2096     case CmpInst::ICMP_ULT:
2097       // Always false.
2098       return getFalse(ITy);
2099     }
2100   }
2101
2102   // Variants on "max(x,y) >= min(x,z)".
2103   Value *C, *D;
2104   if (match(LHS, m_SMax(m_Value(A), m_Value(B))) &&
2105       match(RHS, m_SMin(m_Value(C), m_Value(D))) &&
2106       (A == C || A == D || B == C || B == D)) {
2107     // max(x, ?) pred min(x, ?).
2108     if (Pred == CmpInst::ICMP_SGE)
2109       // Always true.
2110       return getTrue(ITy);
2111     if (Pred == CmpInst::ICMP_SLT)
2112       // Always false.
2113       return getFalse(ITy);
2114   } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
2115              match(RHS, m_SMax(m_Value(C), m_Value(D))) &&
2116              (A == C || A == D || B == C || B == D)) {
2117     // min(x, ?) pred max(x, ?).
2118     if (Pred == CmpInst::ICMP_SLE)
2119       // Always true.
2120       return getTrue(ITy);
2121     if (Pred == CmpInst::ICMP_SGT)
2122       // Always false.
2123       return getFalse(ITy);
2124   } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) &&
2125              match(RHS, m_UMin(m_Value(C), m_Value(D))) &&
2126              (A == C || A == D || B == C || B == D)) {
2127     // max(x, ?) pred min(x, ?).
2128     if (Pred == CmpInst::ICMP_UGE)
2129       // Always true.
2130       return getTrue(ITy);
2131     if (Pred == CmpInst::ICMP_ULT)
2132       // Always false.
2133       return getFalse(ITy);
2134   } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
2135              match(RHS, m_UMax(m_Value(C), m_Value(D))) &&
2136              (A == C || A == D || B == C || B == D)) {
2137     // min(x, ?) pred max(x, ?).
2138     if (Pred == CmpInst::ICMP_ULE)
2139       // Always true.
2140       return getTrue(ITy);
2141     if (Pred == CmpInst::ICMP_UGT)
2142       // Always false.
2143       return getFalse(ITy);
2144   }
2145
2146   // If the comparison is with the result of a select instruction, check whether
2147   // comparing with either branch of the select always yields the same value.
2148   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
2149     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse))
2150       return V;
2151
2152   // If the comparison is with the result of a phi instruction, check whether
2153   // doing the compare with each incoming phi value yields a common result.
2154   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
2155     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse))
2156       return V;
2157
2158   return 0;
2159 }
2160
2161 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
2162                               const TargetData *TD, const DominatorTree *DT) {
2163   return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
2164 }
2165
2166 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
2167 /// fold the result.  If not, this returns null.
2168 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
2169                                const TargetData *TD, const DominatorTree *DT,
2170                                unsigned MaxRecurse) {
2171   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
2172   assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
2173
2174   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
2175     if (Constant *CRHS = dyn_cast<Constant>(RHS))
2176       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
2177
2178     // If we have a constant, make sure it is on the RHS.
2179     std::swap(LHS, RHS);
2180     Pred = CmpInst::getSwappedPredicate(Pred);
2181   }
2182
2183   // Fold trivial predicates.
2184   if (Pred == FCmpInst::FCMP_FALSE)
2185     return ConstantInt::get(GetCompareTy(LHS), 0);
2186   if (Pred == FCmpInst::FCMP_TRUE)
2187     return ConstantInt::get(GetCompareTy(LHS), 1);
2188
2189   if (isa<UndefValue>(RHS))                  // fcmp pred X, undef -> undef
2190     return UndefValue::get(GetCompareTy(LHS));
2191
2192   // fcmp x,x -> true/false.  Not all compares are foldable.
2193   if (LHS == RHS) {
2194     if (CmpInst::isTrueWhenEqual(Pred))
2195       return ConstantInt::get(GetCompareTy(LHS), 1);
2196     if (CmpInst::isFalseWhenEqual(Pred))
2197       return ConstantInt::get(GetCompareTy(LHS), 0);
2198   }
2199
2200   // Handle fcmp with constant RHS
2201   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
2202     // If the constant is a nan, see if we can fold the comparison based on it.
2203     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
2204       if (CFP->getValueAPF().isNaN()) {
2205         if (FCmpInst::isOrdered(Pred))   // True "if ordered and foo"
2206           return ConstantInt::getFalse(CFP->getContext());
2207         assert(FCmpInst::isUnordered(Pred) &&
2208                "Comparison must be either ordered or unordered!");
2209         // True if unordered.
2210         return ConstantInt::getTrue(CFP->getContext());
2211       }
2212       // Check whether the constant is an infinity.
2213       if (CFP->getValueAPF().isInfinity()) {
2214         if (CFP->getValueAPF().isNegative()) {
2215           switch (Pred) {
2216           case FCmpInst::FCMP_OLT:
2217             // No value is ordered and less than negative infinity.
2218             return ConstantInt::getFalse(CFP->getContext());
2219           case FCmpInst::FCMP_UGE:
2220             // All values are unordered with or at least negative infinity.
2221             return ConstantInt::getTrue(CFP->getContext());
2222           default:
2223             break;
2224           }
2225         } else {
2226           switch (Pred) {
2227           case FCmpInst::FCMP_OGT:
2228             // No value is ordered and greater than infinity.
2229             return ConstantInt::getFalse(CFP->getContext());
2230           case FCmpInst::FCMP_ULE:
2231             // All values are unordered with and at most infinity.
2232             return ConstantInt::getTrue(CFP->getContext());
2233           default:
2234             break;
2235           }
2236         }
2237       }
2238     }
2239   }
2240
2241   // If the comparison is with the result of a select instruction, check whether
2242   // comparing with either branch of the select always yields the same value.
2243   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
2244     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse))
2245       return V;
2246
2247   // If the comparison is with the result of a phi instruction, check whether
2248   // doing the compare with each incoming phi value yields a common result.
2249   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
2250     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse))
2251       return V;
2252
2253   return 0;
2254 }
2255
2256 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
2257                               const TargetData *TD, const DominatorTree *DT) {
2258   return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
2259 }
2260
2261 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
2262 /// the result.  If not, this returns null.
2263 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
2264                                 const TargetData *TD, const DominatorTree *) {
2265   // select true, X, Y  -> X
2266   // select false, X, Y -> Y
2267   if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
2268     return CB->getZExtValue() ? TrueVal : FalseVal;
2269
2270   // select C, X, X -> X
2271   if (TrueVal == FalseVal)
2272     return TrueVal;
2273
2274   if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
2275     if (isa<Constant>(TrueVal))
2276       return TrueVal;
2277     return FalseVal;
2278   }
2279   if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
2280     return FalseVal;
2281   if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
2282     return TrueVal;
2283
2284   return 0;
2285 }
2286
2287 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
2288 /// fold the result.  If not, this returns null.
2289 Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops,
2290                              const TargetData *TD, const DominatorTree *) {
2291   // The type of the GEP pointer operand.
2292   PointerType *PtrTy = cast<PointerType>(Ops[0]->getType());
2293
2294   // getelementptr P -> P.
2295   if (Ops.size() == 1)
2296     return Ops[0];
2297
2298   if (isa<UndefValue>(Ops[0])) {
2299     // Compute the (pointer) type returned by the GEP instruction.
2300     Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, Ops.slice(1));
2301     Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace());
2302     return UndefValue::get(GEPTy);
2303   }
2304
2305   if (Ops.size() == 2) {
2306     // getelementptr P, 0 -> P.
2307     if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
2308       if (C->isZero())
2309         return Ops[0];
2310     // getelementptr P, N -> P if P points to a type of zero size.
2311     if (TD) {
2312       Type *Ty = PtrTy->getElementType();
2313       if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0)
2314         return Ops[0];
2315     }
2316   }
2317
2318   // Check to see if this is constant foldable.
2319   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
2320     if (!isa<Constant>(Ops[i]))
2321       return 0;
2322
2323   return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), Ops.slice(1));
2324 }
2325
2326 /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we
2327 /// can fold the result.  If not, this returns null.
2328 Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val,
2329                                      ArrayRef<unsigned> Idxs,
2330                                      const TargetData *,
2331                                      const DominatorTree *) {
2332   if (Constant *CAgg = dyn_cast<Constant>(Agg))
2333     if (Constant *CVal = dyn_cast<Constant>(Val))
2334       return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs);
2335
2336   // insertvalue x, undef, n -> x
2337   if (match(Val, m_Undef()))
2338     return Agg;
2339
2340   // insertvalue x, (extractvalue y, n), n
2341   if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val))
2342     if (EV->getAggregateOperand()->getType() == Agg->getType() &&
2343         EV->getIndices() == Idxs) {
2344       // insertvalue undef, (extractvalue y, n), n -> y
2345       if (match(Agg, m_Undef()))
2346         return EV->getAggregateOperand();
2347
2348       // insertvalue y, (extractvalue y, n), n -> y
2349       if (Agg == EV->getAggregateOperand())
2350         return Agg;
2351     }
2352
2353   return 0;
2354 }
2355
2356 /// SimplifyPHINode - See if we can fold the given phi.  If not, returns null.
2357 static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
2358   // If all of the PHI's incoming values are the same then replace the PHI node
2359   // with the common value.
2360   Value *CommonValue = 0;
2361   bool HasUndefInput = false;
2362   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
2363     Value *Incoming = PN->getIncomingValue(i);
2364     // If the incoming value is the phi node itself, it can safely be skipped.
2365     if (Incoming == PN) continue;
2366     if (isa<UndefValue>(Incoming)) {
2367       // Remember that we saw an undef value, but otherwise ignore them.
2368       HasUndefInput = true;
2369       continue;
2370     }
2371     if (CommonValue && Incoming != CommonValue)
2372       return 0;  // Not the same, bail out.
2373     CommonValue = Incoming;
2374   }
2375
2376   // If CommonValue is null then all of the incoming values were either undef or
2377   // equal to the phi node itself.
2378   if (!CommonValue)
2379     return UndefValue::get(PN->getType());
2380
2381   // If we have a PHI node like phi(X, undef, X), where X is defined by some
2382   // instruction, we cannot return X as the result of the PHI node unless it
2383   // dominates the PHI block.
2384   if (HasUndefInput)
2385     return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
2386
2387   return CommonValue;
2388 }
2389
2390
2391 //=== Helper functions for higher up the class hierarchy.
2392
2393 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
2394 /// fold the result.  If not, this returns null.
2395 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
2396                             const TargetData *TD, const DominatorTree *DT,
2397                             unsigned MaxRecurse) {
2398   switch (Opcode) {
2399   case Instruction::Add:
2400     return SimplifyAddInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false,
2401                            TD, DT, MaxRecurse);
2402   case Instruction::Sub:
2403     return SimplifySubInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false,
2404                            TD, DT, MaxRecurse);
2405   case Instruction::Mul:  return SimplifyMulInst (LHS, RHS, TD, DT, MaxRecurse);
2406   case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, TD, DT, MaxRecurse);
2407   case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, TD, DT, MaxRecurse);
2408   case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, TD, DT, MaxRecurse);
2409   case Instruction::SRem: return SimplifySRemInst(LHS, RHS, TD, DT, MaxRecurse);
2410   case Instruction::URem: return SimplifyURemInst(LHS, RHS, TD, DT, MaxRecurse);
2411   case Instruction::FRem: return SimplifyFRemInst(LHS, RHS, TD, DT, MaxRecurse);
2412   case Instruction::Shl:
2413     return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false,
2414                            TD, DT, MaxRecurse);
2415   case Instruction::LShr:
2416     return SimplifyLShrInst(LHS, RHS, /*isExact*/false, TD, DT, MaxRecurse);
2417   case Instruction::AShr:
2418     return SimplifyAShrInst(LHS, RHS, /*isExact*/false, TD, DT, MaxRecurse);
2419   case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse);
2420   case Instruction::Or:  return SimplifyOrInst (LHS, RHS, TD, DT, MaxRecurse);
2421   case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse);
2422   default:
2423     if (Constant *CLHS = dyn_cast<Constant>(LHS))
2424       if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
2425         Constant *COps[] = {CLHS, CRHS};
2426         return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, TD);
2427       }
2428
2429     // If the operation is associative, try some generic simplifications.
2430     if (Instruction::isAssociative(Opcode))
2431       if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, DT,
2432                                               MaxRecurse))
2433         return V;
2434
2435     // If the operation is with the result of a select instruction, check whether
2436     // operating on either branch of the select always yields the same value.
2437     if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
2438       if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT,
2439                                            MaxRecurse))
2440         return V;
2441
2442     // If the operation is with the result of a phi instruction, check whether
2443     // operating on all incoming values of the phi always yields the same value.
2444     if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
2445       if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse))
2446         return V;
2447
2448     return 0;
2449   }
2450 }
2451
2452 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
2453                            const TargetData *TD, const DominatorTree *DT) {
2454   return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit);
2455 }
2456
2457 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
2458 /// fold the result.
2459 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
2460                               const TargetData *TD, const DominatorTree *DT,
2461                               unsigned MaxRecurse) {
2462   if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
2463     return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
2464   return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
2465 }
2466
2467 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
2468                              const TargetData *TD, const DominatorTree *DT) {
2469   return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
2470 }
2471
2472 static Value *SimplifyCallInst(CallInst *CI) {
2473   // call undef -> undef
2474   if (isa<UndefValue>(CI->getCalledValue()))
2475     return UndefValue::get(CI->getType());
2476
2477   return 0;
2478 }
2479
2480 /// SimplifyInstruction - See if we can compute a simplified version of this
2481 /// instruction.  If not, this returns null.
2482 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
2483                                  const DominatorTree *DT) {
2484   Value *Result;
2485
2486   switch (I->getOpcode()) {
2487   default:
2488     Result = ConstantFoldInstruction(I, TD);
2489     break;
2490   case Instruction::Add:
2491     Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
2492                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
2493                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
2494                              TD, DT);
2495     break;
2496   case Instruction::Sub:
2497     Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
2498                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
2499                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
2500                              TD, DT);
2501     break;
2502   case Instruction::Mul:
2503     Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, DT);
2504     break;
2505   case Instruction::SDiv:
2506     Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), TD, DT);
2507     break;
2508   case Instruction::UDiv:
2509     Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), TD, DT);
2510     break;
2511   case Instruction::FDiv:
2512     Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), TD, DT);
2513     break;
2514   case Instruction::SRem:
2515     Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), TD, DT);
2516     break;
2517   case Instruction::URem:
2518     Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), TD, DT);
2519     break;
2520   case Instruction::FRem:
2521     Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), TD, DT);
2522     break;
2523   case Instruction::Shl:
2524     Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1),
2525                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
2526                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
2527                              TD, DT);
2528     break;
2529   case Instruction::LShr:
2530     Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1),
2531                               cast<BinaryOperator>(I)->isExact(),
2532                               TD, DT);
2533     break;
2534   case Instruction::AShr:
2535     Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1),
2536                               cast<BinaryOperator>(I)->isExact(),
2537                               TD, DT);
2538     break;
2539   case Instruction::And:
2540     Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT);
2541     break;
2542   case Instruction::Or:
2543     Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT);
2544     break;
2545   case Instruction::Xor:
2546     Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT);
2547     break;
2548   case Instruction::ICmp:
2549     Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
2550                               I->getOperand(0), I->getOperand(1), TD, DT);
2551     break;
2552   case Instruction::FCmp:
2553     Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
2554                               I->getOperand(0), I->getOperand(1), TD, DT);
2555     break;
2556   case Instruction::Select:
2557     Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
2558                                 I->getOperand(2), TD, DT);
2559     break;
2560   case Instruction::GetElementPtr: {
2561     SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
2562     Result = SimplifyGEPInst(Ops, TD, DT);
2563     break;
2564   }
2565   case Instruction::InsertValue: {
2566     InsertValueInst *IV = cast<InsertValueInst>(I);
2567     Result = SimplifyInsertValueInst(IV->getAggregateOperand(),
2568                                      IV->getInsertedValueOperand(),
2569                                      IV->getIndices(), TD, DT);
2570     break;
2571   }
2572   case Instruction::PHI:
2573     Result = SimplifyPHINode(cast<PHINode>(I), DT);
2574     break;
2575   case Instruction::Call:
2576     Result = SimplifyCallInst(cast<CallInst>(I));
2577     break;
2578   }
2579
2580   /// If called on unreachable code, the above logic may report that the
2581   /// instruction simplified to itself.  Make life easier for users by
2582   /// detecting that case here, returning a safe value instead.
2583   return Result == I ? UndefValue::get(I->getType()) : Result;
2584 }
2585
2586 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
2587 /// delete the From instruction.  In addition to a basic RAUW, this does a
2588 /// recursive simplification of the newly formed instructions.  This catches
2589 /// things where one simplification exposes other opportunities.  This only
2590 /// simplifies and deletes scalar operations, it does not change the CFG.
2591 ///
2592 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
2593                                      const TargetData *TD,
2594                                      const DominatorTree *DT) {
2595   assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
2596
2597   // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
2598   // we can know if it gets deleted out from under us or replaced in a
2599   // recursive simplification.
2600   WeakVH FromHandle(From);
2601   WeakVH ToHandle(To);
2602
2603   while (!From->use_empty()) {
2604     // Update the instruction to use the new value.
2605     Use &TheUse = From->use_begin().getUse();
2606     Instruction *User = cast<Instruction>(TheUse.getUser());
2607     TheUse = To;
2608
2609     // Check to see if the instruction can be folded due to the operand
2610     // replacement.  For example changing (or X, Y) into (or X, -1) can replace
2611     // the 'or' with -1.
2612     Value *SimplifiedVal;
2613     {
2614       // Sanity check to make sure 'User' doesn't dangle across
2615       // SimplifyInstruction.
2616       AssertingVH<> UserHandle(User);
2617
2618       SimplifiedVal = SimplifyInstruction(User, TD, DT);
2619       if (SimplifiedVal == 0) continue;
2620     }
2621
2622     // Recursively simplify this user to the new value.
2623     ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
2624     From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
2625     To = ToHandle;
2626
2627     assert(ToHandle && "To value deleted by recursive simplification?");
2628
2629     // If the recursive simplification ended up revisiting and deleting
2630     // 'From' then we're done.
2631     if (From == 0)
2632       return;
2633   }
2634
2635   // If 'From' has value handles referring to it, do a real RAUW to update them.
2636   From->replaceAllUsesWith(To);
2637
2638   From->eraseFromParent();
2639 }