文档教程人工智能【免费下载链接】AISystemAISystem 主要是指AI系统包括AI芯片、AI编译器、AI推理和训练框架等AI全栈底层技术项目地址https://gitcode.com/GitHub_Trending/ai/AISystem点击查看免费下载公共子表达式消除Common Subexpression EliminationCSE是编译器中经典的冗余表达式消除优化技术也是 AI 编译器前端图优化的核心 Pass 之一。本文以 AISystem 项目中 03Compiler/03Frontend/08CSE.md 为主体系统讲解 CSE 在传统编译器中的两类算法局部值编号 LVN 与缓式代码移动 LCM并延伸至 AI 编译器基于计算图 IR 的子图级 CSE 实现以 Golang、TensorFlow 为例帮助读者掌握 CSE 从原理、数学定义到工程落地的完整知识链路。图示AI 编译器中对相同结构子图进行 CSE 的典型流程%x分别经过相同的Op1 → Op2结构后输出Op3与Op4CSE 将冗余子图合并只计算一次后分发结果。一、CSE 的基本原理公共子表达式消除也称冗余表达式消除是普遍应用于各种编译器的经典优化技术。其核心目标是消除程序中重复计算的公共表达式从而减少计算量、提高执行效率。在程序中经常出现多个位置使用相同的表达式进行求值且这些求值结果完全一致。重复计算会引入不必要的开销CSE 的思路是识别出这些重复计算只计算一次将结果保存起来供后续使用。以一个最经典的公共子表达式为例temp b * c a b * c g d b * c e在计算a和d时都使用了b * c这个表达式而程序在计算a、d之前已经计算过b * c并将结果保存在temp中。关键前提是从b * c计算并赋值给temp之后到计算a和d之间b或c的值没有发生改变。满足该前提后即可将a、d中的b * c替换为temptemp b * c a temp g d temp e此时b * c只计算一次后续直接载入temp的值避免了重复计算提升了执行效率。从字幕讲解见 03Compiler/03Frontend/srt/08.srt可提炼出 CSE 的三个基本原则定义可达性Reachability表达式在某点 p 为“可达”当且仅当从入口节点到 p 的每条路径都计算过该表达式且在计算之后、到达 p 之前其任一子表达式如b或c都未被重新赋值。若b或c被重新赋值temp的值就会改变替换便不再成立。成本收益权衡编译器会权衡重复计算的代价与存储表达式的代价。例如当结果是一个非常大的数据如大矩阵、大浮点数时存储开销可能超过重复计算此时应考虑以计算换空间——即重复计算而非存储。这一判断需要结合寄存器压力等其他因素综合决定。作用域分类编译器开发者将 CSE 分为两类——若优化仅限于程序的基本块内称为局部公共子表达式消除若优化范围涵盖多个基本块则称为全局公共子表达式消除。二、传统编译器的 CSE 算法传统编译器中有两种经典的公共子表达式消除方法局部值编号LVN与缓式代码移动LCM。2.1 局部值编号LVN局部值编号Local Value Numbering, LVN是一种局部公共子表达式优化算法用于识别并消除基本块内冗余的表达式。LVN 为每个基本块维护一个散列表存储该基本块中的变量、常量以及表达式的散列值。假设表达式形如x op y散列值记为VN()LVN 的计算过程如下按顺序遍历基本块中的所有表达式。分析表达式x op y的两个子表达式 x 和 y查询散列表若能查询到则返回其对应的散列值若查询不到则创建新的表项与散列值插入散列表后返回。获得VN(x)和VN(y)后计算VN({VN(x) op VN(y)})若散列表中已存在该表达式对应的散列值说明该表达式在前面已经定义过可以直接替换为此前该表达式的计算值若未找到则生成新表项与散列值并插入散列表。可以看到LVN 的本质是利用哈希表记录每个表达式唯一的值编号相同的表达式结构会得到相同的散列值从而在遍历过程中识别出重复计算并复用其结果。这种基于散列的实现简单高效适用于基本块内这种线性执行、无控制流分支的场景。2.2 缓式代码移动LCM缓式代码移动Lazy Code Motion, LCM使用数据流分析技术通过可用表达式Available Expressions、可预测表达式Anticipatable Expressions以及延迟分析Lazy / Delay Analysis这三类数据流问题的方程实现全局的公共子表达式消除。在 LCM 中对于某个待优化的表达式 e通常生成一个新的赋值语句将 e 赋给临时变量形如h x op y其中 h 为临时变量x op y即待优化的表达式 e。LCM 的算法实现主要分两步最早放置Earliest Placement将公共子表达式尽可能向上提找到该表达式第一次被求值的位置。延迟放置Delay Placement公共子表达式在找到第一次求值位置后如果直接插入可能引起新的冗余此时需要将插入位置尽可能下沉并保证下沉前后插入产生的结果相同。可用表达式Available Expressions对于某个使用表达式e: x op y的操作 d若在 d 上 e 是可用表达式当且仅当从程序入口到达操作 d 的所有路径都计算过 e且从求值处到操作 d 之间e 的任何一个子表达式的值都没有发生改变。当一个表达式对某个基本块是可用表达式其含义是从入口基本块b0到基本块bn的入口处的所有路径都计算过 e且从求值处到bn的入口处表达式 e 没有被杀死即其任何一个子表达式都没有被重新计算过。在控制流图中编译器为每个基本块维护可用表达式集合AvailIn(n)定义公式如下AvailIn(n) ∩_{m∈preds(n)} ( DEExpr(m) ∪ ( AvailIn(m) ∩ ¬ExprKill(m) ) )初始条件为b0是程序入口节点AvailIn(n0) ∅对于所有ni ≠ n0AvailIn(ni) {all expression}全集。其中preds(n)基本块bn的前继节点集合DEExpr(m)基本块bm中**向下展示Downward Exposed**的表达式即若表达式e ∈ DEExpr(m)则从 e 的计算处到bm基本块出口e 都未被重新赋值¬ExprKill(m)基本块bm中未被杀死的表达式集合。若e ∈ ExprKill(m)则表明 e 的一个或多个子表达式在bm中被重新计算了。根据公式可知e ∈ AvailIn(n)当且仅当 e 是bn前继节点中向下展示的表达式或 e 在bn前继节点的入口和出口处都是可用表达式。可预测表达式Anticipatable Expressions可预测表达式通常是针对基本块定义的。编译器为每个基本块维护可预测表达式集合AntOut(n)若e ∈ AntOut(n)表示在bn出口处 e 的值可用于预测从bn到出口节点的所有路径上所有表达式 e 的使用即路径上所有使用的表达式 e 都是冗余的。其计算公式如下AntOut(n) ∩_{m∈succ(n)} ( UEExpr(m) ∪ ( AntOut(m) ∩ ¬ExprKill(m) ) )初始条件为bf是程序出口节点AntOut(nf) ∅对于所有ni ≠ nfAntOut(ni) {all expression}全集。其中succ(n)基本块bn的后继节点集合UEExpr(m)基本块bm中**向上展示Upward Exposed**的表达式即在bm中被杀死前所使用的表达式。若e ∈ UEExpr(m)则即使在bm中会修改 e 的一个或多个子表达式这些修改操作也位于使用 e 之后¬ExprKill(m)同上表示bm中未被杀死的表达式集合。根据公式e ∈ AntOut(n)当且仅当 e 是bn后继节点中向上展示的表达式或 e 在bn后继节点的入口和出口处都是可预测表达式。最早放置Earliest Placement最早放置需要用到基本块出入口的可用表达式与可预测表达式因此先给出两者的补全定义。已知基本块bn的入口可用表达式为AvailIn(n)则其出口可用表达式为AvailOut(n) DEExpr(n) ∪ ( AvailIn(n) ∩ ¬ExprKill(n) )即包含bn中向下展示的表达式集合以及在入口处可用且未被bn杀死的表达式集合。已知基本块bn的出口可预测表达式为AntOut(n)则其入口可预测表达式为AntIn(n) UEExpr(n) ∪ ( AntOut(n) ∩ ¬ExprKill(n) )即包含bn中向上展示的表达式集合以及在出口处可预测且未被bn杀死的表达式集合。为了简化最早放置的分析假设每条边含有一个存储集合Earliest(i, j)i、j 分别为源节点与目的节点的编号用于存储待优化的表达式。若e ∈ Earliest(i, j)则该表达式无法通过基本块bi前往更早的边即bi是 e 的最早赋值边界。其定义如下Earliest(i, j) AntIn(j) ∩ ¬AvailOut(i) ∩ ( ExprKill(i) ∪ ¬AntOut(i) )其中e ∈ AntIn(j)根据入口可预测表达式定义从bj的入口到出口基本块e 的任何一个子表达式都没有被重新定值因此可以安全地将 e 移动到Earliest(i, j)。这里的安全指将 e 上移后不会使其他不包含该表达式的路径引入该表达式即不会产生新的冗余表达式。e ∈ ¬AvailOut(i)根据出口可用表达式定义从入口基本块到bi的路径上e 的一个或多个子表达式被重新定值了。为了满足e 不能通过bi前往更早的边e 的子表达式重新定值必须发生在bi中故e ∈ ExprKill(i)。若e ∈ ¬AntOut(i)说明存在一个或多个bi的后继节点e 在这些基本块的入口处不可预测即 e 的一个或多个子表达式在这些路径中被重新定值此时 e 甚至无法被移动到bi中更不可能移动到更早的边上。这两个条件除非同时不满足否则表达式不能移动到更早的边。延迟放置Delay Placement完成最早放置后编译器进行延迟分析。延迟分析是控制流图上的一个前向数据流问题目的是判断边上的某个待优化表达式能否通过其目的节点进入下一条边。编译器为每个基本块维护集合LaterIn(n)若e ∈ LaterIn(n)则表达式 e 在bn的入口处是可延迟的。为每条边维护集合Later(i, j)若e ∈ Later(i, j)则表示 e 可以进入到bj中直观上Later(i, j)就是可能下沉表达式集合。其定义如下LaterIn(j) ∩_{i∈preds(j)} Later(i, j), j ≠ n0 Later(i, j) Earliest(i, j) ∪ ( LaterIn(i) ∩ ¬UEExpr(i) ), i ∈ preds(j)从公式上看可能下沉表达式集合分为两部分e ∈ Earliest(i, j)e 一定是可能下沉的表达式最早放置的表达式自然可以下沉另一部分来自从bi下沉下来的表达式这些表达式满足在bi的入口处可下沉且在bi中不是向上展示的表达式。因为若e ∈ UEExpr(i)表明 e 在bi中被求值若再下沉下沉的这份表达式反而会成为冗余表达式。重写代码Rewrite最后一步利用LaterIn(n)和Later(i, j)生成额外的集合来指导编译器重写代码额外集合包括Insert(i, j)与Delete(i)。Insert(i, j)表示可插入集合定义如下Insert(i, j) Later(i, j) − ( LaterIn(j) ∩ ¬UEExpr(j) )Later(i, j)为可能下沉的集合LaterIn(j) ∩ ¬UEExpr(j)表示可以从bj下沉到底部的集合。从可能下沉集合中去掉所有能下沉的表达式留下的就是不能下沉、需要插入的表达式。插入规则为若bi只有一个后继节点bj则将Insert(i, j)中的表达式插入到bi的出口处若bj只有一个前趋节点bi则将Insert(i, j)中的表达式插入到bj的入口处若前两个条件都不满足则在边bi → bj上新建一个基本块将Insert(i, j)中的表达式插入到该基本块中。需要注意的是由于插入的是新的赋值语句插入后会产生新的冗余表达式例如某个基本块中向上展示的表达式。因此编译器对每个基本块维护一个删除集合Delete(i)定义如下Delete(j) UEExpr(j) ∩ ∪_{i∈preds(j)} Insert(i, j)被删除的正是那些其求值结果可由插入的表达式直接替代的向上展示表达式。三、AI 编译器的公共子表达式消除公共子表达式消除是传统编译器常用的前端优化手段经过迁移也可以应用到深度学习编译器中。区别在于传统编译器的子表达式基于 IR 中的标量表达式如b * c而 AI 编译器中子表达式基于计算图或图层 IR通过搜索计算图中相同结构的子图简化计算图的结构从而减少计算开销。在计算图中若多个节点经过了相同的图结构如{ {Op1, Op2}, Op1→Op2 }AI 编译器会将相同子图的所有不同输出都连接到同一个子图上然后在后续的**死代码消除DCE**阶段删除其他相同的子图从而达到简化计算图、减少计算开销的目的。这一过程在 AISystem 的 03Compiler/03Frontend/09DCE.md 中有对应讲解AI 编译器通过分析计算图找到无用的计算节点或不可达的计算节点并消除。CSE 负责合并相同的子图DCE 负责清理合并后失去引用的冗余节点二者配合完成图级冗余消除。从 AISystem 的 01Introduction.md 可知在 AI 编译器前端优化流程中编译器对输入的 GraphIR 依次执行常量折叠、常量传播、算子融合、表达式简化、表达式替换、公共子表达式消除等前端优化 Pass每个 Pass 的输出仍为 GraphIR 并作为下一个 Pass 的输入。同样在 02AICompiler/03Architecture.md 的通用 AI 编译器架构中计算图优化策略明确包含 CSE公共子表达式消除与 DCE死代码消除等图级优化这些优化与硬件无关可应用于各种后端目标。在 AI 编译器后端实践中CSE 同样是重要的设备无关优化。例如 04Backend/03Optimization.md 中提到TritonIR 上的与硬件无关的优化包含 CSE Pass即 MLIR 的 cse Pass用于消除公共子表达式与 Inliner、Combine、Canonicalizer、LICM 等 Pass 共同构成后端 IR 的优化管线。四、公共子表达式实现案例4.1 传统编译器实现案例以 Golang 为例Golang 编译器是在SSA IR上执行公共子表达式消除的。正式介绍算法前先铺垫两个基础概念。支配性Dominance支配性的含义对于入口基本块b0以及任意基本块bi和bji ≠ j如果从b0到bi的所有路径都经过bj则称bj是bi的支配节点。支配性是一个正向数据流问题编译器为每个基本块维护支配节点集合Dom(n)计算公式如下Dom(n) {n} ∪ ( ∩_{m∈preds(n)} Dom(m) )初始条件为Dom(n0) n0Dom(ni) NN 是控制流图中所有节点的集合i ≠ 0preds(n)表示bn的前继节点集合。支配性在 CSE 中的关键作用是只有当一个 Value 所在的块支配另一个 Value 所在的块时才能用前者安全地替换后者见下文第三步。静态单一赋值SSASSAStatic Single Assignment是一种中间表示IR形式用于在编译器优化和静态分析中表示程序的数据流。SSA 形式中每个变量在程序中只能被赋值一次从而简化数据流分析与优化过程。其特点包括单一赋值每个变量只能被赋值一次每次赋值都会引入一个新的变量版本φ 函数Phi 函数当一个变量具有多个可能的来源时使用 φ 函数选择正确的值。φ 函数接受来自不同基本块的变量版本并在控制流中根据前驱基本块的条件选择正确的版本显式使用每个变量的使用都明确指定其来源即变量的定义使数据流分析与依赖关系跟踪更加直观准确。Golang 的 CSE 算法步骤不同编译器在 CSE 实现细节上不尽相同Golang 在 SSA IR 上的算法分为三步第一步粗粒度划分等价集。遍历所有 Block将 Value 存储在数组 a 中然后按粗粒度标准排序例如操作类型、操作的数据类型、操作数类型等对于粗粒度标准相同的值再按照值的 ID值标号排序。排序完成后对数组 a 切分将粗粒度标准相同的值切分到同一数组存入粗粒度划分等价集中。第二步细粒度划分等价集。在继续处理前需给粗粒度等价集中每个集合的值分配一个等价 ID若集合元素个数大于 1该集合为等价集为集合中每个值分配相同的正数等价 ID若个数等于 1说明是非等价集为该值分配一个负数等价 ID其大小为该值的 ID。然后遍历所有粗粒度等价集按细粒度标准划分。以加法为例v1 Const64 int [1] v2 Const64 int [2] v3 Const64 int [3] v4 Add64 int v1 v2 v5 Add64 int v2 v3 v6 Add64 int v2 v1在粗粒度等价集中存在一个等价集{v4, v5, v6}。将该等价集按细粒度标准操作数的等价 ID排序。由于加法满足交换律排序前需将两个操作数按等价 ID 从小到大排序可得{v6, v4, v5}不难发现v4和v5的两个操作数一模一样分别是{v1, v2}与{v2, v1}经交换律排序后均为{v1, v2}而v6的操作数不同。因此对该等价集切分获得非等价集{v6}和等价集{v4, v5}此时粗粒度等价集变为{{v4, v5}, {v1}, {v2}, {v3}, {v6}}划分完成后对粗粒度等价集重新分配等价 ID然后重复上述步骤直到前后两次粗粒度等价集不再发生变化此时得到细粒度等价集。第三步替换重复表达式。细粒度等价集中的每个等价集都是一组重复的表达式但不能随意消除需要判断Value 所在的块是否支配需要替换的 Value 所在的块若支配则可以安全地替换消除。4.2 AI 编译器实现案例以 TensorFlow 为例TensorFlow 在计算图上实现公共子表达式消除的方式如下第一步获得逆后续节点集Reverse Post-order。TensorFlow 使用反向深度优先搜索Reverse DFS遍历计算图获得逆后续节点集。这样处理的目的是确保在处理某个节点时其所有的输入节点已经处理完毕——逆后续遍历天然满足拓扑序要求。第二步为操作节点计算混合哈希值。遍历逆后续节点集。由于公共子表达式优化只与操作节点有关遍历时忽略非操作节点。TensorFlow 使用混合哈希的计算模式为每个操作节点计算对应的哈希值参与混合哈希计算的节点属性包括输出节点的个数、每个输出节点的类型、输入节点的信息等。这样处理的目的是确保一个表达式对应一个哈希值达到检索公共表达式的目的——输入输出信息相同的节点会得到相同的哈希值。第三步维护公共子表达式候选集并替换。将节点与哈希值一一对应存入候选集。当处理一个新的操作节点时判断其哈希值是否已存在于候选集中若不存在则将该操作节点及其哈希值添加到公共子表达式候选集若存在则用候选集中的既有节点连接到该操作节点的所有输出节点对该操作节点本身不做任何处理——它会在后续的死代码删除DCE中被删除掉。该算法的实现要点可以概括为以哈希表为候选集、以输入输出信息构造哈希键、以逆后续遍历保证拓扑顺序这也是绝大多数 AI 编译器在图层 IR 上实现 CSE 的通用模式参考字幕讲解 03Compiler/03Frontend/srt/08.srt 中的伪代码流程获取逆后续节点 → 建立候选 map → 遍历图 → 计算节点哈希值作为 key → 命中候选集则复用、未命中则登记 → 删除重复节点并重建数据流边。五、本节小结公共子表达式消除就是去掉程序中相同的结构、减少重复计算传统编译器通过找到重复表达式存储表达式的计算结果并用该计算结果替换重复表达式的引用。局部场景用 LVN基于散列表的值编号全局场景用 LCM基于可用表达式、可预测表达式与延迟分析三类数据流方程的最早/延迟放置。AI 编译器通过找到相同的子图将相同子图的所有输出连接到同一个子图再由死代码消除清理冗余子图从而实现公共子表达式消除减少计算开销。通过 CSE可以减少重复计算和冗余代码提高程序性能。但需要注意CSE 可能增加代码的复杂性和内存消耗例如引入临时变量、占用寄存器与存储空间因此在实际应用中需要结合成本收益权衡计算开销 vs 存储开销综合考虑。延伸阅读前端优化整体框架与 Pass 流程03Compiler/03Frontend/01Introduction.md前端优化课程目录与配套资源PPT/视频/字幕03Compiler/03Frontend/README.md与 CSE 配合的死代码消除DCE03Compiler/03Frontend/09DCE.md通用 AI 编译器架构中的图级优化含 CSE、DCE、算子融合等03Compiler/02AICompiler/03Architecture.md后端 IR 优化管线中的 MLIR CSE Pass03Compiler/04Backend/03Optimization.md本节配套视频字幕含算法伪代码讲解03Compiler/03Frontend/srt/08.srt赞分享文档教程人工智能【免费下载链接】AISystemAISystem 主要是指AI系统包括AI芯片、AI编译器、AI推理和训练框架等AI全栈底层技术项目地址https://gitcode.com/GitHub_Trending/ai/AISystem点击查看免费下载相关推荐AISystem 教程AI 编译器前端优化全解析——从图算 IR 到图层优化 PassAISystem 教程AI 编译器前端优化全解析——从图算 IR 到图层优化 Pass AI 编译器前端优化的核心任务是在 AI 框架解析前端代码生成计算图文档教程人工智能AI 编译器前端优化全景从 GraphIR 到图层优化 Pass 体系AISystem 前端优化系列导读AI 编译器前端优化全景从 GraphIR 到图层优化 Pass 体系AISystem 前端优化系列导读 AI 编译器前端优化是连接 AI 框架与底层硬件文档教程人工智能终极指南深度解析UniHacker Unity许可证管理工具的技术实现与实战应用终极指南深度解析UniHacker Unity许可证管理工具的技术实现与实战应用 UniHacker是一款专为Unity开发者设计的跨平台许可证管理工具支持逆向工程桌面应用开发工具上一篇Overleaf-Workshop核心功能大揭秘从编译到实时协作的全流程解析下一篇从传统浮点数到Money库金融系统重构的完整迁移指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考