第五章 代碼優(yōu)化

1、第五章代碼優(yōu)化5.1 局部優(yōu)化局部優(yōu)化5.2 循環(huán)優(yōu)化循環(huán)優(yōu)化優(yōu)化的概念優(yōu)化的概念v代碼優(yōu)化代碼優(yōu)化 對代碼進(jìn)行等價(jià)變換，使得變換后的代碼具有更高對代碼進(jìn)行等價(jià)變換，使得變換后的代碼具有更高的時(shí)間效率和空間效率。的時(shí)間效率和空間效率。v空間效率和時(shí)間效率有時(shí)是一對矛盾，有時(shí)不能兼空間效率和時(shí)間效率有時(shí)是一對矛盾，有時(shí)不能兼顧。顧。v優(yōu)化要求優(yōu)化要求必須是等價(jià)變換必須是等價(jià)變換( (保持功能保持功能) )為優(yōu)化的努力必須是值得的為優(yōu)化的努力必須是值得的v機(jī)器相關(guān)性機(jī)器相關(guān)性機(jī)器相關(guān)優(yōu)化：寄存器優(yōu)化，多處理器優(yōu)化，特殊指機(jī)器相關(guān)優(yōu)化：寄存器優(yōu)化，多處理器優(yōu)化，特殊指令優(yōu)化，無用指令消除等。令優(yōu)化，

2、無用指令消除等。機(jī)器無關(guān)優(yōu)化：對中間代碼的優(yōu)化。機(jī)器無關(guān)優(yōu)化：對中間代碼的優(yōu)化。v優(yōu)化范圍優(yōu)化范圍局部優(yōu)化：單個(gè)局部優(yōu)化：單個(gè)基本塊基本塊范圍內(nèi)的優(yōu)化，包括常量合并、范圍內(nèi)的優(yōu)化，包括常量合并、公共子表達(dá)式刪除、計(jì)算強(qiáng)度削弱和無用代碼刪除等。公共子表達(dá)式刪除、計(jì)算強(qiáng)度削弱和無用代碼刪除等。全局優(yōu)化：主要是全局優(yōu)化：主要是基于循環(huán)基于循環(huán)的優(yōu)化，包括循環(huán)不變量的優(yōu)化，包括循環(huán)不變量代碼外提、刪除歸納變量、計(jì)算強(qiáng)度削弱等。代碼外提、刪除歸納變量、計(jì)算強(qiáng)度削弱等。v優(yōu)化語言級優(yōu)化語言級優(yōu)化語言級：針對中間代碼，針對機(jī)器語言。優(yōu)化語言級：針對中間代碼，針對機(jī)器語言。代碼優(yōu)化的分類代碼優(yōu)化的分類v控制流

3、分析控制流分析的主要目的是分析出程序的循環(huán)結(jié)構(gòu)。的主要目的是分析出程序的循環(huán)結(jié)構(gòu)。 循環(huán)結(jié)構(gòu)中的代碼的效率是整個(gè)程序的效率的關(guān)鍵。循環(huán)結(jié)構(gòu)中的代碼的效率是整個(gè)程序的效率的關(guān)鍵。v數(shù)據(jù)流分析數(shù)據(jù)流分析進(jìn)行數(shù)據(jù)流信息的收集，主要是變量的值進(jìn)行數(shù)據(jù)流信息的收集，主要是變量的值 的獲得和使用情況的數(shù)據(jù)流信息。的獲得和使用情況的數(shù)據(jù)流信息。到達(dá)到達(dá)- -定義分析；活躍變量分析；可用表達(dá)式分析；定義分析；活躍變量分析；可用表達(dá)式分析；v代碼變換代碼變換：根據(jù)上面的分析，對內(nèi)部中間代碼進(jìn)行等：根據(jù)上面的分析，對內(nèi)部中間代碼進(jìn)行等 價(jià)變換。價(jià)變換?？刂屏鞣治隹刂屏鞣治鰯?shù)據(jù)流分析數(shù)據(jù)流分析代碼變換代碼變換代碼優(yōu)

4、化主要完成的工作代碼優(yōu)化主要完成的工作5.1 局部優(yōu)化局部優(yōu)化v指基本塊內(nèi)的優(yōu)化。指基本塊內(nèi)的優(yōu)化。v基本塊：基本塊：是指程序（本課本中假設(shè)已經(jīng)是四是指程序（本課本中假設(shè)已經(jīng)是四元式表示的程序了）中一順序執(zhí)行的語句序元式表示的程序了）中一順序執(zhí)行的語句序列，其中只有一個(gè)入口語句和一個(gè)出口語句。列，其中只有一個(gè)入口語句和一個(gè)出口語句。5.1.1 基本塊的劃分基本塊的劃分v入口語句入口語句（1）四元式語句序列的第一個(gè)語句；）四元式語句序列的第一個(gè)語句；（2）條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到）條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的目標(biāo)語句；的目標(biāo)語句；（3）緊跟在條件轉(zhuǎn)移語句后面的語句。）緊跟在條件

