復試編譯原理課件chapter10

第十章代碼優(yōu)化SchoolofComputerScience&TechnologyHarbinInstituteofTechnology重點：代碼優(yōu)化的任務，局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化的基本方法。

難點：控制流分析，數(shù)據流分析。

2024/3/52第10章

代碼優(yōu)化10.1優(yōu)化的種類10.2控制流分析10.3數(shù)據流分析10.4局部優(yōu)化10.5循環(huán)優(yōu)化10.6全局優(yōu)化10.6本章小結2024/3/53第10章

代碼優(yōu)化代碼優(yōu)化就是為了提高目標程序的效率，對程序進行等價變換，亦即在保持功能不變的前提下，對源程序進行合理的變換，使得目標代碼具有更高的時間效率和/或空間效率。空間效率和時間效率有時是一對矛盾，有時不能兼顧。優(yōu)化的要求：必須是等價變換(保持功能)為優(yōu)化的努力必須是值得的。有時優(yōu)化后的代碼的效率反而會下降。2024/3/54代碼優(yōu)化程序的結構控制流分析的主要目的是分析出程序的循環(huán)結構。循環(huán)結構中的代碼的效率是整個程序的效率的關鍵。數(shù)據流分析進行數(shù)據流信息的收集，主要是變量的值的獲得和使用情況的數(shù)據流信息。到達-定義分析;活躍變量分析;可用表達式分析.代碼變換:根據上面的分析,對中間代碼進行等價變換.控制流分析數(shù)據流分析代碼變換2024/3/5510.1優(yōu)化的種類機器相關性機器相關優(yōu)化：寄存器優(yōu)化，多處理器優(yōu)化，特殊指令優(yōu)化，無用指令消除等。機器無關優(yōu)化：優(yōu)化范圍局部優(yōu)化：單個基本塊范圍內的優(yōu)化，常量合并優(yōu)化，公共子表達式刪除，計算強度削弱和無用代碼刪除。全局優(yōu)化：主要是基于循環(huán)的優(yōu)化：循環(huán)不變優(yōu)化，歸納變量刪除，計算強度削減。優(yōu)化語言級優(yōu)化語言級：針對中間代碼，針對機器語言。2024/3/56程序例子本節(jié)所用的例子i=m

1;j=n;v=a[n]; (1)i:=m

1while(1){ (2)j:=ndoi=i+1;while(a[i]<v); (3)t1:=4*ndoj=j

1;while(a[j]>v); (4)v:=a[t1]if(i>=j)break; (5)i:=i+1x=a[i];a[i]=a[j];a[j]=x; (6)t2:=4*i} (7)t3:=a[t2]x=a[i];a[i]=a[n];a[n]=x; (8)ift3<vgoto(5)2024/3/57程序例子本節(jié)所用的例子i=m

1;j=n;v=a[n]; (9)j:=j

1while(1){ (10)t4:=4*jdoi=i+1;while(a[i]<v); (11)t5:=a[t4] doj=j

1;while(a[j]>v);(12)ift5>vgoto(9)if(i>=j)break; (13)ifi>=jgoto(23)x=a[i];a[i]=a[j];a[j]=x; (14)t6:=4*i} (15)x:=a[t6]x=a[i];a[i]=a[n];a[n]=x;... 2024/3/58流圖i:=m

1j:=nt1:=4*nv:=a[t1]i:=i+1t2:=4*it3:=a[t2]ift3<vgotoB2B1B2j:=j

1t4:=4*jt5:=a[t4]ift5>vgotoB3ifi>=jgotoB6B4B3B5B62024/3/5910.1.1公共子表達式刪除局部公共子表達式B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*it8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB22024/3/51010.1.1公共子表達式刪除局部公共子表達式B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*i

t8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB22024/3/51110.1.1公共子表達式刪除局部公共子表達式B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*i

t8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB2t6:=4*ix:=a[t6]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgotoB22024/3/51210.1.1公共子表達式刪除全局公共子表達式B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*it8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB2t6:=4*ix:=a[t6]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgotoB22024/3/51310.1.1公共子表達式刪除全局公共子表達式B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*it8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB2t6:=4*ix:=a[t6]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgotoB2x:=a[t2]t9:=a[t4]a[t2]:=t9a[t4]:=xgotoB22024/3/51410.1.1公共子表達式刪除B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*i

t8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB2t6:=4*ix:=a[t6]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgotoB2x:=a[t2]t9:=a[t4]a[t2]:=t9a[t4]:=xgotoB22024/3/51510.1.1公共子表達式刪除B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*it8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB2t6:=4*ix:=a[t6]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgotoB2x:=a[t2]t9:=a[t4]a[t2]:=t9a[t4]:=xgotoB2x:=t3a[t2]:=t5a[t4]:=xgotoB22024/3/51610.1.1公共子表達式刪除B6x=a[i];a[i]=a[n];a[n]=x;t11:=4*ix:=a[t11]t12:=4*it13:=4*nt14:=a[t13]a[t12]:=t14t15:=4*na[t15]:=xx:=t3t14:=a[t1]a[t2]:=t14a[t1]:=x2024/3/51710.1.1公共子表達式刪除B6x=a[i];a[i]=a[n];a[n]=x;a[t1]能否作為公共子表達式？t11:=4*ix:=a[t11]t12:=4*it13:=4*nt14:=a[t13]a[t12]:=t14t15:=4*na[t15]:=xx:=t3t14:=a[t1]a[t2]:=t14a[t1]:=x2024/3/51810.1.1公共子表達式刪除i:=m

