Coverage Report

Created: 2017-04-28 04:32

/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
5.07k
  ValidatorResult(const ValidatorResult &Source) {
48
5.07k
    Type = Source.Type;
49
5.07k
    Parameters = Source.Parameters;
50
5.07k
  }
51
52
  /// Construct a result with a certain type and no parameters.
53
99.6k
  ValidatorResult(SCEVType::TYPE Type) : Type(Type) {
54
99.6k
    assert(Type != SCEVType::PARAM && "Did you forget to pass the parameter");
55
99.6k
  }
56
57
  /// Construct a result with a certain type and a single parameter.
58
14.7k
  ValidatorResult(SCEVType::TYPE Type, const SCEV *Expr) : Type(Type) {
59
14.7k
    Parameters.insert(Expr);
60
14.7k
  }
61
62
  /// Get the type of the ValidatorResult.
63
522
  SCEVType::TYPE getType() { return Type; }
64
65
  /// Is the analyzed SCEV constant during the execution of the SCoP.
66
104
  bool isConstant() 
{ return Type == SCEVType::INT || 104
Type == SCEVType::PARAM85
; }
67
68
  /// Is the analyzed SCEV valid.
69
97.3k
  bool isValid() { return Type != SCEVType::INVALID; }
70
71
  /// Is the analyzed SCEV of Type IV.
72
3.13k
  bool isIV() { return Type == SCEVType::IV; }
73
74
  /// Is the analyzed SCEV of Type INT.
75
33.4k
  bool isINT() { return Type == SCEVType::INT; }
76
77
  /// Is the analyzed SCEV of Type PARAM.
78
11.2k
  bool isPARAM() { return Type == SCEVType::PARAM; }
79
80
  /// Get the parameters of this validator result.
81
9.75k
  const ParameterSetTy &getParameters() { return Parameters; }
82
83
  /// Add the parameters of Source to this result.
84
33.7k
  void addParamsFrom(const ValidatorResult &Source) {
85
33.7k
    Parameters.insert(Source.Parameters.begin(), Source.Parameters.end());
86
33.7k
  }
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
11.0k
  void merge(const ValidatorResult &ToMerge) {
93
11.0k
    Type = std::max(Type, ToMerge.Type);
94
11.0k
    addParamsFrom(ToMerge);
95
11.0k
  }
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
/// Check if a SCEV is valid in a SCoP.
121
struct SCEVValidator
122
    : public SCEVVisitor<SCEVValidator, class ValidatorResult> {
123
private:
124
  const Region *R;
125
  Loop *Scope;
126
  ScalarEvolution &SE;
127
  InvariantLoadsSetTy *ILS;
128
129
public:
130
  SCEVValidator(const Region *R, Loop *Scope, ScalarEvolution &SE,
131
                InvariantLoadsSetTy *ILS)
132
49.3k
      : R(R), Scope(Scope), SE(SE), ILS(ILS) {}
133
134
69.1k
  class ValidatorResult visitConstant(const SCEVConstant *Constant) {
135
69.1k
    return ValidatorResult(SCEVType::INT);
136
69.1k
  }
137
138
  class ValidatorResult visitZeroExtendOrTruncateExpr(const SCEV *Expr,
139
522
                                                      const SCEV *Operand) {
140
522
    ValidatorResult Op = visit(Operand);
141
522
    auto Type = Op.getType();
142
522
143
522
    // If unsigned operations are allowed return the operand, otherwise
144
522
    // check if we can model the expression without unsigned assumptions.
145
522
    if (
PollyAllowUnsignedOperations || 522
Type == SCEVType::INVALID0
)
146
522
      return Op;
147
522
148
0
    
if (0
Type == SCEVType::IV0
)
149
0
      return ValidatorResult(SCEVType::INVALID);
150
0
    return ValidatorResult(SCEVType::PARAM, Expr);
151
0
  }
152
153
142
  class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
154
142
    return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
155
142
  }
156
157
380
  class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
158
380
    return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
159
380
  }
160
161
2.00k
  class ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
162
2.00k
    return visit(Expr->getOperand());
163
2.00k
  }
