1

我得到了控制流图的想法；它涉及的节点是基本块（总是发生的操作序列），由代表跳跃的边连接。

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

如果我有两个这样的功能：

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）所以看起来一个普通的有向图不足以定义这些关系......也许我错过了一些东西。

4

1 回答 1

2

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

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

在 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) 这在程序中没有意义。这就是您想知道“普通有向图”是否足够的意思。这个问题有不同的方法，例如： 为每次调用复制一个例程（这里是条形图）。这仅在没有真正递归的情况下才有帮助，并且通常很昂贵。对于静态分析，通过仅使用固定数量的此类副本来“过度近似”路径数量通常很有用。

幻灯片Interprocedural Analysis Lecture Notes (Stephen Chong)似乎是一个很好的介绍。还有一些关于构建此类图的很好的书籍，例如Nielson 等人的《程序分析原理》 。

于 2016-01-21T21:00:56.840 回答