1j:=nt1:=4*nv:=a[t1]i:=i+1t2:=4*it3:=a[t2]ift3<vgotoB2B1B2j:=j

1t4:=4*jt5:=a[t4]ift5>vgotoB3ifi>=jgotoB6B4B3B5B6把a[t1]作為公共子表達式是不穩(wěn)妥的：控制離開B1進入B6之前可能進入B5，而B5有對a的賦值

2024/3/51910.1.2復制傳播

形如f:=g的賦值語句叫做復制語句優(yōu)化過程中會大量引入復制t:=d+ea:=t

刪除局部公共子表達式期間引進復制t:=d+eb:=tc:=tc:=d+eb:=d+ea:=d+e2024/3/52010.1.2復制傳播復制傳播變換的思想是在復制語句f:=g之后盡可能用g代替f復制傳播變換本身并不是優(yōu)化，但它給其它優(yōu)化帶來機會無用代碼刪除x:=t3a[t2]:=t5a[t4]:=

t3gotoB2x:=t3a[t2]:=t5a[t4]:=xgotoB22024/3/52110.1.3無用代碼刪除無用代碼是指計算結果以后不被引用的語句一些優(yōu)化變換可能會引入無用代碼例：debug:=true; debug:=false;... 測試后改成...if(debug)print… if(debug)print…2024/3/52210.1.3無用代碼刪除無用代碼是指計算結果以后不被引用的語句一些優(yōu)化變換可能會引入無用代碼例：復制傳播可能會引入無用代碼x:=t3a[t2]:=t5a[t4]:=t3gotoB2a[t2]:=t5a[t4]:=t3gotoB22024/3/52310.1.4代碼外提結果獨立于循環(huán)執(zhí)行次數(shù)的表達式稱為循環(huán)不變計算。如果將循環(huán)不變計算從循環(huán)中移出到循環(huán)的前面，將會減少循環(huán)執(zhí)行的代碼總數(shù)，大大提高代碼的執(zhí)行效率。這種與循環(huán)有關的優(yōu)化方法稱為代碼外提。例如，下面的while語句中，1imit-2就是循環(huán)不變計算。while(i<=limit-2){/*假設循環(huán)體中的語句不改變limit的值*/}代碼外提將生成如下的等價語句：t:=limit-2;while(i<=t){/*假設循環(huán)體中的語句不改變limit或t*/}2024/3/52410.1.5強度削弱實現(xiàn)同樣的運算可以有多種方式。用計算較快的運算代替較慢的運算。x2 變成 x*x。2*x或2.0*x 變成 x+xx/2 變成 x*0.5anxn+an-1xn-1+…+a1x+a0變成

((…(anx+an-1)x+an-2)…)x+a1)x+a02024/3/52510.1.5強度削弱圖10.6將強度削弱應用到塊B3中的4*j2024/3/52610.1.5歸納變量刪除在圍繞B3的循環(huán)的每次迭代中，j和t4的值總是同步變化，每次j的值減l，t4的值就減4，這是因為4*j賦給了t4，我們將這樣的變量稱為歸納變量如果循環(huán)中存在兩個或更多的歸納變量，也許可以只保留一個，而去掉其余的，以便提高程序的運行效率。2024/3/52710.1.5歸納變量刪除圖10.7歸納變量刪除后的流圖2024/3/52810.2控制流分析為了對程序進行優(yōu)化，尤其是對循環(huán)進行優(yōu)化，必須首先分析程序中的控制流程，以便找出程序中的循環(huán)結構，這是控制流分析的主要任務。為此，首先需要將程序劃分為基本塊集合并轉換成流圖，然后再從流圖中找出循環(huán)。2024/3/52910.2.1基本塊基本塊(basicblock)是一個連續(xù)的語句序列，控制流從它的開始進入，并從它的末尾離開，中間不存在中斷或分支(末尾除外)。下面的三地址碼序列就形成了一個基本塊：t1:＝a*at2:＝a*bt3:＝2*t2t4:＝t1+t3t5:＝b*bt6:＝t4+t52024/3/530基本塊的劃分算法算法10.1基本塊的劃分。輸入：一個三地址碼序列；輸出：一個基本塊列表，其中每個三地址碼僅在一個塊中；步驟：1．首先確定所有的入口(leader)語句，即基本塊的第一個語句。確定入口的規(guī)則如下：a)第一個語句是入口語句；b)任何能由條件轉移語句或無條件轉移語句轉移到的語句都是入口語句；c)緊跟在轉移語句或條件轉移后面的語句是入口語句。2．對于每個入口語句，其基本塊由它和直到下一個入口語句(但不含該入口語句)或程序結束為止的所有語句組成。2024/3/53110.2.2流圖程序的控制流信息可以用流圖表示，流圖是一個節(jié)點為基本塊的有向圖。以程序的第一個語句作為入口語句的節(jié)點稱為初始節(jié)點。如果在某個執(zhí)行序列中B2跟隨在Bl之后，則從Bl到B2有一條有向邊。如果從Bl的最后一條語句有條件或無條件轉移到B2的第一個語句；或者按程序正文的次序B2緊跟在Bl之后，并且Bl不是結束于無條件轉移，則稱B1是B2的前驅，而B2是Bl的后繼。2024/3/53210.2.3循環(huán)流圖中的循環(huán)就是具有唯一入口的強連通子圖，而且從循環(huán)外進入循環(huán)內，必須首先經過循環(huán)的入口節(jié)點。如果從流圖的初始節(jié)點到節(jié)點n的每條路徑都要經過節(jié)點d，則說節(jié)點d支配(dominate)節(jié)點n，記作d

