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/ADT/Statistic.h"
  22 #include "llvm/Analysis/InstructionSimplify.h"
  23 #include "llvm/Analysis/ConstantFolding.h"
  24 #include "llvm/Analysis/Dominators.h"
  25 #include "llvm/Support/PatternMatch.h"
  26 #include "llvm/Support/ValueHandle.h"
  27 #include "llvm/Target/TargetData.h"
  28 using namespace llvm;
  29 using namespace llvm::PatternMatch;
  30
  31 #define RecursionLimit 3
  32
  33 STATISTIC(NumExpand,  "Number of expansions");
  34 STATISTIC(NumFactor , "Number of factorizations");
  35 STATISTIC(NumReassoc, "Number of reassociations");
  36
  37 static Value *SimplifyAndInst(Value *, Value *, const TargetData *,
  38                               const DominatorTree *, unsigned);
  39 static Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *,
  40                             const DominatorTree *, unsigned);
  41 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *,
  42                               const DominatorTree *, unsigned);
  43 static Value *SimplifyOrInst(Value *, Value *, const TargetData *,
  44                              const DominatorTree *, unsigned);
  45 static Value *SimplifyXorInst(Value *, Value *, const TargetData *,
  46                               const DominatorTree *, unsigned);
  47
  48 /// ValueDominatesPHI - Does the given value dominate the specified phi node?
  49 static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
  50   Instruction *I = dyn_cast<Instruction>(V);
  51   if (!I)
  52     // Arguments and constants dominate all instructions.
  53     return true;
  54
  55   // If we have a DominatorTree then do a precise test.
  56   if (DT)
  57     return DT->dominates(I, P);
  58
  59   // Otherwise, if the instruction is in the entry block, and is not an invoke,
  60   // then it obviously dominates all phi nodes.
  61   if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() &&
  62       !isa<InvokeInst>(I))
  63     return true;
  64
  65   return false;
  66 }
  67
  68 /// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning
  69 /// it into "(A op B) op' (A op C)".  Here "op" is given by Opcode and "op'" is
  70 /// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.
  71 /// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
  72 /// Returns the simplified value, or null if no simplification was performed.
  73 static Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS,
  74                           unsigned OpcodeToExpand, const TargetData *TD,
  75                           const DominatorTree *DT, unsigned MaxRecurse) {
  76   // Recursion is always used, so bail out at once if we already hit the limit.
  77   if (!MaxRecurse--)
  78     return 0;
  79
  80   // Check whether the expression has the form "(A op' B) op C".
  81   if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS))
  82     if (Op0->getOpcode() == OpcodeToExpand) {
  83       // It does!  Try turning it into "(A op C) op' (B op C)".
  84       Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
  85       // Do "A op C" and "B op C" both simplify?
  86       if (Value *L = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse))
  87         if (Value *R = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) {
  88           // They do! Return "L op' R" if it simplifies or is already available.
  89           // If "L op' R" equals "A op' B" then "L op' R" is just the LHS.
  90           if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand)
  91                                      && L == B && R == A)) {
  92             ++NumExpand;
  93             return LHS;
  94           }
  95           // Otherwise return "L op' R" if it simplifies.
  96           if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT,
  97                                        MaxRecurse)) {
  98             ++NumExpand;
  99             return V;
 100           }
 101         }
 102     }
 103
 104   // Check whether the expression has the form "A op (B op' C)".
 105   if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
 106     if (Op1->getOpcode() == OpcodeToExpand) {
 107       // It does!  Try turning it into "(A op B) op' (A op C)".
 108       Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
 109       // Do "A op B" and "A op C" both simplify?
 110       if (Value *L = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse))
 111         if (Value *R = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) {
 112           // They do! Return "L op' R" if it simplifies or is already available.
 113           // If "L op' R" equals "B op' C" then "L op' R" is just the RHS.
 114           if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand)
 115                                      && L == C && R == B)) {
 116             ++NumExpand;
 117             return RHS;
 118           }
 119           // Otherwise return "L op' R" if it simplifies.
 120           if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT,
 121                                        MaxRecurse)) {
 122             ++NumExpand;
 123             return V;
 124           }
 125         }
 126     }
 127
 128   return 0;
 129 }
 130
 131 /// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term
 132 /// using the operation OpCodeToExtract.  For example, when Opcode is Add and
 133 /// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)".
 134 /// Returns the simplified value, or null if no simplification was performed.
 135 static Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 136                              unsigned OpcodeToExtract, const TargetData *TD,
 137                              const DominatorTree *DT, unsigned MaxRecurse) {
 138   // Recursion is always used, so bail out at once if we already hit the limit.
 139   if (!MaxRecurse--)
 140     return 0;
 141
 142   BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
 143   BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
 144
 145   if (!Op0 || Op0->getOpcode() != OpcodeToExtract ||
 146       !Op1 || Op1->getOpcode() != OpcodeToExtract)
 147     return 0;
 148
 149   // The expression has the form "(A op' B) op (C op' D)".
 150   Value *A = Op0->getOperand(0), *B = Op0->getOperand(1);
 151   Value *C = Op1->getOperand(0), *D = Op1->getOperand(1);
 152
 153   // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)".
 154   // Does the instruction have the form "(A op' B) op (A op' D)" or, in the
 155   // commutative case, "(A op' B) op (C op' A)"?
 156   if (A == C || (Instruction::isCommutative(OpcodeToExtract) && A == D)) {
 157     Value *DD = A == C ? D : C;
 158     // Form "A op' (B op DD)" if it simplifies completely.
 159     // Does "B op DD" simplify?
 160     if (Value *V = SimplifyBinOp(Opcode, B, DD, TD, DT, MaxRecurse)) {
 161       // It does!  Return "A op' V" if it simplifies or is already available.
 162       // If V equals B then "A op' V" is just the LHS.  If V equals DD then
 163       // "A op' V" is just the RHS.
 164       if (V == B || V == DD) {
 165         ++NumFactor;
 166         return V == B ? LHS : RHS;
 167       }
 168       // Otherwise return "A op' V" if it simplifies.
 169       if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, TD, DT, MaxRecurse)) {
 170         ++NumFactor;
 171         return W;
 172       }
 173     }
 174   }
 175
 176   // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)".
 177   // Does the instruction have the form "(A op' B) op (C op' B)" or, in the
 178   // commutative case, "(A op' B) op (B op' D)"?
 179   if (B == D || (Instruction::isCommutative(OpcodeToExtract) && B == C)) {
 180     Value *CC = B == D ? C : D;
 181     // Form "(A op CC) op' B" if it simplifies completely..
 182     // Does "A op CC" simplify?
 183     if (Value *V = SimplifyBinOp(Opcode, A, CC, TD, DT, MaxRecurse)) {
 184       // It does!  Return "V op' B" if it simplifies or is already available.
 185       // If V equals A then "V op' B" is just the LHS.  If V equals CC then
 186       // "V op' B" is just the RHS.
 187       if (V == A || V == CC) {
 188         ++NumFactor;
 189         return V == A ? LHS : RHS;
 190       }
 191       // Otherwise return "V op' B" if it simplifies.
 192       if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, TD, DT, MaxRecurse)) {
 193         ++NumFactor;
 194         return W;
 195       }
 196     }
 197   }
 198
 199   return 0;
 200 }
 201
 202 /// SimplifyAssociativeBinOp - Generic simplifications for associative binary
 203 /// operations.  Returns the simpler value, or null if none was found.
 204 static Value *SimplifyAssociativeBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 205                                        const TargetData *TD,
 206                                        const DominatorTree *DT,
 207                                        unsigned MaxRecurse) {
 208   assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
 209
 210   // Recursion is always used, so bail out at once if we already hit the limit.
 211   if (!MaxRecurse--)
 212     return 0;
 213
 214   BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
 215   BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
 216
 217   // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely.
 218   if (Op0 && Op0->getOpcode() == Opcode) {
 219     Value *A = Op0->getOperand(0);
 220     Value *B = Op0->getOperand(1);
 221     Value *C = RHS;
 222
 223     // Does "B op C" simplify?
 224     if (Value *V = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) {
 225       // It does!  Return "A op V" if it simplifies or is already available.
 226       // If V equals B then "A op V" is just the LHS.
 227       if (V == B) return LHS;
 228       // Otherwise return "A op V" if it simplifies.
 229       if (Value *W = SimplifyBinOp(Opcode, A, V, TD, DT, MaxRecurse)) {
 230         ++NumReassoc;
 231         return W;
 232       }
 233     }
 234   }
 235
 236   // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely.
 237   if (Op1 && Op1->getOpcode() == Opcode) {
 238     Value *A = LHS;
 239     Value *B = Op1->getOperand(0);
 240     Value *C = Op1->getOperand(1);
 241
 242     // Does "A op B" simplify?
 243     if (Value *V = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) {
 244       // It does!  Return "V op C" if it simplifies or is already available.
 245       // If V equals B then "V op C" is just the RHS.
 246       if (V == B) return RHS;
 247       // Otherwise return "V op C" if it simplifies.
 248       if (Value *W = SimplifyBinOp(Opcode, V, C, TD, DT, MaxRecurse)) {
 249         ++NumReassoc;
 250         return W;
 251       }
 252     }
 253   }
 254
 255   // The remaining transforms require commutativity as well as associativity.
 256   if (!Instruction::isCommutative(Opcode))
 257     return 0;
 258
 259   // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely.
 260   if (Op0 && Op0->getOpcode() == Opcode) {
 261     Value *A = Op0->getOperand(0);
 262     Value *B = Op0->getOperand(1);
 263     Value *C = RHS;
 264
 265     // Does "C op A" simplify?
 266     if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) {
 267       // It does!  Return "V op B" if it simplifies or is already available.
 268       // If V equals A then "V op B" is just the LHS.
 269       if (V == A) return LHS;
 270       // Otherwise return "V op B" if it simplifies.
 271       if (Value *W = SimplifyBinOp(Opcode, V, B, TD, DT, MaxRecurse)) {
 272         ++NumReassoc;
 273         return W;
 274       }
 275     }
 276   }
 277
 278   // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely.
 279   if (Op1 && Op1->getOpcode() == Opcode) {
 280     Value *A = LHS;
 281     Value *B = Op1->getOperand(0);
 282     Value *C = Op1->getOperand(1);
 283
 284     // Does "C op A" simplify?
 285     if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) {
 286       // It does!  Return "B op V" if it simplifies or is already available.
 287       // If V equals C then "B op V" is just the RHS.
 288       if (V == C) return RHS;
 289       // Otherwise return "B op V" if it simplifies.
 290       if (Value *W = SimplifyBinOp(Opcode, B, V, TD, DT, MaxRecurse)) {
 291         ++NumReassoc;
 292         return W;
 293       }
 294     }
 295   }
 296
 297   return 0;
 298 }
 299
 300 /// ThreadBinOpOverSelect - In the case of a binary operation with a select
 301 /// instruction as an operand, try to simplify the binop by seeing whether
 302 /// evaluating it on both branches of the select results in the same value.
 303 /// Returns the common value if so, otherwise returns null.
 304 static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
 305                                     const TargetData *TD,
 306                                     const DominatorTree *DT,
 307                                     unsigned MaxRecurse) {
 308   // Recursion is always used, so bail out at once if we already hit the limit.
 309   if (!MaxRecurse--)
 310     return 0;
 311
 312   SelectInst *SI;
 313   if (isa<SelectInst>(LHS)) {
 314     SI = cast<SelectInst>(LHS);
 315   } else {
 316     assert(isa<SelectInst>(RHS) && "No select instruction operand!");
 317     SI = cast<SelectInst>(RHS);
 318   }
 319
 320   // Evaluate the BinOp on the true and false branches of the select.
 321   Value *TV;
 322   Value *FV;
 323   if (SI == LHS) {
 324     TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse);
 325     FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse);
 326   } else {
 327     TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse);
 328     FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse);
 329   }
 330
 331   // If they simplified to the same value, then return the common value.
 332   // If they both failed to simplify then return null.
 333   if (TV == FV)
 334     return TV;
 335
 336   // If one branch simplified to undef, return the other one.
 337   if (TV && isa<UndefValue>(TV))
 338     return FV;
 339   if (FV && isa<UndefValue>(FV))
 340     return TV;
 341
 342   // If applying the operation did not change the true and false select values,
 343   // then the result of the binop is the select itself.
 344   if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
 345     return SI;
 346
 347   // If one branch simplified and the other did not, and the simplified
 348   // value is equal to the unsimplified one, return the simplified value.
 349   // For example, select (cond, X, X & Z) & Z -> X & Z.
 350   if ((FV && !TV) || (TV && !FV)) {
 351     // Check that the simplified value has the form "X op Y" where "op" is the
 352     // same as the original operation.
 353     Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
 354     if (Simplified && Simplified->getOpcode() == Opcode) {
 355       // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
 356       // We already know that "op" is the same as for the simplified value.  See
 357       // if the operands match too.  If so, return the simplified value.
 358       Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
 359       Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
 360       Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
 361       if (Simplified->getOperand(0) == UnsimplifiedLHS &&
 362           Simplified->getOperand(1) == UnsimplifiedRHS)
 363         return Simplified;
 364       if (Simplified->isCommutative() &&
 365           Simplified->getOperand(1) == UnsimplifiedLHS &&
 366           Simplified->getOperand(0) == UnsimplifiedRHS)
 367         return Simplified;
 368     }
 369   }
 370
 371   return 0;
 372 }
 373
 374 /// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
 375 /// try to simplify the comparison by seeing whether both branches of the select
 376 /// result in the same value.  Returns the common value if so, otherwise returns
 377 /// null.
 378 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
 379                                   Value *RHS, const TargetData *TD,
 380                                   const DominatorTree *DT,
 381                                   unsigned MaxRecurse) {
 382   // Recursion is always used, so bail out at once if we already hit the limit.
 383   if (!MaxRecurse--)
 384     return 0;
 385
 386   // Make sure the select is on the LHS.
 387   if (!isa<SelectInst>(LHS)) {
 388     std::swap(LHS, RHS);
 389     Pred = CmpInst::getSwappedPredicate(Pred);
 390   }
 391   assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
 392   SelectInst *SI = cast<SelectInst>(LHS);
 393
 394   // Now that we have "cmp select(cond, TV, FV), RHS", analyse it.
 395   // Does "cmp TV, RHS" simplify?
 396   if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT,
 397                                     MaxRecurse))
 398     // It does!  Does "cmp FV, RHS" simplify?
 399     if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT,
 400                                       MaxRecurse))
 401       // It does!  If they simplified to the same value, then use it as the
 402       // result of the original comparison.
 403       if (TCmp == FCmp)
 404         return TCmp;
 405   return 0;
 406 }
 407
 408 /// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
 409 /// is a PHI instruction, try to simplify the binop by seeing whether evaluating
 410 /// it on the incoming phi values yields the same result for every value.  If so
 411 /// returns the common value, otherwise returns null.
 412 static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
 413                                  const TargetData *TD, const DominatorTree *DT,
 414                                  unsigned MaxRecurse) {
 415   // Recursion is always used, so bail out at once if we already hit the limit.
 416   if (!MaxRecurse--)
 417     return 0;
 418
 419   PHINode *PI;
 420   if (isa<PHINode>(LHS)) {
 421     PI = cast<PHINode>(LHS);
 422     // Bail out if RHS and the phi may be mutually interdependent due to a loop.
 423     if (!ValueDominatesPHI(RHS, PI, DT))
 424       return 0;
 425   } else {
 426     assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
 427     PI = cast<PHINode>(RHS);
 428     // Bail out if LHS and the phi may be mutually interdependent due to a loop.
 429     if (!ValueDominatesPHI(LHS, PI, DT))
 430       return 0;
 431   }
 432
 433   // Evaluate the BinOp on the incoming phi values.
 434   Value *CommonValue = 0;
 435   for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
 436     Value *Incoming = PI->getIncomingValue(i);
 437     // If the incoming value is the phi node itself, it can safely be skipped.
 438     if (Incoming == PI) continue;
 439     Value *V = PI == LHS ?
 440       SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) :
 441       SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse);
 442     // If the operation failed to simplify, or simplified to a different value
 443     // to previously, then give up.
 444     if (!V || (CommonValue && V != CommonValue))
 445       return 0;
 446     CommonValue = V;
 447   }
 448
 449   return CommonValue;
 450 }
 451
 452 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
 453 /// try to simplify the comparison by seeing whether comparing with all of the
 454 /// incoming phi values yields the same result every time.  If so returns the
 455 /// common result, otherwise returns null.
 456 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
 457                                const TargetData *TD, const DominatorTree *DT,
 458                                unsigned MaxRecurse) {
 459   // Recursion is always used, so bail out at once if we already hit the limit.
 460   if (!MaxRecurse--)
 461     return 0;
 462
 463   // Make sure the phi is on the LHS.
 464   if (!isa<PHINode>(LHS)) {
 465     std::swap(LHS, RHS);
 466     Pred = CmpInst::getSwappedPredicate(Pred);
 467   }
 468   assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
 469   PHINode *PI = cast<PHINode>(LHS);
 470
 471   // Bail out if RHS and the phi may be mutually interdependent due to a loop.
 472   if (!ValueDominatesPHI(RHS, PI, DT))
 473     return 0;
 474
 475   // Evaluate the BinOp on the incoming phi values.
 476   Value *CommonValue = 0;
 477   for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
 478     Value *Incoming = PI->getIncomingValue(i);
 479     // If the incoming value is the phi node itself, it can safely be skipped.
 480     if (Incoming == PI) continue;
 481     Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse);
 482     // If the operation failed to simplify, or simplified to a different value
 483     // to previously, then give up.
 484     if (!V || (CommonValue && V != CommonValue))
 485       return 0;
 486     CommonValue = V;
 487   }
 488
 489   return CommonValue;
 490 }
 491
 492 /// SimplifyAddInst - Given operands for an Add, see if we can
 493 /// fold the result.  If not, this returns null.
 494 static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 495                               const TargetData *TD, const DominatorTree *DT,
 496                               unsigned MaxRecurse) {
 497   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 498     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 499       Constant *Ops[] = { CLHS, CRHS };
 500       return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
 501                                       Ops, 2, TD);
 502     }
 503
 504     // Canonicalize the constant to the RHS.
 505     std::swap(Op0, Op1);
 506   }
 507
 508   // X + undef -> undef
 509   if (isa<UndefValue>(Op1))
 510     return Op1;
 511
 512   // X + 0 -> X
 513   if (match(Op1, m_Zero()))
 514     return Op0;
 515
 516   // X + (Y - X) -> Y
 517   // (Y - X) + X -> Y
 518   // Eg: X + -X -> 0
 519   Value *Y = 0;
 520   if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
 521       match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
 522     return Y;
 523
 524   // X + ~X -> -1   since   ~X = -X-1
 525   if (match(Op0, m_Not(m_Specific(Op1))) ||
 526       match(Op1, m_Not(m_Specific(Op0))))
 527     return Constant::getAllOnesValue(Op0->getType());
 528
 529   /// i1 add -> xor.
 530   if (MaxRecurse && Op0->getType()->isIntegerTy(1))
 531     if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1))
 532       return V;
 533
 534   // Try some generic simplifications for associative operations.
 535   if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, TD, DT,
 536                                           MaxRecurse))
 537     return V;
 538
 539   // Mul distributes over Add.  Try some generic simplifications based on this.
 540   if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul,
 541                                 TD, DT, MaxRecurse))
 542     return V;
 543
 544   // Threading Add over selects and phi nodes is pointless, so don't bother.
 545   // Threading over the select in "A + select(cond, B, C)" means evaluating
 546   // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
 547   // only if B and C are equal.  If B and C are equal then (since we assume
 548   // that operands have already been simplified) "select(cond, B, C)" should
 549   // have been simplified to the common value of B and C already.  Analysing
 550   // "A+B" and "A+C" thus gains nothing, but costs compile time.  Similarly
 551   // for threading over phi nodes.
 552
 553   return 0;
 554 }
 555
 556 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 557                              const TargetData *TD, const DominatorTree *DT) {
 558   return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit);
 559 }
 560
 561 /// SimplifySubInst - Given operands for a Sub, see if we can
 562 /// fold the result.  If not, this returns null.
 563 static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 564                               const TargetData *TD, const DominatorTree *DT,
 565                               unsigned MaxRecurse) {
 566   if (Constant *CLHS = dyn_cast<Constant>(Op0))
 567     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 568       Constant *Ops[] = { CLHS, CRHS };
 569       return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(),
 570                                       Ops, 2, TD);
 571     }
 572
 573   // X - undef -> undef
 574   // undef - X -> undef
 575   if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1))
 576     return UndefValue::get(Op0->getType());
 577
 578   // X - 0 -> X
 579   if (match(Op1, m_Zero()))
 580     return Op0;
 581
 582   // X - X -> 0
 583   if (Op0 == Op1)
 584     return Constant::getNullValue(Op0->getType());
 585
 586   // (X + Y) - Y -> X
 587   // (Y + X) - Y -> X
 588   Value *X = 0;
 589   if (match(Op0, m_Add(m_Value(X), m_Specific(Op1))) ||
 590       match(Op0, m_Add(m_Specific(Op1), m_Value(X))))
 591     return X;
 592
 593   /// i1 sub -> xor.
 594   if (MaxRecurse && Op0->getType()->isIntegerTy(1))
 595     if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1))
 596       return V;
 597
 598   // Mul distributes over Sub.  Try some generic simplifications based on this.
 599   if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul,
 600                                 TD, DT, MaxRecurse))
 601     return V;
 602
 603   // Threading Sub over selects and phi nodes is pointless, so don't bother.
 604   // Threading over the select in "A - select(cond, B, C)" means evaluating
 605   // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
 606   // only if B and C are equal.  If B and C are equal then (since we assume
 607   // that operands have already been simplified) "select(cond, B, C)" should
 608   // have been simplified to the common value of B and C already.  Analysing
 609   // "A-B" and "A-C" thus gains nothing, but costs compile time.  Similarly
 610   // for threading over phi nodes.
 611
 612   return 0;
 613 }
 614
 615 Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 616                              const TargetData *TD, const DominatorTree *DT) {
 617   return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit);
 618 }
 619
 620 /// SimplifyMulInst - Given operands for a Mul, see if we can
 621 /// fold the result.  If not, this returns null.
 622 static Value *SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD,
 623                               const DominatorTree *DT, unsigned MaxRecurse) {
 624   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 625     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 626       Constant *Ops[] = { CLHS, CRHS };
 627       return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(),
 628                                       Ops, 2, TD);
 629     }
 630
 631     // Canonicalize the constant to the RHS.
 632     std::swap(Op0, Op1);
 633   }
 634
 635   // X * undef -> 0
 636   if (isa<UndefValue>(Op1))
 637     return Constant::getNullValue(Op0->getType());
 638
 639   // X * 0 -> 0
 640   if (match(Op1, m_Zero()))
 641     return Op1;
 642
 643   // X * 1 -> X
 644   if (match(Op1, m_One()))
 645     return Op0;
 646
 647   /// i1 mul -> and.
 648   if (MaxRecurse && Op0->getType()->isIntegerTy(1))
 649     if (Value *V = SimplifyAndInst(Op0, Op1, TD, DT, MaxRecurse-1))
 650       return V;
 651
 652   // Try some generic simplifications for associative operations.
 653   if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, TD, DT,
 654                                           MaxRecurse))
 655     return V;
 656
 657   // Mul distributes over Add.  Try some generic simplifications based on this.
 658   if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add,
 659                              TD, DT, MaxRecurse))
 660     return V;
 661
 662   // If the operation is with the result of a select instruction, check whether
 663   // operating on either branch of the select always yields the same value.
 664   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
 665     if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, TD, DT,
 666                                          MaxRecurse))
 667       return V;
 668
 669   // If the operation is with the result of a phi instruction, check whether
 670   // operating on all incoming values of the phi always yields the same value.
 671   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
 672     if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, TD, DT,
 673                                       MaxRecurse))
 674       return V;
 675
 676   return 0;
 677 }
 678
 679 Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD,
 680                              const DominatorTree *DT) {
 681   return ::SimplifyMulInst(Op0, Op1, TD, DT, RecursionLimit);
 682 }
 683
 684 /// SimplifyAndInst - Given operands for an And, see if we can
 685 /// fold the result.  If not, this returns null.
 686 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
 687                               const DominatorTree *DT, unsigned MaxRecurse) {
 688   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 689     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 690       Constant *Ops[] = { CLHS, CRHS };
 691       return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
 692                                       Ops, 2, TD);
 693     }
 694
 695     // Canonicalize the constant to the RHS.
 696     std::swap(Op0, Op1);
 697   }
 698
 699   // X & undef -> 0
 700   if (isa<UndefValue>(Op1))
 701     return Constant::getNullValue(Op0->getType());
 702
 703   // X & X = X
 704   if (Op0 == Op1)
 705     return Op0;
 706
 707   // X & 0 = 0
 708   if (match(Op1, m_Zero()))
 709     return Op1;
 710
 711   // X & -1 = X
 712   if (match(Op1, m_AllOnes()))
 713     return Op0;
 714
 715   // A & ~A  =  ~A & A  =  0
 716   Value *A = 0, *B = 0;
 717   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
 718       (match(Op1, m_Not(m_Value(A))) && A == Op0))
 719     return Constant::getNullValue(Op0->getType());
 720
 721   // (A | ?) & A = A
 722   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
 723       (A == Op1 || B == Op1))
 724     return Op1;
 725
 726   // A & (A | ?) = A
 727   if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
 728       (A == Op0 || B == Op0))
 729     return Op0;
 730
 731   // Try some generic simplifications for associative operations.
 732   if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, DT,
 733                                           MaxRecurse))
 734     return V;
 735
 736   // And distributes over Or.  Try some generic simplifications based on this.
 737   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
 738                              TD, DT, MaxRecurse))
 739     return V;
 740
 741   // And distributes over Xor.  Try some generic simplifications based on this.
 742   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor,
 743                              TD, DT, MaxRecurse))
 744     return V;
 745
 746   // Or distributes over And.  Try some generic simplifications based on this.
 747   if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or,
 748                                 TD, DT, MaxRecurse))
 749     return V;
 750
 751   // If the operation is with the result of a select instruction, check whether
 752   // operating on either branch of the select always yields the same value.
 753   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
 754     if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT,
 755                                          MaxRecurse))
 756       return V;
 757
 758   // If the operation is with the result of a phi instruction, check whether
 759   // operating on all incoming values of the phi always yields the same value.
 760   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
 761     if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT,
 762                                       MaxRecurse))
 763       return V;
 764
 765   return 0;
 766 }
 767
 768 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
 769                              const DominatorTree *DT) {
 770   return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit);
 771 }
 772
 773 /// SimplifyOrInst - Given operands for an Or, see if we can
 774 /// fold the result.  If not, this returns null.
 775 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
 776                              const DominatorTree *DT, unsigned MaxRecurse) {
 777   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 778     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 779       Constant *Ops[] = { CLHS, CRHS };
 780       return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
 781                                       Ops, 2, TD);
 782     }
 783
 784     // Canonicalize the constant to the RHS.
 785     std::swap(Op0, Op1);
 786   }
 787
 788   // X | undef -> -1
 789   if (isa<UndefValue>(Op1))
 790     return Constant::getAllOnesValue(Op0->getType());
 791
 792   // X | X = X
 793   if (Op0 == Op1)
 794     return Op0;
 795
 796   // X | 0 = X
 797   if (match(Op1, m_Zero()))
 798     return Op0;
 799
 800   // X | -1 = -1
 801   if (match(Op1, m_AllOnes()))
 802     return Op1;
 803
 804   // A | ~A  =  ~A | A  =  -1
 805   Value *A = 0, *B = 0;
 806   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
 807       (match(Op1, m_Not(m_Value(A))) && A == Op0))
 808     return Constant::getAllOnesValue(Op0->getType());
 809
 810   // (A & ?) | A = A
 811   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
 812       (A == Op1 || B == Op1))
 813     return Op1;
 814
 815   // A | (A & ?) = A
 816   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
 817       (A == Op0 || B == Op0))
 818     return Op0;
 819
 820   // Try some generic simplifications for associative operations.
 821   if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, DT,
 822                                           MaxRecurse))
 823     return V;
 824
 825   // Or distributes over And.  Try some generic simplifications based on this.
 826   if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And,
 827                              TD, DT, MaxRecurse))
 828     return V;
 829
 830   // And distributes over Or.  Try some generic simplifications based on this.
 831   if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And,
 832                                 TD, DT, MaxRecurse))
 833     return V;
 834
 835   // If the operation is with the result of a select instruction, check whether
 836   // operating on either branch of the select always yields the same value.
 837   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
 838     if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT,
 839                                          MaxRecurse))
 840       return V;
 841
 842   // If the operation is with the result of a phi instruction, check whether
 843   // operating on all incoming values of the phi always yields the same value.
 844   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
 845     if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT,
 846                                       MaxRecurse))
 847       return V;
 848
 849   return 0;
 850 }
 851
 852 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
 853                             const DominatorTree *DT) {
 854   return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit);
 855 }
 856
 857 /// SimplifyXorInst - Given operands for a Xor, see if we can
 858 /// fold the result.  If not, this returns null.
 859 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
 860                               const DominatorTree *DT, unsigned MaxRecurse) {
 861   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 862     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 863       Constant *Ops[] = { CLHS, CRHS };
 864       return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
 865                                       Ops, 2, TD);
 866     }
 867
 868     // Canonicalize the constant to the RHS.
 869     std::swap(Op0, Op1);
 870   }
 871
 872   // A ^ undef -> undef
 873   if (isa<UndefValue>(Op1))
 874     return Op1;
 875
 876   // A ^ 0 = A
 877   if (match(Op1, m_Zero()))
 878     return Op0;
 879
 880   // A ^ A = 0
 881   if (Op0 == Op1)
 882     return Constant::getNullValue(Op0->getType());
 883
 884   // A ^ ~A  =  ~A ^ A  =  -1
 885   Value *A = 0;
 886   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
 887       (match(Op1, m_Not(m_Value(A))) && A == Op0))
 888     return Constant::getAllOnesValue(Op0->getType());
 889
 890   // Try some generic simplifications for associative operations.
 891   if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, DT,
 892                                           MaxRecurse))
 893     return V;
 894
 895   // And distributes over Xor.  Try some generic simplifications based on this.
 896   if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And,
 897                                 TD, DT, MaxRecurse))
 898     return V;
 899
 900   // Threading Xor over selects and phi nodes is pointless, so don't bother.
 901   // Threading over the select in "A ^ select(cond, B, C)" means evaluating
 902   // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
 903   // only if B and C are equal.  If B and C are equal then (since we assume
 904   // that operands have already been simplified) "select(cond, B, C)" should
 905   // have been simplified to the common value of B and C already.  Analysing
 906   // "A^B" and "A^C" thus gains nothing, but costs compile time.  Similarly
 907   // for threading over phi nodes.
 908
 909   return 0;
 910 }
 911
 912 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
 913                              const DominatorTree *DT) {
 914   return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit);
 915 }
 916
 917 static const Type *GetCompareTy(Value *Op) {
 918   return CmpInst::makeCmpResultType(Op->getType());
 919 }
 920
 921 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
 922 /// fold the result.  If not, this returns null.
 923 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 924                                const TargetData *TD, const DominatorTree *DT,
 925                                unsigned MaxRecurse) {
 926   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
 927   assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
 928
 929   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
 930     if (Constant *CRHS = dyn_cast<Constant>(RHS))
 931       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
 932
 933     // If we have a constant, make sure it is on the RHS.
 934     std::swap(LHS, RHS);
 935     Pred = CmpInst::getSwappedPredicate(Pred);
 936   }
 937
 938   // ITy - This is the return type of the compare we're considering.
 939   const Type *ITy = GetCompareTy(LHS);
 940
 941   // icmp X, X -> true/false
 942   // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
 943   // because X could be 0.
 944   if (LHS == RHS || isa<UndefValue>(RHS))
 945     return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
 946
 947   // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
 948   // addresses never equal each other!  We already know that Op0 != Op1.
 949   if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
 950        isa<ConstantPointerNull>(LHS)) &&
 951       (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
 952        isa<ConstantPointerNull>(RHS)))
 953     return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
 954
 955   // See if we are doing a comparison with a constant.
 956   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
 957     // If we have an icmp le or icmp ge instruction, turn it into the
 958     // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
 959     // them being folded in the code below.
 960     switch (Pred) {
 961     default: break;
 962     case ICmpInst::ICMP_ULE:
 963       if (CI->isMaxValue(false))                 // A <=u MAX -> TRUE
 964         return ConstantInt::getTrue(CI->getContext());
 965       break;
 966     case ICmpInst::ICMP_SLE:
 967       if (CI->isMaxValue(true))                  // A <=s MAX -> TRUE
 968         return ConstantInt::getTrue(CI->getContext());
 969       break;
 970     case ICmpInst::ICMP_UGE:
 971       if (CI->isMinValue(false))                 // A >=u MIN -> TRUE
 972         return ConstantInt::getTrue(CI->getContext());
 973       break;
 974     case ICmpInst::ICMP_SGE:
 975       if (CI->isMinValue(true))                  // A >=s MIN -> TRUE
 976         return ConstantInt::getTrue(CI->getContext());
 977       break;
 978     }
 979   }
 980
 981   // If the comparison is with the result of a select instruction, check whether
 982   // comparing with either branch of the select always yields the same value.
 983   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
 984     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse))
 985       return V;
 986
 987   // If the comparison is with the result of a phi instruction, check whether
 988   // doing the compare with each incoming phi value yields a common result.
 989   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
 990     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse))
 991       return V;
 992
 993   return 0;
 994 }
 995
 996 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 997                               const TargetData *TD, const DominatorTree *DT) {
 998   return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
 999 }
