teaching machines

CS 352 Lecture 27 – If * 3

November 11, 2016 by . Filed under cs352, fall 2016, lectures.

Dear students,

Let’s do another Program This:

Translate the following code to ARM assembly: 
if n >= 0 && n <= 9
  print 'digit'

A straightforward implementation might take this approach:

  mov r1, #0
  mov r2, #0

  // Let's assume n is in r0.
  cmp r0, #0
  movgt r1, #1
  cmp r0, #9
  movlt r2, #1

  and r3, r1, r2
  cmp r3, #1
  bne after
then:
  ldr r0, =message
  bl printf

after:
  ...

We put conditional predicates on the mov instructions. If both r1 and r2 get set, then we print.

The problem with this is that we have violated the short-circuiting semantics of the && operator. If the first clause is false, we don’t even consider the second. Short-circuiting is important, and a lot of code relies on it. Like this snippet:

str.length() > 0 && str.charAt(0) == '<'

We should not touch any part of the second clause unless we know the first is true. We can implement this like so:

  cmp r0, #0
  blt after

  cmp r9, #9
  bgt after

then:
  ldr r0, =message
  bl printf

after:
  ...

One interesting takeaway from this example is that the && operation from our high-level language does not actually translate into an and instruction. Many high-level constructs become something completely different at the low-level, defying one’s intuition!

If we have time, we’ll do a comparison between conditional branching and simpler predicated instructions. Here’s a program that generates a bunch of random numbers and then branches to an odd or even count instruction:

.text
.global main

main:
  push {lr}

  mov r0, #133
  bl srand

  mov r4, #0 // i
  mov r7, #0 // count of odds
  mov r8, #0 // count of evens
  b check
loop:
  bl rand
  and r0, r0, #1

  cmp r0, #1
  beq odd
even:
  add r8, r8, #1
  b after
odd:
  add r7, r7, #1
after:

  add r4, r4, #1

check:
  ldr r6, =n
  ldr r6, [r6]
  cmp r4, r6
  bne loop

  mov r0, r5

  pop {lr}
  mov pc, lr

.data
n:
  .word 100000000

We’ll rewrite this without the branches and time both versions using perf from the linux-tools package:

perf_4.4 stat --repeat=2 -e cpu-clock ./myprogram

We’ll close with one or two array processing examples:

See you next class!

Sincerely,

P.S. It’s Haiku Friday!

pc pinpoints code
Pounces cat-like, like popcorn
Propels computing

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

in_range.c

int n = 17;

void in_range() {
  if (n >= 0 && n <= 9) {
    printf("in range");
  }
}

sum.s

.text
.global main

main:
  push {lr}



  ldr r0, =numbers  // r0 = &numbers
  mov r1, #0        // r1 = 0
  b check

loop:
  add r1, r1, r2    // r1 += r2
  add r0, r0, #4    // r0 += 4

check:
  ldr r2, [r0]      // r2 = *r0
  cmp r2, #0
  bne loop

  ldr r0, =message
  bl printf

  pop {lr}
  mov pc, lr

.data
numbers:
  .word 1, 2, 3, 4, 5, 6, 7, 8, 9, 0

message:
  .asciz "The sum is %d!\n"