C 정렬 프로그램 C sort Program
-
Illustrates use of assembly instructions for a C bubble sort function
-
C 프로그램을 어셈블리 프로그램으로 바꿀 때는 다음 절차에 따라 번역한다
1. 프로그램 변수에 레지스터를 할당한다
2. 프로시저 본체에 해당하는 코드를 생성한다
3. 프로시저 호출 후의 레지스터 내용을 호출 전과 같도록 만든다
프로시저 swap
- C code :
void swap(int v[], int k) {
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}-
레지스터 할당
- 이전에 말했듯이, MIPS에서는 인수를 전달하는데 레지스터 $a0 ~ $a3를 사용한다
- swap의 인수는 v, k 두 개 뿐이므로 $a0와 $a1에 할당한다
- 그 외의 변수는 temp 하나 뿐인데, 이는 t0에 할당한다.
-
본체 프로그램
- 나머지 C 코드는 결국 아래와 같다
temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; - MIPS는 바이트 주소를 사용하므로, 각 워드는 실제로 4바이트씩 떨어져 있다. 따라서 인덱스 k를 주소에 더하기 전에 4를 곱해야 한다
- 나머지 C 코드는 결국 아래와 같다
-
MIPS code :
swap :
sll $t1, $a1, 2 // t1 = k * 4
add $t1, $a0, $t1 // t1 = v + (k*4) (address of v[k])
lw $t0, 0($t1) // t0 (temp) = v[k]
lw $t2, 4($t1) // t2 = v[k+1]
sw $t2, 0($t1) // t1 (v[k]) = t2 (v[k+1])
sw $t0, 4($t1) // t2 (v[k+1]) = t0 (temp)
jr $ra // return to calling routine- 프로그램 호출 전/후의 레지스터 값을 같게 유지한다
- $s 레지스터들을 사용하지 않았기 때문에 별도로 해야 할 일은 없다
프로시저 sort
- Non-leaf (calls swap) C code :
void sort(int v[], int n) {
int i, j;
for (i = 0; < 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을 할당한다.
- 두 인수 v와 n은 인수 레지스터 $a0, $a1에 넣고,
양이 너무 많아서 나눠서 작성한다
- The Procedure Body
// sort의 인수를 다른 레지스터에 복사해서 swap을 호출할 때 레지스터 $a0와 $a1을 사용할 수 있게 한다.
move $s2, $a0 // save $a0 into $s2
move $s3, $a1 // save $a1 into $s3
move $s0, $zero // i = 0
for1tst :
// i가 n보다 크면 순환이 종료된다.
slt $t0, $s0, $s3 // if s0 (i) >= s3 (n), t0 = 0
beq $t0, $zero, exit1
addi $s1, $s0, -1 // j = i-1
for2tst :
// 두 조건 (j >= 0, v[j] > v[j+1]) 중 하나라도 거짓이면 순환문에서 나온다.
// 첫 번째 조건에서 탈락(j < 0)이면 바로 순환문에서 나온다
slti $t0, $s1, 0 // if s1 (j) < 0, t0 = 1
bne $t0, $zero, exit2
// 두 번째 조건을 검사한다
sll $t1, $s1, 2 // t1 = j * 4
add $t2, $s2, $t1 // t2 = v + (j * 4) (address of v[j])
lw $t3, 0($t2) // t3 = v[j]
lw $t4, 4($t2) // t4 = v[j+1]
slt $t0, $t4, $t3 // if t4 >= t3, t0 = 0
beq $t0, zero, exit2
// 인수를 전달한다
move $a0, $s2 // 1st param of swap is v (old $a0)
move $a1, $s1 // 2st param of swap is j
// call swap
jal swap
// inner loop
addi $s1, $s1, -1 // j -= 1
j for1st // jump to test of inner loop
exit2 :
//outer loop
addi $s0, $s0, 1 // i += 1
j for1tst // jump to test of outer loop- 프로시저 전과 후의 레지스터 내용을 같게 유지하기
sort :
addi $sp, $sp, -10 // 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)
sw $s1, 4($sp)
sw $s0, 0($sp)
#procedure body
exit1 :
lw $s0, 0($sp) // restore s0 from stack
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $s3, 12($sp)
lw $ra, 16($sp)
addi $sp, $sp, 20 // restore stack poinger
jr $ra // return to calling routineArrays vs. Pointers
- Array indexing involves
multiplying index by element size and adding to array base address
- Pointers correspond directly to memory addresses
We can avoid indexing complexity
- Array version requires shift to be inside loop
Part of index calculation for incremented i
- Compiler can achieve same effect as manual use of pointers
Induction variable elimination
Fallacies
오류 1 : 강력한 명령어를 사용하면 성능이 좋아진다.
- 더 적은 instructions가 요구된다.
- 하지만, 복잡한 instructions는 구현하기가 어렵다. 오히려 모든 instructions의 속도를 낮춰버릴 수도 있다.
- Compilers are good at making fast code from simple instructions
오류 2 : 최고 성능을 얻기 위해 어셈블리 언어로 프로그램 작성하기
- Modern compilers are better at dealing with modern processors
- More line of code can cause more errors and less productivity
오류 3 : 이진 호환성이 중요하다는 것은 instructions set이 변하지 않는다는 것을 의미한다
- x86 instructions set은 매우 극적으로 성장해 왔다.
Pitfalls
함정 1 : 바이트 주소를 사용하는 컴퓨터에서 인접 워드 간의 주소 차이가 1이 아니라는 사실을 잊는 것
- Sequential words are not at sequential addresses
- Increment by 4, not by 1;;
함정 2 : 자동 변수가 정의된 프로시저 외부에서 자동 변수에 대한 포인터를 사용하는 것
(Keeping a pointer to an automatic variable after procedure returns)
- 프로시저의 결과를 전달할 때 프로시저 내에서 지역 변수로 선언된 배열을 가리키는 포인터를 포함시시켠 안된다. 그러한 메모리 영역은 프로시저가 종료되자마자 다른 용도로 재사용된다.
- 따라서 이미 없어진 자동 변수에 대한 포인터를 사용하면 예기치 못한 일이 발생할 수도 있다.
