Minotaur：从LLVM函数中提取一个片段

伪代码这段代码的作用:从一个 LLVM 函数中围绕目标指令 I提取一个“切片” C。这个切片只包含 I 计算所需的、且距离 I 不超过 B 步的指令同时把切片之外的所有输入变成 C 的参数。简单说就是从大函数里切出一块和 I 相关的“小函数”方便后续用程序合成去优化它。为什么要这么样直接把整个 LLVM 函数丢给 SMT 求解器太复杂容易超时。只切出关键的一小部分求解器就能高效处理。找到优化后再替换回原函数整体就能提速。代码详解第一阶段指令提取(1-40行)确定允许的基本块2–5 行如果I在某个循环里只允许该循环内的基本块若是嵌套循环则只取最内层循环。否则只允许不在任何循环里的基本块。目的避免把循环外的无关指令拉进来也避免把循环体外的代码割裂。初始化(6-9 行)Harvested最终要保留在切片里的指令。Unknown那些不在切片内、但被切片用到的值会成为C的参数。Visited防止重复处理。WorkList待处理的指令每个元素是 (指令, 当前深度)初始为 (I, 0)。主循环(12-39 行)从工作列表中取出一条指令WI和它的深度Depth如果已处理过跳过。如果深度 B则把WI放入Unknown说明超出范围不包含在切片里不再往下追。如果WI不被 Minotaur 支持比如某些特殊内建函数也放入Unknown并停止。如果WI所在的基本块不在允许的集合中放入Unknown。否则将WI加入Harvested它是切片的一部分。关键处理依赖如果WI是加载指令Load则通过 MemorySSA 找到可能影响它的最近存储MemoryDef并把那个存储的值MI加入工作列表深度1。这能提取内存依赖。否则遍历WI的所有操作数Op将它们加入工作列表深度1。另外如果WI所在基本块的终止指令是条件分支则把分支条件也加入工作列表深度1。这样能提取控制流依赖让切片更准确。循环结束后第 40 行会把原函数的所有终止指令如ret,br加入Harvested。这是为了保留切片里可能用到的控制流信息虽然最终C是无环的但分支条件已经被提取了。第二阶段构造无环 LLVM 函数42–49 行克隆原函数 F 到 C44 行。删除 C 中不在Harvested里的指令45 行。现在 C 只包含切片中的指令。删除 C 中所有的循环回边46 行。确保 C 是无环的loop-free。把Unknown中的值作为参数加到 C 中47 行。这些是切片外部提供的输入。为I创建返回指令48 行。C 返回的是 I 计算出的值。最后返回这个新函数 C。通俗例子intf(intx,inty,intz){intax/y;// sdivintba^-1;// xorintcb^-1;// xorintdc%z;// sremreturnd;}现在我们想优化c的计算取B1。起点指令c第二个 xor。深度 0c被加入Harvested。深度 1遍历c的操作数发现是b第一个 xor把b加入工作列表深度 1。b被加入 Harvested。深度 1b的操作数是a但a的深度会变成 2超出 B所以a被加入Unknown不再继续。循环结束Harvested包含c和b。Unknown包含a。第二阶段克隆 F删除除b和c外的所有指令。a作为参数添加。最终C是define i64 cut(i64 %a) { %b xor i64 %a, -1 %c xor i64 %b, -1 ret i64 %c }这个切片刚好可以被优化成直接返回%a因为两次取反抵消。小结这个算法是Minotaur 的“切刀”负责把大函数里的一小段相关指令提取出来形成一个独立的小函数。它考虑数据、内存和控制依赖并限制深度确保小函数不会太大。小函数是无环的方便后续 SMT 求解器处理。提取后Minotaur 就可以在小函数上尝试合成更快代码然后替换回原函数。C小例子代码voidprocess(int*data,intlen){for(inti0;ilen;i){intxdata[i];// 加载intyx*2;// 乘法intzy1;// 加法if(z10){// 条件分支data[i]z;// 存储}else{data[i]0;}}}这个函数有一个循环依赖len。循环体内有 加载、计算、条件分支、存储。我们假设 LLVM 已经将其转换为 SSA 形式的 IR。假设我们想优化z y 1这条加法指令即我们要提取一个以这条加法指令为根的切片算法执行过程深度 B 2确定允许的基本块集合-I加法在循环体内所以只允许该循环最内层内的基本块。循环外的代码如for的循环控制不会被纳入切片。初始化Harvested {}最终切片内的指令Unknown {}切片外部、但被切片用到的值WorkList { (I, 0) }主循环处理 I深度 0深度 ≤ 2指令支持基本块允许 → 加入Harvested。遍历操作数y和1。y是由y x * 2定义的1是常量。将(y, 1)加入工作列表。常量直接保留在切片中不需要加入 Unknown。检查基本块终止指令假设这个基本块的终止指令是条件分支br i1 %cond, label %then, label %else其中%cond来自icmp sgt i32 %z, 10。把(cond, 1)加入工作列表。处理 y深度 1深度 ≤ 2 → 加入Harvested。操作数x和2。x 由x load i32, ptr %data_i定义2是常量。把(x, 2)加入工作列表。分支条件已在上一步提取此处无需重复但若 y 所在基本块也有分支也会提取。处理 cond深度 1cond是icmp指令操作数为z和10。z就是我们的目标加法已经在 Harvested 中10 是常量。加入Harvested但无需再推进因为z已处理。处理 x深度 2x是load指令。通过 MemorySSA 找到可能影响这个加载的最近存储假设循环内没有对data[i]的写在本迭代之前MemorySSA 会指向循环前的某个 MemoryDef或者是函数参数。找到的存储值可能是data基址和i索引的计算结果但这里我们简单处理因为 load 的地址是data i * 4它的值在循环外由data指针和循环变量i决定。算法会把load本身加入Harvested但它的地址操作数data和i因为深度已到 2再下一层会变成 3 B所以会被加入Unknown。同时分支条件可能已经在更早深度提取无需重复。循环结束此时Harvested包含%z add i32 %y, 1 %y mul i32 %x, 2 %x load i32, ptr %addr %cond icmp sgt i32 %z, 10以及相关的条件分支指令在代码中虽未显式出现在 IR 中但第 40 行会把所有终止指令加入 Harvested确保控制流结构保留。Unknown包含%addr指向data[i]的地址、%data基址、%i循环索引等取决于 IR 细节。构造无环函数 C克隆原函数。删除除 Harvested 外的所有指令只保留上面那几条。删除所有循环回边保证 C 是无环的。将 Unknown 中的值作为参数添加到 C 中。例如define i32 cut(i32* %addr, i32 %i, i32* %data) { ... }但实际上%addr可能由%data和%i计算得到Minotaur 会把这些依赖也提取为参数。5. 创建返回指令返回%z的值即加法结果最终C类似define i32 cut(i32* %addr, i32 %data_i) { %x load i32, i32* %addr %y mul i32 %x, 2 %z add i32 %y, 1 ret i32 %z }条件分支%cond可能也保留在 C 中如果它被后续指令使用的话但此处最终返回的是 %z条件分支只用于控制流在 C 中可能被简化。为什么这样切有用切出来的小函数C只包含与加法%z计算直接相关的指令且深度 ≤ 2无循环、无复杂控制流。SMT 求解器可以快速分析这个小函数并可能找到更优的实现。例如它可能发现%z add i32 (mul i32 (load i32 %addr), 2), 1等价于%z add i32 (shl i32 (load i32 %addr), 1), 1或者更激进的如果%addr有特殊对齐可以用 SIMD 一次性处理多个元素。优化后的C会被放回原函数替换原来的计算从而提升整体性能。对比原始函数和切片原始函数 process切片 C包含循环、循环控制、多次迭代只包含一次迭代中的核心计算包含存储、条件分支的完整控制流保留与 z 计算相关的控制和内存庞大SMT 无法处理小巧可被 Z3 快速验证通过这种方式Minotaur 实现了“分而治之”的优化策略。