1 for each variable a:
2 Count[a] = 0
3 Stack[a] = [0]
4 rename_basic_block(B) =
5 for each instruction S in block B:
6 for each use of a variable x in S:
7 i = top(Stack[x])
8 replace the use of x with xi
9 for each variable a that S defines
10 count[a] = Count[a] + 1
11 i = Count[a]
12 push i onto Stack[a]
13 replace definition of a with ai
例如，下面的c代码：
1 a = x + y;
2 b = a - 1;
3 a = y + b;
4 b = 4 * x;
5 a = a + b;
1 computeDF[n]:
2 S = {}
3 for each node y in succ[n]
4 if idom(y) ≠ n
5 S = S ∪ {y}
6 for each child c of n in the dom-tree
7 computeDF[c]
8 for each w ∈ DF[c]
9 if n does not dom w, or n = w
10 S = S ∪ {w}
11 DF[n] = S
7.2.9插入φ函数
插入的算法描述如下：
1 place-phi-functions:
2 for each node n:
3 for each variable a ∈ Aorig[n]:
4 defsites[a] = defsites[a] ∪ [n]
5 for each variable a:
6 W = defsites[a]
7 while W ≠ empty list
8 remove some node n from W
9 for each y in DF[n]:
10 if a ∉ Aphi[y]
11 insert-phi(y, a)
12 Aphi[y] = Aphi[y] ∪ {a}
13 if a ∉ Aorig[y]
14 W = W ∪ {y}
15
16 insert-phi(y, a):
17 insert the statement a = ϕ(a, a, …, a)
18 at the top of block y, where the
19 phi-function has as many arguments
20 as y has predecessors
21 Where:
22 Aorig[n]: the set of variables defined at node "n"
23 Aphi[y]: the set of variables that have phi-functions at node "y"
7.2.10变量重命名
1 rename(n):
2 rename-basic-block(n)
3 for each successor Y of n, where n is the j-th predecessor of Y:
4 for each phi-function f in Y, where the operand of f is ‘a’
5 i = top(Stack[a])
6 replace j-th operand with ai
7 for each child X of n:
8 rename(X)
9 for each instruction S ∈ n:
10 for each variable v that S defines:
11 pop Stack[v]
1 i = 1
2 j = 1
3 k = 0
4 while k < 100
5 if j < 20
6 j = i
7 k = k + 1
8 else
9 j = k
10 k = k + 2
11 return j
7.3.2生成控制流图
7.3.3根据控制流图生成支配树
7.3.4计算支配前沿
1 For each statement S in the program:
2 IN[S] = OUT[S] = {}
3 For each variable v in the program:
4 For each statement S that uses v:
5 live(S, v)
6 live(S, v):
7 IN[S] = IN[S] ∪ {v}
8 For each P in pred(S):
9 OUT[P] = OUT[P] ∪ {v}
10 if P does not define v
11 live(P, v)
7.5SSA简史
“An Efficient Method of Computing Static Single Assignment Form, ” appeared in the conference Record of the 16th ACM Symposium on principles of Programming Languages (Jan. 1989).c9x.me/compile/bib/ssa.pdf
Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, ACM Transact~ons on Programmmg Languages and Systems, VO1 13, NO 4, October, le91, Pages 451.490.Efficiently computing static single assignment form and the control dependence graph (utexas.edu)
Lengauer, T. and Tarjan, R. "A Fast Algorithm for Finding Dominators in a Flowgraph", TOPLAS, 1:1 (1979) pp 121-141
Briggs, P. and Cooper, K. and Harvey, J. and Simpson, L. "Practical Improvements to the Construction and Destruction of Static Single Assignment Form", SP&E (28:8), (1998) pp 859-881
1 for each variable a:
2 Count[a] = 0
3 Stack[a] = [0]
4 rename_basic_block(B) =
5 for each instruction S in block B:
6 for each use of a variable x in S:
7 i = top(Stack[x])
8 replace the use of x with xi
9 for each variable a that S defines
10 count[a] = Count[a] + 1
11 i = Count[a]
12 push i onto Stack[a]
13 replace definition of a with ai
例如，下面的c代码：
1 a = x + y;
2 b = a - 1;
3 a = y + b;
4 b = 4 * x;
5 a = a + b;
1 computeDF[n]:
2 S = {}
3 for each node y in succ[n]
4 if idom(y) ≠ n
5 S = S ∪ {y}
6 for each child c of n in the dom-tree
7 computeDF[c]
8 for each w ∈ DF[c]
9 if n does not dom w, or n = w
10 S = S ∪ {w}
11 DF[n] = S
7.2.9插入φ函数
插入的算法描述如下：
1 place-phi-functions:
2 for each node n:
3 for each variable a ∈ Aorig[n]:
4 defsites[a] = defsites[a] ∪ [n]
5 for each variable a:
6 W = defsites[a]
7 while W ≠ empty list
8 remove some node n from W
9 for each y in DF[n]:
10 if a ∉ Aphi[y]
11 insert-phi(y, a)
12 Aphi[y] = Aphi[y] ∪ {a}
13 if a ∉ Aorig[y]
14 W = W ∪ {y}
15
16 insert-phi(y, a):
17 insert the statement a = ϕ(a, a, …, a)
18 at the top of block y, where the
19 phi-function has as many arguments
20 as y has predecessors
21 Where:
22 Aorig[n]: the set of variables defined at node "n"
23 Aphi[y]: the set of variables that have phi-functions at node "y"
7.2.10变量重命名
1 rename(n):
2 rename-basic-block(n)
3 for each successor Y of n, where n is the j-th predecessor of Y:
4 for each phi-function f in Y, where the operand of f is ‘a’
5 i = top(Stack[a])
6 replace j-th operand with ai
7 for each child X of n:
8 rename(X)
9 for each instruction S ∈ n:
10 for each variable v that S defines:
11 pop Stack[v]
1 i = 1
2 j = 1
3 k = 0
4 while k < 100
5 if j < 20
6 j = i
7 k = k + 1
8 else
9 j = k
10 k = k + 2
11 return j
7.3.2生成控制流图
7.3.3根据控制流图生成支配树
7.3.4计算支配前沿
1 For each statement S in the program:
2 IN[S] = OUT[S] = {}
3 For each variable v in the program:
4 For each statement S that uses v:
5 live(S, v)
6 live(S, v):
7 IN[S] = IN[S] ∪ {v}
8 For each P in pred(S):
9 OUT[P] = OUT[P] ∪ {v}
10 if P does not define v
11 live(P, v)
7.5SSA简史
“An Efficient Method of Computing Static Single Assignment Form, ” appeared in the conference Record of the 16th ACM Symposium on principles of Programming Languages (Jan. 1989).c9x.me/compile/bib/ssa.pdf
Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, ACM Transact~ons on Programmmg Languages and Systems, VO1 13, NO 4, October, le91, Pages 451.490.Efficiently computing static single assignment form and the control dependence graph (utexas.edu)
Lengauer, T. and Tarjan, R. "A Fast Algorithm for Finding Dominators in a Flowgraph", TOPLAS, 1:1 (1979) pp 121-141
Briggs, P. and Cooper, K. and Harvey, J. and Simpson, L. "Practical Improvements to the Construction and Destruction of Static Single Assignment Form", SP&E (28:8), (1998) pp 859-881
