2.6 논리 연산 명령어
비트들을 뒤로 묶는 작업과 워드를 비트 단위로 나누는 작업을 간단하게 하는 명령어들이 프로그래밍 언어와 명령어 집합에 추가됌. -> 이러한 명령어들을 논리연산 명령어라 부른다.
이러한 연산 중 첫 번째 -> 자리이동(shift)
- sll(shift left logical)
- srl(shift right logical)
s11 $t2, $s0, 4 # reg $t2 = reg $s0 << 4 bits
R 형식 명령어의 shamt 필드에 대한 설명. 적절한 시기가 됨. 이것은 자리이동량 (shift amount)을 나타내는 것으로 자리이동 명령어에서 사용된다. 따라서 위 명령어의 기계어 형식은 다음과 같다.
sll은 op 코드와 funct 필드가 0, rds는 10($t2), rt는 16($s0), shamt는 4를 갖도록 인코딩 되었다. rs 필드는 사용하지 않으므로 0이 된다. sll 명령은 또 다른 용도로 사용 가능. 왼쪽으로 i비트 자리 이동하면 2의i승을 곱한 것과 같은 결과가 된다. 마치 십진수 수를 i자리만큼 자리이동하면 10의 i승을 곱한 것과 같다. 또 다른 유용한 연산은 AND이다. AND는 비트 대 비트 연산자로서 두 비트 값이 모두 1일 경우에만 결과가 1이 된다.
예시생략. AND는 어떤 비트 패턴에서 0의 위치에 해당하는 비트들을 강제로 0으로 만드는데 사용할 수 있다. AND와 함께 쓰이는 이러한 비트 패턴은 일부 비트를 감추는 역할을 하기 떄문에 마스크(mask)라고 부른다.
OR 연산은 비트 대 비트 연산자로 두 비트 중 하나만 1이면 결과가 1이 되는 것이다.예시 생략
마지막 논리 연산은 NOT이ㅏㄷ. 피연산자 하나를 받아서 피연산자의 비트가 1이면 결과를 0으로, 0이면 어떤 결과를 1로 만든다.
MIPS 설계자들은 3-피연산자 형식을 유지하기 위해 NOT 대신 NOR(NOT OR)명령어를 표현시켰다. 피연산자 하나가 0이면 NOT과 같아진다.
2.7 판단을 위한 명령어
beg register1, register2, L1
인데 register1과 register2의 값이 같으면 L1에 해당하는 문장으로 가라는 뜻이다. beq는 branch if equal을 의미한다.
bne register 1, register2, L1
으로서, register1과 register2의 값이 같지 않으면 L1으로 가라는 뜻이다. bne는 branch if not equal을 의미한다. beq, bne 두 명령어를 조건부 분기라 부른다.
ex) if - then - else를 조건부 분기 번역
다음 코드에서 f,g,h,i,j 는 변수이고 각각은 레지스터 $s0부터 $s4까지에 해당한다. 아래의 C언어 문장 if 문장을 컴파일한 코드는 무엇인가?
if(i == j) f = g + h; else f = g - h;
그림 2.9는 MIPS 코드가 해야 할 일을 보여주는 순서도이다. 첫 번쨰 부분은 같은지 비교하는 것. beq로 번역하면 될 것처럼 보인다. 그러나 실제로는 조건을 검사해서 then 부분을 건너 뛰게 하는 것이 더 효율적이므로 bne를 사용하자 (레이블 else는 나중에 정의한다)
bne $s3, $s4, ELSE # go to Else if i ≠ j
다음 치환문은 연산 하나를 실행하는 것으로 피연산자가 모두 레지스터에 있다면 명령어 하나로 번역된다.
add $s0, $s1, $s2 # f = g + h (skipped if i ≠ j)
이 명령을 실행한 후에는 if 문장의 끝 부분으로 가야 한다. 이것은 무조건 분기(unconditional branch)라는 새로운 종류의 분기 명령으로 해결한다. 이 명령어는 프로세서에게 항상 분기하라고 말한다. MIPS에서는 이 같은 명령어에 jump라는 이름을 붙이고 간략하게 j로 사용한다. (레이블 exit는 나중에 정의한다)
j Exit # go to Exit
else 부분의 치환문도 역시 명령어 하나로 번역된다. 단 이 명령어에는 Else라는 레이블을 붙여야 한다. 그리고 이 명령어 뒤에는 if - then - else 문장의 끝을 표시하는 Exit란 레이블을 둔다.
Else: sub $s0, $s1, $s2 # f = g - h (skipped if i = j) Exit;
어셈블러가 컴파일러나 어셈블리 언어 프로그래머가지겨운 분기 주소 계산을 하지 않도록 해 준다는 것을 기억하라. 이는 마치 적재와 저장 명령어를 위해 데이터 주소를 계산해 주는 것과 똑같다.
컴파일러가 소스 프로그램에는 없는 분기 명령이나 레이블을 만들어내는 경우가 많이 있다.
순환문
계산의 반복에도(순환문 사용)중요하다. 두 경우에 모두 같은 어셈블리 명령어가 사용된다.
ex) while 순환 문의 번역
while (save[i] == k)
i += 1;
i 와 k가 레지스터 $s3, $s5에 할당되었고 배열 save의 시작 주소가 $s6에 저장되어 있다고 할 때 위 c 문장에 해당하는 MIPS 어셈블리 코드를 보여라.
첫 번째로 할 일 -> save[i]를 임시 레지스터로 가져오는 것이다. save[i]를 임시 레지스터에 적재하려면 먼저 그 주소를 구해야 한다. 바이트 주소 문제 때문에 인덱스 i에 4를 곱해서 save의 시작 주소에 더해야 주소가 만들어진다. 2비트씩 좌측 자리이동을 하면 4를 곱한 것과 같으므로 sll 연산을 사용할 수 있다. 순환의 끝에서 처음 명령어로 되돌아갈 수 있도록 Loop 레이블을 추가한다.
Loop: sll $t1, $s3, 2 #Temp reg $t1 = i * 4
save[i]의 주소를 계산하기 위하여 $t1 값에다 $s6에 있는 save의 베이스 주소 값을 더할 필요가 있다.
add $t1, $t1, $s6 # $t1 = address of save[i]
이제 이 주소를 이용해서 save[i]를 임시레지스터에 넣을 수 있다.
lw $t0, 0($t1) # Temp reg $t0 = save[i]
다음은 반복 검사를 수행해서 save[i] ≠ k이면 순환에서 빠져나가는 부분이다.
bne $t0, $s5, Exit # go to Exit if save[i] ≠ k
다음은 i에 1을 더하는 명령어이다.
addi $s3, $s3, 1 # i = i + 1
순환문의 끝에서는 맨 앞의 while 조건 검사로 되돌어가야 한다. 그리고 이 명령의 다음에 Exit 테이블을 두면 번역이 끝난다.
J Loop # go to Loop
Exit:
이렇게 분기 명령어로 끝나는 명령어 시퀀스는 컴파일러에게 특히 중요한 의미가 있기 때문에 기본 블록이라는 별칭이 붙이 있다. 기본 블록이란 분기 명령을 포함하지 않으며(맨 끝에 있을 수 있다) 분기 목적지나 분게 레이블도 없는 맨 앞에 있는 것은 허용된다) 시퀀스이다. 초기 단계 작업 중 하나는 프로그램을 기본 블록을 나누는 일이다.
같은지 다른지 비교하는 것이 가장 흔한 검사겠지만, 경우에 따라서는 두 변수 간의 대소 비교가 필요할 때도 있다. 예를 들어 for 순환문에서 인덱스 변수 값이 0보다 작은지를 검사할 때가 있다. MIPS에서는 두 레지스터의 값을 비교한 후 첫 번째 레지스터 값이 두 번째 레지스터의 값보다 작으면 세 번째 레지스터 값을 1 아니면 0으로 하는 명령어로 이런 일을 처리한다. 이 명령어를 slt(set on less than)이라 한다.
slt $t0, $s3, $s4 # $t0 = 1 if $s3 < $s4
는 레지스터 $s3의 값이 레지스터 $4의 값보다 작으면 레지스터 $t0를 1로 아니면 0으로 하라는 명령이다.
상수 피연산자는 비교에서도 많이 이용된다. 따라서 상수 피연산자를 갖는 slt 명령어가 필요하다. 레지스터 $2가 상수 10보다 작은지 검사하려면 다음과 같이 쓰면 된다.
slti $t0 , $s2, 10 # $t10 = 1 if $s2 < 10
MIPS 컴파일러는 slt, slti, beq, bne와 레지스터 $zero에 있는 상수 0을 이용해서 모든 비교 조건 (같다, 다르다, 작다, 작거나 같다, 크다, 크거나 같다)을 만들 수 있다. (레지스터 $zero는 0번 레지스터를 가리킨다.)
하드웨어는 간단해야 좋다는 von Neumann의 경고를 준수하여 MIPS 구조에서는 구현하기에 너무 복잡한 blt(branch on less than) 명령어를 제외시켰다. 이 명령을 구현하면 클럭 속도가 느려지거나 이 명령 실행에 별도의 클럭 사이클이 더 필요하게 된다. 그러므로 빠른 명령어 두 개를 사용하는 것이 더 유리하다.
비교 명령은 부호 있는 수와 부호 없는 수 사이의 이분법도 다루어야 한다. 어떤 때는 MSB가 1인 수가 음수를 나타내며, 이때는 당연히 MSB가 0인 어떤 양수보다도 작다. 하지만 부호없는 정수의 경우에는 MSB가 1인 수가 MSB가 0인 어떤 수보다도 더 크다.(MSB의 이러한 이중적 의미를 이용해 배열 경계 검사 비용을 줄이는 방법을 곧 보게될 것이다.)
MIPS는 이 두가지 경우를 처리할 수 있도록 set on less than의 두 가지 유형을 제공하고 있는데 slt(set on less than)와 slti(set on less than immediate)는 부호있는 정수에, sltu(set on less than unsigned)와 sltiu(set on less than immediate unsigned)는 부호없는 정수에 사용한다.
부호있는 수와 부호없는 수의 비교 -> 생략
부호 있는 정수를 부호없는 정수처럼 다루면 0≤ x < y 검사 비용을 낮출 수 있는데, 이 검사는 인덱스가 배열의 한계를 벗어닜는지 확인하는 검사가 딱 맞는다. 핵심은 2의 보수로 표현된 음수가 부호없는 정수에서의 큰 수처럼 보인다는 것이다. 즉 2의 보수 표현에서는 MSB가 부호 비트이지만 부호없는 정수에서는 큰 값을 의미한다. 따라서 부호없는 비교 x < y 를 하면, x가 y보다 작은지뿐만 아니라 x가 음수인지도 검사할 수 있다.
ex) 빠른 경계 검사 방법
ex) 위의 방법을 이용하여 인덱스가 경계를 넘는지 검사하는데 필요한 명령어 수를 줄여라. $s1 ≥ $t2이거나 $s1이 음수이면 IndexOutOfBounds로 분기하라.
답 : u, 즉 부호없는 정수 연산을 이용하여 두 가지를 모두 검사할 수 있다.
sltu $t0, $s1, $t2 # $t0 = 0 if $s1 > = length or $s1 < 0
beq $t0, $zero, IndexOutOfBounds # if bad, goto Error
Case/Switch 문장
대부분의 프로그래밍 언어는 특정 변수의 값에 따라 여러 가지 중 하나를 선택하는 case나 switch 문장을 갖고있다. switch를 구현하는 가장 간단한 방법은 계속적인 조건 검사를 통해 switch를 if-then-else의 연속으로 바꾸는 것이다.
그러나 여러 코드의 시작 주소를 표로 만들면 더 효율적으로 구현할 수 있다. 이 떄의 프로그램은 점프 주소 테이블(jump address table) 또는 점프테이블(jump table)의 인덱스만 계산해서 해당 루틴으로 점프할 수 있다. 점프 테이블은 프로그램상의 레이블에 해당하는 주소를 저장하고 있는 배열이다. 프로그램은 점프 테이블의 적당한 주소를 레지스터에 적재한 후 레지스터의 주소를 사용하여 점프한다. MIPS에서는 이런 상황을 다루기 위해 jr(jump register)이라고 하는 명령어를 갖고 있는데 이 명령어는 레지스터에서 명시된 주소로 무조건 점프한다. 다음 절에서 jr이 얼마나 자주 사용하는지를 보게 될 것이다.
참고자료
컴퓨터 구조 및 설계 지음 DAVID A.PATTERSON, JOHN L>HENNESSY