如何基于LLVM从使用位置查找可达定义位置？能否用支配树？

核心解法：构建使用-定义链（UD Chain） #

你要找的是所有能到达目标使用点的定义，这对应编译原理中的「使用-定义链（Use-Definition Chain, UD链）」。LLVM可以通过内置工具或手动数据流分析实现，具体如下：

1. 利用LLVM内置分析工具 #

LLVM提供了现成的分析组件来处理这类数据流问题：

• ReachingDefinitionsAnalysis（LLVM 12+版本）：直接可以获取某一位置的到达定义集合，调用对应API就能拿到所有能到达该使用点的定义指令。
• 结合Value用户链与CFG遍历：如果需要更灵活的实现，可以从使用点对应的Value出发，配合控制流图逆向遍历，但要注意过滤被覆盖的定义——同一路径上后续的定义会覆盖更早的定义。

2. 手动实现逆向CFG遍历 #

如果需要自己实现逻辑，步骤大致如下：

• 从使用点d所在的基本块开始，标记已遍历的基本块避免循环遍历。
• 对当前基本块，从后往前扫描指令：如果找到目标值的定义，将其加入结果集，同时停止该块内的向前扫描（该定义会覆盖块内更早的定义）。
• 递归遍历当前块的所有前驱基本块，重复上述过程。

3. 支配树能不能解决这个问题？ #

不能直接用支配树解决。原因很明确：
支配树的作用是找出所有从入口到目标节点的必经路径上的节点，但到达使用点的定义不一定都在必经路径上。比如你的例子中，c所在的块并不支配d（存在a→b→d的路径不经过c），但c的定义仍然能到达d。支配树更适合找被某个定义支配的使用点（即定义-使用链），而非反过来的使用-定义链。

特殊情况处理 #

• Phi节点：如果使用点在含Phi节点的块中，每个Phi的输入对应前驱块的定义，需要分别追踪每个前驱路径的数据流。
• 函数调用：如果涉及跨函数的参数传递，需要结合CallGraph和AliasAnalysis分析参数的数据流。
• 循环：借助LoopInfo识别循环结构，避免无限遍历，同时处理循环内的定义覆盖。

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