1193323Sed//===- llvm/Analysis/ValueTracking.h - Walk computations --------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file contains routines that help analyze properties that chains of 11193323Sed// computations have. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#ifndef LLVM_ANALYSIS_VALUETRACKING_H 16193323Sed#define LLVM_ANALYSIS_VALUETRACKING_H 17193323Sed 18224145Sdim#include "llvm/ADT/ArrayRef.h" 19218893Sdim#include "llvm/Support/DataTypes.h" 20193323Sed 21193323Sednamespace llvm { 22193323Sed class Value; 23193323Sed class Instruction; 24193323Sed class APInt; 25245431Sdim class DataLayout; 26235633Sdim class StringRef; 27235633Sdim class MDNode; 28263509Sdim class TargetLibraryInfo; 29235633Sdim 30193323Sed /// ComputeMaskedBits - Determine which of the bits specified in Mask are 31193323Sed /// known to be either zero or one and return them in the KnownZero/KnownOne 32193323Sed /// bit sets. This code only analyzes bits in Mask, in order to short-circuit 33193323Sed /// processing. 34198090Srdivacky /// 35198090Srdivacky /// This function is defined on values with integer type, values with pointer 36198090Srdivacky /// type (but only if TD is non-null), and vectors of integers. In the case 37198090Srdivacky /// where V is a vector, the mask, known zero, and known one values are the 38198090Srdivacky /// same width as the vector element, and the bit is set only if it is true 39198090Srdivacky /// for all of the elements in the vector. 40235633Sdim void ComputeMaskedBits(Value *V, APInt &KnownZero, APInt &KnownOne, 41245431Sdim const DataLayout *TD = 0, unsigned Depth = 0); 42235633Sdim void computeMaskedBitsLoad(const MDNode &Ranges, APInt &KnownZero); 43235633Sdim 44218893Sdim /// ComputeSignBit - Determine whether the sign bit is known to be zero or 45218893Sdim /// one. Convenience wrapper around ComputeMaskedBits. 46218893Sdim void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, 47245431Sdim const DataLayout *TD = 0, unsigned Depth = 0); 48218893Sdim 49252723Sdim /// isKnownToBeAPowerOfTwo - Return true if the given value is known to have 50252723Sdim /// exactly one bit set when defined. For vectors return true if every 51252723Sdim /// element is known to be a power of two when defined. Supports values with 52252723Sdim /// integer or pointer type and vectors of integers. If 'OrZero' is set then 53252723Sdim /// returns true if the given value is either a power of two or zero. 54252723Sdim bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero = false, unsigned Depth = 0); 55218893Sdim 56218893Sdim /// isKnownNonZero - Return true if the given value is known to be non-zero 57218893Sdim /// when defined. For vectors return true if every element is known to be 58218893Sdim /// non-zero when defined. Supports values with integer or pointer type and 59218893Sdim /// vectors of integers. 60245431Sdim bool isKnownNonZero(Value *V, const DataLayout *TD = 0, unsigned Depth = 0); 61218893Sdim 62193323Sed /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 63193323Sed /// this predicate to simplify operations downstream. Mask is known to be 64193323Sed /// zero for bits that V cannot have. 65198090Srdivacky /// 66198090Srdivacky /// This function is defined on values with integer type, values with pointer 67198090Srdivacky /// type (but only if TD is non-null), and vectors of integers. In the case 68198090Srdivacky /// where V is a vector, the mask, known zero, and known one values are the 69198090Srdivacky /// same width as the vector element, and the bit is set only if it is true 70198090Srdivacky /// for all of the elements in the vector. 71193323Sed bool MaskedValueIsZero(Value *V, const APInt &Mask, 72245431Sdim const DataLayout *TD = 0, unsigned Depth = 0); 73193323Sed 74193323Sed 75193323Sed /// ComputeNumSignBits - Return the number of times the sign bit of the 76193323Sed /// register is replicated into the other bits. We know that at least 1 bit 77193323Sed /// is always equal to the sign bit (itself), but other cases can give us 78193323Sed /// information. For example, immediately after an "ashr X, 2", we know that 79193323Sed /// the top 3 bits are all equal to each other, so we return 3. 80193323Sed /// 81193323Sed /// 'Op' must have a scalar integer type. 82193323Sed /// 83245431Sdim unsigned ComputeNumSignBits(Value *Op, const DataLayout *TD = 0, 84193323Sed unsigned Depth = 0); 85193323Sed 86199481Srdivacky /// ComputeMultiple - This function computes the integer multiple of Base that 87199481Srdivacky /// equals V. If successful, it returns true and returns the multiple in 88199481Srdivacky /// Multiple. If unsuccessful, it returns false. Also, if V can be 89199481Srdivacky /// simplified to an integer, then the simplified V is returned in Val. Look 90199481Srdivacky /// through sext only if LookThroughSExt=true. 91199481Srdivacky bool ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, 92199481Srdivacky bool LookThroughSExt = false, 93199481Srdivacky unsigned Depth = 0); 94199481Srdivacky 95193323Sed /// CannotBeNegativeZero - Return true if we can prove that the specified FP 96193323Sed /// value is never equal to -0.0. 97193323Sed /// 98193323Sed bool CannotBeNegativeZero(const Value *V, unsigned Depth = 0); 99193323Sed 100218893Sdim /// isBytewiseValue - If the specified value can be set by repeating the same 101218893Sdim /// byte in memory, return the i8 value that it is represented with. This is 102218893Sdim /// true for all i8 values obviously, but is also true for i32 0, i32 -1, 103218893Sdim /// i16 0xF0F0, double 0.0 etc. If the value can't be handled with a repeated 104218893Sdim /// byte store (e.g. i16 0x1234), return null. 105218893Sdim Value *isBytewiseValue(Value *V); 106218893Sdim 107210299Sed /// FindInsertedValue - Given an aggregrate and an sequence of indices, see if 108193323Sed /// the scalar value indexed is already around as a register, for example if 109193323Sed /// it were inserted directly into the aggregrate. 110193323Sed /// 111193323Sed /// If InsertBefore is not null, this function will duplicate (modified) 112193323Sed /// insertvalues when a part of a nested struct is extracted. 113193323Sed Value *FindInsertedValue(Value *V, 114224145Sdim ArrayRef<unsigned> idx_range, 115193323Sed Instruction *InsertBefore = 0); 116193323Sed 117218893Sdim /// GetPointerBaseWithConstantOffset - Analyze the specified pointer to see if 118218893Sdim /// it can be expressed as a base pointer plus a constant offset. Return the 119218893Sdim /// base and offset to the caller. 120218893Sdim Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, 121252723Sdim const DataLayout *TD); 122218893Sdim static inline const Value * 123218893Sdim GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset, 124252723Sdim const DataLayout *TD) { 125218893Sdim return GetPointerBaseWithConstantOffset(const_cast<Value*>(Ptr), Offset,TD); 126218893Sdim } 127218893Sdim 128235633Sdim /// getConstantStringInfo - This function computes the length of a 129193323Sed /// null-terminated C string pointed to by V. If successful, it returns true 130235633Sdim /// and returns the string in Str. If unsuccessful, it returns false. This 131235633Sdim /// does not include the trailing nul character by default. If TrimAtNul is 132235633Sdim /// set to false, then this returns any trailing nul characters as well as any 133235633Sdim /// other characters that come after it. 134235633Sdim bool getConstantStringInfo(const Value *V, StringRef &Str, 135235633Sdim uint64_t Offset = 0, bool TrimAtNul = true); 136235633Sdim 137204792Srdivacky /// GetStringLength - If we can compute the length of the string pointed to by 138204792Srdivacky /// the specified pointer, return 'len+1'. If we can't, return 0. 139204792Srdivacky uint64_t GetStringLength(Value *V); 140218893Sdim 141218893Sdim /// GetUnderlyingObject - This method strips off any GEP address adjustments 142218893Sdim /// and pointer casts from the specified value, returning the original object 143218893Sdim /// being addressed. Note that the returned value has pointer type if the 144218893Sdim /// specified value does. If the MaxLookup value is non-zero, it limits the 145218893Sdim /// number of instructions to be stripped off. 146245431Sdim Value *GetUnderlyingObject(Value *V, const DataLayout *TD = 0, 147218893Sdim unsigned MaxLookup = 6); 148218893Sdim static inline const Value * 149245431Sdim GetUnderlyingObject(const Value *V, const DataLayout *TD = 0, 150218893Sdim unsigned MaxLookup = 6) { 151218893Sdim return GetUnderlyingObject(const_cast<Value *>(V), TD, MaxLookup); 152218893Sdim } 153218893Sdim 154245431Sdim /// GetUnderlyingObjects - This method is similar to GetUnderlyingObject 155245431Sdim /// except that it can look through phi and select instructions and return 156245431Sdim /// multiple objects. 157245431Sdim void GetUnderlyingObjects(Value *V, 158245431Sdim SmallVectorImpl<Value *> &Objects, 159245431Sdim const DataLayout *TD = 0, 160245431Sdim unsigned MaxLookup = 6); 161245431Sdim 162224145Sdim /// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer 163224145Sdim /// are lifetime markers. 164224145Sdim bool onlyUsedByLifetimeMarkers(const Value *V); 165224145Sdim 166235633Sdim /// isSafeToSpeculativelyExecute - Return true if the instruction does not 167235633Sdim /// have any effects besides calculating the result and does not have 168235633Sdim /// undefined behavior. 169235633Sdim /// 170235633Sdim /// This method never returns true for an instruction that returns true for 171235633Sdim /// mayHaveSideEffects; however, this method also does some other checks in 172235633Sdim /// addition. It checks for undefined behavior, like dividing by zero or 173235633Sdim /// loading from an invalid pointer (but not for undefined results, like a 174235633Sdim /// shift with a shift amount larger than the width of the result). It checks 175235633Sdim /// for malloc and alloca because speculatively executing them might cause a 176235633Sdim /// memory leak. It also returns false for instructions related to control 177235633Sdim /// flow, specifically terminators and PHI nodes. 178235633Sdim /// 179235633Sdim /// This method only looks at the instruction itself and its operands, so if 180235633Sdim /// this method returns true, it is safe to move the instruction as long as 181235633Sdim /// the correct dominance relationships for the operands and users hold. 182235633Sdim /// However, this method can return true for instructions that read memory; 183235633Sdim /// for such instructions, moving them may change the resulting value. 184235633Sdim bool isSafeToSpeculativelyExecute(const Value *V, 185245431Sdim const DataLayout *TD = 0); 186235633Sdim 187252723Sdim /// isKnownNonNull - Return true if this pointer couldn't possibly be null by 188252723Sdim /// its definition. This returns true for allocas, non-extern-weak globals 189252723Sdim /// and byval arguments. 190263509Sdim bool isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI = 0); 191252723Sdim 192193323Sed} // end namespace llvm 193193323Sed 194193323Sed#endif 195