Generating a loop from llvm bitcode

Hello

I am developing a backend that generates OpenCL from llvm bitcode. I start with a revived fork of the original LLVM C-Backend and have been modifying it. One thing that the backend lacked was generating proper loop structures; instead it relied on labels and goto statements. Therefore, I am trying to find a way to identify the loop structure and print it out in the backend. So far, the main issue I’ve been having trouble with is identifying the loop induction variable in a straight forward manner; getCanonicalInductionVariable doesn’t always succeed, and I’ve tried using InductionDescriptor, but it fails in cases where the CFG doesn’t include a loop preheader. Also, in both cases, I couldn’t find a direct way of determining the loop exit condition. I am wondering if there are any passes or data structures that would be able to help me accomplish what I am trying to do that I might be missing? Or does the community have any other ideas as to how I should approach this issue?

Any input is much appreciated.

Regards
Adel

"Ejjeh, Adel via llvm-dev" <llvm-dev@lists.llvm.org> writes:

Hello

I am developing a backend that generates OpenCL from llvm bitcode. I
start with a revived fork of the original LLVM C-Backend and have been
modifying it.

How far do you intend to take this? Reconstructing high-level control
flow from a CFG is not possible in the general case without code
duplication. One can do quite a lot but the nature of low-level
optimization means that at some point you'll likely need gotos, unless
code expansion is not a concern. And even then, the result won't look
much like the source program (though you probably don't care).

Beyond that, reconstructing high-level characteristics of values
(finding induction variables, getting proper array dimensions, etc.) is
even more challenging. One can't reconstruct original C struct types,
for example, because many of them get merged into a single LLVM type.
One might be able to do a bit better with TBAA but frontends would have
to save a lot more information in the IR to allow general translation.

There are many things in LLVM that cannot be expressed in C. C has no
"shufflevector" operation, for example. At best one can try to emit
(non-portable) intrinsics which may or may not be acceptable. Or emit
some kind of awful loop, I guess.

The C backend was riddled with problems even beyond the above issues.
If I were going to attempt something like this I don't think I'd start
with that.

It's not a hopeless project as long as you manage your expectations. :slight_smile:

                          -David

Thanks for your input David. I am aware of the concerns that you brought up, and I am aware about the issues of code duplication. I am willing to deal with duplication, but I need to have the proper loop structure. That’s why my main concern right now is to be able to identify the induction variable of the loop so that I can print out the “for …” statement. Even if I am only able to start out with basic loops. The main issue that I haven’t been able to find a straight-foward work around for is determining the loop exit condition, and that is mainly what I am trying to get direction for in my original question. It is unfortunate that the InductionDescriptor data structure stores everything you can think of about an induction variable, except it’s End value.

-Adel

The term for what you are trying to do in general is known as “control-flow graph structuring,” and you can find a bevy of papers on the topic. As David pointed out already, you can’t necessarily structure a generic CFG using goto, but I will caution that there are some constructs that are basically gotos for the purpose of structuring, namely break and continue (indeed, with multilevel break and continue statements, you can structure any non-irreducible graph without a goto). Figuring out which edges should be handled as gotos/breaks/continues and which edges should not is something that is not yet settled research.

As for your actual goal, you might have a better time of things if you start by generating an infinite loop, with breaks for exiting edges and continues for backedges, and then try to remove those via refinement steps (which might work better to handle situations such as loop conditions involving short-circuiting operators). In the case of loops with exactly one exiting block terminating with a conditional branch, the exiting condition is exactly the branch condition (up to negation) of that basic block. In general, doing this sort of analysis safely for generic CFGs is quite difficult, and you should approach the problem from the perspective that you might only sometimes be able to get this information.

Hi,

What you are trying to do is essentially very similar to a decompiler.
e.g. https://github.com/jcdutton/libbeauty
A compiler does the following steps:
OpenCL -> AST -> LLVM IR -> Machine Instructions -> Binary
A Decompiler is:
Binary -> Machine Instruction -> LLVM IR -> AST -> OpenCL

The step you are trying is going from LLVM IR -> AST -> OpenCL.
The LLVM IR can be thought of as the CFG. (Control Flow Graph)
The AST is the Abstract Syntax Tree.
The step from LLVM IR -> AST is generally referred to as “control-flow
graph structuring”.
This is when you take a CFG (if ... then ... goto) to a more
structured representation such as for...loop, do...while.

I am currently writing my own decompiler. https://github.com/jcdutton/libbeauty
I tried the AST step some time ago. It is difficult to do. So, for
now, I am concentrating on Binary -> LLVM IR. I will do the AST step
later.
But, during my AST work, I discovered patterns of CFG that are just
not describable in any higher level structure even though the
CLANG/LLVM compiler probably produced that CFG after some
optimizations.
So, when I revisit the AST step, I am going to look at which LLVM
optimizations produced those strange CFG patterns, and write LLVM IR
passes that "undo" them and thus create a CFG that is more easily
converted in the AST structure.
One trick to the AST step is first identifying the "Entry Point" to
your function.
Then identifying the "Exit Point" of your function.
If there are multiple "Exit Points", Modify the LLVM IR to merge them
all. E.g. Adding "goto exit:"
This merging, makes it a lot easier for the graph algorithms to do
their task better.
Then use simple graph algorithms, control flow path analysis, to
arrange all the basic blocks in a sensible order for the graph.
E.g. Entry point at the top, and Exit point at the bottom of the page.
In my "libbeauty" decompiler, I use xdot and graphviz to output pretty
graph pictures of the CFG.
It is very easy to spot loops using this method, and from that
selecting for...loop or do...while structures.
My CFG graph has nodes, and different colored links between them.
Green=Branch-due-to-True-Forwards
Red=Branch-due-to-False-Forwards
Yellow= Branch-Backwards.

If you have not done already, read up on graph theory.
You might also need to write some of your own LLVM IR passes, to
generally translate the LLVM IR into a form more suited for
structuring and raising to OpenCL.

Kind Regards

James