LLVM 18.0.0git
Delinearization.cpp
Go to the documentation of this file.
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. This pass is
11// only used for testing purposes: if your pass needs delinearization, please
12// use the on-demand SCEVAddRecExpr::delinearize() function.
13//
14//===----------------------------------------------------------------------===//
15
22#include "llvm/IR/Constants.h"
24#include "llvm/IR/Function.h"
27#include "llvm/IR/PassManager.h"
29#include "llvm/Pass.h"
30#include "llvm/Support/Debug.h"
32
33using namespace llvm;
34
35#define DL_NAME "delinearize"
36#define DEBUG_TYPE DL_NAME
37
38// Return true when S contains at least an undef value.
39static inline bool containsUndefs(const SCEV *S) {
40 return SCEVExprContains(S, [](const SCEV *S) {
41 if (const auto *SU = dyn_cast<SCEVUnknown>(S))
42 return isa<UndefValue>(SU->getValue());
43 return false;
44 });
45}
46
47namespace {
48
49// Collect all steps of SCEV expressions.
50struct SCEVCollectStrides {
53
54 SCEVCollectStrides(ScalarEvolution &SE, SmallVectorImpl<const SCEV *> &S)
55 : SE(SE), Strides(S) {}
56
57 bool follow(const SCEV *S) {
58 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
59 Strides.push_back(AR->getStepRecurrence(SE));
60 return true;
61 }
62
63 bool isDone() const { return false; }
64};
65
66// Collect all SCEVUnknown and SCEVMulExpr expressions.
67struct SCEVCollectTerms {
69
70 SCEVCollectTerms(SmallVectorImpl<const SCEV *> &T) : Terms(T) {}
71
72 bool follow(const SCEV *S) {
73 if (isa<SCEVUnknown>(S) || isa<SCEVMulExpr>(S) ||
74 isa<SCEVSignExtendExpr>(S)) {
75 if (!containsUndefs(S))
76 Terms.push_back(S);
77
78 // Stop recursion: once we collected a term, do not walk its operands.
79 return false;
80 }
81
82 // Keep looking.
83 return true;
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>(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 {
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>(S)) {
134 bool HasAddRec = false;
136 for (const auto *Op : Mul->operands()) {
137 const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(Op);
138 if (Unknown && !isa<CallInst>(Unknown->getValue())) {
139 Operands.push_back(Op);
140 } else if (Unknown) {
141 HasAddRec = true;
142 } else {
143 bool ContainsAddRec = false;
144 SCEVHasAddRec ContiansAddRec(ContainsAddRec);
145 visitAll(Op, 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(SE.getMulExpr(Operands));
156 // Stop recursion: once we collected a term, do not walk its operands.
157 return false;
158 }
159
160 // Keep looking.
161 return true;
162 }
163
164 bool isDone() const { return false; }
165};
166
167} // end anonymous namespace
168
169/// Find parametric terms in this SCEVAddRecExpr. We first for parameters in
170/// two places:
171/// 1) The strides of AddRec expressions.
172/// 2) Unknowns that are multiplied with AddRec expressions.
176 SCEVCollectStrides StrideCollector(SE, Strides);
177 visitAll(Expr, StrideCollector);
178
179 LLVM_DEBUG({
180 dbgs() << "Strides:\n";
181 for (const SCEV *S : Strides)
182 dbgs() << *S << "\n";
183 });
184
185 for (const SCEV *S : Strides) {
186 SCEVCollectTerms TermCollector(Terms);
187 visitAll(S, TermCollector);
188 }
189
190 LLVM_DEBUG({
191 dbgs() << "Terms:\n";
192 for (const SCEV *T : Terms)
193 dbgs() << *T << "\n";
194 });
195
196 SCEVCollectAddRecMultiplies MulCollector(Terms, SE);
197 visitAll(Expr, MulCollector);
198}
199
203 int Last = Terms.size() - 1;
204 const SCEV *Step = Terms[Last];
205
206 // End of recursion.
207 if (Last == 0) {
208 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Step)) {
210 for (const SCEV *Op : M->operands())
211 if (!isa<SCEVConstant>(Op))
212 Qs.push_back(Op);
213
214 Step = SE.getMulExpr(Qs);
215 }
216
217 Sizes.push_back(Step);
218 return true;
219 }
220
221 for (const SCEV *&Term : Terms) {
222 // Normalize the terms before the next call to findArrayDimensionsRec.
223 const SCEV *Q, *R;
224 SCEVDivision::divide(SE, Term, Step, &Q, &R);
225
226 // Bail out when GCD does not evenly divide one of the terms.
227 if (!R->isZero())
228 return false;
229
230 Term = Q;
231 }
232
233 // Remove all SCEVConstants.
234 erase_if(Terms, [](const SCEV *E) { return isa<SCEVConstant>(E); });
235
236 if (Terms.size() > 0)
237 if (!findArrayDimensionsRec(SE, Terms, Sizes))
238 return false;
239
240 Sizes.push_back(Step);
241 return true;
242}
243
244// Returns true when one of the SCEVs of Terms contains a SCEVUnknown parameter.
246 for (const SCEV *T : Terms)
247 if (SCEVExprContains(T, [](const SCEV *S) { return isa<SCEVUnknown>(S); }))
248 return true;
249
250 return false;
251}
252
253// Return the number of product terms in S.
254static inline int numberOfTerms(const SCEV *S) {
255 if (const SCEVMulExpr *Expr = dyn_cast<SCEVMulExpr>(S))
256 return Expr->getNumOperands();
257 return 1;
258}
259
260static const SCEV *removeConstantFactors(ScalarEvolution &SE, const SCEV *T) {
261 if (isa<SCEVConstant>(T))
262 return nullptr;
263
264 if (isa<SCEVUnknown>(T))
265 return T;
266
267 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(T)) {
269 for (const SCEV *Op : M->operands())
270 if (!isa<SCEVConstant>(Op))
271 Factors.push_back(Op);
272
273 return SE.getMulExpr(Factors);
274 }
275
276 return T;
277}
278
282 const SCEV *ElementSize) {
283 if (Terms.size() < 1 || !ElementSize)
284 return;
285
286 // Early return when Terms do not contain parameters: we do not delinearize
287 // non parametric SCEVs.
288 if (!containsParameters(Terms))
289 return;
290
291 LLVM_DEBUG({
292 dbgs() << "Terms:\n";
293 for (const SCEV *T : Terms)
294 dbgs() << *T << "\n";
295 });
296
297 // Remove duplicates.
298 array_pod_sort(Terms.begin(), Terms.end());
299 Terms.erase(std::unique(Terms.begin(), Terms.end()), Terms.end());
300
301 // Put larger terms first.
302 llvm::sort(Terms, [](const SCEV *LHS, const SCEV *RHS) {
304 });
305
306 // Try to divide all terms by the element size. If term is not divisible by
307 // element size, proceed with the original term.
308 for (const SCEV *&Term : Terms) {
309 const SCEV *Q, *R;
310 SCEVDivision::divide(SE, Term, ElementSize, &Q, &R);
311 if (!Q->isZero())
312 Term = Q;
313 }
314
316
317 // Remove constant factors.
318 for (const SCEV *T : Terms)
319 if (const SCEV *NewT = removeConstantFactors(SE, T))
320 NewTerms.push_back(NewT);
321
322 LLVM_DEBUG({
323 dbgs() << "Terms after sorting:\n";
324 for (const SCEV *T : NewTerms)
325 dbgs() << *T << "\n";
326 });
327
328 if (NewTerms.empty() || !findArrayDimensionsRec(SE, NewTerms, Sizes)) {
329 Sizes.clear();
330 return;
331 }
332
333 // The last element to be pushed into Sizes is the size of an element.
334 Sizes.push_back(ElementSize);
335
336 LLVM_DEBUG({
337 dbgs() << "Sizes:\n";
338 for (const SCEV *S : Sizes)
339 dbgs() << *S << "\n";
340 });
341}
342
346 // Early exit in case this SCEV is not an affine multivariate function.
347 if (Sizes.empty())
348 return;
349
350 if (auto *AR = dyn_cast<SCEVAddRecExpr>(Expr))
351 if (!AR->isAffine())
352 return;
353
354 const SCEV *Res = Expr;
355 int Last = Sizes.size() - 1;
356 for (int i = Last; i >= 0; i--) {
357 const SCEV *Q, *R;
358 SCEVDivision::divide(SE, Res, Sizes[i], &Q, &R);
359
360 LLVM_DEBUG({
361 dbgs() << "Res: " << *Res << "\n";
362 dbgs() << "Sizes[i]: " << *Sizes[i] << "\n";
363 dbgs() << "Res divided by Sizes[i]:\n";
364 dbgs() << "Quotient: " << *Q << "\n";
365 dbgs() << "Remainder: " << *R << "\n";
366 });
367
368 Res = Q;
369
370 // Do not record the last subscript corresponding to the size of elements in
371 // the array.
372 if (i == Last) {
373
374 // Bail out if the byte offset is non-zero.
375 if (!R->isZero()) {
376 Subscripts.clear();
377 Sizes.clear();
378 return;
379 }
380
381 continue;
382 }
383
384 // Record the access function for the current subscript.
385 Subscripts.push_back(R);
386 }
387
388 // Also push in last position the remainder of the last division: it will be
389 // the access function of the innermost dimension.
390 Subscripts.push_back(Res);
391
392 std::reverse(Subscripts.begin(), Subscripts.end());
393
394 LLVM_DEBUG({
395 dbgs() << "Subscripts:\n";
396 for (const SCEV *S : Subscripts)
397 dbgs() << *S << "\n";
398 });
399}
400
401/// Splits the SCEV into two vectors of SCEVs representing the subscripts and
402/// sizes of an array access. Returns the remainder of the delinearization that
403/// is the offset start of the array. The SCEV->delinearize algorithm computes
404/// the multiples of SCEV coefficients: that is a pattern matching of sub
405/// expressions in the stride and base of a SCEV corresponding to the
406/// computation of a GCD (greatest common divisor) of base and stride. When
407/// SCEV->delinearize fails, it returns the SCEV unchanged.
408///
409/// For example: when analyzing the memory access A[i][j][k] in this loop nest
410///
411/// void foo(long n, long m, long o, double A[n][m][o]) {
412///
413/// for (long i = 0; i < n; i++)
414/// for (long j = 0; j < m; j++)
415/// for (long k = 0; k < o; k++)
416/// A[i][j][k] = 1.0;
417/// }
418///
419/// the delinearization input is the following AddRec SCEV:
420///
421/// AddRec: {{{%A,+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
422///
423/// From this SCEV, we are able to say that the base offset of the access is %A
424/// because it appears as an offset that does not divide any of the strides in
425/// the loops:
426///
427/// CHECK: Base offset: %A
428///
429/// and then SCEV->delinearize determines the size of some of the dimensions of
430/// the array as these are the multiples by which the strides are happening:
431///
432/// CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of sizeof(double)
433/// bytes.
434///
435/// Note that the outermost dimension remains of UnknownSize because there are
436/// no strides that would help identifying the size of the last dimension: when
437/// the array has been statically allocated, one could compute the size of that
438/// dimension by dividing the overall size of the array by the size of the known
439/// dimensions: %m * %o * 8.
440///
441/// Finally delinearize provides the access functions for the array reference
442/// that does correspond to A[i][j][k] of the above C testcase:
443///
444/// CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>]
445///
446/// The testcases are checking the output of a function pass:
447/// DelinearizationPass that walks through all loads and stores of a function
448/// asking for the SCEV of the memory access with respect to all enclosing
449/// loops, calling SCEV->delinearize on that and printing the results.
453 const SCEV *ElementSize) {
454 // First step: collect parametric terms.
456 collectParametricTerms(SE, Expr, Terms);
457
458 if (Terms.empty())
459 return;
460
461 // Second step: find subscript sizes.
462 findArrayDimensions(SE, Terms, Sizes, ElementSize);
463
464 if (Sizes.empty())
465 return;
466
467 // Third step: compute the access functions for each subscript.
468 computeAccessFunctions(SE, Expr, Subscripts, Sizes);
469
470 if (Subscripts.empty())
471 return;
472
473 LLVM_DEBUG({
474 dbgs() << "succeeded to delinearize " << *Expr << "\n";
475 dbgs() << "ArrayDecl[UnknownSize]";
476 for (const SCEV *S : Sizes)
477 dbgs() << "[" << *S << "]";
478
479 dbgs() << "\nArrayRef";
480 for (const SCEV *S : Subscripts)
481 dbgs() << "[" << *S << "]";
482 dbgs() << "\n";
483 });
484}
485
487 const GetElementPtrInst *GEP,
489 SmallVectorImpl<int> &Sizes) {
490 assert(Subscripts.empty() && Sizes.empty() &&
491 "Expected output lists to be empty on entry to this function.");
492 assert(GEP && "getIndexExpressionsFromGEP called with a null GEP");
493 Type *Ty = nullptr;
494 bool DroppedFirstDim = false;
495 for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
496 const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
497 if (i == 1) {
498 Ty = GEP->getSourceElementType();
499 if (auto *Const = dyn_cast<SCEVConstant>(Expr))
500 if (Const->getValue()->isZero()) {
501 DroppedFirstDim = true;
502 continue;
503 }
504 Subscripts.push_back(Expr);
505 continue;
506 }
507
508 auto *ArrayTy = dyn_cast<ArrayType>(Ty);
509 if (!ArrayTy) {
510 Subscripts.clear();
511 Sizes.clear();
512 return false;
513 }
514
515 Subscripts.push_back(Expr);
516 if (!(DroppedFirstDim && i == 2))
517 Sizes.push_back(ArrayTy->getNumElements());
518
519 Ty = ArrayTy->getElementType();
520 }
521 return !Subscripts.empty();
522}
523
525 ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn,
527 Value *SrcPtr = getLoadStorePointerOperand(Inst);
528
529 // Check the simple case where the array dimensions are fixed size.
530 auto *SrcGEP = dyn_cast<GetElementPtrInst>(SrcPtr);
531 if (!SrcGEP)
532 return false;
533
534 getIndexExpressionsFromGEP(*SE, SrcGEP, Subscripts, Sizes);
535
536 // Check that the two size arrays are non-empty and equal in length and
537 // value.
538 // TODO: it would be better to let the caller to clear Subscripts, similar
539 // to how we handle Sizes.
540 if (Sizes.empty() || Subscripts.size() <= 1) {
541 Subscripts.clear();
542 return false;
543 }
544
545 // Check that for identical base pointers we do not miss index offsets
546 // that have been added before this GEP is applied.
547 Value *SrcBasePtr = SrcGEP->getOperand(0)->stripPointerCasts();
548 const SCEVUnknown *SrcBase =
549 dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
550 if (!SrcBase || SrcBasePtr != SrcBase->getValue()) {
551 Subscripts.clear();
552 return false;
553 }
554
555 assert(Subscripts.size() == Sizes.size() + 1 &&
556 "Expected equal number of entries in the list of size and "
557 "subscript.");
558
559 return true;
560}
561
562namespace {
563
564class Delinearization : public FunctionPass {
565 Delinearization(const Delinearization &); // do not implement
566protected:
567 Function *F;
568 LoopInfo *LI;
569 ScalarEvolution *SE;
570
571public:
572 static char ID; // Pass identification, replacement for typeid
573
574 Delinearization() : FunctionPass(ID) {
576 }
577 bool runOnFunction(Function &F) override;
578 void getAnalysisUsage(AnalysisUsage &AU) const override;
579 void print(raw_ostream &O, const Module *M = nullptr) const override;
580};
581
582void printDelinearization(raw_ostream &O, Function *F, LoopInfo *LI,
583 ScalarEvolution *SE) {
584 O << "Delinearization on function " << F->getName() << ":\n";
585 for (Instruction &Inst : instructions(F)) {
586 // Only analyze loads and stores.
587 if (!isa<StoreInst>(&Inst) && !isa<LoadInst>(&Inst) &&
588 !isa<GetElementPtrInst>(&Inst))
589 continue;
590
591 const BasicBlock *BB = Inst.getParent();
592 // Delinearize the memory access as analyzed in all the surrounding loops.
593 // Do not analyze memory accesses outside loops.
594 for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
595 const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(&Inst), L);
596
597 const SCEVUnknown *BasePointer =
598 dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
599 // Do not delinearize if we cannot find the base pointer.
600 if (!BasePointer)
601 break;
602 AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
603
604 O << "\n";
605 O << "Inst:" << Inst << "\n";
606 O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
607 O << "AccessFunction: " << *AccessFn << "\n";
608
610 delinearize(*SE, AccessFn, Subscripts, Sizes, SE->getElementSize(&Inst));
611 if (Subscripts.size() == 0 || Sizes.size() == 0 ||
612 Subscripts.size() != Sizes.size()) {
613 O << "failed to delinearize\n";
614 continue;
615 }
616
617 O << "Base offset: " << *BasePointer << "\n";
618 O << "ArrayDecl[UnknownSize]";
619 int Size = Subscripts.size();
620 for (int i = 0; i < Size - 1; i++)
621 O << "[" << *Sizes[i] << "]";
622 O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
623
624 O << "ArrayRef";
625 for (int i = 0; i < Size; i++)
626 O << "[" << *Subscripts[i] << "]";
627 O << "\n";
628 }
629 }
630}
631
632} // end anonymous namespace
633
634void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
635 AU.setPreservesAll();
638}
639
640bool Delinearization::runOnFunction(Function &F) {
641 this->F = &F;
642 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
643 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
644 return false;
645}
646
647void Delinearization::print(raw_ostream &O, const Module *) const {
648 printDelinearization(O, F, LI, SE);
649}
650
651char Delinearization::ID = 0;
652static const char delinearization_name[] = "Delinearization";
654 true)
657
658FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
659
661 : OS(OS) {}
664 printDelinearization(OS, &F, &AM.getResult<LoopAnalysis>(F),
666 return PreservedAnalyses::all();
667}
basic Basic Alias true
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
#define DL_NAME
static const SCEV * removeConstantFactors(ScalarEvolution &SE, const SCEV *T)
static const char delinearization_name[]
static bool findArrayDimensionsRec(ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes)
static bool containsUndefs(const SCEV *S)
static bool containsParameters(SmallVectorImpl< const SCEV * > &Terms)
static int numberOfTerms(const SCEV *S)
uint64_t Size
Hexagon Common GEP
Select target instructions out of generic instructions
#define F(x, y, z)
Definition: MD5.cpp:55
mir Rename Register Operands
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
Value * RHS
Value * LHS
BinaryOperator * Mul
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
This class represents an Operation in the Expression.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:940
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:569
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:594
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:130
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
This node represents a polynomial recurrence on the trip count of the specified loop.
This node represents multiplication of some number of SCEVs.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an analyzed expression in the program.
bool isZero() const
Return true if the expression is a constant zero.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
op_range operands()
Definition: User.h:242
LLVM Value Representation.
Definition: Value.h:74
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:688
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Terms)
Collect parametric terms occurring in step expressions (first step of delinearization).
void findArrayDimensions(ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)
Compute the array dimensions Sizes from the set of Terms extracted from the memory access function of...
FunctionPass * createDelinearizationPass()
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
void computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes)
Return in Subscripts the access functions for each dimension in Sizes (third step of delinearization)...
void initializeDelinearizationPass(PassRegistry &)
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1652
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool getIndexExpressionsFromGEP(ScalarEvolution &SE, const GetElementPtrInst *GEP, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Gathers the individual index expressions from a GEP instruction.
bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Implementation of fixed size array delinearization.
void delinearize(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)
Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an array...
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:2021
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:1612
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static void divide(ScalarEvolution &SE, const SCEV *Numerator, const SCEV *Denominator, const SCEV **Quotient, const SCEV **Remainder)