Instructions(3)

여기서는 RISC-V의 함수 호출 매커니즘과 스택의 프레임 구조를 알아본다.

Function Calls

함수 호출은 한 프로그램이 다른 코드 블록(함수)를 실행하도록 제어를 이동시키는 것이다.

예를 들어 아래 c 코드를 생각할 수 있다.

void main() {
  int y;
  y = sum(42, 7);
}

int sum(int a, int b) {
  return (a + b);
}

여기서 main 은 caller, sum 은 callee다.

caller와 callee의 역할은 아래와 같다.

역할	하는 일
Caller (호출자)	- 인자(argument)들을 레지스터에 전달 - 복귀 위치를 저장 - 함수로 점프
Callee (피호출자)	- 전달받은 인자로 작업 수행 - 결과를 반환 레지스터에 저장 - 호출 지점으로 복귀 - 호출자가 필요로 하는 레지스터나 메모리를 망가뜨리지 않음

프로그램 카운터 (PC)

PC는 CPU가 다음에 실행할 명령어의 주소를 저장하는 레지스터다.

따라서 CPU가 어디서부터 명령을 읽고 실행해야 하는지를 기억하는 포인터다.

예시로는 아래와 같다. 이렇게 저장되어 있다고 하자.

주소	명령어
0x0000	addi a0, zero, 5
0x0004	addi a1, zero, 2
0x0008	add a2, a0, a1
0x000C	jal func

그러면 CPU가 실행할 때는 이렇게 PC가 변한다.

단계	실행 명령	PC 값
1	addi a0, zero, 5	0x0000
2	addi a1, zero, 2	0x0004
3	add a2, a0, a1	0x0008
4	jal func 실행 시 PC가 func의 주소로 바뀜	0x000C → func 주소

CPU는 항상 PC가 가리키는 주소의 명령어를 실행하고, 그 다음엔 PC + 4로 자동 이동한다.

함수 호출 명령어

jal func

jump and link

다음 명령어 주소(PC + 4)를 ra에 저장한다.

(4인 이유는 RISC-V의 모든 명령어가 4바이트 정렬이라서 다음 명령어는 현재 명령어로부터 4바이트 만큼 떨어진 곳에 존재)

PC를 func의 주소로 변경한다 = 점프한다.

main: jal simple
      add s0, s1, s2
      ...

simple: jr ra

여기서 ra = PC + 4 = 복귀 주소 저장

PC = simple = 점프 실행

jr ra

jump register

ra에 저장된 주소로 복귀한다. (caller로 돌아간다)

jr ra

즉 PC = ra .

인자 전달과 반환값 처리

아래와 같은 C 코드가 있다고 하자

int main() {
    int y;
    y = diffofsums(2, 3, 4, 5);
}

int diffofsums(int f, int g, int h, int i) {
    return (f + g) - (h + i);
}

그러면 RISC-V의 코드는 아래와 같다.

main:
addi a0, zero, 2  # arg0 = 2
addi a1, zero, 3  # arg1 = 3
addi a2, zero, 4  # arg2 = 4
addi a3, zero, 5  # arg3 = 5
jal  diffofsums   # 호출
add  s7, a0, zero # 반환값 저장: y = a0

diffofsums:
add  t0, a0, a1   # t0 = f + g
add  t1, a2, a3   # t1 = h + i
sub  s3, t0, t1   # s3 = (f+g)-(h+i)
add  a0, s3, zero # return value -> a0
jr   ra           # 복귀

1. 인자 2,3,4,5 는 모두 a0 ~ a3 레지스터에 들어간다.
2. jal diffofsums → ra 에 복귀 주소 저장 후 점프
3. diffofsums 의 계산 결과가 a0 에 저장된다.
4. jr ra 로 main으로 복귀한다.
5. add s7, a0, zero 로 y 에 결과를 저장한다.

RISC-V의 코드를 보면 마치 전역변수 같다고 생각할 수 있지만 전역변수는 아니고 레지스터다.

따라서 diffofsums 에서 사용된 레지스터 (t0, t1, s3) 함수 종료 접근 할 수는 있지만 언제든 덮어씌워질 여지가 있다. 따라서 접근하면 안된다는 개념에서 접근 불가능하다고 할 수 있다.

Stack

스택은 함수 실행 중에 잠시 데이터를 저장하는 메모리 공간이다.

