计算机体系结构学习---RISC-V（⼀）
计算机体系结构学习 --- RISC-V（⼀）
1、Instructions for making decisions
条件语句实际上有6种类型，最基本的有两种：
beq rs1,rs2,L1 //若rs1=rs2，那么跳转到L1
bne rs1,rs2,L1 //若rs1!=rs2，那么跳转到L1
这两个指令都是关于有符号数的等于和⾮等于的关系，但是⼤⼩⽐较除了这样的关系之外，还有⼤于，⼩于等于这样的关系，因此有：
若与中均为补码，且和相⽐，更⼩，那么就取该分⽀若，采取该分⽀
若与中均为⽆符号数，且和相⽐，更⼩，那么就取该分⽀同理，若和均为⽆符号数，，采取该分⽀
长颈鹿生活在哪里
条件语句的运⽤范围⾮常⼴泛，包括Loops(循环)，Bounds check shortcut(索引检查)，Ca/Switch statement(⽤于Ca/Switch)等等；
（1）Loops:
举⼀个例⼦，以C语⾔为例：
while(save[i] == k)
i += 1;
我们设save数组的ba地址存在x25，i：x22，k：x24；那么就有asmbly programmable language为：
Loop:
slli x10,x22,3 //i*8
add x10,x10,x25 //x25+x10，确定新save[i]的地址
ld x9,0(x10) //将save[i]的值读⼊x9寄存器中
bne x9,x24,EXIT //若x9==x24，就跳转EXIT
addi x22,x22,1 //i+1
beq x0,x0,LOOP //⾮条件跳转，⼀定会返回LOOP处
EXIT:
其中，条件语句外的简单语句被称为basic block。编译中要做的第⼀件事就是将程序打平成basic block的形式，后⾯会说到。
（2）Bounds check shortcut:
这是⼀种特别的情况，例如如下代码：
bgeu x20,x11,IndexOutofBounds //若x20 >= x11，或者x20<0的话，那么就可以将branch引向索引越界
（3）Ca/Switch statement:
利⽤branch address table/branch table(选择条件序列的地址表)，程序只要索引到表中，再分⽀到对应的quence中即可；其
中，branch table是存放着双字地址的表格；
条件语句包含跳转含义，⽽实⾏跳转还有⽆条件跳转语句，RISC-V中提供了两种⽆条件条件语句，包括jalr和jal。
2、Supporting Procedures in Computer Hardware
（1）对于程序中包含两种特殊跳转，procedure/function，过程/函数；关于过程和函数的执⾏流程略。尚渔味
其中⽤于分配procedure的32位寄存器有x10-x17，⽤于存储返回值。⽽x1是⽤于返回原来地址的寄存器。
在过程语句和函数语句中，有两种⽆条件跳转，分别为jal(jump-and-link instrcution)，这个语句使⽤⽅式如下：
jal x1,ProcedureAdress //跳转到ProcedureAdress处，并将原来程序的地址写⼊x1
⽽jalr⽤于返回原来的地址，如下所⽰：
燕窝怎么做jalr x0,0(x1) //⽆条件跳转回原来的程序地址，⽤于跳转caller程序
⽤于存储当前地址的寄存器，称为PC(program counter)。在连续执⾏的情况下，⽤jal实现，每次返回的地址设为PC+4，再存⼊x1即可。或者有jal x0,Label，即⽆条件跳转⾄Label处，但是不返回任何值作为存储。
其中，有⼀个很关键的⼀点是，就是寄存器值是有限的，我们有的时候需要不⽌8个寄存器，此时我们使⽤stack（堆栈）对需要返回的地址和要⽤到的值进⾏存储。这样的过程称为spil registers to memory。特别注意的是堆栈的地址是从⾼到低的。
堆栈是⼀种last-in-first-out的队列。在使⽤堆栈时，我们需要⼀个堆栈指针sp(stack pointer)，通常是x2。
举⼀个典型例⼦，以C语⾔程序为例:
long long int leaf_example(long long int g,long long int h,long long int i,long long int j)
{
long long int f;
f = (g+h)-(i+j);
return f;
民政工作
}
设g,h,i,j分别分到了寄存器x10,x11,x12,x13中，temp变量分到x20中，(g+h)分到x5，(i+j)分到x6中，其中，x20,x5,x6要被保存下来，将结果转为RISC-V的汇编语⾔，即为：
addi sp,sp,-24
sd x5，16(sp)
sd x6,8(sp)
sd x20,0(sp)
add x5,x10,x11 //x5中存储的是g+h
add x6,x12,x13 //x6中存储的是i+j
sub x20,x5,x6 //x20为f
addi x10,x20,0//将f的值放⼊x10中传递回去
ld x20,0(sp)
ld x6,8(sp)
ld x5,16(sp)
addi sp,sp,24 //删除这个堆栈
但是如果堆栈中的每⼀个值都需要被保存的话，是没有必要的，尤其对于⼀个leaf procedure⽽⾔，有些temp是不⽤被保存的。
因此32个寄存器被分为两组：
对于函数相互调⽤的情况下， 有x1会互相冲突，此时需要将x1也保存下来。
x3可以设为global pointer。
有的时候，为了⽅便的获取堆栈中的值，我们还会设置⼀个frame pointer，fp，存在x8中，令其⼀直指向堆栈的栈顶。
（2）内存分配，内存分配是⼀个很重要的概念。数据，程序等等在计算机内存中存放按照由⾼到低
分别为stack，dynamic data，static data，text，rerved的顺序。⽽stack由上向下，其余由下向上。text中存⼊的是program code。
具体使⽤后⾯讨论编译器的时候会说。
3、Communicating with people
我在第38周的周报中已经讨论过这个问题，就是关于加载值的字长的问题，后⾯还会再说到。字长通过不同的指令可以加载
byte，halfwords，doublewords，words四种。
4. RISC-V Addressing for wide immediates and Address
（1）这⾥涉及到⼀个问题就是当需要加载的⽴即数不⽌12bit长度的时候，我们没有办法使⽤ld这样的命令。我们采⽤⼀种新型的指
令，lui(load upper immediate)。这种指令不是ld这种I-type，⽽是U-type，事实上，U-type只有lui这⼀种命令。其可以⽤于加载20-bit ⽴即数。其余12bit⽤0填充。
例如我们需要将⼀个64-bit的⽴即数放⼊寄存器x19中，则有 0000 0000/0000 0000/0000 0000/0000 0000/0000
0000/0011 1101/0000 1001/0000 0000。
使⽤lui将下划线的值存⼊x19中，即有
lui x19,976
这时再使⽤
addi x19,x19,1280 //0000 1001 0000 0000
即可获得正确的64bit的值。
（2） 对于bne这种判断语句，为SB-type，它有12bit的⽴即数，为了可以获得所有的地址值，因此其求地址的⽅法是PC-relative addressing。
由于SB-type这样的格式提供⼀个符号位，因此可以向前和向后进⾏跳转12bit。
其格式如下所⽰，以陇州
bne x10,x11,2000
为例：
imm[12]imm[10:5]rs2rs1funct3imm[4:1]imm[11]opcode
01111100101101010001100001100111
但是因为bne这样的语句只可以跳转到偶数地址上。
但是PC-relative addressing 仅仅针对的是12bit内相关的地址，因此在地址位于12bit之外的情况，我们需要有⼀种可以跳转的格式：
beq x10,x0,L1 //在x10 == 0的时候，就跳转到L1处，假设L1⾮常远，则有
=>
bne x10,x0,L2
jal x0,L1
L2: //即若x10 ！= 0就跳转到L2处，否则就⽤L1跳到别的地⽅去
（3）对于jal语⾔，为UJ-type。它可以跳转到20-bit之外的地址。此时有UJ-type的格式为：
以
jal x0,2000
为例，有
imm[20]imm[10:1]imm[11]imm[19:12]rd opcode 0111101000000000000000001101111
（4） RISC-V addressing mode summary
对于RISC-V的不同汇编指令进⾏研究可以发现，RISC-V有四种寻址求值⽅式，分别为
直接去⽴即数作为操作数，例如移位指令取寄存器的值作为操作数，例如指令函数从内存中获得的类型计算地址为
RISC-V机器语⾔的格式有6种：
R-type -- add,sub,sll,or,and,...lr.d,sc.d等
I-type -- 取指指令，addi，slli等
S-type -- 存储指令
SB-type -- 条件执⾏语句
U-type -- lui加载语句
UJ-type -- jal 语句
5、Parallelism and instructions: Synchronization
由于存在data race情况，因此我们需要同步机制，synchronization mechanisms。通常可以采⽤lock和unlock⽤于实现只有⼀个processor可运⾏的区域，叫做mutual exclusion，互斥机制。
对于同步机制，典型操作就是原⼦操作，atomic operation。原⼦操作的含义是多线程中操作不会被线程调度机打断操作，操作⼀旦开始就会⼀直运⾏到结束，中间不会换到另⼀个线程。
有⼀种典型的原⼦操作命令就是lr.d和sc.d(load-rerved doubleword和store-rerved doubleword)，这两者命令若lr.d的内存在sc.d ⼯作之前被修改，那么sc.d会失败且不向内存中写值。⽽sc.d不仅在内存中存储值，若成功将某个寄存器值改为0，否则为⾮0值。 // 0表⽰可以访问和修改，1表⽰已有程序在使⽤
sc.d 涉及三种寄存器，分别是hold the address，whether the atomic operation failed or succeed，value to be stored in memory if it is succeed.
例如有程序：
again:
lr.d x10,(x20) //将x20值放⼊x10中
sc.d x11,x23,(x20) //将x23值放⼊x20中，并将成功与否返回x11中
bne x11,x0,again //判断存储是否成功
addi x23,x10,0 //若成功，将x10的值放⼊x23中。
//从⽽实现x20和x23的swap
6、Translating and Starting a Program
这样⼀个过程实际就是C语⾔在外存中(disk/flash memory)中存储，转为⼀个可以在计算机上跑的程序。
转换过程分为4步，以C语⾔为例，对于⼀个C program⽽⾔，先通过Compiler将⾼级语⾔(x.c⽂件)转为Asmbly language
program(x.s⽂件)，再通过Asmbler转为o⽂件，o⽂件和library库⼀起通过Linker转为可执⾏⽂件(x.exe⽂件)。可执⾏⽂件再通过Loader加载到内存中去。
（1）Asmbler转换成的结果为o⽂件，o⽂件中包括object file header，⽤于描述object file的其他⽂件的⼤⼩和位置，text gment 中包含机器码，static data gment中包含程序中所⽤到的数据，relocation information写⼊的是当程序加载⼊memory时指令与数据的地址，symbol table中包含⼀些外界参量的未被定义的label，⽽debugging information中⽤于描述C与机器码之间的编译情况。
（2） 通过Linker实现了⼀个可执⾏⽂件，这样⼀个可执⾏⽂件的主要⼯作是为代码和数据分配真实的内存地址。将多个object⽂件连接在⼀起。
（3） Loader将可执⾏⽂件从外部的disk通过操作系统读⼊内存，并开始使⽤。
（4）其中，library的链接可以分为静态和动态，静态容易导致disk-level waste，⽽动态易导致memory-level waste。关于动态链接库，Dynamically Linked Libraries（DLLs），第⼀次library routines被调⽤的时候，需要经过branches to the dynamic
孟优
linker/loader，⽽当动态加载器/连接器被找到后，那么就需要重新布局，改变某些地址。当routine被找到后，就回到原来的地点。⽽再次调⽤的时候，就会被直接调⽤。
（5） 对java⽽⾔，这样的过程有所不同，java的⽬的是可以安全的在任何电脑上运⾏，因此java的编译与C不同，java直接编译成⼀种解释语⾔，称为java bytecode，通常这⼀步没有任何优化。通过解释器，将java bytecodes与java library routines链接在⼀起，通过解释器获得machine codes，这种软件解释器，称为Java virtual machine(JVM)，可以执⾏Java bytecode。
所谓的解释器，interpreter，就是仿真指令集的程序，其中，interpreter的⼀部分是可携带的，但是因为使⽤解释器导致没有使⽤loader 和linker快。⼀般java程序会⽐C程序慢10倍左右。
因此，java有另⼀种实时解释器，称为JIT，Just In Time Compiler。
7、A C Sort Example to Put it all together
水仙花公主
这部分再次强调了C语⾔转为汇编的过程，且有，程序的运⾏时间是唯⼀可以正确衡量表现性能的指标，⽽像CPI（clocks per instruction）这种单位指令所需要的时钟周期的标准都会因为在不同指令集下程序规模不同，且每⼀个指令所需要的时钟周期不同⽽导致衡量的不准确。
8、Arrays versus Pointer
可以说指针是C语⾔中⼀个⾮常关键的内容，因为指针可以加快程序的运⾏，⽽数组和它相⽐，在数据规模较⼤的时候速度降低不⽌⼏个量级。对于指针⽽⾔，其中存放的是某⼀个变量的地址，*p_a = &a，对指针的调⽤可以是 ：/ *p_a，相当于取到了a的值，⽽实际上，指针可以指向数组，在学习C语⾔的时候，指针数组和数组指针也是两个⾮常容易混淆的概念。个⼈在使⽤的时候其实⾮常不喜欢使⽤数组指针。
因为数组指针的定义是这样的，int (*p_a)[20]，在使⽤(/ *p_a)[0]..就是表⽰数组中的值，⾮常别扭。因此我在对数组进⾏操作的时候还是会使⽤普通指针。
如果从汇编语⾔的⾓度来看，实际上，使⽤指针可以减少对于数组地址的求解，从⽽减少循环中的计算过程，提⾼效率。详细的过程略。
按照书中所说，现在很多编译器可以代替我们完成指针的优化。
9、Advanced Material : Compiling C and Interpreting Java
补充⼀个知识：Java这种属于object-oriented language。⽽⾮以actions/data vs logic。
（1）⾸先要了解C的编译器的⼀般组成：
⼀个编译器通常有四步组成。
第⼀步为The front end，通常也分为四个部分，scanning（对程序中的字符进⾏扫描，区分
names，rerved，words，operators，punctuation symbols，number等等），parsing（⽤于建⽴abstract syntax tree语义抽象树），mantic analysis（语义分析，可以⽤于检查type等等，⽤于形成symbol table），generation of the intermedia reprentation，最后⽣成⼀个中间表达）。中间表达和汇编语⾔已经⾮常相似，但是其默认可以使⽤⽆限的寄存器和资源。
实际上，在第⼀步之后，后⾯的操作与语⾔本⾝⽆关。
第⼆步为High-level optimizations，通常这⼀步进⾏loop-unrolling的优化。
第三步为Local and Global Optimizations，包含common subexpression elimination，constant propogation，copy propogation，dead store elimination 和 strength reduction。
其中，common subexpression elimination这样的步骤中会减少某些不必要的寄存器使⽤，例如x[i] = x[i]+4，⽬标地址的x[i]就不需要再次计算。
global code optimization，有两种⾮常重要的分别是 code motion 和 induction variable elimination，code motion就是将循环中某些⼀直重复的值从循环中提出来，从⽽使循环变得简洁，⽽ induction variable elimination 则是减少数组寻址⽅式，增加指针寻址。
具体关于local 和global的优化是如何实现的我就没有仔细看。七年级上册古诗
第四步中，code generator⼀般进⾏寄存器分配事项。
10、Fallacy and pitfalls：
既然可以写汇编语⾔以获得⾼效表达，那么我们为什么不使⽤汇编语⾔呢？
作者谈到，软件⼯程的公理之⼀就是if you write more lines, coding takes longer。且汇编语⾔难以debugging。
11、Arithmetic for Computers：
