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