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     return SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1);
 496
 497   // Try some generic simplifications for associative operations.
 498   if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, TD, DT,
 499                                           MaxRecurse))
 500     return V;
 501
 502   // Mul distributes over Add.  Try some generic simplifications based on this.
 503   if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul,
 504                                 TD, DT, MaxRecurse))
 505     return V;
 506
 507   // Threading Add over selects and phi nodes is pointless, so don't bother.
 508   // Threading over the select in "A + select(cond, B, C)" means evaluating
 509   // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
 510   // only if B and C are equal.  If B and C are equal then (since we assume
 511   // that operands have already been simplified) "select(cond, B, C)" should
 512   // have been simplified to the common value of B and C already.  Analysing
 513   // "A+B" and "A+C" thus gains nothing, but costs compile time.  Similarly
 514   // for threading over phi nodes.
 515
 516   return 0;
 517 }
 518
 519 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 520                              const TargetData *TD, const DominatorTree *DT) {
 521   return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit);
 522 }
 523
 524 /// SimplifySubInst - Given operands for a Sub, see if we can
 525 /// fold the result.  If not, this returns null.
 526 static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 527                               const TargetData *TD, const DominatorTree *DT,
 528                               unsigned MaxRecurse) {
 529   if (Constant *CLHS = dyn_cast<Constant>(Op0))
 530     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 531       Constant *Ops[] = { CLHS, CRHS };
 532       return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(),
 533                                       Ops, 2, TD);
 534     }
 535
 536   // X - undef -> undef
 537   // undef - X -> undef
 538   if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1))
 539     return UndefValue::get(Op0->getType());
 540
 541   // X - 0 -> X
 542   if (match(Op1, m_Zero()))
 543     return Op0;
 544
 545   // X - X -> 0
 546   if (Op0 == Op1)
 547     return Constant::getNullValue(Op0->getType());
 548
 549   // (X + Y) - Y -> X
 550   // (Y + X) - Y -> X
 551   Value *X = 0;
 552   if (match(Op0, m_Add(m_Value(X), m_Specific(Op1))) ||
 553       match(Op0, m_Add(m_Specific(Op1), m_Value(X))))
 554     return X;
 555
 556   /// i1 sub -> xor.
 557   if (!MaxRecurse && Op0->getType()->isIntegerTy(1))
 558     return SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1);
 559
 560   // Mul distributes over Sub.  Try some generic simplifications based on this.
 561   if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul,
 562                                 TD, DT, MaxRecurse))
 563     return V;
 564
 565   // Threading Sub over selects and phi nodes is pointless, so don't bother.
 566   // Threading over the select in "A - select(cond, B, C)" means evaluating
 567   // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
 568   // only if B and C are equal.  If B and C are equal then (since we assume
 569   // that operands have already been simplified) "select(cond, B, C)" should
 570   // have been simplified to the common value of B and C already.  Analysing
 571   // "A-B" and "A-C" thus gains nothing, but costs compile time.  Similarly
 572   // for threading over phi nodes.
 573
 574   return 0;
 575 }
 576
 577 Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 578                              const TargetData *TD, const DominatorTree *DT) {
 579   return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit);
 580 }
 581
 582 /// SimplifyMulInst - Given operands for a Mul, see if we can
 583 /// fold the result.  If not, this returns null.
 584 static Value *SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD,
 585                               const DominatorTree *DT, unsigned MaxRecurse) {
 586   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 587     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 588       Constant *Ops[] = { CLHS, CRHS };
 589       return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(),
 590                                       Ops, 2, TD);
 591     }
 592
 593     // Canonicalize the constant to the RHS.
 594     std::swap(Op0, Op1);
 595   }
 596
 597   // X * undef -> 0
 598   if (isa<UndefValue>(Op1))
 599     return Constant::getNullValue(Op0->getType());
 600
 601   // X * 0 -> 0
 602   if (match(Op1, m_Zero()))
 603     return Op1;
 604
 605   // X * 1 -> X
 606   if (match(Op1, m_One()))
 607     return Op0;
 608
 609   /// i1 mul -> and.
 610   if (!MaxRecurse && Op0->getType()->isIntegerTy(1))
 611     return SimplifyAndInst(Op0, Op1, TD, DT, MaxRecurse-1);
 612
 613   // Try some generic simplifications for associative operations.
 614   if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, TD, DT,
 615                                           MaxRecurse))
 616     return V;
 617
 618   // Mul distributes over Add.  Try some generic simplifications based on this.
 619   if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add,
 620                              TD, DT, MaxRecurse))
 621     return V;
 622
 623   // If the operation is with the result of a select instruction, check whether
 624   // operating on either branch of the select always yields the same value.
 625   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
 626     if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, TD, DT,
 627                                          MaxRecurse))
 628       return V;
 629
 630   // If the operation is with the result of a phi instruction, check whether
 631   // operating on all incoming values of the phi always yields the same value.
 632   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
 633     if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, TD, DT,
 634                                       MaxRecurse))
 635       return V;
 636
 637   return 0;
 638 }
 639
 640 Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD,
 641                              const DominatorTree *DT) {
 642   return ::SimplifyMulInst(Op0, Op1, TD, DT, RecursionLimit);
 643 }
 644
 645 /// SimplifyAndInst - Given operands for an And, see if we can
 646 /// fold the result.  If not, this returns null.
 647 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
 648                               const DominatorTree *DT, unsigned MaxRecurse) {
 649   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 650     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 651       Constant *Ops[] = { CLHS, CRHS };
 652       return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
 653                                       Ops, 2, TD);
 654     }
 655
 656     // Canonicalize the constant to the RHS.
 657     std::swap(Op0, Op1);
 658   }
 659
 660   // X & undef -> 0
 661   if (isa<UndefValue>(Op1))
 662     return Constant::getNullValue(Op0->getType());
 663
 664   // X & X = X
 665   if (Op0 == Op1)
 666     return Op0;
 667
 668   // X & 0 = 0
 669   if (match(Op1, m_Zero()))
 670     return Op1;
 671
 672   // X & -1 = X
 673   if (match(Op1, m_AllOnes()))
 674     return Op0;
 675
 676   // A & ~A  =  ~A & A  =  0
 677   Value *A = 0, *B = 0;
 678   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
 679       (match(Op1, m_Not(m_Value(A))) && A == Op0))
 680     return Constant::getNullValue(Op0->getType());
 681
 682   // (A | ?) & A = A
 683   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
 684       (A == Op1 || B == Op1))
 685     return Op1;
 686
 687   // A & (A | ?) = A
 688   if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
 689       (A == Op0 || B == Op0))
 690     return Op0;
 691
 692   // Try some generic simplifications for associative operations.
 693   if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, DT,
 694                                           MaxRecurse))
 695     return V;
 696
 697   // And distributes over Or.  Try some generic simplifications based on this.
 698   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
 699                              TD, DT, MaxRecurse))
 700     return V;
 701
 702   // And distributes over Xor.  Try some generic simplifications based on this.
 703   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor,
 704                              TD, DT, MaxRecurse))
 705     return V;
 706
 707   // Or distributes over And.  Try some generic simplifications based on this.
 708   if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or,
 709                                 TD, DT, MaxRecurse))
 710     return V;
 711
 712   // If the operation is with the result of a select instruction, check whether
 713   // operating on either branch of the select always yields the same value.
 714   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
 715     if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT,
 716                                          MaxRecurse))
 717       return V;
 718
 719   // If the operation is with the result of a phi instruction, check whether
 720   // operating on all incoming values of the phi always yields the same value.
 721   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
 722     if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT,
 723                                       MaxRecurse))
 724       return V;
 725
 726   return 0;
 727 }
 728
 729 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
 730                              const DominatorTree *DT) {
 731   return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit);
 732 }
 733
 734 /// SimplifyOrInst - Given operands for an Or, see if we can
 735 /// fold the result.  If not, this returns null.
 736 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
 737                              const DominatorTree *DT, unsigned MaxRecurse) {
 738   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 739     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 740       Constant *Ops[] = { CLHS, CRHS };
 741       return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
 742                                       Ops, 2, TD);
 743     }
 744
 745     // Canonicalize the constant to the RHS.
 746     std::swap(Op0, Op1);
 747   }
 748
 749   // X | undef -> -1
 750   if (isa<UndefValue>(Op1))
 751     return Constant::getAllOnesValue(Op0->getType());
 752
 753   // X | X = X
 754   if (Op0 == Op1)
 755     return Op0;
 756
 757   // X | 0 = X
 758   if (match(Op1, m_Zero()))
 759     return Op0;
 760
 761   // X | -1 = -1
 762   if (match(Op1, m_AllOnes()))
 763     return Op1;
 764
 765   // A | ~A  =  ~A | A  =  -1
 766   Value *A = 0, *B = 0;
 767   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
 768       (match(Op1, m_Not(m_Value(A))) && A == Op0))
 769     return Constant::getAllOnesValue(Op0->getType());
 770
 771   // (A & ?) | A = A
 772   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
 773       (A == Op1 || B == Op1))
 774     return Op1;
 775
 776   // A | (A & ?) = A
 777   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
 778       (A == Op0 || B == Op0))
 779     return Op0;
 780
 781   // Try some generic simplifications for associative operations.
 782   if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, DT,
 783                                           MaxRecurse))
 784     return V;
 785
 786   // Or distributes over And.  Try some generic simplifications based on this.
 787   if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And,
 788                              TD, DT, MaxRecurse))
 789     return V;
 790
 791   // And distributes over Or.  Try some generic simplifications based on this.
 792   if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And,
 793                                 TD, DT, MaxRecurse))
 794     return V;
 795
 796   // If the operation is with the result of a select instruction, check whether
 797   // operating on either branch of the select always yields the same value.
 798   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
 799     if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT,
 800                                          MaxRecurse))
 801       return V;
 802
 803   // If the operation is with the result of a phi instruction, check whether
 804   // operating on all incoming values of the phi always yields the same value.
 805   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
 806     if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT,
 807                                       MaxRecurse))
 808       return V;
 809
 810   return 0;
 811 }
 812
 813 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
 814                             const DominatorTree *DT) {
 815   return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit);
 816 }
 817
 818 /// SimplifyXorInst - Given operands for a Xor, see if we can
 819 /// fold the result.  If not, this returns null.
 820 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
 821                               const DominatorTree *DT, unsigned MaxRecurse) {
 822   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 823     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 824       Constant *Ops[] = { CLHS, CRHS };
 825       return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
 826                                       Ops, 2, TD);
 827     }
 828
 829     // Canonicalize the constant to the RHS.
 830     std::swap(Op0, Op1);
 831   }
 832
 833   // A ^ undef -> undef
 834   if (isa<UndefValue>(Op1))
 835     return Op1;
 836
 837   // A ^ 0 = A
 838   if (match(Op1, m_Zero()))
 839     return Op0;
 840
 841   // A ^ A = 0
 842   if (Op0 == Op1)
 843     return Constant::getNullValue(Op0->getType());
 844
 845   // A ^ ~A  =  ~A ^ A  =  -1
 846   Value *A = 0;
 847   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
 848       (match(Op1, m_Not(m_Value(A))) && A == Op0))
 849     return Constant::getAllOnesValue(Op0->getType());
 850
 851   // Try some generic simplifications for associative operations.
 852   if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, DT,
 853                                           MaxRecurse))
 854     return V;
 855
 856   // And distributes over Xor.  Try some generic simplifications based on this.
 857   if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And,
 858                                 TD, DT, MaxRecurse))
 859     return V;
 860
 861   // Threading Xor over selects and phi nodes is pointless, so don't bother.
 862   // Threading over the select in "A ^ select(cond, B, C)" means evaluating
 863   // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
 864   // only if B and C are equal.  If B and C are equal then (since we assume
 865   // that operands have already been simplified) "select(cond, B, C)" should
 866   // have been simplified to the common value of B and C already.  Analysing
 867   // "A^B" and "A^C" thus gains nothing, but costs compile time.  Similarly
 868   // for threading over phi nodes.
 869
 870   return 0;
 871 }
 872
 873 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
 874                              const DominatorTree *DT) {
 875   return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit);
 876 }
 877
 878 static const Type *GetCompareTy(Value *Op) {
 879   return CmpInst::makeCmpResultType(Op->getType());
 880 }
 881
 882 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
 883 /// fold the result.  If not, this returns null.
 884 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 885                                const TargetData *TD, const DominatorTree *DT,
 886                                unsigned MaxRecurse) {
 887   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
 888   assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
 889
 890   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
 891     if (Constant *CRHS = dyn_cast<Constant>(RHS))
 892       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
 893
 894     // If we have a constant, make sure it is on the RHS.
 895     std::swap(LHS, RHS);
 896     Pred = CmpInst::getSwappedPredicate(Pred);
 897   }
 898
 899   // ITy - This is the return type of the compare we're considering.
 900   const Type *ITy = GetCompareTy(LHS);
 901
 902   // icmp X, X -> true/false
 903   // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
 904   // because X could be 0.
 905   if (LHS == RHS || isa<UndefValue>(RHS))
 906     return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
 907
 908   // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
 909   // addresses never equal each other!  We already know that Op0 != Op1.
 910   if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
 911        isa<ConstantPointerNull>(LHS)) &&
 912       (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
 913        isa<ConstantPointerNull>(RHS)))
 914     return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
 915
 916   // See if we are doing a comparison with a constant.
 917   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
 918     // If we have an icmp le or icmp ge instruction, turn it into the
 919     // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
 920     // them being folded in the code below.
 921     switch (Pred) {
 922     default: break;
 923     case ICmpInst::ICMP_ULE:
 924       if (CI->isMaxValue(false))                 // A <=u MAX -> TRUE
 925         return ConstantInt::getTrue(CI->getContext());
 926       break;
 927     case ICmpInst::ICMP_SLE:
 928       if (CI->isMaxValue(true))                  // A <=s MAX -> TRUE
 929         return ConstantInt::getTrue(CI->getContext());
 930       break;
 931     case ICmpInst::ICMP_UGE:
 932       if (CI->isMinValue(false))                 // A >=u MIN -> TRUE
 933         return ConstantInt::getTrue(CI->getContext());
 934       break;
 935     case ICmpInst::ICMP_SGE:
 936       if (CI->isMinValue(true))                  // A >=s MIN -> TRUE
 937         return ConstantInt::getTrue(CI->getContext());
 938       break;
 939     }
 940   }
 941
 942   // If the comparison is with the result of a select instruction, check whether
 943   // comparing with either branch of the select always yields the same value.
 944   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
 945     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse))
 946       return V;
 947
 948   // If the comparison is with the result of a phi instruction, check whether
 949   // doing the compare with each incoming phi value yields a common result.
 950   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
 951     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse))
 952       return V;
 953
 954   return 0;
 955 }
 956
 957 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 958                               const TargetData *TD, const DominatorTree *DT) {
 959   return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
 960 }
 961
 962 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
 963 /// fold the result.  If not, this returns null.
 964 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 965                                const TargetData *TD, const DominatorTree *DT,
 966                                unsigned MaxRecurse) {
 967   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
 968   assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
 969
 970   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
 971     if (Constant *CRHS = dyn_cast<Constant>(RHS))
 972       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
 973
 974     // If we have a constant, make sure it is on the RHS.
 975     std::swap(LHS, RHS);
 976     Pred = CmpInst::getSwappedPredicate(Pred);
 977   }
 978
 979   // Fold trivial predicates.
 980   if (Pred == FCmpInst::FCMP_FALSE)
 981     return ConstantInt::get(GetCompareTy(LHS), 0);
 982   if (Pred == FCmpInst::FCMP_TRUE)
 983     return ConstantInt::get(GetCompareTy(LHS), 1);
 984
 985   if (isa<UndefValue>(RHS))                  // fcmp pred X, undef -> undef
 986     return UndefValue::get(GetCompareTy(LHS));
 987
 988   // fcmp x,x -> true/false.  Not all compares are foldable.
 989   if (LHS == RHS) {
 990     if (CmpInst::isTrueWhenEqual(Pred))
 991       return ConstantInt::get(GetCompareTy(LHS), 1);
 992     if (CmpInst::isFalseWhenEqual(Pred))
 993       return ConstantInt::get(GetCompareTy(LHS), 0);
 994   }
 995
 996   // Handle fcmp with constant RHS
 997   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
 998     // If the constant is a nan, see if we can fold the comparison based on it.
 999     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
