Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/IVDescriptors.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/Analysis/IVDescriptors.h - IndVar Descriptors -------*- 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 "describes" induction and recurrence variables.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H
14
#define LLVM_ANALYSIS_IVDESCRIPTORS_H
15
16
#include "llvm/ADT/DenseMap.h"
17
#include "llvm/ADT/Optional.h"
18
#include "llvm/ADT/SetVector.h"
19
#include "llvm/ADT/SmallPtrSet.h"
20
#include "llvm/ADT/SmallVector.h"
21
#include "llvm/ADT/StringRef.h"
22
#include "llvm/Analysis/AliasAnalysis.h"
23
#include "llvm/Analysis/DemandedBits.h"
24
#include "llvm/Analysis/EHPersonalities.h"
25
#include "llvm/Analysis/MustExecute.h"
26
#include "llvm/Analysis/TargetTransformInfo.h"
27
#include "llvm/IR/Dominators.h"
28
#include "llvm/IR/IRBuilder.h"
29
#include "llvm/IR/InstrTypes.h"
30
#include "llvm/IR/Operator.h"
31
#include "llvm/IR/ValueHandle.h"
32
#include "llvm/Support/Casting.h"
33
34
namespace llvm {
35
36
class AliasSet;
37
class AliasSetTracker;
38
class BasicBlock;
39
class DataLayout;
40
class Loop;
41
class LoopInfo;
42
class OptimizationRemarkEmitter;
43
class PredicatedScalarEvolution;
44
class PredIteratorCache;
45
class ScalarEvolution;
46
class SCEV;
47
class TargetLibraryInfo;
48
class TargetTransformInfo;
49
50
/// The RecurrenceDescriptor is used to identify recurrences variables in a
51
/// loop. Reduction is a special case of recurrence that has uses of the
52
/// recurrence variable outside the loop. The method isReductionPHI identifies
53
/// reductions that are basic recurrences.
54
///
55
/// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
56
/// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
57
/// array[i]; } is a summation of array elements. Basic recurrences are a
58
/// special case of chains of recurrences (CR). See ScalarEvolution for CR
59
/// references.
60
61
/// This struct holds information about recurrence variables.
62
class RecurrenceDescriptor {
63
public:
64
  /// This enum represents the kinds of recurrences that we support.
65
  enum RecurrenceKind {
66
    RK_NoRecurrence,  ///< Not a recurrence.
67
    RK_IntegerAdd,    ///< Sum of integers.
68
    RK_IntegerMult,   ///< Product of integers.
69
    RK_IntegerOr,     ///< Bitwise or logical OR of numbers.
70
    RK_IntegerAnd,    ///< Bitwise or logical AND of numbers.
71
    RK_IntegerXor,    ///< Bitwise or logical XOR of numbers.
72
    RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
73
    RK_FloatAdd,      ///< Sum of floats.
74
    RK_FloatMult,     ///< Product of floats.
75
    RK_FloatMinMax    ///< Min/max implemented in terms of select(cmp()).
76
  };
77
78
  // This enum represents the kind of minmax recurrence.
79
  enum MinMaxRecurrenceKind {
80
    MRK_Invalid,
81
    MRK_UIntMin,
82
    MRK_UIntMax,
83
    MRK_SIntMin,
84
    MRK_SIntMax,
85
    MRK_FloatMin,
86
    MRK_FloatMax
87
  };
88
89
115k
  RecurrenceDescriptor() = default;
90
91
  RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
92
                       FastMathFlags FMF, MinMaxRecurrenceKind MK,
93
                       Instruction *UAI, Type *RT, bool Signed,
94
                       SmallPtrSetImpl<Instruction *> &CI)
95
      : StartValue(Start), LoopExitInstr(Exit), Kind(K), FMF(FMF),
96
        MinMaxKind(MK), UnsafeAlgebraInst(UAI), RecurrenceType(RT),
97
8.23k
        IsSigned(Signed) {
98
8.23k
    CastInsts.insert(CI.begin(), CI.end());
99
8.23k
  }
100
101
  /// This POD struct holds information about a potential recurrence operation.
102
  class InstDesc {
103
  public:
104
    InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
105
        : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
106
2.73M
          UnsafeAlgebraInst(UAI) {}
107
108
    InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
109
        : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
110
3.06k
          UnsafeAlgebraInst(UAI) {}
111
112
409k
    bool isRecurrence() { return IsRecurrence; }
113
114
0
    bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
115
116
418k
    Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
117
118
10.3k
    MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
119
120
45.8k
    Instruction *getPatternInst() { return PatternLastInst; }
121
122
  private:
123
    // Is this instruction a recurrence candidate.
124
    bool IsRecurrence;
125
    // The last instruction in a min/max pattern (select of the select(icmp())
126
    // pattern), or the current recurrence instruction otherwise.
127
    Instruction *PatternLastInst;
128
    // If this is a min/max pattern the comparison predicate.
129
    MinMaxRecurrenceKind MinMaxKind;
130
    // Recurrence has unsafe algebra.
131
    Instruction *UnsafeAlgebraInst;
132
  };
133
134
  /// Returns a struct describing if the instruction 'I' can be a recurrence
135
  /// variable of type 'Kind'. If the recurrence is a min/max pattern of
136
  /// select(icmp()) this function advances the instruction pointer 'I' from the
137
  /// compare instruction to the select instruction and stores this pointer in
138
  /// 'PatternLastInst' member of the returned struct.
139
  static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
140
                                    InstDesc &Prev, bool HasFunNoNaNAttr);
