Coverage Report

Created: 2017-08-18 19:41

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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.61k
  ValidatorResult(const ValidatorResult &Source) {
48
6.61k
    Type = Source.Type;
49
6.61k
    Parameters = Source.Parameters;
50
6.61k
  }
51
52
  /// Construct a result with a certain type and no parameters.
53
113k
  ValidatorResult(SCEVType::TYPE Type) : Type(Type) {
54
113k
    assert(Type != SCEVType::PARAM && "Did you forget to pass the parameter");
55
113k
  }
56
57
  /// Construct a result with a certain type and a single parameter.
58
17.1k
  ValidatorResult(SCEVType::TYPE Type, const SCEV *Expr) : Type(Type) {
59
17.1k
    Parameters.insert(Expr);
60
17.1k
  }
61
62
  /// Get the type of the ValidatorResult.
63
991
  SCEVType::TYPE getType() { return Type; }
64
65
  /// Is the analyzed SCEV constant during the execution of the SCoP.
66
160
  bool isConstant() 
{ return Type == SCEVType::INT || 160
Type == SCEVType::PARAM113
; }
67
68
  /// Is the analyzed SCEV valid.
69
109k
  bool isValid() { return Type != SCEVType::INVALID; }
70
71
  /// Is the analyzed SCEV of Type IV.
72
4.19k
  bool isIV() { return Type == SCEVType::IV; }
73
74
  /// Is the analyzed SCEV of Type INT.
75
39.5k
  bool isINT() { return Type == SCEVType::INT; }
76
77
  /// Is the analyzed SCEV of Type PARAM.
78
14.3k
  bool isPARAM() { return Type == SCEVType::PARAM; }
79
80
  /// Get the parameters of this validator result.
81
11.5k
  const ParameterSetTy &getParameters() { return Parameters; }
82
83
  /// Add the parameters of Source to this result.
84
38.3k
  void addParamsFrom(const ValidatorResult &Source) {
85
38.3k
    Parameters.insert(Source.Parameters.begin(), Source.Parameters.end());
86
38.3k
  }
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.7k
  void merge(const ValidatorResult &ToMerge) {
93
12.7k
    Type = std::max(Type, ToMerge.Type);
94
12.7k
    addParamsFrom(ToMerge);
95
12.7k
  }
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
213
bool polly::isConstCall(llvm::CallInst *Call) {
121
213
  if (Call->mayReadOrWriteMemory())
122
93
    return false;
123
213
124
213
  for (auto &Operand : Call->arg_operands())
125
114
    
if (114
!isa<ConstantInt>(&Operand)114
)
126
46
      return false;
127
120
128
74
  return true;
129
213
}
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
56.7k
      : R(R), Scope(Scope), SE(SE), ILS(ILS) {}
144
145
78.7k
  class ValidatorResult visitConstant(const SCEVConstant *Constant) {
146
78.7k
    return ValidatorResult(SCEVType::INT);
147
78.7k
  }
148
149
  class ValidatorResult visitZeroExtendOrTruncateExpr(const SCEV *Expr,
150
991
                                                      const SCEV *Operand) {
151
991
    ValidatorResult Op = visit(Operand);
152
991
    auto Type = Op.getType();
153
991
154
991
    // If unsigned operations are allowed return the operand, otherwise
155
991
    // check if we can model the expression without unsigned assumptions.
156
991
    if (
PollyAllowUnsignedOperations || 991
Type == SCEVType::INVALID0
)
157
991
      return Op;
158
991
159
0
    
if (0
Type == SCEVType::IV0
)
160
0
      return ValidatorResult(SCEVType::INVALID);
161
0
    return ValidatorResult(SCEVType::PARAM, Expr);
162
991
  }
163
164
252
  class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
165
252
    return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
166
252
  }
167
168
739
  class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
169
739
    return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
170
739
  }
171
172
2.65k
  class ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
173
2.65k
    return visit(Expr->getOperand());
174
2.65k
  }
175
176
2.98k
  class ValidatorResult visitAddExpr(const SCEVAddExpr *Expr) {
177
2.98k
    ValidatorResult Return(SCEVType::INT);
178
2.98k
179
9.09k
    for (int i = 0, e = Expr->getNumOperands(); 
i < e9.09k
;
++i6.11k
)
{6.18k
180
6.18k
      ValidatorResult Op = visit(Expr->getOperand(i));
181
6.18k
      Return.merge(Op);
182
6.18k
183
6.18k
      // Early exit.
184
6.18k
      if (!Return.isValid())
185
69
        break;
186
6.18k
    }
187
2.98k
188
2.98k
    return Return;
189
2.98k
  }
