LLVM IR 中端 Pass 的设计目标与运行原理
“Ever tried. Ever failed. No matter. Try again. Fail again. Fail better.”
“试过。失败过。没关系。再试一次。再失败一次。失败得好一点。”
（Samuel Beckett《Worstward Ho》）
“9 月 13 日”
凌晨一点零五分。
末班电车在零点二十八分开走了。
站台上只剩一盏灯还亮着，另一盏在闪。
我数到第七次的时候，它灭了。
便利店在坡道下面，玻璃门开着一条缝。
冷气从缝里漏出来。
九月中旬的冷气，已经有点不像夏天了。
我买了一罐热的玉米汤。
一百五十八円。
收据从打印机里慢慢吐出来，还带着一点温度。
我把它翻过来。
背面是空的。
收银台旁边有一支拴着绳子的铅笔，是给填彩票的人用的。
我借了它，在收据背面画了三栏。
第一栏写「要做的」。
第二栏写「在做的」。
第三栏写「做完了」。
水科：「你又在搞这种没用的仪式……」
我：「不，此有用……」
水科：「哪里有用」
我：「写下来的话，就不会忘掉」
水科：「热敏纸三个月就白了」
我：「……」
水科：「你的铅笔字倒还在」
啊。
原来是这个意思。
我把收据折了一下，塞进外套口袋。
罐子很烫，我换了三次手。
坡道上面有人走过来。
步子很轻，几乎听不见。
三日月：「呵呵」
三日月：「末班车，已经没有了」
我：「嗯，我知道」
三日月：「那，还站在这里」
我：「∵汤还没喝完……」
她没有再问。
她站在自动贩卖机旁边，看着那排亮着的按钮。
看了很久。
风从坡道下面上来，把她的头发吹到一边。
我偶尔会思考这种事情。
比如，一份清单要写到多少行，才算写完。
比如，划掉一行，和从来没有写过那一行，是不是同一件事。
比如，热敏纸上的字淡掉的时候，是谁把它擦掉的。
……啊哈哈，想太多了。
汤本来就该凉。
我把它喝完，罐子扔进回收箱，发出一声很轻的响。
水科：「回去」
我：「回去干什么」
水科：「你不是要写清单吗……」
我摸了摸口袋。
收据还在。
第一章 The List 「清单」
“9 月 13 日”
水科住在一楼，窗户正对着坡道。
从她的窗户看出去，能看见水塔的影子压在两排屋顶上。
影子在凌晨的时候会变短，因为她房间的灯比外面亮。
桌上有三台显示器，其中两台是黑的。
亮着的那台上面全是字。
蝉还在叫
水科：「坐」
我：「地上……？」
水科：「地上」
我坐下了。
地板凉。
九月中旬的地板，已经不完全是夏天的温度了。
我把收据掏出来，摊在膝盖上，背面朝上。
三栏。
第一栏还空着。
水科：「你那是什么」
我：「清单」
水科：「给谁看」
我：「给我自己看」
水科：「超一千倍蠢」
我：「……」
水科：「不过正好」
她把亮着的那台显示器转过来一点。
上面是一行命令，还有一长串输出。
水科：「clang -O2，前端把 C++ 翻成 LLVM IR……」
水科：「后还有一长串 pass，一个接一个作用在这份 IR 上……」
我：「一长串是多长？」
水科：「自己数」
我：「数不完……」
水科：「那就别数」
我：「那、」
水科：「你以为清单上有一百个条目，就有一百个算法？」
我：「不是吗？」
水科：「不是」
水科：「真正独立的算法，数量有限……」
我：「重复调用？」
水科：「同一个 InstCombine，一条 -O2 的路径上出现四次」
我：「四次？」
水科：「同一个 SimplifyCFG，也是四次……」
我：「那不就等于没做完吗……」
水科：「对」
她笑了一下。
不，她没有笑。
只是嘴角动了半毫米，又回去了。
我：「正确性依据？」
水科：「就是——凭什么这么改是对的……」
我：「哦」
水科：「别哦」
我：「只能这样？」
水科：「你读下去会发现，它们的论证反复用的只有几句」
她伸手过来，用铅笔的另一头在收据第一栏点了四下。
四个小坑。
水科：「第一句……」
水科：「此值只有一个定义」
我：「所以？」
水科：「故沿一条 use 边，就能取到它……」
水科：「第二句……」
水科：「第三句……」
水科：「第四句……」
我：「四句」
水科：「四句」
我：「剩下的呢？」
水科：「剩下全是这四句，在不同 pass 上的实例化……」
风。
窗外坡道上有一辆自行车经过，链条响了两下，就远了。
我：「那为什么要排成一串？」
水科：「问得好」
我：「故清单本身就是答案……」
水科：「清单本身就是答案」
她在第三栏上面画了一条横线，把三栏变成了四栏。
第四栏没有标题。
我：「这栏写什么？」
水科：「写已经过期的……」
我：「过期？」
水科：「IR 一改，前面算的东西就作废了……」
我：「那不就白算了吗……」
水科：「白算是常态」
我：「鞋带松了」
热敏纸上的字会淡。
铅笔的字不会。
清单空了，才算做完。
可是清单从来没有空过。
我把这四句在心里念了一遍，发现它其实是在说收据。
不对。
收据不会说话。
是我们在替它说话。
“9 月 13 日”
水科：「先看骨架」
她敲了一行命令，输出被折成一个树。
1 | buildPerModuleDefaultPipeline(O2) :1753 |
我：「即目录？」
水科：「PassBuilderPipelines.cpp，第 1753 行……」
我：「1753」
水科：「模块简化在 1113，模块优化在 1508……」
我：「为什么？」
水科：「逐函数简化在 620」
我：「你背得下来？」
水科：「我 grep 过」
我：「啊哈哈，那也算」
水科：「不算」
我：「贩卖机又吞钱了」
她清了清嗓子。
然后用一种我从没听过的、像外国播报员的腔调，开始念。
水科：「S！R！O！A！」
水科：「Early！C！S！E！」
水科：「Jump Threading！」
我：「便当凉了呢」
水科：「Simplify CFG！」
我：「等一下……」
我：「完全听不懂」
水科：「继续」
水科：「Instruction Combining！」
水科：「Reassociate！」
我：「停停停」
水科：「……」
我：「翻译，翻译」
水科：「能提升的，提成 SSA 值……」
我：「EarlyCSE 呢？」
我：「JT？」
水科：「JumpThreading」
我：「CVP？」
水科：「CorrelatedValuePropagation……」
我：「GVN？」
水科：「据此消除跨块重复计算……」
我：「SCCP？」
水科：「IPSCCP 是它的跨过程版本……」
我：「LICM？」
水科：「循环不变量外提……」
我：「BDCE、ADCE、DSE？」
水科：「三种死代码判据」
我：「SCEV？」
水科：「写成关于迭代次数的闭式……」
我：「LAA、TLI、BFI、BPA？」
水科：「块频度、边概率」
我：「NPM、LPM、CGSCC？」
水科：「调用图按强连通分量分层遍历……」
我：「PGO、LTO、VF？」
水科：「用真实运行计数指导优化、链接期优化、向量宽度……」
我：「ConstraintElim？」
水科：「折掉可证恒真、可证恒假的检查……」
我：「还有一个吧，该名字很长的……」
水科：「CalledValuePropagation……」
我：「缩写呢？」
水科：「没有缩写」
我：「硬币卡住了」
水科：「它的缩写会和 CVP 撞车」
我：「嗯、」
水科：「不是哦」
水科：「记住」
我：「记住了……」
她停了一下。
水科：「还有一批不属于任何 pass 的词……」
我：「也要背？」
水科：「要」
我：「啊哈哈，队好长」
水科：「IR，中间表示……」
水科：「本文特指 LLVM IR……」
水科：「pass，流水线上的一道工序」
罐子空了
水科：「产出改写后的 IR，或新的结论……」
我：「SSA？」
水科：「select 是按条件在两个值里挑一个的指令」
我：「这句我记住了……」
我：「∵听起来很惨……」
水科：「哪里惨？」
我：「两个都已经算完了，却只能用其中一个……」
水科：「……」
水科：「CFG 是控制流图，基本块为节点、跳转为边……」
鞋带又松了
水科：「DAG 是有向无环图……」
硬币卡在找零口
水科：「UB，未定义行为……」
我：「poison 呢？」
水科：「LLVM 的一种值」
水科：「但送进分支条件、除数、访存地址，即 UB……」
水科：「同一个 poison，允许对应多种取值……」
我：「多种取值？」
水科：「故语义是个关系，不是函数……」
我：「此后面会用到吗？」
水科：「会」
水科：「AA，别名分析……」
水科：「NoAlias、PartialAlias、MustAlias、MayAlias……」
我：「mem2reg？」
水科：「PromoteMemoryToRegister……」
我：「那是什么？」
水科：「RAUW 是 replaceAllUsesWith……」
我：「alloca？」
水科：「在函数栈帧上分配一块内存的指令」
我：「intrinsic？」
水科：「比如 llvm.memset，比如 llvm.assume……」
我：「GEP？」
水科：「getelementptr，地址计算指令」
我：「trip count？」
水科：「EC 是 exit count，退出前已经完成的迭代次数……」
我：「哪里不一样？」
水科：「转 n 次的循环，退出计数是 n」
水科：「差一」
我：「好处是什么？」
水科：「hoist 是把指令搬到必经的、或次数更少的支配点……」
水科：「sink 是反向，搬到汇合点或低频块……」
水科：「lane 是向量里的一个元素位置……」
我：「那是什么意思？」
水科：「splat 是把同一个标量填满整个向量」
水科：「reduction 是把一串值归约成一个值的运算……」
我：「vtable？」
水科：「虚函数表」
我：「bitcode？」
水科：「LLVM 的序列化 IR 文件……」
我：「Semi-NCA？」
水科：「求支配树的一种算法……」
我：「clobbering access？」
水科：「MemorySSA 里」
我：「罐子空了呢」
水科：「是判断一个 load 是否仍然有效的依据……」
我：「仍然有效……」
水科：「嗯」
我：「故是有保质期的……」
水科：「故是有保质期的……」
她把铅笔从桌上拿起来，在收据第二栏写了一个字。
读。
我：「那是谁的栏？」
水科：「现在是它的了……」
三日月不知道什么时候进来了。
她坐在窗台上，脚悬着，没有穿鞋。
她什么也没说。
水科：「四块定义是从外面借来的……」
水科：「DFS 序列与括号序列」
我：「谁写它？」
水科：「DFS 生成树的四类边，与 SCC 缩点」
水科：「都在 oi-wiki 上，写好了」
我：「电车要来了」
水科：「那就是 worklist 最朴素的形式……」
我：「梅干在正中间」
水科：「DFS 那一页写了」
水科：「每个子树，都对应 DFS 序列中的连续一段」
我：「就这样？」
水科：「Tarjan 缩点后得到 DAG……」
我：「故这四页就是地基」
水科：「地基」
水科：「格上的 worklist 不动点……」
我：「三组？」
水科：「一个记号，只在被定义后才使用……」
我：「万一须提前用呢？」
我：「举个例子？」
我：「听起来像是有人被坑过……」
水科：「被坑过的人，都这么写」
第二章 Refinement 「什么才算改对了」
“9 月 13 日”
水科：「定义 0.2，精化关系……」
我：「精化？」
水科：「得先把事件序列这四个字拆开」
我：「有区别吗？」
水科：「终态相同，中间却多了一次对外调用……」
窗外有一声蝉。
只有一声。
九月的蝉，已经不知道该不该叫了。
水科：「定义 0.1，可观测语义」
水科：「给一个 Function 一份输入 σ……」
便当凉了
水科：「还有运行期才定的 load 结果……」
我：「意思是？」
水科：「O(P,σ) ⊆ Trace ∪ {⊥} ∪ {↑}」
水科：「⊥ 是这次执行触发了 UB，↑ 是不终止」
我：「不终止也算结局？」
我：「那 O 是函数吗？」
水科：「poison 让同一个 σ 允许多条合法 trace，这是引 0.4……」
水科：「即推论 1.6 该方向性的源头」
我：「哪个方向性？」
水科：「定义 0.1a，事件字母表与 trace……」
水科：「Trace = E* ∪ E^ω，序列次序就是执行次序……」
水科：「E 只有四类……」
我：「是、」
水科：「W(a,v)，对可观测地址的普通写……」
贩卖机又吞钱了
水科：「C(f,v̄)，不透明 call」
水科：「V(a,d)，volatile 或 atomic 的访存」
水科：「R(v)，对外的 return……」
我：「不透明 call 是哪些？」
水科：「外部函数、inline asm、任何 callee 未知的调用……」
水科：「callee body 已知时，这一对 call 和 ret 不是事件……」
水科：「它贡献的是自己 body 里的事件」
水科：「volatile 的读也算，每一次都是一个事件」
风把收据吹到栅栏上
水科：「return 只在函数对外可见或地址逃逸时算……」
我：「那什么不是事件？」
水科：「普通 load 不是，读只改变后续事件的因果链……」
水科：「纯算术、比较、phi、select、地址计算，都不是……」
水科：「写未逃逸的 alloca 不是，写不出模块的 internal 全局也不是」
我：「未逃逸」
水科：「地址不可观测，私有性见 T5 引 5.4」
水科：「只有它导致的 W/C/V/R 的差异才可观测……」
水科：「模块内已知 body 的 call 和 ret 那一对也不是……」
我不懂，但我记住了行号。
水科：「内联前后事件逐条对应，Inliner 那条证明会用到……」
我：「故次序到底有没有关系？」
水科：「两个不透明 call 之间一律保序……」
我：「为什么最后一类最狠？」
水科：「无法排除 callee 读写同一个位置」
水科：「第二条的精确化就是定义 0.1b，写的可观测粒度」
水科：「对非 volatile、非 atomic 的普通写……」
我：「观测点有哪几种？」
水科：「OP1，任何可能读到该地址的读……」
水科：「OP2，任何不透明 call」
水科：「OP3，函数返回、线程结束、程序终止」
我：「判据呢？」
水科：「两次写之间若不存在观测点，前一次写不进任何 trace……」
电车门关得比我想的快
水科：「W(a,v) 被记进 trace，⟺存在一个观测点……」
水科：「在它前，a 的最近一次写就是这次」
我：「谁的错？」
水科：「故 DSE 家族从不碰 volatile 与 atomic」
我：「从不？」
水科：「从不」
她在收据第二栏下面写了一行小字。
我凑过去看。
写的是「中间没有人看见」。
“9 月 13 日”
水科：「举个例子，σ 给定 @sink 的内容与 %out 的指向……」
1 | @sink = global i32 0 ; 外部可见 ⇒ 可观测 |
我：「trace 是什么？」
水科：「⟨W1, C1, W2, R⟩……」
水科：「W0 不在里面……」
我：「那 C1 后的写呢？」
水科：「不能随便删，C1 是观测点……」
水科：「log 可能通过任何途径看见 %out」
我：「怎么验证呢？」
水科：「要严格删，就得让 AA 证明此 callee 不读 %out……」
我：「蝉还在叫啊」
水科：「即 DSE 须依赖 AA 结论与函数属性的原因……」
我：「若把 C1 换成一条纯算术呢？」
水科：「W1 与 W2 之间就没有观测点了吗……」
水科：「有」
水科：「W2 写的是另一个地址」
水科：「W1 的观测点是 OP3，return 时 %out 可被 caller 看见」
水科：「故 W1 仍在 trace 里……」
我：「这句我要抄下来……」
水科：「抄在热敏纸上？」
我：「抄在背面」
水科：「……随你」
水科：「出处」
我：「啊、」
水科：「原始口径是 C++ 标准的 as-if rule，intro.execution」
我：「好处是什么？」
水科：「最少要求那段，就是 W/C/V/R 的来源……」
水科：「工程编码是 MemoryEffects，ModRef.h:9，:78」
水科：「MemoryEffectsBase……」
水科：「Instruction.h:887 mayHaveSideEffects()……」
我：「那、那个」
水科：「:827 mayReadOrWriteMemory()……」
水科：「unknown():123，none():128」
我：「哪一条？」
水科：「readOnly():133，writeOnly():138」
水科：「argMemOnly():143」
我：「在哪一行呢？」
水科：「还有 MemoryLocation.h:217……」
水科：「不过定义 0.1、0.1a、0.1b 是本文的记账口径……」
水科：「不是 LLVM 的规范文本……」
我：「为什么特别声明？」
“9 月 13 日”
水科：「定义 0.2，精化」
水科：「P’ ⊑ P，⟺：对一切 σ」
坡道上滑了一下
水科：「要么 ⊥∈O(P,σ)，要么 O(P’,σ) ⊆ O(P,σ)……」
我：「一句话？」
水科：「在旧程序有定义的输入上……」
我：「哪三件？」
水科：「(i) 不许造出新 trace，含把不终止变成终止……」
水科：「(ii) 不许把不 UB 的输入变 UB……」
水科：「(iii) 不许把会停的输入变不停……」
我：「会不会重？」
水科：「都写在 ⊥∉O(P,σ) 的前提下……」
我：「那它没有要求什么？」
水科：「UB 的执行没有行为须保护，这是引 0.5」
水科：「定义开头那条前提把它接住……」
水科：「LoopDeletion 删无副作用的循环……」
笔记上没有这一行。
我：「只能这样？」
水科：「除非 mustprogress 属性明确授权」
水科：「分界就在 (iii)」
水科：「↑ 那一支的语言依据是 intro.progress……」
我：「引 0.3 呢？」
水科：「流水线的正确性≡每个 pass 各自满足 ⊑」
水科：「P0 ⪰ P1 ⪰ …… ⪰ Pn，则 P0 ⪰ Pn……」
我：「证明多长？」
水科：「一行，关系包含的传递性」
我：「一行！」
水科：「嫌短？」
我：「不是，是羡慕」
水科：「这条说明 NPM 为什么只要求每个 pass 各自证明局部正确……」
我：「谁来做呢？」
水科：「任何一个 pass 的声明不成立……」
水科：「末章的 preserve 契约会再次出现同一结构……」
我：「又是这种结构」
水科：「到处都是这种结构」
我：「引 0.4？」
水科：「poison 可任意替换……」
我：「什么条件呢？」
水科：「若 v 在某执行中为 poison……」
水科：「把 v 换成任意同类型值 c，仍满足 0.2」
我：「鞋带松了」
水科：「poison 的消费者只有两种下场」
水科：「c 那条 trace 本就在 O(P,σ) 里，(i) 成立……」
水科：「或送进 UB 位置——br 条件、除数、访存地址、noundef 参数……」
水科：「此时 ⊥∈O(P,σ)，前提不成立，无任何义务……」
数到第十二级就乱了
水科：「配套的指令是 freeze」
我：「引 0.5？」
水科：「UB 分支可剪」
我：「真的？」
水科：「若块 B 的一切执行都触发 UB……」
水科：「删掉全进入 B 的边，保持 0.2……」
我：「嗯、嗯、」
水科：「B 以 unreachable 终结，或 B 只在 nsw 溢出时可达……」
水科：「证明分两种 σ……」
水科：「经 B 的那些，⊥∈O，义务解除」
水科：「不经 B 的那些，删边不影响任何执行，O 逐点相同……」
我：「谁在用？」
水科：「SCCP 剪不可达边，JumpThreading 改道……」
我：「为什么？」
水科：「CVP 折分支，LoopDeletion 删迭代次数为零的循环……」
水科：「SCCPSolver.cpp:796 markEdgeExecutable，:1280」
水科：「删边前先查副作用，JumpThreading.cpp:418」
我：「引 0.6？」
水科：「标志即可证明的前提……」
水科：「add nsw 的语义是……」
水科：「和在 [-2^31, 2^31-1] 里就取该和，否则是 poison……」
我：「换句话说？」
水科：「(a) 消费——带着 nsw 的改写免费拿到那条不等式」
水科：「(b) 生产——想加 nsw 须先证明该不等式……」
我：「有哪几种？」
水科：「nuw、exact、nneg、fast-math flag，同理……」
我：「消费者？」
水科：「CVP，把 nsw 证明出来再写进指令……」
水科：「Reassociate，重排前先检查链上有没有标志」
水科：「IndVarSimplify，扩宽以避免回绕」
水科：「SCEV，hasNoUnsignedWrap 一族……」
水科：「FullUnroll 与 Vectorize，复制 body 时不得凭空造标志……」
水科：「原文在 LangRef 的 add 与 Fast-Math Flags 两节……」
水科：「消费端 ScalarEvolutionExpressions.h:217、:221……」
水科：「生产端 CorrelatedValuePropagation.cpp」
我：「引 0.7？」
水科：「若指令 i 无副作用，且在任何输入下都不会成为 ⊥ 的源……」
水科：「则把它搬到任何支配其全部 use 的位置执行，仍满足 0.2……」
水科：「证明：至多在本来不执行 i 的路径上多算一个不被观测的值」
三日月：「都写着」
水科：「ValueTracking.cpp:7499」
水科：「isSafeToSpeculativelyExecute()……」
水科：「主要调用方 MergedLoadStoreMotion.cpp:11……」
背面已经写满了。
水科：「文件头写的就是 diamond 与 hammock 上的 hoist 和 sink……」
我：「还有别的吗？」
水科：「还有 SpeculativeExecution.cpp:9、LICM.cpp:192」
水科：「AllowSpeculation」
我：「手好冰」
水科：「SpeculativeExecution、MergedLoadStoreMotion」
水科：「GVNHoist、LICM、LoopSink、SimplifyCFG 的 hoist……」
我：「七条引理，管住全部改写……」
水科：「七条，加一个定义……」
三日月还坐在窗台上。
她一直没有出声。
三日月：「呵呵」
三日月：「假设 1」
三日月：「清单上的每一行，被划掉的次数有上限……」
我：「上限是什么？」
三日月：「格的高度」
三日月：「假设 2」
三日月：「只朝一个方向变的话，它一定会停……」
水科：「定义 1.1……」
水科：「(L,⊑) 完备格，f:L→L 单调……」
我：「为什么反过来约定？」
水科：「LLVM 里现成的格有好几个……」
水科：「ValueLattice.h:27，:236 getOverdefined……」
我：「overdefined」
水科：「AliasAnalysis.cpp:126 四值别名格……」
我：「就这样？」
水科：「DemandedBits.h:41 位集合格」
我：「定理 1.2？」
水科：「lfp(f) = ⊓{x | f(x) ⊑ x}，存在……」
水科：「若 L 高度有限，即升链条件……」
水科：「lfp(f) = ⊔ fⁿ(⊥)，且 fʰ(⊥)=fʰ⁺¹(⊥)，h=height(L)」
三日月：「假设 3」
三日月：「停下来时那一行还没被划掉，那它就没有停……」
三日月：「假设 4」
三日月：「宣布它停下来的人，不是清单……」
我：「那是谁？」
三日月：「呵呵」
三日月：「这些都只是注释……」
三日月：「你想要多少，就可增加到多少……」
窗外，贩卖机的灯闪了一下。
我：「引理 1.3 呢」
水科：「worklist 是一个待处理节点的队列……」
水科：「每个节点被取出处理的次数，以格的高度 h 为上界」
水科：「全部节点的处理次数，以 |V|·h 为上界……」
我：「按 RPO 处理呢？」
水科：「每走完一趟，信息沿非回边推进一层循环嵌套的深度……」
我：「读成日常语言是什么？」
水科：「这是分析 pass 必然终止的统一理由……」
我：「那收敛得快不快呢？」
水科：「取决于循环嵌套有多深……」
手心的汗把车票印模糊了
水科：「SCEV 能在每轮循环改写后放心重建」
水科：「实现在 SCCPSolver.h:66、SCCPSolver.cpp:796」
我：「不对吧？」
水科：「引理 1.4，保守合成，join 聚合……」
水科：「若干独立结论合成一个时取 join，最不确定者胜……」
水科：「AA(p,q) = ⊔ AAᵢ(p,q)……」
水科：「NoAlias ⊏ Partial/Must ⊏ MayAlias = ⊤……」
我：「推论？」
水科：「且错在语义不在形态，Verifier 只查形态，看不见……」
我：「什么叫错在语义不在形态？」
水科：「一个分析给出错误的 NoAlias 后……」
我：「那不行吗？」
水科：「故 Verifier 不会报错……」
水科：「是定义 0.2 的 (i)」
我：「哪一层呢？」
水科：「AAManager 的全部分层……」
水科：「ReversePostOrderFunctionAttrs……」
水科：「callee 声明上的属性须是全 caller 都能保证的 meet……」
我：「怎么说？」
水科：「取交，最保守者胜，与 join 方向相反」
水科：「LAA 的 loop-non-alias 回填、AssumptionCache 的事实合并」
我：「谁保证？」
水科：「join 的实现就在 AA 主循环，AliasAnalysis.cpp:126……」
水科：「任一层答 MayAlias 即停，正是 ⊤ 短路……」
我：「定理 1.5？」
水科：「MOP ⊑ MFP……」
水科：「MOP 把每条可行路径各自执行一遍转移函数，再取 meet」
水科：「MFP 是引理 1.3 那套 worklist 迭代得到的不动点……」
水塔的影子比我先到
水科：「块入口先把前驱的结论 join 起来再转移……」
水科：「证明对 RPO 归纳」
我：「故它保证相等吗？」
水科：「不保证，只保证不更精确」
我：「推论 1.6？」
水科：「SCCP 型保证……」
我：「有前提吗？」
水科：「若 MFP 在点 b 给出常数 c……」
水科：「则 b 在任何真实执行中，要么不可达，要么取值恰为 c……」
我：「这条把什么归约成同一句话了？」
水科：「SCCP、IPSCCP」
水科：「CVP 取用值事实的那一步……」
水科：「LazyValueInfo 的 getPredicateAt 与」
我：「又走神了」
水科：「getConstantRangeAtUse……」
水科：「CorrelatedValuePropagation.cpp:297、:467……」
我：「贩卖机又吞钱了」
水科：「GVN 的编号，ConstraintElimination 的不等式闭包」
水科：「CalledValuePropagation 的候选集」
我：「哪句？」
我：「这句也在收据上写一下」
水科：「写不下」
我：「背面还有很多地方……」
水科：「……随你……」
她看着我写。
铅笔尖在热敏纸上刮出很轻的声音。
水科：「ValueLattice.h:27，SCCPSolver.h:87」
水科：「markBlockExecutable」
水科：「IPO/SCCP.cpp:9……」
水科：「引理 1.7，细化即新的一次遍历……」
我：「啊，那个」
水科：「把某个等价或依赖关系加细……」
我：「例子？」
水科：「把有人用，加细成有人用它的第 k 位……」
水科：「消费者四个」
水科：「BDCE，use → demanded bits……」
不，不对，我在数什么
水科：「ADCE，被引用 → 可达于可观测根……」
水科：「DSE，被读 → 被区间覆盖前读到」
水科：「MemorySSA，整个堆 → MemoryLocation」
我：「屋顶好晒」
水科：「这条是引 7.5 的形式化基础……」
我：「是、是、」
水科：「DemandedBits.h:41 加 BDCE.cpp:1……」
水科：「MemorySSA.md……」
水科：「DeadStoreElimination.cpp:9」
热敏纸上的字会淡。
铅笔的字不会。
清单空了，才算做完。
可是清单从来没有空过。
第三章 Dominance 「谁站在谁前面」
“9 月 13 日”
水科：「定义 2.1，支配……」
我：「谁保证？」
水科：「CFG 有唯一入口 entry……」
水科：「a dom b，指 entry 到 b 的每条路径都过 a……」
冰块响得比蝉早
水科：「严格支配去掉 a=b」
水科：「每个非入口块有唯一最深的严格支配者 idom(b)……」
罐子凉透了。
水科：「idom(b) 到 b 连成边，就是支配树……」
水科：「pdom 在反向图上镜像定义……」
水科：「DF(v)：存在 p 指向 w，v dom p，而 w 不严格 dom v」
猜拳出了两次一样的
水科：「IDF(S)=DF⁺(S) 的最小不动点，定理 1.2 保证存在」
我：「算法呢？」
水科：「LLVM 实际用 Semi-NCA……」
水科：「GenericDomTreeConstruction.h:12……」
水科：「接口 Dominators.h:241、PostDominators.h:48……」
我：「先算半支配点，再由最近公共祖先得到 idom……」
水科：「你居然记得」
我：「刚才你念过……」
水科：「定义 2.1a，最小 SSA 形式……」
水科：「同一份程序可写成许多种都合法的 SSA」
水科：「最小 SSA 是 φ 数最少的那一种……」
我：「多久一次？」
水科：「只在确有两条以上路径带着 x 的不同定义汇合的块上放 φ……」
啊哈哈，又走神了
水科：「所需块集合恰是赋值点集的 IDF，J⁺(S)」
我：「mem2reg 用的是它？」
水科：「mem2reg、SROA 提升出来的，MemorySSA 对访存做的……」
水科：「最小说的是 φ 的数量，不是 def 的数量……」
我：「def 一个也不省？」
水科：「PromoteMemoryToRegister.cpp:11……」
水科：「文件头，transformed by using iterated」
水科：「dominator frontiers to place PHI nodes……」
我：「定理 2.2？」
水科：「x 须 phi 的块集合恰为 J⁺(S)=IDF(S∖{entry})……」
或者说，我只是不想排队
水科：「必要性：设 w 不在 J⁺(S)，对支配树归纳」
水科：「w 的每个前驱 p 处 x 有唯一到达定义」
我翻到背面。
水科：「若诸定义互异，就有两条只在 w 汇合的路径……」
贩卖机的灯闪得没规律
水科：「按 DF 定义 w 就该在 J⁺(S)，矛盾……」
水科：「充分性：w 在 J⁺(S) 时那两条路径给出两个不可区分的候选值……」
水科：「phi 不可省」
水科：「GenericIteratedDominanceFrontier.h:13 引的就是它」
我：「推论 2.3？」
水科：「单步取得定义，DCE 即可达性」
水科：「SSA 下每条 Use 直接持有其 def 指针……」
我：「所以？」
水科：「reaching definitions 退化为一次解引用……」
我：「便当凉了呢」
水科：「还有没有人用，退化为一次 use 计数……」
水科：「删一条无 use 且无可观测副作用的指令是安全的……」
水科：「它的值从未进入 O，定义 0.1a 的字母表里没有它」
我：「消费者？」
水科：「mem2reg 与 SROA」
水科：「GVN、InstCombine、一切 DCE、SCEV 的 def-use 归纳」
水科：「Value.h:75、Use.h:35、User.h:44……」
我：「谁触发？」
水科：「Value.h:300 replaceAllUsesWith」
她把笔记本合上一半。
梅干总是在正中间
水科：「出去」
我：「现在？」
水科：「屋里太热」
“9 月 13 日”
坡道下面有一段石阶。
我们坐在那里。
水塔的影子从屋顶上滑下来，落在第三级台阶上。
我把收据压在膝盖下面，怕风吹走。
水科：「引理 2.4，代码移动四条件 M1–M4」
水科：「把 i 从块 A 搬到块 B 保持 0.2，只要四条……」
我：「那、」
水科：「M1，i 的每个操作数，其定义都支配 B……」
水科：「M2，i 的每个使用点 u，B 都支配 u……」
水科：「M3，f_B 不小于 f_A，或 i 满足引 0.7……」
我：「M3」
水科：「执行次数不减，或纯且不会 UB……」
水科：「M4，i 若访存，A 与 B 之间无与之 may-alias 的访问……」
水科：「内存可见性不变，见 T5 引 5.3」
水科：「四者合起来使事件序列逐点相同」
我：「谁在用？」
水科：「凡是在 IR 里移动指令的改写，都要分别满足这四条」
水科：「LICM 的提升与 promote、LoopSink 的下沉……」
水科：「GVNHoist、GVNSink、SpeculativeExecution……」
我：「然后呢？」
水科：「MergedLoadStoreMotion、SimplifyCFG 的 hoist……」
水科：「TailCallElim 的参数赋值搬移」
水科：「全是 M1–M4 的实例」
水科：「差别只在各自怎么证 M3 与 M4……」
我：「这四条清单是的吗？」
水科：「LICM.cpp:181 hoist、:185 sink、LoopSink.cpp:357」
水科：「M3 的判据 ValueTracking.cpp:7499……」
水科：「M4 的判据 MemorySSA.md 的 clobbering access……」
我：「引理 2.5？」
水科：「B pdom A，⟺从 A 到函数出口的每条路径都过 B……」
水科：「故 A 一旦执行，B 必在其后执行恰一次」
排到我时按钮全灭了
水科：「ADCE 用后支配树把控制依赖上的指令一并标活……」
我：「坡道好陡」
水科：「GVNSink 与 MergedLoadStoreMotion」
水科：「LoopDeletion 的零次进入」
水科：「SimplifyCFG 的 sink 与 unreachable 清理」
水科：「ADCE.cpp:101 成员 PostDominatorTree &PDT……」
我：「为什么？」
水科：「:216 从后支配树根的孩子里找 return……」
风把一张落叶吹到台阶上。
九月的落叶还带着一点绿。
我把它捡起来，夹进收据里。
水科：「你在干什么」
我：「书签」
水科：「……那是垃圾」
我：「是书签……」
水科：「引理 2.6，支配推出循环内恒定」
我：「冰化了呢」
水科：「v 的定义支配循环头 h，且 v 在循环内无重定义……」
水科：「SSA 下即循环内没有第二个 def……」
我：「什么时候呢？」
水科：「则 v 在每次迭代取同一值……」
我：「循环头？」
水科：「header、preheader、latch、exit 一律按」
水科：「LoopTerminology.md」
水科：「preheader 是 header 前唯一的外部前驱块……」
手心还是冰的
水科：「latch 是循环体里跳回 header 的该块……」
水科：「exit 是循环外的后继块……」
水科：「SSA 唯一 def，推论 2.3」
我：「硬币卡住了」
水科：「支配保证循环内任意点都看得见该 def，且无竞争者」
水科：「LICM 的不变性判定、SimpleLoopUnswitch 的不变条件……」
我：「谁读它？」
水科：「LoopFlatten 与 LoopFuse 的 trip count 一致性前提……」
水科：「LAA 的仿射下标系数、LoopIdiomRecognize 的常数写识别」
水科：「LoopInfo.h:62 声明……」
水科：「LoopInfo.cpp:67 Loop::isLoopInvariant……」
我：「谁写它？」
水科：「:73 hasLoopInvariantOperands，全部操作数都不在循环内……」
我：「谁去查？」
水科：「LICM.cpp:935 把这两条与安全性一起查」
水科：「ScalarEvolution.h:621 enum LoopDisposition」
水科：「每个 SCEV 按与循环的关系定性……」
我：「收据飞走了」
水科：「entry 处定义的值归入 LoopInvariant……」
我：「引理 2.7？」
水科：「支配树的 O(1) 查询……」
水科：「对 idom 树做一遍 DFS 预编号，得到 tin 与 tout……」
水科：「a dom b ⟺ tin(a)≤tin(b) 且 tout(b)≤tout(a)」
我：「找零口堵着」
水科：「oi-wiki DFS 页那句在支配树上的应用……」
我：「不对吧？」
水科：「GenericDomTree.h:148 getDFSNumIn/getDFSNumOut」
水科：「:505 dominates，:755 updateDFSNumbers」
水科：「DominatorTree 本体」
水科：「LICM、GVN、CVP 的高频支配查询……」
水科：「MemorySSA 沿支配树传播版本、IDFCalculator……」
“9 月 13 日”
水科：「T3，遍历序……」
我：「定义 3.0？」
水科：「从入口块对 CFG 做一遍 DFS……」
我：「伞忘带了」
水科：「把后序倒过来就是 RPO……」
我：「它好在哪？」
水科：「RPO 里前驱排在后继前面，只有回边例外……」
我：「定义 3.0a？」
水科：「四种遍历序，树上四个，图上有意义的三个……」
水科：「只保证 DFS 树上的父先于子……」
水科：「中序，图上定义不出来」
三日月：「不急」
水科：「若存在路径 W 到 V，则 V 排在 W 前，无环时……」
水科：「RPO，若存在路径 V 到 W，则 V 排在 W 前，无环时」
我：「例子？」
水科：「无环图，A→B，A→C，B→D，C→D，D→T……」
水科：「前序 A,B,D,T,C……」
收据被风吹跑了
水科：「后序 T,D,B,C,A……」
我：「嗯，是、」
水科：「RPO A,C,B,D,T」
我：「前序哪里不对？」
水科：「C 排在最后」
水科：「可 C→D，而 D 早在它前面就出现了……」
水科：「RPO 里每条边都从前往后，正是拓扑排序……」
我：「那不行吗？」
水科：「RPO 不是前序」
水科：「树上前序就够用的算法，搬到 DAG 上要的是 RPO……」
我：「带循环的呢？」
水科：「entry→H，H→body，H→exit，body→H……」
水科：「前序 entry,H,body,exit」
收据在口袋里响了一声。
水科：「后序 body,exit,H,entry……」
我不懂，但我记住了行号。
水科：「RPO entry,H,exit,body……」
我：「RPO 与前序不一样了……」
水科：「body 与 exit 互换……」
水科：「故 RPO 退化成引 3.1 那句话」
水科：「要让保证重新成立，只能先按 SCC 缩点……」
蝉还在叫
水科：「在缩点后的 DAG 上谈序，引 3.3……」
我：「为什么数据流要挑此序？」
水科：「两个方向」
水科：「SCCP、GVN、常量传播都是」
我：「有哪几种？」
水科：「ADCE、DSE、BDCE 那一族……」
我：「收益呢？」
水科：「正向在 RPO 下最省……」
水科：「有环时退化为迭代，但 RPO 仍是收敛最快的顺序」
我：「前序呢？」
水科：「两个方向都不能用」
水科：「正向合法序只有 RPO，反向合法序只有后序」
我：「可你刚才说，带循环 CFG 的正向那一栏它满足了……」
水科：「那一栏唯一不满足的边就是回边 body→H……」
水科：「而它按引 3.1 豁免，DFS 树本来就是父先于子……」
水科：「换成 DAG 立即不成立，C→D 被颠倒」
我：「还有一个说法，反向问题用反图上的 RPO」
水科：「原图上的后序，与反图上的 RPO，都是合法的反向序」
我：「差别在哪？」
水科：「本例原图后序 T,D,B,C,A，反图 RPO T,D,C,B,A」
我：「不能反过来？」
水科：「B 与 C 互换，而它俩之间没有路径，谁先都不影响正确性」
水科：「A→B，A→C，B→C，B→D，C→B，B 与 C 成环」
罐子空了
水科：「原图从 A 出发的后序是 C,D,B,A……」
水科：「每条边掉头、以出口 D 为入口，反图 RPO 是 D,B,C,A」
我：「为什么反图 RPO 反而更好？」
水科：「LLVM 里反向图是 marker class Inverse」
水科：「GraphTraits.h:109」
水科：「GenericDomTreeConstruction.h:130」
我：「啊哈哈，队好长」
水科：「std::conditional_t，Inversed 就换成」
我：「罐子空了呢」
水科：「Inverse
我：「最后那条更弱的保证呢？」
水科：「四序对比、RPO≠前序、正反两向如何选序……」
我：「LLVM 侧呢？」
水科：「RPO 的实现就是先 post_order 收集、再用反向迭代器输出」
水科：「PostOrderIterator.h:290」
水科：「ReversePostOrderTraversal」
水科：「:306 注释，Because we want a reverse post」
水科：「order……」
水科：「use reverse iterators from the vector……」
我：「谁写？」
水科：「消费者 NewGVN.cpp:3445、GVN.cpp:3102……」
我：「啊、啊、」
水科：「GVNSink.cpp:514、Reassociate.cpp:2744」
我：「引理 3.1？」
水科：「RPO 与回边」
水科：「DFS 把每条边分成四类……」
水科：「u→v 是回边，指 v 此刻还在 u 的 DFS 栈上……」
我：「顺序呢？」
水科：「即 v 是 u 的祖先」
水科：「则 u→v 是回边，⟺后序里 u 排在 v 前……」
水科：「倒过来，RPO 里就变成 v 在前……」
我：「谁来做呢？」
水科：「除回边以外的一切边在 RPO 中都是前向的……」
我：「推论？」
水科：「沿 RPO 走一趟」
水科：「轮数被嵌套深度而非图规模支配，与引 1.3 合流」
水科：「消费者 GVN 与 NewGVN 的编号序、ADCE」
水科：「mem2reg 的重写序、DominatorTree 的迭代」
水科：「Reassociate.cpp:209 BuildRankMap、LoopInfo」
我：「定理 3.2？」
水科：「h 是循环头，⟺存在回边 n→h……」
水科：「该回边的自然循环是 {h} 并上全不经过 h 到达 n 的 x……」
我：「确定？」
水科：「单入口，可多 latch……」
我：「要重跑吗？」
水科：「消费者 LoopInfo，一遍 DFS，O(V+E)……」
水科：「LPM 的 worklist、SCEV 以 Loop 为索引」
水科：「LoopInfo.cpp:9 文件头，identify natural loops」
我：「引理 3.3？」
水科：「缩点逆拓扑，callee 先」
水科：「调用图按 SCC 缩点后是 DAG」
水科：「逆拓扑序保证 callee 侧 SCC 先于 caller 侧被访问……」
鞋带又松了
水科：「消费者 Inliner 与 CGSCC 遍历」
我：「蝉还在叫啊」
水科：「PostOrderFunctionAttrs……」
水科：「LazyCallGraph 的 SCC 维护、GlobalOpt 的引用图遍历……」
水科：「LazyCallGraph.h:13」
硬币卡在找零口
水科：「NB: This is not a traditional call graph!……」
水科：「:122 引用图是调用图的超集」
水科：「CGSCCPassManager.h:13、:29、:59」
我：「推论 3.4？」
水科：「设属性 A(f) 的转移函数只依赖 f 自身体内结构」
我：「鞋带松了」
水科：「与 {A(g) | f 调 g}……」
水科：「则每个 SCC 只需内部解一次不动点，定理 1.2……」
我：「意思是？」
水科：「SCC 之间单次传递即达全图不动点」
便当凉了
水科：「对缩点 DAG 的逆拓扑秩归纳」
水科：「秩 0 的 SCC 是叶子，无出边依赖，直接收敛……」
水科：「秩 k 的 SCC 依赖的全在秩小于 k 中且已定型……」
我：「换句话说？」
水科：「PostOrderFunctionAttrs……」
水科：「readnone 从调用图的叶子逐层传到根」
我：「贩卖机又吞钱了」
水科：「nocapture 的参数图归纳、InlineCost 的 callee 体积测量……」
水科：「IPSCCP 的跨过程传播」
水科：「FunctionAttrs.cpp:271 Deduce」
水科：「readonly/readnone」
水科：「/writeonly attributes for the SCC」
我：「引理 3.5？」
水科：「LPM 的 worklist 按循环森林的逆后序取循环」
水科：「循环被改写时经 LPMUpdater 把新循环插回 worklist……」
我：「电车要来了」
水科：「unswitch 克隆、flatten 合并都是这种改写……」
水科：「消费者 FunctionToLoopPassAdaptor 的契约」
水科：「LICM、unswitch、full unroll……」
水科：「、须靠 LoopInstSimplify 与 LoopSimplifyCFG」
水科：「进场时重建规范形的事实」
水科：「LoopPassManager.h:13 写明逆后序」
水科：「加强制补 LoopSimplify 与 LCSSA，:218 class」
贩卖机又吞钱了
水科：「LPMUpdater」
我：「顺序不决定正确性……」
水科：「不决定」
我：「那它决定什么？」
水科：「决定你什么时候能停……」
风停了。
落叶从收据里滑出来，落在第三级台阶上。
我没有再捡。
第四章 Algebra 「循环、堆、价钱」
“9 月 13 日”
自动贩卖机在坡道中段，只亮着一半。
我投了一百円，找零滚出来，卡在槽里。
我蹲下去掏。
掏了很久。
水科：「T4，循环代数……」
我：「先等我拿到那一百円……」
水科：「定义 4.1，addrec，SCEV 的链式记法……」
水科：「{a,+,b}_L，在循环 L 里从 a 起每转一次加 b」
水科：「等差数列，下标 L 说明是哪个循环，嵌套时不能混……」
我：「那，是、」
水科：「{a,+,b}_L(i) = a + b·i，i 从 0 起……」
水科：「for (i = 0; i < n; ++i) 里的 i 是 {0,+,1}_L……」
我数到三。
水科：「p = p + 4、初值 %p0，是 {%p0,+,4}_L」
水科：「%A + i*4 是 {%A,+,4}_L」
我：「就这样？」
水科：「向量化能算出第 i 次访问哪个地址，靠的就是它……」
我：「找到了」
一百円硬币，很凉。
水科：「a 与 b 本身还可是别的 SCEV……」
水科：「嵌套：b 又是外层的 addrec，链套链，内层链当外层步长……」
水科：「常数因子吸收：{0,+,2·k} 与 2·{0,+,k} 是同一个节点」
我：「不对吧？」
水科：「硬约束：All operands of an AddRec are required」
水科：「to be loop invariant……」
水科：「即引 2.6 在 SCEV 里的用处……」
我：「为什么不直接留着 φ 环？」
水科：「φ 环只说下一轮由上一轮决定，不说第 i 轮是多少……」
水科：「addrec 把它变成关于迭代次数的闭式……」
水科：「循环结束后是多少、第 i 轮的地址是多少、一共转几次」
我翻到背面。
水科：「都成了代 i 去算的代数问题……」
水科：「引 4.2、引 4.3、定理 4.5 全建立在这一步上……」
我：「嗯、」
水科：「节点记在 FoldingSet，结构哈希，同形折叠成同一节点……」
水科：「故 SCEV 的查询是查表，不是重算」
我：「查表，不是重算」
水科：「ScalarEvolutionExpressions.h:332……」
水科：「SCEVAddRecExpr」
水科：「:324 a polynomial recurrence on the trip」
水科：「count……」
风把收据吹到栅栏上
水科：「:330 那条循环不变约束……」
水科：「ScalarEvolution.h:468，:473 拿 i32 {0,+,1} 举例……」
水科：「demand-driven，沿 SSA 归纳并分类序列」
我：「引理 4.2？」
水科：「EC=n 静态已知 ⇒ 出口处值为 a+b·n……」
水科：「循环外用一次乘加算出，SCEVExpander 物化……」
水科：「证明对 i 归纳」
电车门关得比我想的快
水科：「消费者 IndVarSimplify final-value rewrite……」
水科：「FullUnroll 常量代入……」
水科：「LoopFlatten 合并计数、LoopDeletion 的 EC=0 证明……」
水科：「ScalarEvolution.cpp:8285、:8340……」
我：「引理 4.3？」
水科：「Z_{2^w} 中 a+nb 越界即回绕，nuw/nsw 随之失效，引 0.6……」
水科：「扩到 w’ 使 |a|+n|b| < 2^{w’-1}，则无回绕，推理合法」
水科：「消费者 IndVarSimplify widen、SCEV wrap 传播……」
水科：「LoopVectorize 指针递进、Float2Int 可表示性检查……」
我：「定理 4.4？」
水科：「do-while 正规形……」
水科：「while-do 与 preheader 预检加 latch 尾测的……」
坡道上滑了一下
水科：「do-while 等价」
三日月：「一样的」
水科：「前提 (i) 首次条件求值结果相同，(ii) 条件表达式无副作用」
水科：「证明对迭代次数归纳……」
水科：「n=0，原版不进 body，新版预检失败直落 exit，事件集同为空……」
水科：「n≥1，两版执行同一段 body 序列，判断值相同……」
我：「谁保证？」
水科：「故用权重 {1,127} 计价，p_zero-trip=1/128，引 6.2」
水科：「消费者 LoopRotate、LICM 的推测授权……」
我：「梅干在正中间」
水科：「尾测形确立至少执行一次迭代，M3 的 f_B≥f_A 成立……」
水科：「SCEV trip-count 推导、FullUnroll 与 Vectorize」
我：「什么条件呢？」
水科：「的直线块前提……」
水科：「LoopDeletion」
水科：「LoopRotationUtils.cpp:52 rotate 本体……」
水科：「:49 ZeroTripCountWeights[] = {1, 127}……」
我：「定义 4.4a？」
水科：「单层 for 是 {0,…,n-1}，n 个点……」
我：「是、」
水科：「两层嵌套是矩形 {(i,j) | 0≤i<n, 0≤j<m}，n·m 个点……」
我：「为什么要坐标？」
水科：「interchange、flatten、distribute、fuse……」
水科：「LoopFlatten.cpp:941 select the original……」
水科：「version at runtime」
我：「多久一次？」
水科：「if the iteration space is too large……」
我：「定理 4.5？」
水科：「依赖 (s,t,d⃗)：s 在第 i⃗ 次迭代与 t 在第 i⃗+d⃗」
水科：「d⃗ 是依赖向量，两次迭代的坐标差」
水科：「σ 合法 ⟺ 对一切依赖，σ(i⃗+d⃗) 排在 σ(i⃗) 后」
我：「特例？」
水科：「五个」
数到第十二级就乱了
水科：「interchange σ(i,j)=(j,i)，合法 ⟺ 一切 d⃗」
水科：「flatten σ(i,j)=i·m+j，双射且保序……」
我：「一次就够？」
水科：「distribute，分组后不存在后组→前组的依赖……」
水科：「vectorize，VF 个连续迭代压成一步 ⇒ d⃗=0 或 d≥VF」
水科：「LICM，d⃗ 的循环不变分量为 0 ⇒ 可移出循环……」
水科：「消费者 LoopInterchange、LoopFlatten、LoopFuse……」
水科：「LoopDistribute、LoopVectorize、LICM……」
我：「那是什么？」
水科：「LAA 是 d⃗ 的生产者……」
水科：「LoopAccessAnalysis.h:1049……」
水科：「LoopVectorize.cpp:1172」
水科：「LICM.cpp:935 三重检查、:1294 canSinkOrHoistInst……」
我：「引理 4.6？」
水科：「fuse 的精确条件……」
水科：「两相邻循环 trip count 同为 n」
水科：「合法 ⟺ 不存在 B2→B1 的依赖，且一切 B1→B2 距离 ≥0」
水科：「原序 B1(i) 在时刻 i、B2(j) 在 n+j……」
水科：「融合后 B1(k) 在 2k、B2(k) 在 2k+1……」
水科：「B1(i)→B2(j) 要 2i<2j+1，即 i≤j……」
水科：「B2(i)→B1(j) 要 n+i<j，而 j<n，不可能」
我：「引理 4.7？」
水科：「结合律的定义域……」
水科：「整数加减在 Z_{2^w} 结合且交换 ⇒ reduction 重排无条件合法……」
水科：「故向量化的 reduction 例外须 reassoc/contract 授权」
我：「哪一条？」
水科：「否则定理 4.5 的 vectorize 推论中 d⃗=0 那一支不成立」
我：「那不行吗？」
水科：「Z_{2^w} 是交换环，R 上的浮点子集在 ⊕ 下不是半群……」
水科：「消费者 LoopVectorize、SLPVectorize、Reassociate……」
水科：「Float2Int 是反向，证明浮点链实际落在整数环里……」
我：「然后呢？」
水科：「Reassociate.cpp:436 LinearizeExprTree……」
我：「引理 4.8？」
水科：「c 的操作数全在循环外 ⇒ 引 2.6 得 c 循环内恒定……」
水科：「loop{if(c)B1 else B2} ≡ if(c)loop{B1} else」
水科：「loop{B2}……」
我：「所以？」
水科：「消费者 SimpleLoopUnswitch、LICM 分支外提」
窗外还是黑的。
水科：「LoopFlatten 前提检查、FullUnroll 后 guard 的常量折叠」
水科：「SimpleLoopUnswitch.cpp:86、:169 克隆预算、:577……」
“9 月 13 日”
风变凉了。
我把收据又折了一次。
第四次。
折痕那里裂开一道小口。
我回便利店借了透明胶带，从背面补上。
胶带比收据宽，两边各多出一点，粘在手指上。
水科：「T5，内存版本与别名，堆上的 SSA……」
我：「为什么？」
水科：「定义 5.1……」
水科：「MemoryLocation =（基址，偏移，大小）外加 TBAA 标签」
水科：「μ_k 是第 k 次 may-write 后的堆状态」
手心的汗把车票印模糊了
水科：「两个 Location 的关系只有四种：不交、包含、部分重叠、全等……」
我：「四种怎么判？」
水科：「由偏移与大小的区间运算决定，引 5.5……」
水科：「MemoryLocation.h:217，:40 起的注释讲 LocationSize……」
水科：「GEP 分解 BasicAliasAnalysis.cpp:602……」
水科：「DecomposeGEPExpression」
我：「定理 5.2？」
水科：「堆版本链 = 单地址 SSA……」
水科：「每次 may-write 视为对整个堆的一次定义……」
我：「谁？」
水科：「按定理 2.2 的 IDF 在汇合处插 MemoryPhi……」
我：「谁先？」
水科：「即得堆状态的最小 SSA，最小说的是 MemoryPhi 的数量……」
水科：「再用 AA 把整个堆细化到 MemoryLocation 粒度」
水科：「load 挂最近可能 def 记 MemoryUse，store 生成 MemoryDef」
水科：「call 保守生成 Def……」
贩卖机在坡道下面亮着。
水科：「证明是定理 2.2 在变量=堆上的直接实例，细化那步是引 1.7……」
水科：「消费者 MemorySSA、DSE、EarlyCSE 的 mem 模式、LICM」
水科：「promote……」
水科：「LoopIdiomRecognize、GVN 的 load 折叠、MemCpyOpt」
我：「谁写它？」
水科：「MemoryPhi 复用同一个 IDF 计算器」
水科：「GenericIteratedDominanceFrontier.h:58……」
水科：「堆也是 SSA 是实现事实，不是类比……」
我：「便当凉了呢」
水科：「MemorySSA.md 自称 trivial heap versioning……」
我：「引理 5.3？」
水科：「最近覆盖 def」
水科：「load ℓ 的值 = 支配 ℓ 的、最近一个与 ℓ 的 Location……」
水科：「非 NoAlias 的 def 所写的值……」
我：「几遍？」
水科：「对版本链归纳：跳过的版本要么不支配 ℓ，引 2.7……」
水科：「要么 AA 判 NoAlias，引 1.4……」
水科：「消费者 GVN、EarlyCSE、DSE、LICM、MemCpyOpt」
我：「手好冰」
水科：「MemorySSA.h:1035 getClobberingMemoryAccess……」
我：「多少次？」
水科：「EarlyCSE.cpp:1043 注释直接点名，:1097……」
我：「引理 5.4？」
水科：「a 从不逃逸：不被存入可观测位置、不作实参传出」
水科：「不被 volatile 访问、alloca 不出函数」
水科：「⇒ a 指向的存储私有，内容完全由本函数 store 序列决定……」
水塔的影子比我先到
水科：「⇒ (a,off,size) 这一片可替换为一个 SSA 值……」
水科：「phi 插入点按定理 2.2 计算……」
水科：「OP1/OP2/OP3 都碰不到它」
我：「啊、」
水科：「由定义 0.1b 它的写一次也不进 trace……」
不，不对，我在数什么
水科：「用寄存器复现同一 store/load 序列即可让 O 不变……」
水科：「这一条被多个 pass 共用……」
水科：「SROA 逐片提升、mem2reg 不切片的退化情形」
水科：「GlobalOpt 地址未逃逸的全局、LICM promote-to-register」
我：「硬币卡住了」
水科：「DSE 消除整块 alloca 的那一路……」
水科：「PromoteMemoryToRegister.cpp:1259、:809、:888，SROA.cpp:9……」
我：「那、那个」
水科：「GlobalOpt.cpp:9、LICM.cpp:526……」
水科：「从不逃逸的判定 ModRef.h:365 CaptureComponents、:414 CaptureInfo……」
我：「引理 5.5？」
水科：「[o1,o1+s1) ⊆ [o2,o2+s2) ⟺ o2≤o1 且 o1+s1≤o2+s2」
水科：「推论三条」
水科：「源区刚被常数写满的 memcpy 可换 memset……」
我：「谁的错？」
水科：「相邻同值 memset 可合并为一次……」
水科：「被后续全覆盖 store 吞掉、中间无 may-alias 读的 store 是死的……」
我：「有哪几种？」
水科：「消费者 DSE、MemCpyOpt、BasicAA、LAA……」
水科：「LoopIdiomRecognize」
冰块响得比蝉早
水科：「BasicAliasAnalysis.cpp:1105 aliasGEP」
水科：「DeadStoreElimination.cpp:9……」
我：「引理 5.6？」
水科：「工程解是引 1.4 的保守合成分层」
水科：「消费者 AAManager 与全部层、LAA、内联的 mod-ref 剪枝」
水科：「向量化合法性、LICM……」
我：「谁来做呢？」
水科：「任何一层误答 NoAlias，产出的就是语义错误的程序……」
我：「啊哈哈，队好长」
水科：「形态合法，Verifier 不报……」
“9 月 13 日”
水科：「T6，频度与代价，收益判定的统一标尺……」
水科：「定义 6.1……」
我：「那由谁负责？」
水科：「Pr(p→b) 由静态启发或 PGO 计数给出……」
水科：「静态启发：cold/likely 属性、!prof 元数据、默认偏置……」
水科：「f_b = Σ f_p·Pr(p→b)，f_entry = 1」
我：「电车要来了」
水科：「线性方程组 (I−Aᵀ)f = e」
猜拳出了两次一样的
水科：「循环使 I−Aᵀ 奇异，故按 SCC 消元或迭代求解……」
水科：「BlockFrequencyInfoImpl.h:724 三步，第三步……」
水科：「computeMassInFunction」
水科：「:1259，定点缩放 .cpp:462 convertFloatingToInteger」
我：「又走神了」
水科：「边概率 BranchProbabilityInfo.h:108……」
我：「引理 6.2？」
水科：「出口概率 p 的自然循环，期望迭代次数 1/p」
水科：「E = Σ k(1−p)^{k−1}p = 1/p」
我：「1/p」
水科：「{1,127} 读作循环几乎总会进入……」
三日月：「呵呵」
水科：「unswitch 克隆预算、inline hot-callsite 特判……」
水科：「full unroll 的 n×|B| 上限，同一套按频度加权……」
水科：「LoopRotationUtils.cpp:49……」
水科：「static constexpr uint32_t……」
我：「嗯、嗯、」
水科：「ZeroTripCountWeights[] = {1, 127};」
我：「定义 6.3？」
水科：「盈亏」
水科：「Δ = Σ f_b·(#改前_b − #改后_b)」
罐子凉透了。
水科：「接受 ⟺ Δ>0 且静态体积增量在预算内……」
啊哈哈，又走神了
水科：「消费者 SimplifyCFG hoist/sink」
水科：「SpeculativeExecution……」
水科：「LoopRotate、InlineCost、SimpleLoopUnswitch 预算」
水科：「LoopFullUnroll 预算、LoopIdiomRecognize 的 size 档」
水科：「LoopSink、SLPVectorize 打包树核算……」
水科：「ProfileSummaryInfo 的 hot/cold 阈值」
水科：「InlineCost.h:38 OptSizeThreshold = 50……」
水科：「LoopUnrollPass.cpp:149、:337……」
我：「注记 6.4？」
水科：「Δ_i 用当时的 f 度量，而改写会改 f……」
水科：「故 Σ Δ_i ≥ 0 不成立……」
水科：「即 LoopSink 须排在 LICM 后……」
我：「什么顺序呢？」
水科：「把 LICM 提升位置不当的指令再移回循环内」
水科：「它只在函数带运行期 profile 数据时才动手」
我：「谁都会吗？」
水科：「也是二轮 JumpThreading/CVP 须存在的理由……」
水科：「也是 SLP 须排在 unroll 后的代价模型理由……」
水科：「形式化见定理 7.4……」
水科：「LoopSink.cpp:357，它的存在本身就是承认上一轮 Δ 算得不准」
水科：「再来一轮的硬编码位置 PassBuilderPipelines.cpp:799」
“9 月 13 日”
水科：「T7，规范化与机会图……」
我假装听懂了。
我：「多少？」
水科：「定义 7.1，规范形 = 重写系统 R 的不动点……」
我：「现实呢？」
水科：「InstCombine 的规则集既不终止也不合流」
水科：「故实现是 worklist 加迭代上限……」
水科：「SimplifyCFG、InstCombine、LICM 各出现多回」
我：「再一遍？」
水科：「消费者 InstCombine、InstSimplify、SimplifyCFG……」
水科：「Reassociate，、再来一轮的全部位置……」
水科：「实证就在，InstructionCombining.cpp:6198……」
我：「谁读？」
水科：「if (Iteration >= Opts.MaxIterations」
我：「梅干在正中间」
水科：「&& !VerifyFixpoint)」
水科：「:120–:123 四个按迭代次数分档的计数器……」
水科：「NumOneIteration、NumTwoIterations……」
水科：「NumThreeIterations、NumFourOrMoreIterations……」
我：「确定？」
水科：「:118 是总数计数器 NumWorklistIterations」
我：「定义 7.3？」
水科：「机会算子」
水科：「O_i(x) = IR x 中 i 能改写的机会集」
或者说，我只是不想排队
水科：「连边 i→j ⟺ 存在 x 使 O_j(P_i(x)) ⊋ O_j(x)……」
贩卖机的灯闪得没规律
水科：「i 为 j 创造机会……」
我：「定理 7.4？」
水科：「设在第 k 个位置前」
水科：「一切由更早位置创造、且被第 k 个消费的机会均已物化……」
水科：「即拓扑序的定义……」
我：「手好冰」
水科：「故 O_k 达到它在本清单下能达到的最大值……」
水科：「去掉节点 i，其直接后继 j 的前提失效，O_j 严格变小……」
水科：「消费者是全部」
我：「谁先谁后？」
水科：「例如 SimplifyCFG 把已 rotate 的循环转回原形后再 rotate……」
我：「有出处吗？」
水科：「经验事实全在 PassBuilderPipelines.cpp」
水科：「:620、:759、:765、:799、:1609」
我：「引理 7.5？」
水科：「表示盲区与对应的专门 pass……」
水科：「SSA 数据流用的等价关系是操作数同形则值同……」
水科：「GVN 与 EarlyCSE 的同余……」
水科：「每类由一个专门 pass 按引 1.7 加细后重算」
水科：「聚合体 → 按访问区间切片后的独立单元，引 5.4……」
我：「屋顶好晒」
水科：「SROA / mem2reg……」
水科：「位级死代码 → use 变 demanded bits 位掩码，引 1.7……」
梅干总是在正中间
水科：「BDCE」
水科：「内存搬运与覆盖 → 区间代数，引 5.5」
水科：「MemCpyOpt / DSE……」
水科：「非支配分支上的重复访存 → 图形态菱形而非支配关系，引 2.5……」
我：「又走神了」
水科：「MergedLoadStoreMotion / GVNSink……」
水科：「定义 0.1a 加引 2.5，ADCE」
水科：「ADCE.cpp:198 Collect the set of root……」
水科：「instructions」
我：「啊，那个」
水科：「that are known live……」
我：「引理 7.6？」
水科：「加法链含 sub 的取负展开，规约为系数向量……」
水科：「e ≡ Σ c_i·x_i + k，c_i 与 k 在 Z_{2^w}」
水科：「Z_{2^w} 是交换环 ⇒ 链内可任意重排、合并同类项」
水科：「2x+3x=5x……」
我：「屋顶好晒」
水科：「故代数等价变成语法同形，落进 GVN/EarlyCSE 的同余……」
水科：「消费者 Reassociate 是生产者」
水科：「GVN、EarlyCSE、InstCombine」
我：「是、是、」
水科：「ConstraintElimination，求解器只接受规范形输入……」
水科：「还有 SCCP……」
我：「要什么？」
水科：「链上带 nsw/nuw 时，重排会改变 poison 出现的位置……」
水科：「故须按引 0.6(b) 重新证明，或干脆不动这条链」
水科：「Reassociate.cpp:436 LinearizeExprTree……」
水科：「:449 the number of times that operand」
水科：「occurs……」
水科：「in the linearized expression，那就是系数……」
水科：「:626 RewriteExprTree、:209 BuildRankMap 是项序」
我：「T0 到 T7，被反复引用的一共多少条？」
水科：「十八条」
水科：「0.5、0.6、0.7……」
排到我时按钮全灭了
水科：「1.4、1.5……」
水科：「2.2、2.4、2.5、2.6……」
水科：「3.4」
水科：「4.5、4.7」
水科：「5.3、5.4、5.5……」
我：「多久一次？」
水科：「6.3」
水科：「7.4、7.6……」
我：「被引最多的是哪条？」
水科：「引 0.5，UB 可剪……」
铅笔钝了。
水科：「必然 UB 的路径没有行为要保护……」
水科：「SCCP、JumpThreading、CVP」
手心还是冰的
水科：「LoopDeletion、WholeProgramDevirt」
我：「覆盖面最宽的呢？」
水科：「引 2.4 的 M1–M4……」
水科：「凡是在 IR 里移动指令的改写都要满足这四条……」
水科：「LICM、LoopSink、GVNHoist、GVNSink……」
收据被风吹跑了
水科：「SpeculativeExecution」
水科：「MergedLoadStoreMotion、TailCallElim」
我：「定理 7.4 呢？」
水科：「但它的实质——上游产物是下游前提……」
胶带边缘翘起来了一点。
我把它按回去。
按不平。
第五章 Read Only 「三类只读事实」
“9 月 13 日”
回到屋里。
三日月不在了。
窗台上只留下一点凉。
我：「然后呢？」
水科：「分析 pass，三类只读事实……」
水科：「变换 pass 每一步都依赖它们……」
我：「谁触发？」
水科：「它们回答的都是重算代价高、IR 一改就作废的派生事实……」
水科：「SCEV 是一次符号推导……」
水科：「MemorySSA 是一次全函数建链……」
我：「机制呢？」
水科：「懒算、缓存键、PreservedAnalyses，留到末章……」
水科：「证明一律往回引通用理论」
我：「那先来第一个……」
水科：「DominatorTree 与 PostDominatorTree……」
我：「坡道好陡」
水科：「domtree 与 postdomtree……」
水科：「Dominators.h:241、PostDominators.h:48……」
铅笔钝了。
水科：「概念就是定义 2.1 的全部……」
水科：「算法：按不动点迭代 idom(b) = ⊓_{p→b} idom(p)」
水科：「前驱 idom 的最近公共祖先，至收敛，再做一遍 DFS 预编号……」
蝉还在叫
水科：「产出 dominates 与 properlyDominates 谓词、树本体……」
我：「那、」
水科：「支配边界与 IDF 按需现算……」
水科：「IDFCalculator 用的是 DJ 图上的线性时间算法」
水科：「dominator joiner graph，在支配树上补进祖先指向非后代的辅助边」
水科：「消费方：mem2reg 的 phi 插入点、GVN 折 load……」
三日月：「都写着」
水科：「LICM 的提升落点、ADCE 的控制依赖，用的是后支配树……」
水科：「、一切引 2.4、2.5、2.6 的场合……」
我：「它对 preserve 的要求最严格？」
水科：「配套的 DomTreeUpdater 允许改写者批量登记删边与插边」
我：「不对吧？」
水科：「SimplifyCFG 合块」
水科：「LoopRotate 造 preheader 走的都是这条路……」
我：「所以？」
水科：「证明走定理 1.2、引 2.7、定理 2.2……」
水科：「把当前 idom 估计排成格，depth 越大越保守……」
水科：「收敛值即真 idom，它是满足 f(x)⊑x 的最小元，正是 lfp」
水科：「查询降为区间比较由引 2.7 给出……」
我：「LoopInfo？」
水科：「loops，LoopInfo.h:433……」
我：「谁保证？」
水科：「概念是自然循环与森林，定理 3.2……」
水科：「算法：一遍 DFS 标记回边，当前栈上的前驱即头」
我：「为什么？」
水科：「沿前驱集回溯收块求极小集，O(V+E)」
水科：「产出：每个 Loop 持块列表、header、parent 与 children……」
水科：「latch 与出口边集合……」
水科：「外加块到循环的反向索引 getLoopFor，与 O(1) 包含判定……」
水科：「消费方：LPM 的逆后序 worklist，引 3.5」
水科：「SCEV 的每个 trip count 以 Loop 为索引」
水科：「循环被改写后 LPMUpdater 同步森林并补新循环……」
水科：「证明走引 3.1 与定理 3.2……」
我：「谁先？」
水科：「Loop 集合是良基偏序，逆后序遍历就是子先于父……」
我：「ScalarEvolution？」
水科：「scalar-evolution，ScalarEvolution.h:9」
水科：「算法：沿 def-use 把每条指令归纳成符号 SCEV 节点……」
水科：「常数、entry 处的循环不变量……」
我：「哪一层呢？」
水科：「加法链求解成 {a,+,b}_L，等差或高阶套层，乘法吸收常数因子……」
罐子空了
水科：「节点 memoize 在 FoldingSet，复合表达式共享子项」
水科：「产出 getSCEV 闭式……」
水科：「getTripCountFromExitCount」
我：「谁写它？」
水科：「getSmallConstantTripCount……」
水科：「hasNoUnsignedWrap 与 hasNoSignedWrap 一族溢出事实……」
水科：「SCEVExpander 把闭式物化回指令序列……」
鞋带又松了
水科：「IndVarSimplify 那一步在循环外重算终值，就是它做的」
我：「消费方？」
水科：「full unroll 与 vectorize 要知道迭代次数是否静态可知」
水科：「LoopDeletion 拿它出 EC=0 的证明……」
水科：「unswitch 拿它判 trip count，LAA 拿它做距离比较……」
硬币卡在找零口
水科：「IndVarSimplify 拿它做扩宽与终值外提……」
水科：「代价：结论是对当时 IR 的推导缓存」
水科：「IR 改写后最容易失效」
便当凉了
水科：「PreservedAnalyses 里该显式丢弃结论的 abandon……」
我：「多少次？」
水科：「用得最多的就是它，PassManager.h:951……」
水科：「默认流水线里 ForgetAllSCEVInLoopUnroll 此参数名……」
水科：「直接说明了这一点，PassBuilderPipelines.cpp:568」
水科：「loop 流水线从内到外反复重建也是为此，重建有界，引 1.3……」
我：「出口计数怎么算？」
水科：「设出口条件为 {a,+,b} < c 且 b>0……」
水科：「EC = max(0, ⌈(c−a)/b⌉)……」
我：「冰化了呢」
水科：「最小的 i 使 a+bi ≥ c……」
我：「最小的 i」
水科：「这是引 4.2 的逆用」
水科：「无回绕前提由引 4.3 保证」
水科：「不满足时 SCEV 只能给出缺 nuw/nsw 的保守闭式……」
水科：「getSmallConstantTripCount 随之返回未知……」
我：「唔、」
水科：「结论保守是允许的，推论 1.6……」
我：「MemorySSA？」
水科：「memoryssa，MemorySSA.h:9」
水科：「SSA 处理寄存器，内存没有现成的 SSA 形式」
贩卖机又吞钱了
水科：「MemorySSA 用堆状态的版本链为它建立同样的性质……」
我：「嗯，是、」
水科：「即定理 5.2，φ 的位置同样取最小形式，定义 2.1a……」
水科：「算法：以 MemoryLocation 为粒度沿支配树传播当前 def……」
水科：「汇合处用 IDFCalculator 插 MemoryPhi」
水科：「load 经 walker 沿 def 链跳过不可能影响其 Location 的版本」
我：「谁的错？」
水科：「挂到最近可能 def 上记为 MemoryUse……」
水科：「store 生成 MemoryDef……」
我假装听懂了。
水科：「call 对全堆保守生成 def，纯读或无副作用的由 AA 降级……」
水科：「文件头自称 a trivial form of heap versioning，:15……」
风把收据吹到栅栏上
水科：「产出 Use/Def/Phi 节点图」
水科：「getWalker()->getClobberingMemoryAccess 与其反向 use 遍历……」
水科：「MemorySSAUpdater 保改写方的增量一致性……」
水科：「-verify-memoryssa 可整体校验……」
电车门关得比我想的快
水科：「消费方 EarlyCSE 的 mem 模式、DSE 的写覆盖判定」
我：「确定？」
水科：「LICM 的提升与 promote」
水科：「LoopIdiomRecognize 的整个循环都在写常数匹配……」
水科：「都归结为沿 def 链走一步……」
我：「那条精确到名字的失效声明呢？」
水科：「LPM1 进 loop 时 UseMemorySSA=true，:755……」
水科：「LPM2 传 false，:763」
水科：「理由是 :759 的注释」
水科：「The loop passes in LPM2……」
我：「坡道好陡」
水科：「(LoopIdiomRecognizePass, IndVarSimplifyPass,……」
水科：「LoopDeletionPass and LoopFullUnrollPass)……」
水科：「do not preserve MemorySSA」
坡道上滑了一下
水科：「All loop passes must preserve it……」
水科：「in order to be able to use it……」
我：「宁可不用，也不采信一份没审计过的声明……」
水科：「记住这句，末章还要用……」
我：「AAManager？」
水科：「aa，AliasAnalysis.h:967……」
水科：「别名不可判定，引 5.6」
我：「不可判定」
水科：「一次查询走 AAResults::alias(LocA, LocB, AAQI, CtxI)，:535」
我数到三。
水科：「两个实参都是 MemoryLocation，定义 5.1 的基址加大小……」
水科：「层：BasicAA，GEP 偏移与类型几何的区间推理，引 5.5……」
水科：「ScopedNoAliasAA，!alias.scope 与 !noalias，:24……」
水科：「TypeBasedAA，!tbaa 标签不同即不别名，:9」
数到第十二级就乱了
水科：「GlobalsAA，全局变量的 mod/ref 摘要」
水科：「再过 noalias-metadata 链与 loop-non-alias 缓存……」
水科：「那是 LAA 产出的回填处……」
水科：「产出四值判断 NoAlias/MayAlias/PartialAlias/MustAlias……」
我：「收据飞走了」
水科：「查询带着 MemoryLocation 的 size」
水科：「各层由 addAAResult 逐个登记，:324」
水科：「故分析家族可按 IR 单元动态注册……」
我：「有哪几种？」
水科：「消费方 LICM 提 load、GVN 折 load、DSE 判覆盖……」
我：「啊、啊、」
水科：「向量化证距离、内联时 mod-ref 剪枝……」
水科：「模块优化阶段的 RecomputeGlobalsAAPass 重算全局摘要再写回……」
水科：「:1557」
水科：「证明：四值排成格，聚合取 join，引 1.4」
水科：「区间级判定是引 5.5 的直接应用……」
水科：「(o1,s1) 与 (o2,s2) 不交 ⟺ o1+s1≤o2 或 o2+s2≤o1……」
水科：「这条不等式在 TBAA 标签相同的前提下……」
水科：「就是 BasicAA 的全部推理」
我：「LoopAccessAnalysis？」
水科：「access-info，LoopAccessAnalysis.h:1049」
水科：「概念：向量化的合法性……」
水科：「仿射下标交给 SCEV 解距离与方向……」
我：「那不行吗？」
水科：「AA 结论剪掉不可能别名的对」
水科：「非仿射访问归入 gather/scatter 档案」
我：「怎么验证呢？」
水科：「检查基址区间重叠与 stride……」
水科：「产出：可向量化访存集合、runtime check 清单……」
水科：「每访存的 stride 档案……」
水科：「消费方 LoopVectorize 的合法性判定基本是直接转发它的结论」
水科：「loop-non-alias 结论回填 AA 缓存供 LICM 与 GVN 复用……」
水科：「这也是它身为 loop 分析却影响函数全局的原因……」
水科：「LAA 是定理 4.5 里 d⃗ 的生产者……」
手心的汗把车票印模糊了
水科：「对访问对 (A[α(i)], A[β(j)])」
水科：「若 α 与 β 均为仿射，SCEV 闭式，引 4.2」
我：「换句话说？」
水科：「则依赖存在的必要条件是 α(i)=β(j) 有整数解……」
水科：「解出的 j−i 即 d⃗，无回绕由引 4.3 保证……」
水科：「三分类对应三种证明状态……」
水科：「d⃗ 已知且满足定理 4.5 的调度约束，静态合法」
水塔的影子比我先到
水科：「d⃗ 依赖运行期基址，生成 check」
不，不对，我在数什么
水科：「AA 判 MayAlias 且非仿射，不可向量化……」
水科：「runtime check 的健全性来自引 0.5 的镜像用法……」
水科：「check 失败即走标量版，两版在同一输入下的事件集相同……」
水科：「LoopAccessInfo :726，analyzeLoop :826」
水科：「RuntimePointerChecking :543……」
水科：「getRuntimePointerChecking :752」
水科：「LoopAccessInfoManager :1015」
三日月：「不急」
水科：「:1021 自持一份 AAResults &……」
水科：「把检查变成代码的位置 LoopVectorize.cpp:1172……」
我：「LazyCallGraph？」
水科：「module 层 lcg，PassRegistry.def:31……」
水科：「概念：优化器用的调用关系不能只统计 call 指令」
水科：「一个当前只被存进 vtable 的函数」
我：「找零口堵着」
水科：「NB: This is not a traditional call graph!……」
水科：「:13 到 :16……」
冰块响得比蝉早
水科：「It is a graph which models both the current calls……」
水科：「and potential calls」
我：「就这样？」
水科：「算法：边的定义是引用可达」
水科：「扫描按需展开，只分析已经被访问到的函数，故叫 lazy……」
水科：「产出：函数节点加引用边的图……」
水科：「附带可由 CGSCCPassManager 维护的 SCC 结构……」
我：「在哪一阶段？」
水科：「消费方：CGSCC 层遍历序的基础……」
我又点头。
水科：「逆拓扑保证 callee 先于 caller」
水科：「即内联一节该遍历次序成立的前提，引 3.3、推论 3.4……」
水科：「证明的健全性方向是过近似……」
我：「冰化了呢」
水科：「设运行期实际发生的调用边集为 E_r，LCG 的边集 E ⊇ E_r……」
水科：「多出来的边只会让属性推断更保守，引 1.4 的 join 更多项」
水科：「:18 到 :23 说明它的用途」
我：「那，是、」
水科：「保证全 callee 先于 caller 被访问……」
我：「都有什么呢？」
水科：「适合组织 CGSCC 类优化：内联、outlining、参数提升……」
水科：「:122 引用图是调用图的超集……」
“9 月 13 日”
贩卖机在外面嗡了一声。
我：「还有三个元信息分析」
水科：「频度、profile 摘要与 assume」
水科：「BlockFrequencyAnalysis 与 BranchProbabilityAnalysis」
水科：「block-freq 与 branch-prob……」
我：「谁在用？」
水科：「BPA 先给每条边定概率……」
水科：「静态启发：cold/likely 属性、llvm.expect、默认偏置……」
我：「嗯、」
水科：「llvm.expect 经 LowerExpectIntrinsic 降级为 !prof 元数据……」
水科：「PGO 则由加载 pass 写入真实计数再折算」
我：「真实计数」
水科：「BFI 再解定义 6.1 的线性方程组，最后整体缩放到定点……」
水科：「ProfileSummaryAnalysis……」
水科：「壳在 ProfileSummaryInfo.h:372」
水科：「本体 :42 class ProfileSummaryInfo」
猜拳出了两次一样的
水科：「从函数 entry count 聚合出全模块热分布摘要」
我：「谁来做呢？」
水科：「hot 与 cold 阈值由分位数算出……」
水科：「对外回答 isHotCount :182」
水科：「isFunctionEntryHot :115……」
灯管嗡了一声。
水科：「AssumptionCache……」
水科：「:44 是缓存本体，:189 是包它的分析壳 AssumptionAnalysis」
啊哈哈，又走神了
水科：「收集全函数 llvm.assume，并按被假设的值建索引……」
水科：「查询接口是：关于 %x 我被告知了什么……」
我：「收据飞走了」
水科：「LazyValueInfo 持有一份 AssumptionCache *……」
水科：「LazyValueInfo.cpp:401……」
水科：「求某个值的范围时遍历 assumptionsFor(Val)，:846」
水科：「CVP 的事实就是经这条链拿到的」
或者说，我只是不想排队
水科：「ConstraintElimination 直接扫 llvm.assume intrinsic……」
我：「谁写？」
水科：「ConstraintElimination.cpp:1462……」
水科：「用不上的 assume 由 DropUnnecessaryAssumes 反向清理……」
水科：「默认流水线在向量化后就调它一次，:1350」
我：「多久一次？」
水科：「消费方 SimplifyCFG 折哪边、hoist 与 sink 的盈亏，定义 6.3」
水科：「内联的 hot-callsite 特判、LoopSink 的落点……」
水科：「unswitch 的克隆预算……」
我：「伞忘带了」
水科：「故循环内概率乘积小于 1，(I−Aᵀ) 在每个 SCC 上可逆」
我：「一次就够？」
水科：「定点缩放不改相对量级，故定义 6.3 的 Δ 符号保持不变……」
水科：「assume 的可用性：llvm.assume(c) 的语义是 c 为假时该执行触发 UB……」
水科：「故由引 0.5，把 c 当作使用点处恒真的事实使用是合法的……」
我：「TargetLibraryAnalysis？」
水科：「target-lib-info，TargetLibraryInfo.h:625」
水科：「概念：优化器不能假定 libc 存在……」
水科：「字典由 TableGen 生成……」
我：「在哪一行呢？」
水科：「TargetLibraryInfo.td 逐条给出符号名与签名……」
水科：「:440 def memcpy_chk : TargetLibCall<__memcpy_chk,……」
水科：「Ptr, [Ptr, Ptr, SizeT, SizeT]>;」
水科：「_chk 变体与标准名同典收录」
水科：「TargetLibraryInfoImpl.td 定义参数类型的抽象……」
水科：「SizeT、Int32 这一档……」
水科：「TargetLibraryInfoImpl :93 按 triple 决定这一档平台认哪些名字……」
水科：「对外查询类 TargetLibraryInfo :283」
我：「是、」
水科：「getLibFunc(StringRef) :349」
水科：「getLibFunc(const Function&) :353……」
水科：「getLibFunc(const CallBase&) :359……」
水科：「has(LibFunc) :392 回答本平台有没有它……」
我：「谁做签名校验？」
水科：「isValidProtoForLibFunc :340 做签名校验」
水科：「分配与 free 家族的判定不在 TLI 里」
水科：「在 MemoryBuiltins.h……」
水科：「:56 isAllocationFn、:77 isLibFreeFunction……」
水科：「:127 getAllocationFamily……」
水科：「而它们的实参里都要带一份 TLI……」
水科：「消费方 InferFunctionAttrs 的标注」
水科：「LibCallsShrinkWrap 的错误域」
我：「找零口堵着」
水科：「MemCpyOpt 的区间代数、ExpandMemCmp 的字展开……」
我：「代价是什么？」
水科：「AA 判断此未知调用读不读内存……」
水科：「不同 target 之间的优化差异，相当一部分来自这张表……」
我：「那是什么？」
水科：「TLI 给出的属性是断言而非推导」
水科：「符号名 memcpy 指的就是标准语义的该 memcpy……」
水科：「故 LLVM 提供 -fno-builtin 一类的开关让用户退出这条约定……」
我：「什么时候呢？」
水科：「形式上≡给每个已知库函数附加一组引 0.6 式的前提……」
水科：「下游 pass 消费这些前提时的义务，与消费 nsw 完全相同」
水科：「分析壳 :621 到 :625 的注释顺手给了末章一个现成的例子」
水科：「this pass’s result cannot be invalidated……」
贩卖机的灯闪得没规律
水科：「it is immutable for the life of the module……」
水科：「一份不会因 IR 改写而失效的结论……」
水科：「自然可被全 pass 无条件 preserve」
我：「最后一个……」
水科：「VerifierAnalysis，verify，Verifier.h:109」
水科：「每个 pass 的 run 后，IR 仍是合法 IR……」
我点头。
水科：「phi 入数与前驱严格对齐……」
梅干总是在正中间
水科：「SSA 赋值唯一」
水科：「entry 块无前驱」
水科：「定义支配使用……」
水科：「消费方：-passes=verify 可插进流水线任意两个 pass 之间……」
我：「伞忘带了」
水科：「把谁把 IR 改坏了定位到具体 pass」
水科：「fat-LTO 流水线在把 bitcode 嵌进产物前也排了它一次」
水科：「:1821 的 if (Verify) 之下……」
水科：「:1822 MPM.addPass(VerifierPass())……」
我：「罐子空了呢」
水科：「紧挨着下一行的 EmbedBitcodePass……」
水科：「证明走定理 2.2 的形态侧」
水科：「phi 入数等于前驱数，与定义支配使用这两条……」
水科：「正是定理 2.2 构造的可检验形式……」
排到我时按钮全灭了
水科：「前者保证 phi 的选择函数是全函数……」
手心还是冰的
水科：「后者保证 SSA 值在使用点已定义……」
水科：「故 Verifier 通过，推出 IR 是良构的 SSA」
水科：「但它对定义 0.2 的 (i) 一无所知」
收据被风吹跑了
水科：「AA 答错的 NoAlias、SCEV 算错的 trip count，形态全部合法……」
水科：「前者靠每个 pass 自证，后者才靠工具查……」
我：「故三类？」
水科：「三类」
水科：「domtree、loops、lcg 是图分析……」
我：「罐子空了呢」
水科：「定义单元边界与改写合法性，T2 与 T3」
三日月：「一样的」
水科：「SCEV、MemorySSA、AA、access-info 是数据流分析」
水科：「决定每次改写是否安全，T1、T4、T5……」
水科：「profile、assumptions、TLI 是元信息分析……」
水科：「决定改写是否有收益，T6……」
我换了三次手。
水科：「而每个变换返回的那份 PreservedAnalyses」
我：「蝉还在叫啊」
水科：「哪些结论在该 pass 后仍然成立……」
我：「机制见末章」
水科：「机制见末章……」
我把收据翻过来。
第四栏已经写了一半。
写的全是名字。
一个也不认识的样子。
可是每一个都被人算过一次。
第六章 Prelude 「把前端的东西摆整齐」
“9 月 13 日”
水科：「模块级前奏，PassBuilderPipelines.cpp:1113 起……」
水科：「进正题前先说 T0 那两个定义在本章的用法」
蝉还在叫
水科：「W(a,v) 要求 a 可观测」
水科：「逃逸到本翻译单元之外、被 volatile/atomic 触及……」
水科：「未逃逸的 alloca 与 internal 全局不在此列……」
水科：「引 5.4 的私有性就是这句话的形式化」
我：「谁的错？」
水科：「定义 0.1b 再补一层」
水科：「即便地址可观测，两次写之间没有观测点时前一次也不进 trace……」
水科：「本章 GlobalOpt 的三种情形分别依赖这两条……」
我：「第一件？」
水科：「InferFunctionAttrs」
水科：「IPO/InferFunctionAttrs.cpp……」
水科：「只对声明且未标 optnone 的函数动手，:29 F.isDeclaration()」
我：「啊、」
水科：「拿符号名查 TargetLibraryInfo，命中即按该库函数的语义标注属性……」
我：「谁触发？」
水科：「在 BuildLibCalls.cpp:336 inferNonMandatoryLibFuncAttrs……」
水科：「readnone :66，readonly :99，nounwind :162……」
水科：「参数 nocapture :187，nosync :200」
水科：「nofree :276，willreturn :282」
水科：「带 nobuiltin 的声明跳过不标……」
水科：「:30 !F.hasFnAttribute(Attribute::NoBuiltin)……」
我：「那、那个」
水科：「即 TLI 那条证明里用户可退出命名约定在 IR 侧的开关……」
罐子空了
水科：「driver 侧对应 -fno-builtin」
我：「效果？」
水科：「call 从效果未知的副作用」
水科：「变成带明确效果档案的调用点……」
水科：「LICM 能否提升一个调用、内联是否复制它，判断依据全是这些 attribute……」
鞋带又松了
水科：「不先标注，后续全 pass 只能按最坏情形保守处理……」
我：「为什么排最前？」
水科：「事实还没标上，聚合出来的结论就只能停在最保守的那一格」
水科：「引 1.4」
我：「EarlyFPM？」
水科：「流水线里的变量名，:1162……」
水科：「几件轻量 pass 的组合……」
硬币卡在找零口
水科：「EntryExitInstrumenter，PostInlining=false……」
便当凉了
水科：「按 instrument-function-entry 与 -exit 属性……」
水科：「在函数入口与出口插 mcount」
水科：「__cyg_profile_func_enter 那类插桩调用」
水科：「LowerExpectIntrinsic」
贩卖机又吞钱了
水科：「把 llvm.expect 降级为分支权重元数据……」
水科：「:1164 的注释给的理由……」
我：「蝉还在叫啊」
水科：「Lower llvm.expect to metadata before attempting transforms」
水科：「Compare/branch metadata may alter the behavior」
我：「顺序呢？」
水科：「of passes like SimplifyCFG……」
水科：「再 SimplifyCFG :1168 → SROA → EarlyCSE……」
我：「什么顺序呢？」
水科：「块数与 alloca 数先降一轮，重复计算收敛……」
水科：「内联阈值按函数体积算，定义 6.3」
水科：「cost model 量到的就是无关代码的体积……」
我：「嗯、嗯、」
水科：「O3 在此追加 CallSiteSplitting……」
我：「谁在用？」
水科：「LowerExpectIntrinsic 是恒等式改写加事实换通道……」
水科：「⌊llvm.expect(x,c)⌋ = x 对一切 x 成立」
水科：「c 被记为 !prof 元数据，那是定义 6.1 的合法输入通道……」
风把收据吹到栅栏上
水科：「后续 pass 读得懂元数据、读不懂 intrinsic……」
水科：「即引 1.7 的一次加细……」
水科：「CallSiteSplitting 的正确性靠引 0.5」
我：「IPSCCP？」
水科：「IPO/SCCP.cpp:9……」
水科：「实参常量沿调用边与形参 meet……」
我：「什么条件呢？」
水科：「callee 内分支条件常量化的部分被死代码消除整块带走……」
水科：「foo(42) 一旦确定」
水科：「foo 里不会执行的那半个函数整块消失」
电车门关得比我想的快
水科：「格取 L_v = {⊥} ∪ Const ∪ {⊤}……」
水科：「L_e = {不可达 ⊏ 可达}」
水科：「联合格高度有限，定理 1.2 终止」
灯管又嗡了一声。
水科：「引 1.3 给出 worklist 入队次数的上界，与图规模成线性……」
我：「上界是线性的」
水科：「健全性：转移函数单调，定理 1.5 给 MOP ⊑ MFP……」
水科：「推论 1.6 立即得出形参被判为 c 则一切可达调用中该实参确为 c……」
水科：「边被判不可达，引 0.5 授权整块删除」
水科：「故不同调用形态不再互相 meet 成 ⊤……」
我：「换句话说？」
水科：「健全性由副本与原件逐点同构保证，推论 2.3 的重命名双射」
水科：「遍历序按推论 3.4，callee 侧 SCC 先定型」
我：「CalledValuePropagation？」
水科：「IPO/CalledValuePropagation.cpp:9……」
坡道上滑了一下
水科：「给候选集足够小的间接调用点挂上 !callees 元数据……」
水科：「用的是通用稀疏传播 solver」
数到第十二级就乱了
水科：「文件头，similar to constant propagation」
水科：「and makes uses of the generic sparse propagation solver……」
水科：「就是 SCCP 那台机器换了一个格……」
水科：「更大集合等于更保守，join 是交集」
我：「真的？」
水科：「故 lfp 是满足传播方程的最小候选集，即最精确的过近似……」
我：「怎么验证？」
水科：「健全性方向与 LCG 相同，引 3.3 的证明……」
水科：「由此 devirt 的合法性立刻得到……」
水科：「间接跳转与直接跳转都不在定义 0.1a 的字母表里」
我：「GlobalOpt？」
水科：「IPO/GlobalOpt.cpp:9……」
水科：「初始化后只读的升 constant」
水科：「只被单个函数触及的做与 mem2reg 同构的提升……」
我：「确定？」
水科：「初值折叠、存写折成 SSA 值……」
我：「谁？」
水科：「做完后 GlobalDCE 才能顺着引用链把它们一起删掉」
水科：「GVN 与 InstCombine 才拿得到这些新的立即数」
水科：「三种情形是引 5.4 在模块作用域的三次实例化……」
手心的汗把车票印模糊了
水科：「(i) 只写不读：地址未逃逸故不可观测……」
水科：「其上不存在任何观测点，0.1b……」
水科：「故其写不进任何 trace」
我：「鞋带松了」
水科：「(ii) 初始化后只读：模块内不存在对 G 的 store」
我又点头。
水科：「故对一切 σ，μ_k(G)=μ_0(G) 恒成立……」
水科：「引 5.3 的版本链上没有 def……」
水科：「升 constant 还额外断言外部也不能写……」
水科：「这须 G 具有本地链接……」
我：「不对吧？」
水科：「门槛就是 :1665 hasLocalLinkage()」
水科：「通过才走到 :1540 setConstant(true)……」
水科：「external linkage 的全局可能被别的翻译单元写，pass 不做……」
水科：「(iii) 单函数触及：G 退化为该函数的私有存储……」
水科：「引 5.4 直接适用，phi 插入点由定理 2.2 给出」
“9 月 13 日”
我把收据摊在桌上，用玻璃杯压住一角。
胶带那条边还是翘着。
水科：「AlwaysInliner，:1316」
水科：「把带 alwaysinline 属性的调用点全部展开……」
我：「鞋带松了」
水科：「带 flatten 属性的函数则展开它体内的一切调用点，:97……」
水科：「收集 alwaysinline 调用点的那段在 :108 到 :113」
水科：「AlwaysInliner.cpp:9 文件头……」
水科：「a custom inliner that handles only functions……」
水科：「that are marked as always inline……」
我：「贩卖机又吞钱了」
水科：「流水线传进来的 InsertLifetimeIntrinsics=true」
水科：「被内联函数的静态 alloca 搬进 caller 后……」
我：「便当凉了呢」
水科：「用 llvm.lifetime.start/end 把它们的生命周期区间标出来……」
水科：「InlineFunction.cpp:3130–:3166，:3134 的开关……」
水科：「:3151 与 :3161 的两次插入」
水科：「已带 marker 的与大小为 0 的跳过……」
水科：「动态 alloca 则改用 llvm.stacksave 与 llvm.stackrestore 包住整段……」
水科：「:3168」
水塔的影子比我先到
水科：「这些必选内联体从此以展开形态存在于函数体内，调用点清零……」
我：「是、是、」
水科：「callee 的栈对象变成 caller 里带生命周期标注的私有存储……」
我：「那不行吗？」
水科：「alwaysinline 是语义要求而不是收益判断」
水科：「而生命周期标注须在 alloca 刚搬进 caller 的那一刻就补上……」
水科：「晚了，SROA、DSE、AA 面对的就是……」
不，不对，我在数什么
水科：「看起来在整个 caller 里都活着的栈对象……」
水科：「插入它不会造出新 trace」
水科：「定义 0.1b 本来就允许区间外的写不进 trace……」
我：「不能反过来？」
水科：「引 5.4 的私有性论证故变短而不是变长……」
三日月：「呵呵」
水科：「插入位置本身的合法性走引 2.4(M1)……」
水科：「lifetime.start 插在内联体的第一个新块开头」
水科：「lifetime.end 插在每个 return 前」
水科：「musttail 与 deoptimize 调用和 return 之间不插……」
水科：「:3153 到 :3160 的两个跳过条件……」
水科：「注释里还写了一条：即使 O0 也要插……」
我：「故前奏就是在给后面的人留字条……」
水科：「留字条」
第七章 Bottom Up 「callee 先」
“9 月 13 日”
坡道上面又有人经过。
这一次是两个人，说着话，笑声很短。
我数了一下路灯。
七盏。
其中两盏不亮。
我：「就这样？」
水科：「沿调用图内联，按 SCC 自底向上……」
水科：「Inliner 与 ModuleInlinerWrapperPass，:963……」
水科：「机制在 IPO/Inliner.cpp:9……」
我：「算法？」
水科：「以 LazyCallGraph 的 SCC 缩点图做逆拓扑遍历」
水科：「callee 侧 SCC 先于 caller……」
水科：「对每个调用点计算 InlineCost……」
我：「贩卖机又吞钱了」
水科：「与随 Level 的阈值比较，含 hot-callsite 特判」
水科：「ret 边界接回调用点……」
我：「效果？」
水科：「跨函数数据流全部变成函数内 def-use 链」
水科：「call 开销消失」
我：「意义呢？」
水科：「它是跨过程优化的信息来源……」
水科：「常量进了新上下文才有 SCCP 可用……」
水科：「跨函数的重复表达式才有 GVN 可认……」
我：「一次就够？」
水科：「故主流水线把逐函数简化流水线整个嵌进 CGSCC 遍历」
水科：「:1037」
我：「一千零三十七行」
水科：「操作性等价，加推论 2.3，加定义 6.3……」
水科：「设被调函数体为 B_f，形参 p1..pk……」
我不懂，但我记住了行号。
水科：「调用点实参 a1..ak，call 的定义为 v……」
我：「那、」
水科：「(1) 重命名 B_f 中每个值为新鲜名……」
水科：「SSA 下这是 def-use 图的一个双射，推论 2.3……」
水科：「(2) 绑定 p_i 到 a_i……」
水科：「(3) ret r 变成 v := r，接回原调用点的后继……」
冰块响得比蝉早
水科：「alloca 随复制得到新鲜副本」
我：「等价性怎么论证？」
水科：「一次 call 的语义就是……」
水科：「求值实参 → 绑定形参 → 执行 body → 返回值……」
我：「多久？」
水科：「(1) 到 (3) 把这四步在调用点原地展开……」
我：「触发什么？」
水科：「body 产生的事件序列，定义 0.1a 意义下，逐条不变」
水科：「而 call 与 ret 这一对不在 E 里」
水科：「callee body 已知时调用是透明的……」
水科：「除非函数地址逃逸给栈观测，此时 pass 不做……」
我：「递归呢？」
水科：「只展开一层」
水科：「∵新复制的 body 里的自调用点仍在图上……」
水科：「这保证终止」
我：「遍历序呢？」
水科：「由引 3.3 给出」
水科：「先减小自身体积由定义 6.3 的体积预算给出……」
水科：「cost(callsite) = |B_f| − 简化学分……」
我：「哪一条？」
水科：「学分项恰是定理 7.4 的上游产物折算……」
水科：「代价模型的常量档在 InlineCost.h:38……」
水科：「OptSizeThreshold = 50……」
我：「激进档是多少？」
水科：「OptAggressiveThreshold = 250……」
我：「然后呢？」
水科：「遍历与 SCC 维护在 CGSCCPassManager.h:13……」
水科：「LazyCallGraph.h:109」
水科：「机制全在 IPO/Inliner.cpp:9……」
“9 月 13 日”
我把那一百円投回贩卖机。
掉下来的是一罐咖啡。
我不喝咖啡。
水科：「PostOrderFunctionAttrs……」
我：「所以？」
水科：「IPO/FunctionAttrs.cpp:271……」
水科：「由已定性的 callee 集合，加自身体内的访存、递归、异常结构」
我：「有哪几种？」
水科：「归纳推断 norecurse、readnone、willreturn、nofree……」
我：「什么条件呢？」
水科：「遍历收尾时，每函数的 attribute 集达到当前调用图下的归纳闭包……」
水科：「readnone 这类结论从调用图的叶子逐层传播到根……」
猜拳出了两次一样的
水科：「函数级的无副作用，从孤立事实变成归纳事实」
水科：「内联器的 mod-ref 剪枝与下游 LICM 直接消费这份闭包……」
水科：「A(f) = body(f) 的本地事实 ⊓ ⊓_{g ∈ callees(f)} A(g)……」
我：「为什么？」
水科：「取 meet，最保守者胜，引 1.4」
水科：「A 在属性格上单调，故由定理 1.2 存在不动点」
我：「谁读？」
水科：「由推论 3.4，沿逆拓扑秩归纳……」
水科：「秩 0 的 SCC 不调用任何函数或只调已定性的，单次计算即达不动点……」
我把行号抄在收据背面。
水科：「秩 k 的 SCC 内部若有递归……」
水科：「则 A 限制在该 SCC 上仍是单调自映射」
水科：「格高度有限，故收敛轮数以格高为上界，引 1.3……」
啊哈哈，又走神了
水科：「收尾时全图达到 A 的不动点……」
我：「故它跟内联是反着走的？」
水科：「内联是 callee 先被复制进 caller……」
水科：「属性是 callee 先被证明，caller 再继承」
水科：「下面」
我：「下面？」
水科：「调用图的下面……」
水科：「叶子」
罐子很凉。
我把它放在台阶上，没有打开。
“9 月 13 日”
水科：「DeadArgumentElimination，:1325……」
我：「硬币卡住了」
水科：「跨过程的 def-use 链变短，签名变窄……」
我：「为什么只能排在内联后？」
水科：「源码注释 :1323 写明了……」
我：「便当凉了呢」
水科：「内联把实参代进 callee 后……」
水科：「推论 2.3，加引 1.4 的全称量化……」
我：「有前提吗？」
水科：「形参 p 可删的条件是一条全称命题……」
水科：「模块内每个调用点传给 p 的值」
水科：「都不被 p 的任何 use 读取……」
水科：「推论 2.3 的 use 计数为零……」
我：「谁读它？」
水科：「这与 ReversePostOrderFunctionAttrs 那条证明的前提是同一句」
我：「唔、」
水科：「返回值同理」
水科：「全调用点都不使用 call 的结果时才可删……」
我：「未逃逸这三个字出现好多次了……」
水科：「它是这一整章的门槛……」
我：「那不就白排了一次吗……」
水科：「白排是常态」
水科：「引 1.3 说过，队列一定会空……」
热敏纸上的字会淡。
铅笔的字不会。
清单空了，才算做完。
可是清单从来没有空过。
第八章 First Half 「建立 SSA，消除显然的冗余」
“9 月 13 日”
水科：「逐函数简化流水线，:620……」
我：「谁写它？」
水科：「上半场，建立 SSA 形式，消除显然的冗余……」
我：「第一件就是 SROA？」
水科：「SROA，Scalar/SROA.cpp:9」
水科：「收集每个 alloca 上的全部访问区间……」
我：「谁？」
水科：「只以标量身份被读的片，提成独立的 SSA 值……」
我：「几遍？」
水科：「mem2reg 式的 phi 合并……」
水科：「改写为 bitcast 后的向量或整数位运算」
水科：「:15 注释，minimal slicing of the alloca……」
水科：「so that regions which are merely transferred in and out……」
或者说，我只是不想排队
水科：「of external memory remain unchanged」
我：「嗯，是、」
水科：「聚合内存对象转换为标量或向量 SSA 值」
我：「为什么排第一？」
水科：「∵它是 SSA 形式的前提，而不是可选优化……」
水科：「:19 文件头自己就这么定位……」
水科：「Because this also performs alloca promotion……」
贩卖机的灯闪得没规律
水科：「it can be thought of as also serving」
水科：「the purpose of SSA formation」
水科：「mem2reg 只处理仅有 load/store 访问的 alloca……」
水科：「引 5.4、定理 2.2、定义 6.3……」
梅干总是在正中间
水科：「设 alloca 大小为 n，其上的访问区间集为 I」
水科：「取端点集 E，是全部 o_i、o_i+s_i 与 n 的并……」
我：「为什么？」
水科：「(a) 每次访问都是若干划分格的并，端点全在 E 里……」
水科：「(b) 划分是最细的满足 (a) 的划分」
我：「什么时候呢？」
水科：「故每个格子独立地满足引 5.4 的私有性」
水科：「alloca 地址未逃逸，且只被纯 load/store 触及……」
水科：「可各自提升为一个 SSA 值……」
水科：「phi 插入点由定理 2.2 的 J⁺ 给出，且最小……」
我：「谁的错？」
水科：「整块 memcpy 进出的对象若切开」
背面已经写满了。
水科：「每格都要 extractelement 与 insertelement 重组……」
水科：「按定义 6.3 的 Δ 算下来为负……」
水科：「故注释要求 minimal slicing……」
我：「EarlyCSE？」
水科：「Scalar/EarlyCSE.cpp:9」
水科：「文件头，a simple dominator tree walk……」
我：「访存那一档呢？」
水科：「由构造开关打开，流水线里恰好开着……」
水科：「:639 EarlyCSEPass(true /* Enable mem-ssa. */)……」
排到我时按钮全灭了
水科：「它用 MemorySSA 的最近覆盖 def 判一个 load 是否仍然有效」
我：「代价是什么？」
水科：「逐字重复的表达式与冗余内存访问就地消失」
水科：「early 指在昂贵分析就绪前……」
水科：「减少 InstCombine 的工作量与体积测量的噪声……」
我：「代价呢？」
水科：「成本比 GVN 低得多，故排在此位置……」
水科：「同余关系定义为……」
水科：「(o, op, ⟨v1..vk⟩, flags) 与另一组逐项相同则同余……」
我：「然后呢？」
水科：「∵它的结果在定义 0.1a 下是操作数的确定函数……」
我：「硬币卡住了」
水科：「一个表达式在支配树节点 d 的作用域里插入」
水科：「只有 d 支配的块才看得到它」
水科：「引 2.7 的区间比较正是这一支配关系的判定……」
水科：「引 2.4 的 M1 与 M2……」
水科：「访存那档由引 5.3 判定」
水科：「ℓ 与 ℓ’ 同 Location，且 ℓ 是 ℓ’ 的最近覆盖 def」
我：「啊、啊、」
水科：「MemorySSA 的 clobbering access 恰是 ℓ 自己……」
水科：「则二者同值」
“9 月 13 日”
三日月又出现了。
她站在门口，没有进来。
手里拿着我忘在贩卖机下的那罐咖啡。
三日月：「此……」
三日月：「是你的」
我：「啊、谢谢」
三日月：「冷的了」
我：「嗯」
她把咖啡放在玄关，就走了。
门没有关。
风从坡道下面灌进来，把收据吹得翻了一面。
翻过来那一面，正面的字已经很淡了。
只剩一个 158 还认得出。
水科：「GVNHoist 与 GVNSink，默认关闭……」
水科：「要 -enable-gvn-hoist 或 -enable-gvn-sink 才排进流水线……」
水科：「:253 与 :257 的选项描述里写着 default = off……」
手心还是冰的
水科：「还有 SpeculativeExecution」
水科：「Scalar/SpeculativeExecution.cpp:9」
水科：「hoist 把重复表达式移到必经支配点……」
水科：「sink 把分支两侧同构表达式沉到汇合块，折成一条……」
我：「什么条件呢？」
水科：「SpecExe 把小 if-then-else 两侧的操作提到分支前无条件算」
水科：「结果用 select 按条件挑选」
我：「啊哈哈，队好长」
水科：「表达式计算次数趋近每路径一次……」
水科：「或分支直接变成 select……」
水科：「SpeculativeExecution 的文件头明确提到 GPU」
三日月：「都写着」
水科：「而它在流水线里带的是 OnlyIfDivergentTarget=true，:655……」
我：「不对吧？」
水科：「旁注写的就是 if the target has divergent branches……」
水科：「otherwise nop……」
水科：「即只在分支发散的 target 上生效」
我：「发散」
水科：「x86 上不做任何改写……」
水科：「GVNHoist 与 GVNSink 打开后，在 x86 上也只是偶有收益……」
水科：「三者是同一条引理的三个方向……」
水科：「引 2.4 的 M1–M4、引 2.5、引 0.7……」
收据被风吹跑了
水科：「hoist：设 n 份同构表达式分别在块 B1..Bn」
水科：「取 d 为它们在支配树上的最近公共祖先 LCA」
水科：「M1 由操作数在 B_i 处可用且 d dom B_i 得，支配传递……」
水科：「M2 由全部 use 都在 ∪B_i 的子树内得……」
水科：「M3 则因提到 LCA 后执行次数改变……」
水科：「f_d ≥ Σ f_{B_i} 未必成立，改走引 0.7，纯且不会 UB」
我：「多久？」
水科：「M4 对访存版由引 5.3 判中途无覆盖」
水科：「sink：落点 j 须后支配 B1..Bn，引 2.5……」
窗外还是黑的。
水科：「分支两侧任一支执行，则 j 必执行恰一次……」
水科：「且两份表达式的操作数在 j 处同值……」
水科：「GVN 同余，加操作数定义支配 j」
我：「啊哈哈，队好长」
水科：「故 n 份折成 1 份，执行次数下降」
我：「事件集不变就算安全？」
水科：「纯运算的情形下事件集不变，定义 0.1a……」
水科：「访存的情形另需 M4……」
水科：「SpecExe：把 i 提到分支前是无条件执行……」
水科：「M3 只能靠引 0.7……」
水科：「提到前面后，两支的使用点用 select 接回」
水科：「未被选中那支的 i 结果不被观测，故 O 不变……」
水科：「盈利性由定义 6.3 判……」
水科：「Δ = f_then·c_i 与分支开销的差……」
我：「JumpThreading？」
水科：「Scalar/JumpThreading.cpp」
水科：「对块 X 的条件分支查每个前驱 P」
水科：「若从 P 到达时条件值已可判定……」
我：「那，是、」
水科：「P 的 terminator 常量分支传播过来……」
水科：「就把 P 的这条出边从 X 改接到 X 的目标分支」
我：「多少？」
水科：「X 中对应 phi 项随之折叠」
水科：「X 只有一个前驱时，直接改写 X 的 terminator……」
我：「电车要来了」
水科：「效果：CFG 的边数下降……」
水科：「常常连续触发下一处 threading……」
水科：「定理 7.4 中机会图的自增强边……」
水科：「证明走引 0.5、推论 1.6、引 2.4(M2)……」
我：「确定？」
水科：「设 X 的终结指令为 br c, T, F，前驱 P」
我：「有前提吗？」
水科：「若在路径 P→X 上 c 被判定为真……」
水科：「P 的终结指令本身是常量分支……」
水科：「则该事实沿这条唯一的边成立，推论 1.6 的条件格给出……」
我：「嗯、」
水科：「或路径上的相等事实代入 c 后化简为常量」
水科：「则对一切经 P 进入 X 的执行，X 的终结指令必跳 T」
水科：「把边 P→X 改接为 P→T 后，事件序列不变……」
我翻到背面。
水科：「条件是 X 中从入口到终结指令之间的指令无可观测副作用……」
我：「就这样？」
水科：「否则跳过它们会少产生事件，违反定义 0.2(i)……」
水科：「实现上正是这一步先查 mayHaveSideEffects，:418」
水科：「T 中的 phi 须按 P 经 X 到达这条新路径重算入参」
水科：「若入参是 X 里定义的 phi 结果，则沿 X 的 P-入项取值……」
我：「phi 结果」
水科：「SSA 下唯一，推论 2.3……」
水科：「必要时克隆该计算到 P，合法性再走引 2.4 的 M1–M4……」
我：「只能这样？」
水科：「X 只有一个前驱时，X 的 phi 全部退化为单入项，直接折叠」
我：「CVP？」
水科：「CorrelatedValuePropagation」
水科：「Scalar/CorrelatedValuePropagation.cpp……」
水科：「由该分支条件可推出的：非零、范围、符号、nonnull……」
水科：「事实来自 LazyValueInfo，:99……」
水科：「在每个使用点给出的 ConstantRange」
水科：「把结论以 !range、!nonnull 元数据或 nsw 标志的形式……」
我：「梅干在正中间」
水科：「下游 pass 局部可见的事实集合扩大」
蝉还在叫
水科：「不是本 pass 亲手改的指令也变便宜」
水科：「与 JumpThreading 分工……」
水科：「前者改写 CFG 的边，把路径上已确定的事实固化成图的形状……」
水科：「add 指令上的 nsw 标志，常常就是在这里被证明、再写上去的」
我：「只要这样就行？」
水科：「健全性条件是 def(c) dom A，且 A dom block(i)……」
水科：「后者保证 i 只在走了 A 后才执行，引 2.7 的区间查询……」
我：「所以？」
水科：「故在 i 处 pred(x,y) 恒真是定理不是假设」
水科：「把它的推论写成 !nonnull 与 !range，或直接折叠」
水科：「都满足定义 0.2……」
水科：「生产 nsw 那一路是引 0.6(b) 的义务履行……」
水科：「须先在 ConstantRange 上证明 x+y 不越界……」
水科：「:472 ConstantRange::makeGuaranteedNoWrapRegion……」
水科：「例如由 x∈[0,2^30)、y∈[0,2^30) 得 x+y<2^31」
我：「电车要来了」
水科：「证明失败就不加标志……」
水科：「顺带的两条折算是域引理……」
水科：「∀x,y∈[0,2^31)，x sdiv y = x udiv y……」
罐子空了
水科：「且 x srem y = x urem y，截断向零，位形相同」
水科：「、 x≥0 时 sext 换成 zext」
我：「SimplifyCFG？」
水科：「Scalar/SimplifyCFGPass.cpp……」
水科：「规则本体在 Utils/SimplifyCFG.cpp……」
水科：「流水线传的选项在 SimplifyCFGOptions.h……」
我：「手好冰」
水科：「规则式 CFG 重写集」
水科：「把 switch 的连续 case 转成 icmp……」
水科：「流水线的 convertSwitchRangeToICmp(true)」
水科：「激进档还有 convertSwitchToArithmetic」
我：「是、」
水科：「合并同构分支，按需 hoist/sink 公共指令，迭代应用……」
水科：「块数与边数下降，图更接近树，phi 数量减少……」
我：「谁来做呢？」
水科：「几乎全改图的 pass 都会留下单前驱单后继的冗余块……」
水科：「与其要求每个 pass 自己清理，不如定期集中做一次……」
我：「多久一次？」
水科：「逐函数简化流水线里，每在最可能产生冗余块的 pass 后就排一次……」
水科：「:666、:681、:757、:822……」
水科：「另有 :651 那一处只在 GVN-sink 打开时才排……」
水科：「EarlyFPM 里也有一次，:1168」
水科：「折叠可判定分支：c 为常量时 br c,T,F 的一支必不可达」
水科：「引 0.5 授权删边删块……」
水科：「合并单前驱块：设 B 的唯一前驱是 P，且 P 以 br B 终结……」
水科：「B 中的 phi 因前驱唯一而退化为单入项」
收据在口袋里响了一声。
水科：「定理 2.2 的 J⁺ 在此为空，故可直接用其入参替换」
水科：「switch 转 icmp：设 case 标签构成连续区间 [a,b] 且共用目标 T……」
我：「又走神了」
水科：「switch x{a..b→T, default→D}……」
水科：「≡ br (icmp ule (x−a),(b−a)), T, D……」
水科：「∵ Z_{2^w} 中 x↦x−a 是双射」
水科：「且区间长度 b−a+1 ≤ 2^w」
水科：「故 x 落在无回绕区间 [a,b] 内……」
水科：「⟺ (x−a) mod 2^w ≤ b−a……」
水科：「hoist 与 sink 走引 2.4 的 M1–M4 加定义 6.3 的 Δ>0……」
鞋带又松了
水科：「hoist 到必经点省重复执行」
水科：「sink 到低频分支减少高频路径的指令数……」
水科：「这也是注记 6.4 说的贪心判定的局部性最集中的地方……」
“9 月 13 日”
我：「InstCombine……」
水科：「InstCombine/InstructionCombining.cpp」
水科：「InstCombineAddSub、AndOrXor、Casts、Compares……」
水科：「MulDivRem、Shifts……」
水科：「x+0→x，select(c,a,a)→a」
我：「梅干在正中间」
水科：「任何改写产物立即回灌 worklist，迭代到不动点……」
水科：「表达式收敛到规范且最小的形态，常数折叠到底……」
水科：「peephole，只在局部几条指令的范围内做等价替换」
三日月：「不急」
水科：「与 SimplifyCFG 交替排布，是∵一个管表达式树、一个管图」
水科：「CVP 标出 icmp ne %x, 0 后……」
水科：「InstCombine 才能把对应的 select 换成 trunc……」
我：「屋顶好晒」
水科：「定理 7.4」
我：「怎么验证呢？」
水科：「对一切 σ，作为关系证明 ⌊e⌋_σ = ⌊e’⌋_σ……」
水科：「即两侧取值集合相同，含 poison 行为……」
水科：「并检查标志义务，引 0.6……」
水科：「select(c,a,a)→a：c 为真取 a、为假取 a……」
水科：「c 为 poison 时两侧皆 poison，引 0.4」
水科：「x+0→x：Z_{2^w} 中 x+0=x……」
收据在口袋里响了一声。
水科：「x 为 poison 时两侧皆 poison……」
水科：「带 nsw 时 x+0 不溢出，故标志可保留……」
水科：「(x & 1) ≠ 0 → trunc(x & 1)」
水科：「x&1 ∈ {0,1}，故与 0 的比较等于其唯一有效位」
我：「终止性呢？」
水科：「引 7.2 的两条前提在 InstCombine 的规则集上不成立……」
水科：「故实现用 worklist 加迭代上限……」
水科：「到不动点是设计目标，而非定理」
我：「啊、」
水科：「它解释了为什么 InstCombine 要在清单上反复出现而不是一次……」
我：「所以它会成环？」
水科：「也解释了定理 7.4 的机会图为什么会有环……」
水科：「迭代上限在 InstructionCombining.cpp:6198」
水科：「它把每条 peephole 规则当成一个 refinement 子问题判……」
我：「AggressiveInstCombine？」
水科：「:668，AggressiveInstCombine/AggressiveInstCombine.cpp:9……」
水科：「InstCombine 后紧接的一个 pass」
水科：「当前主要处理 truncate 相关的模式……」
硬币卡在找零口
水科：「文件头自述……」
我：「那、那个」
水科：「Currently, it handles expression patterns for:……」
水科：「* Truncate instruction……」
水科：「另有 TruncInstCombine.cpp 专管截断」
我：「坡道好陡」
水科：「效果：位宽转换链变短」
水科：「它处理的是 InstCombine 规范化后剩下的多指令模式……」
水科：「单条规则看不见的形状，定理 7.4……」
便当凉了
水科：「以截断—扩展对为例，设 w_x ≤ w_t……」
贩卖机又吞钱了
水科：「trunc_{w_t}(zext_{w_t}(x)) = x，高位全零，截断恰好切掉它们」
水科：「trunc_{w_t}(sext_{w_t}(x)) = x 也成立」
水科：「但反向 sext(trunc(x)) = x……」
水科：「只在 x 的高位确为符号扩展时成立……」
水科：「此前提要么由引 0.6 的标志给出……」
水科：「要么由 CVP 写上去的 !range 元数据给出」
我：「LibCallsShrinkWrap？」
水科：「Utils/LibCallsShrinkWrap.cpp:9，位置 :669……」
风把收据吹到栅栏上
水科：「只对结果未被使用的 libcall 动手……」
水科：「这类调用不能直接删，∵它可能设 errno……」
我：「那是什么？」
水科：「errno 是一个可观测的写」
水科：「故把调用包进一个 guard……」
水科：「文件头的例子就是 sqrt(val); 改成 if (val < 0) sqrt(val);……」
水科：「errno 是这类调用无法直接删除的唯一原因……」
水科：「:23 到 :24 还交代了这类代码的来源……」
我：「冰化了呢」
水科：「These partially dead calls are usually results of……」
水科：「C++ abstraction penalty exposed by inlining……」
水科：「大多是内联把 C++ 的抽象代价暴露出来后剩下的……」
我：「收据飞走了」
水科：「pow(x,2)→x*x、exp(log(x))→x 那类恒等式改写不在本 pass」
水科：「而是 InstCombine 经 Utils/SimplifyLibCalls.cpp」
水科：「按 TargetLibraryInfo 的语义档案做……」
我：「怎么看出来？」
水科：「证明：设 libcall f 的结果未被使用……」
我：「一定要吗？」
水科：「则它对 trace 的贡献只有两项……」
水科：「一次调用 C(f,·)，、错误时对外部可观测对象 errno 的写」
水科：「令 E 为会设 errno 的错误条件，由 TLI 的语义档案给出」
水科：「例如 sqrt 的 E = {x<0}……」
电车门关得比我想的快
水科：「改写为 f(x) → if (x∈E) f(x)……」
水科：「x∈E 时两侧都调用，事件序列相同……」
我：「什么条件？」
水科：「x∉E 时新程序少了那一次 C」
水科：「这一步成立的前提是 f 此时已不是不透明 call」
我：「找零口堵着」
水科：「TLI 给了它的语义档案后……」
水科：「它唯一的可观测效果就是 W(&errno, e)……」
水科：「而 x∉E 时此写也不发生，故两侧 trace 相同……」
水科：「故本 pass 的正确性与 InferFunctionAttrs 相同……」
背面已经写满了。
我：「伞忘带了」
水科：「完全依赖 TLI 档案可信」
水科：「guard 的实现细节……」
水科：「判定 x∈E 是纯比较、不会 UB，引 0.7……」
水科：「且须在 f 前执行……」
我：「不能反过来？」
水科：「故用条件分支而不是 select」
水科：「select 的两个操作数都已求值，不具备惰性」
水科：「盈利性由引 6.2，p_E 极低……」
水科：「期望代价 p_E·c_f 远小于 c_f……」
我：「TailCallElim？」
水科：「Scalar/TailRecursionElimination.cpp:9……」
水科：「注册名 tailcallelim，位置 :678」
水科：「函数体以调用自身、结果直接被 return 终结时……」
坡道上滑了一下
水科：「把 call+ret 换成参数按实参重写，加跳回入口的 br……」
水科：「(1) call 与 ret 之间夹着死指令不影响判定」
水科：「(2) 若阻止尾递归的是一个结合且交换的表达式」
水科：「the typical naive factorial or fib implementation……」
水科：「(3) 返回 void、返回调用结果……」
水科：「意义：这是 IR 层的改写，判定须看全函数……」
水科：「全 return 的形态、call 与 ret 之间有无活指令……」
水科：「有无 landing pad 检查栈」
水科：「证明走定义 0.1a 加引 2.4……」
我：「那由谁负责？」
水科：「设 f(p){ β; ret f(p’) }，且尾调用后无任何指令……」
水科：「原版的事件序列是每层递归各贡献自己 body 的事件……」
水科：「改写版是循环 entry: β; p := p’; br entry」
数到第十二级就乱了
水科：「call 与 ret 对内部函数不在 O 中……」
水科：「等价所需的边界条件三条，逐条对应定义 0.1a 的事件类型……」
水科：「(i) 栈深度不可观测」
我数到三。
水科：「没有 landing pad 检视栈、函数地址未逃逸给栈回溯」
我：「哪一层呢？」
水科：「(ii) 各层之间不共享可变存储……」
水科：「alloca 每次调用一份新鲜副本……」
水科：「改写后须确认 β 里没有跨层存活的 alloca 引用……」
水科：「否则把 alloca 提到循环外会改变可见性，引 2.4(M4)」
手心的汗把车票印模糊了
水科：「(iii) 参数赋值的搬移满足 M1，p’ 在跳回点已定义」
水科：「扩展 (2) 的累加器另走引 4.7……」
水塔的影子比我先到
水科：「把 f(p,a) 的递归累积改成 a := a ⊕ p 的循环累积……」
水科：「⊕ 结合交换时两种求值次序在 Z_{2^w} 中同值……」
“9 月 13 日”
我：「Reassociate……」
水科：「Scalar/Reassociate.cpp……」
水科：「把加法链规约为系数向量，含 sub 的取负展开……」
水科：「每表达式写成 Σ c_i·x_i + k 后按项序重排、合并同类项……」
水科：「x2 + x3 → x*5……」
水科：「:684 流水线注释的原话」
我：「又走神了」
水科：「this will form (nearly) minimal multiplication trees……」
不，不对，我在数什么
水科：「代数等价变成语法同形……」
水科：「GVN 与 InstCombine 只能识别语法同形的表达式……」
水科：「Z_{2^w} 是交换环，故加法链中任意重排与结合律改写都保持值……」
我：「换句话说？」
水科：「同类项合并，系数在 Z_{2^w} 中相加……」
水科：「rank 由引 3.1 的 DFS 编号给出」
水科：「即 GVN 与 EarlyCSE 的同余关系能识别它的前提……」
我：「啊，那个」
水科：「乘法树部分，x·x = x^2……」
水科：「x^{2^k} = ((x^2)^2)……」
水科：「由交换半群的幂定义给出……」
水科：「nearly minimal 是指常数因子被提到根部、重复因子被平方化」
水科：「深度按 log 收敛」
我：「罐子空了呢」
水科：「唯一须的是标志，引 0.6……」
水科：「链上若有 nsw/nuw，重排会改变 poison 的产生位置……」
我：「什么顺序呢？」
水科：「故 Reassociate 要么证明重排后仍不溢出，保留标志……」
水科：「对浮点则整条引理不适用，引 4.7，⊕ 不结合」
三日月：「一样的」
水科：「除非有 reassoc 授权……」
我：「最后一件」
水科：「ConstraintElimination……」
水科：「Scalar/ConstraintElimination.cpp:279 class ConstraintInfo……」
水科：「流水线位置 :688，紧跟 Reassociate 后、LPM1 前……」
我：「是、是、」
水科：「开关 -enable-constraint-elimination 的 cl::init(true) 在 :283」
水科：「即默认开着」
我：「蝉还在叫啊」
水科：「把全函数的线性 icmp 假设编码为不等式矩阵……」
水科：「越界判断、x>=0 时的 x<0 分支」
我：「要跑什么？」
水科：「运行时检查整批消失」
水科：「覆盖 sanitizer 与数组边界检查这类代码……」
水科：「UBSan 插入的检查大多是线性可判定的……」
水科：「放在 reassociate 后」
我：「求解器要什么？」
水科：「正∵求解器的输入须是规范形，引 7.6」
水科：「分支两侧的路径条件，引 2.6 与 2.7 的支配……」
水科：「AssumptionCache 的 llvm.assume，引 0.5，假设为假即 UB……」
水科：「设事实集 F = {a_jᵀx ≤ b_j}，待判分支为 cᵀx ≤ d……」
我：「鞋带松了」
水科：「求解器证 F ∪ {cᵀx > d} 在 Q^n 上不可行……」
水科：「则在 Z^n 上不可行，∵ Z^n ⊆ Q^n……」
水科：「引 0.5 授权删除」
我：「完备吗？」
水科：「不完备」
水科：「整数专属的可判情形，如 2x=1 无整数解，会漏掉……」
水科：「但由推论 1.6 的方向性……」
我：「好处是什么？」
水科：「不完备只意味着少删几个 check，不意味着删错」
水科：「规范形作为输入的必要性」
水科：「未经引 7.6 规范化的 2x+3x 与 5x 会被当成两个不同变量……」
水科：「整数线性可行性判定的工程经典是 Pugh 的 Omega Test」
我：「那不行吗？」
水科：「LLVM 侧用的不是 Omega，而是自己的约束系统……」
我：「上半场结束了？」
水科：「结束了一半」
冰块响得比蝉早
水科：「SSA 建立了……」
水科：「式子规范了……」
第九章 Shape 「先把循环捏成契约形」
“9 月 13 日”
我把那罐冷掉的咖啡打开了。
喝了一口。
苦得不对。
我点头。
水科：「LPM1，先整形，再把不变量移出循环……」
水科：「LPM 的契约在此生效……」
水科：「LCSSA，Loop-Closed SSA」
猜拳出了两次一样的
水科：「循环内定义、循环外使用的值，一律经出口 phi 导出」
我：「有哪几种？」
水科：「LoopInfo、DominatorTree、ScalarEvolution 常备……」
我：「LoopSimplify 与 LCSSA？」
水科：「由 adaptor 强制加上，LoopPassManager.h:402」
水科：「实现分别在 Utils/LoopSimplify.cpp 与 Utils/LCSSA.cpp……」
水科：「LoopSimplify 补齐唯一 preheader」
我：「算改对了？」
水科：「唯一 latch、规范 exit……」
水科：「LCSSA 对一切循环内定义、循环外用的值……」
水科：「在出口块插入 phi 再导出」
啊哈哈，又走神了
水科：「效果：循环边界从散布全函数的 use」
我：「屋顶好晒」
水科：「收拢为几个出口 phi……」
水科：「意义：loop pass 故只需改写循环内部……」
水科：「代价，即多余的 phi……」
水科：「在收尾阶段由 InstSimplify 清除……」
水科：「:1649 clean up LCSSA form before generating code……」
水科：「定理 2.2、引 2.7、引 3.5……」
我：「谁在用？」
水科：「(C1) 存在唯一 preheader」
水科：「header 的外部前驱只有它……」
我：「多久一次？」
水科：「(C2) 存在唯一 latch……」
水科：「(C3) exit 块专用……」
水科：「(C4) 若 v 的定义在 L 内、且有 use 在 L 外」
水科：「则该 use 只经 exit phi」
我：「一次就够？」
水科：「(C1) 到 (C3) 由定理 3.2 的森林性质可构造……」
窗外还是黑的。
水科：「其等价性即 SimplifyCFG 合并规则的逆用」
水科：「(C4) 是定理 2.2 在变量=循环内定义的值、赋值点=latch 上的实例」
水科：「exit phi 的插入点集恰是 J⁺({latch})，故最小且足够……」
我：「那、」
水科：「(C4) 换来的性质是改写影响范围有界……」
水科：「loop pass 改动循环内定义 v 后……」
水科：「须修的循环外引用数，从 |uses_外(v)| 此无上界」
或者说，我只是不想排队
水科：「降为 |incoming(φ_exit)| ≤ |pred_内(exit)|……」
我：「谁触发？」
水科：「由 (C3) 有界……」
水科：「噪音的清理是 trivial phi 折叠……」
水科：「exit 的循环内前驱唯一时，LCSSA phi 只有一个入项……」
水科：「而单入项 phi 的选择函数恒取该入项」
水科：「故 φ[v] ≡ v」
我：「LoopInstSimplify 与 LoopSimplifyCFG？」
水科：「Scalar/LoopInstSimplify.cpp 与 Scalar/LoopSimplifyCFG.cpp……」
水科：「LPM1 的前两个 pass……」
贩卖机的灯闪得没规律
水科：「LoopInstSimplify 对循环内指令做单遍化简」
梅干总是在正中间
水科：「LoopSimplifyCFG 是 SimplifyCFG 的循环内受限版……」
水科：「改写范围不出当前 Loop，避免破坏外层已处理的状态」
水科：「效果：被前序 pass 改动过的循环体回到局部最优」
水科：「而 LPM 的内层先、定了不再回头此次序，引 3.5……」
我：「然后呢？」
水科：「这两个 pass 就是该保证的实现处」
水科：「这与引 7.2 里 InstCombine 须迭代上限的情形形成对比……」
“9 月 13 日”
我：「从哪一个开始？」
水科：「LICM，Scalar/LICM.cpp:9」
水科：「提升 must-alias 的内存访问……」
我：「所以？」
水科：「指针不变、MemorySSA def 链上循环内外无可能别名的读写……」
水科：「则 load 提到 preheader、store 沉到 exit」
水科：「中间改写用 SSA 值传递」
水科：「每次迭代一次的计算变成全程一次……」
我：「为什么？」
水科：「循环携带内存变成循环携带 SSA 值……」
我：「谁？」
水科：「不变性由引 2.6 判定」
水科：「i 的全部操作数定义支配 header，且循环内无重定义」
水科：「搬迁走 M1–M4……」
排到我时按钮全灭了
水科：「M1 由操作数定义在循环外……」
水科：「且支配 header 的循环外定义必支配 preheader」
水科：「(C1)：preheader 是 header 的唯一外部前驱……」
水科：「M2 由 preheader 支配循环内一切块……」
我：「什么时候呢？」
水科：「且循环外使用点已经过 LCSSA phi，(C4)……」
水科：「M4 对纯指令空虚成立……」
水科：「M3 是关键」
水科：「f_preheader ≤ f_body，执行次数减少」
我：「坡道好陡」
水科：「故纯指令走引 0.7 无条件合法……」
水科：「sdiv 除数在循环内才非零、访存可能段错误……」
我：「贩卖机又吞钱了」
水科：「即定理 4.4 的 rotate 提供的」
水科：「尾测形下 preheader 执行，推出 body 至少执行一次……」
手心还是冰的
水科：「故 preheader 里新引入的陷阱……」
水科：「定义 0.2(ii) 不被违反」
水科：「流水线里 AllowSpeculation 确实是 rotate 前传 false，:714」
水科：「rotate 后传 true，:720……」
我：「故是为了合法性？」
水科：「不只是」
我：「唔、」
水科：「:708 注释……」
水科：「do not perform speculative hoisting the first time……」
收据被风吹跑了
水科：「as LICM will destroy metadata」
水科：「that may not need to be destroyed……」
水科：「if run after loop rotation……」
水科：「两个理由叠在一起，才是这一对 LICM 的完整解释」
我：「职责二？」
水科：「promote to register」
我：「嗯，是、」
水科：「设位置 ℓ 在循环内 must-alias 不变……」
水科：「引 2.6 加 AA 的 MustAlias……」
笔记上没有这一行。
水科：「且 MemorySSA def 链上」
水科：「循环内外不存在与 ℓ may-alias 的其他访问……」
水科：「引 5.3 的最近覆盖 def，就是被提升的那次写」
我：「最近覆盖 def」
水科：「则 ℓ 在引 5.4 的意义下对此循环是私有的」
三日月：「呵呵」
水科：「load 提到 preheader，M1–M4 同上，M4 由无别名访问给出……」
水科：「store 沉到 exit……」
水科：「落点由引 2.5 的后支配保证……」
水科：「循环内每次写最终都对应 exit 处一次写……」
我：「什么时候？」
水科：「即先写后读的中间值改由 SSA 传递……」
水科：「中间用 phi 在 exit 合并，定理 2.2……」
蝉还在叫
水科：「故循环携带的内存依赖变成循环携带的 SSA 值……」
水科：「循环内那 EC 次写，合并为 exit 处 1 次」
我：「这不是改变了 trace 里的 W 事件条数吗……」
水科：「是」
水科：「这是 LICM 唯一会改变 trace 里 W 事件条数的改写」
水科：「合法性由定义 0.1b 给出……」
水科：「OP1 由循环内外无 may-alias 读排除……」
水科：「OP2 由循环内无不透明 call 触及 ℓ 排除」
我：「就这样？」
水科：「must-alias 不变加 AA 结论，正是这两句的证明义务」
水科：「故那 EC 次写本来就一次也不进 trace……」
我：「谁的错？」
水科：「任何 trace 只在 OP3，即 exit 后，看见 ℓ 的值……」
水科：「而它被 exit 处那一次写原样保留……」
水科：「若 ℓ 根本未逃逸，引 5.4」
水科：「连 OP3 都不存在，那最后 1 次写也可一并省掉」
水科：「:181 hoist，:185 sink……」
罐子凉透了。
水科：「:935 提升候选的三重检查……」
水科：「hasLoopInvariantOperands、canSinkOrHoistInst……」
水科：「isSafeToExecuteUnconditionally……」
水科：「:1294 canSinkOrHoistInst」
水科：「:1826 isSafeToExecuteUnconditionally……」
水科：「AllowSpeculation 就是它的最后一个实参，声明在 :188 到 :192……」
水科：「:2008 promoteLoopAccessesToScalars，调用点 :526……」
我：「冰化了呢」
水科：「不变性本身由 LoopInfo.cpp:67 与 :73 回答」
我：「LoopRotate？」
水科：「LoopRotationUtils.cpp:52」
水科：「把入口边的条件检查克隆进 preheader……」
水科：「循环体改为首指令直落、latch 尾测的 do-while……」
水科：「ZeroTripCountWeights = {1, 127}，就在 :49」
水科：「preheader 加单 latch 加尾测出口……」
水科：「意义：SCEV 的 trip-count 推导……」
我：「啊、啊、」
水科：「unroll 与 vectorize 的整个 body 可当直线块复制的合法性……」
我：「会不会漏？」
水科：「LICM 的推测授权……」
水科：「全部以此形态为前提」
水科：「等价性即定理 4.4，两个前提逐条兑现……」
水科：「(i) 首次条件求值结果相同……」
我：「那，是、」
水科：「其操作数在 preheader 与 latch 处取值相同」
水科：「引 2.6：操作数在循环内不变……」
水科：「若可变，rotate 会先把条件化简到只依赖循环不变量，否则放弃……」
水科：「(ii) 条件无副作用……」
我：「嗯、」
水科：「rotate 只克隆纯比较与分支……」
水科：「可能陷阱的操作数，如 load，需满足引 0.7 才允许复制」
水科：「代价按引 6.2 计……」
水科：「{1,127} 读作 p_zero-trip = 1/128……」
水科：「故多出来的那次求值，期望代价为 (1/128)·c_cmp……」
我：「哪一步之后？」
水科：「而收益是 body 内每次少一条跳回头部的边」
水科：「按定义 6.3 的 Δ 恒正」
我：「SimpleLoopUnswitch？」
水科：「Scalar/SimpleLoopUnswitch.cpp:86……」
水科：「trivial 情形，编译期常量条件，直接折掉一支」
水科：「nontrivial 的 guard 克隆受体积预算约束」
罐子空了
水科：「且只在 O3 打开……」
水科：「NonTrivial 实参写的就是 Level == OptimizationLevel::O3，:723……」
我：「多少？」
水科：「O2 只执行 trivial 的那一半……」
水科：「效果：if (flag) 从每次迭代执行一次变成循环外执行一次」
水科：「紧接的 LPM2 才有可用的输入……」
水科：「不变性由引 2.6 判定，故引 4.8 的分配律直接适用……」
水科：「克隆后每份循环里 c 已知为常量」
水科：「其分支由引 0.5 折掉，B1 与 B2 成为直线块……」
水科：「这一步正是 LPM2 里 full unroll 与 vectorize 须的前提……」
我：「收据飞走了」
水科：「定理 4.4 后的第二次形态收敛……」
水科：「trivial 情形不产生克隆，只折一支，故不计预算」
水科：「nontrivial 情形的体积增量是 |B1|+|B2|−|B|」
水科：「按定义 6.3 与 Level 预算比较，超预算则放弃……」
水科：「推论 1.6 的方向性在此再次生效……」
“9 月 13 日”
咖啡喝到一半，我把它放下了。
罐子底部有一圈没化开的糖。
我：「LoopFlatten 呢……」
水科：「默认关闭」
水科：「-enable-loop-flatten 的 cl::init(false) 在 :226」
水科：「开启后挂在 LPM1 末尾，:725」
水科：「实现在 Scalar/LoopFlatten.cpp……」
水科：「证明内外层间无携带依赖后……」
水科：「两层 trip count 相乘，合成单个循环……」
水科：「:763 的 CreateMul……」
水科：「新 trip count 写回外层出口条件，:781」
我：「内层归纳变量怎么重建？」
水科：「不重建」
水科：「都须匹配 (OuterPHI * InnerTripCount) + InnerPHI 此形状……」
我：「是、」
水科：「不匹配就得用 div/mod 才能还原」
罐子凉透了。
水科：「pass 判定为不划算而放弃……」
水科：「:613 到 :619 的注释与 :620 checkIVUsers……」
水科：「:644 checkOverflow，引 4.3」
水科：「证不出来就生成运行期版本选择，:983」
水科：「:941 select the original version at runtime……」
我：「啊、」
水科：「if the iteration space is too large……」
水科：「循环嵌套深度减一……」
水科：「两层边界检查与两条 latch 合并为一」
我：「哪一层呢？」
水科：「SCEV 面对单层仿射式，推导能力更强……」
水科：「unroll 也只需处理一个循环……」
水科：「证明走定理 4.5 的 flatten 推论、引 4.2、引 2.6……」
水科：「迭代空间为 {(i,j) : 0≤i<n, 0≤j<m}……」
我：「不对吧？」
水科：「映射 σ(i,j) = i·m + j 是双射」
水科：「且 (i,j) 的字典序与 σ 的数值序一致」
水科：「σ(i’,j’) − σ(i,j) = (i’−i)m + (j’−j)……」
水科：「i’>i 时为正，i’=i 且 j’=j 时为零，i’<i 时为负……」
水科：「j 与 j’ 都在 [0,m) 里……」
水科：「故按定理 4.5，只要一切依赖向量在字典序下非负」
水科：「flatten 保序合法……」
水科：「两个附加前提……」
鞋带又松了
水科：「内层 trip count m 对外层循环不变，引 2.6，否则 σ 不是双射……」
水科：「内层无 early exit，否则迭代空间不是矩形」
水科：「逆变换 i = k/m、j = k mod m」
水科：「在 m>0 时是 σ 的逆……」
水科：「且 k < n·m 时不溢出，引 4.3 检查宽度……」
铅笔钝了。
水科：「实现 :644 checkOverflow……」
我：「故它其实不算 div/mod？」
水科：「不算」
水科：「pass 并不真的去算 div/mod……」
水科：「而是要求两个归纳变量的全部用法已经是线性形式 i·m+j……」
水科：「」
水科：「合法性由定理 4.5 保证……」
水科：「两条判据分开，少一条就不做」
我：「少一条就不做……」
水科：「少一条就不做……」
我：「这句话好像也在收据上写过」
水科：「写过」
水科：「在第四栏」
我低头看。
第四栏最上面一行，是我自己写的。
字很淡。
铅笔太钝了。
第十章 Idiom 「认出一个循环，然后把它拿走」
“9 月 13 日”
我：「那不行吗？」
水科：「LPM2，识别惯用法、规范归纳变量、展开……」
我：「找零口堵着」
水科：「LoopIdiomRecognize」
水科：「Scalar/LoopIdiomRecognize.cpp:9……」
水科：「用 MemorySSA 的 def/uses 链，加 SCEV 的地址仿射性」
水科：「常数写连续区，换 memset……」
三日月：「都写着」
水科：「逐元素搬运，换 memcpy 或 memmove……」
水科：「找零扫描，换 strlen 等……」
水科：「:13 文件头注释」
水科：「If compiling for code size we avoid idiom recognition……」
我：「那、那个」
水科：「if the resulting code could be larger……」
水科：「than the code for the original loop……」
水科：「整个循环替换为一条 intrinsic 调用」
我：「好处是什么？」
水科：「收益有两处……」
水科：「memset 由 libc 或后端实现为带非临时存储的向量化例程」
我：「然后呢？」
水科：「non-temporal store，提示硬件这块数据不必进缓存……」
水科：「以 memset 模式为例」
水科：「设循环内唯一的写是 store c, gep(base, i·s)……」
水科：「i 遍历 [0,n)，c 循环不变，引 2.6……」
水科：「地址由 SCEV 给出闭式 base + i·s，引 4.2，仿射……」
我：「多久一次？」
水科：「对 i 归纳：第 i 次迭代写入字节区间」
水科：「[base+is, base+(i+1)s)」
我：「那是什么？」
水科：「n 次迭代后，这些区间的并是 [base, base+ns)……」
水科：「区间两两不交，引 5.5 的区间代数……」
我：「一次就够？」
水科：「每格内容均为 c 重复 s 次……」
水科：「故最终内存状态与 memset(base, c, ns) 逐字节相同」
水科：「trace 也相同」
水科：「n 次写之间不存在观测点……」
我：「嗯、嗯、」
水科：「循环内无读该区的点、无不透明 call……」
我：「有例外？」
水科：「由引 5.3 的最近覆盖 def 判定保证……」
水科：「故由定义 0.1b，这 n 次写一次也不单独进 trace……」
水科：「任何 trace 只在 OP3 处看见 [base, base+ns) 的最终字节」
我：「谁触发？」
水科：「而 llvm.memset 不是不透明 call……」
水科：「LangRef 逐字定义了它的效果，就是产生同一份最终字节状态……」
水科：「故替换后 W/C/V/R 四类事件逐条对应……」
我：「不对吧？」
水科：「memcpy 与 strlen 模式同构」
我：「啊，那个」
水科：「只是把常数 c 换成源区的读值，或把写换成比较」
水科：「盈利性走定义 6.3 的 size 档……」
我：「各模式的入口？」
水科：「常数写 :900 processLoopMemSet……」
水科：「内部走 :1097 processLoopStridedStore……」
水科：「逐元素搬运 :837 processLoopMemCpy」
我：「哪一条？」
水科：「:1279 processLoopStoreOfLoopLoad」
水科：「找零扫描 strlen 与 wcslen 的形状要求写在 :2178 的注释里……」
硬币卡在找零口
水科：「开关是 :137 的 -disable-loop-idiom-strlen……」
水科：「统计项 :104……」
我：「硬币卡住了」
水科：「替换目标 llvm.memset 与 llvm.memcpy 的效果」
水科：「逐字定义在 LangRef 的两节……」
水科：「本 pass 不把循环换成不透明 call……」
水科：「而是换成效果已定义的 intrinsic……」
“9 月 13 日”
我：「IndVarSimplify……」
水科：「Scalar/IndVarSimplify.cpp:9」
我：「是、是、」
水科：「两件事」
水科：「其一，规范出口条件」
我不懂，但我记住了行号。
水科：「for (i = 7; i*i < 1000; ++i)……」
水科：「改写成 for (i = 0; i != 25; ++i)……」
水科：「trip count 成为显式常数比较」
我：「伞忘带了」
水科：「其二，SCEV 扩宽……」
水科：「把 A[i] 的 mul+add 地址算式……」
水科：「替换成围绕 getelementptr 的指针归纳变量……」
水科：「地址表达式从每次重算变成每次迭代一步」
水科：「向量化器按 VF 步进指针……」
我：「那、」
水科：「trip count 显式化后」
水科：「就交给 SCEV 与 unroll……」
我：「唔、」
水科：「正好交给下一个 pass，LoopDeletion……」
水科：「终值外提的证明」
水科：「设循环外使用点 u 引用循环内归纳变量 v = {a,+,b}_L……」
水科：「出口计数 EC = n，引 4.2 已给出闭式……」
水科：「则 u 处 v 的值为 a + b·n……」
水科：「它只依赖循环外量与常数 n」
我：「啊、啊、」
水科：「故可在 exit 前用一次乘加算出」
我：「多少？」
水科：「这是引 2.4 的 M1 在把定义搬到循环外方向的应用……」
水科：「操作数 a、b、n 全在循环外，落点支配全部 use……」
水科：「搬完后循环内 v 若无其他 use，即成为死代码……」
我：「谁写它？」
水科：「推论 2.3 的 use 计数为零，交给 ADCE」
水科：「把 {7,+,1} 与谓词 i² < 1000 联立，解出 n = 25……」
水科：「改写为 {0,+,1} 与 i ≠ 25……」
我假装听懂了。
水科：「健全性由引 4.2 的闭式唯一性给出……」
我：「几遍？」
水科：「原 i 用 i’+7 替换」
水科：「扩宽」
水科：「w 位下 {a,+,b} 若 a+nb 越界即回绕，引 4.3……」
水科：「扩到 w’ 使 |a|+n|b| < 2^{w’-1}……」
我：「那，是、」
水科：「末尾 trunc 回 w 位是无损的」
水科：「∵真实值本就在 w 位范围内……」
我：「谁写？」
水科：「指针递进 q_{k+1} = q_k + s 与 q_k = base + k·s 的等价……」
水科：「由引 4.2 归纳……」
便当凉了
水科：「且指针算术走 getelementptr 而非整数加法……」
水科：「从而绕开引 0.6 的溢出义务」
水科：「终值物化靠 SCEVExpander……」
我：「LoopDeletion？」
水科：「Scalar/LoopDeletion.cpp……」
水科：「preheader 的每个前驱都以常量条件分支绕过它」
水科：「:147 isLoopNeverExecuted，调用点 :462……」
我：「什么时候？」
水科：「删前先把出口 phi 的入项填成 poison……」
水科：「SCEV 给出零回边计数」
水科：「:398 breakBackedgeIfNotTaken……」
水科：「:407 getConstantMaxBackedgeTakenCount……」
我：「在哪里？」
水科：「:409 getBackedgeTakenCount……」
水科：「:216 canProveExitOnFirstIteration」
我：「确定？」
水科：「由 -loop-deletion-enable-symbolic-execution 控制」
水科：「:40 的 cl::init(true) 说明它默认开着……」
我：「谁的错？」
水科：「循环是死的」
水科：「体内无可观测副作用、出口 phi 的值循环不变……」
水科：「:63 isLoopDead……」
水科：「:106 到 :110 逐条查 mayHaveSideEffects()……」
水科：「droppable 的 intrinsic 除外」
我：「所以？」
水科：「pass 入口在 :516」
水科：「另有两条硬性前提……」
水科：「须有 preheader 与专用出口，且出口不能是 EH pad……」
水科：「:442 到 :460……」
水科：「preheader 直通 exit」
水科：「结构上是循环、迭代次数却为 0 的循环若不删」
我：「罐子空了呢」
水科：「会阻碍后面全以循环存在为前提的 pass……」
我：「有几种情形？」
水科：「定理 7.4……」
水科：「(i) 回边一次也不走，EC=0」
水科：「由引 4.2 的闭式解出 n=0……」
水科：「推论 1.6 保证这是真实执行次数……」
我：「是、」
水科：「故 body 一次也不执行……」
水科：「删除循环后 preheader 直通 exit」
水科：「路径集与原图在跳过零次 body 的意义上同构……」
水科：「(ii) 循环是死的……」
水科：「body 无可观测副作用且无循环外活值……」
水科：「O 中不含 body 的任何事件……」
水科：「定义 0.1a 的四类 W/C/V/R 一个都没有」
水科：「且其结果无人消费，推论 2.3 的 use 计数」
三日月：「不急」
水科：「故执行 n 次与执行 0 次的 O 相同……」
水科：「(iii) 循环从不进入……」
水科：「preheader 的全部前驱都以常量条件分支……」
水科：「把 preheader 放在 not-taken 一侧」
我：「那、那个」
水科：「故不存在进入 header 的可行路径」
水科：「引 0.5 的逆向用法：那条边本来就不可达……」
水科：「删除循环后，出口 phi 的入项改成 poison 也不会被观测……」
我：「嗯、嗯、」
水科：「∵那些 phi 只在循环真的执行过时才有意义……」
我：「它用 profile 计数吗？」
水科：「不用」
水科：「此 commit 的 LoopDeletion.cpp 里读不到任何 !prof」
水科：「三条路全部是静态证明……」
我翻到背面。
水科：「profile 只提供值不做的信息……」
水科：「定义 6.3 与引 0.5 的分工」
我：「不终止的循环呢？」
水科：「不能走 (ii)……」
我：「啊哈哈，队好长」
水科：「删除循环后变成有限 trace……」
水科：「正是定义 0.2(i) 明文禁止的那一类……」
我：「不做会怎样？」
水科：「C++ 的前进保证使无副作用却不终止本身 UB」
水科：「即 ⊥ ∈ O(P,σ)，0.2 的义务整体解除，引 0.5 适用……」
水科：「而在实现里，这条语言级授权不是 pass 默认拿走的……」
水科：「而是被编码成 IR 里的属性……」
我：「啊，那个」
水科：「函数上的 mustprogress」
贩卖机又吞钱了
水科：「或循环元数据 llvm.loop.mustprogress」
水科：「判据写得很直白，:112 到 :117 的注释与紧随其后的 mustProgress()」
水科：「函数带 mustprogress……」
水科：「或每个子循环要么带 mustprogress、要么迭代次数静态可知……」
水科：「无限循环不是被 pass 私自删掉的」
水科：「死循环的官方定义在 :422 到 :428 的文档注释里……」
我：「LoopFullUnroll？」
水科：「Scalar/LoopUnrollPass.cpp:1640……」
我：「是、是、」
水科：「trip count 静态已知」
水科：「且展开后体积在 Level 预算内……」
我：「换句话说？」
水科：「构造式直接把 Level 传进 LoopFullUnrollPass……」
水科：「static_cast
水科：「O2 比 O3 紧……」
水科：「把循环体复制 N 份」
我：「再一遍？」
水科：「:149 与 :337 是 trip count 与体积预算……」
我又点头。
水科：「循环消失，成为直线代码……」
水科：「LCSSA phi 的入项全变常数、随后被折叠……」
水科：「跨迭代的冗余，从此成为普通 GVN 能识别的同形重复」
我：「真的？」
水科：「数组访问 A[i] 的下标变编译期常数……」
水科：「即随后 SROA 再执行一遍能……」
水科：「delete small array after loop unroll 的原因，:765……」
我：「电车要来了」
水科：「它与 unswitch 的衔接同样直接……」
我：「有前提吗？」
水科：「guard 分支被常数条件替掉后」
水科：「一个 pass 在清单中的位置……」
水科：「本身取决于其它 pass 为它创造的前提……」
水科：「前提三条」
我：「蝉还在叫啊」
水科：「rotate 已把 body 变成单 latch 的直线块，定理 4.4……」
水科：「故复制 body 是复制一段无内部回边的指令序列」
我：「无内部回边」
水科：「EC = n 静态已知，引 4.2」
水科：「n·|B| 在预算内，定义 6.3 的静态体积项……」
我：「就这样？」
水科：「构造：把 body 复制 n 份串联……」
水科：「第 k 份中归纳变量 {a,+,b} 代入常数 a + b·k……」
水科：「出口条件按 k<n 折为真，引 0.5 删掉假支……」
水科：「等价性对 n 归纳」
水科：「n=0 时由 LoopDeletion 的 (i) 处理……」
我：「那、」
水科：「n→n+1 时前 n 份按归纳假设等价……」
水科：「第 n+1 份对应原第 n+1 次迭代……」
水科：「其执行前提是前 n 份未触发 UB、未提前退出」
我：「UB 的次序问题呢？」
水科：「第 k 份的 UB 对应原第 k 次迭代的 UB」
水科：「故新程序在第 k 份 UB，蕴含原程序在第 k 次迭代 UB……」
水科：「定义 0.2(ii) 不被触犯……」
我：「谁来做呢？」
水科：「LCSSA phi 变成单入项常量后，由 trivial phi 折叠消失」
我：「什么条件呢？」
水科：「若整个 alloca 的访问区间集有限且不重叠……」
水科：「SROA 的划分会把数组切成 n 个独立标量片并各自提升……」
水科：「引 5.4 的第二次应用……」
我：「故 LPM2 是把循环拆掉……」
水科：「认出来的换成一条 intrinsic」
水科：「交给下半场」
第十一章 Second Half 「重新算一遍谁还活着」
“9 月 13 日”
水科：「先是 VectorCombine 的 early folds……」
我：「唔、」
水科：「Vectorize/VectorCombine.cpp」
我：「嗯，是、」
水科：「与 MergedLoadStoreMotion……」
水科：「Scalar/MergedLoadStoreMotion.cpp:11……」
水科：「位置在 :770 与 :773……」
我：「谁在用？」
水科：「夹在 SROA 第二次进场与 GVN 之间」
我：「VectorCombine 做什么？」
水科：「按目标代价模型做标量与向量交互的模式重写」
水科：「extract(extract(……)) 与 extract(insert(……)) 折叠……」
水科：「:662 foldExtractExtract……」
风把收据吹到栅栏上
水科：「insert/extract 与 shuffle 互换……」
水科：「:5940 foldInsExtVectorToShuffle」
水科：「:1096 foldBitcastShuffle」
水科：「:1362 foldExtractedCmps……」
我：「啊、啊、」
水科：「从向量 load 里只取一个元素时，退化为标量 load……」
水科：「:2131 scalarizeLoad」
水科：「:9 到 :11 的文件头……」
我：「谁写？」
水科：「这一类变换不适合放进基于循环或 SLP 的向量化 pass……」
我：「MergedLoadStoreMotion 呢？」
水科：「把 if-then-else 两侧同地址的 load 提到分支前……」
水科：「两侧不同的使用点用 select 接回」
水科：「store 反向可沉」
我：「那，是、」
水科：「效果：重复访存合并……」
水科：「意义：跨控制流的重复 load 是数据流 pass 的盲区……」
水科：「GVN 折 load 要求支配，而分支两侧互不支配」
我：「那不行吗？」
水科：「须有 pass 按图形态而不是值等价来消除」
我：「鞋带松了」
水科：「引 7.5 表中对应的那一行……」
水科：「shufflevector 的语义是索引置换……」
水科：「shufflevector(a,b,m)_k……」
水科：「0 ≤ m_k < N 时取 a 的第 m_k 个」
水科：「N ≤ m_k < 2N 时取 b 的第 m_k−N 个」
水科：「m_k 是 undef 时为 poison……」
我：「确定？」
水科：「故 extractelement(insertelement(v,x,i),i) = x……」
水科：「同索引抵消……」
贩卖机在坡道下面亮着。
水科：「insertelement 两次写同一索引，后写覆盖前写……」
水科：「引 5.5 的单格版本」
水科：「逐 lane 成立即整体成立……」
我：「所以？」
水科：「splat 消除靠 ∀k: v_k = c ⇒ v = broadcast(c)……」
我：「要跑什么？」
水科：「MergedLoadStoreMotion 的证明更强……」
水科：「设菱形，源码注释叫 diamond，也叫 hammock」
水科：「d → {B1, B2} → j……」
水科：「B1 与 B2 各有一条对同一 Location 的 load，ℓ1 与 ℓ2……」
我：「要重跑吗？」
水科：「提到 d 的合法性不能只靠引 0.7……」
水科：「load 可能陷阱，解引用非法地址即 UB」
我：「几遍？」
水科：「这里的论证是：d 的每条出边子树里都存在对该地址的读」
水科：「故任何经过 d 的执行，原本都会读一次此地址……」
我：「是、」
水科：「提前到 d 不可能引入原本不存在的陷阱……」
水科：「定义 0.2(ii) 不被违反……」
水科：「值相同由引 5.3 给出」
水科：「B1 与 B2 之间无支配关系，但也无 may-alias 写插入」
水科：「二者的最近覆盖 def 都是 d 前那一个……」
我点头。
水科：「故 ℓ1 = ℓ2，两处的 use 用 select 或直接替换接回……」
水科：「store 方向反过来……」
水科：「沉到 j 须 j pdom B1 与 B2，引 2.5……」
我：「啊、」
水科：「任一支执行则 j 必执行恰一次」
水科：「且 B1、B2 与 j 之间无 may-alias 读，引 5.3……」
水科：「且两侧写入的值与地址同余，GVN 意义下……」
我：「GVN？」
水科：「Scalar/NewGVN.cpp:9……」
我：「为什么？」
水科：「附带支配可折的 load 到寄存器或常量替换，load PRE……」
水科：「GVN.cpp:3113 propagateEquality」
三日月：「一样的」
水科：「调用点 :3382 与 :3407」
水科：「新建 load 时 !range 元数据原样带过去，:1663……」
我：「NewGVN 呢？」
水科：「改用稀疏形式……」
水科：「目标是补上 SSA 系 GVN 的已知不完备点……」
水科：「识别 phi(a+b, c+d) 与 phi(a,c)+phi(b,d) 等价」
水科：「以上均为 NewGVN.cpp:11 到 :45 文件头的自述」
我：「那、那个」
水科：「默认流水线跑的是 GVN……」
水科：「:774 到 :777 写的是……」
水科：「if (RunNewGVN) NewGVNPass(); else GVNPass();……」
水科：「而 RunNewGVN 由 -enable-newgvn 控制、默认 false，:215」
水科：「跨块、跨循环的重复计算合并为单点……」
水科：「EarlyCSE 已经消除了显然的冗余……」
我：「有哪几种？」
水科：「rotate、unroll、LICM……」
电车门关得比我想的快
水科：「这是它安排在循环阶段后的全部理由，定理 7.4」
水科：「纯运算：同 opcode、同 flags，且操作数逐个同余……」
水科：「load：同 Location，且最近覆盖 def 相同，引 5.3……」
水科：「否则：v = v’」
我：「v 等于 v’」
水科：「健全性对 RPO 归纳，引 3.1 保证编号时操作数已编号」
水科：「设 v 与 v’ 同余且操作数在真实执行中取值相同……」
我：「贩卖机又吞钱了」
水科：「则由纯运算的确定性得 v 与 v’ 同值……」
水科：「定义 0.1a，纯算术不是事件，结果由操作数唯一决定……」
水科：「poison 情形两侧同为 poison，引 0.4」
水科：「leader 须支配被替换点，引 2.7 的区间查询……」
水科：「否则须在汇合处插 phi……」
水科：「此时同余仍成立，但改写从替换升级为 phi 构造……」
我：「嗯、嗯、」
水科：「落回定理 2.2」
我：「不能反过来？」
水科：「NewGVN 的差别在关系本身」
水科：「故闭包条件里多了 phi of ops 与 op of phis 同值这一类等式……」
水科：「这是引 1.7 的又一次加细……」
水科：「代价是不动点迭代更慢，引 1.3 的界变大……」
水科：「对照的 RPO 算法是 Simpson 的 SCC-Based Value Numbering……」
水科：「phi-of-ops 的完备化技术取自 Pai，2015……」
我：「SCCP？」
水科：「函数级，Scalar/SCCP.cpp」
我：「就这样？」
水科：「solver 与 IPSCCP 共用」
水科：「值格乘 CFG 边格的稀疏不动点……」
我：「啊，那个」
水科：「常量沿 def-use 传播，边按条件判定剪枝……」
水科：「与 JumpThreading 的分工是值的常量性与路径上已确定的事实」
水科：「%x = add i32 41, 1 一路折叠为常量时」
水科：「这里删除的范围比 threading 更彻底……」
我：「怎么验证呢？」
水科：「证明与 IPSCCP 完全同一套论证……」
我：「意思是？」
水科：「L_v = {⊥} ∪ Const ∪ {⊤}」
水科：「L_e = {不可达 ⊏ 可达}」
水科：「转移函数单调，定理 1.5 给 MOP ⊑ MFP……」
坡道上滑了一下
水科：「推论 1.6 得判为常数即真为常数、判为不可达即真不可达……」
水科：「后者由引 0.5 授权整块删除……」
水科：「稀疏性来自 SSA……」
水科：「沿 def-use 传播只在被影响的 use 上入队，推论 2.3」
水科：「而边的处理沿 RPO，引 3.1……」
水科：「迭代轮数被嵌套深度而非指令数支配，引 1.3……」
水科：「与 JumpThreading 的分工是条件的形式」
水科：「threading 用的是某前驱路径上 c 已可判定，路径局部事实」
我：「谁的错？」
水科：「SCCP 用的是 c 的定义在全可达路径上都是同一常数，全局事实……」
水科：「标题里的 with Conditional Branches 就是本文说的边格」
“9 月 13 日”
我：「BDCE」
水科：「Scalar/BDCE.cpp」
我：「是、是、」
水科：「以 DemandedBits 结果为依据……」
水科：「自每个 use 反推实际消费的位掩码，回传……」
我假装听懂了。
水科：「shl、and、xor 一类会丢弃高位的指令……」
水科：「其产出若 demand 为空即删……」
水科：「多余扩展的 sext 顺带降为 zext，文件头注释」
我：「便当凉了呢」
水科：「它处理指令级 DCE 的盲区……」
我：「只能这样？」
水科：「shl 的结果有使用者，但只有高 16 位被消费……」
水科：「:784 流水线注释，新暴露的 DCE 机会留给稍后的 ADCE」
水科：「位格 L = 2^{0..w−1} 按包含排序，join 为并集……」
水科：「故反向不动点由定理 1.2 终止……」
我：「那、」
水科：「转移函数按 opcode 给出」
水科：「D(and x,m) = D(r) ∩ bits(m)」
我：「那是什么？」
水科：「D(shl x,k) = {i−k | i ∈ D(r), i ≥ k}……」
水科：「D(trunc_N x) = D(r) ∩ [0,N)……」
水科：「D(or/xor/add) = D(r)，两侧全传……」
水科：「D(select(c,a,b)) = D(r)，且 c 全位被需求」
水科：「删除判据：D(v) = ∅ 且 v 无副作用」
水科：「健全性：O 中每个可观测位都是若干输入位的函数……」
我：「那是什么意思？」
水科：「D 的反向闭包恰是能影响某个可观测位的位集……」
灯管又嗡了一声。
水科：「故 D(v) = ∅ 意味着 v 的任何位都不出现在任何事件里……」
水科：「删掉它 O 不变……」
水科：「sext 换成 zext 是同一判据的弱化版」
我：「唔、」
水科：「换成更便宜的 zext，逐点在被需求的位上相等……」
水科：「这是引 1.7 的典型实例……」
水科：「把 use 关系加细成位级 use 关系后」
我：「谁读？」
水科：「指令级 DCE 的不动点不再是不动点，须重算一遍」
水科：「接口 DemandedBits.h:41 class DemandedBits……」
水科：「:55 getDemandedBits(Instruction*)……」
水科：「:61 isInstructionDead，:64 isUseDead……」
水科：「改写本体 BDCE.cpp:205 BDCEPass::run」
数到第十二级就乱了
水科：「sext→zext 那一条写在 :9 到 :13 的文件头注释里」
水科：「Passes.md 没有收录此 pass，摘要以文件头为准……」
我：「DFAJumpThreading？」
水科：「:797 到 :800……」
我：「嗯，是、」
水科：「Re-consider control flow based optimizations」
水科：「after redundancy elimination, redo DCE, etc.……」
我：「硬币卡住了」
水科：「DFAJumpThreading 处理 switch 驱动的状态机……」
水科：「沿每条 threading 路径克隆块……」
水科：「让克隆体无条件跳到分析认定的下一个 case……」
水科：「DFAJumpThreading.cpp:9 的文件头带 CFG 例子」
水科：「随后 JumpThreading 与 CVP」
我：「再一遍？」
水科：「把 GVN、SCCP、BDCE 后新暴露的边与值事实再消费一轮……」
水科：「意义：GVN 与 SCCP 刚把常量传播到底……」
水科：「这是它排在此位置的全部理由，定理 7.4」
水科：「路径上的状态值经推论 1.6 已知为常量……」
水科：「故克隆体里那条 switch 的目标是编译期确定的……」
水科：「引 0.5 授权剪掉其余分支」
我：「那，是、」
水科：「克隆带来的体积增量按定义 6.3 预算……」
我：「换句话说？」
水科：「JT 与 CVP 二轮的正确性与第一轮是同一条证明……」
水科：「定理 7.4 的直接实例」
“9 月 13 日”
我：「ADCE」
水科：「Scalar/ADCE.cpp:9……」
水科：「收根：isAlwaysLive 判定的指令一律标活……」
水科：「:246 到 :259……」
我：「嗯、」
水科：「EH pad、mayHaveSideEffects() 的指令」
水科：「、非 br/switch 的终结指令……」
我：「是、」
水科：「给常量做值 profile 插桩的调用除外……」
水科：「收根的那一趟在 :198 到 :201……」
水科：「:273 markLiveInstructions」
水科：「markLiveBranchesFromControlDependences……」
水科：「补边界：从后支配树根的孩子里挑出以 return 结束的那些」
水科：「:216 到 :230……」
三日月：「呵呵」
水科：「-adce-remove-loops 的 cl::init(false) 在 :69」
我：「梅干在正中间」
水科：「optimistically assumes that all instructions are dead……」
水科：「until proven otherwise……」
水科：「死计算成批删除」
水科：「即定义 0.2(iii) 那一支义务的实现处……」
水科：「意义：正向 DCE 沿 use 链判定存活……」
水科：「ADCE 从可观测行为反向推导，把这类闭环的死代码整体删除」
我：「手好冰」
水科：「活集定义为最小不动点……」
我：「那指的是什么？」
水科：「Live = lfp(S ↦ R ∪ {ops(i) | i∈S}……」
水科：「∪ {term(B) | B 中有 i∈S}……」
水科：「其中根集 R 是产生定义 0.1a 四类事件的指令……」
水科：「W，对可观测地址的 store……」
我：「不对吧？」
水科：「C，不透明或非纯 call……」
水科：「V，volatile 与 atomic……」
手心的汗把车票印模糊了
水科：「R，return」
水科：「外加 EH pad 这类结构上不能删的指令」
我：「怎么说？」
水科：「实现里的判据就是 mayHaveSideEffects() 加 isEHPad()，:246……」
水科：「它与定义 0.1a 那张什么不是事件的表互为反面……」
水科：「从某个块出发到不了 return 的子树，无限循环」
水科：「删掉它会把 ↑ 变成有限 trace」
铅笔钝了。
我：「又走神了」
水科：「正是定义 0.2(iii) 禁止的那一类……」
水科：「故实现沿后支配树把这些子树整体标活，:216 到 :230……」
水科：「格是 2^I 按包含排序，转移单调，定理 1.2 给终止」
水科：「健全性：i 不属于 Live」
我：「谁来做呢？」
水科：「意味着 i 的结果不在任何根的操作数传递闭包里……」
水科：「且 i 所在块的执行与否不由任何根控制依赖……」
水科：「后支配树的祖先标活正是引 2.5 的用法……」
水科：「若 i 活，则决定 i 所在块是否执行的那些分支也须活……」
我：「啊、」
水科：「否则删掉分支会改变 O 中事件的发生与否……」
水科：「故删除 Live 之外的指令……」
水科：「O 逐点相同……」
水科：「与前向 DCE 的差别形式化为判据不同」
我：「那、那个」
水科：「前向用 {i | uses(i) ≠ ∅} 的不动点」
水科：「phi 与其 latch 上的 add 互相引用形成环……」
水科：「ADCE 把判据换成可观测根的反向可达」
我：「MemCpyOpt？」
水科：「Scalar/MemCpyOptimizer.cpp……」
水科：「对 memset、memcpy、memmove 序列做区间代数……」
水科：「能做哪几件事，源码开头的统计项列得最齐，:71 到 :77……」
我：「嗯、嗯、」
水科：「删掉多余的 memcpy 与 memmove」
水科：「NumMemCpyInstr、NumMemMoveInstr」
我不懂，但我记住了行号。
水科：「把一串常量 store 推成一个 memset，NumMemSetInfer……」
水科：「区间合并的数据结构就是 :81 起的 MemSetRanges……」
我：「注释举了什么例子？」
水科：「它的注释举的例子，就是四个乱序的常量 store 合成 [0,3) 一段……」
水科：「memmove 降级成 memcpy，NumMoveToCpy」
水科：「源区刚被常数写满的 memcpy 改成 memset，NumCpyToSet……」
水科：「、 call slot 与 stack-move 两类……」
我：「啊，那个」
水科：「NumCallSlot、NumStackMove……」
我：「好处是什么？」
水科：「效果：调用条数减少、长度缩短」
水科：「流水线注释给足动机，:585 与 :807 各出现一次」
水科：「Specially optimize memory movement……」
我：「是、是、」
水科：「as it doesn’t look like dataflow in SSA……」
水科：「def-use 链看不出搬运的是什么内容……」
水科：「须由专门的 pass 按地址区间处理」
水科：「引 7.5 表中对应的那一行」
我：「一次就够？」
水科：「前提都是中间无 may-alias 访问……」
水科：「由引 5.3 的最近覆盖 def 判定……」
水科：「实现 :299 accessedBetween 与 :323 writtenBetween」
水科：「第一条，memset(p,c,n1) 接 memset(p+n1,c,n2)」
水科：「≡ memset(p,c,n1+n2)，引 5.5 的区间并……」
水科：「第二条，memset(s,c,n) 接 memcpy(d,s,n)……」
我：「多久？」
水科：「≡ memset(s,c,n) 接 memset(d,c,n)……」
水科：「∵ s[0,n) 全是 c，拷贝即写常数……」
我：「有几个呢？」
水科：「第三条，memset(d,c,n1) 接 memcpy(d,s,n2)」
水科：「≡ memset(d+n2,c,n1−n2) 接 memcpy(d,s,n2)……」
水科：「前段被拷贝覆盖，引 5.5……」
水科：「:827 processMemSet，它转给 tryMergingIntoMemset」
我：「触发什么？」
水科：「邻居可是另一个 memset 或一个 store」
水科：「:1442 performMemCpyToMemSetOptzn……」
水科：「:1298 processMemSetMemCpyDependence……」
水科：「它们正是引 5.5 与定义 0.1b 的具体义务」
水科：「两个目的地址须 MustAlias，:1302」
水科：「且 n2 须可证非零，:1313……」
水科：「否则改写只是个复杂的 no-op……」
水塔的影子比我先到
水科：「方向反过来的那种截短，memcpy 在前、memset 在后……」
我：「然后呢？」
水科：「本 pass 不做」
水科：「∵ memcpy 的两个操作数不允许部分重叠……」
水科：「:1317 到 :1319 的注释……」
水科：「memcpy operands cannot partially overlap……」
我：「屋顶好晒」
水科：「exact equality is allowed……」
水科：「每条的健全性论证同构，走的都是定义 0.1b」
我：「多少？」
水科：「引 5.3 判中间无 may-alias 读，排除 OP1……」
水科：「中间无不透明 call，排除 OP2」
我：「那由谁负责？」
水科：「故它们不进任何 trace」
水科：「trace 里留下的只是每个观测点上该地址呈现的值……」
水科：「这也解释了 MemCpyOpt 为什么须依赖 MemorySSA 与 AA……」
我：「DSE？」
水科：「Scalar/DeadStoreElimination.cpp……」
水科：「沿 MemorySSA def 链，找每个 store 后下一次可能别名访问……」
水科：「:9」
我：「电车要来了」
水科：「对象不逃逸且后续无读，store 连同 alloca 整体消失」
水科：「这是唯一从内存视角删除它们的 pass……」
水科：「排在 ADCE 后……」
水科：「ADCE 刚删除一批看似有副作用的调用」
我：「刚删过一批」
水科：「判据：store s1 写 L1 是死的……」
水科：「⟺存在后继 store s2 写 L2 ⊇ L1，引 5.5 的区间包含……」
我：「那、」
水科：「且 s1 与 s2 之间不存在与 L1 may-alias 的读……」
水科：「引 5.3：若有这样的读，它取的就是 s1 的值」
水科：「删 s1 会改变 O……」
水科：「充分性：L2 ⊇ L1 使 s1 写入的每个字节都被 s2 重写……」
水科：「故两次写后的内存状态与只写 s2 相同……」
水科：「中间无读，推出无观测点，定义 0.1b 的 OP1 被排除……」
我数到三。
我：「唔、」
水科：「OP2 也须排除」
水科：「故 s1 与 s2 之间夹着不透明 call 时」
水科：「还得靠 AA，或 callee 的内存效果属性……」
水科：「memory(none)、memory(argmem: write) 这一类……」
水科：「证明该 call 读不到 L1……」
水科：「第二条路是引 5.4」
我：「嗯，是、」
水科：「store 与 alloca 一起消失……」
水科：「排在 ADCE 后的理由是引 1.4 的 join 项数减少……」
不，不对，我在数什么
水科：「ADCE 删掉的那些调用，原本是 AA 查询里的保守项」
水科：「DSE 才能执行删除……」
水科：「这是定理 7.4 的机会图里一条方向明确的边……」
水科：「ADCE → DSE……」
“9 月 13 日”
我：「最后那一串」
水科：「:811 到 :827」
我：「谁先谁后？」
水科：「MoveAutoInit，再一轮 LICM，CoroElide……」
水科：「SimplifyCFG 带 hoist/sink，InstCombine……」
三日月：「都写着」
水科：「MoveAutoInit 把标记为 auto-init 的指令挪近真正使用它的块……」
水科：「Utils/MoveAutoInit.cpp:9 的注释」
水科：「moves instruction maked as auto-init closer to……」
水科：「the basic block that use it……」
我：「什么时候？」
水科：「eventually removing it from some control path……」
背面已经写满了。
水科：「接着是正文里叫 LPM3 的那段循环流水线」
水科：「里面只装了一件 LICM，:813」
水科：「CoroElide 处理协程帧的分配与销毁……」
我：「什么顺序呢？」
水科：「最后 SimplifyCFG 带 hoist/sink 再清一次图……」
水科：「InstCombine 再折一次表达式……」
水科：「ADCE 与 DSE 后新出现的不变量与冗余，被再消费一轮」
我：「坡道好陡」
水科：「意义：NPM 不追求全局不动点……」
我：「什么时候呢？」
水科：「每个清理 pass 本身就是下一轮优化机会的来源……」
水科：「用机会算子表述」
水科：「设 x_k 为第 k 个位置后的 IR」
水科：「GVN 与 SCCP 后……」
水科：「O_LICM(x_GVN) 真包含 O_LICM(x_LPM1)……」
水科：「∵ GVN 把跨循环重复折成单点后，新的循环不变量出现了……」
我：「啊、啊、」
水科：「SCCP 把常量传到底后……」
水科：「故 CVP 的事实集与 JT 的可 threading 边都变多……」
我：「梅干在正中间」
水科：「由定理 7.4，重复执行不是冗余，而是拓扑序的必要补边……」
我：「为什么不迭代到全局不动点？」
水科：「∵引 7.2 的前提不成立……」
水科：「InstCombine 的规则集不终止」
水科：「且各 pass 之间存在互相创造应用条件的环」
我：「哪一层呢？」
水科：「LICM 出现在 rotate 前、后与清理阶段各一次」
水科：「:714、:720、:814」
我：「那，是、」
水科：「InstCombine 每在一批改写后就排一次……」
水科：「:667、:758、:791、:827……」
我：「嗯、」
水科：「SimplifyCFG 同样……」
水科：「:666、:681、:757、:822」
水科：「另有 :651 那一处只在 GVN-sink 打开时才排」
水科：「EarlyFPM 与模块优化阶段另有若干次……」
水科：「这条流水线本身又被内联器逐个 SCC 嵌套调用……」
我：「怎么看完整清单？」
水科：「用 opt -passes=’default
水科：「MoveAutoInit 那一件另走引 2.4……」
水科：「把它挪近使用点满足 M1，操作数是 alloca 地址与常量……」
水科：「M2，落点支配全部 use」
水科：「M4，中间不得有 may-alias 写，否则初值被覆盖」
水科：「省掉的那些路径上它本来也不被执行，故 O 不变……」
我：「是、」
水科：「还有 DropUnnecessaryAssumes……」
水科：「向量化后就调它一次，:1350……」
我：「下半场就是在打扫……」
水科：「打扫完，还要再看一眼谁活着」
第十二章 Last Shape 「只放大最终的形态」
“9 月 13 日”
水科：「模块优化流水线，:1508……」
水科：「EliminateAvailableExternally 与 ReversePostOrderFunctionAttrs」
冰块响得比蝉早
水科：「:1527」
水科：「前者删掉非 LTO 场景不再须的 available_externally 定义」
水科：「后者在此 commit 里范围很窄……」
我：「什么顺序呢？」
水科：「做的是自顶向下的两条推断，caller 先于 callee……」
我：「手好冰」
水科：「先把调用图按 RefSCC 后序收集，再反向走一遍得到此次序……」
水科：「:2402 deduceFunctionAttributeInRPO……」
水科：「只对内部链接、有定义、仍被使用的单函数 SCC 动手」
水科：「:2417 到 :2420……」
水科：「逐函数调 :2323 addNoRecurseAttrsTopDown……」
水科：「若 F 的全部使用都是已标 norecurse 的函数里的调用……」
我：「不对吧？」
水科：「则 F 也标 norecurse」
水科：「:2353 addNoFPClassAttrsTopDown」
水科：「把全部调用点上观察到的 nofpclass 事实按位取交……」
水科：「写回 F 的参数与返回值……」
水科：「available_externally 的定义体退化为声明……」
水科：「callee 声明上的 norecurse 与 nofpclass 变多……」
水科：「意义：与逆拓扑的 PostOrderFunctionAttrs 方向相反……」
我：「谁保证？」
水科：「归纳推断，由 callee 的已知属性推自身……」
水科：「与代入推断，caller 把已知事实写给 callee」
水科：「互为反向」
灯管嗡了一声。
水科：「available_externally 的定义是仅供优化参考、不会被发射……」
水科：「它从未出现在 O 里……」
我：「多久？」
水科：「但它若留着，会继续充当 GlobalDCE 的引用材料」
水科：「定理 7.4 的同一逻辑……」
水科：「给 F 标 norecurse，⟺……」
水科：「对一切使用 U，U 是一个调用且调用方已标 norecurse」
水科：「给 F 的参数 i 标 nofpclass = C……」
水科：「⟺ C 是全部调用点上 C_cs 的交……」
我：「确定？」
水科：「按引 1.4，第二条就是全调用点结论的 meet」
水科：「:2331 assert(F.hasInternalLinkage()……」
水科：「&& Can only do top-down deduction」
水科：「for internal linkage functions!)」
我：「那、那个」
水科：「norecurse 那一条还额外要求使用须真的是调用……」
水科：「:2342 到 :2347 的 CB->isCallee(&U)……」
水科：「否则函数地址可能被一个 norecurse 函数返回出去……」
我：「嗯、嗯、」
水科：「逆拓扑那趟给出 A(f) 不保守于本地事实与 callee 闭包……」
水科：「正拓扑这趟给出 A(f) 不保守于 caller 侧事实……」
水科：「两次 meet 后属性集单调变小，信息单调变多……」
水科：「且都由定理 1.2 保证有限步收敛」
我：「Float2Int？」
水科：「Scalar/Float2Int.cpp:9」
水科：「文件头把算法写得很短……」
水科：「demote floating point operations to work on integers……」
我：「冰化了呢」
水科：「where that is losslessly possible……」
我翻到背面。
水科：「fptoui、fptosi、fcmp，:89 findRoots……」
水科：「沿 def-use 反向走……」
水科：「为链上每条浮点指令算一个 ConstantRange……」
水科：「:116 seen、:203 calcRange」
水科：「三态判定在 :122 到 :129」
水科：「碰到 uitofp 或 sitofp 就停，那是链的入口……」
我：「谁在用？」
水科：「:314 validateAndTransform、:404 convert」
水科：「opcode 映射 :78 mapBinOpcode」
水科：「比较谓词映射 :51 mapFCmpPred……」
水科：「整数位宽上限由 -float2int-max-integer-bw 控制……」
水科：「:45 的 cl::init(64)……」
我：「收据飞走了」
水科：「浮点指令序列变成整数指令序列」
水科：「整数化后的表达式，重新落入 SCEV 与 GVN 的恒等式适用范围……」
猜拳出了两次一样的
水科：「设 x 是 w 位整数，浮点格式尾数 p 位」
水科：「binary32 的 p = 24……」
水科：「则 |x| < 2^p 推出 sitofp(x) 精确……」
水科：「推出 fptosi(sitofp(x)) = x……」
水科：「且在该范围内 sitofp 保序，单射加单调……」
水科：「故 fcmp olt(sitofp(i), sitofp(j))」
我：「什么前提？」
水科：「≡ icmp slt(i,j)，只要 |i| 与 |j| 都小于 2^p」
我：「什么条件？」
水科：「范围前提由 Float2Int 自己的 ConstantRange 三态传播给出……」
水科：「badRange、unknownRange、validateRange……」
水科：「必要时由 SCEV 补……」
三日月：「不急」
水科：「这是引 4.3 的同一套可表示性检查」
水科：「证明不出来的步骤不改写」
水科：「保守方向又一次由推论 1.6 保证……」
“9 月 13 日”
我：「再整形」
水科：「:1609 到 :1641……」
我：「找零口堵着」
水科：「几个只改结构、不改算术的 pass……」
水科：「LoopRotate 重转」
水科：「注释 :1598 说明 SimplifyCFG 等 pass……」
水科：「这一次带 CheckExitCount=true，:1611……」
水科：「然后 LoopDeletion 再删……」
水科：「然后 LoopInterchange」
水科：「排入条件是 PTO.LoopInterchange，:1618……」
我：「所以？」
水科：「该值在 opt 里默认取自 -enable-loopinterchange 的 cl::init(true)……」
水科：「:219」
水科：「clang 里则由 -finterchange-loops 经 BackendUtil.cpp:901 覆盖……」
我：「多久一次？」
水科：「然后 LoopFuse」
水科：「trip count 一致的相邻循环合并，省掉一遍索引」
水科：「排入条件是 PTO.LoopFusion，:1626……」
我：「几遍？」
水科：「PTO 构造式里写死 :338 的 LoopFusion = false;……」
我：「一次就够？」
水科：「clang 侧对应 -ffuse-loops，BackendUtil.cpp:902……」
水科：「然后 LoopDistribute」
水科：「只对带 llvm.loop.distribute=true 元数据……」
水科：「或开了 -enable-loop-distribute 的循环生效……」
水科：「:1629 的注释就是这么写的」
水科：「嵌套深度、层序、依赖分布三项调整到位……」
我：「伞忘带了」
水科：「指令数不变」
水科：「重转：SimplifyCFG 的合块规则……」
我：「又走神了」
水科：「会把尾测形的 latch 与 header 合并」
水科：「从而把 do-while 变回 while-do」
水科：「定理 4.4 的前提，body 是直线块，失效……」
水科：「等价性证明与第一次完全相同，定理 4.4 是双向的……」
水科：「interchange：σ(i,j) = (j,i)」
我：「凭什么？」
水科：「按定理 4.5 合法，⟺一切依赖向量在新维序下字典序非负」
水科：「即原 d⃗ = (d1,d2) 满足 d2>0，或 d2=0 且 d1≥0……」
水科：「原内层按 i 步进，stride = m·s……」
我换了三次手。
水科：「变成按 j 步进，stride = s……」
水科：「即 LoopVectorize 的连续访存前提」
我：「是、是、」
水科：「fuse：引 4.6 的精确条件……」
水科：「无 B2→B1 依赖，B1→B2 距离 ≥0……」
我：「然后呢？」
水科：「distribute：定理 4.5 的 distribute 推论……」
水科：「把 body 的语句分成 G1 与 G2 后分别成为循环……」
水科：「合法⟺不存在 G2→G1 的依赖」
水科：「收益是把带依赖的访存组隔离，使 G1 保住向量资格……」
水科：「distribution 与 fusion 的依赖判据……」
我：「LoopVectorize？」
水科：「addVectorPasses，:1341」
水科：「Vectorize/LoopVectorizationLegality.cpp……」
水科：「LAA 给出依赖三分类……」
我：「为什么？」
水科：「静态可证的循环，按代价模型选出的向量宽度 VF」
水科：「模型本体是 LoopVectorize.cpp:764 起的 LoopVectorizationCostModel……」
水科：「无法向量化的依赖按 reduction、gather、scatter 特化」
水科：「效果：每迭代 N 条标量运算合并为一条向量运算……」
我：「谁来做呢？」
水科：「意义：吞吐提升 VF 倍由硬件给出……」
我：「代价呢？」
水科：「它放大的是此刻已成形的 IR」
水科：「LCSSA phi 与 unroll 留下的冗余都会进入代价模型」
水科：「调度 σ(k) = (⌊k/VF⌋, k mod VF)……」
水科：「第 ⌊k/VF⌋ 个向量迭代的第 k mod VF 条 lane……」
水科：「承担原第 k 次迭代……」
水科：「逐项验证定理 4.5 的约束」
收据在口袋里响了一声。
水科：「(i) 依赖……」
我：「谁读它？」
水科：「距离 d ≥ VF 的跨向量迭代依赖被 σ 保序……」
水科：「d = 0 的循环内依赖由向量体内语句顺序保持……」
水科：「lane 内顺序即原语句顺序」
水科：「0 < d < VF 的依赖非法」
我：「只能这样？」
水科：「除非它是被识别的 reduction 或 induction……」
水科：「(ii) reduction……」
水科：「把 k 从 0 到 n−1 的 ⊕ 重排成先按 lane 再按组……」
水科：「整数加减在 Z_{2^w} 中无条件成立，引 4.7」
我：「那、」
水科：「浮点须 reassoc 授权，否则这条推论不可用……」
水科：「即浮点 reduction 不向量化的全部理由……」
水科：「(iii) 访存……」
水科：「连续访问，stride 等于元素大小，映射为一条向量 load 或 store」
我：「唔、」
水科：「非连续映射为 gather 或 scatter」
我：「怎么验证呢？」
水科：「may-alias 的指针对生成运行期检查……」
水科：「两支各自满足 (i)，引 0.5 的镜像用法……」
水科：「与 LAA 那条证明相同……」
啊哈哈，又走神了
水科：「(iv) 余数」
水科：「EC = VF·q + r 时，生成 q 个向量迭代加 r 个标量迭代……」
水科：「迭代序列与原循环逐一对应，引 4.2 的闭式给出 q 与 r……」
我：「嗯，是、」
水科：「(v) 指针递进……」
我：「屋顶好晒」
水科：「按 VF·s 步进，宽度取足以避免回绕，引 4.3」
水科：「排在最后的理由由定理 7.4 给出」
水科：「而形态在 LPM2 与再整形两节才定型……」
水科：「提前做会把 LCSSA phi 与 unroll 留下的冗余……」
我：「在哪里？」
水科：「且向量化后的 IR 很难被标量 pass 还原」
水科：「runtime check 的生成点 LoopVectorize.cpp:1172……」
我：「SLPVectorize？」
水科：「Vectorize/SLPVectorizer.cpp:9……」
水科：「排入条件是 PTO.SLPVectorization，:1444」
水科：「clang 侧由 -fslp-vectorize 经 BackendUtil.cpp:907 设定」
我：「谁的错？」
水科：「自底向上……」
水科：「通常是连续 store，或对向量操作数的逐元素运算……」
水科：「沿 use-def 链向上构造打包树……」
水科：「效果：直线代码中的独立标量链合并为向量运算加 shuffle」
我：「啊、啊、」
水科：「unroll 留下的多份直线副本正是它的输入……」
水科：「与 LoopVectorize 互补……」
水科：「向量化为一条 VF 宽指令的健全性条件是 lane 独立」
水科：「对一切 i ≠ j，o_i 与 o_j 之间无数据依赖……」
我：「嗯、」
水科：「各自的 def-use 子图不交……」
水科：「访存则要求 AA 判 NoAlias 或区间不交，引 5.5……」
水科：「在此条件下 SIMD 的逐 lane 语义与标量序列的语义逐点相同」
水科：「vop(a1..aVF, b1..bVF)_l = op(a_l, b_l)，对一切 l」
或者说，我只是不想排队
水科：「对树高归纳」
水科：「叶子由 pack 与 shuffle 重排到位……」
水科：「shufflevector 的索引恒等式，见 VectorCombine 那条证明……」
水科：「内部节点按上式逐 lane 成立……」
我：「逐 lane」
水科：「代价核算按定义 6.3」
水科：「收益是 VF 条标量折成 1 条……」
我：「代价是什么？」
水科：「成本是必要的 shuffle 与 pack……」
水科：「故 SLP 经常出现打包比不打包更贵的负收益树……」
我：「是、」
水科：「superword」
“9 月 13 日”
我：「收尾那几件」
水科：「LoopSink、InstSimplify、DivRemPairs……」
水科：「MergeICmps 与 ExpandMemCmp……」
水科：「LoopSink 把 LICM 提到 preheader、但使用点频度更低的指令……」
三日月：「一样的」
水科：「文件头自述是 the inverse transformation of what LICM does」
水科：「用 alias set tracker 拿更准的别名信息……」
水科：「用 BFI 找最优落点，LoopSink.cpp:9……」
水科：「函数带运行期 profile 数据才干活」
水科：「:360 if (!F.hasProfileData())」
水科：「return PreservedAnalyses::all();……」
水科：「With static profile, the sinking decision may be sub-optimal……」
水科：「InstSimplify，Scalar/InstSimplifyPass.cpp」
我：「坡道好陡」
水科：「单遍折掉 LCSSA phi 残留与单引用 trivial……」
水科：「DivRemPairs，Scalar/DivRemPairs.cpp:9……」
水科：「把同被除数与除数的 {x/d, x%d} 配对……」
水科：「文件头自述，hoists and/or decomposes/recomposes……」
我：「啊、」
水科：「integer division and remainder instructions……」
水科：「MergeICmps 把逐字节 icmp+and 链识别回 memcmp……」
水科：「Scalar/MergeICmps.cpp:9……」
我：「要按什么次序？」
水科：「ExpandMemCmp 再把 memcmp 展开」
我：「那、那个」
水科：「成对目标最优的 load 加比较序列」
水科：「文件头，expand memcmp() calls into……」
水科：「optimally-sized loads and compares for the target……」
水科：「Scalar/ExpandMemCmp.cpp:9……」
我：「蝉还在叫啊」
水科：「意义：它们共同处理一类非算术 IR……」
水科：「SSA 数据流视角看不到的那部分……」
我：「那是什么？」
水科：「LoopSink 是 LICM 的逆运算……」
水科：「合法性同走引 2.4 的 M1–M4，方向相反」
我：「换句话说？」
水科：「M2 要求落点支配全部 use」
水科：「M3 由 f_落点 < f_preheader 给出收益……」
水科：「存在的理由正是注记 6.4……」
水科：「LICM 当时的 Δ 是用当时的频度与寄存器压力算出的……」
水科：「可能不准，须有 pass 回头修正」
我数到三。
水科：「这也是它开头就要查 hasProfileData() 的原因」
水科：「源码注释写的就是静态 profile 下下沉决定可能更差……」
水科：「InstSimplify 的主力是 trivial phi……」
我：「一定要吗？」
水科：「φ[v] 只有单一入项时，phi 的选择函数恒取 v」
水科：「定理 2.2 的构造在 |J⁺| = 0 时退化……」
水科：「故 φ[v] ≡ v……」
我：「那由谁负责？」
水科：「DivRemPairs：由整数除法的定义 x = q·d + r……」
我：「鞋带松了」
水科：「其中 q = x sdiv d，截断向零，r = x srem d」
水科：「故 r = x − q·d 逐点成立」
水科：「唯一的溢出隐患是 q·d……」
水科：「q = INT_MIN、d = −1 时乘法回绕……」
我：「那不是 UB 吗？」
水科：「但该情形下 sdiv INT_MIN, -1 本身就是 UB……」
水科：「由引 0.5，这些执行不须保护」
我：「贩卖机又吞钱了」
水科：「故在非 UB 的全部执行中 |q·d| ≤ |x|，不回绕」
水科：「MergeICmps 与 ExpandMemCmp……」
我：「那是什么意思？」
水科：「n 字节 memcmp 的语义是字节串的字典序比较……」
水科：「cmp(a,b) = sgn( Σ (a_k − b_k)·2^{8(n−1−k)} )」
水科：「故在小端机上按字展开，须先 bswap 再做无符号比较……」
水科：「尾块单独处理 n mod W 字节……」
我：「那指的是什么？」
水科：「W 是机器字长的字节数……」
我：「那不行吗？」
水科：「逐字节 icmp+and 链反向识别回 memcmp」
我：「再来一轮内联？」
水科：「buildModuleInlinerPipeline，:1064……」
水科：「算法与内联一节相同，把 callee 复制进来，就地再简化一轮……」
水科：「效果：LTO 导入与新直接边产生的调用点得到同等待遇……」
我：「便当凉了呢」
水科：「新直接边来自 devirt 前置与内联解锁」
水科：「整条逐函数流水线作为模块级 pass 的附属部分再执行一遍……」
水科：「一条指向 SCCP 与 GVN……」
我：「嗯、嗯、」
水科：「buildModuleInlinerPipeline 就是这次截断……」
水科：「由定理 7.4，不再简化就等于放弃这一轮内联的全部收益……」
“9 月 13 日”
水科：「收尾」
水科：「:1723」
水科：「真实次序是 :1701 GlobalDCE……」
水科：「:1702 ConstantMerge……」
水科：「:1707 MergeFunctions」
贩卖机的灯闪得没规律
水科：「最后才是 devirt」
水科：「WholeProgramDevirt 消费前奏 CalledValuePropagation 的 !callees……」
我：「啊，那个」
水科：「源码统计项 NumSingleImpl」
水科：「WholeProgramDevirt.cpp:127……」
水科：「branch funnel，接 direct call」
水科：「只对用了 llvm.assume(llvm.type.test)……」
我：「冰化了呢」
水科：「或 llvm.type.checked.load 的调用点动手，:30……」
水科：「另有不限 LTO 的 speculative 模式……」
水科：「-devirtualize-speculatively，:52」
水科：「GlobalDCE 沿引用图删失去引用的 internal 全局与 vtable 项」
我：「那、」
水科：「GlobalDCE.cpp:9……」
水科：「ConstantMerge 合并重复常量……」
水科：「MergeFunctions 先算结构哈希……」
水科：「:1122 mergeTwoFunctions」
我把行号抄在收据背面。
水科：「一方是 interposable，链接期可能被别的翻译单元里的同名定义替换……」
水科：「或双方都受 ODR 约束……」
水科：「One Definition Rule，同一实体在各翻译单元里的定义须相同」
水科：「新建一个 internal 函数，让两边都变成跳到它的 thunk」
水科：「跳板函数，:1126……」
我：「有哪几种？」
水科：「间接调用数趋近于零、全局表变小、代码体积下降……」
水科：「意义：调用目标从运行期查 BTB……」
水科：「branch target buffer，硬件用来预测间接跳转目标的表」
我：「唔、」
水科：「devirt 的健全性前提是候选集 S 完备」
水科：「S ⊇ S_运行期，CalledValuePropagation 那条证明……」
水科：「|S|=1 时改直调，事件集不变……」
我：「嗯，是、」
水科：「间接与直接跳转都不在 O 中……」
我：「一次就够？」
水科：「被调函数的 body 执行序列相同」
水科：「|S|>1 时构造 guard 链」
水科：「if (fp == &f1) f1() else if …… else fp()……」
水科：「对 S 做穷尽情形分析……」
梅干总是在正中间
水科：「完备性要求全程序可见，即 LTO」
水科：「故 pass 只处理 llvm.type.test 与 llvm.type.checked.load 覆盖的点……」
我：「啊、啊、」
水科：「GlobalDCE：从根在模块引用图上做可达性……」
水科：「不可达的全局，其地址从不进入 O」
水科：「定义 0.1a 的可观测性，删除不改变任何事件……」
水科：「ConstantMerge：两个逐字节相同的常量合并为一个……」
水科：「须 unnamed_addr……」
水科：「合并会改变 icmp eq ptr 的结果」
我：「那，是、」
水科：「带 unnamed_addr 时地址身份不可观测，故合并安全……」
我：「嗯、」
水科：「MergeFunctions：结构同构……」
水科：「使每条指令的 opcode、flags、类型一致」
水科：「φ 是双模拟，bisimulation……」
水科：「两侧的执行步一一对应且产生相同事件，故 O 相同……」
我：「默认的 -O2 会跑这些吗？」
水科：「不会全跑」
水科：「MergeFunctions 只在 PTO.MergeFunctions 为真时排入」
水科：「:1706……」
三日月：「呵呵」
水科：「而此值默认取自 -enable-merge-functions 的 cl::init(false)……」
窗外还是黑的。
水科：「:191」
水科：「clang 侧由 -fmerge-functions 经 BackendUtil.cpp:908 覆盖……」
水科：「WholeProgramDevirt 在这一段」
我：「硬币卡住了」
水科：「只在 -enable-devirtualize-speculatively 打开」
水科：「且不是 LTO 时才排入」
水科：「:321 的 cl::init(false)，:1718……」
我：「谁先谁后？」
水科：「LTO 流水线里则是无条件排的……」
水科：「ThinLTO post-link :1969……」
水科：「full LTO pre-link :2039」
水科：「ThinLTO pre-link :2120」
水科：「」
水科：「默认的 clang -O2，非 LTO，在这一段实际只跑……」
我：「是、」
水科：「GlobalDCE 与 ConstantMerge……」
水科：「函数合并与去虚拟化，要额外开关或走 LTO……」
我：「故清单上有些名字，其实是睡着的……」
水科：「睡着的」
我把收据翻到正面。
158 那个数字也淡了。
现在正面是一张白纸。
第十三章 Data 「把次序表达为数据」
“9 月 13 日”
我：「谁读？」
水科：「New Pass Manager……」
水科：「前面各章讲的是次序为什么是这样，定理 7.4 的机会图」
我：「什么时候呢？」
水科：「与每一步为什么合法，T0 到 T7」
水科：「NPM 自身承担的职责很少……」
水科：「原因在于次序不再由 C++ 的调用链表达，而是变成了数据」
水科：「它被移入 PassRegistry.def 与解析器……」
我：「五条？」
水科：「第一，pass 与调度解耦……」
水科：「pass 是实现 run(Unit&, AnalysisManager&) 的普通对象……」
水科：「对一层内每个成员各执行一次，由 manager 或 adaptor 负责」
我：「谁读它？」
水科：「pass 对遍历无感知」
水科：「结论缓存在 AnalysisManager……」
水科：「键为（分析 ID，IR 对象地址）……」
水科：「每个 pass 返回 PreservedAnalyses」
我：「啊、」
水科：「manager 每执行完一个 pass 立刻 invalidate……」
我：「那、那个」
水科：「PassRegistry.def 一张 X-macro 表……」
水科：「一个 .def 文件里只写宏调用列表」
水科：「包含方各自定义宏体」
水科：「它登记了全部变换 pass 与分析的名字与构造式……」
水科：「变换按 MODULE、CGSCC、FUNCTION、LOOP 四个层次……」
水科：「各有 *_PASS 与 *_PASS_WITH_PARAMS 两类宏」
排到我时按钮全灭了
水科：「分析同样按四个层次各有 *_ANALYSIS 宏」
我：「多少次？」
水科：「:353 到 :392 是 FUNCTION 那一段……」
水科：「想知道确切有多少个，按宏名前缀 grep 此文件数一遍即可……」
水科：「PassBuilder::parsePassPipeline」
水科：「PassBuilder.cpp:2718……」
我：「哪一层？」
水科：「把 function(sroa,loop-mssa(licm)) 解析成 manager 树」
水科：「首 pass 层次不够时，自动向上补 adaptor」
我：「谁？」
水科：「pass 选项即构造函数参数……」
水科：「sroa
我：「什么时候？」
水科：「PassInstrumentation 回调贯穿每个 pass 前后」
水科：「runBeforePass 返回 false 即整体跳过……」
水科：「-print-before 与 -print-after 全部实现在这几个回调槽上……」
我：「主循环呢？」
水科：「PassManagerImpl.h:28……」
水科：「逐 pass 的固定顺序」
水科：「PI.runBeforePass 判定，:73」
窗外还是黑的。
水科：「Pass->run，:76……」
水科：「AM.invalidate，:80……」
水科：「PI.runAfterPass，:84……」
水科：「PA.intersect，:88」
我：「谁的错？」
水科：「收尾再对本层缓存整体声明 preserve，:95……」
我：「第一条为什么重要？」
水科：「它是本文能按定理到引用组织的前提……」
我：「为什么？」
水科：「pass 不知道自己被调度在哪一层……」
水科：「故同一条引理，例如引 2.4 的 M1–M4……」
我：「哪一层呢？」
水科：「可被 LICM 在 loop 层引用、被 LoopSink 在 function 层引用」
我：「第三条呢？」
水科：「它是定理 7.4 能被验证的前提……」
水科：「次序若硬编码在 C++ 调用链里……」
水科：「它是数据」
我：「找零口堵着」
水科：「故 opt -print-pipeline-passes 能把本文的目录原样输出」
“9 月 13 日”
水科：「变换用 adaptor……」
我：「在哪一阶段？」
水科：「ModuleToFunctionPassAdaptor 逐函数驱动内层流水线……」
水科：「并逐函数作废缓存，PassManager.cpp:107……」
我：「啊，那个」
水科：「分析缓存用 proxy」
水科：「InnerAnalysisManagerProxy，PassManager.h:601」
水科：「设计说明在 :588 起的注释……」
水科：「FunctionToLoopPassAdaptor 额外携带契约……」
我：「是、是、」
水科：「进入 loop 流水线前强制补 LoopSimplify 加 LCSSA」
我：「在哪里？」
水科：「结构被改写时经 LPMUpdater 维持次序不变量……」
水科：「LoopPassManager.h:13……」
水科：「adaptor 的义务是把内层流水线的 preserve 声明……」
我：「只能这样？」
水科：「内层对函数 f 执行完后，只有 f 的缓存可能失效……」
水科：「内层 pass 不得跨函数改写」
水科：「IR 的分层容器结构保证，Module 层以下的 pass 拿不到别的 Function」
我：「那、」
水科：「违反者，内联，须放在 CGSCC 或 Module 层……」
我：「那不行吗？」
水科：「即内联器不能写成 FunctionPass 的形式理由……」
水科：「proxy 的义务是闭包条件……」
水科：「故整体作废」
水科：「FunctionToLoopPassAdaptor 的契约……」
我：「顺序呢？」
水科：「则是引 3.5 与 (C1)–(C4) 的进场条件……」
水科：「内层先，引 3.5；规范形，(C1) 到 (C4)」
罐子凉透了。
水科：「两者都是 loop pass 证明里被反复引用的前提」
水科：「而不是让每个 pass 自己检查……」
我：「其余的机制呢？」
水科：「都是工程细节……」
水科：「懒算，getResult 缓存未命中才构建」
水科：「requires 的子分析迭代到不动点后按序补齐」
手心还是冰的
水科：「成环直接 assert……」
水科：「RequireAnalysisPass 预热，PassManager.h:913……」
我：「在哪一行呢？」
水科：「InvalidateAnalysisPass 丢弃，:940……」
水科：「文本名注册于 PassRegistry.def 的 *_ANALYSIS 节」
水科：「:353 到 :392」
水科：「只有一条单独证明」
水科：「缓存健全性」
水科：「定义 N.1……」
我：「唔、」
水科：「分析缓存 C ⊆ A × Addr……」
我：「不对吧？」
水科：「(A,u) ∈ C 读作 A 对 IR 单元 u 的结论已算出并缓存……」
水科：「不变量 (I)」
水科：「对一切 (A,u) ∈ C，A(u) 的缓存结论对当前 IR 仍成立」
我：「仍成立」
水科：「引理 N.2，主循环维持 (I)……」
水科：「设 pass P 声明的 preserve 集合为 S_P……」
水科：「且 P 的声明是真的……」
我：「伞忘带了」
水科：「S_P ⊆ {A | A 的结论在 P 后仍成立}」
我：「换句话说？」
水科：「则主循环 run P 再 invalidate C∖S_P 后，(I) 保持」
水科：「证明对 pass 序号归纳……」
水科：「设 P 前 (I) 成立……」
水科：「P 后被删的是 ¬S_P 中的条目……」
水科：「留在 C 里的条目全在 S_P 中」
水科：「P 运行期间新算出的条目由构造成立……」
我：「啊、啊、」
水科：「分析总是对当前 IR 计算……」
水科：「故 (I) 在 P 后成立……」
我：「引理 N.3？」
水科：「方向的不对称」
水科：「引 1.4，多层结论取 join，任一层不确定则整体不确定……」
水科：「而 preserve 的声明是乐观的……」
水科：「引理 N.2 的前提无法被检查……」
水科：「声明不成立——pass 说保住了某份结论、实际没保住……」
我：「那，是、」
水科：「则 (I) 被破坏……」
水科：「下游 pass 会用针对旧 IR 的结论去改写新 IR……」
三日月：「都写着」
水科：「产出语义错误的程序」
水科：「而且形态合法，Verifier 不报」
我：「键还是该地址……」
水科：「故 PreservedAnalyses 的默认值是 none()……」
水科：「而 all() 须显式书写、逐个 pass 审计」
水科：「LPM2 的那几个 pass 不 preserve MemorySSA……」
水科：「LPM2 进 loop 时直接传 UseMemorySSA=false，:763……」
水科：「注释在 :759」
我：「SCEV 呢？」
水科：「顺带解释了分析章那句 abandon 用得最多的就是 SCEV……」
水科：「SCEV 的结论是对当时 IR 的符号推导……」
水科：「引 4.2 的闭式依赖具体的 def-use 形状」
我：「就这样？」
水科：「而是否失效，没有代价低的判据……」
水科：「故它默认不被 preserve……」
水科：「引理 N.3 的乐观声明在这里被彻底放弃……」
我：「多少？」
水科：「改成每轮重建，重建有界，引 1.3」
“9 月 13 日”
灯管嗡了一声。
然后，有人站在门口。
我不知道他什么时候来的。
他把手按在门框上，指节很白。
神代：「听好了！」
神代：「次序不在代码里！」
神代：「次序在表格里！」
神代：「ＰａｓｓＲｅｇｉｓｔｒｙ．ｄｅｆ！」
神代：「故它可被打印！可被解析！可被重排！」
神代：「Ｎｅｗ ＰＭ 省掉的那一层，正是次序本身！」
神代：「作废作废作废作废作废作废作废作废作废作废作废作废作废作废作废！」
神代：「谁来宣布收敛？」
神代：「是该敢在 PreservedAnalyses 上写下 all() 的人！」
神代：「而该人——就是我！」
他笑了。
笑完之后，门框上留下一个手印。
然后就走了。
水科：「别理他」
水科：「all() 须显式书写……」
我：「负责到什么程度？」
水科：「负责到形态合法、语义错误、而没有任何工具会报警的程度……」
“9 月 13 日”
水科：「验证」
1 | # 把 -O2 的完整清单打出来（本文目录的机器可读版） |
我：「第一条能打出全部？」
水科：「全部」
水科：「包括 loop-flatten」
我：「那我试试」
我把命令敲进去。
回车。
输出滚了很久。
水科：「怎么了」
我：「没有 loop-flatten……」
水科：「不可能」
我：「自己看」
她抢过键盘，往上翻。
翻了很久。
水科：「-enable-loop-flatten……」
水科：「cl::init(false)，:226……」
我：「嗯、」
水科：「默认关闭」
我：「那你刚才说」
水科：「我把它跟 -enable-loopinterchange 记混了……」
水科：「该是 cl::init(true)，:219」
我：「啊哈哈」
水科：「不许笑」
我：「没笑」
水科：「你在笑」
我：「……啊哈哈」
水科：「超一千倍蠢」
我：「是我蠢吗」
水科：「是我」
她说完这句之后，安静了大概五秒。
然后重新开始念。
水科：「清单，对应定理 7.4 的拓扑序……」
水科：「前后 IR，对应每个 pass 的效果一栏……」
收据在口袋里响了一声。
水科：「verify，对应定义 0.2 的形态侧」
我：「有哪几种？」
水科：「算法、效果、意义、证明……」
我：「Legacy PM 呢？」
水科：「Legacy Pass Manager，NPM 前的那套 pass 调度框架……」
水科：「该时代，这些次序散落在各个 driver 的 addPass 调用序列里」
水科：「NPM 把同一条清单变成可读、可打印、可用文本复现的数据结构」
我：「故整篇讲的东西，最后是一张表」
水科：「最后是一张表……」
我：「然后呢？」
水科：「然后有人去 grep……」
水科：「grep 很久」
水科：「最后发现是三年前有人写了一个 all()」
窗外天还是黑的。
可是黑得不那么彻底了。
终章 Wonderful Everyday 「美好的每一天」
“9 月 13 日”
天快亮的时候，坡道上开始有货车经过。
我们把桌子上的东西收了一遍。
收据被压在最下面。
正面全白了。
一个字也不剩。
背面还在。
四栏，铅笔，划掉的比留下的是我的两倍。
我：「这么早？」
水科：「趁还记得」
收据被风吹跑了
水科：「通用理论」
水科：「T0 到 T7 这批工具覆盖了后文全部证明，每件都有若干消费者」
我：「怎么说？」
水科：「T0 精化，事件字母表 W/C/V/R 加三类结局 τ、⊥、↑」
水科：「T1 格，T2 支配，T3 遍历序，T4 循环代数……」
水科：「T5 内存版本，T6 频度，T7 规范化……」
水科：「被引最多的是引 0.5，UB 可剪……」
水科：「覆盖面最宽的是引 2.4 的 M1–M4」
我：「罐子空了呢」
水科：「凡是在 IR 里移动指令的改写都要满足这四条」
水科：「分析 Pass……」
水科：「图分析回答是否允许改写，支配、循环、调用图，T2 与 T3……」
我：「谁在用？」
水科：「数据流分析回答改写是否安全，SCEV、MemorySSA、AA、LAA」
水科：「T1、T4、T5」
水科：「元信息回答改写是否有收益，频度、assume、TLI，T6……」
铅笔钝了。
水科：「模块级前奏」
我：「有哪几种？」
水科：「属性标注、expect 降级、全局常量化、必选内联展开……」
水科：「后 profile 与内联阈值才度量得准」
水科：「引 1.4 的项数越少越保守」
水科：「SCC 逆拓扑，推论 3.4……」
我：「是、」
水科：「SROA 建立 SSA 形式，引 5.4 加定理 2.2……」
水科：「JT 与 CVP、SimplifyCFG 与 InstCombine……」
我：「几遍？」
水科：「Reassociate 先把式子规范化，GVN 才认得出同形，引 7.6」
水科：「循环 LPM1……」
水科：「(C1) 到 (C4)，加定理 4.4 的 do-while 尾测……」
水科：「再把不变量移出循环，引 2.6 加引 2.4」
水科：「是否允许由支配树回答，是否安全由 AA 回答」
水科：「循环 LPM2……」
我：「啊、」
水科：「引 4.2 加定理 4.4……」
水科：「匹配模式的循环换成 libc intrinsic，引 5.5 的区间恒等式」
水科：「归纳变量规范化成指针递进，引 4.3」
水科：「函数下半场」
我：「下半场」
水科：「GVN 与 SCCP 消除重复，同余加推论 1.6……」
水科：「BDCE、ADCE、DSE 按位、按可观测行为、按堆版本」
水科：「三个判据重新计算存活集，引 1.7 的三次加细」
蝉还在叫
水科：「模块优化」
我：「多久一次？」
水科：「整形的那几个 pass 按定理 4.5 与引 4.6……」
水科：「收尾先做 GlobalDCE 与 ConstantMerge」
水科：「devirt 消费的正是前奏中 CalledValuePropagation 得到的候选集」
水科：「默认的非 LTO -O2 里，它要开关才排入……」
我：「那、那个」
水科：「New Pass Manager……」
水科：「run(unit, AM) 到 PreservedAnalyses 的契约」
我：「嗯、嗯、」
水科：「缓存加逐 pass 作废的主循环」
水科：「PassRegistry.def 加解析器，把流水线当数据……」
水科：「其中最容易出错的是 preserve 声明……」
水科：「引理 N.3 的方向不对称……」
我：「然后呢？」
水科：「然后是三条贯穿全文的共性」
水科：「其一，证明的复用率极高」
水科：「按编号 grep 一遍就能看出哪几条被引用最多」
我：「蝉还在叫啊」
水科：「引 0.5，UB 可剪……」
水科：「定义 6.3，盈亏……」
水科：「引 5.3，最近覆盖 def……」
水科：「引 2.4，代码移动四条件」
水科：「引 1.4，join 聚合」
水科：「引 4.2，闭式与终值……」
水科：「定义 0.1a，事件字母表……」
我：「是、是、」
水科：「推论 1.6，SCCP 型保证……」
我：「哪一条？」
水科：「引 5.4，私有存储提升」
水科：「其中引 5.4 一条」
水科：「被 SROA、mem2reg、GlobalOpt」
水科：「LICM 的 promote 与 DSE 共用……」
我：「啊哈哈，队好长」
水科：「定理 7.4 字面上的引用不算多……」
水科：「真正独立的算法有限」
水科：「其二，每个 pass 的存在理由高度同构……」
水科：「它消除一个别的 pass 的表示盲区，引 7.5 那张表……」
我：「所以？」
水科：「SSA 数据流看不见聚合，SROA 补」
水科：「看不见内存搬运，MemCpyOpt 补」
水科：「看不见位级死，BDCE 补……」
水科：「看不见循环内互相引用的死代码，ADCE 补……」
水科：「看不见分支两边的重复访存，MergedLoadStoreMotion 补……」
水科：「SCEV 要 rotate 过的形」
水科：「GVN 要 reassociate 过的式……」
水科：「向量化要 unroll 过的块……」
我：「什么顺序呢？」
水科：「DSE 要 ADCE 先删掉那些保守的 call……」
水科：「引 1.4 的 join 项变少」
水科：「盲区与对应的 pass，前提与对应的次序……」
水科：「其三，各章不是并列的……」
背面已经写满了。
水科：「rotate 到 LICM，LoopRotationUtils.cpp:52 旁注释……」
水科：「unswitch 到 full unroll，:723……」
水科：「full unroll 到 SROA，:765……」
水科：「ADCE 到 DSE」
水科：「而是同一个事实的不同侧面，定理 7.4……」
水科：「上游的产物是下游的前提……」
水科：「整条链」
1 | ① 前端 IR：alloca 遍布函数体、attrs 缺失 |
我：「怎么读这张链？」
水科：「从任一环向两端各问一句……」
水科：「-O2 的全部次序就是这一套衔接……」
水科：「后面至少一个 pass 的合法性前提失去依据……」
水科：「去掉一环，就是在定理 7.4 的拓扑序里删一个节点」
水科：「其后继的前提失效，O_j 严格变小……」
三日月站在门口。
她手上拿着那罐没喝完的咖啡。
三日月：「划掉的那一行……」
三日月：「也算写过了」
她说完就走了。
“9 月 13 日”
我把收据折起来，塞进贩卖机的找零口。
不是扔掉。
是塞进去，让它待在那里。
找零口很深，只能看见一小截白边。
热敏纸上的字会淡。
铅笔的字不会。
清单空了，才算做完。
可是清单还在被写上新的条目。
我偶尔还会思考这种事情。
比如，一份清单要写到多少行，才算写完。
比如，热敏纸上的字淡掉的时候，是谁把它擦掉的。
……啊哈哈，想太多了。
对我来说，那就只有这种程度。
天亮了。
坡道上面第一班电车开过去，声音很远。
水科：「回去睡」
我：「你今天还要编译吗……」
水科：「要」
我：「编译多久？」
水科：「看循环嵌套多深……」
我：「那不是看文件多大吗……」
水科：「不是」
水科：「引 1.3」
我：「我居然记住了」
水科：「记住了就好」
水科：「明年此 commit 一变，行号全废」
我：「那你还背」
水科：「背」
幸福的每一天……
每一天都很幸福……
我便是生活在这样一个世界上……
我偶尔会思考这种事情。
……
Wonderful Everyday