（计算机软件与理论专业论文）基于静态类型分析的java程序函数调用图构建方法研究.pdf

硕士学位论文 摘要 函数调用图是编译期对程序中函数调用关系的一种静态描述，在函数调用图中， 节点表示函数，边表示函数之间的调用关系。函数调用图在软件工程领域有广泛的应 用，例如编译优化，过程间数据流分析，回归测试，程序理解等。j a v a 语言的多态机 制及子类对父类函数的覆写，使得无法在编译期静态确定虚函数调用点中接受对象的 实际类型，从而无法实现接受对象和目标函数之间的静态绑定，因此j a v a 程序的函数 调用图只是对实际运行时函数调用关系的一种约近。如何提高虚函数调用的解决效 率，减少函数调用图中结点和边的数量，从而使构建的函数调用图能够更准确的反应 程序执行时函数之间的实际调用关系，一直是程序分析领域的热点和难点阃题。 本文首先结合实例对类层次分析，快速类型分析，和x l r a 三种基于静态类型分析 的虚函数调用解决策略进行了详细说明，并在我们实现的构建函数调用图的原型系统 上通过实验比较了上述三种解决方法的分析精度和分析效率。实验证明了x l r a 方法能 够提高快速类型分析的分析精度，并且证明了快速类型分析能够实现分析精度和分析 效率的最好均衡。 本文在原x t a 方法的基础上，根据类型传播和类型可达思想提出了一种改进的 x t a 方法。改进方法用增量式的方式来考虑程序中函数的可达性，并在过程内类型传 播的基础上，对每个可达函数中的实例化对象类型给定一个可达变量的集合，从而进 一步约减虚函数调用点中接受对象的可能类型。通过实例，说明了改进方法对原有 r a 方法分析精度的提高。 本文进一步发展和完善了f t i p 提出的基于集合的算法描述框架，并给出了在此框 架下类层次分析，快速类型分析，a 和本文提出的改进x 1 r a 的算法描述，从集合 论的角度证明了改进方法相对原方法在分析精度上的提高。 本文设计并实现了一个构建函数调用图的原型系统，该原型系统基于对j a v a 程序 的字节码分析，目前能够实现程序的类层次图和基于类层次分析，快速类型分析和 x r a 方法的函数调用图的构建。 关键词：函数调用图，静态类型分析，虚函数调用，类层次分析，快速类型分析 基于静态类型分析的j a v a 程序函数调用图构建方法研究 a b s t r a c t c a l l 鲫hi sa s 诅t i cd e s c i i p t i o no fn 坨m e t i l o dc a l l i n gr e l a t i o 璐h i po fm ep m g r a mi n c o m p i l i n g 血n e ，i nw h i c ht h en o d e si l l 啪t 均：t em e t h o d sm l dt l l es i d e si i l d i c a ：c ct 1 1 ee v o k i i l g r e l a t i o n s h j pb c t 、e m e t h o d s c a l l 鲫hh 嬲b e 姐u d 研d e l yi i l f t 、v a 饥g i n c e f i n g d o m a i l l ，s 1 1 c hu sc 伽p i l i n go p t i m i z a t i o i l ，i n t e i p r o c e d u r a ld a t an o wa n a l y s i s ，陀g r c s s i o nt e s t p r o g 咖吼d e r s t a n d i n g 缸d o n b u tt h ep o l y m o r p m cm e c h a l l i s mo fj a v a 锄dm c o v e r r i d d c no f m em e t l l o di i lt i l ci n h c r “c dd 船sm a k cm ci l l d e f i n i t e n e s so f m ca c t i l a i 呻eo f 也er e c e i v c r ，t l 碥s t a t i cb o n d i n gb e 铆e e nt i l er c c e i v e r 锄dt t l et a r 舛m 劬o dc 妣n o tb c 碍a l i z e d i i it l l ec o m p l i 盯t i 腓s ot 量l ec a l lg r a p ho fj a v ap r o g 舢i sj u s t 觚印p r o x i m a t i o nf - o ra c t i l a l m e t l l o dc a l l i n gr e l a t i o n 蜥n gm en l l lt i i i i e t h e r e f m ，h o wt oa d v 觚c et h ee m c i e n c yf o r s o l v i n gt h ev i m l a lm e 吐l o dc a l l 锄dr e d u c et l l en u m b c ro f d e s 缸dc d g e so f t h cc a l l 鲫ht o m a k et h eb u i nc a l lg 馏p hr 印他mt h ea c t l l a lm c t l l o dc a l l i n gr e l a t i o nd l m n gt l l ep r o g m m 删n g m o r ep r e c i s c l yi l 硒b e e nt i l eh o t 锄dd i 艏c l l l tp r o b l 锄i l lp r o g r a m 觚a l y s i sd o m a i m f i f s t t 1 1 i sd i s 骶f t a t i o ne x p l a i 】dt 1 1 1 优m a i ns o l m i o n st o 重h e 、，i r t l l a lm e m o dc a l lp m b l e m 丘o m 缸p e r s p e c t i v eo f s t “cc i 嬲s 彻a l y s i si nd e t a i lw i t hc ) 【a m p l e s ，t h e 也i c em a i ns o l l n i o i l s a 糟c l 硒sh i e 埘曲ya i l a l y s i s ，r a p i dt y p ca n a l y s i s 姐dx t a b a s c do nt l l cp r o t 0 哆p es y s t e m f o ra u t o m 砒i c a l l yc a l lg r a p hc o n s 由埘o nw er c a l i z e d ，w ec o m p a r e dt h e s et l 】r e cs o l m i o n s 黝l y t i c a lp r e c i s i o n 锄d 黝i 妒c a le 伍c i e n c y w ep m v e dx t ac o u l dg e tt h eb e s t 柚a l y t i c a l p r c c i s i o na n dr 印i dt y p ea i l a l y s i sc o i l l dg e tt l l eb c s tb a l a l l c eb e t w e e n 删y t i c a lp r e c i s i o n 锄d 趾a i y t i c a le m c i e n c y b a s e d m c 嘶g i i l a lx t am e m o d ，t l l i sd i 跚r t a t i o np r e s e n t e d 觚i i n p m v c d a m e t l l o d l l s i i l gt y p ep r o p a g a t i 锄dt y p ea c c e s s i b i l i t y t l l i si 玎1 p r o v e dm e t l l o dc o n s i d e r e dm c a c c e s s i b i l i t yo fm e 血o d i i l p r o g 姗i n c 托m e m a l l y ，b a s e do l lm ei n t r a p r o c e d u a lt y p e p r o p a g a t i o n 锄ds p e c 湎e das e to f c e s s i b l ev a r i a b l e sa c c o r d i n gt 0t l l ec l 勰so fi l l s t a | 1 c c d o b j e c to f e v e r ya c c e s s i b l em e t l l o di no r d e ft or e d l l c ct t l ep o s s i b l et y p eo f t h er e c e i v 盯胁h e r l y t h ee x a m p i er e p i c s 朗l 协t h ei m p r o v e da l g o r i t h mc 强g c tb c t t e r 粗a l y s i sp r e c i s i o nt l l a nt h eo l d 0 n e m sd i s s e r t a t i o na i s od e v e l o p e da l l d 磷n e dt l l ca 1 9 0 r i t h md c s c r i b i l l g 妇w o r kb 嬲e d o ns e tp r e s e 嗽db yf t i p ，觚dp r e s e i l t e dt t 圮a l g o r i t i l md e s c r i p t i o no fc l a s sh i e r a r c h ya 1 1 a l y s i s ， r a p i dt y p e 趾a l y s i s ，x t aa n dt l l ei m p m v e dx t au n d c rt l l i s 劬m e w o 咄t l l i s 舳m e w o r k 锄 舭i l i t a t et op r o v ct h a tt h e 吼p r 0 v c dx ，r am e t l l o dc o l l l dg e tb e t t 盯a l y t i c a lp r e c i s i o nt l l a n 龇耐g i 删x t a m e t i l o d m r o u 班m e p o i n t o f s c tm e o r yv i e w t h i sd i s s e r t a t i o nd e s i 朗e d 锄dr e a l i z e dap r o 似y p cs y s t c mf o ra u t o m a t i c a l l yc a l l 鲫h i i 硕士学位论文 c 瑕痂g t h ep r o t o t y p eb a do n l eb y t e c o d e 肌l a y s i so fj a 、，ap m 粤a ma l l dc a na c c o m p l i s h t h ec o 删i o no fc l 懿sh i e r a r c l l i c a ld i a g 舳觚dt l l ea u t o m a t i c a l l yc r e a t i n go fc a l l 鲫h b 勰e d t l l ec l 硒sl l i e r a r c h y 趾a l y s i s ，缸tt y p c 锄a l y s i s ，x t a k 吁唧o r d s ：c a ug f a p h ，s 协t i ct y p c 蠲a l y s i s ，v i m m lm e t h o dc a l l ，c l a s sh i e r a r c h ya l y s i s ， r a p i dt y p e 衄l y s i s i 基于静态类型分析的j 胛a 程序函数调用图构建方法研究 插图索引 图1 1 一个虚函数调用的实例2 图1 2 类的虚函数表 图1 3 接口的虚函数表。 。4 图1 4 一个函数调用图的示例5 图1 5 基于堆栈采样的p f i l i l l g 技术1 0 图1 6 基于程序插装的p r o f i l i n g 技术l l 图1 7s a m p l i n g1 1 1 s 咖m e n 诅t i o np r ；o f i l i n g 技术1 l 图2 1 示例程序的类层次图1 6 图2 2 根据类层次分析建立的示例程序的函数调用图1 6 图2 3 根据快速类型分析建立的示例程序的函数调用图1 7 图2 4 根据x t a 构建的示例程序的函数调用图。1 9 图2 5 已有算法构建的函数调用图结点数量的比较2 l 图2 6 已有算法构建的函数调用图边数量的比较2 2 图2 7 已有算法的运行时间比较2 3 图3 1 类型传播图构建过程的示意图2 7 图4 1 一个j a v a 源程序3 7 图4 2 图4 1 对应的字节码文件3 7 图4 3 原型系统设计框架图3 7 图4 4 文件选择界面3 9 图4 5 算法选择界面3 9 图4 4 自动生成的类层次图4 3 图4 5 自动生成的函数调用图。4 5 硕士学位论文 附表索引 表1 1s p e c j 、，m 9 8 中虚函数调用比例3 表2 1 测试程序一览表2 0 表2 2 测试程序中包含的类和方法数量的统计2 0 表2 3 已有算法的分析精度比较2 2 表3 1 各种算法的可用类型集合数量比较3 0 v 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 趔斗 日期：刀形年多月刀日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密日。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 日期：娜年舌月乃日 日期：年月日 洲b 纺 硕士学位论文 第l 章绪论 函数调用图是编译期对程序中函数调用关系的一种静态描述，在函数调用图 中，节点表示函数，边表示函数之间的调用关系。在面向过程的语言中，函数之 间的调用关系在编译期就已经确定，因此面向过程语言的函数调用图是对其运行 时函数调用关系的精确描述。而对于面向对象的语言，因为通常通过指针或者对 象引用进行函数调用，并且由于面向对象语言多态机制及子类对父类函数的覆 写，所以无法在编译期静态的确定虚函数调用点中指针或接受对象在运行时的实 际类型，从而无法确定运行时实际调用的目标函数，因此面向对象语言的函数调 用图只是对其程序运行时函数调用关系的一种保守约近。如果在编译期对虚函数 调用点采用不同的处理策略，那么得到的函数调用图所包含的结点和边也不尽相 同。所有虚函数调用处理策略的目标是一致的，那就是通过对虚函数调用点的分 析使构建的函数调用图能够更精确的约近程序运行时实际的函数调用关系。更为 精确的函数调用图在编译优化，过程问数据流分析，回归测试，程序理解等领域 都有着广泛的应用。 1 1 研究背景及意义 j a v a 是由j 锄e sg o s l i n g 等人于1 9 9 1 年在s u nm i c r o s y s t e m s 公司设计出来 的一种面向对象的高级语言【l 】，由于其特有的平台无关性，以及良好的安全性和 健壮性，j a v a 已经逐渐成为了网络程序开发的首选。伴随着网络的普及和快速 发展，j a v a 得到了广泛的应用。然而用j a v a 语言编写的程序相对于用c 或 f o r t r a n 语言编写的程序而言，在性能和运行效率上存在着很大的差距。导致 这种运行效率降低的原因有很多，其中对j a v a 程序中虚函数调用点的动态绑定 处理是一个很重要的方面，因此如何减少由于虚函数调用所带来的运行时开销成 为了近年来j a v a 程序优化和编译器优化的一个热门话题。 1 1 1 虚函数调用的实质一多态 j a v a 语言的多态机制就象一把双刃剑，它既可以允许你用一般性的角度看 待同一族系的所有对象，这意味着大部分的程序代码不至于过度依赖于特定的类 型信息，从而使程序更易于延伸，并使程序的扩展和源代码的维护更加简单；但 同时它也带来了诸如虚函数调用的问题【2 l 。j a v a 中的方法可以分为类方法和实例 方法，类方法是指在普通函数声明前面加上关键字s t a t i c ( 静态的) 所创建的一 类函数，这类函数完全独立于该类的任何对象，能够在类的任何对象创建之前被 访问。实例方法是指需要通过实例化对象的引用进行调用的一类函数，这类函数 基于静态类型分析的j a v a 程序函数调用图构建方法研究 依赖于引用变量的具体类型。必须在实例化该类对象之后才能被访问，j a v a 程 序中声明的大多数函数都属于实例方法。由于j a v a 允许类的继承以及在继承基 础上的向上转型，因此对于一个父类对象的引用而言，它在运行时的实际可能类 型包括父类及其子类的所有类型，这就是j a v a 语言最重要的特征之一一多态。 子类继承了父类的所有属性，并可以通过函数覆写在子类中给出父类中函数的不 同实现，因此对于虚函数调用点而言，我们无法在编译期静态的确定其调用的是 父类还是其任一子类中实现的相应方法，这就是虚函数调用的根源。 c l a s s a p u b l i cs t a t i cv o i dm a i n ( s t r i n g 口a r g s ) f 0 r ( i i l ti = o ；i 2 ；i + + ) aa _ n u l l ； i f ( i ；= o ) ， a = n e wa ( ) ； e l s e a = n e wb ( ) ； a m ( ) ；，( v i r t u a lm e t h o dc a l d p u b l i cv o i dm ( ) s y s t e m o u t p r i m l n ( “i na ) ； ) c l a s sbe x t e n d sa p u b i i cv o i dm ( ) s y s t e m o m p r i n t l n ( “i nb ”) ； 图1 1 一个虚函数调用的实例 如上图所示，b 是a 的子类，在类b 中覆写了类a 的方法m ，考虑类方法 m a i n 中的实例方法调用a m ( ) ，其中变量a 是方法m 的接受对象，且变量a 的声 明类型为a ，根据多态性，可知变量a 可以是类a 的实例对象的引用，也可以 是类b 的实例对象的引用，只有在执行时当i 的值为o 时，它表示的才是类a 的实例对象的引用，当i 的值为l 时，它则表示类b 的实例对象的引用，因此无 法静态的确定变量a 在运行时具体代表的是哪类实例对象的引用，从而无法确定 虚函数调用点a m ( ) 具体调用的是类a 还是类b 的m 函数。如果一个虚函数调 用点在运行时实际调用的函数根据其接受对象类型的不同而不同，那么这样的虚 函数调用点称其为多态函数调用点，如果不管接受对象在运行时的具体类型是什 么，此虚函数调用点始终调用的都是唯一的函数，那么这样的虚函数调用点称其 为单态函数调用点。如果可以通过静态分析将一个虚函数调用点转化为单态函数 2 硕士学位论文 调用点，那么就认为此虚函数调用可以被静态绑定。 表一给出了s p e c j v m 9 8 中的几个测试基准中有关虚虚函数调用的统计数据 例，其中第二列的c a l ls i t e s 是指测试基准中调用点的数目，第三列的v i n u a l 是 指虚函数调用点在所有调用点中的比例。第四列的c a l l s 是指所有调用点处方法 的执行次数，第五列的v i r t u a l 是指虚函数调用执行次数所占的百分比。 根据这些数据我们不难看出，在面向对象语言中，虚函数的使用是非常频繁 的，因此对虚函数调用的研究是一件非常有意义的工作。 表1 1s p e c j v m 9 8 中虚函数调用比例 b e n c h n l a r k sc a l ls i t e s v i r t u a l c a l l sv i r t u a l 2 0 1 c o m p r e s s 2 9 5 3 6 1 9 1 8 ，1 6 3 ，8 5 4 8 6 7 _ 2 0 2 j e s s 4 7 7 l6 5 6 6 ，1 8 8 ，6 6 2 ， 9 4 o 2 0 9d b 3 2 6 l6 2 9 3 ，2 0 2 ，2 1 5 7 2 8 _ 2 2 2 一m p e g a u d i o 3 6 1 26 4 4 2 ，7 8 0 ，4 9 6 9 3 7 _ 2 2 8 _ j a c k 5 1 1 76 3 2 5 ，6 4 3 ，3 4 4 6 5 o f 1 2j a v a 虚拟机 为了理解j a v a 程序在运行时对虚函数调用点的处理方式，了解j a v a 程序的 虚拟运行平台一j a v a 虚拟机( j a v av i n u a lm a c h i n e ，j v m ) 就十分必要。平台无关性 是j a v a 最重要的特征之一，而实现这一特征的基础就是j a v a 虚拟机。j a v a 虚拟 机之所以被称之为“虚拟”的，就是因为它仅仅是由一个规范来定义的抽象计算 机【4 j 。但和真正的c p u 一样，它也具有一个指令集，对类文件迸行装载并以堆 栈的方式执行类文件中的字节码，因此字节码可以抽象地看作是j a v a 虚拟机的 机器指令。尽管字节码是堆栈式语义的指令。如果虚拟机中存在一个即时编译 器，那么该即时编译器可以把字节码编译成与操作系统和硬件相关的本地指令， 并在真正的c p u 上执行。为了实现j a v a 的平台无关性，需要为不同的主机系统 实现不同的j a v a 虚拟机和j a v aa p i ，这样，在编程语言方面不用考虑底层的硬 件和操作系统。j a v a 虚拟机程序模块通常用c c + + 和相应c p u 支持的汇编语言 编写，也可以使用j a v a 语言本身来实现j a v a 虚拟机。 1 1 3 动态绑定机制 把一个服务的调用与请求该服务的对象连接在一起的过程称为“绑定”。如 果请求服务的对象在程序运行前已经明确，则能够在程序编译和连接时完成绑 定，称此方式为静态绑定，在j a v a 中对于类方法，j a v a 虚拟机采取此类绑定方 式。而对于请求服务的对象直到运行时才能确定的情况，则需要在运行时首先辨 别对象类型，然后选择这种类型对象的该服务内容，称此方式为动态绑定【5 1 。在 j a v a 中对于实例方法，j a v a 虚拟机采取此类绑定方式。继承机制映射的“一般 一特殊”关系，使得面向对象软件的类设计可以自顶向下，由粗而精，逐层推 基于静态类型分析的j 料a 程序函数调用图构建方法研究 进，向上共享的高速进行。而动态绑定技术的应用则使这一自顶向下的程序设计 过程变得更为灵活，设计人员只要定义了父类，确定了动态绑定服务的统一接 口，即可利用向上转型为父类类型的接受对象对子类类型中的具体实现提出服务 请求。因而可以明显提高软件设计的抽象层次，优化了设计流程，提高了设计效 率。运用动态绑定技术，还有利于创建离散化的软件体系结构，提高了软件的可 扩展性和重用性【6 1 。j a v a 虚拟机中分别使用指令i n v o k e s t 砒i c 和i n v o k e v i r t u a l 来 调用类方法和实例方法。尽管通常使用i n v o k e v i r t u a l 指令调用实例方法，但是如 果接受对象的声明类型是一个接口的话，j a v a 虚拟机则通过指令i n v o k e i n t e r f a c d 调用在某个实现了该接口的类中定义的相应函数。i n v o k e i n t e r f a c e 指令可以看作 是i n v o k e v i r t u a l 指令的一种特例。为了进一步了解动态绑定所带来的运行时开 销，需要理解i n v o k e v i n u a l 指令的具体执行过程。当j a v a 虚拟机调用 i n v o k e v i n u a l 时，它需要检查接受对象实际运行时类型所对应的虚函数表来得到 目标函数的索引值，计算索引值的过程是动态绑定带来运行时开销的主要方面， 对于i n v o k e v i r t u a i 指令而言，由于子类覆写的函数在子类的虚函数表中对应的索 引值与父类的虚函数表中被覆写函数的索引值相同，因此只需要在该 i n v o k e v i r t u a l 指令第一次被调用时计算目标函数索引值，即使该i n v o k e v i n u a l 指 令对应的接受对象在运行时的类型发生变化，也无需重新计算目标函数的索引 值，只需要在新的接受对象类型对应的虚函数表中根据原有的索引值就可以得到 正确的目标函数。但是对于i n v o k e i n t e r f a c e 指令而言，由于实现该接口的各类之 间不存在层次关系，所以目标函数在该实现该接口的各类对应的虚函数表中的索 引值也不相同，所以如果接受对象在运行时的实际类型发生变化，则对于实现该 接口的不同类的虚函数表必须重新计算其目标函数的索引值。显然 i n v o k e i n t e r f a c e 指令相对i n v o k e v i r t u a l 而言会带来更大的运行时开销。图1 2 和 图1 3 分别对应类的虚函数表和接口的虚函数表。 h 吐睡口扫黼h 廷f = i f 虹 丸b c m 越c | j s 螂) c m l v i 咖越t 毫抵o f 吐镕九e d e 图1 2 类的虚函数表 4 享剀 b 越一皿一越蚶 a m一心一酋一耐 硕士学位论文 b h c 而柚h - 暇蛐 ( a m a i 耐瞰劬嘲嗽 h 地r 盘1 ) l 2 l m l l 耐 m l 珥2 3 一 m ， 4 m i v i f 啦lt 枷o fc l a a i 柚d 磁缸 妇印k 删l 图1 3 接口的虚函数表 从图1 2 可以看出，类b 和类c 都是类a 的子类，并分别对类a 中定义的 m 1 ，m 2 ，m 3 和m 4 四个函数进行了覆写，但是这四个函数在类a ，b ，c 各自 的虚函数表中的对应的索引值却是相同的，因此不管接受对象运行时的类型如何 变化，都只需要计算一次目标函数的索引值。而从图1 3 可以看出，类a 和类b 分别是对接口i 的不同实现，在类a 和类b 中分别实现了接口i 中定义的函数 m 1 ，m 2 ，m 3 和m 4 ，但是这四个函数在类a 对应的虚函数表中的索引值和在类 b 对应的虚函数表中索引值是不相同的，因此一旦接受对象的运行时类型发生了 变化，就需要重新计算目标函数的索引值。 1 。1 4 函数调用图及应用 函数调用图是编译期对程序中函数调用关系的一种静态描述，在函数调用图 中，节点表示函数，边表示函数之间的调用关系【7 1 。 图1 4 一个函数调用图的示例 基于静态类型分析的j a v a 程序函数调用图构建方法研究 因为对于虚函数调用点而言，必须根据运行时接受对象的实际类型才能确定 具体调用的目标函数，所以j a v a 程序的函数调用图只是对程序运行时函数调用 关系的一种保守约近。这种保守约近是指编译期的函数调用图不能准确的反应程 序执行时函数之间的实际调用情况，而只是对实际调用情况的一种近似。这种近 似中不仅包含了实际的调用情况，而且还包含了一些在编译期认为会发生但在实 际运行时并不会发生的函数调用，因此是一种保守的约近。如果在编译期对虚函 数调用点采用不同的处理策略，那么得到的函数调用图所包含的结点和边也不尽 相同，然而所有处理策略的目标是一致的，那就是通过对虚函数调用的分析使构 建的函数调用图能够更准确的反应程序运行时实际的函数调用情况。这种更精确 的函数调用图可以用于：( 1 ) 通过将程序中的一些虚函数调用点转化为单态函数 调用点，从而实现接受对象和目标函数在编译期的静态绑定，并可以进一步通过 函数内联，减少动态绑定所带来的运行时开销，提高程序的执行效率【s 】；( 2 ) 由 于所构建的函数调用图是对运行时函数调用关系的保守约近，那么如果程序中的 某些函数未出现在构建的函数调用图中，说明这些函数在程序中未被使用，通过 去除这部分函数可以达到精简程序的目的【9 l ；( 3 ) 函数调用图表明了函数之间的 调用关系，过程间的数据流和控制流分析必须以函数调用图作为基础，因此函数 调用图在程序切片，修改影响分析，回归测试等领域都有着广泛的应用。程序切 片是一种分析和理解程序的技术，是通过对源程序中每个兴趣点分别计算切片来 达到对程序的分析和理解程序中某个兴趣点的程序切片不仅与在该点定义和使 用的变量有关，而且与影响该变量的值的语句和谓词以及受该变量的值影响的语 句和谓词有关，而这种影响关系的计算是通过构建程序的数据依赖图和控制依赖 图实现的，而构建程序的控制依赖图和数据依赖图必须以程序的函数调用图作为 基础i l0 】；修改影响分析是指在程序中，各个语句之间不是孤立的，一个语句执 行后的不同结果可能使另一个语句执行时得到不同的结果或者决定了另一个语句 执行或者不执行，这两种情况都称前一个语句影响了后一个语句。那么，当修改 程序的某个部分( 语句) 时，可能潜在地影响到程序的其它部分( 语句) ，这就是程 序中存在的修改影响，而找出对某个部分的修改影响到的程序范围也就是修改影 响分析【l ”；回归测试是软件测试的一个重要组成部分，它的目标是在程序修改 后，只对进行修改的部分重新测试，从而达到与完全测试相同的测试覆盖。而对 于所需要重测部分的确认是通过对过程间的数据流或部分数据流分析来实现的 【1 2 l 。( 4 ) 函数调用图在程序理解和反向工程领域也有广泛的应用【1 3 ，“l 。c h i k o f s k y 和c r o s s l l5 】给出逆向工程的定义为一个分析目标系统的过程，它包括如下两个 部分：一是分辨它的组件并分析组件之间的依赖关系；二是建立系统的另外的或 在更高抽象级别上的表达形式。上述逆向工程定义的两部分本质上是一个知识恢 复、知识发现的过程。对于软件这种无形的人工产物来说，逆向工程的主要目的 6 硕士学位论文 首先是重现考察对象所体现的原有设计知识，其次是能发现一些在设计中没有明 显表示出的、存在于设计人员头脑中的设计知识。逆向工程的基本目的是帮助软 件理解，而软件理解是软件中存在的模式和人脑中存在模式的匹配。逆向工程方 法工根据具其抽取的设计知识的抽象层次，即生成结果的可理解程度可以分为四 个层次：( 1 ) 程序实体间的实际关系抽取。( 2 ) 设计模式的识别。( 3 ) 面向对象程序 的度量。( 4 ) 系统结构和域模型的抽象。函数调用图是编译期对程序中函数调用 关系的一种静态描述，是在逆向工程方法的第一个层次上的具体实现。 1 2 研究现状 对于j a v a 程序而言，函数调用图构建中最核心的问题就是对虚函数调用点 的处理，对虚函数调用点的分析精度直接决定了构建的函数调用图的精确程度， 对虚函数调用问题的分析和研究，作为程序优化和编译优化的一个重要方面，从 面向对象语言诞生之日起就一直存在。如何减少虚函数调用点中接受对象的可能 类型集合，从而更好的约近虚函数调用点中接受对象在运行时的实际类型是解决 虚函数调用问题的关键。根据程序执行的不同阶段，对虚函数调用问题的处理方 式主要分为两种：一种是基于编译期的静态类型分析策略【1 6 1 7 1 ，一种基于运行 期的动态编译优化策略【 ，1 9 】。 1 2 1 静态类型分析 静态类型分析是指在程序运行前，基于编译期的程序分析的基础上，考虑过 程内及过程间的对象创建及对象类型的传播，从而对相应的函数调用点中的接受 对象约近其运行时可能类型的一种分析方式。 根据分析过程是否与流程有关，静态类型分析可以分为：流敏感的分析【2 0 ) 和流不敏感的分析【2 1 1 。 流敏感的分析是指基于程序的控制流图的基础上，考虑对象类型从创建到使 用过程中的类型传播的一种分析方式。主要的流敏感的分析包括s h i v e r 提出的 面向s c h e m e 语言的控制流分析( o c f a ) 2 2 】和h e i n t z e 提出的基于集合( s e t b a s e d ) 的分析【2 3 1 ，这两种分析方式都是通过考虑程序的数据流和控制流信息，对程序 中的所有声明变量给定一个可用类型的集合，从而直接的确定虚函数调用点中接 受对象运行时的可能类型。这种分析方式精度高，能够较准确的约近接受对象运 行时的可能类型，但由于需要保存程序的数据流和控制流信息，并且对程序中所 有声明变量都需要给定一个可用类型的集合，因而分析的开销很大，是否能满足 日益变大的程序的类型分析需求还有待实践的进一步证明。 流不敏感的分析是指不考虑基于控制流图的类型传播而直接计算虚函数调用 点中接受对象的运行时可能类型的一种分析方式。这种分析方式的精度虽然可能 7 基于静态类型分析的j a v a 程序函数调用图构建方法研究 不如流敏感的分析高，但算法简单，容易实现，而且分析的开销小，能够较好的 满足程序的扩展性，因而被广泛的用于j a v a 编译的优化。这种分析方式中最主 要的是：由j d e a i l 提出的类层次分析( c l a s sh i e r a r c h ya n a l y s i s ) o2 4 j 和由d a v i d f b a c o n 提出的快速类型分析( r a p i dt y p ea n a l y s i s ) ”】。类层次分析的主要思想 是通过构建程序的类层次图，图中的节点表示程序中各个类以及其所包含的函 数，边表示类之间的继承关系。如果一个接受对象的声明类型为c ，那么根据类 层次分析，此接受对象的运行时可能类型就包括c 以及它的子类的所有类型。 此时如果该虚函数调用点所调用的函数在其所有接受对象的可能类型中未被覆 写，那么此时的虚函数调用可以转化为对父类中目标函数的直接调用，从而进一 步可以通过函数内联( m e t h o di n l i n i n g ) 实现程序优化，减少动态绑定所带来的运 行时开销1 2 6 1 。快速类型分析是基于类层次分析所建立的函数调用图来考虑函数 的可达性，在这种可达性基础上，考虑所有可达函数中的实例化信息，因为对于 虚函数调用点而言，它的接受对象的可能类型必须是在程序中实例化了的类型， 这种分析进一步减小了类层次分析中接受对象可能类型的集合，在与类层次分析 相同的时间复杂度的情况下取得了更好的分析精度。在下一章将对结合实例对两 种分析方法的过程进行详细说明，并在第五章中给出了这两种方法的分析性能评 测。 为了进一步提高快速类型分析的精度，同时又使分析方法对于程序具有较好 的扩展性，f t i p 和v s u n d 盯e s 粕分别在结合了流敏感和流不敏感分析的各自特 点的基础上提出了对快速类型分析方法的改进。 f t i p 提出了x t a ，c t a ，m t a ，f t a 一类方法【2 7 1 ，它的主要思想是对程序中的 每个实体( 包括类，方法和域) 给定一个可用类型的集合，其中c t a 是对程序中 的每个类给定一个可用类型的集合，m t a 是对程序每个方法给定一个可用类型 集合，f t a 是对程序中每个声明域给定一个可用类型的集合，x t a 则是对程序 中每个方法和每个声明域分别给定一个可用类型的集合。与快速类型分析基于类 层次分析所构建的函数调用图来考虑函数的可达性不同，这四种分析方法采用增 量式的方式考虑函数的可达性，因为j a v a 程序都从m a i n 函数开始执行，因此四 种分析方法首先都认为m a i n 函数是永远可达的，从m a i n 函数，逐个的分析每个 可达函数中的虚函数调用点，可用类型的集合包含了在各个实体中创建的实例化 类型集合以及通过参数传递和函数返回值在各个程序实体间传播的可用类型集 合，由于通过增量式的方式来考虑函数的可达性，因此每个可达函数的加入都会 影响原程序实体的可用类型集合，所以这四种分析方法都是基于不断迭代方式构 建函数调用图，当各个程序实体的可用类型集合达到某个固定点，函数调用图的 构建也就随之完成。 v s u n d a r e s a n 提出的可达类型分析方法【2 3 1 ，包含两种变种：分别是变量类 8 硕士学位论文 型分析方法和声明类型分析方法。它的主要思想是通过类层次分析方法或快速类 型分析方法所构建的函数调用图来考虑函数的可达性，因此这种分析方法无需进 行迭代，并在这种可达性的基础上，通过构建所有可达函数内声明变量的类型传 播图，从而给出每个声明变量的可能类型集合，在此基础上，再结合类层次分析 和快速类型分析来进一步约减虚函数调用点中接受对象的可能类型集合。这种分 析方法虽然与o c f a 方法一样给出了每个声明变量的可能类型集合，但是这种 分析方法不考虑可达函数内的控制流信息，只是根据实例化对象类型来初始类型 传播图中的每个变量，并根据赋值语句，参数传递和函数返回值来考虑变量间的 类型传播，因此，降低了0 一c f a 方法的复杂度的同时提高了快速类型分析的分 析精度。根据所构建的类型传播图中节点表示方式的不同，可以分为变量类型分 析和声明类型分析。变量类型分析是指类型传播图中的节点用变量的变量名来表 示，声明类型分析是指类型传播图中的节点用变量的声明类型来表示，同一个声 明类型的不同变量用一个节点表示。 根据分析过程是否与上下文有关，静态类型分析可以分为上下文敏感的分析 【2 9 1 和上下文不敏感的分析【3 们。上下文敏感的分析方法依据同一函数在不同调用 点对象引用指向具体对象的不同而产生不同的分析结果，而上下文不敏感的分析 方法则对同一函数的不同调用只产生一个唯一的近似结果。毫无疑问，相比而言 进行上下文敏感的静态类型分析所取得的结果将会比较精确在众多的上下文敏 感的静态类型分析中，比较有影响的是s h i v e r 提出的k - c f a 分析【3 l j ，它是一种 基于控制流和数据流信息的上下文敏感分析。而我们前面所列举的主要的几种流 敏感和流不敏感的分析都是上下文不敏感的分析。 1 2 2 动态编译优化 静态类型分析只能对虚函数调用点中接受对象的运行时可能类型进行约近， 所以它只能在一定程度上解决j a v a 中的虚函数调用问题，提高j a v a 程序的执行 效率，为了更好的解决虚函数调用问题，迸一步减少动态绑定所带来的运行时开 销。后来又提出了基于动态编译优化的解决策略。 动态编译，即运行时编译，主要是指根据运行时的反馈信息对程序进行动态 编译。p r o f i l i n g 技术是动态编译中的一项核心技术，该技术的主要目标是以最小 的运行时开销得到最精确的p r o f i l e 数据【3 2 l 。这些p r o f i l e 数据往往是优化的候选 者( o p t i m i z a t i o nc a n d i d a t e s ) 以及其他一些编译优化所需的信息( 比如，基本 块的执行频度，c a c h e 命中率等等) 。这里的优化候选者是指经常被执行的代码 序列，这些代码序列被称为“热点”，在动态编译系统中，这些热点可以是经常 执行的方法或者经常执行的某条路径等等。对于程序中的虚函数调用点而言，如 果在多次执行该虚函数调用点的过程时，所调用的始终是接受对象某个可能类型 9 基于静态类型分析的j a v a 程序函数调用图构建方法研究 的相应目标函数，那么则认为此目标函数是热点函数。 按照p r o f i l e 数据的来源来分，p f