Coverage Report

Created: 2017-10-03 07: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
6.67k
  ValidatorResult(const ValidatorResult &Source) {
48
6.67k
    Type = Source.Type;
49
6.67k
    Parameters = Source.Parameters;
50
6.67k
  }
51
52
  /// Construct a result with a certain type and no parameters.
53
117k
  ValidatorResult(SCEVType::TYPE Type) : Type(Type) {
54
117k
    assert(Type != SCEVType::PARAM && "Did you forget to pass the parameter");
55
117k
  }
56
57
  /// Construct a result with a certain type and a single parameter.
58
17.4k
  ValidatorResult(SCEVType::TYPE Type, const SCEV *Expr) : Type(Type) {
59
17.4k
    Parameters.insert(Expr);
60
17.4k
  }
61
62
  /// Get the type of the ValidatorResult.
63
1.03k
  SCEVType::TYPE getType() { return Type; }
64
65
  /// Is the analyzed SCEV constant during the execution of the SCoP.
66
170
  bool isConstant() 
{ return Type == SCEVType::INT || 170
Type == SCEVType::PARAM118
; }
67
68
  /// Is the analyzed SCEV valid.
69
113k
  bool isValid() { return Type != SCEVType::INVALID; }
70
71
  /// Is the analyzed SCEV of Type IV.
72
4.21k
  bool isIV() { return Type == SCEVType::IV; }
73
74
  /// Is the analyzed SCEV of Type INT.
75
40.5k
  bool isINT() { return Type == SCEVType::INT; }
76
77
  /// Is the analyzed SCEV of Type PARAM.
78
14.4k
  bool isPARAM() { return Type == SCEVType::PARAM; }
79
80
  /// Get the parameters of this validator result.
81
12.0k
  const ParameterSetTy &getParameters() { return Parameters; }
82
83
  /// Add the parameters of Source to this result.
84
39.3k
  void addParamsFrom(const ValidatorResult &Source) {
85
39.3k
    Parameters.insert(Source.Parameters.begin(), Source.Parameters.end());
86
39.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.8k
  void merge(const ValidatorResult &ToMerge) {
93
12.8k
    Type = std::max(Type, ToMerge.Type);
94
12.8k
    addParamsFrom(ToMerge);
95
12.8k
  }
96
97
0
  void print(raw_ostream &OS) {
98
0
    switch (Type) {
99
0
    case SCEVType::INT:
100
0
      OS << "SCEVType::INT";
101
0
      break;
102
0
    case SCEVType::PARAM:
103
0
      OS << "SCEVType::PARAM";
104
0
      break;
105
0
    case SCEVType::IV:
106
0
      OS << "SCEVType::IV";
107
0
      break;
108
0
    case SCEVType::INVALID:
109
0
      OS << "SCEVType::INVALID";
110
0
      break;
111
0
    }
112
0
  }
113
};
114
115
0
raw_ostream &operator<<(raw_ostream &OS, class ValidatorResult &VR) {
116
0
  VR.print(OS);
117
0
  return OS;
118
0
}
119
120
213
bool polly::isConstCall(llvm::CallInst *Call) {
121
213
  if (Call->mayReadOrWriteMemory())
122
93
    return false;
123
120
124
120
  for (auto &Operand : Call->arg_operands())
125
114
    
if (114
!isa<ConstantInt>(&Operand)114
)
126
46
      return false;
127
74
128
74
  return true;
129
74
}
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
58.7k
      : R(R), Scope(Scope), SE(SE), ILS(ILS) {}
144
145
81.4k
  class ValidatorResult visitConstant(const SCEVConstant *Constant) {
146
81.4k
    return ValidatorResult(SCEVType::INT);
147
81.4k
  }
148
149
  class ValidatorResult visitZeroExtendOrTruncateExpr(const SCEV *Expr,
150
1.03k
                                                      const SCEV *Operand) {
151
1.03k
    ValidatorResult Op = visit(Operand);
152
1.03k
    auto Type = Op.getType();
153
1.03k
154
1.03k
    // If unsigned operations are allowed return the operand, otherwise
155
1.03k
    // check if we can model the expression without unsigned assumptions.
156
1.03k
    if (
PollyAllowUnsignedOperations || 1.03k
Type == SCEVType::INVALID0
)
157
1.03k
      return Op;
158
0
159
0
    
if (0
Type == SCEVType::IV0
)
160
0
      return ValidatorResult(SCEVType::INVALID);
161
0
    return ValidatorResult(SCEVType::PARAM, Expr);
162
0
  }
