Week 15
本周群聊
毕昇杯宣传
本周 LUG 某名成员结束了他的毕昇杯冲刺周, 这是他回答其它对毕昇杯感兴趣的同学的对话.
群友 A: 你好，打扰一下。昨天在群里看到你说参加毕昇杯找你。问一下是参加过竞赛的学长吗？我之前了解到一点计算机系统能力竞赛的信息，打算参加下一届毕昇杯，开学后开始备赛，可以咨询一下吗？
群友 B: 速来, 刚刚参加完
群友 A: 今年这一届吗
群友 B: 是
群友 A: 我是刚打完龙芯，准备接下来参加这个
群友 A: 问一下有啥备赛流程不
群友 B: 首先先慢慢找找队友, 然后直接开始写今年的就可以了. 就按着今年的要求开始写
群友 A: 看官网的技术方案是吗
群友 B: 对
群友 B: 你写过编译器吗
群友 A: 之前没有, 只是知道一点编译的大致流程
群友 B: 那可能得先看看学点什么, 各种编译器的教程是五花八门的
群友 A: 是的，现在就比较迷茫
群友 B: 而且大部分的结构都不能直接拿来用, 因为这比赛要做优化, 而大部分科普性质的编译器教程都是一趟过的, 没有给优化预留出空间
群友 B: 首先就是要选好 IR
群友 B: 转发聊天记录 1
群友 B: 一般来讲, 毕昇杯用的编译器, 至少都得是 C -> AST -> 某种IR -> 汇编 的, 这样才能在 IR 上做优化
群友 B: C -> AST 的过程要学什么视你的编译器用什么写, 用 Java 写就去看看 Antlr4, 用 C++/C 的话就去看看 bison 或者 antlr
群友 B: AST -> 某种IR 的难度取决于你用何种 IR 跟你的翻译方案, 我们队是用的类似 LLVM 的 IR
群友 B: 三地址IR 的话这一步翻译比较简单, LLVM IR + 所有变量翻译成内存操作难一点, 直接变量翻译成合格的ssa的话比较难
群友 B: 然后 ir -> 汇编这一步操作也是看 ir 形式
群友 B: 如果ir本身就是三地址，那只需要关注寄存器分配, 即多来一个箭头，无限寄存器 ir -> 有限寄存器 ir
群友 B: 如果 ir 是像 llvm 那种的, 那就还得处理一个 phi destruction, 有可能还得再多翻译一步, 把 ir 翻译为三地址的 low level ir, 再来进一步翻译
群友 A: 这些技术的话有具体的内容可以看吗, 目前还属于理论学习的阶段
群友 A: 应该是使用C/C++来实现
群友 B: 转发聊天记录 2
群友 B: 别整太多理论（
群友 B: 因为大部分教编译器理论的, 都是教怎么做编译器的编译器, 实际上写起来根本不用管
群友 B: IR 出来了之后，为数不多的需要理论指导的部分有
群友 B: 数据流分析, 图着色寄存器分配, 如果是llvm ir这种可能还需要一些支配信息构造跟phi相关的玩意
群友 B: 然后还有就是后端窥孔的模式, 如果做向量化的话也要很强的理论指导, 以及还要掌握比较细节的 armv7 汇编的限制 （如果你是负责后端部分的话）
群友 B: 除了这些之外感觉没什么理论是好学的了
群友 A: 我这种情况，备赛的话是先写一个demo还是直接上竞赛要求的啊
群友 B: 直接上就可以
群友 A: 这个是前后端都要写是吗
群友 B: 对, 要实现完整的一个 sysy 到 arm 汇编文本
群友 A: 前面提到的一些技术还比较陌生
群友 A: 只能算是入门
群友 B: 首先你需要想好用什么 IR, 明确跟理解了 IR 是什么就成功了一半
群友 B: 千万不要过多沉迷/害怕于各种前端技术跟SDT, 基本上对这个比赛跟写其他编译器没什么用, 什么 ll, lr 的略过就行, 直接点名龙书
群友 B: 还有 SDT, 就是那个什么语法驱动的翻译, 只有早期年代内存金贵才这样搞, 现在都可以直接用整颗 AST 遍历, 完全不用看, 而且限制很大, 不够灵活
群友 A: IR是指生成的机器无关代码吗
群友 B: 对
群友 B: 首先你要确定你用什么 IR, 它的内存形式是什么. 或者说你得定义好程序里叫 “IR” 的那个数据结构. IR 说白了, 就是一个特殊的, 用来表示源程序的数据结构, 重点在内存形式而不是文本形式. **点名批评 LLVM IR 的文本形式,
群友 A: 我之前看的是B站的本部的课，里面用的是三地址码？
群友 B: 是的
群友 A: 重点在数据结构的设计是吗
群友 B: 三地址 IR 是非常经典的 IR 设计, 特点就是有 “指令” 跟 “变量/位置/虚拟寄存器”. 写成代码就是类似这样的: struct Variable {...} 跟 struct Instruction { Variable def; vector<Variable> operands }. 然后靠在 Variable 上挂各种属性, 或者每个基本块维护一个 map<Variable, Info> 来分析信息, 做优化
群友 A: 这个有相关文章介绍吗
群友 B: 怎么说呢, 感觉没见过有直接写代码给你看的, 都是理论定义, 建议直接看上一年的队伍的, 我们学校今年另一个队就是用三地址的. 光看理论着实没啥用, 看完不会写代码还是不会写代码
群友 A: 噢，差点忘了有源码可以看
群友 B: 我们队有两个ir, 一个是 llvm 这种的, 另一个也是三地址这种的. 前面的用在优化, 后面的用在生成汇编 + 后端优化.
群友 B: llvm 这种 IR 就是基于图的, 写成代码就是 struct Instruction { vector<Instruction> operands }, 直接指令本身当作值, 没有变量的概念
群友 A: 这个可以使用多种吗, 还是说现在还没统一
群友 B: 你写代码会限制自己只使用一种数据结构吗 (
群友 B: IR 就是一个编译器里的参与比较广泛的数据结构而已, 不同的 IR 形式方便做不同的优化
群友 B: 只要你有空, 你大可以各种形式转来转去, 然后把每种形式上的优化都做彻底
群友 A: 噢，这样啊
群友 B: 优化就是算法, IR 就是数据结构, 好的数据结构出来了那就是一半的高效算法了
群友 A: 我得消化一下
群友 A: 问点其它的，这个竞赛是有队伍限制的是吗? 一般我们学校有多少队伍参加啊
群友 B: 我们学校比较少, 我们这届就俩, 2*3, 上一届貌似就一队; 反正都是一两队
群友 A: 确实, 感觉这种没有加分的就少人了
群友 B: 它这比赛是这样的, 初赛队伍数量不限制, 决赛队伍每校限制两队, 然后排不下的挤去外卡
群友 A: 还有外卡一说？
群友 B: 外卡奖跟决赛奖一样的, 但是无奖金, 而且证书上标外卡, 这个限制就是看你初赛的功能性样例
群友 B: 在我们学校的话, 你把功能都实现了, 优化不做应该都能进决赛
群友 A: 去年我们好多同学就是这么被忽悠进的龙芯杯
群友 B: 然后内外卡的奖都有华为校招的一个什么优待, 但是内卡的就突出一个奖金, 而且有面子 (
群友 A: 就冲着奖金来的（
群友 B: 而且显然外卡二等奖的队伍的编译器优于内卡三等奖, 被挤去外卡只能说是学校里牛人太多
群友 A: 话说队伍里大概咋分工合适捏
群友 B: 一般二人转, 一前一后, 一个人负责 sysy -> AST -> IR, 另一个人负责 IR -> (可能的LIR) -> 汇编. 然后前端的搞前端优化, 后端的搞后端优化. 要是多一个人的话, 可以考虑将一些构建跟运维的活给他, 或者让他做特定的优化, 比如来个人专职在后端搞向量化优化
群友 A: 工作量的话是差不多的吗
群友 B: 差不多的, 但是因为我是做前端的, 所以我觉得后端比较恐怖, 要处理一堆 arm 汇编的问题 (
群友 B: 代码量的话也差不多
群友 B: 我们这 Java 项目, 除开自动生成的代码大概 14k 行, IR 跟基础架构占 2k, AST -> IR 又是 2k, IR 上的优化是 3k 左右, 然后剩下的都是后端的. 后端的寄存器分配大概 1k-2k, 然后出汇编文本的 2k 多. 然后因为我们IR 用的 LLVM IR, 后端还有一个 LIR, 它的定义又是 1k-2k. 然后再加点杂七杂八的, 就差不多了, 然后还有 1k-2k 的 IR -> LIR
群友 A: 学校的进度控制怎么样呀, 我之前在龙芯杯的时候是参赛后每周有一个进度汇报
群友 B: 我们散养的, 学校不管的. 我们到 7 月 14 才把 AST -> IR 做完, 然后初赛结束前一周才做完功能性样例, 然后基本上大部分优化都是最后两三周卷
群友 A: 所以学校的支持也不是很多, 靠自己
群友 B: 学校 能给个实验室 (
群友 A: 那现在开始的话，时间应该挺充足的吧, 到明年7、8月，有十个月的时间
群友 B: 是的, 但是要充分考虑到前期起步特别慢的因素, 我高考结束就开始准备了, 但是真正有实质性进展还是报名了之后那段时间, 之前都不知道在哪花了时间
群友 B: 主要是之前花的时间都是在尝试把理论变成代码, 失败了很多, 后来上道了, 知道这理论怎么对上去了, 就可以哗啦啦输出了
群友 A: 可以直接取经, 那现在直接去看源码吗
群友 B: 可以去看, 但是看代码本身比较折磨. 你最好是选一个我校的, 然后找做那个项目的人先让他给你讲讲他们的项目.
群友 A: 感觉没有理论做基础还是有点虚
群友 B: 这个编译器它确实不像 os, 编译器的很多理论只有做编译编译器的人才要学, 就比如那一堆什么正则表达式lllr的玩意, 只要你不是写一个接受文法, 生成前端的程序, 那你直接会写文法用这种工具生成就可以了, 有个概念就行.
群友 B: 而且因为书是书, 特别是龙书, 非常理论. 它没有 target 到特定的 IR 上; 就算有, 这个 IR 的内存结构也非常不清晰. 你看看龙书里, 只有算法的伪代码, 没有数据结构的伪代码, 这就非常难受. 虎书好一点, 但是虎书的代码风格比较丑, 而且要么 C 要么 Java, 无 C++ 版
群友 A: 虎书里给的那些工具可用不, Flex啥的
群友 B: 前端生成器可以用, 也只能用词法/语法生成器, 支持 flex/bison/cups/antlr, 别的都不准 (
群友 A: 这个有官方提供的测试程序啥的吗? 我之前做龙芯的时候，有一个trace测试，可以在每个阶段测试功能正确
群友 B: 怎么说呢
群友 B: 没有
群友 B: 这种直接就能用的, 就是没有. 官方的是类似 OJ 一样的, 只有比赛的时候才开放, 而且错误也不全
群友 A: 那如何debug
群友 B: 自己写
群友 B: 自己做辅助的构建工具跟测试脚本跑官方的测试点
群友 B: 要不然为什么要一整个人来做这活 (). 我们是做了一个 python 脚本, 然后在 docker 里执行这个脚本, 用 qemu 跑
群友 B: 官方就会给一些, 比如说, test.sy, test.in, test.out 之类的文件
群友 B: 你用你的编译器读 test.sy, 编译出 test.s, 然后用 gcc-as (交叉编译)生成 (Armv7的) test.exe, 然后再在 qemu 里让 test.exe 读取 test.in, 然后输出 test.res, 然后比对 test.res 跟 test.out
群友 B: 然后 debug 的话一般就大眼观察法, 你对着 IR 比对一下 IR 有没有翻译错, 再用什么正经编译器编译一个 .s 文件对一下, 或者 gdb 调试 test.exe
群友 A: 就是测试文件啥的有吗?
群友 B: 各年的功能性跟性能样例都公布的, 每年都有一个 gitlab 仓库
群友 B: (资料) https://gitlab.eduxiji.net/nscscc
群友 B: (官网) https://compiler.educg.net/
群友 B: 你直接整个 git repo 拖下来, 然后整理整理就差不多了, 然后官网上应该也有一些说明什么的
群友 A: 好的, 最近先整理一下资料/信息啥的
群友 B: 我们学校带队老师主要是实验中心汪花梅老师, 可以先跟她接触一下
群友 A: 报名是在上半年开始还是秋季学期结束啊
群友 B: 五月中左右
群友 A: 但是学校公开招人应该是在编译原理实验课上吧
群友 B: 我还没见过
群友 B: 不知道, 没见过学校公开招人. 反正在学校的热度没有龙芯杯火
群友 A: 龙芯好像也是今年才火起来, 上一届参加的人比较多
群友 B: 组队的时候原本我认识的几个人都跑去龙芯了, 怨念颇深（
群友 A: 毕竟打着参加就能拿奖的牌子, 而且赛道比较多
转发的聊天记录 1
全都是群友 B 在讲
编译器它就是翻译器, 那视翻译前后的东西不同有不同的技术. 比如说大部分那种什么 “千行写编译器” 的项目, 都是直接 类c语言 -> 汇编. 这种翻译过程一般是一趟的, 源语言里有变量, 目标语言里也有变量, 而且源语言不需要运行时.
而像llvm, gcc那种, 是先把 类c语言 翻译成 某种中间表示 , 然后再把这种中间表示翻译成其他中间表示, 然后再翻译到汇编. 中间会有很多趟不同特性的 “语言” 到不同特性的 “语言” 的翻译过程. 比如有可能是 基于值的表示 (类似 LLVM IR, Graal IR(Sea of Node)) 那种, 有可能是 变量跟指令分开的 带无限寄存器的 三地址表示, 或者又有可能是有限寄存器的三地址, 又或者是基于栈的 (Java 字节码).
然后事实上源语言不同的话对编译技术的要求也有很大不同.
我理解的编译原理实际上就是各种语言/结构的转换函数的排列组合. 而编译原理是学什么的话要看你是怎么翻译, 翻译什么的:
- 直接的一趟的 C -> 汇编 是比较简单
- 我们学校的是 C -> AST -> 三地址 -> 有限寄存器三地址 -> 汇编
- 大部分教程都是 C -> AST -> 汇编, 然后所有变量都使用内存 load/store, 不翻译到有限寄存器去
基本上每一个箭头 (一趟翻译) 都可以看作一个比较独立的部分. 比如 C -> AST, 就有什么正则表达式, LL, LR 之类的可学, 然后 C 这种带变量的到三地址这种也有变量的就很简单. 如果 C 这种带变量的要到 LLVM IR 那种基于值的就比较难, 但是如果是纯函数式语言到 LLVM IR 就又比较简单, 简单和难取决于箭头前后语言的差别程度. 一般编译原理课程中关键的就是教, C -> AST 的前端, 然后 三地址 -> 有限寄存器三地址 的寄存器分配, 然后就是 三地址 -> 汇编 的指令选择部分这三个关键的箭头.
然后就是也有自己到自己的翻译, 这叫优化, 比如把三地址翻译成 (满足某种约束的) 三地址.
然后教程的话, 推荐 Crafting Interpreters
它由两部分组成, 源语言是一个带变量的, 动态类型的, 具有简单的函数调用跟循环控制流的语言, 带闭包, 带简单 OOP. 教程第一部分是介绍这个语言 -> AST 的部分, 手写了一个 LL 的 parser, 然后是一个解释器. 第二部分实现了一个 有限寄存器三地址代码 的 VM (就是它的解释器), 然后把这个语言翻译成 有限寄存器三地址代码. 第一部分跟第二部分的翻译部分是 Java 写的, 第二部分的 VM 是 C 写的. 有兴趣可以看看这个.
转发的聊天记录 2
群友 B: graal 最出名的, 还得是 SoN ir
群友 B: 说起 graal 那就是 graal ir，sea of nodes，稀疏分析经典
群友 B: 我现在的编译器里用的ir就是sea of nodes的变体, 跟llvm差不多, graal的更激进一点就是了
群友 D: 怎么说
群友 B: 传统的三地址ir是指令+操作数, type 指令 = (指令类型，[操作数]), 操作数是独立的东西，可以被不同指令用, 在不同的指令里有可能被杀死（定义/赋值）或者被使用. 这种ir的着重点在于“操作数”并不是表示值，而是表示某种位置一样的东西
群友 B: 但是当下的对ir的优化分析很多时候就是基于值的，你需要知道当到达这个指令的时候这个操作数的位置里是啥值, 这就需要一个到达定值分析. 那么，既然我们关注值，为什么不直接把ir做成只有值的形式呢？
群友 B: 一个显然的补丁是我们让每个变量都只能赋值一次, 这就得到了ssa的三地址ir
群友 B: 另一个做法是, 直接不要“操作数/变量”这个概念, 直接改用 type 指令 = (指令类型，[指令]), 让指令本身作为值变成指令的参数. 这样整个ir就是一个非常大的图结构, 没有循环的情况下就是一棵共用相同子节点的树, 有循环那就是普通的图
群友 B: graal ir就是这样一个定义. 它很明显是“ssa”的–因为ir里根本就没有“赋值”这个操作, 值就是值本身，不需要“赋给”什么“变量”，依附变量存在
群友 B: llvm ir是它还会把一堆的指令收集起来排好顺序组成线性的“基本块”, graal ir就直接拿节点煲汤, 全是散装的, 等到要生成汇编了再把这些“浮动着”的节点线性化, 所以叫 sea of nodes, 一个node就是一个指令, 散装指令直接散着放叫海洋（sea）
群友 C: sea of nodes 是怎么实现的？就是把所有指令都随便乱放吗？还是说有讲究？
群友 B: sea of nodes就是乱放. 因为它这个形式根本不强调什么“执行顺序”. 语言越强调“执行顺序”，那么它就越倾向于是“位置”的; 因为值不会随执行顺序而改变，但“位置的值”会.
群友 C: 乱放有什么好处呢？
群友 B: 乱放的好处就是做优化时不用考虑维护所谓“执行顺序”, 每一个优化都是严格局部的, 不需要像平时的三地址一样搞什么数据流分析，一次次全部遍历ir. 理论上sea of nodes的ir只需要说在自己附近获取些信息就可以了, 不需要一个全局的数据流分析之类的. 数据流分析本身也就是在模拟控制流的流转, 而一个完全基于值的语言是不需要控制流的. 这种分析又叫稀疏分析, 像数据流那种要按顺序遍历的叫密集分析. 而要是 SoN 像llvm ir那种既要做成基于值，又要时刻维护指令的顺序的, 就挺烦, 因为稀疏分析完成之后/完成之中还要时刻考虑这条指令的顺序有没有支配所有使用它的指令的顺序
群友 C: 大概懂了（
群友 B: 当然 SoN ir要到汇编的话还得先排好序, 毕竟汇编就是完全基于位置的语言了
群友 C: 就是在基本块里面分析优化，而不管基本块外面的?
群友 B: 准确来说是, 只需要引用我的和我引用的, 不需要“我附近/前后”的, 与什么控制流啊时间啊顺序无关, 只需要知道值和值的关系
群友 C: 大部分优化都是在分支上做的吗（
群友 C: 好像又不太懂了
群友 B: 啥叫在分支上做
群友 B: 优化也是分层抽象的，有机器无关优化（关注值和语义）跟有关优化（关注特定机器细节）.不同层次的优化适合在不同形式的ir上做, 比如机器有关优化在graal这种ir上做就很难做
群友 C: 按这篇里的说法大概是？我也不懂：https://darksi.de/d.sea-of-nodes/
万恶的前端依赖
是不是每个前端项目装依赖都会有 deprecated 跟 warning
恼了
搞不懂你们前端，太难了
众所周知，宇宙中质量最大的物质并不是黑洞，而是 node_modules/。
夕暮是什么意思
某群友还以为夕暮指的是早上和晚上。事实上，夕暮指的是黄昏捏。
夕暮れ • (yūgure)
evening twilight, evening when the sun goes down
参见：https://en.wiktionary.org/wiki/夕暮れ
游戏社团
由于群友们高频在 Telegram 群聊聊中玩 Gamee 小游戏，遂将群名从「HITsz LUG | 🏳️🌈」改为「HITsz LUG | 🏳️🌈🎮」
A: 不玩游戏没事干
B: A 来学数理逻辑
B: 很好玩的
B: 来看这本书
Git 的近似命令
有如下几条命令：
git pull
git fetch --all
git remote update
都有哪些区别呢？官方文档并没有说明清楚，可以参考 https://stackoverflow.com/questions/17712468/what-is-the-difference-between-git-remote-update-git-fetch-and-git-pull。
Rust 的若干种「引用范式」
报菜名：*mut T、*const T、Box<T>、Rc<T>、Arc<T>、Cell<T>、RefCell<T>、Cow<T>、String、Vec<T>、RawVec<T>、Unique<T>、Shared<T>。你学会了吗？（大雾）
原出处：《Rust in Action》
友链分享
如下： https://vaala.cat、https://blog.imakiseki.cf、https://blog.kquark.com、https://blog.origami404.top、https://blog.sorashu.tech、https://hopp.top、https://roy1994.top、https://huangblog.com。
某群友评价
blog.sorashu.tech：一眼 SUSTech。
Kwin 崩崩崩
实际测试多次发现，一个窗口启动超过一段时间后容易出现抖动、掉帧的 bug。已经在 Telegram、Haruka Player、VLC Player、MPV Player、Plasma、VS Code 上复现。
某群友建议抛弃 KDE Plasma，改用 Sway 自搭桌面环境。除了休眠有点不正常以外，Sway 非常地稳定，非常地新鲜。
Arch Linux 从折腾到随时准备放弃
某使用 Arch Linux 作生产力系统的群友在第 N 次遇到硬件不适配问题后实在忍无可忍，准备随时放弃 Wine 和 Windows 7 虚拟机直接投奔备用系统 Windows 11。其中最严重的问题是电脑机型过新导致每次都需要自行编译 Linux 内核才能使用电脑基带键盘和蓝牙，一旦更新后遇到问题还要再经过漫长的等待才能回滚到旧内核。
现在劝润 Linux 都要提前打听对方的电脑什么时候发售的。
这就是精英教育
某群友发明了「精英教育不等式」：
那没办法啊，人家和国际一流教育接轨，花5000块享受几万刀的教育，属实赢麻。
USTC 坏，每年招 1700 壬，还不给安徽照顾。
全国人民的 USTC！比清北好。
这就是精英教育！
5000 CNY > 30000 USD
本周旧闻慢递
AMD 船新胶水 CPU
草，这个大小有点哈人。
参见：https://www.cnbeta.com/articles/tech/1290773.htm
本周看了啥
Hexspeak
相关冷知识：0xFEE1DEAD 是 Linux 中的 reboot system call。
参见：https://en.wikipedia.org/wiki/Hexspeak
反人类交互设计网站
反向 UI/UX！
看了一眼那个设计师低血压良药。
CTF 入门索引
参见：https://wiki.vaa.la/share/02984f34-8c4c-4c01-a29d-e0aeed41fe1d
群主看了啥
- VIPT L1 Cache 继续增大时解决重名的办法 Why the big L1 Cache is so hard
- 上面文章大佬的龙芯杯工作开源: GitHub
- 群主的: 龙芯杯参赛总结
本周音乐推荐
- 作品名：Mozart Violin Concerto No.3
- 艺术家：Mozart
- 发行时间：1962
- 专辑流派：古典-古典主义时期
- 收听链接：IMSLP