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:
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:
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.
The same for me.
StructuralAnalysis.diff (717 Bytes)