指令格式及其优化（简单应用）



指令一般由两部分组成：一部分是操作码，另一部分是操作地址码。当操作数地址为隐式时（如堆栈的操作，默认为栈顶），后一部分则不是必须的。根据指令地址码部分中显式指明的地址个数，则可形成零地址、单地址、二地址、三地址及四地址指令。


我们说的确定指令格式主要就是选择指令字中的操作码长度和地址数。指令字的长度有定长和变长两种。


我们着重要讨论的问题是指令格式的优化问题，优化就是以较少的格式，以尽可能短的码长来实现各种指令编码。


指令字包括操作码和地址码，所以对这两部分都采取优化措施。


1、操作码的优化。这要用到霍夫曼压缩的概念。霍夫曼压缩法是一种频率相关的编码方法，即出现频率高的字符编码短，频率低的字符编码长，这样可以缩短平均码长。我们要掌握的是用霍夫曼树实现霍夫曼编码。其方法很简单：

根据所给的各种指令使用频率，把它们从小到大依次排好作为叶结点（相同的频率可任取一个排在前），然后把最小的两个结点值（频率）相加，形成一个新结点，以这个结点的值与其他的叶结点值比较大小，仍旧取最小的两个结点值合并产生新结点，直到最终合并为一个根（通常这个值是1或100）。简单地记为：

从小到大排序，

最小两个合并，

重复上述过程，

只剩一个结束。

编码时，从根结点开始向下，凡左边分支都编为"1"，右边分支都编为"0"（也可取反），则从根结点到叶结点的一条路径上的编码组合就是该指令的霍夫曼编码。（请仔细观察图4.12中的霍夫曼树）注意，霍夫曼树不是唯一的（因为相同的频率可以任取一个在前，且编码时又可任取左1或左0），但所得的平均码长应是一样的。由于霍夫曼编码得到的码长很不规整，所以有时候要采用霍夫曼扩展编码，就是在霍夫曼码的基础上对码长加以限制（取几个确定的长度如2位、4位等），对编码作适当改变。

平均码长应该容易计算吧，这也是要用到的。


2、地址码的优化。上面我们学了操作码的优化，但是一条指令码还包括地址码。两者合理安排才能使指令格式得到优化。示意如下：

由于操作码优化后是变长的编码，如果整条指令是定长的，那么使地址码的宽度应随不同指令变化，以配合操作码形成定长指令；也可以通过改变指令字中的地址数和地址码的长度，以使单地址及多址都可以在一条指令中使用；如果操作码和地址码之外还有空余的码位，则设法用来存放立即操作数或常数。

当今的RISC机指令系统中，全都是用定字长指令格式。