Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/IVDescriptors.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/Analysis/IVDescriptors.cpp - 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
#include "llvm/Analysis/IVDescriptors.h"
14
#include "llvm/ADT/ScopeExit.h"
15
#include "llvm/Analysis/AliasAnalysis.h"
16
#include "llvm/Analysis/BasicAliasAnalysis.h"
17
#include "llvm/Analysis/DomTreeUpdater.h"
18
#include "llvm/Analysis/GlobalsModRef.h"
19
#include "llvm/Analysis/InstructionSimplify.h"
20
#include "llvm/Analysis/LoopInfo.h"
21
#include "llvm/Analysis/LoopPass.h"
22
#include "llvm/Analysis/MustExecute.h"
23
#include "llvm/Analysis/ScalarEvolution.h"
24
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
25
#include "llvm/Analysis/ScalarEvolutionExpander.h"
26
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
27
#include "llvm/Analysis/TargetTransformInfo.h"
28
#include "llvm/Analysis/ValueTracking.h"
29
#include "llvm/IR/Dominators.h"
30
#include "llvm/IR/Instructions.h"
31
#include "llvm/IR/Module.h"
32
#include "llvm/IR/PatternMatch.h"
33
#include "llvm/IR/ValueHandle.h"
34
#include "llvm/Pass.h"
35
#include "llvm/Support/Debug.h"
36
#include "llvm/Support/KnownBits.h"
37
38
using namespace llvm;
39
using namespace llvm::PatternMatch;
40
41
#define DEBUG_TYPE "iv-descriptors"
42
43
bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
44
1.80k
                                        SmallPtrSetImpl<Instruction *> &Set) {
45
3.32k
  for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; 
++Use1.52k
)
46
2.93k
    if (!Set.count(dyn_cast<Instruction>(*Use)))
47
1.41k
      return false;
48
1.80k
  
return true394
;
49
1.80k
}
50
51
909k
bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) {
52
909k
  switch (Kind) {
53
909k
  default:
54
299k
    break;
55
909k
  case RK_IntegerAdd:
56
610k
  case RK_IntegerMult:
57
610k
  case RK_IntegerOr:
58
610k
  case RK_IntegerAnd:
59
610k
  case RK_IntegerXor:
60
610k
  case RK_IntegerMinMax:
61
610k
    return true;
62
299k
  }
63
299k
  return false;
64
299k
}
65
66
44.9k
bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
67
44.9k
  return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
68
44.9k
}
69
70
579k
bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) {
71
579k
  switch (Kind) {
72
579k
  default:
73
381k
    break;
74
579k
  case RK_IntegerAdd:
75
197k
  case RK_IntegerMult:
76
197k
  case RK_FloatAdd:
77
197k
  case RK_FloatMult:
78
197k
    return true;
79
381k
  }
80
381k
  return false;
81
381k
}
82
83
/// Determines if Phi may have been type-promoted. If Phi has a single user
84
/// that ANDs the Phi with a type mask, return the user. RT is updated to
85
/// account for the narrower bit width represented by the mask, and the AND
86
/// instruction is added to CI.
87
static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
88
                                   SmallPtrSetImpl<Instruction *> &Visited,
89
197k
                                   SmallPtrSetImpl<Instruction *> &CI) {
90
197k
  if (!Phi->hasOneUse())
91
143k
    return Phi;
92
53.5k
93
53.5k
  const APInt *M = nullptr;
94
53.5k
  Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
95
53.5k
96
53.5k
  // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
97
53.5k
  // with a new integer type of the corresponding bit width.
98
53.5k
  if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
99
108
    int32_t Bits = (*M + 1).exactLogBase2();
100
108
    if (Bits > 0) {
101
72
      RT = IntegerType::get(Phi->getContext(), Bits);
102
72
      Visited.insert(Phi);
103
72
      CI.insert(J);
104
72
      return J;
105
72
    }
106
53.5k
  }
107
53.5k
  return Phi;
108
53.5k
}
109
110
/// Compute the minimal bit width needed to represent a reduction whose exit
111
/// instruction is given by Exit.
112
static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
113
                                                     DemandedBits *DB,
114
                                                     AssumptionCache *AC,
115
9
                                                     DominatorTree *DT) {
116
9
  bool IsSigned = false;
117
9
  const DataLayout &DL = Exit->getModule()->getDataLayout();
118
9
  uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());
119
9
120
9
  if (DB) {
121
9
    // Use the demanded bits analysis to determine the bits that are live out
122
9
    // of the exit instruction, rounding up to the nearest power of two. If the
123
9
    // use of demanded bits results in a smaller bit width, we know the value
124
9
    // must be positive (i.e., IsSigned = false), because if this were not the
125
9
    // case, the sign bit would have been demanded.
126
9
    auto Mask = DB->getDemandedBits(Exit);
127
9
    MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros();
128
9
  }
129
9
130
9
  if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && 
AC3
&&
DT3
) {
131
3
    // If demanded bits wasn't able to limit the bit width, we can try to use
132
3
    // value tracking instead. This can be the case, for example, if the value
133
3
    // may be negative.
134
3
    auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT);
135
3
    auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
136
3
    MaxBitWidth = NumTypeBits - NumSignBits;
137
3
    KnownBits Bits = computeKnownBits(Exit, DL);
138
3
    if (!Bits.isNonNegative()) {
139
1
      // If the value is not known to be non-negative, we set IsSigned to true,
140
1
      // meaning that we will use sext instructions instead of zext
141
1
      // instructions to restore the original type.
142
1
      IsSigned = true;
143
1
      if (!Bits.isNegative())
144
1
        // If the value is not known to be negative, we don't known what the
145
1
        // upper bit is, and therefore, we don't know what kind of extend we
146
1
        // will need. In this case, just increase the bit width by one bit and
147
1
        // use sext.
148
1
        ++MaxBitWidth;
149
1
    }
150
3
  }
151
9
  if (!isPowerOf2_64(MaxBitWidth))
152
2
    MaxBitWidth = NextPowerOf2(MaxBitWidth);
153
9
154
9
  return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
155
9
                        IsSigned);
156
9
}
157
158
/// Collect cast instructions that can be ignored in the vectorizer's cost
159
/// model, given a reduction exit value and the minimal type in which the
160
/// reduction can be represented.
161
static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit,
162
                                 Type *RecurrenceType,
