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

[Simon Moll]

Hi James,

my thesis explicitly describes how to get rid of unstructured
control-flow by means of CFG transformations. In essence the whole
procedure consists in three steps:
1.) make the CFG reducible (Controlled Node Splitting)
2.) Make all loops single exit such that they can be modeled with
BREAK-statements (in nested loops as well).
3.) Restructure abnormal selection paths (The original thesis uses
node splitting. However, the current version relies on predication
which does not duplicate blocks).

After the transformation, all control-flow can be represented with
infinite loops, continue, break and simple if..else.. statements (w/o
short-circuit evaluation).

The transformation does its job quite well and so there isn't even an
AST-primitive for GOTOs in Axtor (the original targets (OpenCL, GLSL)
don't support it).

Anyway, extending the framework to support GOTOs should be
straight-forward: instead of transforming the CFG axtor would then
just drop a GOTO-node whenever it encounters unstructured
control-flow.

I hope i could clarify what Axtor can and can't do.

Regards,
Simon

2012/9/21 James Courtier-Dutton <james.dutton at gmail.com>:
> 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.