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

論文獨(dú)創(chuàng)性聲明 本論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。論文中除 了特別加以標(biāo)注和致謝的地方外，不包含其他人或其它機(jī)構(gòu)已經(jīng)發(fā)表或撰寫(xiě)過(guò)的 研究成果。其他同志對(duì)本研究的啟發(fā)和所做的貢獻(xiàn)均已在論文中作了明確的聲明 并表示了謝意。 作者簽名：縫墊盤(pán) 同期： 論文使用授權(quán)聲明 本人完全了解復(fù)旦大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留 送交論文的復(fù)印件，允許論文被查閱和借閱；學(xué)校可以公布論文的全部或部分內(nèi) 容，可以采用影印、縮印或其它復(fù)制手段保存論文。保密的論文在解密后遵守此 璇。作者簽名：盈醯翮簽名：重芏莖趙嗍貍：紐作者簽名：壟鑫壑盤(pán)導(dǎo)師簽名：鬈芏莖理同期：2 丑：亟：! 摘要 關(guān)鍵字：注解信息，動(dòng)態(tài)二進(jìn)制翻譯器，內(nèi)存優(yōu)化，寄存器化 動(dòng)態(tài)二進(jìn)制翻譯器能夠在運(yùn)行時(shí)將針對(duì)源體系結(jié)構(gòu)編譯的軟件動(dòng)態(tài)翻譯成 目標(biāo)體系結(jié)構(gòu)的軟件并使之運(yùn)行。盡管隨著新的體系結(jié)構(gòu)不斷涌現(xiàn)，動(dòng)態(tài)二進(jìn)制 翻譯器技術(shù)越來(lái)越流行，但是動(dòng)態(tài)二進(jìn)制翻譯器往往會(huì)受限于在翻譯碼上可執(zhí)行 的優(yōu)化方法，無(wú)法使翻譯碼的執(zhí)行性能同移植程序的執(zhí)行性能相媲美。因?yàn)樵纯?執(zhí)行文件中只有二進(jìn)制代碼，缺乏源程序高級(jí)語(yǔ)言的信息，麗且動(dòng)態(tài)二進(jìn)制翻譯 器在翻譯過(guò)程中需要保證翻譯碼同源碼在二進(jìn)制級(jí)別上的兼容性，因此動(dòng)態(tài)二進(jìn) 制翻譯器往往無(wú)法采用一些在靜態(tài)編譯器中常用的代碼優(yōu)化方法。另外，為了保 證在異常發(fā)生的情況下能夠恢復(fù)出一個(gè)精確的體系結(jié)構(gòu)狀態(tài)，翻譯碼中的指令調(diào) 度被限制在個(gè)相對(duì)較小的范圍內(nèi)，更進(jìn)一步的限制了動(dòng)態(tài)二進(jìn)制翻譯器的翻譯 碼優(yōu)化。本文則從一個(gè)創(chuàng)新的角度提出了一種解決上述問(wèn)題的方法。該方法在靜 態(tài)編譯器中收集那些對(duì)動(dòng)態(tài)二進(jìn)制翻譯器優(yōu)化有幫助的信息，并在可執(zhí)行文件中 開(kāi)辟一個(gè)獨(dú)立的注解信息段，將這些優(yōu)化相關(guān)的信息以一定的格式寫(xiě)入其中。在 動(dòng)態(tài)二進(jìn)制翻譯階段，動(dòng)態(tài)二進(jìn)制翻譯器就可以利用注解信息對(duì)翻譯碼迸一步優(yōu) 化，提高翻譯碼的質(zhì)量。本文在g c c4 0 和i a - 3 2e x e c u t i o nl a y e r 上實(shí)現(xiàn)了注解 信息制導(dǎo)的動(dòng)態(tài)二進(jìn)制翻譯框架，并且選擇在可執(zhí)行文件中生成內(nèi)存優(yōu)化相關(guān)的 注解信息?；谧⒔庑畔?，本文在動(dòng)態(tài)二進(jìn)制翻譯器隊(duì)3 2e l 中嘗試了包括寄 存器化，放寬m e m o r yo r d 嘶n g 的限制，加強(qiáng)訪存指令的地址消岐和放寬精確異 常處理等內(nèi)存優(yōu)化。本文選擇s p e c 2 0 0 0 為基準(zhǔn)測(cè)試程序，實(shí)驗(yàn)結(jié)果表明注解信 息制導(dǎo)的動(dòng)態(tài)二進(jìn)制翻譯器中的內(nèi)存優(yōu)化能夠在引入相對(duì)較小的額外開(kāi)銷下獲 得十分不錯(cuò)的性能提升。實(shí)驗(yàn)數(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 。對(duì)于某些特定的基準(zhǔn)測(cè)試 程序，性能提升甚至達(dá)到了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 簡(jiǎn)介 1 筒奔 動(dòng)態(tài)二進(jìn)制翻譯技術(shù)是一種即時(shí)編譯技術(shù) 1 1 1 9 ，它將針對(duì)源體系結(jié)構(gòu)編譯 生成的二進(jìn)制碼( 源二進(jìn)制碼) 動(dòng)態(tài)翻譯成可以在目標(biāo)體系結(jié)構(gòu)上運(yùn)行的二進(jìn)制 碼( 翻譯碼) 。動(dòng)態(tài)二進(jìn)制翻譯技術(shù)主要被用來(lái)保證目標(biāo)體系結(jié)構(gòu)對(duì)源體系結(jié)構(gòu) 的向后兼容。利用動(dòng)態(tài)二進(jìn)制翻譯技術(shù)，所有源軟件無(wú)需移植就可以直接在與源 體系結(jié)構(gòu)不兼容的目標(biāo)機(jī)器上運(yùn)行。 隨著計(jì)算機(jī)體系結(jié)構(gòu)的不斷推陳出新，目前主流的體系結(jié)構(gòu)肯定會(huì)被新的體 系結(jié)構(gòu)所替代。因此當(dāng)前編譯生成的軟件并不一定能夠在將來(lái)的主流機(jī)器上執(zhí) 行。即便將來(lái)的體系結(jié)構(gòu)兼容目前的主流體系結(jié)構(gòu)，其微體系結(jié)構(gòu)肯定會(huì)有較大 的改動(dòng)和變化。因此，針對(duì)目前的微體系結(jié)構(gòu)進(jìn)行優(yōu)化編譯的軟件在將來(lái)的體系 結(jié)構(gòu)上的執(zhí)行性能勢(shì)必大打折扣。為了能夠提高軟件的執(zhí)行性能，需要將軟件的 源代碼針對(duì)目標(biāo)體系結(jié)構(gòu)重新編譯優(yōu)化并進(jìn)行調(diào)試。但是源代碼中往往會(huì)有大量 平臺(tái)相關(guān)的特性存在，例如將一個(gè)3 2 位的軟件編譯成6 4 位的軟件，源代碼中有 效數(shù)據(jù)的長(zhǎng)度變化將會(huì)為重新編譯和優(yōu)化帶來(lái)不少麻煩，因此重新編譯和優(yōu)化源 代碼的移植方法將會(huì)十分的費(fèi)時(shí)費(fèi)力。利用動(dòng)態(tài)二進(jìn)制翻譯技術(shù)，就可以針對(duì)目 標(biāo)體系結(jié)構(gòu)實(shí)現(xiàn)一個(gè)源體系結(jié)構(gòu)的模擬器，針對(duì)源體系結(jié)構(gòu)編譯優(yōu)化的軟件就可 以通過(guò)該模擬器直接運(yùn)行在目標(biāo)機(jī)器上，從而避免了對(duì)源代碼進(jìn)行重新編譯和優(yōu) 化的麻煩。 1 1 動(dòng)態(tài)二進(jìn)制翻譯器的基本框架 源二進(jìn)制程序在動(dòng)態(tài)二進(jìn)制翻譯器上的執(zhí)行往往分為兩個(gè)基本階段：翻譯階 段和執(zhí)行階段。在翻譯階段。動(dòng)態(tài)二進(jìn)制翻譯器對(duì)源二進(jìn)制碼進(jìn)行解碼之后將其 翻譯為目標(biāo)體系結(jié)構(gòu)上的二進(jìn)制碼，即翻譯碼。翻譯完畢后，動(dòng)態(tài)二進(jìn)制翻譯器 便切換到翻譯碼中進(jìn)入執(zhí)行階段。當(dāng)程序在翻譯碼中運(yùn)行至尚未翻譯的代碼片段 時(shí)，便會(huì)切換回動(dòng)態(tài)二進(jìn)制翻譯器從該點(diǎn)開(kāi)始繼續(xù)翻譯源二進(jìn)制碼。這樣源二進(jìn) 制程序就可以在目標(biāo)機(jī)上執(zhí)行。動(dòng)態(tài)二進(jìn)制翻譯器的基本框架如圖l - 1 所示。 5 簡(jiǎn)介 圖1 - 1 ：動(dòng)態(tài)二進(jìn)制翻譯器框架 動(dòng)態(tài)二進(jìn)制翻譯器的翻譯往往會(huì)包含三個(gè)階段：解釋執(zhí)行階段，普通翻譯階 段，優(yōu)化翻譯階段。當(dāng)源二進(jìn)制碼首次執(zhí)行時(shí)，動(dòng)態(tài)二進(jìn)制翻譯器會(huì)對(duì)其進(jìn)行解 釋執(zhí)行。解釋執(zhí)行將不會(huì)保存任何翻譯結(jié)果，如果該源二進(jìn)制碼再次被執(zhí)行時(shí)， 它將再次被翻譯。為了避免重復(fù)翻譯帶來(lái)的開(kāi)銷，當(dāng)源二進(jìn)制碼的執(zhí)行次數(shù)達(dá)到 某一閥值時(shí)，便會(huì)進(jìn)入普通翻譯階段。此時(shí)，動(dòng)態(tài)二進(jìn)制翻譯器對(duì)該源二迸制碼 進(jìn)行翻譯，并將生成的翻譯碼保存在內(nèi)存中。如此，當(dāng)程序再次執(zhí)行到該源二進(jìn) 制碼時(shí)，就可以直接執(zhí)行相對(duì)應(yīng)的翻譯碼，而無(wú)需重新翻譯。由于普通翻譯階段 需要翻譯的源二進(jìn)制碼往往很多，因此動(dòng)態(tài)二進(jìn)制翻譯器會(huì)采用簡(jiǎn)單快速的翻譯 算法，并且在翻譯碼中加入一些額外的代碼來(lái)收集該翻譯碼的動(dòng)態(tài)執(zhí)行行為信 息，該翻譯碼被稱為普通翻譯碼。對(duì)于那些頻繁執(zhí)行的關(guān)鍵代碼塊，當(dāng)其執(zhí)行次 數(shù)超過(guò)某一個(gè)更高的閥值時(shí)，它將被動(dòng)態(tài)二進(jìn)制翻譯器再次翻譯，并且進(jìn)入優(yōu)化 翻譯階段。在優(yōu)化翻譯階段，動(dòng)態(tài)二進(jìn)制翻譯器將花費(fèi)更多的時(shí)間，采用更加復(fù) 雜的算法對(duì)翻譯碼進(jìn)行優(yōu)化翻譯，以期得到更高質(zhì)量的翻譯碼。優(yōu)化翻譯階段生 成的翻譯碼被稱為優(yōu)化翻譯碼，其執(zhí)行效率遠(yuǎn)遠(yuǎn)高于普通翻譯階段生成的普通翻 譯碼。 動(dòng)態(tài)二進(jìn)制翻譯器在生成翻譯碼的時(shí)候，會(huì)將源二進(jìn)制碼塊和翻譯碼塊的對(duì) 應(yīng)關(guān)系記錄在一張對(duì)應(yīng)表中，該表被稱為翻譯映射表。翻譯映射表中的每一項(xiàng)記 錄了一對(duì)源二進(jìn)制碼塊的首地址和與其相對(duì)應(yīng)的翻譯碼塊的首地址。當(dāng)程序執(zhí)行 完一個(gè)翻譯碼塊后，會(huì)根據(jù)當(dāng)前源二進(jìn)制碼的i p ( i n s t r u c t i o np o i n t e r ) 地址在翻 譯映射表中尋找其相應(yīng)的翻譯碼。如果命中，那么就可以從翻譯映射表中讀取后 6 簡(jiǎn)介 繼翻譯碼的入口地址，直接跳轉(zhuǎn)到該翻譯碼繼續(xù)執(zhí)行。若沒(méi)有在翻譯映射表中找 到對(duì)應(yīng)項(xiàng)，說(shuō)明該源二進(jìn)制碼尚未被翻譯，那么動(dòng)態(tài)二進(jìn)制翻譯器就會(huì)從該皿 地址開(kāi)始翻譯源二進(jìn)制碼。在動(dòng)態(tài)二進(jìn)制翻譯器和翻譯碼間進(jìn)行上下文切換十分 費(fèi)時(shí)，為了避免每執(zhí)行完一個(gè)翻譯碼塊就要查詢翻譯映射表，對(duì)于直接跳轉(zhuǎn)指令， 動(dòng)態(tài)二進(jìn)制翻譯器可做如下優(yōu)化。若某一翻譯碼塊a 的后繼翻譯碼塊b 已被生 成，動(dòng)態(tài)二進(jìn)制翻譯器便可在翻譯指令時(shí)將后繼翻譯碼塊b 的入口地址回填到 該翻譯碼塊a 末尾的跳轉(zhuǎn)指令的目標(biāo)地址中，這樣，翻譯碼塊a 執(zhí)行完畢后， 就可通過(guò)該跳轉(zhuǎn)指令直接跳轉(zhuǎn)到后繼翻譯碼b ，而無(wú)需切換到動(dòng)態(tài)二進(jìn)制翻譯器 的上下文查詢翻譯映射表。當(dāng)翻譯碼被更新，例如從普通翻譯碼被更新為優(yōu)化翻 譯碼，動(dòng)態(tài)二進(jìn)制翻譯器不僅需要更新翻譯映射表，還需要對(duì)所有該翻譯碼的前 驅(qū)翻譯碼中的跳轉(zhuǎn)指令的目標(biāo)地址進(jìn)行更新。 ， h， l ? j i l l 、 、 圖1 - 2 ：熱路徑的構(gòu)造 動(dòng)態(tài)二進(jìn)制翻譯器的普通翻譯往往是按照源二進(jìn)制碼的基本塊為單位進(jìn)行翻 譯的，而優(yōu)化翻譯通常會(huì)采取熱路徑的方式翻譯源二進(jìn)制碼【1 h 2 5 。動(dòng)態(tài)二進(jìn) 制翻譯器會(huì)在普通翻譯碼中加入一些額外代碼來(lái)收集普通翻譯碼的動(dòng)態(tài)執(zhí)行行 為信息。例如在普通翻譯碼中加入計(jì)數(shù)代碼統(tǒng)計(jì)該普通翻譯碼的執(zhí)行次數(shù)，從而 判斷該普通翻譯碼的執(zhí)行次數(shù)是否達(dá)到閥值?；蛘邽槠胀ǚg碼的條件跳轉(zhuǎn)指令 加入計(jì)數(shù)代碼統(tǒng)計(jì)該跳轉(zhuǎn)指令的跳轉(zhuǎn)次數(shù)。動(dòng)態(tài)二進(jìn)制翻譯器可以結(jié)合普通翻譯 碼的執(zhí)行次數(shù)和條件跳轉(zhuǎn)指令的跳轉(zhuǎn)次數(shù)推測(cè)該普通翻譯碼的后續(xù)翻譯碼，并可 以此為今后構(gòu)造熱路徑提供依據(jù)。如圖1 2 所示，動(dòng)態(tài)二進(jìn)制翻譯器在構(gòu)造熱路 徑時(shí)可以得到以下信息，翻譯碼塊a 跳轉(zhuǎn)到翻譯碼塊b 的頻率為7 0 ，翻譯碼 塊d 跳轉(zhuǎn)到a 的頻率為9 0 。根據(jù)以上信息，動(dòng)態(tài)二進(jìn)制翻譯器就會(huì)將翻譯碼 7 簡(jiǎn)介 塊a ，b 和d 串聯(lián)起來(lái)，經(jīng)過(guò)代碼優(yōu)化后，構(gòu)成一個(gè)新的翻譯碼塊a ，即熱路 徑a 。然后更新翻譯映射表，將普通翻譯碼塊a ，b ，d 更新為熱路徑a 。最 后更新所有翻譯碼塊a 的前驅(qū)翻譯碼塊的跳轉(zhuǎn)指令，將熱路徑a 的地址回填到 這些跳轉(zhuǎn)指令的目標(biāo)地址。這樣，今后當(dāng)程序再次執(zhí)行到二進(jìn)制碼a 的入口處， 就會(huì)直接執(zhí)行熱路徑a 了。 1 2 動(dòng)態(tài)二進(jìn)制翻譯器的特點(diǎn)和局限性 動(dòng)態(tài)二進(jìn)制翻譯器在各個(gè)領(lǐng)域被廣泛運(yùn)用。動(dòng)態(tài)二迸制翻譯器的一大好處是 能夠讓用戶在新的體系結(jié)構(gòu)上直接運(yùn)行遺留體系結(jié)構(gòu)上的程序。當(dāng)源體系結(jié)構(gòu)與 目標(biāo)體系結(jié)構(gòu)相同時(shí)，動(dòng)態(tài)二進(jìn)制翻譯器能夠被用來(lái)動(dòng)態(tài)優(yōu)化二進(jìn)制程序【5 】， 或者為二進(jìn)制程序提供安全的運(yùn)行環(huán)境【1 2 】。動(dòng)態(tài)二進(jìn)制翻譯器還能被用于降低 硬件的復(fù)雜度和能耗【1 0 】，提供高性能的代碼分析和檢測(cè)工具 1 7 】。隨著基于二 進(jìn)制代碼翻譯的應(yīng)用越來(lái)越多，越來(lái)越多的程序?qū)?huì)運(yùn)行在動(dòng)態(tài)二進(jìn)制翻譯器 上，而動(dòng)態(tài)二進(jìn)制翻譯器也將會(huì)變得越來(lái)越普遍。 但是，動(dòng)態(tài)二進(jìn)制翻譯器常常由于翻譯碼的性能不佳而受人詬病。在那些對(duì) c p u 要求較高的程序中，相比動(dòng)態(tài)二進(jìn)制翻譯器本身的執(zhí)行開(kāi)銷，大部分的程 序執(zhí)行時(shí)間都花在了翻譯碼上，因此翻譯碼的性能對(duì)于整個(gè)程序的執(zhí)行性能尤為 關(guān)鍵。此外，除了提供不同體系結(jié)構(gòu)下程序的兼容性，動(dòng)態(tài)二進(jìn)制翻譯器還需要 發(fā)掘目標(biāo)體系結(jié)構(gòu)的性能潛力。因此研究如何提高翻譯碼的執(zhí)行性能成了多年來(lái) 動(dòng)態(tài)二進(jìn)制翻譯器的研究重點(diǎn)【l 】【l1 1 9 2 0 】。 盡管如此，和直接在目標(biāo)體系結(jié)構(gòu)上編譯的二進(jìn)制碼相比，動(dòng)態(tài)二進(jìn)制翻譯 器生成的翻譯碼性能還是不能令人滿意。由于動(dòng)態(tài)二進(jìn)制翻譯器的輸入是源二進(jìn) 制碼，它缺乏一些高級(jí)語(yǔ)言中才有的重要信息。而通常這些信息對(duì)于靜態(tài)編譯器 在編譯生成二進(jìn)制碼時(shí)的優(yōu)化有很大的幫助。更進(jìn)一步，動(dòng)態(tài)二進(jìn)制翻譯器也可 以被認(rèn)為是對(duì)源體系結(jié)構(gòu)進(jìn)行模擬的虛擬機(jī)，因此需要?jiǎng)討B(tài)二進(jìn)制翻譯器在翻譯 執(zhí)行的過(guò)程中保證翻譯碼和源二進(jìn)制碼在二進(jìn)制級(jí)別上的兼容性。這一要求不僅 添加了動(dòng)態(tài)二進(jìn)制翻譯器的翻譯限制，而且加劇了翻譯碼的優(yōu)化難度。例如二進(jìn) 制級(jí)別的兼容性要求有：1 ) 每一條源指令的語(yǔ)義必須被翻譯指令精確模擬，2 ) 在翻譯碼的執(zhí)行過(guò)程中能夠保證源體系結(jié)構(gòu)的精確異常得到正確處理，3 ) 在翻 譯碼中按照源體系結(jié)構(gòu)的規(guī)范維持源二進(jìn)制碼中訪存指令的訪問(wèn)順序等。 鑒于動(dòng)態(tài)二進(jìn)制翻譯器的廣泛運(yùn)用，程序在動(dòng)態(tài)二進(jìn)制翻譯器上運(yùn)行的機(jī)會(huì) 將會(huì)越來(lái)越多。因此，本文認(rèn)為在針對(duì)某一體系結(jié)構(gòu)編譯源代碼生成二進(jìn)制碼的 時(shí)候，不僅需要考慮該二進(jìn)制碼在該體系結(jié)構(gòu)上執(zhí)行的性能，而且需要考慮該二 進(jìn)制碼今后在動(dòng)態(tài)二進(jìn)制翻譯器上的執(zhí)行性能【2 6 】。在靜態(tài)編譯源程序的時(shí)候加 3 簡(jiǎn)介 入對(duì)動(dòng)態(tài)二進(jìn)制翻譯器的支持將能夠幫助二進(jìn)制碼快速適應(yīng)動(dòng)態(tài)二進(jìn)制翻譯器 的執(zhí)行環(huán)境，并且通過(guò)動(dòng)態(tài)二進(jìn)制翻譯器被快速移植到新的體系結(jié)構(gòu)上，同時(shí)盡 可能降低程序的性能損失。因此，本文認(rèn)為將原先獨(dú)立的兩個(gè)系統(tǒng)，靜態(tài)編譯器 系統(tǒng)和動(dòng)態(tài)二進(jìn)制翻譯器系統(tǒng)視為一個(gè)系統(tǒng)能夠從一個(gè)嶄新的角度來(lái)提高源二 進(jìn)制碼在動(dòng)態(tài)二進(jìn)制翻譯器上的執(zhí)行性能。當(dāng)然，這也要求在動(dòng)態(tài)二進(jìn)制翻譯器 中加入的注解信息具有通用性和體系結(jié)構(gòu)無(wú)關(guān)性，即注解信息能夠被不同體系結(jié) 構(gòu)的動(dòng)態(tài)二進(jìn)制翻譯器所利用。 另外，本文所提的方法還能夠幫助那些希望所開(kāi)發(fā)的軟件能夠在不同平臺(tái)， 或者在將來(lái)的平臺(tái)上運(yùn)行的軟件開(kāi)發(fā)者。雖然他們希望看到自己的軟件運(yùn)行在其 他的體系結(jié)構(gòu)上或者新的體系結(jié)構(gòu)上，但是他們往往缺乏足夠的人力資源或者其 他資源將軟件移植到其它體系結(jié)構(gòu)或平臺(tái)上，或者他們?cè)诘却碌捏w系結(jié)構(gòu)或平 臺(tái)趨于成熟。此時(shí)，如果動(dòng)態(tài)二進(jìn)制翻譯器能夠提供他們可觀的性能，那么動(dòng)態(tài) 二進(jìn)制翻譯技術(shù)對(duì)于他們而言將十分有吸引力。我們相信這些軟件開(kāi)發(fā)者將很樂(lè) 意接受一個(gè)高效的，針對(duì)動(dòng)態(tài)二進(jìn)制翻譯器優(yōu)化的靜態(tài)編譯器。這個(gè)靜態(tài)編譯器 能夠編譯出帶有動(dòng)態(tài)二進(jìn)制翻譯器優(yōu)化相關(guān)的注解信息的二進(jìn)制程序，幫助他們 的軟件在動(dòng)態(tài)二進(jìn)制翻譯器上獲得額外的性能提升。 同樣，我們的方法還能夠幫助提高那些遺留軟件在動(dòng)態(tài)二進(jìn)制翻譯器上的性 能。盡管該方法需要軟件開(kāi)發(fā)者重新編譯他們的軟件，但是這并不會(huì)像軟件移植 那樣帶來(lái)額外的代碼修改，軟件測(cè)試和軟件驗(yàn)證，更不會(huì)對(duì)軟件的質(zhì)量帶來(lái)任何 威脅。而且我們的方法可以被用來(lái)僅僅編譯那些核心的，性能關(guān)鍵的軟件模塊， 而無(wú)需重新編譯所有的源代碼，這樣可以進(jìn)一步減少軟件重新編譯的開(kāi)銷。因此 我們相信注解信息制導(dǎo)的動(dòng)態(tài)二進(jìn)制翻譯器優(yōu)化能夠幫助那些軟件開(kāi)發(fā)者和那 些急需在新的體系結(jié)構(gòu)上改善性能的遺留軟件，具有相當(dāng)不錯(cuò)的應(yīng)用前景。 1 3 注解信息制導(dǎo)的動(dòng)態(tài)二進(jìn)制翻譯器優(yōu)化簡(jiǎn)介 本文從一個(gè)創(chuàng)新的角度提出了在動(dòng)態(tài)二進(jìn)制翻譯器中進(jìn)一步優(yōu)化翻譯碼的方 法。該方法收集源高級(jí)語(yǔ)言在靜態(tài)編譯過(guò)程中的有用信息，在最終生成的二進(jìn)制 文件中加入一個(gè)額外的信息段來(lái)描述該二進(jìn)制程序的行為，并將此信息傳遞給動(dòng) 態(tài)二進(jìn)制翻譯器。圖1 3 給出了該方法的框架。我們定義該額外信息為注解信息， 并定義二進(jìn)制文件中的額外信息段為注解信息段。注解信息由靜態(tài)編譯器生成并 按照預(yù)先定義好的格式存儲(chǔ)在二進(jìn)制文件的注解信息段中，動(dòng)態(tài)二進(jìn)制翻譯器中 的注解信息分析器會(huì)根據(jù)該格式將注解信息提取出來(lái)供優(yōu)化翻譯碼所用。當(dāng)含有 注解信息段的二進(jìn)制文件執(zhí)行在源體系結(jié)構(gòu)或者沒(méi)有注解信息分析器的動(dòng)態(tài)二 進(jìn)制翻譯器上時(shí)，注解信息段將不會(huì)對(duì)該二進(jìn)制程序的正常執(zhí)行帶來(lái)任何影響。 9 簡(jiǎn)介 在圖1 3 所示的注解信息制導(dǎo)的動(dòng)態(tài)二進(jìn)制翻譯框架中，可以在靜態(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í)行階段，通過(guò)結(jié)合靜態(tài)編譯收集得到的 信息和p g o 執(zhí)行得到的反饋信息，可以在靜態(tài)編譯階段生成更加準(zhǔn)確的注解信 息。同樣在動(dòng)態(tài)二進(jìn)制翻譯器中，可以將注解信息和動(dòng)態(tài)收集到的程序執(zhí)行行為 信息相結(jié)合，從而對(duì)翻譯碼進(jìn)行更有針對(duì)性的優(yōu)化。注解信息不僅可以用于翻譯 碼的優(yōu)化，而且也可以用于降低動(dòng)態(tài)二進(jìn)制翻譯器的翻譯優(yōu)化開(kāi)銷，本文將重點(diǎn) 關(guān)注那些能夠被用于指導(dǎo)翻譯碼優(yōu)化的注解信息。 圖1 3 ：注解信息制導(dǎo)動(dòng)態(tài)二進(jìn)制翻譯的基本框架 1 4 注解信息制導(dǎo)的動(dòng)態(tài)二進(jìn)制翻譯器內(nèi)存優(yōu)化 本文著重于注解信息制導(dǎo)的動(dòng)態(tài)二進(jìn)制翻譯器內(nèi)存優(yōu)化，尤其關(guān)注那些能夠 被翻譯成寄存器訪問(wèn)的訪存指令。在靜態(tài)編譯階段，只要一個(gè)變量符合下述條件， 靜態(tài)編譯器就可以在中間語(yǔ)言中將它表示成一個(gè)虛擬寄存器( 在g c c 中被稱為 偽寄存器) 。該變量不是v o l a t i l e 變量，對(duì)其他線程不可見(jiàn)，并且它的地址沒(méi)有 被其它指令引用。盡管寄存器分配會(huì)竭盡所能為每一個(gè)虛擬寄存器分配一個(gè)物理 寄存器，但有些時(shí)候靜態(tài)編譯器迫于有限的物理寄存器數(shù)目，還是不得不用內(nèi)存 空間來(lái)表示某些虛擬寄存器。在動(dòng)態(tài)二進(jìn)制翻譯的過(guò)程中，如果目標(biāo)體系結(jié)構(gòu)有 空閑的物理寄存器，這些用來(lái)表示虛擬寄存器的內(nèi)存空間就可以被重新映射回物 理寄存器。我們定義那些用于表示虛擬寄存器的內(nèi)存空間為可寄存器化內(nèi)存空間 1 0 簡(jiǎn)介 ( r e g i s t e r i z a b l em e m o r y ) ，簡(jiǎn)稱r e m 。同時(shí)定義那些訪問(wèn)可寄存器化內(nèi)存空問(wèn) 的訪存指令為r e m 指令。 一個(gè)r e m 指令的例子如圖1 - 4 所示，圖的左面是用c + + 語(yǔ)言寫(xiě)的函數(shù)加d l ， 右面是對(duì)應(yīng)于該函數(shù)的i a - 3 2 0 二進(jìn)制碼片斷。函數(shù)f o o o 中有四個(gè)局部變量，分 別是i ，j ，k ，塒，變量七和明不是r e m ，因?yàn)樵诤瘮?shù)f o o o 調(diào)用函數(shù)# n c o 時(shí)， 變量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)編譯的時(shí)候，變量塒 是必須被存放在內(nèi)存堆棧上的。變量i 和，是r e m 變量，由圖1 4 所示，與變 量i 相對(duì)應(yīng)的堆?？臻g是 e b p - 2 8 1 ，而與變量，相對(duì)應(yīng)的不僅有堆?？臻g e b p 2 町， 還有寄存器p a x 。如果有足夠的物理寄存器，那么r e m 變量i ，j 在靜態(tài)編譯優(yōu) 化時(shí)可以被放入到寄存器中，而無(wú)需存放在堆棧上。如圖1 - 4 右半部分所示，當(dāng) r e m 變量，的值被指令m o ve a x , d w o r dp 豫 e b p - 2 q 載入到寄存器e a x 之后， 后續(xù)指令對(duì)r e m 變量_ ，的訪問(wèn)就可以直接訪問(wèn)e a x ，而無(wú)需從堆棧上再次載入。 但是迫于物理寄存器數(shù)目有限，r e m 變量無(wú)法常駐于寄存器之中。堆?？臻g 心細(xì)一2 8 1 ， e b p - 2 4 可被認(rèn)為是r e m ，而訪問(wèn)這兩個(gè)內(nèi)存地址的內(nèi)存指令是r e m 指令。如果有多余的寄存器，動(dòng)態(tài)二進(jìn)制翻譯器可以將這兩個(gè)r e m 空間映射到 目標(biāo)體系結(jié)構(gòu)的物理寄存器中，同時(shí)將r e m 指令翻譯成寄存器訪問(wèn)指令。 一 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 指令的例子 簡(jiǎn)介 除了寄存器化，給予r e m 指令的特性，本文也研究了其他諸如放寬m e m o r y o r d e r i n g 的限制，加強(qiáng)訪存指令的地址消岐和放寬精確異常處理等內(nèi)存優(yōu)化方 法，將在下文中詳細(xì)闡述。 g c c 是一個(gè)被廣泛應(yīng)用的開(kāi)源靜態(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 。公司開(kāi)發(fā)的在i t a n i u m 固上運(yùn)行n 3 2 程序的動(dòng)態(tài)二進(jìn)制翻譯器 1 6 】。 我們修改了靜態(tài)編譯器g c c4 0 和動(dòng)態(tài)二進(jìn)制翻譯器i a - 3 2e l ，實(shí)現(xiàn)了注解信 息制導(dǎo)動(dòng)態(tài)二進(jìn)制翻譯的框架。我們通過(guò)修改g c c4 0 ，使之在編譯過(guò)程中收集 與優(yōu)化相關(guān)的注解信息，尤其是r e m 指令相關(guān)信息，最后將生成的注解信息存 放在二進(jìn)制文件的注解信息段。我們也修改i a - 3 2e l ，使之能將二進(jìn)制文件中的 注解信息提取出來(lái)并結(jié)合到翻譯碼的優(yōu)化之中。在利用這些注解信息進(jìn)行了諸如 r e m 空間寄存器化和針對(duì)r e m 指令的其他內(nèi)存優(yōu)化之后，i a - 3 2e l 取得了相 當(dāng)可觀的性能提升。我們用s p e c 2 0 0 0v 1 3 作為我們的基準(zhǔn)測(cè)試程序，注解信息 制導(dǎo)的內(nèi)存優(yōu)化能夠使其在i a - 3 2e l 上獲得不錯(cuò)的性能提升。實(shí)驗(yàn)數(shù)據(jù)表明， i a - 3 2e l 能夠通過(guò)利用注解信息優(yōu)化翻譯碼提高s p e c f p 2 0 0 0 的總體性能達(dá) 1 5 0 3 之多，提高s p e c i n t 2 0 0 0 的總體性能1 2 1 。 本文剩余部分將按如下順序展開(kāi)。在第二部分，我們將著重描述注解信息的 格式，以及如何在靜態(tài)編譯器中生成注解信息和在動(dòng)態(tài)二進(jìn)制翻譯器中讀取注解 信息。第三部分將著重討論基于注解信息的翻譯碼優(yōu)化，詳細(xì)討論包括寄存器化， 放寬m e m o r yo r d e r i n g 的限制，加強(qiáng)訪存指令的地址消岐和放寬精確異常處理等 基于r e m 指令注解信息的內(nèi)存優(yōu)化。在第四部分，我們將展示注解信息制導(dǎo)的 動(dòng)態(tài)二進(jìn)制翻譯優(yōu)化的試驗(yàn)數(shù)據(jù)，并分析其優(yōu)化效果，給予相應(yīng)的評(píng)價(jià)。最后我 們將在第五部分討論相關(guān)工作，在第六部分對(duì)全文進(jìn)行總結(jié)。 注解信息 2 注鰓信息 2 。1 注解信息格式 注解信息是按照一定的格式保存在二進(jìn)制文件的注解信息段中的，靜態(tài)編譯 器按照預(yù)先定義的注解信息格式將注解信息寫(xiě)入到注解信息段中，動(dòng)態(tài)二進(jìn)制翻 譯器也按照該格式將注解信息從二進(jìn)制文件中讀出。因此，定義一個(gè)能夠快速讀 取，便于擴(kuò)展的注解信息格式尤為重要。 2 1 1 通用注解信息格式 為了便于管理和對(duì)注解信息進(jìn)行分類，我們以函數(shù)為注解信息的基本單位， 并定義其為函數(shù)注解信息。每一個(gè)函數(shù)注解信息中記錄著與該函數(shù)相關(guān)的注解信 息。二進(jìn)制文件的注解信息段是由若干個(gè)函數(shù)注解信息組成的，圖2 1 給出了一 個(gè)函數(shù)注解信息的格式。 每個(gè)函數(shù)注解信息都有一個(gè)函數(shù)注解信息頭，用于描述該函數(shù)的一些特性。 除了函數(shù)注解信息頭，函數(shù)注解信息還包括代碼區(qū)間注解信息，代碼區(qū)間的范圍 可以是函數(shù)中某一連續(xù)地址的代碼段，也可以是整個(gè)函數(shù)本身。函數(shù)注解信息可 以由一個(gè)或者多個(gè)代碼區(qū)間注解信息組成。 函數(shù)注解信息頭描述的是與該函數(shù)相關(guān)的一些信息和特性，例如函數(shù)入口地 址和函數(shù)長(zhǎng)度能夠給出所有在函數(shù)內(nèi)的二進(jìn)制碼的范圍。函數(shù)注解信息頭的大小 是固定的，但是函數(shù)注解信息內(nèi)有多少個(gè)代碼區(qū)間注解信息以及函數(shù)注解信息本 身的大小是不定的。為了保證注解信息能夠自我描述并且易于動(dòng)態(tài)二進(jìn)制翻譯器 快速定位和讀取，在函數(shù)注解信息頭中加入了兩個(gè)額外的字段，函數(shù)注解信息長(zhǎng) 度和代碼區(qū)間注解信息的個(gè)數(shù)。前者給出了該函數(shù)注解信息的總長(zhǎng)度，后者則給 出了在該函數(shù)注解信息中有多少個(gè)代碼區(qū)間注解信息。函數(shù)注解信息頭中還可以 加入其它字段，例如驗(yàn)證字段，可用來(lái)標(biāo)明當(dāng)前注解信息格式的版本號(hào)，如果該 版本號(hào)和動(dòng)態(tài)二進(jìn)制翻譯器所預(yù)期的版本號(hào)不相符合，那么動(dòng)態(tài)二進(jìn)制翻譯器可 以選擇不讀取該函數(shù)注解信息。 代碼區(qū)間注解信息描述的是函數(shù)中某一連續(xù)地址區(qū)間中的二迸制碼的屬性。 代碼區(qū)間注解信息緊接著函數(shù)注解信息頭按任意順序排列。代碼區(qū)間注解信息由 代碼區(qū)間注解信息頭和若干注解信息記錄組成。 1 3 注解信息 代碼區(qū)間注解信息頭類似函數(shù)信息頭，不僅描述了該代碼區(qū)間的范圍，而且 描述了該代碼區(qū)間注解信息的長(zhǎng)度。為了能夠有效的減少代碼區(qū)間注解信息的總 長(zhǎng)度，代碼區(qū)間起始地址和結(jié)束地址用它們和函數(shù)起始地址的偏移量來(lái)表示。根 據(jù)函數(shù)長(zhǎng)度不同，該偏移量字段的大小也可隨之改變，我們可以在函數(shù)注解信息 頭的保留字段中標(biāo)明代碼區(qū)間注解信息頭中偏移量字段的大小。通常情況下，代 碼區(qū)間起始地址和結(jié)束地址的字段僅需兩個(gè)字節(jié)即可。 注解信息 段 函數(shù)注解j 礁裟i，一一一一一 l霪餮窘 霪囂唇雪一注解記錄 卜 萋魯垡跫 二l 簍1 一一一一一 信息1 注解記錄 頭 蔭數(shù)起始地址 函數(shù)長(zhǎng)度 函數(shù)注解信息長(zhǎng)度 代碼區(qū)聞注解信息 數(shù)目 保留字段 代碼區(qū)間起始地址 代碼區(qū)間結(jié)柬地址 代碼區(qū)間注解信息 長(zhǎng)度 注解記錄數(shù)日 注解記錄類型 注解記錄長(zhǎng)度 注解記錄體 另一個(gè)注解記錄 另一個(gè)代碼區(qū)間 圖2 1 ：通用注解信息格式 每一個(gè)代碼區(qū)間注解信息中可以包括若干條注解記錄。每條注解記錄的長(zhǎng)度 并不固定，而且可以用來(lái)記錄不同種類的注解信息。注解記錄中保存的是描述該 1 4 注解信息 代碼區(qū)間的注解信息。每條注解記錄都有注解記錄頭和注解記錄體組成。注解記 錄頭不僅描述了該注解記錄的長(zhǎng)度，而且給出了該注解記錄的具體類型。每一個(gè) 注解記錄類型都可以按照各自的格式存儲(chǔ)注解信息。 上述通用注解信息格式具有如下特點(diǎn)：1 ) 簡(jiǎn)潔2 ) 易于讀取3 ) 自我描述4 ) 靈活性和擴(kuò)展性5 ) 平臺(tái)無(wú)關(guān)性。 2 1 2r e m 注解記錄格式 因?yàn)閞 e m 是按照函數(shù)為單位劃分的，因此我們選擇為每一個(gè)函數(shù)注解信息 加入一條r e m 注解記錄來(lái)標(biāo)示該函數(shù)中的r e m 指令。首先，我們尋找出所有 的r e m 指令，并且按照其訪問(wèn)的r e m 地址對(duì)它們進(jìn)行分組。然后為每一組r e m 指令進(jìn)行編號(hào)，稱之為r e m 號(hào)。此時(shí)，每一條r e m 指令都將獲得一個(gè)r e m 號(hào)， 該號(hào)可用于標(biāo)明r e m 指令訪問(wèn)的r e m 地址。 其實(shí)，我們通過(guò)生成初始r e m 映射表來(lái)標(biāo)示r e m 指令在源二迸制碼中的位 置。我們依據(jù)該函數(shù)的源二進(jìn)制碼的大小生成一個(gè)相同大小的初始g e m 映射表 并將其初始化為全零。我們對(duì)源二進(jìn)制碼中的每一條r e m 指令，計(jì)算其相對(duì)于 該函數(shù)起始地址的偏移量，并依據(jù)該偏移量在初始r e m 映射表中找到對(duì)應(yīng)的字 節(jié)，將該r e m 指令的g e m 號(hào)寫(xiě)入到該偏移量中。至此，初始g e m 映射表就被 生成了。 最后，我們將初始g e m 映射表進(jìn)一步壓縮后生成r e m 注解記錄。我們分別 對(duì)初始r e m 映射表中的數(shù)據(jù)零和g e m 號(hào)進(jìn)行壓縮。在r e m 注解信息中，我們 定義每一個(gè)字節(jié)要么用來(lái)表示在初始r e m 映射表中連續(xù)數(shù)據(jù)零的個(gè)數(shù)，要么用 來(lái)表示一個(gè)g e m 號(hào)。因此，我們定義在r e m 注解信息中，當(dāng)一個(gè)字節(jié)的最高 比特位為0 時(shí)，該字節(jié)的剩余7 位比特將被用于表示連續(xù)數(shù)據(jù)零的數(shù)目，而當(dāng)一 個(gè)字節(jié)的最高比特位為l 時(shí)，該字節(jié)的剩余7 位比特則給出了一個(gè)r e m 號(hào)。由 此，我們可將一個(gè)初始g e m 映射表壓縮成r e m 注解記錄，并最終將該記錄保 存在注解信息段中。 因?yàn)槲覀儍H用7 位比特來(lái)表示g e m 號(hào)或者表示連續(xù)數(shù)據(jù)零，因此其最大可 表示范圍為1 2 8 。當(dāng)函數(shù)中出現(xiàn)超過(guò)1 2 8 個(gè)連續(xù)數(shù)據(jù)零時(shí)，我們可以用兩個(gè)或多 個(gè)連續(xù)最高比特位為0 的字節(jié)來(lái)表示這些連續(xù)數(shù)據(jù)零。在注解信息中連續(xù)n 個(gè) 最高位比特為零的字節(jié)可以表示n * 1 2 8 個(gè)連續(xù)數(shù)據(jù)零。而當(dāng)函數(shù)中出現(xiàn)超過(guò)1 2 8 個(gè)g e m 號(hào)時(shí)，我們可以通過(guò)擴(kuò)大注解記錄中用來(lái)表示r e m 號(hào)的數(shù)據(jù)長(zhǎng)度來(lái)實(shí) 現(xiàn)，例如我們可以將兩個(gè)連續(xù)字節(jié)視為整體來(lái)表示g e m 號(hào)，這樣就可以有1 5 位比特的數(shù)據(jù)來(lái)表示r e m 號(hào)，從而可以表示多達(dá)3 2 7 6 8 個(gè)r e m 號(hào)，對(duì)于一般 1 5 注解信息 的函數(shù)而言已經(jīng)綽綽有余了。對(duì)于不同的壓縮方法，我們可以在注解記錄頭中的 注解記錄類型中用比特位表明，方便動(dòng)態(tài)二進(jìn)制翻譯器讀取。 我們根據(jù)圖l - 4 中的代碼片段生成其相應(yīng)的r e m 注解記錄來(lái)進(jìn)一步描述 r e m 注解記錄的生成過(guò)程，如圖2 2 所示。圖中共有三條r e m 指令，為了方 便，我們用指令中訪存地址的立即數(shù)偏移作為該指令的r e m 號(hào)，例如指令a d d d w o r d p 豫膨助0 8 1 ，e a x 的r e m 號(hào)是2 8 。指令i n c d w o r d p 豫 e b p - 2 8 1 相對(duì) 于該代碼區(qū)間的首地址偏移量為8 ，因此在初始r e m 映射表中，偏移量為8 的 地方填入該r e m 指令的r e m 號(hào)，2 8 。同理，另外兩條r e a m 指令的r e m 號(hào)分 別被寫(xiě)入到初始r e m 映射表中偏移量為1 5 和3 4 的地方。初始r e m 映射表中 的其余字節(jié)均為零。我們將根據(jù)該初始r e m 映射表壓縮生成r e m 注解記錄。 初始r e m 映射表中的起始連續(xù)7 個(gè)零在r e m 注解記錄中被表示為o x 7 。初始 r e m 映射表中的第8 個(gè)字節(jié)2 8 在r e m 注解記錄中被表示成r e m 號(hào)0 x 9 c ，因 為r e m 號(hào)總數(shù)小于1 2 8 ，因此我們?cè)趓 e m 注解記錄中用一個(gè)字節(jié)來(lái)表示r e m 號(hào)。最后我們將生成一個(gè)7 個(gè)字節(jié)大小的注解記錄來(lái)表示圖中源二進(jìn)制碼中的 r e m 指令。 圖2 2 ：r e m 注解記錄格式 1 6 注解信息 2 。2 在靜態(tài)編譯器中生成注解信息 在二進(jìn)制文件中生成注解信息不僅需要修改編譯器，還需要修改匯編器和鏈 接器。我們選擇開(kāi)源的靜態(tài)編譯器g c c4 0 1 2 2 來(lái)進(jìn)行實(shí)驗(yàn)。g c c 和其它流行的 靜態(tài)編譯器一樣，有一整套工具來(lái)完成整個(gè)編譯過(guò)程。當(dāng)用戶在命令行中執(zhí)行 g c c 命令時(shí)，以下工具c c l ，a s 和塒會(huì)分別按序被調(diào)用來(lái)完成整個(gè)編譯工作。源 高級(jí)語(yǔ)言代碼首先會(huì)由c c l 編譯成匯編碼，然后再由匯編器a s 翻譯生成可重定 向的目標(biāo)文件。最終，鏈接器膃將所有的可重定向目標(biāo)文件鏈接起來(lái)生成最終 的可執(zhí)行二進(jìn)制文件。因此，為了在最終可執(zhí)行的二進(jìn)制文件中能夠生成注解信 息段，我們不僅需要修改g c c 的編譯器c c l ，也需要修改g c c 的匯編器a s 和 鏈接器搿。 大多數(shù)注解信息是在編譯階段收集得到的。編譯器首先對(duì)高級(jí)語(yǔ)言編寫(xiě)的源 程序進(jìn)行解析，并且以函數(shù)為單位通過(guò)中間語(yǔ)言生成語(yǔ)法分析樹(shù)。然后對(duì)語(yǔ)法分 析樹(shù)進(jìn)行多次遍歷，并不斷對(duì)中間語(yǔ)言進(jìn)行優(yōu)化，最終將優(yōu)化完畢的語(yǔ)法分析樹(shù) 編譯成匯編指令。在這個(gè)過(guò)程中，高級(jí)語(yǔ)言的信息逐漸被丟失，因此，編譯器中 的注解信息生成器在此階段的主要任務(wù)是分析并整理出有用的注解信息。以收集 r e m 指令的注解信息為例，首先我們?cè)诩拇嫫鞣峙淝罢页鏊袀渭拇嫫? p s e u d o r e g i s t e r ) 【2 2 】。偽寄存器中存放的是所有未被聲明為v o l a t i l e 并且沒(méi)有被其它任 何指令引用的標(biāo)量型變量。當(dāng)g c c 開(kāi)始進(jìn)行局部寄存器分配，全局寄存器分配 和寄存器重新分配【2 2 】時(shí)，我們記錄那些會(huì)被暫時(shí)寫(xiě)入到堆棧上的偽寄存器，并 且跟蹤記錄所有訪問(wèn)這些堆棧內(nèi)存空間的訪存指令。在寄存器分配結(jié)束之后，我 們還會(huì)在其后續(xù)優(yōu)化中跟蹤記錄我們所收集到的這些訪存指令，以察看這些指令 是否被其他優(yōu)化更新或者刪除，繼而保證該階段所收集的注解信息的正確性。最 終，我們將收集到的初始注解信息和匯編指令一起寫(xiě)入到編譯器生成的匯編文件 中。 我們修改匯編器使之不僅會(huì)將匯編文件中的初始注解信息按照上一節(jié)描述 的注解信息格式寫(xiě)入目標(biāo)文件，而且會(huì)為那些可重定向的注解信息生成相應(yīng)的樁 ( s t u b s ) 。在每個(gè)目標(biāo)文件中，都會(huì)生成兩個(gè)按照標(biāo)準(zhǔn)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 文件格式生成的注解信息段，個(gè)是常規(guī)的注解信息段，另一個(gè)是可重定向 的注解信息段。匯編器會(huì)按照注解信息的類型分別將他們寫(xiě)入到常規(guī)的注解信息 段或者可重定向的注解信息段。例如類似函數(shù)長(zhǎng)度之類的注解信息在將匯編指令 進(jìn)行二進(jìn)制編碼的時(shí)候就可確定，因此匯編器會(huì)將其寫(xiě)入到常規(guī)的注解信息段 中。而像函數(shù)入口地址之類的注解信息要到最后鏈接的時(shí)候才能確定，因此匯編 1 7 注解信息 器會(huì)在常規(guī)的注解信息段中為其保留一個(gè)樁，并將該樁寫(xiě)入到可重定向的注解信 息段的數(shù)據(jù)項(xiàng)中。 最后在鏈接器中，所有可重定向的目標(biāo)文件會(huì)被鏈接并生成最終的可執(zhí)行二 進(jìn)制文件。因此在鏈接時(shí)，需要計(jì)算那些可重定向的注解信息的值，并根據(jù)可重 定向的注解信息段中的數(shù)據(jù)項(xiàng)獲得保留樁的地址，將計(jì)算值回填入常規(guī)注解信息 段中的保留樁。當(dāng)鏈接全部完成后，鏈接器所要做的就是計(jì)算最終注解信息段的 大小，并在二進(jìn)制文件中預(yù)留足夠的空間，然后合并所有目標(biāo)文件中的注解信息 段生成一個(gè)最終注解信息段，最后將此注解信息段寫(xiě)入到可執(zhí)行二進(jìn)制文件中。 2 。3 在動(dòng)態(tài)二進(jìn)制翻譯器中讀取注解信息 程序往往會(huì)將大多數(shù)執(zhí)行時(shí)間花費(fèi)在很小一段代碼上。同時(shí)，為了避免動(dòng)態(tài) 二進(jìn)制翻譯器讀取注解信息的開(kāi)銷過(guò)高，我們提出了一種分步，按需讀取注解信 息的方法。我們?cè)趧?dòng)態(tài)二進(jìn)制翻譯器中加入了一個(gè)注解信息分析器，如圖2 - 3 所示。注解信息分析器一方面從源二進(jìn)制碼中讀取注解信息，并將這些注解信息 整理后以內(nèi)部表示的形式存儲(chǔ)在動(dòng)態(tài)二進(jìn)制翻譯器的內(nèi)存中。另一方面，動(dòng)態(tài)二 進(jìn)制翻譯器在翻譯的過(guò)程中也可以通過(guò)注解信息分析器查詢感興趣的注解信息。 圖2 3 ：注解信息分析器 在可執(zhí)行二進(jìn)制文件被裝載時(shí)，注解信息分析器會(huì)掃描注解信息段，并為每 個(gè)函數(shù)注解信息建立索引。注解信息分析器會(huì)依次讀入每個(gè)函數(shù)注解信息的地 址，以及該函數(shù)注解信息的函數(shù)注解信息頭。函數(shù)注解信息頭包括函數(shù)起始地址， 函數(shù)長(zhǎng)度，函數(shù)注解信息長(zhǎng)度等字段。為了加速查詢一個(gè)指令地址所在的函數(shù)， 1 8 注解信息 我們利用a v l 2 4 樹(shù)來(lái)存放索引信息，該樹(shù)被稱為注解信息a v l 樹(shù)。所有注解 信息a v l 樹(shù)的節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)注解信息段中的一個(gè)函數(shù)注解信息，其內(nèi)容包含 函數(shù)起始地址，函數(shù)長(zhǎng)度，函數(shù)注解信息首地址，注解信息是否被讀取等字段。 注解信息a v l 樹(shù)中節(jié)點(diǎn)的關(guān)鍵字是函數(shù)起始地址。注解信息索引建立的算法如 圖2 - 4 所示。分步讀取的方法使注解信息分析器在程序起始階段只需要讀取- d , 段注解信息即可，避免了在