MIPS reg assembly

1. 명령어 집합(instruction set)
특정한 구조가 이해할 수 있는 명령어들의 집합 - 컴퓨터 하드웨어에게 일을 시킬 수 있는 도구, 언어의 집합

2. 내장 프로그램(stored-program)개념
여러 종류의 데이터와 명령어를 메모리에 숫자로 저장할 수 있다는 개념. 이 개념에 따라 내장 프로그램 컴퓨터가 만들어짐

3. 워드(word)
컴퓨터에서 자연스러운 접근 단위. 보통 32비트이다. MIPS 구조에서 레지스터 크기에 해당한다.

4. 데이터 전송(data transfer)명령
메모리와 레지스터 사이에서 데이터를 이동하는 명령어.

5. 메모리 주소
메모리 배열 내에서 특정 데이터 요소의 위치를 표시하는데 사용하는 값.

6. 정렬 제약(alignment restriction)
메모리 내에서 데이터는 자연스러운 경계를 지켜서 정렬되어야 한다는 요구조건. 제일 왼쪽, 즉 최상위(big-end) 바이트 주소를 워드 주소로 사용하는 것과 제일 오른쪽, 즉 최하위(little-end) 바이트 주소를 워드 주소로 사용하는 것 두 종류로 나누어진다. MIPS는 Big Endian Intel IA-32는 Little Endian 계열이다.

*. 스필링 레지스터(spilling register)
컴파일러는 자주 사용되는 변수를 가능한 한 많이 레지스터에 넣고 나머지 변수는 메모리에 저장했다가 필요할 때 꺼내서 레지스터에 넣는다. 자주 사용하지 않는 (또는 한참 후에 사용할) 변수를 메모리에 넣는 일을 레지스터를 스필링 한다고 말한다.

*. MIPS 명령어의 필드
[   op   ][   rs   ][   rt   ][   rd   ][ shamt ][ funct ]
6bits      5bits     5bits     5bits     5bits      6bits

op : 명령어가 실행할 연산의 종류 opcode로 불리운다.
rs : 첫 번째 근원지(source) 피연산자 레지스터
rt : 두 번째 근원지 피연산자 레지스터
rd : 목적지(destination) 레지스터, 연산 결과가 기억된다.
shamt : 자리이동(shift) 양. (2.5절에서 shift 명령과 이 용어를 설명한다. 그전까지 이 필드는 사용하지 않고 0으로 채워 둔다.)
funct : 기능(function). op 필드에서 연산의 종류를 표시하고 funct 필드에서는 그 중의 한 연산을 구체적으로 지정한다. 기능 코드(function code)라고 부르기도 한다.

* MIPS 명령어
산술연산자
add                            : $s1 = $s2 + $s3
sub (subtract)             : $s1 = $s2 - $s3
addi (add immediate)   : $s1 = $s2 + 100
addu (add unsigned)    : $s1 = $s2 + $s3
subu (subtract unsigned) : $s1 = $s2 - $s3
addiu (add immediate unsigned) : $s1 = $s2 + 100
mfc0 (move from coprocessor register) : $s1 = $epc :: EPC와 다른 특별한 레지스트를 복사하기 위해 사용
mult (multiply)             : Hi, Lo = $s2 x $s3  :: 64비트 부호 있는 곱셈; Hi, Lo
multu (multiply unsigned) : Hi, Lo = $s2 x $s3  :: 64비트 부호 있는 곱셈; Hi, Lo
div (divide)                   : Lo = $s2 / $s3, Hi = $s2 mod $s3 :: Lo = 몫, Hi = 나머지
divu (divide unsigned)   : Lo = $s2 / $s3, Hi = $s2 mod $s3 :: 부호없는 몫과 나머지
mfhi (move from Hi)      : $s1 = Hi :: Hi의 복사본을 얻는데 사용
mflo (move from Lo)     : $s1 = Lo :: Lo의 복사본을 얻는데 사용

논리연산자
and                            : $s1 = $s2 & $s3
or                               : $s1 = $s2 | $s3
nor                             : $s1 = ~($s2 | $s3)
andi (and immediate)   : $s1 = $s2 & 100
ori (or immediate)        : $s1 = $s2 | 100
sll (shift left logical)      : $s1 = $s2 << 10
srl (shift right logical)   : $s1 = $s2 >> 10

데이터전송 (메모리 <-> 레지스터)
lw (load word)            : $s1 = Memory[$s2 + 100]
sw (store word)          : Memory[$2 + 100] = $s1
lhu (load half unsigned): $s1 = Memory[$s2 + 100]
lbu (load byte unsigned): $s1 = Memory[$s2 + 100]

