[其他]通過雙色布石進行寄存器分配和指定

無效

• 申請號: 86107764
• 申請日: 1986-11-14
• 公開（公告）號: CN86107764A
• 公開（公告）日: 1987-07-01
• 發明（設計）人: 阿施法·阿布杜里曼·穆施;卡爾·馬克斯·施姆普福
• 申請（專利權）人: 國際商用機器公司
• 主分類號: G06F12/02
• 分類號: G06F12/02
• 代理公司: 中國國際貿易促進委員會專利代理部
• 代理人: 余剛

本發明涉及一種方法，在一個無向量或向量處理器中利用該方法，可以在源代碼到機器可執行代碼的編譯期間分配及優化寄存器指定。

在編譯程序構造的標準著作中，艾迪生-韋斯利出版公司1977年版，由愛荷等人所寫的“編譯程序設計的原理”一書和斯普林格-弗萊格1984年版，由韋特等人所著的“編譯程序構造”一書中都指出，計算機源語言，例如PASCAL或FORTRAN，到可由目標機器執行的代碼的轉換是通過一系列變換來完成的。首先對源符號串進行詞法分析，為翻譯確定出原子單位或字，然后進行句法分析，確定出這些字之間的語法關系。輸出是以“分析樹”的形式表示的。該分析樹被轉換為源代碼的中間語言表現形式。大多數編譯程序并不明顯地產生分析樹，而當進行句法分析時形成中間代碼。優化施加于中間代碼，而后產生目標機器可執行代碼或目標代碼。

編譯程序必須執行的任務中包括計算資源的分配和指定，以便由源代碼指令流所確定的計算能夠高效率地完成。有效“資源”中包括計算設備，例如ALU，輸入/輸出，包括寄存器的存貯器，操作系統成份等等。編譯程序的優化部分的任務是（a）縮短代碼長度，（b）在可能的地方增加執行速度，（c）通過資源的高效率分配，將開銷降至最低程度。然后，資源使用或消耗程式一覽表被送入正在編譯的代碼中。

眾所周知，指令流可以被映成圖形結構，并可利用圖論特性的優越性。代碼序列在局部優化中可以用基本程序塊的圖形性質進行分析而在全程優化中則可用程序塊的流程圖分析。

一個基本程序塊是一個連續語句序列。該序列只能從頭開始進入，共且在進入后語句是順序執行的，除非到了結尾，否則不能停止或轉移。

流程圖描述了在基本程序塊之間的控制流。例如，流程圖將表示出基本程序塊之間迭代或遞歸計算所需的循環，轉移和嵌套。

數據相關性的無回路有向圖（DAG）是一數據結構，用于分析基本程序塊。例如，a＝S+C由作為起始節點的b+c表達，每一節點通過各自的邊連接于公共節點c。這不是流程圖，雖然流程圖的每個節點（基本程序塊）可以由一個DAG表示。

“活變量分析”涉及一組技術，該組技術用于確定一個變量名是否具有一個經常在以后的計算中可能用到的值。如果一個變量名在基本程序塊中重新定義之前被使用，或者“活”著離開這一程序塊而未在程序塊中被重新定義，則該變量被認為是“活”著進入程序塊的。因此，一數值在寄存器中被計算之后，并假定在一基本程序塊中已被使用過，如果它在程序塊的結尾“死”了的話，則沒必要存貯該數值。也即如果全部寄存器都已裝滿，而還需要另一個寄存器，則可指定當前含有“死”值的寄存器。

從概念上講，第一個編譯程序變換是將源代碼串映成流程圖，其流程圖的每一節點都是基本程序塊，其控制及數據路徑關系由流程圖的有向邊確定。資源分配和指定的優化工作可以首先在局部或基本程序塊這級進行，然后再在全程流程圖一級進行。

在局部優化中，每一基本程序塊被當作一個獨立的單位，并在優化中不考慮程序塊的內容。為基本程序塊建立的數據相關圖被變換并用以產生最終機器代碼。然后被廢棄，再進行下一個基本程序塊。“數據相關圖”是一個基本程序塊中的一種圖論特征表示。由于一個基本程序塊不能包含循環，因而所有“數據相關圖”的基本塊可以由DAG來表示。而DAG不必是樹。作為示例，如果一個基本程序塊由兩條計算語句x＝u+v和y＝u+w組成，雖然它是無回路的，DAG仍將不是樹。最后，全程優化執行一個流程圖的全程重排，并在基本程序塊之間提供上下文信息。

計算機包括主存貯器，其最快的形式是最昂貴的。若干有限的物理寄存器存貯操作數，以備計算和控制的立即使用。從寄存器到寄存器操作的計算機指令是最快速執行的。如果無法獲得一個寄存器，則中間結果必須被裝入主存貯器，大部分程序體及數據定位于該主存，或者當一個寄存器可以得到時，將中間結果從所述主存轉入該寄存器。從主存到寄存器的裝入及從寄存器到主存貯器的存貯需要更長一些的時間。因此，在評價一個流程圖或基本程序塊時，目標之一是在寄存器中保存盡可能多的計算名即變量，或保證在需要時可以獲得一個寄存器。