164
165
2.72k
  class ValidatorResult visitAddExpr(const SCEVAddExpr *Expr) {
166
2.72k
    ValidatorResult Return(SCEVType::INT);
167
2.72k
168
8.23k
    for (int i = 0, e = Expr->getNumOperands(); 
i < e8.23k
;
++i5.50k
)
{5.55k
169
5.55k
      ValidatorResult Op = visit(Expr->getOperand(i));
170
5.55k
      Return.merge(Op);
171
5.55k
172
5.55k
      // Early exit.
173
5.55k
      if (!Return.isValid())
174
52
        break;
175
5.55k
    }
176
2.72k
177
2.72k
    return Return;
178
2.72k
  }
179
180
3.15k
  class ValidatorResult visitMulExpr(const SCEVMulExpr *Expr) {
181
3.15k
    ValidatorResult Return(SCEVType::INT);
182
3.15k
183
3.15k
    bool HasMultipleParams = false;
184
3.15k
185
10.3k
    for (int i = 0, e = Expr->getNumOperands(); 
i < e10.3k
;
++i7.20k
)
{7.23k
186
7.23k
      ValidatorResult Op = visit(Expr->getOperand(i));
187
7.23k
188
7.23k
      if (Op.isINT())
189
2.91k
        continue;
190
7.23k
191
4.32k
      
if (4.32k
Op.isPARAM() && 4.32k
Return.isPARAM()4.01k
)
{1.18k
192
1.18k
        HasMultipleParams = true;
193
1.18k
        continue;
194
1.18k
      }
195
4.32k
196
3.13k
      
if (3.13k
(Op.isIV() || 3.13k
Op.isPARAM()2.94k
) &&
!Return.isINT()3.02k
)
{31
197
31
        DEBUG(dbgs() << "INVALID: More than one non-int operand in MulExpr\n"
198
31
                     << "\tExpr: " << *Expr << "\n"
199
31
                     << "\tPrevious expression type: " << Return << "\n"
200
31
                     << "\tNext operand (" << Op
201
31
                     << "): " << *Expr->getOperand(i) << "\n");
202
31
203
31
        return ValidatorResult(SCEVType::INVALID);
204
31
      }
205
3.13k
206
3.10k
      Return.merge(Op);
207
3.10k
    }
208
3.15k
209
3.12k
    
if (3.12k
HasMultipleParams && 3.12k
Return.isValid()946
)
210
946
      return ValidatorResult(SCEVType::PARAM, Expr);
211
3.12k
212
2.17k
    return Return;
213
3.12k
  }
214
215
24.9k
  class ValidatorResult visitAddRecExpr(const SCEVAddRecExpr *Expr) {
216
24.9k
    if (
!Expr->isAffine()24.9k
)
{82
217
82
      DEBUG(dbgs() << "INVALID: AddRec is not affine");
218
82
      return ValidatorResult(SCEVType::INVALID);
219
82
    }
220
24.9k
221
24.8k
    ValidatorResult Start = visit(Expr->getStart());
222
24.8k
    ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE));
223
24.8k
224
24.8k
    if (!Start.isValid())
225
1.08k
      return Start;
226
24.8k
227
23.8k
    
if (23.8k
!Recurrence.isValid()23.8k
)
228
0
      return Recurrence;
229
23.8k
230
23.8k
    auto *L = Expr->getLoop();
231
23.8k
    if (
R->contains(L) && 23.8k
(!Scope || 23.2k
!L->contains(Scope)23.2k
))
{21
232
21
      DEBUG(dbgs() << "INVALID: Loop of AddRec expression boxed in an a "
233
21
                      "non-affine subregion or has a non-synthesizable exit "
234
21
                      "value.");
235
21
      return ValidatorResult(SCEVType::INVALID);
236
21
    }
237
23.8k
238
23.7k
    
if (23.7k
R->contains(L)23.7k
)
{23.1k
239
23.1k
      if (
Recurrence.isINT()23.1k
)
{22.5k
240
22.5k
        ValidatorResult Result(SCEVType::IV);
241
22.5k
        Result.addParamsFrom(Start);
242
22.5k
        return Result;
243
22.5k
      }
244
23.1k
245
667
      
DEBUG667
(dbgs() << "INVALID: AddRec within scop has non-int"667
246
667
                      "recurrence part");
247
667
      return ValidatorResult(SCEVType::INVALID);
248
23.1k
    }
