算法Algorithms

工作列表算法Worklist Algorithms

首先，引入 worklist empty作为空工作列表，insert作为插入数据，extract作为删除数据。input作为输入代码，output作为分析结果。

整个过程的伪代码就是：

初始化：新建工作列表，并填充约束。

initialisation(){

W = empty

for all x コ t in S do

​    W = insert((x コ t),W)

​    Analysis[x] = 空

​    infl[x] = 空

for all x コ t in S do

​    for all x\' in FV(t) do

​        infl[x\'] = infl[x\'] ∪ {x コ t}

}

更新数据：将工作列表中的约束分析，如果约束包含子约束，那么将子语句约束插入到工作列表继续分析。

Iteration(){

while W != empty do
    ((x コ t),W) = extract(W)
    new = eval(t,Analysis)
    if(Analysis[x] !コ new){
        Analysis[x] = Analysis[x] ∪ new
        for all x\' コ t\' in infl[x] do
            W = insert((x\' コ t\'),W)
    }

}

后续分析点Reverse Postorder

程序的执行并不是永远自上而下不会跳转的，也并不是不会重复执行同一句语句的，所以，我们的算法也不可以是自上而下的。因此，我们引入Reverse Postorder。

我们对extract()进行修改

W.p保存下一个分析语句所在位置，当当前语句W.c分析完毕后，分析W.p的语句

function extract(W.c,W.p){
    if W.c = nil then 
        W.c = sort_Postorder(W.p)
        W.p=空
    return (head(W.c),(tail(W.c),W.p))    
}

遍历循环算法The Round Robin Algorithm

在后续分析点的理论中，我们需要找到下一句分析的语句，我们使用循环查找。为了方便代码执行，我们将所有语句用序号标记，遍历所有语句，找到符合条件的那一句语句。此时，我们不需要特地标记W.p，只需要利用代码逻辑继续执行就行。

当程序没有分析完时，遍历程序所有语句作为下一句语句分析，当找到符合的语句，重复遍历分析下一句，直到分析完毕。

while change do
    change = false
    for i = 1 to N do
        new = eval(t,Analysis)
        if(Analysis[x_i] !コ new) then 
            change = true
            Analysis[x_i] = Analysis[x_i] ∪ new

代码块遍历Interating Through Strong Components

对于循环遍历算法，我们可以增加一些关系简少遍历。比如有些语句块中不包含跳转，我们只需要按顺序分析即可。或者有些语句有着固定执行顺序。

所以我们将代码分成代码块并标记

for i = 1 to N do
    start(j) = end(j) = i
    while(postorder(i) = i+1){
        end(j) = end(j)++
    }
    i = end(j) + 1
        

此时，我们既要对代码块之间进行分析，又要对代码块内部分析。所以更改代码为

extract(){
    if W.c = nil {
        W.c = start(sort(W.c)+1)
        W.p = W.p \\ W.c
    }
    return (head(W.c),tail(W.c),W.p)
}