[Computer Architecture] (4-5) RISC-V Control Transfer Operation

Control Transfer Operation은 특정 조건에 따라 동작이 달라지는 것을 말한다. 대표적으로 Branch 동작이 있다. Branch 동작은 특정조건이 만족되면 지정된 위치로 이동하고, 만족되지 않으면 다음 Instruction을 수행하도록 한다.

아래와 같이 조건에 따라 L1의 위치로 갈지 말지를 결정할 수 있다.

// branch equal
beq rs1, rs2, L1 # if(rs1 == rs2) goto L1

// branch not equal
bne rs1, rs2, L1 # if(rs1 != rs2) goto L1

C 언어에서 조건문은 if, while, for 문 등이 존재한다. 이 중 if문을 사용한 코드를 Instruction으로 변경해 보자.

// C code
if (i == j)
 f = g + h;
else
 f = g - h; 
 
// instruction friendly code
// i in x22, j in x23
// f in x19, g in x20, h in x21
if (i!=j) goto Else:    #      bne x22, x23, Else
 f = g + h;             #      add x19, x20, x21
 goto Exit;             #      beq x0, x0, Exit  // unconditioanl, x0 = 0(hardwired)
Else:                   # Else:
 f = g - h;             #      sub x19, x20, x21
Exit                    # Exit: ...

위의 C 코드를 아래 왼쪽과 같이 if / goto / else & Exit로 표현하였고, 이를 토대로 아래 오른쪽과 같이 Instruction으로 표현하였다. 즉, C 코드를 if + goto 와 jump를 수행할 위치로 표현하면, Instruction으로 변환하기 쉬워진다.

다음으로는 아래와 같이 while문을 사용한 코드를 살펴보자. while 문을 Loop 구문으로 변경하고, 이를 이용하여 Instruction으로 변경하였다.

// C code
while (A[i] == k)
 i+=1;
 
 
// instruction friendly code
// i in x11, k in x22
// A[] in x33
Loop:                        # Loop:
 if(A[i] != k) goto Exit     #      slli x44, x11, 3     // x44 = 8*i
 i+=1;                       #      add  x44, x44, x33   // x44 = A[] * 8*i
 goto Loop;                  #      ld   x55, 0(x44)     // x55 = M[A[i]]
Exit:                        #      bne  x55, x22, Exit  // if(A[i] !=k) goto Exit
                             #      addi x11, x11, 1    // i=i+1
                             #      beq  x0, x0, Loop    // goto Loop
                             # Exit: ...

Basic Blocks이란 중간에 Branch Target이 없고, Branch 또한 없는 연속적인 Instruction들을 의미한다.

(Branch Target은 맨처음 가능, Branch는 맨 마지막 가능)

Compiler가 이를 파악하여 최적화를 하는 데 사용한다.

또 다른 Branch 종류들을 살펴보자. 작거나, 크거나 같다는 조건도 만들어서 수행할 수 있다.

// branch less than 
blt rs1, rs2, L1 # if(rs1 < rs2) goto L1

// branch greater than or equal
bge rs1, rs2, L1 # if(rs1 >= rs2) goto L1

기본적인 비교는 Signed로 수행되나 Unsigned로 비교하기 위한 Instruction도 존재한다.

// rs1 -> signed :: -1, unsigned : 2^64-1
// rs2 -> signed :: 1, unsigned : 1

// branch less than 
blt rs1, rs2, L1 # if(rs1 < rs2) goto L1   // if(-1 < 1) goto L1

// branch less than, Unsigned
bltu rs1, rs2, L1 # if(rs1 >= rs2) goto L1 // if(2^64-1 < 1) goto L1

그런데 Branch Instruction에서 Traget 주소를 L1이라고 표현하였다. L1은 실제 Instruction에서 어떻게 표현할 수 있을까?

