MIPS

汇编语言

为了阅读和理解机器码（CPU所直接处理的是一条条二进制机器码指令），人们发明了汇编语言（低级语言，稍比机器语言高级）——本质上是一种==助记符==（用一些易于理解的符号代表特定含义的机器码，基本上贴着机器码描述，用标签（Label）来替代地址）。

注意：经常会用到的概念：比特（bit）、位、字节（byte）、半字节、字。

一比特就是一位，一字节是八位，半字节是四位，一个字的大小在不同的计算机架构不同，其中32位CPU中一个字为4个字节，16位CPU中一个字为2个字节，即一个字是能一次处理的最大位数。

寄存器

介绍

寄存器是 CPU 的组成部分之一，是一种高速存储器（甚至是 CPU 可以使用的最高速的一种存储器），可以用来暂存指令，数据，地址等。由于寄存器的成本较高，一般的 CPU 中只有数量很有限的寄存器可供使用。

在 MIPS 体系结构中，CPU 对数据的操作均是基于寄存器的。内存中的数据需要先使用读取（load）类指令保存到寄存器才可使用。操作完成的数据也不能直接保存到内存中，需要使用装载（store）类指令保存至内存中。

MIPS 中的 32 个通用寄存器

所谓通用寄存器，代表它没有明确规定的用途，程序员可以随意对他们赋值、取值，同时它们的值也可以直接参与到各种指令之中。然而，虽然冠有通用的头衔，程序员们还是会以一定的规则来使用它们，这是为了便于程序员之间的交流，同时也是为编译器等工具定下了一定的标准。

这 32 个通用寄存器有两种命名方式，一种是按序号命名 $0~$31（注意前面有个美元的符号），一种就是按功能命名，如下表：

registers Name usage
$0 $zero 常量0（可以用来赋值：add $s0, $0, $a0）
$1 $at 保留给汇编器使用的临时变量
$2-$3 $v0-$v1 函数调用返回值
$4-$7 $a0-$a3 函数调用参数
$8-$15 $t0-$t7 临时变量（由调用者保存，否则易丢失）
$16-$23 $s0-$s7 需要保存的变量（被调用者保存）
$24-$25 $t8-$t9 临时变量（由调用者保存，否则易丢失）
$26-$27 $k0-$k1 留给操作系统使用
$28 $gp 全局指针
$29 $sp 堆栈指针
$30 $fp 帧指针
$31 $ra 返回地址

特别说明：

  • $0 一般不能用于赋值，但这不代表你对它赋值就是错的。在实际中，你可以对 $0 进行赋值，但它的值会始终保持为 0。也就是说对 $0 赋值并不违反语法，但没有==实际效果==。

  • $1 保留给汇编器，一般不使用此寄存器(使用该寄存器可能会导致难以发现的 bug，具体原因请在编写 MIPS 汇编时注意扩展指令是如何翻译成普通指令的)

  • 对s寄存器来说，被调用者需要保证寄存器中的值在调用前后不能发生改变——对应在实际操作中，就是若想要编写一个子函数，则在该子函数中使用的所有s寄存器都必须要在函数的开头入栈，在函数结尾出栈，来确保其值在函数被调用前后不发生变化。

  • 对于t寄存器来说则刚好相反，编写的子函数中使用到t寄存器的地方无需做任何保存，可随意使用——因为维护t寄存器是上层函数的任务

  • 上述两条虽可不遵守，但是一种默认的约定，因此在编写涉及到子函数时，要确保一个函数在被调用前后，其中所用的s寄存器的值并不会发生改变。

  • 一个调用者（即父函数）并不能预知其将要调用的子函数（即被调用者）会使用到哪些 t 寄存器，但可能在调用时并不想失去自己正在使用的某个 t 寄存器中的数据。

    在这种情况下，为了维持 t 寄存器中的数据，调用者有两种选择：一是将所有 t 寄存器中的数据移至 s 寄存器，函数调用结束之后再移回来；二是将自己希望保留的 t 寄存器压入栈中，函数调用结束之后再弹回来。

    第一种方法看似简单，但实际上引入了很多潜在的问题，比如：s 寄存器用完了怎么办？怎么确保子函数一定不会破坏 s 寄存器中的数据？在自动生成汇编代码（如编译）的过程中，怎样确定哪些 s 寄存器是可以用来保存 t 寄存器中的数据的？

    因此，采用第二种方法，是一个更优雅，也更规范的做法。在第二种方法里，不再需要去考虑寄存器之间如何倒腾，只需要借助 sp 指针，不停地用栈去存取自己需要的数据就可以了。这减少了程序员的心智负担，规范了函数调用的过程，也方便了编译器的实现。

    总而言之，调用者维护 t 寄存器，被调用者维护 s 寄存器的意义，就在于让代码更易于模块化。在这种约定下，调用者不需要去考虑被调用者的具体细节，被调用者也不需要去考虑自己被调用的方式。这使得 mips 代码可以以函数为单位进行模块化开发。

  • 子程序调用

三个特殊寄存器

  • PC（Program Counter）：它用于存储当前 CPU 正在执行的指令在内存中的地址。需要注意的是，这个寄存器的值不能用常规的指令进行取值和赋值，但这并不意味着不能做到，只是麻烦一些。
  • HI：这个寄存器用于乘除法。它被用来存放每次乘法结果的高 32 位，也被用来存放除法结果的余数。
  • LO：HI 的孪生兄弟。它被用来存放每次乘法结果的低 32 位，也被用来存放除法结果的商。

CP0 寄存器

当我们的 CPU 设计推进到比较深入的阶段时，我们就需要对异常和中断进行处理，届时我们就会使用到 CP0 寄存器。

CP0 是一个系统控制协处理器，而 CP0 寄存器则是该协处理器工作时需要用到的一些寄存器。在我们的实验中，只会用到其中的 4 个寄存器：SR、Cause、EPC 和 PRId。

简单介绍：

  • SR：用于系统控制，决定是否允许异常和中断
  • Cause：记录异常和中断的类型
  • EPC：保存异常或中断发生时的 PC 值，也就是发送异常或中断时 CPU 正在执行的那条指令的地址。当处理完成之后，CPU 会根据这个地址返回到正常程序中继续往下执行。
  • PRId：处理器 ID，用于实现个性的寄存器。

MIPS汇编指令

初识指令

指令，即是由处理器指令集架构（Instruction Set Architecture，可以理解为计算机体系结构中对程序相关的部分所做的定义）定义的处理器的独立操作，这个操作一般是运算、存储、读取等。一个指令在 CPU 中真正的存在形式是高低电平，也可以理解为由 01 序列组成的机器码。但因为机器码人类难以阅读和理解，所以指令一般由汇编语言来表示，也就是我们俗称的汇编指令。从这个角度上来说，汇编指令只是指令的一种表示形式而已，其实质是一样的。

一条指令的功能较为单一，一般不具有复杂的逻辑。例如「将某两个寄存器的值相加并存入另一个寄存器」，或者是「如果某个寄存器的值满足某个条件则跳转至某条指令」。

一小段汇编程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
.data
.text
.global main
main:
addi $t0, $0, 100 # tag
ori $t1, $0, 200
add $t2, $t1, $t2
sub $t3, $t2, $t1
lui $t4, 233
ori $v0, 1
ori $a0, 2333
mthi $t1
ori $a0, 2333
mthi $t1
syscall
nop #tag
loop:
j loop #tag
nop #tag

其中 tag 标记的 addi $t0, $0, 100 就是一条指令，它的含义为“将 $0 寄存器的值加上 100，并将结果存入 $t0 寄存器”。

需要注意的是，虽然其主要由指令构成，但汇编语言并非全部由指令组成。上面的代码中，第 5-16、18-19 行为严格意义上的指令，其余有标签、伪指令等。

指令格式

指令一般由一个指令名作为开头，后跟该指令的操作数，中间由空格或逗号隔开。指令的操作数的个数一般为 ==0-3== 个，每一个指令都有其固定操作数个数。一般来说，指令的格式如下：

指令名 操作数 1, 操作数 2, 操作数 3

不过，也有如下的指令格式，一般用于存取类指令：

指令名 操作数 1, 操作数 3(操作数 2)

所谓操作数，即指令操作所作用的实体，可以是寄存器、立即数或标签，每个指令都有其固定的对操作数形式的要求。而标签最终会由汇编器转换为立即数。

所谓立即数，即==在指令中设定好的常数==，==可以直接参与运算==，一般长度为 16 位二进制。

而标签，用于使程序更简单清晰。标签用于表示一个地址，以供指令来引用。一般用于表示一个数据存取的地址（类似于数组名）、或者一个程序跳转的地址（类似于函数名，或者 C 语言中 goto 的跳转目标）。在 MIPS 汇编中（以及其他大部分汇编语言中），标签用如下的方式写出：

name:

其中的「name」代表这个标签的名称，可以自行取名。

常见的指令格式样例：

1
2
3
4
5
6
7
add $s0, $a0, $a1
addi $s0, $a0, 12
mult $s1, $s2
beq $a1, $a2, -2
blez $s1, -2
jr $ra
j 0x00003014

当然，前面说过，可以使用标签来代替某个地址，因此也可以以如下方式书写：

1
2
beq $a1, $a2, loop
j loop

这里的 loop 就是一个标签，其所代表的是一段代码的起始地址。在进行汇编时，汇编器会自动把标签转换成我们所需要的立即数，这样就不用我们自己去计算这些地址偏移量，简化了编程难度。

注意：在 MARS 中，跳转指令只能使用标签来进行跳转，不能使用立即数！！！

机器码指令

作为一种机器能够理解的机器语言，机器码是CPU最基本的一种操作，一种原子操作，不可被打断。

精简指令集（RISC，Reduced Instruction Set Computing）：所有指令长度相同，包括MIPS和手机上的ARM……

复杂指令集（CISC，Complex Instruction Set Computing）：指令数目多，长度并不一定相同，包括PC段的x86架构。

一段汇编语言可转换为机器码。

