CS61C-笔记

1. 数的表示与转换

ob 二进制
0x 十六进制

二进制位扩展：

无符号：直接给高位补0
有符号（反码，补码）：高位全部用符号位数字填充
eg. 0b11 = 0b1111, 0b01 = 0b0000001

进制转换：

分组法：
二进制转十六进制：四个为一组，十六进制中一位代表16个数，而二进制中表示16个数需要四个位，故四个位分为一组。其他进制同理
十六转二进制：将每一个数用四位二进制数表示，最后拼接起来

二进制中正负转换的Tricks：

补码下 全为1 值为-1
得到一个正数的负数表示，所有位取反，最后加上1即可

补码加减法中的溢出问题：同符号相加减会可能会溢出（与无符号一样），异号相加减一定不会溢出！

偏移量：在无符号二进制基础上，加上偏移量，使得不会出现正数上涨回到0的情况。
一般bias 取 -(2^n-1^-1),n为你的二进制数所包含的的位数
如你的二进制表示范围为00000~11111，此时所有数都按无符号来表示，在此基础上加上bias就是实际量
则 00000就是最小的负数，11111就是最大的正数，且不会加回到负数上

偏移量法和补码都是很好的表示正负数的方法，各有优劣！

2. C基础

编译器：将代码直接针对对应架构的计算机进行编译，编译后的文件不具备可移植性
解释器：将机器无关的字节码解释成对应硬件架构的机器码

C的编译过程：

main.c (compiler)-> main.o(汇编语言) (linker)-> 可执行文件exe

详细过程：

1. C 预处理器 (C Pre-Processor)——处理预处理指令#
   main.c (C Pre-Processor)-> main.i

      gcc -E main.c -o main.i
   
   2. 编译器 (Compiler)——将预处理后的文件 `main.i` 编译成汇编语言代码文件 main.s,这个阶段会进行语法分析、语义分析和优化
   
      main.i -> main.s
   
      ~~~shell
      gcc -S main.i -o main.s
   
   3. 汇编器 (Assembler)——将汇编代码文件 `main.s` 转换成目标代码文件 `main.o`，即机器码。
   
      ~~~shell
      gcc -c main.s -o main.o

2. 链接器 (Linker)——

   将多个目标文件（如果有）和库文件链接成最终的可执行文件 main.exe 或其他操作系统下的可执行文件格式。

   处理外部符号引用，链接库文件（例如标准库 libc 等）

   gcc main.o -o main.exe

3. 加载器（Loader）

3. C指针，数组，Strings

