[LLVMdev] Seeking advice on Structural Analysis pass

[Tobias Grosser]

On 03/15/2010 05:51 PM, James Stanier wrote:
>
> 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:
>
> 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.

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. :)
The same for me.

> Best,
> James
Cheers

Tobi
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: StructuralAnalysis.diff
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100319/faa1e71b/attachment.ksh>