[컴퓨터 구조] Ch6. Architecture (2) - Programming

여기서는 위에서 살펴본 assembly code, machine code로 high-level software constructs를 구현하는 방법을 소개합니다. (if/else, for loops, while loops, arrays, function calls)

Logical Instructions

and, or, xor, nor = R-type
andi, ori, xori = I-type

Example

Shift Instructions

sll : shirt left logical ⇒ sll $t0, $t1, 5 # $t0 <= $t1 << 5
srl : shift roght logical
sra : shirft right arithmetic ⇒ sra $t0, $t1, 5 #$t0 <= $t1 >>> 5

Variable Shift Instructions

sllv : shift left lofical varialble
srlv : shfit right logical variable
srav : shif right arithmetic variable

첫번째 필드는 사용하지 않는다.
source가 먼저 오고(rt) destination이 뒤에 온다(rd)

Generating Constants

16-bit : addi 사용

1. c 언어
int a = 0x4f3c;

2. MIPS assembly code
addi $s0, $0, 0x4f3c

32-bit : load upper immediate (lui) and (ori)

1. c 언어
int a = 0xFEDC8765;

2. MIPS assembly code
lui $s0, 0xFEDC    # 상위 16비트에 들어감,           $s0 = 0xFEDC0000
ori $s0, $s0, 0x8765 # 나머지 하위 16비트에 들어감,  $s0 = 0xFEDC8765

Exercise

다음 연산의 결과로 $s1에 저장되는 값은??

lui $s0, 0xFEDC
ori $s0, $s0, 0x4321    # $s0 = 0xFEDC8765
addi $t0, $0, 8         # $t0 = 8
srav $s1, $s0, $t0      # $s1 = 0xFFFE DC43 (sign extended)

=> $s1 = 0xFFFE DC43

$s0의 상위 16비트를 얻는 방법은?

$s0 = FEDC1234
$t0 = 0000FEDC

=> srl $t0, $s0, 16

다음 C code를 어셈블리 code로 변환하라

a는 $s0 b는 $s1 c는 $s2에 저장

1. C code
c = (~(a & 0xFF)) + 1 + (b & 0xFF);

2. MIPS assembly code
andi $t0,$s0, 0xFF
nor $t1, $t0, $0
addi $t2, $t1, 1
andi $t3, $s1, 0xFF
add $s2, $t2, $t3

곱셈, 나눗셈

lo, hi : special register라서 번호가 없어서 직접 인코딩이 불가능
32 x 32 bit 곱셈 ( mult ) ⇒ 64bit의 결과

mult $s0, $s1
Result in { hi, lo }   #항상 mult의 결과는 여기로 들어간다.

32 bit 나눗셈 ( div )

div $s0, $s1 
몫은 lo, 나머지는 hi에 저장

lo/hi에서 다른 곳으로 옮기기 (mflo, mfhi)

mflo $2
mfhi $3

Branching

Conditional

beq
bne

Unconditional

j : jump
jr : jump register
jal : jump and link

(1) beq - branch taken

beq 명령어에서 둘이 같으면 target으로 jump하게 된다.

(2) bne - branch not taken

(3) j - jump

(4) jr - jump register

Summary

Conditional Statement

1. If statement

1. C 언어
if (i = = j)
    f = g + h;
f = f – i;

2. MIPS Assembly code
# $s0 = f, $s1 = g, $s2 = h, $s3 = i, $s4 = j

    bne $s3, $s4, **L1**   # if i != j, skip if block
    add $s0, $s1, $s2  # if block: f = g+h
**L1**:
    sub $s0, $s0, $s3  # f = f − i

2. If/Else Statement

1. C 언어
if (i = = j)
    f = g + h;
else
    f = f − i;

2. MIPS Assembly code
# $s0 = f, $s1 = g, $s2 = h, $s3 = i, $s4 = j

    bne $s3, $s4, else        # if i != j, branch to else
    add $s0, $s1, $s2         # if block: f = g+h
    j done                    # skip past the else block
else:
    sub $s0, $s0, $s3         # else block: f = f − i
done:

Getting Loopy

3.While Loops

