Seeking advice on Structural Analysis pass

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:

Hi Tobias,

Thanks for getting back to me. I have just had a peek at the documentation
for your region pass, and it looks really cool, and thanks also for the
pointers to the literature.

If you want an overview of how structural analysis works, some of the pages
from Muchnick's textbook are available through Google Books. Diagrams of the
regions you can recognise are here:

http://books.google.co.uk/books?id=Pq7pHwG1_OkC&lpg=PP1&dq=advanced%20compiler%20design%20and%20implementation&pg=PA203#v=onepage&q=&f=true

With the reduction process of the CFG here:

http://books.google.co.uk/books?id=Pq7pHwG1_OkC&lpg=PP1&dq=advanced%20compiler%20design%20and%20implementation&pg=PA211#v=onepage&q=&f=true

Unfortunately the page that shows a diagram of the control tree for an
example CFG is not included online. I could always forward you a copy of a
work-in-progress paper where it's included in the background section if you
were interested in reading further.

With regards to a repository -- I've only been working on it locally, so
it's just on my personal svn repository. However, if you're interested in
having a glance at the code (it's a bit of a mess) then I've uploaded it for
you, but I'm not responsible for any vomiting:

http://www.informatics.sussex.ac.uk/users/js231/files/StructuralAnalysis.cpp

I haven't tested it on the two testsuites you mention, however I haven't had
time to do so yet. I wrote it towards the end of last summer, got it
working, used it to get results for a paper, and then haven't really touched
it since. It only dawned on me recently that seeing as I spent all that time
doing it, I might as well look into including it into LLVM somehow!

Ideally I'd like to know whether it would be worth my time to tidy the
structural analysis pass up, or whether you'd be interesting in discussing
this further some time to see how we could integrate our approaches, or
whether I should work towards getting it included separately!

Anyone's opinions are welcome on this matter and are appreciated. :slight_smile:

Best,
James

Hi Tobias,

Hi,

Thanks for getting back to me. I have just had a peek at the documentation
for your region pass, and it looks really cool, and thanks also for the
pointers to the literature.

If you want an overview of how structural analysis works, some of the pages
from Muchnick's textbook are available through Google Books. Diagrams of the
regions you can recognise are here:

Advanced Compiler Design Implementation - Steven Muchnick, Muchnick and Associates - Google Books

With the reduction process of the CFG here:

http://books.google.co.uk/books?id=Pq7pHwG1_OkC&lpg=PP1&dq=advanced%20compiler%20design%20and%20implementation&pg=PA211#v=onepage&q=&f=true

Unfortunately the page that shows a diagram of the control tree for an
example CFG is not included online. I could always forward you a copy of a
work-in-progress paper where it's included in the background section if you
were interested in reading further.

Yes, I would really be interested in this.

With regards to a repository -- I've only been working on it locally, so
it's just on my personal svn repository. However, if you're interested in
having a glance at the code (it's a bit of a mess) then I've uploaded it for
you, but I'm not responsible for any vomiting:

http://www.informatics.sussex.ac.uk/users/js231/files/StructuralAnalysis.cpp

Hey this is great, thanks to giving me access to this. Unfortunately it did not compile with llvm HEAD. I changed some obvious things (Patch attached), but was not able to find implementations of

StructuralAnalysis.cpp:495: error: ‘constructVSDG’ was not declared in this scope
StructuralAnalysis.cpp:1244: error: ‘constructRegion’ was not declared in this scope

Furthermore I did not find any print function. How can I see the tree you are building? Is there some kind of export/printing stuff implemented?

I would love to try it on some code to understand the performance of the analysis in Muchnicks textbook and the coverage it achieves.

I haven't tested it on the two testsuites you mention, however I haven't had
time to do so yet. I wrote it towards the end of last summer, got it
working, used it to get results for a paper, and then haven't really touched
it since. It only dawned on me recently that seeing as I spent all that time
doing it, I might as well look into including it into LLVM somehow!

Sure, it would be great to have a structural analysis in LLVM. This is why I have been working on it. I need it for some other projects and it seems to be useful for more people.

Ideally I'd like to know whether it would be worth my time to tidy the
structural analysis pass up, or whether you'd be interesting in discussing
this further some time to see how we could integrate our approaches, or
whether I should work towards getting it included separately!

It would be great discussing this together. Looking in your code I saw that you where able to classify the regions in loop, condition, ...
This is something very interesting, that my current implementation misses.
In my codebase on the other side there is the infrastructure to implement RegionPasses which may facilitate implementations that are based on the control structure tree and the control regions it exposes. Furthermore ether contributed iterators and GraphTraits implementations that allow to work on each region as if it would be a function.

I think all these features would be useful, so it would be nice if we could work together to integrate them in some way.

Considering the core algorithm I would really like to compare our approaches closely. When starting to write my algorithm I also thought about the one mentioned in Muchnicks textbook, however found two limitations. On the one hand it seemed to me a lot of work to implement and on the other hand I hoped to achieve a higher coverage without preprocessing the cfg by allowing regions that I call refined regions.

As I did not use any known algorithm it still needs to be shown that the algorithm is an improvement over the known ones. A comparison to one of the best known algorithms in this area would be great. And if you as a person that is into the topic, could have a closer look at the general idea, this would be awesome.

I wrote some comparison of the different approaches. If you like, I could send you a copy.

Anyone's opinions are welcome on this matter and are appreciated. :slight_smile:

The same for me.

Best,
James

Cheers

Tobi

StructuralAnalysis.diff (717 Bytes)

Folks,

Myself and Tobias are taking this discussion off the mailing list now to
private email, but if you're interested or have questions about the
structural analysis pass, do feel free to get in contact.

Best,
James