[컴퓨터구조개론] 3. MIPs Instruction and Set Architecture(2)

Representing Instructions

Mips에서는 4 byte = 1 instruction이다.

$t0 ~ $t7은 reg’s 8 -15

$t8 ~ $t9은 reg’s 23 – 25

$s0 ~ $s7은 reg’s 16 – 23

 

MIPS R-format(encoding scheme) Instructions

Op: operation code(opcode) 6비트

Rs: first source register number 5비트

Rt: second source register number or target register 5비트

Rd: destination register number(결과값이 저장되는 레지스터) 5비트

Shamt: shift amount 5비트 (추후에 더 자세히..) shift operation으로 사용된다.

Funct: function code 6비트 얘는 op와 비슷한 역할을 한다. Op와 funct가 같이 이 어떤 operation인지 저장한다.

 

 

 

MIPS I-format instructions(상수가 있을 경우)

Rd가 없음. Op: 6bits, rs: 5bits, rt: 5bits, constand or address: 16 bits

Constant의 크기는 -2^15 ~ 2^15-1

I-format은 arithmetic instruction뿐만 아니라 load/store instruction도 사용된다. Arithmetic instruction때는 constant or address자리에 단순히 상수가 온지만 load/store일 때에는 rs자리에 base address 그리고 constant or address자리에 offset이 들어온다.

이전 원리에서 “simplicity favors regularity”라고 했다. 하지만 지금 우리는 새로운 format을 배웠고 앞으로 하나 더 남아 있다. 근데 우리는 왜 이런 다양한 format을 만들게 된 걸까. 하나의 특별한 format만 있으면 좋았겠지만 좋은 performance를 위해서 타협할 수 밖에 없게되었다. 다양한 format으로 조금 복잡해질 수는 있겠지만 오직 32비트 instructions의 크기로 통일 시킬 수 있게되었다. 그래서 instruction의 모양, 디자인은 다를 수 있지만 32비트라는 점은 통일이 되었다.

대신에 타협을 하여 모양의 다양성을 주는 대신에 최대한 format들의 디자인을 비슷하게 만들었다. R format와 I format을 살펴보면 앞에 파트는 똑같다는 것을 알 수 있다.

 

MIPS J-format instructions(jump instruction)

Jump instruction은 j와 jal이 있다. Op는 6비트, constant and address는 26비트를 차지한다

Jump는 어디로 jump하는지 알아야한다. 그럼으로 jump target을 가지고 있어야 한다. Op는 이 operation인 것을 알려주고 나머지 부분 constant and address부분이 jump target의 address를 가리킨다.

여기서의 의문점은 MIPS는 32비트 아키텍쳐이다. 그래서 address of memory location은 반드시 32비트 이여야 한다. 하지만 놀랍게도 여기서 우리에게 주어진 비트수는 26비트 밖에 안된다. J format에서의 이 address는 absolute address가 아니라 PC-relative address이다. Pc는 다음 instruction의 address를 가지고 있다. 그래서 pc 레지스터의 값을 바꾸면 다른 곳으로 jump할 수 있다. 그래서 j-format의 address는 그냥 offset이라고 생각을 해도 된다.

 

Stored Program Computers

결국 format은 3개 밖에 없고 꽤나 regularity하다. 그럼 instruction이 binary로 ecoding 되면 main memory에 저장하게 된다. 폰노이만 구조에서 프로그램은 그냥 데이터와 같이 취급이 된다. 그래서 프로그램은 프로그램의 content를 읽을 수 있다(instruction sequence). 그리고 프로그램의 값을 바꿀 수 있다. 그래서 우리가 compiler와 linker를 사용할 수 있는 것이다.

메모리안에는 많은 프로그램이 있고 각 프로그램은 서로 읽거나 값을 바꿀 수 있다.

 

만약에 두개의 다른 마이크로아키텍쳐의 컴퓨터가 같은 ISA를 가지고 있으면 프로그램은 호환이 될 수 있다.

 

Logical Operations

Instructions for bitwise manipulation-> 이는 logical이 아닌 비트 대 비트로 계산 가능한 형식을 말한다.

Shift left = sll

Shift right = srl

