search for: delinear

Hi all, I have been looking at the `DependenceAnalysis` pass in `llvm/include/llvm/Analysis/DependenceAnalysis.h`. In order for this analysis to produce accurate dependence vectors for multi-dimensional arrays in nested loops, it needs to "delinearize" array element accesses to recover the subscripts in each dimension of the array. I believe that the current implementation of delinearization is based on this paper: http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf. This paper describes how to delinearize the subscripts, a...

...al intended shape of the array may have been > something other than a[n][m], and that we are indexing it such that the > accesses are in-bound with respect to the memory of the whole array but not > with respect to individual dimensions, then I'm not sure we can reason > about *any* delinearization statically (except for the limited cases where > the bounds are compile-time known). > > Am I misunderstanding the issue? > > Bardia Mahjour > Compiler Optimizations > Hydra Squad Lead > IBM Toronto Software Lab > bmahjour at ca.ibm.com (905) 413-2336 > >...

Hello Yes, I agree that the SCEV cannot be simplified. Is my understanding correct that it is passed to a function like "isKnownNegative"? Which could still be able to prove is always true. The delinearisation may be valid, depending on exactly how you define delinearisation (under what conditions it should be giving results). It would be invalid for DA to return a dependency of [0 >] though. The code is perfectly valid from the C or llvm-ir specifications and we can't change the meaning of...

...ern is that the actual intended shape of the array may have been something other than a[n][m], and that we are indexing it such that the accesses are in-bound with respect to the memory of the whole array but not with respect to individual dimensions, then I'm not sure we can reason about *any* delinearization statically (except for the limited cases where the bounds are compile-time known). Am I misunderstanding the issue? Bardia Mahjour Compiler Optimizations Hydra Squad Lead IBM Toronto Software Lab bmahjour at ca.ibm.com (905) 413-2336 From: David Green <David.Green at arm.com> To...

...g/D35430 > Review URL says "GEP" based approach was wrong for multidimensional array > references. The LLVM-DA now uses SCEV representation. But why we are not > getting the distance with SCEV? Current DA will not work for > multidimensional arrays? > It should work with delinearization of multi-dim arrays. > > I need to get dependence distance for a transformation that I am working > on. How do I get distance for such cases, esp multidimensional arrays? > > Thanks and regards, > Venkat. > > On Tue, 18 Sep 2018 at 19:00, Venkataramanan Kumar <...

[CC bollu, mferguson, shil] Am Do., 23. Mai 2019 um 17:13 Uhr schrieb Bardia Mahjour < bmahjour at ca.ibm.com>: > Thanks David and Michael for the clarification. > > I think I understand the rational behind those checks in delinearization > now. > > > Some other languages have stronger guarantees about their array > dimensions accesses being in range. But this being a flat C array, there is > nothing out-of-bounds going on. > > Hmm...perhaps some information about these guarantees can come from the IR...

Hi Ees, SCEV Delinearization is the closest I know. But it has its problems. Well for one your expression should be SCEVable. But more importantly, SCEV Delinearization is trying to deduce something that is high-level (actually source-level) from a low-level IR in which a lot of this info has been lost. So, since there...

...linearized array: > > int *C = alloca(sizeof(int) * m * n); > C[x + m*y]; > > This is intended to have two dimensions, but appear as just one in the > LLVM-IR. The following (C99 VLA) is compiled to approximately the same > LLVM-IR > > int C[n][m]; > C[y][x]; > > Delinearization as mentioned by Stefanos tries to recover the two > subscripts x and y, but can only do so heuristically. Also keep in mind > that > C[1][-1] appears as the same IR as C[0][m-1], so there is no unique way to > delinerarize. In particular, one cannot just assume that if all indice...

...on in one place. Define in include/llvm/IR/Instructions.h as an inline function? Declare in include/llvm/IR/Instructions.h and define in lib/IR/Instructions.cpp? New files? (e.g., IR/InstructionUtils.h and .cpp?) Other suggesctions? I suggest taking the implementation from Analysis/Delinearization.cpp, and create IR/InstructionUtils.h and .cpp. They can then be used to consolidate other Instruction helper functions to one place. Objections? Alternatives? Thanks, Hideki ----------- Relevant background info http://lists.llvm.org/pipermail/llvm-dev/2018-January/120164.html if anyone is...

Hi everyone, I've been using SCEV Delinearization but it fails when other-than-pointer-size values are used in the subscripts. To make that clear, say that we have a target in which pointers are 64-bit for (int32_t i ...) for (int32_t j ...) a[i][j] = ... doesn't work while this: for (int64_t i ...) for (int64_t j ...) does w...

...whatever polly pass I am trying to run opt seem to not find it: opt -load ~/toolchain/install/llvm-3.8/lib/libPolly.so -S -polly-canonicalize matmul.s > matmul.preopt.ll opt: Unknown command line argument '-polly-canonicalize'. Try: 'opt -help' opt: Did you mean '-polly-delinearize'? I am sure that loading the library works, since opt -load ~/toolchain/install/llvm-3.8/lib/libPolly.so -help prints out: Polly Options: Configure the polly loop optimizer -polly - Enable the polly optimizer (only at -O3) -p...

