[컴퓨터 구조] chapter2-2 정리(컴퓨터 언어 : 명령어)

오늘은 chapter2 뒷부분에 대해서 설명하려고 합니다.

 

앞 단원에서, 명령어의 표현과 C코드를 MIPS로 변환하는 방법과 2의 보수법을 사용한 음수의 표현, MIPS의 각종 명령어에 대해서 알아보았습니다. 뒷부분에서는 프로시저의 기본적인 개념과 호출 순서, 레지스터에 관련한 내용들에 대해 알아보고 프로시저(논리프 프로시저, 리프 프로시저)에 대해서 설명드리려고 합니다. 이에 더해 프로그램 실행에 필요한 메모리 레이아웃의 구성은 어떻게 되는지와, 명령어에 따른 주소지정방식에 대해 정리하려고 합니다. 

 

2.8 하드웨어의 프로시저 지원

2.9 문자와 문자열

2.10 32비트 수치와 주소를 위한 MIPS의 주소 지정 방식

 

프로시저(procedure)란 ?

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

- 프로그래머가 한 번에 한 부분씩 집중할 수 있게 함

- 인수(parameters)는 프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스 역할 : 값을 보내고 결과를 받아옴

- 프로시저는 소프트웨어에서 추상화를 구현하는 방법 중 하나

 

