MIPS

조건 분기(Conditional Brances)

MIPS는 조건이 참일 때만 특정 라벨로 분기(이동)하고, 그렇지 않으면 그 다음 줄로 계속 실행한다.

조건문(Conditional Operations)

beq rs, rt, L1  # rs==rt일 때 L1으로 분기
bne rs, rt, L1  # rs!=rt일 때 L1으로 분기
j L1            # 무조건 L1으로 점프

if문 예제

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

Compiled MIPS code:

bne $s3, $s4, Else    # i != j 이면 Else로 점프
add $s0, $s1, $s2     # f = g + h
j Exit
Else: sub $s0, $s1, $s2 # f = g - h
Exit: ...

• 조건을 만족하지 않으면 Else로 점프해서 다른 경로 실행, 마지막엔 j Exit으로 빠져나온다.

반복문(Loop)

while (save[i] == k) i += 1;

• i : $s3, k: $s5, save 배열 주소: $s6

Loop:  sll  $t1, $s3, 2      # i * 4 (byte 주소)
       add  $t1, $t1, $s6    # save[i] 주소
       lw   $t0, 0($t1)      # save[i] 값 로드
       bne  $t0, $s5, Exit   # 같지 않으면 루프 종료
       addi $s3, $s3, 1      # i++
       j    Loop
Exit:  ...

• sll : shift left logical, 즉 i * 4 연산을 의미한다.(int는 4바이트 이므로 주소값 계산)
• 계산된 주소를 lw 명령어를 통해 (0 + $t1) save[i]의 값을 로드한다.

Basic Block

Basic Block은 중간에 분기(branch)가 없고, 오직 처음(진입점), 끝에만 분기가 있는 코드 덩어리를 의미한다. 컴파일러가 최적화할 때 단위로 사용한다.

조건 판별과 결과 저장 : slt / slti

• slt rd, rs, rt : if(rs < rt) rd=1; else rd = 0;
• slti rt, rs, imm : 상수 비교

slt $t0, $s1, $s2     # if ($s1 < $s2)
bne $t0, $zero, L     # $t0 != 0 이면 L로 점프

• beq나 bne과 조합하여 <, >, >= 같은 조건 구현이 가능하다.

• 비교 명령어가 제한적인 이유 : 왜 blt, bge 같은 명령어가 기본으로 없을까?

  • <, >= 같은 비교는 하드웨어서 느리다.
  • beq, bne만 지원하고, 나머지는 slt랑 조합해서 구현하는 방식을 채택 -> 빠른 클럭 속도 유지 가능

• Signed vs Unsigned

  • slt, slti : 부호 있는 비교
  • sltu, sltui : 부호 없는 비교

$s0 = -1 (0xFFFFFFFF)  
$s1 = 1

slt  $t0, $s0, $s1   # true → $t0 = 1
sltu $t0, $s0, $s1   # false → $t0 = 0

• 부호(sign)을 해석하느냐 안 하느냐에 따라 판단이 다르다.

프로시저 호출(Procedure Calling)

• 기본 단계
  1. 인자 전달
  2. 함수 호출
  3. 공간 확보(필요 시)
  4. 계산 수행
  5. 결과 반환
  6. 복귀

주요 레지스터

프로시저 호출 명령어

• 함수 호출(Procedure call) : jump and link : 함수 위치(Label)로 이동 및 $ra에 return address까지 저장

jal ProcedureLabel

• 함수 반환(Procedure retur) : jump register : 다시 원래 위치로 돌아오는 명령어

jr $ra

Leaf Procedure

함수 안에서 더 이상 다른 함수를 호출하지 않는 함수

int leaf_example (int g, h, i, j) {
    int f;
    f = (g + h) - (i + j);
    return f;
}

leaf_example:
    addi $sp, $sp, -4    # 스택 공간 확보
    sw   $s0, 0($sp)     # $s0 저장

    add  $t0, $a0, $a1   # g + h
    add  $t1, $a2, $a3   # i + j
    sub  $s0, $t0, $t1   # f = 결과
    add  $v0, $s0, $zero # 반환값 설정

    lw   $s0, 0($sp)     # $s0 복원
    addi $sp, $sp, 4     # 스택 복구
    jr   $ra             # 복귀

Non-Leaf Procedure

함수 안에서 다른 함수를 호출하는 함수(또는 재귀)

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

fact:
    addi $sp, $sp, -8
    sw   $ra, 4($sp)
    sw   $a0, 0($sp)

    slti $t0, $a0, 1
    beq  $t0, $zero, L1
    addi $v0, $zero, 1
    addi $sp, $sp, 8
    jr   $ra