163
164
274
  class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
165
274
    return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
166
274
  }
167
168
757
  class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
169
757
    return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
170
757
  }
171
172
2.68k
  class ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
173
2.68k
    return visit(Expr->getOperand());
174
2.68k
  }
175
176
3.01k
  class ValidatorResult visitAddExpr(const SCEVAddExpr *Expr) {
177
3.01k
    ValidatorResult Return(SCEVType::INT);
178
3.01k
179
9.19k
    for (int i = 0, e = Expr->getNumOperands(); 
i < e9.19k
;
++i6.17k
) {
180
6.24k
      ValidatorResult Op = visit(Expr->getOperand(i));
181
6.24k
      Return.merge(Op);
182
6.24k
183
6.24k
      // Early exit.
184
6.24k
      if (!Return.isValid())
185
69
        break;
186
6.24k
    }
187
3.01k
188
3.01k
    return Return;
189
3.01k
  }
190
191
4.20k
  class ValidatorResult visitMulExpr(const SCEVMulExpr *Expr) {
192
4.20k
    ValidatorResult Return(SCEVType::INT);
193
4.20k
194
4.20k
    bool HasMultipleParams = false;
195
4.20k
196
13.5k
    for (int i = 0, e = Expr->getNumOperands(); 
i < e13.5k
;
++i9.31k
) {
197
9.37k
      ValidatorResult Op = visit(Expr->getOperand(i));
198
9.37k
199
9.37k
      if (Op.isINT())
200
3.96k
        continue;
201
5.41k
202
5.41k
      
if (5.41k
Op.isPARAM() && 5.41k
Return.isPARAM()5.01k
) {
203
1.19k
        HasMultipleParams = true;
204
1.19k
        continue;
205
1.19k
      }
206
4.21k
207
4.21k
      
if (4.21k
(Op.isIV() || 4.21k
Op.isPARAM()3.99k
) &&
!Return.isINT()4.04k
) {
208
53
        DEBUG(dbgs() << "INVALID: More than one non-int operand in MulExpr\n"
209
53
                     << "\tExpr: " << *Expr << "\n"
210
53
                     << "\tPrevious expression type: " << Return << "\n"
211
53
                     << "\tNext operand (" << Op
212
53
                     << "): " << *Expr->getOperand(i) << "\n");
213
53
214
53
        return ValidatorResult(SCEVType::INVALID);
215
53
      }
216
4.16k
217
4.16k
      Return.merge(Op);
218
4.16k
    }
219
4.20k
220
4.15k
    
if (4.15k
HasMultipleParams && 4.15k
Return.isValid()955
)
221
955
      return ValidatorResult(SCEVType::PARAM, Expr);
222
3.20k
223
3.20k
    return Return;
224
3.20k
  }
225
226
29.0k
  class ValidatorResult visitAddRecExpr(const SCEVAddRecExpr *Expr) {
227
29.0k
    if (
!Expr->isAffine()29.0k
) {
228
124
      DEBUG(dbgs() << "INVALID: AddRec is not affine");
229
124
      return ValidatorResult(SCEVType::INVALID);
230
124
    }
231
28.9k
232
28.9k
    ValidatorResult Start = visit(Expr->getStart());
233
28.9k
    ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE));
234
28.9k
235
28.9k
    if (!Start.isValid())
236
1.11k
      return Start;
237
27.8k
238
27.8k
    
if (27.8k
!Recurrence.isValid()27.8k
)
239
0
      return Recurrence;
240
27.8k
241
27.8k
    auto *L = Expr->getLoop();
242
27.8k
    if (
R->contains(L) && 27.8k
(!Scope || 27.1k
!L->contains(Scope)27.1k
)) {
243
35
      DEBUG(dbgs() << "INVALID: Loop of AddRec expression boxed in an a "
244
35
                      "non-affine subregion or has a non-synthesizable exit "
245
35
                      "value.");
246
35
      return ValidatorResult(SCEVType::INVALID);
247
35
    }
