DCC888 ：SSA （static single assignment form）

Control Flow Graphs Revisited

The Static Single Assignment Form

Each variable in SSA form program has only one definition site

To and From SSA form

利用右边的算法重新定义已definition value的name

phi-function

SSA elimination

critical edges

edge splitting

criteria for inserting phi-function

iterative creation of phi-function

dominance property of SSA form

the dominance frontier

构造Dominator Tree以及Dominator Frontier

e的dominat set是{e，f，g，h}，e的strictly dominate set是{f，g，h}
f的successor是{d，h}，h在e的 strictly dominate里面，所有{d}是e的dominate frontier
g的successor是{k，h}，h在e的 strictly dominate里面，所有{k}是e的dominate frontier
h的successor是{I，e}，I和e都不在e的 strictly dominate里面，所有{I，e}是e的dominate frontier
e的successor是{f，g}，f和g都在e的 strictly dominate里面，两个不属于e的dominate frontier

the dominance frontier criterion

从第一个图开始，f的dominance是{f}，f没有任何strictly dominance，f的successor是{d，h}，

再看第二个图，d的dominance是{d}，d没有任何strictly dominance，d的successor是{I}， df[d]={I}
h的dominance是{h，I}，h 没有任何strictly dominance，h的successor是{e，I}， df[h]={e,I}
I的dominance是{I}，I没有任何strictly dominance，

inserting phi-function

renaming variables

SPARSE ANALYSES 利用ssa 进行analysis

dead code elimination

sparse constant propagation

liveness analysis in ssa form programs