# compilerpractice

**Repository Path**: luoshuang148/compilerpractice

## Basic Information

- **Project Name**: compilerpractice
- **Description**: 无呜呜呜呜呜呜呜呜呜呜呜
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 24
- **Created**: 2025-07-03
- **Last Updated**: 2025-07-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# RISC-V32 代码生成器

这是一个为C语言子集编译器实现的RISC-V32汇编代码生成器，能够将抽象语法树（AST）转换为可执行的RISC-V汇编代码。

## 功能特性

### 1. 完整的RISC-V32指令集支持
- **算术运算**: `add`, `sub`, `mul`, `div`, `rem`
- **逻辑运算**: `and`, `or`, `xor`, `not`
- **比较运算**: `slt`, `sltu`, `seqz`, `snez`
- **控制流**: `beqz`, `bnez`, `j`, `call`, `ret`
- **内存操作**: `lw`, `sw`, `addi`, `lui`

### 2. 函数调用栈管理
- 标准的函数调用约定
- 自动的栈帧管理（prologue/epilogue）
- 参数传递和返回值处理
- 寄存器保存和恢复

### 3. 寄存器分配
- 智能寄存器分配算法
- 临时寄存器管理
- 变量到寄存器的映射
- 寄存器溢出处理

### 4. 控制流生成
- **条件语句**: `if`, `if-else`
- **循环语句**: `while`
- **跳转语句**: `break`, `continue`
- **短路计算**: `&&`, `||`

### 5. 优化功能
- 常量折叠
- 公共子表达式消除
- 寄存器分配优化
- 死代码消除

## 核心组件详解

### Optimizer（优化器）

#### 架构设计
优化器采用多阶段优化策略，在AST层面进行语义保持的转换，提高生成代码的执行效率。

#### 核心优化算法

##### 1. 常量折叠（Constant Folding）
```cpp
// 在编译时计算常量表达式
// 例如: 2 + 3 * 4 -> 14
// 例如: true && false -> false
```

**实现原理**：
- 遍历AST中的表达式节点
- 检测所有操作数都是常量的表达式
- 在编译时执行计算，用结果替换原表达式
- 支持算术、逻辑、比较运算的常量折叠

**优化效果**：
- 减少运行时计算开销
- 简化生成的汇编代码
- 提高程序执行效率

##### 2. 公共子表达式消除（Common Subexpression Elimination）
```cpp
// 识别并重用相同的表达式计算结果
// 例如: a = x + y; b = x + y; -> temp = x + y; a = temp; b = temp;
```

**实现原理**：
- 维护表达式哈希表，记录已计算的表达式
- 检测重复的表达式计算
- 将重复计算替换为临时变量引用
- 在适当位置插入临时变量的计算

**优化效果**：
- 避免重复计算
- 减少寄存器使用
- 提高代码执行效率

##### 3. 死代码消除（Dead Code Elimination）
```cpp
// 移除永远不会执行的代码
// 例如: if (false) { ... } -> 删除整个if块
// 例如: 未使用的变量声明
```

**实现原理**：
- 分析控制流图（CFG）
- 识别不可达的基本块
- 检测未使用的变量和表达式
- 安全地删除死代码

**优化效果**：
- 减少代码体积
- 提高编译速度
- 简化生成的汇编代码

#### 优化器接口
```cpp
class Optimizer {
public:
    // 执行所有优化pass
    void optimize(ASTNode* root);
    
private:
    // 常量折叠优化
    void constantFolding(ASTNode* node);
    
    // 公共子表达式消除
    void commonSubexpressionElimination(ASTNode* node);
    
    // 死代码消除
    void deadCodeElimination(ASTNode* node);
    
    // 表达式哈希表，用于CSE
    std::unordered_map<std::string, ASTNode*> exprCache;
};
```

### CodeGenerator（代码生成器）

#### 架构设计
代码生成器采用递归下降的方式遍历AST，为每个语法结构生成对应的RISC-V汇编代码。采用寄存器分配策略和栈帧管理确保生成的代码正确且高效。

#### 核心组件