조건부 분기
beq (branch on equal) : if ($s1 == $s2) go to L
bne (branch on not equal) : if ($s1 != $s2) go to L
slt (set on less than)   : if ($s2 < $s3) $s1 = 1; else $s1 = 0
sltu (set less than unsigned): if ($s2 < $s3) $s1 = 1; else $s1 = 0
sltiu (set less than immediate unsigned): if ($s2 < 100) $s1 = 1; else $s1 = 0

무조건 점프
j (jump)                      : go to L
jr (jump register)          : go to $ra
jal (jump and link)       : $ra = PC + 4; go to L 
13. 기본 블럭(basic block)
분기 명령을 포함하지 않으며(맨 끝에는 있을 수 있다.) 분기 목적지나 분기 레이블도 없는(맨 앞에 있는 것은 허용된다.) 명령어 시퀀스. 오랫동안 쓰여질 메모리 블럭인지의 구분 기준이기도 하며 컴파일러가 초기 단계에 하는 작업중의 하나이다.

16. jal(jump-and-link)
지정된 주소로 점프하면서 동시에 다음 명령어의 주소를 레지스터(MIPS에서는 $ra)에 저장하는 명령어.

17. 복귀주소(return address)
프로시저 종료 후 제자리로 돌아갈 수 있게 하는 호출위치에 대한 링크. MIPS에서는 $ra 레지스터에 저장된다.

18. 프로그램 카운터(program counter, PC)
실행 중인 명령어의 주소를 가지고 있는 레지스터.

22. 스택 포인터(stack pointer)
가장 최근에 스택에 할당된 주소를 가리키는 값. 레지스터가 스필될 장소 또는 레지스터의 옛날 값을 찾을 수 있는 장소를 표시한다.

* 레지스터는 데이터를 저장하는 중 속도가 가장 빠른 장소이므로 가능한 많이 사용하는 것이 바람직 하지만, 레지스터가 제한되어 있으므로 프로시져 호출 시에는 다음과 같은 제약조건이 부여되고 그 이외에는 stack 을 활용한다.

$a0 - $a3 : 전달할 인수를 가지고 있는 인수 레지스터 4개
$v0 - $v1 : 처리 결과를 되돌려 주는 결과 값 레지스터 2개
$ra : 호출한 곳으로 되돌아 갈 때 사용하는 복귀주소 레지스터 1개
$t0 - $t9 : 프로시져 호출 시, 피호출 프로그램이 원상 복구해 주지 않는 임시 레지스터 10개
$s0 - $s7 : 프로시져 호출 전과 후의 값이 같게 유지되어야 하는 저장 레지스터 8개 
        (피호출 프로그램이 이 레지스터를 사용하면 원래 값을 저장했다가 원상 복구 해야 함.)

23. 전역 포인터(global pointer, $gp)
정적 데이터를 가리키는데 사용하도록 예약된 레지스터.

24. 프로시져 프레임(procedure frame)
레지스터에 들어가지 못할만큼 큰 배열이나 구조체같은 지역 변수를 저장하는데에도 스택을 사용하게 되는데. 이 떄에 프로시져의 $s 레지스터들과 지역 변수를 저장하는 스택(stack) 부분을 말하며 액티베이션 레코드라고도 한다.

25. 프레임 포인터($fp)
프로시져의 저장된 레지스터와 지역 변수의 위치를 표시하는 값.

* 메모리의 사용 시에 스택은 최상위 주소에서부터 시작해서 아래쪽으로 자라며 아래와 같은 모양이다.
$sp -> 7fff fffc     ────────
                                            stack
                                             ↓
 
                                             ↑
                                    dynamic data (heap)
$gp -> 1000 8000 ────────
                                        static data
$gp -> 1000 0000 ────────
                                             text
pc  -> 0040 0000 ────────
                                           사용유보
                            0 ────────

26. 텍스트 세그먼트(text segment)
Unix 목적 파일에서 원시 파일 루틴의 기계어가 수록된 부분.

27. PC-상대주소지정방식(PC-relative addressing)
PC와 명령어 내 상수의 합이 실제 주소가 되는 주소 지정방식으로 32bit 명령어를 만드는 방식이기도 하다.

28. MIPS 주소지정방식
1. 수치(immediate) 주소지정 ... 피연산자는 명령어 내에 있는 상수이다.           [ op ][ rs ][ rt ][    수   치   값    ]

