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>