Coverage Report

Created: 2019-07-24 05:18

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