1. C 언어
int pow = 1;
int x = 0;

while (pow != 128)
{
    pow = pow * 2;
    x = x + 1;
}

2. MIPS Assembly code 
# $s0 = pow, $s1 = x
    addi $s0, $0, 1        # pow = 1
    addi $s1, $0, 0        # x = 0
    addi $t0, $0, 128      # t0 = 128 for comparison
while:
    beq $s0, $t0, done     # if pow = = 128, exit while loop
    sll $s0, $s0, 1        # pow = pow * 2
    addi $s1, $s1, 1       # x = x+1
    j while
done:

beq는 register끼리만 비교가 가능하다.
상수를 register에 넣고 register끼리 비교해야 된다.

4. For loops

1. C 언어
int sum = 0;

for (i = 0; i != 10; i = i + 1) {
    sum = sum + i ;
}

// equivalent to the following while loop
int sum = 0;
int i = 0;

while (i != 10) {
    sum = sum + i;
    i = i + 1;
}

2. MIPS Assembly code
# $s0 = i, $s1 = sum
    add $s1, $0, $0        # sum = 0
    addi $s0, $0, 0        # i = 0
    addi $t0, $0, 10       # $t0 = 10
for:
    beq $s0, $t0, done     # if i = = 10, branch to done
    add $s1, $s1, $s0      # sum = sum + i
    addi $s0, $s0, 1       # increment i
    j for
done:

5. Less Than Comparison

1. C 언어
int sum = 0;
int i;

for (i = 1; i < 101; i = i * 2){
    sum = sum + i;
}

2. MIPS Assembly code
# $s0 = i, $s1 = sum
    addi $s1, $0, 0      # sum = 0
    addi $s0, $0, 1      # i = 1
    addi $t0, $0, 101    # $t0 = 101
loop:
    slt $t1, $s0, $t0    # if (i < 101) $t1 = 1, else $t1 = 0
    beq $t1, $0, done    # if $t1 == 0 (i >= 101), branch to done
    add $s1, $s1, $s0    # sum = sum + i
    sll $s0, $s0, 1      # i = i*2
    j loop
done:

Arrays

base address = 첫번째 element의 주소
address = base + index * size

1. Accessing Arrays

1. C 언어
int array[5];
array[0] = array[0] * 8;
array[1] = array[1] * 8;

2. MIPS Assembly code
# $s0 = base address of array
    lui $s0, 0x1000       # $s0 = 0x10000000
    ori $s0, $s0, 0x7000  # $s0 = 0x10007000
    lw $t1, 0($s0)        # $t1 = array[0]
    sll $t1, $t1, 3       # $t1 = $t1 << 3 = $t1 * 8
    sw $t1, 0($s0)        # array[0] = $t1
    Iw $t1, 4($s0)        # $t1 = array[1]
    sll $t1, $t1, 3       # $t1 = $t1 << 3 = $t1 * 8
    sw $t1, 4($s0)        # array[1] = $t1

2. Arrays Using For Loops

1. C 언어
int i;
int array[1000];
for (i = 0; i < 1000; i = i + 1){
    array[i] = array[i] * 8;
}

2. MIPS Assembly code
# $s0 = array base address, $s1 = i
# initialization code
    lui $s0, 0x23B8       # $s0 = 0x23B80000
    ori $s0, $s0, 0xF000  # $s0 = 0x23B8F000
    addi $s1, $0, 0       # i = 0
    addi $t2, $0, 1000    # $t2 = 1000
loop:
    slt $t0, $s1, $t2     # i < 1000?
    beq $t0, $0, done     # if not, then done
    sll $t0, $s1, 2       # $t0 = i*4 (byte offset)
    add $t0, $t0, $s0     # address of array[i]
    lw $t1, 0($t0)        # $t1 = array[i]
    sll $t1, $t1, 3       # $t1 = array[i] * 8
    sw $t1, 0($t0)        # array[i] = array[i] * 8
    addi $s1, $s1, 1      # i = i+1
    j loop                # repeat
done:

ASCII Code

text character 마다 부여된 unique byte value

Function Calls

Caller : calling function

