Branches (While Loop - !0)

Consider the code block:

int x = 0;

while(x <= 10) {
  x++;

}
x += 4;

while(x > 10) {
  x--;
}
x -= 4;  

When we have a loop condition that involves a non-zero argument, we need to re-express that condition in terms of a zero argument. The code block above translates to:

int x = 0;

while(x -10 <= 0) {         // or [ 0 <= 10 - x]
  x++;
}
x += 4;

while(x -10 > 0) {          // or [ 0 > 10 - x]
  x--;
}
x -= 4;  

Converting to assembly gives:

0:   ld $0x0000, r0       # x = 0

# first loop, false conditional at top
2:   ld $0xfffffff6, r1   # r1 = -10
8:   mov r0, r2            
     add r1, r2           # r2 = x - 10
     bgt r2, 0x0012       # if x-10 > 0, x > 10, !(x <= 10) goto +3

     inc r0               # x++
     br 0x0008            # goto -4

12:  add $4, r0           # x += 4

# second loop, true conditional at bottom
14:  ld $0xfffffff6, r1   # r1 = -10
1a:  br 0x0022            # goto +4
1c:  dec r0               # x--;

     mov r0, r2
     add r1, r2           # r2 = x - 10;
22:  bgt r2, 0x001c       # if x-10 > 0, x > 10 goto -3

     add $-4, r0          # x -= 4  

Note: the condition being evaluated in each case is identical, it is just treated differently. In one block, it is used as a condition to exit the loop; in the other, it is used as a condition to continue the loop.

Bonus: Advanced Branching (Switch Statement)

Consider a switch statement:

switch(r0) {
  case 0: ~~~0;
          break;
  case 1: ~~~1;
          break;
  ...
  case 0xf: ~~~f;
            break;
  default:
            ~~~default;
}
~~~done

If / Else Naive Implementation

  0: rr move r1, r0     # r1 = r0
     beq r1, 0x??0      # goto "0" case
     dec r1             # r1 = r0 - 1
     beq r1, 0x??1      # goto "1" case
     ...
     dec r1             # r1 = r0 - f
     beq r1, 0x??f      # goto "f" case
     ~~~default         # execute "default" case
     br 0x???           # exit
??0: ~~~0               # execute "0" case
     br 0x???           # exit
??1: ~~~1               # execute "1" case
     br 0x???           # exit
...
??f: ~~~f               # execute "f" case
???: ~~~done            # outside the switch

Case     # conditions evaluated      # branches taken
  0                 1                      2
  1                 2                      2
 ..
  e                15                      2
  f                16                      1
 <0                17                      1
 >f                17                      1
Sum:              170                     31

Every additional case adds progressively more and more to the number of conditions evaluated. The number of branches taken remains constant for each execution path.

Switch / Jump Table Implementation

   0:  move r1, r0          # r1 = r0
       dec r1               
       bgt r1 0x08          # ensure >=0 (in range)
       br "def"             # if not, goto "default" case
   8:  move r1, r0          # r1 = r0
       ld $0xFFFFFFF1, r2   # r2 = -f
       add r2, r1           # r1 = r0 - f
       bgt r1 "def"         # goto "default" case if > f
       move r1, r0          # r1 = r0 (and r1 is in range)
       ld $0x00001000, r2   # r2 = & jump table
       jmp *(4*r1, r2)      # jump to the right case
"c0":  ~~~0                 # case "0"
       br "done"            # exit
"c1":  ~~~1                 # case "1"
       br "done"            # exit
...
"cf":  ~~~f                 # case "f"
       br "done"            # exit
"def": ~~~~default         # "default" case
"done" ~~~~done            # outside the switch
...
1000:  &"c0"    # jump table, filled with addresses of cases
       &"c1"
       ...
       &"cf"

Case     # conditions evaluated      # branches taken
  0                 3                      3
  1                 3                      3
 ..
  e                 3                      3
  f                 3                      3
 <0                 1                      1
 >f                 2                      1
Sum:               48                     47

