1
2#include "polly/Support/SCEVValidator.h"
3#include "polly/ScopDetection.h"
4#include "llvm/Analysis/RegionInfo.h"
5#include "llvm/Analysis/ScalarEvolution.h"
6#include "llvm/Analysis/ScalarEvolutionExpressions.h"
7#include "llvm/Support/Debug.h"
8
9using namespace llvm;
10using namespace polly;
11
12#include "polly/Support/PollyDebug.h"
13#define DEBUG_TYPE "polly-scev-validator"
14
15namespace SCEVType {
16/// The type of a SCEV
17///
18/// To check for the validity of a SCEV we assign to each SCEV a type. The
19/// possible types are INT, PARAM, IV and INVALID. The order of the types is
20/// important. The subexpressions of SCEV with a type X can only have a type
21/// that is smaller or equal than X.
22enum TYPE {
23 // An integer value.
24 INT,
25
26 // An expression that is constant during the execution of the Scop,
27 // but that may depend on parameters unknown at compile time.
28 PARAM,
29
30 // An expression that may change during the execution of the SCoP.
31 IV,
32
33 // An invalid expression.
34 INVALID
35};
36} // namespace SCEVType
37
38/// The result the validator returns for a SCEV expression.
39class ValidatorResult final {
40 /// The type of the expression
41 SCEVType::TYPE Type;
42
43 /// The set of Parameters in the expression.
44 ParameterSetTy Parameters;
45
46public:
47 /// The copy constructor
48 ValidatorResult(const ValidatorResult &Source) {
49 Type = Source.Type;
50 Parameters = Source.Parameters;
51 }
52
53 /// Construct a result with a certain type and no parameters.
54 ValidatorResult(SCEVType::TYPE Type) : Type(Type) {
55 assert(Type != SCEVType::PARAM && "Did you forget to pass the parameter");
56 }
57
58 /// Construct a result with a certain type and a single parameter.
59 ValidatorResult(SCEVType::TYPE Type, const SCEV *Expr) : Type(Type) {
60 Parameters.insert(X: Expr);
61 }
62
63 /// Get the type of the ValidatorResult.
64 SCEVType::TYPE getType() { return Type; }
65
66 /// Is the analyzed SCEV constant during the execution of the SCoP.
67 bool isConstant() { return Type == SCEVType::INT || Type == SCEVType::PARAM; }
68
69 /// Is the analyzed SCEV valid.
70 bool isValid() { return Type != SCEVType::INVALID; }
71
72 /// Is the analyzed SCEV of Type IV.
73 bool isIV() { return Type == SCEVType::IV; }
74
75 /// Is the analyzed SCEV of Type INT.
76 bool isINT() { return Type == SCEVType::INT; }
77
78 /// Is the analyzed SCEV of Type PARAM.
79 bool isPARAM() { return Type == SCEVType::PARAM; }
80
81 /// Get the parameters of this validator result.
82 const ParameterSetTy &getParameters() { return Parameters; }
83
84 /// Add the parameters of Source to this result.
85 void addParamsFrom(const ValidatorResult &Source) {
86 Parameters.insert_range(R: Source.Parameters);
87 }
88
89 /// Merge a result.
90 ///
91 /// This means to merge the parameters and to set the Type to the most
92 /// specific Type that matches both.
93 void merge(const ValidatorResult &ToMerge) {
94 Type = std::max(a: Type, b: ToMerge.Type);
95 addParamsFrom(Source: ToMerge);
96 }
97
98 void print(raw_ostream &OS) {
99 switch (Type) {
100 case SCEVType::INT:
101 OS << "SCEVType::INT";
102 break;
103 case SCEVType::PARAM:
104 OS << "SCEVType::PARAM";
105 break;
106 case SCEVType::IV:
107 OS << "SCEVType::IV";
108 break;
109 case SCEVType::INVALID:
110 OS << "SCEVType::INVALID";
111 break;
112 }
113 }
114};
115
116raw_ostream &operator<<(raw_ostream &OS, ValidatorResult &VR) {
117 VR.print(OS);
118 return OS;
119}
120
121/// Check if a SCEV is valid in a SCoP.
122class SCEVValidator : public SCEVVisitor<SCEVValidator, ValidatorResult> {
123private:
124 const Region *R;
125 Loop *Scope;
126 ScalarEvolution &SE;
127 InvariantLoadsSetTy *ILS;
128
129public:
130 SCEVValidator(const Region *R, Loop *Scope, ScalarEvolution &SE,
131 InvariantLoadsSetTy *ILS)
132 : R(R), Scope(Scope), SE(SE), ILS(ILS) {}
133
134 ValidatorResult visitConstant(const SCEVConstant *Constant) {
135 return ValidatorResult(SCEVType::INT);
136 }
137
138 ValidatorResult visitVScale(const SCEVVScale *VScale) {
139 // We do not support VScale constants.
140 POLLY_DEBUG(dbgs() << "INVALID: VScale is not supported");
141 return ValidatorResult(SCEVType::INVALID);
142 }
143
144 ValidatorResult visitZeroExtendOrTruncateExpr(const SCEV *Expr,
145 const SCEV *Operand) {
146 ValidatorResult Op = visit(S: Operand);
147 auto Type = Op.getType();
148
149 // If unsigned operations are allowed return the operand, otherwise
150 // check if we can model the expression without unsigned assumptions.
151 if (PollyAllowUnsignedOperations || Type == SCEVType::INVALID)
152 return Op;
153
154 if (Type == SCEVType::IV)
155 return ValidatorResult(SCEVType::INVALID);
156 return ValidatorResult(SCEVType::PARAM, Expr);
157 }
158
159 ValidatorResult visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr) {
160 return visit(S: Expr->getOperand());
161 }
162
163 ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
164 return visitZeroExtendOrTruncateExpr(Expr, Operand: Expr->getOperand());
165 }
166
167 ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
168 return visitZeroExtendOrTruncateExpr(Expr, Operand: Expr->getOperand());
169 }
170
171 ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
172 return visit(S: Expr->getOperand());
173 }
174
175 ValidatorResult visitAddExpr(const SCEVAddExpr *Expr) {
176 ValidatorResult Return(SCEVType::INT);
177
178 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
179 ValidatorResult Op = visit(S: Expr->getOperand(i));
180 Return.merge(ToMerge: Op);
181
182 // Early exit.
183 if (!Return.isValid())
184 break;
185 }
186
187 return Return;
188 }
189
190 ValidatorResult visitMulExpr(const SCEVMulExpr *Expr) {
191 ValidatorResult Return(SCEVType::INT);
192
193 bool HasMultipleParams = false;
194
195 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
196 ValidatorResult Op = visit(S: Expr->getOperand(i));
197
198 if (Op.isINT())
199 continue;
200
201 if (Op.isPARAM() && Return.isPARAM()) {
202 HasMultipleParams = true;
203 continue;
204 }
205
206 if ((Op.isIV() || Op.isPARAM()) && !Return.isINT()) {
207 POLLY_DEBUG(
208 dbgs() << "INVALID: More than one non-int operand in MulExpr\n"
209 << "\tExpr: " << *Expr << "\n"
210 << "\tPrevious expression type: " << Return << "\n"
211 << "\tNext operand (" << Op << "): " << *Expr->getOperand(i)
212 << "\n");
213
214 return ValidatorResult(SCEVType::INVALID);
215 }
216
217 Return.merge(ToMerge: Op);
218 }
219
220 if (HasMultipleParams && Return.isValid())
221 return ValidatorResult(SCEVType::PARAM, Expr);
222
223 return Return;
224 }
225
226 ValidatorResult visitAddRecExpr(const SCEVAddRecExpr *Expr) {
227 if (!Expr->isAffine()) {
228 POLLY_DEBUG(dbgs() << "INVALID: AddRec is not affine");
229 return ValidatorResult(SCEVType::INVALID);
230 }
231
232 ValidatorResult Start = visit(S: Expr->getStart());
233 ValidatorResult Recurrence = visit(S: Expr->getStepRecurrence(SE));
234
235 if (!Start.isValid())
236 return Start;
237
238 if (!Recurrence.isValid())
239 return Recurrence;
240
241 auto *L = Expr->getLoop();
242 if (R->contains(L) && (!Scope || !L->contains(L: Scope))) {
243 POLLY_DEBUG(
244 dbgs() << "INVALID: Loop of AddRec expression boxed in an a "
245 "non-affine subregion or has a non-synthesizable exit "
246 "value.");
247 return ValidatorResult(SCEVType::INVALID);
248 }
249
250 if (R->contains(L)) {
251 if (Recurrence.isINT()) {
252 ValidatorResult Result(SCEVType::IV);
253 Result.addParamsFrom(Source: Start);
254 return Result;
255 }
256
257 POLLY_DEBUG(dbgs() << "INVALID: AddRec within scop has non-int"
258 "recurrence part");
259 return ValidatorResult(SCEVType::INVALID);
260 }
261
262 assert(Recurrence.isConstant() && "Expected 'Recurrence' to be constant");
263
264 // Directly generate ValidatorResult for Expr if 'start' is zero.
265 if (Expr->getStart()->isZero())
266 return ValidatorResult(SCEVType::PARAM, Expr);
267
268 // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}'
269 // if 'start' is not zero.
270 const SCEV *ZeroStartExpr = SE.getAddRecExpr(
271 Start: SE.getConstant(Ty: Expr->getStart()->getType(), V: 0),
272 Step: Expr->getStepRecurrence(SE), L: Expr->getLoop(), Flags: Expr->getNoWrapFlags());
273
274 ValidatorResult ZeroStartResult =
275 ValidatorResult(SCEVType::PARAM, ZeroStartExpr);
276 ZeroStartResult.addParamsFrom(Source: Start);
277
278 return ZeroStartResult;
279 }
280
281 ValidatorResult visitSMaxExpr(const SCEVSMaxExpr *Expr) {
282 ValidatorResult Return(SCEVType::INT);
283
284 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
285 ValidatorResult Op = visit(S: Expr->getOperand(i));
286
287 if (!Op.isValid())
288 return Op;
289
290 Return.merge(ToMerge: Op);
291 }
292
293 return Return;
294 }
295
296 ValidatorResult visitSMinExpr(const SCEVSMinExpr *Expr) {
297 ValidatorResult Return(SCEVType::INT);
298
299 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
300 ValidatorResult Op = visit(S: Expr->getOperand(i));
301
302 if (!Op.isValid())
303 return Op;
304
305 Return.merge(ToMerge: Op);
306 }
307
308 return Return;
309 }
310
311 ValidatorResult visitUMaxExpr(const SCEVUMaxExpr *Expr) {
312 // We do not support unsigned max operations. If 'Expr' is constant during
313 // Scop execution we treat this as a parameter, otherwise we bail out.
314 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
315 ValidatorResult Op = visit(S: Expr->getOperand(i));
316
317 if (!Op.isConstant()) {
318 POLLY_DEBUG(dbgs() << "INVALID: UMaxExpr has a non-constant operand");
319 return ValidatorResult(SCEVType::INVALID);
320 }
321 }
322
323 return ValidatorResult(SCEVType::PARAM, Expr);
324 }
325
326 ValidatorResult visitUMinExpr(const SCEVUMinExpr *Expr) {
327 // We do not support unsigned min operations. If 'Expr' is constant during
328 // Scop execution we treat this as a parameter, otherwise we bail out.
329 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
330 ValidatorResult Op = visit(S: Expr->getOperand(i));
331
332 if (!Op.isConstant()) {
333 POLLY_DEBUG(dbgs() << "INVALID: UMinExpr has a non-constant operand");
334 return ValidatorResult(SCEVType::INVALID);
335 }
336 }
337
338 return ValidatorResult(SCEVType::PARAM, Expr);
339 }
340
341 ValidatorResult visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) {
342 // We do not support unsigned min operations. If 'Expr' is constant during
343 // Scop execution we treat this as a parameter, otherwise we bail out.
344 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
345 ValidatorResult Op = visit(S: Expr->getOperand(i));
346
347 if (!Op.isConstant()) {
348 POLLY_DEBUG(
349 dbgs()
350 << "INVALID: SCEVSequentialUMinExpr has a non-constant operand");
351 return ValidatorResult(SCEVType::INVALID);
352 }
353 }
354
355 return ValidatorResult(SCEVType::PARAM, Expr);
356 }
357
358 ValidatorResult visitGenericInst(Instruction *I, const SCEV *S) {
359 if (R->contains(Inst: I)) {
360 POLLY_DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
361 "within the region\n");
362 return ValidatorResult(SCEVType::INVALID);
363 }
364
365 return ValidatorResult(SCEVType::PARAM, S);
366 }
367
368 ValidatorResult visitLoadInstruction(Instruction *I, const SCEV *S) {
369 if (R->contains(Inst: I) && ILS) {
370 ILS->insert(X: cast<LoadInst>(Val: I));
371 return ValidatorResult(SCEVType::PARAM, S);
372 }
373
374 return visitGenericInst(I, S);
375 }
376
377 ValidatorResult visitDivision(const SCEV *Dividend, const SCEV *Divisor,
378 const SCEV *DivExpr,
379 Instruction *SDiv = nullptr) {
380
381 // First check if we might be able to model the division, thus if the
382 // divisor is constant. If so, check the dividend, otherwise check if
383 // the whole division can be seen as a parameter.
384 if (isa<SCEVConstant>(Val: Divisor) && !Divisor->isZero())
385 return visit(S: Dividend);
386
387 // For signed divisions use the SDiv instruction to check for a parameter
388 // division, for unsigned divisions check the operands.
389 if (SDiv)
390 return visitGenericInst(I: SDiv, S: DivExpr);
391
392 ValidatorResult LHS = visit(S: Dividend);
393 ValidatorResult RHS = visit(S: Divisor);
394 if (LHS.isConstant() && RHS.isConstant())
395 return ValidatorResult(SCEVType::PARAM, DivExpr);
396
397 POLLY_DEBUG(
398 dbgs() << "INVALID: unsigned division of non-constant expressions");
399 return ValidatorResult(SCEVType::INVALID);
400 }
401
402 ValidatorResult visitUDivExpr(const SCEVUDivExpr *Expr) {
403 if (!PollyAllowUnsignedOperations)
404 return ValidatorResult(SCEVType::INVALID);
405
406 const SCEV *Dividend = Expr->getLHS();
407 const SCEV *Divisor = Expr->getRHS();
408 return visitDivision(Dividend, Divisor, DivExpr: Expr);
409 }
410
411 ValidatorResult visitSDivInstruction(Instruction *SDiv, const SCEV *Expr) {
412 assert(SDiv->getOpcode() == Instruction::SDiv &&
413 "Assumed SDiv instruction!");
414
415 const SCEV *Dividend = SE.getSCEV(V: SDiv->getOperand(i: 0));
416 const SCEV *Divisor = SE.getSCEV(V: SDiv->getOperand(i: 1));
417 return visitDivision(Dividend, Divisor, DivExpr: Expr, SDiv);
418 }
419
420 ValidatorResult visitSRemInstruction(Instruction *SRem, const SCEV *S) {
421 assert(SRem->getOpcode() == Instruction::SRem &&
422 "Assumed SRem instruction!");
423
424 auto *Divisor = SRem->getOperand(i: 1);
425 auto *CI = dyn_cast<ConstantInt>(Val: Divisor);
426 if (!CI || CI->isZeroValue())
427 return visitGenericInst(I: SRem, S);
428
429 auto *Dividend = SRem->getOperand(i: 0);
430 const SCEV *DividendSCEV = SE.getSCEV(V: Dividend);
431 return visit(S: DividendSCEV);
432 }
433
434 ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
435 Value *V = Expr->getValue();
436
437 if (!Expr->getType()->isIntegerTy() && !Expr->getType()->isPointerTy()) {
438 POLLY_DEBUG(
439 dbgs() << "INVALID: UnknownExpr is not an integer or pointer");
440 return ValidatorResult(SCEVType::INVALID);
441 }
442
443 if (isa<UndefValue>(Val: V)) {
444 POLLY_DEBUG(dbgs() << "INVALID: UnknownExpr references an undef value");
445 return ValidatorResult(SCEVType::INVALID);
446 }
447
448 if (Instruction *I = dyn_cast<Instruction>(Val: Expr->getValue())) {
449 switch (I->getOpcode()) {
450 case Instruction::IntToPtr:
451 return visit(S: SE.getSCEVAtScope(V: I->getOperand(i: 0), L: Scope));
452 case Instruction::Load:
453 return visitLoadInstruction(I, S: Expr);
454 case Instruction::SDiv:
455 return visitSDivInstruction(SDiv: I, Expr);
456 case Instruction::SRem:
457 return visitSRemInstruction(SRem: I, S: Expr);
458 default:
459 return visitGenericInst(I, S: Expr);
460 }
461 }
462
463 if (Expr->getType()->isPointerTy()) {
464 if (isa<ConstantPointerNull>(Val: V))
465 return ValidatorResult(SCEVType::INT); // "int"
466 }
467
468 return ValidatorResult(SCEVType::PARAM, Expr);
469 }
470};
471
472/// Check whether a SCEV refers to an SSA name defined inside a region.
473class SCEVInRegionDependences final {
474 const Region *R;
475 Loop *Scope;
476 const InvariantLoadsSetTy &ILS;
477 bool AllowLoops;
478 bool HasInRegionDeps = false;
479
480public:
481 SCEVInRegionDependences(const Region *R, Loop *Scope, bool AllowLoops,
482 const InvariantLoadsSetTy &ILS)
483 : R(R), Scope(Scope), ILS(ILS), AllowLoops(AllowLoops) {}
484
485 bool follow(const SCEV *S) {
486 if (auto Unknown = dyn_cast<SCEVUnknown>(Val: S)) {
487 Instruction *Inst = dyn_cast<Instruction>(Val: Unknown->getValue());
488
489 if (Inst) {
490 // When we invariant load hoist a load, we first make sure that there
491 // can be no dependences created by it in the Scop region. So, we should
492 // not consider scalar dependences to `LoadInst`s that are invariant
493 // load hoisted.
494 //
495 // If this check is not present, then we create data dependences which
496 // are strictly not necessary by tracking the invariant load as a
497 // scalar.
498 LoadInst *LI = dyn_cast<LoadInst>(Val: Inst);
499 if (LI && ILS.contains(key: LI))
500 return false;
501 }
502
503 // Return true when Inst is defined inside the region R.
504 if (!Inst || !R->contains(Inst))
505 return true;
506
507 HasInRegionDeps = true;
508 return false;
509 }
510
511 if (auto AddRec = dyn_cast<SCEVAddRecExpr>(Val: S)) {
512 if (AllowLoops)
513 return true;
514
515 auto *L = AddRec->getLoop();
516 if (R->contains(L) && !L->contains(L: Scope)) {
517 HasInRegionDeps = true;
518 return false;
519 }
520 }
521
522 return true;
523 }
524 bool isDone() { return false; }
525 bool hasDependences() { return HasInRegionDeps; }
526};
527
528/// Find all loops referenced in SCEVAddRecExprs.
529class SCEVFindLoops final {
530 SetVector<const Loop *> &Loops;
531
532public:
533 SCEVFindLoops(SetVector<const Loop *> &Loops) : Loops(Loops) {}
534
535 bool follow(const SCEV *S) {
536 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Val: S))
537 Loops.insert(X: AddRec->getLoop());
538 return true;
539 }
540 bool isDone() { return false; }
541};
542
543void polly::findLoops(const SCEV *Expr, SetVector<const Loop *> &Loops) {
544 SCEVFindLoops FindLoops(Loops);
545 SCEVTraversal<SCEVFindLoops> ST(FindLoops);
546 ST.visitAll(Root: Expr);
547}
548
549/// Find all values referenced in SCEVUnknowns.
550class SCEVFindValues final {
551 ScalarEvolution &SE;
552 SetVector<Value *> &Values;
553
554public:
555 SCEVFindValues(ScalarEvolution &SE, SetVector<Value *> &Values)
556 : SE(SE), Values(Values) {}
557
558 bool follow(const SCEV *S) {
559 const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(Val: S);
560 if (!Unknown)
561 return true;
562
563 Values.insert(X: Unknown->getValue());
564 Instruction *Inst = dyn_cast<Instruction>(Val: Unknown->getValue());
565 if (!Inst || (Inst->getOpcode() != Instruction::SRem &&
566 Inst->getOpcode() != Instruction::SDiv))
567 return false;
568
569 const SCEV *Dividend = SE.getSCEV(V: Inst->getOperand(i: 1));
570 if (!isa<SCEVConstant>(Val: Dividend))
571 return false;
572
573 const SCEV *Divisor = SE.getSCEV(V: Inst->getOperand(i: 0));
574 SCEVFindValues FindValues(SE, Values);
575 SCEVTraversal<SCEVFindValues> ST(FindValues);
576 ST.visitAll(Root: Dividend);
577 ST.visitAll(Root: Divisor);
578
579 return false;
580 }
581 bool isDone() { return false; }
582};
583
584void polly::findValues(const SCEV *Expr, ScalarEvolution &SE,
585 SetVector<Value *> &Values) {
586 SCEVFindValues FindValues(SE, Values);
587 SCEVTraversal<SCEVFindValues> ST(FindValues);
588 ST.visitAll(Root: Expr);
589}
590
591bool polly::hasScalarDepsInsideRegion(const SCEV *Expr, const Region *R,
592 llvm::Loop *Scope, bool AllowLoops,
593 const InvariantLoadsSetTy &ILS) {
594 SCEVInRegionDependences InRegionDeps(R, Scope, AllowLoops, ILS);
595 SCEVTraversal<SCEVInRegionDependences> ST(InRegionDeps);
596 ST.visitAll(Root: Expr);
597 return InRegionDeps.hasDependences();
598}
599
600bool polly::isAffineExpr(const Region *R, llvm::Loop *Scope, const SCEV *Expr,
601 ScalarEvolution &SE, InvariantLoadsSetTy *ILS) {
602 if (isa<SCEVCouldNotCompute>(Val: Expr))
603 return false;
604
605 SCEVValidator Validator(R, Scope, SE, ILS);
606 POLLY_DEBUG({
607 dbgs() << "\n";
608 dbgs() << "Expr: " << *Expr << "\n";
609 dbgs() << "Region: " << R->getNameStr() << "\n";
610 dbgs() << " -> ";
611 });
612
613 ValidatorResult Result = Validator.visit(S: Expr);
614
615 POLLY_DEBUG({
616 if (Result.isValid())
617 dbgs() << "VALID\n";
618 dbgs() << "\n";
619 });
620
621 return Result.isValid();
622}
623
624static bool isAffineExpr(Value *V, const Region *R, Loop *Scope,
625 ScalarEvolution &SE, ParameterSetTy &Params) {
626 const SCEV *E = SE.getSCEV(V);
627 if (isa<SCEVCouldNotCompute>(Val: E))
628 return false;
629
630 SCEVValidator Validator(R, Scope, SE, nullptr);
631 ValidatorResult Result = Validator.visit(S: E);
632 if (!Result.isValid())
633 return false;
634
635 auto ResultParams = Result.getParameters();
636 Params.insert_range(R&: ResultParams);
637
638 return true;
639}
640
641bool polly::isAffineConstraint(Value *V, const Region *R, Loop *Scope,
642 ScalarEvolution &SE, ParameterSetTy &Params,
643 bool OrExpr) {
644 if (auto *ICmp = dyn_cast<ICmpInst>(Val: V)) {
645 return isAffineConstraint(V: ICmp->getOperand(i_nocapture: 0), R, Scope, SE, Params,
646 OrExpr: true) &&
647 isAffineConstraint(V: ICmp->getOperand(i_nocapture: 1), R, Scope, SE, Params, OrExpr: true);
648 } else if (auto *BinOp = dyn_cast<BinaryOperator>(Val: V)) {
649 auto Opcode = BinOp->getOpcode();
650 if (Opcode == Instruction::And || Opcode == Instruction::Or)
651 return isAffineConstraint(V: BinOp->getOperand(i_nocapture: 0), R, Scope, SE, Params,
652 OrExpr: false) &&
653 isAffineConstraint(V: BinOp->getOperand(i_nocapture: 1), R, Scope, SE, Params,
654 OrExpr: false);
655 /* Fall through */
656 }
657
658 if (!OrExpr)
659 return false;
660
661 return ::isAffineExpr(V, R, Scope, SE, Params);
662}
663
664ParameterSetTy polly::getParamsInAffineExpr(const Region *R, Loop *Scope,
665 const SCEV *Expr,
666 ScalarEvolution &SE) {
667 if (isa<SCEVCouldNotCompute>(Val: Expr))
668 return ParameterSetTy();
669
670 InvariantLoadsSetTy ILS;
671 SCEVValidator Validator(R, Scope, SE, &ILS);
672 ValidatorResult Result = Validator.visit(S: Expr);
673 assert(Result.isValid() && "Requested parameters for an invalid SCEV!");
674
675 return Result.getParameters();
676}
677
678std::pair<const SCEVConstant *, const SCEV *>
679polly::extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
680 auto *ConstPart = cast<SCEVConstant>(Val: SE.getConstant(Ty: S->getType(), V: 1));
681
682 if (auto *Constant = dyn_cast<SCEVConstant>(Val: S))
683 return std::make_pair(x&: Constant, y: SE.getConstant(Ty: S->getType(), V: 1));
684
685 auto *AddRec = dyn_cast<SCEVAddRecExpr>(Val: S);
686 if (AddRec) {
687 const SCEV *StartExpr = AddRec->getStart();
688 if (StartExpr->isZero()) {
689 auto StepPair = extractConstantFactor(S: AddRec->getStepRecurrence(SE), SE);
690 const SCEV *LeftOverAddRec =
691 SE.getAddRecExpr(Start: StartExpr, Step: StepPair.second, L: AddRec->getLoop(),
692 Flags: AddRec->getNoWrapFlags());
693 return std::make_pair(x&: StepPair.first, y&: LeftOverAddRec);
694 }
695 return std::make_pair(x&: ConstPart, y&: S);
696 }
697
698 if (auto *Add = dyn_cast<SCEVAddExpr>(Val: S)) {
699 SmallVector<const SCEV *, 4> LeftOvers;
700 auto Op0Pair = extractConstantFactor(S: Add->getOperand(i: 0), SE);
701 auto *Factor = Op0Pair.first;
702 if (SE.isKnownNegative(S: Factor)) {
703 Factor = cast<SCEVConstant>(Val: SE.getNegativeSCEV(V: Factor));
704 LeftOvers.push_back(Elt: SE.getNegativeSCEV(V: Op0Pair.second));
705 } else {
706 LeftOvers.push_back(Elt: Op0Pair.second);
707 }
708
709 for (unsigned u = 1, e = Add->getNumOperands(); u < e; u++) {
710 auto OpUPair = extractConstantFactor(S: Add->getOperand(i: u), SE);
711 // TODO: Use something smarter than equality here, e.g., gcd.
712 if (Factor == OpUPair.first)
713 LeftOvers.push_back(Elt: OpUPair.second);
714 else if (Factor == SE.getNegativeSCEV(V: OpUPair.first))
715 LeftOvers.push_back(Elt: SE.getNegativeSCEV(V: OpUPair.second));
716 else
717 return std::make_pair(x&: ConstPart, y&: S);
718 }
719
720 const SCEV *NewAdd = SE.getAddExpr(Ops&: LeftOvers, Flags: Add->getNoWrapFlags());
721 return std::make_pair(x&: Factor, y&: NewAdd);
722 }
723
724 auto *Mul = dyn_cast<SCEVMulExpr>(Val: S);
725 if (!Mul)
726 return std::make_pair(x&: ConstPart, y&: S);
727
728 SmallVector<const SCEV *, 4> LeftOvers;
729 for (const SCEV *Op : Mul->operands())
730 if (isa<SCEVConstant>(Val: Op))
731 ConstPart = cast<SCEVConstant>(Val: SE.getMulExpr(LHS: ConstPart, RHS: Op));
732 else
733 LeftOvers.push_back(Elt: Op);
734
735 return std::make_pair(x&: ConstPart, y: SE.getMulExpr(Ops&: LeftOvers));
736}
737
738const SCEV *polly::tryForwardThroughPHI(const SCEV *Expr, Region &R,
739 ScalarEvolution &SE,
740 ScopDetection *SD) {
741 if (auto *Unknown = dyn_cast<SCEVUnknown>(Val: Expr)) {
742 Value *V = Unknown->getValue();
743 auto *PHI = dyn_cast<PHINode>(Val: V);
744 if (!PHI)
745 return Expr;
746
747 Value *Final = nullptr;
748
749 for (unsigned i = 0; i < PHI->getNumIncomingValues(); i++) {
750 BasicBlock *Incoming = PHI->getIncomingBlock(i);
751 if (SD->isErrorBlock(BB&: *Incoming, R) && R.contains(BB: Incoming))
752 continue;
753 if (Final)
754 return Expr;
755 Final = PHI->getIncomingValue(i);
756 }
757
758 if (Final)
759 return SE.getSCEV(V: Final);
760 }
761 return Expr;
762}
763
764Value *polly::getUniqueNonErrorValue(PHINode *PHI, Region *R,
765 ScopDetection *SD) {
766 Value *V = nullptr;
767 for (unsigned i = 0; i < PHI->getNumIncomingValues(); i++) {
768 BasicBlock *BB = PHI->getIncomingBlock(i);
769 if (!SD->isErrorBlock(BB&: *BB, R: *R)) {
770 if (V)
771 return nullptr;
772 V = PHI->getIncomingValue(i);
773 }
774 }
775
776 return V;
777}
778

source code of polly/lib/Support/SCEVValidator.cpp