141
142
  /// Returns true if instruction I has multiple uses in Insts
143
  static bool hasMultipleUsesOf(Instruction *I,
144
                                SmallPtrSetImpl<Instruction *> &Insts,
145
                                unsigned MaxNumUses);
146
147
  /// Returns true if all uses of the instruction I is within the Set.
148
  static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
149
150
  /// Returns a struct describing if the instruction if the instruction is a
151
  /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
152
  /// or max(X, Y).
153
  static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
154
155
  /// Returns a struct describing if the instruction is a
156
  /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
157
  static InstDesc isConditionalRdxPattern(RecurrenceKind Kind, Instruction *I);
158
159
  /// Returns identity corresponding to the RecurrenceKind.
160
  static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
161
162
  /// Returns the opcode of binary operation corresponding to the
163
  /// RecurrenceKind.
164
  static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
165
166
  /// Returns true if Phi is a reduction of type Kind and adds it to the
167
  /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
168
  /// non-null, the minimal bit width needed to compute the reduction will be
169
  /// computed.
170
  static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
171
                              bool HasFunNoNaNAttr,
172
                              RecurrenceDescriptor &RedDes,
173
                              DemandedBits *DB = nullptr,
174
                              AssumptionCache *AC = nullptr,
175
                              DominatorTree *DT = nullptr);
176
177
  /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
178
  /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
179
  /// non-null, the minimal bit width needed to compute the reduction will be
180
  /// computed.
181
  static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
182
                             RecurrenceDescriptor &RedDes,
183
                             DemandedBits *DB = nullptr,
184
                             AssumptionCache *AC = nullptr,
185
                             DominatorTree *DT = nullptr);
186
187
  /// Returns true if Phi is a first-order recurrence. A first-order recurrence
188
  /// is a non-reduction recurrence relation in which the value of the
189
  /// recurrence in the current loop iteration equals a value defined in the
190
  /// previous iteration. \p SinkAfter includes pairs of instructions where the
191
  /// first will be rescheduled to appear after the second if/when the loop is
192
  /// vectorized. It may be augmented with additional pairs if needed in order
193
  /// to handle Phi as a first-order recurrence.
194
  static bool
195
  isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
196
                         DenseMap<Instruction *, Instruction *> &SinkAfter,
197
                         DominatorTree *DT);
198
199
2.41k
  RecurrenceKind getRecurrenceKind() { return Kind; }
200
201
1.42k
  MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
202
203
2.24k
  FastMathFlags getFastMathFlags() { return FMF; }
204
205
1.36k
  TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
206
207
9.59k
  Instruction *getLoopExitInstr() { return LoopExitInstr; }
208
209
  /// Returns true if the recurrence has unsafe algebra which requires a relaxed
210
  /// floating-point model.
211
8.23k
  bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
212
213
  /// Returns first unsafe algebra instruction in the PHI node's use-chain.
214
1.77k
  Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
215
216
  /// Returns true if the recurrence kind is an integer kind.
217
  static bool isIntegerRecurrenceKind(RecurrenceKind Kind);
218
219
  /// Returns true if the recurrence kind is a floating point kind.
220
  static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind);
221
222
  /// Returns true if the recurrence kind is an arithmetic kind.
223
  static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
224
225
  /// Returns the type of the recurrence. This type can be narrower than the
226
  /// actual type of the Phi if the recurrence has been type-promoted.
227
5.55k
  Type *getRecurrenceType() { return RecurrenceType; }
228
229
  /// Returns a reference to the instructions used for type-promoting the
230
  /// recurrence.
231
3.44k
  SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }
232
233
  /// Returns true if all source operands of the recurrence are SExtInsts.
234
13
  bool isSigned() { return IsSigned; }
235
236
private:
237
  // The starting value of the recurrence.
238
  // It does not have to be zero!
239
  TrackingVH<Value> StartValue;
240
  // The instruction who's value is used outside the loop.
241
  Instruction *LoopExitInstr = nullptr;
242
  // The kind of the recurrence.
243
  RecurrenceKind Kind = RK_NoRecurrence;
244
  // The fast-math flags on the recurrent instructions.  We propagate these
245
  // fast-math flags into the vectorized FP instructions we generate.
246
  FastMathFlags FMF;
247
  // If this a min/max recurrence the kind of recurrence.
248
  MinMaxRecurrenceKind MinMaxKind = MRK_Invalid;
249
  // First occurrence of unasfe algebra in the PHI's use-chain.
250
  Instruction *UnsafeAlgebraInst = nullptr;
251
  // The type of the recurrence.
