Isekai LLVM update #2: conditionals and loops

How to recognize conditional statements and loops in LLVM IR code

Authors: Ivan Glushenkov, Viktor Krapivenskiy

This is the second article in our series. Previous article: update #1. Next article: update #3

We looked at the LLVM IR block patterns that clang generates for “if”, “switch”, “for”, “while” and “do…while” C statements with “-O0”. We notice that, in general (i.e. with the exceptions mentioned below):

1. There is always exactly one block that terminates with the “ret” instruction, corresponding to the “return” statement in C. We will call this block “final”.
2. The statements map to one of the following patterns, which we call the conditional pattern and the loop pattern:

There are some exceptions to this, as these patterns will not appear in the following cases:

1. For conditional statements where the condition expression is constant, there will be no conditional branch and therefore no C vertex in IR.
2. Loops of the sort “do … while(0)” compile to “linear” branches, so there will again be no C vertex in IR.

We also note that:

1. In the conditional pattern, C has 1 or more outgoing edges, while in the loop pattern, it will always have exactly 2 outgoing edges.
2. For infinite loops of the sort “while(1)” and “for(…; 1; …)”, clang seems to generate an IR that corresponds to the loop pattern. However, we will not support such infinite loops.

On the above graphs:

1. The vertices represent LLVM basic blocks.
2. The C vertex is a block that terminates with a conditional branch.
3. The S vertex is a “sink” vertex, it is the “end” of a conditional or loop statement;
4. The edges represent the “may jump onto” relation;
5. A curved line with a cloud means “a detached graph connected with the outer world only with one single inward edge and one single outward edge”. This may degenerate into a null graph, in which case the curved-line-with-a-cloud becomes a single edge.
6. A line ending with a double arrow means “there is a path from here to the final block.”

To distinguish between the conditional and loop patterns we start by building the shortest-path tree (that for unweighted graphs coincides with the BFS tree) on the inverted control-flow graph (with edge directions reversed) from the final block; let us call this tree Θ.

We then apply the following algorithm to any vertex C that terminates with a conditional branch:

1) Calculate the lowest common ancestor in Θ of all the children of C in IR. This will be the S vertex, which we need so we know where the conditional or loop statement ends, which is when we can stop generating conditional code.

2) Decide if it is a conditional statement or a loop:

if C has either one or at least three outgoing edges in IR, then it is a conditional statement;

elsif C is a child of itself, then it is a loop;

else it is a loop if and only if C has a child B, different from C, such that the shortest path between B and S in Θ includes C.

As S is a common ancestor in Θ of all the child blocks of C in IR, this algorithm is obviously correct.

Now let’s look at the complexity of the algorithm. We define LCA(A, B) to be the lowest common ancestor of A and B, and write “A ≤ B” to mean that B is an ancestor of A.

The good news is that the query “does the shortest path from vertex X to vertex Y in the tree include vertex Z” is equivalent to:

(X ≤ Z or Y ≤ Z) and Z ≤ LCA(X, Y),

because the shortest path between X and Y consists of ascending from X to LCA(X, Y) and then descending to Y.

The lowest-common-ancestor and is-ancestor queries on a tree can be answered quickly — with some preprocessing, of course. For example, if the Tarjan’s off-line lowest common ancestor algorithm is used, the complexity is linear in the number of edges and vertices.

Here you can find the links to the implementation:

https://github.com/shdown/isekai/blob/939e28ba07c6d50ee9f75b34978d0a07c27f1b6d/src/graph_utils.cr

https://github.com/shdown/isekai/blob/939e28ba07c6d50ee9f75b34978d0a07c27f1b6d/src/bitcode_parser.cr#L81