컴퓨터 구 lecture note #06

https://inyongs.tistory.com/121

 

[ 컴퓨터구조 ] MIPS Instructions (+Instruction to binary)

 

[Lecture04] ISA part2 참고

---

🤯Register Usage and Stack

추가적인 register와 stack 에 해 알아보자.

 

MIPS register에는 다음과 같은 register가 존재한다.

• $v0,$v1 : return값을 담는 레지스터이다. return값은 오직 하나만 존재한다. 따라서 하나의 레지스터만 필요하다.
  그러나 레지스터가 두 개 존재하는 이유는 만약 리턴 값이 32bit을 넘을 경우 $v1을 이용하여 추가적인 공간을 사용한다.
• $a0-$a3 : argument를 저장하는 레지스터이다. 오직 4개만 존재하며 만약 4개가 넘을 시 메모리의 stack을 이용한다.
• $t0-$9 : temporaries값을 저장하는 레지스터이다. 이 레지스터의 값들은 다른 함수 호출 시 보존되지 않는다. 덮여 쓰일 수 있는 값이다.
• $s0-$s7 : saved값을 저장하는 레지스터이다. 이 레지스터 값들은 보존되어야 하는 값이므로 메모리의 stack을 이용하여 미리 값을 복사해놓고 덮어쓴 다음 return 하기 전에 원래의 값을 restore 한다.
• $gp : global pointer 글로벌 변수에 쓰인다.
• $sp : stack pointer
• $fp : frame pointer
• $ra : return address 

다음은 Stack에 대해 알아보자. 레지스터가 한정적인 개수만 존재하므로 우리는 Stack을 이용한다.

LIFO구조이며 스택 포인터인 $sp를 통하여 가장 최근에 할당된 주소를 가리킨다.
스택의 주소는 최신에 할당될수록 낮아진다.

---

🤯 Memory Layout

 

메모리는 위 그림과 같은 구조를 가지고 있다.

Text : Program code
Static data : 전역 변수
Dynamic data : heap(malloc,new)
Stack : automatic storage

Dynamic data영역은 점점 높은 주소로, Stack은 점섬 낮은주소로 할당 된다.
만약 Stack과 Dynamic data영역이 만나게 된다면 더 이상 메모리를 새로운 곳에 사용할 수 없다.

만약 메모리 Protection이 있다면 프로그램이 Crash되겠지만 Protection이 없다면 동적 데이터와 스택이 만나더라도 아무일도 일어나지않아 데이터를 덮어쓰게 되어 프로그램에 치명적 오류를 발생시킬 수 있다.

Reserved영역은 특별한 사용을 위해 예약되어 있는 공간이다.

 

🤯 stack frame구조

함수 내에 선언된 변수가 stack에 할당되는 것은 이미 알고 있다.

procedure call(절차적 함수호출)을 하는 동안, register와 지역변수들 모두 stack에 할당된다.

stack frame : 함수 호출 과정에서 할당되는 메모리 블록

함수가 반환되면 그 함수의 stack frame을 날린다.

 

🤯 stack pointer 레지스터

스택을 쌓거나 반환하기 위해서는 top의 위치를 기억해야 하는데, cpu register에 그 역할을 하는 sp(stack pointer)라는 register가 존재한다.

함수 호출 시 선언된 변수의 크기만큼 sp는 올라가게 되는데, 

호출된 함수가 종료될 경우 sp는 그만큼 내려가야한다.

그만큼은 어느정도인가?

이를 해결하기 위해 frame pointer 레지스터를 사용한다.

 

🤯 frame pointer 레지스터

sp 포인터가 가르키고 있던 주소값을 기억하는 형태로 구현

그렇다고 새로운 함수가 호출될때마다 fp 레지스터 값을 백업해 놓지 않고

sp 레지스터의 값을 fp 레지스터로 바로바로 덮어 씌운다면 문제가 발생한다.

한번의 함수 반환 뒤에는 이미 덮어 씌워졌기 때문에 그 이전의 함수로 갈수 없기 때문이다.

이를 해결하기 위해서 sp 레지스터의 값을 fp 레지스터로 덮어씌우기전에 

fp 레지스터의 값을 스택에 저장(백업)한다.

그래서 함수 반환시 fp 레지스터는 스택에 있는 값을 불러와 이전 함수위치를 알수 있게 되는 것이다.

 

🤯 과정

함수 호출시

1) fp 의 주소값을 스택에 저장

