Coverage Report

Created: 2018-06-24 14:39

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/Support/SCEVValidator.cpp
Line
Count
Source (jump to first uncovered line)
1
2
#include "polly/Support/SCEVValidator.h"
3
#include "polly/ScopInfo.h"
4
#include "llvm/Analysis/RegionInfo.h"
5
#include "llvm/Analysis/ScalarEvolution.h"
6
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
7
#include "llvm/Support/Debug.h"
8
9
using namespace llvm;
10
using namespace polly;
11
12
#define DEBUG_TYPE "polly-scev-validator"
13
14
namespace SCEVType {
15
/// The type of a SCEV
16
///
17
/// To check for the validity of a SCEV we assign to each SCEV a type. The
18
/// possible types are INT, PARAM, IV and INVALID. The order of the types is
19
/// important. The subexpressions of SCEV with a type X can only have a type
20
/// that is smaller or equal than X.
21
enum TYPE {
22
  // An integer value.
23
  INT,
24
25
  // An expression that is constant during the execution of the Scop,
26
  // but that may depend on parameters unknown at compile time.
27
  PARAM,
28
29
  // An expression that may change during the execution of the SCoP.
30
  IV,
31
32
  // An invalid expression.
33
  INVALID
34
};
35
} // namespace SCEVType
36
37
/// The result the validator returns for a SCEV expression.
38
class ValidatorResult {
39
  /// The type of the expression
40
  SCEVType::TYPE Type;
41
42
  /// The set of Parameters in the expression.
43
  ParameterSetTy Parameters;
44
45
public:
46
  /// The copy constructor
47
7.22k
  ValidatorResult(const ValidatorResult &Source) {
48
7.22k
    Type = Source.Type;
49
7.22k
    Parameters = Source.Parameters;
50
7.22k
  }
51
52
  /// Construct a result with a certain type and no parameters.
53
122k
  ValidatorResult(SCEVType::TYPE Type) : Type(Type) {
54
122k
    assert(Type != SCEVType::PARAM && "Did you forget to pass the parameter");
55
122k
  }
56
57
  /// Construct a result with a certain type and a single parameter.
58
17.8k
  ValidatorResult(SCEVType::TYPE Type, const SCEV *Expr) : Type(Type) {
59
17.8k
    Parameters.insert(Expr);
60
17.8k
  }
61
62
  /// Get the type of the ValidatorResult.
63
1.07k
  SCEVType::TYPE getType() { return Type; }
64
65
  /// Is the analyzed SCEV constant during the execution of the SCoP.
66
166
  bool isConstant() { return Type == SCEVType::INT || 
Type == SCEVType::PARAM110
; }
67
68
  /// Is the analyzed SCEV valid.
69
117k
  bool isValid() { return Type != SCEVType::INVALID; }
70
71
  /// Is the analyzed SCEV of Type IV.
72
4.45k
  bool isIV() { return Type == SCEVType::IV; }
73
74
  /// Is the analyzed SCEV of Type INT.
75
42.2k
  bool isINT() { return Type == SCEVType::INT; }
76
77
  /// Is the analyzed SCEV of Type PARAM.
78
15.0k
  bool isPARAM() { return Type == SCEVType::PARAM; }
79
80
  /// Get the parameters of this validator result.
81
12.4k
  const ParameterSetTy &getParameters() { return Parameters; }
82
83
  /// Add the parameters of Source to this result.
84
41.8k
  void addParamsFrom(const ValidatorResult &Source) {
85
41.8k
    Parameters.insert(Source.Parameters.begin(), Source.Parameters.end());
86
41.8k
  }
87
88
  /// Merge a result.
89
  ///
90
  /// This means to merge the parameters and to set the Type to the most
91
  /// specific Type that matches both.
92
14.2k
  void merge(const ValidatorResult &ToMerge) {
93
14.2k
    Type = std::max(Type, ToMerge.Type);
94
14.2k
    addParamsFrom(ToMerge);
95
14.2k
  }
96
97
  void print(raw_ostream &OS) {
98
    switch (Type) {
99
    case SCEVType::INT:
100
      OS << "SCEVType::INT";
101
      break;
102
    case SCEVType::PARAM:
103
      OS << "SCEVType::PARAM";
104
      break;
105
    case SCEVType::IV:
106
      OS << "SCEVType::IV";
107
      break;
108
    case SCEVType::INVALID:
109
      OS << "SCEVType::INVALID";
110
      break;
111
    }
112
  }
113
};
114
115
0
raw_ostream &operator<<(raw_ostream &OS, class ValidatorResult &VR) {
116
0
  VR.print(OS);
117
0
  return OS;
118
0
}
119
120
190
bool polly::isConstCall(llvm::CallInst *Call) {
121
190
  if (Call->mayReadOrWriteMemory())
122
84
    return false;
123
106
124
106
  for (auto &Operand : Call->arg_operands())
125
100
    if (!isa<ConstantInt>(&Operand))
126
42
      return false;
127
106
128
106
  
return true64
;
129
106
}
130
131
/// Check if a SCEV is valid in a SCoP.
132
struct SCEVValidator
133
    : public SCEVVisitor<SCEVValidator, class ValidatorResult> {
134
private:
135
  const Region *R;
136
  Loop *Scope;
137
  ScalarEvolution &SE;
138
  InvariantLoadsSetTy *ILS;
139
140
public:
141
  SCEVValidator(const Region *R, Loop *Scope, ScalarEvolution &SE,
142
                InvariantLoadsSetTy *ILS)
143
60.3k
      : R(R), Scope(Scope), SE(SE), ILS(ILS) {}
144
145
84.5k
  class ValidatorResult visitConstant(const SCEVConstant *Constant) {
146
84.5k
    return ValidatorResult(SCEVType::INT);
147
84.5k
  }
148
149
  class ValidatorResult visitZeroExtendOrTruncateExpr(const SCEV *Expr,
150
1.07k
                                                      const SCEV *Operand) {
151
1.07k
    ValidatorResult Op = visit(Operand);
152
1.07k
    auto Type = Op.getType();
153
1.07k
154
1.07k
    // If unsigned operations are allowed return the operand, otherwise
155
1.07k
    // check if we can model the expression without unsigned assumptions.
156
1.07k
    if (PollyAllowUnsignedOperations || 
Type == SCEVType::INVALID0
)
157
1.07k
      return Op;
158
0
159
0
    if (Type == SCEVType::IV)
160
0
      return ValidatorResult(SCEVType::INVALID);
161
0
    return ValidatorResult(SCEVType::PARAM, Expr);
162
0
  }
163
164
283
  class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
165
283
    return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
166
283
  }