1000
1001 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
1002 /// fold the result.  If not, this returns null.
1003 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1004                                const TargetData *TD, const DominatorTree *DT,
1005                                unsigned MaxRecurse) {
1006   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
1007   assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
1008
1009   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
1010     if (Constant *CRHS = dyn_cast<Constant>(RHS))
1011       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
1012
1013     // If we have a constant, make sure it is on the RHS.
1014     std::swap(LHS, RHS);
1015     Pred = CmpInst::getSwappedPredicate(Pred);
1016   }
1017
1018   // Fold trivial predicates.
1019   if (Pred == FCmpInst::FCMP_FALSE)
1020     return ConstantInt::get(GetCompareTy(LHS), 0);
1021   if (Pred == FCmpInst::FCMP_TRUE)
1022     return ConstantInt::get(GetCompareTy(LHS), 1);
1023
1024   if (isa<UndefValue>(RHS))                  // fcmp pred X, undef -> undef
1025     return UndefValue::get(GetCompareTy(LHS));
1026
1027   // fcmp x,x -> true/false.  Not all compares are foldable.
1028   if (LHS == RHS) {
1029     if (CmpInst::isTrueWhenEqual(Pred))
1030       return ConstantInt::get(GetCompareTy(LHS), 1);
1031     if (CmpInst::isFalseWhenEqual(Pred))
1032       return ConstantInt::get(GetCompareTy(LHS), 0);
1033   }
1034
1035   // Handle fcmp with constant RHS
1036   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
1037     // If the constant is a nan, see if we can fold the comparison based on it.
1038     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
1039       if (CFP->getValueAPF().isNaN()) {
1040         if (FCmpInst::isOrdered(Pred))   // True "if ordered and foo"
1041           return ConstantInt::getFalse(CFP->getContext());
1042         assert(FCmpInst::isUnordered(Pred) &&
1043                "Comparison must be either ordered or unordered!");
1044         // True if unordered.
1045         return ConstantInt::getTrue(CFP->getContext());
1046       }
1047       // Check whether the constant is an infinity.
1048       if (CFP->getValueAPF().isInfinity()) {
1049         if (CFP->getValueAPF().isNegative()) {
1050           switch (Pred) {
1051           case FCmpInst::FCMP_OLT:
1052             // No value is ordered and less than negative infinity.
1053             return ConstantInt::getFalse(CFP->getContext());
1054           case FCmpInst::FCMP_UGE:
1055             // All values are unordered with or at least negative infinity.
1056             return ConstantInt::getTrue(CFP->getContext());
1057           default:
1058             break;
1059           }
1060         } else {
1061           switch (Pred) {
1062           case FCmpInst::FCMP_OGT:
1063             // No value is ordered and greater than infinity.
1064             return ConstantInt::getFalse(CFP->getContext());
1065           case FCmpInst::FCMP_ULE:
1066             // All values are unordered with and at most infinity.
1067             return ConstantInt::getTrue(CFP->getContext());
1068           default:
1069             break;
1070           }
1071         }
1072       }
1073     }
1074   }
1075
1076   // If the comparison is with the result of a select instruction, check whether
1077   // comparing with either branch of the select always yields the same value.
1078   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
1079     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse))
1080       return V;
1081
1082   // If the comparison is with the result of a phi instruction, check whether
1083   // doing the compare with each incoming phi value yields a common result.
1084   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
1085     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse))
1086       return V;
1087
1088   return 0;
1089 }
1090
1091 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1092                               const TargetData *TD, const DominatorTree *DT) {
1093   return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
1094 }
1095
1096 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
1097 /// the result.  If not, this returns null.
1098 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
1099                                 const TargetData *TD, const DominatorTree *) {
1100   // select true, X, Y  -> X
1101   // select false, X, Y -> Y
1102   if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
1103     return CB->getZExtValue() ? TrueVal : FalseVal;
1104
1105   // select C, X, X -> X
1106   if (TrueVal == FalseVal)
1107     return TrueVal;
1108
1109   if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
1110     return FalseVal;
1111   if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
1112     return TrueVal;
1113   if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
1114     if (isa<Constant>(TrueVal))
1115       return TrueVal;
1116     return FalseVal;
1117   }
1118
1119   return 0;
1120 }
1121
1122 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
1123 /// fold the result.  If not, this returns null.
1124 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
1125                              const TargetData *TD, const DominatorTree *) {
1126   // The type of the GEP pointer operand.
1127   const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType());
1128
1129   // getelementptr P -> P.
1130   if (NumOps == 1)
1131     return Ops[0];
1132
1133   if (isa<UndefValue>(Ops[0])) {
1134     // Compute the (pointer) type returned by the GEP instruction.
1135     const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1],
1136                                                              NumOps-1);
1137     const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace());
1138     return UndefValue::get(GEPTy);
1139   }
1140
1141   if (NumOps == 2) {
1142     // getelementptr P, 0 -> P.
1143     if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
1144       if (C->isZero())
1145         return Ops[0];
1146     // getelementptr P, N -> P if P points to a type of zero size.
1147     if (TD) {
1148       const Type *Ty = PtrTy->getElementType();
1149       if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0)
1150         return Ops[0];
1151     }
1152   }
1153
1154   // Check to see if this is constant foldable.
1155   for (unsigned i = 0; i != NumOps; ++i)
1156     if (!isa<Constant>(Ops[i]))
1157       return 0;
1158
1159   return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
1160                                         (Constant *const*)Ops+1, NumOps-1);
1161 }
1162
1163 /// SimplifyPHINode - See if we can fold the given phi.  If not, returns null.
1164 static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
1165   // If all of the PHI's incoming values are the same then replace the PHI node
1166   // with the common value.
1167   Value *CommonValue = 0;
1168   bool HasUndefInput = false;
1169   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1170     Value *Incoming = PN->getIncomingValue(i);
1171     // If the incoming value is the phi node itself, it can safely be skipped.
1172     if (Incoming == PN) continue;
1173     if (isa<UndefValue>(Incoming)) {
1174       // Remember that we saw an undef value, but otherwise ignore them.
1175       HasUndefInput = true;
1176       continue;
1177     }
1178     if (CommonValue && Incoming != CommonValue)
1179       return 0;  // Not the same, bail out.
1180     CommonValue = Incoming;
1181   }
1182
1183   // If CommonValue is null then all of the incoming values were either undef or
1184   // equal to the phi node itself.
1185   if (!CommonValue)
1186     return UndefValue::get(PN->getType());
1187
1188   // If we have a PHI node like phi(X, undef, X), where X is defined by some
1189   // instruction, we cannot return X as the result of the PHI node unless it
1190   // dominates the PHI block.
1191   if (HasUndefInput)
1192     return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
1193
1194   return CommonValue;
1195 }
1196
1197
1198 //=== Helper functions for higher up the class hierarchy.
1199
1200 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
1201 /// fold the result.  If not, this returns null.
1202 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
1203                             const TargetData *TD, const DominatorTree *DT,
1204                             unsigned MaxRecurse) {
1205   switch (Opcode) {
1206   case Instruction::Add: return SimplifyAddInst(LHS, RHS, /* isNSW */ false,
1207                                                 /* isNUW */ false, TD, DT,
1208                                                 MaxRecurse);
1209   case Instruction::Sub: return SimplifySubInst(LHS, RHS, /* isNSW */ false,
1210                                                 /* isNUW */ false, TD, DT,
1211                                                 MaxRecurse);
1212   case Instruction::Mul: return SimplifyMulInst(LHS, RHS, TD, DT, MaxRecurse);
1213   case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse);
1214   case Instruction::Or:  return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse);
1215   case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse);
1216   default:
1217     if (Constant *CLHS = dyn_cast<Constant>(LHS))
1218       if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
1219         Constant *COps[] = {CLHS, CRHS};
1220         return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
1221       }
1222
1223     // If the operation is associative, try some generic simplifications.
1224     if (Instruction::isAssociative(Opcode))
1225       if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, DT,
1226                                               MaxRecurse))
1227         return V;
1228
1229     // If the operation is with the result of a select instruction, check whether
1230     // operating on either branch of the select always yields the same value.
1231     if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
1232       if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT,
1233                                            MaxRecurse))
1234         return V;
1235
1236     // If the operation is with the result of a phi instruction, check whether
1237     // operating on all incoming values of the phi always yields the same value.
1238     if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
1239       if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse))
1240         return V;
1241
1242     return 0;
1243   }
1244 }
1245
1246 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
1247                            const TargetData *TD, const DominatorTree *DT) {
1248   return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit);
1249 }
1250
1251 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
1252 /// fold the result.
1253 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1254                               const TargetData *TD, const DominatorTree *DT,
1255                               unsigned MaxRecurse) {
1256   if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
1257     return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
1258   return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
1259 }
1260
1261 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1262                              const TargetData *TD, const DominatorTree *DT) {
1263   return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
1264 }
1265
1266 /// SimplifyInstruction - See if we can compute a simplified version of this
1267 /// instruction.  If not, this returns null.
1268 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
1269                                  const DominatorTree *DT) {
1270   Value *Result;
1271
1272   switch (I->getOpcode()) {
1273   default:
1274     Result = ConstantFoldInstruction(I, TD);
1275     break;
1276   case Instruction::Add:
1277     Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
1278                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
1279                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
1280                              TD, DT);
1281     break;
1282   case Instruction::Sub:
1283     Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
1284                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
1285                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
1286                              TD, DT);
1287     break;
1288   case Instruction::Mul:
1289     Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, DT);
1290     break;
1291   case Instruction::And:
1292     Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT);
1293     break;
1294   case Instruction::Or:
1295     Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT);
1296     break;
1297   case Instruction::Xor:
1298     Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT);
1299     break;
1300   case Instruction::ICmp:
1301     Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
1302                               I->getOperand(0), I->getOperand(1), TD, DT);
1303     break;
1304   case Instruction::FCmp:
1305     Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
1306                               I->getOperand(0), I->getOperand(1), TD, DT);
1307     break;
1308   case Instruction::Select:
1309     Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
1310                                 I->getOperand(2), TD, DT);
1311     break;
1312   case Instruction::GetElementPtr: {
1313     SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
1314     Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT);
1315     break;
1316   }
1317   case Instruction::PHI:
1318     Result = SimplifyPHINode(cast<PHINode>(I), DT);
1319     break;
1320   }
1321
1322   /// If called on unreachable code, the above logic may report that the
1323   /// instruction simplified to itself.  Make life easier for users by
1324   /// detecting that case here, returning a safe value instead.
1325   return Result == I ? UndefValue::get(I->getType()) : Result;
1326 }
1327
1328 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
1329 /// delete the From instruction.  In addition to a basic RAUW, this does a
1330 /// recursive simplification of the newly formed instructions.  This catches
1331 /// things where one simplification exposes other opportunities.  This only
1332 /// simplifies and deletes scalar operations, it does not change the CFG.
1333 ///
1334 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
1335                                      const TargetData *TD,
1336                                      const DominatorTree *DT) {
1337   assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
1338
1339   // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
1340   // we can know if it gets deleted out from under us or replaced in a
1341   // recursive simplification.
1342   WeakVH FromHandle(From);
1343   WeakVH ToHandle(To);
1344
1345   while (!From->use_empty()) {
1346     // Update the instruction to use the new value.
1347     Use &TheUse = From->use_begin().getUse();
1348     Instruction *User = cast<Instruction>(TheUse.getUser());
1349     TheUse = To;
1350
1351     // Check to see if the instruction can be folded due to the operand
1352     // replacement.  For example changing (or X, Y) into (or X, -1) can replace
1353     // the 'or' with -1.
1354     Value *SimplifiedVal;
1355     {
1356       // Sanity check to make sure 'User' doesn't dangle across
1357       // SimplifyInstruction.
1358       AssertingVH<> UserHandle(User);
1359
1360       SimplifiedVal = SimplifyInstruction(User, TD, DT);
1361       if (SimplifiedVal == 0) continue;
1362     }
1363
1364     // Recursively simplify this user to the new value.
1365     ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
1366     From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
1367     To = ToHandle;
1368
1369     assert(ToHandle && "To value deleted by recursive simplification?");
1370
1371     // If the recursive simplification ended up revisiting and deleting
1372     // 'From' then we're done.
1373     if (From == 0)
1374       return;
1375   }
1376
1377   // If 'From' has value handles referring to it, do a real RAUW to update them.
1378   From->replaceAllUsesWith(To);
1379
1380   From->eraseFromParent();
1381 }