資源分配裝置的製作方法

2023-05-27 12:40:36 4

專利名稱：資源分配裝置的製作方法
技術領域：
本發明是關於在用高級語言編寫的程序翻譯成機器語言程序的編譯程序中將程序中的變量分配到寄存器、存貯器等資源的資源分配裝置。
近年來，採用面向機內用途的微處理器以適應各種各樣要求的信息設備正在蓬勃發展。在這樣的信息設備開發中，在軟體方面，也要求處理的高速化和徹底降低硬體成本(縮小存貯器尺寸)。因此，在上述信息設備的開發中，應徹底去掉冗長的傳輸命令、最大限度地發揮尋址方式等微處理器所具有的功能，採用彙編語言進行軟體的開發。但是，由於彙編語言的語法是微處理器的命令體系，所以，開發效率低，在源文件的移植性方面有問題。因而採用高級程式語言來完成面向機內用途的微處理器的軟體來提高開發效率，近年引起了很大的關注。
如採用高級程式語言，程式設計師可以用將變量作為操作算符的運算來表現程序中的數值的保持、運算、傳送等處理。此變量可以利用程序任意地定義，而且，可以只採用必要的個數，所以，程式設計師可以自由地描述程序。另外，所描述的程序(稱為源程序)經過編譯就成為計算機可以理解的機器語言程序。該機器語言程序中的運算由機器語言命令表示，而由於該機器語言命令將寄存器或存貯器作為操作算符，因而必須給上述變量分配寄存器或存貯器。這種分配處理被稱為資源分配處理。此資源分配處理在最大限度發揮微處理器的能力的軟體開發中受到特別的重視。
在對現有的資源分配裝置加以描述以前，對下面的說明中使用的術語進行說明。
變量的定義、引用、使用設定變量值稱為「定義」；使用設定的值稱為「引用」。另外，在程序中定義或引用變量，稱為「使用」。
中間命令為易於處理，編譯程序將源程序碼變換成為中間的代碼稱為中間碼，中間代碼的一步叫做中間命令。在中間命令中存在4組或3組等，將它們變換後就生成最終的目標碼。另外，將源程序變換成中間命令串的程序叫做中間程序。
生存區間所謂生存區間，廣義地說就是各變量所保持的值為有效的區間，狹義地說就是指從定義變量值的中間命令到最後引用該被定義的值的中間命令為止的程序中的區間，生存區間即以其區間由所包含的中間命令的集合來表示。這裡，定義變量值的中間命令相當於生存區間的開始點，在引用在生存區間中定義的值的中間命令中，最後引用的中間命令相當於生存區間的結束點。另外，由於以中間命令的集合積來判斷生存區間的重複、非重複，所以，在生存區間的終始一致的中間命令中，設定生存區間不重疊。
中間命令程序(將圖3A所示的源程序變換後的程序)和與該生存區間的對應的例子示於