Bitwise AND = and, andi(i가 들어가면 immediate)

Bitwise OR = or, ori

Bitwise NOT = nor(왜 nor? 사실 MIPS는 not을 지원하지 않는다. Nor (destination register), A, 0은 ~A가 된다. 왜인지는 수업때 안가르켜줬다 흑흑)

 

Shift Operations

Sll I bit를 하면 2^i를 곱한것이다. Shamt는 i의 값을 가지게 되고 op와 funct는 0의 값을 가진다.

Srl도 위와 같고 이외에 sla/sra라는 operation이 있다. 우리가 right shift를 하게 되면 맨 왼쪽에 있는 MSB가 logical이기 때문에 항상 0이 들어오게된다. 덕분에 sign(부호)이 바뀔 수도 있다. 그래서 완벽하게 바뀐 값을 보존하기 위해서 sra를 사용한다. 그래서 msb값은 이전의 sign을 그대로 적용하게 된다.

 

AND Operations

And operation은 비트를 감추는데 굉장히 유용하다. And 비트는 내가 보존하고 싶은 몇 개의 비트를 제외하고 나머지 비트들을 0으로 초기화 시킬 수 있다. (밑처럼 말이다..)

 

 

OR Operations

Or operation은 기존의 word에 새로운 비트들을 추가하는데 유용하게 사용된다.

 

NOT Operations

Not operation은 각 비트를 바꾸는데 많이 사용된다. 0을 1로, 1을 0으로. 위에서 말했던 것처럼 MIPS에서는 not operation이 없기 때문에 nor $t0, $t1, $zero이처럼 사용한다.

 

Instructions for Making Decisions

Conditional Operations

해당 조건이 만족되면 점프 아니면 그냥 진행이 된다.

Beq rs, rt, L1

If(rs==rt) jump to L1   L1은 address of target instruction이다. 하지만 binary로 바뀌면 L1은 pc relative value로 바뀐다. 왜냐하면 크기가 부족하기 때문에.

Bne rs, rt, L1

If(rs!=rt) jump to L1

J L1

모든 조건 무시하고 일단 L1으로 점프한다.

 

Compiling If Statement

If(i==j) f=g+h

Else f=g-h

F,g,h,I,j in $s0, $s1, $s2,$s3,$s4

Bne $s3, $s4, Else

Add $s0, $s1, $s2

J Exit

Else: sub $s0, $s1, $s2

Exit:…

Label은 address의 mnemonic이라고 한다.

 

Compiling loop Statements

While (save[i] == k) i+=1;

I in $s3, $s5 address of save in $s6

Loop: sll $t1, $s3, 2         ->s3*4

      Add $t1, $t1, $s6

      Lw $t0, 0($t1)

      Bne $t0, $s5, Exit

      Addi $s3, $s3, 1

      J Loop

Exit:…

 

Basic Blocks

Code block은 sequence of instruction이다. 이는 두가지 특징을 가지고 있는데

1.     No embedded branches. 앞서 말한 조건문 branch instruction들이 포함되지 않는다. 그래서 중간에 다른 Exit로 가는 것이 안된다.

2.     No branch targets. 중간에 들어오는 것도 안된다.

정리하자면 code block에서 시작이 되면 반드시 끝까지 가야한다.

왜 중요하냐면 a compiler identifies basic blocks for optimization. 이 뜻은 컴파일러는 이 basic block을 optimization할때의 하나의 유닛으로 보기 때문이다.

An advanced processor can be accelerate execution of basic blocks. 어차피 위의 특성 때문에 쉽게 주어진 코드를 보고 쉽게 결과를 예측할 수 있기에 basic block의 실행을 가속화 시킬 수 있다. 더 자세한 부분은 나중에 다루게 될것이다.

 

Mode Conditional Operation

이번엔 어떠한 조건들을 해당할 때 결과값을 1 또는 0을 내는 operation을 볼 것이다. 1이면 참, 0이면 거짓이다.

Slt rd, rs, rt    #if(rs<rt) rd=1, else rd=0    set은 값을 1으로하고 clear는 0으로 바꾼다.

Slti rt, rs, constant  #if(rs<constant) rt=1; else rt=0

