Idempotent Slices with Applications to Code-Size Reduction

本文正式化了幂等后向切片的概念，提出了一种基于 GSA 形式的有效提取算法，并通过在 LLVM 测试套件中的实验证明，该算法能够识别并合并非连续指令序列，从而实现高达 7.24% 的代码体积缩减。

要点

这篇论文提出了一种名为**“幂等切片”（Idempotent Slices）的新技术，旨在帮助计算机程序变得更小、更精简。为了让你轻松理解，我们可以把编写程序想象成“整理一个巨大的仓库”，而这篇论文就是提出了一套全新的“智能打包与去重”**策略。

以下是用通俗语言和比喻对这篇论文核心内容的解读：

1. 核心问题：仓库里的“重复劳动”

想象你经营着一个巨大的仓库（计算机程序），里面有成千上万个工人（指令）在搬运货物。

• 现状：有时候，不同的工人会在不同的时间、不同的地点，重复做完全一样的动作。比如，工人 A 在仓库东头把箱子从货架搬到地面，工人 B 在西头也做了一模一样的事。
• 传统做法：以前的优化方法（如 LLVM 的 IROutliner）就像是一个**“找相同段落”的编辑。它只能把紧挨在一起**的重复动作合并。如果两个重复的动作中间隔了一大堆其他工作，它就没法合并了。
• 新发现：作者发现，有些重复的动作虽然分散在仓库的不同角落，甚至中间隔着复杂的路线（控制流），但它们本质上是一模一样的“任务包”。只要把这些分散的“任务包”提取出来，合并成一个“标准作业流程”，仓库就能省下巨大的空间。

2. 什么是“幂等切片”？（Idempotent Slices）

这是论文的核心概念。

• 比喻：想象你在做一道菜（计算一个值）。
  • 普通切片：可能包含切菜、炒菜、甚至把菜端上桌。如果你重复做这个切片，可能会把菜端两次，或者把盘子打碎（副作用）。
  • 幂等切片：这是一个**“纯数学计算”的任务。比如“把两个数字相加”。无论你把这个任务做 1 次还是 100 次，只要输入的数字一样，结果永远一样，而且不会改变仓库里的任何东西**（不会修改内存、不会报错、不会改变程序状态）。
• 关键点：这种“幂等”特性非常重要。因为它意味着我们可以安全地把这个任务从原来的地方“剪”下来，打包成一个独立的“小盒子”（函数），然后在需要的地方随时调用它，而不用担心会搞乱程序。

3. 技术难点：为什么以前做不到？

以前的算法（Guimarães 等人的方法）就像是一个**“只看局部地图”**的向导。

• 问题：在复杂的仓库（程序）里，有些路径看起来很奇怪（比如没有“单入口单出口”的简单结构，或者变量定义得很乱）。以前的向导在这些复杂路口会迷路，导致它漏掉了很多可以合并的重复任务。
• 比喻：以前的方法只能识别那些“直来直去”的重复动作。一旦遇到像“迷宫”一样的程序结构，它就找不到重复的部分了。

4. 解决方案：GSA 形式（带“门”的地图）

作者提出了一种新的地图绘制方法，叫做GSA（门控静态单赋值形式）。

• 比喻：想象给仓库的每个路口都装上了**“智能门”和“路牌”**。
  • 以前的地图（SSA）只告诉你“这里有两个来源的货物汇合了”，但没说清楚“到底哪条路来的”。
  • GSA 地图不仅告诉你货物来源，还明确标出了**“只有当红灯亮时，货物才从这条路来”**（控制依赖）。
• 效果：有了这张带“门”的地图，算法就能像侦探一样，精准地追踪每一个变量的来源，无论程序结构多复杂（哪怕像迷宫一样），都能准确找出那些分散的、重复的“幂等任务包”。

5. 实际应用：代码瘦身（Code-Size Reduction）

一旦找到了这些分散的重复任务，算法会做三件事：

1. 剪下：把分散在各处的重复代码块剪下来。
2. 打包：把它们合并成一个通用的“标准函数”。
3. 替换：把原来那些重复的代码块删掉，只留下一个“调用这个标准函数”的指令。

结果：

• 空间节省：就像把仓库里 10 个重复的“搬运工”换成了 1 个“标准搬运流程”，仓库（程序文件）变小了。
• 实验数据：在测试了 2000 多个真实程序后，作者发现，在某些特定的复杂程序上，这种方法能把代码体积减少 7% 到 12%。这比以前的任何单一方法都要强，而且它还能发现以前方法看不到的重复部分。

