[컴퓨터구조] RISC-V 명령어의 타입, Procedure Calling

명령어의 타입을 알아보기 전 숫자표기법을 먼저 알아보자!

숫자 표기법

Unsigned Binary Integers

• 범위 : 0 부터 2^n-1

Signed Binary Integers

• 반을 쪼개서 음수, 양수로 사용한다. 음수가 하나 더 많음 -> 0 때문에
• 63번 비트는 부호비트이다.
  • 1은 음수
  • 0은 양수
• 특정한 숫자들
  • 0 : 0000 0000 … 0000
  • -1 : 1111 1111 … 1111
  • Most-negative : 1000 0000 …. 0000
  • Most-positive : 0111 1111 … 1111

보수를 취한 다음 1을 더해서 Negative를 만들어준다.

Sign Extension (부호 확장)

더 많은 비트를 사용해서 숫자의 값은 유지하면서 표현하는 방법이다.

• Sign bit을 가지고 왼쪽으로 복사한다.
• RISC-V instruction set에서는
  • lb : loaded byte
  • lbu : unsigned

---

Instruction Format

Instruction은 machine code라고 불리는 이진수로 encoded 된다.

모든 명령어는 디자인 규칙에 의하여 32비트로 제한되며, 이 32비트 안에 모든 것을 표현해야 한다.

이 때 명령어를 여러 타입으로 나누어서 표현하게 만들었는데, 이를 Instruction Format 이라고 표현한다.

• R-Type(Register Type)
• I-Type(Immediate Type)
• S-Type(Store Type)

세 타입 모두 인코딩 방식이 다르다

R-Type

산술과 논리 연산에 사용된다.
제일 기본적인 포맷
register의 R -> register를 다 쓰는 포맷

32비트 안에 모든 것을 넣었으며, opcode, func3, func7을 통하여 어떤 명령을 수행할 지 결정한다.

• rd : destination register, 값을 넣고자 하는 레지스터
• rs1 : 첫 번째 source가 되는 register
• rs2 : 두 번째 source가 되는 register

register에 해당하는 bit가 모두 5비트인 것은 레지스터의 개수가 32개이기 때문이다.

따라서 opcode, func3, func7을 통하여 어떤 명령을 할 지 결정하고, 해당 명령을 rs1, rs2에 적용하여 rd에 저장한다.

example

• func7 : 0
• func3 : 0
• opcode : 0110011
• rd : 01001
• rs1 : 10100
• rs2 : 10101

I-Type

load 혹은 constant 연산을 위해 존재하는 instruction format
즉각적인 산술 및 load 지침을 위해 사용한다.
immediate 비트는 총 12개이며, 여기에 상수 또는 offset이 들어가게 된다.

a = b + 100 // immediate에 100 저장, b는 rs1, a는 rd
load R1, 100(R2) // R2가 base address, 100이 offset, rs1에 저장
// offset은 immediate에 저장

• immediate : 일정한 피연산자 또는 기본 주소에 오프셋 추가

설계 원리3 : 좋은 디자인에는 적당한 절충이 필요하다

비록 다른 format이여도 32비트는 유지해야하며, format을 가능한 한 비슷하게 만들어야 한다.
그렇기 때문에 R-Type의 rs2와 func7이 합쳐져서 I-type의 immediate가 된 것이다.

근데 imme은 최대 12비트이기 때문에 32비트의 숫자를 처음부터 덧셈을 하려면 어떻게 해야할까?

이를 위한 명령어는 추후에 나온다.

S-Type

Store를 위한 instruction format

rd가 없다. store는 레지스터에 있는 메모리를 저장소로 보내는 것이여서 그 부분을 immediate로 써서 메모리를 확보했다.

• rs1 : 저장공간의 base address
• rs2 : 저장할 값이 있는 register

rs2에 있는 값을 rs1 + imm[11:5] + imm[4:0]에 넣는다.

Logical Operation

