상수 연산

• 16비트 상수를 32비트 상수로 바꿀 때 상위 16비트에 0을 삽입

1. andi(and immediate)
2. ori(or immediate)

2.7 판단을 위한 명령어

조건부 분기 명령어

1. beq(branch if equal)
   • register1과 register2의 값이 같으면 L1에 해당하는 문장으로 가라는 뜻

   beq register1, register2, L1

2. bne(branch if not equal)
   • register1과 register2의 값이 다르면 L1에 해당하는 문장으로 가라는 뜻

   bne register1, register2, L1

C 코드

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

MIPS코드

bne $s3, $s4, Else	# go to Else if i != j
add $s0, $s1, $s2	# f = g + h (skipped if i != j)
j	Exit			# go to Exit
Else: sub $s0, $s1, $s2	# f = g - h (skipped if i == j)
Exit: 

• j : 무조건 분기 명령어로 프로세서에게 항상 분기하라고 한다
  

순환문

C 언어

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

MIPS 언어

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

• sll $t1, $t3, 2
  - save[i]를 임시 레지스터로 가져오는 것
  - 바이트 주소를 사용하므로 인덱스 i에 4를 곱해서 save의 시작주소에 더해야 주소가 만들어짐
  - 2비트씩 왼쪽 자리 이동을 하면 4를 곱한 것과 같다
• Loop
  - 순환의 끝에서 처음 명령어로 되돌아갈 수있도록 하는 레이블
• lw $t0, 0($t1)
  - 이 주소를 이용해 save[i]를 임시 레지스터에 넣음

기본 블록

• 분기 명령어로 끝나는 명령어 시퀀스
• 분기 명령을 포함하지 않으며 분기 목적지나 분기 레이블도 없는 시퀀스

비교 명령어

1. slt(set on less than)
   • 첫 번째 레지스터 값이 두 번째 레지스터의 값보다 작으면 세 번째 레지스터 값을 1, 크거나 같으면 0으로 하는 명령어

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

2. slti
   • 상수 피연산자를 갖는 slt 명령어

   slti $t0, $s2, 10	# $t0 = 1 if $s2 < 10

3. sltu(set on less than unsigned), sltiu(set on less than immediate unsigned)
   • 부호 없는 정수 비교
   • x < y를 할 시, x가 y보다 작은지 뿐만 아니라 x가 음수인지도 검사할 수 있다

Case/Switch 문장

1. 점프 주소 테이블(jump address table) or 점프 테이블(jump table)
   • 인덱스를 계산해서 해당 루틴으로 점프할 수 있도록 도와주는 프로그램
   • 프로그램상의 레이블에 해당하는 주소를 저장하고 있는 배열
   • 점프 테이블에서 적당한 주소를 레지스터에 적재한 후 이 주소를 사요하여 점프
   • jr(jump register) 명령어

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

프로시저

1. 프로시저(procedure) 혹은 함수
   - 이해하기 쉽고 재사용이 가능하도록 프로그램을 구조화하는 방법 중 하나
   - 프로그래머가 한 번에 한 부분씩 집중해서 처리할 수 있도록 도와줌

   소프트웨어에서 추상화를 구현하는 방법 중 하나

2. 인수
   • 프로시저에 값을 보내고, 결과를 받아 오는 일

프로시저 순서

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

MIPS 소프트웨어와 프로시저

1. 레지스터 할당
   • $a0 ~ $a3 : 전달할 인수를 가지고 있는 인수 레지스터 4개
   • $v0 ~ $v1 : 반환되는 값을 갖게 되는 값 레지스터 2개
   • $ra : 호출한 곳으로 되돌아가기 위한 복귀 주소를 가지고 있는 레지스터 1개
2. 명령어 제공
   • jal(jump-and link) : 지정된 주소로 점프하면서 동시에 다음 명령어의 주소를 $ra 레지스터에 저장

   jal ProcedureAddress

한 프로시저가 여러 곳에서 호출될 수 있으므로 복귀 주소는 꼭 필요

명령어 주소 레지스터

• 명령어 주소 레지스터(instruction address register) 혹은 프로그램 카운터(program counter) 혹은 PC 라고 부른다
• 현재 실행 중인 명령어의 주소를 기억
• jal 명령은 프로시저에서 복귀할 때 다음 명령어부터 실행하도록 PC + 4를 레지스터 $ra에 저장한다

스택

• 레지스터 스필링에 이상적인 자료구조
• 나중에 들어간 것이 먼저 나오는 구조
• 다음 프로시저가 스필할 레지스터를 저장할 장소나 레지스터의 옛날 값이 저장된 장소를 표시하기 위해 최근에 할당된 주소를 가리키는 포인터가 필요
• 데이터를 넣는 작업을 push, 데이터를 꺼내는 작업을 pop이라고 함

1. 스택 포인터(stack pointer)
   • 레지스터 값 하나가 스택에 저장되거나 스택에서 복구될 때마다 한 워드씩 조정
   • $sp
   • 높은 주소에서 낮은 주소로 성장하기 때문에, 푸시를 하면 스택 포인터 값을 감소시키고, 스택에서 팝할 때는 스택 포인터를 증가시킴

