設(shè)程序片段S=if C then S1 else S2，S1和S2可以是由賦值、條件、循環(huán)構(gòu)成的復(fù)雜語句，S不為當(dāng)前程序最后語句或某個(gè)循環(huán)主體最后語句，則S對(duì)應(yīng)的流圖生成的深度優(yōu)先生成樹T有3條樹邊，有S1的出口數(shù)+S2出口數(shù)-1條交叉邊。為什么是3條樹邊？C到S1、C到S2、S1或S2到S3（S3是S后繼結(jié)點(diǎn)，下同）。為什么交叉邊數(shù)是S1出口數(shù)+S2出口數(shù)-1？因?yàn)榱鲌D中S1出口及S2出口到S3的邊，在生成T的過程中，只有1個(gè)出口比S3先訪問，這對(duì)應(yīng)形成1條樹邊，訪問S3后再訪問其它出口，這對(duì)應(yīng)形成其它出口到S3的交叉邊，注意這里沒有前向邊，因?yàn)檩^晚訪問的出口在T中不可能是S3的祖先。如果把S改為if C then S1，情況會(huì)怎樣？結(jié)果取決于生成T的過程中先訪問S3還是S1。若先訪問S3，則有樹邊2條：C到S3、C到S1，交叉邊數(shù)等于S1的出口數(shù)：S1的每個(gè)出口到S3各一條邊，沒有前向邊。若先訪問S2，則有樹邊1條：C到S2，前向邊1條：C到S3，交叉邊數(shù)等于S1出口數(shù)-1。
總結(jié)此類問題分析的基本思路是對(duì)程序控制結(jié)構(gòu)先構(gòu)建流圖，再構(gòu)建深度優(yōu)先生成樹，辨別其中的前向邊、交叉邊、后退邊
1.閉包記錄分配：若逃逸分析能識(shí)別哪些閉包記錄在創(chuàng)建它們的函數(shù)中是出口不活躍的，則這些閉包記錄可分配在棧幀中（不再是堆中）
2.內(nèi)聯(lián)擴(kuò)展：由于小函數(shù)較多，因此內(nèi)聯(lián)可以免去調(diào)用開銷而提高性能，對(duì)于遞歸函數(shù)，需先用循環(huán)前置頭轉(zhuǎn)換再內(nèi)聯(lián)，如果是尾遞歸函數(shù)，可先使用尾調(diào)用優(yōu)化刪除遞歸。如果一個(gè)函數(shù)的所有調(diào)用都被內(nèi)聯(lián)擴(kuò)展，并且該函數(shù)沒有作為參數(shù)傳遞或其它方式被引用，那么可以刪除這個(gè)函數(shù)本身即函數(shù)定義。內(nèi)聯(lián)擴(kuò)展可以繼續(xù)作用于擴(kuò)展后的函數(shù)體，只要存在函數(shù)調(diào)用，這也叫層疊式內(nèi)聯(lián)
3.循環(huán)不變量參數(shù)外提：遞歸函數(shù)經(jīng)過循環(huán)前置頭轉(zhuǎn)換后，若每次遞歸調(diào)用頭函數(shù)，傳入的某些參數(shù)值總不變，則可以將它們從函數(shù)參數(shù)中刪除，函數(shù)體中的每次使用出現(xiàn)用序曲函數(shù)對(duì)應(yīng)的參數(shù)名替換
4.解開嵌套的let：將嵌套的多層let中的代碼合并為一個(gè)let中的代碼，in中的代碼不變
5.避免代碼膨脹：由于內(nèi)聯(lián)復(fù)制函數(shù)體，通常使程序體積變大，且層疊式內(nèi)聯(lián)可無限擴(kuò)展下去，因此為避免代碼膨脹，有如下啟發(fā)式策略對(duì)內(nèi)聯(lián)進(jìn)行控制
a) 只內(nèi)聯(lián)執(zhí)行很頻繁的函數(shù)調(diào)用，可根據(jù)靜態(tài)估計(jì)比如循環(huán)嵌套深度、迭代次數(shù)，或根據(jù)執(zhí)行剖面分析反饋，計(jì)算函數(shù)的執(zhí)行頻率
b) 內(nèi)聯(lián)很小的函數(shù)，其函數(shù)體不會(huì)比直接調(diào)用多出較多指令
c) 內(nèi)聯(lián)只調(diào)用一次的函數(shù)，然后刪除原來的函數(shù)定義
1. 整數(shù)r>s>0，(r, s)=1，2?r+s，x=r^2-s^2, y=2rs, z=r^2+s^2，求證(x, y)=1，(y, z)=1
?證明：由2?r+s（r與s必一奇一偶）知2?r-s，故2?r^2-s^2，以及2?(r+s)(r+s)。又1=(r, s)=(r+s, r)=(r+s, s)=(r+s, rs)。同理得1=(r, s)=(r-s, rs)，故1=((r+s)(r-s), rs)=(r^2-s^2, rs)，又1=(2, r^2-s^2)，故(r^2-s^2, 2rs)=1，即(x, y)=1。?(y, z)=(2rs, r^2+s^2)=(2rs, r^2+s^2+2rs)=(2rs, (r+s)(r+s))=(rs, (r+s)(r+s))=(rs, r+s)=(r, r+s)=(r, s)=1
?注：用最大公約數(shù)定義、整除性質(zhì)、反證法，也可以得出(x, y)=1，(y, z)=1。本法則直接從最大公約數(shù)定理推導(dǎo)
2. u^2+3v^2=2p不可能成立，u、v為整數(shù)，p為奇素?cái)?shù)
證明：u^2+3v^2=2p => u^2+v^2=2(p-v^2) => ?2|u^2+v^2=(u+v)^2-2uv => 2|(u+v)^2 => 2|u+v。得出這個(gè)中間結(jié)論，再由它可得4|2(u+v)|2v(u+v)=2v^2+2uv，以及4|(u+v)^2=u^2+v^2+2uv，故得4|u^2+3v^2+4uv，繼得4|u^2+3v^2=2p，即2|p，所以矛盾，證畢
?3. 若四個(gè)正整數(shù)y1*x2=y2*x1，(x1,y1)=(x2,y2)=1，則x1=x2，y1=y2
?證明：由y1*x2=y2*x1可得x1|y1*x2，又因(x1,y1)=1，故x1|x2；另得x2|y2*x1，又因(x2,y2)=1，故x2|x1；終得x1=x2，y1=y2
4. 假設(shè)2?z，z^3=x^2+3y^2有解且滿足(x, y)=1，其通解形式為x=a^3-9ab^2，y=3a^2b-3b^2，a、b滿足z=a^2+3b^2，求證(-3/p)=1，p是z的任一素因子；(a, 3b)=1
證明：先論證中間結(jié)論3?z，p>3且(p, xy)=1。若3|z，則3|x^2+3y^2=>3|x^2=>3|x=>9|x^2，另有9|x^2+3y^2=>9|3y^2=>3|y^2=>3|y，這與(x, y)=1矛盾，故3?z。又2?z，得p>3，由此若p|x，則p|3y^2得p|y，或若p|y，則p|x^2得p|x，都與(x, y)=1矛盾，故(p, xy)=1。
再論證勒讓德符號(hào)(-3/p)=1。由以上中間結(jié)論得等價(jià)形式x^2+3y^2=(Z^3p^2)p，及p?x^2、p?y^2，推得1=(x^2/p)=(-3y^2/p)=(-3/p)。
最后論證(a, 3b)=1。假設(shè)2|z，則2|a^2+b^2=(a+b)^2-2ab或(a-b)^2+2ab =>2|a+b, 2|a-b。因題設(shè)是2?z，故2?a+b, 2?a-b，由此推得2?a^2-b^2, 4?a^2-b^2，進(jìn)而8?a^2-b^2，即(8, a^2-b^2)=1。由1=(x, y)=(a^3-9ab^2, 3a^2b-3b^2)=(a(a^2-9b^2), 3b(a^2-b^2))。又(a^2-9b^2, a^2-b^2)=(8b^2, a^2-b^2)=(b^2, b^2-a^2)=(b^2, a^2)=(a, b)^2，于是令a^2-9b^2=(a, b)^2*A, a^2-b^2=(a, b)^2*B，則得1=(x, y)=(a, b)^2*(aA, 3bB)，故(a, 3b)=1
5. 已知2?u+w，3?u，(u, w)=1，求證(2u, u^2+3w^2)=1
證明：2?u+w=>2?u^2+w^2=>2?u^2+3w^2，即(2, u^2+3w^2)=1。
由3?u，(u, w)=1得(u, 3w)=(u, 3w^2)=(u, u^2+3w^2)=1。
綜上兩式結(jié)果得(2u, u^2+3w^2)=1
6. 已知(3v, w)=1，2?3v+w，求證(18v, 3v^2+w^2)=1
證明：(3v, w)=1=>(3v, w^2)=(3v, 3v^2+w^2)=1。
(3v, w)=1=>(3, w)=1=>(3, w^2)=(3, 3v^2+w^2)=1。2?3v+w=>2?v+w=>2?v^2+w^2=>2?3v^2+w^2，即(2, 3v^2+w^2)=1。
綜上三式結(jié)果得(18v, 3v^2+w^2)=1
###############################
從1、5和6問題的證明過程可得，如果一個(gè)數(shù)由兩個(gè)或多個(gè)因子相乘，那么求證是否互素可以逐一求每個(gè)因子與另一個(gè)數(shù)是否都互素
周知aes有限域同構(gòu)于系數(shù)為F2域一元多項(xiàng)式環(huán)的商環(huán)，其理想由不可約多項(xiàng)式m(x)=x^8+x^4+x^3+x+1生成，即F2^8≌F2[x]/(m(x))。這次進(jìn)一步用域擴(kuò)張的觀點(diǎn)分析，可以得知F2[x]/(m(x))正是包涵m(x)零點(diǎn)的擴(kuò)域，設(shè)為K。那么如何理解？
令I(lǐng)=(m(x))，則K=F2[x]/I，理解關(guān)鍵是找出m(x)在K上的零點(diǎn)，以及K怎樣包涵F2？
1. 零點(diǎn)為~x。這里用~g(x)表示多項(xiàng)式在K中的陪集，即~g(x)=g(x)+I，所以~x=x+I。把~x代入m(x)，根據(jù)商環(huán)定義的加乘運(yùn)算，代換結(jié)果為m(x)+I=~m(x)=~0（~0是K的零元）。那么還有嗎？比如~(x+a)（a非0），~x^2，代入這些得到的陪集代表不等于m(x)，所以不是零點(diǎn)。因此零點(diǎn)是唯一的一次多項(xiàng)式x之陪集
2. 構(gòu)造映射σ，把0對(duì)到K中的零多項(xiàng)式即~0，1對(duì)到K中的常數(shù)多項(xiàng)式即~1，且σ(0+1)=~1=~0+~1=σ(0)+σ(1)，σ(0*1)=~0=~0*~1=σ(0)*σ(1)，又依多項(xiàng)式比較法則得~0不等于~1，故σ是單同態(tài)，K包涵F2
小結(jié)：商群、商環(huán)、商域類似模同余之剩余系，理解這些結(jié)構(gòu)的關(guān)鍵是深入理解等價(jià)類、陪集，進(jìn)而可理解正規(guī)子群、理想，最后就是商X之類的東西
1. 輸入：前者是二進(jìn)制可執(zhí)行程序，后者是高級(jí)語言源程序
2. 優(yōu)化對(duì)象：前者主要是直線型代碼區(qū)域比如蹤跡或超塊（熱點(diǎn)路徑代碼），超塊類似后者中的擴(kuò)展塊；后者是控制流圖，即所有代碼塊，不限于熱點(diǎn)路徑代碼。超塊構(gòu)造類似后者中的基本塊放置和過程放置
3. 優(yōu)化方法：前者要運(yùn)行時(shí)采集剖析數(shù)據(jù)比如結(jié)點(diǎn)剖析和邊剖析，再基于剖析數(shù)據(jù)形成有利于指令cache局部性的超塊，然后在超塊上作常量傳播、常量折疊、強(qiáng)度削弱、復(fù)寫傳播、死代碼消除、公共表達(dá)式消除等基本優(yōu)化，也會(huì)作指令重排，但考慮到陷阱處理要恢復(fù)精確的客戶進(jìn)程狀態(tài)，因此比較受限，沒有后者中的指令重排自由。后者如果基于剖析作優(yōu)化，那么效果和前者差不多
4. 寄存器分配：都是基于活躍范圍的沖突圖著色算法，但前者考慮到陷阱處理會(huì)延長相關(guān)寄存器的活躍范圍，而后者不用
————————————————————————
總結(jié)：二進(jìn)制優(yōu)化所用的技術(shù)和編譯優(yōu)化其實(shí)相同，不同的是為陷阱處理所作的改變調(diào)整，以及運(yùn)用在熱點(diǎn)代碼塊而非所有塊
1. NFA到DFA：設(shè)NFA的狀態(tài)數(shù)為n，根據(jù)子集構(gòu)造法，則至多有2^n個(gè)狀態(tài)轉(zhuǎn)移，對(duì)每個(gè)狀態(tài)轉(zhuǎn)移，其狀態(tài)分量至多有n個(gè)狀態(tài)，每個(gè)狀態(tài)計(jì)算它的可達(dá)狀態(tài)集合耗時(shí)為O(n^2)，另可達(dá)狀態(tài)集合的并耗時(shí)為O(n^2)，故一個(gè)轉(zhuǎn)移耗時(shí)為n*O(n^2)=O(n^3)，則所有轉(zhuǎn)移總耗時(shí)為O(n^3*2^n)。由于實(shí)際產(chǎn)生的狀態(tài)數(shù)遠(yuǎn)小于2^n（通常為n），因此耗時(shí)為O(n^3*s)，s為DFA實(shí)際具有的狀態(tài)數(shù)
2. DFA到NFA：轉(zhuǎn)化方法是修改轉(zhuǎn)移表，對(duì)每個(gè)狀態(tài)轉(zhuǎn)移的目標(biāo)狀態(tài)加上集合括號(hào)（因NFA對(duì)特定輸入可能有多個(gè)目標(biāo)狀態(tài)，故為集合），若轉(zhuǎn)為£-DFA，則還需對(duì)每個(gè)狀態(tài)增加對(duì)£的轉(zhuǎn)移為空集。該方法耗時(shí)為O(n)，n為DFA的狀態(tài)數(shù)
3. DFA到正則表達(dá)式：設(shè)DFA狀態(tài)數(shù)為n，根據(jù)遞推公式R(i,j,k)=R(i,j,k-1)+R(i,k,k-1)R(k,k,k-1)^*R(k,j,k-1)（1<=i<=j<=n，0<=k<=n）來逐步構(gòu)造表達(dá)式，最終的表達(dá)式就是所有R(1,j,n)的并，其中j為可接受狀態(tài)。該過程會(huì)產(chǎn)生總共n^3+n^2個(gè)表達(dá)式，每次k遞增導(dǎo)致表達(dá)式長度增為4倍，故總耗時(shí)為O(n^3*4^n)。另一種更快的方法是消除所有除初始和接受狀態(tài)外的中間狀態(tài)，每次消除一個(gè)，就合并其前驅(qū)經(jīng)過它到其后繼的正則表達(dá)式和前驅(qū)直接到后繼的正則表達(dá)式，因前驅(qū)或后繼至多n-2個(gè)，則共有(n-2)^2個(gè)前驅(qū)到后繼的直通邊，且中間狀態(tài)至多n-2個(gè)，故耗時(shí)為O(n^3)；最后合并各接受狀態(tài)的正則表達(dá)式，因接受狀態(tài)至多n-1個(gè)，故耗時(shí)為O(n)。故總耗時(shí)為O(n^3)
4. 正則表達(dá)式到£-NFA：作詞法分析，對(duì)每個(gè)終結(jié)符號(hào)構(gòu)建狀態(tài)結(jié)點(diǎn)及轉(zhuǎn)移邊，即子£-NFA，特定符號(hào)對(duì)應(yīng)用并、連接、閉包、結(jié)合之一聯(lián)合已構(gòu)建的子£-NFA，耗時(shí)為O(n)，n為正則表達(dá)式的長度
1. 三條定律：交換律、結(jié)合律、吸收律（對(duì)于半格是冪等律），吸收律包含了冪等律
2. 上下界：交半格每對(duì)元素都有唯一最大下界，并半格每對(duì)元素都有唯一最小上界，格每對(duì)元素都有唯一最大下界和唯一最小上界
3. 格定義一個(gè)偏序，偏序有三個(gè)性質(zhì)：自反性、反對(duì)稱性、傳遞性
4. 格與偏序的關(guān)系：每個(gè)格對(duì)應(yīng)一個(gè)偏序，但不是所有偏序都對(duì)應(yīng)一個(gè)格，要滿足每對(duì)元素都有唯一最小上界和（或，對(duì)于半格）唯一最大下界。如果集合中的任何一個(gè)子集（包括空集）均存在最小上界和最大下界，那么對(duì)應(yīng)一個(gè)完備格
5. 任何元素有限的格都是完備格，格中的交運(yùn)算和并運(yùn)算對(duì)于其定義的偏序來說是單調(diào)的
6. 格的乘積、和、提升、映射仍然是格，利用這個(gè)性質(zhì)，可以在已有格的基礎(chǔ)上增量地構(gòu)造描述能力更豐富的格，這種技術(shù)稱為論域精化，是提高程序靜態(tài)分析精度的重要指導(dǎo)思想之一
周知cpu為方便亂序執(zhí)行，內(nèi)部會(huì)使用重命名寄存器技術(shù)消除數(shù)據(jù)依賴（war和waw）。編譯器在如下場(chǎng)景也會(huì)用到重命名
1. 靜態(tài)單賦值。過程內(nèi)的每個(gè)變量唯一定義一次，原有相同的則會(huì)重命名，包括phi結(jié)點(diǎn)的定值
2. bb表調(diào)度。為消除反相關(guān)依賴即war，可以重命名讀操作使用或?qū)懖僮鞫x的值，這樣能調(diào)度產(chǎn)生總時(shí)鐘周期更少的指令序列，但可能增加寄存器壓力導(dǎo)致溢出而新增了長延遲操作（內(nèi)存加載/存儲(chǔ)）并迫使另一輪調(diào)度
3. ebb表調(diào)度。對(duì)于某一ebb的一條路徑p，p存在過早退出路徑pe，p和pe的公共前綴是基本塊b，當(dāng)調(diào)度p時(shí)，如果某個(gè)操作i向后移動(dòng)到b，且i定義的值殺死了pe上的同名值，那么需要重命名i的定值。若i的定值被重命名，且其在p的出口處是活躍的，則調(diào)度器需要在出口處復(fù)制回原來的名字
4. trace表調(diào)度。蹤跡不同于ebb路徑，它允許中間存在多個(gè)前驅(qū)即入口的基本塊，而后者不能。當(dāng)調(diào)度存在多入口的塊b的某蹤跡t時(shí)，t上的某操作i可能前向移動(dòng)跨越b（t外的代碼路徑需作補(bǔ)償），若i殺死了一個(gè)活躍范圍跨越b的值，則需要重命名i的定值；同理，若i向后移動(dòng)跨越b且殺死了t上的某值，則需重命名i的定值，這時(shí)t外的代碼路徑補(bǔ)償可以使用同一名字
1. 不可達(dá)代碼是指無論輸入什么都不會(huì)執(zhí)行的代碼，對(duì)過程而言，即是從入口基本塊到不了（沒有路徑可達(dá)）的那些基本塊；死代碼是指可達(dá)但計(jì)算了后面任何可執(zhí)行路徑都不會(huì)使用其計(jì)算結(jié)果的代碼，比如死變量和死指令
2. 不可達(dá)代碼的識(shí)別本質(zhì)是有向圖的可達(dá)性判定與傳遞閉包計(jì)算問題，一般用DFS法處理。先找到從入口基本塊不可達(dá)的基本塊，再刪除（同時(shí)改變其前驅(qū)和后繼基本塊的指向），直到找不到為止。死代碼的識(shí)別可用活躍分析或必要指令標(biāo)記法，對(duì)于活躍分析，刪除基本塊出口不活躍的變量定值，以及它所使用不活躍操作數(shù)的定值；對(duì)于標(biāo)記法，從必要指令出發(fā)，根據(jù)def-use鏈和use-def鏈，不斷標(biāo)記對(duì)其操作數(shù)有貢獻(xiàn)的指令，最后刪除沒被標(biāo)記的那些指令
3. 不可達(dá)代碼和死代碼可能來源于程序員，更可能源于編譯器的其它一些優(yōu)化產(chǎn)生，刪除優(yōu)化它們能顯著減小代碼體積，對(duì)執(zhí)行速度有間接的影響，因?yàn)榭赡芨纳浦噶罡咚倬弻拥睦寐?/div>
1. 目的是識(shí)別循環(huán)中那種在每個(gè)迭代都產(chǎn)生相同值的計(jì)算，并將它們移到循環(huán)之外。注意，如果一個(gè)計(jì)算出現(xiàn)在嵌套循環(huán)內(nèi)，對(duì)外循環(huán)的特定迭代而言，內(nèi)循環(huán)的每個(gè)迭代都產(chǎn)生相同的值，但外循環(huán)的不同迭代產(chǎn)生不同的值，那么這種計(jì)算將移到內(nèi)循環(huán)外，而非外循環(huán)外
2. 識(shí)別循環(huán)不變量可以基于數(shù)據(jù)流分析求得的use-def鏈，一條指令是循環(huán)不變的，當(dāng)它的每個(gè)操作數(shù)滿足以下條件之一
a）該操作數(shù)是常數(shù)
b）該操作數(shù)的所有到達(dá)定值在循環(huán)之外。因?yàn)槿粲幸粋€(gè)在循環(huán)內(nèi)，則該指令就可能是循環(huán)變化的，除非那個(gè)定值是循環(huán)不變量
c）該操作數(shù)只存在一個(gè)為循環(huán)不變量的到達(dá)定值，且該指令之前沒有對(duì)其左部變量（若有）的使用。因?yàn)槿粲卸鄠€(gè)這樣的定值，則該指令就可能是循環(huán)變化的，除非多個(gè)定值結(jié)果都一樣；因?yàn)槿羟懊嬗袑?duì)其左部變量的使用，則該指令的賦值就殺死了左部變量的初值，這樣外提后左部變量第一次迭代就會(huì)使用錯(cuò)誤的定值
3. 由于以上條件沒考慮到控制流分析，不能保證循環(huán)不變量在每個(gè)迭代中執(zhí)行，以及循環(huán)不變量之左部變量的所有使用都是相同的值。因此為了保證外提后的代碼行為正確，還需要滿足條件：循環(huán)不變量所在基本塊必須是循環(huán)中所有使用了其左部變量的基本塊和所有出口基本塊的必經(jīng)結(jié)點(diǎn)。當(dāng)外提循環(huán)不變量后，考慮到循環(huán)有可能執(zhí)行0次即一開始就不滿足循環(huán)進(jìn)入條件，可以用是否進(jìn)入循環(huán)的測(cè)試條件來保護(hù)前置塊，即識(shí)別終止條件是否一開始就為false，來保護(hù)它。這種方法總是安全的，但增加了代碼體積。不過若終止條件恒為true或false，則常數(shù)傳播分析會(huì)刪除這個(gè)冗余測(cè)試，如果為false，那么還會(huì)刪除前置塊