190
191
4.19k
  class ValidatorResult visitMulExpr(const SCEVMulExpr *Expr) {
192
4.19k
    ValidatorResult Return(SCEVType::INT);
193
4.19k
194
4.19k
    bool HasMultipleParams = false;
195
4.19k
196
13.4k
    for (int i = 0, e = Expr->getNumOperands(); 
i < e13.4k
;
++i9.28k
)
{9.33k
197
9.33k
      ValidatorResult Op = visit(Expr->getOperand(i));
198
9.33k
199
9.33k
      if (Op.isINT())
200
3.94k
        continue;
201
9.33k
202
5.39k
      
if (5.39k
Op.isPARAM() && 5.39k
Return.isPARAM()5.01k
)
{1.19k
203
1.19k
        HasMultipleParams = true;
204
1.19k
        continue;
205
5.39k
      }
206
5.39k
207
4.19k
      
if (4.19k
(Op.isIV() || 4.19k
Op.isPARAM()3.98k
) &&
!Return.isINT()4.02k
)
{53
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
4.19k
      }
216
4.19k
217
4.19k
      Return.merge(Op);
218
4.19k
    }
219
4.19k
220
4.13k
    
if (4.13k
HasMultipleParams && 4.13k
Return.isValid()955
)
221
955
      return ValidatorResult(SCEVType::PARAM, Expr);
222
4.13k
223
3.18k
    return Return;
224
4.19k
  }
225
226
28.1k
  class ValidatorResult visitAddRecExpr(const SCEVAddRecExpr *Expr) {
227
28.1k
    if (
!Expr->isAffine()28.1k
)
{124
228
124
      DEBUG(dbgs() << "INVALID: AddRec is not affine");
229
124
      return ValidatorResult(SCEVType::INVALID);
230
28.1k
    }
231
28.1k
232
28.1k
    ValidatorResult Start = visit(Expr->getStart());
233
28.0k
    ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE));
234
28.0k
235
28.0k
    if (!Start.isValid())
236
1.11k
      return Start;
237
28.0k
238
26.9k
    
if (26.9k
!Recurrence.isValid()26.9k
)
239
0
      return Recurrence;
240
26.9k
241
26.9k
    auto *L = Expr->getLoop();
242
26.9k
    if (
R->contains(L) && 26.9k
(!Scope || 26.2k
!L->contains(Scope)26.2k
))
{35
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
26.9k
    }
248
26.9k
249
26.8k
    
if (26.8k
R->contains(L)26.8k
)
{26.2k
250
26.2k
      if (
Recurrence.isINT()26.2k
)
{25.5k
251
25.5k
        ValidatorResult Result(SCEVType::IV);
252
25.5k
        Result.addParamsFrom(Start);
253
25.5k
        return Result;
254
26.2k
      }
255
26.2k
256
720
      
DEBUG720
(dbgs() << "INVALID: AddRec within scop has non-int"720
257
720
                      "recurrence part");
258
26.2k
      return ValidatorResult(SCEVType::INVALID);
259
26.8k
    }
260
26.8k
261
26.8k
    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
655
267
655
    // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}'
268
655
    // if 'start' is not zero.
269
655
    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
655
    return ZeroStartResult;
278
28.1k
  }
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 < e3.57k
;
++i2.41k
)
{2.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
34
  class ValidatorResult visitUMaxExpr(const SCEVUMaxExpr *Expr) {
296
34
    // We do not support unsigned max operations. If 'Expr' is constant during
297
34
    // Scop execution we treat this as a parameter, otherwise we bail out.
298
102
    for (int i = 0, e = Expr->getNumOperands(); 
i < e102
;
++i68
)
{68
299
68
      ValidatorResult Op = visit(Expr->getOperand(i));
300
68
301
68
      if (
!Op.isConstant()68
)
{0
302
0
        DEBUG(dbgs() << "INVALID: UMaxExpr has a non-constant operand");
303
0
        return ValidatorResult(SCEVType::INVALID);
304
68
      }
305
68
    }
306
34
307
34
    return ValidatorResult(SCEVType::PARAM, Expr);
308
34
  }
309
310
2.32k
  ValidatorResult visitGenericInst(Instruction *I, const SCEV *S) {
311
2.32k
    if (
R->contains(I)2.32k
)
{107
312
107
      DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
313
107
                      "within the region\n");
314
107
      return ValidatorResult(SCEVType::INVALID);
315
2.32k
    }
316
2.32k
317
2.21k
    return ValidatorResult(SCEVType::PARAM, S);
318
2.32k
  }
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)79
)
{65
324
65
      auto Call = cast<CallInst>(I);
325
65
326
65
      if (!isConstCall(Call))
327
31
        return ValidatorResult(SCEVType::INVALID, S);
328
79
    }
