MIPS 딥다이브 📪

2.5 논리연산 명령어

배경: 🖳초기의컴퓨터🖳는 워드 전체에 대한 처리에만 관심을 가졌지만, 워드 내 일부 비트들에 대한 연산, 심지어 하나 하나의 비트에 대한 연산도 필요해졌다. (인간의 욕심은 끝이 없고...) 워드 내에 8비트로 저장된 문자를 검사하는 작업이 이러한 연산의 한 예이다. 뒤를 이어, 📦︎비트를 워드로 묶는 작업📦︎(packing)과 워드를 🗳비트 단위로 나누는 작업🗳(unpacking) 을 간단하게 하는 명령어들이 프로글밍 언어와 명령어 집합에 추가되었다. 이러한 명령어들을 논리연산 명령어라 부른다.

⏪ Shift ⏩

이러한 연산 중 첫 번째는 자리이동 연산이다. 이 명령어는 워드 내의 모든 비트를 왼쪽 또는 오른쪽으로 이동시키고, 이동 후에 빈 자리는 0으로 체운다.

• 0000 0000 0000 0000 0000 0000 0000 1001(two) = 9(ten)

이를 왼쪽으로 4번 자리이동시키면 ⏪

sll $t2 , $s0, 4 #reg $t2 = reg $ << 4 bits

• 0000 0000 0000 0000 0000 0000 1001 0000(two) = 144(ten)

이 된다.

MIPS에서는 이 명령어들을 sll(shift left logical) srl(shift right logical)로 부른다. 이제 앞서 미뤄뒀던 ✳ shamt ✳ 이 등장한다. 이는 자리 이동량(shift amount)을 나타내는 것으로 위의 명령어에서 shamt은 4가 된다.

🏧 위의 연산 결과를 다시 한 번 보면, 단순한 이동이 아니라는 것을 알 수 있다. sll(⏪)은 2^i를 곱한 것과 같은 결과가 된다.

---

⚠ AND & OR & NOT ⚠

또 다른 유용한 연산은 AND이다. AND연산은 비트 대 비트 연산자로 두 비트 값이 모두 1일 경우에만 결과가 1이 된다. 이와 반대로, OR 연산자는 1이 하나만 포함되어 있더라도 1이 된다. NOT 연산은 피연산자의 비트가 0이면 1, 1이면 0으로 만든다. MIPS의 설계자들은 위에서 살펴본 것처럼 3-피연산자 형식을 유지하기 위해서 NOR명령어를 포함시켰다. NOR0 = NOT(A OR 0) = NOT(A)가 되는 것이다.

---

2.6 ⚖ 판단을 위한 명령어 ⚖

컴퓨터가 단순한 계산기와 다른 점은 판단기능이 있다는 점이다. 입력 데이터나 연산 결과에 따라 다른 명령어를 실행할 수 있다. 프로그래밍 언어에서는 보통 if 문으로 판단 기능을 표현한다.

beq register1, register2, L1 

beq(branch if equal)는 레지스터1과 레지스터2의 값이 같으면 L1에 해당하는 문장으로 가라는 뜻이다.

bne register1, register2, L1 

또 다른 예는 bne(branch if not equal)로 두 레지스터가 같지 않으면 L1으로 가라는 뜻이다. 이 두 명령어를 조건부 분기라고 부른다.

예제 if-then-else를 조건부 분기로 번역 

다음 코드에서 f,g,h,i,j는 변수이고 
각각은 레지스터 $s0부터 $s4까지에 해당한다. 컴파일한 코드는? 

if (i == j) f = g + h ; else f = g - h;

bne $s3, $s4, Else 

add $s0, $s1, $s2 

이 명령을 실행한 후에는 if문장의 젤 끝으로 가야한다. 
이것은 무조건 분기라는 새로운 종류의 분기로 해결. 
이 명령어는 프로세서에게 하상 분기하라고 말한다. 
MIPS에서는 이 같은 명령어에 jump라는 이름을 붙이고
j로 간략하게 사용한다. 

하드웨어, 소프트웨어 인터페이스

같은지 다른지 비교하는 것도 중요하지만 대소 비교가 필요할 때도 있다. for 순환문 등에서 인덱스 변수 값이 0보다 작은지 검사할 때가 있다. slt(set on less than) 명령어는 두 레지스터의 값을 비교한 후 첫 번째 레지스터 값이 두 번째보다 작으면 세 번째 레지스터 값을 1, 아니면 0으로 하는 명령어로 이런 일을 처리한다.

slt $t0, $s3, $s4 #t0 = 1 if $s3 < $s4