More cases do not grow the number of conditions evaluated per path, and the number of branches taken per path remains constant.

Special Note: the number of branches taken in the above example is higher than that of the if/else example due to the branch on the ">0" case. This branch can be eliminated by reversing the test:

   0:  move r1, r0          # r1 = r0
       not r1               # 
       inc r1               # r1 = -r0
       bgt r1 "def"         # goto "default" if <0
   8:  move r1, r0
       ld $0xFFFFFFF1, r2   # r2 = -f
       add r2, r1           # r1 = r0 - f
       bgt r1 "def"         # goto "default" case if > f
       move r1, r0          # r1 = r0 (and r1 is in range)
       ld $0x00001000, r2   # r2 = & jump table
       jmp *(4*r1, r2)      # jump to the right case
...

Case     # conditions evaluated      # branches taken
  0                 3                      2
  1                 3                      2
 ..
  e                 3                      2
  f                 3                      2
 <0                 1                      1
 >f                 2                      1
Sum:               48                     32

For more information, see Implementing Common Control Structures in Assembly Language and/or C to Assembly Translation III.

Branches (While Loop - false)

while(x != 0 ) {
  ~~~i
  ~~~i
  ~~~i
}
~~~o

Address	Machine	Assembly	Notes
	assume r0 = x
0:	9005	beq r0, 0x10	branch to exit
2:	~~~i		true case
	~~~i
	~~~i
8:	80FC	br 0x00	loop
10:	~~~o		exited loop

Note 1: 2 branches total, 1 branch taken on critical path.

Note 2: conditional at top.

Branches (While Loop - true)

while( x == 0 ) {
 ~~i
 ~~i
 ~~i
}
~~ o

Naive / Literal

Address	Machine	Assembly	Notes
	assume r0 = x
0:	9002	beq r0, 0x04	conditional
2:	8005	br 0x0c	exit
4:	~~~i		true case
	~~~i
	~~~i
a:	80FB	br 0x00	loop
c:	~~~o		exited loop

Note: 3 branches total, 2 branches in critical path.

Preferred

Address	Machine	Assembly	Notes
	assume r0 = x
0:	8004	br 0x08	prime (need to check condition)
2:	~~~i		true case
	~~~i
	~~~i
8:	90FD	beq r0, 0x02	loop conditional
	~~~o		exited loop

Note 1: 2 branches total, 1 branch in critical path.

Note 2: conditional at bottom.

Branches (If Statements)

If without Else

if( x == 0 ) {
  x = 1;
}
x++;

Address	Machine	Assembly	Notes
	assume r0 = x
0:	9002	beq r0, 0x0004	if true, skip false
2:	8004	br 0x000a	false case, skip true
4:	0000 0000 0001	ld $0x0001, r0	true case
a:	6300	inc r0	after if block

Note: the false case comes first since we branch somewhere else when true.

If with Else

if( x == 0 ) {
  x = 1;
} else {
  x = 2;
}
x++;

Address	Machine	Assembly	Notes
	assume r0 = x
0:	9005	beq r0, 0x000a	if true, skip false
2:	0000 0000 0002	ld $0x0002, r0	false case
8:	8004	br 0x0010	skip true
a:	0000 0000 0001	ld $0x0001, r0	true case
10:	6300	inc r0	after if block

Structures in Machine Memory

typedef struct {
  int a;
  int b;
} T;

T foo;
T bar[2];
T* h = (T*) malloc( 3* sizeof(T) );  // reserve heap space

address	value	offset	c name	region
0:	~~~~~			program
	...
1000:	???? ????	00	foo.a	global variables
	???? ????	01	foo.b
1008:	???? ????	00	bar[0].a
	???? ????	01	bar[0].b
	???? ????	02	bar[1].a
	???? ????	03	bar[1].b
1018:	0000 2000	00	h
	...
2000:	???? ????	00	h[0].a	heap
	???? ????	01	h[0].b
	???? ????	02	h[1].a
	???? ????	03	h[1].b
	???? ????	04	h[2].a
	???? ????	05	h[2].b