252
  Type *RecurrenceType = nullptr;
253
  // True if all source operands of the recurrence are SExtInsts.
254
  bool IsSigned = false;
255
  // Instructions used for type-promoting the recurrence.
256
  SmallPtrSet<Instruction *, 8> CastInsts;
257
};
258
259
/// A struct for saving information about induction variables.
260
class InductionDescriptor {
261
public:
262
  /// This enum represents the kinds of inductions that we support.
263
  enum InductionKind {
264
    IK_NoInduction,  ///< Not an induction variable.
265
    IK_IntInduction, ///< Integer induction variable. Step = C.
266
    IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
267
    IK_FpInduction   ///< Floating point induction variable.
268
  };
269
270
public:
271
  /// Default constructor - creates an invalid induction.
272
172k
  InductionDescriptor() = default;
273
274
  /// Get the consecutive direction. Returns:
275
  ///   0 - unknown or non-consecutive.
276
  ///   1 - consecutive and increasing.
277
  ///  -1 - consecutive and decreasing.
278
  int getConsecutiveDirection() const;
279
280
145k
  Value *getStartValue() const { return StartValue; }
281
235k
  InductionKind getKind() const { return IK; }
282
66.9k
  const SCEV *getStep() const { return Step; }
283
85
  BinaryOperator *getInductionBinOp() const { return InductionBinOp; }
284
  ConstantInt *getConstIntStepValue() const;
285
286
  /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
287
  /// induction, the induction descriptor \p D will contain the data describing
288
  /// this induction. If by some other means the caller has a better SCEV
289
  /// expression for \p Phi than the one returned by the ScalarEvolution
290
  /// analysis, it can be passed through \p Expr. If the def-use chain
291
  /// associated with the phi includes casts (that we know we can ignore
292
  /// under proper runtime checks), they are passed through \p CastsToIgnore.
293
  static bool
294
  isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
295
                 InductionDescriptor &D, const SCEV *Expr = nullptr,
296
                 SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
297
298
  /// Returns true if \p Phi is a floating point induction in the loop \p L.
299
  /// If \p Phi is an induction, the induction descriptor \p D will contain
300
  /// the data describing this induction.
301
  static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
302
                               InductionDescriptor &D);
303
304
  /// Returns true if \p Phi is a loop \p L induction, in the context associated
305
  /// with the run-time predicate of PSE. If \p Assume is true, this can add
306
  /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
307
  /// induction.
308
  /// If \p Phi is an induction, \p D will contain the data describing this
309
  /// induction.
310
  static bool isInductionPHI(PHINode *Phi, const Loop *L,
311
                             PredicatedScalarEvolution &PSE,
312
                             InductionDescriptor &D, bool Assume = false);
313
314
  /// Returns true if the induction type is FP and the binary operator does
315
  /// not have the "fast-math" property. Such operation requires a relaxed FP
316
  /// mode.
317
65.6k
  bool hasUnsafeAlgebra() {
318
65.6k
    return (IK == IK_FpInduction) && 
InductionBinOp71
&&
319
65.6k
           
!cast<FPMathOperator>(InductionBinOp)->isFast()71
;
320
65.6k
  }
321
322
  /// Returns induction operator that does not have "fast-math" property
323
  /// and requires FP unsafe mode.
324
44
  Instruction *getUnsafeAlgebraInst() {
325
44
    if (IK != IK_FpInduction)
326
1
      return nullptr;
327
43
328
43
    if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
329
0
      return nullptr;
330
43
    return InductionBinOp;
331
43
  }
332
333
  /// Returns binary opcode of the induction operator.
334
26.3k
  Instruction::BinaryOps getInductionOpcode() const {
335
26.3k
    return InductionBinOp ? 
InductionBinOp->getOpcode()26.3k
336
26.3k
                          : 
Instruction::BinaryOpsEnd58
;
337
26.3k
  }
338
339
  /// Returns a reference to the type cast instructions in the induction
340
  /// update chain, that are redundant when guarded with a runtime
341
  /// SCEV overflow check.
342
204k
  const SmallVectorImpl<Instruction *> &getCastInsts() const {
343
204k
    return RedundantCasts;
344
204k
  }
345
346
private:
347
  /// Private constructor - used by \c isInductionPHI.
348
  InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
349
                      BinaryOperator *InductionBinOp = nullptr,
350
                      SmallVectorImpl<Instruction *> *Casts = nullptr);
351
352
  /// Start value.
353
  TrackingVH<Value> StartValue;
354
  /// Induction kind.
355
  InductionKind IK = IK_NoInduction;
356
  /// Step value.
357
  const SCEV *Step = nullptr;
358
  // Instruction that advances induction variable.
359
  BinaryOperator *InductionBinOp = nullptr;
360
  // Instructions used for type-casts of the induction variable,
361
  // that are redundant when guarded with a runtime SCEV overflow check.
362
  SmallVector<Instruction *, 2> RedundantCasts;
363
};
364
365
} // end namespace llvm
366
367
#endif // LLVM_ANALYSIS_IVDESCRIPTORS_H