167
168
788
  class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
169
788
    return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
170
788
  }
171
172
2.68k
  class ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
173
2.68k
    return visit(Expr->getOperand());
174
2.68k
  }
175
176
3.32k
  class ValidatorResult visitAddExpr(const SCEVAddExpr *Expr) {
177
3.32k
    ValidatorResult Return(SCEVType::INT);
178
3.32k
179
10.1k
    for (int i = 0, e = Expr->getNumOperands(); i < e; 
++i6.84k
) {
180
6.91k
      ValidatorResult Op = visit(Expr->getOperand(i));
181
6.91k
      Return.merge(Op);
182
6.91k
183
6.91k
      // Early exit.
184
6.91k
      if (!Return.isValid())
185
69
        break;
186
6.91k
    }
187
3.32k
188
3.32k
    return Return;
189
3.32k
  }
190
191
4.44k
  class ValidatorResult visitMulExpr(const SCEVMulExpr *Expr) {
192
4.44k
    ValidatorResult Return(SCEVType::INT);
193
4.44k
194
4.44k
    bool HasMultipleParams = false;
195
4.44k
196
14.2k
    for (int i = 0, e = Expr->getNumOperands(); i < e; 
++i9.79k
) {
197
9.85k
      ValidatorResult Op = visit(Expr->getOperand(i));
198
9.85k
199
9.85k
      if (Op.isINT())
200
4.20k
        continue;
201
5.65k
202
5.65k
      if (Op.isPARAM() && 
Return.isPARAM()5.19k
) {
203
1.19k
        HasMultipleParams = true;
204
1.19k
        continue;
205
1.19k
      }
206
4.45k
207
4.45k
      if ((Op.isIV() || 
Op.isPARAM()4.16k
) &&
!Return.isINT()4.28k
) {
208
53
        LLVM_DEBUG(
209
53
            dbgs() << "INVALID: More than one non-int operand in MulExpr\n"
210
53
                   << "\tExpr: " << *Expr << "\n"
211
53
                   << "\tPrevious expression type: " << Return << "\n"
212
53
                   << "\tNext operand (" << Op << "): " << *Expr->getOperand(i)
213
53
                   << "\n");
214
53
215
53
        return ValidatorResult(SCEVType::INVALID);
216
53
      }
217
4.40k
218
4.40k
      Return.merge(Op);
219
4.40k
    }
220
4.44k
221
4.44k
    
if (4.39k
HasMultipleParams4.39k
&&
Return.isValid()955
)
222
955
      return ValidatorResult(SCEVType::PARAM, Expr);
223
3.44k
224
3.44k
    return Return;
225
3.44k
  }