如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
.data
.text
.global main
main:
addi $t0, $0, 100
ori $t1, $0, 200
add $t2, $t1, $t2
sub $t3, $t2, $t1
lui $t4, 233
ori $v0, 1
ori $a0, 2333
mthi $t1
syscall
nop
loop:
j loop
nop

转换结果(16进制)：

1
2
3
4
5
6
7
8
9
10
11
12
20080064
340900c8
012a5020
01495822
3c0c00e9
34420001
3484091d
01200011
0000000c
00000000
08000c0a
00000000

机器码指令格式

R型指令

R 型指令的操作数最多，一般用于运算指令。例如 add、sub、sll 等。其格式如下（左侧为高位，右侧为低位）：

op rs rt rd shamt func
6bits 5bits 5bits 5bits 5bits 6bits

R型指令的op等于0，代表R型指令。func与op组合起来决定该条指令的操作（操作符）

rs（Source Register）指定存放第一个操作数的寄存器，rt（Target Register）为存放第二个，rd存放计算结果（Destination Register）

I型指令

16位的立即数。一般用于addi、subi、ori 等与立即数相运算的指令（这里需要注意：在写汇编语言的时候，需要使用负号来标记负数，而不要和机器码一样认为首位的 1 就代表负数），或 beq、bgtz 等比较跳转指令，因为它们要让两个寄存器的值相比并让 PC 偏移 offset 这么多，刚好利用了全部的字段。还有存取指令，例如 sw、lw，它们在使用时需要对地址指定一个偏移值，也会用到立即数字段。

op rs rt offset or immediate
6bits 5bits 5bits 16bits

rs：存储器操作数的基地址，rt：寄存器操作数的地址

对于跳转指令，op：分支指令操作码；rs和rt为要比较的两个寄存器（rs更靠近op）；immediate满足相对寻址的位移量（即转向指令与当前PC间的指令数），由于指令4个字节，则：PC（跳转后） = （PC（跳转前） + 4) + (immediate * 4)

J型指令

常见的为j和jar，它们需要直接跳转至某个地址，而非用当前的PC值+偏移量计算出新的地址，需要位数较多。

op address
6bits 26bits

目标地址：26位，按如下方式计算转向地址：

字对齐，26位扩展成28位（低两位补0)，最高4位：直接取PC的高4位

New PC = { PC（原地址）[31..28], target address, 00 }

注意:

严格来说，并非所有的指令都严格遵守上面三种格式，有的如 eret、syscall 指令一样没有操作数；有的如 jalr 指令一样某些字段被固定为某个值。不过，就大部分指令而言，都可按上面三种格式进行解释，某些字段被固定也可以按照格式来识别为 R、I、J 中的一种，因此这三种格式要着重理解。

解读

  • op：也称 opcode、操作码，用于标识指令的功能。CPU 需要通过这个字段来识别这是一条什么指令。不过，由于 op 只有 6 位，不足以表示所有的 MIPS 指令，因此在 R 型指令中，有 func 字段来辅助它的功能。

  • func: 用于辅助 op 来识别指令。

  • rs、rt、rd： 通用寄存器的代号，并不特指某一寄存器。范围是$0~$31，用机器码表示就是 00000~11111。

  • shamt：移位值，用于移位指令。

  • offset：地址偏移量。

  • immediate：立即数。

  • address：跳转目标地址，用于跳转指令 。

结合《MIPS-C 指令集》(下简称手册)读懂指令

  • **+**：手册中的所有 + 一律将其左右两侧的操作数视为无符号数，再进行相加。
  • **-**：手册中的所有 - 一律将其左右两侧的操作数视为无符号数，再进行相减。
  • 下标：变量的下标代表变量中所取用的位，temp31 即代表 temptemp 变量在二进制表示下的第 31 位。特别的，下标中的.. 可理解为至，temp31..0与 temp[31:0] 是等价的。
  • 上标：某一位二进制数（即 00 或 11 ）的上标代表该数字重复的位数，0^5^ 即代表 5′b00000。
  • **||**：该符号代表拼接操作。temp1∣∣temp2与 {temp1,temp2}等价。
  • sign_extend() ：代表符号扩展，其扩展结果的正负会与被扩展数相同，一般用于有符号数。其扩展方法是，将被扩展数不足的部分用被扩展数的符号位补全。即若被扩展数为正数，则将其高位用 0 补全至相应位数；若为负数，则在高位补 1 至相应位数。
  • zero_extend() ：代表无符号扩展，即倘若被扩展数位数不足，则将其高位补 0 至相应位数。
  • GPR ：即 General Purpose Register （通用寄存器），其后的中括号内为寄存器编号， GPR[rs] 即可表示编号为 rs 的寄存器。
  • memory ：表示内存，当其后跟随中括号时，表示存储在以括号中数值为起始地址的 4 字节内存中的数据。以 memory[Addr] 为例，其表示以 Addr 为首地址的 4 字节内存中存储的数据。

MIPS-C指令集

1.ADD：符号加（R型指令）

格式：add rd, rs, rt

描述：GPR[rd] <—GPR[rs]+GPR[rt]

示例：add $s1, $s2, $s3

不溢出的话，add同addu等价

2.ADDI：符号加立即数（I）

格式：addi rt, rs, immediate

示例：addi $s1, $s2, $s3

不考虑溢出，则addi与addiu等价

3.ADDIU：无符号加立即数（I）

格式：addiu rt, rs, immediate

“无符号”是误导，本意是不考虑溢出

4.ADDU:无符号加（R）

不考虑溢出

5.AND:与（R）

and $s1, $s2, $s3:$s1<—$s2 AND $s3

6.ANDI:与立即数（I）

格式 andi rt, rs, immediate

7.BEQ：相等时转移（I）

格式：beq rs, rt, offset

描述：if (GPR[rs] == GPR[rt]) then 转移

操作：

1
2
3
4
if (GPR[rs] == GPR[rt]) 
PC <- PC + 4 + sign_extend(offset||0^2) 
else 
PC <- PC + 4

示例：beq $s1, $s2, -2

8.BGEZ:大于等于0时转移（类I）

转移操作同BEQ（传入两个操作数即可）

9.BGTZ：大于0时转移（类I）

转移操作同BEQ（传入两个操作数即可）

10.BLEZ：小于等于0时转移（类I）

转移操作同BEQ（传入两个操作数即可）

11.BLTZ：小于0时转移（类I）

转移操作同BEQ（传入两个操作数即可）

12.BNE：不等于时转移（I）

转移操作同BEQ（传入三个操作数）

13.BREAK：断点

示例：break

描述：产生断点异常

14.DIV：符号除（类R）

格式：div rs, rt

描述：(HI, LO) <- GPR[rs] / GPR[rt]

商存放在LO寄存器，余数存放在HI寄存器

若除数为0则HI/LO结果不可预测

15.DIVU：无符号除

操作：LO<- (0||GPR[rs]) div (0||GPR[rt])

HI<- (0||GPR[rs]) mod (0||GPR[rt])

作为无符号除法，所以先对其0扩展1位后再进行计算

16.ERET：异常返回

格式：eret

描述：eret 将保存在 CP0 的 EPC 寄存器中的现场(被中断指令的下一条地址)写入 PC，从而实现从中断、异常或指令执行错误的处理程序中返回。

操作：PC<-CP0[epc]

当程序被硬件中断、执行 sc 指令、指令执行异常(如除 0)时，PC 将被保存在 EPC 中。

【注意】如果是硬件中断和 SC，EPC 中保存的 PC+4；如果是指令执行异常(如除零、 异常等)，则保存 PC。

17.J:跳转（J）

格式：j target

描述：j 指令是 PC 相关的转移指令。当把 4GB 划分为 16 个 256MB 区域，j 指令可以在当前 PC 所在的 256MB 区域内任意跳转。

操作：PC <- PC31..28||instr_index||0^2^

如果需要跳转范围超出了当前 PC 所在的 256MB 区域内时，可以使用 JR 指令。

26位地址码表示的是64M，但j指令立即数有低位补00的扩展（即应是表示64M条指令，不是64MB），因此应该是表示64M*4=265MB代码大小。

18.JAL:跳转并链接（J）

描述：jal 指令是函数指令，PC 转向被调用函数，同时将当前 PC+4 保存在 GPR[31]也就是$ra中。当把 4GB 划分为 16 个 256MB 区域，jal 指令可以在当前 PC 所在的 256MB 区域内任意跳转。

操作：PC<-PC31..28||instr_index||0^2^

​ GPR[31]<-PC + 4

jal 与 jr 配套使用。jal 用于调用函数（指令转到被调函数处，也就是标签标记处，并且将当前地址值+4存在GPR[31]也就是$ra处），函数中碰到jr后返回指令到GPR[rs] jr指令后跟着的寄存器表示的地址处，通常jr 用于函数返回。当所调用的函数地址超出了当前 PC 所在的 256MB 区域内时，可以使用 jalr指令。

19.JALR:跳转并链接（类R）

格式：jalr rd, rs

描述：jalr指令是函数指令，PC转向被调用函数(函数入口地址保存在GPR[rs]中)，同时将当前 PC+4 保存在 GPR[rd]中。

20.JR：跳转至寄存器

格式：jr rs

操作：PC <- GPR[rs]

jr 与 jal/jalr 配套使用。jal/jalr 用于调用函数，jr 用于函数返回.

jr指令跳转到的是寄存器中的值，有32位，但是没有低位扩展，所以有2^32^=2^2^ * 2^10^ * 2^10^ * 2^10^B=4GB

21.LB:加载字节（I）

格式：lb rt,offset(base)

描述：GPR[rt] <- memory[GPR[base]+offset]

操作：Addr <- GPR[base] + sign_ext(offset)

​ memword <- memory[Addr] （这步要先确保Addr是4的整数倍先对Addr进行字对齐，即最低两位置0，再计算memword）

​ byte <- Addr1..0 （byte的计算仍按原Addr）

​ GPR[rt] <- sign_ext(memword7+8byte..8byte)

示例：lb $v1,3($s0)

