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 !

the issue

When I started using the HRMc compiler, I noticed that there were several useless jumps and labels all over the place, sometimes leading to huge chains of jumps that could just be removed in the generated code.

Let’s start with this simple program that puts in the output tape every non-zero item from the input tape.

# example.hrm
start:
# read from inbox
emp = inbox
# put in the output queue if emp is non-zero
if nz then
    outbox
endif
# start again
jmp start

The program is then compiled (without optimizations!) to this “assembly” snippet. As you can see, the compiler here generates some ad-hoc labels to implement the if operation with jumps.

The little ASCII diagram of the jumps lets us understand two things about the flow of the program

1. the jumps both reach the same instruction (the last jump), because it’s tagged with two labels (_hrm_1, _hrm_endif_1)
2. the last jump goes back to the first instruction, tagged start

# hrmc example.hrm --no-unreachable --no-jump-compression
start:        inbox      <----(2)------|
              jez _hrm_1 ----------|   |
              outbox               |   |
              jmp _hrm_endif_1 --| |   |
_hrm_1,                          | |   |
_hrm_endif_1: jmp start  <--(1)--|-|   |
                     |-----------------|

The problem with this code here is that the game CPU would spend nearly a third of its time following jumps. Running it with hrm-interpreter, with random inputs we’d notice that jumps are more than half of all instructions executed from the CPU. Isn’t it a waste of time? What if we could avoid the “jump chain” and go directly to the right instruction?

the algorithm

Let’s define a “jump chain”: if a jump A, either conditional or unconditional, refers to a label that tags another jump instruction B, then we have a jump chain. An example of a jump chain is (1) in the previous example: it’s safe to replace jmp _hrm_endif_1 with jmp start, as they’re clearly equivalent in that context.

The idea is then to shrink/compress the jump chain: every time we find a jump, either conditional or unconditional, we find the first non-jump operation directly reachable from that node in the AST, then take the label associated with that instruction and replace the original jump’s label with it.

Let’s then look at a commented version of the algorithm, as implemented in conversion.py of hrm-compiler

# compress_jumps: Instruction[] -> Instruction[]
def compress_jumps(ast):
    # labels_in_ast : Instruction[] -> Map<label: string, position: number>
    # labels_in_ast maps every label to the position of the instruction tagged by the label
    labels_positions = labels_in_ast(ast)

    compressed_ast = []

    for index, ast_item in enumerate(ast):
        if type(ast_item) in [p.JumpOp, p.JumpCondOp]:
            jump_going_nowhere = False
            try:
                # get the first position executable by `_label`
                _label = ast_item.label_name
                next_pos = labels_positions[_label]
            except KeyError:
                # `_label` does not tag any instruction.
                # save the instruction: removing jumps, either conditional or
                # unconditional, modified the semantics of the source program
                compressed_ast.append(ast_item)
                # go to the next instruction
                continue

            # let's visit the jump chain:
            # a jump chain stops when
            # (1) the current instruction is not an unconditional jump,
            # (2) the instruction was already visited (countermeasure to loops)
            # (3) the jump instruction refers to a label that does not tag any instruction.
            # the algorithm updates `_label` until the jump chain stops.
            visited = [False for i in ast]
            while type(ast[next_pos]) == p.JumpOp and \
                not visited[next_pos] and \
                not jump_going_nowhere:
                visited[next_pos] = True
                _label = ast[next_pos].label_name
                try:
                    next_pos = labels_positions[_label]
                except KeyError:
                    jump_going_nowhere = True

            # no matter why the previous loop stopped,
            # _label is guaranteed to contain the label that is located
            # nearest to the first non-`jmp` instruction.
            # let's then create add the new jump instruction to compressed_ast
            if type(ast_item) == p.JumpOp:
                compressed_ast.append(p.JumpOp(_label))
            else:
                compressed_ast.append(p.JumpCondOp(_label, ast_item.condition))
        else:
            compressed_ast.append(ast_item)

    return compressed_ast