dom

n，d又稱為n的必經節(jié)點。根據該定義，每個節(jié)點都支配它自身，而循環(huán)的入口節(jié)點則支配循環(huán)中的所有節(jié)點。2024/3/533支配節(jié)點集計算算法10.2支配節(jié)點集計算。輸入：流圖G，其節(jié)點集為N，邊集為E，初始節(jié)點為n0輸出：關系dom；步驟：1．D(n0):={n0};2．forN–{n0}中的ndoD(n):=N;/*初始化完畢*/3．whileD(n)發(fā)生變化do4．forN–{n0}中的ndo5．D(n):={n}∪D(p);2024/3/534循環(huán)循環(huán)的性質：循環(huán)必須有唯一的入口點，稱為首節(jié)點(header)。首節(jié)點支配循環(huán)中的所有節(jié)點。循環(huán)至少迭代一次，亦即至少有一條返回首節(jié)點的路徑。為了尋找流圖中的循環(huán)，必須尋找可以返回到循環(huán)入口節(jié)點的有向邊，這種邊叫做回邊(backedge)，如果b

dom

a，則邊a→b稱為回邊。利用支配節(jié)點集可以求出流圖中的所有回邊。給定一條回邊n→d，定義該邊的自然循環(huán)(naturalloop)為d加上所有不經過d而能到達n的節(jié)點集合。d是該循環(huán)的首節(jié)點。2024/3/535例10.63dom4回邊4→34dom7回邊7→410→7的自然循環(huán){7，8，10}7→4的自然循環(huán){4,5,6,7,8,10}4→3，8→3的自然循環(huán){3,4,5,6,7,8,10}2024/3/536自然循環(huán)的構造算法10.3構造回邊的自然循環(huán)。輸入：流圖G和回邊n→d；輸出：由n→d的自然循環(huán)中所有節(jié)點構成的集合loop；procedureinsert(m);ifm不在loop中thenbeginloop:=loop∪{m};將m壓入棧stackend;/*下面是主程序*/stack:=空;loop:=cceuwou;insert(n);whilestack非空dobegin從stack彈出第一個元素m;form的每個前驅pdoinsert(p)end2024/3/537循環(huán)如果將自然循環(huán)當作“循環(huán)”，則循環(huán)或者互不相交，或者一個在另外一個里面。內循環(huán)：不包含其他循環(huán)的循環(huán)稱為內循環(huán)。如果兩個循環(huán)具有相同的首節(jié)點，那么很難說一個包含另外一個。此時把兩個循環(huán)合并。B0B1B2B32024/3/538循環(huán)某些變換要求我們將循環(huán)中的某些語句移到首節(jié)點的前面。因此，在開始處理循環(huán)L之前，往往需要先創(chuàng)建一個稱為前置首節(jié)點的新塊。前置首節(jié)點的唯一后繼是L的首節(jié)點，原來從L外到達L首節(jié)點的邊都將改成進入前置首節(jié)點，從循環(huán)L里面到達首節(jié)點的邊不改變。初始時前置首節(jié)點為空，但對L的變換可能會將一些語句放到該節(jié)點中。首節(jié)點

首節(jié)點

前置首節(jié)點2024/3/539可歸約流圖可歸約流圖：一個流圖G是可約的，當且僅當可以把它的邊分成兩個不相交的組，其中一組僅含回邊，另一組的邊都不是回邊，這些邊被稱為前向邊，所有前向邊形成一個無環(huán)有向圖，在該圖中，每個節(jié)點都可以從G的初始節(jié)點到達。循環(huán)的可約流圖具有一個重要的性質，就是當流圖中的一些節(jié)點被看作是循環(huán)的節(jié)點集合時，這些節(jié)點之間一定包含一條回邊。于是，為了找出流圖可約程序中的所有循環(huán)，只要檢查回邊的自然循環(huán)即可。B1B2B3圖10.10一個不可約流圖2024/3/54010.3數(shù)據流分析為了進行代碼優(yōu)化，編譯器必須掌握程序中變量的定義和引用情況，有了這些信息才能對源程序進行合適的等價變換。例如，了解每個基本塊的出口處哪些變量是活躍的可以改進寄存器的利用率，執(zhí)行常量合并和無用代碼刪除則需要利用變量的“到達-定義”信息。對程序中變量的定義和引用關系的分析稱為數(shù)據流分析

