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

>Polyhedral representations are powerful but somewhat expensive to >construct and simple dependence tests don't construct them. Forcing >all dependence test results to go through them would be overkill. >Also, many loop transforms, e.g., loop interchange, don't need the >polyhedral info, just direction vectors. You could instead provide >both direction

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 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 Fri, Aug 22, 2008 at 5:03 PM, Vikram S. Adve <vadve at cs.uiuc.edu> wrote: > Thanks! This is all very interesting, and tells me that LLVM has a > way to go to fully support all of these capabilities (if that is the > right thing to do, which isn't clear). OTOH, it looks like a lot of > real-world software that is using LLVM already doesn't seem to be > affected by

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

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 22 August 2008 16:14, Daniel Berlin wrote: > On Fri, Aug 22, 2008 at 5:03 PM, Vikram S. Adve <vadve at cs.uiuc.edu> wrote: > > Thanks! This is all very interesting, and tells me that LLVM has a > > way to go to fully support all of these capabilities (if that is the > > right thing to do, which isn't clear). OTOH, it looks like a lot of > >

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

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

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

On Aug 22, 2008, at 4:27 PM, David Greene wrote: > Exactly right. One of my first jobs here was to fix a bunch of > overflow > problems exposed by optimization. It's now become a tradition to > give this task to any new optimizer employee. :) But that sounds like Cray is being fairly conservative in treating overflow problems as errors during optimization. Is that

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

Thanks! This is all very interesting, and tells me that LLVM has a way to go to fully support all of these capabilities (if that is the right thing to do, which isn't clear). OTOH, it looks like a lot of real-world software that is using LLVM already doesn't seem to be affected by the lack of them. Does anyone know of any C/C++ programs that require integer overflow on signed

> 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. Sure. For now, I am posting it as an attachment, because it does not build against the current SVN version. It is really basic (for example, it cannot produce distance vectors,

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

>However, there is one issue I have ignored - possibility of overflow in >the index expression. Suppose, we have such a loop: > for (i8 i = 0; i != 200; ++i) { > A[2 * i + 5] = ... > ... = A[2 * i + 3] > } >If both index expressions are evaluated in 8-bit arithmetic, >then the dependence equation should be solved in modular arithmetic: > 2 * i + 5 == 2 * (i +

> Thanks! This is all very interesting, and tells me that LLVM has a > way to go to fully support all of these capabilities (if that is the > right thing to do, which isn't clear). OTOH, it looks like a lot of > real-world software that is using LLVM already doesn't seem to be > affected by the lack of them. LLVM's current choice is safe for all applications. The