As hinted by the previous ASCII diagram, the algorithm exploits the graph-like features of the instruction array (named AST here, but it's more similar to a compiler-specific Intermediate Representation, or IR): the algorithm does a depth-first visit of the graph defined by the IR: the visit stops when one of three conditions become true:

1. the currently visited instruction is not a conditional jump
2. the instruction was already visited
3. it is not possible to visit the next instruction

When the visit stops, _label is the name of the label that is nearest to the non-jmp instruction that the CPU is going to execute at the end of the jump chain.

There are two possible cases:

1. we reached the non-jmp instruction: _label is the name of the label tagging that instruction
2. we couldn't reach the non-jmp instruction: the algorithm stopped at the jmp instruction, and we can get the name of the label from it

the result

If we enable this optimization in the compiler, it will generate the following code:

# hrmc example.hrm --no-unreachable # jump-compression is enabled
start:        inbox     <------|
              jez start  ---->-|
              outbox           |
              jmp start  ---->-|
_hrm_1,                        |
_hrm_endif_1: jmp start  ---->-|

Now we see that every jump instruction now refers to the right label: it means we are not going to waste time jumping around!

Conclusions

In this article, I tried to explain a simple optimization I've implemented in HRMc, a simple compiler for the Human Resource Machine game's assembly language. Thank you for spending your time reading these notes.

Did you enjoy this explanation? Does this optimization have a real/academic name? Feel free to tell me on Twitter ! If you liked this article, please consider offering me a Ko-fi !

How does it work?

The source language is a superset of the target language, so the translation is easy. The translation from the source to the target language is done in multiple passes, and each pass removes a part of the superset language or rewrites part of the AST to make the next pass' work simpler. At the end of the process, the AST that the "code generation" routines work on is only made of target language's instructions and statements, making the "code generation" phase very simple and straightforward.`

Let me explain what I mean by looking at this simple example: put in the OUTBOX only the items in the INBOX that are not ZERO, and keep a counter of non-zero items.

# let's define an alias for a memory cell, to make it easier
# to understand what the code does. The cell is already
# set to zero by the game.
alias 1 counter
pickone:
# retrieve an item from the INBOX
emp = inbox
# if `emp` is not ZERO, then put the value stored
# inside `emp` into the OUTBOX
if nz then
    incr counter
    outbox
endif
jmp pickone

The compiler would parse it, generate the IR and perform two conversions. The first one, in our case, changes all the if nz (if nonzero value in emp) to if ez (if emp contains a zero value), to normalize the IR for the second pass.

alias 1 counter
pickone:
emp = inbox
# transformation here!
if ez then
    # nothing to do here!
else
    incr counter
    outbox
endif
jmp pickone

The second conversion, well, converts the if to target-language structures: conditional and unconditional jumps. The previous pass makes the work of this one easier, making the code simpler, as it has to handle just this case.

alias 1 counter
pickone:
emp = inbox
# if -> jump here! simplify code generation!
jez _hrm_if_1
incr counter
outbox
jmp _hrm_endif_1
_hrm_if_1:
_hrm_endif_1:
# the `if` is fully transformed, and ends here.
jmp pickone

After that, the code generation phase converts our IR to the target language. Again, the code generation' implementation is simpler because we translated higher level IR into equivalent IR that is nearer to the target language and thus easier to translate.

As it is a tool to help me think about the problem I'm trying to solve, this language is far from being a real, complete language with all the usual things you may be used to find in other languages. If you look at the code in the repository, you may discover I didn't implement a while construct: it's not a problem, you can build it with if and jmp, or conditional jumps. Instead, I preferred to create some helpers to let me think about a problem without worrying about "oh I don't have jnz, just jez, so I have to write this thing differently", I can just throw a if nz and let the compiler handle that.

Things to work on

The compiler can generate better code, to fix some problems due to the new instructions and operations added to the base language. After this post, I wrote a couple of optimizations, such as jump compression (to remove useless unconditional jumps) and unreachable code removal (to remove instructions that will be never executed and make the generated code smaller), but I'm sure there are other optimizations I can implement.

Another thing to consider is that the "emulated processor" the gamer is programming in Human Resource Machine is very limited: it only has one register, and its instruction set is very small. Those limitations make it difficult to create a richer language, but I think it'll be fun to overcome these challenges.

Do you like this project? Whisper (or shout!) your opinions via Twitter, or consider offering me a coffee on Ko-fi !

Before we go further... what is a buildpack?

A buildpack is a collection of scripts that prepares a virtual machine (dyno in Heroku slang) to build and run your application in the cloud. In this article we're going to see how to build one of these.

Ok, let's see...

The documentation about custom buildpack explains how a buildpack works, and which files are necessary to successfully build and run a project in the cloud (foundry).

Custom buildpacks need three (executable) files:

• bin/detect

  This script determines whethever or not to apply the buildpack to an application. Basically it checks if you are using the wrong buildpack for your project, and stops you before you try to use the Java buildpack for a Rust application. Buildpacks can also be "framework-specific", so it makes sense to check if you're trying to run a Gradle buildpack to build an application meant to be built by Maven.

  It is run with only one parameter: the path to the build directory, where the source code and the files loaded during cf push are loaded. In a Rust application, it will contain your source code.

  CloudFoundry expects it to return 0 if everything is ok and the buildpack can continue, 1 otherwise.

• bin/compile

  This script is in charge of configuring the environment and generating a runnable binary from sources. A Rust buildpack would download rustup, install it and use cargo build to build your application.

  This script is run with two parameters: the build directory and the cache directory. The last one will contain the assets created during the build process. A Rust buildpack we will speak about later used to store the compiled libraries there, in order to "cache" dependencies and make deploys faster.

• bin/release

  This script must generate a .yml file that describes how the application should be executed. An example of such a .yml follows:

  default_process_types:
      web: ./target/release/YOUR_APPLICATION_NAME # in Rust, this suffices.
  

  This script only takes one parameter, the build directory. Please note: some developers use this script as a simple template, in order to automatically generate the correct .yml file during the execution of bin/compile.

An example of a buildpack that has these three scripts is the Rust buildpack built by Aaron Santavicca. If we look at it, we can see that:

• bin/detect checks if our project has a Cargo.toml file. If it doesn't, it cannot be built with cargo.
• bin/compile installs rustup, builds your application with cargo and generates the real bin/release script.
• bin/release is a template to be modified when running bin/compile.

...and that's it. CloudFoundry runs these scripts, reads the .yml file and runs everything as requested. Yay!

Hey, I'm used to Heroku, do I need to change my trusted buildpack?

No, you don't need it.

CloudFoundry buildpacks are compatible with Heroku ones: the good guy HoverBear provides a working buildpack for Rust that relies on multirust and caches build artifacts (mostly dependencies), so you don't have to lose five minutes to build the world every time you launch cf push (at least, it used to do that before RustFest, to brutally fix an unexpected problem with removed dependencies and broken slug size limits).

However, making them run is a bit trickier. When I was evaluating Rust buildpacks, I looked at the HoverBear one, and... bin/release script wasn't there. What kind of magic was going here? How did it even work?

After some testing (and reading the docs), I found out that there are... two ways to make buildpacks missing bin/release work.

The first one is adding the command attribute to the manifest.yml file you wrote for your application. A command: ./target/release/YOUR_APPLICATION_NAME should suffice.

The second one is to add a Procfile to the project. A Procfile is a file that tells CloudFoundry (or Heroku) which command has to be executed to start your application. A simple Procfile for a Rust app may just contain the line

web: ./target/release/YOUR_APPLICATION_NAME

Conclusion

My team and I are developing web apps on Predix (a CloudFoundry instance managed by GE), and I use Rust to build some quick-and-dirty test backends to generate random responses for our frontend. To run Rust on CF, I needed to understand how to build a new application on it, and I spent some time to fully understand how things work. I hope these notes can be useful for you too!