Interference Graph

释义 Definition

干涉图 / 冲突图：在编译器的寄存器分配中常用的一种图结构。图中的每个节点通常表示一个变量（更准确地说是“活跃区间/临时变量”），如果两个变量在程序的某些点上同时活跃（live）、不能分配到同一个寄存器，就在它们之间连一条边，表示它们彼此“冲突/干涉”。

发音 Pronunciation (IPA)

/ˌɪntərˈfɪrəns ɡræf/

例句 Examples

An interference graph shows which variables cannot share a register.
干涉图用来表示哪些变量不能共用同一个寄存器。

We build the interference graph from liveness analysis, then color it to assign registers while minimizing spills.
我们通过活跃性分析构建干涉图，再对其进行图着色以分配寄存器，并尽量减少溢出到内存（spill）。

词源 Etymology

interference 源自拉丁语词根 *inter-*（在……之间）+ ferre（携带、带来），在技术语境中常指“相互妨碍/冲突”；graph 源自希腊语 *graph-*（书写、描绘），在数学与计算机科学中指“图（由点和边构成的结构）”。合起来 interference graph 直译为“表示相互冲突关系的图”。

相关词 Related Words

• Register Allocation
• Liveness Analysis
• Graph Coloring
• Spill
• Live Range
• Control Flow Graph
• SSA
• Chaitin Algorithm

文学与作品 Literary Works

• Compilers: Principles, Techniques, and Tools（Aho, Lam, Sethi, Ullman，“龙书”）：在寄存器分配章节讨论干涉图与图着色方法。
• Modern Compiler Implementation（Andrew W. Appel）：以干涉图为核心结构讲解基于图着色的寄存器分配。
• Chaitin 等人的经典论文（如关于 register allocation via graph coloring 的研究）：提出并推广了用干涉图建模寄存器冲突关系的思路。