【毕业学位论文】（Word原稿）基于LLVM的全局代码静态分析-软件工程

基于 全局代码静态分析 第 1 页 共 5 页 基于 全局代码静态分析 摘要 本次毕业设计的目标是改良 译系统的工具链 兼容性 并在此基础上设计并实现基于全局代码静态分析中使用加强的二阶段锁协议达成死锁规避。 全局代码静态分析是编译阶段针对完整程序的分析，也称作全程序静态分析。而 本次毕业设计选择 基于 统的全程序分析 是由于该系统的全局静态分析 能够脱离原程序语言而独立于 平台的中间表达式分析，使得其应用范围更广泛，移植性强 。 统提供了完整而成熟的中间代码分析框架，扩展性好，性能强大，为广大开发研究人员编写静态分析程序打下了坚实的 基础。美中不足的是， 统中的编译工具链尚在初步开发阶段，其兼容性远不如已然成熟的 得相当多的标准工程无法便利地使用 一方面， 统中绝大多数的分析手段均集中在过程内优化，对于全局代码的优化手段相当有限。本次毕业设计的任务就是改良 译工具链，提高其兼容性以及为 首先通过改善 具链而更容易得到工程的全局中间代码，然后在此 间代码上进行全局分析，将所有的加锁解锁信息统筹 规划并修改成符合二阶段锁的具体规范的新代码，从而实现死锁规避，提高并行程序代码的可靠性。 静态代码分析是诸多程序分析中最常用的方法，能够在编译时就发现程序中存在的缺陷，潜伏的问题，能够优化的部分以及可预测的效率等等 程序中的各种属性特征。相对动态代码分析，即运行时代码分析而言，静态代码分析从程序的文本表现，也就是代码本身出发，采取类似于三岁看到老的观点去审视，嗅探，揣摩和把握程序。在理论基础和运用层面上静态代码分析和动态代码分析相辅相成， 都是 为 了 构建更为高效安全的程序。这其中编译器家族所吸收集成的大量静态分析 手法经过多年的发展已经日渐成熟并且不断有新的突破。现在的各大编译器世家都把静态代码分析视为最重要的组成部分，把缺陷规避和深度优化作为首要任务来设计实现更为强大的编译器。当然，编译器整合的优化和分析毕竟还会受到编译器自身编译语言的部分限制，还会牵涉到不少 程序语言自身相关的依赖关系。那么作为静态代码分析中重要的一部分，平台无关 分析 就 自然而然 地成为了理论研究的核心地带，负责支撑起广大编译器和分析工具的跨语言能力，并可以显著提高编译器本身代码的可重用性，加速编译器的开发和演化。更进一步，有的编译系统更是完全建立在平 台无关的中间代码之上，创造出以中间 代码 为分析核心的深度优化体系，充分扩张编译时的分析优化阶段，最后才实现编译目标代码实现完整的编译过程。这其中的佼佼者就是统。 统始于 2002 年，一直致力于中间代码深度分析优化。 但其中不足 的是，其编译工具链仍然处于 初步开发 之中，对于许多工程项目无法实现兼容的编译行为。当然这个也相当大程度上和 统编译出的中间代码不是本地可执行代码不无关系，造成编译脚本的命令和实际编译行为造成冲突。另外一点是，编译 脚本，一般来说是 程，所依赖的编译工具链是 者 G+这样的成熟而强大的编译工具链。与它们无与伦比的兼容 基于 全局代码静态分析 第 2 页 共 5 页 性能够相提并论的编译工具链 屈指可数 。这 主要是因为编译开关 的 不兼容 而 造成 不成熟 的编译工具链无法消化而只能报告错误 ，引起编译终止 。由于修改工程中的编译脚本相当费时费力而且容易出错，我们不如改良 统的编译工具链，提升其兼容性来适应那些工程项目，为能够采用 个系统的深度优化而做这一部分的工作。 主要的任务就是拦截并修改编译命令，去除 具链所 不适应的编译开关，修改 部分 译工具链的默认行为以适应多数工程项目，然后借助于用例测试来保障编译工具链的普适性。这项工作是为了 统能在更多的项目中展开身手，受到更少的束缚而所必需的。就目前情况而言，效果是非常明显的，包括 大型项目也可以在不修改或者非常有限的修改编译脚本的前提下顺利编译成中间代码了。 有了改善的编译工具链之后， 静态代码分析系统终于可以 在众多项目中进行其计划的深度多次分析优化了 。既然能够编译出全程序中间代码，我们自然会把目光投向于全局分析 和优化上。 合实验室提出了并行程序中的死锁规避问题，这个死锁规避的措施是在全程序的静态分析中运用数据库中很早提出的二阶段锁的技术，运用到静态代码的分析修改上从而实现的。并行程序的工程一般比较庞大，而 合实验室现有的工具无法对于分散的源代码进行分析， 而 全程序中间代码分析可以被 充分利用 。那么在 们需要做的就是统计规划全局的加锁和解锁信息，把中间代码修改成符合二阶段锁的规范就可以实现这一目的。我们的目标是，所有的线程都必须只存在一个只能获得锁的阶段，以及一个只能释放锁的阶段，而且 所有线程获得锁和释放锁的顺序都是全局规定好的，否则在并发的时候就可能出现循环等待的情况而死锁。这一技术是打破了死锁四要素之一的循环等待而达成死锁规避的。而且把加锁和解锁集中之后会扩展开临界区，会不可避免地对性能造成一定的影响。但是对于死锁代价十分高的高可靠应用领域来说，性能上的牺牲是工程妥协，权衡利弊之后还是需要 接受 的。 至此，从 统的编译工具链兼容整合到应用全局静态分析这一整条流水线已经完成， 这也是本次毕业设计所期望达到的目标。 关键词： 态分析，全局代码分析，死锁规避 ，二阶段锁 协议 基于 全局代码静态分析 第 3 页 共 5 页 N he of is to of a a in to is at as is it to of a It of is in it a as a is is no CC a of is in So is to of a is by is to it in to of is It of at to on to of 基于 全局代码静态分析 第 4 页 共 5 页 in to of a an of a to in to to on to to on of to It to on It of of by to on is is of 002 on of is it to We it on CC + to a of CC in It an to an To up in it of is a of is to If is it on a of to to of is to to a + We to 基于 全局代码静态分析 第 5 页 共 5 页 is of to of be as in of So is to be to be in to a in to of a of a we be no on a of on HP a to to on an of in to a to to of P an to to do is is to to it in is on a to of Of in a or of be we to a on is 基于 全局代码静态分析 第 1 页 共 5 页 目 录 第一章 绪论 局代码静态分析 统 统架构 拟指令集 基于 优化 锁和 二阶段锁 技术 静态程序分析中的死锁规避 二阶段锁协议和死锁规避 二阶段锁协议在全局代码静态分析中的改良 章小结 二章 译工具链的兼容整合 始编译工具链 特性 .1 编译开关 .2 行为 模式 的特性 特性 .1 链接开关 .2 行为模式 译工具链的改良 具链改良的需求设计 命令行为 解析 部分的分析设计 命令开关解析部分的分析设计 三章 基于二阶段锁的死锁规避 阶段锁 协议的不足和特定改良 二阶段锁协议下的死锁 二阶段锁的全局加锁顺序 态分析 全局 统筹锁 限和进一步的工作 加锁和解锁语句的返回值 加锁和解锁语句的位置和临界区域压缩 加锁和解锁语句的移动位置和程序行为改变 锁的别名 四 章 设计原型和实验数据 实验数据 9基于 全局代码静态分析 第 2 页 共 5 页 1） 局静态分析死锁规避的原型实现 和实验结果 五章 结论 考文献 辞 于 全局代码静态分析 第 1 页 共 25 页 第一章 绪论 全局代码静态分析在程序分析理论研究领域历史最为悠久，而且还能够不断有着新的进步和突破。 当然，局部代码分析也是百家争鸣，一片兴旺。过程内部的优化简明扼要而且局部效果非常显著，是代价小而且收效高的分析手段。和局部代码静态分析的焦点不同，全局代码分析必须站在更高的起点上，从整个代码的有机体出发，看到 全局的联系才能对于全代码分析优化产生更加具有影响力的全面效果。就算是再优秀的过程内部优化，如果仅仅从程序的片段出发，看不到别处，必然视野受到了限制而致使其无法做出更进一步的考虑，然而它们欠缺的纵观全局的能力就是全局代码分析的着眼点和战略定位。 全局代码静态分析 其中一部分研究领域是依赖于程序语言设计本身的，并将静态分析研究和程序语言设计紧密结合，致力于创造出更优良的程序语言和分析设计。另一部分反其道而行之，相对当今程序设计语言的多样性和多元化发展趋势而选择了能够适应更多平台的语言无关分析。当分析手段和程序语言 本身脱离了紧密的结合之后，虽然可能会造成一部分针对某些程序语言的特效分析手法没有施展的空间，但是类似于光谱药和特效药的功能特点一般，夸平台语言的全局代码静态分析仍然是 稳稳当当地占据了程序分析方法的一席之地。 统 是中间代码分析优化框架的佼佼者。它的 全名叫做低层虚拟机，听上去比较像虚拟技术。但是其实低层虚拟机是 统中核心的中间代码所依赖的低层 指令集架构 （ ， 统本身是为了把程序转换成其特有的中间代码而进行平台无关的深度分析优化。在 统里面虽然不乏全局分析和优化，但是从整个 系统的优化分析工具的组成来看，过程内部优化仍然占了大多数。全局代码分析也是 统支持良好的一种分析手段， 在 合实验室的提案下，基于 全局死锁规避分析应运而生。 局代码静态分析 全局代码静态分析问世已经很久了，其难度和立足点之高让很多研究 进展缓慢。 由于现代程序语言 为了突出工程性，减少逻辑复杂度，逼近人性化等等其他富有影响力的因素而采取了诸如强化面向对象设计，模块化，构件化，提升抽象度的手段来削弱编写程序的人员成本。但是这个工程决策的负面影响必然是牵扯到了运行时的程序性能。程序的庞大 化和复杂度上升很大程度上增加了编译器方面的压力，造成了很多优秀的分析优化方法无法在零散的程序片段上施展。全局代码分析在这方面受到的压力是最明显的。除了上述工程人力成本方面的考虑，还有各种因素会影响着全程序分析难以实现。比如分布式程序通过远距离信息交流完成功能，但是各个组件之间仅存有限的接口可以访问，出于安全以及设计的要求考虑，它们互相之间并不了解对方内部运行的机制。 分布式系统的全局优化只能借助优秀的架构师来统筹，全局代码在这类系统中是无法触及的。又或者，含有第三方外包软件的应用程序越来越多，而第三方所开发的 软件库不一定是可见的，也会出现类似于组件之间可见度非常低的情况。那么对于全代码分析来说，就算运用技术手段使得第三方库绕过分析的范围，或者部分进行分析，也还是会出现一部分的黑盒从而无法达成最理想的效果。 即便如此，近年来多核技术的发展造成了并行计算领域的加速进化，而传统的过程内部优化是难以胜任并行程序复杂的并发关系分析的。那么全局代码分析由此机会重新得到了 基于 全局代码静态分析 第 2 页 共 25 页 充分的重视而生机勃勃。并行程序之间的协议和行为只能够在过程间分析优化中取得效果，不仅仅是增强程序的并行性 这类应用更是需要站在全代码的角度进行分析才能更加精准 地把握并行线程的互动 ，例如在全局寻找符合代码交换律的代码段 1等提高程序并行率的研究 ，死锁嗅探和规避也需要如此 。 于是，全局代码分析在计算机界推进并行计算技术的同时得到了进一步的关注，能够绽放出新的光芒。 统 统是一套独特的编译基础架构，它支持多层次（ 化 2。这个设计的初衷是为了能够支持深度的过程间优化和配置驱动（ 化，并且在这过程中保持商业强度的性能。 虚拟指令集是整个系统的核心，它既有低层的指令特征，又有高级的 类型信息，使得低层代码的变换优化和高层的激进的过程间优化同时成为可能。 译框架也同时被设计和实现出来，并且成为了诸多学术研究的孵化地。 统架构 统本身从多层次深度优化的出发点而设计，意图让非常具有侵略性的优化贯穿整个程序的生命周期，并且同时保持优化的实用性。 传统的编译器把编译程序分开为编译和链接两个阶段：首先编译单个的源程序文件，产出目标的 件；然后，通过链接器把相互关联的 件有组织地拼接成一个整体的目标可执行代码。如果系统足够简单的话，基本上大部分的工作都 是由编译器完成的，链接器顶多只需要按照要求填充符号标记和相关地址再拼接文件就可以了。 然保留了这个传统的编译器链接器分工，是为了将源文件互不干涉地被编译这个好处留着。但是编译好的源代码并不是直接变成本地机器所熟识的可执行代码，而是编译成 拟指令集。 链接器把虚拟指令集连接起来， 运行优化步骤，然后才会把虚拟指令集转换成本地可执行代码。这么做是为了 够运行复杂的全局优化，而这对于整个优化系统是至关重要的。 在优化过程中有一部分的优化变换代价十分高昂，不适合在运行时出现，所以当机 器处于闲时就能利用线下的优化器运行这些复杂的优化，改善目标代码的性能，在下一次运行目标代码之前做好事先准备。 统的运行时优化避免了传统 运行时优化的两个弊端：一是它采集的信息主要是从开发者方面得到的，而不是最终用户；二是开发者很少真的用到采集来的信息。 且开发者从中也不需要额外的工作就可以完成优化工作。 拟指令集 统和其他的系统相比，很重要一个区别就是它使用的代码表现形式。为了达到期望的深度优化目标，其代码表 现形式必须要具有低层的容易产生变换的简单指令，又需要高层的类型信息等等来支持 链接时和链接后的深度优化。 拟指令集代表了一个虚拟的架构，其中组成的元素是普通处理器内最关键并且常用的指令，但是避开了特定机器类型的限制，例如物理寄存器，流水线，底层调用规范和陷阱等。 拟指令集采用三地址代码，是 构和语言无关编译器长年使用的代码类型。从相貌上看来，三地址代码具有小型，操作正交等特性，和机器码非常相像，而且可以很容易被压缩以减小 代码体积。而且 用 态单定义）形式作为 代码的主要形式。 式规定每个变量定义恰好一次，并且所有的引用全被该次定义所影响。 式能够大大简化许多数据流分析。 取强类型系统，每个 量和内存分配都是拥有类型标记的，而且所有的操作都是按照严格的类型规则运行的。这个信息使得非常广泛的高级变换能够在低级代码 基于 全局代码静态分析 第 3 页 共 25 页 上发生。而且严格类型也致使一致性检查能够探测出各中的类型不匹配错误。 显示内存分配和统一内存模型也是一大特点。牵涉到内存的优化通常能让编译器十分头疼，显示的内存分配可以把内存分配信息更好地传递给编译器，所以分配内存的指令 被加入了虚拟指令集中。 指令集中也包含了异常处