Coverage Report

Created: 2017-06-28 17:40

/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.19k
  ValidatorResult(const ValidatorResult &Source) {
48
6.19k
    Type = Source.Type;
49
6.19k
    Parameters = Source.Parameters;
50
6.19k
  }
51
52
  /// Construct a result with a certain type and no parameters.
53
107k
  ValidatorResult(SCEVType::TYPE Type) : Type(Type) {
54
107k
    assert(Type != SCEVType::PARAM && "Did you forget to pass the parameter");
55
107k
  }
56
57
  /// Construct a result with a certain type and a single parameter.
58
16.0k
  ValidatorResult(SCEVType::TYPE Type, const SCEV *Expr) : Type(Type) {
59
16.0k
    Parameters.insert(Expr);
60
16.0k
  }
61
62
  /// Get the type of the ValidatorResult.
63
985
  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
104k
  bool isValid() { return Type != SCEVType::INVALID; }
70
71
  /// Is the analyzed SCEV of Type IV.
72
3.80k
  bool isIV() { return Type == SCEVType::IV; }
73
74
  /// Is the analyzed SCEV of Type INT.
75
37.0k
  bool isINT() { return Type == SCEVType::INT; }
76
77
  /// Is the analyzed SCEV of Type PARAM.
78
13.2k
  bool isPARAM() { return Type == SCEVType::PARAM; }
79
80
  /// Get the parameters of this validator result.
81
10.7k
  const ParameterSetTy &getParameters() { return Parameters; }
82
83
  /// Add the parameters of Source to this result.
84
36.5k
  void addParamsFrom(const ValidatorResult &Source) {
85
36.5k
    Parameters.insert(Source.Parameters.begin(), Source.Parameters.end());
86
36.5k
  }
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.3k
  void merge(const ValidatorResult &ToMerge) {
93
12.3k
    Type = std::max(Type, ToMerge.Type);
94
12.3k
    addParamsFrom(ToMerge);
95
12.3k
  }
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
120
  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
120
}
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
53.4k
      : R(R), Scope(Scope), SE(SE), ILS(ILS) {}
144
145
74.7k
  class ValidatorResult visitConstant(const SCEVConstant *Constant) {
146
74.7k
    return ValidatorResult(SCEVType::INT);
147
74.7k
  }
148
149
  class ValidatorResult visitZeroExtendOrTruncateExpr(const SCEV *Expr,
150
985
                                                      const SCEV *Operand) {
151
985
    ValidatorResult Op = visit(Operand);
152
985
    auto Type = Op.getType();
153
985
154
985
    // If unsigned operations are allowed return the operand, otherwise
155
985
    // check if we can model the expression without unsigned assumptions.
156
985
    if (
PollyAllowUnsignedOperations || 985
Type == SCEVType::INVALID0
)
157
985
      return Op;
158
985
159
0
    
if (0
Type == SCEVType::IV0
)
160
0
      return ValidatorResult(SCEVType::INVALID);
161
0
    return ValidatorResult(SCEVType::PARAM, Expr);
162
0
  }
163
164
258
  class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
165
258
    return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
166
258
  }
167
168
727
  class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
169
727
    return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
170
727
  }
171
172
2.15k
  class ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
173
2.15k
    return visit(Expr->getOperand());
174
2.15k
  }
175
176
2.96k
  class ValidatorResult visitAddExpr(const SCEVAddExpr *Expr) {
177
2.96k
    ValidatorResult Return(SCEVType::INT);
178
2.96k
179
9.03k
    for (int i = 0, e = Expr->getNumOperands(); 
i < e9.03k
;
++i6.07k
)
{6.14k
180
6.14k
      ValidatorResult Op = visit(Expr->getOperand(i));
181
6.14k
      Return.merge(Op);
182
6.14k
183
6.14k
      // Early exit.
184
6.14k
      if (!Return.isValid())
185
69
        break;
186
6.14k
    }
187
2.96k
188
2.96k
    return Return;
189
2.96k
  }