위와 같은 산술 연산, data transfer operation을 제외하고 논리 연산을 위한 명령어가 존재한다.

• not 은 1과 xor 연산을 함으로써 구현한다.

단어의 비트 그룹을 추출하고 삽입하는데 유용하다.

여기서 immediate는 shift를 위해 사용한다. 32 bit가 word이기 때문에 63비트 이상의 시프트는 필요 없기 때문에 남은 비트를 func 비트로 재활용한다.

• sra, srai 연산은 오른쪽으로 shift함과 동시에 Sign Extension이 일어난다.
• AND Operation
  • 마스크 비트로 많이 사용하며 선택한 비트만 남기고 싶을 경우 사용한다.
    

    

• OR Operation
  • 어떤 특정 부분에 있는 bit을 포함시킬 때
    

    

• XOR Operation
  • 두 bit가 같으면 0 다르면 1
    

    

---

Decision Instruction

결정을 위한 명령어로 while, if, else가 있다.

bne, beq

• bne (branch not equal)
• beq (branch equal)

if(조건문)에서 조건문이 True 라면 if문 안의 명령어를 실행하고, 조건문이 False라면 else문 안의 명령어를 실행하거나, if문을 탈출한다.

탈출 한다는 것은 다음 명령어의 위치를 바꿈을 의미한다.

C코드와 RISC-V 컴파일 방법

만약 i와 j가 같다면 바로 아래의 명령어를 실행할 것이고, 아니라면 else문의 명령어를 실행한다.

분기를 위한 명령어를 Conditional Branches 라고 한다. -> 조건에 따라 branch를 옮긴다는 뜻

• bne : 명령어 안에 포함되어 있는 두 개의 레지스터가 같지 않다면 특정 Label로 이동한다.
• beq : 명령어 안에 포함되어 있는 두 개의 레지스터가 같다면 특정 Label로 이동한다.

bne x22, x23, Else // x22 레지스터의 값과 x23레지스터의 값이 같지 않다면 Else로 이동

beq x0, x0 은 뭘까? -> Uncolditional branch 명령어로 항상 branch를 움직이게 하는 명령어

만약 Unconditional branch를 사용하지 않는다면, Else로 이동하지 않음에도 불구하고, 순차적으로 명령어를 실행하기 때문에 결국 Else 명령어를 실행하게 된다.

while

while (save[i] == k) i += 1;
// i는 x22, k는 x24, save의 시작주소는 x25

/*
Loop: slli x10, x22, 3 // left shift 3번이니까 *8 (실제 메모리 주소와 매핑)
add x10, x10, x25 // 배열의 base address의 offset을 더하기 위함
ld x9, 0(x10) // base address 역할을 한다. x10에 있는 주소만 가져올 수 있다.
bne x9, x24, Exit // 같지 않으면 exit
addi x22, x22, 1
beq x0, x0, Loop // Unconditional Branch
*/

blt(u), bge(u)

• blt : branch less than
• bge : branch greater than

뒤에 u가 붙는다면 레지스터 값을 unsigned로 간주한 후 명령어를 실행한다.

• blt : 두 개의 레지스터 값을 비교한 후 rs1이 rs2보다 작다면 branch 변경
• bge : 두 개의 레지스터 값을 비교한 후 rs1이 rs2보다 크거나 같다면 branch 변경

해당 레지스터 값이 있을 때

blt rs1, rs2, L // rs2가 크기 때문에 L로 이동한다. 
bltu rs1, rs2, L // rs1이 더 크기 때문에 L로 이동하지 않는다. 

case/switch statment는 명령어가 바로바로 이동할 수 있게 Label 을 정하고 Table을 만들어 놓는다.

SB-Type

PC : 현재 명령어의 주소를 지정하고 있는 레지스터, branch를 위한 base register, 현재 PC의 위치에 따라서 움직일 branch의 주소를 지정한다 (PC-relative addressing)

SB : Short Branch

