2. MIPS : Program Execution

Program Execution

프로그램의 실행은 abstraction level의 관점에서 크게 2가지로 분류할 수 있다.

 

Abstraction Level

Abstraction level은 HLL과 ISA로 나뉜다.

• HLL(High-Level Language)
  • 생산성을 높이기 위한 interface
  • machine language의 interface
• ISA
  • HW/SW interface

 

Program Execution

Abstraction level에 따라 아래처럼 나뉠 수 있다.

결국 HLL의 관점에서 프로그램의 실행은 procedure call-return의 반복으로 볼 수 있다.

 

• HLL 관점
  • statement, function이 하나씩 실행되는 과정
    * statement, function : HLL의 primitive
  • object level
    • object끼리 message를 주고 받는 것은 실행차원에서 결국 function call-return의 반복이다.
  • procedure level
    • = function level
    • function(procedure) call-return이 반복된다.
  • statement level
    • 하나의 statement가 어떻게 machine instruction으로 바뀌어 실행되는가
• ISA 관점
  • machine instruction이 하나씩 실행되는 과정 
  • machine instruction level
    • HW-SW interface
    • machine instruction이 하나씩 실행되는 과정
  • processor internal level
    • fetch-decode-execute
    • machine instruction보다 low level이다.

 

---

Procedure Calls

Procedure call(function call)은 프로그램 실행에 있어서 가장 fundamental한 행동이다.

 

프로그램에서 procedure call-return의 흐름을 나타낸 것을 procedure call graph라고 한다.

가장 바깥쪽에 있어서 다른 function을 call 하지 않는 function을 leaf procedure라고 한다.

 

함수를 호출하는 것을 caller, 호출 당하는 함수를 callee라고 한다.

대부분의 procedure는 둘 다의 역할을 하지만, leaf procedure는 callee의 역할만 한다.

procedure call graph

 

---

Leaf Procedure

함수 call-return 과정

함수의 호출 과정은 다음과 같다.

1. Caller
   1. 함수의 parameter를 callee가 접근할 수 있게 한다.
      • 어떻게 parameter를 넘길 것인가? <pre>$a0-$a3</pre>
   2. callee로 jump한다.(jump and link, <pre>jal</pre>)
      • return address를 어디에 저장할 것인가? <pre>$ra</pre>
2. Callee
   1. 연산에 필요한 register를 acquire한다.
      • 만약 caller가 해당 register에 의미있는 값을 넣고 사용 중이라면? Caller가 사용하던 register의 값은 어떻게 할 것인가? : Stack에 저장
   2. 작업을 수행한다.
   3. return value를 caller가 접근할 수 있게 한다.
      • return value를 어떻게 넘길 것인가? <pre>$v0-$v1</pre>
   4. caller의 위치로 돌아간다.(jump register, <pre>jr $ra</pre>)

 

Program execution은 procedual call-return의 연속일 정도로 fundamental하고 꽤 common case이다.

따라서 프로세서는 이를 빠르게 처리해줘야 한다.

이를 위해 값의 저장/넘기기를 위해서 레지스터를 이용한다.

 

Parameter, Return Value 저장

• Parameter 넘기기
  • <pre>$a0 - $a3</pre>
    • 4개의 argument register을 사용하여 parameter로 넘긴다.
    • argument passing 전용으로 사용한다.
    • 더 많은 레지스터를 argument passing을 위해 사용한다면 다른 용도로 사용할 레지스터의 수가 적어지게 된다. 따라서 더 많은 레지스터를 argument register를 위해 할당하지 않는다.
    • 벤치마크 분석을 하면 대부분의 function들은 4개 이하의 argument를 사용하기 때문에 argument register로 4개로 지정을 한다.
• Return value 넘기기
  • <pre>$v0 - $v1</pre>
    • return value를 위해 2개의 register를 사용한다.
    • return value passing 전용으로 사용한다.
    • C에서는 항상 1개의 return value만 사용한다. 그러나 double type은 64bit로, 이를 return 하기 위해서는 2개의 레지스터를 사용해야 한다. 때문에 2개의 레지스터를 할당한 것이다.
    • 여러 item을 return 할 때는 그 item들을 structure로 만들어서 포인터를 return하거나, external variable(global variable)을 사용한다.
• Return address 저장
  • <pre>$ra</pre>
    • return address를 저장하기 위한 레지스터이다.
    • MIPS에서는 $r31을 $ra로 사용한다.

 

참고 : MIPS의 레지스터

MIPS의 레지스터 name은 procedual call-return의 관점에서 지어진다.

그만큼 procedual call-return이 fundamental 한 것임을 시사한다.

MIPS의 레지스터 분류

 

---

Coordinating Register Usage (Acquire Register)

Acquire Register가 필요한 이유

연산에 필요한 레지스터에 caller에서 의미있는 값을 넣어놨을 수도 있다.

따라서 사용할 레지스터들은 사용 전에 들어있는 값들을 옮겨놔야 한다.

 

즉, callee가 레지스터에 들어있는 caller의 데이터를 변경할 수 있기 때문에 문제가 발생하는 것이다.

 

예를 들어, callee의 코드가 아래와 같다면 t0, t1, s0에 있는 값들을 사용 전에 옮겨놔야 한다.

add $t0, $a0, $a1
add $t1, $a2, $a3 
sub $s0, $t0, $t1 
add $v0, $s0, $zero	// set return value

 

