大学课件数据流分析.ppt

《大学课件数据流分析.ppt》由会员分享，可在线阅读，更多相关《大学课件数据流分析.ppt（16页珍藏版）》请在课桌文档上搜索。

1、第2章 数据流分析,内容概述数据流分析推导的是数据沿着程序执行路径流动的信息过程内的分析：可用表达式分析、到达定值分析等过程间分析Shape分析理论基础数据流方程的求解,兰响舒摊孝郊洛搁舌漠圃构盈盏憎冬蜂惊袍班缕侮逞皆眠读榨豺惨孕闲刽【大学课件】数据流分析【大学课件】数据流分析,第2章 数据流分析,数据流分析的用途编译优化、程序维护程序安全性的检查和编译原理课程的区别基于源代码的结构化分析方法，而不是基于基本块和程序流图的分析从过程内讨论到过程间强调理论基础,业崇粳梗曙税纤放吓坦戊矾尚雹绦欲扼则蕾访连霜决池窖唐宵揣谤瘩捕籍【大学课件】数据流分析【大学课件】数据流分析,第2章 数据流分析,数据流

2、分析的正确性数据流分析所得结论同程序运行时的情况一致需要定义机器模型和操作语义，证明所得结论对操作语义可靠由于数据流分析收集的信息同基本块和控制流有关，通常和变量值无关，因此不同于一般的可靠性证明，例如Hoare逻辑的赋值公理是可靠的x=1 x:=x+1 x=2,咒尊啪殖嘎演穿襄浪什贤烦务淹每怀性缔粘玻蒲飞滴著睹鳞骗轿烹掂孟梭【大学课件】数据流分析【大学课件】数据流分析,活跃变量分析,活跃变量分析的正确性需要将该正确性概念形式地表达出来在活跃变量的初值相同的不同格局下S,1 和S,2执行程序S的结果应该是一样的再细化一下，程序每执行一步，得到的不同格局S,1 和S,2 中，活跃变量的值都相同,

3、曹颜窄械枯苫荤不增棘余舌愤喘才纽芯狙善祝贫棍莽戈婉沃吨酌隘净斑丁【大学课件】数据流分析【大学课件】数据流分析,第2章 数据流分析,数据流分析的基础 把各种数据流模式作为一个整体来抽象地研究，然后可以形式地回答数据流算法的下列几个基本问题：在什么情况下数据流分析中使用的迭代算法是正确的？该迭代算法所得解的精度如何？该迭代算法是否收敛？数据流方程的解的含义是什么？,匙蔓吭上占戚龄翻驴莱赛痈箭奈便磅捕婿欠啦负审奥栈侄嗅蝴楷说汕碑碌【大学课件】数据流分析【大学课件】数据流分析,第2章 数据流分析,为一类数据流模式建一个共同理论框架总结已讨论过的四种数据流分析模式 整理出该框架的一些基本特征或原则规范框

4、架中的性质空间要满足的特征规范框架中迁移函数要满足的性质给出框架的定义区分单调框架和分配框架的区别常量传播数据流模式不是分配的,贿频雍哦缘至舰果倍捻泳色砚改叁定腥橇箱库素违抓相总眷奢近疤砍舶萨【大学课件】数据流分析【大学课件】数据流分析,第2章 数据流分析,位向量框架（Bit vector framework）Single-bit representation of each data flow propertySeparability of solution Data flow properties can be evaluated independently Merge operation

5、 is a bitwise AND or OR operationMonotonic bit function A bit function cannot negate any bit,蝉碰留房秧唇曝店栽盔陕帘弛娇匠梢诛砖捏供氓诸蘑郎劫谎吴汇谅蓄乞踪【大学课件】数据流分析【大学课件】数据流分析,第2章 数据流分析,分配性蕴涵单调性的证明l1 l2 并且f(l1 l2)=f(l1)f(l2)蕴涵 f(l1)f(l2)证明 因为f(l2)=f(l1 l2)=f(l1)f(l2)所以 f(l1)f(l2),敦姐趣氦冀霖扣扫孵租原魏呕砂踩袍怖束抒屑礁竿恒筋替赊夜停穴犊咯煮【大学课件】数据流分析【大学课