imm의 점프해야 할 값들은 흩어져있다. 프로그램을 수행하다가 conditional jump를 하면 프로그램 카운트가 있는걸 기준으로 근처로 이동할 가능성이 많다.

• Target address = PC + immdiate * 2 (2칸 shift) -> 4바이트 단위로 이동하기 때문에
• 실제로 SB-Type이 움직일 수 있는 범위는 현재 명령어를 기준으로 +- 2^10

branch instruction은 모두 SB-Type 이다.

SB-Type은 짝수로만 이동이 가능하다. 해당 type의 format은 아래와 같은데

• imm이 1부터 12이다. -> 실제로 명령어의 imm의 0번째는 0으로 취급하겠다.

그렇기 때문에 사실상 imm을 13개를 쓰는 것과 마찬가지고 명령어의 범위는 -4096 ~ 4094이다.

왜 그럴까?

32bit architecture 의 경우 word가 4byte이다. 따라서 하나의 명령어가 저장되어 있는 공간은 4Byte이므로 4의 배수가 아닌 숫자로 명령어 위치를 바꾸는 것은 불가능하다.

4의 배수는 항상 비트의 끝자리가 00으로 끝나므로, 끝의 두 자리는 따로 명시하지 않아도 된다. 따라서 imm은 2~13까지만 명시하는게 정상이지만, RISC-V 개발 당시 2byte 명령어도 지원할 계획이 있어서 끝에 0 하나만 없앴다.

그렇기 때문에 기존의 1~12비트에 해당하는 -2^11 ~ 2^11 - 1에서 2을 곱하여 위의 범위가 나온다.

beq를 구현할 때 사용한다.

---

Procedure Calling

코드를 작성하다 보면, 다른 함수를 호출해야 하는 경우가 빈번하다. 우리는 argument를 function call을 하며, 해당 함수의 작업이 끝나면, return을 통해서 값을 돌려받는다.

프로그램은 procedure을 위해서 반드시 아래의 여섯가지 실행을 따라야 한다.

1. procedure이 볼 수 있는 곳에 파라미터를 넣는다.
2. procedure에 control 권한을 부여한다.
3. procedure을 위한 저장공간을 확보한다.
4. 해당된 작업을 수행한다.
5. program을 calling한 함수가 볼 수 있는 곳에 result 값을 넣는다.
6. control 권한을 나를 호출한 함수에게 반납한다.

이 때, g, h, a를 메모리에 넣는다면 어떻게 될까?
함수가 호출될 때마다 메모리를 참조해야 하므로, overhead가 커질 것이다.

따라서 해당 값들은 register에 넣어야 한다.

procedure calling을 위한 9개의 레지스터가 있다.]

Procedure Calling Register

Procedure를 부르는 함수를 caller라고 하고 부름에 응답하는 함수를 Callee라고 한다.
(통상적으로는 main 함수가 Caller, 다른 function이 Callee)

procedure calling을 위해서는 우선

파라미터가 들어갈 공간과

리턴을 위한 공간,

다시 권한을 반납할 때 돌아가야 할 장소를 저장하는 공간 이 세가지가 필요하다.

 

x10 ~ x17	파라미터 혹은 return value를 위한 8개의 파라미터 레지스터를 저장
통상적으로 x10과 x11은 return value를 위해 사용된다.
x1	origin으로 돌아가기 위한 하나의 return 주소를 저장

 

 

Caller는 8개의 파라미터를 x10 ~ x17에 저장하고 Callee는 자신이 수행한 작업에 대한 return value를 x10 혹은 x11에 저장한 후, x1에 저장되어 있는 주소로 권한을 반납한다.

만약 Callee에게 넘겨줘야 할 파라미터가 8개를 넘어가게 되면?

register spilling을 통해 메모리에 초과된 파라미터를 저장한다. -> 오버헤드를 피하기 위해서는 파라미터를 8개 이하로만 주는 것이 좋다.

• register spilling
  • spilling : 자주 사용하지 않는 변수를 메모리에 넣는 것
  • 레지스터 스필링에 이상적인 자료구조는 스택이다. 스택은 나중에 들어간 것이 먼저 나오는 자료구조로써 스택에는 다음 프로시저가 spill할 레지스터를 저장할 장소나 레지스터의 옛날 값이 저장된 장소를 표시하기 위해 최근에 할당된 주소를 가리키는 포인터가 필요하기 때문에
  • RISC-V 에서 스택 포인터는 레지스터 x2 이며 sp로도 불린다. => 해당 포인터는 레지스터 하나가 스택에 저장되거나 스택에서 복구될 때마다 4(32비트) 또는 8(64비트)씩 조정된다.
  • 스택은 높은 주소에서 낮은 주소로 성장하기 때문에 push할 때는 값을 빼주고 pop할 때는 더해줘야 한다.

int main() {
  r = procedure(int g, int h);
}

이런 식으로 함수를 호출하게 되면 레지스터 x10과 x11에 파라미터를 넣고 x1에는 현재 명령어의 위치 + 4 (32비트 기준) 을 집어 넣는다. 함수가 종료되고 main에서 다음 명령어를 실행해야 하기 때문이다.

하지만 Caller와 Callee의 명령어가 순차적으로 있는 게 아닐텐데 어떻게 명령어 위치를 변경할까?

새로운 명령어가 필요하다.

---

jal

jal(jump and link)은 Caller가 Callee에게 권한을 넘길 때 사용하는 명령어
지정된 주소로 분기하는 동시에, 복귀한 뒤 실행할 다음 명령어의 주소를 목적지 레지스터 rd 에 저장하기 때문에 jal이라고 부른다.

link 는 프로시저 종료 후 올바른 주소로 돌아올 수 있도록 호출한 곳과 프로시저 사이에 링크를 형성한다는 뜻이다.

jal x1, ProcedureLable

Procedure Address로 점프하는 동시에 x1에는 return address를 입력한다.

jalr

jalr(jump and link register) 는 프로시저에서 복귀하기 위해 사용되는 명령어
Callee가 Caller에게 권한을 반납할 때 사용하는 명령어이다.

jalr x0 0(x1)

x1에는 base address 가 들어있고 0은 offset, x0은 destination register이다. x1에는 이미 목적지가 저장되어 있기 때문에 offset에 0을 넣고 x0은 hardwired register이기 때문에 값을 넣어도 무시된다.

==> 따라서 해당 명령어는 x1에 저장되어 있는 값으로 점프한다.

---

Leaf Procedure Example

가장 말단에 있는 프로시저 (다른 프로시저를 호출하지 않는 프로시저)

long long int leaf_example (long long int g, long long int h,long long int i, long long int j) {
    long long int f;
    f = (g + h) --(i + j);
    return f;
}

/*
 Arguments g, …, j in x10, …, x13 (func argument reg) 파라미터 저장
 f in x20 (saved reg)
 temporaries x5, x6 스택 마련
 */

• 각각 프로시저는 자기 자신의 스택을 마련한다.
• 위 예시에서 사용하는 register는 총 3개이고 따라서 3개의 register를 쓰기 위해 저장공간을 확보한다.
• x5, x6, x20 등 Callee가 값을 바꾸는 레지스터는 스택에 그 값을 보존해준다. 상위함수에서 쓰고 있었을 수도 있기 때문이다.
• 이후에는 return 하기 전에 값을 복구함으로써 caller의 local value를 보장한다.
• 결과는 x10에 저장된다.

• RISC-V 에서 함수호출 명령어 동작 방법

• (a) : 함수 호출 전 스택의 상태
• (b) : 함수 호출 동안 스택의 상태
• (c) : 함수호출이 끝난 후 스택의 상태

Register Saving Convention

상위 함수의 값을 보존하기 위해 stack에 값을 저장했지만 실제로 상위함수가 썼는지 안썼는지도 모르는 register를 저장하는 것은 비효율적이다.
따라서 RISC-V에서는 이러한 비효율을 방지하기 위하여 register spilling을 두 개의 그룹으로 나누어서 관리(저장) 한다.

