基于谓词代码的编译优化技术研究

程序中大量分支指令的存在,严重制约了体系结构和编译器开发并行性的能力。有效发掘指令级并行性的一个主要挑战是要克服分支指令带来的限制。利用谓词执行可有效地删除分支,将分支指令转换为谓词代码,从而扩大了指令调度的范围并且删除了分支误测带来的性能损失。阐述了基于谓词代码的指令调度、软件流水、寄存器分配、指令归并等编译优化技术。设计并实现了一个基于谓词代码的指令调度算法。实验表明,对谓词代码进行编译优化,能有效提高指令并行度,缩短代码执行时间,提高程序性能。     

动态二进制翻译中的冗余LOAD删除优化技术

动态二进制翻译系统是根据程序的动态执行信息来将源机器上的可执行代码翻译成目标机器上的可执行代码.在翻译成中间表示的过程中会产生一些冗余的LOAD指令,为提高代码的执行效率,提出对这些LOAD指令进行冗余删除优化.该优化技术可以使优化效果超过其自身的开销,达到优化的目的.     

基于持续监控的动态内联优化

动态编译技术是非常有效的一项优化技术,但是,当前的信息采集与持续监控技术面临运行开销过大、信息精度不够以及代码过渡膨胀等问题.以Intel ORP(open runtime platform)作为基础平台,设计了基于在线反馈与持续监控的动态编译系统;根据当前信息采集技术存在的一些问题改进了代码插装机制;实现了对虚方法接收者对象的类型持续监控;编译系统根据在线采集和持续监控所获得的信息指导内联优化;针对持续监控过程中产生大量无用代码的问题,提出了已编译代码动态卸载方法.SpecJVM98和Java Grande Forum Benchmark等测试基准的运行结果表明,被测程序的平均性能得到了提高.同时,代码动态卸载算法也有效地减轻了系统的运行时负载.     

相关路径静态分析中协同式逆向推理方法

相关路径生成,是程序动态分析中的一种重要方法.通过对目标执行路径的获取和分析来生成与其相关的近邻执行路径,在程序行为特征分析、编译优化和调试等研究方向有重要的作用.现有的方法主要通过改变路径节点序列来生成近邻的路径集合,由于缺乏关键节点的路径引导信息,导致生成大量冗余或者无效的路径集合.提出采用协同式逆向分析的近邻路径生成方法,针对目标路径的后置条件,采用逆向符号分析方法产生程序各个基本块的前置条件作为执行路径的引导信息.同时,通过调整距离因子k的取值,可以有针对性地生成与目标路径的编辑距离不超过k的近邻路径集合.实验结果表明:与现有方法相比,该方法在准确性和效率方面有明显的优势.     

GCC中基于值剖视的代码特例化

基于剖视的优化技术根据程序先前运行时收集的剖视信息来指导编译优化。文章给出了一种在GCC中基于值剖视的代码特例化实现方法。NPB和SPEC CPU2000基准程序测试结果表明,该代码特例化方法能够有效提高程序性能,同时引入的开销较小。     

ARM程序设计优化策略与技术

程序优化是指软件编程结束后,利用软件开发工具对程序进行调整和改进,让程序充分利用资源,提高运行效率,缩减代码尺寸的过程。按照优化的侧重点不同,程序优化可分为运行速度优化和代码尺寸优化。运行速度优化是指在充分掌握软硬件特性的基础上,通过应用程序结构调整等手段来降低完成指定任务所需执行的指令数。     

一种基于动态插桩的JavaScript反事实执行方法

目前,静态分析技术已被广泛用于JavaScript程序的安全性分析。但是由于JavaScript支持通过eval等方法在运行时动态生成代码,仅靠静态分析难以取得动态生成代码。一种可行的解决方法是通过动态运行目标程序取得动态生成代码,再对其进行静态分析。然而,动态运行目标程序只能覆盖有限的执行路径,会遗漏其他执行路径中的动态生成代码。针对这一问题,基于动态插桩实现了一个反事实执行方法。该方法通过修改JavaScript引擎,在其语法解析阶段动态插入反事实执行体,使条件不成立的分支路径和当前执行路径均能够得到执行。通过该插桩方式,即使嵌套调用eval等方法,也能在其动态生成代码中完成插桩。同时,还实现了一种按需undo方法,以消除反事实执行体中赋值操作带来的影响,且能够避免冗余操作。实验结果表明,实现的方法能够有效地扩大动态分析中执行路径的覆盖面。     