프로시저 호출 순서 (1~2(caller), 3~6(callee)

1. 인수(parameters)를 레지스터(Register)로 넘김

2. 프로시저로 제어를 넘김

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

4. 필요한 작업 수행

5. 호출한 프로그램을 위해서 레지스터에 결과를 저장

6. 원래 위치로 제어를 돌려준다.

 

레지스터 활용

1. $a0 - $a3 : 인수 레지스터(reg’s 4-7)(메서드가 실행될 때 해당 메서드에 값을 전달해 주기 위함)

2. $v0, $v1 : 결과 레지스터( reg’s 2 and 3)

3. $t0 - $t9 : 보존하지 않는 변수 레지스터(호출된 프로시저에 의해서 덮어 씌워질 수 있음)

4. $s0 - $s7 : 보존돼야 하는 변수 레지스터(호출된 프로시저는 원래 값을 따로 저장하여 복원해야 함)

5. $gp : 정적 데이터를 위한 글로벌 포인터(reg 28)

6. $sp : 스택 포인터(reg 29)

7. $fp : 프레임 포인터(reg 30)

8. $ra : 복귀 주소(reg 31)

 

프로시저 호출 명령어 

jal(jump-and-link)

여기에서 link는 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 link를 형성한다는 의미

jal ProcedureAddress

1. 지정된 Address로 점프(Jump)
2. 다음 명령어의 주소(PC  + 4)를 $ra 레지스터에 저장

프로시저 복귀 명령어

jr(jump register)

 

jr $ra

1. 피호출프로그램(callee)으로부터 호출프로그램(caller)으로 복귀(제어를 넘김)
2. 피호출 프로그램은 계산을 끝낸 후 계산 결과를 $v0-$v1에 넣은 후 jr 명령어를 실행하여 복귀
3. $ra를 프로그램 카운터 레지스터(PC)로 복사 
4. 내장 프로그램은 현재 실행 중인 명령어의 주소를 기억하는 레지스터를 필요로 합니다. 이를 PC라고 부름

리프 프로시저(Leaf Procedure) vs 논-리프 프로시저(Non-Leaf Procedure)

 

리프 프로시저(Leaf Procedure)

리프 프로시저란 "다른 프로시저를 호출하지 않는 프로시저"입니다.

 

C code

 

 int leaf(int g, h, i, j)
 {
    int f;
    f = (g + h) - (i - j)
    return f;
 }
 Arguments g, h, i, j in $a0, $a1, $a2, $a3
 f in $s0
 result in $v0

 

인자값은 각각 $a0 ~ $a3에 저장되어 있고, 계산 결괏값은 $s0에 저장되어 있는데 복귀하기 전에 계산 결과를 $v0(결과 레지스터)에 저장한 후 복귀해야 합니다.

다음 C코드를 MIPS 어셈블리어로 변환한 결과를 한 줄씩 정리해보려고 합니다. 

 

MIPS code

 

leaf_example :

addi $sp, $sp, -4

sw $s0, 0($sp)

// addi 연산을 통해 스택포인터($sp)를 4만큼 감소시키고 stack 메모리 공간을 확보, $s0값을 스택의 위치에 저장

add $t0, $a0, $a1

add $t1 $a2, $a3

sub $s0, $t0, $t1

// 연산 진행 f = (g + h) - (i + j), MIPS 구조상 산술 명령어는 레지스터를 3개를 사용해야 하므로 C코드보다 코드가 길어짐

add $v0, $s0, $zero

// 결과값 $s0를 $v0(결과 레지스터)에 저장

lw $s0, 0($sp)

addi $sp, $sp, 4

//  $s0의 값을 불러온 후, 스택포인터($sp)의 값을 4를 증가시켜 stack 메모리 공간 해제

jr $ra 

// 호출 프로그램으로 복귀

 

논-리프 프로시저(Non-Leaf Procedures)

다른 프로시저를 호출하는 프로시저

중첩된 호출을 위해서, 호출하는 프로시저/프로그램이 보존이 필요한 레지스터를 스택 자료구조에 저장하는 것이 필요

 

중첩된 프로시저 예시

• 주 프로그램이 인수값 3을 가지고 프로시저 A를 호출(jal A, $ra의 A의 복귀주소 저장, $a0에 인수값 3이 저장)
• 프로시저 A가 인수값 7을 가지고 프로시저 B를 호출(jal B, $ra에 B의 복귀주소 저장, $a0에 인수 값 저장)
• 다음과 같은 상황에서 충돌이 일어나서 A로 복귀하지 못함($ra의 복귀주소에 B의 복귀주소가 겹치고, $a0에 인수값도 다른 값이 저장되기 때문)
• 이를 해결하기 위해 스택 포인터($sp) 사용(보존되어야 할 모든 레지스터를 메모리에 스필링 할 수 있음)

호출 프로그램(caller)은 인수 레지스터($a0 ~ $a3), 임시 레지스터($t0 ~ $t9) 중 호출 후에도 필요한 레지스터 푸시

피호출 프로그램(callee)은 복귀주소 레지스터($ra), 저장 레지스터($s0 ~ $s7) 푸시

여기에서 스택 포인터($sp)는 레지스터를 가리리키 위한 포인터 역할을 하는 레지스터

푸시할 때 $sp값 감소, 풀 할 때 증가

 

C code

int fact (int n)

{

     if(n<1) return f;

     else return n * fact(n-1);

}

n in $a0, result in $v0

 

MIPS code

fact : 

     addi  $sp, $sp, 8

     sw     $ra, 4($sp)

     sw     $a0, 0($sp)

     // addi를 연산을 통해 8만큼의 공간 확보, 재귀적으로 함수를 수행하려면 $ra,  $a0가 덮어 쓰이면 안 되기 때문

     // 해당 스택에 $ra, $a0값 저장

     slti     $t0, $a0, 1

     beq   $t0, $zero, L1

     // n<1이면 분기가 일어나지 않고 아래에 있는 addi 연산 수행, 그렇지 않으면 L1으로 분기

     addi  $v0, $zero, 1

     addi  $sp, $sp, 8

     jr        $ra

L1 : addi $a0, $a0, -1

       jal    fact

       // $a0값을 1만큼 감소시키고 fact 함수 호출

       lw    $a0, 0($sp)

       lw    $ra,  4($sp)

      addi $sp, $sp, 8

      mul  $v0, $a0, $v0

       jr     $ra

      // 함수가 리턴되어 돌아왔으므로 현재 함수의 stack에서 $a0, $ra를 load 하여 이전 함수에서 리턴 받았던 $v0와 곱하는 연산을 수행 후 다시 $ra로 복귀

 

문자열 복사 프로시저

 

문자열 y를 x로 복사하는 프로시저

C code

void strcpy (char x[], char y[])

{

      int i;

      i = 0;

      while((x[i]!=y[i])!='\0') i+=1;

}

// Address of x, y in $a0, $a1

// i in $s0

 

MIPS code

strcpy : 

     addi $sp, $sp, -4

     sw    $s0, 0($sp)

     add  $s0, $zero, $zero

// 스택포인터 값 조정 후 $s0값을 $sp에 저장, $s0에 0을 넣는다.(i=0 초기화)

L1 : add $t1, $s0, $a1

       lbu  $t2, 0($t1)

// y[i]에 대해 주소 계산(y의 시작 주소와 i를 더함), 바이트를 부호 없는 0으로 확장하여 $t2에 넣는다.($t2 = y[i])

// sb : 레지스터 값을 메모리에 저장하는 명령어

       add $t3, $s0, $a0

         sb   $t2, 0($t3)

//x[i]에 대해 주소 계산 후 $t2에 있는 값을 x[i]의 주소 값에 있는 메모리에 저장 (x[i] = y[i]) 

       beq  $t2, $zero, L2

// y[i] = 0 이면 L2로 분기

       addi $s0, $s0, 1

          j      L1

// 그렇지 않으면 1 증가 후 L1으로 분기

L2 : lw    $s0, 0($sp)

      addi  $sp, $sp, 4

        jr     $ra

// y[i]=0이면, $s0값을 로드하고 스택 포인터 증가 후 호출 프로그램으로 복귀 

 

 

메모리 레이아웃 

• 프로그램의 실행을 위해 운영체제(OS)가 프로그램의 정보를 메모리에 로드
• CPU가 코드를 처리하기 위해, 메모리가 명령어와 데이터들을 저장해야 함
• 프로그램 실행을 위해 메모리 공간인 코드, 데이터, 스택, 힙을 할당
• 이러한 주소 공간은 가상메모리=논리적 메모리라고 부름

1. 스택 영역

• 피호출프로그램에 의해서 할당되는 지역변수 할당
• 프로시저 호출 시, 레지스터($ra, $s, $a)와 지역변수를 스택 구조로 쌓음
• 프로시저 프레임(저장된 레지스터와 지역변수를 가지고 있는 스택 영역)
• 프로그램이 자동으로 사용하는 임시 메모리 영역
  • 호출 함수 수행을 마치고 복귀할 주소 및 데이터를 임시로 저장하는 공간 -> 함수 호출이 완료되면 사라짐
• 푸시(push) -> 데이터 저장, 팝(pop) -> 데이터 추출 ---> LIFO 구조
• 메모리가 높은 주소에서 낮은 주소 방향으로 할당
• 재귀함수를 반복해서 호출되거나 함수가 지역변수를 메모리를 초과할 정도로 많이 가지고 있으면 스택 오버플로우 발생
• 프로시저 호출 중에 $sp의 값이 변할 수 있기에 변수 참조 시에 값이 변하지 않는 프레임 포인터($fp)를 사용하는 것이 좋음

2. 힙 영역

• 프로그래머가 직접 공간을 할당 및 해제하는 메모리 공간
• 동적 할당을 위한 공간
• malloc, new를 통해 메모리 할당 -> free, delete를 통해 메모리 해제, 이러한 과정을 통해 메모리를 효율적으로 사용할 수 있게 됨
• 메모리가 낮은 주소에서 높은 주소로 할당 
• 힙 오버플로우도 발생 가능

3. 텍스트 영역

• 실행할 프로그램의 코드가 저장되는 영역
• 사용자가 작성한 프로그램 함수들의 코드가 CPU가 읽을 수 있는 기계어 형태로 변환되어 저장됨
• CPU가 code 영역에 저장된 명령을 하나씩 가져가서 처리, Read-Only로 되어 있음

4. 데이터 영역

• 전역 변수 또는 정적 변수를 위한 영역
• 주소값만 가지고 있으면 모두 찾아갈 수 있고, 덮어쓸 수 있으므로 수정도 가능
• 프로그램 시작과 함께 할당되어 프로그램이 종료되면 소멸

부호 확장 명령어 

lb, lbu, sb (32비트 확장)

lb rt, offset(rs) load시 부호확장

lbu rt, offset(rs) load시 부호 없는 확장

sb rt, offset(rs) 

lh, lhu, sh (16비트 확장)

 

32비트 상수 

프로그램에서 상수는 대체로 크기가 작지만, 32비트 수치를 레지스터에 넣을 필요가 있는 경우가 있습니다.

그럴 경우에는 lui와 ori를 사용합니다.

 

lui rt, constant

레지스터 rt의 상위 16bit에 상수값을 load, 하위 16비트 0으로 채움

ori rs, rt, constant

상위 16비트는 0으로 채우고 하위 16비트를 상수로 채운 후 rt와 or 연산

 

32비트를 상수를 만들 때 andi와 ori 차이

andi를 적용하는 경우에는 MSB를 복사하는 부호확장 후에 덧셈을 진행하기에 1이 복사될 수 있지만, 

반면 ori는 0을 상위 16비트에 채운 후 연산 진행

 

 

분기와 점프명령에서의 주소 지정

 

PC-상대적 주소 지정 (PC+4)+(Branch offset), (beq, bne 명령어 실행 시 사용)

• 대부분의 분기 대상은 가까이 있는 명령어로 분기(조건문 분기는 주로 순환문이나 if문에서 사용)
• PC를 기준으로 앞, 뒤 2^15 워드(2^17 바이트만큼 분기 가능)
• 현재 수행되고 있는 명령어에 다음 명령어의 주소를 구함(PC+4)
• 주소의 default가 워드 단위이므로 주소 끝에 2비트를 0으로 채움(Word-> Byte)
• 부호 확장(Sign extension) 진행 후 덧셈 연산을 통해 구해진 Branch Target Address를 PC에 넣음 

의사 직접 주소 지정 (j, jal 명령어 실행 시 적용) (2^26 word = 2^28 바이트 = 256MB 내에서 주소 지정)

• PC에서 상위 4비트는 불변
• PC의 상위 4비트를 Branch Address에 넣음, 주소값은 26 -> 28비트가 됩니다.
• Branch address(32비트)를 PC에 복사하고 메모리에 적재합니다. 

아주 먼 거리로의 분기

만일 분기 타켓이 16비트 오프셋으로 부족하다면, 아래와 같이 분기하도록 함

(명령어 하나를 더 사용해서 점프)

기존

beq $s0, $s1, L1

수정 : 명령어 하나를 더 사용해서 점프

bne $s0, $s1, L2

j L1

L2 : 

 

다섯 가지 MIPS 주소 지정 방식 요약

1. 수치(immediate) 주소 지정 : 피연산자는 명령어 내에 있는 상수(addi 명령어 사용 시 적용)
2. 레지스터 주소 지정 : 피연산자는 레지스터(add, sub 명령어 사용시 적용)
3. 변위 주소 지정 : 피연산자는 메모리 내용, 메모리 주소는 레지스터 + 명령어 내 상수를 더해 주소를 구함(lw, sw 명령어 사용시 적용)
4. PC-상대적 주소 지정 : PC값과 명령어 내 상수 값을 더해 주소를 구함(beq, bne 명령어 사용시 적용)
5. 의사 직접 주소 지정: 명령어 내의 26비트를 PC의 상위 비트들과 연접하여 점프 주소를 구함(j, jal 명령어 사용시 적용)