명령어(Instructions)[4]

32-bit Constants

• 대부분의 상수는 아주 작기 때문에 16-bit immediate면 충분하다.
• 가끔, 32-bit constant를 위해 레지스터의 상위 16비트에 상수를 넣는 lui를 제공한다. (load upper immediate)
  lui rt, constant
  : copies 16-bit constant to left 16 bits of rt
  : Clear right 16 bits of rt to 0
• 하위 16비트는 그 다음에 나오는 다른 명령으로 채운다.

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

A.

lui $s0, 61 // 61 = 0000 0000 0011 1101
ori $s0, $s0, 2304 // 2304 = 0000 1001 0000 0000

Branch Addressing

• branch instruction은 opcode, two register, target address를 지정한다.

• 대부분의 branch target은 branch 근처에 있다.

  op	rs	rt	constant or address
  6 bits	5 bits	5 bits	16 bits

• 이 방식이면, 모든 branch address가 16비트 필드 안에 들어가야 한다.
  하지만 이건 현실적으로 너무 작은 크기이다.
• 그래서, 어떤 레지스터를 지정해서 그 값을 분기 주소(branch address)와 더하도록 한다.
  PC = 레지스터 + 분기 주소(??)
• 이 방식은 프로그램 크기가 2^32까지 커지는 것을 허용한다

• 다음 문제는 그럼 어떤 레지스터를 사용하느냐 이다
• 조건부 branch는 보통 순환문이나 if문에서 사용되므로, 가까이 있는 명령오로 분기(branch)하는 경향이 있다.
• PC(program counter)는 현 명령어의 주소를 가지고 있으므로 branch address를 더할 레지스터로 PC를 선택하면 현 위치에서 ±2^15 워드 안에 있는 곳은 어디든 분기할 수 있다.
• 거의 모든 순환문과 if문의 분기 범위가 2^16워드 이내이므로 PC는 이상적인 선택이다.

• 이런 분기 주소지정 방식을 PC 상대 주소지정 (PC-relative addressing)이라고 한다.
• 보통 하드웨어는 PC를 일찍 증가시켜 다음 명령어를 가리키게 하는 것이 편리하다.
• 즉, 실제 MIPS 주소는 현재 명령어 주소(PC)를 기준으로 하는 것이 아니라 다음 명령어 주소(PC + 4)를 기준으로 하게 된다.

• Target address = PC + offset * 4

---

Jump Addressing

• Jump targets could be anywhere in text segment

  op	address
  6 bits	26 bits

• Target address = PC$_{31...28}$ : (address * 4)

---

Target Addressing Example

while(save[i] == k) i+= 1;의 컴파일 코드는

Loop : 
  sll $t1, $s3, 2 // temp reg $t1 = 4 * i
  add $t1, $t1, $s6 // $t1 = address of save[i]
  lw $t0, 0($t1) // temp reg $t0 = save[i]
  bne $t0, $s5, Exit // if save[i] != k, go to Exit
  addi $s3, $s3, 1 // i = i + 1
  j Loop // go to Loop
  
Exit : ...

이다. Loop의 주소가 80000번지라고 할 때, 위 프로그램에 해당하는 MIPS 기계어 코드를 구해보자.

• MIPS 명령어는 바이트 주소를 사용하므로, 이웃한 워드의 주소는 4씩 차이가 난다
• bne 명령은 다음 명령어 주소(80016)에 8을 더해서 목적지 주소를 구한다.
• 현재 명령어 기준의 상대적 위치(80012 + 12)나 목적지 주소 전체(80024)를 표현하는 대신,
  다음 명령어를 기준으로 한 상대적 위치가 명령어에 표시된다
• j 명령어는 Loop에 해당하는 주소 전체 (20000 * 4 = 80000)을 사용한다.

보면 beq, bne, j 등은 word 를 이용하기 때문에 x4를 하는데,
lw, sw는 바이트로 가기 때문에 x4를 따로 하지 않는 것 같다.

---

Branching Far Away

• branch target이 16비트로 나타낼 수 없는 먼 곳에 있다면, assembler rewrites the code

• 원래 코드

