使用Cytron算法生成SSA

Question

我正在尝试使用 Cytron 的 算法 生成 SSA 一切似乎都工作正常，但对于某些测试用例我遇到了问题。我有以下循环测试示例设置：

我的问题出现在节点

w8

上

0x100003f50

的定义上。 在其主导边界集中以

0x100003f50

作为节点并以

w8

作为定义的节点是：

0x100003f64

0x100003f50

0x100003fa8

注意，节点

0x100003fa8

最初没有定义，在第二次迭代时，它确实具有

w8

节点

0x100003f90

和

0x100003f78

的 phi 赋值形式的定义。

因此，在 phi 函数插入步骤之后，我们有 3 个参数用于 phi 赋值，用于节点

w8

中的定义

0x100003f50

。

在重命名步骤之后，我们将 phi 变量替换为定义 phi 赋值的块的前驱中的相应定义，在本例中

0x100003f50

，

0x100003f50

节点只有 2 个前驱，因此替换为

w8

的 phi 参数缺少重命名，不仅对我来说，迭代块的后继者以用相应的块索引替换它们的 phi 函数参数没有多大意义，因为在经典中示例：

似乎工作得很好，定义 phi 函数的每个块的前身也将该块作为其主导边界，在我的示例中，定义 phi 函数的测试块的前身为

w8

，即块

0x100003f50 

，将入口块和循环边缘节点作为前身，保留 phi 参数之一不变，所以我想知道我在这里错过了什么？

Answer 1

我不知道这是否是正确的答案，或者我只是错过了一些东西，但我想到了如果当前节点在支配树中的某个位置有一个不是所讨论的前沿节点的节点，它也有相同的边界节点，那么我不会为这种特殊情况插入另一个 phi 参数。

这是用 python 编写的部分修复：

                        # Cases where node has a doiminator which also defines the symbol
                        # and both has the same frontier node (can happen in loop)
                        # and so the dominator dominates the definition of the symbol of the
                        # current node then we don't need to insert another variable to the
                        # phi assingment of the frontiner node
                        idom = node.idom
                        quit = False
                        while idom != None and idom != frontier_node:
                            if frontier_node in idom.dominance_frontier and idom in procedure.symbol_defs[sym]:
                                quit = True
                                break
                            idom = idom.idom
                        
                        if quit: # continue to the next node in the enacpsuling loop of phi nodes insertion
                            continue