상수 피연산자는 비교에서도 많이 사용한다. 그럴 때는 i를 살포시 붙여서 slti를 사용한다.

---

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

📣프로시저(procedure)나 함수는 이해하기 쉽고 ♻ 재사용 ♻이 가능하도록 프로그램을 구조화하는 방법으로 앞서 살펴본 추상화(abstraction)과 관련이 있다. 프로시저는 프로그래머가 한 번에 한 부분씩 집중해서 처리할 수 있도록 해준다.

📣인수(parameter)는시저에 값을 보내고 결과를 가져오는 일을 하므로, 프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스 역할을 한다.

프로그램이 프로시저를 실행할 때도 다음과 같이 여섯 단계를 거친다.

1. 프로시저가 접근할 수 있는 곳에 인수를 넣는다
2. 프로시저로 제어를 넘긴다.
3. 프로시저가 필요로 하는 메모리 자원을 획득한다.
4. 필요한 작업을 수행한다.
5. 호출한 프로그램이 접근할 수 있는 장소에 결과 값을 넣는다.
6. 프로시저는 프로그램 내의 여러 곳에서 호출될 수 있으므로 원래 위치로 제어를 돌려준다.

앞서, 공부했던 것처럼 레지스터는 데이터를 저장하는 가장 빠른 곳이므로 가능한 많이 사용하는 것이 좋다. 그래서 MIPS는 관례에 따라 레지스터 32를 할당한다.

• a$0 - a$3: 전달할 인수를 가지고 있는 인수 레지스터 4개
• $v0 - $v1: 반환되는 값을 갖게 되는 값 레지스터 2개
• $ra: 호출한 곳으로 되돌아가기 위한 복귀 주소를 가지고 있는 레지스터 1개

이후에는 키워드 중심으로 프로시저 명령어에 대해서 알아보자!

⤵️ Jal 명령어(return address) ⤵️

MIPS 어셈블리 언어는 레지스터를 할당할 뿐만 아니라 프로시저를 위한 명령어도 제공한다. 그 예가 지정한 주소로 점프하면서 동시에 다른 명령어의 주소를 ra레지스터에 저장하는 명령어로 jal 명령어 (jump - and - link instruction)라 부른다.

↩️ 복귀주소(return address) ↩️

이름에서 link는 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 주소 또는 링크를 형성한다는 뜻이다. 레지스터가 $ra(레지스터31)에 기억되는 이 링크를 복귀 주소(return address)라고 부른다. 한 프로시저가 여러 곳에서 호출될 수 있으므로 복귀 주소는 꼭 필요하다.

⤴️ Jr 명령어(jump register) ⤴️

앞서 살펴본 링크와 복귀를 지원하기 위해서 MIPS는 jr명령을 사용한다. 이 명령어는 레지스터에 저장되 주소로 무조건 점프하라는 뜻이다.

jr $ra 로 많이 사용된다. 

위 명령언느 레지스터 $ra에 저장되어 있는 주소로 점프하라는 뜻이다. 호출프로그램(caller)은 $a0 - $a3에 전달한 인수 값을 넣은 후 jal x명령을 이용해서 프로시저(함수) X(피호출 프로그램으로, callee라고 부른다)로 점프한다. callee는 계산을 끝낸 후 계산 결과를 $v0 - $v1에 얺은 후 jr $ra 명령을 실행하여 복귀한다.

접목!
내장 프로그램 개념은 현재 수행 중인 명령어의주소를 기억하는 레지스터를 필요로 한다. 이 레지스터의 이름은 명령어 주소 레지스터(instruction address register)라고 하는 것이 타당하지만 보통 프로그램 카운터 (program counter, PC)라 부른다. jal 명령은 프로시저에서 복귀할 대 다음 명령어부터 실행되도록 PC + 4를 레지스터 $ra에 저장한다.

---

더 많은 레지스터의 사용

컴퍼일러가 프로시저를 번역하는 데 인수 레지스터 4개, 결과 값 레지스터 2개 만으로 부족한 경우를 생각해 보자. 프로시저 호출이 다른 부분에 영향을 미치면 안 된다. 그렇기 때문에 복귀하기 전에 프로시저 호출 전의 상태로 되돌려 놓아야 한다. (레지스터 스필링!)

레지스터 스필링에 이상적인 자료구조는 스택(stack)이다. 스택은 나중에 들어온 것이 먼저 나오는 (LIFO) 구조이다. 스택에서는 다음 프로시저가 스필할 레지스터를 저장할 장소나 레지스터으 옛날 값이 저장된 장소를 표시하기 위해서 최근에 할당된 주소를 가리킬 포인터가 필요하다.