163
6
                                 SmallPtrSetImpl<Instruction *> &Casts) {
164
6
165
6
  SmallVector<Instruction *, 8> Worklist;
166
6
  SmallPtrSet<Instruction *, 8> Visited;
167
6
  Worklist.push_back(Exit);
168
6
169
39
  while (!Worklist.empty()) {
170
33
    Instruction *Val = Worklist.pop_back_val();
171
33
    Visited.insert(Val);
172
33
    if (auto *Cast = dyn_cast<CastInst>(Val))
173
6
      if (Cast->getSrcTy() == RecurrenceType) {
174
4
        // If the source type of a cast instruction is equal to the recurrence
175
4
        // type, it will be eliminated, and should be ignored in the vectorizer
176
4
        // cost model.
177
4
        Casts.insert(Cast);
178
4
        continue;
179
4
      }
180
29
181
29
    // Add all operands to the work list if they are loop-varying values that
182
29
    // we haven't yet visited.
183
29
    for (Value *O : cast<User>(Val)->operands())
184
54
      if (auto *I = dyn_cast<Instruction>(O))
185
35
        if (TheLoop->contains(I) && !Visited.count(I))
186
27
          Worklist.push_back(I);
187
29
  }
188
6
}
189
190
bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
191
                                           Loop *TheLoop, bool HasFunNoNaNAttr,
192
                                           RecurrenceDescriptor &RedDes,
193
                                           DemandedBits *DB,
194
                                           AssumptionCache *AC,
195
909k
                                           DominatorTree *DT) {
196
909k
  if (Phi->getNumIncomingValues() != 2)
197
0
    return false;
198
909k
199
909k
  // Reduction variables are only found in the loop header block.
200
909k
  if (Phi->getParent() != TheLoop->getHeader())
201
27
    return false;
202
909k
203
909k
  // Obtain the reduction start value from the value that comes from the loop
204
909k
  // preheader.
205
909k
  Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
206
909k
207
909k
  // ExitInstruction is the single value which is used outside the loop.
208
909k
  // We only allow for a single reduction value to be used outside the loop.
209
909k
  // This includes users of the reduction, variables (which form a cycle
210
909k
  // which ends in the phi node).
211
909k
  Instruction *ExitInstruction = nullptr;
212
909k
  // Indicates that we found a reduction operation in our scan.
213
909k
  bool FoundReduxOp = false;
214
909k
215
909k
  // We start with the PHI node and scan for all of the users of this
216
909k
  // instruction. All users must be instructions that can be used as reduction
217
909k
  // variables (such as ADD). We must have a single out-of-block user. The cycle
218
909k
  // must include the original PHI.
219
909k
  bool FoundStartPHI = false;
220
909k
221
909k
  // To recognize min/max patterns formed by a icmp select sequence, we store
222
909k
  // the number of instruction we saw from the recognized min/max pattern,
223
909k
  //  to make sure we only see exactly the two instructions.
224
909k
  unsigned NumCmpSelectPatternInst = 0;
225
909k
  InstDesc ReduxDesc(false, nullptr);
226
909k
227
909k
  // Data used for determining if the recurrence has been type-promoted.
228
909k
  Type *RecurrenceType = Phi->getType();
229
909k
  SmallPtrSet<Instruction *, 4> CastInsts;
230
909k
  Instruction *Start = Phi;
231
909k
  bool IsSigned = false;
232
909k
233
909k
  SmallPtrSet<Instruction *, 8> VisitedInsts;
234
909k
  SmallVector<Instruction *, 8> Worklist;
235
909k
236
909k
  // Return early if the recurrence kind does not match the type of Phi. If the
237
909k
  // recurrence kind is arithmetic, we attempt to look through AND operations
238
909k
  // resulting from the type promotion performed by InstCombine.  Vector
239
909k
  // operations are not limited to the legal integer widths, so we may be able
240
909k
  // to evaluate the reduction in the narrower width.
241
909k
  if (RecurrenceType->isFloatingPointTy()) {
242
44.9k
    if (!isFloatingPointRecurrenceKind(Kind))
243
31.2k
      return false;
244
865k
  } else {
245
865k
    if (!isIntegerRecurrenceKind(Kind))
246
285k
      return false;
247
579k
    if (isArithmeticRecurrenceKind(Kind))
248
197k
      Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
249
579k
  }
250
909k
251
909k
  Worklist.push_back(Start);
252
593k
  VisitedInsts.insert(Start);
253
593k
254
593k
  // Start with all flags set because we will intersect this with the reduction
255
593k
  // flags from all the reduction operations.
256
593k
  FastMathFlags FMF = FastMathFlags::getFast();
257
593k
258
593k
  // A value in the reduction can be used:
259
593k
  //  - By the reduction:
260
593k
  //      - Reduction operation:
261
593k
  //        - One use of reduction value (safe).
262
593k
  //        - Multiple use of reduction value (not safe).
263
593k
  //      - PHI:
264
593k
  //        - All uses of the PHI must be the reduction (safe).
265
593k
  //        - Otherwise, not safe.
266
593k
  //  - By instructions outside of the loop (safe).
267
593k
  //      * One value may have several outside users, but all outside
268
593k
  //        uses must be of the same value.
269
593k
  //  - By an instruction that is not part of the reduction (not safe).
270
593k
  //    This is either:
271
593k
  //      * An instruction type other than PHI or the reduction operation.
272
593k
  //      * A PHI in the header other than the initial PHI.
273
1.19M
  while (!Worklist.empty()) {
274
1.18M
    Instruction *Cur = Worklist.back();
275
1.18M
    Worklist.pop_back();
276
1.18M
277
1.18M
    // No Users.
278
1.18M
    // If the instruction has no users then this is a broken chain and can't be
279
1.18M
    // a reduction variable.
280
1.18M
    if (Cur->use_empty())
281
11.2k
      return false;
282
1.17M
283
1.17M
    bool IsAPhi = isa<PHINode>(Cur);
284
1.17M
285
1.17M
    // A header PHI use other than the original PHI.
286
1.17M
    if (Cur != Phi && 
IsAPhi577k
&&
Cur->getParent() == Phi->getParent()1.80k
)
287
4
      return false;
288
1.17M
289
1.17M
    // Reductions of instructions such as Div, and Sub is only possible if the
290
1.17M
    // LHS is the reduction variable.
291
1.17M
    if (!Cur->isCommutative() && 
!IsAPhi984k
&&
!isa<SelectInst>(Cur)389k
&&
292
1.17M
        
!isa<ICmpInst>(Cur)375k
&&
!isa<FCmpInst>(Cur)359k
&&
293
1.17M
        
!VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0)))357k
)
294
168k
      return false;
