HRMc optimizations - unreachable code removal

Source

tl;dr: this post explains a compiler optimization based on graph visits to remove the code that won’t be executed in the generated source code

In HRMc I try to keep every transformation as small as possible, have a minimum set of assumptions about the input, and avoid having to think about future transformations. This philosophy means that every pass does just what it should do, but it also implies that some stuff that will be considered “useless” after the transformation is not removed.

Let’s look at the jump compression optimization: after the execution of that transformation, we can see that the last jmp start is not going to be executed.

# hrmc example.hrm --no-unreachable # jump-compression is enabled, unreachable-code is not
start:        inbox     <------|
              jez start  ---->-|
              outbox           |
              jmp start  ---->-|
_hrm_1,
_hrm_endif_1: jmp start  <-------- won't be executed! ever!

Obviously, an optimization named “jump compression” should not bother removing that instruction. We’d need a different pass to deal with that.

traversing the execution graph

Let’s talk about instructions, the execution flow of a program and graphs.

# A simple program in HRM that for each item
# in the inbox, filters and writes all the "zero"s.
start:  inbox
        jez write
        jmp start
        copyto 1   # this won't be executed! pay attention!
write:  outbox
        jmp start

In most programming languages, instructions are executed sequentially, from start to end. To be able to express complex programs, a programming language must leave a way to select different instructions according to a specific state (if <condition>) and a way to repeat instructions until some condition happens (while <condition>). In lower-languages, they are implemented using jumps. Conditional jumps (j<condition> <label>) set the next instruction to the instruction tagged with <label> only if the <condition> is respected, continues to the successive instruction otherwise. Unconditional jumps (jmp <label>) set the next instruction to the one tagged with <label>.

start
+------------+
| inbox      <----------+
+------------+   |      |
      |          |      |
+-----v------+   |      |
| jez write  |   |      |
+------------+   |      |
   |      |false |      |
   |      |      |      |
   |   +--v---------+   |
   |   | jmp start  |   |
   |   +------------+   |
   |true                |
   |                    |
   |   +------------+   |
   |   | copyto 1   |   |
   |   +------------+   |
   |                    |
   |     write          |
+--v---------+          |
|  outbox    |          |
+------------+          |
    |                   |
+---v--------+          |
| jmp start  +----------+
+------------+

This is the execution flow of the program written before: we can see it looks like a graph, and in fact it is! Most of boxes have one outward arrow to the next box, and the box containing a “conditional jump” (jez write) has two arrows pointing to two different boxes! It is clear that there is a one-to-one correspondence between boxes and instructions.

Let’s notice a small thing: there is a box with no arrows pointing to it. It means that the instruction inside the box (copyto 1) won’t be executed! Why can I say so? Because that box is not reachable from the first box: there does not exist a path from inbox to copyto 1. Instead, outbox is reachable: the path is inbox -> jez write -> outbox. copyto 1 is marked as unreachable code, or dead code because it won’t be executed. Removing such instructions does not modify what a program does!

How can we understand if an instruction will be executed? The execution flow graph is… a graph, so we can perform a depth-first search on it and see which nodes are visited or not.

There is a more interesting fact, though: we can use that algorithm to generate a new graph without unreachable instructions! The rule to follow is: if the algorithm visits a conditional jump instruction, always visit the branch that would be executed if the condition would evaluate to false. This rule will help us generate an equivalent code if you linearize the graph.

The non-recursive version of the depth-first search algorithm implemented in conversion.py of hrm-compiler identifies visited nodes and keeps track of the labels associated to the visited nodes.

Did you enjoy this explanation? Tell me what you think about it. If it helped you, please consider offering me a Ko-fi !