teaching machines

CS 352 Lecture 25 – Branching

November 7, 2016 by Chris Johnson. Filed under cs352, fall 2016, lectures.

Dear students,

We ended our discussion of ARM assembly last time wanting to tell the user if they answered a math problem correctly or incorrectly. To support this, we needed to branch between two different sequences of code. We’ve seen unconditional branches that jump our program counter to some other labeled section, but what we need here is a conditional branch.

ARM doesn’t have any conditional branch instructions. It has something better. Just about every individual instruction can be made conditional by appending one of these suffixes onto the instruction name:

Prior to the condition check, the program status register must be set, probably using a cmp instruction. The register has four bits (N, Z, C, and V) that are examined by a condition instruction to determine if it should be executed or not.

We’ll explore use of conditional branches by writing programs that do the following:

• Flip a coin and report heads or tails.
• Mimic echo.

One of the biggest payoffs of learning assembly is you see how high-level languages perform their magic. For example, consider this if statement:

if cond
  f
else 
  g

When compiled, this becomes:

  cond
  bne else
then:
  f
  b after
else:
  g
after:
  ...

What if cond has a binary logical operator, like &&? How does shortcircuiting work at the assembly level? It just breaks the condition up into pieces, and branches after each one. For example, consider this code, which checks if a number n is between 100 and 200:

if 100 <= n && n <= 200
  f

In ARM assembly, this looks like:

  ldr r0, =n
  ldr r0, [r0]
  cmp r0, #100
  blt after
  cmp r0, #200
  bgt after
then:
  f
after:
  ...

What happens to a loop that looks like this in a high-level language?

while cond
  f
  update

We might, at first, make a direct translation to assembly:

loop:
  cond
  beq end
  f
  update
  b loop
after:
  ...

But this is not ideal. On all but the final iteration of the loop, that first branch is wasted computation. Then we do a second branch. The potential jumping around incurred by branching can frustrate performance, so we’d like to avoid that as much as possible. We can eliminate one branch by restructuring this as a do-while loop, but doing a one-time, pre-loop jump to the while:

b check
loop:
  f
  update
check:
  cond
  bne loop
after:
  ...

See you next class!

Sincerely,

P.S. Here’s the code we wrote together…

heads_tails.s

.text
.global main

main:
  push {lr}
  
  mov r0, #0
  bl time
  bl srand
  bl rand  

  mov r1, r0

  and r0, r0, #1
  cmp r0, #1

  beq else

then:
  ldr r0, =heads_message
  b end
else:
  ldr r0, =tails_message
end:

  bl printf
  // is r0 even? or odd?

  pop {lr}
  
  mov pc, lr

.data
heads_message:
  .asciz "H %d\n"

tails_message:
  .asciz "T %d\n"