Contents

1 About this module

• Prerequisites:
• Objectives: This module explains how C control structures are compiled to assembly language code.

2 Purpose of this module

This module contains the instructions to convert a C program into assembly language code in a step-by-step manner. While this module is not intended for people who want to write compilers, it is certainly useful for that purpose.

3 C control structures

This section introduces simple transformations that turn regular C code into C code that has no control structures except for “conditional goto” constructs.

3.1 Condition statements

Translates to

If there is no else, then

translates to

This is because the following code optimizes to no code:

3.2 Pre-checking loop

Translates to

3.3 Post-checking loop

Translates to

4 Conditional goto and boolean operators

From the previous section, if a condition involves negation (not), disjunction (or) or conjunction (and), we must first take care of those operators. This section discusses how those operators, while used in conditional goto statements, can be transformed.

4.1 not

Transforms to

4.2 or

becomes

4.3 and

becomes

4.4 Simple reductions

Although the transformations will work in all cases, they are not always necessary.

For example, !(x >= y) is (x < y).

Also, (x < y) || (x > y) is (x != y).

Using algebra to reduce boolean operators saves a bit of control structure transformations, and can lead to more efficient code.

5 Comparisons

With the previous sections, regular C control structures are reduced to conditional goto statements that do not use any boolean operators. This means that the conditional goto statements must only contain comparison operators.

Because the toy processor can only confirm “less than” and “equal to” using a single instruction, we need to translate all comparison operators to these two operators (with the help of some logical operators):

• $x<y$ is just that
• $x>y$ is reversed to $y<x$
• $x\le y$ is $\left(x<y\right)\vee \left(x=y\right)$
• $x\ge y$ is $\left(y<x\right)\vee \left(y=x\right)$
• $x=y$ is just that
• $x\ne y$ is $\neg \left(x=y\right)$

5.1 General compare

is a generalized conditional goto statement. x r y is the abstraction of x is r y. In an actual program, x is an expression, r is a comparison operator (the toy processor is confined to equal-to and less-than), and y is another expression.

For now, however, let us assume that x and y are registers.

This conditional goto statement transforms to the following pseudo assembly instructions:

For example, let us assume the C code is as follows (x and y are unsigned):

Then the matching assembly code is as follows:

Because the toy processor can only compare registers, compare to constants need to first load the constant to a register using the ldi instruction.

6 About nesting and labels

Although the previous sections use the generic labels L0, L1 and L2, your program should use more useful label names. This section recommends a structured method to name the labels.

6.1 Indentation

While most assembly language programs do not make use of indentation, it makes sense to use indentation the same way as in a high level programming language. This is because indentation reflects the structure of an algorithm, and assembly language programs can be well structured like a high level programming language.

6.2 More useful names

Use more useful names, such as loopBegin, loopEnd, else, endIf and etc. whenever it is appropriate.

6.3 Sequential numbers

Constructs of the same nesting level should use sequential numbers as a suffix to differentiate from each other. For example,

translates to

6.4 Nested constructs

Nested constructs should technically use a suffix or prefix notation to indicate how they are nested. A prefix (where the deeper structure is named first) is easier to read, as the first part of the label shows the meaning of the label. However, a suffix is more natural, especially to people who are used to C/C++ programming.

Using the suffix method,

transforms to

The following represents the same logic, but using the prefix method (nested structure named first):

Note that the “sequence number” of each nesting can restart from 1 because the prefix or suffix of the parent structure makes it unique.

An alternative (to more experienced programmers) is to simply use sequential numbers for each construct. As one construct is converted, simply pick the next available sequential number. This method requires that the programmer only perform the translation of one construct at a time. Furthermore, the label names no longer reflect the nested structure of the code.

6.5 Boolean operator reduction transformations

Boolean operator reduction transformation are low level transformations. As such, the labels generated as a result should simply add a suffix to the original labels. For example,

translates to

7 A longer example

Here is a long(er) example to illustrate the concepts introduced in this module. To make the “diff” between revisions stand out more, you can copy-and-paste each section of code into files. Then, use vimdiff or a similar visualized diff command to have the changes highlighted. If you have XWindow running, there is a whole list of these tools: tkdiff, xxdiff, diffuse, gvimdiff, etc.

Let’s say we want to convert the following code into assembly code:

This program no particular “meaning” as in useful behavior, its only purpose is to serve as an example.

First, I can comment out the entire program, and start to work on it little-by-little. This can be done with a single command in vi, there is a reason to learn how to use it!

Next, let us declare the global variables:

The initialization portion is also quite easy.

Adding x to z requires an intermediate register, but otherwise it is also straightforward.

Now let us take care of the inner-most conditional statement. First, we reduce to “ugly” conditional statement code:

DeMorgan’s law allows us to simplify the negated disjunction a little. DeMorgan’s law says $\overline{X+Y}=\bar{X}\cdot Ȳ$.

Now is a good time to take care of the outer conjunction. We can reduce the conjunction by converting the conditional-goto into multiple statements:

We can now take care of the simple transformations:

Now we translate the other conjunction.

Then we turn the conditional goto into native assembly language code: