如何在控制流图中包含子程序调用？

Question

我想到了 control flow graph；它涉及的节点是基本块（总是发生的操作序列），由表示跳跃的边连接。

但是你如何表示子程序调用？

如果我有两个这样的函数:

int tweedledee(void)
{
    int x = 16;
    return x + do_something();
}

int tweedledum(int n)
{
    if (n < 0)
       return n;
    else
       return n + do_something();
}

两个函数都调用 do_something()，然后我需要一种方法允许从 tweedledee 中的块跳转到 do_something，然后再跳回到 tweedledee ，以及从 tweedledum 中的块跳转到 do_something 然后返回到 tweedledum，但是从来没有从 tweedledee 跳到 do_something 然后到 tweedledum。（或者 tweedledum → do_something → tweedledee）所以看起来普通的有向图不足以定义这些关系……也许我遗漏了什么。

Answer 1

程序使 CFG 和静态分析通常非常复杂。在控制流图中有不同的方法来表示例程调用。

第一个也是常见的解决方案是为每个例程创建一个CFG，并将"call nodes"（例如tweedledee中对应"CALL do_something()"的基本块）拆分为两个节点，实际调用块 C 和块 R 来写入 return 值。

在C和被调用例程的起始块之间插入一条边（通常是特殊类型），在被调用例程的结束块和R之间插入另一条边。一个简单的例子：

void foo() { int x = bar(); }
int bar() { return 1; }

可能会转换为：

[init::foo] ==> [CALL bar()]  [x = RETVAL(bar())] ==> [end::foo]
                     ||            /\
                     \/            ||
                [init::bar] ==> [ret = 1 (end::bar)]

如果有另一个对 bar() 的调用，例如来自例程

void foo2() { int y = bar(); }

那么下图可能就是结果：

 [init::foo] ==> [CALL bar()]  [x = RETVAL(bar())] ==> [end::foo]
                     ||            /\
                     \/            ||
                [init::bar] ==> [ret = 1 (end::bar)]
                     /\            ||
                     ||            \/
 [init::foo2]==> [CALL bar()]  [x = RETVAL(bar())] ==> [end::foo2]

这里的问题：这个图中现在有路径（例如 init::foo ==> CALL bar() ==> init::bar ==> ret = 1 ==> x = RETVAL (bar()) ==> end::foo2) 这在程序中没有意义。这就是您想知道 "plain directed graph" 是否足够的意思。这个问题有不同的方法，例如：为例程的每次调用制作例程的副本（这里是栏）。这只有在没有真正的递归的情况下才有用，而且通常很昂贵。对于静态分析，通过仅使用固定数量的此类副本来 "overapproximate" 路径数量通常很有用。

幻灯片Interprocedural Analysis Lecture Notes (Stephen Chong) 似乎是一个很好的介绍。也有很多关于构建此类图的好书，例如Principles of Program Analysis 尼尔森等人

如何在控制流图中包含子程序调用？

How do you include subroutine calls in a control flow graph?

static-analysis

control-flow-graph