2. 레지스터 주소지정 ... 피연산자는 레지스터이다.
   [ op ][ rs ][ rt ][ rd ][ ... ][ funct ]
               └────────→ [      레지스터     ]

3. 베이스(base) 또는 변위(displacement) 주소시정 ... 메모리 내용이 피연산자이다. 
  메모리 주소는 레지스터와 명령어 내의 상수값을 더해서 구한다.
   [ op ][ rs ][ rt ][    Address    ]
               └───────┐                                  메모리
                                               (+) ──→ [ 바이트 | 하프워드|     워드       ]
             [      레지스터     ]──┘


4. PC-상대주소지정 ... PC값과 명령어 내 상수의 합을 더해서 주소를 구한다.
   [ op ][ rs ][ rt ][    Address    ]
               └───────┐                                  메모리
                                               (+) ──→[                 워드                 ]
             [      레지스터     ]──┘

5. 의사직접(pseudodirect) 주소지정 ... 명령어 내의 26비트를 PC의 상위 비트들과 연접하여 점프주소를 구한다.
   [ op ][              Address            ]
               └───────┐                                  메모리
                                               (:) ──→ [ 바이트 | 하프워드|     워드       ]
             [           PC        ]──┘


30. 의사 명령어(pseudoinstruction)
하드웨어가 지원하지 않는 어셈블리 언어 명령어를 마치 실제 잇는 것 처럼 어셈블러가 처리하는 명령어.
예를 들어 MIPS에서는 SYSTEM에는 MOV명령어가 없으나 어셈블러 명령어에는 있다.
"move $t0, $t1" 라고 명령어를 입력하여도
"add $t0, $zero, $t1" 으로 해석하여 기계어로 바꾼다.

31. 기계어
컴퓨터 시스템 내부에서 사용하기 위한 이진수 형태의 명령어

32. 심볼 테이블(symbol table)
레이블 이름을 명령어가 기억된 메모리 워드의 주소와 짝 지워주는 표

*. UNIX 시스템의 목적파일은 아래의 여섯 부분으로 구성된다.
1. 목적파일 헤더 : 목적파일을 구성하는 각 부분의 크기와 위치를 서술한다.
2. 텍스트 세그먼트 : 기계어 코드가 들어있다.
3. 정적 데이터 세그먼트 : 프로그램 수명동안 할당되는 데이터가 들어있다. 
 (UNIX는 프로그램 실행이 끝날 때까지 계속 할당되는 정적 데이터와 프로그램의 요구에 다라 커졌다 작아졌다
  하는 동적 데이터 두 가지를 프로그램이 사용할 수 있게 한다.)
4. 재배치(relocation) 정보 : 프로그램이 메모리에 적재될 때 절대주소에 의존하는 명령어와 데이터 워드를 표시.
  (가상의 주소정보를 갖고있다가 실행시에 진입점과 실제 주소를 맵핑한다)
5. 심볼 테이블 : 외부 참조같이 아직 정의되지 않고 남아 있는 레이블들을 저장한다.
  (커널 내부의 함수나 변수 중 외부에서 참조할 수 있는 함수의 심볼과 주소를 담은 테이블)
6. 디버깅 정보 : 각 모듈이 어떻게 번역되었는지에 대한 간단한 설명이 들어있다. 디버거는 이 정보를 이용해서
  기계어와 C 원시 파일을 연관 짓고 자료 구조를 판독한다.

33. 링커(linker)
링크 에디터라고도 한다. 따로 따로 어셈블 된 기계어 프로그램을 결합하고 정의 안 된 레이블의 주소를 찾아내어 실행 파일을 만드는 시스템 프로그램.

34. 실행파일(executable file)
목적파일 형식의 기능 프로그램으로, 미해결 참조, 재배치 정보, 심볼 테이블, 디버깅 정보를 가지고 있지 않다.

35. 로더
목적 프로그램을 메인 메모리에 적재해서 실행할 수 있게 하는 시스템 프로그램
운영체제는 디스크에 있는 실행파일을 메모리에 넣고 이를 시작시킨다. UNIX 시스템은 이 일을 다음 순서로 실행한다.

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

36. Java 바이트코드
Java 프로그램을 인터프리터하기 위해 설계된 명령어 집합의 명령어

37. 자바 가상머신(JVM)
Java 바이트 코드를 인터프리터 하는 프로그램

38. JIT(Just In Time)
실행 시에 작동하는 컴파일러를 일반적으로 일컫는 말. 인터프리터된 코드를 컴퓨터 고유의 명령어로 번역한다.

