将控制流图扁平化为结构化代码
我想将控制流图（CFG）渲染为高级代码。通常这很容易；遍历树，依次渲染每个基本块，然后用 goto 将它们粘合在一起。
不幸的是，现在 goto 已经过时了，大多数现代语言都不支持它们。因此，我需要某种方法将基本块粘合在一起，仅使用语言中存在的控制流语句：for、while、do。 ..while、if、break 和 Continue。 （我不愿意考虑使用变量构建状态机。）
看来，虽然有算法可以做到这一点，但它们并非在所有情况下都有效。也就是说，仅使用上述有限的一组控制流结构就可以构造出无法扁平化为结构化代码的CFG。
这对我来说直观上似乎是显而易见的，但我无法证明这一点（并且我发现的算法的文档没有详细介绍）。我还没有找到一个不能像这样展平的 CFG 的例子。
我想确切地知道这是否可能。
选项 (a)：有没有人有一个不能按上述方式展平的 CFG 的示例？ （这会告诉我这是不可能的。）
选项（b）：是否有人有证据证明CFG可以如上所述被展平？ （这将告诉我这是可能的。）也非常需要一种算法来做到这一点，因为我必须让它工作......
I would like to render a control flow graph (CFG) out to high-level code. Normally this is very easy; walk the tree, render each basic block in turn, glue it all together with gotos.
Unfortunately, gotos are out of fashion these days, and most modern languages don't support them. So I need some way to glue my basic blocks together using only those control flow statements that exist in the language: for, while, do...while, if, break and continue. (I'm not willing to consider building a state machine using variables.)
It would appear that while there are algorithms to do this, they will not work in every case. That is, it's possible to construct a CFG that cannot be flattened to structured code using only the above limited set of control flow structures.
This seems intuitively obvious to me, but I can't prove it (and the documentation for the algorithms I've found don't go into more detail). And I haven't been able to find an example of a CFG which can't be flattened like this.
I would like to know, definitively, if this is possible or not.
Option (a): does anyone have a example of a CFG which cannot be flattened as described above? (Which will tell me that it's not possible.)
Option (b): does anyone have a proof that CFGs can be flattened as described above? (Which will tell me that it is possible.) An algorithm to do it would be highly desirable, too, as I would then have to make it work...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
尽管这个问题很久以前就被问过，但这实际上似乎是可能的。 Mozilla 在将 LLVM 编译为 JS（或现在的 WebAssembly）时也遇到了类似的问题。 JS 和 WebAssembly 只允许结构化控制流，而 LLVM 允许任意控制流。
他们写了一篇关于此的论文，该论文也用于 WebAssembly：
although this question was asked a long time ago this actually seems to be possible. Mozilla had a similar problem when compiling LLVM to JS (or now WebAssembly). JS and WebAssembly only allow structured control flow, while LLVM allows arbitrary control flow.
They'v written a paper about this which is also used for WebAssembly:
我想我已经有结果了。
答案似乎是：不可能。这是来自朱塞佩·雅科皮尼 (Giuseppe Jacopini) 于 1966 年发表的一篇名为“只有两种形成规则的流程图、图灵机和语言”的论文中的Communications of the ACM，第 9 卷，第 366 至 371 页。 CiteSeer 链接。（有趣的是，我发现引用了摘自高德纳 (Knuth) 的开创性著作（从我的角度来看，这非常烦人）转到被认为有害的声明。）
令人失望的是，他们没有证据，说他们找不到。
好消息是，该论文确实描述了一种策略，以高效的方式仅使用有限的控制流机制，使用尽可能少的状态，将任意 CFG 转换为 CFG。这篇论文相当困难，但看起来很有希望。
I think I have a result.
The answer seems to be: it is not possible. This is from Communications of the ACM, volume 9, pages 366 to 371 in a paper from 1966 called "Flow Diagrams, Turing Machines and Languages with only Two Formation Rules" by Giuseppe Jacopini. CiteSeer link. (Which, amusingly, I found referenced from Knuth's seminal (and, from my point of view, incredibly annoying) Go To Statement Considered Harmful.)
Disappointingly, they don't have a proof, saying they were unable to find one.
The good news is that the paper does describe a strategy for converting an arbitrary CFG into a CFG using only limited control-flow mechanisms in an efficient fashion, using as little state as possible. The paper is pretty hard going but it looks promising.
如果控制流图不是可简化，那么它就不能像您所描述的那样“扁平化”为结构化控制流。任何不可约 CFG 都包含以下内容的某些变体
这里
y和z都是相互进入的循环，这是不可能创建的正常的结构化控制流程。但是，大多数控制流图都可以进行转换。您可以使用辅助数据结构 Dominator Tree 来执行此操作。例如，请参阅 Haskell 中的此实现。
If the Control Flow Graph is not reducible, then it cannot be "flattened" to structured control flow as you describe. Any irreducable CFG contains some variant of the following
Here both
yandzare loops that enter each other, which would be impossible to create with normal structured control flow.However, most Control Flow Graphs can be converted. You can use the auxiliary data structure the Dominator Tree to do this. See this implementation in Haskell for example.
上图虽然不可简化，但可以通过添加辅助变量（例如“jump”）的结构化控制流来实现。我们在 x 上方添加一个块 w，它设置 Jump=false 并转到 x。然后我们创建一个新的块 v，设置 Jump=true，并将从 x 出来的右边缘指向 v 而不是 z。然后我们将 v、x 和 z 定向到一个新块 u，条件是 if Jump=true, z else y。然后添加 z 的第一条语句来设置 Jump = false。这添加了最少的代码，没有重复，并将该结构变成具有单个条目的循环。
减少不可约控制流：
The above graph, while irreducible, can be implemented with structured control flow with the addition of a helper variable, say "jump". We add a block w above x which sets jump=false and goes to x. Then we create a new block v that sets jump=true, and direct the right edge coming out of x to v instead of to z. Then we direct v, x, and z to a new block u, with a condition if jump=true, z else y. Then the first statement of z added to set jump = false. This adds a minimum of code with no duplication and turns this structure into a loop with a single entry.
Reducing irreducible control flow: