第151集：函数定义的中间代码生成

核心知识点讲解

函数定义的基本形式

在编程语言中，函数定义的基本形式如下：

return_type function_name(parameter1_type parameter1_name, parameter2_type parameter2_name, ...) {
    // 函数体
    statement1;
    statement2;
    ...
    return return_value;
}

函数定义的中间代码生成

生成函数定义的中间代码需要考虑以下几个方面：

函数序言（Prologue）：在函数开始处生成的代码，用于保存调用者的上下文、分配局部变量的空间等。
函数体：生成函数体内语句的中间代码。
函数尾声（Epilogue）：在函数结束处生成的代码，用于恢复调用者的上下文、返回值处理等。

栈帧布局

栈帧（Stack Frame）是函数调用时在栈上分配的一块内存空间，用于存储以下信息：

返回地址：函数执行完毕后返回到调用点的地址。
参数：传递给函数的参数。
局部变量：函数内部定义的变量。
保存的寄存器：被函数修改但需要在函数返回时恢复的寄存器值。
临时变量：函数执行过程中产生的临时数据。

函数序言的生成

函数序言通常包括以下步骤：

保存返回地址：将当前程序计数器的值保存到栈帧中。
保存帧指针：将当前帧指针的值保存到栈帧中，然后更新帧指针。
分配局部变量空间：在栈上为局部变量分配空间。
保存寄存器：保存被函数修改但需要恢复的寄存器的值。

函数尾声的生成

函数尾声通常包括以下步骤：

恢复寄存器：将之前保存的寄存器值恢复。
释放局部变量空间：调整栈指针，释放局部变量占用的空间。
恢复帧指针：将帧指针恢复到之前保存的值。
返回到调用点：跳转到之前保存的返回地址。

实用案例分析

案例1：简单函数定义

示例代码

int add(int a, int b) {
    return a + b;
}

生成的三地址码

add:
    // 函数序言
    // 保存返回地址和帧指针
    push %ra
    push %fp
    mov %sp, %fp
    // 分配局部变量空间（本函数无局部变量）
    
    // 函数体
    t1 = a + b
    
    // 函数尾声
    // 将返回值存入返回寄存器
    mov t1, %v0
    // 释放局部变量空间
    mov %fp, %sp
    // 恢复帧指针和返回地址
    pop %fp
    pop %ra
    // 返回到调用点
    ret

案例2：带局部变量的函数定义

示例代码

int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

生成的三地址码

factorial:
    // 函数序言
    // 保存返回地址和帧指针
    push %ra
    push %fp
    mov %sp, %fp
    // 分配局部变量空间（result 和 i）
    sub $8, %sp
    
    // 函数体
    result = 1
    i = 1
L1: if i <= n goto L2
    goto L3
L2: t1 = result * i
    result = t1
    t2 = i + 1
    i = t2
    goto L1
L3: 
    
    // 函数尾声
    // 将返回值存入返回寄存器
    mov result, %v0
    // 释放局部变量空间
    mov %fp, %sp
    // 恢复帧指针和返回地址
    pop %fp
    pop %ra
    // 返回到调用点
    ret

案例3：带数组局部变量的函数定义

示例代码

int sum_array(int n) {
    int arr[10];
    int sum = 0;
    for (int i = 0; i < n && i < 10; i++) {
        arr[i] = i;
        sum += arr[i];
    }
    return sum;
}

生成的三地址码

sum_array:
    // 函数序言
    // 保存返回地址和帧指针
    push %ra
    push %fp
    mov %sp, %fp
    // 分配局部变量空间（arr[10]、sum 和 i）
    // arr[10] 需要 10 * 4 = 40 字节，sum 和 i 各需要 4 字节，总共 48 字节
    sub $48, %sp
    
    // 函数体
    sum = 0
    i = 0
L1: if i < n goto L2
    goto L4
L2: if i < 10 goto L3
    goto L4
L3: t1 = i * 4
    t2 = arr + t1
    *t2 = i
    t3 = *t2
    t4 = sum + t3
    sum = t4
    t5 = i + 1
    i = t5
    goto L1
L4: 
    
    // 函数尾声
    // 将返回值存入返回寄存器
    mov sum, %v0
    // 释放局部变量空间
    mov %fp, %sp
    // 恢复帧指针和返回地址
    pop %fp
    pop %ra
    // 返回到调用点
    ret

案例4：带嵌套作用域的函数定义

示例代码

int outer_function(int x) {
    int y = x + 1;
    
    int inner_function(int z) {
        return y + z;
    }
    
    return inner_function(5);
}

生成的三地址码

outer_function:
    // 函数序言
    push %ra
    push %fp
    mov %sp, %fp
    sub $8, %sp  // 为 y 分配空间
    
    // 函数体
    y = x + 1
    
    // 调用 inner_function
    param 5
    t1 = call inner_function, 1
    
    // 函数尾声
    mov t1, %v0
    mov %fp, %sp
    pop %fp
    pop %ra
    ret