*. 프로시져 확장(procedure inlining) <- 고수준 최적화
함수 호출문장을 함수 본문으로 대치하는 것이며, 이 때 프로시져의 가인수는 호출 프로그램의 실인수로 대치된다.

39. 순환문 펼치기(loop unrolling) <- 고수준 최적화
순환문 본체를 여러 번 반복해서 쓰고 변환된 순환문의 반복 회수를 그 만큼 줄이는 방법으로 배열의 접근하는 순환의 성능을 높이기 위한 기술이다. 순환 본체를 여러 번 복사한 후 서로 다른 반복에 속한 명령어들을 함께 스케쥴 한다.
순환 오버헤드를 줄일 뿐 아니라 다른 최적화 기법을 적용할 기회를 늘려준다.

*. 지역 및 전역 최적화
1. 기본 블럭(basic block) 내에서 수행되며 전역 최적화의 전초와 후속 단계로 수행된다.
2. 여러 개의 기본 블럭에 걸쳐서 수행
3. 전역 레지스터 할당은 코드의 한 부분에 대해서 변수를 레지스터에 할당하는 것
전역 최적화뿐만 아니라 공통 부분식 제거(common subexpression elimination), 상수 전파(constant propagation), 복사 전파(copy propagation), 비사용 메모리 제거(dead store elimination), 강도 약화(strength reduction) 등의 지역 최적화가 수행된다.

*. 프로시져 swap 을 어셈블리로 해석해보자
C 코드 (int type으로 가정)
void swap(int v[], int k)
{
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}

어셈블리 코드
우선 인수전달 시에 레지스터 $a0, $a1, $a2, $a3 를 사용하는데 인수가 두 개 뿐이므로 $a0 와 $a1 에 할당된다.

1. temp = v[k];
sll     $t1, $a1, 2     # MIPS 는 바이트 주소를 사용하므로 실제로 4 바이트씩 떨어져 있으므로 :: reg $t1 = k * 4
add   $t1, $a0, $t1   # 실제 v 주소에서 ( k + 1 ) 인덱스 주소 값을 $t1 에 넣기 위해서 다시 :: reg $t1 = v + (k * 4)

2. v[k] = v[k+1];
lw     $t0, 0($t1)      # $t1을 이용해서 v[k]를 적재하고, :: reg $t0 (temp) = v[k]
lw     $t2, 4($t1)      # t1에 4를 더해 v[k+1]을 적재할 수 있다. :: reg $t2 = v[k + 1]

3. v[k+1] = temp;
sw    $t2, 0($t1)      # $t0와 $t2를 반대 주소에 저장 v[k] = reg $t2
sw    $t0, 4($t1)      # v[k + 1] = reg $t0 (temp)

4. return
jr       $ra               # return to calling routine  

*. 결론
명령어 집합 설계자를 위한 설계원칙
1. 간단하기 위해서는 규칙적인 것이 좋다.
    : 모든 명령어의 길이를 똑 같게 한 것.
    : 산술 명령어는 항상 레지스터 피연산자가 세개로 한 것.
    : 어떤 명령어 형식에서나 레지스터 필드의 위치를 일정하게 만든것.

2. 작은 것이 빠르다.
    : 레지스터 개수를 32개로 제한한 것.
3. 자주 생기는 일을 빠르게 하라.
    : 조건부 분기에 PC-상대 주소를 사용한 것.
    : 수치 주소로 상수 피연산자를 사용할 수 있게 만든 것.
4. 좋은 설계에는 절충이 필요하다.
    : 명령어 내의 주소나 상수부는 클수록 좋으며 모든 명령어의 길이는 같은 것이 좋다는 요구사항을 절충 한 것. 


*. 오류 및 함정
오류 : 강력한 명령어를 사용하면 성능이 좋아진다.
강력한 명령어는 프로그램이 실행하는 명령어의 개수를 줄이자는 의도이지만, 간결성을 희생하는 것이므로, 클럭 사이클 시간이 길어지거나 필요한 클럭 사이클 개수가 많아져서 오히려 시간이 늘어날 위험이 있다.

함정 : 최고 성능을 얻기 위해 어셈블리 언어로 프로그램 작성하기.
과거에는 컴파일러가 생성하는 코드가 성능이 좋지 않았으나 현재는 많은 발전이 있어서 사람이 정의하는 것 보다 기계가 더 효율적인 방식을 알고 있으며, 고급언어를 사용하게되면 향후에 새로운 기종이 개발되더라도 호환성을 보장받을 수 있으므로 잘못된 말이다.

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

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

출처 : http://psyoblade.egloos.com/2411691