代碼$a10;if($cond){$a20;}echo$a;數(shù)據(jù)結(jié)構(gòu) (zend_ssa.h)整個(gè) SSA 系統(tǒng)的核心是三個(gè)結(jié)構(gòu)體zend_ssa (頂層容器) ├── cfg: zend_cfg ← 控制流圖基本塊、前驅(qū)/后繼、支配樹 ├── blocks[]: zend_ssa_block ← 每個(gè)基本塊的 phi 鏈表頭 ├── ops[]: zend_ssa_op ← 每條指令的 SSA 信息use/def 編號(hào) 鏈表 ├── vars[]: zend_ssa_var ← 每個(gè) SSA 變量的 def-use 信息 └── vars_count ← SSA 變量總數(shù)zend_ssa_op (每條指令在 SSA 中的視圖)typedefstruct_zend_ssa_op{intop1_use;// op1 讀的是哪個(gè) ssa_var (≥0) 或 -1intop2_use;// op2 讀的是哪個(gè) ssa_var (≥0) 或 -1intresult_use;// result 讀的是哪個(gè) ssa_var (≥0少見) 或 -1intop1_def;// op1 定義的是哪個(gè) ssa_var (≥0) 或 -1intop2_def;// op2 定義的是哪個(gè) ssa_var (≥0) 或 -1intresult_def;// result 定義的是哪個(gè) ssa_var (≥0) 或 -1intop1_use_chain;// 該 use 在使用鏈表中的下一個(gè) use 指令編號(hào)intop2_use_chain;intres_use_chain;}zend_ssa_op;zend_ssa_var (每個(gè) SSA 變量的元信息)typedefstruct_zend_ssa_var{intvar;// 原始變量編號(hào)CV#0, CV#1, TMP#last_var0...intscc;// 強(qiáng)連通分量intdefinition;// 定義該 ssa_var 的指令編號(hào)入口intuse_chain;// 使用該 ssa_var 的第一個(gè) use 指令編號(hào)鏈表頭zend_ssa_phi*definition_phi;// 如果是 phi 定義的指向 phizend_ssa_phi*phi_use_chain;// 該變量在 phi 中的使用列表unsignedintalias:2;// 是否可能被間接修改符號(hào)表別名等}zend_ssa_var;zend_ssa_phi (phi 函數(shù))typedefstruct_zend_ssa_phi{zend_ssa_phi*next;// 同一 BB 中的下一個(gè) phiintpi;// ≥0 表示 e-SSA Pi 節(jié)點(diǎn)來自哪個(gè)前驅(qū) BBintvar;// 原始 CV/VAR/TMP 變量號(hào)intssa_var;// 該 phi 定義的 SSA 變量編號(hào)intblock;// 所在基本塊zend_ssa_phi**use_chains;// 每個(gè) source 的使用鏈表int*sources;// phi 的源 SSA 變量號(hào)數(shù)組每個(gè)前驅(qū)一個(gè)}zend_ssa_phi;三階段構(gòu)建流程 (zend_build_ssa, zend_ssa.c:996)階段 0控制流圖 支配者樹在 SSA 構(gòu)建之前zend_build_cfg() 已經(jīng)完成了CFG: BB0 [start0, len2] (ASSIGN $a,10; JMPZ $cond,BB2) │ successors: BB1, BB2 ├─? BB1 [start2, len2] (ASSIGN $a,20; JMP BB2) │ successors: BB2 └─? BB2 [start4, len2] (ECHO $a; RETURN) successors: (exit) 支配者樹 (dominator tree): BB0 為根函數(shù)入口 BB1: idom BB0 (BB0 支配 BB1) BB2: idom BB0 (BB0 支配 BB2) BB2 的前驅(qū): BB0, BB1 (這是合并點(diǎn)) 預(yù)排序索引: BB0: level0, children→BB1→BB2 BB1: level1 BB2: level1階段 1: DFG 構(gòu)建 zend_build_dfg() def 傳播 Phi 放置 (zend_build_ssa, line 1017-1116)Step 1a: DFG 收集 def/use 集合 (zend_build_dfg, zend_dfg.c:252)遍歷每個(gè) BB 的每條指令逐條調(diào)用 _zend_dfg_add_use_def_op() (zend_dfg.c:22)BB0: OP0 ASSIGN $a, 10 → op1_typeIS_CV($a): zend_bitset_incl(use, $a) ← $a 的舊值被使用覆蓋前 → 然后 goto add_op1_def (line 213): zend_bitset_incl(def, $a) → result_def 無 BB0: use{$a} def{$a} OP1 JMPZ $cond, BB2 → op1_typeIS_CV($cond): zend_bitset_incl(use, $cond) ← 讀 $cond → 無 def BB0: use{$a, $cond} def{$a} BB1: OP2 ASSIGN $a, 20 → 同上: use{$a}, def{$a} BB1: use{$a} def{$a} OP3 JMP BB2 → 無 use, 無 def BB2: OP4 ECHO $a → op1_typeIS_CV($a): zend_bitset_incl(use, $a) BB2: use{$a} def{} OP5 RETURN 1 → IS_CONST, 無 useStep 1b: 計(jì)算 liveness (in/out) (zend_build_dfg, line 288-310)經(jīng)典的數(shù)據(jù)流不動(dòng)點(diǎn)迭代in use ∪(out - def), out ∪in(successors)一回合 BB2: out{} inuse{$a} BB1: outin(BB2){$a} inuse{$a} ∪({$a} - def{$a}) {$a} BB0: outin(BB1)∪in(BB2){$a} inuse{$a,$cond} ∪({$a} - {$a}) {$a, $cond}Step 1c: 傳播 def 確定 Phi 位置 (line 1044-1116)這是核心。算法逐條傳播 def 集合對(duì)于每個(gè) CFG 合并點(diǎn)前驅(qū)數(shù) 1 的 BB沿支配者邊往上走找到需要 phi 的變量。初始化: def_j 每個(gè) BB 的局部 def 集合 phi_j {} (空) 迭代: BB2 (predecessors_count2 1, 是合并點(diǎn)): 對(duì)每個(gè)前驅(qū) k: kBB0: iBB0, i ! idom(BB2)BB0? 否 → 停止 (BB0 直接支配 BB2) kBB1: iBB1, i ! idom(BB2)BB0? 是 → phi_j | phi_j ∩ def(BB1) ∩ in(BB2) → phi(BB2) {} ∩ {$a} ∩ {$a} {} → 然后 i idom(BB1) BB0 idom(BB2) → 停止 首次迭代 phi_2 {}全都滿足 → 不變更新 def_2 的 phi 部分 但是: def(BB0){$a}, def(BB1){$a}, in(BB2){$a} 實(shí)際算法在 line 1062 用 union_with_intersection: phi_2 | phi_2 ∩ def(i) ∩ in(BB2) 等一下這個(gè)邏輯是: phi_j U_{predecessor k} (phi_j ∩ def(i) ∩ in(j)) 對(duì)于所有在 idom 之上的 i。當(dāng) i ! idom(j) 時(shí)繼續(xù)上行。 首輪: phi_2 {} → 交集為空 → phi_2 {} 但 zend_bitset_subset(phi_2, def_2, set_size)? def(BB2) {}, phi_2 {} → 是子集 → changed0 ... 實(shí)際上首輪不變但問題在于 BB0 的 def{$a} 沒到達(dá) BB2 覆蓋 def(BB2)... 實(shí)際上這個(gè)算法有問題需要第二輪。讓我簡(jiǎn)化解釋...實(shí)際上 PHP 的算法更精妙。在標(biāo)準(zhǔn)教科書法中phi 放置dominance frontier 上。PHP 采用一種變體foreach block j with1predecessors:foreach predecessor k:ikwhilei!idom(j):phi_j|def_i ∩ in_j// 在非直接支配者的路徑上任何被定義且活躍的變量需要 phiiidom(i)實(shí)際結(jié)果簡(jiǎn)化后的 PHP 算法對(duì)于 BB2 (predecessorsBB0, BB1, idomBB0): 前驅(qū) BB0: iBB0 idom → 不進(jìn)入 while 前驅(qū) BB1: iBB1 ! idom → 進(jìn)入 while phi(BB2) | def(BB1) ∩ in(BB2) | {$a} ∩ {$a} | {$a} i idom(BB1) BB0 idom(BB2) → 退出 結(jié)果: phi(BB2) {$a} def(BB2) {} → phi ? def → def(BB2) | phi → def(BB2) {$a} changed 1 → 再次迭代 第二次迭代: phi(BB2) {$a}, def(BB0) {$a}, def(BB1) {$a} phi | phi ∩ def(BB1) ∩ in(BB2) {$a} ∩ {$a} ∩ {$a} {$a} 不變 → def(BB2)已經(jīng)包含 {$a} → 沒有新phi → 收斂在合并點(diǎn)創(chuàng)建 phi 指令 (line 1083-1116)在 BB2 中為 $a 創(chuàng)建 phi: phi-pi -1 (普通 phi, 不是 e-SSA Pi) phi-var 0 (CV#0, 即 $a) phi-ssa_var -1 (renaming 階段分配) phi-sources[0] -1 (來自 BB0 前驅(qū), 待填充) phi-sources[1] -1 (來自 BB1 前驅(qū), 待填充) phi-block 2階段 2: 變量重命名 (zend_ssa_rename, line 914)這是經(jīng)典 Cytron 算法的 renaming pass。按照支配樹的前序遍歷進(jìn)行。關(guān)鍵數(shù)據(jù)結(jié)構(gòu)var[]// var[原始var_num] 當(dāng)前活躍的 SSA 變量號(hào)// 初始值: var[0]0 ($a), var[1]1 ($cond) 等// 初始 for CV: var[i] i (line 1128)// 對(duì)于 TMP_VAR: var[i] -1 (line 1125)遞歸遍歷支配樹 (使用 worklist 模擬遞歸line 914-988)進(jìn)入 BB0 (n0): // 1. 處理 BB0 的 phi (BB0 沒有 phi) // 2. 遍歷 BB0 的指令 (zend_ssa_rename_in_block, line 820) OP0 ASSIGN $a, 10 → op1_typeIS_CV → op1_use var[0] 0 (ssa_var[0]) ← 讀 $a 的舊值 → opcodeZEND_ASSIGN → goto add_op1_def: op1_def ssa_vars_count 2 ← 創(chuàng)建新的 ssa_var var[0] 2 ← 更新 $a 的活躍版本 ssa_vars_count → 3 → ssa_ops[0]: {op1_use:0, op1_def:2} OP1 JMPZ $cond, BB2 → op1_typeIS_CV → op1_use var[1] 1 (ssa_var[1]) → result_typeIS_TMP_VAR → result_def ssa_vars_count 3 var[last_var0] 3 ← TMP 變量也需要 rename ssa_vars_count → 4 → ssa_ops[1]: {op1_use:1, result_def:3} // 3. 填充后繼 BB 的 phi sources BB0 的后繼: BB1, BB2 對(duì)于 BB2 的 phi $a (ssa_var 尚為 -1): phi-sources[0] var[0] 2 ← 填充 BB0→BB2 邊上的值 // 4. 遞歸處理子節(jié)點(diǎn) 先 BB1 (level1), 再 BB2 (level1) 進(jìn)入 BB1 (n1): // 1. 無 phi // 2. 遍歷指令 OP2 ASSIGN $a, 20 → op1_use var[0] 2 ← 當(dāng)前 $a 活躍版本仍是 ssa_var[2]來自 BB0 → 等等! 這是 ASSIGN, no_val 標(biāo)注: zend_ssa_is_no_val_use(line 221) 返回 true → op1_use 存在但被標(biāo)記為 no_val (值不重要) → add_op1_def: op1_def ssa_vars_count 4 ← 新版本 var[0] 4 ← $a 的活躍版本更新為 4 → ssa_ops[2]: {op1_use:2, op1_def:4} OP3 JMP BB2 → 無 use, 無 def // 3. 填充后繼 BB2 的 phi sources 對(duì)于 BB2 的 phi $a: phi-sources[1] var[0] 4 ← 填充 BB1→BB2 邊上的值 // 4. BB1 沒有子節(jié)點(diǎn) (leaf) → 直接回溯 var[0] 恢復(fù)為 2 (退出 BB1 時(shí)回滾 var 數(shù)組) 進(jìn)入 BB2 (n2, BB0 的另一個(gè)子節(jié)點(diǎn)): // 1. 處理 BB2 的 phi (zend_ssa_rename_in_block, line 829) phi for $a: phi-ssa_var ssa_vars_count 5 ← 為 phi 分配 ssa_var 編號(hào) var[0] 5 ← $a 的活躍版本現(xiàn)在變成 phi 的結(jié)果 OP4 ECHO $a → op1_typeIS_CV → op1_use var[0] 5 ← 使用 phi 結(jié)果! → ssa_ops[4]: {op1_use:5} OP5 RETURN 1 → IS_CONST → 無 SSA 參與 // 3. BB2 無后繼 → 不再填充 phi sources // 4. 無子節(jié)點(diǎn) → 回溯構(gòu)建 use-def 鏈表 (zend_ssa_compute_use_def_chains, line 1144)這是最關(guān)鍵的一步。從后往前掃描所有指令為每個(gè)被使用的 ssa_var 建立從 def 到所有 use 的單鏈表。重命名后的 ssa_ops (opN_use / opN_def):OP0 ASSIGN: op1_use0, op1_def2 ssa_ops[0] OP1 JMPZ: op1_use1, result_def3 ssa_ops[1] OP2 ASSIGN: op1_use2, op1_def4 ssa_ops[2] OP3 JMP: (無 SSA) ssa_ops[3] OP4 ECHO: op1_use5 ssa_ops[4] OP5 RETURN: (無 SSA) ssa_ops[5]BB2 phi: ssa_var5, sources[2, 4] (來自 BB0→2, BB1→4)逆向掃描建立鏈表 (line 1167-1193)// ssa_vars 每位初始化為:// var -1// scc -1// definition -1// use_chain -1 ← 鏈表頭-1 表示空for(iop_array-last-1;i0;i--){// 從最后的指令往前zend_ssa_op*opssa-opsi;// 鏈入 use 鏈表 (頭插法)if(op-op1_use0){op-op1_use_chainssa_vars[op-op1_use].use_chain;// 保存舊鏈頭ssa_vars[op-op1_use].use_chaini;// 新鏈頭 當(dāng)前指令}// 對(duì) op2_use, result_use 同理// 設(shè)置 definition 指針if(op-op1_def0){ssa_vars[op-op1_def].definitioni;// 指向定義指令}// 對(duì) op2_def, result_def 同理}逆向掃描的執(zhí)行過程i5 OP5 RETURN: 無 use, 無 def → 無事 i4 OP4 ECHO: op1_use5 → ssa_ops[4].op1_use_chain ssa_vars[5].use_chain -1 → ssa_vars[5].use_chain 4 ← ssa_var[5] 被 OP4 使用 ssa_vars[5]: use_chain 4 i3 OP3 JMP: 無 i2 OP2 ASSIGN: op1_use2, op1_def4 → op1_use_chain ssa_vars[2].use_chain -1 → ssa_vars[2].use_chain 2 ← ssa_var[2] 被 OP2(op1) 使用 → ssa_vars[4].definition 2 ← ssa_var[4] 由 OP2 定義 ssa_vars[2]: use_chain 2 ssa_vars[4]: definition 2 i1 OP1 JMPZ: op1_use1, result_def3 → op1_use_chain ssa_vars[1].use_chain -1 → ssa_vars[1].use_chain 1 ← ssa_var[1] 被 OP1(op1) 使用 → ssa_vars[3].definition 1 ← ssa_var[3] 由 OP1 定義 ssa_vars[1]: use_chain 1 ssa_vars[3]: definition 1 i0 OP0 ASSIGN: op1_use0, op1_def2 → op1_use_chain ssa_vars[0].use_chain -1 → ssa_vars[0].use_chain 0 ← ssa_var[0] 被 OP0(op1) 使用 → ssa_vars[2].definition 0 ← ssa_var[2] 由 OP0 定義 ssa_vars[0]: use_chain 0 ssa_vars[2]: definition 0 ssa_vars[2]: use_chain 2 (之前已有)最后處理 phi 的 use 鏈 (line 1196-1210)for(i0;issa-cfg.blocks_count;i){zend_ssa_phi*phissa-blocks[i].phis;while(phi){phi-blocki;ssa_vars[phi-ssa_var].varphi-var;ssa_vars[phi-ssa_var].definition_phiphi;// phi 是定義// ... 填充 phi 到 source 的使用鏈表phiphi-next;}}// BB2 的 phi: sources[2, 4], ssa_var5// ssa_vars[5].definition_phi phi// ssa_vars[5].definition -1 (不是指令定義的是 phi 定義的)// ssa_vars[2] 的 phi_use_chain 中包含此 phi (ssa_var[2] 是這個(gè) phi 的一個(gè) source)// ssa_vars[4] 的 phi_use_chain 中包含此 phi最終完整的 use-def 鏈ssa_var[0]: $a 的初始版本 (入口值) definition -1 (函數(shù)入口無定義指令) use_chain 0 ──? OP0 (ASSIGN, op1_use, no_val) ssa_var[1]: $cond 的初始版本 definition -1 use_chain 1 ──? OP1 (JMPZ, op1_use) ssa_var[2]: $a 的第 2 個(gè)版本 (10) definition 0 ← 由 OP0 (ASSIGN $a, 10) 定義 use_chain 2 ──? OP2 (ASSIGN, op1_use, no_val) phi_use_chain ──? phi in BB2, source[0] ssa_var[3]: JMPZ 結(jié)果 (條件跳轉(zhuǎn)的布爾值) definition 1 use_chain -1 (未使用) ssa_var[4]: $a 的第 3 個(gè)版本 (20) definition 2 ← 由 OP2 (ASSIGN $a, 20) 定義 use_chain -1 (通過 phi 使用不在指令鏈表中) phi_use_chain ──? phi in BB2, source[1] ssa_var[5]: phi($a, BB0→2, BB1→4) 的結(jié)果 definition_phi phi in BB2 definition -1 use_chain 4 ──? OP4 (ECHO, op1_use)圖示化:遍歷 use-def 鏈的 API從 def 遍歷所有 use#defineFOREACH_USE(var,use)do{\int_var_num(var)-ssa-vars,next;\for(use(var)-use_chain;use0;usenext){\nextzend_ssa_next_use(ssa-ops,_var_num,use);// zend_ssa.h:193-203 — 輔助函數(shù)staticzend_always_inlineintzend_ssa_next_use(constzend_ssa_op*ssa_op,intvar,intuse){ssa_opuse;// 指針移到 use 所在的 ssa_opif(ssa_op-op1_usevar){returnssa_op-op1_use_chain;// 返回鏈表中下一個(gè) use}elseif(ssa_op-op2_usevar){returnssa_op-op2_use_chain;}else{returnssa_op-res_use_chain;// result_use 情況}}從 phi source 遍歷 phi 使用// zend_ssa.h:277-284#defineFOREACH_PHI_USE(var,phi)do{\int_var_num(var)-ssa-vars;\zend_ssa_phi*next_phi;\for(phi(var)-phi_use_chain;phi;phinext_phi){\next_phizend_ssa_next_use_phi(ssa,_var_num,phi);// zend_ssa.h:205-218staticzend_always_inline zend_ssa_phi*zend_ssa_next_use_phi(constzend_ssa*ssa,intvar,constzend_ssa_phi*p){if(p-pi0){returnp-use_chains[0];// Pi 節(jié)點(diǎn)只有一個(gè) source}else{// 遍歷 sources 找到匹配的返回對(duì)應(yīng)的 use_chainfor(intj0;jssa-cfg.blocks[p-block].predecessors_count;j){if(p-sources[j]var){returnp-use_chains[j];}}}}優(yōu)化階段如何使用 use-def 鏈DCE 死代碼消除 (dce.c)DCE 沿 use 鏈反向 傳播活性。從 RETURN/ECHO 等必然活躍的指令出發(fā)將它們的操作數(shù)標(biāo)記為活躍再標(biāo)記操作數(shù)的定義指令為活躍如此遞歸。// dce.c:294 — 操作數(shù)入隊(duì)staticvoidadd_operands_to_worklists(...){if(ssa_op-op1_use0){if(!zend_bitset_in(instr_worklist,ssa_var[op1_use].definition)){zend_bitset_incl(instr_worklist,ssa_var[op1_use].definition);}}// op2_use 同理}// dce.c:326 — 檢查變量是否死staticboolis_var_dead(zend_ssa*ssa,intvar_num,...){// 檢查 use_chain 中是否所有 use 都是死指令// 檢查 phi_use_chain 中是否所有 phi use 都是死}具體追蹤ECHO $a 必然 active → ssa_var[5] 活躍 → 沿著 use 鏈: 1. use_chain4: OP4 活躍 (ECHO 本身) 2. ssa_var[5] 的 definition_phi 指向 BB2 的 phi → 遍歷 phi 的所有 sources [2, 4]: → ssa_var[2] 活躍, ssa_var[4] 活躍 3. ssa_var[2] 活躍 → ssa_var[2].definition 0 → OP0 活躍 → ssa_var[2] 的 phi_use_chain (作為 phi source) → 已檢查 4. ssa_var[4] 活躍 → ssa_var[4].definition 2 → OP2 活躍 5. OP0 活躍 → 但 op1_use ssa_var[0] 是 no_val (值不重要) → ssa_var[0] 不標(biāo)記活躍 (初始版本未被真正使用)結(jié)果: OP0, OP2, OP4 都活著 → 沒有死代碼SCCP 常量傳播 (sccp.c)SCCP 用 use-def 鏈的反向從 def 找 use。當(dāng) SCCP 發(fā)現(xiàn)一個(gè)變量是常量通過 replace_constant_operands() 遍歷 use 鏈把所有 use 替換為常量。// sccp.c:2377 — replace_constant_operandsstaticintreplace_constant_operands(sccp_ctx*ctx){for(intiop_array-last_var;issa-vars_count;i){if(!IS_TOP(ctx-values[i])!IS_BOT(ctx-values[i])){// 是個(gè)常量遍歷所有 use 替換FOREACH_USE(ssa-vars[i],use){try_replace_op1(ctx,oplineuse,ssa_opuse,i,ctx-values[i]);try_replace_op2(ctx,oplineuse,ssa_opuse,i,ctx-values[i]);}FOREACH_USE_END();// 也遍歷 phi_use_chainFOREACH_PHI_USE(ssa-vars[i],phi){// 在 phi 中也替換源}FOREACH_PHI_USE_END();}}}類型推斷 (zend_inference.c)類型推斷沿 SSA 指令順序處理但遇到循環(huán)時(shí)需要迭代到不動(dòng)點(diǎn)。對(duì)于每個(gè) ssa_opop1 和 op2 的 use 給出 ssa_var_info[use].type然后根據(jù)操作碼語義計(jì)算 result 類型。// zend_inference.c 中對(duì) ADD 的處理caseZEND_ADD:t1ssa-var_info[ssa_op-op1_use].type;// 查 use 的類型t2ssa-var_info[ssa_op-op2_use].type;tmpbinary_op_result_type(ssa,ZEND_ADD,t1,t2,...);UPDATE_SSA_TYPE(tmp,ssa_op-result_def);// 更新 def 的類型總結(jié)雙向鏈表 vs 單向鏈PHP 的 SSA use-def 是兩個(gè)方向的索引方向存儲(chǔ)位置用途def → use (正向)ssa_var.use_chain opN_use_chainDCE反向活性傳播、SCCP常量替換到 use 點(diǎn)use → def (反向)ssa_var.definition / ssa_var.definition_phi任何時(shí)候需要知道誰定義了這個(gè)值每個(gè)優(yōu)化都會(huì)用到鏈表為什么用頭插法逆向掃描// zend_ssa_compute_use_def_chains, line 1167for(iop_array-last-1;i0;i--){// 頭插法: 更晚的 use 在鏈表頭部op-op1_use_chainssa_vars[op-op1_use].use_chain;// 舊鏈頭變新節(jié)點(diǎn)nextssa_vars[op-op1_use].use_chaini;// 新鏈頭 當(dāng)前}逆向頭插的結(jié)果是 use 鏈按指令從后往前排列這對(duì) DCE 有利DCE 是反向傳播靠后的 use 先處理符合直覺而且不需要二次遍歷一次掃描同時(shí)建立 definition 和 use 鏈。為什么 op1_use 和 op1_def 可以同時(shí)非 -1像 $a $a 1 編譯為 ASSIGN_OP $a, 1復(fù)合賦值這條指令既讀 $a 的舊值又寫 $a 的新值。所以op1_use ssa_var[舊版本] ← 讀舊值做運(yùn)算op1_def ssa_var[新版本] ← 寫回新值這就是 SSA 的核心約定每條指令最多定義一個(gè)新的 SSA 變量號(hào)但可以讀多個(gè)舊的 SSA 變量號(hào)。 php8 use-def鏈
代碼$a10;if($cond){$a20;}echo$a;數(shù)據(jù)結(jié)構(gòu) (zend_ssa.h)整個(gè) SSA 系統(tǒng)的核心是三個(gè)結(jié)構(gòu)體zend_ssa (頂層容器) ├── cfg: zend_cfg ← 控制流圖基本塊、前驅(qū)/后繼、支配樹 ├── blocks[]: zend_ssa_block ← 每個(gè)基本塊的 phi 鏈表頭 ├── ops[]: zend_ssa_op ← 每條指令的 SSA 信息use/def 編號(hào) 鏈表 ├── vars[]: zend_ssa_var ← 每個(gè) SSA 變量的 def-use 信息 └── vars_count ← SSA 變量總數(shù)zend_ssa_op (每條指令在 SSA 中的視圖)typedefstruct_zend_ssa_op{intop1_use;// op1 讀的是哪個(gè) ssa_var (≥0) 或 -1intop2_use;// op2 讀的是哪個(gè) ssa_var (≥0) 或 -1intresult_use;// result 讀的是哪個(gè) ssa_var (≥0少見) 或 -1intop1_def;// op1 定義的是哪個(gè) ssa_var (≥0) 或 -1intop2_def;// op2 定義的是哪個(gè) ssa_var (≥0) 或 -1intresult_def;// result 定義的是哪個(gè) ssa_var (≥0) 或 -1intop1_use_chain;// 該 use 在使用鏈表中的下一個(gè) use 指令編號(hào)intop2_use_chain;intres_use_chain;}zend_ssa_op;zend_ssa_var (每個(gè) SSA 變量的元信息)typedefstruct_zend_ssa_var{intvar;// 原始變量編號(hào)CV#0, CV#1, TMP#last_var0...intscc;// 強(qiáng)連通分量intdefinition;// 定義該 ssa_var 的指令編號(hào)入口intuse_chain;// 使用該 ssa_var 的第一個(gè) use 指令編號(hào)鏈表頭zend_ssa_phi*definition_phi;// 如果是 phi 定義的指向 phizend_ssa_phi*phi_use_chain;// 該變量在 phi 中的使用列表unsignedintalias:2;// 是否可能被間接修改符號(hào)表別名等}zend_ssa_var;zend_ssa_phi (phi 函數(shù))typedefstruct_zend_ssa_phi{zend_ssa_phi*next;// 同一 BB 中的下一個(gè) phiintpi;// ≥0 表示 e-SSA Pi 節(jié)點(diǎn)來自哪個(gè)前驅(qū) BBintvar;// 原始 CV/VAR/TMP 變量號(hào)intssa_var;// 該 phi 定義的 SSA 變量編號(hào)intblock;// 所在基本塊zend_ssa_phi**use_chains;// 每個(gè) source 的使用鏈表int*sources;// phi 的源 SSA 變量號(hào)數(shù)組每個(gè)前驅(qū)一個(gè)}zend_ssa_phi;三階段構(gòu)建流程 (zend_build_ssa, zend_ssa.c:996)階段 0控制流圖 支配者樹在 SSA 構(gòu)建之前zend_build_cfg() 已經(jīng)完成了CFG: BB0 [start0, len2] (ASSIGN $a,10; JMPZ $cond,BB2) │ successors: BB1, BB2 ├─? BB1 [start2, len2] (ASSIGN $a,20; JMP BB2) │ successors: BB2 └─? BB2 [start4, len2] (ECHO $a; RETURN) successors: (exit) 支配者樹 (dominator tree): BB0 為根函數(shù)入口 BB1: idom BB0 (BB0 支配 BB1) BB2: idom BB0 (BB0 支配 BB2) BB2 的前驅(qū): BB0, BB1 (這是合并點(diǎn)) 預(yù)排序索引: BB0: level0, children→BB1→BB2 BB1: level1 BB2: level1階段 1: DFG 構(gòu)建 zend_build_dfg() def 傳播 Phi 放置 (zend_build_ssa, line 1017-1116)Step 1a: DFG 收集 def/use 集合 (zend_build_dfg, zend_dfg.c:252)遍歷每個(gè) BB 的每條指令逐條調(diào)用 _zend_dfg_add_use_def_op() (zend_dfg.c:22)BB0: OP0 ASSIGN $a, 10 → op1_typeIS_CV($a): zend_bitset_incl(use, $a) ← $a 的舊值被使用覆蓋前 → 然后 goto add_op1_def (line 213): zend_bitset_incl(def, $a) → result_def 無 BB0: use{$a} def{$a} OP1 JMPZ $cond, BB2 → op1_typeIS_CV($cond): zend_bitset_incl(use, $cond) ← 讀 $cond → 無 def BB0: use{$a, $cond} def{$a} BB1: OP2 ASSIGN $a, 20 → 同上: use{$a}, def{$a} BB1: use{$a} def{$a} OP3 JMP BB2 → 無 use, 無 def BB2: OP4 ECHO $a → op1_typeIS_CV($a): zend_bitset_incl(use, $a) BB2: use{$a} def{} OP5 RETURN 1 → IS_CONST, 無 useStep 1b: 計(jì)算 liveness (in/out) (zend_build_dfg, line 288-310)經(jīng)典的數(shù)據(jù)流不動(dòng)點(diǎn)迭代in use ∪(out - def), out ∪in(successors)一回合 BB2: out{} inuse{$a} BB1: outin(BB2){$a} inuse{$a} ∪({$a} - def{$a}) {$a} BB0: outin(BB1)∪in(BB2){$a} inuse{$a,$cond} ∪({$a} - {$a}) {$a, $cond}Step 1c: 傳播 def 確定 Phi 位置 (line 1044-1116)這是核心。算法逐條傳播 def 集合對(duì)于每個(gè) CFG 合并點(diǎn)前驅(qū)數(shù) 1 的 BB沿支配者邊往上走找到需要 phi 的變量。初始化: def_j 每個(gè) BB 的局部 def 集合 phi_j {} (空) 迭代: BB2 (predecessors_count2 1, 是合并點(diǎn)): 對(duì)每個(gè)前驅(qū) k: kBB0: iBB0, i ! idom(BB2)BB0? 否 → 停止 (BB0 直接支配 BB2) kBB1: iBB1, i ! idom(BB2)BB0? 是 → phi_j | phi_j ∩ def(BB1) ∩ in(BB2) → phi(BB2) {} ∩ {$a} ∩ {$a} {} → 然后 i idom(BB1) BB0 idom(BB2) → 停止 首次迭代 phi_2 {}全都滿足 → 不變更新 def_2 的 phi 部分 但是: def(BB0){$a}, def(BB1){$a}, in(BB2){$a} 實(shí)際算法在 line 1062 用 union_with_intersection: phi_2 | phi_2 ∩ def(i) ∩ in(BB2) 等一下這個(gè)邏輯是: phi_j U_{predecessor k} (phi_j ∩ def(i) ∩ in(j)) 對(duì)于所有在 idom 之上的 i。當(dāng) i ! idom(j) 時(shí)繼續(xù)上行。 首輪: phi_2 {} → 交集為空 → phi_2 {} 但 zend_bitset_subset(phi_2, def_2, set_size)? def(BB2) {}, phi_2 {} → 是子集 → changed0 ... 實(shí)際上首輪不變但問題在于 BB0 的 def{$a} 沒到達(dá) BB2 覆蓋 def(BB2)... 實(shí)際上這個(gè)算法有問題需要第二輪。讓我簡(jiǎn)化解釋...實(shí)際上 PHP 的算法更精妙。在標(biāo)準(zhǔn)教科書法中phi 放置dominance frontier 上。PHP 采用一種變體foreach block j with1predecessors:foreach predecessor k:ikwhilei!idom(j):phi_j|def_i ∩ in_j// 在非直接支配者的路徑上任何被定義且活躍的變量需要 phiiidom(i)實(shí)際結(jié)果簡(jiǎn)化后的 PHP 算法對(duì)于 BB2 (predecessorsBB0, BB1, idomBB0): 前驅(qū) BB0: iBB0 idom → 不進(jìn)入 while 前驅(qū) BB1: iBB1 ! idom → 進(jìn)入 while phi(BB2) | def(BB1) ∩ in(BB2) | {$a} ∩ {$a} | {$a} i idom(BB1) BB0 idom(BB2) → 退出 結(jié)果: phi(BB2) {$a} def(BB2) {} → phi ? def → def(BB2) | phi → def(BB2) {$a} changed 1 → 再次迭代 第二次迭代: phi(BB2) {$a}, def(BB0) {$a}, def(BB1) {$a} phi | phi ∩ def(BB1) ∩ in(BB2) {$a} ∩ {$a} ∩ {$a} {$a} 不變 → def(BB2)已經(jīng)包含 {$a} → 沒有新phi → 收斂在合并點(diǎn)創(chuàng)建 phi 指令 (line 1083-1116)在 BB2 中為 $a 創(chuàng)建 phi: phi-pi -1 (普通 phi, 不是 e-SSA Pi) phi-var 0 (CV#0, 即 $a) phi-ssa_var -1 (renaming 階段分配) phi-sources[0] -1 (來自 BB0 前驅(qū), 待填充) phi-sources[1] -1 (來自 BB1 前驅(qū), 待填充) phi-block 2階段 2: 變量重命名 (zend_ssa_rename, line 914)這是經(jīng)典 Cytron 算法的 renaming pass。按照支配樹的前序遍歷進(jìn)行。關(guān)鍵數(shù)據(jù)結(jié)構(gòu)var[]// var[原始var_num] 當(dāng)前活躍的 SSA 變量號(hào)// 初始值: var[0]0 ($a), var[1]1 ($cond) 等// 初始 for CV: var[i] i (line 1128)// 對(duì)于 TMP_VAR: var[i] -1 (line 1125)遞歸遍歷支配樹 (使用 worklist 模擬遞歸line 914-988)進(jìn)入 BB0 (n0): // 1. 處理 BB0 的 phi (BB0 沒有 phi) // 2. 遍歷 BB0 的指令 (zend_ssa_rename_in_block, line 820) OP0 ASSIGN $a, 10 → op1_typeIS_CV → op1_use var[0] 0 (ssa_var[0]) ← 讀 $a 的舊值 → opcodeZEND_ASSIGN → goto add_op1_def: op1_def ssa_vars_count 2 ← 創(chuàng)建新的 ssa_var var[0] 2 ← 更新 $a 的活躍版本 ssa_vars_count → 3 → ssa_ops[0]: {op1_use:0, op1_def:2} OP1 JMPZ $cond, BB2 → op1_typeIS_CV → op1_use var[1] 1 (ssa_var[1]) → result_typeIS_TMP_VAR → result_def ssa_vars_count 3 var[last_var0] 3 ← TMP 變量也需要 rename ssa_vars_count → 4 → ssa_ops[1]: {op1_use:1, result_def:3} // 3. 填充后繼 BB 的 phi sources BB0 的后繼: BB1, BB2 對(duì)于 BB2 的 phi $a (ssa_var 尚為 -1): phi-sources[0] var[0] 2 ← 填充 BB0→BB2 邊上的值 // 4. 遞歸處理子節(jié)點(diǎn) 先 BB1 (level1), 再 BB2 (level1) 進(jìn)入 BB1 (n1): // 1. 無 phi // 2. 遍歷指令 OP2 ASSIGN $a, 20 → op1_use var[0] 2 ← 當(dāng)前 $a 活躍版本仍是 ssa_var[2]來自 BB0 → 等等! 這是 ASSIGN, no_val 標(biāo)注: zend_ssa_is_no_val_use(line 221) 返回 true → op1_use 存在但被標(biāo)記為 no_val (值不重要) → add_op1_def: op1_def ssa_vars_count 4 ← 新版本 var[0] 4 ← $a 的活躍版本更新為 4 → ssa_ops[2]: {op1_use:2, op1_def:4} OP3 JMP BB2 → 無 use, 無 def // 3. 填充后繼 BB2 的 phi sources 對(duì)于 BB2 的 phi $a: phi-sources[1] var[0] 4 ← 填充 BB1→BB2 邊上的值 // 4. BB1 沒有子節(jié)點(diǎn) (leaf) → 直接回溯 var[0] 恢復(fù)為 2 (退出 BB1 時(shí)回滾 var 數(shù)組) 進(jìn)入 BB2 (n2, BB0 的另一個(gè)子節(jié)點(diǎn)): // 1. 處理 BB2 的 phi (zend_ssa_rename_in_block, line 829) phi for $a: phi-ssa_var ssa_vars_count 5 ← 為 phi 分配 ssa_var 編號(hào) var[0] 5 ← $a 的活躍版本現(xiàn)在變成 phi 的結(jié)果 OP4 ECHO $a → op1_typeIS_CV → op1_use var[0] 5 ← 使用 phi 結(jié)果! → ssa_ops[4]: {op1_use:5} OP5 RETURN 1 → IS_CONST → 無 SSA 參與 // 3. BB2 無后繼 → 不再填充 phi sources // 4. 無子節(jié)點(diǎn) → 回溯構(gòu)建 use-def 鏈表 (zend_ssa_compute_use_def_chains, line 1144)這是最關(guān)鍵的一步。從后往前掃描所有指令為每個(gè)被使用的 ssa_var 建立從 def 到所有 use 的單鏈表。重命名后的 ssa_ops (opN_use / opN_def):OP0 ASSIGN: op1_use0, op1_def2 ssa_ops[0] OP1 JMPZ: op1_use1, result_def3 ssa_ops[1] OP2 ASSIGN: op1_use2, op1_def4 ssa_ops[2] OP3 JMP: (無 SSA) ssa_ops[3] OP4 ECHO: op1_use5 ssa_ops[4] OP5 RETURN: (無 SSA) ssa_ops[5]BB2 phi: ssa_var5, sources[2, 4] (來自 BB0→2, BB1→4)逆向掃描建立鏈表 (line 1167-1193)// ssa_vars 每位初始化為:// var -1// scc -1// definition -1// use_chain -1 ← 鏈表頭-1 表示空for(iop_array-last-1;i0;i--){// 從最后的指令往前zend_ssa_op*opssa-opsi;// 鏈入 use 鏈表 (頭插法)if(op-op1_use0){op-op1_use_chainssa_vars[op-op1_use].use_chain;// 保存舊鏈頭ssa_vars[op-op1_use].use_chaini;// 新鏈頭 當(dāng)前指令}// 對(duì) op2_use, result_use 同理// 設(shè)置 definition 指針if(op-op1_def0){ssa_vars[op-op1_def].definitioni;// 指向定義指令}// 對(duì) op2_def, result_def 同理}逆向掃描的執(zhí)行過程i5 OP5 RETURN: 無 use, 無 def → 無事 i4 OP4 ECHO: op1_use5 → ssa_ops[4].op1_use_chain ssa_vars[5].use_chain -1 → ssa_vars[5].use_chain 4 ← ssa_var[5] 被 OP4 使用 ssa_vars[5]: use_chain 4 i3 OP3 JMP: 無 i2 OP2 ASSIGN: op1_use2, op1_def4 → op1_use_chain ssa_vars[2].use_chain -1 → ssa_vars[2].use_chain 2 ← ssa_var[2] 被 OP2(op1) 使用 → ssa_vars[4].definition 2 ← ssa_var[4] 由 OP2 定義 ssa_vars[2]: use_chain 2 ssa_vars[4]: definition 2 i1 OP1 JMPZ: op1_use1, result_def3 → op1_use_chain ssa_vars[1].use_chain -1 → ssa_vars[1].use_chain 1 ← ssa_var[1] 被 OP1(op1) 使用 → ssa_vars[3].definition 1 ← ssa_var[3] 由 OP1 定義 ssa_vars[1]: use_chain 1 ssa_vars[3]: definition 1 i0 OP0 ASSIGN: op1_use0, op1_def2 → op1_use_chain ssa_vars[0].use_chain -1 → ssa_vars[0].use_chain 0 ← ssa_var[0] 被 OP0(op1) 使用 → ssa_vars[2].definition 0 ← ssa_var[2] 由 OP0 定義 ssa_vars[0]: use_chain 0 ssa_vars[2]: definition 0 ssa_vars[2]: use_chain 2 (之前已有)最后處理 phi 的 use 鏈 (line 1196-1210)for(i0;issa-cfg.blocks_count;i){zend_ssa_phi*phissa-blocks[i].phis;while(phi){phi-blocki;ssa_vars[phi-ssa_var].varphi-var;ssa_vars[phi-ssa_var].definition_phiphi;// phi 是定義// ... 填充 phi 到 source 的使用鏈表phiphi-next;}}// BB2 的 phi: sources[2, 4], ssa_var5// ssa_vars[5].definition_phi phi// ssa_vars[5].definition -1 (不是指令定義的是 phi 定義的)// ssa_vars[2] 的 phi_use_chain 中包含此 phi (ssa_var[2] 是這個(gè) phi 的一個(gè) source)// ssa_vars[4] 的 phi_use_chain 中包含此 phi最終完整的 use-def 鏈ssa_var[0]: $a 的初始版本 (入口值) definition -1 (函數(shù)入口無定義指令) use_chain 0 ──? OP0 (ASSIGN, op1_use, no_val) ssa_var[1]: $cond 的初始版本 definition -1 use_chain 1 ──? OP1 (JMPZ, op1_use) ssa_var[2]: $a 的第 2 個(gè)版本 (10) definition 0 ← 由 OP0 (ASSIGN $a, 10) 定義 use_chain 2 ──? OP2 (ASSIGN, op1_use, no_val) phi_use_chain ──? phi in BB2, source[0] ssa_var[3]: JMPZ 結(jié)果 (條件跳轉(zhuǎn)的布爾值) definition 1 use_chain -1 (未使用) ssa_var[4]: $a 的第 3 個(gè)版本 (20) definition 2 ← 由 OP2 (ASSIGN $a, 20) 定義 use_chain -1 (通過 phi 使用不在指令鏈表中) phi_use_chain ──? phi in BB2, source[1] ssa_var[5]: phi($a, BB0→2, BB1→4) 的結(jié)果 definition_phi phi in BB2 definition -1 use_chain 4 ──? OP4 (ECHO, op1_use)圖示化:遍歷 use-def 鏈的 API從 def 遍歷所有 use#defineFOREACH_USE(var,use)do{\int_var_num(var)-ssa-vars,next;\for(use(var)-use_chain;use0;usenext){\nextzend_ssa_next_use(ssa-ops,_var_num,use);// zend_ssa.h:193-203 — 輔助函數(shù)staticzend_always_inlineintzend_ssa_next_use(constzend_ssa_op*ssa_op,intvar,intuse){ssa_opuse;// 指針移到 use 所在的 ssa_opif(ssa_op-op1_usevar){returnssa_op-op1_use_chain;// 返回鏈表中下一個(gè) use}elseif(ssa_op-op2_usevar){returnssa_op-op2_use_chain;}else{returnssa_op-res_use_chain;// result_use 情況}}從 phi source 遍歷 phi 使用// zend_ssa.h:277-284#defineFOREACH_PHI_USE(var,phi)do{\int_var_num(var)-ssa-vars;\zend_ssa_phi*next_phi;\for(phi(var)-phi_use_chain;phi;phinext_phi){\next_phizend_ssa_next_use_phi(ssa,_var_num,phi);// zend_ssa.h:205-218staticzend_always_inline zend_ssa_phi*zend_ssa_next_use_phi(constzend_ssa*ssa,intvar,constzend_ssa_phi*p){if(p-pi0){returnp-use_chains[0];// Pi 節(jié)點(diǎn)只有一個(gè) source}else{// 遍歷 sources 找到匹配的返回對(duì)應(yīng)的 use_chainfor(intj0;jssa-cfg.blocks[p-block].predecessors_count;j){if(p-sources[j]var){returnp-use_chains[j];}}}}優(yōu)化階段如何使用 use-def 鏈DCE 死代碼消除 (dce.c)DCE 沿 use 鏈反向 傳播活性。從 RETURN/ECHO 等必然活躍的指令出發(fā)將它們的操作數(shù)標(biāo)記為活躍再標(biāo)記操作數(shù)的定義指令為活躍如此遞歸。// dce.c:294 — 操作數(shù)入隊(duì)staticvoidadd_operands_to_worklists(...){if(ssa_op-op1_use0){if(!zend_bitset_in(instr_worklist,ssa_var[op1_use].definition)){zend_bitset_incl(instr_worklist,ssa_var[op1_use].definition);}}// op2_use 同理}// dce.c:326 — 檢查變量是否死staticboolis_var_dead(zend_ssa*ssa,intvar_num,...){// 檢查 use_chain 中是否所有 use 都是死指令// 檢查 phi_use_chain 中是否所有 phi use 都是死}具體追蹤ECHO $a 必然 active → ssa_var[5] 活躍 → 沿著 use 鏈: 1. use_chain4: OP4 活躍 (ECHO 本身) 2. ssa_var[5] 的 definition_phi 指向 BB2 的 phi → 遍歷 phi 的所有 sources [2, 4]: → ssa_var[2] 活躍, ssa_var[4] 活躍 3. ssa_var[2] 活躍 → ssa_var[2].definition 0 → OP0 活躍 → ssa_var[2] 的 phi_use_chain (作為 phi source) → 已檢查 4. ssa_var[4] 活躍 → ssa_var[4].definition 2 → OP2 活躍 5. OP0 活躍 → 但 op1_use ssa_var[0] 是 no_val (值不重要) → ssa_var[0] 不標(biāo)記活躍 (初始版本未被真正使用)結(jié)果: OP0, OP2, OP4 都活著 → 沒有死代碼SCCP 常量傳播 (sccp.c)SCCP 用 use-def 鏈的反向從 def 找 use。當(dāng) SCCP 發(fā)現(xiàn)一個(gè)變量是常量通過 replace_constant_operands() 遍歷 use 鏈把所有 use 替換為常量。// sccp.c:2377 — replace_constant_operandsstaticintreplace_constant_operands(sccp_ctx*ctx){for(intiop_array-last_var;issa-vars_count;i){if(!IS_TOP(ctx-values[i])!IS_BOT(ctx-values[i])){// 是個(gè)常量遍歷所有 use 替換FOREACH_USE(ssa-vars[i],use){try_replace_op1(ctx,oplineuse,ssa_opuse,i,ctx-values[i]);try_replace_op2(ctx,oplineuse,ssa_opuse,i,ctx-values[i]);}FOREACH_USE_END();// 也遍歷 phi_use_chainFOREACH_PHI_USE(ssa-vars[i],phi){// 在 phi 中也替換源}FOREACH_PHI_USE_END();}}}類型推斷 (zend_inference.c)類型推斷沿 SSA 指令順序處理但遇到循環(huán)時(shí)需要迭代到不動(dòng)點(diǎn)。對(duì)于每個(gè) ssa_opop1 和 op2 的 use 給出 ssa_var_info[use].type然后根據(jù)操作碼語義計(jì)算 result 類型。// zend_inference.c 中對(duì) ADD 的處理caseZEND_ADD:t1ssa-var_info[ssa_op-op1_use].type;// 查 use 的類型t2ssa-var_info[ssa_op-op2_use].type;tmpbinary_op_result_type(ssa,ZEND_ADD,t1,t2,...);UPDATE_SSA_TYPE(tmp,ssa_op-result_def);// 更新 def 的類型總結(jié)雙向鏈表 vs 單向鏈PHP 的 SSA use-def 是兩個(gè)方向的索引方向存儲(chǔ)位置用途def → use (正向)ssa_var.use_chain opN_use_chainDCE反向活性傳播、SCCP常量替換到 use 點(diǎn)use → def (反向)ssa_var.definition / ssa_var.definition_phi任何時(shí)候需要知道誰定義了這個(gè)值每個(gè)優(yōu)化都會(huì)用到鏈表為什么用頭插法逆向掃描// zend_ssa_compute_use_def_chains, line 1167for(iop_array-last-1;i0;i--){// 頭插法: 更晚的 use 在鏈表頭部op-op1_use_chainssa_vars[op-op1_use].use_chain;// 舊鏈頭變新節(jié)點(diǎn)nextssa_vars[op-op1_use].use_chaini;// 新鏈頭 當(dāng)前}逆向頭插的結(jié)果是 use 鏈按指令從后往前排列這對(duì) DCE 有利DCE 是反向傳播靠后的 use 先處理符合直覺而且不需要二次遍歷一次掃描同時(shí)建立 definition 和 use 鏈。為什么 op1_use 和 op1_def 可以同時(shí)非 -1像 $a $a 1 編譯為 ASSIGN_OP $a, 1復(fù)合賦值這條指令既讀 $a 的舊值又寫 $a 的新值。所以op1_use ssa_var[舊版本] ← 讀舊值做運(yùn)算op1_def ssa_var[新版本] ← 寫回新值這就是 SSA 的核心約定每條指令最多定義一個(gè)新的 SSA 變量號(hào)但可以讀多個(gè)舊的 SSA 變量號(hào)。