3

我正在编写一些代码来为特定的中间表示生成调用图，而无需通过静态扫描 IR 代码来执行它。IR 代码本身并不太复杂，我对函数调用序列的外观有很好的理解，所以我需要做的就是跟踪调用。我目前正在以明显的方式进行操作：

  • 跟踪我们的位置
  • 如果我们遇到一个函数调用，分支到那个位置，执行并返回
  • 分支在调用者和被调用者之间设置边缘

我对自己的进展感到满意，但我想确保我不会在这里重新发明轮子并面对极端情况。我想知道是否有任何公认的好的算法（和/或设计模式）可以有效地做到这一点？

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

4

2 回答 2

4

从学术的角度来看，这里有一些考虑：

  • 你在乎保守/正确吗？例如，假设您正在分析的代码包含通过函数指针的调用。如果您只是生成文档，则无需处理此问题。如果您正在执行可能出错的代码优化，您将需要假设“通过指针调用”意味着“可能是任何东西”。

  • 当心异常的执行路径。您的 IR 可能会或可能不会将其从您那里抽象出来，但请记住，许多操作可能会引发语言级异常以及硬件中断。同样，这取决于您以后要对调用图做什么。

  • 考虑如何处理循环（例如递归、相互递归）。这可能会影响您以后编写用于遍历图形的代码的方式（即，它们将需要某种“已访问”集以避免永远遍历循环）。

干杯。

3 月 6 日更新：

基于添加到原始帖子的额外信息：

  • 小心虚方法调用。请记住，通常不知道将执行哪个方法。您可能不得不假设调用将转到特定类的任何子类。标准示例有点像这样：假设你有一个ArrayList<A>，并且你有class B extends A. 基于随机数生成器，您将添加A和的实例B到列表中。现在您调用列表中x.foo()的所有内容x，其中foo()一个虚拟方法 inA带有一个覆盖 in B。因此，仅通过查看源代码，无法知道循环是否在运行时调用A.foo、B.foo或两者。
于 2011-03-06T06:18:41.293 回答
2

我不知道算法，但pycallgraph做得不错。值得检查它的来源。它不长，应该适合检查现有的设计模式。

于 2011-03-06T05:30:21.020 回答