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