LLVM  mainline
ValueTracking.cpp
Go to the documentation of this file.
00001 //===- ValueTracking.cpp - Walk computations to compute properties --------===//
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 contains routines that help analyze properties that chains of
00011 // computations have.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/Analysis/ValueTracking.h"
00016 #include "llvm/ADT/SmallPtrSet.h"
00017 #include "llvm/Analysis/AssumptionCache.h"
00018 #include "llvm/Analysis/InstructionSimplify.h"
00019 #include "llvm/Analysis/MemoryBuiltins.h"
00020 #include "llvm/Analysis/LoopInfo.h"
00021 #include "llvm/IR/CallSite.h"
00022 #include "llvm/IR/ConstantRange.h"
00023 #include "llvm/IR/Constants.h"
00024 #include "llvm/IR/DataLayout.h"
00025 #include "llvm/IR/Dominators.h"
00026 #include "llvm/IR/GetElementPtrTypeIterator.h"
00027 #include "llvm/IR/GlobalAlias.h"
00028 #include "llvm/IR/GlobalVariable.h"
00029 #include "llvm/IR/Instructions.h"
00030 #include "llvm/IR/IntrinsicInst.h"
00031 #include "llvm/IR/LLVMContext.h"
00032 #include "llvm/IR/Metadata.h"
00033 #include "llvm/IR/Operator.h"
00034 #include "llvm/IR/PatternMatch.h"
00035 #include "llvm/IR/Statepoint.h"
00036 #include "llvm/Support/Debug.h"
00037 #include "llvm/Support/MathExtras.h"
00038 #include <cstring>
00039 using namespace llvm;
00040 using namespace llvm::PatternMatch;
00041 
00042 const unsigned MaxDepth = 6;
00043 
00044 /// Enable an experimental feature to leverage information about dominating
00045 /// conditions to compute known bits.  The individual options below control how
00046 /// hard we search.  The defaults are choosen to be fairly aggressive.  If you
00047 /// run into compile time problems when testing, scale them back and report
00048 /// your findings.
00049 static cl::opt<bool> EnableDomConditions("value-tracking-dom-conditions",
00050                                          cl::Hidden, cl::init(false));
00051 
00052 // This is expensive, so we only do it for the top level query value.
00053 // (TODO: evaluate cost vs profit, consider higher thresholds)
00054 static cl::opt<unsigned> DomConditionsMaxDepth("dom-conditions-max-depth",
00055                                                cl::Hidden, cl::init(1));
00056 
00057 /// How many dominating blocks should be scanned looking for dominating
00058 /// conditions?
00059 static cl::opt<unsigned> DomConditionsMaxDomBlocks("dom-conditions-dom-blocks",
00060                                                    cl::Hidden,
00061                                                    cl::init(20000));
00062 
00063 // Controls the number of uses of the value searched for possible
00064 // dominating comparisons.
00065 static cl::opt<unsigned> DomConditionsMaxUses("dom-conditions-max-uses",
00066                                               cl::Hidden, cl::init(2000));
00067 
00068 // If true, don't consider only compares whose only use is a branch.
00069 static cl::opt<bool> DomConditionsSingleCmpUse("dom-conditions-single-cmp-use",
00070                                                cl::Hidden, cl::init(false));
00071 
00072 /// Returns the bitwidth of the given scalar or pointer type (if unknown returns
00073 /// 0). For vector types, returns the element type's bitwidth.
00074 static unsigned getBitWidth(Type *Ty, const DataLayout &DL) {
00075   if (unsigned BitWidth = Ty->getScalarSizeInBits())
00076     return BitWidth;
00077 
00078   return DL.getPointerTypeSizeInBits(Ty);
00079 }
00080 
00081 // Many of these functions have internal versions that take an assumption
00082 // exclusion set. This is because of the potential for mutual recursion to
00083 // cause computeKnownBits to repeatedly visit the same assume intrinsic. The
00084 // classic case of this is assume(x = y), which will attempt to determine
00085 // bits in x from bits in y, which will attempt to determine bits in y from
00086 // bits in x, etc. Regarding the mutual recursion, computeKnownBits can call
00087 // isKnownNonZero, which calls computeKnownBits and ComputeSignBit and
00088 // isKnownToBeAPowerOfTwo (all of which can call computeKnownBits), and so on.
00089 typedef SmallPtrSet<const Value *, 8> ExclInvsSet;
00090 
00091 namespace {
00092 // Simplifying using an assume can only be done in a particular control-flow
00093 // context (the context instruction provides that context). If an assume and
00094 // the context instruction are not in the same block then the DT helps in
00095 // figuring out if we can use it.
00096 struct Query {
00097   ExclInvsSet ExclInvs;
00098   AssumptionCache *AC;
00099   const Instruction *CxtI;
00100   const DominatorTree *DT;
00101 
00102   Query(AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr,
00103         const DominatorTree *DT = nullptr)
00104       : AC(AC), CxtI(CxtI), DT(DT) {}
00105 
00106   Query(const Query &Q, const Value *NewExcl)
00107       : ExclInvs(Q.ExclInvs), AC(Q.AC), CxtI(Q.CxtI), DT(Q.DT) {
00108     ExclInvs.insert(NewExcl);
00109   }
00110 };
00111 } // end anonymous namespace
00112 
00113 // Given the provided Value and, potentially, a context instruction, return
00114 // the preferred context instruction (if any).
00115 static const Instruction *safeCxtI(const Value *V, const Instruction *CxtI) {
00116   // If we've been provided with a context instruction, then use that (provided
00117   // it has been inserted).
00118   if (CxtI && CxtI->getParent())
00119     return CxtI;
00120 
00121   // If the value is really an already-inserted instruction, then use that.
00122   CxtI = dyn_cast<Instruction>(V);
00123   if (CxtI && CxtI->getParent())
00124     return CxtI;
00125 
00126   return nullptr;
00127 }
00128 
00129 static void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
00130                              const DataLayout &DL, unsigned Depth,
00131                              const Query &Q);
00132 
00133 void llvm::computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
00134                             const DataLayout &DL, unsigned Depth,
00135                             AssumptionCache *AC, const Instruction *CxtI,
00136                             const DominatorTree *DT) {
00137   ::computeKnownBits(V, KnownZero, KnownOne, DL, Depth,
00138                      Query(AC, safeCxtI(V, CxtI), DT));
00139 }
00140 
00141 bool llvm::haveNoCommonBitsSet(Value *LHS, Value *RHS, const DataLayout &DL,
00142                                AssumptionCache *AC, const Instruction *CxtI,
00143                                const DominatorTree *DT) {
00144   assert(LHS->getType() == RHS->getType() &&
00145          "LHS and RHS should have the same type");
00146   assert(LHS->getType()->isIntOrIntVectorTy() &&
00147          "LHS and RHS should be integers");
00148   IntegerType *IT = cast<IntegerType>(LHS->getType()->getScalarType());
00149   APInt LHSKnownZero(IT->getBitWidth(), 0), LHSKnownOne(IT->getBitWidth(), 0);
00150   APInt RHSKnownZero(IT->getBitWidth(), 0), RHSKnownOne(IT->getBitWidth(), 0);
00151   computeKnownBits(LHS, LHSKnownZero, LHSKnownOne, DL, 0, AC, CxtI, DT);
00152   computeKnownBits(RHS, RHSKnownZero, RHSKnownOne, DL, 0, AC, CxtI, DT);
00153   return (LHSKnownZero | RHSKnownZero).isAllOnesValue();
00154 }
00155 
00156 static void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne,
00157                            const DataLayout &DL, unsigned Depth,
00158                            const Query &Q);
00159 
00160 void llvm::ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne,
00161                           const DataLayout &DL, unsigned Depth,
00162                           AssumptionCache *AC, const Instruction *CxtI,
00163                           const DominatorTree *DT) {
00164   ::ComputeSignBit(V, KnownZero, KnownOne, DL, Depth,
00165                    Query(AC, safeCxtI(V, CxtI), DT));
00166 }
00167 
00168 static bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth,
00169                                    const Query &Q, const DataLayout &DL);
00170 
00171 bool llvm::isKnownToBeAPowerOfTwo(Value *V, const DataLayout &DL, bool OrZero,
00172                                   unsigned Depth, AssumptionCache *AC,
00173                                   const Instruction *CxtI,
00174                                   const DominatorTree *DT) {
00175   return ::isKnownToBeAPowerOfTwo(V, OrZero, Depth,
00176                                   Query(AC, safeCxtI(V, CxtI), DT), DL);
00177 }
00178 
00179 static bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
00180                            const Query &Q);
00181 
00182 bool llvm::isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
00183                           AssumptionCache *AC, const Instruction *CxtI,
00184                           const DominatorTree *DT) {
00185   return ::isKnownNonZero(V, DL, Depth, Query(AC, safeCxtI(V, CxtI), DT));
00186 }
00187 
00188 static bool MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout &DL,
00189                               unsigned Depth, const Query &Q);
00190 
00191 bool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout &DL,
00192                              unsigned Depth, AssumptionCache *AC,
00193                              const Instruction *CxtI, const DominatorTree *DT) {
00194   return ::MaskedValueIsZero(V, Mask, DL, Depth,
00195                              Query(AC, safeCxtI(V, CxtI), DT));
00196 }
00197 
00198 static unsigned ComputeNumSignBits(Value *V, const DataLayout &DL,
00199                                    unsigned Depth, const Query &Q);
00200 
00201 unsigned llvm::ComputeNumSignBits(Value *V, const DataLayout &DL,
00202                                   unsigned Depth, AssumptionCache *AC,
00203                                   const Instruction *CxtI,
00204                                   const DominatorTree *DT) {
00205   return ::ComputeNumSignBits(V, DL, Depth, Query(AC, safeCxtI(V, CxtI), DT));
00206 }
00207 
00208 static void computeKnownBitsAddSub(bool Add, Value *Op0, Value *Op1, bool NSW,
00209                                    APInt &KnownZero, APInt &KnownOne,
00210                                    APInt &KnownZero2, APInt &KnownOne2,
00211                                    const DataLayout &DL, unsigned Depth,
00212                                    const Query &Q) {
00213   if (!Add) {
00214     if (ConstantInt *CLHS = dyn_cast<ConstantInt>(Op0)) {
00215       // We know that the top bits of C-X are clear if X contains less bits
00216       // than C (i.e. no wrap-around can happen).  For example, 20-X is
00217       // positive if we can prove that X is >= 0 and < 16.
00218       if (!CLHS->getValue().isNegative()) {
00219         unsigned BitWidth = KnownZero.getBitWidth();
00220         unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros();
00221         // NLZ can't be BitWidth with no sign bit
00222         APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
00223         computeKnownBits(Op1, KnownZero2, KnownOne2, DL, Depth + 1, Q);
00224 
00225         // If all of the MaskV bits are known to be zero, then we know the
00226         // output top bits are zero, because we now know that the output is
00227         // from [0-C].
00228         if ((KnownZero2 & MaskV) == MaskV) {
00229           unsigned NLZ2 = CLHS->getValue().countLeadingZeros();
00230           // Top bits known zero.
00231           KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
00232         }
00233       }
00234     }
00235   }
00236 
00237   unsigned BitWidth = KnownZero.getBitWidth();
00238 
00239   // If an initial sequence of bits in the result is not needed, the
00240   // corresponding bits in the operands are not needed.
00241   APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
00242   computeKnownBits(Op0, LHSKnownZero, LHSKnownOne, DL, Depth + 1, Q);
00243   computeKnownBits(Op1, KnownZero2, KnownOne2, DL, Depth + 1, Q);
00244 
00245   // Carry in a 1 for a subtract, rather than a 0.
00246   APInt CarryIn(BitWidth, 0);
00247   if (!Add) {
00248     // Sum = LHS + ~RHS + 1
00249     std::swap(KnownZero2, KnownOne2);
00250     CarryIn.setBit(0);
00251   }
00252 
00253   APInt PossibleSumZero = ~LHSKnownZero + ~KnownZero2 + CarryIn;
00254   APInt PossibleSumOne = LHSKnownOne + KnownOne2 + CarryIn;
00255 
00256   // Compute known bits of the carry.
00257   APInt CarryKnownZero = ~(PossibleSumZero ^ LHSKnownZero ^ KnownZero2);
00258   APInt CarryKnownOne = PossibleSumOne ^ LHSKnownOne ^ KnownOne2;
00259 
00260   // Compute set of known bits (where all three relevant bits are known).
00261   APInt LHSKnown = LHSKnownZero | LHSKnownOne;
00262   APInt RHSKnown = KnownZero2 | KnownOne2;
00263   APInt CarryKnown = CarryKnownZero | CarryKnownOne;
00264   APInt Known = LHSKnown & RHSKnown & CarryKnown;
00265 
00266   assert((PossibleSumZero & Known) == (PossibleSumOne & Known) &&
00267          "known bits of sum differ");
00268 
00269   // Compute known bits of the result.
00270   KnownZero = ~PossibleSumOne & Known;
00271   KnownOne = PossibleSumOne & Known;
00272 
00273   // Are we still trying to solve for the sign bit?
00274   if (!Known.isNegative()) {
00275     if (NSW) {
00276       // Adding two non-negative numbers, or subtracting a negative number from
00277       // a non-negative one, can't wrap into negative.
00278       if (LHSKnownZero.isNegative() && KnownZero2.isNegative())
00279         KnownZero |= APInt::getSignBit(BitWidth);
00280       // Adding two negative numbers, or subtracting a non-negative number from
00281       // a negative one, can't wrap into non-negative.
00282       else if (LHSKnownOne.isNegative() && KnownOne2.isNegative())
00283         KnownOne |= APInt::getSignBit(BitWidth);
00284     }
00285   }
00286 }
00287 
00288 static void computeKnownBitsMul(Value *Op0, Value *Op1, bool NSW,
00289                                 APInt &KnownZero, APInt &KnownOne,
00290                                 APInt &KnownZero2, APInt &KnownOne2,
00291                                 const DataLayout &DL, unsigned Depth,
00292                                 const Query &Q) {
00293   unsigned BitWidth = KnownZero.getBitWidth();
00294   computeKnownBits(Op1, KnownZero, KnownOne, DL, Depth + 1, Q);
00295   computeKnownBits(Op0, KnownZero2, KnownOne2, DL, Depth + 1, Q);
00296 
00297   bool isKnownNegative = false;
00298   bool isKnownNonNegative = false;
00299   // If the multiplication is known not to overflow, compute the sign bit.
00300   if (NSW) {
00301     if (Op0 == Op1) {
00302       // The product of a number with itself is non-negative.
00303       isKnownNonNegative = true;
00304     } else {
00305       bool isKnownNonNegativeOp1 = KnownZero.isNegative();
00306       bool isKnownNonNegativeOp0 = KnownZero2.isNegative();
00307       bool isKnownNegativeOp1 = KnownOne.isNegative();
00308       bool isKnownNegativeOp0 = KnownOne2.isNegative();
00309       // The product of two numbers with the same sign is non-negative.
00310       isKnownNonNegative = (isKnownNegativeOp1 && isKnownNegativeOp0) ||
00311         (isKnownNonNegativeOp1 && isKnownNonNegativeOp0);
00312       // The product of a negative number and a non-negative number is either
00313       // negative or zero.
00314       if (!isKnownNonNegative)
00315         isKnownNegative = (isKnownNegativeOp1 && isKnownNonNegativeOp0 &&
00316                            isKnownNonZero(Op0, DL, Depth, Q)) ||
00317                           (isKnownNegativeOp0 && isKnownNonNegativeOp1 &&
00318                            isKnownNonZero(Op1, DL, Depth, Q));
00319     }
00320   }
00321 
00322   // If low bits are zero in either operand, output low known-0 bits.
00323   // Also compute a conserative estimate for high known-0 bits.
00324   // More trickiness is possible, but this is sufficient for the
00325   // interesting case of alignment computation.
00326   KnownOne.clearAllBits();
00327   unsigned TrailZ = KnownZero.countTrailingOnes() +
00328                     KnownZero2.countTrailingOnes();
00329   unsigned LeadZ =  std::max(KnownZero.countLeadingOnes() +
00330                              KnownZero2.countLeadingOnes(),
00331                              BitWidth) - BitWidth;
00332 
00333   TrailZ = std::min(TrailZ, BitWidth);
00334   LeadZ = std::min(LeadZ, BitWidth);
00335   KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
00336               APInt::getHighBitsSet(BitWidth, LeadZ);
00337 
00338   // Only make use of no-wrap flags if we failed to compute the sign bit
00339   // directly.  This matters if the multiplication always overflows, in
00340   // which case we prefer to follow the result of the direct computation,
00341   // though as the program is invoking undefined behaviour we can choose
00342   // whatever we like here.
00343   if (isKnownNonNegative && !KnownOne.isNegative())
00344     KnownZero.setBit(BitWidth - 1);
00345   else if (isKnownNegative && !KnownZero.isNegative())
00346     KnownOne.setBit(BitWidth - 1);
00347 }
00348 
00349 void llvm::computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
00350                                              APInt &KnownZero) {
00351   unsigned BitWidth = KnownZero.getBitWidth();
00352   unsigned NumRanges = Ranges.getNumOperands() / 2;
00353   assert(NumRanges >= 1);
00354 
00355   // Use the high end of the ranges to find leading zeros.
00356   unsigned MinLeadingZeros = BitWidth;
00357   for (unsigned i = 0; i < NumRanges; ++i) {
00358     ConstantInt *Lower =
00359         mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
00360     ConstantInt *Upper =
00361         mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
00362     ConstantRange Range(Lower->getValue(), Upper->getValue());
00363     if (Range.isWrappedSet())
00364       MinLeadingZeros = 0; // -1 has no zeros
00365     unsigned LeadingZeros = (Upper->getValue() - 1).countLeadingZeros();
00366     MinLeadingZeros = std::min(LeadingZeros, MinLeadingZeros);
00367   }
00368 
00369   KnownZero = APInt::getHighBitsSet(BitWidth, MinLeadingZeros);
00370 }
00371 
00372 static bool isEphemeralValueOf(Instruction *I, const Value *E) {
00373   SmallVector<const Value *, 16> WorkSet(1, I);
00374   SmallPtrSet<const Value *, 32> Visited;
00375   SmallPtrSet<const Value *, 16> EphValues;
00376 
00377   while (!WorkSet.empty()) {
00378     const Value *V = WorkSet.pop_back_val();
00379     if (!Visited.insert(V).second)
00380       continue;
00381 
00382     // If all uses of this value are ephemeral, then so is this value.
00383     bool FoundNEUse = false;
00384     for (const User *I : V->users())
00385       if (!EphValues.count(I)) {
00386         FoundNEUse = true;
00387         break;
00388       }
00389 
00390     if (!FoundNEUse) {
00391       if (V == E)
00392         return true;
00393 
00394       EphValues.insert(V);
00395       if (const User *U = dyn_cast<User>(V))
00396         for (User::const_op_iterator J = U->op_begin(), JE = U->op_end();
00397              J != JE; ++J) {
00398           if (isSafeToSpeculativelyExecute(*J))
00399             WorkSet.push_back(*J);
00400         }
00401     }
00402   }
00403 
00404   return false;
00405 }
00406 
00407 // Is this an intrinsic that cannot be speculated but also cannot trap?
00408 static bool isAssumeLikeIntrinsic(const Instruction *I) {
00409   if (const CallInst *CI = dyn_cast<CallInst>(I))
00410     if (Function *F = CI->getCalledFunction())
00411       switch (F->getIntrinsicID()) {
00412       default: break;
00413       // FIXME: This list is repeated from NoTTI::getIntrinsicCost.
00414       case Intrinsic::assume:
00415       case Intrinsic::dbg_declare:
00416       case Intrinsic::dbg_value:
00417       case Intrinsic::invariant_start:
00418       case Intrinsic::invariant_end:
00419       case Intrinsic::lifetime_start:
00420       case Intrinsic::lifetime_end:
00421       case Intrinsic::objectsize:
00422       case Intrinsic::ptr_annotation:
00423       case Intrinsic::var_annotation:
00424         return true;
00425       }
00426 
00427   return false;
00428 }
00429 
00430 static bool isValidAssumeForContext(Value *V, const Query &Q) {
00431   Instruction *Inv = cast<Instruction>(V);
00432 
00433   // There are two restrictions on the use of an assume:
00434   //  1. The assume must dominate the context (or the control flow must
00435   //     reach the assume whenever it reaches the context).
00436   //  2. The context must not be in the assume's set of ephemeral values
00437   //     (otherwise we will use the assume to prove that the condition
00438   //     feeding the assume is trivially true, thus causing the removal of
00439   //     the assume).
00440 
00441   if (Q.DT) {
00442     if (Q.DT->dominates(Inv, Q.CxtI)) {
00443       return true;
00444     } else if (Inv->getParent() == Q.CxtI->getParent()) {
00445       // The context comes first, but they're both in the same block. Make sure
00446       // there is nothing in between that might interrupt the control flow.
00447       for (BasicBlock::const_iterator I =
00448              std::next(BasicBlock::const_iterator(Q.CxtI)),
00449                                       IE(Inv); I != IE; ++I)
00450         if (!isSafeToSpeculativelyExecute(I) && !isAssumeLikeIntrinsic(I))
00451           return false;
00452 
00453       return !isEphemeralValueOf(Inv, Q.CxtI);
00454     }
00455 
00456     return false;
00457   }
00458 
00459   // When we don't have a DT, we do a limited search...
00460   if (Inv->getParent() == Q.CxtI->getParent()->getSinglePredecessor()) {
00461     return true;
00462   } else if (Inv->getParent() == Q.CxtI->getParent()) {
00463     // Search forward from the assume until we reach the context (or the end
00464     // of the block); the common case is that the assume will come first.
00465     for (BasicBlock::iterator I = std::next(BasicBlock::iterator(Inv)),
00466          IE = Inv->getParent()->end(); I != IE; ++I)
00467       if (I == Q.CxtI)
00468         return true;
00469 
00470     // The context must come first...
00471     for (BasicBlock::const_iterator I =
00472            std::next(BasicBlock::const_iterator(Q.CxtI)),
00473                                     IE(Inv); I != IE; ++I)
00474       if (!isSafeToSpeculativelyExecute(I) && !isAssumeLikeIntrinsic(I))
00475         return false;
00476 
00477     return !isEphemeralValueOf(Inv, Q.CxtI);
00478   }
00479 
00480   return false;
00481 }
00482 
00483 bool llvm::isValidAssumeForContext(const Instruction *I,
00484                                    const Instruction *CxtI,
00485                                    const DominatorTree *DT) {
00486   return ::isValidAssumeForContext(const_cast<Instruction *>(I),
00487                                    Query(nullptr, CxtI, DT));
00488 }
00489 
00490 template<typename LHS, typename RHS>
00491 inline match_combine_or<CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>,
00492                         CmpClass_match<RHS, LHS, ICmpInst, ICmpInst::Predicate>>
00493 m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
00494   return m_CombineOr(m_ICmp(Pred, L, R), m_ICmp(Pred, R, L));
00495 }
00496 
00497 template<typename LHS, typename RHS>
00498 inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::And>,
00499                         BinaryOp_match<RHS, LHS, Instruction::And>>
00500 m_c_And(const LHS &L, const RHS &R) {
00501   return m_CombineOr(m_And(L, R), m_And(R, L));
00502 }
00503 
00504 template<typename LHS, typename RHS>
00505 inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Or>,
00506                         BinaryOp_match<RHS, LHS, Instruction::Or>>
00507 m_c_Or(const LHS &L, const RHS &R) {
00508   return m_CombineOr(m_Or(L, R), m_Or(R, L));
00509 }
00510 
00511 template<typename LHS, typename RHS>
00512 inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Xor>,
00513                         BinaryOp_match<RHS, LHS, Instruction::Xor>>
00514 m_c_Xor(const LHS &L, const RHS &R) {
00515   return m_CombineOr(m_Xor(L, R), m_Xor(R, L));
00516 }
00517 
00518 /// Compute known bits in 'V' under the assumption that the condition 'Cmp' is
00519 /// true (at the context instruction.)  This is mostly a utility function for
00520 /// the prototype dominating conditions reasoning below.
00521 static void computeKnownBitsFromTrueCondition(Value *V, ICmpInst *Cmp,
00522                                               APInt &KnownZero,
00523                                               APInt &KnownOne,
00524                                               const DataLayout &DL,
00525                                               unsigned Depth, const Query &Q) {
00526   Value *LHS = Cmp->getOperand(0);
00527   Value *RHS = Cmp->getOperand(1);
00528   // TODO: We could potentially be more aggressive here.  This would be worth
00529   // evaluating.  If we can, explore commoning this code with the assume
00530   // handling logic.
00531   if (LHS != V && RHS != V)
00532     return;
00533 
00534   const unsigned BitWidth = KnownZero.getBitWidth();
00535 
00536   switch (Cmp->getPredicate()) {
00537   default:
00538     // We know nothing from this condition
00539     break;
00540   // TODO: implement unsigned bound from below (known one bits)
00541   // TODO: common condition check implementations with assumes
00542   // TODO: implement other patterns from assume (e.g. V & B == A)
00543   case ICmpInst::ICMP_SGT:
00544     if (LHS == V) {
00545       APInt KnownZeroTemp(BitWidth, 0), KnownOneTemp(BitWidth, 0);
00546       computeKnownBits(RHS, KnownZeroTemp, KnownOneTemp, DL, Depth + 1, Q);
00547       if (KnownOneTemp.isAllOnesValue() || KnownZeroTemp.isNegative()) {
00548         // We know that the sign bit is zero.
00549         KnownZero |= APInt::getSignBit(BitWidth);
00550       }
00551     }
00552     break;
00553   case ICmpInst::ICMP_EQ:
00554     if (LHS == V)
00555       computeKnownBits(RHS, KnownZero, KnownOne, DL, Depth + 1, Q);
00556     else if (RHS == V)
00557       computeKnownBits(LHS, KnownZero, KnownOne, DL, Depth + 1, Q);
00558     else
00559       llvm_unreachable("missing use?");
00560     break;
00561   case ICmpInst::ICMP_ULE:
00562     if (LHS == V) {
00563       APInt KnownZeroTemp(BitWidth, 0), KnownOneTemp(BitWidth, 0);
00564       computeKnownBits(RHS, KnownZeroTemp, KnownOneTemp, DL, Depth + 1, Q);
00565       // The known zero bits carry over
00566       unsigned SignBits = KnownZeroTemp.countLeadingOnes();
00567       KnownZero |= APInt::getHighBitsSet(BitWidth, SignBits);
00568     }
00569     break;
00570   case ICmpInst::ICMP_ULT:
00571     if (LHS == V) {
00572       APInt KnownZeroTemp(BitWidth, 0), KnownOneTemp(BitWidth, 0);
00573       computeKnownBits(RHS, KnownZeroTemp, KnownOneTemp, DL, Depth + 1, Q);
00574       // Whatever high bits in rhs are zero are known to be zero (if rhs is a
00575       // power of 2, then one more).
00576       unsigned SignBits = KnownZeroTemp.countLeadingOnes();
00577       if (isKnownToBeAPowerOfTwo(RHS, false, Depth + 1, Query(Q, Cmp), DL))
00578         SignBits++;
00579       KnownZero |= APInt::getHighBitsSet(BitWidth, SignBits);
00580     }
00581     break;
00582   };
00583 }
00584 
00585 /// Compute known bits in 'V' from conditions which are known to be true along
00586 /// all paths leading to the context instruction.  In particular, look for
00587 /// cases where one branch of an interesting condition dominates the context
00588 /// instruction.  This does not do general dataflow.
00589 /// NOTE: This code is EXPERIMENTAL and currently off by default.
00590 static void computeKnownBitsFromDominatingCondition(Value *V, APInt &KnownZero,
00591                                                     APInt &KnownOne,
00592                                                     const DataLayout &DL,
00593                                                     unsigned Depth,
00594                                                     const Query &Q) {
00595   // Need both the dominator tree and the query location to do anything useful
00596   if (!Q.DT || !Q.CxtI)
00597     return;
00598   Instruction *Cxt = const_cast<Instruction *>(Q.CxtI);
00599 
00600   // Avoid useless work
00601   if (auto VI = dyn_cast<Instruction>(V))
00602     if (VI->getParent() == Cxt->getParent())
00603       return;
00604 
00605   // Note: We currently implement two options.  It's not clear which of these
00606   // will survive long term, we need data for that.
00607   // Option 1 - Try walking the dominator tree looking for conditions which
00608   // might apply.  This works well for local conditions (loop guards, etc..),
00609   // but not as well for things far from the context instruction (presuming a
00610   // low max blocks explored).  If we can set an high enough limit, this would
00611   // be all we need.
00612   // Option 2 - We restrict out search to those conditions which are uses of
00613   // the value we're interested in.  This is independent of dom structure,
00614   // but is slightly less powerful without looking through lots of use chains.
00615   // It does handle conditions far from the context instruction (e.g. early
00616   // function exits on entry) really well though.
00617 
00618   // Option 1 - Search the dom tree
00619   unsigned NumBlocksExplored = 0;
00620   BasicBlock *Current = Cxt->getParent();
00621   while (true) {
00622     // Stop searching if we've gone too far up the chain
00623     if (NumBlocksExplored >= DomConditionsMaxDomBlocks)
00624       break;
00625     NumBlocksExplored++;
00626 
00627     if (!Q.DT->getNode(Current)->getIDom())
00628       break;
00629     Current = Q.DT->getNode(Current)->getIDom()->getBlock();
00630     if (!Current)
00631       // found function entry
00632       break;
00633 
00634     BranchInst *BI = dyn_cast<BranchInst>(Current->getTerminator());
00635     if (!BI || BI->isUnconditional())
00636       continue;
00637     ICmpInst *Cmp = dyn_cast<ICmpInst>(BI->getCondition());
00638     if (!Cmp)
00639       continue;
00640 
00641     // We're looking for conditions that are guaranteed to hold at the context
00642     // instruction.  Finding a condition where one path dominates the context
00643     // isn't enough because both the true and false cases could merge before
00644     // the context instruction we're actually interested in.  Instead, we need
00645     // to ensure that the taken *edge* dominates the context instruction.
00646     BasicBlock *BB0 = BI->getSuccessor(0);
00647     BasicBlockEdge Edge(BI->getParent(), BB0);
00648     if (!Edge.isSingleEdge() || !Q.DT->dominates(Edge, Q.CxtI->getParent()))
00649       continue;
00650 
00651     computeKnownBitsFromTrueCondition(V, Cmp, KnownZero, KnownOne, DL, Depth,
00652                                       Q);
00653   }
00654 
00655   // Option 2 - Search the other uses of V
00656   unsigned NumUsesExplored = 0;
00657   for (auto U : V->users()) {
00658     // Avoid massive lists
00659     if (NumUsesExplored >= DomConditionsMaxUses)
00660       break;
00661     NumUsesExplored++;
00662     // Consider only compare instructions uniquely controlling a branch
00663     ICmpInst *Cmp = dyn_cast<ICmpInst>(U);
00664     if (!Cmp)
00665       continue;
00666 
00667     if (DomConditionsSingleCmpUse && !Cmp->hasOneUse())
00668       continue;
00669 
00670     for (auto *CmpU : Cmp->users()) {
00671       BranchInst *BI = dyn_cast<BranchInst>(CmpU);
00672       if (!BI || BI->isUnconditional())
00673         continue;
00674       // We're looking for conditions that are guaranteed to hold at the
00675       // context instruction.  Finding a condition where one path dominates
00676       // the context isn't enough because both the true and false cases could
00677       // merge before the context instruction we're actually interested in.
00678       // Instead, we need to ensure that the taken *edge* dominates the context
00679       // instruction. 
00680       BasicBlock *BB0 = BI->getSuccessor(0);
00681       BasicBlockEdge Edge(BI->getParent(), BB0);
00682       if (!Edge.isSingleEdge() || !Q.DT->dominates(Edge, Q.CxtI->getParent()))
00683         continue;
00684 
00685       computeKnownBitsFromTrueCondition(V, Cmp, KnownZero, KnownOne, DL, Depth,
00686                                         Q);
00687     }
00688   }
00689 }
00690 
00691 static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero,
00692                                        APInt &KnownOne, const DataLayout &DL,
00693                                        unsigned Depth, const Query &Q) {
00694   // Use of assumptions is context-sensitive. If we don't have a context, we
00695   // cannot use them!
00696   if (!Q.AC || !Q.CxtI)
00697     return;
00698 
00699   unsigned BitWidth = KnownZero.getBitWidth();
00700 
00701   for (auto &AssumeVH : Q.AC->assumptions()) {
00702     if (!AssumeVH)
00703       continue;
00704     CallInst *I = cast<CallInst>(AssumeVH);
00705     assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() &&
00706            "Got assumption for the wrong function!");
00707     if (Q.ExclInvs.count(I))
00708       continue;
00709 
00710     // Warning: This loop can end up being somewhat performance sensetive.
00711     // We're running this loop for once for each value queried resulting in a
00712     // runtime of ~O(#assumes * #values).
00713 
00714     assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
00715            "must be an assume intrinsic");
00716 
00717     Value *Arg = I->getArgOperand(0);
00718 
00719     if (Arg == V && isValidAssumeForContext(I, Q)) {
00720       assert(BitWidth == 1 && "assume operand is not i1?");
00721       KnownZero.clearAllBits();
00722       KnownOne.setAllBits();
00723       return;
00724     }
00725 
00726     // The remaining tests are all recursive, so bail out if we hit the limit.
00727     if (Depth == MaxDepth)
00728       continue;
00729 
00730     Value *A, *B;
00731     auto m_V = m_CombineOr(m_Specific(V),
00732                            m_CombineOr(m_PtrToInt(m_Specific(V)),
00733                            m_BitCast(m_Specific(V))));
00734 
00735     CmpInst::Predicate Pred;
00736     ConstantInt *C;
00737     // assume(v = a)
00738     if (match(Arg, m_c_ICmp(Pred, m_V, m_Value(A))) &&
00739         Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
00740       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00741       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00742       KnownZero |= RHSKnownZero;
00743       KnownOne  |= RHSKnownOne;
00744     // assume(v & b = a)
00745     } else if (match(Arg,
00746                      m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), m_Value(A))) &&
00747                Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
00748       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00749       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00750       APInt MaskKnownZero(BitWidth, 0), MaskKnownOne(BitWidth, 0);
00751       computeKnownBits(B, MaskKnownZero, MaskKnownOne, DL, Depth+1, Query(Q, I));
00752 
00753       // For those bits in the mask that are known to be one, we can propagate
00754       // known bits from the RHS to V.
00755       KnownZero |= RHSKnownZero & MaskKnownOne;
00756       KnownOne  |= RHSKnownOne  & MaskKnownOne;
00757     // assume(~(v & b) = a)
00758     } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_And(m_V, m_Value(B))),
00759                                    m_Value(A))) &&
00760                Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
00761       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00762       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00763       APInt MaskKnownZero(BitWidth, 0), MaskKnownOne(BitWidth, 0);
00764       computeKnownBits(B, MaskKnownZero, MaskKnownOne, DL, Depth+1, Query(Q, I));
00765 
00766       // For those bits in the mask that are known to be one, we can propagate
00767       // inverted known bits from the RHS to V.
00768       KnownZero |= RHSKnownOne  & MaskKnownOne;
00769       KnownOne  |= RHSKnownZero & MaskKnownOne;
00770     // assume(v | b = a)
00771     } else if (match(Arg,
00772                      m_c_ICmp(Pred, m_c_Or(m_V, m_Value(B)), m_Value(A))) &&
00773                Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
00774       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00775       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00776       APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
00777       computeKnownBits(B, BKnownZero, BKnownOne, DL, Depth+1, Query(Q, I));
00778 
00779       // For those bits in B that are known to be zero, we can propagate known
00780       // bits from the RHS to V.
00781       KnownZero |= RHSKnownZero & BKnownZero;
00782       KnownOne  |= RHSKnownOne  & BKnownZero;
00783     // assume(~(v | b) = a)
00784     } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_Or(m_V, m_Value(B))),
00785                                    m_Value(A))) &&
00786                Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
00787       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00788       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00789       APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
00790       computeKnownBits(B, BKnownZero, BKnownOne, DL, Depth+1, Query(Q, I));
00791 
00792       // For those bits in B that are known to be zero, we can propagate
00793       // inverted known bits from the RHS to V.
00794       KnownZero |= RHSKnownOne  & BKnownZero;
00795       KnownOne  |= RHSKnownZero & BKnownZero;
00796     // assume(v ^ b = a)
00797     } else if (match(Arg,
00798                      m_c_ICmp(Pred, m_c_Xor(m_V, m_Value(B)), m_Value(A))) &&
00799                Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
00800       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00801       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00802       APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
00803       computeKnownBits(B, BKnownZero, BKnownOne, DL, Depth+1, Query(Q, I));
00804 
00805       // For those bits in B that are known to be zero, we can propagate known
00806       // bits from the RHS to V. For those bits in B that are known to be one,
00807       // we can propagate inverted known bits from the RHS to V.
00808       KnownZero |= RHSKnownZero & BKnownZero;
00809       KnownOne  |= RHSKnownOne  & BKnownZero;
00810       KnownZero |= RHSKnownOne  & BKnownOne;
00811       KnownOne  |= RHSKnownZero & BKnownOne;
00812     // assume(~(v ^ b) = a)
00813     } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_Xor(m_V, m_Value(B))),
00814                                    m_Value(A))) &&
00815                Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
00816       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00817       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00818       APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
00819       computeKnownBits(B, BKnownZero, BKnownOne, DL, Depth+1, Query(Q, I));
00820 
00821       // For those bits in B that are known to be zero, we can propagate
00822       // inverted known bits from the RHS to V. For those bits in B that are
00823       // known to be one, we can propagate known bits from the RHS to V.
00824       KnownZero |= RHSKnownOne  & BKnownZero;
00825       KnownOne  |= RHSKnownZero & BKnownZero;
00826       KnownZero |= RHSKnownZero & BKnownOne;
00827       KnownOne  |= RHSKnownOne  & BKnownOne;
00828     // assume(v << c = a)
00829     } else if (match(Arg, m_c_ICmp(Pred, m_Shl(m_V, m_ConstantInt(C)),
00830                                    m_Value(A))) &&
00831                Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
00832       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00833       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00834       // For those bits in RHS that are known, we can propagate them to known
00835       // bits in V shifted to the right by C.
00836       KnownZero |= RHSKnownZero.lshr(C->getZExtValue());
00837       KnownOne  |= RHSKnownOne.lshr(C->getZExtValue());
00838     // assume(~(v << c) = a)
00839     } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_Shl(m_V, m_ConstantInt(C))),
00840                                    m_Value(A))) &&
00841                Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
00842       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00843       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00844       // For those bits in RHS that are known, we can propagate them inverted
00845       // to known bits in V shifted to the right by C.
00846       KnownZero |= RHSKnownOne.lshr(C->getZExtValue());
00847       KnownOne  |= RHSKnownZero.lshr(C->getZExtValue());
00848     // assume(v >> c = a)
00849     } else if (match(Arg,
00850                      m_c_ICmp(Pred, m_CombineOr(m_LShr(m_V, m_ConstantInt(C)),
00851                                                 m_AShr(m_V, m_ConstantInt(C))),
00852                               m_Value(A))) &&
00853                Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
00854       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00855       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00856       // For those bits in RHS that are known, we can propagate them to known
00857       // bits in V shifted to the right by C.
00858       KnownZero |= RHSKnownZero << C->getZExtValue();
00859       KnownOne  |= RHSKnownOne  << C->getZExtValue();
00860     // assume(~(v >> c) = a)
00861     } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_CombineOr(
00862                                              m_LShr(m_V, m_ConstantInt(C)),
00863                                              m_AShr(m_V, m_ConstantInt(C)))),
00864                                    m_Value(A))) &&
00865                Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
00866       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00867       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00868       // For those bits in RHS that are known, we can propagate them inverted
00869       // to known bits in V shifted to the right by C.
00870       KnownZero |= RHSKnownOne  << C->getZExtValue();
00871       KnownOne  |= RHSKnownZero << C->getZExtValue();
00872     // assume(v >=_s c) where c is non-negative
00873     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
00874                Pred == ICmpInst::ICMP_SGE && isValidAssumeForContext(I, Q)) {
00875       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00876       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00877 
00878       if (RHSKnownZero.isNegative()) {
00879         // We know that the sign bit is zero.
00880         KnownZero |= APInt::getSignBit(BitWidth);
00881       }
00882     // assume(v >_s c) where c is at least -1.
00883     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
00884                Pred == ICmpInst::ICMP_SGT && isValidAssumeForContext(I, Q)) {
00885       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00886       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00887 
00888       if (RHSKnownOne.isAllOnesValue() || RHSKnownZero.isNegative()) {
00889         // We know that the sign bit is zero.
00890         KnownZero |= APInt::getSignBit(BitWidth);
00891       }
00892     // assume(v <=_s c) where c is negative
00893     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
00894                Pred == ICmpInst::ICMP_SLE && isValidAssumeForContext(I, Q)) {
00895       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00896       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00897 
00898       if (RHSKnownOne.isNegative()) {
00899         // We know that the sign bit is one.
00900         KnownOne |= APInt::getSignBit(BitWidth);
00901       }
00902     // assume(v <_s c) where c is non-positive
00903     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
00904                Pred == ICmpInst::ICMP_SLT && isValidAssumeForContext(I, Q)) {
00905       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00906       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00907 
00908       if (RHSKnownZero.isAllOnesValue() || RHSKnownOne.isNegative()) {
00909         // We know that the sign bit is one.
00910         KnownOne |= APInt::getSignBit(BitWidth);
00911       }
00912     // assume(v <=_u c)
00913     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
00914                Pred == ICmpInst::ICMP_ULE && isValidAssumeForContext(I, Q)) {
00915       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00916       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00917 
00918       // Whatever high bits in c are zero are known to be zero.
00919       KnownZero |=
00920         APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes());
00921     // assume(v <_u c)
00922     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
00923                Pred == ICmpInst::ICMP_ULT && isValidAssumeForContext(I, Q)) {
00924       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
00925       computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
00926 
00927       // Whatever high bits in c are zero are known to be zero (if c is a power
00928       // of 2, then one more).
00929       if (isKnownToBeAPowerOfTwo(A, false, Depth + 1, Query(Q, I), DL))
00930         KnownZero |=
00931           APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes()+1);
00932       else
00933         KnownZero |=
00934           APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes());
00935     }
00936   }
00937 }
00938 
00939 /// Determine which bits of V are known to be either zero or one and return
00940 /// them in the KnownZero/KnownOne bit sets.
00941 ///
00942 /// NOTE: we cannot consider 'undef' to be "IsZero" here.  The problem is that
00943 /// we cannot optimize based on the assumption that it is zero without changing
00944 /// it to be an explicit zero.  If we don't change it to zero, other code could
00945 /// optimized based on the contradictory assumption that it is non-zero.
00946 /// Because instcombine aggressively folds operations with undef args anyway,
00947 /// this won't lose us code quality.
00948 ///
00949 /// This function is defined on values with integer type, values with pointer
00950 /// type, and vectors of integers.  In the case
00951 /// where V is a vector, known zero, and known one values are the
00952 /// same width as the vector element, and the bit is set only if it is true
00953 /// for all of the elements in the vector.
00954 void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
00955                       const DataLayout &DL, unsigned Depth, const Query &Q) {
00956   assert(V && "No Value?");
00957   assert(Depth <= MaxDepth && "Limit Search Depth");
00958   unsigned BitWidth = KnownZero.getBitWidth();
00959 
00960   assert((V->getType()->isIntOrIntVectorTy() ||
00961           V->getType()->getScalarType()->isPointerTy()) &&
00962          "Not integer or pointer type!");
00963   assert((DL.getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) &&
00964          (!V->getType()->isIntOrIntVectorTy() ||
00965           V->getType()->getScalarSizeInBits() == BitWidth) &&
00966          KnownZero.getBitWidth() == BitWidth &&
00967          KnownOne.getBitWidth() == BitWidth &&
00968          "V, KnownOne and KnownZero should have same BitWidth");
00969 
00970   if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
00971     // We know all of the bits for a constant!
00972     KnownOne = CI->getValue();
00973     KnownZero = ~KnownOne;
00974     return;
00975   }
00976   // Null and aggregate-zero are all-zeros.
00977   if (isa<ConstantPointerNull>(V) ||
00978       isa<ConstantAggregateZero>(V)) {
00979     KnownOne.clearAllBits();
00980     KnownZero = APInt::getAllOnesValue(BitWidth);
00981     return;
00982   }
00983   // Handle a constant vector by taking the intersection of the known bits of
00984   // each element.  There is no real need to handle ConstantVector here, because
00985   // we don't handle undef in any particularly useful way.
00986   if (ConstantDataSequential *CDS = dyn_cast<ConstantDataSequential>(V)) {
00987     // We know that CDS must be a vector of integers. Take the intersection of
00988     // each element.
00989     KnownZero.setAllBits(); KnownOne.setAllBits();
00990     APInt Elt(KnownZero.getBitWidth(), 0);
00991     for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
00992       Elt = CDS->getElementAsInteger(i);
00993       KnownZero &= ~Elt;
00994       KnownOne &= Elt;
00995     }
00996     return;
00997   }
00998 
00999   // The address of an aligned GlobalValue has trailing zeros.
01000   if (auto *GO = dyn_cast<GlobalObject>(V)) {
01001     unsigned Align = GO->getAlignment();
01002     if (Align == 0) {
01003       if (auto *GVar = dyn_cast<GlobalVariable>(GO)) {
01004         Type *ObjectType = GVar->getType()->getElementType();
01005         if (ObjectType->isSized()) {
01006           // If the object is defined in the current Module, we'll be giving
01007           // it the preferred alignment. Otherwise, we have to assume that it
01008           // may only have the minimum ABI alignment.
01009           if (!GVar->isDeclaration() && !GVar->isWeakForLinker())
01010             Align = DL.getPreferredAlignment(GVar);
01011           else
01012             Align = DL.getABITypeAlignment(ObjectType);
01013         }
01014       }
01015     }
01016     if (Align > 0)
01017       KnownZero = APInt::getLowBitsSet(BitWidth,
01018                                        countTrailingZeros(Align));
01019     else
01020       KnownZero.clearAllBits();
01021     KnownOne.clearAllBits();
01022     return;
01023   }
01024 
01025   if (Argument *A = dyn_cast<Argument>(V)) {
01026     unsigned Align = A->getType()->isPointerTy() ? A->getParamAlignment() : 0;
01027 
01028     if (!Align && A->hasStructRetAttr()) {
01029       // An sret parameter has at least the ABI alignment of the return type.
01030       Type *EltTy = cast<PointerType>(A->getType())->getElementType();
01031       if (EltTy->isSized())
01032         Align = DL.getABITypeAlignment(EltTy);
01033     }
01034 
01035     if (Align)
01036       KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align));
01037     else
01038       KnownZero.clearAllBits();
01039     KnownOne.clearAllBits();
01040 
01041     // Don't give up yet... there might be an assumption that provides more
01042     // information...
01043     computeKnownBitsFromAssume(V, KnownZero, KnownOne, DL, Depth, Q);
01044 
01045     // Or a dominating condition for that matter
01046     if (EnableDomConditions && Depth <= DomConditionsMaxDepth)
01047       computeKnownBitsFromDominatingCondition(V, KnownZero, KnownOne, DL,
01048                                               Depth, Q);
01049     return;
01050   }
01051 
01052   // Start out not knowing anything.
01053   KnownZero.clearAllBits(); KnownOne.clearAllBits();
01054 
01055   // Limit search depth.
01056   // All recursive calls that increase depth must come after this.
01057   if (Depth == MaxDepth)
01058     return;  
01059 
01060   // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has
01061   // the bits of its aliasee.
01062   if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
01063     if (!GA->mayBeOverridden())
01064       computeKnownBits(GA->getAliasee(), KnownZero, KnownOne, DL, Depth + 1, Q);
01065     return;
01066   }
01067 
01068   // Check whether a nearby assume intrinsic can determine some known bits.
01069   computeKnownBitsFromAssume(V, KnownZero, KnownOne, DL, Depth, Q);
01070 
01071   // Check whether there's a dominating condition which implies something about
01072   // this value at the given context.
01073   if (EnableDomConditions && Depth <= DomConditionsMaxDepth)
01074     computeKnownBitsFromDominatingCondition(V, KnownZero, KnownOne, DL, Depth,
01075                                             Q);
01076 
01077   Operator *I = dyn_cast<Operator>(V);
01078   if (!I) return;
01079 
01080   APInt KnownZero2(KnownZero), KnownOne2(KnownOne);
01081   switch (I->getOpcode()) {
01082   default: break;
01083   case Instruction::Load:
01084     if (MDNode *MD = cast<LoadInst>(I)->getMetadata(LLVMContext::MD_range))
01085       computeKnownBitsFromRangeMetadata(*MD, KnownZero);
01086     break;
01087   case Instruction::And: {
01088     // If either the LHS or the RHS are Zero, the result is zero.
01089     computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q);
01090     computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
01091 
01092     // Output known-1 bits are only known if set in both the LHS & RHS.
01093     KnownOne &= KnownOne2;
01094     // Output known-0 are known to be clear if zero in either the LHS | RHS.
01095     KnownZero |= KnownZero2;
01096     break;
01097   }
01098   case Instruction::Or: {
01099     computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q);
01100     computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
01101 
01102     // Output known-0 bits are only known if clear in both the LHS & RHS.
01103     KnownZero &= KnownZero2;
01104     // Output known-1 are known to be set if set in either the LHS | RHS.
01105     KnownOne |= KnownOne2;
01106     break;
01107   }
01108   case Instruction::Xor: {
01109     computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q);
01110     computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
01111 
01112     // Output known-0 bits are known if clear or set in both the LHS & RHS.
01113     APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
01114     // Output known-1 are known to be set if set in only one of the LHS, RHS.
01115     KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
01116     KnownZero = KnownZeroOut;
01117     break;
01118   }
01119   case Instruction::Mul: {
01120     bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
01121     computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW, KnownZero,
01122                         KnownOne, KnownZero2, KnownOne2, DL, Depth, Q);
01123     break;
01124   }
01125   case Instruction::UDiv: {
01126     // For the purposes of computing leading zeros we can conservatively
01127     // treat a udiv as a logical right shift by the power of 2 known to
01128     // be less than the denominator.
01129     computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
01130     unsigned LeadZ = KnownZero2.countLeadingOnes();
01131 
01132     KnownOne2.clearAllBits();
01133     KnownZero2.clearAllBits();
01134     computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, DL, Depth + 1, Q);
01135     unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
01136     if (RHSUnknownLeadingOnes != BitWidth)
01137       LeadZ = std::min(BitWidth,
01138                        LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
01139 
01140     KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
01141     break;
01142   }
01143   case Instruction::Select:
01144     computeKnownBits(I->getOperand(2), KnownZero, KnownOne, DL, Depth + 1, Q);
01145     computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, DL, Depth + 1, Q);
01146 
01147     // Only known if known in both the LHS and RHS.
01148     KnownOne &= KnownOne2;
01149     KnownZero &= KnownZero2;
01150     break;
01151   case Instruction::FPTrunc:
01152   case Instruction::FPExt:
01153   case Instruction::FPToUI:
01154   case Instruction::FPToSI:
01155   case Instruction::SIToFP:
01156   case Instruction::UIToFP:
01157     break; // Can't work with floating point.
01158   case Instruction::PtrToInt:
01159   case Instruction::IntToPtr:
01160   case Instruction::AddrSpaceCast: // Pointers could be different sizes.
01161     // FALL THROUGH and handle them the same as zext/trunc.
01162   case Instruction::ZExt:
01163   case Instruction::Trunc: {
01164     Type *SrcTy = I->getOperand(0)->getType();
01165 
01166     unsigned SrcBitWidth;
01167     // Note that we handle pointer operands here because of inttoptr/ptrtoint
01168     // which fall through here.
01169     SrcBitWidth = DL.getTypeSizeInBits(SrcTy->getScalarType());
01170 
01171     assert(SrcBitWidth && "SrcBitWidth can't be zero");
01172     KnownZero = KnownZero.zextOrTrunc(SrcBitWidth);
01173     KnownOne = KnownOne.zextOrTrunc(SrcBitWidth);
01174     computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
01175     KnownZero = KnownZero.zextOrTrunc(BitWidth);
01176     KnownOne = KnownOne.zextOrTrunc(BitWidth);
01177     // Any top bits are known to be zero.
01178     if (BitWidth > SrcBitWidth)
01179       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth);
01180     break;
01181   }
01182   case Instruction::BitCast: {
01183     Type *SrcTy = I->getOperand(0)->getType();
01184     if ((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
01185         // TODO: For now, not handling conversions like:
01186         // (bitcast i64 %x to <2 x i32>)
01187         !I->getType()->isVectorTy()) {
01188       computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
01189       break;
01190     }
01191     break;
01192   }
01193   case Instruction::SExt: {
01194     // Compute the bits in the result that are not present in the input.
01195     unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
01196 
01197     KnownZero = KnownZero.trunc(SrcBitWidth);
01198     KnownOne = KnownOne.trunc(SrcBitWidth);
01199     computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
01200     KnownZero = KnownZero.zext(BitWidth);
01201     KnownOne = KnownOne.zext(BitWidth);
01202 
01203     // If the sign bit of the input is known set or clear, then we know the
01204     // top bits of the result.
01205     if (KnownZero[SrcBitWidth-1])             // Input sign bit known zero
01206       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth);
01207     else if (KnownOne[SrcBitWidth-1])           // Input sign bit known set
01208       KnownOne |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth);
01209     break;
01210   }
01211   case Instruction::Shl:
01212     // (shl X, C1) & C2 == 0   iff   (X & C2 >>u C1) == 0
01213     if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
01214       uint64_t ShiftAmt = SA->getLimitedValue(BitWidth);
01215       computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
01216       KnownZero <<= ShiftAmt;
01217       KnownOne  <<= ShiftAmt;
01218       KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); // low bits known 0
01219     }
01220     break;
01221   case Instruction::LShr:
01222     // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
01223     if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
01224       // Compute the new bits that are at the top now.
01225       uint64_t ShiftAmt = SA->getLimitedValue(BitWidth);
01226 
01227       // Unsigned shift right.
01228       computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
01229       KnownZero = APIntOps::lshr(KnownZero, ShiftAmt);
01230       KnownOne  = APIntOps::lshr(KnownOne, ShiftAmt);
01231       // high bits known zero.
01232       KnownZero |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
01233     }
01234     break;
01235   case Instruction::AShr:
01236     // (ashr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
01237     if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
01238       // Compute the new bits that are at the top now.
01239       uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
01240 
01241       // Signed shift right.
01242       computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
01243       KnownZero = APIntOps::lshr(KnownZero, ShiftAmt);
01244       KnownOne  = APIntOps::lshr(KnownOne, ShiftAmt);
01245 
01246       APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt));
01247       if (KnownZero[BitWidth-ShiftAmt-1])    // New bits are known zero.
01248         KnownZero |= HighBits;
01249       else if (KnownOne[BitWidth-ShiftAmt-1])  // New bits are known one.
01250         KnownOne |= HighBits;
01251     }
01252     break;
01253   case Instruction::Sub: {
01254     bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
01255     computeKnownBitsAddSub(false, I->getOperand(0), I->getOperand(1), NSW,
01256                            KnownZero, KnownOne, KnownZero2, KnownOne2, DL,
01257                            Depth, Q);
01258     break;
01259   }
01260   case Instruction::Add: {
01261     bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
01262     computeKnownBitsAddSub(true, I->getOperand(0), I->getOperand(1), NSW,
01263                            KnownZero, KnownOne, KnownZero2, KnownOne2, DL,
01264                            Depth, Q);
01265     break;
01266   }
01267   case Instruction::SRem:
01268     if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
01269       APInt RA = Rem->getValue().abs();
01270       if (RA.isPowerOf2()) {
01271         APInt LowBits = RA - 1;
01272         computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1,
01273                          Q);
01274 
01275         // The low bits of the first operand are unchanged by the srem.
01276         KnownZero = KnownZero2 & LowBits;
01277         KnownOne = KnownOne2 & LowBits;
01278 
01279         // If the first operand is non-negative or has all low bits zero, then
01280         // the upper bits are all zero.
01281         if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
01282           KnownZero |= ~LowBits;
01283 
01284         // If the first operand is negative and not all low bits are zero, then
01285         // the upper bits are all one.
01286         if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
01287           KnownOne |= ~LowBits;
01288 
01289         assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
01290       }
01291     }
01292 
01293     // The sign bit is the LHS's sign bit, except when the result of the
01294     // remainder is zero.
01295     if (KnownZero.isNonNegative()) {
01296       APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
01297       computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, DL,
01298                        Depth + 1, Q);
01299       // If it's known zero, our sign bit is also zero.
01300       if (LHSKnownZero.isNegative())
01301         KnownZero.setBit(BitWidth - 1);
01302     }
01303 
01304     break;
01305   case Instruction::URem: {
01306     if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
01307       APInt RA = Rem->getValue();
01308       if (RA.isPowerOf2()) {
01309         APInt LowBits = (RA - 1);
01310         computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1,
01311                          Q);
01312         KnownZero |= ~LowBits;
01313         KnownOne &= LowBits;
01314         break;
01315       }
01316     }
01317 
01318     // Since the result is less than or equal to either operand, any leading
01319     // zero bits in either operand must also exist in the result.
01320     computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
01321     computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, DL, Depth + 1, Q);
01322 
01323     unsigned Leaders = std::max(KnownZero.countLeadingOnes(),
01324                                 KnownZero2.countLeadingOnes());
01325     KnownOne.clearAllBits();
01326     KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
01327     break;
01328   }
01329 
01330   case Instruction::Alloca: {
01331     AllocaInst *AI = cast<AllocaInst>(V);
01332     unsigned Align = AI->getAlignment();
01333     if (Align == 0)
01334       Align = DL.getABITypeAlignment(AI->getType()->getElementType());
01335 
01336     if (Align > 0)
01337       KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align));
01338     break;
01339   }
01340   case Instruction::GetElementPtr: {
01341     // Analyze all of the subscripts of this getelementptr instruction
01342     // to determine if we can prove known low zero bits.
01343     APInt LocalKnownZero(BitWidth, 0), LocalKnownOne(BitWidth, 0);
01344     computeKnownBits(I->getOperand(0), LocalKnownZero, LocalKnownOne, DL,
01345                      Depth + 1, Q);
01346     unsigned TrailZ = LocalKnownZero.countTrailingOnes();
01347 
01348     gep_type_iterator GTI = gep_type_begin(I);
01349     for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) {
01350       Value *Index = I->getOperand(i);
01351       if (StructType *STy = dyn_cast<StructType>(*GTI)) {
01352         // Handle struct member offset arithmetic.
01353 
01354         // Handle case when index is vector zeroinitializer
01355         Constant *CIndex = cast<Constant>(Index);
01356         if (CIndex->isZeroValue())
01357           continue;
01358 
01359         if (CIndex->getType()->isVectorTy())
01360           Index = CIndex->getSplatValue();
01361 
01362         unsigned Idx = cast<ConstantInt>(Index)->getZExtValue();
01363         const StructLayout *SL = DL.getStructLayout(STy);
01364         uint64_t Offset = SL->getElementOffset(Idx);
01365         TrailZ = std::min<unsigned>(TrailZ,
01366                                     countTrailingZeros(Offset));
01367       } else {
01368         // Handle array index arithmetic.
01369         Type *IndexedTy = GTI.getIndexedType();
01370         if (!IndexedTy->isSized()) {
01371           TrailZ = 0;
01372           break;
01373         }
01374         unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits();
01375         uint64_t TypeSize = DL.getTypeAllocSize(IndexedTy);
01376         LocalKnownZero = LocalKnownOne = APInt(GEPOpiBits, 0);
01377         computeKnownBits(Index, LocalKnownZero, LocalKnownOne, DL, Depth + 1,
01378                          Q);
01379         TrailZ = std::min(TrailZ,
01380                           unsigned(countTrailingZeros(TypeSize) +
01381                                    LocalKnownZero.countTrailingOnes()));
01382       }
01383     }
01384 
01385     KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ);
01386     break;
01387   }
01388   case Instruction::PHI: {
01389     PHINode *P = cast<PHINode>(I);
01390     // Handle the case of a simple two-predecessor recurrence PHI.
01391     // There's a lot more that could theoretically be done here, but
01392     // this is sufficient to catch some interesting cases.
01393     if (P->getNumIncomingValues() == 2) {
01394       for (unsigned i = 0; i != 2; ++i) {
01395         Value *L = P->getIncomingValue(i);
01396         Value *R = P->getIncomingValue(!i);
01397         Operator *LU = dyn_cast<Operator>(L);
01398         if (!LU)
01399           continue;
01400         unsigned Opcode = LU->getOpcode();
01401         // Check for operations that have the property that if
01402         // both their operands have low zero bits, the result
01403         // will have low zero bits.
01404         if (Opcode == Instruction::Add ||
01405             Opcode == Instruction::Sub ||
01406             Opcode == Instruction::And ||
01407             Opcode == Instruction::Or ||
01408             Opcode == Instruction::Mul) {
01409           Value *LL = LU->getOperand(0);
01410           Value *LR = LU->getOperand(1);
01411           // Find a recurrence.
01412           if (LL == I)
01413             L = LR;
01414           else if (LR == I)
01415             L = LL;
01416           else
01417             break;
01418           // Ok, we have a PHI of the form L op= R. Check for low
01419           // zero bits.
01420           computeKnownBits(R, KnownZero2, KnownOne2, DL, Depth + 1, Q);
01421 
01422           // We need to take the minimum number of known bits
01423           APInt KnownZero3(KnownZero), KnownOne3(KnownOne);
01424           computeKnownBits(L, KnownZero3, KnownOne3, DL, Depth + 1, Q);
01425 
01426           KnownZero = APInt::getLowBitsSet(BitWidth,
01427                                            std::min(KnownZero2.countTrailingOnes(),
01428                                                     KnownZero3.countTrailingOnes()));
01429           break;
01430         }
01431       }
01432     }
01433 
01434     // Unreachable blocks may have zero-operand PHI nodes.
01435     if (P->getNumIncomingValues() == 0)
01436       break;
01437 
01438     // Otherwise take the unions of the known bit sets of the operands,
01439     // taking conservative care to avoid excessive recursion.
01440     if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) {
01441       // Skip if every incoming value references to ourself.
01442       if (dyn_cast_or_null<UndefValue>(P->hasConstantValue()))
01443         break;
01444 
01445       KnownZero = APInt::getAllOnesValue(BitWidth);
01446       KnownOne = APInt::getAllOnesValue(BitWidth);
01447       for (Value *IncValue : P->incoming_values()) {
01448         // Skip direct self references.
01449         if (IncValue == P) continue;
01450 
01451         KnownZero2 = APInt(BitWidth, 0);
01452         KnownOne2 = APInt(BitWidth, 0);
01453         // Recurse, but cap the recursion to one level, because we don't
01454         // want to waste time spinning around in loops.
01455         computeKnownBits(IncValue, KnownZero2, KnownOne2, DL,
01456                          MaxDepth - 1, Q);
01457         KnownZero &= KnownZero2;
01458         KnownOne &= KnownOne2;
01459         // If all bits have been ruled out, there's no need to check
01460         // more operands.
01461         if (!KnownZero && !KnownOne)
01462           break;
01463       }
01464     }
01465     break;
01466   }
01467   case Instruction::Call:
01468   case Instruction::Invoke:
01469     if (MDNode *MD = cast<Instruction>(I)->getMetadata(LLVMContext::MD_range))
01470       computeKnownBitsFromRangeMetadata(*MD, KnownZero);
01471     // If a range metadata is attached to this IntrinsicInst, intersect the
01472     // explicit range specified by the metadata and the implicit range of
01473     // the intrinsic.
01474     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
01475       switch (II->getIntrinsicID()) {
01476       default: break;
01477       case Intrinsic::ctlz:
01478       case Intrinsic::cttz: {
01479         unsigned LowBits = Log2_32(BitWidth)+1;
01480         // If this call is undefined for 0, the result will be less than 2^n.
01481         if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext()))
01482           LowBits -= 1;
01483         KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
01484         break;
01485       }
01486       case Intrinsic::ctpop: {
01487         unsigned LowBits = Log2_32(BitWidth)+1;
01488         KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
01489         break;
01490       }
01491       case Intrinsic::x86_sse42_crc32_64_64:
01492         KnownZero |= APInt::getHighBitsSet(64, 32);
01493         break;
01494       }
01495     }
01496     break;
01497   case Instruction::ExtractValue:
01498     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) {
01499       ExtractValueInst *EVI = cast<ExtractValueInst>(I);
01500       if (EVI->getNumIndices() != 1) break;
01501       if (EVI->getIndices()[0] == 0) {
01502         switch (II->getIntrinsicID()) {
01503         default: break;
01504         case Intrinsic::uadd_with_overflow:
01505         case Intrinsic::sadd_with_overflow:
01506           computeKnownBitsAddSub(true, II->getArgOperand(0),
01507                                  II->getArgOperand(1), false, KnownZero,
01508                                  KnownOne, KnownZero2, KnownOne2, DL, Depth, Q);
01509           break;
01510         case Intrinsic::usub_with_overflow:
01511         case Intrinsic::ssub_with_overflow:
01512           computeKnownBitsAddSub(false, II->getArgOperand(0),
01513                                  II->getArgOperand(1), false, KnownZero,
01514                                  KnownOne, KnownZero2, KnownOne2, DL, Depth, Q);
01515           break;
01516         case Intrinsic::umul_with_overflow:
01517         case Intrinsic::smul_with_overflow:
01518           computeKnownBitsMul(II->getArgOperand(0), II->getArgOperand(1), false,
01519                               KnownZero, KnownOne, KnownZero2, KnownOne2, DL,
01520                               Depth, Q);
01521           break;
01522         }
01523       }
01524     }
01525   }
01526 
01527   assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
01528 }
01529 
01530 /// Determine whether the sign bit is known to be zero or one.
01531 /// Convenience wrapper around computeKnownBits.
01532 void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne,
01533                     const DataLayout &DL, unsigned Depth, const Query &Q) {
01534   unsigned BitWidth = getBitWidth(V->getType(), DL);
01535   if (!BitWidth) {
01536     KnownZero = false;
01537     KnownOne = false;
01538     return;
01539   }
01540   APInt ZeroBits(BitWidth, 0);
01541   APInt OneBits(BitWidth, 0);
01542   computeKnownBits(V, ZeroBits, OneBits, DL, Depth, Q);
01543   KnownOne = OneBits[BitWidth - 1];
01544   KnownZero = ZeroBits[BitWidth - 1];
01545 }
01546 
01547 /// Return true if the given value is known to have exactly one
01548 /// bit set when defined. For vectors return true if every element is known to
01549 /// be a power of two when defined. Supports values with integer or pointer
01550 /// types and vectors of integers.
01551 bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth,
01552                             const Query &Q, const DataLayout &DL) {
01553   if (Constant *C = dyn_cast<Constant>(V)) {
01554     if (C->isNullValue())
01555       return OrZero;
01556     if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
01557       return CI->getValue().isPowerOf2();
01558     // TODO: Handle vector constants.
01559   }
01560 
01561   // 1 << X is clearly a power of two if the one is not shifted off the end.  If
01562   // it is shifted off the end then the result is undefined.
01563   if (match(V, m_Shl(m_One(), m_Value())))
01564     return true;
01565 
01566   // (signbit) >>l X is clearly a power of two if the one is not shifted off the
01567   // bottom.  If it is shifted off the bottom then the result is undefined.
01568   if (match(V, m_LShr(m_SignBit(), m_Value())))
01569     return true;
01570 
01571   // The remaining tests are all recursive, so bail out if we hit the limit.
01572   if (Depth++ == MaxDepth)
01573     return false;
01574 
01575   Value *X = nullptr, *Y = nullptr;
01576   // A shift of a power of two is a power of two or zero.
01577   if (OrZero && (match(V, m_Shl(m_Value(X), m_Value())) ||
01578                  match(V, m_Shr(m_Value(X), m_Value()))))
01579     return isKnownToBeAPowerOfTwo(X, /*OrZero*/ true, Depth, Q, DL);
01580 
01581   if (ZExtInst *ZI = dyn_cast<ZExtInst>(V))
01582     return isKnownToBeAPowerOfTwo(ZI->getOperand(0), OrZero, Depth, Q, DL);
01583 
01584   if (SelectInst *SI = dyn_cast<SelectInst>(V))
01585     return isKnownToBeAPowerOfTwo(SI->getTrueValue(), OrZero, Depth, Q, DL) &&
01586            isKnownToBeAPowerOfTwo(SI->getFalseValue(), OrZero, Depth, Q, DL);
01587 
01588   if (OrZero && match(V, m_And(m_Value(X), m_Value(Y)))) {
01589     // A power of two and'd with anything is a power of two or zero.
01590     if (isKnownToBeAPowerOfTwo(X, /*OrZero*/ true, Depth, Q, DL) ||
01591         isKnownToBeAPowerOfTwo(Y, /*OrZero*/ true, Depth, Q, DL))
01592       return true;
01593     // X & (-X) is always a power of two or zero.
01594     if (match(X, m_Neg(m_Specific(Y))) || match(Y, m_Neg(m_Specific(X))))
01595       return true;
01596     return false;
01597   }
01598 
01599   // Adding a power-of-two or zero to the same power-of-two or zero yields
01600   // either the original power-of-two, a larger power-of-two or zero.
01601   if (match(V, m_Add(m_Value(X), m_Value(Y)))) {
01602     OverflowingBinaryOperator *VOBO = cast<OverflowingBinaryOperator>(V);
01603     if (OrZero || VOBO->hasNoUnsignedWrap() || VOBO->hasNoSignedWrap()) {
01604       if (match(X, m_And(m_Specific(Y), m_Value())) ||
01605           match(X, m_And(m_Value(), m_Specific(Y))))
01606         if (isKnownToBeAPowerOfTwo(Y, OrZero, Depth, Q, DL))
01607           return true;
01608       if (match(Y, m_And(m_Specific(X), m_Value())) ||
01609           match(Y, m_And(m_Value(), m_Specific(X))))
01610         if (isKnownToBeAPowerOfTwo(X, OrZero, Depth, Q, DL))
01611           return true;
01612 
01613       unsigned BitWidth = V->getType()->getScalarSizeInBits();
01614       APInt LHSZeroBits(BitWidth, 0), LHSOneBits(BitWidth, 0);
01615       computeKnownBits(X, LHSZeroBits, LHSOneBits, DL, Depth, Q);
01616 
01617       APInt RHSZeroBits(BitWidth, 0), RHSOneBits(BitWidth, 0);
01618       computeKnownBits(Y, RHSZeroBits, RHSOneBits, DL, Depth, Q);
01619       // If i8 V is a power of two or zero:
01620       //  ZeroBits: 1 1 1 0 1 1 1 1
01621       // ~ZeroBits: 0 0 0 1 0 0 0 0
01622       if ((~(LHSZeroBits & RHSZeroBits)).isPowerOf2())
01623         // If OrZero isn't set, we cannot give back a zero result.
01624         // Make sure either the LHS or RHS has a bit set.
01625         if (OrZero || RHSOneBits.getBoolValue() || LHSOneBits.getBoolValue())
01626           return true;
01627     }
01628   }
01629 
01630   // An exact divide or right shift can only shift off zero bits, so the result
01631   // is a power of two only if the first operand is a power of two and not
01632   // copying a sign bit (sdiv int_min, 2).
01633   if (match(V, m_Exact(m_LShr(m_Value(), m_Value()))) ||
01634       match(V, m_Exact(m_UDiv(m_Value(), m_Value())))) {
01635     return isKnownToBeAPowerOfTwo(cast<Operator>(V)->getOperand(0), OrZero,
01636                                   Depth, Q, DL);
01637   }
01638 
01639   return false;
01640 }
01641 
01642 /// \brief Test whether a GEP's result is known to be non-null.
01643 ///
01644 /// Uses properties inherent in a GEP to try to determine whether it is known
01645 /// to be non-null.
01646 ///
01647 /// Currently this routine does not support vector GEPs.
01648 static bool isGEPKnownNonNull(GEPOperator *GEP, const DataLayout &DL,
01649                               unsigned Depth, const Query &Q) {
01650   if (!GEP->isInBounds() || GEP->getPointerAddressSpace() != 0)
01651     return false;
01652 
01653   // FIXME: Support vector-GEPs.
01654   assert(GEP->getType()->isPointerTy() && "We only support plain pointer GEP");
01655 
01656   // If the base pointer is non-null, we cannot walk to a null address with an
01657   // inbounds GEP in address space zero.
01658   if (isKnownNonZero(GEP->getPointerOperand(), DL, Depth, Q))
01659     return true;
01660 
01661   // Walk the GEP operands and see if any operand introduces a non-zero offset.
01662   // If so, then the GEP cannot produce a null pointer, as doing so would
01663   // inherently violate the inbounds contract within address space zero.
01664   for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
01665        GTI != GTE; ++GTI) {
01666     // Struct types are easy -- they must always be indexed by a constant.
01667     if (StructType *STy = dyn_cast<StructType>(*GTI)) {
01668       ConstantInt *OpC = cast<ConstantInt>(GTI.getOperand());
01669       unsigned ElementIdx = OpC->getZExtValue();
01670       const StructLayout *SL = DL.getStructLayout(STy);
01671       uint64_t ElementOffset = SL->getElementOffset(ElementIdx);
01672       if (ElementOffset > 0)
01673         return true;
01674       continue;
01675     }
01676 
01677     // If we have a zero-sized type, the index doesn't matter. Keep looping.
01678     if (DL.getTypeAllocSize(GTI.getIndexedType()) == 0)
01679       continue;
01680 
01681     // Fast path the constant operand case both for efficiency and so we don't
01682     // increment Depth when just zipping down an all-constant GEP.
01683     if (ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand())) {
01684       if (!OpC->isZero())
01685         return true;
01686       continue;
01687     }
01688 
01689     // We post-increment Depth here because while isKnownNonZero increments it
01690     // as well, when we pop back up that increment won't persist. We don't want
01691     // to recurse 10k times just because we have 10k GEP operands. We don't
01692     // bail completely out because we want to handle constant GEPs regardless
01693     // of depth.
01694     if (Depth++ >= MaxDepth)
01695       continue;
01696 
01697     if (isKnownNonZero(GTI.getOperand(), DL, Depth, Q))
01698       return true;
01699   }
01700 
01701   return false;
01702 }
01703 
01704 /// Does the 'Range' metadata (which must be a valid MD_range operand list)
01705 /// ensure that the value it's attached to is never Value?  'RangeType' is
01706 /// is the type of the value described by the range.
01707 static bool rangeMetadataExcludesValue(MDNode* Ranges,
01708                                        const APInt& Value) {
01709   const unsigned NumRanges = Ranges->getNumOperands() / 2;
01710   assert(NumRanges >= 1);
01711   for (unsigned i = 0; i < NumRanges; ++i) {
01712     ConstantInt *Lower =
01713         mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 0));
01714     ConstantInt *Upper =
01715         mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 1));
01716     ConstantRange Range(Lower->getValue(), Upper->getValue());
01717     if (Range.contains(Value))
01718       return false;
01719   }
01720   return true;
01721 }
01722 
01723 /// Return true if the given value is known to be non-zero when defined.
01724 /// For vectors return true if every element is known to be non-zero when
01725 /// defined. Supports values with integer or pointer type and vectors of
01726 /// integers.
01727 bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
01728                     const Query &Q) {
01729   if (Constant *C = dyn_cast<Constant>(V)) {
01730     if (C->isNullValue())
01731       return false;
01732     if (isa<ConstantInt>(C))
01733       // Must be non-zero due to null test above.
01734       return true;
01735     // TODO: Handle vectors
01736     return false;
01737   }
01738 
01739   if (Instruction* I = dyn_cast<Instruction>(V)) {
01740     if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range)) {
01741       // If the possible ranges don't contain zero, then the value is
01742       // definitely non-zero.
01743       if (IntegerType* Ty = dyn_cast<IntegerType>(V->getType())) {
01744         const APInt ZeroValue(Ty->getBitWidth(), 0);
01745         if (rangeMetadataExcludesValue(Ranges, ZeroValue))
01746           return true;
01747       }
01748     }
01749   }
01750 
01751   // The remaining tests are all recursive, so bail out if we hit the limit.
01752   if (Depth++ >= MaxDepth)
01753     return false;
01754 
01755   // Check for pointer simplifications.
01756   if (V->getType()->isPointerTy()) {
01757     if (isKnownNonNull(V))
01758       return true; 
01759     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V))
01760       if (isGEPKnownNonNull(GEP, DL, Depth, Q))
01761         return true;
01762   }
01763 
01764   unsigned BitWidth = getBitWidth(V->getType()->getScalarType(), DL);
01765 
01766   // X | Y != 0 if X != 0 or Y != 0.
01767   Value *X = nullptr, *Y = nullptr;
01768   if (match(V, m_Or(m_Value(X), m_Value(Y))))
01769     return isKnownNonZero(X, DL, Depth, Q) || isKnownNonZero(Y, DL, Depth, Q);
01770 
01771   // ext X != 0 if X != 0.
01772   if (isa<SExtInst>(V) || isa<ZExtInst>(V))
01773     return isKnownNonZero(cast<Instruction>(V)->getOperand(0), DL, Depth, Q);
01774 
01775   // shl X, Y != 0 if X is odd.  Note that the value of the shift is undefined
01776   // if the lowest bit is shifted off the end.
01777   if (BitWidth && match(V, m_Shl(m_Value(X), m_Value(Y)))) {
01778     // shl nuw can't remove any non-zero bits.
01779     OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V);
01780     if (BO->hasNoUnsignedWrap())
01781       return isKnownNonZero(X, DL, Depth, Q);
01782 
01783     APInt KnownZero(BitWidth, 0);
01784     APInt KnownOne(BitWidth, 0);
01785     computeKnownBits(X, KnownZero, KnownOne, DL, Depth, Q);
01786     if (KnownOne[0])
01787       return true;
01788   }
01789   // shr X, Y != 0 if X is negative.  Note that the value of the shift is not
01790   // defined if the sign bit is shifted off the end.
01791   else if (match(V, m_Shr(m_Value(X), m_Value(Y)))) {
01792     // shr exact can only shift out zero bits.
01793     PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V);
01794     if (BO->isExact())
01795       return isKnownNonZero(X, DL, Depth, Q);
01796 
01797     bool XKnownNonNegative, XKnownNegative;
01798     ComputeSignBit(X, XKnownNonNegative, XKnownNegative, DL, Depth, Q);
01799     if (XKnownNegative)
01800       return true;
01801   }
01802   // div exact can only produce a zero if the dividend is zero.
01803   else if (match(V, m_Exact(m_IDiv(m_Value(X), m_Value())))) {
01804     return isKnownNonZero(X, DL, Depth, Q);
01805   }
01806   // X + Y.
01807   else if (match(V, m_Add(m_Value(X), m_Value(Y)))) {
01808     bool XKnownNonNegative, XKnownNegative;
01809     bool YKnownNonNegative, YKnownNegative;
01810     ComputeSignBit(X, XKnownNonNegative, XKnownNegative, DL, Depth, Q);
01811     ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, DL, Depth, Q);
01812 
01813     // If X and Y are both non-negative (as signed values) then their sum is not
01814     // zero unless both X and Y are zero.
01815     if (XKnownNonNegative && YKnownNonNegative)
01816       if (isKnownNonZero(X, DL, Depth, Q) || isKnownNonZero(Y, DL, Depth, Q))
01817         return true;
01818 
01819     // If X and Y are both negative (as signed values) then their sum is not
01820     // zero unless both X and Y equal INT_MIN.
01821     if (BitWidth && XKnownNegative && YKnownNegative) {
01822       APInt KnownZero(BitWidth, 0);
01823       APInt KnownOne(BitWidth, 0);
01824       APInt Mask = APInt::getSignedMaxValue(BitWidth);
01825       // The sign bit of X is set.  If some other bit is set then X is not equal
01826       // to INT_MIN.
01827       computeKnownBits(X, KnownZero, KnownOne, DL, Depth, Q);
01828       if ((KnownOne & Mask) != 0)
01829         return true;
01830       // The sign bit of Y is set.  If some other bit is set then Y is not equal
01831       // to INT_MIN.
01832       computeKnownBits(Y, KnownZero, KnownOne, DL, Depth, Q);
01833       if ((KnownOne & Mask) != 0)
01834         return true;
01835     }
01836 
01837     // The sum of a non-negative number and a power of two is not zero.
01838     if (XKnownNonNegative &&
01839         isKnownToBeAPowerOfTwo(Y, /*OrZero*/ false, Depth, Q, DL))
01840       return true;
01841     if (YKnownNonNegative &&
01842         isKnownToBeAPowerOfTwo(X, /*OrZero*/ false, Depth, Q, DL))
01843       return true;
01844   }
01845   // X * Y.
01846   else if (match(V, m_Mul(m_Value(X), m_Value(Y)))) {
01847     OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V);
01848     // If X and Y are non-zero then so is X * Y as long as the multiplication
01849     // does not overflow.
01850     if ((BO->hasNoSignedWrap() || BO->hasNoUnsignedWrap()) &&
01851         isKnownNonZero(X, DL, Depth, Q) && isKnownNonZero(Y, DL, Depth, Q))
01852       return true;
01853   }
01854   // (C ? X : Y) != 0 if X != 0 and Y != 0.
01855   else if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
01856     if (isKnownNonZero(SI->getTrueValue(), DL, Depth, Q) &&
01857         isKnownNonZero(SI->getFalseValue(), DL, Depth, Q))
01858       return true;
01859   }
01860 
01861   if (!BitWidth) return false;
01862   APInt KnownZero(BitWidth, 0);
01863   APInt KnownOne(BitWidth, 0);
01864   computeKnownBits(V, KnownZero, KnownOne, DL, Depth, Q);
01865   return KnownOne != 0;
01866 }
01867 
01868 /// Return true if 'V & Mask' is known to be zero.  We use this predicate to
01869 /// simplify operations downstream. Mask is known to be zero for bits that V
01870 /// cannot have.
01871 ///
01872 /// This function is defined on values with integer type, values with pointer
01873 /// type, and vectors of integers.  In the case
01874 /// where V is a vector, the mask, known zero, and known one values are the
01875 /// same width as the vector element, and the bit is set only if it is true
01876 /// for all of the elements in the vector.
01877 bool MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout &DL,
01878                        unsigned Depth, const Query &Q) {
01879   APInt KnownZero(Mask.getBitWidth(), 0), KnownOne(Mask.getBitWidth(), 0);
01880   computeKnownBits(V, KnownZero, KnownOne, DL, Depth, Q);
01881   return (KnownZero & Mask) == Mask;
01882 }
01883 
01884 
01885 
01886 /// Return the number of times the sign bit of the register is replicated into
01887 /// the other bits. We know that at least 1 bit is always equal to the sign bit
01888 /// (itself), but other cases can give us information. For example, immediately
01889 /// after an "ashr X, 2", we know that the top 3 bits are all equal to each
01890 /// other, so we return 3.
01891 ///
01892 /// 'Op' must have a scalar integer type.
01893 ///
01894 unsigned ComputeNumSignBits(Value *V, const DataLayout &DL, unsigned Depth,
01895                             const Query &Q) {
01896   unsigned TyBits = DL.getTypeSizeInBits(V->getType()->getScalarType());
01897   unsigned Tmp, Tmp2;
01898   unsigned FirstAnswer = 1;
01899 
01900   // Note that ConstantInt is handled by the general computeKnownBits case
01901   // below.
01902 
01903   if (Depth == 6)
01904     return 1;  // Limit search depth.
01905 
01906   Operator *U = dyn_cast<Operator>(V);
01907   switch (Operator::getOpcode(V)) {
01908   default: break;
01909   case Instruction::SExt:
01910     Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits();
01911     return ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q) + Tmp;
01912 
01913   case Instruction::SDiv: {
01914     const APInt *Denominator;
01915     // sdiv X, C -> adds log(C) sign bits.
01916     if (match(U->getOperand(1), m_APInt(Denominator))) {
01917 
01918       // Ignore non-positive denominator.
01919       if (!Denominator->isStrictlyPositive())
01920         break;
01921 
01922       // Calculate the incoming numerator bits.
01923       unsigned NumBits = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
01924 
01925       // Add floor(log(C)) bits to the numerator bits.
01926       return std::min(TyBits, NumBits + Denominator->logBase2());
01927     }
01928     break;
01929   }
01930 
01931   case Instruction::SRem: {
01932     const APInt *Denominator;
01933     // srem X, C -> we know that the result is within [-C+1,C) when C is a
01934     // positive constant.  This let us put a lower bound on the number of sign
01935     // bits.
01936     if (match(U->getOperand(1), m_APInt(Denominator))) {
01937 
01938       // Ignore non-positive denominator.
01939       if (!Denominator->isStrictlyPositive())
01940         break;
01941 
01942       // Calculate the incoming numerator bits. SRem by a positive constant
01943       // can't lower the number of sign bits.
01944       unsigned NumrBits =
01945           ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
01946 
01947       // Calculate the leading sign bit constraints by examining the
01948       // denominator.  Given that the denominator is positive, there are two
01949       // cases:
01950       //
01951       //  1. the numerator is positive.  The result range is [0,C) and [0,C) u<
01952       //     (1 << ceilLogBase2(C)).
01953       //
01954       //  2. the numerator is negative.  Then the result range is (-C,0] and
01955       //     integers in (-C,0] are either 0 or >u (-1 << ceilLogBase2(C)).
01956       //
01957       // Thus a lower bound on the number of sign bits is `TyBits -
01958       // ceilLogBase2(C)`.
01959 
01960       unsigned ResBits = TyBits - Denominator->ceilLogBase2();
01961       return std::max(NumrBits, ResBits);
01962     }
01963     break;
01964   }
01965 
01966   case Instruction::AShr: {
01967     Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
01968     // ashr X, C   -> adds C sign bits.  Vectors too.
01969     const APInt *ShAmt;
01970     if (match(U->getOperand(1), m_APInt(ShAmt))) {
01971       Tmp += ShAmt->getZExtValue();
01972       if (Tmp > TyBits) Tmp = TyBits;
01973     }
01974     return Tmp;
01975   }
01976   case Instruction::Shl: {
01977     const APInt *ShAmt;
01978     if (match(U->getOperand(1), m_APInt(ShAmt))) {
01979       // shl destroys sign bits.
01980       Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
01981       Tmp2 = ShAmt->getZExtValue();
01982       if (Tmp2 >= TyBits ||      // Bad shift.
01983           Tmp2 >= Tmp) break;    // Shifted all sign bits out.
01984       return Tmp - Tmp2;
01985     }
01986     break;
01987   }
01988   case Instruction::And:
01989   case Instruction::Or:
01990   case Instruction::Xor:    // NOT is handled here.
01991     // Logical binary ops preserve the number of sign bits at the worst.
01992     Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
01993     if (Tmp != 1) {
01994       Tmp2 = ComputeNumSignBits(U->getOperand(1), DL, Depth + 1, Q);
01995       FirstAnswer = std::min(Tmp, Tmp2);
01996       // We computed what we know about the sign bits as our first
01997       // answer. Now proceed to the generic code that uses
01998       // computeKnownBits, and pick whichever answer is better.
01999     }
02000     break;
02001 
02002   case Instruction::Select:
02003     Tmp = ComputeNumSignBits(U->getOperand(1), DL, Depth + 1, Q);
02004     if (Tmp == 1) return 1;  // Early out.
02005     Tmp2 = ComputeNumSignBits(U->getOperand(2), DL, Depth + 1, Q);
02006     return std::min(Tmp, Tmp2);
02007 
02008   case Instruction::Add:
02009     // Add can have at most one carry bit.  Thus we know that the output
02010     // is, at worst, one more bit than the inputs.
02011     Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
02012     if (Tmp == 1) return 1;  // Early out.
02013 
02014     // Special case decrementing a value (ADD X, -1):
02015     if (const auto *CRHS = dyn_cast<Constant>(U->getOperand(1)))
02016       if (CRHS->isAllOnesValue()) {
02017         APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
02018         computeKnownBits(U->getOperand(0), KnownZero, KnownOne, DL, Depth + 1,
02019                          Q);
02020 
02021         // If the input is known to be 0 or 1, the output is 0/-1, which is all
02022         // sign bits set.
02023         if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue())
02024           return TyBits;
02025 
02026         // If we are subtracting one from a positive number, there is no carry
02027         // out of the result.
02028         if (KnownZero.isNegative())
02029           return Tmp;
02030       }
02031 
02032     Tmp2 = ComputeNumSignBits(U->getOperand(1), DL, Depth + 1, Q);
02033     if (Tmp2 == 1) return 1;
02034     return std::min(Tmp, Tmp2)-1;
02035 
02036   case Instruction::Sub:
02037     Tmp2 = ComputeNumSignBits(U->getOperand(1), DL, Depth + 1, Q);
02038     if (Tmp2 == 1) return 1;
02039 
02040     // Handle NEG.
02041     if (const auto *CLHS = dyn_cast<Constant>(U->getOperand(0)))
02042       if (CLHS->isNullValue()) {
02043         APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
02044         computeKnownBits(U->getOperand(1), KnownZero, KnownOne, DL, Depth + 1,
02045                          Q);
02046         // If the input is known to be 0 or 1, the output is 0/-1, which is all
02047         // sign bits set.
02048         if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue())
02049           return TyBits;
02050 
02051         // If the input is known to be positive (the sign bit is known clear),
02052         // the output of the NEG has the same number of sign bits as the input.
02053         if (KnownZero.isNegative())
02054           return Tmp2;
02055 
02056         // Otherwise, we treat this like a SUB.
02057       }
02058 
02059     // Sub can have at most one carry bit.  Thus we know that the output
02060     // is, at worst, one more bit than the inputs.
02061     Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
02062     if (Tmp == 1) return 1;  // Early out.
02063     return std::min(Tmp, Tmp2)-1;
02064 
02065   case Instruction::PHI: {
02066     PHINode *PN = cast<PHINode>(U);
02067     unsigned NumIncomingValues = PN->getNumIncomingValues();
02068     // Don't analyze large in-degree PHIs.
02069     if (NumIncomingValues > 4) break;
02070     // Unreachable blocks may have zero-operand PHI nodes.
02071     if (NumIncomingValues == 0) break;
02072 
02073     // Take the minimum of all incoming values.  This can't infinitely loop
02074     // because of our depth threshold.
02075     Tmp = ComputeNumSignBits(PN->getIncomingValue(0), DL, Depth + 1, Q);
02076     for (unsigned i = 1, e = NumIncomingValues; i != e; ++i) {
02077       if (Tmp == 1) return Tmp;
02078       Tmp = std::min(
02079           Tmp, ComputeNumSignBits(PN->getIncomingValue(i), DL, Depth + 1, Q));
02080     }
02081     return Tmp;
02082   }
02083 
02084   case Instruction::Trunc:
02085     // FIXME: it's tricky to do anything useful for this, but it is an important
02086     // case for targets like X86.
02087     break;
02088   }
02089 
02090   // Finally, if we can prove that the top bits of the result are 0's or 1's,
02091   // use this information.
02092   APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
02093   APInt Mask;
02094   computeKnownBits(V, KnownZero, KnownOne, DL, Depth, Q);
02095 
02096   if (KnownZero.isNegative()) {        // sign bit is 0
02097     Mask = KnownZero;
02098   } else if (KnownOne.isNegative()) {  // sign bit is 1;
02099     Mask = KnownOne;
02100   } else {
02101     // Nothing known.
02102     return FirstAnswer;
02103   }
02104 
02105   // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
02106   // the number of identical bits in the top of the input value.
02107   Mask = ~Mask;
02108   Mask <<= Mask.getBitWidth()-TyBits;
02109   // Return # leading zeros.  We use 'min' here in case Val was zero before
02110   // shifting.  We don't want to return '64' as for an i32 "0".
02111   return std::max(FirstAnswer, std::min(TyBits, Mask.countLeadingZeros()));
02112 }
02113 
02114 /// This function computes the integer multiple of Base that equals V.
02115 /// If successful, it returns true and returns the multiple in
02116 /// Multiple. If unsuccessful, it returns false. It looks
02117 /// through SExt instructions only if LookThroughSExt is true.
02118 bool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple,
02119                            bool LookThroughSExt, unsigned Depth) {
02120   const unsigned MaxDepth = 6;
02121 
02122   assert(V && "No Value?");
02123   assert(Depth <= MaxDepth && "Limit Search Depth");
02124   assert(V->getType()->isIntegerTy() && "Not integer or pointer type!");
02125 
02126   Type *T = V->getType();
02127 
02128   ConstantInt *CI = dyn_cast<ConstantInt>(V);
02129 
02130   if (Base == 0)
02131     return false;
02132 
02133   if (Base == 1) {
02134     Multiple = V;
02135     return true;
02136   }
02137 
02138   ConstantExpr *CO = dyn_cast<ConstantExpr>(V);
02139   Constant *BaseVal = ConstantInt::get(T, Base);
02140   if (CO && CO == BaseVal) {
02141     // Multiple is 1.
02142     Multiple = ConstantInt::get(T, 1);
02143     return true;
02144   }
02145 
02146   if (CI && CI->getZExtValue() % Base == 0) {
02147     Multiple = ConstantInt::get(T, CI->getZExtValue() / Base);
02148     return true;
02149   }
02150 
02151   if (Depth == MaxDepth) return false;  // Limit search depth.
02152 
02153   Operator *I = dyn_cast<Operator>(V);
02154   if (!I) return false;
02155 
02156   switch (I->getOpcode()) {
02157   default: break;
02158   case Instruction::SExt:
02159     if (!LookThroughSExt) return false;
02160     // otherwise fall through to ZExt
02161   case Instruction::ZExt:
02162     return ComputeMultiple(I->getOperand(0), Base, Multiple,
02163                            LookThroughSExt, Depth+1);
02164   case Instruction::Shl:
02165   case Instruction::Mul: {
02166     Value *Op0 = I->getOperand(0);
02167     Value *Op1 = I->getOperand(1);
02168 
02169     if (I->getOpcode() == Instruction::Shl) {
02170       ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1);
02171       if (!Op1CI) return false;
02172       // Turn Op0 << Op1 into Op0 * 2^Op1
02173       APInt Op1Int = Op1CI->getValue();
02174       uint64_t BitToSet = Op1Int.getLimitedValue(Op1Int.getBitWidth() - 1);
02175       APInt API(Op1Int.getBitWidth(), 0);
02176       API.setBit(BitToSet);
02177       Op1 = ConstantInt::get(V->getContext(), API);
02178     }
02179 
02180     Value *Mul0 = nullptr;
02181     if (ComputeMultiple(Op0, Base, Mul0, LookThroughSExt, Depth+1)) {
02182       if (Constant *Op1C = dyn_cast<Constant>(Op1))
02183         if (Constant *MulC = dyn_cast<Constant>(Mul0)) {
02184           if (Op1C->getType()->getPrimitiveSizeInBits() <
02185               MulC->getType()->getPrimitiveSizeInBits())
02186             Op1C = ConstantExpr::getZExt(Op1C, MulC->getType());
02187           if (Op1C->getType()->getPrimitiveSizeInBits() >
02188               MulC->getType()->getPrimitiveSizeInBits())
02189             MulC = ConstantExpr::getZExt(MulC, Op1C->getType());
02190 
02191           // V == Base * (Mul0 * Op1), so return (Mul0 * Op1)
02192           Multiple = ConstantExpr::getMul(MulC, Op1C);
02193           return true;
02194         }
02195 
02196       if (ConstantInt *Mul0CI = dyn_cast<ConstantInt>(Mul0))
02197         if (Mul0CI->getValue() == 1) {
02198           // V == Base * Op1, so return Op1
02199           Multiple = Op1;
02200           return true;
02201         }
02202     }
02203 
02204     Value *Mul1 = nullptr;
02205     if (ComputeMultiple(Op1, Base, Mul1, LookThroughSExt, Depth+1)) {
02206       if (Constant *Op0C = dyn_cast<Constant>(Op0))
02207         if (Constant *MulC = dyn_cast<Constant>(Mul1)) {
02208           if (Op0C->getType()->getPrimitiveSizeInBits() <
02209               MulC->getType()->getPrimitiveSizeInBits())
02210             Op0C = ConstantExpr::getZExt(Op0C, MulC->getType());
02211           if (Op0C->getType()->getPrimitiveSizeInBits() >
02212               MulC->getType()->getPrimitiveSizeInBits())
02213             MulC = ConstantExpr::getZExt(MulC, Op0C->getType());
02214 
02215           // V == Base * (Mul1 * Op0), so return (Mul1 * Op0)
02216           Multiple = ConstantExpr::getMul(MulC, Op0C);
02217           return true;
02218         }
02219 
02220       if (ConstantInt *Mul1CI = dyn_cast<ConstantInt>(Mul1))
02221         if (Mul1CI->getValue() == 1) {
02222           // V == Base * Op0, so return Op0
02223           Multiple = Op0;
02224           return true;
02225         }
02226     }
02227   }
02228   }
02229 
02230   // We could not determine if V is a multiple of Base.
02231   return false;
02232 }
02233 
02234 /// Return true if we can prove that the specified FP value is never equal to
02235 /// -0.0.
02236 ///
02237 /// NOTE: this function will need to be revisited when we support non-default
02238 /// rounding modes!
02239 ///
02240 bool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) {
02241   if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V))
02242     return !CFP->getValueAPF().isNegZero();
02243 
02244   // FIXME: Magic number! At the least, this should be given a name because it's
02245   // used similarly in CannotBeOrderedLessThanZero(). A better fix may be to
02246   // expose it as a parameter, so it can be used for testing / experimenting.
02247   if (Depth == 6)
02248     return false;  // Limit search depth.
02249 
02250   const Operator *I = dyn_cast<Operator>(V);
02251   if (!I) return false;
02252 
02253   // Check if the nsz fast-math flag is set
02254   if (const FPMathOperator *FPO = dyn_cast<FPMathOperator>(I))
02255     if (FPO->hasNoSignedZeros())
02256       return true;
02257 
02258   // (add x, 0.0) is guaranteed to return +0.0, not -0.0.
02259   if (I->getOpcode() == Instruction::FAdd)
02260     if (ConstantFP *CFP = dyn_cast<ConstantFP>(I->getOperand(1)))
02261       if (CFP->isNullValue())
02262         return true;
02263 
02264   // sitofp and uitofp turn into +0.0 for zero.
02265   if (isa<SIToFPInst>(I) || isa<UIToFPInst>(I))
02266     return true;
02267 
02268   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
02269     // sqrt(-0.0) = -0.0, no other negative results are possible.
02270     if (II->getIntrinsicID() == Intrinsic::sqrt)
02271       return CannotBeNegativeZero(II->getArgOperand(0), Depth+1);
02272 
02273   if (const CallInst *CI = dyn_cast<CallInst>(I))
02274     if (const Function *F = CI->getCalledFunction()) {
02275       if (F->isDeclaration()) {
02276         // abs(x) != -0.0
02277         if (F->getName() == "abs") return true;
02278         // fabs[lf](x) != -0.0
02279         if (F->getName() == "fabs") return true;
02280         if (F->getName() == "fabsf") return true;
02281         if (F->getName() == "fabsl") return true;
02282         if (F->getName() == "sqrt" || F->getName() == "sqrtf" ||
02283             F->getName() == "sqrtl")
02284           return CannotBeNegativeZero(CI->getArgOperand(0), Depth+1);
02285       }
02286     }
02287 
02288   return false;
02289 }
02290 
02291 bool llvm::CannotBeOrderedLessThanZero(const Value *V, unsigned Depth) {
02292   if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V))
02293     return !CFP->getValueAPF().isNegative() || CFP->getValueAPF().isZero();
02294 
02295   // FIXME: Magic number! At the least, this should be given a name because it's
02296   // used similarly in CannotBeNegativeZero(). A better fix may be to
02297   // expose it as a parameter, so it can be used for testing / experimenting.
02298   if (Depth == 6)
02299     return false;  // Limit search depth.
02300 
02301   const Operator *I = dyn_cast<Operator>(V);
02302   if (!I) return false;
02303 
02304   switch (I->getOpcode()) {
02305   default: break;
02306   case Instruction::FMul:
02307     // x*x is always non-negative or a NaN.
02308     if (I->getOperand(0) == I->getOperand(1)) 
02309       return true;
02310     // Fall through
02311   case Instruction::FAdd:
02312   case Instruction::FDiv:
02313   case Instruction::FRem:
02314     return CannotBeOrderedLessThanZero(I->getOperand(0), Depth+1) &&
02315            CannotBeOrderedLessThanZero(I->getOperand(1), Depth+1);
02316   case Instruction::FPExt:
02317   case Instruction::FPTrunc:
02318     // Widening/narrowing never change sign.
02319     return CannotBeOrderedLessThanZero(I->getOperand(0), Depth+1);
02320   case Instruction::Call: 
02321     if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 
02322       switch (II->getIntrinsicID()) {
02323       default: break;
02324       case Intrinsic::exp:
02325       case Intrinsic::exp2:
02326       case Intrinsic::fabs:
02327       case Intrinsic::sqrt:
02328         return true;
02329       case Intrinsic::powi: 
02330         if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
02331           // powi(x,n) is non-negative if n is even.
02332           if (CI->getBitWidth() <= 64 && CI->getSExtValue() % 2u == 0)
02333             return true;
02334         }
02335         return CannotBeOrderedLessThanZero(I->getOperand(0), Depth+1);
02336       case Intrinsic::fma:
02337       case Intrinsic::fmuladd:
02338         // x*x+y is non-negative if y is non-negative.
02339         return I->getOperand(0) == I->getOperand(1) && 
02340                CannotBeOrderedLessThanZero(I->getOperand(2), Depth+1);
02341       }
02342     break;
02343   }
02344   return false; 
02345 }
02346 
02347 /// If the specified value can be set by repeating the same byte in memory,
02348 /// return the i8 value that it is represented with.  This is
02349 /// true for all i8 values obviously, but is also true for i32 0, i32 -1,
02350 /// i16 0xF0F0, double 0.0 etc.  If the value can't be handled with a repeated
02351 /// byte store (e.g. i16 0x1234), return null.
02352 Value *llvm::isBytewiseValue(Value *V) {
02353   // All byte-wide stores are splatable, even of arbitrary variables.
02354   if (V->getType()->isIntegerTy(8)) return V;
02355 
02356   // Handle 'null' ConstantArrayZero etc.
02357   if (Constant *C = dyn_cast<Constant>(V))
02358     if (C->isNullValue())
02359       return Constant::getNullValue(Type::getInt8Ty(V->getContext()));
02360 
02361   // Constant float and double values can be handled as integer values if the
02362   // corresponding integer value is "byteable".  An important case is 0.0.
02363   if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) {
02364     if (CFP->getType()->isFloatTy())
02365       V = ConstantExpr::getBitCast(CFP, Type::getInt32Ty(V->getContext()));
02366     if (CFP->getType()->isDoubleTy())
02367       V = ConstantExpr::getBitCast(CFP, Type::getInt64Ty(V->getContext()));
02368     // Don't handle long double formats, which have strange constraints.
02369   }
02370 
02371   // We can handle constant integers that are multiple of 8 bits.
02372   if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
02373     if (CI->getBitWidth() % 8 == 0) {
02374       assert(CI->getBitWidth() > 8 && "8 bits should be handled above!");
02375 
02376       if (!CI->getValue().isSplat(8))
02377         return nullptr;
02378       return ConstantInt::get(V->getContext(), CI->getValue().trunc(8));
02379     }
02380   }
02381 
02382   // A ConstantDataArray/Vector is splatable if all its members are equal and
02383   // also splatable.
02384   if (ConstantDataSequential *CA = dyn_cast<ConstantDataSequential>(V)) {
02385     Value *Elt = CA->getElementAsConstant(0);
02386     Value *Val = isBytewiseValue(Elt);
02387     if (!Val)
02388       return nullptr;
02389 
02390     for (unsigned I = 1, E = CA->getNumElements(); I != E; ++I)
02391       if (CA->getElementAsConstant(I) != Elt)
02392         return nullptr;
02393 
02394     return Val;
02395   }
02396 
02397   // Conceptually, we could handle things like:
02398   //   %a = zext i8 %X to i16
02399   //   %b = shl i16 %a, 8
02400   //   %c = or i16 %a, %b
02401   // but until there is an example that actually needs this, it doesn't seem
02402   // worth worrying about.
02403   return nullptr;
02404 }
02405 
02406 
02407 // This is the recursive version of BuildSubAggregate. It takes a few different
02408 // arguments. Idxs is the index within the nested struct From that we are
02409 // looking at now (which is of type IndexedType). IdxSkip is the number of
02410 // indices from Idxs that should be left out when inserting into the resulting
02411 // struct. To is the result struct built so far, new insertvalue instructions
02412 // build on that.
02413 static Value *BuildSubAggregate(Value *From, Value* To, Type *IndexedType,
02414                                 SmallVectorImpl<unsigned> &Idxs,
02415                                 unsigned IdxSkip,
02416                                 Instruction *InsertBefore) {
02417   llvm::StructType *STy = dyn_cast<llvm::StructType>(IndexedType);
02418   if (STy) {
02419     // Save the original To argument so we can modify it
02420     Value *OrigTo = To;
02421     // General case, the type indexed by Idxs is a struct
02422     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
02423       // Process each struct element recursively
02424       Idxs.push_back(i);
02425       Value *PrevTo = To;
02426       To = BuildSubAggregate(From, To, STy->getElementType(i), Idxs, IdxSkip,
02427                              InsertBefore);
02428       Idxs.pop_back();
02429       if (!To) {
02430         // Couldn't find any inserted value for this index? Cleanup
02431         while (PrevTo != OrigTo) {
02432           InsertValueInst* Del = cast<InsertValueInst>(PrevTo);
02433           PrevTo = Del->getAggregateOperand();
02434           Del->eraseFromParent();
02435         }
02436         // Stop processing elements
02437         break;
02438       }
02439     }
02440     // If we successfully found a value for each of our subaggregates
02441     if (To)
02442       return To;
02443   }
02444   // Base case, the type indexed by SourceIdxs is not a struct, or not all of
02445   // the struct's elements had a value that was inserted directly. In the latter
02446   // case, perhaps we can't determine each of the subelements individually, but
02447   // we might be able to find the complete struct somewhere.
02448 
02449   // Find the value that is at that particular spot
02450   Value *V = FindInsertedValue(From, Idxs);
02451 
02452   if (!V)
02453     return nullptr;
02454 
02455   // Insert the value in the new (sub) aggregrate
02456   return llvm::InsertValueInst::Create(To, V, makeArrayRef(Idxs).slice(IdxSkip),
02457                                        "tmp", InsertBefore);
02458 }
02459 
02460 // This helper takes a nested struct and extracts a part of it (which is again a
02461 // struct) into a new value. For example, given the struct:
02462 // { a, { b, { c, d }, e } }
02463 // and the indices "1, 1" this returns
02464 // { c, d }.
02465 //
02466 // It does this by inserting an insertvalue for each element in the resulting
02467 // struct, as opposed to just inserting a single struct. This will only work if
02468 // each of the elements of the substruct are known (ie, inserted into From by an
02469 // insertvalue instruction somewhere).
02470 //
02471 // All inserted insertvalue instructions are inserted before InsertBefore
02472 static Value *BuildSubAggregate(Value *From, ArrayRef<unsigned> idx_range,
02473                                 Instruction *InsertBefore) {
02474   assert(InsertBefore && "Must have someplace to insert!");
02475   Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(),
02476                                                              idx_range);
02477   Value *To = UndefValue::get(IndexedType);
02478   SmallVector<unsigned, 10> Idxs(idx_range.begin(), idx_range.end());
02479   unsigned IdxSkip = Idxs.size();
02480 
02481   return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore);
02482 }
02483 
02484 /// Given an aggregrate and an sequence of indices, see if
02485 /// the scalar value indexed is already around as a register, for example if it
02486 /// were inserted directly into the aggregrate.
02487 ///
02488 /// If InsertBefore is not null, this function will duplicate (modified)
02489 /// insertvalues when a part of a nested struct is extracted.
02490 Value *llvm::FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range,
02491                                Instruction *InsertBefore) {
02492   // Nothing to index? Just return V then (this is useful at the end of our
02493   // recursion).
02494   if (idx_range.empty())
02495     return V;
02496   // We have indices, so V should have an indexable type.
02497   assert((V->getType()->isStructTy() || V->getType()->isArrayTy()) &&
02498          "Not looking at a struct or array?");
02499   assert(ExtractValueInst::getIndexedType(V->getType(), idx_range) &&
02500          "Invalid indices for type?");
02501 
02502   if (Constant *C = dyn_cast<Constant>(V)) {
02503     C = C->getAggregateElement(idx_range[0]);
02504     if (!C) return nullptr;
02505     return FindInsertedValue(C, idx_range.slice(1), InsertBefore);
02506   }
02507 
02508   if (InsertValueInst *I = dyn_cast<InsertValueInst>(V)) {
02509     // Loop the indices for the insertvalue instruction in parallel with the
02510     // requested indices
02511     const unsigned *req_idx = idx_range.begin();
02512     for (const unsigned *i = I->idx_begin(), *e = I->idx_end();
02513          i != e; ++i, ++req_idx) {
02514       if (req_idx == idx_range.end()) {
02515         // We can't handle this without inserting insertvalues
02516         if (!InsertBefore)
02517           return nullptr;
02518 
02519         // The requested index identifies a part of a nested aggregate. Handle
02520         // this specially. For example,
02521         // %A = insertvalue { i32, {i32, i32 } } undef, i32 10, 1, 0
02522         // %B = insertvalue { i32, {i32, i32 } } %A, i32 11, 1, 1
02523         // %C = extractvalue {i32, { i32, i32 } } %B, 1
02524         // This can be changed into
02525         // %A = insertvalue {i32, i32 } undef, i32 10, 0
02526         // %C = insertvalue {i32, i32 } %A, i32 11, 1
02527         // which allows the unused 0,0 element from the nested struct to be
02528         // removed.
02529         return BuildSubAggregate(V, makeArrayRef(idx_range.begin(), req_idx),
02530                                  InsertBefore);
02531       }
02532 
02533       // This insert value inserts something else than what we are looking for.
02534       // See if the (aggregrate) value inserted into has the value we are
02535       // looking for, then.
02536       if (*req_idx != *i)
02537         return FindInsertedValue(I->getAggregateOperand(), idx_range,
02538                                  InsertBefore);
02539     }
02540     // If we end up here, the indices of the insertvalue match with those
02541     // requested (though possibly only partially). Now we recursively look at
02542     // the inserted value, passing any remaining indices.
02543     return FindInsertedValue(I->getInsertedValueOperand(),
02544                              makeArrayRef(req_idx, idx_range.end()),
02545                              InsertBefore);
02546   }
02547 
02548   if (ExtractValueInst *I = dyn_cast<ExtractValueInst>(V)) {
02549     // If we're extracting a value from an aggregrate that was extracted from
02550     // something else, we can extract from that something else directly instead.
02551     // However, we will need to chain I's indices with the requested indices.
02552 
02553     // Calculate the number of indices required
02554     unsigned size = I->getNumIndices() + idx_range.size();
02555     // Allocate some space to put the new indices in
02556     SmallVector<unsigned, 5> Idxs;
02557     Idxs.reserve(size);
02558     // Add indices from the extract value instruction
02559     Idxs.append(I->idx_begin(), I->idx_end());
02560 
02561     // Add requested indices
02562     Idxs.append(idx_range.begin(), idx_range.end());
02563 
02564     assert(Idxs.size() == size
02565            && "Number of indices added not correct?");
02566 
02567     return FindInsertedValue(I->getAggregateOperand(), Idxs, InsertBefore);
02568   }
02569   // Otherwise, we don't know (such as, extracting from a function return value
02570   // or load instruction)
02571   return nullptr;
02572 }
02573 
02574 /// Analyze the specified pointer to see if it can be expressed as a base
02575 /// pointer plus a constant offset. Return the base and offset to the caller.
02576 Value *llvm::GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset,
02577                                               const DataLayout &DL) {
02578   unsigned BitWidth = DL.getPointerTypeSizeInBits(Ptr->getType());
02579   APInt ByteOffset(BitWidth, 0);
02580   while (1) {
02581     if (Ptr->getType()->isVectorTy())
02582       break;
02583 
02584     if (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) {
02585       APInt GEPOffset(BitWidth, 0);
02586       if (!GEP->accumulateConstantOffset(DL, GEPOffset))
02587         break;
02588 
02589       ByteOffset += GEPOffset;
02590 
02591       Ptr = GEP->getPointerOperand();
02592     } else if (Operator::getOpcode(Ptr) == Instruction::BitCast ||
02593                Operator::getOpcode(Ptr) == Instruction::AddrSpaceCast) {
02594       Ptr = cast<Operator>(Ptr)->getOperand(0);
02595     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Ptr)) {
02596       if (GA->mayBeOverridden())
02597         break;
02598       Ptr = GA->getAliasee();
02599     } else {
02600       break;
02601     }
02602   }
02603   Offset = ByteOffset.getSExtValue();
02604   return Ptr;
02605 }
02606 
02607 
02608 /// This function computes the length of a null-terminated C string pointed to
02609 /// by V. If successful, it returns true and returns the string in Str.
02610 /// If unsuccessful, it returns false.
02611 bool llvm::getConstantStringInfo(const Value *V, StringRef &Str,
02612                                  uint64_t Offset, bool TrimAtNul) {
02613   assert(V);
02614 
02615   // Look through bitcast instructions and geps.
02616   V = V->stripPointerCasts();
02617 
02618   // If the value is a GEP instruction or constant expression, treat it as an
02619   // offset.
02620   if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
02621     // Make sure the GEP has exactly three arguments.
02622     if (GEP->getNumOperands() != 3)
02623       return false;
02624 
02625     // Make sure the index-ee is a pointer to array of i8.
02626     PointerType *PT = cast<PointerType>(GEP->getOperand(0)->getType());
02627     ArrayType *AT = dyn_cast<ArrayType>(PT->getElementType());
02628     if (!AT || !AT->getElementType()->isIntegerTy(8))
02629       return false;
02630 
02631     // Check to make sure that the first operand of the GEP is an integer and
02632     // has value 0 so that we are sure we're indexing into the initializer.
02633     const ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1));
02634     if (!FirstIdx || !FirstIdx->isZero())
02635       return false;
02636 
02637     // If the second index isn't a ConstantInt, then this is a variable index
02638     // into the array.  If this occurs, we can't say anything meaningful about
02639     // the string.
02640     uint64_t StartIdx = 0;
02641     if (const ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
02642       StartIdx = CI->getZExtValue();
02643     else
02644       return false;
02645     return getConstantStringInfo(GEP->getOperand(0), Str, StartIdx + Offset,
02646                                  TrimAtNul);
02647   }
02648 
02649   // The GEP instruction, constant or instruction, must reference a global
02650   // variable that is a constant and is initialized. The referenced constant
02651   // initializer is the array that we'll use for optimization.
02652   const GlobalVariable *GV = dyn_cast<GlobalVariable>(V);
02653   if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())
02654     return false;
02655 
02656   // Handle the all-zeros case
02657   if (GV->getInitializer()->isNullValue()) {
02658     // This is a degenerate case. The initializer is constant zero so the
02659     // length of the string must be zero.
02660     Str = "";
02661     return true;
02662   }
02663 
02664   // Must be a Constant Array
02665   const ConstantDataArray *Array =
02666     dyn_cast<ConstantDataArray>(GV->getInitializer());
02667   if (!Array || !Array->isString())
02668     return false;
02669 
02670   // Get the number of elements in the array
02671   uint64_t NumElts = Array->getType()->getArrayNumElements();
02672 
02673   // Start out with the entire array in the StringRef.
02674   Str = Array->getAsString();
02675 
02676   if (Offset > NumElts)
02677     return false;
02678 
02679   // Skip over 'offset' bytes.
02680   Str = Str.substr(Offset);
02681 
02682   if (TrimAtNul) {
02683     // Trim off the \0 and anything after it.  If the array is not nul
02684     // terminated, we just return the whole end of string.  The client may know
02685     // some other way that the string is length-bound.
02686     Str = Str.substr(0, Str.find('\0'));
02687   }
02688   return true;
02689 }
02690 
02691 // These next two are very similar to the above, but also look through PHI
02692 // nodes.
02693 // TODO: See if we can integrate these two together.
02694 
02695 /// If we can compute the length of the string pointed to by
02696 /// the specified pointer, return 'len+1'.  If we can't, return 0.
02697 static uint64_t GetStringLengthH(Value *V, SmallPtrSetImpl<PHINode*> &PHIs) {
02698   // Look through noop bitcast instructions.
02699   V = V->stripPointerCasts();
02700 
02701   // If this is a PHI node, there are two cases: either we have already seen it
02702   // or we haven't.
02703   if (PHINode *PN = dyn_cast<PHINode>(V)) {
02704     if (!PHIs.insert(PN).second)
02705       return ~0ULL;  // already in the set.
02706 
02707     // If it was new, see if all the input strings are the same length.
02708     uint64_t LenSoFar = ~0ULL;
02709     for (Value *IncValue : PN->incoming_values()) {
02710       uint64_t Len = GetStringLengthH(IncValue, PHIs);
02711       if (Len == 0) return 0; // Unknown length -> unknown.
02712 
02713       if (Len == ~0ULL) continue;
02714 
02715       if (Len != LenSoFar && LenSoFar != ~0ULL)
02716         return 0;    // Disagree -> unknown.
02717       LenSoFar = Len;
02718     }
02719 
02720     // Success, all agree.
02721     return LenSoFar;
02722   }
02723 
02724   // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y)
02725   if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
02726     uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs);
02727     if (Len1 == 0) return 0;
02728     uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs);
02729     if (Len2 == 0) return 0;
02730     if (Len1 == ~0ULL) return Len2;
02731     if (Len2 == ~0ULL) return Len1;
02732     if (Len1 != Len2) return 0;
02733     return Len1;
02734   }
02735 
02736   // Otherwise, see if we can read the string.
02737   StringRef StrData;
02738   if (!getConstantStringInfo(V, StrData))
02739     return 0;
02740 
02741   return StrData.size()+1;
02742 }
02743 
02744 /// If we can compute the length of the string pointed to by
02745 /// the specified pointer, return 'len+1'.  If we can't, return 0.
02746 uint64_t llvm::GetStringLength(Value *V) {
02747   if (!V->getType()->isPointerTy()) return 0;
02748 
02749   SmallPtrSet<PHINode*, 32> PHIs;
02750   uint64_t Len = GetStringLengthH(V, PHIs);
02751   // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return
02752   // an empty string as a length.
02753   return Len == ~0ULL ? 1 : Len;
02754 }
02755 
02756 /// \brief \p PN defines a loop-variant pointer to an object.  Check if the
02757 /// previous iteration of the loop was referring to the same object as \p PN.
02758 static bool isSameUnderlyingObjectInLoop(PHINode *PN, LoopInfo *LI) {
02759   // Find the loop-defined value.
02760   Loop *L = LI->getLoopFor(PN->getParent());
02761   if (PN->getNumIncomingValues() != 2)
02762     return true;
02763 
02764   // Find the value from previous iteration.
02765   auto *PrevValue = dyn_cast<Instruction>(PN->getIncomingValue(0));
02766   if (!PrevValue || LI->getLoopFor(PrevValue->getParent()) != L)
02767     PrevValue = dyn_cast<Instruction>(PN->getIncomingValue(1));
02768   if (!PrevValue || LI->getLoopFor(PrevValue->getParent()) != L)
02769     return true;
02770 
02771   // If a new pointer is loaded in the loop, the pointer references a different
02772   // object in every iteration.  E.g.:
02773   //    for (i)
02774   //       int *p = a[i];
02775   //       ...
02776   if (auto *Load = dyn_cast<LoadInst>(PrevValue))
02777     if (!L->isLoopInvariant(Load->getPointerOperand()))
02778       return false;
02779   return true;
02780 }
02781 
02782 Value *llvm::GetUnderlyingObject(Value *V, const DataLayout &DL,
02783                                  unsigned MaxLookup) {
02784   if (!V->getType()->isPointerTy())
02785     return V;
02786   for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
02787     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
02788       V = GEP->getPointerOperand();
02789     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
02790                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
02791       V = cast<Operator>(V)->getOperand(0);
02792     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
02793       if (GA->mayBeOverridden())
02794         return V;
02795       V = GA->getAliasee();
02796     } else {
02797       // See if InstructionSimplify knows any relevant tricks.
02798       if (Instruction *I = dyn_cast<Instruction>(V))
02799         // TODO: Acquire a DominatorTree and AssumptionCache and use them.
02800         if (Value *Simplified = SimplifyInstruction(I, DL, nullptr)) {
02801           V = Simplified;
02802           continue;
02803         }
02804 
02805       return V;
02806     }
02807     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
02808   }
02809   return V;
02810 }
02811 
02812 void llvm::GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects,
02813                                 const DataLayout &DL, LoopInfo *LI,
02814                                 unsigned MaxLookup) {
02815   SmallPtrSet<Value *, 4> Visited;
02816   SmallVector<Value *, 4> Worklist;
02817   Worklist.push_back(V);
02818   do {
02819     Value *P = Worklist.pop_back_val();
02820     P = GetUnderlyingObject(P, DL, MaxLookup);
02821 
02822     if (!Visited.insert(P).second)
02823       continue;
02824 
02825     if (SelectInst *SI = dyn_cast<SelectInst>(P)) {
02826       Worklist.push_back(SI->getTrueValue());
02827       Worklist.push_back(SI->getFalseValue());
02828       continue;
02829     }
02830 
02831     if (PHINode *PN = dyn_cast<PHINode>(P)) {
02832       // If this PHI changes the underlying object in every iteration of the
02833       // loop, don't look through it.  Consider:
02834       //   int **A;
02835       //   for (i) {
02836       //     Prev = Curr;     // Prev = PHI (Prev_0, Curr)
02837       //     Curr = A[i];
02838       //     *Prev, *Curr;
02839       //
02840       // Prev is tracking Curr one iteration behind so they refer to different
02841       // underlying objects.
02842       if (!LI || !LI->isLoopHeader(PN->getParent()) ||
02843           isSameUnderlyingObjectInLoop(PN, LI))
02844         for (Value *IncValue : PN->incoming_values())
02845           Worklist.push_back(IncValue);
02846       continue;
02847     }
02848 
02849     Objects.push_back(P);
02850   } while (!Worklist.empty());
02851 }
02852 
02853 /// Return true if the only users of this pointer are lifetime markers.
02854 bool llvm::onlyUsedByLifetimeMarkers(const Value *V) {
02855   for (const User *U : V->users()) {
02856     const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U);
02857     if (!II) return false;
02858 
02859     if (II->getIntrinsicID() != Intrinsic::lifetime_start &&
02860         II->getIntrinsicID() != Intrinsic::lifetime_end)
02861       return false;
02862   }
02863   return true;
02864 }
02865 
02866 static bool isDereferenceableFromAttribute(const Value *BV, APInt Offset,
02867                                            Type *Ty, const DataLayout &DL,
02868                                            const Instruction *CtxI,
02869                                            const DominatorTree *DT,
02870                                            const TargetLibraryInfo *TLI) {
02871   assert(Offset.isNonNegative() && "offset can't be negative");
02872   assert(Ty->isSized() && "must be sized");
02873   
02874   APInt DerefBytes(Offset.getBitWidth(), 0);
02875   bool CheckForNonNull = false;
02876   if (const Argument *A = dyn_cast<Argument>(BV)) {
02877     DerefBytes = A->getDereferenceableBytes();
02878     if (!DerefBytes.getBoolValue()) {
02879       DerefBytes = A->getDereferenceableOrNullBytes();
02880       CheckForNonNull = true;
02881     }
02882   } else if (auto CS = ImmutableCallSite(BV)) {
02883     DerefBytes = CS.getDereferenceableBytes(0);
02884     if (!DerefBytes.getBoolValue()) {
02885       DerefBytes = CS.getDereferenceableOrNullBytes(0);
02886       CheckForNonNull = true;
02887     }
02888   } else if (const LoadInst *LI = dyn_cast<LoadInst>(BV)) {
02889     if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable)) {
02890       ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
02891       DerefBytes = CI->getLimitedValue();
02892     }
02893     if (!DerefBytes.getBoolValue()) {
02894       if (MDNode *MD = 
02895               LI->getMetadata(LLVMContext::MD_dereferenceable_or_null)) {
02896         ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
02897         DerefBytes = CI->getLimitedValue();
02898       }
02899       CheckForNonNull = true;
02900     }
02901   }
02902   
02903   if (DerefBytes.getBoolValue())
02904     if (DerefBytes.uge(Offset + DL.getTypeStoreSize(Ty)))
02905       if (!CheckForNonNull || isKnownNonNullAt(BV, CtxI, DT, TLI))
02906         return true;
02907 
02908   return false;
02909 }
02910 
02911 static bool isDereferenceableFromAttribute(const Value *V, const DataLayout &DL,
02912                                            const Instruction *CtxI,
02913                                            const DominatorTree *DT,
02914                                            const TargetLibraryInfo *TLI) {
02915   Type *VTy = V->getType();
02916   Type *Ty = VTy->getPointerElementType();
02917   if (!Ty->isSized())
02918     return false;
02919   
02920   APInt Offset(DL.getTypeStoreSizeInBits(VTy), 0);
02921   return isDereferenceableFromAttribute(V, Offset, Ty, DL, CtxI, DT, TLI);
02922 }
02923 
02924 /// Return true if Value is always a dereferenceable pointer.
02925 ///
02926 /// Test if V is always a pointer to allocated and suitably aligned memory for
02927 /// a simple load or store.
02928 static bool isDereferenceablePointer(const Value *V, const DataLayout &DL,
02929                                      const Instruction *CtxI,
02930                                      const DominatorTree *DT,
02931                                      const TargetLibraryInfo *TLI,
02932                                      SmallPtrSetImpl<const Value *> &Visited) {
02933   // Note that it is not safe to speculate into a malloc'd region because
02934   // malloc may return null.
02935 
02936   // These are obviously ok.
02937   if (isa<AllocaInst>(V)) return true;
02938 
02939   // It's not always safe to follow a bitcast, for example:
02940   //   bitcast i8* (alloca i8) to i32*
02941   // would result in a 4-byte load from a 1-byte alloca. However,
02942   // if we're casting from a pointer from a type of larger size
02943   // to a type of smaller size (or the same size), and the alignment
02944   // is at least as large as for the resulting pointer type, then
02945   // we can look through the bitcast.
02946   if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) {
02947     Type *STy = BC->getSrcTy()->getPointerElementType(),
02948          *DTy = BC->getDestTy()->getPointerElementType();
02949     if (STy->isSized() && DTy->isSized() &&
02950         (DL.getTypeStoreSize(STy) >= DL.getTypeStoreSize(DTy)) &&
02951         (DL.getABITypeAlignment(STy) >= DL.getABITypeAlignment(DTy)))
02952       return isDereferenceablePointer(BC->getOperand(0), DL, CtxI,
02953                                       DT, TLI, Visited);
02954   }
02955 
02956   // Global variables which can't collapse to null are ok.
02957   if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
02958     return !GV->hasExternalWeakLinkage();
02959 
02960   // byval arguments are okay.
02961   if (const Argument *A = dyn_cast<Argument>(V))
02962     if (A->hasByValAttr())
02963       return true;
02964     
02965   if (isDereferenceableFromAttribute(V, DL, CtxI, DT, TLI))
02966     return true;
02967 
02968   // For GEPs, determine if the indexing lands within the allocated object.
02969   if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
02970     // Conservatively require that the base pointer be fully dereferenceable.
02971     if (!Visited.insert(GEP->getOperand(0)).second)
02972       return false;
02973     if (!isDereferenceablePointer(GEP->getOperand(0), DL, CtxI,
02974                                   DT, TLI, Visited))
02975       return false;
02976     // Check the indices.
02977     gep_type_iterator GTI = gep_type_begin(GEP);
02978     for (User::const_op_iterator I = GEP->op_begin()+1,
02979          E = GEP->op_end(); I != E; ++I) {
02980       Value *Index = *I;
02981       Type *Ty = *GTI++;
02982       // Struct indices can't be out of bounds.
02983       if (isa<StructType>(Ty))
02984         continue;
02985       ConstantInt *CI = dyn_cast<ConstantInt>(Index);
02986       if (!CI)
02987         return false;
02988       // Zero is always ok.
02989       if (CI->isZero())
02990         continue;
02991       // Check to see that it's within the bounds of an array.
02992       ArrayType *ATy = dyn_cast<ArrayType>(Ty);
02993       if (!ATy)
02994         return false;
02995       if (CI->getValue().getActiveBits() > 64)
02996         return false;
02997       if (CI->getZExtValue() >= ATy->getNumElements())
02998         return false;
02999     }
03000     // Indices check out; this is dereferenceable.
03001     return true;
03002   }
03003 
03004   // For gc.relocate, look through relocations
03005   if (const IntrinsicInst *I = dyn_cast<IntrinsicInst>(V))
03006     if (I->getIntrinsicID() == Intrinsic::experimental_gc_relocate) {
03007       GCRelocateOperands RelocateInst(I);
03008       return isDereferenceablePointer(RelocateInst.getDerivedPtr(), DL, CtxI,
03009                                       DT, TLI, Visited);
03010     }
03011 
03012   if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
03013     return isDereferenceablePointer(ASC->getOperand(0), DL, CtxI,
03014                                     DT, TLI, Visited);
03015 
03016   // If we don't know, assume the worst.
03017   return false;
03018 }
03019 
03020 bool llvm::isDereferenceablePointer(const Value *V, const DataLayout &DL,
03021                                     const Instruction *CtxI,
03022                                     const DominatorTree *DT,
03023                                     const TargetLibraryInfo *TLI) {
03024   // When dereferenceability information is provided by a dereferenceable
03025   // attribute, we know exactly how many bytes are dereferenceable. If we can
03026   // determine the exact offset to the attributed variable, we can use that
03027   // information here.
03028   Type *VTy = V->getType();
03029   Type *Ty = VTy->getPointerElementType();
03030   if (Ty->isSized()) {
03031     APInt Offset(DL.getTypeStoreSizeInBits(VTy), 0);
03032     const Value *BV = V->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
03033     
03034     if (Offset.isNonNegative())
03035       if (isDereferenceableFromAttribute(BV, Offset, Ty, DL,
03036                                          CtxI, DT, TLI))
03037         return true;
03038   }
03039 
03040   SmallPtrSet<const Value *, 32> Visited;
03041   return ::isDereferenceablePointer(V, DL, CtxI, DT, TLI, Visited);
03042 }
03043 
03044 bool llvm::isSafeToSpeculativelyExecute(const Value *V,
03045                                         const Instruction *CtxI,
03046                                         const DominatorTree *DT,
03047                                         const TargetLibraryInfo *TLI) {
03048   const Operator *Inst = dyn_cast<Operator>(V);
03049   if (!Inst)
03050     return false;
03051 
03052   for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
03053     if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i)))
03054       if (C->canTrap())
03055         return false;
03056 
03057   switch (Inst->getOpcode()) {
03058   default:
03059     return true;
03060   case Instruction::UDiv:
03061   case Instruction::URem: {
03062     // x / y is undefined if y == 0.
03063     const APInt *V;
03064     if (match(Inst->getOperand(1), m_APInt(V)))
03065       return *V != 0;
03066     return false;
03067   }
03068   case Instruction::SDiv:
03069   case Instruction::SRem: {
03070     // x / y is undefined if y == 0 or x == INT_MIN and y == -1
03071     const APInt *Numerator, *Denominator;
03072     if (!match(Inst->getOperand(1), m_APInt(Denominator)))
03073       return false;
03074     // We cannot hoist this division if the denominator is 0.
03075     if (*Denominator == 0)
03076       return false;
03077     // It's safe to hoist if the denominator is not 0 or -1.
03078     if (*Denominator != -1)
03079       return true;
03080     // At this point we know that the denominator is -1.  It is safe to hoist as
03081     // long we know that the numerator is not INT_MIN.
03082     if (match(Inst->getOperand(0), m_APInt(Numerator)))
03083       return !Numerator->isMinSignedValue();
03084     // The numerator *might* be MinSignedValue.
03085     return false;
03086   }
03087   case Instruction::Load: {
03088     const LoadInst *LI = cast<LoadInst>(Inst);
03089     if (!LI->isUnordered() ||
03090         // Speculative load may create a race that did not exist in the source.
03091         LI->getParent()->getParent()->hasFnAttribute(Attribute::SanitizeThread))
03092       return false;
03093     const DataLayout &DL = LI->getModule()->getDataLayout();
03094     return isDereferenceablePointer(LI->getPointerOperand(), DL, CtxI, DT, TLI);
03095   }
03096   case Instruction::Call: {
03097     if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
03098       switch (II->getIntrinsicID()) {
03099       // These synthetic intrinsics have no side-effects and just mark
03100       // information about their operands.
03101       // FIXME: There are other no-op synthetic instructions that potentially
03102       // should be considered at least *safe* to speculate...
03103       case Intrinsic::dbg_declare:
03104       case Intrinsic::dbg_value:
03105         return true;
03106 
03107       case Intrinsic::bswap:
03108       case Intrinsic::ctlz:
03109       case Intrinsic::ctpop:
03110       case Intrinsic::cttz:
03111       case Intrinsic::objectsize:
03112       case Intrinsic::sadd_with_overflow:
03113       case Intrinsic::smul_with_overflow:
03114       case Intrinsic::ssub_with_overflow:
03115       case Intrinsic::uadd_with_overflow:
03116       case Intrinsic::umul_with_overflow:
03117       case Intrinsic::usub_with_overflow:
03118         return true;
03119       // Sqrt should be OK, since the llvm sqrt intrinsic isn't defined to set
03120       // errno like libm sqrt would.
03121       case Intrinsic::sqrt:
03122       case Intrinsic::fma:
03123       case Intrinsic::fmuladd:
03124       case Intrinsic::fabs:
03125       case Intrinsic::minnum:
03126       case Intrinsic::maxnum:
03127         return true;
03128       // TODO: some fp intrinsics are marked as having the same error handling
03129       // as libm. They're safe to speculate when they won't error.
03130       // TODO: are convert_{from,to}_fp16 safe?
03131       // TODO: can we list target-specific intrinsics here?
03132       default: break;
03133       }
03134     }
03135     return false; // The called function could have undefined behavior or
03136                   // side-effects, even if marked readnone nounwind.
03137   }
03138   case Instruction::VAArg:
03139   case Instruction::Alloca:
03140   case Instruction::Invoke:
03141   case Instruction::PHI:
03142   case Instruction::Store:
03143   case Instruction::Ret:
03144   case Instruction::Br:
03145   case Instruction::IndirectBr:
03146   case Instruction::Switch:
03147   case Instruction::Unreachable:
03148   case Instruction::Fence:
03149   case Instruction::LandingPad:
03150   case Instruction::AtomicRMW:
03151   case Instruction::AtomicCmpXchg:
03152   case Instruction::Resume:
03153     return false; // Misc instructions which have effects
03154   }
03155 }
03156 
03157 /// Return true if we know that the specified value is never null.
03158 bool llvm::isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI) {
03159   // Alloca never returns null, malloc might.
03160   if (isa<AllocaInst>(V)) return true;
03161 
03162   // A byval, inalloca, or nonnull argument is never null.
03163   if (const Argument *A = dyn_cast<Argument>(V))
03164     return A->hasByValOrInAllocaAttr() || A->hasNonNullAttr();
03165 
03166   // Global values are not null unless extern weak.
03167   if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
03168     return !GV->hasExternalWeakLinkage();
03169 
03170   // A Load tagged w/nonnull metadata is never null. 
03171   if (const LoadInst *LI = dyn_cast<LoadInst>(V))
03172     return LI->getMetadata(LLVMContext::MD_nonnull);
03173 
03174   if (auto CS = ImmutableCallSite(V))
03175     if (CS.isReturnNonNull())
03176       return true;
03177 
03178   // operator new never returns null.
03179   if (isOperatorNewLikeFn(V, TLI, /*LookThroughBitCast=*/true))
03180     return true;
03181 
03182   return false;
03183 }
03184 
03185 static bool isKnownNonNullFromDominatingCondition(const Value *V,
03186                                                   const Instruction *CtxI,
03187                                                   const DominatorTree *DT) {
03188   unsigned NumUsesExplored = 0;
03189   for (auto U : V->users()) {
03190     // Avoid massive lists
03191     if (NumUsesExplored >= DomConditionsMaxUses)
03192       break;
03193     NumUsesExplored++;
03194     // Consider only compare instructions uniquely controlling a branch
03195     const ICmpInst *Cmp = dyn_cast<ICmpInst>(U);
03196     if (!Cmp)
03197       continue;
03198 
03199     if (DomConditionsSingleCmpUse && !Cmp->hasOneUse())
03200       continue;
03201 
03202     for (auto *CmpU : Cmp->users()) {
03203       const BranchInst *BI = dyn_cast<BranchInst>(CmpU);
03204       if (!BI)
03205         continue;
03206       
03207       assert(BI->isConditional() && "uses a comparison!");
03208 
03209       BasicBlock *NonNullSuccessor = nullptr;
03210       CmpInst::Predicate Pred;
03211 
03212       if (match(const_cast<ICmpInst*>(Cmp),
03213                 m_c_ICmp(Pred, m_Specific(V), m_Zero()))) {
03214         if (Pred == ICmpInst::ICMP_EQ)
03215           NonNullSuccessor = BI->getSuccessor(1);
03216         else if (Pred == ICmpInst::ICMP_NE)
03217           NonNullSuccessor = BI->getSuccessor(0);
03218       }
03219 
03220       if (NonNullSuccessor) {
03221         BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
03222         if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
03223           return true;
03224       }
03225     }
03226   }
03227 
03228   return false;
03229 }
03230 
03231 bool llvm::isKnownNonNullAt(const Value *V, const Instruction *CtxI,
03232                    const DominatorTree *DT, const TargetLibraryInfo *TLI) {
03233   if (isKnownNonNull(V, TLI))
03234     return true;
03235 
03236   return CtxI ? ::isKnownNonNullFromDominatingCondition(V, CtxI, DT) : false;
03237 }
03238 
03239 OverflowResult llvm::computeOverflowForUnsignedMul(Value *LHS, Value *RHS,
03240                                                    const DataLayout &DL,
03241                                                    AssumptionCache *AC,
03242                                                    const Instruction *CxtI,
03243                                                    const DominatorTree *DT) {
03244   // Multiplying n * m significant bits yields a result of n + m significant
03245   // bits. If the total number of significant bits does not exceed the
03246   // result bit width (minus 1), there is no overflow.
03247   // This means if we have enough leading zero bits in the operands
03248   // we can guarantee that the result does not overflow.
03249   // Ref: "Hacker's Delight" by Henry Warren
03250   unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
03251   APInt LHSKnownZero(BitWidth, 0);
03252   APInt LHSKnownOne(BitWidth, 0);
03253   APInt RHSKnownZero(BitWidth, 0);
03254   APInt RHSKnownOne(BitWidth, 0);
03255   computeKnownBits(LHS, LHSKnownZero, LHSKnownOne, DL, /*Depth=*/0, AC, CxtI,
03256                    DT);
03257   computeKnownBits(RHS, RHSKnownZero, RHSKnownOne, DL, /*Depth=*/0, AC, CxtI,
03258                    DT);
03259   // Note that underestimating the number of zero bits gives a more
03260   // conservative answer.
03261   unsigned ZeroBits = LHSKnownZero.countLeadingOnes() +
03262                       RHSKnownZero.countLeadingOnes();
03263   // First handle the easy case: if we have enough zero bits there's
03264   // definitely no overflow.
03265   if (ZeroBits >= BitWidth)
03266     return OverflowResult::NeverOverflows;
03267 
03268   // Get the largest possible values for each operand.
03269   APInt LHSMax = ~LHSKnownZero;
03270   APInt RHSMax = ~RHSKnownZero;
03271 
03272   // We know the multiply operation doesn't overflow if the maximum values for
03273   // each operand will not overflow after we multiply them together.
03274   bool MaxOverflow;
03275   LHSMax.umul_ov(RHSMax, MaxOverflow);
03276   if (!MaxOverflow)
03277     return OverflowResult::NeverOverflows;
03278 
03279   // We know it always overflows if multiplying the smallest possible values for
03280   // the operands also results in overflow.
03281   bool MinOverflow;
03282   LHSKnownOne.umul_ov(RHSKnownOne, MinOverflow);
03283   if (MinOverflow)
03284     return OverflowResult::AlwaysOverflows;
03285 
03286   return OverflowResult::MayOverflow;
03287 }
03288 
03289 OverflowResult llvm::computeOverflowForUnsignedAdd(Value *LHS, Value *RHS,
03290                                                    const DataLayout &DL,
03291                                                    AssumptionCache *AC,
03292                                                    const Instruction *CxtI,
03293                                                    const DominatorTree *DT) {
03294   bool LHSKnownNonNegative, LHSKnownNegative;
03295   ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, DL, /*Depth=*/0,
03296                  AC, CxtI, DT);
03297   if (LHSKnownNonNegative || LHSKnownNegative) {
03298     bool RHSKnownNonNegative, RHSKnownNegative;
03299     ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, DL, /*Depth=*/0,
03300                    AC, CxtI, DT);
03301 
03302     if (LHSKnownNegative && RHSKnownNegative) {
03303       // The sign bit is set in both cases: this MUST overflow.
03304       // Create a simple add instruction, and insert it into the struct.
03305       return OverflowResult::AlwaysOverflows;
03306     }
03307 
03308     if (LHSKnownNonNegative && RHSKnownNonNegative) {
03309       // The sign bit is clear in both cases: this CANNOT overflow.
03310       // Create a simple add instruction, and insert it into the struct.
03311       return OverflowResult::NeverOverflows;
03312     }
03313   }
03314 
03315   return OverflowResult::MayOverflow;
03316 }
03317 
03318 static SelectPatternFlavor matchSelectPattern(ICmpInst::Predicate Pred,
03319                                               Value *CmpLHS, Value *CmpRHS,
03320                                               Value *TrueVal, Value *FalseVal,
03321                                               Value *&LHS, Value *&RHS) {
03322   LHS = CmpLHS;
03323   RHS = CmpRHS;
03324 
03325   // (icmp X, Y) ? X : Y
03326   if (TrueVal == CmpLHS && FalseVal == CmpRHS) {
03327     switch (Pred) {
03328     default: return SPF_UNKNOWN; // Equality.
03329     case ICmpInst::ICMP_UGT:
03330     case ICmpInst::ICMP_UGE: return SPF_UMAX;
03331     case ICmpInst::ICMP_SGT:
03332     case ICmpInst::ICMP_SGE: return SPF_SMAX;
03333     case ICmpInst::ICMP_ULT:
03334     case ICmpInst::ICMP_ULE: return SPF_UMIN;
03335     case ICmpInst::ICMP_SLT:
03336     case ICmpInst::ICMP_SLE: return SPF_SMIN;
03337     }
03338   }
03339 
03340   // (icmp X, Y) ? Y : X
03341   if (TrueVal == CmpRHS && FalseVal == CmpLHS) {
03342     switch (Pred) {
03343     default: return SPF_UNKNOWN; // Equality.
03344     case ICmpInst::ICMP_UGT:
03345     case ICmpInst::ICMP_UGE: return SPF_UMIN;
03346     case ICmpInst::ICMP_SGT:
03347     case ICmpInst::ICMP_SGE: return SPF_SMIN;
03348     case ICmpInst::ICMP_ULT:
03349     case ICmpInst::ICMP_ULE: return SPF_UMAX;
03350     case ICmpInst::ICMP_SLT:
03351     case ICmpInst::ICMP_SLE: return SPF_SMAX;
03352     }
03353   }
03354 
03355   if (ConstantInt *C1 = dyn_cast<ConstantInt>(CmpRHS)) {
03356     if ((CmpLHS == TrueVal && match(FalseVal, m_Neg(m_Specific(CmpLHS)))) ||
03357         (CmpLHS == FalseVal && match(TrueVal, m_Neg(m_Specific(CmpLHS))))) {
03358 
03359       // ABS(X) ==> (X >s 0) ? X : -X and (X >s -1) ? X : -X
03360       // NABS(X) ==> (X >s 0) ? -X : X and (X >s -1) ? -X : X
03361       if (Pred == ICmpInst::ICMP_SGT && (C1->isZero() || C1->isMinusOne())) {
03362         return (CmpLHS == TrueVal) ? SPF_ABS : SPF_NABS;
03363       }
03364 
03365       // ABS(X) ==> (X <s 0) ? -X : X and (X <s 1) ? -X : X
03366       // NABS(X) ==> (X <s 0) ? X : -X and (X <s 1) ? X : -X
03367       if (Pred == ICmpInst::ICMP_SLT && (C1->isZero() || C1->isOne())) {
03368         return (CmpLHS == FalseVal) ? SPF_ABS : SPF_NABS;
03369       }
03370     }
03371     
03372     // Y >s C ? ~Y : ~C == ~Y <s ~C ? ~Y : ~C = SMIN(~Y, ~C)
03373     if (const auto *C2 = dyn_cast<ConstantInt>(FalseVal)) {
03374       if (C1->getType() == C2->getType() && ~C1->getValue() == C2->getValue() &&
03375           (match(TrueVal, m_Not(m_Specific(CmpLHS))) ||
03376            match(CmpLHS, m_Not(m_Specific(TrueVal))))) {
03377         LHS = TrueVal;
03378         RHS = FalseVal;
03379         return SPF_SMIN;
03380       }
03381     }
03382   }
03383 
03384   // TODO: (X > 4) ? X : 5   -->  (X >= 5) ? X : 5  -->  MAX(X, 5)
03385 
03386   return SPF_UNKNOWN;
03387 }
03388 
03389 static Constant *lookThroughCast(ICmpInst *CmpI, Value *V1, Value *V2,
03390                                  Instruction::CastOps *CastOp) {
03391   CastInst *CI = dyn_cast<CastInst>(V1);
03392   Constant *C = dyn_cast<Constant>(V2);
03393   if (!CI || !C)
03394     return nullptr;
03395   *CastOp = CI->getOpcode();
03396 
03397   if (isa<SExtInst>(CI) && CmpI->isSigned()) {
03398     Constant *T = ConstantExpr::getTrunc(C, CI->getSrcTy());
03399     // This is only valid if the truncated value can be sign-extended
03400     // back to the original value.
03401     if (ConstantExpr::getSExt(T, C->getType()) == C)
03402       return T;
03403     return nullptr;
03404   }
03405   if (isa<ZExtInst>(CI) && CmpI->isUnsigned())
03406     return ConstantExpr::getTrunc(C, CI->getSrcTy());
03407 
03408   if (isa<TruncInst>(CI))
03409     return ConstantExpr::getIntegerCast(C, CI->getSrcTy(), CmpI->isSigned());
03410 
03411   return nullptr;
03412 }
03413 
03414 SelectPatternFlavor llvm::matchSelectPattern(Value *V,
03415                                              Value *&LHS, Value *&RHS,
03416                                              Instruction::CastOps *CastOp) {
03417   SelectInst *SI = dyn_cast<SelectInst>(V);
03418   if (!SI) return SPF_UNKNOWN;
03419 
03420   ICmpInst *CmpI = dyn_cast<ICmpInst>(SI->getCondition());
03421   if (!CmpI) return SPF_UNKNOWN;
03422 
03423   ICmpInst::Predicate Pred = CmpI->getPredicate();
03424   Value *CmpLHS = CmpI->getOperand(0);
03425   Value *CmpRHS = CmpI->getOperand(1);
03426   Value *TrueVal = SI->getTrueValue();
03427   Value *FalseVal = SI->getFalseValue();
03428 
03429   // Bail out early.
03430   if (CmpI->isEquality())
03431     return SPF_UNKNOWN;
03432 
03433   // Deal with type mismatches.
03434   if (CastOp && CmpLHS->getType() != TrueVal->getType()) {
03435     if (Constant *C = lookThroughCast(CmpI, TrueVal, FalseVal, CastOp))
03436       return ::matchSelectPattern(Pred, CmpLHS, CmpRHS,
03437                                   cast<CastInst>(TrueVal)->getOperand(0), C,
03438                                   LHS, RHS);
03439     if (Constant *C = lookThroughCast(CmpI, FalseVal, TrueVal, CastOp))
03440       return ::matchSelectPattern(Pred, CmpLHS, CmpRHS,
03441                                   C, cast<CastInst>(FalseVal)->getOperand(0),
03442                                   LHS, RHS);
03443   }
03444   return ::matchSelectPattern(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal,
03445                               LHS, RHS);
03446 }