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