248
27.7k
249
27.7k
    
if (27.7k
R->contains(L)27.7k
) {
250
27.1k
      if (
Recurrence.isINT()27.1k
) {
251
26.3k
        ValidatorResult Result(SCEVType::IV);
252
26.3k
        Result.addParamsFrom(Start);
253
26.3k
        return Result;
254
26.3k
      }
255
720
256
720
      
DEBUG720
(dbgs() << "INVALID: AddRec within scop has non-int"
257
720
                      "recurrence part");
258
720
      return ValidatorResult(SCEVType::INVALID);
259
720
    }
260
655
261
27.7k
    assert(Recurrence.isConstant() && "Expected 'Recurrence' to be constant");
262
655
263
655
    // Directly generate ValidatorResult for Expr if 'start' is zero.
264
655
    if (Expr->getStart()->isZero())
265
493
      return ValidatorResult(SCEVType::PARAM, Expr);
266
162
267
162
    // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}'
268
162
    // if 'start' is not zero.
269
162
    const SCEV *ZeroStartExpr = SE.getAddRecExpr(
270
162
        SE.getConstant(Expr->getStart()->getType(), 0),
271
162
        Expr->getStepRecurrence(SE), Expr->getLoop(), Expr->getNoWrapFlags());
272
162
273
162
    ValidatorResult ZeroStartResult =
274
162
        ValidatorResult(SCEVType::PARAM, ZeroStartExpr);
275
162
    ZeroStartResult.addParamsFrom(Start);
276
162
277
162
    return ZeroStartResult;
278
162
  }
279
280
1.16k
  class ValidatorResult visitSMaxExpr(const SCEVSMaxExpr *Expr) {
281
1.16k
    ValidatorResult Return(SCEVType::INT);
282
1.16k
283
3.57k
    for (int i = 0, e = Expr->getNumOperands(); 
i < e3.57k
;
++i2.41k
) {
284
2.41k
      ValidatorResult Op = visit(Expr->getOperand(i));
285
2.41k
286
2.41k
      if (!Op.isValid())
287
0
        return Op;
288
2.41k
289
2.41k
      Return.merge(Op);
290
2.41k
    }
291
1.16k
292
1.16k
    return Return;
293
1.16k
  }
294
295
39
  class ValidatorResult visitUMaxExpr(const SCEVUMaxExpr *Expr) {
296
39
    // We do not support unsigned max operations. If 'Expr' is constant during
297
39
    // Scop execution we treat this as a parameter, otherwise we bail out.
298
117
    for (int i = 0, e = Expr->getNumOperands(); 
i < e117
;
++i78
) {
299
78
      ValidatorResult Op = visit(Expr->getOperand(i));
300
78
301
78
      if (
!Op.isConstant()78
) {
302
0
        DEBUG(dbgs() << "INVALID: UMaxExpr has a non-constant operand");
303
0
        return ValidatorResult(SCEVType::INVALID);
304
0
      }
305
78
    }
306
39
307
39
    return ValidatorResult(SCEVType::PARAM, Expr);
308
39
  }
309
310
2.40k
  ValidatorResult visitGenericInst(Instruction *I, const SCEV *S) {
311
2.40k
    if (
R->contains(I)2.40k
) {
312
111
      DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
313
111
                      "within the region\n");
314
111
      return ValidatorResult(SCEVType::INVALID);
315
111
    }
316
2.28k
317
2.28k
    return ValidatorResult(SCEVType::PARAM, S);
318
2.28k
  }
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
) {
324
65
      auto Call = cast<CallInst>(I);
325
65
326
65
      if (!isConstCall(Call))
327
31
        return ValidatorResult(SCEVType::INVALID, S);
328
48
    }
329
48
    return ValidatorResult(SCEVType::PARAM, S);
330
48
  }
331
332
4.99k
  ValidatorResult visitLoadInstruction(Instruction *I, const SCEV *S) {
333
4.99k
    if (
R->contains(I) && 4.99k
ILS2.83k
) {
334
2.83k
      ILS->insert(cast<LoadInst>(I));
335
2.83k
      return ValidatorResult(SCEVType::PARAM, S);
336
2.83k
    }
337
2.15k
338
2.15k
    return visitGenericInst(I, S);
339
2.15k
  }
