LLVM调用图DFS遍历叶节点出现null节点及路径缺失问题

问题复现代码 #

尝试以深度优先搜索（DFS）方式遍历LLVM中的CallGraph（调用图），简化实现代码如下：

CallGraph CG = CallGraph(M); 
 for (auto IT = df_begin(&CG), EI = df_end(&CG); IT != EI; IT++) {
     if(Function *F = IT->getFunction()){
         dbgs() << "fun name " << F->getName() << "\n";
     }else{
         dbgs() << "fun address " << IT->getFunction() << "\n";
     }
     dbgs() << "distance " << IT.getPathLength() << "\n"
 }

运行代码后控制台打印结果如下：

fun address 0x0 
distance 1 
fun name s2n_alpn_send 
distance 2 
fun name s2n_calculate_stacktrace 
distance 3 
fun address 0x0 
distance 4 
fun name strlen 
distance 3 
fun name s2n_stuffer_write_uint16 
distance 3 

待解决疑问 #

• 为何DFS遍历会到达距离为4的0x0地址，调用图的叶位置为什么会存在null空节点？
• 原本需求是通过DFS遍历调用图，收集同一路径下的节点，以此统计单个函数调用的所有函数，但将遍历结果和CG.dump()的输出对比后，发现存在部分路径、节点缺失的情况，该问题的成因是什么？

空节点（0x0地址）出现原因 #

LLVM CallGraph中getFunction()返回空指针的节点是设计预留的特殊节点，对应CallsExternalNode，不属于异常情况：

• 遍历输出中距离为1的0x0节点是CallGraph的全局虚拟根节点，本身不对应任何模块内的实际函数，是整个调用图遍历的默认起点。
• 距离为4的0x0节点是s2n_calculate_stacktrace的调用边指向的外部调用节点：只要函数存在当前编译单元（Module）内无法解析到具体定义的调用——包括调用了未在当前模块实现的库函数、静态分析无法确定目标的间接调用、仅声明未定义的函数——这类调用的目标都会被统一指向这个全局空节点。
• 该节点本身没有任何出边，DFS遍历走到该节点就会触发回溯，因此会出现在路径末端（叶位置），路径长度比调用它的函数多1。

遍历出现节点、路径缺失的原因 #

直接使用LLVM自带的df_begin/df_end迭代器做DFS遍历出现内容缺失，是迭代器默认行为和CallGraph::dump()逻辑不一致导致的：

• 默认DFS迭代器开启了全局节点去重：任意节点（包括上述空外部节点）只要被访问过一次，后续其他路径再遇到指向该节点的边时，迭代器会直接跳过，不会重复遍历对应路径。比如示例中s2n_calculate_stacktrace已经访问过一次空节点，后续其他函数指向空节点的外部调用边都会被跳过，对应路径不会出现在遍历结果中。
• 默认DFS从全局虚拟根出发，仅遍历根可达的节点：如果模块内存在孤立函数（比如定义后从未被直接调用的静态函数、仅被间接调用但CallGraph未识别到调用边的函数），这类节点不会被根出发的DFS遍历到，但CallGraph::dump()会输出调用图中存储的所有节点，二者对比就会出现节点缺失。

如果需求是统计单个函数的所有被调函数，不要直接从全局根做DFS遍历，应当以目标函数对应的CallGraphNode作为遍历起点，按需调整遍历的去重逻辑，不要直接依赖默认df迭代器的全局去重行为。

内容的提问来源于stack exchange，提问作者Rubujubi