想象你是一家大饭店的主厨。你的后厨有几百道菜，每道菜都写在一张菜谱上：先洗菜、再切菜、开火、放调料……有一天，采购部通知你：酱油换牌子了。你脑子里立刻冒出一个问题——哪些菜的味道会变？ 要回答这个问题，光靠一摞菜谱是不够的：菜谱只写了每道菜自己的步骤顺序，却写不出「这道菜出锅的酱汁，是下一道菜腌肉的原料」，也写不出「只有在客人点了辣味套餐时，这道菜才会被端上桌」。你需要一张工序关系图：把每个步骤画成节点，用箭头标出「谁把半成品递给谁」（原料流动），以及「谁开了开关、谁才被执行」（条件闸门）。这张图，就是程序世界里的程序依赖图（Program Dependence Graph，PDG）。软件工程师和 AI 代码助手也靠同样的思路理解程序：改一行代码会波及谁？Bug 的根源藏在哪？这篇文章，就带你从零看懂这张「后厨地图」。

岗位关联

掌握程序依赖图，等于拿到「让 AI 真正读懂代码因果关系」的钥匙——它是程序切片、缺陷定位、变更影响分析、代码安全扫描等代码智能技术的共同地基，也是你从「会写代码」进阶为「会分析代码」的关键一步。

目录
  1. 可视化演示
  2. 基本概念：一张「后厨工序图」
  3. 数据依赖：原料接力赛
  4. 控制依赖：厨师长的「开关」
  5. 构建算法：两步画出工序图
  6. 程序切片：只动「相关」的步骤
  7. 影响分析：改一处，波及全厨房
  8. 工程挑战：千人厨房的效率难题
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示程序依赖图PDG的构建流程、程序切片分析与安全漏洞检测，交互切换查看各阶段核心指标。

本节配有交互动效（进入视口后自动加载，约 3KB）。

PDG构建流程：从源码到依赖图 AST语法树经控制流分析构建CFG控制流图 数据流分析融合控制依赖与数据依赖生成PDG PDG=CDG∪DDG 程序依赖图是程序切片和影响分析的核心数据结构

基本概念：一张「后厨工序图」

主厨画后厨地图时，不会把菜谱整段抄上去，而是把每一个操作步骤（洗菜、切姜、下锅、装盘）都画成一个小圆圈，再用两种箭头把它们连起来：红色箭头表示「只有前面那道判断通过了，这一步才会被执行」，绿色箭头表示「这一步的成品会作为原料流入那一步」。这张只关心因果、不关心「谁站在谁旁边」的图，就是后厨的工序关系图。

程序世界里，「步骤」就是源代码里的语句（statement）和判断条件（predicate）。把每个语句画成一个节点，把上述两种因果关系画成有向边，得到的图就叫程序依赖图（PDG）。它最早由 Jeanne Ferrante 等人在 1987 年提出，目的是把程序的语义依赖从代码的物理书写顺序中解放出来——就像工序图把因果从菜谱的排版里解放出来一样。

PDG 由两部分构成：数据依赖边记录「谁把值传给谁」，控制依赖边记录「谁决定谁是否执行」。二者合并，就得到一张同时携带数据流与控制流信息的程序表示。与控制流图（CFG）相比，PDG 不强调执行顺序的线性排列——顺序被「编码」进了依赖关系里：如果 A 必须比 B 先执行，那一定是因为 B 在数据上或控制上依赖于 A。

回到后厨：有了这张工序图，主厨不再需要按「菜谱页码」找答案，只需要沿着箭头看因果。接下来我们要做的，就是弄清这两种箭头分别是怎么产生的。

PDG(G)=(N, Ec∪Ed)\displaystyle \mathrm{PDG}(G) = (N,\ E_{c} \cup E_{d})
通俗说：PDG 就是「节点 + 两类箭头」的集合，节点是语句，一类箭头管数据流动，一类箭头管执行开关。
  1. N（节点集合）程序里的每个语句、每个判断条件都被抽象成一个节点。
    N={S1, S2, ⋯ , Sn}N = \{ S_{1},\ S_{2},\ \cdots,\ S_{n} \}
  2. E_c（控制依赖边）从「判断条件」指向「由它决定是否执行的语句」的边。
    Ec={(Si, Sj)∣branch(Si)⇒exec(Sj)}E_{c} = \{ (S_{i},\ S_{j}) \mid branch(S_{i}) \Rightarrow exec(S_{j}) \}
  3. E_d（数据依赖边）从「写入变量 v 的语句」指向「读取 v 的语句」的边。
    Ed={(Si, Sj)∣def(Si, v)⇒use(Sj, v)}E_{d} = \{ (S_{i},\ S_{j}) \mid def(S_{i},\ v) \Rightarrow use(S_{j},\ v) \}
  4. ∪（并集）两类边合并成完整的依赖图，且互不重叠。
    Ec∩Ed=∅E_{c} \cap E_{d} = \varnothing

