[LLVMdev] Dependence Analysis [was: Flow-Sensitive AA]
wmatyjewicz at fastmail.fm
Sat Aug 23 09:01:39 PDT 2008
> The only interface provided by LoopMemDepAnalysis is "bool
> carriesDependence()" which may not be sufficient. But we can extend
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
> 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.
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.
More information about the llvm-dev