2025-北航编译技术优化文章
对于优化，主要分为两个阶段的优化：中端和后端。中端对中间代码先进行优化，随后由后端生成目标代码，再由后端优化代码进行进一步的优化。 核心的优化工作主要集中在以下三个方面： mem2reg：将内存变量提升为 SSA 寄存器形式，减少 load/store 指令。 removePhi：将 Phi 指令转化为 Move 指令，以便后端 MIPS 翻译。 regAlloc：使用图着色算法进行寄存器分配。 此外，为了支撑这些核心优化，还实现了一些基础的 Pass，如死代码删除、CFG 构建、支配关系分析等。 中端优化中端优化即机器无关优化，主要针对 LLVM IR 进行处理。 死代码删除死代码删除分为两层：删除不可达基本块和删除无用指令。 删不可达基本块SurplusBlock 的实现基于图的可达性分析：从入口块出发进行 DFS，标记所有可达的块，最后将未被标记的块从函数中移除。同时，还需要清理跳转指令之后的无用指令。 1234567891011121314// 从入口块开始DFSvisited = new...
2025-北航编译技术实验文法定义及相关说明
知识产权声明：以下内容由北航编译技术课程组提供，并非本人创作，本人只负责搬运，有任何问题请以课程组为准！！！ 2025编译技术实验文法定义及相关说明一、概要SysY 语言是编译技术实验所完成的编译器的源语言，是 C 语言的一个子集。一个 SysY 语言源程序文件中有且仅有一个名为 main 的主函数定义，除此之外包含若干全局变量声明、常量声明和其他函数定义。SysY 语言支持 32 位有符号数 int 类型及其的一维数组类型；const 修饰符用于声明常量。 SysY 语言本身没有提供输入/输出(I/O)的语言构造，I/O 是以运行时库方式提供，库函数可以在 SysY 程序中的函数内调用。部分 SysY 运行时库函数的参数类型会超出 SysY 支持的数据类型，如可以为字符串。SysY 编译器需要能处理这种情况，将 SysY 程序中这样的参数正确地传递给 SysY 运行时库。 函数：函数可以带参数也可以不带参数，参数的类型可以是 int 或其一维数组类型；函数可以返回 int 类型的值，或者不返回值（即声明为 void 类型）。当参数为 int...
2025 北航编译原理期中期末题目回顾
本文章主要记录了2025秋季学期北航编译原理课程实验上机期中期末的回忆题目~ 题目均由本人回忆记录，可能与原题稍有偏差，但大体思路一致 期中题目1. 新增 elif 文法：具体新增文法如下： 123Stmt -> 'if' '(' Cond ')'Stmt { 'elif' '(' Cond ')' Stmt } 1.有elif 2.无elif 3.有多个elif [ 'else' Stmt ] // 1.有else 2.无else 解题思路： 词法分析阶段识别 elif 为一个保留关键字，建立 ELIFTK。 语法分析阶段，对于 IfStmt 语法结构，新增一个 list 用来装 elif，里面每一个单元涵盖 Cond 和 Stmt。在 toString 的时候，先对 if 语句进行 toString，然后看有没有 elif，如果有的话就仿照 if 的 toString 操作去写就可以。最后对...
LLM MoE RL 学习报告
LLM MoE RL 学习报告第一部分 深入理解 LLM MoE 的路由器机制1. 路由器的训练机制 路由器通常是一个怎样的网络结构？在 MoE 架构中，一部分 Decoder Layer 把原来的 FFN Layer 被替换为了 MoE Layer。MoE Layer 通常由一个路由器和多个专家组成。 路由器是一个前馈神经网络，通常有两种网络结构： 一层线性层 + softmax ：词向量经过 attention 层和残差归一化后，进入路由器，假设每个输入 Token 的维度是 d_model，路由器下游有 N 个专家，那么路由器就做了一个 d_model -> N 的线性映射。之后再对维度为 N 的结果进行 softmax，每个维度分别对应该 Token 与每个专家的匹配度或权重。 用公式表示为，路由器内部有一个 d_model * N 大小的权重矩阵 W。输入 x 先与 W 进行矩阵乘法，得到 logits。$$logits = x * W$$之后再进行 softmax 得到最后的概率。$$probabilities =...
北航操作系统-OS-lab6-实验报告
1. 思考题想让父进程作为读者，只需要反过来操作就可以了。先关闭写，再进行读操作，最后关闭读并退出即可。代码如下： 123456default: close(fildes[1]); read(fildes[0], buf, 100); printf("father-process read:%s", buf); close(fildes[0]); exit(EXIT_SUCCESS); dup...
北航操作系统-OS-lab5-实验报告
1. 思考题 使用kseg0去读写设备，会导致读取的数据可能不正确。因为kseg0段使用cache来访存，当CPU访问一个物理地址时，会先检查该地址所在块是否在cache中，如果在那么直接从cache中进行读或写，如果不在那么申请一块并从内存中读取该块的内容到cache中，并重新访问。这样做之所以可行是因为对cache中的块的数据进行操作等效于对内存直接操作。但是如果外设对内存的操作不会引起cache的变化，如果外设对内存中的数据进行了修改，那么cache中对应块没有随之修改，这就会导致cache中的块的数据和内存中块数据不一致，导致CPU访问的时候读取到了错误的数据。同理CPU的写入也会先写进cache，之后再回写到内存中，这样会导致外设有可能读不到CPU写入的数据。 一个磁盘块的大小是4KB，也就是4096字节；而一个文件控制块FCB的大小固定为256字节，因此一个磁盘块中最多能存储16个文件控制块。一个目录最多拥有1024个磁盘块，因此最多能有16384个文件。我们文件系统支持单个文件最多拥有1024个磁盘块，也就是4MB。 缓冲区的范围是 [DISKMAP,...
北航操作系统-OS-lab4-实验报告
1. 思考题 内核在保存现场的时候，通过 SAVE_ALL 宏操作，来将通用寄存器中的值保存在内核栈指针所指向的位置，在异常处理结束时恢复现场，从而防止通用寄存器的值被破坏改变。 可以从当时的 $a0 - $a3 寄存器中得到用户调用 msyscall 时传入的参数。因为在系统调用的时候，这几个寄存器的值不会被改变，因此可以直接获取。 方式就是让sys开头的函数通过正常获取参数的方式，能够获取正确的参数。而这样做的保证是，在用户调用syscall相关函数后，会进行传参，此时会在$a0 - $a3寄存器中保存值，并在用户栈中开辟栈帧，存入相关参数。之后调用msyscall函数，这个函数是个页函数，因此没有栈帧，不会改变栈指针的位置，这个函数直接调用了syscall，陷入了内核态，因此此时 $a0 - $a3...
北航操作系统-OS-lab3-实验报告
1. 思考题 首先，MIPS中的虚拟内存结构如下： 因此，base_pgdir中建立了pages和envs的物理地址与虚存中pages和envs的虚拟地址之间的关系，这也同样解释了在map_segment中传入的UPAGES和UENVS的含义，就是pages和envs的虚存首地址。 之后，由于MOS的内核数据共享机制，需要把UTOP以上UVPT以下，即pages和envs的数据暴露给用户空间，因为base_pgdir中已经有分配好的映射关系，因此需要把UTOP到UVPT所对应的页目录项赋值给每个进程的页目录。又由于用户自身的4MB页表放置在UVPT，因此页目录自映射项相对于页目录的偏移即为PDX(UVPT)，因此需要把e->env_pgdir[PDX(UVPT)] = PADDR(e->env_pgdir) |...
北航操作系统-OS-lab2-实验报告
1. 思考题 在编写的 C 程序中，指针变量中存储的地址被视为虚拟地址，MIPS 汇编程序中 lw 和 sw 指令使用的地址也被视为虚拟地址。CPU访问的都是虚拟地址，通过MMU来转换成对应的物理地址，最后访问内存中的数据。 首先，用宏来处理链表可以化简链表的操作，通过将特定功能的代码封装在宏定义中，可以在实现特定功能时简化操作，增加代码可读性和可维护性。其次，当链表的操作需要修改时，由于该操作会被大量复用，如果逐一修改工作量太大，而用宏则可以只修改宏定义，方便更改。最后，很多种类的链表都包含相似的操作，只要这些链表结构相同，就都可以用这些宏定义来实现相似的操作，只是传入的参数不同，方便了众多链表的使用。 在实验环境中，有单向链表、双向链表、单向队列、双向队列、循环队列。 ...