[LLVMdev] [OT] Control Flow Graph(CFG) into Abstract Syntax Tree(AST)

[James Courtier-Dutton]

On 21 September 2012 09:51, Ralf Karrenberg <Chareos at gmx.de> wrote:
> Hi,
>
> Simon Moll (in CC) has written a decompiler for LLVM in his Bachelor's
> Thesis here at Saarland University. The thesis is titled "Decompilation of
> LLVM IR" and can be found here:
> http://www.cdl.uni-saarland.de/publications/
>
> The library he implemented is called "Axtor" (for "AST Extractor") and has
> been used primarily to generate OpenCL code from LLVM. In this context, it
> successfully compiles OpenCL -> LLVM -> OpenCL "cycles".
> Simon will be able to give you more information, also in terms of license
> details which I don't remember.
>

I have read the pdf doc.
It covers some things well, but is missing an important piece of information.
It only needs to cover well formed CFG. I.e. Normal loops and if...then...else.
It does not need to handle "goto".
Specifically:
Section 4.1.2
1) Figure 4.2: Ir-reducible control-flow.
2) Figure 4.3: A CFG with loop-crossing branches.
3) Figure 4.4: Ab-normal selection paths.

If the original program was written in C, these types of CFG are all possible.
The only way to represent these in AST is to introduce "gotos" at
strategic points in the CFG.
I am looking at various CFG graphs, and from looking at them, it is
quite obvious to me which branches should be gotos, and which should
be loops or if...then...else. The problem I have is coming up with an
algorithm that would make the same decisions as I would.