beq $s0, $s1, L1

• 수정된 코드

	bne $s0, $s1, L2
	j L1
L2 : ...

---

Addressing Mode Summary

수치 주소지정 Immediate addressing

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

레지스터 주소지정 Register addressing

• 피연산자는 레지스터이다.

베이스 또는 변위 주소지정 Base addressing

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

PC 상대 주소지정 PC-relative addressing

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

의사직접 주소지정 Pseudodirect addressing

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

---

동기화 Synchronization

• 두 프로세서가 메모리의 영역을 공유한다
  • P1 writes, then P2 reads
  • P2가 안전하게 읽을 수 있게 하기 위해 P1이 언제까지 쓰기를 마쳐야 하는지를 알려면, 태스크들이 동기화되어야 한다.
  • If P1 and P2 don't synchronize, data race

    data race(데이터 경쟁관계)
    : 이벤트가 일어나는 순서에 따라 프로그램의 결과가 달라질 수 있는 상황.

• Hardware support가 필요하다.
  • 메모리 주소에서 읽고(read) 쓰는(write) 것을 원자적으로(atomically) 처리할 능력을 가진 하드웨어 프리미티브가 있어야 한다.
  • 메모리가 읽고 쓰는 중간에 아무것도 끼어들 수 없어야 한다.

• Single instruction
  • atomic swap of register <-> memory
    레지스터의 값을 메모리 값과 교환한다.

    • 간단한 lock을 만들어 보자.
    • 이 lock은 0이면 사용 가능하고, 1이면 사용할 수 없음을 표시한다
    • 프로세서는 레지스터에 있는 값 1과 메모리에 있는 lock을 맞바꿈으로써 lock을 1로 만들고자 한다.
    • 만약 다른 프로세서가 이미 접근을 주장하였다면, 교환 명령어가 가져온 값은 1일 것이고, 아닌 경우에는 0일 것이다.
    • 후자의 경우, 그 값이 1로 바뀌어서 다른 프로세서에 있는 경쟁관계의 교환 명령이 0을 읽어가지 못하게 한다.

  • atomic pair of instructions
    한 쌍의 명령어.
    두 번째 명령어는 한 쌍의 명령어가 마치 원자적인 것처럼 실행되었는지를 나타내는 값을 반환한다.

Synchronization in MIPS

• Load linked (특수 적재 명령어) : ll rt, offset(rs)
• Store conditional (특수 저장 명령어) : sc rt, offset(rs)

• 이 명령어 쌍은 순차적으로 사용된다
• 만약, load linked에 의해 명시된 메모리 주소의 내용이
  같은 주소에 대한 store conditional 명령어가 실행되기 전에 바뀐다면
  store conditional 명령은 실패하게 된다.
• store conditional 는 레지스터 값을 메모리에 저장하고
  동시에 그 레지스터 값을 1로 바꾸게 되면 성공이고,
  만약 실패한다면 레지스터 값은 0이 된다.
• load linked는 초깃값을 반환하고
  store conditional은 성공할 때만 1을 반환하기 때문에
  다음 명령어 시퀀스는 $s1의 내용이 가리키는 메모리 주소에 대해 원자적 교환(atomic exchange)를 하게 된다

again : addi $t0, $zero, 1 // copy locked value
		ll 	      $t1, 0($s1) // load linked
        sc        $t0, 0($s1) // store conditional
        beq 	  $t0, $zero, again // branch if store fails
        add 	  $s4, $zero, $t1 // put load value in $s4

---

프로그램 번역과 실행 Translation and Startup

컴파일러 Compiler

• 컴파일러는 c 프로그램을 어셈블리 언어 프로그램으로 바꾼다

어셈블러 Assembler

• 어셈블리 언어는 상위 수준 소프트웨어와의 인터페이스이므로 원래는 없는 명령어를 어셈블러가 독자적으로 제공할 수도 있다.

• 의사명령어(pseudoinstructions)
  : 하드웨어가 지원하지 않는 어셈블리 언어 명령어를 마치 실제 있는 것처럼 어셈블러가 처리하는 명령어

