[컴퓨터구조] 7. MIPS assembly programming(Array etc.)

Array

• Access large amounts of similar data
• Index: access each element
• Size: number of elements
• 5-element array
• Base address = = 0x12348000 (address of first element, array[0])
• First step in accessing an array: load base address into a register(register로 base address를 로드)

Accessing Arrays

// C Code
int array[5];
array[0] = array[0] * 2;
array[1] = array[1] * 2;

 

# MIPS assembly code
# array base address = $s0
lui $s0, 0x1234         # 0x1234 in upper half of $S0
ori $s0, $s0, 0x8000     # 0x8000 in lower half of $s0

lw $t1, 0($s0)             # $t1 = array[0]
sll $t1, $t1, 1         # $t1 = $t1 * 2
sw $t1, 0($s0)             # array[0] = $t1

lw $t1, 4($s0)             # $t1 = array[1]
sll $t1, $t1, 1         # $t1 = $t1 * 2
sw $t1, 4($s0)             # array[1] = $t1

 

Array using For Loops

// C Code
int array[1000];
int i;

for (i=0; i < 1000; i = i + 1)
    array[i] = array[i] * 8;

# MIPS assembly code
# $s0 = array base address, $s1 = i
# 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:

 

Function Calls

• Caller: calling function (in this case, main)
• Calle: called function (in this case, sum)

//C Code
void main()
{
    int y;
    y = sum(42, 7);
    ...
}

int sum (int a, int b)
{
    return (a + b);
}

• $ra를 통해 다시 돌아오고 반환할 때는 값을 $v0에 담아서 반환한다.
  • ra: return address

 

Function Conventions

• Caller:
  • passes arguments to callee
  • jumps to callee
• Callee:
  • performs the function
  • returns result to caller
  • returns to point of call
  • must not overwrite registers or memory needed by caller

j vs. jal

 

MIPS Function Conventions

• Call Function: jump and link (jal , or call)
• Return from function: jump register (jr)
• Arguments: $a0 - $a3 ($4-$7)
• Return value: $v0 - $v1 ($2-$3)

 

Function Calls

//C Code
int main() {
    simple();
    a = b + c;
}

void simple() {
    return;
}

# MIPS assembly code
0x00400200 main: jal simple  #PC + 4 -> $ra
0x00400204 add $s0, $s1, $s2
...

0x00401020 simple: jr $ra

jal : 다음 address(0x00400204), 즉 돌아올 자리를 $ra에 저장시키고 jump한다.

 

void means that simple doesn't return a value

jal: jumps to simple (call)

• $ra = PC + 4 = 0x00400204

jr $ra: jumps to address in $ra (0x00400204) (ret)

 

Input Arguments & Return Value

MIPS Conventions

• Argument values: $a0 - $a3
• Return value: $v0

// C Code
int main() 
{
    int y;
    ...
    y = diffofsums(2, 3, 4, 5); // 4 arguments ,$a0-$a3
    ...
}
int diffofsums(int f, int g, int h, int i)
{
    int result;
    result = (f + g) - (h + i);
    return result; // return value
}

# MIPS assembly code
# $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

s0에 담기는 내용은 $ra 이후에 사라지는가?

만약 main에서 t0, t1, s0를 이미 사용했다면 즉 4개가 넘으면 stack memory을 이용한다.

 

# MIPS assembly code
# $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

• diffofsums overworte 3 register: $t0, $t1, $s0
• diffofsums can use stack to temporarily store registers

 

The Stack

• Memory used to temporarily save variables
• Like stack of dishes, last-in-first-out(LIFO) queue
• Expands: uses more memory when more space needed
• Contracts: uses less memory when the space is no longer needed(pop)
• 스택은 위에서부터 내려오는 방식, 힙은 아래에서 위로 올라가는 방식
• 스택을 사용하기 전에는 쓸 만큼 stack pointer를 증가 시켜서 다음 빈 스택을 가리켜야 하기 때문에 stack pointer를 이동시켜야 한다.
• 즉, stack pointer 전까지의 공간은 누가 사용하고 있는 것
• Grows down (from higher to lower memory address)
• Stack pointer: $sp points to top of the stack

 

