]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- llvm/Analysis/ValueTracking.h - Walk computations --------*- C++ -*-===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // | |
10 | // This file contains routines that help analyze properties that chains of | |
11 | // computations have. | |
12 | // | |
13 | //===----------------------------------------------------------------------===// | |
14 | ||
15 | #ifndef LLVM_ANALYSIS_VALUETRACKING_H | |
16 | #define LLVM_ANALYSIS_VALUETRACKING_H | |
17 | ||
18 | #include "llvm/ADT/ArrayRef.h" | |
19 | #include "llvm/Support/DataTypes.h" | |
20 | ||
21 | namespace llvm { | |
22 | class Value; | |
23 | class Instruction; | |
24 | class APInt; | |
970d7e83 | 25 | class DataLayout; |
223e47cc LB |
26 | class StringRef; |
27 | class MDNode; | |
85aaf69f | 28 | class AssumptionCache; |
1a4d82fc JJ |
29 | class DominatorTree; |
30 | class TargetLibraryInfo; | |
223e47cc | 31 | |
1a4d82fc JJ |
32 | /// Determine which bits of V are known to be either zero or one and return |
33 | /// them in the KnownZero/KnownOne bit sets. | |
223e47cc LB |
34 | /// |
35 | /// This function is defined on values with integer type, values with pointer | |
36 | /// type (but only if TD is non-null), and vectors of integers. In the case | |
1a4d82fc | 37 | /// where V is a vector, the known zero and known one values are the |
223e47cc LB |
38 | /// same width as the vector element, and the bit is set only if it is true |
39 | /// for all of the elements in the vector. | |
85aaf69f | 40 | void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, |
1a4d82fc | 41 | const DataLayout *TD = nullptr, unsigned Depth = 0, |
85aaf69f | 42 | AssumptionCache *AC = nullptr, |
1a4d82fc JJ |
43 | const Instruction *CxtI = nullptr, |
44 | const DominatorTree *DT = nullptr); | |
45 | /// Compute known bits from the range metadata. | |
46 | /// \p KnownZero the set of bits that are known to be zero | |
47 | void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, | |
48 | APInt &KnownZero); | |
223e47cc LB |
49 | |
50 | /// ComputeSignBit - Determine whether the sign bit is known to be zero or | |
1a4d82fc | 51 | /// one. Convenience wrapper around computeKnownBits. |
223e47cc | 52 | void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, |
1a4d82fc | 53 | const DataLayout *TD = nullptr, unsigned Depth = 0, |
85aaf69f | 54 | AssumptionCache *AC = nullptr, |
1a4d82fc JJ |
55 | const Instruction *CxtI = nullptr, |
56 | const DominatorTree *DT = nullptr); | |
223e47cc | 57 | |
970d7e83 LB |
58 | /// isKnownToBeAPowerOfTwo - Return true if the given value is known to have |
59 | /// exactly one bit set when defined. For vectors return true if every | |
60 | /// element is known to be a power of two when defined. Supports values with | |
61 | /// integer or pointer type and vectors of integers. If 'OrZero' is set then | |
62 | /// returns true if the given value is either a power of two or zero. | |
1a4d82fc | 63 | bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero = false, unsigned Depth = 0, |
85aaf69f | 64 | AssumptionCache *AC = nullptr, |
1a4d82fc JJ |
65 | const Instruction *CxtI = nullptr, |
66 | const DominatorTree *DT = nullptr); | |
223e47cc LB |
67 | |
68 | /// isKnownNonZero - Return true if the given value is known to be non-zero | |
69 | /// when defined. For vectors return true if every element is known to be | |
70 | /// non-zero when defined. Supports values with integer or pointer type and | |
71 | /// vectors of integers. | |
1a4d82fc | 72 | bool isKnownNonZero(Value *V, const DataLayout *TD = nullptr, |
85aaf69f | 73 | unsigned Depth = 0, AssumptionCache *AC = nullptr, |
1a4d82fc JJ |
74 | const Instruction *CxtI = nullptr, |
75 | const DominatorTree *DT = nullptr); | |
223e47cc LB |
76 | |
77 | /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use | |
78 | /// this predicate to simplify operations downstream. Mask is known to be | |
79 | /// zero for bits that V cannot have. | |
80 | /// | |
81 | /// This function is defined on values with integer type, values with pointer | |
82 | /// type (but only if TD is non-null), and vectors of integers. In the case | |
83 | /// where V is a vector, the mask, known zero, and known one values are the | |
84 | /// same width as the vector element, and the bit is set only if it is true | |
85 | /// for all of the elements in the vector. | |
85aaf69f | 86 | bool MaskedValueIsZero(Value *V, const APInt &Mask, |
1a4d82fc | 87 | const DataLayout *TD = nullptr, unsigned Depth = 0, |
85aaf69f | 88 | AssumptionCache *AC = nullptr, |
1a4d82fc JJ |
89 | const Instruction *CxtI = nullptr, |
90 | const DominatorTree *DT = nullptr); | |
223e47cc | 91 | |
223e47cc LB |
92 | /// ComputeNumSignBits - Return the number of times the sign bit of the |
93 | /// register is replicated into the other bits. We know that at least 1 bit | |
94 | /// is always equal to the sign bit (itself), but other cases can give us | |
95 | /// information. For example, immediately after an "ashr X, 2", we know that | |
96 | /// the top 3 bits are all equal to each other, so we return 3. | |
97 | /// | |
98 | /// 'Op' must have a scalar integer type. | |
99 | /// | |
1a4d82fc | 100 | unsigned ComputeNumSignBits(Value *Op, const DataLayout *TD = nullptr, |
85aaf69f | 101 | unsigned Depth = 0, AssumptionCache *AC = nullptr, |
1a4d82fc JJ |
102 | const Instruction *CxtI = nullptr, |
103 | const DominatorTree *DT = nullptr); | |
223e47cc LB |
104 | |
105 | /// ComputeMultiple - This function computes the integer multiple of Base that | |
106 | /// equals V. If successful, it returns true and returns the multiple in | |
107 | /// Multiple. If unsuccessful, it returns false. Also, if V can be | |
108 | /// simplified to an integer, then the simplified V is returned in Val. Look | |
109 | /// through sext only if LookThroughSExt=true. | |
110 | bool ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, | |
111 | bool LookThroughSExt = false, | |
112 | unsigned Depth = 0); | |
113 | ||
114 | /// CannotBeNegativeZero - Return true if we can prove that the specified FP | |
115 | /// value is never equal to -0.0. | |
116 | /// | |
117 | bool CannotBeNegativeZero(const Value *V, unsigned Depth = 0); | |
118 | ||
119 | /// isBytewiseValue - If the specified value can be set by repeating the same | |
120 | /// byte in memory, return the i8 value that it is represented with. This is | |
121 | /// true for all i8 values obviously, but is also true for i32 0, i32 -1, | |
122 | /// i16 0xF0F0, double 0.0 etc. If the value can't be handled with a repeated | |
123 | /// byte store (e.g. i16 0x1234), return null. | |
124 | Value *isBytewiseValue(Value *V); | |
125 | ||
126 | /// FindInsertedValue - Given an aggregrate and an sequence of indices, see if | |
127 | /// the scalar value indexed is already around as a register, for example if | |
128 | /// it were inserted directly into the aggregrate. | |
129 | /// | |
130 | /// If InsertBefore is not null, this function will duplicate (modified) | |
131 | /// insertvalues when a part of a nested struct is extracted. | |
132 | Value *FindInsertedValue(Value *V, | |
133 | ArrayRef<unsigned> idx_range, | |
1a4d82fc | 134 | Instruction *InsertBefore = nullptr); |
223e47cc LB |
135 | |
136 | /// GetPointerBaseWithConstantOffset - Analyze the specified pointer to see if | |
137 | /// it can be expressed as a base pointer plus a constant offset. Return the | |
138 | /// base and offset to the caller. | |
139 | Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, | |
970d7e83 | 140 | const DataLayout *TD); |
223e47cc LB |
141 | static inline const Value * |
142 | GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset, | |
970d7e83 | 143 | const DataLayout *TD) { |
223e47cc LB |
144 | return GetPointerBaseWithConstantOffset(const_cast<Value*>(Ptr), Offset,TD); |
145 | } | |
146 | ||
147 | /// getConstantStringInfo - This function computes the length of a | |
148 | /// null-terminated C string pointed to by V. If successful, it returns true | |
149 | /// and returns the string in Str. If unsuccessful, it returns false. This | |
150 | /// does not include the trailing nul character by default. If TrimAtNul is | |
151 | /// set to false, then this returns any trailing nul characters as well as any | |
152 | /// other characters that come after it. | |
153 | bool getConstantStringInfo(const Value *V, StringRef &Str, | |
154 | uint64_t Offset = 0, bool TrimAtNul = true); | |
155 | ||
156 | /// GetStringLength - If we can compute the length of the string pointed to by | |
157 | /// the specified pointer, return 'len+1'. If we can't, return 0. | |
158 | uint64_t GetStringLength(Value *V); | |
159 | ||
160 | /// GetUnderlyingObject - This method strips off any GEP address adjustments | |
161 | /// and pointer casts from the specified value, returning the original object | |
162 | /// being addressed. Note that the returned value has pointer type if the | |
163 | /// specified value does. If the MaxLookup value is non-zero, it limits the | |
164 | /// number of instructions to be stripped off. | |
1a4d82fc | 165 | Value *GetUnderlyingObject(Value *V, const DataLayout *TD = nullptr, |
223e47cc LB |
166 | unsigned MaxLookup = 6); |
167 | static inline const Value * | |
1a4d82fc | 168 | GetUnderlyingObject(const Value *V, const DataLayout *TD = nullptr, |
223e47cc LB |
169 | unsigned MaxLookup = 6) { |
170 | return GetUnderlyingObject(const_cast<Value *>(V), TD, MaxLookup); | |
171 | } | |
172 | ||
173 | /// GetUnderlyingObjects - This method is similar to GetUnderlyingObject | |
174 | /// except that it can look through phi and select instructions and return | |
175 | /// multiple objects. | |
176 | void GetUnderlyingObjects(Value *V, | |
177 | SmallVectorImpl<Value *> &Objects, | |
1a4d82fc | 178 | const DataLayout *TD = nullptr, |
223e47cc LB |
179 | unsigned MaxLookup = 6); |
180 | ||
181 | /// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer | |
182 | /// are lifetime markers. | |
183 | bool onlyUsedByLifetimeMarkers(const Value *V); | |
184 | ||
185 | /// isSafeToSpeculativelyExecute - Return true if the instruction does not | |
186 | /// have any effects besides calculating the result and does not have | |
187 | /// undefined behavior. | |
188 | /// | |
189 | /// This method never returns true for an instruction that returns true for | |
190 | /// mayHaveSideEffects; however, this method also does some other checks in | |
191 | /// addition. It checks for undefined behavior, like dividing by zero or | |
192 | /// loading from an invalid pointer (but not for undefined results, like a | |
193 | /// shift with a shift amount larger than the width of the result). It checks | |
194 | /// for malloc and alloca because speculatively executing them might cause a | |
195 | /// memory leak. It also returns false for instructions related to control | |
196 | /// flow, specifically terminators and PHI nodes. | |
197 | /// | |
198 | /// This method only looks at the instruction itself and its operands, so if | |
199 | /// this method returns true, it is safe to move the instruction as long as | |
200 | /// the correct dominance relationships for the operands and users hold. | |
201 | /// However, this method can return true for instructions that read memory; | |
202 | /// for such instructions, moving them may change the resulting value. | |
203 | bool isSafeToSpeculativelyExecute(const Value *V, | |
1a4d82fc | 204 | const DataLayout *TD = nullptr); |
970d7e83 LB |
205 | |
206 | /// isKnownNonNull - Return true if this pointer couldn't possibly be null by | |
207 | /// its definition. This returns true for allocas, non-extern-weak globals | |
208 | /// and byval arguments. | |
1a4d82fc JJ |
209 | bool isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI = nullptr); |
210 | ||
211 | /// Return true if it is valid to use the assumptions provided by an | |
212 | /// assume intrinsic, I, at the point in the control-flow identified by the | |
213 | /// context instruction, CxtI. | |
214 | bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, | |
215 | const DataLayout *DL = nullptr, | |
216 | const DominatorTree *DT = nullptr); | |
223e47cc | 217 | |
85aaf69f SL |
218 | enum class OverflowResult { AlwaysOverflows, MayOverflow, NeverOverflows }; |
219 | OverflowResult computeOverflowForUnsignedMul(Value *LHS, Value *RHS, | |
220 | const DataLayout *DL, | |
221 | AssumptionCache *AC, | |
222 | const Instruction *CxtI, | |
223 | const DominatorTree *DT); | |
224 | OverflowResult computeOverflowForUnsignedAdd(Value *LHS, Value *RHS, | |
225 | const DataLayout *DL, | |
226 | AssumptionCache *AC, | |
227 | const Instruction *CxtI, | |
228 | const DominatorTree *DT); | |
223e47cc LB |
229 | } // end namespace llvm |
230 | ||
231 | #endif |