similar to: [LLVMdev] Dependence Analysis [was: Flow-Sensitive AA]

>> One nit-pick, I see that some of the interfaces use tons of parameter, >> which is something I'd like reduce for ease of use. > >Right. It was my concern as well, but I eventually decided to write it >this way. Feel free to change it. > As we are speaking about modifying the lib, here are two things I would like to modify/add in it: - Replacing depedency

On Wednesday 03 September 2008 12:39, Matthieu Delahaye wrote: = > API: This is the matter of providing the possibilities to ask useful > questions, and providing useful answers. [in the pow of the passes that > are using the analysis]. > > The "textbook" version would be: give me the memory dependency(ies) > between these two instructions. With the possibility to

On Wed, 2008-09-03 at 10:50 -0500, David Greene wrote: > On Friday 29 August 2008 12:15, Matthieu Delahaye wrote: > > > > - DataDependenceAnalysis will select various dependence tests based > > > on > > > user selection. We want a interface similar to AnalysisGroup used > > > by > > > Alias Analysis, but we also want to allow the possibility of

In the general case, I think you have to be conservative about this because programmers may deliberately want this kind of "wraparound" behavior, e.g., with periodic boundary conditions. But 99.9% of programs probably don't need that so it would be bad to penalize them for this corner case. In such a situation, I think you just have to support both choices, but choose the

On Wednesday 20 August 2008 14:07, Vikram S. Adve wrote: > At Illinois, we are working on a parallelizing compiler but we're at > an extremely early stage. We too will need a dependence analysis > interface that can support fairly aggressive analysis, including > strong tests, direction vectors, perhaps distance vectors, and > dependence breaking conditions. We were going to

Hi, On Fri, 2008-08-29 at 09:24 -0700, Devang Patel wrote: [...] > - Put various tests, DeltaTest, in lib/Analysis folder. The > transformation pass does not need to see these details. I believe some low-level tests should actually not be implemented as a separate Analysis but placed into Support. For instance, DeltaTest would use GCD or other tests on a different set of indexes once

On Aug 22, 2008, at 9:34 AMPDT, Chris Lattner wrote: > > On Aug 22, 2008, at 9:30 AM, Vikram S. Adve wrote: > >> In the general case, I think you have to be conservative about this >> because programmers may deliberately want this kind of "wraparound" >> behavior, e.g., with periodic boundary conditions. But 99.9% of >> programs probably don't need

On Aug 22, 2008, at 11:53 AM, Dale Johannesen wrote: > > On Aug 22, 2008, at 9:34 AMPDT, Chris Lattner wrote: > >> >> On Aug 22, 2008, at 9:30 AM, Vikram S. Adve wrote: >> >>> In the general case, I think you have to be conservative about this >>> because programmers may deliberately want this kind of "wraparound" >>> behavior, e.g.,

Wojtek Matyjewicz has written a simple DependenceAnalysis interface and sent email about it to llvmdev in June -- the message is attached. He said he wrote several tests behind that interface -- ZIV, strong SIV, Banerjee, and some form of the Delta test -- and two students in my Spring class added the Omega test. I have not reviewed his interface yet because I've been traveling

On Friday 29 August 2008 12:15, Matthieu Delahaye wrote: > > - DataDependenceAnalysis will select various dependence tests based > > on > > user selection. We want a interface similar to AnalysisGroup used > > by > > Alias Analysis, but we also want to allow the possibility of running > > multiple tests at the same time. > > That will probably be the

On Aug 29, 2008, at 10:15 AM, Matthieu Delahaye wrote: > Hi, > > On Fri, 2008-08-29 at 09:24 -0700, Devang Patel wrote: > [...] >> - Put various tests, DeltaTest, in lib/Analysis folder. The >> transformation pass does not need to see these details. > > > I believe some low-level tests should actually not be implemented as a > separate Analysis but placed into

Wojtek, Please see David's message below. Have you or can you check in your code, perhaps as a project for now? That will allow us to start looking at it and perhaps collaborating on it. --Vikram Associate Professor, Computer Science University of Illinois at Urbana-Champaign http://llvm.org/~vadve On Aug 20, 2008, at 3:05 PM, David Greene wrote: > On Wednesday 20 August 2008

> We want to model this as an analysis and make following changes. > > - Rename LoopMemDepAnalysis as DataDependenceAnalysis. Various > transformation passes will use this interface to access data > dependence info. This is an external interface. Put this in include/ > llvm/Analysis. > - Make DirectionVector (and later on DistanceVector) independent > interface and

On Aug 22, 2008, at 4:49 PM, John Regehr wrote: > Has anyone quantified the optimizations afforded by undefined signed > overflow? I'd expect that the benefits are minimal for most codes. In most cases, I agree. But for codes that depend heavily on dependence analysis, I would think that being conservative with index expressions would really kill any disambiguation capability and

On Aug 22, 2008, at 9:30 AM, Vikram S. Adve wrote: > In the general case, I think you have to be conservative about this > because programmers may deliberately want this kind of "wraparound" > behavior, e.g., with periodic boundary conditions. But 99.9% of > programs probably don't need that so it would be bad to penalize them > for this corner case. In such a

On Sun, Aug 24, 2008 at 6:28 PM, Eli Friedman <eli.friedman at gmail.com> wrote: > On Sun, Aug 24, 2008 at 2:46 PM, Wojciech Matyjewicz > <wmatyjewicz at fastmail.fm> wrote: >>> I asked myself the same question. Without mod, how do you ensure that for instance the expression 2*i+255 was not actually 2*i-1 ? >> >> I think it is not possible in general, but I

On Sun, Aug 24, 2008 at 2:46 PM, Wojciech Matyjewicz <wmatyjewicz at fastmail.fm> wrote: >> I asked myself the same question. Without mod, how do you ensure that for instance the expression 2*i+255 was not actually 2*i-1 ? > > I think it is not possible in general, but I believe it is possible in > case of affine expressions used as GEP indices. > > I assume, GEP indices

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

On Aug 21, 2008, at 1:37 AM, Wojciech Matyjewicz wrote: > I am investigating what changes are necessary to add support for > first-class structs and arrays and will prepare a version to check > in as > a LLVM project if there still is interest. We want to model this as an analysis and make following changes. - Rename LoopMemDepAnalysis as DataDependenceAnalysis. Various