lib/Analysis/InstructionSimplify.cpp

   1 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements routines for folding instructions into simpler forms
  11 // that do not require creating new instructions.  This does constant folding
  12 // ("add i32 1, 1" -> "2") but can also handle non-constant operands, either
  13 // returning a constant ("and i32 %x, 0" -> "0") or an already existing value
  14 // ("and i32 %x, %x" -> "%x").  All operands are assumed to have already been
  15 // simplified: This is usually true and assuming it simplifies the logic (if
  16 // they have not been simplified then results are correct but maybe suboptimal).
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #include "llvm/Analysis/InstructionSimplify.h"
  21 #include "llvm/ADT/SetVector.h"
  22 #include "llvm/ADT/Statistic.h"
  23 #include "llvm/Analysis/AliasAnalysis.h"
  24 #include "llvm/Analysis/AssumptionCache.h"
  25 #include "llvm/Analysis/CaptureTracking.h"
  26 #include "llvm/Analysis/CmpInstAnalysis.h"
  27 #include "llvm/Analysis/ConstantFolding.h"
  28 #include "llvm/Analysis/LoopAnalysisManager.h"
  29 #include "llvm/Analysis/MemoryBuiltins.h"
  30 #include "llvm/Analysis/ValueTracking.h"
  31 #include "llvm/Analysis/VectorUtils.h"
  32 #include "llvm/IR/ConstantRange.h"
  33 #include "llvm/IR/DataLayout.h"
  34 #include "llvm/IR/Dominators.h"
  35 #include "llvm/IR/GetElementPtrTypeIterator.h"
  36 #include "llvm/IR/GlobalAlias.h"
  37 #include "llvm/IR/Operator.h"
  38 #include "llvm/IR/PatternMatch.h"
  39 #include "llvm/IR/ValueHandle.h"
  40 #include "llvm/Support/KnownBits.h"
  41 #include <algorithm>
  42 using namespace llvm;
  43 using namespace llvm::PatternMatch;
  44
  45 #define DEBUG_TYPE "instsimplify"
  46
  47 enum { RecursionLimit = 3 };
  48
  49 STATISTIC(NumExpand,  "Number of expansions");
  50 STATISTIC(NumReassoc, "Number of reassociations");
  51
  52 static Value *SimplifyAndInst(Value *, Value *, const SimplifyQuery &, unsigned);
  53 static Value *SimplifyBinOp(unsigned, Value *, Value *, const SimplifyQuery &,
  54                             unsigned);
  55 static Value *SimplifyFPBinOp(unsigned, Value *, Value *, const FastMathFlags &,
  56                               const SimplifyQuery &, unsigned);
  57 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const SimplifyQuery &,
  58                               unsigned);
  59 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
  60                                const SimplifyQuery &Q, unsigned MaxRecurse);
  61 static Value *SimplifyOrInst(Value *, Value *, const SimplifyQuery &, unsigned);
  62 static Value *SimplifyXorInst(Value *, Value *, const SimplifyQuery &, unsigned);
  63 static Value *SimplifyCastInst(unsigned, Value *, Type *,
  64                                const SimplifyQuery &, unsigned);
  65 static Value *SimplifyGEPInst(Type *, ArrayRef<Value *>, const SimplifyQuery &,
  66                               unsigned);
  67
  68 /// For a boolean type or a vector of boolean type, return false or a vector
  69 /// with every element false.
  70 static Constant *getFalse(Type *Ty) {
  71   return ConstantInt::getFalse(Ty);
  72 }
  73
  74 /// For a boolean type or a vector of boolean type, return true or a vector
  75 /// with every element true.
  76 static Constant *getTrue(Type *Ty) {
  77   return ConstantInt::getTrue(Ty);
  78 }
  79
  80 /// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"?
  81 static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS,
  82                           Value *RHS) {
  83   CmpInst *Cmp = dyn_cast<CmpInst>(V);
  84   if (!Cmp)
  85     return false;
  86   CmpInst::Predicate CPred = Cmp->getPredicate();
  87   Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1);
  88   if (CPred == Pred && CLHS == LHS && CRHS == RHS)
  89     return true;
  90   return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS &&
  91     CRHS == LHS;
  92 }
  93
  94 /// Does the given value dominate the specified phi node?
  95 static bool valueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
  96   Instruction *I = dyn_cast<Instruction>(V);
  97   if (!I)
  98     // Arguments and constants dominate all instructions.
  99     return true;
 100
 101   // If we are processing instructions (and/or basic blocks) that have not been
 102   // fully added to a function, the parent nodes may still be null. Simply
 103   // return the conservative answer in these cases.
 104   if (!I->getParent() || !P->getParent() || !I->getFunction())
 105     return false;
 106
 107   // If we have a DominatorTree then do a precise test.
 108   if (DT)
 109     return DT->dominates(I, P);
 110
 111   // Otherwise, if the instruction is in the entry block and is not an invoke,
 112   // then it obviously dominates all phi nodes.
 113   if (I->getParent() == &I->getFunction()->getEntryBlock() &&
 114       !isa<InvokeInst>(I))
 115     return true;
 116
 117   return false;
 118 }
 119
 120 /// Simplify "A op (B op' C)" by distributing op over op', turning it into
 121 /// "(A op B) op' (A op C)".  Here "op" is given by Opcode and "op'" is
 122 /// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.
 123 /// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
 124 /// Returns the simplified value, or null if no simplification was performed.
 125 static Value *ExpandBinOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
 126                           Instruction::BinaryOps OpcodeToExpand,
 127                           const SimplifyQuery &Q, unsigned MaxRecurse) {
 128   // Recursion is always used, so bail out at once if we already hit the limit.
 129   if (!MaxRecurse--)
 130     return nullptr;
 131
 132   // Check whether the expression has the form "(A op' B) op C".
 133   if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS))
 134     if (Op0->getOpcode() == OpcodeToExpand) {
 135       // It does!  Try turning it into "(A op C) op' (B op C)".
 136       Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
 137       // Do "A op C" and "B op C" both simplify?
 138       if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse))
 139         if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
 140           // They do! Return "L op' R" if it simplifies or is already available.
 141           // If "L op' R" equals "A op' B" then "L op' R" is just the LHS.
 142           if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand)
 143                                      && L == B && R == A)) {
 144             ++NumExpand;
 145             return LHS;
 146           }
 147           // Otherwise return "L op' R" if it simplifies.
 148           if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
 149             ++NumExpand;
 150             return V;
 151           }
 152         }
 153     }
 154
 155   // Check whether the expression has the form "A op (B op' C)".
 156   if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
 157     if (Op1->getOpcode() == OpcodeToExpand) {
 158       // It does!  Try turning it into "(A op B) op' (A op C)".
 159       Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
 160       // Do "A op B" and "A op C" both simplify?
 161       if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse))
 162         if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) {
 163           // They do! Return "L op' R" if it simplifies or is already available.
 164           // If "L op' R" equals "B op' C" then "L op' R" is just the RHS.
 165           if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand)
 166                                      && L == C && R == B)) {
 167             ++NumExpand;
 168             return RHS;
 169           }
 170           // Otherwise return "L op' R" if it simplifies.
 171           if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
 172             ++NumExpand;
 173             return V;
 174           }
 175         }
 176     }
 177
 178   return nullptr;
 179 }
 180
 181 /// Generic simplifications for associative binary operations.
 182 /// Returns the simpler value, or null if none was found.
 183 static Value *SimplifyAssociativeBinOp(Instruction::BinaryOps Opcode,
 184                                        Value *LHS, Value *RHS,
 185                                        const SimplifyQuery &Q,
 186                                        unsigned MaxRecurse) {
 187   assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
 188
 189   // Recursion is always used, so bail out at once if we already hit the limit.
 190   if (!MaxRecurse--)
 191     return nullptr;
 192
 193   BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
 194   BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
 195
 196   // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely.
 197   if (Op0 && Op0->getOpcode() == Opcode) {
 198     Value *A = Op0->getOperand(0);
 199     Value *B = Op0->getOperand(1);
 200     Value *C = RHS;
 201
 202     // Does "B op C" simplify?
 203     if (Value *V = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
 204       // It does!  Return "A op V" if it simplifies or is already available.
 205       // If V equals B then "A op V" is just the LHS.
 206       if (V == B) return LHS;
 207       // Otherwise return "A op V" if it simplifies.
 208       if (Value *W = SimplifyBinOp(Opcode, A, V, Q, MaxRecurse)) {
 209         ++NumReassoc;
 210         return W;
 211       }
 212     }
 213   }
 214
 215   // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely.
 216   if (Op1 && Op1->getOpcode() == Opcode) {
 217     Value *A = LHS;
 218     Value *B = Op1->getOperand(0);
 219     Value *C = Op1->getOperand(1);
 220
 221     // Does "A op B" simplify?
 222     if (Value *V = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) {
 223       // It does!  Return "V op C" if it simplifies or is already available.
 224       // If V equals B then "V op C" is just the RHS.
 225       if (V == B) return RHS;
 226       // Otherwise return "V op C" if it simplifies.
 227       if (Value *W = SimplifyBinOp(Opcode, V, C, Q, MaxRecurse)) {
 228         ++NumReassoc;
 229         return W;
 230       }
 231     }
 232   }
 233
 234   // The remaining transforms require commutativity as well as associativity.
 235   if (!Instruction::isCommutative(Opcode))
 236     return nullptr;
 237
 238   // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely.
 239   if (Op0 && Op0->getOpcode() == Opcode) {
 240     Value *A = Op0->getOperand(0);
 241     Value *B = Op0->getOperand(1);
 242     Value *C = RHS;
 243
 244     // Does "C op A" simplify?
 245     if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
 246       // It does!  Return "V op B" if it simplifies or is already available.
 247       // If V equals A then "V op B" is just the LHS.
 248       if (V == A) return LHS;
 249       // Otherwise return "V op B" if it simplifies.
 250       if (Value *W = SimplifyBinOp(Opcode, V, B, Q, MaxRecurse)) {
 251         ++NumReassoc;
 252         return W;
 253       }
 254     }
 255   }
 256
 257   // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely.
 258   if (Op1 && Op1->getOpcode() == Opcode) {
 259     Value *A = LHS;
 260     Value *B = Op1->getOperand(0);
 261     Value *C = Op1->getOperand(1);
 262
 263     // Does "C op A" simplify?
 264     if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
 265       // It does!  Return "B op V" if it simplifies or is already available.
 266       // If V equals C then "B op V" is just the RHS.
 267       if (V == C) return RHS;
 268       // Otherwise return "B op V" if it simplifies.
 269       if (Value *W = SimplifyBinOp(Opcode, B, V, Q, MaxRecurse)) {
 270         ++NumReassoc;
 271         return W;
 272       }
 273     }
 274   }
 275
 276   return nullptr;
 277 }
 278
 279 /// In the case of a binary operation with a select instruction as an operand,
 280 /// try to simplify the binop by seeing whether evaluating it on both branches
 281 /// of the select results in the same value. Returns the common value if so,
 282 /// otherwise returns null.
 283 static Value *ThreadBinOpOverSelect(Instruction::BinaryOps Opcode, Value *LHS,
 284                                     Value *RHS, const SimplifyQuery &Q,
 285                                     unsigned MaxRecurse) {
 286   // Recursion is always used, so bail out at once if we already hit the limit.
 287   if (!MaxRecurse--)
 288     return nullptr;
 289
 290   SelectInst *SI;
 291   if (isa<SelectInst>(LHS)) {
 292     SI = cast<SelectInst>(LHS);
 293   } else {
 294     assert(isa<SelectInst>(RHS) && "No select instruction operand!");
 295     SI = cast<SelectInst>(RHS);
 296   }
 297
 298   // Evaluate the BinOp on the true and false branches of the select.
 299   Value *TV;
 300   Value *FV;
 301   if (SI == LHS) {
 302     TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse);
 303     FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse);
 304   } else {
 305     TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse);
 306     FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse);
 307   }
 308
 309   // If they simplified to the same value, then return the common value.
 310   // If they both failed to simplify then return null.
 311   if (TV == FV)
 312     return TV;
 313
 314   // If one branch simplified to undef, return the other one.
 315   if (TV && isa<UndefValue>(TV))
 316     return FV;
 317   if (FV && isa<UndefValue>(FV))
 318     return TV;
 319
 320   // If applying the operation did not change the true and false select values,
 321   // then the result of the binop is the select itself.
 322   if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
 323     return SI;
 324
 325   // If one branch simplified and the other did not, and the simplified
 326   // value is equal to the unsimplified one, return the simplified value.
 327   // For example, select (cond, X, X & Z) & Z -> X & Z.
 328   if ((FV && !TV) || (TV && !FV)) {
 329     // Check that the simplified value has the form "X op Y" where "op" is the
 330     // same as the original operation.
 331     Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
 332     if (Simplified && Simplified->getOpcode() == unsigned(Opcode)) {
 333       // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
 334       // We already know that "op" is the same as for the simplified value.  See
 335       // if the operands match too.  If so, return the simplified value.
 336       Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
 337       Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
 338       Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
 339       if (Simplified->getOperand(0) == UnsimplifiedLHS &&
 340           Simplified->getOperand(1) == UnsimplifiedRHS)
 341         return Simplified;
 342       if (Simplified->isCommutative() &&
 343           Simplified->getOperand(1) == UnsimplifiedLHS &&
 344           Simplified->getOperand(0) == UnsimplifiedRHS)
 345         return Simplified;
 346     }
 347   }
 348
 349   return nullptr;
 350 }
 351
 352 /// In the case of a comparison with a select instruction, try to simplify the
 353 /// comparison by seeing whether both branches of the select result in the same
 354 /// value. Returns the common value if so, otherwise returns null.
 355 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
 356                                   Value *RHS, const SimplifyQuery &Q,
 357                                   unsigned MaxRecurse) {
 358   // Recursion is always used, so bail out at once if we already hit the limit.
 359   if (!MaxRecurse--)
 360     return nullptr;
 361
 362   // Make sure the select is on the LHS.
 363   if (!isa<SelectInst>(LHS)) {
 364     std::swap(LHS, RHS);
 365     Pred = CmpInst::getSwappedPredicate(Pred);
 366   }
 367   assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
 368   SelectInst *SI = cast<SelectInst>(LHS);
 369   Value *Cond = SI->getCondition();
 370   Value *TV = SI->getTrueValue();
 371   Value *FV = SI->getFalseValue();
 372
 373   // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it.
 374   // Does "cmp TV, RHS" simplify?
 375   Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse);
 376   if (TCmp == Cond) {
 377     // It not only simplified, it simplified to the select condition.  Replace
 378     // it with 'true'.
 379     TCmp = getTrue(Cond->getType());
 380   } else if (!TCmp) {
 381     // It didn't simplify.  However if "cmp TV, RHS" is equal to the select
 382     // condition then we can replace it with 'true'.  Otherwise give up.
 383     if (!isSameCompare(Cond, Pred, TV, RHS))
 384       return nullptr;
 385     TCmp = getTrue(Cond->getType());
 386   }
 387
 388   // Does "cmp FV, RHS" simplify?
 389   Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse);
 390   if (FCmp == Cond) {
 391     // It not only simplified, it simplified to the select condition.  Replace
 392     // it with 'false'.
 393     FCmp = getFalse(Cond->getType());
 394   } else if (!FCmp) {
 395     // It didn't simplify.  However if "cmp FV, RHS" is equal to the select
 396     // condition then we can replace it with 'false'.  Otherwise give up.
 397     if (!isSameCompare(Cond, Pred, FV, RHS))
 398       return nullptr;
 399     FCmp = getFalse(Cond->getType());
 400   }
 401
 402   // If both sides simplified to the same value, then use it as the result of
 403   // the original comparison.
 404   if (TCmp == FCmp)
 405     return TCmp;
 406
 407   // The remaining cases only make sense if the select condition has the same
 408   // type as the result of the comparison, so bail out if this is not so.
 409   if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy())
 410     return nullptr;
 411   // If the false value simplified to false, then the result of the compare
 412   // is equal to "Cond && TCmp".  This also catches the case when the false
 413   // value simplified to false and the true value to true, returning "Cond".
 414   if (match(FCmp, m_Zero()))
 415     if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse))
 416       return V;
 417   // If the true value simplified to true, then the result of the compare
 418   // is equal to "Cond || FCmp".
 419   if (match(TCmp, m_One()))
 420     if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse))
 421       return V;
 422   // Finally, if the false value simplified to true and the true value to
 423   // false, then the result of the compare is equal to "!Cond".
 424   if (match(FCmp, m_One()) && match(TCmp, m_Zero()))
 425     if (Value *V =
 426         SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()),
 427                         Q, MaxRecurse))
 428       return V;
 429
 430   return nullptr;
 431 }
 432
 433 /// In the case of a binary operation with an operand that is a PHI instruction,
 434 /// try to simplify the binop by seeing whether evaluating it on the incoming
 435 /// phi values yields the same result for every value. If so returns the common
 436 /// value, otherwise returns null.
 437 static Value *ThreadBinOpOverPHI(Instruction::BinaryOps Opcode, Value *LHS,
 438                                  Value *RHS, const SimplifyQuery &Q,
 439                                  unsigned MaxRecurse) {
 440   // Recursion is always used, so bail out at once if we already hit the limit.
 441   if (!MaxRecurse--)
 442     return nullptr;
 443
 444   PHINode *PI;
 445   if (isa<PHINode>(LHS)) {
 446     PI = cast<PHINode>(LHS);
 447     // Bail out if RHS and the phi may be mutually interdependent due to a loop.
 448     if (!valueDominatesPHI(RHS, PI, Q.DT))
 449       return nullptr;
 450   } else {
 451     assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
 452     PI = cast<PHINode>(RHS);
 453     // Bail out if LHS and the phi may be mutually interdependent due to a loop.
 454     if (!valueDominatesPHI(LHS, PI, Q.DT))
 455       return nullptr;
 456   }
 457
 458   // Evaluate the BinOp on the incoming phi values.
 459   Value *CommonValue = nullptr;
 460   for (Value *Incoming : PI->incoming_values()) {
 461     // If the incoming value is the phi node itself, it can safely be skipped.
 462     if (Incoming == PI) continue;
 463     Value *V = PI == LHS ?
 464       SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) :
 465       SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse);
 466     // If the operation failed to simplify, or simplified to a different value
 467     // to previously, then give up.
 468     if (!V || (CommonValue && V != CommonValue))
 469       return nullptr;
 470     CommonValue = V;
 471   }
 472
 473   return CommonValue;
 474 }
 475
 476 /// In the case of a comparison with a PHI instruction, try to simplify the
 477 /// comparison by seeing whether comparing with all of the incoming phi values
 478 /// yields the same result every time. If so returns the common result,
 479 /// otherwise returns null.
 480 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
 481                                const SimplifyQuery &Q, unsigned MaxRecurse) {
 482   // Recursion is always used, so bail out at once if we already hit the limit.
 483   if (!MaxRecurse--)
 484     return nullptr;
 485
 486   // Make sure the phi is on the LHS.
 487   if (!isa<PHINode>(LHS)) {
 488     std::swap(LHS, RHS);
 489     Pred = CmpInst::getSwappedPredicate(Pred);
 490   }
 491   assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
 492   PHINode *PI = cast<PHINode>(LHS);
 493
 494   // Bail out if RHS and the phi may be mutually interdependent due to a loop.
 495   if (!valueDominatesPHI(RHS, PI, Q.DT))
 496     return nullptr;
 497
 498   // Evaluate the BinOp on the incoming phi values.
 499   Value *CommonValue = nullptr;
 500   for (Value *Incoming : PI->incoming_values()) {
 501     // If the incoming value is the phi node itself, it can safely be skipped.
 502     if (Incoming == PI) continue;
 503     Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse);
 504     // If the operation failed to simplify, or simplified to a different value
 505     // to previously, then give up.
 506     if (!V || (CommonValue && V != CommonValue))
 507       return nullptr;
 508     CommonValue = V;
 509   }
 510
 511   return CommonValue;
 512 }
 513
 514 static Constant *foldOrCommuteConstant(Instruction::BinaryOps Opcode,
 515                                        Value *&Op0, Value *&Op1,
 516                                        const SimplifyQuery &Q) {
 517   if (auto *CLHS = dyn_cast<Constant>(Op0)) {
 518     if (auto *CRHS = dyn_cast<Constant>(Op1))
 519       return ConstantFoldBinaryOpOperands(Opcode, CLHS, CRHS, Q.DL);
 520
 521     // Canonicalize the constant to the RHS if this is a commutative operation.
 522     if (Instruction::isCommutative(Opcode))
 523       std::swap(Op0, Op1);
 524   }
 525   return nullptr;
 526 }
 527
 528 /// Given operands for an Add, see if we can fold the result.
 529 /// If not, this returns null.
 530 static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
 531                               const SimplifyQuery &Q, unsigned MaxRecurse) {
 532   if (Constant *C = foldOrCommuteConstant(Instruction::Add, Op0, Op1, Q))
 533     return C;
 534
 535   // X + undef -> undef
 536   if (match(Op1, m_Undef()))
 537     return Op1;
 538
 539   // X + 0 -> X
 540   if (match(Op1, m_Zero()))
 541     return Op0;
 542
 543   // X + (Y - X) -> Y
 544   // (Y - X) + X -> Y
 545   // Eg: X + -X -> 0
 546   Value *Y = nullptr;
 547   if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
 548       match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
 549     return Y;
 550
 551   // X + ~X -> -1   since   ~X = -X-1
 552   Type *Ty = Op0->getType();
 553   if (match(Op0, m_Not(m_Specific(Op1))) ||
 554       match(Op1, m_Not(m_Specific(Op0))))
 555     return Constant::getAllOnesValue(Ty);
 556
 557   // add nsw/nuw (xor Y, signmask), signmask --> Y
 558   // The no-wrapping add guarantees that the top bit will be set by the add.
 559   // Therefore, the xor must be clearing the already set sign bit of Y.
 560   if ((IsNSW || IsNUW) && match(Op1, m_SignMask()) &&
 561       match(Op0, m_Xor(m_Value(Y), m_SignMask())))
 562     return Y;
 563
 564   // add nuw %x, -1  ->  -1, because %x can only be 0.
 565   if (IsNUW && match(Op1, m_AllOnes()))
 566     return Op1; // Which is -1.
 567
 568   /// i1 add -> xor.
 569   if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
 570     if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
 571       return V;
 572
 573   // Try some generic simplifications for associative operations.
 574   if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q,
 575                                           MaxRecurse))
 576     return V;
 577
 578   // Threading Add over selects and phi nodes is pointless, so don't bother.
 579   // Threading over the select in "A + select(cond, B, C)" means evaluating
 580   // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
 581   // only if B and C are equal.  If B and C are equal then (since we assume
 582   // that operands have already been simplified) "select(cond, B, C)" should
 583   // have been simplified to the common value of B and C already.  Analysing
 584   // "A+B" and "A+C" thus gains nothing, but costs compile time.  Similarly
 585   // for threading over phi nodes.
 586
 587   return nullptr;
 588 }
 589
 590 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
 591                              const SimplifyQuery &Query) {
 592   return ::SimplifyAddInst(Op0, Op1, IsNSW, IsNUW, Query, RecursionLimit);
 593 }
 594
 595 /// Compute the base pointer and cumulative constant offsets for V.
 596 ///
 597 /// This strips all constant offsets off of V, leaving it the base pointer, and
 598 /// accumulates the total constant offset applied in the returned constant. It
 599 /// returns 0 if V is not a pointer, and returns the constant '0' if there are
 600 /// no constant offsets applied.
 601 ///
 602 /// This is very similar to GetPointerBaseWithConstantOffset except it doesn't
 603 /// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc.
 604 /// folding.
 605 static Constant *stripAndComputeConstantOffsets(const DataLayout &DL, Value *&V,
 606                                                 bool AllowNonInbounds = false) {
 607   assert(V->getType()->isPtrOrPtrVectorTy());
 608
 609   Type *IntPtrTy = DL.getIntPtrType(V->getType())->getScalarType();
 610   APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth());
 611
 612   // Even though we don't look through PHI nodes, we could be called on an
 613   // instruction in an unreachable block, which may be on a cycle.
 614   SmallPtrSet<Value *, 4> Visited;
 615   Visited.insert(V);
 616   do {
 617     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
 618       if ((!AllowNonInbounds && !GEP->isInBounds()) ||
 619           !GEP->accumulateConstantOffset(DL, Offset))
 620         break;
 621       V = GEP->getPointerOperand();
 622     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
 623       V = cast<Operator>(V)->getOperand(0);
 624     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
 625       if (GA->isInterposable())
 626         break;
 627       V = GA->getAliasee();
 628     } else {
 629       if (auto CS = CallSite(V))
 630         if (Value *RV = CS.getReturnedArgOperand()) {
 631           V = RV;
 632           continue;
 633         }
 634       break;
 635     }
 636     assert(V->getType()->isPtrOrPtrVectorTy() && "Unexpected operand type!");
 637   } while (Visited.insert(V).second);
 638
 639   Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset);
 640   if (V->getType()->isVectorTy())
 641     return ConstantVector::getSplat(V->getType()->getVectorNumElements(),
 642                                     OffsetIntPtr);
 643   return OffsetIntPtr;
 644 }
 645
 646 /// Compute the constant difference between two pointer values.
 647 /// If the difference is not a constant, returns zero.
 648 static Constant *computePointerDifference(const DataLayout &DL, Value *LHS,
 649                                           Value *RHS) {
 650   Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
 651   Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
 652
 653   // If LHS and RHS are not related via constant offsets to the same base
 654   // value, there is nothing we can do here.
 655   if (LHS != RHS)
 656     return nullptr;
 657
 658   // Otherwise, the difference of LHS - RHS can be computed as:
 659   //    LHS - RHS
 660   //  = (LHSOffset + Base) - (RHSOffset + Base)
 661   //  = LHSOffset - RHSOffset
 662   return ConstantExpr::getSub(LHSOffset, RHSOffset);
 663 }
 664
 665 /// Given operands for a Sub, see if we can fold the result.
 666 /// If not, this returns null.
 667 static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 668                               const SimplifyQuery &Q, unsigned MaxRecurse) {
 669   if (Constant *C = foldOrCommuteConstant(Instruction::Sub, Op0, Op1, Q))
 670     return C;
 671
 672   // X - undef -> undef
 673   // undef - X -> undef
 674   if (match(Op0, m_Undef()) || match(Op1, m_Undef()))
 675     return UndefValue::get(Op0->getType());
 676
 677   // X - 0 -> X
 678   if (match(Op1, m_Zero()))
 679     return Op0;
 680
 681   // X - X -> 0
 682   if (Op0 == Op1)
 683     return Constant::getNullValue(Op0->getType());
 684
 685   // Is this a negation?
 686   if (match(Op0, m_Zero())) {
 687     // 0 - X -> 0 if the sub is NUW.
 688     if (isNUW)
 689       return Constant::getNullValue(Op0->getType());
 690
 691     KnownBits Known = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
 692     if (Known.Zero.isMaxSignedValue()) {
 693       // Op1 is either 0 or the minimum signed value. If the sub is NSW, then
 694       // Op1 must be 0 because negating the minimum signed value is undefined.
 695       if (isNSW)
 696         return Constant::getNullValue(Op0->getType());
 697
 698       // 0 - X -> X if X is 0 or the minimum signed value.
 699       return Op1;
 700     }
 701   }
 702
 703   // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
 704   // For example, (X + Y) - Y -> X; (Y + X) - Y -> X
 705   Value *X = nullptr, *Y = nullptr, *Z = Op1;
 706   if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z
 707     // See if "V === Y - Z" simplifies.
 708     if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1))
 709       // It does!  Now see if "X + V" simplifies.
 710       if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) {
 711         // It does, we successfully reassociated!
 712         ++NumReassoc;
 713         return W;
 714       }
 715     // See if "V === X - Z" simplifies.
 716     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
 717       // It does!  Now see if "Y + V" simplifies.
 718       if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse-1)) {
 719         // It does, we successfully reassociated!
 720         ++NumReassoc;
 721         return W;
 722       }
 723   }
 724
 725   // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies.
 726   // For example, X - (X + 1) -> -1
 727   X = Op0;
 728   if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z)
 729     // See if "V === X - Y" simplifies.
 730     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
 731       // It does!  Now see if "V - Z" simplifies.
 732       if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse-1)) {
 733         // It does, we successfully reassociated!
 734         ++NumReassoc;
 735         return W;
 736       }
 737     // See if "V === X - Z" simplifies.
 738     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
 739       // It does!  Now see if "V - Y" simplifies.
 740       if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse-1)) {
 741         // It does, we successfully reassociated!
 742         ++NumReassoc;
 743         return W;
 744       }
 745   }
 746
 747   // Z - (X - Y) -> (Z - X) + Y if everything simplifies.
 748   // For example, X - (X - Y) -> Y.
 749   Z = Op0;
 750   if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y)
 751     // See if "V === Z - X" simplifies.
 752     if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse-1))
 753       // It does!  Now see if "V + Y" simplifies.
 754       if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse-1)) {
 755         // It does, we successfully reassociated!
 756         ++NumReassoc;
 757         return W;
 758       }
 759
 760   // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies.
 761   if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) &&
 762       match(Op1, m_Trunc(m_Value(Y))))
 763     if (X->getType() == Y->getType())
 764       // See if "V === X - Y" simplifies.
 765       if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
 766         // It does!  Now see if "trunc V" simplifies.
 767         if (Value *W = SimplifyCastInst(Instruction::Trunc, V, Op0->getType(),
 768                                         Q, MaxRecurse - 1))
 769           // It does, return the simplified "trunc V".
 770           return W;
 771
 772   // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...).
 773   if (match(Op0, m_PtrToInt(m_Value(X))) &&
 774       match(Op1, m_PtrToInt(m_Value(Y))))
 775     if (Constant *Result = computePointerDifference(Q.DL, X, Y))
 776       return ConstantExpr::getIntegerCast(Result, Op0->getType(), true);
 777
 778   // i1 sub -> xor.
 779   if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
 780     if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
 781       return V;
 782
 783   // Threading Sub over selects and phi nodes is pointless, so don't bother.
 784   // Threading over the select in "A - select(cond, B, C)" means evaluating
 785   // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
 786   // only if B and C are equal.  If B and C are equal then (since we assume
 787   // that operands have already been simplified) "select(cond, B, C)" should
 788   // have been simplified to the common value of B and C already.  Analysing
 789   // "A-B" and "A-C" thus gains nothing, but costs compile time.  Similarly
 790   // for threading over phi nodes.
 791
 792   return nullptr;
 793 }
 794
 795 Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
 796                              const SimplifyQuery &Q) {
 797   return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
 798 }
 799
 800 /// Given operands for a Mul, see if we can fold the result.
 801 /// If not, this returns null.
 802 static Value *SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
 803                               unsigned MaxRecurse) {
 804   if (Constant *C = foldOrCommuteConstant(Instruction::Mul, Op0, Op1, Q))
 805     return C;
 806
 807   // X * undef -> 0
 808   // X * 0 -> 0
 809   if (match(Op1, m_CombineOr(m_Undef(), m_Zero())))
 810     return Constant::getNullValue(Op0->getType());
 811
 812   // X * 1 -> X
 813   if (match(Op1, m_One()))
 814     return Op0;
 815
 816   // (X / Y) * Y -> X if the division is exact.
 817   Value *X = nullptr;
 818   if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y
 819       match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0)))))   // Y * (X / Y)
 820     return X;
 821
 822   // i1 mul -> and.
 823   if (MaxRecurse && Op0->getType()->isIntOrIntVectorTy(1))
 824     if (Value *V = SimplifyAndInst(Op0, Op1, Q, MaxRecurse-1))
 825       return V;
 826
 827   // Try some generic simplifications for associative operations.
 828   if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q,
 829                                           MaxRecurse))
 830     return V;
 831
 832   // Mul distributes over Add. Try some generic simplifications based on this.
 833   if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add,
 834                              Q, MaxRecurse))
 835     return V;
 836
 837   // If the operation is with the result of a select instruction, check whether
 838   // operating on either branch of the select always yields the same value.
 839   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
 840     if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q,
 841                                          MaxRecurse))
 842       return V;
 843
 844   // If the operation is with the result of a phi instruction, check whether
 845   // operating on all incoming values of the phi always yields the same value.
 846   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
 847     if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q,
 848                                       MaxRecurse))
 849       return V;
 850
 851   return nullptr;
 852 }
 853
 854 Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
 855   return ::SimplifyMulInst(Op0, Op1, Q, RecursionLimit);
 856 }
 857
 858 /// Check for common or similar folds of integer division or integer remainder.
 859 /// This applies to all 4 opcodes (sdiv/udiv/srem/urem).
 860 static Value *simplifyDivRem(Value *Op0, Value *Op1, bool IsDiv) {
 861   Type *Ty = Op0->getType();
 862
 863   // X / undef -> undef
 864   // X % undef -> undef
 865   if (match(Op1, m_Undef()))
 866     return Op1;
 867
 868   // X / 0 -> undef
 869   // X % 0 -> undef
 870   // We don't need to preserve faults!
 871   if (match(Op1, m_Zero()))
 872     return UndefValue::get(Ty);
 873
 874   // If any element of a constant divisor vector is zero or undef, the whole op
 875   // is undef.
 876   auto *Op1C = dyn_cast<Constant>(Op1);
 877   if (Op1C && Ty->isVectorTy()) {
 878     unsigned NumElts = Ty->getVectorNumElements();
 879     for (unsigned i = 0; i != NumElts; ++i) {
 880       Constant *Elt = Op1C->getAggregateElement(i);
 881       if (Elt && (Elt->isNullValue() || isa<UndefValue>(Elt)))
 882         return UndefValue::get(Ty);
 883     }
 884   }
 885
 886   // undef / X -> 0
 887   // undef % X -> 0
 888   if (match(Op0, m_Undef()))
 889     return Constant::getNullValue(Ty);
 890
 891   // 0 / X -> 0
 892   // 0 % X -> 0
 893   if (match(Op0, m_Zero()))
 894     return Constant::getNullValue(Op0->getType());
 895
 896   // X / X -> 1
 897   // X % X -> 0
 898   if (Op0 == Op1)
 899     return IsDiv ? ConstantInt::get(Ty, 1) : Constant::getNullValue(Ty);
 900
 901   // X / 1 -> X
 902   // X % 1 -> 0
 903   // If this is a boolean op (single-bit element type), we can't have
 904   // division-by-zero or remainder-by-zero, so assume the divisor is 1.
 905   // Similarly, if we're zero-extending a boolean divisor, then assume it's a 1.
 906   Value *X;
 907   if (match(Op1, m_One()) || Ty->isIntOrIntVectorTy(1) ||
 908       (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
 909     return IsDiv ? Op0 : Constant::getNullValue(Ty);
 910
 911   return nullptr;
 912 }
 913
 914 /// Given a predicate and two operands, return true if the comparison is true.
 915 /// This is a helper for div/rem simplification where we return some other value
 916 /// when we can prove a relationship between the operands.
 917 static bool isICmpTrue(ICmpInst::Predicate Pred, Value *LHS, Value *RHS,
 918                        const SimplifyQuery &Q, unsigned MaxRecurse) {
 919   Value *V = SimplifyICmpInst(Pred, LHS, RHS, Q, MaxRecurse);
 920   Constant *C = dyn_cast_or_null<Constant>(V);
 921   return (C && C->isAllOnesValue());
 922 }
 923
 924 /// Return true if we can simplify X / Y to 0. Remainder can adapt that answer
 925 /// to simplify X % Y to X.
 926 static bool isDivZero(Value *X, Value *Y, const SimplifyQuery &Q,
 927                       unsigned MaxRecurse, bool IsSigned) {
 928   // Recursion is always used, so bail out at once if we already hit the limit.
 929   if (!MaxRecurse--)
 930     return false;
 931
 932   if (IsSigned) {
 933     // |X| / |Y| --> 0
 934     //
 935     // We require that 1 operand is a simple constant. That could be extended to
 936     // 2 variables if we computed the sign bit for each.
 937     //
 938     // Make sure that a constant is not the minimum signed value because taking
 939     // the abs() of that is undefined.
 940     Type *Ty = X->getType();
 941     const APInt *C;
 942     if (match(X, m_APInt(C)) && !C->isMinSignedValue()) {
 943       // Is the variable divisor magnitude always greater than the constant
 944       // dividend magnitude?
 945       // |Y| > |C| --> Y < -abs(C) or Y > abs(C)
 946       Constant *PosDividendC = ConstantInt::get(Ty, C->abs());
 947       Constant *NegDividendC = ConstantInt::get(Ty, -C->abs());
 948       if (isICmpTrue(CmpInst::ICMP_SLT, Y, NegDividendC, Q, MaxRecurse) ||
 949           isICmpTrue(CmpInst::ICMP_SGT, Y, PosDividendC, Q, MaxRecurse))
 950         return true;
 951     }
 952     if (match(Y, m_APInt(C))) {
 953       // Special-case: we can't take the abs() of a minimum signed value. If
 954       // that's the divisor, then all we have to do is prove that the dividend
 955       // is also not the minimum signed value.
 956       if (C->isMinSignedValue())
 957         return isICmpTrue(CmpInst::ICMP_NE, X, Y, Q, MaxRecurse);
 958
 959       // Is the variable dividend magnitude always less than the constant
 960       // divisor magnitude?
 961       // |X| < |C| --> X > -abs(C) and X < abs(C)
 962       Constant *PosDivisorC = ConstantInt::get(Ty, C->abs());
 963       Constant *NegDivisorC = ConstantInt::get(Ty, -C->abs());
 964       if (isICmpTrue(CmpInst::ICMP_SGT, X, NegDivisorC, Q, MaxRecurse) &&
 965           isICmpTrue(CmpInst::ICMP_SLT, X, PosDivisorC, Q, MaxRecurse))
 966         return true;
 967     }
 968     return false;
 969   }
 970
 971   // IsSigned == false.
 972   // Is the dividend unsigned less than the divisor?
 973   return isICmpTrue(ICmpInst::ICMP_ULT, X, Y, Q, MaxRecurse);
 974 }
 975
 976 /// These are simplifications common to SDiv and UDiv.
 977 static Value *simplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
 978                           const SimplifyQuery &Q, unsigned MaxRecurse) {
 979   if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
 980     return C;
 981
 982   if (Value *V = simplifyDivRem(Op0, Op1, true))
 983     return V;
 984
 985   bool IsSigned = Opcode == Instruction::SDiv;
 986
 987   // (X * Y) / Y -> X if the multiplication does not overflow.
 988   Value *X;
 989   if (match(Op0, m_c_Mul(m_Value(X), m_Specific(Op1)))) {
 990     auto *Mul = cast<OverflowingBinaryOperator>(Op0);
 991     // If the Mul does not overflow, then we are good to go.
 992     if ((IsSigned && Mul->hasNoSignedWrap()) ||
 993         (!IsSigned && Mul->hasNoUnsignedWrap()))
 994       return X;
 995     // If X has the form X = A / Y, then X * Y cannot overflow.
 996     if ((IsSigned && match(X, m_SDiv(m_Value(), m_Specific(Op1)))) ||
 997         (!IsSigned && match(X, m_UDiv(m_Value(), m_Specific(Op1)))))
 998       return X;
 999   }
1000
1001   // (X rem Y) / Y -> 0
1002   if ((IsSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
1003       (!IsSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
1004     return Constant::getNullValue(Op0->getType());
1005
1006   // (X /u C1) /u C2 -> 0 if C1 * C2 overflow
1007   ConstantInt *C1, *C2;
1008   if (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_ConstantInt(C1))) &&
1009       match(Op1, m_ConstantInt(C2))) {
1010     bool Overflow;
1011     (void)C1->getValue().umul_ov(C2->getValue(), Overflow);
1012     if (Overflow)
1013       return Constant::getNullValue(Op0->getType());
1014   }
1015
1016   // If the operation is with the result of a select instruction, check whether
1017   // operating on either branch of the select always yields the same value.
1018   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1019     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1020       return V;
1021
1022   // If the operation is with the result of a phi instruction, check whether
1023   // operating on all incoming values of the phi always yields the same value.
1024   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1025     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1026       return V;
1027
1028   if (isDivZero(Op0, Op1, Q, MaxRecurse, IsSigned))
1029     return Constant::getNullValue(Op0->getType());
1030
1031   return nullptr;
1032 }
1033
1034 /// These are simplifications common to SRem and URem.
1035 static Value *simplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
1036                           const SimplifyQuery &Q, unsigned MaxRecurse) {
1037   if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
1038     return C;
1039
1040   if (Value *V = simplifyDivRem(Op0, Op1, false))
1041     return V;
1042
1043   // (X % Y) % Y -> X % Y
1044   if ((Opcode == Instruction::SRem &&
1045        match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
1046       (Opcode == Instruction::URem &&
1047        match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
1048     return Op0;
1049
1050   // (X << Y) % X -> 0
1051   if ((Opcode == Instruction::SRem &&
1052        match(Op0, m_NSWShl(m_Specific(Op1), m_Value()))) ||
1053       (Opcode == Instruction::URem &&
1054        match(Op0, m_NUWShl(m_Specific(Op1), m_Value()))))
1055     return Constant::getNullValue(Op0->getType());
1056
1057   // If the operation is with the result of a select instruction, check whether
1058   // operating on either branch of the select always yields the same value.
1059   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1060     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1061       return V;
1062
1063   // If the operation is with the result of a phi instruction, check whether
1064   // operating on all incoming values of the phi always yields the same value.
1065   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1066     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1067       return V;
1068
1069   // If X / Y == 0, then X % Y == X.
1070   if (isDivZero(Op0, Op1, Q, MaxRecurse, Opcode == Instruction::SRem))
1071     return Op0;
1072
1073   return nullptr;
1074 }
1075
1076 /// Given operands for an SDiv, see if we can fold the result.
1077 /// If not, this returns null.
1078 static Value *SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1079                                unsigned MaxRecurse) {
1080   return simplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse);
1081 }
1082
1083 Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1084   return ::SimplifySDivInst(Op0, Op1, Q, RecursionLimit);
1085 }
1086
1087 /// Given operands for a UDiv, see if we can fold the result.
1088 /// If not, this returns null.
1089 static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1090                                unsigned MaxRecurse) {
1091   return simplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse);
1092 }
1093
1094 Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1095   return ::SimplifyUDivInst(Op0, Op1, Q, RecursionLimit);
1096 }
1097
1098 /// Given operands for an SRem, see if we can fold the result.
1099 /// If not, this returns null.
1100 static Value *SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1101                                unsigned MaxRecurse) {
1102   // If the divisor is 0, the result is undefined, so assume the divisor is -1.
1103   // srem Op0, (sext i1 X) --> srem Op0, -1 --> 0
1104   Value *X;
1105   if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
1106     return ConstantInt::getNullValue(Op0->getType());
1107
1108   return simplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse);
1109 }
1110
1111 Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1112   return ::SimplifySRemInst(Op0, Op1, Q, RecursionLimit);
1113 }
1114
1115 /// Given operands for a URem, see if we can fold the result.
1116 /// If not, this returns null.
1117 static Value *SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1118                                unsigned MaxRecurse) {
1119   return simplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse);
1120 }
1121
1122 Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1123   return ::SimplifyURemInst(Op0, Op1, Q, RecursionLimit);
1124 }
1125
1126 /// Returns true if a shift by \c Amount always yields undef.
1127 static bool isUndefShift(Value *Amount) {
1128   Constant *C = dyn_cast<Constant>(Amount);
1129   if (!C)
1130     return false;
1131
1132   // X shift by undef -> undef because it may shift by the bitwidth.
1133   if (isa<UndefValue>(C))
1134     return true;
1135
1136   // Shifting by the bitwidth or more is undefined.
1137   if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
1138     if (CI->getValue().getLimitedValue() >=
1139         CI->getType()->getScalarSizeInBits())
1140       return true;
1141
1142   // If all lanes of a vector shift are undefined the whole shift is.
1143   if (isa<ConstantVector>(C) || isa<ConstantDataVector>(C)) {
1144     for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; ++I)
1145       if (!isUndefShift(C->getAggregateElement(I)))
1146         return false;
1147     return true;
1148   }
1149
1150   return false;
1151 }
1152
1153 /// Given operands for an Shl, LShr or AShr, see if we can fold the result.
1154 /// If not, this returns null.
1155 static Value *SimplifyShift(Instruction::BinaryOps Opcode, Value *Op0,
1156                             Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) {
1157   if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
1158     return C;
1159
1160   // 0 shift by X -> 0
1161   if (match(Op0, m_Zero()))
1162     return Constant::getNullValue(Op0->getType());
1163
1164   // X shift by 0 -> X
1165   // Shift-by-sign-extended bool must be shift-by-0 because shift-by-all-ones
1166   // would be poison.
1167   Value *X;
1168   if (match(Op1, m_Zero()) ||
1169       (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
1170     return Op0;
1171
1172   // Fold undefined shifts.
1173   if (isUndefShift(Op1))
1174     return UndefValue::get(Op0->getType());
1175
1176   // If the operation is with the result of a select instruction, check whether
1177   // operating on either branch of the select always yields the same value.
1178   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1179     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1180       return V;
1181
1182   // If the operation is with the result of a phi instruction, check whether
1183   // operating on all incoming values of the phi always yields the same value.
1184   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1185     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1186       return V;
1187
1188   // If any bits in the shift amount make that value greater than or equal to
1189   // the number of bits in the type, the shift is undefined.
1190   KnownBits Known = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
1191   if (Known.One.getLimitedValue() >= Known.getBitWidth())
1192     return UndefValue::get(Op0->getType());
1193
1194   // If all valid bits in the shift amount are known zero, the first operand is
1195   // unchanged.
1196   unsigned NumValidShiftBits = Log2_32_Ceil(Known.getBitWidth());
1197   if (Known.countMinTrailingZeros() >= NumValidShiftBits)
1198     return Op0;
1199
1200   return nullptr;
1201 }
1202
1203 /// Given operands for an Shl, LShr or AShr, see if we can
1204 /// fold the result.  If not, this returns null.
1205 static Value *SimplifyRightShift(Instruction::BinaryOps Opcode, Value *Op0,
1206                                  Value *Op1, bool isExact, const SimplifyQuery &Q,
1207                                  unsigned MaxRecurse) {
1208   if (Value *V = SimplifyShift(Opcode, Op0, Op1, Q, MaxRecurse))
1209     return V;
1210
1211   // X >> X -> 0
1212   if (Op0 == Op1)
1213     return Constant::getNullValue(Op0->getType());
1214
1215   // undef >> X -> 0
1216   // undef >> X -> undef (if it's exact)
1217   if (match(Op0, m_Undef()))
1218     return isExact ? Op0 : Constant::getNullValue(Op0->getType());
1219
1220   // The low bit cannot be shifted out of an exact shift if it is set.
1221   if (isExact) {
1222     KnownBits Op0Known = computeKnownBits(Op0, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
1223     if (Op0Known.One[0])
1224       return Op0;
1225   }
1226
1227   return nullptr;
1228 }
1229
1230 /// Given operands for an Shl, see if we can fold the result.
1231 /// If not, this returns null.
1232 static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1233                               const SimplifyQuery &Q, unsigned MaxRecurse) {
1234   if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse))
1235     return V;
1236
1237   // undef << X -> 0
1238   // undef << X -> undef if (if it's NSW/NUW)
1239   if (match(Op0, m_Undef()))
1240     return isNSW || isNUW ? Op0 : Constant::getNullValue(Op0->getType());
1241
1242   // (X >> A) << A -> X
1243   Value *X;
1244   if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1)))))
1245     return X;
1246
1247   // shl nuw i8 C, %x  ->  C  iff C has sign bit set.
1248   if (isNUW && match(Op0, m_Negative()))
1249     return Op0;
1250   // NOTE: could use computeKnownBits() / LazyValueInfo,
1251   // but the cost-benefit analysis suggests it isn't worth it.
1252
1253   return nullptr;
1254 }
1255
1256 Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1257                              const SimplifyQuery &Q) {
1258   return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
1259 }
1260
1261 /// Given operands for an LShr, see if we can fold the result.
1262 /// If not, this returns null.
1263 static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1264                                const SimplifyQuery &Q, unsigned MaxRecurse) {
1265   if (Value *V = SimplifyRightShift(Instruction::LShr, Op0, Op1, isExact, Q,
1266                                     MaxRecurse))
1267       return V;
1268
1269   // (X << A) >> A -> X
1270   Value *X;
1271   if (match(Op0, m_NUWShl(m_Value(X), m_Specific(Op1))))
1272     return X;
1273
1274   return nullptr;
1275 }
1276
1277 Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1278                               const SimplifyQuery &Q) {
1279   return ::SimplifyLShrInst(Op0, Op1, isExact, Q, RecursionLimit);
1280 }
1281
1282 /// Given operands for an AShr, see if we can fold the result.
1283 /// If not, this returns null.
1284 static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1285                                const SimplifyQuery &Q, unsigned MaxRecurse) {
1286   if (Value *V = SimplifyRightShift(Instruction::AShr, Op0, Op1, isExact, Q,
1287                                     MaxRecurse))
1288     return V;
1289
1290   // all ones >>a X -> -1
1291   // Do not return Op0 because it may contain undef elements if it's a vector.
1292   if (match(Op0, m_AllOnes()))
1293     return Constant::getAllOnesValue(Op0->getType());
1294
1295   // (X << A) >> A -> X
1296   Value *X;
1297   if (match(Op0, m_NSWShl(m_Value(X), m_Specific(Op1))))
1298     return X;
1299
1300   // Arithmetic shifting an all-sign-bit value is a no-op.
1301   unsigned NumSignBits = ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
1302   if (NumSignBits == Op0->getType()->getScalarSizeInBits())
1303     return Op0;
1304
1305   return nullptr;
1306 }
1307
1308 Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1309                               const SimplifyQuery &Q) {
1310   return ::SimplifyAShrInst(Op0, Op1, isExact, Q, RecursionLimit);
1311 }
1312
1313 /// Commuted variants are assumed to be handled by calling this function again
1314 /// with the parameters swapped.
1315 static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp,
1316                                          ICmpInst *UnsignedICmp, bool IsAnd) {
1317   Value *X, *Y;
1318
1319   ICmpInst::Predicate EqPred;
1320   if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) ||
1321       !ICmpInst::isEquality(EqPred))
1322     return nullptr;
1323
1324   ICmpInst::Predicate UnsignedPred;
1325   if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) &&
1326       ICmpInst::isUnsigned(UnsignedPred))
1327     ;
1328   else if (match(UnsignedICmp,
1329                  m_ICmp(UnsignedPred, m_Specific(Y), m_Value(X))) &&
1330            ICmpInst::isUnsigned(UnsignedPred))
1331     UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
1332   else
1333     return nullptr;
1334
1335   // X < Y && Y != 0  -->  X < Y
1336   // X < Y || Y != 0  -->  Y != 0
1337   if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE)
1338     return IsAnd ? UnsignedICmp : ZeroICmp;
1339
1340   // X >= Y || Y != 0  -->  true
1341   // X >= Y || Y == 0  -->  X >= Y
1342   if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd) {
1343     if (EqPred == ICmpInst::ICMP_NE)
1344       return getTrue(UnsignedICmp->getType());
1345     return UnsignedICmp;
1346   }
1347
1348   // X < Y && Y == 0  -->  false
1349   if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ &&
1350       IsAnd)
1351     return getFalse(UnsignedICmp->getType());
1352
1353   return nullptr;
1354 }
1355
1356 /// Commuted variants are assumed to be handled by calling this function again
1357 /// with the parameters swapped.
1358 static Value *simplifyAndOfICmpsWithSameOperands(ICmpInst *Op0, ICmpInst *Op1) {
1359   ICmpInst::Predicate Pred0, Pred1;
1360   Value *A ,*B;
1361   if (!match(Op0, m_ICmp(Pred0, m_Value(A), m_Value(B))) ||
1362       !match(Op1, m_ICmp(Pred1, m_Specific(A), m_Specific(B))))
1363     return nullptr;
1364
1365   // We have (icmp Pred0, A, B) & (icmp Pred1, A, B).
1366   // If Op1 is always implied true by Op0, then Op0 is a subset of Op1, and we
1367   // can eliminate Op1 from this 'and'.
1368   if (ICmpInst::isImpliedTrueByMatchingCmp(Pred0, Pred1))
1369     return Op0;
1370
1371   // Check for any combination of predicates that are guaranteed to be disjoint.
1372   if ((Pred0 == ICmpInst::getInversePredicate(Pred1)) ||
1373       (Pred0 == ICmpInst::ICMP_EQ && ICmpInst::isFalseWhenEqual(Pred1)) ||
1374       (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT) ||
1375       (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT))
1376     return getFalse(Op0->getType());
1377
1378   return nullptr;
1379 }
1380
1381 /// Commuted variants are assumed to be handled by calling this function again
1382 /// with the parameters swapped.
1383 static Value *simplifyOrOfICmpsWithSameOperands(ICmpInst *Op0, ICmpInst *Op1) {
1384   ICmpInst::Predicate Pred0, Pred1;
1385   Value *A ,*B;
1386   if (!match(Op0, m_ICmp(Pred0, m_Value(A), m_Value(B))) ||
1387       !match(Op1, m_ICmp(Pred1, m_Specific(A), m_Specific(B))))
1388     return nullptr;
1389
1390   // We have (icmp Pred0, A, B) | (icmp Pred1, A, B).
1391   // If Op1 is always implied true by Op0, then Op0 is a subset of Op1, and we
1392   // can eliminate Op0 from this 'or'.
1393   if (ICmpInst::isImpliedTrueByMatchingCmp(Pred0, Pred1))
1394     return Op1;
1395
1396   // Check for any combination of predicates that cover the entire range of
1397   // possibilities.
1398   if ((Pred0 == ICmpInst::getInversePredicate(Pred1)) ||
1399       (Pred0 == ICmpInst::ICMP_NE && ICmpInst::isTrueWhenEqual(Pred1)) ||
1400       (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGE) ||
1401       (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGE))
1402     return getTrue(Op0->getType());
1403
1404   return nullptr;
1405 }
1406
1407 /// Test if a pair of compares with a shared operand and 2 constants has an
1408 /// empty set intersection, full set union, or if one compare is a superset of
1409 /// the other.
1410 static Value *simplifyAndOrOfICmpsWithConstants(ICmpInst *Cmp0, ICmpInst *Cmp1,
1411                                                 bool IsAnd) {
1412   // Look for this pattern: {and/or} (icmp X, C0), (icmp X, C1)).
1413   if (Cmp0->getOperand(0) != Cmp1->getOperand(0))
1414     return nullptr;
1415
1416   const APInt *C0, *C1;
1417   if (!match(Cmp0->getOperand(1), m_APInt(C0)) ||
1418       !match(Cmp1->getOperand(1), m_APInt(C1)))
1419     return nullptr;
1420
1421   auto Range0 = ConstantRange::makeExactICmpRegion(Cmp0->getPredicate(), *C0);
1422   auto Range1 = ConstantRange::makeExactICmpRegion(Cmp1->getPredicate(), *C1);
1423
1424   // For and-of-compares, check if the intersection is empty:
1425   // (icmp X, C0) && (icmp X, C1) --> empty set --> false
1426   if (IsAnd && Range0.intersectWith(Range1).isEmptySet())
1427     return getFalse(Cmp0->getType());
1428
1429   // For or-of-compares, check if the union is full:
1430   // (icmp X, C0) || (icmp X, C1) --> full set --> true
1431   if (!IsAnd && Range0.unionWith(Range1).isFullSet())
1432     return getTrue(Cmp0->getType());
1433
1434   // Is one range a superset of the other?
1435   // If this is and-of-compares, take the smaller set:
1436   // (icmp sgt X, 4) && (icmp sgt X, 42) --> icmp sgt X, 42
1437   // If this is or-of-compares, take the larger set:
1438   // (icmp sgt X, 4) || (icmp sgt X, 42) --> icmp sgt X, 4
1439   if (Range0.contains(Range1))
1440     return IsAnd ? Cmp1 : Cmp0;
1441   if (Range1.contains(Range0))
1442     return IsAnd ? Cmp0 : Cmp1;
1443
1444   return nullptr;
1445 }
1446
1447 static Value *simplifyAndOrOfICmpsWithZero(ICmpInst *Cmp0, ICmpInst *Cmp1,
1448                                            bool IsAnd) {
1449   ICmpInst::Predicate P0 = Cmp0->getPredicate(), P1 = Cmp1->getPredicate();
1450   if (!match(Cmp0->getOperand(1), m_Zero()) ||
1451       !match(Cmp1->getOperand(1), m_Zero()) || P0 != P1)
1452     return nullptr;
1453
1454   if ((IsAnd && P0 != ICmpInst::ICMP_NE) || (!IsAnd && P1 != ICmpInst::ICMP_EQ))
1455     return nullptr;
1456
1457   // We have either "(X == 0 || Y == 0)" or "(X != 0 && Y != 0)".
1458   Value *X = Cmp0->getOperand(0);
1459   Value *Y = Cmp1->getOperand(0);
1460
1461   // If one of the compares is a masked version of a (not) null check, then
1462   // that compare implies the other, so we eliminate the other. Optionally, look
1463   // through a pointer-to-int cast to match a null check of a pointer type.
1464
1465   // (X == 0) || (([ptrtoint] X & ?) == 0) --> ([ptrtoint] X & ?) == 0
1466   // (X == 0) || ((? & [ptrtoint] X) == 0) --> (? & [ptrtoint] X) == 0
1467   // (X != 0) && (([ptrtoint] X & ?) != 0) --> ([ptrtoint] X & ?) != 0
1468   // (X != 0) && ((? & [ptrtoint] X) != 0) --> (? & [ptrtoint] X) != 0
1469   if (match(Y, m_c_And(m_Specific(X), m_Value())) ||
1470       match(Y, m_c_And(m_PtrToInt(m_Specific(X)), m_Value())))
1471     return Cmp1;
1472
1473   // (([ptrtoint] Y & ?) == 0) || (Y == 0) --> ([ptrtoint] Y & ?) == 0
1474   // ((? & [ptrtoint] Y) == 0) || (Y == 0) --> (? & [ptrtoint] Y) == 0
1475   // (([ptrtoint] Y & ?) != 0) && (Y != 0) --> ([ptrtoint] Y & ?) != 0
1476   // ((? & [ptrtoint] Y) != 0) && (Y != 0) --> (? & [ptrtoint] Y) != 0
1477   if (match(X, m_c_And(m_Specific(Y), m_Value())) ||
1478       match(X, m_c_And(m_PtrToInt(m_Specific(Y)), m_Value())))
1479     return Cmp0;
1480
1481   return nullptr;
1482 }
1483
1484 static Value *simplifyAndOfICmpsWithAdd(ICmpInst *Op0, ICmpInst *Op1) {
1485   // (icmp (add V, C0), C1) & (icmp V, C0)
1486   ICmpInst::Predicate Pred0, Pred1;
1487   const APInt *C0, *C1;
1488   Value *V;
1489   if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_APInt(C0)), m_APInt(C1))))
1490     return nullptr;
1491
1492   if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Value())))
1493     return nullptr;
1494
1495   auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0));
1496   if (AddInst->getOperand(1) != Op1->getOperand(1))
1497     return nullptr;
1498
1499   Type *ITy = Op0->getType();
1500   bool isNSW = AddInst->hasNoSignedWrap();
1501   bool isNUW = AddInst->hasNoUnsignedWrap();
1502
1503   const APInt Delta = *C1 - *C0;
1504   if (C0->isStrictlyPositive()) {
1505     if (Delta == 2) {
1506       if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_SGT)
1507         return getFalse(ITy);
1508       if (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT && isNSW)
1509         return getFalse(ITy);
1510     }
1511     if (Delta == 1) {
1512       if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_SGT)
1513         return getFalse(ITy);
1514       if (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGT && isNSW)
1515         return getFalse(ITy);
1516     }
1517   }
1518   if (C0->getBoolValue() && isNUW) {
1519     if (Delta == 2)
1520       if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT)
1521         return getFalse(ITy);
1522     if (Delta == 1)
1523       if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGT)
1524         return getFalse(ITy);
1525   }
1526
1527   return nullptr;
1528 }
1529
1530 static Value *simplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
1531   if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true))
1532     return X;
1533   if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/true))
1534     return X;
1535
1536   if (Value *X = simplifyAndOfICmpsWithSameOperands(Op0, Op1))
1537     return X;
1538   if (Value *X = simplifyAndOfICmpsWithSameOperands(Op1, Op0))
1539     return X;
1540
1541   if (Value *X = simplifyAndOrOfICmpsWithConstants(Op0, Op1, true))
1542     return X;
1543
1544   if (Value *X = simplifyAndOrOfICmpsWithZero(Op0, Op1, true))
1545     return X;
1546
1547   if (Value *X = simplifyAndOfICmpsWithAdd(Op0, Op1))
1548     return X;
1549   if (Value *X = simplifyAndOfICmpsWithAdd(Op1, Op0))
1550     return X;
1551
1552   return nullptr;
1553 }
1554
1555 static Value *simplifyOrOfICmpsWithAdd(ICmpInst *Op0, ICmpInst *Op1) {
1556   // (icmp (add V, C0), C1) | (icmp V, C0)
1557   ICmpInst::Predicate Pred0, Pred1;
1558   const APInt *C0, *C1;
1559   Value *V;
1560   if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_APInt(C0)), m_APInt(C1))))
1561     return nullptr;
1562
1563   if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Value())))
1564     return nullptr;
1565
1566   auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0));
1567   if (AddInst->getOperand(1) != Op1->getOperand(1))
1568     return nullptr;
1569
1570   Type *ITy = Op0->getType();
1571   bool isNSW = AddInst->hasNoSignedWrap();
1572   bool isNUW = AddInst->hasNoUnsignedWrap();
1573
1574   const APInt Delta = *C1 - *C0;
1575   if (C0->isStrictlyPositive()) {
1576     if (Delta == 2) {
1577       if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_SLE)
1578         return getTrue(ITy);
1579       if (Pred0 == ICmpInst::ICMP_SGE && Pred1 == ICmpInst::ICMP_SLE && isNSW)
1580         return getTrue(ITy);
1581     }
1582     if (Delta == 1) {
1583       if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_SLE)
1584         return getTrue(ITy);
1585       if (Pred0 == ICmpInst::ICMP_SGT && Pred1 == ICmpInst::ICMP_SLE && isNSW)
1586         return getTrue(ITy);
1587     }
1588   }
1589   if (C0->getBoolValue() && isNUW) {
1590     if (Delta == 2)
1591       if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_ULE)
1592         return getTrue(ITy);
1593     if (Delta == 1)
1594       if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_ULE)
1595         return getTrue(ITy);
1596   }
1597
1598   return nullptr;
1599 }
1600
1601 static Value *simplifyOrOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
1602   if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false))
1603     return X;
1604   if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/false))
1605     return X;
1606
1607   if (Value *X = simplifyOrOfICmpsWithSameOperands(Op0, Op1))
1608     return X;
1609   if (Value *X = simplifyOrOfICmpsWithSameOperands(Op1, Op0))
1610     return X;
1611
1612   if (Value *X = simplifyAndOrOfICmpsWithConstants(Op0, Op1, false))
1613     return X;
1614
1615   if (Value *X = simplifyAndOrOfICmpsWithZero(Op0, Op1, false))
1616     return X;
1617
1618   if (Value *X = simplifyOrOfICmpsWithAdd(Op0, Op1))
1619     return X;
1620   if (Value *X = simplifyOrOfICmpsWithAdd(Op1, Op0))
1621     return X;
1622
1623   return nullptr;
1624 }
1625
1626 static Value *simplifyAndOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd) {
1627   Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
1628   Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
1629   if (LHS0->getType() != RHS0->getType())
1630     return nullptr;
1631
1632   FCmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1633   if ((PredL == FCmpInst::FCMP_ORD && PredR == FCmpInst::FCMP_ORD && IsAnd) ||
1634       (PredL == FCmpInst::FCMP_UNO && PredR == FCmpInst::FCMP_UNO && !IsAnd)) {
1635     // (fcmp ord NNAN, X) & (fcmp ord X, Y) --> fcmp ord X, Y
1636     // (fcmp ord NNAN, X) & (fcmp ord Y, X) --> fcmp ord Y, X
1637     // (fcmp ord X, NNAN) & (fcmp ord X, Y) --> fcmp ord X, Y
1638     // (fcmp ord X, NNAN) & (fcmp ord Y, X) --> fcmp ord Y, X
1639     // (fcmp uno NNAN, X) | (fcmp uno X, Y) --> fcmp uno X, Y
1640     // (fcmp uno NNAN, X) | (fcmp uno Y, X) --> fcmp uno Y, X
1641     // (fcmp uno X, NNAN) | (fcmp uno X, Y) --> fcmp uno X, Y
1642     // (fcmp uno X, NNAN) | (fcmp uno Y, X) --> fcmp uno Y, X
1643     if ((isKnownNeverNaN(LHS0) && (LHS1 == RHS0 || LHS1 == RHS1)) ||
1644         (isKnownNeverNaN(LHS1) && (LHS0 == RHS0 || LHS0 == RHS1)))
1645       return RHS;
1646
1647     // (fcmp ord X, Y) & (fcmp ord NNAN, X) --> fcmp ord X, Y
1648     // (fcmp ord Y, X) & (fcmp ord NNAN, X) --> fcmp ord Y, X
1649     // (fcmp ord X, Y) & (fcmp ord X, NNAN) --> fcmp ord X, Y
1650     // (fcmp ord Y, X) & (fcmp ord X, NNAN) --> fcmp ord Y, X
1651     // (fcmp uno X, Y) | (fcmp uno NNAN, X) --> fcmp uno X, Y
1652     // (fcmp uno Y, X) | (fcmp uno NNAN, X) --> fcmp uno Y, X
1653     // (fcmp uno X, Y) | (fcmp uno X, NNAN) --> fcmp uno X, Y
1654     // (fcmp uno Y, X) | (fcmp uno X, NNAN) --> fcmp uno Y, X
1655     if ((isKnownNeverNaN(RHS0) && (RHS1 == LHS0 || RHS1 == LHS1)) ||
1656         (isKnownNeverNaN(RHS1) && (RHS0 == LHS0 || RHS0 == LHS1)))
1657       return LHS;
1658   }
1659
1660   return nullptr;
1661 }
1662
1663 static Value *simplifyAndOrOfCmps(Value *Op0, Value *Op1, bool IsAnd) {
1664   // Look through casts of the 'and' operands to find compares.
1665   auto *Cast0 = dyn_cast<CastInst>(Op0);
1666   auto *Cast1 = dyn_cast<CastInst>(Op1);
1667   if (Cast0 && Cast1 && Cast0->getOpcode() == Cast1->getOpcode() &&
1668       Cast0->getSrcTy() == Cast1->getSrcTy()) {
1669     Op0 = Cast0->getOperand(0);
1670     Op1 = Cast1->getOperand(0);
1671   }
1672
1673   Value *V = nullptr;
1674   auto *ICmp0 = dyn_cast<ICmpInst>(Op0);
1675   auto *ICmp1 = dyn_cast<ICmpInst>(Op1);
1676   if (ICmp0 && ICmp1)
1677     V = IsAnd ? simplifyAndOfICmps(ICmp0, ICmp1) :
1678                 simplifyOrOfICmps(ICmp0, ICmp1);
1679
1680   auto *FCmp0 = dyn_cast<FCmpInst>(Op0);
1681   auto *FCmp1 = dyn_cast<FCmpInst>(Op1);
1682   if (FCmp0 && FCmp1)
1683     V = simplifyAndOrOfFCmps(FCmp0, FCmp1, IsAnd);
1684
1685   if (!V)
1686     return nullptr;
1687   if (!Cast0)
1688     return V;
1689
1690   // If we looked through casts, we can only handle a constant simplification
1691   // because we are not allowed to create a cast instruction here.
1692   if (auto *C = dyn_cast<Constant>(V))
1693     return ConstantExpr::getCast(Cast0->getOpcode(), C, Cast0->getType());
1694
1695   return nullptr;
1696 }
1697
1698 /// Given operands for an And, see if we can fold the result.
1699 /// If not, this returns null.
1700 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1701                               unsigned MaxRecurse) {
1702   if (Constant *C = foldOrCommuteConstant(Instruction::And, Op0, Op1, Q))
1703     return C;
1704
1705   // X & undef -> 0
1706   if (match(Op1, m_Undef()))
1707     return Constant::getNullValue(Op0->getType());
1708
1709   // X & X = X
1710   if (Op0 == Op1)
1711     return Op0;
1712
1713   // X & 0 = 0
1714   if (match(Op1, m_Zero()))
1715     return Constant::getNullValue(Op0->getType());
1716
1717   // X & -1 = X
1718   if (match(Op1, m_AllOnes()))
1719     return Op0;
1720
1721   // A & ~A  =  ~A & A  =  0
1722   if (match(Op0, m_Not(m_Specific(Op1))) ||
1723       match(Op1, m_Not(m_Specific(Op0))))
1724     return Constant::getNullValue(Op0->getType());
1725
1726   // (A | ?) & A = A
1727   if (match(Op0, m_c_Or(m_Specific(Op1), m_Value())))
1728     return Op1;
1729
1730   // A & (A | ?) = A
1731   if (match(Op1, m_c_Or(m_Specific(Op0), m_Value())))
1732     return Op0;
1733
1734   // A mask that only clears known zeros of a shifted value is a no-op.
1735   Value *X;
1736   const APInt *Mask;
1737   const APInt *ShAmt;
1738   if (match(Op1, m_APInt(Mask))) {
1739     // If all bits in the inverted and shifted mask are clear:
1740     // and (shl X, ShAmt), Mask --> shl X, ShAmt
1741     if (match(Op0, m_Shl(m_Value(X), m_APInt(ShAmt))) &&
1742         (~(*Mask)).lshr(*ShAmt).isNullValue())
1743       return Op0;
1744
1745     // If all bits in the inverted and shifted mask are clear:
1746     // and (lshr X, ShAmt), Mask --> lshr X, ShAmt
1747     if (match(Op0, m_LShr(m_Value(X), m_APInt(ShAmt))) &&
1748         (~(*Mask)).shl(*ShAmt).isNullValue())
1749       return Op0;
1750   }
1751
1752   // A & (-A) = A if A is a power of two or zero.
1753   if (match(Op0, m_Neg(m_Specific(Op1))) ||
1754       match(Op1, m_Neg(m_Specific(Op0)))) {
1755     if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
1756                                Q.DT))
1757       return Op0;
1758     if (isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
1759                                Q.DT))
1760       return Op1;
1761   }
1762
1763   if (Value *V = simplifyAndOrOfCmps(Op0, Op1, true))
1764     return V;
1765
1766   // Try some generic simplifications for associative operations.
1767   if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q,
1768                                           MaxRecurse))
1769     return V;
1770
1771   // And distributes over Or.  Try some generic simplifications based on this.
1772   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
1773                              Q, MaxRecurse))
1774     return V;
1775
1776   // And distributes over Xor.  Try some generic simplifications based on this.
1777   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor,
1778                              Q, MaxRecurse))
1779     return V;
1780
1781   // If the operation is with the result of a select instruction, check whether
1782   // operating on either branch of the select always yields the same value.
1783   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1784     if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q,
1785                                          MaxRecurse))
1786       return V;
1787
1788   // If the operation is with the result of a phi instruction, check whether
1789   // operating on all incoming values of the phi always yields the same value.
1790   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1791     if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q,
1792                                       MaxRecurse))
1793       return V;
1794
1795   return nullptr;
1796 }
1797
1798 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1799   return ::SimplifyAndInst(Op0, Op1, Q, RecursionLimit);
1800 }
1801
1802 /// Given operands for an Or, see if we can fold the result.
1803 /// If not, this returns null.
1804 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1805                              unsigned MaxRecurse) {
1806   if (Constant *C = foldOrCommuteConstant(Instruction::Or, Op0, Op1, Q))
1807     return C;
1808
1809   // X | undef -> -1
1810   // X | -1 = -1
1811   // Do not return Op1 because it may contain undef elements if it's a vector.
1812   if (match(Op1, m_Undef()) || match(Op1, m_AllOnes()))
1813     return Constant::getAllOnesValue(Op0->getType());
1814
1815   // X | X = X
1816   // X | 0 = X
1817   if (Op0 == Op1 || match(Op1, m_Zero()))
1818     return Op0;
1819
1820   // A | ~A  =  ~A | A  =  -1
1821   if (match(Op0, m_Not(m_Specific(Op1))) ||
1822       match(Op1, m_Not(m_Specific(Op0))))
1823     return Constant::getAllOnesValue(Op0->getType());
1824
1825   // (A & ?) | A = A
1826   if (match(Op0, m_c_And(m_Specific(Op1), m_Value())))
1827     return Op1;
1828
1829   // A | (A & ?) = A
1830   if (match(Op1, m_c_And(m_Specific(Op0), m_Value())))
1831     return Op0;
1832
1833   // ~(A & ?) | A = -1
1834   if (match(Op0, m_Not(m_c_And(m_Specific(Op1), m_Value()))))
1835     return Constant::getAllOnesValue(Op1->getType());
1836
1837   // A | ~(A & ?) = -1
1838   if (match(Op1, m_Not(m_c_And(m_Specific(Op1), m_Value()))))
1839     return Constant::getAllOnesValue(Op0->getType());
1840
1841   Value *A, *B;
1842   // (A & ~B) | (A ^ B) -> (A ^ B)
1843   // (~B & A) | (A ^ B) -> (A ^ B)
1844   // (A & ~B) | (B ^ A) -> (B ^ A)
1845   // (~B & A) | (B ^ A) -> (B ^ A)
1846   if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
1847       (match(Op0, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
1848        match(Op0, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
1849     return Op1;
1850
1851   // Commute the 'or' operands.
1852   // (A ^ B) | (A & ~B) -> (A ^ B)
1853   // (A ^ B) | (~B & A) -> (A ^ B)
1854   // (B ^ A) | (A & ~B) -> (B ^ A)
1855   // (B ^ A) | (~B & A) -> (B ^ A)
1856   if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
1857       (match(Op1, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
1858        match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
1859     return Op0;
1860
1861   // (A & B) | (~A ^ B) -> (~A ^ B)
1862   // (B & A) | (~A ^ B) -> (~A ^ B)
1863   // (A & B) | (B ^ ~A) -> (B ^ ~A)
1864   // (B & A) | (B ^ ~A) -> (B ^ ~A)
1865   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1866       (match(Op1, m_c_Xor(m_Specific(A), m_Not(m_Specific(B)))) ||
1867        match(Op1, m_c_Xor(m_Not(m_Specific(A)), m_Specific(B)))))
1868     return Op1;
1869
1870   // (~A ^ B) | (A & B) -> (~A ^ B)
1871   // (~A ^ B) | (B & A) -> (~A ^ B)
1872   // (B ^ ~A) | (A & B) -> (B ^ ~A)
1873   // (B ^ ~A) | (B & A) -> (B ^ ~A)
1874   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
1875       (match(Op0, m_c_Xor(m_Specific(A), m_Not(m_Specific(B)))) ||
1876        match(Op0, m_c_Xor(m_Not(m_Specific(A)), m_Specific(B)))))
1877     return Op0;
1878
1879   if (Value *V = simplifyAndOrOfCmps(Op0, Op1, false))
1880     return V;
1881
1882   // Try some generic simplifications for associative operations.
1883   if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q,
1884                                           MaxRecurse))
1885     return V;
1886
1887   // Or distributes over And.  Try some generic simplifications based on this.
1888   if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q,
1889                              MaxRecurse))
1890     return V;
1891
1892   // If the operation is with the result of a select instruction, check whether
1893   // operating on either branch of the select always yields the same value.
1894   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1895     if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q,
1896                                          MaxRecurse))
1897       return V;
1898
1899   // (A & C1)|(B & C2)
1900   const APInt *C1, *C2;
1901   if (match(Op0, m_And(m_Value(A), m_APInt(C1))) &&
1902       match(Op1, m_And(m_Value(B), m_APInt(C2)))) {
1903     if (*C1 == ~*C2) {
1904       // (A & C1)|(B & C2)
1905       // If we have: ((V + N) & C1) | (V & C2)
1906       // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0
1907       // replace with V+N.
1908       Value *N;
1909       if (C2->isMask() && // C2 == 0+1+
1910           match(A, m_c_Add(m_Specific(B), m_Value(N)))) {
1911         // Add commutes, try both ways.
1912         if (MaskedValueIsZero(N, *C2, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
1913           return A;
1914       }
1915       // Or commutes, try both ways.
1916       if (C1->isMask() &&
1917           match(B, m_c_Add(m_Specific(A), m_Value(N)))) {
1918         // Add commutes, try both ways.
1919         if (MaskedValueIsZero(N, *C1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
1920           return B;
1921       }
1922     }
1923   }
1924
1925   // If the operation is with the result of a phi instruction, check whether
1926   // operating on all incoming values of the phi always yields the same value.
1927   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1928     if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse))
1929       return V;
1930
1931   return nullptr;
1932 }
1933
1934 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1935   return ::SimplifyOrInst(Op0, Op1, Q, RecursionLimit);
1936 }
1937
1938 /// Given operands for a Xor, see if we can fold the result.
1939 /// If not, this returns null.
1940 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1941                               unsigned MaxRecurse) {
1942   if (Constant *C = foldOrCommuteConstant(Instruction::Xor, Op0, Op1, Q))
1943     return C;
1944
1945   // A ^ undef -> undef
1946   if (match(Op1, m_Undef()))
1947     return Op1;
1948
1949   // A ^ 0 = A
1950   if (match(Op1, m_Zero()))
1951     return Op0;
1952
1953   // A ^ A = 0
1954   if (Op0 == Op1)
1955     return Constant::getNullValue(Op0->getType());
1956
1957   // A ^ ~A  =  ~A ^ A  =  -1
1958   if (match(Op0, m_Not(m_Specific(Op1))) ||
1959       match(Op1, m_Not(m_Specific(Op0))))
1960     return Constant::getAllOnesValue(Op0->getType());
1961
1962   // Try some generic simplifications for associative operations.
1963   if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q,
1964                                           MaxRecurse))
1965     return V;
1966
1967   // Threading Xor over selects and phi nodes is pointless, so don't bother.
1968   // Threading over the select in "A ^ select(cond, B, C)" means evaluating
1969   // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
1970   // only if B and C are equal.  If B and C are equal then (since we assume
1971   // that operands have already been simplified) "select(cond, B, C)" should
1972   // have been simplified to the common value of B and C already.  Analysing
1973   // "A^B" and "A^C" thus gains nothing, but costs compile time.  Similarly
1974   // for threading over phi nodes.
1975
1976   return nullptr;
1977 }
1978
1979 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1980   return ::SimplifyXorInst(Op0, Op1, Q, RecursionLimit);
1981 }
1982
1983
1984 static Type *GetCompareTy(Value *Op) {
1985   return CmpInst::makeCmpResultType(Op->getType());
1986 }
1987
1988 /// Rummage around inside V looking for something equivalent to the comparison
1989 /// "LHS Pred RHS". Return such a value if found, otherwise return null.
1990 /// Helper function for analyzing max/min idioms.
1991 static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred,
1992                                          Value *LHS, Value *RHS) {
1993   SelectInst *SI = dyn_cast<SelectInst>(V);
1994   if (!SI)
1995     return nullptr;
1996   CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
1997   if (!Cmp)
1998     return nullptr;
1999   Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1);
2000   if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS)
2001     return Cmp;
2002   if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) &&
2003       LHS == CmpRHS && RHS == CmpLHS)
2004     return Cmp;
2005   return nullptr;
2006 }
2007
2008 // A significant optimization not implemented here is assuming that alloca
2009 // addresses are not equal to incoming argument values. They don't *alias*,
2010 // as we say, but that doesn't mean they aren't equal, so we take a
2011 // conservative approach.
2012 //
2013 // This is inspired in part by C++11 5.10p1:
2014 //   "Two pointers of the same type compare equal if and only if they are both
2015 //    null, both point to the same function, or both represent the same
2016 //    address."
2017 //
2018 // This is pretty permissive.
2019 //
2020 // It's also partly due to C11 6.5.9p6:
2021 //   "Two pointers compare equal if and only if both are null pointers, both are
2022 //    pointers to the same object (including a pointer to an object and a
2023 //    subobject at its beginning) or function, both are pointers to one past the
2024 //    last element of the same array object, or one is a pointer to one past the
2025 //    end of one array object and the other is a pointer to the start of a
2026 //    different array object that happens to immediately follow the first array
2027 //    object in the address space.)
2028 //
2029 // C11's version is more restrictive, however there's no reason why an argument
2030 // couldn't be a one-past-the-end value for a stack object in the caller and be
2031 // equal to the beginning of a stack object in the callee.
2032 //
2033 // If the C and C++ standards are ever made sufficiently restrictive in this
2034 // area, it may be possible to update LLVM's semantics accordingly and reinstate
2035 // this optimization.
2036 static Constant *
2037 computePointerICmp(const DataLayout &DL, const TargetLibraryInfo *TLI,
2038                    const DominatorTree *DT, CmpInst::Predicate Pred,
2039                    AssumptionCache *AC, const Instruction *CxtI,
2040                    Value *LHS, Value *RHS) {
2041   // First, skip past any trivial no-ops.
2042   LHS = LHS->stripPointerCasts();
2043   RHS = RHS->stripPointerCasts();
2044
2045   // A non-null pointer is not equal to a null pointer.
2046   if (llvm::isKnownNonZero(LHS, DL) && isa<ConstantPointerNull>(RHS) &&
2047       (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE))
2048     return ConstantInt::get(GetCompareTy(LHS),
2049                             !CmpInst::isTrueWhenEqual(Pred));
2050
2051   // We can only fold certain predicates on pointer comparisons.
2052   switch (Pred) {
2053   default:
2054     return nullptr;
2055
2056     // Equality comaprisons are easy to fold.
2057   case CmpInst::ICMP_EQ:
2058   case CmpInst::ICMP_NE:
2059     break;
2060
2061     // We can only handle unsigned relational comparisons because 'inbounds' on
2062     // a GEP only protects against unsigned wrapping.
2063   case CmpInst::ICMP_UGT:
2064   case CmpInst::ICMP_UGE:
2065   case CmpInst::ICMP_ULT:
2066   case CmpInst::ICMP_ULE:
2067     // However, we have to switch them to their signed variants to handle
2068     // negative indices from the base pointer.
2069     Pred = ICmpInst::getSignedPredicate(Pred);
2070     break;
2071   }
2072
2073   // Strip off any constant offsets so that we can reason about them.
2074   // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets
2075   // here and compare base addresses like AliasAnalysis does, however there are
2076   // numerous hazards. AliasAnalysis and its utilities rely on special rules
2077   // governing loads and stores which don't apply to icmps. Also, AliasAnalysis
2078   // doesn't need to guarantee pointer inequality when it says NoAlias.
2079   Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
2080   Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
2081
2082   // If LHS and RHS are related via constant offsets to the same base
2083   // value, we can replace it with an icmp which just compares the offsets.
2084   if (LHS == RHS)
2085     return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset);
2086
2087   // Various optimizations for (in)equality comparisons.
2088   if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) {
2089     // Different non-empty allocations that exist at the same time have
2090     // different addresses (if the program can tell). Global variables always
2091     // exist, so they always exist during the lifetime of each other and all
2092     // allocas. Two different allocas usually have different addresses...
2093     //
2094     // However, if there's an @llvm.stackrestore dynamically in between two
2095     // allocas, they may have the same address. It's tempting to reduce the
2096     // scope of the problem by only looking at *static* allocas here. That would
2097     // cover the majority of allocas while significantly reducing the likelihood
2098     // of having an @llvm.stackrestore pop up in the middle. However, it's not
2099     // actually impossible for an @llvm.stackrestore to pop up in the middle of
2100     // an entry block. Also, if we have a block that's not attached to a
2101     // function, we can't tell if it's "static" under the current definition.
2102     // Theoretically, this problem could be fixed by creating a new kind of
2103     // instruction kind specifically for static allocas. Such a new instruction
2104     // could be required to be at the top of the entry block, thus preventing it
2105     // from being subject to a @llvm.stackrestore. Instcombine could even
2106     // convert regular allocas into these special allocas. It'd be nifty.
2107     // However, until then, this problem remains open.
2108     //
2109     // So, we'll assume that two non-empty allocas have different addresses
2110     // for now.
2111     //
2112     // With all that, if the offsets are within the bounds of their allocations
2113     // (and not one-past-the-end! so we can't use inbounds!), and their
2114     // allocations aren't the same, the pointers are not equal.
2115     //
2116     // Note that it's not necessary to check for LHS being a global variable
2117     // address, due to canonicalization and constant folding.
2118     if (isa<AllocaInst>(LHS) &&
2119         (isa<AllocaInst>(RHS) || isa<GlobalVariable>(RHS))) {
2120       ConstantInt *LHSOffsetCI = dyn_cast<ConstantInt>(LHSOffset);
2121       ConstantInt *RHSOffsetCI = dyn_cast<ConstantInt>(RHSOffset);
2122       uint64_t LHSSize, RHSSize;
2123       if (LHSOffsetCI && RHSOffsetCI &&
2124           getObjectSize(LHS, LHSSize, DL, TLI) &&
2125           getObjectSize(RHS, RHSSize, DL, TLI)) {
2126         const APInt &LHSOffsetValue = LHSOffsetCI->getValue();
2127         const APInt &RHSOffsetValue = RHSOffsetCI->getValue();
2128         if (!LHSOffsetValue.isNegative() &&
2129             !RHSOffsetValue.isNegative() &&
2130             LHSOffsetValue.ult(LHSSize) &&
2131             RHSOffsetValue.ult(RHSSize)) {
2132           return ConstantInt::get(GetCompareTy(LHS),
2133                                   !CmpInst::isTrueWhenEqual(Pred));
2134         }
2135       }
2136
2137       // Repeat the above check but this time without depending on DataLayout
2138       // or being able to compute a precise size.
2139       if (!cast<PointerType>(LHS->getType())->isEmptyTy() &&
2140           !cast<PointerType>(RHS->getType())->isEmptyTy() &&
2141           LHSOffset->isNullValue() &&
2142           RHSOffset->isNullValue())
2143         return ConstantInt::get(GetCompareTy(LHS),
2144                                 !CmpInst::isTrueWhenEqual(Pred));
2145     }
2146
2147     // Even if an non-inbounds GEP occurs along the path we can still optimize
2148     // equality comparisons concerning the result. We avoid walking the whole
2149     // chain again by starting where the last calls to
2150     // stripAndComputeConstantOffsets left off and accumulate the offsets.
2151     Constant *LHSNoBound = stripAndComputeConstantOffsets(DL, LHS, true);
2152     Constant *RHSNoBound = stripAndComputeConstantOffsets(DL, RHS, true);
2153     if (LHS == RHS)
2154       return ConstantExpr::getICmp(Pred,
2155                                    ConstantExpr::getAdd(LHSOffset, LHSNoBound),
2156                                    ConstantExpr::getAdd(RHSOffset, RHSNoBound));
2157
2158     // If one side of the equality comparison must come from a noalias call
2159     // (meaning a system memory allocation function), and the other side must
2160     // come from a pointer that cannot overlap with dynamically-allocated
2161     // memory within the lifetime of the current function (allocas, byval
2162     // arguments, globals), then determine the comparison result here.
2163     SmallVector<Value *, 8> LHSUObjs, RHSUObjs;
2164     GetUnderlyingObjects(LHS, LHSUObjs, DL);
2165     GetUnderlyingObjects(RHS, RHSUObjs, DL);
2166
2167     // Is the set of underlying objects all noalias calls?
2168     auto IsNAC = [](ArrayRef<Value *> Objects) {
2169       return all_of(Objects, isNoAliasCall);
2170     };
2171
2172     // Is the set of underlying objects all things which must be disjoint from
2173     // noalias calls. For allocas, we consider only static ones (dynamic
2174     // allocas might be transformed into calls to malloc not simultaneously
2175     // live with the compared-to allocation). For globals, we exclude symbols
2176     // that might be resolve lazily to symbols in another dynamically-loaded
2177     // library (and, thus, could be malloc'ed by the implementation).
2178     auto IsAllocDisjoint = [](ArrayRef<Value *> Objects) {
2179       return all_of(Objects, [](Value *V) {
2180         if (const AllocaInst *AI = dyn_cast<AllocaInst>(V))
2181           return AI->getParent() && AI->getFunction() && AI->isStaticAlloca();
2182         if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
2183           return (GV->hasLocalLinkage() || GV->hasHiddenVisibility() ||
2184                   GV->hasProtectedVisibility() || GV->hasGlobalUnnamedAddr()) &&
2185                  !GV->isThreadLocal();
2186         if (const Argument *A = dyn_cast<Argument>(V))
2187           return A->hasByValAttr();
2188         return false;
2189       });
2190     };
2191
2192     if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) ||
2193         (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs)))
2194         return ConstantInt::get(GetCompareTy(LHS),
2195                                 !CmpInst::isTrueWhenEqual(Pred));
2196
2197     // Fold comparisons for non-escaping pointer even if the allocation call
2198     // cannot be elided. We cannot fold malloc comparison to null. Also, the
2199     // dynamic allocation call could be either of the operands.
2200     Value *MI = nullptr;
2201     if (isAllocLikeFn(LHS, TLI) &&
2202         llvm::isKnownNonZero(RHS, DL, 0, nullptr, CxtI, DT))
2203       MI = LHS;
2204     else if (isAllocLikeFn(RHS, TLI) &&
2205              llvm::isKnownNonZero(LHS, DL, 0, nullptr, CxtI, DT))
2206       MI = RHS;
2207     // FIXME: We should also fold the compare when the pointer escapes, but the
2208     // compare dominates the pointer escape
2209     if (MI && !PointerMayBeCaptured(MI, true, true))
2210       return ConstantInt::get(GetCompareTy(LHS),
2211                               CmpInst::isFalseWhenEqual(Pred));
2212   }
2213
2214   // Otherwise, fail.
2215   return nullptr;
2216 }
2217
2218 /// Fold an icmp when its operands have i1 scalar type.
2219 static Value *simplifyICmpOfBools(CmpInst::Predicate Pred, Value *LHS,
2220                                   Value *RHS, const SimplifyQuery &Q) {
2221   Type *ITy = GetCompareTy(LHS); // The return type.
2222   Type *OpTy = LHS->getType();   // The operand type.
2223   if (!OpTy->isIntOrIntVectorTy(1))
2224     return nullptr;
2225
2226   // A boolean compared to true/false can be simplified in 14 out of the 20
2227   // (10 predicates * 2 constants) possible combinations. Cases not handled here
2228   // require a 'not' of the LHS, so those must be transformed in InstCombine.
2229   if (match(RHS, m_Zero())) {
2230     switch (Pred) {
2231     case CmpInst::ICMP_NE:  // X !=  0 -> X
2232     case CmpInst::ICMP_UGT: // X >u  0 -> X
2233     case CmpInst::ICMP_SLT: // X <s  0 -> X
2234       return LHS;
2235
2236     case CmpInst::ICMP_ULT: // X <u  0 -> false
2237     case CmpInst::ICMP_SGT: // X >s  0 -> false
2238       return getFalse(ITy);
2239
2240     case CmpInst::ICMP_UGE: // X >=u 0 -> true
2241     case CmpInst::ICMP_SLE: // X <=s 0 -> true
2242       return getTrue(ITy);
2243
2244     default: break;
2245     }
2246   } else if (match(RHS, m_One())) {
2247     switch (Pred) {
2248     case CmpInst::ICMP_EQ:  // X ==   1 -> X
2249     case CmpInst::ICMP_UGE: // X >=u  1 -> X
2250     case CmpInst::ICMP_SLE: // X <=s -1 -> X
2251       return LHS;
2252
2253     case CmpInst::ICMP_UGT: // X >u   1 -> false
2254     case CmpInst::ICMP_SLT: // X <s  -1 -> false
2255       return getFalse(ITy);
2256
2257     case CmpInst::ICMP_ULE: // X <=u  1 -> true
2258     case CmpInst::ICMP_SGE: // X >=s -1 -> true
2259       return getTrue(ITy);
2260
2261     default: break;
2262     }
2263   }
2264
2265   switch (Pred) {
2266   default:
2267     break;
2268   case ICmpInst::ICMP_UGE:
2269     if (isImpliedCondition(RHS, LHS, Q.DL).getValueOr(false))
2270       return getTrue(ITy);
2271     break;
2272   case ICmpInst::ICMP_SGE:
2273     /// For signed comparison, the values for an i1 are 0 and -1
2274     /// respectively. This maps into a truth table of:
2275     /// LHS | RHS | LHS >=s RHS   | LHS implies RHS
2276     ///  0  |  0  |  1 (0 >= 0)   |  1
2277     ///  0  |  1  |  1 (0 >= -1)  |  1
2278     ///  1  |  0  |  0 (-1 >= 0)  |  0
2279     ///  1  |  1  |  1 (-1 >= -1) |  1
2280     if (isImpliedCondition(LHS, RHS, Q.DL).getValueOr(false))
2281       return getTrue(ITy);
2282     break;
2283   case ICmpInst::ICMP_ULE:
2284     if (isImpliedCondition(LHS, RHS, Q.DL).getValueOr(false))
2285       return getTrue(ITy);
2286     break;
2287   }
2288
2289   return nullptr;
2290 }
2291
2292 /// Try hard to fold icmp with zero RHS because this is a common case.
2293 static Value *simplifyICmpWithZero(CmpInst::Predicate Pred, Value *LHS,
2294                                    Value *RHS, const SimplifyQuery &Q) {
2295   if (!match(RHS, m_Zero()))
2296     return nullptr;
2297
2298   Type *ITy = GetCompareTy(LHS); // The return type.
2299   switch (Pred) {
2300   default:
2301     llvm_unreachable("Unknown ICmp predicate!");
2302   case ICmpInst::ICMP_ULT:
2303     return getFalse(ITy);
2304   case ICmpInst::ICMP_UGE:
2305     return getTrue(ITy);
2306   case ICmpInst::ICMP_EQ:
2307   case ICmpInst::ICMP_ULE:
2308     if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2309       return getFalse(ITy);
2310     break;
2311   case ICmpInst::ICMP_NE:
2312   case ICmpInst::ICMP_UGT:
2313     if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2314       return getTrue(ITy);
2315     break;
2316   case ICmpInst::ICMP_SLT: {
2317     KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2318     if (LHSKnown.isNegative())
2319       return getTrue(ITy);
2320     if (LHSKnown.isNonNegative())
2321       return getFalse(ITy);
2322     break;
2323   }
2324   case ICmpInst::ICMP_SLE: {
2325     KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2326     if (LHSKnown.isNegative())
2327       return getTrue(ITy);
2328     if (LHSKnown.isNonNegative() &&
2329         isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2330       return getFalse(ITy);
2331     break;
2332   }
2333   case ICmpInst::ICMP_SGE: {
2334     KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2335     if (LHSKnown.isNegative())
2336       return getFalse(ITy);
2337     if (LHSKnown.isNonNegative())
2338       return getTrue(ITy);
2339     break;
2340   }
2341   case ICmpInst::ICMP_SGT: {
2342     KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2343     if (LHSKnown.isNegative())
2344       return getFalse(ITy);
2345     if (LHSKnown.isNonNegative() &&
2346         isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2347       return getTrue(ITy);
2348     break;
2349   }
2350   }
2351
2352   return nullptr;
2353 }
2354
2355 /// Many binary operators with a constant operand have an easy-to-compute
2356 /// range of outputs. This can be used to fold a comparison to always true or
2357 /// always false.
2358 static void setLimitsForBinOp(BinaryOperator &BO, APInt &Lower, APInt &Upper) {
2359   unsigned Width = Lower.getBitWidth();
2360   const APInt *C;
2361   switch (BO.getOpcode()) {
2362   case Instruction::Add:
2363     if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) {
2364       // FIXME: If we have both nuw and nsw, we should reduce the range further.
2365       if (BO.hasNoUnsignedWrap()) {
2366         // 'add nuw x, C' produces [C, UINT_MAX].
2367         Lower = *C;
2368       } else if (BO.hasNoSignedWrap()) {
2369         if (C->isNegative()) {
2370           // 'add nsw x, -C' produces [SINT_MIN, SINT_MAX - C].
2371           Lower = APInt::getSignedMinValue(Width);
2372           Upper = APInt::getSignedMaxValue(Width) + *C + 1;
2373         } else {
2374           // 'add nsw x, +C' produces [SINT_MIN + C, SINT_MAX].
2375           Lower = APInt::getSignedMinValue(Width) + *C;
2376           Upper = APInt::getSignedMaxValue(Width) + 1;
2377         }
2378       }
2379     }
2380     break;
2381
2382   case Instruction::And:
2383     if (match(BO.getOperand(1), m_APInt(C)))
2384       // 'and x, C' produces [0, C].
2385       Upper = *C + 1;
2386     break;
2387
2388   case Instruction::Or:
2389     if (match(BO.getOperand(1), m_APInt(C)))
2390       // 'or x, C' produces [C, UINT_MAX].
2391       Lower = *C;
2392     break;
2393
2394   case Instruction::AShr:
2395     if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) {
2396       // 'ashr x, C' produces [INT_MIN >> C, INT_MAX >> C].
2397       Lower = APInt::getSignedMinValue(Width).ashr(*C);
2398       Upper = APInt::getSignedMaxValue(Width).ashr(*C) + 1;
2399     } else if (match(BO.getOperand(0), m_APInt(C))) {
2400       unsigned ShiftAmount = Width - 1;
2401       if (!C->isNullValue() && BO.isExact())
2402         ShiftAmount = C->countTrailingZeros();
2403       if (C->isNegative()) {
2404         // 'ashr C, x' produces [C, C >> (Width-1)]
2405         Lower = *C;
2406         Upper = C->ashr(ShiftAmount) + 1;
2407       } else {
2408         // 'ashr C, x' produces [C >> (Width-1), C]
2409         Lower = C->ashr(ShiftAmount);
2410         Upper = *C + 1;
2411       }
2412     }
2413     break;
2414
2415   case Instruction::LShr:
2416     if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) {
2417       // 'lshr x, C' produces [0, UINT_MAX >> C].
2418       Upper = APInt::getAllOnesValue(Width).lshr(*C) + 1;
2419     } else if (match(BO.getOperand(0), m_APInt(C))) {
2420       // 'lshr C, x' produces [C >> (Width-1), C].
2421       unsigned ShiftAmount = Width - 1;
2422       if (!C->isNullValue() && BO.isExact())
2423         ShiftAmount = C->countTrailingZeros();
2424       Lower = C->lshr(ShiftAmount);
2425       Upper = *C + 1;
2426     }
2427     break;
2428
2429   case Instruction::Shl:
2430     if (match(BO.getOperand(0), m_APInt(C))) {
2431       if (BO.hasNoUnsignedWrap()) {
2432         // 'shl nuw C, x' produces [C, C << CLZ(C)]
2433         Lower = *C;
2434         Upper = Lower.shl(Lower.countLeadingZeros()) + 1;
2435       } else if (BO.hasNoSignedWrap()) { // TODO: What if both nuw+nsw?
2436         if (C->isNegative()) {
2437           // 'shl nsw C, x' produces [C << CLO(C)-1, C]
2438           unsigned ShiftAmount = C->countLeadingOnes() - 1;
2439           Lower = C->shl(ShiftAmount);
2440           Upper = *C + 1;
2441         } else {
2442           // 'shl nsw C, x' produces [C, C << CLZ(C)-1]
2443           unsigned ShiftAmount = C->countLeadingZeros() - 1;
2444           Lower = *C;
2445           Upper = C->shl(ShiftAmount) + 1;
2446         }
2447       }
2448     }
2449     break;
2450
2451   case Instruction::SDiv:
2452     if (match(BO.getOperand(1), m_APInt(C))) {
2453       APInt IntMin = APInt::getSignedMinValue(Width);
2454       APInt IntMax = APInt::getSignedMaxValue(Width);
2455       if (C->isAllOnesValue()) {
2456         // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX]
2457         //    where C != -1 and C != 0 and C != 1
2458         Lower = IntMin + 1;
2459         Upper = IntMax + 1;
2460       } else if (C->countLeadingZeros() < Width - 1) {
2461         // 'sdiv x, C' produces [INT_MIN / C, INT_MAX / C]
2462         //    where C != -1 and C != 0 and C != 1
2463         Lower = IntMin.sdiv(*C);
2464         Upper = IntMax.sdiv(*C);
2465         if (Lower.sgt(Upper))
2466           std::swap(Lower, Upper);
2467         Upper = Upper + 1;
2468         assert(Upper != Lower && "Upper part of range has wrapped!");
2469       }
2470     } else if (match(BO.getOperand(0), m_APInt(C))) {
2471       if (C->isMinSignedValue()) {
2472         // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2].
2473         Lower = *C;
2474         Upper = Lower.lshr(1) + 1;
2475       } else {
2476         // 'sdiv C, x' produces [-|C|, |C|].
2477         Upper = C->abs() + 1;
2478         Lower = (-Upper) + 1;
2479       }
2480     }
2481     break;
2482
2483   case Instruction::UDiv:
2484     if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) {
2485       // 'udiv x, C' produces [0, UINT_MAX / C].
2486       Upper = APInt::getMaxValue(Width).udiv(*C) + 1;
2487     } else if (match(BO.getOperand(0), m_APInt(C))) {
2488       // 'udiv C, x' produces [0, C].
2489       Upper = *C + 1;
2490     }
2491     break;
2492
2493   case Instruction::SRem:
2494     if (match(BO.getOperand(1), m_APInt(C))) {
2495       // 'srem x, C' produces (-|C|, |C|).
2496       Upper = C->abs();
2497       Lower = (-Upper) + 1;
2498     }
2499     break;
2500
2501   case Instruction::URem:
2502     if (match(BO.getOperand(1), m_APInt(C)))
2503       // 'urem x, C' produces [0, C).
2504       Upper = *C;
2505     break;
2506
2507   default:
2508     break;
2509   }
2510 }
2511
2512 static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS,
2513                                        Value *RHS) {
2514   Type *ITy = GetCompareTy(RHS); // The return type.
2515
2516   Value *X;
2517   // Sign-bit checks can be optimized to true/false after unsigned
2518   // floating-point casts:
2519   // icmp slt (bitcast (uitofp X)),  0 --> false
2520   // icmp sgt (bitcast (uitofp X)), -1 --> true
2521   if (match(LHS, m_BitCast(m_UIToFP(m_Value(X))))) {
2522     if (Pred == ICmpInst::ICMP_SLT && match(RHS, m_Zero()))
2523       return ConstantInt::getFalse(ITy);
2524     if (Pred == ICmpInst::ICMP_SGT && match(RHS, m_AllOnes()))
2525       return ConstantInt::getTrue(ITy);
2526   }
2527
2528   const APInt *C;
2529   if (!match(RHS, m_APInt(C)))
2530     return nullptr;
2531
2532   // Rule out tautological comparisons (eg., ult 0 or uge 0).
2533   ConstantRange RHS_CR = ConstantRange::makeExactICmpRegion(Pred, *C);
2534   if (RHS_CR.isEmptySet())
2535     return ConstantInt::getFalse(ITy);
2536   if (RHS_CR.isFullSet())
2537     return ConstantInt::getTrue(ITy);
2538
2539   // Find the range of possible values for binary operators.
2540   unsigned Width = C->getBitWidth();
2541   APInt Lower = APInt(Width, 0);
2542   APInt Upper = APInt(Width, 0);
2543   if (auto *BO = dyn_cast<BinaryOperator>(LHS))
2544     setLimitsForBinOp(*BO, Lower, Upper);
2545
2546   ConstantRange LHS_CR =
2547       Lower != Upper ? ConstantRange(Lower, Upper) : ConstantRange(Width, true);
2548
2549   if (auto *I = dyn_cast<Instruction>(LHS))
2550     if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
2551       LHS_CR = LHS_CR.intersectWith(getConstantRangeFromMetadata(*Ranges));
2552
2553   if (!LHS_CR.isFullSet()) {
2554     if (RHS_CR.contains(LHS_CR))
2555       return ConstantInt::getTrue(ITy);
2556     if (RHS_CR.inverse().contains(LHS_CR))
2557       return ConstantInt::getFalse(ITy);
2558   }
2559
2560   return nullptr;
2561 }
2562
2563 /// TODO: A large part of this logic is duplicated in InstCombine's
2564 /// foldICmpBinOp(). We should be able to share that and avoid the code
2565 /// duplication.
2566 static Value *simplifyICmpWithBinOp(CmpInst::Predicate Pred, Value *LHS,
2567                                     Value *RHS, const SimplifyQuery &Q,
2568                                     unsigned MaxRecurse) {
2569   Type *ITy = GetCompareTy(LHS); // The return type.
2570
2571   BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS);
2572   BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS);
2573   if (MaxRecurse && (LBO || RBO)) {
2574     // Analyze the case when either LHS or RHS is an add instruction.
2575     Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
2576     // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null).
2577     bool NoLHSWrapProblem = false, NoRHSWrapProblem = false;
2578     if (LBO && LBO->getOpcode() == Instruction::Add) {
2579       A = LBO->getOperand(0);
2580       B = LBO->getOperand(1);
2581       NoLHSWrapProblem =
2582           ICmpInst::isEquality(Pred) ||
2583           (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) ||
2584           (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap());
2585     }
2586     if (RBO && RBO->getOpcode() == Instruction::Add) {
2587       C = RBO->getOperand(0);
2588       D = RBO->getOperand(1);
2589       NoRHSWrapProblem =
2590           ICmpInst::isEquality(Pred) ||
2591           (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) ||
2592           (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap());
2593     }
2594
2595     // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow.
2596     if ((A == RHS || B == RHS) && NoLHSWrapProblem)
2597       if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A,
2598                                       Constant::getNullValue(RHS->getType()), Q,
2599                                       MaxRecurse - 1))
2600         return V;
2601
2602     // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow.
2603     if ((C == LHS || D == LHS) && NoRHSWrapProblem)
2604       if (Value *V =
2605               SimplifyICmpInst(Pred, Constant::getNullValue(LHS->getType()),
2606                                C == LHS ? D : C, Q, MaxRecurse - 1))
2607         return V;
2608
2609     // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow.
2610     if (A && C && (A == C || A == D || B == C || B == D) && NoLHSWrapProblem &&
2611         NoRHSWrapProblem) {
2612       // Determine Y and Z in the form icmp (X+Y), (X+Z).
2613       Value *Y, *Z;
2614       if (A == C) {
2615         // C + B == C + D  ->  B == D
2616         Y = B;
2617         Z = D;
2618       } else if (A == D) {
2619         // D + B == C + D  ->  B == C
2620         Y = B;
2621         Z = C;
2622       } else if (B == C) {
2623         // A + C == C + D  ->  A == D
2624         Y = A;
2625         Z = D;
2626       } else {
2627         assert(B == D);
2628         // A + D == C + D  ->  A == C
2629         Y = A;
2630         Z = C;
2631       }
2632       if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse - 1))
2633         return V;
2634     }
2635   }
2636
2637   {
2638     Value *Y = nullptr;
2639     // icmp pred (or X, Y), X
2640     if (LBO && match(LBO, m_c_Or(m_Value(Y), m_Specific(RHS)))) {
2641       if (Pred == ICmpInst::ICMP_ULT)
2642         return getFalse(ITy);
2643       if (Pred == ICmpInst::ICMP_UGE)
2644         return getTrue(ITy);
2645
2646       if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) {
2647         KnownBits RHSKnown = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2648         KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2649         if (RHSKnown.isNonNegative() && YKnown.isNegative())
2650           return Pred == ICmpInst::ICMP_SLT ? getTrue(ITy) : getFalse(ITy);
2651         if (RHSKnown.isNegative() || YKnown.isNonNegative())
2652           return Pred == ICmpInst::ICMP_SLT ? getFalse(ITy) : getTrue(ITy);
2653       }
2654     }
2655     // icmp pred X, (or X, Y)
2656     if (RBO && match(RBO, m_c_Or(m_Value(Y), m_Specific(LHS)))) {
2657       if (Pred == ICmpInst::ICMP_ULE)
2658         return getTrue(ITy);
2659       if (Pred == ICmpInst::ICMP_UGT)
2660         return getFalse(ITy);
2661
2662       if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE) {
2663         KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2664         KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2665         if (LHSKnown.isNonNegative() && YKnown.isNegative())
2666           return Pred == ICmpInst::ICMP_SGT ? getTrue(ITy) : getFalse(ITy);
2667         if (LHSKnown.isNegative() || YKnown.isNonNegative())
2668           return Pred == ICmpInst::ICMP_SGT ? getFalse(ITy) : getTrue(ITy);
2669       }
2670     }
2671   }
2672
2673   // icmp pred (and X, Y), X
2674   if (LBO && match(LBO, m_c_And(m_Value(), m_Specific(RHS)))) {
2675     if (Pred == ICmpInst::ICMP_UGT)
2676       return getFalse(ITy);
2677     if (Pred == ICmpInst::ICMP_ULE)
2678       return getTrue(ITy);
2679   }
2680   // icmp pred X, (and X, Y)
2681   if (RBO && match(RBO, m_c_And(m_Value(), m_Specific(LHS)))) {
2682     if (Pred == ICmpInst::ICMP_UGE)
2683       return getTrue(ITy);
2684     if (Pred == ICmpInst::ICMP_ULT)
2685       return getFalse(ITy);
2686   }
2687
2688   // 0 - (zext X) pred C
2689   if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) {
2690     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
2691       if (RHSC->getValue().isStrictlyPositive()) {
2692         if (Pred == ICmpInst::ICMP_SLT)
2693           return ConstantInt::getTrue(RHSC->getContext());
2694         if (Pred == ICmpInst::ICMP_SGE)
2695           return ConstantInt::getFalse(RHSC->getContext());
2696         if (Pred == ICmpInst::ICMP_EQ)
2697           return ConstantInt::getFalse(RHSC->getContext());
2698         if (Pred == ICmpInst::ICMP_NE)
2699           return ConstantInt::getTrue(RHSC->getContext());
2700       }
2701       if (RHSC->getValue().isNonNegative()) {
2702         if (Pred == ICmpInst::ICMP_SLE)
2703           return ConstantInt::getTrue(RHSC->getContext());
2704         if (Pred == ICmpInst::ICMP_SGT)
2705           return ConstantInt::getFalse(RHSC->getContext());
2706       }
2707     }
2708   }
2709
2710   // icmp pred (urem X, Y), Y
2711   if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) {
2712     switch (Pred) {
2713     default:
2714       break;
2715     case ICmpInst::ICMP_SGT:
2716     case ICmpInst::ICMP_SGE: {
2717       KnownBits Known = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2718       if (!Known.isNonNegative())
2719         break;
2720       LLVM_FALLTHROUGH;
2721     }
2722     case ICmpInst::ICMP_EQ:
2723     case ICmpInst::ICMP_UGT:
2724     case ICmpInst::ICMP_UGE:
2725       return getFalse(ITy);
2726     case ICmpInst::ICMP_SLT:
2727     case ICmpInst::ICMP_SLE: {
2728       KnownBits Known = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2729       if (!Known.isNonNegative())
2730         break;
2731       LLVM_FALLTHROUGH;
2732     }
2733     case ICmpInst::ICMP_NE:
2734     case ICmpInst::ICMP_ULT:
2735     case ICmpInst::ICMP_ULE:
2736       return getTrue(ITy);
2737     }
2738   }
2739
2740   // icmp pred X, (urem Y, X)
2741   if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) {
2742     switch (Pred) {
2743     default:
2744       break;
2745     case ICmpInst::ICMP_SGT:
2746     case ICmpInst::ICMP_SGE: {
2747       KnownBits Known = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2748       if (!Known.isNonNegative())
2749         break;
2750       LLVM_FALLTHROUGH;
2751     }
2752     case ICmpInst::ICMP_NE:
2753     case ICmpInst::ICMP_UGT:
2754     case ICmpInst::ICMP_UGE:
2755       return getTrue(ITy);
2756     case ICmpInst::ICMP_SLT:
2757     case ICmpInst::ICMP_SLE: {
2758       KnownBits Known = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
2759       if (!Known.isNonNegative())
2760         break;
2761       LLVM_FALLTHROUGH;
2762     }
2763     case ICmpInst::ICMP_EQ:
2764     case ICmpInst::ICMP_ULT:
2765     case ICmpInst::ICMP_ULE:
2766       return getFalse(ITy);
2767     }
2768   }
2769
2770   // x >> y <=u x
2771   // x udiv y <=u x.
2772   if (LBO && (match(LBO, m_LShr(m_Specific(RHS), m_Value())) ||
2773               match(LBO, m_UDiv(m_Specific(RHS), m_Value())))) {
2774     // icmp pred (X op Y), X
2775     if (Pred == ICmpInst::ICMP_UGT)
2776       return getFalse(ITy);
2777     if (Pred == ICmpInst::ICMP_ULE)
2778       return getTrue(ITy);
2779   }
2780
2781   // x >=u x >> y
2782   // x >=u x udiv y.
2783   if (RBO && (match(RBO, m_LShr(m_Specific(LHS), m_Value())) ||
2784               match(RBO, m_UDiv(m_Specific(LHS), m_Value())))) {
2785     // icmp pred X, (X op Y)
2786     if (Pred == ICmpInst::ICMP_ULT)
2787       return getFalse(ITy);
2788     if (Pred == ICmpInst::ICMP_UGE)
2789       return getTrue(ITy);
2790   }
2791
2792   // handle:
2793   //   CI2 << X == CI
2794   //   CI2 << X != CI
2795   //
2796   //   where CI2 is a power of 2 and CI isn't
2797   if (auto *CI = dyn_cast<ConstantInt>(RHS)) {
2798     const APInt *CI2Val, *CIVal = &CI->getValue();
2799     if (LBO && match(LBO, m_Shl(m_APInt(CI2Val), m_Value())) &&
2800         CI2Val->isPowerOf2()) {
2801       if (!CIVal->isPowerOf2()) {
2802         // CI2 << X can equal zero in some circumstances,
2803         // this simplification is unsafe if CI is zero.
2804         //
2805         // We know it is safe if:
2806         // - The shift is nsw, we can't shift out the one bit.
2807         // - The shift is nuw, we can't shift out the one bit.
2808         // - CI2 is one
2809         // - CI isn't zero
2810         if (LBO->hasNoSignedWrap() || LBO->hasNoUnsignedWrap() ||
2811             CI2Val->isOneValue() || !CI->isZero()) {
2812           if (Pred == ICmpInst::ICMP_EQ)
2813             return ConstantInt::getFalse(RHS->getContext());
2814           if (Pred == ICmpInst::ICMP_NE)
2815             return ConstantInt::getTrue(RHS->getContext());
2816         }
2817       }
2818       if (CIVal->isSignMask() && CI2Val->isOneValue()) {
2819         if (Pred == ICmpInst::ICMP_UGT)
2820           return ConstantInt::getFalse(RHS->getContext());
2821         if (Pred == ICmpInst::ICMP_ULE)
2822           return ConstantInt::getTrue(RHS->getContext());
2823       }
2824     }
2825   }
2826
2827   if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() &&
2828       LBO->getOperand(1) == RBO->getOperand(1)) {
2829     switch (LBO->getOpcode()) {
2830     default:
2831       break;
2832     case Instruction::UDiv:
2833     case Instruction::LShr:
2834       if (ICmpInst::isSigned(Pred) || !LBO->isExact() || !RBO->isExact())
2835         break;
2836       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
2837                                       RBO->getOperand(0), Q, MaxRecurse - 1))
2838           return V;
2839       break;
2840     case Instruction::SDiv:
2841       if (!ICmpInst::isEquality(Pred) || !LBO->isExact() || !RBO->isExact())
2842         break;
2843       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
2844                                       RBO->getOperand(0), Q, MaxRecurse - 1))
2845         return V;
2846       break;
2847     case Instruction::AShr:
2848       if (!LBO->isExact() || !RBO->isExact())
2849         break;
2850       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
2851                                       RBO->getOperand(0), Q, MaxRecurse - 1))
2852         return V;
2853       break;
2854     case Instruction::Shl: {
2855       bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap();
2856       bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap();
2857       if (!NUW && !NSW)
2858         break;
2859       if (!NSW && ICmpInst::isSigned(Pred))
2860         break;
2861       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
2862                                       RBO->getOperand(0), Q, MaxRecurse - 1))
2863         return V;
2864       break;
2865     }
2866     }
2867   }
2868   return nullptr;
2869 }
2870
2871 /// Simplify integer comparisons where at least one operand of the compare
2872 /// matches an integer min/max idiom.
2873 static Value *simplifyICmpWithMinMax(CmpInst::Predicate Pred, Value *LHS,
2874                                      Value *RHS, const SimplifyQuery &Q,
2875                                      unsigned MaxRecurse) {
2876   Type *ITy = GetCompareTy(LHS); // The return type.
2877   Value *A, *B;
2878   CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE;
2879   CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B".
2880
2881   // Signed variants on "max(a,b)>=a -> true".
2882   if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
2883     if (A != RHS)
2884       std::swap(A, B);       // smax(A, B) pred A.
2885     EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
2886     // We analyze this as smax(A, B) pred A.
2887     P = Pred;
2888   } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) &&
2889              (A == LHS || B == LHS)) {
2890     if (A != LHS)
2891       std::swap(A, B);       // A pred smax(A, B).
2892     EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
2893     // We analyze this as smax(A, B) swapped-pred A.
2894     P = CmpInst::getSwappedPredicate(Pred);
2895   } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
2896              (A == RHS || B == RHS)) {
2897     if (A != RHS)
2898       std::swap(A, B);       // smin(A, B) pred A.
2899     EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
2900     // We analyze this as smax(-A, -B) swapped-pred -A.
2901     // Note that we do not need to actually form -A or -B thanks to EqP.
2902     P = CmpInst::getSwappedPredicate(Pred);
2903   } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) &&
2904              (A == LHS || B == LHS)) {
2905     if (A != LHS)
2906       std::swap(A, B);       // A pred smin(A, B).
2907     EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
2908     // We analyze this as smax(-A, -B) pred -A.
2909     // Note that we do not need to actually form -A or -B thanks to EqP.
2910     P = Pred;
2911   }
2912   if (P != CmpInst::BAD_ICMP_PREDICATE) {
2913     // Cases correspond to "max(A, B) p A".
2914     switch (P) {
2915     default:
2916       break;
2917     case CmpInst::ICMP_EQ:
2918     case CmpInst::ICMP_SLE:
2919       // Equivalent to "A EqP B".  This may be the same as the condition tested
2920       // in the max/min; if so, we can just return that.
2921       if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
2922         return V;
2923       if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
2924         return V;
2925       // Otherwise, see if "A EqP B" simplifies.
2926       if (MaxRecurse)
2927         if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse - 1))
2928           return V;
2929       break;
2930     case CmpInst::ICMP_NE:
2931     case CmpInst::ICMP_SGT: {
2932       CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
2933       // Equivalent to "A InvEqP B".  This may be the same as the condition
2934       // tested in the max/min; if so, we can just return that.
2935       if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
2936         return V;
2937       if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
2938         return V;
2939       // Otherwise, see if "A InvEqP B" simplifies.
2940       if (MaxRecurse)
2941         if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse - 1))
2942           return V;
2943       break;
2944     }
2945     case CmpInst::ICMP_SGE:
2946       // Always true.
2947       return getTrue(ITy);
2948     case CmpInst::ICMP_SLT:
2949       // Always false.
2950       return getFalse(ITy);
2951     }
2952   }
2953
2954   // Unsigned variants on "max(a,b)>=a -> true".
2955   P = CmpInst::BAD_ICMP_PREDICATE;
2956   if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
2957     if (A != RHS)
2958       std::swap(A, B);       // umax(A, B) pred A.
2959     EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
2960     // We analyze this as umax(A, B) pred A.
2961     P = Pred;
2962   } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) &&
2963              (A == LHS || B == LHS)) {
2964     if (A != LHS)
2965       std::swap(A, B);       // A pred umax(A, B).
2966     EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
2967     // We analyze this as umax(A, B) swapped-pred A.
2968     P = CmpInst::getSwappedPredicate(Pred);
2969   } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
2970              (A == RHS || B == RHS)) {
2971     if (A != RHS)
2972       std::swap(A, B);       // umin(A, B) pred A.
2973     EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
2974     // We analyze this as umax(-A, -B) swapped-pred -A.
2975     // Note that we do not need to actually form -A or -B thanks to EqP.
2976     P = CmpInst::getSwappedPredicate(Pred);
2977   } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) &&
2978              (A == LHS || B == LHS)) {
2979     if (A != LHS)
2980       std::swap(A, B);       // A pred umin(A, B).
2981     EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
2982     // We analyze this as umax(-A, -B) pred -A.
2983     // Note that we do not need to actually form -A or -B thanks to EqP.
2984     P = Pred;
2985   }
2986   if (P != CmpInst::BAD_ICMP_PREDICATE) {
2987     // Cases correspond to "max(A, B) p A".
2988     switch (P) {
2989     default:
2990       break;
2991     case CmpInst::ICMP_EQ:
2992     case CmpInst::ICMP_ULE:
2993       // Equivalent to "A EqP B".  This may be the same as the condition tested
2994       // in the max/min; if so, we can just return that.
2995       if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
2996         return V;
2997       if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
2998         return V;
2999       // Otherwise, see if "A EqP B" simplifies.
3000       if (MaxRecurse)
3001         if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse - 1))
3002           return V;
3003       break;
3004     case CmpInst::ICMP_NE:
3005     case CmpInst::ICMP_UGT: {
3006       CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
3007       // Equivalent to "A InvEqP B".  This may be the same as the condition
3008       // tested in the max/min; if so, we can just return that.
3009       if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
3010         return V;
3011       if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
3012         return V;
3013       // Otherwise, see if "A InvEqP B" simplifies.
3014       if (MaxRecurse)
3015         if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse - 1))
3016           return V;
3017       break;
3018     }
3019     case CmpInst::ICMP_UGE:
3020       // Always true.
3021       return getTrue(ITy);
3022     case CmpInst::ICMP_ULT:
3023       // Always false.
3024       return getFalse(ITy);
3025     }
3026   }
3027
3028   // Variants on "max(x,y) >= min(x,z)".
3029   Value *C, *D;
3030   if (match(LHS, m_SMax(m_Value(A), m_Value(B))) &&
3031       match(RHS, m_SMin(m_Value(C), m_Value(D))) &&
3032       (A == C || A == D || B == C || B == D)) {
3033     // max(x, ?) pred min(x, ?).
3034     if (Pred == CmpInst::ICMP_SGE)
3035       // Always true.
3036       return getTrue(ITy);
3037     if (Pred == CmpInst::ICMP_SLT)
3038       // Always false.
3039       return getFalse(ITy);
3040   } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
3041              match(RHS, m_SMax(m_Value(C), m_Value(D))) &&
3042              (A == C || A == D || B == C || B == D)) {
3043     // min(x, ?) pred max(x, ?).
3044     if (Pred == CmpInst::ICMP_SLE)
3045       // Always true.
3046       return getTrue(ITy);
3047     if (Pred == CmpInst::ICMP_SGT)
3048       // Always false.
3049       return getFalse(ITy);
3050   } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) &&
3051              match(RHS, m_UMin(m_Value(C), m_Value(D))) &&
3052              (A == C || A == D || B == C || B == D)) {
3053     // max(x, ?) pred min(x, ?).
3054     if (Pred == CmpInst::ICMP_UGE)
3055       // Always true.
3056       return getTrue(ITy);
3057     if (Pred == CmpInst::ICMP_ULT)
3058       // Always false.
3059       return getFalse(ITy);
3060   } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
3061              match(RHS, m_UMax(m_Value(C), m_Value(D))) &&
3062              (A == C || A == D || B == C || B == D)) {
3063     // min(x, ?) pred max(x, ?).
3064     if (Pred == CmpInst::ICMP_ULE)
3065       // Always true.
3066       return getTrue(ITy);
3067     if (Pred == CmpInst::ICMP_UGT)
3068       // Always false.
3069       return getFalse(ITy);
3070   }
3071
3072   return nullptr;
3073 }
3074
3075 /// Given operands for an ICmpInst, see if we can fold the result.
3076 /// If not, this returns null.
3077 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3078                                const SimplifyQuery &Q, unsigned MaxRecurse) {
3079   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
3080   assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
3081
3082   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
3083     if (Constant *CRHS = dyn_cast<Constant>(RHS))
3084       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
3085
3086     // If we have a constant, make sure it is on the RHS.
3087     std::swap(LHS, RHS);
3088     Pred = CmpInst::getSwappedPredicate(Pred);
3089   }
3090
3091   Type *ITy = GetCompareTy(LHS); // The return type.
3092
3093   // icmp X, X -> true/false
3094   // icmp X, undef -> true/false because undef could be X.
3095   if (LHS == RHS || isa<UndefValue>(RHS))
3096     return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
3097
3098   if (Value *V = simplifyICmpOfBools(Pred, LHS, RHS, Q))
3099     return V;
3100
3101   if (Value *V = simplifyICmpWithZero(Pred, LHS, RHS, Q))
3102     return V;
3103
3104   if (Value *V = simplifyICmpWithConstant(Pred, LHS, RHS))
3105     return V;
3106
3107   // If both operands have range metadata, use the metadata
3108   // to simplify the comparison.
3109   if (isa<Instruction>(RHS) && isa<Instruction>(LHS)) {
3110     auto RHS_Instr = cast<Instruction>(RHS);
3111     auto LHS_Instr = cast<Instruction>(LHS);
3112
3113     if (RHS_Instr->getMetadata(LLVMContext::MD_range) &&
3114         LHS_Instr->getMetadata(LLVMContext::MD_range)) {
3115       auto RHS_CR = getConstantRangeFromMetadata(
3116           *RHS_Instr->getMetadata(LLVMContext::MD_range));
3117       auto LHS_CR = getConstantRangeFromMetadata(
3118           *LHS_Instr->getMetadata(LLVMContext::MD_range));
3119
3120       auto Satisfied_CR = ConstantRange::makeSatisfyingICmpRegion(Pred, RHS_CR);
3121       if (Satisfied_CR.contains(LHS_CR))
3122         return ConstantInt::getTrue(RHS->getContext());
3123
3124       auto InversedSatisfied_CR = ConstantRange::makeSatisfyingICmpRegion(
3125                 CmpInst::getInversePredicate(Pred), RHS_CR);
3126       if (InversedSatisfied_CR.contains(LHS_CR))
3127         return ConstantInt::getFalse(RHS->getContext());
3128     }
3129   }
3130
3131   // Compare of cast, for example (zext X) != 0 -> X != 0
3132   if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) {
3133     Instruction *LI = cast<CastInst>(LHS);
3134     Value *SrcOp = LI->getOperand(0);
3135     Type *SrcTy = SrcOp->getType();
3136     Type *DstTy = LI->getType();
3137
3138     // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input
3139     // if the integer type is the same size as the pointer type.
3140     if (MaxRecurse && isa<PtrToIntInst>(LI) &&
3141         Q.DL.getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) {
3142       if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
3143         // Transfer the cast to the constant.
3144         if (Value *V = SimplifyICmpInst(Pred, SrcOp,
3145                                         ConstantExpr::getIntToPtr(RHSC, SrcTy),
3146                                         Q, MaxRecurse-1))
3147           return V;
3148       } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) {
3149         if (RI->getOperand(0)->getType() == SrcTy)
3150           // Compare without the cast.
3151           if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
3152                                           Q, MaxRecurse-1))
3153             return V;
3154       }
3155     }
3156
3157     if (isa<ZExtInst>(LHS)) {
3158       // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the
3159       // same type.
3160       if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
3161         if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
3162           // Compare X and Y.  Note that signed predicates become unsigned.
3163           if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
3164                                           SrcOp, RI->getOperand(0), Q,
3165                                           MaxRecurse-1))
3166             return V;
3167       }
3168       // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended
3169       // too.  If not, then try to deduce the result of the comparison.
3170       else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
3171         // Compute the constant that would happen if we truncated to SrcTy then
3172         // reextended to DstTy.
3173         Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
3174         Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy);
3175
3176         // If the re-extended constant didn't change then this is effectively
3177         // also a case of comparing two zero-extended values.
3178         if (RExt == CI && MaxRecurse)
3179           if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
3180                                         SrcOp, Trunc, Q, MaxRecurse-1))
3181             return V;
3182
3183         // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit
3184         // there.  Use this to work out the result of the comparison.
3185         if (RExt != CI) {
3186           switch (Pred) {
3187           default: llvm_unreachable("Unknown ICmp predicate!");
3188           // LHS <u RHS.
3189           case ICmpInst::ICMP_EQ:
3190           case ICmpInst::ICMP_UGT:
3191           case ICmpInst::ICMP_UGE:
3192             return ConstantInt::getFalse(CI->getContext());
3193
3194           case ICmpInst::ICMP_NE:
3195           case ICmpInst::ICMP_ULT:
3196           case ICmpInst::ICMP_ULE:
3197             return ConstantInt::getTrue(CI->getContext());
3198
3199           // LHS is non-negative.  If RHS is negative then LHS >s LHS.  If RHS
3200           // is non-negative then LHS <s RHS.
3201           case ICmpInst::ICMP_SGT:
3202           case ICmpInst::ICMP_SGE:
3203             return CI->getValue().isNegative() ?
3204               ConstantInt::getTrue(CI->getContext()) :
3205               ConstantInt::getFalse(CI->getContext());
3206
3207           case ICmpInst::ICMP_SLT:
3208           case ICmpInst::ICMP_SLE:
3209             return CI->getValue().isNegative() ?
3210               ConstantInt::getFalse(CI->getContext()) :
3211               ConstantInt::getTrue(CI->getContext());
3212           }
3213         }
3214       }
3215     }
3216
3217     if (isa<SExtInst>(LHS)) {
3218       // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the
3219       // same type.
3220       if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
3221         if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
3222           // Compare X and Y.  Note that the predicate does not change.
3223           if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
3224                                           Q, MaxRecurse-1))
3225             return V;
3226       }
3227       // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended
3228       // too.  If not, then try to deduce the result of the comparison.
3229       else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
3230         // Compute the constant that would happen if we truncated to SrcTy then
3231         // reextended to DstTy.
3232         Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
3233         Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy);
3234
3235         // If the re-extended constant didn't change then this is effectively
3236         // also a case of comparing two sign-extended values.
3237         if (RExt == CI && MaxRecurse)
3238           if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse-1))
3239             return V;
3240
3241         // Otherwise the upper bits of LHS are all equal, while RHS has varying
3242         // bits there.  Use this to work out the result of the comparison.
3243         if (RExt != CI) {
3244           switch (Pred) {
3245           default: llvm_unreachable("Unknown ICmp predicate!");
3246           case ICmpInst::ICMP_EQ:
3247             return ConstantInt::getFalse(CI->getContext());
3248           case ICmpInst::ICMP_NE:
3249             return ConstantInt::getTrue(CI->getContext());
3250
3251           // If RHS is non-negative then LHS <s RHS.  If RHS is negative then
3252           // LHS >s RHS.
3253           case ICmpInst::ICMP_SGT:
3254           case ICmpInst::ICMP_SGE:
3255             return CI->getValue().isNegative() ?
3256               ConstantInt::getTrue(CI->getContext()) :
3257               ConstantInt::getFalse(CI->getContext());
3258           case ICmpInst::ICMP_SLT:
3259           case ICmpInst::ICMP_SLE:
3260             return CI->getValue().isNegative() ?
3261               ConstantInt::getFalse(CI->getContext()) :
3262               ConstantInt::getTrue(CI->getContext());
3263
3264           // If LHS is non-negative then LHS <u RHS.  If LHS is negative then
3265           // LHS >u RHS.
3266           case ICmpInst::ICMP_UGT:
3267           case ICmpInst::ICMP_UGE:
3268             // Comparison is true iff the LHS <s 0.
3269             if (MaxRecurse)
3270               if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp,
3271                                               Constant::getNullValue(SrcTy),
3272                                               Q, MaxRecurse-1))
3273                 return V;
3274             break;
3275           case ICmpInst::ICMP_ULT:
3276           case ICmpInst::ICMP_ULE:
3277             // Comparison is true iff the LHS >=s 0.
3278             if (MaxRecurse)
3279               if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp,
3280                                               Constant::getNullValue(SrcTy),
3281                                               Q, MaxRecurse-1))
3282                 return V;
3283             break;
3284           }
3285         }
3286       }
3287     }
3288   }
3289
3290   // icmp eq|ne X, Y -> false|true if X != Y
3291   if (ICmpInst::isEquality(Pred) &&
3292       isKnownNonEqual(LHS, RHS, Q.DL, Q.AC, Q.CxtI, Q.DT)) {
3293     return Pred == ICmpInst::ICMP_NE ? getTrue(ITy) : getFalse(ITy);
3294   }
3295
3296   if (Value *V = simplifyICmpWithBinOp(Pred, LHS, RHS, Q, MaxRecurse))
3297     return V;
3298
3299   if (Value *V = simplifyICmpWithMinMax(Pred, LHS, RHS, Q, MaxRecurse))
3300     return V;
3301
3302   // Simplify comparisons of related pointers using a powerful, recursive
3303   // GEP-walk when we have target data available..
3304   if (LHS->getType()->isPointerTy())
3305     if (auto *C = computePointerICmp(Q.DL, Q.TLI, Q.DT, Pred, Q.AC, Q.CxtI, LHS,
3306                                      RHS))
3307       return C;
3308   if (auto *CLHS = dyn_cast<PtrToIntOperator>(LHS))
3309     if (auto *CRHS = dyn_cast<PtrToIntOperator>(RHS))
3310       if (Q.DL.getTypeSizeInBits(CLHS->getPointerOperandType()) ==
3311               Q.DL.getTypeSizeInBits(CLHS->getType()) &&
3312           Q.DL.getTypeSizeInBits(CRHS->getPointerOperandType()) ==
3313               Q.DL.getTypeSizeInBits(CRHS->getType()))
3314         if (auto *C = computePointerICmp(Q.DL, Q.TLI, Q.DT, Pred, Q.AC, Q.CxtI,
3315                                          CLHS->getPointerOperand(),
3316                                          CRHS->getPointerOperand()))
3317           return C;
3318
3319   if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) {
3320     if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) {
3321       if (GLHS->getPointerOperand() == GRHS->getPointerOperand() &&
3322           GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() &&
3323           (ICmpInst::isEquality(Pred) ||
3324            (GLHS->isInBounds() && GRHS->isInBounds() &&
3325             Pred == ICmpInst::getSignedPredicate(Pred)))) {
3326         // The bases are equal and the indices are constant.  Build a constant
3327         // expression GEP with the same indices and a null base pointer to see
3328         // what constant folding can make out of it.
3329         Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType());
3330         SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end());
3331         Constant *NewLHS = ConstantExpr::getGetElementPtr(
3332             GLHS->getSourceElementType(), Null, IndicesLHS);
3333
3334         SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end());
3335         Constant *NewRHS = ConstantExpr::getGetElementPtr(
3336             GLHS->getSourceElementType(), Null, IndicesRHS);
3337         return ConstantExpr::getICmp(Pred, NewLHS, NewRHS);
3338       }
3339     }
3340   }
3341
3342   // If the comparison is with the result of a select instruction, check whether
3343   // comparing with either branch of the select always yields the same value.
3344   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
3345     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
3346       return V;
3347
3348   // If the comparison is with the result of a phi instruction, check whether
3349   // doing the compare with each incoming phi value yields a common result.
3350   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
3351     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
3352       return V;
3353
3354   return nullptr;
3355 }
3356
3357 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3358                               const SimplifyQuery &Q) {
3359   return ::SimplifyICmpInst(Predicate, LHS, RHS, Q, RecursionLimit);
3360 }
3361
3362 /// Given operands for an FCmpInst, see if we can fold the result.
3363 /// If not, this returns null.
3364 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3365                                FastMathFlags FMF, const SimplifyQuery &Q,
3366                                unsigned MaxRecurse) {
3367   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
3368   assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
3369
3370   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
3371     if (Constant *CRHS = dyn_cast<Constant>(RHS))
3372       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
3373
3374     // If we have a constant, make sure it is on the RHS.
3375     std::swap(LHS, RHS);
3376     Pred = CmpInst::getSwappedPredicate(Pred);
3377   }
3378
3379   // Fold trivial predicates.
3380   Type *RetTy = GetCompareTy(LHS);
3381   if (Pred == FCmpInst::FCMP_FALSE)
3382     return getFalse(RetTy);
3383   if (Pred == FCmpInst::FCMP_TRUE)
3384     return getTrue(RetTy);
3385
3386   // UNO/ORD predicates can be trivially folded if NaNs are ignored.
3387   if (FMF.noNaNs()) {
3388     if (Pred == FCmpInst::FCMP_UNO)
3389       return getFalse(RetTy);
3390     if (Pred == FCmpInst::FCMP_ORD)
3391       return getTrue(RetTy);
3392   }
3393
3394   // NaN is unordered; NaN is not ordered.
3395   assert((FCmpInst::isOrdered(Pred) || FCmpInst::isUnordered(Pred)) &&
3396          "Comparison must be either ordered or unordered");
3397   if (match(RHS, m_NaN()))
3398     return ConstantInt::get(RetTy, CmpInst::isUnordered(Pred));
3399
3400   // fcmp pred x, undef  and  fcmp pred undef, x
3401   // fold to true if unordered, false if ordered
3402   if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS)) {
3403     // Choosing NaN for the undef will always make unordered comparison succeed
3404     // and ordered comparison fail.
3405     return ConstantInt::get(RetTy, CmpInst::isUnordered(Pred));
3406   }
3407
3408   // fcmp x,x -> true/false.  Not all compares are foldable.
3409   if (LHS == RHS) {
3410     if (CmpInst::isTrueWhenEqual(Pred))
3411       return getTrue(RetTy);
3412     if (CmpInst::isFalseWhenEqual(Pred))
3413       return getFalse(RetTy);
3414   }
3415
3416   // Handle fcmp with constant RHS.
3417   const APFloat *C;
3418   if (match(RHS, m_APFloat(C))) {
3419     // Check whether the constant is an infinity.
3420     if (C->isInfinity()) {
3421       if (C->isNegative()) {
3422         switch (Pred) {
3423         case FCmpInst::FCMP_OLT:
3424           // No value is ordered and less than negative infinity.
3425           return getFalse(RetTy);
3426         case FCmpInst::FCMP_UGE:
3427           // All values are unordered with or at least negative infinity.
3428           return getTrue(RetTy);
3429         default:
3430           break;
3431         }
3432       } else {
3433         switch (Pred) {
3434         case FCmpInst::FCMP_OGT:
3435           // No value is ordered and greater than infinity.
3436           return getFalse(RetTy);
3437         case FCmpInst::FCMP_ULE:
3438           // All values are unordered with and at most infinity.
3439           return getTrue(RetTy);
3440         default:
3441           break;
3442         }
3443       }
3444     }
3445     if (C->isZero()) {
3446       switch (Pred) {
3447       case FCmpInst::FCMP_UGE:
3448         if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
3449           return getTrue(RetTy);
3450         break;
3451       case FCmpInst::FCMP_OLT:
3452         // X < 0
3453         if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
3454           return getFalse(RetTy);
3455         break;
3456       default:
3457         break;
3458       }
3459     } else if (C->isNegative()) {
3460       assert(!C->isNaN() && "Unexpected NaN constant!");
3461       // TODO: We can catch more cases by using a range check rather than
3462       //       relying on CannotBeOrderedLessThanZero.
3463       switch (Pred) {
3464       case FCmpInst::FCMP_UGE:
3465       case FCmpInst::FCMP_UGT:
3466       case FCmpInst::FCMP_UNE:
3467         // (X >= 0) implies (X > C) when (C < 0)
3468         if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
3469           return getTrue(RetTy);
3470         break;
3471       case FCmpInst::FCMP_OEQ:
3472       case FCmpInst::FCMP_OLE:
3473       case FCmpInst::FCMP_OLT:
3474         // (X >= 0) implies !(X < C) when (C < 0)
3475         if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
3476           return getFalse(RetTy);
3477         break;
3478       default:
3479         break;
3480       }
3481     }
3482   }
3483
3484   // If the comparison is with the result of a select instruction, check whether
3485   // comparing with either branch of the select always yields the same value.
3486   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
3487     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
3488       return V;
3489
3490   // If the comparison is with the result of a phi instruction, check whether
3491   // doing the compare with each incoming phi value yields a common result.
3492   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
3493     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
3494       return V;
3495
3496   return nullptr;
3497 }
3498
3499 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3500                               FastMathFlags FMF, const SimplifyQuery &Q) {
3501   return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF, Q, RecursionLimit);
3502 }
3503
3504 /// See if V simplifies when its operand Op is replaced with RepOp.
3505 static const Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp,
3506                                            const SimplifyQuery &Q,
3507                                            unsigned MaxRecurse) {
3508   // Trivial replacement.
3509   if (V == Op)
3510     return RepOp;
3511
3512   // We cannot replace a constant, and shouldn't even try.
3513   if (isa<Constant>(Op))
3514     return nullptr;
3515
3516   auto *I = dyn_cast<Instruction>(V);
3517   if (!I)
3518     return nullptr;
3519
3520   // If this is a binary operator, try to simplify it with the replaced op.
3521   if (auto *B = dyn_cast<BinaryOperator>(I)) {
3522     // Consider:
3523     //   %cmp = icmp eq i32 %x, 2147483647
3524     //   %add = add nsw i32 %x, 1
3525     //   %sel = select i1 %cmp, i32 -2147483648, i32 %add
3526     //
3527     // We can't replace %sel with %add unless we strip away the flags.
3528     if (isa<OverflowingBinaryOperator>(B))
3529       if (B->hasNoSignedWrap() || B->hasNoUnsignedWrap())
3530         return nullptr;
3531     if (isa<PossiblyExactOperator>(B))
3532       if (B->isExact())
3533         return nullptr;
3534
3535     if (MaxRecurse) {
3536       if (B->getOperand(0) == Op)
3537         return SimplifyBinOp(B->getOpcode(), RepOp, B->getOperand(1), Q,
3538                              MaxRecurse - 1);
3539       if (B->getOperand(1) == Op)
3540         return SimplifyBinOp(B->getOpcode(), B->getOperand(0), RepOp, Q,
3541                              MaxRecurse - 1);
3542     }
3543   }
3544
3545   // Same for CmpInsts.
3546   if (CmpInst *C = dyn_cast<CmpInst>(I)) {
3547     if (MaxRecurse) {
3548       if (C->getOperand(0) == Op)
3549         return SimplifyCmpInst(C->getPredicate(), RepOp, C->getOperand(1), Q,
3550                                MaxRecurse - 1);
3551       if (C->getOperand(1) == Op)
3552         return SimplifyCmpInst(C->getPredicate(), C->getOperand(0), RepOp, Q,
3553                                MaxRecurse - 1);
3554     }
3555   }
3556
3557   // Same for GEPs.
3558   if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
3559     if (MaxRecurse) {
3560       SmallVector<Value *, 8> NewOps(GEP->getNumOperands());
3561       transform(GEP->operands(), NewOps.begin(),
3562                 [&](Value *V) { return V == Op ? RepOp : V; });
3563       return SimplifyGEPInst(GEP->getSourceElementType(), NewOps, Q,
3564                              MaxRecurse - 1);
3565     }
3566   }
3567
3568   // TODO: We could hand off more cases to instsimplify here.
3569
3570   // If all operands are constant after substituting Op for RepOp then we can
3571   // constant fold the instruction.
3572   if (Constant *CRepOp = dyn_cast<Constant>(RepOp)) {
3573     // Build a list of all constant operands.
3574     SmallVector<Constant *, 8> ConstOps;
3575     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
3576       if (I->getOperand(i) == Op)
3577         ConstOps.push_back(CRepOp);
3578       else if (Constant *COp = dyn_cast<Constant>(I->getOperand(i)))
3579         ConstOps.push_back(COp);
3580       else
3581         break;
3582     }
3583
3584     // All operands were constants, fold it.
3585     if (ConstOps.size() == I->getNumOperands()) {
3586       if (CmpInst *C = dyn_cast<CmpInst>(I))
3587         return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0],
3588                                                ConstOps[1], Q.DL, Q.TLI);
3589
3590       if (LoadInst *LI = dyn_cast<LoadInst>(I))
3591         if (!LI->isVolatile())
3592           return ConstantFoldLoadFromConstPtr(ConstOps[0], LI->getType(), Q.DL);
3593
3594       return ConstantFoldInstOperands(I, ConstOps, Q.DL, Q.TLI);
3595     }
3596   }
3597
3598   return nullptr;
3599 }
3600
3601 /// Try to simplify a select instruction when its condition operand is an
3602 /// integer comparison where one operand of the compare is a constant.
3603 static Value *simplifySelectBitTest(Value *TrueVal, Value *FalseVal, Value *X,
3604                                     const APInt *Y, bool TrueWhenUnset) {
3605   const APInt *C;
3606
3607   // (X & Y) == 0 ? X & ~Y : X  --> X
3608   // (X & Y) != 0 ? X & ~Y : X  --> X & ~Y
3609   if (FalseVal == X && match(TrueVal, m_And(m_Specific(X), m_APInt(C))) &&
3610       *Y == ~*C)
3611     return TrueWhenUnset ? FalseVal : TrueVal;
3612
3613   // (X & Y) == 0 ? X : X & ~Y  --> X & ~Y
3614   // (X & Y) != 0 ? X : X & ~Y  --> X
3615   if (TrueVal == X && match(FalseVal, m_And(m_Specific(X), m_APInt(C))) &&
3616       *Y == ~*C)
3617     return TrueWhenUnset ? FalseVal : TrueVal;
3618
3619   if (Y->isPowerOf2()) {
3620     // (X & Y) == 0 ? X | Y : X  --> X | Y
3621     // (X & Y) != 0 ? X | Y : X  --> X
3622     if (FalseVal == X && match(TrueVal, m_Or(m_Specific(X), m_APInt(C))) &&
3623         *Y == *C)
3624       return TrueWhenUnset ? TrueVal : FalseVal;
3625
3626     // (X & Y) == 0 ? X : X | Y  --> X
3627     // (X & Y) != 0 ? X : X | Y  --> X | Y
3628     if (TrueVal == X && match(FalseVal, m_Or(m_Specific(X), m_APInt(C))) &&
3629         *Y == *C)
3630       return TrueWhenUnset ? TrueVal : FalseVal;
3631   }
3632
3633   return nullptr;
3634 }
3635
3636 /// An alternative way to test if a bit is set or not uses sgt/slt instead of
3637 /// eq/ne.
3638 static Value *simplifySelectWithFakeICmpEq(Value *CmpLHS, Value *CmpRHS,
3639                                            ICmpInst::Predicate Pred,
3640                                            Value *TrueVal, Value *FalseVal) {
3641   Value *X;
3642   APInt Mask;
3643   if (!decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, X, Mask))
3644     return nullptr;
3645
3646   return simplifySelectBitTest(TrueVal, FalseVal, X, &Mask,
3647                                Pred == ICmpInst::ICMP_EQ);
3648 }
3649
3650 /// Try to simplify a select instruction when its condition operand is an
3651 /// integer comparison.
3652 static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,
3653                                          Value *FalseVal, const SimplifyQuery &Q,
3654                                          unsigned MaxRecurse) {
3655   ICmpInst::Predicate Pred;
3656   Value *CmpLHS, *CmpRHS;
3657   if (!match(CondVal, m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS))))
3658     return nullptr;
3659
3660   if (ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero())) {
3661     Value *X;
3662     const APInt *Y;
3663     if (match(CmpLHS, m_And(m_Value(X), m_APInt(Y))))
3664       if (Value *V = simplifySelectBitTest(TrueVal, FalseVal, X, Y,
3665                                            Pred == ICmpInst::ICMP_EQ))
3666         return V;
3667   }
3668
3669   // Check for other compares that behave like bit test.
3670   if (Value *V = simplifySelectWithFakeICmpEq(CmpLHS, CmpRHS, Pred,
3671                                               TrueVal, FalseVal))
3672     return V;
3673
3674   // If we have an equality comparison, then we know the value in one of the
3675   // arms of the select. See if substituting this value into the arm and
3676   // simplifying the result yields the same value as the other arm.
3677   if (Pred == ICmpInst::ICMP_EQ) {
3678     if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
3679             TrueVal ||
3680         SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
3681             TrueVal)
3682       return FalseVal;
3683     if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
3684             FalseVal ||
3685         SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
3686             FalseVal)
3687       return FalseVal;
3688   } else if (Pred == ICmpInst::ICMP_NE) {
3689     if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
3690             FalseVal ||
3691         SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
3692             FalseVal)
3693       return TrueVal;
3694     if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
3695             TrueVal ||
3696         SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
3697             TrueVal)
3698       return TrueVal;
3699   }
3700
3701   return nullptr;
3702 }
3703
3704 /// Given operands for a SelectInst, see if we can fold the result.
3705 /// If not, this returns null.
3706 static Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
3707                                  const SimplifyQuery &Q, unsigned MaxRecurse) {
3708   if (auto *CondC = dyn_cast<Constant>(Cond)) {
3709     if (auto *TrueC = dyn_cast<Constant>(TrueVal))
3710       if (auto *FalseC = dyn_cast<Constant>(FalseVal))
3711         return ConstantFoldSelectInstruction(CondC, TrueC, FalseC);
3712
3713     // select undef, X, Y -> X or Y
3714     if (isa<UndefValue>(CondC))
3715       return isa<Constant>(FalseVal) ? FalseVal : TrueVal;
3716
3717     // TODO: Vector constants with undef elements don't simplify.
3718
3719     // select true, X, Y  -> X
3720     if (CondC->isAllOnesValue())
3721       return TrueVal;
3722     // select false, X, Y -> Y
3723     if (CondC->isNullValue())
3724       return FalseVal;
3725   }
3726
3727   // select ?, X, X -> X
3728   if (TrueVal == FalseVal)
3729     return TrueVal;
3730
3731   if (isa<UndefValue>(TrueVal))   // select ?, undef, X -> X
3732     return FalseVal;
3733   if (isa<UndefValue>(FalseVal))   // select ?, X, undef -> X
3734     return TrueVal;
3735
3736   if (Value *V =
3737           simplifySelectWithICmpCond(Cond, TrueVal, FalseVal, Q, MaxRecurse))
3738     return V;
3739
3740   return nullptr;
3741 }
3742
3743 Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
3744                                 const SimplifyQuery &Q) {
3745   return ::SimplifySelectInst(Cond, TrueVal, FalseVal, Q, RecursionLimit);
3746 }
3747
3748 /// Given operands for an GetElementPtrInst, see if we can fold the result.
3749 /// If not, this returns null.
3750 static Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
3751                               const SimplifyQuery &Q, unsigned) {
3752   // The type of the GEP pointer operand.
3753   unsigned AS =
3754       cast<PointerType>(Ops[0]->getType()->getScalarType())->getAddressSpace();
3755
3756   // getelementptr P -> P.
3757   if (Ops.size() == 1)
3758     return Ops[0];
3759
3760   // Compute the (pointer) type returned by the GEP instruction.
3761   Type *LastType = GetElementPtrInst::getIndexedType(SrcTy, Ops.slice(1));
3762   Type *GEPTy = PointerType::get(LastType, AS);
3763   if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType()))
3764     GEPTy = VectorType::get(GEPTy, VT->getNumElements());
3765   else if (VectorType *VT = dyn_cast<VectorType>(Ops[1]->getType()))
3766     GEPTy = VectorType::get(GEPTy, VT->getNumElements());
3767
3768   if (isa<UndefValue>(Ops[0]))
3769     return UndefValue::get(GEPTy);
3770
3771   if (Ops.size() == 2) {
3772     // getelementptr P, 0 -> P.
3773     if (match(Ops[1], m_Zero()) && Ops[0]->getType() == GEPTy)
3774       return Ops[0];
3775
3776     Type *Ty = SrcTy;
3777     if (Ty->isSized()) {
3778       Value *P;
3779       uint64_t C;
3780       uint64_t TyAllocSize = Q.DL.getTypeAllocSize(Ty);
3781       // getelementptr P, N -> P if P points to a type of zero size.
3782       if (TyAllocSize == 0 && Ops[0]->getType() == GEPTy)
3783         return Ops[0];
3784
3785       // The following transforms are only safe if the ptrtoint cast
3786       // doesn't truncate the pointers.
3787       if (Ops[1]->getType()->getScalarSizeInBits() ==
3788           Q.DL.getIndexSizeInBits(AS)) {
3789         auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * {
3790           if (match(P, m_Zero()))
3791             return Constant::getNullValue(GEPTy);
3792           Value *Temp;
3793           if (match(P, m_PtrToInt(m_Value(Temp))))
3794             if (Temp->getType() == GEPTy)
3795               return Temp;
3796           return nullptr;
3797         };
3798
3799         // getelementptr V, (sub P, V) -> P if P points to a type of size 1.
3800         if (TyAllocSize == 1 &&
3801             match(Ops[1], m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0])))))
3802           if (Value *R = PtrToIntOrZero(P))
3803             return R;
3804
3805         // getelementptr V, (ashr (sub P, V), C) -> Q
3806         // if P points to a type of size 1 << C.
3807         if (match(Ops[1],
3808                   m_AShr(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
3809                          m_ConstantInt(C))) &&
3810             TyAllocSize == 1ULL << C)
3811           if (Value *R = PtrToIntOrZero(P))
3812             return R;
3813
3814         // getelementptr V, (sdiv (sub P, V), C) -> Q
3815         // if P points to a type of size C.
3816         if (match(Ops[1],
3817                   m_SDiv(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
3818                          m_SpecificInt(TyAllocSize))))
3819           if (Value *R = PtrToIntOrZero(P))
3820             return R;
3821       }
3822     }
3823   }
3824
3825   if (Q.DL.getTypeAllocSize(LastType) == 1 &&
3826       all_of(Ops.slice(1).drop_back(1),
3827              [](Value *Idx) { return match(Idx, m_Zero()); })) {
3828     unsigned IdxWidth =
3829         Q.DL.getIndexSizeInBits(Ops[0]->getType()->getPointerAddressSpace());
3830     if (Q.DL.getTypeSizeInBits(Ops.back()->getType()) == IdxWidth) {
3831       APInt BasePtrOffset(IdxWidth, 0);
3832       Value *StrippedBasePtr =
3833           Ops[0]->stripAndAccumulateInBoundsConstantOffsets(Q.DL,
3834                                                             BasePtrOffset);
3835
3836       // gep (gep V, C), (sub 0, V) -> C
3837       if (match(Ops.back(),
3838                 m_Sub(m_Zero(), m_PtrToInt(m_Specific(StrippedBasePtr))))) {
3839         auto *CI = ConstantInt::get(GEPTy->getContext(), BasePtrOffset);
3840         return ConstantExpr::getIntToPtr(CI, GEPTy);
3841       }
3842       // gep (gep V, C), (xor V, -1) -> C-1
3843       if (match(Ops.back(),
3844                 m_Xor(m_PtrToInt(m_Specific(StrippedBasePtr)), m_AllOnes()))) {
3845         auto *CI = ConstantInt::get(GEPTy->getContext(), BasePtrOffset - 1);
3846         return ConstantExpr::getIntToPtr(CI, GEPTy);
3847       }
3848     }
3849   }
3850
3851   // Check to see if this is constant foldable.
3852   if (!all_of(Ops, [](Value *V) { return isa<Constant>(V); }))
3853     return nullptr;
3854
3855   auto *CE = ConstantExpr::getGetElementPtr(SrcTy, cast<Constant>(Ops[0]),
3856                                             Ops.slice(1));
3857   if (auto *CEFolded = ConstantFoldConstant(CE, Q.DL))
3858     return CEFolded;
3859   return CE;
3860 }
3861
3862 Value *llvm::SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
3863                              const SimplifyQuery &Q) {
3864   return ::SimplifyGEPInst(SrcTy, Ops, Q, RecursionLimit);
3865 }
3866
3867 /// Given operands for an InsertValueInst, see if we can fold the result.
3868 /// If not, this returns null.
3869 static Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
3870                                       ArrayRef<unsigned> Idxs, const SimplifyQuery &Q,
3871                                       unsigned) {
3872   if (Constant *CAgg = dyn_cast<Constant>(Agg))
3873     if (Constant *CVal = dyn_cast<Constant>(Val))
3874       return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs);
3875
3876   // insertvalue x, undef, n -> x
3877   if (match(Val, m_Undef()))
3878     return Agg;
3879
3880   // insertvalue x, (extractvalue y, n), n
3881   if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val))
3882     if (EV->getAggregateOperand()->getType() == Agg->getType() &&
3883         EV->getIndices() == Idxs) {
3884       // insertvalue undef, (extractvalue y, n), n -> y
3885       if (match(Agg, m_Undef()))
3886         return EV->getAggregateOperand();
3887
3888       // insertvalue y, (extractvalue y, n), n -> y
3889       if (Agg == EV->getAggregateOperand())
3890         return Agg;
3891     }
3892
3893   return nullptr;
3894 }
3895
3896 Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val,
3897                                      ArrayRef<unsigned> Idxs,
3898                                      const SimplifyQuery &Q) {
3899   return ::SimplifyInsertValueInst(Agg, Val, Idxs, Q, RecursionLimit);
3900 }
3901
3902 Value *llvm::SimplifyInsertElementInst(Value *Vec, Value *Val, Value *Idx,
3903                                        const SimplifyQuery &Q) {
3904   // Try to constant fold.
3905   auto *VecC = dyn_cast<Constant>(Vec);
3906   auto *ValC = dyn_cast<Constant>(Val);
3907   auto *IdxC = dyn_cast<Constant>(Idx);
3908   if (VecC && ValC && IdxC)
3909     return ConstantFoldInsertElementInstruction(VecC, ValC, IdxC);
3910
3911   // Fold into undef if index is out of bounds.
3912   if (auto *CI = dyn_cast<ConstantInt>(Idx)) {
3913     uint64_t NumElements = cast<VectorType>(Vec->getType())->getNumElements();
3914     if (CI->uge(NumElements))
3915       return UndefValue::get(Vec->getType());
3916   }
3917
3918   // If index is undef, it might be out of bounds (see above case)
3919   if (isa<UndefValue>(Idx))
3920     return UndefValue::get(Vec->getType());
3921
3922   return nullptr;
3923 }
3924
3925 /// Given operands for an ExtractValueInst, see if we can fold the result.
3926 /// If not, this returns null.
3927 static Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
3928                                        const SimplifyQuery &, unsigned) {
3929   if (auto *CAgg = dyn_cast<Constant>(Agg))
3930     return ConstantFoldExtractValueInstruction(CAgg, Idxs);
3931
3932   // extractvalue x, (insertvalue y, elt, n), n -> elt
3933   unsigned NumIdxs = Idxs.size();
3934   for (auto *IVI = dyn_cast<InsertValueInst>(Agg); IVI != nullptr;
3935        IVI = dyn_cast<InsertValueInst>(IVI->getAggregateOperand())) {
3936     ArrayRef<unsigned> InsertValueIdxs = IVI->getIndices();
3937     unsigned NumInsertValueIdxs = InsertValueIdxs.size();
3938     unsigned NumCommonIdxs = std::min(NumInsertValueIdxs, NumIdxs);
3939     if (InsertValueIdxs.slice(0, NumCommonIdxs) ==
3940         Idxs.slice(0, NumCommonIdxs)) {
3941       if (NumIdxs == NumInsertValueIdxs)
3942         return IVI->getInsertedValueOperand();
3943       break;
3944     }
3945   }
3946
3947   return nullptr;
3948 }
3949
3950 Value *llvm::SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
3951                                       const SimplifyQuery &Q) {
3952   return ::SimplifyExtractValueInst(Agg, Idxs, Q, RecursionLimit);
3953 }
3954
3955 /// Given operands for an ExtractElementInst, see if we can fold the result.
3956 /// If not, this returns null.
3957 static Value *SimplifyExtractElementInst(Value *Vec, Value *Idx, const SimplifyQuery &,
3958                                          unsigned) {
3959   if (auto *CVec = dyn_cast<Constant>(Vec)) {
3960     if (auto *CIdx = dyn_cast<Constant>(Idx))
3961       return ConstantFoldExtractElementInstruction(CVec, CIdx);
3962
3963     // The index is not relevant if our vector is a splat.
3964     if (auto *Splat = CVec->getSplatValue())
3965       return Splat;
3966
3967     if (isa<UndefValue>(Vec))
3968       return UndefValue::get(Vec->getType()->getVectorElementType());
3969   }
3970
3971   // If extracting a specified index from the vector, see if we can recursively
3972   // find a previously computed scalar that was inserted into the vector.
3973   if (auto *IdxC = dyn_cast<ConstantInt>(Idx)) {
3974     if (IdxC->getValue().uge(Vec->getType()->getVectorNumElements()))
3975       // definitely out of bounds, thus undefined result
3976       return UndefValue::get(Vec->getType()->getVectorElementType());
3977     if (Value *Elt = findScalarElement(Vec, IdxC->getZExtValue()))
3978       return Elt;
3979   }
3980
3981   // An undef extract index can be arbitrarily chosen to be an out-of-range
3982   // index value, which would result in the instruction being undef.
3983   if (isa<UndefValue>(Idx))
3984     return UndefValue::get(Vec->getType()->getVectorElementType());
3985
3986   return nullptr;
3987 }
3988
3989 Value *llvm::SimplifyExtractElementInst(Value *Vec, Value *Idx,
3990                                         const SimplifyQuery &Q) {
3991   return ::SimplifyExtractElementInst(Vec, Idx, Q, RecursionLimit);
3992 }
3993
3994 /// See if we can fold the given phi. If not, returns null.
3995 static Value *SimplifyPHINode(PHINode *PN, const SimplifyQuery &Q) {
3996   // If all of the PHI's incoming values are the same then replace the PHI node
3997   // with the common value.
3998   Value *CommonValue = nullptr;
3999   bool HasUndefInput = false;
4000   for (Value *Incoming : PN->incoming_values()) {
4001     // If the incoming value is the phi node itself, it can safely be skipped.
4002     if (Incoming == PN) continue;
4003     if (isa<UndefValue>(Incoming)) {
4004       // Remember that we saw an undef value, but otherwise ignore them.
4005       HasUndefInput = true;
4006       continue;
4007     }
4008     if (CommonValue && Incoming != CommonValue)
4009       return nullptr;  // Not the same, bail out.
4010     CommonValue = Incoming;
4011   }
4012
4013   // If CommonValue is null then all of the incoming values were either undef or
4014   // equal to the phi node itself.
4015   if (!CommonValue)
4016     return UndefValue::get(PN->getType());
4017
4018   // If we have a PHI node like phi(X, undef, X), where X is defined by some
4019   // instruction, we cannot return X as the result of the PHI node unless it
4020   // dominates the PHI block.
4021   if (HasUndefInput)
4022     return valueDominatesPHI(CommonValue, PN, Q.DT) ? CommonValue : nullptr;
4023
4024   return CommonValue;
4025 }
4026
4027 static Value *SimplifyCastInst(unsigned CastOpc, Value *Op,
4028                                Type *Ty, const SimplifyQuery &Q, unsigned MaxRecurse) {
4029   if (auto *C = dyn_cast<Constant>(Op))
4030     return ConstantFoldCastOperand(CastOpc, C, Ty, Q.DL);
4031
4032   if (auto *CI = dyn_cast<CastInst>(Op)) {
4033     auto *Src = CI->getOperand(0);
4034     Type *SrcTy = Src->getType();
4035     Type *MidTy = CI->getType();
4036     Type *DstTy = Ty;
4037     if (Src->getType() == Ty) {
4038       auto FirstOp = static_cast<Instruction::CastOps>(CI->getOpcode());
4039       auto SecondOp = static_cast<Instruction::CastOps>(CastOpc);
4040       Type *SrcIntPtrTy =
4041           SrcTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(SrcTy) : nullptr;
4042       Type *MidIntPtrTy =
4043           MidTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(MidTy) : nullptr;
4044       Type *DstIntPtrTy =
4045           DstTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(DstTy) : nullptr;
4046       if (CastInst::isEliminableCastPair(FirstOp, SecondOp, SrcTy, MidTy, DstTy,
4047                                          SrcIntPtrTy, MidIntPtrTy,
4048                                          DstIntPtrTy) == Instruction::BitCast)
4049         return Src;
4050     }
4051   }
4052
4053   // bitcast x -> x
4054   if (CastOpc == Instruction::BitCast)
4055     if (Op->getType() == Ty)
4056       return Op;
4057
4058   return nullptr;
4059 }
4060
4061 Value *llvm::SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
4062                               const SimplifyQuery &Q) {
4063   return ::SimplifyCastInst(CastOpc, Op, Ty, Q, RecursionLimit);
4064 }
4065
4066 /// For the given destination element of a shuffle, peek through shuffles to
4067 /// match a root vector source operand that contains that element in the same
4068 /// vector lane (ie, the same mask index), so we can eliminate the shuffle(s).
4069 static Value *foldIdentityShuffles(int DestElt, Value *Op0, Value *Op1,
4070                                    int MaskVal, Value *RootVec,
4071                                    unsigned MaxRecurse) {
4072   if (!MaxRecurse--)
4073     return nullptr;
4074
4075   // Bail out if any mask value is undefined. That kind of shuffle may be
4076   // simplified further based on demanded bits or other folds.
4077   if (MaskVal == -1)
4078     return nullptr;
4079
4080   // The mask value chooses which source operand we need to look at next.
4081   int InVecNumElts = Op0->getType()->getVectorNumElements();
4082   int RootElt = MaskVal;
4083   Value *SourceOp = Op0;
4084   if (MaskVal >= InVecNumElts) {
4085     RootElt = MaskVal - InVecNumElts;
4086     SourceOp = Op1;
4087   }
4088
4089   // If the source operand is a shuffle itself, look through it to find the
4090   // matching root vector.
4091   if (auto *SourceShuf = dyn_cast<ShuffleVectorInst>(SourceOp)) {
4092     return foldIdentityShuffles(
4093         DestElt, SourceShuf->getOperand(0), SourceShuf->getOperand(1),
4094         SourceShuf->getMaskValue(RootElt), RootVec, MaxRecurse);
4095   }
4096
4097   // TODO: Look through bitcasts? What if the bitcast changes the vector element
4098   // size?
4099
4100   // The source operand is not a shuffle. Initialize the root vector value for
4101   // this shuffle if that has not been done yet.
4102   if (!RootVec)
4103     RootVec = SourceOp;
4104
4105   // Give up as soon as a source operand does not match the existing root value.
4106   if (RootVec != SourceOp)
4107     return nullptr;
4108
4109   // The element must be coming from the same lane in the source vector
4110   // (although it may have crossed lanes in intermediate shuffles).
4111   if (RootElt != DestElt)
4112     return nullptr;
4113
4114   return RootVec;
4115 }
4116
4117 static Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
4118                                         Type *RetTy, const SimplifyQuery &Q,
4119                                         unsigned MaxRecurse) {
4120   if (isa<UndefValue>(Mask))
4121     return UndefValue::get(RetTy);
4122
4123   Type *InVecTy = Op0->getType();
4124   unsigned MaskNumElts = Mask->getType()->getVectorNumElements();
4125   unsigned InVecNumElts = InVecTy->getVectorNumElements();
4126
4127   SmallVector<int, 32> Indices;
4128   ShuffleVectorInst::getShuffleMask(Mask, Indices);
4129   assert(MaskNumElts == Indices.size() &&
4130          "Size of Indices not same as number of mask elements?");
4131
4132   // Canonicalization: If mask does not select elements from an input vector,
4133   // replace that input vector with undef.
4134   bool MaskSelects0 = false, MaskSelects1 = false;
4135   for (unsigned i = 0; i != MaskNumElts; ++i) {
4136     if (Indices[i] == -1)
4137       continue;
4138     if ((unsigned)Indices[i] < InVecNumElts)
4139       MaskSelects0 = true;
4140     else
4141       MaskSelects1 = true;
4142   }
4143   if (!MaskSelects0)
4144     Op0 = UndefValue::get(InVecTy);
4145   if (!MaskSelects1)
4146     Op1 = UndefValue::get(InVecTy);
4147
4148   auto *Op0Const = dyn_cast<Constant>(Op0);
4149   auto *Op1Const = dyn_cast<Constant>(Op1);
4150
4151   // If all operands are constant, constant fold the shuffle.
4152   if (Op0Const && Op1Const)
4153     return ConstantFoldShuffleVectorInstruction(Op0Const, Op1Const, Mask);
4154
4155   // Canonicalization: if only one input vector is constant, it shall be the
4156   // second one.
4157   if (Op0Const && !Op1Const) {
4158     std::swap(Op0, Op1);
4159     ShuffleVectorInst::commuteShuffleMask(Indices, InVecNumElts);
4160   }
4161
4162   // A shuffle of a splat is always the splat itself. Legal if the shuffle's
4163   // value type is same as the input vectors' type.
4164   if (auto *OpShuf = dyn_cast<ShuffleVectorInst>(Op0))
4165     if (isa<UndefValue>(Op1) && RetTy == InVecTy &&
4166         OpShuf->getMask()->getSplatValue())
4167       return Op0;
4168
4169   // Don't fold a shuffle with undef mask elements. This may get folded in a
4170   // better way using demanded bits or other analysis.
4171   // TODO: Should we allow this?
4172   if (find(Indices, -1) != Indices.end())
4173     return nullptr;
4174
4175   // Check if every element of this shuffle can be mapped back to the
4176   // corresponding element of a single root vector. If so, we don't need this
4177   // shuffle. This handles simple identity shuffles as well as chains of
4178   // shuffles that may widen/narrow and/or move elements across lanes and back.
4179   Value *RootVec = nullptr;
4180   for (unsigned i = 0; i != MaskNumElts; ++i) {
4181     // Note that recursion is limited for each vector element, so if any element
4182     // exceeds the limit, this will fail to simplify.
4183     RootVec =
4184         foldIdentityShuffles(i, Op0, Op1, Indices[i], RootVec, MaxRecurse);
4185
4186     // We can't replace a widening/narrowing shuffle with one of its operands.
4187     if (!RootVec || RootVec->getType() != RetTy)
4188       return nullptr;
4189   }
4190   return RootVec;
4191 }
4192
4193 /// Given operands for a ShuffleVectorInst, fold the result or return null.
4194 Value *llvm::SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
4195                                        Type *RetTy, const SimplifyQuery &Q) {
4196   return ::SimplifyShuffleVectorInst(Op0, Op1, Mask, RetTy, Q, RecursionLimit);
4197 }
4198
4199 static Constant *propagateNaN(Constant *In) {
4200   // If the input is a vector with undef elements, just return a default NaN.
4201   if (!In->isNaN())
4202     return ConstantFP::getNaN(In->getType());
4203
4204   // Propagate the existing NaN constant when possible.
4205   // TODO: Should we quiet a signaling NaN?
4206   return In;
4207 }
4208
4209 static Constant *simplifyFPBinop(Value *Op0, Value *Op1) {
4210   if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1))
4211     return ConstantFP::getNaN(Op0->getType());
4212
4213   if (match(Op0, m_NaN()))
4214     return propagateNaN(cast<Constant>(Op0));
4215   if (match(Op1, m_NaN()))
4216     return propagateNaN(cast<Constant>(Op1));
4217
4218   return nullptr;
4219 }
4220
4221 /// Given operands for an FAdd, see if we can fold the result.  If not, this
4222 /// returns null.
4223 static Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
4224                                const SimplifyQuery &Q, unsigned MaxRecurse) {
4225   if (Constant *C = foldOrCommuteConstant(Instruction::FAdd, Op0, Op1, Q))
4226     return C;
4227
4228   if (Constant *C = simplifyFPBinop(Op0, Op1))
4229     return C;
4230
4231   // fadd X, -0 ==> X
4232   if (match(Op1, m_NegZeroFP()))
4233     return Op0;
4234
4235   // fadd X, 0 ==> X, when we know X is not -0
4236   if (match(Op1, m_PosZeroFP()) &&
4237       (FMF.noSignedZeros() || CannotBeNegativeZero(Op0, Q.TLI)))
4238     return Op0;
4239
4240   // With nnan: (+/-0.0 - X) + X --> 0.0 (and commuted variant)
4241   // We don't have to explicitly exclude infinities (ninf): INF + -INF == NaN.
4242   // Negative zeros are allowed because we always end up with positive zero:
4243   // X = -0.0: (-0.0 - (-0.0)) + (-0.0) == ( 0.0) + (-0.0) == 0.0
4244   // X = -0.0: ( 0.0 - (-0.0)) + (-0.0) == ( 0.0) + (-0.0) == 0.0
4245   // X =  0.0: (-0.0 - ( 0.0)) + ( 0.0) == (-0.0) + ( 0.0) == 0.0
4246   // X =  0.0: ( 0.0 - ( 0.0)) + ( 0.0) == ( 0.0) + ( 0.0) == 0.0
4247   if (FMF.noNaNs() && (match(Op0, m_FSub(m_AnyZeroFP(), m_Specific(Op1))) ||
4248                        match(Op1, m_FSub(m_AnyZeroFP(), m_Specific(Op0)))))
4249     return ConstantFP::getNullValue(Op0->getType());
4250
4251   return nullptr;
4252 }
4253
4254 /// Given operands for an FSub, see if we can fold the result.  If not, this
4255 /// returns null.
4256 static Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
4257                                const SimplifyQuery &Q, unsigned MaxRecurse) {
4258   if (Constant *C = foldOrCommuteConstant(Instruction::FSub, Op0, Op1, Q))
4259     return C;
4260
4261   if (Constant *C = simplifyFPBinop(Op0, Op1))
4262     return C;
4263
4264   // fsub X, +0 ==> X
4265   if (match(Op1, m_PosZeroFP()))
4266     return Op0;
4267
4268   // fsub X, -0 ==> X, when we know X is not -0
4269   if (match(Op1, m_NegZeroFP()) &&
4270       (FMF.noSignedZeros() || CannotBeNegativeZero(Op0, Q.TLI)))
4271     return Op0;
4272
4273   // fsub -0.0, (fsub -0.0, X) ==> X
4274   Value *X;
4275   if (match(Op0, m_NegZeroFP()) &&
4276       match(Op1, m_FSub(m_NegZeroFP(), m_Value(X))))
4277     return X;
4278
4279   // fsub 0.0, (fsub 0.0, X) ==> X if signed zeros are ignored.
4280   if (FMF.noSignedZeros() && match(Op0, m_AnyZeroFP()) &&
4281       match(Op1, m_FSub(m_AnyZeroFP(), m_Value(X))))
4282     return X;
4283
4284   // fsub nnan x, x ==> 0.0
4285   if (FMF.noNaNs() && Op0 == Op1)
4286     return Constant::getNullValue(Op0->getType());
4287
4288   return nullptr;
4289 }
4290
4291 /// Given the operands for an FMul, see if we can fold the result
4292 static Value *SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
4293                                const SimplifyQuery &Q, unsigned MaxRecurse) {
4294   if (Constant *C = foldOrCommuteConstant(Instruction::FMul, Op0, Op1, Q))
4295     return C;
4296
4297   if (Constant *C = simplifyFPBinop(Op0, Op1))
4298     return C;
4299
4300   // fmul X, 1.0 ==> X
4301   if (match(Op1, m_FPOne()))
4302     return Op0;
4303
4304   // fmul nnan nsz X, 0 ==> 0
4305   if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op1, m_AnyZeroFP()))
4306     return ConstantFP::getNullValue(Op0->getType());
4307
4308   // sqrt(X) * sqrt(X) --> X, if we can:
4309   // 1. Remove the intermediate rounding (reassociate).
4310   // 2. Ignore non-zero negative numbers because sqrt would produce NAN.
4311   // 3. Ignore -0.0 because sqrt(-0.0) == -0.0, but -0.0 * -0.0 == 0.0.
4312   Value *X;
4313   if (Op0 == Op1 && match(Op0, m_Intrinsic<Intrinsic::sqrt>(m_Value(X))) &&
4314       FMF.allowReassoc() && FMF.noNaNs() && FMF.noSignedZeros())
4315     return X;
4316
4317   return nullptr;
4318 }
4319
4320 Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
4321                               const SimplifyQuery &Q) {
4322   return ::SimplifyFAddInst(Op0, Op1, FMF, Q, RecursionLimit);
4323 }
4324
4325
4326 Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
4327                               const SimplifyQuery &Q) {
4328   return ::SimplifyFSubInst(Op0, Op1, FMF, Q, RecursionLimit);
4329 }
4330
4331 Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
4332                               const SimplifyQuery &Q) {
4333   return ::SimplifyFMulInst(Op0, Op1, FMF, Q, RecursionLimit);
4334 }
4335
4336 static Value *SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF,
4337                                const SimplifyQuery &Q, unsigned) {
4338   if (Constant *C = foldOrCommuteConstant(Instruction::FDiv, Op0, Op1, Q))
4339     return C;
4340
4341   if (Constant *C = simplifyFPBinop(Op0, Op1))
4342     return C;
4343
4344   // X / 1.0 -> X
4345   if (match(Op1, m_FPOne()))
4346     return Op0;
4347
4348   // 0 / X -> 0
4349   // Requires that NaNs are off (X could be zero) and signed zeroes are
4350   // ignored (X could be positive or negative, so the output sign is unknown).
4351   if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZeroFP()))
4352     return ConstantFP::getNullValue(Op0->getType());
4353
4354   if (FMF.noNaNs()) {
4355     // X / X -> 1.0 is legal when NaNs are ignored.
4356     // We can ignore infinities because INF/INF is NaN.
4357     if (Op0 == Op1)
4358       return ConstantFP::get(Op0->getType(), 1.0);
4359
4360     // (X * Y) / Y --> X if we can reassociate to the above form.
4361     Value *X;
4362     if (FMF.allowReassoc() && match(Op0, m_c_FMul(m_Value(X), m_Specific(Op1))))
4363       return X;
4364
4365     // -X /  X -> -1.0 and
4366     //  X / -X -> -1.0 are legal when NaNs are ignored.
4367     // We can ignore signed zeros because +-0.0/+-0.0 is NaN and ignored.
4368     if ((BinaryOperator::isFNeg(Op0, /*IgnoreZeroSign=*/true) &&
4369          BinaryOperator::getFNegArgument(Op0) == Op1) ||
4370         (BinaryOperator::isFNeg(Op1, /*IgnoreZeroSign=*/true) &&
4371          BinaryOperator::getFNegArgument(Op1) == Op0))
4372       return ConstantFP::get(Op0->getType(), -1.0);
4373   }
4374
4375   return nullptr;
4376 }
4377
4378 Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF,
4379                               const SimplifyQuery &Q) {
4380   return ::SimplifyFDivInst(Op0, Op1, FMF, Q, RecursionLimit);
4381 }
4382
4383 static Value *SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF,
4384                                const SimplifyQuery &Q, unsigned) {
4385   if (Constant *C = foldOrCommuteConstant(Instruction::FRem, Op0, Op1, Q))
4386     return C;
4387
4388   if (Constant *C = simplifyFPBinop(Op0, Op1))
4389     return C;
4390
4391   // Unlike fdiv, the result of frem always matches the sign of the dividend.
4392   // The constant match may include undef elements in a vector, so return a full
4393   // zero constant as the result.
4394   if (FMF.noNaNs()) {
4395     // +0 % X -> 0
4396     if (match(Op0, m_PosZeroFP()))
4397       return ConstantFP::getNullValue(Op0->getType());
4398     // -0 % X -> -0
4399     if (match(Op0, m_NegZeroFP()))
4400       return ConstantFP::getNegativeZero(Op0->getType());
4401   }
4402
4403   return nullptr;
4404 }
4405
4406 Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF,
4407                               const SimplifyQuery &Q) {
4408   return ::SimplifyFRemInst(Op0, Op1, FMF, Q, RecursionLimit);
4409 }
4410
4411 //=== Helper functions for higher up the class hierarchy.
4412
4413 /// Given operands for a BinaryOperator, see if we can fold the result.
4414 /// If not, this returns null.
4415 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4416                             const SimplifyQuery &Q, unsigned MaxRecurse) {
4417   switch (Opcode) {
4418   case Instruction::Add:
4419     return SimplifyAddInst(LHS, RHS, false, false, Q, MaxRecurse);
4420   case Instruction::Sub:
4421     return SimplifySubInst(LHS, RHS, false, false, Q, MaxRecurse);
4422   case Instruction::Mul:
4423     return SimplifyMulInst(LHS, RHS, Q, MaxRecurse);
4424   case Instruction::SDiv:
4425     return SimplifySDivInst(LHS, RHS, Q, MaxRecurse);
4426   case Instruction::UDiv:
4427     return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse);
4428   case Instruction::SRem:
4429     return SimplifySRemInst(LHS, RHS, Q, MaxRecurse);
4430   case Instruction::URem:
4431     return SimplifyURemInst(LHS, RHS, Q, MaxRecurse);
4432   case Instruction::Shl:
4433     return SimplifyShlInst(LHS, RHS, false, false, Q, MaxRecurse);
4434   case Instruction::LShr:
4435     return SimplifyLShrInst(LHS, RHS, false, Q, MaxRecurse);
4436   case Instruction::AShr:
4437     return SimplifyAShrInst(LHS, RHS, false, Q, MaxRecurse);
4438   case Instruction::And:
4439     return SimplifyAndInst(LHS, RHS, Q, MaxRecurse);
4440   case Instruction::Or:
4441     return SimplifyOrInst(LHS, RHS, Q, MaxRecurse);
4442   case Instruction::Xor:
4443     return SimplifyXorInst(LHS, RHS, Q, MaxRecurse);
4444   case Instruction::FAdd:
4445     return SimplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4446   case Instruction::FSub:
4447     return SimplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4448   case Instruction::FMul:
4449     return SimplifyFMulInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4450   case Instruction::FDiv:
4451     return SimplifyFDivInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4452   case Instruction::FRem:
4453     return SimplifyFRemInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4454   default:
4455     llvm_unreachable("Unexpected opcode");
4456   }
4457 }
4458
4459 /// Given operands for a BinaryOperator, see if we can fold the result.
4460 /// If not, this returns null.
4461 /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the
4462 /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp.
4463 static Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4464                               const FastMathFlags &FMF, const SimplifyQuery &Q,
4465                               unsigned MaxRecurse) {
4466   switch (Opcode) {
4467   case Instruction::FAdd:
4468     return SimplifyFAddInst(LHS, RHS, FMF, Q, MaxRecurse);
4469   case Instruction::FSub:
4470     return SimplifyFSubInst(LHS, RHS, FMF, Q, MaxRecurse);
4471   case Instruction::FMul:
4472     return SimplifyFMulInst(LHS, RHS, FMF, Q, MaxRecurse);
4473   case Instruction::FDiv:
4474     return SimplifyFDivInst(LHS, RHS, FMF, Q, MaxRecurse);
4475   default:
4476     return SimplifyBinOp(Opcode, LHS, RHS, Q, MaxRecurse);
4477   }
4478 }
4479
4480 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4481                            const SimplifyQuery &Q) {
4482   return ::SimplifyBinOp(Opcode, LHS, RHS, Q, RecursionLimit);
4483 }
4484
4485 Value *llvm::SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4486                              FastMathFlags FMF, const SimplifyQuery &Q) {
4487   return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, Q, RecursionLimit);
4488 }
4489
4490 /// Given operands for a CmpInst, see if we can fold the result.
4491 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
4492                               const SimplifyQuery &Q, unsigned MaxRecurse) {
4493   if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
4494     return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse);
4495   return SimplifyFCmpInst(Predicate, LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4496 }
4497
4498 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
4499                              const SimplifyQuery &Q) {
4500   return ::SimplifyCmpInst(Predicate, LHS, RHS, Q, RecursionLimit);
4501 }
4502
4503 static bool IsIdempotent(Intrinsic::ID ID) {
4504   switch (ID) {
4505   default: return false;
4506
4507   // Unary idempotent: f(f(x)) = f(x)
4508   case Intrinsic::fabs:
4509   case Intrinsic::floor:
4510   case Intrinsic::ceil:
4511   case Intrinsic::trunc:
4512   case Intrinsic::rint:
4513   case Intrinsic::nearbyint:
4514   case Intrinsic::round:
4515   case Intrinsic::canonicalize:
4516     return true;
4517   }
4518 }
4519
4520 static Value *SimplifyRelativeLoad(Constant *Ptr, Constant *Offset,
4521                                    const DataLayout &DL) {
4522   GlobalValue *PtrSym;
4523   APInt PtrOffset;
4524   if (!IsConstantOffsetFromGlobal(Ptr, PtrSym, PtrOffset, DL))
4525     return nullptr;
4526
4527   Type *Int8PtrTy = Type::getInt8PtrTy(Ptr->getContext());
4528   Type *Int32Ty = Type::getInt32Ty(Ptr->getContext());
4529   Type *Int32PtrTy = Int32Ty->getPointerTo();
4530   Type *Int64Ty = Type::getInt64Ty(Ptr->getContext());
4531
4532   auto *OffsetConstInt = dyn_cast<ConstantInt>(Offset);
4533   if (!OffsetConstInt || OffsetConstInt->getType()->getBitWidth() > 64)
4534     return nullptr;
4535
4536   uint64_t OffsetInt = OffsetConstInt->getSExtValue();
4537   if (OffsetInt % 4 != 0)
4538     return nullptr;
4539
4540   Constant *C = ConstantExpr::getGetElementPtr(
4541       Int32Ty, ConstantExpr::getBitCast(Ptr, Int32PtrTy),
4542       ConstantInt::get(Int64Ty, OffsetInt / 4));
4543   Constant *Loaded = ConstantFoldLoadFromConstPtr(C, Int32Ty, DL);
4544   if (!Loaded)
4545     return nullptr;
4546
4547   auto *LoadedCE = dyn_cast<ConstantExpr>(Loaded);
4548   if (!LoadedCE)
4549     return nullptr;
4550
4551   if (LoadedCE->getOpcode() == Instruction::Trunc) {
4552     LoadedCE = dyn_cast<ConstantExpr>(LoadedCE->getOperand(0));
4553     if (!LoadedCE)
4554       return nullptr;
4555   }
4556
4557   if (LoadedCE->getOpcode() != Instruction::Sub)
4558     return nullptr;
4559
4560   auto *LoadedLHS = dyn_cast<ConstantExpr>(LoadedCE->getOperand(0));
4561   if (!LoadedLHS || LoadedLHS->getOpcode() != Instruction::PtrToInt)
4562     return nullptr;
4563   auto *LoadedLHSPtr = LoadedLHS->getOperand(0);
4564
4565   Constant *LoadedRHS = LoadedCE->getOperand(1);
4566   GlobalValue *LoadedRHSSym;
4567   APInt LoadedRHSOffset;
4568   if (!IsConstantOffsetFromGlobal(LoadedRHS, LoadedRHSSym, LoadedRHSOffset,
4569                                   DL) ||
4570       PtrSym != LoadedRHSSym || PtrOffset != LoadedRHSOffset)
4571     return nullptr;
4572
4573   return ConstantExpr::getBitCast(LoadedLHSPtr, Int8PtrTy);
4574 }
4575
4576 static bool maskIsAllZeroOrUndef(Value *Mask) {
4577   auto *ConstMask = dyn_cast<Constant>(Mask);
4578   if (!ConstMask)
4579     return false;
4580   if (ConstMask->isNullValue() || isa<UndefValue>(ConstMask))
4581     return true;
4582   for (unsigned I = 0, E = ConstMask->getType()->getVectorNumElements(); I != E;
4583        ++I) {
4584     if (auto *MaskElt = ConstMask->getAggregateElement(I))
4585       if (MaskElt->isNullValue() || isa<UndefValue>(MaskElt))
4586         continue;
4587     return false;
4588   }
4589   return true;
4590 }
4591
4592 template <typename IterTy>
4593 static Value *SimplifyIntrinsic(Function *F, IterTy ArgBegin, IterTy ArgEnd,
4594                                 const SimplifyQuery &Q, unsigned MaxRecurse) {
4595   Intrinsic::ID IID = F->getIntrinsicID();
4596   unsigned NumOperands = std::distance(ArgBegin, ArgEnd);
4597
4598   // Unary Ops
4599   if (NumOperands == 1) {
4600     // Perform idempotent optimizations
4601     if (IsIdempotent(IID)) {
4602       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(*ArgBegin)) {
4603         if (II->getIntrinsicID() == IID)
4604           return II;
4605       }
4606     }
4607
4608     Value *IIOperand = *ArgBegin;
4609     Value *X;
4610     switch (IID) {
4611     case Intrinsic::fabs: {
4612       if (SignBitMustBeZero(IIOperand, Q.TLI))
4613         return IIOperand;
4614       return nullptr;
4615     }
4616     case Intrinsic::bswap: {
4617       // bswap(bswap(x)) -> x
4618       if (match(IIOperand, m_BSwap(m_Value(X))))
4619         return X;
4620       return nullptr;
4621     }
4622     case Intrinsic::bitreverse: {
4623       // bitreverse(bitreverse(x)) -> x
4624       if (match(IIOperand, m_BitReverse(m_Value(X))))
4625         return X;
4626       return nullptr;
4627     }
4628     case Intrinsic::exp: {
4629       // exp(log(x)) -> x
4630       if (Q.CxtI->hasAllowReassoc() &&
4631           match(IIOperand, m_Intrinsic<Intrinsic::log>(m_Value(X))))
4632         return X;
4633       return nullptr;
4634     }
4635     case Intrinsic::exp2: {
4636       // exp2(log2(x)) -> x
4637       if (Q.CxtI->hasAllowReassoc() &&
4638           match(IIOperand, m_Intrinsic<Intrinsic::log2>(m_Value(X))))
4639         return X;
4640       return nullptr;
4641     }
4642     case Intrinsic::log: {
4643       // log(exp(x)) -> x
4644       if (Q.CxtI->hasAllowReassoc() &&
4645           match(IIOperand, m_Intrinsic<Intrinsic::exp>(m_Value(X))))
4646         return X;
4647       return nullptr;
4648     }
4649     case Intrinsic::log2: {
4650       // log2(exp2(x)) -> x
4651       if (Q.CxtI->hasAllowReassoc() &&
4652           match(IIOperand, m_Intrinsic<Intrinsic::exp2>(m_Value(X)))) {
4653         return X;
4654       }
4655       return nullptr;
4656     }
4657     default:
4658       return nullptr;
4659     }
4660   }
4661
4662   // Binary Ops
4663   if (NumOperands == 2) {
4664     Value *LHS = *ArgBegin;
4665     Value *RHS = *(ArgBegin + 1);
4666     Type *ReturnType = F->getReturnType();
4667
4668     switch (IID) {
4669     case Intrinsic::usub_with_overflow:
4670     case Intrinsic::ssub_with_overflow: {
4671       // X - X -> { 0, false }
4672       if (LHS == RHS)
4673         return Constant::getNullValue(ReturnType);
4674
4675       // X - undef -> undef
4676       // undef - X -> undef
4677       if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS))
4678         return UndefValue::get(ReturnType);
4679
4680       return nullptr;
4681     }
4682     case Intrinsic::uadd_with_overflow:
4683     case Intrinsic::sadd_with_overflow: {
4684       // X + undef -> undef
4685       if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS))
4686         return UndefValue::get(ReturnType);
4687
4688       return nullptr;
4689     }
4690     case Intrinsic::umul_with_overflow:
4691     case Intrinsic::smul_with_overflow: {
4692       // 0 * X -> { 0, false }
4693       // X * 0 -> { 0, false }
4694       if (match(LHS, m_Zero()) || match(RHS, m_Zero()))
4695         return Constant::getNullValue(ReturnType);
4696
4697       // undef * X -> { 0, false }
4698       // X * undef -> { 0, false }
4699       if (match(LHS, m_Undef()) || match(RHS, m_Undef()))
4700         return Constant::getNullValue(ReturnType);
4701
4702       return nullptr;
4703     }
4704     case Intrinsic::load_relative: {
4705       Constant *C0 = dyn_cast<Constant>(LHS);
4706       Constant *C1 = dyn_cast<Constant>(RHS);
4707       if (C0 && C1)
4708         return SimplifyRelativeLoad(C0, C1, Q.DL);
4709       return nullptr;
4710     }
4711     case Intrinsic::powi:
4712       if (ConstantInt *Power = dyn_cast<ConstantInt>(RHS)) {
4713         // powi(x, 0) -> 1.0
4714         if (Power->isZero())
4715           return ConstantFP::get(LHS->getType(), 1.0);
4716         // powi(x, 1) -> x
4717         if (Power->isOne())
4718           return LHS;
4719       }
4720       return nullptr;
4721     default:
4722       return nullptr;
4723     }
4724   }
4725
4726   // Simplify calls to llvm.masked.load.*
4727   switch (IID) {
4728   case Intrinsic::masked_load: {
4729     Value *MaskArg = ArgBegin[2];
4730     Value *PassthruArg = ArgBegin[3];
4731     // If the mask is all zeros or undef, the "passthru" argument is the result.
4732     if (maskIsAllZeroOrUndef(MaskArg))
4733       return PassthruArg;
4734     return nullptr;
4735   }
4736   default:
4737     return nullptr;
4738   }
4739 }
4740
4741 template <typename IterTy>
4742 static Value *SimplifyCall(ImmutableCallSite CS, Value *V, IterTy ArgBegin,
4743                            IterTy ArgEnd, const SimplifyQuery &Q,
4744                            unsigned MaxRecurse) {
4745   Type *Ty = V->getType();
4746   if (PointerType *PTy = dyn_cast<PointerType>(Ty))
4747     Ty = PTy->getElementType();
4748   FunctionType *FTy = cast<FunctionType>(Ty);
4749
4750   // call undef -> undef
4751   // call null -> undef
4752   if (isa<UndefValue>(V) || isa<ConstantPointerNull>(V))
4753     return UndefValue::get(FTy->getReturnType());
4754
4755   Function *F = dyn_cast<Function>(V);
4756   if (!F)
4757     return nullptr;
4758
4759   if (F->isIntrinsic())
4760     if (Value *Ret = SimplifyIntrinsic(F, ArgBegin, ArgEnd, Q, MaxRecurse))
4761       return Ret;
4762
4763   if (!canConstantFoldCallTo(CS, F))
4764     return nullptr;
4765
4766   SmallVector<Constant *, 4> ConstantArgs;
4767   ConstantArgs.reserve(ArgEnd - ArgBegin);
4768   for (IterTy I = ArgBegin, E = ArgEnd; I != E; ++I) {
4769     Constant *C = dyn_cast<Constant>(*I);
4770     if (!C)
4771       return nullptr;
4772     ConstantArgs.push_back(C);
4773   }
4774
4775   return ConstantFoldCall(CS, F, ConstantArgs, Q.TLI);
4776 }
4777
4778 Value *llvm::SimplifyCall(ImmutableCallSite CS, Value *V,
4779                           User::op_iterator ArgBegin, User::op_iterator ArgEnd,
4780                           const SimplifyQuery &Q) {
4781   return ::SimplifyCall(CS, V, ArgBegin, ArgEnd, Q, RecursionLimit);
4782 }
4783
4784 Value *llvm::SimplifyCall(ImmutableCallSite CS, Value *V,
4785                           ArrayRef<Value *> Args, const SimplifyQuery &Q) {
4786   return ::SimplifyCall(CS, V, Args.begin(), Args.end(), Q, RecursionLimit);
4787 }
4788
4789 Value *llvm::SimplifyCall(ImmutableCallSite ICS, const SimplifyQuery &Q) {
4790   CallSite CS(const_cast<Instruction*>(ICS.getInstruction()));
4791   return ::SimplifyCall(CS, CS.getCalledValue(), CS.arg_begin(), CS.arg_end(),
4792                         Q, RecursionLimit);
4793 }
4794
4795 /// See if we can compute a simplified version of this instruction.
4796 /// If not, this returns null.
4797
4798 Value *llvm::SimplifyInstruction(Instruction *I, const SimplifyQuery &SQ,
4799                                  OptimizationRemarkEmitter *ORE) {
4800   const SimplifyQuery Q = SQ.CxtI ? SQ : SQ.getWithInstruction(I);
4801   Value *Result;
4802
4803   switch (I->getOpcode()) {
4804   default:
4805     Result = ConstantFoldInstruction(I, Q.DL, Q.TLI);
4806     break;
4807   case Instruction::FAdd:
4808     Result = SimplifyFAddInst(I->getOperand(0), I->getOperand(1),
4809                               I->getFastMathFlags(), Q);
4810     break;
4811   case Instruction::Add:
4812     Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
4813                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
4814                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(), Q);
4815     break;
4816   case Instruction::FSub:
4817     Result = SimplifyFSubInst(I->getOperand(0), I->getOperand(1),
4818                               I->getFastMathFlags(), Q);
4819     break;
4820   case Instruction::Sub:
4821     Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
4822                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
4823                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(), Q);
4824     break;
4825   case Instruction::FMul:
4826     Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1),
4827                               I->getFastMathFlags(), Q);
4828     break;
4829   case Instruction::Mul:
4830     Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), Q);
4831     break;
4832   case Instruction::SDiv:
4833     Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), Q);
4834     break;
4835   case Instruction::UDiv:
4836     Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), Q);
4837     break;
4838   case Instruction::FDiv:
4839     Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1),
4840                               I->getFastMathFlags(), Q);
4841     break;
4842   case Instruction::SRem:
4843     Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), Q);
4844     break;
4845   case Instruction::URem:
4846     Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), Q);
4847     break;
4848   case Instruction::FRem:
4849     Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1),
4850                               I->getFastMathFlags(), Q);
4851     break;
4852   case Instruction::Shl:
4853     Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1),
4854                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
4855                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(), Q);
4856     break;
4857   case Instruction::LShr:
4858     Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1),
4859                               cast<BinaryOperator>(I)->isExact(), Q);
4860     break;
4861   case Instruction::AShr:
4862     Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1),
4863                               cast<BinaryOperator>(I)->isExact(), Q);
4864     break;
4865   case Instruction::And:
4866     Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), Q);
4867     break;
4868   case Instruction::Or:
4869     Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), Q);
4870     break;
4871   case Instruction::Xor:
4872     Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), Q);
4873     break;
4874   case Instruction::ICmp:
4875     Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
4876                               I->getOperand(0), I->getOperand(1), Q);
4877     break;
4878   case Instruction::FCmp:
4879     Result =
4880         SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), I->getOperand(0),
4881                          I->getOperand(1), I->getFastMathFlags(), Q);
4882     break;
4883   case Instruction::Select:
4884     Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
4885                                 I->getOperand(2), Q);
4886     break;
4887   case Instruction::GetElementPtr: {
4888     SmallVector<Value *, 8> Ops(I->op_begin(), I->op_end());
4889     Result = SimplifyGEPInst(cast<GetElementPtrInst>(I)->getSourceElementType(),
4890                              Ops, Q);
4891     break;
4892   }
4893   case Instruction::InsertValue: {
4894     InsertValueInst *IV = cast<InsertValueInst>(I);
4895     Result = SimplifyInsertValueInst(IV->getAggregateOperand(),
4896                                      IV->getInsertedValueOperand(),
4897                                      IV->getIndices(), Q);
4898     break;
4899   }
4900   case Instruction::InsertElement: {
4901     auto *IE = cast<InsertElementInst>(I);
4902     Result = SimplifyInsertElementInst(IE->getOperand(0), IE->getOperand(1),
4903                                        IE->getOperand(2), Q);
4904     break;
4905   }
4906   case Instruction::ExtractValue: {
4907     auto *EVI = cast<ExtractValueInst>(I);
4908     Result = SimplifyExtractValueInst(EVI->getAggregateOperand(),
4909                                       EVI->getIndices(), Q);
4910     break;
4911   }
4912   case Instruction::ExtractElement: {
4913     auto *EEI = cast<ExtractElementInst>(I);
4914     Result = SimplifyExtractElementInst(EEI->getVectorOperand(),
4915                                         EEI->getIndexOperand(), Q);
4916     break;
4917   }
4918   case Instruction::ShuffleVector: {
4919     auto *SVI = cast<ShuffleVectorInst>(I);
4920     Result = SimplifyShuffleVectorInst(SVI->getOperand(0), SVI->getOperand(1),
4921                                        SVI->getMask(), SVI->getType(), Q);
4922     break;
4923   }
4924   case Instruction::PHI:
4925     Result = SimplifyPHINode(cast<PHINode>(I), Q);
4926     break;
4927   case Instruction::Call: {
4928     CallSite CS(cast<CallInst>(I));
4929     Result = SimplifyCall(CS, Q);
4930     break;
4931   }
4932 #define HANDLE_CAST_INST(num, opc, clas) case Instruction::opc:
4933 #include "llvm/IR/Instruction.def"
4934 #undef HANDLE_CAST_INST
4935     Result =
4936         SimplifyCastInst(I->getOpcode(), I->getOperand(0), I->getType(), Q);
4937     break;
4938   case Instruction::Alloca:
4939     // No simplifications for Alloca and it can't be constant folded.
4940     Result = nullptr;
4941     break;
4942   }
4943
4944   // In general, it is possible for computeKnownBits to determine all bits in a
4945   // value even when the operands are not all constants.
4946   if (!Result && I->getType()->isIntOrIntVectorTy()) {
4947     KnownBits Known = computeKnownBits(I, Q.DL, /*Depth*/ 0, Q.AC, I, Q.DT, ORE);
4948     if (Known.isConstant())
4949       Result = ConstantInt::get(I->getType(), Known.getConstant());
4950   }
4951
4952   /// If called on unreachable code, the above logic may report that the
4953   /// instruction simplified to itself.  Make life easier for users by
4954   /// detecting that case here, returning a safe value instead.
4955   return Result == I ? UndefValue::get(I->getType()) : Result;
4956 }
4957
4958 /// Implementation of recursive simplification through an instruction's
4959 /// uses.
4960 ///
4961 /// This is the common implementation of the recursive simplification routines.
4962 /// If we have a pre-simplified value in 'SimpleV', that is forcibly used to
4963 /// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of
4964 /// instructions to process and attempt to simplify it using
4965 /// InstructionSimplify.
4966 ///
4967 /// This routine returns 'true' only when *it* simplifies something. The passed
4968 /// in simplified value does not count toward this.
4969 static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV,
4970                                               const TargetLibraryInfo *TLI,
4971                                               const DominatorTree *DT,
4972                                               AssumptionCache *AC) {
4973   bool Simplified = false;
4974   SmallSetVector<Instruction *, 8> Worklist;
4975   const DataLayout &DL = I->getModule()->getDataLayout();
4976
4977   // If we have an explicit value to collapse to, do that round of the
4978   // simplification loop by hand initially.
4979   if (SimpleV) {
4980     for (User *U : I->users())
4981       if (U != I)
4982         Worklist.insert(cast<Instruction>(U));
4983
4984     // Replace the instruction with its simplified value.
4985     I->replaceAllUsesWith(SimpleV);
4986
4987     // Gracefully handle edge cases where the instruction is not wired into any
4988     // parent block.
4989     if (I->getParent() && !I->isEHPad() && !isa<TerminatorInst>(I) &&
4990         !I->mayHaveSideEffects())
4991       I->eraseFromParent();
4992   } else {
4993     Worklist.insert(I);
4994   }
4995
4996   // Note that we must test the size on each iteration, the worklist can grow.
4997   for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
4998     I = Worklist[Idx];
4999
5000     // See if this instruction simplifies.
5001     SimpleV = SimplifyInstruction(I, {DL, TLI, DT, AC});
5002     if (!SimpleV)
5003       continue;
5004
5005     Simplified = true;
5006
5007     // Stash away all the uses of the old instruction so we can check them for
5008     // recursive simplifications after a RAUW. This is cheaper than checking all
5009     // uses of To on the recursive step in most cases.
5010     for (User *U : I->users())
5011       Worklist.insert(cast<Instruction>(U));
5012
5013     // Replace the instruction with its simplified value.
5014     I->replaceAllUsesWith(SimpleV);
5015
5016     // Gracefully handle edge cases where the instruction is not wired into any
5017     // parent block.
5018     if (I->getParent() && !I->isEHPad() && !isa<TerminatorInst>(I) &&
5019         !I->mayHaveSideEffects())
5020       I->eraseFromParent();
5021   }
5022   return Simplified;
5023 }
5024
5025 bool llvm::recursivelySimplifyInstruction(Instruction *I,
5026                                           const TargetLibraryInfo *TLI,
5027                                           const DominatorTree *DT,
5028                                           AssumptionCache *AC) {
5029   return replaceAndRecursivelySimplifyImpl(I, nullptr, TLI, DT, AC);
5030 }
5031
5032 bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
5033                                          const TargetLibraryInfo *TLI,
5034                                          const DominatorTree *DT,
5035                                          AssumptionCache *AC) {
5036   assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!");
5037   assert(SimpleV && "Must provide a simplified value.");
5038   return replaceAndRecursivelySimplifyImpl(I, SimpleV, TLI, DT, AC);
5039 }
5040
5041 namespace llvm {
5042 const SimplifyQuery getBestSimplifyQuery(Pass &P, Function &F) {
5043   auto *DTWP = P.getAnalysisIfAvailable<DominatorTreeWrapperPass>();
5044   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
5045   auto *TLIWP = P.getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
5046   auto *TLI = TLIWP ? &TLIWP->getTLI() : nullptr;
5047   auto *ACWP = P.getAnalysisIfAvailable<AssumptionCacheTracker>();
5048   auto *AC = ACWP ? &ACWP->getAssumptionCache(F) : nullptr;
5049   return {F.getParent()->getDataLayout(), TLI, DT, AC};
5050 }
5051
5052 const SimplifyQuery getBestSimplifyQuery(LoopStandardAnalysisResults &AR,
5053                                          const DataLayout &DL) {
5054   return {DL, &AR.TLI, &AR.DT, &AR.AC};
5055 }
5056
5057 template <class T, class... TArgs>
5058 const SimplifyQuery getBestSimplifyQuery(AnalysisManager<T, TArgs...> &AM,
5059                                          Function &F) {
5060   auto *DT = AM.template getCachedResult<DominatorTreeAnalysis>(F);
5061   auto *TLI = AM.template getCachedResult<TargetLibraryAnalysis>(F);
5062   auto *AC = AM.template getCachedResult<AssumptionAnalysis>(F);
5063   return {F.getParent()->getDataLayout(), TLI, DT, AC};
5064 }
5065 template const SimplifyQuery getBestSimplifyQuery(AnalysisManager<Function> &,
5066                                                   Function &);
5067 }