2024/3/541數(shù)據流分析的種類到達-定義分析活躍變量分析可用表達式分析2024/3/54210.3.1數(shù)據流方程的一般形式下面的方程叫做數(shù)據流方程：out[S]=gen[S]∪(in[S]-kill[S])(10.3)

該方程的含義是，當控制流通過一個語句S時，在S末尾得到的信息(out[S])或者是在S中產生的信息(gen[S])，或者是進入S開始點時攜帶的、并且沒有被S注銷的那些信息(in[S]表示進入S開始點時攜帶的信息，kill[S]表示被S注銷的信息)。也可以根據out[S]來定義in[S]

in[S]=(out[S]-kill[S])∪gen[S](10.4)2024/3/54310.3.1數(shù)據流方程的一般形式不同的問題方程的意義可能有所不同，主要可由以下兩點來區(qū)別：信息流向問題。根據信息流向可以將數(shù)據流分析問題分為正向和反向兩類，正向的含義是根據in集合來計算out集合，反向則是從out集合來計算in集合。聚合操作問題。所謂聚合操作，是指當有多條邊進入某一基本塊B時，由B的前驅節(jié)點的out集計算in[B]時采用的集合操作(并或交)。到達-定義等方程采用并操作，全局可用表達式采用的則是交操作。2024/3/54410.3.1數(shù)據流方程的一般形式在基本塊中，將相鄰語句間的位置稱為點，第一個語句前和最后一個語句后的位置也稱為點。從點pl到點pn的路徑是這樣的點序列pl，p2,…，pn,對于