226
227
30.0k
  class ValidatorResult visitAddRecExpr(const SCEVAddRecExpr *Expr) {
228
30.0k
    if (!Expr->isAffine()) {
229
124
      LLVM_DEBUG(dbgs() << "INVALID: AddRec is not affine");
230
124
      return ValidatorResult(SCEVType::INVALID);
231
124
    }
232
29.9k
233
29.9k
    ValidatorResult Start = visit(Expr->getStart());
234
29.9k
    ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE));
235
29.9k
236
29.9k
    if (!Start.isValid())
237
1.11k
      return Start;
238
28.8k
239
28.8k
    if (!Recurrence.isValid())
240
0
      return Recurrence;
241
28.8k
242
28.8k
    auto *L = Expr->getLoop();
243
28.8k
    if (R->contains(L) && 
(28.1k
!Scope28.1k
||
!L->contains(Scope)28.1k
)) {
244
15
      LLVM_DEBUG(
245
15
          dbgs() << "INVALID: Loop of AddRec expression boxed in an a "
246
15
                    "non-affine subregion or has a non-synthesizable exit "
247
15
                    "value.");
248
15
      return ValidatorResult(SCEVType::INVALID);
249
15
    }
250
28.8k
251
28.8k
    if (R->contains(L)) {
252
28.1k
      if (Recurrence.isINT()) {
253
27.4k
        ValidatorResult Result(SCEVType::IV);
254
27.4k
        Result.addParamsFrom(Start);
255
27.4k
        return Result;
256
27.4k
      }
257
730
258
730
      LLVM_DEBUG(dbgs() << "INVALID: AddRec within scop has non-int"
259
730
                           "recurrence part");
260
730
      return ValidatorResult(SCEVType::INVALID);
261
730
    }
262
689
263
689
    assert(Recurrence.isConstant() && "Expected 'Recurrence' to be constant");
264
689
265
689
    // Directly generate ValidatorResult for Expr if 'start' is zero.
266
689
    if (Expr->getStart()->isZero())
267
502
      return ValidatorResult(SCEVType::PARAM, Expr);
268
187
269
187
    // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}'
270
187
    // if 'start' is not zero.
271
187
    const SCEV *ZeroStartExpr = SE.getAddRecExpr(
272
187
        SE.getConstant(Expr->getStart()->getType(), 0),
273
187
        Expr->getStepRecurrence(SE), Expr->getLoop(), Expr->getNoWrapFlags());
274
187
275
187
    ValidatorResult ZeroStartResult =
276
187
        ValidatorResult(SCEVType::PARAM, ZeroStartExpr);
277
187
    ZeroStartResult.addParamsFrom(Start);
278
187
279
187
    return ZeroStartResult;
280
187
  }
281
282
1.41k
  class ValidatorResult visitSMaxExpr(const SCEVSMaxExpr *Expr) {
283
1.41k
    ValidatorResult Return(SCEVType::INT);
284
1.41k
285
4.32k
    for (int i = 0, e = Expr->getNumOperands(); i < e; 
++i2.91k
) {
286
2.91k
      ValidatorResult Op = visit(Expr->getOperand(i));
287
2.91k
288
2.91k
      if (!Op.isValid())
289
0
        return Op;
290
2.91k
291
2.91k
      Return.merge(Op);
292
2.91k
    }
293
1.41k
294
1.41k
    return Return;
295
1.41k
  }
296
297
39
  class ValidatorResult visitUMaxExpr(const SCEVUMaxExpr *Expr) {
298
39
    // We do not support unsigned max operations. If 'Expr' is constant during
299
39
    // Scop execution we treat this as a parameter, otherwise we bail out.
300
117
    for (int i = 0, e = Expr->getNumOperands(); i < e; 
++i78
) {
301
78
      ValidatorResult Op = visit(Expr->getOperand(i));
302
78
303
78
      if (!Op.isConstant()) {
304
0
        LLVM_DEBUG(dbgs() << "INVALID: UMaxExpr has a non-constant operand");
305
0
        return ValidatorResult(SCEVType::INVALID);
306
0
      }
307
78
    }
308
39
309
39
    return ValidatorResult(SCEVType::PARAM, Expr);
310
39
  }
