生成调用图的好算法是什么？

Question

3

我正在编写一些代码，用于生成特定中间表示的调用图，而无需通过静态扫描IR代码来执行它。 IR代码本身并不太复杂，我对函数调用序列的样子有很好的理解，所以我只需要跟踪调用。我目前正在按照显而易见的方式进行：

我对我所得到的结果感到满意，但我想确保我没有重复造轮子，并且面对角落情况。我想知道是否有任何已接受的良好算法（和/或设计模式），可以高效地执行此操作？

更新： IR代码是自制Java类语言的字节码反汇编，并且看起来像Jasmine规范。

- Legend

你能多说一些关于你想要分析的IR吗？它是什么样子的，它的特征与绑定和函数调用有关吗？ - phooji

@phooji：当然。这是由JReveal Jasmine反汇编器生成的字节码IR。它似乎没有描述任何关于重新绑定的内容，但如果我发现任何新信息，我会回复您的。但我可以肯定地说，因为它正在反汇编Java程序，所以没有指针。 - Legend

我已经快速浏览了Jasmine字节码规范。唯一立即引起我的注意的是虚拟方法调用; 请参见下面更新的答案。 - phooji

@phooji：感谢您的时间。我刚刚接受了您的答案并添加了一条评论。 - Legend

2个回答

2

我不知道这个算法，但是pycallgraph做得很好。值得查看它的源代码。它并不长，适合用于检查现有的设计模式。

- Russ

+1 谢谢。很抱歉没有说明清楚。我更新了我的问题。我遇到了pycallgraph，但我不想执行代码，而是想通过解析我的中间代码来生成调用图。 - Legend

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phooji · Accepted Answer

从学术角度考虑，以下是一些注意事项：

您是否关心保守/正确？例如，假设您正在分析的代码包含通过函数指针调用。如果您只是生成文档，则不需要处理此问题。如果您正在进行可能失败的代码优化，则需要假定“通过指针调用”表示“可以是任何内容”。
小心异常执行路径。您的IR可能会将其抽象化，也可能不会，但请记住，许多操作都可以引发语言级别的异常以及硬件中断。同样，这取决于您稍后要对调用图做什么。
考虑如何处理循环（例如递归、相互递归）。这可能会影响您稍后编写用于遍历图形的代码方式（即，它们需要某种“访问”集来避免永远遍历循环）。

干杯。

3月6日更新：

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

小心虚方法调用。请记住，一般情况下无法知道将执行哪个方法。您可能需要假定调用将转到特定类的任何子类。标准示例大致如下：假设您有一个ArrayList<A>，并且您有class B extends A。基于随机数生成器，您将向列表中添加A和B的实例。现在，您为列表中的所有x调用x.foo()，其中foo()是A中具有B覆盖的虚拟方法。因此，仅通过查看源代码，无法知道循环在运行时调用A.foo、B.foo还是两者都调用。