程序變換方法和程序變換系統的製作方法
2023-06-04 23:14:01 1
專利名稱：程序變換方法和程序變換系統的製作方法
技術領域：
本發明一般涉及一種程序變換方法，一種程序變換系統，和一種存儲程序變換程序的存儲介質。具體地講，本發明涉及一種用於把由程式語言描述的源程序變換(編譯)為由計算機、中央處理器(CPU)等可執行的語言(機器語言、彙編語言等)描述的目標程序的程序變換方法和程序變換系統。
圖15是日本未審查專利公開1-118931中公開的一種現有程序變換系統的結構實例的方框圖。
圖15中所示的程序變換系統是由一個第一程序存儲部分151，一個編譯器152，一個第二程序存儲部分153，一個第三程序存儲部分154，一個輸入數據存儲部分155，一個程序執行部分156，一個第四程序存儲部分157，和一個剖析(parsing)結果存儲部分158構成的。
首先，編譯器152從第一程序存儲部分151讀出一個由C語言之類的程式語言描述的源程序，臨時地產生一個由機器語言、彙編語言之類的語言描述的目標程序，並且把臨時產生的目標程序存儲在第二程序存儲部分153。
在這裡，臨時產生的目標程序是通過把源程序以描述的順序次序變換為機器語言、彙編語言等的代碼而產生的程序。儘管臨時產生的目標程序是可以由計算機、中央處理器(CPU)等執行的，由於只是把源程序變換成源程序代碼順序次序的代碼，所以它固有的冗餘部分使得以臨時產生形式保持的整體目標程序的長度(代碼量)很大。因此適於存儲臨時產生的目標程序的主存儲器需要大的存儲容量。此外，目標程序執行周期變得很長，因而降低了效率。
因此，需要產生一種有效和優化的目標程序。此後把上述處理中從源程序變換為依照源程序中描述的順序次序代碼的目標程序稱為「臨時目標程序」，以區別於優化後的最終目標程序。
有各種優化目標程序的方法。在這裡，在一個過程中對指令的排列優化編碼。過程的意思是指計算機或CPU要執行的算術運算之類的一組處理，通常稱為函數或子程序。在整個說明書和權利要求中，將把這種處理組統稱為「過程」。
在一個程序中，在程序的某一部分的一些過程(此後稱為「主調用(caller)」輔助過程)的執行中需要調用其它過程(此後稱為「被調用(callee)」輔助過程)。因此，當把源程序變換成目標程序並把所得的目標程序存儲在主存儲器中時，如果一個主調用輔助過程的指令代碼和一個與前者最為相關的一個主調用輔助過程的指令代碼物理地相互緊挨著排列，那麼一個過程調用指令可以從長跳轉指令變為短跳轉指令。
通過這種改變可以減少整個目標程序的代碼量。結合這種改變，在計算機或CPU中執行目標程序的執行速度可以是較高的。把將來具有很可能相繼執行的指令代碼排列在目標程序的物理上緊挨的位置上稱為過程指令代碼的排列優化。
接下來，程序執行部分156從第四程序存儲部分157讀出一個過程調用頻率剖析程序，並執行之。即，程序執行部分156從第二程序存儲部分153讀出臨時目標程序。與之結合，程序執行部分156還讀出存儲在輸入數據存儲部分155中由操作員輸入的輸入數據。然後，程序執行部分156模擬臨時目標程序的執行，並且結合這種模擬執行，累計臨時目標程序中某一過程中其它過程的調用發生的次數。把累計的結果作為過程參考頻率剖析結果存儲在剖析結果存儲部分158中。
藉此，編譯器152從剖析結果存儲部分158讀出過程參考頻率剖析結果，以計算任意兩個過程之間的參考關係的緊密性。根據所得的緊密性，進行指令代碼的排列優化，以產生最終目標過程，存儲在第三程序存儲部分154中。
另一方面，圖16是日本未審查專利公開9-34725中公開的一個現有程序變換系統的結構實例的方框圖。
圖16中所示的程序變換系統一般是由一個源程序存儲部分161，一個編譯器162和一個目標程序存儲部分163構成的。
編譯器162一般是由一個剖析部分164，一個過程調用發生計數部分165，一個代碼產生部分166，一個過程調用計數數據存儲部分167，一個特定空間排列程序確定部分168，一個目標程序輸出部分169構成的。在這裡，一個特定空間的意思是設定在一個程序空間的一部分中的一個有限代碼量的特定區。
剖析部分164從源程序存儲部分161讀出要剖析的源程序，並且剖析形成源程序的語法。過程調用計數部分165計算在剖析語法時剖析部分164識別出的每個過程的有關過程的調用次數。
代碼產生部分166進行兩次代碼產生。即，在第一次代碼產生，根據剖析部分164的剖析結果，如果語法不是過程調用指令，代碼產生部分166產生一個正常代碼，而如果語法是過程調用指令，則使用正常調用指令產生一個指令代碼。另一方面，代碼產生部分166在第二代碼產生中從開始端掃描第一次代碼產生的結果。然後，如果代碼是過程調用指令，並且訪問特定空間排列過程確定部分168的結果顯示過程是確定要排列在特定空間中的特定空間排列過程，用一個指定的具有小字節計數的調用指令代碼替換具有大字節計數的正常調用指令代碼。
過程調用計數數據存儲部分167存儲過程調用發生計數部分165計算的每個過程的調用次數，和在第一代碼產生中產生的代碼的代碼量。特定空間排列過程確定部分168根據存儲在過程調用計數數據存儲部分167中的調用計數和代碼量，通過給予具有較大調用計數的過程優先次序因而使得要在特定空間中排列的過程的代碼量的總和落在特定空間的代碼量範圍內的方法，選擇和確定要排列在特定空間內的過程。
目標程序輸出部分169，在訪問特定空間排列過程確定部分168的結果顯示代碼產生部分166產生的代碼是特定空間排列過程的一個定義部分的代碼的時候，輸出代碼給附加了該特定空間排列屬性的段，並且在代碼產生部分166產生的代碼不是特定空間排列過程的確定部分的代碼時，輸出一個正常段。在這裡，段的意思是當把代碼排列在程序空間時作為排列的最小單元的一組代碼。
如上所述，目標程序輸出部分166分隔了特定空間排列過程和正常過程。接下來，目標程序輸出部分169輸出參數區之類的數據，輸出組合為目標程序的一個代碼部分和一個數據部分，並存儲在目標程序存儲部分163中。
利用上述的構造，可以減小產生的目標程序的代碼量。結合這種構造，可以節省程序空間。並且可以提高計算機或CPU執行目標程序的執行速度。
另一方面，在日本未審查專利公開1-118931公開的現有程序變換系統中，由於進行過程的指令代碼的排列優化的目標只是使用者在源程序中定義的過程，這限制了目標程序效率的改進。
另一方面，在日本未審查專利公開9-34725公開的現有程序變換系統中，由於特定空間具有有限的代碼量，因而限制了要在特定空間內排列的過程。因此，限制了目標程序的效率的提高。
另一方面，當要用一個由CPU，解碼器等構成的單片微型計算機執行程序變換系統產生的目標程序時，目標程序被存儲在外主存儲器中，使得能夠順序地從主存儲器中讀出目標程序的每個代碼。然後，在解碼器解碼後，CPU剖析用於執行的目標程序。在這種情況下，為了提高CPU的執行速度，在單片微型計算機中提供有一個具有小的暫時存儲容量和高存取速度並且存儲從一般具有大的存儲容量和低存取速度的主存儲器讀出的代碼的高速緩衝存儲器。
在裝配有高速緩衝存儲器的單片微型計算機中，在CPU執行代碼時，在從主存儲器讀出的目標程序中的每個代碼存儲在高速緩衝存儲器中之前，解碼器不能對它進行解碼，並且CPU不能剖析和執行它。在這種單片微型計算機中，有各種把從主存儲器讀出的每個代碼存儲在高速緩衝存儲器中的方法。其中，直接映像法是在高速緩衝存儲器中存儲每個代碼的方法之一。
如圖17中所示，在直接映像法中，高速緩衝存儲器171被劃分為多個存儲區(此後稱為高速緩存行)。與此結合，主存儲器172的每個存儲區被劃分。主存儲器172的每個存儲區是對應於高速緩衝存儲器171的每個高速緩存行建立的。
在圖17中，高速緩衝存儲器171是由171a至171e五個高速緩存行組成的。對應於這些高速緩存行，把主存儲器172劃分成每個都具有與每個高速緩存行相同存儲容量的存儲區。以五個為一個單元，每個存儲區對應於相應的五個高速緩存行171a至171e。也就是說，主存儲器172的存儲區172-1a至172-第一實體對應於高速緩存行171a至171e作為一組。同樣，存儲區172-2a至172-第二實體對應於高速緩存行171a至171e。最後的存儲區172-na至172-ne(n是自然數)也對應於高速緩存行171a至171e。
當要用程序變換系統產生使用直接映像法的單片微型計算機執行的目標程序的時候，會遇到以下的缺陷。
例如，當用程序變換系統把圖18中所示的用C語言描述的源程序變換成目標程序時，如圖19中所示，過程func_A和func_B的相應的指令代碼被存儲在主存儲器172中。
在圖19中，過程func_A的指令代碼存儲在主存儲器172的存儲區172-1a至172-1c中。過程func_B的指令代碼也存儲在主存儲器172的存儲區172-2a至172-2b中。因此，過程func_A的指令代碼對應於高速緩衝存儲器171的高速緩存行171a至171c。另一方面，過程func_B的指令代碼對應於高速緩衝存儲器171的高速緩存行171a和171b。
在這種情況下，當CPU執行圖18中所示源程序變換產生的目標程序時，從主存儲器172的存儲區172_1a至172_1c讀出過程func_A的指令代碼和一次存儲在高速緩衝存儲器171的高速緩存行171a至171c中，並且隨後由解碼器解碼和由CPU剖析和執行。
接下來，把過程func_B的指令代碼從主存儲器172的存儲區172_2a至172_2b中讀出，並臨時存儲在高速緩衝存儲器171的高速緩存行171a至171b中。在這裡，由於過程func_A的指令代碼的一部分已經存儲在高速緩衝存儲器171的高速緩存行171a和171b中，因此過程func_B的指令代碼在那裡覆蓋存儲(覆蓋寫入)。因此過程func_A的指令代碼的一部分不能被後續讀出。此後，存儲在高速緩衝存儲器171的高速緩存行171a至171b中的過程func_B的指令代碼被解碼器解碼並由CPU剖析和執行。
接著，圖18中所示的源程序必須再次執行過程func_A的指令代碼。但是，由於過程func_B的指令代碼已經存儲在高速緩衝存儲器171的高速緩存行171a和171b中，因而過程func_A的指令代碼的一部分不能被讀出。因此，再次從主存儲器172的存儲區172_1a至172_1b讀出過程func_A的指令代碼。然後，把過程func_A的指令代碼臨時存儲在高速緩衝存儲器171的高速緩存行171a至171b中，由解碼器解碼和由CPU剖析和執行。
如上所述，當把將來極可能相繼執行的兩個過程的指令代碼存儲在對應於高速緩衝存儲器的相同高速緩存行的主存儲器的存儲區中的時候(這將稱為裝載在相同高速緩存行上)，存儲在高速緩衝存儲器171中的先從主存儲器讀出的指令代碼的全部或一部分，被從主存儲器讀出並且寫在高速緩衝存儲器171的相同高速緩存行上的後續寫入的過程的指令代碼重寫。這種狀況被稱為衝突(高速緩存衝突)。如果這種衝突經常發生，可能會使加快CPU的執行速度的高速緩衝存儲器失效。更糟糕的是，它可能會造成CPU執行速度的降低。
作為在高速緩衝存儲器中存儲從主存儲器讀出的每個代碼的方法，有一種完全相關的允許把主存儲器的數據存儲到高速緩衝存儲器的任何高速緩存行的方法，存在一種用來作為直接映像法與完全相關方法的中間方法的相關方法和排列主存儲器的數據的多個高速緩存行，以及各種可聯合直接映像法使用的方法。如上所述，可能造成高速緩衝存儲器上過程的衝突。
在日本未審查專利公開1-118931和日本未審查專利公開9-34725公開的現有程序變換系統中，沒有考慮到上述的衝突。因此，作為過程指令代碼排列優化或在特定空間中過程排列的結果，如果兩個將來極有可能相繼執行的過程的指令代碼被裝載到高速緩衝存儲器171的相同的高速緩存行上，衝突是固有的。因此，即使能夠減少整個目標程序的代碼量，也不能加快CPU的執行速度。
另一方面，由於指令代碼沒有存儲在高速緩衝存儲器171中，因為衝突而不能讀出指令代碼(這些一般稱為高速緩存丟失)，所以目標程序執行中頻繁使用的過程不能通過每次使用時從主存儲器172讀出指令代碼和存儲在對應的高速緩衝存儲器的高速緩存行中提高CPU的執行速度。因此，需要把頻繁使用的過程儘可能長時間地存儲在高速緩衝存儲器171中，而不造成衝突。
但是，在日本未審查專利公開1-118931和日本未審查專利公開9-34725公開的現有程序變換系統中，對目標程序執行中的高速緩存丟失根本沒有考慮。因此，即使是出於這一點，CPU的執行速度也不能提高。
本發明的目的是要提供一種能夠成功地防止高速緩衝存儲器上不同過程的衝突，能夠防止頻繁使用的過程的高速緩存丟失，因而能夠提高計算機、CPU等執行目標程序的速度的程序變換方法和程序變換系統。
根據本發明的第一方面，一種用於把由程式語言描述的源程序變換為數據處理系統可執行語言描述的目標程序的程序變換方法，包括第一處理，將源程序中使用的至少一部分過程、函數或子程序變換為一種使得目標程序可以被存儲在數據處理系統的主存儲器的任意存儲區中的形式；第二處理，根據在源程序變換為目標程序的處理過程中獲得的有關於過程、函數或子程序的信息，在主存儲器的存儲內中對應於一高速緩衝存儲器的高速緩存行的存儲區中排列第一處理中變換的或未變換的過程、函數或子程序，而不造成高速緩存衝突；和第三處理，根據排列的結果產生目標程序。
在優選構造中，過程、函數或子程序是使用者在源程序中定義的、使用者定義並檢驗的、以程式語言在處理系統中預先準備的、和以指令代碼形式預先準備的過程、函數或子程序中的至少一種。
在另一優選構造中，信息是通過執行從源程序變換的一個臨時目標程序獲得的，並且是由指示過程、函數或子程序實際被調用的次數的信息和指示過程、函數或子程序之間的調用關係的信息構成的。
在再一個優選構造中，信息是通過執行從源程序變換的一個臨時目標程序獲得的，並且是由指示過程、函數或子程序實際被調用的次數的信息和指示過程、函數或子程序之間的調用關係的信息構成的，在第二處理中，根據調用頻率把過程、函數或子程序劃分為多個組，和把過程、函數或子程序排列在主存儲器存儲區中對應於一個高速緩衝存儲器的高速緩存行的存儲區內。
根據本發明的第二方面，一種用於把由程式語言描述的源程序變換為數據處理系統可執行語言描述的目標程序的程序變換方法，包括第一處理，當在數據處理系統中使用目標程序時，將源程序中使用的過程、函數或子程序的至少一部分變換為一種在數據處理系統的一個主存儲器的任意存儲區中存儲的形式；第二處理，將源程序變換為目標程序，和與之結合，關於目標程序，把源程序中使用者定義的過程、函數或子程序變換為可在主存儲器的任意區中存儲的形式；第三處理，連結第一處理中變換的過程、函數或子程序和第二處理中獲得的目標程序；第四處理，利用執行通過第三處理獲得的目標程序，收集由指示過程、函數或子程序實際被調用的次數的信息和指示過程、函數或子程序之間的調用關係的信息構成的動態信息；第五處理，根據動態信息，在主存儲器的存儲區中對應於高速緩衝存儲器的高速緩存行的存儲區中排列過程、函數或子程序，並避免高速緩存衝突；和第六處理，根據排列信息，通過連結第一處理中變換的過程、函數或子程序和在第二處理中獲得的目標程序產生最終目標程序。
在優選構造中，過程、函數或子程序是使用者在源程序中定義的、使用者定義並檢驗的、在處理系統中以程式語言預先準備的、和以指令形式預先準備的過程、函數或子程序中的至少一種。
在另一優選構造中，在第二處理中，根據調用頻率把過程、函數或子程序劃分為多個組，和把過程、函數或子程序排列在主存儲器的存儲區中對應於一個高速緩衝存儲器的高速緩存行的存儲區內。
根據本發明的第三方面，一種用於把由程式語言描述的源程序變換為數據處理系統可執行語言描述的目標程序的程序變換方法，包括第一處理，將源程序變換為一個臨時目標程序，和與之結合，在執行臨時目標程序時，插入過程、函數或子程序實際被調用的次數的計數代碼；第二處理，把使用者在源程序中定義的、使用者定義並檢驗的、在處理系統中以程式語言預先準備的、和以指令代碼形式預先準備的過程、函數或子程序中的一個與通過第一處理獲得的臨時目標程序連結；第三處理，利用執行通過第二處理獲得的目標程序，收集由指示過程、函數或子程序實際被調用的次數的信息和過程、函數或子程序之間的調用關係的信息組成的動態信息；第四處理，根據動態信息，在主存儲器的存儲區中對應於高速緩衝存儲器的高速緩存行的存儲內中排列過程、函數或子程序，並避免高速緩存衝突；和第五處理，把在源程序中將要使用的過程、函數或子程序中由使用者在源程序中定義的一個、由使用者定義並檢驗的一個、在處理系統中以程式語言預先準備的一個、和以指令代碼形式預先準備的一個的至少一部分變換為可在主存儲器的任意存儲區中存儲的一種形式，其中目標程序按照在數據處理系統中實際使用的形式存儲；第六處理，在把源程序變換為目標程序之後，關於目標程序，把使用者在源程序中定義的過程、函數或子程序變換為一種可在主存儲器的任意區中存儲的形式；第七處理，根據排列信息，通過連結第五處理中變換的過程、函數或子程序和第六處理中獲得的目標程序產生最終目標程序。
在該優選構造中，在第四處理中，根據調用頻率把過程、函數或子程序劃分為多個組，和把過程、函數或子程序排列在主存儲器的存儲區中對應於一個高速緩衝存儲器的高速緩存行的存儲區內。
根據本發明的第四方面，一種用於把由程式語言描述的源程序變換為數據處理系統可執行語言描述的目標程序的程序變換系統，包括過程變換裝置，用於將源程序中使用的過程、函數或子程序的至少一部分變換為一種使得目標程序可以被存儲在數據處理系統的主存儲器的任意存儲區中的形式；優化裝置，用於根據在源程序至目標程序的變換處理過程中獲得的有關過程、函數或子程序的信息，把過程變換裝置中變換的或未變換的過程、函數或子程序排列在主存儲器存儲區中對應於一個高速緩衝存儲器的高速緩存行的存儲區中，而不造成高速緩存衝突；和產生裝置，用於根據排列的結果產生目標程序。
在該優選構造中，過程、函數或子程序是使用者在源程序中定義的、使用者定義並檢驗的、預先在處理系統中以程式語言準備的、和預先以指令代碼形式準備的過程、函數或子程序的至少一種。
在另一優選構造中，信息是通過執行從源程序變換的臨時目標程序而獲得的，並且是由指示過程、函數或子程序實際被調用的次數的信息和指示過程、函數或在例程之間的調用關係的信息構成的，在優化裝置中，根據調用頻率把過程、函數或子程序劃分為多個組，和將過程、函數或子程序排列在主存儲器存儲區中的對應於一個高速緩衝存儲器的高速緩存行的存儲區內。
根據本發明的第五方面，一種用於把由程式語言描述的源程序變換為數據處理系統可執行語言描述的目標程序的程序變換系統，包括用於當目標程序在數據處理系統中使用時將源程序中使用的過程、函數或子程序的至少一部分變換為一種用於在數據處理系統的主存儲器的任意存儲區中存儲的形式的過程變換裝置，用於把源程序變換為目標程序，和與之結合，關於目標程序，把使用者在源程序中定義的過程、函數或子程序變換為一種可以存儲在主存儲器的任意存儲區中的形式的程序變換裝置，用於連結在過程變換裝置中變換的過程、函數或子程序和在程序變換裝置中獲得的目標程序的連結裝置，用於利用執行通過連結裝置獲得的目標程序，收集由指示過程、函數或子程序實際被調用的次數的信息和指示過程、函數或子程序之間的調用關係的信息構成的動態信息的動態信息收集裝置，和用於根據動態信息，避免高速緩存衝突地在主存儲器存儲區中對應於高速緩衝存儲器的高速緩存行的存儲區中排列過程、函數或子程序的優化裝置，連結裝置根據排列信息，通過連結在過程變換裝置變換的過程、函數或子程序和在程序變換裝置獲得的目標程序產生最終目標程序。
根據本發明的第六方面，一種用於把由程式語言描述的源程序變換為數據處理系統可執行語言描述的目標程序的程序變換系統，包括用於將源程序變換為一臨時目標程序，和與之結合，在執行臨時目標程序時，插入計算過程、函數或子程序被實際調用的次數的代碼的程序變換裝置；用於將源程序中使用者定義的，使用者定義並檢驗的，在處理系統中以程式語言預先準備的，和以指令代碼形式預先準備的過程、函數或子程序中的一個與通過程序變換裝置獲得的臨時目標程序連結的連結裝置；用於利用執行通過連結裝置獲得的目標程序，收集由指示過程、函數或子程序實際被調用的次數的信息和指示過程、函數或子程序之間的調用關係的信息構成的動態信息的動態信息收集裝置；用於根據動態信息，避免高速緩存衝突地在主存儲器存儲區中對應於高速緩衝存儲器的高速緩存行的存儲區中排列過程、函數或子程序的優化裝置；和用於把要在源程序中使用的過程、函數或子程序中由使用者在源程序中定義的、使用者定義並檢驗的、在處理系統中以程式語言預先準備的、以指令代碼形式預先準備的過程、函數或子程序至少一部分變換為可以存儲在主存儲器的任意存儲區中的一種形式的過程變換裝置，在主存儲器的該存儲區中按照在數據處理系統中實際使用的形式存儲目標程序；程序變換裝置將源程序變換為目標程序，關於目標程序，把使用者在源程序中定義的過程、函數或子程序變換為一種可以存儲在主存儲器的任意區中的形式，連結裝置根據排列信息，通過連結在過程變換裝置變換的過程、函數或子程序和在程序變換裝置中獲得的目標程序產生一個最終目標程序。
從下面給出的詳細描述中可以對本發明的其它目的，特徵和優點有更清楚的了解。
通過下面給出的詳細說明和本發明優選實施例的附圖可以更充分地理解本發明，但是，不應當把優選實施例的附圖作為對本發明的限制，而只是幫助解釋和理解。
在附圖中圖1是顯示根據本發明的程序變換系統的第一實施例的結構的方框圖；圖2是顯示圖1的程序變換系統的第一實施例中使用的一個源程序的實例的示意圖；圖3是顯示圖1的程序變換系統的第一實施例的操作的流程圖；圖4是顯示圖1的程序變換系統的第一實施例中優化部分的一個過程的排列優化處理的流程圖；圖5是顯示被過程A至G佔據的高速緩存行的數量的一個實例的示意圖；圖6是顯示由優化部分產生的過程調用圖的實例的示意圖；圖7是說明圖1中所示的程序變換系統的第一實施例中優化部分中過程的排列優化處理的示意圖；圖8是顯示一個排列信息的實例的示意圖；圖9是說明在不執行過程的排列優化處理時將要造成的缺陷的說明示意圖；圖10是顯示在圖6的過程調用圖中過程C和D是標準庫過程的情況的示意圖；圖11是用於解釋在標準庫過程被置於過程排列優化處理目的之外的情況中的缺陷的示意圖；圖12是顯示根據本發明的程序變換系統的第二實施例的結構的方框圖；圖13是顯示根據本發明的程序變換系統的第三實施例的結構的方框圖；圖14是顯示圖13的程序變換系統的第三實施例的操作的流程圖；圖15是顯示現有程序變換系統的結構的第一實例的方框圖；圖16是顯示現有程序變換系統的結構的第二實例的方框圖；圖17是用於解釋在一個直接映像方法中高速緩衝存儲器與主存儲器之間的關係的示意圖；圖18是顯示一個要在現有技術中使用的源程序是用C語言表達的情況的一個實例的示意圖；和圖19是用於解釋過程在高速緩衝存儲器中衝突的解釋性示意圖。
以下參考附圖通過本發明的優選實施例對本發明進行詳細地討論。在以下的說明中，提出了大量的特定細節，以便提供對本發明的徹底理解。但是，熟悉本領域的技術人員應當明白，可以不用這些特定細節實現本發明。在其它實例中，沒有詳細地示出眾所周知的結構，以避免使本發明模糊。(第一實施例)圖1是顯示根據本發明的程序變換系統的第一實施例的結構的方框圖。
程序變換系統的所示實施例一般是由第一至第四程序存儲部分31至34，編譯器35，連結器36，剖析器37，第一和第二信息存儲部分38和39，優化部分40，第一和第二庫存儲部分41和42，以及庫產生部分43構成的。
第一程序存儲部分31是由包括ROM,RAM等的半導體存儲器、FD(軟盤)、HD(硬碟)、CD-ROM之類的存儲介質構成的。在第一程序存儲部分31中，預先存儲了一個由C語言之類的程式語言描述的源程序。在所示實施例中，將針對C語言作為程式語言的情況進行討論。
編譯器35把源程序編譯為可再排列的目標程序，並隨後變換為可每個過程排列的可再排列目標程序，以存儲在第二程序存儲部分32中。在這裡，可再排列目標程序是一個可以存儲在主存儲器的任何存儲區中的目標程序。此外，可每個過程排列的意思是能夠在可再排列目標程序內進行過程的排列。
應當指出，在所示實施例中，如同前面所指出的，過程一般不僅代表原始意義上的過程，而且代表函數和子程序。在過程中，包括使用者過程，使用者庫過程，標準庫過程，運行時庫過程，等等。
在這裡，使用者過程是一個使用者在源程序中定義的過程。例如，當使用者準備圖2中所示的源程序時，過程func,func1和func2都是使用者過程。
使用者庫過程源於使用者過程，並被考慮為具有高的普遍應用性，因而在經過調試之類的檢驗後存儲在第一庫存儲部分41。例如，當把圖2中所示源程序編譯為可再排列目標程序後利用調適之類的處理把源程序存儲在第一庫存儲部分41中時，所有的過程func,func1和func2都成為使用者庫過程。標準庫過程是預先在一種諸如編譯器之類的以程式語言描述源程序的處理系統中準備的，並且可以不經使用者定義而使用的過程。例如，在C語言中，用於輸出一個字符串作為標準輸出的過程prinff，用於返回字符串的長度的過程strlen等，都是標準庫過程。
運行時庫過程是預先用指令代碼描述的形式的、用於大代碼量、一般應用性高的，並且預先存儲在第一庫存儲部分41中的過程。如果編譯器35在每次產生目標程序時產生指令代碼，那麼具有高的一般應用性和大代碼量的指令串必然是低效率的。因此，把這種指令串預先建立為用指令代碼描述的過程，使得在產生目標程序時能夠產生一個調用這種過程的代碼。然後，通過連結器36連結這種過程。例如，無視執行最終目標程序的CPU之類的器件沒有十進位浮點運算的指令的實事，在源程序中說明了浮點型參數或運算，編譯器35利用包括多個諸如浮動過程加，浮動過程減之類的指令串產生目標程序。浮動過程加或浮動過程減是運行期庫過程。
第二程序存儲部分32是由包括RAM之類的半導體存儲器，FD,HD等的存儲介質構成的，並且存儲可每個過程排列的可再排列目標程序。
連結器36建立存儲在第二程序存儲部分32中的可每個過程排列的可再排列目標程序和存儲在第二庫存儲部分42中的可每個過程排列的可再排列庫(以後將對其進行討論)之間的連結，以產生一個可執行臨時目標程序存儲在第三程序存儲部分33中。與之結合，根據存儲在第二信息存儲部分39中的排列信息(以後將對其進行討論)，在可每個過程排列的可再排列目標程序與可每個過程排列的可再排列庫之間建立連結，以產生一個可執行最終目標程序，存儲在第四程序存儲部分34中。
第三程序存儲部分33是由一種諸如包括RAM等的半導體存儲器，FD,HD之類的存儲介質構成的，並且存儲臨時目標程序。第四程序存儲部分34是由一種諸如包括RAM等的半導體存儲器，FD,HD之類的存儲介質構成的,並且存儲最終目標程序。
剖析器37是由一個硬體仿真器，一個軟體仿真器等構成的，並且利用執行從第三程序存儲部分33讀出的臨時目標程序收集包括過程之間的調用關係、各過程的調用次數、循環結構信息等在內的動態信息(剖析信息)。然後，把這樣得到的動態信息存儲在第一信息存儲部分38中。
在這裡，循環結構信息是指示在該循環結構中調用的一個特定過程的信息。具體地講，是寫在源程序的循環結構中的使得在剖析器37的操作過程中能夠識別出循環結構的起點和終點的特定標記。通過剖析器37利用標記識別循環結構的起點和終點，可以識別出在循環結構中調用的過程是在該循環結構中。這樣就能夠判斷過程在循環結構內相繼執行的可能性是高的。
第一信息存儲部分38是由一種諸如包括RAM等的半導體存儲器，FD,HD之類的存儲介質構成的，並且存儲動態信息。
優化部分40根據存儲在第一信息存儲部分38中的動態信息進行所有過程的排列優化，以避免將來極有可能相繼執行的過程在高速緩衝存儲器上的衝突，和避免頻繁使用的過程的高速緩存未命中。優化部分40還產生一個用於向連結器36指明過程的排列的排列信息，和把這樣產生的排列信息存儲在第二信息存儲部分39中。
第二信息存儲部分39是由一種諸如包括RAM等的半導體存儲器，FD,HD之類的存儲介質構成的，並且存儲排列信息。
第一庫存儲部分41是由一種諸如包括ROM,RAM等的半導體存儲器，FD,HD,CD-ROM之類的存儲介質構成的，並且存儲包括標準庫過程、運行期庫過程和使用者庫過程在內的可再排列庫。在這裡，可再排列庫是可再排列目標程序。但是，為了與編譯器35產生的可再排列目標程序區分開，存儲在第一庫存儲部分41中的可再排列目標程序被稱為可再排列庫。
庫產生部分43把存儲在第一庫存儲部分41中的可再排列庫變換為可每個過程排列的可再排列庫，存儲在第二庫存儲部分42中。第二庫存儲部分42是由諸如包括RAM等的半導體存儲器，FD,HD之類的存儲介質構成的，並且存儲可每過程排列的可再排列庫。
接下來，參考圖3至10討論具有上述構造的程序變換系統的操作。
首先，在圖3中所示的步驟301，庫產生部分43把存儲在第一庫存儲部分41中的每個可再排列庫變換為可每個過程排列的可再排列庫，識別過程單元以存儲在第二庫存儲部分42中。
在一個可再排列庫中的作為一組的多個過程一般包括在一節中，例如作為排列的一個單元的文本節(.text.節)。當在連結器36中連結時，把這些過程聚合在一起成為文本節。每個單獨的過程不能每個過程獨立地排列。因此，通過把每個單獨節劃分為每過程多個節，可以在連結器36建立連結時適當地排列每個過程。
以下將討論把可再排列庫內的文本節劃分成每過程多個節的處理。
首先，由於指示自身過程可以外部使用的全局屬性和有關過程屬性的符號信息等被加在過程的前端，這些全局屬性和符號信息被識別為用來提及一前導地址的前導標記。
接著，根據每個過程的前導標記的識別，新產生每一過程的具有區分名稱的節，例如，「過程名_源程序名(procedure name_source programname)」，等等。然後，把可再排列庫中的有關各節的信息集中和新近地記錄在可再排列庫中的一個特定部分，例如，節頭部分。如果文本節在可再排列庫中是不需要的，那麼刪除相關的信息。
由於可再排列庫具有指示可再排列庫中各種信息在各部分的位置的偏移量，當如上述那樣加入新節時，必然會造成在信息與偏移量之間的相應的誤差。因此，必須更新偏移量。把上述處理過的每個可再排列庫存儲在第二程序存儲部分32中，作為可每過程排列的可再排列庫。
在步驟302，編譯器35把源程序編譯成可再排列目標程序，並隨後進行與在步驟301庫產生部分43的處理相同的處理，將可再排列庫變換為可每過程排列的可再排列庫，存儲在第二程序存儲部分32中。
在步驟303，連結器36在存儲於第二程序存儲部分32中的可每過程排列的可再排列目標程序與存儲於第二庫存儲部分42中的可每過程排列的可再排列庫之間進行連結，以產生可執行臨時目標程序，存儲在第三程序存儲部分33中。
在步驟304，剖析器37利用執行從第三程序存儲部分33讀出的臨時目標程序，收集包括各過程之間的調用關係、各過程的調用次數、循環結構信息等等的動態信息。剖析器37把這樣得到的動態信息存儲在第一信息存儲部分38中。
在步驟305，優化部分40根據存儲在第一信息存儲部分38中的動態信息進行對所有過程的排列優化，以產生排列信息，存儲在第二信息存儲部分39中。以後將討論過程排列優化的細節。
在步驟306，連結器36在可每過程排列的可再排列目標程序與可每過程排列的可再排列庫之間建立連結，以產生可執行最終目標程序，存儲在第四程序存儲部分34中。此後，結束這一處理序列。
接下來，參考圖4至10討論優化部分40的過程排列優化處理。
存在著各種有效利用高速緩衝存儲器的過程的排列優化方法。在所示的實施例中，使用了A.H.Hasemi等在「利用高速緩存行著色的有效過程映像」(A.H.Hasemi,et al,「Efficient Procedure Mapping UsingCache Line Coloring」,SIGPLAN,pp 171-182,June,1997)中公開的利用高速緩存行著色的排列方法。
首先，作為前提，從主存儲器讀出程序變換系統產生的並且存儲在主存儲器中的目標程序的每個代碼，並隨後通過直接映像法存儲在由四個高速緩存行組成的高速緩衝存儲器中。
在要編譯的源程序中，順序描述了七個過程A至G。當把源程序編譯成目標程序時，圖5中示出了各過程A至G的代碼量，要佔據的形成高速緩衝存儲器的高速緩存行的數量(高速緩存行數)。
另一方面，作為在剖析器37中動態剖析的結果，假設從過程A至過程B的調用頻率是「90」，從過程B至過程C的調用頻率是「80」，從過程C至過程D的調用頻率是「70」，從過程A至過程E的調用頻率是「40」，從過程E至過程C的調用頻率是「100」，從過程E至過程F的調用頻率是「0」，和從過程F至過程G的調用頻率是「0」。
利用高速緩存行著色的排列方法減少了在利用以後將討論的過程調用圖的一個產生(從一個過程到其它過程的直接調用關係)中的高速緩衝存儲器上的衝突。在排列方法中，為每個高速緩存行指派一種「顏色」，並利用排列所需「顏色」數量，即高速緩存行數，過程在其上排列的「顏色」，和不可用組進行過程的排列。
在所示實施例中，分別將紅色(r)指派給第一高速緩存行，綠色(g)指派給第二高速緩存行，藍色(b)指派給第三高速緩存行，和黃色(y)指派給第四高速緩存行。不可用組是與調用和被調用有直接關係的各個過程，並且被稱為已經排列的過程所佔據的「顏色」的聚合組。
首先，在圖4中所示的步驟401，優化部分40根據存儲在第一信息存儲部分38中的動態信息產生如圖6中所示的過程調用圖。在圖6中，節點A至G代表過程。節點之間的線代表過程的調用關係。為線所加的數值代表從起始節點，即在箭頭路線上的過程，到端點節點，即在箭頭尖端的過程的調用頻率。
在步驟402，關於過程調用圖，線和節點被分為一個具有高調用頻率的組和一個具有低調用頻率的組。在所示實施例中，如可以從圖6中看到的，具有高調用頻率的組是由節點A至E、從節點A至節點B的線、從節點A至節點E的線、從節點B至節點C的線、從節點C至節點D的線、和從節點E至節點C的線組成的。另一方面，具有低調用頻率的組是由節點F和G，從節點E至節點F的線，和從節點F至節點G的線組成的。
在步驟403，在劃分的每個組內重新排列線和節點。即，在具有高調用頻率的組中，從加到線上的較大數值開始以降序方式進行再排列。與之形成對照，在具有低調用頻率的組中，再排列是以從過程的較大高速緩存行數開始的降序方式進行再排列的，並且主要是為填充程序空間中的空白而排列的。
在所示的實施例中，如從圖6可以看到的，在具有高調用頻率的組中，線是以從節點E至節點C的線、從節點A至節點B的線、從節點B至節點C的線、從節點C至節點D的線和從節點A至節點E的線的順序次序排列的。另一方面，在具有低調用頻率的組中，如從圖6可以看到的，由於過程G的高速緩存行數是2，過程F的高速緩存行數是1，所以節點是以節點G然後節點F的順序次序排列的。
在步驟404中，進行是否有遺留下的高調用頻率組的線的判斷。當判斷的結果是肯定(「是」)的時候，處理前進到步驟405。此時，由於處理是第一次執行，所有的線都是被遺留的。因此，判斷的結果為「是」。
在步驟405，進行遺留線內再排列次序中的最高次序線的兩端的節點是否仍未排列的檢查。如果結果為是，處理前進到步驟406。在所示的情況中，遺留線內最高次序的線是從節點E至節點C的線，並且由於處理第一次執行，兩端的節點E和C仍未排列。因此，判斷的結果為「是」。
在步驟406，在彼此相鄰地排列了目標線的兩端的節點之後，處理前進到步驟407。在本例中，目標線兩端的節點可以排列在程序空間的任意位置。在本例中，可以從圖5中得知，過程E和C的高速緩存行數都是2。如圖7的第一行中所示，過程E的部分E1和E2排列在第一和第二高速緩存行上(顏色是紅(r)和綠(g))。過程C的部分C1和C2排列在第三和第四高速緩存行上(顏色是藍(b)和黃(y))。在這種情況下，考慮合併節點E和C，以形成一個單一的節點。這種單一節點將被稱為複合節點E-C。
在步驟407，在更新不能使用的組之後，處理返回到步驟404。
在節點E的場合，在其上節點C是被節點E直接調用關係的高速緩存行的「顏色」是藍(b)和黃(y)，不可用組成為E{b,y}。同樣，在節點C的場合，在其上節點E是被節點C直接調用關係的高速緩存行的「顏色」是紅(r)和綠(g)。因此，不可用組成為C{r,g}。
重複進行上述步驟404至407的處理，直到具有高調用頻率的組內的線中沒有其兩端節點留下未被排列的線遺留下來。如果在具有高調用頻率的組中沒有線被遺留下來，步驟404的判斷結果成為「否」。那麼，處理前進到步驟416。在本例中，由於留下了從節點A至節點B的線，並且兩端的節點A和B仍未排列，所以執行步驟406和407的處理。
如從圖5可以得知的，過程A和B都具有高速緩存行數1。因此，如圖7第一行中所示，過程A被排列在第三高速緩存行(顏色是藍(b))，過程B被排列在第四高速緩存行(顏色是黃(y))。因而節點A和B成為複合節點A-B。接下來，在節點A的場合，在其上節點B是被節點A直接調用的關係的高速緩存行的「顏色」是黃色(y)，不可用組成為A{y}。同樣，在節點B的場合，在其上節點A是被節點B直接調用的關係的高速緩存行的「顏色」是藍色(b)，不可用組成為B{b}。
應當注意，在圖6中所示的過程調用圖中，儘管事實是留下了從節點A至節點E的線，由於在其上節點E被排列在節點A的不可用組中的顏色紅(r)與綠(g)的高速緩存行沒有被包括。這是因為由於低調用頻率次序，還沒有處理從節點A至節點E的線。在當前狀態下，可能引起有關從節點A至節點E線衝突，處理按照原始線次序進行。因此，當前狀態是可接受的。
另一方面，當留下了具有高調用頻率組中的線但遺留線的任意一端的節點已經排列的時候，步驟405的判斷結果成為「否」。處理前進到步驟408。
在步驟408，進行處理目標的線是否是連接兩個不同複合節點中的節點的線的檢查。如果在步驟408檢查的結果為是，那麼處理前進到步驟409。在當前條件下，由於具有遺留下的線中最高次序的從節點B指向節點C的線是連接複合節點E-C和複合節點A-B的線，步驟408的判斷結果為是。因此，處理前進到步驟409。
在步驟409，關於作為處理目標的線，兩個複合節點被合併為一個單一的複合節點。這是通過把兩個複合節點中具有較少合併節點數的複合節點(以後稱為短複合節點)耦合到具有較多合併節點數的複合節點(以後稱為長複合節點)進行的。在把短複合節點耦合到長複合節點時，即使在程序空間中，也是短複合節點被耦合到長複合節點。
首先，確定要把短複合節點排列在長複合節點的哪一側。具體地講，作出在組成長複合節點的節點中，組成處理目標線的節點的中心位置朝向長複合節點的左還是右邊界的判斷，判斷是利用達到左和右邊界所需的高速緩存行數進行的。因此，確定短複合節點排列在朝向中心位置的一側。
接下來，確定和排列排列短複合節點的方向。具體地講，是這樣確定短複合節點的方向的，使得在組成處理目標的線的多個節點中，不是組成長複合節點的節點能夠儘可能靠近長複合節點中已經排列的節點排列。在這種場合，如果短複合節點排列引起衝突，把不是組成長複合節點的節點的位置從組成長複合節點的節點偏移，直到解決了衝突。但是，當在不是組成長複合節點的節點的任何排列位置都不能避免衝突時，將不是組成長複合節點的節點的排列位置移回到初始排列位置。然後處理前進到步驟410。
在所示實施例中，複合節點E-C和A-B都有兩個合併的節點。因此，兩個複合節點都可以作為短複合節點。但是，在所示情況中，把複合節點A-B作為短複合節點。
在組成長複合節點的節點E和C中，形成作為處理目標的從節點B指向節點C的線的節點C的中心位置處於圖7的第一行中所示的部分C1和C2之間。因此，到達長複合節點E-C的左側邊界所需的高速緩存行的數量是三，而到達長複合節點E-C的右側邊界所需的高速緩存行的數量是一。因此，把短複合節點A-B排列在長複合節點E-C的右側。
然後，確定短複合節點A-B的方向，使得在形成作為處理目標的從節點B指向節點C的線的節點B和C中，不是組成長複合節點E-C的節點B位於儘可能靠近已經被排列的節點C的位置。因此，複合節點成為B-A。由於在上述的排列中沒有造成衝突，保持這樣的排列(見圖7的第二行)。由此產生了新的複合節點E-C-B-A。
在步驟410，進行通過上述的排列處理是否在程序空間中形成了空白區的檢查。如果在步驟410的檢查結果為「否」，那麼處理前進到步驟407。在所示情況中，由於沒有形成空白區，處理前進到步驟407。接著，在更新了不可用組之後，處理返回到步驟404。
在節點A的場合，由於其上節點B是以直接調用的關係排列的高速緩存行的「顏色」是紅(r)，不可用組成為A{r}。同樣，在節點B的場合，由於節點A以直接調用關係排列於其上的高速緩存行的「顏色」是綠(g)，並且由於節點C以直接調用關係排列於其上的高速緩存行的「顏色」是藍(b)和黃(y)，因此，不可用組變為B{g,b,y}(見圖7的第二行)。
在另一方面，當在步驟410檢查的結果為「是」時，即當通過上述的排列處理在程序空間中形成了空白區時，處理前進到步驟411。
在步驟411，把具有低調用頻率組中具有高次序的節點排列在空白區中。此後，處理前進到步驟407。
重複上述步驟404,405,408至411和407的處理，直到發現在具有高調用頻率的組的線中沒有連接兩個相互不同的複合節點中的節點的線，並且任意一側的節點已經被排列。那麼，如果沒有遺留具有高調用頻率的組的線，步驟404的檢查結果為「否」。處理前進到步驟416。
如果具有高調用頻率的組的線中沒有連接的兩個相互不同的複合節點中的節點的線，並且已經排列了任意一側的節點，步驟408的檢查結果為「否」。那麼，處理前進到步驟412。
通過上述的處理，處理了從節點E至節點C的線、從節點A至節點B的線、和從節點B至節點C的線。因此，在具有高調用頻率的組中，留下了從節點C至節點D的線和從節點A至節點E的線。但是，這些線不是其中一個節點已經被排列的線，並且不連接兩個不同複合節點。因此，在步驟408的檢查結果為「否」。因此，處理前進到步驟412。
在步驟412，檢查是否組成作為處理目標的線的兩個節點中的一個節點組成複合節點，並且另一個節點還沒有排列。如果在步驟412的檢查結果為「是」，那麼處理前進到步驟413。在本例中，在剩餘的線中具有最高次序的從節點C至節點D的線具有組成複合節點E-C-B-A的節點C，和還沒有排列的節點D。因此，在步驟412的檢查結果為「是」。因而處理前進到步驟413。
在步驟413，使處理目標線的未排列節點與複合節點耦合。一旦未排列節點耦合於複合節點，未排列節點即使在程序的空間上也與複合節點耦合。
首先，確定把未排列節點排列在複合節點的哪一側。具體地講，是判斷在組成複合節點的節點中，是在複合節點的左邊界還是右邊界包括了組成處理目標線的節點的中心位置，判斷是通過到達左和右邊界所需的高速緩存行數作出的。於是，確定把未排列節點排列在朝向中心位置的一側。
在這種情況下，如果未排列節點的排列造成衝突，那麼使不是組成複合節點的節點從組成複合節點的節點偏移，直到解決衝突。但是，當在不是組成複合節點的節點的任何排列位置都不能避免衝突時，把不是組成複合節點的節點的排列位置返回到初始排列位置。然後，處理前進到步驟410。
在組成複合節點E-C-B-A的節點E,C,B,A中，從節點C至節點D的處理目標線的中心位置，如圖7的第一行所示，在部分C1和C2之間。因此，到達複合節點E-C-B-A的左邊界所需的高速緩存行數是三，而到達複合節點E-C-B-A的右邊界所需的高速緩存行數也是三。所以，可以把未排列節點排列在複合節點E-C-B-A的左右任意一側。在所示的情況中，確定把節點D排列在複合節點E-C-B-A的左側。
在這種情況下，當節點D的部分D1和D2緊接著節點E的部分E1的左側時，在節點D的部分D1和D2與節點C的部分C1和C2之間可能會造成衝突。因此，為了避免衝突，把節點D的部分D1和D2排列在離開節點E的部分E1的兩個高速緩存行距離的位置上(見圖7的第三行)。
接下來，在這種場合，相當於兩個高速緩存行的空白區形成在節點D的部分D1和D2的右側。那麼，在步驟410的驗查結果為「是」。因此，處理前進到步驟411。
在步驟411，在節點D的部分D1和D2右側的兩個高速緩存行的空白區中，排列具有低調用頻率組中的具有最高次序的節點。在所示情況中，在上述空白區中排列節點G(見圖7的第四行)。接著，在更新了不可用組後，處理前進到步驟407。然後，處理返回到步驟404。在節點D的場合，其上的節點C被節點D直接調用的高速緩存行的「顏色」是藍(b)和黃(y)，不可用組變為D{b,y}(見圖7的第三行)。
重複進行上述步驟404,405,408,412,413,410,411和407的處理，直到發現在具有高調用頻率組的遺留線中沒有這樣的線，其不連接兩個相互不同的複合節點中的節點，而是連接相對兩端的節點之一，該線的一個節點組成複合節點而另一側的節點尚未排列，並且任意一端的節點已經排列。那麼，如果沒有留下的具有高調用頻率組的線，在步驟404的檢查結果為「否」。處理前進到步驟416。
如果發現在具有高調用頻率組的遺留線中沒有這樣的線，其不連接兩個相互不同的複合節點中的節點，而連接相對兩端的節點之一，該線的一個節點組成複合節點而另一側的節點尚未排列，並且任意一端的節點已經排列。在驟412檢查的結果為「否」。那麼，處理前進到步驟414。
通過上述處理，處理了從節點E至節點C的線，從節點A至節點B的線，從節點B至節點C的線，和從節點C至節點D的線。因此，在具有高調用頻率的組中，僅留下了從節點A至節點E的線。但是，這個線不是具有高調用頻率組的遺留線中的不連接兩個相互不同的複合節點中的節點，而是連接線相對兩端的節點之一的線，該線的一個節點組成複合節點而另一側的節點尚未排列，並且任意一端的節點已經排列。因此，在步驟412的檢查結果為「否」。那麼，處理前進到步驟414。
在步驟414，檢查是否組成處理目標線的兩個節點中的一個節點組成了複合節點，而另一個節點尚未排列。如果在步驟414的檢查結果為「是」，處理前進到步驟415。在本例中，在遺留線中有最高的次序的從節點A至節點E的線，具有組成複合節點E-C-B-A的兩個節點，並且節點E尚未排列。因此，在步驟414的檢查結果為「是」。那麼，處理前進到步驟415。
在步驟415，消除組成處理目標線的節點之間的衝突。即，如果在組成處理目標線的節點之間產生衝突，將最靠近複合節點邊界的一個節點向邊界以外偏移，直到解決了衝突。但是，當在該節點的任何偏移位置都不能避免衝突時，把該節點返回到最初排列的位置。然後，處理前進到步驟410。
在所示實施例中，處理目標線是從節點A至節點E的線。可以從圖7的第四行看到，在節點A與E之間造成衝突。在組成從節點A至節點E的線的節點A和E中，節點A更靠近複合節點E-C-B-A的邊界。因此，把節點A偏移到邊界之外。在所示情況中，由於可以通過把節點A偏移一高速緩存行避免衝突，因而將節點A排列在偏移一高速緩存行的位置上(見圖7的第五行)。
接下來，在所示情況下，在節點A的右側形成了一高速緩存行的空白區。因此，在步驟410的判斷結果為「是」。因而處理前進到步驟411。
在步驟411，節點A右側的一高速緩存行的空白區中，排列遺留在具有低調用頻率組中的節點。在本例中，排列節點F之後(見圖7的第六行)，處理前進到步驟407。在更新不可用組之後，處理返回到步驟404。在節點A的場合，在其上節點E和B是以被節點A直接調用的關係排列的高速緩存行的「顏色」是紅(r)和綠(g)，不可用組變為A{r,g}(見圖7的第五行)。同樣，在節點B的場合，在其上節點C是以被節點B和節點A直接調用的關係排列的高速緩存行的「顏色」是藍(b)和黃(y)。因此，不可用組成為B{b,y}(見圖7的第五行)。
重複進行上述步驟404,405,408,412,414,415,410,411和407的處理，直到沒有留下連接同一複合節點中的節點的線。如果沒有遺留的具有高調用頻率組中的線，步驟404判斷的結果為「否」。那麼處理前進到步驟416。
在步驟416，關於具有低調用頻率的組中的剩餘節點，排列是通過簡單的深度優先選取進行的。當通過上述處理將多個複合節點相互排列開時，根據調用的頻率給每個複合節點賦予優先次序，以確定最後的排列。然後，處理序列結束。
在圖8中示出了通過上述過程的排列優化處理得到的排列信息的一個實例。
作為前提，假設過程A和B包括在一個文件名為「test1.o」的源程序文件中，函數E,F和G包括在一個文件名為「test2.o」的源程序文件中，過程C和D是包括在文件名為「1ibc.a」的庫文件中的標準庫過程。此外，還假設一個高速緩存行的大小為32位元組(0×20)。
在圖8中，「GROUP1」是在把輸出節作為一組處理的情況中給予的段名。「! LOAD」代表一個段的類型。這個欄位是固定的。在所示情況中，「LOAD」代表要在存儲器中裝載的段。「 RX」代表一個段的屬性，它顯示了段的讀出/寫入/執行屬性。在一個指令部分(文本代碼)的情況下，它固定為「 RX」。「A0×1000」代表對準條件，對準條件表示當段在存儲空間排列時的對準條件。在所示情況中，示出了對準條件為「0×1000」的情況。
另一方面，「_D_LIB」,「_G_test2」等是代表通過耦合相同類型和屬性的輸入節形成的組的輸出段名。「$PROGBITS」代表輸入節的類型。在文本代碼的場合，輸入節的類型固定為「$PROGBITS」。「？AX」代表表示存儲器的佔據/可寫/可執行等屬性的節屬性。在文本代碼的場合，它固定為「 AX」。
「A0×20」代表在輸出節中排列輸入節時的對準條件。由於出於每高速緩存行排列的考慮，對準條件是作為一個高速緩存行的大小的0×20。「_D_test1」,「_G_test2」等代表要在輸出節中排列的輸入節的名。「1ibc.a」,「test2.0」等代表包括在輸入節中的文件名。當輸出節是由多個文件的相同輸入節集合形成的時候，可以描述多個文件名。
如上所述，通過提供每個過程的輸入節名，利用排列條件可以指定過程的排列順序。如上所述，利用所示實施例的結構，在剖析器37剖析時，向把可再排列庫變換為可每過程排列的可再排列庫的庫產生部分43提供了有關所有過程的收集動態信息，根據動態信息產生確定所有過程的優化排列的排列信息，和根據排列信息排列所有過程。因此，可以減少高速緩衝存儲器上所有組成目標程序的過程之間的衝突。與之結合，可以減少頻繁使用的過程的高速緩存丟失。藉此，在計算機或CPU執行目標程序時可以提高執行速度。
在這方面，當要編譯的源程序中包括七個過程並且是以順序次序描述的時候，把源程序編譯成目標程序時A至G各過程的高速緩存行數如圖5中所示，如果根本不提供優化部分40進行的過程的排列優化處理，源程序中的過程A至G以描述的次序編譯成目標程序。因此，如圖9中所示，造成過程C與E之間產生衝突。
另一方面，在本發明中，不區分過程的類型，所有過程同樣地處理並且排列是可每過程排列的，完全消除衝突的可能性高。在如圖6中所示的過程調用圖中，如圖10中所示，過程C和D是標準庫過程。如在現有技術中，如果把過程C和D置於過程的排列優化處理目標之外，即使在使用上述發表的文獻中公開的高速緩存行著色法，由於下面的原因，也不可能完全避免衝突。在現有技術中，當在源程序中描述了多個標準庫過程的一個調用指令時，一旦要在連結器中建立連結，從庫存儲部分讀出多個對應的標準庫過程，併集中地排列在現有技術主存儲器的特定存儲區中。這不可能指明每個過程的排列。
圖11示出了在把標準庫過程C和D排除在過程排列優化處理之外的情況中，優化部分進行的過程的排列優化處理的方法。在這種情況中，由於標準庫過程C和D被排除在排列優化處理之外，從過程E至過程C的線和從過程B至過程C的線自然也被排除在處理之外。因此，如圖11的第五行中所示，可以避免過程E和過程C的衝突。(第二實施例)以下討論根據本發明的程序變換系統的第二實施例。
圖12是顯示根據本發明的程序變換系統的第二實施例的結構的方框圖。在圖12中，與圖1中所示的相同元件用相同的參考號標識，並且忽略了對這些相同元件的詳細描述，以便避免冗長的描述，保證描述足夠簡明，以便於對本發明的清晰理解。
在圖12所示的程序變換系統的所示實施例中，除了庫產生部分43之外也為存儲在第一庫存儲部分41中的可再排列庫提供了連結器36。以下是提供這種構造的原因。
即，當可再排列庫的數量很大時，要用很長的時間把存儲在第一庫存儲部分41中的可再排列庫變換為可每過程排列的可再排列庫。
因此，對於可再排列庫的一部分，不用庫產生部分43把可再排列庫變換為可每過程排列的可再排列庫，而通過連結器36建立對可每過程排列的可再排列庫的直接連結。
在這種情況下，例如，可以用連結器36根據存儲在第一信息存儲部分38中的動態信息或每個過程的代碼量判斷直接提供給連結器36的可再排列庫。
如上所述，利用上述構造，可以在比第一實施例更短的時間內產生最終目標程序。(第三實施例)以下將討論根據本發明的程序變換系統的第三實施例。
圖13是顯示根據本發明的程序變換系統的第三實施例的結構的方框圖。在圖13中，與圖12中所示相同的元件用相同的參考號標識，並忽略了對這些相同元件的詳細描述，以便避免冗長的描述，保證描述足夠簡明，以便於對本發明的清晰理解。
在程序變換系統的第三實施例中，新提供了一個編譯器44和一個剖析器45，替代圖12中所示的編譯器35和剖析器37。
與圖12中所示的剖析器37不同，剖析器45僅具有簡單地讀出存儲在第三程序存儲部分33中的可執行臨時目標程序和執行讀出的臨時目標程序的功能。另一方面，在把源程序編譯為可執行臨時目標程序時，編譯器44把一個計算剖析器45執行臨時目標程序時實際執行的過程的次數的計數代碼插入到臨時目標程序中。藉此，剖析器45可以通過執行臨時目標程序收集包括過程之間調用關係，各過程的調用次數等的動態信息，並把得到的動態信息存儲在第一信息存儲部分38中。
以下將參考圖14討論上述構造的程序變換系統的第三實施例的操作。
首先，在圖14所示的步驟1401中，編譯器44把從第一程序存儲部分31讀出的源程序(見圖2)編譯成帶有插入計數代碼的可執行臨時目標程序，存儲在第二程序存儲部分32中。
在步驟1402，連結器36建立存儲在第二程序存儲部分32中的插入了計數代碼的臨時目標程序與存儲在第一庫存儲部分41中的可再排列庫之間的連結，以產生可執行臨時目標程序，存儲在第三程序存儲部分33中。
在步驟1403，剖析器45執行從第三程序存儲部分33中讀出的臨時目標程序。在這種情況中，由於計數代碼插入在臨時目標程序中，因而收集了由過程之間的調用關係、每個過程的調用次數等構成的動態信息。把得到的動態信息存儲在第一信息存儲部分38中。
在步驟1404，優化部分40根據存儲在第一信息存儲部分38中的動態信息，通過進行對所有過程的排列優化產生排列信息，存儲在第二信息存儲部分39中。步驟1404的處理實際上與第一實施例中步驟305的處理相同。因此，省略了對這一步驟的詳細描述，以便避免冗長的描述，保證描述足夠簡明，以便於對本發明的清晰理解。
在步驟1405，庫產生部分43通過識別每個過程把存儲在第一庫存儲部分41中的可再排列庫變換成可每過程排列的可再排列庫，存儲在第二庫存儲部分42中。步驟1405的處理實際上與第一實施例中步驟301的處理相同。因此，省略了對這一步驟的詳細描述，以便避免冗長的描述，保證描述足夠簡明，以便於對本發明的清晰理解。
在步驟1406，編譯器35把源程序編譯為可再排列目標程序，並隨後用與在步驟1405中庫產生部分43的處理方法相同的處理，變換成可每過程排列的可再排列目標程序，存儲在第二程序存儲部分32中。
在步驟1407，連結器36根據存儲在第二信息存儲部分39中的排列信息建立可每過程排列的可再排列目標程序與可每過程排列的可再排列庫之間的連結，以產生可執行最終目標程序，存儲在第四程序存儲部分34中。此後，處理序列結束。
利用上述實施例的構造，即使剖析器45沒有收集動態信息的功能，也能獲得與第一實施例實際相同的效果。
儘管本發明是通過它的示範實施例圖示和說明的，但是熟悉本領域的技術人員應當懂得，可以對其進行上述和各種其它改變、刪除和添加，而不脫離本發明的精神和範圍。因此，不應當認為本發明僅限於上述特定實施例，而是包括有關附屬權利要求中提出的特徵的，能夠在包含範圍內實現的所有可能的實施例及其等同物。
例如，儘管本發明在上述實施例中，是以用於從一個源程序產生一個最終目標程序的範例圖示和說明的，但不應當把本發明限於說明的實施例。即，理所當然，本發明可以用在把多個源程序編譯成各自的可再排列目標程序，然後用連結器36連結產生的可再排列目標程序以產生一個最終目標程序這樣的場合。
另一方面，在上述的各實施例中，各程序存儲部分31至34，各信息存儲部分38和39和庫存儲部分41和42是用相互不同的存儲介質構成的。但是，本發明並不限於所示實施例。也就是說，各存儲部分可以用共同的存儲介質的不同存儲區形成。
在這種情況下，各程序存儲部分31至34和庫存儲部分41和42是存儲需要相對大的存儲容量的程序或可再排列庫，因此可以用FD,HD或CD-ROM構成。另一方面，由於各信息存儲部分38和39是存儲需要相對小的存儲容量的數據，這些信息存儲部分38和39可以用諸如RAM,ROM之類的半導體存儲器形成。
另一方面，在上述實施例中的各裝置是以硬體構造說明的。本發明並不限於所述實施例中顯示的構造。也就是說可以用具有CPU(中央處理器)、ROM、RAM之類的內存儲器、FDD(軟盤驅動器)、HDD(硬碟驅動器)、CD-ROM驅動器之類的外存儲器以及輸出裝置和輸入裝置的計算機構成程序變換系統，上述編譯器35和44，連結器36和剖析器37和45可以由CPU構成，並且可以把實現上述功能的程序變換程序存儲在諸如包括ROM等的半導體存儲器或FD、HD、CD-ROM之類的存儲介質中。
在這種情況下，上述內存儲器或外存儲器可以作為各程序存儲部分31至34，各信息存儲部分38和39，以及庫存儲部分41和42使用。把程序變換程序從存儲介質裝載到CPU，以控制CPU的操作。CPU響應程序變換程序的啟動，發揮編譯器35和44、連結器36和剖析器37和45的功能。在程序變換程序的控制下，執行上述處理。
如上所述，利用上述本發明的構造，可以避免高速緩衝存儲器上各種過程之間的衝突。也可以防止頻繁使用的過程的高速緩存丟失。藉此，當計算機或CPU執行時，可以加快執行速度。
儘管本發明是通過它的示範實施例圖示和說明的，但是熟悉本領域的技術人員應當懂得，可以對其進行上述和各種其它改變，刪除和添加，而不脫離本發明的精神和範圍。因此，不應當認為本發明僅限於上述特定實施例，而是包括有關附屬權利要求中提出的特徵的，能夠在包含範圍內實現的所有可能的實施例及其等同物。
權利要求
1．程序變換方法，用於把由程式語言描述的源程序變換為數據處理系統可執行語言所描述的目標程序，該程序變換方法包括第一處理，將所述源程序中使用的至少一部分過程、函數或子程序變換為一種使得所述目標程序可以被存儲在所述數據處理系統的主存儲器的任意存儲區內的形式；第二處理，根據在所述源程序變換為所述目標程序的處理過程中獲得的有關於所述過程、函數或子程序的信息，在所述主存儲器的存儲區中對應於一高速緩衝存儲器的高速緩存行的所述存儲區內排列所述第一處理中變換的或未變換的過程、函數或子程序，而不造成高速緩存衝突；和第三處理，根據排列的結果產生所述目標程序。
2．如權利要求1所述的程序變換方法，其中所述過程、函數或子程序至少是使用者在所述源程序中定義的、使用者定義並檢驗的、以所述程式語言在一處理系統中預先準備的、和以指令代碼形式預先準備的過程、函數或子程序中的一種。
3．如權利要求1所述的程序變換方法，其中所述信息是通過執行從所述源程序變換的一個臨時目標程序得到的，並且是由指示所述過程、函數或子程序實際被調用的次數的信息和指示過程、函數或子程序之間的調用關係的信息組成的。
4．如權利要求1所述的程序變換方法，其中所述信息是通過執行從所述源程序變換的一個臨時目標程序得到的，並且是由指示所述過程、函數或子程序實際被調用的次數的信息和指示過程、函數或子程序之間的調用關係的信息組成的，在所述第二處理中，所述過程、函數或子程序根據調用頻率被劃分為多個組，和將所述過程、函數或子程序排列在所述主存儲器的存儲區中對應於一個高速緩衝存儲器的高速緩存行的所述存儲區內。
5．程序變換方法，用於把由程式語言描述的源程序變換為數據處理系統可執行語言描述的目標程序，該程序變換方法包括第一處理，當在所述數據處理系統中使用所述目標程序時，將所述源程序中使用的過程、函數或子程序的至少一部分變換為一種在所述數據處理系統的一個主存儲器的任意存儲區中存儲的形式；第二處理，將所述源程序變換為所述目標程序，和與之結合，關於所述目標程序，把所述源程序中使用者定義的過程、函數或子程序變換為可在所述主存儲器的任意區中存儲的形式；第三處理，連結所述第一處理中變換的過程、函數或子程序和所述第二處理中獲得的目標程序；第四處理，利用執行通過所述第三處理得到的目標程序，收集由指示過程、函數或子程序實際被調用的次數的信息和指示所述過程、函數或子程序之間的調用關係的信息構成的動態信息；第五處理，根據所述動態信息，在所述主存儲器的存儲區中對應於高速緩衝存儲器的高速緩存行的所述存儲區中排列所述過程、函數或子程序，同時避免高速緩存衝突；和第六處理，根據所述排列信息，通過連結所述第一處理中變換的所述過程、函數或子程序和在所述第二處理中獲得的目標程序產生最終目標程序。
6．如權利要求5所述的程序變換方法，其中所述過程、函數或子程序至少是使用者在所述源程序中定義的、使用者定義並檢驗的、以所述程式語言在一處理系統中預先準備的，和以指令代碼形式預先準備的過程、函數或子程序中的一種。
7．如權利要求5所述的程序變換方法，其中在所述第二處理中，所述過程、函數或子程序根據調用頻率被劃分為多個組，和將所述過程、函數或子程序排列在所述主存儲器的存儲區中對應於一個高速緩衝存儲器的高速緩存行的所述存儲區內。
8．程序變換方法，用於把由程式語言描述的源程序變換為數據處理系統可執行語言描述的目標程序，該程序變換方法包括第一處理，將所述源程序變換為一個臨時目標程序，和與之結合，在執行所述臨時目標程序時，插入對所述過程、函數或子程序實際被調用的次數計數的代碼；第二處理，把使用者在所述源程序中定義的、使用者定義並檢驗的、在處理系統中以所述程式語言預先準備的、和以指令代碼形式預先準備的過程、函數或子程序中的一個與通過所述第一處理獲得的所述臨時目標程序連結；第三處理，利用執行通過所述第二處理得到的目標程序，收集由指示過程、函數或子程序實際被調用的次數的信息和所述過程、函數或子程序之間的調用關係的信息組成的動態信息；第四處理，根據所述動態信息，在所述主存儲器的存儲區中對應於高速緩衝存儲器的高速緩存行的所述存儲區中排列所述過程、函數或子程序，同時避免高速緩存衝突；和第五處理，在所述源程序中將被使用的過程、函數或子程序中由使用者在所述源程序中定義的一個、由使用者定義並檢驗的一個、在處理系統中以所述程式語言預先準備的一個、和以指令代碼形式預先準備的一個中至少一部分變換為可在所述主存儲器的任意存儲區中存儲的一種形式，其中所述目標程序按照在所述數據處理系統中實際使用的形式存儲；第六處理，在把所述源程序變換為所述目標程序之後，關於所述目標程序，把使用者在所述源程序中定義的過程、函數或子程序變換為一種可在所述主存儲器的任意區中存儲的形式；第七處理，根據所述排列信息，通過連結在所述第五處理中變換的所述過程、函數或子程序和在所述第六處理中獲得的目標程序產生最終目標程序。
9．如權利要求8所述的程序變換方法，其中在所述第四處理中，所述過程、函數或子程序根據調用頻率被劃分為多個組，和將所述過程、函數或子程序排列在所述主存儲器的存儲區中對應於一個高速緩衝存儲器的高速緩存行的所述存儲區內。
10．程序變換系統，用於把由程式語言描述的源程序變換為數據處理系統可執行語言描述的目標程序，所述程序變換系統包括；過程變換裝置(43)，用於將所述源程序中使用的過程、函數或子程序的至少一部分變換為一種使得所述目標程序可以被存儲在所述數據處理系統的主存儲器的任意存儲區中的形式；優化裝置(40)，用於根據在所述源程序至所述目標程序的變換處理過程中獲得的有關所述過程、函數或子程序的信息，把在所述過程變換裝置中變換的或未變換的過程、函數或子程序排列在所述主存儲器存儲區中對應於一個高速緩衝存儲器的高速緩存行的所述存儲區內，而不會造成高速緩存衝突；和產生裝置(36)，用於根據排列的結果產生所述目標程序。
11．如權利要求10所述的程序變換系統，其中所述過程、函數或子程序是使用者在所述源程序中定義的、使用者定義並檢驗的、預先在處理系統中以所述程式語言準備的，和預先以指令代碼形式準備的過程、函數或子程序的至少一種。
12．如權利要求10所述的程序變換系統，其中所述信息是通過執行從所述源程序變換來的臨時目標程序而獲得的，並且是由指示過所述過程、函數或子程序實際被調用的次數的信息和指示過程、函數或子程序之間的調用關係的信息構成的。
13．如權利要求10所述的程序變換系統，其中所述信息是通過執行從所述源程序變換來的臨時目標程序而獲得的，並且是由指示過所述程、函數或子程序實際被調用的次數的信息和指示過程、函數或子程序之間的調用關係的信息構成的，在所述優化裝置(40)中，根據調用頻率把所述過程、函數或子程序劃分為多個組，和將所述過程、函數或子程序排列在所述主存儲器存儲區中的對應於一個高速緩衝存儲器的高速緩存行的所述存儲區內。
14．程序變換系統，用於把由程式語言描述的源程序變換為數據處理系統可執行語言描述的目標程序，所述程序變換系統包括過程變換裝置(43)，用於將所述源程序中使用的過程、函數或子程序的至少一部分變換為一種當所述目標程序在所述數據處理系統中使用時用於在所述數據處理系統的主存儲器的任意存儲區中存儲的形式；程序變換裝置(35)，用於把所述源程序變換為所述目標程序，和與之結合，關於所述目標程序，把使用者在所述源程序中定義的過程、函數或子程序變換為一種可以存儲在所述主存儲器的任意存儲區中的形式；連結裝置(36)，用於連結在所述過程變換裝置中變換的過程、函數或子程序和在所述程序變換裝置中獲得的目標程序；動態信息收集裝置(37)，用於利用執行通過所述連結裝置獲得的目標程序，收集由指示過程、函數或子程序實際被調用的次數的信息和指示過程、函數或子程序之間的調用關係的信息構成的動態信息；和優化裝置(40)，用於根據所述動態信息，在所述主存儲器存儲區中對應於高速緩衝存儲器的高速緩存行的所述存儲區中排列所述過程、函數或子程序，同時避免高速緩存衝突；所述連結裝置(36)根據所述排列信息，通過連結在所述過程變換裝置變換的所述過程、函數或子程序和在所述程序變換裝置獲得的目標程序產生最終目標程序。
15．如權利要求14所述的程序變換系統，其中所述優化裝置(40)，根據調用頻率把所述過程、函數或子程序劃分為多個組，和將所述過程、函數或子程序排列在所述主存儲器存儲區中的對應於一個高速緩衝存儲器的高速緩存行的所述存儲區內。
16．程序變換系統，用於把由程式語言描述的源程序變換為數據處理系統可執行語言描述的目標程序，所述程序變換系統包括程序變換裝置(35)，用於將所述源程序變換為一臨時目標程序，和與之結合，在執行所述臨時目標程序時，插入計算所述過程、函數或子程序被實際調用的次數的代碼；連結裝置(36)，用於將所述源程序中使用者定義的、使用者定義並檢驗的、在處理系統中以所述程式語言預先準備的、和以指令代碼形式預先準備的過程、函數或子程序中的一個與通過所述程序變換裝置獲得的所述臨時目標程序連結；動態信息收集裝置(37)，用於利用執行通過所述連結裝置獲得的目標程序，收集由指示過程、函數或子程序實際被調用的次數的信息和指示所述過程、函數或子程序之間的調用關係的信息構成的動態信息；優化裝置(40)，用於根據所述動態信息，在所述主存儲器存儲區中對應於高速緩衝存儲器的高速緩存行的所述存儲區內排列所述過程、函數或子程序，同時避免高速緩存衝突；和過程變換裝置(43)，用於把要在所述源程序中使用的過程、函數或子程序中的一個由使用者在所述源程序中定義的、使用者定義並檢驗的、在處理系統中以所述程式語言預先準備的、以指令代碼形式預先準備的過程、函數或子程序中至少一部分變換為可以存儲在其中存儲著要在所述數據處理系統中實際使用的所述目標程序的所述主存儲器的任意存儲區中的一種形式；所述程序變換裝置(35)將所述源程序變換為所述目標程序，關於所述目標程序，把使用者在所述源程序中定義的過程、函數或子程序變換為一種可以存儲在所述主存儲器的任意區中的形式，並且所述連結裝置(36)根據所述排列信息，通過連結在所述過程變換裝置變換的所述過程、函數或子程序和在所述程序變換裝置中獲得的目標程序產生一個最終目標程序。
17．如權利要求16所述的程序變換系統，其中在所述優化裝置(40)中，根據調用頻率把所述過程、函數或子程序劃分為多個組，和將所述過程、函數或子程序排列在所述主存儲器存儲區中的對應於一個高速緩衝存儲器的高速緩存行的所述存儲區內。
全文摘要
一種用於把源程序變換為數據處理系統可執行語言描述的目標程序的程序變換方法,包括將所述源程序中使用的至少一部分過程、函數或子程序變換為一種使得目標程序可以被存儲在數據處理系統的主存儲器的任意存儲區中的形式;根據上述處理過程獲得的有關於過程、函數或子程序的信息,在主存儲器對應於一高速緩衝存儲器的高速緩存行的存儲區中設置在第一處理中變換的或未變換的過程、函數或子程序,而不造成高速緩存衝突;和根據排列的結果產生目標程序。
文檔編號G06F12/08GK1228558SQ9910082
公開日1999年9月15日 申請日期1999年2月23日 優先權日1998年2月16日
發明者磯崎博子 申請人:日本電氣株式會社