LLVM  15.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 (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 
524 namespace {
525 
526 class Delinearization : public FunctionPass {
527  Delinearization(const Delinearization &); // do not implement
528 protected:
529  Function *F;
530  LoopInfo *LI;
531  ScalarEvolution *SE;
532 
533 public:
534  static char ID; // Pass identification, replacement for typeid
535 
536  Delinearization() : FunctionPass(ID) {
538  }
539  bool runOnFunction(Function &F) override;
540  void getAnalysisUsage(AnalysisUsage &AU) const override;
541  void print(raw_ostream &O, const Module *M = nullptr) const override;
542 };
543 
544 void printDelinearization(raw_ostream &O, Function *F, LoopInfo *LI,
545  ScalarEvolution *SE) {
546  O << "Delinearization on function " << F->getName() << ":\n";
547  for (Instruction &Inst : instructions(F)) {
548  // Only analyze loads and stores.
549  if (!isa<StoreInst>(&Inst) && !isa<LoadInst>(&Inst) &&
550  !isa<GetElementPtrInst>(&Inst))
551  continue;
552 
553  const BasicBlock *BB = Inst.getParent();
554  // Delinearize the memory access as analyzed in all the surrounding loops.
555  // Do not analyze memory accesses outside loops.
556  for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
557  const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(&Inst), L);
558 
559  const SCEVUnknown *BasePointer =
560  dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
561  // Do not delinearize if we cannot find the base pointer.
562  if (!BasePointer)
563  break;
564  AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
565 
566  O << "\n";
567  O << "Inst:" << Inst << "\n";
568  O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
569  O << "AccessFunction: " << *AccessFn << "\n";
570 
571  SmallVector<const SCEV *, 3> Subscripts, Sizes;
572  delinearize(*SE, AccessFn, Subscripts, Sizes, SE->getElementSize(&Inst));
573  if (Subscripts.size() == 0 || Sizes.size() == 0 ||
574  Subscripts.size() != Sizes.size()) {
575  O << "failed to delinearize\n";
576  continue;
577  }
578 
579  O << "Base offset: " << *BasePointer << "\n";
580  O << "ArrayDecl[UnknownSize]";
581  int Size = Subscripts.size();
582  for (int i = 0; i < Size - 1; i++)
583  O << "[" << *Sizes[i] << "]";
584  O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
585 
586  O << "ArrayRef";
587  for (int i = 0; i < Size; i++)
588  O << "[" << *Subscripts[i] << "]";
589  O << "\n";
590  }
591  }
592 }
593 
594 } // end anonymous namespace
595 
596 void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
597  AU.setPreservesAll();
600 }
601 
603  this->F = &F;
604  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
605  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
606  return false;
607 }
608 
609 void Delinearization::print(raw_ostream &O, const Module *) const {
610  printDelinearization(O, F, LI, SE);
611 }
612 
613 char Delinearization::ID = 0;
614 static const char delinearization_name[] = "Delinearization";
616  true)
619 
620 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
621 
623  : OS(OS) {}
626  printDelinearization(OS, &F, &AM.getResult<LoopAnalysis>(F),
628  return PreservedAnalyses::all();
629 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:76
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:1508
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2115
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:724
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:152
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:780
InstIterator.h
llvm::Function
Definition: Function.h:60
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:1185
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:1795
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::createDelinearizationPass
FunctionPass * createDelinearizationPass()
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1909
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:380
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1271
T
#define T
Definition: Mips16ISelLowering.cpp:341
delinearization_name
static const char delinearization_name[]
Definition: Delinearization.cpp:614
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:4683
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:3043
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:113
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: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:281
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:54
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2145
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:624
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:4398
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:239
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:5344
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:970
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::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:1086
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:12798
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::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: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: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:4515
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
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:337
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
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1550
PassManager.h
llvm::unique
auto unique(Range &&R, Predicate P)
Definition: STLExtras.h:1767
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
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:615
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
DerivedTypes.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
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:172
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
containsParameters
static bool containsParameters(SmallVectorImpl< const SCEV * > &Terms)
Definition: Delinearization.cpp:245
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:622
llvm::SCEV::isZero
bool isZero() const
Return true if the expression is a constant zero.
Definition: ScalarEvolution.cpp:425
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:9211
Debug.h
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1246
Passes.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37