inner_function:
    // 函数序言
    push %ra
    push %fp
    mov %sp, %fp
    // 无局部变量，不需要分配空间
    
    // 函数体
    // 注意：这里需要访问外部函数的变量 y
    t2 = y + z
    
    // 函数尾声
    mov t2, %v0
    mov %fp, %sp
    pop %fp
    pop %ra
    ret

案例5：递归函数定义

示例代码

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

生成的三地址码

fibonacci:
    // 函数序言
    push %ra
    push %fp
    mov %sp, %fp
    // 无局部变量，不需要分配空间
    
    // 函数体
    if n <= 1 goto L1
    goto L2
L1: mov n, %v0
    // 函数尾声
    mov %fp, %sp
    pop %fp
    pop %ra
    ret
L2: // 计算 fibonacci(n - 1)
    t1 = n - 1
    param t1
    t2 = call fibonacci, 1
    // 计算 fibonacci(n - 2)
    t3 = n - 2
    param t3
    t4 = call fibonacci, 1
    // 计算和
    t5 = t2 + t4
    
    // 函数尾声
    mov t5, %v0
    mov %fp, %sp
    pop %fp
    pop %ra
    ret

代码实现

下面是一个简单的函数定义中间代码生成器的实现，使用 Python 语言：

class FunctionDefinitionCodeGenerator:
    def __init__(self):
        self.temp_count = 0
        self.label_count = 0
        self.instructions = []
    
    def new_temp(self):
        """生成新的临时变量名"""
        self.temp_count += 1
        return f"t{self.temp_count}"
    
    def new_label(self):
        """生成新的标签名"""
        self.label_count += 1
        return f"L{self.label_count}"
    
    def generate_expression(self, expr):
        """生成表达式的中间代码
        
        Args:
            expr: 表达式，以元组形式表示，如 ('+', 'a', 'b')
            
        Returns:
            存储表达式结果的临时变量名
        """
        if isinstance(expr, tuple):
            op = expr[0]
            if op == '+' or op == '-' or op == '*' or op == '/':
                # 二元运算符
                left = self.generate_expression(expr[1])
                right = self.generate_expression(expr[2])
                temp = self.new_temp()
                self.instructions.append(f"{temp} = {left} {op} {right}")
                return temp
            elif op == '>' or op == '<' or op == '>=' or op == '<=' or op == '==' or op == '!=':
                # 比较运算符
                left = self.generate_expression(expr[1])
                right = self.generate_expression(expr[2])
                temp = self.new_temp()
                self.instructions.append(f"{temp} = {left} {op} {right}")
                return temp
            elif op == 'call':
                # 函数调用
                func_name = expr[1]
                args = expr[2]
                # 生成参数传递的中间代码
                for arg in args:
                    arg_result = self.generate_expression(arg)
                    self.instructions.append(f"param {arg_result}")
                # 生成函数调用指令
                temp = self.new_temp()
                self.instructions.append(f"{temp} = call {func_name}, {len(args)}")
                return temp
        else:
            # 常量或变量
            return expr
    
    def generate_statement(self, stmt):
        """生成语句的中间代码
        
        Args:
            stmt: 语句，可以是赋值语句、if语句等
        """
        if isinstance(stmt, dict):
            if 'type' in stmt:
                if stmt['type'] == 'assignment':
                    # 赋值语句
                    lvalue = stmt['lvalue']
                    rvalue = stmt['rvalue']
                    result = self.generate_expression(rvalue)
                    self.instructions.append(f"{lvalue} = {result}")
                elif stmt['type'] == 'if':
                    # if语句
                    condition = stmt['condition']
                    then_stmt = stmt['then_stmt']
                    else_stmt = stmt.get('else_stmt', None)
                    # 生成条件表达式的中间代码
                    cond_result = self.generate_expression(condition)
                    # 生成标签
                    then_label = self.new_label()
                    end_label = self.new_label()
                    # 生成条件跳转指令
                    self.instructions.append(f"if {cond_result} goto {then_label}")
                    # 如果有else分支，生成跳转到else标签的指令
                    if else_stmt:
                        else_label = self.new_label()
                        self.instructions.append(f"goto {else_label}")
                    else:
                        self.instructions.append(f"goto {end_label}")
                    # 生成then分支的语句
                    self.instructions.append(f"{then_label}:")
                    self.generate_statement(then_stmt)
                    self.instructions.append(f"goto {end_label}")
                    # 如果有else分支，生成else分支的语句
                    if else_stmt:
                        self.instructions.append(f"{else_label}:")
                        self.generate_statement(else_stmt)
                    # 生成结束标签
                    self.instructions.append(f"{end_label}:")
                elif stmt['type'] == 'return':
                    # return语句
                    expr = stmt.get('expression', None)
                    if expr:
                        result = self.generate_expression(expr)
                        self.instructions.append(f"return {result}")
                    else:
                        self.instructions.append(f"return")
                elif stmt['type'] == 'for':
                    # for循环
                    init_stmt = stmt['init']
                    condition = stmt['condition']
                    update_stmt = stmt['update']
                    body_stmt = stmt['body']
                    # 生成初始化语句
                    self.generate_statement(init_stmt)
                    # 生成标签
                    loop_label = self.new_label()
                    body_label = self.new_label()
                    end_label = self.new_label()
                    # 生成循环开始标签
                    self.instructions.append(f"{loop_label}:")
                    # 生成条件表达式
                    cond_result = self.generate_expression(condition)
                    # 生成条件跳转指令
                    self.instructions.append(f"if !{cond_result} goto {end_label}")
                    # 生成循环体开始标签
                    self.instructions.append(f"{body_label}:")
                    # 生成循环体语句
                    self.generate_statement(body_stmt)
                    # 生成更新语句
                    self.generate_statement(update_stmt)
                    # 生成跳转到循环开始的指令
                    self.instructions.append(f"goto {loop_label}")
                    # 生成循环结束标签
                    self.instructions.append(f"{end_label}:")
                elif stmt['type'] == 'block':
                    # 代码块
                    for s in stmt['statements']:
                        self.generate_statement(s)
    
    def generate_function_definition(self, func_name, params, body, local_vars=None):
        """生成函数定义的中间代码
        
        Args:
            func_name: 函数名
            params: 参数列表
            body: 函数体语句
            local_vars: 局部变量列表
        """
        # 生成函数入口标签
        self.instructions.append(f"{func_name}:")
        
        # 生成函数序言
        self.instructions.append("    // 函数序言")
        # 保存返回地址和帧指针
        self.instructions.append("    push %ra")
        self.instructions.append("    push %fp")
        self.instructions.append("    mov %sp, %fp")
        # 分配局部变量空间
        if local_vars:
            # 假设每个局部变量占用4字节
            local_var_size = len(local_vars) * 4
            self.instructions.append(f"    sub ${local_var_size}, %sp")
        
        # 生成函数体的中间代码
        self.generate_statement(body)
        
        # 生成函数尾声
        self.instructions.append("    // 函数尾声")
        # 释放局部变量空间
        self.instructions.append("    mov %fp, %sp")
        # 恢复帧指针和返回地址
        self.instructions.append("    pop %fp")
        self.instructions.append("    pop %ra")
        # 返回到调用点
        self.instructions.append("    ret")
    
    def get_instructions(self):
        """获取生成的中间代码指令"""
        return self.instructions

