Coverage Report

Created: 2017-11-23 03:11

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