C 코드

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

MIPS 언어

leaf_example:
 addi	$sp, $sp, -12	# adjust stack to make room for 3 items
 sw		$t1, 8($sp)		# save register $t1 for use afterwards
 sw		$t0, 4($sp)		# save register $t2 for use afterwards
 sw		$s0, 0($s0)		# save register $s0 for use afterwards
 add	$t0, $a0, $a1	# register $t0 contains g + h
 add	$t1, $a2, $a3	# register $t1 contains i + j
 sub	$s0, $t0, $t1	# f = $t0 - $t1, which is (g + h) - (i + j)
 add	$v0, $s0, $zero	# returns f ($v0 = $s0 + 0)
 lw		$s0, 0($sp)		# restore register $s0 for caller
 lw		$t0, 4($sp)		# restore register $t0 for caller
 lw		$t1, 8($sp)		# restore register $t1 for caller
 addi 	$sp, $sp, 12	# adjust stack to delete 3 items
 jr		$ra				$ jump back to calling routine

• addi $sp, $sp, -12 : 스택에 세 워드를 저장할 자리를 만든 후 값을 저장
• add $v0, $s0, $zero : f를 결과값 레지스터에 복사
• addi $sp, $sp, 12 : 저장해 두었던 값을 스택에서 꺼내 레지스터를 원상 복구
• jr $ra : 복귀 주소를 사용하는 점프 명령

• 임시 레지스터 값도 저장했다가 원상 복구해야 한다고 가정했지만, 사용하지도 않는 레지스터 값을 쓸데없이 저장했다가 복구하는 일이 생길 수 있음

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

중첩된 프로시저

• 말단 프로시저 : 다른 프로시저를 호출하지 않는 프로시저
• 중첩된 프로시저의 경우 레지스터 간의 충돌이 있을 수 있다

1. 값이 보존되어야 하는 모든 레지스터를 스택에 넣는다
   • 스택 포인터 $sp는 스택에 저장되는 레지스터 개수에 맞추어 조정된다
   • 복귀한 후에는 메모리에서 값을 꺼내 레지스터를 원상 복구하고 이에 맞추어 스택 포인터를 다시 조정한다

저장 변수 유형

• 기억된 내용을 어떻게 해석하는 가는 데이터형(type)과 저장 유형(strage class)에 따라 달라진다

1. 저장 유형
   • 자동 변수 : 프로시저 내에서만 정의
   • 정적 변수 : 프로시저로 들어간 후나 프로시저에서 빠져나온 후에도 계속 존재 (모든 프로시저 외부에서 선언된 변수, static, 전역 포인터($gp))

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

• 프로시저 프레임(procedure frame) or 액티베이션 레코드(activation record)
  : 저장된 레지스터와 지역변수를 가지고 있는 스택 영역
  

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

• 스택은 최상위 주소부터 시작해서 아래쪽으로 자란다.
• 최하위 주소 부분은 사용이 유보
• 텍스트 세그먼트 : 최하위 주소의 다음 부분으로 MIPS 기계어 코드가 들어가는 부분
• 정적 데이터 세그먼트 : 코드 위쪽 부분으로 상수와 기타 정적 변수들이 들어가는 부분
• 힙 : 링크드 리스트와 같이 크기가 가변적인 자료구조를 위한 세그먼트
• 스택과 힙은 서로 마주보면서 자라도록 할당

힙과 함수

• malloc() : 힙에 공간을 할당한 후 이 공간을 가리키는 포인터를 결과값으로 보내줌
• free() : 포인터가 가리키는 힙 공간을 반납하는데 이를 잊어버리면 메모리 누출이 발생하고, 일찍 반납하면 매달린 포인터가 발생

MIPS 어셈블리 언어의 레지스터 사용 관례

자주 생기는 일을 빠르게 : 인자 레지스터 4개와 리턴값 레지스터 2개, 저장 레지스터 8개, 임시 레지스터 10개면 대부분의 프로시저를 충족시키기 때문에 메모리에 갈 일이 없어 속도가 빨라진다

2.9 문자와 문자열

이진수와 ASCII

10억은 1,000,000,000이기 때문에 10개의 ASCII 자릿수가 필요하다
각각이 8비트 길이이므로 메모리는 $(10 * 8) / 32$

바이트 전송 명령어

1. lb(load byte)
   : 메모리에서 한 바이트를 읽어서 레지스터의 오른쪽 8비트에 채우는 명령어
2. sb(store byte)
   : 레지스터의 오른쪽 8비트를 메모리로 보내는 명령어

lb $t0, 0($sp)	# Read byte from source
sb $t0, 0($gp)	# Write byte to destination

가변 길이의 문자열 표현

1. 문자열의 맨 앞에 길이를 표시하는 방법 (Java)
2. 같이 사용되는 변수에 그 길이를 표시하는 방법
3. 마지막에 문자열의 끝을 표시하는 특수 문자를 두는 방법 (C)

문자열 복사 프로시저

