lib/Analysis/InstructionSimplify.cpp

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