乌龙茶馆

指令(MIPS-32)(working)

计算机语言中的基本单词就是指令。

各种语言的指令集能体现出一定的相似性，因为所有计算机都是基于基本原理相似的硬件技术所构建的。计算机设计者致力于找到一种语言，既能方便硬件和编译器的设计，使性能达到最佳，又使成本和功耗最低。计组读了很久，沿着书中的习惯，详细的了解该指令集。

冯诺依曼体系结构

五大功能部件

• 输入设备
• 输出设备
• 运算器
• 控制器
• 存储器：存储数据结构，下标从0开始的一维数组(抽象)

MIPS-32指令集概况

• 32个寄存器，大小为32位。
• 2^30个存储器字，32位为一组。
• 字节编址，故需要遵照对齐限制(数据地址与存储器的自然边界对齐的需求)。
• 采用大端编址

单位与约定

• 字：计算机中的基本访问单位，通常32位为一组，在MIPS体系结构中与寄存器大小相同。
• 变量对应的寄存器：$s0, $s1…
• 编译时的临时寄存器：$t0, $t1…
• $zero恒置为0，简化指令集。

  助记符

  add，sub，addi，lw，sw，sll，srl，and，andi，or，ori，nor，beq，bne，j，slt，slti

设计三原则

• 原则1：简单源于规整
• 原则2：越小越快
• 原则3：适宜的折中方案

指令的表示

指令在计算机内部是以若干或低或高的电信号序列表示的，形式上与数的表示相同。指令的布局形式叫作指令格式，MIPS指令占32位，与数据字的位数相等。

为了与汇编语言形成区分，我们把指令的数字形式称为机器语言，指令序列为机器码。

为了避免读写冗长的二进制字串，又由于几乎所有计算机的数据大小都是4的整数倍，因此流行用十六进制表示。

由于字段的限制，故设计者选择一条折中的限制，即保证所有指令长度相同，但不同类型的指令采用不同的指令格式。即

• R型：用于寄存器。
• I型：用于立即数。

R型的字段表示(算术指令格式)

op	rs	rt	rd	shamt	funct
6位	5位	5位	5位	5位	6位

取字指令的常数被限制在32以内。

I型的字段表示(数据传送指令格式)

op	rs	rt	constant or address
6位	5位	5位	16位

16位的地址字段允许取字指令取相对于基址寄存器地址偏移32768个字节范围内的任何数据字。

MIPS中各字段名称及含义如下：

• op：指令的基本操作，通常称为操作码。
• rs：第一个源操作数寄存器。
• rt：第二个源操作数寄存器。若是取数，则会用于指明接收取数结果的目的寄存器。
• rd：用于存放操作结果的目的寄存器。
• shamt：位移量，不使用该字段可置为0。
• funct：功能码，用于指明op字敦中操作的特定变式。

MIPS指令编码

指令	格式	op	rs	rt	rd	shamt	funct	address
add	R	0	reg	reg	reg	0	32	no applicable
sub	R	0	reg	reg	reg	0	34	no applicable
addi	I	8	reg	reg	no applicable	no applicable	no applicable	常数
lw	I	35	reg	reg	no applicable	no applicable	no applicable	address
sw	I	43	reg	reg	no applicable	no applicable	no applicable	address

因为几乎所有的指令都要用到寄存器，故必须有一套约定来将寄存器的名字映射为数字。如下表：

寄存器名称	映射到的数字
$t0	8
$t1	9
$t2	10
$t3	11
$t4	12
$t5	13
$t6	14
$t7	15
$s0	16
$s1	17
$s2	18
$s3	19
$s4	20
$s5	21
$s6	22
$s7	23

eg：将下列汇编语言翻译为机器语言

lw $t0, 1200($t1)
add $t0, $s2, $t0
sw $t0, 1200($t1)

先用十进制表示机器语言指令：

lw $t0, 1200($t1)

op	rs	rt	constant or address
35	9	8	1200

add $t0, $s2, $t0

op	rs	rt	rd	shamt	funct
0	18	8	8	0	32

sw $t0, 1200($t1)

op	rs	rt	constant or address
43	9	8	1200

再换算为二进制即可。

算术操作

算术运算指令

