基于基于LLVM的程序切片系统的程序切片系统2014年6月7日目录页目录页contents0101选题选题0202设计设计0303实现实现1、选题问题：问题：背景背景当一个大的计算机程序被分解成一个个较小的程序片以后，很容易被构造、理解和维护。在程序分析测试时，由于程序段代码量大，针对不同程序变量、接口的测试分析起来较为困难，费时又费力，而且还容易出错。解决：解决：我们需要一些用于程序分解的技术和方法，在这些技术中程序切片起到了无可替代的作用1、选题发展发展（1）基于数据流方程的程序切片阶段）基于数据流方程的程序切片阶段（2）基于依赖图的程序切片阶段）基于依赖图的程序切片阶段（3）面向对象程序切片阶段）面向对象程序切片阶段（4）程序切片发展）程序切片发展“百花齐放百花齐放”阶段阶段M.Weiser（基于CFG的数据流方程）K.J.Ottenstein（基于程序依赖图）、S.Horwitz（前向切片）等M.J.Horrald（扩充的依赖图）、D.Liang和Z.Chen（面向对象动态切片）削片、砍片、数据切片、层次切片和无定型切片2、设计理理论基本思想M.Weiser等人将只与某个输出有关的语句和谓词所构成的程序成为程序的一种静态切片（staticslice），并提出了基于CFG的计算程序切片的算法。他定义的程序切片是通过对初始程序删除零条或多条语句得到的可执行程序。切片准则是二元组，其中V表示在n定义或使用变量的集合，n表示程序中的某个点。关于切片准则的程序切片是程序P的语句的一个子集S，它必须满足：（1）S必须是一个有效程序；（2）对一个给定的输入，P中断时，S也中断，无论何时，与S相关的语句被执行时，计算V中所有变量的值都必须是相同的。2、设计理理论依赖关系在一个源代码中，对于一个变量的有直接影响关系的称为数据依赖，而对一个变量有间接影响关系的称为控制依赖，比如出现if，while的时候。第4条语句的i变量和第7条语句i变量有着直接影响关系，所以其存在数据依赖关系第6条语句存在if判断语句，所以对i变量的语句存在间接依赖，我们称之为控制依赖关系2、设计理理论依赖图的构造目前的程序切片大都是以SDG为基础，在其上利用图的可达性算法获得的。SDG包含许多过程依赖图（ProcedureDependenceGraph，PDG），每一个PDG对应程序中的一个过程。PDG由点和边组成，其中点代表语句或判定表达式，边又分为数据依赖边和控制依赖边。基于数据流分析的算法：确定直接相关变量与语句，确定间接相关变量和语句的方程图的可达性算法：找出所有从依赖图的入口节点到切片准则节点的所有路径，把这些路径所经过的节点标记出来，其构成的集合就是关于切片准则的一个依赖图切片。2、设计理理论25467图中可以看出，对于i变量，我们根据控制依赖和数据依赖关系构造成简单的依赖图。其中结点为父子关系的为控制依赖关系，节点是虚线的是数据依赖关系。依赖图的构造的例子2、设计理理论设计流程图源程序源程序数据依赖关系数据依赖关系控制依赖关系控制依赖关系系统依赖图（系统依赖图（SDG）切片生成器切片生成器基于数据/控制流分析算法可达性计算根据依赖关系构造成图2、设计理理论支撑工具LLVM（LowLevelVirtualMachine），可以作为多种语言编译器的后台。LLVM编译系统编译系统中间代码中间代码集集 成成 库库工工 具具虚虚拟拟指指令令集集高高层层结结构构类类型型系系统统核核心心库库分分析析库库转转换换库库代代码码生生成成库库运运行行库库目目标标处处理理库库基基本本工工具具编编译译工工具具调调试试工工具具后后端端工工具具单单指指令令内内函函数数原原子子类类型型衍衍生生类类型型2、设计理理论支撑工具LLVM工具及相互关系工具及相互关系2、设计理理论支撑工具LLVM编译流程编译流程高高级语言言前端前端中中间代代码优化器化器后端代后端代码生成器生成器C代代码C+代代码LLVM IRLLVM IR后端代后端代码文件文件标准的准的标量量优化和化和循循环优化化进程程间优化（跨函化（跨函数）数）3、运行演示执行步骤1编译过程：在LLVMSlicer-build目录下依次执行指令：（1）cmake.（2）make2执行过程：在LLVMSlicer-build-src目录下依次执行指令：（1）optload./LLVMSliser.socreate-hammock-cfgslice-intercalc.bcocalc1.bc（2）sh./process.sh源程序名切片变量3、运行演示切片举例对左边程序中的X变量进行切片：执行切片之后，在LLVMSlicer-bulid-src目录下会创建一个test文件夹，test文件夹中包括如下的内容：