190
191
3.80k
  class ValidatorResult visitMulExpr(const SCEVMulExpr *Expr) {
192
3.80k
    ValidatorResult Return(SCEVType::INT);
193
3.80k
194
3.80k
    bool HasMultipleParams = false;
195
3.80k
196
12.3k
    for (int i = 0, e = Expr->getNumOperands(); 
i < e12.3k
;
++i8.50k
)
{8.55k
197
8.55k
      ValidatorResult Op = visit(Expr->getOperand(i));
198
8.55k
199
8.55k
      if (Op.isINT())
200
3.55k
        continue;
201
8.55k
202
5.00k
      
if (5.00k
Op.isPARAM() && 5.00k
Return.isPARAM()4.62k
)
{1.19k
203
1.19k
        HasMultipleParams = true;
204
1.19k
        continue;
205
1.19k
      }
206
5.00k
207
3.80k
      
if (3.80k
(Op.isIV() || 3.80k
Op.isPARAM()3.60k
) &&
!Return.isINT()3.64k
)
{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
53
      }
216
3.80k
217
3.75k
      Return.merge(Op);
218
3.75k
    }
219
3.80k
220
3.75k
    
if (3.75k
HasMultipleParams && 3.75k
Return.isValid()952
)
221
952
      return ValidatorResult(SCEVType::PARAM, Expr);
222
3.75k
223
2.79k
    return Return;
224
3.75k
  }
225
226
26.7k
  class ValidatorResult visitAddRecExpr(const SCEVAddRecExpr *Expr) {
227
26.7k
    if (
!Expr->isAffine()26.7k
)
{110
228
110
      DEBUG(dbgs() << "INVALID: AddRec is not affine");
229
110
      return ValidatorResult(SCEVType::INVALID);
230
110
    }
231
26.7k
232
26.6k
    ValidatorResult Start = visit(Expr->getStart());
233
26.6k
    ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE));
234
26.6k
235
26.6k
    if (!Start.isValid())
236
1.10k
      return Start;
237
26.6k
238
25.5k
    
if (25.5k
!Recurrence.isValid()25.5k
)
239
0
      return Recurrence;
240
25.5k
241
25.5k
    auto *L = Expr->getLoop();
242
25.5k
    if (
R->contains(L) && 25.5k
(!Scope || 24.8k
!L->contains(Scope)24.8k
))
{23
243
23
      DEBUG(dbgs() << "INVALID: Loop of AddRec expression boxed in an a "
244
23
                      "non-affine subregion or has a non-synthesizable exit "
245
23
                      "value.");
246
23
      return ValidatorResult(SCEVType::INVALID);
247
23
    }
248
25.5k
249
25.4k
    
if (25.4k
R->contains(L)25.4k
)
{24.8k
250
24.8k
      if (
Recurrence.isINT()24.8k
)
{24.1k
251
24.1k
        ValidatorResult Result(SCEVType::IV);
252
24.1k
        Result.addParamsFrom(Start);
253
24.1k
        return Result;
254
24.1k
      }
255
24.8k
256
717
      
DEBUG717
(dbgs() << "INVALID: AddRec within scop has non-int"717
257
717
                      "recurrence part");
258
717
      return ValidatorResult(SCEVType::INVALID);
259
24.8k
    }
260
25.4k
261
631
    assert(Recurrence.isConstant() && "Expected 'Recurrence' to be constant");
262
631
263
631
    // Directly generate ValidatorResult for Expr if 'start' is zero.
264
631
    if (Expr->getStart()->isZero())
265
489
      return ValidatorResult(SCEVType::PARAM, Expr);
266
631
267
631
    // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}'
268
631
    // if 'start' is not zero.
269
142
    const SCEV *ZeroStartExpr = SE.getAddRecExpr(
270
142
        SE.getConstant(Expr->getStart()->getType(), 0),
271
142
        Expr->getStepRecurrence(SE), Expr->getLoop(), Expr->getNoWrapFlags());
272
142
273
142
    ValidatorResult ZeroStartResult =
274
142
        ValidatorResult(SCEVType::PARAM, ZeroStartExpr);
275
142
    ZeroStartResult.addParamsFrom(Start);
276
142
277
142
    return ZeroStartResult;
278
631
  }
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
0
      }
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
)
{109
312
109
      DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
313
109
                      "within the region\n");
314
109
      return ValidatorResult(SCEVType::INVALID);
315
109
    }
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
65
    }
329
48
    return ValidatorResult(SCEVType::PARAM, S);
330
79
  }
