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