컴퓨터 구조론 Lecture 2 - 5

D0Lim·2021년 1월 7일
수업 필기컴퓨터 공학컴퓨터 구조컴퓨터 구조론

컴퓨터 구조론

목록 보기
8/13
post-thumbnail

시작하기 전

이 글은 필자가 수업시간에 들은 내용과 강의록을 토대로 정리한 글입니다.
수업 필기이다 보니, 오류가 있거나 설명이 부족한 부분이 있을 수 있습니다.
궁금하신 점이나 지적하실 점이 있다면 댓글로 달아주세요! 확인 후 내용을 추가하거나 답변해드리도록 하겠습니다 :)

레지스터 사용과 스택(Register Usage and Stack)

MIPS 레지스터에 대한 추가 사항

  • $v0 , $v1 : 결과값 (레지스터 2, 3번)
    • 2개를 사용하는 이유는 결과값이 64비트 사이즈일 경우를 처리하기 위해서이다.
    • 결과값이 32비트 혹은 그 이하라면, 하나만 쓴다.
  • $a0 ~ $a3 : 매개변수 (레지스터 4 ~ 7번)
  • $t0 ~ $t9 : 임시 값
    • 피 호출자(callee)에 의해 보존되지 않는다.
    • 다른 말로, 호출자(caller)에서 사용하던 값이 덮어씌워질 수 있다.
  • $s0 ~ $s7 : 저장된 값
    • 피 호출자(callee)에 의해서 저장되고, 다시 복원되어야 한다.
    • 다른 말로 반환하기 전에 원래 사용하던 값으로 복원해주어야 한다는 뜻이다.
  • $gp : 정적 데이터(static data)를 위한 전역 포인터 (레지스터 28번)
  • $sp : 스택 포인터 (레지스터 29번)
  • $fp : 프레임(frame) 포인터 (레지스터 30번)
  • $ra : 반환 주소(return address) (레지스터 31번)

스택

  • 후입 선출 방식으로 동작하는 자료구조
  • 스택 포인터 ($sp) : 스택에서 가장 최근에 할당된 주소를 저장하는 레지스터

Leaf 프로시저(Leaf Procedures)

Leaf 프로시저란?

  • Leaf 프로시저는 또 다른 프로시저를 호출하지 않는 프로시저이다.

예시

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

  • 매개변수 g, … , j는 $a0 , … , $a3 에 저장된다.

  • f는 $s0 에 저장된다. 따라서, $s0 은 스택에 저장해야 한다.

  • 결과는 $v0 에 저장한다.

  • MIPS 코드

leaf_example:
    addi $sp, $sp, -4      # Save $s0 
    sw   $s0, 0($sp)       # on stack (push)
    add  $t0, $a0, $a1     # 
    add  $t1, $a2, $a3     # Procedure body
    sub  $s0, $t0, $t1     # 
    add  $v0, $s0, $zero   # Result
    lw   $s0, 0($sp)       # Restore 
    addi $sp, $sp, 4       # $s0
    jr   $ra               # Return

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

Non-Leaf 프로시저란?

  • Non-Leaf 프로시저는 또 다른 프로시저를 호출하는 프로시저이다.
  • 중첩 호출을 위해, 호출자는 다음을 스택에 저장해야 한다.
    • 호출자로 돌아오는 반환 주소(return address)
    • 호출(다른 프로시저에서의 작업)이 끝난 후에 필요할 모든 매개변수나 임시 변수들
  • 호출이 끝난 후 스택으로부터 복원된다.

예시

  • C 코드
int fact (int n)
{
    if (n < 1) return 1;
    else return n * fact(n - 1);
}

  • 매개변수 n은 $a0에 저장된다.

  • 결과는 $v0 에 저장한다.

  • MIPS 코드

fact:
    addi $sp, $sp, -8    # adjust stack for 2 items
    sw   $ra, 4($sp)     # save return address to caller
    sw   $a0, 0($sp)     # save argument of this procedure
    slti $t0, $a0, 1     # test for n < 1
    beq  $t0, $zero, L1
    addi $v0, $zero, 1   # if so, result is 1
    addi $sp, $sp, 8     #   pop 2 items from stack
    jr   $ra             #   and return