i(l≤i≤n-1)下列條件之一成立：pi是緊接在一個語句前面的點，pi+1是同一塊中緊跟在該語句后面的點；pi是某基本塊的結束點，而pi+1是后繼塊的開始點。為簡單起見，假設控制只能從一個開始點進入基本塊，而當基本塊結束時控制只能從一個結束點離開。2024/3/54510.3.2到達-定義分析變量x的定義是一條賦值或可能賦值給x的語句。最普通的定義是對x的賦值或從I/O設備讀一個值并賦給x的語句，這些語句比較明確地為x定義了一個值，稱為x的明確定義。也有一些語句只是可能為x定義一個值，稱為x的含糊定義，其常見形式有：1．以x為參數(shù)的過程調用(傳值方式除外)或者可能訪問x的過程；2．通過可能指向x的指針對x賦值。2024/3/54610.3.2到達-定義分析對于定義d，如果存在一條從緊跟d的點到p的路徑，并且在這條路徑上d沒有被“注銷”，則稱定義d到達(reach)點p。如果沿著這條路徑的某兩點間存在a的其它定義，則將注銷(kill)變量a的那個定義。注意，只有a的明確定義才能注銷a的其它定義。到達定義信息可以用引用-定義鏈(即ud-鏈)來保存，它是一個鏈表，對于變量的每次引用，到達該引用的所有定義都保存在該鏈表中。2024/3/54710.3.2到達-定義分析如果塊B中在變量a的引用之前沒有任何a的明確定義，那么a的這次引用的ud-鏈為in[B]中a的定義的集合。如果B中在a的這次引用之前存在a的明確定義，那么只有a的最后一次定義會在ud-鏈中，而in[B]不能放在ud-鏈中另外，如果存在a的含糊定義，那么所有那些在該定義和a的這次引用之間沒有a的明確定義的定義都將被放在a的這次引用的ud-鏈中利用ud-鏈可以求出循環(huán)中的所有循環(huán)不變計算，常量傳播也需要用到ud-鏈信息2024/3/548到達定義數(shù)據流方程(記號)in[B]:表示基本塊B的入口點處各個變量的定義集合。如果B中點p之前有x的定義d，且這個定義能夠到達p，則點p處x的ud鏈是2eiaqsw。否則，點p處x的ud鏈就是in[B]中x的定義集合。P[B]：B的所有前驅基本塊的集合。2024/3/549到達定義數(shù)據流方程(記號)gen[B]：各個變量在B內定義，并能夠到達B的出口點的所有定義的集合。out[B]：各個變量的能夠到達基本塊B的出口點的所有定義的集合。kill[B]：各個變量在基本塊B中重新定義，即在此塊內部被注銷的定義點的集合。2024/3/550到達定義數(shù)據流方程in[B]=∪out[p]wherepisinP[B]out[B]=gen[B]∪(in[B]-kill[B])其中：gen[B]可以從基本塊中求出：使用DAG圖就可以得到。kill[B]中，對于整個流圖中的所有x的定義點，如果B中有對x的定義，那么該定義點在kill[B]中。2024/3/551方程求解算法使用迭代方法。初始值設置為：in[Bi]=空；out[B]=gen[Bi];change=true;while(change){ change=false; foreachBdo {in[B]=∪out[p]wherepisinP[B]; out[B]=gen[B]∪(in[B]-kill[B]); oldout=out[B]; if(out[B]!=oldout)change=true;}}2024/3/552算法例子gen[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:- m 1 id2:= n jd3:= u2 ad4:+ i 1 id5:- j 1 jd6:= u2 ad7:= u3 iB1B2B3B42024/3/553計算過程初始化：in[B1]=in[B2]=in[B3]=in[B4]=空out[B1]={d1,d2,d3},out[B2]={d4,d5}out[B3]={d6},out[B4]={d7}.第一次循環(huán)：in[B1]=空;in[B2]={d1,d2,d3,d7};in[B3]={d4,d5};in[B4]={d4,d5,d6};out[B1]={d1,d2,d3};out[B2]={d3,d4,d5}…結果：in[B1]=空；out[B1]={d1,d2,d3};in[B2]={d1,d2,d3,d5,d6,d7};out[B2]={d3,d4,d5,d6};in[B3]={d3,d4,d5,d6}; out[B3]={d4,d5,d6};in[B4]={d3,d4,d5,d6};out[B4]={d3,d5,d6,d7};2024/3/55410.3.3活躍變量分析對于變量x和點p，在流圖中沿從p開始的某條路徑，是否可以引用x在p點的值。如果可以則稱x在p點是活躍的，否則，x在p點就是無用的?；钴S變量信息在目標代碼生成時具有重要的作用。當我們在寄存器中計算一個值之后，通常假設在某個塊中還要引用它，如果它在該塊的末尾是無用的，則不需要存儲該值。消除復制四元式的依據也是對活躍變量的分析。如果某個變量的值在以后不被引用，那么該復制四元式可以被消除。2024/3/555記號in[B]:基本塊B的入口點的活躍變量集合。out[B]:是在基本塊B的出口點的活躍變量集。def[B]:是在基本塊b內的定義，但是定義前在B中沒有被引用的變量的集合。use[B]:表示在基本塊中引用，但是引用前在B中沒有被定義的變量集合。其中，def[B]和use[B]是可以從基本塊B中直接求得的量，因此在方程中作為已知量。2024/3/556活躍變量數(shù)據流方程in[B]=use[B]∪(out[B]-def[B])out[B]=∪in[S]，其中S為B的所有后繼。變量在某點活躍，表示變量在該點的值在以后會被使用。第一個方程表示：一個變量在進入塊B時是活躍的，如果它在該塊中于定義前被引用一個變量在離開塊B時是活躍的，而且在該塊中沒有被重新定義。第二個方程表示：一個變量在離開塊B時是活躍的，當且僅當它在進入該塊的某個后繼時是活躍的。2024/3/557活躍變量數(shù)據流方程求解設置初值：in[Bi]=空;重復執(zhí)行以下步驟直到in[Bi]不再改變：for(i=1;i<n;i++){out[Bi]=∪in[s];s是Bi的后繼；in[Bi]=use[Bi]∪(out[Bi]-def[Bi]);}2024/3/558活躍變量數(shù)據流方程例子def[B1]={i,j,a}use[B1]={m,n,u1}def[B2]=空use[B2]={i,j}def[B3]={a}use[B3]={u2}def[B4]={i}use[B4]={u3}d1:- m 1 id2:= n jd3:= u2 ad4:+ i 1 id5:- j 1 jd6:= u2 ad7:= u3 i2024/3/559迭代過程第一次循環(huán)：out[B1]=空 in[B1]={m,n,u1}out[B2]=空 in[B2]={i,j}out[B3]={i,j} in[B3]={i,j,u2}out[B4]={i,j,u2}in[B4]={j,u2,u3}第二次循環(huán)：out[B1]={i,j,u2,u3} in[B1]={m,n,u1,u2,u3}out[B2]={i,j,u2,u3} in[B2]={i,j,u2,u3}out[B3]={i,j,u2,u3} in[B3]={i,j,u2,u3}out[B4]={i,j,u2,u3} in[B4]={j,u2,u3}第三次循環(huán)各個值不再改變，完成求解。2024/3/56010.3.3活躍變量分析定義-引用鏈定義-引用鏈(簡稱du-鏈)是一種和活躍變量分析方式相同的數(shù)據流信息。定義-引用鏈的計算與引用-定義鏈的計算正好相反，它是從變量x的某個定義點p出發(fā)，計算該定義可以到達的所有引用s的集合，所謂可以到達是指從p到s有一條沒有重新定義x的路徑。在代碼優(yōu)化過程中，無用代碼刪除、強度削弱、循環(huán)中的代碼外提以及目標代碼生成過程中的寄存器分配都要用到du-鏈信息。2024/3/56110.3.4可用表達式分析如果從初始節(jié)點到p的每一條路徑(不必是無環(huán)路的)都要計算xopy，而且在到達p的這些路徑上沒有對x或y的賦值，則稱表達式xopy在p點是可用的。對表達式的注銷：如果基本塊B中含有對x或y的賦值(或可能賦值)，而且后來沒有重新計算xopy，則稱B注銷了表達式xopy。表達式的生成：如果基本塊B明確地計算了xopy，并且后來沒有重新定義x或y，則稱B生成了表達式xopy?？捎帽磉_式信息的主要用途是檢測公共子表達式。2024/3/562記號out[B]：在基本塊出口處的可用表達式集合。in[B]：在基本塊入口處的可用表達式集合。e_gen[B]：基本塊B生成的可用表達式的集合。e_kill[B]：基本塊B注銷的可用表達式的集合。e_gen[B]和e_kill[B]的值可以直接從流圖計算出來，因此在數(shù)據流方程中，可以將e_gen[B]和e_kill[B]當作已知量看待。2024/3/563e_gen[B]的計算對于一個基本塊B，e_gen[B]的計算過程為：初始設置：e_gen[B]=空；順序掃描每個四元式：對于四元式opxyz，把xopy加入e_gen[B]，從gen[B]中刪除和z相關的表達式。最后的e_gen[B]就是相應的集合。2024/3/564e_kill[B]的計算設流圖的表達式全集為E;初始設置：EK=空；順序掃描基本塊的每個四元式：對于四元式opxyz，把表達式xopy從EK中消除；把E中所有和z相關的四元式加入到EK中。掃描完所有的四元式之后，EK就是所求的e_kill[B]。2024/3/565數(shù)據流方程out[B]=e_gen[B]∪(in[B]-e_kill[B])in[B]=∩out[p]B!=B1,p是B的前驅。in[B1]=空集說明：在程序開始的時候，無可用表達式。(3)一個表達式在某個基本塊的入口點可用，必須要求它在所有前驅的出口點也可用。（2）一個表達式在某個基本塊的出口點可用，或者該表達式是由它的產生的；或者該表達式在入口點可用，且沒有被注銷掉。（1）Bp2p1p3inoutgen-kill2024/3/566方程求解算法迭代算法初始化：in[B1]=空;out[B1]=e_gen[B1];out[Bi]=U-e_kill[Bi](i>=2)重復執(zhí)行下列算法直到out穩(wěn)定:for（i=2;i<=n;i++){in[Bi]=∩out[p],p是Bi的前驅；out[Bi]=e_gen[Bi]∪(in[Bi]-e_kill[Bi]);}2024/3/567算法說明初始化值和前面的兩個算法不同。out[Bi]的初值大于實際的值。在迭代的過程種，out[Bi]的值逐漸縮小直到穩(wěn)定。U表示四元式的全集，就是四元式序列中所有表達式xopy的集合。2024/3/56810.4局部優(yōu)化基本塊的功能實際上就是計算一組表達式，這些表達式是在基本塊出口活躍的變量的值。如果兩個基本塊計算一組同樣的表達式，則稱它們是等價的?？梢詫緣K應用很多變換而不改變它所計算的表達式集合，許多這樣的變換對改進最終由某基本塊生成的代碼的質量很有用。利用基本塊的dag表示可以實現(xiàn)一些常用的對基本塊的變換。2024/3/56910.4.1基本塊的dag表示dag的構造方法⑴基本塊中出現(xiàn)的每個變量都有一個dag節(jié)點表示其初始值。⑵基本塊中的每個語句s都有一個dag節(jié)點n與之相關聯(lián)。n的子節(jié)點是那些在s之前、最后一次對s中用到的運算對象進行定義的語句所對應的節(jié)點。⑶節(jié)點n由s中用到的運算符來標記，節(jié)點n還附加了一組變量，這些變量在基本塊中都是由s最后定義的。⑷如果有的話，還要記下那些其值在塊的出口是活躍的節(jié)點，它們是輸出節(jié)點。流圖的另一個基本塊以后可能會用到這些變量的值。2024/3/570利用dag進行的基本塊變換⑴局部公共子表達式刪除。⑵無用代碼刪除。⑶交換兩個獨立的相鄰語句的次序，以便減少某個臨時值需要保存在寄存器中的時間。⑷使用代數(shù)規(guī)則重新排列三地址碼的運算對象的順序，以便簡化計算過程。2024/3/57110.4.2局部公共子表達式刪除例10.12a:=b+cb:=a-dc:=b+cd:=a-d(10.8)如果b在出口處不是活躍的：a:=b+cd:=a-dc:=d+c

