1//===---- Delinearization.cpp - MultiDimensional Index Delinearization ----===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This implements an analysis pass that tries to delinearize all GEP
10// instructions in all loops using the SCEV analysis functionality.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Analysis/Delinearization.h"
15#include "AnalysisOptions.h"
16#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/Analysis/ScalarEvolution.h"
18#include "llvm/Analysis/ScalarEvolutionDivision.h"
19#include "llvm/Analysis/ScalarEvolutionExpressions.h"
20#include "llvm/IR/Constants.h"
21#include "llvm/IR/DerivedTypes.h"
22#include "llvm/IR/Function.h"
23#include "llvm/IR/InstIterator.h"
24#include "llvm/IR/Instructions.h"
25#include "llvm/IR/PassManager.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/Support/raw_ostream.h"
28
29using namespace llvm;
30
31#define DL_NAME "delinearize"
32#define DEBUG_TYPE DL_NAME
33
34// Return true when S contains at least an undef value.
35static inline bool containsUndefs(const SCEV *S) {
36 return SCEVExprContains(Root: S, Pred: [](const SCEV *S) {
37 if (const auto *SU = dyn_cast<SCEVUnknown>(Val: S))
38 return isa<UndefValue>(Val: SU->getValue());
39 return false;
40 });
41}
42
43namespace {
44
45// Collect all steps of SCEV expressions.
46struct SCEVCollectStrides {
47 ScalarEvolution &SE;
48 SmallVectorImpl<const SCEV *> &Strides;
49
50 SCEVCollectStrides(ScalarEvolution &SE, SmallVectorImpl<const SCEV *> &S)
51 : SE(SE), Strides(S) {}
52
53 bool follow(const SCEV *S) {
54 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: S);
55 if (!AR || !AR->isAffine())
56 return false;
57
58 Strides.push_back(Elt: AR->getStepRecurrence(SE));
59 return true;
60 }
61
62 bool isDone() const { return false; }
63};
64
65// Collect all SCEVUnknown and SCEVMulExpr expressions.
66struct SCEVCollectTerms {
67 SmallVectorImpl<const SCEV *> &Terms;
68
69 SCEVCollectTerms(SmallVectorImpl<const SCEV *> &T) : Terms(T) {}
70
71 bool follow(const SCEV *S) {
72 if (isa<SCEVUnknown>(Val: S) || isa<SCEVMulExpr>(Val: S) ||
73 isa<SCEVSignExtendExpr>(Val: S))
74 if (!containsUndefs(S))
75 Terms.push_back(Elt: S);
76
77 // Keep looking when S is a specific type expression.
78 return isa<SCEVAddExpr, SCEVAddRecExpr>(Val: S);
79 }
80
81 bool isDone() const { return false; }
82};
83
84// Check if a SCEV contains an AddRecExpr.
85struct SCEVHasAddRec {
86 bool &ContainsAddRec;
87
88 SCEVHasAddRec(bool &ContainsAddRec) : ContainsAddRec(ContainsAddRec) {
89 ContainsAddRec = false;
90 }
91
92 bool follow(const SCEV *S) {
93 if (isa<SCEVAddRecExpr>(Val: S)) {
94 ContainsAddRec = true;
95
96 // Stop recursion: once we collected a term, do not walk its operands.
97 return false;
98 }
99
100 // Keep looking.
101 return true;
102 }
103
104 bool isDone() const { return false; }
105};
106
107// Find factors that are multiplied with an expression that (possibly as a
108// subexpression) contains an AddRecExpr. In the expression:
109//
110// 8 * (100 + %p * %q * (%a + {0, +, 1}_loop))
111//
112// "%p * %q" are factors multiplied by the expression "(%a + {0, +, 1}_loop)"
113// that contains the AddRec {0, +, 1}_loop. %p * %q are likely to be array size
114// parameters as they form a product with an induction variable.
115//
116// This collector expects all array size parameters to be in the same MulExpr.
117// It might be necessary to later add support for collecting parameters that are
118// spread over different nested MulExpr.
119struct SCEVCollectAddRecMultiplies {
120 SmallVectorImpl<const SCEV *> &Terms;
121 ScalarEvolution &SE;
122
123 SCEVCollectAddRecMultiplies(SmallVectorImpl<const SCEV *> &T,
124 ScalarEvolution &SE)
125 : Terms(T), SE(SE) {}
126
127 bool follow(const SCEV *S) {
128 if (auto *Mul = dyn_cast<SCEVMulExpr>(Val: S)) {
129 bool HasAddRec = false;
130 SmallVector<SCEVUse, 0> Operands;
131 for (const SCEV *Op : Mul->operands()) {
132 const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(Val: Op);
133 if (Unknown && !isa<CallInst>(Val: Unknown->getValue())) {
134 Operands.push_back(Elt: Op);
135 } else if (Unknown) {
136 HasAddRec = true;
137 } else {
138 bool ContainsAddRec = false;
139 SCEVHasAddRec ContiansAddRec(ContainsAddRec);
140 visitAll(Root: Op, Visitor&: ContiansAddRec);
141 HasAddRec |= ContainsAddRec;
142 }
143 }
144 if (Operands.size() == 0)
145 return true;
146
147 if (!HasAddRec)
148 return false;
149
150 Terms.push_back(Elt: SE.getMulExpr(Ops&: Operands));
151 }
152
153 // Keep looking when S is a specific type expression.
154 return isa<SCEVAddExpr, SCEVAddRecExpr>(Val: S);
155 }
156
157 bool isDone() const { return false; }
158};
159
160} // end anonymous namespace
161
162/// Find parametric terms in this SCEVAddRecExpr. We first for parameters in
163/// two places:
164/// 1) The strides of AddRec expressions.
165/// 2) Unknowns that are multiplied with AddRec expressions.
166void llvm::collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr,
167 SmallVectorImpl<const SCEV *> &Terms) {
168 SmallVector<const SCEV *, 4> Strides;
169 SCEVCollectStrides StrideCollector(SE, Strides);
170 visitAll(Root: Expr, Visitor&: StrideCollector);
171
172 LLVM_DEBUG({
173 dbgs() << "Strides:\n";
174 for (const SCEV *S : Strides)
175 dbgs().indent(2) << *S << "\n";
176 });
177
178 for (const SCEV *S : Strides) {
179 SCEVCollectTerms TermCollector(Terms);
180 visitAll(Root: S, Visitor&: TermCollector);
181 }
182
183 LLVM_DEBUG({
184 dbgs() << "Terms:\n";
185 for (const SCEV *T : Terms)
186 dbgs().indent(2) << *T << "\n";
187 });
188
189 SCEVCollectAddRecMultiplies MulCollector(Terms, SE);
190 visitAll(Root: Expr, Visitor&: MulCollector);
191}
192
193static bool findArrayDimensionsRec(ScalarEvolution &SE,
194 SmallVectorImpl<const SCEV *> &Terms,
195 SmallVectorImpl<const SCEV *> &Sizes) {
196 int Last = Terms.size() - 1;
197 const SCEV *Step = Terms[Last];
198
199 // End of recursion.
200 if (Last == 0) {
201 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Val: Step)) {
202 SmallVector<SCEVUse, 2> Qs;
203 for (const SCEV *Op : M->operands())
204 if (!isa<SCEVConstant>(Val: Op))
205 Qs.push_back(Elt: Op);
206
207 Step = SE.getMulExpr(Ops&: Qs);
208 }
209
210 Sizes.push_back(Elt: Step);
211 return true;
212 }
213
214 for (const SCEV *&Term : Terms) {
215 // Normalize the terms before the next call to findArrayDimensionsRec.
216 const SCEV *Q, *R;
217 SCEVDivision::divide(SE, Numerator: Term, Denominator: Step, Quotient: &Q, Remainder: &R);
218
219 // Bail out when GCD does not evenly divide one of the terms.
220 if (!R->isZero())
221 return false;
222
223 Term = Q;
224 }
225
226 // Remove all SCEVConstants.
227 erase_if(C&: Terms, P: [](const SCEV *E) { return isa<SCEVConstant>(Val: E); });
228
229 if (Terms.size() > 0)
230 if (!findArrayDimensionsRec(SE, Terms, Sizes))
231 return false;
232
233 Sizes.push_back(Elt: Step);
234 return true;
235}
236
237// Returns true when one of the SCEVs of Terms contains a SCEVUnknown parameter.
238static inline bool containsParameters(SmallVectorImpl<const SCEV *> &Terms) {
239 for (const SCEV *T : Terms)
240 if (SCEVExprContains(Root: T, Pred: [](const SCEV *S) { return isa<SCEVUnknown>(Val: S); }))
241 return true;
242
243 return false;
244}
245
246// Return the number of product terms in S.
247static inline int numberOfTerms(const SCEV *S) {
248 if (const SCEVMulExpr *Expr = dyn_cast<SCEVMulExpr>(Val: S))
249 return Expr->getNumOperands();
250 return 1;
251}
252
253static const SCEV *removeConstantFactors(ScalarEvolution &SE, const SCEV *T) {
254 if (isa<SCEVConstant>(Val: T))
255 return nullptr;
256
257 if (isa<SCEVUnknown>(Val: T))
258 return T;
259
260 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Val: T)) {
261 SmallVector<SCEVUse, 2> Factors;
262 for (const SCEV *Op : M->operands())
263 if (!isa<SCEVConstant>(Val: Op))
264 Factors.push_back(Elt: Op);
265
266 return SE.getMulExpr(Ops&: Factors);
267 }
268
269 return T;
270}
271
272void llvm::findArrayDimensions(ScalarEvolution &SE,
273 SmallVectorImpl<const SCEV *> &Terms,
274 SmallVectorImpl<const SCEV *> &Sizes,
275 const SCEV *ElementSize) {
276 if (Terms.size() < 1 || !ElementSize)
277 return;
278
279 // Early return when Terms do not contain parameters: we do not delinearize
280 // non parametric SCEVs.
281 if (!containsParameters(Terms))
282 return;
283
284 LLVM_DEBUG({
285 dbgs() << "Terms:\n";
286 for (const SCEV *T : Terms)
287 dbgs().indent(2) << *T << "\n";
288 });
289
290 // Remove duplicates.
291 array_pod_sort(Start: Terms.begin(), End: Terms.end());
292 Terms.erase(CS: llvm::unique(R&: Terms), CE: Terms.end());
293
294 // Put larger terms first.
295 llvm::sort(C&: Terms, Comp: [](const SCEV *LHS, const SCEV *RHS) {
296 return numberOfTerms(S: LHS) > numberOfTerms(S: RHS);
297 });
298
299 // Try to divide all terms by the element size. If term is not divisible by
300 // element size, proceed with the original term.
301 for (const SCEV *&Term : Terms) {
302 const SCEV *Q, *R;
303 SCEVDivision::divide(SE, Numerator: Term, Denominator: ElementSize, Quotient: &Q, Remainder: &R);
304 if (!Q->isZero())
305 Term = Q;
306 }
307
308 SmallVector<const SCEV *, 4> NewTerms;
309
310 // Remove constant factors.
311 for (const SCEV *T : Terms)
312 if (const SCEV *NewT = removeConstantFactors(SE, T))
313 NewTerms.push_back(Elt: NewT);
314
315 LLVM_DEBUG({
316 dbgs() << "Terms after sorting:\n";
317 for (const SCEV *T : NewTerms)
318 dbgs().indent(2) << *T << "\n";
319 });
320
321 if (NewTerms.empty() || !findArrayDimensionsRec(SE, Terms&: NewTerms, Sizes)) {
322 Sizes.clear();
323 return;
324 }
325
326 // The last element to be pushed into Sizes is the size of an element.
327 Sizes.push_back(Elt: ElementSize);
328
329 LLVM_DEBUG({
330 dbgs() << "Sizes:\n";
331 for (const SCEV *S : Sizes)
332 dbgs().indent(2) << *S << "\n";
333 });
334}
335
336void llvm::computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr,
337 SmallVectorImpl<const SCEV *> &Subscripts,
338 SmallVectorImpl<const SCEV *> &Sizes) {
339 // Early exit in case this SCEV is not an affine multivariate function.
340 if (Sizes.empty())
341 return;
342
343 if (auto *AR = dyn_cast<SCEVAddRecExpr>(Val: Expr))
344 if (!AR->isAffine())
345 return;
346
347 // Clear output vector.
348 Subscripts.clear();
349
350 LLVM_DEBUG(dbgs() << "\ncomputeAccessFunctions\n"
351 << "Memory Access Function: " << *Expr << "\n");
352
353 const SCEV *Res = Expr;
354 int Last = Sizes.size() - 1;
355
356 for (int i = Last; i >= 0; i--) {
357 const SCEV *Size = Sizes[i];
358 const SCEV *Q, *R;
359
360 SCEVDivision::divide(SE, Numerator: Res, Denominator: Size, Quotient: &Q, Remainder: &R);
361
362 LLVM_DEBUG({
363 dbgs() << "Computing 'MemAccFn / Sizes[" << i << "]':\n";
364 dbgs() << " MemAccFn: " << *Res << "\n";
365 dbgs() << " Sizes[" << i << "]: " << *Size << "\n";
366 dbgs() << " Quotient (Leftover): " << *Q << "\n";
367 dbgs() << " Remainder (Subscript Access Function): " << *R << "\n";
368 });
369
370 Res = Q;
371
372 // Do not record the last subscript corresponding to the size of elements in
373 // the array.
374 if (i == Last) {
375
376 // Bail out if the byte offset is non-zero.
377 if (!R->isZero()) {
378 Subscripts.clear();
379 Sizes.clear();
380 return;
381 }
382
383 continue;
384 }
385
386 // Record the access function for the current subscript.
387 Subscripts.push_back(Elt: R);
388 }
389
390 // Also push in last position the remainder of the last division: it will be
391 // the access function of the innermost dimension.
392 Subscripts.push_back(Elt: Res);
393
394 std::reverse(first: Subscripts.begin(), last: Subscripts.end());
395
396 LLVM_DEBUG({
397 dbgs() << "Subscripts:\n";
398 for (const SCEV *S : Subscripts)
399 dbgs().indent(2) << *S << "\n";
400 dbgs() << "\n";
401 });
402}
403
404/// Splits the SCEV into two vectors of SCEVs representing the subscripts and
405/// sizes of an array access. Returns the remainder of the delinearization that
406/// is the offset start of the array. The SCEV->delinearize algorithm computes
407/// the multiples of SCEV coefficients: that is a pattern matching of sub
408/// expressions in the stride and base of a SCEV corresponding to the
409/// computation of a GCD (greatest common divisor) of base and stride. When
410/// SCEV->delinearize fails, it returns the SCEV unchanged.
411///
412/// For example: when analyzing the memory access A[i][j][k] in this loop nest
413///
414/// void foo(long n, long m, long o, double A[n][m][o]) {
415///
416/// for (long i = 0; i < n; i++)
417/// for (long j = 0; j < m; j++)
418/// for (long k = 0; k < o; k++)
419/// A[i][j][k] = 1.0;
420/// }
421///
422/// the delinearization input is the following AddRec SCEV:
423///
424/// AddRec: {{{%A,+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
425///
426/// From this SCEV, we are able to say that the base offset of the access is %A
427/// because it appears as an offset that does not divide any of the strides in
428/// the loops:
429///
430/// CHECK: Base offset: %A
431///
432/// and then SCEV->delinearize determines the size of some of the dimensions of
433/// the array as these are the multiples by which the strides are happening:
434///
435/// CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of sizeof(double)
436/// bytes.
437///
438/// Note that the outermost dimension remains of UnknownSize because there are
439/// no strides that would help identifying the size of the last dimension: when
440/// the array has been statically allocated, one could compute the size of that
441/// dimension by dividing the overall size of the array by the size of the known
442/// dimensions: %m * %o * 8.
443///
444/// Finally delinearize provides the access functions for the array reference
445/// that does correspond to A[i][j][k] of the above C testcase:
446///
447/// CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>]
448///
449/// The testcases are checking the output of a function pass:
450/// DelinearizationPass that walks through all loads and stores of a function
451/// asking for the SCEV of the memory access with respect to all enclosing
452/// loops, calling SCEV->delinearize on that and printing the results.
453void llvm::delinearize(ScalarEvolution &SE, const SCEV *Expr,
454 SmallVectorImpl<const SCEV *> &Subscripts,
455 SmallVectorImpl<const SCEV *> &Sizes,
456 const SCEV *ElementSize) {
457 // Clear output vectors.
458 Subscripts.clear();
459 Sizes.clear();
460
461 // First step: collect parametric terms.
462 SmallVector<const SCEV *, 4> Terms;
463 collectParametricTerms(SE, Expr, Terms);
464
465 if (Terms.empty())
466 return;
467
468 // Second step: find subscript sizes.
469 findArrayDimensions(SE, Terms, Sizes, ElementSize);
470
471 if (Sizes.empty())
472 return;
473
474 // Third step: compute the access functions for each subscript.
475 computeAccessFunctions(SE, Expr, Subscripts, Sizes);
476}
477
478static std::optional<APInt> tryIntoAPInt(const SCEV *S) {
479 if (const auto *Const = dyn_cast<SCEVConstant>(Val: S))
480 return Const->getAPInt();
481 return std::nullopt;
482}
483
484/// Collects the absolute values of constant steps for all induction variables.
485/// Returns true if we can prove that all step recurrences are constants and \p
486/// Expr is divisible by \p ElementSize. Each step recurrence is stored in \p
487/// Steps after divided by \p ElementSize.
488static bool collectConstantAbsSteps(ScalarEvolution &SE, const SCEV *Expr,
489 SmallVectorImpl<uint64_t> &Steps,
490 uint64_t ElementSize) {
491 // End of recursion. The constant value also must be a multiple of
492 // ElementSize.
493 if (const auto *Const = dyn_cast<SCEVConstant>(Val: Expr)) {
494 const uint64_t Mod = Const->getAPInt().urem(RHS: ElementSize);
495 return Mod == 0;
496 }
497
498 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: Expr);
499 if (!AR || !AR->isAffine())
500 return false;
501
502 const SCEV *Step = AR->getStepRecurrence(SE);
503 std::optional<APInt> StepAPInt = tryIntoAPInt(S: Step);
504 if (!StepAPInt)
505 return false;
506
507 APInt Q;
508 uint64_t R;
509 APInt::udivrem(LHS: StepAPInt->abs(), RHS: ElementSize, Quotient&: Q, Remainder&: R);
510 if (R != 0)
511 return false;
512
513 // Bail out when the step is too large.
514 std::optional<uint64_t> StepVal = Q.tryZExtValue();
515 if (!StepVal)
516 return false;
517
518 Steps.push_back(Elt: *StepVal);
519 return collectConstantAbsSteps(SE, Expr: AR->getStart(), Steps, ElementSize);
520}
521
522bool llvm::findFixedSizeArrayDimensions(ScalarEvolution &SE, const SCEV *Expr,
523 SmallVectorImpl<uint64_t> &Sizes,
524 const SCEV *ElementSize) {
525 if (!ElementSize)
526 return false;
527
528 std::optional<APInt> ElementSizeAPInt = tryIntoAPInt(S: ElementSize);
529 if (!ElementSizeAPInt || *ElementSizeAPInt == 0)
530 return false;
531
532 std::optional<uint64_t> ElementSizeConst = ElementSizeAPInt->tryZExtValue();
533
534 // Early exit when ElementSize is not a positive constant.
535 if (!ElementSizeConst)
536 return false;
537
538 if (!collectConstantAbsSteps(SE, Expr, Steps&: Sizes, ElementSize: *ElementSizeConst) ||
539 Sizes.empty()) {
540 Sizes.clear();
541 return false;
542 }
543
544 // At this point, Sizes contains the absolute step recurrences for all
545 // induction variables. Each step recurrence must be a multiple of the size of
546 // the array element. Assuming that the each value represents the size of an
547 // array for each dimension, attempts to restore the length of each dimension
548 // by dividing the step recurrence by the next smaller value. For example, if
549 // we have the following AddRec SCEV:
550 //
551 // AddRec: {{{0,+,2048}<%for.i>,+,256}<%for.j>,+,8}<%for.k> (ElementSize=8)
552 //
553 // Then Sizes will become [256, 32, 1] after sorted. We don't know the size of
554 // the outermost dimension, the next dimension will be computed as 256 / 32 =
555 // 8, and the last dimension will be computed as 32 / 1 = 32. Thus it results
556 // in like Arr[UnknownSize][8][32] with elements of size 8 bytes, where Arr is
557 // a base pointer.
558 //
559 // TODO: Catch more cases, e.g., when a step recurrence is not divisible by
560 // the next smaller one, like A[i][3*j].
561 llvm::sort(Start: Sizes.rbegin(), End: Sizes.rend());
562 Sizes.erase(CS: llvm::unique(R&: Sizes), CE: Sizes.end());
563
564 // The last element in Sizes should be ElementSize. At this point, all values
565 // in Sizes are assumed to be divided by ElementSize, so replace it with 1.
566 assert(Sizes.back() != 0 && "Unexpected zero size in Sizes.");
567 Sizes.back() = 1;
568
569 for (unsigned I = 0; I + 1 < Sizes.size(); I++) {
570 uint64_t PrevSize = Sizes[I + 1];
571 if (Sizes[I] % PrevSize) {
572 Sizes.clear();
573 return false;
574 }
575 Sizes[I] /= PrevSize;
576 }
577
578 // Finally, the last element in Sizes should be ElementSize.
579 Sizes.back() = *ElementSizeConst;
580 return true;
581}
582
583/// Splits the SCEV into two vectors of SCEVs representing the subscripts and
584/// sizes of an array access, assuming that the array is a fixed size array.
585///
586/// E.g., if we have the code like as follows:
587///
588/// double A[42][8][32];
589/// for i
590/// for j
591/// for k
592/// use A[i][j][k]
593///
594/// The access function will be represented as an AddRec SCEV like:
595///
596/// AddRec: {{{0,+,2048}<%for.i>,+,256}<%for.j>,+,8}<%for.k> (ElementSize=8)
597///
598/// Then findFixedSizeArrayDimensions infers the size of each dimension of the
599/// array based on the fact that the value of the step recurrence is a multiple
600/// of the size of the corresponding array element. In the above example, it
601/// results in the following:
602///
603/// CHECK: ArrayDecl[UnknownSize][8][32] with elements of 8 bytes.
604///
605/// Finally each subscript will be computed as follows:
606///
607/// CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>]
608///
609/// Note that this function doesn't check the range of possible values for each
610/// subscript, so the caller should perform additional boundary checks if
611/// necessary.
612///
613/// Also note that this function doesn't guarantee that the original array size
614/// is restored "correctly". For example, in the following case:
615///
616/// double A[42][4][64];
617/// double B[42][8][32];
618/// for i
619/// for j
620/// for k
621/// use A[i][j][k]
622/// use B[i][2*j][k]
623///
624/// The access function for both accesses will be the same:
625///
626/// AddRec: {{{0,+,2048}<%for.i>,+,512}<%for.j>,+,8}<%for.k> (ElementSize=8)
627///
628/// The array sizes for both A and B will be computed as
629/// ArrayDecl[UnknownSize][4][64], which matches for A, but not for B.
630///
631/// TODO: At the moment, this function can handle only simple cases. For
632/// example, we cannot handle a case where a step recurrence is not divisible
633/// by the next smaller step recurrence, e.g., A[i][3*j].
634bool llvm::delinearizeFixedSizeArray(ScalarEvolution &SE, const SCEV *Expr,
635 SmallVectorImpl<const SCEV *> &Subscripts,
636 SmallVectorImpl<const SCEV *> &Sizes,
637 const SCEV *ElementSize) {
638 // Clear output vectors.
639 Subscripts.clear();
640 Sizes.clear();
641
642 // First step: find the fixed array size.
643 SmallVector<uint64_t, 4> ConstSizes;
644 if (!findFixedSizeArrayDimensions(SE, Expr, Sizes&: ConstSizes, ElementSize)) {
645 Sizes.clear();
646 return false;
647 }
648
649 // Convert the constant size to SCEV.
650 for (uint64_t Size : ConstSizes)
651 Sizes.push_back(Elt: SE.getConstant(Ty: Expr->getType(), V: Size));
652
653 // Second step: compute the access functions for each subscript.
654 computeAccessFunctions(SE, Expr, Subscripts, Sizes);
655
656 return !Subscripts.empty();
657}
658
659bool llvm::validateDelinearizationResult(ScalarEvolution &SE,
660 ArrayRef<const SCEV *> Sizes,
661 ArrayRef<const SCEV *> Subscripts) {
662 // Sizes and Subscripts are as follows:
663 //
664 // Sizes: [UNK][S_2]...[S_n]
665 // Subscripts: [I_1][I_2]...[I_n]
666 //
667 // where the size of the outermost dimension is unknown (UNK).
668
669 auto AddOverflow = [&](const SCEV *A, const SCEV *B) -> const SCEV * {
670 if (!SE.willNotOverflow(BinOp: Instruction::Add, /*IsSigned=*/Signed: true, LHS: A, RHS: B))
671 return nullptr;
672 return SE.getAddExpr(LHS: A, RHS: B);
673 };
674
675 auto MulOverflow = [&](const SCEV *A, const SCEV *B) -> const SCEV * {
676 if (!SE.willNotOverflow(BinOp: Instruction::Mul, /*IsSigned=*/Signed: true, LHS: A, RHS: B))
677 return nullptr;
678 return SE.getMulExpr(LHS: A, RHS: B);
679 };
680
681 // Range check: 0 <= I_k < S_k for k = 2..n.
682 for (size_t I = 1; I < Sizes.size(); ++I) {
683 const SCEV *Size = Sizes[I - 1];
684 const SCEV *Subscript = Subscripts[I];
685 if (!SE.isKnownNonNegative(S: Subscript))
686 return false;
687
688 // TODO: It may be better that delinearization itself unifies the types of
689 // all elements in Sizes and Subscripts.
690 Type *WiderTy = SE.getWiderType(Ty1: Subscript->getType(), Ty2: Size->getType());
691 Subscript = SE.getNoopOrSignExtend(V: Subscript, Ty: WiderTy);
692 Size = SE.getNoopOrSignExtend(V: Size, Ty: WiderTy);
693 if (!SE.isKnownPredicate(Pred: ICmpInst::ICMP_SLT, LHS: Subscript, RHS: Size)) {
694 LLVM_DEBUG(dbgs() << "Range check failed: " << *Subscript << " <s "
695 << *Size << "\n");
696 return false;
697 }
698 }
699
700 // The offset computation is as follows:
701 //
702 // Offset = I_n +
703 // S_n * I_{n-1} +
704 // ... +
705 // (S_2 * ... * S_n) * I_1
706 //
707 // Regarding this as a function from (I_1, I_2, ..., I_n) to integers, it
708 // must be injective. To guarantee it, the above calculation must not
709 // overflow. Since we have already checked that 0 <= I_k < S_k for k = 2..n,
710 // the minimum and maximum values occur in the following cases:
711 //
712 // Min = [I_1][0]...[0] = S_2 * ... * S_n * I_1
713 // Max = [I_1][S_2-1]...[S_n-1]
714 // = (S_2 * ... * S_n) * I_1 +
715 // (S_2 * ... * S_{n-1}) * (S_2 - 1) +
716 // ... +
717 // (S_n - 1)
718 // = (S_2 * ... * S_n) * I_1 +
719 // (S_2 * ... * S_n) - 1 (can be proven by induction)
720 // = Min + (S_2 * ... * S_n) - 1
721 //
722 // NOTE: I_1 can be negative, so Min is not just 0.
723 const SCEV *Prod = SE.getOne(Ty: Sizes[0]->getType());
724 for (const SCEV *Size : Sizes) {
725 Prod = MulOverflow(Prod, Size);
726 if (!Prod)
727 return false;
728 }
729 const SCEV *Min = MulOverflow(Prod, Subscripts[0]);
730 if (!Min)
731 return false;
732
733 // We have already checked that Min and Prod don't overflow, so it's enough
734 // to check whether Min + Prod - 1 doesn't overflow.
735 const SCEV *MaxPlusOne = AddOverflow(Min, Prod);
736 if (!MaxPlusOne)
737 return false;
738 if (!SE.willNotOverflow(BinOp: Instruction::Sub, /*IsSigned=*/Signed: true, LHS: MaxPlusOne,
739 RHS: SE.getOne(Ty: MaxPlusOne->getType())))
740 return false;
741
742 return true;
743}
744
745bool llvm::getIndexExpressionsFromGEP(ScalarEvolution &SE,
746 const GetElementPtrInst *GEP,
747 SmallVectorImpl<const SCEV *> &Subscripts,
748 SmallVectorImpl<const SCEV *> &Sizes) {
749 assert(Subscripts.empty() && Sizes.empty() &&
750 "Expected output lists to be empty on entry to this function.");
751 assert(GEP && "getIndexExpressionsFromGEP called with a null GEP");
752 LLVM_DEBUG(dbgs() << "\nGEP to delinearize: " << *GEP << "\n");
753 Type *Ty = nullptr;
754 Type *IndexTy = SE.getEffectiveSCEVType(Ty: GEP->getPointerOperandType());
755 bool DroppedFirstDim = false;
756 for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
757 const SCEV *Expr = SE.getSCEV(V: GEP->getOperand(i_nocapture: i));
758 if (i == 1) {
759 Ty = GEP->getSourceElementType();
760 if (auto *Const = dyn_cast<SCEVConstant>(Val: Expr))
761 if (Const->getValue()->isZero()) {
762 DroppedFirstDim = true;
763 continue;
764 }
765 Subscripts.push_back(Elt: Expr);
766 continue;
767 }
768
769 auto *ArrayTy = dyn_cast<ArrayType>(Val: Ty);
770 if (!ArrayTy) {
771 LLVM_DEBUG(dbgs() << "GEP delinearize failed: " << *Ty
772 << " is not an array type.\n");
773 Subscripts.clear();
774 Sizes.clear();
775 return false;
776 }
777
778 Subscripts.push_back(Elt: Expr);
779 if (!(DroppedFirstDim && i == 2))
780 Sizes.push_back(Elt: SE.getConstant(Ty: IndexTy, V: ArrayTy->getNumElements()));
781
782 Ty = ArrayTy->getElementType();
783 }
784 LLVM_DEBUG({
785 dbgs() << "Subscripts:\n";
786 for (const SCEV *S : Subscripts)
787 dbgs() << *S << "\n";
788 dbgs() << "\n";
789 });
790
791 return !Subscripts.empty();
792}
793
794namespace {
795
796void printDelinearization(raw_ostream &O, Function *F, LoopInfo *LI,
797 ScalarEvolution *SE) {
798 O << "Printing analysis 'Delinearization' for function '" << F->getName()
799 << "':";
800 const AnalysisOptions &Opts = getAnalysisOptions(F: *F);
801 for (Instruction &Inst : instructions(F)) {
802 // Only analyze loads and stores.
803 if (!isa<StoreInst>(Val: &Inst) && !isa<LoadInst>(Val: &Inst))
804 continue;
805
806 const BasicBlock *BB = Inst.getParent();
807 Loop *L = LI->getLoopFor(BB);
808 // Only delinearize the memory access in the innermost loop.
809 // Do not analyze memory accesses outside loops.
810 if (!L)
811 continue;
812
813 const SCEV *AccessFn = SE->getSCEVAtScope(V: getPointerOperand(V: &Inst), L);
814
815 const SCEVUnknown *BasePointer =
816 dyn_cast<SCEVUnknown>(Val: SE->getPointerBase(V: AccessFn));
817 // Do not delinearize if we cannot find the base pointer.
818 if (!BasePointer)
819 break;
820 AccessFn = SE->getMinusSCEV(LHS: AccessFn, RHS: BasePointer);
821
822 O << "\n";
823 O << "Inst:" << Inst << "\n";
824 O << "AccessFunction: " << *AccessFn << "\n";
825
826 SmallVector<const SCEV *, 3> Subscripts, Sizes;
827
828 auto IsDelinearizationFailed = [&]() {
829 return Subscripts.size() == 0 || Sizes.size() == 0 ||
830 Subscripts.size() != Sizes.size();
831 };
832
833 delinearize(SE&: *SE, Expr: AccessFn, Subscripts, Sizes, ElementSize: SE->getElementSize(Inst: &Inst));
834 if (Opts.delinearize_use_fixed_size_array_heuristic &&
835 IsDelinearizationFailed()) {
836 Subscripts.clear();
837 Sizes.clear();
838 delinearizeFixedSizeArray(SE&: *SE, Expr: AccessFn, Subscripts, Sizes,
839 ElementSize: SE->getElementSize(Inst: &Inst));
840 }
841
842 if (IsDelinearizationFailed()) {
843 O << "failed to delinearize\n";
844 continue;
845 }
846
847 O << "Base offset: " << *BasePointer << "\n";
848 O << "ArrayDecl[UnknownSize]";
849 int Size = Subscripts.size();
850 for (int i = 0; i < Size - 1; i++)
851 O << "[" << *Sizes[i] << "]";
852 O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
853
854 O << "ArrayRef";
855 for (int i = 0; i < Size; i++)
856 O << "[" << *Subscripts[i] << "]";
857 O << "\n";
858
859 bool IsValid = validateDelinearizationResult(SE&: *SE, Sizes, Subscripts);
860 O << "Delinearization validation: " << (IsValid ? "Succeeded" : "Failed")
861 << "\n";
862 }
863}
864
865} // end anonymous namespace
866
867DelinearizationPrinterPass::DelinearizationPrinterPass(raw_ostream &OS)
868 : OS(OS) {}
869PreservedAnalyses DelinearizationPrinterPass::run(Function &F,
870 FunctionAnalysisManager &AM) {
871 printDelinearization(O&: OS, F: &F, LI: &AM.getResult<LoopAnalysis>(IR&: F),
872 SE: &AM.getResult<ScalarEvolutionAnalysis>(IR&: F));
873 return PreservedAnalyses::all();
874}
875