《深入理解计算机系统》练习题4.4-4.5

谁践踏了优雅 2022-03-30 09:22 281阅读 0赞

# 4.4 #

用Y86-64来实现一个递归求和函数：如下

long rsum(long *start, long count) { 
      if (count <= 0)
    	  return 0;
      return *start + rsum(start+1,count-1);
    }

没想出来答案，但能看明白答案==

**下面为x86-64的代码：**  
![在这里插入图片描述][20190105162249208.jpg]  
1.表面上看起来，每次进入递归函数都会`movl $0, %eax`使得返回值寄存器；实际上，是每次递归除了最后一次的递归终点，都会先执行函数体的前半段（以`call rsum`分开），即每次执行函数体前半段都会使得%rax为0，但这并不会产生错误影响（虽然我觉得有点多余，把`movl $0, %eax`放在.L9代码块里不好吗，就只需要做一次了）。执行了最后一次即递归终点后，返回上一层函数，执行上一层函数的后半段，以后对%rax产生操作就只有addq指令了。

2.`pushq %rbx`，对于上一层函数来说，当前函数为被调用者，作为被调用者，就要做好被调用者的工作，把上一层函数保存在%rbx的值入栈存起来，然后再放心大胆地使用%rbx。

3.%rbx一直存的都是当前数组指针指向的值。

**下面为Y86-64的代码：**  
![在这里插入图片描述][20190105163643759.png]  
有一些差别呢：  
清零用的xorq；测试用的andq；跳转用的je，毕竟为0就是终止条件。

**下面为MinGW编译得到的代码**，使用命令为`gcc -Og -S test.c`：

.file	"test.c"
    	.text
    	.globl	_rsum
    	.def	_rsum;	.scl	2;	.type	32;	.endef
    _rsum:
    LFB0:
    	.cfi_startproc
    	pushl	%ebx     # 将被调用者保存寄存器%ebx的值入栈存起来
    	.cfi_def_cfa_offset 8
    	.cfi_offset 3, -8
    	subl	$24, %esp  # 分配了24字节的栈空间
    	.cfi_def_cfa_offset 32
    	movl	32(%esp), %ecx # 从32开始，跳过了之前入栈存的值所在的8字节；32与36相差4，一个地址只需要4字节存储，是数组元素的地址
    	movl	36(%esp), %edx # 36处存储count的地址，取出count放入%edx
    	testl	%edx, %edx   # %edx是count
    	jle	L3   # 大于0的正常情况即递归过程，会走下面这块代码
    	movl	(%ecx), %ebx  # 取出数组元素指针指向的值放入%ebx中
    	subl	$1, %edx      # count减一
    	movl	%edx, 4(%esp) # 在新分配栈空间存新的count
    	addl	$4, %ecx      # 数组元素指针减四
    	movl	%ecx, (%esp)  # 在新分配栈空间存新的start
    	call	_rsum
    	addl	%ebx, %eax
    L1:
    	addl	$24, %esp  #收回栈空间
    	.cfi_remember_state
    	.cfi_def_cfa_offset 8
    	popl	%ebx       #取出保存的值
    	.cfi_restore 3
    	.cfi_def_cfa_offset 4
    	ret
    L3:
    	.cfi_restore_state
    	movl	$0, %eax  #这句只会执行一次，进行了优化
    	jmp	L1
    	.cfi_endproc
    LFE0:
    	.ident	"GCC: (MinGW.org GCC-6.3.0-1) 6.3.0"

一直对MinGW编译得到的汇编有点疑问，比如第一个参数和第二个参数为什么不用%rdi和%rsi，但这里先忽略不计吧。  
1.%ecx存的是数组元素指针，%ebx存的是数组元素，%edx存的是count。

2.编译器认为long型变量是4字节的。

3.从`movl 32(%esp), %ecx`和`movl 36(%esp), %edx`，可以看出编译器认为指针只需要4字节存储，32与36相差4可以看出，且用4字节的%ecx寄存器来存指针，也可以看出。

4.解释一下为什么分配了24栈空间，又要从32地址偏移处取变量，用下图解释：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]  
这是因为保存%ebx的值时用了8字节，栈空间又分配了24字节，所以要想取到上一个栈帧中的变量，就得偏移32字节。  
上图过程可以一直进行下去。

# 4.5 #

答案看懂了，但是有点奇怪，明明都使用条件跳转了，还非得要在loop里面先把-x给算出来；先判断x的正负，如果需要再计算-x这样不好吗？所以我觉得loop部分应该这样改写：

loop:
      mrmovq (%rdi), %r10
      jge pos    # 如果x小于0那么将执行下面三行
      xorq %r11, %r11    # 接下来三行将%r10赋值为-x
      subq %r10, %r11
      rrmovq %r11, %r10

另外取负指令是`neg`；也可以通过每位取反再加1，取反指令是`not`。怕是Y86-64里面没有这两个指令吧。

[20190105162249208.jpg]: /images/20220330/6fa6e7fe185845959ad7bc641c1816f5.png
[20190105163643759.png]: /images/20220330/010bb07847ac4249931fe3a0167fcaac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]: /images/20220330/e49e8daab69244728ab3eaeb0c07633a.png