CPU가 함수 호출할 때 잠시 값을 쌓아두고 함수가 끝나면 다시 꺼내는 개념.

함수를 호출할 때는 여러 가지 값이 임시로 필요하다.

• 복귀 주소(ra)
• 함수 인자들
• 지역 변수들
• 보존해야 할 레지스터

그래서 스택이 필요하다.

RISC-V에서는 스택을 메모리의 높은 주소에서 낮은 주소 방향으로 쌓는다.

주소	설명
높은 주소	오래된 데이터
↓	새 데이터 쌓임
낮은 주소	현재 스택 포인터(sp)가 가리키는 위치

스택 포인터 (sp)

sp (x2) 레지스터는 현재 스택의 최상단을 가리킨다.

예를 들어서 스택에 공간을 만들려면

addi sp, sp, -4   # 스택 포인터를 아래로 내려서 4바이트 공간 확보
sw   s3, 0(sp)    # s3 값을 스택에 저장

다 사용했다면

lw s3, 0(sp)      # 저장해둔 값 복원
addi sp, sp, 4    # 스택 포인터 되돌리기 (공간 해제)

실제로 사용한다면 아래와 같이 사용할 수 있다.

diffofsums:
  addi sp, sp, -12      # 스택에 공간 확보 (12바이트)
  sw   s3, 8(sp)        # s3 저장
  sw   t0, 4(sp)        # t0 저장
  sw   t1, 0(sp)        # t1 저장
  ...
  lw   s3, 8(sp)        # s3 복원
  lw   t0, 4(sp)        # t0 복원
  lw   t1, 0(sp)        # t1 복원
  addi sp, sp, 12       # 스택 공간 해제
  jr   ra

Preserved Registers

함수 호출 시에 어떤 레지스터를 누가 저장해야 하는지 정하는 규칙들이다.

스택에서 봤던 건 값을 저장하는 수단이었고 이번에는 어떤 값을 저장해야 하는가를 정리한다.

함수를 호출할 떄는 아래와 같은 상황이 대부분일거다.

main() → diffofsums()

main에서 어떤 레지스터를 쓰고 있다가 diffofsums를 호출하면 diffofsums도 자기 계산을 위해서 레지스터들을 막 사용할거다.

그럼 main의 값들이 덮어써질 수 있다.

이런 상황을 방지하고자 누가 무엇을 저장할지 약속을 정한다.

s: 함수가 끝나도 값이 유지되어야 함

t: 함수 안에서 잠깐 쓰고 버림

그래서 아까 위에서 봤던 diffofsums 를 다시 보자

여기서 임시값이 스택포인터에 저장되고 있는데 이렇게 하면 반칙이다.

아래처럼 수정할 수 있다.

# s3 = result
diffofsums:
  addi sp, sp, -4
  sw   s3, 0(sp)        # s3만 저장 (필요한 유일한 preserved)
  add  t0, a0, a1
  add  t1, a2, a3
  sub  s3, t0, t1
  add  a0, s3, zero
  lw   s3, 0(sp)
  addi sp, sp, 4
  jr   ra

Non-Leaf Function Calls

리프 함수는 다른 함수를 부르지 않는 함수라 해서 리프 함수다.

논 리프 함수는 함수 안에서 다른 함수를 부르는 함수다.

문제점은 ra 레지스터가 덮어 씌워진다는 것이다.

리프 함수에는 ra 를 신경 안 써도 됐었다.

왜냐하면 ra 는 caller 가 보낸 복귀 주소를 보존하고 있기 때문에 그냥 jr ra 하면 돌아가면 됐기 때문이다.

하지만 논 리프 함수는 아래처럼 생겼다.

func1:
  ...                # 어떤 계산
  jal func2          # 다른 함수 호출
  ...                # 이후 실행될 코드
  jr  ra             # func1 복귀

main이 func1을 호출할 때 ra가 저장 되었을텐데 func1이 func2를 호출하면서 기존의 ra가 덮어씌워진다.

따라서 논 리프 함수는 다른 함수를 호출하기 전에 이렇게 해야된다.

func1:
  addi sp, sp, -4     # 스택 공간 확보
  sw   ra, 0(sp)      # 현재 복귀 주소 백업
  jal  func2          # 다른 함수 호출 (ra 덮임)
  lw   ra, 0(sp)      # 원래 ra 복원
  addi sp, sp, 4      # 스택 해제
  jr   ra             # 원래 caller로 복귀