MIPS算术运算指令很严格，操作数必须来自寄存器

add & sub

add a, b, c # a = b + c

如上的语句表达两个变量b和c相加，并将结果放置于变量a中。每条MIPS指令只执行一个操作，有且只有3个变量。如果想完成四个变量的相加就需要三条语句才能办到。减法同理，如下：

sub a, b, c # a = b - c

算术常数的运算指令addi

程序经常会在某个操作用到常数，例如将数组下标加1以指向下一个元素。若要使用常数，则需要将其从存储器中取出，效率会减慢。因此我们可以使用一个操作数是常数的算术操作指令，即加立即数(add immediate)，写成addi。

addi $s3, $s3, 4  # $s3 = $s3 + 4

由于MIPS支持负常数，故不需要设置减立即数的指令。

数据传送指令

处理器仅将少量数据存入寄存器中，而算术操作指令仅对寄存器进行操作，故为读取存储器的数据，就必须包含在存储器和寄存器之间传送数据的指令。

数据传送指令中的常量称为偏移量，存放基址的寄存器称为基址寄存器。

• 取数(load)：将数据从存储器复制到寄存器。
• 存数(store)：和取数相对。

为访问存储器的字，指令还要给出存储器的地址。由前可知，MIPS是按照字节编址，字的起始位置必须是4的倍数，故字节寻址也会影响数组的下标，与基址寄存器相加的偏移量必须是下标乘以4。

lw & sw

eg：假设变量h存放在寄存器$s2中，数组A的基址放在$s3中，用MIPS汇编指令编译：A[12] = h + A[8]。

lw $t0, 32($s3) # gets A[8]
add $t0, $s2, $t0 # gets A[8] + h
sw $t0, 48($s3) # store h + A[8] in A[12]

lw和sw是MIPS体系结构中在存储器和寄存器之间复制字的指令，许多程序的变量个数要远多于寄存器的个数。编译器会将最常用的变量保存至寄存器中，若将不常使用的变量存回存储器的过程叫做寄存器溢出。由设计原则2，编译器必须高效利用寄存器。

逻辑操作

逻辑操作产生的目的是用于简化对字中若干位进行打包或者拆包的操作。

C，JAVA和MIPS的逻辑操作见下表：

逻辑操作	C操作符	JAVA操作符	MIPS指令
左移	«	«	sll
右移	»	»>	srl
按位与	&	&	and, andi
按位或	|	|	or, ori
按位取反	-	-	nor

移位

逻辑左移sll：

sll $t2, $s0, 4 # reg $t2 = reg $s0 << 4 bits

机器语言如下：

op	rs	rt	rd	shamt	funct
0	0	16	10	4	0

指令sll的编码在op字段和funct字段都为0，rd为10($t2)，rt为16($s0)，shamt为4，rs字段置为0。

按位与

两个操作位均为1时结果为1。

and $t0, $t1, $t2 # reg $t0 = reg $t1 & reg $t2
# $t2: 0000 0000 0000 0000 0000 1101 1100 0000
# $t1: 0000 0000 0000 0000 0011 1100 0000 0000
则$t0：0000 0000 0000 0000 0000 1100 0000 0000

引出了掩码的概念。

按位或

两个操作位任意为1时结果为1。

or $t0, $t1, $t2 # reg $t0 = reg $t1 | reg $t2
# $t2: 0000 0000 0000 0000 0000 1101 1100 0000
# $t1: 0000 0000 0000 0000 0011 1100 0000 0000
则$t0：0000 0000 0000 0000 0011 1101 1100 0000

按位取反(NOR)

NOT仅有一个操作数，为保持三操作数的格式，引入了或非NOR来替代NOT，等价于：

A NOR 0 = NOT(A OR 0) = NOT(A)

nor $t0, $t1, $t3 # reg $t0 = ~ (reg $t1 | reg $t3)
# $t3 = 0
则$t0：1111 1111 1111 1111 1100 0011 1111 1111

立即数与andi，立即数或ori

在与立即数进行逻辑与操作和逻辑或操作时，立即数的高16位补0后形成32位常数进行计算，而作立即数加法时，需将立即数进行符号扩展。

决策指令