L1: addi $a0, $a0, -1    # else decrement n
    jal  fact            # recursive call
    lw   $a0, 0($sp)     # restore original n
    lw   $ra, 4($sp)     #  and return address
    addi $sp, $sp, 8     # pop 2 items from stack
    mul  $v0, $a0, $v0   # multiply to get result
    jr   $ra             # and return

Non-Leaf 프로시저의 경우, 피호출자가 호출자의 반환 주소(return address)를 스택에 저장해야 한다. 특히 재귀일 경우 더 그런데, 중첩적으로 호출이 일어날 경우 스택에 반환 주소가 있어야만 스택에서 pop을 하며 제대로 원래 위치로 돌아갈 수 있기 때문이다.

스택에서의 지역 데이터(Local Data on the Stack)

local data on stack

  • 지역 데이터는 피 호출자에 의해서 할당된다.
    • 예를 들어 C 자동 변수가 있다. 일반적으로 생각하는 함수 내 변수들은 모두 자동변수다.
  • 프로시저 프레임 (활성화 기록)
    • 몇몇 컴파일러들이 스택 저장소를 관리하기 위해 사용한다고 한다.

매개변수가 4개 이상이라면? 지역변수는 어디에 저장해? (More than 4 arguements? Local variables?)

variable4

  • 위의 그림에서 볼 수 있듯, 매개변수가 4개보다 많을 경우, 스택의 프레임(stack frame) 보다 더 아래(Bottom)쪽에 매개변수를 저장한다. 스택의 프레임은 스택에 할당되는 해당 프로시저의 메모리 블럭 정도로 생각하면 된다. 즉, 스택에 할당되는 프로시저 블록의 바깥에 있다.

  • 지역 변수는 저장 레지스터보다 더 위(Top)쪽에 저장하도록 한다.

  • 스택은 큰 주소값을 가지는 쪽이 Bottom이 되도록 만들어지는데, 그리하여 앞의 예제로 사용했던 팩토리얼 예제의 경우 우측 사진과 같이 스택에 할당되게 된다.

메모리 레이아웃(Memory Layout)

memory_layout

  • 텍스트 : 프로그램 코드
  • 정적 데이터 : 전역 변수들
    • 예를 들어, C에서의 static 변수, 상수 배열 등이 있다.
    • $gp 는 오프셋(offset)을 이용해서 이 부분으로 접근할 수 있게 초기화된다.
  • 동적 데이터 : 힙(heap)
    • 예를 들어 C에서의 malloc/free가 이 동적 데이터 영역을 사용한다.
    • 스택 : 자동 저장공간이다.

바이트 / Halfword 연산(Byte / Halfword Operation)

  • MIPS에서의 바이트(byte) / halfword의 불러오기(load)와 저장(store)
    • 문자열 처리가 가장 기본적인 경우이다.
  • 참고로, Halfword는 2바이트이다.

lb rt, offset(rs) / lh rt, offset(rs)

  • rt로 32비트 부호 확장을 수행한다.

lbu rt, offset(rs) / lhu rt, offset(rs)

  • rt로 0으로 채우는 32비트 확장을 수행한다. (Unsigned 확장)

sb rt, offset(rs) / sh rt, offset(rs)

  • 가장 오른쪽에 있는 바이트 혹은 halfword를 offset(rs)에 저장한다.

문자열 복사 예시(String Copy Example)

  • C 코드
    • Null로 끝나는 문자열을 기준으로 한다.
void strcpy (char x[], char y[])
{
    int i;
    i = 0;
    while ((x[i]=y[i]) != '\0')
        i += 1;
}

  • x와 y의 주소는 $a0 과 $a1 에 저장된다.

  • i는 $s0 에 저장된다.

  • MIPS 코드

strcpy:
    addi $sp, $sp, -4       # adjust stack for 1 item
    sw   $s0, 0($sp)        # save $s0
    add  $s0, $zero, $zero  # i = 0
L1: add  $t1, $s0, $a1      # $t1 = &y[i]
    lbu  $t2, 0($t1)        # $t2 = y[i]
    add  $t3, $s0, $a0      # $t3 = &x[i]
    sb   $t2, 0($t3)        # x[i] = $t2 = y[i]
    beq  $t2, $zero, L2     # exit loop if y[i] == 0
    addi $s0, $s0, 1        # i = i + 1
    j    L1                 # next iteration of loop