5、轉(zhuǎn)移語句后面的語句。v出口語句出口語句（1）下一個(gè)入口語句的前導(dǎo)語句；）下一個(gè)入口語句的前導(dǎo)語句；（2）轉(zhuǎn)移語句（包括其自身）；）轉(zhuǎn)移語句（包括其自身）；（3）停語句（包括其自身）。）停語句（包括其自身）。v基本塊的劃分基本塊的劃分1、求出四元式程序之中各個(gè)基本塊的入口語句。、求出四元式程序之中各個(gè)基本塊的入口語句。2、對每一入口語句，構(gòu)造其所屬的基本塊。即由該、對每一入口語句，構(gòu)造其所屬的基本塊。即由該入口語句到出口語句之間的語句序列。入口語句到出口語句之間的語句序列。3、凡未被納入某一基本塊的語句，都是程序中控制、凡未被納入某一基本塊的語句，都是程序中控制流程無法到達(dá)的語句，因而也是不會被

6、執(zhí)行到的流程無法到達(dá)的語句，因而也是不會被執(zhí)行到的語句，可以把它們刪除。語句，可以把它們刪除。(1) read (C)(2) A= 0(3) B= 1(4) L1: A=A + B(5) if B= C goto L2(6) B=B+1(7) goto L1(8) L2: write (A)(9) halt為其劃分基本塊。為其劃分基本塊?！纠坑兴脑酱a程序如下：【例】有四元式代碼程序如下：5.1.2 基本塊的基本塊的DAG表示表示vDAG 指有向無環(huán)圖（指有向無環(huán)圖（ Directed Acyclic Graph ），），常用來對基本塊進(jìn)行優(yōu)化。常用來對基本塊進(jìn)行優(yōu)化。v基本塊的基本塊的

7、DAG 是是在結(jié)點(diǎn)上帶有標(biāo)記在結(jié)點(diǎn)上帶有標(biāo)記的的 DAG。 葉結(jié)點(diǎn)葉結(jié)點(diǎn) 代表名字的初值，以唯一的標(biāo)識符（變量代表名字的初值，以唯一的標(biāo)識符（變量名字或常數(shù)）標(biāo)記。通常用名字或常數(shù)）標(biāo)記。通常用x0表示變量名字表示變量名字x的初的初值。值。 內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn) 用運(yùn)算符作為標(biāo)記。用運(yùn)算符作為標(biāo)記。 所有結(jié)點(diǎn)所有結(jié)點(diǎn)都可有都可有一個(gè)或多個(gè)一個(gè)或多個(gè)附加標(biāo)識符，表示這些附加標(biāo)識符，表示這些變量具有該結(jié)點(diǎn)所代表的值。變量具有該結(jié)點(diǎn)所代表的值。 （其他四元式的其他四元式的 DAG 結(jié)點(diǎn)形式參見教材結(jié)點(diǎn)形式參見教材P131圖圖5-1）DAG 結(jié)點(diǎn)結(jié)點(diǎn) A BAop Bop n1 n2BCn1n2n1n3n

8、1n2四元式四元式A=BA=op BA= B op CA運(yùn)算符標(biāo)記運(yùn)算符標(biāo)記四元式和與其對應(yīng)的四元式和與其對應(yīng)的DAGDAG結(jié)點(diǎn)形式結(jié)點(diǎn)形式 基本塊基本塊 DAG 表示的構(gòu)造算法表示的構(gòu)造算法 設(shè)設(shè) A=B, A=op B, A=B op C分別為第分別為第0、1、2型四元式，設(shè)型四元式，設(shè)函數(shù)函數(shù) Node(name) 返回最近創(chuàng)建的關(guān)聯(lián)于返回最近創(chuàng)建的關(guān)聯(lián)于 name 的結(jié)點(diǎn)。的結(jié)點(diǎn)。 首先，置首先，置 DAG 為空。為空。 對基本塊的每一個(gè)四元式，依次執(zhí)行下列步驟：對基本塊的每一個(gè)四元式，依次執(zhí)行下列步驟： v若若 Node(B) 無定義，則創(chuàng)建一個(gè)標(biāo)記為無定義，則創(chuàng)建一個(gè)標(biāo)記為 B 的