数据依赖：原料接力赛

后厨里最常见的因果是「供料」：炖牛腩的汤底，要用来烧豆腐；切好的姜丝，要撒进蒸鱼。如果姜丝切得不对，蒸鱼的味道就变了——这就是原料接力。后厨地图上的绿色箭头，画的就是这种半成品传递。

程序里的「原料」是变量（variable）。一个语句写入（定义）变量 v，另一个语句读取（使用）变量 v，且中间没有被再次写入，那么后者就在数据上依赖前者。这种关系叫数据依赖（data dependence），也叫定义-使用关系（def-use relation）。

数据依赖分为三种：流依赖（flow dependence，写后读 RAW）、反依赖（anti-dependence，读后写 WAR）和输出依赖（output dependence，写后写 WAW）。其中流依赖是「真依赖」——它代表值的真实传递，无法通过改名消除；反依赖和输出依赖是「假依赖」，源于变量被复用，可以通过引入新变量或重命名来消除，编译器做寄存器重命名时就会用到这个性质。检查「中间是否有重定义」是判定流依赖的关键：它要求从写入语句到读取语句的路径上，v 没有被任何语句覆盖，即找到的是「最近的写入者」。

想象一锅高汤：只要中间没人把汤倒掉重新换水，端到下一道菜面前的，就是最初那锅汤。数据依赖就是在回答：「这道菜用的，到底是哪一锅汤？」

Sj→ δ Si  ⟺  ∃v: Def(Si, v)∧Use(Sj, v)∧∀Sk∈path(Si, Sj): ¬Def(Sk, v)\displaystyle S_{j} \xrightarrow{\ \delta\ } S_{i} \iff \exists v:\ Def(S_{i},\ v) \wedge Use(S_{j},\ v) \wedge \forall S_{k} \in path(S_{i},\ S_{j}):\ \neg Def(S_{k},\ v)
一行读懂：i 写了 v、j 读了 v、i 到 j 之间没人再改 v，j 就依赖 i。
  1. Def(S_i, v)（定义）语句 i 对变量 v 赋值，v 的值从这里「出生」。
    Def(Si, v):v←⋯Def(S_{i},\ v):\quad v \gets \cdots
  2. Use(S_j, v)（使用）语句 j 读取 v 的值参与计算。
    Use(Sj, v):⋯←⋯+vUse(S_{j},\ v):\quad \cdots \gets \cdots + v
  3. path(S_i, S_j)（路径）从 i 到 j 在 CFG 上要经过的所有语句。
    path(Si, Sj):Si→Sk1→⋯→Sjpath(S_{i},\ S_{j}):\quad S_{i} \to S_{k_{1}} \to \cdots \to S_{j}
  4. ¬Def(S_k, v)（中间无覆盖）路径上每个中间语句都没有重新定义 v，保证 j 读到的是 i 写的那个值。
    ∀Sk∈path: v∉Def(Sk)\forall S_{k} \in path:\ v \notin Def(S_{k})

控制依赖：厨师长的「开关」

后厨里还有一种因果与原料无关：「只有客人点了辣味套餐，这道水煮鱼才会下锅；没点，鱼就养在水池里。」水煮鱼并不「消费」点单这个动作的产物，但它的生死由点单决定——这就是开关关系。

程序里，「点单」对应判断条件（predicate），比如 if 语句。一个语句是否会被执行，取决于判断条件走哪个分支。这种「是否执行由谁决定」的关系，就是控制依赖（control dependence）。它建立在控制流图（CFG）的基础上，核心工具是后支配（post-domination）关系：从某个节点出发，无论走哪条路径，最终都必然经过另一个节点。

基于后支配，控制依赖的精确定义是：存在 i 的一个后继 p，使得 j 后支配 p，但 j 并不后支配 i 本身。这一定义刻画了「j 是否执行，取决于从 i 走了哪条路」。特别要注意循环结构：循环头（loop header）控制着回边上的语句是否继续执行，因此循环体末尾的语句也控制依赖于循环条件。

