[SPARC] 27. 일차원 배열

지난 글에서는 스택 프레임을 사용하는 예제를 정리하였다.

이번 글에서는 스택 메모리에 일차원 배열을 선언하는 방법을 정리하고자 한다.

---

스택에서 일차원 배열 선언하기

함수 안에서 아래와 같이 변수를 선언한다고 해보자.

int a;
int array[5];
int b;

 

이 경우, 실제 스택에는 지역변수들이 어떤 순서로 들어갈까?

우선 선언한 순서대로, 높은 주소인 %fp부터 채워지므로 a > array > b 순서로 채워진다.

 

그렇다면 array 내부에서는 어떤 순서로 채워질까?

array 내부에서는 array[0]~array[4] 가 주소가 '증가하는' 순서대로 할당이 되어야 한다.

그런데 스택에서는 점점 주소가 감소하는 방향으로 공간이 넓어지므로 아래와 같은 순서로 할당받게 된다.

 

[높은 주소]                                                                        [낮은 주소]

a > array[4] > array[3] > array[2] > array[1] > array[0] > b

 

array의 첫번째 원소 주소는 %fp - 4 - 20 이다.(배열 이전에 a가 먼저 4바이트를 가지고, 배열은 4바이트 공간 5개이므로)

따라서 %fp - 24 로 0번째 원소에 접근하고, %fp - 20 으로 1번째 원소,... 순으로 접근할 수 있다.

 

즉, 위 예제에서 배열의 i번째 원소의 메모리 주소는 %fp - 24 + 4*i  = 시작주소 + 4*i 이다.

 

배열의 시작 주소와 관련된 값은 -24 이므로 이를 상수화 하여 아래와 같이 어셈블리 코드로 작성할 수도 있다.

ARRAY_START = -24

sll %l0, 2, %o0   ! %l0 = i / bit shift to left twice ==> i << 2 = i * 4
add %fp, %o0, %o0 ! %o0 += %fp  /  i * 4 + %fp
ld  [%o0 + ARRAY_START], %o0 ! i*4 + %fp + (-24) == i-th array element address

 

---

일차원 배열 순회 예제

이제 배열의 원소 값을 계산하는 방법을 알았으니, 이를 이용하여 배열을 순회해보자.

배열을 순회하는 예제로, 아래와 같은 C코드를 어셈블리로 컴파일해보자.

int main() {
    int nums[20] = {17, 11, -161, -32, -893, 566, 25, 88, 67, -90};
    int n = 10;
    int min;
    register int i; // i 는 자주 읽고 쓰므로, 레지스터에 저장해두자.
    
    min = nums[0]; // 최소값은 어차피 저 값들 중 하나니까 0번째 원소를 미리 넣어두기
    
    for (i = 1; i < n; i++)
    	if (nums[i] < min)
        	min = nums[i]
}

 

int 형 변수 20개가 있는 배열을 선언해두고, 10개만 채운다음, 이 배열을 순회하면서 최소값을 찾는 코드이다.

---

스택 사이즈 계산

우선 '메인' 이라는 함수를 선언해야 하므로, 스택 프레임 사이즈를 계산해줘야 한다.

지역 변수는 int 공간 20개가 모여있는 배열이 먼저 선언되었고, 이후에 int 형 변수가 2개 선언되었다.

따라서 지역변수의 크기는 4*20 + 4*2 = 88 이다.

 

(강의록에서는 - (92 + 88) & -8 = -184 로 스택 프레임 사이즈를 계산했다.

그런데 함수 호출이 없으니까 92가 아니라 64에 더해야 하지 않을까? 앞 스택프레임 계산 예제에서는 실제로 64에 더하기도 했고.. => printf 함수 때문에 92로 했는데, 64가 맞다고 함.)

 

원문 코드에서 함수 호출이 없으므로, - (64 + 88) & -8 = -152 byte 만큼의 스택프레임을 할당하면 된다.

---

어셈블리 코드

어셈블리 코드는 아래와 같이 작성할 수 있다.

 

스택 안에서 선언한 배열을 초기화해준다.

(어쩔 수 없는 노가다 작업이다.)

 

min, n 변수를 초기화 한다.

 

반복문을 돌면서 최소값을 찾는다.

배열의 원소 사이즈가 4byte라서 주소값이 4 단위로 증가한다.

4를 곱하는 작업을 비트시프트 연산을 통해 수행했다.

 

강의록에서는 나와 다른 반복문을 짰다.

코드 아래쪽에 반복 조건을 확인하는 코드를 작성하고, 반복조건이 만족중이라면 코드 중간에 반복문 블럭으로 넘긴다.

코드가 실행되면서 자연스럽게 아래쪽의 반복 조건을 확인하는 코드로 넘어온다. (do - while 같은 느낌)

나는 while (1) 을 돌다가, 반복 조건에 안맞으면 break 해서 나가는 방식으로 코드를 작성하였다.

 

 

실행 결과 최소값이 잘 출력된다.

---

예제 개선하기 (1) - 자주 읽는 변수를 레지스터로

근데 min, n 변수는 반복문을 돌면서 매번 읽는다. (min 변수는 경우에 따라 쓰기도 한다.)

매번 읽기 위해 메모리에서 레지스터로  불러오는 작업은 비효율적이다.

따라서 min, n 변수도 레지스터로 선언해보자.

 

이제 스택에서 8바이트의 지역변수 공간이 필요없어졌으니, 할당할 스택 사이즈도 줄어든다.