ra 를 스택에 저장해 두는 것이다.

예시

# f1 (non-leaf function) uses s4-s5 and needs a0-a1 after call to f2
f1:
  addi sp, sp, -20   # make space on stack for 5 words
  sw   a0, 16(sp)
  sw   a1, 12(sp)
  sw   ra, 8(sp)     # ra 백업
  sw   s4, 4(sp)     # callee-saved s4 백업
  sw   s5, 0(sp)     # callee-saved s5 백업
  jal  f2            # call f2 (ra 덮임)
  ...                # 이후 계산
  lw   ra, 8(sp)
  lw   s4, 4(sp)
  lw   s5, 0(sp)
  addi sp, sp, 20
  jr   ra

Recursive Functions

이건 재귀함수다.

스택 프레임이 계층적으로 쌓이고 복원되는 구조를 보여준다.

factorial:
    addi sp, sp, -8       # 스택 공간 확보 (8바이트)
    sw   a0, 4(sp)        # n (argument) 저장
    sw   ra, 0(sp)        # 복귀 주소 저장

    addi t0, zero, 1      # t0 = 1
    bgt  a0, t0, else     # if (a0 > 1) -> else로
    addi a0, zero, 1      # base case: factorial(0 or 1) = 1
    addi sp, sp, 8        # 스택 해제
    jr   ra               # 복귀

else:
    addi a0, a0, -1       # n - 1
    jal  factorial        # factorial(n - 1) 호출

    lw   t1, 4(sp)        # t1 = n 복원
    lw   ra, 0(sp)        # 복귀 주소 복원
    addi sp, sp, 8        # 스택 해제

    mul  a0, t1, a0       # a0 = n * factorial(n - 1)
    jr   ra               # 복귀

1. 맨 처음에는 main과 같은 상위 함수가 factorial을 불렀다고 가정하자.
2. sp로 공간을 확보한 뒤 a0와 ra의 값을 기억하도록 저장한다.
3. 이때의 ra는 main의 jal factorial의 다음 라인 주소
4. a0 는 3이라고 가정하자
5. insctruction에 따라 bgt 라인에서 else로 브랜치 한다.
6. 여기서는 a0 를 1 감소 시킨다.
7. 그리곤 factorial로 jump and link 한다.
8. 이때 ra는 갱신된다. ra는 else의 jal factorial의 다음 라인 주소
9. factorial의 instruction에 따라 sp로 공간을 확보한 뒤 새로운 a0와 ra를 저장
10. 이때 a0의 값은 2이므로 bgt라인에서 다시 else로 이동.
11. a0를 1 감소 시키고 다음 라인인 jal factorial 로 다시 factorial로 jump and link
12. 다시 sp로 공간을 확보한 뒤 새로운 a0와 ra를 저장, 여기서 ra는 else에서의 jal factorial의 다음 라인 주소
13. a0도 1이고 t0도 1이니까 bgt에서 안 걸리고 다음 라인 실행
14. 이제부터 factorial 계산 실행

1. a0를 1로 셋
2. sp 공간 해제 ⇒ 2칸 위로 이동 (여기서의 위치 0은 ra(else에서의 jal factorial의 다음 라인 주소)를 가지고, 위치 4에서는 2라는 값을 가지고 있음)
3. ra로 jump register , 여기서 ra는 else에서의 jal factorial의 다음 라인 주소
4. 4(sp) 의 2라는 값이 t1에 , 0(sp) 의 jal factorial의 다음 라인 주소값이 ra에 저장됨 (step 2 참고)
5. sp 공간 해제 ⇒ 2칸 위로 이동 (여기서의 위치 0은 ra(main의 jal factorial의 다음 라인 주소)를 가지고, 위치 4에서는 3라는 값을 가지고 있음)
6. mul로 a0와 t1를 곱해서 a0에 저장 ⇒ 1 * 2 = 2
7. ra로 jump register , 여기서 ra는 else에서의 jal factorial의 다음 라인 주소
8. 4(sp) 의 3라는 값이 t1에 , 0(sp) 의 main의 jal factorial의 다음 라인 주소값이 ra에 저장됨 (step 5 참고)
9. mul로 a0와 t1를 곱해서 a0에 저장 ⇒ 2 * 3 = 6
10. ra로 jump register, 여기서 ra 는 main의 jal factorial의 다음 라인 주소