【免费下载链接】publicationsPublications from Trail of Bits项目地址https://gitcode.com/GitHub_Trending/pu/publications点击查看免费下载本篇技术指南围绕 Trail of Bits 在 EuroLLVM 2024 上的演讲《Repurposing LLVM analyses in MLIR: Also there and back again across the Tower of IRs》展开核心讲解如何在不重写 LLVM 既有分析工具的前提下把它们无缝复用到 MLIR 生态通过一条贯穿 Clang AST、VAST 各层 MLIR 与 LLVM IR 的 IR 之塔Tower of IRs借助逐层快照与 provenance溯源链接建立双向映射最终把 LLVM 分析结论直接关联回任意 MLIR dialect。读者读完可掌握 快照 位置映射 的核心机制、vast-front/opt的完整降级流水线实操以及依赖分析结果如何跨层回溯到高层 MLIR 与源代码。一、问题背景LLVM 分析的遗产与 MLIR 的断层LLVM IR 沉淀了二十余年丰富而成熟的分析工具链依赖分析dependence analysis、别名分析、循环优化、数据流分析等等。但伴随 MLIR 的兴起新一代编译器与程序分析工具纷纷转向 MLIR 作为统一基础设施。一个现实问题随之而来这些宝贵的、经过实战检验的 LLVM 分析如何在 MLIR 中被继续使用理想的答案是完全不必改动这些分析本身——原样复用让 MLIR 直接受益。更进一步我们还希望将 LLVM IR 上得到的分析结论例如这条 store 指令依赖哪条 store直接关联回高层的 MLIR dialect甚至关联回源代码行。这正是本演讲要解决的问题而解决方案就是演讲标题中的 Tower of IRs。二、主角 VAST以程序分析为目标的 MLIR 编译器要理解 Tower of IRs首先要认识它的载体——VASTVerified/Analysis-oriented Static Toolkit一个基于 MLIR 的、面向程序分析的 C/C 编译器。VAST 的定位可从两点概括见 VAST 演讲 README传统编译器只输出一层 IR而程序分析恰恰需要同时看到代码的多种进展形态——从非常高层的抽象到非常低层的机器相关表示LLVM IR 对程序分析而言很少是最佳表示因为它丢失了大量高层语义类型信息、控制流结构、对象边界等。VAST 的设计目标见本次演讲幻灯片在从 Clang AST 到 LLVM IR 的路径上逐级表示代码的演化尽可能保留信息不做激进的丢弃型降级允许构建新的程序抽象而不被某一种 IR 锁定。从管线结构看VAST 一端是 Clang 生成的 AST另一端是 LLVM IR中间则是多层 MLIR 表示High Level MLIR、Mid Level MLIR、Low Level MLIR以及最接近 LLVM 的 LLVM MLIR即llvmdialect 模块。VAST 的目标是把这条完整的降级路径全部用 MLIR 表达出来——这也为分析结论跨层映射提供了物理基础。三、Tower of IRs核心思想Tower of IRs 是本演讲提出的核心概念幻灯片给出了三个视角1. 自顶向下视图Top-down view以源代码Clang AST为塔顶逐层向下是 VAST High Level MLIR → VAST Mid Level MLIR → VAST Low Level MLIR → LLVM MLIR → LLVM IR。塔的每一层都是 MLIR 的一个快照snapshot层与层之间用 provenance 链接Provenance Links相连。2. 自底向上视图Bottom-up view与顶向下视图等价强调塔内任意相邻两层之间存在双向映射Bidirectional mapping between MLIR modules。这意味着你既可以从高层推导低层也可以从低层追溯回高层。3. 真实的多级 IRMulti-Level IR把上述视图合起来Tower of IRs 本质上就是一条完整的、带层间映射的多级 IR 链。任何一层上的分析结果都可以沿着 provenance 链向上或向下旅行。用一句话概括MLIR Snapshots Provenance Links Multi-Level IR。快照保证每一层都是稳定、可复现的 IR 状态provenance 链接保证层与层之间的元素函数、变量、指令可以相互指认。四、逐层快照与位置映射generateLocationsFromIR层间映射是如何实现的演讲揭示了一个关键机制MLIR 的mlir::generateLocationsFromIR工具函数。这个函数的工作方式如下给定一份 IR比如某一层的 MLIR 模块把它快照snapshot到指定输出流形成该层稳定文本形态利用该快照文件内打印出来的位置信息locations为元素生成新的 location。于是源 MLIR 经过一次 Transform降级/优化 pass产生新的 MLIR 后两个模块之间可以通过快照文件中的位置建立起对应关系低层 IR 中每个操作都带有一个指向其前世上一层快照中对应位置的 location。这本质上是把 MLIR 内建的Loc位置机制当作跨层索引来用。这套机制意味着只要各层都保留 location层间映射就是自动的不必为每一对相邻层手写专门的翻译表分析结果只要落在某个操作/值上就能顺着 location 链回溯。五、实战让fun()走一遍 Tower of IRs演讲用一个极简的 C 函数演示了整条流水线。源代码如下void fun() { int a 2; int b a 3; int c b * 13; }示例中常量 2、3、13 取自 OEIS A100424即对正整数做三次筛法变换得到5.1 第一步从前端生成高层 MLIR使用vast-frontVAST 的前端驱动工具生成高层hlMLIRvast-front -vast-emit-mlirhl输出中可以看到变量c的高层表示——类型还是!hl.value!hl.int这样的 VAST 高层类型运算仍是hl.mul这类高级算术操作且携带loc(source:4)指向源代码第 4 行%2 hl.var c : !hl.value!hl.int { %4 hl.ref %1 : !hl.lvalue!hl.int %5 hl.implicit_cast %4 LValueToRValue : !hl.int %6 hl.const #hl.integer13 : !hl.int %7 hl.mul %5, %6 : !hl.int hl.value.yield %7 : !hl.int } loc(source:4)注意hl.implicit_cast ... LValueToRValue——这是 C 语义中左值读取的显式表达正是 LLVM IR 里会丢失的信息。5.2 第二步降级类型hl → 带具体整型用optLLVM 的优化器驱动VAST pass 注册在其中执行类型降级opt -vast-hl-lower-types!hl.int变成具体的si32有符号 32 位整数其余结构不变location 更新为loc(high-level:15)%2 hl.var c : !hl.valuesi32 { %4 hl.ref %1 : !hl.lvaluesi32 %5 hl.implicit_cast %4 LValueToRValue : si32 %6 hl.const #hl.integer13 : si32 %7 hl.mul %5, %6 : si32 hl.value.yield %7 : si32 } loc(high-level:15)这个例子也回答了是否需要每层都做快照演讲明确说对于不改变 MLIR 中关键结构的变换可以跳过快照或者对未变化的模块使用恒等映射identity maps。快照策略是可以按需裁剪的不必机械地对每个 pass 都拍一张。5.3 第三步ABI 与函数降级接下来是一组 ABI 相关的 passopt -vast-emit-abi opt -vast-lower-abi opt -vast-hl-to-ll-func这一步处理函数签名、调用约定与 ABI 层语义为进入 low level 表示做准备。5.4 第四步变量与控制流降级opt -vast-hl-to-ll-varshl.var开始变为lldialect 的显式变量操作ll.uninitialized_var、ll.initialize等运算类型变成(si32, si32) - si32%9 ll.uninitialized_var : !hl.lvaluesi32 %10 hl.ref %8 : !hl.lvaluesi32 %11 hl.implicit_cast %10 LValueToRValue : si32 %12 hl.const #hl.integer13 : si32 %13 hl.mul %11, %12 : (si32, si32) - si32 %14 ll.initialize %9, %13 loc(hl-to-ll-func:21)随后是控制流与区域region降级opt -vast-hl-to-ll-cf opt -vast-hl-to-lazy-regions opt -vast-hl-to-ll-gepshl-to-lazy-regions处理 C 的作用域/复合语句在 MLIR region 中的惰性表示hl-to-ll-geps则生成与指针运算GEP对应的地址计算。5.5 第五步值类别降级引入内存操作opt -vast-hl-lower-value-categories这里把 C 的值类别左值/右值语义落实为真正的内存操作——出现ll.alloca、ll.load、ll.store%6 ll.alloca : !ll.ptrsi32 %7 ll.load %2 : si32 %8 hl.const #hl.integer13 : si32 %9 hl.mul %7, %8 : (si32, si32) - si32 ll.store %6, %9 loc(hl-to-ll-geps:15)注意 location 此时已经指向hl-to-ll-geps:15而不是源代码行——location 记录的是在塔中哪一层、哪个位置生成这正是跨层索引的凭证。5.6 第六步落到 LLVM dialect-vast-to-llvm转换到标准llvmdialect%8 llvm.mlir.constant(1 : index) %9 llvm.alloca %8 x i32 %10 llvm.load %4 %11 llvm.mlir.constant(13 : i32) %12 llvm.mul %10, %11 llvm.store %12, %9 loc(hl-lower-value-categories:15)5.7 第七步生成 LLVM IR最终得到标准 LLVM IR与 Clang 传统编译产物形态一致define void fun() { %1 alloca i32, i64 1, align 4 store i32 2, ptr %1, align 4 %2 alloca i32, i64 1, align 4 %3 load i32, ptr %1, align 4 %4 add i32 %3, 3 store i32 %4, ptr %2, align 4 %5 alloca i32, i64 1, align 4 %6 load i32, ptr %2, align 4 %7 mul i32 %6, 13 store i32 %7, ptr %5, align 4 ret void }至此塔顶的hl.var b一路变成了塔底的alloca/store序列。而整个过程中保留的 location 链让这些看似脱胎换骨的指令依然能指认回它们的源头。5.8 VAST 主要 pass 一览演讲还给出了 VAST 内置 pass 的全景清单按职责可分为几组ABI 相关emit-abi、lower-abi、fn-args-to-alloca高层语义降级hl-to-ll-vars、hl-to-ll-cf、hl-to-lazy-regions、hl-to-ll-geps、hl-to-ll-func、splice-trailing-scopes类型与内建处理hl-lower-elaborated-types、hl-lower-typedefs、hl-to-std-types、hl-to-hl-builtin清理与优化hl-dce死代码消除、hl-lower-value-categories最终出口to-llvm六、回程依赖分析结果如何Walk back the TowerTower of IRs 的杀手级应用是在 LLVM IR 层运行经典分析再把结论映射回高层。演讲以依赖分析dependence analysis为例。在 LLVM IR 层依赖分析会得出诸如store i32 %4, ptr %2与%3 load i32, ptr %1之间的依赖关系。这个结论本身只能落在 LLVM IR 的指令上对使用高层 dialect 的分析者意义有限。但借助塔结构可以沿 provenance 链逐层回溯Walk back the Tower of IRsLLVM IR 层store i32 %4, ptr %2LLVM dialect 层llvm.store %7, %4Low level VAST 层%8 ll.initialize %3, %7High level VAST 层%1 hl.var b : si32 { ... hl.value.yield %7 : si32 }回到最原始的高层类型表示%1 hl.var b : !hl.lvalue!hl.int最终对应到源代码int b a 3;于是一条 LLVM IR 的依赖边被翻译成了源代码层面的数据依赖b的初始化依赖a的读取。这正是幻灯片标题 Also there and back again出自托尔金《霍比特人》的梗的含义——分析可以从塔顶走下去到 LLVM也能带着结论走回塔顶。跨层收集依赖Gather dependencies across layers的意义在于高层分析如检测未初始化变量、类型混淆、对象生命周期问题不再需要自己在 LLVM IR 上重写一遍依赖算法而是直接复用 LLVM 现成的、经过验证的实现。七、方法的通用性与使用边界演讲在最后强调了这套方法的通用性快照 位置映射的思路不仅适用于 VAST其他 MLIR 工具链同样可以借鉴——只要你的降级流水线保留 location并定期对关键状态做快照就能建立跨层索引。同时演讲也给出了明确的注意事项警惕变换的激进程度aggressiveness过于激进的变换如大规模内联、常量折叠、内存重排、删除中间值会破坏元素之间的对应关系导致跨层链接失败hinder cross-layer linking因此在构建这种可回溯流水线时应保守地选择哪些 pass 允许改写结构对会破坏 provenance 的优化予以抑制或延后。这与 VAST 尽量保留信息的总体设计目标一脉相承——分析型编译器与优化型编译器的取舍完全不同。八、体验与延伸本场演讲的完整幻灯片见 slides.pdf录制视频为 EuroLLVM 20242024-04-10演讲者 Henrich Lauko演讲中提到 VAST 目前已在 Compiler Explorergodbolt上提供单层MLIR 的在线试玩Tower 的多层形态soon即将上线——可以推断多层在线体验属于后续规划背景知识可参见同仓库的 VAST: MLIR for program analysis of C/C 演讲LLVM Dev Meeting 2022以及 MLIR is the future of program analysis 等材料它们共同构成了 VAST 系列演讲的完整叙事。结语Tower of IRs 提供了一种务实而优雅的路径让 MLIR 生态不必推倒重来保留 LLVM 二十年积累的分析资产通过逐层快照 provenance 链接把新旧世界连接起来。分析者既可以在 LLVM IR 上运行成熟的依赖分析、别名分析又能把结论精确地映射回高层 MLIR dialect 乃至源代码——真正做到there and back again。而这一切的关键约束只有一个在降级过程中善待你的 location。赞分享【免费下载链接】publicationsPublications from Trail of Bits项目地址https://gitcode.com/GitHub_Trending/pu/publications点击查看免费下载相关推荐Reactotron 官方示例应用完全指南用 example-app 跑通 React Native / React JS 调试链路Reactotron 官方示例应用完全指南用 example app 跑通 React Native / React JS 调试链路 本文以 ReactotrTrail of Bits 演讲解读深入分析 Flame 恶意软件中的 MD5 碰撞攻击Trail of Bits 演讲解读深入分析 Flame 恶意软件中的 MD5 碰撞攻击 本篇技术指南基于本仓库 presentations/AnalyzinLLVM 常量时间编码支持Trail of Bits 用 __builtin_ct_select 在编译器层面阻断时序侧信道攻击LLVM 常量时间编码支持Trail of Bits 用 __builtin_ct_select 在编译器层面阻断时序侧信道攻击 本篇文章解读 Trail o上一篇CANN/pypto-gym QKV RMSNorm RoPE缓存API报告下一篇Ethermint EVM追踪器使用教程深入分析智能合约执行的终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考