C언어

void strcpy (char x[], char y[])
{
	int i;
    
    i = 0;
    while ((x[i] = y[i]) != '\0')	/*copy and test byte*/
    i += 1;
}

MIPS

strcpy :
	add	$sp, $sp, -4	# adjust stack for 1 more item
    sw	$s0, 4($sp)		# save $s0
    add	$s0, $zero, $zero	# i = 0 + 0
L1 : 
	add	$t1, $s0, $a1	# address of y[i] in $t1
	lbu	$t2, 0($t1)		# $t2 = y[i]
    add	$t3, $s0, $a0	# address of x[i] in $t3
    sb	$t2, 0($t3)		# x[i] = y[i]
    beq	$t2, $zero, L2	# if y[i] == 0, go to L2
    addi	$s0, $s0, 1	# i = i + 1
    j	L1				# go to L1
L2 :
	lw	$s0, 0($sp)		# y[i] == 0 : end of string:
    addi	$sp, $sp, 4	# pop 1 word off stack
    jr	$ra				# return

• lbu $t2, 0($t1) : y는 워드 배열이 아니고 바이트 배열이므로 i에 4를 곱할 필요가 없다. lb는 바이트를 부호 확장해서 레지스터에 넣는 명령어이고, lbu는 바이트를 0 확장해서 레지스터에 넣는 명령어다.
• strcpy : 말단 프로시저이므로 컴파일러가 i를 임시 레지스터에 할당했으면 이를 저장하고 복구하는 일을 피할 수 있다

Java의 문자와 문자열

• 유니코드(Unicode) : 인간이 사용하는 거의 모든 언어의 자모를 수용할 수 있는 범용 인코딩
• Java는 포괄성을 위해 문자를 유니코드 즉, 16비트(하프워드)로 표현한다

1. lh(load half)
   : 메모리에서 16비트를 읽어와서 레지스터의 우측 16비트에 넣는다. 부호 있는 수로 취급하여 상위 16비트를 부호 확장하여 채운다
2. lhu(load halfword unsigned)
   : 부호없는 수를 적재
3. sh(store half)
   : 레지스터의 우측 16비트를 메모리에 쓴다

lhu	$t0, 0($sp)	# Read halfword (16 bits) from source
sh	$t0, 0($gp) # Write halfword (16 bits) to destination

바이트 할당

1. MIPS : 스택에 저장될 때 어떤 종류든 4바이트 할당
2. C : 한 워드에 4바이트씩 묶어서 넣는다
3. Java : 한 워드에 두 하프워드씩 묶어서 넣는다

데이터의 종류는 데이터를 처리하는 프로그램에 인코딩되어 있다

2.10 32비트 수치와 주소를 위한 MIPS의 주소지정 방식

32비트 수치 피연산자

• 대부분 16비트 필드면 충분하지만 때에 따라서는 더 큰 상수가 필요한 경우가 있다
• lui(load upper immediate) : 레지스터의 상위 16비트에 상수를 넣고 하위 16비트는 그 다음에 나오는 다른 명령으로 채운다

목표 레지스터 $s0

$s0 = 0000 0000 0011 1101 0000 1101 0000 0000

1. lui를 이용해서 상위 16비트를 채운다

lui	$s0, 61	# 61 decimal = 0000 0000 0011 1101two

이후 $s0

$s0 = 0000 0000 0011 1101 0000 0000 0000 0000

2. 하위 16비트 채운다

ori	$s0, $s0, 2304	# 2304 decimal = 0000 1001 0000 0000

이후 $s0

$s0 = 0000 0000 0011 1101 0000 1001 0000 0000

• addi 명령어는 16비트 상수 필드의 MSB를 상위 16비트에 복사하여 32비트를 만드는 부호 확장을 이용하지만 ori 명령어는 상위 16비트를 0으로 채운 후 연산한다

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

1. PC 상대 주소 지정(PC relative addressing)
   R 타입의 경우 모든 주소가 16비트 필드에 들어가야 하기 때문에 레지스터를 지정해서 그 값을 분기 주소와 더하는 방법으로 주소의 크기 제한을 극복한다

   	PC = 레지스터 + 분기주소

   SPEC 벤치마크에서 조건부 분기의 절반가량이 16개 명령어 이상 떨어지지 않은 위치로 분기하므로 분기 주소를 더할 레지스터로 PC를 선택하면 현 위치에서 215워드 이내 떨어진 곳은 어디든지 분기할 수 있다

   자주 생기는 일을 빠르게
   : 가까이 있는 명령어들의 주소 지정을 빠르게

2. J 타입
   프로시저들은 가까이 붙어 있을 이유가 없으므로 다른 주소 지정 방식을 사용

분기할 거리를 바이트 단위가 아니라 워드 단위로 나타내면 더 먼 거리까지 분기 가능

기계어에서의 분기 변위

MIPS

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

기계어 코드

• 바이트 주소를 사용하므로 이웃한 워드는 4 바이트씩 차이가 난다
• bne $t0, $s5, Exit : 다음 명령어 주소(80016)에 8을 더해서 목적지 주소를 구한다
• j Loop : Loop에 해당하는 주소 전체($20000 \times 4 = 80000$)를 사용

