标签: ssa

我听过的反对函数式语言的一个论点是,单个赋值编码太难了,或者至少比"普通"编程要难得多.

但是通过我的代码,我意识到如果你用一种合理的现代语言写作,我真的没有很多(任何？)使用模式,使用单一的赋值形式也无法编写.

那么变量的用例有哪些在一个单独的范围调用中变化？请记住,在这种情况下,调用之间不同的循环索引,参数和其他范围限制值不是多个赋值(除非您出于某种原因必须在正文中更改它们),并假设您正在编写某些内容远远高于汇编语言级别,在那里你可以编写类似的东西

values.sum

或(如果没有提供金额)

function collection.sum --> inject(zero, function (v,t) --> t+v )

和

x = if a > b then a else b

要么

n = case s 
  /^\d*$/ : s.to_int
  ''      : 0
  '*'     : a.length
  '?'     : a.length.random
  else    fail "I don't know how many you want"

当你需要,并有列表推导,地图/收集等等.

您是否发现在这样的环境中仍然需要/需要可变变量,如果是,那么对于什么？

澄清一点,我不是要求对SSA表格的异议进行背诵,而是要求适用这些异议的具体例子.我正在寻找具有可变变量的清晰简洁的代码,如果没有它们就无法编写.

到目前为止我最喜欢的例子(以及我对他们的最佳反对意见):

1. 保罗约翰逊的Fisher-Yates算法答案,当你包含大O约束时,它非常强大.但是,正如catulahoops指出的那样,big-O问题与SSA问题无关,而是与可变数据类型相关联,并且在预留的情况下,可以在SSA中清楚地编写算法:

    shuffle(Lst) ->
        array:to_list(shuffle(array:from_list(Lst), erlang:length(Lst) - 1)).
    shuffle(Array, 0) -> Array;
    shuffle(Array, N) ->
        K = random:uniform(N) …

   Run Code Online (Sandbox Code Playgroud)

众所周知如何将代码从SSA表示转换为寄存器机器.(基本上,图形着色寄存器分配是这种转换的核心.)

但是从SSA转换为堆栈机器的一般方法是什么？(CIL字节代码,在我看的情况下.)我希望它更简单,因为不需要寄存器分配？

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

我一直在徘徊的想法是将堆栈位置附加到SSA ID,然后在代码路径收敛时查看堆栈中仍然存在的内容,但这似乎不是做事的Right Way(TM).

是否有一种简单的算法可以跟踪多个代码路径中的堆栈操作并在收敛时确定冲突？

Administrative Normal Form是代码的中间表示,适合编译器使用,逻辑上等同于单静态分配但具有一些优点.例如,检查程序是否是有效的SSA表单是关于通过图表的可能路径集合的存在性问题.但是,检查程序是否是有效的ANF表达式只是本地语法的问题.

从严格的功能代码生成ANF非常容易,但我有兴趣从包含变量更新,循环等的命令式代码生成ANF.

有简单的算法将SSA转换为ANF.但是,如果您想快速生成SSA,那么首先生成SSA会变得非常重要.看起来直观的是,如果你想要的是更简单,更透明的格式,那么直接生成它而不是通过更不透明的形式应该更有效.

是否有已发布的算法直接从命令式代码生成ANF？

例如，我有一段C代码：

void foo(int x) {
    int y;
    if (x > 0) {
        y = 1;
    } else {
        y = 2;
    }
    // do something with y
}

为了在 LLVM IR 级别简化此代码（y可以放入寄存器而不是堆栈中），我可以使用select：

define void @foo(i32 %x) {
    %result = icmp sgt i32 %x, 0
    %y = select i1 %result, i32 1, i32 2
    ; do something with %y
}

但是，如果我使用phi，代码会变得更长：

define void @foo(i32 %x) {
    %result = icmp sgt i32 %x, 0
    br i1 …

我知道如何基于寄存器以及基于堆栈的虚拟机如何独立工作.我知道两者的优点和缺点.我想知道的是,有没有人试图合并这两者？

我试图在网上搜索这种虚拟机的存在,但无济于事.我得到的最好结果是一篇关于混合虚拟机(HyVM)的文章.如果确实为编程语言创建了这样的虚拟机,我将有兴趣查看其源代码以了解它是如何工作的.

也许有人可以指出我找到这样一个虚拟机的正确方向,或者将我链接到本主题中详述的文章或博客文章.

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

x = 1;            // A
if (P)            // A
    y = x + 1;    // B
    y = y + 1;    // B
x = x + 1;        // C
return;           // C

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

Entry --- A --------- C --- Exit
           \         /
            \-- …

LLVM的opt -S -mem2reg过程产生了所谓的“修剪” SSA，即删除了所有无效phi函数的形式。我想将这些phi指令保留在IR中，以获得“最小” SSA，但是我没有找到简单的方法来做到这一点。

我注定要从头开始实施整个SSA构建算法，还是有一种方法可以使用现有工具来实现？

我编写以下C代码，其中变量X被分配了两次：

int main()
{
        int x;
        x = 10;
        x = 20;
        return 0;
}

使用以下命令编译并生成IR表示

clang -emit-llvm -c ssa.c

产生红外线

; Function Attrs: nounwind uwtable
define i32 @main() #0 {
entry:
  %retval = alloca i32, align 4
  %x = alloca i32, align 4
  store i32 0, i32* %retval
  store i32 10, i32* %x, align 4
  store i32 20, i32* %x, align 4
  ret i32 0
}

如果我对SSA格式的理解是正确的，则在此示例中，我们应将x1和x2视为生成的两个LLVM IR变量，并分别分配两个值10和20。我们应该使用一些特定的选项来获得SSA IR表示，或者我对IR表示的理解不正确吗？请指教。

编辑：正如一个答案中所建议的那样，使用-mem2reg优化传递会给我以下输出

clang -c -emit-llvm ssa.c -o ssa.bc
opt -mem2reg …

我可以将抽象语法树直接翻译成SSA格式,还是需要创建控制流图,然后从所述CFG创建静态单一分配表？

在控制流图的上下文中:我如何为类似c的程序表示这一点？我想我可以存储每个函数中所有基本块的CFG图,但是当我调用一个函数时,这可能会使事情复杂化.我能想到的另一种方法是整个程序的CFG,即所有源文件,但是我如何存储有关函数的信息？我可以在基本块(即父节点)中存储指向该函数的指针吗？

如果我从CFG生成SSA,我是否需要担心代表语句控制流的CFG？我想我只需要代表基本的块控制流程.