Program Slicing

论文地址：Program Slicing | IEEE Journals & Magazine | IEEE Xplore

TSE-1984-CCFA

总结：1.基于“切片准则”从程序中抽取一个子程序，使得在语句处对变量集的行为与原程序一致；2.寻找最小切片无法算法自动化，因可规约为停机问题；3.Weiser 提供了保守的数据流分析方法获取可行切片

背景与动机

大规模程序需要分解 Weiser 指出，大型程序若要方便人类理解与维护，就必须能被分解成可管理的部分。常见的分解方式包括过程（procedures）和抽象数据类型（ADTs），但这些都要求在编程时明确设计，难以在程序已完成后自动抽取出可独立执行、且与某些行为相关的子程序。

程序切片（Program Slicing）的提出 程序切片是一种根据“数据流（data flow）和控制流（control flow）”分析来自动分解程序的方法。核心思想是：

先选定某个“感兴趣”的程序点及变量集（即“切片准则”）；
然后在保证“对这些变量在该点的行为不变”的前提下，尽量删去与此无关的其它部分；
形成一个可独立编译/执行的“切片”

关键性质 论文强调切片在保证原程序指定行为（语义）不变的同时，极大地简化了程序规模。Weiser 也论述了切片在调试（debugging）、并行执行（parallel processing）、维护（maintenance）等方面都有潜在价值

主要贡献

给出了切片的形式化定义；
讨论了最小切片（statement-minimal slice）不可判定；
提出了基于数据流分析的近似算法；
通过实证（对学生编写的 19 个编译器）探讨了切片规模、重叠率等统计结果

定义

论文第 1～2 页首先在不带过程调用的场景下，给出图论与程序执行的形式化

有向图（Digraph）

令为一有向图：

是节点集合
是有序边集合
若，则称为的直接前驱（immediate predecessor），为的直接后继（immediate successor）

流程图（Flowgraph）

在编译器和程序分析中，一般用单入口（）形式的流程图描述程序控制流：从出发，可达所有节点

Hammock graph：进一步要求单出口（）结构，使得从任何节点都能到达出口节点

程序节点的 REF / DEF 集

：语句（或节点）读取（使用）了哪些变量
：语句写入（定义）了哪些变量

状态轨迹（State Trajectory）

程序的执行可视为状态序列：

其中表示当前执行的节点，是对所有变量赋值的函数（映射变量名 →值），该轨迹仅讨论会终止（halt）的情况

切片准则（Slicing Criterion）

形式表示为，其中是程序中的某条语句（或节点），是一组感兴趣的变量
研究如何在保证 “语句处的变量集合的行为不变” 前提下，删去无关语句

投影函数（Projection Function）

给定切片准则，定义投影作用于状态轨迹，丢弃与不相关的节点，以及与不相关的变量值

若执行轨迹是，则只保留满足的状态，并在其状态映射中仅保留变量的赋值。

切片（Slice）

在此定义下，程序的一个子集若能在执行时对切片准则的投影保持完全一致，则称为原程序在该准则下的一个“切片”
一般可通过删除零个或多个语句而得

逆支配点（inverse dominator, d） 在单出口流程图（hammock graph）中，若节点处于从到出口节点的所有路径上，则逆支配

INFL(b)（Influence set）取一条从分支节点到其最近逆支配点的路径，除开两端，路径上所有语句就组成，它刻画了的控制范围——即哪些语句的执行取决于的分支选择

寻找切片的方法

最小切片判定不可解

论文先证明：若试图找到“在语句数量上最小”的切片，这相当于能区分一个程序中某条语句是否会在执行中对目标点的变量产生影响。而此过程可以用来解决停机问题（halting problem），因此不存在通用的可判算法（第 2 页末到第 3 页）
数据流近似算法
- 由于最小性不可解，Weiser 给出了基于数据流分析的保守方法
- 定义了一个函数，指示在节点处对切片准则可能相关的变量集合。它通过向前或向后传播依赖关系、合并控制分支等方式递归计算
- 具体形式如：若，则初始相关变量包含准则中的。若是某个节点的直接前驱，则视乎、和的交集来决定哪些变量可能对后续节点产生影响
- 如果当前节点就是切片标准中的目标点，那么我们关注的变量就是切片标准中指定的变量集合中的成员，这个条件是为了在程序中向后回溯依赖，推导哪些变量会影响后续节点的值，从而影响点的状态。当前节点中读取了变量 ；也定义了变量 ，且是后续节点所依赖的；那么就认为也应该被认为是相关变量，纳入。当前节点 没有定义变量 ，即的值未被改变；但该变量是后继节点所依赖的；那么我们认为当前节点也对的传播具有影响，因此也纳入相关变量集合中
语句级的切片
- 进一步将变量相关性映射到语句相关性：若当前语句定义了某个后续需要的变量，则该语句被保留
- 这样便构造出一个近似的切片集合，保证不遗漏真正会影响目标变量的语句，但也可能因“保守”而多包含一些间接无关的语句
- 定义的某个变量（即在中）也出现在下一条语句的相关变量集合中
- 充分条件，非必要条件，在一定影响，不在可能影响
- ：之前通过数据依赖得到的“直接相关语句”集合
- ：把中每条语句所处 分支节点的控制区 INFL(n) 全部并起来，得到 对切片“间接相关”的所有分支语句
- 这些分支本身也许 并不定义或引用目标变量，但它们决定了中语句是否会被执行，因此需要纳入后续切片计算
寻找切片的迭代扩张法

