【逻辑门的奇妙冒险】第7篇 如果有如果：分支指令
本篇目标：
1.设计分支指令格式；
2.设计译码模块；
3.完成对PC的控制，实现分支指令；
4.利用分支指令实现乘法；
5.算法入门：快速幂。
上一篇我们连接了RegFile和ALU，整理了几个输出，设计了输入组合，定义了“指令”，并且设计了一个计数器和复用器的模块，使得指令可以被自动化地执行，诞生了第一个“程序”。接下来我们就要丰富指令的类型，添加分支指令，以支持更丰富的程序。
1.设计分支指令格式
我们首先回顾一下，上一篇中出现的4种指令，有的是寄存器之间的加法，有的是寄存器加立即数的，有的是寄存器之间的减法，最好介绍原地交换两个数的时候，引入了一个寄存器间的异或，整理如下：
我们的机器目前可以识别这些指令，如果把它们按序接入复用器，就可以自动执行这些指令。现在的问题是，执行的永远是线性的，就是从复用器的第一个输入直到最后一个输入。我们想，能不能不那么线性，运行取指令的时候，飘逸一点，跳跃一点。
这就需要设计分支指令了，它的功能是，如果满足分支条件，那么那个计数器就就不在是加一，而是加上我们指定的值，或者减去我们指定的值。因此，很自然的，我们需要指定某些值，所以需要用到IMM，同时我们也需要设计分支的条件，这个一般用的是寄存器之间比较大小。回想起来我们的ALU有三种判断，相等、小于、和大于等于。正好，我们就可以设计借此出三条分支指令：
这个BEQ的意思就是branch if equal，相应的，BLT就是branch if less than，而BGE自然是branch if great or equal。很显然，这里的比大小，就是两个源寄存器之间比了。我们如果这么写：
BEQ x1 x0 -2
意思就是如果x1和x0相等，则下一次计数器减去2。它的二进制码和应该是：
101 1 001 000 111110
好勒，我们的分支指令初步设计完成。
2.设计译码模块；
我们不难注意到，现在的这个机器的连线，开始有点复杂了，我们看：
接下来，分支指令的加入又会变得更加复杂，比如说，分支指令需要两个数去比大小，但是这俩源寄存器号的位置和先前指令的位置不太一样，我们连线的时候就需要多调整一下。进一步地，分支指令并不需要写回RegFile，所以寄存器文件的写回使能wen信号，不能再是常量1了，我们需要根据当前指令是否要写回RegFile而动态地给出正确的wen值。这话一说，我们猛然发现，RegFile的raddr1和radd2还有waddr，也是需要动态给出的。因此，我们有必要整理一下我们的电路。
首先梳理一下，我们的这个电路需要多少控制信号呢？首先是ALU的选择信号、然后是两个源寄存器号、接着是否需要IMM参与运算以及IMM是多少、最后是是否需要写回RegFile和写回寄存器号。我们可以整理出这样一个表：
表中的括号表示指令本身的第几位到第几位。我们现在横过来看，比如说radd2这行的意思就是：
当指令是ADD时，raddr2等于指令的第5位到第3位；
当指令是ADDI时，raddr2是无所谓的；
当指令是SUB和XOR时，raddr2还是指令的第5位到第3位；
当指令是BEQ/BLT/BGE时，raddr2等于指令的第8位到第6位。
其他的行同理可得。由此，我们就可以为这些信号设计电路了，一个最简易的方案是这样的：
既然xxx表示无所谓，那么我们就可以取任意值来简化电路，例如IMM可以全部都是(5,0)，waddr也可以全都都是(11,9)。同时，我们也注意到，此时的S正好等价于指令的高3位（显然是设计指令的时候故意的），imm正好等价于指令的12位（显然也是故意的），因此可以直连，很有效地简化了电路。
这就叫做译码电路，但是现在还有点小问题。这个电路下边的指令分类要怎么得到呢？其实我们可以观察一下我们设计出来的指令：
真巧，每一条指令的高四位都不一样（显然也是故意设计的），我们就可以根据高四位的值来判断当前是什么指令，现在我们把判断逻辑加上去，看看新的译码电路：
OK，现在我们把这个译码电路封装成译码模块，这个一般也叫译码器Decoder：
我们把它安装到之前的处理器电路上，看看效果：
很OK，没毛病~
3.完成对PC的控制，实现分支指令；
接下来我们就要实现分支指令了，这里的关键显然在于控制那个取指令的计数器。其实那个计数器是有名字的，它叫程序计数器，Program Counter，一般简称PC。
我们可以这样做：准备两套PC的更新方式，一个是传统的PC累加一，另一个就是加上IMM了，具体选择哪一个方式更新，取决于当前是否是分支指令且分支条件成立了。PC更新的电路可以这样的：
这里我们把PC扩展成5位了，现在最多有32条指令。同时Decoder模块需要拉出一个是否是分支的判断信号，这个也比较简单，可以是下面这样：
左边是Decoder模块的内部实现，多出了一个输出口，右边是它的外部封装。接下来我们需要把这个东西接回处理器电路，在合适的时候启用不一样的PC更新方式，具体说来就是当前是否是分支指令，并且分支条件是否成立，分支条件就是ALU的输出是不是1：
接下来我们试验一下，写几个分支指令试试我们的电路是否正确执行了，是否真的跳转了？我们的程序可以是这样的：
ADDI x1 x0 31（011 1 001 000 011111）（0x721f）
ADDI x2 x0 21（011 1 010 000 010101）（0x7415）
BGE x1 x2 4（111 0 001 010 000100）（0xe284）
XOR x1 x1 x2（010 0 001 001 010000）（0x4250）
XOR x2 x1 x2（010 0 010 001 010000）（0x4450）
XOR x1 x1 x2（010 0 001 001 010000）（0x4250）
这个程序在交换两个数之前，先判断一下1号寄存器的值是否大于等于2号寄存器的，如果是，那就跳过交换。这是电路是执行情况：
果然跳过去了，没有触发交换。我们不妨再试试往回跳，看看能不能成功，这次程序是这样的：
ADDI x1 x0 31（011 1 001 000 011111）（0x721f）
ADDI x2 x0 21（011 1 010 000 010101）（0x7415）
XOR x1 x1 x2（010 0 001 001 010000）（0x4250）
XOR x2 x1 x2（010 0 010 001 010000）（0x4450）
XOR x1 x1 x2（010 0 001 001 010000）（0x4250）
BLT x1 x2 -3（110 0 001 010 111100）（0xc2bd）
首先加载1号31，2号21，然后交换，最后看一下如果1号寄存器的值小于2号的，那就往回跳三条指令，再交换回来。因此程序最后应该还1号31，2号21。我们试一下：
OK，没问题~
4.利用分支指令实现乘法；
有了分支指令之后，我们的程序就可以丰富一些了，最直观的一个应用就是我们可以做软件乘法了。我们知道7乘以6，可以看做是6个7相加。具体到电路上，一个累加一个计数既可。比如说我们写这样一个程序：
ADDI x7 x0 1（011 1 111 000 000001）（0x7e01）
ADDI x1 x0 6（011 1 001 000 000110）（0x7206）
ADDI x2 x0 7（011 1 010 000 000111）（0x7407）
ADD x3 x3 x2（011 0 011 011 010000）（0x66d0）
SUB x1 x1 x7（100 0 001 001 111000）（0x8278）
BLT x0 x1 -2（110 0 000 001 111110）（0xc07e）
它的功能就是把7乘以6的值放到了3号寄存器，我们试运行一下
没有问题~更进一步地，我们的乘法还可以套娃。毕竟我们的立即数只有6位，放不下很大的数。加载大数可以用乘法来凑。比如说我们想要让一个寄存器的值等于10000，又因为10000等于25乘以25乘以16，我们准备两层循环就可以做到了，代码是这样的：
ADDI x7 x0 1（011 1 111 000 000001）（0x7e01）
ADDI x5 x0 25（011 1 101 000 011001）（0x7a19）
ADDI x1 x0 16（011 1 001 000 010000）（0x7210）
ADDI x2 x0 25（011 1 010 000 011001）（0x7419）
ADD x6 x6 x5（011 0 110 110 101000）（0x6da8）
SUB x2 x2 x7（100 0 010 010 111000）（0x84b8）
BLT x0 x2 -2（110 0 000 010 111110）（0xc0be）
SUB x1 x1 x7（100 0 001 001 111000）（0x8278）
BLT x0 x1 -5（110 0 000 001 111011）（0xc07b）
运行起来是这样的
这里我们还添加了一个时钟计数器，就是计算这个程序运行了多少个时钟周期完成。同时因为运行周期数比较多，软件仿真的时候，需要加快时钟频率，为了操作方便我们添加了一条停机指令HALT，全0编码，一旦遇到这条指令，PC就停止变化，完成停机操作。
5.算法入门：快速幂。
我们注意到，乘法套娃确实可以加载很大的数，但是这个运行周期就有点多了，加载10000至少1000周期以上了，很明显这个方法并不高明。有什么更加漂亮的做法呢？
我们注意到，ADD指令其实可以轻松做到乘以2的操作，如果只要设定一个初值，然后一直自己加自己写回自己，就是一次乘以2的操作了。这样，我们就可以得到连串2的整数次幂，也就是2、4、8、16、32、64、128……进一步地，我们注意到，任何数都可以用2的整数次幂累加而成，比方说10000，它就是8192+1024+512+256+16。所以，加载10000，我们可以这么做：
ADDI x6 x0 16（011 1 110 000 010000）（0x7c10）//16
ADD x1 x0 x6（011 0 001 000 110000）（0x6230）//x1=16
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//32
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//64
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//128
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//256
ADD x2 x0 x6（011 0 010 000 110000）（0x6430）//x1=256
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//512
ADD x3 x0 x6（011 0 011 000 110000）（0x6630）//x3=512
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//1024
ADD x4 x0 x6（011 0 100 000 110000）（0x6830）//x4=512
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//2018
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//4096
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）//8192
ADD x6 x6 x1（011 0 110 110 001000）（0x6d88）
ADD x6 x6 x2（011 0 110 110 010000）（0x6d90）
ADD x6 x6 x3（011 0 110 110 011000）（0x6d98）
ADD x6 x6 x4（011 0 110 110 100000）（0x6da0）
上机器运行一下试试，OK没问题，我们数一下用了多少时钟周期:
只要18周期，这显然是要比乘法套娃要快很多。这个算法就叫做快速幂算法。
再进一步地，这个其实也还不够好，我们其实可以根据10000这个数量身定制一个快速幂。我们知道我们可以现在乘以2了，所以，只要得到了5000，那么一步就可以到10000。那要怎么得到5000呢？只要我们得到2500，那么5000也就有了。那要怎么得到2500呢？只要1250。然后是要625。到了这里625就不是偶数，不好拆了，这里可以扭一下，我们认为625是有600加上25得到的，我们真正需要的是600。继续，那要怎么得到600呢，只要300……以此类推，我们的算法步骤就清晰了，顺着捋一遍就是加50、加25、乘2、乘2、乘2、加25、乘2、乘2、乘2、乘2，代码是这样的：
ADDI x6 x0 50（011 1 110 000 110010）（0x7c32）
ADDI x6 x6 25（011 1 110 110 011001）（0x7d99
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）
ADDI x6 x6 25（011 1 110 110 011001）（0x7d99）
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）
ADD x6 x6 x6（011 0 110 110 110000）（0x6db0）
上机运行，没问题，而且更快了，只要10个周期，甚至占用的空间也更少了:
最后，预告一下，下一篇引入访存指令之后，我们的机器就比较完备了，到时候就可以给大家介绍稍微进阶一点的算法了。