311
312
2.40k
  ValidatorResult visitGenericInst(Instruction *I, const SCEV *S) {
313
2.40k
    if (R->contains(I)) {
314
111
      LLVM_DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
315
111
                           "within the region\n");
316
111
      return ValidatorResult(SCEVType::INVALID);
317
111
    }
318
2.29k
319
2.29k
    return ValidatorResult(SCEVType::PARAM, S);
320
2.29k
  }
321
322
78
  ValidatorResult visitCallInstruction(Instruction *I, const SCEV *S) {
323
78
    assert(I->getOpcode() == Instruction::Call && "Call instruction expected");
324
78
325
78
    if (R->contains(I)) {
326
64
      auto Call = cast<CallInst>(I);
327
64
328
64
      if (!isConstCall(Call))
329
30
        return ValidatorResult(SCEVType::INVALID, S);
330
48
    }
331
48
    return ValidatorResult(SCEVType::PARAM, S);
332
48
  }
333
334
4.98k
  ValidatorResult visitLoadInstruction(Instruction *I, const SCEV *S) {
335
4.98k
    if (R->contains(I) && 
ILS2.83k
) {
336
2.83k
      ILS->insert(cast<LoadInst>(I));
337
2.83k
      return ValidatorResult(SCEVType::PARAM, S);
338
2.83k
    }
339
2.15k
340
2.15k
    return visitGenericInst(I, S);
341
2.15k
  }
342
343
  ValidatorResult visitDivision(const SCEV *Dividend, const SCEV *Divisor,
344
                                const SCEV *DivExpr,
345
761
                                Instruction *SDiv = nullptr) {
346
761
347
761
    // First check if we might be able to model the division, thus if the
348
761
    // divisor is constant. If so, check the dividend, otherwise check if
349
761
    // the whole division can be seen as a parameter.
350
761
    if (isa<SCEVConstant>(Divisor) && 
!Divisor->isZero()712
)
351
709
      return visit(Dividend);
352
52
353
52
    // For signed divisions use the SDiv instruction to check for a parameter
354
52
    // division, for unsigned divisions check the operands.
355
52
    if (SDiv)
356
8
      return visitGenericInst(SDiv, DivExpr);
357
44
358
44
    ValidatorResult LHS = visit(Dividend);
359
44
    ValidatorResult RHS = visit(Divisor);
360
44
    if (LHS.isConstant() && RHS.isConstant())
361
44
      return ValidatorResult(SCEVType::PARAM, DivExpr);
362
0
363
0
    LLVM_DEBUG(
364
0
        dbgs() << "INVALID: unsigned division of non-constant expressions");
365
0
    return ValidatorResult(SCEVType::INVALID);
366
0
  }
367
368
410
  ValidatorResult visitUDivExpr(const SCEVUDivExpr *Expr) {
369
410
    if (!PollyAllowUnsignedOperations)
370
0
      return ValidatorResult(SCEVType::INVALID);
371
410
372
410
    auto *Dividend = Expr->getLHS();
373
410
    auto *Divisor = Expr->getRHS();
374
410
    return visitDivision(Dividend, Divisor, Expr);
375
410
  }
376
377
351
  ValidatorResult visitSDivInstruction(Instruction *SDiv, const SCEV *Expr) {
378
351
    assert(SDiv->getOpcode() == Instruction::SDiv &&
379
351
           "Assumed SDiv instruction!");
380
351
381
351
    auto *Dividend = SE.getSCEV(SDiv->getOperand(0));
382
351
    auto *Divisor = SE.getSCEV(SDiv->getOperand(1));
383
351
    return visitDivision(Dividend, Divisor, Expr, SDiv);
384
351
  }
385
386
212
  ValidatorResult visitSRemInstruction(Instruction *SRem, const SCEV *S) {
387
212
    assert(SRem->getOpcode() == Instruction::SRem &&
388
212
           "Assumed SRem instruction!");
389
212
390
212
    auto *Divisor = SRem->getOperand(1);
391
212
    auto *CI = dyn_cast<ConstantInt>(Divisor);
392
212
    if (!CI || 
CI->isZeroValue()209
)
393
3
      return visitGenericInst(SRem, S);
394
209
395
209
    auto *Dividend = SRem->getOperand(0);
396
209
    auto *DividendSCEV = SE.getSCEV(Dividend);
397
209
    return visit(DividendSCEV);
398
209
  }
399
400
16.9k
  ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
401
16.9k
    Value *V = Expr->getValue();
