Program Dependence Graph

释义 Definition

程序依赖图（PDG）：一种用于表示程序中各语句/操作之间依赖关系的图结构，主要包含数据依赖（data dependence）与控制依赖（control dependence）。常用于程序切片（program slicing）、编译器优化、静态分析与安全审计等场景。

发音 Pronunciation (IPA)

/ˈproʊɡræm dɪˈpɛndəns ɡræf/

例句 Examples

A program dependence graph helps visualize how statements affect each other.
程序依赖图有助于可视化各条语句如何相互影响。

Using a program dependence graph, the analyzer computed a backward slice to trace the origin of a vulnerability across multiple functions.
分析器利用程序依赖图计算后向切片，以跨越多个函数追踪漏洞的来源。

词源 Etymology

该术语由 program（程序）、dependence（依赖） 与 graph（图） 组合而成，字面意思是“描述程序依赖关系的图”。在编译与程序分析领域中，PDG 作为一种经典中间表示被系统化提出并推广，尤其与“程序切片”方法的发展密切相关。

相关词 Related Words

• Program Slicing
• Data Dependence
• Control Dependence
• Dependence Graph
• Control Flow Graph
• Data Flow Analysis
• Static Analysis
• Compiler Optimization
• SSA Form

文献作品 Notable Works

• The Program Dependence Graph and Its Use in Optimization（Ferrante, Ottenstein, Warren，ACM TOPLAS，1987）
• Compilers: Principles, Techniques, and Tools（Aho, Sethi, Ullman；常称“龙书”，相关章节涉及依赖与程序分析思想）
• Advanced Compiler Design and Implementation（Steven Muchnick；涵盖依赖分析与优化相关内容）