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   // ITy - This is the return type of the compare we're considering.
 942   const Type *ITy = GetCompareTy(LHS);
 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   // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
 951   // addresses never equal each other!  We already know that Op0 != Op1.
 952   if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
 953        isa<ConstantPointerNull>(LHS)) &&
 954       (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
 955        isa<ConstantPointerNull>(RHS)))
 956     return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
 957
 958   // See if we are doing a comparison with a constant.
 959   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
 960     // If we have an icmp le or icmp ge instruction, turn it into the
 961     // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
 962     // them being folded in the code below.
 963     switch (Pred) {
 964     default: break;
 965     case ICmpInst::ICMP_ULE:
 966       if (CI->isMaxValue(false))                 // A <=u MAX -> TRUE
 967         return ConstantInt::getTrue(CI->getContext());
 968       break;
 969     case ICmpInst::ICMP_SLE:
 970       if (CI->isMaxValue(true))                  // A <=s MAX -> TRUE
 971         return ConstantInt::getTrue(CI->getContext());
 972       break;
 973     case ICmpInst::ICMP_UGE:
 974       if (CI->isMinValue(false))                 // A >=u MIN -> TRUE
 975         return ConstantInt::getTrue(CI->getContext());
 976       break;
 977     case ICmpInst::ICMP_SGE:
 978       if (CI->isMinValue(true))                  // A >=s MIN -> TRUE
 979         return ConstantInt::getTrue(CI->getContext());
 980       break;
 981     }
 982   }
 983
 984   // If the comparison is with the result of a select instruction, check whether
 985   // comparing with either branch of the select always yields the same value.
 986   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
 987     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse))
 988       return V;
 989
 990   // If the comparison is with the result of a phi instruction, check whether
 991   // doing the compare with each incoming phi value yields a common result.
 992   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
 993     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse))
 994       return V;
 995
 996   return 0;
 997 }
 998
 999 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1000                               const TargetData *TD, const DominatorTree *DT) {
1001   return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
1002 }
1003
1004 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
1005 /// fold the result.  If not, this returns null.
1006 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1007                                const TargetData *TD, const DominatorTree *DT,
1008                                unsigned MaxRecurse) {
1009   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
1010   assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
1011
1012   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
1013     if (Constant *CRHS = dyn_cast<Constant>(RHS))
1014       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
1015
1016     // If we have a constant, make sure it is on the RHS.
1017     std::swap(LHS, RHS);
1018     Pred = CmpInst::getSwappedPredicate(Pred);
1019   }
1020
1021   // Fold trivial predicates.
1022   if (Pred == FCmpInst::FCMP_FALSE)
1023     return ConstantInt::get(GetCompareTy(LHS), 0);
1024   if (Pred == FCmpInst::FCMP_TRUE)
1025     return ConstantInt::get(GetCompareTy(LHS), 1);
1026
1027   if (isa<UndefValue>(RHS))                  // fcmp pred X, undef -> undef
1028     return UndefValue::get(GetCompareTy(LHS));
1029
1030   // fcmp x,x -> true/false.  Not all compares are foldable.
1031   if (LHS == RHS) {
1032     if (CmpInst::isTrueWhenEqual(Pred))
1033       return ConstantInt::get(GetCompareTy(LHS), 1);
1034     if (CmpInst::isFalseWhenEqual(Pred))
1035       return ConstantInt::get(GetCompareTy(LHS), 0);
1036   }
1037
1038   // Handle fcmp with constant RHS
1039   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
1040     // If the constant is a nan, see if we can fold the comparison based on it.
1041     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
1042       if (CFP->getValueAPF().isNaN()) {
1043         if (FCmpInst::isOrdered(Pred))   // True "if ordered and foo"
1044           return ConstantInt::getFalse(CFP->getContext());
1045         assert(FCmpInst::isUnordered(Pred) &&
1046                "Comparison must be either ordered or unordered!");
1047         // True if unordered.
1048         return ConstantInt::getTrue(CFP->getContext());
1049       }
1050       // Check whether the constant is an infinity.
1051       if (CFP->getValueAPF().isInfinity()) {
1052         if (CFP->getValueAPF().isNegative()) {
1053           switch (Pred) {
1054           case FCmpInst::FCMP_OLT:
1055             // No value is ordered and less than negative infinity.
1056             return ConstantInt::getFalse(CFP->getContext());
1057           case FCmpInst::FCMP_UGE:
1058             // All values are unordered with or at least negative infinity.
1059             return ConstantInt::getTrue(CFP->getContext());
1060           default:
1061             break;
1062           }
1063         } else {
1064           switch (Pred) {
1065           case FCmpInst::FCMP_OGT:
1066             // No value is ordered and greater than infinity.
1067             return ConstantInt::getFalse(CFP->getContext());
1068           case FCmpInst::FCMP_ULE:
1069             // All values are unordered with and at most infinity.
1070             return ConstantInt::getTrue(CFP->getContext());
1071           default:
1072             break;
1073           }
1074         }
1075       }
1076     }
1077   }
1078
1079   // If the comparison is with the result of a select instruction, check whether
1080   // comparing with either branch of the select always yields the same value.
1081   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
1082     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse))
1083       return V;
1084
1085   // If the comparison is with the result of a phi instruction, check whether
1086   // doing the compare with each incoming phi value yields a common result.
1087   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
1088     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse))
1089       return V;
1090
1091   return 0;
1092 }
1093
1094 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1095                               const TargetData *TD, const DominatorTree *DT) {
1096   return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
1097 }
1098
1099 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
1100 /// the result.  If not, this returns null.
1101 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
1102                                 const TargetData *TD, const DominatorTree *) {
1103   // select true, X, Y  -> X
1104   // select false, X, Y -> Y
1105   if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
1106     return CB->getZExtValue() ? TrueVal : FalseVal;
1107
1108   // select C, X, X -> X
1109   if (TrueVal == FalseVal)
1110     return TrueVal;
1111
1112   if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
1113     return FalseVal;
1114   if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
1115     return TrueVal;
1116   if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
1117     if (isa<Constant>(TrueVal))
1118       return TrueVal;
1119     return FalseVal;
1120   }
1121
1122   return 0;
1123 }
1124
1125 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
1126 /// fold the result.  If not, this returns null.
1127 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
1128                              const TargetData *TD, const DominatorTree *) {
1129   // The type of the GEP pointer operand.
1130   const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType());
1131
1132   // getelementptr P -> P.
1133   if (NumOps == 1)
1134     return Ops[0];
1135
1136   if (isa<UndefValue>(Ops[0])) {
1137     // Compute the (pointer) type returned by the GEP instruction.
1138     const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1],
1139                                                              NumOps-1);
1140     const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace());
1141     return UndefValue::get(GEPTy);
1142   }
1143
1144   if (NumOps == 2) {
1145     // getelementptr P, 0 -> P.
1146     if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
1147       if (C->isZero())
1148         return Ops[0];
1149     // getelementptr P, N -> P if P points to a type of zero size.
1150     if (TD) {
1151       const Type *Ty = PtrTy->getElementType();
1152       if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0)
1153         return Ops[0];
1154     }
1155   }
1156
1157   // Check to see if this is constant foldable.
1158   for (unsigned i = 0; i != NumOps; ++i)
1159     if (!isa<Constant>(Ops[i]))
1160       return 0;
1161
1162   return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
1163                                         (Constant *const*)Ops+1, NumOps-1);
1164 }
1165
1166 /// SimplifyPHINode - See if we can fold the given phi.  If not, returns null.
1167 static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
1168   // If all of the PHI's incoming values are the same then replace the PHI node
1169   // with the common value.
1170   Value *CommonValue = 0;
1171   bool HasUndefInput = false;
1172   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1173     Value *Incoming = PN->getIncomingValue(i);
1174     // If the incoming value is the phi node itself, it can safely be skipped.
1175     if (Incoming == PN) continue;
1176     if (isa<UndefValue>(Incoming)) {
1177       // Remember that we saw an undef value, but otherwise ignore them.
1178       HasUndefInput = true;
1179       continue;
1180     }
1181     if (CommonValue && Incoming != CommonValue)
1182       return 0;  // Not the same, bail out.
1183     CommonValue = Incoming;
1184   }
1185
1186   // If CommonValue is null then all of the incoming values were either undef or
1187   // equal to the phi node itself.
1188   if (!CommonValue)
1189     return UndefValue::get(PN->getType());
1190
1191   // If we have a PHI node like phi(X, undef, X), where X is defined by some
1192   // instruction, we cannot return X as the result of the PHI node unless it
1193   // dominates the PHI block.
1194   if (HasUndefInput)
1195     return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
1196
1197   return CommonValue;
1198 }
1199
1200
1201 //=== Helper functions for higher up the class hierarchy.
1202
1203 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
1204 /// fold the result.  If not, this returns null.
1205 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
1206                             const TargetData *TD, const DominatorTree *DT,
1207                             unsigned MaxRecurse) {
1208   switch (Opcode) {
1209   case Instruction::Add: return SimplifyAddInst(LHS, RHS, /* isNSW */ false,
1210                                                 /* isNUW */ false, TD, DT,
1211                                                 MaxRecurse);
1212   case Instruction::Sub: return SimplifySubInst(LHS, RHS, /* isNSW */ false,
1213                                                 /* isNUW */ false, TD, DT,
1214                                                 MaxRecurse);
1215   case Instruction::Mul: return SimplifyMulInst(LHS, RHS, TD, DT, MaxRecurse);
1216   case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse);
1217   case Instruction::Or:  return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse);
1218   case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse);
1219   default:
1220     if (Constant *CLHS = dyn_cast<Constant>(LHS))
1221       if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
1222         Constant *COps[] = {CLHS, CRHS};
1223         return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
1224       }
1225
1226     // If the operation is associative, try some generic simplifications.
1227     if (Instruction::isAssociative(Opcode))
1228       if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, DT,
1229                                               MaxRecurse))
1230         return V;
1231
1232     // If the operation is with the result of a select instruction, check whether
1233     // operating on either branch of the select always yields the same value.
1234     if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
1235       if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT,
1236                                            MaxRecurse))
1237         return V;
1238
1239     // If the operation is with the result of a phi instruction, check whether
1240     // operating on all incoming values of the phi always yields the same value.
1241     if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
1242       if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse))
1243         return V;
1244
1245     return 0;
1246   }
1247 }
1248
1249 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
1250                            const TargetData *TD, const DominatorTree *DT) {
1251   return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit);
1252 }
1253
1254 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
1255 /// fold the result.
1256 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1257                               const TargetData *TD, const DominatorTree *DT,
1258                               unsigned MaxRecurse) {
1259   if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
1260     return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
1261   return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
1262 }
1263
1264 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
1265                              const TargetData *TD, const DominatorTree *DT) {
1266   return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
1267 }
1268
1269 /// SimplifyInstruction - See if we can compute a simplified version of this
1270 /// instruction.  If not, this returns null.
1271 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
1272                                  const DominatorTree *DT) {
1273   Value *Result;
1274
1275   switch (I->getOpcode()) {
1276   default:
1277     Result = ConstantFoldInstruction(I, TD);
1278     break;
1279   case Instruction::Add:
1280     Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
1281                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
1282                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
1283                              TD, DT);
1284     break;
1285   case Instruction::Sub:
1286     Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
1287                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
1288                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
1289                              TD, DT);
1290     break;
1291   case Instruction::Mul:
1292     Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, DT);
1293     break;
1294   case Instruction::And:
1295     Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT);
1296     break;
1297   case Instruction::Or:
1298     Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT);
1299     break;
1300   case Instruction::Xor:
1301     Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT);
1302     break;
1303   case Instruction::ICmp:
1304     Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
1305                               I->getOperand(0), I->getOperand(1), TD, DT);
1306     break;
1307   case Instruction::FCmp:
1308     Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
1309                               I->getOperand(0), I->getOperand(1), TD, DT);
1310     break;
1311   case Instruction::Select:
1312     Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
1313                                 I->getOperand(2), TD, DT);
1314     break;
1315   case Instruction::GetElementPtr: {
1316     SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
1317     Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT);
1318     break;
1319   }
1320   case Instruction::PHI:
1321     Result = SimplifyPHINode(cast<PHINode>(I), DT);
1322     break;
1323   }
1324
1325   /// If called on unreachable code, the above logic may report that the
1326   /// instruction simplified to itself.  Make life easier for users by
1327   /// detecting that case here, returning a safe value instead.
1328   return Result == I ? UndefValue::get(I->getType()) : Result;
1329 }
1330
1331 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
1332 /// delete the From instruction.  In addition to a basic RAUW, this does a
1333 /// recursive simplification of the newly formed instructions.  This catches
1334 /// things where one simplification exposes other opportunities.  This only
1335 /// simplifies and deletes scalar operations, it does not change the CFG.
1336 ///
1337 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
1338                                      const TargetData *TD,
1339                                      const DominatorTree *DT) {
1340   assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
1341
1342   // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
1343   // we can know if it gets deleted out from under us or replaced in a
1344   // recursive simplification.
1345   WeakVH FromHandle(From);
1346   WeakVH ToHandle(To);
1347
1348   while (!From->use_empty()) {
1349     // Update the instruction to use the new value.
1350     Use &TheUse = From->use_begin().getUse();
1351     Instruction *User = cast<Instruction>(TheUse.getUser());
1352     TheUse = To;
1353
1354     // Check to see if the instruction can be folded due to the operand
1355     // replacement.  For example changing (or X, Y) into (or X, -1) can replace
1356     // the 'or' with -1.
1357     Value *SimplifiedVal;
1358     {
1359       // Sanity check to make sure 'User' doesn't dangle across
1360       // SimplifyInstruction.
1361       AssertingVH<> UserHandle(User);
1362
1363       SimplifiedVal = SimplifyInstruction(User, TD, DT);
1364       if (SimplifiedVal == 0) continue;
1365     }
1366
1367     // Recursively simplify this user to the new value.
1368     ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
1369     From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
1370     To = ToHandle;
1371
1372     assert(ToHandle && "To value deleted by recursive simplification?");
1373
1374     // If the recursive simplification ended up revisiting and deleting
1375     // 'From' then we're done.
1376     if (From == 0)
1377       return;
1378   }
1379
1380   // If 'From' has value handles referring to it, do a real RAUW to update them.
1381   From->replaceAllUsesWith(To);
1382
1383   From->eraseFromParent();
1384 }