402
16.9k
403
16.9k
    if (!Expr->getType()->isIntegerTy() && 
!Expr->getType()->isPointerTy()230
) {
404
0
      LLVM_DEBUG(dbgs() << "INVALID: UnknownExpr is not an integer or pointer");
405
0
      return ValidatorResult(SCEVType::INVALID);
406
0
    }
407
16.9k
408
16.9k
    if (isa<UndefValue>(V)) {
409
27
      LLVM_DEBUG(dbgs() << "INVALID: UnknownExpr references an undef value");
410
27
      return ValidatorResult(SCEVType::INVALID);
411
27
    }
412
16.8k
413
16.8k
    if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) {
414
5.97k
      switch (I->getOpcode()) {
415
5.97k
      case Instruction::IntToPtr:
416
30
        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
417
5.97k
      case Instruction::PtrToInt:
418
67
        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
419
5.97k
      case Instruction::Load:
420
4.98k
        return visitLoadInstruction(I, Expr);
421
5.97k
      case Instruction::SDiv:
422
351
        return visitSDivInstruction(I, Expr);
423
5.97k
      case Instruction::SRem:
424
212
        return visitSRemInstruction(I, Expr);
425
5.97k
      case Instruction::Call:
426
78
        return visitCallInstruction(I, Expr);
427
5.97k
      default:
428
247
        return visitGenericInst(I, Expr);
429
10.9k
      }
430
10.9k
    }
431
10.9k
432
10.9k
    return ValidatorResult(SCEVType::PARAM, Expr);
433
10.9k
  }
434
};
435
436
class SCEVHasIVParams {
437
  bool HasIVParams = false;
438
439
public:
440
11.7k
  SCEVHasIVParams() {}
441
442
26.8k
  bool follow(const SCEV *S) {
443
26.8k
    const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S);
444
26.8k
    if (!Unknown)
445
25.6k
      return true;
446
1.19k
447
1.19k
    CallInst *Call = dyn_cast<CallInst>(Unknown->getValue());
448
1.19k
449
1.19k
    if (!Call)
450
1.18k
      return true;
451
6
452
6
    if (isConstCall(Call)) {
453
6
      HasIVParams = true;
454
6
      return false;
455
6
    }
456
0
457
0
    return true;
458
0
  }
459
460
26.7k
  bool isDone() { return HasIVParams; }
461
11.7k
  bool hasIVParams() { return HasIVParams; }
462
};
463
464
/// Check whether a SCEV refers to an SSA name defined inside a region.
465
class SCEVInRegionDependences {
466
  const Region *R;
467
  Loop *Scope;
468
  const InvariantLoadsSetTy &ILS;
469
  bool AllowLoops;
470
  bool HasInRegionDeps = false;
471
472
public:
473
  SCEVInRegionDependences(const Region *R, Loop *Scope, bool AllowLoops,
474
                          const InvariantLoadsSetTy &ILS)
475
24.4k
      : R(R), Scope(Scope), ILS(ILS), AllowLoops(AllowLoops) {}
476
477
71.5k
  bool follow(const SCEV *S) {
478
71.5k
    if (auto Unknown = dyn_cast<SCEVUnknown>(S)) {
479
22.0k
      Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
480
22.0k
481
22.0k
      CallInst *Call = dyn_cast<CallInst>(Unknown->getValue());
482
22.0k
483
22.0k
      if (Call && 
isConstCall(Call)114
)
484
20
        return false;
485
22.0k
486
22.0k
      if (Inst) {
487
12.5k
        // When we invariant load hoist a load, we first make sure that there
488
12.5k
        // can be no dependences created by it in the Scop region. So, we should
489
12.5k
        // not consider scalar dependences to `LoadInst`s that are invariant
490
12.5k
        // load hoisted.
491
12.5k
        //
492
12.5k
        // If this check is not present, then we create data dependences which
493
12.5k
        // are strictly not necessary by tracking the invariant load as a
494
12.5k
        // scalar.
495
12.5k
        LoadInst *LI = dyn_cast<LoadInst>(Inst);
496
12.5k
        if (LI && 
ILS.count(LI) > 08.31k
)
497
2.01k
          return false;
498
19.9k
      }
499
19.9k
500
19.9k
      // Return true when Inst is defined inside the region R.
501
19.9k
      if (!Inst || 
!R->contains(Inst)10.5k
)
502
11.3k
        return true;
503
8.62k
504
8.62k
      HasInRegionDeps = true;
505
8.62k
      return false;
506
8.62k
    }
507
49.4k
508
49.4k
    if (auto AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
509
13.5k
      if (AllowLoops)
510
0
        return true;
511
13.5k
512
13.5k
      auto *L = AddRec->getLoop();
513
13.5k
      if (R->contains(L) && 
!L->contains(Scope)13.3k
) {
514
25
        HasInRegionDeps = true;
515
25
        return false;
516
25
      }
517
49.4k
    }
518
49.4k
519
49.4k
    return true;
520
49.4k
  }
521
60.8k
  bool isDone() { return false; }
522
24.4k
  bool hasDependences() { return HasInRegionDeps; }
523
};
524
525
namespace polly {
526
/// Find all loops referenced in SCEVAddRecExprs.
527
class SCEVFindLoops {
528
  SetVector<const Loop *> &Loops;
529
530
public:
531
15.8k
  SCEVFindLoops(SetVector<const Loop *> &Loops) : Loops(Loops) {}
532
533
41.5k
  bool follow(const SCEV *S) {
534
41.5k
    if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S))
535
9.28k
      Loops.insert(AddRec->getLoop());
536
41.5k
    return true;
537
41.5k
  }
