一種針對受限制的索引尋址模式的偏移量分配優化方法
2023-05-04 08:36:06
專利名稱：一種針對受限制的索引尋址模式的偏移量分配優化方法
技術領域：
本發明涉及一種尋址操作編譯優化、偏移量分配(Offset Assignment)優化方法，特別涉及一種針對「受限制的索引尋址模式」的偏移量分配優化方法。
背景技術：
由於嵌入式處理器的片上存儲容量有限，因此如何減少代碼大小是編譯器為嵌入式處理器生成代碼時需要考慮的一個因素。偏移量分配優化，就是通過重新分配變量在存儲器中的位置，從而最大化的利用處理器提供的特定尋址模式來優化尋址代碼的一種優化方法。
偏移量分配優化最早由文獻1[S.Liao，S.Devadas，K.Keutzer，S，Tjiang，A.Wang.Storage Assignment to Decrease Code Size.ACM SIGPLAN Conferenceon Programming Language Design and Implementation，1995]提出，是針對部分嵌入式處理器提供的自增/自減(autoincrement/autodecrement)尋址模式的一種優化方法。自增/自減尋址模式是指指令在訪問地址寄存器所指向地址的同時，地址寄存器的值自增或自減k(通常k＝1)。充分利用自增/自減尋址模式來訪存，可以減少顯式的地址計算。所以，通過重新分配變量在存儲器中的位置，使得儘可能多的利用自增/自減尋址模式來進行訪存，能夠減少代碼大小，提高代碼效率。
有一些嵌入式處理器，如Intel IXP 2400，除了支持自增/自減尋址模式外，還支持一種特殊的索引尋址模式，即基地址+偏移量的尋址模式，我們將這種特殊的索引尋址模式稱為「受限制的索引尋址模式」。不同於一般的通用處理器中索引尋址模式的是，「受限制的索引尋址模式」對基地址和偏移量有一定的限制偏移量為0到m-1之間的一個常數(m為一個常數，比如16)，而基地址必須是m字(word)的倍數。如果將要訪問的變量的地址與基地址的偏移量不在0到m-1之間，則我們需要重新設定基地址，即重新設定地址寄存器。針對這種「受限制的索引尋址模式」，也可以進行偏移量分配優化，但目前尚未有文獻公開。
文獻2[Y.choi，T.Kim，H.Han.Memory Layout Techniques for VariablesUtilizing Efficient DRAM Access Modes in Embedded System Design.IEEETransactions on Computer-Aided Design of Integrated Circuits and Systems，Vol.24，NO.2，Feb 2005]曾對類似的問題進行過研究。該文獻2是針對一些嵌入式系統中對訪問動態隨機存儲器(DRAM)提供的一種頁模式(page mode)優化方法。頁模式是指當前訪問動態隨機存儲器中的變量和上一次訪問的變量處在同一頁時，可以使用的一種比普通模式更為高效的一種訪存模式。與「受限制的索引尋址模式」有所不同的是，頁模式的使用是由硬體來負責的，在生成的代碼中沒有體現。所以，針對這種頁模式的偏移量分配優化不能減少代碼大小，僅可以提高程序性能。
文獻2提出的針對頁模式的優化方法主要思想如下首先提取出動態隨機存儲器中變量的訪問序列(access sequence)；再根據訪問序列構造訪問圖(accessgraph)，圖上的頂點對應訪問序列中出現的變量，邊上的權重代表相應兩個頂點在訪問序列中出現相鄰的次數；然後根據一定的算法將訪問圖劃分成若干個頂點數目不超過m的子圖(m為頁模式中一頁的大小)，使得各個子圖之內的頂點構成的子圖之內邊的權重之和最大；最後，變量在動態隨機存儲器中的位置就按上一步中確定的劃分進行分配，每個子圖的頂點相應的分成一頁。
文獻2優化方法的核心算法就是將訪問圖劃分成若干個子圖的算法，給出了一個啟發式算法，算法進行的是循環求解，每個循環劃分出一個子圖。用attract_in(P，x)表示頂點x與當前子圖P內所有頂點構成的邊上的權重之和，用attract_out(P，x)表示頂點x與當前子圖P外所有頂點構成的邊上的權重之和。在每個循環的開始，找出權重最大的一條邊，將這條邊的兩個節點加入P。以後每次選擇attract_in值最大的節點加入到P中。當attract_in值最大的節點有多個的時候，如果當前選擇的不是子圖中的最後一個節點，則隨機選這些節點中的一個；否則，選擇這些節點中attract_out值較小的那個。
由於實際程序中出現有多個attract_in值最大的節點的情況比較多，對這些節點的選擇採用隨機的方法並不合理，降低了優化的效果。同時，當選擇子圖中的最後一個節點時，文獻2公開的方法中也存在問題，實際上，這最後一個節點並不是選擇attract_in值越大的越好。如圖1(a)、(b)所示，說明了文獻2的不足之處按照文獻2的算法，先將頂點a，c加入頁，在考慮加本組的最後一個節點的時候，因為頂點d的attract_in值大於b的attract_in值，所以選擇頂點d，形成了頂點a、c、d在一個頁，頂點b、e在另一個頁的布局，兩個子圖之間的頂點構成的邊的權重之和為4，如圖1(a)所示。但是，如果最後一步選擇頂點b，則兩個子圖之間的頂點構成的邊的權重之和為3，如圖1(b)所示，顯然比前一選擇更好。
綜上所述，在現有針對頁模式的偏移量分配優化方法中，存在對頁劃分不合理的問題，從而降低了編譯優化的性能。
發明內容
本發明的目的是克服現有針對頁模式的偏移量分配優化方法中存在對頁劃分不合理的問題，從而提供一種採用改進圖劃分算法的針對「受限制的索引尋址模式」的偏移量分配優化方法。
為了實現上述目的，本發明採取如下技術方案一種針對受限制的索引尋址模式的偏移量分配優化方法，包括以下步驟1.對存儲器中的所有變量形成訪問圖；2.新建一個組group，找出當前訪問圖中權重最大的一條邊，將它的兩個頂點加入組group，並將這兩個頂點標記為已分配；3.選取一個未分配的節點x，判斷是否滿足下列四種情況之一(1)將要選取的節點不是組group的最後一個節點；且節點x是所有未分配節點中與當前組group內所有節點構成的邊上的權重之和最大的節點；(2)當前組group中節點的數目小於「受限制的索引尋址模式」中利用同一個基地址最多能訪問變量的數目m的1/2；且節點x是所有未分配節點中與當前組group內部所有節點構成的邊上的權重之和最大的節點之一；且節點x是所有未分配節點中與當前組group外部所有節點構成的邊上的權重之和最大的節點；(3)將要選取的節點是組group的最後一個節點；且節點x與組group內部的所有節點的總權重減去節點x與組group外部的所有未分配節點的總權重的差值是所有未分配節點中最大；(4)將要選取的節點是組group的最後一個節點；且節點x是所有未分配節點中與組group內部節點和外部節點的總權重差值最大的節點之一；且節點x是所有未分配節點中與當前組group內所有節點構成的邊上的權重之和最大的節點；將滿足上述四種情況之一的節點x加入組group，並將節點x在訪問圖中標記為已分配；4.重複執行步驟3，直到組group中的變量數已滿，即達到一個基地址最多能訪問變量的數目m；
5.組group中的變量形成一個子圖，將組group中的變量在存儲器中相應地分成一組，將組group中的所有節點以及相應的邊從訪問圖上刪除；6.重複執行步驟2，直到將訪問圖中的節點全部分配完畢。
在上述技術方案中，步驟1的執行過程為遍歷要編譯的程序單元，遇到對存儲器中變量v的一次訪問，假設上一次訪問到的存儲器中變量為u，則將新增邊u，v加入訪問圖。
在上述技術方案中，如果優化的首要目的是減少代碼大小，則所述新增邊u，v的權重設為1。
在上述技術方案中，如果優化的首要目的是提高代碼執行效率，則所述新增邊u，v的權重設為其所在基本塊的執行頻率，或者為兩個變量分別所在的兩個基本塊之間控制邊的執行頻率。
與現有技術相比，本發明的有益效果在於本發明在對訪問圖進行劃分的時候，考慮了attract_in值相等的情況下，若當前組中節點的數量小於可允許最大數量的一半，則優先選取attract_out值最大的節點，有助於減少不同子圖間的頂點構成的邊的權重；而對於每個組最後一個節點，選擇attract_in-attract_out最大的節點則更為合理，對attract_in-attract_out相等的情況，優先選擇attract_in最大者，這樣也減少了不同子圖間的頂點構成的邊的權重。本發明減少了對地址寄存器的設定操作，優化了代碼，從而提高了編譯優化性能。
圖1(a)、(b)表示使用文獻2的方法對訪問圖進行劃分的不足之處；圖2(a)是具體實施例中對存儲器中變量的訪問序列的示意圖；圖2(b)是圖2(a)中訪問序列所對應的訪問圖；圖2(c)是本發明實施前的變量在存儲器中排列情況的示意圖；圖2(d)是本發明實施前生成代碼中有關存儲器訪問的代碼片斷示意圖；圖3(a)是採用文獻2的方法對圖2(b)中訪問圖的劃分結果的示意圖；圖3(b)是採用文獻2的方法後的變量在存儲器中排列情況的示意圖；圖3(c)是採用文獻2的方法後生成代碼中有關存儲器訪問的代碼片斷示意圖；圖4(a)是本發明實施後對圖2(b)中訪問圖的劃分結果的示意圖；
圖4(b)是本發明實施後的變量在存儲器中排列情況的示意圖；圖4(c)是本發明實施後生成代碼中有關存儲器訪問的代碼片斷示意圖；圖面說明圖2(a)中，a，b，c，d，e，f代表存放在存儲器中的變量；圖2(d)中，指令LOAD AR，0表示將地址寄存器AR的值賦0；0(AR)表示以地址寄存器AR中的值為基地址，訪問相對於基地址的偏移量為0的那個變量。
圖3(c)和圖4(c)中，指令的意思同圖2(d)中所述；具體實施方式
下面結合附圖和具體實施方式
對本發明作進一步詳細描述針對「受限制的索引尋址模式」的偏移量分配優化方法，本實施例的目標是使生成代碼中對地址寄存器的設定操作最小化。根據現有工作，本發明採用改進的圖劃分方法來實現偏移量分配，此時圖劃分的目標即使得不同子圖間的頂點構成的子圖間邊的權重之和最小化。而已有的針對頁模式的優化方法中，圖劃分的目標為使得各個子圖之內的頂點構成的子圖之內邊的權重之和最大化，這與本發明的方法中的使得不同子圖間的頂點構成的子圖間邊的權重之和最小化的目標實質上是等價的。所以本發明利用已有的針對頁模式的優化方法來進行圖劃分，進而實施偏移量分配優化，但由於針對頁模式的優化方法中存在一些問題，本發明對其進行了改進。對與組group內的節點形成的邊的權重之和即attract_in值相等時節點的選擇和對於每個組最後一個節點的選擇作了更細緻的考慮，提高了優化效果。
本實施例的針對「受限制的索引尋址模式」的偏移量分配優化方法其中，v表示指令訪問的存儲在存儲器中的一個變量；last_access_variable表示相對於v的上一次訪問的存儲器中的變量；m表示使用「受限制的索引尋址模式」時利用同一個基地址最多能訪問的變量的數目；group表示當前處理的組；|group|表示組group中節點的數量；x表示一個尚未分配的節點；max_node表示目前為止選擇的準備加入組group的節點；attract_in(group，x)表示節點x與當前組group內所有節點構成的邊上的權重之和；attract_out(group，x)表示節點x與當前組group外所有節點構成的邊上的權重之和；P表示已經劃分出來的所有組group的集合。
本實施例的方法包括步驟如下1)置變量last_access_variable的值為-1；(變量last_access_variable用來記錄上一次訪問的存儲器中的變量，初始時last_access_variable的值設為-1。)2)判斷程序單元中所有指令是否都已處理過？如果是，執行步驟7)；如果否，執行下一步；3)讀入一條指令，判斷指令中是否存在對存儲器的訪問？若是，執行下一步；若否，執行步驟2)；4)記錄當前指令中訪問的變量v，判斷last_access_variable的值是否為-1？若否，執行下一步；若是，執行步驟6)；5)將邊last_access_variable，v加入到訪問圖中；如果優化的首要目的是較少代碼大小，則這條新增邊的權重為1；如果優化的首要目的是提高代碼執行效率，則這條新增邊的權重為其所在基本塊的執行頻率，或者為兩個變量分別所在的兩個基本塊之間控制邊的執行頻率；本實施例中，新增邊的權重為1；6)置last_access_variable為當前指令中訪問的變量v，執行步驟2)；7)判斷訪問圖的頂點集是否為空？若是，執行步驟17)；若否，執行下一步；8)判斷訪問圖的頂點數目是否小於m或者訪問圖中邊的數量是否為0(m表示使用「受限制的索引尋址模式」時，相對於同一個基址能訪問的變量的數量)？如果這兩個條件中的任意一個成立，執行下一步；否則，執行步驟10)；9)將訪問圖中的頂點按照其在程序中出現的先後順序劃分成若干組，並將分成的組加入到已有組的集合P中，執行步驟17)；10)新建一個組group，找出當前訪問圖中權重最大的一條邊，將它的兩個頂點加入新建組group，並將兩個頂點在當前訪問圖中標記為已分配；11)判斷組group中變量的數目是否小於m，若是，執行下一步；若否，執行步驟16)；12)判斷是否已遍歷所有未分配節點？若是，執行步驟15)；若否，執行下一步；13)選取一個未分配節點x，判斷是否滿足下面四種情況之一①group中變量的數目小於m-1且attract_in(group，x)值大於attract_in(group，max_node)；②group中變量的數目小於m/2且attract_in(group，max_node)等於attract_in(group，x)且attract_out(group，x)大於attract_out(group，max_node)；③group中變量的數目等於m-1且attract_in(group，x)-attract_out(group，x)大於attract_in(group，max_node)-attract_out(group，max_node)；④group中變量的數目等於m-1且attract_in(group，x)-attract_out(group，x)等於attract_in(group，max_node)-attract_out(group，max_node)且attract_in(group，x)大於attract_in(group，max_node)；滿足上述四種情況之一，執行下一步；否則，執行步驟12)；14)置max_node為x，執行步驟12)；15)將max_node加入group，並將max_node標誌為已分配，執行步驟11)；16)將group加入已有組的集合P中，將group中的所有節點以及相應的邊從訪問圖上刪除，執行步驟7)；17)根據P決定變量在存儲器中的分布，結束。
下面結合附圖，說明本實施例的優化效果。
圖2(a)表示了在圖2、3、4中用到的訪問序列為S＝{a，b，c，d，e，f，c，b，f，c，f，e，d}，m＝4；圖2(b)則為訪問序列S所對應的訪問圖。
圖2(c)中所示變量的分布未作優化，它是按照變量在訪問序列中第一次出現的先後順序來決定的。如圖所示，變量a、b、c、d在一個組，e、f在另一個組。對於這種變量分布，圖2(d)顯示了相應生成代碼中的訪存部分的片斷，可以看出，除了程序開始時對地址寄存器的初始化設定操作，程序中還需要6條額外的對地址寄存器進行設定的指令。
圖3(a)所示為採用文獻2的方法對訪問圖的劃分結果c、f、b、e構成一個子圖，a、d構成另外一個子圖。圖3(b)表示了對應於圖3(a)中圖劃分，即使用文獻2的方法進行優化後，變量在存儲器中的分布情況。對於這種分布，圖3(c)顯示了相應生成代碼中的訪存部分的片斷，如圖所示，程序需要4條額外的對地址寄存器進行設定的指令。
圖4(a)所示為採用本發明對訪問圖的劃分結果，c、f、b、a構成一個子圖，d、e構成另外一個子圖。圖4(b)表示了對應於圖4(a)中的圖劃分，即使用本發明進行優化後，變量在存儲器中的分布情況。對於這種分布，圖4(c)顯示了相應生成代碼中的訪存部分的片斷，如圖所示，程序中僅需要3條額外的對地址寄存器進行設定的指令。
將圖4(c)與圖3(c)進行對比，即可看出本發明相對已有方法的改進。
權利要求
1.一種針對受限制的索引尋址模式的偏移量分配優化方法，包括以下步驟1)對存儲器中的所有變量形成訪問圖；2)新建一個組group，找出當前訪問圖中權重最大的一條邊，將它的兩個頂點加入組group，並將這兩個頂點標記為已分配；3)選取一個未分配的節點x，判斷是否滿足下列四種情況之一(a)將要選取的節點不是組group的最後一個節點；且節點x是所有未分配節點中與當前組group內所有節點構成的邊上的權重之和最大的節點；(b)當前組group中節點的數目小於「受限制的索引尋址模式」中利用同一個基地址最多能訪問變量的數目m的1/2；且節點x是所有未分配節點中與當前組group內部所有節點構成的邊上的權重之和最大的節點之一；且節點x是所有未分配節點中與當前組group外部所有節點構成的邊上的權重之和最大的節點；(c)將要選取的節點是組group的最後一個節點；且節點x與組group內部的所有節點的總權重減去節點x與組group外部的所有未分配節點的總權重的差值是所有未分配節點中最大；(d)將要選取的節點是組group的最後一個節點；且節點x是所有未分配節點中與組group內部節點和外部節點的總權重差值最大的節點之一；且節點x是所有未分配節點中與當前組group內所有節點構成的邊上的權重之和最大的節點；將滿足上述四種情況之一的節點x加入組group，並將節點x在訪問圖中標記為已分配；4)重複執行步驟3)，直到組group中的變量數已滿，即達到一個基地址最多能訪問變量的數目m；5)組group中的變量形成一個子圖，將組group中的變量在存儲器中相應地分成一組，將組group中的所有節點以及相應的邊從訪問圖上刪除；6)重複執行步驟2)，直到將訪問圖中的節點全部分配完畢。
2.根據權利要求1所述的針對受限制的索引尋址模式的偏移量分配優化方法，其特徵在於，所述步驟1)的執行過程為遍歷要編譯的程序單元，遇到對存儲器中變量v的一次訪問，假設上一次訪問到的存儲器中變量為u，則將新增邊u，v加入訪問圖。
3.根據權利要求2所述的針對受限制的索引尋址模式的偏移量分配優化方法，其特徵在於，所述新增邊u，v的權重設為1。
4.根據權利要求2所述的針對受限制的索引尋址模式的偏移量分配優化方法，其特徵在於，所述新增邊u，v的權重設為其所在基本塊的執行頻率，或者為兩個變量分別所在的兩個基本塊之間控制邊的執行頻率。
5.一種針對受限制的索引尋址模式的偏移量分配優化方法，包括以下步驟1)置變量last_access_variable的值為-1；2)判斷程序單元中所有指令是否都已處理過？如果是，執行步驟7)；如果否，執行下一步；3)讀入一條指令，判斷指令中是否存在對存儲器的訪問？若是，執行下一步；若否，執行步驟2)；4)記錄當前指令中訪問的變量v，判斷last_access_variable的值是否為-1？若否，執行下一步；若是，執行步驟6)；5)將新增邊last_access_variable，v加入到訪問圖中；6)置last_access_variable為當前指令中訪問的變量v，執行步驟2)；7)判斷訪問圖的頂點集是否為空？若是，執行步驟17)；若否，執行下一步；8)判斷訪問圖的頂點數目是否小於m或者訪問圖中邊的數量是否為0？其中m表示使用「受限制的索引尋址模式」時，相對於同一個基址能訪問的變量的數量；如果這兩個條件中的任意一個成立，執行下一步；否則，執行步驟10)；9)將訪問圖中的頂點按照其在程序中出現的先後順序劃分成若干組，並將分成的組加入到已有組的集合P中，執行步驟17)；10)新建一個組group，找出當前訪問圖中權重最大的一條邊，將它的兩個頂點加入新建組group，並將兩個頂點在當前訪問圖中標記為已分配；11)判斷組group中變量的數目是否小於m，若是，執行下一步；若否，執行步驟16)；12)判斷是否已遍歷所有未分配節點？若是，執行步驟15)；若否，執行下一步；13)選取一個未分配節點x，判斷是否滿足下面四種情況之一①group中變量的數目小於m-1且attract_in(group，x)值大於attract_in(group，max_node)；②group中變量的數目小於m/2且attract_in(group，max_node)等於attract_in(group，x)且attract_out(group，x)大於attract_out(group，max_node)；③group中變量的數目等於m-1且attract_in(group，x)-attract_out(group，x)大於attract_in(group，max_node)-attract_out(group，max_node)；④group中變量的數目等於m-1且attract_in(group，x)-attract_out(group，x)等於attract_in(group，max_node)-attract_out(group，max_node)且attract_in(group，x)大於attract_in(group，max_node)；滿足上述四種情況之一，執行下一步；否則，執行步驟12)；14)置max_node為x，執行步驟12)；15)將max_node加入group，並將max_node標誌為已分配，執行步驟11)；16)將group加入已有組的集合P中，將group中的所有節點以及相應的邊從訪問圖上刪除，執行步驟7)；17)根據P決定變量在存儲器中的分布，結束。
6.根據權利要求5所述的針對受限制的索引尋址模式的偏移量分配優化方法，其特徵在於，所述新增邊的權重為1。
7.根據權利要求5所述的針對受限制的索引尋址模式的偏移量分配優化方法，其特徵在於，所述新增邊的權重為其所在基本塊的執行頻率，或者為兩個變量分別所在的兩個基本塊之間控制邊的執行頻率。
全文摘要
本發明公開了一種針對受限制的索引尋址模式的偏移量分配優化方法。本發明在對訪問圖進行劃分的時候，考慮了多個頂點與當前子圖內所有頂點構成的邊上的權重之和相等的情況下，若當前組中節點的數量小於可允許最大數量的一半，則優先選取與當前子圖外所有頂點構成的邊上的權重之和值最大的節點，有助於減少不同子圖間的頂點構成的邊的權重；而對於每個組最後一個節點，選擇與組內部的所有節點的總權重減去節點x與組外部的所有未分配節點的總權重的差值是所有未分配節點中最大的節點；對前述差值相等的多個節點，選擇與當前組內所有節點構成的邊上的權重之和最大的節點。
文檔編號G06F9/45GK1877530SQ20051007660
公開日2006年12月13日 申請日期2005年6月10日 優先權日2005年6月10日
發明者包斌, 吳承勇, 劉弢, 張兆慶 申請人:中國科學院計算技術研究所