LLVM  16.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 
17 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/Analysis/Passes.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/DerivedTypes.h"
24 #include "llvm/IR/Function.h"
25 #include "llvm/IR/InstIterator.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/PassManager.h"
28 #include "llvm/InitializePasses.h"
29 #include "llvm/Pass.h"
30 #include "llvm/Support/Debug.h"
32 
33 using 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.
39 static 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 
47 namespace {
48 
49 // Collect all steps of SCEV expressions.
50 struct SCEVCollectStrides {
51  ScalarEvolution &SE;
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.
67 struct 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.
90 struct 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.
124 struct 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.
254 static inline int numberOfTerms(const SCEV *S) {
255  if (const SCEVMulExpr *Expr = dyn_cast<SCEVMulExpr>(S))
256  return Expr->getNumOperands();
257  return 1;
258 }
259 
260 static 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) {
303  return numberOfTerms(LHS) > numberOfTerms(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 
344  SmallVectorImpl<const SCEV *> &Subscripts,
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.
450 void llvm::delinearize(ScalarEvolution &SE, const SCEV *Expr,
451  SmallVectorImpl<const SCEV *> &Subscripts,
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,
488  SmallVectorImpl<const SCEV *> &Subscripts,
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 
562 namespace {
563 
564 class Delinearization : public FunctionPass {
565  Delinearization(const Delinearization &); // do not implement
566 protected:
567  Function *F;
568  LoopInfo *LI;
569  ScalarEvolution *SE;
570 
571 public:
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 
582 void 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 
634 void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
635  AU.setPreservesAll();
638 }
639 
641  this->F = &F;
642  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
643  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
644  return false;
645 }
646 
647 void Delinearization::print(raw_ostream &O, const Module *) const {
648  printDelinearization(O, F, LI, SE);
649 }
650 
651 char Delinearization::ID = 0;
652 static const char delinearization_name[] = "Delinearization";
654  true)
657 
658 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
659 
661  : OS(OS) {}
664  printDelinearization(OS, &F, &AM.getResult<LoopAnalysis>(F),
666  return PreservedAnalyses::all();
667 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::array_pod_sort
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:1642
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2161
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
InstIterator.h
T
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::PseudoProbeReservedId::Last
@ Last
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::erase_if
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:1997
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::createDelinearizationPass
FunctionPass * createDelinearizationPass()
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1794
ScalarEvolution.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
delinearization_name
static const char delinearization_name[]
Definition: Delinearization.cpp:652
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::ScalarEvolution::getPointerBase
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
Definition: ScalarEvolution.cpp:4718
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::initializeDelinearizationPass
void initializeDelinearizationPass(PassRegistry &)
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::ScalarEvolution::getMulExpr
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.
Definition: ScalarEvolution.cpp:3090
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:114
llvm::visitAll
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
Definition: ScalarEvolutionExpressions.h:723
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
ScalarEvolutionDivision.h
llvm::SCEVMulExpr
This node represents multiplication of some number of SCEVs.
Definition: ScalarEvolutionExpressions.h:281
llvm::tryDelinearizeFixedSizeImpl
bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Implementation of fixed size array delinearization.
Definition: Delinearization.cpp:524
llvm::Instruction
Definition: Instruction.h:42
llvm::SCEVExprContains
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Definition: ScalarEvolutionExpressions.h:730
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2191
llvm::SCEVUnknown::getValue
Value * getValue() const
Definition: ScalarEvolutionExpressions.h:592
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::DelinearizationPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Delinearization.cpp:662
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
llvm::collectParametricTerms
void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Terms)
Collect parametric terms occurring in step expressions (first step of delinearization).
Definition: Delinearization.cpp:173
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:74
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4442
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1682
llvm::logicalview::LVPrintKind::Sizes
@ Sizes
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:264
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
findArrayDimensionsRec
static bool findArrayDimensionsRec(ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes)
Definition: Delinearization.cpp:200
llvm::getPointerOperand
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
Definition: Instructions.h:5372
llvm::pdb::Unknown
@ Unknown
Definition: PDBTypes.h:396
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:929
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::print
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Definition: GCNRegPressure.cpp:138
llvm::findArrayDimensions
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...
Definition: Delinearization.cpp:279
llvm::LoopInfo
Definition: LoopInfo.h:1108
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
llvm::ScalarEvolution::getElementSize
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
Definition: ScalarEvolution.cpp:13247
llvm::getIndexExpressionsFromGEP
bool getIndexExpressionsFromGEP(ScalarEvolution &SE, const GetElementPtrInst *GEP, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Gathers the individual index expressions from a GEP instruction.
Definition: Delinearization.cpp:486
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:685
llvm::SCEVDivision::divide
static void divide(ScalarEvolution &SE, const SCEV *Numerator, const SCEV *Denominator, const SCEV **Quotient, const SCEV **Remainder)
Definition: ScalarEvolutionDivision.cpp:55
DL_NAME
#define DL_NAME
Definition: Delinearization.cpp:35
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::delinearize
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...
Definition: Delinearization.cpp:450
llvm::ScalarEvolution::getMinusSCEV
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
Definition: ScalarEvolution.cpp:4550
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:351
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:342
Function.h
llvm::SCEVUnknown
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
Definition: ScalarEvolutionExpressions.h:571
llvm::computeAccessFunctions
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)...
Definition: Delinearization.cpp:343
PassManager.h
llvm::unique
auto unique(Range &&R, Predicate P)
Definition: STLExtras.h:1965
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
removeConstantFactors
static const SCEV * removeConstantFactors(ScalarEvolution &SE, const SCEV *T)
Definition: Delinearization.cpp:260
ScalarEvolutionExpressions.h
Instructions.h
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true, true) FunctionPass *llvm
Definition: Delinearization.cpp:653
Delinearization.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
DerivedTypes.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::getLoadStorePointerOperand
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
Definition: Instructions.h:5358
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
containsParameters
static bool containsParameters(SmallVectorImpl< const SCEV * > &Terms)
Definition: Delinearization.cpp:245
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
raw_ostream.h
numberOfTerms
static int numberOfTerms(const SCEV *S)
Definition: Delinearization.cpp:254
containsUndefs
static bool containsUndefs(const SCEV *S)
Definition: Delinearization.cpp:39
llvm::DelinearizationPrinterPass::DelinearizationPrinterPass
DelinearizationPrinterPass(raw_ostream &OS)
Definition: Delinearization.cpp:660
llvm::SCEV::isZero
bool isZero() const
Return true if the expression is a constant zero.
Definition: ScalarEvolution.cpp:435
InitializePasses.h
llvm::ScalarEvolution::getSCEVAtScope
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
Definition: ScalarEvolution.cpp:9647
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
Passes.h