版权所有南京大学计算机科学与技术系许畅等2022春季版 5.目标代码生成 本章实验为实验四，是最后一次实验，其任务是在词法分析、语法分析、语义分析和中间 代码生成程序的基础上，将C一源代码翻译为MPS32指令序列（可以包含伪指令），并在 SPIM Simulator.上运行。当你完成实验四之后，你就拥有了一个自己独立编写、可以实际运行 的编译器。 选择MIPS作为目标体系结构是因为它属于RISC范畴，与x86等体系结构相比形式简单便 于我们处理。如果你对于MPS体系结构或汇编语言不熟悉并不要紧，我们会提供详细的参考 资料。 需要注意的是，由于本次实验的代码会与之前实验中你已经写好的代码进行对接，因此保 持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重 要。 5.1 实验内容 5.1.1实验要求 为了完成实验四，我们建议你下载并安装SPIM Simulator)用于对生成的目标代码进行检查 和调试，SPIM Simulator的官方下载地址为：http://pages.cs.wisc.edu/~larus/spim.html。这 是由原Wisconsin-Madison的Jame Larus教授（现在在微软）领导编写的一个功能强大的 MIPS32汇编语言的汇编器和模拟器，其最新的图形界面版本QtSPIM由于使用了Qt组件因而 可以在各大操作系统平台如Windows、Linux、Mac等上运行，推荐安装。我们会在后面介绍 有关SPIM Simulator的使用方法。 你需要做的就是将实验三中得到的中间代码经过与具体体系结构相关的指令选择、寄存器 选择以及栈管理之后，转换为MPS32汇编代码。我们要求你的程序能输出正确的汇编代码。 “正确”是指该汇编代码在SPIM Simulator（命令行或Qt版本均可)上运行结果正确。因 此，以下几个方面不属于检查范围： 1)寄存器的使用与指派可以不必遵循MIPS32的约定。只要不影响在SPIM Simulator中的 正常运行，你可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该 存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。 2)栈的管理（包括栈帧中的内容及存放顺序）也不必遵循MPS32的约定。你甚至可以使 用栈以外的方式对过程调用间各种数据的传递进行管理，前提是你输出的目标代码（即 93
版权所有 南京大学计算机科学与技术系 许畅等 2022春季版 93 5. 目标代码生成 本章实验为实验四，是最后一次实验，其任务是在词法分析、语法分析、语义分析和中间 代码生成程序的基础上，将C−−源代码翻译为MIPS32指令序列（可以包含伪指令），并在 SPIM Simulator上运行。当你完成实验四之后，你就拥有了一个自己独立编写、可以实际运行 的编译器。 选择MIPS作为目标体系结构是因为它属于RISC范畴，与x86等体系结构相比形式简单便 于我们处理。如果你对于MIPS体系结构或汇编语言不熟悉并不要紧，我们会提供详细的参考 资料。 需要注意的是，由于本次实验的代码会与之前实验中你已经写好的代码进行对接，因此保 持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重 要。 5.1 实验内容 5.1.1 实验要求 为了完成实验四，我们建议你下载并安装SPIM Simulator用于对生成的目标代码进行检查 和调试，SPIM Simulator的官方下载地址为：http://pages.cs.wisc.edu/~larus/spim.html。这 是由原Wisconsin-Madison的Jame Larus教授（现在在微软）领导编写的一个功能强大的 MIPS32汇编语言的汇编器和模拟器，其最新的图形界面版本QtSPIM由于使用了Qt组件因而 可以在各大操作系统平台如Windows、Linux、Mac等上运行，推荐安装。我们会在后面介绍 有关SPIM Simulator的使用方法。 你需要做的就是将实验三中得到的中间代码经过与具体体系结构相关的指令选择、寄存器 选择以及栈管理之后，转换为MIPS32汇编代码。我们要求你的程序能输出正确的汇编代码。 “正确”是指该汇编代码在SPIM Simulator（命令行或Qt版本均可）上运行结果正确。因 此，以下几个方面不属于检查范围： 1) 寄存器的使用与指派可以不必遵循MIPS32的约定。只要不影响在SPIM Simulator中的 正常运行，你可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该 存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。 2) 栈的管理（包括栈帧中的内容及存放顺序）也不必遵循MIPS32的约定。你甚至可以使 用栈以外的方式对过程调用间各种数据的传递进行管理，前提是你输出的目标代码（即
版权所有南京大学计算机科学与技术系许畅等2022春季版 MIPS32汇编代码)能运行正确。 当然，不检查并不代表不重要。我们建议你试着去遵守MPS32中的各种约定，否则你的 程序生成的目标代码在SPIM Simulator中运行时可能会出现一些意想不到的错误。 另外，实验四对作为输入的C-一源代码有如下的假设： 1)假设1：输入文件中不包含任何词法、语法或语义错误（函数也必有return语句）。 2)假设2：不会出现注释、八进制或十六进制整型常数、浮点型常数或者变量。 3)假设3：整型常数都在16bts位的整数范围内，也就是说你不必考虑如果某个整型常数 无法在addi等包含立即数的指令中表示时该怎么办。 4)假设4：不会出现类型为结构体或高维数组（高于1维的数组）的变量。 5)假设5：设有全局变量的使用，并且所有变量均不重名，变量的存储空间都放到该变量 所在的函数的活动记录中。 6)假设6：任何函数参数都只能是简单变量，也就是说数组和结构体不会作为参数传入某 个函数中。 7)假设7：函数不会返回结构体或数组类型的值。 8)假设8：函数只会进行一次定义（没有函数声明）。 在进行实验四之前，请阅读后面的实验指导部分，以确保你已经了解MPS32汇编语言以 及SPIM Simulator的使用方法，这些内容是你顺利完成实验四的前提。 5.1.2输入格式 你的程序的输入是一个包含C-一源代码的文本文件，你的程序需要能够接收一个输入文件 名和一个输出文件名作为参数。例如，假设你的程序名为cc、输入文件名为test1.cmm、输出 文件名为out1.s,程序和输入文件都位于当前目录下，那么在Liux命令行下运行./cc test1.cmm out1.s即可将输出结果写入当前目录下名为out1.s的文件中。 5.1.3输出格式 实验四要求你的程序将运行结果输出到文件。对于每个输入文件，你的程序应当输出相应 的MPS32汇编代码。我们将使用SPIM Simulator对你输出的汇编代码的正确性进行测试，任 何能被SPIM Simulator执行并且结果正确的输出都将被接受。 5.1.4测试环境 你的程序将在如下环境中被编译并运行（同实验一）： 94
版权所有 南京大学计算机科学与技术系 许畅等 2022春季版 94 MIPS32汇编代码）能运行正确。 当然，不检查并不代表不重要。我们建议你试着去遵守MIPS32中的各种约定，否则你的 程序生成的目标代码在SPIM Simulator中运行时可能会出现一些意想不到的错误。 另外，实验四对作为输入的C−−源代码有如下的假设： 1) 假设1：输入文件中不包含任何词法、语法或语义错误（函数也必有return语句）。 2) 假设2：不会出现注释、八进制或十六进制整型常数、浮点型常数或者变量。 3) 假设3：整型常数都在16bits位的整数范围内，也就是说你不必考虑如果某个整型常数 无法在addi等包含立即数的指令中表示时该怎么办。 4) 假设4：不会出现类型为结构体或高维数组（高于1维的数组）的变量。 5) 假设5：没有全局变量的使用，并且所有变量均不重名，变量的存储空间都放到该变量 所在的函数的活动记录中。 6) 假设6：任何函数参数都只能是简单变量，也就是说数组和结构体不会作为参数传入某 个函数中。 7) 假设7：函数不会返回结构体或数组类型的值。 8) 假设8：函数只会进行一次定义（没有函数声明）。 在进行实验四之前，请阅读后面的实验指导部分，以确保你已经了解MIPS32汇编语言以 及SPIM Simulator的使用方法，这些内容是你顺利完成实验四的前提。 5.1.2 输入格式 你的程序的输入是一个包含C−−源代码的文本文件，你的程序需要能够接收一个输入文件 名和一个输出文件名作为参数。例如，假设你的程序名为cc、输入文件名为test1.cmm、输出 文件名为out1.s，程序和输入文件都位于当前目录下，那么在Linux命令行下运行./cc test1.cmm out1.s即可将输出结果写入当前目录下名为out1.s的文件中。 5.1.3 输出格式 实验四要求你的程序将运行结果输出到文件。对于每个输入文件，你的程序应当输出相应 的MIPS32汇编代码。我们将使用SPIM Simulator对你输出的汇编代码的正确性进行测试，任 何能被SPIM Simulator执行并且结果正确的输出都将被接受。 5.1.4 测试环境 你的程序将在如下环境中被编译并运行（同实验一）：
版权所有南京大学计算机科学与技术系许畅等2022春季版 1)GNU Linux Release:Ubuntu 12.04,kernel version 3.2.0-29; 2)GCC version 4.6.3; 3)GNU Flex version 2.5.35; 4)GNU Bison version 2.5; 5)QtSPIM version 9.1.9. 一般而言，只要避免使用过于冷门的特性，使用其它版本的Liux或者GCC等，也基本上 不会出现兼容性方面的问题。注意，实验四的检查过程中不会去安装或尝试引用各类方便编程 的函数库（如gb等），因此请不要在你的程序中使用它们。 5.1.5提交要求 实验四要求提交如下内容（同实验一)： 1)Flex、Bison以及C语言的可被正确编译运行的源程序。 2)一份PDF格式的实验报告，内容包括： )你的程序实现了哪些功能？简要说明如何实现这些功能。清晰的说明有助于助教 对你的程序所实现的功能进行合理的测试。 b)你的程序应该如何被编译？可以使用脚本、makefile或逐条输入命令进行编译，请 详细说明应该如何编译你的程序。无法顺利编译将导致助教无法对你的程序所实 现的功能进行任何测试，从而丢失相应的分数。 C)实验报告的长度不得超过三页！所以实验报告中需要重点描述的是你的程序中的 亮点，是你认为最个性化、最具独创性的内容，而相对简单的、任何人都可以做 的内容则可不提或简单地提一下，尤其要避免大段地向报告里贴代码。实验报告 中所出现的最小字号不得小于五号字（或英文11号字）。 5.1.6样例 实验四无选做要求，因此下面只列举必做内容样例。请仔细阅读样例，以加深对实验要求 以及输出格式要求的理解。 样例1： 输入： 1 int main() 2{ 3 int a =0,b=1,i=0,ni n read(); 5 while (i<n) 95
版权所有 南京大学计算机科学与技术系 许畅等 2022春季版 95 1) GNU Linux Release: Ubuntu 12.04, kernel version 3.2.0-29； 2) GCC version 4.6.3； 3) GNU Flex version 2.5.35； 4) GNU Bison version 2.5； 5) QtSPIM version 9.1.9。 一般而言，只要避免使用过于冷门的特性，使用其它版本的Linux或者GCC等，也基本上 不会出现兼容性方面的问题。注意，实验四的检查过程中不会去安装或尝试引用各类方便编程 的函数库（如glib等），因此请不要在你的程序中使用它们。 5.1.5 提交要求 实验四要求提交如下内容（同实验一）： 1) Flex、Bison以及C语言的可被正确编译运行的源程序。 2) 一份PDF格式的实验报告，内容包括： a) 你的程序实现了哪些功能？简要说明如何实现这些功能。清晰的说明有助于助教 对你的程序所实现的功能进行合理的测试。 b) 你的程序应该如何被编译？可以使用脚本、makefile或逐条输入命令进行编译，请 详细说明应该如何编译你的程序。无法顺利编译将导致助教无法对你的程序所实 现的功能进行任何测试，从而丢失相应的分数。 c) 实验报告的长度不得超过三页！所以实验报告中需要重点描述的是你的程序中的 亮点，是你认为最个性化、最具独创性的内容，而相对简单的、任何人都可以做 的内容则可不提或简单地提一下，尤其要避免大段地向报告里贴代码。实验报告 中所出现的最小字号不得小于五号字（或英文11号字）。 5.1.6 样例 实验四无选做要求，因此下面只列举必做内容样例。请仔细阅读样例，以加深对实验要求 以及输出格式要求的理解。 样例1： 输入： 1 int main() 2 { 3 int a = 0, b = 1, i = 0, n; 4 n = read(); 5 while (i < n)
版权所有南京大学计算机科学与技术系许畅等2022春季版 6 { 7 int c a b; 8 write(b); 9 a =b; 10 b=ci 11 i=i+1; 12 13 return 0; 14 } 输出： 该样例程序读入一个整数n,然后计算并输出前n个Fibonacci数的值。将其翻译为一段能 在SPIM Simulator中执行的正确的目标代码可以是这样的： 1 data 2 _prompt:.asciiz "Enter an integer: 3 ret:.asciiz "\n" .globl main 5 .text read: 7 li Sv0,4 8 la Sa0, prompt 9 syscall 10 1i$v0,5 11 syscall 12 jr Sra 13 14 write: 15 1i$v0,1 16 syscall 17 1i$v0,4 18 1a $a0,_ret 19 syscall 20 move $v0,$o 21 jr Sra 22 23 main: 24 11$t5,0 25 1i$t4,1 26 1i$t3,0 27 addi ssp,Ssp,-4 28 sw Sra,0(Ssp) 29 jal read 30 lw sra,0(Ssp) 31 addi ssp,Ssp, 32 move $t1,Svo 33 move $t2,$t1 34 labell: 35 blt $t3,$t2,label2 36 jlabel3 37 label2: 38 add stl,st5,st4 39 move Sa0,$t4 40 addi ssp,Ssp, -4 41 sw Sra,0(Ssp) 42 jal write 43 1w Sra,0(Ssp) 44 addi ssp,Ssp,4 45 move st5,$t4 46 move $t4,St1 47 addi st1,$t3,1 48 move $t3,$tl 49 jlabell 50 label3: 51 move $v0,$0 96
版权所有 南京大学计算机科学与技术系 许畅等 2022春季版 96 6 { 7 int c = a + b; 8 write(b); 9 a = b; 10 b = c; 11 i = i + 1; 12 } 13 return 0; 14 } 输出： 该样例程序读入一个整数n，然后计算并输出前n个Fibonacci数的值。将其翻译为一段能 在SPIM Simulator中执行的正确的目标代码可以是这样的： 1 .data 2 _prompt: .asciiz "Enter an integer:" 3 _ret: .asciiz "\n" 4 .globl main 5 .text 6 read: 7 li $v0, 4 8 la $a0, _prompt 9 syscall 10 li $v0, 5 11 syscall 12 jr $ra 13 14 write: 15 li $v0, 1 16 syscall 17 li $v0, 4 18 la $a0, _ret 19 syscall 20 move $v0, $0 21 jr $ra 22 23 main: 24 li $t5, 0 25 li $t4, 1 26 li $t3, 0 27 addi $sp, $sp, -4 28 sw $ra, 0($sp) 29 jal read 30 lw $ra, 0($sp) 31 addi $sp, $sp, 4 32 move $t1, $v0 33 move $t2, $t1 34 label1: 35 blt $t3, $t2, label2 36 j label3 37 label2: 38 add $t1, $t5, $t4 39 move $a0, $t4 40 addi $sp, $sp, -4 41 sw $ra, 0($sp) 42 jal write 43 lw $ra, 0($sp) 44 addi $sp, $sp, 4 45 move $t5, $t4 46 move $t4, $t1 47 addi $t1, $t3, 1 48 move $t3, $t1 49 j label1 50 label3: 51 move $v0, $0
版权所有南京大学计算机科学与技术系许畅等2022春季版 SPIM Version 8.0 of January 8,2010 Copyright 1990-2010,James R.Larus All Rights Reserved. See the file README for a full copyright notice. Loaded:/usr/lib/spim/exceptions.s Enter an integer:7 2 358 13 图15.样例1汇编代码的运行结果。 52 jr Sra 该汇编代码在命令行SPIM Simulator中的运行结果如图15所示（输入7，则输出前7个 Fibonacci数)。 样例2： 输入： 1 int fact(int n) 2{ 3 if(n==1) 4 return n; else 6 return (n fact(n 1)); 8 9 int main() 10{ 11 int m,result; 12 m read(); 13 if (m >1) 14 result fact(m); 15 else 16 result 1; 17 write(result); 18 return 0; 19 输出： 该样例程序读入一个整数n,然后计算并输出nl的值。将其翻译为一段能在SPIM Simula- tor中执行的正确的目标代码可以是这样的： 1.data 2 prompt:.asciiz "Enter an integer:" 3 ret:.asciiz "\n" 4 .globl main 5 .text read: 7 1i$v0,4 8 la $a0,prompt 9 syscall 10 1i$v0,5 11 syscall 12 jr Sra 13 97
版权所有 南京大学计算机科学与技术系 许畅等 2022春季版 97 52 jr $ra 该汇编代码在命令行SPIM Simulator中的运行结果如图15所示（输入7，则输出前7个 Fibonacci数）。 样例2： 输入： 1 int fact(int n) 2 { 3 if (n == 1) 4 return n; 5 else 6 return (n * fact(n - 1)); 7 } 8 9 int main() 10 { 11 int m, result; 12 m = read(); 13 if (m > 1) 14 result = fact(m); 15 else 16 result = 1; 17 write(result); 18 return 0; 19 } 输出： 该样例程序读入一个整数n，然后计算并输出n!的值。将其翻译为一段能在SPIM Simulator中执行的正确的目标代码可以是这样的： 1 .data 2 _prompt: .asciiz "Enter an integer:" 3 _ret: .asciiz "\n" 4 .globl main 5 .text 6 read: 7 li $v0, 4 8 la $a0, _prompt 9 syscall 10 li $v0, 5 11 syscall 12 jr $ra 13 图15. 样例1汇编代码的运行结果
版权所有南京大学计算机科学与技术系许畅等2022春季版 Console Enter an integer:7 5040 图16.样例2汇编代码的运行结果。 14 write: 15 1i$v0,1 16 syscall 17 1i$v0,4 18 1a$a0, _ret 19 syscall 20 move $v0,$0 2 jr Sra main: 2 addi ssp,Ssp,-4 sw Sra,0(Ssp) 26 jal read lw sra,0(Ssp) 28 addi ssp,Ssp,4 2 move $t1,Sv0 0 11$t3,1 3 bgt stl,st3,label6 2 jlabel7 33 label6: 3 move $a0,$t1 35 addi $sp,Ssp,-4 36 sw$ra,0(Ssp)】 37 jal fact 38 1w Sra,0(Ssp) 39 addi ssp,ssp,4 4 move $t2, $v0 41 jlabel8 label7: 3 1i$t2,1 44 label8: 45 move Sa0,$t2 46 addi ssp,Ssp,-4 47 sw Sra,0(Ssp) 48 jal write 49 1w Sra,0(Ssp) 50 addi ssp,Ssp,4 51 move $v0,S0 52 jr Sra 53 54 fact: 55 1i$t4,1 56 beg Sa0,$t4,labell 57 ilabel2 58 labell: 59 move $v0,Sa0 60 jr Sra 61 label2: 62 addi ssp,Ssp,-8 sw Sa0,(Ssp) 64 sw$ra,4(ssp)】 65 sub Sa0,Sa0,1 66 ial fact 67 1w$a0,($sp) 68 lw sra,4(Ssp) 69 addi ssp,Ssp,8 70 mul $v0,$vo,Sa0 71 ir Sra 98
版权所有 南京大学计算机科学与技术系 许畅等 2022春季版 98 14 write: 15 li $v0, 1 16 syscall 17 li $v0, 4 18 la $a0, _ret 19 syscall 20 move $v0, $0 21 jr $ra 22 23 main: 24 addi $sp, $sp, -4 25 sw $ra, 0($sp) 26 jal read 27 lw $ra, 0($sp) 28 addi $sp, $sp, 4 29 move $t1, $v0 30 li $t3, 1 31 bgt $t1, $t3, label6 32 j label7 33 label6: 34 move $a0, $t1 35 addi $sp, $sp, -4 36 sw $ra, 0($sp) 37 jal fact 38 lw $ra, 0($sp) 39 addi $sp, $sp, 4 40 move $t2, $v0 41 j label8 42 label7: 43 li $t2, 1 44 label8: 45 move $a0, $t2 46 addi $sp, $sp, -4 47 sw $ra, 0($sp) 48 jal write 49 lw $ra, 0($sp) 50 addi $sp, $sp, 4 51 move $v0, $0 52 jr $ra 53 54 fact: 55 li $t4, 1 56 beq $a0, $t4, label1 57 j label2 58 label1: 59 move $v0, $a0 60 jr $ra 61 label2: 62 addi $sp, $sp, -8 63 sw $a0, ($sp) 64 sw $ra, 4($sp) 65 sub $a0, $a0, 1 66 jal fact 67 lw $a0, ($sp) 68 lw $ra, 4($sp) 69 addi $sp, $sp, 8 70 mul $v0, $v0, $a0 71 jr $ra 图16. 样例2汇编代码的运行结果
版权所有南京大学计算机科学与技术系许畅等2022春季版 该汇编程序在QtSPIM中的运行结果如图16所示（输入7，输出5040)。 除了上面给的两个样例以外，你的程序要能够将其它符合假设的C一源代码翻译为目标代 码，我们将通过检查目标代码是否能在SPIM Simulator.上运行并得到正确结果来判断你的程序 的正确性。 99
版权所有 南京大学计算机科学与技术系 许畅等 2022春季版 99 该汇编程序在QtSPIM中的运行结果如图16所示（输入7，输出5040）。 除了上面给的两个样例以外，你的程序要能够将其它符合假设的C−−源代码翻译为目标代 码，我们将通过检查目标代码是否能在SPIM Simulator上运行并得到正确结果来判断你的程序 的正确性
版权所有南京大学计算机科学与技术系许畅等2022春季版 File Simulator Registers Text Segment Data Segment Window Help 心边日d口得，口日 F伊R9 n碱风e[I句 Data Text int Regs [16] 国Tex User Text3ment1o0400oo01,.【0440000】 I90400900】8fa40090154,9t523) 183:Iw sa0 0(sspl arge 等就t口器 =3000ff10 040000c 0004100 112.54.3 16:0a02 00e202 00000 [nain] 188888 or152,50,10 1:1w010 yCa11 192:yca1yca10ext Kerne1Text5 egnent【s00000001,【80o1o009J Ert明 9归a0a2 ut we need to use thea 4c240204 w54,516(停1) mt026,1 andt 4.94.31 ode Field 0000010 97:andi tao tao Oxif 。1 34020001 05：51y1 1110:11 sv0 4 syacall 4 (print_str) e0001c4 0c019000 2672 800001c81 0024002 1w54,384(1 00001d4 080000a 【00001d8】34010018or11,50,24 116:bne sko 0x18 okpe Bad pe exception aeothat 0x00400024 start at 0x00400000 gmain at 0x00000000 图17.QtSPIM运行界面。 5.2 实验指导 在实验三中，我们已经将输入程序翻译为涉及相当多底层细节的中间代码。这些中间代码 在很大程度上已经可以很容易地翻译成许多RSC的机器代码，不过仍然存在以下问题： 1)中间代码与目标代码之间并不是严格一一对应的。有可能某条中间代码对应多条目标 代码，也有可能多条中间代码对应一条目标代码。 2)中间代码中我们使用了数目不受限的变量和临时变量，但处理器所拥有的寄存器数量 是有限的。RISC机器的一大特点就是运算指令的操作数总是从寄存器中获得。 3)中间代码中我们并没有处理有关函数调用的细节。函数调用在中间代码中被抽象为若 干条ARG语句和一条CALL语句，但在目标机器上一般不会有专门的器件为我们进行参数传 递，我们必须借助于寄存器或栈来完成这一点。 其中，第一个问题被称为指令选择(Instruction Selection)问题，第二个问题被称为寄 存器分配(Register Allocation)问题，第三个问题则需要考虑如何对栈进行管理。在实验四 中我们的主要任务就是编写程序来处理这三个问题。 100
版权所有 南京大学计算机科学与技术系 许畅等 2022春季版 100 5.2 实验指导 在实验三中，我们已经将输入程序翻译为涉及相当多底层细节的中间代码。这些中间代码 在很大程度上已经可以很容易地翻译成许多RISC的机器代码，不过仍然存在以下问题： 1) 中间代码与目标代码之间并不是严格一一对应的。有可能某条中间代码对应多条目标 代码，也有可能多条中间代码对应一条目标代码。 2) 中间代码中我们使用了数目不受限的变量和临时变量，但处理器所拥有的寄存器数量 是有限的。RISC机器的一大特点就是运算指令的操作数总是从寄存器中获得。 3) 中间代码中我们并没有处理有关函数调用的细节。函数调用在中间代码中被抽象为若 干条ARG语句和一条CALL语句，但在目标机器上一般不会有专门的器件为我们进行参数传 递，我们必须借助于寄存器或栈来完成这一点。 其中，第一个问题被称为指令选择（Instruction Selection）问题，第二个问题被称为寄 存器分配（Register Allocation）问题，第三个问题则需要考虑如何对栈进行管理。在实验四 中我们的主要任务就是编写程序来处理这三个问题。 图17. QtSPIM运行界面
版权所有南京大学计算机科学与技术系许畅等2022春季版 Data ser data8gent【100000001,10040o00】静态数据区 100100001 65746e456e612072746e592072656765 E n t e r a n i n t e g e r 100100101 000a003a000000000000000000000000 100100201.【1003ffff】00000000 用户栈 User staek [7ttrE9501..[800000001 17EEFF950] 00000002 00400060 00000003004D00 7EEEE9601 0000000004000f000000005 004000f0 TEFEf9701 00000006 004000￡0 00000007 004000E0 00000008 04000g4 0040001800000001 一00000000 ++·+··”· +++ 7ffff9b0 ffffec3 [7ffff9c0] 7ffffe49 7ffffe3a 7ffffe00 图18.内存中的数据信息。 ⑧Set Run Parameters Address or label to start running program 0x00400000 Command-line arguments to pass to progran OK 图19.运行参数设置对话框。 5.2.1 QtSPIM简易教程 “工欲善其事，必先利其器”，在着手解决前面所说的三个问题之前，让我们先来考察 实验四所要用到的工具SPIM Simulator。. SPIM Simulator有两种版本：命令行版和GUI版，这两个版本功能相似。命令行版使用更 简洁，GUI版使用更直观，你可以根据自己的喜好进行选择。如果选择命令行版，则可以直接 在终端键入sudo apt-.get install spim命令进行安装（注意需要机器已经连接外网），如果选择 GUI版，则需要访问SPIM Simulator的官方地址htp://pages..cs.wisc.edu/-~larus//spim.html来 下载并安装QtSPIM的Liux版本。命令行版的使用很简单，键入 spim-file[汇编代码文件名] 即可运行。其更详细的使用方法可以通过阅读手册man spim进行学习，下面的介绍主要 针对GUI版本。 成功安装并运行QSPM之后，可以看到如图17所示的界面。其中中间面积最大的一片是 代码区，里面显示了许多MPS用户代码和内核代码，而左侧列出了MPS中的各个寄存器以及 这些寄存器中保存的内容。无论是代码还是寄存器内容，都可以通过上面的菜单选项切换二进 制/十进制/什六进制的显示方式。 101
版权所有 南京大学计算机科学与技术系 许畅等 2022春季版 101 5.2.1 QtSPIM简易教程 “工欲善其事，必先利其器”，在着手解决前面所说的三个问题之前，让我们先来考察 实验四所要用到的工具SPIM Simulator。 SPIM Simulator有两种版本：命令行版和GUI版，这两个版本功能相似。命令行版使用更 简洁，GUI版使用更直观，你可以根据自己的喜好进行选择。如果选择命令行版，则可以直接 在终端键入sudo apt-get install spim命令进行安装（注意需要机器已经连接外网），如果选择 GUI版，则需要访问SPIM Simulator的官方地址http://pages.cs.wisc.edu/~larus/spim.html来 下载并安装QtSPIM的Linux版本。命令行版的使用很简单，键入 spim -file [汇编代码文件名] 即可运行。其更详细的使用方法可以通过阅读手册man spim进行学习，下面的介绍主要 针对GUI版本。 成功安装并运行QtSPIM之后，可以看到如图17所示的界面。其中中间面积最大的一片是 代码区，里面显示了许多MIPS用户代码和内核代码，而左侧列出了MIPS中的各个寄存器以及 这些寄存器中保存的内容。无论是代码还是寄存器内容，都可以通过上面的菜单选项切换二进 制/十进制/十六进制的显示方式。 图18. 内存中的数据信息。 图19. 运行参数设置对话框
版权所有南京大学计算机科学与技术系许畅等2022春季版 表7.数据段中常见的storage_.ype。 storage_type 描述 .ascii str 存储str于内存中，但不以null结尾。 .asciiz str 存储str于内存中，并以nul结尾。 .byte bl,b2,bn 连续存储n个字节(8bits位)的值于内存中。 half h1,h2,.hn 连续存储n个半字(16bits位)的值于内存中。 .word wl,w2,.wn 连续存储n个字(32bits位)的值于内存中。 .space n 在当前段分配n个字节的空间。 从图中我们可以看到用户代码区已经存在一部分代码了，该代码的主要作用是布置初始运 行环境并调用名为main的函数。此时由于我们设有载入任何包含main标签的代码，如果我们 运行这段代码，会发现运行到jal main那一行就会出错。现在我们将一段包含main标签以及声 明main标签为全局标签的“globl main”语句的MPS32代码（例如前面样例1的输出）保存 为后缀名为.s或者.asm的文件。单击QtSPIM.工具栏上的按钮来选择我们保存好的文件，此时 就可以看到文件中的代码已经被载入到QtSPIM的代码区，再运行这段代码就能在Console窗 口观察到运行结果了。你也可以使用QtSPIM工具栏上的按钮或按F10快捷键来单步执行该代 码。 使用SPIM Simulator的一个好处就是我们不需要千预内存的分配，它会帮我们自动划分内 存中的代码区、数据区和栈区。SPIM Simulator具体采用大端(Big Endian,即数据从高位字 节到低位字节在内存中按照从低地址到高地址的顺序依次存储)还是小端(Little Endian,即 数据从低位字节到高位字节在内存中按照从低地址到高地址的顺序依次存储)的存储方式取决 于你机器的处理器的存储方式（由于大多数台式机或笔记本都使用了ntel x86体系结构的处理 器，不出意外的话你会发现自己的SPIM Simulator是小端机)。 在代码区上方的选项卡处切换到“Data”选项卡，就可以看到当前内存中的数据信息， 如图18所示。单击菜单栏上的Simulator→Run parameters,在弹出的对话框（如图19所示） 中可以设置程序运行的起始地址以及传给main函数的命令行参数。 5.2.2MIPS32汇编代码书写 SPIM Simulator不仅是一个MIPS32的模拟器，也是一个MPS32的汇编器。想要让SPIM Simulator正常模拟，你首先需要为它准备符合格式的MIPS32汇编代码文本文件。非操作系统 内核的汇编代码文件必须以.s或者.sm作为文件的后缀名。汇编代码由若干代码段和若干数据 段组成，其中代码段以.text开头，数据段以.data开头。汇编代码中的注释以#开头。 102
版权所有 南京大学计算机科学与技术系 许畅等 2022春季版 102 从图中我们可以看到用户代码区已经存在一部分代码了，该代码的主要作用是布置初始运 行环境并调用名为main的函数。此时由于我们没有载入任何包含main标签的代码，如果我们 运行这段代码，会发现运行到jal main那一行就会出错。现在我们将一段包含main标签以及声 明main标签为全局标签的“.globl main”语句的MIPS32代码（例如前面样例1的输出）保存 为后缀名为.s或者.asm的文件。单击QtSPIM工具栏上的按钮来选择我们保存好的文件，此时 就可以看到文件中的代码已经被载入到QtSPIM的代码区，再运行这段代码就能在Console窗 口观察到运行结果了。你也可以使用QtSPIM工具栏上的按钮或按F10快捷键来单步执行该代 码。 使用SPIM Simulator的一个好处就是我们不需要干预内存的分配，它会帮我们自动划分内 存中的代码区、数据区和栈区。SPIM Simulator具体采用大端（Big Endian，即数据从高位字 节到低位字节在内存中按照从低地址到高地址的顺序依次存储）还是小端（Little Endian，即 数据从低位字节到高位字节在内存中按照从低地址到高地址的顺序依次存储）的存储方式取决 于你机器的处理器的存储方式（由于大多数台式机或笔记本都使用了Intel x86体系结构的处理 器，不出意外的话你会发现自己的SPIM Simulator是小端机）。 在代码区上方的选项卡处切换到“Data”选项卡，就可以看到当前内存中的数据信息， 如图18所示。单击菜单栏上的Simulator → Run parameters，在弹出的对话框（如图19所示） 中可以设置程序运行的起始地址以及传给main函数的命令行参数。 5.2.2 MIPS32汇编代码书写 SPIM Simulator不仅是一个MIPS32的模拟器，也是一个MIPS32的汇编器。想要让SPIM Simulator正常模拟，你首先需要为它准备符合格式的MIPS32汇编代码文本文件。非操作系统 内核的汇编代码文件必须以.s或者.asm作为文件的后缀名。汇编代码由若干代码段和若干数据 段组成，其中代码段以.text开头，数据段以.data开头。汇编代码中的注释以#开头。 表7. 数据段中常见的storage_type。 storage_type 描述 .ascii str 存储str于内存中，但不以null结尾。 .asciiz str 存储str于内存中，并以null结尾。 .byte b1, b2, …, bn 连续存储n个字节（8bits位）的值于内存中。 .half h1, h2, …, hn 连续存储n个半字（16bits位）的值于内存中。 .word w1, w2, …, wn 连续存储n个字（32bits位）的值于内存中。 .space n 在当前段分配n个字节的空间