[CA] Lecture #10
Leaf Procedure Example
// C code
int leaf_example (int g, int h, int i, int j){
int f;
f = (g+h) - (i+j);
return f;
}
// g~j: x10~x13, f: x20
// temporaries x5, x6: g+h = x5, t+j = x6
- Memory - stack 저장: x5, x6, x20
- caller --> collee --> caller
--> stack에 저장: collee에 의해 사용되어 값이 변하는 것만 저장한다.
Local Data on the Stack
// Assembly code
leaf_example:
addi sp, sp, -12 // stack에 12 byte 공간 확보
sw x5, 8(sp) // base: sp, offset: 8인 주소의 stack에 register x6값을 store
sw x6, 4(sp)
sw x20, 0(sp)
add x5, x10, x11 // x5 = x10 + x11
add x6, x12, x13
sub x20, x5, x6
addi x10, x20, 0 // return: x10
lw x20, 0(sp) // stack --> register
lw x6, 4(sp)
lw x5, 8(sp)
addi sp, sp, 12 // stack pointer 원래 위치로 이동
jalr x0, 0(x1) // return address(PC + 4): x0
Register Usage
- x5~x7, x28~x31: temporary registers
--> Not preserved by the callee. (stack에 저장할 필요x) - x8~x9, x18~x27: saved registers
--> Preserved by the callee. (stack에 저장)
Non-Leaf Procedures
: Procedures that call other procedures.
- caller가 stack에 저장해야 되는 것: return address, arguments and temporaries needed after the call.
--> Restore from the stack after the call.
Non-Leaf Procedure Example
// C code
int fact (int n){
if (n<1)
return 1;
else
return n*fact(n-1);
}
// Assembly code
fact:
addi sp, sp, -8 // stack 공간 확보
sw x1, 4(sp) // x1: return address
sw x10, 0(sp) // x10: n
addi x5, x10, -1 // x5 = n-1
bge x5, x0, L1 // if(x5>0), branch to L1
addi x10, x0, 1 // else, set x10(return value) to 1
addi sp, sp, 8
jalr x0, 0(x1)
L1: addi x10, x10, -1 // n = n-1
jal x1, fact // jump to fact --> fact(n-1)
addi x6, x10, 0
lw x10, 0(sp)
lw x1, 4(sp)
addi sp, sp, 8
mul x10, x10, x6
jalr x0, 0(x1) // return
1) x10에 2를 먼저 넣어놓고, 함수를 호출한다.
x10 = 2
jal x1, fact // 함수 호출, x1: return address (PC + 4)
2) stack에 x1, x10을 저장하기 위한 8-byte 공간을 마련한다.
addi sp, sp, -8
3) stack에 x1, x10의 값을 저장한다.
sw x1, 4(sp) // x1: return address
sw x10, 0(sp) // x10: 2
4) if문을 수행한다.
addi x5, x10, -1 // x5 = 2-1 = 1
bge x5, x0, L1 // if(x5>0), branch to L1
5) x5(1) > 0이므로, L1으로 branch한다.
addi x10, x10, -1 // x10 = 2-1 = 1: fact(1)을 호출하기 위한 준비 과정
jal x1, fact // fact으로 jump
6) fact 함수를 수행한다. --> fact(1)
addi sp, sp, -8 // stack에 8-byte 공간 마련
sw x1, 4(sp) // x1: L1+8 (???)
sw x10, 0(sp) // x10: 1
addi x5, x10, -1 // x5 = 1-1 = 0
bge x5, x0,L1 // if(x5>0), branch to L1
7) L1으로 branch
addi x10, x10, -1 // x10 = 1-1 = 0: fact(0)을 하기 위한 준비 과정
jal x1, fact // jump to fact
8) fact 함수를 수행한다. --> fact(0)
addi sp, sp, -8
sw x1, 4(sp) // x1: L1+8
sw x10, 0(sp) // x10: 0
addi x5, x10, -1 // x5 = 0-1 = -1
bge x5, x0, L1 // x5 == -1이므로, branch하지 않는다.
9) L1으로 branch하지 않고, fact: 를 마저 진행한다.
addi x10, x0, 1 // x10 = 1: return 1
addi sp, sp, 8 // sp = sp+8: stack pointer 이동
jalr x0, 0(x1) // jump to x1
10) jalr x0, 0(x1)
addi x6, x0, 0 // x6 = 1
lw x10, 0(sp) // x10 = 1
lw x1, 4(sp) // x1 = L1+8
addi sp, sp, 8
mul x10, x10, x6 // x10 = 1 * 1
jalr x0, 0(x1) // jump to x1
11) jump to x1
addi x6, x10, 0 // x6 = 1
lw x10, 0(sp) // x10 = 2 (stack에 저장된 x10값이 2였음)
lw x1, 4(sp) // x1 = L1+8
addi sp, sp, 8
mul x10, x10, x6 // x10 = 2 * 1
jalr x0, 0(x1) // jump to x1
Q. L1의 범위? (어떻게 아나요?
Character Data
- ASCII: 128 characters
- Latin-1: 256 characters
- Unicode: 32-bit character set --> 2^32
RISC-V Addressing for Wide Immediates and Addresses
- immediate: 12-bit --> -2^11~(2^11 - 1)
Wide Immediate Operand: lui
▶ lui (Load Upper Immediate) --> U type
: 상위 20-bit의 immediate를 사용한다.
Addressing in Branches
▶ SB format:
- PC-relative addressing
Target address = PC + immediate * 2 (LSB = 0으로 고정하기 때문)
Addressing in Branches (Example)
Unconditional jump-and-link Instructions (jal)
▶ UJ-type format:
Unconditional jump-and-link Instructions (jal) (Example)
PC Relative Addressing
RISC-V Addressing Mode Summary
- immediate addressing: addi
- register addressing: add
- base or displacement addressing: lw, sw
- PC-relative addressing: beq, bne --> PC + offset(immediate)
--> PC(현재 사용하는 instruction)을 기준으로 얼마나 jump?
RISC-V Instruction Encoding
Effect of Compiler Optimization
Fallacies
Concluding Remarks
▶ Design principles:
- Simplicity favors regularity.
- Smaller is faster.
- Good design demands good compromises.
▶ Make the common case fast.
▶ Layers of software/hardware.
- Compiler, Assembler, Hardware