Computer Science/Computer Architecture

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

great_park 2022. 10. 9. 14:49
반응형

여기서는 위에서 살펴본 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

https://blog.kakaocdn.net/dn/GwE3o/btrN674oV4l/mOCRpmsfKmxRjQWPsrXGy0/img.png

 

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

https://blog.kakaocdn.net/dn/bYJtBK/btrN393v4C5/S7XQ90osDxBtKtPVGdGtkk/img.png

  • 첫번째 필드는 사용하지 않는다.
  • 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
  1. beq
  2. bne
  • Unconditional
  1. j : jump
  2. jr : jump register
  3. jal : jump and link

(1) beq - branch taken

https://blog.kakaocdn.net/dn/bUn0xr/btrN3Tr5lNf/LHLEsllnzIksvX4ECfmPtK/img.png

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

 

(2) bne - branch not taken

https://blog.kakaocdn.net/dn/bLlquC/btrN5F1m99i/5KYq0528NBgSNvETrfBw3K/img.png

 

(3) j - jump

https://blog.kakaocdn.net/dn/zGn0q/btrN40ZcUq6/LyP6bgEZlq6an38tWiOWm1/img.png

 

(4) jr - jump register

https://blog.kakaocdn.net/dn/XI9bZ/btrN39PYwRJ/qgFAZOghnYjaBxKV8mcZUK/img.png

 

Summary

https://blog.kakaocdn.net/dn/55ouS/btrN8ASOrpv/AX2kqTUmn2vViiodKTTVJ0/img.png

 

 

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
  • https://blog.kakaocdn.net/dn/dtxAVQ/btrN4Y8cylE/F9qHWkQT50MIklQSCd0ZGK/img.png

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
  1. callee에게 argument를 넘김
  2. callee로 jump
  • Calee : called function
  1. function을 수행
  2. caller에게 return
  3. call의 point를 return
  4. 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

https://blog.kakaocdn.net/dn/blU6py/btrN40StC4B/qwWNlyDO8maZF7GPsaGi2K/img.png

  • 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

https://blog.kakaocdn.net/dn/cnDxoC/btrN38RpGCt/I4M3gxbMf3FR6Vb3qvCRc1/img.png

 

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
반응형
저작자표시