Instructions for Making Decisions

 If-then-else

컴퓨터와 단순 계산기와 다른점은 바로 판단할 수 있는 기능이다. input과 계산된 결과값에 따라서 컴퓨터는 다른 instruction을 수행할 수 있다. 주로 Java나 C와 같은 high-level programming language에서는 if statement를 이용한다. (때로는 go to도 사용한다). RISC-V assembly language는 go to 가 있는 if statement와 비슷한 두개의 decision-making instructions, 즉 판단 명령어가 있다. 첫번째로는 다음과 같다.

beq rs1, rs2, L1

rs1의 값이 rs2의 값과 같으면, L1에 해당하는 문장으로 가라는 뜻이다. beq는 branch if equal 을 의미한다. 다음 명령어는 다음과 같다.

bne rs1, rs2, L1

beq와 반대로 rs1과 rs2가 같지 않으면, L1으로 가라는 뜻이다. bne는 branch (if) not equal 을 의미한다. 다음 예시를 보자.

 

Compiling if-then-else into Conditional Branches

In the following code segment, f, g, h, i, and j are variables. If the five variables f through j correspond to the five registers x19 through x23, what is the compiled RISC-V code for this C if statement?

if (i == j) f = g + h; else f = g −h;

f, g, h, i, j라는 값이 있고, 각각의 값은 레지스터 x19부터 x23까지에 저장되어있을 때, 주어진 if-else를 RISC-V로 표현하라는 문제이다. 가장 기본적인 if-else로, 만약, i == j 이면, g + h를 하고, 아니면, g - h 를 해서 f에 저장하는 문제이다. 반복 없이 프로그램은 끝나게 된다. 먼저, i 와 j 값이 같지 않은지 bne를 이용해서 검사한 후, 같지 않을경우, Else로 보낸다.

bne x22, x23, Else // go to else if (i != j)

이후, 아래의 instructions에 도달한다는것은 i 와 j의 값이 같다는 말이므로, g(x20) 와 h(x21)를 저장 후, f(x19)에 저장해준다.

add x19, x20, x21 // f = g + h

이 명령을 실행했다면, 중간에 모든 과정을 스킵한 후, Exit으로 가야한다. 그러므로, 항상 참인 값을 넣어서 Exit으로 향하게 한다.

beq x0, x0, Exit // if (0 == 0), go to Exit

i 와 j가 같지 않을 경우에 처리를 해줘야한다. 아래와같이 계산해서 f에 저장해준다. 이후, Exit 해준다.

Else: sub x19, x20, x21 // f = g - h
Exit:

 

Loops

Compiling a while Loop in C

Here is a traditional loop in C:

while (save[i] == k){
    i += 1;
}

Assume that i and k correspond to registers x22 and x24 and the base of the array save is in x25. What is the RISC-V assembly code corresponding to this C code?

i의 값이 레지스터 x22에, k의 값이 레지스터 x24에 저장되어있고, save의 base address가 x25에 저장되어있을 때, 위의 while loop을 RISC-V assembly code로 나타내라는 문제이다. 첫번째로, save[i]를 임시 레지스터로 가지고 와야하는데, 그러려면 주소를 구해야한다. i 는 1씩 늘어나지만, 실제 주소값은 8씩 늘어나기때문에, 인덱스가 4라면 base address로부터 32만큼 떨어진곳이 save[i]의 주소이다. 그러므로, 이전 포스트에서 다루었던 slli를 이용해서 계산할 수 있다.

Loop: slli x10, x22, 3 // Temp reg x10 = i * 8

이후, x25에 있는 base address에 위에서 계산된 x10에 저장된 값을 더해서 다시 x10에 저장해주면, 그것이 save[i]의 주소가 된다.

add x10, x10, x25 // x10 = address of save[0] + i * 8 = address of save[i]

이제, 임시 레지스터에 save[i]에 있는 값을 load해온다. 이것 또한 이전 글에서 언급했던 ld(load doubleword)를 이용한다.

ld x9, 0(x10) // Temp reg x9 = save[i]

이제, 로드된 값을 k와 비교해서 같으면 프로그램을 끝내고, 아니라면 loop안에 있는 작업을 해주어야 한다. bne를 이용해본다.

bne x9, x24, Exit // save[i](x9) != k(x24), then go to Exit.

그렇지 않다면, i 에 1을 더한다. 이는 addi를 사용해서 바로 더해줄 수 있다.

addi x22, x22, 1 // i = i + 1

앞의 조건이 충족되지 않았기때문에 Loop으로 돌아간다. bne에서 같지 않았을경우, 그 아래 Exit 레이블로 가서 연산이 끝난다.

beq x0, x0, Loop // Go to Loop
Exit:

 

Comparison

RISC-V B-Types

위의 beq, bne이외에도 비교를 하는 instruction에는 blt, bge, bltu, bgeu등이 있다. 설명은 이미지에 나와있으니 생략한다.

 

Bounds Check Shortcut

부호가 있는 수를 부호가 없는것처럼 다루면 $ 0 <= x < y $를 계산할 때, 효율적으로 계산할 수 있다. 그래서 x < y를 체크하면, x가 y보다 작은지 뿐만 아니고 x의 부호가 무엇인지도 체크할 수 있다. 이는, two's complement를 이용해서 앞자리가 모두 1이기 때문에, 아주 큰 숫자가 된다. 아래 예시를 보자.

Reduce an index-out-of-bounds check: branch to IndexOutOfBounds if x20 ≥ x11 or if x20 is negative.

위에서 말한 방법을 이용해서 IndexOutOfBounds 에러가 나는 경계를 넘는지에 대한 검사를 하라는 문제인데, 만약 x20 레지스터값이 x11보다 작거나 크면, 또는 x20이 negative이면 IndexOutOfBounds라는 문제이다. 이는 bgeu(branch if greater than or equal, unsigned)를 이용하면 된다.

bgeu x20, x11, IndexOutOfBounds // if x20 >= x11 or x20 < 0, goto IndexOutOfBounds

 

 

Reference

David A. Patterson and John L. Hennessy. 2013. Computer Organization and Design, Fifth Edition: The Hardware/Software Interface (5th. ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

RISC-V: building a datapath for conditional Branch instructions

 

Offset typo in RV32I Conditional Branches · Issue #583 · riscv/riscv-isa-manual