아주 먼 거리로의 분기

레지스터 $s0가 레지스터 $s1과 같으면 분기하는 코드

beq	$s0, $s1, L1

L1이 아주 멀어도 분기가 가능한 코드

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

MIPS 주소지정 방식 요약

주소지정 방식(addressing mode) : 여러 형태의 주소 표현

1. 수치(immediate) 주소 지정 : 피연산자는 명령어 내에 있는 상수
2. 레지스터 주소 지정 : 피연산자는 레지스터
3. 베이스 또는 변위 주소지정 : 피연산자는 메모리 내용이며, 메모리 주소는 레지스터와 명령어 내의 상수를 더해서 구한다
4. PC 상대 주소지정 : PC값과 명령어 내의 상수의 합을 더해서 구한다
5. 의사직접 주소지정 : 명령어 내의 26비트를 PC의 상위 비트들과 연접하여 점프 주소를 구한다

기계어의 해독

• 코어 덤프(core dump)를 읽을 때 기계어로부터 원래의 어셈블리 언어를 추출해야 한다

기계어

00af 8020hex

16진수 변환

0000 0000 1010 1111 1000 0000 0010 0000

비트 31-29 : 000
비트 28-26 : 000
=> R형식 명령어

op     rs    rt    rd    shamt funct   
000000 00101 01111 10000 00000 100000

비트 5-3 : 100
비트 2-0 : 000
=> add 명령어

MIPS

add	$s0, $a1, $t7

2.11 병렬성과 명령어 : 동기화

태스크 동기화

• 협력 : 다른 태스크들이 읽어야 하는 새로운 값을 어떤 태스크가 쓰고 있음
• 태스크 동기화 : 태스크가 언제까지 쓰기를 마쳐야 다른 태스크들이 안전하게 읽을 수 있는지 판단하기 위해 필요하며 동기화 되어 있지 않을 경우 데이터 경쟁관계가 될 수 있다

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

동기화 매커니즘

1. lock과 unlock

   • 단 하나의 프로세서만이 작업할 수 있는 영역 생성 (상호배제(muture exclusion))
   • 더 복잡한 동기화 매커니즘을 구현

2. 하드웨어 프리미티브

   • 원자적으로 처리할 능력
   • 메모리에서 읽고 쓰는 중간에 아무것도 끼어들 수 없음

   1) 원자적 교환(atomic exchange or atomic swap)

   • 레지스터 값을 메모리 값과 서로 맞바꿈

     lock은 0이면 사용 가능하고 1이면 사용할 수 없다는 것을 가정.
     레지스터에 있는 값 1과 lock에 해당하는 메모리 내용을 맞바꿔 lock을 1로 만들고자 함
     이미 접근을 주장하였다면 교환 명령어가 가져온 값은 1일 것이며 그렇지 않은 경우에는 0

   • 동시에 교환할 경우 둘 중 한 프로세서가 교환을 먼저 수행해서 0을 가져오면 나머지 프로세스는 1을 읽게 됨

   2) 명령어 두개

   • 두 번째 명령어는 이 한 쌍의 명령어가 원자적인 것처럼 실행되었는지를 나타내는 값을 반환
   • load linked와 store conditional
   • 명령어는 순차적으로 사용
   • load linked 명령어에 의해 명시된 메모리 주소의 내용이 같은 주소에 대한 store conditional 명령어가 실행되기 전에 바뀐다면 store conditional 명령은 실패
   • store conditional 명령어는 레지스터 값을 메모리에 저장하고, 성공하면 레지스터 값을 1로, 실패히면 레지스터 값을 0으로 바꾸는 일을 함

   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(0)
       add		$s4, $zero, $t1	# put load value in $s4

   • ll 명령어와 sc 명령어 사이에 어떤 프로세스가 끼어들어서 메모리 값을 수정하면, sc는 $t0에 0을 반환하기 때문에 again으로 가서 코드 시퀀스를 다시 실행
   • 멀티프로세서 동기화를 위해 제시되었지만 단일프로세서에서도 동작한다

2.12 프로그램 번역과 실행

번역 계층

1. 컴파일러

   • C 프로그램을 어셈블리 언어 프로그램으로 바꿈
   • 어셈블리 언어 프로그램 : 컴퓨터가 이해할 수 있는 명령의 기호 형태