圖1中。在圖1中，生存區間以豎線條s1、s2、s3表示。生存區間的起始點和結束點以p1、p2、p3、p4……代表。在圖1中，變量c和d存在2個起始點，這是因為變量c、d是在判定語言「if(b＜10){處理p1}else{處理p2}」的處理p1、p2中定義的緣故。
分配對象作為資源的分配對象，還有單純地取變量的情況，但是，對於一個變量存在多個生存區間時，可以對各個生存區間分配各自的資源元素，所以，在本說明書中分配對象是指變量和生存區間的組合，分配對象保持變量和生存區間。這裡，當如圖1的變量b那樣存在多個生存區間時，為了相互區別起見，對於分配對象b1、b2，作為獨立的分配對象表示。
而將「定義」、「引用」、「使用」分配對象保持的變量分別稱之為「定義」、「引用」、「使用」保持該變量的分配對象。並將分配對象定義的中間命令和引用的中間命令分別稱做該分配對象的定義中間命令、引用中間命令，而將定義和引用中間命令合併稱之為使用中間命令。
分配優先級進行分配時用於決定分配對象的分配順序的參數。
計算分配優先級有各種各樣的方法。例如，下面{公式1}中所示即為以程序中的分配對象的使用率作為分配優先級時的計算公式的例子。
{公式1}分配優先級＝使用率＝分配對象使用的中間命令的個數/生存區間的長度另外，在程序中的循環處理中存在分配對象使用的中間命令時，亦可在分配優先級中算入其循環層次。
例如分配優先級＝使用率＝使用中間命令存在的循環層次總和/生存區間的長度。
資源元素是計算機硬體的元素中可以對分配對象分配的最小單位。暫時保存值的緩存器和各個寄存器、存貯器中的單位地址的存貯器元素即為其例子。0號寄存器、1號寄存器、地址100的存貯器、地址101的存貯器即分別為別的資源元素。
資源表示完成相同功能的資源元素的集合。
例如，在資源中存在寄存器和存貯器。另外，寄存器能像地址寄存器(AR)、數據寄存器(DR)、全局寄存器、局部寄存器這樣按完成相同功能來加以分類。存貯器則能像高速存貯器、低速存貯器那樣以實現相同功能來分類。這樣，只要資源元素能按完成相同功能加以分類，則其分類就成為各個資源。
幹涉圖形是用圖形來表示分配對象與分配對象之間的生存區間的重疊的圖象。
幹涉圖形是以分配對象作為圖形的頂點，以生存區間作為相互連結重疊的分配對象(頂點)的邊來描繪的。
頂點的次數在幹涉圖形中，是與頂點連接的邊數。
圖2是編譯程序的結構圖。編譯程序由語法分析設備11、優化設備12、資源分配設備63、代碼生成設備14組成。下面，利用圖1、圖2的結構圖及圖3A、3B、3C的說明圖說明該編譯程序的各組成部分。
語法分析設備11對作為文件存貯在存貯裝置(圖外)中的源程序進行句法分析、語法分析和語義分析，將源程序變換成中間程序。例如，將圖3A的源程序變換成圖1的中間程序。
優化設備12為了改善最後生成的機器語言程序的程序大小及處理執行時間對中間程序作優化處理。由於優化過程的細節不是本發明的主要著眼點，所以，說明從略，僅對與資源分配處理特別相關點加以說明。優化操作中包含有稱為基本分塊化、控制流分析、數據流分析的操作。基本分塊化處理是將處理對象程序分割成基本程序塊。
現對這種分割處理作簡單說明。首先，優化設備12檢測中間程序的最初的中間命令、無條件或條件轉移的目的中間命令、無條件或條件轉移之後的中間命令，將所檢測的這些作為引導。優化設備12，由此引導開始提取直至下一引導的前一個或直至程序的最後為止的一系列中間命令。利用該提取處理得到的命令串稱為基本程序塊，作為以後的處理單位。
控制流分析是指對各基本程序塊間的控制流程進行分析。
數據流分析是指對各基本程序塊中各個的變量在何處定義，在何處被引用的情況進行分析。參照這些分析結果可以獲得變量的生存區間的信息。
資源分配設備63採用作為資源分配用算法之一的利用圖形退化的圖形彩色法，將寄存器、存貯器分配給中間程序中的分配對象。利用圖形退化的圖形彩色法是指在進行幹涉圖形各頂點的分色時按照如果以邊連接就塗不同的顏色的規則近似地以最少的顏色數來進行幹涉圖形各頂點的分色的算法。圖3A的程序中的分配對象通過資源分配處理，如圖3B那樣分配資源元素。在本圖中，示出了對圖3A所示的分配對象分配資源元素R0，對分配對象b2分配資源元素R2。
代碼生成裝置14如圖3c所示的那樣使中間程序內各中間命令實現機器語言命令化，將中間程序變換成目標機器能識讀的機器語言程序。將這樣由代碼生成裝置14變換的機器語言程序稱為目標程序。此目標程序中的機器語言命令與圖1的源程序和中間程序的對應用符號①②③④表示。在上述機器語言命令化中，對各機器語言命令的操作數使用圖3B中所示的資源分配結果。另外，圖中的傳輸命令t11、t12、t13、t14、t15……是為了圖1的中間程序的各中間命令的處理利用機器語言命令實現而由代碼生成設備14生成的。按照資源分配的結果，也有可能某幾個這種傳送命令是不用的。在圖3c中，由於分配對象b2和c分配給同一寄存器，所以，⑦是無需生成傳送命令的例子。
下面對資源分配設備63進行說明。上述採用圖形彩色法的資源分配處理的詳情在下列文獻中有記載。
作為現有的資源分配方式，特別是寄存器的分配方式的有[1]A.V.Aho，R.Sethi，J.D.Ullman「CompilersPrinciples，Techniques and Tools(編譯程序原理，技術及工具)」，Addison-wesley，1986[2]Chaitin「Register Allocation and Spilling via graphcoloring(通過圖形彩色進行寄存器分配和散失)」US Patenr No.4 571 678，Feb.18，1986[3]Frederick Chow，John Hennessy「Register Allocation byPriority-based Coloring(利用優先級的彩色進行寄存器分配)」，Compnter Systems Laboratory，Stanford University[4]David Bornstein，…Ron Y.Pinter「Spill Codeminimization techniques of ontimizing compilers(優化編譯程序的散失碼最小化技術)」，SIGPLAN 1989，IBM Israel Science andTechonolugy Techniow City Haifa Israel[5]佐佐政孝「プロゲラミング言語處理系(程式語言處理系統)」，巖波書店レヅスタ割付け(寄存器分配)p420～p423。森、他「複合バンク機構み考慮レた系統的存レジスタ割當て方式とその一般化(考慮複合存貯裝置的系統的寄存器分配方式及其通用化)」，情報處理學會Vol.30，No，6，Jun，1989(基本上是以基於寄存器彩色法為主流。)上述資源分配設備63的結構示於圖4。如圖4所示，資源分配設備63具有根據優化設備12的處理結果生成分配對象的分配對象生成部分71、保存由分配對象生成部71所生成的分配對象的分配對象保持部分72、應用上述{公式1}所示的計算式計算並存儲該保持部所保持的各分配對象的優先級的優先級計算部73、存貯關於圖1所示的各分配對象的生存區間的信息和該生存區間如何重疊的信息的生存區間信息存貯部74、將保持部所保持的全部分配對象展開成幹涉圖形狀的展開部75、用於展開部進行展開用的緩存器76、用於裝載全部由展開部暫時展開的分配對象的堆棧77、以上述利用圖形退化的圖形彩色法進行資源分配的控制部80和以圖3B的形式存貯資源分配結果的存貯部78。
圖5A、5B及圖6A～6I用來說明利用圖形退化的圖形彩色法。現在利用這些圖來說明上述資源分配設備63的處理情況。這裡，設能分配的寄存器為三個，沒有分配給寄存器的即分配主存貯器。
上述展開部75用圖5A所示的幹涉圖形表示圖1所示的分配對象和該分配對象的生存區間的重疊。在這樣的幹涉圖形中，各分配對象具有怎樣的分配對象和生存區間的重疊用由頂點發出的邊數(次數)表示。另外，由於在圖5B所示的分配對象中生存區間的終點和始點在1中間命令中彼此相一致的(圖1的分配對象b2、c)可看作是一個分配對象，所以，圖5B所示的控制部80將各自相對應的頂點加以結合來簡化幹涉圖形(圖5B分配對象b2、c)。這樣簡化之後幹涉圖形的頂點中出現高低不同的現象，頂點的次數在寄存器的數量小於3時的頂點稱為次數低的頂點，次數大於寄存器的數量的頂點稱為次數高的頂點。這種次數的高低被用作為圖形退化的成立條件。所謂圖形退化是指，如圖6A的矢量y11、y12指示的那樣按由{公式1}求得優先級低的順序消除次數低的頂點，將對消除的頂點的分配對象裝載入後進先出式的堆棧區內，消除e2和d的結果是圖5A和5B所示的幹涉圖形向圖6B所示狀態變遷。
在此圖6B的狀態下，由於所有頂點的次數都高，所以，上述條件不成立。因此，在這些頂點中，如矢量y13所示的那樣，對優先級最低的分配對象b1分配存貯器消除頂點b1。通過消除該頂點b1，幹涉圖形向圖6c變遷，上述成立條件再次成立。在圖6c的狀態下再次反覆進行圖形退化處理，如圖6D所示的那樣將全部分配對象裝入堆棧。在這樣裝載處理結果之後，進行資源分配處理。首先，如圖6E所示從堆棧頂點取出分配對象a，將寄存器R0分配給分配對象a，同樣，從堆棧頂點取出分配對象e1、b2c，如圖6F、6G所示，將寄存器R1、R2分配給分配對象e1、b2c。下一順序的分配對象e2、d與b2c的生存區間重疊，但與分配對象a、e1的生存區間不重疊，所以，如圖6H中所示，將能分配的寄存器中號碼最小的寄存器R0分配到分配對象e2，同樣，如圖6I所示，將寄存器R1分配給分配對象d。藉助這樣的分配處理，可將不同的寄存器分配給生存區間相互重疊的分配對象。
上述分配對象a、b2、c、d、e1、e2、b1通過資源分配處理分配某個資源元素，在C語言等高級語言中存在預先設定與分配對象的組合的寄存器。這就是為了實現提高函數調用操作的效率所採用的寄存器，稱為自變量寄存器、返回值寄存器、破壞性寄存器。
自變量寄存器是指在調用函數時以寄存器引渡自變量所用的寄存器。中間程序中作為自變量使用的分配對象分配這種自變量寄存器。
返回值寄存器是用於送回函數調用的返回值的寄存器。中間程序中用於送回返回值的分配對象分配此返回值寄存器。
破壞性寄存器是分配給在函數調用開始和結束時的存放值無需保留的寄存器。這種破壞性寄存器的目的是為減輕函數調用的總開銷。在進行上述函數調用時，利用在所調用的函數內的處理可以改寫各寄存器的內容，在函數調用的前後必須進行寄存器內容的保存、復元。但是，由於對全部寄存器進行這種保存、復元操作會使函數調用操作的總開銷增大，因此，預先設定不必進行寄存器內容的保存、復元作業的破壞性寄存器，為了在生存區間不合有分配對象中的函數調用命令，還是分配破壞性寄存器，以使保存、復元操作減少到最低限度。
但是，按照上述現有技術的資源分配設備，則存在只能進行使目標程序的執行時間、存貯器尺寸增大的資源分配的問題。現參照圖7對此問題進行說明。此圖中的豎線表示分配對象的生存區間，其中，空白部分表示未分配的分配對象，畫斜線的部分表示已經分配的分配對象。另一方面，在此圖中，由於表示分配對象x0、x1、x5的豎線具有與表示分割對象z0、z1、z2的豎線平行的部分，可見它們生存區間相互重疊。
例如，如圖7所示，生存區間相互連接的那些分配對象之間(分配對象x0、x1、x2、x3、x4、x5)通過上述頂點結合而結合為一個分配對象y。結合的分配對象y與已經分配了資源元素R0的分配對象z0、分配了資源元素R1的分配對象z1、分配了資源元素R2的分配對象z2的生存區間重疊。這樣，如果與已經分配的分配對象的生存區間相重疊，則分配給已經分配的分配對象的資源元素(資源元素R0、R1、R2)就不能分配給分配對象y。因此，組成分配對象y的分配對象x0、x1、x2、x3、x4、x5便全部分配了存貯器。如果將這些分配對象全都分配給存貯器，則將這些分配對象作為操作算符使用的中間命令就全部變換為將存貯器作為操作算符的機器語言命令。一般說來，操作算符在存貯器的機器語言命令的執行速度慢、存貯器的尺寸大時，將對目標程序的執行時間和存貯器的尺寸產生不良的影響。
另外，當資源分為3種以上的功能時，若不進行與資源的功能對應的分配對象的分配，就會對目標程序的執行時間和存貯器尺寸產生不良的影響。
在上述文獻中，[6]所記載的內容是描述關於參照地址寄存器、數據寄存器等多種不同類的寄存器進行訪問所需要的成本的資源分配。在該文獻中，附加所謂的「保持C語言中的指針式那樣的地址型變量的分配對象全都分配至地址寄存器」的規則。但在地址型的分配對象中，也可以存在加法運算和減法運算中多次使用，並且，少量進行存貯器作的間接引用的分配對象。關於數據寄存器，在具有高速加法運算和減法運算的目標機器中，如果一律將這樣的分配對象分配到地址寄存器，在目標程序中就會產生多個從地址寄存器向數據寄存器傳送的傳輸命令，結果，將使目標程序的存貯器的尺寸和執行時間增大。
這樣，只單純考慮在訪問某種寄存器時所必須的成本，反而會招致生成很多傳輸命令。
另外，還存在有無法實現可能直接利用為了改善函數調用效率而設定的自變量寄存器、返回值寄存器、破壞性寄存器的存貯值進行資源分配方面的問題。
圖形彩色法是一種為了最適當地區別幹涉圖形的頂點的近似算法。由於自變量寄存器、返回值寄存器、破壞性寄存器是在算法執行前預先分配給分配對象的資源元素，所以，在幹涉圖形中這些寄存器被看做是著色的頂點。為了實現能直接利用返回值寄存器、自變量寄存器的存放值的資源分配，如果將著色的頂點編入幹涉圖形內是有效的，就必須進行將其他頂點著色成這種顏色的處理，這就超出了圖形彩色法的範圍。鑑於上述理由，通常作為圖形彩色法中分配的寄存器必須準備用於各個獨立的自變量寄存器、返回值寄存器、破壞性寄存器的寄存器。並且，為了使用自變量寄存器、返回值寄存器的存放值，需要分配用寄存器的傳輸命令。這樣，如果需要傳輸命令，則必然增大與追加該命令對應的目標程序的存貯器大小和執行時間。
上述問題所造成的影響僅在寄存器的數量足夠充裕的情況下才可以不考慮。但是，如許多面向機內用途的微處理器那樣限制寄存器的數量時，或者在設置完成功能不同的寄存器數量少但品種多時，這些問題就顯得很突出了。
本發明的第一目的在於提供一種能按優先級順序將資源元素分配給分配對象、並且可以通過將傳送命令的生成數量限制到最低限度而將目標程序的存貯器大小和執行時間限制到最低限度的資源分配設備。
本發明的第二目的是提供能對嵌套級深的場所優先分配寄存器並能獲得將這種已分配的寄存器不斷向嵌套級淺的場所擴散的靈活的分配結果的資源分配設備。
本發明的第三目的在於提供能在使用頻度高的場所優先分配寄存器並能獲得不斷地將這些已經分配的寄存器擴散到使用頻度低的場所的靈活的分配結果的資源分配設備。
本發明的第四目的是提供詳細地掌握生存區間的連接和已分配場所的遠近及重疊而進行資源分配的資源分配設備。
本發明的第五目的在於提供能夠確實地理解微處理器具有的資源的各個功能並適當地分配給分配對象的資源分配設備。
本發明的第六目的是提供自變量寄存器、返回值寄存器、破壞性寄存器等分配的對象預先確定的分配對象能夠實現將其資源向周圍擴展的那樣靈活的資源分配的資源分配設備。
本發明的第一、第四目的可以按如下方式達到，即在將以高級語言編寫的程序翻譯成為機器語言程序的編譯程序中使用的、生成多個作為以程式語言描述的程序中的變量與生存區間的組合的分配對象、順序將具有寄存器、存貯器等硬體資源的資源元素分配給所生成的分配對象的資源分配設備中，具有根據分配對象中已經被分配的分配對象的生存區間與下一個應分配的分配對象的生存區間之間在程序中具有怎樣的位置關係來對各資源元素計算出表示下一個應分配的分配對象中哪個資源元素合適的得失值的得失值計算裝置、根據對各資源元素計算出的得失值的大小，將哪一資源元素分配給應分配的分配對象的分配裝置和反覆啟動得失值計算裝置及分配裝置直至所有分配對象均被分配為止的控制裝置。
利用這種結構，生存區間具有互相連接的位置關係的多個分配對象群根據生存區間的長短增加得失值，另外，因為在該群中的分配對象中儘管已分配的分配對象和生存區間重複，分配不同的資源元素，所以，生存區間相互連接的多個分配對象不是一律地分配到同一資源元素，而是以對生存區間的遠近發生影響來進行資源分配。因而，周圍的分配狀態將影響下次的資源分配，從而可以進一步減少傳輸命令。
這裡，如所述的那樣，上述資源分配設備具有判定程序中各分配對象的位置關係的位置關係判定裝置。此位置關係判定裝置設置有判定已被分配資源元素的分配對象的生存區間與應分配的分配對象的生存區間是否重複的重複關係判定裝置，和判定已被分配資源元素的分配對象的生存區間與應分配的分配對象的生存區間是否連接的已分配—被分配間連續判定裝置。得失值計算裝置設置有在由已分配—被分配間連續判定裝置判定應分配的分配對象與生存區間為連接時，就根據從已被分配資源元素的分配對象到應分配的分配對象的生存區間長短，使判定為連接的已分配的分配對象增加被分配的資源元素的得失值的第一增加部。分配裝置不將分配給具有由重複關係判定裝置判定生存區間重複的已分配的分配對象的資源元素分配給應分配的分配對象，而將判定為生存區間不重複的已分配的分配對象中得失值最大的資源元素分配給應分配的分配對象。
如所述的那樣，位置關係判定裝置設置有檢測具有與已分配了資源元素的分配對象重疊的生存區間的未分配的分配對象的已分配一側的重疊分配對象檢測裝置和判定所檢測的未分配的分配對象的生存區間與應分配的分配對象的生存區間是否連接的未分配—被分配間連續判定裝置。得失值計算裝置設置有當判定為連接時根據從由已分配一側的重疊分配對象檢測裝置檢測的未分配的分配對象到應分配的分配對象止的生存區間的長短減少分配給該已分配的分配對象的資源元素的得失值的第一減小部。
另外，由於通過減小得失值從應分配的分配對象角度看分配給發生損失的位置的分配對象的資源元素評估為較低級的，所以，周圍的分配狀態將影響下次的資源分配，從而可以大為減少傳輸命令。
如所述的那樣，當利用分配畢側重疊分配檢測裝置判定有多個未分配的分配對象時，未分配—被分配間連續判定裝置就判斷在被檢測出的多個未分配的分配對象中哪一個生存區間與應分配的分配對象的生存區間連接。
按照上述就能夠防止通過檢測未分配的分配對象，多次減少已分配的分配對象所分配的資源元素的得失值，可以防止比其他情況評價為較低級的。
本發明的第二、三目的如所述的那樣，具有與各分配對象相對應地存貯反映程序中分配對象的使用頻度和/或生存區間的嵌套級的分配對象優先級的優先級存貯裝置，得失值計算裝置和分配裝置按照優先級存貯裝置存貯的優先級順序確定應分配的分配對象。
按照上述由於按照使用頻度或嵌套水平高的順序進行資源元素分配，所以，可以實現計及生存區間的位置關係、使用頻度和嵌套級的資源分配，從而可以提高目標程序的質量。
如所述的那樣，位置關係判定裝置設置有當由得失值計算裝置對各資源元素計算出的得失值在多個資源元素相互間具有相同大小時，就檢測具有與應分配的分配對象的生存區間重疊的生存區間的未分配的分配對象的被分配一側重疊分配對象檢測裝置，和判定檢測的分配對象的生存區間與已分配了資源元素的分配對象的生存區間是否連接的未分配—已分配間連續判定裝置。得失值計算裝置設置有檢測由被分配一側重疊分配對象檢測裝置檢測的分配對象的優先級的優先級檢測部計算從已分配的分配對象到被檢測得的未分配的分配對象的生存區間長短的第一長短計算部和將檢測的優先級乘以所計算出的長短值，並根據此計算結果減小該已分配的資源元素的得失值的第二減小部。
由此，按照上述，由於通過減小得失值，從應分配對象方面看分配給發生損失的位置的分配對象的資源元素評價為較低級的，所以，周圍的分配狀態對下次的資源分割產生影響，從而可以大為減少傳輸命令。
如所述的那樣，位置關係判定裝置設置有，檢測具有與已分配了資源元素的分配對象的生存區間重疊的生存區間的未分配的分配對象的已分配一側重疊分配對象檢測裝置和判定由被分配一側重疊分配對象檢測裝置檢測的未分配的分配對象的生存區間是否與由已分配一側重疊分配對象檢測裝置檢測的未分配的分配對象的生存區間相連接的未分配—未分配間連續判定裝置。得失值計算裝置設置有，計算從由被分配一側重疊分配對象檢測裝置檢測的未分配的分配對象開始到由已分配一側重疊分配對象檢測裝置檢測的未分配的分配對象的生存區間長短的第二長短計算部和將檢測的優先級乘以計算出的減短值並根據此乘法結果使分配給已分配的分配對象的資源元素的得失值增大的第二增加部。
按照上述，由於通過增大得失值從應分配的分配對象方面看分配給獲益的位置的分配對象的資源元素評價為較高級的，所以，周圍的分配狀態對下次的資源分配產生影響，從而可以大為減少傳輸命令。
如所示的那樣，當由已分配一側重疊分配對象檢測裝置判定為多個未分配的分配對象時，未分配—未分配間連續判定裝置判斷所檢測的多個未分配的分配對象中哪一個生存區間與應分配的分配對象的生存區間連接。
按照上述，通過檢測未分配的分配對象，多次減少分配給已分配的分配對象的資源元素的得失值，可以防止比其他情況評價為較低級的。
如所述的那樣，資源分配設備設置有對應地存貯全部資源元素和各個別資源元素的得失值的初始值的得失值存貯部。第一及第二增加部使得失值存貯部存放的各資源元素的得失值增加，第一及第二減少部使失值存貯部存放的各資源元素的得失值減小。
按照上述，得失值存貯部所存放的各資源元素的得失值由第一及第二增加部增加，得失值存貯部中所存放的各資源元素的得失值由第一及第二減小部減小。因此，從應分配的分配對象方面看，即使將同一資源元素分配給獲益的位置和發生損失的位置，也能客觀地評價該資源元素帶來何種程度的利益或損失，從而可以更周密進行資源分配。或者，由於得失值存貯部對應地存放全部資源元素和各資源元素的得失值的累計的初始值，所以，如果全部資源元素分配給發生損失的位置，則不論未分配給哪一個分配對象的資源元素的得失值都比較大。因此，可以將不論未分配給哪個分配對象的資源元素分配到應分配的分配對象。
如所述的那樣，本發明的第五目的，可以按如下方式達到，即具有當在程序中分配各資源的資源元素時，通過對應分配的分配對象與各資源元素的組合計算出其集合值的推斷值來估算應分配的分配對象定義的全部定義命令和使用的全部使用命令的執行周期和/或代碼大小的總和值達到何種程度的推斷裝置和比較各資源元素的推斷結果即推斷值並判斷推斷值為最小的資源元素是一個還是多個的資源元素單復判定裝置。當判定為一個時，前述分配裝置將推斷值最小的資源元素分配給應分配的分配對象，當判定為多個時將得失值為最大的資源元素分配給應分配的分配對象。
按照上述，在切換使用推斷值還是使用得失值後而使用推斷值時，由於能將代碼大小及執行時間反映到資源分配中，所以，可以充分靈活運用微處理器所具有的命令的詳細的成本信息，為了從分為三種以上的功能的資源分配給分配對象，所以選出合適的多個資源元素。在開發面向具有多個功能不同的資源的機構用途的微處理器的程序時，如果使用本發明的編譯程序，就能作成充分發揮該微處理器具備的功能的目標程序。
如所述的那樣，推斷裝置具有使用機器語言的命令格式對程序中的分配對象的全部定義命令及使用命令輸出表示程序中的分配對象的定義命令及使用命令的信息即命令模式的命令模式輸出部、與由命令模式輸出部輸出的命令模式分別對應地存貯表示在機器語言命令的各操作數中應用各資源的資源元素時的該定義命令及使用命令的執行周期和/或代碼大小的成本的成本存貯部和由成本存貯部取出與所輸出的命令模式相對應的成本並將所取出的成本按各資源元素求和後將求和所得的總和值作為推斷值的成本總和部。
按照上述，由於為了使分配對象的定義命令及使用命令實現機器語言化而精密地判斷哪種資源的資源元素合適，所以，可以作成充分發揮目標機器的微處理器所備有的功能的目標程序。
如上述所述的那樣，資源分配設備具有當由得失值計算裝置對各資源元素計算出的得失值在多個不同資源的資源元素之間具有相同的大小時，對優先級比應分配的分配對象低並在應分配的分配對象之後分配的全部未分配的分配對象預測最適宜的資源元素的預測裝置，而上述分配裝置將由預測裝置預測的資源元素分配給應分配的分配對象。
按照上述，當對已分配的資源元素計算的得失值在多個不同的資源的資源元素之間成為同樣大小時，由於分配裝置根據預測為與優先級更低的所有的分配對象相適應的資源元素，將資源元素分配給應分配的分配對象，所以，根據利用得失值的比較難分優劣時，便可進行更精密的資源元素的選擇。結果，便可進行優先級更低的全部分配對象的定義命令、使用命令的執行時間和/或代碼尺度小的資源分配。進而，如果這樣分配資源元素，由於在進行下一個分配對象的分配時可以繼承該資源元素，所以，生存區間互相連接的分配對象能夠分配同一資源元素的可能性就提高了。
如上所述的那樣，預測裝置具有如下裝置的結構，即檢測所有具有與應分配的分配對象所具有的生存區間連接的生存區間並且優先級比該分配對象低的未分配的分配對象的第一後續分配對象檢測裝置，通過對由第一後續分配對象檢測裝置檢測的全部分配對象與各資源元素的組合計算出該總和值的推斷值來推斷當將各資源元素分配給所檢測的各分配對象時該分配對象定義的全部定義命令和使用的全部使用命令的執行周期和/或代碼大小的總和值達到何種程度的第一推斷裝置、對由第一後續分配對象檢測裝置檢測的每一分配對象計數介於第一後續分配對象檢測裝置檢測的各分配對象與應分配的分配對象之間的連續的生存區間的長度的第一生存區間長度計數裝置、將對所檢測的各分配對象計數的生存區間的長短作為加權值，對由第一推斷裝置對檢測的分配對象與各資源元素的組合所計算的推斷值進行加權的第一加權裝置、將由第一加權裝置加權的推斷值對每一資源元素進行求和的第一求和裝置和將由第一求和裝置求和的總和結果為最小的資源元素判定為與優先級比應分配的分配對象低的未分配的分配對象最適合的第一最佳資源元素判定裝置。
按照上述，由於在優先級更低、並在應分配的分配對象之後進行分配的分配對象中，根據生存區間相互連續的定義命令、使用命令的執行時間和/或代碼大小的推斷值的大小和未分配的分配對象離應分配的分配對象多遠進行預測，所以，位於接近應分配的分配對象的位置上的分配對象的定義命令、使用命令的執行時間和/或代碼大小評估為大的，而將位於離應分配的分配對象遠的位置上的分配對象的定義命令、使用命令的執行時間和/或代碼大小評估為小的。因此，只要將同一資源元素分配給生存區間相互連續的分配對象便可提高可能性。結果，對於後續的分配對象，可以可靠地進行使執行時間和/或代碼大小減小的資源元素的預測。
如上所述的那樣，預測裝置具有如下裝置的結構，即當由第一最佳資源元素判定裝置判定多個資源元素最合適時檢測生存區間與應分配的分配對象重疊的未分配的分配對象和具有與此未分配的分配對象的生存區間相連接的生存區間的未分配的分配對象的第二後續分配對象檢測裝置、通過對檢測的分配對象與各資源元素的組合計算出該總和值的推斷值來推斷當對由第二後續分配對象檢測裝置檢測的未分配的分配對象分配以各資源元素時被檢測的各分配對象定義的全部定義命令和使用的所有使用命令的執行周期和/或代碼大小的總和值達到何種程度的第二推斷裝置、對由該第二後續分配對象檢測裝置檢測的每一分配對象計數介於應分配的分配對象具有的生存區間與生存區間重疊的未分配的分配對象和具有與此重疊一側的分配對象的生存區間連接的生存區間的分配對象之間而連續的生存區間長度的第二生存區間長度計數裝置、將對該分配對象計數的生存區間的長短和各分配對象的優先級作為加權值對於由第2推斷裝置對由第二後續分配對象檢測裝置檢測的未分配的分配對象與各資源元素的組合推斷的推斷值進行加權的第二加權裝置、將經第二加權裝置加權後的各分配對象的推斷值對每一資源元素進行求和的第二求和裝置和將由第二求和裝置求和的各資源元素的總和值為最大的資源元素判定為與在應分配的分配對象之後進行分配的全部未分配的分配對象最合適的資源元素的第二最佳資源元素判定裝置。
按照上述，由於在優先級更低並在應分配的分配對象之後進行分配的分配對象中，根據生存區間重疊一側的分配對象的定義命令、使用命令的執行時間和/或代碼大小的推斷值的比較和應分配的分配對象離未分配的分配對象多遠進行預測，所以，對於後續的分配對象，可以可靠地進行使執行時間和/或代碼尺度減小的資源元素的預測。
如上所述的那樣，第一和第二加權裝置在由第一和第二生存區間長度計數裝置計數的分配對象的生存區間長度為0時，將1作為生存區間的長短進行加權，當計數的生存區間的長度不是0時，就計算該生存區間長度的倒數，並將算出的生存區間長度的倒數作為生存區間的長短進行加權處理。
按照上述，由於計算應分配的分配對象的生存區間長度與由求和部求和的生存區間長度之和的倒數、並由倒數計算部將計算結果作為生存區間的長短，所以，可以將生存區間的長度之和反映在資源分配中，從而可以更多地減少傳輸命令。
如上所述的那樣，資源分配設備中還具有存貯多個使用機器語言命令格式表示程序中的分配對象的定義命令和使用命令的信息即命令模式和與各命令模式對應地存貯表示在機器語言命令的各操作數中使用各資源的資源元素時程序中的分配對象的定義命令及使用命令的執行周期和/或代碼大小的成本的成本存貯裝置。第一推斷裝置具有讀取與由第一後續分配對象檢測裝置檢測的未分配的分配對象的所有定義命令及使用命令對應的命令模式並將讀出的命令模式輸出的第一命令模式輸出部和從成本存貯裝置取出與輸出的命令模式對應的成本並將取出的成本對每一資源元素求和從而將求和的總和值作為推斷值的第一成本求和部。第二推斷裝置具有讀出與由第二後續分配對象檢測裝置檢測的未分配的分配對象的全部定義命令及使用命令對應的命令模式並將讀出的命令模式輸出的第二命令模式輸出部和從成本存貯裝置取出與輸出的命令模式對應的成本並將取出的成本對各資源元素進行求和從而將求和的總和值作為推斷值的第二成本求和部。
按照上述，由於為了使分配對象的定義命令及使用命令實現機器語言命令化而精密地判斷哪一資源的資源元素最適合，所以，對於後續的分配對象，可以更可靠地進行使執行時間和/或代碼大小減少的資源元素的預測。
本發明的第六目的，可以如所述的那樣，利用如下方式實現，即資源分配設備進而還具有從前述程序中檢測應分配的資源元素預先確定的分配對象的預約分配對象檢測裝置和存貯應分配給預約分配對象檢測裝置檢測的分配對象的資源元素的預約資源元素存貯裝置。分配裝置將應分配的資源元素分配給由預約分配對象檢測裝置檢測的分配對象，並在分配之後將某個資源元素分配給優先級最大的分配對象。
按照上述，可以將自變量寄存器、返回值寄存器、破壞性寄存器分配給其他分配對象，從而可以進行能直接利用自變量寄存器、返回值寄存器、破壞性寄存器的存貯值的資源分配。因此，可以更多地減少傳輸命令。
如所述的那樣，分配對象的生存區間的起始點和結束點均用程序中的命令位置信息表示。資源分配設備進而還具有分別對應地存貯程序中的分配對象、與各分配對象的生存區間的起始點相當的命令位置信息和與各分配對象的生存區間的結束點相當的命令位置信息的起始結束點存貯裝置、參照起始結束點存貯裝置查找出程序中與各分配對象的生存區間的起始點相當的命令位置信息和與結束點相當的命令位置信息、並將找出的分配對象和程序中的分配對象作成同一生存區間繼承關係集合的第二集合化裝置、參照起始結束點存貯裝置查找出程序中與各分配對象的生存區間的結束點相當的命令位置信息和與結束點相當的命令位置信息，並將找出的分配對象和程序中的分配對象作成同一生存區間繼承關係集合的第二集合化裝置和將程序中的分配對象與由第一及第二集合化裝置進行集合化處理後的生存區間繼承集合對應地寫入生存區間繼承關係集合存貯部的寫入裝置。
按照上述，由於利用寫入裝置將程序中的分配對象和由第一及第二集合化裝置進行集合化處理後的生存區間繼承集合對應地寫入生存區間繼承關係集合存貯部，所以，可以更有效地判斷生存區間的繼承和非繼承。
如所述的那樣，是一種將用高級語言編寫的程序翻譯成機器語言程序的編譯程序並將寄存器、存貯器等硬體即資源具有的資源元素分配給用程式語言描述的程序中的變量和生存區間的組合即分配對象的資源分配設備，該資源分配設備具有與優先級對應地保持程序中的分配對象的分配對象保持裝置、從前述分配對象保持裝置取出優先級最高的分配對象將某個資源元素分給此優先級最高的分配對象的第一資源元素分配裝置、從前述分配對象保持裝置中取出相對於此前分配的分配對象的優先級，具有下一位的優先級的分配對象的分配對象取出裝置、對於前述分配對象取出裝置取出的分配對象，檢測生存區間重疊的分配對象的一次重疊分配對象檢測裝置、對於前述一次重疊分配對象檢測裝置檢測的分配對象檢測已分配的資源元素的資源元素檢測裝置、檢測已分配了與檢測的資源元素不同的資源元素的全部分配對象的分配對象—資源元素檢測裝置、在由分配對象—資源元素檢測裝置檢測的已分配的分配對象中判斷生存區間與由分配對象取出裝置取出的分配對象連接的全部分配對象的增益一側連續已分配的分配對象判斷裝置、根據從判定為連續的已分配的分配對象到由分配對象取出裝置取出的分配對象的生存區間長短，對分配給判定為生存區間連續的分配對象的全部資源元素，計算出表示已分配給分配對象的資源元素對此後要分配的分配對象適合到何種程度數值即得失值的第一得失值計算裝置、將計算出的得失值對由分配對象—資源元素檢測裝置所判定的各資源元素進行累計的累計裝置、將由累計裝置累計的累計值為最大的資源元素分配給由分配對象取出裝置取出的分配對象的第二分配裝置和反覆起動前述分配對象取出裝置直到全部分配對象分配完為止的控制裝置。
如所述的那樣，資源分配設備還具有在由分配對象—資源元素檢測裝置檢測的已分配的分配對象中判斷生存區間與由分配對象取出裝置取出的分配對象不連接而且生存區間不重疊的分配對象的第一非重疊非連續已分配的分配對象判斷裝置、對於生存區間與由第一非重疊非連續已分配的分配對象判斷裝置判斷的已分配的分配對象的生存區間重疊的未分配的分配對象，檢測生存區間與由分配對象取出裝置取出的分配對象連續的分配對象的增益一側連續未分配的分配對象檢測裝置、根據從由增益一側連續未分配的分配對象檢測裝置檢測的未分配的分配對象到由分配對象取出裝置取出的分配對象的生存區間長短，計算分配給由第一非重疊非連續已分配的分配對象判斷裝置判斷的已分配的分配對象的資源元素的得失值的第二得失值計算裝置和從關於由前述累計裝置累計的該資源元素的得失值減去由第二得失值計算裝置計算的得失值的第一減法裝置。第二分配裝置將由第一減法裝置對得失值進行減法運算後的得失值為最大的資源元素分配給分配對象取出裝置取出的分配對象。
按照上述，由於將已分配的分配對象中得失值大的分配給應分配的分配對象，所以，在將資源元素分配給分配對象的過程中，可以精密地判斷向分配對象分配的資源元素的分配狀況。因此，存貯器與寄存器間、和寄存器與寄存器間的傳輸命令也減少，從而可以提高最後生成的機器語言程序的程序大小和執行速度。尤其是在對寄存器數量少的目標機器進行資源分配時，上述程序大小和執行速度的提高特別明顯。
如所述的那樣，資源分配設備還具有在由分配對象—資源元素檢測裝置檢測的已分配的分配對象中判斷生存區間與由一次重疊分配對象檢測裝置檢測的分配對象連續的重疊一側連續已分配的分配對象判斷裝置、根據從由重疊一側連續已分配的分配對象判斷裝置判斷的已分配的分配對象到由一次重疊分配對象檢測裝置檢測的分配對象的生存區間的長短，計算分配給由重疊一側連續已分配的分配對象判斷裝置判斷的已分配的分配對象的資源元素的得失值的第三得失值計算裝置和從由經前述累計裝置累計的關於該資源元素的累計值中減去由第三得失值計算裝置計算的得失值的第二減法裝置。第二分配裝置將由第二減法裝置對得失值進行減法運算後的累計值為最大的資源元素分配給由分配對象取出裝置取出的分配對象。
按照上述，利用減小得失值，從應分配的分配對象方面看，將分配給發生損失位置的分配對象的資源元素評價為低級的，所以，周邊的分配狀況將影響下次的資源分配，從而可以更多地減少傳輸命令。
如所述的那樣，資源分配設備還具有在由分配對象—資源元素檢測裝置檢測的已分配的分配對象中判斷生存區間與由一次重疊分配對象檢測裝置檢測的分配對象不連接而且生存區間不重疊的分配對象的第二非重疊非連續已分配的分配對象判斷裝置、對於生存區間與由第二非重疊非連續已分配的分配對象判斷裝置判斷的已分配的分配對象的生存區間重疊的未分配的分配對象，判斷生存區間與由一次重疊分配對象檢測裝置檢測的分配對象連續的重疊一側連續未分配的分配對象判斷裝置、根據從重疊一側未分配的分配對象判斷裝置判斷的分配對象到由一次重疊分配對象檢測裝置檢測的分配對象的生存區間的長短，計算分配給由第二非重疊非連續已分配的分配對象判斷裝置判斷的已分配的分配對象的資源元素的得失值的第四得失值計算裝置和將由前述累計裝置累計的關於該資源元素的累計值與由第四得失值計算裝置計算的得失值相加的第二加法裝置。第二分配裝置將由第二加法裝置對得失值進行加法運算後的累計值為最大的資源元素分配給分配對象取出裝置取出的分配對象。
按照上述，通過減少得失值，從應分配的分配對象方面看，分配給發生損失的位置的分配對象的資源元素評價為低級的，因此周邊的分配狀況將影響下次的資源分配，從而可以更多地減少傳輸命令。
圖1為表示程序及該程序中分配對象的圖；圖2為編譯程序的結構圖；圖3A～3C是編譯程序的處理過程的圖；圖4是先有的資源分配裝置63的結構的圖；圖5A、5B是幹涉圖形和通過將該幹涉圖形頂點連接而幹涉圖形如何變化的圖；圖6A～6F是幹涉圖形發生圖形簡併的圖；圖7是表示頂點連接引起的問題的圖；圖8是實施例的資源分配設備13的結構圖；圖9為分配資源元素確定部26的結構圖；圖10為使用成本計算部34的結構圖；圖11A為推斷增益計算部36的結構圖；圖11B為資源類別成本計算部39的結構圖；圖12為資源分配控制部27的流程圖；圖13為資源元素確定部38的流程圖；圖14是使用成本計算控制部14的控制內容的流程圖；圖15是增益推斷控制部5 1的控制內容的流程圖；圖16為得失計算的流程圖；圖17是資源類別成本計算控制部501的控制內容的流程圖；圖18為後續成本計算子程序的流程圖；圖19是資源與成本的對應的圖；圖20是通過將各資源的資源元素分配給分配對象，該分配對象定義、使用的中間命令的成本如何增減的圖；圖21是已分配的分配對象的得失值如何增減的說明圖；圖22是已分配的分配對象的得失值如何增減的說明圖；圖23是未分配的分配對象的後續成本值成為何值的說明圖；圖24是分配對象保持部21的保持內容的一例的圖；圖25是分配對象保持部21的保持內容的一例的圖；圖26A是分配狀態表的保持內容的變化的一例的圖；圖26B是分配候補資源元素保持部31的保持內容的一例的圖；圖27A是運算成本表的一例的圖；圖27B是使用成本保持部的變化的一例的圖；圖28A是增益保持部37的保持內容變化的一例的圖；圖28B是得失保持部56的保持內容變化的一例的圖；圖28C是追蹤對象保持部52的保持內容變化的一例的圖；圖29A是已處理的分配對象保持部53的保持內容變化的一例的圖；圖29B是已損失的分配對象保持部54的保持內容變化的一例的圖；圖29C是重複分配對象保持部55的保持內容變化的一例的圖；圖30A是資源類別成本保持部40的保持內容變化的一例的圖；圖30B是資源類別總成本保持部505的保持內容變化的一例的圖；圖30C是追蹤對象保持部504的保持內容變化的一例的圖；圖31A是已處理分配對象保持部506的保持內容變化的一例的圖；圖31B是資源成本模式保持部502的保持內容變化的一例的圖；圖31C是評價資源保持部41的保持內容變化的一例的圖；圖31D是重複分配對象保持部507的保持內容變化的一例的圖；圖32是用高級語言編寫的程序的示例圖；圖33是程序例的中間代碼與分配對象的生存區間的圖；圖34是對圖33中的分配對象t265計算得失值時可尋求資源繼承關係的分配對象的圖。
下面，在對本發明實施例說明之前先對所用的術語加以說明。
循環層次所謂循環層次，是指循環的嵌套深度，中間命令的循環層次是指存在中間命令的循環的層次。例如，在圖33中，中間命令i1的循環層次為1。由於中間命令i8處在中間命令i31的轉移之前，所以循環層次為2。
多資源表示像存貯器等那樣具有較其他的裝置更豐富的資源元素，不論將哪個資源元素分配給分配對象也不會對生成代碼的質量產生特別的影響的資源。
分配資源是指以分配給分配對象的資源元素或多資源作為基元的集合。通常，對一個分配對象分配一個分配資源，但是這裡，如前所述，由於資源是指具有相同功能的資源元素的集合，所以，所謂將多資源R分配給分配對象，就是指將屬於R的某一資源元素分配給分配對象。
資源元素(廣義)表示分配資源的元素。下面，只要沒有特別申明，資源元素就是廣義的意義。
資源繼承關系所謂資源繼承關係是指可以繼承分配對象之間分配的資源元素的關係。另外，所謂資源元素的繼承，是指分配與已分配的資源元素相同的資源元素，通過分配這種相同的資源元素，可以省去在代碼生成設備中，生成傳輸命令。此外，還可以將已分配的資源元素向周圍擴展。在程序中，這種資源繼承關係利用生存區間的連續來表示。亦即，如果程序中的某一中間命令s1是分配對象y的生存區間的結束點，而且中間命令s1是分配對象x的起始點，則分配對象x與分配對象y就存在資源元素繼承關係。但是，生存區間的終始點一致，當即使分配同一資源元素也不能明顯地免除生成傳輸命令時，就不存在資源繼承關係。
例如，在程序的中間命令s1∶x＝y；中，當分配對象x的生存區間的起始點是中間命令s1、分配對象y的生存區間的結束點是中間命令s1時，如果分配對象x和分配對象y分配相同的資源元素，就不需要從分配對象y向分配對象x傳送。因此，分配對象x與分配對象y具有資源繼承關係。
另外，當目標機器是＝地址形式的微處理器、向運算符存貯運算結果時(目標機器的減法命令的被減數一側的操作數存貯運算結果時)，在程序的中間命令s2∶z＝x-w；中，當分配對象z的生存區間的起始點是中間命令s2、分配對象x的生存區間的結束點是中間命令s2時，分配對象x與分配對象z具有資源繼承關係。因此，如果對分配對象x與分配對象z分配相同的資源元素，就不用生成不需要的傳輸命令。但是，當分配對象w也是中間命令s2為生存區間的結束點時，如果對分配對象z分配資源元素，反而會增加傳輸命令，所以，分配對象z與分配對象w不存在資源繼承關係。
另外，通常當分配對象A與分配對象A1、分配對象A2……分配對象An-2與分配對象An-1、分配對象An-1與分配對象An分別存在資源繼承關係時，就說分配對象A與分配對象An「間接地存在資源繼承關係」。例如，在上述的中間命令s1、s2中，分配對象y與分配對象z通過分配對象x間接地存在資源繼承關係。
使用成本值所謂使用成本值是指如果將各個資源的資源元素分配給現在想分配的分配對象x時表示分配對象x使用的中間命令的代碼大小和執行時間達到何種程度的值。下面，照圖19及20中所示的使用成本計算例的說明圖說明中間命令和使用成本值的關係。
圖19是通過將各資源的資源元素成為運算符表示機器語言命令的代碼大小及執行時間如何增減的圖。
圖中，示出了「C(X，AR，INDIRECT REFERENCE)＝1」、「C(X，DR，INDIRECT REFERENCE)＝2」、「C(X，Mem，INDIRECT REFERENCE)＝3」數學表達式。它們表示為了用機器語言命令執行稱為「間接引用」的命令可以使用哪個資源。
「C(X，AR，INIRECT REFERENCE)＝1」表示用地址寄存器(AR)執行稱為間接引用的命令時存貯器大小或執行時間增加「1」。
「C(X，DR，INDIRECT REFERENCE)＝2」表示用數據寄存器(DR)執行稱為間接引用的命令時存貯器大小或執行時間增加「2」。
「C(X，Mem，INDIRECT REFERENCE)＝3」表示用存貯器(Mem)進行稱為間接引用的命令時存貯器大小或執行時間增加「3」。
另外，圖中的「C(X，Mem，ADDITION)＝3」表示用存貯器進行加法運算時存貯器大小或執行時間增加「3」。
「C(X，Mem，SUBTRACTION)＝3」表示用存貯器進行減法運算時存貯器大小或執行時間增加「3」。
在圖20中，左半部所示的是中間程序的例子。此中間程序內的一部分分配對象用○符號包圍，從該○符號伸出箭頭線。箭頭線a11從圖中的分配對象「s」伸出，a11的末端分為三個箭頭。位於該末端的「C(S，AR，INDIRECT REFERENCE)」「C(S，DR，INDIRECT REFERENCE)」「C(S，Mem，INDIRECTREFEPENCE)」表示分配對象s由間接引用命令的使用。其下面的「Cost(AR，S)＝1」「Cost(DR，S)＝2」「Cost(Mem，S)＝3」表示對分配對象s的使用成本值的總和。亦即，表示當將資源AR的資源元素分配給分配對象s時，其使用成本值為「1」，將資源DR的資源元素分配給分配對象s時，使用成本值為「2」。另外，還表示當將Mem分配給分配對象s時，使用成本值為「3」。
另外，在此程序例中三個地點存在有分配對象r，這些分配對象也用○符號包圍。並由此分配對象伸出箭頭線a13、a14、a15。在這些箭頭線的末端各自存在三個「C(r，AR，INDIRECTREFERENCE)」、「C(r，DR，INDIRECT REFERENCE)」、「C(r，Mem，INDIRECT REFERENCE)」，它們表示由於在基本程序中三個地方使用分配對象r，所以，對三個地方進行評價。這三個地方的使用成本值的總和為「Cost(AR，r)＝3」「Cost(DR，r)＝6」「Cost(Mem，r)＝9」。
按照箭頭線a11、a12、a13……所示的那樣，計算上述這種使用成本值的總和值時，如圖20下半部的表所示的那樣，可以得到全部分配對象的三種資源的使用成本值的總和。這一總和是對各分配對象合適、不合適的參數，該值越小，表示資源對該分配對象越合適。但是，這種使用成本的缺點是以代碼大小和執行時間為標準。所以，相同功能的數據寄存器D0～D2和地址寄存器A0～A2不論使用成本成為哪個相同的值，都只是一個大致的標準。
得失值得失值是指表示已分配給分配對象的資源元素對現在要分配的分配對象的影響有多大的值。因此，將得失值賦予已分配的各資源元素。將此得失值對每一資源元素累計的值稱為增益值。
下面，參照圖21所示說明圖說明已分配的資源元素的得失值達到多大的值。圖21是表示將增益因素作為處理對象時的各資源元素的得失值的說明圖。圖中的分配對象x按優先級的優先順序為第二位、分配的序號巡迴過來的分配對象(在以後的說明中如未加特別申明，均在這種意義上使用分配對象x)。
圖中所示的豎線表示分配對象的生存區間，其中，空白的表示未分配的分配對象，畫黑斜線的表示已分配的分配對象。該分配對象的生存區間的起點和終點用黑點「·」表示。在圖中的黑點中間存在用橫向虛線連接的情況。這表示生存區間的終點與起點一致，這樣便可知道，起始點和結束點利用虛線連結的分配對象之間存在資源繼承關係。在表示生存區間的豎線上分別以「分配對象x1」「分配對象x2」「分配對象x11」附加上表示具有該生存區間的分配對象的名稱的字符串。
在相應分配對象中，分配了資源元素的在該字符串正下方示出表示資源元素的名稱的字符串。從此表示該資源元素的名稱的字符串伸出箭頭線，在其箭頭端部有數學式「+1/L1」、「+1/(L1+L2)」、「+1/(L1+L3+L4)」，這些數式表示各資源元素的得失值。
在本圖中，由字符串「資源元素D2」伸出箭頭線，其箭頭端伸至數學式「+1/L1」，這表示分配給分配對象x3的資源元素D2的得失值為「+1/L1」。
由字符串「資源元素D3」伸出箭頭線，其箭頭端伸至數學式「+1/(L1+L2)」，這表示分配給分配對象x1的資源元素D3的得失值為「+1/(L1+L2)」。得失值成為這樣的值是因為生存區間長度L2，介於在分配對象x1的生存區間與分配對象x的生存區間之間，此生存區間長度反映在得失值中的緣故。
由字符串「資源元素D1」伸出箭頭線，其箭頭端伸至數學式「+1/(L1+L3+L4)」，這表示分配給分配對象x2的資源元素D1的得失值為「+1/(L1+L3+L4)」。得失值成為這樣的值，是因為生存區間長L3及生存區間長L4的生存區間介於分配對象x2的生存區間和分配對象x的生存區間之間，此生存區間的長度反映在得失值中的緣故。
另一方面，在本圖中，由於表示分配對象x11有豎線具有與具有生存區間L3的分配對象相併行的部分，所以，判定分配對象x11與具有生存區間L3的分配對象x5的生存區間重疊。
在此豎線的左下部附加有字符串「-1/(L1+L3)」，它表示分配給分配對象x11的資源元素D0的得失值為「-1/(L1+L3)」。得失值之所以成為這樣的值，是因為生存區間長度L3的生存區間介於分配對象x11的生存區間和分配對象x的生存區間之間，反映此生存區間的長度的緣故。
另外，在本圖中，得失值「-1/(L1+L3)」帶負號，而「+1/(L1+L2)」、「+1/(L1+L3+L4)」帶正號，其理由如下。
因為賦予得失值「+1/(L1+L2)」的資源元素D3分配給分配對象x時，分配給可以去掉傳輸命令的分配對象(分配對象x1)，賦予得失值「+1/(L1+L3+L4)」的資源元素D1分配給分配對象x時，分配給可以去掉傳輸命令的分配對象(分配對象x2)，與之相反，賦予得失值「-1/(L1+L3)」的資源元素D0分配給分配對象x時，分配給產生傳輸命令的分配對象(分配對象x11)。
另外，由於得失值的分母是以分配對象x作為基點的生存區間長度之和，所以，簡單地將生存區間長度L1作為「1」亦可。
由以上說明可知，分配給離分配對象x越近的分配對象的資源元素，得失值越大，分配給離分配對象x越遠的分配對象的資源元素，得失值越小。分配的順序巡迴過來的分配對象影響更近的已分配的資源元素。如前所述，在數據寄存器D0、D1、D2間和地址寄存器A0、A1、A2間等相同功能的資源間難於按使用成本決定優劣。與此相反，在數據寄存器D0、D1、D2中，得失值則影響先分配的那一個處理。即使在已分配的情況下，在數據寄存器D0、D1、D2中，利用哪一個最接近分配對象x來決定優劣。
另外，從已分配的分配對象方面來看，可以對本身臨近的後續分配對象發生影響。也就是說，已分配的分配對象可以將與自身相同的資源元素分配給周圍的分配對象。在本實施例中，也是按表徵嵌套級和使用頻度的分配優先級的順序將資源元素分配給分配對象的，但是，利用此優先級與得失值的組合，對嵌套級深的地點優先地分配寄存器，便可獲得將此已分配的寄存器向嵌套級淺的地點擴散的靈活的分配結果。同樣，對使用頻度高的地點優先地分配寄存器，也可獲得將已分配的寄存器向嵌套級低的地點擴散的靈活的分配結果。而且，還能實現自變量寄存器、返回值寄存器、破壞性寄存器等預先分配的對方已確定的分配對象將其資源向周圍擴散的靈活的資源分配。
以上的說明對生存區間與分配對象x連續的已分配的分配對象進行了說明，但是，如果只看到連續的情況，反而會產生損失。這就是與分配對象x重疊一側的延長線上已分配了數個資源元素時，應避免對它們進行任何分配。在不能避免時，就必須從中選擇損失最輕的進行分配。為了定量地評估這種損失，也可使用得失值。下面，參照圖22的說明圖說明為了評估損失使用得失值的情況。在圖22中，豎線表示分配對象，其中，空白的表示未分配的分配對象，畫黑斜線的表示已分配的分配對象。該生存區間的起點和終點用黑點「·」表示。圖中的黑點間用橫向虛線連接的，表示其生存區間的終點與起點相一致，這樣，便可知道利用虛線連接終起點的分配對象之間存在資源繼承關係。在表示生存區間的豎線上分別用「分配對象x2」、「分配對象x3」、「分配對象x4」字樣標上表示具有該生存區間的分配對象的名稱的字符串。
在該分配對象中，分配了資源元素在該字符串的正下方示出表示資源元素的名稱的字符串。在由這些表示資源元素名稱的字符串伸出的箭頭線的端部表示出數學式「+Px/(L2+L3)」、「-Px/(L2+L3)」，它們表示各資源元素的得失值。
在本圖中，由字符串「資源元素D1」伸出箭頭線，其箭頭端到達字符串「-Px/(L2+L3)」，這表示分配給分配對象x4的資源元素D1的帶負號的得失值，也就是說，表示損失的得失值是「-Px/(L2+L3)」。得失值之所以成為這樣的值，是因為生存區間長度L2和L3的生存區間介於分配對象x4的生存區間與和分配對象x生存區間重疊的分配對象x2的生存區間之間，這一生存區間的長度反映在得失值中。
另一方面，在本圖中，由於表示分配對象x31的豎線具有與具有生存區間長度L3的分配對象x3相併行的部分，所以，可知分配對象x31與分配對象x3的生存區間互相重疊。
此豎線的左下方標有字符串「+Px(L2+L3)」，它表示分配給分配對象x31的資源元素D2的得失值為「+Px/(L2+L3)」。得失值之所以成為這一值，是因為介於生存區間長度L2和生存區間長度L3的生存區間分配對象x31的生存區間與和分配對象x生存區間重疊的分配對象x2的生存區間之間，反映此生存區間的長度的緣故。
在本圖中，得失值「-Px(L2+L3)」帶有負號，「+Px(L2+L3)」帶有正號，其理由如下。這是因為賦予得失值「+Px/(L2+L3)」的資源元素D2分配給分配對象時，分配到可以去掉傳輸命令的分配對象(分配對象x31)賦予得失值「-Px(L2+L3)」的資源元素D2分配給分配對象x時，分配給產生傳輸命令的分配對象(分配對象x4)。另外，由於得失值的分母是以分配對象x2為基點的生存區間長度之和，所以，將生存區間長度L2簡單地作為「1」亦可。
追蹤對象所謂追蹤對象，是指為追尋資源繼承關係而計算出各資源元素的得失值的信息。由此，追蹤對象包含表示在程序中追尋當前資源繼承關係的地址的信息(它以分配對象名表示)和介於此地點的分配對象與分配對象x之間的生存區間的總和以及在當前位置上成為可以分配的資源元素的集合。由於包含這些信息，所以，在本實施例中，將追蹤對象作為結構體變量處理，將上述當前位置信息、生存區間的總和和可以分配的資源元素的集合作為其結構體的結構要素來處理(在本實施例中，追蹤對象用A表示、當前追蹤位置的分配對象用A.ASO表示、生存區間長度的總和用A.LNS表示、資源元素集合用A.RES表示)。
後續成本值後續成本值是表示通過將各資源的資源元素分配給分配對象x而使用優先級比分配對象x更低、在分配對象x之後進行分配的分配對象的中間命令的代碼大小和實行時間如何增減的值。
下面，參照圖23的說明圖說明優先次序為下位的未分配的分配對象的後續成本值成為多大的值。圖23是表示未分配的分配對象的後續成本的說明圖。
圖中所示的空白的豎線表示分配對象的生存區間，該分配對象的生存區間的起點和終點用空白圓圈表示。圖中的空白圓圈中存在用橫虛線連接的情況，它表示生存區間的終點與起點一致，這樣，便可知道用虛線連接終始點的分配對象之間存在資源繼承關係。在表示生存區間的豎線上分標用「分配對象x1」、「分配對象x2」、「分配對象x3」標以表示分配對象的名稱的字符串。另外，在分配對象x1的左邊列有中間命令群「x1＝u+v』『y＝x1+200』『r＝x1/40』『t＝30+x1』『w＝x1+3』」。這些表示在中間程序中使用分配對象x1的中間命令群。
在分配對象x2的左邊列有中間命令群「『x2＝u+v』『y＝x2+200』『r＝x2/40』『t＝30+x2』『w＝x2+3』」，它們表示在中間程序中使用分配對象x2的中間命令群。
另外，在分配對象x3的左邊列有中間命令群「『x3＝u+v』『y＝x3+200』『r＝x3/40』『t＝30+x3』『w＝x3+32』」，它們表示在中間程序中使用分配對象x3的中間命令群。
在本圖中，在字符串「分配對象1」的正下方存在字符串「DR的後續成本值」和「AR的後續成本值」，進而在它的下面還有數學式「Cost(DR)/L」和「Cost(AR)/L」，這些數學式表示將資源即數據寄存器、地址寄存器的資源元素分配給分配對象x1時分配對象x1的後續成本值。另外，從位於分配對象x1左邊的中間命令群的各中間命令「『x1＝u+v』、『y＝x1+200』、『r＝x1/40』『t＝30+x1』、『w＝x1+3』」，伸出的箭頭到達該數學式中的「Cost(DR)」「Cost(AR)」，這表示後續成本值的算式中的使用成本的總和值「Cost(DR)」、「Cost(AR)」是分配數據寄存器DR、地址寄存器AR的資源元素時分配對象x1的使用成本值的總和值。
在本圖中，在字符串「分配對象x2」正下方存在字符串「DR的後續成本」和「AR的後續成本」，在其下面還有數學式「Cost(DR)/(L1+L)」和「Cost(AR)/(L1+L)」，這些數學式表示分配對象x2的後續成本。另外，從位於分配對象x2的左側的中間命令群的各中間命令「『x2＝u+v』『y＝x3+200』『r＝x2/40』『t＝30+x2』『w＝x2+3』」伸出的箭頭到達該後續成本值的算式中的「Cost(DR)」「Cost(AR)」，這表示後續成本值的算式中的使用成本的總和值「Cost(DR)」「Cost(AR)」是在分配數據寄存器DR、地址寄存器AR的資源元素時中間命令群中的分配對象x2的使用成本值的總和值。此使用成本總和值「Cost(DR)」、「Cost(AR)」在數學式中用生存區間長度(L1+L)相除，這表示分配對象x1介於分配對象x2與分配對象x之間、其生存區間長度(L1+L)反映在後續成本值中。
在字符串「分配對象x3」的正下方存在字符串「DR的後續成本值」和「AR的後續成本值」，在其下面還有數學式「Cost(DR)/(L1+L2+L)」和「Cost(AR)/(L1+L2+L)」，這些數學式表示分配對象x3的後續成本值。另外，從位於分配對象左側的中間命令群的各中間命令「『x1＝u+v』『y＝x3+200』『r＝x3/40』『t＝30+x3』『w＝x3+32』」伸出的箭頭到達該後續成本值式中的使用成本的總和值「Cost(DR)」、「Cost(AR)」，這表示後續成本式中的「Cost(DR」、「Cost(AR)」是分配數據寄存器DR、地址寄存器AR的資源元素對中間命令群中的分配對象x3的使用成本值的總和值。此使用成本值的總和值「Cost(DR)」、「Cost(AR)」在數學式中除以生存區間長度(L1+L2+L)，這表示分配對象x1、x2介於分配對象x3與分配對象x之間，其生存區間長度的總和(L1+L2+L)反映在後續成本值中。而且，由於後續成本值的分母是以分配對象x作為基點的生存區間之和，所以，可以簡單地將生存區間長L作為「1」。
資源分配設備13的結構
圖8是資源分配設備13的結構圖。資源分配設備13由分配對象保持部21、分配對象生成部22、生存區間重複分配對象檢測部23、資源繼承分配對象檢測部24、分配優先級計算部25、分配資源元素確定部26和資源分配控制部27構成。
分配對象保持部21保存由分配對象生成部生成的分配對象和分配對象信息所組成的分配信息表，另外，還保存分配狀態表。
圖24和25是分配信息表的一個例子。圖24表示利用下面進行的分配處理分配資源元素的分配對象的分配信息。圖中的這些內容與圖33所示的中間程序例中存在的分配對象及生存區間對應。
如圖24中所示，分配信息表由以中間命令集合表示分配對象n10及該分配對象的生存區間在程序中佔多大範圍的分配對象的生存區間n11、以該集合的元素數表示的該分配對象的生存區間長度n12、表示該分配對象使用的中間命令的使用中間命令集合n13、成為該生存區間的起始點的中間命令的集合即起始點集合n14、成為該生存區間的結束點的中間命令的集合即結束點集合n15、具有與該分配對象的生存區間重複的生存區間的分配對象的集合即重複分配對象集合n16、表示與該分配對象具有資源繼承關係的分配對象的集合的資源繼承分配對象集合n17和該分配對象的分配優先級n18組成。
在本圖中，分配對象「t35」的右側的「i2～i6」表示分配對象t35的生存區間由圖33中的i2到i6的中間命令描述。
其右側的「5」表示分配對象「t35」的生存區間長度。其右側的「i1、i5、i6」表示使用分配對象「t35」的中間命令。其右側的「i1」表示分配對象「t35」的起始點集合為「i1」。其右側的「i6」表示分配對象「t35」的結束點集合為「i6」。其右側的「t34、t1、a1、p1」表示分配對象「t35」的重複分配對象集合為「t34、t1、a1、p1」。其右側的「t1、pr1」表示與分配對象「t35」具有資源繼承關係的分配對象為「Pr1」。其右側的「0.6」表示分配對象「t35」的優先級。而且，起始點即「i1」之所以不包含在生存區間n11中，是因為可以根據生存區間的集合積簡單地判定生存區間的起始點一致的分配對象間的生存區間不重疊。因此，設定在所有的分配對象的生存區間中不包含起始點。
圖25是實變量(Ar)、函數的返回值(Fr)、破壞性寄存器(Br)等已分配了資源元素的分配對象的分配信息的示例。
圖25所示分配信息表由分配對象n20、以中間命令的集合表示該分配對象的生存區間在中間程序內佔多大範圍的分配對象的生存區間n21、以該集合的元素數表示的該分配對象的生存區間長度n22、表示使用該分配對象的中間命令的使用中間命令集合n23、成為該生存區間的起始點的中間命令的集合即起始點集合n24、成為該生存區間的結束點的中間命令的集合即結束點集合n25、具有與該分配對象的生存區間相重複的生存區間的分配對象的集合即重複分配對象集合n26、表示與該分配對象具有資源繼承關係的分配對象的資源繼承關係分配對象集合n27和分配給該分配對象的分配資源元素n28組成。
圖26A是分配狀態表的示例。分配狀態表由分配對象一覽和記入分配給各分配對象的資源元素的記入欄組成，反映分配是如何進行的。此圖的內容與圖33所示的中間程序例內存在的分配對象和生存區間相對應。
在此圖記入欄內，右端付加「(a)」的表示優先級最高的分配對象「t262」在進行分配時的分配狀態。右端付加「(b)」的表示優先級為次一級的分配對象「t263」進行分配時的分配狀態。在右端附加「(c)」的是優先級再下一級分配對象「t264」進行分配時的分配狀態。
分配對象生成部22根據數據流分析結果(下面稱為數據流信息)和控制流分析結果(下面稱為控制流信息)生成分配對象。另外，這時還檢測出生存區間、使用中間命令和生存區間的起始點及結束點。如圖25所示，在進行分配處理之前，需要進行分配的分配對象在此處分配資源元素。生成的分配對象存放到分配對象保持部21中。
生存區間重複分配對象檢測部23檢驗分配對象彼此間的生存區間的重疊。亦即，尋求生存區間與任一分配對象x重疊的分配對象的集合即分配對象集合Ov(x)。Ov(x)的內容保持在分配對象保持部21中。
資源繼承分配對象檢測部24對保持在分配對象保持部21中的分配對象檢測具有資源繼承關係的全部分配對象。亦即，尋求與任意的分配對象x具有繼承關係的分配對象的集合即分配對象集合Rs(x)。Rs(x)的內容保持在分配對象保持部21中。
為了獲得Rs(x)的集合化，按如下過程進行。
由於分配對象保持部21對應地保持各分配對象、與各分配對象的生存區間的起始點相當的中間命令和與各分配對象的生存區間的結束點相當的中間命令，所以，資源繼承分配對象檢測部24從保持的分配對象中檢測全部與分配對象x的生存區間的起始點相當的中間命令與結束點相當的分配對象。並且，使檢測出的分配對象與分配對象x成為同一集合。
另外，檢測全部與分配對象x的生存區間的結束點相當的中間命令與起始點相當的全部分配對象。並且，使探測出的分配對象與分配對象x成為同一集合。反覆進行上述處理，生成各分配對象的Rs(x)。但是，顯而易見，即使將相同的資源元素分配給測得的分配對象與分配對象x，當不能省掉傳輸命令時，也不能使之成為同一集合。
分配優先級計算部25對保持在分配對象保持部21中的分配對象x計算分配優先級。所謂分配優先級，是指表示從哪一個分配對象開始進行對資源元素的分配的優先次序。這裡，使用下面的算式來進行計算分配優先級＝(存在x的使用中間命令的循環層次的總和)/(x的生存區間的長度)。
分配資源元素確定部26根據分配信息表的記載內容將資源元素分配給分配對象。
資源分配控制部27控制全部分配處理。
圖12是資源分配控制部27的流程圖。
在步驟a1，資源分配控制部27啟動分配對象生成部22。
在步驟a2，資源分配控制部27啟動生存區間重複分配對象檢測部23。
在步驟a3，資源分配控制部27啟動資源繼承分配對象檢測部24。
在步驟a4，資源分配控制部27啟動分配優先級計算部25。
在步驟a5，分配資源控制部27啟動分配資源元素確定部26。
分配資源元素確定部26構成為根據分配信息表保持的內容確定分配給各分配對象的資源元素。
圖9為圖8中的分配資源元素確定部26的結構圖。
分配資源元素確定部26由分配候補資源元素保持部31、可分配資源元素檢測部32、使用成本計算部34、使用成本保持部35、推斷增益計算部36、增益保持部37、資源元素確定控制部38、資源類別成本計算部39、資源類別成本保持部40和評價資源保持部41組成。
圖13為資源元素確定控制部38的流程圖。如圖13所示，此流程圖包括下列步驟求取可分配給分配對象x的資源元素(步b3)；當存在多個可分配資源元素時，通過計算各資源元素的使用成本來選取應分配的資源元素(步b4)；如果選取的結果只剩下一個資源元素時，就將該資源元素分配給分配對象x(步b16)；如果選取結果剩下多個資源元素時，就對它們篩選候補元素的(步b7)；通過對篩選的候補元素計算得失值對分配給分配對象x的資源元素進行再次選擇(步b8)；當再次選取的結果僅剩下單一資源的資源元素時，就將此資源元素分配給分配對象x(步b14)；當再次選取的結果還有多個資源的資源元素時，就計算各資源的後續成本值對各資源所具有的資源元素再一次進行選擇(步b12)。從而，對於未分配的分配對象，便成為按照分配優先級順序進行上述處理(步b1～b14)循環結構。
在在此流程圖中，集合R表示未分給生存區間與分配對象x重疊的分配對象的資源元素的集合。
下面，按照順序對此流程圖的各個步驟作更詳細的說明。
在步驟b1，資源元素確定控制部38當存在保持在分配對象保持部21內並且還未分配資源元素的分配對象時，就執行步驟b2，當在分配對象保持部21中不存在時，就結束分配資源元素確定部26的處理。
在步驟b2，資源元素確定控制部38從分配對象保持部21保持的未分配的分配對象中取出由分配優先級計算部25求出的分配優先級最高的分配對象x。
在步驟b3，啟動可分配資源元素檢測部32，計算可分配給分配對象x的資源元素的集合。亦即，計算未分配給生存區間與分配對象x重疊的分配對象的資源元素(稱為可分配資源元素)的集合R，並保存到分配候補資源元素保持部31中。
在步驟b4，詳細地說，就是啟動使用成本計算部34，對分配候補資源元素保持部31所保持的集合R的各資源元素，計算分配對象x的中間命令的使用成本，並將計算結果保存在使用成本保持部35中。
在步驟b5，在分配候補資源元素保持部31所保存的資源元素中，當在由步驟b5所得到的使用成本為最小的資源元素中存在多資源rh時，就執行步驟b15，否則就執行步驟b6。
在步驟b6，在分配候補資源元素保持部31所保存的資源元素中，當由步驟b4得到的使用成本為最小的資源元素r只有一個時，就執行步驟b16，否則就執行步驟b7。
在步驟b7，使分配候補資源元素保持部31暫時空出來，只將在步驟b4得到的使用成本為最小的資源元素重新保存到分配候補資源元素保持部31中。
在步驟b8，更詳細地說，就是啟動推斷增益計算部36，根據具有分配對象x的資源繼承關係的分配對象求各資源元素的增益值，並將求得的增益值保存到增益保持部37內。
在步驟b9，在分配候補資源元素保持部31中保存的資源元素中，計算在步驟b8求得的保存在增益保持部37中的增益值為最大的資源元素的集合Rs，使分配候補資源元素保持部31的內容暫時空出來保存屬於此集合Rs的資源元素。
在步驟b10，計算集合Rs內的資源元素所屬的資源的集合RES，並保存到評價資源保持部41內。
在步驟b11，當在評價資源保持部41保持的集合RES中存在多個資源時，就執行步驟b12，否則就執行步驟b14。
在步驟b12，更詳細地說，就是啟動資源類別成本計算部39，計算後續成本值，並將對各資源的計算結果保存到資源類別成本保持部40內。
在步驟b13，將屬於評價資源保持部41的是資源類別成本保持部40所存放的成本為最小的資源所具有的資源元素並且保存在分配候補資源元素保持部31中的資源元素分配給分配對象x；然後返回步驟b1。
在步驟b14，將分配候補資源元素保持部31中所保存的資源元素分配給分配對象x，然後返回步驟b1。
在步驟b15，當將多資源rh的資源元素分配給生存區間與分配對象x重疊的分配對象時，就將與其資源元素不同的多資源rh的資源元素分配給分配對象x，然後返回步驟b1。
在步驟b16，將資源元素r分配給分配對象x，然後返回步驟b1。
分配候補資源元素保持部31保持對分配對象x可分配的資源元素。分配候補資源元素保持部31的保存內容及其保持內容的變化如圖26B所示。在本圖中，標在右端的(a)、(d)、(e)、(f)…與圖26A所示的(a)、(d)、(e)、(f)…對應。從而與圖33所示的程序例內的(a)、(e)、(f)、…對應。這裡，所謂可分配資源元素就是未分配給生存區間與分配對象x重疊的分配對象的資源元素。
由圖26B的(a)、(d)的狀態可知D0、D1、D2、D3、A0、A1、A2、Mm是可分配資源元素。另外，還可知道，當從(f)的狀態變化為(f-1)的狀態時，資源元素D1則作為可分配資源元素而被除外。
可分配資源元素檢測部32在步驟b3啟動，檢測可分配的資源元素。由可分配資源元素檢測部32求得的可分配資源元素的集合存儲到分配候補資源元素保持部31內。
使用成本計算部34在步驟b4啟動，通過計算使用成本來評估在將保存在分配候補資源元素保持部31中的各資源元素分配給分配對象x時，與分配對象x使用的中間命令對應的機器語言命令佔據多大的存貯器空間或需要多少執行時間，並選擇各資源元素。另外，使用成本計算部34將作為評估結果而計算的成本值按各資源元素保存到使用成本保持部35中。
使用成本保持部35保存在步驟b4計算的使用成本計算部34的計算結果。
使用成本計算部34評估存貯器大小或執行時間與此相反，通過計算得失值將各資源元素分配給分配對象x時，推斷增益計算部36，估算能刪除多少傳輸命令，並選擇各資源元素。
增益保持部37在步驟b9保存由推斷增益計算部36計算得的得失值的累計即增益值。圖28A是增益保持部37的保持內容的示例。在本圖中，各記入欄的右端標以符號「(d)」、「(d-1)」、「(d-2)」、「(d-3)」、「(d-4)」……，它們表示推斷增益計算部36對於分配對象t265的各資源元素的增益值的保持內容的變化。
資源元素確定控制部38控制所有確定資源分配的處理。
資源類別成本計算部39在步驟b12當由推斷增益計算部36計算的增益值對多個資源為最大時，進行後續成本值的計算。
資源類別成本保持部40按每一資源保存資源類別成本計算部39的計算結果即後續成本值。
評價資源保持部41保存在步驟b12根據資源類別成本計算部39的計算判明為有效的資源。圖31c是評價資源保持部41的保存內容的示例。圖中各記入欄右端標以符號「(d)」、「(d-1)」，這些符號表示資源類別成本計算部39對於分配對象t265的評價資源保持部41的保持內容的變化。
圖9所示的使用成本計算部34構成為計算各分配對象的使用成本。圖10是使用成本計算部34的結構。
使用成本計算部34由模式保持部43、運算成本保持部44、總成本保持部46和使用成本計算控制部47組成。
圖14為使用成本計算控制部47的流程圖。
在此流程圖中，中間命令i表示分配對象使用的中間命令。資源元素r表示分配候補資源元素保持部31中保存的資源元素。成本模式p表示使用資源元素r對中間命令i生成的成本模式(關於成本模式下面說明)。
此流程圖是對分配對象x的全部使用中間命令反覆執行生成將資源元素r用於分配對象x中的使用中間命令i的算符(操作數)時的成本模式p的步驟c5、計算與生成的成本模式p匹配的成本項的步驟c6和將求得的成本項累加到總成本保持部46中的步驟c7的循環結構(步驟c4～c9)，此循環結構還是對可分配的全部資源元素反覆進行的二重循環結構(步驟c2～c10，關於成本項下面介紹)。
下面，對此流程圖的各個步驟按順序作更詳細說明。
在步驟c1，將使用成本保持部35的保持區域中與分配候補資源元素保持部31保存的資源元素對應的位置寫入零，否則就寫入「無效」。
在步驟c2，對分配候補資源元素保持部31保持的所有資源元素r反覆執行步驟c3到c10的處理。反覆處理結束後，便結束使用成本計算部34的操作。
在步驟c3，使總成本保持部46保持為零。
在步驟c4，每次取出一個使用作為輸入所賦予的分配對象x的中間命令，並對取出的中間命令反覆執行從步驟c5到步驟c9的一系列處理。
在步驟c5，將資源元素r嵌套到在中間命令i中使用分配對象x的部分，生成中間命令i的成本模式p，並保存到模式保持部43中。
在步驟c6，使成本模式p與運算成本保持部44保存的成本項進行匹配，並取出匹配的成本項e1。
在步驟c7，取出成本項e1的成本，並將取出的成本累加到總成本保持部46中。
在步驟c8，判斷在成本項e1的WORK中是否已設定資源元素，已設定時就執行步驟c9，否則就執行步驟c4。所謂WORK，就是除了對機器指令的操作數及運算結果設定的資源元素外，利用代碼生成部14變換中間命令i時所需要的資源元素。
在步驟c9，計算分配給在生存區間包含中間命令i的分配對象的資源元素的集合R1，當在集合R1中存在由成本項e1的WORK指定的資源元素r1時，就將溢出成本累加到總成本保持部46中。所謂溢出成本，是指一旦將資源元素r1的存貯值保存到堆積中，在中間命令i使用後返回時所需的成本。在溢出成本的相加運算後執行步驟c4(下面，將資源元素r1稱做中間命令i中的溢出資源元素)。
在步驟c10，將對分配對象x分配資源元素r時的使用成本作為總成本保持部46保存的值存放到使用成本保持部35中，然後執行步驟c2。
模式保持部43保存在步驟c5生成的成本模式。所謂成本模式，是指按如下所示的四個項目的組合表示使用分配對象x的中間命令，是為了更具體更精確地計算使用成本中所必須的。四個項目的組合為(OP，OPR1，OPR2，RESULT)OP—在此項目內設定「乘法」、「加法」、「代入」等中間命令的運算符的種類。
OPR1—此項目與中間命令的第一操作數(OP為二項運算時與左邊的操作數相當)對應，描述此第一操作數是如何設定的。
如果第一操作數設定的即時值，就設定表示即時值的「IM」。如果第一操作數的分配對象已分配，就設定該資源元素。當操作數不是即時值並且未分配資源元素時，就設定表示未分配的「未」。另外，在此第一操作數的項目內還附加有表示此中間命令是否相當於結束點的「K」或「N」的特徵。
OPR2—在此項目內設定與中間命令的第二操作數相當(為二項運算時與右邊的操作數相當)的和OPR1相同的值。
RESULT—在此項目內設定表示用於保存運算結果的資源元素與分配給哪個分配對象的資源元素相同的信息。
當與左邊分配的資源元素相同時，就在RESULT內設定為「左同」、與右邊相同時，就設定為「右同」，當左右兩邊均不同時，就設定為「異」。另外，在結果中未分配資源元素時，就設定為「未」。但是，在進行代入運算和比較運算時，此項目就是未設定。
(下面稱此四組模式為成本模式)例如，在圖33的程序例中的中間命令i3「t1＝t34+3」中，分配對象t34分配給D0、而分配對象t1未分配時，就將運算類型的項目設定為「加法」。另外，由於中間命令i3為分配對象t34的結束中間命令，而分配對象t34分配給分配對象D0，所以，OPR1設定為「D0.K」。由於第二操作數是即時值「3」，所以，OPR2設定為「IM」。由於運算結果的t1是未分配，所以，RESULT的項目設定為「未」。
因此，中間命令i3「t1＝t43+3」的成本模式為(加法，D0.K，IM，未)。
運算成本保持部44保存以所有成本模式和與該成本模式對應的成本為欄目的運算成本表，是更具體、更精確地進行使用成本計算所必須的。
圖27A是運算成本表的示例。成本模式由前面所說的四個項目OP，OPR1，OPR2，RESULT、表示除在該項目的組合中分配給操作數和結果的資源元素之外所需的資源元素的WORK和表示該組合的成本值的COST組成(下面構成本表的元素稱為成本項)。
例如，在圖27中，Dn，Dm表示資源DR的資源元素中不論D0～D3中的哪一個都匹配。另外，An、Am表示資源AR的資源元素中不論A0～A2中的哪一個都匹配。IM表示與即時值匹配。Dn與An由「1」分開，這表示不論資源DR或資源AD的哪一個資源元素都匹配。如圖27A(a)的成本項那樣，沒有「K」、「N」特徵的表示不管成本模式中是否標有「K」、「N」特徵都與其匹配。前述的「t1＝t34+3」的成本模式(加法D0.K，IM，未)與圖27A(b)的成本項匹配。因此，該成本模式的成本為3。
這樣，匹配的成本便在總成本保持部46中累加求總和。
使用成本計算控制部47輸入分配對象x，為了計算將分配候補資源元素保持部31保存的各資源元素分配給分配對象x時的使用成本，按照圖14所示的流程圖進行控制。
推斷增益計算部36構成為通過計算增益值來估算傳輸命令的削減情況。圖11A為推斷增益計算部36的結構圖。
推斷增益計算部36由增益推斷控制部5-1、追蹤對象保持部52、已處理的分配對象保持部53、已損失的分配對象保持部54、重複分配對象保持部55和得失保持部56組成。
增益推斷控制部51進行用於計算分配對象x的增益值的處理控制。
圖15及圖16是增益推斷控制部15的處理內容的流程圖。圖15是增益推斷控制部51的處理控制的主流程，圖16為得失計算處理的流程圖(由此流程圖表示的得失值計算處理稱為得失計算子程序)。
圖15的流程圖具有根據分配對象x生成用於追尋資源繼承關係的追蹤對象的步驟d3、利用追蹤對象順序追尋資源繼承關係並在計算出各資源元素的得失值後進行資源元素的第一階段的再次選擇的步驟d4和當第一階段的再次選擇的結果增益值為最大的資源元素是多個時追尋生存區間與分配對象x重疊並且未分配的分配對象的資源繼承關係並在計算各資源元素的得失值後進行資源元素的第二階段的再次選擇的步驟d12～d17。
本流程圖的第二階段的再次選擇的部分由對分配對象y(生存區間與分配對象x重疊的並且未分配的分配對象)生成追蹤對象的步驟d15、對該追蹤對象計算得失值的步驟d16和從資源元素的增益值中減去將計算的得失值乘以分配對象y的優先級所得值的步驟d17構成對全部分配對象y反覆進行的循環結構(步驟d12～d17)。
下面，對本流程圖的各個步驟按順序作更詳細說明。
在圖15中步驟d1，增益推斷控制部51將與增益保持部37和得失保持部56的各資源元素對應的內容置為零。
在步驟d2，清除追蹤對象保持部52、處理畢分配對象保持部53、已損失分配對象保持部54。
在步驟d3，對分配對象x生成追蹤對象A(x)，將A(x)的各欄位項設定為追蹤對象A(x)的分配對象＝A(X).ASO＝X
追蹤對象A(x)的生存區間長度之和＝A(x).LNS＝1追蹤對象A(x)的資源元素集合＝A(x).RES＝分配候補資源元素保持部31所保存的資源元素的集合併將生成的追蹤對象A(x)存貯到追蹤對象保持部52內。
在步驟d4，調出後而所述的得失計算子程序進行得失計算，並將各資源元素的計算結果保存在得失保持部56中。
在步驟d5，將按各資源元素保存在得失保持部56中的值存入增益保持部37。
在步驟d6，計算分配候補資源元素保持部31存放的資源元素並且存放於增益保持部37中的值為最大的資源元素的集合RS。
在步驟d7，當集合RS的元素數為多個時就執行步驟d8。否則就結束推斷增益計算部36的處理。
在步驟d8，當存在生存區間與分配對象x重疊並且未分配的分配對象時，就執行步驟d9。否則就結束推斷增益計算部36的處理。
在步驟d9，暫時清除分配候補資源元素保持部31，並重新全部存放集合RS的資源元素。
在步驟d10，將與增益保持部37的各資源元素對應的內容置為零，並清除追蹤對象保持部52。
在步驟d11，只將生存區間與分配對象x重疊並且未分配的分配對象存入重複分配對象保持部55。
在步驟d12，反覆執行步驟d13～d17直至將重複分配對象保持部55清除為止。
在步驟d13，從重複分配對象保持部55取出一個分配對象y，並從重複分配對象保持部55中將其去除。
在步驟d14，將與得失保持部56各資源元素相對應的內容置為零，並清除處理畢分配對象保持部53和已損失分配對象保持部54。
在步驟d15，對分配對象y生成追蹤對象B(y)，將B(y)的各項設定為追蹤對象B(y)的分配對象＝B(y).ASO＝y追蹤對象B(y)的生存區間長之和＝B(y).LNS＝1追蹤對象B(y)的資源元素集合＝B(y).RES＝分配候補資源元素保持部31中保存的資源元素的集合。
並將生成的追蹤對象B(y)存入追蹤對象保持部52。
在步驟d16，調出後而所述的得失計算子程序進行得失計算，並將各資源元素的計算結果存入得失保持部56。
在步驟d17，將分配給按各資源元素保持在得失保持部56中的值乘以分配對象y的分配優先級的值，從增益保持部37中減去，然後返回步驟d12。
如上所述，增益推斷控制部51根據與分配對象x具有資源繼承關係的分配對象計算出增益值(步驟d1～d5)，當計算的增益值為最大的資源元素有多個時，還要考慮其中分配給生存區間重疊的其他分配對象y有可能削減傳輸命令的情況，然後才計算最後的增益值(步驟d9～d17)。
特別是對生存區間與分配對象x重疊的分配對象y計算的得失值，表示如果分配給分配對象y時是有多大益處的資源元素。益處越大的資源元素分配給分配對象x時表示傳輸命令越增加。而且由於在分配對象y中分配優先級小的分配給寄存器等個數有限的資源元素的可能性也很小，所以，必須將其效果評估得較小。因此，在步驟d17中將對分配對象y計算的得失值乘以分配對象y的分配優先級的值從增益保持部37中減除。得失計算程序的詳細流程
得失計算子程序是從圖15的步驟d4及步驟d16調出的一個子程序，在圖15的流程步驟d3及步驟d15對追蹤對象保持部52存放的所有追蹤對象反覆執行圖16的處理。
在得失計算子程序中，有判斷在連續生存群(生存區間相互連接的一系列分配對象的集合)中資源元素是否已分配給當前正在尋求資源繼承關係的位置的分配對象A.ASO的步驟e3，並按照此步驟e3的判斷結果切換是執行步驟e4還是執行步驟e5～e10。
在步驟e4，當判定已分配時就假定已追尋到已分配的分配對象，並計算其資源元素的得失值，資源元素的增益值只增加該得失值。與此相反，在步驟e3，當未分配時，就在步驟e5～e10將搜索範圍向生存區間與分配對象A.ASO重疊的一側擴展。具體說，就是具有計算分配對象A.ASO的損失因素(成為增益值減少的因素的分配對象)的步驟e5～e8、計算分配給成為損失因素的分配對象的資源元素的得失值並將該資源元素的增益值只減少此得失值的步驟e9和在減少之後對與分配對象A.ASO具有資源繼承關係的分配對象重新生成追蹤對象的步驟10，反覆執行步驟e2～e10直至保存追蹤對象的追蹤對象保持部52中不存在追蹤對象為止，從而構成順序追蹤具有資源繼承關係的分配對象的循環結構。
下面，對此流程圖中的各個步驟按順序更詳細地說明。
在步驟e1，反覆執行步驟e2至步驟e10直到追蹤對象保持部52空了為止。如果空了就結束得失計算子程序的處理。
在步驟e2，從追蹤對象保持部52中取出一個追蹤對象A，從追蹤對象保持部52中除去，並將追蹤對象A的分配對象項目即分配對象A.ASO存入已處理分配對象保持部53中。
在步驟e3，判斷資源元素r是否已分配給分配對象A.ASO，已分配時就執行步驟e4，否則就執行步驟e5。
在步驟e4，資源元素r屬於追蹤對象A的資源元素集合的項目即A.RES時計算得失值＝1/追蹤對象A的生存區間長度之和A.LNS，並將此值與得失保持部56的資源元素r的內容相加。然後，返回步驟e1。
在步驟e5，計算生存區間與分配對象A.ASO重疊的並且已分配資源元素的分配對象的集合OSI。
在步驟e6，計算已分配給屬於集合OSI的分配對象的資源元素的集合RSI。
在步驟e7，計算屬於集合OS1並且未存入已損失分配對象保持部54的分配對象x的集合OS2，並將集合OS2的元素存入已損失分配對象保持部54。
在步驟e8，計算已分配給屬於集合OS2的分配對象的資源元素的集合RS2。
在步驟e9，計算得失值＝1/追蹤對象A的生存區間長度之和A.LNS，並從屬於得失保持部56內的集合RS2的資源元素的內容減去求得的得失值。
在步驟e10，對全部與分配對象A.ASO具有資源繼承關係的分配對象，並且未存放在已處理的分配對象保持部53中的分配對象y按每一個y生成追蹤對象B(y)，將B(y)的各項設定為追蹤對象B(y)的分配對象＝B(y).ASO＝y追蹤對象B(y)的生存區間長度之和＝B(y).LNS＝生存區間長之和A.LNS+分配對象A.A.SO的生存區間長追蹤對象B(y)的資源元素集合＝B(y).RES＝資源元素集合A.RES-集合RS1，並將生成的追蹤對象B(y)存入追蹤對象保持部52，在執行步驟e10之後返回步驟e1。
如上所述，得失計算子程序通過利用步驟e10將具有資源繼承關係的分配對象重新追加到追蹤對象保持部52內，便可追循資源繼承關係。由於利用該設定可以增加追蹤對象，所以，還擴大了得失值計算的搜索範圍。
追蹤對象保持部52保存在步驟d3、d15、e10作為得失計算子程序的處理對象而生成的多個追蹤對象。圖28C是追蹤對象保持部52保存的內容示例。圖中各記入欄標有符號「(d)」、「(d-1)」、「(d-2)」、「(d-3)」、「(d-4)」……，它們表示與分配對象t265對應的由推斷增益計算部36的追蹤對象保持部52的保存內容的變化。標有這些符號「(d)」、「(d-1)」、「(d-2)」、「(d-3)」、「(d-4)」……的追蹤對象的分配對象表示計算分配對象t265的得失值對尋求資源繼承關係的分配對象。尋求這種資源繼承關係的分配對象與分配對象t265的生存區間具有怎樣的位置關係如圖34所示。圖中用粗黑豎線表示成為得失值計算對象的分配對象t265，在進行該得失計算時尋求資源繼承關係的分配對象空白豎線表示。
在圖28C記入欄內，右端標有「(d-1)」的表示已生成將分配對象t265作為結構體的結構部件的追蹤對象。同樣，右端標有「(d-4)」的表示已生成將具有與分配對象t265的生存區間重疊的生存區間的分配對象p1作為結構體的結構部件的追蹤對象。同樣，右端標有「(d-6)」的表示已生成將具有與分配對象t265的生存區間重疊的生存區間的分配對象a3作為結構體的結構部件的追蹤對象。
另外，右端標有「(d-8)」的表示已生成將與具有與分配對象t265的生存區間重疊的生存區間的分配對象a3存在資源繼承關係的分配對象t263、t264、x2、x3作為結構體的結構部件的追蹤對象。
利用圖28C中的「(d-4)」，將生存區間相互重疊的分配對象p1選擇為對分配對象t265的追蹤對象。利用圖28C中的「(d-6)」將生存區間相互重疊的分配對象a3選擇為對分配對象t265的追蹤對象。利用圖28C中的「(d-8)」將與分配對象a3具有資源繼承關係的分配對象t263、t264、x2、x3選擇為對分配對象t265的追蹤對象。
這樣，參照圖28C可知，為了計算分配對象t265的得失值，將搜索範圍擴展到了分配對象t263、t264、x2、x3。
已處理的分配對象保持部53保存在步驟e2結束得失計算子程序的處理的追蹤對象的分配對象。特別是已處理分配對象保持部53的作用是直接或間接地循環資源繼承關係時，是為了防止得失計算子程序的處理發生無限反覆的情況。
圖29A是已處理分配對象保持部53的保存內容的示例。圖中，各記入欄標有符號「(d)」、「(d-1)」、「(d-2)」、「(d-3)」、「(d-4)」……，這表示與分配對象t265對應的推斷增益計算部36的已處理分配對象保持部53的保持內容的變化。在本圖的記入欄內，右端標有「(d-1)」的表示分配對象t265已成為已處理的分配對象。由此可知，隨著按「(d-1)」、「(d-2)」、「(d-3)」、「(d-4)」……的順序進入下一欄，預先將具有與分配對象t265的生存區間重疊的生存區間的分配對象P1、具有與分配對象t265的生存區間重疊的生存區間的分配對象a3及與分配對象a3存在資源繼承關係的分配對象t263、t264、x2、x3作為結構部件的追蹤對象追加到已處理分配對象保持部53內。
由於已損失分配對象保持部54在得失計算子程序的過程中對同一分配對象不進行二次以上的減除得失值的處理。所以，在步驟e7作為損失因素暫時保存選擇的分配對象。這樣，設置已損失分配對象保持部54就是為了要避免過度地估量損失因素。例如，首先在步驟d3將保持圖21的分配對象x的追蹤對象存入追蹤對象保持部52中。然後，將得失計算子程序調出，在步驟e10將保持分配對象x3、x4、x5的追蹤對象存入追蹤對象保持部52。此時如果不經過步驟e7、e8，而在步驟e9使用集合RS1代替集合RS2時，在步驟e9處理保持分配對象x4、x5的追蹤對象時，生存區間與分配對象x4、x5重疊的分配對象x11分配的資源元素D0的得失值便減除二次。此後，保持分配對象x6的追蹤對象在步驟e9進行處理時同樣也減除分配對象x11分配的資源元素D0的得失值，從而有可能將資源元素D0的得失值計算得極小。為了防止出現這種情況，在步驟e7僅將已損失分配對象保持部54中未存放的分配對象作為得失值計算的對象。
圖29B是已損失分配對象保持部54的保持內容的示例。圖中，各記入欄標有符號「(d)」、「(d-1)」、「(d-2)」、「(d-3)」、「(d-4)」……，它表示與對對象t265對應的推斷增益計算部36的已損失分配對象保持部54的保持內容的變化。在該圖記入欄內，右端標有「(d)」、「(d-1)」、「(d-2)」的表示在對分配對象t265的推斷增益計算的初期階段已成為損失因素的分配對象。由此可知，對在「(d-3)」欄中具有與分配對象t265的生存區間重疊的生存區間的分配對象p1調出得失計算子程序，預先將與分配對象p1生存區間重疊的分配對象Ar11、Fr1、Ar12等追加到已損失分配對象保持部54中。
重複分配對象保持部55保持生存區間與分配對象x重疊並未分配資源元素的分配對象。圖29C是重複對象保持部55的保持內容的示例。圖中各記入欄內，右端標有符號「(d)」、「(d-1)」、「(d-2)」，它表示與分配對象t265對應的推斷增益計算部36的重複分配對象保持部55的保持內容的變化。特別是右端標有「(d)」的表示具有與分配對象t265的生存區間重疊的生存區間的分配對象p1、分配對象a3已存入重複分配對象保持部55。
得失保持部56按每一資源元素保持在步驟d4、d16通過執行得失計算子程序計算的得失值。圖28B是得失保持部56的保持內容的示例。圖中各記入欄內，右端標有符號「(d)」、「(d-1)」、「(d-2)」、「(d-3)」、「(d-4)」……，這表示與分配對象t265對應的推斷增益計算部36的得失保持部56的保持內容的變化。
圖11B中所示的資源類別成本計算部39構成為對分配順序在後的分配對象分配更合適的資源元素。
資源類別成本計算部39由資源類別成本計算控制部501、成本模式保持部502、資源運算成本保持部503、追蹤對象保持部504、資源類別總成本保持部505、處理畢分配對象保持部506、和重複分配對象保持部507組成。
資源類別成本計算控制部501進行用於計算分配對象x的資源類別的使用成本的處理進行控制。
圖17和圖18是資源類別成本計算控制部501的處理內容的流程圖。圖17是表示資源類別成本計算控制部的處理控制的主流程，圖18為後續成本值計算處理的主流程(將利用此流程圖表示的後續成本值計算處理稱為後續成本值計算子程序)。
圖17的流程圖具有，生成用於從分配對象x追循資源繼承關係的追蹤對象的步驟f3、按照追蹤對象順序追尋資源繼承關係及計算出各資源的後續成本值後進行資源的第一階段又一次選擇的步驟f4、當第一階段的又一次選擇的結果即後續成本值為最小的資源有多個時追尋生存區間與分配對象x重疊並且未分配的分配對象的資源繼承關係以及在計算出各資源的後續成本值後進行資源元素的第二階段的又一次選擇的步驟f15。
此流程圖的第二階段的又一次選擇的部分，具有對分配對象y(生存區間與分配對象x重疊並且未分配的分配對象)生成追蹤對象的步驟f14、對該追蹤對象計算後續成本值的步驟f15和將計算的後續成本值乘以分配對象y的優先級的乘積值從資源的後續成本值中減去的步驟f16，從而構成的對所有的分配對象y反覆進行循環結構(步驟f11～f16)。
下面，按照順序對此流程圖的各個步驟作更詳細說明。
在步驟f1，將與資源類別成本保持部40和資源類別總成本保持部505的各資源對應的內容置為零。
在步驟f2，清除追蹤對象保持部504、處理畢分配對象保持部506。
在步驟f3，對分配對象x生成追蹤對象rA(x)，將rA(x)的各項目設定為追蹤對象rA(x)的分配對象 ＝rA(x).ASO＝x追蹤對象rA(x)的生成區間長之和＝rA(x).LNS＝1，並將生成的追蹤對象rA(x)存入追蹤對象保持部504。
在步驟f4，調出後面所述的後續成本值計算子程序，進行成本計算，並將各資源的計算結果存入資源類別總成本保持部505。
在步驟f5，將按各資源存放在資源類別總成本保持部505中的值存進資源類別成本保持部40。
在步驟f6，計算資源類別成本保持部40中存放的值為最小的資源的集合R，將評價資源保持部41清除存進屬於集合R的資源。
在步驟f7，當集合R的元素數為多個時就執行步驟f8。否則就結束資源類別成本計算部39的處理。
在步驟f8，當存在生存區間與分配對象x重疊並且未分配的分配對象時，就執行步驟f9。否則就結束資源類別成本計算部39的處理。
在步驟f9，將與資源類別成本保持部40的各資源對應的內容置為零，清除追蹤對象保持部504。
在步驟f10，只將生存區間與分配對象x重疊並且未分配的分配對象存入重複分配對象保持部507。
在步驟f11，反覆執行步驟f12至步驟f16的處理直至將重複分配對象保持部507清除為止。清除後就結束資源類別成本計算部39的處理。
在步驟f12，從重複分配對象保持部507取出一個分配對象y，並從重複分配對象保持部507中除去。
在步驟f13，將與資源類別總成本保持部505的各資源對應的內容置為零，並清除處理畢分配對象保持部506。
在步驟f14，對分配對象y生成追蹤對象rB(y)，將rB(y)的各項目設定為追蹤對象rB(y)的分配對象 ＝rB(y).ASO＝y追蹤對象rB(y)的生存區間長之和＝rB(y).LNS＝1，並將生成的追蹤對象rB(y)存入追蹤對象保持部504。
在步驟f15，調出後面所述的後續成本值計算子程序，進行成本計算，並將各個資源的計算結果存入資源類別總成本保持部505。
在步驟f16，對評價資源保持部41存放的各資源，將控制資源類別總成本保持部505存放的值乘以分配對象y的分配優先級的乘積值從資源類別成本保持部40中減去，然後返回步驟f11。
如上所述，資源類別成本計算控制部501根據與分配對象x具有資源繼承關係的分配對象計算出使用成本值(步驟f1～步驟f5)，當計算的成本值為最小的資源有多個時，通過對其中生存區間重疊的其他分配對象y進行成本計算，計算還考慮了分配對象y的分配對象x的成本(步驟f9～步驟f16)，特別是，在步驟f15求出的使用成本大的資源對於生存區間與分配對象x重疊的分配對象y來說是需要使用成本的資源並在分配對象x中除了包含該資源還存在其他可分配的資源時，如果將該資源分配給分配對象x，則將不需要成本的資源分配給分配對象y的可能性就增大了。因此，在步驟f16中將求得的成本從資源類別成本保持部40中減去。另外，在步驟f16中將求得的成本乘以分配對象y的優先級，是因為在分配對象y中優先級低的分配給寄存器等的個數有限的資源的可能也小，所以，將其效果估算得小。
圖18為後續成本值計算子程序的流程圖。後續成本值計算子程序具有對分配對象rA.ASO中的使用中間命令生成成本模式的步驟g5、與成本項進行匹配並取出成本項e1的成本c的步驟g6、根據該成本c和追蹤對象rA的生存區間長度之和rA.LNS計算出後續成本值＝成本c/rA.LNS的步驟g7和將計算的後續成本值加到資源r的後續成本值的步驟g8，從而構成對分配對象rA.ASO中所含的全部使用中間命令反覆進行的循環結構(步驟g4～g8)。
這一循環結構還構成為對資源元素又一次進行選擇後剩餘的資源反覆進行的二重循環結構(步驟g3)。
另外，該二重循環結構每當從追蹤對象保持部504取出的追蹤對象rA時進行起動，在追蹤對象保持部504中每執行一次二重循環結構時便構成重新存入與追循當前資源繼承關係的地點的分配對象rA.ASO存在資源繼承關係的分配對象(步驟g9)。因此，該二重循環結構便構成為直到連續地反覆進行到處理完具有資源繼承關係的全部分配對象為止的三重循環結構(步驟g1)。
下面，按順序對本流程圖的各個步驟作更詳細地說明。
在步驟g1，反覆執行步驟g2至步驟g9的處理直到將追蹤對象保持部504清除為止。清除之後就結束後續成本值計算子程序的處理。
在步驟g2，從追蹤對象保持部504取出一個追蹤對象rA，從追蹤對象保持部504中消除。並將追蹤對象rA的分配對象項目即分配對象rA.ASO存入處理畢分配對象保持部506。
在步驟g3，對保持在評價資源保持部41中的資源並且可分配給追蹤對象rA的分配對象項目即分配對象rA.ASO的資源r一個一個地反覆執行步驟g4～步驟g8的一連串的處理。在結束該反覆處理之後就執行步驟g9。這裡，所謂可分配給分配對象rA.ASO的資源是指未分配給生存區間與分配對象rA.ASO重疊的分配對象的資源元素所屬的資源。亦即，生存區間與分配對象rA.ASO重疊的分配對象中的資源具有的資源元素已全部配完時該資源就成為不可分配的。
在步驟g4，逐次取出一個使用分配對象rA.ASO的中間命令，對取出的中間命令i反覆執行步驟g5～步驟g8的一連串處理。當反覆處理結束後，返回步驟g3。
在步驟g5，將資源r分配給在中間命令i中使用分配對象rA.ASO的部分，生成中間命令i的成本模式p，並保存到成本模式保持部502中。
在步驟g6，使成本模式保持部502中保存的成本模式p與資源運算成本保持部503中保持的成本項間進行匹配，並取出匹配的成本項e1。
在步驟g7，取出成本項e1的成本c，並根據該成本c和追蹤對象rA的生存區間長度之和rA.LNS計算後續成本值＝成本c/rA.LNS。
在步驟g8，將在步驟g7求得的後續成本值加進資源類別總成本保持部505的資源r的內容中。接著，返回步驟g4。
在步驟g9，對與分配對象rA.ASO存在資源繼承關係的未分配的分配對象並且未存進已處理分配對象保持部506內的所有分配對象y生成各個分配對象的追蹤對象rB(y)，將rB(y)的各項目設定為追蹤對象rB(y)的分配對象＝rB(y).ASO＝y追蹤對象rB(y)的生存區間長度之和＝rB(y).LNS＝生存區間長度之和rA.LNS+分配對象rA.ASO的生存區間長，並將生成的追蹤對象rB(y)存入追蹤對象保持部504，然後返回步驟g1。
成本模式保持部502保存為了計算後續成本值而在圖18的步驟g5中生成的成本模式。由於此成本模式是由與模式保持部43所保持的相同的項目構成的，所以，省略其說明。圖31B是資源成本模式保持部502的保持內容的示例。圖中各記入欄內，右端標有符號「(d)」，它表示與分配對象t265對應的資源類別成本計算部39的資源成本模式保持部502的變化。
資源運算成本保持部503為了用於後續成本值計算而保存以全部成本模式和與該成本模式對應的成本為欄目的運算成本表。
資源運算成本保持部503保持的運算成本表由圖27A中的OP、OPR1、OPR2、RESULT構成的四個項目和表示該項目的組合的成本值的成本組成。
追蹤對象保持部504保存成為後續成本值計算子程序的處理對象的多個追蹤對象。追蹤對象保持部504保持的追蹤對象與在推斷增益計算部36中使用的追蹤對象保持部52保持的追蹤對象不同，從組成部件中省去了可分配的資源元素的集合。因此，追蹤對象保持部504保持的追蹤對象由分配對象與生成區間長度之和的二個項目的數據構成。在本實施例中，為了與追蹤對象保持部52中保持的追蹤對象相區別，在追蹤對象中，用ASO表示追循當前資源繼承關係的地點的分配對象，用LNS表示到其為止的生存區間長度之和，在引用它們時，在前面附加上「r」進行表示，如分配對象rA.ASO和生存區間長度之和rA.LNS那樣。
資源類別總成本保持部505保存在後續成本值計算子程序中計算的成本。
已處理分配對象保持部506與推斷增益計算部36的已處理分配對象保持部53一樣，保存完成後續成本值計算子程序的處理的分配對象。與處理畢分配對象保持部53一樣，已處理分配對象保持部506的作用也是當資源繼承關係直接或間接地循環時用預防止後續成本值計算子程序的處理發生無限反覆的情況。圖31A是已處理分配對象保持部506的保持內容示例。圖中各記入欄內，右端標有符號「(d)」、「(d-1)」、「(d-2)」、「(d-3)」、「(d-4)」……，這表示與分配對象t265對應的資源類別成本計算部39的處理畢分配對象保持部506的變化。圖中記入欄內，右端標以「(d-1)」的是表示資源類別成本計算部39對分配對象t265處理完的最初時刻的分配對象。由此可知，隨著按照「(d-1)」、「(d-2)」、「(d-3)」、「(d-4)」……順序進入下一欄，預先將具有與分配對象t265的生存區間重疊的生存區間的分配對象a3以及和分配對象a3存在資源繼承關係的分配對象x2、x3作為組成部件的追蹤對象被追加到處理畢分配對象保持部506內。
重複分配對象保持部507保存生存區間與分配對象x重疊並且未分配資源元素的分配對象。圖31D是重複分配對象保持部507的保持內容的示例。圖中各記入欄內，右端標有符號「(d)」、「(d-1)」、「(d-2)」……，它們表示與分配對象t265對應的資源類別成本計算部39的重複分配對象保持部507的變化。右端標以「(d)」的表示重複分配對象保持部507已存進具有與分配對象t265的生存區間重疊的生存區間的分配對象p1和分配對象a3。
下面，再次參照前所示的流程圖說明上述那樣構成的本實施例的資源分配裝置的具體處理內容。
首先，作為前提，設這裡進行處理的資源為地址寄存器(AR)、數據寄存器(DR)，設多資源為存貯器(Mm)。另外，設資源AR的資源元素為A0、A1、A2，資源DR的資源元素為D0、D1、D2，多資源Mm也作為資源元素。
另外，作為資源類別的功能限制資源AR具有間接引用存貯器的功能，但是，資源DR不具有。資源DR可以成為乘除法運算的運算符，資源AR則不能。另外，在函數的自變量傳送使用的自變量寄存器和函數調用中，設破壞性寄存器為D0、D1、A0，函數的返回值使用的返回值寄存器為D0、A0，並按照返回值的數據類進行D0、A0的區別使用。
對圖32中的c語言編寫的程序利用現有語法分析裝置11和優化裝置12輸出圖33(1)所示的3地址式中間程序。利用優化裝置12從中間程序中抽出基本程序塊，得到控制流信息和數據流信息。在圖33(1)中，特別以箭頭↑表示間接引用運算，圖中的變量Ar1、Ar2、Fr分別表示保存函數的實自變量和函數的返回值的變量。
在這種狀態下，將處理轉移到資源分配設備13中。資源分配控制部27起動分配對象生成部22。分配對象生成部22根據控制流信息和數據流信息生成與變量對應的分配對象(步驟a1)。結果，便得到從圖24的n10到n15的信息。圖24表示利用下面進行的分配處理分配資源元素，圖25示出表示實自變量(Ar)、函數的返回值(Fr)、破壞性寄存器(Br)的分配對象。圖33(2)用實線表示生存區間的狀態。在圖33(2)和圖24中，如變量t26那樣生存區間存在多個的變量分別成為不同的分配對象，所以，區分為t261、t262。
圖24所示的分配對象的信息保存在圖8中的分配對象保持部21中。
接著，資源分配控制部27起動生存區間重複分配對象檢測部23。生存區間重複分配對象檢測部23對分配對象保持部21保存的各個分配對象求生存區間重疊的分配對象(步驟a2)。結果，得到圖24的n16的信息。
然後，資源分配控制部27起動資源繼承分配對象檢測部24。資源繼承分配對象檢測部24對分配對象保持部21中所保存的各個分配對象求存在資源繼承關係的分配對象(步驟a3)。結果，得到圖24的n17的信息。
而後，資源分配控制部27起動分配優先級計算部25。分配優先級計算部25對各分配對象的按下式計算分配優先級(步驟a4)分配優先級＝使用率＝使用中間命令存在的循環層次總和/生存區間的長。
再後，資源分配控制部27起動分配資源元素決定部26。分配資源元素決定部26從分配優先級高的分配對象開始順序將資源元素分配給分配對象(步驟a5)。
下面，參照圖13所示的資源元素決定控制部38的流程圖說明分配資源元素決定部26的處理。
首先，資源元素決定控制部38判斷是否存在未分配的分配對象，從未分配的分配對象中取出分配優先級最高的分配對象t262(步驟b1、b2)。
接著，資源元素決定控制部38起動可分配資源元素檢測部32(步驟b3)。可分配資源元素檢測部32將未分配給生存區間重疊的分配對象的資源元素即D0、D1、D2、D3、A1、A2和多資源元素的Mm保存到分配候補資源元素保持部31中(圖26B的(a))。然後，資源元素決定控制部38起動使用成本計算部34(步驟b4)。
使用成本計算部34對各資源元素求在分配對象t262的使用地點使用保存在分配候補資源元素保持部31中的資源元素時的使用成本。
下面，參照圖14所示的使用成本計算控制部的流程圖說明使用成本計算部34的處理內容。
首先，使用成本計算控制部47將使用成本保持部35的各資源元素的內容置為零(步驟c1)。
接著，使用成本計算控制部47取出分配候補資源元素保持部31存放的尚未計算使用成本的資源元素D0(步驟c2)。
然後，使用成本計算控制部47將總成本保持部46清零(步驟c3)。
再後，使用成本計算控制部47在分配對象t262的使用中間命令中取出對D0進行使用成本計算的中間命令i10(步驟c4)。
使用成本計算控制部47對使用中間命令i10生成成本模式(代入，D0.N，D0.K，-)，並保存在模式保持部43中(步驟c5)。
接著，使用成本計算控制部47將運算成本保持部44中保持的圖27A中的運算成本表與模式保持部43中保持的成本模式進行匹配。此時與圖27A(C)的成本項的匹配成立，得到成本0並將所得到的成本加到總成本保持部46中所保持的值上(步驟c6、c7)。
然後，使用成本計算控制部47判定匹配的成本項的WORK項目還沒有設定，並執行步驟c4。
使用成本計算控制部47取出對分配對象t262的D0尚未計算使用成本的中間命令i11，生成成本模式(加法，D0，K，Im，未)，並保存進保持部43。使之與圖27A的運算成本表的(b)成本項匹配成立，得到成本並加到總成本保持部46中。接著，判定匹配的成本項的WORK項目還未設定。並執行步驟c4(步驟c4～c8)。
隨後，使用成本計算控制部47對資源元素D0檢測不存在尚未計算使用成本的分配對象t262的中間命令的資源元素，將總成本保持部46中保存的值作為將D0分配給t262時的使用成本保存為使用成本保持部35的D0的內容(步驟c4、c10)。
使用成本計算控制部47從分配候補資源元素保持部31中取出尚未計算使用成本的資源元素D1，與資源元素D0時一樣，對分配對象t262的中間命令i10、i11分別生成成本模式(代入，D1.N，D0.K，-)(加法，D1.K，Im，未)，使之與運算成本表匹配，與圖27A(d)、(b)的成本項匹配後，分別得到成本1、2。並且，在總成本保持部46中得到其總和後，保存進使用成本保持部35的D1欄中(步驟c2～c8)。
接著，使用成本計算控制部47對資源元素D2、D3、A0、A1、A2也與資源元素D1一樣進行計算，得到使用成本值的結果。
然後，使用成本計算控制部47從分配候補資源元素保持部31中取出尚未計算使用成本的資源元素Mm，分別對分配對象t265的中間命令i10、i11生成成本模式(代入，Mm.N，D0.K，-)，(加法，Mm.K，Im，未)，使之與運算成本表匹配，與圖27A的(e)、(f)的成本項匹配後，分別得到成本2、3。並且，在總成本保持部46得到其總和5後，保存進使用成本保持部35的Mm欄內(步驟c2～c7)。另外，圖27A(f)的成本項的WORK項目雖然已指定，但是，由於不存在中間命令i11的溢出資源元素，所以，總成本保持部46中不計算入溢出成本(步驟c8、c9)。
再後，使用成本計算控制部47判定不存在存放在分配候補資源元素保持部31中的尚未求使用成本的資源元素(步驟c2)，結束使用成本計算部34的處理，並返回步驟b4。這一時刻的使用成本保持部35的內容，可以如圖27B的(a)那樣得到。
資源元素決定控制部38參照使用成本保持部35判定多資源即Mm的成本並非最小後(步驟b5)，就執行步驟b6。
然後，資源元素決定控制部38參照成本保持部35判定存在使用成本為最小的資源元素D0，並將資源元素D0分配給分配對象t262(步驟b6、b16、圖26A的(a)、圖27B的(a))。
資源元素決定控制部38返回到步驟b1，對未分配的分配對象t263、t264也和分配對象t262一樣進行分配處理，如圖26A的(b)、(c)那樣分配D0。
資源元素決定控制部38取出未分配的並且優先級高的t265(步驟b1、b2)。
接著，資源元素決定控制部38起動可分配資源元素檢測部32，得到可分配的資源元素D0、D1、D2、D3、A0、A1、A2、Mm後保存進分配候補資源元素保持部31中(步驟b3，圖26B的(d))。
然後，資源元素決定控制部38起動使用成本計算控制部34，如圖27B(d)所示的那樣對分配候補資源元素保持部31的各資源元素的計算使用成本(步驟b4)。
資源元素決定控制部38判斷多資源即存貯器的使用成本是否為最小，但是，由於不是最小，所以進行步驟b6(步驟b5)。
然後，資源元素決定控制部38判斷使用成本最小的資源元素是否是唯一的，但是，由於不是唯一的，所以進行步驟b7(步驟b6)。
資源元素決定控制部38將使用成本不是最小的資源元素從分配候補資源元素保持部31的分配候補集合中去除(步驟b7、圖26B的(d-1))。
而後，資源元素決定控制部38輸入t265，起動推斷增益計算部36，對分配候補資源元素保持部31中保持的各資源元素進行增益計算(步驟b8)。
這裡，參照圖15、圖16所示的增益推斷控制部51的流程圖說明關於t265的推斷增益計算部36的處理內容。
首先，增益推斷控制部51將與增益保持部37和得失保持部56各資源元素對應的內容置為零(步驟d1、圖28A(d)、圖28B(d))。
接著，增益推斷控制部51清除追蹤對象保持部52、已處理分配對象保持部53和已損失分配對象保持部54(步驟d2、圖28C(d)、圖29A(d)、圖29B(d))。
然後，增益推斷控制部51對分配對象t265生成追蹤對象A1，按圖24將A1的各項目設定為A1.ASO＝t265A1.LNS＝1A1.RES＝D0、D1、D2、D3、A0、A1、A2。
如圖28C(d-1)所示的那樣，將A1存入追蹤對象保持部52(步驟d3)。在圖28C(d-1)中用(A1、t265、1(D0、D1、D2、D3、A0、A1、A2))表示追蹤對象，各項目表示(追蹤對象名、分配對象、生存區間長度之和，資源元素集合)。
再後，增益推斷控制部51調出得失計算子程序。
這裡，參照圖16所示的流程圖進一步說明關於分配對象t265的增益推斷控制部51的處理內容。
首先，在步驟e1、e2，從追蹤對象保持部52中取出追蹤對象A1，並從追蹤對象保持部52中消除。將追蹤對象A1的分配對象項目即分配對象t265存入已處理分配對象保持部53(圖28C(d-2)，圖29A(d-1))。
接著，在步驟e3，因為追蹤對象A1的分配對象項目即分配對象t265沒有分配資源元素，所以，進入步驟e5。
在步驟e5～e9，因為集合OS1是空的，所以，集合RS1、集合OS2、集合RS2也是空的，不計算得失值(圖29B(d-1))。
而後，在步驟e10，因為不存在與追蹤對象A1的分配對象項目即分配對象t265具有資源繼承關係的分配對象，所以，不生成新的追蹤對象，並返回步驟e1。
再後，在步驟e1，因為追蹤對象保持部52如圖28C(d-2)所示的那樣是空的，所以，結束得失計算子程序的處理，並返回步驟d4。
現在，參照圖15所示流程圖的步驟d5以下的步驟進一步對關於分配對象t265的增益推斷控制部51的處理內容加以說明。
首先，增益推斷控制部51將圖28B(d)所示的得失保持部56的值存入增益保持部37(步驟d5，圖28A(d-1))。
接著，增益推斷控制部51計算存放在圖28A(d-1)所示的增益保持部37中的值為最大的資源元素的集合RS＝(D0、D1、D2、D3、A0、A1、A2)(步驟d6)。
由於集合RS的元素為多個，存在生存區間與分配對象t265重疊並且未分配的分配對象p1、p3，所以，增益推斷控制部51執行步驟d9(步驟d7、d8)。
增益推斷控制部51將集合RS存入分配候補資源元素保持部31，將與增益保持部37的各資源元素對應的內容置為零，將追蹤對象保持部52清除，並將生存區間與分配對象t265重疊並且未分配的分配對象p1、a3存入重複分配對象保持部55(步驟d9、d10、d11，圖26B(d-2)、圖28C(d-3)、圖28A(d-2)、圖29C(d))。
接著，增益推斷控制部51從重複分配對象保持部55中取出分配對象p1，並從重複分配對象保持部55中消除(步驟d12、d13，圖29C(d-1))。
將與得失保持部56的各資源元素對應的內容置為零，增益推斷控制部51清除已處理分配對象保持部53和已損失分配對象保持部54(步驟d14、圖28B(d-1)、圖29A(d-2)、圖29B(d-2))。
然後，增益推斷控制部51對分配對象p1生成追蹤對象A2，根據圖24將A2的各項目設定為A2.ASO＝P1A2.LNS＝1A2.RES＝D0、D1、D2、D3、A0、A1、A2。並如圖28C(d-4)所示的那樣將A2存入追蹤對象保持部52(步驟d15)。
再後，增益推斷控制部51調出得失計算子程序。
現在，參照圖16所示的流程圖進一步說明關於分配對象t265的增益推斷控制部51的處理內容。
首先，在步驟e1、e2從追蹤對象保持部52中取出追蹤對象A2，並從追蹤對象保持部52中消除。將追蹤對象A2的分配對象項目即分配對象p1存進已處理分配對象保持部52(圖28C(D-5)、圖29A(d-3))。
然後，在步驟e3，因為追蹤對象A2的分配對象項目即分配對象p1未分配資源元素，所以，進入步驟e5。
在步驟e5、e6，計算集合OS1＝(Ar11，Fr1，Ar12，Ar22，Fr2，Ar13，Ar23，Fr3，Br1，Br2，Br3，t262，t263，t264)和集合RS1＝(D0、D1、A0)。
在步驟e7、e8，因為如圖29B(d-2)所示的那樣已損失分配對象保持部54為空的，所以，有集合OS2＝CAr11，Fr1，Ar12，Ar22，Fr2，Ar13，Ar23，Fr3，Br1，Br2，Br3，t262，t263，t264)、集合RS2＝(D0、D1、A0)，已損失分配對象保持部54成為圖29B的(d-3)。
在步驟e9，計算得失值＝1/A2.LNS＝1，並從圖28B(d-1)的得失保持部56的資源元素D0、D1、A0的內容中減除(圖28B(d-2))。
在步驟e10，因為不存在與追蹤對象A2的分配對象項目即分配對象b2具有資源繼承關係的分配對象，所以，不生成新的追蹤對象。並返回步驟e1。
然後，在步驟e1，如圖28C(d-5)所示的那樣，由於追蹤對象保持部52為空的，所以，結束得失計算子程序的處理，並返回步驟d16。
現在，參照圖15的流程圖的步驟d17以下的步驟說明有關分配對象t265的增益推斷控制部51的處理內容。
首先，增益推斷控制部51將存放在圖28B(d-2)所示的得失保持部56中的值乘以分配對象p1的分配優先級0.27的值從增益保持部37中減去。亦即，如圖28B(d-2)所示的那樣，當得失值為負值時，最後就如圖28A(d-3)那樣將各值相加。並返回步驟d12(步驟d17)。
接著，增益推斷控制部51從重複分配對象保持部55中取出分配對象a3，並從重複對象保持部55中消除(步驟d12、d13，圖29C(d-2))。
再後，增益推斷控制部51將與得失保持部56的各資源元素對應的內容置為零，清除已處理分配對象保持部53和已損失分配對象保持部54(步驟d14，圖28B(d-3)、圖29A(d-4)、圖29B(d-4))。
增益推斷控制部51對分配對象a3生成追蹤對象A3，按圖24和圖26B的(d-2)將A3的各項目設定為A3.ASO＝a3A3.LNS＝1A3.RES＝D0、D1、D2、D3、A0、A1、A2。如圖28C(d-6)所示的那樣，將A2存入追蹤對象保持部52(步驟d15)。
然後，增益推斷控制部51調出得失值計算子程序(步驟d16)。
這裡，參照圖16所示的流程圖說明有關分配對象t265的增益推斷控制部51的處理內容。
首先，在步驟e1、e2，從追蹤對象保持部52中取出追蹤對象A3，從追蹤對象保持部52中消除。並將追蹤對象A3的分配對象項目即分配對象a3存入已處理分配對象保持部53(圖28C(D-7)，圖29A(d-5))。
在步驟e3，由於追蹤對象A3的分配對象項的分配對象a3未分配資源元素，所以，進入步驟e5。
在步驟e5～e9，由於集合OS1為空的，所以，集合RS1、集合OS2、集合RS2也是空的，所以，不計算得失值(圖29B(d-5))。
然後，在步驟e10，對與追蹤對象A3的分配對象項目即分配對象a3具有資源繼承關係的分配對象t263、t264、x2、x3，如圖28C的(d-8)所示的那樣生成追蹤對象A4、A5、A6、A7。這裡，各追蹤對象的生存區間長度之和成為A3.LNS的1與分配對象a3的生存區間長度3的和4，並返回步驟e1。
接著，在步驟e1、e2，從追蹤對象保持部52中取出追蹤對象A4，從追蹤對象保持部52中消除。並將追蹤對象A4的分配對象項目即分配對象t263存入已處理分配對象保持部53(圖28C(d-9)、圖29A(d-6))。
在步驟e3，由於追蹤對象A4的分配對象項目即分配對象t263已分配資源元素D0，故進入步驟e4。
在步驟e4，計算得失值＝1/A4.LNS＝0.25，加到圖28B(d-3)的得失保持部56的資源元素D0的內容中，並返回步驟e1(圖28B(d-4))。
接著，對追蹤對象A5也進行與追蹤對象A4同樣的處理，追蹤對象保持部52轉移到圖28C的(d-10)，得失保持部56轉移到圖28B的(d-5)，已處理分配對象保持部53轉移到圖29A的(d-7)(步驟e1～e4、e11)。
然後，在步驟e1、e2，從追蹤對象保持部52中取出追蹤對象A6，從追蹤對象保持部52中去除。並將追蹤對象A6的分配對象項目即分配對象x2存入已處理分配對象保持部53中(圖28C(d-11)，圖29A(d-8))。
在步驟e3，由於追蹤對象A6的分配對象項目即分配對象x2未分配資源元素，所以，進入步驟e5。
在步驟e5、e6，計算集合OS1＝(Ar12，Ar22，Fr2，t263，Br2)和集合RS1＝(D0、D1、A0)。
在步驟e7、e8，由於已損失分配對象保持部54如圖29B的(d-5)所示的那樣是空的，所以，成為集合OS2＝(Ar12、Ar22、Fr2、t263、Br2)，集合RS2＝(D0、D1、A0)，已損失分配對象保持部54成為圖29B的(d-6)。
在步驟e9，計算得失值＝1/A6.LNS＝0.25，從圖28B(d-5)的得失保持部56的資源元素D0、D1、A0的內容中減除(圖28B(d-6))。
然後，在步驟e10，因為與追蹤對象A6的分配對象項目即分配對象x2具有資源繼承關係的分配對象a3已存進圖29A(d-8)的已處理分配對象保持部53中，故不生成追蹤對象。返回步驟e1。
對追蹤對象A7也作與追蹤對象A6同樣的處理，追蹤對象保持部52轉移到圖28C的(d-12)，得失保持部56轉移到圖28B的(d-7)，已處理分配對象保持部轉移到圖29A的(d-9)(步驟e1～e4、e10)。
在步驟e1，由於追蹤對象保持部52如圖28C的(d-12)所示的那樣是空的，故結束得失計算子程序的處理，並返回步驟d16。
現在，參照圖15所示的流程圖的步驟d17以下的步驟說明有關分配對象t265的增益推斷控制部51的處理內容。
首先，增益推斷控制部51將圖28B的(d-7)所示的得失保持部56中存放的值乘以分配對象a3的分配優先級2.67的值從增益保持部37中減去。亦即，如圖28B的(d-7)所示的那樣，得失為負數時，最後就如圖28A的(d-4)所示的那樣將各值相加，並返回步驟d12(步驟d17)。
然後，如圖29C的(d-2)所示的那樣，由於重複分配對象保持部55是空的，故增益推斷控制部51使推斷增益計算部36結束處理，並返回步驟b8。
現在，參照圖14所示的流程圖的步驟b9以下的步驟再次說明關於分配對象t265的資源類別成本計算部39的處理內容。
首先，資源元素決定控制部38計算存放在圖28A的(d-4)所示的增益保持部37中的值為最大的資源元素的集合RS＝(D1、A0)，並存進分配候補資源元素保持部33中(圖26B(d-3))(步驟b9)。
然後，資源元素決定控制部38根據集合RS的內容得到集合RES＝(AR，DR)，並存入評價資源41(步驟b10，圖31C(d))。
由於集合RES存在二個資源，故資源元素決定控制部38執行步驟b12(步驟b11)。
然後，資源元素決定控制部38起動資源類別成本計算部39，進行成本計算(步驟b12)。
現在，參照圖17所示的流程圖再次說明關於分配對象t265的資源類別成本計算部39的處理內容。
首先，資源類別成本計算控制部501將與資源成本保持部40和資源類別總成本保持部505的各資源元素對應的內容置為零(步驟f1，圖30A(d)，圖30B(d))。
資源類別成本計算控制部501清除追蹤對象保持部504和已處理分配對象保持部506(步驟f2，圖30C(d)，圖31A(d))。
然後，資源類別成本計算控制部501對分配對象t265生成追蹤對象rA1，將rA1的各項目設定為rA1.ASO＝t265rA1.LNS＝1。然後，如圖30C的(d-1)所示的那樣，將rA1存入追蹤對象保持部504(步驟f3)。在圖30C(d-1)中如(rA1，t265，1)那樣表示追蹤對象，各項目表示(分配對象名、分配對象、生存區間長之和)。
而後，資源類別成本計算控制部501調出後續成本值計算子程序(步驟f4)。
現在，參照圖18所示的流程圖說明有關分配對象t265的資源類別成本計算部39的處理內容。
首先，在步驟g1、g2，從追蹤對象保持部504中取出追蹤對象rA1，從追蹤對象保持部504中消除。並將追蹤對象rA1的分配對象項目即t265存入已處理分配對象保持部506中(圖30C(d-2)，圖31A(d-1))。
然後，在步驟g3，由於存在存放在圖31C(d)的評價資源保持部41中的具有可分配給分配對象t265的資源AR、DR，所以，首先對資源AR執行步驟g4以下的各步。
在步驟g4，首先取出分配對象t265的使用中間命令i27，在步驟g5生成成本模式(間接引用，An，未，一)，並存入成本模式保持部502中(圖31B(d))。
在步驟g6，取出與成本模式(間接引用，An，未)相匹配的成本項即圖27A的(g)。
在步驟g7，根據取出的成本項的成本2與追蹤對象rA1的生存區間長度之和即rA1.LSN計算後續成本值2/1＝2。
然後，將在步驟g8求得的後續成本值與資源類別總成本保持部505的資源AR的內容相加。(圖30B(d-1))。
然後，返回步驟g4，取出分配對象t265的中間命令i28，生成成本模式(加法，未，An，未)，取出與該成本模式相匹配的圖27A的(f)的成本模式。根據該成本模式的成本3與追蹤對象rA1的生成區間長度之和即rA1.LSN計算後續成本值3/1＝3，並與資源類別總成本保持部505的資源AR的內容相加，成為圖30B的(d-2)。
然後，返回到步驟g4，但是由於已取出全部分配對象t265的中間命令，所以，返回步驟g3。
對資源DR也進行與資源AR同樣的成本計算時，由於與圖27A的(g)、(f)的成本項匹配，結果資源類別總成本保持部505成為圖30B的(d-3)。
然後，返回步驟g3，由於對評價資源保持部41存放的全部資源AR、DR(圖31C(d))的成本計算已結束，所以，執行步驟g9。
在步驟g9，由於不存在與分配對象t265具有資源繼承關係的分配對象，所以，不生成追蹤對象。
然後，返回步驟g1，但是，如圖30C的(d-2)所示的那樣，由於追蹤對象保持部504是空的，故結束後續成本值計算子程序的處理，返回步驟f4。
現在，參照圖17的流程圖中步驟f5以下的步驟說明關於分配對象t265的資源類別成本計算部39的處理內容。
首先，在步驟f5，將資源類別總成本保持部505存放的值存入資源類別成本保持部40中(圖30A(d-1))。
然後，在步驟f6，計算資源類別成本保持部40的值為最小的資源AR、DR，如圖31C的(d-1)所示的那樣存入評價資源保持部41。
在步驟f7，由於資源類別成本保持部40的值為最小的資源有多個，故執行步驟f8。
在步驟f8，由於存在生存區間與分配對象t265重疊的分配對象p1、a3，故執行步驟f9。
在步驟f9、f10，將資源類別成本保持部40的內容置為零，清除追蹤對象保持部504，將分配對象p1、a3存入重複分配對象保持部507(圖30A(d-2)、圖30C(d-3)、圖31D(d))。
在步驟f11、f12、f13，從重複分配對象保持部507中取出分配對象p1，將資源類別總成本保持部505的內容置為零，清除已處理分配對象保持部505(圖31D(d-1)、圖30B(d-4)、圖31A(d-2))。
在步驟f14，對取出的分配對象p1生成追蹤對象rA2，將rA2的各項目設定為rA2.ASO＝P1rA2.LNS＝1。如圖30C的(d-4)所示的那樣，將rA2存入追蹤對象保持部504。
然後，資源類別成本計算部501調出後續成本值計算子程序(步驟f15)。
現在，參照圖18所示的流程圖說明關於分配對象t265的資源類別成本計算部39的處理內容。
首先，在步驟g1、g2，從追蹤對象保持部504中取出追蹤對象rA2，從追蹤對象504中消除。並將追蹤對象rA2的分配對象項目即分配對象p1存入已處理分配對象保持部506中(圖30C(d-5)，圖31A(d-3))。
然後，在步驟g3，由於存在存放在圖31C(d-1)的評價資源保持部41中的可分配給分配對象p1的資源AR、DR，所以，首先對資源AR執行步驟g4以下的步驟。
對分配對象p1的使用中間命令i5、i27、i29、i30分別生成成本模式(代入，An，未，一)，(間接引用，未，An，一)、(加法、An，IM，左同)、(間接引用，未，An，一)，使之分別與圖27A的成本項(h)(i)(a)(i)匹配，根據追蹤對象rA2的生存區間長度之和rA2.LNS計算後續成本值時，如圖30R的(d-5)所示的那樣更新資源類別總成本保持部505的資源AR的內容(步驟g4～g8)。
然後，返回步驟g3，取出資源DR，對分配對象的使用中間命令i5、i27、i29、i30分別生成成本模式(代入，Dn，未，一)、(間接引用，未，Dn，一)、(加法，Dn，IM，左同)、(間接引用，未，Dn，一)，使之分別與圖27A的成本項(h)(j)(a)(i)匹配，根據追蹤對象rA2的生存區間長度之和即rA2.LNS計算後續成本值時，如圖30B的(d-6)所示的那樣，更新資源類別總成本保持部505的資源DR的內容(步驟g4～g8)。
然後，返回步驟g3，由於滿足條件的資源已全部取出，故執行步驟g9。
在步驟g9，由於不存在與分配對象p1具有資源繼承關係的分配對象，故不重新生成追蹤對象，並返回步驟g1。
然後，在步驟g1，如圖30C的(d-5)所示的那樣，由於追蹤對象保持部504為空的，所以，結束後續成本值計算子程序，並返回步驟f15。
現在，參照圖17的流程圖中步驟f16以下的步驟說明關於分配對象t265的資源類別成本計算部39的處理內容。
首先，在步驟f16，按照得失保持部56中存放的值和分配對象p1的優先級0.27，如圖30A的(d-3)所示的那樣，更新資源類別成本保持部40的資源AR、DR的內容。
在步驟f11、f12、f13，從重複分配對象保持部507中取出分配對象a3，將資源類別總成本保持部505的內容置為零，清除已處理分配對象保持部506(圖31D(d-2)、圖30B(d-7)、圖31A(d-4))。
在步驟f14，對取出的分配對象a3的生成追蹤對象rA3，將rA3的各項目設定為rA3.ASO＝a3rA3.LNS＝1。如圖30C的(d-6)所示的那樣，將rA3存入追蹤對象保持部504。
然後，在步驟f15，資源類別成本計算控制部501調出後續成本值計算子程序。
現在，參照圖18所示的流程圖說明有關分配對象t265的資源類別成本計算部39的處理內容。
首先，在步驟g1、g2，從追蹤對象保持部504中取出追蹤對象rA3，從追蹤對象保持部504中刪除。並將追蹤對象rA3的分配對象項目即分配對象a3存入處理畢分配對象保持部506(圖30C(d-7)，圖31A(d-5))。
在步驟g3，由於存在存放在圖31C的(d-1)的評價資源保持部41中的可分配給分配對象a3的資源AR、DR，故執行步驟g4以下各步。
對分配對象a3的中間命令i20、i26、i28分別生成成本模式(加法，未，未，不同)、(加法，未，未，不同)、(加法，An，未，未)，使之與圖27的成本項(k)(k)(1)匹配，如圖30B的(d-8)所示的那樣，更新資源類別總成本保持部505的資源AR的內容(步驟g4～g8)。
然後，返回步驟g3，取出資源DR，對資源DR進行同樣的處理，如圖30B的(d-9)所示的那樣，更新資源類別總成本保持部505的資源DR的內容(步驟g4～g8)。
然後，返回步驟g3，由於滿足條件的資源已全部取出，所以，執行步驟g9。
在步驟g9，對與分配對象a3具有資源繼承關係的未分配的分配對象並且未存放到圖31A的(d-5)的已處理分配對象保持部506中的分配對象x2、x3，如圖30C的(d-8)所示的那樣，生成追蹤對象rA4、rA5。
接著，在步驟g1、g2，從追蹤對象保持部504中取出追蹤對象rA4，從追蹤對象保持部504中消除。並將追蹤對象rA4的分配對象項目即x2存入已處理分配對象保持部506中(圖30C(d-9)，圖31A(d-6))。
在步驟g3，由於存在存放在圖31C(d-1)的評價資源保持部41中的可分配給分配對象x2的資源AR、DR，所以，執行步驟g4以下的處理。
對分配對象x2的使用中間命令i12、i13、i20分別生成(加法，未，IM，不同)、(加法，An，IM，未)、(加法、未，An，未)，使之與圖27A的成本項(m)(b)(f)匹配，計算成本值8，由於追蹤對象rA4的生存區間長度之和項目即rA4.LNS為4，所以，後續成本值就成為8/4＝2，如圖30B的(d-10)所示的那樣，更新資源類別總成本保持部505的資源AR的內容(步驟g4～g8)。
然後，返回步驟g3，取出資源DR，對資源DR進行同樣的處理，如圖30B(d-11)所示的那樣，更新資源類別總成本保持部505的資源DR的內容(步驟g4～g8)。
然後，返回步驟g3，由於滿足條件的資源已全部取出，故執行步驟g9。
在步驟g9，因為與分配對象x2具有資源繼承關係的唯一分配對象a3，如圖31A(d-6)所示的那樣未存入已處理分配對象保持部506中，故不重新生成追蹤對象，並返回步驟g1。
在步驟g1、g2，從追蹤對象保持部504中取出追蹤對象rA5，從追蹤對象保持部504中消除。並將追蹤對象rA5的分配對象項目即x3存入處理畢分配對象保持部506中(圖30C(d-10)、圖31A(d-7))。
接著，與前述追蹤對象rA4的分配對象x2一樣，對分配對象x3的使用中間命令i13、i26計算資源AR、DR的後續成本值如圖30B(d-12)所示的那樣，更新資源類別總成本保持部505的資源AR及資源DR的內容(步驟g3～g8)。
在步驟g9，由於與分配對象x3具有資源繼承關係的唯一的分配對象a3如圖31A(d-7)所示的那樣未存入已處理分配對象保持部506，故不生成新的追蹤對象而返回步驟g1。
接著，在步驟g1，如圖30C(d-10)所示的那樣，由於追蹤對象保持部504為空的，故結束後續成本值計算子程序，並返回步驟f15。
現在，參照圖17的流程圖中步驟f16以下步驟說明關於分配對象t265的資源類別成本計算部39的處理內容。
首先，在步驟f16，根據得失保持部56中存放的值和分配對象a3的優先級2.67，如圖30A(d-4)所示的那樣，更新資源成本保持部40的資源AR、DR的內容。
接著，返回步驟f11，但是，如圖31D(d-2)所示的那樣，由於重複分配對象保持部507是空的，所以，終止資源類別成本計算部39的處理，並返回步驟b12。
現在，參照圖14所示的流程圖的步驟b13以下各步說明有關分配對象t265的資源類別成本計算部39的處理內容。
首先，資源元素決定控制部38將屬於圖31C(d-1)的評價資源保持部41的、存放在圖30A(d-4)的資源類別成本保持部40中的成本為最小的資源、並且是存放在圖26B(d-3)的分配候補資源元素保持部31中的資源元素D1，分配給t265(步驟b13)。
對全部分配對象進行這樣的處理，並將資源元素分配給各分配對象(對上述分配對象t265以後的分配對象的說明省略)。
這樣，根據本發明，由於參照程序中的各分配對象的資源繼承關係達到多大範圍，所以，可以進行更理想的資源分配。
向嵌套級深的地點優先分配寄存器，再可以獲得預先將此已分配的寄存器向嵌套淺的場所擴散的靈活的分配結果。另外，向使用頻率高的場所優先分配寄存器，也可以獲得預先將此已分配的寄存器向嵌套級淺低的地點擴散的靈活的分配結果。進而，可以實現自變量寄存器、返回值寄存器、破壞性寄存器等預先分配的對象已確定的分配對象將其資源向周圍擴展的靈活的資源分配。
由於分配結果極其簡單，所以，可以進一步改善最後生成的機器語言程序的程序大小和執行速度。
上述實施例雖然是按順次進行使用成本值計算、得失值計算、後續成本值計算的結構將計算處理按層次細分的形式加以說明的，但本實施例在不離開其宗旨的範圍內可以變更地實施。下面列舉出二個代表性的應用示例。
應用例1特別是當對減少執行時間比對縮小編譯程序生成的目的代碼的大小更重視時，已知存在分配對象x的使用中間命令i的循環級或i的執行次數時，可以將其執行次數與在步驟c7取出的成本項e1的成本相乘、並將乘積值加到總成本保持部中(在圖15的使用成本計算控制部47的流程圖的步驟c4檢測循環級次，並輸入使用成本計算部34)。
應用例2在步驟b9求出的資源元素的集合RS中存在多個資源元素時，在步驟b12的資源類別成本計算的後續成本值計算中，通過進行與在步驟b4進行的使用成本計算相同的處理，也可以從集合RS中選出更合適的資源元素分配給分配對象x。
這時，首先將步驟g5～g8置換為與步驟c5～c9相同的處理，計算使用成本，然後，將如圖17、18中的總成本保持部46置換為資源類別總成本保持部505、將使用成本保持部35置換為資源類別成本保持部40、將使用成本置換為後續成本值。然後，在步驟b11判定集合RS的元素是否為多個。
在步驟b12和步驟f1～f6，計算將屬於資源RS的資源元素分配給與分配對象x具有資源繼承關係或者間接地具有資源繼承關係的未分配的分配對象x1時的使用成本，並將計算出的使用成本再除以從分配對象x到分配對象x1的生存區間的長度，然後，將得到的值保存進使用成本保持部35中。反之，在步驟f7，當使用成本保持部35中所保存的最小成本的資源元素有多個時，就執行步驟f8，在步驟f8～f11，計算將屬於集合RS的資源元素分配給生存區間與分配對象x重疊並且未分配的分配對象x2存在資源繼承關係的或者間接地具有資源繼承關係的未分配的分配對象x3時的使用成本，並將計算出的值除以從分配對象x2到分配對象x3的生存區間的長度，然後再乘以-1，最後將所得結果保存於使用成本保持部35中。
這樣，參照保持使用成本的使用成本保持部35的保持內容，便可將保持內容為最小的資源元素分配給分配對象x。
應用例3
作為得失值雖然使用了生存區間之和，但也可將其作為分配對象的個數。例如，在圖21中，可用從分配對象x到分配對象x2存在的分配對象的個數3(分配對象x、x5、x6)，使分配給分配對象x2的資源要素D1的得失值為1/3。
應用例4
在本實施例中，求出正號得失值和負號得失值後，將它們的和作為最後的得失值，但也可以分別使用上述得失值，根據一方的得失值縮小分配寄存器的候補，另外根據另一方的得失值決定分配寄存器。例如，在圖15中的分配對象x的寄存器決定中，可分配給分配對象x的資源要素為D1、D2、D3。這時，可分配的資源要素中，首先將負得失值最小的資源要素作為分配對象x的分配候補。但是，關於負得失值不能設定的資源要素，將負得失值取為0。於是，資源要素D2、D3的負得失值變為0。這樣一來，由於資源要素D1的負得失值為Px/(L2+L3)，所以負得失值最大的資源要素變為D2、D3，將其作為新的分配對象x的分配候補。
其次，將正得失值最大的資源要素分配給分配對象x。但是，關於正得失值設定的資源要素，正得失值取0。於是，資源要素D3的得失值變為0，將得失值最大的資源要素D2分配給分配對象。
權利要求
1.用於將高級語言編寫的程序翻譯成機器語言程序的編譯程序、生成多個以程式語言描述的程序中的變量與生存區間的組合即分配對象並將寄存器、存貯器等硬體資源所具有的資源元素順序分配給所生成的分配對象的資源分配設備，其特徵是包含如下結構，即得失值計算裝置，根據分配對象中已分配的分配對象的生存區間和隨後應分配的分配對象的生存區間在程序處於什麼樣的位置關係，對各資源元素計算表示哪一資源元素對隨後應分配的分配對象適宜的得失值；分配裝置，根據對各資源元素計算的得失值的大小將某個資源元素分配給應分配的分配對象；和控制裝置，反覆起動得失值計算裝置和分配裝置，直至全部分配對象被分配為止。
2.權利要求1中所述資源分配設備，其特徵是具有判斷程序中各分配對象的位置關係的位置關係判斷裝置，所述位置關係判斷裝置包含如下結構，即重複關係判斷裝置，判斷已分配資源元素的分配對象的生存區間是否與應分配的分配對象的生存區間相重複；已分配一被分配間連續判斷裝置，判斷已分配資源元素的分配對象的生存區間與應分配的分配對象的生存區間是否連續。所述得失值計算裝置包含如下結構，即第一增加部，當由已分配一被分配間連續判斷裝置判定生存區間與應分配的分配對象連續時，就根據從已分配資源元素的分配對象到應分配的分配對象為止的生存區間的長短，在判定為連續的已分配的分配對象中，使已分配的資源元素的得失值增加，上述分配裝置不將分配給具有由重複關係判斷裝置判定生存區間重複的已分配的分配對象的資源元素分配給應分配的分配對象，而將判定生存區間不重複的已分配的分配對象中得失值為最大的資源元素分配給應分配的分配對象。
3.權利要求2中所述資源分配設備，其特徵是所述位置關係判斷裝置包含如下結構，即已分配一側重疊分配對象檢測裝置，檢測具有與已分配資源元素的分配對象重疊的生存區間的未分配的分配對象；和未分配—被分配間連續判斷裝置，判斷所檢測的未分配的分配對象的生存區間與應分配的分配對象的生存區間是否連續，所述得失值計算裝置包含如下結構，即第一減少部，當判斷為連續時，根據從已分配一側重疊分配對象檢測裝置檢測的未分配的分配對象到應分配的分配對象的生存區間的長短，減小分配給該已分配的分配對象的資源元素的得失值。
4.權利要求3中所述資源分配設備，其特徵是當由已分配一側重疊分配對象檢測裝置判定有多個未分配的分配對象時，所述未分配—被分配間連續判斷裝置判斷所檢測的多個未分配的分配對象中哪一個的生存區間與應分配的分配對象的生存區間連續。
5.權利要求3中所述資源分配設備，其特徵是還包含優先級存貯裝置，用於與各分配對象相對應地存貯反映程序中分配對象的使用頻度和/或生存區間的嵌套級的分配對象的優先級；所述得失值計算裝置和分配裝置按此優先級存貯裝置存貯的優先級順序確定應分配的分配對象。
6.權利要求5中所述資源分配設備，其特徵是所述位置關係判斷裝置包含如下結構，即被分配一側重疊分配對象檢測裝置，在由得失值計算裝置對各資源元素計算出的得失值在多個資源元素相互大小相同時，檢測具有與應分配的分配對象的生存區間重疊的生存區間的未分配的分配對象；和未分配—已分配間連續判定裝置，判斷所檢測的分配對象的生存區間與已分配資源元素的分配對象的生存區間是否連續，所述得失值計算裝置包含如下結構，即優先級檢測部，檢測由被分配一側重疊分配對象檢測部檢測的分配對象的優先級；第一縮短計算部，計算從已分配的分配對象到所檢測的未分配的分配對象的生存區間的長短；和第二減小部，將所檢測的優先級乘以計算的長短，根據此乘積結果減小該已分配資源元素的得失值。
7.權利要求6中所述資源分配設備，其特徵是所述位置關係判斷裝置包含如下結構，即已分配一側重疊分配對象檢測裝置，檢測具有與已分配資源元素的分配對象的生存區間重疊的生存區間的未分配的分配對象；未分配—未分配間連續判斷裝置，判斷由被分配一側重疊分配對象檢測裝置檢測的未分配的分配對象的生存區間是否與由已分配一側重疊分配對象檢測裝置檢測的未分配的分配對象的生存區間相連續，所述得失值計算裝置包含如下結構，即第二縮短計算部，計算從被分配一側重疊分配對象檢測裝置所檢測的未分配的分配對象到已分配側重疊分配對象檢測裝置所檢測的未分配的分配對象的生存區間長短；第二增加部，將檢測的優先級乘以計算長短，根據此乘積結果增加分配給已分配的分配對象的資源元素的得失值。
8.權利要求7中所述資源分配設備，其特徵是當由已分配一側重疊分配對象檢測裝置判定有多個未分配的分配對象時，所述未分配—未分配間連續判斷裝置判斷所檢測的多個未分配的分配對象中哪一個的生存區間與應分配的分配對象的生存區間相連續。
9.權利要求7中所述資源分配設備，其特徵是還包含有得失值存貯部，存放全部資源元素和各自對應的各資源元素的得失值的初始值，第一和第二增加部使得失值存貯部中存放的各資源元素的得失值增加，而第一和第二減小部則使得失值存貯部中存放的各資源元素的得失值減少。
10.權利要求9中所述資源分配設備，其特徵是還包含如下結構，即推斷裝置，在程序中分配各資源的資源元素時，對於分配的分配對象與各資源元素的組合通過計算其總和值的推斷值，來推斷定義3應分配的分配對象的全部定義命令和使用的全部使用命令的執行周期和/或代碼大小的總和值達到什麼程度；和資源元素單復判斷裝置，對各資源元素的推斷結果即推斷值進行比較，判斷推斷值為最小的資源元素是一個還是多個，當判定為一個時，所述分配裝置將推斷值為最小的資源元素分配給應分配的分配對象，當判定為多個時，將得失值為最大的資源元素分配給應分配的分配對象。
11.權利要求10中所述資源分配設備，其特徵是所述推斷裝置包含如下結構，即命令模式輸出部，對在程序中分配對象的全部定義命令和使用命令，採用機器語言命令格式輸出表示程序中的該分配對象的定義命令和使用命令的信息即命令模式；成本存貯部，與由命令模式輸出部輸出的命令模式分別對應地存貯表示機器語言命令的各操作數中應用各資源的資源元素時該定義命令和使用命令的執行周期和/或代碼大小的成本；和成本總和部，從成本存貯部中取出與所輸出的命令模式對應的成本，將取出的成本對各資源元素累計求和，並將求和所得的總和值作為推斷值。
12.權利要求10中所述資源分配設備，其特徵是還包含預測裝置，用於當時各資源元素由得失值計算裝置計算的得失值在多個不同資源的資源元素之間具有相同大小時，預測優先級比應分配的分配對象低、並且對於在此應分配的分配對象之後進行分配的全部未分配的分配對象最適合的資源元素。上述分配裝置將由預測裝置預測的資源元素分配給應分配的分配對象。
13.權利要求12中所述資源分配設備，其特徵是所述預測裝置包含如下結構，即第一後續分配對象檢測裝置，用於檢測全部具有與應分配的分配對象的生存區間相連續的生存區間並且優先級比該分配對象低的未分配的分配對象。第一推斷裝置，對於第一後續分配對象檢測裝置檢測的全部分配對象和各資源元素的組合通過計算該總和值的推斷值，推斷當向檢測的各分配對象分配各資源元素時定義該分配對象的全部定義命令和使用的全部使用命令的執行周期和/或代碼大小的總和值達到什麼程度；第一生存區間長度計數裝置，對由第一後續分配對象檢測裝置所檢測的每一分配對象，計數介於由第一後續分配對象檢測裝置檢測的各分配對象與應分配的分配對象之間的連續的生存區間長度；第一加權裝置，對於檢測的各分配對象與各資源元素的組合，將對該分配對象計數的生存區間的長短作為權重對由第一推斷裝置計算的推斷值進行加權；第一總和裝置，對由第一加權裝置加權後的推斷值按各資源元素進行求和計算；和第一優化資源元素判斷裝置，將由第一總和裝置求和的總和結果為最小的資源元素判斷為最合適於優先級比應分配的分配對象低的未分配的分配對象的資源元素。
14.權利要求13中所述資源分配設備，其特徵是所述預測裝置包含如下結構，即第二後續分配對象檢測裝置，當判定由第一優化資源元素判斷裝置是多個資源元素最合適時，檢測生存區間與應分配的分配對象重疊的未分配的分配對象和具有與該未分配的分配對象的生存區間連續的生存區間的未分配的分配對象；第二推斷裝置，當將各資源元素分配給由第二後續分配對象檢測裝置檢測的未分配的分配對象時，對於檢測的分配對象與各資源元素的組合，通過計算該總和值的推斷值；來推斷定義所檢測的各分配對象的全部定義命令和使用的全部使用命令的執行周期和/或代碼大小的總和值達到什麼程度；第二生存區間長計數裝置，對於由第二後續分配對象檢測裝置檢測的每一分配對象，計數介於生存區間與應分配的分配對象的生存區間重疊的未分配的分配對象和具有與該重疊一側的分配對象的生存區間連續的生存區間的分配對象之間的連續的生存區間的長度；第二加權裝置，對於由第二後續分配對象檢測裝置檢測的未分配的分配對象與各資源元素的組合，將對該分配對象計數的生存區間的長短和各分配對象的優先級作為權重對由第二推斷裝置推斷的推斷值進行加權；第二總和裝置，對由第二加權裝置加權後的各分配對象的推斷值按各資源元素進行求和計算；和第二優化資源元素判斷裝置，判定由第二總和裝置對各資源元素求和的總和值為最大的資源元素為最合適於在應分配的分配對象之後進行分配的全部未分配的分配對象的資源元素。
15.權利要求14中所述資源分配設備，其特徵是所述第一和第二加權裝置，在第一和第二生存區間長度計數裝置計數的分配對象間的生存區間長度為0時，將1作為生存區間的長短進行加權，當計數的生存區間長度不是0時，就計算該生存區間長度的倒數，並將計算的此生存區間長的倒數作為生存區間長短進行加權。
16.權利要求15中所述資源分配設備，其特徵是包含有成本存貯裝置，當存貯多個使用機器語言命令格式表示程序中分配對象的定義命令和使用命令的信息即命令模式、並在機器語言命令中使用各資源的資源元素時，與各命令模式對應地存貯表示程序中的分配對象的定義命令和使用命令的執行周期和/或代碼大小的成本，上述第一推斷裝置包含如下結構，即第一命令模式輸出部，讀出與由第一後續分配對象檢測裝置檢測的未分配的分配對象的全部定義命令和使用命令對應的命令模式，並輸出讀出的命令模式；和第一成本總和部，從成本存貯裝置中取出與輸出的命令模式對應的成本，按每一資源元素對取出的成本進行求和計算，並將求和的總和值作為推斷值，所述第二推斷裝置包含如下結構，即第二命令模式輸出部，讀出與由第二後續分配對象檢測裝置檢測的未分配的分配對象的全部定義命令和使用命令對應的命令模式，並輸出讀出的命令模式；和第二成本總和部，從成本存貯裝置中取出與輸出的命令模式對應的成本，按每一資源元素對取出的成本進行求和計算，並將求和的總和值作為推斷值。
17.權利要求16中所述資源分配設備，其特徵是命令模式具有表示運算結果的存貯目標為哪一操作數或與任一操作數也不一致的信息，與存貯目標為操作數的命令模式對應的成本小於與非操作數命令模式對應的成本。
18.權利要求16中所述資源分配設備，其特徵是命令模式具有表示對應的使用命令是生存區間的結束點或非結束點的信息，與是結束點的命令模式對應的成本小於與非結束點對應的命令模式的成本。
19.權利要求9中所述資源分配設備，其特徵是還包含如下結構，即預約分配對象檢測裝置，根據上述程序檢測應分配的資源元素預先確定的分配對象；和預約資源元素存貯裝置，存貯應分配給預約分配對象檢測裝置檢測的分配對象的資源元素，分配裝置將應分配的資源元素分配給由預約分配對象檢測裝置檢測的分配對象，在分配之後將某個資源元素分配給優先級最大的分配對象。
20.權利要求19中所述資源分配設備，其特徵是所述預約分配對象檢測裝置根據上述程序檢測保持調用函數的自變量的分配對象，上述預約資源元素存貯裝置存貯應分配給該分配對象的自變量寄存器。
21.權利要求19中所述資源分配設備，其特徵是所述預約分配對象檢測裝置根據上述程序檢測保持函數調用的返回值的分配對象，上述預約資源元素存貯裝置存貯應分配給該分配對象的返回值寄存器。
22.權利要求19中所述資源分配設備，其特徵是所述預約分配對象檢測裝置根據上述程序檢測數值可重置的分配對象，所述預約資源元素存貯裝置存貯應分配給該分配對象的破壞寄存器。
23.權利要求9中所述資源分配設備，其特徵是還包含如下結構，即生存區間繼承關係集合存貯裝置，與由生存區間在該分配對象的起始點結束的全部分配對象和生存區間在該分配對象的結束點開始的全部分配對象組成的集合即生存區間繼承關係集合對應地存貯程序中的各分配對象，上述已分配—被分配間連續判斷裝置包含如下結構，即第一判斷部，參照關於應分配的分配對象的生存區間繼承關係集合，判斷在該生存區間繼承關係集合中是否存在已分配的分配對象；第二判定部，用於當判定不存在已分配的分配對象時，取出生存區間繼承關係集合內的其他分配對象，並參照關於取出的分配對象的生存區間繼承關係集合，判斷該生存區間繼承關係集合中是否存在已分配的分配對象；控制部，用於反覆起動第二判定部直至判定存在已分配的分配對象時為止；總和部，用於對作為檢測結果的分配對象的生存區間長度進行求和計算；和倒數計算部，計算應分配的分配對象的生存區間長度與由總和部求和的生存區間長度之和的倒數，並將計算結果作為生存區間長短。
24.權利要求23中所述資源分配設備，其特徵是分配對象的生存區間利用從該生存區間所佔據的程序中由開始點到結束點的命令位置信息表示，所述總和部對此命令位置信息進行求和計算，並將總和值作為生存區間長度。
25.權利要求24中所述資源分配設備，其特徵是分配對象的生存區間的開始點和結束點用程序中的命令位置信息表示，所述資源分配設備還包含如下結構，即開始結束點存貯裝置，對應地存貯程序中的分配對象、與各分配對象的生存區間的開始點相當的命令位置信息和與各分配對象的生存區間的結束點相當的命令位置信息；第一集合化裝置，參照開始結束點存貯裝置，查找出與程序中各分配對象的以生存區間的開始點相當的命令位置信息與結束點相當的全部分配對象，並將查找出的分配對象和程序中的分配對象作為同一生存區間繼承關係集合；第二集合化裝置，參照開始結束點存貯裝置，查找出與程序中各分配對象的於生存區間的結束點相當的命令位置信息與開始點相當的全部分配對象，並將查找出的分配對象和程序中的分配對象作為同一生存區間繼承關係集合；和寫入裝置，將程序中的分配對象和由第一及第二集合化裝置進行集合化處理後的生存區間繼承集合對應地寫入生存區間繼承關係集合存貯部。
26.權利要求9中所述資源分配設備，其特徵是還包含生存區間繼承關係集合存貯裝置，與由生存區間在分配對象的開始點結束的全部分配對象和生存區間在該分配對象的結束點開始的全部分配對象組成的集合即生存區間繼承關係集合對應地存貯程序中的各分配對象；上述未分配—被分配間連續判斷裝置包含如下結構，即第一判斷部，參照關於應分配的分配對象的生存區間繼承關係集合，判斷該生存區間繼承關係集合中是否存在由已分配一側重分配對象檢測裝置檢測的未分配的分配對象；第二判斷部，用於當判定不存在未分配的分配對象時就取出生存區間繼承關係集合內的其他的分配對象，並參照關於取出的分配對象的生存區間繼承關係集合，判斷該生存區間繼承關係集合中是否存在由已分配一側重分配對象檢測裝置檢測的未分配的分配對象；控制部，用於反覆起動第二判斷部直至判定存在有未分配的分配對象時為止，上述得失值計算裝置包含如下結構，即總和部，用於對作為檢測結果的分配對象的生存區間長度進行求總和；倒數計算部，計算應分配的分配對象的生存區間長度與由總和部求和的生存區間長度之和的倒數，並將計算結果作為生存區間長短。
27.權利要求26中所述資源分配設備，其特徵是分配對象的生存區間利用從該生存區間所佔據的程序中開始點到結束點的命令位置信息表示。
28.權利要求27中所述資源分配設備，其特徵是分配對象的生存區間的開始點和結束點用程序中的命令位置信息表示。上述資源分配設備還包含如下結構，即開始結束點存貯裝置，對應地存貯程序中的分配對象、與各分配對象的生存區間的開始點相當的命令位置信息和與各分配對象的生存區間的結束點相當的命令位置信息；第一集合化裝置，參照開始結束點存貯裝置查找出與程序中各分配對象的生存區間開始點相當的命令位置信息與結束點相當的全部分配對象，並將查找出的分配對象與程序中的分配對象作為同一生存區間繼承關係集合；第二集合化裝置，參照開始結束點存貯裝置查找出與程序中各分配對象的生存區間結束點相當的命令位置信息與開始點相當的全部分配對象，並將查找出的分配對象與程序中的分配對象作為同一生存區間繼承關係集合；寫入裝置，將程序中的分配對象和由第一及第二集合化裝置進行集合化處理後的生存區間繼承集合對應地寫入生存區間繼承關係集合存貯部。
29.權利要求9中所述資源分配設備，其特徵是還包含有生存區間繼承關係集合存貯裝置，用於與由生存區間在該分配對象的開始點結束的全部分配對象和生存區間在該分配對象的結束點開始的全部分配對象構成的集合即生存區間繼承關係集合對應地存貯程序中的各分配對象，上述未分配—分配畢間連續判斷裝置包含如下結構，即第一判斷部，參照關於由被分配一側重疊分配對象檢測裝置檢測的未分配的分配對象的生存區間繼承關係集合，判斷該生存區間繼承關係集合中是否存在已分配的分配對象；第二判斷部，用於當不存在已分配的分配對象時，取出生存區間繼承關係集合內的其他的分配對象，並參照關於取出的分配對象的生存區間繼承關係集合，判斷該生存區間繼承關係集合中是否存在有已分配的分配對象；控制部，用於反覆起動第二判斷部直到判定存在已分配的分配對象時為止，上述得失值計算裝置包含如下結構，即總和部，對作為檢測結果的分配對象的生存區間長度進行求和計算；倒數計算部，計算應分配的分配對象的生存區間長度與由總和部求和的生存區間長度之和的倒數，並將計算結果作為生存區間長短。
30.權利要求29中所述資源分配設備，其特徵是分配對象的生存區間用該生存區間所佔據的程序中的開始點到結束點的命令位置信息表示，總和部對命令位置信息數進行求和，並將總和值作為生存區間長度。
31.權利要求30中所述資源分配設備，其特徵是分配對象生存區間的開始點和結束點用程序中的命令位置信息表示，上述資源分配設備還包含如下結構，即開始結束點存貯裝置，對應地存貯程序中的分配對象、與各分配對象的生存區間的開始點相當的命令位置信息和與各分配對象的生存區間的結束點相當的命令位置信息；第一集合化裝置，參照開始結束點存貯裝置，查找出與程序中各分配對象的生存區間的開始點相當的命令位置信息與結束點相當的全部分配對象，並將查找出的分配對象與程序中的分配對象作為同一生存區間繼承關係集合；第二集合化裝置，參照開始結束點存貯裝置，查找出與程序中各分配對象的生存區間的結束點相當的命令位置信息與開始點相當的全部分配對象，並將查找出的分配對象與程序中的分配對象作為同一生存區間繼承關係集合；和寫入裝置，將程序中的分配對象和由第一及第二集合化裝置進行集合化處理後的生存區間繼承集合對應地寫入生存區間繼承關係集合存貯部。
32.權利要求9中所述資源分配設備，其特徵是還包含生存區間繼承關係集合存貯裝置，對應與由生存區間在該分配對象的開始點結束的全部分配對象和生存區間在該分配對象的結束點開始的全部分配對象構成的集合即生存區間繼承關係集合對應地存貯程序中的各分配對象，上述未分配—未分配間連續判斷裝置包含如下結構，即第一判斷部，參照關於由被分配一側重疊分配對象檢測裝置檢測的未分配的分配對象的生存區間繼承關係集合，判斷在該生存區間繼承關係集合中是否存在由已分配一側重分配對象檢測裝置檢測的未分配的分配對象；第二判斷部，用於當判定不存在未分配的分配對象時，取出生存區間繼承關係集合中的其他分配對象，並參照關於取出的分配對象的生存區間繼承關係集合，判斷該生存區間繼承關係集合中是否存在由已分配一側重分配對象檢測裝置所檢測的未分配的分配對象；控制部，用於反覆起動第二判斷部直到判定存在未分配的分配對象時為止；總和部，對作為檢測結果的分配對象的生存區間長度進行求和計算；和倒數計算部，計算應分配的分配對象的生存區間長度與由總和部求和的生存區間長度之和的倒數，並將計算結果作為生存區間長短。
33.權利要求32中所述資源分配設備，其特徵是分配對象的生存區間用該生存區間所佔據的程序中的開始點到結束點的命令位置信息表示，總和部對命令位置信息數求和，並將求和值作為生存區間長度。
34.權利要求33中所述資源分配設備，其特徵是分配對象的生存區間的開始點和結束點用程序中的命令位置信息表示，上述資源分配設備還包含如下結構，即開始結束點存貯裝置，對應地存貯程序中的分配對象、與各分配對象生存區間的開始點相當的命令位置信息和與各分配對象生存區間結束點相當的命令位置信息；第一集合化裝置，參照開始結束點存貯裝置，查找出與程序中各分配對象的生存區間開始點相當的命令位置信息與結束點相當的全部分配對象，並將查找出的分配對象與程序中的分配對象作為同一的生存區間繼承關係集合；第二集合化裝置，參照開始結束點存貯裝置，查找出與程序中各分配對象的生存區間的結束點相當的命令位置信息與起始點相當的全部分配對象，並將查找出的分配對象與程序中的分配對象作為同一的生存區間繼承關係集合；寫入裝置，將程序中的分配對象與由第一和第二集合化裝置進行集合化處理後的生存區間繼承集合對應地寫入生存區間繼承關係集合存貯部。
35.用於將高級語言編寫的程序翻譯成機器語言程序的編譯程序、生成多個以程式語言描述的程序中的變量與生存區間的組合即分配對象並將優先級賦予生成的分配對象後，按優先級順序將寄存器、存貯器等硬體即資源的資源元素分配給分配對象的資源分配設備，其特徵是包含如下結構，即優先級賦予裝置，從程序各部分檢測程序中的分配對象的使用頻度和/或生存區間的嵌套級，並根據檢測結果將優先級賦予分配對象；得失值計算裝置，根據分配對象中已分配的分配對象的生存區間與隨後應分配的分配對象的生存區間在程序中處於什麼樣的位置關係對各資源元素計算表示哪一資源元素合適於隨後應分配的分配對象的得失值；分配裝置，根據對各資源元素計算出的得失值的大小將某個資源元素分配給應分配的分配對象；控制裝置，用於反覆起動得失值計算裝置和分配裝置直至全部分配對象分配完為止。
36.權利要求35中所述資源分配設備，其特徵是還包含如下結構，即推斷裝置，對應分配的分配對象與各資源元素的組合，通過計算其總和值的推斷值，來推斷在程序中分配各資源的資源元素時應分配的分配對象已定義的全部定義命令和使用的全部使用命令的執行周期和/或代碼大小的總和值達到什麼程度；資源元素單復判斷裝置，將每一資源元素的推斷結果即推斷值加以比較，判斷推斷值為最小的資源元素是一個還是多個，所述分配裝置，當判定為一個時就將推斷值為最小的資源元素分配給應分配的分配對象，當判定為多個時就將得失值為最大的資源元素分配給應分配的分配對象。
37.權利要求36中所述資源分配設備，其特徵是所述推斷裝置包含如下結構，即命令模式輸出部，對程序中的該分配對象的全部定義命令和使用命令輸出使用機器語言命令的命令格式表示程序中的分配對象的定義命令和使用命令的信息即命令模式；成本存貯部，與由命令模式輸出部輸出得的命令模式對應地分別存貯表示當在機器語言命令的各操作數中使用各資源的資源元素時的該定義命令和使用命令的執行周期和/或代碼大小的成本；成本總和部，取出與由成本存貯部輸出的命令模式對應的成本，對取出的成本按每一資源元素進行求和計算，並將求和的總和值作為推斷值。
38.用於將高級語言編寫的程序翻譯成機器語言程序的編譯程序，將寄存器、存貯器等硬體即資源的資源元素分配給用程式語言描述的程序中的變量與生存區間的組合即分配對象的資源分配設備，其特徵是包含如下結構，即分配對象保持裝置，與優先級對應地保持程序中的分配對象；第一資源元素分配裝置，從上述分配對象保持裝置中取出優先級最高的分配對象，並將某個資源元素分配給優先級最高的分配對象。分配對象取出裝置，從上述分配對象保持裝置中取出相對於此前分配的分配對象的優先級具有下一級的優先級的分配對象；一次重疊分配對象檢測裝置，檢測生存區間與所述分配對象取出裝置取出的分配對象重疊的分配對象；資源元素檢測裝置，檢測已分配給上述一次重疊分配對象檢測裝置檢測的分配對象的資源元素；分配對象—資源元素檢測裝置，檢測已分配了與檢測的資源元素不同的資源元素的全部分配對象；增益側連續已分配分配對象判定裝置，判斷由分配對象—資源元素檢測裝置檢測的已分配的分配對象中生存區間與由分配對象取出裝置取出的分配對象連續的全部分配對象；第一得失值計算裝置，根據從判斷為連續的已分配的分配對象到由分配對象取出裝置取出的分配對象的生存區間的長短，對分配給判定生存區間連續的分配對象的所有資源元素，計算表示已分配給分配對象的資源元素對現在要分配的分配對象適合到何種程度的值即得失值；累計裝置，對由分配對象—資源元素檢測裝置判定的各資源元素累計計算的得失值；第二資源分配裝置，將由累計裝置累計的累計值為最大的資源元素分配給由分配對象取出裝置取出的分配對象；控制裝置，反覆起動所述分配對象取出裝置直至全部分配對象分配完為止。
39.權利要求38中所述資源分配設備，其特徵是還包含如下結構，即第一非重疊非連續已分配分配對象判定裝置，判斷由分配對象—資源元素檢測裝置檢測的已分配的分配對象中生存區間與分配對象取出裝置取出的分配對象不連續並且生存區間不重疊的分配對象；增益一側連續未分配分配對象檢測裝置，檢測生存區間與由第一非重疊非連續分配畢分配對象判定裝置判定的已分配的分配對象的生存區間重疊的未分配的分配對象，並且生存區間與由分配對象取出裝置取出的分配對象連續的分配對象；第二得失值計算裝置，根據從由增益一側連續未分配分配對象檢測裝置檢測的未分配的分配對象到分配對象取出裝置取出的分配對象的生存區間的長短，計算分配給由第一非重疊非連續已分配分配對象判定裝置判定的已分配的分配對象的資源元素的得失值；第一減法裝置，從上述累計裝置累計的該資源元素的得失值中減去由第二得失值計算裝置計算出的得失值，上述第二分配裝置將由第一減法裝置減掉得失值後的得失值為最大的資源元素分配給分配對象取出裝置取出的分配對象。
40.權利要求39中所述資源分配設備，其特徵是還包含如下結構，即重疊一側連續已分配分配對象判定裝置，判斷由分配對象—資源元素檢測裝置檢測的已分配的分配對象中，生存區間與由一次重疊分配對象檢測裝置檢測的分配對象連續的分配對象；第三得失值計算裝置，根據從由重疊一側連續已分配分配對象判定裝置判定的已分配的分配對象到由一次重疊分配對象檢測裝置檢測的分配對象的生存區間的長短，計算分配給由重疊一側連續已分配的分配對象判定裝置判定的已分配的分配對象的資源元素的得失值；第二減法裝置，從由上述累計裝置累計的該資源元素的累計值中減去由第三得失值計算裝置計算的得失值，上述第二分配裝置將由第二減法裝置減去得失值後的累計值為最大的資源元素分配給分配對象取出裝置取出的分配對象。
41.權利要求40中所述資源分配設備，其特徵是還包含如下結構，即第二非重疊非連續已分配的分配對象判定裝置，判斷由分配對象—資源元素檢測裝置檢測的已分配的分配對象中，生存區間與由一次重疊分配對象檢測裝置檢測的分配對象不連續並且生存區間不重疊的分配對象；重疊一側連續未分配分配對象判定裝置，判定生存區間與由第二非重疊非連續已分配的分配對象判定裝置判定的已分配的分配對象的生存區間重疊的未分配的分配對象並且生存區間與由一次重疊分配對象檢測裝置檢測的分配對象連續的分配對象；第四得失值計算裝置，根據從由重疊一側連續未分配分配對象判定裝置判定的分配對象到由一次重疊分配對象檢測裝置所檢測的分配對象的生存區間的長短，計算分配給由第二非重疊非連續已分配的分配對象判定裝置判定的已分配的分配對象的資源元素的得失值；加法裝置，將由上述累計裝置累計的關於該資源元素的累計值與由第四得失值計算裝置計算的得失值進行加法運算；上述第二分配裝置將由第二加法裝置將得失值加進後的累計值為最大的資源元素分配給由分配對象取出裝置取出的分配對象。
全文摘要
資源分配設備生成變量和該變量的生存區間的組合即分配對象，對每一分配對象分別求生存區間重疊的分配對象和存在資源繼承關係的分配對象，並計算分配的優先級。然後，分配資源元素確定部從優先級高的分配對象起對各分配對象分配可分配的資源元素時，計算在程序中分配對象的使用場所所花費的成本和具有資源繼承關係的分配對象將目標代碼中傳輸命令的減少程度定量化的增益值，將使用成本最少並且增益值最大的資源元素分配給分配對象。
文檔編號G06F9/45GK1138173SQ96101898
公開日1996年12月18日 申請日期1996年3月13日 優先權日1995年3月16日
發明者田中旭, 佐山旬子, 湯川博司, 小谷謙介 申請人:松下電器產業株式會社