2022年2022年可执行代码级优化器生成框 .pdf

! # $% % % & % % () # $&* *+, #清华大学学报-自然科学版./ 0 12 34567 83 2 9- :2;0期*% % ( =? AB( =# B* C , +D$*D% & $* D+可执行代码级优化器生成框架蒋琛=戴桂兰=戴军=张素琴-清华大学计算机科学与技术系=北京$% % C( .收稿日期E* % +&$%& %C基金项目E国家自然科学基金资助项目- D% C+% ( .作者简介E蒋琛- $FF& . =女-汉. =广西=硕士研究生G通讯联系人E戴桂兰=助理研究员=H&I 72 A E J72 4AK I72 A BL12 345 67BJ 6B: 3摘要E编 译 基 础 设 施 生 成 的 编 译 器 对 与 目 标 机 特 征 相 关的优化支持不足!同时嵌入式应用系统的发展要求高质量的目 标 代 码!为 此!提 出 一 种 可 执 行 代 码 级 优 化 器 生 成 框 架 # $ %& ( )* + , - ./0+1 2 1 3 45 6 4, +1 / 67 4, 2 8 / 49: !以 及该框架的关键支撑技术;与现有的编译器生成工具相结合!如$ ) / 2 01 . 4 ) / . ) +1 / 6: !可以实现高质量编译器的快速开发!并可以方便地充分利用目标机特点进行相关优化!提高目标代码质量;实验结果证明! # $ %是一个简便?灵活且有效的可执行代码级优化器生成工具;关键词E编译器生成工具优化器可执行代码中图分类号E 0 M +$(文献标识码E N文章编号E$ % % % & % % (- *% % ( . % & $*D% &% (OPQ R STU VW QXYT Z Z Q Q _Q UTZ X_ U Q a X bcd e f g h i j k=le dg m no pk=led cmk=q r e f gsmt nk- u QYU T Q _ TXv XYST Q wR Z Q_R Q U_xy QR z_XW X =y | Z _zSU _ Z Q | Z T = ! Q ZZ _ #$% &=vzZ _U.V| T UR T EM (13L: I ) 2 A(14 3(7LJ * + : I ) 2A (2 3,(71L( 6: L6( 142 92 316 ,2 : 2 3 L1 6) ) (L,7(: 52L: L6( (A7LJ ) L2 I 2 -7L2 31BN3. : 6L7* A ) L2I 2-( 43(7L2 3 ,(7I / (0 - H1 2 3 . / 71 J9A ) J=/ 52 : 542 912 I ) ( 9J: J467A 2 L+, (I * JJ J7) ) A 2 : 7L2 31+1LI 1B5 2 L5: I ) 2 A (2 3, (71L(6: L6(116: 5712 ) )- 2 # 8: I ) 2A ( : AA : L2 3. =L 5H 1 2 3 : 73 462 : 0A + : I ) 17 32 3L4( 7LJ43(7L2 3 392 ( 3I 3L , ( 5245 467A 2 L+ : I) 2 A (1B0 5H 1 2 3 : 737A 12 I ) ( 9 L5 , 237A: J 467A2 L+ * + L702 3 47 J973L74 , L5 1) : 27AI 7: 52 3 : 57(7: L( 2 1L2 : 1BH . ) ( 2 I 3L7A (16A L11 5 /L57L L5H 1 2 3: 73 ,A . 2 * A + 73J , ,2: 2 3LA + 43 (7L . : 6L7* A ) L2 I 2 -(1B6 Q aX x| E: I ) 2 A (7 76L I 7L2 :43(7L (7 ) L2I 2-( 7 . : 6L7* A : J嵌入式系统复杂性的不断增加和特定应用体系结构的层出不穷使得对自动生成工具的需求越来越迫切8$9G对于编译环境而言=到目前为止=人们开发了广泛使用的编译基础设施或可重定向编译器=例如2 ) ) - 2 # 8: I ) 2A ( : A A : L2 3 . : ; ) )- A 73): I ) 2A ( .和 8 !3 - L73, (J832 9(12 L+ 23L(I J2 &7L , (I 7L.等8*9G这些生成工具虽然大大提高了编译系统的开发效率7但其结果编译器所产生的目标代码的质量往往不能令人满意G于是=近年来=优化器自动生成工具的研究开始引起人们的关注=具有代 表 性 的 工 作 是 汇 编 代 码 级 优 化 器 生 成 框 架-M 1 MN # .8+9G据了解=目前尚无可执行代码级优化器自动生成工具的研究成果出现G在可执行代码级=由于一些找不到源码的库文件的链入=扩展了优化范围7同时=由于汇编程序充分展开=且没有失去任何信息=为优 化 提供了准确的 信 息8* 97另 外=可 执 行 代 码 充分地体现了目标机的特征=更易于进行与目标机相关的优化G由此可见=在可执行代码级会比在汇编代码级或中间表示级进行优化效果更加明显G本 文 提 出 的 可 执 行 代 码 级 优 化 器 生 成 框 架H1 2 3- . :6L7*A ) L2 I 2-( 43(7L2 3 ,(7I ?框架结构H1 2 3的结构如图$所示G从图$中可以看出系统的输入为目标机信息=输出为相应目标机的可执行代码级优化器G特定目标机信息主要包括硬件资源:指令集:流水线等=它们是进行与目标机相关的优化必不可少的信息G将目标机信息用一种机器描述语言进行描述=然后经过机器描述语言解析器=提取信息存储于目标机体系结构数据库中=以便于代码分析器和优化,分析器的构造器的访问G名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 特定目标机的可执行代码级优化器的核心是代码分析器和优化!分析器代码分析器扫描源程序#提取控制流和数据流等信息#构造相应程序表示优化!分析器对代码分析器构造的程序表示进行分析和优化#其结果可以进一步分析和优化#直至生成满意的目标代码 $ %&应能根据目标体系结构数据库 的 信 息#自 动 生 成 相 应 的 代 码 分 析 器 和 优 化!分析器在$ %&存在的情况下#整个编译环境的开发和运行如图(所示#底层是一个完整的编译过程源程序通过编译器生成可执行代码#然后经过可执行代码级优化器#进行与目标机相关的优化#从而生成最终的优化后可执行代码其中#中间层即为$%&系统它为用户提供接口以描述目标体系结构特征#并且允许用户选择优化算法#然后根据用户提供的信息构造特定目标机的优化器可执行代码级优化器生成框架名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 持!因此开发一种专门的机器描述语言用于# $ %&中对体系结构特性的描述是十分必要的! ( 代码分析器的自动生成代码分析器对可执行代码进行预处理完成控制流重构和数据流分析建立相应的数据结构为后续的优化提供基础因此在可执行代码级优化器中占据重要地位!# $ %&作为可执行代码级优化器的生成工具代码分析器的自动生成自然成为其一项重要任务!可执行代码是源程序充分展开和一系列等价变换 的 结 果因 此源 程 序 中 的 结 构 化 信 息 已 不 太 明显!为实现进一步的优化必须能够在可执行代码中重构控制流图作为代码优化的前提!因此 # $ %&应能提供控制流的重构算法并且能保证该算法的通用性!其中控制流重构的难点是间接控制流问题即由于跳转地址不是静态存储于程序中而是在程序执行时存放在某个寄存器中因此需要对跳转和调用指令目标地址进行计算!为了获得所涉及的寄存器中值的信息需要使用程序切片)* + ,技术!限于篇幅有关可执行代码级的程序切片技术在另文中讨论!数据流分析是许多优化技术实现的前提是代码分析器的主要任务之一!由于不同的优化技术所需要的数据流信息各不相同因此也需要在# $ %&中集成多种数据流分析方法! ( -优化技术优化技术种类繁多选择何种优化技术对优化效果具有重要影响!考虑到可执行代码级优化器及其输入文件的特殊性需要选用现有编译器在中间代码级优化中较少采用并且在可执行代码级比较有效的优化技术!例如寄存器分配.指令调度.延时槽填充等这些优化技术在%/ /生成的编译器中没有进行或者进行得不够充分!另外由于实现某些优化技术时进行的代码变换或者由于可执行代码级对程序的充分展开使得某些在中间代码级有效的优化技术在可执行代码级同样有效!例如尾合并分支优化和死代码消除!但由于优化技术的实现是一件费时的工作因此需要在优化效率与工作量方面进行折衷权衡!-实例研究以清华大学自行研制的处理器0 1 2 34为例利 用# $ %&自动 生 成 一个 特 定 目 标 机 的 优 化 器!0 1 2 34是 一款5 67/处 理 器遵 循36 47 89 /体系结构并且在此基础上对流水线进行了修改增加了并行加和并行减指令!下面以实现一种局部指令调度优化技术为例讨论如何利用目标机信息基于# $ %&框架实现一个特定优化器的过程!结 构互锁: ; ?= AB C =DE是0 1 2 34较为特殊的一种硬件特性即由于指令共用一个处理器设备而造成的指令间执行的延时!因为局部指令调度可以利用结构互锁信息在延时槽内调度不具有互锁关系的指令以提高处理器的利用率所以结构互锁信息对于目标代码的优化具有重要意义需要精确描述结构互锁信息!结 构 互 锁 信 息 的 描 述 如 图F所 示其 中7=1 C =D为保留字!EJ8 88: _E名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 节点!的#$%值的计算方法如下&#$%!()*+, -! )存在互锁./ -! )不存在互锁0.! *1 2表/给出%3 4 5可 执 行 代码 级 优 化 器 性 能测试结果6测试在关闭7 89: ;的情况下进行-其中优化前与优化后的测试单位皆为循环数6表3 8? A/ BC ,/ D, ,E2DCFGHHI;JK LMNDN CNCEO/ 2POQA R: MJSG; ; ?PC/ CC ,P/ T EBBB2O,UA H ?899ANDPCNPCOT2P,QA R: MJSG; ; ?V带输出WNBBTEOND OPD,N2TO由表/可知-优化后代码的执行速度比优化前有明显提高-最高达E2DC-最低为/ 2PO-平均为D2PE6X结束语/ W该优化器是在Y 7 7生成的编译器优化的基础上对目标代码进行的再次优化-仍然取得了明显的优化效果6这说明基于QZ Y U生成的可执行代码级优化器可以达到理想的优化效果6NWQZ YU生 成特 定 体 系 结构 可 执行 代 码 级 优化器的过程简单6编译环境开发人员只需用特定的格 式 描 述 机器 信息-选 择 优 化 算法- QZ Y U就 可 以自动生成优化器6可见-利用这种优化器的生成框架-可以大大简化优化器的开发工作6PWQZ YU可 以灵 活 地 生 成特 定 体系 结 构 的 优化器6编译环境开发人员可以选择所采用的优化算法-并且可以扩展已有的优化算法6提出了一种可执行代码级优化器的生成框架-它能够方便高效可靠地为特定体系结构生成优化器-配合现有编译环境生成工具-可以快速生成高质量的编译系统6同时-由于与编译器的相对独立-可执行代码级优化器生成框架能够灵活方便地集成到现有的工具链中6目前完成了可执行代码级优化器生成框架的分析和设计工作-初步实现了可执行代码级优化器生成 框 架 的 原 型-并 针 对 清 华 大 学 自 行 研 制 的%3 4 5芯 片 生 成 了 特 定 体 系 结 构 的 可 执 行 代 码级优化器-取得了比较满意的结果6今后工作的重点是进一步完善优化器生成框架-早日实现产品化6参考文献V1 _aWb/ cd 8e A fgd 2d ; M 8LR; M 8HI;5 L hA IA ?R% IK8?i%: ; A Lg j j I A 98M A ? A ? 7 89: ;kA l GI8M A ? 8?i7 i ;$ ?KM LGl ; ?M 8M A ?bmc2n8?j GL&$ ?i A 8?$ ?KM A M GM ; h %; 9: ? I Ro-/OOO2bNc戴军2目标代码级优化器生成框架研究bmc 2北京&清 华大学-N , , P2mg $pG?2k M Gi o ?5 KM j 8KKZj M A l A q; LY ; ? ; L8M A ?RUL8l ; r Lsbmc2F; A e A ?R&%KA ?R: G84 ?Af ; LKA M o-N, , P2VA ?7: A ?; K; WbPcn 8KM ?; L m25 Z d 5 g t &gL; M 8LR; M 8HI;K oKM ; lh Lj KM j 8KKK j M A l A K8M A ?K8?i8?8IoK; Kbg c 25L 9; ; i A ?RK hg 7 k$Y 5 # g tu Ls K: j ? # 8?RG8R; K- 7 l j A I; LK8?i % I Kh LQl H; i i ; ikoKM ; lKb 7 c 2v8?9 Gf ; LF7 -78?8i 8&g7 -N, , , 2bCc%m# & g: 8Li r 8L; 8?igKK; l HIom ; K9LA j M A ?# 8?RG8R; bd c2%m# / 2P-k88LHLG9s; ?&k 88LI8? i4?Af ; LKA M o-/OOO2bDc%A jU2gKGLf ; oh j L RL8lKIA 9A ? RM; 9: ?A SG; Kb pc 2w x) yz |xyx! y #z !$ z ! ) ! % & -/OOD- VPW &/ N/ EO2bBcFA ?sI ; om -Y8I I8R: ; L n 2gi f 8?9; KA?7 l j GM ; LKb c2k8?mA ; R -7g &g 98i ; lA 9 5 L; KK-/OOB2PBN/蒋琛-等&可执行代码级优化器生成框架名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 可执行代码级优化器生成框架作者：蒋琛， 戴桂兰， 戴军， 张素琴作者单位：清华大学,计算机科学与技术系,北京,100084刊名：清华大学学报(自然科学版)英文刊名：JOURNAL OF TSINGHUA UNIVERSITY(SCIENCE AND TECHNOLOGY)年，卷(期)：2004,44(9)被引用次数：1次参考文献(6条)1. Binkley D;Gallagher KAdvances in Computers 19962. Tip FA survey of program slicing techniques 1995(03)3. TDL: A hardware and Assembly Description Language 19994. Kastner DPORPAN: A retargetable system for postpasss optimisations and analyses 20005. 戴军 目标代码级优化器生成框架研究 20036. Rajiv A RRetargetable Profiling Tools an Their Application in Cache Simulation an CoeInstrumentation 1999引证文献(1条)1. 杨乔 逻辑组态软件中编译器的设计与实现学位论文硕士 2005本文链接： http:/ - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -