Coverage Report

Created: 2019-04-21 11:35

/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/ScopDetection.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
2.75k
  ValidatorResult(const ValidatorResult &Source) {
48
2.75k
    Type = Source.Type;
49
2.75k
    Parameters = Source.Parameters;
50
2.75k
  }
51
52
  /// Construct a result with a certain type and no parameters.
53
44.9k
  ValidatorResult(SCEVType::TYPE Type) : Type(Type) {
54
44.9k
    assert(Type != SCEVType::PARAM && "Did you forget to pass the parameter");
55
44.9k
  }
56
57
  /// Construct a result with a certain type and a single parameter.
58
7.96k
  ValidatorResult(SCEVType::TYPE Type, const SCEV *Expr) : Type(Type) {
59
7.96k
    Parameters.insert(Expr);
60
7.96k
  }
61
62
  /// Get the type of the ValidatorResult.
63
186
  SCEVType::TYPE getType() { return Type; }
64
65
  /// Is the analyzed SCEV constant during the execution of the SCoP.
66
50
  bool isConstant() { return Type == SCEVType::INT || 
Type == SCEVType::PARAM40
; }
67
68
  /// Is the analyzed SCEV valid.
69
45.0k
  bool isValid() { return Type != SCEVType::INVALID; }
70
71
  /// Is the analyzed SCEV of Type IV.
72
1.55k
  bool isIV() { return Type == SCEVType::IV; }
73
74
  /// Is the analyzed SCEV of Type INT.
75
15.3k
  bool isINT() { return Type == SCEVType::INT; }
76
77
  /// Is the analyzed SCEV of Type PARAM.
78
5.75k
  bool isPARAM() { return Type == SCEVType::PARAM; }
79
80
  /// Get the parameters of this validator result.
81
4.03k
  const ParameterSetTy &getParameters() { return Parameters; }
82
83
  /// Add the parameters of Source to this result.
84
15.6k
  void addParamsFrom(const ValidatorResult &Source) {
85
15.6k
    Parameters.insert(Source.Parameters.begin(), Source.Parameters.end());
86
15.6k
  }
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
5.82k
  void merge(const ValidatorResult &ToMerge) {
93
5.82k
    Type = std::max(Type, ToMerge.Type);
94
5.82k
    addParamsFrom(ToMerge);
95
5.82k
  }
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
48
bool polly::isConstCall(llvm::CallInst *Call) {
121
48
  if (Call->mayReadOrWriteMemory())
122
18
    return false;
123
30
124
30
  for (auto &Operand : Call->arg_operands())
125
30
    if (!isa<ConstantInt>(&Operand))
126
17
      return false;
127
30
128
30
  
return true13
;
129
30
}
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
22.9k
      : R(R), Scope(Scope), SE(SE), ILS(ILS) {}
144
145
31.0k
  class ValidatorResult visitConstant(const SCEVConstant *Constant) {
146
31.0k
    return ValidatorResult(SCEVType::INT);
147
31.0k
  }
148
149
  class ValidatorResult visitZeroExtendOrTruncateExpr(const SCEV *Expr,
150
186
                                                      const SCEV *Operand) {
151
186
    ValidatorResult Op = visit(Operand);
152
186
    auto Type = Op.getType();
153
186
154
186
    // If unsigned operations are allowed return the operand, otherwise
155
186
    // check if we can model the expression without unsigned assumptions.
156
186
    if (PollyAllowUnsignedOperations || 
Type == SCEVType::INVALID0
)
157
186
      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
59
  class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
165
59
    return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
166
59
  }
167
168
127
  class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
169
127
    return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
170
127
  }
171
172
739
  class ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
173
739
    return visit(Expr->getOperand());
174
739
  }
175
176
1.32k
  class ValidatorResult visitAddExpr(const SCEVAddExpr *Expr) {
177
1.32k
    ValidatorResult Return(SCEVType::INT);
178
1.32k
179
3.93k
    for (int i = 0, e = Expr->getNumOperands(); i < e; 
++i2.61k
) {
180
2.64k
      ValidatorResult Op = visit(Expr->getOperand(i));
181
2.64k
      Return.merge(Op);
182
2.64k
183
2.64k
      // Early exit.
184
2.64k
      if (!Return.isValid())
185
26
        break;
186
2.64k
    }
187
1.32k
188
1.32k
    return Return;
189
1.32k
  }
190
191
1.53k
  class ValidatorResult visitMulExpr(const SCEVMulExpr *Expr) {
192
1.53k
    ValidatorResult Return(SCEVType::INT);
193
1.53k
194
1.53k
    bool HasMultipleParams = false;
195
1.53k
196
5.23k
    for (int i = 0, e = Expr->getNumOperands(); i < e; 
++i3.70k
) {
197
3.72k
      ValidatorResult Op = visit(Expr->getOperand(i));
198
3.72k
199
3.72k
      if (Op.isINT())
200
1.46k
        continue;
201
2.25k
202
2.25k
      if (Op.isPARAM() && 
Return.isPARAM()2.07k
) {
203
704
        HasMultipleParams = true;
204
704
        continue;
205
704
      }
206
1.55k
207
1.55k
      if ((Op.isIV() || 
Op.isPARAM()1.42k
) &&
!Return.isINT()1.49k
) {
208
23
        LLVM_DEBUG(
209
23
            dbgs() << "INVALID: More than one non-int operand in MulExpr\n"
210
23
                   << "\tExpr: " << *Expr << "\n"
211
23
                   << "\tPrevious expression type: " << Return << "\n"
212
23
                   << "\tNext operand (" << Op << "): " << *Expr->getOperand(i)
213
23
                   << "\n");
214
23
215
23
        return ValidatorResult(SCEVType::INVALID);
216
23
      }
217
1.52k
218
1.52k
      Return.merge(Op);
219
1.52k
    }
220
1.53k
221
1.53k
    
if (1.50k
HasMultipleParams1.50k
&&
Return.isValid()504
)
222
504
      return ValidatorResult(SCEVType::PARAM, Expr);
223
1.00k
224
1.00k
    return Return;
225
1.00k
  }
226
227
11.0k
  class ValidatorResult visitAddRecExpr(const SCEVAddRecExpr *Expr) {
228
11.0k
    if (!Expr->isAffine()) {
229
40
      LLVM_DEBUG(dbgs() << "INVALID: AddRec is not affine");
230
40
      return ValidatorResult(SCEVType::INVALID);
231
40
    }
232
11.0k
233
11.0k
    ValidatorResult Start = visit(Expr->getStart());
234
11.0k
    ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE));
235
11.0k
236
11.0k
    if (!Start.isValid())
237
698
      return Start;
238
10.3k
239
10.3k
    if (!Recurrence.isValid())
240
0
      return Recurrence;
241
10.3k
242
10.3k
    auto *L = Expr->getLoop();
243
10.3k
    if (R->contains(L) && 
(10.1k
!Scope10.1k
||
!L->contains(Scope)10.1k
)) {
244
5
      LLVM_DEBUG(
245
5
          dbgs() << "INVALID: Loop of AddRec expression boxed in an a "
246
5
                    "non-affine subregion or has a non-synthesizable exit "
247
5
                    "value.");
248
5
      return ValidatorResult(SCEVType::INVALID);
249
5
    }
250
10.3k
251
10.3k
    if (R->contains(L)) {
252
10.1k
      if (Recurrence.isINT()) {
253
9.80k
        ValidatorResult Result(SCEVType::IV);
254
9.80k
        Result.addParamsFrom(Start);
255
9.80k
        return Result;
256
9.80k
      }
257
339
258
339
      LLVM_DEBUG(dbgs() << "INVALID: AddRec within scop has non-int"
259
339
                           "recurrence part");
260
339
      return ValidatorResult(SCEVType::INVALID);
261
339
    }
262
200
263
200
    assert(Recurrence.isConstant() && "Expected 'Recurrence' to be constant");
264
200
265
200
    // Directly generate ValidatorResult for Expr if 'start' is zero.
266
200
    if (Expr->getStart()->isZero())
267
133
      return ValidatorResult(SCEVType::PARAM, Expr);
268
67
269
67
    // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}'
270
67
    // if 'start' is not zero.
271
67
    const SCEV *ZeroStartExpr = SE.getAddRecExpr(
272
67
        SE.getConstant(Expr->getStart()->getType(), 0),
273
67
        Expr->getStepRecurrence(SE), Expr->getLoop(), Expr->getNoWrapFlags());
274
67
275
67
    ValidatorResult ZeroStartResult =
276
67
        ValidatorResult(SCEVType::PARAM, ZeroStartExpr);
277
67
    ZeroStartResult.addParamsFrom(Start);
278
67
279
67
    return ZeroStartResult;
280
67
  }
281
282
797
  class ValidatorResult visitSMaxExpr(const SCEVSMaxExpr *Expr) {
283
797
    ValidatorResult Return(SCEVType::INT);
284
797
285
2.44k
    for (int i = 0, e = Expr->getNumOperands(); i < e; 
++i1.65k
) {
286
1.65k
      ValidatorResult Op = visit(Expr->getOperand(i));
287
1.65k
288
1.65k
      if (!Op.isValid())
289
0
        return Op;
290
1.65k
291
1.65k
      Return.merge(Op);
292
1.65k
    }
293
797
294
797
    return Return;
295
797
  }
296
297
6
  class ValidatorResult visitUMaxExpr(const SCEVUMaxExpr *Expr) {
298
6
    // We do not support unsigned max operations. If 'Expr' is constant during
299
6
    // Scop execution we treat this as a parameter, otherwise we bail out.
300
18
    for (int i = 0, e = Expr->getNumOperands(); i < e; 
++i12
) {
301
12
      ValidatorResult Op = visit(Expr->getOperand(i));
302
12
303
12
      if (!Op.isConstant()) {
304
0
        LLVM_DEBUG(dbgs() << "INVALID: UMaxExpr has a non-constant operand");
305
0
        return ValidatorResult(SCEVType::INVALID);
306
0
      }
307
12
    }
308
6
309
6
    return ValidatorResult(SCEVType::PARAM, Expr);
310
6
  }
311
312
423
  ValidatorResult visitGenericInst(Instruction *I, const SCEV *S) {
313
423
    if (R->contains(I)) {
314
32
      LLVM_DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
315
32
                           "within the region\n");
316
32
      return ValidatorResult(SCEVType::INVALID);
317
32
    }
318
391
319
391
    return ValidatorResult(SCEVType::PARAM, S);
320
391
  }
321
322
25
  ValidatorResult visitCallInstruction(Instruction *I, const SCEV *S) {
323
25
    assert(I->getOpcode() == Instruction::Call && "Call instruction expected");
324
25
325
25
    if (R->contains(I)) {
326
14
      auto Call = cast<CallInst>(I);
327
14
328
14
      if (!isConstCall(Call))
329
7
        return ValidatorResult(SCEVType::INVALID, S);
330
18
    }
331
18
    return ValidatorResult(SCEVType::PARAM, S);
332
18
  }
333
334
1.76k
  ValidatorResult visitLoadInstruction(Instruction *I, const SCEV *S) {
335
1.76k
    if (R->contains(I) && 
ILS1.43k
) {
336
1.43k
      ILS->insert(cast<LoadInst>(I));
337
1.43k
      return ValidatorResult(SCEVType::PARAM, S);
338
1.43k
    }
339
322
340
322
    return visitGenericInst(I, S);
341
322
  }