295
1.00M
296
1.00M
    // Any reduction instruction must be of one of the allowed kinds. We ignore
297
1.00M
    // the starting value (the Phi or an AND instruction if the Phi has been
298
1.00M
    // type-promoted).
299
1.00M
    if (Cur != Start) {
300
408k
      ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
301
408k
      if (!ReduxDesc.isRecurrence())
302
366k
        return false;
303
41.8k
      if (isa<FPMathOperator>(ReduxDesc.getPatternInst()))
304
3.95k
        FMF &= ReduxDesc.getPatternInst()->getFastMathFlags();
305
41.8k
    }
306
1.00M
307
1.00M
    bool IsASelect = isa<SelectInst>(Cur);
308
634k
309
634k
    // A conditional reduction operation must only have 2 or less uses in
310
634k
    // VisitedInsts.
311
634k
    if (IsASelect && 
(666
Kind == RK_FloatAdd666
||
Kind == RK_FloatMult658
) &&
312
634k
        
hasMultipleUsesOf(Cur, VisitedInsts, 2)10
)
313
0
      return false;
314
634k
315
634k
    // A reduction operation must only have one use of the reduction value.
316
634k
    if (!IsAPhi && 
!IsASelect40.1k
&&
Kind != RK_IntegerMinMax39.4k
&&
317
634k
        
Kind != RK_FloatMinMax39.1k
&&
hasMultipleUsesOf(Cur, VisitedInsts, 1)39.1k
)
318
24
      return false;
319
634k
320
634k
    // All inputs to a PHI node must be a reduction value.
321
634k
    if (IsAPhi && 
Cur != Phi594k
&&
!areAllUsesIn(Cur, VisitedInsts)1.80k
)
322
1.41k
      return false;
323
633k
324
633k
    if (Kind == RK_IntegerMinMax &&
325
633k
        
(96.3k
isa<ICmpInst>(Cur)96.3k
||
isa<SelectInst>(Cur)96.0k
))
326
933
      ++NumCmpSelectPatternInst;
327
633k
    if (Kind == RK_FloatMinMax && 
(3.40k
isa<FCmpInst>(Cur)3.40k
||
isa<SelectInst>(Cur)3.38k
))
328
36
      ++NumCmpSelectPatternInst;
329
633k
330
633k
    // Check  whether we found a reduction operator.
331
633k
    FoundReduxOp |= !IsAPhi && 
Cur != Start40.1k
;
332
633k
333
633k
    // Process users of current instruction. Push non-PHI nodes after PHI nodes
334
633k
    // onto the stack. This way we are going to have seen all inputs to PHI
335
633k
    // nodes once we get to them.
336
633k
    SmallVector<Instruction *, 8> NonPHIs;
337
633k
    SmallVector<Instruction *, 8> PHIs;
338
1.46M
    for (User *U : Cur->users()) {
339
1.46M
      Instruction *UI = cast<Instruction>(U);
340
1.46M
341
1.46M
      // Check if we found the exit user.
342
1.46M
      BasicBlock *Parent = UI->getParent();
343
1.46M
      if (!TheLoop->contains(Parent)) {
344
46.6k
        // If we already know this instruction is used externally, move on to
345
46.6k
        // the next user.
346
46.6k
        if (ExitInstruction == Cur)
347
3
          continue;
348
46.6k
349
46.6k
        // Exit if you find multiple values used outside or if the header phi
350
46.6k
        // node is being used. In this case the user uses the value of the
351
46.6k
        // previous iteration, in which case we would loose "VF-1" iterations of
352
46.6k
        // the reduction operation if we vectorize.
353
46.6k
        if (ExitInstruction != nullptr || 
Cur == Phi46.6k
)
354
36.0k
          return false;
355
10.6k
356
10.6k
        // The instruction used by an outside user must be the last instruction
357
10.6k
        // before we feed back to the reduction phi. Otherwise, we loose VF-1
358
10.6k
        // operations on the value.
359
10.6k
        if (!is_contained(Phi->operands(), Cur))
360
76
          return false;
361
10.5k
362
10.5k
        ExitInstruction = Cur;
363
10.5k
        continue;
364
10.5k
      }
365
1.41M
366
1.41M
      // Process instructions only once (termination). Each reduction cycle
367
1.41M
      // value must only be used once, except by phi nodes and min/max
368
1.41M
      // reductions which are represented as a cmp followed by a select.
369
1.41M
      InstDesc IgnoredVal(false, nullptr);
370
1.41M
      if (VisitedInsts.insert(UI).second) {
371
1.37M
        if (isa<PHINode>(UI))
372
6.87k
          PHIs.push_back(UI);
373
1.37M
        else
374
1.37M
          NonPHIs.push_back(UI);
375
1.37M
      } else 
if (36.8k
!isa<PHINode>(UI)36.8k
&&
376
36.8k
                 
(531
(531
!isa<FCmpInst>(UI)531
&&
!isa<ICmpInst>(UI)531
&&
377
531
                   !isa<SelectInst>(UI)) ||
378
531
                  
(346
!isConditionalRdxPattern(Kind, UI).isRecurrence()346
&&
379
346
                   
!isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence()336
)))
380
227
        return false;
381
1.41M
382
1.41M
      // Remember that we completed the cycle.
383
1.41M
      if (UI == Phi)
384
32.2k
        FoundStartPHI = true;
385
1.41M
    }
386
633k
    Worklist.append(PHIs.begin(), PHIs.end());
387
597k
    Worklist.append(NonPHIs.begin(), NonPHIs.end());
388
597k
  }
389
593k
390
593k
  // This means we have seen one but not the other instruction of the
391
593k
  // pattern or more than just a select and cmp.
392
593k
  
if (8.25k
(8.25k
Kind == RK_IntegerMinMax8.25k
||
Kind == RK_FloatMinMax8.07k
) &&
393
8.25k
      
NumCmpSelectPatternInst != 2196
)
394
9
    return false;
395
8.24k
396
8.24k
  if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
397
4
    return false;