How Functions use the Stack

• Called functions must have no unintened side effects
• But diffofsums overwrites 3 registers: $t0, $t1, $s0

# MIPS assembly
# $s0 = result
diffofsums:
    add $t0, $a0, $a1     # $t0 = f + g
    add $t1, $a2, $a4     # $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

 

Storing Register Values on the Stack

• push(sw), pop(lw)

# $s0 = result
diffofsums:
addi $sp, $sp, -12     # make space on stack
                    # to store 3 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

s0, t0, t1을 쓰고 싶어서 잠깐 stack에 저장해 두었다가 사용 후에 다시 변수에 가져오는(restore)

---

Q)$t1,t0, s0에다가 스택 내용을 저장하고 스택 pointer만 옮기는 것이기 때문에 사실상 스택 안에는 그 내용이 유지되어 있는 것인데 스택 포인터 아래에 있는 내용은 그냥 빈 공간 취급하는 것인가?

A) 맞음 override

Q)subroutine에서 모든 걸 다 저장해야하는가?

• 그래서 t와 s로 구분한 것

---

The stack during diffofsums Call

 

Register

s로 시작하는 데이터는 중요한 데이터이기 때문에 다른 function에서 사용후 값을 다시 되돌리는 callee-saved 방식이고 t로 시작하는 데이터는 temporary 데이터이기 때문에 다른 function에서 마음대로 값을 바꿀 수 있기 때문에 main 함수에서 저장해야 하는 caller-saved 방식이다.

# $s0 = result
diffofsums:
    addi $sp, $sp, -4 # make space on stack to 
                      # store one register
    sw $s0, 0($sp)    # save $s0 on stack
                      # no need to save $t0 or $t1
    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 $s0, 0($sp)    # restore $s0 from stack
    addi $sp, $sp, 4  # deallocate stack space
    jr $ra               # return to caller

그래서 t의 내용은 function에서 저장하지 않아도 되기 때문에 addi $sp, $sp, -12가 아니라addi $sp, $sp, -4 이고 (s내용만 저장)

Q)어? 근데 t0가 이미 있어서 스택에 저장해야 되는 것 아닌가?

A) 그게 아니라 t0 내용은 main함수가 아닌 다른 함수에서 마음대로 사용해도 되는 메커니즘이기 때문에 굳이 스택을 만들어 줄 필요없이 0부터 사용하고 싶은대로 사용하는 것이다.

---

f1()으로 jump하기 전에 $ra에 *을 저장하고 jump하고 f1()함수가 종료할 때 jr $ra을 통해 caller로 돌아가게 된다.

그런데 만약 f1() 안에 f2()라는 함수를 호출하면 또 f2로 jump하기 전에 $ra에 f2의 return address가 담기게 되는데 f2가 종료시에 jr $ra(f1()함수의)로 돌아가고 f1에서 함수 종료시 $ra 명령어로 main으로 돌아가야 하는데 현재 $ra에는 f2의 주소가 담겨있기 때문에 이는 stack을 사용하여 해결한다!

즉, main에서 f1()으로 jal할 때 $ra 값이 stack에 push 되었다가 f2()가 호출될때는 $ra에 overriding되어도 f1()에 다시 돌아와서 return address를 할 때에는 stack의 내용을 pop하면 main의 return address값을 가져올 수 있는 것이다.

---

Multiple Function Calls

proc1:
    addi $sp, $sp, -4     # make space on stack
    sw $ra, 0($sp)         # save $ra on stack(push)
    jal proc2             # override current return address to $ra
    ...
    lw $ra, 0($sp)         # restore $s0 from stack
    addi $sp, $sp, 4     # deallocate stack space(원상복귀)
    jr $ra                 # return to caller

 

Recursive Function Call

• Function that calls it self
• When convertint to assembly code:
  • In the first pass, treat recursive calls as if it's calling a different function and ignore overwritten registers.
  • Then save/restore registers on stack as needed.