342
343
  ValidatorResult visitDivision(const SCEV *Dividend, const SCEV *Divisor,
344
                                const SCEV *DivExpr,
345
124
                                Instruction *SDiv = nullptr) {
346
124
347
124
    // First check if we might be able to model the division, thus if the
348
124
    // divisor is constant. If so, check the dividend, otherwise check if
349
124
    // the whole division can be seen as a parameter.
350
124
    if (isa<SCEVConstant>(Divisor) && 
!Divisor->isZero()105
)
351
102
      return visit(Dividend);
352
22
353
22
    // For signed divisions use the SDiv instruction to check for a parameter
354
22
    // division, for unsigned divisions check the operands.
355
22
    if (SDiv)
356
3
      return visitGenericInst(SDiv, DivExpr);
357
19
358
19
    ValidatorResult LHS = visit(Dividend);
359
19
    ValidatorResult RHS = visit(Divisor);
360
19
    if (LHS.isConstant() && RHS.isConstant())
361
19
      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
54
  ValidatorResult visitUDivExpr(const SCEVUDivExpr *Expr) {
369
54
    if (!PollyAllowUnsignedOperations)
370
0
      return ValidatorResult(SCEVType::INVALID);
371
54
372
54
    auto *Dividend = Expr->getLHS();
373
54
    auto *Divisor = Expr->getRHS();
374
54
    return visitDivision(Dividend, Divisor, Expr);
375
54
  }
376
377
70
  ValidatorResult visitSDivInstruction(Instruction *SDiv, const SCEV *Expr) {
378
70
    assert(SDiv->getOpcode() == Instruction::SDiv &&
379
70
           "Assumed SDiv instruction!");
380
70
381
70
    auto *Dividend = SE.getSCEV(SDiv->getOperand(0));
382
70
    auto *Divisor = SE.getSCEV(SDiv->getOperand(1));
383
70
    return visitDivision(Dividend, Divisor, Expr, SDiv);
384
70
  }
385
386
80
  ValidatorResult visitSRemInstruction(Instruction *SRem, const SCEV *S) {
387
80
    assert(SRem->getOpcode() == Instruction::SRem &&
388
80
           "Assumed SRem instruction!");
389
80
390
80
    auto *Divisor = SRem->getOperand(1);
391
80
    auto *CI = dyn_cast<ConstantInt>(Divisor);
392
80
    if (!CI || 
CI->isZeroValue()77
)
393
3
      return visitGenericInst(SRem, S);
394
77
395
77
    auto *Dividend = SRem->getOperand(0);
396
77
    auto *DividendSCEV = SE.getSCEV(Dividend);
397
77
    return visit(DividendSCEV);
398
77
  }
399
400
7.44k
  ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
401
7.44k
    Value *V = Expr->getValue();
402
7.44k
403
7.44k
    if (!Expr->getType()->isIntegerTy() && 
!Expr->getType()->isPointerTy()37
) {
404
0
      LLVM_DEBUG(dbgs() << "INVALID: UnknownExpr is not an integer or pointer");
405
0
      return ValidatorResult(SCEVType::INVALID);
406
0
    }
407
7.44k
408
7.44k
    if (isa<UndefValue>(V)) {
409
6
      LLVM_DEBUG(dbgs() << "INVALID: UnknownExpr references an undef value");
410
6
      return ValidatorResult(SCEVType::INVALID);
411
6
    }
412
7.43k
413
7.43k
    if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) {
414
2.05k
      switch (I->getOpcode()) {
415
2.05k
      case Instruction::IntToPtr:
416
8
        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
417
2.05k
      case Instruction::PtrToInt:
418
17
        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
419
2.05k
      case Instruction::Load:
420
1.76k
        return visitLoadInstruction(I, Expr);
421
2.05k
      case Instruction::SDiv:
422
70
        return visitSDivInstruction(I, Expr);
423
2.05k
      case Instruction::SRem:
424
80
        return visitSRemInstruction(I, Expr);
425
2.05k
      case Instruction::Call:
426
25
        return visitCallInstruction(I, Expr);
427
2.05k
      default:
428
95
        return visitGenericInst(I, Expr);
429
5.37k
      }
430
5.37k
    }
