这里首先需要区分下树和图的遍历，只考虑dfs方式
树以二叉树为例子：dfs有pre-order，in-order，post-order。
图
只考虑有向图，一个start节点
拓扑排序考虑到图可能存在环，问题会有些复杂。
先考虑拓扑排序，有两种情况
DAG情况（无环），不断删除入度为0的节点或者用 reverse post order方式。
12345678图1: Entry / \ A B \ / Exit
pre-
...
2026.04.28
体系结构
计算机体系结构量化研究方法
编译器相关比较推荐的书
高级编译器设计与实现 (鲸书)
ssa based compiler design
深入理解llvm代码生成 (彭成寒等著)
LLVM Code Generation A deep dive into compiler backend development (Quentin Colombet)
编译器设计 (Engineering a Compiler)
https://gcc.godbolt.org/ h
...
2026.04.22
0
构建llvm-tblgen， cmake configure后 cd build && ninja llvm-tblgen
查看tblgen对某个td文件的实际命令：在build.ninja里面搜索。比如说 X86GenAsmMatcher.inc是怎么编译出来的.
12345678910# Custom command for lib\Target\X86\X86GenAsmMatcher.incbuild lib/Target/X86/X86GenA
...
2026.04.22
线程组织 grid，block，thread。 一个kernel启动的所有线程称为grid。block是调度单元。<<<网格大小，线程块大小>>>
实际硬件：GPU，SM （stream multiprocessor），SP。 SM： local register file + shared memory+L1 cache+ a number of functional units that perform computations
...
2026.04.13
学习下mlir
1. 基本概念
树形结构。Op，Region，Block，Op
使用基本块参数代替phi
Operand结构
操作
返回值：OpResult
regions
attrDict，属性字典
参数：OpOperand, 经典的Use结构
Value是ValueImpl*的包装，type+kind
Type, TypeStorage* 实际上是AbstractType* = {dialect, interface, typeid,name, subt
...
2026.04.13
以mac air构建为例，耗时26min。
123456789101112cmake -G Ninja \ -DCMAKE_EXPORT_COMPILE_COMMANDS=ON \ -S ./llvm -B build \ -DCMAKE_BUILD_TYPE=RELWITHDEBINFO \ -DLLVM_BUILD_EXAMPLES=ON \ -DLLVM_ENABLE_PROJECTS="mlir" \ -DLL
...
2026.04.13
参考 https://cs.wheaton.edu/~tvandrun/writings/cc04.pdf只考虑表达式，基于SSA
GVN是将Global value numbering，而PRE是Partial redundancy elimination。一个是值编号，一个是部分冗余消除。
GVN的思路简单，按照domtree进行深度优先遍历，记录每个block中表达式的编号，如果重复就删除重复的。对如下ir
12345678910111213141516define
...
2026.04.08
依赖的分析
value number
live range(liveness). 这块挺复杂的.
machine dom tree/machine loop
block frequency
value number
VNInfo 能处理ssa和non-ssa格式的mir
一个例子：
12345678910111213141516171819; llc %s -march=aarch64 --stop-after=register-coalescer declar
...
2026.03.22
greedygreedy以RegallocBase为基础。每个要被分配的虚拟寄存器有这几个阶段。
12345678enum LiveRangeStage { RS_New, // 初始状态 RS_Assign, // 尝试分配一个物理寄存器 RS_Split, // 分配失败，拆分生命周期来尝试分配 RS_Split2, // Split分配失败，再次拆分尝试分配 RS_Spill, // 分配失败，溢出到memor
...
2026.03.22
接上一篇。列举下RABasic需要的数据结构
LiveRegMatrix， LiveIntervals， VirtRegMap， LiveIntervalUnion
LiveIntervals
核心的查询接口。
VirtRegIntervals Map<reg, LiveIntervals>
RegMaskSlots 是用来储存哪些指令用了regmask（基本是call），在判断干涉时用到，按照slotindex排序
RegMaskBits，查询的ca
...
2026.03.22