Computer Organization Ch2

[Toc] # RISC-V edition Reduced Instruction Set Computer ([RISC](https://en.wikipedia.org/wiki/Reduced_instruction_set_computer)): MIPS, ARM, RISC-V Instruction Set Architecture ([ISA](https://en.wikipedia.org/wiki/Instruction_set_architecture)), the repertorie of instructions of a computer. Different computer have different instruction set but with many aspects in common. Another two popular instrction set: MIPS and ARM. __four principle of computer instruction__ 1. simplicity favors regularity 簡單有利於規律性 2. smaller is faster 越小越快 3. good design demands compromise 綜合考慮 4. make the common fast 常用指令速度快 ## resister | Number | Name | Usage | | ------ | ------- | --------------------------------- | | 0 | x0 | the constant value 0 | | 1 | x1(ra) | return address(link register) | | 2 | x2(sp) | stack pointer | | 3 | x3(gp) | global pointer | | 4 | x4(tp) | thread pointer(local) | | 5-7 | x5-x7 | temporary registers | | 8-9 | x8-x9 | saved registers | | 10-17 | x10-x17 | function auguments / return value | | 18-27 | x18-x27 | saved registers | | 28-31 | x28-x31 | temporary registers | comparison with MIPS | Number | Name | Usage | | ------ | --------- | -------------------------------------------- | | 0 | $zero | the constant value 0 | | 1 | $at | reserved for assembler | | 2-3 | $v0 - $v1 | first and second return values, respectively | | 4-7 | $a0 - $a3 | first four arguments to functions | | 8-15 | $t0 - $t7 | temporary registers | | 16-23 | $s0 - $s7 | saved registers | | 24-25 | $t8, $t9 | temporary registers | | 26-27 | $k0, $k1 | reserved for kernel (operating system) | | 28 | $gp | global pointer | | 29 | $sp | stack pointer | | 30 | $fp | frame pointer | | 31 | $ra | return address | ## instruction formats 32-bits for an instruction ![image](https://hackmd.io/_uploads/HkTkyc3aa.png) :::success * ==__R-type__== funct(7)+rs2(5)+rs1(5)+funct(3)+rd(5)+opcode(7) for arithemetic instruction format * ==__I-type__== immediate(12)+rs1(5)+funct(3)+rd(5)+opcode(7) for loads and immediate arithemetic * ==__S-type__== immediate(7)+rs2(5)+rs1(5)+funct(3)+immediate(5)+opcode(7) for stores and conditional branches * ==__U-type__== immedtate(20)+rd(5)+opconde(7) for upper immediate format ::: _funct:_ the additional opcode field. _rs1:_ the first register source operand. _rs2:_ the second register source operand. _rd:_ the register destination operand. It gets the results of the _operaton. _opcode:_ the basic operation of the instruction. ## arithmetic instruction * ```add $rd, $rs1, $rs2``` $rd = $rs1 + $rs2 * ```addu $rd, $rs1, $rs2``` (unsigned number) $rd = $rs1 + $rs2 * ```addi $rd, $rs1, immed``` $rd = $rs1 + immed * ```sub $rd, $rs1, $rs2``` $rd = $rs1 - $rs2 * ```subu $rd, $rs1, $rs2``` (unsigned number) $rd = $rs1 - $rs2 * ```subi $rd, $rs1, immed``` $rd = $rs1 - immed ==EXAMPLE== the C code of ```f = (g + h) + (i + j)```, and the variables of ```f, g, h, i, j``` are assigned to the register x19, x20, ... , x23 respectively. ``` add x5, x20, x21 add x6, x22, x23 sub x19, x5, x6 ``` _*note: x5 and x6 are temporary registers._ --- 1. unsigned binary intergers range: 0 to +2n -1, using 32 bits, 0 to +4,294,967,295 EXAPMLE: 0000 0000 0000 0000 0000 0000 0000 10112 = 1110 2. __2's complement__ signed integers bit 31 is __sign bit__: 1 for negative numbers, 0 for non-negative numbers range: -2n-1 to +2n-1 -1, using 32 bits, -2,147,483,648 to +2,147,483,647 EXAMPLE: 1111 1111 1111 1111 1111 1111 1111 11002 = - 0000 0000 0000 0000 0000 0000 0000 00112 + 110 = -(310 + 110) = -4~10~ _most-negative_: 1000 0000 ... 0000 _most-positive_: 0111 1111 ... 1111 --- __hexadecimal__ ![image](https://hackmd.io/_uploads/SyRPqa3Ta.png) ## memory __register operands__ RISC-V has 32x32-bit (RISCV-32), 32x64-bit (RISCV-64) register file variants. | OS | pointers | int | long int | long long int | | ----------------- | -------- | ------- | -------- | ------------- | | Microsoft Windows | 64 bits | 32 bits | 32 bits | 64 bits | | Linux, most Unix | 64 bits | 32 bits | 64 bits | 64 bits | > 32-bit data is called a =="word"==(or 4 bytes). > 64-bit data is called a "double word". > __"byte address"__ means that the index points to a byte of memory. > > 32 general-purpose temporary registers, each temporary register has 32 bits or 4 bytes called a word. > 32個通用型暫存器，每個暫存器有32bits稱一個word > > 232 bytes with addressed for 0 to 232 -1 > words are aligned in memory, so address must be a multiple of 4 * x5-x7, x28-x31 for temporary values * x8-x9, x18-x27 for saved variables | | register | memory | | ------------ | -------- | ------ | | capacity | small | large | | access speed | fast | slow | 1. Since register have stored in ==processor==, the access speed is faster than memory. 2. Registers provide compiler some temporary registers when the compiler turn the high-level language into the low-level language, which could reduce the information communciation between processor and memory. 3. Register can improve code density. --- * ```lw $rd = offset($rs1)``` _load word, memory to register_, $rd = $rs1[offset], the unit of offset is byte * ```sw $rd = offset($rs1)``` _store word, register to memory_, $rd = $rs1[offset], the unit of offset is byte __endian__ 1. ==Big Endian (MIPS)==: most significant byte at least addredd of a word 最高位位元組放在最低記憶體位置上 2. ==Little Endian (RISC-V)==: least significant byte at least addredd of a word 最低位位元組放在最低記憶體位置上 3. ARM supports both endians | | big endian | little endian | |:---:|:----------------- | ----------------- | | 0 | most significant | least significant | | 1 | ... | ... | | 2 | | | | 3 | | | | 4 | least significant | most significant | | 5 | | | | 6 | | | | 7 | | | | 8 | | | ```c #include <stdio.h> typedef union { unsigned long l; unsigned char c[4]; } x; int main() { x y; y.l = 0x12345678; if (y.c[0] == 0x78 && y.c[1] == 0x56 && y.c[2] == 0x34 && y.c[3] == 0x12) printf("little endian\n"); else if (y.c[0] == 0x12 && y.c[1] == 0x34 && y.c[2] == 0x56 && y.c[3] == 0x78) printf("big endian\n"); else printf("unknown\n"); printf("address - 0x%lx:\n", y.l); for (int i = 0; i < 4; i++) printf("%p: 0x%02X\n", &y.c[i], y.c[i]); } ``` RESULT > CPU: Apple M1 > OS: MacOS Sonoma 14.0 > Compiler: gcc-13 (Homebrew GCC 13.2.0) 13.2.0 ```zsh $ gcc -std=c11 endian.c -o endian little endian address - 0x12345678: 0x16bacf270: 0x78 0x16bacf271: 0x56 0x16bacf272: 0x34 0x16bacf273: 0x12 ``` ==EXAMPLE1== the C code of ```g = h + A[8]```, and the variables of ```g``` is assigned to the register of x20, ```h``` is assigned to the x21 and the base address of the array of int, ```A```, is in x22. ``` lw x9, 32(x22) # a word is 4 bytes(8x4=32) add x20, x21, x9 ``` ==EXAMPLE2== the C code of ```A[12] = h + A[8]```, and the variable of ```h``` is assigned to the register of x21 and base the address of the array of int, ```A```, is in x22 ``` lw x9, 32(x22) add x9 x21, x9 sw x9, 48(x22) ``` ==EXAMPLE3== swap function turn the C code segment ```c swap(int v[], int k){ int temp; temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; } ``` into RISC-V code. array ```v[]``` is assigned in x10, ```k``` in x11, ```temp``` in x5 ``` slli x6, x11, 2 add x6, x10, x6 lw x5, 0(x6) lw x7, 4(x6) sw x7, 0(x6) sw x5, 4(x6) jalr x0, 0(x1) ``` --- * ```lwu $rd = offset($rs1)``` (unsigned number) $rd = $rs1[offset] * ```swu $rd = offset($rs1)``` (unsigned number) $rd = $rs1[offset] ## representing instruction in the computer ==EXAMPLE1== turn ```add x9, x20, x21``` into machine code :::info _*note: the instruction format of ==R-type== is funct(7)+rs2(5)+rs1(5)+funct(3)+rd(5)+opcode(7)_ ::: the opcode of ```add``` is 51, the number of ```x9``` is 9, ```x20``` is 20 and ```x21``` is 21. and they're corresponding to op, rd, rs1, rs2. | funct7 | rs2 | rs1 | funct3 | rd | opcode | | --------- | ------- | ------- | ------ | ------- | --------- | | 0b0000000 | 0b10101 | 0b10100 | 0b000 | 0b01001 | 0b0110011 | which is 0x015A04B3. ==EXAMPLE2== turn the C code segment```A[30] = h + A[30] +1``` into RISC-V code and machine code if ```x10``` has the base of the array ```A``` and x21 corresponds to ```h``` ``` lw x9, 120(x10) # offset = 30 x 4 bytes add x9, x21, x9 addi x9, x9, 1 sw x9, 120(x10) ``` :::info _*note1: the instruction format of ==I-type== is immediate(12)+rs1(5)+funct(3)+rd(5)+opcode(7)_ _*note2: immediate for constant operand, of offset added to base address_ _*note3: the instruction format of ==S-type== is immediate(7)+rs2(5)+rs1(5)+funct(3)+immediate(5)+opcode(7)_ ::: the machine code of ```lw``` is (I-type) | immediate | rs1 | funct3 | rd | opcode | | ------------------ | ---------- | ------- | --------- | ----------- | | 120=0b000011110000 | 10=0b01010 | 2=0b010 | 9=0b01001 | 3=0b0000011 | the machine code of ```add``` is (R-type) | funct7 | rs2 | rs1 | funct3 | rd | opcode | | ----------- | --------- | ---------- | ------- | --------- | ------------ | | 0=0b0000000 | 9=0b01001 | 21=0b10101 | 0=0b000 | 9=0b01001 | 51=0b0110011 | the machine code of ```addi``` is (I-type) | immediate | rs1 | funct3 | rd | opcode | | ---------------- | --------- | ------- | --------- | ------------ | | 1=0b000000000001 | 9=0b01001 | 0=0b000 | 9=0b01001 | 19=0b0010011 | the machine code of ```sw``` is (S-type) | immediate | rs2 | rs1 | funct3 | immediate | opcode | | ----------- | --------- | ---------- | ------- | ---------- | ------------ | | 3=0b0000011 | 9=0b01001 | 10=0b01010 | 2=0b010 | 24=0b11000 | 35=0b0100011 | --- :::danger * __How to access an array element with displacement > 2^15^-1?__ ![image](https://hackmd.io/_uploads/r1s7RMJCp.png) ::: ## bitwise / logical instruction * ```sll $rd, $rs1, $rs2``` $rd = $rs1 << $rs2 * ```slli $rd, $rs1, immed``` slli by i bits multiple 2^i^ * ```srl $rd, $rs1, $rs2``` $rd = $rs1 >> $rs2 * ```srli $rd, $rs1, immed``` * ```sra $rd, $rs1, $rs2``` shift right arithemetic, $rd = $rs1 >> $rs2 * ```srai $rd, $rs1, immed``` * ```and $rd, $rs1, $rs2``` * ```andi $rd, $rs1, immed``` * ```or $rd, $rs1, $rs2``` * ```ori $rd, $rs1, $immed``` * ```xor $rd, $rs1, $rs2``` * ```xori $rd, $rs1, $immed``` replaced NOT operation used in other ISAs, set some bits to 1, leave others unchanged ==EXAMPLE== ```xor x9, x10, x11``` | name | machine code | | ---- | --------------------------------------- | | x9 | ```1111 1111 1111 1111 1111 0010 0011 1111``` | | x10 | ```0000 0000 0000 0000 0000 1101 1100 0000``` | | x11 | ```1111 1111 1111 1111 1111 1111 1111 1111``` | ## conditional branch * ```beq $rs1, $rs2, $L1``` branch if equal, if($rs1 == $rs2) goto $L1 * ```bnq $rs1, $rs2, $L1``` branch if not equal, if($rs1 != $rs2) goto $L1 * ```blt $rs1, $rs2, $L1``` branch if less than, if($rs1 < $rs2) goto $L1 * ```bltu $rs1, $rs2, $L1``` branch if less than, unsigned, if($rs1 < $rs2) goto $L1 * ```bge $rs1, $rs2, $L1``` branch if greater or equal, if($rs1 >= $rs2) goto $L1 * ```bgeu $rs1, $rs2, $L1``` branch if greater or equal, unsigned, if($rs1 >= $rs2) goto $L1 ==EXAMPLE== turn the C code segment ```c if (i == j) f = g + h; else f = g - h; ``` into RISC-V code. the variables ```f, g, h, i, j``` corresponding to x19, x20, ... , x23 ``` bne x22, x23, Else # not(i == j), jump to Else add x19, x20, x21 beq x0, x0, Exit # unconditional Else: sub x19, x20, x21 Exit: ``` _*note: when the C code use "==", than the RISC-V code use "bne(!=)", vice versa._ ==EXAMPLE== turn the C code segment```if (a >= b) a += 1;``` into RISC-V code. ```a``` in x22, and ```b``` in x23. ``` blt x23, x22, Exit addi x22, x22, 1 Exit: ``` :::info Notice the signed and unsigned symbol for example: x22 = ```1111 1111 1111 1111 1111 1111 1111 1111``` x23 = ```0000 0000 0000 0000 0000 0000 0000 0001``` then 1. ```blt x22, x23, L1 # signed``` x22 < 23, since -1~10~ < +1~10~ 2. ```bltu x22, x23, L1 #unsigned``` x22 > x23, since +4,294,957,295~10~ > +1~10~ ::: ## loop ==EXAMPLE== turn the C code segment ```c while(save[i] == k) i += 1; ``` into RISC-V code. the variables ```i``` and ```k``` in x22 and x24, address of ```save``` in x25 ``` Loop: slli x10, x22, 2 # word to byte address add x10, x10, x25 lw x9, 0(x10) bne x9, x24, Exit addi x22, x22, 1 beq x0, x0, Loop Exit: ``` | block | address | | --------- | ------- | | ... | ... | | save[i+2] | x25+8 | | save[i+1] | x25+4 | | save[i] | x25 | _*note: shift left 1 byte(int), 1 byte = 4 bits = 2^2^ bits, ```slli $rs, $rd, 2```_ ## function call in the execution of a procedure, the program must follow these step: 1. Put parameters in a place where the procedure can access them. 2. Transfer control to the procedure. 3. Acquire the storage resources needed for the procedure. 4. Perform the desired task. 5. Put the result value in a place where the calling program can access it. 6. Return control to the point of origin, since a procedure can be called from several points in a program. RISC-V provides some register for function call * ```x10-17``` eight parameter registers in which to pass parameters or return values. * ```x1```: one return address register > ```x5-x7, x28-x31```: temporary register > ```x8-x9, x18-x27```: saved register --- * ```jal $x1, $L1``` procedure call, address of following instruction put in x1, and jump and link to the L1 * ```jalr x0, 0(x1)``` procedure return, jump to 0 + address in x1 use x0 as rd, which could not be changed ==EXAMPLE== turn the C code segment ```c int leaf_example(int g, int h, int i, int j){ int f; f = (g + h) - (i + j); return f; } ``` into RISC-V code. the arguments in ```g, h, i ,j``` in x10, x11, x12, x12 respectively, the ```f``` in x20(saved register), and the x5 and x6 for temporary register ``` leaf_example: addi sp, sp, -12 # move down the stack pointer sw x5, 8(sp) # push sw x6, 4(sp) # push sw x20, 0(sp) # push add x5, x10, x11 add x6, x12, x13 sub x20, x5, x6 addi x10, x20, 0 # x10 is the return value of f lw x20, 0(sp) # pop lw x6, 4(sp) # pop lw x5, 8(sp) # pop addi sp, sp, 12 jalr x0, 0(x1) ``` ![image](https://hackmd.io/_uploads/HydY8rTap.png) ## recursive non-leaf procedure which call other procedure the C code segment ```c int fact(int n){ if (n < 1) return 1; else return n * fact(n-1); } ``` argument ```n``` in x10 and result in x10 the RISC-V code ``` fact: addi sp, sp -8 sw x1, 4(sp) sw x10, 0(sp) addi x5, x10, -1 bge x5, x0, L1 # if (n - 1) >= 0, goto L1 addi x10, x10, 1 # else, return 1 addi sp, sp, 8 # pop jalr x0, 0(x1) # return to caller L1: addi x10, x10, -1 # n-1 jal x1, fact # call n-1 addi x6, x10, 0 # move result of fact(n - 1) to x6 lw x10, 0(sp) lw x1, 4(sp) addi sp, sp, 8 mul x10, x10, x6 # return n * fact(n - 1) jalr x0, 0(x1) ``` ![image](https://hackmd.io/_uploads/HyqWboIAp.png) ![image](https://hackmd.io/_uploads/rkw31La6p.png) ## memory layout ![image](https://hackmd.io/_uploads/rywPCRn66.png) _stack_: automatic storgae for procedure calls _caller_: the program provides the necessary parameter values. _callee_: a procedure that executes a series of intructions based on parameters provided by the caller and then returns the control to the caller. ```c #include <stdio.h> const int global_x = 1; // data （read-only area） int global_y = 1; // data （read-write area） int global_z; // bss int main() { const static int x = 1; // data （read-only area） static int y = 1; // data （read-write area) static int z; // bss int w = 1; // stack char *buf = (char *)malloc(sizeof(char) * 100); // heap // ... free(buf); return 0; } ``` ## dealing with ASCII character a character of ASCII is 8-bits length, we could not just use ```lw``` ans ```sw```. RISC-V provides some instruction below: * ```lb $rd = offset($rs1)``` load byte, $rd = $rs1[offset] * ```lbu $rd = offset($rs1)``` (unsigned number) * ```sb $rd = offset($rs1)``` store byte, $rd = $rs1[offset] ==EXAMPLE== turn the C code segment ```c void strcpy (char x[], char y[]){ size_t i; i = 0; while ((x[i] = y[i]) != ‘\0’) /* copy & test byte */ i += 1; } ``` into RISC-V code. the base addressed for array ```x``` and ```y``` are in x10 and x11, while ```i``` is in x19. ``` strcpy: addi sp, sp, -4 sw x19, 0(sp) add x19, x0, x0 # i = 0 + 0 L1: add x5, x19, x11 # address of y[i] in x5 lbu x6, 0(x5) add x7, x19, x10 sb x6, 0(x7) beq x6, x0, L2 addi x19, x19, 1 jal x0, L1 L2: lw x19, 0(sp) addi sp, sp , 4 jalr x0, 0(x1) ``` ## dealing with unicode character by defalut unicode, a character takes 16-bits which is a half-word. * ```lh $rd = offset($rs1)``` load half word, $rd = $rs1[offset] * ```lhu $rd = offset($rs1)``` (unsigned number) * ```sh $rd = offset($rs1)``` :::info __COMPARISON__: load and store(unsighed) * load / store / load unsigned byte: ```lb/sb/lbu rd, offset($rs1)``` * load / store / load unsigned byte halfword: ```lh/sh/lhu rd, offset($rs1)``` * load / store / load unsigned byte word: ```lw/sw/lwu rd, offset($rs1)``` ::: ## for the occasional 32-bits constant * ```lui $rd, immed``` which load the upper __20-bits__ copy 20 bits constant to bits [31:12] of $rd clear right 12-bits [11:0] of $rd to 0 :::info _*note: using a new instuction format for upper immediate format, ==U-type== immedtate(20)+rd(5)+opconde(7)_ ::: for example: how to load ```0000 0000 0011 1101 0000 0101 0000 0000``` in x19? ``` lui x19, 976 #0b00000000001111010000 = 976 addi x19, x19, 1280 #0b010100000000 = 1280 ``` The final value in register x19 is the desired value: ```00000000 00111101 00000101 00000000``` ## branch addressing :::info _*note:_ __S-type__: immediate(7)+rs2(5)+rs1(5)+funct(3)+immediate(5)+opcode(7) _for stores and conditional branches_ __U-type__: immedtate(20)+rd(5)+opconde(7) _for upper immediate format and jump addressing_ ::: * ==__SB-type__== immed[12]+immed[10:5]+rs2(5)+rs1(5)+funct(3)+immed[4:1]+immed[11]+opcode(7) The address uses an unusual encoding, which simplifies datapath design but complicates assembly. most branch targets are near branch __PC-relative addressing = PC + immed x 2__ * ==__UJ-type__== immed[20]+immed[10:1]+immed[11]+immed[19:12]+rd(5)+opcode(7) for long jump, e.g., to 32-bits absolute address :::success lui: load address [31:12] to temp register jalr: add address [11:0] and jump to address ::: ==EXAMPLE== the C code segment ```c while(save[i] == k) i += 1; ``` the RISC-V code the variables ```i``` and ```k``` in x22 and x24, address of ```save``` in x25 ``` Loop: slli x10, x22, 2 # word to byte address add x10, x10, x25 lw x9, 0(x10) bne x9, x24, Exit addi x22, x22, 1 beq x0, x0, Loop Exit: ``` assuming the loop at location 80000 the machine code will be: | address | immed7 | rs2 | rs1 | funct3 | rd | opcode | | ------- | ------- | ----------- | ----------- | ------ | ----------- | ------- | | 80000 | 0000000 | 00010=2~2~ | 10110=22~2~ | 001 | 01010=10~2~ | 0010011 | | 80004 | 0000000 | 11001=25~2~ | 01010=10~2~ | 000 | 01010=10~2~ | 0110011 | | 80008 | 0000000 | 00000 | 01010=10~2~ | 011 | 01001=9~2~ | 0000011 | | 80012 | 0000000 | 11000=24~2~ | 01001=9~2~ | 001 | 01100=12~2~ | 1100011 | | 80016 | 0000000 | 00001=1~2~ | 10110=22~2~ | 000 | 10110=22~2~ | 0010011 | | 80020 | 0000000 | 00000 | 00000 | 000 | 01101=13~2~ | 1100011 | | 80024 | | | | | | | The ```bne``` instruction on the fourth line adds 3 words or 12 bytes to the address of the instruction, specifying the branch destination relative to the branch instruction (12 + 80012) and not using the full destination address (80024). The branch instruction on the last line does a similar calculation for a backwards branch (−20 + 80020), corresponding to the label Loop. ![image](https://hackmd.io/_uploads/rkqsPiLRp.png) ## RISCV addressing mode summary 1. _immediate addressing_: where the operand is a constant within the instruction itself 2. _register addressig_: where the operand is a register 3. _base on displacement addressing_: where the operand is at the memory location whose address is the sum of a register and a constant in the instruction 4. _**PC-relative** addressing_: where the branch address is the sum of the PC and a constant in the instruction ![image](https://hackmd.io/_uploads/HJqGviIA6.png) ==EXAMPLE== given a branch in register ```x10``` being equal to zero ```beq x10, x0, L1``` replace it by a pair of instructions that offers a much greater branching distance. these instruction replace the short-address conditional branch: ``` bne x10, x0, L2 jal x0, L1 L2: ``` ![image](https://hackmd.io/_uploads/ByTl9_qJ0.png) * decoding machine code what is the ```0x00578833``` corresponding to the machine instruction? ```0b0000 0000 0101 0111 1000 1000 0011 0011``` | funct7 | rs2 | rs1 | funct3 | rd | opcode | | ------- | ----- | ----- | ------ | ----- | ------- | | 0000000 | 00101 | 01111 | 000 | 10000 | 0110011 | hence, this is ```add x16, x16. x5``` ![image](https://hackmd.io/_uploads/HkTkyc3aa.png) ## parallelism and synchronization * Data Race: two memory accesses from a data race if they are from different threads to the same location, at least one is a write, and they occur one after another. 資料為非同步時，資料可能被同時執行的process錯誤覆寫。 * RISC-V provides```lr.w rd, (rs1)``` and ```sc.w rd, (rs1), (rs2)```, called _load-reserve word_ and _store-conditional word_ :::info if the contents of the memory location specified by the load-reserved are changed before the store-conditional to the same address occurs, then the store-conditional fails and does not write the value to memory. The store-conditional is defined to both store the value of a (presumably different) register in memory and to change the value of another register to a 0 if it succeeds and to a nonzero value if it fails. Thus, sc.w specifies three registers: one to hold the address, one to indicate whether the atomic operation failed or succeeded, and one to hold the value to be stored in memory if it succeeded. Since the load-reserved returns the initial value, and the store-conditional returns 0 only if it succeeds, the following sequence implements an atomic exchange on the memory location specified by the contents of x20: ::: ==EXAMPLE== ``` again: lr.w x10, (x20) // load reserve sc.w x11, x23, (x20) // store conditional bne x11, x0, again // branch if store fails (0) addi x23, x10, 0 // put loaded value in x23 ``` ## c compiling process ![image](https://hackmd.io/_uploads/Skr8CRhpp.png) ### compiler and assembler (object file) the compiler transforms the C program into an _assembly language program_ object file is a combination of machine code, instructions, data, and information needed to place instructions properly in memory. to produce the binary version of each instruction in the assembly language program, the assemblr must determine the addressed corresponding to all lebels. Assemblers keep track of labels used in branches and data transfer instruvtions an a ==symbol table==. the object file for UNIX system typically contains six distinct pieces: * the _header_ describes the size and position of the other pieces of the object file. * the _text segment_ contains the machine code. * the _static data segment_ contans data allocated for the life of the program. * the _relocation information_ identifies instrution and data words that depend on absolute address when the program is loaded into memory. * the _symbol table_ the remaining labels that are not defined, such as external references. * the _debugging information_ contains a concise description of how the modules were compiled so that a debugger can associate machine instructions with C source files and make data structure readable. ### linker which takes all the independently assembled machine language program and stutches them together. three steps for linker: 1. place code and data modules symbolically in memory 2. determine the address of data and instruction labels 3. patch both the internal and externel references the linker uses the relocation information and symbol table in each object module to resolve all undefined labels. such references occur in branch instructions, jump instructions, and data addresses, so the job of this program is much like that of an editor: it finds the old addresses and replaces them with the new addresses. the reason a linker is useful is that it is much faster to patch code than it is to recompile and reassemble. the linker produces an executable file that can be run. typically, executable file has the same format as an object file, except that it contains no unresolved reference. --- ==EXAMPLE== link the two object file below. the example will show how a linker work. there're instructions that refer to the addresses of procedures A and B and the instructions that refer to the addresses of data words X and Y. _*note: we show the instructions in assembly language just to make the example understandable; in reality, the instructions would be numbers._ | ==object file header== | | | | | -------------------------- | --------------------------- | ----------------------------- | --------------------------- | | | name | Procedure A | | | | test size | 100~hex~ | | | | data size | 20~hex~ | | | ==test segment== | address | instruction | | | | 0 | ```lw x10, 0(x3)``` | | | | 4 | ```jal x1, 0``` | | | | ... | ... | | | | ... | ... | | | ==data segment== | 0 | (X) | | | | ... | ... | | | ==relocation information== | address | instruction type | dependency | | | 0 | ```lw``` | X | | | 4 | ```jal``` | B | | ==symbol table== | label | address | | | | X | - | | | | B | - | | | ==object file header== | | | | | -------------------------- | --------------------------- | ----------------------------- | --------------------------- | | | name | Procedure B | | | | test size | 200~hex~ | | | | data size | 30~hex~ | | | ==test segment== | address | instruction | | | | 0 | ```sw x11, 0(x3)``` | | | | 4 | ```jal x1, 0``` | | | | ... | ... | | | | ... | ... | | | ==data segment== | 0 | (Y) | | | | ... | ... | | | ==relocation information== | address | instruction type | dependency | | | 0 | ```sw``` | Y | | | 4 | ```jal``` | A | | ==symbol table== | label | address | | | | Y | - | | | | A | - | | AFTER LINK ==executable file header== | text size | data size | | --------- | --------- | | 300~hex~ | 50~hex~ | ==text segment== | address | instruction | | ------------------------ | -------------------- | | 0000 0000 0040 0000~hex~ | ```lw x0 , 0(x3)``` | | 0000 0000 0040 0004~hex~ | ```jal x1, 252``` | | ... | ... | | 0000 0000 0040 0100~hex~ | ```sw x11, 32(x3)``` | | 0000 0000 0040 0104~hex~ | ```jal x1, -260``` | | ... | | ==data segment== | address | | | ------------------------ | --------------------------- | | 0000 0000 0000 1000~hex~ | X | | ... | ... | | 0000 0000 0040 1020~hex~ | Y | | ... | ... | 1. The jump and link instructions use PC-relative addressing. Thus, for the `jal` at address `40 0004`~hex~ to go to `40 0100`~hex~ (the address of procedure `B`), it must put (`40 0100`~hex~ – `40 0004`~hex~) or `252`~ten~ in its address field. Similarly, since `40 0000`~hex~ is the address of procedure `A`, the `jal` at `40 0104`~hex~ gets the negative number `-260`~ten~ (`40 0000`~hex~ – `40 0104`~hex~) in its address field. 2. The load addresses are harder because they are relative to a base register. This example uses `x3` as the base register, assuming it is initialized to `0000 0000 1000 0000`~hex~. To get the address `0000 0000 1000 0000`~hex~ (the address of word `X`), we place 0ten in the address field of `lw` at address `40 0000`~hex~. Similarly, we place `20`~hex~ in the address field of `sw` at address `40 0100`~hex~ to get the address `0000 0000 1000 0020`~hex~ (the address of doubleword `Y`). 3. Store addresses are handled just like load addresses, except that their S-type instruction format represents immediates differently than loads’ I-type format. We place `32`~ten~ in the address field of `sw `at address `40 0100`~hex~ to get the address `0000 0000 1000 0020`~hex~ (the address of word `Y`). ### loader The loader follows these steps in UNIX systems: 1. Reads the executable file header to determine size of the text and data segments. 2. Creates an address space large enough for the text and data. 3. Copies the instructions and data from the executable file into memory. 4. Copies the parameters (if any) to the main program onto the stack. 5. Initializes the processor registers and sets the stack pointer to the first free location. 6. Branches to a start-up routine that copies the parameters into the argument registers and calls the main routine of the program. When the main routine returns, the start-up routine terminates the program with an exit system call. ## a c sort example turn the C code segment ```c void swap(int v[], int k) { int temp; temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; } void sort(int v[], int n) // v[1, n] { int i, j; for (i = 0; i < n; ++i) for (j = i - 1; j >= 0 && v[j] > v[j + 1]; --j) swap(v, j); } ``` into RISC-V code. swap: v in `x10`, k in `x11`, temp in `x5` sort: v in `x10`, n in `x11`, i in`x19`, j in `x20` ``` swap: slli x6, x11, 2 // reg x6 = k * 4 add x6, x10, x6 // reg x6 = v + (k * 4) lw x5, 0(x6) // reg x5 (temp) = v[k] lw x7, 4(x6) // reg x7 = v[k + 1] sw x7, 0(x6) // v[k] = reg x7 sw x5, 4(x6) // v[k+1] = reg x5 (temp) jalr x0, 0(x1) // return to calling routine ``` ``` sort: addi sp, sp, -20 // make room on stack for 5 regs sw x1, 16(sp) // save x1 on stack sw x22, 12(sp) // save x22 on stack sw x21, 8(sp) // save x21 on stack sw x20, 4(sp) // save x20 on stack sw x19, 0(sp) // save x19 on stack addi x21, x10, 0 // copy parameter x10 into x21 addi x22, x11, 0 // copy parameter x11 into x22 addi x19, x0, 0 // i = 0 for1tst: bge x19, x22, exit1 // go to exit1 if i >= n addi x19, x22, -1 // j = i - 1 for2tst: blt x20, x0, exit2 // go to exit2 if j < 0 slli x5, x20, 2 // x5 = j * 4 add x5, x21, x5 // x5 = v + (j * 4) lw x6, 0(x5) // x6 = v[j] lw x7, 4(x5) // x7 = v[j+1] ble x6, x7, exit2 // go to exit2 if x6 < x7 addi x10, x21, 0 // first swap parameter is v addi x11, x20, 0 // second swap parameter is j jal x1, swap // call swap addi x20, x20, -1 // j for2tst jal x0, for2tst // go to for2tst exit2: addi x19, x19, 1 // i += 1 jal x0, for1tst // go to for1tst exit1: lw x19, 0(sp) // restore x19 from stack lw x20, 4(sp) // restore x20 from stack lw x21, 8(sp) // restore x21 from stack lw x22, 12(sp) // restore x22 from stack lw x1, 16(sp) // restore return address from stack addi sp, sp, 20 // restore stack pointer jalr x0, 0(x1) // return to calling routine ``` ![截圖 2024-04-03 下午4.15.43](https://hackmd.io/_uploads/Hy0Necq10.png) ## array vs pointer ![截圖 2024-04-03 下午4.17.54](https://hackmd.io/_uploads/H1fTe5qkA.png) ## fallacies and pitfalls * fallacies: 1. powerful instrucion leads higher performance * fewer instructions required * but complex instructions are hard to implement * compilers are good at making fast code from simple instruction 2. use assembly code for high performance * but modern compilers are better at dealing with modern processors * more lines of code may cause more errors and less productivity * pitfalls: 1. sequential **words** are not at sequential addresses * increment by **4**, not 1 2. keeping a pointer to an automatic variable after procedure returns ![截圖 2024-04-03 下午4.20.09](https://hackmd.io/_uploads/r1DH-qcJR.png)