CS计算机代考程序代写 Java assembly CPSC 213 Introduction to Computer Systems

CPSC 213 Introduction to Computer Systems
Unit 1d
Static Control Flow
1
Readings for Next 2 Lectures
‣ Textbook
• Condition Codes – Loops • 3.6.1-3.6.5
2

Control Flow
‣ The flow of control is
• the sequence of instruction executions performed by a program
• every program execution can be described by such a linear sequence
‣ Controlling flow in languages like Java
3
Loops (S5-loop)
‣ In Java
}
int s=0;
int i;
int a[] = {2,4,6,8,10,12,14,16,18,20};
void foo () {
for (i=0; i<10; i++) s += a[i]; } ‣In C public class Foo { static int s = 0; static int i; static int a[] = new int[10]; static void foo () { for (i=0; i<10; i++) s += a[i]; } 4 Implement loops in machine int s=0; int i; int a[] = {2,4,6,8,10,12,14,16,18,20}; void foo () { for (i=0; i<10; i++) s += a[i]; } ‣ Can we implement this loop with the existing ISA? 5 Loop unrolling ‣ Using array syntax int s=0; int i; int a[10] = {2,4,6,8,10,12,14,16,18,20}; void foo () { i = 0; s += a[i]; i++; s += i++; ... s += i++; } ‣ Using pointer-arithmetic syntax for access to a? ‣ Will this technique generalize a[i]; a[i]; • will it work for all loops? why or why not? 6 Control-Flow ISA Extensions ‣ Conditional branches • goto

if
‣ Options for evaluating condition
• unconditional
• conditional based on value of a register (==0, >0 etc.) – goto

if 0
• conditional check result of last executed ALU instruction – goto

if last ALU result 0
‣ Specifying target address
• absolute 32-bit address
– this requires a 6 byte instruction, which means jumps have high overhead – is this a serious problem? how would you decide?
– are jumps for for/while/if etc. different from jumps for procedure call?
7
PC Relative Addressing
‣ Motivation
• jumps are common and so we want to make them as fast as possible
• small instructions are faster than large ones, so make some jumps be two bytes
‣ Observation
• some jumps such as for/while/if etc. normally jump to a nearby instruction
• so the jump distance can be described by a small number that could fit in a byte
‣ PC Relative Addressing
• specifies jump target as a delta from address of current instruction (actually next)
• in the execute stage pc register stores the address of next sequential instruction
• the pc-relative jump delta is applied to the value of the pc register – jumping with a delta of 0 jumps to the next instruction
• jump instructions that use pc-relative addressing are called branches
‣ Absolute Addressing
• specifies jump target using full 32-bit address
• use when the jump distance too large to fit in a byte
8

ISA for Static Control Flow (part 1)
‣ ISA requirement (apparently) • at least one PC-relative jump
– specify relative distance using real distance / 2 — why?
• at least one absolute jump
• some conditional jumps (at least = and > 0) – make these PC-relative — why?
‣ New instructions (so far)
Name
Semantics
Assembly
Machine
branch
pc ← (a==pc+oo*2)
br a
8-oo
branch if equal
pc ← (a==pc+oo*2) if r[c]==0
beg rc, a
9coo
branch if greater
pc ← (a==pc+oo*2) if r[c]>0
bgt rc, a
acoo
jump
pc ← a
ja
b— aaaaaaaa
9
Implementing for loops (S5-loop) for (i=0; i<10; i++) s += a[i]; ‣ General form • in C and Java for (; ; )
• pseudo-code template

loop: goto end_loop if not


goto loop
end_loop:
10

‣ This example
• pseudo code template
loop:
end_loop:
i=0
goto end_loop if not (i<10) s+=a[i] i++ goto loop • ISA suggest two transformations - only conditional branches we have compared to 0, not 10 - no need to store i and s in memory in each loop iteration, so use temp_ to indicate this loop: temp_i=0 temp_s=0 temp_t=temp_i-10 goto end_loop if temp_t==0 temp_s+=a[temp_i] temp_i++ goto loop end_loop: s=temp_s i=temp_i 11 loop: temp_i=0 temp_s=0 temp_t=temp_i-10 goto end_loop if temp_t==0 temp_s+=a[temp_i] temp_i++ goto loop end_loop: s=temp_s i=temp_i • assembly code loop: Assume that all variables are global variables ld $0x0,r0 ld $a, r1 ld $0x0,r2 ld $0xfffffff6, r4 mov r0, r5 add r4, r5 beq r5, end_loop ld (r1, r0, 4), r3 add r3, r2 inc r0 br loop #r0=temp_i=0 # r1 = address of a[0] #r2=temp_s=0 # r4 = -10 # r5 = temp_i # r5 = temp_i-10 # if temp_i=10 goto +4 # r3 = a[temp_i] # temp_s += a[temp_i] # temp_i++ # goto -7 # r1 = address of s # s = temp_s # i = temp_i end_loop: ld $s, r1 st r2, 0x0(r1) st r0, 0x4(r1) 12 Implementing if-then-else (S6-if) if (a>b)
max = a;
else
max = b;
‣ General form
• in Java and C
– if else
• pseudo-code template
temp_c = not
goto then if (temp_c==0)
else:
goto end_if
then: end_if:
13
‣ This example
• pseudo-code template
temp_a=a
temp_b=b
temp_c=temp_a-temp_b
goto then if (temp_c>0)
else: temp_max=temp_b
goto end_if
then: temp_max=temp_a
end_if: max=temp_max
• assembly code
ld $a,r0
ld 0x0(r0), r0 ld $b,r1
ld 0x0(r1), r1 mov r1, r2
not r2
inc r2
add r0, r2
bgt r2, then
else: mov r1, r3
br end_if
then: mov r0, r3
end_if: ld $max, r0
st r3, 0x0(r0)
#r0=&a
# r0 = a
#r1=&b
# r1 = b
#r2=b #temp_c=!b #temp_c=-b
# temp_c = a-b
# if (a>b) goto +2 # temp_max = b
# goto +1
# temp_max = a
# r0 = &max
# max = temp_max
14

Static Procedure Calls
15
Code Examples (S6-static-call)
public class A {
static void ping () {}
}
public class Foo {
static void foo () {
A.ping (); }
}
‣Java
• a method is a sub-routine with a name, arguments and local scope
• method invocation causes the sub-routine to run with values bound to arguments and with a possible result bound to the invocation
void ping () {}
void foo () {
ping ();
}
‣C
• a procedure is …
• a procedure call is …
16

Diagraming a Procedure Call
void foo () {
ping ();
}
‣ Caller
• goto ping
-j ping
• continue executing
void ping () {}
‣ Callee
• do whatever ping does
• goto foo just after call to ping()
– ??????
Questions
How is RETURN implemented?
It’s a jump, but is the address a static property or a dynamic one?
17
Implementing Procedure Return
‣ return address is
• the address the procedure jumps to when it completes
• the address of the instruction following the call that caused it to run • a dynamic property of the program
‣ questions
• how does procedure know the return address? • how does it jump to a dynamic address?
18

‣ saving the return address
• only the caller knows the address
• so the caller must save it before it makes the call
– caller will save the return address in r6
• there is a bit of a problem here if the callee makes a procedure call, more later …
• we need a new instruction to read the PC – we’ll call it gpc
‣ jumping back to return address
• we need new instruction to jump to an address stored in a register – callee can assume return address is in r6
19
ISA for Static Control Flow (part 2)
‣ New requirements
• read the value of the PC
• jump to a dynamically determined target address
‣ Complete new set of instructions
Name
Semantics
Assembly
Machine
branch
pc ← (a==pc+oo*2)
br a
8-oo
branch if equal
pc ← (a==pc+oo*2) if r[c]==0
beg a
9coo
branch if greater
pc ← (a==pc+oo*2) if r[c]>0
bgt a
acoo
jump
pc ← a
ja
b— aaaaaaaa
get pc
r[d] ← pc
gpc rd
6f-d
indirect jump
pc ← r[t] + (o==pp*2)
j o(rt)
ctpp
20

Compiling Procedure Call / Return
void foo () {
ping ();
}
foo: ld $ping, r0
gpc r6
inca r6
j (r0)
# r0 = address of ping ()
# r6 = pc of next instruction
# r6 = pc + 4
# goto ping ()
# return
void ping () {}
ping: j (r6)
21