L1: addi $a0, $a0, -1
    jal  fact          # 재귀 호출
    lw   $a0, 0($sp)    # n 복원
    lw   $ra, 4($sp)    # $ra 복원
    addi $sp, $sp, 8
    mul  $v0, $a0, $v0  # n * fact(n-1)
    jr   $ra

Byte/Halfword 연산(문자열 처리 관련)

• 바이트/하프워드 로드/스토어 명령어

• MIPS는 32비트 구조라서, 메모리 접근 시 기본 단위는 word(4바이트)이다. 하지만 문자열 처리 같은 작업에서는 1바이트(문자) 단위로 작업을 해야 하므로, 위 명령어들을 사용해서 원하는 만큼의 메모리만 접근하는 것이다.

String Copy

문자열 복사 관련 명령어

문자열 복사 예제

• C 코드

void strcpy (char x[], char y[]) {
  int i = 0;
  while ((x[i] = y[i]) != '\0') i++;
}
// Adresses of x, y in $a0, $a1
// i in $s0

• MIPS code

strcpy:
  addi $sp, $sp, -4      # 스택 공간 확보
  sw $s0, 0($sp)         # $s0 저장
  add $s0, $zero, $zero  # i = 0
L1:
  add $t1, $s0, $a1      # y[i] 주소 계산
  lbu $t2, 0($t1)        # y[i] = $t2
  add $t3, $s0, $a0      # x[i] 주소 계산
  sb $t2, 0($t3)         # x[i] = y[i]
  beq $t2, $zero, L2     # y[i] == '\0'이면 종료
  addi $s0, $s0, 1       # i++
  j L1                   # 반복
L2:
  lw $s0, 0($sp)         # $s0 복원
  addi $sp, $sp, 4       # 스택 복구
  jr $ra                 # 복귀

32비트 상수(32-bit Constants)

32비트 상수 구성 명령어

• 예시(16비트 immediate만으로 충분하지 않을 때):

lui $s0, 61         # 상위 16비트 = 61 (0x3D)
ori $s0, $s0, 2304  # 하위 16비트 = 2304 (0x0900)

• 최종 결과 : 0x3D0900이 $s0에 저장된다.
• lui : Load Upper Immediate, 상위 16비트를 설정하고 하위는 0으로 채운다.
• ori : 논리합(OR)을 통해 하위 16비트를 설정한다.

분기(branch) 및 점프(jump) 관련 명령어

분기(Branch) 명령어 주소 계산

• 분기(Branch) 명령어 형식

  

• op : 명령어(opcode), 예: beq, bne

• rs, rt : 비교할 두 개의 레지스터

• offset : 분기할 주소까지의 거리(단위: 명령어 수)

• Branch 명령어는 PC-relative 방식을 사용한다.

PC-relative Addressing(상대 주소 방식)

MIPS의 분기 명령어는 절대 주소를 직접 저장하지 않고, 현재 명령어 위치(PC)를 기준으로 offset만 저장한다.

Target Address = (PC + 4) + (offset × 4)

• PC + 4는 이미 다음 명령어로 넘어간 상태(MIPS는 항상 먼저 PC+=4)
• offset x 4 : 오프셋은 "명령어 단위(word, 4바이트)"로 저장되므로 4를 곱해 실제 주소 단위로 변환해야한다.

"near branch"

대부분의 분기(branch) 타겟은 near branch이다.

• offset 필드는 16비트 -> 표현 가능한 값의 범위

  -2^15 ~ 2^15 - 1 = -32768 ~ 32767 (word 단위)
  → 실제 주소 단위로는 -131072 ~ +131068 (byte 단위)

• 따라서 분기 가능한 범위는 현재 PC 기준 -128KB ~ +128KB정도로, 비교적 가까운 거리(near)에만 분기가 가능하다.

• 멀리 떨어진 곳은 jump 명령어(j, jal) 또는 어셈블러의 자동 분기 우회 방식을 사용한다.

예제

// C code
if (a == b) {
    // do something
}

# MIPS code
beq $t0, $t1, Label   # $t0 == $t1이면 Label로 분기

• 현재 PC가 0x1000이고, Label이 0x1010에 있다고 가정하면
  • PC는 이미 0x1004 상태
  • offset 계산 : (0x1010 - 0x1004) / 4 = 3
  • 명령어로는 beq $t0, $t1, 3