그래서 스택 포인터 등장! 이 스택 포인터(stack pointer)는 레지스터 값 하나가 스택이 되거나 스택에서 복구될 때마다 한 워드씩 조정된다. 레지스터 29를 할당해 놓고 있는데 이름은 $sp이다.

자료구조 와의 연!결!고!리 스택에 데이터를 넣는 작업을 푸시(push), 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다. 스택은 높은 주소에서 낮은 쪽으로 성장한다. 그래서 반직관적으로 느껴지지만 푸시를 할 땐느 주소를 감소시켜야 하고, 스택에서 팝을 할 때는 포인터 값을 증가시켜야 한다. (갑자기 자료구조가 나와서 당황스럽지만 keep calm and keep going)

int leaf_example(int g, int h, int i, int j) {
    int f;

    f = (g + h) - (i + j);
    return f;
}

leaf_example:
우선 프로시저 레이블로 시작된다. 

============================================================
    addi $sp, $sp, -12(4*3)          # 3개 레지스터를 저장할 자리를 만든다. 
    sw $t1, 8($sp)              # 나중에 사용하기 위한 $t1 저장
    sw $t0, 4($sp)              # 나중에 사용하기 위한 $t0 저장
    sw $s0, 0($sp)              # 나중에 사용하기 위한 $s0 저장
    ======================================================
    add $t0, $a0, $a1           # $t0 = g + h
    add $t1, $a2, $a3           # $t1 = i + j
    sub $s0, $t0, $t1           # f = $t0 - $t1 = (g + h) - (i + j)
    add $v0, $s0, $zero         # return f

============================================================   
    lw $s0, 0($sp)              # caller를 위해 $s0을 load한다.
    lw $t0, 4($sp)              # caller를 위해 $t0을 load한다.
    lw $t1, 8($sp)              # caller를 위해 $t1을 load한다.
    addi $sp, $sp, 12           # 되돌아오기 전에 저장해 두었던 값을 스택에서 꺼내 레지스터를 원상 복구한다. 
    
    ===========================================================
    jr $ra                      # 호출한 곳으로 돌아간다.

레지스터 값을 쓸데없이 저장했다 복구하는 일이 생길 수 있다. 이를 예방하기 위해 MIPS 소프트웨어는 레지스터 18개를 두 종류로 나눈다.

• $t0 ~ $t9: 프로시저 호출 시, 피호출 프로그램이 값을 보존해 주지 않는 임시 레지스터
• $s0 ~ $s7: 프로시저 호출 전과 후의 값이 같게 유지되어야 하는 변수 레지스터 8개

이런 관례는 레지스터 스필링을 많이 줄일 수 있다. $t0 ~ $t9는 호출 전후 같은 값을 유지할 필요가 없기 때문에 저장/적재 명령을 하지 않아도 된다.

---

중첩된 프로시저

📣 말단(leaf) 프로시저는 다른 프로시저를 호출하지 않는 프로시저를 말한다. 말단 프로시저만 있다면 일이 쉽겠지만 공부하는 우리의 바람과 달리 그렇지 못한다. 프로그래밍을 하다보면 자주 마주하는 상황이지만 프로시저는 다른 프로시저를 호출할 수 있다. 심지어 자기 자신을 호출하는 📣재귀 프로시저도 존재한다.

nt fact(int n) {
    if (n < 1) {
        return 1;
    } else {
        return (n * fact(n-1));
    }
}

============================================================ 
fact:
    addi $sp, $sp, -8       # 2개 레지스터를 저장할 공간 확보
    sw $ra, 4($sp)          # 복귀 주소를 저장
    sw $a0, 0($sp)          # 인수 n 저장

📣 #fact가 처음 호출 되었을 때 sw는 fact를 호출한 프로그램의 주소를 저장한다. 
n보다 작은지 검사해서 n이 조건에 부합하면 L1으로 가게 하는 명령어

    slti $t0, $a0, 1        # if n < 1 then $t0 = 1, else $t0 = 0
    beq $t0, $zero, L1      # if $t0 = 0 (n > = 1) then go to L1
    
📣#n이 1보다 작으면 팩토리얼이니까 1을 값레지스터에 넣고 반환한다.
이때 0에다 1을 더해서 $v0에 넣는다. 복귀 전에 +8을 해주면서 저장된 값 2개를 버리고 이후에 복귀 주소로 점프한다. 

    addi $v0, $zero, 1      # return 1
    addi $sp, $sp, 8        # 2개 레지스터를 스택에서 pop
    jr $ra
