问题标签 [ssa]

我正在为堆栈机器（特别是CIL）开发编译器，并且我已将代码解析为基本块图。从这里开始，我希望将SSA应用于这些方法，但进展并不顺利。我的第一次尝试（在使用平面列表而不是图表时）是迭代代码并保留一堆 SSA id（即，用于分配目标），当我产生分配时推送它们，当我弹出它们时他们被使用了。这适用于单个基本块，但我根本无法弄清楚如何处理生成 Φ 函数。

我一直在折腾的想法是将堆栈位置附加到 SSA id，然后查看代码路径收敛时堆栈上仍然存在的内容，但这似乎不是做事的正确方式 (TM)。

是否有一种简单的算法来跟踪跨多个代码路径的堆栈操作并确定它们收敛时的冲突？

我听到的反对函数式语言的一个论点是，单一赋值编码太难了，或者至少比“普通”编程困难得多。

但是通过我的代码，我意识到我真的没有很多（任何？）使用模式，如果你用一种相当现代的语言编写的话，这些模式不能用单一的赋值形式来编写。

那么在一次调用范围内变化的变量的用例是什么？请记住，在这种情况下，循环索引、参数和其他在调用之间变化的范围绑定值不是多重赋值（除非您出于某种原因必须在正文中更改它们），并假设您正在编写一些东西远远高于汇编语言级别，您可以在其中编写诸如

或（如果未提供总和）

和

或者

当您需要时，并有列表推导、地图/收集等可用。

您是否发现在这样的环境中您仍然想要/需要可变变量，如果是，那是为了什么？

澄清一下，我不是要求背诵对 SSA 表格的反对意见，而是要求这些反对意见适用的具体示例。我正在寻找带有可变变量的清晰简洁的代码，没有它们就无法编写。

到目前为止我最喜欢的例子（以及我期望的最好的反对意见）：

1. Paul Johnson 的Fisher-Yates 算法答案，当您包含大 O 约束时，它非常强大。但是，正如 catulahoops 指出的那样，big-O 问题与 SSA 问题无关，而是与可变数据类型有关，并且将这些放在一边，算法可以在 SSA 中相当清楚地编写：

   /li>

2. jpalecek 的多边形面积示例：

   这可能仍然写成：

   或者，由于有些人反对这个公式的密度，它可以被改写：

   /li>

3. Princess 关于用不可变结构实现 O(1) 队列的困难的观点很有趣（并且很可能为一个令人信服的例子提供基础），但正如所述，它基本上是关于数据结构的可变性，而不是直接关于多重分配问题.

4. 我对埃拉托色尼筛法的答案很感兴趣，但不相信。在他引用的论文中给出的合适的 big-O，提取尽可能多的素数生成器在使用或不使用 SSA 的情况下看起来都不容易正确实现。

嗯，谢谢大家的尝试。由于大多数答案要么是 1）基于可变数据结构，而不是基于单一赋值，以及 2）它们是关于单一赋值形式的，因此本领域技术人员很容易反驳，我将从我的演讲和/或重组中划出界限（也许可以将其作为讨论主题作为备用，以防万一我在时间用完之前用完了单词）。

再次感谢。

到目前为止，这是我能想到的：

gcc 相关：

• 树木 SSA
• 树 SSA——GCC 的新优化框架
• Tree SSA 一种新的 GCC 优化基础架构
• 树SSA的设计与实现

其他：

• 机器 SUIF 的稀疏条件常数传播的一种实现
• 显式并行程序的并发静态单一赋值形式和常量传播

我已将其设为社区 wiki，因此请随时添加您自己的资源 - 谢谢！

例如：

如何以SSA 形式表示以下 x86 ：

通过引入一些伪函数，我想出了：

但我认为它太冗长了

谁能告诉我如何RSASSA-PKCS1-v1.5在 Java 中生成签名？

实际上，我想知道如何java.security.Signature上课。

我必须使用任何 3rd 方库吗？

我正在为基于寄存器的字节码编写一个编译器到一个具有静态单一分配 (SSA) 形式的 IR（具体来说，从 Dalvik VM 字节码到 LLVM IR，但我希望这个问题可以用于一般主题）和我想知道最好的或理论上最干净的方法来解决这个问题。