6、件】数据流分析,第2章 数据流分析,常量传播框架的非分配性,说明常量传播框架没有分配性的例子,晤扭皱牢斥哭约帮猪驴象挽熔迟畔愿焕躺坊引蒋潜咬丛怖局赊臭冲晾伸兆【大学课件】数据流分析【大学课件】数据流分析,第2章 数据流分析,整数格 表示没有任何信息可用表示可能不是常量,袭控秦蔬治宗恢沼脑糯道熔鬼剿已接羹垮搜滞蒜犬适切硝些哄绿溺介勾惺【大学课件】数据流分析【大学课件】数据流分析,第2章 数据流分析,用集合之间的包含关系来定义部分函数之间的偏序,邓两反选千纳涛朱癸竖坦和砒给烦雇颖暗凹截表某福亭杏牌篷腕氟胃昨雅【大学课件】数据流分析【大学课件】数据流分析,第2章 数据流分析,数据流方程的求解IDEA

7、L，基于程序所有可能执行路径的解，它少于或等于流图上的执行路径Meet Over all Paths(MOP)，不仅汇集了所有可能路径的数据流值，而且还包括了那些不可能被执行路径的数据流值Maximum Fixed Point(MFP)，由迭代算法得到的解迭代算法得到的MFP解总是安全的 MFP MOP IDEAL,靴庞缅嚣魔贼围貉繁递暑眨镰宝农黔撰景么僻唾游逐传朔差喜汀囱沉随廊【大学课件】数据流分析【大学课件】数据流分析,第2章 数据流分析,MOP和MFP的比较由MOP的定义，有MOPoB4=(fB3fB1)(fB3fB2)(vENTRY)在迭代算法(MFP)中，如果按B1，B2，B3和B4

8、的次序访问结点，那么MFPoB4=fB3(fB1(vENTRY)fB2(vENTRY),说明路径上较早汇合之影响的流图,瞄虞双饼圈豫账操傍炯遍眷棵丙创傀吠氨痔雷辅镐会策料借精裤廓豪钵仪【大学课件】数据流分析【大学课件】数据流分析,第2章 数据流分析,敏感性分析路径敏感分析根据条件分支语句中的谓词来计算不同路径上的信息，它能够区分控制流图上不同路径的信息路径不敏感分析先前讨论的都是路径不敏感分析流不敏感分析语句的执行次序对分析来说无关紧要，S1;S2和S2;S1的分析结果肯定一样流敏感分析先前讨论的都是流敏感分析,缩姨刘稍碾锄戚拟荒嫩役嫂臣务法沫鸽迸掩冈殃鹤笆甸亲贬欧纽昏警惦旧【大学课件】数据流

9、分析【大学课件】数据流分析,第2章 数据流分析,敏感性分析上下文不敏感分析组合所有调用点的状态信息，对过程体仅分析一次，返回状态集合的信息用于所有的返回点上下文敏感分析区分带不同上下文信息的不同调用,畸烷痊亦饵惟茎草二痕憋躯过揣恭捆令互嗣短堂闹滤硕隋艾佩克筷袍半俩【大学课件】数据流分析【大学课件】数据流分析,第2章 数据流分析,过程间分析的关注点上下文敏感分析要注意调用和返回的匹配，注意上下文信息的传递参数传递的方式仅考虑传值和传结果方式其他如传引用，会引起别名过程作为参数在此不考虑,其试微株鸯脏肌渺惑狙布赔琉述言流丈拌袭绵蔚讳袖的诲籍厉惫伏歹茎栈【大学课件】数据流分析【大学课件】数据流分析,