============================================================ 
L1:
    addi $a0, $a0, -1       # n = n - 1
    jal fact                # fact를 호출한다.

    lw $a0, 0($sp)          # 호출한 곳의 인수 n 가져오기
    lw $ra, 4($sp)          # 호출 주소 가져오기
    addi $sp, $sp, 8        # 2개 레지스터를 스택에서 pop

    mul $v0, $a0, $v0       # $v0 = n * funct(n - 1)

    jr $ra                  # 호출한 곳으로 돌아간다.

하드웨어 소프트웨어 인터페이스

레지스터에 들어가지 못할 만큼 큰 배열이나 구조체 같은 지역 변수를 저장하는 데도 스택이 사용되기 때문에 어려워진다. 프로시저의 저장된 레지스터와 지역 변수를 가지고 있는 스택 영역을 📣프로시저 프레임(procedure frame) 또는 📣액티베이션 레코드(activation record)라고 부른다. 위의 그림은 프로시저 호출 전, 중, 후의 스택 상태를 보여준다.

MIPS 소프트웨어 중에는 프레임 포인터(frame pointer $fp)가 프로시저 프레임의 첫 번째 워드를 가리키도록 한다. 스택 포인터 값이 프로시저 내에서 바뀔 수도 있으므로 메모리 내 지역 변수에 대한 변위는 변수가 프로시저 어느 부분에서 사용되느냐에 따라 달라질 수 있다.

😵 만약 프레임 포인터를 사용하면, 프레임 포인터가 변하지 않는 베이스 레지스터 역할을 하므로 지역 변수 참조가 간단해진다. 별도의 프레임 포인터 사용 여부와 상관없이 액티베이션 레코드는 항상 스택에 존재함에 유의하랑. 😵

---

새 데이터를 위한 힙 공간의 할당

Stack

최상위 주소에서부터 시작해 아래쪽으로 자란다.

Dynamic Data

힙(Heap)을 사용한다. 스택과 힙이 서로 마주 보며 자라도록 할당하기 때문에 메모리를 효율적으로 사용한다. C는 함수를 사용해서 힙의 공간을 할당 받기도, 돌려주기도 한다. (malloc(), free()) 근데 사용하고 반납을 잊어버리면 메모리 누출(memory leak)이 발생해 운영체제가 붕괴될 수 있다. 반면에 너무 일찍 반납하면 '매달린 포인터'(dangling pointer)가 발생한다. Java에선느 이런 버그를 피하기 위해 자동 메모리 할당과 가비지 컬렉션을 이용한다.

Static Data 정적 데이터 세그먼트(static data segment)

상수와 기타 정적 변수들이 여기에 들어가며 크기가 고정되어 있는 배열을 사용한다. 이곳에 들어가는 배열은 그 크기가 고정되어 있어서 정적 데이터 세그먼트에 잘 맞는다. 그러나 연결 리스트(linked list) 같은 자료구조는 크기가 가변적이므로 한 층 더 위인 dynamic data에 들어간다.

Text

MIPS 기계어 코드가 들어가는 부분이며 텍스트 세그먼트(text segment)라 부른다.

Reserved

최하위 주소부분은 사용이 유보되어 있다.

<참고> MIPS 어셈블리 언어의 레지스터 사용 관례
The 32 MIPS registers are partitioned as follows:

• Register 0 : $zero always stores the constant 0
• Regs 2-3 : $v0, $v1 return values of a procedure
• Regs 4-7 : $a0-$a3 input arguments to a procedure
• Regs 8-15 : $t0-$t7 temporaries #굳이 메모리에 가지고 갈 필요가 없다.
• Regs 16-23: $s0-$s7 variables
• Regs 24-25: $t8-$t9 more temporaries
• Reg 28 : $gp global pointer
• Reg 29 : $sp stack pointer
• Reg 30 : $fp frame pointer
• Reg 31 : $ra return address

---

2.8 MIPS의 32비트 수치를 위한 주소 지정 및 복잡한 주소지정 방식 🏠️

프로그램에서 사용하는 상수는 대체로 크기가 작다. 그러므로 대부분은 작은 16비트면 충분하다. enough! 하지만 대에 따라서는 더 큰 상수가 필요한 경우가 있다. 이럴 때를 위해 MIPS는 레지스터의 상위 16 비트에 상수를 넣는 lui(load upper immediate)명령어를 제공한다. 하위 16 비튼느 그 다음에 나오는 다른 명령으로 채울 수 있다.

32비트 상수의 로딩