• ex) Factorial function
  • factorial(n) = n!
    • =n*(n-1)*(n-2)*(n-3) ... *1
  • Example: factorial(6) = 6!=720
  • =6*5*4*3*2*1

// High-level code
int factorial (int n) {
    if (n <= 1)
        return 1;
    else
        return (n * ractorial(n-1));
}

factorial:
    addi $sp, $sp, -8     # save regs
    sw $a0, 4($sp)
    sw $ra, 0($sp)
    addi $t0, $0, 2
    slt $t0, $a0, $t0     # a <= 1 ?
    beq $t0, $0, else     # no: go to else
    addi $v0, $0, 1     # yes: return 1
    addi $sp, $sp, 8     # restore $sp
    jr $ra                 # return
else:
    addi $a0, $a0, -1     # n = n - 1
    jal factorial         # recursive call
    lw $ra, 0($sp)         # restore $ra
    lw $a0, 4($sp)         # restore $a0
    addi $sp, $sp, 8     # restore $sp
    mul $v0, $a0, $v0     # n*factorial(n-1)
    jr $ra                 # return

 

Stack During Recursive Call

 

Function Call Summary

• Caller
  • Put arguments in $a-$a3
  • Save any needed registers ($ra, maybe $t0-t9)
  • jal callee
  • Restore registers
  • Look for result in $v0
• Callee
  • s register만 저장
  • Save registers that might be disturbed ($s0-$s7)
  • Perform function
  • Put result in $v0
  • Restore registers
  • jr $ra

 

Addressing Modes

How do we address the operands?

• Register Only
  • add $5, $6, $7
• Immediate
  • addi $5, $6, -3
• Base Addressing
  • lw $1, 4($2) <- data memory
• PC-Relative
  • beq $1, $2, Label <- prog. mem.
• Pseudo Direct
  • J Label <- prog. mem.

 

Addressing Modes

How do we address the operands?(In MIPS)

• Register Only
• Immediate
• Base Addressing
• PC-Relative
• Pseudo Direct

 

Register Only

• Operands found in registers
  • Example: add $s0, $t2, $t3
  • Example: sub $t8, $s1, $0
• Immediate
  • 16-bit immediate used as an operand
    • Example:addi $s4, $t5, -73
    • Example: ori $t3, $t7 0xFF

 

Base Addressing

• Address of operand is:
  base address + sign-extended immediate
• Example: lw $s4, 72($0)
  • $0은 data memory의 address
  • address = $0 + 72
• Example: sw $t2, -25($t1)
  • address = $t1 - 25

 

PC-Relative Addressing

• Program memory
• 우리는 label을 그냥 사용하면 되지만 예를 들어 else: 로 가야할 때 PC에서 얼마만큼 떨어진 곳으로 가야 하는 지를 알아야 한다.
• Program memory address

0x10         beq $t0, $0, else
0x14         addi $v0, $0, 1 
0x18         addi $sp, $sp, i
0x1C         jr $ra
0x20     else: addi $a0, $a0, -1
0x24         jal factorial

위와 같은 경우에 beq에서 $t0와 $0가 같으면 else로 jump하는데 이 때 4칸을 뛰어야 한다.

그런데 PC에서는 미리 다음 주소로 이동하기 위해 값을 다음으로 지정해 놓고 있기 때문에 3칸만 뛰어도 되는 것이다.

BTA(Branch Target Address) = (PC + 4) + (Imm<<2)

• 4를 더한 것은 PC가 다음으로 이동하기 위해 미리 한 칸 가 있는 것이고 imm(3)에 left shift를 2번하면 x4의 효과가 있기 때문에 한 것이다.(따라서 (PC+4) + 3*4)

 

Pseudo-direct Addressing

0x0040005C             jal sum
...
0x004000A0         sum: add $v0, $a0, $a1

