生成调用图的好算法？

Question

我正在编写一些代码来生成特定中间表示的调用图，而不通过静态扫描IR代码来执行它。IR代码本身并不太复杂，我很清楚函数调用序列是什么样的，所以我需要做的就是跟踪调用。我目前的做法很明显：

• 跟踪我们在哪里
• 如果我们遇到一个函数调用，分支到那个位置，执行并返回。
• 而分支则在呼叫者和被叫者之间放置一个边缘。

我对我取得的进展感到满意，但我想确保我不会在这里和面对角落的情况下重新发明轮子。我想知道是否有任何公认的好算法(和/或设计模式)能够有效地做到这一点？

更新： IR代码是从一种自制的Java语言中反汇编的字节码，看起来像茉莉花规格。

Answer 1

从学术角度来看，以下是一些考虑因素：

• 你关心保守/正确吗？例如，假设您分析的代码包含一个通过函数指针进行的调用。如果您只是生成文档，那么就没有必要处理这个问题。如果您正在进行可能出错的代码优化，则需要假设“通过指针调用”意味着“可能是任何事情。”
• 小心异常的执行路径。您的IR可能会也可能不会将其抽象出来，但请记住，许多操作都会抛出语言级别的异常以及硬件中断。同样，这取决于您以后想要对调用图做什么。
• 考虑如何处理循环(例如递归、互递归)。这可能会影响您以后编写遍历图的代码的方式(也就是说，它们将需要某种类型的“访问”集，以避免永远遍历周期)。

干杯。

更新3月6日

根据添加到原始帖子中的额外信息：

• 注意虚拟方法调用。请记住，一般来说，不知道将执行哪种方法。您可能必须假设调用将转到特定类的任何子类。标准示例有点像这样:假设您有一个ArrayList<A>，而您有一个class B extends A。基于随机数生成器，您将向列表中添加A和B实例。现在为列表中的所有x调用x，其中foo()是A中的一个虚拟方法，在B中有一个覆盖。因此，只要查看源代码，就无法知道循环是在运行时调用A.foo、B.foo还是同时调用两者。