...in include/llvm/IR/Instructions.h as an inline function? > Declare in include/llvm/IR/Instructions.h and define in lib/IR/Instructions.cpp? > New files? (e.g., IR/InstructionUtils.h and .cpp?) > Other suggesctions? > > I suggest taking the implementation from Analysis/Delinearization.cpp, > and create IR/InstructionUtils.h and .cpp. They can then be used to > consolidate other Instruction helper functions to one place. What other instruction helper functions do you have in mind? Names like "Utils" worry me because they generally turn into a dumping groun...

...functionality so that all pairs of memory references are tested. Finally, all the test cases have been updated. I haven't yet updated DA to analyze pairs of pointer dereferences. I wanted to get the initial correction in place first. I also expect that analyzer pointer derefs will benefit from delinearization and am hoping it gets incorporated soon. If someone could review this change and check it in, if appropriate, I'd be obliged. Thanks, Preston -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/2012111...

...e-checks for no-overflow assumptions > (PredicatedScalarEvolution::setNoOverflow). > > Michael > > Am Fr., 18. Sept. 2020 um 18:13 Uhr schrieb Stefanos Baziotis via llvm-dev > <llvm-dev at lists.llvm.org>: > >> Hi everyone, >> >> I've been using SCEV Delinearization but it fails when >> other-than-pointer-size values are used in the subscripts. To make that >> clear, say that we have a target in which pointers are 64-bit >> >> for (int32_t i ...) >> for (int32_t j ...) >> a[i][j] = ... >> >> doesn'...

...ferences are tested. Finally, all the test cases have >> been updated. >> >> I haven't yet updated DA to analyze pairs of pointer dereferences. I >> wanted to get the initial correction in place first. I also expect that >> analyzer pointer derefs will benefit from delinearization and am hoping it >> gets incorporated soon. >> >> If someone could review this change and check it in, if appropriate, I'd >> be obliged. >> >> Thanks, >> Preston >> >> >> > -- Best Regards, Erkan Diken ------------------...

...in include/llvm/IR/Instructions.h as an inline function? > Declare in include/llvm/IR/Instructions.h and define in lib/IR/Instructions.cpp? > New files? (e.g., IR/InstructionUtils.h and .cpp?) > Other suggesctions? > > I suggest taking the implementation from Analysis/Delinearization.cpp, > and create IR/InstructionUtils.h and .cpp. They can then be used to > consolidate other Instruction helper functions to one place. What other instruction helper functions do you have in mind? Names like "Utils" worry me because they generally turn into a dumping gro...

...; pairs of memory references are tested. Finally, all the test cases have > been updated. > > I haven't yet updated DA to analyze pairs of pointer dereferences. I > wanted to get the initial correction in place first. I also expect that > analyzer pointer derefs will benefit from delinearization and am hoping it > gets incorporated soon. > > If someone could review this change and check it in, if appropriate, I'd > be obliged. > > Thanks, > Preston > > > -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists...

...--------- - Status Updates - Impact of Loop Rotation on existing passes (Min-Yih) - Bugzilla bugs update (Vivek) - Loop Cache Cost Analysis (https://reviews.llvm.org/D63459) (Ettore) - Loop Guard API (https://reviews.llvm.org/D63885) (Whitney) - Data Dependence Graph (Bardia) - Delinearization (Gary Elsesser) - Loop vs Function pass (Jamie Schmeiser) - Loop Guard API (Whitney) Bardia Mahjour Compiler Optimizations IBM Toronto Software Lab bmahjour at ca.ibm.com (905) 413-2336 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.or...

...ed the guessing game from the array analysis. - This has also been implemented as part of a GSoC effort to unify Chapel and Polly. - Molly, the distributed version of Polly written by Michael Kruse for his PhD also implemented a similar scheme. In his use-case, optimistic run-time checks with delinearization was not possible, so this kind of intrinsic was _necessary_ for the application, not just _good to have_. More details are available in his PhD thesis: [Lattice QCD Optimization and Polytopic Representations of Distributed Memory](https://tel.archives-ouvertes.fr/tel-01078440). In part...

...l review comments are addressed. Waiting for approval. - Bugzilla bugs update (Vivek) - Florian has a patch fixing loop bugs related to max trip count. ---------------------------- Tentative Agenda for Sept 25 ---------------------------- Presentation from Marc Moreno Maza about his work on delinearization. - Status Updates - Follow up on multi-dimensional array indexing RFC (Siddharth) - Impact of Loop Rotation on existing passes (Min-Yih) - Data Dependence Graph (https://reviews.llvm.org/D65350) (Bardia) - Bugzilla bugs update (Vivek) - Others? Bardia Mahjour Compiler Optimizati...