점프(jump) 명령어 주소 계산

• jump 명령어 형식

• op : 명령어(예: j, jal)
• address : 26비트 target 주소

Jump 명령어의 주소 계산 방식

Target Address = (PC[31:28] << 28) | (address << 2)

1. Jump 명령어 안에는 26비트 주소가 들어있고,

2. 이는 외쪽으로 2비트 시프트되어 하위 28비트를 구성한다.

3. 상위 4비트는 현재 PC의 상위 4비트(PC[31 : 28])를 그대로 사용한다.

• 예시:
  • 현재 PC가 0x00400000
  • jump 명령어 내 address 필드가 0x0003FF0일 경우

Target Address = 0x00400000[31:28] : (0x0003FF0 << 2)
               = 0x00400000 | 0x000FFC0
               = 0x0043FF00 (점프할 최종 주소)

Jump는 왜 멀리갈 수 있는가?

Branch 명령어는 16비트 offset만 가능했지만, jump는 26비트 address * 4 = 약 228바이트 범위가 가능하다. 즉, 코드가 멀리 떨어져 있어도 접근이 가능하다.

Branching Far Away

MIPS의 branch 명령어는 16비트 offset만 사용이 가능하다. 즉 실제 주소 범위는 ±128KB이다. 하지만 현실에서 분기할 타겟이 너무 멀리 떨어진 경우가 있다. 예를 들어 beq $s0, $s1, L1에서 L1이 500KB 떨어진 곳에 있다면, branch 명령어 하나로 도달할 수 없다.

해결책으로 어셈블러가 Jump와 함께 분기 코드를 자동 재작성을 한다.

beq $s0, $s1, L1     # 원래 의도
↓
bne $s0, $s1, L2     # 조건 반전: 다르면 L2로 가고
j   L1               # Jump로 멀리 있는 L1으로 점프
L2:                  # 조건 안 맞으면 여기로 떨어짐

beq는 가까운 거리만 가능해서 조건을 뒤집은 다음, 가까운 곳인 L2로 분기 시킨다. j L1로 멀리 있는 진짜 목표 L1으로 이동시킨다. 조건을 뒤집는 이유는 jump는 무조건 실행되므로, 조건 실패 시 jump를 피하기 위해 조건을 반전시킨다.(어셈블러가 자동으로 처리, 프로그래머는 몰라도 된다.)

Target Addressing Exmaple(Branch & Jump Cont.)

아래 예제는 MIPS의 분기와 점프 명령어가 실제로 어떻게 주소를 계산해서 흐름을 제어하는지 보여주는 예제이다.

Loop:
sll  $t1, $s3, 2        # $t1 = $s3 * 4
add  $t1, $t1, $s6      # $t1 = base + offset
lw   $t0, 0($t1)        # 메모리에서 데이터 로드
bne  $t0, $s5, Exit     # 다르면 Exit으로 분기
addi $s3, $s3, 1        # 인덱스 증가
j    Loop               # 다시 Loop로 점프
Exit:

• 가정 : Loop 라벨의 주소는 0x80000

• PC + 4 = 0x80016 (다음 명령어 주소)
• Exit 주소 = 0x80024
• offset = (0x80024 - 0x80016) / 4 = 0xE /4 = 2 >> 실제로는 offset 필드에 2가 저장됨.

Target = (PC + 4) + (offset × 4)

Addressing Mode Summary

동기화(Synchronization)

• 여러 CPU/레지스터가 메모리를 공유할 때, 데이터 레이스 방지를 위해 필요하다.
• 읽기-수정-쓰기 사이에 다른 접근이 불가해야한다.

동기화 관련 명령어

try:
  add $t0, $zero, $s4   # 교환할 값
  ll $t0, 0($s1)        # 주소의 값 읽기
  addi $t0, $t0, 1      # 값 수정
  sc $t0, 0($s1)        # 조건부 저장
  beq $t0, $zero, try   # 실패 시 반복

어셈블리 가상 명령어(Pseudoinstruction)

실제 기계어로 1:1 대응되지 않지만, 편의를 위해 제공되는 명령어이다.

slt $at, $t0, $t1  
bne $at, $zero, L

오브젝트 모듈 구성

컴파일러 또는 어셈블러가 생성하는 출력물:

• Header : 정보 요약
• Text Segment : 명령어 코드
• Static Data Segment : 고정된 변수들
• Relocation Info : 주소 조정 저보
• Symbol Table : 전역 심볼 정보
• Debug Info : 소스 코드와의 연계 정보