249
23.7k
250
590
    assert(Recurrence.isConstant() && "Expected 'Recurrence' to be constant");
251
590
252
590
    // Directly generate ValidatorResult for Expr if 'start' is zero.
253
590
    if (Expr->getStart()->isZero())
254
466
      return ValidatorResult(SCEVType::PARAM, Expr);
255
590
256
590
    // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}'
257
590
    // if 'start' is not zero.
258
124
    const SCEV *ZeroStartExpr = SE.getAddRecExpr(
259
124
        SE.getConstant(Expr->getStart()->getType(), 0),
260
124
        Expr->getStepRecurrence(SE), Expr->getLoop(), Expr->getNoWrapFlags());
261
124
262
124
    ValidatorResult ZeroStartResult =
263
124
        ValidatorResult(SCEVType::PARAM, ZeroStartExpr);
264
124
    ZeroStartResult.addParamsFrom(Start);
265
124
266
124
    return ZeroStartResult;
267
590
  }
268
269
1.16k
  class ValidatorResult visitSMaxExpr(const SCEVSMaxExpr *Expr) {
270
1.16k
    ValidatorResult Return(SCEVType::INT);
271
1.16k
272
3.57k
    for (int i = 0, e = Expr->getNumOperands(); 
i < e3.57k
;
++i2.41k
)
{2.41k
273
2.41k
      ValidatorResult Op = visit(Expr->getOperand(i));
274
2.41k
275
2.41k
      if (!Op.isValid())
276
0
        return Op;
277
2.41k
278
2.41k
      Return.merge(Op);
279
2.41k
    }
280
1.16k
281
1.16k
    return Return;
282
1.16k
  }
283
284
6
  class ValidatorResult visitUMaxExpr(const SCEVUMaxExpr *Expr) {
285
6
    // We do not support unsigned max operations. If 'Expr' is constant during
286
6
    // Scop execution we treat this as a parameter, otherwise we bail out.
287
18
    for (int i = 0, e = Expr->getNumOperands(); 
i < e18
;
++i12
)
{12
288
12
      ValidatorResult Op = visit(Expr->getOperand(i));
289
12
290
12
      if (
!Op.isConstant()12
)
{0
291
0
        DEBUG(dbgs() << "INVALID: UMaxExpr has a non-constant operand");
292
0
        return ValidatorResult(SCEVType::INVALID);
293
0
      }
294
12
    }
295
6
296
6
    return ValidatorResult(SCEVType::PARAM, Expr);
297
6
  }
298
299
1.79k
  ValidatorResult visitGenericInst(Instruction *I, const SCEV *S) {
300
1.79k
    if (
R->contains(I)1.79k
)
{97
301
97
      DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
302
97
                      "within the region\n");
303
97
      return ValidatorResult(SCEVType::INVALID);
304
97
    }
305
1.79k
306
1.69k
    return ValidatorResult(SCEVType::PARAM, S);
307
1.79k
  }
308
309
4.29k
  ValidatorResult visitLoadInstruction(Instruction *I, const SCEV *S) {
310
4.29k
    if (
R->contains(I) && 4.29k
ILS2.67k
)
{2.67k
311
2.67k
      ILS->insert(cast<LoadInst>(I));
312
2.67k
      return ValidatorResult(SCEVType::PARAM, S);
313
2.67k
    }
314
4.29k
315
1.62k
    return visitGenericInst(I, S);
316
4.29k
  }