Gold Machine's Branching Instructions

opcode	format	semantics	example	example assembly (RISC)
branch	8-oo	pc = pc-2 + 2*o	1000: 8006	br 0x100c
branch if equal	9roo	if r[r] == 0, pc = pc-2 + 2*o	1000: 9206	beq r2, 0x100c
branch if greater	aroo	if r[r] > 0, pc = pc-2 + 2*o	1000: a206	bgt r2, 0x100c
jump	b--- aaaaaaaa	pc = a	1000: b000 00008000	jmp 0x8000
get pc	6f-d	r[d] = pc-2	6f01	gpc r1
jump indirect	croo	pc = r[r] + 2*o	c103	jmp 0x3(r1)
jump indirect, b+o	droo	pc = m[ r[r] + 4*o ]	d103	jmp *0x3(r1)
jump indirect, index	eir-	pc = m r[r] + 4*r[i] ]	e120	jmp *(4*r1,r2)

Note 1: All "branch" machine language instructions are relative to the current PC (though their assembly versions are absolute). All "jump" instructions are absolute.

Note 2: the semantics for each branch instruction include a -2. This is to undo the +2 increment to PC during the fetch stage.

Corollary to Note 2: a branch of "0" should make the branch instruction branch to itself. So if you ever branch by 0, you will enter an infinite loop. This simplifies branching forwards and backwards.

Pointer Example

C	Gold Assembly	Gold Machine	Notes
int a = -1;		1000: ffffffff	&a = 1000
int b = -1;		1004: ffffffff	&b = 1004
int* p = &a;		2000: 00001000	&p = 2000
void foo() {
*p = 5;	ld $0x5, r0 ld $0x2000, r1 ld 0x0(r1), r2 st r0, 0x0(r2)	0000 0000 0005 0100 0000 2000 1012 3002	r0 ~ *p r1 = &p r2 = p *p = *p
p = &c;	ld $0x1004, r2 st r2, 0x0(r1)	0200 0000 1004 3201	r2 = &c p = &c
*p = 8;	ld $0x8, r0 st r0, 0x0(r2)	0000 0000 0008 3002	r0 ~ *p *p = *p
}

TODO: insert slide show

Tracing Machine Execution

Short Example

previous next

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13.

Store Example

previous next

1, 2, 3, 4, 5, 6, 7.

Mapping C to Assembly to Machine Language

Short Example

C	Gold Assembly	Gold Machine	Notes
void foo() {
int a = 0;	ld $0x0, r1	0100 0000 0000	r1 ~ a
a++;	inc r1	6301
a *= 2;	add r1, r1	6111
}

Store Example

C	Gold Assembly	Gold Machine	Notes
int a = 2;		1000: 0000 0002	&a = 1000
void foo() {
	ld $0x1000, r0 ld 0x0(r0), r1	0: 0000 0000 1000 1001	r0 = &a r1 = a
a++;	inc r1	6301
a *= 2;	add r1, r1	6111
	st r1, 0x0(r0)	3001	a = r1
}

Array Example

C	Gold Assembly	Gold Machine	Notes
int[] a = {0,1,2,3};		1000: 0000 0000 0000 0001 0000 0002 0000 0003	&a[] = 1000
int b = -1;		2000: ffff ffff	&b = 2000
void sum() {
b = 0;	ld $0x0, r2	0: 0200 0000 0000	r2 ~ b
	ld $0x1000, r0	0000 0000 1000	r0 = &a
b += a[0];	ld 0x0(r0), r1 add r1, r2	1001 6112
b += a[1];	ld 0x4(r0), r1 add r1, r2	1101 6112
b += a[2];	ld 0x8(r0), r1 add r1, r2	1201 6112
b += a[3];	ld 0xc(r0), r1 add r1, r2	1301 6112
	ld $0x2000, r0 st r2, 0x0(r0)	0000 0000 2000 3002	r0 = &b b = r2
}