22.LBU:加载无符号字符（I)

操作同LB略有不同：

​ Addr <- GPR[base] + sign_ext(offset)

​ memword <- memory[Addr]

​ byte <- Addr1..0

​ GPR[rt] <- zero_ext(memword7+8byte..8byte)

最后一步操作中扩展的是0而不是符号位

23.LH：加载半字（类I）

操作同LB略有不同：

​ Addr <- GPR[base] + sign_ext(offset)

​ memword <- memory[Addr]

​ byte <- Addr1

​ GPR[rt] <- sign_ext(memword15+16byte.16byte)

半字一般为两个字节，16位

约束：Addr 必须是 2 的倍数(即 Addr0 必须为 0)，否则产生地址错误异常

24.LHU：加载无符号半字(I)

操作同LH略有不同：

​ Addr <- GPR[base] + sign_ext(offset)

​ memword <- memory[Addr]

​ byte <- Addr1

​ GPR[rt] <- zero_ext(memword15+16byte.16byte)

25.LUI：立即数加载至高位(I)

格式：lui rt,immediate

操作：GPR[rt] <- immediate||0^16^

26.LW:加载字(I)

操作与LB不同：

Addr<-GPR[base]+sign_ext(offset)

GPR[rt]<-memory[Addr]

约束：Addr必须是4的倍数，否则会产生地址错误异常

27.MFC0：读CP0寄存器（类R）

操作：GPR[rt] <- CP0[rd]

28.MFHI:读HI寄存器

操作：GPR[rt] <- HI

当乘法/除法计算完毕后，需要用 mfhi 读取相应的结果。

29.MFLO：读LO寄存器

用法同MFHI

30.MTC0：写CP0寄存器（类R）

同MFC0操作相反。

31.MTHI：写HI寄存器

与MFHI操作相反

mthi/mtlo 只在进行中断响应是需要使用。此时与 mfhi/mflo 配套使用确保被中断程序的乘除法运算在中断响应结束后能够得到正确结果。

32.MTLO：写LO寄存器

操作同MFLO相反

33.MULT：符号乘

格式：mult rs,rt

描述：(HI, LO)<- GPR[rs]×GPR[rt]，乘积低32位存放在LO寄存器，高32位存放在HI寄存器。所有操作数均为有符号数。

操作：

prod <- GPR[rs]× GPR[rt]

HI <- prod63..32

LO <- prod31..0

34.MULTU:无符号乘

所有操作数为无符号数，操作同MULT略有不同：

prod <- （0||GPR[rs]）×（0||GPR[rt]）

HI <- prod63..32

LO <- prod31..0

35.NOR：或非（R）

操作：nor $s1, $s2, $s3:$s1<—$s2 nor $s3

36.OR:或（R）

操作：or $s1, $s2, $s3:$s1<—$s2 or $s3

37.ORI:或立即数（I）

ori rt, rs, immediate:

GPR[rt] <- GPR[rs] OR zero_extend(immediate)

38.SB:存储字节（类I）

格式： sb rt, offset(base)

描述：memory[GPR[base]+offset] <- GPR[rt]

操作：Addr <- GPR[base] + sign_extend(offset)

​ byte <- Addr1..0

​ memory[Addr]7+8byte..8byte <- GPR[rt]7:0

约束：Addr必须是4的倍数，否则会产生地址错误异常，要先进行字对齐。

39.SH：存储半字节（类I）

操作同SB略有不同：

​ Addr <- GPR[base] + sign_extend(offset)

​ byte <- Addr1

​ memory[Addr]15+16byte..16byte <- GPR[rt]15:0

约束：Addr必须是2的倍数，否则会产生地址错误异常，否则要进行字对齐。这里的Addr要对齐存入时的完整一个字的地址，是对(其所在的字的地址)【表示】的字的【部分字节】的操作，例如memory[Addr]31…16应该是对齐存入时完整字地址，如果Addr=0x1002，存入时的首地址是0x1000，则若是小端存储，写入的应该是0x1003和0x1002；若是大端存储，写入的应该是0x1000和0x1001。因为大小端只涉及内存的解释问题，这包括了读取的解释（怎么把这几个字节组成起来）和写入的解释（怎么把几个字节分布开来），本质上是寄存器值=>（大小端映射）=>内存的多个字节数据=>（大小端映射）=>寄存器值。

40.SLL：逻辑左移（类R)

格式：sll rd, rt, s

描述：GPR[rd] <- GPR[rt] << s

操作: GPR[rd] <- GPR[rt] (31-s)..0||0^s^

sll $0, $0, 0 对应的指令码是 0x0000_0000，也被认为是 NOP(空操作指令)。 该指令有时被用于空循环，有时被编译器用于与体系结构相关的编译优化。

41.SLLV:逻辑可变左移（R）

格式：sllv rd, rt, rs

描述： GPR[rd] <- GPR[rt] << GPR[rs]

操作：s <- GPR[rs]4..0

​ GPR[rd] <- GPR[rt] (31-s)..0||0^s^

GPR[rs]的位31至位5被忽略

42.SLT:小于(最低位)置1（有符号）（R）

格式：slt rd,rs,rt (rs:00000)

描述：GPR[rd] <- (GPR[rs] < GPR[rt])

操作： GPR[rd] <- (GPR[rs] < GPR[rt]) ? 0^31^||1 : 0^32^

43.SLTI:小于立即数置1（有符号）（I）

操作同SLT略有不同：

GPR[rd] <- (GPR[rs] < sign_extend(immediate)) ? 0^31^||1 : 0^32^

44.SLTIU：小于立即数置1（无符号）（I）

操作同SLTI略有不同：

GPR[rd] <- (GPR[rs] < 0||sign_extend(immediate)) ? 0^31^||1 : 0^32^

45.SLTU：小于置1（无符号）（R）

操作同SLT略有不同：

GPR[rd] <- (0||GPR[rs] < 0||GPR[rt]) ? 0^31^||1 : 0^32^

46.SRA：算术右移（类R）

格式：sra rd, rt, s

操作：GPR[rd] <- GPR[rt]31^s^ ||GPR[rt]31..s

47.SRAV：算术可变右移（R）

格式：srav rd, rt, rs

操作：s <- GPR[rs]4..0

GPR[rd] <- GPR[rt]31^s^ ||GPR[rt]31..s

GPR[rs]的位31至5位被忽略

48.SRL:逻辑右移（类R）

操作同SRA略有不同：

GPR[rd] <- 0^s^ ||GPR[rt]31..s

49.SRLV：逻辑可变右移（R）

操作同SRAV略有不同：

s <- GPR[rs]4..0

GPR[rd] <- 0^s^ ||GPR[rt]31..s

50.SUB：符号减（R）

格式：sub rd,rs,rt

操作：

temp <- (GPR[rs]31||GPR[rs]) - (GPR[rt]31||GPR[rt])

if temp32 ≠ temp31 then

SignalException(IntegerOverflow)

else GPR[rd] ← temp31..0

endif

temp32 ≠ temp31 代表计算结果溢出。

如果不考虑溢出，则 sub 与 subu 等价。

51.SUBU:无符号减（R）

GPR[rd] <- GPR[rs] - GPR[rt]

不考虑减法溢出。例如：0x0000_0000 - 0xFFFF_FFFF = 0x0000_0001， 即结果为非负值。

52.SW：存储字（I）

格式：sw rt, offset(base)

描述：memory[GPR[base]+offset] <- GPR[rt]

操作：Addr <- GPR[base] + sign_ext(offset)

memory[Addr] <- GPR[rt]

Addr必须为4的倍数，否则产生地址错误异常

53.SYSCALL：系统调用

描述：产生系统调用异常

操作：SignalException(systemcall)

一般都是为$a0和$v0寄存器赋值

$v0中存储的值 syscall指令执行时的操作
1 输出存储在$a0整型数
2 输出存储在$f12的单精度浮点数
3 输出存储在$f12的双精度浮点数
4 （前提：把要输出的字符串在内存中的首地址赋给$a0寄存器）输出$a0指向的字符串
5 读入整型数至$v0存储器中
6 读入float型浮点数至$f0存储器中
7 读入double型浮点数至$f0存储器中
8 读入指向字符串的指针至$a0中，$a1存储的值代表读入字符的最大个数，不过考虑到字符结尾的”\0”能够读取的字符的最大数量应该是$a1寄存器所存储的值-1
9
10 程序结束
11 输出$a0中存储的字符（存储的是ASCII码）
12 读入字符至$v0存储器
13
14
15
16
17

54.XOR:异或（R）

操作：GPR[rd] <—GPR[rs] XOR GPR[rt]

55.XORI：异或立即数（I）

操作同XOR略有不同：

GPR[rd] <—GPR[rs] XOR zero_extend(immediate)

扩展指令

扩展指令功能主要是简化程序。汇编器将一些常用、但标准指令集不提供的功能封装为一条指令；或者改变现有指令的操作数的形式或个数，使其以新的形式出现。需要注意的是，它们只是形式上是一条新指令，而实际上，在汇编器将其汇编之后，还是使用标准指令来实现的。

最常用到的一条扩展指令是li指令，它用来为某个寄存器赋值，比如 li $a0,100 就是将 100 赋给 $a0 寄存器。汇编器在翻译这条扩展指令时会根据需要，将它翻译成不同的基本指令或基本指令的组合。如下，第一条 li 指令后面的立即数不多于 16 位，因此只被翻译成了一条 addiu；第二条 li 指令后面的立即数多于 16 位，因此被翻译成了 lui+ori 的组合。

li指令

另一条常用的扩展指令是 la 指令，这条指令与 li 指令非常类似，都是为寄存器赋值，只不过是使用标签来为寄存器赋值。经过了前面的学习，大家应该已经知道标签本质上对应一个 32 位地址，但 li 指令并不能直接使用标签来为寄存器赋值，必须要使用 la。比如 la $t0, fibs 这条指令就是把 fibs 这个标签的地址存入$t0 中。

la指令