340
341
  ValidatorResult visitDivision(const SCEV *Dividend, const SCEV *Divisor,
342
                                const SCEV *DivExpr,
343
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
54
351
54
    // For signed divisions use the SDiv instruction to check for a parameter
352
54
    // division, for unsigned divisions check the operands.
353
54
    
if (54
SDiv54
)
354
8
      return visitGenericInst(SDiv, DivExpr);
355
46
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
0
361
0
    
DEBUG0
(dbgs() << "INVALID: unsigned division of non-constant expressions");
362
0
    return ValidatorResult(SCEVType::INVALID);
363
0
  }
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
209
392
209
    auto *Dividend = SRem->getOperand(0);
393
209
    auto *DividendSCEV = SE.getSCEV(Dividend);
394
209
    return visit(DividendSCEV);
395
209
  }
396
397
16.4k
  ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
398
16.4k
    Value *V = Expr->getValue();
399
16.4k
400
16.4k
    if (
!Expr->getType()->isIntegerTy() && 16.4k
!Expr->getType()->isPointerTy()230
) {
401
0
      DEBUG(dbgs() << "INVALID: UnknownExpr is not an integer or pointer");
402
0
      return ValidatorResult(SCEVType::INVALID);
403
0
    }
404
16.4k
405
16.4k
    
if (16.4k
isa<UndefValue>(V)16.4k
) {
406
27
      DEBUG(dbgs() << "INVALID: UnknownExpr references an undef value");
407
27
      return ValidatorResult(SCEVType::INVALID);
408
27
    }
409
16.4k
410
16.4k
    
if (Instruction *16.4k
I16.4k
= dyn_cast<Instruction>(Expr->getValue())) {
411
5.90k
      switch (I->getOpcode()) {
412
30
      case Instruction::IntToPtr:
413
30
        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
414
67
      case Instruction::PtrToInt:
415
67
        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
416
4.99k
      case Instruction::Load:
417
4.99k
        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
230
      default:
425
230
        return visitGenericInst(I, Expr);
426
10.5k
      }
427
10.5k
    }
428
10.5k
429
10.5k
    return ValidatorResult(SCEVType::PARAM, Expr);
430
10.5k
  }
431
};
432
433
class SCEVHasIVParams {
434
  bool HasIVParams = false;
435
436
public:
437
11.4k
  SCEVHasIVParams() {}
438
439
25.6k
  bool follow(const SCEV *S) {
440
25.6k
    const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S);
441
25.6k
    if (!Unknown)
442
24.4k
      return true;
443
1.15k
444
1.15k
    CallInst *Call = dyn_cast<CallInst>(Unknown->getValue());
445
1.15k
446
1.15k
    if (!Call)
447
1.14k
      return true;
448
6
449
6
    
if (6
isConstCall(Call)6
) {
450
6
      HasIVParams = true;
451
6
      return false;
452
6
    }
453
0
454
0
    return true;
455
0
  }
456
457
25.6k
  bool isDone() { return HasIVParams; }
458
11.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
  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
34.5k
      : R(R), Scope(Scope), ILS(ILS), AllowLoops(AllowLoops) {}
473
474
97.6k
  bool follow(const SCEV *S) {
475
97.6k
    if (auto 
Unknown97.6k
= dyn_cast<SCEVUnknown>(S)) {
476
27.3k
      Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
477
27.3k
478
27.3k
      CallInst *Call = dyn_cast<CallInst>(Unknown->getValue());
479
27.3k
480
27.3k
      if (
Call && 27.3k
isConstCall(Call)136
)
481
30
        return false;
482
27.3k
483
27.3k
      
if (27.3k
Inst27.3k
) {
484
14.5k
        // When we invariant load hoist a load, we first make sure that there
485
14.5k
        // can be no dependences created by it in the Scop region. So, we should
486
14.5k
        // not consider scalar dependences to `LoadInst`s that are invariant
487
14.5k
        // load hoisted.
488
14.5k
        //
489
14.5k
        // If this check is not present, then we create data dependences which
490
14.5k
        // are strictly not necessary by tracking the invariant load as a
491
14.5k
        // scalar.
492
14.5k
        LoadInst *LI = dyn_cast<LoadInst>(Inst);
493
14.5k
        if (
LI && 14.5k
ILS.count(LI) > 09.99k
)
494
2.61k
          return false;
495
24.6k
      }
496
24.6k
497
24.6k
      // Return true when Inst is defined inside the region R.
498
24.6k
      
if (24.6k
!Inst || 24.6k
!R->contains(Inst)11.9k
)
499
15.9k
        return true;
500
8.72k
501
8.72k
      HasInRegionDeps = true;
502
8.72k
      return false;
503
8.72k
    }
504
70.3k
505
70.3k
    
if (auto 70.3k
AddRec70.3k
= dyn_cast<SCEVAddRecExpr>(S)) {
506
20.2k
      if (AllowLoops)
507
0
        return true;
508
20.2k
509
20.2k
      auto *L = AddRec->getLoop();
510
20.2k
      if (
R->contains(L) && 20.2k
!L->contains(Scope)19.8k
) {
511
38
        HasInRegionDeps = true;
512
38
        return false;
513
38
      }
514
70.3k
    }
515
70.3k
516
70.3k
    return true;
517
70.3k
  }
