Optimizing Java: theory and practice
ZORAN BUDIMLIC AND KEN KENNEDY
Rice University Computer Science Department, 6100 South Main, Houston TX 77005, U.S.A.
SUMMARY
The enormous popularity of the Internet has made an instant star of the Java programming language. Javarsquo;s portability, reusability, security and clean design has made it the language of choice for Web-based applications and a popular alternative to C for object-oriented programming. Unfortunately, the performance of the standard Java implementation, even with just-in-time compilation technology, is far behind the most popular languages today. The need for an aggressive optimizing compiler for Java is clear.
Building on preliminary experience with the JavaSoft bytecode optimizer, this paper explores some of the issues that arise in building efficient implementations of Java. A number of interesting problems are presented by the Java language design, making classical optimization strategies much harder to implement. On the other hand, Java presents the opportunity for some new optimizations, unique for this language. 1997 by John Wiley amp; Sons, Ltd.
1. INTRODUCTION
In this paper we present the results of a summer project on optimizingJava doneat JavaSoft DivisionofSunMicrosystems,alongwith preliminaryresultsofcontinuingresearchatRice University. Many interesting compilation problems emerge when trying to optimize Java, including:
1.unavailabilityofthecompleteprogramatcompilationtime,eliminatingopportunitiesfor interprocedural optimization
2. the exception mechanism, which limits code movement optimizations
3. the high abstraction level of the Java Virtual Machine instruction codes (bytecodes),which hides many machine dependent optimization opportunities from the compiler.
In this paper, we discuss those problems, propose some solutions, and suggest areas for further research.
This paper is organized into several sections. Section 2 describes possible approaches to optimizing Java. Section 3 presents the design of our current research compiler, including the optimizations implemented and advantages and limitations of the compilation model it employs. Section 4 describes an approach to Java optimization that relaxes the compilation model and presents some new optimizations with preliminary results. Section 5 describes an aggressive strategy for Java optimization, discussing its potential and applicability. Section 6 addresses the Java exception mechanism, which presents a problem for optimizationregardlessof the strategy employed.The final Section draws conclusionsfrom this preliminary work and present some directions for future research.
CCC 1040–3108/97/060445–19 $17.50 Received March 1997
1997 by John Wiley amp; Sons, Ltd.
2. OPTIMIZATION STRATEGIES
There are three distinct strategies for optimizing Java compilation, each having advantages and disadvantages for particular applications and situations. In this paper, we describe each of them and discuss their applicability to different problems for which Java might be used.
The first approach is to stay within the Java compilation model defined by Sun Microsystems – code is generated for the Java Virtual Machine (VM), the compiler processes one class at a time, and the generatedcodeis completelyindependentofthe platformon which it is executed. This means that the compiler cannot make any assumptions about the machine on which the VM code will be executed and the VM cannot make any assumptions about the compiler that is being used to generate VM bytecodes.
This model is used in a project begun at JavaSoft that is discussed in Section 3 of the paper. This approach has an obvious advantage: no changes are made to the current Java execution environment, so the portability, security and functionality that are the hallmarks of the Java technologyare preserved.Unfortunately,that compilationmodel, along with the combination of the Java features, leaves only limited room for performance improvement. However, for applications where absolute portability and security are crucial, the compiler must stay within the boundaries of this model. Given that requirement, it is nevertheless worthwhile to exploit every opportunity for performance improvement no matter how small.
An approach at the opposite end of the spectrum would be to sacrifice the portability and security of the Java Virtual Machine, concentrating instead on the construction of the highly sophisticated optimizing native code compiler. Although this would sacrifice the portability of the VM object code and the security required for execution over the Internet, the source code would remain portable and it could always be recompiled using the first compilation strategy for use over the Internet. This approach is suggested for the very highperformance server applications where Fortran and C are currently being used. Some important aspects of this strategy are discussed in Section 5.
A third approachwould combinefeaturesof thefirst two,compromisingsomeportability and functionality for better performance. As we will show in Section 4, relaxing the constraints on the way the Java code is currently compiled and executed can impact the performance significantly. This model would still keep all of the convenience and power of execution over the Internet and the Java Virtual Machine security model would still be enforced. The compiler and the VM would know about each other, weakening the absolute portabilitymodel,so thatthecross knowledgecould beused to achievehigherperformance. Underthis scheme the compilationprocesswould notbe as simple as in the JavaSoftmodel. This model would be suitable for applications that require execution over the net, with all thesecurity ofthe Java VM instructionset, butwhichare willing to belimited to the specific compilers and VMs that are supporting this model.
As al
剩余内容已隐藏，支付完成后下载完整资料
优化Java：理论与实践
佐兰·布尔迪克利和肯·肯尼迪
赖斯大学计算机科学系，美国南休斯敦6100南，德克萨斯州77005
摘要
互联网的巨大普及使Java编程语言立即成为明星。 Java的可移植性，可重用性，安全性和简洁的设计使其成为基于Web的应用程序的首选语言，并且是面向对象编程的C 的流行替代方案。 不幸的是，即使采用即时编译技术，标准Java实现的性能也远远落后于当今最流行的语言。 很明显，需要针对Java的积极优化编译器。
基于对JavaSoft字节码优化器的初步经验，本文探讨了在构建Java的有效实现中出现的一些问题。 Java语言设计提出了许多有趣的问题，这使得经典的优化策略难以实施。 另一方面，Java为这种语言独有的一些新优化提供了机会。1997年，约翰·威利父子公司（John Wiley＆Sons，Ltd.）
1.引言
在本文中，我们介绍了一个由SunMicrosystems的JavaSoft Division完成的关于优化Java的夏季项目的结果，以及水稻大学的持续研究的初步结果。 尝试优化Java时会出现许多有趣的编译问题，包括：
1.编译时没有完整的程序，消除了过程间优化的机会
2.异常机制，它限制了代码移动的优化
3. Java虚拟机指令代码（字节码）的高抽象级别，这对编译器隐藏了许多与机器相关的优化机会。
在本文中，我们讨论了这些问题，提出了一些解决方案，并提出了需要进一步研究的领域。
本文分为几个部分。 第2节描述了优化Java的可能方法。 第3节介绍了我们当前研究的编译器的设计，包括所实现的优化以及所采用的编译模型的优缺点。 第4节描述了Java优化的方法，该方法放宽了编译模型，并提供了一些具有初步结果的新优化。 第5节介绍Java优化的积极策略，并讨论其潜力和适用性。 第6节介绍了Java异常机制，无论采用何种策略，它都提出了一个优化问题。最后一部分从这一初步工作中得出了结论，并提出了未来研究的方向。
2.优化策略
有三种不同的优化Java编译的策略，每种策略在特定的应用程序和情况下各有利弊。在本文中，我们描述了它们中的每一个，并讨论了它们对Java可能使用的不同问题的适用性。
第一种方法是保留在Sun Microsystems定义的Java编译模型中-为Java虚拟机（VM）生成代码，编译器一次处理一个类，并且生成的代码完全独立于执行该代码的平台。这意味着编译器无法对将在其上执行VM代码的计算机进行任何假设，并且VM无法对将用于生成VM字节码的编译器进行任何假设。
该模型在JavaSoft开始的项目中使用，该项目在本文的第3节中进行了讨论。这种方法具有明显的优势：无需对当前的Java执行环境进行任何更改，因此保留了Java技术的可移植性，安全性和功能性。不幸的是，该编译模型以及Java功能的组合都没有了。只有有限的性能提升空间。但是，对于绝对可移植性和安全性至关重要的应用程序，编译器必须位于此模型的范围之内。鉴于此要求，无论大小如何，都应抓住一切机会来提高性能。
相反，一种方法是牺牲Java虚拟机的可移植性和安全性，而专注于构建高度复杂的优化本机代码编译器。尽管这会牺牲VM对象代码的可移植性和在Internet上执行所需的安全性，但是源代码将保持可移植性，并且始终可以使用在Internet上使用的第一种编译策略对其进行重新编译。对于目前正在使用Fortran和C 的高性能服务器应用程序，建议使用此方法。第5节讨论了此策略的一些重要方面。
第三种方法将结合前两者的功能，从而牺牲一些可移植性和功能性，以获得更好的性能。正如我们将在第4节中显示的那样，放宽对当前Java代码的编译和执行方式的约束可能会极大地影响性能。该模型仍将保留通过Internet执行的所有便利和功能，并且Java虚拟机安全模型仍将得到实施。编译器和VM会相互了解，从而削弱了绝对的可移植性模型，因此可以利用交叉知识来实现更高的性能。在这种方案下，编译过程不会像Java软件模型中那样简单。该模型将适合具有Java VM指令集的所有安全性但需要通过网络执行的应用程序，但希望将其限于支持该模型的特定编译器和VM。
如前所述，每种策略都有其优点和缺点，应选择正确的模型来满足预期应用程序的需求。
3.标准模型
在本节中，我们描述了当前编译器中使用的第一种方法。在该项目的设计和实现过程中，一位作者是JavaSoft的一名暑期实习生，期间完成了许多优化Java的有趣问题，揭示了迄今为止使用的编译模型的一些局限性。
我们的研究编译器基于分布式Sun Java编译器，其中包括一个独立的字节码到字节码优化器。之所以选择这种结构，是因为有两个原因。首先，当JavaSoft开始努力时，优化器更容易开发和调试，因为它与JavaSoft的javac编译器的当前版本无关。其次，该结构还使优化器独立于任何编译器，因此可用于优化其他Java编译器以及编译为Java VM的任何其他语言生成的代码。第三，它可以用作许多即时（JIT）运行时编译器的优化预传递，这些编译器现已得到广泛使用。
编译器本身分为一系列相互松散连接的阶段：
1.解析输入类并将其加载到内存中
2.将堆栈机字节码转换为传统的表达式树并构建控制流程图（CFG）
3.将CFG转换为静态单一分配（SSA）形式
4.在SSA上执行一些标准优化-死代码消除和恒定传播
5.从SSA恢复CFG，必要时重命名本地变量
6.在CFG本身上执行本地优化-本地公共子表达式消除，复制传播和寄存器分配
7.生成最终程序为JavaVM字节码，并执行窥孔优化（堆栈分配，用更便宜的运算符替换）。
在接下来的几节中，我们将讨论其中的一些操作。
3.1．高级源恢复
Java字节码不是特别适合优化的中间表示形式。文献中的大多数优化都适用于类似表达式的代码，使用变量和寄存器而不是堆栈。最常见的中间表示形式是类似于汇编语言的三地址和两地址指令序列。
Java VM是一台堆栈计算机，这使数据流分析变得复杂。我们遇到的最常见的困难是需要跟踪变量在操作员堆栈之间的使用情况。这促使我们开发出将Java VM字节码转换为表达式树的过程，该树更适合于分析。
转换过程很简单。通过扫描Java VM字节码中的分支来标识基本块，并在此过程中标识分支目标。通过这种方式建立CFG的结构后，我们将每个基本块中的字节码转换为表达式树。
通过遍历使用表达式堆栈模拟虚拟机行为的基本块，可以完成向表达式树的转换。有以下三种情况：
1.遇到构造字节码时（即在堆栈上创建常量或将局部变量压入堆栈的字节码），相应的常量或变量将被压入表达式堆栈
2.模拟算术运算时，将从表达式堆栈中弹出适当数量的操作数，构造所得表达式，然后将其推回表达式堆栈。
3.通过在表达式堆栈中弹出顶部表达式并构造一个赋值，可以模拟将值存储在堆栈顶部的局部变量中的字节码。
在为每个基本块构造了表达式树之后，必须在每个基本块条目处合并表达式堆栈。构造表达式时，表达式树构造函数将任意的“寄存器”名称分配给局部变量。如果两个或多个块在其出口处具有非空的表达式栈，并且它们在CFG中的同一点合并，则表达式栈必须统一。这是通过将堆栈上的每个表达式与其他堆栈上的适当表达式统一来完成的。将必须统一的复杂表达式转换为对临时变量的赋值，然后将该变量与其他表达式统一。进行统一分配的代码插入到合并点之后的块的开头。对CFG中的分割点执行了类似的合并操作，在分割之前在块的末尾插入了代码（如有必要）。
3.2． SSA的构造和使用
用于许多编译器优化的最快已知算法使用SSA形式表示正在优化的程序。这是我们在编译器中选择它作为中间表示的主要原因。 SSA的构建和重建算法在其他地方有详细描述。
Java程序的SSA构造和重构中的一个问题尚未解决。我们当前的实现仅将方法的局部变量转换为SSA名称，而忽略所有实例变量。这是因为某些代码移动优化（例如，循环不变代码运动）在恢复CFG时需要SSA重构算法来重命名变量。当然，对于Java中的实例变量和全局变量来说，这是不可接受的，因为这会更改类接口。我们认为，从SSA（因此也从其优化）省略实例变量会导致所生成代码的质量显着下降。我们计划使用Briggs，Schillingburg和Simpson开发的技术，这些技术在存储位置使用标签来处理实例变量。 SSA上的所有优化都将意识到实例变量标签，并会相应地采取措施，因此在重构CFG之后，不会更改类接口。
3.3．消除死代码并不断传播
消除死代码是传统语言中一项重要且易于理解的优化。在将此优化应用于Java时，重要的是要了解Java异常机制的影响。由于许多Java指令可能会导致异常，因此死代码消除算法的预通过必须将所有这些指令标记为关键（例如不可删除），从而限制了死代码消除的机会。
本文后面将讨论一些处理异常的方法。
对于恒定传播，我们使用众所周知的Wegman–Zadeck算法。
3.4.局部通用子表达式消除
在实现局部公共子表达式消除中，我们使用了众所周知的值编号算法。值编号为消除常见子表达式提供了非常自然的框架。程序中所有变量均已编号，只有两个变量具有相同的值时，它们的编号才相同。仅当两个表达式具有相同的结构并且其操作数具有相同的值编号时，它们才具有相同的值（并获得相同的值编号）。发现值编号后，发现常见的子表达式，立即存储为给定子表达式计算的值并用简单的负荷替换所有后续计算就变得很简单了。
3.5.注册和堆栈分配
Java虚拟机是一个堆栈计算机，因此在通常意义上它没有寄存器的概念。此外，它没有内存的概念，只是可能存储大量临时变量的本地变量和用于操作的堆栈。但是，访问堆栈与本地变量的速度存在实质性差异。
四个局部变量（0–3）的特殊代码用于分配给它们的加载和存储操作比正常操作短。使用这些变量时，这将导致代码更短，执行速度更快。同样，前64个局部变量可以放入当前正在开发的某些Java微处理器上的寄存器高速缓存中。可以合理预期大多数专用Java微处理器以及常规处理器的运行时环境会将一些局部变量缓存在其寄存器中。尽管速度差异还不够大（相对于传统处理器的寄存器访问，缓存访问和内存访问时间），不足以证明完整的Graphcoloring分配算法的实现是合理的，但它们的意义足以促使我们实现一种简单的方法，但是快速有效，启发式以利用所描述的不对称性。寄存器分配算法如下：
（i）如果编译后的方法足够大，则将输入值（最初存储在从0开始的局部变量中）考虑在内，以进行寄存器分配和重定位，否则将其保留在原始位置
（ii）对于每个基本块，列出可用寄存器
（iii）遍历每个块，将最低的可用寄存器分配给已分配了值的变量，并用其分配的寄存器替换局部变量的用法
（iv）如果当前指令最后一次使用该变量，则将相应的寄存器放在空闲列表中
（v）在为每个基本块分配寄存器之后，将寄存器分配给全局值。跨越基本块的每个局部变量都被视为全局变量，并且为整个方法分配了唯一的寄存器。从基本块寄存器分配中分配的最大寄存器编号开始，依次为这些变量分配寄存器。
尽管这种简单的策略虽然不及图着色分配器那么激进和有效，但在实践中却非常有效，尤其是对于面向对象编程风格非常常见的短方法而言。
如前所述，运算符堆栈通常是Java虚拟机中最快的内存。尽可能多地使用堆栈来存储中间值将大大加快代码的速度。我们使用非常简单的代码传递来发现重用堆栈的可能性：
（a）如果存储在某个局部变量中的值仅使用一次，并在下一条指令中使用，则消除该存储和后续的加载，将其保留在堆栈上。这是最常见的情况，因为它是将大型表达式分解为子表达式并分别进行计算而导致的。
（b）如果存储在本地变量中的值被接下来的两条指令使用了两次，则存储和随后的两次加载将被替换为堆栈上的值。这种情况是第3.1节中描述的统一算法和通用子表达式消除算法的共同结果。
再次，这是一种非常简单的方法，尽管有更多有效的算法可以最佳地使用堆栈来生成堆栈计算机的代码，但我们发现这种方法非常适合我们的需求。
3.6.性能
性能结果非常有趣，因为实际执行时间的改善大于指令数量的减少。这主要是局部通用子表达式消除的结果，该子表达式用寄存器引用替换了许多数组访问，并且对窥孔进行了优化，用执行相同工作的廉价指令替换了现有指令。
在我们看来，在此编译模型下可能获得的总体性能是适度的。可以实现一些附加的优化，并且可以对当前的优化进行一些改进，但是除非编译模型发生变化，否则我们认为除了即时编译器可以提供的优化之外，还不可能进行较大的改进。为了获得更大的改进，至少需要牺牲当前Java编译和执行模型的一部分。
4.放松模型
如果可以释放当前Java编译模型的某些规则，则可能是更有效的Java优化方法。特别是，鉴于标准的Java面向对象编码风格（频繁的方法调用，许多短的方法）以及过程间优化技术（例如积极的方法内联化）可能会带来实质性的性能提升。
不幸的是，现有的Java编译和执行模型不允许使用常规语言的文献中所述的过程间分析，但最终类和方法除外。原因是编译器必须假定同一类内部的方法调用以及其他对象的方法都进行后期绑定。这是在编译时手头没有整个程序的结果。
但是，如果我们更改模型，则可能会进行一些过程间优化，下一节中介绍的对象内联将查看编译器可用的所有类，并且只要可以证明方法调用必须是静态的，就可以内联整个对象。代码复制依赖于运行时机制来区分优化类和非优化类，并决定使用哪个实例化实例和哪个实例继承。
4.1.对象
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[410004]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
