# [디지털 논리 설계] Chapter 6 - 9. 재귀 함수와 Jump, Pseudoinstruction

Об этом предложении

[디지털 논리 설계] Chapter 6 - 9. 재귀 함수와 Jump, Pseudoinstruction 지난 편에서는 함수 호출과 Stack을 배웠다. 핵심은 다음과 같았다. 함수 인자 → a0 ~ a7 함수 호출 → jal 복귀 주소 → ra 함수 반환값 → a0 함수 복귀 → jr ra 그리고 함수가 기존 Register 값을 보존해야 할 때는 Stack 을 사용했다. 이번에는 이 내용을 조금 더 확장해서 Non-Leaf Function Recursive Function jal / jalr Pseudoinstruction Label Long Jump 을 공부한다. 1. Leaf Function과 Non-Leaf Function 함수는 다른 함수를 호출하느냐에 따라 구분할 수 있다. Leaf Function 다른 함수를 호출하지 않는 함수이다. 예: f2: 계산 jr ra 자기 할 일만 하고 Caller에게 돌아간다. Non-Leaf Function 다른 함수를 다시 호출하는 함수이다. 예: main ↓ f1 ↓ f2 여기서 f1 은 f2 를 호출한다. 따라서 f1 은 Non-Leaf Function 이다. 2. Non-Leaf Function에서 왜 ra를 저장해야 할까? jal 을 실행하면 돌아올 주소가 ra 에 저장된다. 예: main ↓ jal f1 그러면 ra 에는 f1이 끝난 뒤 main의 어디로 돌아가야 하는지 가 저장된다. 그런데 f1 안에서 다시 jal f2 를 실행하면? jal 은 다시 ra 를 사용한다. 즉 기존 ra 값이 덮어써진다. 3. 그래서 Stack에 ra를 저장한다 다른 함수를 호출하기 전에: addi sp, sp, -4 sw ra, 0(sp) 로 ra 를 Stack에 저장한다. 그다음: jal f2 를 실행한다. f2에서 돌아온 뒤: lw ra, 0(sp) addi sp, sp, 4 로 원래 ra 를 복원한다. 마지막: jr ra 를 통해 원래 Caller로 돌아간다. 4. 전체 흐름 f1 시작 ↓ ra를 Stack에 저장 ↓ f2 호출 ↓ f2에서 복귀 ↓ ra 복원 ↓ 원래 Caller로 복귀 즉 Non-Leaf Function에서는 다른 함수를 호출하면서 복귀 주소가 사라지지 않도록 ra를 보존해야 한다. 5. Function Call 전체 규칙 PDF에서는 함수 호출 과정을 Caller와 Callee로 정리한다. Caller 함수를 호출하는 쪽이다. Caller는 필요하면: Register 저장 ↓ a0 ~ a7에 인자 넣기 ↓ jal로 함수 호출 ↓ a0에서 반환값 받기 ↓ 저장했던 Register 복원 을 수행한다. Callee 호출되는 함수다. Callee는 필요하면: s0 ~ s11 같은 Register 저장 ↓ 함수 실행 ↓ 결과를 a0에 저장 ↓ Register 복원 ↓ jr ra 를 수행한다. 6. Recursive Function 이번에는 재귀 함수다. Recursive Function은 자기 자신을 다시 호출하는 함수 이다. 예: factorial(n) 팩토리얼은 다음과 같이 정의할 수 있다. n! = n × (n-1) × (n-2) × ... × 1 예: 3! = 3 × 2 × 1 = 6 7. 재귀로 factorial 만들기 C 코드: int factorial(int n) { if (n <= 1) return 1; else return n * factorial(n - 1); } 예를 들어: factorial(3) 을 실행하면 factorial(3) = 3 × factorial(2) factorial(2) = 2 × factorial(1) factorial(1) = 1 이다. 그다음 거꾸로 올라온다. factorial(1) = 1 factorial(2) = 2 × 1 = 2 factorial(3) = 3 × 2 = 6 8. 재귀 함수에서 생기는 문제 재귀 함수도 결국 함수가 함수를 호출하는 것 이다. 그런데 이번에는 자기 자신을 호출 한다. 따라서 호출할 때마다 ra a0 같은 값이 계속 바뀔 수 있다. 예를 들어: factorial(3) 에서 a0 = 3 인데, 다음 호출 전에: a0 = 2 가 된다. 그다음 호출에서는: a0 = 1 이 된다. 그런데 나중에 다시 3 × 2 를 계산하려면 이전의 3과 2가 필요하다. 9. 그래서 재귀 함수에서도 Stack이 중요하다 호출하기 전에 필요한 값을 Stack에 저장한다. PDF 예제에서는: addi sp, sp, -8 sw a0, 4(sp) sw ra, 0(sp) 를 사용한다. 즉 Stack에: 현재 n 값 복귀 주소 ra 를 저장한다. 10. 재귀 호출 그다음: addi a0, a0, -1 jal factorial 을 실행한다. 즉: factorial(n - 1) 을 호출한다. 11. 재귀 호출에서 돌아오면 Stack에 저장했던 값을 다시 가져온다. lw t1, 4(sp) lw ra, 0(sp) addi sp, sp, 8 여기서: t1 = 원래 n a0 = factorial(n-1)의 결과 가 된다. 따라서: mul a0, t1, a0 을 하면 a0 = n × factorial(n-1) 이 된다. 12. 재귀에서 Stack이 중요한 이유 재귀 호출은 여러 함수 호출이 겹친다. 예: factorial(3) ↓ factorial(2) ↓ factorial(1) 각 호출마다 자기만의 n ra 값이 필요하다. 그래서 Stack에 각각의 값을 따로 저장한다. 즉: 함수 호출마다 Stack Frame이 하나씩 생긴다. 13. Jump 다시 보기 PDF에서는 이후 Jump를 다시 자세히 설명한다. RISC-V의 무조건 Jump는 크게 jal jalr 두 가지이다. 14. jal 형식: jal rd, imm 동작은: rd = PC + 4 PC = PC + imm 이다. 쉽게 말하면: 현재 다음 명령어 주소를 rd에 저장 ↓ imm만큼 떨어진 위치로 이동 한다. 함수 호출에서 흔히: jal ra, 함수 를 사용한다. 그래서 ra 에 복귀 주소가 저장된다. 15. jalr jalr 는 Jump And Link Register 이다. 형식: jalr rd, rs, imm PDF의 설명대로 개념적으로: rd = PC + 4 PC = rs + SignExt(imm) 이다. 즉 jal 이 현재 PC를 기준으로 이동한다면, jalr 는 Register에 저장된 주소를 기준 으로 이동할 수 있다. 16. 그런데 우리가 전에 j, jr을 사용했는데? 맞다. 우리는 지금까지: j target jr ra 를 많이 사용했다. 그런데 PDF에서는 이들이 Pseudoinstruction 이라고 설명한다. 17. Pseudoinstruction이란? Pseudoinstruction은 프로그래머가 편하게 사용할 수 있도록 만든 가짜 명령어 이다. 여기서 가짜라는 뜻은 CPU가 직접 가지고 있는 실제 명령어가 아니다. 라는 의미다. Assembler가 실제 RISC-V 명령어로 바꿔준다. 18. j는 실제로 무엇일까? 우리가 썼던: j label 은 실제로: jal zero, label 이다. 왜 zero 일까? jal 은 원래 복귀 주소를 destination register에 저장한다. 하지만 j 는 그냥 이동만 하면 되므로 복귀 주소가 필요 없다. RISC-V의 zero 는 항상 0이고, 여기에 값을 써도 버려진다. 따라서: jal zero, label 을 하면 복귀 주소는 버리고 label로 이동만 한다. 19. jr ra는 실제로? jr ra 는 실제로: jalr zero, ra, 0 이다. 의미: ra가 가리키는 주소로 이동 하면서 복귀 주소는 zero 에 써서 버린다. 20. ret도 Pseudoinstruction 함수에서 돌아갈 때: ret 이라고 쓸 수도 있다. 이것도 실제로는: jalr zero, ra, 0 이다. 즉: ret = jr ra = jalr zero, ra, 0 라고 이해할 수 있다. 21. 다른 Pseudoinstruction PDF에는 여러 예가 나온다. 예: mv t5, s3 는 실제로: addi t5, s3, 0 이다. 즉 값을 복사하는 것처럼 보이지만, 실제로는 0을 더한다. not s7, t2 는 실제로: xori s7, t2, -1 이다. nop 은 실제로: addi zero, zero, 0 이다. 아무 변화도 일어나지 않으므로 No Operation 이라는 뜻이다. 22. Label Assembly에서: loop: done: simple: 같은 것을 많이 봤다. 이것이 Label이다. Label은 이동할 위치에 사람이 알아보기 쉬운 이름을 붙인 것 이다. 예: jal simple 이라고 적으면 Assembler는 실제로 simple 의 위치를 계산한다. 23. Label은 실제 Machine Code에 이름으로 저장되지 않는다 CPU는 simple loop done 같은 이름을 이해하지 못한다. Assembler가 Label의 실제 위치를 계산해서 Immediate Offset 으로 바꾼다. 즉: jal simple 은 최종적으로 현재 위치에서 simple까지 얼마나 떨어져 있는가 라는 숫자로 바뀐다. 24. PDF의 Label 예제 예를 들어: 0x00000300 jal simple ... 0x0000051C simple: 이라면 거리: 0x51C - 0x300 = 0x21C 이다. 따라서 Label은 실제 명령어에서는 0x21C만큼 이동 하는 형태로 바뀐다. 25. Long Jump 문제가 하나 있다. jal 이나 jalr 에서 사용할 수 있는 Immediate의 크기는 제한되어 있다. PDF에서는: jal → 20-bit immediate jalr → 12-bit immediate 라고 설명한다. 즉 너무 멀리 있는 곳으로 한 번에 이동할 수 없을 수도 있다. 26. auipc 멀리 이동하기 위해 PDF에서는 auipc 명령어를 소개한다. auipc 는 현재 PC에 큰 Immediate 값을 더할 수 있도록 사용된다. 이를 jalr 와 함께 사용하면 더 먼 위치까지 Jump할 수 있다. 27. call Pseudoinstruction PDF에서는: call 이라는 Pseudoinstruction도 소개한다. 큰 범위로 함수 호출을 할 때 내부적으로: auipc jalr 조합으로 바뀔 수 있다. 즉: call 함수 를 쓰면 프로그래머가 직접 복잡한 Jump 주소 계산을 할 필요가 없다. Assembler가 실제 명령어로 바꿔준다. 이번 편 핵심 정리 Non-Leaf Function 다른 함수를 호출하는 함수 다른 jal 이 ra 를 덮어쓸 수 있으므로: ra를 Stack에 저장 해야 할 수 있다. Recursive Function 자기 자신을 호출하는 함수 호출마다 필요한: 인자 ra 기타 Register 를 Stack에 저장한다. jal Jump + 복귀 주소 저장 jalr Register 주소를 기준으로 Jump Pseudoinstruction 실제 CPU 명령어는 아니지만 프로그래머가 편하게 사용하는 명령어 Assembler가 실제 RISC-V 명령어로 바꾼다. 예: j label → jal zero, label jr ra → jalr zero, ra, 0 ret → jalr zero, ra, 0 mv t5, s3 → addi t5, s3, 0 Label Jump할 위치에 붙이는 이름 Assembler가 실제 거리인 Immediate Offset 으로 변환한다. 가장 중요하게 기억할 것 이번 편을 한 줄로 연결하면: 함수를 여러 번 호출하면 Register와 ra가 덮어써질 수 있다. ↓ 그래서 Stack에 저장한다. 그리고: j, jr, ret 같은 명령어는 실제로는 jal / jalr을 편하게 표현한 Pseudoinstruction이다. 라고 기억하면 된다. 다음 편 다음부터 드디어 PDF의 Machine Language 파트로 들어간다. 다음 편에서는: R-Type I-Type S-Type B-Type U-Type J-Type opcode rs1 rs2 rd funct3 funct7 를 공부한다. 즉 지금까지 사람이 읽었던 add s0, s1, s2 가 실제 CPU 안에서는 0과 1의 32비트 명령어 로 어떻게 바뀌는지를 배우게 된다.