538
41.5k
  bool isDone() { return false; }
539
};
540
541
15.8k
void findLoops(const SCEV *Expr, SetVector<const Loop *> &Loops) {
542
15.8k
  SCEVFindLoops FindLoops(Loops);
543
15.8k
  SCEVTraversal<SCEVFindLoops> ST(FindLoops);
544
15.8k
  ST.visitAll(Expr);
545
15.8k
}
546
547
/// Find all values referenced in SCEVUnknowns.
548
class SCEVFindValues {
549
  ScalarEvolution &SE;
550
  SetVector<Value *> &Values;
551
552
public:
553
  SCEVFindValues(ScalarEvolution &SE, SetVector<Value *> &Values)
554
19.6k
      : SE(SE), Values(Values) {}
555
556
46.0k
  bool follow(const SCEV *S) {
557
46.0k
    const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S);
558
46.0k
    if (!Unknown)
559
39.1k
      return true;
560
6.88k
561
6.88k
    Values.insert(Unknown->getValue());
562
6.88k
    Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
563
6.88k
    if (!Inst || 
(2.92k
Inst->getOpcode() != Instruction::SRem2.92k
&&
564
2.92k
                  
Inst->getOpcode() != Instruction::SDiv2.88k
))
565
6.76k
      return false;
566
118
567
118
    auto *Dividend = SE.getSCEV(Inst->getOperand(1));
568
118
    if (!isa<SCEVConstant>(Dividend))
569
2
      return false;
570
116
571
116
    auto *Divisor = SE.getSCEV(Inst->getOperand(0));
572
116
    SCEVFindValues FindValues(SE, Values);
573
116
    SCEVTraversal<SCEVFindValues> ST(FindValues);
574
116
    ST.visitAll(Dividend);
575
116
    ST.visitAll(Divisor);
576
116
577
116
    return false;
578
116
  }
579
39.1k
  bool isDone() { return false; }
