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 /// ThreadBinOpOverSelect - In the case of a binary operation with a select
  57 /// instruction as an operand, try to simplify the binop by seeing whether
  58 /// evaluating it on both branches of the select results in the same value.
  59 /// Returns the common value if so, otherwise returns null.
  60 static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
  61                                     const TargetData *TD,
  62                                     const DominatorTree *DT,
  63                                     unsigned MaxRecurse) {
  64   SelectInst *SI;
  65   if (isa<SelectInst>(LHS)) {
  66     SI = cast<SelectInst>(LHS);
  67   } else {
  68     assert(isa<SelectInst>(RHS) && "No select instruction operand!");
  69     SI = cast<SelectInst>(RHS);
  70   }
  71
  72   // Evaluate the BinOp on the true and false branches of the select.
  73   Value *TV;
  74   Value *FV;
  75   if (SI == LHS) {
  76     TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse);
  77     FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse);
  78   } else {
  79     TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse);
  80     FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse);
  81   }
  82
  83   // If they simplified to the same value, then return the common value.
  84   // If they both failed to simplify then return null.
  85   if (TV == FV)
  86     return TV;
  87
  88   // If one branch simplified to undef, return the other one.
  89   if (TV && isa<UndefValue>(TV))
  90     return FV;
  91   if (FV && isa<UndefValue>(FV))
  92     return TV;
  93
  94   // If applying the operation did not change the true and false select values,
  95   // then the result of the binop is the select itself.
  96   if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
  97     return SI;
  98
  99   // If one branch simplified and the other did not, and the simplified
 100   // value is equal to the unsimplified one, return the simplified value.
 101   // For example, select (cond, X, X & Z) & Z -> X & Z.
 102   if ((FV && !TV) || (TV && !FV)) {
 103     // Check that the simplified value has the form "X op Y" where "op" is the
 104     // same as the original operation.
 105     Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
 106     if (Simplified && Simplified->getOpcode() == Opcode) {
 107       // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
 108       // We already know that "op" is the same as for the simplified value.  See
 109       // if the operands match too.  If so, return the simplified value.
 110       Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
 111       Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
 112       Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
 113       if (Simplified->getOperand(0) == UnsimplifiedLHS &&
 114           Simplified->getOperand(1) == UnsimplifiedRHS)
 115         return Simplified;
 116       if (Simplified->isCommutative() &&
 117           Simplified->getOperand(1) == UnsimplifiedLHS &&
 118           Simplified->getOperand(0) == UnsimplifiedRHS)
 119         return Simplified;
 120     }
 121   }
 122
 123   return 0;
 124 }
 125
 126 /// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
 127 /// try to simplify the comparison by seeing whether both branches of the select
 128 /// result in the same value.  Returns the common value if so, otherwise returns
 129 /// null.
 130 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
 131                                   Value *RHS, const TargetData *TD,
 132                                   const DominatorTree *DT,
 133                                   unsigned MaxRecurse) {
 134   // Make sure the select is on the LHS.
 135   if (!isa<SelectInst>(LHS)) {
 136     std::swap(LHS, RHS);
 137     Pred = CmpInst::getSwappedPredicate(Pred);
 138   }
 139   assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
 140   SelectInst *SI = cast<SelectInst>(LHS);
 141
 142   // Now that we have "cmp select(cond, TV, FV), RHS", analyse it.
 143   // Does "cmp TV, RHS" simplify?
 144   if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT,
 145                                     MaxRecurse))
 146     // It does!  Does "cmp FV, RHS" simplify?
 147     if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT,
 148                                       MaxRecurse))
 149       // It does!  If they simplified to the same value, then use it as the
 150       // result of the original comparison.
 151       if (TCmp == FCmp)
 152         return TCmp;
 153   return 0;
 154 }
 155
 156 /// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
 157 /// is a PHI instruction, try to simplify the binop by seeing whether evaluating
 158 /// it on the incoming phi values yields the same result for every value.  If so
 159 /// returns the common value, otherwise returns null.
 160 static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
 161                                  const TargetData *TD, const DominatorTree *DT,
 162                                  unsigned MaxRecurse) {
 163   PHINode *PI;
 164   if (isa<PHINode>(LHS)) {
 165     PI = cast<PHINode>(LHS);
 166     // Bail out if RHS and the phi may be mutually interdependent due to a loop.
 167     if (!ValueDominatesPHI(RHS, PI, DT))
 168       return 0;
 169   } else {
 170     assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
 171     PI = cast<PHINode>(RHS);
 172     // Bail out if LHS and the phi may be mutually interdependent due to a loop.
 173     if (!ValueDominatesPHI(LHS, PI, DT))
 174       return 0;
 175   }
 176
 177   // Evaluate the BinOp on the incoming phi values.
 178   Value *CommonValue = 0;
 179   for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
 180     Value *Incoming = PI->getIncomingValue(i);
 181     // If the incoming value is the phi node itself, it can safely be skipped.
 182     if (Incoming == PI) continue;
 183     Value *V = PI == LHS ?
 184       SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) :
 185       SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse);
 186     // If the operation failed to simplify, or simplified to a different value
 187     // to previously, then give up.
 188     if (!V || (CommonValue && V != CommonValue))
 189       return 0;
 190     CommonValue = V;
 191   }
 192
 193   return CommonValue;
 194 }
 195
 196 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
 197 /// try to simplify the comparison by seeing whether comparing with all of the
 198 /// incoming phi values yields the same result every time.  If so returns the
 199 /// common result, otherwise returns null.
 200 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
 201                                const TargetData *TD, const DominatorTree *DT,
 202                                unsigned MaxRecurse) {
 203   // Make sure the phi is on the LHS.
 204   if (!isa<PHINode>(LHS)) {
 205     std::swap(LHS, RHS);
 206     Pred = CmpInst::getSwappedPredicate(Pred);
 207   }
 208   assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
 209   PHINode *PI = cast<PHINode>(LHS);
 210
 211   // Bail out if RHS and the phi may be mutually interdependent due to a loop.
 212   if (!ValueDominatesPHI(RHS, PI, DT))
 213     return 0;
 214
 215   // Evaluate the BinOp on the incoming phi values.
 216   Value *CommonValue = 0;
 217   for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
 218     Value *Incoming = PI->getIncomingValue(i);
 219     // If the incoming value is the phi node itself, it can safely be skipped.
 220     if (Incoming == PI) continue;
 221     Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse);
 222     // If the operation failed to simplify, or simplified to a different value
 223     // to previously, then give up.
 224     if (!V || (CommonValue && V != CommonValue))
 225       return 0;
 226     CommonValue = V;
 227   }
 228
 229   return CommonValue;
 230 }
 231
 232 /// SimplifyAddInst - Given operands for an Add, see if we can
 233 /// fold the result.  If not, this returns null.
 234 static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 235                               const TargetData *TD, const DominatorTree *DT,
 236                               unsigned MaxRecurse) {
 237   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 238     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 239       Constant *Ops[] = { CLHS, CRHS };
 240       return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
 241                                       Ops, 2, TD);
 242     }
 243
 244     // Canonicalize the constant to the RHS.
 245     std::swap(Op0, Op1);
 246   }
 247
 248   // X + undef -> undef
 249   if (isa<UndefValue>(Op1))
 250     return Op1;
 251
 252   // X + 0 -> X
 253   if (match(Op1, m_Zero()))
 254     return Op0;
 255
 256   // X + (Y - X) -> Y
 257   // (Y - X) + X -> Y
 258   // Eg: X + -X -> 0
 259   Value *Y = 0;
 260   if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
 261       match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
 262     return Y;
 263
 264   // X + ~X -> -1   since   ~X = -X-1
 265   if (match(Op0, m_Not(m_Specific(Op1))) ||
 266       match(Op1, m_Not(m_Specific(Op0))))
 267     return Constant::getAllOnesValue(Op0->getType());
 268
 269   // Threading Add over selects and phi nodes is pointless, so don't bother.
 270   // Threading over the select in "A + select(cond, B, C)" means evaluating
 271   // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
 272   // only if B and C are equal.  If B and C are equal then (since we assume
 273   // that operands have already been simplified) "select(cond, B, C)" should
 274   // have been simplified to the common value of B and C already.  Analysing
 275   // "A+B" and "A+C" thus gains nothing, but costs compile time.  Similarly
 276   // for threading over phi nodes.
 277
 278   return 0;
 279 }
 280
 281 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 282                              const TargetData *TD, const DominatorTree *DT) {
 283   return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit);
 284 }
 285
 286 /// SimplifySubInst - Given operands for a Sub, see if we can
 287 /// fold the result.  If not, this returns null.
 288 static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 289                               const TargetData *TD, const DominatorTree *,
 290                               unsigned MaxRecurse) {
 291   if (Constant *CLHS = dyn_cast<Constant>(Op0))
 292     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 293       Constant *Ops[] = { CLHS, CRHS };
 294       return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(),
 295                                       Ops, 2, TD);
 296     }
 297
 298   // X - undef -> undef
 299   // undef - X -> undef
 300   if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1))
 301     return UndefValue::get(Op0->getType());
 302
 303   // X - 0 -> X
 304   if (match(Op1, m_Zero()))
 305     return Op0;
 306
 307   // X - X -> 0
 308   if (Op0 == Op1)
 309     return Constant::getNullValue(Op0->getType());
 310
 311   // (X + Y) - Y -> X
 312   // (Y + X) - Y -> X
 313   Value *X = 0;
 314   if (match(Op0, m_Add(m_Value(X), m_Specific(Op1))) ||
 315       match(Op0, m_Add(m_Specific(Op1), m_Value(X))))
 316     return X;
 317
 318   // Threading Sub over selects and phi nodes is pointless, so don't bother.
 319   // Threading over the select in "A - select(cond, B, C)" means evaluating
 320   // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
 321   // only if B and C are equal.  If B and C are equal then (since we assume
 322   // that operands have already been simplified) "select(cond, B, C)" should
 323   // have been simplified to the common value of B and C already.  Analysing
 324   // "A-B" and "A-C" thus gains nothing, but costs compile time.  Similarly
 325   // for threading over phi nodes.
 326
 327   return 0;
 328 }
 329
 330 Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 331                              const TargetData *TD, const DominatorTree *DT) {
 332   return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit);
 333 }
 334
 335 /// SimplifyAndInst - Given operands for an And, see if we can
 336 /// fold the result.  If not, this returns null.
 337 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
 338                               const DominatorTree *DT, unsigned MaxRecurse) {
 339   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 340     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 341       Constant *Ops[] = { CLHS, CRHS };
 342       return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
 343                                       Ops, 2, TD);
 344     }
 345
 346     // Canonicalize the constant to the RHS.
 347     std::swap(Op0, Op1);
 348   }
 349
 350   // X & undef -> 0
 351   if (isa<UndefValue>(Op1))
 352     return Constant::getNullValue(Op0->getType());
 353
 354   // X & X = X
 355   if (Op0 == Op1)
 356     return Op0;
 357
 358   // X & 0 = 0
 359   if (match(Op1, m_Zero()))
 360     return Op1;
 361
 362   // X & -1 = X
 363   if (match(Op1, m_AllOnes()))
 364     return Op0;
 365
 366   // A & ~A  =  ~A & A  =  0
 367   Value *A = 0, *B = 0;
 368   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
 369       (match(Op1, m_Not(m_Value(A))) && A == Op0))
 370     return Constant::getNullValue(Op0->getType());
 371
 372   // (A | ?) & A = A
 373   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
 374       (A == Op1 || B == Op1))
 375     return Op1;
 376
 377   // A & (A | ?) = A
 378   if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
 379       (A == Op0 || B == Op0))
 380     return Op0;
 381
 382   // (A & B) & A -> A & B
 383   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
 384       (A == Op1 || B == Op1))
 385     return Op0;
 386
 387   // A & (A & B) -> A & B
 388   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
 389       (A == Op0 || B == Op0))
 390     return Op1;
 391
 392   // If the operation is with the result of a select instruction, check whether
 393   // operating on either branch of the select always yields the same value.
 394   if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
 395     if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT,
 396                                          MaxRecurse-1))
 397       return V;
 398
 399   // If the operation is with the result of a phi instruction, check whether
 400   // operating on all incoming values of the phi always yields the same value.
 401   if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
 402     if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT,
 403                                       MaxRecurse-1))
 404       return V;
 405
 406   return 0;
 407 }
 408
 409 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD,
 410                              const DominatorTree *DT) {
 411   return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit);
 412 }
 413
 414 /// SimplifyOrInst - Given operands for an Or, see if we can
 415 /// fold the result.  If not, this returns null.
 416 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
 417                              const DominatorTree *DT, unsigned MaxRecurse) {
 418   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 419     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 420       Constant *Ops[] = { CLHS, CRHS };
 421       return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
 422                                       Ops, 2, TD);
 423     }
 424
 425     // Canonicalize the constant to the RHS.
 426     std::swap(Op0, Op1);
 427   }
 428
 429   // X | undef -> -1
 430   if (isa<UndefValue>(Op1))
 431     return Constant::getAllOnesValue(Op0->getType());
 432
 433   // X | X = X
 434   if (Op0 == Op1)
 435     return Op0;
 436
 437   // X | 0 = X
 438   if (match(Op1, m_Zero()))
 439     return Op0;
 440
 441   // X | -1 = -1
 442   if (match(Op1, m_AllOnes()))
 443     return Op1;
 444
 445   // A | ~A  =  ~A | A  =  -1
 446   Value *A = 0, *B = 0;
 447   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
 448       (match(Op1, m_Not(m_Value(A))) && A == Op0))
 449     return Constant::getAllOnesValue(Op0->getType());
 450
 451   // (A & ?) | A = A
 452   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
 453       (A == Op1 || B == Op1))
 454     return Op1;
 455
 456   // A | (A & ?) = A
 457   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
 458       (A == Op0 || B == Op0))
 459     return Op0;
 460
 461   // (A | B) | A -> A | B
 462   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
 463       (A == Op1 || B == Op1))
 464     return Op0;
 465
 466   // A | (A | B) -> A | B
 467   if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
 468       (A == Op0 || B == Op0))
 469     return Op1;
 470
 471   // If the operation is with the result of a select instruction, check whether
 472   // operating on either branch of the select always yields the same value.
 473   if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)))
 474     if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT,
 475                                          MaxRecurse-1))
 476       return V;
 477
 478   // If the operation is with the result of a phi instruction, check whether
 479   // operating on all incoming values of the phi always yields the same value.
 480   if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1)))
 481     if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT,
 482                                       MaxRecurse-1))
 483       return V;
 484
 485   return 0;
 486 }
 487
 488 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD,
 489                             const DominatorTree *DT) {
 490   return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit);
 491 }
 492
 493 /// SimplifyXorInst - Given operands for a Xor, see if we can
 494 /// fold the result.  If not, this returns null.
 495 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
 496                               const DominatorTree *DT, unsigned MaxRecurse) {
 497   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
 498     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
 499       Constant *Ops[] = { CLHS, CRHS };
 500       return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
 501                                       Ops, 2, TD);
 502     }
 503
 504     // Canonicalize the constant to the RHS.
 505     std::swap(Op0, Op1);
 506   }
 507
 508   // A ^ undef -> undef
 509   if (isa<UndefValue>(Op1))
 510     return Op1;
 511
 512   // A ^ 0 = A
 513   if (match(Op1, m_Zero()))
 514     return Op0;
 515
 516   // A ^ A = 0
 517   if (Op0 == Op1)
 518     return Constant::getNullValue(Op0->getType());
 519
 520   // A ^ ~A  =  ~A ^ A  =  -1
 521   Value *A = 0, *B = 0;
 522   if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
 523       (match(Op1, m_Not(m_Value(A))) && A == Op0))
 524     return Constant::getAllOnesValue(Op0->getType());
 525
 526   // (A ^ B) ^ A = B
 527   if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
 528       (A == Op1 || B == Op1))
 529     return A == Op1 ? B : A;
 530
 531   // A ^ (A ^ B) = B
 532   if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
 533       (A == Op0 || B == Op0))
 534     return A == Op0 ? B : A;
 535
 536   // Threading Xor over selects and phi nodes is pointless, so don't bother.
 537   // Threading over the select in "A ^ select(cond, B, C)" means evaluating
 538   // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
 539   // only if B and C are equal.  If B and C are equal then (since we assume
 540   // that operands have already been simplified) "select(cond, B, C)" should
 541   // have been simplified to the common value of B and C already.  Analysing
 542   // "A^B" and "A^C" thus gains nothing, but costs compile time.  Similarly
 543   // for threading over phi nodes.
 544
 545   return 0;
 546 }
 547
 548 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD,
 549                              const DominatorTree *DT) {
 550   return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit);
 551 }
 552
 553 static const Type *GetCompareTy(Value *Op) {
 554   return CmpInst::makeCmpResultType(Op->getType());
 555 }
 556
 557 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
 558 /// fold the result.  If not, this returns null.
 559 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 560                                const TargetData *TD, const DominatorTree *DT,
 561                                unsigned MaxRecurse) {
 562   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
 563   assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
 564
 565   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
 566     if (Constant *CRHS = dyn_cast<Constant>(RHS))
 567       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
 568
 569     // If we have a constant, make sure it is on the RHS.
 570     std::swap(LHS, RHS);
 571     Pred = CmpInst::getSwappedPredicate(Pred);
 572   }
 573
 574   // ITy - This is the return type of the compare we're considering.
 575   const Type *ITy = GetCompareTy(LHS);
 576
 577   // icmp X, X -> true/false
 578   // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
 579   // because X could be 0.
 580   if (LHS == RHS || isa<UndefValue>(RHS))
 581     return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
 582
 583   // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
 584   // addresses never equal each other!  We already know that Op0 != Op1.
 585   if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
 586        isa<ConstantPointerNull>(LHS)) &&
 587       (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
 588        isa<ConstantPointerNull>(RHS)))
 589     return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
 590
 591   // See if we are doing a comparison with a constant.
 592   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
 593     // If we have an icmp le or icmp ge instruction, turn it into the
 594     // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
 595     // them being folded in the code below.
 596     switch (Pred) {
 597     default: break;
 598     case ICmpInst::ICMP_ULE:
 599       if (CI->isMaxValue(false))                 // A <=u MAX -> TRUE
 600         return ConstantInt::getTrue(CI->getContext());
 601       break;
 602     case ICmpInst::ICMP_SLE:
 603       if (CI->isMaxValue(true))                  // A <=s MAX -> TRUE
 604         return ConstantInt::getTrue(CI->getContext());
 605       break;
 606     case ICmpInst::ICMP_UGE:
 607       if (CI->isMinValue(false))                 // A >=u MIN -> TRUE
 608         return ConstantInt::getTrue(CI->getContext());
 609       break;
 610     case ICmpInst::ICMP_SGE:
 611       if (CI->isMinValue(true))                  // A >=s MIN -> TRUE
 612         return ConstantInt::getTrue(CI->getContext());
 613       break;
 614     }
 615   }
 616
 617   // If the comparison is with the result of a select instruction, check whether
 618   // comparing with either branch of the select always yields the same value.
 619   if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
 620     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
 621       return V;
 622
 623   // If the comparison is with the result of a phi instruction, check whether
 624   // doing the compare with each incoming phi value yields a common result.
 625   if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
 626     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
 627       return V;
 628
 629   return 0;
 630 }
 631
 632 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 633                               const TargetData *TD, const DominatorTree *DT) {
 634   return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
 635 }
 636
 637 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
 638 /// fold the result.  If not, this returns null.
 639 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 640                                const TargetData *TD, const DominatorTree *DT,
 641                                unsigned MaxRecurse) {
 642   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
 643   assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
 644
 645   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
 646     if (Constant *CRHS = dyn_cast<Constant>(RHS))
 647       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
 648
 649     // If we have a constant, make sure it is on the RHS.
 650     std::swap(LHS, RHS);
 651     Pred = CmpInst::getSwappedPredicate(Pred);
 652   }
 653
 654   // Fold trivial predicates.
 655   if (Pred == FCmpInst::FCMP_FALSE)
 656     return ConstantInt::get(GetCompareTy(LHS), 0);
 657   if (Pred == FCmpInst::FCMP_TRUE)
 658     return ConstantInt::get(GetCompareTy(LHS), 1);
 659
 660   if (isa<UndefValue>(RHS))                  // fcmp pred X, undef -> undef
 661     return UndefValue::get(GetCompareTy(LHS));
 662
 663   // fcmp x,x -> true/false.  Not all compares are foldable.
 664   if (LHS == RHS) {
 665     if (CmpInst::isTrueWhenEqual(Pred))
 666       return ConstantInt::get(GetCompareTy(LHS), 1);
 667     if (CmpInst::isFalseWhenEqual(Pred))
 668       return ConstantInt::get(GetCompareTy(LHS), 0);
 669   }
 670
 671   // Handle fcmp with constant RHS
 672   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
 673     // If the constant is a nan, see if we can fold the comparison based on it.
 674     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
 675       if (CFP->getValueAPF().isNaN()) {
 676         if (FCmpInst::isOrdered(Pred))   // True "if ordered and foo"
 677           return ConstantInt::getFalse(CFP->getContext());
 678         assert(FCmpInst::isUnordered(Pred) &&
 679                "Comparison must be either ordered or unordered!");
 680         // True if unordered.
 681         return ConstantInt::getTrue(CFP->getContext());
 682       }
 683       // Check whether the constant is an infinity.
 684       if (CFP->getValueAPF().isInfinity()) {
 685         if (CFP->getValueAPF().isNegative()) {
 686           switch (Pred) {
 687           case FCmpInst::FCMP_OLT:
 688             // No value is ordered and less than negative infinity.
 689             return ConstantInt::getFalse(CFP->getContext());
 690           case FCmpInst::FCMP_UGE:
 691             // All values are unordered with or at least negative infinity.
 692             return ConstantInt::getTrue(CFP->getContext());
 693           default:
 694             break;
 695           }
 696         } else {
 697           switch (Pred) {
 698           case FCmpInst::FCMP_OGT:
 699             // No value is ordered and greater than infinity.
 700             return ConstantInt::getFalse(CFP->getContext());
 701           case FCmpInst::FCMP_ULE:
 702             // All values are unordered with and at most infinity.
 703             return ConstantInt::getTrue(CFP->getContext());
 704           default:
 705             break;
 706           }
 707         }
 708       }
 709     }
 710   }
 711
 712   // If the comparison is with the result of a select instruction, check whether
 713   // comparing with either branch of the select always yields the same value.
 714   if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
 715     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
 716       return V;
 717
 718   // If the comparison is with the result of a phi instruction, check whether
 719   // doing the compare with each incoming phi value yields a common result.
 720   if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
 721     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1))
 722       return V;
 723
 724   return 0;
 725 }
 726
 727 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 728                               const TargetData *TD, const DominatorTree *DT) {
 729   return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
 730 }
 731
 732 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
 733 /// the result.  If not, this returns null.
 734 Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
 735                                 const TargetData *TD, const DominatorTree *) {
 736   // select true, X, Y  -> X
 737   // select false, X, Y -> Y
 738   if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
 739     return CB->getZExtValue() ? TrueVal : FalseVal;
 740
 741   // select C, X, X -> X
 742   if (TrueVal == FalseVal)
 743     return TrueVal;
 744
 745   if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
 746     return FalseVal;
 747   if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
 748     return TrueVal;
 749   if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
 750     if (isa<Constant>(TrueVal))
 751       return TrueVal;
 752     return FalseVal;
 753   }
 754
 755   return 0;
 756 }
 757
 758 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
 759 /// fold the result.  If not, this returns null.
 760 Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
 761                              const TargetData *TD, const DominatorTree *) {
 762   // The type of the GEP pointer operand.
 763   const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType());
 764
 765   // getelementptr P -> P.
 766   if (NumOps == 1)
 767     return Ops[0];
 768
 769   if (isa<UndefValue>(Ops[0])) {
 770     // Compute the (pointer) type returned by the GEP instruction.
 771     const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1],
 772                                                              NumOps-1);
 773     const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace());
 774     return UndefValue::get(GEPTy);
 775   }
 776
 777   if (NumOps == 2) {
 778     // getelementptr P, 0 -> P.
 779     if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
 780       if (C->isZero())
 781         return Ops[0];
 782     // getelementptr P, N -> P if P points to a type of zero size.
 783     if (TD) {
 784       const Type *Ty = PtrTy->getElementType();
 785       if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0)
 786         return Ops[0];
 787     }
 788   }
 789
 790   // Check to see if this is constant foldable.
 791   for (unsigned i = 0; i != NumOps; ++i)
 792     if (!isa<Constant>(Ops[i]))
 793       return 0;
 794
 795   return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
 796                                         (Constant *const*)Ops+1, NumOps-1);
 797 }
 798
 799 /// SimplifyPHINode - See if we can fold the given phi.  If not, returns null.
 800 static Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) {
 801   // If all of the PHI's incoming values are the same then replace the PHI node
 802   // with the common value.
 803   Value *CommonValue = 0;
 804   bool HasUndefInput = false;
 805   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 806     Value *Incoming = PN->getIncomingValue(i);
 807     // If the incoming value is the phi node itself, it can safely be skipped.
 808     if (Incoming == PN) continue;
 809     if (isa<UndefValue>(Incoming)) {
 810       // Remember that we saw an undef value, but otherwise ignore them.
 811       HasUndefInput = true;
 812       continue;
 813     }
 814     if (CommonValue && Incoming != CommonValue)
 815       return 0;  // Not the same, bail out.
 816     CommonValue = Incoming;
 817   }
 818
 819   // If CommonValue is null then all of the incoming values were either undef or
 820   // equal to the phi node itself.
 821   if (!CommonValue)
 822     return UndefValue::get(PN->getType());
 823
 824   // If we have a PHI node like phi(X, undef, X), where X is defined by some
 825   // instruction, we cannot return X as the result of the PHI node unless it
 826   // dominates the PHI block.
 827   if (HasUndefInput)
 828     return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0;
 829
 830   return CommonValue;
 831 }
 832
 833
 834 //=== Helper functions for higher up the class hierarchy.
 835
 836 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
 837 /// fold the result.  If not, this returns null.
 838 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 839                             const TargetData *TD, const DominatorTree *DT,
 840                             unsigned MaxRecurse) {
 841   switch (Opcode) {
 842   case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse);
 843   case Instruction::Or:  return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse);
 844   case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse);
 845   case Instruction::Add: return SimplifyAddInst(LHS, RHS, /* isNSW */ false,
 846                                                 /* isNUW */ false, TD, DT,
 847                                                 MaxRecurse);
 848   case Instruction::Sub: return SimplifySubInst(LHS, RHS, /* isNSW */ false,
 849                                                 /* isNUW */ false, TD, DT,
 850                                                 MaxRecurse);
 851   default:
 852     if (Constant *CLHS = dyn_cast<Constant>(LHS))
 853       if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
 854         Constant *COps[] = {CLHS, CRHS};
 855         return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
 856       }
 857
 858     // If the operation is with the result of a select instruction, check whether
 859     // operating on either branch of the select always yields the same value.
 860     if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)))
 861       if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT,
 862                                            MaxRecurse-1))
 863         return V;
 864
 865     // If the operation is with the result of a phi instruction, check whether
 866     // operating on all incoming values of the phi always yields the same value.
 867     if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS)))
 868       if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse-1))
 869         return V;
 870
 871     return 0;
 872   }
 873 }
 874
 875 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
 876                            const TargetData *TD, const DominatorTree *DT) {
 877   return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit);
 878 }
 879
 880 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
 881 /// fold the result.
 882 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 883                               const TargetData *TD, const DominatorTree *DT,
 884                               unsigned MaxRecurse) {
 885   if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
 886     return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
 887   return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse);
 888 }
 889
 890 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
 891                              const TargetData *TD, const DominatorTree *DT) {
 892   return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit);
 893 }
 894
 895 /// SimplifyInstruction - See if we can compute a simplified version of this
 896 /// instruction.  If not, this returns null.
 897 Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD,
 898                                  const DominatorTree *DT) {
 899   Value *Result;
 900
 901   switch (I->getOpcode()) {
 902   default:
 903     Result = ConstantFoldInstruction(I, TD);
 904     break;
 905   case Instruction::Add:
 906     Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
 907                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
 908                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
 909                              TD, DT);
 910     break;
 911   case Instruction::Sub:
 912     Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
 913                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
 914                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
 915                              TD, DT);
 916     break;
 917   case Instruction::And:
 918     Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT);
 919     break;
 920   case Instruction::Or:
 921     Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT);
 922     break;
 923   case Instruction::Xor:
 924     Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT);
 925     break;
 926   case Instruction::ICmp:
 927     Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
 928                               I->getOperand(0), I->getOperand(1), TD, DT);
 929     break;
 930   case Instruction::FCmp:
 931     Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
 932                               I->getOperand(0), I->getOperand(1), TD, DT);
 933     break;
 934   case Instruction::Select:
 935     Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
 936                                 I->getOperand(2), TD, DT);
 937     break;
 938   case Instruction::GetElementPtr: {
 939     SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
 940     Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT);
 941     break;
 942   }
 943   case Instruction::PHI:
 944     Result = SimplifyPHINode(cast<PHINode>(I), DT);
 945     break;
 946   }
 947
 948   /// If called on unreachable code, the above logic may report that the
 949   /// instruction simplified to itself.  Make life easier for users by
 950   /// detecting that case here, returning a safe value instead.
 951   return Result == I ? UndefValue::get(I->getType()) : Result;
 952 }
 953
 954 /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
 955 /// delete the From instruction.  In addition to a basic RAUW, this does a
 956 /// recursive simplification of the newly formed instructions.  This catches
 957 /// things where one simplification exposes other opportunities.  This only
 958 /// simplifies and deletes scalar operations, it does not change the CFG.
 959 ///
 960 void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
 961                                      const TargetData *TD,
 962                                      const DominatorTree *DT) {
 963   assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
 964
 965   // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
 966   // we can know if it gets deleted out from under us or replaced in a
 967   // recursive simplification.
 968   WeakVH FromHandle(From);
 969   WeakVH ToHandle(To);
 970
 971   while (!From->use_empty()) {
 972     // Update the instruction to use the new value.
 973     Use &TheUse = From->use_begin().getUse();
 974     Instruction *User = cast<Instruction>(TheUse.getUser());
 975     TheUse = To;
 976
 977     // Check to see if the instruction can be folded due to the operand
 978     // replacement.  For example changing (or X, Y) into (or X, -1) can replace
 979     // the 'or' with -1.
 980     Value *SimplifiedVal;
 981     {
 982       // Sanity check to make sure 'User' doesn't dangle across
 983       // SimplifyInstruction.
 984       AssertingVH<> UserHandle(User);
 985
 986       SimplifiedVal = SimplifyInstruction(User, TD, DT);
 987       if (SimplifiedVal == 0) continue;
 988     }
 989
 990     // Recursively simplify this user to the new value.
 991     ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT);
 992     From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
 993     To = ToHandle;
 994
 995     assert(ToHandle && "To value deleted by recursive simplification?");
 996
 997     // If the recursive simplification ended up revisiting and deleting
 998     // 'From' then we're done.
 999     if (From == 0)
1000       return;
1001   }
1002
1003   // If 'From' has value handles referring to it, do a real RAUW to update them.
1004   From->replaceAllUsesWith(To);
1005
1006   From->eraseFromParent();
1007 }