6. 代价与收益

• 编译时间：因为要画这张复杂的“带门地图”并仔细追踪，编译程序的时间稍微增加了一点点（平均约 4%）。
• 运行速度：程序运行起来几乎没有变慢，甚至因为代码更紧凑，CPU 缓存效率更高，在某些情况下反而跑得更快了。
• 互补性：这个方法不是要取代以前的方法，而是和它们**“组队”**。如果把新方法、旧方法和其他优化手段一起用，效果最好，能进一步压缩代码。

总结

这篇论文就像是一个**“超级整理师”。它不再满足于只整理整齐排列的重复物品，而是利用一种“带路牌的智能地图”（GSA），深入复杂的迷宫，把那些分散在角落、看似杂乱但本质相同**的重复工作找出来，打包成一个通用的“标准件”。

这样做不仅让程序文件变得更小（节省存储空间和带宽），而且因为逻辑更清晰，程序运行起来也更高效。这对于嵌入式设备（如手机、汽车芯片，空间宝贵）和大型服务器（节省内存和传输成本）来说，是一个非常实用的优化技术。

技术摘要

论文技术总结：基于幂等切片（Idempotent Slices）的代码大小缩减

1. 研究背景与问题定义

1.1 核心概念：幂等向后切片 (Idempotent Backward Slices)

论文提出了一种新的程序切片概念——幂等向后切片。

• 定义：给定程序中的一个值，其幂等向后切片是指计算该值的最大子程序。该子程序具有幂等性（Idempotent），即对于相同的输入变量绑定，无论执行多少次，其计算结果和程序的可观察状态（如内存、控制流）都保持一致。
• 与传统的区别：
  • 传统切片（Dense Slice）：关注影响某个指令的所有语句，通常用于调试或测试，可能包含副作用（如内存写入、异常）。
  • 幂等切片：必须是引用透明的（Referentially Transparent），即可以被视为一个纯函数。它不能包含可能改变全局状态或引发异常的指令（如写内存、函数调用、除零风险等）。
  • 稀疏性：基于 SSA（静态单赋值）形式，仅追踪定义 - 使用链，而非所有语句。

1.2 现有方法的局限性

此前，Guimarães 和 Pereira (2023) 曾尝试利用类似概念将“按值调用”转换为“按需调用”（Lazy Evaluation）。然而，他们的算法存在两个主要缺陷，导致无法在通用控制流图（CFG）上正确提取切片：

1. 依赖 CSSA 属性：原算法假设程序满足“常规静态单赋值”（CSSA）属性，即 $\phi$ 函数的存活范围不重叠。但在实际优化后的代码中，变量常通过 $\phi$ 函数关联且存活范围重叠，导致算法失效。
2. 依赖"Hammock"结构：原算法要求控制流图可分解为单入口单出口（SESE）区域的树结构。对于不具备此结构的复杂 CFG（如某些特定的分支模式），原算法会遗漏必要的控制依赖边，导致切片不完整。

2. 方法论

2.1 核心算法：基于 GSA 形式的切片提取

为了解决上述问题，作者提出了一种基于 门控静态单赋值（Gated Static Single Assignment, GSA） 形式的算法。

• GSA 形式：在 SSA 基础上，显式地引入控制谓词（Gate）。
  • 用 $\gamma$-指令 替代 $\phi$ 函数，将控制流路径的谓词与数据流显式绑定。
  • 用 $\mu$-指令 表示循环头，用 $\eta$-指令 表示循环出口处的值门控。
  • 优势：GSA 将数据依赖和控制依赖统一编码在指令语法中，无需单独计算控制依赖图。
• 算法流程：
  1. 转换：将程序转换为 GSA 形式（采用 Tu 和 Padua 的路径编号算法）。
  2. 依赖图遍历：从切片准则（目标变量）开始，在 GSA 依赖图上进行向后遍历。
     • 由于 GSA 显式了控制依赖，遍历过程只需跟随所有边（数据边和控制边）。
     • 停止条件：
       • 函数边界：遇到函数参数停止。
       • 循环边界：遇到定义在同一循环深度（Loop Depth）的 $\mu$ 指令或更浅深度的变量停止（确保切片不跨越循环边界，保持幂等性）。
  3. 切片提取：收集遍历到的所有基本块，形成切片区域。
  4. 重构控制流：利用“第一支配点”（First Dominator）概念，将切片区域重构为独立的单入口函数（Single-Entry Function）。