398
8.23k
399
8.23k
  if (Start != Phi) {
400
9
    // If the starting value is not the same as the phi node, we speculatively
401
9
    // looked through an 'and' instruction when evaluating a potential
402
9
    // arithmetic reduction to determine if it may have been type-promoted.
403
9
    //
404
9
    // We now compute the minimal bit width that is required to represent the
405
9
    // reduction. If this is the same width that was indicated by the 'and', we
406
9
    // can represent the reduction in the smaller type. The 'and' instruction
407
9
    // will be eliminated since it will essentially be a cast instruction that
408
9
    // can be ignore in the cost model. If we compute a different type than we
409
9
    // did when evaluating the 'and', the 'and' will not be eliminated, and we
410
9
    // will end up with different kinds of operations in the recurrence
411
9
    // expression (e.g., RK_IntegerAND, RK_IntegerADD). We give up if this is
412
9
    // the case.
413
9
    //
414
9
    // The vectorizer relies on InstCombine to perform the actual
415
9
    // type-shrinking. It does this by inserting instructions to truncate the
416
9
    // exit value of the reduction to the width indicated by RecurrenceType and
417
9
    // then extend this value back to the original width. If IsSigned is false,
418
9
    // a 'zext' instruction will be generated; otherwise, a 'sext' will be
419
9
    // used.
420
9
    //
421
9
    // TODO: We should not rely on InstCombine to rewrite the reduction in the
422
9
    //       smaller type. We should just generate a correctly typed expression
423
9
    //       to begin with.
424
9
    Type *ComputedType;
425
9
    std::tie(ComputedType, IsSigned) =
426
9
        computeRecurrenceType(ExitInstruction, DB, AC, DT);
427
9
    if (ComputedType != RecurrenceType)
428
3
      return false;
429
6
430
6
    // The recurrence expression will be represented in a narrower type. If
431
6
    // there are any cast instructions that will be unnecessary, collect them
432
6
    // in CastInsts. Note that the 'and' instruction was already included in
433
6
    // this list.
434
6
    //
435
6
    // TODO: A better way to represent this may be to tag in some way all the
436
6
    //       instructions that are a part of the reduction. The vectorizer cost
437
6
    //       model could then apply the recurrence type to these instructions,
438
6
    //       without needing a white list of instructions to ignore.
439
6
    collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts);
440
6
  }
441
8.23k
442
8.23k
  // We found a reduction var if we have reached the original phi node and we
443
8.23k
  // only have a single instruction with out-of-loop users.
444
8.23k
445
8.23k
  // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
446
8.23k
  // is saved as part of the RecurrenceDescriptor.
447
8.23k
448
8.23k
  // Save the description of this reduction variable.
449
8.23k
  RecurrenceDescriptor RD(
450
8.23k
      RdxStart, ExitInstruction, Kind, FMF, ReduxDesc.getMinMaxKind(),
451
8.23k
      ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
452
8.23k
  RedDes = RD;
453
8.23k
454
8.23k
  return true;
455
8.23k
}
456
457
/// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
458
/// pattern corresponding to a min(X, Y) or max(X, Y).
459
RecurrenceDescriptor::InstDesc
460
3.67k
RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
461
3.67k
462
3.67k
  assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
463
3.67k
         "Expect a select instruction");
464
3.67k
  Instruction *Cmp = nullptr;
465
3.67k
  SelectInst *Select = nullptr;
466
3.67k
467
3.67k
  // We must handle the select(cmp()) as a single instruction. Advance to the
468
3.67k
  // select.
469
3.67k
  if ((Cmp = dyn_cast<ICmpInst>(I)) || 
(Cmp = dyn_cast<FCmpInst>(I))2.84k
) {
470
853
    if (!Cmp->hasOneUse() || 
!(Select = dyn_cast<SelectInst>(*I->user_begin()))826
)
471
540
      return InstDesc(false, I);
472
313
    return InstDesc(Select, Prev.getMinMaxKind());
473
313
  }
474
2.82k
475
2.82k
  // Only handle single use cases for now.
476
2.82k
  if (!(Select = dyn_cast<SelectInst>(I)))
477
0
    return InstDesc(false, I);
478
2.82k
  if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
479
2.82k
      
!(Cmp = dyn_cast<FCmpInst>(I->getOperand(0)))106
)
480
12
    return InstDesc(false, I);
481
2.81k
  if (!Cmp->hasOneUse())
482
231
    return InstDesc(false, I);
483
2.58k
484
2.58k
  Value *CmpLeft;
485
2.58k
  Value *CmpRight;
486
2.58k
487
2.58k
  // Look for a min/max pattern.
488
2.58k
  if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
489
451
    return InstDesc(Select, MRK_UIntMin);
490
2.13k
  else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
491
98
    return InstDesc(Select, MRK_UIntMax);
492
2.03k
  else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
493
219
    return InstDesc(Select, MRK_SIntMax);
494
1.81k
  else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
495
146
    return InstDesc(Select, MRK_SIntMin);
496
1.66k
  else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
497
12
    return InstDesc(Select, MRK_FloatMin);
498
1.65k
  else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
499
8
    return InstDesc(Select, MRK_FloatMax);
500
1.64k
  else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
501
8
    return InstDesc(Select, MRK_FloatMin);
502
1.64k
  else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
503
8
    return InstDesc(Select, MRK_FloatMax);
504
1.63k
505
1.63k
  return InstDesc(false, I);
506
1.63k
}
507
508
/// Returns true if the select instruction has users in the compare-and-add
509
/// reduction pattern below. The select instruction argument is the last one
510
/// in the sequence.
511
///
512
/// %sum.1 = phi ...
513
/// ...
514
/// %cmp = fcmp pred %0, %CFP
515
/// %add = fadd %0, %sum.1
516
/// %sum.2 = select %cmp, %add, %sum.1
517
RecurrenceDescriptor::InstDesc
518
RecurrenceDescriptor::isConditionalRdxPattern(
519
460
    RecurrenceKind Kind, Instruction *I) {
520
460
  SelectInst *SI = dyn_cast<SelectInst>(I);
521
460
  if (!SI)
522
0
    return InstDesc(false, I);
523
460
524
460
  CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
525
460
  // Only handle single use cases for now.
526
460
  if (!CI || 
!CI->hasOneUse()458
)
527
29
    return InstDesc(false, I);
528
431
529
431
  Value *TrueVal = SI->getTrueValue();
530
431
  Value *FalseVal = SI->getFalseValue();
531
431
  // Handle only when either of operands of select instruction is a PHI
532
431
  // node for now.
533
431
  if ((isa<PHINode>(*TrueVal) && 
isa<PHINode>(*FalseVal)128
) ||
534
431
      
(386
!isa<PHINode>(*TrueVal)386
&&
!isa<PHINode>(*FalseVal)303
))
535
65
    return InstDesc(false, I);
536
366
537
366
  Instruction *I1 =
538
366
      isa<PHINode>(*TrueVal) ? 
dyn_cast<Instruction>(FalseVal)83
539
366
                             : 
dyn_cast<Instruction>(TrueVal)283
;
540
366
  if (!I1 || 
!I1->isBinaryOp()355
)
541
242
    return InstDesc(false, I);
542
124
543
124
  Value *Op1, *Op2;
544
124
  if ((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1)  ||
545
124
       
m_FSub(m_Value(Op1), m_Value(Op2)).match(I1)95
) &&
546
124
      
I1->isFast()35
)
547
16
    return InstDesc(Kind == RK_FloatAdd, SI);
