Part2 (Control Instructions)
1) Conditional branch
2) Unconditional branch(jump)
3) Procedure call and return
1) Conditional branch
Control Instructions (Branch instruction)
- control instructions의 기능: control flow(또는 program execution flow)를 바꾼다.
→ PC 값을 바꾸는거.
→ 전체 instruction의 약 20프로 차지 (벤치마크 프로그램 분석시)
→ common case이므로 branch instruction을 빠르게 구현하는게 중요하다.
- MIPS conditional branch(or decision making) instructions:
→ 그런데 address는 32비트임. 이걸 32비트 길이의 instruction 안에 넣을 수 없다. 즉, 작은 비트로 target-address를 표현하는게 핵심
→ 그래서 낸 아이디어가 32비트 주소를 넣어주는게 아니라 현재 PC 값에서 얼마나 점프하면 되는지 표시하는거
Conditional Branch
- PC-relative addressing mode
(정확히 표현하면 아래처럼 표현해야한다. word 단위로 표현된걸 byte 단위로 바꿔야해서 * 4)
(사실 곱하기를 하는 것도 아님. 그냥 shift 2번 하는거)
→ 32비트로 주소를 줬으면 그건 absolute한 방식이다. 하지만 현 PC값에서 얼마나 떨어져있는지 표시하므로 relative한 방식
→ operand로 레지스터 2개랑 상수 1개 온다.
- Conditional branch instruction은 I-format을 사용한다.
→ 뒤에 상수부분은 offset이라 불러도 되고 jump distance라고 불러도 된다.
→ offset 쪽에 음수를 넣어서 PC값이 감소하는 방향으로 점프하는걸 backward jump 라고 부르고 (loop 쓰면 backward jump 많이 한다.)
offset 쪽에 양수를 넣어서 PC값이 증가하는 방향으로 점프하는걸 forward jump라고 부른다.
→ 조건이 맞아서 jump가 일어나면, branch taken이라고 표현한다.
조건이 맞지 않아서 jump가 일어나지 않으면 branch untaken이라고 표현한다.
→ offset은 2의 보수로 나타나야한다. (앞으로 점프할 수도 있고, 뒤로 점프할 수도 있으니까 음수도 표현가능해야함.)
<표현범위>
(워드 단위로 나타내기 때문에) 18 bits 를 쓰는거랑 같은 효과를 가진다.
그래서 범위는 (-2 ^17) ~ (2^17-1)
- Performance Question) jump distance를 표현하는데 16비트 정도면 충분할까?
if문을 컴파일 했을 때 점프하는 거리가 얼마 되지 않기 때문에 이정도면 대부분의 경우를 충분히 커버할 수 있다.
(benchmark 프로그램을 돌려보고 분석해서 내린 결론)
- beq r1, r2, r3 → 이렇게 레지스터 3개 쓰면 안되나?
→ 이렇게 하면 32비트 주소를 그대로 넣을 수 있음.
→ (앞에서 언급한거랑 비슷한데) 컴파일러가 if문을 컴파일하게 되면 jump할 때의 distance 값을 상수갑승로 알게 된다.
그런데 만약 R 포멧을 쓰게 되면 컴파일러는 자기가 알고 있는 상수값을 굳이 레지스터에 넣어줘야한다. 이때 instruction 이 추가로 소요
그래서 Single instruction으로 해결이 안된다.
→ 그래서 RISC instruction에서는 레지스터 기반의 conditional branch instruction을 제공하지 않는다.
자신이 알고 있는 상수값을 바로 사용할 수 있는 I format 기반의 conditional branch instruction 만 제공한다.
- Relative jump is position-independent
→ 아까 PC relative jump라고 표현했었음. relative jump는 현재 위치에서 얼마나 뛰는지를 표현한다는 의미
→ relative jump는 굉장히 좋은 성질을 가진다!!
code들을 통째로 옮겨도 jump distance는 같으므로 추가적인 처리가 필요가 없다.
→ linking을 하게 되면 여러개의 object 파일들을 묶어서 executable 파일을 만든다. 이 과정에서 코드들의 위치가 바뀌게 되는데
Relative jump는 이때의 일을 줄여준다. (jump distance 값은 손볼 필요가 없으니까)
Comparison for Branch
- 위에서 branch equal이랑 branch not equal 만 배웠지만 우리 C 코드 짜다보면 branch-if-less-than 이런것도 많이나온다.
→ if (i<j) 이런건 beq, bne 이런걸로 처리가 불가능하기 때문에 MIPS에서는 slt (set less than)이라는 instruction을 제공한다.
- 그런데 위와 같이 variable과 variable을 비교하는 경우 말고, variable과 constant를 비교하는 경우도 많이 나온다.
이때 R format을 쓸려면 constant를 register로 옮기는데 instruction을 하나 소요해야한다.
이를 방지하기 위해 slt는 R foramt으로도 지원되고 I foramt으로도 지원된다.
- Comparison instruction: slt(set less than), sgt(set greater than) , sge(set greater than or equal), sle(set less than or equal), slti,....
- 그냥 slt 말고 blt를 만들어서 하나의 Instruction으로 처리하면 안되나? 저렇게 하면 2개로 처리해야하잖아!
→ 하드웨어에서 >, ≥, <, ≤ 를 하는 건 = , ≠ 를 하는것보다 오래 걸린다.
→ bne, beq는 =, ≠ 를 비교하는거. 이땐 그냥 bit by bit comparision을 하면 된다.
각각 비교하면 되니까. 병렬로 비교가 가능하다.
→ 그런데 blt를 할려면 빼기를 한 다음 양수인지 음수인지 확인해봐야한다.
그런데 빼기(더하기로 구현)을 할려면 carry가 발생하므로 sequential하게 연산을 해야해서 시간이 오래걸린다.
이렇게 오래걸리는걸 한 Instruction으로 만들면, 이 instruction 때문에 cct(clock cycle time)이 늘어나게 되어서 다른 instruction 까지 다 늦게 돌아감
그래서 MIPS에서는 blt와 같은 instruction을 지원하지 않는거
→ (IC vs cct) 에서 cct를 줄이고 IC를 늘리기로 택한 것이다. 이게 좋은 선택인지는 벤치마크 프로그램을 돌려봐야 정확하게 알 수 있다.
Signed vs Unsigned Comparision
앞에서 slt 는 R format도 지원되고 I format도 지원된다고 했었음.
그런데 두 수의 비교는 unsigned 사이의 비교도 있고, signed 사이의 비교도 있음. 이것도 따로 지원해줘야한다.
→ 같은 value 들의 비교지만 unsigned 에서의 비교일때랑 signed 에서의 비교일때랑 결과가 다르다.
2) Unconditional branch(jump)
- MIPS unconditional branch instruction
- If-else나 procedure call을 할 때 많이 사용된다.
- 근데 왜 새로운 instruction을 만드나? "beq r1, r1, offset" 하면 되지 않나?
→ jump라는 새로운 instruction을 만들지 말고, 기존에 있던 beq operation 쓰면 되지 않나?
→ procedure call에도 사용되다보니 16비트는 표현하기에 충분하지 않음
- J format을 사용
→ 다른 Instruction이랑 마찬가지로 opcode로 6 bits를 사용하고
→ target address를 표현하기 위해 나머지 26비트를 모두 destination address를 표현하는데 할당한다.
이것도 word 단위로 표현하기 때문에 2비트를 아낄 수 있다. 근데 주소는 32비트인데 남은 4비트는 어떡하지??
→ 앞의 4비트는 항상 0이니까 (사실 항상 0이라고 하긴 그럼) 괜찮고 뒤에 2비트는 word 단위로 표현되니까 괜찮음.
즉, 28비트만 있다면 코드의 모든 주소를 표현할 수 있음
→ executable file 내에 있는 코드를 static code라고 한다!!!
- jump instruction에서 operand 하나 주고 address를 표현하는 방식을 MIPS에서 Pseudo-direct addressing mode라고 부른다.
→ direct addressing은 컴퓨터에서 흔하게 쓰이는 용어. 32비트 주소를 다 주는게 direct addressing mode이다.
그런데 여기서는 32비트를 다 주는게 아니라 26비트밖에 못줌. 하지만 32비트를 다 주는 것과 같은 효과를 가진다. 그래서 pseudo-direct addressing
→ 그런데 이렇게 PC 상위 4비트에 0000을 넣는게 아니라 기존 PC값의 상위 4비트를 복사한다.
기존 PC의 상위 4비트를 복사하는게 더 일반적 표현. 0000을 넣으면 제한적인 동작밖에 못한다. 왜??
→ 상위 4비트를 기존 PC값에서 복사해와야, static code 뿐만 아니라 dynamic 라이브러리 안에서도 jump instruction을 사용할 수 있다.
→ 근데 static code 쪽에서 다이나믹 라이브러리에 있는 function을 call 할 땐 어떻게 할까?
그땐 이 jump instruction을 못 쓰고 새로운 instruction을 사용하게 된다. (jr)
Exercise: Compiling Loop Statement
→ 어셈블리로 어떻게 나타나는지 살펴봤음. 그렇다면 binary로는 어떻게 나타날까?
Basic Blocks
- basic block은 다음을 만족시키는 sequence of instruction이다.
1) embedded branch가 없고
2) branch out이 없음
→ 나중에 컴파일러를 공부하거나 advnaced 프로세서를 공부할 때 basic block에 대해서는 최적화가 쉽다
Additional Instruction Support
- 컴파일러는 unconditional jump를 해야하는건 확실한데 어디로 뛰어야하는지 알 수 없는 상황을 맞이한다.
→ run time에 어디로 뛸지 결정되기 때문 (case-switch가 그런 상황: unconditional jump를 한다는게 의외다. )
→ j instruction을 쓸 순 없음. destination address를 26비트로 줘야하는데 어디로 가야하는지 모르니까
→ beq instruction도 쓸 순 없음. jump-distance를 16비트로 줘야하는데 얼마나 뛸지 모름
- 그래서 제공되는게 jr instruction
→ jr 뒤에 레지스터 1개가 나온다. 이 레지스터 안에 어디로 점프해야하는지 주소가 담겨있다.
→ operand로 레지스터 1개만 나오기 때문에 R format과 I format 중 뭘 쓰던 상관없지만 opcode 를 아끼기 위해 R-format 사용
→ 컴파일러가 각 case들을 컴파일하는데는 아무 문제가 없다.
case 0을 컴파일해서 0001 0000에 넣어놓고
case 1을 컴파일해서 0001 0100에 넣어놓고~~
→ 이렇게 컴파일을 다 끝낸 뒤 각 case의 시작주소를 모아 jump table을 만든다.
- switch는 if-else로도 구현이 가능하다. 컴파일러가 그냥 switch를 if-else if 로 바꿔서 컴파일하면 안되나?
만약 case가 100개인 경우 if-else if~로 바꾸면 평균적으로 비교를 50번해야한다. 너무 비효율적.
→ 스마트한 컴파일러의 경우 case 수가 작으면 if-else if로 바꿔서 컴파일하고
→ case 수가 많으면 바꾸지 않고 jr를 써서 컴파일을 한다.
- Indirection은 powerful한 method다!
→ 방금처럼 jump table을 만들어서 jump table에 갔다가 각 case에 대한 코드로 가는걸 indirection이라고 한다.
→ Indirection을 하기 위해선 Instruction을 추가로 더 사용하게 되므로 느려진다. 하지만 direction을 할 수 없는 난처한 경우를 해결할 수 있음
Jump Register(jr) instruction
< jr은 언제 쓰이는가? >
1) target address를 compiler time에 알 수 없을때. (runtime에 결정된다. )
- Case or switch statement
- OOP에서 virtual function을 사용할 때
- Dynamic shared library (DLL) → 이 라이브러리가 어느 주소에 할당 될지 런타임에 결정되기 때문에 target address를 알 수 없음
→ 즉, 다이나믹 라이브러리를 사용할 경우 jr를 쓸 수밖에 없는 2가지 이유를 모두 가지게 된다.
(1) full 32 비트 주소를 다 줘야한다. (PC값의 앞 4비트를 복사할 수 없음)
(2) target address가 runtime에 결정된다. (런타임에 library가 어디로 바인딩 되는지 확인해서 함수의 주소를 register에 넣고 jr 써야함)
- Return from procedure call
ISA Design
- Computer system design
→ Architecture, OS, compiler
→ 우리 지금 컴퓨터 시스템 디자인 부분을 보고 있다.
- Input for ISA design
→ OS vendors, application designer
→ instruction set 디자인의 많은 부분은 프로세서 디자인 하는 사람이 독단적으로 하는게 아니다.
OS 디자이너와 컴파일러 디자이너와 application 디자이너와 협의를 해서 그 결과에 따라 설계를 하는거
→ 즉, ISA를 디자인한다는 것은 OS 디자이너, 컴파일러 디자이너, 다른 application 디자이너들의 요구조건을 최적으로 수용하는 과정
→ (협의의 좋은 예) MIPS에서는 executable 파일, 다이나믹 라이브러리 등이 어떤 주소를 사용하는지 설계 때 다 결정을 해놓게 된다.
컴파일러가 컴파일을 할 때 이 원칙에 맞춰 주소를 할당하게 되고
OS는 이 원칙에 맞춰 executable file을 이해를 해서 process address space를 만들어주고
이 원칙에 맞춰 프로세서 디자이너는 j format을 설계하게 되는거임
- ISA design
→ ISA 디자인은 소프트웨어와 하드웨어 interaction을 감당하는 분야
Summary
MIPS에서는 3개의 format을 사용
MIPS에서는 5개의 addressing mode를 사용 → 자주 쓰이는 operation을 single instruction으로 만들자는 취지로 만들어진거
3) Procedure call and return
Return from Procedure Call
- Compiler는 누가 어디서 call 할지 모름
- Caller는 return address를 r31(ra)에 저장한다.
- Return from call을 하기 위해서
→ 다음 Instruction을 실행하면 된다.
Procedural Call Instruction
- 우리 이미 Unconditional jump instruction 2개를 배웠다.
1) j(jump), 2) jr(jump register)
→ procedural jump는 unconditional jump + return address register에 돌아갈 주소만 저장하면 된다.
→ return address register에 돌아갈 주소를 저장하는 것을 "Link" 라고 한다.
- unconditional jump 와 Link를 하는 instruction을 새로 제공
1) jal (jump and link)
2) jalr (jump and link register)
"jal" and "jalr"
1) jal은 j와 마찬가지로 j format 사용
→ 현재 PC값은 ra에 저장하고 PC 값의 앞 4비트는 놔두고 26비트를 들고 오고 뒤에 0 2개를 붙여서 만든 주소로 jump
→ 현재 PC 값은 ra에 저장하고 r5 레지스터에 있는 값으로 이동함
Pseudoinstruction
→ 추가적으로 이 용어를 알아야한다.
→ 어셈블리 language에 존재하는 일종의 가짜 instruction
- move $t0, $t1 같은 경우 MIPS에서 제공하지 않는다 $zero를 통해 add로 구현가능하기 때문
하지만 이렇게 제공하지 않음에도 불구하고 어셈블리 프로그래머가 move에 익숙하므로 이 instruction을 제공한다.
물론 나중에 move를 add로 슬쩍 바꾼다.
즉, 실제 존재하는게 아닌데 프로그래머의 편의를 위해 제공하는거
- blt $t0, $t1, 4 같은 경우도 MIPS에서 제공하지 않지만
어셈블리 프로그래머들은 이걸 편하게 생각하기 때문에 어셈블리 언어에서 허용을 한다.
물론 이건 나중에 slt와 jeq 또는 jne 2개의 instruction으로 살짝 바꾼다.
Overview of MIPS
MIPS의 경우 instruction이 단순해서 IC가 늘어날 수밖에 없다. 그래서 스마트 컴파일러에 많이 의존을 한다.
그리고 기회가 있을때마다 CPI가 작은 instruction으로 바꿀 수 없나 기회를 엿봄
ex) 곱하기 → shift 연산
Uploaded by N2T