所以不是「写在 if 大括号里的就算被控制」——就像后厨里，无论客人点不点辣，米饭都要蒸，米饭就不受「点辣」开关控制。只有那些「选了这个分支才做、选了那个分支就跳过」的菜，才真的被开关捏在手里。

Sj c-dep Si  ⟺  ∃p∈succ(Si): PDOM(Sj, p)∧¬PDOM(Sj, Si)\displaystyle S_{j}\ \text{c-dep}\ S_{i} \iff \exists p \in succ(S_{i}):\ PDOM(S_{j},\ p) \wedge \neg PDOM(S_{j},\ S_{i})
通俗说：从 i 分岔出去的路，有一条必然经过 j，但 j 不是所有路的必经点——j 就被 i 的开关控制着。
  1. succ(S_i)（分支出口）i 在 CFG 中的直接后继节点集合，即「分岔出去的路」。
    succ(Si)={p∣(Si, p)∈ECFG}succ(S_{i}) = \{ p \mid (S_{i},\ p) \in E_{CFG} \}
  2. PDOM(S_j, p)（后支配支路）从支路 p 出发的每条路径最终都经过 j，走这条路就躲不开 j。
    ∀π∈paths(p, EXIT): Sj∈π\forall \pi \in paths(p,\ EXIT):\ S_{j} \in \pi
  3. ¬PDOM(S_j, S_i)（不后支配源头）存在从 i 出发却不经过 j 的路径，说明 j 不是「无论如何都会执行」。
    ∃π′∈paths(Si, EXIT): Sj∉π′\exists \pi' \in paths(S_{i},\ EXIT):\ S_{j} \notin \pi'
  4. ∃p（存在判定）两条支路中至少有一条被 j 锁死，j 才真正被 i 的抉择「牵着走」。
    ∃p∈succ(Si): PDOM(Sj, p)∧¬PDOM(Sj, Si)\exists p \in succ(S_{i}):\ PDOM(S_{j},\ p) \wedge \neg PDOM(S_{j},\ S_{i})

构建算法：两步画出工序图

主厨要画后厨工序图，不会一次画出所有箭头。他先按动线把灶台、案板、蒸锅的位置摆好（相当于流程骨架），再一道菜一道菜地核对：这道菜用了哪锅汤？那笔订单决定了哪道菜下锅？分两轮检查，才画得干净。

PDG 的构建也分两大步，且顺序有讲究：第一轮在 CFG 上计算后支配关系，生成控制依赖边；第二轮做数据流分析，计算定义-使用链，生成数据依赖边。两轮结果合并，即是完整 PDG。

第一轮中，控制依赖的计算流程是：构造 CFG → 求后支配树 → 对每个节点考察其每个后继，用前述定义判定依赖。第二轮中，数据依赖的计算常用到达定义（reaching definitions）数据流方程：对每个基本块 B，求出「进入 B 时仍然活跃的定义集合 In[B]」与「离开 B 时的定义集合 Out[B]」。如果一个定义能到达某个使用点且未被杀死（kill），就生成一条数据依赖边。为了提高精度，还可以加入别名分析、过程间分析等手段，减少「误报」的依赖边。

就像主厨核对原料：进后厨时哪些高汤还活着，被哪道菜用掉、被哪道菜换掉，最后哪些汤还能传给下一道菜——方程里的每个符号，都是后厨账本上的一行。