레지스터 $s0에 다음 32비트 상수를 채우는 MIPS 어셈블리 코드를 작성하라. 
0000 0000 0011 1101 0000 1001 0000 0000

📣 먼저 lui를 이용해서 상위 16 비트를 채운다. 값은 십진수로 61
lui $s0, 61             # 61 = 0000 0000 0011 110

📣 다음은 하위 16비트를 더하면 된다. 하위 16비트의 값은 십진수로 2304
ori $s0, $s0, 2304      # 2304 = 0000 1001 0000 0000

📣 lui $s0, 61을 실행한 후 $s0의 값은 
0000 0000 0011 1101 0000 0000 0000 0000이 된다.

컴파일러나 어셈블러는 큰 숫자를 직접 다룰 수 없기 때문에 몇 조가긍로 나눈 후 레지스터에서 재조립 해야 한다. 수치 명령어의 상수는 물론 load나 store의 메모리 주소도 상수 필드 크기의 문제가 된다. MIPS 소프트웨어처럼 이 문제를 어셈블러가 해결하도록 하려면 큰 값을 만들 때 임시 레지스터를 제공해야 한다. 어셈블러를 위해 예약된 레지스터 $at가 이런 용도로 사용된다.

---

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

MIPS에서 가장 간단한 주소지정 방식은 점프 명령에서 사용하는 것이다. 점프 명령은 6비트의 op코드와 26비트의 주소 필드로 구성되는 J 타입 명령어 형식을 사용한다. 그러므로

j 10000 #go to location 10000

을 어셈블 하면 op의 부분에는 2, address에는 10000이 들어간다.

bne $s0,$s1, Exit #go to Exit if $s0 !== s1

조건부 분기 명령에는 분기 주소 외에 두 개의 피연산자가 더 있다. 그러므로 J를 쓰지 못하고 다음과 같이 어셈블 되어 16 비트만 쓸 수 있다.

PC 상대 주소지정(PC-relative addressing)

만일 프로그램에서 사용하는 모든 주소가 이 16비트 필드에 들어가야 한다면, 어떤 프로그램도 2^16보다 더 커질 수 없다. 그러나 이는 너무 작다. 어떻게 해결할까? 대안은 어떤 레지스터를 지정해서 그 값을 분기 주소와 더하도록 하는 것이다. 이렇게 했을 때 분기 주소는 PC = 레지스터 + 분기주소가 된다.

이 방식은 프로그램 크기가 2^32까지 커지는 것을 허용하면서 조건부 분기도 지원하며 분기 주소의 크기 제한을 극복한다. 그렇다면 이제 남은 문제는 어떤 레지스터를 사용하는가이다.

조건부 분기를 자세히 보면 대부분이 16개 명령어 이상 떨어지지 않은 위치로 분기한다. PC는 현 명령어의 주소를 가지고 있으므로 분기 주소를 더할 레지스터로 PC를 선택하면 현 위치에서 +-2^15워드 이내 떨어진 곳은 어디로든지 분기할 수 있다. 최근의 모든 컴퓨터가 그렇듯 MIPS도 모든 조건부 분기 명령에 PC 상대 주소를 사용한다. 조건부 분기의 목적지는 대부분 가까운 곳에 있기 때문이다.

이후에 살펴보겠지만 하드웨어 입장에서는 PC를 일직 증가시켜 다음 명령어를 가리키게 하는 것이 편하다. 그러므로 실제 MIPS 주소는 현재 명령어 주소PC를 기준으로 하는 것이 아니라 다음 명령어 주소 PC + 4를 기준으로 한다.

반면에, 프로시저들은 가까이 붙어 있어야할 이유가 없다. JAL 명령은 그래서 다른 주소 지정 방식을 이용한다. MIPS에서 j명령이나 jal명령어가 긴 주소를 사용할 수 있도록 J타입 형식을 사용한다.

MIPS 주소지정 방식 요약

여러 형태의 주소 표현을 일반적으로 주소 지정 방식(addressing mode)라고 한다.

1. 수치(immediate) 주소 지정:

피연산자는 명령어 내에 있는 상수이다.

2. 레지스터 주소 지정 :

피연산자는 레지스터

3. 베이스(base) 주소지정:

메모리 내용이 피연산자이다. 메모리 주소는 레지스터와 명령어 내의 상수를 더해서 구한다.

4. PC 상대 주소지정:

pc 값과 명령어 내 상수의 합을 더해서 주소를 구한다.

5. 의사직접(pseudodircet) 주소 지정:

명령어 내의 26비트를 PC의 상위 비트들과 연접하여 점프 주소를 구한다.