9、葉結(jié)點(diǎn)，并令的葉結(jié)點(diǎn)，并令Node(B) 為這個(gè)結(jié)點(diǎn)；為這個(gè)結(jié)點(diǎn)； (1) 對于對于2型四元式型四元式，v若若Node(C) 無定義，再創(chuàng)建標(biāo)記為無定義，再創(chuàng)建標(biāo)記為C 的葉結(jié)點(diǎn)，并令的葉結(jié)點(diǎn)，并令 Node(C) 為這個(gè)結(jié)點(diǎn)。為這個(gè)結(jié)點(diǎn)。v若若 Node(B)和和 Node(C)都是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，都是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，執(zhí)行執(zhí)行B op C，令得到的新常數(shù)為，令得到的新常數(shù)為p。 若若Node(p) 無定義，則構(gòu)造一個(gè)用無定義，則構(gòu)造一個(gè)用 p 做標(biāo)記的葉結(jié)做標(biāo)記的葉結(jié)點(diǎn)點(diǎn) n,置置Node(p)=n。 若若 Node(B) 或或 Node(C)是處是處理當(dāng)前語句時(shí)新構(gòu)造出來的結(jié)點(diǎn)，則

10、刪除它。理當(dāng)前語句時(shí)新構(gòu)造出來的結(jié)點(diǎn)，則刪除它。 （這一步有（這一步有合并已知量合并已知量的作用）的作用）v若若 Node(B) 或或 Node(C)不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則檢查是否存在某個(gè)標(biāo)記為則檢查是否存在某個(gè)標(biāo)記為 op 的結(jié)點(diǎn)，其左孩的結(jié)點(diǎn)，其左孩子是子是 Node(B) ，而右孩子是，而右孩子是Node(C) ？ 若無，則創(chuàng)建這樣的結(jié)點(diǎn)。若無，則創(chuàng)建這樣的結(jié)點(diǎn)。 若有，則把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并且若有，則把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并且 無論有無，都令該結(jié)點(diǎn)為無論有無，都令該結(jié)點(diǎn)為 n。（這一步有（這一步有刪除多余運(yùn)算刪除多余運(yùn)算的作用）的作用）(2)對于對于

11、1型四元式型四元式v若若 Node(B) 是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則執(zhí)行是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則執(zhí)行 op B，令得到的新常數(shù)為，令得到的新常數(shù)為p. 若若 Node(p)無定義，則無定義，則構(gòu)造一個(gè)用構(gòu)造一個(gè)用 p 做標(biāo)記的葉結(jié)點(diǎn)做標(biāo)記的葉結(jié)點(diǎn) n，置，置node(p)=n。 若若Node(B) 是處理當(dāng)前語句時(shí)新構(gòu)造出來的結(jié)點(diǎn)，是處理當(dāng)前語句時(shí)新構(gòu)造出來的結(jié)點(diǎn)，則刪除它。（這一步有則刪除它。（這一步有合并已知量合并已知量的作用）的作用）v若若 Node(B) 不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則檢查是否存在某個(gè)標(biāo)記為檢查是否存在某個(gè)標(biāo)記為 op 的結(jié)點(diǎn)，其的結(jié)點(diǎn)，其唯一的孩子

12、是唯一的孩子是Node(B)？ 若無，則創(chuàng)建這樣的結(jié)點(diǎn)若無，則創(chuàng)建這樣的結(jié)點(diǎn);若有，則把已有若有，則把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)；并且無論有無，都的結(jié)點(diǎn)作為它的結(jié)點(diǎn)；并且無論有無，都令該結(jié)點(diǎn)為令該結(jié)點(diǎn)為n。 （這一步有（這一步有刪除多余運(yùn)算刪除多余運(yùn)算的作用）的作用）v若若Node(A)無定義，則把無定義，則把A附加在葉結(jié)點(diǎn)附加在葉結(jié)點(diǎn)n上上并令并令Node(A)=n；否則，先從；否則，先從Node(A)的附的附加標(biāo)識符集中將加標(biāo)識符集中將A刪去（如果刪去（如果Node(A) 是葉是葉結(jié)點(diǎn)，則不能將結(jié)點(diǎn)，則不能將A刪去），然后再把刪去），然后再把A附加到附加到新結(jié)點(diǎn)新結(jié)點(diǎn)n上，并令上，并令Node