2) fp 에 sp 값을 덮어씌운다.

3) 할당된 메모리 만큼(지역변수, 매개변수) sp 값 증가

함수 종료시

4) sp 에 fp 값을 덮어씌운다. (3번에서 할당한 스택프레임을 날리는 효과)

5) 스택에 저장된 이전 fp 값을 fp 에 덮어씌운다.

 

Stack 영역

: 함수의 호출과 관계되는 지역 변수와 매개 변수가 저장되는 영역이다. 스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다. 이렇게 스택 영역에 저장되는 함수의 호출 정보를 스택 프레임(stack frame)이라고 한다.

 

스택 영역은 푸시(push) 동작으로 데이터를 저장하고 팝(pop) 동작으로 데이터를 인출한다. 이러한 스택은 후입 선출(LIFO, Last-In-First-Out) 방식에 따라 동작하므로 가장 늦게 저장된 데이터가 가장 먼저 인출된다.

스택 영역은 메모리의 높은 주소에서 낮은 주소의 방향으로 할당된다.

 

낭비되는 공간이 없고 하나의 명령만으로 메모리 조작과 주소 조작이 가능하다는 장점이 있고

한계가 존재하여 한계를 초과하도록 삽입할 수 없다는 단점이 있다

 

Heap 영역

: 프로그래머가 할당/해제하는 메모리 공간이다. 이 공간에 메모리를 할당하는 것을 동적할당(Dynamic Memory Allocation)이라고도 부른다. 메모리의 낮은 주소에서 높은 주소의 방향으로 할당된다.

malloc() 또는 new 연산자 등을 통해 할당하고 free() 또는 delete 연산자 등을 통해서 해제가 가능하다.

런타임 시에 크기가 결정된다.

 

프로그램에 필요한 개체의 개수나 크기를 미리 알 수 없는 경우와 개체가 너무 커서 스택 할당자에 맞지 않는 경우 사용 가능하다.

 

위의 Heap 영역과 Stack 영역은 같은 공간을 공유한다.

Heap 영역이 메모리 위쪽 주소부터 할당되면 Stack 영역은 메모리의 아래쪽부터 할당되는 식이다.

따라서 각 영역이 상대 공간을 침범하는 일이 발생할 수 있는데 Heap이 Stack 영역을 침범하는 경우 Heap overflow라 하고, Stack이 Heap 영역을 침범하는 경우Stack overflow라고 한다.

 

 

< R format >

 

이 R format에 add $t0, $s1, $s2 를 넣어보면 아래와 같다.

이것을 10진수로 표현하면 아래와 같다.

(참고) register는 각자 번호가 매겨져있다. ($s1=17, $s2=18, $t0=8)

이것을 그대로 binary code로 표현해보면 아래와 같다.

 

 

add $t0, $s1, $s2 에서 00000010001100100100000000100000 으로 바뀌는 과정을 살펴보았다.

그런데 문제점이 하나 있다. 5bits 필드로는 2^5 = 32 보다 큰 수를 표현할 수 없다.

32보다 큰 상수나, 주소값이 오게 된다면 표현할 수 없다는 것이다.

따라서 5bits 필드보다 큰 필드가 필요하게 되었다.

결국 16bits를 표현할 수 있는 I format을 만들게 되었다.

 

엇, 그런데 설계원칙에서는 형태를 통일하라는 원칙이 있었는데? 왜 3개로 나뉘게 만들었지?

여기서 설계 원칙이 또 등장한다.

 

Design Principle 4: Good design demands good compromises

좋은 설계에는 적당한 절충이 필요하다.

 

모든 명령어의 길이를 같게 하고 싶은 생각과 명령어 형식을 한가지로 통일하고 싶은 생각 사이에서 충돌이 생기게 된 것이다. 여기서 설계자들이 택한 절충안은 모든 명령어의 길이(32bits)를 같게 하되, 명령어 종류에 따라 형식(R,I,J format)은 다르게 하는 것이었다.

 

2. I format

 

 

op : 연산자

rs : base register

rt : destination register

constant : 표현범위는 -2^15 ~ 2^15 -1 이다.

address : offset. rs의 주소값으로부터 얼마나 떨어져 있나를 표시한다.

 

 

I format은 R format과 달리 16bits를 이용해 상수와 주소표현이 가능하다. 그래서 주소값을 가져오는 bne, beq, lw, sw 등의 분기문과 상수연산을 하는 addi, addiu, andi 등이 가능하다.