329
48
    return ValidatorResult(SCEVType::PARAM, S);
330
79
  }
331
332
4.84k
  ValidatorResult visitLoadInstruction(Instruction *I, const SCEV *S) {
333
4.84k
    if (
R->contains(I) && 4.84k
ILS2.74k
)
{2.74k
334
2.74k
      ILS->insert(cast<LoadInst>(I));
335
2.74k
      return ValidatorResult(SCEVType::PARAM, S);
336
4.84k
    }
337
4.84k
338
2.10k
    return visitGenericInst(I, S);
339
4.84k
  }
340
341
  ValidatorResult visitDivision(const SCEV *Dividend, const SCEV *Divisor,
342
                                const SCEV *DivExpr,
343
562
                                Instruction *SDiv = nullptr) {
344
562
345
562
    // First check if we might be able to model the division, thus if the
346
562
    // divisor is constant. If so, check the dividend, otherwise check if
347
562
    // the whole division can be seen as a parameter.
348
562
    if (
isa<SCEVConstant>(Divisor) && 562
!Divisor->isZero()511
)
349
508
      return visit(Dividend);
350
562
351
562
    // For signed divisions use the SDiv instruction to check for a parameter
352
562
    // division, for unsigned divisions check the operands.
353
54
    
if (54
SDiv54
)
354
8
      return visitGenericInst(SDiv, DivExpr);
355
54
356
54
    ValidatorResult LHS = visit(Dividend);
357
46
    ValidatorResult RHS = visit(Divisor);
358
46
    if (
LHS.isConstant() && 46
RHS.isConstant()46
)
359
46
      return ValidatorResult(SCEVType::PARAM, DivExpr);
360
46
361
0
    
DEBUG0
(dbgs() << "INVALID: unsigned division of non-constant expressions");0
362
46
    return ValidatorResult(SCEVType::INVALID);
363
562
  }
364
365
276
  ValidatorResult visitUDivExpr(const SCEVUDivExpr *Expr) {
366
276
    if (!PollyAllowUnsignedOperations)
367
0
      return ValidatorResult(SCEVType::INVALID);
368
276
369
276
    auto *Dividend = Expr->getLHS();
370
276
    auto *Divisor = Expr->getRHS();
371
276
    return visitDivision(Dividend, Divisor, Expr);
372
276
  }
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 || 212
CI->isZeroValue()209
)
390
3
      return visitGenericInst(SRem, S);
391
212
392
212
    auto *Dividend = SRem->getOperand(0);
393
209
    auto *DividendSCEV = SE.getSCEV(Dividend);
394
212
    return visit(DividendSCEV);
395
212
  }
396
397
16.1k
  ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
398
16.1k
    Value *V = Expr->getValue();
399
16.1k
400
16.1k
    if (
!Expr->getType()->isIntegerTy() && 16.1k
!Expr->getType()->isPointerTy()223
)
{0
401
0
      DEBUG(dbgs() << "INVALID: UnknownExpr is not an integer or pointer");
402
0
      return ValidatorResult(SCEVType::INVALID);
403
16.1k
    }
404
16.1k
405
16.1k
    
if (16.1k
isa<UndefValue>(V)16.1k
)
{27
406
27
      DEBUG(dbgs() << "INVALID: UnknownExpr references an undef value");
407
27
      return ValidatorResult(SCEVType::INVALID);
408
16.1k
    }
409
16.1k
410
16.1k
    