13、(A)=n。（這一步有（這一步有刪除無用賦值刪除無用賦值的作用）的作用） 基本塊基本塊 DAG 表示的構(gòu)造舉例表示的構(gòu)造舉例（P132 例例5.15.1）T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6 n13.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6 n1 n23.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1 n5

14、n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1R0r0+T2 n6 n5 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1R0r0+T2*A n6 n5 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1R0r0+T2*A

15、, B n6 n5 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1, T3R0r0+T2*A, B n6 n5 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1, T3R0r0+T2,T4*A, B n6 n5 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T

16、4T6=R-rB=T5*T66.28T1, T3R0r0+T2,T4*A, B, T5 n6 n5 n7 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1, T3R0r0+T2,T4*A, B, T5-T6 n8 n6 n5 n7 n1 n2 n3 n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1, T3R0r0+T2,T4*A, T5-T6*B 從基本塊的從基本

17、塊的 DAG 表示可得到等價(jià)的基本塊表示可得到等價(jià)的基本塊-從下圖的從下圖的 DAG 可得到右邊的新的基本塊可得到右邊的新的基本塊 （經(jīng)拓?fù)渑判蚣疤砑舆m當(dāng)?shù)膹?fù)寫語句）（經(jīng)拓?fù)渑判蚣疤砑舆m當(dāng)?shù)膹?fù)寫語句） n8 n6 n5 n7 n1 n2 n3 n43.14T0T0=3.14T1=6.28T3=6.28T2=R+rT4=T2A=6.28*T2T5=AT6=R-rB=A*T66.28T1, T3R0r0+T2,T4*A, T5-T6*B 從基本塊的從基本塊的 DAG 表示可得到等價(jià)的基本塊表示可得到等價(jià)的基本塊- 比較變換前后的基本塊比較變換前后的基本塊T0=3.14T1=6.28T3=6.28T

18、2=R+rT4=T2A=6.28*T2T5=AT6=R-rB=A*T6T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6所作的優(yōu)化所作的優(yōu)化合并已知量合并已知量刪除多余運(yùn)算刪除多余運(yùn)算刪除無用賦值刪除無用賦值v利用利用DAG進(jìn)行基本塊優(yōu)化的進(jìn)行基本塊優(yōu)化的基本思想基本思想： 首先按基本塊內(nèi)的四元式序列順序?qū)⑺械氖紫劝椿緣K內(nèi)的四元式序列順序?qū)⑺械乃脑綐?gòu)造成一個(gè)四元式構(gòu)造成一個(gè)DAG，然后按照構(gòu)造結(jié)點(diǎn)，然后按照構(gòu)造結(jié)點(diǎn)的次序?qū)⒌拇涡驅(qū)AG還原成四元式序列。還原成四元式序列。v注意：注意：由于在構(gòu)造由于在構(gòu)造DA

19、G的同時(shí)已經(jīng)做了局部的同時(shí)已經(jīng)做了局部優(yōu)化，所以最后所得到的就是經(jīng)過優(yōu)化過的優(yōu)化，所以最后所得到的就是經(jīng)過優(yōu)化過的四元式序列。四元式序列。5.2 5.2 循環(huán)優(yōu)化循環(huán)優(yōu)化v循環(huán)體是優(yōu)化的重點(diǎn)循環(huán)體是優(yōu)化的重點(diǎn)v控制流圖控制流圖具有惟一具有惟一首結(jié)點(diǎn)首結(jié)點(diǎn)的有向圖。的有向圖。用來給出循環(huán)的定義。用來給出循環(huán)的定義。給出找出程序中循環(huán)的算法。給出找出程序中循環(huán)的算法。v循環(huán)的定義循環(huán)的定義具有唯一入口結(jié)點(diǎn)的強(qiáng)連通子圖。具有唯一入口結(jié)點(diǎn)的強(qiáng)連通子圖。v強(qiáng)連通子圖強(qiáng)連通子圖任意兩結(jié)點(diǎn)間的通路上各結(jié)點(diǎn)屬于子圖。任意兩結(jié)點(diǎn)間的通路上各結(jié)點(diǎn)屬于子圖。循環(huán)的查找方法見課本P138第5.2.2小節(jié)！5.2.3

