[LLVMdev] Seeking advice on Structural Analysis pass

[Tobias Grosser]

On 03/13/2010 08:54 PM, James Stanier wrote:
>
> Hi folks,

Hi James,

I have also been working on such a pass for the last couple of month. 
The pass itself is finished and ether has written some further LLVM 
support implementing a RegionPass class, that can be used to implement 
region passes that work like the existing LoopPasses today, but use a 
region instead of a loop or function as work unit.

As I wrote it myself I am obviously interested in region detection and 
the program structure tree itself.

Furthermore I would be interested to understand your pass and the 
differences between our approaches. Hopefully we could combine both of 
them and get LLVM a really great region detection framework.

If you are interested the current code for our region pass is in this 
git repository:
http://repo.or.cz/w/llvm-complete/pofl.git/shortlog/refs/heads/regioninfo

Is there any repository for your code?

Some information about our region pass can be found in this mail:
http://lists.cs.uiuc.edu/pipermail/llvmdev/2010-March/029996.html

I just copied the relevant part for you:
-----------------------------------------------------------------------
The basic ideas are taken from "The Program Structure Tree - Richard 
Johnson, David Pearson, Keshav Pingali - 1994", however enriched with 
ideas from "The Refined Process Structure Tree - Jussi Vanhatalo, Hagen 
Voelyer, Jana Koehler - 2009".
The algorithm to calculate these data structures however is completely
different, as it takes advantage of existing information already 
available in (Post)dominance tree and dominance frontier passes. This 
leads to a simpler and in practice hopefully better performing 
algorithm. The runtime of the algorithms described in the paper above 
are both linear in graph size, O(V+E), whereas this algorithm is 
probably in O(V+E2) in the worst case, as the dominance frontier 
information itself is quadratic. In practice runtime seems to be in the 
order of dominance tree calculation (tested on the polyhedron.com 
benchmarks)
-----------------------------------------------------------------------

Did you try your code on the LLVM testsuite? How fast/slow is it e.g. 
compared to dominance calculation? Does it need any passes as prerequisites.

It would also be nice to see if it can handle the testcases in 
test/Analysis/RegionInfo that can be found in the git repository 
mentioned above.

As you are actually using region info, I would highly appreciate any 
comments on the refined regions as described in the paper above or the 
RegionInfo.h header in our pass (available in git). Do you think they 
are useful? In my experience there are almost twice as much refined 
regions as just plain regions as described in Johnson.

Chears

Tobias