• 26bit밖에 없는데 32bit를 만들어야 하는 경우
  • JTA(Jump Target Address)
  • 맨 뒤에 2 비트를 0으로 채움
  • 맨 앞의 4bit(한 바이트)는 PC에서 그대로 가져온다.
  • J타입은 원래 어디로 jump 할 지를 바로 정해주는 direct addressing인데 여기서 32bit를 만들기 위해 앞의 4bit는 PC에서 왔기 때문에 Pseudo-direct addressing이라고 한다.

 

How to Compile & Run a Program

What is Stored in Memory?

• Instructions (also called text)
• Data
  • Global/static: allocated before program begins
  • Dynamic: allocated within program
• How big is memory?
  • At most 2³² = 4 gigabytes (4 GB)
  • From address 0x00000000 to 0xFFFFFFFF

 

MIPS Memory Map

• Text segment: 256MB
• Global data segment: 64 KB, accessed by $gp
• $gp does not change during execution (unlike $sp)
• Reserved: I/O 영역(위) 과 OS(아래)가 사용하는 공간

 

Example RISC-V Memory Map

address는 다르지만 기본적인 구조는 매우 유사함(MIPS와)

 

Example Program: C Code

int f, g, y; // global variables
int main(void) 
{
    f = 2;
    g = 3;
    y = sum(f, g);

    return y;
}
int sum(int a, int b) {
    return (a + b);
}

 

Example Program: compiling

.data
f:
g:
y:
.text
main:
    addi $sp, $sp, -4     # stack frame
    sw $ra, 0($sp)         # store $ra
    addi $a0, $0, 2     # $a0 = 2
    sw $a0, f             # f = 2 ; label을 그냥 그대로 써도 됨
    addi $a1, $0, 3     # $a1 = 3
    sw $a1, g             # g = 3
    jal sum             # call sum
    sw $v0, y             # y = sum()
    lw $ra, 0($sp)         # restore $ra
    addi $sp, $sp, 4     # restore $sp
    jr $ra                 # return to OS
sum:
    add $v0, $a0, $a1     # $v0 = a + b
    jr $ra                 # return

 

Example Program: Symbol Table

f,g,y : data memory

main, sum: program memory(text memory)

 

Example Program: linking (Executable)

sw $a0, 0x8000($gp)가 의미하는 것:

global pointer는 memory의 global data 공간을 가리키고 있는데 이 공간에서 0x8000만큼 떨어진 곳으로 store하라는 것인데 0x8000은 맨 앞의 8이 이진수로 '1000'을 나타내고 이는 -8이기 때문에 -8000을 의미하는 것인데, 0x10008000에 있던 $gp 가 0x10000000으로 가서 f를 저장하고 g를 저장할 때는 0x8004만큼 움직이면 -7996을 의미하는 것이기 때문에 f를 저장한 곳보다 4만큼 위의 공간에 저장하는 것이다.

 

Example Program: loading (in memory)

• OS loads the program from storage
• OS sets $gp=0x10008000, and $sp= 0x7ffffffc, and jump to the beginning of the program (jal 0x00400000).
• Reserved area: memory-mapped I/O, interrupt vector

---

Lab 1: MIPS Assembly Programming

MIPS을 해보는 것처럼 실행할 수 있는 runtime simulator인 MARS로 구동시킬 것임

---

Odds & Ends (Misc.)

• Pseudo-instructions
  • Not a part of ISA, but commonly used
  • assembler가 진짜 instruction으로 바꿔줌
• Exceptions(interrupt)
  • Unscheduled function call(예기치 않은 function call)
  • Exception handler is at 0x80000180
• Signed and unsigned instructions
• Floating-point instructions

 

Pseudoinstruction

• li $s0, 0x1234AA77 (load immediate) : 32bit를 immediate로 쓸 때에는 두 과정으로 나누어 준다.
  • lui / ori

 

Exception

• Unscheduled function call to exception handler
• Caused by:
  • Hardware, also called an interrupt, e.g., keyboard
  • Software, also called traps, e.g., undefined instruction
• When exception occurs, the processor:
  • Records the cause of the exception (원인을 저장)
  • Jumps to exception handler (at instruction address 0x80000180)
  • Returns to program

 