2.2 应用：基于切片的代码大小缩减 (SBCR)

作者将幂等切片应用于代码大小优化，提出了 SBCR (Slice-Based Code-Size Reduction) 流程：

1. 识别：遍历程序中的所有二元指令，识别其幂等向后切片。
2. 外提（Outlining）：将符合条件的切片提取为独立的函数。
3. 去重与合并：
   • 利用 LLVM 的 mergefunc 机制，检测并合并同构（Isomorphic）的切片函数。
   • 使用结构哈希（Structural Hashing）快速过滤，再进行精确等价性检查。
4. 成本模型：仅当合并后的代码能减少总体大小时才保留。模型参数包括：指令数 ($I$)、参数数 ($P$)、出现次数 ($C$)。
   • 实验得出的最佳阈值：$P \le 1$, $I \le 20$, $C \ge 10$。

3. 主要贡献

1. 形式化定义：首次形式化了“幂等向后切片”的概念，明确了其作为引用透明函数的语义属性。
2. 鲁棒算法：提出了一种基于 GSA 形式的高效算法，能够正确处理非 CSSA 属性和非 Hammock 结构的控制流图，解决了现有算法的遗漏问题。
3. 稀疏代码缩减优化：实现了 SBCR 优化器，能够合并非连续、非有序甚至跨基本块的指令序列，这是传统基于序列对齐（Sequence Alignment）或仅针对基本块内连续指令的优化器（如 LLVM IROutliner）无法做到的。
4. 实证评估：在 LLVM 测试套件（2007 个程序）上进行了全面评估，证明了该方法在特定场景下的显著效果，且与其他优化技术互补。

4. 实验结果

实验在 LLVM 17 上运行，对比了三种技术：

• SBCR (本文方法)
• FMSA (Rocha et al., 2020，基于序列对齐的函数合并)
• IROutliner (LLVM 标准外提 Pass)

关键数据：

• 代码大小缩减：
  • 在整体 2007 个程序中，SBCR 对 .text 段的几何平均缩减为 -0.11%（部分程序因开销增加）。
  • 但在受益的程序子集中（29 个程序），SBCR 实现了 -7.24% 的几何平均缩减。
  • 最佳案例：在 AMGmk 基准测试中，SBCR 在 -Os 优化基础上进一步缩减了 -12.49% 的代码大小。
• 互补性：
  • SBCR 并不包含也不被 FMSA 或 IROutliner 包含。三者发现的冗余模式不同。
  • 组合效果：将三者串联（IROutliner $\to$ SBCR $\to$ FMSA）在 86 个基准测试中实现了 -14.43% 的指令数缩减，优于单独使用任何一项。
• 运行时性能：
  • 大多数情况下无显著性能差异。
  • 部分程序因指令缓存（I-Cache）局部性提升而加速（如 GlobalDataFlow-dbl 加速 3.39%）。
  • 少数程序因函数调用开销略有减速（平均 +0.06%）。
• 编译开销：
  • 平均增加编译时间 4.22%。
  • 尽管理论复杂度为 $O(N^2)$，但在实际代码中表现出近线性行为，因为大多数切片很小且满足成本模型的切片很少。

5. 意义与结论

• 理论意义：证明了 GSA 形式是进行精确程序切片和依赖分析的优越基础，能够处理复杂的控制流依赖。
• 工程价值：
  • 提供了一种新的代码去重维度：能够识别并合并非连续的冗余代码块。
  • 对于高度优化的代码（如 -Os 序列后），SBCR 能发现传统基于连续指令块的优化器无法发现的冗余。
  • 与现有的代码大小优化技术（如 FMSA, IROutliner）具有互补性，组合使用可最大化代码压缩率。
• 未来方向：需要进一步优化成本模型和启发式算法，以防止在激进应用时导致代码膨胀，并探索与基于配置（Profile-Guided）优化的结合。

总结：该论文通过引入幂等向后切片和 GSA 形式，解决了一个长期存在的控制流依赖分析问题，并据此提出了一种强大的代码大小缩减技术。实验表明，该方法在特定场景下能显著减小二进制体积，且与其他优化手段结合效果更佳。