callee에게 argument를 넘김
callee로 jump

Calee : called function

function을 수행
caller에게 return
call의 point를 return
caller가 필요한 메모리나 레지스터를 덮어쓰면 안된다.

MIPS Function Conventions

Call function : jump and link (jal) 사용
Return : jump register (jr) 사용
Arguments : $a0 ~ $a3 사용 → callee는 caller가 여기에 넘겼을 것이라 생각하고 가져감
Retrun value : $v0 → callee가 여기에 저장, caller는 여기서 가져감

Function Calls

1. C 언어
int main() {
    simple();
    ...
}
// void means the function returns no value
void simple() {
    return;
}

2. MIPS Assembly code

0x00400200 main: jal simple # call function
0x00400204       ...
0x00401020 simple: jr $ra # return

=> 
jal : jumps to simple
         $ra = PC + 4 = 0x00400204
jr $ra : jumps to address in $ra (0x00400204)

Input Arguments & Return value

1. C 언어
int main()
{
    int y;
    ...
    y = diffofsums(2, 3, 4, 5);
    ...
}

int diffofsums(int f, int g, int h, int i)
{
    int result;
    result = (f + g) − (h + i);
    return result;
}

2. MPIS Assembly code  (!문제점이 있는 코드! -> callee가 caller가 사용하는 곳을 덮어씀)
# $s0 = y
main:
    ...
    addi $a0, $0, 2         # argument 0 = 2
    addi $a1, $0, 3         # argument 1 = 3
    addi $a2, $0, 4         # argument 2 = 4
    addi $a3, $0, 5         # argument 3 = 5
    jal diffofsums          # call function
    add $s0, $v0, $0        # y = returned value
    ...
# $s0 = result
diffofsums:
    add $t0, $a0, $a1       # $t0 = f+g
    add $t1, $a2, $a3       # $t1 = h+i
    sub $s0, $t0, $t1       # result = (f + g) − (h + i)
    add $v0, $s0, $0        # put return value in $v0
    jr $ra                  # return to caller

⇒ 여기서 문제점은, callee는 caller가 사용하는 register와 memory를 사용할 수 없다는 점이다.

이를 해결하기 위해서 stack을 사용하여 잠시 담아뒀다가 꺼내는 식으로 해결할 수 있습니다!

Stack

메모리 영역에서 stack과 heap은 동적으로 구현된다. 이때 효율성을 위해서 heap은 밑에서 부터 grow up,하고, stack은 위에서 부터 grow down한다.
Stack pointer : $sp = stack의 top을 가리키는 pointer

위에서의 코드를 stack을 이용하여 개선하면 아래와 같습니다.

# $s0 = result
diffofsums:
    addi $sp, $sp, −12  # make space on stack to store three registers
    sw $s0, 8($sp)      # save $s0 on stack
    sw $t0, 4($sp)      # save $t0 on stack
    sw $t1, 0($sp)      # save $t1 on stack
    add $t0, $a0, $a1   # $t0 = f+g
    add $t1, $a2, $a3   # $t1 = h+i
    sub $s0, $t0, $t1   # result = (f + g) − (h + i)
    add $v0, $s0, $0    # put return value in $v0
    lw $t1, 0($sp)      # restore $t1 from stack
    lw $t0, 4($sp)      # restore $t0 from stack
    lw $s0, 8($sp)      # restore $s0 from stack
    addi $sp, $sp, 12   # deallocate stack space
    jr $ra              # return to caller

Preserved and nonpreserved registers

preserverd ⇒ callee 입장에서는 이것만 보존하면 됨
nonpreserverd ⇒ 나머지는 원하는 caller가 해야 한다.

Multiple Function Calls

아래의 경우는 callee가 다른 함수를 호출하는 경우이다.

procl:
    addi $sp, $sp, -4
    sw $ra, 0($sp)    #ra를 stack에 저장
    jal proc2         #ra에 return address update 시킴
    ...
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

Exercise

main:
    ...
    addi $a0, $0, 1
    addi #a1, $0, 2
    jal func
    add $s0, $v0, $s0
    ...
