资源描述：
《上下文敏感指针分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、计算机学报000505计算机学报CHINESEJOURNALOFCOMPUTERS2000 Vol.23 No.5 P.477-485上下文敏感的过程间指针分析黄波 臧斌宇 韦俊银 朱传琪摘 要 提出了一种新的指针指向信息的过程间传播方法，对过程间指针分析所必须解决的若干重要问题给出了详尽的算法，从而形成了一种实用的上下文敏感的过程间指针分析框架.该方法已在C程序分析工具Agassiz系统中实现，实验数据说明这些方法是行之有效的.关键词 上下文敏感，指针分析，过程间分析，扩充参数中图法分类号： TP311Context-
2、SensitiveInterproceduralPointerAnalysisHUANGBo ZANGBin-Yu WEIJun-Yin ZHUChuan-Qi(InstituteofParallelProcessing,FudanUniversity,Shanghai200433)Abstract InterproceduralpointeranalysisplaysanimportantroleinparallelizingCprogram.Inthispaper,anewapproachtohowtopropaga
3、tepoint-toinformationaccrossfunctionsisintroduced,detailedsolutionstomanyimportantproblemsthatexistininterproceduralpointeranalysisarealsopresented.Basedontheseideas,acontext-sensitiveinterproceduralpointeranalysisalgorithm,whichhasbeenimplementedinAgassiz,ananal
4、yzingtoolforCprogram,isintroduced.Experimentalresultsillustratethatthealgorithmiseffective.Keywords context-sensitive,pointeranalysis,interproceduralanalysis,extendedparameter1 引 言 程序的并行性分析与并行优化依赖于比较强的数据流分析手段，在对C程序进行数据流分析时，由于指针数据类型的存在，如果预先不对指针变量的指向目标进行分析而采取保守的估计
5、，必然会大幅度地降低所获取数据流信息的准确性，从而导致后续的程序分析与并行优化难以取得比较好的效果.以如下的小程序段为例： int*p,i,j,k; ⋯ p=&i; /*S1*/ *p=10;/*S2*/如果不做指针分析，在分析语句S2时就得假定指针变量p可能指向i，j和k3个变量，那就必然得出S2可能对变量i，j和k都进行了定值的结论.但通过指针分析，p确定指向变量i这个事实可以通过对语句S1的分析而得到，从而在分析S2时可以确定此语句只对变量i的值进行了定义. 上面这个小程序只是一个非常简单的例子，由于复
6、杂数据结构与多种控制结构的存在，实际的指针分析将非常复杂，函数调用的存在尤其加剧了这种复杂性.众所周知，函数调用可能会引起全局指针变量指向信息的修改，也可能会通过对多级指针类型的形参所指向的目标的修改从而间接地修改调用点实参的指针指向信息；反过来，被调用函数可能会依函数调用点指针指向信息的不同而有不同的分析结果.这就要求我们在对C程序进行指针分析时，必须跨过程进行指针指向信息的求取，即进行过程间分析. 为了尽可能地削弱指针变量的存在对程序分析的影响，许多学者曾提出各种不同的过程间指针分析方法［1—8］.这些过程间指针分
7、析方法按所求取信息的准确程度可分成两类：上下文敏感（context-sensitive）的分析方法［1—3，5，6］和上下文不敏感（context-insensitive）的分析方法［4,7,8］.上下文敏感的分析方法依据同一函数不同调用点指针指向模式的不同而产生不同的分析结果，而上下文不敏感的分析方法则对同一函数的不同调用只产生一个唯一的近似结果.毫无疑问，相比而言进行上下文敏感的过程间指针分析所取得的结果将会比较精确.万方数据file:///E
8、/qk/jsjxb/jsjx2000/0005/000505.htm（第
9、1／12页）2010-3-231:14:00计算机学报000505在众多的上下文敏感的过程间指针分析方法中，比较有影响的是Emami和Wilson的工作.Emami首次提出了指针信息的point-to表示法，能比较有效地表示指针的指向信息，并进而提出了一个上下文敏感的过程间指针分析框架，但是他所提出的方法实际上相当于
