similar to: [LLVMdev] Array Dependence Analysis

Hi, > As part of the advanced compilers course semester project (at UIUC), we > are starting to implement array dependence analysis for LLVM. I'm currently working on a similar project and hoping to finish it in about two weeks. I am going to share the code when it's ready. I've spent some time analyzing LLVM code for scientific and "ordinary" programs to find out

>> As part of the advanced compilers course semester project (at >> UIUC), we >> are starting to implement array dependence analysis for LLVM. Great! This is something we've needed for a long time. > I'm currently working on a similar project and hoping to finish it in > about two weeks. Cool! I think the most critical part of this is to get a good

Hi, > Cool! I think the most critical part of this is to get a good > interface for dependence analysis. There are lots of interesting > implementations that have various time/space tradeoffs. > > For example, it would be great if Omega was available as an option, > even if the compiler didn't use it by default. This argues for making > dependence analysis

On Mar 15, 2008, at 4:48 PM, Alexandre Duchâteau wrote: > Any suggestion on features, tests and/or interface are welcome. LLVM loop transformer operates at loop level, which is not what many optimizers do in general. So, a loop level interface (i.e. based on LoopPass in llvm) to find loop-carried dependence is preferable to loop optimizer. - Devang

Hi all! I have recently finished the first prototype of data dependence analysis for LLVM. Now that I have some more time I would like to prepare a "production" version. In this post I'll try to describe the current state and propose a work plan. Currently, the analysis has a very simplified interface (it allows to query for dependence between two given instructions or whether a

> I'm not following your example.  If you have two sibling loops with the same parent, one will frequently, but not always dominate the other.  Can you give a specific example of when forming a recurrence between two siblings (without one dominating the other), is useful? The situation can happen with guarded loops or with a user guard like below: if (c) { for (i = 0; i < n; i++)

On Thu, 29 Nov 2007, Wojciech Matyjewicz wrote: > As for the dependence analysis, I need this piece for my project, and I > am preparing myself to write it. Great! > I am currently studying some papers, but haven't yet decided on the > method. Maybe some of you have experience in the area and would like to > advise me something? In the next few days I am going to take a look

Forwarding to the dev list, in case others ran into similar issues and/or have input on this topic. Bardia Mahjour ----- Forwarded by Bardia Mahjour/Toronto/IBM on 2020/03/30 02:25 PM ----- From: Bardia Mahjour/Toronto/IBM To: listmail at philipreames.com Cc: "Michael Kruse" <llvm at meinersbur.de> Date: 2020/03/26 11:47 AM Subject: Scalar Evolution Expressions Involving Sibling

Hi Jimmy, It's good to know that the problem is not specific to the case I ran into. May be you can provide your example as well, since Philip seems to be interested in some specific examples. If the assertion in getAddrExpr is deemed necessary, then I think a condition check would be the next best solution as it helps client code guard against such cases and make alternative arrangements to

Wojtek, If you like, I can help guide this SoC project. I would also like to see if we can coordinate with Alex and Albert, who are doing the class project here. As a first comment, your 3 layers are a good organization but two comments: 1. Layer 1 shd also look at loop bounds and array bounds: those can be used to disprove some deps. 2. The interface will also need to compute direction and

Thanks for sharing the known problem. I think to solve the problem properly, we need to fully understand why that assumption about dominance is there and the implications of removing it. It would be good if you could be more specific about your idea of nullptr or SCEV_unknown (eg which function would return those values and when), but returning nullptr from getAddExpr or getSCEVAtScope may be

On Aug 20, 2008, at 8:56 AM, David Greene wrote: > What I really need is a dependence analysis interface. I need to know > about loop-carried dependencies and that sort of things, whether two > memory > operations reference the same data, distance information, etc.. As > far as I > can tell, there's no infrastructure for this in LLVM. Right, this is something we've

On Monday 18 August 2008 17:48, David Greene wrote: > > Normally, the conversion to SSA form is sufficient. Can you talk > > about cases where this matters to you? > > Mostly it involves tying into our memory dependence analysis which > annotates things on program points. I need a way to translate back > to our optimizer data structures. > > So it's not

Hi Sanjoy & Hal, Looking at LoopDependenceAnalysis::analyzeZIV ... I don't understand much about SCEV, but the code seems inadequate. Consider these three examples: int a = ...; // we can't be sure of the relationship between a and b int b = ...; // perhaps they are parameters, or the result of I/O for (int i = 0; i < n; i++) { v[a][i] = ...; v[a + 1][i] = ...; } for (int i

Hi, Devang Patel wrote: > LLVM loop transformer operates at loop level, which is not what many > optimizers do in general. So, a loop level interface (i.e. based on > LoopPass in llvm) to find loop-carried dependence is preferable to > loop optimizer. Do you mean making Array Dependence Analysis a loop-level analysis? Would its results be available for some function-level pass

On Mar 18, 2008, at 9:21 AM, Wojciech Matyjewicz wrote: > Hi, > >> Cool! I think the most critical part of this is to get a good >> interface for dependence analysis. There are lots of interesting >> implementations that have various time/space tradeoffs. >> >> For example, it would be great if Omega was available as an option, >> even if the compiler

Hi Preston, Thanks for the feedback! > In LoopDependenceAnalysis::AnalyzePair, what's going to happen if we > have something like this > > for (i = 0; i < n; i++) > for (j = 0; j < n; j++) > A[i][j]++; > > versus > > for (i = 0; i < n; i++) > for (j = 0; j < n; j++) > A[j][i]++; I think this can be fixed by ordering the subscripts

On Mar 18, 2008, at 8:03 AM, Wojciech Matyjewicz wrote: > Hi, > > Devang Patel wrote: >> LLVM loop transformer operates at loop level, which is not what many >> optimizers do in general. So, a loop level interface (i.e. based on >> LoopPass in llvm) to find loop-carried dependence is preferable to >> loop optimizer. > > Do you mean making Array Dependence

On Nov 29, 2007, at 11:11 AM, Wojciech Matyjewicz wrote: > As you have noticed, loops aren't represented directly in the LLVM IR. > However, there are analysis passes which may be helpful to > "reconstruct" > them. For example: LoopInfo pass detects natural loops (as sets of > basic > blocks) and ScalarEvolution pass finds loop induction variables (and >

[+CC Andy] Hi Elena, I don't have any fundamental issues with teaching SCEV about floating point types, but given this will be a major change, I think a high level roadmap should be discussed on llvm-dev before we start reviewing and committing changes. Here are some issues that I think are worth discussing: - Core motivation: why do we even care about optimizing floating point