SPARC Assembler Data Structure - Array

어떤 언어에서나 가장 많이 사용되는 기본적인 자료구조는 배열이다.
이 배열이 어셈블러에서는 어떻게 구현되어 있으며,
우리가 C로 사용하는 배열이 어떻게 되어있는지 알아보도록 하자.

Stack 구조를 확실하게 알고 있다면 배열도 정말 간단하게 구현할 수 있다.

Array는 Register를 이용하지 않고 Memory를 이용한다. (당연히 Register는 개수가 제한적이니까.)
Memory연산과 관련해서는 ld와 st명령을 사용하는데 기본적으로 다음과 같다.

Opcode	세부내용
ldsb	signed byte
ldub	unsigned byte
ldsh	signed half word
lduh	unsigned half word
ld	word
ldd	double word
stb	low byte
sth	low 2 byte
st	word
std	double word

메모리 관련 연산 사용시 주의하여야 할 점은
첫째로, 해당 메모리 부분이 align이 8byte 단위로 되어 있어야 한다.
          (제일 긴 단위가 double로 8 byte기 때문에 8로 정렬한다.)
둘째로, st(저장)한 부분과 ld(로드)한 부분이 크기가 서로 일치하여야 한다. (그래야 원하는 값을 얻을 수 있다.)
셋째로, st(저장)할때는 Unsigned/Signed 구분할 필요가 없지만 ld(로드)할 때는 원하는 값으로 구분해줘야한다.
          (표현가능한 수의 범위가 확실히 다르기 때문이다.)
넷째로, 값을 넣을때 상수 값은 넣지 못한다. Register를 이용해야 한다.
           ex) st 7, [%fp-4]    ← 이런건 에러 유발   
                mov 7, %o0
                st %o0, [%fp-4] ← 이런식으로 바꿔주어야 함.
다섯째로, []대가로 내부에서는 레지스터 + 레지스터, 레지스터+ 상수만 가능하다.

참고로 []란 마치 포인터처럼 사용된다. []내에 주소값이 들어가면 그 주소가 가리키는 곳의 값을 가져온다.
마치 포인터의 *를 생각하면 개념을 쉽게 잡을 수 있을 것이다.
그리고 주소값으로 무언가 이용하기 위해서는 %sp와 %fp를 이용한 상수 또는 레지스터와의 연산으로 상대적인 위치를 확인할 수 있다.
%sp 및 %fp를 이용하면 전 단계의 스택영역에 접근이 가능한데, 그방법은 전에 언급하였으므로 생략하도록 한다.

다음의 간단한 코드는 간단한 배열을 순환해가며 저장하고,
다시 순환하면서 출력하는 코드이다.
이때 저장하는 부분과 순환하는 부분을 다른 방식으로 구성해보았다.
전자(저장하는 부분)는 sll을 사용한 부분이고 후자(출력하는 부분)은 add를 이용하여 Index를 구성하였다.

배열이란 같은 자료형의 연속된 집합이라고 정의할 수 있다.
그렇기 때문에 배열에 접근하기 위해서는 같은 값의 크기를 언제나 곱해가면 연산하게 된다.

   먼저 기본적으로는 왼쪽이 가장 이해하기 쉬운 Memory Map이라고 할 수 있겠다.
   좌측에 보면 가운데 ary 크기가 선언되어 있고 위 아래로 다른 타입의 자료가 선언되어 있다. 다른건 필요 없고 가운데만 눈여겨 보자.
   보면 처음에 fp-28을 하는데, 이는 배열에 사용될 전체 메모리 공간을 확보한 것이고, 그후로 인덱스가 증가함에 따라 fp-28의 상태에서 4씩 +를 해나감으로써 접근하는 모습을 볼 수 있다.(그림에서 4를 +하는 이유는 자료형이 4byte이기 때문임)
   즉 처음에 fp를 이용하여 배열 전체 크기를 잡아준후 그상태에서 Stack의 위에서 아래 방향으로 내려오면서 각 값에 접근하는 것이다.
   [왼쪽 표에서 아래는 높은 주소, 위가 낮은 주소, 아래에서 위로 Stack이 쌓여지는 방향이다.]

   이를 식으로 보면 다음과 같다.
Ary[0] :   %fp-배열의 크기(byte)+0*4
Ary[1] :   %fp-배열의 크기(byte)+1*4
Ary[2] :   %fp-배열의 크기(byte)+2*4
.
.
이러한 과정으로 증가한다. 즉 배열의 인덱스에서 해당 자료의 크기를 곱한 값을 더해 나감으로써 위에서 아래로 접근한다.
(메모리를 접근할때 보통 fp를 기준으로 아래에서 위방향으로 접근한다. 배열은 반대)