##### 1. 寄存器分配器（RegisterAllocator）
```cpp
class RegisterAllocator {
private:
    // 寄存器使用状态
    std::vector<bool> usedRegisters;
    // 变量到寄存器的映射
    std::unordered_map<std::string, int> varToReg;
    // 寄存器到变量的映射
    std::vector<std::string> regToVar;
    
public:
    // 分配寄存器给变量
    int allocateRegister(const std::string& var);
    
    // 释放寄存器
    void freeRegister(int reg);
    
    // 获取变量当前使用的寄存器
    int getRegister(const std::string& var);
};
```

**分配策略**：
- **贪心分配**：优先使用空闲寄存器
- **寄存器溢出**：当寄存器不足时，将变量溢出到栈
- **生命周期管理**：跟踪变量的使用范围，及时释放寄存器

**寄存器约定**：
- `a0-a7`: 参数传递和返回值
- `t0-t6`: 临时寄存器，调用者保存
- `s0-s11`: 保存寄存器，被调用者保存
- `sp`: 栈指针
- `ra`: 返回地址

##### 2. 栈帧管理器（StackFrameManager）
```cpp
class StackFrameManager {
private:
    int frameSize;           // 当前栈帧大小
    int localVarOffset;      // 局部变量偏移量
    std::unordered_map<std::string, int> varOffsets; // 变量偏移量映射
    
public:
    // 分配局部变量空间
    int allocateLocalVar(const std::string& var, int size);
    
    // 获取变量在栈中的偏移量
    int getVarOffset(const std::string& var);
    
    // 生成函数序言
    void generatePrologue();
    
    // 生成函数尾声
    void generateEpilogue();
};
```

**栈帧布局**：
```
高地址
+------------------+
|   参数区域       |  <- 调用者栈帧
+------------------+
|   返回地址       |  <- 当前栈帧
+------------------+
|   保存的s0       |
+------------------+
|   局部变量       |
+------------------+
|   临时空间       |
+------------------+
低地址
```

##### 3. 控制流生成器（ControlFlowGenerator）
```cpp
class ControlFlowGenerator {
private:
    int labelCounter;        // 标签计数器
    std::stack<std::string> breakLabels;    // break标签栈
    std::stack<std::string> continueLabels; // continue标签栈
    
public:
    // 生成条件语句
    void generateIfStmt(ASTNode* node);
    
    // 生成循环语句
    void generateWhileStmt(ASTNode* node);
    
    // 生成短路计算
    void generateShortCircuit(ASTNode* node, 
                             const std::string& trueLabel, 
                             const std::string& falseLabel);
};
```

**控制流实现**：
- **条件语句**：使用条件跳转指令（`beqz`, `bnez`）
- **循环语句**：使用标签和跳转指令实现循环控制
- **短路计算**：优化逻辑表达式的求值顺序

#### 代码生成策略

##### 1. 表达式代码生成
```cpp
Register CodeGenerator::generateExpression(ASTNode* node) {
    switch (node->type) {
        case AST_BINARY_OP:
            return generateBinaryOp(node);
        case AST_UNARY_OP:
            return generateUnaryOp(node);
        case AST_VAR_REF:
            return generateVarRef(node);
        case AST_NUM_LITERAL:
            return generateNumLiteral(node);
        case AST_FUNC_CALL:
            return generateFuncCall(node);
    }
}
```

**生成策略**：
- **二元运算**：生成左操作数→生成右操作数→执行运算
- **一元运算**：生成操作数→执行运算
- **变量引用**：加载变量值到寄存器
- **常量**：使用立即数指令
- **函数调用**：保存寄存器→传递参数→调用函数→恢复寄存器

##### 2. 语句代码生成
```cpp
void CodeGenerator::generateStatement(ASTNode* node) {
    switch (node->type) {
        case AST_IF_STMT:
            generateIfStmt(node);
            break;
        case AST_WHILE_STMT:
            generateWhileStmt(node);
            break;
        case AST_RETURN_STMT:
            generateReturnStmt(node);
            break;
        case AST_DECL_ASSIGN_STMT:
            generateDeclAssignStmt(node);
            break;
    }
}
```

**生成策略**：
- **声明赋值**：分配变量空间→生成表达式→存储结果
- **返回语句**：生成返回值表达式→设置返回值寄存器→生成返回指令
- **条件语句**：生成条件→条件跳转→生成分支代码
- **循环语句**：生成循环头→循环体→跳转回循环头

