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