317
318
  ValidatorResult visitDivision(const SCEV *Dividend, const SCEV *Divisor,
319
                                const SCEV *DivExpr,
320
338
                                Instruction *SDiv = nullptr) {
321
338
322
338
    // First check if we might be able to model the division, thus if the
323
338
    // divisor is constant. If so, check the dividend, otherwise check if
324
338
    // the whole division can be seen as a parameter.
325
338
    if (
isa<SCEVConstant>(Divisor) && 338
!Divisor->isZero()287
)
326
284
      return visit(Dividend);
327
338
328
338
    // For signed divisions use the SDiv instruction to check for a parameter
329
338
    // division, for unsigned divisions check the operands.
330
54
    
if (54
SDiv54
)
331
8
      return visitGenericInst(SDiv, DivExpr);
332
54
333
46
    ValidatorResult LHS = visit(Dividend);
334
46
    ValidatorResult RHS = visit(Divisor);
335
46
    if (
LHS.isConstant() && 46
RHS.isConstant()46
)
336
46
      return ValidatorResult(SCEVType::PARAM, DivExpr);
337
46
338
0
    
DEBUG0
(dbgs() << "INVALID: unsigned division of non-constant expressions");0
339
0
    return ValidatorResult(SCEVType::INVALID);
340
46
  }
341
342
130
  ValidatorResult visitUDivExpr(const SCEVUDivExpr *Expr) {
343
130
    if (!PollyAllowUnsignedOperations)
344
0
      return ValidatorResult(SCEVType::INVALID);
345
130
346
130
    auto *Dividend = Expr->getLHS();
347
130
    auto *Divisor = Expr->getRHS();
348
130
    return visitDivision(Dividend, Divisor, Expr);
349
130
  }
350
351
208
  ValidatorResult visitSDivInstruction(Instruction *SDiv, const SCEV *Expr) {
352
208
    assert(SDiv->getOpcode() == Instruction::SDiv &&
353
208
           "Assumed SDiv instruction!");
354
208
355
208
    auto *Dividend = SE.getSCEV(SDiv->getOperand(0));
356
208
    auto *Divisor = SE.getSCEV(SDiv->getOperand(1));
357
208
    return visitDivision(Dividend, Divisor, Expr, SDiv);
358
208
  }
359
360
212
  ValidatorResult visitSRemInstruction(Instruction *SRem, const SCEV *S) {
361
212
    assert(SRem->getOpcode() == Instruction::SRem &&
362
212
           "Assumed SRem instruction!");
363
212
364
212
    auto *Divisor = SRem->getOperand(1);
365
212
    auto *CI = dyn_cast<ConstantInt>(Divisor);
366
212
    if (
!CI || 212
CI->isZeroValue()209
)
367
3
      return visitGenericInst(SRem, S);
368
212
369
209
    auto *Dividend = SRem->getOperand(0);
370
209
    auto *DividendSCEV = SE.getSCEV(Dividend);
371
209
    return visit(DividendSCEV);
372
212
  }
373
374
13.7k
  ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
375
13.7k
    Value *V = Expr->getValue();
376
13.7k
377
13.7k
    if (
!Expr->getType()->isIntegerTy() && 13.7k
!Expr->getType()->isPointerTy()211
)
{0
378
0
      DEBUG(dbgs() << "INVALID: UnknownExpr is not an integer or pointer");
379
0
      return ValidatorResult(SCEVType::INVALID);
380
0
    }
381
13.7k
382
13.7k
    
if (13.7k
isa<UndefValue>(V)13.7k
)
{30
383
30
      DEBUG(dbgs() << "INVALID: UnknownExpr references an undef value");
384
30
      return ValidatorResult(SCEVType::INVALID);
385
30
    }
386
13.7k
387
13.7k
    
if (Instruction *13.7k
I13.7k
= dyn_cast<Instruction>(Expr->getValue()))
{4.96k
388
4.96k
      switch (I->getOpcode()) {
389
28
      case Instruction::IntToPtr:
390
28
        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
391
63
      case Instruction::PtrToInt:
392
63
        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
393
4.29k
      case Instruction::Load:
394
4.29k
        return visitLoadInstruction(I, Expr);
395
208
      case Instruction::SDiv:
396
208
        return visitSDivInstruction(I, Expr);
397
212
      case Instruction::SRem:
398
212
        return visitSRemInstruction(I, Expr);
399
158
      default:
400
158
        return visitGenericInst(I, Expr);
401
4.96k
      }
402
4.96k
    }
403
13.7k
404
8.75k
    return ValidatorResult(SCEVType::PARAM, Expr);
405
13.7k
  }
406
};
407
408
/// Check whether a SCEV refers to an SSA name defined inside a region.
409
class SCEVInRegionDependences {
410
  const Region *R;
411
  Loop *Scope;
412
  bool AllowLoops;
413
  bool HasInRegionDeps = false;
414
415
public:
416
  SCEVInRegionDependences(const Region *R, Loop *Scope, bool AllowLoops)
417
18.9k
      : R(R), Scope(Scope), AllowLoops(AllowLoops) {}
418
419
53.1k
  bool follow(const SCEV *S) {
420
53.1k
    if (auto 
Unknown53.1k
= dyn_cast<SCEVUnknown>(S))
{14.4k
421
14.4k
      Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
422
14.4k
423
14.4k
      // Return true when Inst is defined inside the region R.
424
14.4k
      if (
!Inst || 14.4k
!R->contains(Inst)6.80k
)
425
9.48k
        return true;
426
14.4k
427
4.99k
      HasInRegionDeps = true;
428
4.99k
      return false;
429
14.4k
    }
430
53.1k
431
38.6k
    
if (auto 38.6k
AddRec38.6k
= dyn_cast<SCEVAddRecExpr>(S))
{11.0k
432
11.0k
      if (AllowLoops)
433
0
        return true;
434
11.0k
435
11.0k
      
if (11.0k
!Scope11.0k
)
{12
436
12
        HasInRegionDeps = true;
437
12
        return false;
438
12
      }
439
11.0k
      auto *L = AddRec->getLoop();
440
11.0k
      if (
R->contains(L) && 11.0k
!L->contains(Scope)10.8k
)
{0
441
0
        HasInRegionDeps = true;
442
0
        return false;
443
0
      }
444
11.0k
    }
445
38.6k
446
38.6k
    return true;
447
38.6k
  }
448
48.1k
  bool isDone() { return false; }
449
18.9k
  bool hasDependences() { return HasInRegionDeps; }
450
};
451
452
namespace polly {
453
/// Find all loops referenced in SCEVAddRecExprs.
454
class SCEVFindLoops {
455
  SetVector<const Loop *> &Loops;
456
457
public:
458
13.2k
  SCEVFindLoops(SetVector<const Loop *> &Loops) : Loops(Loops) {}
459
460
34.4k
  bool follow(const SCEV *S) {
461
34.4k
    if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S))
462
7.97k
      Loops.insert(AddRec->getLoop());
463
34.4k
    return true;
464
34.4k
  }
465
34.4k
  bool isDone() { return false; }
466
};
467
468
13.2k
void findLoops(const SCEV *Expr, SetVector<const Loop *> &Loops) {
469
13.2k
  SCEVFindLoops FindLoops(Loops);
470
13.2k
  SCEVTraversal<SCEVFindLoops> ST(FindLoops);
471
13.2k
  ST.visitAll(Expr);
472
13.2k
}
473
474
/// Find all values referenced in SCEVUnknowns.
475
class SCEVFindValues {
476
  ScalarEvolution &SE;
477
  SetVector<Value *> &Values;
478
479
public:
480
  SCEVFindValues(ScalarEvolution &SE, SetVector<Value *> &Values)
481
15.5k
      : SE(SE), Values(Values) {}
482
483
36.9k
  bool follow(const SCEV *S) {
484
36.9k
    const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S);
485
36.9k
    if (!Unknown)
486
31.2k
      return true;
487
36.9k
488
5.68k
    Values.insert(Unknown->getValue());
489
5.68k
    Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
490
5.68k
    if (
!Inst || 5.68k
(Inst->getOpcode() != Instruction::SRem &&2.67k
491
2.63k
                  Inst->getOpcode() != Instruction::SDiv))
492
5.59k
      return false;
493
5.68k
494
83
    auto *Dividend = SE.getSCEV(Inst->getOperand(1));
495
83
    if (!isa<SCEVConstant>(Dividend))
496
2
      return false;
497
83
498
81
    auto *Divisor = SE.getSCEV(Inst->getOperand(0));
499
81
    SCEVFindValues FindValues(SE, Values);
500
81
    SCEVTraversal<SCEVFindValues> ST(FindValues);
501
81
    ST.visitAll(Dividend);
502
81
    ST.visitAll(Divisor);
503
81
504
81
    return false;
505
83
  }
506
31.2k
  bool isDone() { return false; }