548
108
549
108
  if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && 
(I1->isFast())41
)
550
4
    return InstDesc(Kind == RK_FloatMult, SI);
551
104
552
104
  return InstDesc(false, I);
553
104
}
554
555
RecurrenceDescriptor::InstDesc
556
RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
557
408k
                                        InstDesc &Prev, bool HasFunNoNaNAttr) {
558
408k
  Instruction *UAI = Prev.getUnsafeAlgebraInst();
559
408k
  if (!UAI && 
isa<FPMathOperator>(I)406k
&&
!I->hasAllowReassoc()14.2k
)
560
14.0k
    UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
561
408k
562
408k
  switch (I->getOpcode()) {
563
408k
  default:
564
188k
    return InstDesc(false, I);
565
408k
  case Instruction::PHI:
566
1.80k
    return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
567
408k
  case Instruction::Sub:
568
147k
  case Instruction::Add:
569
147k
    return InstDesc(Kind == RK_IntegerAdd, I);
570
147k
  case Instruction::Mul:
571
10.1k
    return InstDesc(Kind == RK_IntegerMult, I);
572
147k
  case Instruction::And:
573
9.32k
    return InstDesc(Kind == RK_IntegerAnd, I);
574
147k
  case Instruction::Or:
575
9.34k
    return InstDesc(Kind == RK_IntegerOr, I);
576
147k
  case Instruction::Xor:
577
912
    return InstDesc(Kind == RK_IntegerXor, I);
578
147k
  case Instruction::FMul:
579
4.52k
    return InstDesc(Kind == RK_FloatMult, I, UAI);
580
147k
  case Instruction::FSub:
581
4.66k
  case Instruction::FAdd:
582
4.66k
    return InstDesc(Kind == RK_FloatAdd, I, UAI);
583
13.9k
  case Instruction::Select:
584
13.9k
    if (Kind == RK_FloatAdd || 
Kind == RK_FloatMult13.9k
)
585
114
      return isConditionalRdxPattern(Kind, I);
586
13.8k
    LLVM_FALLTHROUGH;
587
32.2k
  case Instruction::FCmp:
588
32.2k
  case Instruction::ICmp:
589
32.2k
    if (Kind != RK_IntegerMinMax &&
590
32.2k
        
(28.9k
!HasFunNoNaNAttr28.9k
||
Kind != RK_FloatMinMax83
))
591
28.8k
      return InstDesc(false, I);
592
3.34k
    return isMinMaxSelectCmpPattern(I, Prev);
593
408k
  }
594
408k
}
595
596
bool RecurrenceDescriptor::hasMultipleUsesOf(
597
    Instruction *I, SmallPtrSetImpl<Instruction *> &Insts,
598
39.1k
    unsigned MaxNumUses) {
599
39.1k
  unsigned NumUses = 0;
600
117k
  for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
601
78.3k
       
++Use78.3k
) {
602
78.3k
    if (Insts.count(dyn_cast<Instruction>(*Use)))
603
39.2k
      ++NumUses;
604
78.3k
    if (NumUses > MaxNumUses)
605
24
      return true;
606
78.3k
  }
607
39.1k
608
39.1k
  
return false39.1k
;
609
39.1k
}
610
bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
611
                                          RecurrenceDescriptor &RedDes,
612
                                          DemandedBits *DB, AssumptionCache *AC,
613
106k
                                          DominatorTree *DT) {
614
106k
615
106k
  BasicBlock *Header = TheLoop->getHeader();
616
106k
  Function &F = *Header->getParent();
617
106k
  bool HasFunNoNaNAttr =
618
106k
      F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
619
106k
620
106k
  if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
621
106k
                      AC, DT)) {
622
5.95k
    LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
623
5.95k
    return true;
624
5.95k
  }
625
100k
  if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
626
100k
                      AC, DT)) {
627
42
    LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
628
42
    return true;
629
42
  }
630
100k
  if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes, DB,
631
100k
                      AC, DT)) {
632
155
    LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
633
155
    return true;
634
155
  }
635
100k
  if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
636
100k
                      AC, DT)) {
637
39
    LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
638
39
    return true;
639
39
  }
640
100k
  if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes, DB,
641
100k
                      AC, DT)) {
642
23
    LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
643
23
    return true;
644
23
  }
645
100k
  if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, RedDes,
646
100k
                      DB, AC, DT)) {
647
169
    LLVM_DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
648
169
    return true;
649
169
  }
650
100k
  if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
651
100k
                      AC, DT)) {
652
30
    LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
653
30
    return true;
654
30
  }
655
100k
  if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
656
100k
                      AC, DT)) {
657
1.80k
    LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
658
1.80k
    return true;
659
1.80k
  }
660
98.6k
  if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes, DB,
661
98.6k
                      AC, DT)) {
662
18
    LLVM_DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi
663
18
                      << "\n");
664
18
    return true;
665
18
  }
666
98.6k
  // Not a reduction of known type.
667
98.6k
  return false;