(152 - 8 = 144)

 

 

아주 간단하게 코드가 바뀌었다.

이제 l1, l2 변수가 다른 의미로 사용되므로, 반복문 내부에서 임시 변수로 사용했던 레지스터들을 수정해준다.

 

이제 실행해보면

 

동일하게 실행결과가 나오는 것을 확인할 수 있다.

---

예제 개선하기 (2) - 배열 주소값 계산 최적화

배열 주소값을 계산할 때 매번 %fp + 시작주소 + 인덱스*4 를 계산하는 것은 효율적이지 않다.

인덱스가 증가함에따라 상대적으로 이전에 방문했던 배열주소에 4만 더해주면 된다.

 

이렇게 반복문을 돌기 전에 미리 0번 인덱스의 주소를 계산해서 넣어두고

 

이렇게 주소를 매번 4씩 증가시키면서 돌면 된다.

 

실행결과도 잘 나온다.

---

예제 개선하기 (3) - 인덱스 변수 없애기

이제 상대주소를 이용해서 배열을 순회하고 최소값을 찾도록 예제를 개선하였다.

그런데 이미 계산된 상대주소가 4씩 증가하다보니, 더 이상 인덱스 i 가 배열 주소 계산에 사용되지 않는다.

그저 반복 횟수만을 조절하는 기능으로 사용될 뿐이다.

이제 불필요한 변수 i 를 없애보자.

 

만약 i 가 없다면, 반복의 종료를 어떻게 체크해야할까?

우리는 배열의 10번째 인덱스에 있는 값을 체크할 때까지만 반복을 할 예정이다.

따라서 마지막 주소인 10번째 인덱스의 주소를 계산해서 현재 주소가 마지막 주소보다 작은 동안 반복하면 된다.

 

이를 C언어로 표현하면 아래와 같이 표현할 수 있다.

int main() {
    int nums[20] = {17, 11, -161, -32, -893, 566, 25, 88, 67, -90};
    int n = 10;
    int min;
    register int address;
    register int end_address;
    
    end_address = (int)nums + n * sizeof(int);
    
    min = nums[0]; // 최소값은 어차피 저 값들 중 하나니까 0번째 원소를 미리 넣어두기
    
    for (
    	address = (int)nums + sizeof(int);
        address < end_address;
        address += sizeof(int)
    )
    	if (nums[i] < min)
        	min = nums[i];
}

 

이제 이 코드를 어셈블리로 바꿔보자.

 

기존에 i 값을 사용하던 변수는 사용하지 않고, 대신 end_address 를 계산해서 l2 에 넣어준다.

 

반복문은 조건 체크하는 부분만 바꿔주면 된다.

 

실행결과가 동일하게 나오는 것을 알 수 있다.

---

정적 메모리에 배열 선언하기

이번엔 정적 메모리공간, 즉, data 섹션에 배열을 선언해보자.

int main() {
    static int nums[20] = {17, 11, -161, -32, -893, 566, 25, 88, 67, -90};
    int n = 10;
    int min;
    register int address;
    register int end_address;
    
    end_address = (int)nums + n * sizeof(int);
    
    min = nums[0]; // 최소값은 어차피 저 값들 중 하나니까 0번째 원소를 미리 넣어두기
    
    for (
    	address = (int)nums + sizeof(int);
        address < end_address;
        address += sizeof(int)
    )
    	if (nums[i] < min)
        	min = nums[i];
}

 

즉, 이렇게 선언하는 것과 같다.

어셈블리 코드에서는 배열을 초기화하는 부분과 배열에 접근하는 방법을 바꾸어주면 된다.

 

더 이상 배열이 스택에 선언되지 않으므로, 스택 사이즈는 80만큼 추가로 감소한다.

그래서 그냥 64바이트를 잡아주면 된다.

(그런데 나는 printf 함수를 호출할 예정이라 92바이트로 잡았다.)

 

우선 배열 초기화는 다음과 같이 할 수 있다.

 

스택에 선언하면, 일일히 st 명령어로 초기화를 해줘야 했는데,

그 노가다가 코드 한줄로 끝나니 너무 편안하다.

.data
nums: .word 17, 11, -161, -32, -893
      .word 566, 25, 88, 67, -90
str:	.asciz "min value is %d\n"
.align 8

.text
n = -4
.global main
			main: save %sp, -96, %sp
				set nums, %l2

				! int min = nums[0]
				ld [%l2], %l1
			
				! int n = 10
				mov 10, %l0
				st  %l0, [%fp + n]
			
				! from now on %l0 is i
				mov 1, %l0
				ld  [%fp + n], %o0 !% o0 = n = 10 
			loop:
				cmp %l0, %o0
				bge break
				nop
				add %l2, 4, %l2
				ld  [%l2], %l3
				cmp %l3, %l1
				bge end
				nop
				mov %l3, %l1
			end:
				inc %l0
				ba loop
				nop
			
			break:
				set str, %o0
				mov %l1, %o1
				call printf
				nop
			
				ret
				restore

 

이상하게 오류가 나와서 그냥 예제 1번 코드를 적당히 이용하여 작성하였다..

 

실행결과 같은 값이 잘 나오는 것을 알 수 있었다.

---

지금까지 일차원 배열에 대해 정리하였다.

다음 글에서는 다차원 배열에 대해 정리할 예정이다.

 

다차원 배열을 정리하고, 구조체를 정리하면 메모리 파트는 끝난다.

빨리 서브루틴을 정리하고 싶다 ㅎㅎ