» CS 352 Lecture 26

CS 352 Lecture 26 – If++

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

Dear students,

Let’s start with a Program This!

Translate this high-level pseudocode into ARM assembly:
if n == 0
  print 'R'
else if n == 1
  print 'Y'
else if n == 2
  print 'G'

A straightforward translation of this might look something like this:

  // Let's assume n is in r0.
  cmp r0, #0
  beq red
  cmp r0, #1
  beq yellow
  cmp r0, #2
  beq green
  
  // No cases apply.
  b after

red:
  mov r1, #82
  b after

yellow:
  mov r1, #89
  b after

green:
  mov r1, #71

after:
  ldr r0, =message

What’s unfortunate about this straightforward translation is that it must walk through a series of conditional branches. Every conditional branch causes a disruption in the implicit flow of instructions, which messes up pipelining and fast execution. There’s got to be a better way! And there is: switch. In a high-level language, a switch looks something like this:

switch n
  case 0
    print 'R'
  case 1
    print 'Y'
  case 2
    print 'G'

Instead of implementing a switch by walking a conditional ladder, let’s create an array of the labels that we might branch to. We’ll call this array jumptable:

jumptable:
  .word red, yellow, green

Now, we can jump to the appropriate label by using r0 to index into this array:

ldr r1, =jumptable       // r1 = &jumptable
add r1, r1, r0, LSL #2   // r1 = r1[r0] (really r1 = r1 + r0 * 4)
ldr r1, [r1]             // r1 = *r1
mov pc, r1

Is a switch faster than a conditional ladder? Probably, as it turns a linear search for the address into a constant-time jump. It does come at the cost of extra storage for the labels array. If all the cases contain the same number of instructions, the labels array isn’t really necessary and we can just compute the destination address. Each of our cases is two instructions (8 bytes) long, so our calculation looks like this:

ldr r1, =red             // r1 = &red
add r1, r1, r0, LSL #3   // r1 = r1[r0] (really r1 = r1 + r0 * 8)
mov pc, r1

Bear in mind that C# and Java 7 allow switching on strings. It’s an interesting thought exercise to figure out how they implement that.

Here’s your TODO list to complete for we meet again:

Read chapters 1 through 6 of ARM Assembler in Raspberry Pi. On a quarter sheet, write down 2-3 questions or observations inspired by your reading.

See you next class!

Sincerely,

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

ryg.s

.text
.global main

main:
  push {lr}

  sub r0, r0, #1

  cmp r0, #0
  beq red
  cmp r0, #1
  beq yellow
  cmp r0, #2
  beq green

red:
  mov r1, #82
  b end
yellow:
  mov r1, #89
  b end
green:
  mov r1, #71

end:
  ldr r0, =message
  bl printf

  pop {lr}
  mov pc, lr

.data
message:
  .asciz "Color: %c\n"

ryg2.s

.text
.global main

main:
  push {lr}

  sub r0, r0, #1

  //cmp r0, #0
  //beq red
  //cmp r0, #1
  //beq yellow
  //cmp r0, #2
  //beq green

  ldr r1, =jumptable     // r1 = &jumptable
  add r1, r1, r0, LSL #2 // r1 = r1[r0]  ; r1 = r1 + r0 * 4
  ldr r1, [r1]           // r1 = *r1
  mov pc, r1

red:
  mov r1, #82
  b end
yellow:
  mov r1, #89
  b end
green:
  mov r1, #71

end:
  ldr r0, =message
  bl printf

  pop {lr}
  mov pc, lr

jumptable:
  .word red, yellow, green

.data
message:
  .asciz "Color: %c\n"