507
};
508
509
void findValues(const SCEV *Expr, ScalarEvolution &SE,
510
15.4k
                SetVector<Value *> &Values) {
511
15.4k
  SCEVFindValues FindValues(SE, Values);
512
15.4k
  SCEVTraversal<SCEVFindValues> ST(FindValues);
513
15.4k
  ST.visitAll(Expr);
514
15.4k
}
515
516
bool hasScalarDepsInsideRegion(const SCEV *Expr, const Region *R,
517
18.9k
                               llvm::Loop *Scope, bool AllowLoops) {
518
18.9k
  SCEVInRegionDependences InRegionDeps(R, Scope, AllowLoops);
519
18.9k
  SCEVTraversal<SCEVInRegionDependences> ST(InRegionDeps);
520
18.9k
  ST.visitAll(Expr);
521
18.9k
  return InRegionDeps.hasDependences();
522
18.9k
}
523
524
bool isAffineExpr(const Region *R, llvm::Loop *Scope, const SCEV *Expr,
525
39.6k
                  ScalarEvolution &SE, InvariantLoadsSetTy *ILS) {
526
39.6k
  if (isa<SCEVCouldNotCompute>(Expr))
527
0
    return false;
528
39.6k
529
39.6k
  SCEVValidator Validator(R, Scope, SE, ILS);
530
39.6k
  DEBUG({
531
39.6k
    dbgs() << "\n";
532
39.6k
    dbgs() << "Expr: " << *Expr << "\n";
533
39.6k
    dbgs() << "Region: " << R->getNameStr() << "\n";
534
39.6k
    dbgs() << " -> ";
535
39.6k
  });
536
39.6k
537
39.6k
  ValidatorResult Result = Validator.visit(Expr);
538
39.6k
539
39.6k
  DEBUG({
540
39.6k
    if (Result.isValid())
541
39.6k
      dbgs() << "VALID\n";
542
39.6k
    dbgs() << "\n";
543
39.6k
  });
544
39.6k
545
39.6k
  return Result.isValid();
546
39.6k
}
547
548
static bool isAffineExpr(Value *V, const Region *R, Loop *Scope,
549
50
                         ScalarEvolution &SE, ParameterSetTy &Params) {
550
50
  auto *E = SE.getSCEV(V);
551
50
  if (isa<SCEVCouldNotCompute>(E))
552
0
    return false;
553
50
554
50
  SCEVValidator Validator(R, Scope, SE, nullptr);
555
50
  ValidatorResult Result = Validator.visit(E);
556
50
  if (!Result.isValid())
557
0
    return false;
558
50
559
50
  auto ResultParams = Result.getParameters();
560
50
  Params.insert(ResultParams.begin(), ResultParams.end());
561
50
562
50
  return true;
563
50
}
564
565
bool isAffineConstraint(Value *V, const Region *R, llvm::Loop *Scope,
566
                        ScalarEvolution &SE, ParameterSetTy &Params,
567
81
                        bool OrExpr) {
568
81
  if (auto *
ICmp81
= dyn_cast<ICmpInst>(V))
{25
569
25
    return isAffineConstraint(ICmp->getOperand(0), R, Scope, SE, Params,
570
25
                              true) &&
571
25
           isAffineConstraint(ICmp->getOperand(1), R, Scope, SE, Params, true);
572
56
  } else 
if (auto *56
BinOp56
= dyn_cast<BinaryOperator>(V))
{10
573
10
    auto Opcode = BinOp->getOpcode();
574
10
    if (
Opcode == Instruction::And || 10
Opcode == Instruction::Or4
)
575
6
      return isAffineConstraint(BinOp->getOperand(0), R, Scope, SE, Params,
576
6
                                false) &&
577
6
             isAffineConstraint(BinOp->getOperand(1), R, Scope, SE, Params,
578
6
                                false);
579
10
    /* Fall through */
580
10
  }
581
81
582
50
  
if (50
!OrExpr50
)
583
0
    return false;
584
50
585
50
  return isAffineExpr(V, R, Scope, SE, Params);
586
50
}
587
588
ParameterSetTy getParamsInAffineExpr(const Region *R, Loop *Scope,
589
9.70k
                                     const SCEV *Expr, ScalarEvolution &SE) {
590
9.70k
  if (isa<SCEVCouldNotCompute>(Expr))
591
0
    return ParameterSetTy();
592
9.70k
593
9.70k
  InvariantLoadsSetTy ILS;
594
9.70k
  SCEVValidator Validator(R, Scope, SE, &ILS);
595
9.70k
  ValidatorResult Result = Validator.visit(Expr);
596
9.70k
  assert(Result.isValid() && "Requested parameters for an invalid SCEV!");
597
9.70k
598
9.70k
  return Result.getParameters();
599
9.70k
}
600
601
std::pair<const SCEVConstant *, const SCEV *>
602
15.2k
extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
603
15.2k
  auto *ConstPart = cast<SCEVConstant>(SE.getConstant(S->getType(), 1));