431
5.37k
432
5.37k
    return ValidatorResult(SCEVType::PARAM, Expr);
433
5.37k
  }
434
};
435
436
class SCEVHasIVParams {
437
  bool HasIVParams = false;
438
439
public:
440
5.21k
  SCEVHasIVParams() {}
441
442
9.92k
  bool follow(const SCEV *S) {
443
9.92k
    const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S);
444
9.92k
    if (!Unknown)
445
9.57k
      return true;
446
351
447
351
    CallInst *Call = dyn_cast<CallInst>(Unknown->getValue());
448
351
449
351
    if (!Call)
450
349
      return true;
451
2
452
2
    if (isConstCall(Call)) {
453
2
      HasIVParams = true;
454
2
      return false;
455
2
    }
456
0
457
0
    return true;
458
0
  }
459
460
9.92k
  bool isDone() { return HasIVParams; }
461
5.21k
  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
8.86k
      : R(R), Scope(Scope), ILS(ILS), AllowLoops(AllowLoops) {}
476
477
27.7k
  bool follow(const SCEV *S) {
478
27.7k
    if (auto Unknown = dyn_cast<SCEVUnknown>(S)) {
479
8.99k
      Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
480
8.99k
481
8.99k
      CallInst *Call = dyn_cast<CallInst>(Unknown->getValue());
482
8.99k
483
8.99k
      if (Call && 
isConstCall(Call)30
)
484
3
        return false;
485
8.98k
486
8.98k
      if (Inst) {
487
5.24k
        // When we invariant load hoist a load, we first make sure that there
488
5.24k
        // can be no dependences created by it in the Scop region. So, we should
489
5.24k
        // not consider scalar dependences to `LoadInst`s that are invariant
490
5.24k
        // load hoisted.
491
5.24k
        //
492
5.24k
        // If this check is not present, then we create data dependences which
493
5.24k
        // are strictly not necessary by tracking the invariant load as a
494
5.24k
        // scalar.
495
5.24k
        LoadInst *LI = dyn_cast<LoadInst>(Inst);
496
5.24k
        if (LI && 
ILS.count(LI) > 03.82k
)
497
1.34k
          return false;
498
7.64k
      }
499
7.64k
500
7.64k
      // Return true when Inst is defined inside the region R.
501
7.64k
      if (!Inst || 
!R->contains(Inst)3.90k
)
502
4.09k
        return true;
503
3.54k
504
3.54k
      HasInRegionDeps = true;
505
3.54k
      return false;
506
3.54k
    }
507
18.7k
508
18.7k
    if (auto AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
509
4.46k
      if (AllowLoops)
510
0
        return true;
511
4.46k
512
4.46k
      auto *L = AddRec->getLoop();
513
4.46k
      if (R->contains(L) && 
!L->contains(Scope)4.38k
) {
514
3
        HasInRegionDeps = true;
515
3
        return false;
516
3
      }
517
18.7k
    }
518
18.7k
519
18.7k
    return true;
520
18.7k
  }
521
22.8k
  bool isDone() { return false; }
522
8.86k
  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
6.78k
  SCEVFindLoops(SetVector<const Loop *> &Loops) : Loops(Loops) {}
532
533
16.2k
  bool follow(const SCEV *S) {
534
16.2k
    if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S))
535
3.52k
      Loops.insert(AddRec->getLoop());
536
16.2k
    return true;
537
16.2k
  }
538
16.2k
  bool isDone() { return false; }
539
};
540
541
6.78k
void findLoops(const SCEV *Expr, SetVector<const Loop *> &Loops) {
542
6.78k
  SCEVFindLoops FindLoops(Loops);
543
6.78k
  SCEVTraversal<SCEVFindLoops> ST(FindLoops);
544
6.78k
  ST.visitAll(Expr);
545
6.78k
}
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
7.41k
      : SE(SE), Values(Values) {}
