计算机硬件对过程的支持

一、过程（Procedure）概述

过程（或函数）是结构化编程的核心工具，用于提高程序的可读性和代码复用性。过程允许程序员将任务分解为模块化部分，通过参数传递数据并返回结果，实现与程序其他部分的接口。

定义：

过程：根据提供的参数执行特定任务的存储子程序。
比喻为“侦探”：接受任务（参数），获取资源，执行任务，返回结果，不干扰系统其他部分，仅基于“需要知道”的原则工作。

过程运行的六个步骤：

将参数放置在过程可访问的位置。
将控制权移交至过程。
分配过程所需的存储资源。
执行任务。
将结果放置在调用程序可访问的位置。
将控制权返回调用点（支持多点调用）。

二、MIPS架构对过程的支持

MIPS架构通过寄存器分配和特定指令支持过程调用，优化性能。

1. 寄存器分配约定

MIPS有32个寄存器，部分用于过程调用：

参数寄存器：$a0 ~ $a3（4个），用于传递参数。
返回值寄存器：$v0 ~ $v1（2个），用于返回结果。
返回地址寄存器：$ra，保存调用点的返回地址。
栈指针寄存器：$sp（第29号寄存器），指向栈顶。
全局指针寄存器：$gp，指向静态数据区。
帧指针寄存器：$fp（可选），指向过程帧的第一个字。

寄存器分类：

临时寄存器（$t0 ~ $t9）：无需在过程调用中保存。
保存寄存器（$s0 ~ $s7）：若使用，需由被调用者保存和恢复。

2. 关键指令

跳转和链接指令（jal）：
- 格式：jal ProcedureAddress
- 功能：跳转到指定地址，同时将下一条指令地址（PC+4）保存到$ra。
- 返回地址：存储在$ra中，用于过程返回。
寄存器跳转指令（jr）：
- 格式：jr $ra
- 功能：无条件跳转到$ra中的地址，实现过程返回。
程序计数器（PC）：
- 保存当前执行指令的地址，jal指令将PC+4存入$ra。

3. 栈（Stack）管理

栈是后进先出（LIFO）的数据结构，用于寄存器换出和局部变量存储。

栈指针（$sp）：指向栈顶，最新分配地址。
压栈（push）：将数据存入栈，$sp减小。
出栈（pop）：移除栈顶数据，$sp增大。
栈增长方向：从高地址到低地址。
过程帧（Procedure Frame）：
- 也称活动记录，包含保存的寄存器和局部变量。
- 帧指针（$fp）：指向过程帧的第一个字，提供固定基址，简化局部变量引用。
- 若无局部变量，编译器可省略$fp设置。

4. 内存分配

MIPS内存分配约定：

代码段（Text Segment）：存储机器代码，从低地址开始（0x00400000）。
静态数据段：存储常量和静态变量，从0x10000000开始。
堆（Heap）：动态数据结构（如链表），从静态数据段后向上增长。
栈（Stack）：从高地址（0x7fffffff）向下增长。
全局指针（$gp）：初始化为0x10008000，便于访问静态数据。

C语言内存管理：

动态变量：在过程内有效，退出时失效。
静态变量：程序运行期间始终存在。
堆管理：
- malloc()：分配堆空间，返回指针。
- free()：释放堆空间。
- 常见错误：
  - 内存泄漏：未释放空间，导致内存耗尽。
  - 悬摆指针：过早释放空间，导致指针指向无效位置。
Java：自动内存分配和垃圾回收，减少内存管理错误。

三、过程调用示例

1. 叶过程（Leaf Procedure）

不调用其他过程的过程，较为简单。
示例：C过程int leaf_example(int g, int h, int i, int j)：

int leaf_example(int g, int h, int i, int j) {
    int f;
    f = (g + h) - (i + j);
    return f;
}

MIPS汇编代码：

leaf_example:
    addi $sp, $sp, -12        # 分配栈空间（3个字）
    sw $t1, 8($sp)            # 保存$t1
    sw $t0, 4($sp)            # 保存$t0
    sw $s0, 0($sp)            # 保存$s0
    add $t0, $a0, $a1         # $t0 = g + h
    add $t1, $a2, $a3         # $t1 = i + j
    sub $s0, $t0, $t1         # $s0 = (g + h) - (i + j)
    add $v0, $s0, $zero       # 返回值$v0 = f
    lw $s0, 0($sp)            # 恢复$s0
    lw $t0, 4($sp)            # 恢复$t0
    lw $t1, 8($sp)            # 恢复$t1
    addi $sp, $sp, 12         # 释放栈空间
    jr $ra                    # 返回

优化：因$t0、$t1为临时寄存器，无需保存，代码可简化。

2. 嵌套过程（递归）

调用其他过程或自身的递归过程，需小心处理寄存器冲突。
示例：递归阶乘int fact(int n)：

int fact(int n) {
    if (n < 1) return 1;
    else return n * fact(n - 1);
}

MIPS汇编代码：

fact:
    addi $sp, $sp, -8         # 分配栈空间（2个字）
    sw $ra, 4($sp)            # 保存返回地址
    sw $a0, 0($sp)            # 保存参数n
    slti $t0, $a0, 1          # 测试n < 1
    beq $t0, $zero, L1        # 若n >= 1，跳转L1
    addi $v0, $zero, 1        # 返回1
    addi $sp, $sp, 8          # 释放栈空间
    jr $ra                    # 返回
