（計算機軟件與理論專業(yè)論文）注解信息制導(dǎo)的動態(tài)二進制翻譯器內(nèi)存優(yōu)化.pdf

論文獨創(chuàng)性聲明 本論文是我個人在導(dǎo)師指導(dǎo)下進行的研究工作及取得的研究成果。論文中除 了特別加以標注和致謝的地方外，不包含其他人或其它機構(gòu)已經(jīng)發(fā)表或撰寫過的 研究成果。其他同志對本研究的啟發(fā)和所做的貢獻均已在論文中作了明確的聲明 并表示了謝意。 作者簽名：縫墊盤 同期： 論文使用授權(quán)聲明 本人完全了解復(fù)旦大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留 送交論文的復(fù)印件，允許論文被查閱和借閱；學(xué)?？梢怨颊撐牡娜炕虿糠謨?nèi) 容，可以采用影印、縮印或其它復(fù)制手段保存論文。保密的論文在解密后遵守此 璇。作者簽名：盈醯翮簽名：重芏莖趙嗍貍：紐作者簽名：壟鑫壑盤導(dǎo)師簽名：鬈芏莖理同期：2 丑：亟：! 摘要 關(guān)鍵字：注解信息，動態(tài)二進制翻譯器，內(nèi)存優(yōu)化，寄存器化 動態(tài)二進制翻譯器能夠在運行時將針對源體系結(jié)構(gòu)編譯的軟件動態(tài)翻譯成 目標體系結(jié)構(gòu)的軟件并使之運行。盡管隨著新的體系結(jié)構(gòu)不斷涌現(xiàn)，動態(tài)二進制 翻譯器技術(shù)越來越流行，但是動態(tài)二進制翻譯器往往會受限于在翻譯碼上可執(zhí)行 的優(yōu)化方法，無法使翻譯碼的執(zhí)行性能同移植程序的執(zhí)行性能相媲美。因為源可 執(zhí)行文件中只有二進制代碼，缺乏源程序高級語言的信息，麗且動態(tài)二進制翻譯 器在翻譯過程中需要保證翻譯碼同源碼在二進制級別上的兼容性，因此動態(tài)二進 制翻譯器往往無法采用一些在靜態(tài)編譯器中常用的代碼優(yōu)化方法。另外，為了保 證在異常發(fā)生的情況下能夠恢復(fù)出一個精確的體系結(jié)構(gòu)狀態(tài)，翻譯碼中的指令調(diào) 度被限制在個相對較小的范圍內(nèi)，更進一步的限制了動態(tài)二進制翻譯器的翻譯 碼優(yōu)化。本文則從一個創(chuàng)新的角度提出了一種解決上述問題的方法。該方法在靜 態(tài)編譯器中收集那些對動態(tài)二進制翻譯器優(yōu)化有幫助的信息，并在可執(zhí)行文件中 開辟一個獨立的注解信息段，將這些優(yōu)化相關(guān)的信息以一定的格式寫入其中。在 動態(tài)二進制翻譯階段，動態(tài)二進制翻譯器就可以利用注解信息對翻譯碼迸一步優(yōu) 化，提高翻譯碼的質(zhì)量。本文在g c c4 0 和i a - 3 2e x e c u t i o nl a y e r 上實現(xiàn)了注解 信息制導(dǎo)的動態(tài)二進制翻譯框架，并且選擇在可執(zhí)行文件中生成內(nèi)存優(yōu)化相關(guān)的 注解信息。基于注解信息，本文在動態(tài)二進制翻譯器隊3 2e l 中嘗試了包括寄 存器化，放寬m e m o r yo r d 嘶n g 的限制，加強訪存指令的地址消岐和放寬精確異 常處理等內(nèi)存優(yōu)化。本文選擇s p e c 2 0 0 0 為基準測試程序，實驗結(jié)果表明注解信 息制導(dǎo)的動態(tài)二進制翻譯器中的內(nèi)存優(yōu)化能夠在引入相對較小的額外開銷下獲 得十分不錯的性能提升。實驗數(shù)據(jù)顯示優(yōu)化后，s p e c 印2 0 0 0 的整體性能提高了 1 5 0 3 ，而s p e c i n t 2 0 0 0 的整體性能則提高了1 2 1 。對于某些特定的基準測試 程序，性能提升甚至達到了3 7 0 9 。 3 a b s t m e t a b s t r a c t k e y w o r d s ：m e t a d a t a ，d y n a m i cb i n a r yt r a n s l a t o r , m e m o r yo p t i m i z a t i o n ， r e g i s t e r i z a t i o n d y n a m i cb i n a r yt r a n s l a t o ro f f e r ss o l u t i o n sf o rt r a n s l a t i n ga n dr u n n i n gs o u r c e a r c h i t e c t u r eb i n a r i e so nt a r g e ta r c h i t e c t u r ea tr u n t i m e r e g a r d l e s so f i t sg r o w i n g p o p u l a r i t ya sn e w a r c h i t e c t u r e sk e 印e m e r g i n g ，p r a c t i c a id y n a m i cb i n a r yt r a n s l a t o r s u s u a l l ys u f f e rf r o mt h el i m i t e do p t i m i z a t i o n sp e r f o r m e dw h e ng e n e r a t i n gt r a n s l a t e d c o d e t h ep e r f o r m a n c eo f t r a n s l a t e dc o d ei sp o o r l yc o m p a r e dt ot h a to f t h en a t i v e c o d e s i n c et h ee x e c u t a b l ef i l e so n l yc o n t a i np u r eb i n a r i e sa n du s u a l l yl a c kt h eu s e f u l i n f o r m a t i o na v a i l a b l ei nh i 曲l e v e ls o u r c ec o d e ，ad y n a m i cb i n a r yt r a n s l a t o ri sn o t a b l et op e r f o r mt y p i c a lo p t i m i z a t i o n st h a ta r ep o p u l a ri nas m i l ec o m p i l e r i na d d i t i o n , b i n a r yl e v e lc o m p a t i b i l i t yh a st ob ek e p td u r i n gt h ep r o c e s s i n go f b i n a r yt r a n s l a t i o n , w h i c hf u r t h e rp r e v e n t sad y n a m i cb i n a r yt r a n s l a t o rf r o ma g g r e s s i v eo p t i m i z a t i o u s f u r t h e r m o r e ，i no r d e rt oe n s u r eap r e c i c o n t e x tr e c o v e r yw h e ne x c e p t i o nh a p p e n si n t h et r a n s l a t e dc o d e ，i n s t r u c t i o ns c h e d u l i n gh a st ob ec o n s e r v a t i v e l yl i m i t e dt oas m a l l w i n d o wi nad y n a m i cb i n a r yt r a n s l a t o r t oa d d r e s st h e s ei s s u e s ，t h i sp a p e rp r o p o s e s a ni n n o v a t i v em e t h o do f p a s s i n gp e r f o r m a n c ec r i t i c a li n f o r m a t i o nf r o ms t a t i c c o m p i l a t i o nt od y n a m i cb i n a r yt r a n s l a t i o n t h ei n f o r m a t i o ni sc o l l e c t e dd u r i n gs t a t i c c o m p i l a t i o na n ds t o r e du s i n gap r e d e f i n e df o r m a ti nas e p a r a t es e c t i o nc a l l e dm e t a d a t a s e c t i o ni nt h ef i n a le x e c u t a b l ef i l e i nb i n a r yt r a n s l a t i o np h a s e ，ad y n a m i cb i n a r y t r a n s l a t o rc a nu t i l i z et h em e m d a mt op e r f o r ma g g r e s s i v eo p t i m i z a t i o n sa n di m p r o v e t h ep e r f o r m a n c eo f t h et r a n s l a t e dc o d e w eh a v ei m p l e m e n t e dag e n e r a la n d e x t e n s i b l ef r a m e w o r ko f m e t a d a t ad r i v e no p t i m i z a t i o u si ng c c4 0a n di a - 3 2 e x e c u t i o nl a y e r , a n ds e l e c t e dm e t a d a mr e l a t e dt om e m o r yo p t i m i z a t i o na so u rt a r g e t t h em e t a d a t ae n a b l e si a - 3 2e lt op e r f o r mm e m o r yo p t i m i z a t i o n ss u c ha s r e g i s t e r i z a t i o n ，m e m o r yo r d e r i n gr e l a x a t i o n , m e m o r yd i s a m b i g u a t i o ne n h a n c e m e n t a n dp r e c i s ee x c e p t i o ns e m a n t i c sr e l a x a t i o n w cc h o s es p e c 2 0 0 0t ob eo u r b e n c h m a r ka n de x p e r i m e n t ss h o w e dap o s i t i v ep e r f o r m a n c ei m p r o v e m e n tw h i l e i n t r o d u c i n gm o d e s to v e r h e a d t h eo v e r a l lp e r f o r m a n c ei m p r o v e m e n tr e a c h e s1 5 0 3 f o rs p e c f p 2 0 0 0a n d1 2 1 f o rs p e c i n t 2 0 0 0 f o rs o m es p e c i f i cb e n c h m a r k , t h e p e r f o r m a n c ei m p r o v e m e n ti sg ! v e nu p t o3 7 0 9 4 簡介 1 筒奔 動態(tài)二進制翻譯技術(shù)是一種即時編譯技術(shù) 1 1 1 9 ，它將針對源體系結(jié)構(gòu)編譯 生成的二進制碼( 源二進制碼) 動態(tài)翻譯成可以在目標體系結(jié)構(gòu)上運行的二進制 碼( 翻譯碼) 。動態(tài)二進制翻譯技術(shù)主要被用來保證目標體系結(jié)構(gòu)對源體系結(jié)構(gòu) 的向后兼容。利用動態(tài)二進制翻譯技術(shù)，所有源軟件無需移植就可以直接在與源 體系結(jié)構(gòu)不兼容的目標機器上運行。 隨著計算機體系結(jié)構(gòu)的不斷推陳出新，目前主流的體系結(jié)構(gòu)肯定會被新的體 系結(jié)構(gòu)所替代。因此當前編譯生成的軟件并不一定能夠在將來的主流機器上執(zhí) 行。即便將來的體系結(jié)構(gòu)兼容目前的主流體系結(jié)構(gòu)，其微體系結(jié)構(gòu)肯定會有較大 的改動和變化。因此，針對目前的微體系結(jié)構(gòu)進行優(yōu)化編譯的軟件在將來的體系 結(jié)構(gòu)上的執(zhí)行性能勢必大打折扣。為了能夠提高軟件的執(zhí)行性能，需要將軟件的 源代碼針對目標體系結(jié)構(gòu)重新編譯優(yōu)化并進行調(diào)試。但是源代碼中往往會有大量 平臺相關(guān)的特性存在，例如將一個3 2 位的軟件編譯成6 4 位的軟件，源代碼中有 效數(shù)據(jù)的長度變化將會為重新編譯和優(yōu)化帶來不少麻煩，因此重新編譯和優(yōu)化源 代碼的移植方法將會十分的費時費力。利用動態(tài)二進制翻譯技術(shù)，就可以針對目 標體系結(jié)構(gòu)實現(xiàn)一個源體系結(jié)構(gòu)的模擬器，針對源體系結(jié)構(gòu)編譯優(yōu)化的軟件就可 以通過該模擬器直接運行在目標機器上，從而避免了對源代碼進行重新編譯和優(yōu) 化的麻煩。 1 1 動態(tài)二進制翻譯器的基本框架 源二進制程序在動態(tài)二進制翻譯器上的執(zhí)行往往分為兩個基本階段：翻譯階 段和執(zhí)行階段。在翻譯階段。動態(tài)二進制翻譯器對源二進制碼進行解碼之后將其 翻譯為目標體系結(jié)構(gòu)上的二進制碼，即翻譯碼。翻譯完畢后，動態(tài)二進制翻譯器 便切換到翻譯碼中進入執(zhí)行階段。當程序在翻譯碼中運行至尚未翻譯的代碼片段 時，便會切換回動態(tài)二進制翻譯器從該點開始繼續(xù)翻譯源二進制碼。這樣源二進 制程序就可以在目標機上執(zhí)行。動態(tài)二進制翻譯器的基本框架如圖l - 1 所示。 5 簡介 圖1 - 1 ：動態(tài)二進制翻譯器框架 動態(tài)二進制翻譯器的翻譯往往會包含三個階段：解釋執(zhí)行階段，普通翻譯階 段，優(yōu)化翻譯階段。當源二進制碼首次執(zhí)行時，動態(tài)二進制翻譯器會對其進行解 釋執(zhí)行。解釋執(zhí)行將不會保存任何翻譯結(jié)果，如果該源二進制碼再次被執(zhí)行時， 它將再次被翻譯。為了避免重復(fù)翻譯帶來的開銷，當源二進制碼的執(zhí)行次數(shù)達到 某一閥值時，便會進入普通翻譯階段。此時，動態(tài)二進制翻譯器對該源二迸制碼 進行翻譯，并將生成的翻譯碼保存在內(nèi)存中。如此，當程序再次執(zhí)行到該源二進 制碼時，就可以直接執(zhí)行相對應(yīng)的翻譯碼，而無需重新翻譯。由于普通翻譯階段 需要翻譯的源二進制碼往往很多，因此動態(tài)二進制翻譯器會采用簡單快速的翻譯 算法，并且在翻譯碼中加入一些額外的代碼來收集該翻譯碼的動態(tài)執(zhí)行行為信 息，該翻譯碼被稱為普通翻譯碼。對于那些頻繁執(zhí)行的關(guān)鍵代碼塊，當其執(zhí)行次 數(shù)超過某一個更高的閥值時，它將被動態(tài)二進制翻譯器再次翻譯，并且進入優(yōu)化 翻譯階段。在優(yōu)化翻譯階段，動態(tài)二進制翻譯器將花費更多的時間，采用更加復(fù) 雜的算法對翻譯碼進行優(yōu)化翻譯，以期得到更高質(zhì)量的翻譯碼。優(yōu)化翻譯階段生 成的翻譯碼被稱為優(yōu)化翻譯碼，其執(zhí)行效率遠遠高于普通翻譯階段生成的普通翻 譯碼。 動態(tài)二進制翻譯器在生成翻譯碼的時候，會將源二進制碼塊和翻譯碼塊的對 應(yīng)關(guān)系記錄在一張對應(yīng)表中，該表被稱為翻譯映射表。翻譯映射表中的每一項記 錄了一對源二進制碼塊的首地址和與其相對應(yīng)的翻譯碼塊的首地址。當程序執(zhí)行 完一個翻譯碼塊后，會根據(jù)當前源二進制碼的i p ( i n s t r u c t i o np o i n t e r ) 地址在翻 譯映射表中尋找其相應(yīng)的翻譯碼。如果命中，那么就可以從翻譯映射表中讀取后 6 簡介 繼翻譯碼的入口地址，直接跳轉(zhuǎn)到該翻譯碼繼續(xù)執(zhí)行。若沒有在翻譯映射表中找 到對應(yīng)項，說明該源二進制碼尚未被翻譯，那么動態(tài)二進制翻譯器就會從該皿 地址開始翻譯源二進制碼。在動態(tài)二進制翻譯器和翻譯碼間進行上下文切換十分 費時，為了避免每執(zhí)行完一個翻譯碼塊就要查詢翻譯映射表，對于直接跳轉(zhuǎn)指令， 動態(tài)二進制翻譯器可做如下優(yōu)化。若某一翻譯碼塊a 的后繼翻譯碼塊b 已被生 成，動態(tài)二進制翻譯器便可在翻譯指令時將后繼翻譯碼塊b 的入口地址回填到 該翻譯碼塊a 末尾的跳轉(zhuǎn)指令的目標地址中，這樣，翻譯碼塊a 執(zhí)行完畢后， 就可通過該跳轉(zhuǎn)指令直接跳轉(zhuǎn)到后繼翻譯碼b ，而無需切換到動態(tài)二進制翻譯器 的上下文查詢翻譯映射表。當翻譯碼被更新，例如從普通翻譯碼被更新為優(yōu)化翻 譯碼，動態(tài)二進制翻譯器不僅需要更新翻譯映射表，還需要對所有該翻譯碼的前 驅(qū)翻譯碼中的跳轉(zhuǎn)指令的目標地址進行更新。 ， h， l ? j i l l 、 、 圖1 - 2 ：熱路徑的構(gòu)造 動態(tài)二進制翻譯器的普通翻譯往往是按照源二進制碼的基本塊為單位進行翻 譯的，而優(yōu)化翻譯通常會采取熱路徑的方式翻譯源二進制碼【1 h 2 5 。動態(tài)二進 制翻譯器會在普通翻譯碼中加入一些額外代碼來收集普通翻譯碼的動態(tài)執(zhí)行行 為信息。例如在普通翻譯碼中加入計數(shù)代碼統(tǒng)計該普通翻譯碼的執(zhí)行次數(shù)，從而 判斷該普通翻譯碼的執(zhí)行次數(shù)是否達到閥值?；蛘邽槠胀ǚg碼的條件跳轉(zhuǎn)指令 加入計數(shù)代碼統(tǒng)計該跳轉(zhuǎn)指令的跳轉(zhuǎn)次數(shù)。動態(tài)二進制翻譯器可以結(jié)合普通翻譯 碼的執(zhí)行次數(shù)和條件跳轉(zhuǎn)指令的跳轉(zhuǎn)次數(shù)推測該普通翻譯碼的后續(xù)翻譯碼，并可 以此為今后構(gòu)造熱路徑提供依據(jù)。如圖1 2 所示，動態(tài)二進制翻譯器在構(gòu)造熱路 徑時可以得到以下信息，翻譯碼塊a 跳轉(zhuǎn)到翻譯碼塊b 的頻率為7 0 ，翻譯碼 塊d 跳轉(zhuǎn)到a 的頻率為9 0 。根據(jù)以上信息，動態(tài)二進制翻譯器就會將翻譯碼 7 簡介 塊a ，b 和d 串聯(lián)起來，經(jīng)過代碼優(yōu)化后，構(gòu)成一個新的翻譯碼塊a ，即熱路 徑a 。然后更新翻譯映射表，將普通翻譯碼塊a ，b ，d 更新為熱路徑a 。最 后更新所有翻譯碼塊a 的前驅(qū)翻譯碼塊的跳轉(zhuǎn)指令，將熱路徑a 的地址回填到 這些跳轉(zhuǎn)指令的目標地址。這樣，今后當程序再次執(zhí)行到二進制碼a 的入口處， 就會直接執(zhí)行熱路徑a 了。 1 2 動態(tài)二進制翻譯器的特點和局限性 動態(tài)二進制翻譯器在各個領(lǐng)域被廣泛運用。動態(tài)二迸制翻譯器的一大好處是 能夠讓用戶在新的體系結(jié)構(gòu)上直接運行遺留體系結(jié)構(gòu)上的程序。當源體系結(jié)構(gòu)與 目標體系結(jié)構(gòu)相同時，動態(tài)二進制翻譯器能夠被用來動態(tài)優(yōu)化二進制程序【5 】， 或者為二進制程序提供安全的運行環(huán)境【1 2 】。動態(tài)二進制翻譯器還能被用于降低 硬件的復(fù)雜度和能耗【1 0 】，提供高性能的代碼分析和檢測工具 1 7 】。隨著基于二 進制代碼翻譯的應(yīng)用越來越多，越來越多的程序?qū)\行在動態(tài)二進制翻譯器 上，而動態(tài)二進制翻譯器也將會變得越來越普遍。 但是，動態(tài)二進制翻譯器常常由于翻譯碼的性能不佳而受人詬病。在那些對 c p u 要求較高的程序中，相比動態(tài)二進制翻譯器本身的執(zhí)行開銷，大部分的程 序執(zhí)行時間都花在了翻譯碼上，因此翻譯碼的性能對于整個程序的執(zhí)行性能尤為 關(guān)鍵。此外，除了提供不同體系結(jié)構(gòu)下程序的兼容性，動態(tài)二進制翻譯器還需要 發(fā)掘目標體系結(jié)構(gòu)的性能潛力。因此研究如何提高翻譯碼的執(zhí)行性能成了多年來 動態(tài)二進制翻譯器的研究重點【l 】【l1 1 9 2 0 】。 盡管如此，和直接在目標體系結(jié)構(gòu)上編譯的二進制碼相比，動態(tài)二進制翻譯 器生成的翻譯碼性能還是不能令人滿意。由于動態(tài)二進制翻譯器的輸入是源二進 制碼，它缺乏一些高級語言中才有的重要信息。而通常這些信息對于靜態(tài)編譯器 在編譯生成二進制碼時的優(yōu)化有很大的幫助。更進一步，動態(tài)二進制翻譯器也可 以被認為是對源體系結(jié)構(gòu)進行模擬的虛擬機，因此需要動態(tài)二進制翻譯器在翻譯 執(zhí)行的過程中保證翻譯碼和源二進制碼在二進制級別上的兼容性。這一要求不僅 添加了動態(tài)二進制翻譯器的翻譯限制，而且加劇了翻譯碼的優(yōu)化難度。例如二進 制級別的兼容性要求有：1 ) 每一條源指令的語義必須被翻譯指令精確模擬，2 ) 在翻譯碼的執(zhí)行過程中能夠保證源體系結(jié)構(gòu)的精確異常得到正確處理，3 ) 在翻 譯碼中按照源體系結(jié)構(gòu)的規(guī)范維持源二進制碼中訪存指令的訪問順序等。 鑒于動態(tài)二進制翻譯器的廣泛運用，程序在動態(tài)二進制翻譯器上運行的機會 將會越來越多。因此，本文認為在針對某一體系結(jié)構(gòu)編譯源代碼生成二進制碼的 時候，不僅需要考慮該二進制碼在該體系結(jié)構(gòu)上執(zhí)行的性能，而且需要考慮該二 進制碼今后在動態(tài)二進制翻譯器上的執(zhí)行性能【2 6 】。在靜態(tài)編譯源程序的時候加 3 簡介 入對動態(tài)二進制翻譯器的支持將能夠幫助二進制碼快速適應(yīng)動態(tài)二進制翻譯器 的執(zhí)行環(huán)境，并且通過動態(tài)二進制翻譯器被快速移植到新的體系結(jié)構(gòu)上，同時盡 可能降低程序的性能損失。因此，本文認為將原先獨立的兩個系統(tǒng)，靜態(tài)編譯器 系統(tǒng)和動態(tài)二進制翻譯器系統(tǒng)視為一個系統(tǒng)能夠從一個嶄新的角度來提高源二 進制碼在動態(tài)二進制翻譯器上的執(zhí)行性能。當然，這也要求在動態(tài)二進制翻譯器 中加入的注解信息具有通用性和體系結(jié)構(gòu)無關(guān)性，即注解信息能夠被不同體系結(jié) 構(gòu)的動態(tài)二進制翻譯器所利用。 另外，本文所提的方法還能夠幫助那些希望所開發(fā)的軟件能夠在不同平臺， 或者在將來的平臺上運行的軟件開發(fā)者。雖然他們希望看到自己的軟件運行在其 他的體系結(jié)構(gòu)上或者新的體系結(jié)構(gòu)上，但是他們往往缺乏足夠的人力資源或者其 他資源將軟件移植到其它體系結(jié)構(gòu)或平臺上，或者他們在等待新的體系結(jié)構(gòu)或平 臺趨于成熟。此時，如果動態(tài)二進制翻譯器能夠提供他們可觀的性能，那么動態(tài) 二進制翻譯技術(shù)對于他們而言將十分有吸引力。我們相信這些軟件開發(fā)者將很樂 意接受一個高效的，針對動態(tài)二進制翻譯器優(yōu)化的靜態(tài)編譯器。這個靜態(tài)編譯器 能夠編譯出帶有動態(tài)二進制翻譯器優(yōu)化相關(guān)的注解信息的二進制程序，幫助他們 的軟件在動態(tài)二進制翻譯器上獲得額外的性能提升。 同樣，我們的方法還能夠幫助提高那些遺留軟件在動態(tài)二進制翻譯器上的性 能。盡管該方法需要軟件開發(fā)者重新編譯他們的軟件，但是這并不會像軟件移植 那樣帶來額外的代碼修改，軟件測試和軟件驗證，更不會對軟件的質(zhì)量帶來任何 威脅。而且我們的方法可以被用來僅僅編譯那些核心的，性能關(guān)鍵的軟件模塊， 而無需重新編譯所有的源代碼，這樣可以進一步減少軟件重新編譯的開銷。因此 我們相信注解信息制導(dǎo)的動態(tài)二進制翻譯器優(yōu)化能夠幫助那些軟件開發(fā)者和那 些急需在新的體系結(jié)構(gòu)上改善性能的遺留軟件，具有相當不錯的應(yīng)用前景。 1 3 注解信息制導(dǎo)的動態(tài)二進制翻譯器優(yōu)化簡介 本文從一個創(chuàng)新的角度提出了在動態(tài)二進制翻譯器中進一步優(yōu)化翻譯碼的方 法。該方法收集源高級語言在靜態(tài)編譯過程中的有用信息，在最終生成的二進制 文件中加入一個額外的信息段來描述該二進制程序的行為，并將此信息傳遞給動 態(tài)二進制翻譯器。圖1 3 給出了該方法的框架。我們定義該額外信息為注解信息， 并定義二進制文件中的額外信息段為注解信息段。注解信息由靜態(tài)編譯器生成并 按照預(yù)先定義好的格式存儲在二進制文件的注解信息段中，動態(tài)二進制翻譯器中 的注解信息分析器會根據(jù)該格式將注解信息提取出來供優(yōu)化翻譯碼所用。當含有 注解信息段的二進制文件執(zhí)行在源體系結(jié)構(gòu)或者沒有注解信息分析器的動態(tài)二 進制翻譯器上時，注解信息段將不會對該二進制程序的正常執(zhí)行帶來任何影響。 9 簡介 在圖1 3 所示的注解信息制導(dǎo)的動態(tài)二進制翻譯框架中，可以在靜態(tài)編譯階段加 入p g o ( p r o f i l eg u i d e do p t i m i z a t i o n ) 執(zhí)行階段，通過結(jié)合靜態(tài)編譯收集得到的 信息和p g o 執(zhí)行得到的反饋信息，可以在靜態(tài)編譯階段生成更加準確的注解信 息。同樣在動態(tài)二進制翻譯器中，可以將注解信息和動態(tài)收集到的程序執(zhí)行行為 信息相結(jié)合，從而對翻譯碼進行更有針對性的優(yōu)化。注解信息不僅可以用于翻譯 碼的優(yōu)化，而且也可以用于降低動態(tài)二進制翻譯器的翻譯優(yōu)化開銷，本文將重點 關(guān)注那些能夠被用于指導(dǎo)翻譯碼優(yōu)化的注解信息。 圖1 3 ：注解信息制導(dǎo)動態(tài)二進制翻譯的基本框架 1 4 注解信息制導(dǎo)的動態(tài)二進制翻譯器內(nèi)存優(yōu)化 本文著重于注解信息制導(dǎo)的動態(tài)二進制翻譯器內(nèi)存優(yōu)化，尤其關(guān)注那些能夠 被翻譯成寄存器訪問的訪存指令。在靜態(tài)編譯階段，只要一個變量符合下述條件， 靜態(tài)編譯器就可以在中間語言中將它表示成一個虛擬寄存器( 在g c c 中被稱為 偽寄存器) 。該變量不是v o l a t i l e 變量，對其他線程不可見，并且它的地址沒有 被其它指令引用。盡管寄存器分配會竭盡所能為每一個虛擬寄存器分配一個物理 寄存器，但有些時候靜態(tài)編譯器迫于有限的物理寄存器數(shù)目，還是不得不用內(nèi)存 空間來表示某些虛擬寄存器。在動態(tài)二進制翻譯的過程中，如果目標體系結(jié)構(gòu)有 空閑的物理寄存器，這些用來表示虛擬寄存器的內(nèi)存空間就可以被重新映射回物 理寄存器。我們定義那些用于表示虛擬寄存器的內(nèi)存空間為可寄存器化內(nèi)存空間 1 0 簡介 ( r e g i s t e r i z a b l em e m o r y ) ，簡稱r e m 。同時定義那些訪問可寄存器化內(nèi)存空問 的訪存指令為r e m 指令。 一個r e m 指令的例子如圖1 - 4 所示，圖的左面是用c + + 語言寫的函數(shù)加d l ， 右面是對應(yīng)于該函數(shù)的i a - 3 2 0 二進制碼片斷。函數(shù)f o o o 中有四個局部變量，分 別是i ，j ，k ，塒，變量七和明不是r e m ，因為在函數(shù)f o o o 調(diào)用函數(shù)# n c o 時， 變量k 是以引用的方式作為參數(shù)被傳遞到函數(shù)f u n c o 的，其值有可能在函數(shù)f u n c o 中被修改。而變量m 則被聲明為v o l a t i l e 變量，因此在靜態(tài)編譯的時候，變量塒 是必須被存放在內(nèi)存堆棧上的。變量i 和，是r e m 變量，由圖1 4 所示，與變 量i 相對應(yīng)的堆?？臻g是 e b p - 2 8 1 ，而與變量，相對應(yīng)的不僅有堆?？臻g e b p 2 町， 還有寄存器p a x 。如果有足夠的物理寄存器，那么r e m 變量i ，j 在靜態(tài)編譯優(yōu) 化時可以被放入到寄存器中，而無需存放在堆棧上。如圖1 - 4 右半部分所示，當 r e m 變量，的值被指令m o ve a x , d w o r dp 豫 e b p - 2 q 載入到寄存器e a x 之后， 后續(xù)指令對r e m 變量_ ，的訪問就可以直接訪問e a x ，而無需從堆棧上再次載入。 但是迫于物理寄存器數(shù)目有限，r e m 變量無法常駐于寄存器之中。堆?？臻g 心細一2 8 1 ， e b p - 2 4 可被認為是r e m ，而訪問這兩個內(nèi)存地址的內(nèi)存指令是r e m 指令。如果有多余的寄存器，動態(tài)二進制翻譯器可以將這兩個r e m 空間映射到 目標體系結(jié)構(gòu)的物理寄存器中，同時將r e m 指令翻譯成寄存器訪問指令。 一 i i “3 2 自 4 i n tf u n c ( i n t & a ) ： - , q ；二= 二， v o i df o o o ， i n t i j k = 1 ： k 曲p - 1 2 1 | (】 v o l a t i l ei n tm ：ime “d w o r op t r e b p - 1 2 i m n ，- 2 嘲 w h i l e o ) f jw o p - 2 , q () = i = ( | n op n o r d p t r e b p - | ， w o p - 1 6 1 (1 i + + ： i - w v m x , d w o r dp t r 陋呻2 i 】+ j 互。；j ) 暇m ( j c c ) f u n c ( k ) ： f _ 刪d w o r dp t r e b p - 2 8 , e a x i + = j ； n l2 j ： r n o vd w o r dp t rl 融恥1 田e 截 ) ) f j c c 圖1 _ 4 ：r e m 指令的例子 簡介 除了寄存器化，給予r e m 指令的特性，本文也研究了其他諸如放寬m e m o r y o r d e r i n g 的限制，加強訪存指令的地址消岐和放寬精確異常處理等內(nèi)存優(yōu)化方 法，將在下文中詳細闡述。 g c c 是一個被廣泛應(yīng)用的開源靜態(tài)編譯器，i a 3 2e l ( i a 一3 2e x e c u t i o nl a y e r ) 是由i n t e l 。公司開發(fā)的在i t a n i u m 固上運行n 3 2 程序的動態(tài)二進制翻譯器 1 6 】。 我們修改了靜態(tài)編譯器g c c4 0 和動態(tài)二進制翻譯器i a - 3 2e l ，實現(xiàn)了注解信 息制導(dǎo)動態(tài)二進制翻譯的框架。我們通過修改g c c4 0 ，使之在編譯過程中收集 與優(yōu)化相關(guān)的注解信息，尤其是r e m 指令相關(guān)信息，最后將生成的注解信息存 放在二進制文件的注解信息段。我們也修改i a - 3 2e l ，使之能將二進制文件中的 注解信息提取出來并結(jié)合到翻譯碼的優(yōu)化之中。在利用這些注解信息進行了諸如 r e m 空間寄存器化和針對r e m 指令的其他內(nèi)存優(yōu)化之后，i a - 3 2e l 取得了相 當可觀的性能提升。我們用s p e c 2 0 0 0v 1 3 作為我們的基準測試程序，注解信息 制導(dǎo)的內(nèi)存優(yōu)化能夠使其在i a - 3 2e l 上獲得不錯的性能提升。實驗數(shù)據(jù)表明， i a - 3 2e l 能夠通過利用注解信息優(yōu)化翻譯碼提高s p e c f p 2 0 0 0 的總體性能達 1 5 0 3 之多，提高s p e c i n t 2 0 0 0 的總體性能1 2 1 。 本文剩余部分將按如下順序展開。在第二部分，我們將著重描述注解信息的 格式，以及如何在靜態(tài)編譯器中生成注解信息和在動態(tài)二進制翻譯器中讀取注解 信息。第三部分將著重討論基于注解信息的翻譯碼優(yōu)化，詳細討論包括寄存器化， 放寬m e m o r yo r d e r i n g 的限制，加強訪存指令的地址消岐和放寬精確異常處理等 基于r e m 指令注解信息的內(nèi)存優(yōu)化。在第四部分，我們將展示注解信息制導(dǎo)的 動態(tài)二進制翻譯優(yōu)化的試驗數(shù)據(jù)，并分析其優(yōu)化效果，給予相應(yīng)的評價。最后我 們將在第五部分討論相關(guān)工作，在第六部分對全文進行總結(jié)。 注解信息 2 注鰓信息 2 。1 注解信息格式 注解信息是按照一定的格式保存在二進制文件的注解信息段中的，靜態(tài)編譯 器按照預(yù)先定義的注解信息格式將注解信息寫入到注解信息段中，動態(tài)二進制翻 譯器也按照該格式將注解信息從二進制文件中讀出。因此，定義一個能夠快速讀 取，便于擴展的注解信息格式尤為重要。 2 1 1 通用注解信息格式 為了便于管理和對注解信息進行分類，我們以函數(shù)為注解信息的基本單位， 并定義其為函數(shù)注解信息。每一個函數(shù)注解信息中記錄著與該函數(shù)相關(guān)的注解信 息。二進制文件的注解信息段是由若干個函數(shù)注解信息組成的，圖2 1 給出了一 個函數(shù)注解信息的格式。 每個函數(shù)注解信息都有一個函數(shù)注解信息頭，用于描述該函數(shù)的一些特性。 除了函數(shù)注解信息頭，函數(shù)注解信息還包括代碼區(qū)間注解信息，代碼區(qū)間的范圍 可以是函數(shù)中某一連續(xù)地址的代碼段，也可以是整個函數(shù)本身。函數(shù)注解信息可 以由一個或者多個代碼區(qū)間注解信息組成。 函數(shù)注解信息頭描述的是與該函數(shù)相關(guān)的一些信息和特性，例如函數(shù)入口地 址和函數(shù)長度能夠給出所有在函數(shù)內(nèi)的二進制碼的范圍。函數(shù)注解信息頭的大小 是固定的，但是函數(shù)注解信息內(nèi)有多少個代碼區(qū)間注解信息以及函數(shù)注解信息本 身的大小是不定的。為了保證注解信息能夠自我描述并且易于動態(tài)二進制翻譯器 快速定位和讀取，在函數(shù)注解信息頭中加入了兩個額外的字段，函數(shù)注解信息長 度和代碼區(qū)間注解信息的個數(shù)。前者給出了該函數(shù)注解信息的總長度，后者則給 出了在該函數(shù)注解信息中有多少個代碼區(qū)間注解信息。函數(shù)注解信息頭中還可以 加入其它字段，例如驗證字段，可用來標明當前注解信息格式的版本號，如果該 版本號和動態(tài)二進制翻譯器所預(yù)期的版本號不相符合，那么動態(tài)二進制翻譯器可 以選擇不讀取該函數(shù)注解信息。 代碼區(qū)間注解信息描述的是函數(shù)中某一連續(xù)地址區(qū)間中的二迸制碼的屬性。 代碼區(qū)間注解信息緊接著函數(shù)注解信息頭按任意順序排列。代碼區(qū)間注解信息由 代碼區(qū)間注解信息頭和若干注解信息記錄組成。 1 3 注解信息 代碼區(qū)間注解信息頭類似函數(shù)信息頭，不僅描述了該代碼區(qū)間的范圍，而且 描述了該代碼區(qū)間注解信息的長度。為了能夠有效的減少代碼區(qū)間注解信息的總 長度，代碼區(qū)間起始地址和結(jié)束地址用它們和函數(shù)起始地址的偏移量來表示。根 據(jù)函數(shù)長度不同，該偏移量字段的大小也可隨之改變，我們可以在函數(shù)注解信息 頭的保留字段中標明代碼區(qū)間注解信息頭中偏移量字段的大小。通常情況下，代 碼區(qū)間起始地址和結(jié)束地址的字段僅需兩個字節(jié)即可。 注解信息 段 函數(shù)注解j 礁裟i，一一一一一 l霪餮窘 霪囂唇雪一注解記錄 卜 萋魯垡跫 二l 簍1 一一一一一 信息1 注解記錄 頭 蔭數(shù)起始地址 函數(shù)長度 函數(shù)注解信息長度 代碼區(qū)聞注解信息 數(shù)目 保留字段 代碼區(qū)間起始地址 代碼區(qū)間結(jié)柬地址 代碼區(qū)間注解信息 長度 注解記錄數(shù)日 注解記錄類型 注解記錄長度 注解記錄體 另一個注解記錄 另一個代碼區(qū)間 圖2 1 ：通用注解信息格式 每一個代碼區(qū)間注解信息中可以包括若干條注解記錄。每條注解記錄的長度 并不固定，而且可以用來記錄不同種類的注解信息。注解記錄中保存的是描述該 1 4 注解信息 代碼區(qū)間的注解信息。每條注解記錄都有注解記錄頭和注解記錄體組成。注解記 錄頭不僅描述了該注解記錄的長度，而且給出了該注解記錄的具體類型。每一個 注解記錄類型都可以按照各自的格式存儲注解信息。 上述通用注解信息格式具有如下特點：1 ) 簡潔2 ) 易于讀取3 ) 自我描述4 ) 靈活性和擴展性5 ) 平臺無關(guān)性。 2 1 2r e m 注解記錄格式 因為r e m 是按照函數(shù)為單位劃分的，因此我們選擇為每一個函數(shù)注解信息 加入一條r e m 注解記錄來標示該函數(shù)中的r e m 指令。首先，我們尋找出所有 的r e m 指令，并且按照其訪問的r e m 地址對它們進行分組。然后為每一組r e m 指令進行編號，稱之為r e m 號。此時，每一條r e m 指令都將獲得一個r e m 號， 該號可用于標明r e m 指令訪問的r e m 地址。 其實，我們通過生成初始r e m 映射表來標示r e m 指令在源二迸制碼中的位 置。我們依據(jù)該函數(shù)的源二進制碼的大小生成一個相同大小的初始g e m 映射表 并將其初始化為全零。我們對源二進制碼中的每一條r e m 指令，計算其相對于 該函數(shù)起始地址的偏移量，并依據(jù)該偏移量在初始r e m 映射表中找到對應(yīng)的字 節(jié)，將該r e m 指令的g e m 號寫入到該偏移量中。至此，初始g e m 映射表就被 生成了。 最后，我們將初始g e m 映射表進一步壓縮后生成r e m 注解記錄。我們分別 對初始r e m 映射表中的數(shù)據(jù)零和g e m 號進行壓縮。在r e m 注解信息中，我們 定義每一個字節(jié)要么用來表示在初始r e m 映射表中連續(xù)數(shù)據(jù)零的個數(shù)，要么用 來表示一個g e m 號。因此，我們定義在r e m 注解信息中，當一個字節(jié)的最高 比特位為0 時，該字節(jié)的剩余7 位比特將被用于表示連續(xù)數(shù)據(jù)零的數(shù)目，而當一 個字節(jié)的最高比特位為l 時，該字節(jié)的剩余7 位比特則給出了一個r e m 號。由 此，我們可將一個初始g e m 映射表壓縮成r e m 注解記錄，并最終將該記錄保 存在注解信息段中。 因為我們僅用7 位比特來表示g e m 號或者表示連續(xù)數(shù)據(jù)零，因此其最大可 表示范圍為1 2 8 。當函數(shù)中出現(xiàn)超過1 2 8 個連續(xù)數(shù)據(jù)零時，我們可以用兩個或多 個連續(xù)最高比特位為0 的字節(jié)來表示這些連續(xù)數(shù)據(jù)零。在注解信息中連續(xù)n 個 最高位比特為零的字節(jié)可以表示n * 1 2 8 個連續(xù)數(shù)據(jù)零。而當函數(shù)中出現(xiàn)超過1 2 8 個g e m 號時，我們可以通過擴大注解記錄中用來表示r e m 號的數(shù)據(jù)長度來實 現(xiàn)，例如我們可以將兩個連續(xù)字節(jié)視為整體來表示g e m 號，這樣就可以有1 5 位比特的數(shù)據(jù)來表示r e m 號，從而可以表示多達3 2 7 6 8 個r e m 號，對于一般 1 5 注解信息 的函數(shù)而言已經(jīng)綽綽有余了。對于不同的壓縮方法，我們可以在注解記錄頭中的 注解記錄類型中用比特位表明，方便動態(tài)二進制翻譯器讀取。 我們根據(jù)圖l - 4 中的代碼片段生成其相應(yīng)的r e m 注解記錄來進一步描述 r e m 注解記錄的生成過程，如圖2 2 所示。圖中共有三條r e m 指令，為了方 便，我們用指令中訪存地址的立即數(shù)偏移作為該指令的r e m 號，例如指令a d d d w o r d p 豫膨助0 8 1 ，e a x 的r e m 號是2 8 。指令i n c d w o r d p 豫 e b p - 2 8 1 相對 于該代碼區(qū)間的首地址偏移量為8 ，因此在初始r e m 映射表中，偏移量為8 的 地方填入該r e m 指令的r e m 號，2 8 。同理，另外兩條r e a m 指令的r e m 號分 別被寫入到初始r e m 映射表中偏移量為1 5 和3 4 的地方。初始r e m 映射表中 的其余字節(jié)均為零。我們將根據(jù)該初始r e m 映射表壓縮生成r e m 注解記錄。 初始r e m 映射表中的起始連續(xù)7 個零在r e m 注解記錄中被表示為o x 7 。初始 r e m 映射表中的第8 個字節(jié)2 8 在r e m 注解記錄中被表示成r e m 號0 x 9 c ，因 為r e m 號總數(shù)小于1 2 8 ，因此我們在r e m 注解記錄中用一個字節(jié)來表示r e m 號。最后我們將生成一個7 個字節(jié)大小的注解記錄來表示圖中源二進制碼中的 r e m 指令。 圖2 2 ：r e m 注解記錄格式 1 6 注解信息 2 。2 在靜態(tài)編譯器中生成注解信息 在二進制文件中生成注解信息不僅需要修改編譯器，還需要修改匯編器和鏈 接器。我們選擇開源的靜態(tài)編譯器g c c4 0 1 2 2 來進行實驗。g c c 和其它流行的 靜態(tài)編譯器一樣，有一整套工具來完成整個編譯過程。當用戶在命令行中執(zhí)行 g c c 命令時，以下工具c c l ，a s 和塒會分別按序被調(diào)用來完成整個編譯工作。源 高級語言代碼首先會由c c l 編譯成匯編碼，然后再由匯編器a s 翻譯生成可重定 向的目標文件。最終，鏈接器膃將所有的可重定向目標文件鏈接起來生成最終 的可執(zhí)行二進制文件。因此，為了在最終可執(zhí)行的二進制文件中能夠生成注解信 息段，我們不僅需要修改g c c 的編譯器c c l ，也需要修改g c c 的匯編器a s 和 鏈接器搿。 大多數(shù)注解信息是在編譯階段收集得到的。編譯器首先對高級語言編寫的源 程序進行解析，并且以函數(shù)為單位通過中間語言生成語法分析樹。然后對語法分 析樹進行多次遍歷，并不斷對中間語言進行優(yōu)化，最終將優(yōu)化完畢的語法分析樹 編譯成匯編指令。在這個過程中，高級語言的信息逐漸被丟失，因此，編譯器中 的注解信息生成器在此階段的主要任務(wù)是分析并整理出有用的注解信息。以收集 r e m 指令的注解信息為例，首先我們在寄存器分配前找出所有偽寄存器( p s e u d o r e g i s t e r ) 【2 2 】。偽寄存器中存放的是所有未被聲明為v o l a t i l e 并且沒有被其它任 何指令引用的標量型變量。當g c c 開始進行局部寄存器分配，全局寄存器分配 和寄存器重新分配【2 2 】時，我們記錄那些會被暫時寫入到堆棧上的偽寄存器，并 且跟蹤記錄所有訪問這些堆棧內(nèi)存空間的訪存指令。在寄存器分配結(jié)束之后，我 們還會在其后續(xù)優(yōu)化中跟蹤記錄我們所收集到的這些訪存指令，以察看這些指令 是否被其他優(yōu)化更新或者刪除，繼而保證該階段所收集的注解信息的正確性。最 終，我們將收集到的初始注解信息和匯編指令一起寫入到編譯器生成的匯編文件 中。 我們修改匯編器使之不僅會將匯編文件中的初始注解信息按照上一節(jié)描述 的注解信息格式寫入目標文件，而且會為那些可重定向的注解信息生成相應(yīng)的樁 ( s t u b s ) 。在每個目標文件中，都會生成兩個按照標準b f d ( b i n a r y f i l e d e s c r i p t o r ) 2 3 文件格式生成的注解信息段，個是常規(guī)的注解信息段，另一個是可重定向 的注解信息段。匯編器會按照注解信息的類型分別將他們寫入到常規(guī)的注解信息 段或者可重定向的注解信息段。例如類似函數(shù)長度之類的注解信息在將匯編指令 進行二進制編碼的時候就可確定，因此匯編器會將其寫入到常規(guī)的注解信息段 中。而像函數(shù)入口地址之類的注解信息要到最后鏈接的時候才能確定，因此匯編 1 7 注解信息 器會在常規(guī)的注解信息段中為其保留一個樁，并將該樁寫入到可重定向的注解信 息段的數(shù)據(jù)項中。 最后在鏈接器中，所有可重定向的目標文件會被鏈接并生成最終的可執(zhí)行二 進制文件。因此在鏈接時，需要計算那些可重定向的注解信息的值，并根據(jù)可重 定向的注解信息段中的數(shù)據(jù)項獲得保留樁的地址，將計算值回填入常規(guī)注解信息 段中的保留樁。當鏈接全部完成后，鏈接器所要做的就是計算最終注解信息段的 大小，并在二進制文件中預(yù)留足夠的空間，然后合并所有目標文件中的注解信息 段生成一個最終注解信息段，最后將此注解信息段寫入到可執(zhí)行二進制文件中。 2 。3 在動態(tài)二進制翻譯器中讀取注解信息 程序往往會將大多數(shù)執(zhí)行時間花費在很小一段代碼上。同時，為了避免動態(tài) 二進制翻譯器讀取注解信息的開銷過高，我們提出了一種分步，按需讀取注解信 息的方法。我們在動態(tài)二進制翻譯器中加入了一個注解信息分析器，如圖2 - 3 所示。注解信息分析器一方面從源二進制碼中讀取注解信息，并將這些注解信息 整理后以內(nèi)部表示的形式存儲在動態(tài)二進制翻譯器的內(nèi)存中。另一方面，動態(tài)二 進制翻譯器在翻譯的過程中也可以通過注解信息分析器查詢感興趣的注解信息。 圖2 3 ：注解信息分析器 在可執(zhí)行二進制文件被裝載時，注解信息分析器會掃描注解信息段，并為每 個函數(shù)注解信息建立索引。注解信息分析器會依次讀入每個函數(shù)注解信息的地 址，以及該函數(shù)注解信息的函數(shù)注解信息頭。函數(shù)注解信息頭包括函數(shù)起始地址， 函數(shù)長度，函數(shù)注解信息長度等字段。為了加速查詢一個指令地址所在的函數(shù)， 1 8 注解信息 我們利用a v l 2 4 樹來存放索引信息，該樹被稱為注解信息a v l 樹。所有注解 信息a v l 樹的節(jié)點對應(yīng)于一個注解信息段中的一個函數(shù)注解信息，其內(nèi)容包含 函數(shù)起始地址，函數(shù)長度，函數(shù)注解信息首地址，注解信息是否被讀取等字段。 注解信息a v l 樹中節(jié)點的關(guān)鍵字是函數(shù)起始地址。注解信息索引建立的算法如 圖2 - 4 所示。分步讀取的方法使注解信息分析器在程序起始階段只需要讀取- d , 段注解信息即可，避免了在