555
556
17.7k
  bool follow(const SCEV *S) {
557
17.7k
    const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S);
558
17.7k
    if (!Unknown)
559
14.3k
      return true;
560
3.37k
561
3.37k
    Values.insert(Unknown->getValue());
562
3.37k
    Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
563
3.37k
    if (!Inst || 
(1.56k
Inst->getOpcode() != Instruction::SRem1.56k
&&
564
1.56k
                  
Inst->getOpcode() != Instruction::SDiv1.54k
))
565
3.34k
      return false;
566
28
567
28
    auto *Dividend = SE.getSCEV(Inst->getOperand(1));
568
28
    if (!isa<SCEVConstant>(Dividend))
569
0
      return false;
570
28
571
28
    auto *Divisor = SE.getSCEV(Inst->getOperand(0));
572
28
    SCEVFindValues FindValues(SE, Values);
573
28
    SCEVTraversal<SCEVFindValues> ST(FindValues);
574
28
    ST.visitAll(Dividend);
575
28
    ST.visitAll(Divisor);
576
28
577
28
    return false;
578
28
  }
579
14.3k
  bool isDone() { return false; }
580
};
581
582
void findValues(const SCEV *Expr, ScalarEvolution &SE,
583
7.38k
                SetVector<Value *> &Values) {
584
7.38k
  SCEVFindValues FindValues(SE, Values);
585
7.38k
  SCEVTraversal<SCEVFindValues> ST(FindValues);
586
7.38k
  ST.visitAll(Expr);
587
7.38k
}
588
589
5.21k
bool hasIVParams(const SCEV *Expr) {
590
5.21k
  SCEVHasIVParams HasIVParams;
591
5.21k
  SCEVTraversal<SCEVHasIVParams> ST(HasIVParams);
592
5.21k
  ST.visitAll(Expr);
593
5.21k
  return HasIVParams.hasIVParams();
594
5.21k
}
595
596
bool hasScalarDepsInsideRegion(const SCEV *Expr, const Region *R,
597
                               llvm::Loop *Scope, bool AllowLoops,
598
8.86k
                               const InvariantLoadsSetTy &ILS) {
599
8.86k
  SCEVInRegionDependences InRegionDeps(R, Scope, AllowLoops, ILS);
600
8.86k
  SCEVTraversal<SCEVInRegionDependences> ST(InRegionDeps);
601
8.86k
  ST.visitAll(Expr);
602
8.86k
  return InRegionDeps.hasDependences();
603
8.86k
}
604
605
bool isAffineExpr(const Region *R, llvm::Loop *Scope, const SCEV *Expr,
606
18.8k
                  ScalarEvolution &SE, InvariantLoadsSetTy *ILS) {
607
18.8k
  if (isa<SCEVCouldNotCompute>(Expr))
608
0
    return false;
609
18.8k
610
18.8k
  SCEVValidator Validator(R, Scope, SE, ILS);
611
18.8k
  LLVM_DEBUG({
612
18.8k
    dbgs() << "\n";
613
18.8k
    dbgs() << "Expr: " << *Expr << "\n";
614
18.8k
    dbgs() << "Region: " << R->getNameStr() << "\n";
615
18.8k
    dbgs() << " -> ";
616
18.8k
  });
617
18.8k
618
18.8k
  ValidatorResult Result = Validator.visit(Expr);
619
18.8k
620
18.8k
  LLVM_DEBUG({
621
18.8k
    if (Result.isValid())
622
18.8k
      dbgs() << "VALID\n";
623
18.8k
    dbgs() << "\n";
624
18.8k
  });
625
18.8k
626
18.8k
  return Result.isValid();
627
18.8k
}
628
629
static bool isAffineExpr(Value *V, const Region *R, Loop *Scope,
630
6
                         ScalarEvolution &SE, ParameterSetTy &Params) {
631
6
  auto *E = SE.getSCEV(V);
632
6
  if (isa<SCEVCouldNotCompute>(E))
633
0
    return false;
634
6
635
6
  SCEVValidator Validator(R, Scope, SE, nullptr);
636
6
  ValidatorResult Result = Validator.visit(E);
637
6
  if (!Result.isValid())
638
0
    return false;
639
6
640
6
  auto ResultParams = Result.getParameters();
641
6
  Params.insert(ResultParams.begin(), ResultParams.end());
642
6
643
6
  return true;
644
6
}
645
646
bool isAffineConstraint(Value *V, const Region *R, llvm::Loop *Scope,
647
                        ScalarEvolution &SE, ParameterSetTy &Params,
648
9
                        bool OrExpr) {
649
9
  if (auto *ICmp = dyn_cast<ICmpInst>(V)) {
650
3
    return isAffineConstraint(ICmp->getOperand(0), R, Scope, SE, Params,
651
3
                              true) &&
652
3
           isAffineConstraint(ICmp->getOperand(1), R, Scope, SE, Params, true);
653
6
  } else if (auto *BinOp = dyn_cast<BinaryOperator>(V)) {
654
0
    auto Opcode = BinOp->getOpcode();
655
0
    if (Opcode == Instruction::And || Opcode == Instruction::Or)
656
0
      return isAffineConstraint(BinOp->getOperand(0), R, Scope, SE, Params,
657
0
                                false) &&
658
0
             isAffineConstraint(BinOp->getOperand(1), R, Scope, SE, Params,
659
0
                                false);
660
6
    /* Fall through */
661
6
  }
662
6
663
6
  if (!OrExpr)
664
0
    return false;
665
6
666
6
  return isAffineExpr(V, R, Scope, SE, Params);
667
6
}
668
669
ParameterSetTy getParamsInAffineExpr(const Region *R, Loop *Scope,
670
4.02k
                                     const SCEV *Expr, ScalarEvolution &SE) {
671
4.02k
  if (isa<SCEVCouldNotCompute>(Expr))
672
0
    return ParameterSetTy();
673
4.02k
674
4.02k
  InvariantLoadsSetTy ILS;
675
4.02k
  SCEVValidator Validator(R, Scope, SE, &ILS);
676
4.02k
  ValidatorResult Result = Validator.visit(Expr);
677
4.02k
  assert(Result.isValid() && "Requested parameters for an invalid SCEV!");
678
4.02k
679
4.02k
  return Result.getParameters();
680
4.02k
}
681
682
std::pair<const SCEVConstant *, const SCEV *>
683
6.37k
extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
684
6.37k
  auto *ConstPart = cast<SCEVConstant>(SE.getConstant(S->getType(), 1));