580
};
581
582
void findValues(const SCEV *Expr, ScalarEvolution &SE,
583
19.4k
                SetVector<Value *> &Values) {
584
19.4k
  SCEVFindValues FindValues(SE, Values);
585
19.4k
  SCEVTraversal<SCEVFindValues> ST(FindValues);
586
19.4k
  ST.visitAll(Expr);
587
19.4k
}
588
589
11.7k
bool hasIVParams(const SCEV *Expr) {
590
11.7k
  SCEVHasIVParams HasIVParams;
591
11.7k
  SCEVTraversal<SCEVHasIVParams> ST(HasIVParams);
592
11.7k
  ST.visitAll(Expr);
593
11.7k
  return HasIVParams.hasIVParams();
594
11.7k
}
595
596
bool hasScalarDepsInsideRegion(const SCEV *Expr, const Region *R,
597
                               llvm::Loop *Scope, bool AllowLoops,
598
24.4k
                               const InvariantLoadsSetTy &ILS) {
599
24.4k
  SCEVInRegionDependences InRegionDeps(R, Scope, AllowLoops, ILS);
600
24.4k
  SCEVTraversal<SCEVInRegionDependences> ST(InRegionDeps);
601
24.4k
  ST.visitAll(Expr);
602
24.4k
  return InRegionDeps.hasDependences();
603
24.4k
}
604
605
bool isAffineExpr(const Region *R, llvm::Loop *Scope, const SCEV *Expr,
606
47.9k
                  ScalarEvolution &SE, InvariantLoadsSetTy *ILS) {
607
47.9k
  if (isa<SCEVCouldNotCompute>(Expr))
608
0
    return false;
609
47.9k
610
47.9k
  SCEVValidator Validator(R, Scope, SE, ILS);
611
47.9k
  LLVM_DEBUG({
612
47.9k
    dbgs() << "\n";
613
47.9k
    dbgs() << "Expr: " << *Expr << "\n";
614
47.9k
    dbgs() << "Region: " << R->getNameStr() << "\n";
615
47.9k
    dbgs() << " -> ";
616
47.9k
  });
617
47.9k
618
47.9k
  ValidatorResult Result = Validator.visit(Expr);
619
47.9k
620
47.9k
  LLVM_DEBUG({
621
47.9k
    if (Result.isValid())
622
47.9k
      dbgs() << "VALID\n";
623
47.9k
    dbgs() << "\n";
624
47.9k
  });
625
47.9k
626
47.9k
  return Result.isValid();
627
47.9k
}
628
629
static bool isAffineExpr(Value *V, const Region *R, Loop *Scope,
630
52
                         ScalarEvolution &SE, ParameterSetTy &Params) {
631
52
  auto *E = SE.getSCEV(V);
632
52
  if (isa<SCEVCouldNotCompute>(E))
633
0
    return false;
634
52
635
52
  SCEVValidator Validator(R, Scope, SE, nullptr);
636
52
  ValidatorResult Result = Validator.visit(E);
637
52
  if (!Result.isValid())
638
0
    return false;
639
52
640
52
  auto ResultParams = Result.getParameters();
641
52
  Params.insert(ResultParams.begin(), ResultParams.end());
642
52
643
52
  return true;
644
52
}
645
646
bool isAffineConstraint(Value *V, const Region *R, llvm::Loop *Scope,
647
                        ScalarEvolution &SE, ParameterSetTy &Params,
648
84
                        bool OrExpr) {
649
84
  if (auto *ICmp = dyn_cast<ICmpInst>(V)) {
650
26
    return isAffineConstraint(ICmp->getOperand(0), R, Scope, SE, Params,
651
26
                              true) &&
652
26
           isAffineConstraint(ICmp->getOperand(1), R, Scope, SE, Params, true);
653
58
  } else if (auto *BinOp = dyn_cast<BinaryOperator>(V)) {
654
10
    auto Opcode = BinOp->getOpcode();
655
10
    if (Opcode == Instruction::And || 
Opcode == Instruction::Or4
)
656
6
      return isAffineConstraint(BinOp->getOperand(0), R, Scope, SE, Params,
657
6
                                false) &&
658
6
             isAffineConstraint(BinOp->getOperand(1), R, Scope, SE, Params,
659
6
                                false);
660
52
    /* Fall through */
661
52
  }
662
52
663
52
  if (!OrExpr)
664
0
    return false;
665
52
666
52
  return isAffineExpr(V, R, Scope, SE, Params);
667
52
}
668
669
ParameterSetTy getParamsInAffineExpr(const Region *R, Loop *Scope,
670
12.4k
                                     const SCEV *Expr, ScalarEvolution &SE) {
671
12.4k
  if (isa<SCEVCouldNotCompute>(Expr))
672
0
    return ParameterSetTy();
673
12.4k
674
12.4k
  InvariantLoadsSetTy ILS;
675
12.4k
  SCEVValidator Validator(R, Scope, SE, &ILS);
676
12.4k
  ValidatorResult Result = Validator.visit(Expr);
677
12.4k
  assert(Result.isValid() && "Requested parameters for an invalid SCEV!");
678
12.4k
679
12.4k
  return Result.getParameters();
680
12.4k
}
681
682
std::pair<const SCEVConstant *, const SCEV *>
683
19.4k
extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
684
19.4k
  auto *ConstPart = cast<SCEVConstant>(SE.getConstant(S->getType(), 1));
685
19.4k
686
19.4k
  if (auto *Constant = dyn_cast<SCEVConstant>(S))
687
8.80k
    return std::make_pair(Constant, SE.getConstant(S->getType(), 1));
688
10.6k
689
10.6k
  auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
690
10.6k
  if (AddRec) {
691
4.47k
    auto *StartExpr = AddRec->getStart();
692
4.47k
    if (StartExpr->isZero()) {
693
3.29k
      auto StepPair = extractConstantFactor(AddRec->getStepRecurrence(SE), SE);
694
3.29k
      auto *LeftOverAddRec =
695
3.29k
          SE.getAddRecExpr(StartExpr, StepPair.second, AddRec->getLoop(),
696
3.29k
                           AddRec->getNoWrapFlags());
697
3.29k
      return std::make_pair(StepPair.first, LeftOverAddRec);
698
3.29k
    }
699
1.18k
    return std::make_pair(ConstPart, S);
700
1.18k
  }