518
86.2k
  bool isDone() { return false; }
519
34.5k
  bool hasDependences() { return HasInRegionDeps; }
520
};
521
522
namespace polly {
523
/// Find all loops referenced in SCEVAddRecExprs.
524
class SCEVFindLoops {
525
  SetVector<const Loop *> &Loops;
526
527
public:
528
15.4k
  SCEVFindLoops(SetVector<const Loop *> &Loops) : Loops(Loops) {}
529
530
40.0k
  bool follow(const SCEV *S) {
531
40.0k
    if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S))
532
8.95k
      Loops.insert(AddRec->getLoop());
533
40.0k
    return true;
534
40.0k
  }
535
40.0k
  bool isDone() { return false; }
536
};
537
538
15.4k
void findLoops(const SCEV *Expr, SetVector<const Loop *> &Loops) {
539
15.4k
  SCEVFindLoops FindLoops(Loops);
540
15.4k
  SCEVTraversal<SCEVFindLoops> ST(FindLoops);
541
15.4k
  ST.visitAll(Expr);
542
15.4k
}
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.9k
      : SE(SE), Values(Values) {}
552
553
44.3k
  bool follow(const SCEV *S) {
554
44.3k
    const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S);
555
44.3k
    if (!Unknown)
556
37.6k
      return true;
557
6.63k
558
6.63k
    Values.insert(Unknown->getValue());
559
6.63k
    Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
560
6.63k
    if (
!Inst || 6.63k
(Inst->getOpcode() != Instruction::SRem &&
561
2.84k
                  Inst->getOpcode() != Instruction::SDiv))
562
6.54k
      return false;
563
83
564
83
    auto *Dividend = SE.getSCEV(Inst->getOperand(1));
565
83
    if (!isa<SCEVConstant>(Dividend))
566
2
      return false;
567
81
568
81
    auto *Divisor = SE.getSCEV(Inst->getOperand(0));
569
81
    SCEVFindValues FindValues(SE, Values);
570
81
    SCEVTraversal<SCEVFindValues> ST(FindValues);
571
81
    ST.visitAll(Dividend);
572
81
    ST.visitAll(Divisor);
573
81
574
81
    return false;
575
81
  }
576
37.6k
  bool isDone() { return false; }