L2: lw   $s0, 0($sp)        # restore saved $s0
    addi $sp, $sp, 4        # pop 1 item from stack
    jr   $ra                # and return
  • 참고로, 배열의 index를 찾기 위해 특정 값(예를 들어 4)를 곱해주는 과정이 없는데, 이는 문자열은 char형 배열이기 때문에, 1바이트로 이루어져 있기 때문이다.

32비트 상수(32-bit Constants)

  • 대부분의 상수들은 작다.
    • 이 말인즉슨, I 포맷의 16비트 즉각값(immediate)만으로도 충분하다는 것이다.
  • 가끔 32비트 상수들을 저장해야 할 경우
lui rt, constant

를 사용하면 된다.

  • load-upper-immediate : 16비트 상수를 rt의 왼쪽(윗쪽) 16비트에 복사하고, 오른쪽 16비트는 0으로 초기화한다.

  • ori 를 사용하여 오른쪽(아랫쪽) 16비트를 설정해주도록 한다.(addi 를 사용하지 말것!)
    2018-10-13 2 27 13

  • 예시를 보면, addi , ori 이 두 명령어가 무슨 차이가 있는가 의문이 들 수 있다. 하지만 떠올려보라, addi 는 I 포맷 명령어이다. 즉, 32비트 상수 값을 제대로 처리할 수 없다.

분기 주소 지정(Branch Addressing)

  • beq 나 bne 같은 명령들은 I 포맷 명령이기 때문에 다음 요소들에 대한 정보를 가지고 있어야 한다.
    iformat

  • 대부분의 분기의 목적지는 분기 명령 근처에 위치한다.

    • 앞 혹은 뒤 혹은 현재 명령의 PC 근처에 있다.
    • 반복문과 if 문을 컴파일 했을 때의 결과를 생각해보면 그러하다.

  • “PC에 상대적인 주소 지정(PC-Relative addressing)”

    • 주소의 기준을 PC로 삼는 것이다.
    • 목적지 주소(Target address) = PC + offset ×\times 4
    • PC를 기준으로 ±215\pm2^{15} word의 범위 안에서 분기할 수 있다. 이는 ±215\pm2^{15} 명령(instruction)이나 ±217\pm2^{17} 바이트(128kB)와 같다.
    • 참고로, 목적 주소를 알아내려고 할 때, PC는 이미 4만큼 증가한 상황일 것이다.
      • 결국 사실상 현재 분기 명령으로부터 목적지 주소(Target address) = (PC + 4) + offset ×\times 4이라고 볼 수 있다.

점프 주소 지정(Jump Addressing)

  • 점프(j , jal)의 목적지는 텍스트 부분 내에서 어디든 될 수 있다.

    • PC에서 멀리 떨어져 있을 수도 있다.
    • J 포맷을 사용하여 정확한 전체 주소를 명령(instruction)에 표현할 수 있다.
      j format

  • 주소를 저장할 때, 오른쪽으로 두 번 시프트 한 값이 저장되기 때문에, 결국 주소의 28비트를 기억하고 있다.

  • 의사 직접 점프 주소 지정((Pseudo) “Direct jump addressing”)

    • 두 번 시프트 한 값을 복원해야하기 때문에, 4를 곱해주어야 한다.
    • 목적지 주소 = 주소 ×\times 4
    • 2262^{26} word(= 2282^{28} 바이트) 범위 내에서 어떤 주소로든 점프할 수 있다.
    • 왜 갑자기 비트 수를 따지다가 바이트나 word가 나오는지 헷갈릴 수 있다.
      • 위의 비트는 말그대로 값이고, word나 바이트는 단위라고 생각하면 이해하기 쉽다.
      • 즉, J 포맷의 주소에 들어가는 것은 값이고, 그 값을 읽는 단위가 word나 바이트가 되는 것이다.

  • 그렇다면 28비트의 정보는 알 수 있는데, 나머지 최상위(Top) 4비트는 어떻게 처리하는가?

    • PC의 최상위(Top) 4비트를 사용한다고 한다. 그렇다면, 이 방식을 이용한 이동 범위는 다음 그림으로 나타낼 수 있겠다.
      2018-10-13 1 23 17

  • 위의 그림에서, PC 주변의 칠해져 있는 부분이 이동 가능한 범위이다. 즉, PC의 최상위 4비트가 고정된 범위 이내에서 자유로이 이동이 가능하다.

  • 점프 레지스터 명령(jr)

    • R 포맷 명령
    • 레지스터 안의 32비트를 이용하여 주소 전체를 이동할 수 있다.