计算机和简单计算器的区别就在于决策能力，根据输入数据和计算过程中产生的值，它可以执行不同的指令。

程序语言通常使用if语句描述决策，有时也是用go to语句和标签。MIPS汇编语言中有两条类似if和go to语句功能的指令。

条件分支指令

该指令会先比较两个值，然后根据比较的结果决定是否从程序中的一个新地址开始执行指令序列。

beq(branch if equal)

beq register1, register2, L1

若两个寄存器数值相等，则转到L1的语句来执行。

bne(branch if not equal)

bne register1, register2, L1

若两个寄存器数值不相等，则转到L1的语句来执行。

eg：将if-then-else语句编译为条件分支指令。在下面这段代码中，f，g，h，i，j都是变量，设该5个变量依次对应于从$s0到$s4的寄存器，求这条C语言if语句编译后形成的MIPS代码。

if (i == j) f = g + h; else f = g - h;

首先验证i和j是否相等，需要一条beq指令。不过通过测试分支的相反条件来跳过if语句后面的then部分，代码效率更高，所以还是用bne指令更好。还要定义一个Else标签。

bne $s3, $s4, Else  # go to Else if i != j

接下来是个单操作，来实现 f = g + h

add $s0, $s1, $s2  # f = g + h(skipped if i != j)

在if语句结尾部分，还要引入另一种分支指令，为无条件分支指令，当执行到该指令后，程序必须分支。MIPS将无条件分支指令命名为jump，简写为j。Exit标签也需要定义。

j Exit  # go to Exit

if语句中else部分的赋值语句也可以编译成一条指令，只需将标签Else加在这条指令前、标签Exit加在该条指令后面，表示if-then-else编译的代码结束。

Else: sub $s0, $s1, $s2  # f = g - h(skipped if i = j)
Exit: 

循环

无论是在二选一的if语句中，还是在迭代计算的循环语句中，决策都起着重要作用。但这两种情况下，关于决策的汇编语言指令是相同的。

eg：编译while循环语句

while (save[i] == k)
      i += 1;

假设i和k存放在寄存器$s3和$s5中，数组save的基址存放在寄存器$s6中。

我们的思路，首先是将save[i]读入进一个临时寄存器中，在读入前需要计算地址，将4*i加到基址后形成访存地址。我们可以采用逻辑左移实现该乘法。

定义一个标签，以便能在循环末端跳回该指令。

Loop: sll $t1, $s3, 2 # Temp reg $t1 = i * 4

为得到save[i]的地址，需要将$t1和$t6中save的基址相加。

add $t1, $t1, $s6 # $t1 = address of save[i]

将该地址存入一个临时寄存器中

lw $t0, 0($t1)

下一条指令进行循环判断，若save[i] != k则退出循环。

bne $t0, $s5, Exit

再下一条指令将i自加。

addi $s3, $s3, 1  # i = i + 1

在循环的末尾，程序跳到循环的开始。随后增加一个Exit标签。

j Loop  # go to Loop
Exit:

基本块是没有分支(可能出现在末尾者除外)并且没有分支目标/分支标签(可能出现在开始者除外)的指令序列

小于则置位(set on less than)

最常见的判断语句可能是相等或不等，但有时判断一个变量是否小于另一个变量也非常有用。例如for循环就需要判断索引变量是否小于0。在MIPS中，使用slt来实现。该指令在比较两个寄存器内容之后，若第一个寄存器小于第二个寄存器，则将第三个寄存器设置为1，否则设置为0.

slt $t0, $s3, $s4 # $t0 = 1 if $s3 < $s4

同样也有立即数版本

slti $t0, $s2, 10 # $t0 = 1 if $s2 < 10

遵循简单的设计原则，MIPS体系并没有提供小于则分支的指令，它会延长时钟周期时间，或增加平均执行每条指令的周期数(CPI)。MIPS编译器使用slt、slti、beq、bne和固定值0($zero)来创建所有的比较条件：相等、不等、小于或等于、大于、大于或等于。

MIPS引入sltu和sltiu指令处理无符号整数。将有符号数作为无符号数进行处理，是一种检查数组下标是否越界的方法，很巧妙。

eg:检查代码仅使用一条sltu指令即可同时进行两种检查：

sltu $t0, $ts1, $t2 # $t0 = 0 if $s1 >= length or $s1 < 0
beq $t0, $zero, IndexOutOfBounds # if bad, goto Error

Switch&Case

实现的最简单的办法就是借助一系列的条件判断，转化为if-then-else的嵌套。更高效的办法就是转移表。

过程

根据提供的参数执行一定任务的存储的子程序。

程序员用过程进行结构化编程。它允许程序员每次只需将将精力集中在任务的一部分，参数承担过程与其他程序，数据之间接口的角色。

过程运行时，程序必须遵循6个步骤

• 将参数放在过程可以访问的位置。
• 将控制转交给过程。
• 获得过程所需的存储资源。
• 执行需要的任务。
• 将结果的值放在调用程序可以访问的位置。
• 将控制返回初始点，因为一个过程可能由一个程序中的多个点调用。

MIPS体系为过程调用分配寄存器时遵循以下规定：

• $a0 ~ $a3：用于传递参数的4个参数寄存器。
• $v0 ~ $v1：用于返回值的两个值寄存器。
• $ra：用于返回起始点的返回地址寄存器。

实现调用操作的时一条过程调用指令：jal，jump-and-link instruction，跳转到某个地址的同时将下一条指令的地址保存在寄存器$ra中。格式如下：

jal ProcedureAddress

指令中链接部分表示指向调用点的地址或链接，以允许过程返回到合适的地址。存储在寄存器$ra(31号寄存器)中的链接部分称为返回地址。返回地址是必须的，因为同一个过程可能会在程序的不同部分调用。

所以，MIPS体系引入寄存器跳转指令jr，jump register。用于case语句，表示无条件跳转到寄存器指定的地址。

jr $ra

调用者与被调用者

调用程序称为调用者，将参数值放在$a0 ~ $a3，然后使用jal X跳转至过程X，即被调用者。被调用者执行运算，将结果存放在$v0 ~ $v1，然后使用jr $ra指令将控制返回给调用者。

程序计数器PC

在存储程序的概念中，使用一个寄存器来保存当前运行的指令地址是绝对必要的。即程序计数器(PC)。jal指令实际上将PC+4保存在寄存器$ra中，从而将链接指向下一条指令，为过程返回做好准备。

若是对于一个过程，编译器需要使用多于4个参数寄存器和两个返回值寄存器。

由于在任务完成后必须消除踪迹，因此调用者使用的任何寄存器都必须恢复到过程调用前所存储的值。

换出寄存器的最理想的数据结构是栈，一种后入先出的队列。栈需要一个指针指向栈中最新分配的地址，以指示下一个过程放置换出寄存器的位置，或是寄存器旧值的存放位置。在每次寄存器进行保存或恢复时，栈指针以字为单位进行调整。MIPS软件为栈指针准备了第29号寄存器，将其命名为$sp。将数据放入栈中称为压栈(push)，从栈中移除数据称为出栈(pop)。

栈增长是按照地址从高到低的顺序进行的。这意味着将数据压栈时，栈指针值减小；而数据出栈时，栈长度缩短，栈指针增大。

eg：编译一个不含调用的C程序

int lef_example(int g, int h, int i, int j)
{
      int f;

      f = (g + h) - (i + j);
      return f;
}

编译后的MIPS代码及过程如下：

参数变量g，h，i和j对应参数寄存器$a0、$a1、$a2和$a3，f对应$s0。编译后的程序是以如下标号开始的过程：

leaf_example:

下一步是保存过程中使用的寄存器。使用两个临时寄存器，因此需要保存三个寄存器：$s0、$t0和$t1。我们将旧值压栈，建立三个字节的空间：

addi $sp, $sp, -12  # adjust stack to make room for 3 items
sw $t1, 8($sp)     # save register $t1 for use afterwards
sw $t0, 4($sp)     # save register $t0 for use afterwards
sw $s0, 0($sp)     # save register $s0 for use afterwards

存入 g + h，i + j 和 f：

add $t0, $a0, $a1  # register $t0 contains g + h
add $t1, $a2, $a3  # register $t0 contains g + h
sub $s0, $t0, $t1  # f = $t0 - $ t1, which is (g + h) - (i + j) 

This site is open source. Improve this page.