例如，如果我们有基于寄存器的指令：

那么我们不能再使用 vA 的旧值，因为它已被覆盖并替换为 vD - vE。

在 SSA 形式中，我们会有更多类似的东西

因为每个变量只分配一次。

问题在于，在从基于寄存器的语言进行映射时，我们不需要 SSA 表单跟踪的这些先前值，因为我们只使用每个寄存器的最新值。对我来说，继续创建我们永远不会使用的新变量似乎是一种不好的做法，或者只是“肮脏的”，但我想这就是你从表示中得到的。

因此，我的问题是实现这种映射的最佳方式是什么（有点主观，抱歉）。我最初的想法是，因为我知道每种方法使用的（固定）寄存器数量，所以我可以跟踪每个寄存器的最新值，并且只使用它，但我不确定如何会在实践中工作。

我期待听到你的想法。

我正在为我正在编写的编译器实现SSA 构造。SSA 算法中有一些我不理解的东西（使用Cytron 论文和《Java 中的现代编译器实现》一书，AW Appel 的第二版）。如果一个变量y第一次在一个直接的控制流路径中定义（并使用）但从未在另一个并行路径中定义，该怎么办？我是否必须在连接点（块定义的优势边界y）插入 PHI 函数？

例如，在块 B 中有 的第一个定义y。我是否必须在块 C 的开头插入一条 PHI 指令，带有两个操作数（一个用于每个传入的控制流路径）？然后在 SSA 重命名：我将如何命名来自从未定义的路径A -> C（而不是通过 B）的操作数？y

我一直在研究使用 SSA 指定的 IR 代码，尤其是以这种形式生成 LLVM IR。但是，我很困惑当呈现具有非平凡复制语义的类型时这是否有效。例如，

在这种 SSA 形式中，至少在最明显的层面上，这会导致令人讨厌的副本混乱（即使对于 C++）。LLVM 之类的优化器真的可以准确地优化这种情况吗？SSA 是否适用于具有非平凡复制/分配/等语义的类型？

编辑：问题是，如果我使用 LLVM SSA 寄存器来表示复杂类型（在本例std:string中+=为并避免讨厌的副本？

我正在研究 Java 字节码的优化器，并决定使用 SSA。然而，大多数优化要求所有操作都是纯函数式的，因此为了处理副作用，我决定为每个可能产生副作用的操作添加一个额外的不透明状态参数和返回值。这将防止优化或重新排序具有副作用的操作。例如，忽略异常处理，你会得到类似这个伪代码的东西。

我在做什么有名字吗？这是一个好方法吗？听说函数式语言有一个概念叫Monads，听上去很像但又不一样。使用单子是更好的方法吗？如果是这样，我该如何修改它以使用单子？

我需要为 C 代码制作数据流图。数据流图是指图中的节点表示加法和乘法等操作，边表示节点之间的操作数（数据）流的图。我的目标是分析计算密集型内核的数据流图的并行性和执行时间。我使用了许多工具从 Trimaran、Oink、GCC 等 C 程序生成数据流图。在这些工具中，GCC 的 Gimple 内部表示为我提供了 SSA 中每个基本块的一些数据流分析（静态单一分配）表格。SSA 表格简化了我的分析。这是我使用 GCC 的方法：

-fdump-tree-cfg为每个函数生成一个控制流图，其中节点代表基本块，边代表控制依赖。还显示了每个基本块中的数据依赖性。但是，它没有给出每个基本块的数据流图。我需要将数据依赖可视化，以便分析每个基本块中的数据流。

举个例子，如果你应用-fdump-tree-cfg到下面的代码

你得到这个：

-fdump-tree-vcg生成格式的控制流图VCG，但不携带任何数据依赖信息。

但是，GCC 有一些限制。例如，GCC 不会为每个基本块生成可视化的数据流图。我想知道是否有任何工具可以为 C 程序生成数据流图？或者可能有一个 GCC 插件来从 Gimple 表示生成数据流图。

PS：工具应该是平台独立的，不限于特定的架构。例如，GCC 中的 Gimple 表示是独立于体系结构的。