SSA形式程序构建的系统依赖图（SDG）是否可能存在环？

答案是肯定的——即使是经过SSA转换、变量仅赋值一次的程序，生成的SDG依然可能出现环结构，不管是单纯的控制依赖环，还是结合函数调用的环。下面分两种情况举例说明：

1. 循环控制流导致的控制依赖环 #

SSA只是处理变量的赋值逻辑，完全不会改变程序的控制流结构。像常见的while循环、for循环这类本身带有循环逻辑的代码，转成SSA后，对应的SDG里依然会有控制依赖形成的环。

举个简单的例子：
原始代码：

int i = 0;
while (i < 10) {
    i = i + 1;
}

转换为SSA形式后：

i_0 = 0;
if (i_0 < 10) goto loop_body;
loop_body:
i_1 = i_0 + 1;
if (i_1 < 10) goto loop_body;

在对应的SDG中：

• 第一个条件判断节点（i_0 < 10）控制loop_body块的执行，形成控制边：条件判断1 -> loop_body
• loop_body块里生成了i_1，第二个条件判断节点（i_1 < 10）依赖i_1的数据，同时这个条件判断的结果会决定是否回到loop_body，形成控制边：loop_body -> 条件判断2 -> loop_body
  最终就形成了loop_body -> 条件判断2 -> loop_body的控制依赖环，和变量是否是单赋值无关。

2. 递归函数调用导致的环 #

递归调用本身就是一种循环逻辑，在SDG中会形成跨函数的控制+数据依赖环。

举个阶乘递归的例子：
原始代码：

int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n-1);
}

简化的SSA形式：

fact(n_0):
    if (n_0 == 0) goto return_1;
    n_1 = n_0 - 1;
    res_0 = fact(n_1);
    res_1 = n_0 * res_0;
    return res_1;
return_1:
    return 1;

对应的SDG里：

• 函数fact的入口节点依赖于递归调用节点（res_0 = fact(n_1)）的控制流（因为调用会重新进入函数入口）
• 递归调用节点依赖于n_1的计算节点，而n_1的计算又依赖于函数入口的参数n_0
  最终形成环：fact入口 -> n_1计算节点 -> 递归调用节点 -> fact入口

关键说明 #

SSA的作用是消除同一变量多次赋值导致的数据依赖环，但它管不了程序本身的控制流循环（比如while、for）或者递归调用。而SDG同时包含控制依赖和数据依赖，只要程序存在循环控制逻辑，就必然会在SDG中出现环结构。

内容的提问来源于stack exchange，提问作者Abdulellah Alsaheel