一種Java虛擬機的位置無關代碼生成方法
2023-05-23 17:02:21
專利名稱：一種Java虛擬機的位置無關代碼生成方法
技術領域：
本發明屬於Java虛擬機技術領域，具體涉及一種Java虛擬機的位置無關代碼生成方法。
背景技術：
如今，物聯網、移動計算等技術的飛速發展和硬體製造成本的降低使嵌入式設備在人們的日常生活中越來越重要。以Android為代表的嵌入式作業系統進一步推動了嵌入式設備在機頂盒、平板電腦、智慧型手機以及車載控制等行業的大規模應用，並導致出現了數量眾多，功能各異的應用程式。應用程式的性能直接關係到用戶體驗，決定著相應產品的市場控制力，也影響著技術發展的方向和進程。因此，提升程序的性能，特別是運行在嵌入式
設備上的應用程式的性能，變得越來越迫切而重要。可執行代碼緩存復用技術是一種常用的提升程序性能的方法。通過緩存即時編譯器等生成的可執行代碼至文件並在運行時復用這些代碼，該方法可降低或消除即時編譯系統的檢測與編譯延時，從而提升虛擬機執行效率。代碼緩存復用技術的關鍵是消除可執行代碼中的位置依賴從而確保可執行代碼的位置無關性。這需要編譯器在編譯方法時按特定的策略和代碼存儲格式完成可指令代碼的生成工作。這些策略被稱為位置無關代碼生成方法，而代碼存儲格式則稱為代碼布局方式。現有的位置依賴消除方法是使用符號表在編譯過程中，編譯器從代碼中的位置相關處提取所依賴的符號信息，並計算各符號相對於程序地址空間中某一全局固定位置的地址偏移；符號及其偏移被存儲在統一的符號表中，符號表及其描述信息與代碼一起存儲至文件系統。該方法的實質是將位置依賴的直接引用替換為間接引用，將代碼中位置相關點的地址綁定操作推遲到運行時完成。因該方法必須配合專門的動態連結器和連結過程，增加了程序執行等待時間和即時編譯器的實現難度；維護符號表、計算符號偏移也需很大開銷，所以適用靜態編譯器卻不適宜於即時編譯器系統，更不適用嵌入式平臺。嵌入式平臺的處理器能力相對較弱，內存等硬體資源有限且多數為電池驅動，因此，為在嵌入式平臺上更高效地緩存復用代碼，必須設計新的針對嵌入式系統這些特徵設計的位置無關代碼生成方法和代碼布局方式。
發明內容
本發明的目的是提供一種高效、且輕量級的位置無關代碼生成方法，並在Android作業系統內置虛擬機Dalvik上將其實現，為代碼緩存復用等更多優化技術提供基本支持，從而提聞程序性能。本發明首先調研了 Dalvik虛擬機生成的可執行代碼中的位置相關性，並分析總結了這些相關性對可執行代碼的影響；然後，針對可執行代碼中不同種類的位置依賴，分別提出了消除依賴的方法，並實現了相應的代碼生成器。其中採用對象引用即時解析和按需解析技術，取代傳統的基於符號表和連結器的解析技術，尤其適合嵌入式平臺。調研結果顯示，虛擬機的即時編譯器生成的可執行代碼中主要存在以下位置依賴信息
I、分支跳轉目標位置。當分支指令的目標地址為絕對尋址時，該指令就是位置相關的。2、函數位置，即虛擬機函數的入口地址。當Java程序在執行過程中需調用非Java語言編寫函數時，調用指令依賴函數具體地址。3、數據位置，即指令的操作數。可執行代碼中的數據位置依賴主要是指令的操作數，它們包括Java類對象引用、實例的引用、數組引用以及字符串常量的引用等。這些對象的虛擬機內部表示為結構體，因此，其引用實質上是指向特定結構體的指針。它可能以寄存器中的全局變量或編譯器為簡便指令操作而嵌入指令流中的立即數形式出現。4、異常處理器位置。異常處理功能因其實現差別，也可能使代碼位置相關。例如，當定位異常表中的Try、Catch塊使用絕對尋址時，跳轉指令依賴異常處理器目標地址。本發明提供的位置無關代碼生成方法，主要目標是消除上述四種依賴。具體說來， 本發明使用基於PC寄存器的相對尋址和特殊代碼格式布局消除分支跳轉目標位置依
賴和異常處理器位置依賴；使用簡單函數表消除函數位置依賴；將依賴數據和對該數據的解析過程嵌入指令流中的運行時按需解析和即時解析技術，消除數據位置依賴。本發明設計的位置無關代碼生成方法，包括兩個方面針對不同位置依賴的消除方法和整體代碼布局方法。本發明的位置依賴消除方法分別針對上述四種位置依賴信息，設計了位置相關性消除策略。對於分支跳轉目標位置依賴和異常處理器位置依賴，本方法採用基於PC寄存器的相對尋址策略與整體代碼內存布局一起實現消除。圖I示例了整體代碼內存布局，該內存布局演示了對分支指令跳轉目標的依賴消除其中的Idr r2, [pc, #-256]和add pc,pc, r2指令即是以PC為基址寄存器，在常量池中存儲跳轉目標，使代碼避免絕對地址跳轉，從而消除位置中的依賴。對於函數位置依賴，本發明使用簡單函數表將函數調用轉換為間接調用。首先，本發明在線程的本地存儲結構TLS (Thread Local Storage)中存儲函數表，並在表中存儲各函數在當前虛擬機實例的地址，然後在各個方法的棧幀中存放指向該結構體的指針。在生成代碼時，編譯器從棧幀中取得該TLS結構的指針；然後藉助函數名查詢其在函數表中的位置，該位置是相對於TLS結構首地址的偏移；最後生成代碼。由於在不同虛擬機實例中雖然相同函數的絕對地址不同，但是相對於函數表的偏移地址卻是相同的，因此對函數地址的依賴消除解決了位置無關性代碼中的一個難點。本方法一般適用於對虛擬機內部函數的調用，此類函數需要在編譯器中明確的指出，並不適用於普通的Java函數。圖2展示了該種方法，圖中下框所示代碼片段即為即時編譯器使用該策略生成的代碼。其中tlsOffset是TLS結構指針在棧幀中的位置偏移，offset是被調用函數在TLS結構中的位置偏移。通過三元組<SP, tlsOffset, offset〉可以唯一確定任意函數,而該三元組中不包含任何位置依賴。因此，使用圖2所示策略可成功消除函數位置依賴。對於數據位置依賴，本發明採用即時解析方法消除。本發明首先在指令流中為這些引用預留出位置(初始化為空值)，然後生成引用解析邏輯代碼以在運行時對這些預留位置的值進行解析回填。其中，未被回填的代碼被稱為原始代碼，它們是位置無關的；回填後的代碼是原始碼的一份拷貝，它的引用位置與虛擬機的具體實例相關。圖3是本發明使用該所設計的數據位置依賴消除策略過程。該策略將代碼依賴的引用數據嵌入指令流中，並提供一條快速執行路徑(對應圖3中實線)和一條慢速執行路徑(對應圖3中虛線)。嵌入指令中的引用初始值為空值，其實際值由慢速路徑在運行時解析並回填。在慢速路徑中，輔助函數負責完成引用的解析回填操作以及相關的字節碼功能。按圖3所示過程，通常情況下，慢速路徑在程序的生命周期中最多只執行一次，執行完後獲得的回填代碼再次被執行時將選擇快速路徑。與即時編譯的基本原理類似，該方法實現了對所依賴數據引用的按需解析(On-Demand Resolution)與即時解析(Just-In-Time Resolution):如果代碼中某些片段不會被執行到，這些片段中的引用就無需解析，而對於會執行到的代碼片段，其中的引用在執行之時完成解析並在解析後立刻執行。與傳統 的符號表和動態連結的方式相比，按需解析和即時解析技術無需專門的連結器，降低了框架的實現難度；無需連結過程，省去因鏈式解析帶來的執行延時。因此，按需解析和即時解析支持很適於但也不限於嵌入式Java虛擬機平臺。在代碼布局設計方法中，本發明結合位置無關代碼生成策略，對代碼內存空間做了劃分，圖I是代碼空間布局的具體結構。本方法需要將位置無關代碼存儲空間劃分三個區間常量池、代碼區和異常信息表區。常量池區存儲代碼使用常量用於PC相對尋址的偏移值(用於消除分支跳轉目標位置依賴和異常處理器位置依賴)，常量如類和方法索引等以及指令立即數等；代碼區存儲所有位置無關可執行代碼，該區中涉及分支跳轉的指令需藉助常量池中存儲的相對尋址偏移值來保證代碼的位置無關性；異常信息表區用於保存各異常處理try塊和catch塊位置，其存儲的值為Java異常處理器相對於當前PC寄存器值的偏移值。這些偏移值用以保證代碼區中異常處理跳轉目標指令的位置無關性。本發明的有益效果是(I)本發明設計了一種全新的位置無關代碼生成方法，適用於但不限於嵌入式平臺。(2)本發明探索了動態生成代碼的位置無關性，為其他與代碼位置依賴相關的優化技術提供參考。(3)本發明所設計的位置無關代碼生成方法的位置依賴消除策略對其他託管語言運行時環境實現代碼位置無關化有引導意義。(4)本發明提出的引用按需解析與即時解析技術在保持虛擬機即時編譯器生成位置無關代碼時開銷較低的情況下，獲得較高效率的代碼。
圖I為本發明設計的位置無關代碼存儲格式。圖2為基於簡單函數表的位置依賴消除。圖3為用按需解析與即時解析技術消除數據位置依賴過程。圖4為輔助函數實現模板。圖5為const-class的位置無關代碼生成算法實現示例。
具體實施例方式在具體實施過程中，本發明主要包括兩部分內容策略算法實施與輔助函數實現。前者主要包括算法實現與內存布局。對於算法，本發明以Dalvik字節碼為例，展示基於模板的算法實施過程；對於內存布局，實施時只需藉助虛擬機即時編譯器的代碼管理器或內存管理器即可簡單實現，不再贅述。輔助函數的效率關係到解析過程的效率，進而影響整個程序的執行時間長短。本發明以ARM彙編語言為基礎實現輔助函數，以確保輔助函數有較高的效率。下面按代碼編譯過程的先後順序描述具體實施過程，由代碼生成方法所需要數據準備階段、各生成算法的實現以及最終代碼生成構成
步驟一、數據準備
該步驟目的在於為生成位置無關代碼準備必需的數據結構。I.在方法入口(Prologue)代碼的生成邏輯中添加棧幀TLS結構體指針，為代碼在運行時獲取函數表基址做準備。2.實現輔助函數。本發明以彙編語言為基礎實現輔助函數。由於輔助函數通常有結構上的相似性，因而本發明為輔助函數提取了可復用模板，以降低實現難度。圖4展示了該模板，實現輔助函數時，只需替換其中的問號、星號、虛擬機函數以及相應的異常處
理邏輯即可。總體處理邏輯如下首先在調用外部函數之前需要保存好當前執行狀態的上下文，主要包括寄存器的狀態；然後檢查當前執行是否觸發了異常，如果存在異常的話就跳轉到相應的異常處理邏輯；如果當前沒有異常發生，則需要為需要調用的函數準備好參數，之後直接調用該函數即可；在函數調用完成之後需要恢復原先的上下文狀態以及處理返回值；最後在在輔助函數返回之前仍需要對異常進行判斷和處理。3.在TLS結構中申請簡單函數表空間，並在線程創建時用輔助函數地址按既定順序填充各表項，為代碼在運行時獲取函數地址做準備。步驟二、各生成算法的實現
經過步驟一，編譯前所需數據已經準備完成。編譯過程中，不同的消除策略也需要不同的數據，這些數據放置在常量池中與生成代碼處在相對位置不變的內存空間。實現生成算法時，首先找到原生成器針對不同字節碼的實現；然後，按圖1、2、3所示策略重寫代碼生成邏輯。以Dalvik的字節碼const-class為例，其依賴類型為數據依賴。依據圖3所示的過程，const-class的生成邏輯如圖5所示。圖5中算法邏輯使用按需與即時解析技術，將代碼依賴的引用數據嵌入指令流中(第8行),並提供快速執行路徑(由第1-2-4行組成)和慢速執行路徑(由第1-2-3-5-6-7行構成)。const-class指令在編譯過程中主要需要解決的依賴類型為數據依賴。圖5中第8行指令為引用的地址預留了空間，第一行指令首先讀取該預留空間中的值，第二行判斷該值，如果是第一次執行，由於預留空間的默認值為NULL因此控制流跳轉到第五行開始執行即時解析的代碼，執行完後會進行解析地址的回填，這樣第二次執行的時候第三行代碼會判斷出該預留空間已經被回填，因此會直接跳轉到第10行返回該值。步驟三、代碼生成
經過步驟一、二，本發明為即時編譯器添加了新的代碼生成器。該生成器使用本文所述代碼生成方法，為Java方法即時編譯生成位置無關代碼。
權利要求
1. 一種Java虛擬機的位置無關代碼生成方法，其特徵在於包括兩個方面針對不同位置依賴的消除方法和整體代碼布局方法；其中， 1、所述針對不同位置依賴的消除方法，包括 (1)對於分支跳轉目標位置依賴和異常處理器位置依賴，採用基於PC寄存器的相對尋址策略與整體代碼內存布局一起實現消除，該方法主要適用於Java代碼之間的跳轉關係； (2)對於函數位置依賴，使用簡單函數表將對函數的直接調用轉換為間接調用；首先，在線程的本地存儲結構TLS中存儲函數表，並在表中存儲各函數在當前虛擬機實例的地址，然後在各個方法的棧幀中存放指向該結構體的指針；在生成代碼時，編譯器從棧幀中取得該TLS結構的指針；然後藉助函數名查詢其在函數表中的位置，該位置是相對於TLS結構首地址的偏移；最後生成代碼；由於在不同虛擬機實例中雖然相同函數的絕對地址不同，但是相對於函數表的偏移地址卻是相同的，因此對函數地址的依賴消除解決了位置無關性代碼中的一個難點；本方法一般適用於對虛擬機內部函數的調用，此類函數需要在編譯器中明確的指出，並不適用於普通的Java函數； (3)對於數據位置依賴，採用即時解析方法消除；在Java代碼的執行過程中需要根據一些符號對相應的地址進行解析，然而在代碼編譯的時候由於代碼還未實際執行，因此無法獲知此類地址，同時此類解析操作通常比較費時並且每次解析得到的地址都是固定的；本發明採用即時解析和回填的方式對此類位置依賴進行消除和優化，方法如下首先在指令流中為這些引用預留出位置，然後生成引用解析邏輯代碼以在運行時對這些預留位置的值進行解析回填；其中，未被回填的代碼被稱為原始代碼，它們是位置無關的；回填後的代碼是原始碼的一份拷貝，它的引用位置與虛擬機的具體實例相關，解析出來的位置被回填後，下次執行時將不再需要再次執行解析代碼而是從回填的地址中直接讀取即可得到所需要的位置地址； 2、所述整體代碼布局方法，結合位置無關代碼生成策略，對代碼內存空間做了劃分，SP將位置無關代碼存儲空間劃分三個區間常量池、代碼區和異常信息表區；常量池區存儲代碼使用常量用於PC相對尋址的偏移值，可消除分支跳轉目標位置依賴和異常處理器位置依賴；代碼區存儲所有位置無關可執行代碼，該區中涉及分支跳轉的指令需藉助常量池中存儲的相對尋址偏移值來保證代碼的位置無關性；異常信息表區用於保存各異常處理try塊和catch塊位置，其存儲的值為Java異常處理器相對於當前PC寄存器值的偏移值，這些偏移值用以保證代碼區中異常處理跳轉目標指令的位置無關性。
全文摘要
本發明屬於Java虛擬機技術領域，具體為一種Java虛擬機的位置無關代碼生成方法。本發明針對分支跳轉目標位置依賴、異常處理器位置依賴、函數位置依賴和數據位置依賴，設計了針對代碼中不同種類的位置依賴消除策略，使虛擬機的即時編譯器生成的可執行代碼不含位置依賴。這些生成的位置無關代碼可進而作他用，如將其緩存並復用以提升虛擬機執行效率等。
文檔編號G06F9/44GK102819435SQ20121026126
公開日2012年12月12日 申請日期2012年7月26日 優先權日2012年7月26日
發明者楊珉, 張源, 周波 申請人:復旦大學