1、 136 第 5 章 习 题 答 案3 假定某计算机中有一条转移指令，采用相对寻址方式，共占两个字节，第一字节是操作码，第二字节是相对位移量（用补码表示），CPU 每次从内存只能取一个字节。假设执行到某转移指令时 PC 的内容为 200，执行该转移指令后要求转移到 100 开始的一段程序执行，则该转移指令第二字节的内容应该是多少？参考答案：因为执行到该转移指令时 PC 为 200，所以说明该转移指令存放在 200 单元开始的两个字节中。因为 CPU 每次从内存只能取一个字节，所以每次取一个字节后 PC 应该加 1。该转移指令的执行过程为：取 200 单元中的指令操作码并译码PC+1取 201
2、单元的相对位移量PC+1计算转移目标地址。假设该转移指令第二字节为 Offset，则 100=200+2+Offset，即Offset = 100202 = 102 = 10011010B （注：没有说定长指令字，所以不一定是每条指令占 2 个字节。）4 假设地址为 1200H 的内存单元中的内容为 12FCH，地址为 12FCH 的内存单元的内容为38B8H，而 38B8H 单元的内容为 88F9H。说明以下各情况下操作数的有效地址和操作数各是多少？（1）操作数采用变址寻址，变址寄存器的内容为 12，指令中给出的形式地址为 1200H。 （2）操作数采用一次间接寻址，指令中给出的地址码为 1
3、200H。（3） 操作数采用寄存器间接寻址，指令中给出的寄存器编号为 8，8 号寄存器的内容为1200H。参考答案：（1） 有效地址 EA=000CH+1200H=120CH，操作数未知。（2） 有效地址 EA=(1200H)=12FCH，操作数为 38B8H。（3） 有效地址 EA=1200H，操作数为 12FCH。5 通过查资料了解 Intel 80x86 微处理器和 MIPS 处理器中各自提供了哪些加法指令，说明每条加法指令的汇编形式、指令格式和功能，并比较加、减运算指令在这两种指令系统中不同的设计方式，包括不同的溢出处理方式。参考答案（详细信息略）：MIPS:Intel 80x86:
4、137 6 某计算机指令系统采用定长指令字格式，指令字长 16 位，每个操作数的地址码长 6 位。指令分二地址、单地址和零地址三类。若二地址指令有 k2 条，无地址指令有 k0 条，则单地址指令最多有多少条？参考答案：设单地址指令有 k1 条，则 (16 k2) 26 k1) 26 = k0，所以 k1= (16 k2) 26 k0/26 7 某计算机字长 16 位，每次存储器访问宽度 16 位，CPU 中有 8 个 16 位通用寄存器。现为该机设计指令系统，要求指令长度为字长的整数倍，至多支持 64 种不同操作，每个操作数都支持4 种寻址方式：立即（I）、寄存器直接（ R）、寄存器间接（S）
5、和变址（X），存储器地址位数和立即数均为 16 位，任何一个通用寄存器都可作变址寄存器，支持以下 7 种二地址指令格式（R、I、S、X 代表上述四种寻址方式）：RR 型、RI 型、RS 型、RX 型、XI 型、SI 型、SS 型。请设计该指令系统的 7 种指令格式，给出每种格式的指令长度、各字段所占位数和含义，并说明每种格式指令需要几次存储器访问？参考答案：指令格式可以有很多种，只要满足以下的要求即可。操作码字段：6 位；寄存器编号：3 位；直接地址和立即数：16 位；变址寄存器编号：3 位；总位数是 8 的倍数。指令格式例 1：0000 OP (6 位 ) R t (3 位) Rs (3 位
6、)RR 型0010 OP (6 位 ) Rt (3 位) Imm16 (16 位)RI 型0100 OP (6 位 ) R t (3 位) Rs (3 位)RS 型0110 OP (6 位 ) Rt (3 位) Offset16 (16 位)RX 型 Rx (3 位)1000 OP (6 位 ) Rx (3 位) Imm16 (16 位)XI 型1010 OP (6 位 ) R t (3 位) 000SI 型1100 OP (6 位 ) Rt (3 位)SS 型 Rs (3 位)Offset16 (16 位)000000Imm16 (16 位)指令格式例 2： 138 01OP (6 位 )
7、R t (3 位) Rs (3 位)RR 型 01OP (6 位 ) Rt (3 位) Imm16 (16 位)RI 型 000OP (6 位 ) R t (3 位) Rs (3 位)RS 型OP (6 位 ) Offset16 (16 位)RX 型 Rx (3 位)OP (6 位 ) Rx (3 位) Imm16 (16 位)XI 型OP (6 位 ) R t (3 位) 000SI 型OP (6 位 ) Rt (3 位)SS 型 Rs (3 位)Offset16 (16 位)00Imm16 (16 位)011001R t (3 位)01 1111 0000010 0010 10寻址方式字段
8、(2 位)-00：立即；01：寄直；10：寄间； 11-变址8 有些计算机提供了专门的指令，能从 32 位寄存器中抽取其中任意一个位串置于一个寄存器的低位有效位上，并高位补 0，如下图所示。MIPS 指令系统中没有这样的指令，请写出最短的一个 MIPS 指令序列来实现这个功能，要求 i=5, j=22, 操作前后的寄存器分别为$s0 和$s2。31 j i 0(31j)位 (ji)位 (i+1)位31 0(32(ji) )位 (ji)位0 000参考答案：可以先左移 9 位，然后右移 15 位，即：sll $s2, $s0, 9srl $s2, $s2, 15 思考：(1) 第二条用算术右移指
9、令 sra 行不行？不行，因为不能保证高位补 0！(2) 若第一条指令中的$s2 改成其他寄存器 R，则会带来什么问题？所用寄存器 R 的值被破坏！9 以下程序段是某个过程对应的指令序列。入口参数 int a 和 int b 分别置于$a0 和$a1 中，返回参数是该过程的结果，置于$v0 中。要求为以下 MIPS 指令序列加注释，并简单说明该过程的功能。add $t0, $zero, $zeroloop: beq $a1, $zero, finish 139 add $t0, $t0, $a0sub $a1, $a1, 1j loopfinish: addi $t0, $t0, 100add
10、 $v0, $t0, $zero参考答案：1: 将 t0 寄存器置零2: 如果 a1 的值等于零则程序转移到 finish 处3: 将 t0 和 a0 的内容相加，结果存放于 t04: 将 a1 的值减 15: 无条件转移到 loop 处6: 将 t0 的内容加上 100，结果存放于 t07: 将 t0 的值存放在 v0该程序的功能是计算“100+ab”10 下列指令序列用来对两个数组进行处理，并产生结果存放在$v0 中。假定每个数组有 2500 个字，其数组下标为 0 到 2499。两个数组的基地址分别存放在$a0 和$a1 中，数组长度分别存放在$a2 和$a3 中。要求为以下 MIPS
11、指令序列加注释，并简单说明该过程的功能。假定该指令序列运行在一个时钟频率为 2GHz 的处理器上，add、addi 和 sll 指令的 CPI 为 1；lw 和 bne指令的 CPI 为 2，则最坏情况下运行所需时间是多少秒？sll $a2, $a2, 2sll $a3, $a3, 2add $v0, $zero, $zeroadd $t0, $zero, $zeroouter: add $t4, $a0, $t0lw $t4, 0($t4)add $t1, $zero, $zeroinner: add $t3, $a1, $t1lw $t3, 0($t3)bne $t3, $t4, skip
12、addi $v0, $v0, 1skip: addi $t1, $t1, 4bne $t1, $a3, inneraddi $t0, $t0, 4bne $t0, $a2, outer参考答案：1: 将 a2 的内容左移 2 位，即乘 42: 将 a3 的内容左移 2 位，即乘 43: 将 v0 置零4: 将 t0 置零 140 5: 将第一个数组的首地址存放在 t46: 取第一个数组的第一个元素存放在 t47: 将 t1 置零8: 将第二个数组的首地址存放在 t39: 取第二个数组的第一个元素存放在 t310: 如果 t3 和 t4 不相等，则跳转到 skip11: 将 v0 的值加 1，结
13、果存于 v012: 将 t1 的值加 4，结果存于 t113: 如果 t1 不等于 a3，即还未取完数组中所有元素，则转移到 inner14: 将 t0 的值加 415: 如果 t0 不等于 a2，即还未取完数组中所有元素，则转移到 outer该程序的功能是统计两个数组中相同元素的个数。程序最坏的情况是：两个数组所有元素都相等，这样每次循环都不会执行 skip。因此，指令总条数为：5+2500(3+25006+2)=37512505，其中：add,addi 和 sll 的指令条数为：4+2500(2+25003+1)=18757504lw 和 bne 的指令条数为： 1+2500(1+2500
14、3+1)=18755001所以：程序执行的时间为：(2GHzclock 的 clock time=1/2G=0.5ns) (187575041+187550012) 0.5ns = 28133753ns0.028s11 用一条 MIPS 指令或最短的指令序列实现以下 C 语言语句：b=25|a 。假定编译器将 a 和 b 分别分配到$t0 和$t1 中。如果把 25 换成 65536，即 b=65536|a，则用 MIPS 指令或指令序列如何实现？参考答案：只要用一条指令 ori $t1, $t0, 25 就可实现。如果把 25 换成 65536，则不能用一条指令 ori $t1, $t0,
15、65536 来实现，因为 65536 （1 0000 0000 0000 0000B）不能用 16 位立即数表示。可用以下两条指令实现。lui $t1, 1or $t1, $t0, $t112 以下程序段是某个过程对应的 MIPS 指令序列，其功能为复制一个存储块数据到另一个存储块中，存储块中每个数据的类型为 float，源数据块和目的数据块的首地址分别存放在$a0 和$a1 中，复制的数据个数存放在$v0 中，作为返回参数返回给调用过程。在复制过程中遇到 0则停止，最后一个 0 也需要复制，但不被计数。已知程序段中有多个 Bug，请找出它们并修改。addi $v0, $zero, 0loop
16、: lw $v1, 0($a0)sw $v1, 0($a1)addi $a0, $a0, 4addi $a1, $a1, 4beq $v1, $zero, loop 141 参考答案：修改后的代码如下： addi $v0, $zero, 0loop: lw $v1, 0($a0)sw $v1, 0($a1)beq $v1, $zero, exitaddi $a0, $a0, 4addi $a1, $a1, 4addi $v0, $v0, 1j loopexit:13 说明 beq 指令的含义，并解释为什么汇编程序在对下列汇编源程序中的 beq 指令进行汇编时会遇到问题，应该如何修改该程序段？h
17、ere: beq $s0, $s2, therethere: addi $s1, $s0, 4参考答案：beq 是一个 I-型指令，可以跳转到当前指令前，也可以跳转到当前指令后。其转移目的地址的计算公式为：PC+4+offset4，offset 是 16 位带符号整数，用补码表示。因此，分支指令 beq的相对转移范围如下。其正跳范围为：0000 0000 0000 0000（4） 0111 1111 1111 1111（2 17=4+(2151)4）负跳范围为：1000 0000 0000 0000（42 17=4+(215)4） 1111 1111 1111 1111（0=4+(1)4）超过
18、以上范围的跳转就不能用上述指令序列实现。因此，上述指令序列应该改成以下指令序列：here: bne $s0, $s2, skipj thereskip: there: add $s0, $s0, $s014 以下 C 语言程序段中有两个函数 sum_array 和 compare，假定 sum_array 函数第一个被调用，全局变量 sum 分配在寄存器 $s0 中。要求写出每个函数对应的 MIPS 汇编表示，并画出每个函数调用前、后栈中的状态、帧指针和栈指针的位置。1 int sum=0;2 int sum_array(int array, int num) 3 4 int i;5 for
19、(i = 0; i b)12 return 1;13 else14 return 0;15 参考答案（图略）：程序由两个过程组成，全局静态变量 sum 分配给$s0。为了尽量减少指令条数，并减少访问内存次数。在每个过程的过程体中总是先使用临时寄存器$t0$t9，临时寄存器不够或者某个值在调用过程返回后还需要用，就使用保存寄存器$s0$s7。MIPS 指令系统中没有寄存器传送指令，为了提高汇编表示的可读性，引入一条伪指令 move来表示寄存器传送，汇编器将其转换为具有相同功能的机器指令。伪指令“move $t0, $s0”对应的机器指令为“add $t0,$zero,$s0”。（1）过程 set
20、_array：该过程和教材中例 5.10 中的不同，在例 5.10 中 array 数组是过程sum_array 的局部变量，应该在过程栈帧中给数组分配空间，但该题中的数组 array 是在其他过程中定义的，仅将其数组首地址作为参数传递给过程 sum_array（假定在在$a0 中），因此，无需在其栈帧中给数组分配空间。此外，还有一个入口参数为 num（假定在$a1 中），有一个返回参数sum，被调用过程为 compare。因此，其栈帧中除了保留所用的保存寄存器外，还必须保留返回地址，以免在调用过程 compare 时被覆盖。是否保存$fp 要看具体情况，如果确保后面都不用到$fp，则可以不保
21、存，但为了保证$fp 的值不被后面的过程覆盖，通常情况下，应该保存 $fp 的值。栈帧中要保存的信息只有返回地址$ra 和帧指针$fp ，其栈帧空间为 42=8B。汇编表示如下：move $s0, $zero # sum=0set-array: addi $sp, $sp, 8 # generate stack framesw $ra, 4($sp) # save $ra on stacksw $fp, 0($sp) # save $fp on stackaddi $fp, $sp, 4 # set $fpmove $t2, $a0 # base address of array move $
22、t0, $a1 # $t0=num move $t3, $zero # i=0loop: slt $t1, $t3, $t0 # if i=num, $t1= 0beq $t1, $zero, exit1 # if $t1= 0, jump to exit1move $a0, $t0 # $a0=num move $a1, $t3 # $a1=iaddi $a1, $a1, 1 # $a1=i+1jal compare # call compare 143 beq $v0, $zero, else # if $v0 = 0, jump to elsesll $t1, $t3, 2 # i4 a
23、dd $t1, $t2, $t1 # $t1=arrayilw $t4, 0($t1) # load arrayiadd $s0, $s0, $t4 # sum+=arrayielse： addi $t3, $t3, 1 # i=i+1j loop exit1: lw $ra, 4($sp) # restore $ra lw $fp, 0($sp) # restore $fpaddi $sp, $sp, 8 # free stack framejr $ra # return to caller（2）过程 compare：入口参数为 a 和 b，分别在$a0 和$a1 中。有一个返回参数，没有局
24、部变量，是叶子过程，且过程体中没有用到任何保存寄存器，所以栈帧中不需要保留任何信息。compare: move $v0, $zero # return 0beq $a0, $a1, exit2 # if $a0=$a1, jump to exit2slt $t1, $a0, $a1 # if $a0=$a1, $t1= 0bne $t1, $zero, exit2 # if $a0$a1, jump to exit2ori $v0, $zero,1 # return 1exit2: jr $ra15 以下是一个计算阶乘的 C 语言递归过程，请按照 MIPS 过程调用协议写出该递归过程对应的MI
25、PS 汇编语言程序，要求目标代码尽量短（提示：乘法运算可用乘法指令“mul rd, rs, rt”来实现，功能为“rd(rs) (rt)”）。int fact ( int n) if (n 1) return (1) ;else return (n*fact (n-1) )；参考答案：Fact:addi $sp,$sp,-8sw $ra,4($sp)sw $a0,0($sp)slti $t0,$a0,1beq $t0,$zero,L1addi $v0,$zero,1addi $sp,$sp,8jr $raL1:addi $a0,$a0,-1 144 jal Factlw $a0,0($sp)lw $ra,4($sp)addi $sp,$sp,8mul $v0,$a0,$v0jr $ra
