LLVM API Documentation

InstructionSimplify.cpp
Go to the documentation of this file.
00001 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements routines for folding instructions into simpler forms
00011 // that do not require creating new instructions.  This does constant folding
00012 // ("add i32 1, 1" -> "2") but can also handle non-constant operands, either
00013 // returning a constant ("and i32 %x, 0" -> "0") or an already existing value
00014 // ("and i32 %x, %x" -> "%x").  All operands are assumed to have already been
00015 // simplified: This is usually true and assuming it simplifies the logic (if
00016 // they have not been simplified then results are correct but maybe suboptimal).
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #define DEBUG_TYPE "instsimplify"
00021 #include "llvm/Analysis/InstructionSimplify.h"
00022 #include "llvm/ADT/SetVector.h"
00023 #include "llvm/ADT/Statistic.h"
00024 #include "llvm/Analysis/ConstantFolding.h"
00025 #include "llvm/Analysis/MemoryBuiltins.h"
00026 #include "llvm/Analysis/ValueTracking.h"
00027 #include "llvm/IR/ConstantRange.h"
00028 #include "llvm/IR/DataLayout.h"
00029 #include "llvm/IR/Dominators.h"
00030 #include "llvm/IR/GetElementPtrTypeIterator.h"
00031 #include "llvm/IR/GlobalAlias.h"
00032 #include "llvm/IR/Operator.h"
00033 #include "llvm/IR/PatternMatch.h"
00034 #include "llvm/IR/ValueHandle.h"
00035 using namespace llvm;
00036 using namespace llvm::PatternMatch;
00037 
00038 enum { RecursionLimit = 3 };
00039 
00040 STATISTIC(NumExpand,  "Number of expansions");
00041 STATISTIC(NumFactor , "Number of factorizations");
00042 STATISTIC(NumReassoc, "Number of reassociations");
00043 
00044 struct Query {
00045   const DataLayout *DL;
00046   const TargetLibraryInfo *TLI;
00047   const DominatorTree *DT;
00048 
00049   Query(const DataLayout *DL, const TargetLibraryInfo *tli,
00050         const DominatorTree *dt) : DL(DL), TLI(tli), DT(dt) {}
00051 };
00052 
00053 static Value *SimplifyAndInst(Value *, Value *, const Query &, unsigned);
00054 static Value *SimplifyBinOp(unsigned, Value *, Value *, const Query &,
00055                             unsigned);
00056 static Value *SimplifyCmpInst(unsigned, Value *, Value *, const Query &,
00057                               unsigned);
00058 static Value *SimplifyOrInst(Value *, Value *, const Query &, unsigned);
00059 static Value *SimplifyXorInst(Value *, Value *, const Query &, unsigned);
00060 static Value *SimplifyTruncInst(Value *, Type *, const Query &, unsigned);
00061 
00062 /// getFalse - For a boolean type, or a vector of boolean type, return false, or
00063 /// a vector with every element false, as appropriate for the type.
00064 static Constant *getFalse(Type *Ty) {
00065   assert(Ty->getScalarType()->isIntegerTy(1) &&
00066          "Expected i1 type or a vector of i1!");
00067   return Constant::getNullValue(Ty);
00068 }
00069 
00070 /// getTrue - For a boolean type, or a vector of boolean type, return true, or
00071 /// a vector with every element true, as appropriate for the type.
00072 static Constant *getTrue(Type *Ty) {
00073   assert(Ty->getScalarType()->isIntegerTy(1) &&
00074          "Expected i1 type or a vector of i1!");
00075   return Constant::getAllOnesValue(Ty);
00076 }
00077 
00078 /// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"?
00079 static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS,
00080                           Value *RHS) {
00081   CmpInst *Cmp = dyn_cast<CmpInst>(V);
00082   if (!Cmp)
00083     return false;
00084   CmpInst::Predicate CPred = Cmp->getPredicate();
00085   Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1);
00086   if (CPred == Pred && CLHS == LHS && CRHS == RHS)
00087     return true;
00088   return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS &&
00089     CRHS == LHS;
00090 }
00091 
00092 /// ValueDominatesPHI - Does the given value dominate the specified phi node?
00093 static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
00094   Instruction *I = dyn_cast<Instruction>(V);
00095   if (!I)
00096     // Arguments and constants dominate all instructions.
00097     return true;
00098 
00099   // If we are processing instructions (and/or basic blocks) that have not been
00100   // fully added to a function, the parent nodes may still be null. Simply
00101   // return the conservative answer in these cases.
00102   if (!I->getParent() || !P->getParent() || !I->getParent()->getParent())
00103     return false;
00104 
00105   // If we have a DominatorTree then do a precise test.
00106   if (DT) {
00107     if (!DT->isReachableFromEntry(P->getParent()))
00108       return true;
00109     if (!DT->isReachableFromEntry(I->getParent()))
00110       return false;
00111     return DT->dominates(I, P);
00112   }
00113 
00114   // Otherwise, if the instruction is in the entry block, and is not an invoke,
00115   // then it obviously dominates all phi nodes.
00116   if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() &&
00117       !isa<InvokeInst>(I))
00118     return true;
00119 
00120   return false;
00121 }
00122 
00123 /// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning
00124 /// it into "(A op B) op' (A op C)".  Here "op" is given by Opcode and "op'" is
00125 /// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.
00126 /// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
00127 /// Returns the simplified value, or null if no simplification was performed.
00128 static Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS,
00129                           unsigned OpcToExpand, const Query &Q,
00130                           unsigned MaxRecurse) {
00131   Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand;
00132   // Recursion is always used, so bail out at once if we already hit the limit.
00133   if (!MaxRecurse--)
00134     return nullptr;
00135 
00136   // Check whether the expression has the form "(A op' B) op C".
00137   if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS))
00138     if (Op0->getOpcode() == OpcodeToExpand) {
00139       // It does!  Try turning it into "(A op C) op' (B op C)".
00140       Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
00141       // Do "A op C" and "B op C" both simplify?
00142       if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse))
00143         if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
00144           // They do! Return "L op' R" if it simplifies or is already available.
00145           // If "L op' R" equals "A op' B" then "L op' R" is just the LHS.
00146           if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand)
00147                                      && L == B && R == A)) {
00148             ++NumExpand;
00149             return LHS;
00150           }
00151           // Otherwise return "L op' R" if it simplifies.
00152           if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
00153             ++NumExpand;
00154             return V;
00155           }
00156         }
00157     }
00158 
00159   // Check whether the expression has the form "A op (B op' C)".
00160   if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
00161     if (Op1->getOpcode() == OpcodeToExpand) {
00162       // It does!  Try turning it into "(A op B) op' (A op C)".
00163       Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
00164       // Do "A op B" and "A op C" both simplify?
00165       if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse))
00166         if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) {
00167           // They do! Return "L op' R" if it simplifies or is already available.
00168           // If "L op' R" equals "B op' C" then "L op' R" is just the RHS.
00169           if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand)
00170                                      && L == C && R == B)) {
00171             ++NumExpand;
00172             return RHS;
00173           }
00174           // Otherwise return "L op' R" if it simplifies.
00175           if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
00176             ++NumExpand;
00177             return V;
00178           }
00179         }
00180     }
00181 
00182   return nullptr;
00183 }
00184 
00185 /// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term
00186 /// using the operation OpCodeToExtract.  For example, when Opcode is Add and
00187 /// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)".
00188 /// Returns the simplified value, or null if no simplification was performed.
00189 static Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS,
00190                              unsigned OpcToExtract, const Query &Q,
00191                              unsigned MaxRecurse) {
00192   Instruction::BinaryOps OpcodeToExtract = (Instruction::BinaryOps)OpcToExtract;
00193   // Recursion is always used, so bail out at once if we already hit the limit.
00194   if (!MaxRecurse--)
00195     return nullptr;
00196 
00197   BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
00198   BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
00199 
00200   if (!Op0 || Op0->getOpcode() != OpcodeToExtract ||
00201       !Op1 || Op1->getOpcode() != OpcodeToExtract)
00202     return nullptr;
00203 
00204   // The expression has the form "(A op' B) op (C op' D)".
00205   Value *A = Op0->getOperand(0), *B = Op0->getOperand(1);
00206   Value *C = Op1->getOperand(0), *D = Op1->getOperand(1);
00207 
00208   // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)".
00209   // Does the instruction have the form "(A op' B) op (A op' D)" or, in the
00210   // commutative case, "(A op' B) op (C op' A)"?
00211   if (A == C || (Instruction::isCommutative(OpcodeToExtract) && A == D)) {
00212     Value *DD = A == C ? D : C;
00213     // Form "A op' (B op DD)" if it simplifies completely.
00214     // Does "B op DD" simplify?
00215     if (Value *V = SimplifyBinOp(Opcode, B, DD, Q, MaxRecurse)) {
00216       // It does!  Return "A op' V" if it simplifies or is already available.
00217       // If V equals B then "A op' V" is just the LHS.  If V equals DD then
00218       // "A op' V" is just the RHS.
00219       if (V == B || V == DD) {
00220         ++NumFactor;
00221         return V == B ? LHS : RHS;
00222       }
00223       // Otherwise return "A op' V" if it simplifies.
00224       if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, Q, MaxRecurse)) {
00225         ++NumFactor;
00226         return W;
00227       }
00228     }
00229   }
00230 
00231   // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)".
00232   // Does the instruction have the form "(A op' B) op (C op' B)" or, in the
00233   // commutative case, "(A op' B) op (B op' D)"?
00234   if (B == D || (Instruction::isCommutative(OpcodeToExtract) && B == C)) {
00235     Value *CC = B == D ? C : D;
00236     // Form "(A op CC) op' B" if it simplifies completely..
00237     // Does "A op CC" simplify?
00238     if (Value *V = SimplifyBinOp(Opcode, A, CC, Q, MaxRecurse)) {
00239       // It does!  Return "V op' B" if it simplifies or is already available.
00240       // If V equals A then "V op' B" is just the LHS.  If V equals CC then
00241       // "V op' B" is just the RHS.
00242       if (V == A || V == CC) {
00243         ++NumFactor;
00244         return V == A ? LHS : RHS;
00245       }
00246       // Otherwise return "V op' B" if it simplifies.
00247       if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, Q, MaxRecurse)) {
00248         ++NumFactor;
00249         return W;
00250       }
00251     }
00252   }
00253 
00254   return nullptr;
00255 }
00256 
00257 /// SimplifyAssociativeBinOp - Generic simplifications for associative binary
00258 /// operations.  Returns the simpler value, or null if none was found.
00259 static Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS,
00260                                        const Query &Q, unsigned MaxRecurse) {
00261   Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc;
00262   assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
00263 
00264   // Recursion is always used, so bail out at once if we already hit the limit.
00265   if (!MaxRecurse--)
00266     return nullptr;
00267 
00268   BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
00269   BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
00270 
00271   // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely.
00272   if (Op0 && Op0->getOpcode() == Opcode) {
00273     Value *A = Op0->getOperand(0);
00274     Value *B = Op0->getOperand(1);
00275     Value *C = RHS;
00276 
00277     // Does "B op C" simplify?
00278     if (Value *V = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
00279       // It does!  Return "A op V" if it simplifies or is already available.
00280       // If V equals B then "A op V" is just the LHS.
00281       if (V == B) return LHS;
00282       // Otherwise return "A op V" if it simplifies.
00283       if (Value *W = SimplifyBinOp(Opcode, A, V, Q, MaxRecurse)) {
00284         ++NumReassoc;
00285         return W;
00286       }
00287     }
00288   }
00289 
00290   // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely.
00291   if (Op1 && Op1->getOpcode() == Opcode) {
00292     Value *A = LHS;
00293     Value *B = Op1->getOperand(0);
00294     Value *C = Op1->getOperand(1);
00295 
00296     // Does "A op B" simplify?
00297     if (Value *V = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) {
00298       // It does!  Return "V op C" if it simplifies or is already available.
00299       // If V equals B then "V op C" is just the RHS.
00300       if (V == B) return RHS;
00301       // Otherwise return "V op C" if it simplifies.
00302       if (Value *W = SimplifyBinOp(Opcode, V, C, Q, MaxRecurse)) {
00303         ++NumReassoc;
00304         return W;
00305       }
00306     }
00307   }
00308 
00309   // The remaining transforms require commutativity as well as associativity.
00310   if (!Instruction::isCommutative(Opcode))
00311     return nullptr;
00312 
00313   // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely.
00314   if (Op0 && Op0->getOpcode() == Opcode) {
00315     Value *A = Op0->getOperand(0);
00316     Value *B = Op0->getOperand(1);
00317     Value *C = RHS;
00318 
00319     // Does "C op A" simplify?
00320     if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
00321       // It does!  Return "V op B" if it simplifies or is already available.
00322       // If V equals A then "V op B" is just the LHS.
00323       if (V == A) return LHS;
00324       // Otherwise return "V op B" if it simplifies.
00325       if (Value *W = SimplifyBinOp(Opcode, V, B, Q, MaxRecurse)) {
00326         ++NumReassoc;
00327         return W;
00328       }
00329     }
00330   }
00331 
00332   // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely.
00333   if (Op1 && Op1->getOpcode() == Opcode) {
00334     Value *A = LHS;
00335     Value *B = Op1->getOperand(0);
00336     Value *C = Op1->getOperand(1);
00337 
00338     // Does "C op A" simplify?
00339     if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
00340       // It does!  Return "B op V" if it simplifies or is already available.
00341       // If V equals C then "B op V" is just the RHS.
00342       if (V == C) return RHS;
00343       // Otherwise return "B op V" if it simplifies.
00344       if (Value *W = SimplifyBinOp(Opcode, B, V, Q, MaxRecurse)) {
00345         ++NumReassoc;
00346         return W;
00347       }
00348     }
00349   }
00350 
00351   return nullptr;
00352 }
00353 
00354 /// ThreadBinOpOverSelect - In the case of a binary operation with a select
00355 /// instruction as an operand, try to simplify the binop by seeing whether
00356 /// evaluating it on both branches of the select results in the same value.
00357 /// Returns the common value if so, otherwise returns null.
00358 static Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS,
00359                                     const Query &Q, unsigned MaxRecurse) {
00360   // Recursion is always used, so bail out at once if we already hit the limit.
00361   if (!MaxRecurse--)
00362     return nullptr;
00363 
00364   SelectInst *SI;
00365   if (isa<SelectInst>(LHS)) {
00366     SI = cast<SelectInst>(LHS);
00367   } else {
00368     assert(isa<SelectInst>(RHS) && "No select instruction operand!");
00369     SI = cast<SelectInst>(RHS);
00370   }
00371 
00372   // Evaluate the BinOp on the true and false branches of the select.
00373   Value *TV;
00374   Value *FV;
00375   if (SI == LHS) {
00376     TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse);
00377     FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse);
00378   } else {
00379     TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse);
00380     FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse);
00381   }
00382 
00383   // If they simplified to the same value, then return the common value.
00384   // If they both failed to simplify then return null.
00385   if (TV == FV)
00386     return TV;
00387 
00388   // If one branch simplified to undef, return the other one.
00389   if (TV && isa<UndefValue>(TV))
00390     return FV;
00391   if (FV && isa<UndefValue>(FV))
00392     return TV;
00393 
00394   // If applying the operation did not change the true and false select values,
00395   // then the result of the binop is the select itself.
00396   if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
00397     return SI;
00398 
00399   // If one branch simplified and the other did not, and the simplified
00400   // value is equal to the unsimplified one, return the simplified value.
00401   // For example, select (cond, X, X & Z) & Z -> X & Z.
00402   if ((FV && !TV) || (TV && !FV)) {
00403     // Check that the simplified value has the form "X op Y" where "op" is the
00404     // same as the original operation.
00405     Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
00406     if (Simplified && Simplified->getOpcode() == Opcode) {
00407       // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
00408       // We already know that "op" is the same as for the simplified value.  See
00409       // if the operands match too.  If so, return the simplified value.
00410       Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
00411       Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
00412       Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
00413       if (Simplified->getOperand(0) == UnsimplifiedLHS &&
00414           Simplified->getOperand(1) == UnsimplifiedRHS)
00415         return Simplified;
00416       if (Simplified->isCommutative() &&
00417           Simplified->getOperand(1) == UnsimplifiedLHS &&
00418           Simplified->getOperand(0) == UnsimplifiedRHS)
00419         return Simplified;
00420     }
00421   }
00422 
00423   return nullptr;
00424 }
00425 
00426 /// ThreadCmpOverSelect - In the case of a comparison with a select instruction,
00427 /// try to simplify the comparison by seeing whether both branches of the select
00428 /// result in the same value.  Returns the common value if so, otherwise returns
00429 /// null.
00430 static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
00431                                   Value *RHS, const Query &Q,
00432                                   unsigned MaxRecurse) {
00433   // Recursion is always used, so bail out at once if we already hit the limit.
00434   if (!MaxRecurse--)
00435     return nullptr;
00436 
00437   // Make sure the select is on the LHS.
00438   if (!isa<SelectInst>(LHS)) {
00439     std::swap(LHS, RHS);
00440     Pred = CmpInst::getSwappedPredicate(Pred);
00441   }
00442   assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!");
00443   SelectInst *SI = cast<SelectInst>(LHS);
00444   Value *Cond = SI->getCondition();
00445   Value *TV = SI->getTrueValue();
00446   Value *FV = SI->getFalseValue();
00447 
00448   // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it.
00449   // Does "cmp TV, RHS" simplify?
00450   Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse);
00451   if (TCmp == Cond) {
00452     // It not only simplified, it simplified to the select condition.  Replace
00453     // it with 'true'.
00454     TCmp = getTrue(Cond->getType());
00455   } else if (!TCmp) {
00456     // It didn't simplify.  However if "cmp TV, RHS" is equal to the select
00457     // condition then we can replace it with 'true'.  Otherwise give up.
00458     if (!isSameCompare(Cond, Pred, TV, RHS))
00459       return nullptr;
00460     TCmp = getTrue(Cond->getType());
00461   }
00462 
00463   // Does "cmp FV, RHS" simplify?
00464   Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse);
00465   if (FCmp == Cond) {
00466     // It not only simplified, it simplified to the select condition.  Replace
00467     // it with 'false'.
00468     FCmp = getFalse(Cond->getType());
00469   } else if (!FCmp) {
00470     // It didn't simplify.  However if "cmp FV, RHS" is equal to the select
00471     // condition then we can replace it with 'false'.  Otherwise give up.
00472     if (!isSameCompare(Cond, Pred, FV, RHS))
00473       return nullptr;
00474     FCmp = getFalse(Cond->getType());
00475   }
00476 
00477   // If both sides simplified to the same value, then use it as the result of
00478   // the original comparison.
00479   if (TCmp == FCmp)
00480     return TCmp;
00481 
00482   // The remaining cases only make sense if the select condition has the same
00483   // type as the result of the comparison, so bail out if this is not so.
00484   if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy())
00485     return nullptr;
00486   // If the false value simplified to false, then the result of the compare
00487   // is equal to "Cond && TCmp".  This also catches the case when the false
00488   // value simplified to false and the true value to true, returning "Cond".
00489   if (match(FCmp, m_Zero()))
00490     if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse))
00491       return V;
00492   // If the true value simplified to true, then the result of the compare
00493   // is equal to "Cond || FCmp".
00494   if (match(TCmp, m_One()))
00495     if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse))
00496       return V;
00497   // Finally, if the false value simplified to true and the true value to
00498   // false, then the result of the compare is equal to "!Cond".
00499   if (match(FCmp, m_One()) && match(TCmp, m_Zero()))
00500     if (Value *V =
00501         SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()),
00502                         Q, MaxRecurse))
00503       return V;
00504 
00505   return nullptr;
00506 }
00507 
00508 /// ThreadBinOpOverPHI - In the case of a binary operation with an operand that
00509 /// is a PHI instruction, try to simplify the binop by seeing whether evaluating
00510 /// it on the incoming phi values yields the same result for every value.  If so
00511 /// returns the common value, otherwise returns null.
00512 static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS,
00513                                  const Query &Q, unsigned MaxRecurse) {
00514   // Recursion is always used, so bail out at once if we already hit the limit.
00515   if (!MaxRecurse--)
00516     return nullptr;
00517 
00518   PHINode *PI;
00519   if (isa<PHINode>(LHS)) {
00520     PI = cast<PHINode>(LHS);
00521     // Bail out if RHS and the phi may be mutually interdependent due to a loop.
00522     if (!ValueDominatesPHI(RHS, PI, Q.DT))
00523       return nullptr;
00524   } else {
00525     assert(isa<PHINode>(RHS) && "No PHI instruction operand!");
00526     PI = cast<PHINode>(RHS);
00527     // Bail out if LHS and the phi may be mutually interdependent due to a loop.
00528     if (!ValueDominatesPHI(LHS, PI, Q.DT))
00529       return nullptr;
00530   }
00531 
00532   // Evaluate the BinOp on the incoming phi values.
00533   Value *CommonValue = nullptr;
00534   for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
00535     Value *Incoming = PI->getIncomingValue(i);
00536     // If the incoming value is the phi node itself, it can safely be skipped.
00537     if (Incoming == PI) continue;
00538     Value *V = PI == LHS ?
00539       SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) :
00540       SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse);
00541     // If the operation failed to simplify, or simplified to a different value
00542     // to previously, then give up.
00543     if (!V || (CommonValue && V != CommonValue))
00544       return nullptr;
00545     CommonValue = V;
00546   }
00547 
00548   return CommonValue;
00549 }
00550 
00551 /// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try
00552 /// try to simplify the comparison by seeing whether comparing with all of the
00553 /// incoming phi values yields the same result every time.  If so returns the
00554 /// common result, otherwise returns null.
00555 static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
00556                                const Query &Q, unsigned MaxRecurse) {
00557   // Recursion is always used, so bail out at once if we already hit the limit.
00558   if (!MaxRecurse--)
00559     return nullptr;
00560 
00561   // Make sure the phi is on the LHS.
00562   if (!isa<PHINode>(LHS)) {
00563     std::swap(LHS, RHS);
00564     Pred = CmpInst::getSwappedPredicate(Pred);
00565   }
00566   assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!");
00567   PHINode *PI = cast<PHINode>(LHS);
00568 
00569   // Bail out if RHS and the phi may be mutually interdependent due to a loop.
00570   if (!ValueDominatesPHI(RHS, PI, Q.DT))
00571     return nullptr;
00572 
00573   // Evaluate the BinOp on the incoming phi values.
00574   Value *CommonValue = nullptr;
00575   for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) {
00576     Value *Incoming = PI->getIncomingValue(i);
00577     // If the incoming value is the phi node itself, it can safely be skipped.
00578     if (Incoming == PI) continue;
00579     Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse);
00580     // If the operation failed to simplify, or simplified to a different value
00581     // to previously, then give up.
00582     if (!V || (CommonValue && V != CommonValue))
00583       return nullptr;
00584     CommonValue = V;
00585   }
00586 
00587   return CommonValue;
00588 }
00589 
00590 /// SimplifyAddInst - Given operands for an Add, see if we can
00591 /// fold the result.  If not, this returns null.
00592 static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
00593                               const Query &Q, unsigned MaxRecurse) {
00594   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
00595     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
00596       Constant *Ops[] = { CLHS, CRHS };
00597       return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), Ops,
00598                                       Q.DL, Q.TLI);
00599     }
00600 
00601     // Canonicalize the constant to the RHS.
00602     std::swap(Op0, Op1);
00603   }
00604 
00605   // X + undef -> undef
00606   if (match(Op1, m_Undef()))
00607     return Op1;
00608 
00609   // X + 0 -> X
00610   if (match(Op1, m_Zero()))
00611     return Op0;
00612 
00613   // X + (Y - X) -> Y
00614   // (Y - X) + X -> Y
00615   // Eg: X + -X -> 0
00616   Value *Y = nullptr;
00617   if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
00618       match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
00619     return Y;
00620 
00621   // X + ~X -> -1   since   ~X = -X-1
00622   if (match(Op0, m_Not(m_Specific(Op1))) ||
00623       match(Op1, m_Not(m_Specific(Op0))))
00624     return Constant::getAllOnesValue(Op0->getType());
00625 
00626   /// i1 add -> xor.
00627   if (MaxRecurse && Op0->getType()->isIntegerTy(1))
00628     if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
00629       return V;
00630 
00631   // Try some generic simplifications for associative operations.
00632   if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q,
00633                                           MaxRecurse))
00634     return V;
00635 
00636   // Mul distributes over Add.  Try some generic simplifications based on this.
00637   if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul,
00638                                 Q, MaxRecurse))
00639     return V;
00640 
00641   // Threading Add over selects and phi nodes is pointless, so don't bother.
00642   // Threading over the select in "A + select(cond, B, C)" means evaluating
00643   // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
00644   // only if B and C are equal.  If B and C are equal then (since we assume
00645   // that operands have already been simplified) "select(cond, B, C)" should
00646   // have been simplified to the common value of B and C already.  Analysing
00647   // "A+B" and "A+C" thus gains nothing, but costs compile time.  Similarly
00648   // for threading over phi nodes.
00649 
00650   return nullptr;
00651 }
00652 
00653 Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
00654                              const DataLayout *DL, const TargetLibraryInfo *TLI,
00655                              const DominatorTree *DT) {
00656   return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query (DL, TLI, DT),
00657                            RecursionLimit);
00658 }
00659 
00660 /// \brief Compute the base pointer and cumulative constant offsets for V.
00661 ///
00662 /// This strips all constant offsets off of V, leaving it the base pointer, and
00663 /// accumulates the total constant offset applied in the returned constant. It
00664 /// returns 0 if V is not a pointer, and returns the constant '0' if there are
00665 /// no constant offsets applied.
00666 ///
00667 /// This is very similar to GetPointerBaseWithConstantOffset except it doesn't
00668 /// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc.
00669 /// folding.
00670 static Constant *stripAndComputeConstantOffsets(const DataLayout *DL,
00671                                                 Value *&V,
00672                                                 bool AllowNonInbounds = false) {
00673   assert(V->getType()->getScalarType()->isPointerTy());
00674 
00675   // Without DataLayout, just be conservative for now. Theoretically, more could
00676   // be done in this case.
00677   if (!DL)
00678     return ConstantInt::get(IntegerType::get(V->getContext(), 64), 0);
00679 
00680   Type *IntPtrTy = DL->getIntPtrType(V->getType())->getScalarType();
00681   APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth());
00682 
00683   // Even though we don't look through PHI nodes, we could be called on an
00684   // instruction in an unreachable block, which may be on a cycle.
00685   SmallPtrSet<Value *, 4> Visited;
00686   Visited.insert(V);
00687   do {
00688     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
00689       if ((!AllowNonInbounds && !GEP->isInBounds()) ||
00690           !GEP->accumulateConstantOffset(*DL, Offset))
00691         break;
00692       V = GEP->getPointerOperand();
00693     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
00694       V = cast<Operator>(V)->getOperand(0);
00695     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
00696       if (GA->mayBeOverridden())
00697         break;
00698       V = GA->getAliasee();
00699     } else {
00700       break;
00701     }
00702     assert(V->getType()->getScalarType()->isPointerTy() &&
00703            "Unexpected operand type!");
00704   } while (Visited.insert(V));
00705 
00706   Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset);
00707   if (V->getType()->isVectorTy())
00708     return ConstantVector::getSplat(V->getType()->getVectorNumElements(),
00709                                     OffsetIntPtr);
00710   return OffsetIntPtr;
00711 }
00712 
00713 /// \brief Compute the constant difference between two pointer values.
00714 /// If the difference is not a constant, returns zero.
00715 static Constant *computePointerDifference(const DataLayout *DL,
00716                                           Value *LHS, Value *RHS) {
00717   Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
00718   Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
00719 
00720   // If LHS and RHS are not related via constant offsets to the same base
00721   // value, there is nothing we can do here.
00722   if (LHS != RHS)
00723     return nullptr;
00724 
00725   // Otherwise, the difference of LHS - RHS can be computed as:
00726   //    LHS - RHS
00727   //  = (LHSOffset + Base) - (RHSOffset + Base)
00728   //  = LHSOffset - RHSOffset
00729   return ConstantExpr::getSub(LHSOffset, RHSOffset);
00730 }
00731 
00732 /// SimplifySubInst - Given operands for a Sub, see if we can
00733 /// fold the result.  If not, this returns null.
00734 static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
00735                               const Query &Q, unsigned MaxRecurse) {
00736   if (Constant *CLHS = dyn_cast<Constant>(Op0))
00737     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
00738       Constant *Ops[] = { CLHS, CRHS };
00739       return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(),
00740                                       Ops, Q.DL, Q.TLI);
00741     }
00742 
00743   // X - undef -> undef
00744   // undef - X -> undef
00745   if (match(Op0, m_Undef()) || match(Op1, m_Undef()))
00746     return UndefValue::get(Op0->getType());
00747 
00748   // X - 0 -> X
00749   if (match(Op1, m_Zero()))
00750     return Op0;
00751 
00752   // X - X -> 0
00753   if (Op0 == Op1)
00754     return Constant::getNullValue(Op0->getType());
00755 
00756   // (X*2) - X -> X
00757   // (X<<1) - X -> X
00758   Value *X = nullptr;
00759   if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())) ||
00760       match(Op0, m_Shl(m_Specific(Op1), m_One())))
00761     return Op1;
00762 
00763   // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
00764   // For example, (X + Y) - Y -> X; (Y + X) - Y -> X
00765   Value *Y = nullptr, *Z = Op1;
00766   if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z
00767     // See if "V === Y - Z" simplifies.
00768     if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1))
00769       // It does!  Now see if "X + V" simplifies.
00770       if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) {
00771         // It does, we successfully reassociated!
00772         ++NumReassoc;
00773         return W;
00774       }
00775     // See if "V === X - Z" simplifies.
00776     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
00777       // It does!  Now see if "Y + V" simplifies.
00778       if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse-1)) {
00779         // It does, we successfully reassociated!
00780         ++NumReassoc;
00781         return W;
00782       }
00783   }
00784 
00785   // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies.
00786   // For example, X - (X + 1) -> -1
00787   X = Op0;
00788   if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z)
00789     // See if "V === X - Y" simplifies.
00790     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
00791       // It does!  Now see if "V - Z" simplifies.
00792       if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse-1)) {
00793         // It does, we successfully reassociated!
00794         ++NumReassoc;
00795         return W;
00796       }
00797     // See if "V === X - Z" simplifies.
00798     if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
00799       // It does!  Now see if "V - Y" simplifies.
00800       if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse-1)) {
00801         // It does, we successfully reassociated!
00802         ++NumReassoc;
00803         return W;
00804       }
00805   }
00806 
00807   // Z - (X - Y) -> (Z - X) + Y if everything simplifies.
00808   // For example, X - (X - Y) -> Y.
00809   Z = Op0;
00810   if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y)
00811     // See if "V === Z - X" simplifies.
00812     if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse-1))
00813       // It does!  Now see if "V + Y" simplifies.
00814       if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse-1)) {
00815         // It does, we successfully reassociated!
00816         ++NumReassoc;
00817         return W;
00818       }
00819 
00820   // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies.
00821   if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) &&
00822       match(Op1, m_Trunc(m_Value(Y))))
00823     if (X->getType() == Y->getType())
00824       // See if "V === X - Y" simplifies.
00825       if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
00826         // It does!  Now see if "trunc V" simplifies.
00827         if (Value *W = SimplifyTruncInst(V, Op0->getType(), Q, MaxRecurse-1))
00828           // It does, return the simplified "trunc V".
00829           return W;
00830 
00831   // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...).
00832   if (match(Op0, m_PtrToInt(m_Value(X))) &&
00833       match(Op1, m_PtrToInt(m_Value(Y))))
00834     if (Constant *Result = computePointerDifference(Q.DL, X, Y))
00835       return ConstantExpr::getIntegerCast(Result, Op0->getType(), true);
00836 
00837   // Mul distributes over Sub.  Try some generic simplifications based on this.
00838   if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul,
00839                                 Q, MaxRecurse))
00840     return V;
00841 
00842   // i1 sub -> xor.
00843   if (MaxRecurse && Op0->getType()->isIntegerTy(1))
00844     if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
00845       return V;
00846 
00847   // Threading Sub over selects and phi nodes is pointless, so don't bother.
00848   // Threading over the select in "A - select(cond, B, C)" means evaluating
00849   // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
00850   // only if B and C are equal.  If B and C are equal then (since we assume
00851   // that operands have already been simplified) "select(cond, B, C)" should
00852   // have been simplified to the common value of B and C already.  Analysing
00853   // "A-B" and "A-C" thus gains nothing, but costs compile time.  Similarly
00854   // for threading over phi nodes.
00855 
00856   return nullptr;
00857 }
00858 
00859 Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
00860                              const DataLayout *DL, const TargetLibraryInfo *TLI,
00861                              const DominatorTree *DT) {
00862   return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Query (DL, TLI, DT),
00863                            RecursionLimit);
00864 }
00865 
00866 /// Given operands for an FAdd, see if we can fold the result.  If not, this
00867 /// returns null.
00868 static Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
00869                               const Query &Q, unsigned MaxRecurse) {
00870   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
00871     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
00872       Constant *Ops[] = { CLHS, CRHS };
00873       return ConstantFoldInstOperands(Instruction::FAdd, CLHS->getType(),
00874                                       Ops, Q.DL, Q.TLI);
00875     }
00876 
00877     // Canonicalize the constant to the RHS.
00878     std::swap(Op0, Op1);
00879   }
00880 
00881   // fadd X, -0 ==> X
00882   if (match(Op1, m_NegZero()))
00883     return Op0;
00884 
00885   // fadd X, 0 ==> X, when we know X is not -0
00886   if (match(Op1, m_Zero()) &&
00887       (FMF.noSignedZeros() || CannotBeNegativeZero(Op0)))
00888     return Op0;
00889 
00890   // fadd [nnan ninf] X, (fsub [nnan ninf] 0, X) ==> 0
00891   //   where nnan and ninf have to occur at least once somewhere in this
00892   //   expression
00893   Value *SubOp = nullptr;
00894   if (match(Op1, m_FSub(m_AnyZero(), m_Specific(Op0))))
00895     SubOp = Op1;
00896   else if (match(Op0, m_FSub(m_AnyZero(), m_Specific(Op1))))
00897     SubOp = Op0;
00898   if (SubOp) {
00899     Instruction *FSub = cast<Instruction>(SubOp);
00900     if ((FMF.noNaNs() || FSub->hasNoNaNs()) &&
00901         (FMF.noInfs() || FSub->hasNoInfs()))
00902       return Constant::getNullValue(Op0->getType());
00903   }
00904 
00905   return nullptr;
00906 }
00907 
00908 /// Given operands for an FSub, see if we can fold the result.  If not, this
00909 /// returns null.
00910 static Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
00911                               const Query &Q, unsigned MaxRecurse) {
00912   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
00913     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
00914       Constant *Ops[] = { CLHS, CRHS };
00915       return ConstantFoldInstOperands(Instruction::FSub, CLHS->getType(),
00916                                       Ops, Q.DL, Q.TLI);
00917     }
00918   }
00919 
00920   // fsub X, 0 ==> X
00921   if (match(Op1, m_Zero()))
00922     return Op0;
00923 
00924   // fsub X, -0 ==> X, when we know X is not -0
00925   if (match(Op1, m_NegZero()) &&
00926       (FMF.noSignedZeros() || CannotBeNegativeZero(Op0)))
00927     return Op0;
00928 
00929   // fsub 0, (fsub -0.0, X) ==> X
00930   Value *X;
00931   if (match(Op0, m_AnyZero())) {
00932     if (match(Op1, m_FSub(m_NegZero(), m_Value(X))))
00933       return X;
00934     if (FMF.noSignedZeros() && match(Op1, m_FSub(m_AnyZero(), m_Value(X))))
00935       return X;
00936   }
00937 
00938   // fsub nnan ninf x, x ==> 0.0
00939   if (FMF.noNaNs() && FMF.noInfs() && Op0 == Op1)
00940     return Constant::getNullValue(Op0->getType());
00941 
00942   return nullptr;
00943 }
00944 
00945 /// Given the operands for an FMul, see if we can fold the result
00946 static Value *SimplifyFMulInst(Value *Op0, Value *Op1,
00947                                FastMathFlags FMF,
00948                                const Query &Q,
00949                                unsigned MaxRecurse) {
00950  if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
00951     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
00952       Constant *Ops[] = { CLHS, CRHS };
00953       return ConstantFoldInstOperands(Instruction::FMul, CLHS->getType(),
00954                                       Ops, Q.DL, Q.TLI);
00955     }
00956 
00957     // Canonicalize the constant to the RHS.
00958     std::swap(Op0, Op1);
00959  }
00960 
00961  // fmul X, 1.0 ==> X
00962  if (match(Op1, m_FPOne()))
00963    return Op0;
00964 
00965  // fmul nnan nsz X, 0 ==> 0
00966  if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op1, m_AnyZero()))
00967    return Op1;
00968 
00969  return nullptr;
00970 }
00971 
00972 /// SimplifyMulInst - Given operands for a Mul, see if we can
00973 /// fold the result.  If not, this returns null.
00974 static Value *SimplifyMulInst(Value *Op0, Value *Op1, const Query &Q,
00975                               unsigned MaxRecurse) {
00976   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
00977     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
00978       Constant *Ops[] = { CLHS, CRHS };
00979       return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(),
00980                                       Ops, Q.DL, Q.TLI);
00981     }
00982 
00983     // Canonicalize the constant to the RHS.
00984     std::swap(Op0, Op1);
00985   }
00986 
00987   // X * undef -> 0
00988   if (match(Op1, m_Undef()))
00989     return Constant::getNullValue(Op0->getType());
00990 
00991   // X * 0 -> 0
00992   if (match(Op1, m_Zero()))
00993     return Op1;
00994 
00995   // X * 1 -> X
00996   if (match(Op1, m_One()))
00997     return Op0;
00998 
00999   // (X / Y) * Y -> X if the division is exact.
01000   Value *X = nullptr;
01001   if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y
01002       match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0)))))   // Y * (X / Y)
01003     return X;
01004 
01005   // i1 mul -> and.
01006   if (MaxRecurse && Op0->getType()->isIntegerTy(1))
01007     if (Value *V = SimplifyAndInst(Op0, Op1, Q, MaxRecurse-1))
01008       return V;
01009 
01010   // Try some generic simplifications for associative operations.
01011   if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q,
01012                                           MaxRecurse))
01013     return V;
01014 
01015   // Mul distributes over Add.  Try some generic simplifications based on this.
01016   if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add,
01017                              Q, MaxRecurse))
01018     return V;
01019 
01020   // If the operation is with the result of a select instruction, check whether
01021   // operating on either branch of the select always yields the same value.
01022   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
01023     if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q,
01024                                          MaxRecurse))
01025       return V;
01026 
01027   // If the operation is with the result of a phi instruction, check whether
01028   // operating on all incoming values of the phi always yields the same value.
01029   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
01030     if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q,
01031                                       MaxRecurse))
01032       return V;
01033 
01034   return nullptr;
01035 }
01036 
01037 Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
01038                              const DataLayout *DL, const TargetLibraryInfo *TLI,
01039                              const DominatorTree *DT) {
01040   return ::SimplifyFAddInst(Op0, Op1, FMF, Query (DL, TLI, DT), RecursionLimit);
01041 }
01042 
01043 Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
01044                              const DataLayout *DL, const TargetLibraryInfo *TLI,
01045                              const DominatorTree *DT) {
01046   return ::SimplifyFSubInst(Op0, Op1, FMF, Query (DL, TLI, DT), RecursionLimit);
01047 }
01048 
01049 Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1,
01050                               FastMathFlags FMF,
01051                               const DataLayout *DL,
01052                               const TargetLibraryInfo *TLI,
01053                               const DominatorTree *DT) {
01054   return ::SimplifyFMulInst(Op0, Op1, FMF, Query (DL, TLI, DT), RecursionLimit);
01055 }
01056 
01057 Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const DataLayout *DL,
01058                              const TargetLibraryInfo *TLI,
01059                              const DominatorTree *DT) {
01060   return ::SimplifyMulInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit);
01061 }
01062 
01063 /// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can
01064 /// fold the result.  If not, this returns null.
01065 static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
01066                           const Query &Q, unsigned MaxRecurse) {
01067   if (Constant *C0 = dyn_cast<Constant>(Op0)) {
01068     if (Constant *C1 = dyn_cast<Constant>(Op1)) {
01069       Constant *Ops[] = { C0, C1 };
01070       return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI);
01071     }
01072   }
01073 
01074   bool isSigned = Opcode == Instruction::SDiv;
01075 
01076   // X / undef -> undef
01077   if (match(Op1, m_Undef()))
01078     return Op1;
01079 
01080   // undef / X -> 0
01081   if (match(Op0, m_Undef()))
01082     return Constant::getNullValue(Op0->getType());
01083 
01084   // 0 / X -> 0, we don't need to preserve faults!
01085   if (match(Op0, m_Zero()))
01086     return Op0;
01087 
01088   // X / 1 -> X
01089   if (match(Op1, m_One()))
01090     return Op0;
01091 
01092   if (Op0->getType()->isIntegerTy(1))
01093     // It can't be division by zero, hence it must be division by one.
01094     return Op0;
01095 
01096   // X / X -> 1
01097   if (Op0 == Op1)
01098     return ConstantInt::get(Op0->getType(), 1);
01099 
01100   // (X * Y) / Y -> X if the multiplication does not overflow.
01101   Value *X = nullptr, *Y = nullptr;
01102   if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) {
01103     if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1
01104     OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0);
01105     // If the Mul knows it does not overflow, then we are good to go.
01106     if ((isSigned && Mul->hasNoSignedWrap()) ||
01107         (!isSigned && Mul->hasNoUnsignedWrap()))
01108       return X;
01109     // If X has the form X = A / Y then X * Y cannot overflow.
01110     if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X))
01111       if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y)
01112         return X;
01113   }
01114 
01115   // (X rem Y) / Y -> 0
01116   if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
01117       (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
01118     return Constant::getNullValue(Op0->getType());
01119 
01120   // If the operation is with the result of a select instruction, check whether
01121   // operating on either branch of the select always yields the same value.
01122   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
01123     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
01124       return V;
01125 
01126   // If the operation is with the result of a phi instruction, check whether
01127   // operating on all incoming values of the phi always yields the same value.
01128   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
01129     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
01130       return V;
01131 
01132   return nullptr;
01133 }
01134 
01135 /// SimplifySDivInst - Given operands for an SDiv, see if we can
01136 /// fold the result.  If not, this returns null.
01137 static Value *SimplifySDivInst(Value *Op0, Value *Op1, const Query &Q,
01138                                unsigned MaxRecurse) {
01139   if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse))
01140     return V;
01141 
01142   return nullptr;
01143 }
01144 
01145 Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const DataLayout *DL,
01146                               const TargetLibraryInfo *TLI,
01147                               const DominatorTree *DT) {
01148   return ::SimplifySDivInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit);
01149 }
01150 
01151 /// SimplifyUDivInst - Given operands for a UDiv, see if we can
01152 /// fold the result.  If not, this returns null.
01153 static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const Query &Q,
01154                                unsigned MaxRecurse) {
01155   if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse))
01156     return V;
01157 
01158   return nullptr;
01159 }
01160 
01161 Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout *DL,
01162                               const TargetLibraryInfo *TLI,
01163                               const DominatorTree *DT) {
01164   return ::SimplifyUDivInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit);
01165 }
01166 
01167 static Value *SimplifyFDivInst(Value *Op0, Value *Op1, const Query &Q,
01168                                unsigned) {
01169   // undef / X -> undef    (the undef could be a snan).
01170   if (match(Op0, m_Undef()))
01171     return Op0;
01172 
01173   // X / undef -> undef
01174   if (match(Op1, m_Undef()))
01175     return Op1;
01176 
01177   return nullptr;
01178 }
01179 
01180 Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const DataLayout *DL,
01181                               const TargetLibraryInfo *TLI,
01182                               const DominatorTree *DT) {
01183   return ::SimplifyFDivInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit);
01184 }
01185 
01186 /// SimplifyRem - Given operands for an SRem or URem, see if we can
01187 /// fold the result.  If not, this returns null.
01188 static Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
01189                           const Query &Q, unsigned MaxRecurse) {
01190   if (Constant *C0 = dyn_cast<Constant>(Op0)) {
01191     if (Constant *C1 = dyn_cast<Constant>(Op1)) {
01192       Constant *Ops[] = { C0, C1 };
01193       return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI);
01194     }
01195   }
01196 
01197   // X % undef -> undef
01198   if (match(Op1, m_Undef()))
01199     return Op1;
01200 
01201   // undef % X -> 0
01202   if (match(Op0, m_Undef()))
01203     return Constant::getNullValue(Op0->getType());
01204 
01205   // 0 % X -> 0, we don't need to preserve faults!
01206   if (match(Op0, m_Zero()))
01207     return Op0;
01208 
01209   // X % 0 -> undef, we don't need to preserve faults!
01210   if (match(Op1, m_Zero()))
01211     return UndefValue::get(Op0->getType());
01212 
01213   // X % 1 -> 0
01214   if (match(Op1, m_One()))
01215     return Constant::getNullValue(Op0->getType());
01216 
01217   if (Op0->getType()->isIntegerTy(1))
01218     // It can't be remainder by zero, hence it must be remainder by one.
01219     return Constant::getNullValue(Op0->getType());
01220 
01221   // X % X -> 0
01222   if (Op0 == Op1)
01223     return Constant::getNullValue(Op0->getType());
01224 
01225   // If the operation is with the result of a select instruction, check whether
01226   // operating on either branch of the select always yields the same value.
01227   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
01228     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
01229       return V;
01230 
01231   // If the operation is with the result of a phi instruction, check whether
01232   // operating on all incoming values of the phi always yields the same value.
01233   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
01234     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
01235       return V;
01236 
01237   return nullptr;
01238 }
01239 
01240 /// SimplifySRemInst - Given operands for an SRem, see if we can
01241 /// fold the result.  If not, this returns null.
01242 static Value *SimplifySRemInst(Value *Op0, Value *Op1, const Query &Q,
01243                                unsigned MaxRecurse) {
01244   if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse))
01245     return V;
01246 
01247   return nullptr;
01248 }
01249 
01250 Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const DataLayout *DL,
01251                               const TargetLibraryInfo *TLI,
01252                               const DominatorTree *DT) {
01253   return ::SimplifySRemInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit);
01254 }
01255 
01256 /// SimplifyURemInst - Given operands for a URem, see if we can
01257 /// fold the result.  If not, this returns null.
01258 static Value *SimplifyURemInst(Value *Op0, Value *Op1, const Query &Q,
01259                                unsigned MaxRecurse) {
01260   if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse))
01261     return V;
01262 
01263   return nullptr;
01264 }
01265 
01266 Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout *DL,
01267                               const TargetLibraryInfo *TLI,
01268                               const DominatorTree *DT) {
01269   return ::SimplifyURemInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit);
01270 }
01271 
01272 static Value *SimplifyFRemInst(Value *Op0, Value *Op1, const Query &,
01273                                unsigned) {
01274   // undef % X -> undef    (the undef could be a snan).
01275   if (match(Op0, m_Undef()))
01276     return Op0;
01277 
01278   // X % undef -> undef
01279   if (match(Op1, m_Undef()))
01280     return Op1;
01281 
01282   return nullptr;
01283 }
01284 
01285 Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, const DataLayout *DL,
01286                               const TargetLibraryInfo *TLI,
01287                               const DominatorTree *DT) {
01288   return ::SimplifyFRemInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit);
01289 }
01290 
01291 /// isUndefShift - Returns true if a shift by \c Amount always yields undef.
01292 static bool isUndefShift(Value *Amount) {
01293   Constant *C = dyn_cast<Constant>(Amount);
01294   if (!C)
01295     return false;
01296 
01297   // X shift by undef -> undef because it may shift by the bitwidth.
01298   if (isa<UndefValue>(C))
01299     return true;
01300 
01301   // Shifting by the bitwidth or more is undefined.
01302   if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
01303     if (CI->getValue().getLimitedValue() >=
01304         CI->getType()->getScalarSizeInBits())
01305       return true;
01306 
01307   // If all lanes of a vector shift are undefined the whole shift is.
01308   if (isa<ConstantVector>(C) || isa<ConstantDataVector>(C)) {
01309     for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; ++I)
01310       if (!isUndefShift(C->getAggregateElement(I)))
01311         return false;
01312     return true;
01313   }
01314 
01315   return false;
01316 }
01317 
01318 /// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can
01319 /// fold the result.  If not, this returns null.
01320 static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1,
01321                             const Query &Q, unsigned MaxRecurse) {
01322   if (Constant *C0 = dyn_cast<Constant>(Op0)) {
01323     if (Constant *C1 = dyn_cast<Constant>(Op1)) {
01324       Constant *Ops[] = { C0, C1 };
01325       return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI);
01326     }
01327   }
01328 
01329   // 0 shift by X -> 0
01330   if (match(Op0, m_Zero()))
01331     return Op0;
01332 
01333   // X shift by 0 -> X
01334   if (match(Op1, m_Zero()))
01335     return Op0;
01336 
01337   // Fold undefined shifts.
01338   if (isUndefShift(Op1))
01339     return UndefValue::get(Op0->getType());
01340 
01341   // If the operation is with the result of a select instruction, check whether
01342   // operating on either branch of the select always yields the same value.
01343   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
01344     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
01345       return V;
01346 
01347   // If the operation is with the result of a phi instruction, check whether
01348   // operating on all incoming values of the phi always yields the same value.
01349   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
01350     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
01351       return V;
01352 
01353   return nullptr;
01354 }
01355 
01356 /// SimplifyShlInst - Given operands for an Shl, see if we can
01357 /// fold the result.  If not, this returns null.
01358 static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
01359                               const Query &Q, unsigned MaxRecurse) {
01360   if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse))
01361     return V;
01362 
01363   // undef << X -> 0
01364   if (match(Op0, m_Undef()))
01365     return Constant::getNullValue(Op0->getType());
01366 
01367   // (X >> A) << A -> X
01368   Value *X;
01369   if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1)))))
01370     return X;
01371   return nullptr;
01372 }
01373 
01374 Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
01375                              const DataLayout *DL, const TargetLibraryInfo *TLI,
01376                              const DominatorTree *DT) {
01377   return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Query (DL, TLI, DT),
01378                            RecursionLimit);
01379 }
01380 
01381 /// SimplifyLShrInst - Given operands for an LShr, see if we can
01382 /// fold the result.  If not, this returns null.
01383 static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
01384                                const Query &Q, unsigned MaxRecurse) {
01385   if (Value *V = SimplifyShift(Instruction::LShr, Op0, Op1, Q, MaxRecurse))
01386     return V;
01387 
01388   // X >> X -> 0
01389   if (Op0 == Op1)
01390     return Constant::getNullValue(Op0->getType());
01391 
01392   // undef >>l X -> 0
01393   if (match(Op0, m_Undef()))
01394     return Constant::getNullValue(Op0->getType());
01395 
01396   // (X << A) >> A -> X
01397   Value *X;
01398   if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) &&
01399       cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap())
01400     return X;
01401 
01402   return nullptr;
01403 }
01404 
01405 Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
01406                               const DataLayout *DL,
01407                               const TargetLibraryInfo *TLI,
01408                               const DominatorTree *DT) {
01409   return ::SimplifyLShrInst(Op0, Op1, isExact, Query (DL, TLI, DT),
01410                             RecursionLimit);
01411 }
01412 
01413 /// SimplifyAShrInst - Given operands for an AShr, see if we can
01414 /// fold the result.  If not, this returns null.
01415 static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
01416                                const Query &Q, unsigned MaxRecurse) {
01417   if (Value *V = SimplifyShift(Instruction::AShr, Op0, Op1, Q, MaxRecurse))
01418     return V;
01419 
01420   // X >> X -> 0
01421   if (Op0 == Op1)
01422     return Constant::getNullValue(Op0->getType());
01423 
01424   // all ones >>a X -> all ones
01425   if (match(Op0, m_AllOnes()))
01426     return Op0;
01427 
01428   // undef >>a X -> all ones
01429   if (match(Op0, m_Undef()))
01430     return Constant::getAllOnesValue(Op0->getType());
01431 
01432   // (X << A) >> A -> X
01433   Value *X;
01434   if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) &&
01435       cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap())
01436     return X;
01437 
01438   return nullptr;
01439 }
01440 
01441 Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
01442                               const DataLayout *DL,
01443                               const TargetLibraryInfo *TLI,
01444                               const DominatorTree *DT) {
01445   return ::SimplifyAShrInst(Op0, Op1, isExact, Query (DL, TLI, DT),
01446                             RecursionLimit);
01447 }
01448 
01449 /// SimplifyAndInst - Given operands for an And, see if we can
01450 /// fold the result.  If not, this returns null.
01451 static Value *SimplifyAndInst(Value *Op0, Value *Op1, const Query &Q,
01452                               unsigned MaxRecurse) {
01453   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
01454     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
01455       Constant *Ops[] = { CLHS, CRHS };
01456       return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
01457                                       Ops, Q.DL, Q.TLI);
01458     }
01459 
01460     // Canonicalize the constant to the RHS.
01461     std::swap(Op0, Op1);
01462   }
01463 
01464   // X & undef -> 0
01465   if (match(Op1, m_Undef()))
01466     return Constant::getNullValue(Op0->getType());
01467 
01468   // X & X = X
01469   if (Op0 == Op1)
01470     return Op0;
01471 
01472   // X & 0 = 0
01473   if (match(Op1, m_Zero()))
01474     return Op1;
01475 
01476   // X & -1 = X
01477   if (match(Op1, m_AllOnes()))
01478     return Op0;
01479 
01480   // A & ~A  =  ~A & A  =  0
01481   if (match(Op0, m_Not(m_Specific(Op1))) ||
01482       match(Op1, m_Not(m_Specific(Op0))))
01483     return Constant::getNullValue(Op0->getType());
01484 
01485   // (A | ?) & A = A
01486   Value *A = nullptr, *B = nullptr;
01487   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
01488       (A == Op1 || B == Op1))
01489     return Op1;
01490 
01491   // A & (A | ?) = A
01492   if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
01493       (A == Op0 || B == Op0))
01494     return Op0;
01495 
01496   // A & (-A) = A if A is a power of two or zero.
01497   if (match(Op0, m_Neg(m_Specific(Op1))) ||
01498       match(Op1, m_Neg(m_Specific(Op0)))) {
01499     if (isKnownToBeAPowerOfTwo(Op0, /*OrZero*/true))
01500       return Op0;
01501     if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/true))
01502       return Op1;
01503   }
01504 
01505   // Try some generic simplifications for associative operations.
01506   if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q,
01507                                           MaxRecurse))
01508     return V;
01509 
01510   // And distributes over Or.  Try some generic simplifications based on this.
01511   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
01512                              Q, MaxRecurse))
01513     return V;
01514 
01515   // And distributes over Xor.  Try some generic simplifications based on this.
01516   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor,
01517                              Q, MaxRecurse))
01518     return V;
01519 
01520   // Or distributes over And.  Try some generic simplifications based on this.
01521   if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or,
01522                                 Q, MaxRecurse))
01523     return V;
01524 
01525   // If the operation is with the result of a select instruction, check whether
01526   // operating on either branch of the select always yields the same value.
01527   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
01528     if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q,
01529                                          MaxRecurse))
01530       return V;
01531 
01532   // If the operation is with the result of a phi instruction, check whether
01533   // operating on all incoming values of the phi always yields the same value.
01534   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
01535     if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q,
01536                                       MaxRecurse))
01537       return V;
01538 
01539   return nullptr;
01540 }
01541 
01542 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const DataLayout *DL,
01543                              const TargetLibraryInfo *TLI,
01544                              const DominatorTree *DT) {
01545   return ::SimplifyAndInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit);
01546 }
01547 
01548 /// SimplifyOrInst - Given operands for an Or, see if we can
01549 /// fold the result.  If not, this returns null.
01550 static Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q,
01551                              unsigned MaxRecurse) {
01552   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
01553     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
01554       Constant *Ops[] = { CLHS, CRHS };
01555       return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
01556                                       Ops, Q.DL, Q.TLI);
01557     }
01558 
01559     // Canonicalize the constant to the RHS.
01560     std::swap(Op0, Op1);
01561   }
01562 
01563   // X | undef -> -1
01564   if (match(Op1, m_Undef()))
01565     return Constant::getAllOnesValue(Op0->getType());
01566 
01567   // X | X = X
01568   if (Op0 == Op1)
01569     return Op0;
01570 
01571   // X | 0 = X
01572   if (match(Op1, m_Zero()))
01573     return Op0;
01574 
01575   // X | -1 = -1
01576   if (match(Op1, m_AllOnes()))
01577     return Op1;
01578 
01579   // A | ~A  =  ~A | A  =  -1
01580   if (match(Op0, m_Not(m_Specific(Op1))) ||
01581       match(Op1, m_Not(m_Specific(Op0))))
01582     return Constant::getAllOnesValue(Op0->getType());
01583 
01584   // (A & ?) | A = A
01585   Value *A = nullptr, *B = nullptr;
01586   if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
01587       (A == Op1 || B == Op1))
01588     return Op1;
01589 
01590   // A | (A & ?) = A
01591   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
01592       (A == Op0 || B == Op0))
01593     return Op0;
01594 
01595   // ~(A & ?) | A = -1
01596   if (match(Op0, m_Not(m_And(m_Value(A), m_Value(B)))) &&
01597       (A == Op1 || B == Op1))
01598     return Constant::getAllOnesValue(Op1->getType());
01599 
01600   // A | ~(A & ?) = -1
01601   if (match(Op1, m_Not(m_And(m_Value(A), m_Value(B)))) &&
01602       (A == Op0 || B == Op0))
01603     return Constant::getAllOnesValue(Op0->getType());
01604 
01605   // Try some generic simplifications for associative operations.
01606   if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q,
01607                                           MaxRecurse))
01608     return V;
01609 
01610   // Or distributes over And.  Try some generic simplifications based on this.
01611   if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q,
01612                              MaxRecurse))
01613     return V;
01614 
01615   // And distributes over Or.  Try some generic simplifications based on this.
01616   if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And,
01617                                 Q, MaxRecurse))
01618     return V;
01619 
01620   // If the operation is with the result of a select instruction, check whether
01621   // operating on either branch of the select always yields the same value.
01622   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
01623     if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q,
01624                                          MaxRecurse))
01625       return V;
01626 
01627   // If the operation is with the result of a phi instruction, check whether
01628   // operating on all incoming values of the phi always yields the same value.
01629   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
01630     if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse))
01631       return V;
01632 
01633   return nullptr;
01634 }
01635 
01636 Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const DataLayout *DL,
01637                             const TargetLibraryInfo *TLI,
01638                             const DominatorTree *DT) {
01639   return ::SimplifyOrInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit);
01640 }
01641 
01642 /// SimplifyXorInst - Given operands for a Xor, see if we can
01643 /// fold the result.  If not, this returns null.
01644 static Value *SimplifyXorInst(Value *Op0, Value *Op1, const Query &Q,
01645                               unsigned MaxRecurse) {
01646   if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
01647     if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
01648       Constant *Ops[] = { CLHS, CRHS };
01649       return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(),
01650                                       Ops, Q.DL, Q.TLI);
01651     }
01652 
01653     // Canonicalize the constant to the RHS.
01654     std::swap(Op0, Op1);
01655   }
01656 
01657   // A ^ undef -> undef
01658   if (match(Op1, m_Undef()))
01659     return Op1;
01660 
01661   // A ^ 0 = A
01662   if (match(Op1, m_Zero()))
01663     return Op0;
01664 
01665   // A ^ A = 0
01666   if (Op0 == Op1)
01667     return Constant::getNullValue(Op0->getType());
01668 
01669   // A ^ ~A  =  ~A ^ A  =  -1
01670   if (match(Op0, m_Not(m_Specific(Op1))) ||
01671       match(Op1, m_Not(m_Specific(Op0))))
01672     return Constant::getAllOnesValue(Op0->getType());
01673 
01674   // Try some generic simplifications for associative operations.
01675   if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q,
01676                                           MaxRecurse))
01677     return V;
01678 
01679   // And distributes over Xor.  Try some generic simplifications based on this.
01680   if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And,
01681                                 Q, MaxRecurse))
01682     return V;
01683 
01684   // Threading Xor over selects and phi nodes is pointless, so don't bother.
01685   // Threading over the select in "A ^ select(cond, B, C)" means evaluating
01686   // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
01687   // only if B and C are equal.  If B and C are equal then (since we assume
01688   // that operands have already been simplified) "select(cond, B, C)" should
01689   // have been simplified to the common value of B and C already.  Analysing
01690   // "A^B" and "A^C" thus gains nothing, but costs compile time.  Similarly
01691   // for threading over phi nodes.
01692 
01693   return nullptr;
01694 }
01695 
01696 Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const DataLayout *DL,
01697                              const TargetLibraryInfo *TLI,
01698                              const DominatorTree *DT) {
01699   return ::SimplifyXorInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit);
01700 }
01701 
01702 static Type *GetCompareTy(Value *Op) {
01703   return CmpInst::makeCmpResultType(Op->getType());
01704 }
01705 
01706 /// ExtractEquivalentCondition - Rummage around inside V looking for something
01707 /// equivalent to the comparison "LHS Pred RHS".  Return such a value if found,
01708 /// otherwise return null.  Helper function for analyzing max/min idioms.
01709 static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred,
01710                                          Value *LHS, Value *RHS) {
01711   SelectInst *SI = dyn_cast<SelectInst>(V);
01712   if (!SI)
01713     return nullptr;
01714   CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
01715   if (!Cmp)
01716     return nullptr;
01717   Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1);
01718   if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS)
01719     return Cmp;
01720   if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) &&
01721       LHS == CmpRHS && RHS == CmpLHS)
01722     return Cmp;
01723   return nullptr;
01724 }
01725 
01726 // A significant optimization not implemented here is assuming that alloca
01727 // addresses are not equal to incoming argument values. They don't *alias*,
01728 // as we say, but that doesn't mean they aren't equal, so we take a
01729 // conservative approach.
01730 //
01731 // This is inspired in part by C++11 5.10p1:
01732 //   "Two pointers of the same type compare equal if and only if they are both
01733 //    null, both point to the same function, or both represent the same
01734 //    address."
01735 //
01736 // This is pretty permissive.
01737 //
01738 // It's also partly due to C11 6.5.9p6:
01739 //   "Two pointers compare equal if and only if both are null pointers, both are
01740 //    pointers to the same object (including a pointer to an object and a
01741 //    subobject at its beginning) or function, both are pointers to one past the
01742 //    last element of the same array object, or one is a pointer to one past the
01743 //    end of one array object and the other is a pointer to the start of a
01744 //    different array object that happens to immediately follow the first array
01745 //    object in the address space.)
01746 //
01747 // C11's version is more restrictive, however there's no reason why an argument
01748 // couldn't be a one-past-the-end value for a stack object in the caller and be
01749 // equal to the beginning of a stack object in the callee.
01750 //
01751 // If the C and C++ standards are ever made sufficiently restrictive in this
01752 // area, it may be possible to update LLVM's semantics accordingly and reinstate
01753 // this optimization.
01754 static Constant *computePointerICmp(const DataLayout *DL,
01755                                     const TargetLibraryInfo *TLI,
01756                                     CmpInst::Predicate Pred,
01757                                     Value *LHS, Value *RHS) {
01758   // First, skip past any trivial no-ops.
01759   LHS = LHS->stripPointerCasts();
01760   RHS = RHS->stripPointerCasts();
01761 
01762   // A non-null pointer is not equal to a null pointer.
01763   if (llvm::isKnownNonNull(LHS, TLI) && isa<ConstantPointerNull>(RHS) &&
01764       (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE))
01765     return ConstantInt::get(GetCompareTy(LHS),
01766                             !CmpInst::isTrueWhenEqual(Pred));
01767 
01768   // We can only fold certain predicates on pointer comparisons.
01769   switch (Pred) {
01770   default:
01771     return nullptr;
01772 
01773     // Equality comaprisons are easy to fold.
01774   case CmpInst::ICMP_EQ:
01775   case CmpInst::ICMP_NE:
01776     break;
01777 
01778     // We can only handle unsigned relational comparisons because 'inbounds' on
01779     // a GEP only protects against unsigned wrapping.
01780   case CmpInst::ICMP_UGT:
01781   case CmpInst::ICMP_UGE:
01782   case CmpInst::ICMP_ULT:
01783   case CmpInst::ICMP_ULE:
01784     // However, we have to switch them to their signed variants to handle
01785     // negative indices from the base pointer.
01786     Pred = ICmpInst::getSignedPredicate(Pred);
01787     break;
01788   }
01789 
01790   // Strip off any constant offsets so that we can reason about them.
01791   // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets
01792   // here and compare base addresses like AliasAnalysis does, however there are
01793   // numerous hazards. AliasAnalysis and its utilities rely on special rules
01794   // governing loads and stores which don't apply to icmps. Also, AliasAnalysis
01795   // doesn't need to guarantee pointer inequality when it says NoAlias.
01796   Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
01797   Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
01798 
01799   // If LHS and RHS are related via constant offsets to the same base
01800   // value, we can replace it with an icmp which just compares the offsets.
01801   if (LHS == RHS)
01802     return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset);
01803 
01804   // Various optimizations for (in)equality comparisons.
01805   if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) {
01806     // Different non-empty allocations that exist at the same time have
01807     // different addresses (if the program can tell). Global variables always
01808     // exist, so they always exist during the lifetime of each other and all
01809     // allocas. Two different allocas usually have different addresses...
01810     //
01811     // However, if there's an @llvm.stackrestore dynamically in between two
01812     // allocas, they may have the same address. It's tempting to reduce the
01813     // scope of the problem by only looking at *static* allocas here. That would
01814     // cover the majority of allocas while significantly reducing the likelihood
01815     // of having an @llvm.stackrestore pop up in the middle. However, it's not
01816     // actually impossible for an @llvm.stackrestore to pop up in the middle of
01817     // an entry block. Also, if we have a block that's not attached to a
01818     // function, we can't tell if it's "static" under the current definition.
01819     // Theoretically, this problem could be fixed by creating a new kind of
01820     // instruction kind specifically for static allocas. Such a new instruction
01821     // could be required to be at the top of the entry block, thus preventing it
01822     // from being subject to a @llvm.stackrestore. Instcombine could even
01823     // convert regular allocas into these special allocas. It'd be nifty.
01824     // However, until then, this problem remains open.
01825     //
01826     // So, we'll assume that two non-empty allocas have different addresses
01827     // for now.
01828     //
01829     // With all that, if the offsets are within the bounds of their allocations
01830     // (and not one-past-the-end! so we can't use inbounds!), and their
01831     // allocations aren't the same, the pointers are not equal.
01832     //
01833     // Note that it's not necessary to check for LHS being a global variable
01834     // address, due to canonicalization and constant folding.
01835     if (isa<AllocaInst>(LHS) &&
01836         (isa<AllocaInst>(RHS) || isa<GlobalVariable>(RHS))) {
01837       ConstantInt *LHSOffsetCI = dyn_cast<ConstantInt>(LHSOffset);
01838       ConstantInt *RHSOffsetCI = dyn_cast<ConstantInt>(RHSOffset);
01839       uint64_t LHSSize, RHSSize;
01840       if (LHSOffsetCI && RHSOffsetCI &&
01841           getObjectSize(LHS, LHSSize, DL, TLI) &&
01842           getObjectSize(RHS, RHSSize, DL, TLI)) {
01843         const APInt &LHSOffsetValue = LHSOffsetCI->getValue();
01844         const APInt &RHSOffsetValue = RHSOffsetCI->getValue();
01845         if (!LHSOffsetValue.isNegative() &&
01846             !RHSOffsetValue.isNegative() &&
01847             LHSOffsetValue.ult(LHSSize) &&
01848             RHSOffsetValue.ult(RHSSize)) {
01849           return ConstantInt::get(GetCompareTy(LHS),
01850                                   !CmpInst::isTrueWhenEqual(Pred));
01851         }
01852       }
01853 
01854       // Repeat the above check but this time without depending on DataLayout
01855       // or being able to compute a precise size.
01856       if (!cast<PointerType>(LHS->getType())->isEmptyTy() &&
01857           !cast<PointerType>(RHS->getType())->isEmptyTy() &&
01858           LHSOffset->isNullValue() &&
01859           RHSOffset->isNullValue())
01860         return ConstantInt::get(GetCompareTy(LHS),
01861                                 !CmpInst::isTrueWhenEqual(Pred));
01862     }
01863 
01864     // Even if an non-inbounds GEP occurs along the path we can still optimize
01865     // equality comparisons concerning the result. We avoid walking the whole
01866     // chain again by starting where the last calls to
01867     // stripAndComputeConstantOffsets left off and accumulate the offsets.
01868     Constant *LHSNoBound = stripAndComputeConstantOffsets(DL, LHS, true);
01869     Constant *RHSNoBound = stripAndComputeConstantOffsets(DL, RHS, true);
01870     if (LHS == RHS)
01871       return ConstantExpr::getICmp(Pred,
01872                                    ConstantExpr::getAdd(LHSOffset, LHSNoBound),
01873                                    ConstantExpr::getAdd(RHSOffset, RHSNoBound));
01874   }
01875 
01876   // Otherwise, fail.
01877   return nullptr;
01878 }
01879 
01880 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
01881 /// fold the result.  If not, this returns null.
01882 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
01883                                const Query &Q, unsigned MaxRecurse) {
01884   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
01885   assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
01886 
01887   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
01888     if (Constant *CRHS = dyn_cast<Constant>(RHS))
01889       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
01890 
01891     // If we have a constant, make sure it is on the RHS.
01892     std::swap(LHS, RHS);
01893     Pred = CmpInst::getSwappedPredicate(Pred);
01894   }
01895 
01896   Type *ITy = GetCompareTy(LHS); // The return type.
01897   Type *OpTy = LHS->getType();   // The operand type.
01898 
01899   // icmp X, X -> true/false
01900   // X icmp undef -> true/false.  For example, icmp ugt %X, undef -> false
01901   // because X could be 0.
01902   if (LHS == RHS || isa<UndefValue>(RHS))
01903     return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
01904 
01905   // Special case logic when the operands have i1 type.
01906   if (OpTy->getScalarType()->isIntegerTy(1)) {
01907     switch (Pred) {
01908     default: break;
01909     case ICmpInst::ICMP_EQ:
01910       // X == 1 -> X
01911       if (match(RHS, m_One()))
01912         return LHS;
01913       break;
01914     case ICmpInst::ICMP_NE:
01915       // X != 0 -> X
01916       if (match(RHS, m_Zero()))
01917         return LHS;
01918       break;
01919     case ICmpInst::ICMP_UGT:
01920       // X >u 0 -> X
01921       if (match(RHS, m_Zero()))
01922         return LHS;
01923       break;
01924     case ICmpInst::ICMP_UGE:
01925       // X >=u 1 -> X
01926       if (match(RHS, m_One()))
01927         return LHS;
01928       break;
01929     case ICmpInst::ICMP_SLT:
01930       // X <s 0 -> X
01931       if (match(RHS, m_Zero()))
01932         return LHS;
01933       break;
01934     case ICmpInst::ICMP_SLE:
01935       // X <=s -1 -> X
01936       if (match(RHS, m_One()))
01937         return LHS;
01938       break;
01939     }
01940   }
01941 
01942   // If we are comparing with zero then try hard since this is a common case.
01943   if (match(RHS, m_Zero())) {
01944     bool LHSKnownNonNegative, LHSKnownNegative;
01945     switch (Pred) {
01946     default: llvm_unreachable("Unknown ICmp predicate!");
01947     case ICmpInst::ICMP_ULT:
01948       return getFalse(ITy);
01949     case ICmpInst::ICMP_UGE:
01950       return getTrue(ITy);
01951     case ICmpInst::ICMP_EQ:
01952     case ICmpInst::ICMP_ULE:
01953       if (isKnownNonZero(LHS, Q.DL))
01954         return getFalse(ITy);
01955       break;
01956     case ICmpInst::ICMP_NE:
01957     case ICmpInst::ICMP_UGT:
01958       if (isKnownNonZero(LHS, Q.DL))
01959         return getTrue(ITy);
01960       break;
01961     case ICmpInst::ICMP_SLT:
01962       ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL);
01963       if (LHSKnownNegative)
01964         return getTrue(ITy);
01965       if (LHSKnownNonNegative)
01966         return getFalse(ITy);
01967       break;
01968     case ICmpInst::ICMP_SLE:
01969       ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL);
01970       if (LHSKnownNegative)
01971         return getTrue(ITy);
01972       if (LHSKnownNonNegative && isKnownNonZero(LHS, Q.DL))
01973         return getFalse(ITy);
01974       break;
01975     case ICmpInst::ICMP_SGE:
01976       ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL);
01977       if (LHSKnownNegative)
01978         return getFalse(ITy);
01979       if (LHSKnownNonNegative)
01980         return getTrue(ITy);
01981       break;
01982     case ICmpInst::ICMP_SGT:
01983       ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL);
01984       if (LHSKnownNegative)
01985         return getFalse(ITy);
01986       if (LHSKnownNonNegative && isKnownNonZero(LHS, Q.DL))
01987         return getTrue(ITy);
01988       break;
01989     }
01990   }
01991 
01992   // See if we are doing a comparison with a constant integer.
01993   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
01994     // Rule out tautological comparisons (eg., ult 0 or uge 0).
01995     ConstantRange RHS_CR = ICmpInst::makeConstantRange(Pred, CI->getValue());
01996     if (RHS_CR.isEmptySet())
01997       return ConstantInt::getFalse(CI->getContext());
01998     if (RHS_CR.isFullSet())
01999       return ConstantInt::getTrue(CI->getContext());
02000 
02001     // Many binary operators with constant RHS have easy to compute constant
02002     // range.  Use them to check whether the comparison is a tautology.
02003     uint32_t Width = CI->getBitWidth();
02004     APInt Lower = APInt(Width, 0);
02005     APInt Upper = APInt(Width, 0);
02006     ConstantInt *CI2;
02007     if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) {
02008       // 'urem x, CI2' produces [0, CI2).
02009       Upper = CI2->getValue();
02010     } else if (match(LHS, m_SRem(m_Value(), m_ConstantInt(CI2)))) {
02011       // 'srem x, CI2' produces (-|CI2|, |CI2|).
02012       Upper = CI2->getValue().abs();
02013       Lower = (-Upper) + 1;
02014     } else if (match(LHS, m_UDiv(m_ConstantInt(CI2), m_Value()))) {
02015       // 'udiv CI2, x' produces [0, CI2].
02016       Upper = CI2->getValue() + 1;
02017     } else if (match(LHS, m_UDiv(m_Value(), m_ConstantInt(CI2)))) {
02018       // 'udiv x, CI2' produces [0, UINT_MAX / CI2].
02019       APInt NegOne = APInt::getAllOnesValue(Width);
02020       if (!CI2->isZero())
02021         Upper = NegOne.udiv(CI2->getValue()) + 1;
02022     } else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) {
02023       // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2].
02024       APInt IntMin = APInt::getSignedMinValue(Width);
02025       APInt IntMax = APInt::getSignedMaxValue(Width);
02026       APInt Val = CI2->getValue().abs();
02027       if (!Val.isMinValue()) {
02028         Lower = IntMin.sdiv(Val);
02029         Upper = IntMax.sdiv(Val) + 1;
02030       }
02031     } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) {
02032       // 'lshr x, CI2' produces [0, UINT_MAX >> CI2].
02033       APInt NegOne = APInt::getAllOnesValue(Width);
02034       if (CI2->getValue().ult(Width))
02035         Upper = NegOne.lshr(CI2->getValue()) + 1;
02036     } else if (match(LHS, m_AShr(m_Value(), m_ConstantInt(CI2)))) {
02037       // 'ashr x, CI2' produces [INT_MIN >> CI2, INT_MAX >> CI2].
02038       APInt IntMin = APInt::getSignedMinValue(Width);
02039       APInt IntMax = APInt::getSignedMaxValue(Width);
02040       if (CI2->getValue().ult(Width)) {
02041         Lower = IntMin.ashr(CI2->getValue());
02042         Upper = IntMax.ashr(CI2->getValue()) + 1;
02043       }
02044     } else if (match(LHS, m_Or(m_Value(), m_ConstantInt(CI2)))) {
02045       // 'or x, CI2' produces [CI2, UINT_MAX].
02046       Lower = CI2->getValue();
02047     } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) {
02048       // 'and x, CI2' produces [0, CI2].
02049       Upper = CI2->getValue() + 1;
02050     }
02051     if (Lower != Upper) {
02052       ConstantRange LHS_CR = ConstantRange(Lower, Upper);
02053       if (RHS_CR.contains(LHS_CR))
02054         return ConstantInt::getTrue(RHS->getContext());
02055       if (RHS_CR.inverse().contains(LHS_CR))
02056         return ConstantInt::getFalse(RHS->getContext());
02057     }
02058   }
02059 
02060   // Compare of cast, for example (zext X) != 0 -> X != 0
02061   if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) {
02062     Instruction *LI = cast<CastInst>(LHS);
02063     Value *SrcOp = LI->getOperand(0);
02064     Type *SrcTy = SrcOp->getType();
02065     Type *DstTy = LI->getType();
02066 
02067     // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input
02068     // if the integer type is the same size as the pointer type.
02069     if (MaxRecurse && Q.DL && isa<PtrToIntInst>(LI) &&
02070         Q.DL->getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) {
02071       if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
02072         // Transfer the cast to the constant.
02073         if (Value *V = SimplifyICmpInst(Pred, SrcOp,
02074                                         ConstantExpr::getIntToPtr(RHSC, SrcTy),
02075                                         Q, MaxRecurse-1))
02076           return V;
02077       } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) {
02078         if (RI->getOperand(0)->getType() == SrcTy)
02079           // Compare without the cast.
02080           if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
02081                                           Q, MaxRecurse-1))
02082             return V;
02083       }
02084     }
02085 
02086     if (isa<ZExtInst>(LHS)) {
02087       // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the
02088       // same type.
02089       if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
02090         if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
02091           // Compare X and Y.  Note that signed predicates become unsigned.
02092           if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
02093                                           SrcOp, RI->getOperand(0), Q,
02094                                           MaxRecurse-1))
02095             return V;
02096       }
02097       // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended
02098       // too.  If not, then try to deduce the result of the comparison.
02099       else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
02100         // Compute the constant that would happen if we truncated to SrcTy then
02101         // reextended to DstTy.
02102         Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
02103         Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy);
02104 
02105         // If the re-extended constant didn't change then this is effectively
02106         // also a case of comparing two zero-extended values.
02107         if (RExt == CI && MaxRecurse)
02108           if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
02109                                         SrcOp, Trunc, Q, MaxRecurse-1))
02110             return V;
02111 
02112         // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit
02113         // there.  Use this to work out the result of the comparison.
02114         if (RExt != CI) {
02115           switch (Pred) {
02116           default: llvm_unreachable("Unknown ICmp predicate!");
02117           // LHS <u RHS.
02118           case ICmpInst::ICMP_EQ:
02119           case ICmpInst::ICMP_UGT:
02120           case ICmpInst::ICMP_UGE:
02121             return ConstantInt::getFalse(CI->getContext());
02122 
02123           case ICmpInst::ICMP_NE:
02124           case ICmpInst::ICMP_ULT:
02125           case ICmpInst::ICMP_ULE:
02126             return ConstantInt::getTrue(CI->getContext());
02127 
02128           // LHS is non-negative.  If RHS is negative then LHS >s LHS.  If RHS
02129           // is non-negative then LHS <s RHS.
02130           case ICmpInst::ICMP_SGT:
02131           case ICmpInst::ICMP_SGE:
02132             return CI->getValue().isNegative() ?
02133               ConstantInt::getTrue(CI->getContext()) :
02134               ConstantInt::getFalse(CI->getContext());
02135 
02136           case ICmpInst::ICMP_SLT:
02137           case ICmpInst::ICMP_SLE:
02138             return CI->getValue().isNegative() ?
02139               ConstantInt::getFalse(CI->getContext()) :
02140               ConstantInt::getTrue(CI->getContext());
02141           }
02142         }
02143       }
02144     }
02145 
02146     if (isa<SExtInst>(LHS)) {
02147       // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the
02148       // same type.
02149       if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
02150         if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
02151           // Compare X and Y.  Note that the predicate does not change.
02152           if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
02153                                           Q, MaxRecurse-1))
02154             return V;
02155       }
02156       // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended
02157       // too.  If not, then try to deduce the result of the comparison.
02158       else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
02159         // Compute the constant that would happen if we truncated to SrcTy then
02160         // reextended to DstTy.
02161         Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
02162         Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy);
02163 
02164         // If the re-extended constant didn't change then this is effectively
02165         // also a case of comparing two sign-extended values.
02166         if (RExt == CI && MaxRecurse)
02167           if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse-1))
02168             return V;
02169 
02170         // Otherwise the upper bits of LHS are all equal, while RHS has varying
02171         // bits there.  Use this to work out the result of the comparison.
02172         if (RExt != CI) {
02173           switch (Pred) {
02174           default: llvm_unreachable("Unknown ICmp predicate!");
02175           case ICmpInst::ICMP_EQ:
02176             return ConstantInt::getFalse(CI->getContext());
02177           case ICmpInst::ICMP_NE:
02178             return ConstantInt::getTrue(CI->getContext());
02179 
02180           // If RHS is non-negative then LHS <s RHS.  If RHS is negative then
02181           // LHS >s RHS.
02182           case ICmpInst::ICMP_SGT:
02183           case ICmpInst::ICMP_SGE:
02184             return CI->getValue().isNegative() ?
02185               ConstantInt::getTrue(CI->getContext()) :
02186               ConstantInt::getFalse(CI->getContext());
02187           case ICmpInst::ICMP_SLT:
02188           case ICmpInst::ICMP_SLE:
02189             return CI->getValue().isNegative() ?
02190               ConstantInt::getFalse(CI->getContext()) :
02191               ConstantInt::getTrue(CI->getContext());
02192 
02193           // If LHS is non-negative then LHS <u RHS.  If LHS is negative then
02194           // LHS >u RHS.
02195           case ICmpInst::ICMP_UGT:
02196           case ICmpInst::ICMP_UGE:
02197             // Comparison is true iff the LHS <s 0.
02198             if (MaxRecurse)
02199               if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp,
02200                                               Constant::getNullValue(SrcTy),
02201                                               Q, MaxRecurse-1))
02202                 return V;
02203             break;
02204           case ICmpInst::ICMP_ULT:
02205           case ICmpInst::ICMP_ULE:
02206             // Comparison is true iff the LHS >=s 0.
02207             if (MaxRecurse)
02208               if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp,
02209                                               Constant::getNullValue(SrcTy),
02210                                               Q, MaxRecurse-1))
02211                 return V;
02212             break;
02213           }
02214         }
02215       }
02216     }
02217   }
02218 
02219   // Special logic for binary operators.
02220   BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS);
02221   BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS);
02222   if (MaxRecurse && (LBO || RBO)) {
02223     // Analyze the case when either LHS or RHS is an add instruction.
02224     Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
02225     // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null).
02226     bool NoLHSWrapProblem = false, NoRHSWrapProblem = false;
02227     if (LBO && LBO->getOpcode() == Instruction::Add) {
02228       A = LBO->getOperand(0); B = LBO->getOperand(1);
02229       NoLHSWrapProblem = ICmpInst::isEquality(Pred) ||
02230         (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) ||
02231         (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap());
02232     }
02233     if (RBO && RBO->getOpcode() == Instruction::Add) {
02234       C = RBO->getOperand(0); D = RBO->getOperand(1);
02235       NoRHSWrapProblem = ICmpInst::isEquality(Pred) ||
02236         (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) ||
02237         (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap());
02238     }
02239 
02240     // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow.
02241     if ((A == RHS || B == RHS) && NoLHSWrapProblem)
02242       if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A,
02243                                       Constant::getNullValue(RHS->getType()),
02244                                       Q, MaxRecurse-1))
02245         return V;
02246 
02247     // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow.
02248     if ((C == LHS || D == LHS) && NoRHSWrapProblem)
02249       if (Value *V = SimplifyICmpInst(Pred,
02250                                       Constant::getNullValue(LHS->getType()),
02251                                       C == LHS ? D : C, Q, MaxRecurse-1))
02252         return V;
02253 
02254     // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow.
02255     if (A && C && (A == C || A == D || B == C || B == D) &&
02256         NoLHSWrapProblem && NoRHSWrapProblem) {
02257       // Determine Y and Z in the form icmp (X+Y), (X+Z).
02258       Value *Y, *Z;
02259       if (A == C) {
02260         // C + B == C + D  ->  B == D
02261         Y = B;
02262         Z = D;
02263       } else if (A == D) {
02264         // D + B == C + D  ->  B == C
02265         Y = B;
02266         Z = C;
02267       } else if (B == C) {
02268         // A + C == C + D  ->  A == D
02269         Y = A;
02270         Z = D;
02271       } else {
02272         assert(B == D);
02273         // A + D == C + D  ->  A == C
02274         Y = A;
02275         Z = C;
02276       }
02277       if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse-1))
02278         return V;
02279     }
02280   }
02281 
02282   // icmp pred (urem X, Y), Y
02283   if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) {
02284     bool KnownNonNegative, KnownNegative;
02285     switch (Pred) {
02286     default:
02287       break;
02288     case ICmpInst::ICMP_SGT:
02289     case ICmpInst::ICMP_SGE:
02290       ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL);
02291       if (!KnownNonNegative)
02292         break;
02293       // fall-through
02294     case ICmpInst::ICMP_EQ:
02295     case ICmpInst::ICMP_UGT:
02296     case ICmpInst::ICMP_UGE:
02297       return getFalse(ITy);
02298     case ICmpInst::ICMP_SLT:
02299     case ICmpInst::ICMP_SLE:
02300       ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL);
02301       if (!KnownNonNegative)
02302         break;
02303       // fall-through
02304     case ICmpInst::ICMP_NE:
02305     case ICmpInst::ICMP_ULT:
02306     case ICmpInst::ICMP_ULE:
02307       return getTrue(ITy);
02308     }
02309   }
02310 
02311   // icmp pred X, (urem Y, X)
02312   if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) {
02313     bool KnownNonNegative, KnownNegative;
02314     switch (Pred) {
02315     default:
02316       break;
02317     case ICmpInst::ICMP_SGT:
02318     case ICmpInst::ICMP_SGE:
02319       ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL);
02320       if (!KnownNonNegative)
02321         break;
02322       // fall-through
02323     case ICmpInst::ICMP_NE:
02324     case ICmpInst::ICMP_UGT:
02325     case ICmpInst::ICMP_UGE:
02326       return getTrue(ITy);
02327     case ICmpInst::ICMP_SLT:
02328     case ICmpInst::ICMP_SLE:
02329       ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL);
02330       if (!KnownNonNegative)
02331         break;
02332       // fall-through
02333     case ICmpInst::ICMP_EQ:
02334     case ICmpInst::ICMP_ULT:
02335     case ICmpInst::ICMP_ULE:
02336       return getFalse(ITy);
02337     }
02338   }
02339 
02340   // x udiv y <=u x.
02341   if (LBO && match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) {
02342     // icmp pred (X /u Y), X
02343     if (Pred == ICmpInst::ICMP_UGT)
02344       return getFalse(ITy);
02345     if (Pred == ICmpInst::ICMP_ULE)
02346       return getTrue(ITy);
02347   }
02348 
02349   if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() &&
02350       LBO->getOperand(1) == RBO->getOperand(1)) {
02351     switch (LBO->getOpcode()) {
02352     default: break;
02353     case Instruction::UDiv:
02354     case Instruction::LShr:
02355       if (ICmpInst::isSigned(Pred))
02356         break;
02357       // fall-through
02358     case Instruction::SDiv:
02359     case Instruction::AShr:
02360       if (!LBO->isExact() || !RBO->isExact())
02361         break;
02362       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
02363                                       RBO->getOperand(0), Q, MaxRecurse-1))
02364         return V;
02365       break;
02366     case Instruction::Shl: {
02367       bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap();
02368       bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap();
02369       if (!NUW && !NSW)
02370         break;
02371       if (!NSW && ICmpInst::isSigned(Pred))
02372         break;
02373       if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
02374                                       RBO->getOperand(0), Q, MaxRecurse-1))
02375         return V;
02376       break;
02377     }
02378     }
02379   }
02380 
02381   // Simplify comparisons involving max/min.
02382   Value *A, *B;
02383   CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE;
02384   CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B".
02385 
02386   // Signed variants on "max(a,b)>=a -> true".
02387   if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
02388     if (A != RHS) std::swap(A, B); // smax(A, B) pred A.
02389     EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
02390     // We analyze this as smax(A, B) pred A.
02391     P = Pred;
02392   } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) &&
02393              (A == LHS || B == LHS)) {
02394     if (A != LHS) std::swap(A, B); // A pred smax(A, B).
02395     EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
02396     // We analyze this as smax(A, B) swapped-pred A.
02397     P = CmpInst::getSwappedPredicate(Pred);
02398   } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
02399              (A == RHS || B == RHS)) {
02400     if (A != RHS) std::swap(A, B); // smin(A, B) pred A.
02401     EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
02402     // We analyze this as smax(-A, -B) swapped-pred -A.
02403     // Note that we do not need to actually form -A or -B thanks to EqP.
02404     P = CmpInst::getSwappedPredicate(Pred);
02405   } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) &&
02406              (A == LHS || B == LHS)) {
02407     if (A != LHS) std::swap(A, B); // A pred smin(A, B).
02408     EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
02409     // We analyze this as smax(-A, -B) pred -A.
02410     // Note that we do not need to actually form -A or -B thanks to EqP.
02411     P = Pred;
02412   }
02413   if (P != CmpInst::BAD_ICMP_PREDICATE) {
02414     // Cases correspond to "max(A, B) p A".
02415     switch (P) {
02416     default:
02417       break;
02418     case CmpInst::ICMP_EQ:
02419     case CmpInst::ICMP_SLE:
02420       // Equivalent to "A EqP B".  This may be the same as the condition tested
02421       // in the max/min; if so, we can just return that.
02422       if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
02423         return V;
02424       if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
02425         return V;
02426       // Otherwise, see if "A EqP B" simplifies.
02427       if (MaxRecurse)
02428         if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1))
02429           return V;
02430       break;
02431     case CmpInst::ICMP_NE:
02432     case CmpInst::ICMP_SGT: {
02433       CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
02434       // Equivalent to "A InvEqP B".  This may be the same as the condition
02435       // tested in the max/min; if so, we can just return that.
02436       if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
02437         return V;
02438       if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
02439         return V;
02440       // Otherwise, see if "A InvEqP B" simplifies.
02441       if (MaxRecurse)
02442         if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1))
02443           return V;
02444       break;
02445     }
02446     case CmpInst::ICMP_SGE:
02447       // Always true.
02448       return getTrue(ITy);
02449     case CmpInst::ICMP_SLT:
02450       // Always false.
02451       return getFalse(ITy);
02452     }
02453   }
02454 
02455   // Unsigned variants on "max(a,b)>=a -> true".
02456   P = CmpInst::BAD_ICMP_PREDICATE;
02457   if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
02458     if (A != RHS) std::swap(A, B); // umax(A, B) pred A.
02459     EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
02460     // We analyze this as umax(A, B) pred A.
02461     P = Pred;
02462   } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) &&
02463              (A == LHS || B == LHS)) {
02464     if (A != LHS) std::swap(A, B); // A pred umax(A, B).
02465     EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
02466     // We analyze this as umax(A, B) swapped-pred A.
02467     P = CmpInst::getSwappedPredicate(Pred);
02468   } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
02469              (A == RHS || B == RHS)) {
02470     if (A != RHS) std::swap(A, B); // umin(A, B) pred A.
02471     EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
02472     // We analyze this as umax(-A, -B) swapped-pred -A.
02473     // Note that we do not need to actually form -A or -B thanks to EqP.
02474     P = CmpInst::getSwappedPredicate(Pred);
02475   } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) &&
02476              (A == LHS || B == LHS)) {
02477     if (A != LHS) std::swap(A, B); // A pred umin(A, B).
02478     EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
02479     // We analyze this as umax(-A, -B) pred -A.
02480     // Note that we do not need to actually form -A or -B thanks to EqP.
02481     P = Pred;
02482   }
02483   if (P != CmpInst::BAD_ICMP_PREDICATE) {
02484     // Cases correspond to "max(A, B) p A".
02485     switch (P) {
02486     default:
02487       break;
02488     case CmpInst::ICMP_EQ:
02489     case CmpInst::ICMP_ULE:
02490       // Equivalent to "A EqP B".  This may be the same as the condition tested
02491       // in the max/min; if so, we can just return that.
02492       if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
02493         return V;
02494       if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
02495         return V;
02496       // Otherwise, see if "A EqP B" simplifies.
02497       if (MaxRecurse)
02498         if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1))
02499           return V;
02500       break;
02501     case CmpInst::ICMP_NE:
02502     case CmpInst::ICMP_UGT: {
02503       CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
02504       // Equivalent to "A InvEqP B".  This may be the same as the condition
02505       // tested in the max/min; if so, we can just return that.
02506       if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
02507         return V;
02508       if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
02509         return V;
02510       // Otherwise, see if "A InvEqP B" simplifies.
02511       if (MaxRecurse)
02512         if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1))
02513           return V;
02514       break;
02515     }
02516     case CmpInst::ICMP_UGE:
02517       // Always true.
02518       return getTrue(ITy);
02519     case CmpInst::ICMP_ULT:
02520       // Always false.
02521       return getFalse(ITy);
02522     }
02523   }
02524 
02525   // Variants on "max(x,y) >= min(x,z)".
02526   Value *C, *D;
02527   if (match(LHS, m_SMax(m_Value(A), m_Value(B))) &&
02528       match(RHS, m_SMin(m_Value(C), m_Value(D))) &&
02529       (A == C || A == D || B == C || B == D)) {
02530     // max(x, ?) pred min(x, ?).
02531     if (Pred == CmpInst::ICMP_SGE)
02532       // Always true.
02533       return getTrue(ITy);
02534     if (Pred == CmpInst::ICMP_SLT)
02535       // Always false.
02536       return getFalse(ITy);
02537   } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
02538              match(RHS, m_SMax(m_Value(C), m_Value(D))) &&
02539              (A == C || A == D || B == C || B == D)) {
02540     // min(x, ?) pred max(x, ?).
02541     if (Pred == CmpInst::ICMP_SLE)
02542       // Always true.
02543       return getTrue(ITy);
02544     if (Pred == CmpInst::ICMP_SGT)
02545       // Always false.
02546       return getFalse(ITy);
02547   } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) &&
02548              match(RHS, m_UMin(m_Value(C), m_Value(D))) &&
02549              (A == C || A == D || B == C || B == D)) {
02550     // max(x, ?) pred min(x, ?).
02551     if (Pred == CmpInst::ICMP_UGE)
02552       // Always true.
02553       return getTrue(ITy);
02554     if (Pred == CmpInst::ICMP_ULT)
02555       // Always false.
02556       return getFalse(ITy);
02557   } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
02558              match(RHS, m_UMax(m_Value(C), m_Value(D))) &&
02559              (A == C || A == D || B == C || B == D)) {
02560     // min(x, ?) pred max(x, ?).
02561     if (Pred == CmpInst::ICMP_ULE)
02562       // Always true.
02563       return getTrue(ITy);
02564     if (Pred == CmpInst::ICMP_UGT)
02565       // Always false.
02566       return getFalse(ITy);
02567   }
02568 
02569   // Simplify comparisons of related pointers using a powerful, recursive
02570   // GEP-walk when we have target data available..
02571   if (LHS->getType()->isPointerTy())
02572     if (Constant *C = computePointerICmp(Q.DL, Q.TLI, Pred, LHS, RHS))
02573       return C;
02574 
02575   if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) {
02576     if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) {
02577       if (GLHS->getPointerOperand() == GRHS->getPointerOperand() &&
02578           GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() &&
02579           (ICmpInst::isEquality(Pred) ||
02580            (GLHS->isInBounds() && GRHS->isInBounds() &&
02581             Pred == ICmpInst::getSignedPredicate(Pred)))) {
02582         // The bases are equal and the indices are constant.  Build a constant
02583         // expression GEP with the same indices and a null base pointer to see
02584         // what constant folding can make out of it.
02585         Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType());
02586         SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end());
02587         Constant *NewLHS = ConstantExpr::getGetElementPtr(Null, IndicesLHS);
02588 
02589         SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end());
02590         Constant *NewRHS = ConstantExpr::getGetElementPtr(Null, IndicesRHS);
02591         return ConstantExpr::getICmp(Pred, NewLHS, NewRHS);
02592       }
02593     }
02594   }
02595 
02596   // If the comparison is with the result of a select instruction, check whether
02597   // comparing with either branch of the select always yields the same value.
02598   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
02599     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
02600       return V;
02601 
02602   // If the comparison is with the result of a phi instruction, check whether
02603   // doing the compare with each incoming phi value yields a common result.
02604   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
02605     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
02606       return V;
02607 
02608   return nullptr;
02609 }
02610 
02611 Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
02612                               const DataLayout *DL,
02613                               const TargetLibraryInfo *TLI,
02614                               const DominatorTree *DT) {
02615   return ::SimplifyICmpInst(Predicate, LHS, RHS, Query (DL, TLI, DT),
02616                             RecursionLimit);
02617 }
02618 
02619 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
02620 /// fold the result.  If not, this returns null.
02621 static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
02622                                const Query &Q, unsigned MaxRecurse) {
02623   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
02624   assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
02625 
02626   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
02627     if (Constant *CRHS = dyn_cast<Constant>(RHS))
02628       return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
02629 
02630     // If we have a constant, make sure it is on the RHS.
02631     std::swap(LHS, RHS);
02632     Pred = CmpInst::getSwappedPredicate(Pred);
02633   }
02634 
02635   // Fold trivial predicates.
02636   if (Pred == FCmpInst::FCMP_FALSE)
02637     return ConstantInt::get(GetCompareTy(LHS), 0);
02638   if (Pred == FCmpInst::FCMP_TRUE)
02639     return ConstantInt::get(GetCompareTy(LHS), 1);
02640 
02641   if (isa<UndefValue>(RHS))                  // fcmp pred X, undef -> undef
02642     return UndefValue::get(GetCompareTy(LHS));
02643 
02644   // fcmp x,x -> true/false.  Not all compares are foldable.
02645   if (LHS == RHS) {
02646     if (CmpInst::isTrueWhenEqual(Pred))
02647       return ConstantInt::get(GetCompareTy(LHS), 1);
02648     if (CmpInst::isFalseWhenEqual(Pred))
02649       return ConstantInt::get(GetCompareTy(LHS), 0);
02650   }
02651 
02652   // Handle fcmp with constant RHS
02653   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
02654     // If the constant is a nan, see if we can fold the comparison based on it.
02655     if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
02656       if (CFP->getValueAPF().isNaN()) {
02657         if (FCmpInst::isOrdered(Pred))   // True "if ordered and foo"
02658           return ConstantInt::getFalse(CFP->getContext());
02659         assert(FCmpInst::isUnordered(Pred) &&
02660                "Comparison must be either ordered or unordered!");
02661         // True if unordered.
02662         return ConstantInt::getTrue(CFP->getContext());
02663       }
02664       // Check whether the constant is an infinity.
02665       if (CFP->getValueAPF().isInfinity()) {
02666         if (CFP->getValueAPF().isNegative()) {
02667           switch (Pred) {
02668           case FCmpInst::FCMP_OLT:
02669             // No value is ordered and less than negative infinity.
02670             return ConstantInt::getFalse(CFP->getContext());
02671           case FCmpInst::FCMP_UGE:
02672             // All values are unordered with or at least negative infinity.
02673             return ConstantInt::getTrue(CFP->getContext());
02674           default:
02675             break;
02676           }
02677         } else {
02678           switch (Pred) {
02679           case FCmpInst::FCMP_OGT:
02680             // No value is ordered and greater than infinity.
02681             return ConstantInt::getFalse(CFP->getContext());
02682           case FCmpInst::FCMP_ULE:
02683             // All values are unordered with and at most infinity.
02684             return ConstantInt::getTrue(CFP->getContext());
02685           default:
02686             break;
02687           }
02688         }
02689       }
02690     }
02691   }
02692 
02693   // If the comparison is with the result of a select instruction, check whether
02694   // comparing with either branch of the select always yields the same value.
02695   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
02696     if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
02697       return V;
02698 
02699   // If the comparison is with the result of a phi instruction, check whether
02700   // doing the compare with each incoming phi value yields a common result.
02701   if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
02702     if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
02703       return V;
02704 
02705   return nullptr;
02706 }
02707 
02708 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
02709                               const DataLayout *DL,
02710                               const TargetLibraryInfo *TLI,
02711                               const DominatorTree *DT) {
02712   return ::SimplifyFCmpInst(Predicate, LHS, RHS, Query (DL, TLI, DT),
02713                             RecursionLimit);
02714 }
02715 
02716 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
02717 /// the result.  If not, this returns null.
02718 static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal,
02719                                  Value *FalseVal, const Query &Q,
02720                                  unsigned MaxRecurse) {
02721   // select true, X, Y  -> X
02722   // select false, X, Y -> Y
02723   if (Constant *CB = dyn_cast<Constant>(CondVal)) {
02724     if (CB->isAllOnesValue())
02725       return TrueVal;
02726     if (CB->isNullValue())
02727       return FalseVal;
02728   }
02729 
02730   // select C, X, X -> X
02731   if (TrueVal == FalseVal)
02732     return TrueVal;
02733 
02734   if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
02735     if (isa<Constant>(TrueVal))
02736       return TrueVal;
02737     return FalseVal;
02738   }
02739   if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
02740     return FalseVal;
02741   if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
02742     return TrueVal;
02743 
02744   return nullptr;
02745 }
02746 
02747 Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
02748                                 const DataLayout *DL,
02749                                 const TargetLibraryInfo *TLI,
02750                                 const DominatorTree *DT) {
02751   return ::SimplifySelectInst(Cond, TrueVal, FalseVal, Query (DL, TLI, DT),
02752                               RecursionLimit);
02753 }
02754 
02755 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
02756 /// fold the result.  If not, this returns null.
02757 static Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const Query &Q, unsigned) {
02758   // The type of the GEP pointer operand.
02759   PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()->getScalarType());
02760 
02761   // getelementptr P -> P.
02762   if (Ops.size() == 1)
02763     return Ops[0];
02764 
02765   if (isa<UndefValue>(Ops[0])) {
02766     // Compute the (pointer) type returned by the GEP instruction.
02767     Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, Ops.slice(1));
02768     Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace());
02769     if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType()))
02770       GEPTy = VectorType::get(GEPTy, VT->getNumElements());
02771     return UndefValue::get(GEPTy);
02772   }
02773 
02774   if (Ops.size() == 2) {
02775     // getelementptr P, 0 -> P.
02776     if (match(Ops[1], m_Zero()))
02777       return Ops[0];
02778     // getelementptr P, N -> P if P points to a type of zero size.
02779     if (Q.DL) {
02780       Type *Ty = PtrTy->getElementType();
02781       if (Ty->isSized() && Q.DL->getTypeAllocSize(Ty) == 0)
02782         return Ops[0];
02783     }
02784   }
02785 
02786   // Check to see if this is constant foldable.
02787   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
02788     if (!isa<Constant>(Ops[i]))
02789       return nullptr;
02790 
02791   return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), Ops.slice(1));
02792 }
02793 
02794 Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout *DL,
02795                              const TargetLibraryInfo *TLI,
02796                              const DominatorTree *DT) {
02797   return ::SimplifyGEPInst(Ops, Query (DL, TLI, DT), RecursionLimit);
02798 }
02799 
02800 /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we
02801 /// can fold the result.  If not, this returns null.
02802 static Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
02803                                       ArrayRef<unsigned> Idxs, const Query &Q,
02804                                       unsigned) {
02805   if (Constant *CAgg = dyn_cast<Constant>(Agg))
02806     if (Constant *CVal = dyn_cast<Constant>(Val))
02807       return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs);
02808 
02809   // insertvalue x, undef, n -> x
02810   if (match(Val, m_Undef()))
02811     return Agg;
02812 
02813   // insertvalue x, (extractvalue y, n), n
02814   if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val))
02815     if (EV->getAggregateOperand()->getType() == Agg->getType() &&
02816         EV->getIndices() == Idxs) {
02817       // insertvalue undef, (extractvalue y, n), n -> y
02818       if (match(Agg, m_Undef()))
02819         return EV->getAggregateOperand();
02820 
02821       // insertvalue y, (extractvalue y, n), n -> y
02822       if (Agg == EV->getAggregateOperand())
02823         return Agg;
02824     }
02825 
02826   return nullptr;
02827 }
02828 
02829 Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val,
02830                                      ArrayRef<unsigned> Idxs,
02831                                      const DataLayout *DL,
02832                                      const TargetLibraryInfo *TLI,
02833                                      const DominatorTree *DT) {
02834   return ::SimplifyInsertValueInst(Agg, Val, Idxs, Query (DL, TLI, DT),
02835                                    RecursionLimit);
02836 }
02837 
02838 /// SimplifyPHINode - See if we can fold the given phi.  If not, returns null.
02839 static Value *SimplifyPHINode(PHINode *PN, const Query &Q) {
02840   // If all of the PHI's incoming values are the same then replace the PHI node
02841   // with the common value.
02842   Value *CommonValue = nullptr;
02843   bool HasUndefInput = false;
02844   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
02845     Value *Incoming = PN->getIncomingValue(i);
02846     // If the incoming value is the phi node itself, it can safely be skipped.
02847     if (Incoming == PN) continue;
02848     if (isa<UndefValue>(Incoming)) {
02849       // Remember that we saw an undef value, but otherwise ignore them.
02850       HasUndefInput = true;
02851       continue;
02852     }
02853     if (CommonValue && Incoming != CommonValue)
02854       return nullptr;  // Not the same, bail out.
02855     CommonValue = Incoming;
02856   }
02857 
02858   // If CommonValue is null then all of the incoming values were either undef or
02859   // equal to the phi node itself.
02860   if (!CommonValue)
02861     return UndefValue::get(PN->getType());
02862 
02863   // If we have a PHI node like phi(X, undef, X), where X is defined by some
02864   // instruction, we cannot return X as the result of the PHI node unless it
02865   // dominates the PHI block.
02866   if (HasUndefInput)
02867     return ValueDominatesPHI(CommonValue, PN, Q.DT) ? CommonValue : nullptr;
02868 
02869   return CommonValue;
02870 }
02871 
02872 static Value *SimplifyTruncInst(Value *Op, Type *Ty, const Query &Q, unsigned) {
02873   if (Constant *C = dyn_cast<Constant>(Op))
02874     return ConstantFoldInstOperands(Instruction::Trunc, Ty, C, Q.DL, Q.TLI);
02875 
02876   return nullptr;
02877 }
02878 
02879 Value *llvm::SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout *DL,
02880                                const TargetLibraryInfo *TLI,
02881                                const DominatorTree *DT) {
02882   return ::SimplifyTruncInst(Op, Ty, Query (DL, TLI, DT), RecursionLimit);
02883 }
02884 
02885 //=== Helper functions for higher up the class hierarchy.
02886 
02887 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
02888 /// fold the result.  If not, this returns null.
02889 static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
02890                             const Query &Q, unsigned MaxRecurse) {
02891   switch (Opcode) {
02892   case Instruction::Add:
02893     return SimplifyAddInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false,
02894                            Q, MaxRecurse);
02895   case Instruction::FAdd:
02896     return SimplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
02897 
02898   case Instruction::Sub:
02899     return SimplifySubInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false,
02900                            Q, MaxRecurse);
02901   case Instruction::FSub:
02902     return SimplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
02903 
02904   case Instruction::Mul:  return SimplifyMulInst (LHS, RHS, Q, MaxRecurse);
02905   case Instruction::FMul:
02906     return SimplifyFMulInst (LHS, RHS, FastMathFlags(), Q, MaxRecurse);
02907   case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, Q, MaxRecurse);
02908   case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse);
02909   case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, Q, MaxRecurse);
02910   case Instruction::SRem: return SimplifySRemInst(LHS, RHS, Q, MaxRecurse);
02911   case Instruction::URem: return SimplifyURemInst(LHS, RHS, Q, MaxRecurse);
02912   case Instruction::FRem: return SimplifyFRemInst(LHS, RHS, Q, MaxRecurse);
02913   case Instruction::Shl:
02914     return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false,
02915                            Q, MaxRecurse);
02916   case Instruction::LShr:
02917     return SimplifyLShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse);
02918   case Instruction::AShr:
02919     return SimplifyAShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse);
02920   case Instruction::And: return SimplifyAndInst(LHS, RHS, Q, MaxRecurse);
02921   case Instruction::Or:  return SimplifyOrInst (LHS, RHS, Q, MaxRecurse);
02922   case Instruction::Xor: return SimplifyXorInst(LHS, RHS, Q, MaxRecurse);
02923   default:
02924     if (Constant *CLHS = dyn_cast<Constant>(LHS))
02925       if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
02926         Constant *COps[] = {CLHS, CRHS};
02927         return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, Q.DL,
02928                                         Q.TLI);
02929       }
02930 
02931     // If the operation is associative, try some generic simplifications.
02932     if (Instruction::isAssociative(Opcode))
02933       if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, Q, MaxRecurse))
02934         return V;
02935 
02936     // If the operation is with the result of a select instruction check whether
02937     // operating on either branch of the select always yields the same value.
02938     if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
02939       if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, Q, MaxRecurse))
02940         return V;
02941 
02942     // If the operation is with the result of a phi instruction, check whether
02943     // operating on all incoming values of the phi always yields the same value.
02944     if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
02945       if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, Q, MaxRecurse))
02946         return V;
02947 
02948     return nullptr;
02949   }
02950 }
02951 
02952 Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
02953                            const DataLayout *DL, const TargetLibraryInfo *TLI,
02954                            const DominatorTree *DT) {
02955   return ::SimplifyBinOp(Opcode, LHS, RHS, Query (DL, TLI, DT), RecursionLimit);
02956 }
02957 
02958 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
02959 /// fold the result.
02960 static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
02961                               const Query &Q, unsigned MaxRecurse) {
02962   if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
02963     return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse);
02964   return SimplifyFCmpInst(Predicate, LHS, RHS, Q, MaxRecurse);
02965 }
02966 
02967 Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
02968                              const DataLayout *DL, const TargetLibraryInfo *TLI,
02969                              const DominatorTree *DT) {
02970   return ::SimplifyCmpInst(Predicate, LHS, RHS, Query (DL, TLI, DT),
02971                            RecursionLimit);
02972 }
02973 
02974 static bool IsIdempotent(Intrinsic::ID ID) {
02975   switch (ID) {
02976   default: return false;
02977 
02978   // Unary idempotent: f(f(x)) = f(x)
02979   case Intrinsic::fabs:
02980   case Intrinsic::floor:
02981   case Intrinsic::ceil:
02982   case Intrinsic::trunc:
02983   case Intrinsic::rint:
02984   case Intrinsic::nearbyint:
02985   case Intrinsic::round:
02986     return true;
02987   }
02988 }
02989 
02990 template <typename IterTy>
02991 static Value *SimplifyIntrinsic(Intrinsic::ID IID, IterTy ArgBegin, IterTy ArgEnd,
02992                                 const Query &Q, unsigned MaxRecurse) {
02993   // Perform idempotent optimizations
02994   if (!IsIdempotent(IID))
02995     return nullptr;
02996 
02997   // Unary Ops
02998   if (std::distance(ArgBegin, ArgEnd) == 1)
02999     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(*ArgBegin))
03000       if (II->getIntrinsicID() == IID)
03001         return II;
03002 
03003   return nullptr;
03004 }
03005 
03006 template <typename IterTy>
03007 static Value *SimplifyCall(Value *V, IterTy ArgBegin, IterTy ArgEnd,
03008                            const Query &Q, unsigned MaxRecurse) {
03009   Type *Ty = V->getType();
03010   if (PointerType *PTy = dyn_cast<PointerType>(Ty))
03011     Ty = PTy->getElementType();
03012   FunctionType *FTy = cast<FunctionType>(Ty);
03013 
03014   // call undef -> undef
03015   if (isa<UndefValue>(V))
03016     return UndefValue::get(FTy->getReturnType());
03017 
03018   Function *F = dyn_cast<Function>(V);
03019   if (!F)
03020     return nullptr;
03021 
03022   if (unsigned IID = F->getIntrinsicID())
03023     if (Value *Ret =
03024         SimplifyIntrinsic((Intrinsic::ID) IID, ArgBegin, ArgEnd, Q, MaxRecurse))
03025       return Ret;
03026 
03027   if (!canConstantFoldCallTo(F))
03028     return nullptr;
03029 
03030   SmallVector<Constant *, 4> ConstantArgs;
03031   ConstantArgs.reserve(ArgEnd - ArgBegin);
03032   for (IterTy I = ArgBegin, E = ArgEnd; I != E; ++I) {
03033     Constant *C = dyn_cast<Constant>(*I);
03034     if (!C)
03035       return nullptr;
03036     ConstantArgs.push_back(C);
03037   }
03038 
03039   return ConstantFoldCall(F, ConstantArgs, Q.TLI);
03040 }
03041 
03042 Value *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin,
03043                           User::op_iterator ArgEnd, const DataLayout *DL,
03044                           const TargetLibraryInfo *TLI,
03045                           const DominatorTree *DT) {
03046   return ::SimplifyCall(V, ArgBegin, ArgEnd, Query(DL, TLI, DT),
03047                         RecursionLimit);
03048 }
03049 
03050 Value *llvm::SimplifyCall(Value *V, ArrayRef<Value *> Args,
03051                           const DataLayout *DL, const TargetLibraryInfo *TLI,
03052                           const DominatorTree *DT) {
03053   return ::SimplifyCall(V, Args.begin(), Args.end(), Query(DL, TLI, DT),
03054                         RecursionLimit);
03055 }
03056 
03057 /// SimplifyInstruction - See if we can compute a simplified version of this
03058 /// instruction.  If not, this returns null.
03059 Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout *DL,
03060                                  const TargetLibraryInfo *TLI,
03061                                  const DominatorTree *DT) {
03062   Value *Result;
03063 
03064   switch (I->getOpcode()) {
03065   default:
03066     Result = ConstantFoldInstruction(I, DL, TLI);
03067     break;
03068   case Instruction::FAdd:
03069     Result = SimplifyFAddInst(I->getOperand(0), I->getOperand(1),
03070                               I->getFastMathFlags(), DL, TLI, DT);
03071     break;
03072   case Instruction::Add:
03073     Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
03074                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
03075                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
03076                              DL, TLI, DT);
03077     break;
03078   case Instruction::FSub:
03079     Result = SimplifyFSubInst(I->getOperand(0), I->getOperand(1),
03080                               I->getFastMathFlags(), DL, TLI, DT);
03081     break;
03082   case Instruction::Sub:
03083     Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
03084                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
03085                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
03086                              DL, TLI, DT);
03087     break;
03088   case Instruction::FMul:
03089     Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1),
03090                               I->getFastMathFlags(), DL, TLI, DT);
03091     break;
03092   case Instruction::Mul:
03093     Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT);
03094     break;
03095   case Instruction::SDiv:
03096     Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT);
03097     break;
03098   case Instruction::UDiv:
03099     Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT);
03100     break;
03101   case Instruction::FDiv:
03102     Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT);
03103     break;
03104   case Instruction::SRem:
03105     Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT);
03106     break;
03107   case Instruction::URem:
03108     Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT);
03109     break;
03110   case Instruction::FRem:
03111     Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT);
03112     break;
03113   case Instruction::Shl:
03114     Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1),
03115                              cast<BinaryOperator>(I)->hasNoSignedWrap(),
03116                              cast<BinaryOperator>(I)->hasNoUnsignedWrap(),
03117                              DL, TLI, DT);
03118     break;
03119   case Instruction::LShr:
03120     Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1),
03121                               cast<BinaryOperator>(I)->isExact(),
03122                               DL, TLI, DT);
03123     break;
03124   case Instruction::AShr:
03125     Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1),
03126                               cast<BinaryOperator>(I)->isExact(),
03127                               DL, TLI, DT);
03128     break;
03129   case Instruction::And:
03130     Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT);
03131     break;
03132   case Instruction::Or:
03133     Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT);
03134     break;
03135   case Instruction::Xor:
03136     Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT);
03137     break;
03138   case Instruction::ICmp:
03139     Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
03140                               I->getOperand(0), I->getOperand(1), DL, TLI, DT);
03141     break;
03142   case Instruction::FCmp:
03143     Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
03144                               I->getOperand(0), I->getOperand(1), DL, TLI, DT);
03145     break;
03146   case Instruction::Select:
03147     Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
03148                                 I->getOperand(2), DL, TLI, DT);
03149     break;
03150   case Instruction::GetElementPtr: {
03151     SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
03152     Result = SimplifyGEPInst(Ops, DL, TLI, DT);
03153     break;
03154   }
03155   case Instruction::InsertValue: {
03156     InsertValueInst *IV = cast<InsertValueInst>(I);
03157     Result = SimplifyInsertValueInst(IV->getAggregateOperand(),
03158                                      IV->getInsertedValueOperand(),
03159                                      IV->getIndices(), DL, TLI, DT);
03160     break;
03161   }
03162   case Instruction::PHI:
03163     Result = SimplifyPHINode(cast<PHINode>(I), Query (DL, TLI, DT));
03164     break;
03165   case Instruction::Call: {
03166     CallSite CS(cast<CallInst>(I));
03167     Result = SimplifyCall(CS.getCalledValue(), CS.arg_begin(), CS.arg_end(),
03168                           DL, TLI, DT);
03169     break;
03170   }
03171   case Instruction::Trunc:
03172     Result = SimplifyTruncInst(I->getOperand(0), I->getType(), DL, TLI, DT);
03173     break;
03174   }
03175 
03176   /// If called on unreachable code, the above logic may report that the
03177   /// instruction simplified to itself.  Make life easier for users by
03178   /// detecting that case here, returning a safe value instead.
03179   return Result == I ? UndefValue::get(I->getType()) : Result;
03180 }
03181 
03182 /// \brief Implementation of recursive simplification through an instructions
03183 /// uses.
03184 ///
03185 /// This is the common implementation of the recursive simplification routines.
03186 /// If we have a pre-simplified value in 'SimpleV', that is forcibly used to
03187 /// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of
03188 /// instructions to process and attempt to simplify it using
03189 /// InstructionSimplify.
03190 ///
03191 /// This routine returns 'true' only when *it* simplifies something. The passed
03192 /// in simplified value does not count toward this.
03193 static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV,
03194                                               const DataLayout *DL,
03195                                               const TargetLibraryInfo *TLI,
03196                                               const DominatorTree *DT) {
03197   bool Simplified = false;
03198   SmallSetVector<Instruction *, 8> Worklist;
03199 
03200   // If we have an explicit value to collapse to, do that round of the
03201   // simplification loop by hand initially.
03202   if (SimpleV) {
03203     for (User *U : I->users())
03204       if (U != I)
03205         Worklist.insert(cast<Instruction>(U));
03206 
03207     // Replace the instruction with its simplified value.
03208     I->replaceAllUsesWith(SimpleV);
03209 
03210     // Gracefully handle edge cases where the instruction is not wired into any
03211     // parent block.
03212     if (I->getParent())
03213       I->eraseFromParent();
03214   } else {
03215     Worklist.insert(I);
03216   }
03217 
03218   // Note that we must test the size on each iteration, the worklist can grow.
03219   for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
03220     I = Worklist[Idx];
03221 
03222     // See if this instruction simplifies.
03223     SimpleV = SimplifyInstruction(I, DL, TLI, DT);
03224     if (!SimpleV)
03225       continue;
03226 
03227     Simplified = true;
03228 
03229     // Stash away all the uses of the old instruction so we can check them for
03230     // recursive simplifications after a RAUW. This is cheaper than checking all
03231     // uses of To on the recursive step in most cases.
03232     for (User *U : I->users())
03233       Worklist.insert(cast<Instruction>(U));
03234 
03235     // Replace the instruction with its simplified value.
03236     I->replaceAllUsesWith(SimpleV);
03237 
03238     // Gracefully handle edge cases where the instruction is not wired into any
03239     // parent block.
03240     if (I->getParent())
03241       I->eraseFromParent();
03242   }
03243   return Simplified;
03244 }
03245 
03246 bool llvm::recursivelySimplifyInstruction(Instruction *I,
03247                                           const DataLayout *DL,
03248                                           const TargetLibraryInfo *TLI,
03249                                           const DominatorTree *DT) {
03250   return replaceAndRecursivelySimplifyImpl(I, nullptr, DL, TLI, DT);
03251 }
03252 
03253 bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
03254                                          const DataLayout *DL,
03255                                          const TargetLibraryInfo *TLI,
03256                                          const DominatorTree *DT) {
03257   assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!");
03258   assert(SimpleV && "Must provide a simplified value.");
03259   return replaceAndRecursivelySimplifyImpl(I, SimpleV, DL, TLI, DT);
03260 }