701
6.20k
702
6.20k
  if (auto *Add = dyn_cast<SCEVAddExpr>(S)) {
703
259
    SmallVector<const SCEV *, 4> LeftOvers;
704
259
    auto Op0Pair = extractConstantFactor(Add->getOperand(0), SE);
705
259
    auto *Factor = Op0Pair.first;
706
259
    if (SE.isKnownNegative(Factor)) {
707
93
      Factor = cast<SCEVConstant>(SE.getNegativeSCEV(Factor));
708
93
      LeftOvers.push_back(SE.getNegativeSCEV(Op0Pair.second));
709
166
    } else {
710
166
      LeftOvers.push_back(Op0Pair.second);
711
166
    }
712
259
713
381
    for (unsigned u = 1, e = Add->getNumOperands(); u < e; 
u++122
) {
714
260
      auto OpUPair = extractConstantFactor(Add->getOperand(u), SE);
715
260
      // TODO: Use something smarter than equality here, e.g., gcd.
716
260
      if (Factor == OpUPair.first)
717
113
        LeftOvers.push_back(OpUPair.second);
718
147
      else if (Factor == SE.getNegativeSCEV(OpUPair.first))
719
9
        LeftOvers.push_back(SE.getNegativeSCEV(OpUPair.second));
720
138
      else
721
138
        return std::make_pair(ConstPart, S);
722
260
    }
723
259
724
259
    auto *NewAdd = SE.getAddExpr(LeftOvers, Add->getNoWrapFlags());
725
121
    return std::make_pair(Factor, NewAdd);
726
5.94k
  }
727
5.94k
728
5.94k
  auto *Mul = dyn_cast<SCEVMulExpr>(S);
729
5.94k
  if (!Mul)
730
5.28k
    return std::make_pair(ConstPart, S);
731
660
732
660
  SmallVector<const SCEV *, 4> LeftOvers;
733
660
  for (auto *Op : Mul->operands())
734
1.37k
    if (isa<SCEVConstant>(Op))
735
594
      ConstPart = cast<SCEVConstant>(SE.getMulExpr(ConstPart, Op));
736
776
    else
737
776
      LeftOvers.push_back(Op);
738
660
739
660
  return std::make_pair(ConstPart, SE.getMulExpr(LeftOvers));
740
660
}
741
742
const SCEV *tryForwardThroughPHI(const SCEV *Expr, Region &R,
743
                                 ScalarEvolution &SE, LoopInfo &LI,
744
32.2k
                                 const DominatorTree &DT) {
745
32.2k
  if (auto *Unknown = dyn_cast<SCEVUnknown>(Expr)) {
746
5.61k
    Value *V = Unknown->getValue();
747
5.61k
    auto *PHI = dyn_cast<PHINode>(V);
748
5.61k
    if (!PHI)
749
5.56k
      return Expr;
750
48
751
48
    Value *Final = nullptr;
752
48
753
99
    for (unsigned i = 0; i < PHI->getNumIncomingValues(); 
i++51
) {
754
94
      BasicBlock *Incoming = PHI->getIncomingBlock(i);
755
94
      if (isErrorBlock(*Incoming, R, LI, DT) && 
R.contains(Incoming)7
)
756
3
        continue;
757
91
      if (Final)
758
43
        return Expr;
759
48
      Final = PHI->getIncomingValue(i);
760
48
    }
761
48
762
48
    
if (5
Final5
)
763
5
      return SE.getSCEV(Final);
764
26.6k
  }
765
26.6k
  return Expr;
766
26.6k
}
767
768
Value *getUniqueNonErrorValue(PHINode *PHI, Region *R, LoopInfo &LI,
769
11
                              const DominatorTree &DT) {
770
11
  Value *V = nullptr;
771
25
  for (unsigned i = 0; i < PHI->getNumIncomingValues(); 
i++14
) {
772
22
    BasicBlock *BB = PHI->getIncomingBlock(i);
773
22
    if (!isErrorBlock(*BB, *R, LI, DT)) {
774
19
      if (V)
775
8
        return nullptr;
776
11
      V = PHI->getIncomingValue(i);
777
11
    }
778
22
  }
779
11
780
11
  
return V3
;
781
11
}
782
} // namespace polly