DCC888 ：SSA （static single assignment form）
时间：2023-04-10 19:07:00
SSA ：static single assignment form
- Control Flow Graphs Revisited
- The Static Single Assignment Form
- To and From SSA form
-
- 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
- the dominance frontier criterion
- inserting phi-function
- renaming variables
- SPARSE ANALYSES 利用ssa 进行analysis
-
- dead code elimination
- sparse constant propagation
- liveness analysis in ssa form programs
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在里面，两个不属于edominate 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
