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

[Wojciech Matyjewicz]

Hi,

> The only interface provided by LoopMemDepAnalysis is "bool  
> carriesDependence()" which may not be sufficient. But we can extend  
> this.

Right. It was the only method I used for my purposes. I believe that 
most of the high-level functionality could be built on top of the 
testDependence() method in LMDAImplementation class.

I see one more major missing feature - lack of support for 
loop-independent dependences.

> The ArrayDepTest provides testDependenc() as well as testPositions().  
> I'm not very clear about the testPositions(). Would it be possible for  
> you to explain this ?

The idea was to provide infrastructure for different dependence tests. 
The ArrayDepTester class can be seen as a manager. Each concrete test 
(ie. the Delta test) is implemented as a subclass of ArrayDepTest. Tests 
are inserted into ArrayDepTester object in order of increasing 
complexity. ArrayDepTester::testDependence() first partition indexing 
positions (GEP operands) into separable positions and coupled position 
groups (according to the terminology in "Optimizing Compilers for Modern 
Architectures"). Then the dependence tests (ArrayDepTest objects) are 
run independently for each coupled position group (separable position 
can be seen a special case of coupled position group). This is a reason 
for ArrayDepTest::testPositions() method exists. It is given the same 
arguments as ArrayDepTester::testDependence() but with additional 
information about particular positions to test. It returns one of three 
answers: NoDependence, ExactDependence, PossibleDependence. First two 
answers tells there is no need to run more complex tests on this 
position group. The last ones causes ArrayDepTester to try next (more 
complex) test to refine the answer.

An example:
   for i:
     for j:
       A[i][j][k] = A[i+1][j][k+j]

There is one separable indexing position - the first one. The second and 
third create a coupled group. Suppose, we have two tests - the Delta 
test (which incorporates ZIV and SIV) and the Omega test. ArrayDepTester 
will first run the Delta test on the first position. It will easily 
detect an exact dependence, so there will be no use in running the Omega 
test. However, it may be the case that for the group consisting of 
second and third positions the Delta test is not sufficient and the 
Omega test will produce better results.

To be honest, I am not sure if this infrastructure is not an overkill 
for my simple prototype. I was just trying to code concepts from 
"Optimizing compilers for Modern Architectures" book.

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

-Wojtek