331
332
4.85k
  ValidatorResult visitLoadInstruction(Instruction *I, const SCEV *S) {
333
4.85k
    if (
R->contains(I) && 4.85k
ILS2.74k
)
{2.74k
334
2.74k
      ILS->insert(cast<LoadInst>(I));
335
2.74k
      return ValidatorResult(SCEVType::PARAM, S);
336
2.74k
    }
337
4.85k
338
2.10k
    return visitGenericInst(I, S);
339
4.85k
  }
340
341
  ValidatorResult visitDivision(const SCEV *Dividend, const SCEV *Divisor,
342
                                const SCEV *DivExpr,
343
561
                                Instruction *SDiv = nullptr) {
344
561
345
561
    // First check if we might be able to model the division, thus if the
346
561
    // divisor is constant. If so, check the dividend, otherwise check if
347
561
    // the whole division can be seen as a parameter.
348
561
    if (
isa<SCEVConstant>(Divisor) && 561
!Divisor->isZero()510
)
349
507
      return visit(Dividend);
350
561
351
561
    // For signed divisions use the SDiv instruction to check for a parameter
352
561
    // division, for unsigned divisions check the operands.
353
54
    
if (54
SDiv54
)
354
8
      return visitGenericInst(SDiv, DivExpr);
355
54
356
46
    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
0
    return ValidatorResult(SCEVType::INVALID);
363
46
  }
364
365
275
  ValidatorResult visitUDivExpr(const SCEVUDivExpr *Expr) {
366
275
    if (!PollyAllowUnsignedOperations)
367
0
      return ValidatorResult(SCEVType::INVALID);
368
275
369
275
    auto *Dividend = Expr->getLHS();
370
275
    auto *Divisor = Expr->getRHS();
371
275
    return visitDivision(Dividend, Divisor, Expr);
372
275
  }
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
209
    auto *Dividend = SRem->getOperand(0);
393
209
    auto *DividendSCEV = SE.getSCEV(Dividend);
394
209
    return visit(DividendSCEV);
395
212
  }
396
397
15.0k
  ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
398
15.0k
    Value *V = Expr->getValue();
399
15.0k
400
15.0k
    if (
!Expr->getType()->isIntegerTy() && 15.0k
!Expr->getType()->isPointerTy()223
)
{0
401
0
      DEBUG(dbgs() << "INVALID: UnknownExpr is not an integer or pointer");
402
0
      return ValidatorResult(SCEVType::INVALID);
403
0
    }
404
15.0k
405
15.0k
    
if (15.0k
isa<UndefValue>(V)15.0k
)
{30
406
30
      DEBUG(dbgs() << "INVALID: UnknownExpr references an undef value");
407
30
      return ValidatorResult(SCEVType::INVALID);
408
30
    }
409
15.0k
410
15.0k
    
if (Instruction *15.0k
I15.0k
= dyn_cast<Instruction>(Expr->getValue()))
{5.72k
411
5.72k
      switch (I->getOpcode()) {
412
28
      case Instruction::IntToPtr:
413
28
        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
414
63
      case Instruction::PtrToInt:
415
63
        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
416
4.85k
      case Instruction::Load:
417
4.85k
        return visitLoadInstruction(I, Expr);
418
286
      case Instruction::SDiv:
419
286
        return visitSDivInstruction(I, Expr);
420
212
      case Instruction::SRem:
421
212
        return visitSRemInstruction(I, Expr);
422
79
      case Instruction::Call:
423
79
        return visitCallInstruction(I, Expr);
424
208
      default:
425
208
        return visitGenericInst(I, Expr);
426
5.72k
      }
427
5.72k
    }
428
15.0k
429
9.32k
    return ValidatorResult(SCEVType::PARAM, Expr);
430
15.0k
  }
431
};
432
433
class SCEVHasIVParams {
434
  bool HasIVParams = false;
435
436
public:
437
10.4k
  SCEVHasIVParams() {}
438
439
22.7k
  bool follow(const SCEV *S) {
440
22.7k
    const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S);
441
22.7k
    if (!Unknown)
442
21.8k
      return true;
443
22.7k
444
864
    CallInst *Call = dyn_cast<CallInst>(Unknown->getValue());
445
864
446
864
    if (!Call)
447
858
      return true;
448
864
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
6
  }
456
457
22.7k
  bool isDone() { return HasIVParams; }
458
10.4k
  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
  bool AllowLoops;
466
  bool HasInRegionDeps = false;
467
468
public:
469
  SCEVInRegionDependences(const Region *R, Loop *Scope, bool AllowLoops)
470
31.2k
      : R(R), Scope(Scope), AllowLoops(AllowLoops) {}
471
472
88.3k
  bool follow(const SCEV *S) {
473
88.3k
    if (auto 
Unknown88.3k
= dyn_cast<SCEVUnknown>(S))
{24.8k
474
24.8k
      Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
475
24.8k
476
24.8k
      CallInst *Call = dyn_cast<CallInst>(Unknown->getValue());
477
24.8k
478
24.8k
      if (
Call && 24.8k
isConstCall(Call)136
)
479
30
        return false;
480
24.8k
481
24.8k
      // Return true when Inst is defined inside the region R.
482
24.8k
      
if (24.8k
!Inst || 24.8k
!R->contains(Inst)13.7k
)
483
14.2k
        return true;
484
24.8k
485
10.6k
      HasInRegionDeps = true;
486
10.6k
      return false;
487
24.8k
    }
488
88.3k
489
63.4k
    
if (auto 63.4k
AddRec63.4k
= dyn_cast<SCEVAddRecExpr>(S))
{18.3k
490
18.3k
      if (AllowLoops)
491
0
        return true;
492
18.3k
493
18.3k
      
if (18.3k
!Scope18.3k
)
{32
494
32
        HasInRegionDeps = true;
495
32
        return false;
496
32
      }
497
18.3k
      auto *L = AddRec->getLoop();
498
18.3k
      if (
R->contains(L) && 18.3k
!L->contains(Scope)18.0k
)
{0
499
0
        HasInRegionDeps = true;
500
0
        return false;
501
0
      }
502
18.3k
    }
503
63.4k
504
63.4k
    return true;
505
63.4k
  }
506
77.6k
  bool isDone() { return false; }
507
31.2k
  bool hasDependences() { return HasInRegionDeps; }
508
};
509
510
namespace polly {
511
/// Find all loops referenced in SCEVAddRecExprs.
512
class SCEVFindLoops {
513
  SetVector<const Loop *> &Loops;
514
515
public:
516
14.0k
  SCEVFindLoops(SetVector<const Loop *> &Loops) : Loops(Loops) {}
517
518
36.1k
  bool follow(const SCEV *S) {
519
36.1k
    if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S))
520
8.32k
      Loops.insert(AddRec->getLoop());
521
36.1k
    return true;
522
36.1k
  }
523
36.1k
  bool isDone() { return false; }
524
};
525
526
14.0k
void findLoops(const SCEV *Expr, SetVector<const Loop *> &Loops) {
527
14.0k
  SCEVFindLoops FindLoops(Loops);
528
14.0k
  SCEVTraversal<SCEVFindLoops> ST(FindLoops);
529
14.0k
  ST.visitAll(Expr);
530
14.0k
}
531
532
/// Find all values referenced in SCEVUnknowns.
533
class SCEVFindValues {
534
  ScalarEvolution &SE;
535
  SetVector<Value *> &Values;
536
537
public:
538
  SCEVFindValues(ScalarEvolution &SE, SetVector<Value *> &Values)
539
17.1k
      : SE(SE), Values(Values) {}
540
541
40.7k
  bool follow(const SCEV *S) {
542
40.7k
    const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S);
543
40.7k
    if (!Unknown)
544
34.5k
      return true;
545
40.7k
546
6.14k
    Values.insert(Unknown->getValue());
547
6.14k
    Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
548
6.14k
    if (
!Inst || 6.14k
(Inst->getOpcode() != Instruction::SRem &&2.79k
549
2.75k
                  Inst->getOpcode() != Instruction::SDiv))
550
6.06k
      return false;
551
6.14k
552
83
    auto *Dividend = SE.getSCEV(Inst->getOperand(1));
553
83
    if (!isa<SCEVConstant>(Dividend))
554
2
      return false;
555
83
556
81
    auto *Divisor = SE.getSCEV(Inst->getOperand(0));
557
81
    SCEVFindValues FindValues(SE, Values);
558
81
    SCEVTraversal<SCEVFindValues> ST(FindValues);
559
81
    ST.visitAll(Dividend);
560
81
    ST.visitAll(Divisor);
561
81
562
81
    return false;
563
83
  }
564
34.5k
  bool isDone() { return false; }
