[컴퓨터 구조] 명령어(Instruction)[6] - 프로시저(함수) 지원을 위한 명령어

 

 

 

 

 

 

🧐 프로시저 (procedure)

프로시저나 함수는 이해하기 쉽고, 재사용이 가능하도록 프로그램을 구조화하는 방법 중 하나입니다.

 

프로그램이 프로시저를 실행할 때에는 다음과 같이 여섯 단계를 거쳐야 합니다.

1. 프로시저가 접근할 수 있는 곳에 인수를 넣는다. ( x10 - x17 레지스터 사용 )

2. 프로시저로 제어를 넘긴다. ( jal x1, ProcedureAddress 명령어 사용 )

3. 프로시저가 필요로 하는 메모리 자원을 획득한다. 

4. 필요한 작업을 수행한다.

5. 호출한 프로그램이 접근할 수 있는 장소에 결과값을 넣는다. ( x10 - x17 레지스터 사용 )

6. 프로시저는 프로그램 내의 여러 곳에서 호출될 수 있으므로, 원래 위치로 제어권을 돌려준다. ( jalr x0, 0(x1) )

(참고로 x0은 상수 0이 들어있는 레지스터입니다.)

 

 

 

레지스터는 데이터를 저장하는 가장 빠른 장소이므로, 가능한 많이 사용하는 것이 바람직합니다.

그로므로 RISC-V 소프트웨어는 프로시저를 호출할 때 다음의 레지스터 할당 관례를 따릅니다.

x10 - x17 : 전달할 인수와 결과값을 가지고 있는 인수 레지스터 8개

x1 : 호출한 곳으로 되돌아가기 위한 복귀 주소(return address)를 가지고 있는 레지스터 1개

 

RISC-V 어셈블리 언어는 이렇게 프로시저를 위해 레지스터를 할당할 뿐 아니라, 프로시저를 위한 명령어도 제공합니다.

 

이제부터 이러한 명령어들에 대해 자세히 알아보도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 jal (jump-and-link) 명령어

프로시저 호출을 위해 사용되는 명령어로

지정된 주소로 분기하는 동시에, 복귀한 뒤 실행할 다음 명령어의 주소를 목적지 레지스터 rd 에 저장하기 때문에 jal (jump and link) 명령어라 부릅니다.

 

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

 

다음과 같이 사용합니다.

jal x1, ProcedureLabel

 

위 명령어를 실행하면 복귀한 뒤 실행할 다음 명령어의 주소를 x1 레지스터에 넣어줍니다.

해당 주소를 복귀 주소(return address)라 부릅니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 jalr (jump-and-link-register) 명령어

프로시저에서 복귀하기 위해 사용되는 명령어입니다.

 

다음과 같이 사용합니다.

jalr x0, 0(x1)

위 명령어는 레지스터 x1에 저장되어 있는 주소로 분기하라는 뜻입니다.

 

 

호출 프로그램은 x10 - x17 레지스터에 전달할 인수값을 넣은 후,

jal x1, Procedure 명령을 이용해서 프로시저 Procedure(피호출 프로그램이라 부릅니다)로 분기합니다.

 

 

피호출 프로그램은 계산을 끝낸 후 계산 결과를 같은 인수 레지스터에 넣은 후 

jalr x0, 0(x1) 명령어를 실행하여 복귀합니다.

 

 

내장 프로그램 개념은 현재 수행중인 명령어의 주소를 기억하는 레지스터를 필요로 합니다.

이 레지스터가 바로 PC(program counter)입니다.

 

jal 명령은 프로시저에서 복귀할 때 다음 명령어부터 실행하도록 PC + 4를 목적지 레지스터에 저장합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 많은 레지스터를 사용하는 경우

컴파일러가 프로시저를 번역할 때, 인수 레지스터 8개( x10 - x17 )만으로는 부족한 경우가 있습니다.

 

프로시저 호출이 다른 부분에 영향을 미쳐서는 안되기 때문에,

호출 프로그램에서 사용하는 모든 레지스터는 복귀하기 전에 프로시저 호출 전에 상태로 되돌려 놓아야 합니다.

 

이 상황은 이전 글 에서 설명한 레지스터 스필링이 필요한 경우입니다.

 

레지스터 스필링에 이상적인 자료구조는 스택입니다.

 

스택은 나중에 들어간 것이 먼저 나오는 자료구조로써,

스택에는 다음 프로시저가 spill할 레지스터를 저장할 장소나 레지스터의 옛날 값이 저장된 장소를 표시하기 위해 최근에 할당된 주소를 가리키는 포인터가 필요합니다.

 

RISC-V 에서 스택 포인터는 레지스터 x2이며, sp로도 불립니다.

 

해당 스택 포인터(stack pointer)는 레지스터 하나가 스택에 저장되거나 스택에서 복구될 때마다 8씩(32비트 컴퓨터의 경우 4씩) 조정됩니다.

 

스택은 높은 주소에서 낮은 주소 쪽으로 '성장'합니다.

따라서 스택에 push할 때에는 스택 포인터 값을 감소시켜야 하고,

