Passing Parameters to Subroutines via Registers

Subroutine

subroutine은 function 혹은 procedure라고도 부른다.
single-entry, single-exit를 가지고 있고 exit하고 나면 자신을 call했던 caller에게 return된다.

subroutine이 call되면 link register(LR)은 다음 instruction의 memory address를 hold해 subroutine의 실행이 종료되면 return 할 수 있도록 한다.

Link Register (LR)

link register(LR, R14)은 return address를 hold한다.
이미 알고있는 얘기... 앞에서 주구장창 언급됨

Calling and Exiting a Subroutine

subroutine은 다음과 같은 방법으로 실행된다.

BL	label		; LR = addr of next instruction
				; PC = label
...
BX	LR			; PC = LR

BL을 통해 next instruction의 address를 LR에 넣고 subroutine의 실행이 끝나면 LR 위치로 돌아오는 것이다.

label은 subroutine의 이름이고 컴파일러는 label을 memory address로 translate한다. subroutine의 실행이 끝나면 LR이 return address를 hold하고 있다.

ARM Calling Convention

ARM의 calling convention을 보면 r0~r3는 함수의 argument를 담는 데에 사용되고 그 중 r0는 함수의 return value를 담는다.
만약 함수의 argument가 4개보다 많을 경우 그 때부터는 stack을 사용한다.

r4~r11(r9제외)은 general purpose register로 사용된다.
함수 내의 local variable을 담아 연산을 하는 데에 사용된다.

r12~r15까지는 special purpose register로 각각 특별한 목적을 가지고 사용된다.

Passing Arguments via Registers

각 argument와 return value의 크기에 따라 어떤 register에 담기는지를 나타내는 그림이다.

r0부터 필요한 만큼 사용한다. r0에는 항상 LSB 32 bit가 담긴다.

Example

SSQ()에서 첫 번째 argument인 x는 r0에, 두 번째 argument인 y는 r1에 담겼고 return value인 z가 r0에 담긴 것을 확인할 수 있다.

실제로는 이런식으로 실행되는데, 실제로는 PC의 마지막 bit는 항상 1이 되어야 한다. ARM Cortex-M에서는 ARM mode가 지원되지 않기 때문이다 (여기 참고).
현재 실행되고 있는 것은 Thumb mode이다. ADD R2, R3인 것만 봐도 알 수 있다. 만약 ARM mode였다면 ADD R2, R2, R3이었을 것이다.

하지만 PC에 들어가는 주소값의 LSB가 항상 1이어야 한다고 해서 실제 instruction이 위치한 memory의 주소가 홀수인 것은 아니다 (여기 참고).

input argument가 어디에 담겼는지, return value가 어디에 담겼는지에 집중하면 될듯.

Reality (PC)

위의 예제에서 PC는 2 혹은 4씩 증가했다.
하지만 원래 PC는 항상4 씩 증가한다.

매 시점마다 instruction memory에서는 4 bytes씩 fetch한다.
이 4 bytes는 두 개의 16-bit instruction일 수도 있고 하나의 32-bit instruction일 수도 있다.

fetch하는 입장에서는 next instruction이 16-bit인지 32-bit인지 알 수 없기 때문에 fetcher는 무조건 일단 4-byte단위로 fetch한다.
그리고 그 이후에 instruction의 상위 5-bit을 통해 그 instruction이 16-bit인지 32-bit인지 확인한다.

Preserve Environment via Stack

Stack Growth Convention

stack은 last-in-first-out(LIFO) 형태의 data structure를 가지고 있다.
stack에서는 가장 최근에 add된 item(top of the stack)만 access할 수 있다.

push, pop의 두 가지 operation이 있다.

Ascending, Descending

• Descending stack은 stack이 아래로 자란다. 정확히 말하면 memory address가 작아지는 쪽으로 stack이 자란다.

• Ascending stack은 stack이 위로 자란다. memory address가 커지는 쪽으로 stack이 자라고 stack top이 stack의 top address를 가리킨다.

Full, Empty