# 测试代码
generator = FunctionDefinitionCodeGenerator()

# 测试函数定义
print("测试函数定义的中间代码生成:")

# 生成 factorial 函数的中间代码
factorial_body = {
    'type': 'if',
    'condition': ('<=', 'n', '1'),
    'then_stmt': {
        'type': 'return',
        'expression': 'n'
    },
    'else_stmt': {
        'type': 'return',
        'expression': ('*', 'n', ('call', 'factorial', [('-', 'n', '1')]))
    }
}
generator.generate_function_definition('factorial', ['n'], factorial_body, ['result', 'i'])

# 生成 main 函数的中间代码
main_body = {
    'type': 'assignment',
    'lvalue': 'result',
    'rvalue': ('call', 'factorial', ['5'])
}
generator.generate_function_definition('main', [], main_body, ['result'])

# 打印生成的中间代码
for instr in generator.get_instructions():
    print(instr)

运行结果

测试函数定义的中间代码生成:
factorial:
    // 函数序言
    push %ra
    push %fp
    mov %sp, %fp
    sub $8, %sp
    if n <= 1 goto L1
    goto L2
L1:
    return n
    // 函数尾声
    mov %fp, %sp
    pop %fp
    pop %ra
    ret
L2:
    t1 = n - 1
    param t1
    t2 = call factorial, 1
    t3 = n * t2
    return t3
    // 函数尾声
    mov %fp, %sp
    pop %fp
    pop %ra
    ret
main:
    // 函数序言
    push %ra
    push %fp
    mov %sp, %fp
    sub $4, %sp
    param 5
    t4 = call factorial, 1
    result = t4
    // 函数尾声
    mov %fp, %sp
    pop %fp
    pop %ra
    ret

总结

函数定义的中间代码生成是编译器前端的重要组成部分，它涉及到函数序言、函数体和函数尾声的生成，以及栈帧布局的设计。函数序言和尾声负责保存和恢复调用者的上下文，确保函数调用的正确执行。栈帧布局则决定了函数参数、局部变量和临时数据的存储方式。

在生成函数定义的中间代码时，需要注意以下几点：

栈帧布局：合理设计栈帧布局，确保参数、局部变量和临时数据的正确存储和访问。
函数序言和尾声：正确生成函数序言和尾声，确保调用者的上下文能够被正确保存和恢复。
局部变量：为局部变量分配足够的空间，并正确计算它们在栈帧中的地址。
返回值处理：将函数的返回值正确存储到指定的位置，以便调用者能够获取。
递归函数：对于递归函数，需要确保每次递归调用都能够正确分配栈帧，并在递归结束后正确释放。