2. 어셈블러

   • 상위 수준 소프트웨어와의 인터페이스

   • 원래는 없는 명령어를 어셈블러가 독자적으로 제공

   • 의사명령어 : 하드웨어로 구현되어 있지 않더라도 어셈블러가 알아서 처리하여 번역과 프로그래밍을 간편하게 하는 명령어로 실제의 하드웨어 구현보다 훨씬 더 풍부한 어셈블리 언어 명령어 집합을 제공

     $zero를 레지스터의 내용을 다른 레지스터로 복사하는 move 명령어를 구현하는데 사용할 수 있음
     blt 명령어를 slt와 bne 2개의 명령어로 바꿀 수있음 (bgt, bge, ble도 가능)

   • 어셈블리 언어 프로그램을 목적 파일(object file)로 바꾼다

     목적 파일 : 기계어 명령어, 데이터, 명령어를 메모리에 적절하게 배치하기 위해 필요한 각종 정보들이 혼합
     - 목적 파일 헤더 : 목적 파일을 구성하는 각 부분의 크기와 위치를 서술
     - 텍스트 세그먼트 : 기계어 코드가 들어 있음
     - 정적 데이터 세그먼트 : 프로그램 수명 동안 할당되는 데이터가 들어 있다 (정적 데이터와 동적 데이터를 사용할 수 있게 함)
     - 재배치 정보 : 프로그램이 메모리에 적재될 때 절대 주소를 사용해야 하는 명령어와 데이터 워드 표시
     - 심벌 테이블 : 외부 참조같이 아직 정의되지 않고 남아 있는 레이블들을 저장
     - 디버깅 정보 : 각 모듈이 어떻게 번역되었는지에 대한 간단한 설명

   • 분기나 데이터 전송 명령에서 사용된 모든 레이블을 심벌 테이블(symbol table)에 저장

3. 링커

   • 프로시저가 한 줄이라도 고치면 전체 프로그램을 다시 컴파일하고 어셈블해야하는 방법이 아닌 각 프로시저를 따로따로 컴파일, 어셈블하는 시스템 프로그램

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

   • 각 목적 모듈의 재배치 정보와 심벌 테이블을 이용해서 미정의 레이블의 주소를 결정
   • 구주소를 신주소로 바꾸는 일을 하므로 에디터와 유사한 점이 있어 링크에디터, 즉 링커라고 부름
   • 모듈을 메모리에 적재할 때 절대 참조(실제 메모리 주소)는 모두 실제 위치에 해당하는 값으로 재설정
   • 실행 파일(execution file)을 생성

     실행 파일 : 목적 파일과 같은 형식을 갖지만 미해결된 참조가 없는 파일

4. 로더

   • 디스크에 실행 파일이 준비되면 운영체제가 디스크에서 실행 파일을 읽어서 메모리에 적재하고 실행시키는 시스템 프로그램

     1. 실행 파일 헤더를 읽어서 텍스트와 세그먼트의 크기를 알아낸다
     2. 텍스트와 데이터가 들어갈 만한 주소 공간을 확보 한다
     3. 실행 파일의 명령어와 데이터를 메모리에 복사한다
     4. 주 프로그램에 전달해야 할 인수가 있으면 이를 스택에 복사한다
     5. 레지스터를 초기화하고, 스택 포인터는 사용 가능한 첫 주소를 가리키게 한다
     6. 가동 루틴으로 점프한다

동적 링크 라이브러리

전통적인 방법

• 프로그램 실행 전에 라이브러리를 링크
• 라이브러리 루틴이 실행 코드의 일부가 되고, 호출이 실제 실행되지 않더라도 모두 적재해야 한다

DLL

• 동적 링크 라이브러리 (dynamically linked library, DLL)
• 프로그램 실행 전에는 라이브러리가 링크되지도 않고 적재되지도 않는다
• 전역 프로시저의 위치와 이름에 대한 정보를 추가로 가지고 있음

1. 초기의 DLL
   • 로더 : 동적 링커를 실행
   • 동적 링커 : 파일에 저장된 추가 정보를 이용해서 적절한 라이브러리를 찾고 모든 외부 참조를 갱신
   • 호출될 가능성이 있는 모든 라이브러리 루틴을 링크
2. 지연 프로시저 링키지형의 DLL
   • 모든 루틴을 실제로 호출된 후에 링크
   • 간접 접근 기법을 사용

     프로그램 끝에 있는 더미 루틴들을 호출하는 전역 루틴에서 시작
     전역 루틴 하나당 더미 엔트리가 존재하고, 더미 엔트리에는 간접 점프가 존재
     1) 루틴 처음 호출
     - 더미 엔트리를 호출하고 간접 점프를 따라간다
     - 원하는 라이브러리 루틴을 표시하기 위해 레지스터에 숫자를 넣고 동적 링커/로더로 점프하는 코드를 가리킨다
     - 원하는 루틴을 찾아서 재사상하고, 이 루틴을 가리키도록 간접 점프 위치에 있는 주소를 바꾼다
     - 그 주소로 점프 후, 루틴의 실행이 끝나면 원래 호출한 위치로 돌아온다
     2) 이후 호출
     - 추가로 돌아다니는 일 없이 해당 루틴으로 바로 간접점프

   • 추가 공간을 필요로 하지만 전체 라이브러리를 복사하거나 링크할 필요가 없음

Java 프로그램의 실행

1. Compiler
   • 인터프리트하기 쉬운 Java 바이트 코드 명령어 집합으로 컴파일