Shorter is better, 우리가 branch instruction을 알고 있는데도 이 condition operation을 사용하는 이유이다. 더 자세한건 뒤에서 다룰 예정이다.

Beq, bne이와 결합하여 이런식으로 사용하기도 한다.

Slt $t0, $s1, $s2  #if($s1 <$s2)

Bne $t0, $zero, L  #branch to L

 

Branch Instruction Design

근데 왜 저건 하나의 operation이 없을까? 마치 blt, bge이런 operation처럼 더 간편한 operation말이다. 그냥 대소비교 >, <, <=, >=는 같다, 다르다와는 조금 더 복잡하다. 그래서 branch instruction이 조금 복잡하다. 그래서 대소비교 operation은 clock cycle을 조금 느리게 한다. 왜냐하면 <=, >=와 같이 두개의 복잡한 operation를 같은 clock에 동작하게 하여야 한다. Instruction set은 가장 느린 clock speed를 참고하게 되는데 이렇게 되면 느려진 clock speed 때문에 다른 모든 instruction조차 느려지게 된다. 결국 principle4처럼 good design principle이였다는 걸 알 수 있다.

 

Signed vs Unsigned

Signed comparison: slt, slit

Unsigned comparision: sltu, sltui

 

Supporting Procedures in Computer Hardware

Procedure Calling

1.     Place parameters(함수에 호출된 매개변수) in register

2.     Transfer control to procedure(function) CPU가 함수의 첫번째 instruction으로 넘어간 상태

3.     Acquire storage for procedure ->메모리에 자리를 만들어줌 usually local variable. 어쩔때는 register spilling도 해야한다.

4.     Perform procedure’s operations

5.     Place result in register for caller

6.     Return to place of call     

 

Register Usage

Argument: $a0~$s3 (reg’s 4-7)

Result value: $v0,$v1 (reg’s2 and 3)

Temporary value: $t0~$t9.  Can be overwritten by callee(function to be executed) 이 뜻은 caller-save register이다. Caller-save register는 각 함수내에서 마음대로 쓸 수 있는 레지스터이다. Caller함수에서 저장되면 callee함수에서 변경을 해도 callee함수가 끝나도 레지스터값은 바뀌지 않는다.

Saved: $s0~$s7(callee saved register) 얘는 반대로 caller에도 영향을 미칠 수 있다.

Global pointer for static data: $gp (reg 28)

Stack pointer: $sp (reg 29)

Frame pointer: $fp (reg 30)

Return pointer: $ra (reg 31)

 

Procedure call instructions

(jump and link)Jal ProcedureLabel

-address of following instruction(이 instruction은 PC를 말한다.) put in $ra 그래서 jal이 불리면 PC안의 값이 $ra에 저장이 되고 점프를 한다.

Jr $ra

ra값이 PC에 저장. 그래서 return address로 점프가능

 

Leaf Procedure Example

Int leaf_Example(int g,h,I,j)

{

           Int f;

           f=(g+h)-(i+j)l

           return f;

}

Argument g,..,j in $a0.,…$a3

F in $s0

Result in $v0

MIPS Code:

Leaf_example:

           Addi $sp, $sp, -4            #sp는 top of the stack 스택 크기를 4만큼 늘림

           Sw $s0, 0($sp)               #s0를 저장

           Add $t0, $a0, $a1

           Add $t1, $a2, $a3

           Sub $s0, $t0, $t1

           Add $v0, $s0, $zero

           Lw $s0, 0($sp)               #restore

           Addi $sp, $sp, 4             #stack size를 처음처럼 되돌린다

           Jr $ra

 

Non-Leaf Procedure

Nested call(중첩함수 call), caller needs to save on the stack:

-its return address

-any arguments and temporaries needed after the call

Restore from the stack after the call

Non-leaf Procedure Example

Int fact(int n)

{

           If(n<1) return f;

           Else return n*fact(n-1);

}

-Argument n in $a0, result in $v0

Leaf procedure은 함수안에 함수를 call하지 않는 함수

여기서 처음 살펴볼 것은 $a0에 원래의 argument 0이 있는데 새롭게 fact(n-1)을 호출하면 $a0은 어떻게 되는가.

 