• 예를 들면, $zero 레지스터는 항상 0의 값을 가지기 때문에
  한 레지스터의 값을 다른 레지스터로 복사하는 move 명령어를 구현하는 데 사용할 수 있다. MIPS에는 move 명령어가 없지만 MIPS 어셈블러는 이 명령을 받아들인다
  move $t0, $t1 -> add $t0, $zero, $t1

• 또한, MIPS는 blt(branch on less than)를 slt와 bne 두 개의 명령어로 바꾼다. 이 외에도 bgt, bge, ble 명령어가 이런 방식으로 처리된다.

• 결과적으로, 의사명령어(pseudoinstructions)는 실제 하드웨어 구현보다 훨씬 더 풍부한 어셈블리 언어 명령어 집합을 제공한다. 이 대가로, 어셈블러 전용으로 레지스터 하나($at)를 유보해 두어야 한다.

• Assembler (or compiler) translates program into machine instructions
  어셈블러는 어셈블리 언어 프로그램을 목적 파일(object file)로 바꾼다. 목적 파일에는 기계어 명령어, 데이터, 명령어를 메모리에 적절히 배치하기 위해 필요한 각종 정보들이 혼합되어 있다
  • Header : 목적 파일을 구성하는 각 부분의 크기나 위치 서술
  • Text segment : 기계어 코드가 들어 있다.
  • Static data segment : 프로그램 수명 동안 할당되는 데이터가 들어 있다. (Data allocated for the life of the program)
  • Relcation info : 프로그램이 메모리에 적재(load)될 때 절대 주소(absolute location)에 의존하는 명령어와 데이터 워드를 표시
  • Symbol table : 외부 참조같이 아직 정의되지 않고 남아 있는 레이블 저장

    심벌 테이블
    : 레이블 이름을 명령어가 기억된 메모리 워드의 주소와 짝지어 주는 테이블

  • Debug info : 각 모듈이 어떻게 번역되었는지에 대한 간단한 설명

링커 Linker

• 따로따로 어셈블된 기계어 프로그램을 하나로 연결해 주는 일을 한다.

1. Merges segments
2. Resolve labels (determine their addresses)
3. Patch location-dependent and external refs

in 교재
1. 코드와 데이터 모듈을 메모리에 심벌 형태로 올려 놓는다.
2. 데이터와 명령어 레이블의 주소를 결정한다
3. 외부 및 내부 참조를 해결한다

• 링커는 컴퓨터에서 실행될 수 있는 실행 파일(executable file)을 생성한다.

로더 Loader

• 운영체제는 디스크에 있는 실행 파일을 메모리에 넣고, 이를 시작시킨다

1. Read header to determine segment sizes
   • 실행 파일 헤더를 읽어서 텍스트와 데이터 세그먼트의 크기를 알아낸다.

2. Create virtual address space
   • 텍스트와 데이터가 들어갈 만한 주소 공간을 확보한다.

3. Copy text and initialized data into memory. Or set page table entries so they can be faulted in
   • 실행 파일의 명령어와 데이터를 메모리에 복사한다

4. Set up arguments on stack
   • 주 프로그램에 전달해야 할 인수가 있으면 이를 스택에 복사한다

5. Initalize registers (including $sp, $fp, $gp)
   • 레지스터를 초기화하고, 스텍 포인터는 사용 가능한 첫 주소를 가리키게 한다.

6. Jump to startup routine. Copy arguments to $a0, ... and calls main. When main returns, do exit syscall
   • 기동 루틴(start-up routine)으로 점프한다. 이 기동 루틴에서는 인수를 인수 레지스터에 넣고, 프로그램의 주 루틴을 호출한다. 주 프로그램에서 기동 루틴으로 복귀하면 exit 시스템 호출을 사용하여 프로그램을 종료시킨다

동적 링크 라이브러리 Dynamic Linking

• 실행 시에 프로그램과 링크되는 라이브러리 루틴
• 이 방식에서 프로그램 실행 전에는 라이브러리가 링크되지도 않고 적재되지도 않는다.
• 대신 프로그램과 라이브러리 루틴은 전역적 프로시저의 위치와 이름에 대한 정보를 추가로 가지고 있다.