面向数据库模式变更的代码演化推荐方法

许多软件依赖数据库来存储信息。数据库模式的变更可能导致程序代码中与数据库相关的SQL语句代码不能正常执行,因而找出一种能够直接定位到需要修改的SQL语句代码并推荐出这些代码可能的修改方案的方法是十分必要的。提出的面向数据库模式变更的代码演化推荐方法首先自动检测出软件系统数据库模式发生的变更,随后采用程序切片技术得出与数据库操作相关的程序切片;确定受到数据库模式变更影响的程序切片后,利用源程序转换流程图算法将程序切片转化为程序流程图;根据程序流程图的分支条件得出SQL语句所有可能的特定执行路径;最后采用图映射的方法对每条路径的SQL语句进行变更语句推荐,推荐出新数据库模式下可执行的SQL语句。为了验证该方法的可行性,实现了一个用于自动检测数据库模式变更并能推荐出SQL语句演化后代码的插件工具。     

减小运行时优化开销的方法

运行时优化在程序运行期间，根据采集到的相关信息，确定程序的热点并进行优化，从而加速程序的执行。然而，运行时优化本身有一定的开销，有时候会抵消甚至超出优化得到的效果。该文设计和实现了一个基于SMP/IPF(英特尔安腾系列)/Linux架构的自适应二进制代码优化/编译框架，其中包含了运行时优化。分析了运行时优化的阶段和开销，并介绍了在设计和实现该框架的过程中，为减小这种开销所提出的思路和采用的方法。     

动态二进制翻译器QEMU中冗余指令消除技术研究

计算机体系结构的不断发展,使得代码迁移工作变得尤为重要,在这种背景下,二进制翻译技术应运而生。二进制翻译技术使得在已有的体系结构下生成的可执行文件自动迁移到新的体系结构中成为可能。以龙芯2F处理器为硬件平台,研究二进制翻译器QEMU中冗余指令的删除优化技术,使用代码活性分析方法来降低代码膨胀度,提高执行效率。该优化技术带来的优化效果超过其自身开销,具有实际优化价值。     

Safe,multiphase bounds check elimination in Java

As part of its type‐safety regime, Java's semantics require precise exceptions at runtime when programs attempt out‐of‐bound array accesses. This paper describes a Java implementation that utilizes a multiphase approach to identifying safe array accesses. This approach reduces runtime overhead by spreading the out‐of‐bounds checking effort across multiple phases of compilation and execution: production of mobile code from source code, just‐in‐time (JIT) compilation in the virtual machine, application method invocations, and the execution of individual array accesses. The code producer uses multiple passes (including common subexpression elimination, load elimination, induction variable substitution, speculation of dynamically verified invariants, and inequality constraint analysis) to identify unnecessary bounds checks and prove their redundancy. During class‐loading and JIT compilation, the virtual machine verifies the proofs, inserts code to dynamically validate speculated invariants, and generates code specialized under the assumption that the speculated invariants hold. During each runtime method invocation, the method parameters and other inputs are checked against the speculated invariants, and execution reverts to unoptimized code if the speculated invariants do not hold. The combined effect of the multiple phases is to shift the effort associated with bounds‐checking array access to phases that are executed earlier and less frequently, thus, reducing runtime overhead. Experimental results show that this approach is able to eliminate more bounds checks than prior approaches with minimal overhead during JIT compilation. These results also show the contribution of each of the passes to the overall elimination. Furthermore, this approach increased the speed at which the benchmarks executed by up to 16%. Copyright © 2010 John Wiley & Sons, Ltd.     

结合模型和迭代编译优化矩阵相乘程序

高性能计算应用程序获得的持续性能与机器峰值性能的差距日益扩大,很大程度上制约着高性能计算的发展。程序变换通过对程序进行适应机器体系结构特征的优化变换,提高程序实际执行性能,是解决该问题的有效途径之一。很多高级程序变换均具有数值参数,为了获得最优性能,需要仔细选择参数的值。传统的编译器使用简单的模型选择这些参数,难以适应日趋复杂的硬件平台和应用程序。迭代编译通过生成不同的程序版本并在实际硬件评估上运行程序,来评估关键优化参数的值并决定能够产生最优性能的值,显著优于静态方法,但巨大的优化开销限制了其应用范围。本文针对矩阵相乘程序提出一种结合性能模型和迭代编译的优化方法,利用基于对机器体系结构和程序的经验知识构造性能模型约束优化空间,并使用遗传算法加速在优化空间中寻找优秀解的过程。实验结果表明,该方法可以较低的开销获得更优的性能优化效果。     

