lib/Analysis/InstructionSimplify.cpp

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