565
};
566
567
void findValues(const SCEV *Expr, ScalarEvolution &SE,
568
17.0k
                SetVector<Value *> &Values) {
569
17.0k
  SCEVFindValues FindValues(SE, Values);
570
17.0k
  SCEVTraversal<SCEVFindValues> ST(FindValues);
571
17.0k
  ST.visitAll(Expr);
572
17.0k
}
573
574
10.4k
bool hasIVParams(const SCEV *Expr) {
575
10.4k
  SCEVHasIVParams HasIVParams;
576
10.4k
  SCEVTraversal<SCEVHasIVParams> ST(HasIVParams);
577
10.4k
  ST.visitAll(Expr);
578
10.4k
  return HasIVParams.hasIVParams();
579
10.4k
}
580
581
bool hasScalarDepsInsideRegion(const SCEV *Expr, const Region *R,
582
31.2k
                               llvm::Loop *Scope, bool AllowLoops) {
583
31.2k
  SCEVInRegionDependences InRegionDeps(R, Scope, AllowLoops);
584
31.2k
  SCEVTraversal<SCEVInRegionDependences> ST(InRegionDeps);
585
31.2k
  ST.visitAll(Expr);
586
31.2k
  return InRegionDeps.hasDependences();
587
31.2k
}
588
589
bool isAffineExpr(const Region *R, llvm::Loop *Scope, const SCEV *Expr,
590
42.6k
                  ScalarEvolution &SE, InvariantLoadsSetTy *ILS) {
591
42.6k
  if (isa<SCEVCouldNotCompute>(Expr))
592
0
    return false;
593
42.6k
594
42.6k
  SCEVValidator Validator(R, Scope, SE, ILS);
595
42.6k
  DEBUG({
596
42.6k
    dbgs() << "\n";
597
42.6k
    dbgs() << "Expr: " << *Expr << "\n";
598
42.6k
    dbgs() << "Region: " << R->getNameStr() << "\n";
599
42.6k
    dbgs() << " -> ";
600
42.6k
  });
601
42.6k
602
42.6k
  ValidatorResult Result = Validator.visit(Expr);
603
42.6k
604
42.6k
  DEBUG({
605
42.6k
    if (Result.isValid())
606
42.6k
      dbgs() << "VALID\n";
607
42.6k
    dbgs() << "\n";
608
42.6k
  });
609
42.6k
610
42.6k
  return Result.isValid();
611
42.6k
}
612
613
static bool isAffineExpr(Value *V, const Region *R, Loop *Scope,
614
50
                         ScalarEvolution &SE, ParameterSetTy &Params) {
615
50
  auto *E = SE.getSCEV(V);
616
50
  if (isa<SCEVCouldNotCompute>(E))
617
0
    return false;
618
50
619
50
  SCEVValidator Validator(R, Scope, SE, nullptr);
620
50
  ValidatorResult Result = Validator.visit(E);
621
50
  if (!Result.isValid())
622
0
    return false;
623
50
624
50
  auto ResultParams = Result.getParameters();
625
50
  Params.insert(ResultParams.begin(), ResultParams.end());
626
50
627
50
  return true;
628
50
}
629
630
bool isAffineConstraint(Value *V, const Region *R, llvm::Loop *Scope,
631
                        ScalarEvolution &SE, ParameterSetTy &Params,
632
81
                        bool OrExpr) {
633
81
  if (auto *
ICmp81
= dyn_cast<ICmpInst>(V))
{25
634
25
    return isAffineConstraint(ICmp->getOperand(0), R, Scope, SE, Params,
635
25
                              true) &&
636
25
           isAffineConstraint(ICmp->getOperand(1), R, Scope, SE, Params, true);
637
56
  } else 
if (auto *56
BinOp56
= dyn_cast<BinaryOperator>(V))
{10
638
10
    auto Opcode = BinOp->getOpcode();
639
10
    if (
Opcode == Instruction::And || 10
Opcode == Instruction::Or4
)
640
6
      return isAffineConstraint(BinOp->getOperand(0), R, Scope, SE, Params,
641
6
                                false) &&
642
6
             isAffineConstraint(BinOp->getOperand(1), R, Scope, SE, Params,
643
6
                                false);
644
10
    /* Fall through */
645
10
  }
646
81
647
50
  
if (50
!OrExpr50
)
648
0
    return false;
649
50
650
50
  return isAffineExpr(V, R, Scope, SE, Params);
651
50
}
652
653
ParameterSetTy getParamsInAffineExpr(const Region *R, Loop *Scope,
654
10.7k
                                     const SCEV *Expr, ScalarEvolution &SE) {
655
10.7k
  if (isa<SCEVCouldNotCompute>(Expr))
656
0
    return ParameterSetTy();
657
10.7k
658
10.7k
  InvariantLoadsSetTy ILS;
659
10.7k
  SCEVValidator Validator(R, Scope, SE, &ILS);
660
10.7k
  ValidatorResult Result = Validator.visit(Expr);
661
10.7k
  assert(Result.isValid() && "Requested parameters for an invalid SCEV!");
662
10.7k
663
10.7k
  return Result.getParameters();
664
10.7k
}
665
666
std::pair<const SCEVConstant *, const SCEV *>
667
16.8k
extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
668
16.8k
  auto *ConstPart = cast<SCEVConstant>(SE.getConstant(S->getType(), 1));