처음에 -8을 스택포인터에 더해 4바이트 두개의 자리를 만들어둔다. Ra와 a0는 callee function에서 바뀔 수가 있으니 스택포인터에 저장한다. Slti~jal이 함수의 body이다.

 

Local Data on the Stack

Local Data는 자신함수만을 위한 변수이고 이는 스택에 저장이 된다. Fp는 stack frame의 시작부분을 가리킨다. Frame은 스택에서 현재 함수의 위치를 가리킨다. 그래서 fp가 지정되있으므로 스택프레임 밖의 memory location에 가지 못하게 한다. $sp는 top of the stack이고 fp는 bottom of the stack이다.

하나의 stack frame은 saved argument register, saved return address, saved saved register, local arrays and structures순으로 있다.

Memory Layout

 

Text는 프로그램 코드이다. Static data는 global variable이다. 왜 이때 나오냐면 전역변수는 컴파일전에 컴파일러가 알고 있기 때문이다. 그 다음은 heap, stack이다.

 

Communicating with people(Handling characters) input/output

Character Data

문자를 encode하기 위해서 ASCII또는 unicode를 쓴다. 유니코드는 많은 encoding방법이 있는데 그중 Latin-1은 알파벳을 표현하는 방법이다. 이는 아스키코드에 포함이 된다.

아스키코드는 128글자를 표현한다. 그래서 7비트가 필요했지만 요즘에는 8비트로 바뀌었다.

유니코드의 첫 128글자는 아스키코드와 같다. 그래서 아스크코드와 유니코드는 호환가능하다.

 

Byte/Halfword Operations

아스키코드가 한 문자를 표현하기 위해 1바이트가 필요하기 때문에 우리는 MIPS에서 byte또는 halfword를 데이터 operation을 써야한다.

Lb rt, offset(rs)

여기서는 rt의 나머지 부분을 rs의 msb에 의해 sign extended된다.

Lbu rt, offset(rs)

Zero extended to 32bits in rt, 여기서 rt는 32비트이고 rs에서 1비트만 읽어오면 rt의 나머지 비트들은 0으로 채워진다.

Sb rt, offset(rs)

Lh rt, offset(rs)

이건 하프워드임으로 rs의 16비트를 읽어와 rt에 저장된다.

Lhu rt, offset(rs)

Sh rt, offset(rs)

 

String copy Example

 

 

 

 

MIPS Addressing for 32-Bits Immediates and Addresses(어떻게 32비트에 상수가 저장되는지)

32-bits Constants

i-format에서 constant는 16비트를 차지하고 있음. 그치만 32비트 크기의 상수를 포함시켜야 할 때 먼저 32비트를 두개의 16비트로 쪼갠다. 그리고 처음의 16비트를 target register에 lui instruction을 사용하여 저장한다. 그래서 rt는 앞에 16비트부분을 복사하게 된다. 참고로 rt도 32비트이다. 남은 16비트는 0인 상태이다. 그럼 ori instruction을 사용하여 나머지 16비트도 rt에 저장하게 되면 끝이난다.

Lui $s0, 61

Ori $s0, $s0, 2304

 

Branch Addressing

그럼 branch target을 어떻게 인코드하는지 살펴보자. 근데 모든 address를 branch target으로 줄 필요가 없다. Because every instruction take 4 bytes in memory that means 메모리안에 있는 instruction의 address의 시작은 반드시 4의 배수이여야 한다. 그래서 address의 0,4,8,12,16만 기억하고 있으면 된다. 그래서 target address = PC + offset * 4가 된다. 그래서 커버할 수 있는 범위가 늘어나게 된다. 그럼에도 불구하고 더 먼 jump를 하고 싶다면 unconditional jump를 하면된다.

이게 어떻게 가능하냐면 jal instruction은 address가 26비트이기 때문이다.

그래도 더 멀리 점프를 하고 싶으면 컴파일러는 자동적으로 여러 번 점프를 하도록 코드를 바꾸어 컴파일하게 된다.

(사실 이 부분은 이해하기 좀 어려워서 시간이 남으면 더 연구하는 걸로…)