C언어나 기타 언어에서 배열의 첫번째 인덱스가 0인 사실도 여기에서 기인한다고 한다. 어셈블리에서 fp로 인한 연산때문에 처음에는 항상 처음에는 0을 곱한 값을 더해주어야 한다. 이러한 배열의 인덱스 접근상의 편의로 배열의 인덱스는 항상 0부터 시작한다고 한다.

어셈블리어에서 배열을 설정할때 또 고려해야할 점이 바로 이부분이다.
곱셈을 수행하게 되면 add를 여러번 수행하기 때문에 쓸데없이 수행시간을 많이 잡아먹게 된다.
이부분은 최소화 하기 위해서 .mul 함수를 사용하지 않고, sll이나 add를 이용한 접근 방법이 있다.
그 두가지를 기준으로 아래 코드를 작성하여 보았다.

[작성환경 : solaris sparc machine  작성툴 : Vi editor   컴파일러 : gcc]
.section ".data" str: .asciz "%d\n" .section ".text" .global printf .global main main: save %sp, -136, %sp add %fp, -40, %l3 ! Array Size 4 byte x 10 mov 0, %l1 ! Count Loop and Array Value for1: sll %l1, 2, %l4 ! %l4 is Array Index 0,4,8,12...36 st %l1, [%l3+%l4] inc %l1 cmp %l1, 10 bl for1 nop clr %l0 ! %l0 is Array Index clr %l1 ! %l1 is Count Loop for2: set str, %o0 call printf ld [%l3+%l0], %o1 inc %l1 cmp %l1, 10 bl for2 add %l0, 4, %l0 ret restore

10~16이 배열을 저장할 메모리를 for 문으로 돌면서 Index값을 저장하는 코드이다.
20~27또한 배열을 순환하면서 값을 출력하는 코드인데,

이 둘의 큰 차이점이 있다.
저장하는 부분은 sll을 사용하였고, 출력하는 부분은 add를 사용하여 인덱스를 조작하였다.
직관적으로는 add를 이용하는 법이 간단하기는 하나,
효율적이고 이론적으로 하기 위해서는 sll을 이용하는 것이 타당하다.
특히 2차원 배열 이상으로 넘어갈 경우 sll방향으로 하여야 올바른 코딩이 가능해진다.
sll을 이용한 이유는

%fp-40+Index*4  (메모리상의 각 배열 주소)

에서 Multiple을 효과적으로 수행하기 위함이다.
(곱하기를 하려면 사실 .mul을 call해줘야하는데 함수를 호출하여 Stack이 쌓이기 때문에 아주 비효율적이다.)
자료형이 4byte이기 때문에 sll %l1, 2, %l4를 이용하였다.
sll을 두칸하면 곱하기 4라는 사실은 기본으로 알고 있어야 한다. (한칸은 곱하기 2다.)

add를 이용할때는 byte크기마다 증가해가며 접근하기 때문에 처음 접근하기에는 매우 편리하다.
단, 이차원으로 넘어가면 작성하기 까다로워진다.
위 코드에서는 Index와 Loop변수를 두개 주었지만, 사실 하나로도 가능하다. 그럴 경우 cmp할때 주소 크기로 비교를 해주어야 한다.

참고할 점 :
배열이 할당된 메모리에 접근하기 위해서 sll을 사용하기 위해서는 크기를 2의 승수로 잡아야 한다.
그래야 효율적으로 배열을 사용할 수 있다.
즉 Index를 2의 승수로 한뒤 shift 연산을 사용하는 것이 효율적이다.
빠른 주소연산을 위해 배열 크기를 2의 멱승으로 잡는 것이 중요하다.

<결과값을 출력하면 저장된 Index번호가 차례대로 출력된다.>

※ 잡 담
    언제나 느끼는거지만 머리로 떠올리는것과 결과가 다르면 정말 짜증이 날 수 밖에 없다.
    메모리의 경우 fp, sp를 이용하여 주소접근이 많아 정확한 계산을 하면 정확한 답이 나온다.
    즉 생각과 다른 값이 나오는 경우는 결국, 본인의 미스 및 이해의 부족일 수 밖에 없다 -.,-;
    필자도 사실 fp, sp제어에서 많은 착오가 있었다 ㅠ.ㅜ;