func:    #callee
    addi $sp, $sp, -4
    sw $s0, 0($sp)
    or $t0, $a0, $s1
    addi $s0, $t0, 4
    add $v0, $t0, $s0
    lw $s0, 0($sp)
    addi $sp, $sp, 4
    jr $ra

main:
    ...
    addi $a0, $0, 1
    addi $a1, $0, 2
    jal func
    add $s0, $v0, $0
    ...

func:
    addi $sp, $sp, -12
    sw $ra, 0($sp)
    sw $s0, 4($sp)
    sw $s1, 8($sp)
    or $t0, $a0, $a1
    addi $s0, $t0, 4
    jal func2          # ra를 update
    and $s1, $0, $v0
    add $v0, $v0, $s1
    lw $ra, 0($sp)
    lw $s0, 4($sp)
    lw $s1, 8($sp)
    addi $sp, $sp, 12
    jr $ra

func2:
    addi $t0, $0, 0
    addi $vo, $t0, 4
    jr $ra

Recursive Function Call

1. C언어
int factorial(int n){
    if (n <= 1){
        return 1;
    }
}
else{
    return (n * factorial(n − 1));
}

2. MIPS Assembly code
     factorial: 
0x90      addi $sp, $sp, −8  # make room on stack
0x94      sw $a0, 4($sp)     # store $a0
0x98      sw $ra, 0($sp)     # store $ra
0x9C      addi $t0, $0, 2    # $t0 = 2
OxAO      slt $t0, $a0, $t0  # n <= 1 ?
0xA4      beq $t0, $0, else  # no: goto else
0xA8      addi $v0, $0, 1    # yes: return 1
OxAC      addi $sp, $sp, 8   # restore $sp
OxBO      jr $ra             # return
     else: 
0xB4      addi $a0, $a0, −1  #n = n − 1
0xB8      jal factorial      # recursive call
OxBC      Iw $ra, 0($sp)     # restore $ra
OxCO      Iw $a0, 4($sp)     # restore $a0
0xC4      addi $sp, $sp, 8   # restore $sp
0xC8      mul $v0, $a0, $v0  # n * factorial(n−1)
OxCC      jr $ra             # return

Function Call Summary

1. Caller

$a0 ~ $a3 : argument 저장
save any needed register : $ra, maybe $t0 ~ $t9
jal callee
restore registers
$v0 : 리턴값이 여기에 있을 것이라 생각하고 수행

2. Callee

$s0 ~ $s7 : register 사용
함수 수행
$v0 : 여기에 리턴값 저장
restore registers
jr $ra

저작자표시

'Computer Science > Computer Architecture' 카테고리의 다른 글

[컴퓨터 구조] Ch7. Microarchitecture (0)	2022.11.19
[컴퓨터 구조] Ch6. Architecture (3) - Addressing Mode, Odds & Ends (0)	2022.10.09
[컴퓨터 구조] Ch6. Architecture (1) - Assembly Language, Machine Language (1)	2022.10.08
[컴퓨터 구조] Ch5. Digital Building Blocks (3) - Memory Arrays, Logic Arrays - ROM, DRAM, SRAM 중점으로 (0)	2022.09.25
[컴퓨터 구조] Ch5. Digital Building Blocks (2) - Number System : Floating-point number 부동 소숫점 중심으로 (1)	2022.09.24

Logical Instructions

Example

Shift Instructions

Variable Shift Instructions

Generating Constants

Exercise

곱셈, 나눗셈

Branching

(1) beq - branch taken

(2) bne - branch not taken

(3) j - jump

(4) jr - jump register

Summary

Conditional Statement

1. If statement

2. If/Else Statement

Getting Loopy

3.While Loops

4. For loops

5. Less Than Comparison

Arrays

1. Accessing Arrays

2. Arrays Using For Loops

ASCII Code

Function Calls

MIPS Function Conventions

Function Calls

Input Arguments & Return value

Stack

Preserved and nonpreserved registers

Multiple Function Calls

Exercise

Recursive Function Call

Function Call Summary

'Computer Science > Computer Architecture' 카테고리의 다른 글

티스토리툴바