C小贴士：变量声明不初始化，内部存放的是未知数据
void* 万能指针：可以指向任意类型的东西
函数指针：int (temp) (void/, void/*); 声明一个参数类型为void *， void * ，返回值为int的函数指针变量temp

地址空间大小：32-bit机器——地址空间是32bit，可以最多一次访问0~2^32^ - 1 不同内存点，数据通道几乎总是以32位方式传输
字对齐：向0内存点对齐，比如32位int变量的内存地址开头必须为0，4，8，C，0…

数组与指向数组存储元素类型的指针的区别：一般来说没有区别

char* pointer == char pointer[]

但是指针可以++，而数组不可以！
数组指针运算：

ar[0] == *ar;	ar[2] == *(ar + 2);

Segmentation faults 段错误——读写无法访问的内存
bus errors 总线错误——读到一个字不对齐的变量内存

使用句柄来修改指针——句柄：**ptr 指向指针的指针

4. C内存管理

malloc和free相伴而行，但注意，free中传入的指针只能是指向malloc返回的地址的指针！
注意，malloc返回null代表分配内存失败
对malloc的内存空间重新分配内存的是realloc，传入malloc返回的地址的指针
注意：realloc可能会移动数据位置

int *ip = (int *) malloc(10 * sizeof(int));
if (ip == NULL)	...Do()....  /Do something to deal with it
ip = (int*) realloc(ip, 20 * sizeof(int));

An array name is not a variable 数组名不是一个变量
strlen()函数会找出char*字符串的长度，但是不包括NULL终止符，因此分配空间时应该：

char* string = .....;
char* ptr = (char*) malloc(strlen(string) + 1);
strcpy(ptr, string);

C的三个内存区域：

静态存储区：存储全局变量，大小无法被改变，但是可以读写
栈：存储局部变量，参数，返回地址。会向下增长
堆：存储诸如malloc分配的动态内存空间。会向上增长

神奇的是，栈空间拓展和释放仅仅是移动栈指针向下向上，释放时向上移动指针而并没有执行清理释放区域中的内存

内存块的结构和malloc分配：

一个内存块有一个header，存储该内存块的大小，以及指向下一个内存块的指针。整个内存空间类似一个由一个个内存块结点组成的循环链表！

三种处理malloc()分配空间的方式：
1. Best Fit 最佳适配：搜索所有堆内存块找到最适合你malloc申请大小的那块给你。
2. First Fit 首次适配：每次都从头开始，找到首个大于等于你malloc请求的空间大小的块给你。
3. Next Fit 下次适配：从上次分配给你的块的位置继续，找到首个大于等于你m·alloc请求空间大小的块给你。

被释放的空间是不应该被访问的！下图以被释放的栈空间为例

free的不慎使用会导致释放错误的内存空间

struct foo* f = malloc(sizeof(struct foo) * 10);
f++;
free(f);
// 没人知道free这时候会做什么！因为free只会跟踪malloc返回的内存地址，然后正确释放这一大块空间！

5. Floating Point 浮点数

Fixing Point固定二进制小数点数

小数点左边为2^0^, 2^1^, 2^2^ 小数点右边的数位代表2^-1^, 2^-2^等等，但是小数点固定在一个位置，比如左向右数第二位上。
除法左移——例如 11 1111 == 63
我对64 / 16， 就得到： 11.1111 == 64/16, 左移小数点四位

Floating Point浮点数

思路：对一个二进制数，找出其中的尾数mantissa（左右边界都是1，边界外面都是0），作为第一参数
小数点距离尾数左边界的位数——指数exponent，作为第二参数。
如16.375 == 10000.011，转化为规范化二进制为：1.0000011 x 2^4^,有效值10000011，指数为4，代表小数点在1.0这一位的基础上，向右移动4位。如同十进制中的科学计数一样，我们默认1.xxxx这个1一直存在，故只需记录最左边1的右边的有效数字0000011，这里的数字我们成为有效位(Significand)。
这便是浮点的由来

浮点数的大致形式（IEEE floating point）：

Underflow：无限接近0
Overflow：溢出最大最小表示范围

float：1符号位，8指数位，23有效值存储位
double：1符号位，11指数位，52有效值存储位

float和double中的0：
符号位为1或0，表示-0和+0，指数全为0，有效值也全为0

**浮点数的正式形式(IEEE 754浮点标准)：**使用了之前bias偏移量的思路

-1^符号位的值^ x 0b(1.000… + 0.有效位) x 2^(指数位值-127) 注意：【这里的加号是类似字符串拼接的加】
127是2^n-1^-1 得到的
通过偏移量方式，我们得以用字面上的正的指数值，来表示偏移后实际上负和正的指数值，使得小数点可以在1.xxx的基础上实现左移和右移，完善了浮点数的表示

特殊数字

指数全为0，有效位全为0，表示0
||
指数全为0，有效位非全0，（此时认为尾数第一位变成0，也就是0.xxxx形式）表示最小规格数字范围——最小值为-1^0^ x 2^-22^ x 2^-127^ = 2^-149^
||
指数非全1，有效位非全0，表示浮点数
||
指数全为1，有效位全为0，表示∞
||
指数全为1，有效位非全0，表示NaN——Not a Number——由于有效位可以有各种取值，每一个NaN值可以广泛应用于编码各种实际中的错误信息

浮点数转为十进制数示例：

普通浮点数：1/3

浮点数加法不满足结合律

舍入

满足四舍五入规则。
当数字正好位于中间——如十进制中2.5时，舍入最近的偶数，即2，而非3
二进制也遵循一样的规则
0101 ‘100’ 引号内部的数我们需要舍入，由二进制特性，显而易见100是000~111的中间数，也就类似于上面2.5的中间情况，因此0101100应该舍入到最近的偶数，也就是0110 ‘000’
同理：0100 ‘100’ --> 0100 ‘000’

6. RISC-V 简介

指令集：一种特定体系结构可以执行的指令集合——由汇编语言表示
指令集架构：适用于某一或一类处理器的特定指令集
历史：简单，数量少的指令集架构设计哲学被广泛认可

寄存器Register——位于处理器内核中的硬件对象，数量有限。对数据的操作是在寄存器的数据上进行的

x86指令集架构——8个寄存器；
RISC-V指令集架构——32个寄存器
字word——与指令集架构的变种有关。如RV32架构，一个字word对应32bit，4byte
RISC-V的字word长也为32bit

RISC-V寄存器
32个寄存器编号x0~x31
x0是特殊的寄存器，永远存有数据0——无论你对x0寄存器做什么操作，其永远都为0

汇编：
每一行汇编语言最多包含一条指令

add x1, x2, x3
# 1. add 操作的名称
# 2. x1  存储操作结果的寄存器
# 3. x2  操作所使用的数据取自源寄存器1
# 4. x3  操作所使用的数据取自源寄存器2

执行C中代码如：a = b + c + d - e

add x10, x1, x2		# a_temp = b + c
add x10, x10, x3	# a_temp = a_temp + d
sub x10, x10, x4	# a = a_temp - e

立即数immediates——汇编中的数值常量
RISC-V用于加立即数的指令是 addi ——add immediate

addi x3, x4, 10

寄存器足迹——特定内核使用的寄存器数量

小端序——RISC-V遵循的字节序

一个字word中最低位的有效字节byte，获取该字中的最低的地址，该最低地址也成为字word的地址

注意：字节序只是影响字节在内存中的存储顺序，而bit的存储一直都是低位在一个字节的低处（最右边）

例如：存储一个十进制数1025
1025 = 00000000 00000000 00000100 00000001 对应四个字节
如果采用小端序，内存为空，则字节00000001 放在内存地址为0处，00000100 放在内存地址为1处 以此类推…
如果采用大端序，内存为空，则字节00000000 放在内存地址为0处，00000000 放在内存地址为1处 以此类推…

7. RISC-V: lw, sw, Decisions I

寄存器vs内存

寄存器：32个，每个寄存器的大小为一个字word，所以总共32*32=1024bit，128bytes
内存（DRAM）：非常非常多，一般笔记本是2~64GB的内存

寄存器速度 ~= 50~500 * 内存速度

从内存加载数据到寄存器——Load Word
Store Word和Load Word的偏移量必须是4的倍数，因为一个word是四个Byte！！！

// C Code
int A[100]; int h = 12;
int g = h + A[3];

lw x10, 12(x15)	  # 寄存器x10获得了内存中A[3]的值
add x11, x12, x10 # g = h + A[3]
# Note x15——指向A[0]的基指针， 12——偏移12bytes，即三个int值

从寄存器存储数据到内存——Store Word

int A[100];
A[10] = h + A[3];

lw x10, 12(x15)   # 获取A[3]值
add x10, x12, x10 # h + A[3]
sw x10, 40(x15)	  # A[10] = h + A[3]

允许以更小的单位进行偏移的语法——Store Bye，Load Byte
sb和lb，偏移量允许是byte的任意整数倍，可以运输诸如颜色值这样的一字节长度数据

符号扩展：将有效最高位符号位复制到剩余高位字节中为0的位
无符号扩展：lbu指令Load Unsigned Byte，只是简单把字节复制过来，高位以0填充

计算机决策的实现——分支指令

# 有条件分支指令
beq reg1, reg2, L1
# if(reg1的值) == reg2的值，goto L1标签的位置执行代码
# else 继续执行下一行
# beq——branch if equal
# bne——branch if not equal
# blt——branch if less than
# bge——branch if greater or equal than
# bltu——branch if less than （unsigned）
# bgeu——branch if greater or equal than （unsigned）

# 无条件分指令
# j label
# j——jump，跳转至lable处。类似goto

#注意：条件分支中不能与立即数进行比较，只能寄存器与寄存器进行比较

example：

// C Code
int A[20];
int sum = 0;
for (int i = 0; i < 20; i++)
    sum += A[i];

# RISC-V Code
add x9, x8, x0	# x9 = x8 = &A[0]
add x10, x0, x0 # int sum = 0
add x11, x0, x0 # int i = 0
addi x13, x0, 20# i_max = 20
Loop:
    bge x11, x13, Done
    lw x12, 0(x9)	  # x12 = A[i]
    add x10, x10, x12 # sum += A[i]
    addi x9, x9, 4    # x9 = &A[i+1]
    addi x11, x11, 1  # i++
    j Loop
Done:

8. RISC-V: Decisions II

位运算的汇编

位与

# Register
and x5, x6, x7	# x5 = x6 & x7
# Immediate
andi x5, x6, 3  # x5 = x6 & 3

位与用于Masking：
andi 一个 0000 00FF，可以提取出最低的那个有效字节
andi 一个 FF00 0000，可以提取出最高的那个有效字节

位非

没有该指令，但只需与全1的立即数进行XOR异或即可

位移

逻辑位移:

# 左移——sll：shift left logical
# Register
sll x11, x12, x13	# x11 = x12 << x13
# Immediate
slli x11, x12, 2	# x11 = x12 << 2

# 右移——srl：shift right logical
# 与左移用法一样

逻辑位移的十进制意义：左移n位，相当于原十进制数乘以2^n^，右移是除以2^n^并取整

算术位移（只有算术右移）：
一般有符号数的右移都是算术右移：用符号位的数值填充右移产生的空位
算术右移的十进制意义：原十进制数除以2^n^并向0取整
注意：C的算术右移要求：右移除法后，向0舍入取整！

# sra——shift right arithmetic
# srai——shift right arithmetic immediate
# 用法见逻辑右移代码

程序是如何存储和执行的

经过汇编器Assembler以后，生成.o文件，即机器码文件。由于这些文件太大，因此不会存在寄存器里，而是存储在内存中，存储.o的内存区域叫做Program区域。Program区域的数据其实就是一系列由字word宽度为单位的数据组成的RISC-V指令。

Program Counter——一个特殊的寄存器，位于处理器内部，存储着将要执行的下一条指令的字节地址
如果是顺序执行时，下一条指令的字节地址是当前指令地址加上一个字word（四个字节）

汇编中的一些语法上特性

符号寄存器名称Symbolic Register Names

--> a0~a7

x10~x17 --> a0~a7  用于函数调用的参数寄存器
x0      --> zero   代表0

伪指令Pseudo-instructions

一些指令用于简化常见的汇编操作（不需要使用基础指令做大量拼接，简化为一个伪指令，类似语法糖）
但实际上伪指令只是便于我们增加汇编代码可读性，底层会转变为对应的基础指令的组合
example：

mv rd, rs  # 等价于 addi rd, rs, 0 	 mv——move value
li rd, 13  # 等价于 addi rd, x0, 13     li——load immediate
nop	       # 等价于 addi x0, x0, 0		无操作

9. RISC-V: Procedures

RISC-V中的函数调用

RISC-V函数调用的规范：

1. 调用函数的主程序把参数放在函数可以找到他们的地方——设置一系列寄存器
2. 使用一条指令将处理器的控制权交给函数——跳转和链接指令 jal
3. 函数获取其需要的局部资源
4. 函数执行其指令
5. 将返回值放置在主程序能获取的位置，并且恢复所有改变的寄存器到调用前的状态（回收清理）
6. 调用指令将控制权交回给主程序如 ret

a0~a7作为8个函数参数寄存器argument register；
其中a0和a1将保存函数的返回值；
x1保存返回地址return address——我们称为ra；
s0~s1（x8~x9）和s2~s11（x18~x27）存储寄存器saved register

jr ra	# 在函数调用结束后，从函数返回到ra返回值地址上。不使用j，因为j后得带着一个硬编码lable
jal FunctionLabel # jump and link：自动存储返回值地址到ra，并且jump到函数地址上
ret		# 等价于 jr ra  跳转回返回值地址

# j, jr, ret都是伪指令
# jal和jalr是基础指令

汇编中的栈

s0~s1， s2~s11一般都会用来存储函数中产生的局部变量，但是我们知道函数结束后，寄存器要恢复到调用前的状态。假如函数中产生了局部变量int f 存储在了寄存器s0中，那么s0中的值放在哪里才能在函数结束时被恢复呢？
答案就是——栈！
为了追踪栈内存，我们需要使用一个stack pointer栈内存指针sp，追踪当前栈的地址。
这个指针sp在RISC-V中规定存在寄存器x2中

栈内存一般是从顶部开始，向下增长。因此入栈是递减栈指针，出栈是递增栈指针。

通常，每个函数都有一组需要放在栈上的数据，我们称之为——栈帧stack frame（也叫堆栈帧，堆栈也指栈）
栈帧——存储返回值地址，返回值，参数，局部变量等一切东西
栈指针sp告诉我们最后一个栈帧的内存地址，即栈的最底部元素在哪里。

example：

// C Code
int Leaf(int g, int h, int i, int j)
{
    int f;
    f = (g+h) - (i+j);
    return f;
}
// 我们认为在汇编时会需要生成两个局部变量才行（ghij是参数有参数寄存器）

# RISC-V
# Leaf():
# 以下三行叫做序言Prolog，为函数调用做前提准备
addi sp, sp, -8		# 在栈中分配两个字存放两个局部变量，因此栈指针-8
sw s1, 4(sp)	    # 将存储寄存器中的局部变量值store word存储至内存中距离sp指针4个字节偏移量的地址（向上）
sw s0, 0(sp)	    # 将第二个局部变量值store word存储至内存中距离sp指针0个字节偏移量的地址（向上）
# 接下来是函数的具体指令
add s0, a0, a1	    # f = g+h
add s1, a2, a3	    # s1 = i+j
sub a0, s0, s1	    # return f = (g+h)-(i+j)
# 准备函数返回了，先进行恢复——以下三行叫结尾epilogue
lw s0, 0(sp)	    # 恢复s0中函数调用前存储的值
lw s1, 4(sp)
addi sp, sp, 8	    # 上移栈指针

jr ra			   # 函数返回

普通函数调用的过程中会产生的问题：

以上是主程序调用一个函数时会发生的过程，但是你肯定会思考，那么函数中调用函数呢，我们知道返回值地址存放在x1即ra寄存器中，那么下一次调用就会覆盖掉第一次调用时的返回值地址，参数寄存器也是同样的道理，因此，肯定有一套解决方案，请看如下！！

嵌套函数

Caller——调用者
Callee——被调用者

在使用jal指令时，会把寄存器分为保留寄存器Preserved Register和临时寄存器Volatile Register两

1. 保留寄存器——在第一个函数调用过程中函数修改过的寄存器，如上面Leaf函数里的存储寄存器s0和s1，
   第一个函数会把s0和s1的值存在栈帧中，同样的第二个函数也会把第一个函数修改过的s0和s1存入栈帧，自己再覆写s0和s1寄存器，由此循环往复！

   但注意，并不是所有的存储寄存器s0~s11都需要被写入栈帧，只有函数需要修改的那些才需要被写入，其他的不动！

2. 临时寄存器——返回值地址寄存器ra，参数寄存器a0~a7，这些临时寄存器变量大概率会被下次函数覆写，那些可能会被修改的临时寄存器才需要被存入栈帧中——要看情况！

下图说明了寄存器地存储情况，注意最右边一列是这些寄存器的值被存入了谁的栈帧中

嵌套函数的example：

// C Code
int sumSquare(int x, int y)
{
	return mult(x, x) + y;
}

# RISC-V
sumSquare:
addi sp, sp, -8  # push stack
sw ra, 4(sp)
sw a1, 0(sp)	# save y
mv a1, a0	    # mult(x, x) --> mult(a0, a1)
jal mult	    # 注意调用mult函数后，a0寄存器将存储着mult函数的返回值
lw a1, 0(sp) 	# 恢复y
add a0, a0, a1 	# a0 = mult(x,x) + y
lw ra, 4(sp)    # 恢复return address
addi sp, sp, 8  # pop stack
jr ra

C内存分配 vs 汇编内存分配

C内存分配：

1. Static内存区：静态变量
2. Heap内存区：malloc动态分配的内存
3. Stack内存区：函数调用过程中的栈帧的内存

各内存区的具体位置：
Stack位于内存最顶部的位置，向下扩展，有一个栈指针sp指向stack区域
RV32标准下的Program（存储程序的文本数据）规定位于地址0001 0000~16进制~地址处（很底部位置）
Static位于Program的上面，有一个全局指针gp指向static data区域
Heap位于Static的上面，向上扩展

RISC-V指令集架构汇编语言总结！

基础指令：

10. RISC-V: Instruction Formats I

RISC-V指令在二进制中的底层表示方式

为了遵循和数据大小的一致性，RISC-V中每一条指令的大小都为32-bit
32位可以表示至多2^32^，数量过多，为此我们会把32位的指令切分为字段fields，这些字段会给处理器一个线索，告知处理器这个指令的信息：什么类型的指令，对哪些寄存器进行操作
RISC-V的常见指令fields区分如下：

R-Format 算术和逻辑运算的寄存器-寄存器指令

R-Format将指令分为6个字段Fields：

opcode 操作码 7-bit

0-6 opcode 操作码 7-bit   （所有R-Format格式的指令操作码都是一样的：0110011）
7-11 rd 表示目标寄存器的二进制代号 5-bit		（5-bit是因为寄存器有32个，刚好可以对应到其中一个寄存器）
12-14 funct3 3-bit
15-19 rs1 表示源寄存器1的二进制代号 5-bit
20-24 rs2 表示源寄存器2的二进制代号 5-bit
25-31 funct7 7-bit

funct3和func7这10-bit数据决定了指令是执行哪种操作

R-Format指令的一个实际例子：

R格式的所有指令如下：

# 新指令
slt rd, rs1, rs2
# slt——set less than 小于
# rd == rs1 < rs2 ? 1 : 0

注意到在高位第二位为1的指令都需要应用符号位扩展的操作——sub和sra

I-Format 立即数指令

I-Format的格式和一个具体指令：

I-Format所有指令

注意事项：
1.涉及到位移的相关操作时，位移量限制为5位（图中shamt），因为寄存器是32位的，位移超过五位是无效的
2.指令有九条，但funct3只有3位最多支持8个编码，因此看到srli和srai共用了101编码。但是由于位移量限制为5位，因此高位的前七位可以被用于编码区分指令，这里遵循类似R-Format中第二高位位1代表需要符号扩展的规范，此处高二位为1也代表需要符号扩展，实际上带表指令srai——因为shift right arithmetic immediate 就是需要符号扩展的！

Load指令

Load指令需要rd，rs1，immediate三个要素，因此可以使用I-Format，但更改其opcode

为啥lw没有unsigned版本？
因位寄存器有32位，load word也是32位，不需要进行符号扩展，刚刚好填满对应。
而lb，lh，load byte和load half byte都需要进行符号扩展，即有效低位写入，高位以有效位中最高位（符号位）复制填充，而他们对应的unsigned版本就不需要进行符号扩展，仅以0填充

S-Format 存储指令

S-Format格式和指令实例

Immediate被分为高位7位和低位5位，实际上操作时会合成12位来看待这个立即数。分开两个地方在我们看来很混乱，但这样分，可以尽可能保证rs2寄存器的二进制码位于和其他格式相近的位置，有利于处理器的操作和硬件设计！

所有的S-Format指令：

11. RISC-V: Instruction Formats II

B-Format 分支指令

**PC相对寻址：**根据Program Counter当前指向的指令为基础，相对寻址下一条指令的内存地址
PC指针的单位是一个字Word（四个字节byte）

如下图：顺序执行和跳转分支，两种情况（注意下面的情况其实不适用于RISC-V，因为其支持压缩指令集！）

分支跳转时，加给PC的这个立即数可以是正数也可以是负数，对应分支向前和向后跳转！

压缩指令集

指令集架构的一个子集，其指令是16-bit的。在某些情况下，比如闪存中，为了保证内存的紧凑型，缩小占用空间。

RISC-V的实际PC寻址方式——为了支持压缩指令集的16位和普通指令集中的32位，需要以半个字，两个字节为单位

这里immediate * 2只是代表寻址的增减数是2的倍数，实际上二进制存储的时候偏移量是多少字节就以立即数的二进制形式存下，不需要再*2

举例如下，16字节的偏移量，换算成二进制立即数，由于寻址偏移以2字节为单位，因此立即数最低位一定为0，否则就是奇数了，因此，我们可以用12-bit来表示13-bit的立即数，并且按照如下B-Format的方式存储，最左边是存储最高位数

所有的B-Format分支指令

U-Format “Upper Immediate上部立即数” 对长立即数的处理

在I,B,S-Format中，立即数都由12位进行存储，如果想以32位存储，则还缺失20位。此时我们引入上部立即数格式

# U-Format的两条新指令——lui和auipc 基础指令
# lui - Load Upper Immediate 将上部立即数加载到目标寄存器rd，并将最低12位置零
# auipc - Add Upper Immediate to PC(Program Counter) 将上立即数添加到PC并且将结果存储在目标寄存器rd中
Label: auipc x10, 0  # 把Label这个标签的地址的上20位放入x10寄存器

加载长立即数的例子：先lui存储高20位，再用立即数加法加上低12位

符号扩展带来的立即数加法问题！

如果你转换成二进制来看就会发现，由于addi加法会进行符号扩展，最终导致加完高20位中最低位减去了1！

解决方法：进行lui操作时就给lui的上立即数再加上1，这样底下addi加法后-1就会抵消得到正确值。幸运的是，我们有伪指令

适用于加载长立即数的伪指令——li （Load Immediate）

# Load Immediate
li x10, 0xDEADBEEF

J-Format jal指令

jal 会将PC + 4的值存储在目标寄存器rd中，作为返回地址（这里的值是一个相对值，因为PC是相对寻址的）
随后让 PC = PC + Offset进行跳转
注意这里立即数（代表的跳转标签）是20位，但由于我们跳转指令是2字节为单位，因此最低位一定是0，所以这里存的是除了最低位的20位。也就是说这里immediate实际上可以存到21位

j Label == jal x0, Label # 等价式
jal ra, FuncName

jalr指令 使用I-Format，这个指令是用于跳转到绝对地址的方法

RISC-V Instruction Formats 总结！

12. CALL——编译，汇编，链接，加载

翻译与解释

翻译：从高级语言一步步转换成机器语言——C的编译过程
解释：将高级语言通过解释器直接解释为不依赖于体系结构的代码并执行——解释与执行一同进行，低性能
Java是半解释型语言，先经过Java Compiler编译为不依赖于机器结构的代码，再经过Java解释器解释代码

解释器的一些实际作用——模拟器

我们可以在现代硬件中通过模拟器执行古老硬件的代码，比如执行老游戏机的游戏，二者使用不同的指令集，这就是通过假装这个模拟器软件是一个硬件，并把老游戏的代码通过解释器解释为可执行的代码，在模拟器软件层面执行。虽然代码的解释和执行并没有得到硬件的帮助和加速，但成功获得了兼容性，非常神奇！

编译器：main.c -> main.s

将C代码翻译为汇编代码—— 这里翻译过程中编译器会根据你的编译参数做一些优化操作

汇编器：main.s -> main.o

将.s 汇编代码中的伪指令替换成基础指令，使用一些神奇的汇编指令，创建一些表，将汇编代码转为机器码，输出目标文件.o

以下是一些指令，在汇编器解析.s文件的过程中用于指示接下来的数据是什么类型的内容

重定位表Relocation Table

对于那些需要引用外部数据，静态数据，或者说通过绝对地址来获取的数据来说，在汇编器阶段是无法决定的，只有那些相对寻址的可以被确定下来。为此，汇编器会生成一个重定位表来把这些需要绝对地址的地方标上重定位符号，以便在最终链接阶段重定位最终的绝对地址

符号表Symbol Table

哪些符号（标签）可以被其他人调用或引用，以访问我的函数或数据

Object File Fromat目标文件.o 的格式

链接器: main.o + XX.o -> a.out

1.把所有text段数据按顺序从各个.o文件中取出放在一起
2.把所有data段数据按顺序取出放在一起
3.解决引用问题：浏览所有的重定位表，解决重定位问题——把绝对地址替换掉重定位符号的位置

四种寻址方式

静态链接与动态链接

静态链接：把所有.o文件链接起来，并且输出到可执行文件里，此时所有数据包括库文件的也加入到可执行文件
动态链接：有一行代码，标识需要include一个库，但是这个库的内容并没有加入到可执行文件中，只在可执行文件运行时去加载——也就是把责任推给加载器Loader，而非链接器Linker来做
注意动态链接这一步目前来说都是在机器码层面进行的链接

动态链接的好处在于当一个庞大的库更新时，其他动态引用这个库的可执行文件都不需要重新编译，因为是在运行时引用

加载器：

加载器的任务是把可执行文件从磁盘中加载到内存中，设置所有需要设置的东西，并且运行之——这实际上是操作系统的任务之一

Example：Hello World

Hello.c

#include <stdio.h>
int main()
{
    printf("Hello, %s/n", "World");
    return 0;
}

经过编译器 ->
Hello.s

经过汇编器 ->
Hello.o

图中只有中间的二进制码部分是存在于.o文件中的，其余都是便于阅读理解
其中标红的部分是涉及到绝对地址的，因此填上0需要链接器进行重定位！

经过链接器 ->
a.out

13. 同步数字系统简介

同步：所有操作都由一个“时钟”来控制
数字：现实世界中的电压值将被用于表示0，1这两个离散值

逻辑门的诞生

香农在论文中发现了电路与逻辑的关系，在其论文中联系起了电路与数学家乔治布尔的布尔代数，命名为Boolean

晶体管Transistor

是一种半导体器件，可以通过另一个源来控制其处于导电或者不导电的状态。晶体管可以通过控制作为放大器和开关的作用。
现代数字系统：CMOS——Complementary Metal Oxide Semiconductor 互补金属氧化物半导体

充当开关的MOS晶体管的电路图

与非门NAND Gate —— 可以用来构建与，或，非门

信号与波形

信号：通过导线传输，当数字值被视为0和1时才可视作信号，一条导线只有一个信号，会存在延迟

加法器电路

将4bit的电压值加和视作一个值

可以看到加法器存在延迟，如图中A = 3, B = 10的初始，C仍然等于上一次结果。这个延迟称为加法器传播延迟

计算机工程中的两类电路（大类）

组合逻辑电路

没有副作用，不记录状态，没有记忆，输出只与输入有关，相同的输入得到相同输出
eg. 加法器

时序电路（状态电路）

有状态变化，有记忆特性
eg. 寄存器，缓存，磁盘，内存

14. 时序电路（状态电路）

累加器

寄存器

一个n位的寄存器由n个一位的触发器（FF）组成！

触发器——上升沿触发型（意味着在Clock时钟从0到1的时候被触发）

回顾——所有时间延迟，寄存器，触发器相关的名词

有限状态机FSM

抽象的电路图如下：
CL: Combination Logic 组合逻辑电路
PS: Previous State
NS: Next State

15. 组合逻辑电路

数据多路复用器 Data Multiplexors

二路复用器，a，b，s三个输入，得到一个输出。其中s是控制作用，结论是：
c = (~s)a + sb
即：非s为真，c的值取决于a；s为真，c的值取决于b

其实就是多路中只有一路决定输出

算术逻辑单元 Arithmetic and Logic Unit (ALU)

摆烂了…随意看了下加法器与减法器电路，=

16. 单核CPU设计-1 数据通路

数据通路 Data Path

处理器中包含执行指令集架构中所有指令所需的硬件部分

控制 Control

控制数据路径，告诉路径如何设置自身

执行汇编指令的几个步骤

1.指令获取
2.指令解码
3.寄存器访问
4.执行阶段
5.内存访问
6.写回阶段

add指令的数据通路设计

指令 add rd, rs1, rs2 的数据通路：

上述add指令的延时图：

sub指令的数据通路设计

可见，只是给ALU单元上增加了一个控制元件，选择是执行加法还是减法即可
其他R-Type指令也采用相同的数据通路设计，只是控制这里改变一下即可！

addi 立即数加法指令的数据通路

在刚刚R-Type指令数据通路基础上，加上一个mux（多路复用器），和对应的控制单元BSel，效果是当BSel的信号为0时，多路复用器的输出等于rs2，BSel为1，多路复用器的输出等于Imm立即数。
此数据通路就是RISC-V中R-Type和I-Type指令共享的数据通路，可以支持以上两种类型的指令！

Imm立即数的生成

Imm Gen模块：

将指令内存的addi指令上的imm部分的12位连上立即数的12位，寄存器高20位符号扩展（复制）imm的第十二位

17. 单核CPU设计-2 数据通路

load word指令的数据通路

为了支持load word，数据通路增加设计如下，加入与内存的交互

支持store word指令

S-Format指令中，立即数被分开在两个部分，而I-Format中就在最高12位
因此我们的立即数生成单元需要进行修改以支持这两种立即数格式
不过可以注意到二者最高7位都在最高位，因此这一块可以不变，而且选择最高位进行符号扩展也没有问题
接下来就是添加一个多路复用器，选择I格式时，取接下来的五位，选择S格式时，取11-7位的五位

在数据通路设计上，立即数生成器做如上更新，同时加入一个rs2指向内存中的写入线路，同时设置内存Data Memory的MemRW信号为Write写入即可，这样就可以把寄存器的值写入内存中

支持分支指令

分支指令的数据通路

1.我们需要将立即数生成器设置为B-Format立即数类型
2.我们需要将Branch Comp模块的控制信号设置为无符号或是有符号
3.我们需要控制ALU单元前的黄色的多路复用器，确定输入ALU的是寄存器的值还是Program Counter的值

Branch Comp模块

B-Format中的立即数生成器

B格式的存储方式如下，可见imm[11]放在立即数中的最低一位（指令位第七位），因此在生成立即数时，需要将这一位移动到最高第二位

在立即数生成器中，只需使用一个一位宽的多路复用器，选择是否移动该位的数字即可

支持JALR Jump and Link Register指令——I-Format

将PC+4的值写入rd寄存器作为函数调用的返回地址，通过将rs+immediate的值写入PC来跳转到对应函数（绝对寻址）

JALR数据通路，仅在原基础上添加了黄线内容

支持JAL Jump and Link指令——J-Format

有20位宽的立即数
PC+4的值写入rd寄存器作为函数返回地址
设置PC = PC + immediate 作为PC要跳转到的函数地址（相对寻址）

可见我们支持该指令只需添加J-Format立即数生成即可

支持U-Format——长立即数

U格式只有两条指令：LUI和AUIPC
lui将20位长立即数加载到rd寄存器中，并将低12位清零
auipc将长立即数与PC相加，得到的结果存储在rd中

RISC-V单核CPU数据通路总图

可以支持所有的汇编指令！

18. 单核CPU设计-3 控制模块

CSR ——Control and Status Register

控制和状态寄存器：与我们的32个通用寄存器分开，有多达4096个.常用于监控状态和性能以及与其他设备（如外围设备）进行通信

CSR相关的指令格式如下

# csr read write 将csr内容复制到rd中（rd不是x0寄存器时），并且将rs1的内容复制到csr中
csrrw rd, csr, rs1

指令的Timing

add指令的延时图：

其中X表示一束输出或输入端口（在此是32个端口）

关键路径：指令执行中耗时最长的延时路径
在此处add中是执行阶段，下图深黄色路径

控制逻辑设计

控制模块其实就是一张表，选取一个要执行的指令后从中读取要设置的控制信号的值即可！

设计控制逻辑，我们可以使用一个只读的写死的内存表，也可以使用一堆与门和或门。在实践中，我们使用后者

如图，指令解码后，会有唯一一条指令黄线亮起，并且寻址到只读内存表（右边部分）对应该指令的控制信号内容处
这个地址解码器是一个很大的与门。控制信号的输出部分则是一个巨大的或门

add指令的与门解码如下：

22. Caches-1

二进制前缀

快速推导寻址的简洁记法

比如2^34^bit是多少，十位数是3，因此是G，个位数是4，因此是2^4^=16
答案是 16GB！

Cache出现的原因——CPU速度和访问内存的速度的差距问题

可见CPU性能提升远远大于内存的提升，随着技术升级，由于不断加入新的东西和新的计算机元件，内存的物理距离可能就离CPU寄存器很远，同时访问内存的指令从只需要一个变化到了几千个，访问内存的速度会严重影响指令执行效率，因此我们迫切需要一种技术来解决该问题

Cache是什么

Cache缓存始终是内存内容的一个副本

Cache是一个位于CPU上的存储空间，其速度，容量，价格都介于DRAM和寄存器之间，因此是一种折中之举

内存层次结构（宽泛的内存）

寄存器 <— 缓存 <— 内存 <— 磁盘

Cache的设计原则

时间局部性

如果我最近使用过它，我很可能很快就会再次使用它

空间局部性

如果我访问了某个内存位置，我很可能很快就会访问其邻居

23. Caches-2

直接映射缓存

如上图，四个字节为一组且一个block是一个字节时，内存中一个字节存入缓存的位置只需看内存中地址最低两个有效位的值mod4即可找到！
但是可以发现，我们这样确实把内存中的字节复制到了缓存中，但是我们并不知道缓存中蓝色区域存储的那个字节是内存中哪一块蓝色的字节！

缓存中持有数据的单位称为block，一个block可能是一个字节，也可能是多个

Block的宽度大于一个字节时

我们在缓存中加入一个tag标签，用来指示同样映射到缓存中蓝色区域的block是内存中的哪一块block
那么这个tag符合什么规范呢？

tag为了简洁，指定如下：
将cache的大小搬入内存中，以cache大小完全划分所有内存，然后从0开始编号如上图黄色的0，1，2，3
每一cache大小的内存区域对应在cache里的编号即为划分的编号！

然后，找到在一个tag里的数据，我们还需要确定该数据在cache中的第几行（蓝色？红色？黄色行？）第几列（左边还是右边？）

行数的确定我们称为index
列数的确定我们称为offset
cache映射宏观区域的确定我们称为tag

最低位的集合，即index和offset决定了Area
offset告诉了我们Area的width，index告诉了我们Area的height
offset = 一个block所包含的字节的数量（一个offset对应一个byte）
index = block的数量（一个index对应一个block）

可见index * offset = Area = 该cache中数据所对应的字节地址数！
再通过该cache的tag确定区域，即可知道该地址的绝对位置！

32位指令集架构机器Cache的约定：
一个block有两个字节，因此offset需要一位来确定
一个cache区域占有8bytes，因此需要四行，即四个index，因此index需要两位来确定
剩下29位即确定tag

访问内存的实际流程

发送内存访问指令，首先来到缓存，检查缓存是否持有该地址的copy，如果有立即返回
如果没有，则向内存地址发送请求，获取到地址上的数据后，将这一数据所在的一整个block都送回给缓存，缓存再返还给寄存器

Cache相关术语

cache命中

访问内存数据时，该数据刚好在cache中

cache未命中

cache中那块内存为空

cache未命中且块替换

cache那个地方有数据，但并非我需要的数据

cache命中率

cache命中的次数占总内存请求次数的比例

未命中惩罚

从内存中获取数据来替换cache中block的时间称为未命中惩罚

命中时间

访问缓存所需要的时间

$

$ 被视为cache的符号记号

cache的有效位

在tag的最高一位设置成有效位
该位为0时，表示cache中该内存是垃圾数据，永远不会被命中
为1时，表示该内存已被填入有效数据了，有可能被命中？

24. Cache-3

访问Cache的过程示例——读取数据

有一个block为4个word即16字节宽的，10个index高的cache
我们要访问的内存地址为 下图顶部的地址

查找的顺序为：Index -> Valid -> Tag -> Offset 即 IVTO

先看index是什么，确定在cache的第几行，接着看最高的有效位是0还是1确定是热缓存还是冷缓存。
如果是0，则立刻到实际内存地址中取出该地址所在的**一整个block的数据（也就是16字节数据）**并加载存储在cache对应位置中，更新cache中的tag，把此index行有效位设置为1，再根据offset的值把cache中刚刚存储的数据返回

如果有效位是1，如上图情况，则执行IVTO的T，查看Cache中该index数据的tag是不是跟我要访问的内存地址相匹配，此处匹配，那么查询offset找到cache中的数据并返回

如果index步骤找到了cache中的一行，且valid有效位为1，如下图，但是tag发现不匹配
那么说明cache中存在这一行的数据需要被替换
执行缓存未命中且块替换操作，访问内存实际地址把一整块block存入cache的这一行
更新cache中的tag等信息

写入数据时cache和内存发生了什么

如果要对同一个内存地址读取，写入，读取，再写入，再读取
如果每次写入都要既更新cache又去更新实际内存地址中的数据，那么这个操作将会非常低效
因此我们对写入更新做一些优化！

该优化的思想就是更新cache中的内容，但是实际内存中的内容先不去修改！

Dirty bit 脏位

类似valid bit，我们加上一个dirty bit，该位为1时，表示cache中该block的数据和实际内存地址中对应block数据不相同！
当cache中dirty bit为1的block在被读取时需要进行块替换时，我们才被该block的数据写入到内存实际对应block中去！这样就可以保证我们的写入数据能够被成功写入且极大提高性能效率

Block的大小

如果block很小，那么我们的cache命中率将会降低
如果block很大，那么我们的未命中惩罚将会增加（未命中时付出的代价）

因此设计block大小，需要考虑这两个因素，通过相乘两者图像找到最低点

完全关联缓存

这种缓存下，我们不再记录一个block的index，只留下tag和offset
不保留index的好处是，原来有index时，会出现映射到相同index的不同tag的数据，这种情况发生时需要进行块替换操作

现在，由于没有index，所以不会发生映射到同一个位置的情况，但是要实现完全关联缓存，缓存必须几乎无限大（足以存下整个内存的数据），显然这是一个理想状态。如果缓存不是无限大的，那么必然会发生同一个位置出现不同数据，但此时不同数据出现的原因是缓存不够大，因此这种cache未命中称为 容量未命中 （刚刚的块替换未命中称为冲突未命中）

25. Caches-4

组相联缓存 Set-Associative Caches

N路组相联缓存：每个set里面有N个block
原来的Tag，Offset含义不变，Index变成这里的set

在每个Index里，内存是完全关联缓存的形式

一个大于1路的组相联缓存，既能够获得直接映射缓存的优势，也能够解决块替换未命中（冲突未命中）的低效问题！

块替换策略

LRU(Least Recently Used)——最久未使用位：
记录最近是否访问的cache位置，常见策略是
对于一个2路组相联缓存，index为0的set中，一个block有两个字节
如果第一次强制未命中为offset为0，则，第0字节被加载数据，且设置其LRU位为0
同时设置offset为1的LRU为1，表示其是最久未使用位

下次命中到此index时，会优先替换LRU为1的offset位置

平均访问时间

平均访问时间 = 命中时间 + 未命中率 * 未命中惩罚

多级缓存

有了多级缓存后，
平均访问时间 = （L1命中时间 + L1未命中率 * L1未命中惩罚）
但是 L1未命中惩罚 = （L2命中时间 + L2未命中率 * L2未命中惩罚）
…
如此递归下去！