核心思路：从仅含 直接数据依赖 的初始切片出发，反复把 1）影响这些语句的控制语句（分支） 2）新语句产生的 数据依赖 一并加入，直到集合不再增长（达到不动点）

步骤	数学递推	说明
1. 扩展相关变量		把当前分支集合中各分支对节点的变量影响并入
2. 更新分支集合		用求控制范围，把新切片语句控制它们的分支全部纳入
3. 更新语句切片	$或$	若语句属于分支集合，或其定义的变量被下一条语句使用，则加入切片

循环直到 不再变化，得到最终切片和变量集合

复杂度估计

每轮需要一次 数据流求解（）＋一次 支配/逆支配分析（近线性）来计算
至多引入条语句才会收敛 ⇒ 总复杂度上界（=语句数, =控制流边数），作者指出这一上界 偏保守，实践更快

在过程间跨越的切片

当程序包含多个过程/函数时，仅在当前过程内部生成的切片往往不足以保持 切片准则（slicing criterion）指定的语义，因为数据与控制信息会沿着调用链传播。Weiser 在 1984 年的经典论文中提出了一套 两步 + 迭代 的跨过程切片框架，核心在于：

单过程切片 （Step 1）
- 先把当前过程 P 当作一个 闭世界 进行切片，完全套用前一节介绍的 数据依赖 + 控制依赖迭代闭包方法
- 所有外部调用（例如 CALL Q(...)）临时视为普通语句，其 DEF/REF 使用已有的过程摘要（summary information）或保守近似
延伸切片准则 （Step 2）
- 根据 P 内部得到的相关 变量集 RC，为 被调过程 或 调用 P 的过程 生成 新的切片准则，再对子过程/父过程执行 Step 1
- 如此 UP / DOWN / ENT 三种传播在调用图中反复迭代，直到不再产生新准则

符号与基本概念

记号	含义
`C = ⟨i, V⟩`	初始切片准则：过程 `P` 内语句 i，变量集 V
`R_C(s)`	Step 1 得到的相关变量集合在语句 s 处的值
`S_C`	对应的语句切片集合
`UP_0(C)`	向上传播一次得到的新准则集合
`DOWN_0(C)`	向下传播一次得到的新准则集合
`ENT_0(C)`	入口传播（外部可调用入口）的新准则集合
`UP, DOWN, ENT`	作用于准则集合的映射，取并后再级联
`(UP ∪ DOWN ∪ ENT)^*(C)`	在调用图中取传递闭包 ⇒ 完整准则集合

向下传播 (DOWN)

设 P 在语句 i 调用过程 Q，形参为 F = (f₁,…,fₖ)，实参为 A = (a₁,…,aₖ)

可能外流的变量：
形参与作用域替换：将 ROUT(i) 中出现的实参替换为对应形参，再与 Q 可见变量 SCOPE_Q 相交
生成准则：

其中为的最后语句，保证投影时捕获到所有返回效果

向上传播 (UP)

若外过程 Q 在语句调用当前过程 P，则需把 影响 P 内部形参的变量 反向传播到 Q

设为 P 的第一条语句
用替换 A ← F（形参 → 实参）:

入口传播 (ENT)

对于 可被外部任意调用 的 entry procedures，无法精准获知谁会在何时调用它们。Weiser 采用 最坏情况 假设：

调用次序任意，且可能无限多次；
调用间可读写 所有外部全局变量 OUT；
每次调用都可能读写所有 引用形参 。

因此，若 P 为入口过程，构造 $为所有入口过程$

迭代算法与收敛

准则集  WorkList ← { C0 }
repeat
    取出一个准则 C ← WorkList
    S_C , R_C ← 单过程切片(P_C, C)   -- Step 1
    New ← UP_0(C) ∪ DOWN_0(C) ∪ ENT_0(C)
    将 New − 已处理 准则 放入 WorkList