if (Instruction *16.1k
I16.1k
= dyn_cast<Instruction>(Expr->getValue()))
{5.72k
411
5.72k
      switch (I->getOpcode()) {
412
5.72k
      case Instruction::IntToPtr:
413
5.72k
        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
414
5.72k
      case Instruction::PtrToInt:
415
5.72k
        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
416
5.72k
      case Instruction::Load:
417
5.72k
        return visitLoadInstruction(I, Expr);
418
5.72k
      case Instruction::SDiv:
419
5.72k
        return visitSDivInstruction(I, Expr);
420
5.72k
      case Instruction::SRem:
421
5.72k
        return visitSRemInstruction(I, Expr);
422
5.72k
      case Instruction::Call:
423
5.72k
        return visitCallInstruction(I, Expr);
424
5.72k
      default:
425
5.72k
        return visitGenericInst(I, Expr);
426
5.72k
      }
427
16.1k
    }
428
16.1k
429
10.4k
    return ValidatorResult(SCEVType::PARAM, Expr);
430
16.1k
  }
431
};
432
433
class SCEVHasIVParams {
434
  bool HasIVParams = false;
435
436
public:
437
11.1k
  SCEVHasIVParams() {}
438
439
24.9k
  bool follow(const SCEV *S) {
440
24.9k
    const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S);
441
24.9k
    if (!Unknown)
442
23.7k
      return true;
443
24.9k
444
24.9k
    CallInst *Call = dyn_cast<CallInst>(Unknown->getValue());
445
1.15k
446
1.15k
    if (!Call)
447
1.14k
      return true;
448
1.15k
449
6
    
if (6
isConstCall(Call)6
)
{6
450
6
      HasIVParams = true;
451
6
      return false;
452
6
    }
453
6
454
0
    return true;
455
24.9k
  }
456
457
24.9k
  bool isDone() { return HasIVParams; }
458
11.1k
  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
32.9k
      : R(R), Scope(Scope), ILS(ILS), AllowLoops(AllowLoops) {}
473
474
93.2k
  bool follow(const SCEV *S) {
475
93.2k
    if (auto 
Unknown93.2k
= dyn_cast<SCEVUnknown>(S))
{26.0k
476
26.0k
      Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
477
26.0k
478
26.0k
      CallInst *Call = dyn_cast<CallInst>(Unknown->getValue());
479
26.0k
480
26.0k
      if (
Call && 26.0k
isConstCall(Call)136
)
481
30
        return false;
482
26.0k
483
26.0k
      
if (26.0k
Inst26.0k
)
{13.7k
484
13.7k
        // When we invariant load hoist a load, we first make sure that there
485
13.7k
        // can be no dependences created by it in the Scop region. So, we should
486
13.7k
        // not consider scalar dependences to `LoadInst`s that are invariant
487
13.7k
        // load hoisted.
488
13.7k
        //
489
13.7k
        // If this check is not present, then we create data dependences which
490
13.7k
        // are strictly not necessary by tracking the invariant load as a
491
13.7k
        // scalar.
492
13.7k
        LoadInst *LI = dyn_cast<LoadInst>(Inst);
493
13.7k
        if (
LI && 13.7k
ILS.count(LI) > 09.45k
)
494
2.43k
          return false;
495
26.0k
      }
496
26.0k
497
26.0k
      // Return true when Inst is defined inside the region R.
498
23.6k
      
if (23.6k
!Inst || 23.6k
!R->contains(Inst)11.2k
)
499
15.5k
        return true;
500
23.6k
501
23.6k
      HasInRegionDeps = true;
502
23.6k
      return false;
503
93.2k
    }
504
93.2k
505
67.1k
    
if (auto 67.1k
AddRec67.1k
= dyn_cast<SCEVAddRecExpr>(S))
{19.4k
506
19.4k
      if (AllowLoops)
507
0
        return true;
508
19.4k
509
19.4k
      auto *L = AddRec->getLoop();
510
19.4k
      if (
R->contains(L) && 19.4k
!L->contains(Scope)19.1k
)
{30
511
30
        HasInRegionDeps = true;
512
30
        return false;
513
19.4k
      }
514
67.1k
    }
515
67.1k
516
67.0k
    return true;
517
93.2k
  }
518
82.5k
  bool isDone() { return false; }
519
32.9k
  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.0k
  SCEVFindLoops(SetVector<const Loop *> &Loops) : Loops(Loops) {}
529
530
39.0k
  bool follow(const SCEV *S) {
531
39.0k
    if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S))
532
8.72k
      Loops.insert(AddRec->getLoop());
533
39.0k
    return true;
534
39.0k
  }
535
39.0k
  bool isDone() { return false; }