2. JVM(Java virtual machine)
   • 소프트웨어 인터프리터

     인터프리터
     : 명령어 집합 구조를 시뮬레이션하는 프로그램

   • Java 바이트 코드를 실행
   • 실행 중에 주소를 찾아서 별도의 어셈블리 단계가 필요 없다
   • 높은 이식성과 낮은 성능
3. JIT(just in time)
   • 이식성을 훼손하지 않으면서 실행 속도를 개선하기 위해 프로그램이 실행되는 도중에 번역을 하는 컴파일러
   • 실행 중인 프로그램의 특성을 파악해서 많이 사용되는 메소드를 찾아내서 기계어로 번역

2.13 종합 : C 정렬 프로그램

프로시저 swap

swap : 메모리 내의 두 값을 단순히 맞바꾸는 것

C언어

void swap(int v[], int k)
{
	int temp;
    temp = v[k];
    v[k] = v[k + 1];
    v[k + 1] = temp;
}

v, k : $a0, $a1
temp : $t0 (swap은 말단 프로시저이므로)

MIPS

sll	$t1, $a1, 2		# reg $t1 = k * 4
add	$t1, $a0, $a1	# reg $t1 = v + (k * 4)
lw	$t0, 0($t1)		# reg $t0 (temp) = v[k]
lw	$t2, 4($t1)		# reg $t2 = v[k + 1]
					# refers to next element of v
lw	$t2, 0($t1)		# v[k] = reg $t2
lw	$t0, 4($t1)		# v[k + 1] = reg $t0 (temp)

sll $t1, $a1, 2 : 각 워드는 실제로 4 바이트씩 떨어져 있음

프로시저 sort

sort : 버블정렬 방법으로 정수 배열을 정렬하는 swap 프로시저를 호출하는 프로그램

C언어

void sort(int v[], int n)
{
	int i, j;
    for (i = 0; i < n; i+= 1)
    	for (j = i - 1; j >= 0 && v[j] > v[j + 1]; j+= 1) {
        	swap(v, j);
        }
}

v, n : $a0, $a1
i, j : $s0, $s1

MIPS

sort: 
 addi	$sp, $sp, -20	# make room on stack for 5 registers
 sw		$ra, 16($sp)	# save $ra on stack
 sw		$s3, 12($sp)	# save $s3 on stack
 sw		$s2, 8($sp)		# save $s2 on stack
 sw		$s1, 4($sp)		# save $s1 on stack
 sw		$s0, 0($sp)		# save $s0 on stack
 
 move	$s2, $a0		# copy parameter $a0 into $s2 (save $a0)
 move	$s3, $a1		# copy parameter $a1 into $s3 (save $a1)
 
 move	$s0, $zero		# i = 0
for1tst :
 slt	$t0, $s0, $s3	# reg $t0 = 0 if $s0 >= $s3 (i >= n)
 beq	$t0, $zero, exit1	# go to exit1 if $s0 >= $s3 (i >= n)
 
 addi	$s1, $s0, -1	# j = i - 1
for2tst :
 slti	$t0, $s1, 0		# reg $t0 = 1 if $s1 < 0 (j < 0)
 bne 	$t0, $zero, exit2	# go to exit2 if $s1 < 0 (j < 0)
 sll	$t1, $s1, 2		# reg $t1 = j *  4
 add	$t2, $st, $t1	# reg $t2 = v + (j * 4)
 lw		$t3, 0($t2)		# reg $t3 = v[j]
 lw		$t4, 4($t2)		# reg $t4 = v[j + 1]
 slt	$t0, $t4, $t3	# reg $t0 = 0 if $t4 <= $t3
 beq	$t0, $zero, exit2	# go to exit2 if $t4 <= $t3
 
 move	$a0, $s2		# 1st parameter of swap is v (old $a0)
 move 	$a1, $s1		# 2nd parameter of swap is j
 jal	swap			# swap code
 
 addi	$s1, $s1, -1	# j -= 1
 j		for2tst			# jump to test of inner loop
 
exit2 :
 addi	$s0, $s0, 1		# i += 1
 j		for1tst			# jump to test of outer loop
 
exit1 :
 lw		$s0, 0($sp)		# restore $s0 from stack
 lw		$s1, 4($sp)		# restore $s1 from stack
 lw		$s2, 8($sp)		# restore $s2 from stack
 lw		$s3, 12($sp)	# restore $s3 from stack
 lw		$ra, 16($sp)	# restore $ra from stack
 addi	$sp, $sp, 20	# restore stack pointer
 
 jr		$ra				# return to calling routine

프로그램 성능

• 프로그램 성능에 대한 정확한 척도는 오로지 실행시간뿐임

• 프로그램 언어, 컴파일 대 인터프리팅, 알고리즘이 실행 시간에 영향을 끼친다
• 프로그램 언어 : 최적화되지 않은 C 프로그램이 인터프린트된 Java 코드보다 8.3배 빠르다
• 컴파일 : JIT 컴파일러 사용 시 Java 프로그램이 최적화되지 않은 C 프로그램보다 2.1배 빠르고, 최고로 최적화된 C 코드보다는 겨우 1.13배 정도만 느리다
• 알고리즘 : 인터프린팅 Java로 구현된 퀵정렬과 최고로 최적화하여 컴파일한 C 코드 버블정렬을 비교하면 퀵정렬이 50배 정도 빠르다