until WorkList 为空
切片结果 = ⋃  所有 S_C

调用图与过程个数有限 → 迭代必定终止

复杂度

每轮：（重新求数据流） + 近线性（支配/逆支配求 B）
最多加入 n 条新语句 ⇒ 总体上界
Weiser 指出实际运行通常远快于理论上界

示例（改编自论文 Fig. 4）

1 READ(A,B)
2 CALL Q(A,B)
3 Z := A + B

PROCEDURE Q(VAR X,Y: INTEGER)
4   X := 0
5   Y := X + 3
6   RETURN

原准则 C₀ = ⟨3,{Z}⟩（关注输出 Z）
DOWN：由语句 2 得到 C₁ = ⟨6,{X,Y}⟩（形参 X,Y 在 Q 内可能影响返回）
UP：由 Q 返回再映射回调用者，得到 C₂ = ⟨2,{B}⟩
按迭代算法最终切片 = {1,2,3,4,5,6}（语义等价但移除了与 Z 无关代码）

优缺点与实践意义

优势	局限
自动、保守：不遗漏影响语句	切片可能偏大（保守近似）
精确参数替换，避免串名	需要过程摘要/符号信息
可与入口最坏假设结合单独编译	外部库过大时复杂度上升
为后续 SDG / 趋近最小切片技术奠基	无法区分“必经”与“实际可达”路径

实验

独立编译与外部过程

若程序调用外部库或过程、或被外部调用，尚需做最坏情况假设：外部过程可能读/写任何全局变量或传参变量
因此外部调用与被外部调用也会衍生新的切片准则，做进一步扩展分析
Weiser 提供了一个函数 ENT（entry）来处理这种多入口场景：将外部过程的可能读写集合纳入切片传播

切片规模的统计

论文第 5 页中，Weiser 将其方法应用到 19 个“学生编译器”上，每个约 500～900 行

做法：以输出语句（WRITE）+输出的变量集为切片准则，自动产生一系列切片；然后将差异小于 30 条语句的切片合并为“簇”（clusters）
统计结果见论文表 I：
- Useless（没出现在任何切片中的语句）、Common（在所有切片中的语句）、Slices（切片数量）、Clusters（合并后簇的数量）等指标
- 还统计了簇间的长度、重叠比（Overlap）等
主要结论：在这些编译器中，平均有相当一部分语句永远不会影响任何输出（Useless），证明切片能明显减小程序规模；同时也观察到不少切片之间共享大量语句（Overlap），说明编译器内部各功能耦合度较高

并行执行切片

因为一个切片是独立可执行的程序，它只产生对原程序整体行为的“部分投影”
若要在多处理器环境下并行执行，可以让各切片独立跑，通过“拼接器（splicer）”在运行时合并它们的输出流以重现完整行为；见论文中第 5～6 页的图示（Fig. 5）
这样做无需共享内存或锁机制，减少同步开销，但会产生重复计算。Weiser 指出这对分布式系统、VLSI 处理器设计等或有好处

未来展望

Weiser 在论文末尾（第 6 页）总结了程序切片的潜力及局限：

优势
- 可自动获得，对已有大型程序尤其有用
- 体量小，方便人工理解、调试、测试
- 彼此独立，可在并行/分布式场景下使用
- 精确定义，基于行为投影保证语义一致性
问题
- 计算代价：切片需要数据流、控制流分析，可能在大型代码上耗时颇高
- 某些程序可能在“感兴趣行为”上过度耦合，导致切片并未比原程序小多少
- 独立切片看似简单，但若合并时依旧有一些依赖无法被简化，需要手动再做优化
应用前景
- 调试与维护：程序员可更快聚焦到影响目标变量的关键语句
- 复杂系统：如分布式/并行系统，为减少同步开销，或进行“按需执行”
- 程序验证与度量：基于切片可定义新的复杂度量度，或进行等价验证等

总体评价与结论

学术地位：Weiser 的这篇 1984 年论文是“程序切片”概念的奠基之作。其形式化定义、不可判定结论以及数据流近似算法，至今仍构成相关研究的基础
实践意义：切片技术在调试、逆向工程、安全分析（信息流追踪）、软件演化等方面都被广泛使用。Weiser 提供了详实的实验和性能讨论，展示了切片在真实编译器项目中的可行性
后续影响：论文中提到的“控制依赖”、“跨过程切片”、“并行拼接”等想法，日后都发展成程序分析和分布式计算中的重要研究方向

换个研究

Program Slicing

Program Slicing

背景与动机

定义

寻找切片的方法