536
};
537
538
15.0k
void findLoops(const SCEV *Expr, SetVector<const Loop *> &Loops) {
539
15.0k
  SCEVFindLoops FindLoops(Loops);
540
15.0k
  SCEVTraversal<SCEVFindLoops> ST(FindLoops);
541
15.0k
  ST.visitAll(Expr);
542
15.0k
}
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
18.2k
      : SE(SE), Values(Values) {}
552
553
42.9k
  bool follow(const SCEV *S) {
554
42.9k
    const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S);
555
42.9k
    if (!Unknown)
556
36.4k
      return true;
557
42.9k
558
42.9k
    Values.insert(Unknown->getValue());
559
6.47k
    Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
560
6.47k
    if (
!Inst || 6.47k
(Inst->getOpcode() != Instruction::SRem &&2.80k
561
2.80k
                  Inst->getOpcode() != Instruction::SDiv))
562
6.39k
      return false;
563
6.47k
564
6.47k
    auto *Dividend = SE.getSCEV(Inst->getOperand(1));
565
83
    if (!isa<SCEVConstant>(Dividend))
566
2
      return false;
567
83
568
83
    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
83
    return false;
575
42.9k
  }
576
36.4k
  bool isDone() { return false; }
577
};
578
579
void findValues(const SCEV *Expr, ScalarEvolution &SE,
580
18.1k
                SetVector<Value *> &Values) {
581
18.1k
  SCEVFindValues FindValues(SE, Values);
582
18.1k
  SCEVTraversal<SCEVFindValues> ST(FindValues);
583
18.1k
  ST.visitAll(Expr);
584
18.1k
}
585
586
11.1k
bool hasIVParams(const SCEV *Expr) {
587
11.1k
  SCEVHasIVParams HasIVParams;
588
11.1k
  SCEVTraversal<SCEVHasIVParams> ST(HasIVParams);
589
11.1k
  ST.visitAll(Expr);
590
11.1k
  return HasIVParams.hasIVParams();
591
11.1k
}
592
593
bool hasScalarDepsInsideRegion(const SCEV *Expr, const Region *R,
594
                               llvm::Loop *Scope, bool AllowLoops,
595
32.9k
                               const InvariantLoadsSetTy &ILS) {
596
32.9k
  SCEVInRegionDependences InRegionDeps(R, Scope, AllowLoops, ILS);
597
32.9k
  SCEVTraversal<SCEVInRegionDependences> ST(InRegionDeps);
598
32.9k
  ST.visitAll(Expr);
599
32.9k
  return InRegionDeps.hasDependences();
600
32.9k
}
601
602
bool isAffineExpr(const Region *R, llvm::Loop *Scope, const SCEV *Expr,
603
45.1k
                  ScalarEvolution &SE, InvariantLoadsSetTy *ILS) {
604
45.1k
  if (isa<SCEVCouldNotCompute>(Expr))
605
0
    return false;
606
45.1k
607
45.1k
  SCEVValidator Validator(R, Scope, SE, ILS);
608
45.1k
  DEBUG({
609
45.1k
    dbgs() << "\n";
610
45.1k
    dbgs() << "Expr: " << *Expr << "\n";
611
45.1k
    dbgs() << "Region: " << R->getNameStr() << "\n";
612
45.1k
    dbgs() << " -> ";
613
45.1k
  });
614
45.1k
615
45.1k
  ValidatorResult Result = Validator.visit(Expr);
616
45.1k
617
45.1k
  DEBUG({
618
45.1k
    if (Result.isValid())
619
45.1k
      dbgs() << "VALID\n";
620
45.1k
    dbgs() << "\n";
621
45.1k
  });
622
45.1k
623
45.1k
  return Result.isValid();
624
45.1k
}
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 *
ICmp84
= dyn_cast<ICmpInst>(V))
{26
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
84
  } else 
if (auto *58
BinOp58
= dyn_cast<BinaryOperator>(V))
{10
651
10
    auto Opcode = BinOp->getOpcode();
652
10
    if (
Opcode == Instruction::And || 10
Opcode == Instruction::Or4
)
653
10
      return isAffineConstraint(BinOp->getOperand(0), R, Scope, SE, Params,
654
6
                                false) &&
655
6
             isAffineConstraint(BinOp->getOperand(1), R, Scope, SE, Params,
656
10
                                false);
657
10
    /* Fall through */
658
84
  }
659
84
660
52
  
if (52
!OrExpr52
)
661
0
    return false;
662
52
663
52
  return isAffineExpr(V, R, Scope, SE, Params);
664
84
}
665
666
ParameterSetTy getParamsInAffineExpr(const Region *R, Loop *Scope,
667
11.5k
                                     const SCEV *Expr, ScalarEvolution &SE) {
668
11.5k
  if (isa<SCEVCouldNotCompute>(Expr))
669
0
    return ParameterSetTy();
670
11.5k
671
11.5k
  InvariantLoadsSetTy ILS;
672
11.5k
  SCEVValidator Validator(R, Scope, SE, &ILS);
673
11.5k
  ValidatorResult Result = Validator.visit(Expr);
674
11.5k
  assert(Result.isValid() && "Requested parameters for an invalid SCEV!");
675
11.5k
676
11.5k
  return Result.getParameters();
677
11.5k
}
678
679
std::pair<const SCEVConstant *, const SCEV *>
680
18.1k
extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
681
18.1k
  auto *ConstPart = cast<SCEVConstant>(SE.getConstant(S->getType(), 1));
682
18.1k
683
18.1k
  if (auto *Constant = dyn_cast<SCEVConstant>(S))
684
8.14k
    return std::make_pair(Constant, SE.getConstant(S->getType(), 1));
685
18.1k
686
18.1k
  auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
687
9.97k
  if (
AddRec9.97k
)
{4.11k
688
4.11k
    auto *StartExpr = AddRec->getStart();
689
4.11k
    if (
StartExpr->isZero()4.11k
)
{3.06k
690
3.06k
      auto StepPair = extractConstantFactor(AddRec->getStepRecurrence(SE), SE);
691
3.06k
      auto *LeftOverAddRec =
692
3.06k
          SE.getAddRecExpr(StartExpr, StepPair.second, AddRec->getLoop(),
693
3.06k
                           AddRec->getNoWrapFlags());
694
3.06k
      return std::make_pair(StepPair.first, LeftOverAddRec);
695
4.11k
    }
696
1.05k
    return std::make_pair(ConstPart, S);
697
9.97k
  }
698
9.97k
699
5.85k
  
if (auto *5.85k
Add5.85k
= dyn_cast<SCEVAddExpr>(S))
{235
700
235
    SmallVector<const SCEV *, 4> LeftOvers;
701
235
    auto Op0Pair = extractConstantFactor(Add->getOperand(0), SE);
702
235
    auto *Factor = Op0Pair.first;
703
235
    if (
SE.isKnownNegative(Factor)235
)
{80
704
80
      Factor = cast<SCEVConstant>(SE.getNegativeSCEV(Factor));
705
80
      LeftOvers.push_back(SE.getNegativeSCEV(Op0Pair.second));
706
235
    } else {
707
155
      LeftOvers.push_back(Op0Pair.second);
708
235
    }
709
235
710
347
    for (unsigned u = 1, e = Add->getNumOperands(); 
u < e347
;
u++112
)
{236
711
236
      auto OpUPair = extractConstantFactor(Add->getOperand(u), SE);
712
236
      // TODO: Use something smarter than equality here, e.g., gcd.
713
236
      if (Factor == OpUPair.first)
714
106
        LeftOvers.push_back(OpUPair.second);
715
130
      else 
if (130
Factor == SE.getNegativeSCEV(OpUPair.first)130
)
716
6
        LeftOvers.push_back(SE.getNegativeSCEV(OpUPair.second));
717
130
      else
718
124
        return std::make_pair(ConstPart, S);
719
236
    }
720
235
721
235
    auto *NewAdd = SE.getAddExpr(LeftOvers, Add->getNoWrapFlags());
722
235
    return std::make_pair(Factor, NewAdd);
723
5.85k
  }
724
5.85k
725
5.85k
  auto *Mul = dyn_cast<SCEVMulExpr>(S);
726
5.62k
  if (!Mul)
727
5.00k
    return std::make_pair(ConstPart, S);
728
5.62k
729
5.62k
  SmallVector<const SCEV *, 4> LeftOvers;
730
621
  for (auto *Op : Mul->operands())
731
1.29k
    
if (1.29k
isa<SCEVConstant>(Op)1.29k
)
732
555
      ConstPart = cast<SCEVConstant>(SE.getMulExpr(ConstPart, Op));
733
1.29k
    else
734
737
      LeftOvers.push_back(Op);
735
621
736
5.62k
  return std::make_pair(ConstPart, SE.getMulExpr(LeftOvers));
737
18.1k
}
738
} // namespace polly