685
6.37k
686
6.37k
  if (auto *Constant = dyn_cast<SCEVConstant>(S))
687
2.85k
    return std::make_pair(Constant, SE.getConstant(S->getType(), 1));
688
3.51k
689
3.51k
  auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
690
3.51k
  if (AddRec) {
691
1.46k
    auto *StartExpr = AddRec->getStart();
692
1.46k
    if (StartExpr->isZero()) {
693
1.08k
      auto StepPair = extractConstantFactor(AddRec->getStepRecurrence(SE), SE);
694
1.08k
      auto *LeftOverAddRec =
695
1.08k
          SE.getAddRecExpr(StartExpr, StepPair.second, AddRec->getLoop(),
696
1.08k
                           AddRec->getNoWrapFlags());
697
1.08k
      return std::make_pair(StepPair.first, LeftOverAddRec);
698
1.08k
    }
699
377
    return std::make_pair(ConstPart, S);
700
377
  }
701
2.05k
702
2.05k
  if (auto *Add = dyn_cast<SCEVAddExpr>(S)) {
703
90
    SmallVector<const SCEV *, 4> LeftOvers;
704
90
    auto Op0Pair = extractConstantFactor(Add->getOperand(0), SE);
705
90
    auto *Factor = Op0Pair.first;
706
90
    if (SE.isKnownNegative(Factor)) {
707
25
      Factor = cast<SCEVConstant>(SE.getNegativeSCEV(Factor));
708
25
      LeftOvers.push_back(SE.getNegativeSCEV(Op0Pair.second));
709
65
    } else {
710
65
      LeftOvers.push_back(Op0Pair.second);
711
65
    }
712
90
713
127
    for (unsigned u = 1, e = Add->getNumOperands(); u < e; 
u++37
) {
714
90
      auto OpUPair = extractConstantFactor(Add->getOperand(u), SE);
715
90
      // TODO: Use something smarter than equality here, e.g., gcd.
716
90
      if (Factor == OpUPair.first)
717
36
        LeftOvers.push_back(OpUPair.second);
718
54
      else if (Factor == SE.getNegativeSCEV(OpUPair.first))
719
1
        LeftOvers.push_back(SE.getNegativeSCEV(OpUPair.second));
720
53
      else
721
53
        return std::make_pair(ConstPart, S);
722
90
    }
723
90
724
90
    auto *NewAdd = SE.getAddExpr(LeftOvers, Add->getNoWrapFlags());
725
37
    return std::make_pair(Factor, NewAdd);
726
1.96k
  }
