代码优化课件.ppt

9.3全局數據流分析介紹in[B] out[B]B100000001110000B211101110011110B300111000001110B400111100010111gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m?1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j?1d6:a:=u2B39.3全局數據流分析介紹in[B] out[B]B100000001110000B211101110011110B300111100001110B400111100010111gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m?1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j?1d6:a:=u2B39.3全局數據流分析介紹in[B]=?out[P] P是B的前驅out[B]=gen[B]?(in[B]?kill[B]) 到達-定值方程是正向的方程，另一類數據流方程是反向的到達-定值方程的合流算符是求並集，另一類數據流方程的合流算符是求交集到達-定值的資訊存儲為引用-定值鏈（或叫ud鏈），指能到達變數的某個引用的所有定值9.3全局數據流分析介紹9.3.3可用運算式x:=y+z x:=y+z x:=y+z. . .. y:=… z:=… . . .p p py+z在p點 y+z在p點 y+z在p點可用 不可用 不可用9.3全局數據流分析介紹t1:=4*i?t2:=4*iB1B2B3t1:=4*ii:=t0:=4*it2:=4*iB1B2B39.3全局數據流分析介紹計算可用運算式的方程out[B]=e_gen[B]?(in[B]?e_kill[B])in[B]= ?out[P] （B不是初始塊） P是B的前驅in[B1]=? （B1是初始塊）和到達-定值方程的區別初始塊的in處理為特殊情況合流算符是交集運算而不是並集運算到達-定值求最小解，可用運算式求最大解9.3全局數據流分析介紹in集合的不同初值比較in[B2]=out[B1]?out[B2]（以B2為例） out[B2]=G?(in[B2]?K)B1B2Oj+1=G?(Ij?K)Ij+1=out[B1]?Oj+1I0=? I0=UO1=G O1=U?KI1=out[B1]?G I1=out[B1]?KO2=G O2=G?(out[B1]?K)9.3全局數據流分析介紹9.3.4活躍變數分析x的值在p點開始的路徑上被引用，我們說x在p點活躍，否則稱x在p點是死亡的in[B]：開始點的活躍變數集合out[B]：結束點的活躍變數集合def[B]：塊B中有定值且該定值前無引用的變數集use[B]：塊