上面的例子就是利用现有基础指令组合出新的扩展指令。当然，我们也可以对现有指令进行简化或转写，例如前面提到过的 j 0xc0a，我们可以将其立即数改为一个标签，这样汇编器会在进行汇编时，会将标签所代表的立即数计算出来，形成基本指令的形式，例如下图：

转写指令

除了像li这种标准指令集中不存在的指令是扩展指令，一些标准指令集中的指令也可能以扩展指令的形式出现。后者与标准指令不同之处大都在于参数的类型、参数的个数（下例）或**参数的位数（例：ori $a0,$a1,0x12345678)**。

例如: ori $a0, 4

这就是一条扩展指令，汇编器会把它翻译为：ori $a0, $a0, 4

move $a0, $s1指令也是一条扩展指令，是将$s1赋值给$a0

sge $t1, $t2, $t3：$t1 == ($t2 >= $t3) ? 1 : 0

伪指令

伪指令（Directives）是用来指导汇编器如何处理程序的语句，有点类似于其他语言中的预处理命令。伪指令不是指令，它并不会被编译为机器码，但它却能影响其他指令的汇编结果。常用的伪指令有以下几个：

  • .data：用于预先存储数据的伪指令的开始标志。
  • .text：程序代码指令开始的标志。
  • .word：以字为单位存储数据。
  • .asciiz：以字节为单位存储字符串。
  • .space：申请若干个字节的未初始化的内存空间。
  • .ascii: 功能同.asciiz
  • **.byte:**将[label]: .byte x,y,z,h…中的x,y,z,h按8位一个字节存储以4个数字一个字的方式存储在内存地址中

注意

1.使用伪指令初始化数据时，.word、.asciiz等伪指令存储的数据是从.data声明的首地址开始，按照伪指令声明顺序紧密有序的存储。

2..ascii与.asciiz区别是后者会在字符串后补’\0’。这将会导致前者在输出字符串时由于没有后置”\0”，可能会一直输出内存地址上连续的都由.ascii定义的字符串，因为没到”\0”,输出不会停止。（每个内存地址上初始值就为”\0”).

3..asciiz和.ascii存放字符串的时候在内存地址上体现的是一个字符一个地址数，即一个字节，例如

1
2
3
4
5
6
.data 0x00001000
str: .asciiz "hello world"
num: .byte 1,2,3,4,5,6,7,8
.text
li $a0, 0x00001000
lw $t0, 12($a0)

str从0x00001000开始存，又由于小端存储（四个字符为一个字的存，在字中采用小端存储），0x00001000存入l,0x00001001:l,…0x00001008:\0(.asciiz末尾添”\0”),0x00001009:d,0x0000100a:l,0x0000100b:r.

因此num从0x0000100c开始存，由于小端存储，.byte将0x04（8位）存入0x0000100c,0x03:0x0000100d,0x02:0x0000100e,0x01:0x0000100f,0x08:0x00001010,0x07:0x00001011,0x06:0x00001012,0x05:0x00001013。若为num: .byte 1,2,3,4,5,6，则0x00001010和0x00001011均为0即未填入，而其他都没变。

MIPS汇编程序解析

第一个汇编程序

输出”Hello World”

文本代码：

1
2
3
4
5
6
7
8
9
10
.data   //变量的声明和分配从此开始
str: .asciiz    "Hello World"  //代表分配了一定的内存空间，用来存储这个字符串，字符串最后有一个 ’\0’，str 是这个字符串的标签 (label)

.text  //代表程序从此开始
la  $a0, str
li  $v0, 4
syscall

li  $v0, 10
syscall

第5、6、9行是扩展指令，在执行中分别转换成addi $4, $0, 4、addiu $2, $0, 4、addiu $2, $0, 10。

第 7 行和第 10 行的 syscall，会根据当前的 $v0 寄存器的值，进行相应的操作，比如执行第 7 行 syscall 的时候，$v0=4，此时就会输出 $a0 寄存器指向的字符串，执行第 10 行 syscall 的时候，$v0=10，此时程序结束运行。有关 syscall 的说明，可以按快捷键 F1，在 MIPS -> Syscalls 页面中查到相应的用法。

这个 MIPS 汇编程序在运行的时候，先把 str 的地址 (0x0) 赋值给 $a0，然后令 $v0=4，执行syscall，输出 $a0 寄存器指向的字符串 ”Hello World”，直到遇到 ’\0’ 为止，最后令 $v0=10，执行 syscall，结束程序。

简单循环例子

输入n，输出1+……+n的值

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
.text
li  $v0,5
syscall                 # 输入一个整数，输入的数存到 $v0 中
move $s0, $v0           # 赋值，$s0 = $v0,move为扩展指令
li  $s1, 0              # $s1 用于存储累加的值，$s1 = 0
li  $t0, 1              # $t0 是循环变量

loop:
bgt $t0, $s0, loop_end  # 这里用了一个扩展指令 bgt,当 $t0 > $s0 的时候跳转到 loop_end
add $s1, $s1, $t0       # $s1 = $s1 + $t0
addi $t0, $t0, 1        # $t0 = $t0 + 1
j   loop                # 无条件跳转到 loop 标签

loop_end:
move $a0, $s1           # 赋值，$a0 = $s1
li  $v0, 1              # $v0 = 1，在 syscall 中会输出 $a0 的值
syscall         
li  $v0,10              # $v0 = 10
syscall                 # 结束程序
1
2
3
bgt $t0, $s0, loop_end 
《=》slt $1, $16, $8
 // bne $1, $0, 3

在MIPS中使用数组

要求：输入整数n（[2,10]),接下来n行，每行一个整数，输出时先输出The numbers are:，将n个整数按输入顺序输出，两个数字间有空格。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
.data
array: .space 40           # 存储这些数需要用到数组，数组需要使用 10 * 4 = 40 字节
                           # 一个 int 整数需要占用 4 个字节，需要存储 10 个 int 整数
                           # 因此，array[0] 的地址为 0x00，array[1] 的地址为 0x04
                           # array[2] 的地址为 0x08，以此类推。

str:   .asciiz "The numbers are:\n"//类似宏定义，str<=>字符串
space: .asciiz " "//space<=>空格

.text
li $v0,5
syscall                    # 输入一个整数
move $s0, $v0              # $s0 is n
li $t0, 0                  # $t0 循环变量

loop_in:
beq $t0, $s0, loop_in_end  # $t0 == $s0 的时候跳出循环,直接跳去loop_in_end处
li $v0, 5
syscall                    # 输入一个整数
sll $t1, $t0, 2            # $t1 = $t0 << 2，即 $t1 = $t0 * 4
sw $v0, array($t1)         # 把输入的数存入地址为 array + $t1 的内存中
addi $t0, $t0, 1           # $t0 = $t0 + 1
j loop_in                  # 跳转到 loop_in

loop_in_end:
la $a0, str
li $v0, 4
syscall                    # 输出提示信息
li $t0, 0
loop_out:
beq $t0, $s0, loop_out_end
sll $t1, $t0, 2            # $t1 = $t0 << 2，即 $t1 = $t0 * 4
lw $a0, array($t1)         # 把内存中地址为 array + $t1 的数取出到 $a0 中，在array数组中地址也要按四字节一个int来存储
li $v0, 1
syscall                    # 输出 $a0
la $a0, space
li $v0, 4
syscall                    # 输出一个空格
addi $t0, $t0, 1
j loop_out

loop_out_end:
li $v0, 10
syscall                    # 结束程序

在MIPS中使用二维数组

要求输入两个数m和n（[1,8]),代表一个m行n列的矩阵，此后的m*n行每行一个整数，输入矩阵的元素，最后输出该矩阵，每两个数字中一个空格，最后有回车。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
.data
matrix: .space  256             # int matrix[8][8]   8*8*4 字节,一个int型数4个字节
                                # matrix[0][0] 的地址为 0x00，matrix[0][1] 的地址为 0x04，……
                                # matrix[1][0] 的地址为 0x20，matrix[1][1] 的地址为 0x24，……
                                # ……
str_enter:  .asciiz "\n"
str_space:  .asciiz " "

# 这里使用了宏，%i 为存储当前行数的寄存器，%j 为存储当前列数的寄存器
# 把 (%i * 8 + %j) * 4 存入 %ans 寄存器中
.macro  getindex(%ans, %i, %j)
    sll %ans, %i, 3             # %ans = %i * 8
    add %ans, %ans, %j          # %ans = %ans + %j
    sll %ans, %ans, 2           # %ans = %ans * 4
.end_macro

.text
li  $v0, 5
syscall                         #读入
move $s0, $v0                   # 行数
li  $v0, 5
syscall
move $s1, $v0                   # 列数
# 这里使用了循环嵌套
li  $t0, 0                      # $t0 是一个循环变量

in_i:                           # 这是外层循环
beq $t0, $s0, in_i_end
li  $t1, 0                      # $t1 是另一个循环变量
in_j:                           # 这是内层循环
beq $t1, $s1, in_j_end
li  $v0, 5
syscall                         # 注意一下下面几行，在 Execute 页面中 Basic 列变成了什么
getindex($t2, $t0, $t1)         # 这里使用了宏，就不用写那么多行来算 ($t0 * 8 + $t1) * 4 了
sw  $v0, matrix($t2)            # matrix[$t0][$t1] = $v0
addi $t1, $t1, 1
j   in_j
in_j_end:
addi $t0, $t0, 1
j   in_i
in_i_end:
# 这里使用了循环嵌套，和输入的时候同理
li  $t0, 0

out_i:
beq $t0, $s0, out_i_end
li  $t1, 0
out_j:
beq $t1, $s1, out_j_end
getindex($t2, $t0, $t1)
lw  $a0, matrix($t2)            # $a0 = matrix[$t0][$t1]
li  $v0, 1
syscall
la  $a0, str_space
li  $v0, 4
syscall                         # 输出一个空格
addi $t1, $t1, 1
j   out_j
out_j_end:
la  $a0, str_enter
li  $v0, 4
syscall                         # 输出一个回车
addi $t0, $t0, 1
j   out_i

