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
}