search for: delinearization

...is/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, and as a last step it requires certain conditions to be met in order to validate that the delinearized indexes are correct. The `tryDelinearize` functio...

...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 > > > &...

...Other people may have different opinions though. Any improvements to DA in general would be excellent, and it has a lot of room for improvement. Dave From: Bardia Mahjour Sent: 22 May 2019 18:09 To: David Green Cc: Doerfert, Johannes; llvm-dev at lists.llvm.org; nd Subject: Re: Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis   Hi David, Sorry for my delayed response. > There are already some function like isKnownPredicate that attempt to deal with some of this is DA. Can we extend the other for these cases? Perhaps with some extra information that we have that SCEV would in g...

...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: &quot...

...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 < > ve...

[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 > th...

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's...

...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 indices are &...

...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 curiou...

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 work. I...

I just checkout release_38 branches of llvm, clang and polly and built it on and x86 Ubuntu with cmake: CMAKE_BUILD_TYPE="Debug" CMAKE_INSTALL_PREFIX="$HOME/toolchain/install/llvm-3.8" LLVM_TARGETS_TO_BUILD="X86" cmake -G "Unix Makefiles" \ -DBUILD_SHARED_LIBS="ON" \ -DCMAKE_BUILD_TYPE=$CMAKE_BUILD_TYPE \

...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 ground for t...

...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/20121112/ae8e5...

...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't work...

...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 ground for...

...; 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.o...

...--------- - 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.org/piper...

...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 particular,...

...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 Optimizations IBM...