##### 3. 函数调用生成
```cpp
void CodeGenerator::generateFuncCall(ASTNode* node) {
    // 1. 保存调用者保存的寄存器
    saveCallerSavedRegisters();
    
    // 2. 生成参数表达式并传递
    for (auto& arg : node->children) {
        Register reg = generateExpression(arg);
        // 将参数移动到a0-a7寄存器
        moveToArgRegister(reg, argIndex++);
    }
    
    // 3. 调用函数
    emit("call " + node->value);
    
    // 4. 恢复调用者保存的寄存器
    restoreCallerSavedRegisters();
    
    // 5. 获取返回值（在a0寄存器中）
    return getReturnValue();
}
```

**调用约定**：
- **参数传递**：使用a0-a7寄存器，超过8个参数使用栈
- **返回值**：使用a0寄存器
- **寄存器保存**：调用者保存t0-t6，被调用者保存s0-s11
- **栈对齐**：保持16字节对齐

#### 代码生成器接口
```cpp
class CodeGenerator {
private:
    RegisterAllocator regAllocator;
    StackFrameManager stackManager;
    ControlFlowGenerator flowGenerator;
    std::vector<std::string> assemblyCode;
    
public:
    // 生成完整的汇编代码
    std::string generateCode(ASTNode* root);
    
    // 生成函数代码
    void generateFunction(ASTNode* node);
    
    // 生成表达式代码
    Register generateExpression(ASTNode* node);
    
    // 生成语句代码
    void generateStatement(ASTNode* node);
    
    // 输出汇编代码
    void outputAssembly(const std::string& filename);
};
```

## 编译和使用

### Linux/macOS 平台

#### 1. 编译编译器
```bash
make all
```

#### 2. 运行测试
```bash
# 简单测试
make test

# 复杂测试
./compiler test_complex.c
```

### Windows 平台

#### 1. 环境准备
- 安装 MSYS2 或 MinGW-w64
- 安装 bison 和 flex
- 参考 [Windows 编译指南](README_WINDOWS.md)

#### 2. 编译方法

**方法一：使用批处理脚本（推荐）**
```cmd
build_windows.bat
```

**方法二：使用 Makefile**
```cmd
make -f Makefile.windows all
```

**方法三：手动编译**
```cmd
bison -d parser.y
move parser.tab.c parser.tab.cpp
flex -o lexer.cpp lexer.l
g++ -std=c++11 -Wall -O2 -o compiler.exe *.cpp
```

#### 3. 运行测试
```cmd
compiler.exe test.c
compiler.exe test_complex.c
```

### 3. 查看生成的汇编代码
编译器会输出：
- 抽象语法树
- 符号表
- 生成的RISC-V汇编代码
- 保存汇编代码到 `.s` 文件

## 代码结构

### 核心类

#### `CodeGenerator`
主要的代码生成器类，负责：
- 遍历AST并生成汇编代码
- 管理函数调用栈
- 处理控制流
- 调用优化器

#### `RegisterAllocator`
寄存器分配器，负责：
- 分配和释放寄存器
- 管理寄存器使用状态
- 变量到寄存器的映射
- 寄存器溢出处理

### 关键方法

#### 表达式代码生成
```cpp
Register generateExpression(ASTNode* node);
Register generateBinaryOp(ASTNode* node);
Register generateUnaryOp(ASTNode* node);
Register generateVarRef(ASTNode* node);
Register generateNumLiteral(ASTNode* node);
Register generateFuncCall(ASTNode* node);
```

#### 语句代码生成
```cpp
void generateStatement(ASTNode* node);
void generateIfStmt(ASTNode* node);
void generateWhileStmt(ASTNode* node);
void generateReturnStmt(ASTNode* node);
```

#### 控制流生成
```cpp
void generateCondition(ASTNode* node, const std::string& trueLabel, const std::string& falseLabel);
void generateShortCircuit(ASTNode* node, const std::string& trueLabel, const std::string& falseLabel);
```

## 示例

### 输入C代码
```c
int factorial(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

int main() {
    int x = 5;
    int result = factorial(x);
    return result;
}
```