우선, Instruction의 위치 특성을 파악해 보자. 기본적으로 RISC-V의 Instruction 크기는 일반적으로 32-bit이나, Compress Extention을 사용하면 16-bit으로도 사용가능하다. 메모리는 Byte-addressable 이므로 가장 작은 Instruction 크기(2B)를 가질 때, Instruction의 위치는 짝수 주소마다 존재하게 된다. 짝수 주소는 정수*2로 표현되므로 이 정수 값을 Instruction bit으로 사용하고, 실제 계산은 2를 곱하여 진행된다.

모든 메모리의 주소를 표현하려면 많은 bit이 필요하다. 그런데 프로그램들을 잘 살펴보면, Branch Target 주소는 현재 주소가 크게 멀지 않다. 즉, 대부분의 Branch Instruction의 경우, Branch Target은 지금 위치(PC)로부터 앞에 있거나 뒤에 존재한다. 따라서 아래와 같이 Base Address를 지금 위치(PC)로 설정하고, Offset를 입력받아 Target 주소를 만들어 표현해도 충분하다.

Target address = PC + signExt(12-bit immediate value << 1)

아래와 같이 Branch는 SB-Type을 사용하고, Target address를 표현하기 위한 imm12가 존재한다.

또 다른 Branch의 사용 예는 특정 함수로 이동하여 수행하는 경우이다. 코드 상에서 특정 함수를 수행하고, 다시 돌아와 나머지 코드를 수행하게 된다. 그런데 다시 돌아오려면 돌아올 주소값을 저장하고 있어야 한다. 이런 동작은 많이 발생하므로 효율적으로 하기 위하여 Jump를 하면서, 동시에 돌아올 주소 값을 저장할 수 있도록 한다. 아래 예제처럼 bar(x)를 수행하고 나면 z = y + 1를 수행해야 하므로 해당 주소를 저장하고 있어야 한다.

// jump and link
jal rd, imm20 # rd = PC + 4; PC = PC + SignExt(imm20<<1) // UJ Type

이 'jal'을 사용할 때, x0(hardwired zero)를 활용하여 Return address를 저장하지 않고, 그냥 Jump를 하도록 할 수 도 있다.

// jump and link ->> not link
jal x0, imm20 # x0(hardwired zero) = PC + 4; PC = PC + SignExt(imm20<<1) // UJ Type

ra(return address)를 활용하여 Function을 수행하고 다시 돌아올 수도 있다.

// jump and link ->> call function and return
jal ra, imm20 # ra(return address) = PC + 4; PC = PC + SignExt(imm20<<1) // UJ Type

그런데, 많은 경우가 PC-relative addressing을 사용하다고 하지만, 위 방식으로 표현할 수 없는 주소로 이동하는 경우도 있다. 구체적으로 아래와 같이 Target address가 해당 범위 밖이라면 표현 불가능 한 것이다.

// signed 12-bit   : -2^11 <= x <= 2^11-1
// 2*signed 12-bit : -2^12 <= x <= 2^12-2
// PC + 2*signed 12-bit
PC - 2^12 <= x <= PC + 2^12-2

이를 해결하기 위해, 아래와 같이 Register에 저장된 값으로 Jump를 수행할 수 있는 Instruction이 존재한다.

// jump and link Register
jalr rd, imm12(rs) # rd = PC + 4; PC = rs + imm12 // I-Type

아래와 같이 'jalr'를 이용하여 Return을 수행할 수 도 있다.

// jump and link Register -> return to ra
jalr x0, 0(ra) # x0(hardwired zero) = PC + 4; PC = ra + 0 // I-Type

아래와 같이 32-bit 절대 주소의 함수를 호출할 수 도 있다.

// load upper immediate  -> high 20-bit
// jump and link Register-> jump to (high 20-bit + low 12-bit) address
lui x1, <high 20-bits>
jalr x0, <low 12-bits>(x1) # x0(hardwired zero) = PC + 4; PC = x1 + <low 12-bits> // I-Type

또한 PC-relative with 32-bit offset도 가능하다.

// Add Upper immediate PC  -> PC + high 20-bit
// jump and link Register-> jump to (PC + high 20-bit + low 12-bit) address
auipc x1, <high 20-bits>
jalr x0, <low 12-bits>(x1) # x0(hardwired zero) = PC + 4; PC = x1 + <low 12-bits> // I-Type