L1:
    addi $a0, $a0, -1         # n = n - 1
    jal fact                  # 递归调用fact
    lw $a0, 0($sp)            # 恢复n
    lw $ra, 4($sp)            # 恢复返回地址
    addi $sp, $sp, 8          # 释放栈空间
    mul $v0, $a0, $v0         # 返回n * fact(n-1)
    jr $ra                    # 返回

关键点：

保存$ra和$a0，防止递归调用覆盖。
栈管理确保正确恢复寄存器和返回地址。

四、字符与字符串处理

1. ASCII与Unicode

ASCII：8位编码，广泛用于英文字符。
- 示例："Cal"表示为67, 97, 108, 0（C语言以null结束）。
Unicode：16位编码（UTF-16），支持多语言，Java默认使用。
- 示例：支持希腊文、西里尔文等，UTF-8为变长编码。

MIPS指令：

字节操作：
- lb（load byte）：读取字节，符号扩展。
- sb（store byte）：存储字节。
半字操作（Unicode）：
- lh（load halfword）：读取16位，符号扩展。
- lhu（load halfword unsigned）：无符号读取。
- sh（store halfword）：存储16位。

2. 字符串复制示例

C过程：strcpy复制以null结束的字符串：

void strcpy(char x[], char y[]) {
    int i = 0;
    while ((x[i] = y[i]) != '\0') i++;
}

MIPS汇编代码：

strcpy:
    addi $sp, $sp, -4         # 分配栈空间
    sw $s0, 0($sp)            # 保存$s0
    add $s0, $zero, $zero     # i = 0
L1:
    add $t1, $s0, $a1         # y[i]地址
    lbu $t2, 0($t1)           # 读取y[i]
    add $t3, $s0, $a0         # x[i]地址
    sb $t2, 0($t3)            # x[i] = y[i]
    beq $t2, $zero, L2        # 若y[i] == 0，退出
    addi $s0, $s0, 1          # i++
    j L1                      # 继续循环
L2:
    lw $s0, 0($sp)            # 恢复$s0
    addi $sp, $sp, 4          # 释放栈空间
    jr $ra                    # 返回

优化：因strcpy为叶过程，可用临时寄存器（如$t0）替代$s0，省略保存/恢复。

五、寻址模式

MIPS支持五种寻址模式：

立即数寻址：操作数为指令中的常数。
寄存器寻址：操作数为寄存器。
基址寻址：地址为基址寄存器+常数，操作数在内存。
PC相对寻址：地址为PC+常数，用于条件分支。
伪直接寻址：跳转地址由26位字段左移2位+PC高4位组成。

分支与跳转：

条件分支：使用PC相对寻址，16位字地址，范围±2^15字。
跳转（j, jal）：使用伪直接寻址，26位字地址，范围2^28字节。
远距离分支：通过反转条件+无条件跳转实现：

assembly bne $s0, $s1, L2 j L1 L2:

六、32位立即数

指令：

lui（load upper immediate）：加载16位常数到寄存器高16位，低16位填0。
ori：设置低16位，结合lui构造32位常数。

示例：加载0x00003D090000：

lui $s0, 61               # 高16位：0000 0000 0011 1101
ori $s0, $s0, 2304        # 低16位：0000 1001 0000 0000

七、机器语言解码

示例：解码0x00af8020：

转换为二进制：000000 00101 01111 10000 00000 100000
操作码（31-26）：000000，R型指令。
功能码（5-0）：100000，为add。
寄存器：rs=5($a1), rt=15($t7), rd=16($s0)。
汇编指令：add $s0, $a1, $t7。

八、C与Java对比

内存管理：
- C：程序员显式管理（malloc/free），易导致指针错误和内存泄漏。
- Java：自动内存分配和垃圾回收，减少错误。
字符串：
- C：以null（0）结束，占用内存较少。
- Java：包含长度字段（类似数组），占用更多内存。
- 操作：Java提供内置方法（如长度计算），比C更快。
字符：
- C：使用8位ASCII。
- Java：使用16位Unicode，支持多语言。

小测验答案：

关于C和Java：
- 正确：1（C显式管理，Java自动），2（C易导致指针和内存泄漏错误）。
存储1亿：
- 最大：Java的String（16位Unicode，20字节）。
- 次之：C的string（8位ASCII，10字节）。
- 最小：C的int（32位，4字节）。

九、扩展与总结

递归优化：尾递归（如sum示例）可通过迭代实现，减少调用开销：

assembly sum: slti $t0, $a0, 1 bne $t0, $zero, sum_exit add $a1, $a1, $a0 addi $a0, $a0, -1 j sum sum_exit: add $v0, $a1, $zero jr $ra
性能优化：
- 使用临时寄存器减少保存/恢复开销。
- 栈对齐（4字节）提高访问效率。
- PC相对寻址优化分支指令性能。
硬件支持：
- 寄存器快速存储数据，减少内存访问。
- 专用指令（jal, jr）简化过程调用。
- 栈和堆动态管理内存，支持复杂程序。