그런데 과연 16bits로 상수값과 메모리 주소값을 전부 표현할 수 있을까?

1) 상수값

우선, 프로그램에서 사용하는 대부분의 상수값은 작아서 16bits로 표현이 가능하다.

그렇다는건 16bits보다 큰 상수가 나올 때도 있다는 말이다. 그 때는 어떻게 해야하나?

바로 상위 16bits와 하위 16bits를 lui, ori 를 사용하여 32bit 상수를 표현하면 된다.

 

예시를 들어보자. $s0에 아래 32bits 상수를 채워보자.

0000 0000 0011 1101 0000 1001 0000 0000

 

1. lui를 통해 상위 16bits를 채운다.

상위 16bits = 0000 0000 0011 1101(two) = 61(ten)

lui $s0, 61

=> 현재 $s0 = 0000 0000 0011 1101 0000 0000 0000 0000

 

2. ori를 통해 하위 16bits를 더한다.

하위 16bits = 0000 1001 0000 0000(two) = 2304(ten)

ori $s0, $s0, 2304

=> 최종 $s0 = 0000 0000 0011 1101 0000 1001 0000 0000 = 4000000

 

32bits 상수값을 표현할 때, 이렇게 I format instruction인 lui와 ori를 통해 32bits 상수값을 표현하면 된다.

 

2) 주소값

I format에서 주소값을 표현할 때는 조건부 분기의 경우이다. (bne, beq) 조건부 분기는 주로 반복문이나 조건문에서 사용되므로, 대부분 가까이 있는 범위로 분기한다고 볼 수 있다. 이는 대부분 2^16 word 이내로 분기한다고 말할 수 있다. 

 

현재 위치로부터 얼만큼 떨어져 있나를 표시해주면 된다. 이것을 PC-relative addressing (PC 상대 주소지정)라고 한다.

 

분기문을 생각해보자.

조건이 맞으면 목표 위치까지 이동해야한다. 이 목표 위치. 즉, 목표 위치의 주소값을 어떻게 구할까?

현재 메모리에서 내가 있는 주소값인 PC(Program Counter)를 어떤 레지스터 주소값에 분기 주소를 더해주면 된다.

PC = 레지스터 + 분기주소 라고 말할 수 있다.

 

무슨말이지..?

내가 이동하고 싶은 메모리 주소는 내가 현재있는 주소값에서 얼마나 떨어져 있는지를 더해줌으로써 구하면 된다.

즉, 타겟 주소 = 현재 주소 + 떨어진 거리 이다.

그리고 이 타겟 주소를 현재 가리키고 있는 주소(PC)라고 지정해주면 된다.

그러면 현재 가리키고 있는 주소(PC)가 이동하고 싶은 메모리 주소를 가리키게 된다.

 

그래서 16bits 필드엔 뭐가 들어가는 거야?

타겟 주소 = 현재 주소 + 떨어진 거리

이것은 이렇게 표현할 수 있다.

타겟 주소 = 현재 주소 + offset*4

여기서 offset이 16bits 필드에 들어가게 된다.

 

(주의)

나중에 배우지만, 하드웨어 입장에서는 PC를 미리 4 만큼 증가시켜 놓는다.

즉, 실제 MIPS 주소는 PC를 기준으로 하는 것이 아니라, (PC+4) 를 기준으로 하게 된다.

그래서 실제론 이동하고 싶은 메모리 주소를 (현재주소+4 + 떨어진 거리)로 구해주어야 한다.

 

3. J format

 

op : 연산자

address : 주소

 

I format에서 16bits로 주소를 표현하지만, J format은 26bits로 주소값을 표현한다.

가장 심플한 형태이다. J 와 Jal 이 J format에 속한다.

 

그런데 이 26 bits로도 모든 주소값을 표현하기 힘들다.

어떻게 32bits로 표현할 수 있을까?

 

1. byte 주소가 아닌 워드 주소를 사용해서, 26bits의 4배만큼의 28 bits로 표현가능하다.

byte 주소로 80000 인 곳으로 Jump 한다고 하면, address에는 word 단위로 표현해 80000/4 = 20000이 저장되어 있다.

그래서 address * 4 로 28bits만큼의 주소를 표현할 수 있다.

4를 곱해주는 것은 left shift 2번 해준것과 똑같다.

 

2. 나머지 4bits는 PC의 상위 4bits를 가져와서 표현한다.

즉, PC가 0010 0000 0000 0000 0000 0000 0000 0000 이라면

