LLVM/Legacy CallGraphSCCPass

按强连通分量组织递归调用图优化

LLVM 的 legacy 调用图 pass 管理器使用 Tarjan SCC 迭代器，将相互递归的函数作为一组，并按被调用方优先的顺序处理分组。

llvmorg-19.1.0图处理与编译核验 2026-10-09

工程问题#

调用图中可能存在直接或间接递归，无法把每个函数单独排成无环调用顺序；跨函数优化需要一个能保留递归关系的处理单位。

实际实现#

SCC 迭代器用显式 DFS 栈记录探索进度，维护最小访问编号；找到分量根时弹出成员形成 SCC。CGPassManager 消费这些分量，对同一分量内的函数执行相应 passes，并在去虚化取得进展时允许有限次重访。

处理流程#

从调用图入口开展 DFS，记录访问编号和可达的最小编号
在分量根处从成员栈弹出完整 SCC
按 SCC DAG 的逆拓扑顺序遍历分组
对当前分量执行分析与变换，按条件有限重访

源码片段#

固定版本 · 原文摘录

llvm/lib/Analysis/CallGraphSCCPass.cppllvmorg-19.1.0 · L501–L514

查看原文件

501bool CGPassManager::runOnModule(Module &M) {502  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();503  bool Changed = doInitialization(CG);504505  // Walk the callgraph in bottom-up SCC order.506  scc_iterator<CallGraph*> CGI = scc_begin(&CG);507508  CallGraphSCC CurSCC(CG, &CGI);509  while (!CGI.isAtEnd()) {510    // Copy the current SCC and increment past it so that the pass can hack511    // on the SCC if it wants to without invalidating our iterator.512    const std::vector<CallGraphNode *> &NodeVec = *CGI;513    CurSCC.initialize(NodeVec);514    ++CGI;

CGPassManager::runOnModule

管理器实际从调用图建立 SCC 迭代器，取出当前分量并复制到 CurSCC，再继续遍历；这说明 SCC 算法在真实优化流水线中的入口。

CPPApache-2.0 WITH LLVM-exception

llvm/include/llvm/ADT/SCCIterator.hllvmorg-19.1.0 · L203–L215

查看原文件

203    if (minVisitNum != nodeVisitNumbers[visitingN])204      continue;205206    // A full SCC is on the SCCNodeStack!  It includes all nodes below207    // visitingN on the stack.  Copy those nodes to CurrentSCC,208    // reset their minVisit values, and return (this suspends209    // the DFS traversal till the next ++).210    do {211      CurrentSCC.push_back(SCCNodeStack.back());212      SCCNodeStack.pop_back();213      nodeVisitNumbers[CurrentSCC.back()] = ~0U;214    } while (CurrentSCC.back() != visitingN);215    return;

scc_iterator::GetNextSCC

当最小可达访问编号等于当前节点编号时，找到 SCC 根；从成员栈弹出节点直到该根，并把完成节点标为已离开待定分量。

CPPApache-2.0 WITH LLVM-exception

分别给出工程调用点与 Tarjan 的分量提取逻辑；访问编号传播和 DFS 推进位于 SCCIterator.h 的相邻代码中。

收益与取舍#

工程分析

带来的收益

把相互递归函数放在同一分析单位中
被调用方分量先于调用方分量处理，为自底向上的分析与优化提供顺序

付出的代价

一次静态图上的 Tarjan 遍历为 O(V+E)，图变换后的维护和重复优化另计
调用图被修改时需遵守迭代器和 pass 管理器的更新规则

可比较的选择

仅做普通拓扑排序原始调用图可能有环，须先压缩 SCC 或采用其他能处理环的分析方法。

版本与适用范围#

对应 LLVM llvmorg-19.1.0 中 legacy pass manager 的 CallGraphSCCPass 路径；新 pass manager 的 LazyCallGraph / CGSCC 是另一套维护机制，不能以此片段代表其实现。

参考来源#

源码、官方文档与原始论文

llvm · CGPassManager::runOnModule

llvm/lib/Analysis/CallGraphSCCPass.cpp · CGPassManager::runOnModule

源码llvmorg-19.1.0

llvm · scc_iterator::GetNextSCC

llvm/include/llvm/ADT/SCCIterator.h · scc_iterator::GetNextSCC