15-745 © Seth Copen Goldstein 2001-4 115-745SSACopyright © Seth Copen Goldstein 2001-515-745 © Seth Copen Goldstein 2001-4 2Def-Use chains are expensivefoo(int i, int j) {…switch (i) {case 0: x=3;break;case 1: x=1; break;case 2: x=6; break;case 3: x=7; break;default: x = 11;}switch (j) {case 0: y=x+7; break;case 1: y=x+4; break; case 2: y=x-2; break;case 3: y=x+1; break;default: y=x+9;}…15-745 © Seth Copen Goldstein 2001-4 3Def-Use chains are expensivefoo(int i, int j) {…switch (i) {case 0: x=3;case 1: x=1;case 2: x=6;case 3: x=7;default: x = 11;}switch (j) {case 0: y=x+7;case 1: y=x+4; case 2: y=x-2;case 3: y=x+1;default: y=x+9;}…In general,N defsM uses⇒ O(NM) space and timeA solution is to limit each var to ONE def site15-745 © Seth Copen Goldstein 2001-4 4Def-Use chains are expensivefoo(int i, int j) {…switch (i) {case 0: x=3; break;case 1: x=1; break;case 2: x=6;case 3: x=7;default: x = 11;}x1 is one of the above x’sswitch (j) {case 0: y=x1+7;case 1: y=x1+4; case 2: y=x1-2;case 3: y=x1+1;default: y=x1+9;}…A solution is to limit each var to ONE def site15-745 © Seth Copen Goldstein 2001-4 5Advantages of SSA• Makes du-chains explicit• Makes dataflow analysis easier• Improves register allocation– Automatically builds Webs– Makes building interference graphs easier• For most programs reduces space/time requirements15-745 © Seth Copen Goldstein 2001-4 6SSA• Static single assignment is an IR where every variable is assigned a value at most once in the program text• Easy for a basic block:– assign to a fresh variable at each stmt.– Each use uses the most recently defined var.– (Similar to Value Numbering)15-745 © Seth Copen Goldstein 2001-4 7Straight-line SSAa ← x + yb ← a + xa ← b + 2c ← y + 1a ← c + a15-745 © Seth Copen Goldstein 2001-4 8Straight-line SSAa ← x + yb ← a + xa ← b + 2c ← y + 1a ← c + aa1← x + yb1← a1+ xa2← b1+ 2c1← y + 1a3← c1+ a215-745 © Seth Copen Goldstein 2001-4 9SSA• Static single assignment is an IR where every variable is assigned a value at most once in the program text• Easy for a basic block:– assign to a fresh variable at each stmt.– Each use uses the most recently defined var.– (Similar to Value Numbering)• What about at joins in the CFG?15-745 © Seth Copen Goldstein 2001-4 10a1← x + yb1← a1+ xMerging at Joinsa ← b + 2c ← y + 1c ← 12if (i) {a ← x + yb ← a + x} else {a ← b + 2c ← y + 1}a ← c + ac1← 12if (i)a4← c?+ a?15-745 © Seth Copen Goldstein 2001-4 11SSA• Static single assignment is an IR where every variable is assigned a value at most once in the program text• Easy for a basic block:– assign to a fresh variable at each stmt.– Each use uses the most recently defined var.– (Similar to Value Numbering)• What about at joins in the CFG?– Use a notional fiction: A Φ function15-745 © Seth Copen Goldstein 2001-4 12Merging at Joinsa2← b + 2c2← y + 1c1← 12if (i)a1← x + yb1← a1+ xa3← Φ(a1,a2)c3← Φ(c1,c2)b2← Φ(b1, ?)a4← c3+ a315-745 © Seth Copen Goldstein 2001-4 13The Φ function• Φ merges multiple definitions along multiple control paths into a single definition.• At a BB with p predecessors, there are p arguments to the Φ function.xnew← Φ(x1, x1, x1, … , xp)• How do we choose which xito use?– We don’t really care!– If we care, use moves on each incoming edge15-745 © Seth Copen Goldstein 2001-4 14“Implementing” Φa2← b + 2c2← y + 1a3← a2c3← c2c1← 12if (i)a1← x + yb1← a1+ xa3← a1c3← c1a3← Φ(a1,a2)c3← Φ(c1,c2)a4← c3+ a315-745 © Seth Copen Goldstein 2001-4 15Trivial SSA• Each assignment generates a fresh variable.• At each join point insert Φ functions for all live variables.y ← xy ← 2z ← y + xx ← 1y1← x1y2← 2x2← Φ(x1,x1)y3← Φ(y1,y2)z1← y3+ x2x1← 1Way too many Φfunctions inserted.15-745 © Seth Copen Goldstein 2001-4 16Minimal SSA• Each assignment generates a fresh variable.• At each join point insert Φ functions for all variables with multiple outstanding defs.y ← xy ← 2z ← y + xx ← 1y1← x1y2← 2y3← Φ(y1,y2)z1← y3+ x1x1← 115-745 © Seth Copen Goldstein 2001-4 17Another Examplea ← 0b ← a + 1c ← c + ba ← b * 2a < Nreturn c15-745 © Seth Copen Goldstein 2001-4 18Another Examplea ← 0b ← a + 1c ← c + ba ← b * 2a < Nreturn ca1← 0a3← Φ(a1,a2)c3← Φ(c1,c2)b2← a3+ 1c2← c3+ b2a2← b2* 2a2< Nreturn c2Notice use of c115-745 © Seth Copen Goldstein 2001-4 19Lets optimize the following:i=1;j=1;k=0;while (k<100) {if (j<20) {j=i;k++;} else {j=k;k+=2;}}return j;i ← 1j ← 1k ← 0k < 100?j < 20? return jj ← ik ← k + 1j ← kk ← k + 2124657315-745 © Seth Copen Goldstein 2001-4 20First, turn into SSAi ← 1j ← 1k ← 0k < 100?j < 20? return jj ← ik ← k + 1j ← kk ← k + 21246573i ← 1j ← 1k ← 0k < 100?j < 20? return jj ← ik ← k + 1j ← kk ← k + 2124657315-745 © Seth Copen Goldstein 2001-4 21Properties of SSAi1← 1j1← 1k1← 0j2← Φ(j4,j1)k2← Φ(k4,k1)k2< 100?j2< 20? return j2j3← i1k3← k2+ 1j5← k2k5← k2+ 2j4← Φ(j3,j5)k4← Φ(k3,k5)1246573• Only 1 assignment per variable• definitions dominate uses• Can we use this to help with constant propagation?15-745 © Seth Copen Goldstein 2001-4 22Constant Propagation•If “v ← c”, replace all uses of v with c•If “v ← Φ(c,c,c)” replace all uses of v with cW <- list of all defswhile !W.isEmpty {Stmt S <- W.removeOneif S has form “v <- Φ(c,…,c)”replace S with V <- cif S has form “v <- c” thendelete Sforeach stmt U that uses v,replace v with c in UW.add(U)}15-745 © Seth Copen Goldstein 2001-4 23Other stuff we can do?• Copy propagationdelete “x ←Φ(y)” and replace all x with ydelete “x ← y” and replace all x with y•Constant Folding(Also, constant conditions too!)• Unreachable CodeRemember to delete all edges from unreachable block15-745 © Seth Copen Goldstein 2001-4 24Constant Propagationi1← 1j1← 1k1← 0j2← Φ(j4,j1)k2← Φ(k4,k1)k2< 100?j2< 20? return j2j3← i1k3← k2+ 1j5← k2k5← k2+ 2j4← Φ(j3,j5)k4← Φ(k3,k5)124657315-745 © Seth Copen Goldstein 2001-4 25Constant Propagationi1← 1j1← 1k1← 0j2← Φ(j4,1)k2← Φ(k4,k1)k2< 100?j2< 20? return j2j3← 1k3← k2+ 1j5← k2k5← k2+ 2j4← Φ(j3,j5)k4← Φ(k3,k5)124657315-745 © Seth Copen Goldstein 2001-4 26Constant Propagationi1← 1j1← 1k1← 0j2← Φ(j4,1)k2← Φ(k4,k1)k2< 100?j2< 20?
View Full Document
Unlocking...