668
98.6k
}
669
670
bool RecurrenceDescriptor::isFirstOrderRecurrence(
671
    PHINode *Phi, Loop *TheLoop,
672
32.9k
    DenseMap<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) {
673
32.9k
674
32.9k
  // Ensure the phi node is in the loop header and has two incoming values.
675
32.9k
  if (Phi->getParent() != TheLoop->getHeader() ||
676
32.9k
      Phi->getNumIncomingValues() != 2)
677
0
    return false;
678
32.9k
679
32.9k
  // Ensure the loop has a preheader and a single latch block. The loop
680
32.9k
  // vectorizer will need the latch to set up the next iteration of the loop.
681
32.9k
  auto *Preheader = TheLoop->getLoopPreheader();
682
32.9k
  auto *Latch = TheLoop->getLoopLatch();
683
32.9k
  if (!Preheader || !Latch)
684
0
    return false;
685
32.9k
686
32.9k
  // Ensure the phi node's incoming blocks are the loop preheader and latch.
687
32.9k
  if (Phi->getBasicBlockIndex(Preheader) < 0 ||
688
32.9k
      Phi->getBasicBlockIndex(Latch) < 0)
689
0
    return false;
690
32.9k
691
32.9k
  // Get the previous value. The previous value comes from the latch edge while
692
32.9k
  // the initial value comes form the preheader edge.
693
32.9k
  auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
694
32.9k
  if (!Previous || 
!TheLoop->contains(Previous)32.8k
||
isa<PHINode>(Previous)32.8k
||
695
32.9k
      
SinkAfter.count(Previous)31.9k
) // Cannot rely on dominance due to motion.
696
1.00k
    return false;
697
31.9k
698
31.9k
  // Ensure every user of the phi node is dominated by the previous value.
699
31.9k
  // The dominance requirement ensures the loop vectorizer will not need to
700
31.9k
  // vectorize the initial value prior to the first iteration of the loop.
701
31.9k
  // TODO: Consider extending this sinking to handle other kinds of instructions
702
31.9k
  // and expressions, beyond sinking a single cast past Previous.
703
31.9k
  if (Phi->hasOneUse()) {
704
19.3k
    auto *I = Phi->user_back();
705
19.3k
    if (I->isCast() && 
(I->getParent() == Phi->getParent())778
&&
I->hasOneUse()776
&&
706
19.3k
        
DT->dominates(Previous, I->user_back())702
) {
707
43
      if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking.
708
22
        SinkAfter[I] = Previous;
709
43
      return true;
710
43
    }
711
31.8k
  }
712
31.8k
713
31.8k
  for (User *U : Phi->users())
714
42.1k
    if (auto *I = dyn_cast<Instruction>(U)) {
715
42.1k
      if (!DT->dominates(Previous, I))
716
31.6k
        return false;
717
42.1k
    }
718
31.8k
719
31.8k
  
return true234
;
720
31.8k
}
721
722
/// This function returns the identity element (or neutral element) for
723
/// the operation K.
724
Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
725
1.25k
                                                      Type *Tp) {
726
1.25k
  switch (K) {
727
1.25k
  case RK_IntegerXor:
728
1.14k
  case RK_IntegerAdd:
729
1.14k
  case RK_IntegerOr:
730
1.14k
    // Adding, Xoring, Oring zero to a number does not change it.
731
1.14k
    return ConstantInt::get(Tp, 0);
732
1.14k
  case RK_IntegerMult:
733
40
    // Multiplying a number by 1 does not change it.
734
40
    return ConstantInt::get(Tp, 1);
735
1.14k
  case RK_IntegerAnd:
736
31
    // AND-ing a number with an all-1 value does not change it.
737
31
    return ConstantInt::get(Tp, -1, true);
738
1.14k
  case RK_FloatMult:
739
3
    // Multiplying a number by 1 does not change it.
740
3
    return ConstantFP::get(Tp, 1.0L);
741
1.14k
  case RK_FloatAdd:
742
34
    // Adding zero to a number does not change it.
743
34
    return ConstantFP::get(Tp, 0.0L);
744
1.14k
  default:
745
0
    llvm_unreachable("Unknown recurrence kind");
746
1.25k
  }
747
1.25k
}
748
749
/// This function translates the recurrence kind to an LLVM binary operator.
750
1.36k
unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
751
1.36k
  switch (Kind) {
752
1.36k
  case RK_IntegerAdd:
753
1.03k
    return Instruction::Add;
754
1.36k
  case RK_IntegerMult:
755
40
    return Instruction::Mul;
756
1.36k
  case RK_IntegerOr:
757
94
    return Instruction::Or;
758
1.36k
  case RK_IntegerAnd:
759
31
    return Instruction::And;
760
1.36k
  case RK_IntegerXor:
761
15
    return Instruction::Xor;
762
1.36k
  case RK_FloatMult:
763
3
    return Instruction::FMul;
764
1.36k
  case RK_FloatAdd:
765
34
    return Instruction::FAdd;
766
1.36k
  case RK_IntegerMinMax:
767
89
    return Instruction::ICmp;
768
1.36k
  case RK_FloatMinMax:
769
18
    return Instruction::FCmp;
770
1.36k
  default:
771
0
    llvm_unreachable("Unknown recurrence operation");
772
1.36k
  }
773
1.36k
}
774
775
InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
776
                                         const SCEV *Step, BinaryOperator *BOp,
777
                                         SmallVectorImpl<Instruction *> *Casts)
778
65.8k
    : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
779
65.8k
  assert(IK != IK_NoInduction && "Not an induction");
780
65.8k
781
65.8k
  // Start value type should match the induction kind and the value
782
65.8k
  // itself should not be null.
783
65.8k
  assert(StartValue && "StartValue is null");
784
65.8k
  assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
785
65.8k
         "StartValue is not a pointer for pointer induction");
786
65.8k
  assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
787
65.8k
         "StartValue is not an integer for integer induction");
788
65.8k
789
65.8k
  // Check the Step Value. It should be non-zero integer value.
790
65.8k
  assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
791
65.8k
         "Step value is zero");
792
65.8k
793
65.8k
  assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
794
65.8k
         "Step value should be constant for pointer induction");
795
65.8k
  assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
796
65.8k
         "StepValue is not an integer");
797
65.8k
798
65.8k
  assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
799
65.8k
         "StepValue is not FP for FpInduction");
800
65.8k
  assert((IK != IK_FpInduction ||
801
65.8k
          (InductionBinOp &&
802
65.8k
           (InductionBinOp->getOpcode() == Instruction::FAdd ||
803
65.8k
            InductionBinOp->getOpcode() == Instruction::FSub))) &&
804
65.8k
         "Binary opcode should be specified for FP induction");