out_i_end:
li  $v0, 10
syscall

求Fibonacci数的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
.data
fibs: .space   48           # "array" of 12 words to contain fib values
size: .word  12             # size of "array",the length of array
space:.asciiz  " "          # space to insert between numbers
head: .asciiz  "The Fibonacci numbers are:\n"

.text
la   $t0, fibs              # load address of array
la   $t5, size              # load address of size variable
lw   $t5, 0($t5)            # load array size
li   $t2, 1                 # 1 is first and second Fib. number
sw   $t2, 0($t0)            # F[0] = 1
sw   $t2, 4($t0)            # F[1] = F[0] = 1
addi $t1, $t5, -2           # Counter for loop, will execute (size-2) times

loop:
lw   $t3, 0($t0)            # Get value from array F[n]
lw   $t4, 4($t0)            # Get value from array F[n+1]
add  $t2, $t3, $t4          # $t2 = F[n] + F[n+1]
sw   $t2, 8($t0)            # Store F[n+2] = F[n] + F[n+1] in array
addi $t0, $t0, 4            # increment address of Fib. number source
addi $t1, $t1, -1           # decrement loop counter
bgtz $t1, loop              # repeat if not finished yet.
la   $a0, fibs              # first argument for print (array)
add  $a1, $zero, $t5        # second argument for print (size)
jal  print                  # call print routine.
li   $v0, 10                # system call for exit
syscall                     # we are out of here.

print:
add  $t0, $zero, $a0        # starting address of array
add  $t1, $zero, $a1        # initialize loop counter to array size
la   $a0, head              # load address of print heading
li   $v0, 4                 # specify Print String service
syscall                     # print heading

out:
lw   $a0, 0($t0)            # load fibonacci number for syscall
li   $v0, 1                 # specify Print Integer service
syscall                     # print fibonacci number
la   $a0, space             # load address of spacer for syscall
li   $v0, 4                 # specify Print String service
syscall                     # output string
addi $t0, $t0, 4            # increment address
addi $t1, $t1, -1           # decrement loop counter
bgtz $t1, out               # repeat if not finished
jr   $ra                    # return

变量声明与定义

1）.data

格式：.data [address]

说明：

  • 定义程序的数据段，初始地址为 address，若无 address 参数，初始地址为设置的默认地址。
  • 需要用伪指令声明的程序变量需要紧跟着该指令。比如该程序中的 fibs, size, space, head 这四个变量。

2）.text

格式：.text [address]

说明：

  • 定义程序的代码段，初始地址为 address，若无 address 参数，初始地址为设置的默认地址。
  • 该指令后面就是程序代码。
  • 在 MARS 中如果前面没有使用 .data 伪指令，可以不使用 .text 直接编写程序代码，代码将放置在前面设置的代码段默认地址中，但如果前面使用了 .data 伪指令，务必在代码段开始前使用 .text 进行标注。

3）.space

格式： [name]: .space [n]

说明：

  • 申请 n 个字节未初始化的内存空间，类似于其他语言中的数组声明。

  • 这段数据的初始地址保存在标签 name 中。

  • name 的地址是由 .data 段的初始地址加上前面所申请的数据大小计算得出的。由于前面申请的空间大小不定，有可能会出现后来申请的空间没有字对齐的情况，从而在使用 sw,lw 一类指令时出现错误，所以在申请空间时尽可能让 n 为 4 的倍数，防止在数据存取过程中出现问题。

4） .word

格式：[name]: .word [data1].[data2] …

说明：

  • 在内存数据段中以字为单位连续存储数据 data1, data2,… (也就是将 datax 写入对应的 1 个字的空间，注意 .word 和 .space 的区别，以及.word和.byte之间的区别)

  • 这段数据的初始地址保存在标签 name 中。计算方式与上面相同。

5）.asciiz

格式：[name]: . asciiz “[content]”

说明：

  • 以字节为单位存储字符串，末尾以 NULL 结尾。
  • 这个字符串在内存数据区的初始地址保存在标签 name 中。
  • 注意 .asciiz 与 .ascii 这两条伪指令的区别。前者在字符串末尾加”\0”，后者不加。
  • .asciiz 由于是按字节存储，可能会导致之后分配的空间首地址无法字对齐的情况发生，请大家自行思考解决方法(感觉可以采用将字符串拆分成若干个符合要求的字符串最后输出时拼接而成即可。

宏的使用

主要是为了简化程序，避免过多的复制粘贴使代码冗长，复用性差，通过宏的使用提高复用性。

不带参数

定义方式如下：

1
2
3
.macro macro_name
# 代码段
.end_macro

例如：定义一个结束程序的宏：

1
2
3
4
.macro done
   li $v0, 10
   syscall
.end_macro
带参数

定义方式如下：

1
2
3
.macro macro_name(%parameter1, %parameter2, ...)#注意：百分号一定不能少
# 代码段
.end_macro

例如：去一个存储在内存地址中的第%i行，第%j列的矩阵的数（设矩阵最大列数为8，则需要通过计算（行数 * 最大列数 + 列数） * 4来在内存地址上取值，因此可以通过宏来封装计算过程，便于复用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
.macro getIndex(%ans, %i, %j)
    sll %ans, %i, 3 #左移三位，相当于乘以8
    add %ans, %j, %ans
    sll %ans, %ans, 2 #左移两位，相当于乘以4
.end_macro

//more pervasive way
.macro calc_addr(%dst, %row, %column, %rank)
    #dts: the register to save the calculated address
    #row: the row that element is in
    #column: the column that element is in
    #rank: the number of columns in the matrix
    mult %row, %rank #get the row distance
    mflo %dst
    add %dst, %dst, %column #get the correct address
    sll %dst, %dst, 2 #get the address in the internal address
.end_macro
.eqv

用法：.eqv EQV_NAME string

类似于C语言中的#define宏定义，汇编器会将EQV_NAME的地方替换成string，可以用来定义一些常量。

或者用来取别名，方便阅读

分配寄存器

代码详见求Fibonacci数的程序的代码段的8-14行

1.la指令用于获取标签所指向的地址，相当于获取数组第一个存储空间的指针，如：la $t0, fibs就是将fibs这个标签对应的地址0x00000000存入了$t0寄存器，方便后续向里面存入Fibonacci数，注意：内存地址一位存一个字节，而存入的Fibonacci数作为int型，需要4个字节，存入后一个数需要向高地址偏移4个地址。

2.la $t5, size和lw $t5, 0($t5)两行使用$t5寄存器保存所需要计算的Fibonacci数的总个数，先用前者将size的地址载入$t5中，再用后者从内存中的$t5所保存的地址（初始时偏移量为0）开始读取一个字即12写入$t5中。

3.li指令可以直接往寄存器中写入一个32位的立即数（扩展后的）。而sw $t2, 0($t0)和sw $t2, 4($t0)是将前两个初始Fibonacci数存入数组中，也就是$t0寄存器中保存地址对应的空间。

循环运算

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
loop:
lw   $t3, 0($t0)      # Get value from array F[n-2]
lw   $t4, 4($t0)      # Get value from array F[n-1]
add  $t2, $t3, $t4    # $t2 = F[n-2] + F[n-1]
sw   $t2, 8($t0)      # Store F[n] = F[n-2] + F[n-1] in array
addi $t0, $t0, 4      # increment address of Fib. number source
addi $t1, $t1, -1     # decrement loop counter
bgtz $t1, loop        # repeat if not finished yet.
la   $a0, fibs        # first argument for print (array)
add  $a1, $zero, $t5  # second argument for print (size)
jal  print            # call print routine.
li   $v0, 10          # system call for exit
syscall               # we are out of here.

前两行从fibs数组中取前两个Fibonacci数F(n-1)和F(n-2)，再根据第三行得到F(n)得到新的Fibonacci数，再通过第四行存入数组中，接下来两行用于修改变量，将$t0移动4个偏移量，换到下一个地址，$t1自减1，代表要求的Fibonacci数减1.第8行的跳转指令，是大于0便跳转，意味着Fibonacci数没求完，循环就不会结束，第十一行的jal print表示跳转到print处开始输出，并将一行的地址保存在$ra寄存器中，方便在函数中jr $ra直接返回到原函数使用处的下一条指令，完成对于函数的调用与返回。

MIPS汇编程序设计

条件语句

代码：(if/else语句)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
.text
li $t1, 100             #t1 = 100
li $t2, 200             #t2 = 200
slt $t3, $t1, $t2       #if(t1 < t2) t3 = 1,slt:表示小于，最低位置1，即若($t1<$t2),$t3=0x00000001;反之，$t3=0x00000000 
beq $t3, $0, if_1_else//the core code,decide that next code go to which line and do what
nop
#do something
j if_1_end              #jump to end
nop
if_1_else:
#do something else

if_1_end:
li $v0, 10
syscall

if/else if/else语句：

可以用类似if/else的语句继续编写一个判断加转移块。

switch语句：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
.data 
array: .space 16
size: .word 4
str1: .asciiz "please enter an Integer"
str2: .asciiz "please enter an Integer between zero and three"

.text
    la $t0, array  #load the address of array
    la $t2, array  #variable point
    la $t1, size   #load the address of array size
    lw $t1, 0($t1) #load array size
    jal input      #go to input
    jal switch     #go to switch
    li $v0, 10
    syscall

input:
    la $a0, str1    #load the address of the string1
    li $v0, 4
    syscall        #print the indication
    li $v0, 5 
    syscall        #read an Integer
    sw $v0, 0($t2) #write the Integer into the $t2
    addi $t1, $t1, -1 #change the number of the input loop
    addi $t2, $t2, 4 #move the address
    bgtz $t1, input #circle the loop if greater than zero 
    jr $ra
    
switch: 
    la $a0, str2   #load the address of the string2
    li $v0, 4
    syscall
    li $v0, 5
    syscall #read the Integer
    sll $t1, $v0, 2  #sll get moved address
    add $t0, $t0, $t1 #get the address
    lw $a0, 0($t0) #write the option number into $a0
    li $v0, 1
    syscall
    jr $ra

可以通过类似的地址偏移的方式实现switch选择

循环语句

for循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
.text
li $t1, 100             #n = 100
li $t2, 0               #i

for_begin1:             #for (int i = 0; i < n; i++)
slt $t3, $t2, $t1       #{
beq $t3, $0, for_end1  
nop      
#do something
addi $t2, $t2, 1        #i++
j for_begin1
nop                     #}  

for_end1:
li $v0, 10
syscall

2、3行初始化，6行判断i<n是否为真，跳转指令，9行作为需在循环体中执行的代码，10行为自增变量，11行闭环循环。

while循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
.data
str: .asciiz "please input an Integer number:"

.text
    la $a0, str
    li $v0, 4
    syscall
    li $v0, 5
    syscall #receive a number into $v0
    move $s0, $v0 #move the number for $v0 to $s0
    li $s1, 0 #$s1serve as the ans that contains the result of the addition
    li $t0, 1 #$t0server as the variate that indicates the current number to be added
    
while:
    bgt $t0, $s0, while_end #when $t0>$s0,the code goes to while_end  
    add $s1, $s1, $t0 
    addi $t0, $t0, 1
    j while #continue the circle
    
while_end:
    move $a0, $s1 #move the final ans to $a0
    li $v0, 1
    syscall #output the ans
    li $v0, 10
    syscall #end the programm

do-while循环无非是在while循环的基础上在循环体外先做一次循环体内的内容罢了。

main函数的定义

1
.global main #前提：需要在Settings中勾选Initialize Program Counter to global 'main' if defined，实质也是定义一个标签

子过程调用关键

跳转指令：jal、jalr、jr（return）

为了便于协作与理解，需要满足一定的协议

栈的理解与使用

前提：

1.过程自身满足栈的结构

2.过程调用子过程时需满足栈的结构

3.子过程执行前后需移动栈指针$sp（分配与释放栈）

在MIPS中一般使用从高地址向低地址延申使用栈，即优先使用高地址，栈是一段内存，其中划分出来的每一个小段称为栈帧，一个栈帧供一个过程使用，最开始，父过程栈帧在较高地址，调用子过程后，子过程栈帧在较低地址区域，子子过程的栈帧在更低地址区域。

对于一个栈帧，大概由以下几个部分由高地址到低地址构成：

临时变量（高地址）（t寄存器以及因寄存器不足而需要保存的变量）
返回地址（保存$ra的地方）
需要保存的寄存器（$s0-$s7若该过程需要使用这些寄存器，那便需要在该过程开始时将其保存在这里，在该过程结束时将其移回寄存器，注意：只需要保存使用的寄存器，不使用的无需保存）
其他参数（无对应寄存器，只能存在栈空间中）
参数0-3（低地址）（指的是该过程调用其他过程，即其子过程时传给其子过程的参数，由对应的寄存器$a0-$a3,之后其子过程可以自行决定是否使用这段栈空间，需要注意的是这四个字只是声明而无需初始化，即这四个字的值可以不定）

栈的使用方法

1.计算好栈帧大小

2.栈指针始终指向栈顶

3.过程开始时分配栈空间（假设此时的栈帧大小为32字节，则需要执行addiu $sp, $sp, -32指令）

4.过程结束时回收栈空间（同上假设，则需要执行addiu $sp, $sp, 32指令）

5.以栈指针为基地址进行栈的存取（sw $t0, 24($sp)

以假设为例：栈空间的分布大致如下：

+16 main.$t0
+12 main.$a3
+8 main.$a2
+4 main.$a1
main.$sp main.$a0
+28 sort.$t2
+24 sort.$t1
+20 sort.$t0
+16 sort.$ra
+12 sort.$a3
+8 sort.$a2
+4 sort.$a1
sort.$sp（低地址） sort.$a0

在这里main作为一种叶子函数，不需要返回值和需要保存的寄存器。

示例：通过选择排序法将数组排序，下为部分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 stack: .space 100 #apply for 100 bytes for the stack
 
 # 在使用过程中，需要先通过下列代码初始化栈指针
 # la $sp, stack
 # addiu $sp, $sp, 100 #依据你所申请的空间大小
 # addiu $sp, $sp, -20 #大小取决于函数使用的总空间大小
 .text
 
 sort: #the entrance of the sorted function
   addiu $sp, $sp, -32
   move $t0, $a0 #the number of the element in the array
   li $t1, 0 #the variate for counting the circle number
   for_4_begin:
     slt $t2, $t1, $t0 
     beq $t2, $zero, for_4_end #when can the circle continues
     nop #think about the delayed branching
     
     la $t2, array #get the address of the head 
     li $t3, 4 
     mult $t1, $t3
     mflo $t3 #get the result of the multiplication
     addu $t2, $t2, $t3 #to avoid changing the value of $t1 
 
     move $a0, $t0
     move $a1, $t1 #move the relevant number into the space in the stack
     
     sw $t2, 28($sp)
     sw $t1, 24($sp)
     sw $t0, 20($sp)
     sw $ra, 16($sp) #according to the graph above, write the value contained in register into the stack
     
     jal findmin #go to the findmin function
     nop
     
     lw $ra, 16($sp)
     lw $t0, 20($sp)
     lw $t1, 24($sp)
     lw $t2, 28($sp) #load the data from the stack to the original place
     
     lw $t3, 0($v0) #get the address of the finded min
     lw $t4, 0($t2) #get the address of the current element
     sw $t3, 0($t2)
     sw $t4, 0($v0) #exchange the value between the current and the min
     
     addi $t1, $t1, 1 #enable the circle
     j for_4_begin #go to the begin of the circle
     nop
   for_4_end:
   addiu $sp, $sp, 32 #remain the status of the stack point
   jr $ra
   nop
   
findmin:
   la $t0, array 
   sll $a0, $a0, 2 #$a0 is the number of the array
   subi $a0, $a0, 4 #get the relative distance 
   addu $t0, $t0, $a0 #get the address of the last element
   
   lw $t1, 0($t0) #set the last element as the minimum value 
   move $t2, $t0 #set the address of the last element as the address of the minimum value
   
   move $t3, $t0 #set $t3 as the variate i
   la $t0, array #reset the $t0 to the head to make the circle
   sll $a1, $a1, 2 #$a1 is the i defined in the bigger circle
   addu $t0, $t0, $a1
   
   for_3_begin:
     sge $t4, $t3, $t0 #judge whether i less than $t0
     beq $t4, $zero, for_3_end
     nop
     
     lw $t5, 0($t3) #get the value of the relative distance of i
     
     slt $t6, $t5, $t1 #judge whether $t5<$t1,put the result into $t6
     beq $t6, $zero, if_1_else
     nop
     
     move $t1, $t5 #update the minimum value
     move $t2, $t3 #update the address of the minimum value
      j if_1_end
      nop
      if_1_else:
      if_1_end:
      subi $t3, $t3, 4 #i-=4
      j for_3_begin
      nop
      
      for_3_end:
        move $v0, $t2 #return the address of the minimum value
        jr $ra
        nop

函数调用

函数特性:
  • 函数是一个代码块，可以由指定语句调用，并且在执行完毕后返回调用语句。
  • 函数通过传参，可以实现代码的复用。
  • 函数只能通过返回值等有限手段对函数外造成影响。
  • 函数里依然可以嵌套调用函数。
代码复用：

为了复用代码，必须让一些特定寄存器作为”接收器“，对于不同的参数，都采用同一组寄存器来存储值，即形参寄存器$a0, $a1, $a2, $a3，同理：对返回值也需要指定特定的寄存器。

例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int sum(int a, int b)
{
    int tmp = a + b;
    return tmp;
}

int main()
{
    int a = 2;
    int b = 3;
    int c = 4;
    int d = 5;

    int sum1 = sum(a, b);
    printf("%d", sum1);
    sum2 = sum(c, d);
    printf("%d", sum2);
    return 0;
}

上述C语言代码可以通过下列汇编代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
.macro end
    li      $v0, 10
    syscall
.end_macro

.macro printStr(%str)
    la      $a0, %str
    li      $v0, 4
    syscall
.end_macro

.data
space: .asciiz " "

.text
li      $s0, 2
li      $s1, 3
li      $s2, 4
li      $s3, 5 #赋初值

move    $a0, $s0 #传参
move    $a1, $s1
jal     sum
move    $s4, $v0 #获得返回值

li      $v0, 1
move    $a0, $s4
syscall #输出整型数

printStr(space)

move    $a0, $s2
move    $a1, $s3
jal     sum
move    $s5, $v0

li      $v0, 1
move    $a0, $s5
syscall

end

sum:
#将参数存入临时寄存器中
move    $t0, $a0
move    $t1, $a1 
#函数过程
add     $v0, $t0, $t1
jr      $ra

$a0, $a1, $a2, $a3只是一种约定，当传递的参数超过4个时，一般将多出的参数存入内存中，在MIPS中使用内存的主要方法是利用栈，通过控制栈指针寄存器$sp完成对内存的访问。

特别注意：实际上栈中未被分配出去内存区域的只有地址低于栈指针寄存器$sp那部分栈，即以栈指针寄存器$sp在自减前的地址为起始位置的子空间已被分配出去了，因此在需要向栈空间存储数据前，需先将栈指针寄存器$sp自减相应大小，再进行存储操作。

避免对外界造成影响：

错误代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
.macro end
    li      $v0, 10
    syscall
.end_macro

.text
li      $s0, 2
li      $s1, 3
li      $t0, 4

move    $a0, $s0 #传参
move    $a1, $s1
jal     sum
move    $s4, $v0 #获得返回值

move    $a0, $s4
move    $a1, $t0
jal     sum
move    $s5, $v0

li      $v0, 1
move    $a0, $s5
syscall

end

sum:
#将参数存入临时寄存器中
move    $t0, $a0 #t0被修改了,换一个不在函数体内使用的寄存器或许也行，但是不是长久之计（
move    $t1, $a1
#函数过程
add     $v0, $t0, $t1
jr      $ra

需要保证函数不会对外部造成影响，方法即为应用栈（作用是保存和恢复函数使用的寄存器，函数应计算返回值，但不应产生其他负面影响）

同样也有两种使用栈的位置：

调用函数前，调用者保存
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
.macro end
    li      $v0, 10
    syscall
.end_macro

.text
li      $s0, 2
li      $s1, 3
li      $t0, 4

move    $a0, $s0 #传参
move    $a1, $s1
addi    $sp, $sp, -4
sw      $t0, 0($sp) #sum函数调用前将$t0存储的值入栈
jal     sum
lw      $t0, 0($sp) 
addi    $sp, $sp, 4 #出栈
move    $s4, $v0 #获得返回值

move    $a0, $s4
move    $a1, $t0
addi    $sp, $sp, -4
sw      $t0, 0($sp) #入栈
jal     sum
lw      $t0, 0($sp)
addi    $sp, $sp, 4 #出栈
move    $s5, $v0

li      $v0, 1
move    $a0, $s5
syscall

end

sum:
#将参数存入临时寄存器中
move    $t0, $a0
move    $t1, $a1
#函数过程
add     $v0, $t0, $t1
jr      $ra
被调用者保存（在sum里出入栈）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
.macro end
    li      $v0, 10
    syscall
.end_macro

.text
li      $s0, 2
li      $s1, 3
li      $t0, 4

move    $a0, $s0 #传参
move    $a1, $s1
jal     sum
move    $s4, $v0 #获得返回值

move    $a0, $s4
move    $a1, $t0
jal     sum
move    $s5, $v0

li      $v0, 1
move    $a0, $s5
syscall

end

sum:
#入栈过程
addi    $sp, $sp, -4
sw      $t0, 0($sp)
#将参数存入临时寄存器中
move    $t0, $a0
move    $t1, $a1
#函数过程
add     $v0, $t0, $t1
#出栈过程
lw      $t0, 0($sp)
addi    $sp, $sp, 4
#return
jr      $ra
嵌套函数调用

由于只有一个$ra寄存器，因此在嵌套函数调用时，&ra会被修改可能会导致死循环的状况出现。将下列C语言代码转换为汇编语言时，若没有充分考虑对于$ra寄存器值得存储，将会出现两块指令来回跳转的死循环情况，因此，一旦一个函数不是叶子函数（不会调用其他函数的函数），就需要保存和恢复$ra（通过栈实现），

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
.macro end
    li $v0, 10
    syscall
.end_macro

.text
li      $s0, 2
li      $s1, 3

move    $a0, $s0
move    $a1, $s1 #传入参数
jal     cal
move    $s5, $v0 #获得返回值

li      $v0, 1
move    $a0, $s5
syscall

end

sum:
#将 $t0 和 $t1 入栈
addi    $sp, $sp, -4
sw      $t0, 0($sp) #存入栈空间中
addi    $sp, $sp, -4
sw      $t1, 0($sp)
#将参数存入临时寄存器中
move    $t0, $a0
move    $t1, $a1
#函数过程
add     $v0, $t0, $t1
#将 $t0 和 $t1 出栈
lw      $t1, 0($sp) 
addi    $sp, $sp, 4
lw      $t0, 0($sp) 
addi    $sp, $sp, 4
#return
jr      $ra

cal:
#将 $ra 入栈
addi    $sp, $sp, -4
sw      $ra, 0($sp)
#将参数存入临时寄存器中
move    $t0, $a0
move    $t1, $a1
#调用 sum 的过程
move    $a0, $t1
move    $a1, $t0
jal     sum
move    $t2, $v0
#运算a-sum(b, a)
sub     $v0, $t0, $t2
#将ra出栈
lw      $ra, 0($sp) 
addi    $sp, $sp, 4
#return
jr      $ra
递归函数调用

递归函数的本质是一个在函数体内调用自身的嵌套函数。

例：阶乘程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>

int factorial(int n)
{
    if(n == 1)
    {
        return 1;
    }
    else
    {
        return n * factorial(n - 1);
    }
}

int main()
{
    printf("%d\n", factorial(5));
    
    return 0;
}

汇编版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#结束程序
.macro end
    li      $v0, 10
    syscall
.end_macro

#读取一个整型数并存储到%des中
.macro getInt(%des)
    li      $v0, 5
    syscall
    move    %des, $v0
.end_macro

#打印%src中存储的整型数
.macro printInt(%src)
    move    $a0, %src
    li      $v0, 1
    syscall
.end_macro

#将%src存储的数值压入栈中
.macro push(%src)
    addi    $sp, $sp, -4
    sw      %src, 0($sp)
.end_macro

#将栈顶数据出栈，并保存在%des寄存器中
.macro pop(%des)
    lw      %des, 0($sp)
    addi    $sp, $sp, 4
.end_macro

.text
main:
    getInt($s0)

    move    $a0, $s0
    jal     factorial
    move    $s1, $v0

    printInt($s1)
    end

factorial:
    # 入栈
    push($ra)
    push($t0)
    # 将参数存入临时寄存器中
    move    $t0, $a0
    # 函数过程
    bne     $t0, 1, else
    # 基准情况
    if:
        li      $v0, 1
        j       if_end  
    # 递归情况  
    else:
        subi    $t1, $t0, 1
        move    $a0, $t1
        jal     factorial
        mult    $t0, $v0
        mflo    $v0
    if_end:
    # 出栈
    pop($t0)
    pop($ra)
    # 返回
    jr      $ra

对每个函数，入口和出口都是十分固定的，即入栈、函数过程、出栈、返回这四个基本流程）。

哈密顿回路思路

实现满足下面功能的汇编程序：

输入一个具有 个顶点的无向图 ，判断 是否有哈密尔顿回路。（哈密顿回路问题，建议使用递归解决）

输入格式

第一行是一个整数 ，代表 有 个顶点，第二行是一个整数 ，代表 有 条边，接下来的 行，每行具有一个整数，设每个奇数行的数为 ,它下一行的数 ，序号为 , 的两个顶点间具有一条边，两个整数之间以回车隔开（点的标号从 1 开始）

输出格式

输出一个整数，若为 0 则代表 不具有哈密尔顿回路，若为 1 则代表 具有哈密尔顿回路。

约定

1、

2、

3、请勿使用 .globl main

4、最大运行指令条数限制为 100000

5、请使用 syscall 结束程序：

1
2
li $v0, 10
syscall

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5
6
1
2
1
3
2
3
2
4
3
5
4
5

输出样例

1
1

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5
6
1
2
1
3
2
3
2
4
1
4
4
5

输出样例

1
0

提交要求

  • 请勿使用 .globl main。
  • 不考虑延迟槽。
  • 只需要提交 .asm 文件。
  • 程序的初始地址设置（Mars->Settings->Memory Configuration）为Compact,Data at Address 0。
提示

哈密顿回路的定义：设 G=(V,E)是一个图，若G中一个回路通过且仅通过每一个顶点一次，则称这个回路为哈密顿回路。

例如，下图中红色的回路就是一个哈密顿回路

哈密顿回路.png

我们希望大家通过这道题目来练习使用汇编语言设计递归程序，因此建议大家使用递归的方式解决，以下是一个参考思路：

采用dfs（深度优先搜索），从一个点开始，搜索与之相邻且未经过的点，直到找到一条哈密顿回路。

参考C语言代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
int G[8][8];    // 采用邻接矩阵存储图中的边
int book[8];    // 用于记录每个点是否已经走过
int m, n, ans;

void dfs(int x) {
    book[x] = 1;
    int flag = 1, i;
    // 判断是否经过了所有的点
    for (i = 0; i < n; i++) {
        flag &= book[i];
    }
    // 判断是否形成一条哈密顿回路
    if (flag && G[x][0]) {
        ans = 1;
        return;
    }
    // 搜索与之相邻且未经过的边
    for (i = 0; i < n; i++) {
        if (!book[i] && G[x][i]) {
            dfs(i);
        }
    }
    book[x] = 0;
}

int main() {
    scanf("%d%d", &n, &m);
    int i, x, y;
    for (i = 0; i < m; i++) {
        scanf("%d%d", &x, &y);
        G[x - 1][y - 1] = 1;
        G[y - 1][x - 1] = 1;
    }
    // 从第0个点（编号为1）开始深搜
    dfs(0);
    printf("%d", ans);
    return 0;
}

大致思路就是根据C语言版本改成汇编语言：

注意：

1.勤使用宏定义，提高复用性

2.递归函数在设计时要关注什么在递归调用过程中不能改变，而什么可以，不能改变的变量就压入栈中并在调用结束后按顺序依次出栈，像在本题中递归方法中的第二个循环的i在再次递归调用时是不能改变的，即在新的递归函数被调用前其需要入栈以保存，得调用结束后再重新赋值，ps：递归函数中第一个循环和第二个循环中的i不要用同一个寄存器去存储，容易导致混乱。

3.假如递归传入参数是当前参数的简单变形，在原递归层中参数不能改变（即需要通过入栈的方式将其保存起来），那么传入下一个递归层的参数可以通过一个可以改变的变量在调用下一次递归前都赋一次值，并在递归函数的开头以move指令的方式赋给相应的参数，进而实现递归的正确调用，需要注意的是第一次调用就传入初始参数，相应的可变变量也要赋成相应的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
.data
matrix: .space 256 #int G[8][8],8*8*4=256 bytes
book: .space 32 #int book[8],8*4 = 32 bytes
stack: .space 256 #the size of the stack

#end the program
.macro end
   li $v0, 10
   syscall
.end_macro

#read an Integer into %des
.macro getInt(%des)
   li $v0, 5
   syscall
   move %des, $v0
.end_macro

#print the Integer in %src
.macro printInt(%src)
   li $v0, 1
   move $a0, %src
   syscall
.end_macro

#push the data in %src into the stack
.macro push(%src)
   addi $sp, $sp, -4
   sw %src, 0($sp)
.end_macro

#pop the data at the top of the stack and save it in %des
.macro pop(%des)
   lw %des, 0($sp)
   addi $sp, $sp, 4
.end_macro

#get the index of G[x][y]
.macro getindex(%ans,%x,%y)
   mult %x, $s0
   mflo %ans #%ans = %x * n
   add %ans, %ans, %y #%ans = %ans + %y
   sll %ans, %ans, 2 #%ans = %ans * 4
.end_macro

#get the index of book[x]
.macro getindexofbook(%ans,%x)
   sll %ans, %x, 2
.end_macro

.text
main:
   la $sp, stack #put the $sp in the bottom of the stack
   addiu $sp, $sp, 256 #adjust it into the top of the stack
   getInt($s0) #read the number of the dot -- n into $s0
   getInt($s1) #read the number of the line -- m into $s1
    
   li $t0, 0 #serve as the circle variate i
   jal for_1_begin
   
   li $t0, 0
   li $a0, 0 
   li $s2, 0 #serve as the ans
   li $t3, 0 #serve as the second circle's i
   jal dfs #$a0 serve as x
   
   #print
   printInt($s2)
   addiu $sp, $sp, -256
   end
   
for_1_begin:
   bge $t0, $s1, for_1_end #i>=m then break
        
   getInt($t1)
   getInt($t2) #scanf("%d%d",&x,&y)
   
   addi $t1, $t1, -1
   addi $t2, $t2, -1
   
   getindex($t3,$t1,$t2)
   li $v0, 1
   sw $v0, matrix($t3) #G[x-1][y-1] = 1
   
   li $v0, 1
   getindex($t3,$t2,$t1)
   sw $v0, matrix($t3) #G[y-1][x-1] = 1
   addi $t0, $t0, 1
   j for_1_begin 
  
   for_1_end:
      jr $ra
      
dfs:
   #push
   push($ra)
   push($t0)
   push($t3)
   #move the data the the circle variate into $t0
   move $t0, $a0
   #the body of the function
   getindexofbook($t1,$t0)
   li $v0, 1
   sw $v0, book($t1) #book[x] = 1
   li $t2, 1 #int flag = 1
   li $t9, 0 #serve as the first circle's i
   
   #check if all dots are visited
   for_2_begin:
      bge $t9, $s0, for_2_end #i>=n,then break
      getindexofbook($t4,$t9)
      la $t5, book
      add $t5, $t5, $t4
      lw $t5, 0($t5) #$t4 = book[i]
      and $t2, $t2, $t5 #flag &= book[i]
      addi $t9, $t9, 1 #i++
      j for_2_begin
   for_2_end:
   
   #check whether a hamilton circle is formed
   bne $t2, 1, if_1_end
   getindex($t4,$t0,$0)
   la $t5, matrix #serve as the head of the matrix
   add $t5, $t5, $t4 
   lw $t5, 0($t5)
   bne $t5, 1, if_1_end
   li $s2, 1
   j return
   if_1_end:
   
   #search deeply for the adjacent dot who is unvisited
   li $t3, 0 #i=0
   for_3_begin:
      bge $t3, $s0, for_3_end #i>=n, then break
      getindexofbook($t4,$t3)#the distance the dot relative to the head 
      la $t5, book
      add $t5, $t5, $t4
      lw $t5, 0($t5) #$t5 = book[i]
      getindex($t6,$t0,$t3)
      la $t7, matrix
      add $t7, $t7, $t6
      lw $t7, 0($t7) #$t8 = G[x][i]
      bne $t5, 0, if_2_end
      bne $t7, 1, if_2_end
      move $a0, $t3 #move the i to $a0,then circle again
      jal dfs #dfs(i)
      if_2_end:
      addi $t3, $t3, 1
      j for_3_begin
   for_3_end:
   getindexofbook($t4,$t0)
   li $v0, 0
   sw $v0, book($t4) #book[x] = 0
   #pop
   return:
   pop($t3)
   pop($t0)
   pop($ra)
   #return
   jr $ra
高精度阶乘

题面：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
第一行读取n

计算并输出n的阶乘，输出字符串长度小于等于1000

步数限制为200,000

请使用syscall结束程序：

li $v0, 10
syscall
样例1
给出以下输入：

24
期望的输出为：

620448401733239439360000

由于int型整型数溢出问题，本题不可采用一位一位相乘的方法，因此用C写出如下朴素的利用int型数组将两个数的相乘转化为大数的每一位同小数相乘再进行进位处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
   int i = 2, j;//i=2，从n=2开始计算，n=0和n=1的答案都是1
int length = 0;
array[0] = 1;
for (i; i <= n; i++) {
	for (j = 0; j <= length; j++) {
		array[j] *= i;
	} //大数的每一位都以小数
	for (j = 0; j < length; j++) {
		if (array[j] >= 10) {
			int hold = array[j];
			array[j] %= 10;
			array[j+1] += hold / 10;
		}
	}
	while (array[length] >= 10) {
		int temp = array[length];
		array[length] %= 10;
		array[++length] += temp / 10;
	}//进位处理，
}
if (n == 1) {
	printf("1");
}
else{
	for (i = length; i>=0; i--) {
		printf("%d", array[i]);
	}
}

得到以上代码的汇编版本后却没有通过，个人认为是在进位处理时，后面的进位加到前面导致前面的溢出：

因此考虑令数组的每一位储存大数的更多位数，即：提高进制到1000

得到如下汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# adjust carry-out
.macro adjust(%now)
   getArrayi($t2, %now) #array[%now]
   move $t3, $t2 #hold = array[%now]
   
   li $v0, 1000
   div $t2, $v0
   mfhi $t2 #$t2 %= 1000
   sll $v0, %now, 2
   sw $t2, array($v0) #array[%now] %= 1000
   
   li $v0, 1000
   div $t3, $v0 #hold / 1000
   mflo $t4
   
   addi $t5, %now, 1 #$t5 = i + 1
   getArrayi($t6, $t5) #$t5 = array[i + 1]
   add $t6, $t6, $t4 
   sll $v0, $t5, 2
   sw $t6, array($v0) #array += hold/1000 
.end_macro

#because the higher binary, the leading zero needs to be adjusted when you print,because it wil print 0 while it actually is 000
           bne n, 1, if_else
           if:
             li $v0, 1
             printInt($v0)
           j for_4_end
           if_else:
           move i, length #i = length
           for_4_begin:
             blt i, 0, for_4_end #i<0
             getArrayi($t2, i)
             beq i, length, three_print
             bge $t2, 100, three_print 
             bge $t2, 10, two_print
             bge $t2, 1, one_print
             printInt($t2)
             printInt($t2)
             printInt($t2) #printf("000"); avoid printing the single zero while there actually three zero
             j if_2_end
             
             two_print:
               printInt($0)
               printInt($t2)
               j if_2_end #print one leading zero
               
             one_print:
               printInt($0)
               printInt($0)
               printInt($t2) #print two leading zero
               j if_2_end
               
             three_print:
               printInt($t2) #printf
          
             if_2_end:
             addi i, i, -1 #i--
             j for_4_begin  #
            
           for_4_end:

注意前导零的处理，循环的书写一定要规范。

MARS小工具

MARS的Tool菜单里有个叫做Instruction Counter的工具，点击Connect to MIPS后运行程序可以看见程序跑了多少天实际的指令，可以作为相应题目指令限制的参考。

MIPS程序的内存视图

Text：程序代码段，最大代码长度：256M-4M

Static data：全局变量，$gp寄存器初始地址+-偏移量寻址本段内存

Dynamic data：堆

Stack：栈，自动存储区

image-20241021145023421

MIPS程序的编译、链接和加载

image-20241021155940327

编译

1.转换汇编指令

2.生成符号分配表

3.为全局变量、指令分配内存地址

4.转换成机器指令，保存到目标文件

例：将如下代码转换为汇编代码

1
2
3
4
5
6
7
8
9
10
11
int f, g, y; //globle variables
int main(void) 
{
f=2;
g=3;
y=sum(f,g);
return y;
}
int sum(int a, int b) {
return (a+b);
}

寄存器$4($a0)=f, $5($a1)=g

操作系统会把从main返回的地址提前送$ra

程序区从0x00400000开始

静态数据区从0x10000000开始

全局指针$28($gp)=0x10008000

​ 符号分配表

image-20241021154928555

image-20241021160116312

链接

1.链接其他目标代码文件和库函数文件（多个目标代码文件，链接时需要重新分配指令地址和数据地址）

2.生成一个完整的可执行代码文件

image-20241021160327728

加载

1.可执行代码加载到内存（指令加载到代码段，数据加载到数据段）

2.设置PC、SP、GP

image-20241021160441146

几种典型ISA简介

x86指令架构

8086/8088CPU结构

CISC指令集：数千条指令；变长指令格式；分段式存储管理；物理地址扩展

ARM架构

移动端、嵌入式系统和物联网标准

ARM指令集、Thumb指令

RISC-V架构

完全开源，继承MIPS

image-20241021160938283

RISC与CISC

CISC（复杂指令系统计算机）

设置更多、更复杂指令实现更多的功能，减少运行程序所需的指令数，依靠硬件提升运行速度，实例：x86

SISC（精简指令系统计算机）

减少指令种类、简化指令功能，降低单个指令的执行周期数（CPI）来提高MIPS（单位时间执行百万条指令数），提升运行速度，实例：MIPS、ARM、RISC-V

image-20241021161032483

两者相互学习借鉴。

MIPS处理器设计

CPU功能与组成

功能

取数、存数、传送、运算

组成

数据通路：指令执行过程中，指令数据流经过的部件和路径的总称，指令的执行部件。

设计步骤

MIPS模型机

单周期通路时序控制：

所有操作（组合逻辑）在单个时钟周期内完成；

信号在时钟周期内从状态单元输出经组合逻辑再回到状态单元输入；

状态单元时钟信号上跳沿同步

单周期数据通路设计

取指令（取出PC后维持一个周期后将PC+4重新写入PC寄存器）、读寄存器（根据PC读取的指令、读取相应寄存器操作数）、ALU运算、数据存区、写寄存器。