스택에서 데이터를 꺼내는 경우에는 스택 포인터 값을 증가시켜야 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

⭐️ 예시 1 - 다른 프로시저를 호출하지 않는 C 프로시저의 컴파일

다른 프로시저를 호출하지 않는 프로시저를 말단(leaf) 프로시저라 합니다.

 

다음과 같은 C코드를 살펴보겠습니다.

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

 

위 코드에서 레지스터는 다음과 같이 사용됩니다.

• 인자 g, h, i, j는 x10, x11, x12, x13에 할당됩니다.
• 지역변수 f는 x20 레지스터에 할당됩니다.
  • 피호출자는 x20을 스택에 저장해 주어야 합니다. 
  • 호출자에서 x20을 사용하고 있었을 수도 있기 때문에, 값을 보존시켜 주어야 하기 때문입니다.
• 임시 레지스터로는 x5, x6 를 사용합니다.
  • x5 - x7은 임시 레지스터로써, 피호출자에서 보존해줄 필요가 없습니다.
• 결과는 x10에 저장됩니다.

 

 

어셈블리어는 다음과 같습니다.

addi sp, sp, -8 //스택에 x20을 저장하기 위해 1칸의 공간이 필요하며, 따라서 8바이트의 공간을 늘려줍니다(-8)

sd x20, 0(sp) // 호출자에서 사용한 x20레지스터에 들어있는 값을 스택에 저장합니다. x20은 8바이트이므로 0(sp)에서 8(sp)만큼의 공간을 사용합니다.

add x5, x10, x11 // 임시 레지스터 x5에 g + h 저장
add x6, x12, x13 // 임시 레지스터 x6에 i + j 저장

sub x20, x5, x6 // f = x5 - x6

addi x10, x20, 0 // 결과는 x10에 담기므로 x20에 0을 더한 값을 x10에 저장합니다.

ld x20, 0(sp) // 호출자에서 x20레지스터에 할당하였던 값을 복구합니다.

addi sp, sp, 8 // 늘렸던 스택의 공간을 줄입니다.

jalr x0, 0(x1) // 복귀 주소로 복귀합니다.

 

 

 

아래 그림은 프로시저 호출 전후와, 프로시저 실행 중이 스택 상태를 나타낸 그림입니다.

 

 

 

이전 글 에서 살펴본 바와 같이 RISC-V 소프트웨어는 레지스터 주소에 대한 Convention을 다음과 같이 정하였습니다.

x5 - x7, x28 - x31 :  프로시저 호출 시, 피호출 프로그램이 값을 보존해주지 않는 레지스터

x8 - x9, x18 - x27 : 프로시저 호출 전과 후의 값이 같게 유지되어야 하는 저장 레지스터
(피호출 프로그램이 이 레지스터를 사용하려면 원래 값을 저장했다가 원상 복구해야 합니다.)

이러한 간단한 관례를 정함으로써 레지스터 스필링을 많이 줄일 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

⭐️ 예시 2 - 다른 프로시저를 호출하는 C 프로시저의 컴파일

말단 프로시저가 아닌 프로시저를 호출하는 경우, 생각해 주어야 할 것들이 많아집니다.

 

 

예를 들어 main 프로그램이 파라미터(인수)값 3을 가지고 프로시저 A를 호출했다고 가정하겠습니다.

 

이때 레지스터 x10(인수 레지스터)에 3을 넣은 후 jal x1, A 명령을 실행할 것입니다.

 

프로시저 A에서는 다시 인수 7을 레지스터 x10에 넣고, jal x1, B를 호출했다고 가정하겠습니다.

 

아직 A가 다 끝나지 않은 상태에서 x10에 새로운 값을 넣어주었기에,

x10에서 기존에 사용하던 3의 값이 사라지고 7로 덮어씌워집니다. (충돌 발생)

 

마찬가지로 레지스터 x1에는 돌아갈 main 프로그램의 주소가 아닌 A프로시저의 주소가 담겨있으므로,

B가 리턴된 이후 A에서 main 프로그램으로 돌아갈 방법이 사라집니다.

 

 

 

이러한 문제를 해결하기 위한 한 가지 방법은 저장 레지스터에서 했던 것처럼

값이 보존되어야 할 모든 레지스터를 스택에 넣는 것입니다.

 

호출 프로그램은 인수 레지스터(x10 - x17)와, 임시 레지스터 (x5 - x7과 x28 - x31) 중 

프로시저 호출 이후에도 계속 사용해야 하는 것은 모두 스택에 넣습니다.

피호출 프로그램은 복귀 주소 레지스터 x1과, 저장 레지스터 (x8 - x9와 x18 - x27) 중

피호출 프로그램이 사용하는 레지스터를 모두 저장합니다.

 

스택 포인터는 스택에 저장되는 레지스터 개수에 맞추어 조정됩니다.

 

복귀할 때에는 메모리에서 값을 꺼내 레지스터를 원상 복구하고 이에 맞추어 스택 포인터를 다시 조정합니다.

 

 

 

 

 

예시 C 코드는 다음과 같습니다.

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

 

 