577
};
578
579
void findValues(const SCEV *Expr, ScalarEvolution &SE,
580
18.8k
                SetVector<Value *> &Values) {
581
18.8k
  SCEVFindValues FindValues(SE, Values);
582
18.8k
  SCEVTraversal<SCEVFindValues> ST(FindValues);
583
18.8k
  ST.visitAll(Expr);
584
18.8k
}
585
586
11.4k
bool hasIVParams(const SCEV *Expr) {
587
11.4k
  SCEVHasIVParams HasIVParams;
588
11.4k
  SCEVTraversal<SCEVHasIVParams> ST(HasIVParams);
589
11.4k
  ST.visitAll(Expr);
590
11.4k
  return HasIVParams.hasIVParams();
591
11.4k
}
592
593
bool hasScalarDepsInsideRegion(const SCEV *Expr, const Region *R,
594
                               llvm::Loop *Scope, bool AllowLoops,
595
34.5k
                               const InvariantLoadsSetTy &ILS) {
596
34.5k
  SCEVInRegionDependences InRegionDeps(R, Scope, AllowLoops, ILS);
597
34.5k
  SCEVTraversal<SCEVInRegionDependences> ST(InRegionDeps);
598
34.5k
  ST.visitAll(Expr);
599
34.5k
  return InRegionDeps.hasDependences();
600
34.5k
}
601
602
bool isAffineExpr(const Region *R, llvm::Loop *Scope, const SCEV *Expr,
603
46.7k
                  ScalarEvolution &SE, InvariantLoadsSetTy *ILS) {
604
46.7k
  if (isa<SCEVCouldNotCompute>(Expr))
605
0
    return false;
606
46.7k
607
46.7k
  SCEVValidator Validator(R, Scope, SE, ILS);
608
46.7k
  DEBUG({
609
46.7k
    dbgs() << "\n";
610
46.7k
    dbgs() << "Expr: " << *Expr << "\n";
611
46.7k
    dbgs() << "Region: " << R->getNameStr() << "\n";
612
46.7k
    dbgs() << " -> ";
613
46.7k
  });
614
46.7k
615
46.7k
  ValidatorResult Result = Validator.visit(Expr);
616
46.7k
617
46.7k
  DEBUG({
618
46.7k
    if (Result.isValid())
619
46.7k
      dbgs() << "VALID\n";
620
46.7k
    dbgs() << "\n";
621
46.7k
  });
622
46.7k
623
46.7k
  return Result.isValid();
624
46.7k
}
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)) {
647
26
    return isAffineConstraint(ICmp->getOperand(0), R, Scope, SE, Params,
648
26
                              true) &&
649
26
           isAffineConstraint(ICmp->getOperand(1), R, Scope, SE, Params, true);
650
58
  } else 
if (auto *58
BinOp58
= dyn_cast<BinaryOperator>(V)) {
651
10
    auto Opcode = BinOp->getOpcode();
652
10
    if (
Opcode == Instruction::And || 10
Opcode == Instruction::Or4
)
653
6
      return isAffineConstraint(BinOp->getOperand(0), R, Scope, SE, Params,
654
6
                                false) &&
655
6
             isAffineConstraint(BinOp->getOperand(1), R, Scope, SE, Params,
656
6
                                false);
657
52
    /* Fall through */
658
52
  }
659
52
660
52
  
if (52
!OrExpr52
)
661
0
    return false;
662
52
663
52
  return isAffineExpr(V, R, Scope, SE, Params);
664
52
}
665
666
ParameterSetTy getParamsInAffineExpr(const Region *R, Loop *Scope,
667
11.9k
                                     const SCEV *Expr, ScalarEvolution &SE) {
668
11.9k
  if (isa<SCEVCouldNotCompute>(Expr))
669
0
    return ParameterSetTy();
670
11.9k
671
11.9k
  InvariantLoadsSetTy ILS;
672
11.9k
  SCEVValidator Validator(R, Scope, SE, &ILS);
673
11.9k
  ValidatorResult Result = Validator.visit(Expr);
674
11.9k
  assert(Result.isValid() && "Requested parameters for an invalid SCEV!");
675
11.9k
676
11.9k
  return Result.getParameters();
677
11.9k
}
678
679
std::pair<const SCEVConstant *, const SCEV *>
680
18.7k
extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
681
18.7k
  auto *ConstPart = cast<SCEVConstant>(SE.getConstant(S->getType(), 1));
682
18.7k
683
18.7k
  if (auto *Constant = dyn_cast<SCEVConstant>(S))
684
8.47k
    return std::make_pair(Constant, SE.getConstant(S->getType(), 1));
685
10.2k
686
10.2k
  auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
687
10.2k
  if (
AddRec10.2k
) {
688
4.27k
    auto *StartExpr = AddRec->getStart();
689
4.27k
    if (
StartExpr->isZero()4.27k
) {
690
3.17k
      auto StepPair = extractConstantFactor(AddRec->getStepRecurrence(SE), SE);
691
3.17k
      auto *LeftOverAddRec =
692
3.17k
          SE.getAddRecExpr(StartExpr, StepPair.second, AddRec->getLoop(),
693
3.17k
                           AddRec->getNoWrapFlags());
694
3.17k
      return std::make_pair(StepPair.first, LeftOverAddRec);
695
3.17k
    }
696
1.10k
    return std::make_pair(ConstPart, S);
697
1.10k
  }