### 生成的RISC-V汇编代码
```assembly
# RISC-V32 Assembly Code Generated by Compiler

# Data section
.data

# Text section
.text
.globl main

factorial:
# Function prologue
    addi sp, sp, -16
    sw ra, 12(sp)
    sw s0, 8(sp)
    addi s0, sp, 16

# if (n <= 1)
    lw x5, -4(s0)      # Load n
    addi x6, x0, 1     # Load 1
    slt x7, x6, x5     # n > 1
    xori x7, x7, 1     # n <= 1
    beqz x7, else_0

# return 1
    addi a0, x0, 1
    lw ra, 12(sp)
    lw s0, 8(sp)
    addi sp, sp, 16
    ret

else_0:
# return n * factorial(n - 1)
    lw x5, -4(s0)      # Load n
    addi x6, x0, 1     # Load 1
    sub x7, x5, x6     # n - 1
    
    # Save registers
    addi sp, sp, -32
    sw t0, 0(sp)
    sw t1, 4(sp)
    sw t2, 8(sp)
    sw t3, 12(sp)
    sw t4, 16(sp)
    sw t5, 20(sp)
    sw t6, 24(sp)
    sw a0, 28(sp)
    
    mv a0, x7          # Set parameter
    call factorial     # Call factorial
    
    # Restore registers
    lw t0, 0(sp)
    lw t1, 4(sp)
    lw t2, 8(sp)
    lw t3, 12(sp)
    lw t4, 16(sp)
    lw t5, 20(sp)
    lw t6, 24(sp)
    lw a0, 28(sp)
    addi sp, sp, 32
    
    mv x6, a0          # Get return value
    lw x5, -4(s0)      # Load n
    mul x7, x5, x6     # n * factorial(n-1)
    mv a0, x7          # Set return value
    
    lw ra, 12(sp)
    lw s0, 8(sp)
    addi sp, sp, 16
    ret

main:
# Function prologue
    addi sp, sp, -16
    sw ra, 12(sp)
    sw s0, 8(sp)
    addi s0, sp, 16

# int x = 5
    addi x5, x0, 5
    sw x5, -4(s0)

# int result = factorial(x)
    lw x5, -4(s0)      # Load x
    
    # Save registers
    addi sp, sp, -32
    sw t0, 0(sp)
    sw t1, 4(sp)
    sw t2, 8(sp)
    sw t3, 12(sp)
    sw t4, 16(sp)
    sw t5, 20(sp)
    sw t6, 24(sp)
    sw a0, 28(sp)
    
    mv a0, x5          # Set parameter
    call factorial     # Call factorial
    
    # Restore registers
    lw t0, 0(sp)
    lw t1, 4(sp)
    lw t2, 8(sp)
    lw t3, 12(sp)
    lw t4, 16(sp)
    lw t5, 20(sp)
    lw t6, 24(sp)
    lw a0, 28(sp)
    addi sp, sp, 32
    
    mv x5, a0          # Get return value
    sw x5, -8(s0)      # Store result

# return result
    lw x5, -8(s0)      # Load result
    mv a0, x5          # Set return value
    
    lw ra, 12(sp)
    lw s0, 8(sp)
    addi sp, sp, 16
    ret
```

## 优化策略

### 1. 常量折叠
在编译时计算常量表达式，减少运行时开销。

### 2. 公共子表达式消除
识别并重用相同的表达式计算结果。

### 3. 寄存器分配优化
使用图着色算法进行更高效的寄存器分配。

### 4. 死代码消除
移除永远不会执行的代码。

## 扩展功能

### 1. 支持更多数据类型
- `float`, `double`
- 数组和指针
- 结构体

### 2. 高级优化
- 循环优化
- 内联函数
- 尾递归优化

### 3. 调试支持
- 生成调试信息
- 符号表输出
- 错误定位

## 注意事项

1. **栈对齐**: RISC-V要求栈指针16字节对齐
2. **寄存器约定**: 遵循RISC-V调用约定
3. **内存管理**: 正确处理栈帧和局部变量
4. **错误处理**: 处理编译时错误和运行时异常

## 测试和验证

使用RISC-V模拟器（如QEMU、Spike）验证生成的汇编代码：

```bash
# 使用RISC-V GCC编译
riscv64-unknown-elf-gcc -o test test.s

# 使用QEMU运行
qemu-riscv64 test
```

这个代码生成器为你的编译器项目提供了完整的后端支持，能够生成高效的RISC-V汇编代码。