레지스터 할당은 다음과 같습니다

• 인자 n은 x10
• 결과는 x10에 저장됩니다.

번역된 어셈블리어는 다음과 같습니다.

addi sp, sp, -16  // 복귀 주소(x1)와 인수 n (x10)를 저장하기 위한 공간 2칸 할당
sd x1, 8(sp)      // 복귀 주소를 스택에 저장
sd x10, 0(sp)     // 인수 n을 저장

// if(n < 1)은  if(n - 1 < 0) 과 동일하며, 0의 값은 x0에 저장되어 있으므로 이와 같이 바꾸는 것이 더 빠릅니다.

addi x5, x10, -1  // x5 = n - 1 을 저장
bge x5, x0, L1    // n-1(x5) >= 0(x0)인 경우 L1으로 이동 
addi x10, x0, 1   // 결과는 1 (n-1 < 0인 경우이다.) 

// ld x10, 0(sp)
// ld x1, 8(sp)
// 위 두 코드는 필요 없는데, 이유는 더이상의 procedure 호출 없이 return 시켜주기 때문에 값을 저장하지 않아도 됩니다.
// 즉 Leaf Procedure와 동일합니다.

addi sp, sp, 16   // 할당된 스택 반환
jalr x0, 0(x1)    //return


L1:
addi x10, x10, -1 // n = n - 1
jal x1, fact      // 재귀 호출
addi x6, x10, 0  // 결과를 x6으로 이동
ld x10, 0(sp)     // 호출자에서 사용해야 하는 인수값(n) 복구
ld x1, 8(sp)      // 호출자에서 사용해야 하는 복귀 주소(x1) 복구
addi sp, sp, 16   // 스택 공간 반납
mul x10, x10, x6  // result is n * fact(n-1)
jalr x0, 0(x1)    // return

 

 

 

 

 

 

 

 

 

🧐 전역 포인터 (global pointer)

C 변수는 기억 장치의 한 장소에 해당합니다.

 

여기에 기억된 내용을 어떻게 해석하는가는 데이터형(Type)과 저장 유형(storage class)에 따라 달라집니다.

데이터형의 예로는 정수형, 문자형 등이 있습니다.

 

C에는 자동(automatic)과 정적(static) 두가지 저장 유형이 있습니다.

 

자동 변수는 프로시저 내에서만 정의되는 것으로 프로시저가 종료되면 없어집니다.

 

정적 변수는 프로시저로 들어간 후나 프로시저에서 빠져나온 후에도 계속 존재합니다.

 

모든 프로시저의 외부에서 선언된 C 변수는 정적 변수로 간주되며, static이라는 키워드를 사용해서 선언된 변수도 마찬가지입니다.

 

그 나머지는 모두 자동 변수입니다.

 

정적 데이터를 쉽게 접근할 수 있도록 어떤 RISC-V 컴파일러는 x3을 전역 포인터(global pointer, gp)로 사용합니다.

 

 

 

 

아래 표는 프로시저 호출 전후의 값 보존 관계를 보여줍니다.

보존되는 것	보존되지 않는 것
Saved registers :  x8 - x9,  x18 - x27	Temporary registers :  x5 - x7,  x28 - x31
Stack pointer register : x2 (sp)	Argument/result. registers :  x10 - x17
Frame pointer register : x8 (fp)
Return address registers : x1 (ra)
Stack above the Stack pointer(스택 포인터 위에 존재하는 스택)	Stack below the Stack pointer(스택 포인터 아래에 존재하는 스택)

( 전역 포인터를 사용하는 경우에는 전역 포인터도 보존되지만, 이는 다음에 설명하겠습니다 :D )

 

 

 

 

 

 

 

 

 

 

🧐 스택 공간의 할당

레지스터에 들어가지 못할 만큼 큰 배열이나 구조체 같은 지역 변수를 저장하는 데에도 스택이 사용되기 때문에 문제가 복잡해집니다.

 

프로시저의 저장(saved) 레지스터와 지역 변수를 가지고 있는 가지고 있는 스택 영역을 프로시저 프레임(procedure frame) 또는 스택 프레임(stack frame) 또는 액티베이션 레코드(activation record)라고 부릅니다.

 

아래 그림은 프로시저 호출 전, 중, 후의 스택 상태를 보여줍니다.

 

 

 

어떤 RISC-V 컴파일러는 프레임 포인터(fp), 즉 레지스터 x8이 프로시저 프레임의 첫 번째 워드를 가리키도록 합니다.

 

스택 포인터의 값이 프로시저 내에서 바뀔 수도 있으므로,

메모리 내 지역 변수에 대한 변위(offset)는 변수가 프로시저 어느 부분에서 사용되느냐에 따라 달라질 수 있습니다.

 

이런 이유로 프로시저를 이해하는 것이 더 어려워집니다.

 

 

반면에 프레임 포인터는 변하지 않는 베이스 레지스터 역할을 하므로, 이를 이용하면 지역변수 참조가 간단해집니다.

 

별도의 프레임 포인터를 사용하지 않더라도, 액티베이션 레코드는 항상 스택에 존재합니다.