805
65.8k
806
65.8k
  if (Casts) {
807
23
    for (auto &Inst : *Casts) {
808
23
      RedundantCasts.push_back(Inst);
809
23
    }
810
15
  }
811
65.8k
}
812
813
0
int InductionDescriptor::getConsecutiveDirection() const {
814
0
  ConstantInt *ConstStep = getConstIntStepValue();
815
0
  if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
816
0
    return ConstStep->getSExtValue();
817
0
  return 0;
818
0
}
819
820
120k
ConstantInt *InductionDescriptor::getConstIntStepValue() const {
821
120k
  if (isa<SCEVConstant>(Step))
822
119k
    return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
823
834
  return nullptr;
824
834
}
825
826
bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
827
                                           ScalarEvolution *SE,
828
6.59k
                                           InductionDescriptor &D) {
829
6.59k
830
6.59k
  // Here we only handle FP induction variables.
831
6.59k
  assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
832
6.59k
833
6.59k
  if (TheLoop->getHeader() != Phi->getParent())
834
0
    return false;
835
6.59k
836
6.59k
  // The loop may have multiple entrances or multiple exits; we can analyze
837
6.59k
  // this phi if it has a unique entry value and a unique backedge value.
838
6.59k
  if (Phi->getNumIncomingValues() != 2)
839
0
    return false;
840
6.59k
  Value *BEValue = nullptr, *StartValue = nullptr;
841
6.59k
  if (TheLoop->contains(Phi->getIncomingBlock(0))) {
842
5.91k
    BEValue = Phi->getIncomingValue(0);
843
5.91k
    StartValue = Phi->getIncomingValue(1);
844
5.91k
  } else {
845
680
    assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
846
680
           "Unexpected Phi node in the loop");
847
680
    BEValue = Phi->getIncomingValue(1);
848
680
    StartValue = Phi->getIncomingValue(0);
849
680
  }
850
6.59k
851
6.59k
  BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
852
6.59k
  if (!BOp)
853
454
    return false;
854
6.14k
855
6.14k
  Value *Addend = nullptr;
856
6.14k
  if (BOp->getOpcode() == Instruction::FAdd) {
857
405
    if (BOp->getOperand(0) == Phi)
858
264
      Addend = BOp->getOperand(1);
859
141
    else if (BOp->getOperand(1) == Phi)
860
55
      Addend = BOp->getOperand(0);
861
5.73k
  } else if (BOp->getOpcode() == Instruction::FSub)
862
63
    if (BOp->getOperand(0) == Phi)
863
24
      Addend = BOp->getOperand(1);
864
6.14k
865
6.14k
  if (!Addend)
866
5.79k
    return false;
867
343
868
343
  // The addend should be loop invariant
869
343
  if (auto *I = dyn_cast<Instruction>(Addend))
870
287
    if (TheLoop->contains(I))
871
272
      return false;
872
71
873
71
  // FP Step has unknown SCEV
874
71
  const SCEV *Step = SE->getUnknown(Addend);
875
71
  D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
876
71
  return true;
877
71
}
878
879
/// This function is called when we suspect that the update-chain of a phi node
880
/// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
881
/// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
882
/// predicate P under which the SCEV expression for the phi can be the
883
/// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
884
/// cast instructions that are involved in the update-chain of this induction.
885
/// A caller that adds the required runtime predicate can be free to drop these
886
/// cast instructions, and compute the phi using \p AR (instead of some scev
887
/// expression with casts).
888
///
889
/// For example, without a predicate the scev expression can take the following
890
/// form:
891
///      (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
892
///
893
/// It corresponds to the following IR sequence:
894
/// %for.body:
895
///   %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
896
///   %casted_phi = "ExtTrunc i64 %x"
897
///   %add = add i64 %casted_phi, %step
898
///
899
/// where %x is given in \p PN,
900
/// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
901
/// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
902
/// several forms, for example, such as:
903
///   ExtTrunc1:    %casted_phi = and  %x, 2^n-1
904
/// or:
905
///   ExtTrunc2:    %t = shl %x, m
906
///                 %casted_phi = ashr %t, m
907
///
908
/// If we are able to find such sequence, we return the instructions
909
/// we found, namely %casted_phi and the instructions on its use-def chain up
910
/// to the phi (not including the phi).
911
static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE,
912
                                    const SCEVUnknown *PhiScev,
913
                                    const SCEVAddRecExpr *AR,
914
15
                                    SmallVectorImpl<Instruction *> &CastInsts) {
915
15
916
15
  assert(CastInsts.empty() && "CastInsts is expected to be empty.");
917
15
  auto *PN = cast<PHINode>(PhiScev->getValue());
918
15
  assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
919
15
  const Loop *L = AR->getLoop();
920
15
921
15
  // Find any cast instructions that participate in the def-use chain of
922
15
  // PhiScev in the loop.
923
15
  // FORNOW/TODO: We currently expect the def-use chain to include only
924
15
  // two-operand instructions, where one of the operands is an invariant.
925
15
  // createAddRecFromPHIWithCasts() currently does not support anything more
926
15
  // involved than that, so we keep the search simple. This can be
927
15
  // extended/generalized as needed.
928
15
929
38
  auto getDef = [&](const Value *Val) -> Value * {
930
38
    const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
931
38
    if (!BinOp)
932
0
      return nullptr;
933
38
    Value *Op0 = BinOp->getOperand(0);
934
38
    Value *Op1 = BinOp->getOperand(1);
935
38
    Value *Def = nullptr;
936
38
    if (L->isLoopInvariant(Op0))
937
0
      Def = Op1;
938
38
    else if (L->isLoopInvariant(Op1))
939
38
      Def = Op0;
940
38
    return Def;
941
38
  };
942
15
943
15
  // Look for the instruction that defines the induction via the
944
15
  // loop backedge.
945
15
  BasicBlock *Latch = L->getLoopLatch();
946
15
  if (!Latch)
947
0
    return false;
948
15
  Value *Val = PN->getIncomingValueForBlock(Latch);
949
15
  if (!Val)
950
0
    return false;
951
15
952
15
  // Follow the def-use chain until the induction phi is reached.
953
15
  // If on the way we encounter a Value that has the same SCEV Expr as the
954
15
  // phi node, we can consider the instructions we visit from that point
955
15
  // as part of the cast-sequence that can be ignored.
956
15
  bool InCastSequence = false;
957
15
  auto *Inst = dyn_cast<Instruction>(Val);
958
53
  while (Val != PN) {
959
38
    // If we encountered a phi node other than PN, or if we left the loop,
960
38
    // we bail out.
961
38
    if (!Inst || !L->contains(Inst)) {
962
0
      return false;
963
0
    }
964
38
    auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
965
38
    if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
966
15
      InCastSequence = true;
967
38
    if (InCastSequence) {
968
23
      // Only the last instruction in the cast sequence is expected to have
969
23
      // uses outside the induction def-use chain.
970
23
      if (!CastInsts.empty())
971
8
        if (!Inst->hasOneUse())
972
0
          return false;
973
23
      CastInsts.push_back(Inst);
974
23
    }
975
38
    Val = getDef(Val);
976
38
    if (!Val)
977
0
      return false;
978
38
    Inst = dyn_cast<Instruction>(Val);
979
38
  }
980
15
981
15
  return InCastSequence;
982
15
}
983
984
bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
985
                                         PredicatedScalarEvolution &PSE,