In[B]=⋃P∈pred(B)Out[P],Out[B]=Gen[B]∪(In[B]−Kill[B])\displaystyle In[B] = \bigcup_{P \in pred(B)} Out[P], \qquad Out[B] = Gen[B] \cup (In[B] - Kill[B])
通俗说：把「进入厨房时还活着的原料记录」汇集起来，减去被这道工序消耗或覆盖的，加上这道工序新产生的，得到「离开厨房时还活着的原料记录」。
  1. In[B]（块入口定义集）所有前驱块流出的定义在 B 入口处汇合，取并集。
    In[B]=⋃P∈pred(B)Out[P]In[B] = \bigcup_{P \in pred(B)} Out[P]
  2. Gen[B]（本块生成）B 内部新产生的变量定义，且在本块内没有被再次覆盖。
    Gen[B]={(v, d)∣d∈B∧v∈Def(d)∧¬∃d′∈B, d′>d: v∈Def(d′)}Gen[B] = \{ (v,\ d) \mid d \in B \wedge v \in Def(d) \wedge \neg \exists d' \in B,\ d' > d:\ v \in Def(d') \}
  3. Kill[B]（本块杀死）B 内对 v 的重新定义，会杀掉所有更早到达的 v 的定义。
    Kill[B]={(v, d)∣v∈Def(B)∧d∉B∧v∈Def(d)}Kill[B] = \{ (v,\ d) \mid v \in Def(B) \wedge d \notin B \wedge v \in Def(d) \}
  4. Out[B]（块出口定义集）入口活跃的定义减去被杀死者，并上新生成者，就是本块交给后继的「接力棒」。
    Out[B]=Gen[B]∪(In[B]−Kill[B])Out[B] = Gen[B] \cup (In[B] - Kill[B])

程序切片：只动「相关」的步骤

客人投诉水煮鱼太麻。主厨不会把整个后厨翻一遍，而是沿着工序图的箭头往回走：鱼是谁腌的？花椒是谁放的？腌制用的料酒是哪批？只有这些「影响麻味」的步骤才需要检查。这张「与某个结果有关的步骤子集」，就是后厨世界的切片。

程序里，这个操作叫程序切片（program slicing）。给定切片准则（slicing criterion）——一个语句 S 和一组变量 V——程序切片就是求「所有可能影响 S 处 V 取值的语句集合」。这个集合叫后向切片（backward slice），它在调试与缺陷定位中大显身手。

程序切片的价值在于：它把一个庞大的程序约简为与当前关注点相关的子集，且保证在切片准则上的行为与原程序一致。在 PDG 上，切片计算变成了一次可达性（reachability）问题：从准则节点出发，沿数据依赖边和控制依赖边反向遍历，所有能到达的节点构成后向切片；反过来，从准则节点沿依赖边正向遍历，所有被它影响的节点构成前向切片（forward slice）。经典的 Weiser 切片与基于依赖图的 Ottenstein–Ottenstein 切片是两种主要流派，后者更高效，因为它把问题归结为图可达性，一次遍历即可完成。

后向切片是「查上游」：这盘鱼太麻，往上追到花椒；前向切片是「看下游」：如果换掉这批花椒，哪些菜会跟着变味。方向不同，用途不同，但都在这张因果网上走路。

BackSlice(S, V)={n∈N∣n→(Ec∪Ed)∗S}\displaystyle BackSlice(S,\ V) = \{ n \in N \mid n \xrightarrow{(E_{c} \cup E_{d})^{*}} S \}
通俗说：后向切片就是「从目标语句倒着沿箭头走，凡是走得到的地方都收进名单」。
  1. S（切片准则的语句）我们关心行为的目标语句，例如出错的 print 或可疑的赋值。
    criterion=(S, V)criterion = (S,\ V)
  2. V（关注的变量集）我们关心这些变量在 S 处的取值。
    V⊆Use(S)∪Def(S)V \subseteq Use(S) \cup Def(S)
  3. E（依赖边集合）切片沿数据流与控制流的因果链传播，两类箭头都算数。
    E=Ec∪EdE = E_{c} \cup E_{d}
  4. n →* S（可达闭包）从 n 出发沿 E 走零步或多步能到 S，n 就入选切片。
    BackSlice(S, V)={n∈N∣n→E∗S}BackSlice(S,\ V) = \{ n \in N \mid n \xrightarrow{E^{*}} S \}

影响分析：改一处，波及全厨房

采购部通知酱油换牌子。主厨最关心的是：这瓶新酱油进了哪些菜？哪些菜的味道会因此改变？他会从「酱油」这个节点出发，沿着工序图的箭头往前推，被波及的菜，都要重新试菜、重新上菜单。

程序里，「换酱油」就是一次代码变更（change），「重新试菜」就是回归测试（regression testing），而「找出哪些代码会受影响」的过程叫变更影响分析（change impact analysis）。它的核心技术正是前向切片。

设变更涉及的语句集合为 Δ，影响集就是 Δ 中每个语句的前向切片的并集。被影响到的语句，其执行结果可能改变，因而需要重新测试。缺陷定位（fault localization）则是影响分析的「镜像」用法：从失败点出发做后向切片，把嫌疑代码从整个程序缩小到切片范围内。在代码安全分析中，污点分析也依赖 PDG：把用户输入标记为污点（taint），沿数据依赖边追踪它是否流入危险函数（sink），从而发现注入漏洞。

就像试菜清单——酱油涉及的菜划勾，没涉及的菜照常出餐。影响分析让 AI 工程师在动代码之前，先看清「这一改，会惊动后厨里的谁」。

Impact(Δ)=⋃s∈ΔForwardSlice(s, All(s))\displaystyle Impact(\Delta) = \bigcup_{s \in \Delta} ForwardSlice(s,\ All(s))
通俗说：把每个变更点「向前看」的波及范围都圈出来，合并在一起，就是整个变更的爆炸半径。
  1. Δ（变更集）一次提交或重构中所有被修改的语句。
    Δ={s∈N∣changed(s)}\Delta = \{ s \in N \mid changed(s) \}
  2. All(s)（全变量集）s 处所有变量都值得关注，因为变更可能影响任意输出。
    All(s)=Def(s)∪Use(s)All(s) = Def(s) \cup Use(s)
  3. ForwardSlice（前向切片）从 s 出发沿依赖边正向可到达的语句，即「被 s 影响」的集合。
    ForwardSlice(s, V)={n∈N∣s→(Ec∪Ed)∗n}ForwardSlice(s,\ V) = \{ n \in N \mid s \xrightarrow{(E_{c} \cup E_{d})^{*}} n \}
  4. ⋃（并集）多处变更的影响区重叠也没关系，并集给出总爆炸半径。
    Impact(Δ)=⋃s∈ΔForwardSlice(s, All(s))Impact(\Delta) = \bigcup_{s \in \Delta} ForwardSlice(s,\ All(s))

工程挑战：千人厨房的效率难题

上面讲的是几十道菜的小厨房。现实中，大厂的后厨有上百万道菜：几千位厨师同时改菜谱、几万道菜共享原料池。要全量画一张覆盖所有因果的工序图，光箭头就可能画出几十亿条——纸都不够用。主厨必须学会「偷懒」：只重画被改动的区域，用近似图代替精确图。

程序仓库也一样：Linux 内核这类千万行级项目，所有语句构成的全量精确 PDG，其依赖边在最坏情况下是 O(n²) 量级，构建与存储都难以承受。工程化 PDG 的三大主题是：大规模构建、增量更新、精度-效率权衡。

针对大规模构建，主流思路是模块化分层：先为每个函数构建过程内 PDG，再用调用图（call graph）建立过程间依赖，按需解析别名，避免全量精化。针对增量更新，增量 PDG 构建只对变更语句所在函数重建依赖边，再沿调用边传播变更标记，使单次更新成本从 O(n²) 降到接近 O(Δ)。精度-效率权衡方面，工业级分析器常采用流不敏感或上下文不敏感的近似，牺牲少量精度，换取毫秒级分析与可控内存。

千人厨房里的工序图永远画不完，但聪明的后厨只维护「最近改动区域的因果网」，并用足够的近似保证大多数时候判断正确。理论告诉你能画多准，工程告诉你在有限时间里画得多快——两者之间的缝，正是 AI 代码助手的用武之地。

∣Ec∣+∣Ed∣=O(n2)→ Δ-update O(∣Δ∣)\displaystyle |E_{c}| + |E_{d}| = O(n^{2}) \quad \xrightarrow{\ \Delta\text{-update}\ } \quad O(|\Delta|)
通俗说：全量图最坏是「每人和每个人都可能发生关系」的规模；增量更新只想一个问题：「这次只改了这几行，把这几行周边的因果网重画就好。」
  1. n（语句规模）程序规模的基本度量，百万行代码即 n 达百万级。
    n=∣N∣n = |N|
  2. O(n²)（最坏边数）任意两语句之间理论上都可能产生依赖边，边数是节点数的平方级。
    ∣E∣≤n(n−1)2=O(n2)|E| \le \frac{n(n-1)}{2} = O(n^{2})
  3. Δ（变更规模）一次提交实际改动的语句数，通常远小于 n。
    ∣Δ∣≪n|\Delta| \ll n
  4. O(|Δ|)（增量目标）理想情况下，更新成本只与改动规模挂钩，与总仓库大小解耦。
    cost≈O(∣Δ∣)cost \approx O(|\Delta|)

AI 应用场景

场景1：AI 代码助手的缺陷定位

阶段：代码理解与诊断

解决的问题：面对一个失败的测试用例，AI 助手要回答「bug 在哪里」。传统做法是让工程师在数千行日志里人肉搜索，或把整个文件喂给大模型「猜」。基于 PDG 的后向切片，AI 先把失败断言（如 assert x == 5）作为切片准则，得到影响 x 取值的语句集合，再把模型注意力集中到切片内的候选行，定位准确率和推理成本都大幅改善。

具体案例：Meta 的内部调试工具使用动态后向切片分析崩溃堆栈对应的语句，辅助工程师在几分钟内定位生产环境崩溃根因；国内某编译器团队把 PDG 切片嵌入 AI 插件，在「空指针异常」场景下将嫌疑代码从平均 200 行缩小到 15 行左右。

场景2：开源代码的安全漏洞扫描

阶段：静态分析与安全审计

解决的问题：开源组件「投毒」事件频发，人工审计不可能读完全部依赖。基于 PDG 的污点分析把「用户可控输入」标记为污点源，沿数据依赖边追踪它是否到达危险函数（如 eval、SQL 拼接），同时用控制依赖边过滤掉「即使数据流到也没有实际执行路径」的误报。

具体案例：CodeQL 的污点追踪查询、SonarQube 的安全规则都构建在类似 PDG 的中间表示上。安全团队写一条「从 request.getParameter 到 Statement.execute 的流式查询」，就能在数秒内扫完整仓，发现 SQL 注入与命令注入漏洞。

场景3：大型仓库的测试影响分析

阶段：持续集成与质量保障

解决的问题：大仓每次提交动辄触发上万测试、跑数小时。传统做法是「全量回归」，浪费算力且反馈慢。基于前向切片的影响分析：对本次变更的语句集合求前向切片，只有覆盖到切片内语句的测试才被选中重跑。

具体案例：Google 的测试影响分析平台在每次代码评审后计算影响集，将需要运行的测试裁剪到全量的 1%~10%，让合并前验证从小时级降到分钟级；Meta 的同类平台让万级测试的 monorepo 也能做到「改哪测哪」。

Python 演示

python69 行
#!/usr/bin/env python3# -*- coding: utf-8 -*-"""小型程序依赖图(PDG)构建与后向切片演示"""  class Stmt:    """程序语句: 编号, 文本, 写入变量, 读取变量, 控制守卫"""     def __init__(self, sid, text, defined, used, ctrl=None):        self.sid = sid        self.text = text        self.defined = set(defined)   # 本语句写入的变量        self.used = set(used)         # 本语句读取的变量        self.ctrl = ctrl              # 控制本语句的 if 条件编号  def data_deps(prog):    """扫描定义-使用链, 求数据依赖边(流依赖)"""    deps = set()    last_def = {}                          # 变量 -> 最近一次写入它的语句编号    for st in sorted(prog, key=lambda s: s.sid):        for v in st.used:                  # 语句读了哪些变量            if v in last_def:              # 存在未覆盖的最近写入者                deps.add((last_def[v], st.sid))        for v in st.defined:               # 语句写了哪些变量            last_def[v] = st.sid    return deps  def all_deps(prog):    """合并数据依赖边与控制依赖边, 得到完整 PDG 边集"""    deps = data_deps(prog)    for st in prog:        if st.ctrl is not None:            deps.add((st.ctrl, st.sid))    # 控制依赖边: if -> 分支语句    return deps  def backward_slice(prog, deps, target):    """沿依赖边反向传播, 返回 target 语句的后向切片"""    rev = {}    for src, dst in deps:        rev.setdefault(dst, []).append(src)  # 建反向邻接表    worklist = [target]    seen = set()    while worklist:        cur = worklist.pop()        if cur in seen:            continue        seen.add(cur)        worklist.extend(rev.get(cur, []))    # 沿反向边继续扩散    return sorted(seen)  def main():    prog = [        Stmt(1, "x = a + b", ["x"], ["a", "b"]),        Stmt(2, "if (x > 0)", [], ["x"]),        Stmt(3, "y = x * 2", ["y"], ["x"], ctrl=2),        Stmt(4, "print(y)", [], ["y"], ctrl=2),    ]    edges = all_deps(prog)    print("PDG 依赖边:", sorted(edges))    print("语句3的后向切片:", backward_slice(prog, edges, 3))    print("语句4的后向切片:", backward_slice(prog, edges, 4))  if __name__ == "__main__":    main()
目的：用 60 行代码实现一个微型 PDG 构建器——扫描定义-使用链得到数据依赖边、合并 if 守卫得到控制依赖边，再用反向邻接表完成后向切片，直观演示正文中的核心算法。
  1. self.defined = set(defined)把写入的变量存成集合，后续查「谁是 v 的写入者」只需 O(1)。
  2. for v in st.used:逐个检查本语句读取的变量，为它寻找最近的写入者。
  3. if v in last_def:撞见「上一个写 v 的语句」还没被覆盖，就说明依赖成立。
  4. deps.add((last_def[v], st.sid))记录一条「写入语句 → 读取语句」的流依赖边。
  5. deps.add((st.ctrl, st.sid))把 if 条件指向分支语句的控制依赖边也并入边集。
  6. rev.setdefault(dst, []).append(src)建反向邻接表，为「倒着走箭头」做准备。
  7. worklist.extend(rev.get(cur, []))从切片准则出发，沿反向依赖边一层层扩散收集。

常见误区

误区「控制流图（CFG）画的是执行顺序，程序依赖图（PDG）不就是把每个语句之间『有关联』的都连起来吗？我感觉 CFG 上多画几条箭头就是 PDG 了。」

正解PDG 不是 CFG 的简单加强版。CFG 保留语句的顺序与拓扑，而 PDG 只保留语义依赖关系（数据依赖 + 控制依赖），顺序信息完全分散到依赖边里——同一个 PDG 可以对应多种合法的执行顺序。这就像后厨地图只画「谁给谁供料、谁受谁开关控制」，不画「谁站在谁左边」。把两者混为一谈，做切片时会把不该包含的语句算进来。

为何常见：大多数教材先教 CFG，PDG 又画成带箭头的图，初学者自然以为 PDG 是 CFG 的「超集」。

误区「语句 A 写了变量 x，语句 B 读了变量 x，它们肯定有数据依赖！」

正解数据依赖还要求「中间没有被重新赋值」。如果 A: x=1, B: x=2, C: print(x)，那么 C 依赖的是 B 而不是 A，A 与 C 之间没有依赖边。这就像「第一锅汤倒掉了、第二锅汤才是给客人那锅」，第一锅汤和客人的菜没有关系。判断依赖要看最近的写入者（def-use 链），不是单纯看变量名。

为何常见：人对「名字相同」的直觉太强，容易忽略变量的值会被覆盖。

误区「只要写在 if 里面的代码，都一定和控制语句有控制依赖。」

正解控制依赖的定义更严格：只有当「某个分支被执行而另一个分支不执行，导致某语句要么执行要么不执行」时，该语句才控制依赖于这个 if。比如 if (x>0) { y=1; } z=y+1; 中，z=y+1 无论在哪个分支都会执行（它后支配两个分支出口），所以 z 不控制依赖于 if。真正的「开关」只作用于那些会被跳过或选中的语句。

为何常见：从语法嵌套上看「在 if 里面」，而忽略了「无论如何都会执行」的后支配情况。

误区「切片不就是把没用的行删掉嘛，编译器优化里也这么干。」

正解切片是有明确准则的：给定切片准则（某语句 + 一组变量），切片保留的是「会影响该语句在该变量上取值的全部语句」。它删除的语句不是因为「没用」，而是因为不影响切片准则所关心的行为。同一个程序，换一个切片准则，得到完全不同的切片。这跟死代码删除（dead code elimination）的目标和方法都不同。

为何常见：切片前后代码都变短了，看起来都像「删代码」，容易混淆概念。

误区「为了让 AI 更聪明地分析代码，PDG 当然是越精确越好，宁可慢一点也要全量构建。」

正解对百万行级别的大仓库，全量精确 PDG 的边数可到 O(n²)，构建时间和内存都无法承受。工业界的做法是权衡：用流不敏感或上下文不敏感的近似，或增量更新只对变更区域重建。精度 90% 但秒级完成，往往比精度 99% 但跑一小时更实用。理论最优和工程可用之间，必须做取舍。

为何常见：学术研究追求精确，初学者容易把「理论上更好」当成「工程上更好」。

面试题

Q1. 程序依赖图（PDG）中的两类依赖边是？

单选题 · easy

  • A.语法依赖边与语义依赖边
  • B.数据依赖边与控制依赖边← 正确答案
  • C.顺序依赖边与跳转依赖边
  • D.调用依赖边与返回依赖边

答案：B。PDG 融合数据依赖（谁给谁供料）和控制依赖（谁受谁开关控制），对应后厨地图里的「原料流动」和「条件闸门」。顺序不是一种独立的依赖边，它被编码进依赖关系中。

Q2. 对于语句 y = x + 1; 与 print(y);，后者对前者的依赖是？

单选题 · easy

  • A.反依赖（读后写）
  • B.输出依赖（写后写）
  • C.流依赖（写后读）← 正确答案
  • D.控制依赖（分支控制）

答案：C。第二个语句读取 y，而 y 是第一个语句写入的，写后读（RAW）构成流依赖，故称「真依赖」。反依赖是读后写，输出依赖是写后写，都不符合这里的读写顺序。

Q3. 关于控制依赖，下列说法正确的是？

单选题 · mid

  • A.凡是写在 if 语句块内的代码都依赖于该 if
  • B.语句 j 后支配 i 的所有后继即控制依赖
  • C.存在后继 p，j 后支配 p 且不后支配 i← 正确答案
  • D.循环中所有语句都控制依赖于其入口

答案：C。控制依赖的经典定义是「存在 i 的一个后继 p，j 后支配 p，但 j 不后支配 i 本身」。选项 A、D 把「语法上在块内或循环内」误当成了依赖关系；选项 B 的条件实际上意味着 j 后支配 i，构不成「开关」。

Q4. 程序切片通常以什么为起始点？

单选题 · mid

  • A.切片准则（语句加变量集）← 正确答案
  • B.函数入口语句（第一行）
  • C.程序出口语句（最后一行）
  • D.任意一条执行路径

答案：A。切片准则 <S, V> 指定「我们关心哪个语句在哪些变量上的取值」。后向切片从这个准则出发，沿依赖边反向收集所有可能影响它的语句。没有准则的「切片」无从谈起。

Q5. 以下哪一项是影响分析最直接的实现手段？

单选题 · hard

  • A.后向切片，从变更语句回推
  • B.前向切片，沿依赖边前推← 正确答案
  • C.死代码删除，删除变更语句
  • D.只计算到达定义数据流

答案：B。变更影响分析关心「改了这一处，还有哪些语句的结果会变」，这正是前向切片：从变更点出发沿依赖边扩散。后向切片用于寻找根源，方向正好相反；死代码删除与影响分析目标无关。

Q6. 数据依赖边存在的必要条件是？

单选题 · mid

  • A.存在未被覆盖的定义-使用链← 正确答案
  • B.两语句的物理距离足够近
  • C.两语句使用相同类型数据
  • D.两语句属于同一个函数

答案：A。变量 v 在语句 i 被定义、在语句 j 被使用，且 i 到 j 的路径上 v 没有被重新定义，才能连出数据依赖边。若中间被覆盖，最近的写入者才是依赖对象——像后厨里被倒掉的第一锅汤。

Q7. PDG 构建中，控制依赖边通常通过哪种结构计算？

单选题 · hard

  • A.借助语法树的前序遍历
  • B.后支配树加分支后继分析← 正确答案
  • C.依赖符号表的哈希冲突
  • D.依赖正则表达式匹配

答案：B。控制依赖定义建立在后支配关系之上。先由 CFG 求后支配树，再对每个节点的每个后继检查「子节点是否后支配该后继但不后支配该节点」，即可生成控制依赖边。

Q8. 判断语句 j 对语句 i 有流依赖，需要满足哪些条件？

多选题 · easy

  • A.i 定义了变量 v← 正确答案
  • B.j 使用了变量 v← 正确答案
  • C.路径中间没有重新赋值← 正确答案
  • D.i 和 j 之间没有控制依赖

答案：ABC。流依赖 = 写后读（RAW），三个条件缺一不可：有定义、有使用、且中间无覆盖。是否同时存在控制依赖并不影响流依赖的存在，D 是干扰项。

Q9. 下列哪些技术直接建立在程序依赖图之上？

多选题 · mid

  • A.程序切片后向与前向← 正确答案
  • B.变更影响分析模块← 正确答案
  • C.污点分析追踪数据传播← 正确答案
  • D.编译器的词法分析器

答案：ABC。切片是 PDG 上的可达性计算，影响分析是前向切片，污点分析本质是沿数据依赖边追踪传播。词法分析只做字符切分，与依赖图无关。

Q10. 大规模程序构建 PDG 时，工程上常采用的取舍包括？

多选题 · hard

  • A.流不敏感近似牺牲精度← 正确答案
  • B.增量更新只重建变更区域← 正确答案
  • C.压缩合并冗余依赖边← 正确答案
  • D.完全放弃控制依赖边

答案：ABC。为控制 O(n²) 的边膨胀，工业界常用流不敏感近似、增量重建、边压缩等手段，在精度与成本间权衡。但控制依赖是 PDG 的半边天，完全放弃会让切片失真，不是常规取舍，D 错误。