Editing Basic Assembly Programming (section)

== Control Flow ==

Most useful programs aren’t a “straight line” of instructions to do and then stop. We usually want to change what we’re doing depending on some input, or repeat some code multiple times. For this, we have '''jump instructions'''. Jump instructions let us break out of the normal control flow of “do this instruction, then do the next one in order.” Instead, we get to say “do this instruction, then ''jump'' to the 10th instruction and keep going from there” (for example).

OVERTURE jump instructions take the instruction number to jump to from register 0 (so it is easy to <code>loadi</code>) and a “value” against which they can check a “condition” from register 3 (so that it can be the result of the last arithmetic/logic operation). The Turing Complete assembler lets you write <code>label some_label_name_here</code>, which makes <code>some_label_name_here</code> a constant that refers to the index of the following instruction.

OVERTURE has several different jump instructions. In the level Conditionals, you implemented a unit that can check if a number is less than 0, equal to 0, or greater than 0. The jump instructions can act ''conditionally'', jumping only if a specified condition is true of the “value.” The condition <code>always</code> can be used to make the jump ''unconditional'' - it will always jump. A typical unconditional jump mnemonic is <code>jump</code>, <code>jmp</code>, or simply <code>j</code>. You may also see <code>branch</code> or <code>b</code>, which is just another word for exactly the same thing. A conditional “Jump if zero” mnemonic could be <code>jump_zero</code>, <code>jmpzero</code>, <code>jtz</code> (jump-true-zero), or simply <code>jz</code>, where “jump if ''not'' zero” might be <code>jfz</code> or <code>jnz</code>. Other typical abbreviations are <code>gt</code> for greater-than, <code>ge</code> for greater-or-equal, and <code>lt</code> and <code>le</code> the same for less than. Some other assembly languages may have even more conditions.

{{Note|text='''“jump” vs “branch”:''' ''Usually'', “jump” instructions are unconditional, and “branch” instructions are conditional. This is not a hard rule and it’s not uncommon for an architecture to offer a <code>b</code> instruction which is just <code>j</code> in disguise.}}

<span id="a-simple-loop-partial-storage-cracker-spoilers"></span>
===== A Simple Loop (partial Storage Cracker spoilers) =====

Let’s write a program that starts with 0, and then repeatedly adds 1 and keeps repeating that until the result is 0 again. We store the value <code>1</code>, which we need repeatedly, in register 2 ''outside'' of the loop, because we don’t need to re-compute it every time. Then we perform the addition, check the value, and, if it’s not zero, move the result to register 1 so that we can keep going.

Notice how we have to go out of our way to move the result of the addition back into register 1 with <code>move|s3|d1</code>. The ''loop body'', or the part of the loop between the label and the jump back to the label, is written to expect that the values to add are already in registers 1 and 2. This is called a ''loop invariant''. It is fact about the state of the machine that ''must'' be true on both entry to and exit from the loop body. It’s very important to think about your loop invariants when writing loops. As the loop body becomes more complicated, failing to maintain the invariants (called ''violating'' the invariant) is a major source of bugs. If you document the invariants well, these bugs are easy to catch!

<pre>loadi|1     # set up register 2
move|s0|d2  # with the value 1
label loop  # the next instruction is the start of the loop
add         # register 3 = register 1 + register 2
loadi|done  # register 0 = address of the instruction after the loop
jz          # jump out of the loop if the result of addition is 0
move|s3|d1  # register 1 = the result of addition
loadi|loop  # load the address of the first loop instruction
j           # and jump to it.

label done</pre>
That’s not so bad! But we can do a bit better.

<span id="a-better-loop-layout"></span>
===== A Better Loop Layout =====

Because our loop has an unconditional jump at the bottom, and a conditional jump in the middle, every iteration of the loop will execute two jump instructions. For OVERTURE, this isn’t a huge deal, but for more complicated architectures this can be very expensive (jumps are typically among the slowest operations a processor can do, because processors are very optimized for “straight-line” code, as conditional jumps might or might not disrupt the flow of the program,and things like speculative execution would not be happy :/ ). What if we could make the conditional branch dual-purpose?

If a conditional jump fails, we always move on to the next instruction in sequence. If that instruction were the instruction after the loop, we wouldn’t need the second branch. Our conditional branch could jump to the top of the loop, and “falling through” to the next instruction could end the loop! The trick is that we have inverted the condition. Instead of jumping if we should ''stop'', we jump if we should ''continue''. This is called the “do-while” loop layout, and it is how almost all loops are written in assembly. It looks like this:

<pre>loadi|1
move|s0|d2
label loop
add
move|s3|d1
loadi|loop
jnz
label done</pre>
And now we have saved one instruction in the loop.

In our case, we didn’t want to check the condition before doing the first addition. But what if we did? We need the condition to be at the bottom of the loop for this to work, right? Indeed, we do. But if we use a second jump instruction to ''enter'' the loop, we don’t have to execute the second jump instruction on every iteration of the loop, and that’s still better. Such a loop might look like this:

<pre>loadi|check
j

label loop
add
move|s3|d1

label check
loadi|loop
jnz

label done</pre>

<span id="if-then-and-if-then-else"></span>
===== If-Then and If-Then-Else =====

Sometimes we want to execute a little piece of code only if some condition holds. And maybe we want to execute a different piece of code only if it fails. In “structured” programming languages, these constructs are called <code>if</code> and <code>if ... else</code>. Just like for loops, our lives get a little bit simpler if we ''invert'' the condition. This is the standard in assembly language programming, so really make sure you get used to that. Demorgan’s Laws can also be quite helpful.

Suppose we want to read an input and output 1 if the number is 10, and zero otherwise. In a structure language, that might look like this:

<syntaxhighlight lang="c">if (input == 10) {
  output 1
}
else {
  output 0
}</syntaxhighlight>

Let’s translate that into assembly. Firstly, we can’t do <code>== 10</code>. What we ''can'' do is <code>input - 10</code>. If the result is 0, the input was 10.

<pre>move|inp|d1 # read from input to register 1
loadi|10
move|s0|d2  # get 10 into register 2
sub         # compare them
loadi|else
jnz         # jump to the else case if input was not 10

label then  # fall through to here if the input was 10
loadi|1
move|s0|out
loadi|done
j

label else
loadi|0
move|s0|out

label done</pre>

A deeper if-elseif-else chain is implemented by simply repeating this inside the <code>else</code> block.