• Full stack은 stack이 꽉 찬 것으로, SP가 stack에서 가장 나중에 push된 item을 가리킨다. SP는 다음 stack의 top address를 가리키는데 stack이 꽉 찼기 때문에 더 이상 가리킬 다음 위치가 없는 것이다.

• Empty stack은 SP가 stack의 다음 free space를 가리키는 것이다.
  여기서 'empty'의 의미는 stack이 완전히 비었다의 의미가 아니라 빈 공간이 남았다의, full의 반대의 의미로 쓰이는 것 같다.

Cortex-M Stack

Cortex-M의 stack에서 stack pointer(SP)는 R13이다.
또한 Cortex-M은 full descending stack을 사용한다. 즉 stack은 무조건 아래로, memory address가 작아지는 쪽으로 자란다.

Full Descending Stack

stack이 memory address가 작아지는 쪽으로 자란다.

아래로 자라는 stack이기 때문에 push는 아래와 같은 조건을 만족한다.

PUSH	{register_list}

is equivalent to

STMDB	SP!, {register_list}

SP가 stack의 top address를 가리키고 있기 때문에 push하기 전에 먼저 SP의 값을 4 byte만큼 감소시켜야 한다.
따라서 이를 STMDB와 SP!로 동일하게 표현할 수 있다.

또한 pop 또한 아래의 조건을 만족한다.

POP		{register_list}

is equivalent to

LDMIA	SP!, {register_list}

SP가 stack의 top address를 가리키고 있기 때문에 pop은 현재 SP가 가리키고 있던 item부터 진행된다. 따라서 IA를 사용한다.

push와 pop에서 STMDB와 LDMIA를 사용한다는 것은 register_list의 순서를 고려하지 않는다는 뜻이다 (참조).
즉, 레지스터의 번호가 작은 것이 low address와 대응된다.

Stack

PUSH

PUSH	{Rd}	; SP = SP - 4
				; (*SP) = Rd

SP를 먼저 4 감소시킨 후 해당 위치에 Rd를 저장한다.

만약 Rd에 들어가는 레지스터가 여러 개일 경우

PUSH	{r6,r7,r8}		; PUSH	{r8}
						; PUSH	{r7}
is equivalent to		; PUSH	{r6}

PUSH	{r8,r7,r6}

📌 register의 order은 관계가 없다. 무조건 registesr의 number가 작은 것이 lowest memory address에 저장된다 (나중에 push됨).

위의 예제에서는 r6이 제일 작은 번호이기 때문에 가장 작은 memory address에 저장하기 위해 마지막에 push하였다.
stack이 아래로 자라기 때문에 나중에 push될 수록 작은 memory address를 가진다.

POP

POP		{Rd}	; Rd = (*SP)
				; SP = SP + 4

현재 SP의 위치에 있는 item부터 pop하면 되기 때문에 먼저 pop을 한 뒤 SP를 4 증가시킨다.

만약 Rd에 들어가는 레지스터가 여러 개일 경우

POP		{r6,r7,r8}		; POP	{r6}
						; POP	{r7}
is equivalent to		; POP	{r8}

POP		{r8,r7,r6}

📌 register의 order은 관계가 없다. 무조건 작은 memory address에 있던 item이 작은 number의 register에 저장된다 (먼저 pop됨).

위의 예제에서는 r6이 제일 작은 번호이기 때문에 가장 작은 memory address에 있는 item을 r6에 넣어주어야 한다.
stack이 아래로 자라기 때문에 먼저 pop할 수록 작은 memory address의 item이다.

Preserve Runtime Environment via Stack

subroutine안에 들어갔을 때, caller에서 사용하던 레지스터의 값이 바뀌면 원래 caller의 실행에 문제가 생길 수 있다.

따라서 이를 방지하기 위해 stack을 사용해 register의 값을 보존한다.

caller가 subroutine을 실행하기 전 자신이 save해주는 register를 caller-saved register라고 부른다.
callee가 자신을 실행하기 전에 save해두는 regster를 callee-saved register라고 한다.

위의 예시에서 r4는 callee인 foo()가 값을 보존했으므로 callee-saved register이다.
위의 예시를 보면 LR을 보존해 subroutine으로부터 안전하게 return하는 것을 볼 수 있다.

stack에 push했던 LR을 PC에 pop해 restore하는 것과 LR을 다시 LR에 pop한 다음 BX LR을 실행하는 것은 동일하다고 볼 수 있다 (return하는 과정).
하지만 BX LR을 사용하기 위해서는 subroutine에 들어올 때 BL을 통해 LR값을 update했다는 전제가 있어야 한다 (당연한 소리).
만약 호출된 subroutine이 그 내부에서 또 다른 subroutine을 호출하지 않는다면 굳이 subroutine을 실행하기 전 LR을 push할 필요가 없다. 그저 return될 때 자신의 LR에 담겨있는 값으로 BX LR을 하면 된다.

하지만 subroutine 내부에서 또 다른 subroutine을 호출할 것이라면 반드시 LR을 push해서 save 해두어야 한다. 다른 subroutine으로 branch하면서 LR값이 그 subroutine이 return할 address로 바뀔 것이기 때문이다.
이 때 LR을 push해두지 않으면 최초의 함수로 return할 수 없게 된다.

Initializing the Stack Pointer (SP)

stack을 사용하기 전에 software는 stack space를 정의하고 stack pointer(SP)를 initialize해야한다.

보통 startup.s라는 어셈플리 파일이 이 과정을 수행한다.

Cortex-M 에서는 SP를 vector table의 첫번째 4-byte로 자동으로 initialize해주는 mechanism을 제공한다.

Stack and Recursive Functions

Recursive Functions

recursive function은 task를 잘게 쪼개서 자기 자신을 반복적으로 호출해 task를 처리한다.

아래는 대표적인 예제인 Factorial을 recursive function으로 해결하는 과정을 보여준다.

Recursive Factorial in Assembly

1. nested call 이전에 stack에 push LR (& working registers)를 한다.
2. nested call로부터 return하고 나면 pop LR (& working regsiters)를 한다.

다음은 factorial을 실행하는 어셈블리 코드이다.
r4는 첫 번째 general purpose register이다. r0~r3까지는 argument를 담는 곳이기 때문에 local variable을 담는 용도로 사용할 수 없다 (위의 calling convention 참고).

ret label의 pop {r4,pc}에서 맨 처음에 stack에 pop 해뒀던 lr을 pc에 restore하면서 BX LR을 명시적으로 실행하지 않고도 return할 수 있다.
lr은 r14이므로 r4의 번호가 더 작기 때문에 PUSH {r4,lr}에서 lr이 먼저 push된다. 번호가 작은 것이 lower memory address에 위치해야하기 때문이다.
factorial에 3을 넣어서 시작했기 때문에 BNE문에 걸려서 factorial()을 다시 실행하게 된다.아까 까지의 과정을 반복적으로 수행하면 위와 같은 형태가 된다.
그러면 이제 BNE문에 걸리지 않는 상태가 되어 ret label의 instruction을 실행할 수 있다. 그럼 아래와 같은 형태가 된다.

pop 역시 나열된 register의 순서는 중요하지 않다. r15인 pc가 r4보다 번호가 크기 때문에 lower memory address에 저장되어 있던 값이 r4로 load된다.
즉, 먼저 pop한 것을 r4에 넣고 그 다음 pop한 것을 PC에 넣는다.

그럼 pc가 0x08000148로 바뀌면서 MUL을 실행하고, r0의 값이 2*1 = 2로 바뀐다.
그리고 바로 아래의 B ret을 실행하면 다시 아까와 같은 상황이 된다.
그리고 여기서 다시 바뀐 PC로 인해 MUL을 실행하면 원했던 결과인 6을 얻을 수 있다.
그리고 다시 아래의 B ret을 실행하면 ret label로 돌아오는데, 여기서 한 번 더 pop을 하면 가장 처음에 넣었던 lr을 복원하게 된다.
이렇게 되면 factorial 실행이 완료된 것이다.
이리저리 왔다갔다 해서 헷갈릴 수는 있지만 어떤 느낌인지는 알 수 있지..ㅎㅎ