1000       if (CFP->getValueAPF().isNaN()) {
1001         if (FCmpInst::isOrdered(Pred))   // True "if ordered and foo"
1002           return ConstantInt::getFalse(CFP->getContext());
1003         assert(FCmpInst::isUnordered(Pred) &&
1004                "Comparison must be either ordered or unordered!");
1005         // True if unordered.
1006         return ConstantInt::getTrue(CFP->getContext());
1007       }
1008       // Check whether the constant is an infinity.
1009       if (CFP->getValueAPF().isInfinity()) {
1010         if (CFP->getValueAPF().isNegative()) {
1011           switch (Pred) {
1012           case FCmpInst::FCMP_OLT:
1013             // No value is ordered and less than negative infinity.
1014             return ConstantInt::getFalse(CFP->getContext());
1015           case FCmpInst::FCMP_UGE:
1016             // All values are unordered with or at least negative infinity.
1017             return ConstantInt::getTrue(CFP->getContext());
1018           default:
1019             break;
1020           }
1021         } else {
1022           switch (Pred) {
1023           case FCmpInst::FCMP_OGT:
1024             // No value is ordered and greater than infinity.
1025             return ConstantInt::getFalse(CFP->getContext());
1026           case FCmpInst::FCMP_ULE:
1027             // All values are unordered with and at most infinity.
1028             return ConstantInt::getTrue(CFP->getContext());
1029           default:
1030             break;
1031           }
1032         }
1033       }
1034     }
1035   }
1036
1037   // If the comparison is with the result of a select instruction, check whether
1038   // comparing with either branch of the select always yields the same value.
1039   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
1040     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse))
1041       return V;
1042
1043   // If the comparison is with the result of a phi instruction, check whether
1044   // doing the compare with each incoming phi value yields a common result.
1045   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
1046     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse))
1047       return V;
1048
1049   return 0;
1050 }
1051
1052 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1053                               const TargetData *TD, const DominatorTree *DT) {
1054   return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
1055 }
1056
1057 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
1058 /// the result.  If not, this returns null.
1059 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
1060                                 const TargetData *TD, const DominatorTree *) {
1061   // select true, X, Y  -> X
1062   // select false, X, Y -> Y
1063   if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
1064     return CB->getZExtValue() ? TrueVal : FalseVal;
1065
1066   // select C, X, X -> X
1067   if (TrueVal == FalseVal)
1068     return TrueVal;
1069
1070   if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
1071     return FalseVal;
1072   if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
1073     return TrueVal;
1074   if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
1075     if (isa<Constant>(TrueVal))
1076       return TrueVal;
1077     return FalseVal;
1078   }
1079
1080   return 0;
1081 }
1082
1083 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
1084 /// fold the result.  If not, this returns null.
1085 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
1086                              const TargetData *TD, const DominatorTree *) {
1087   // The type of the GEP pointer operand.
1088   const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType());
1089
1090   // getelementptr P -> P.
1091   if (NumOps == 1)
1092     return Ops[0];
1093
1094   if (isa<UndefValue>(Ops[0])) {
1095     // Compute the (pointer) type returned by the GEP instruction.
1096     const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1],
1097                                                              NumOps-1);
1098     const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace());
1099     return UndefValue::get(GEPTy);
1100   }
1101
1102   if (NumOps == 2) {
1103     // getelementptr P, 0 -> P.
1104     if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
1105       if (C->isZero())
1106         return Ops[0];
1107     // getelementptr P, N -> P if P points to a type of zero size.
1108     if (TD) {
1109       const Type *Ty = PtrTy->getElementType();
1110       if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0)
1111         return Ops[0];
1112     }
1113   }
1114
1115   // Check to see if this is constant foldable.
1116   for (unsigned i = 0; i != NumOps; ++i)
1117     if (!isa<Constant>(Ops[i]))
1118       return 0;
1119
1120   return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
1121                                         (Constant *const*)Ops+1, NumOps-1);
1122 }
1123
1124 /// SimplifyPHINode - See if we can fold the given phi.  If not, returns null.
1125 static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
1126   // If all of the PHI's incoming values are the same then replace the PHI node
1127   // with the common value.
1128   Value *CommonValue = 0;
1129   bool HasUndefInput = false;
1130   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1131     Value *Incoming = PN->getIncomingValue(i);
1132     // If the incoming value is the phi node itself, it can safely be skipped.
1133     if (Incoming == PN) continue;
1134     if (isa<UndefValue>(Incoming)) {
1135       // Remember that we saw an undef value, but otherwise ignore them.
1136       HasUndefInput = true;
1137       continue;
1138     }
1139     if (CommonValue && Incoming != CommonValue)
1140       return 0;  // Not the same, bail out.
1141     CommonValue = Incoming;
1142   }
1143
1144   // If CommonValue is null then all of the incoming values were either undef or
1145   // equal to the phi node itself.
1146   if (!CommonValue)
1147     return UndefValue::get(PN->getType());
1148
1149   // If we have a PHI node like phi(X, undef, X), where X is defined by some
1150   // instruction, we cannot return X as the result of the PHI node unless it
1151   // dominates the PHI block.
1152   if (HasUndefInput)
1153     return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
1154
1155   return CommonValue;
1156 }
1157
1158
1159 //=== Helper functions for higher up the class hierarchy.
1160
1161 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
1162 /// fold the result.  If not, this returns null.
1163 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
1164                             const TargetData *TD, const DominatorTree *DT,
1165                             unsigned MaxRecurse) {
1166   switch (Opcode) {
1167   case Instruction::Add: return SimplifyAddInst(LHS, RHS, /* isNSW */ false,
1168                                                 /* isNUW */ false, TD, DT,
1169                                                 MaxRecurse);
1170   case Instruction::Sub: return SimplifySubInst(LHS, RHS, /* isNSW */ false,
1171                                                 /* isNUW */ false, TD, DT,
1172                                                 MaxRecurse);
1173   case Instruction::Mul: return SimplifyMulInst(LHS, RHS, TD, DT, MaxRecurse);
1174   case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse);
1175   case Instruction::Or:  return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse);
1176   case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse);
1177   default:
1178     if (Constant *CLHS = dyn_cast<Constant>(LHS))
1179       if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
1180         Constant *COps[] = {CLHS, CRHS};
1181         return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
1182       }
1183
1184     // If the operation is associative, try some generic simplifications.
1185     if (Instruction::isAssociative(Opcode))
1186       if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, DT,
1187                                               MaxRecurse))
1188         return V;
1189
1190     // If the operation is with the result of a select instruction, check whether
1191     // operating on either branch of the select always yields the same value.
1192     if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
1193       if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT,
1194                                            MaxRecurse))
1195         return V;
1196
1197     // If the operation is with the result of a phi instruction, check whether
1198     // operating on all incoming values of the phi always yields the same value.
1199     if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
1200       if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse))
1201         return V;
1202
1203     return 0;
1204   }
1205 }
1206
1207 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
1208                            const TargetData *TD, const DominatorTree *DT) {
1209   return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit);
1210 }
1211
1212 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
1213 /// fold the result.
1214 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1215                               const TargetData *TD, const DominatorTree *DT,
1216                               unsigned MaxRecurse) {
1217   if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
1218     return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
1219   return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
1220 }
1221
1222 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1223                              const TargetData *TD, const DominatorTree *DT) {
1224   return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
1225 }
1226
1227 /// SimplifyInstruction - See if we can compute a simplified version of this
1228 /// instruction.  If not, this returns null.
1229 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
1230                                  const DominatorTree *DT) {
1231   Value *Result;
1232
1233   switch (I->getOpcode()) {
1234   default:
1235     Result = ConstantFoldInstruction(I, TD);
1236     break;
1237   case Instruction::Add:
1238     Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
1239                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
1240                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
1241                              TD, DT);
1242     break;
1243   case Instruction::Sub:
1244     Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
1245                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
1246                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
1247                              TD, DT);
1248     break;
1249   case Instruction::Mul:
1250     Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, DT);
1251     break;
1252   case Instruction::And:
1253     Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT);
1254     break;
1255   case Instruction::Or:
1256     Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT);
1257     break;
1258   case Instruction::Xor:
1259     Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT);
1260     break;
1261   case Instruction::ICmp:
1262     Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
1263                               I->getOperand(0), I->getOperand(1), TD, DT);
1264     break;
1265   case Instruction::FCmp:
1266     Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
1267                               I->getOperand(0), I->getOperand(1), TD, DT);
1268     break;
1269   case Instruction::Select:
1270     Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
1271                                 I->getOperand(2), TD, DT);
1272     break;
1273   case Instruction::GetElementPtr: {
1274     SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
1275     Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT);
1276     break;
1277   }
1278   case Instruction::PHI:
1279     Result = SimplifyPHINode(cast<PHINode>(I), DT);
1280     break;
1281   }
1282
1283   /// If called on unreachable code, the above logic may report that the
1284   /// instruction simplified to itself.  Make life easier for users by
1285   /// detecting that case here, returning a safe value instead.
1286   return Result == I ? UndefValue::get(I->getType()) : Result;
1287 }
1288
1289 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
1290 /// delete the From instruction.  In addition to a basic RAUW, this does a
1291 /// recursive simplification of the newly formed instructions.  This catches
1292 /// things where one simplification exposes other opportunities.  This only
1293 /// simplifies and deletes scalar operations, it does not change the CFG.
1294 ///
1295 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
1296                                      const TargetData *TD,
1297                                      const DominatorTree *DT) {
1298   assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
1299
1300   // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
1301   // we can know if it gets deleted out from under us or replaced in a
1302   // recursive simplification.
1303   WeakVH FromHandle(From);
1304   WeakVH ToHandle(To);
1305
1306   while (!From->use_empty()) {
1307     // Update the instruction to use the new value.
1308     Use &TheUse = From->use_begin().getUse();
1309     Instruction *User = cast<Instruction>(TheUse.getUser());
1310     TheUse = To;
1311
1312     // Check to see if the instruction can be folded due to the operand
1313     // replacement.  For example changing (or X, Y) into (or X, -1) can replace
1314     // the 'or' with -1.
1315     Value *SimplifiedVal;
1316     {
1317       // Sanity check to make sure 'User' doesn't dangle across
1318       // SimplifyInstruction.
1319       AssertingVH<> UserHandle(User);
1320
1321       SimplifiedVal = SimplifyInstruction(User, TD, DT);
1322       if (SimplifiedVal == 0) continue;
1323     }
1324
1325     // Recursively simplify this user to the new value.
1326     ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
1327     From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
1328     To = ToHandle;
1329
1330     assert(ToHandle && "To value deleted by recursive simplification?");
1331
1332     // If the recursive simplification ended up revisiting and deleting
1333     // 'From' then we're done.
1334     if (From == 0)
1335       return;
1336   }
1337
1338   // If 'From' has value handles referring to it, do a real RAUW to update them.
1339   From->replaceAllUsesWith(To);
1340
1341   From->eraseFromParent();
1342 }