604
15.2k
605
15.2k
  if (auto *Constant = dyn_cast<SCEVConstant>(S))
606
6.97k
    return std::make_pair(Constant, SE.getConstant(S->getType(), 1));
607
15.2k
608
8.23k
  auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
609
8.23k
  if (
AddRec8.23k
)
{3.57k
610
3.57k
    auto *StartExpr = AddRec->getStart();
611
3.57k
    if (
StartExpr->isZero()3.57k
)
{2.66k
612
2.66k
      auto StepPair = extractConstantFactor(AddRec->getStepRecurrence(SE), SE);
613
2.66k
      auto *LeftOverAddRec =
614
2.66k
          SE.getAddRecExpr(StartExpr, StepPair.second, AddRec->getLoop(),
615
2.66k
                           AddRec->getNoWrapFlags());
616
2.66k
      return std::make_pair(StepPair.first, LeftOverAddRec);
617
2.66k
    }
618
909
    return std::make_pair(ConstPart, S);
619
3.57k
  }
620
8.23k
621
4.66k
  
if (auto *4.66k
Add4.66k
= dyn_cast<SCEVAddExpr>(S))
{210
622
210
    SmallVector<const SCEV *, 4> LeftOvers;
623
210
    auto Op0Pair = extractConstantFactor(Add->getOperand(0), SE);
624
210
    auto *Factor = Op0Pair.first;
625
210
    if (
SE.isKnownNegative(Factor)210
)
{69
626
69
      Factor = cast<SCEVConstant>(SE.getNegativeSCEV(Factor));
627
69
      LeftOvers.push_back(SE.getNegativeSCEV(Op0Pair.second));
628
141
    } else {
629
141
      LeftOvers.push_back(Op0Pair.second);
630
141
    }
631
210
632
311
    for (unsigned u = 1, e = Add->getNumOperands(); 
u < e311
;
u++101
)
{211
633
211
      auto OpUPair = extractConstantFactor(Add->getOperand(u), SE);
634
211
      // TODO: Use something smarter than equality here, e.g., gcd.
635
211
      if (Factor == OpUPair.first)
636
95
        LeftOvers.push_back(OpUPair.second);
637
116
      else 
if (116
Factor == SE.getNegativeSCEV(OpUPair.first)116
)
638
6
        LeftOvers.push_back(SE.getNegativeSCEV(OpUPair.second));
639
116
      else
640
110
        return std::make_pair(ConstPart, S);
641
211
    }
642
210
643
100
    auto *NewAdd = SE.getAddExpr(LeftOvers, Add->getNoWrapFlags());
644
100
    return std::make_pair(Factor, NewAdd);
645
210
  }
646
4.66k
647
4.45k
  auto *Mul = dyn_cast<SCEVMulExpr>(S);
648
4.45k
  if (!Mul)
649
4.02k
    return std::make_pair(ConstPart, S);
650
4.45k
651
427
  SmallVector<const SCEV *, 4> LeftOvers;
652
427
  for (auto *Op : Mul->operands())
653
904
    
if (904
isa<SCEVConstant>(Op)904
)
654
361
      ConstPart = cast<SCEVConstant>(SE.getMulExpr(ConstPart, Op));
655
904
    else
656
543
      LeftOvers.push_back(Op);
657
427
658
427
  return std::make_pair(ConstPart, SE.getMulExpr(LeftOvers));
659
4.45k
}
660
} // namespace polly