[LLVMdev] Seeking advice on Structural Analysis pass

[Trevor Harmon]

On Mar 13, 2010, at 11:54 AM, James Stanier wrote:

> It
> analyses the CFG and recognises specific region schema, such as if- 
> then,
> if-then-else, while-loop, etc., and builds a "control tree" which  
> represents
> the hierarchical structure of the input program.

I am not sure if my definition of a control flow tree is the same as  
yours, but if it is, I am very interested. For my recent Ph.D. work, I  
created control flow trees from Java bytecode in order to calculate  
the WCET of a program. Operating on a CFT instead of a CFG makes the  
calculation much faster because, in many cases, one can simply perform  
a recursive descent into the tree (a linear operation), rather than  
formulating an ILP problem from the CFG and waiting for an ILP solver  
to do its thing (an exponential operation).

For Java, I got lucky because I found a bytecode decompiler that  
creates a CFT of Java programs as a side-effect of its reverse  
engineering process. I was then able to adapt this internal CFT data  
structure into something more general-purpose and readily usable for  
WCET analysis. I also was able to transform the CFT into a CFG (for  
performance comparisons) by adding back-edges to the tree in the  
appropriate places.

I am now attempting to adapt the work I did for Java to C++, using  
LLVM as the foundation. It's difficult, however, because LLVM only  
provides CFGs, not CFTs. And while transforming a CFT into a CFG is  
relatively straightforward, going the other direction is not. I assume  
this is where I could benefit from your and Tobias's work. It sounds  
like you are both working on (or have solved) the problem of  
converting LLVM's CFGs into CFTs. Am I understanding that correctly?

Just to be clear, a rough example of what I mean by CFT and CFG can be  
found in the attachments. Both diagrams represent the exact same  
control flow (from SpeedSensor.java); they are simply two different  
ways of structuring that control flow: one as a tree, the other as a  
graph.

Trevor



-------------- next part --------------
A non-text attachment was scrubbed...
Name: SpeedSensor.java
Type: application/octet-stream
Size: 478 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100315/41c61b7e/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cft.pdf
Type: application/pdf
Size: 34703 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100315/41c61b7e/attachment.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cfg.pdf
Type: application/pdf
Size: 30589 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100315/41c61b7e/attachment-0001.pdf>