20、循環(huán)優(yōu)化循環(huán)優(yōu)化v代碼外提代碼外提v強(qiáng)度削弱強(qiáng)度削弱v刪除歸納變量刪除歸納變量方法方法 1：代碼外提：代碼外提v將將循環(huán)不變運(yùn)算循環(huán)不變運(yùn)算移到循環(huán)外。移到循環(huán)外?！纠俊纠?有程序如下，試對其進(jìn)行優(yōu)化。有程序如下，試對其進(jìn)行優(yōu)化。i = 0;while( i = 20 goto (8)(3) if i = 20 goto (8)v循環(huán)不變運(yùn)算的定義：循環(huán)不變運(yùn)算的定義：P142v查找循環(huán)中不變運(yùn)算的算法描述：查找循環(huán)中不變運(yùn)算的算法描述：P144v代碼外提算法描述：代碼外提算法描述：P144方法方法 2：強(qiáng)度削弱：強(qiáng)度削弱v把程序中執(zhí)行時(shí)間較長的運(yùn)算替把程序中執(zhí)行時(shí)間較長的運(yùn)算替換為執(zhí)行時(shí)

21、間較短的運(yùn)算。換為執(zhí)行時(shí)間較短的運(yùn)算。X : = K * i + Y相關(guān)計(jì)算相關(guān)計(jì)算i = i + C歸納變量歸納變量（ K、C、Y 為循環(huán)不變量）為循環(huán)不變量）改改為為X = X + K * C（ 設(shè)設(shè) X 的初值的初值 = Y - K * C ）(4) x = 4 * i(5) i = i + 1(6) y = t1 + x(7) goto (3)(5) x = x + 4(6) i = i + 1(7) y = t1 + x(8) goto (4)(1) i = 0(2) t1 = z * 6(1) i = 0(2) t1 = z * 6(3) x = -4(3) if i = 20 g

22、oto (8)(4) if i = 20 goto (9)方法方法 3: 消除歸納變量消除歸納變量v利用利用歸納變量歸納變量相關(guān)的計(jì)算相關(guān)的計(jì)算代替代替歸納變量歸納變量的計(jì)算的計(jì)算條件表達(dá)式的修改條件表達(dá)式的修改無用語句的刪除無用語句的刪除(5) x = x + 4(6) i = i + 1(7) y = t1 + x(8) goto (4)(4) x = x + 4(5) y = t1 + x(6) goto (3)(1) i = 0(2) t1 = z * 6 (3) x = -4(1) t1 = z * 6(2) x = -4(4) if i = 20 goto (9)(3) if x

23、= 76 goto (7)v強(qiáng)度削弱和刪除歸納變量的算法描述：強(qiáng)度削弱和刪除歸納變量的算法描述： P147代碼優(yōu)化示例代碼優(yōu)化示例本節(jié)所用的例子本節(jié)所用的例子i = m - -1; (1) i = m - -1 j = n; (2) j = n v = an; (3) t1 = 4 * * n (4) v = at1while (1) do i = i +1; while(aiv); (5) i = i + 1 (6) t2 = 4 * * i (7) t3 = at2 (8) if t3v); (9) j = j - -1 (10) t4 = 4 * * j (11) t5 = at4 (1

24、2) if t5v goto (9) if (i = j) break; (13) if i =j goto (23) x=ai; (14) t6 = 4 * i (15 ) x = at6ai=aj; (16) t7=4*i (17) t8=4*j (18) t9=at8 (19) at7=t9 aj=x; (20) t10=4*j (21) at10=x (22) goto (5) x=ai; (23) t11=4*i (24) x=at11ai=an; (25) t12=4*i (26) t13=4*n (27) t14=at13 (28) at12=t14an=x; (29) t15=

25、4*n (30) at15=xi = m - -1j = nt1 = 4 * * nv = at1i = i + 1t2 = 4 * * it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B61、刪除公共子表達(dá)式、復(fù)寫傳播、刪除公共子表達(dá)式、復(fù)寫傳播B5 x=ai; ai=aj; aj=x;t6 = 4 * * ix = at6t7 = 4 * * i t8 = 4 * * jt9 = at8at7 = t9t10 = 4 * * jat10 = xgoto B2B5 x=ai; ai=aj; aj=x;t6 = 4 * * ix = at6t7 =

26、4 * * i t8 = 4 * * jt9 = at8at7 = t9t10 = 4 * * jat10 = xgoto B2B5 x=ai; ai=aj; aj=x;t6 = 4 * * ix = at6t7 = 4 * * i t8 = 4 * * jt9 = at8at7 = t9t10 = 4 * * jat10 = xgoto B2t6 = 4 * * ix = at6t8 = 4 * * jt9 = at8at6 = t9at8 = xgoto B2B5 x=ai; ai=aj; aj=x;t6 = 4 * * ix = at6t7 = 4 * * i t8 = 4 * * jt9 = at8at7 = t9t10 = 4 * * jat10 = xgoto B2t6 = 4 * * ix