Exception Registers

• Not part of register clk
  • Cause: Records cause of exception
  • EPC (Exception PC): Records PC where exception occurred
    • exception handler에서 다 처리한 후 다시 돌아올 자리
• EPC and Cause: part of Coprocessor 0
• Move from Coprocessor 0
  • mfc0 $t0, EPC
  • Moves contents of EPC into $t0

 

Exception Causes

 

Exception Flow

• Processor saves cause and exception PC in Cause and EPC
• Processor jumps to exception handler (0x80000180)
• Exception handler:
  • Saves registers on stack
    • 내가 사용할 register 저장(어떤 register가 문제인지 모르기 때문에)
  • Reads Cause register
    • mfc0 $k0, Cause
  • Handles exception
  • Restores registers
  • Returns to program
    • mfc0 $k0, EPC //$k0, $k1 reserved by OS jr $k0
    • jr $k0

 

Exception Example

• Example: read one input from a keyborad (assum interrupt is enabled)

$k0-$k1 : OS temporaries

 

Signed & Unsigned Instructions

• Addition and subtraction
• Multiplication and division
• Set less than

 

Addition & Subtraction

• Signed: add, addi, sub
  • Same operation as unsigned versions
  • But processor takes exception on overflow
• Unsigned: addu, addiu, subu
  • Doesn't take exception on overflow

Note: addiu sign-extends the immediate (two versions are identical except exception is triggered.)

 

Mul

• Signed: mult, div
• Unsigned: multu, divu

ex) 0xFFFF_FFFF * 0xFFFF_FFFF

=> 0xFFFFFFFE00000001 (unsigned)

=> 0x0000000000000001 (signed)

 

Set Less Than

• Signed: slt, slti
• Unsigned: sltu, sltiu

Note: sltiu sign-extends the immediate before comparing it to the register.

 

Loads

• Signed:
  • Sign-extends to create 32-bit value to load into register
  • Load halfword: lh
  • Load byte: lb
• Unsigned:
  • Zero-extends to create 32-bit value
  • Load halfword unsigned: lhu
  • Load byte: lbu

 

Floating-Point Coprocessor(or Accelerator)

별로 중요하지 않음, 내부가 중요함

 

Example design

 

Floating-Point Instructions

• Floating-point coprocessor(Coprocessor 1)
• 32 32-bit floating-pointer registers($f0-$f31)
• Double-precision values held in two floating point registers
  • e.g., $f0 and $f1,$f2 and $f3, etc.
  • Double-precision floating point registers: $f0, $f2, $f4, etc.

F-Type Instruction Format

• Opcode = 17 (010001₂)
• Single-precision:
  • cop = 16 (010000₂)
  • add.s , sub.s, div.s, neg.s, abs.s, etc.
• Double-precision:
  • cop = 17 (010001₂)
  • add.d, sub.d, div.d, neg.d, abs.d, etc.

 

Floating-Point Branches

• Set/clear condition flag: fpcond
  • Equality: c.seq.s, c.seq.d
  • Less than: c.lt.s, c.lt.d
  • Less than or equal: c.le.s, c.le.d
• Conditional branch
  • bclf: branches if fpcond is FALSE
  • bclt: branches if fpcond is TRUE
• Loads and stores
  • lwc1: lwc1 $ft1, 42($s1) ; load coprocessor 1
  • swc1: swc1 $fs2, 17($sp)

 

ARM & MIPS instruction set

난이도: MIPS < RISC-V < ARM

ARM은 복잡, MIPS은 비교적 쉬움, 이 사이에 있는 것이 RISC-V

---

Q)

A)handling하는 방식이 processor마다 조금씩 다를 수 있다.

Q)floating point /single, double

A)

범위가 틀린 것

single precision

• 32 bit
• float a;

double precision

• 64bit
• double b;

Q)unsigned에서는 overflow가 일어나지 않는데 이를 어떻게 처리하는 것인가?

A)있을 수 있으나 무시하여 발생하지 않도록 설계하는 것이다.

---