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