[LLVMdev] Seeking advice on Structural Analysis pass

[Tobias Grosser]

On 03/16/2010 05:02 PM, James Stanier wrote:
>
> Hi Trevor,
>
> I just studied your diagrams -- I *think* that the "control tree" of
> structural analysis is not same as the "control flow tree" from your own
> Java work. However, as you understand your work more than I do, I present
> you with some fancy coloured diagrams that I drew that might help you (and
> others!) understand what structural analysis does a bit better than the
> black-and-white ones in Muchnick's book.
>
> This first diagram shows a CFG in step 1, and the steps of reduction that
> structural analysis performs:
> http://www.informatics.sussex.ac.uk/users/js231/img/sa-example-reduction.pdf
>
> For example, in the first step, the red cloud indicates that the blocks "B6"
> and "exit" are matched to the "continuous blocks" schema. These are then
> reduced into an abstract node which is called B6a and is coloured red (the
> same colour as the cloud) in the next step. Then, block "B5" is matched to
> the "self loop" schema, and replaced by the pink abstract node "B5a" in the
> next diagram. This continues until there is only one node left, and
> structural analysis has finished.
>
> This second diagram shows the control tree that is built while these
> reductions are occurring, which shows the hierarchical structure of the
> program. The coloured nodes are the abstract nodes from the first diagram,
> and all leaf nodes are the original basic blocks.
> http://www.informatics.sussex.ac.uk/users/js231/img/sa-controltree.pdf
>
> Does this make it any clearer? I'm happy to explain it in more detail.

Hi James,

this is very close to what ether and me have implemented. However you 
have got the nicer graphics, they look great.

If you want to try the RegionInfo pass call:
opt -regions -analyze somefile.ll

This will print you a tree that is not as nice as your graphics, but 
should have the same semantics. The algorithm I used is probably 
different, however the results are the same.

The main difference I see between our approaches is that you classify 
the regions, whereas in the RegionInfo analysis a tree out of (yet 
unclassified) regions is created

Therefore the RegionInfo analysis is probably a little bit more general, 
as I am just looking for anything that is either a single entry single 
exit region (simple region) or can be transformed to such a region be 
inserting merge blocks (refined region). As your pass seems to work on 
block schemas it will probaly only detect regions that fit in a schema 
that you have implemented. Is this correct?

I would be interested how your pass handles unstructured control flow.
Especially in the problematic cases I put in the RegionInfo test suite.

They are available at this place:
http://repo.or.cz/w/llvm-complete/pofl.git/tree/refs/heads/regioninfo:/test/Analysis/RegionInfo

Ether and me are currently adding doxygen comments. If you are 
interested you could also have a look at our doxygen documentation

http:://tobias.osaft.eu/regioninfo/doxygen

To me it seems as if our approaches are close enough together to merge 
them. I think your code could take advantage of the iterators and the 
RegionPass we have written. Whereas we would be really glad to have the 
classification of the regions,

This way we could e.g. write RegionPasses that only work on continuous 
blocks. Or only on if/then/else blocks. Something that seems very useful 
to me.

I would be interested in your opinion

Tobias