2.14 배열과 포인터

배열을 사용한 clear

C언어

clear1(int array[], int size)
{
	int i;
    for (i = 0; i < size; i+=1)
    	array[i] = 0;
}

array, size : $a0, $a1
i : $t0

MIPS

 move $t0, $zero	# i = 0 (register $t0 = 0)
loop1 :
 sll $t1, $t0, 2	# $t1 = i * 4
 add $t2, $a0, $t1	# $t2 = address of array[i]
 sw	 $zero, 0($t2)	# array[i] = 0
 addi	$t0, $t0, 1	# i = i + 1
 slt	$t3, $t0, $al	# $t3 = (i < size)
 bne	$t3, $zero, loop1	# if (i < size) go to loop1

포인터를 사용한 clear

clear2(int *array, int size)
{
	int *p;
    for (p = &array[0]; p < &array[size]; p = p + 1)
    	*p = 0;
}

array, size : $a0, $a1
p : $t0

MIPS

 move	$t0, $a0	# p = address of array[0]
 sll	$t1, $a1, 2	# $t1 = size * 4
 add	$t2, $a0, $t1	# $t2 = address of array[size]
loop2 :
 sw		$zero, 0($t0)	# Memory[p] = 0
 addi	$t0, $t0, 4		# p = p + 4
 slt	$t3, $t0, $t2	# $t3 = (p < &array[size])
 bne	$t3, $zero, loop2	# if (p < &array[size]) go to loop2

2.16 실례 : ARMv7(32비트) 명령어

• MIPS는 레지스터가 더 많고 ARM은 주소지정 방식이 더 많다

주소지정 방식

• ARM에는 상수 0을 갖고 있는 레지스터가 없다
• 레지스터를 원하는 만큼 자리이동한 후 다른 레지스터 값에 더하여 주소를 만든 다음, 이 주소를 이용하여 레지스터 값을 바꾸는 주소지정 방식이용

비교 및 조건부 분기

• 프로그램 상태 워드에 저장되는 4개의 전통적인 조건 코드 negative, zero, carry, overflow 비트 사용
• 조건부 분기 명령어로 조건 코드를 검사해서 모든 부호없는 비교와 부호있는 비교를 수행
• 모든 명령어가 조건부로 실행
• 실행 여부는 지정된 조건코드 값에 따라 결정
• 모든 명령어의 첫 4비트 필드는 실행 여부를 결정하기 위해서 검사할 조건코드들을 지정하여 이 명령어가 nop(no operation) 명령어로 작동할지 아니면 실제 명령어로 작동할 지 결정함
• 레지스터 필드가 짧고 레지스터 개수가 MIPS의 절반이다

1. CMP
   • 한 피연산자에서 다른 피연산자를 뺀 후 그 차이에 따라 조건 코드를 설정
2. CMN(Compare Negative)
   • 한 핀연산자에다 다른 피연산자를 더하여 그 결과로 조건 코드를 설정
3. TST
   • 두 피연산자에 논리적 AND 연산을 수행하여 overflow를 제외한 모든 조건 코드를 설정
4. TEQ
   • 두 피연산자에 exclusive OR 연산을 하여 overflow를 제외한 나머지 조건 코드를 설정

ARM의 고유한 특징

• 12비트 수치 필드 : 하위 8비트 앞에 0을 24개 붙여 32비트 수로 만든 다음, 이 필드의 왼쪽 4비트에 2를 곱한 값에 해당되는 비트만큼 오른쪽으로 회전

실례 : ARMv8(64비트) 명령어

ARMv7과의 비교

• 조건부 실행 필드가 없어졌다
• 수치 필드를 단순한 12비트 상수로 변경
• 다중 적재(load multiple) 명령어와 다중 저장(store multiple) 명령어가 없어졌다
• PC는 일반 레지스터가 아니다
• 범용 레지스터를 32개로 늘림
• 항상 0을 갖는 레지스터 존재
• 주소지정 방식이 모든 워드 크기에 대해 동작
• 나눗셈 명령어 추가

실례 : RISC-V 명령어

• International이라는 기구에서 관리하는 개방형 구조
• 32비트 버전과 64비트 버전 존재

RISC-V와 MIPS의 공통점

• 모두 32비트
• 32개의 범용 레지스터
• 항상 0을 갖는 레지스터
• 메모리 접근은 적재와 저장 명령어를 통해서만 가능
• 다중 레지스터에 접근하거나 저장하는 명령어 없음
• 레지스터가 0 혹은 0이 아니면 분기하라는 명령어 존재
• 주소지정 방식이 모든 데이터 크기에 적용

RISC-V와 MIPS의 차이점

분기명령어의 차이

• RISC-V : 두 레지스터를 비교하는 분기 명령어 존재
• MIPS : 비교 결과가 참이냐 아니냐에 따라 레지스터를 0 혹은 1로 설정하는 비교 명령어 존재

