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

[Vikram S. Adve]

David, I agree with all of what you said here except for one point:


On Sep 3, 2008, at 3:06 PM, David Greene wrote:
<snip>
>>
>> This is what I had in mind when I talked above the difficulty of  
>> having
>> a good API that do not change every time a new analysis is added. I
>> doubt this API could be defined without the review of analysis  
>> users and
>> writers.
>
> But ultimately these "tricks" such as runtime decision-making are  
> not under
> the purvue of the memory dependence analysis.  In these cases the  
> compiler is
> "forcing" an answer it wants by create code paths where it knows  
> certain
> properties.  There's no analysis necessary because the compiler  
> created those
> paths in the first place with very specific goals in mind.

That may not be the case because the compiler may need dependence  
"breaking conditions" to generate this code.  For example, such a  
condition might say [a particular instruction pair does not have a  
dependence if] "N > sizeof(A)" or "i + j < 10".  The dependence *test*  
usually has to generate this condition, e.g., polyhedral analyses like  
Omega can do this.

The same functionality could also be useful for interactive porting  
tools helping users port programs to a parallel language, one of the  
target projects for the dependence analyzer here at Illinois.

Having said that ...


>  I think the
> interface you've outlined above is sufficient for now.  We'll gain  
> experience
> and add to it later if necessary.
<snip>

... I agree: let's do the basic Yes/No/Maybe and Direction/Distance  
vectors for now, and add more sophisticated queries as clients emerge  
for them.

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve