依賴分析與循環(huán)變換概要課件

依賴分析與循環(huán)變換吳佳駿依賴分析與循環(huán)變換1依賴分析依賴分析是指令調(diào)度和數(shù)據(jù)cache優(yōu)化的一個重要的工具。依賴關(guān)系決定了保證程序正常執(zhí)行時的指令順序。其中包含對于兩個給定的寄存器或者內(nèi)存引用是否訪問了統(tǒng)一區(qū)域,和指令之間的資源沖突。依賴分析也用于程序的向量化和并行化等利用調(diào)整語句順序來提高性能的工作中依賴分類控制依賴數(shù)據(jù)依賴依賴分析2依賴分類控制依賴就是從程序控制流中產(chǎn)生的約束,例如S2對于S3和S4。b+cifa10gotoL1僅在S2的條件不滿足的時候S3d=b*c和S4才被執(zhí)行。如果S1和S2存在控制依賴我們就寫作S1δcS2,S5L1:d=e/2;所以S28S3并且S28s4數(shù)據(jù)依賴是由語句間數(shù)據(jù)流所產(chǎn)生的約束,例如S3和S4之間S3賦值給d然后S4使用它,同樣S4對e賦值S3使用它。在這兩種凊況下改變語句的順序都會造成程序運行時產(chǎn)生錯誤的結(jié)果。依賴分類3數(shù)據(jù)依賴分類依賴:如果S1S2并且前面的語句定值后面的語句使那個值,這種就叫做流依賴,表示為S1反依賴:如果S1←S2并且S1使用S2設(shè)定的值,我們就說這里存在反依賴,寫作S出依賴:如果S1←S2并且它們都對同樣的變量賦值,就說這里存在輸出依賴,寫作S1δ°S2輸入依賴:如果S1S2并且它們都讀取同樣的值,我就說這里存在輸入依賴要注意的入依賴對語句并沒有限制語句的執(zhí)行順序,但是它對數(shù)組元素的標量替換有用數(shù)據(jù)依賴分類4依賴圖組依賴關(guān)系集合可以用一個有向圖來表示,我們把這圖叫做依賴圖。在圖中節(jié)點表示語句邊表示依賴關(guān)系。每條邊都被標記來表示依賴類型,除了流依賴未被標記?？刂埔蕾囃ǔ１缓雎缘舫强刂埔蕾囀莾蓚€節(jié)點之間的唯一依賴關(guān)系a=b+cifa10gotoL1d=b'ce=d+1依賴圖5依賴圖依賴圖6基本塊依賴DAG在依賴DAG中節(jié)點表示機器指令或者低等級的中間代碼,它的邊表示指令之間的依賴關(guān)系條從1到2的邊可能有如下幾種依賴關(guān)系對一個12用的寄存器或者地址寫值,118121使用一個2改變了值的地址或者寄存器l1和12對同一個地址或者寄存器賦值我們不能確定11是否能移動到2前,例如用不同寄存器r1和r12+12]訪問地址。除非我們可以肯定它們指向不同的地址,否則我們就認定它們之間存在依賴關(guān)系基本塊依賴DAG7DAG如果必須等到|執(zhí)行一些時鐘周期后才能執(zhí)行我們1r3=[r15](4)2r4=[15+41(4)就說在DAG中是12的前3r2=r3-r4驅(qū)。在DAG中我們忽略掉r5=[r12]依賴邊的類型。而是用5r12=r12+4和12之間正確執(zhí)行的最小6r6=r3*r5時鐘周期間隔來標記邊15+4]=38r5=r6+2例如必須等到|執(zhí)行2時鐘周期后才能執(zhí)行,我們就標記這條邊為1。在中我們假設(shè)一個oad指令要兩個周期完成DAG8119在例子中指令1和2是相互獨立的,因為他們訪問的是不同的地址。指因為它使用了1的結(jié)果存在2訪間的地址拜直有可能和4訪問的從4到6的邊和一條6到8的邊。但是如么這條邊就不算是多余的,因為1,2,4,5,6,7,8,3和1,2,4,5,6,8,7,3都是可行的,但是第一個要8個時鐘周期但是第二個需要9個時鐘周期。在例子中指令1和2是相互獨立的,因為他們訪問的是不同的地址。10依賴分析與循環(huán)變換概要課件11依賴分析與循環(huán)變換概要課件12依賴分析與循環(huán)變換概要課件13依賴分析與循環(huán)變換概要課件14依賴分析與循環(huán)變換概要課件15依賴分析與循環(huán)變換概要課件16依賴分析與循環(huán)變換概要課件17依賴分析與循環(huán)變換概要課件18依賴分析與循環(huán)變換概要課件19依賴分析與循環(huán)變換概要課件20依賴分析與循環(huán)變換概要課件21依賴分析與循環(huán)變換概要課件22依賴分析與循環(huán)變換概要課件23依賴分析與循環(huán)變換概要課件24依賴分析與循環(huán)變換概要課件25依賴分析與循環(huán)變換概要課件26依賴分析與循環(huán)變換概要課件27依賴分析與循環(huán)變換概要課件28依賴分析與循環(huán)變換概要課件29依賴分析與循環(huán)變換概要課件30依賴分析與循環(huán)變換概要課件31依賴分析與循環(huán)變換概要課件32依賴分析與循環(huán)變換概要課件33依賴分析與循環(huán)變換概要課件34依賴分析與循環(huán)變換概要課件35依賴分析與循環(huán)變換概要課件36依賴分析與循環(huán)變換概要課件37依賴分析與循環(huán)變換概要課件38依賴分析與循環(huán)變換概要課件39依賴分析與循環(huán)變換概要課件40依賴分析與循環(huán)變換概要課件41依賴分析與循環(huán)變換概要課件42依賴分析與循環(huán)變換概要課件43依賴分析與循環(huán)變換概要課件44依賴分析與循環(huán)變換概要課件45依賴分析與循環(huán)變換概要課件46依賴分析與循環(huán)變換概要課件47依賴分析與循環(huán)變換概要課件48依賴分析與循環(huán)變換概要課件49依賴分析與循環(huán)變換概要課件50依賴分析與循環(huán)變換概要課件51依賴分析與循環(huán)變換概要課件52依賴分析與循環(huán)變換概要課件53依賴分析與循環(huán)變換概要課件54依賴分析與循環(huán)變換概要課件55依賴分析與循環(huán)變換概要課件56依賴分析與循環(huán)變換概要課件57依賴分析與循環(huán)變換概要課件58依賴分析與循環(huán)變換概要課件59依賴分析與循環(huán)變換概要課件60依賴分析與循環(huán)變換概要課件61依賴分析與循環(huán)變換概要課件62依賴分析與循環(huán)變換概要課