• Caller saved registers
  • x5x7, x28x31 : callee 호출 이후에 보장이 되지 않는 temporary register들
  • caller가 call을 하기 전에 미리 저장해야 한다.
  • 해당 레지스터들은 procedure call 이후에 변경되어 있을 수 있다.
  • procedure call 이후에 복구한다.
• Callee saved registers
  • x8x9, x18x27 : Procedure call 이후에 필수로 보장되어야하는 register들
  • 만약 사용했다면 Callee는 반드시 저장하고 복구해야 한다.
  • callee는 caller에게 return 하기 전에 해당 값들을 복구해야 한다.
  • 해당 register들은 procedure call 이후에 보장되어야 한다.

caller saved registers 호출 이후에 변경되어도 상관이 없는 register들이므로, 저장을 하는 것은 caller의 선택이다. 하지만 callee saved registers는 호출 이후에도 절대 변경되면 안 되는 register들이기 때문에 반드시 저장되어야 한다.

caller 입장에서는 callee saved registers가 매우 중요한 register

Non-Leaf Procedure

또 다른 funtion을 부를 수 있다. Nested call이라고도 불린다.
Callee가 Caller가 된다.

예를 들어서 main 프로그램이 파라미터를 3을 가지고 프로시저 A를 호출했다.

이 때 레지스터 x10에 3을 넣은 후 jal x1, A 명령어를 실행 할 것이다.

프로시저 A에서는 다시 인수 7을 가지고 jal x1, B 명령어로 프로시저 B를 호출했다.

아직 A가 다 끝나지 않은 상태에서 x10에 새로운 값을 넣어주었기 때문에 x10에서는 기존에 사용하던 3이 7로 덮어씌워지게 된다. (충돌 발생)

마찬가지로 레지스터 x1에는 돌아갈 main 프로그램의 주소가 아닌 A프로시저의 주소가 담겨있으므로 B가 리턴된 이후 A에서 main 프로그램으로 돌아갈 방법이 사라진다.

이러한 문제를 해결하기 위해서는 값이 보존되어야 할 모든 레지스터를 스택에 넣는 것이다.

그렇기 때문에 caller는 x10~x17을 저장해야 하고 callee는 x1을 저장해야 한다.

Callee saved registers는 Preserved가 되고 Caller saved register 는 Not Preserved가 된다.

코드를 예시로 보면

long long int fact (long long int n) {
    if (n > 1) return 1;
    else return n * fact(n - 1)
}

/*
    Argument n in x10
    result in x10
*/

---

Local Data on the Stack

메모리 안의 stack에는 saved register, local variable 뿐만 아니라 크기가 큰 array, structure등이 들어가 있다.
이러한 stack은 procedure frame 혹은 activation record 라고 한다.

이때 fp(frame pointer, x8)은 frame의 첫 번째 word를 가리키게 된다.

왜 필요할까??

• sp는 함수 내에 변수를 위하여 공간을 만든다.
• 그러고 나서 함수가 끝난다면 sp는 값을 더하여 해당 procedure과 관련된 정보를 지운다.
• 이 때, sp는 어디서부터 해당 procedure 이 시작되었는지 모르기 때문에, fp가 해당 procedure frame의 첫 번째 word에 있는 것이다.
• 따라서 sp = fp를 하면 procedure frame은 모두 pop이 되어 버린다.

하지만 여기서도 문제점이 발생한다.

• procedure call이 연속적으로 발생할 때 fp 또한 overriding 된다는 것
• 연속적으로 발생한다면, 또 다른 procedure frame이 생긴다.
• 따라서 fp는 a의 first word를 가리키고 있다.
• 그렇게 되면 이전의 procedure frame의 fp는?

그렇기 때문에 fp 또한 procedure frame에 저장한다.

참고

https://ttl-blog.tistory.com/983
https://hi-guten-tag.tistory.com/249