Data Flow Analysis as a General Concept for the Transport of Verifiable Program Annotations

Just-in-Time (JIT) compilation is frequently employed in order to speed-up the execution of platform-independent and dynamically extensible mobile code applications. Since the time required for dynamic compilation directly influences a program's execution time, JIT compilers usually utilize only simple and fast techniques for program analysis and optimization. To improve further the analysis and optimization process of such compilers program annotations can be used.However, mostly all current annotation approaches suffer from the fact that the verification of transmitted program information is time consuming and therefore will not be carried out on the consumer side of a mobile code system. In this paper, we present a verifiable annotation technique that is based on a well known iterative data flow algorithm and which can be used for the transmission of all program information that can be derived through data flow analysis. Preliminary measurements of compilation and verification time indicate that the presented technique seems to be implementable and therefore could be used as an all-purpose transportation technique for safe program annotations.     

Interprocedural partial redundancy elimination with application todistributed memory compilation

Partial Redundancy Elimination (PRE) is a general scheme for suppressing partial redundancies which encompasses traditional optimizations like loop invariant code motion and redundant code elimination. In this paper, we address the problem of performing this optimization interprocedurally. We present an Interprocedural Partial Redundancy Elimination (IPRE) scheme based upon a new, concise, full program representation. Our method is applicable to arbitrary recursive programs. We use interprocedural partial redundancy elimination for placement of communication and communication preprocessing statements while compiling for distributed memory parallel machines. We have implemented our scheme as an extension to the Fortran D compilation system. We present experimental results from two codes compiled using our system to demonstrate the useful of IPRE in distributed memory compilation     

监督学习模型指导的函数级编译优化参数选择方法研究

基于机器学习的迭代编译方法可以在对新程序进行迭代编译时,有效预测新程序的最佳优化参数组合。现有方法在模型训练过程中存在优化参数组合搜索效率较低、程序特征表示不恰当、预测精度不高的问题。因此,基于机器学习的迭代编译方法是当前迭代编译领域内的一个研究热点,其研究挑战在于学习算法选择、优化参数搜索以及程序特征表示等问题。基于监督学习技术,提出了一种程序优化参数预测方法。该方法首先通过约束多目标粒子群算法对优化参数空间进行搜索,找到样本函数的最佳优化参数;然后,通过动静结合的程序特征表示技术,对函数特征进行抽取;最后,通过由函数特征和优化参数形成的样本构建监督学习模型,对新程序的优化参数进行预测。分别采用k近邻法和softmax回归建立统计模型,实验结果表明,新方法在NPB测试集和大型科学计算程序上实现了较好的预测性能。     

Dynamic Event Generation for Runtime Checking using the JDI

Approaches to runtime checking have to track the execution of a software system and therefore have to deal with generating and processing execution events. Often these techniques are applied at the code level – either by inserting new source code prior to the compilation or by modifying the target code, e.g. Java byte code, before running the program.The jassda [4,3] framework and tool enable runtime checking of Java programs against a CSP-like specification. For generating events it uses the Java Debug Interface (JDI) and thus no modifications to the code are necessary. Another advantage is that events are generated on demand, i.e. dynamically at runtime it is determined which events to generate for the current debug run without modifying the program itself. This paper shows how this event generation is done by the jassda framework.     

Speculative optimizations for interpreting environments

Most constrained systems use interpreters to run mobile programs written in Java. Such interpreters are designed to minimize resource usage and often do not allow mobile code in the devices to be changed. For this reason, runtime optimization is typically not supported, even though it is completely feasible. In this paper, we propose optimistic optimization as a concept for improving application performance in restricted interpreter environments. In an optimistic optimization, a mobile program is restructured speculatively during code generation. This requires that it is possible to undo such optimizations, at runtime, if an incorrect use is detected or the set of available classes has changed when compared with compile time. Experimental results show that interpreted applications using optimistic optimizations tend to run faster when compared with their conventionally optimized counterparts. Compared with standard load elimination, reductions in runtimes of up to 9% for optimistic load elimination and up to 23% for the combined optimization were achieved. Whereas an average performance improvement of 1.87% for optimistic load elimination and 3.7% for the combined optimization could be realized. Copyright © 2013 John Wiley & Sons, Ltd.