lib/Analysis/InstructionSimplify.cpp

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