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/ADT/Optional.h" 20 #include "llvm/IR/CallSite.h" 21 #include "llvm/IR/Constants.h" 22 #include "llvm/IR/Instruction.h" 23 #include "llvm/IR/Intrinsics.h" 24 #include <cassert> 25 #include <cstdint> 26 27 namespace llvm { 28 29 class AddOperator; 30 class APInt; 31 class AssumptionCache; 32 class DataLayout; 33 class DominatorTree; 34 class GEPOperator; 35 class IntrinsicInst; 36 struct KnownBits; 37 class Loop; 38 class LoopInfo; 39 class MDNode; 40 class OptimizationRemarkEmitter; 41 class StringRef; 42 class TargetLibraryInfo; 43 class Value; 44 45 /// Determine which bits of V are known to be either zero or one and return 46 /// them in the KnownZero/KnownOne bit sets. 47 /// 48 /// This function is defined on values with integer type, values with pointer 49 /// type, and vectors of integers. In the case 50 /// where V is a vector, the known zero and known one values are the 51 /// same width as the vector element, and the bit is set only if it is true 52 /// for all of the elements in the vector. 53 void computeKnownBits(const Value *V, KnownBits &Known, 54 const DataLayout &DL, unsigned Depth = 0, 55 AssumptionCache *AC = nullptr, 56 const Instruction *CxtI = nullptr, 57 const DominatorTree *DT = nullptr, 58 OptimizationRemarkEmitter *ORE = nullptr); 59 60 /// Returns the known bits rather than passing by reference. 61 KnownBits computeKnownBits(const Value *V, const DataLayout &DL, 62 unsigned Depth = 0, AssumptionCache *AC = nullptr, 63 const Instruction *CxtI = nullptr, 64 const DominatorTree *DT = nullptr, 65 OptimizationRemarkEmitter *ORE = nullptr); 66 67 /// Compute known bits from the range metadata. 68 /// \p KnownZero the set of bits that are known to be zero 69 /// \p KnownOne the set of bits that are known to be one 70 void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, 71 KnownBits &Known); 72 73 /// Return true if LHS and RHS have no common bits set. 74 bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, 75 const DataLayout &DL, 76 AssumptionCache *AC = nullptr, 77 const Instruction *CxtI = nullptr, 78 const DominatorTree *DT = nullptr); 79 80 /// Return true if the given value is known to have exactly one bit set when 81 /// defined. For vectors return true if every element is known to be a power 82 /// of two when defined. Supports values with integer or pointer type and 83 /// vectors of integers. If 'OrZero' is set, then return true if the given 84 /// value is either a power of two or zero. 85 bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, 86 bool OrZero = false, unsigned Depth = 0, 87 AssumptionCache *AC = nullptr, 88 const Instruction *CxtI = nullptr, 89 const DominatorTree *DT = nullptr); 90 91 bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI); 92 93 /// Return true if the given value is known to be non-zero when defined. For 94 /// vectors, return true if every element is known to be non-zero when 95 /// defined. For pointers, if the context instruction and dominator tree are 96 /// specified, perform context-sensitive analysis and return true if the 97 /// pointer couldn't possibly be null at the specified instruction. 98 /// Supports values with integer or pointer type and vectors of integers. 99 bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0, 100 AssumptionCache *AC = nullptr, 101 const Instruction *CxtI = nullptr, 102 const DominatorTree *DT = nullptr); 103 104 /// Returns true if the give value is known to be non-negative. 105 bool isKnownNonNegative(const Value *V, const DataLayout &DL, 106 unsigned Depth = 0, 107 AssumptionCache *AC = nullptr, 108 const Instruction *CxtI = nullptr, 109 const DominatorTree *DT = nullptr); 110 111 /// Returns true if the given value is known be positive (i.e. non-negative 112 /// and non-zero). 113 bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth = 0, 114 AssumptionCache *AC = nullptr, 115 const Instruction *CxtI = nullptr, 116 const DominatorTree *DT = nullptr); 117 118 /// Returns true if the given value is known be negative (i.e. non-positive 119 /// and non-zero). 120 bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth = 0, 121 AssumptionCache *AC = nullptr, 122 const Instruction *CxtI = nullptr, 123 const DominatorTree *DT = nullptr); 124 125 /// Return true if the given values are known to be non-equal when defined. 126 /// Supports scalar integer types only. 127 bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL, 128 AssumptionCache *AC = nullptr, 129 const Instruction *CxtI = nullptr, 130 const DominatorTree *DT = nullptr); 131 132 /// Return true if 'V & Mask' is known to be zero. We use this predicate to 133 /// simplify operations downstream. Mask is known to be zero for bits that V 134 /// cannot have. 135 /// 136 /// This function is defined on values with integer type, values with pointer 137 /// type, and vectors of integers. In the case 138 /// where V is a vector, the mask, known zero, and known one values are the 139 /// same width as the vector element, and the bit is set only if it is true 140 /// for all of the elements in the vector. 141 bool MaskedValueIsZero(const Value *V, const APInt &Mask, 142 const DataLayout &DL, 143 unsigned Depth = 0, AssumptionCache *AC = nullptr, 144 const Instruction *CxtI = nullptr, 145 const DominatorTree *DT = nullptr); 146 147 /// Return the number of times the sign bit of the register is replicated into 148 /// the other bits. We know that at least 1 bit is always equal to the sign 149 /// bit (itself), but other cases can give us information. For example, 150 /// immediately after an "ashr X, 2", we know that the top 3 bits are all 151 /// equal to each other, so we return 3. For vectors, return the number of 152 /// sign bits for the vector element with the mininum number of known sign 153 /// bits. 154 unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, 155 unsigned Depth = 0, AssumptionCache *AC = nullptr, 156 const Instruction *CxtI = nullptr, 157 const DominatorTree *DT = nullptr); 158 159 /// This function computes the integer multiple of Base that equals V. If 160 /// successful, it returns true and returns the multiple in Multiple. If 161 /// unsuccessful, it returns false. Also, if V can be simplified to an 162 /// integer, then the simplified V is returned in Val. Look through sext only 163 /// if LookThroughSExt=true. 164 bool ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, 165 bool LookThroughSExt = false, 166 unsigned Depth = 0); 167 168 /// Map a call instruction to an intrinsic ID. Libcalls which have equivalent 169 /// intrinsics are treated as-if they were intrinsics. 170 Intrinsic::ID getIntrinsicForCallSite(ImmutableCallSite ICS, 171 const TargetLibraryInfo *TLI); 172 173 /// Return true if we can prove that the specified FP value is never equal to 174 /// -0.0. 175 bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI, 176 unsigned Depth = 0); 177 178 /// Return true if we can prove that the specified FP value is either NaN or 179 /// never less than -0.0. 180 /// 181 /// NaN --> true 182 /// +0 --> true 183 /// -0 --> true 184 /// x > +0 --> true 185 /// x < -0 --> false 186 bool CannotBeOrderedLessThanZero(const Value *V, const TargetLibraryInfo *TLI); 187 188 /// Return true if the floating-point scalar value is not a NaN or if the 189 /// floating-point vector value has no NaN elements. Return false if a value 190 /// could ever be NaN. 191 bool isKnownNeverNaN(const Value *V); 192 193 /// Return true if we can prove that the specified FP value's sign bit is 0. 194 /// 195 /// NaN --> true/false (depending on the NaN's sign bit) 196 /// +0 --> true 197 /// -0 --> false 198 /// x > +0 --> true 199 /// x < -0 --> false 200 bool SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI); 201 202 /// If the specified value can be set by repeating the same byte in memory, 203 /// return the i8 value that it is represented with. This is true for all i8 204 /// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double 205 /// 0.0 etc. If the value can't be handled with a repeated byte store (e.g. 206 /// i16 0x1234), return null. 207 Value *isBytewiseValue(Value *V); 208 209 /// Given an aggregrate and an sequence of indices, see if the scalar value 210 /// indexed is already around as a register, for example if it were inserted 211 /// directly into the aggregrate. 212 /// 213 /// If InsertBefore is not null, this function will duplicate (modified) 214 /// insertvalues when a part of a nested struct is extracted. 215 Value *FindInsertedValue(Value *V, 216 ArrayRef<unsigned> idx_range, 217 Instruction *InsertBefore = nullptr); 218 219 /// Analyze the specified pointer to see if it can be expressed as a base 220 /// pointer plus a constant offset. Return the base and offset to the caller. 221 Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, 222 const DataLayout &DL); 223 static inline const Value * 224 GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset, 225 const DataLayout &DL) { 226 return GetPointerBaseWithConstantOffset(const_cast<Value *>(Ptr), Offset, 227 DL); 228 } 229 230 /// Returns true if the GEP is based on a pointer to a string (array of 231 // \p CharSize integers) and is indexing into this string. 232 bool isGEPBasedOnPointerToString(const GEPOperator *GEP, 233 unsigned CharSize = 8); 234 235 /// Represents offset+length into a ConstantDataArray. 236 struct ConstantDataArraySlice { 237 /// ConstantDataArray pointer. nullptr indicates a zeroinitializer (a valid 238 /// initializer, it just doesn't fit the ConstantDataArray interface). 239 const ConstantDataArray *Array; 240 241 /// Slice starts at this Offset. 242 uint64_t Offset; 243 244 /// Length of the slice. 245 uint64_t Length; 246 247 /// Moves the Offset and adjusts Length accordingly. 248 void move(uint64_t Delta) { 249 assert(Delta < Length); 250 Offset += Delta; 251 Length -= Delta; 252 } 253 254 /// Convenience accessor for elements in the slice. 255 uint64_t operator[](unsigned I) const { 256 return Array==nullptr ? 0 : Array->getElementAsInteger(I + Offset); 257 } 258 }; 259 260 /// Returns true if the value \p V is a pointer into a ConstantDataArray. 261 /// If successful \p Slice will point to a ConstantDataArray info object 262 /// with an appropriate offset. 263 bool getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice, 264 unsigned ElementSize, uint64_t Offset = 0); 265 266 /// This function computes the length of a null-terminated C string pointed to 267 /// by V. If successful, it returns true and returns the string in Str. If 268 /// unsuccessful, it returns false. This does not include the trailing null 269 /// character by default. If TrimAtNul is set to false, then this returns any 270 /// trailing null characters as well as any other characters that come after 271 /// it. 272 bool getConstantStringInfo(const Value *V, StringRef &Str, 273 uint64_t Offset = 0, bool TrimAtNul = true); 274 275 /// If we can compute the length of the string pointed to by the specified 276 /// pointer, return 'len+1'. If we can't, return 0. 277 uint64_t GetStringLength(const Value *V, unsigned CharSize = 8); 278 279 /// This method strips off any GEP address adjustments and pointer casts from 280 /// the specified value, returning the original object being addressed. Note 281 /// that the returned value has pointer type if the specified value does. If 282 /// the MaxLookup value is non-zero, it limits the number of instructions to 283 /// be stripped off. 284 Value *GetUnderlyingObject(Value *V, const DataLayout &DL, 285 unsigned MaxLookup = 6); 286 static inline const Value *GetUnderlyingObject(const Value *V, 287 const DataLayout &DL, 288 unsigned MaxLookup = 6) { 289 return GetUnderlyingObject(const_cast<Value *>(V), DL, MaxLookup); 290 } 291 292 /// \brief This method is similar to GetUnderlyingObject except that it can 293 /// look through phi and select instructions and return multiple objects. 294 /// 295 /// If LoopInfo is passed, loop phis are further analyzed. If a pointer 296 /// accesses different objects in each iteration, we don't look through the 297 /// phi node. E.g. consider this loop nest: 298 /// 299 /// int **A; 300 /// for (i) 301 /// for (j) { 302 /// A[i][j] = A[i-1][j] * B[j] 303 /// } 304 /// 305 /// This is transformed by Load-PRE to stash away A[i] for the next iteration 306 /// of the outer loop: 307 /// 308 /// Curr = A[0]; // Prev_0 309 /// for (i: 1..N) { 310 /// Prev = Curr; // Prev = PHI (Prev_0, Curr) 311 /// Curr = A[i]; 312 /// for (j: 0..N) { 313 /// Curr[j] = Prev[j] * B[j] 314 /// } 315 /// } 316 /// 317 /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects 318 /// should not assume that Curr and Prev share the same underlying object thus 319 /// it shouldn't look through the phi above. 320 void GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects, 321 const DataLayout &DL, LoopInfo *LI = nullptr, 322 unsigned MaxLookup = 6); 323 324 /// This is a wrapper around GetUnderlyingObjects and adds support for basic 325 /// ptrtoint+arithmetic+inttoptr sequences. 326 bool getUnderlyingObjectsForCodeGen(const Value *V, 327 SmallVectorImpl<Value *> &Objects, 328 const DataLayout &DL); 329 330 /// Return true if the only users of this pointer are lifetime markers. 331 bool onlyUsedByLifetimeMarkers(const Value *V); 332 333 /// Return true if the instruction does not have any effects besides 334 /// calculating the result and does not have undefined behavior. 335 /// 336 /// This method never returns true for an instruction that returns true for 337 /// mayHaveSideEffects; however, this method also does some other checks in 338 /// addition. It checks for undefined behavior, like dividing by zero or 339 /// loading from an invalid pointer (but not for undefined results, like a 340 /// shift with a shift amount larger than the width of the result). It checks 341 /// for malloc and alloca because speculatively executing them might cause a 342 /// memory leak. It also returns false for instructions related to control 343 /// flow, specifically terminators and PHI nodes. 344 /// 345 /// If the CtxI is specified this method performs context-sensitive analysis 346 /// and returns true if it is safe to execute the instruction immediately 347 /// before the CtxI. 348 /// 349 /// If the CtxI is NOT specified this method only looks at the instruction 350 /// itself and its operands, so if this method returns true, it is safe to 351 /// move the instruction as long as the correct dominance relationships for 352 /// the operands and users hold. 353 /// 354 /// This method can return true for instructions that read memory; 355 /// for such instructions, moving them may change the resulting value. 356 bool isSafeToSpeculativelyExecute(const Value *V, 357 const Instruction *CtxI = nullptr, 358 const DominatorTree *DT = nullptr); 359 360 /// Returns true if the result or effects of the given instructions \p I 361 /// depend on or influence global memory. 362 /// Memory dependence arises for example if the instruction reads from 363 /// memory or may produce effects or undefined behaviour. Memory dependent 364 /// instructions generally cannot be reorderd with respect to other memory 365 /// dependent instructions or moved into non-dominated basic blocks. 366 /// Instructions which just compute a value based on the values of their 367 /// operands are not memory dependent. 368 bool mayBeMemoryDependent(const Instruction &I); 369 370 /// Return true if it is valid to use the assumptions provided by an 371 /// assume intrinsic, I, at the point in the control-flow identified by the 372 /// context instruction, CxtI. 373 bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, 374 const DominatorTree *DT = nullptr); 375 376 enum class OverflowResult { AlwaysOverflows, MayOverflow, NeverOverflows }; 377 378 OverflowResult computeOverflowForUnsignedMul(const Value *LHS, 379 const Value *RHS, 380 const DataLayout &DL, 381 AssumptionCache *AC, 382 const Instruction *CxtI, 383 const DominatorTree *DT); 384 OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, 385 const Value *RHS, 386 const DataLayout &DL, 387 AssumptionCache *AC, 388 const Instruction *CxtI, 389 const DominatorTree *DT); 390 OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, 391 const DataLayout &DL, 392 AssumptionCache *AC = nullptr, 393 const Instruction *CxtI = nullptr, 394 const DominatorTree *DT = nullptr); 395 /// This version also leverages the sign bit of Add if known. 396 OverflowResult computeOverflowForSignedAdd(const AddOperator *Add, 397 const DataLayout &DL, 398 AssumptionCache *AC = nullptr, 399 const Instruction *CxtI = nullptr, 400 const DominatorTree *DT = nullptr); 401 402 /// Returns true if the arithmetic part of the \p II 's result is 403 /// used only along the paths control dependent on the computation 404 /// not overflowing, \p II being an <op>.with.overflow intrinsic. 405 bool isOverflowIntrinsicNoWrap(const IntrinsicInst *II, 406 const DominatorTree &DT); 407 408 /// Return true if this function can prove that the instruction I will 409 /// always transfer execution to one of its successors (including the next 410 /// instruction that follows within a basic block). E.g. this is not 411 /// guaranteed for function calls that could loop infinitely. 412 /// 413 /// In other words, this function returns false for instructions that may 414 /// transfer execution or fail to transfer execution in a way that is not 415 /// captured in the CFG nor in the sequence of instructions within a basic 416 /// block. 417 /// 418 /// Undefined behavior is assumed not to happen, so e.g. division is 419 /// guaranteed to transfer execution to the following instruction even 420 /// though division by zero might cause undefined behavior. 421 bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I); 422 423 /// Return true if this function can prove that the instruction I 424 /// is executed for every iteration of the loop L. 425 /// 426 /// Note that this currently only considers the loop header. 427 bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, 428 const Loop *L); 429 430 /// Return true if this function can prove that I is guaranteed to yield 431 /// full-poison (all bits poison) if at least one of its operands are 432 /// full-poison (all bits poison). 433 /// 434 /// The exact rules for how poison propagates through instructions have 435 /// not been settled as of 2015-07-10, so this function is conservative 436 /// and only considers poison to be propagated in uncontroversial 437 /// cases. There is no attempt to track values that may be only partially 438 /// poison. 439 bool propagatesFullPoison(const Instruction *I); 440 441 /// Return either nullptr or an operand of I such that I will trigger 442 /// undefined behavior if I is executed and that operand has a full-poison 443 /// value (all bits poison). 444 const Value *getGuaranteedNonFullPoisonOp(const Instruction *I); 445 446 /// Return true if this function can prove that if PoisonI is executed 447 /// and yields a full-poison value (all bits poison), then that will 448 /// trigger undefined behavior. 449 /// 450 /// Note that this currently only considers the basic block that is 451 /// the parent of I. 452 bool programUndefinedIfFullPoison(const Instruction *PoisonI); 453 454 /// \brief Specific patterns of select instructions we can match. 455 enum SelectPatternFlavor { 456 SPF_UNKNOWN = 0, 457 SPF_SMIN, /// Signed minimum 458 SPF_UMIN, /// Unsigned minimum 459 SPF_SMAX, /// Signed maximum 460 SPF_UMAX, /// Unsigned maximum 461 SPF_FMINNUM, /// Floating point minnum 462 SPF_FMAXNUM, /// Floating point maxnum 463 SPF_ABS, /// Absolute value 464 SPF_NABS /// Negated absolute value 465 }; 466 467 /// \brief Behavior when a floating point min/max is given one NaN and one 468 /// non-NaN as input. 469 enum SelectPatternNaNBehavior { 470 SPNB_NA = 0, /// NaN behavior not applicable. 471 SPNB_RETURNS_NAN, /// Given one NaN input, returns the NaN. 472 SPNB_RETURNS_OTHER, /// Given one NaN input, returns the non-NaN. 473 SPNB_RETURNS_ANY /// Given one NaN input, can return either (or 474 /// it has been determined that no operands can 475 /// be NaN). 476 }; 477 478 struct SelectPatternResult { 479 SelectPatternFlavor Flavor; 480 SelectPatternNaNBehavior NaNBehavior; /// Only applicable if Flavor is 481 /// SPF_FMINNUM or SPF_FMAXNUM. 482 bool Ordered; /// When implementing this min/max pattern as 483 /// fcmp; select, does the fcmp have to be 484 /// ordered? 485 486 /// \brief Return true if \p SPF is a min or a max pattern. 487 static bool isMinOrMax(SelectPatternFlavor SPF) { 488 return !(SPF == SPF_UNKNOWN || SPF == SPF_ABS || SPF == SPF_NABS); 489 } 490 }; 491 492 /// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind 493 /// and providing the out parameter results if we successfully match. 494 /// 495 /// If CastOp is not nullptr, also match MIN/MAX idioms where the type does 496 /// not match that of the original select. If this is the case, the cast 497 /// operation (one of Trunc,SExt,Zext) that must be done to transform the 498 /// type of LHS and RHS into the type of V is returned in CastOp. 499 /// 500 /// For example: 501 /// %1 = icmp slt i32 %a, i32 4 502 /// %2 = sext i32 %a to i64 503 /// %3 = select i1 %1, i64 %2, i64 4 504 /// 505 /// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt 506 /// 507 SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, 508 Instruction::CastOps *CastOp = nullptr); 509 static inline SelectPatternResult 510 matchSelectPattern(const Value *V, const Value *&LHS, const Value *&RHS, 511 Instruction::CastOps *CastOp = nullptr) { 512 Value *L = const_cast<Value*>(LHS); 513 Value *R = const_cast<Value*>(RHS); 514 auto Result = matchSelectPattern(const_cast<Value*>(V), L, R); 515 LHS = L; 516 RHS = R; 517 return Result; 518 } 519 520 /// Return true if RHS is known to be implied true by LHS. Return false if 521 /// RHS is known to be implied false by LHS. Otherwise, return None if no 522 /// implication can be made. 523 /// A & B must be i1 (boolean) values or a vector of such values. Note that 524 /// the truth table for implication is the same as <=u on i1 values (but not 525 /// <=s!). The truth table for both is: 526 /// | T | F (B) 527 /// T | T | F 528 /// F | T | T 529 /// (A) 530 Optional<bool> isImpliedCondition(const Value *LHS, const Value *RHS, 531 const DataLayout &DL, bool LHSIsTrue = true, 532 unsigned Depth = 0); 533 } // end namespace llvm 534 535 #endif // LLVM_ANALYSIS_VALUETRACKING_H 536