727
1.96k
728
1.96k
  auto *Mul = dyn_cast<SCEVMulExpr>(S);
729
1.96k
  if (!Mul)
730
1.78k
    return std::make_pair(ConstPart, S);
731
179
732
179
  SmallVector<const SCEV *, 4> LeftOvers;
733
179
  for (auto *Op : Mul->operands())
734
367
    if (isa<SCEVConstant>(Op))
735
165
      ConstPart = cast<SCEVConstant>(SE.getMulExpr(ConstPart, Op));
736
202
    else
737
202
      LeftOvers.push_back(Op);
738
179
739
179
  return std::make_pair(ConstPart, SE.getMulExpr(LeftOvers));
740
179
}
741
742
const SCEV *tryForwardThroughPHI(const SCEV *Expr, Region &R,
743
                                 ScalarEvolution &SE, LoopInfo &LI,
744
11.4k
                                 const DominatorTree &DT) {
745
11.4k
  if (auto *Unknown = dyn_cast<SCEVUnknown>(Expr)) {
746
2.81k
    Value *V = Unknown->getValue();
747
2.81k
    auto *PHI = dyn_cast<PHINode>(V);
748
2.81k
    if (!PHI)
749
2.79k
      return Expr;
750
17
751
17
    Value *Final = nullptr;
752
17
753
34
    for (unsigned i = 0; i < PHI->getNumIncomingValues(); 
i++17
) {
754
34
      BasicBlock *Incoming = PHI->getIncomingBlock(i);
755
34
      if (isErrorBlock(*Incoming, R, LI, DT) && 
R.contains(Incoming)3
)
756
0
        continue;
757
34
      if (Final)
758
17
        return Expr;
759
17
      Final = PHI->getIncomingValue(i);
760
17
    }
761
17
762
17
    
if (0
Final0
)
763
0
      return SE.getSCEV(Final);
764
8.64k
  }
765
8.64k
  return Expr;
766
8.64k
}
767
768
Value *getUniqueNonErrorValue(PHINode *PHI, Region *R, LoopInfo &LI,
769
4
                              const DominatorTree &DT) {
770
4
  Value *V = nullptr;
771
11
  for (unsigned i = 0; i < PHI->getNumIncomingValues(); 
i++7
) {
772
8
    BasicBlock *BB = PHI->getIncomingBlock(i);
773
8
    if (!isErrorBlock(*BB, *R, LI, DT)) {
774
5
      if (V)
775
1
        return nullptr;
776
4
      V = PHI->getIncomingValue(i);
777
4
    }
778
8
  }
779
4
780
4
  
return V3
;
781
4
}
782
} // namespace polly