概述CGSCC代表Call-Graph Strongly Connected Component即调用图的强连通分量这是一个在编译器优化(特别是过程间优化)中非常重要的概念Call Graph (调用图)这是一个表示程序中函数/过程之间调用关系的有向图节点(Node) 通常代表程序中的一个函数(Function) 或过程 (Procedure)有向边(Directed Edge): 如果函数 A 调用了 函数 B 则存在一条从节点 A 指向 节点 B 的边Strongly Connected Component - SCC (强连通分量)这是图论中的一个概念在一个有向图中一个强连通分量是指一个最大的子图(即一组节点及其之间的边) 其中任意两个节点都是互相可达的。也就是说对于SCC中的任意两个节点 u 和 v都存在一条 从 u 到 v 的路径 也存在一条从 v 到 u 的路径一个图可以被分解成一个 或 多个 SCC 。 不属于同一个SCC 的节点之间不一定双向可达的Call-Graph SCC(CGSCC)将SCC 的概念应用到程序的 Call graph,就得到了CGSCC一个CGSCC 是调用图中的一个强连通分量它包含了一组函数这组函数之间通过调用关系形成了一个循环在 CGSCC 内部函数之间存在相互递归或循环调用的关系无论是直接循环 A - B - A 还是更大的间接循环 A - B - C - A。CGSCC 外部的函数调用关系不会形成这样的循环为什么 CGSCC 在编译优化中很重要**优化单元 **许多重要的过程间优化Interprocedural Optimization, IPO是以 CGSCC 为单位进行的。编译器如 LLVM有一个专门的优化阶段叫 CGSCCPassManager处理递归/循环调用优化器在处理递归函数或一组相互递归的函数时需要将它们视为一个整体单元来分析和优化因为它们的执行是相互依赖的。CGSCC 自然地将这些相关的函数分组在一起优化顺序编译器需要按照特定的顺序遍历和优化函数。CGSCC 的拓扑结构SCC 通常按照拓扑序处理即先处理没有入边的 SCC再处理依赖它们的 SCC为这种遍历提供了一个合理的、能够处理递归依赖的顺序框架内联决策函数内联Function Inlining决策有时会考虑 CGSCC 边界。在 CGSCC 内部进行内联可能会解开递归或循环调用为更激进的优化如将递归转换为循环创造机会简单例子假设一个程序有以下函数main() 调用 foo() foo() 调用 bar() 和 baz() bar() 调用 baz() baz() 调用 bar()调用图main - foo foo - bar, baz bar - baz baz - bar (形成一个 bar - baz 的循环)分析SCC:bar 和 baz 互相调用形成一个强连通分量 {bar, baz}main 和 foo 本身没有形成循环 (foo 调用 bar/baz , 但是 bar/baz 不调用 foo/main)。 main 调用 foo但foo不调用 main它们各自属于自己的SCC (main 和 foo) 或者如果 foo 只被 main调用且不形成 其他循环{main, foo} 也可能被视为一个SCC因此这个调用图的CGSCC有:CGSCC1: {bar, baz}CGSCC2: {foo}CGSCC3: {main}编译器在优化时可能会先独立处理 CGSCC1 ({bar, baz})因为它们内部有循环调用依赖然后再处理 CGSCC2 ({foo})最后处理 CGSCC3 ({main})。在处理 foo 时它知道调用 bar 或 baz 是调用到另一个 SCC (CGSCC1)