Coverage Report

Created: 2018-11-13 17:19

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