698
5.97k
699
5.97k
  
if (auto *5.97k
Add5.97k
= dyn_cast<SCEVAddExpr>(S)) {
700
239
    SmallVector<const SCEV *, 4> LeftOvers;
701
239
    auto Op0Pair = extractConstantFactor(Add->getOperand(0), SE);
702
239
    auto *Factor = Op0Pair.first;
703
239
    if (
SE.isKnownNegative(Factor)239
) {
704
84
      Factor = cast<SCEVConstant>(SE.getNegativeSCEV(Factor));
705
84
      LeftOvers.push_back(SE.getNegativeSCEV(Op0Pair.second));
706
239
    } else {
707
155
      LeftOvers.push_back(Op0Pair.second);
708
155
    }
709
239
710
355
    for (unsigned u = 1, e = Add->getNumOperands(); 
u < e355
;
u++116
) {
711
240
      auto OpUPair = extractConstantFactor(Add->getOperand(u), SE);
712
240
      // TODO: Use something smarter than equality here, e.g., gcd.
713
240
      if (Factor == OpUPair.first)
714
110
        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
240
    }
720
239
721
115
    auto *NewAdd = SE.getAddExpr(LeftOvers, Add->getNoWrapFlags());
722
115
    return std::make_pair(Factor, NewAdd);
723
5.73k
  }
724
5.73k
725
5.73k
  auto *Mul = dyn_cast<SCEVMulExpr>(S);
726
5.73k
  if (!Mul)
727
5.10k
    return std::make_pair(ConstPart, S);
728
626
729
626
  SmallVector<const SCEV *, 4> LeftOvers;
730
626
  for (auto *Op : Mul->operands())
731
1.30k
    
if (1.30k
isa<SCEVConstant>(Op)1.30k
)
732
560
      ConstPart = cast<SCEVConstant>(SE.getMulExpr(ConstPart, Op));
733
1.30k
    else
734
742
      LeftOvers.push_back(Op);
735
18.7k
736
18.7k
  return std::make_pair(ConstPart, SE.getMulExpr(LeftOvers));
737
18.7k
}
738
739
const SCEV *tryForwardThroughPHI(const SCEV *Expr, Region &R,
740
                                 ScalarEvolution &SE, LoopInfo &LI,
741
31.4k
                                 const DominatorTree &DT) {
742
31.4k
  if (auto *
Unknown31.4k
= dyn_cast<SCEVUnknown>(Expr)) {
743
5.45k
    Value *V = Unknown->getValue();
744
5.45k
    auto *PHI = dyn_cast<PHINode>(V);
745
5.45k
    if (!PHI)
746
5.40k
      return Expr;
747
48
748
48
    Value *Final = nullptr;
749
48
750
99
    for (unsigned i = 0; 
i < PHI->getNumIncomingValues()99
;
i++51
) {
751
94
      BasicBlock *Incoming = PHI->getIncomingBlock(i);
752
94
      if (
isErrorBlock(*Incoming, R, LI, DT) && 94
R.contains(Incoming)7
)
753
3
        continue;
754
91
      
if (91
Final91
)
755
43
        return Expr;
756
48
      Final = PHI->getIncomingValue(i);
757
48
    }
758
48
759
5
    
if (5
Final5
)
760
5
      return SE.getSCEV(Final);
761
25.9k
  }
762
25.9k
  return Expr;
763
25.9k
}
764
765
Value *getUniqueNonErrorValue(PHINode *PHI, Region *R, LoopInfo &LI,
766
11
                              const DominatorTree &DT) {
767
11
  Value *V = nullptr;
768
25
  for (unsigned i = 0; 
i < PHI->getNumIncomingValues()25
;
i++14
) {
769
22
    BasicBlock *BB = PHI->getIncomingBlock(i);
770
22
    if (
!isErrorBlock(*BB, *R, LI, DT)22
) {
771
19
      if (V)
772
8
        return nullptr;
773
11
      V = PHI->getIncomingValue(i);
774
11
    }
775
22
  }
776
11
777
3
  return V;
778
11
}
779
} // namespace polly