목적지 주소 지정 예시(Target Addressing Example)

  • 6강의 반복문 코드를 참고하자.

    • Loop 라벨의 위치가 80000라고 하자.
      2018-10-13 1 47 37

  • 위의 그림에서, 화살표가 시작되는 bne 의 2는 오프셋(offset)이다. 즉, PC 상대적인 주소 지정을 사용한 것이다.

  • 또한, j 의 Loop의 주소를 살펴보면, 20000이다. 상기했듯, 주소를 오른쪽으로 2번 시프트하여 저장하기 때문에, 실제 주소를 구하려면 4를 곱해야 하고, 목적지 주소가 80000임을 알 수 있다.

멀리 분기(Branching Far Away)

  • 만약, 분기의 목적지가 16비트 오프셋으로 표현하기에 너무 멀리 있다면, 어셈블러가 코드를 재작성한다.
  • 예를 들어, beq $s0, $s1, L1 이라는 코드가 있는데, L1이 너무나도 멀리 있다면, 어셈블러는 이 코드를 다음과 같이 재작성하여 문제를 해결한다.
    bne $s0, $s1, L2
    j   L1
L2:       ...

주소 지정 모드 요약(Addressing Mode Summary)

  1. 즉각 주소 지정(Immediate addressing) : I 포맷 사용
  2. 레지스터 주소 지정(Register addressing) : R 포맷의 rs 사용.
  • JR
  1. 기본 주소 지정(Base addressing) : I 포맷에서 오프셋 사용
  • LW
  • SW
  1. PC 상대적인 주소 지정(PC-relative addressing) : I 포맷에서 오프셋 사용
  • BEQ
  • BNE
  1. 의사간접 주소 지정(Pseudodirect addressing) : J 포맷 사용
  • J
  • JAL

참고로, : 는 합친다는 뜻이다.

기계어 해독(Decoding Machine Language)

  • 00af8020hex\mathrm{00af8020}_{\mathrm{hex}} 는 무슨 뜻일까?
    • 이 기계어 표현은 어셈블리 언어로는 어떤 명령문일까?

해독하기 위해서 이를 먼저 32비트의 이진수로 변환하고, 그린카드를 참고해서 포맷에 맞추어 천천히 해결하면 된다. 참고로, opcode가 첫 6비트이기 때문에 이에 맞추어 해독하면 된다.

어셈블러 의사 지시(Assembler Pseudoinstructions)

  • 대부분 어셈블러 명령과 기계 명령은 일대일 관계이다.
  • 의사 지시(Pseudo-instruction) : 어셈블러의 상상속의 어떤 허구 명령이다. 우리가 진짜 코드를 작성하기 전에 짜보는 의사 코드와 비슷한 것이라고 보면 될 듯 하다.
  • 예를 들어, move $t0, $t1 은 add $t0, $zero, $t1 이 되고, blt $t0, $t1, L 은 
slt $at, $t0, $t1
bne $at, $zero, L

이 되는 식이다.

  • 이는 오직 어셈블리 언어에서만 해당한다.
    • 어셈블리 프로그래밍과 번역을 간결하게 만들어 준다.
  • $at 는 레지스터 1번으로써, 어셈블러 임시 변수이다.
  • 이는 bgt , bge , ble 에도 똑같이 적용된다.

번역과 실행(Translation and Startup)

C 프로그램들은 실행까지 다음 과정을 거친다.
tas

  • 컴파일러 ~ 어셈블러 사이의 과정에서 대부분의 컴파일러들은 오브젝트 모듈들을 바로 생성한다고 한다.
  • 오브젝트들이 생성된 시점 ~ 실행 가능한 기계어 프로그램이 만들어지는 시점까지를 정적 링킹이라고 한다.
profile
D0Lim
이전 포스트

컴퓨터 구조론 Lecture 2 - 4

다음 포스트

컴퓨터 구조론 Lecture 2 - 6

0개의 댓글