LLVM  14.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/LLVMContext.h"
28 #include "llvm/IR/PassManager.h"
29 #include "llvm/IR/Type.h"
30 #include "llvm/InitializePasses.h"
31 #include "llvm/Pass.h"
32 #include "llvm/Support/Debug.h"
34 
35 using namespace llvm;
36 
37 #define DL_NAME "delinearize"
38 #define DEBUG_TYPE DL_NAME
39 
40 // Return true when S contains at least an undef value.
41 static inline bool containsUndefs(const SCEV *S) {
42  return SCEVExprContains(S, [](const SCEV *S) {
43  if (const auto *SU = dyn_cast<SCEVUnknown>(S))
44  return isa<UndefValue>(SU->getValue());
45  return false;
46  });
47 }
48 
49 namespace {
50 
51 // Collect all steps of SCEV expressions.
52 struct SCEVCollectStrides {
53  ScalarEvolution &SE;
55 
56  SCEVCollectStrides(ScalarEvolution &SE, SmallVectorImpl<const SCEV *> &S)
57  : SE(SE), Strides(S) {}
58 
59  bool follow(const SCEV *S) {
60  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
61  Strides.push_back(AR->getStepRecurrence(SE));
62  return true;
63  }
64 
65  bool isDone() const { return false; }
66 };
67 
68 // Collect all SCEVUnknown and SCEVMulExpr expressions.
69 struct SCEVCollectTerms {
71 
72  SCEVCollectTerms(SmallVectorImpl<const SCEV *> &T) : Terms(T) {}
73 
74  bool follow(const SCEV *S) {
75  if (isa<SCEVUnknown>(S) || isa<SCEVMulExpr>(S) ||
76  isa<SCEVSignExtendExpr>(S)) {
77  if (!containsUndefs(S))
78  Terms.push_back(S);
79 
80  // Stop recursion: once we collected a term, do not walk its operands.
81  return false;
82  }
83 
84  // Keep looking.
85  return true;
86  }
87 
88  bool isDone() const { return false; }
89 };
90 
91 // Check if a SCEV contains an AddRecExpr.
92 struct SCEVHasAddRec {
93  bool &ContainsAddRec;
94 
95  SCEVHasAddRec(bool &ContainsAddRec) : ContainsAddRec(ContainsAddRec) {
96  ContainsAddRec = false;
97  }
98 
99  bool follow(const SCEV *S) {
100  if (isa<SCEVAddRecExpr>(S)) {
101  ContainsAddRec = true;
102 
103  // Stop recursion: once we collected a term, do not walk its operands.
104  return false;
105  }
106 
107  // Keep looking.
108  return true;
109  }
110 
111  bool isDone() const { return false; }
112 };
113 
114 // Find factors that are multiplied with an expression that (possibly as a
115 // subexpression) contains an AddRecExpr. In the expression:
116 //
117 // 8 * (100 + %p * %q * (%a + {0, +, 1}_loop))
118 //
119 // "%p * %q" are factors multiplied by the expression "(%a + {0, +, 1}_loop)"
120 // that contains the AddRec {0, +, 1}_loop. %p * %q are likely to be array size
121 // parameters as they form a product with an induction variable.
122 //
123 // This collector expects all array size parameters to be in the same MulExpr.
124 // It might be necessary to later add support for collecting parameters that are
125 // spread over different nested MulExpr.
126 struct SCEVCollectAddRecMultiplies {
128  ScalarEvolution &SE;
129 
130  SCEVCollectAddRecMultiplies(SmallVectorImpl<const SCEV *> &T,
131  ScalarEvolution &SE)
132  : Terms(T), SE(SE) {}
133 
134  bool follow(const SCEV *S) {
135  if (auto *Mul = dyn_cast<SCEVMulExpr>(S)) {
136  bool HasAddRec = false;
138  for (auto Op : Mul->operands()) {
139  const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(Op);
140  if (Unknown && !isa<CallInst>(Unknown->getValue())) {
141  Operands.push_back(Op);
142  } else if (Unknown) {
143  HasAddRec = true;
144  } else {
145  bool ContainsAddRec = false;
146  SCEVHasAddRec ContiansAddRec(ContainsAddRec);
147  visitAll(Op, ContiansAddRec);
148  HasAddRec |= ContainsAddRec;
149  }
150  }
151  if (Operands.size() == 0)
152  return true;
153 
154  if (!HasAddRec)
155  return false;
156 
157  Terms.push_back(SE.getMulExpr(Operands));
158  // Stop recursion: once we collected a term, do not walk its operands.
159  return false;
160  }
161 
162  // Keep looking.
163  return true;
164  }
165 
166  bool isDone() const { return false; }
167 };
168 
169 } // end anonymous namespace
170 
171 /// Find parametric terms in this SCEVAddRecExpr. We first for parameters in
172 /// two places:
173 /// 1) The strides of AddRec expressions.
174 /// 2) Unknowns that are multiplied with AddRec expressions.
178  SCEVCollectStrides StrideCollector(SE, Strides);
179  visitAll(Expr, StrideCollector);
180 
181  LLVM_DEBUG({
182  dbgs() << "Strides:\n";
183  for (const SCEV *S : Strides)
184  dbgs() << *S << "\n";
185  });
186 
187  for (const SCEV *S : Strides) {
188  SCEVCollectTerms TermCollector(Terms);
189  visitAll(S, TermCollector);
190  }
191 
192  LLVM_DEBUG({
193  dbgs() << "Terms:\n";
194  for (const SCEV *T : Terms)
195  dbgs() << *T << "\n";
196  });
197 
198  SCEVCollectAddRecMultiplies MulCollector(Terms, SE);
199  visitAll(Expr, MulCollector);
200 }
201 
205  int Last = Terms.size() - 1;
206  const SCEV *Step = Terms[Last];
207 
208  // End of recursion.
209  if (Last == 0) {
210  if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Step)) {
212  for (const SCEV *Op : M->operands())
213  if (!isa<SCEVConstant>(Op))
214  Qs.push_back(Op);
215 
216  Step = SE.getMulExpr(Qs);
217  }
218 
219  Sizes.push_back(Step);
220  return true;
221  }
222 
223  for (const SCEV *&Term : Terms) {
224  // Normalize the terms before the next call to findArrayDimensionsRec.
225  const SCEV *Q, *R;
226  SCEVDivision::divide(SE, Term, Step, &Q, &R);
227 
228  // Bail out when GCD does not evenly divide one of the terms.
229  if (!R->isZero())
230  return false;
231 
232  Term = Q;
233  }
234 
235  // Remove all SCEVConstants.
236  erase_if(Terms, [](const SCEV *E) { return isa<SCEVConstant>(E); });
237 
238  if (Terms.size() > 0)
239  if (!findArrayDimensionsRec(SE, Terms, Sizes))
240  return false;
241 
242  Sizes.push_back(Step);
243  return true;
244 }
245 
246 // Returns true when one of the SCEVs of Terms contains a SCEVUnknown parameter.
248  for (const SCEV *T : Terms)
249  if (SCEVExprContains(T, [](const SCEV *S) { return isa<SCEVUnknown>(S); }))
250  return true;
251 
252  return false;
253 }
254 
255 // Return the number of product terms in S.
256 static inline int numberOfTerms(const SCEV *S) {
257  if (const SCEVMulExpr *Expr = dyn_cast<SCEVMulExpr>(S))
258  return Expr->getNumOperands();
259  return 1;
260 }
261 
262 static const SCEV *removeConstantFactors(ScalarEvolution &SE, const SCEV *T) {
263  if (isa<SCEVConstant>(T))
264  return nullptr;
265 
266  if (isa<SCEVUnknown>(T))
267  return T;
268 
269  if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(T)) {
271  for (const SCEV *Op : M->operands())
272  if (!isa<SCEVConstant>(Op))
273  Factors.push_back(Op);
274 
275  return SE.getMulExpr(Factors);
276  }
277 
278  return T;
279 }
280 
284  const SCEV *ElementSize) {
285  if (Terms.size() < 1 || !ElementSize)
286  return;
287 
288  // Early return when Terms do not contain parameters: we do not delinearize
289  // non parametric SCEVs.
290  if (!containsParameters(Terms))
291  return;
292 
293  LLVM_DEBUG({
294  dbgs() << "Terms:\n";
295  for (const SCEV *T : Terms)
296  dbgs() << *T << "\n";
297  });
298 
299  // Remove duplicates.
300  array_pod_sort(Terms.begin(), Terms.end());
301  Terms.erase(std::unique(Terms.begin(), Terms.end()), Terms.end());
302 
303  // Put larger terms first.
304  llvm::sort(Terms, [](const SCEV *LHS, const SCEV *RHS) {
305  return numberOfTerms(LHS) > numberOfTerms(RHS);
306  });
307 
308  // Try to divide all terms by the element size. If term is not divisible by
309  // element size, proceed with the original term.
310  for (const SCEV *&Term : Terms) {
311  const SCEV *Q, *R;
312  SCEVDivision::divide(SE, Term, ElementSize, &Q, &R);
313  if (!Q->isZero())
314  Term = Q;
315  }
316 
318 
319  // Remove constant factors.
320  for (const SCEV *T : Terms)
321  if (const SCEV *NewT = removeConstantFactors(SE, T))
322  NewTerms.push_back(NewT);
323 
324  LLVM_DEBUG({
325  dbgs() << "Terms after sorting:\n";
326  for (const SCEV *T : NewTerms)
327  dbgs() << *T << "\n";
328  });
329 
330  if (NewTerms.empty() || !findArrayDimensionsRec(SE, NewTerms, Sizes)) {
331  Sizes.clear();
332  return;
333  }
334 
335  // The last element to be pushed into Sizes is the size of an element.
336  Sizes.push_back(ElementSize);
337 
338  LLVM_DEBUG({
339  dbgs() << "Sizes:\n";
340  for (const SCEV *S : Sizes)
341  dbgs() << *S << "\n";
342  });
343 }
344 
346  SmallVectorImpl<const SCEV *> &Subscripts,
348  // Early exit in case this SCEV is not an affine multivariate function.
349  if (Sizes.empty())
350  return;
351 
352  if (auto *AR = dyn_cast<SCEVAddRecExpr>(Expr))
353  if (!AR->isAffine())
354  return;
355 
356  const SCEV *Res = Expr;
357  int Last = Sizes.size() - 1;
358  for (int i = Last; i >= 0; i--) {
359  const SCEV *Q, *R;
360  SCEVDivision::divide(SE, Res, Sizes[i], &Q, &R);
361 
362  LLVM_DEBUG({
363  dbgs() << "Res: " << *Res << "\n";
364  dbgs() << "Sizes[i]: " << *Sizes[i] << "\n";
365  dbgs() << "Res divided by Sizes[i]:\n";
366  dbgs() << "Quotient: " << *Q << "\n";
367  dbgs() << "Remainder: " << *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(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(Res);
393 
394  std::reverse(Subscripts.begin(), Subscripts.end());
395 
396  LLVM_DEBUG({
397  dbgs() << "Subscripts:\n";
398  for (const SCEV *S : Subscripts)
399  dbgs() << *S << "\n";
400  });
401 }
402 
403 /// Splits the SCEV into two vectors of SCEVs representing the subscripts and
404 /// sizes of an array access. Returns the remainder of the delinearization that
405 /// is the offset start of the array. The SCEV->delinearize algorithm computes
406 /// the multiples of SCEV coefficients: that is a pattern matching of sub
407 /// expressions in the stride and base of a SCEV corresponding to the
408 /// computation of a GCD (greatest common divisor) of base and stride. When
409 /// SCEV->delinearize fails, it returns the SCEV unchanged.
410 ///
411 /// For example: when analyzing the memory access A[i][j][k] in this loop nest
412 ///
413 /// void foo(long n, long m, long o, double A[n][m][o]) {
414 ///
415 /// for (long i = 0; i < n; i++)
416 /// for (long j = 0; j < m; j++)
417 /// for (long k = 0; k < o; k++)
418 /// A[i][j][k] = 1.0;
419 /// }
420 ///
421 /// the delinearization input is the following AddRec SCEV:
422 ///
423 /// AddRec: {{{%A,+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
424 ///
425 /// From this SCEV, we are able to say that the base offset of the access is %A
426 /// because it appears as an offset that does not divide any of the strides in
427 /// the loops:
428 ///
429 /// CHECK: Base offset: %A
430 ///
431 /// and then SCEV->delinearize determines the size of some of the dimensions of
432 /// the array as these are the multiples by which the strides are happening:
433 ///
434 /// CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of sizeof(double)
435 /// bytes.
436 ///
437 /// Note that the outermost dimension remains of UnknownSize because there are
438 /// no strides that would help identifying the size of the last dimension: when
439 /// the array has been statically allocated, one could compute the size of that
440 /// dimension by dividing the overall size of the array by the size of the known
441 /// dimensions: %m * %o * 8.
442 ///
443 /// Finally delinearize provides the access functions for the array reference
444 /// that does correspond to A[i][j][k] of the above C testcase:
445 ///
446 /// CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>]
447 ///
448 /// The testcases are checking the output of a function pass:
449 /// DelinearizationPass that walks through all loads and stores of a function
450 /// asking for the SCEV of the memory access with respect to all enclosing
451 /// loops, calling SCEV->delinearize on that and printing the results.
452 void llvm::delinearize(ScalarEvolution &SE, const SCEV *Expr,
453  SmallVectorImpl<const SCEV *> &Subscripts,
455  const SCEV *ElementSize) {
456  // First step: collect parametric terms.
458  collectParametricTerms(SE, Expr, Terms);
459 
460  if (Terms.empty())
461  return;
462 
463  // Second step: find subscript sizes.
464  findArrayDimensions(SE, Terms, Sizes, ElementSize);
465 
466  if (Sizes.empty())
467  return;
468 
469  // Third step: compute the access functions for each subscript.
470  computeAccessFunctions(SE, Expr, Subscripts, Sizes);
471 
472  if (Subscripts.empty())
473  return;
474 
475  LLVM_DEBUG({
476  dbgs() << "succeeded to delinearize " << *Expr << "\n";
477  dbgs() << "ArrayDecl[UnknownSize]";
478  for (const SCEV *S : Sizes)
479  dbgs() << "[" << *S << "]";
480 
481  dbgs() << "\nArrayRef";
482  for (const SCEV *S : Subscripts)
483  dbgs() << "[" << *S << "]";
484  dbgs() << "\n";
485  });
486 }
487 
489  const GetElementPtrInst *GEP,
490  SmallVectorImpl<const SCEV *> &Subscripts,
491  SmallVectorImpl<int> &Sizes) {
492  assert(Subscripts.empty() && Sizes.empty() &&
493  "Expected output lists to be empty on entry to this function.");
494  assert(GEP && "getIndexExpressionsFromGEP called with a null GEP");
495  Type *Ty = nullptr;
496  bool DroppedFirstDim = false;
497  for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
498  const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
499  if (i == 1) {
500  Ty = GEP->getSourceElementType();
501  if (auto *Const = dyn_cast<SCEVConstant>(Expr))
502  if (Const->getValue()->isZero()) {
503  DroppedFirstDim = true;
504  continue;
505  }
506  Subscripts.push_back(Expr);
507  continue;
508  }
509 
510  auto *ArrayTy = dyn_cast<ArrayType>(Ty);
511  if (!ArrayTy) {
512  Subscripts.clear();
513  Sizes.clear();
514  return false;
515  }
516 
517  Subscripts.push_back(Expr);
518  if (!(DroppedFirstDim && i == 2))
519  Sizes.push_back(ArrayTy->getNumElements());
520 
521  Ty = ArrayTy->getElementType();
522  }
523  return !Subscripts.empty();
524 }
525 
526 namespace {
527 
528 class Delinearization : public FunctionPass {
529  Delinearization(const Delinearization &); // do not implement
530 protected:
531  Function *F;
532  LoopInfo *LI;
533  ScalarEvolution *SE;
534 
535 public:
536  static char ID; // Pass identification, replacement for typeid
537 
538  Delinearization() : FunctionPass(ID) {
540  }
541  bool runOnFunction(Function &F) override;
542  void getAnalysisUsage(AnalysisUsage &AU) const override;
543  void print(raw_ostream &O, const Module *M = nullptr) const override;
544 };
545 
546 void printDelinearization(raw_ostream &O, Function *F, LoopInfo *LI,
547  ScalarEvolution *SE) {
548  O << "Delinearization on function " << F->getName() << ":\n";
549  for (Instruction &Inst : instructions(F)) {
550  // Only analyze loads and stores.
551  if (!isa<StoreInst>(&Inst) && !isa<LoadInst>(&Inst) &&
552  !isa<GetElementPtrInst>(&Inst))
553  continue;
554 
555  const BasicBlock *BB = Inst.getParent();
556  // Delinearize the memory access as analyzed in all the surrounding loops.
557  // Do not analyze memory accesses outside loops.
558  for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
559  const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(&Inst), L);
560 
561  const SCEVUnknown *BasePointer =
562  dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
563  // Do not delinearize if we cannot find the base pointer.
564  if (!BasePointer)
565  break;
566  AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
567 
568  O << "\n";
569  O << "Inst:" << Inst << "\n";
570  O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
571  O << "AccessFunction: " << *AccessFn << "\n";
572 
573  SmallVector<const SCEV *, 3> Subscripts, Sizes;
574  delinearize(*SE, AccessFn, Subscripts, Sizes, SE->getElementSize(&Inst));
575  if (Subscripts.size() == 0 || Sizes.size() == 0 ||
576  Subscripts.size() != Sizes.size()) {
577  O << "failed to delinearize\n";
578  continue;
579  }
580 
581  O << "Base offset: " << *BasePointer << "\n";
582  O << "ArrayDecl[UnknownSize]";
583  int Size = Subscripts.size();
584  for (int i = 0; i < Size - 1; i++)
585  O << "[" << *Sizes[i] << "]";
586  O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
587 
588  O << "ArrayRef";
589  for (int i = 0; i < Size; i++)
590  O << "[" << *Subscripts[i] << "]";
591  O << "\n";
592  }
593  }
594 }
595 
596 } // end anonymous namespace
597 
598 void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
599  AU.setPreservesAll();
602 }
603 
605  this->F = &F;
606  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
607  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
608  return false;
609 }
610 
611 void Delinearization::print(raw_ostream &O, const Module *) const {
612  printDelinearization(O, F, LI, SE);
613 }
614 
615 char Delinearization::ID = 0;
616 static const char delinearization_name[] = "Delinearization";
618  true)
621 
622 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
623 
625  : OS(OS) {}
628  printDelinearization(OS, &F, &AM.getResult<LoopAnalysis>(F),
630  return PreservedAnalyses::all();
631 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
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:155
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:1499
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2093
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:705
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
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
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:783
InstIterator.h
T
llvm::Function
Definition: Function.h:62
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
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:1168
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:1781
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
llvm::createDelinearizationPass
FunctionPass * createDelinearizationPass()
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1883
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::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:359
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1268
delinearization_name
static const char delinearization_name[]
Definition: Delinearization.cpp:616
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:4408
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:3014
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::visitAll
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
Definition: ScalarEvolutionExpressions.h:680
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
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:286
llvm::Instruction
Definition: Instruction.h:45
llvm::SCEVExprContains
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Definition: ScalarEvolutionExpressions.h:687
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:2123
Type.h
llvm::DelinearizationPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Delinearization.cpp:626
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:175
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:78
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4110
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:77
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:206
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:202
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
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:5324
llvm::pdb::Unknown
@ Unknown
Definition: PDBTypes.h:395
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:967
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:928
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:67
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:281
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::ScalarEvolution::getElementSize
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
Definition: ScalarEvolution.cpp:12358
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:488
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::RecurKind::Mul
@ Mul
Product of integers.
llvm::SCEVDivision::divide
static void divide(ScalarEvolution &SE, const SCEV *Numerator, const SCEV *Denominator, const SCEV **Quotient, const SCEV **Remainder)
Definition: ScalarEvolutionDivision.cpp:57
DL_NAME
#define DL_NAME
Definition: Delinearization.cpp:37
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
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:452
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:4242
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:325
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:352
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:530
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:345
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1541
PassManager.h
llvm::unique
auto unique(Range &&R, Predicate P)
Definition: STLExtras.h:1753
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
removeConstantFactors
static const SCEV * removeConstantFactors(ScalarEvolution &SE, const SCEV *T)
Definition: Delinearization.cpp:262
ScalarEvolutionExpressions.h
Instructions.h
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true, true) FunctionPass *llvm
Definition: Delinearization.cpp:617
Delinearization.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
DerivedTypes.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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:172
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
LLVMContext.h
containsParameters
static bool containsParameters(SmallVectorImpl< const SCEV * > &Terms)
Definition: Delinearization.cpp:247
raw_ostream.h
numberOfTerms
static int numberOfTerms(const SCEV *S)
Definition: Delinearization.cpp:256
containsUndefs
static bool containsUndefs(const SCEV *S)
Definition: Delinearization.cpp:41
llvm::DelinearizationPrinterPass::DelinearizationPrinterPass
DelinearizationPrinterPass(raw_ostream &OS)
Definition: Delinearization.cpp:624
llvm::SCEV::isZero
bool isZero() const
Return true if the expression is a constant zero.
Definition: ScalarEvolution.cpp:407
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:8817
Debug.h
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1243
Passes.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38