Isekai LLVM update #2: conditionals and loops

How to recognize conditional statements and loops in LLVM IR code

Ivan Glushenkov
Aug 7, 2019 · 3 min read

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:
Image for post
Image for post

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 “AB” 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:

(XZ or YZ) 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

Sikoba Network

Ivan Glushenkov

Written by

IT Entrepreneur interested in software engineering, management, business thinking and personal development.

Sikoba Network

SikobaPay is a blockchain-based system for registering, tracking and clearing debt. We help to #reduceMoneyDependency by unlocking hidden financial resources and #boostLocalEconomies, especially in developing countries.

Ivan Glushenkov

Written by

IT Entrepreneur interested in software engineering, management, business thinking and personal development.

Sikoba Network

SikobaPay is a blockchain-based system for registering, tracking and clearing debt. We help to #reduceMoneyDependency by unlocking hidden financial resources and #boostLocalEconomies, especially in developing countries.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store