669
16.8k
670
16.8k
  if (auto *Constant = dyn_cast<SCEVConstant>(S))
671
7.65k
    return std::make_pair(Constant, SE.getConstant(S->getType(), 1));
672
16.8k
673
9.21k
  auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
674
9.21k
  if (
AddRec9.21k
)
{3.87k
675
3.87k
    auto *StartExpr = AddRec->getStart();
676
3.87k
    if (
StartExpr->isZero()3.87k
)
{2.87k
677
2.87k
      auto StepPair = extractConstantFactor(AddRec->getStepRecurrence(SE), SE);
678
2.87k
      auto *LeftOverAddRec =
679
2.87k
          SE.getAddRecExpr(StartExpr, StepPair.second, AddRec->getLoop(),
680
2.87k
                           AddRec->getNoWrapFlags());
681
2.87k
      return std::make_pair(StepPair.first, LeftOverAddRec);
682
2.87k
    }
683
996
    return std::make_pair(ConstPart, S);
684
3.87k
  }
685
9.21k
686
5.34k
  
if (auto *5.34k
Add5.34k
= dyn_cast<SCEVAddExpr>(S))
{234
687
234
    SmallVector<const SCEV *, 4> LeftOvers;
688
234
    auto Op0Pair = extractConstantFactor(Add->getOperand(0), SE);
689
234
    auto *Factor = Op0Pair.first;
690
234
    if (
SE.isKnownNegative(Factor)234
)
{80
691
80
      Factor = cast<SCEVConstant>(SE.getNegativeSCEV(Factor));
692
80
      LeftOvers.push_back(SE.getNegativeSCEV(Op0Pair.second));
693
154
    } else {
694
154
      LeftOvers.push_back(Op0Pair.second);
695
154
    }
696
234
697
345
    for (unsigned u = 1, e = Add->getNumOperands(); 
u < e345
;
u++111
)
{235
698
235
      auto OpUPair = extractConstantFactor(Add->getOperand(u), SE);
699
235
      // TODO: Use something smarter than equality here, e.g., gcd.
700
235
      if (Factor == OpUPair.first)
701
105
        LeftOvers.push_back(OpUPair.second);
702
130
      else 
if (130
Factor == SE.getNegativeSCEV(OpUPair.first)130
)
703
6
        LeftOvers.push_back(SE.getNegativeSCEV(OpUPair.second));
704
130
      else
705
124
        return std::make_pair(ConstPart, S);
706
235
    }
707
234
708
110
    auto *NewAdd = SE.getAddExpr(LeftOvers, Add->getNoWrapFlags());
709
110
    return std::make_pair(Factor, NewAdd);
710
234
  }
711
5.34k
712
5.10k
  auto *Mul = dyn_cast<SCEVMulExpr>(S);
713
5.10k
  if (!Mul)
714
4.58k
    return std::make_pair(ConstPart, S);
715
5.10k
716
528
  SmallVector<const SCEV *, 4> LeftOvers;
717
528
  for (auto *Op : Mul->operands())
718
1.10k
    
if (1.10k
isa<SCEVConstant>(Op)1.10k
)
719
462
      ConstPart = cast<SCEVConstant>(SE.getMulExpr(ConstPart, Op));
720
1.10k
    else
721
644
      LeftOvers.push_back(Op);
722
528
723
528
  return std::make_pair(ConstPart, SE.getMulExpr(LeftOvers));
724
5.10k
}
725
} // namespace polly