986
131k
                                         InductionDescriptor &D, bool Assume) {
987
131k
  Type *PhiTy = Phi->getType();
988
131k
989
131k
  // Handle integer and pointer inductions variables.
990
131k
  // Now we handle also FP induction but not trying to make a
991
131k
  // recurrent expression from the PHI node in-place.
992
131k
993
131k
  if (!PhiTy->isIntegerTy() && 
!PhiTy->isPointerTy()51.0k
&&
!PhiTy->isFloatTy()6.60k
&&
994
131k
      
!PhiTy->isDoubleTy()6.20k
&&
!PhiTy->isHalfTy()12
)
995
12
    return false;
996
131k
997
131k
  if (PhiTy->isFloatingPointTy())
998
6.59k
    return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
999
124k
1000
124k
  const SCEV *PhiScev = PSE.getSCEV(Phi);
1001
124k
  const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1002
124k
1003
124k
  // We need this expression to be an AddRecExpr.
1004
124k
  if (Assume && 
!AR29.3k
)
1005
29.1k
    AR = PSE.getAsAddRec(Phi);
1006
124k
1007
124k
  if (!AR) {
1008
58.4k
    LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1009
58.4k
    return false;
1010
58.4k
  }
1011
66.2k
1012
66.2k
  // Record any Cast instructions that participate in the induction update
1013
66.2k
  const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1014
66.2k
  // If we started from an UnknownSCEV, and managed to build an addRecurrence
1015
66.2k
  // only after enabling Assume with PSCEV, this means we may have encountered
1016
66.2k
  // cast instructions that required adding a runtime check in order to
1017
66.2k
  // guarantee the correctness of the AddRecurrence respresentation of the
1018
66.2k
  // induction.
1019
66.2k
  if (PhiScev != AR && 
SymbolicPhi96
) {
1020
15
    SmallVector<Instruction *, 2> Casts;
1021
15
    if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
1022
15
      return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
1023
66.2k
  }
1024
66.2k
1025
66.2k
  return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1026
66.2k
}
1027
1028
bool InductionDescriptor::isInductionPHI(
1029
    PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1030
    InductionDescriptor &D, const SCEV *Expr,
1031
66.3k
    SmallVectorImpl<Instruction *> *CastsToIgnore) {
1032
66.3k
  Type *PhiTy = Phi->getType();
1033
66.3k
  // We only handle integer and pointer inductions variables.
1034
66.3k
  if (!PhiTy->isIntegerTy() && 
!PhiTy->isPointerTy()12.1k
)
1035
1
    return false;
1036
66.3k
1037
66.3k
  // Check that the PHI is consecutive.
1038
66.3k
  const SCEV *PhiScev = Expr ? 
Expr66.2k
:
SE->getSCEV(Phi)107
;
1039
66.3k
  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1040
66.3k
1041
66.3k
  if (!AR) {
1042
8
    LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1043
8
    return false;
1044
8
  }
1045
66.3k
1046
66.3k
  if (AR->getLoop() != TheLoop) {
1047
0
    // FIXME: We should treat this as a uniform. Unfortunately, we
1048
0
    // don't currently know how to handled uniform PHIs.
1049
0
    LLVM_DEBUG(
1050
0
        dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
1051
0
    return false;
1052
0
  }
1053
66.3k
1054
66.3k
  Value *StartValue =
1055
66.3k
      Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
1056
66.3k
1057
66.3k
  BasicBlock *Latch = AR->getLoop()->getLoopLatch();
1058
66.3k
  if (!Latch)
1059
0
    return false;
1060
66.3k
  BinaryOperator *BOp =
1061
66.3k
      dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
1062
66.3k
1063
66.3k
  const SCEV *Step = AR->getStepRecurrence(*SE);
1064
66.3k
  // Calculate the pointer stride and check if it is consecutive.
1065
66.3k
  // The stride may be a constant or a loop invariant integer value.
1066
66.3k
  const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1067
66.3k
  if (!ConstStep && 
!SE->isLoopInvariant(Step, TheLoop)928
)
1068
9
    return false;
1069
66.3k
1070
66.3k
  if (PhiTy->isIntegerTy()) {
1071
54.1k
    D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
1072
54.1k
                            CastsToIgnore);
1073
54.1k
    return true;
1074
54.1k
  }
1075
12.1k
1076
12.1k
  assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1077
12.1k
  // Pointer induction should be a constant.
1078
12.1k
  if (!ConstStep)
1079
484
    return false;
1080
11.6k
1081
11.6k
  ConstantInt *CV = ConstStep->getValue();
1082
11.6k
  Type *PointerElementType = PhiTy->getPointerElementType();
1083
11.6k
  // The pointer stride cannot be determined if the pointer element type is not
1084
11.6k
  // sized.
1085
11.6k
  if (!PointerElementType->isSized())
1086
2
    return false;
1087
11.6k
1088
11.6k
  const DataLayout &DL = Phi->getModule()->getDataLayout();
1089
11.6k
  int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
1090
11.6k
  if (!Size)
1091
2
    return false;
1092
11.6k
1093
11.6k
  int64_t CVSize = CV->getSExtValue();
1094
11.6k
  if (CVSize % Size)
1095
0
    return false;
1096
11.6k
  auto *StepValue =
1097
11.6k
      SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
1098
11.6k
  D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue, BOp);
1099
11.6k
  return true;
1100
11.6k
}