몇 가지 예제에 대해서 살펴보도록 하겠다.

1. If Statement Example

// C code
long max (long x, long y)
{ 
 if (x > y)
  return x;
 else
  return y;
 }

// instruction friendly code
long max (long x, long y)
{
 if(y>=x)
  goto done;
 y=x;
done:
 return y;
}

// x is in a0
// y is in a1

max:
    bqe  a1, a0, L1  # if(y>=x) goto L1
    addi a1, a0, 0   # y = x + 0
L1: 
    addi a0, a1, 0   # return y -> a0 -> return register
    jalr x0, 0(ra)   # ret

2. do-while Loop Example

long fact_do (long x)
{
 long result = 1;
 do{
  result *=x;
  x = x - 1;
 } while (x > 1);
 return result;
}

// instruction friendly code
long fact_do (long x)
{
 long result = 1;
LOOP:
   result *=x;
   x = x - 1
   if(x>1) goto Loop;
   return result;
}

// instruction
// x is in a0
fact_do:
        addi a5, a0, 0  # a5 = x
        addi a0, x0, 1  # a0 = 1
L2:
        mul a0, a0, a5  # result *= x
        addi a5, a5, -1 # x = x - 1
        addi a4, x0, 1  # a4 = 1
        bgt  a5, a4, L2 # if (x>1) goto L2
        jalr x0, 0(ra)  # ret

3. While Loop Example

long fact_while (long x)
{
 long result = 1;
 while (x > 1){ 
  result *=x;
  x = x - 1;
 }
 return result;
}

// instruction friendly code
long fact_while (long x)
{
 long result = 1;
LOOP:
   if(x<=1) goto Exit;
   result *=x;
   x = x - 1
   goto Loop;
Exit:
   return result;
}

// instruction
// x is in a0
fact_while:
        addi a5, a0, 0  # a5 = x
        addi a0, x0, 1  # a0 = 1   
L2:
        addi a4, x0, 1  # a4 = 1            // Loop 를 수행할 필요 없음.
        ble  a5, a4, L4 # if(x <=1) goto L4 // Loop 시작 여부 체크 -> 중복
        mul a0, a0, a5  # result *= x
        addi a5, a5, -1 # x = x - 1        
        beq  x0, x0, L2 # goto L2           // Loop 시작 여부 체크 -> 중복
L4:        
        jalr x0, 0(ra)  # ret
        
// modified instruction
// x is in a0
fact_while2:
        addi a5, a0, 0  # a5 = x
        addi a0, x0, 1  # a0 = 1   
        addi a4, x0, 1  # a4 = 1            // Loop 를 수행할 필요 없음.
        ble  a5, a4, L4 # if(x <=1) goto L4 // Loop 시작 여부 체크(1번만)
L2:
        mul a0, a0, a5  # result *= x
        addi a5, a5, -1 # x = x - 1        
        bne  a5, a4, L3 # if(x!=1) goto L3  // Loop 시작 여부 체크
L4:        
        jalr x0, 0(ra)  # ret

4. Foor Loop -> while -> do-while -> goto version!!

for loop은 위의 시작 interator를 하나 두고 수행한다.

저작자표시

'IT_Study > CS_Study' 카테고리의 다른 글

[Computer Architecture] (6) Array vs Pointer (2)	2024.04.28
[Computer Architecture] (5) RISC-V Procedure Call (1)	2024.04.28
[Computer Architecture] (4-4) RISC-V Data Transfer Operation (1)	2024.04.28
[Computer Architecture] (4-3) RISC-V Arithmetic / Logical Operation (0)	2024.04.27
[Computer Architecture] (4-2) RISC-V Register 설명 (0)	2024.04.27

소소하게 일상을 기록하는 페이지

[Computer Architecture] (4-5) RISC-V Control Transfer Operation

'IT_Study > CS_Study' 카테고리의 다른 글

댓글

티스토리툴바

[Computer Architecture] (4-5) RISC-V Control Transfer Operation

'IT_Study > CS_Study' 카테고리의 다른 글

관련글

댓글

티스토리툴바