.
CPSC 213 – 2018 Winter Term 2
Exam Review: Reading and writing assembly
1 [1 marks] Answer the following questions on static control flow.
1a Giveassemblycodeforthefollowing.Assumexandyareglobalintegervariables.
if (x > 0 && x < 10) {
y = x;
} else {
y = 0;
}
ld $x, r0
ld (r0), r0
bgt r0, L0
br L2
L0: ld $10, r1
mov r0, r2
not r2
inc r2
add r2, r1
bgt r1, L1
L2: ld $0, r0
L1: ld $y, r1
st r0, (r1)
# r0=&x
# r0=x
# if (x>0) goto L0 # else goto L2
# r1=10
# r2=x
#
# r2=-x
# r1 = 10-x
# if (x>10) goto L1 # r0=0
# r1=&y
# y=r0(0orx)
1b Consideraprocedurewiththefollowingsignature:int foo(int a, int b); Give assembly code for the following.
x = foo(x, y);
ld $x, r1
ld (r1), r0
ld $y, r2
ld (r2), r2
deca r5
deca r5
st r1, (r5)
st r2, 4(r5) # arg1 = y
gpc $6,r6 j foo inca r5 inca r5
ld $x, r1
st r0, (r1)
#r6=ra
# foo(x, y)
# sp += 8
# r1 = &x
# x = foo(x,y)
# r1 = &x
# r0 = x
# r2 = &y
# r2 = y
# sp -= 8
# arg0 = x
.
2 [1 marks] Give the SM213 assembly for the foo procedure below. Assume the caller of foo’s prologue was implemented correctly (so r5 is pointing to the right place). Similar to in lecture, assume that we use r0 for return values, r5 for the stack pointer, r6 for the return address, and that parameters are passed using the stack. Comments are not required.
int foo(int n) {
int a = 0;
int i;
for (i = 0; i < n; i++) {
a += bar(a); }
return a; }
foo: ld $-12, r1
add r1, r5
st r6, 8(r5)
ld $0, r0
ld $0, r1
L0: ld 12(r5), r2
not r2
inc r2
add r1, r2
beq r2, L1
st r0, (r5)
st r1, 4(r5)
deca r5
st r0, (r5)
gpc $6, r6
j bar
inca r5
ld (r5), r3
add r3, r0
ld 4(r5), r1
inc r1
br L0
L1: ld 8(r5), r6
ld $12, r1
add r1, r5
j (r6)
#
# allocate stack
# save ra into stack # a=0
# i=0
# r1=x
#
# r2=-x
# r2=i -x
# if i=x goto L1
# save a into stack # save i into stack
# caller prologue # get ra
# call bar(a)
# caller epilogue # r3=a
# r0=a
# r1=i
# i++
# goto L0
# load ra
# callee epilogue # deallocate stack # return a
+ bar(a)
2
.
3 [1 marks] Give the SM213 assembly for the foo procedure below. Assume the caller of foo’s prologue was implemented correctly (so r5 is pointing to the right place). Similar to in lecture this semester, assume that we use r0 for return values, r5 for the stack pointer, and r6 for the return address. Comments are not required.
int foo(int a, int b) {
int x = a+1;
int y = a+b;
bar();
if (x > y) {
return x*2;
} else
return y; }
}
foo:
ld $0xfffffff4, r1
add r1, r5
st r6, 0x8(r5)
ld 0xc(r5), r1
ld 0x10(r5), r2
add r1, r2
inc r1
st r1, 0x0(r5)
st r2, 0x4(r5)
gpc $0x6, r6
j bar
ld 0x0(r5), r1
ld 0x4(r5), r2
mov r2, r3
not r3
inc r3
add r1, r3
bgt r3, ret
mov r2, r0
br end
shl $1, r1
mov r1, r0
ld 0x8(r5), r6
ld $12, r1
add r1, r5
j 0x0(r6)
# r1 = -12
# allocate callee part of stack frame # store ra
#r1=a
# r2 = b
#r2=a+b
#r1=a+1
#savex =a+1intostackframe #savey =a+bintostackframe #putra into r6
# bar()
#r1=x
#r2=y
#r3=y
#r3=-y #r3=x-y #gotoretifx>y #r0=y
# goto end #r1=2*x #r0=2*x
# load ra into r6 #r1=12
# callee epilogue
# return r0
ret: end:
3
.
4 [8 marks] Procedure Calls. Give the SM213 assembly for the longest procedure shown below. Assume the caller of longest’s prologue was implemented correctly (so r5 is pointing to the right place). Similar to in lecture this semester, assume that we use r0 for return values, r5 for the stack pointer, and r6 for the return address.
struct Rect {
int length;
int width; };
int longest(struct Rect* r) {
if (r->length > r->width)
return r->length;
return r->width;
}
longest: deca r5
st r6, (r5)
ld 4(r5), r1
ld (r1), r1
ld (r1), r2
ld 4(r1), r3
mov r3, r4
not r4
inc r4
add r2, r4
bgt r4, L1
mov r3, r0
br L2
L1: mov r2, r0
L2: ld (r5), r6
inca r5 j (r6)
# allocate space for ra in stack frame # store ra in stack
# r1=&r
# r1=r
# r2 = r->length
# r3 = r->width
# r4 = r->width
#
# r4 = -r->width
# r4 = r->length – r->width
# if r->length > r->width goto L1
# r0 = r->width
# goto L2
# r0 = r->length
# load ra into r6
# deallocate stack frame
# return
4
.
5 [1 marks] The following procedures use the call/return conventions described in class, where we use r0 for return values, r5 for the stack pointer, and r6 for the return address.
foo: deca r5
deca r5
st r6, 4(r5)
ld $0, r1
st r1, 0(r5)
ld 8(r5), r2
# allocate callee portion of stack frame # int result
# save return address on stack #r1=0=i’
#result=0 #r2=a; #r3=n
#r3=-n #r4=i’ #r4=i’ -n
ld 12(r5),
not r3
inc r3
L0: mov r1, r4
add r3, r4
beq r4, L1
bgt r4, L1
r3
ld(r2,r1,4),r4 deca r5
st r4, 0(r5)
gpc $6, r6
j bar
inca r5
ld 0(r5), r4
add r0, r4
st r4, 0(r5)
inc r1
br L0
L1: ld 0(r5), r0
ld 4(r5), r6
inca r5
inca r5
j (r6)
bar: ld 0(r5), r7
ld $1,
ld $0,
and r7,
beq r4,
mov r7,
L2: j
r4
r0
r4
L2
r0
(r6)
# goto L1
# goto L1
#r4=a[i’]
# allocation caller portion of stack # save a[i’] on stack as first arg
# compute ra
# r’ = bar(a[i])
# deallocate caller portion of stack # r4 = result
# result’ += result’ + r’
# result = result’ + r’
# i’++;
# goto L0
# r0 = result
# get ra from stack
# deallocate callee portion of stack
# return result
#x=arg1
#r4=1
#r0=0
#r4=arg1&1 #gotoL2if(arg1&1)==0 #r0=arg1
# return r0 (arg1 or 0 depending on cond)
if i’==n if i’>n
5
.
5a Carefullycommenteverylineofcodeabove. 5b ConverttheassemblyintoC.
int bar(int arg1) {
if (arg1 & 1)
return arg1;
return 0;
}
int foo(int *a, int n) {
int result = 0;
for (int i = 0; i < n; i++) {
result += bar(a[i]);
}
return result;
}
5c Whatisthepurposeofthecodefrompreviouspage?Givethesimplest,plainEnglishdescriptionyoucan. foo returns the sum of all odd numbers in the array a.
6
.
6 [1 marks] Comment the following assembly code and then translate it into C.
fn: deca r5
st r6, (r5)
ld 4(r5),r1 ld $1,r0
ld $-1, r2 add r1, r2 bgt r2, L0
br L3
L0: and r1, r0
beq r0, L1
mov r1, r3
add r1, r1
add r3, r1
inc r1
br L2
L1: shr $1, r1
L2: deca r5
st r1, (r5)
gpc $6, r6
j fn
inca r5
inc r0
L3: ld (r5), r6
inca r5
j (r6)
# allocate stack frame # store ra
#r1=n
#r0=1
# r2=-1
# r2=n-1
# ifn>1gotoL0
# goto L3
# r0=n &1
# if n&1 goto L1
# r3=n
# r1=2n
# r1=3n
# r1=3n+1
# goto L2
# r1=n/2
# allocate stack frame
# save n on stack
# r6=ra
# jump to fn
# deallocate stack frame
# r0 = 1 + value returned from fn # r6=ra
# deallocate stack frame
# return r0
6a WriteyourtranslatedCcodebelow:
int fn(int n) {
if (n <= 1)
return 1;
if (n & 1)
return 1 + fn(3n + 1);
else
}
return 1 + fn(n / 2);
7
.
7 [1 marks] The following procedure uses the call/return conventions described in class, where we use r0 for return values, r5 for the stack pointer, and r6 for the return address.
fn: deca r5 # Allocate space for left
deca r5 # Allocate space for ra
st r6, 4(r5) # Save return address in stack ld 8(r5), r0 # r0 = argument n
beq r0, L1 # ifnis0,return0
ld 4(r0), r1 # r1 = n->left
deca r5 # Allocate space for argument st r1, (r5) # Save n->left as argument
gpc $6, r6
j fn
inca r5
st r0, (r5) # Store return address in stack
ld 8(r5), r0 # r0 = argument n
gpc $6, r6
j fn
inca r5
ld (r5), r2 # r2 = left
mov r2, r3
not r3
inc r3
add r0, r3
bgt r3, L0
mov r2, r0
# r3 = left
# r3 = ̃left
# r3 = -left
# r3 = right-left
# if right>left skip next line (r0 is right)
# r0 = left
# increment return value
# Save return address in r6
# Call fn(n->left)
# Free argument space
ld 8(r0), r1 # r1 = n->right
deca r5 # Allocate space for argument
st r1, (r5) # Save n->right as argument
# Save return address in r6
# Call fn(n->right)
# Free argument space
L0: inc r0
L1: ld 4(r5), r6 # Retrieve return address
inca r5
inca r5
j (r6)
# Free space for ra
# Free space for left
# Return
Assumethefunctionabovereceivesapointertoastruct treenode,definedasfollows:
struct treenode {
int value;
struct treenode *left, *right;
};
7a Carefullycommenteverylineofcodeabove. 7b ConverttheassemblyintoC.
7c Whatisthepurposeofthecodefrompreviouspage?Givethesimplest,plainEnglishdescriptionyoucan. fn returns the height of the binary tree.
int fn(struct treenode *t) {
if (!t) return 0;
int i = fn(t->left), j = fn(t->right);
return i > j ? i + 1 : j + 1;
}
8