따라서 다음과 같은 과정을 통해 사용할 레지스터의 값들을 stack에 옮겨놓고 연산을 해야 한다.

연산이 끝난 후에는 다시 stack에서 값들을 불러와서 register를 복원시켜야 한다.

// save $t1, t0, s0 in stack
addi $sp, $sp, -12
sw $t1, 8($sp)
sw $t0, 4($sp)
sw $s0, 0($sp)

add $t0, $a0, $a1
add $t1, $a2, $a3 
sub $s0, $t0, $t1 
// set return value
add $v0, $s0, $zero	

// restore $t1, t0, s0 from stack
lw, $s0, 0($sp)		
lw, $t0, 4($sp) 
lw, $t1, 8($sp) 
addi $sp, $sp, 12

// jump back to caller
jr $ra

 

 

일반적인 Coordinating Register Usage

Caller의 레지스터 값들을 스택에 넣고 복원하는 방법은 두 가지가 있다.

MIPS에서는 caller saving에 가까운 혼합된 방법을 사용한다.

 

두 경우 다 pessimistic이다.

실제로 레지스터에 중요한 값이 들어있는지는 모르지만 사용할(사용한) 레지스터의 값들을 backup한다.

 

• Callee saving
  • 레지스터에 대한 모든 책임이 callee에게 있는 것이다.
  • register saving-restore를 항상 callee가 한다.
  • pessimistic
    • 컴파일러는 레지스터에 실제로 의미있는 값이 들어있는지는 모른다. 그러나 항상 최악의 경우를 가정해야 하기 때문에 항상 callee가 사용하는 모든 register를 backup한다.
• Caller saving
  • 레지스터에 대한 모든 책임이 caller에게 있는 것이다.
  • register saving-restore를 항상 caller가 한다.
  • pessimistic
    • 컴파일러는 레지스터에 실제로 의미있는 값이 들어있는지는 모른다. 그러나 항상 최악의 경우를 가정해야 하기 때문에 항상 caller가 사용하는 모든 register를 backup한다.

 

MIPS Coordinating Register Usage

MIPS는 계산에 사용되는 레지스터를 두 그룹으로 나눈다.

 

이름은 caller 입장에서 생각하면 된다.

Callee가 알아서 save-restore한다면 caller 입장에서 항상 원래의 값이 보장되기 때문에 "saved"이다.

반면 caller가 스스로 save-restore한다면 caller 입장에서 항상 변한다고 가정하는 것이기 때문에 "temporary"이다.

 

• saved register(<pre>$s</pre>)
  • callee saving
  • callee에서 사용할 레지스터를 callee에서 save-restore한다.
  • callee가 save-restore 하기 때문에 caller 입장에서는 항상 값이 보장(saved)된다.
  • main을 제외한 모든 function에서는 $s을 쓰기 전 스택에 저장해야 한다. main을 호출하는 함수는 없기 때문이다.

• temporary register(<pre>$t</pre>)
  • caller saving
  • caller에서 자신이 사용한 레지스터를 save-restore한다.
  • caller가 스스로 save-restore해야하기 때문에 caller 입장에서 항상 값이 달라진다(temporary)고 가정한다.

 

따라서 컴파일 할 때는 callee 입장이 되므로 $t는 그냥 사용한다.

$s는 사용 전에 반드시 스택에 저장하고 연산 후에는 다시 복구해야 한다.

• 만약 <pre>$t</pre>를 다 사용해도 부족하다면 <pre>$s</pre>을 사용한다.
  • 단, $s를 사용하기 전에 스택에 값을 저장해야 한다.
  • $s에 저장하는 과정이 필요하기 때문에 실행 속도가 늦어진다.
• 만약 <pre>$t</pre>에 <pre>$s</pre>까지 사용해도 부족하다면 메모리에 저장해서 사용한다.
  • 단, 메모리에는 접근하는 속도가 떨어지기 때문에 실행 속도가 늦어진다.

 

만약 callee(f1)에서 다른 함수(f2)를 call 한다면 f1은 caller가 되므로 $t register들을 backup해놔야 한다.

Callee saving과 caller saving 중에 어떤 것이 더 좋은지, 몇개를 $s로 사용하고 몇개를 $t로 사용하는 것이 좋은지는 벤치마크를 분석하여 파악한다.

 

따라서 위에서 확인했던 예제는 다음과 같이 줄어든다.

// save $s0 in stack
addi $sp, $sp, -4
sw $s0, 0($sp)

add $t0, $a0, $a1
add $t1, $a2, $a3 
sub $s0, $t0, $t1 
// set return value
add $v0, $s0, $zero	

// restore $s0 from stack
lw, $s0, 0($sp)
addi $sp, $sp, 4

// jump back to caller
jr $ra

 

그런데 여기서 <pre>sub $s0, $t0, $t1</pre>과 <pre>add $v0, $s0, $zero</pre>는 하나로 합칠 수 있다.

결국 $s0는 사용할 필요가 없어지고, 그에따라 스택에 save-restore 할 필요 없어진다.

따라서 아래와 같이 줄일 수 있다.

add $t0, $a0, $a1
add $t1, $a2, $a3 
sub $v0, $t0, $t1 

// jump back to caller
jr $ra

 

예제

void strcpy (char x[], char y[]) {
	int i;
  	i = 0;
  	while ((x[i]=y[i])!='\0')
      	i += 1; 
}