상위 4bits인 0010 을 가져오는 것이다.

PC 상위 4bits는 바뀌지 않은 채로 표현된다. 이는 MIPS의 단점이라고 말할 수 있다.

 

MIPS instruction -> Binary machine code

Loop:  ....
         ....
         J    Loop
Exit :  

(Loop의 주소값 : 80000)

 

 

 

 

< J format >

J의 op는 2(hex)이다.

J Loop 에서 Loop의 주소값/4 를 address에 넣어준다. (word 단위로 넣은 것임)

결국, 중요한것은 jump 명령어는 워드단위 주소접근을 한다는 점이다!!!!!!!!! ex) j 10000 # 40000번지의 주소로 점프하시오.

이를 binary로 표현하면 아래와 같다.

이렇게 binary로 표현하였다.

 

 

 

현재 표현된 address는 00 0000 0000 0100 1110 0010 0000 은 26bits이다. 이것으로 타겟 주소를 찾는 것도 살펴봐보자. 즉, 26bits의 address를 32bits로 확장하는 과정을 살펴보자.

 

1. left shift 두번

address = 0000 0000 0001 0011 1000 1000 0000

 

2. PC bits에서 상위 4개의 bits를 가져와서 address의 상위 4bits로 사용한다.

(PC = 80024 이라고 가정. 32bits로 표현하면 PC = 0000 0000 0000 0001 0011 1000 1001 1000)

address = 0000 0000 0000 0001 0011 1000 1000 0000

 

 

26bits인 address 00 0000 0000 0100 1110 0010 0000 를

32bits인 address 0000 0000 0000 0001 0011 1000 1000 0000 로 표현하였고, 이 주소는 타겟 주소가 된다.

 

Branch Addressing

MIPS에는 beq, bne 등 분기 연산이 존재한다. 이는 조건을 판단하여 원하는 주소로 이동하는 명령어이다.
이 명령들에서 분기가 어떻게 이루어지는지 알아보자.

 

우선, beq, bne연산은 I-format 연산으로 16bit의 Adress를 담을 공간을 가지고 있다.
대부분의 branch연산의 목표 주소는 현재 위치에 가까운 곳에 위치하고 있기 때문에 16bit에서 처리가 가능하다.(if, loops 등) 

 

branch 연산에 사용하는 주소 계산방법은 PC-relative addressing이다.

 

Target address = PC + offset  * 4를 통하여 주소를 설정할 수 있다. 
여기서 offset은 16bit에 저장된 address주소를 말한다. 4를 곱해주는 이유는 하나의 연산이 4byte이기 때문이다.

 

이 방법을 통하여 우리는 +-2^15의 byte를 이동할 수 있다.

 

따라서 실제로는 (PC+4) + offset * 4 를 통하여 Target address를 설정할 수 있다.

 

만약 branch연산을 통해 분기하고자 하는 거리가 매우 멀 경우 어셈블러는 자동적으로 코드를 재 작성한다.
예를 들어 beq $s0, $s1, L1 명령에서 L1의 거리가 표현이 불가능한 거리라면 
bne $s0, $s1, L2 , j L1 명령을 통하여 명령을 두 개로 나누어 이동을 수행한다. J-format은 어느 거리던 이동할 수 있기 때문이다.

Jump Addressing

jumb연산에는 j와 jal연산이 있다. 이 연산을 통하여 어느 주소든지 이동할 수 있다.

PC와 거리가 멀더라도 text segment를 통하여 이동이 가능하다.

위 명령을 J-format형식에 속한다. J-format은 6bit의 op필드와 26bit의 32bit 필드를 가지고 있다.

그림 2.1

Target adress = address * 4를 통하여 설정할 수 있다. 따라서 우리는 총 2^28 byte의 크기에 이동할 수 있다.(2^26에서 *4이므로 <<2와 같음)
하지만 총 32bit의 주소를 이동하기에는 비트가 모자라다. 따라서 이때 필요한 추가적인 4bit를 PC의 TOP 4bit를 이용한다. PC의 첫 4BIT는 메모리의 256BM의 공간을 나타내고 있다. 따라서 4BIT + 28BIT=32BIT의 공간을 이동할 수 있다.

jr연산은 레지스터를 이용하여 jump 하는 것이므로 따로 PC의 BIT를 사용하지 않고 32비트를 표현하는 레지스터를 통하여 바로 점프할 수 있다. 이는 R-format이다.