실례 : x86 명령어

x86 레지스터와 데이터 주소지정 방식

• 80386 : 모든 16비트 레지스터를 32비트로 확장 (범용 레지스터)
• 피연산자 하나는 근원지이면서 동시에 목적지
• 피연산자 중 하나가 메모리에 상주 가능

  메모리 피연산자
  : 모든 주소지정 방식을 사용할 수 있지만, 특정 주소 지정 방식에서 사용할 수 있는 레지스터에 제한 있음

x86의 정수 연산

• 80386 : 8비트(바이트), 16비트(워드), 32비트(더블 워드) 지원
• 대부분의 프로그램이 16비트나 32비트 데이터 중 한 가지를 주로 사용하는 경향이 있으므로 코드 세그먼트 레지스터의 비트 하나를 이용하여 디폴트 데이터 크기를 선언
• 디폴트 크기가 아닌 데이터를 사용할 시 8비트짜리 접두사를 붙여 사용

  접두사

  1. 디폴트가 아닌 다른 세그먼트 레지스터의 사용
  2. 동기화 지원을 위한 버스 잠금
  3. ECX 레지스터가 0이 될 때까지 명령어의 반복 실행 (가변 개수의 데이터 복사)

정수 명령

1. move, push, pop을 포함하는 데이터 전송 명령
2. 검사와 정수 및 십진수 연산을 포함하는 산술 및 논리 명령
3. 조건부 분기, 무조건 점프, call, return 등을 포함하는 제어 흐름 명령
4. 문자열 이동 및 문자열 비교 등을 포함하는 문자열 명령

조건부 분기

• 조건코드에 의해 결정
• 연산 결과에 따라 자동적으로 값 결정되며 연산 결과가 0과 같은지 비교하는데 가장 많이 사용
• 분기 명령어는 조건코드를 검사
• 명령어는 길이가 일정하지 않으므로 PC 상대 주소지정 방식에서 워드 단위가 아닌 바이트 단위 사용

x86의 명령어 인코딩

• op code 바이트에는 피연산자의 크기를 표시하는 비트가 포함
• 어떤 명령어에서는 주소지정 방식과 레지스터 필드가 op에 포함

2.21 오류 및 함정

오류

1. 강력한 명령어를 사용하면 성능이 좋아진다.

• 명령어 실행 방식을 변경하는 접두사를 이용하는 것보다 명령어를 반복적으로 늘어놓는 것이 1.5배 빠르다

2. 최고 성능을 얻기 위해서 어셈블리 언어로 프로그램 작성하기

• 컴파일러 기술이 발달하면서 컴파일러 코드와 손으로 작성한 코드 간의 차이가 줄어들었음
• 어셈블리 프로그램은 코딩과 디버깅에 더 많은 시간이 걸리고, 이식성이 없으며, 유지 보수가 어렵고 일단 프로그램이 작성된다면 생각보다 오래 사용해야 하기 때문에 위험성이 있다
• 상위 수준 언어를 사용하면 장래 새 기종이 개발되더라도 새 컴파일러에 맞게 수정하여 사용할 수 있고 유지 보수가 쉽다

3. 상업용 프로그램의 이진 호환성이 중요하다는 것은 성공적인 명령어 집합은 변하지 않는다는 것을 의미한다

• 40년 동안 평균적으로 한 달에 하나 이상의 명령어가 추가되었다

함정

1. 바이트 주소를 사용하는 컴퓨터에서 인접 워드 간의 주소 차이가 1이 아니라는 사실을 잊는 것

2. 자동 변수가 정의된 프로시저 외부에서 자동 변수에 대한 포인터를 사용하는 것

• 지역 변수로 선언된 배열은 프로시저가 종료되자마자 다른 용도로 재사용된다

2.22 결론

1. 내장 프로그램의 두 가지 원리
   • 숫자와 같은 형태의 명령어를 사용한다
   • 변경 가능한 메모리에 프로그램을 저장한다
2. 설계 원칙
   1) 간단하게 하기 위해서는 규칙적인 것이 좋다
   - 항상 레지스터 피연산자 3개를 갖도록 한 것
   - 어떤 명령어 형식에서나 레지스터 필드 위치가 일정
   2) 작은 것이 더 빠르다
   - MIPS의 레지스터 개수를 32개로 제한
   3) 좋은 설계에는 적당한 절충이 필요하다
   - 명령어 내의 주소나 상수부는 클수록 좋다는 것과 명령어의 길이는 같은 것이 좋다는 것을 절충
3. 주요 아이디어
   1) 타입
   - 숫자에는 내재하는 타입이 있는 것이 아니라 프로그램이 데이터 타입 결정
   2) 자주 생기는 일을 빠르게
   - 조건부 분기에 PC 상대 주소를 사용한 것
   - 큰 상수 피연산자를 위해 수치 주소지정 방식을 도입한 것
   3) 추상화
   - 어셈블러가 어셈블리 언어를 기계가 이해할 수 있는 이진수로 번역하고, 하드웨어에 없는 명령을 추가하여 명령어 집합을 확장하는 것