流敏感按需指针别名分析算法.pdf

《流敏感按需指针别名分析算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、计算机研究与发展DOI：１０．７５４４/issn１０００‐１２３９．２０１５．２０１４０３３６JournalofComputerResearchandDevelopment５２（７）：１６２０１６３０，２０１５流敏感按需指针别名分析算法逄龙苏小红马培军赵玲玲（哈尔滨工业大学计算机科学与技术学院哈尔滨１５０００１）（hitpanglong＠gmail．com）ResearchonFlowSensitiveDemandDrivenAliasAnalysisPangLong，SuXiaohong，MaPeijun，andZhaoLingling（SchoolofC

2、omputerScienceandTechnology，HarbinInstituteofTechnology，Harbin１５０００１）AbstractInordertoimprovetheresponseefficiencyofpointeraliasqueriesintheinteractiveenvironment，researchesareinterestedinthedemanddrivenstrategytoreducethecostforanalyzingtheunrelatedpointervariableswithrespecttothe

3、objectives．Thedemanddrivenaliasanalysisbasedonthecontextfreegrammarhasbeenproposed．However，itsprecisionisonlylimitedtotheflow‐insensitivity．Theflow‐insensitivitypointeraliasrestrictstheprecisionofoverlyinganalysis，sothebugdetectionresultsinmorefalsealarmsthantheonewithflow‐sensitiv

4、ealiasanalysis．Inthispaper，weproposeademanddrivenpointeraliasanalysisbasedonthegraphreachabilityandthecontextfreegrammartoprovidetheflowsensitiveprecision，whichhastolerableadditionaloverheadcomparingwiththeflow‐insensitivealiasanalysis．Firsttheupdatesofpointervariablesarediscrimina

5、tedbythepartialsinglestaticassignmenttofilterouttheunrelatedpointervariablesasearlyaspossible．Thenthesequenceofcontrolflowalongtheseassignmentsisexpressedintheformoflevellinearizationcode，whichisusedtoconstructtheassignmentflowgraph．Finally，thequeryofaliasindemanddrivenisformalized

6、asthesearchofreachabilityoftargetnodesintheassignmentflowgraphtoachievetheprecisionofflowsensitivity．Theexperimentsdemonstratethatthispresentedmethodcanimprovetheflowsensitivitytheprecisionofaliasanalysisindemanddrivenwithoverheadtolerable．Keywordsaliasanalysis；flowsensitivity；dema

7、nddrivensearch；contextfreelanguage；graphreachability摘要为了提高交互环境下指针别名查询的响应效率，近期研究提出通过只分析与目标相关指针的按需分析策略来降低浪费在与目标无关的指针分析的额外开销．典型的代表是基于上下文无关文法的按需别名分析算法．但是，该算法的精度只局限于控制流不敏感．控制流不敏感的别名关系将约束上层分析的精度．针对该不足，提出了具有流敏感精度的按需别名分析算法．首先采用不完全静态单赋值语句形式来区分指针变量赋值实例，然后通过层次线性化编码方法来表达控制流图中的流敏感信息以构建赋值流图，最后将别

8、名关系查询问题转换为在赋值流图上搜索目标结点间在控制