圖10.13基本塊(10.8)的dag2024/3/57210.4.3無用代碼刪除在dag上刪除無用代碼的方法很簡單：只要從dag上刪除所有沒有附加活躍變量的根節(jié)點(即沒有父節(jié)點的節(jié)點)即可。重復進行這樣的處理即可從dag中刪除所有與無用代碼相對應的節(jié)點。a:=b+cb:=b-dc:=c+de:=b+c圖10.14中的a和b是活躍變量，而c和e不是，我們可以立即刪除標記為e的根節(jié)點。隨后，標記為c的節(jié)點變成了根節(jié)點，下一步也可以被刪除。

圖10.14基本塊(10.9)的dag2024/3/57310.4.4代數(shù)恒等式的使用代數(shù)恒等式代表基本塊上另一類重要的優(yōu)化方法，下面是一些常見的代數(shù)恒等式：x+0=0+x=xx–0=xx*1=1*x=xx/1=x另外一類代數(shù)優(yōu)化是局部強度削弱，即用較快的運算符取代較慢的運算符，例如：x**2=x*x2.0*x=x+xx/2=x*0.52024/3/57410.4.4代數(shù)恒等式的使用第三類相關的優(yōu)化技術是常量合并。即在編譯時對常量表達式進行計算，并利用它們的值取代常量表達式。例如，表達式2*3.14可以替換為6.28。dag構造過程可以幫助我們應用上述和更多其它的通用代數(shù)變換，比如交換律和結合律。2024/3/57510.4.5數(shù)組引用的dag表示在dag中表示數(shù)組訪問的正確方法為：將數(shù)組元素賦給其他變量的運算(如x=a[i])用一個新創(chuàng)建的運算符為=[]的節(jié)點表示。該節(jié)點的左右子節(jié)點分別代表數(shù)組初始值(本例中為a0)和下標i。變量x則是該節(jié)點的附加標記之一。對數(shù)組元素的賦值(如a[j]=y)則用一個新創(chuàng)建的運算符為[]=的節(jié)點來表示。該節(jié)點的三個子節(jié)點分別表示a0、j和y。該節(jié)點不帶任何附加標記。這是因為該節(jié)點的創(chuàng)建注銷了所有當前已經創(chuàng)建的、其值依賴于a0的節(jié)點，而一個被注銷的節(jié)點不可能再獲得任何標記。也就是說，它不可能成為一個公共子表達式。2024/3/57610.4.5數(shù)組引用的dag表示例10.14基本塊x=a[i]a[j]=yz=a[i]的dag如圖10.15所示。圖10.15將數(shù)組元素賦值給其他變量的語句序列的dag2024/3/57710.4.6指針賦值和過程調用的dag表示當像語句x=*p或*q=y那樣通過指針進行間接賦值時，并不知道p和q指向哪里。x=*p可能是對任意某個變量的引用，而*q=y則可能是對任意某個變量的賦值。因而，運算符=*必須把當前所有帶有附加標識符的節(jié)點當作其參數(shù)。但這么做將會影響無用代碼的刪除。更為嚴重的是，*=運算符將把所有迄今為止構造出來的dag中的其他節(jié)點全部注銷?？梢赃M行一些全局指針分析，以便把一個指針在代碼中某個位置上可能指向的變量限制在一個較小的的子集內。2024/3/57810.4.7從dag到基本塊的重組對每個具有一個或多個附加變量的節(jié)點，構造一個三地址碼來計算其中某個變量的值。盡量把計算得到的結果賦給一個在基本塊出口處活躍的變量，如果沒有全局活躍變量的信息，則假設程序的所有變量在基本塊的出口處都是活躍的(臨時變量除外)。如果節(jié)點具有多個附加的活躍變量，則必須引入復制語句，以便為每一個變量都賦予正確的值。當然，通過全局優(yōu)化技術可以消除這些復制語句。2024/3/57910.4.7從dag到基本塊的重組當從dag重構基本塊時，不僅要關心用哪些變量來存放dag中節(jié)點的值，還要關心計算不同節(jié)點值的語句順序。下面是應遵循的規(guī)則：⑴語句的順序必須遵守dag中節(jié)點的順序。也就是說，只有在計算出某個節(jié)點的各個子節(jié)點的值之后，才能計算該節(jié)點的值。⑵對數(shù)組的賦值必須跟在所有(按照原基本塊中的語句順序)在它之前的對同一數(shù)組的賦值或引用之后2024/3/58010.4.7從dag到基本塊的重組⑶對數(shù)組元素的引用必須跟在所有(在原基本塊中)在它之前的對同一數(shù)組的賦值語句之后。對同一數(shù)組的兩次引用可以交換順序，前提是交換時它們都沒有越過某個對同一數(shù)組的賦值運算。⑷對某個變量的引用必須跟在所有(在原基本塊中)在它之前的過程調用或指針賦值運算之后。⑸任何過程調用或指針賦值都必須跟在所有(在原基本塊中)在它之前的對任何變量的引用之后。2024/3/58110.5循環(huán)優(yōu)化循環(huán)不變計算的檢測代碼外提歸納變量刪除和強度削弱2024/3/58210.5.1循環(huán)不變計算的檢測算法10.7循環(huán)不變計算檢測。輸入：由一組基本塊構成的循環(huán)L，每個基本塊包括一系列的三地址碼，且每個三地址碼的ud-鏈均可用；輸出：從控制進入循環(huán)L一直到離開L，每次都計算同樣值的三地址碼；步驟：1．將如下語句標記為“不變”：它們的運算對象或者是常數(shù)，或者它們的所有到達-定義都在循環(huán)L的外面。2．重復步驟(3),直到某次重復沒有新的語句可標記為“不變”為止3．將如下語句標記為“不變”：它們先前沒有被標記，而且它們的所有運算對象或者是常數(shù)，或者其到達定義都在循環(huán)L之外，或者只有一個到達定義，這個定義是循環(huán)L中已標記為“不變”的語句。2024/3/58310.5.2代碼外提將語句s：x:=y+z外提的條件：1．含有語句s的塊是循環(huán)中所有出口節(jié)點的支配節(jié)點，出口節(jié)點指的是其后繼節(jié)點不在循環(huán)中的節(jié)點2．循環(huán)中沒有其它語句對x賦值。如果x是只賦值一次的臨時變量，該條件肯定滿足，因此不必檢查。3．循環(huán)中x的引用僅由s到達，如果x是臨時變量，該條件一般也可以滿足。2024/3/58410.5.2代碼外提算法10.8代碼外提輸入：帶有ud-鏈和支配節(jié)點信息的循環(huán)L；輸出：循環(huán)的修正版本，增加了前置首節(jié)點，且(可能)有一些語句外提到前置首節(jié)點中；步驟：1．應用算法10.7尋找循環(huán)不變語句。2．對(1)中找到的每個定義x的語句s，檢查是否滿足下列條件：a)s所在的塊支配L的所有出口；b)x在L的其它地方沒有被定義，而且c)L中所有x的引用只能由s中x的定義到達。3．按算法10.7找出的次序，把(1)中找出的滿足(2)中3個條件的每個語句移到新的前置首節(jié)點。但是，若s的運算對象在L中被定義(由算法10.7的(3)找出這種s)，那么只有這些對象的定義語句外提到前置首節(jié)點后，才能外提s。2024/3/58510.5.3歸納變量刪除和強度削弱算法10.9歸納變量檢測輸入：帶有到達定義信息和循環(huán)不變計算信息(由算法10.7得到)的循環(huán)L；輸出：一組歸納變量，以及與每個歸納變量j相關聯(lián)的三元組(i,c,d)，其中i是基本歸納變量，c和d是常量，在j的定義點，j的值由c*i+d給出。稱j屬于i族，基本歸納變量i也屬于它自己的族；步驟：1．在循環(huán)L中找出所有的基本歸納變量，此處需要用到循環(huán)不變計算的信息。與每個基本歸納變量i相關聯(lián)的三元組為(i,1,0)。2024/3/58610.5.3歸納變量刪除和強度削弱2．在L中尋找具有下列形式之一且只被賦值一次的變量k：k:＝j*b，k:＝b*j，k:＝j/b，k:＝j±b，k:＝b±j其中，b是常數(shù)，j是基本的或非基本的歸納變量。⑴如果j是基本歸納變量，則k在j族中。k的三元組依賴于定義它的語句。例如，如果k是由k:＝j*b定義的，則k的三元組為(j,b,0)。類似地可以定義其他情況的三元組。⑵如果j不是基本歸納變量，假設j屬于i族，則j還要滿足如下要求：a)在循環(huán)L中對j的唯一賦值和對k的賦值之間沒有對i的賦值。b)循環(huán)L外沒有j的定義可到達k。此時利用j的三元組(i,c,d)和定義k的語句即可計算k的三元組。例如，定義k:＝b*j導致k的三元組為(i,b*c,b*d)。注意，b*c和b*d可以在分析過程中完成計算，因為b，c和d都是常數(shù)。2024/3/58710.5.3歸納變量刪除和強度削弱算法10.10用于歸納變量的強度削弱。輸入：循環(huán)L，附帶有到達定義信息和由算法10.9算出的歸納變量族；輸出：修正后的循環(huán)；步驟：依次考察每個基本歸納變量i。對每個三元組為(i,c,d)的i族歸納變量j，執(zhí)行如下步驟：1．建立新變量s，但如果變量jl和j2具有同樣的三元組，則只為它們建立一個新變量。2．用j:＝s代替對j的賦值。2024/3/58810.5.3歸納變量刪除和強度削弱3．在L中緊跟在每個賦值語句i:＝i+n之后(n是常數(shù))，添加上如下語句：

s:=s+c*n

其中，表達式c*n的計算結果為一個常數(shù)，因為c和n都是常數(shù)。將s放入i族，其三元組為(i,c,d)。4．必須保證在循環(huán)的入口處s的初值為c*i+d，該初始化可以放在前置首節(jié)點的末尾，由下面兩個語句組成：

s:＝c*i／*如果c為1