* doc/abc_optimization/* : Detailed elaboration on abc analysis in the cacaovm written by Klaus Braeutigam
--- /dev/null
+\documentclass[11pt,a4paper]{article}\r
+\r
+\usepackage{gwa}\r
+\usepackage{graphicx}\r
+\usepackage{url}\r
+\usepackage{ngerman}\r
+\usepackage[latin1]{inputenc}\r
+\usepackage{textcomp}\r
+\usepackage{multicol}\r
+\r
+\begin{document}\r
+\r
+\title{Optimization of Array Bounds Checking in the Context of Cacao Java Virtual Machine}\r
+\r
+\author{\r
+ \authN{Bräutigam Klaus}\\\r
+ \matNr{0825965}\\\r
+ \authI{Institute of Computer Languages}\\\r
+ \authU{Technical University of Vienna}\\\r
+ \email{e0825965@student.tuwien.ac.at}\\\\\r
+ \authN{Bachelor Thesis BSc. in Informatics - Software and Information\r
+ Engineering 033 534 }\\\r
+ \authN{supervised by Univ.Prof. Dr. Andreas Krall}\r
+}\r
+\r
+\maketitle\r
+\r
+\begin{multicols}{2}\r
+\r
+%% Abstract -------------------------------------------------------------------\r
+\r
+\abstract{\r
+This document deals with array bounds check optimizations in a very general and historical\r
+way but also strongly relates to the details of implementation within the \r
+Cacao Java Virtual Machine that was developed by the Institute of Computer Languages\r
+of the Technical University of Vienna. Good and sustainable problem solutions \r
+can only be found if previous ideas are studied to improve own considerations\r
+and even more important if failures that happened in the past are not repeated.\r
+So the first main part is dedicated to a study of previous\r
+approaches concerning array bounds check optimization and their environments \r
+to obtain a solid knowledge base for the general problem. \r
+The second part describes details and relations important\r
+to understand the technique choosen for the Cacao Java VM. So the document should\r
+also be interesting for people only searching for a comprehensive overview of \r
+the abstract array bounds check optimization problem.\r
+\r
+}\r
+\r
+%% Introduction ---------------------------------------------------------------\r
+\r
+\section{Introduction}\r
+Array bounds checking and the optimizations necessary for efficient\r
+realization were exhaustively researched and discussed in the past four\r
+or five decades. The rise of high level computer programming languages led\r
+directly to several improvements of the background and environments of them.\r
+For example array accesses have always been common malfunction sources and\r
+security holes. If an array access index is not within the bounds of the array,\r
+memory space is accessed illegally. This can lead to dramatic problems.\r
+Therefore computer language architects recognized very fast that\r
+these array accesses must be validated before execution to increase the safety and\r
+stability of applications. So in most cases array access indices are compared \r
+to the array bounds before executing them. But this introduces some\r
+kind of overhead during compilation and or execution. Due to the fact that\r
+processed information amount increases much faster than our technological\r
+calculation possibilities any type of overhead must be reduced or completely\r
+removed from applications in any thinkable way. As will be seen in the\r
+following chapters the approaches and techniques for reducing overhead of\r
+array bounds checks can be very different. To completely understand the\r
+problem of array bounds checks optimization (short ABCs) all related aspects \r
+must be taken into account and all topics must also be seen from a more\r
+abstract view.\r
+\r
+%% General aspects of ABCs ----------------------------------------------------\r
+\r
+\section{A Generic Reflection of ABCs\label{sec:structure}}\r
+This chapter provides a solid overview for ABC optimizations. The\r
+most common forms of implementation are explained and the neccesity for\r
+improvements of ABC optimizations are motivated. Furthermore some background\r
+information will be provided to get a feeling for the relations of the topic.\r
+But it must be kept in mind that an exhaustive explanation of the topic is\r
+far out of the documents scope so we will only touch on the general ideas.\r
+\r
+ \subsection{Implementation of Array Bounds Checking}\r
+ Before designing new optmization techniques for ABCs it's important to know\r
+ exactly how these checks are implemented. There are many ways to realize\r
+ ABCs. Elaborateness and performance are important to keep in mind when\r
+ choosing a technique and also the insertion method is interesting because\r
+ it is greatly connected to the language architecture. Should tests\r
+ be integreated automatically without developers knowledge or should\r
+ ABCs only be integrated selectively by programmers or quality assurance.\r
+ \r
+ \subsubsection{Compare Instruction Strategy}\r
+ Most implementations are done using compare instructions of the\r
+ processor and a conditional jump to react to failed comparisons. For this\r
+ technique the array inception and length are obtained and compared to\r
+ the index. For a more detailed description and good examples please\r
+ consult\r
+ \cite{AComparisonOfArrayBoundsCheckingOnSuperscalarAndVLIWArchitectures:2002}.\r
+ For some languages like Java that assure that arrays only start\r
+ with index null only one check is necessary to check lower and \r
+ upper bounds using an unsigned compare instruction. This assures that\r
+ indices are always within the specified array bounds and that exceptions\r
+ or other reactions are done on the right point of program execution.\r
+\r
+ \subsubsection{Hardware Implementation}\r
+ It is also possible to implement ABCs directly and completely in\r
+ hardware. This means some more effort in processor architecture but\r
+ the resulting run-time overhead of ABC execution can be reduced \r
+ practically to 0.0\%. There have been several approaches from Sun\r
+ Microsystems, Inc. to design a new generation of processors that are\r
+ capable of this. \r
+ \cite{ProcessorWithAcceleratedArrayAcessBoundsChecking:2000}\r
+ for example describes a processor that uses two hardware comparators and\r
+ a disjunction to inform the instruction execution unit about the validness\r
+ of the array access instruction.\r
+ \cite{ApparatusAndMethodForArrayBoundsCheckingWithAShadowFile:2001} is an\r
+ even more improved way. In addition it uses a shadow register to further\r
+ boost and integrate ABCs into the general instruction flow of the processor.\r
+\r
+ \subsubsection{Other Approaches}\r
+ Other more exotic approaches of ABC implementation also exist.\r
+ An interesting one can be found in \r
+ \cite{ArrayBoundsCheckEliminationUtilizingAPageProtectionMechanism:2003}\r
+ where the processor page protection mechanism is used to identify ABCs and\r
+ even improve their effectiveness by eliminating unnecessary ones.\r
+ \r
+ \subsection{The Real Overhead Introduced by ABCs}\r
+ Before crying out for costly and time-consuming optimizations for a specific\r
+ mechanism we will analyze the overhead caused by this. Is it\r
+ really worth while studying and researching the topic? This is in many cases a difficult\r
+ question because future trends must also be considered to get a clear result.\r
+ Concerning ABCs it depends on the ABC implementation, the language\r
+ design and architecture and on the application itself.\r
+ \r
+ \subsubsection{Overhead Reduction through Hardware}\r
+ For decades information processing machines were mainly designed as single\r
+ processor systems that didn't really considered modern programming techniques\r
+ and patterns. Nearly all higher-level improvements that were reached in\r
+ computer programming were done in an abstract way using software\r
+ (virtual machines, multiprocessing, null pointer checks, ABCs\ldots). In the past\r
+ there were some approaches that tried to completely integrate ABCs in hardware, but\r
+ these were refused very fast. Nevertheless we can\r
+ view something in connection to ABCs by comparing benchmarks of the same\r
+ application on the same virtual machines running on different processor\r
+ generations. For example take overhead benchmark results from\r
+ \cite{AVerifiableControlFlowAwareConstraintAnalyzerForBoundsCheckElimination:2009}\r
+ and compare them to that of\r
+ \cite{SafeMultiphaseBondsCheckEliminationInJava:2010} and it's easy to\r
+ recognize that the same application on the same virtual machine with the same\r
+ configuration produces a different overhead. In this case the reason can be\r
+ found very fast. The first benchmark was calculated on a single processor\r
+ system where the second uses a multicore processor. This new processor\r
+ generation is able to the reduce the overhead of ABCs without changing the\r
+ technique or implementation of ABCs. So the question if ABC optimization pays\r
+ not only depends on the software but also on the hardware it is running on.\r
+ Newer processor generations will be able to furthermore reduce the overhead\r
+ raised by ABCs implemented as processor instructions but it is very unlikely\r
+ that the approaches of implementing ABCs completely in hardware will be\r
+ realized in the near future.\r
+ \r
+ \subsubsection{Overhead in Different Types of Applications}\r
+ To reduce overhead of ABCs the application where the optimization operates on\r
+ must use arrays frequently otherwise the overhead produced is insignificant\r
+ and not really measureable\cite{SafeMultiphaseBondsCheckEliminationInJava:2010}.\r
+ An important question is if these optimizations really pay for many\r
+ applications. For example Java is mainly used due to it's simple and clear\r
+ object oriented and abstract nature. Most developers use Java only in\r
+ conjunction with powerful frameworks like Spring and many of them only for\r
+ web-based applications. The resulting ABC overhead in these strong object\r
+ oriented applications is practically not measurable even if many arrays\r
+ are used. The overhead is mainly caused by nested method calls (invokes) which\r
+ are also very difficult to reduce. ABC optimizations only really pay on\r
+ applications with simple object relations that make excessive use of arrays\r
+ and matrix calculations like scientific research and development. But for\r
+ these cases it is maybe better and easier to use extremely optimized data\r
+ structures that are recognized by machines and executed in a special way.\r
+ \cite{EliminationOfJavaArrayBoundsChecksInThePresenceOfIndirection:2002}\r
+ mentions some libraries and also explain some new special data structures\r
+ that follow this approach.\r
+ \r
+ \subsubsection{Necessarity for ABC Optimization}\r
+ It's difficult to argue pro/contra to ABC optimization and the approach that\r
+ should be taken to implement it because this strongly depends on the language\r
+ architecture and many other factors discussed here. But in general it should\r
+ be the architects and implementors target to evolve the language to the most\r
+ effective, efficient and clear state. Even if hardware is capable of executing\r
+ ABCs without any resulting overhead it is better to eliminate unnecessary code\r
+ to improve low-level code quality cleanness and clearance. Program code at\r
+ any abstraction layer should not contain any superfluous instructions or code\r
+ parts even if they have no impact on execution time or security. Moreover some\r
+ slight processor architectures (embedded systems) maybe will never be capable\r
+ of implementing ABC in hardware!\r
+\r
+ \subsection{Important Relations to ABC Optimization}\r
+ This chapter explains some important basic conditions that should\r
+ be noticed before starting to think about ABC optimization techniques but\r
+ some of them are valid for nearly all kinds of optimizations. At first the array\r
+ access index types are important to be studied in detail to identify possible\r
+ limitations raised by them. The next important fact is that optimizations\r
+ only pay if their benefits outperform the generated overhead. It should\r
+ also be kept in mind that the elaborateness and form of implementation\r
+ dramatically influences the effectiveness of the optimization.\r
+ \r
+ \subsubsection{Array Access Index Types}\r
+ The array access index type must also be taken into consideration for\r
+ several reasons. Most computer programming languages (from now on referred\r
+ to as languages) of even all programming paradigms accept the type integer\r
+ as array index type. The word length of this type varies in most of the cases and\r
+ furthermore signs of integral numerical types can also be treated differently.\r
+ In C/C++ integer types exist as signed or unsigned and the length is not specified\r
+ and depends mainly on the instruction length of the underlying hardware. \r
+ On the other side Java declares it's integer type explicitly signed and\r
+ 32bit wide (range from -2.147.483.648 to 2.147.483.647 in 2's complement).\r
+ The Java language furthermore declares that overflowing or underflowing values\r
+ are wrapped around which is not desired for array access index types because\r
+ there are hardly reasonable applications that access arrays using overflowing index\r
+ expressions. \cite{JavaLanguageSpecificationv3.0:2005}\r
+ This source of malfunctions and security leaks must also be tackled precisely\r
+ while designing optimization mechanisms.\r
+ \r
+ \subsubsection{Benefits to Execution Time Ratio}\r
+ The ABC optimization benefits must always outperform the execution\r
+ time necessary to calculate them. It is not acceptable that an optimization is\r
+ implemented that saves execution time for some applications and slows others\r
+ down. There is nothing to gain.\r
+ \cite{AComprehensiveApproachToArrayBoundsCheckEliminationForJava:2002}\r
+ for example shows that activated ABC optimization together with others\r
+ slows down some applications of the used benchmark. This is extremely important\r
+ to consider for optimization techniques that work during Just-In-Time\r
+ compilation and execution where expensive, elaborate and in the first\r
+ instance disturbing processes must be omitted as far as possible. As\r
+ mentioned in the next chapter this is maybe best accomplished by splitting\r
+ optimization techniques into different phases to locate them where they are\r
+ unproblematic to run.\r
+\r
+ \subsubsection{Intermediate Representation}\r
+ Which intermediate representation should the optimization operate on? This\r
+ has to be considered too. Most compilers fulfill their\r
+ compilation tasks in several phases and for this reason different intermediate\r
+ representations of the programs form. These depend completely on the compiler\r
+ architecture and the language itself especially on the programming paradigm \r
+ \cite{ModernCompilerImplementationInC:1998}.\r
+ But not only during the compilation process do new program representations\r
+ arise. For interpreted languages some kind of IR is necessary to transport\r
+ code between compiler and interpreter. For example the Java Byte Code is such\r
+ an IR that is delivered to the Java Virtual Machine and executed. If the\r
+ interpreter wants to apply some optimizations to the code it is forced to\r
+ operate on the intermediate representation delivered to him or to do an\r
+ extremely expensive transformation into an other desired form which slows down\r
+ execution even more. Java Byte Code for example is not very adequate to serve\r
+ as IR because it suffers from many problems concerning size, security\ldots \r
+ and is not really practical for exhaustive optimizations. Finally it should\r
+ not be forgotten that also high level code (Java, C++) can be a very\r
+ suitable representation for obtaining some optimization constraints!\par\r
+ \r
+ A lot of effort has been spent in using Java Byte Code annotations for\r
+ integrating optimization information into conventional class files that are\r
+ ignored by most compilers and allowing some to boost execution performance.\r
+ But these approaches have also a lot of disadvantages because the annotations\r
+ are abused, the usage is not standardized, further increased size and process\r
+ amount\ldots.\r
+ \cite{AFrameworkForOptimizingJavaUsingAttributes:2000} describes an example\r
+ framework that follows the previously discussed one. Also\r
+ \cite{VerifiableAnnotationsForEmbeddedJavaEnvironments:2005} can be an\r
+ interesting source for the beginning because it focuses on especially on \r
+ three important optimizations and on low cost checks. Furthermore\r
+ \cite{VerifiableRangeAnalysisAnnotationsForArrayBoundsCheckElimination:2007}\r
+ and \cite{SafeBoundsCheckAnnotations:2008} deal with annotations specifically\r
+ for ABC optimizations. In the historic review many more approaches will be\r
+ mentioned that are based on this construct.\par\r
+ \r
+ Another way to deal with the problem of IR is to use a completely new approach\r
+ and in the past several forms based on Static Single Assignment (SSA) where\r
+ researched and proven to be the commonly used ones in the future. The form is based on\r
+ the constraint that every variable can have only one point of assignment and\r
+ not more or less. But many more constraints and ideas were integrated into\r
+ different modern SSA forms that were adapted and optimized for several\r
+ reasons and techniques. For getting a general idea of SSA forms consult\r
+ \cite{AVerifiableSSAProgramRepresentationForAgressiveCompilerOptimization:2006}.\r
+ \cite{SafeTSAATypeSafeAndReferentiallySecureMobileCodeRepresentationBasedOnStaticSingleAssignmentForm:2001}\r
+ explains SafeTSA which is a type safe and size optimized SSA form and used in\r
+ \cite{UsingTheSafeTSARepresentationToBoostThePerformanceOfAnExistingJavaVirtualMachine:2002}\r
+ to optimize execution performance of a Java Virtual Machine. Another approach\r
+ is covered by\r
+ \cite{AVerifiableSSAProgramRepresentationForAgressiveCompilerOptimization:2006}\r
+ that focuses on clean and efficient embedding of range checks into other aggressive\r
+ optimization phases.\r
+ \cite{ABCDEliminatingArrayBoundsChecksOnDemand:2000} uses a new representation\r
+ by introducing new constraints for dealing efficiently with program branches\r
+ (if-else, while\ldots) called Extended SSA form (eSSA).\r
+ Another SSA form named HSSA is introduced in conjunction with a new\r
+ optimization algorithm ABCE in\r
+ \cite{ArrayBoundsCheckEliminationForJavaBasedOnSparseRepresentation:2009}. \r
+ Finally\r
+ \cite{TowardsArrayBoundCheckEliminationInJavaTMVirtualMachineLanguage:1999}\r
+ even introduces a new Java Byte Code representation called JVMLa that is also\r
+ suitable for several optimization tasks. Nearly all of these systems are not\r
+ commonly used and are therefore not standardized but show how future\r
+ intermediate representations could be designed or influenced by different\r
+ ideas.\r
+\r
+ \subsubsection{Positioning of Optimizations}\r
+ Being generally aware of all previously discussed circumstances another very\r
+ important aspect must be recognized regarding positioning of optimizations.\r
+ The main differentiation can be seen between compiled and interpreted\r
+ languages.\par\r
+ \r
+ Compiled languages are restricted to optimizations that can be calculated at\r
+ compile time (mainly static optimizations). This imposes really big\r
+ limitations on the possible and suitable techniques but expensive\r
+ computations do not therefore really mean big problems. High compile\r
+ time is widely accepted with special optimization level\r
+ parameters (for example -O3 for most C compilers). For development and\r
+ debugging the optimizations are not really necessary so they are omitted and\r
+ for deployment one optimized version is created where expensive and long\r
+ running optimizations are not seen problematic.\par\r
+ \r
+ For interpreted language architectures new aspects must be taken into account.\r
+ On the one hand the possibility for powerful highly dynamic optimizations\r
+ arise that use information only available at run time but on the other hand\r
+ it is unacceptable to compute expensive optimizations because it would slow\r
+ down execution dramatically. So the most successful approach would probably be\r
+ to split up dynamic optimizations to compile- and run time parts.\r
+ Expensive precalculations are delegated to the compiler and fast and effective\r
+ optimizations that use information obtained at compile- and run time are\r
+ calculated by the interpreter (virtual machine). This approach was\r
+ exhaustively researched by most recently published ABC optimization\r
+ techniques. At compile time some constraints and equalities/unequalities are\r
+ infered from high level code and intermediate representations through\r
+ theorem proving and even speculation and special optimizing virtual machines\r
+ interpret these constraints and annotations to calculate very effective\r
+ optimizations efficiently.\r
+ \cite{SafeMultiphaseBondsCheckEliminationInJava:2010} and all previous\r
+ versions of the same authors\r
+ \cite{AVerifiableControlFlowAwareConstraintAnalyzerForBoundsCheckElimination:2009},\r
+ \cite{SpeculativeImprovementsToVerfifiableBoundsCheckElimination:2008}\ldots \r
+ are recommended for understanding the complete idea. Also most previously\r
+ mentioned approaches that use annotations in any form (Soot framework)\r
+ basically follow it.\par\r
+ \r
+ One must also consider that optimizations must fit into the compilation and\r
+ interpretation process. Optimizations should not be an isolated process that\r
+ is quickly added to the compiler/interpreter architecture at the end of the\r
+ design process. Moreover optimizations and related techniques and\r
+ especially used intermediate representations should be taken into\r
+ account very early in language architecture design to get clean, clear,\r
+ effective and efficient compilation and interpretation processes overall \r
+ \cite{ModernCompilerImplementationInC:1998}.\r
+ Nearly all mechanisms researched in the context of Java and the Java Virtual\r
+ Machines suffer from the drawback that many optimizations are added to the\r
+ constructs too late and are therefore not really suitable for the complete\r
+ systems.\r
+ \r
+ \subsection{Types of ABCs}\r
+ ABCs can always be found before array access instructions. In Java the\r
+ instructions are provided for every primitive type as xaload and xastore where\r
+ x represents the array type (integer, float, signed byte, character\ldots).\r
+ But not only the array access instructions itself are important for ABCs but\r
+ also the context were they appear. Therefore some placements of\r
+ ABCs are of special significance. These are now described a little bit in\r
+ detail to understand which forms of interest can arise. The first three\r
+ classify if ABCs can be proven statically, dynamic or never as really\r
+ necessary during execution for keeping to the Java conventions. The second\r
+ three deal with the code structure where these ABCs occure. A good explanation\r
+ concerning raw classification of ABCs in general can be found in \r
+ \cite{AFreshLookAtOptimizingArrayBoundChecking:1990} and more recently by the\r
+ same author in\r
+ \cite{OptimizingArrayBoundChecksUsingFlowAnalysis:1993}.\r
+ \r
+ \subsubsection{Redundant ABCs}\r
+ Some ABCs that are inserted by primitive insertion algorithms are completely\r
+ redundant and can be statically proven unnecessary at all. For example three\r
+ sequential array accesses a[i] and a[i+1] and a[i+2] lead to three inserted\r
+ ABCs but the first two of them are completely redundant because the third\r
+ dominates them. The overall number of these checks is very low and the\r
+ execution time amount occupied by them even lower. So there\r
+ are hardly reasonable optimizations possible through elimination of them but\r
+ they are very easy and cheap to compute and remove so it should be done for\r
+ reasons of cleaness and completeness. These are only important to be\r
+ removed if they occur within loops.\r
+ \r
+ \subsubsection{Partial Redundant ABCs}\r
+ Some ABCs are related through different program branches that arise because of\r
+ if-else or while statements that lead to ABCs that are partially redundant.\r
+ Sometimes they can be simplified or partially eliminated. These ABCs also arise\r
+ relatively often in programs and therefore optimization through\r
+ elimination or code motion can really pay. For a detailed explanation\r
+ on this topic please consult the good considerations in\r
+ \cite{GlobalOptimizationBySuppressionOfPartialRedundancies:1979}.\r
+ \r
+ \subsubsection{Necessary ABCs}\r
+ There are ABCs in existence that exactly represent what they are invented for.\r
+ They are placed in front of array access instructions that can't be proven to\r
+ be valid so there are ABCs that can not be eliminated but sometimes simplified\r
+ or moved using code motion procedures. A good and simple example for this are\r
+ array access indices read from command line or from an external data source\r
+ like files or a database!\r
+ They occur in dependence on the application from seldom to very often. Whether an ABC\r
+ can be proven superfluous or necessary depends stronly on the power of the\r
+ used optimization technique. Sometimes array accesses that deal with\r
+ indirection or interprocedural array access program structures can't be proven\r
+ unnecessary although they are. This will also be explained in the chapter about global ABCs.\r
+ Advanced techniques that are capable of proving these exotic kinds of\r
+ redundant or partial redundant ABCs can sometimes eliminate or simplify big\r
+ amounts of elaborate and unnecessary ABCs.\r
+ \r
+ \subsubsection{Local ABCs}\r
+ Local ABCs are found in straight program structures without branches, loops\r
+ and other conditional statements. These code parts are executed\r
+ sequentially without possible interruptions and are generally very simple and\r
+ short. Local ABCs are in most cases redundant and can be completely eliminated\r
+ but don't have much impact on program execution time.\r
+ \r
+ \subsubsection{Global ABCs}\r
+ Global ABCs are much more difficult. We must at first distinguish between\r
+ interprocedural and intraprocedural global ABCs. If several method invokes are\r
+ integrated into one array access it is hard to automatically analyze the\r
+ structure and obtain constraints especially in languages like Java with\r
+ dynamic class loading. These are called interprocedural. Only very few\r
+ techniques have the power to prove such elaborate ABCs unnecessary. If\r
+ ABCs are only analyzed in the context of one method without\r
+ additional method invokes they are called intraprocedural. Also array accesses\r
+ where indices are again placed in arrays (indirection) can be very challenging\r
+ to prove redudant. A technique that pays special attention to ABCs in the\r
+ presence of indirection is\r
+ \cite{EliminationOfJavaArrayBoundsChecksInThePresenceOfIndirection:2002} that\r
+ gives a solid insight into the difficulties raised by this topic. Due to the\r
+ frequent occurence in combination with matrix calculations and other costly\r
+ procedures optimizations of global ABCs can reduce execution time of\r
+ programs.\r
+ \r
+ \subsubsection{ABCs in Loops}\r
+ ABCs that are placed in loops deserve special attention because here\r
+ the biggest runtime overheads of all possible ABC types arise. If unnecessary ABCs\r
+ are placed in loops they are often repeated and result in huge\r
+ fractions of execution time. Sometimes Local and Global ABCs are found in\r
+ loops and can be eliminated or simplified and sometimes ABCs can even be moved\r
+ out of the loop using code motion techniques. This allows dramatic optimizations.\r
+ One problem that arises is that some optimizations change the program behavior\r
+ and especially the exception throw conventions of the Java language can\r
+ introduce a big additional effort. All this must be taken into account. ABC loop\r
+ optimization is so important and powerful that some techniques reach good\r
+ improvements only by analyzing some common loop structures/patterns. For\r
+ example\r
+ \cite{ArrayBoundsCheckEliminationInTheContextOfDeoptimization:2009} describes\r
+ the mechanisms implemented in the HotSpot Java Virtual Machine that is based\r
+ on this idea.\r
+\r
+%% Historic review of ABCs ----------------------------------------------------\r
+\r
+\section{A Historic Review of ABCs and Related Optimization}\r
+The presentation of history concerning ABC optimizations will be done in a\r
+chronological order to underline the whole evolution. To get a quick insight into\r
+the different documents some kind of classification will always be provided that\r
+keeps as far as possible to parameters explained in the past chapter so that it\r
+should be possible to quickly understand the raw idea described.\r
+\r
+ \subsection{The Early Beginning}\r
+ The first approaches for dealing with ABC optimization all operate on high level\r
+ code representation (no additional intermediate representation necessary)and\r
+ use data flow graphs to represent program parts in an abstract manner. The real\r
+ ideas of ABCs and optimizations in this direction can't be explicitly\r
+ attributed to one person.\par\r
+ \r
+ In the authors opinion William H. Harrison was the\r
+ first that directly covered the problem. In May 1977 he describes in \r
+ \cite{CompilerAnalysisOfTheValueRangesForVariables:1977} the more\r
+ general problem of value range analysis of variables. Array bound checks are a\r
+ subproblem of this because array indices are only numerical variables that must\r
+ keep to value ranges (0..arraylength). He introduced in his paper an algorithm\r
+ called Range Propagation that obtains variable value ranges starting\r
+ with [-Inf:+Inf] by analyzing the related programing structures for each\r
+ variable [0..100] for example. Another algorithm Range Analysis even\r
+ covers the problem of induction with variables and therefore mainly concerns\r
+ loops. The algorithm builds through derivations linear equations that are then\r
+ solved based on a data flow analysis. He also introduced the idea of loop\r
+ counting, general program diagnostic and program termination that can identify\r
+ several mistakes and malfunctions to the programmer. This can be seen as the\r
+ real origin of the idea how to insert and optimize ABCs effectively. His\r
+ algorithms are inserted into the conventional compilation process and he even\r
+ considered overall execution time of compilation in his algorithms.\par \r
+ \r
+ In 1977 nearly at the same time Norihisa Suzuki and Kiyoshi Ishihata composed\r
+ \cite{ImplementationOfAnArrayBoundChecker:1977} where they explicitly insert\r
+ ABCs in high level code in the form of assert statements in front of\r
+ array accesses to provide comfortable error information. This is done by\r
+ deducing formulas from the program and using a theorem prover to decide if an\r
+ ABC (assertion) is necessary for an access instruction or not. Because only static\r
+ analysis is done no real powerful optimizations can be applied. Especially the\r
+ intraprocedural form limits the general success but most local and even some\r
+ global ABCs are tackled. All things considered this paper is the first really\r
+ modern approach for dealing with theorem proving of ABCs and definitly a good\r
+ starting point for studying the topic in depth.\par\r
+ \r
+ In 1979 E. Morel and C. Renvoise published\r
+ \cite{GlobalOptimizationBySuppressionOfPartialRedundancies:1979} that\r
+ introduced the idea of formal consideration of partial redundancies that are\r
+ also necessary for more elaborte analyzing of Global ABCs. For really\r
+ understanding partial redundant ABCs this paper is a must.\par\r
+\r
+ In 1982 Victoria Markstein, John Cocke and Peter Markstein presented a new\r
+ approach for optimizing ABCs in \r
+ \cite{OptimizationOfRangeChecking:1982}. For the first time the idea is\r
+ documented that code parts with high execution frequencies (loops) deserve\r
+ special attention (analysis effort). They introduced usage of subexpression\r
+ elimination and code motion for optimizing ABCs. The technique operates on the\r
+ code by deriving Strongly Connected Regions SCRs using USE and DEF\r
+ functions. These were also used previously by\r
+ \cite{CompilerAnalysisOfTheValueRangesForVariables:1977} albeit the\r
+ explanations were much more complicated and detailed. The technique is based on\r
+ data flow analysis and meant to be integrated into a multiphase compiler after\r
+ all previous optimizations were accomplished. The same authors even obtained an\r
+ USPatent in 1987 for their ABC optimization technique\r
+ \cite{OptimizationOfRangeChecking:1987}.\par\r
+ \r
+ In 1990 Rajiv Gupta published results of his researches on ABC\r
+ optimization in \r
+ \cite{AFreshLookAtOptimizingArrayBoundChecking:1990}. He used a\r
+ so called Minimal Control Flow Graph MCFG to implement some new\r
+ revolutionary approaches like elimination of redudant ABCs, combination of\r
+ partial redundant ABCs and propagation of ABCs out of loops (code motion). It\r
+ exactly describes how the MCFG is built from source code and also the\r
+ algorithms to perform elimination, propagation and combination of ABCs. This\r
+ gives very precise guidance for first experiments with ABC optimization\r
+ algorithms and abstract representations.\r
+ \r
+ \r
+\r
+ In 1992 Jonathan M. Asuru presented in\r
+ \cite{OptimizationOfArraySubscriptRangeChecks:1992} an approach that started dealing\r
+ more precisely with Global ABCs that definitely allow more important\r
+ optimizations. He claimed that previous techniques where not able to deal with\r
+ elaborating loops (nested loops, nonconstant induction variables\ldots) and he\r
+ was right. He described two new mechanisms that were able to deal with much\r
+ more complicated program constructs than all others before.\r
+ \begin{description}\r
+ \item[Inner-Loop Guard Elimination ILGE] deals generally with conventional\r
+ known local and global ABC types.\r
+\r
+ \item[Conservative Expression Substitution CES] deals with nested loops and\r
+ partial order for related range checks. Also important with CES is Local Range\r
+ Check Optimization where the greatest lower bound and least upper bounds are\r
+ used to eliminate range checks that are redundant or partially redundant.\r
+ Furthermore Loop Relative Global Range Check Optimization builds up a system\r
+ of structures to improve nested loops checking and finally Range Check\r
+ Propagation uses range check motion to move ABCs to more efficient program\r
+ places.\r
+ \end{description} \par\r
+\r
+ In 1993 Rajiv Gupta again published his new insights into the topic in\r
+ \cite{OptimizingArrayBoundChecksUsingFlowAnalysis:1993}. Many refinements to\r
+ his previous ideas were added and the knowledge about the general problem of ABC\r
+ optimization increased. He assumed that readers are familiar with his last work \r
+ \cite{AFreshLookAtOptimizingArrayBoundChecking:1990}.\r
+ \begin{description}\r
+ \item[Local Optimization] deals with Identical Checks, Subsumed Checks with\r
+ Identical Bounds and Subsumed Checks with Identical Subscript Expressions\r
+\r
+ \item[Global Optimizations] are implemented using at first an algorithm for\r
+ modifying checks to create Redundant Checks and secondly an algorithm for the\r
+ reelimination of Redundant Checks. This important idea of first inserting new\r
+ checks and eliminating them is brilliant and will be used by further\r
+ techniques in the future. It allows the identification and resolution of difficult\r
+ redundancies.\r
+\r
+ \item[Propagation of Checks Out of Loops] is done using a refined algorithm\r
+ for propagation.\r
+ \end{description} \par\r
+\r
+ \subsection{The Chaotic Middle Ages}\r
+ Until 1995 (ca. the first two decades) only a very small group of visioners\r
+ researched ABCs and related optimization techniques. All these approaches\r
+ operated for performance and technological reasons directly on high level\r
+ program code like J. Welsh for Pascal\r
+ \cite{EconomicRangeChecksInPascal:1978} and some others for C and Fortran.\r
+ All things considered all previous approaches were based on the same general\r
+ idea of building flow graphs and applying data flow analysis. But since 1995\r
+ many scientists started researching ABC optimization and therefore a chaotic\r
+ amount of new techniques and ideas appeared. From 1995 on most approaches are\r
+ based on SSA program intermediate representations and algorithms suitable for\r
+ processing optimizations on it but also some exotic and completely new ideas\r
+ were invented and researched. \par\r
+ \r
+ In 1995 Priyadarshan Kolte and Michael Wolfe published\r
+ \cite{EliminationOfRedundantArraySubscriptRangeChecks:1995} where they explain\r
+ their ABC optimization techniques in the Nascent Fortran compiler. They use an\r
+ SSA intermediate form for induction analysis and furthermore a Check\r
+ Implication Graph CIG for global ABCs. They tried different approaches but also\r
+ mentioned that a combination of them would deliver the best results. Also some\r
+ new and more detailed information about Partial Redundant Elimination PRE is\r
+ provided that directly covers optimization of partial redundant ABCs.\r
+ \begin{description}\r
+ \item[No-Insertion NI] means optimization with check elimination without adding\r
+ any new checks that are simpler.\r
+ \item[Safe-Earliest SE] achieves a little bit more eliminations than LNI and NI\r
+ but not much and is the first of two PRE placement checks.\r
+ \item[Latest-Not-Isolated LNI] is only a second PRE placement check.\r
+ \item[Check Strengthening CS] is already described in\r
+ \cite{OptimizingArrayBoundChecksUsingFlowAnalysis:1993}.\r
+ \item[Preheader-Insertion LI] with only loop invariant checks.\r
+ \item[Preheader-Insertion Loop Limit Substitution LLS] is the clear winner if\r
+ compile time and elimination number are taken into account.\r
+ \end{description} \par\r
+ This paper proves in the end that optimized check insertion techniques are much\r
+ better than only elimination techniques. \par\r
+ \r
+ In 1998 Hongwei Xi and Frank Pfenning dealt in \r
+ \cite{EliminatingArrayBoundCheckingThroughDependentTypes:1998} with ABC\r
+ optimization in ML. So this time ABC optimization also gets very interesting\r
+ for other programming paradigms like functional programming.\par\r
+ But also S. P. Midkiff and J. E. Moreira and M. Snir published a new work\r
+ concerning this topic. \r
+ \cite{OptimizingArrayReferenceCheckingInJavaPrograms:1998} is a\r
+ very voluminous paper that directly covers the problem of ABC optimization for\r
+ the Java language. At the beginning a very formal theory about the topic is\r
+ presented and then all optimization techniques are explained in detail and\r
+ always presented with good examples on high level Java source code. This work\r
+ gives really comprehensive insight into the topic in relation to the Java\r
+ language. \par\r
+ \r
+ In 1999 the paper\r
+ \cite{TowardsArrayBoundCheckEliminationInJavaTMVirtualMachineLanguage:1999}\r
+ from Xi and Xia introduced a new idea. They did not agree with the standard\r
+ Java Virtual Machine Language JVML (Java Byte Code) and wanted to cope with\r
+ ABCs through a new system of dependent types to improve safeness of the\r
+ language and allow at the same time successful optimizations. So they\r
+ architectured a new intermediate code representation called JVMLa that should\r
+ be created by the Java Compiler and that should only contain ABCs that can't be\r
+ proven unnecessary at compile-time. This approach is questionable because the\r
+ Java Compiler output (JVML) is standardized and wide spread and a very\r
+ complicated ABC optimization part (at compile time) is assumed to function\r
+ already properly in the Java Compiler. This is very inpractical but a theoretic\r
+ idea that may by taken into account by other approaches or languages in the\r
+ future. \par\r
+ \r
+ In 2000 the previously mentioned USPatent\r
+ \cite{ProcessorWithAcceleratedArrayAcessBoundsChecking:2000} was registered and\r
+ Bodik, Gupta and Sarkar presented a new algorithm for optimized ABC execution in\r
+ \cite{ABCDEliminatingArrayBoundsChecksOnDemand:2000}. This algorithm is an\r
+ exotic one because it uses a transformation process at run time that converts\r
+ from Java Byte Code to a slightly extended SSA form (eSSA) which is normaly a\r
+ very expensive procedure and applies a constraint analyzer and solver on it that\r
+ really achieves performance gain. The used constraint analyzer adds\r
+ constraints to the eSSA instructions and build up an inequality graph IG\r
+ where only a shortest path finder (constraint solver) is applied to optimize\r
+ ABCs. This is very impressive because the whole approach is very costly but it\r
+ really pays like depicted in the results. Array Bound Check elimination on\r
+ Demand (ABCD) was really able to improve execution time of some applications in\r
+ the used benchmark. \par\r
+ \r
+ In 2001, one year after the last USPatent concerning hardware implementation of\r
+ ABCs,\r
+ \cite{ApparatusAndMethodForArrayBoundsCheckingWithAShadowFile:2001} was\r
+ registered as a new idea. Also Chin, Khoo and Xu published in \r
+ \cite{DerivingPreconditionsForArrayBoundCheckElimination:2001} some further\r
+ ideas how to derive preconditions for ABCs. This very formal approach and\r
+ documentation gives some more detailed insights into the problem of program\r
+ code analysis for optimizing ABCs. \par\r
+ \r
+ In 2002 Bentley, Watterson and Lowenthal compared execution of ABC execution on\r
+ Superscalar and VLIW hardware architecture in\r
+ \cite{AComparisonOfArrayBoundsCheckingOnSuperscalarAndVLIWArchitectures:2002}\r
+ which gives good explanations concerning implementation of ABCs using processor\r
+ compare instructions. \par\r
+\r
+ Qian, Hendren and Verbrugge present three algorithms\r
+ they implemented using the Soot framework previously mentioned in IBMs HPCJ in\r
+ \cite{AComprehensiveApproachToArrayBoundsCheckEliminationForJava:2002}. The\r
+ first algorithm Variable Constraint Analysis (VCA) works on a simplified\r
+ directed weighted graph that reflects the relations and behavior of relevant\r
+ variables (array access indices). Array Field Analysis AFA and Rectangular\r
+ Array Analysis deal with special forms of array structures that are hard to\r
+ analyze but can in some circiumstances really allow good optimizations. \par\r
+ \r
+ Gurd and Freeman et al. presented a further paper \r
+ \cite{EliminationOfJavaArrayBoundsChecksInThePresenceOfIndirection:2002} that\r
+ exactly captures the problem of ABCs in the presence of indirection what\r
+ simply means that array access indices are stored in an other array.\r
+ Optimizations in this scope are not easy and require a new technique.\r
+ The solution is not embedded in the Java Compiler or VM itself\r
+ but implemented directly as Java classes that must be used by programmers.\r
+ Three classes with different approaches are presented but only one of them\r
+ seems really useable.\r
+ \begin{description}\r
+ \item[ImmutableIntMultiarray:] The array is checked for invalid bounds and is\r
+ not allowed to be modified during index access operations!\r
+ \item[MutableImmutableStateIntMultiarray]: The array can be in two states, in\r
+ the first (mutable) bounds are checked and in the second (immutable) no checks\r
+ occur.\r
+ \item[ValueBoundedIntMultiarray:] This array forces that all entries (indices)\r
+ are within the defined range and so no exception is possible.\r
+ \end{description}\r
+ The idea and all of the explanations and details about matrix\r
+ calculations and related ABCs are really good but generally the practical\r
+ benefits are rare because Java especially wants to permit that program style of\r
+ classes has impact on run time and performance because this is exactly what\r
+ Java wants to abstract from. \par\r
+ \r
+ In 2002 Gupta, Pratt, Midkiff and Moreira registered the USPatent \r
+ \cite{MethodForOptimizingArrayBoundsChecksInPrograms:2002} where they describe a\r
+ very general method for optimizing ABCs in many facets. \par\r
+\r
+ In 2003 Motohiro Kawahito published in an interesting and very exotic idea for ABC\r
+ \cite{ArrayBoundsCheckEliminationUtilizingAPageProtectionMechanism:2003}\r
+ elimination by exploiting the hardware processors page protection mechanism.\r
+ It is based on the idea to place an array to the end/beginning of a page and\r
+ inspect if an access leaves the valid page. If the page protection throws an\r
+ exception it can be derived that the array bounds were violated. \par\r
+ \r
+ In 2005 Nguyen and Irigoin presented with\r
+ \cite{EfficientAndEffectiveArrayBoundChecking:2005}\r
+ a document that implements in a FORTRAN compiler (PIPS) some\r
+ optimizations of ABCs. The general ideas are well known but the detailed\r
+ and formal descriptions give further insights into the details of the\r
+ whole problem. The first idea is based on Guptas approach. Insert ABCs and\r
+ eliminate redudant ones. Furthermore insert ABCs that can't be proven\r
+ unnecessary. And the last important thing is an algorithm for array size\r
+ checking and analysis to prove array access vioaltions over different procedure\r
+ calls. So the technique allows interprocedural ABC optimization that is a real\r
+ challenge and rarely implemented anywhere. \par\r
+ \r
+ Another large document \r
+ \cite{SymbolicBoundsAnalysisOfPointersArrayIndicesAndAccessedMemoryRegions:2005}\r
+ was publisehd by Rugina and Rinard where they describe a new framework that\r
+ deals with general problems like access memory regions but also with bounds\r
+ analysis of pointer array indices. Due to the extensiveness of it any\r
+ explanation about this is widely out of this documents scope. \par\r
+\r
+ In 2007 two new directions were started that are explained more precisely in the\r
+ next chapter. \par\r
+ \r
+ In 2008 Popeea, Xu and Chin presented in\r
+ \cite{APracticalAndPreciseInferenceAndSpecializerForArrayBoundChecksElimination:2008}\r
+ theory and experiments that use forward relational analysis to obtain\r
+ postconditions and backward precondition derivation to inference precise\r
+ (path, context sensitive) and practical pre/postconditions for an inference\r
+ algorithm to reduce ABCs. Two phases inference and specialization (inserts\r
+ necessary checks) are used to obtain the right pre/postconditions. Weak and\r
+ strong derivation processes lead to the results. In the analysis phase\r
+ Presburger algorithm is used that has high complexity and therefore the number\r
+ of formulas must be reduced as far as possible. Flexivariants of methods mean\r
+ that due to their usage the conditions can be weaker or stronger, so different\r
+ condition strengths are calculated and stored for maximum of efficiency and\r
+ minimum of memory effort. The technique also deals with array indirections.\r
+ It works on a high level artificial language IMP that allows no loops but\r
+ recursion (fix-point analysis) and also has some other restrictions. The inference\r
+ algorithm must be run at compile time and some cases were really expensive\r
+ (\(>\)60min)! So it is not suitable for run-time checks! The approach takes interprocedural\r
+ behavior into account but without dynamic class loading, because the analysis\r
+ works bottom-up. The work is in general an extremely formal approach that makes\r
+ hard use of formulas, foreign symbols and hard to understand mathematical\r
+ definitions so the contribution is in best case of theoretical nature but not\r
+ really suitable in practice.\r
+ \r
+ \subsection{State-Of-The-Art Methodologies}\r
+ The previous path through history was very chaotic but since 2007 two\r
+ real main directions arise that have the potential to be, in the end, satisfactory for\r
+ solving the problem of ABC optimization. The first approach is implemented\r
+ already in the HotSpot Java Virtual Machine and uses a fast transformation from\r
+ Java Byte Code to an SSA based intermediate representation to apply low cost\r
+ but extremely effective analysis techniques for well known code patterns and\r
+ code structures to improve ABC optimization quality quite good and precise. The\r
+ second approach can be summarized under the name Multiphase Bound Check\r
+ Elimination (MBCE) where Java Compiler and Java Virtual Machine process separated\r
+ parts of the ABC optimization process to get high quality and highly efficient results.\r
+ The benchmarks and measurements are also suitable to reveal the real impact and\r
+ efficiency of the presented and tested techniques. \par\r
+ \r
+ In 2007 Würthinger, Wimmer and Mössenböck published \r
+ \cite{ArrayBoundsCheckEliminationForTheJavaHotSpotTMClientCompiler:2007} were\r
+ they present insights into the general functionality of the HotSpot Java VM and\r
+ the ABC optimization technique they use. Their algorithm optimizes some well\r
+ known programming patterns in Java to eliminate redundant checks and to move\r
+ partial redundant checks out of loops but keep in mind deopimization for not\r
+ provable check eliminations. This means that if checks can't be proven valid\r
+ the VM stops JIT compilation usage and goes back (ORS) to interpretation mode\r
+ (deoptimization) that is slower but easily allows keeping to the Java language\r
+ conventions like throwing exceptions at the right place\ldots. But results show\r
+ no significant increase in optimization, because the part of execution time is\r
+ not very high in the used benchmarks! A maximum of 5\% was possible! The\r
+ solution is clean, keeps to widely accepted standards and optimizes ABCs if\r
+ they occur very often. \par\r
+ \r
+ Another publication \r
+ \cite{VerifiableRangeAnalysisAnnotationsForArrayBoundsCheckElimination:2007}\r
+ from 2007 is the beginning of the most recently researched\r
+ technique of von Ronne, Psarris and Niedzielski. This document describes\r
+ verifiable annotations based on SafeTSA for optimizing ABCs by shifting slow\r
+ optimizations to a Java to SafeTSA compiler and let the JIT compiler do fast\r
+ and also efficient optimizations based on the created annotations. This allows\r
+ usage of expensive optimization techniques in time critical virtual machines\r
+ (JIT compilers). The interesting problem of integer\r
+ overflow/underflow that is not taken into account by many other techniques but\r
+ means a security and safety leak is also mentioned. This should be taken into consideration for\r
+ any implementation to react accordingly to over- and underflows. The theory of\r
+ the build constraints and linear inequality/equalities and the prover are\r
+ strongly related to \r
+ \cite{ABCDEliminatingArrayBoundsChecksOnDemand:2000} but provide\r
+ some improvements and are also meant to be only integrated into low level code\r
+ (SafeTSA) as annotations and therefore use much more expensive techniques than\r
+ ABCD can. \par\r
+ \r
+ In 2008 Nguyen and Keryell published\r
+ \cite{EfficientIntraproceduralArrayBoundChecking:2008} that describes a\r
+ further framework that is based on deriving expensive linear equalities at\r
+ compile-time and integrating them as annotations into a special form of\r
+ intermediate representation like SafeTSA for example. This approach is strongly\r
+ connected to the previous paper\r
+ \cite{VerifiableRangeAnalysisAnnotationsForArrayBoundsCheckElimination:2007}\r
+ (same introduction). They implemented a verifyable annotation generator that\r
+ is based on Jikes RVM 2.2.0. Its use extended Fourier-Motzkin's variable\r
+ elimination (FMVE) to derive proofs. The framework presented is called VBCE\r
+ Verifiable Bound Check Elimination and can be directly compared to VDF (Verifiable\r
+ Data Flow Analysis). The intraprocedural approach that is not able to deal with\r
+ interprocedural relations, works on high level code at compile time and\r
+ annotations and is therefore not suitable for direct JIT optimization.\r
+ Loop invariants are not taken into account. \par\r
+ \r
+ Furthermore in this year Gampe, von Ronne and Niedzielski et al. published two\r
+ updates\r
+ \cite{SafeBoundsCheckAnnotations:2008}\r
+ and\r
+ \cite{SpeculativeImprovementsToVerfifiableBoundsCheckElimination:2008}\r
+ of their previous work\r
+ \cite{VerifiableRangeAnalysisAnnotationsForArrayBoundsCheckElimination:2007}\r
+ that introduce speculation and newer mechanisms for annotations into the\r
+ optimization technique. The papers improves the previous framework further.\r
+ It also works on high level code at compile but now takes loop invariants into\r
+ account.\r
+ \r
+ To get the relationship of their publications on the\r
+ topic these papers should be studied at least at a glance.\r
+ \r
+ In 2009 Würthinger, Wimmer and Mössenböck revealed a further update of their\r
+ approach in \r
+ \cite{ArrayBoundsCheckEliminationInTheContextOfDeoptimization:2009} that\r
+ introduces further improvements and optimizations in the HotSpot Java VM.\r
+ The document is logically strongly related to\r
+ \cite{ArrayBoundsCheckEliminationForTheJavaHotSpotTMClientCompiler:2007}\r
+ and explains that code duplication (loop versioning) is avoided using the\r
+ interpretation mode of the VM to retain exception semantics for PRCs.\r
+ It provides a good explanation of all parts especially PRC in loops and why loops\r
+ with additional exit conditions can't be optimized. Furthermore conditions are\r
+ not managed in an equality/inequality graph but for every instruction.\r
+ Interprocedural optimizations are not taken into account due to dynamic class\r
+ loading mechanism of Java. Loading new classes leads to more information about\r
+ array acessing and can lead to deoptimization (OSR at safepoint back to stack)\r
+ if the new conditions can't prove the previously optimizations. But several\r
+ ABCs can be grouped if proveable which leads to further optimizations. All\r
+ things considered a really suitable ABC optimization technique clearly\r
+ embedded in the VM and very effective goind by the test results. \par\r
+ \r
+ \cite{ArrayBoundsCheckEliminationForJavaBasedOnSparseRepresentation:2009} from\r
+ Yang, Huang and Yang is another publication from 2009 that introduces new\r
+ algorithm ABCE that is based on HSSA form and can be used in a Java static\r
+ compiler. It builds an inequality graph and eliminates FRC (fully redudant\r
+ checks) and PRC (partially redundant checks) on it in two phases. The work is\r
+ based on the Openjc java compiler that is restricted to very few platforms and\r
+ not widespread. This compiler uses a five phase generation style where in the\r
+ fourth phase the optimization is done on code that was transformed to HSSA \r
+ form and back. That means a lot of time effort. The quality and embedding of\r
+ the algorithm into the compiler is suitable but not useable for run time\r
+ optimizations and therefore too restricted. Furthermore the article only uses\r
+ percentage of ABC elimination as benchmark and a very intransparent\r
+ performance score graphic! \par\r
+ \r
+ In the same year Gampe, von Ronne and Niedzielski et al. published another\r
+ update\r
+ \cite{AVerifiableControlFlowAwareConstraintAnalyzerForBoundsCheckElimination:2009}\r
+ of their previous work\r
+ \cite{VerifiableRangeAnalysisAnnotationsForArrayBoundsCheckElimination:2007}\r
+ that further improves their ABC optimization technique. In the document a new\r
+ more modern technique is presented that is also based on eSSA of the ABCD\r
+ algorithm and claimed to be 10\% more efficient than on SafeTSA. Then CAS\r
+ (constraint analysis system) a verifiable symbolic program constraint analyser\r
+ is presented. The approach is like previous ones also based on multiphase and\r
+ FVME. \par\r
+ \r
+ From 2010 the last known publication about ABC optimization is\r
+ \cite{SafeMultiphaseBondsCheckEliminationInJava:2010} again from Gampe, von\r
+ Ronne and Niedzielski et al. They refined the details of their\r
+ multiphase ABC optimization technique based on SafeTSA with annotations, CAS\r
+ and elaborate speculations. The results and also the additional provided\r
+ information about the topic show that the solution is practically satisfying.\r
+ The most challenging problems\r
+ connected to ABCs are solved and the solution is well embedded into a Java\r
+ Compiler and Java VM. They are not widespread but solve the problem of ABCs as\r
+ far as possible to be both efficient and convenient.\r
+\r
+ \subsection{Historical Conclusion}\r
+ Lastest research in ABC optimizations prove the assumption that only an early and\r
+ clean integration into the compilation and or interpretation process together\r
+ with suitable intermediate representations and multiple optimization phases \r
+ lead to practically satisfying results that really pay and tackle all newly\r
+ introduced problems. For Java the lately improved approach of the HotSpot Java \r
+ VM and the multiphase bound check elimination MBCE promise practical success\r
+ because all other previous techniques suffer from many drawbacks that can't\r
+ really be solved due to the overall environment of the language architecture,\r
+ hardware, future developments and other aspects of reality.\r
+\r
+%% ABCs in the Cacao Java VM --------------------------------------------------\r
+\r
+\section{ABCs in Cacao Java Virtual Machine}\r
+\r
+ \subsection{Introduction to Cacao Java Virtual Machine}\r
+ The work on the Cacao Java VM was started in 1996 by Rainhard Grafl and\r
+ Andreas Krall. They wanted to create a free, efficient and stable Java VM for\r
+ a wide variety of processor architectures and platforms. In the following years\r
+ many people joined the development team and implemented several extensions,\r
+ refinements and more and more architectures were provided. The implementation\r
+ is mostly done in C and some parts were already refactored to C++. The VM is partitioned\r
+ into modules (*.h/*.hpp with *.c/*.cpp) and keeps to the relevant Java standards \r
+ concerning behavior and general structure. For more detailed information about the\r
+ Cacao Java VM consult\r
+ \cite{HandbookForJavaCacaoVirtualMachine:1996} and\r
+ \cite{CacaoA64BitJavaVMJustInTimeCompiler:1997}.\r
+\r
+ \subsection{Array Bounds Checking in Cacao Java Virtual Machine}\r
+ In this chapter we will describe in general all necessary aspects concerning ABCs.\r
+ The Cacao Java VM uses integer compare instructions of the processor to implement\r
+ ABCs. They are generated together with all other code parts during JIT compilation\r
+ by the code generators from a special internal intermediate representation whose form\r
+ is strongly related to quadruples and derived from the Java Byte Code provided by \r
+ Java class files. ABCs are positioned in front of array accesses. \r
+ The JIT compilation is done locally on every method invocation and therefore only\r
+ allows intraprocedural optimizations, so it's impossible to solve intermediate ABC\r
+ optimization because all underlying and parallel methods must be analyzed. Some\r
+ experiments with example applications showed that execution with ABCs turned on leads\r
+ to significant execution time overhead. For some applications this overhead is\r
+ enormous so in consideration of all properties of the Cacao Java VM, its environment and\r
+ implementation an ABC optimization would be able to drastically reduce execution\r
+ time for some types of applications. In the past this motivated the creation of\r
+ an ABC optimizer in the Cacao Java VM.\r
+ \r
+ \subsection{Array Bounds Check Optimization in Cacao Java Virtual Machine}\r
+ In the year 1998 Christopher Krügel added an ABC optimizer for loops to the Cacao Java VM. This led to\r
+ improvements concerning execution time of array intensive applications. For the\r
+ reasons previously explained the optimization algorithm design was limited by \r
+ many constraints so the author only concentrated on the most important topics.\r
+ A useful generic introduction into the optimizer can be obtained from\r
+ \cite{HandbookForJavaCacaoVirtualMachine:1996} in chapter 5.7 Loop Optimization.\r
+ \r
+ \subsubsection{Power and Properties of the ABC Optimizer}\r
+ The intermediate representation (IR) used within the Cacao Java VM is not really suitable\r
+ for complicated high performance optimization like for example SSA based IRs are. This\r
+ has historical reasons, because these representation formats got famous in the past decade\r
+ and also have disadvantages so that their usage must be carefully taken into account\r
+ during the whole design process of an abstract machine or compiler.\r
+ For this reason the algorithm design was in the first instance limited by the complexity raised \r
+ by analysis and transformations of this quadruple related IR. The time consumption of the \r
+ optimizer must be recognized.\r
+ Secondly the JIT compiler architecture limited the optimization scope to one local method.\r
+ This further constraints possibilities because no global ABCs can be removed. \r
+ Due to the internal architecture of the Cacao Java VM\r
+ the structures and algorithms grew very complicated and so the developer only focused on the\r
+ most important facts concerning ABC optimization. The author concentrated only on optimization within \r
+ loops and even furthermore he restricted his algorithm to loops with induction \r
+ variables with constant grow factors (up or down). Maybe\r
+ the algorithm designer used the argument that many empirical tests in the past showed that these\r
+ kinds of loops introduce most of the execution time overhead because they are very often and commonly\r
+ used by programmers in many programming languages. The results he presented proved the concept to\r
+ be generally suitable. So he did not analyze detailed theoretical differences on redudant/\r
+ partial redudant or necessary/local/global ABCs. He simply concentrated on ABCs that seem to \r
+ cause the most overhead in loops within normal applications.\r
+\r
+ \subsubsection{Generic Design Issues of the ABC Optimizer}\r
+ This chapter will provide a generic overview over the design of the ABC optimizer \r
+ and the added improvements. A detailed explanation is, due to the amount of information,\r
+ not possible within the document's scope. For a further functional explanation please consult\r
+ \cite{HandbookForJavaCacaoVirtualMachine:1996}\r
+ and for the implementational details directly the comments in the Cacao Java VM source code. \r
+ \par\r
+ The general idea of the algorithm is to analyze a method during its JIT compilation process\r
+ for loops. This is accomplished by a depth first search of code blocks (basic blocks), then\r
+ calculating the domintators of the blocks using the Lengauer-Tarjan algorithm \r
+ \cite{AFastAlgorithmForFindingDominatorsInAFlowGraph:1979}\r
+ and detecting all loops by searching for back edges\r
+ \cite{ModernCompilerImplementationInC:1998}. These are very time consuming tasks because all\r
+ nodes (basic blocks) of the method must be iterated several times one every method compilation.\r
+ After this happend identical loops are merged, nested loops resolved and all together they are topologically sorted.\r
+ The loops are optimized in their sorted order by analyzing their loop headers and the variables/constants\r
+ involved in array access instructions. If properties are found that allow optimization the\r
+ loop and its header are adapted to suit optimal execution behavior. If nested loops exist their\r
+ combinatorical behavior must be considered.\r
+ The loop header must be adapted in such a way that new dynamic and static constraints introduced by code motion\r
+ out of the loop are inserted. In general only loops can be optimized where array index variables\r
+ are constant (full), only increment (lower bound) or only decrement (upper bound) by constant values.\r
+ Loop headers with or statements can't be optimized by the algorithm as cases\r
+ where array index variables are modified within exception handling (catch) blocks.\r
+ The original loops are replaced by the optimized (memory layout) with a conditional\r
+ jump to the originals if some dynamic constraints don't hold.\r
+ Also important for the optimization design is to notice that the original version of the loop is\r
+ held in memory parallel to the optimized one to allow correct execution with ABCs in the case\r
+ that some dynamic constraints don't hold or can't be proved. This introduces a lot of time\r
+ and space overhead during jit compilation because of the copy procedure. The correct patching\r
+ of links between code blocks and an exact exception handling add even more complexity to the\r
+ solution. So every optimized loop exists two times within the memory.\r
+\r
+ \subsubsection{Implementation of the ABC Optimizer}\r
+ \r
+ This chapter is dedicated to give an abstract but fundamental introduction\r
+ to the structure of the ABC optimization algorithm. At first\r
+ the most important data structures are explained to get an idea what kind\r
+ of data is necessary for the processes (temporary and in the end). Then we will\r
+ have a clear look at the algorithm in form of an abstract pseudocode that represents\r
+ generally all important functions and the behavior overall. The functions are\r
+ named to be self explanatory to express their meaning but for understanding the\r
+ ideas behind it maybe a good beginning would be to first consult the good generic \r
+ textual description found in\r
+ \cite{HandbookForJavaCacaoVirtualMachine:1996} in chapter 5.7 Loop Optimization.\r
+ This could give some useful introducing information before studying the real behavior.\r
+\r
+\end{multicols}\r
+\r
+ The most important data structures to understand the ABC optimization algorithm:\r
+ \r
+ \begin{description}\r
+\r
+ \item[LoopData (ld)] is a data structure that contains all necessary\r
+ intermediate information and states necessary during the ABC\r
+ optimization like detected loops, exception graphs, auxiliary\r
+ information to improve algorithm performance...\r
+\r
+ \item[JITData (jd)] contains all information about the just-in-time\r
+ compiled method that is currently optimized. This structure\r
+ contains for example the methods code blocks (basic blocks),\r
+ the number of codeblocks, exception table...\r
+\r
+ \item[LoopContainer (lc)] that holds all information about a specific\r
+ loop, like the contained code blocks for example.\r
+\r
+ \item[BasicBlocks (bb)] is a container that contains code of one\r
+ atomic code part of the method (no branch/jump) instruction\r
+ contained. So this means that a basic block is garanteed to\r
+ be executed in one exact sequence.\r
+\r
+ \end{description}\r
+ \r
+ So the most important data structures are now identified and the algorithm\r
+ can be described in pseudocode.\\\r
+\r
+ Preconditions are that the method must be completely parsed, analyzed\r
+ and all information must be correctly stored within the related\r
+ jitdata structure.\r
+\r
+ %% Codesection -----------------------------------------------------------------\r
+\r
+ \begin{verbatim}\r
+\r
+ depthFirstSearchOnMethodBasicBlocks (jd)\r
+ exploreDominators (ld)\r
+ detectLoopsInMethod (jd, ld)\r
+ analyzeDoubleLoopHeaders (ld)\r
+ analyzeNestedLoops (jd, ld)\r
+ for all LoopContainers (lc) {\r
+ optimizeSingleLoop (jd, ld, lc)\r
+ }\r
+ redirectMethodEntryBlock (jd, ld)\r
+\r
+ optimizeSingleLoop (jd, ld, lc) {\r
+ analyzeLoopForArrayAccesses (jd, ld, lc)\r
+ if ( analyzeLoopForOrAndExceptions (jd, ld, lc) == true ) {\r
+ initializeLoopHeaderConstraints (jd, ld, lc)\r
+ removeHeaderBoundChecks (jd, ld, lc)\r
+ for all BasicBlocks (bb) {\r
+ removeBoundChecks (jd, ld, lc)\r
+ }\r
+ insertChecksIntoLoopHeader (jd, ld)\r
+ }\r
+ }\r
+\r
+ initializeLoopHeaderConstraints (jd, ld, lc) {\r
+ if ( last Instruction in header is comparison against constant )\r
+ obtainLeftArgumentDetails (ld, lc)\r
+ } else if ( last Instruction in header is standard comparison ) {\r
+ obtainLeftArgumentDetails (ld, lc)\r
+ obtainRightArgumentDetails (ld, lc)\r
+ } else {\r
+ // unknown constraints for these conditions\r
+ }\r
+ if ( both sides contain changing or both have no index variables ) {\r
+ // no constraints can be proven valid\r
+ } else {\r
+ force index variable to be on left side\r
+ ForceRightSideToBeConstant (ld, lc)\r
+ obtainDynamicConstraints (ld, lc)\r
+ }\r
+ }\r
+\r
+ removeBoundChecks (jd, ld, lc) {\r
+ mergeConstraintsWithNestedLoops (ld, lc)\r
+ for all Instructions of BasicBlock (bb) {\r
+ if ( Instruction is accessing array ) {\r
+ obtainIndexVariableDetails (ld, bb)\r
+ calculateBoundConstraints (jd, ld, bb)\r
+ createLoopHeaderCodeMotionChecks (jd, ld, bb)\r
+ }\r
+ }\r
+ for all successors of BasicBlock (bb) {\r
+ removeBoundChecks (jd, ld, bb)\r
+ }\r
+ }\r
+\r
+ insertChecksIntoLoopHeader (jd, ld) {\r
+ copyCompleteLoop (jd, ld)\r
+ createBasicBlockForCodeMotionChecks (jd, ld)\r
+ insertGotoInstructionsForHandlingNewLoopHeaderBasicBlock (jd, ld)\r
+ adaptExceptionHandlingRegions (jd, ld)\r
+ informParentLoopsAboutNewHeader (jd, ld)\r
+ for all LoopHeaderCodeMotionChecks {\r
+ createInstructionsForConstraintChecks (jd, ld)\r
+ insertInstructionsIntoNewLoopHeader (jd, ld)\r
+ }\r
+ updateJumpTargetsOfLoops (jd, ld)\r
+ updateExceptionHandlingForNewAndDuplicatedLoop (jd, ld)\r
+ }\r
+ \r
+ \end{verbatim}\r
+ \r
+ %% Codesection end -------------------------------------------------------------\r
+\r
+ Postconditions are that the methods jitdata structure holds correct, executable\r
+ and optimized loop code blocks that have no semantic differences to the original form.\newline\r
+ \r
+ Keep in mind that this pseudocode representation is due to the documents scope\r
+ very generic so for more detailed information it's maybe best to directly consult\r
+ source code with its comments because it's hard to go further into details and\r
+ preserving overview.\r
+ \r
+ \subsubsection{Results and Performance of the ABC Optimizer}\r
+ This chapter presents results that were taken from an application that sieves prime numbers.\r
+\r
+ \begin{table}[!ht]\r
+ \caption{Benchmark Results of ABCs in Cacao}\r
+ \label{BenchResABCsInCacao}\r
+ \begin{center}\r
+ \begin{tabular}{lccc}\r
+ Configuration&Light&Normal&Hard\\\r
+ \hline\r
+ Runs&10&5&2\\\r
+ Normal&5,563&55,195&551,355\\\r
+ without ABCs -cb&5,562&55,192&551,414\\\r
+ with -oloop&5,560&55,182&551,350\\\r
+ \hline\r
+ \end{tabular}\r
+ \par\medskip\footnotesize\r
+ The measurements are selected to rise by a factor of 10 every level starting from 50000/10000.\r
+ \end{center}\r
+ \end{table}\r
+ \r
+ From this data with polynomic behavior a fixed per centage of speed acceleration should\r
+ be proven but it's easy to see that there are no differences between these configurations.\r
+ This encourages the assumption that ABCs are always created within the Cacao Java VM whatever\r
+ arguments are passed. The proof for this assumption will be done using assembler code output\r
+ from the machine application.\r
+ \r
+\begin{multicols}{2}\r
+ \r
+ \subsubsection{Possible Improvements for the ABC Optimizer}\r
+ The algorithm is due to its constraints of the virtual machine architecture a very conservative approach\r
+ and has no really complicated mechanisms like speculation/probability calculations or exhaustive\r
+ stack exploration. The implementation is done in C (structured programming technique) so\r
+ it's not really likely to find exhaustive performance improvements in its implementation, but like\r
+ always some possibilities remain that could lead to better results. A very expensive\r
+ part of the ABC optimization algorithm includes the necessarity for loop detection at the beginning. \r
+ This is accomplished by usage of the Lengauer-Tarjan algorithm presented in\r
+ \cite{AFastAlgorithmForFindingDominatorsInAFlowGraph:1979}. \r
+ This algorithm has good properties concerning asymptotic complexity and is especially \r
+ used by mathematicians therefore the preferred solution for very big graphs (\(>\) 30.000 nodes)\r
+ and also presented for example in \r
+ \cite{ModernCompilerImplementationInC:1998}. \r
+ But in practice methods and nested loops are in general much smaller and own only\r
+ tens or hundreds of nodes in their control flow graphs. Cooper, Harvey and Kennedy showed in\r
+ \cite{ASImpleFastDominanceAlgorithm:2001} \r
+ that an other algorithm that has higher asymptotic complexity than the Lengauer-Tarjan performs much \r
+ better for smaller graphs because the complexity issue is only really valid for very big (asymptotic) graphs \r
+ that normaly do not occur in most other programs. The authors claim that their algorithm is for\r
+ conventional method and loop graphs 2,5 times faster than the Lengauer-Tarjan algorithm. If the\r
+ experiments are valid, there exists a possibility to improve the whole ABC optimization algorithm by\r
+ using the simpler algorithm of Cooper, Harvey and Kennedy. The algorithm and especially its proof \r
+ are also much simpler to understand and therefore to implement. \par\r
+ One fact must be kept in mind. To really allow drastic improvements in algorithm performance \r
+ the complete Cacao Java Virtual Machine architecture must be reconsidered and this demanding\r
+ task can only be done in an iterative way over a long period of time.\r
+\r
+%% Conclusion -----------------------------------------------------------------\r
+\r
+\section{Conclusion}\r
+The document presented general information about the topic of ABCs overall and also preserved\r
+historical aspects that show up the evolvement. The main part dealed with ABC optimization in the\r
+Cacao Java VM. All things considered the task of successful array bounds check optimization is a complicated and\r
+challenging quest with many facets and relations. A lot of details must be considered in design and\r
+also implementation phases. But it is definitly a problem that must be solved satisfactorily for all\r
+future developments in computer languages and informatics in general because it is simply not bearable\r
+to waste computing time for any superfluous calculations for any reasons. The ABC optimization within loops in\r
+the Cacao Java Virtual Machine is very conservative due to its environment and also for historical reasons.\r
+So we are definitly far away from the perfect solution but the algorithm proved to be useful in some cases\r
+(programs) and this is the first step towards evolvement of a practical really satisfying result.\r
+\r
+%% Bibliography ---------------------------------------------------------------\r
+\r
+\bibliographystyle{alpha}\r
+\bibliography{bibfile}\r
+\r
+\end{multicols}\r
+\r
+\end{document}\r
+\r
+%% End ------------------------------------------------------------------------\r
--- /dev/null
+# General books and articles that cover the topic over all and are necessary for understanding the whole problem.\r
+###############################################################################\r
+\r
+@Manual{JavaVMSpecification1.0:1995,\r
+ title = "The {Java} Virtual Machine Specification",\r
+ month = aug,\r
+ added-by = "sti",\r
+ URL = "http://java.sun.com/doc/vmspec/VMSpec.ps",\r
+ keywords = "java, virtual machine, bytecode",\r
+ edition = "1.0 Beta",\r
+ annote = "a virtual machine similar to UCSD p-code or smalltalk.\r
+ stack-machine. dynamic loading. direct support for\r
+ object orientation (e.g. virtual method calls)",\r
+ organization = "Sun Microsystems",\r
+ year = "1995",\r
+}\r
+\r
+@Book{JavaLanguageSpecificationv3.0:2005,\r
+ author = "James Gosling and Bill Joy and Guy Steele and Gilad\r
+ Bracha",\r
+ address = "Boston, Mass.",\r
+ title = "The {Java} Language Specification, Third Edition",\r
+ publisher = "Addison-Wesley",\r
+ series = "The Java Series",\r
+ year = "2005",\r
+}\r
+\r
+@Article{CompilingJavaJustInTime:1997,\r
+ author = "Timothy Cramer and Richard Friedman and Terrence\r
+ Miller and David Seherger and Robert Wilson and Mario\r
+ Wolczko",\r
+ title = "Compiling {Java} Just in Time: Using runtime\r
+ compilation to improve {Java} program performance",\r
+ journal = "IEEE Micro",\r
+ volume = "17",\r
+ number = "3",\r
+ pages = "36--??",\r
+ month = may # "\slash " # jun,\r
+ year = "1997",\r
+ CODEN = "IEMIDZ",\r
+ ISSN = "0272-1732",\r
+ bibdate = "Tue Aug 12 12:35:06 MDT 1997",\r
+ URL = "http://pascal.computer.org/mi/books/mi1997/pdf/m3036.pdf",\r
+ acknowledgement = "Nelson H. F. Beebe, University of Utah, Department\r
+ of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake\r
+ City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1\r
+ 801 581 4148, e-mail: \path|beebe@math.utah.edu|,\r
+ \path|beebe@acm.org|, \path|beebe@computer.org|\r
+ (Internet), URL:\r
+ \path|http://www.math.utah.edu/~beebe/|",\r
+}\r
+\r
+@InProceedings{FastEffectiveCodeGenerationInAJustInTimeJavaCompiler:1998,\r
+ title = "Fast, Effective Code Generation in a Just-In-Time Java\r
+ Compiler",\r
+ author = "Ali-Reza Adl-Tabatabai and Michal Cierniak and\r
+ Guei-Yuan Lueh and Vishesh M. Parikh and James M.\r
+ Stichnoth",\r
+ year = "1998",\r
+ bibdate = "2010-01-10",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/pldi/pldi98.html#Adl-TabatabaiCLPS98",\r
+ booktitle = "PLDI",\r
+ pages = "280--290",\r
+ URL = "http://doi.acm.org/10.1145/277650.277740",\r
+}\r
+\r
+@InProceedings{TheDesignAndImplementationOfACertifyingCompiler:1998,\r
+ author = "G. Necula and P. Lee",\r
+ title = "The {D}esign and {I}mplementation of a {C}ertifying\r
+ {C}ompiler",\r
+ booktitle = "Proc. of PLDI'98",\r
+ year = "1998",\r
+ publisher = "ACM Press",\r
+}\r
+\r
+@InProceedings{DesignImplementationAndEvaluationOfOptimizationsInAJavaJustInTimeCompiler:1999,\r
+ title = "Design, Implementation, and Evaluation of\r
+ Optimizations in a Just-in-Time Compiler",\r
+ author = "Kazuaki Ishizaki and Motohiro Kawahito and Toshiaki\r
+ Yasue and Mikio Takeuchi and Takeshi Ogasawara and\r
+ Toshio Suganuma and Tamiya Onodera and Hideaki Komatsu\r
+ and Toshio Nakatani",\r
+ year = "1999",\r
+ bibdate = "2002-12-17",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/java/java1999.html#IshizakiKYTOSOKN99",\r
+ booktitle = "Java Grande",\r
+ pages = "119--128",\r
+ URL = "http://doi.acm.org/10.1145/304065.304111",\r
+}\r
+\r
+@Article{CacaoA64BitJavaVMJustInTimeCompiler:1997,\r
+ author = "Andreas Krall and Reinhard Grafl",\r
+ title = "{CACAO} -- {A} 64-bit Java{VM} Just-in-Time Compiler",\r
+ journal = "Concurrency: Practice and Experience",\r
+ volume = "9",\r
+ number = "11",\r
+ pages = "1017--1030",\r
+ month = nov,\r
+ year = "1997",\r
+ keywords = "computational science \& engineering Java: simulation\r
+ \& modeling,",\r
+}\r
+\r
+@book{HandbookForJavaCacaoVirtualMachine:1996,\r
+ title= {Handbook for Java Cacao Virtual Machine},\r
+ author= {Andreas Krall and Reinhard Grafl et al.},\r
+ publisher= {http://www.cacaovm.org},\r
+ year= {1996},\r
+ pages= {116}\r
+}\r
+\r
+@Article{MarmotAnOptimizingCompilerForJava:2000,\r
+ title = "Marmot: an optimizing compiler for Java",\r
+ author = "Robert P. Fitzgerald and Todd B. Knoblock and Erik Ruf\r
+ and Bjarne Steensgaard and David Tarditi",\r
+ journal = "Softw, Pract. Exper",\r
+ year = "2000",\r
+ number = "3",\r
+ volume = "30",\r
+ bibdate = "2003-11-25",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/journals/spe/spe30.html#FitzgeraldKRST00",\r
+ pages = "199--232",\r
+}\r
+\r
+@InProceedings{VerifiableAnnotationsForEmbeddedJavaEnvironments:2005,\r
+ title = "Verifiable annotations for embedded java\r
+ environments",\r
+ author = "Guangyu Chen and Mahmut T. Kandemir",\r
+ bibdate = "2006-02-15",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/cases/cases2005.html#ChenK05",\r
+ booktitle = "CASES",\r
+ booktitle = "Proceedings of the 2005 International Conference on\r
+ Compilers, Architecture, and Synthesis for Embedded\r
+ Systems, {CASES} 2005, San Francisco, California,\r
+ {USA}, September 24-27, 2005",\r
+ publisher = "ACM",\r
+ year = "2005",\r
+ editor = "Thomas M. Conte and Paolo Faraboschi and William H.\r
+ Mangione-Smith and Walid A. Najjar",\r
+ ISBN = "1-59593-149-X",\r
+ pages = "105--114",\r
+ URL = "http://doi.acm.org/10.1145/1086297.1086312",\r
+}\r
+\r
+@Book{ModernCompilerImplementationInC:1998,\r
+ author = "Andrew W. Appel",\r
+ title = "Modern Compiler Implementation in {C}",\r
+ publisher = "Cambridge University Press",\r
+ ISBN = "0-521-58390-X",\r
+ year = "1998",\r
+}\r
+\r
+###############################################################################\r
+# Now some references are presented that deal with intermediate representations especially with several SSA forms.\r
+###############################################################################\r
+\r
+@Article{EfficientlyComputingSSAFormAndTheControlDependenceGraph:1991,\r
+ author = "Ron Cytron and Jeanne Ferrante and Barry K. Rosen and\r
+ Mark N. Wegman and F. Kenneth Zadeck",\r
+ title = "Efficiently computing static single assignment form\r
+ and the control dependence graph",\r
+ number = "4",\r
+ volume = "13",\r
+ month = oct,\r
+ added-by = "msteiner",\r
+ URL = "http://doi.acm.org/10.1145/115372.115320",\r
+ added-at = "Sat Jul 29 09:22:31 2006",\r
+ annote = "Classical paper on the SSA (Static Single Assignment)\r
+ form for intermediary code representation in\r
+ (optimizing) compilers. See\r
+ \url{http://www.cs.man.ac.uk/~jsinger/ssa.html} for\r
+ bibliography of SSA related work.",\r
+ pages = "451--490",\r
+ journal = "TOPLAS",\r
+ year = "1991",\r
+}\r
+\r
+@Article{AVerifiableSSAProgramRepresentationForAgressiveCompilerOptimization:2006,\r
+ author = "Menon and Glew and Murphy and McCreight and Shpeisman\r
+ and Adl-Tabatabai and Petersen",\r
+ title = "A Verifiable {SSA} Program Representation for\r
+ Aggressive Compiler Optimization",\r
+ journal = "SPNOTICES: ACM SIGPLAN Notices",\r
+ volume = "41",\r
+ year = "2006",\r
+}\r
+\r
+@Article{SafeTSAATypeSafeAndReferentiallySecureMobileCodeRepresentationBasedOnStaticSingleAssignmentForm:2001,\r
+ author = "Wolfram Amme and Niall Dalton and Jeffery von Ronne\r
+ and Michael Franz",\r
+ title = "{SafeTSA}: {A} Type Safe and Referentially Secure\r
+ Mobile-Code Representation Based on Static Single\r
+ Assignment Form",\r
+ journal = "ACM SIG{\-}PLAN Notices",\r
+ volume = "36",\r
+ number = "5",\r
+ pages = "137--147",\r
+ month = may,\r
+ year = "2001",\r
+ CODEN = "SINODQ",\r
+ ISSN = "0362-1340",\r
+ bibdate = "Sun Dec 14 09:18:26 MST 2003",\r
+ bibsource = "http://www.acm.org/sigplan/pldi/pldi2001/pldi_program.html;\r
+ http://portal.acm.org/",\r
+ acknowledgement = "Nelson H. F. Beebe, University of Utah, Department\r
+ of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake\r
+ City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1\r
+ 801 581 4148, e-mail: \path|beebe@math.utah.edu|,\r
+ \path|beebe@acm.org|, \path|beebe@computer.org|\r
+ (Internet), URL:\r
+ \path|http://www.math.utah.edu/~beebe/|",\r
+}\r
+\r
+@Misc{UsingTheSafeTSARepresentationToBoostThePerformanceOfAnExistingJavaVirtualMachine:2002,\r
+ title = "Using the Safe{TSA} Representation to Boost the\r
+ Performance of an Existing Java Virtual Machine",\r
+ author = "Wolfram Amme and Jeffery Von Ronne and Michael Franz",\r
+ year = "2003",\r
+ month = dec # "~07",\r
+ abstract = "High-performance just-in-time compilers for Java need\r
+ to invest considerable effort before actual code\r
+ generation can commence. SafeTSA, a typed intermediate\r
+ representation based on SSA form, was designed to ease\r
+ this burden, decreasing the time required for dynamic\r
+ compilation, without sacrificing safety or code\r
+ quality.",\r
+ citeseer-references = "oai:CiteSeerPSU:2678; oai:CiteSeerPSU:717751;\r
+ oai:CiteSeerPSU:284691; oai:CiteSeerPSU:554814;\r
+ oai:CiteSeerPSU:114398; oai:CiteSeerPSU:328282;\r
+ oai:CiteSeerPSU:89224",\r
+ annote = "Wolfram Amme (Friedrich-Schiller-Universit at Jena;\r
+ Institut f ur Informatik; Ernst-Abbe-Platz 1-4; D-07743\r
+ Jena , Germany); Jeffery Von Ronne (Information and\r
+ Computer Science; 127B Computer Science Trailer);\r
+ Michael Franz (Information and Computer Science; 444\r
+ Computer Science Bldg);",\r
+ bibsource = "OAI-PMH server at cs1.ist.psu.edu",\r
+ language = "en",\r
+ oai = "oai:CiteSeerPSU:599324",\r
+ rights = "unrestricted",\r
+ URL = "http://citeseer.ist.psu.edu/599324.html;\r
+ http://www.ics.uci.edu/~jronne/pubs/cpc2003-safetsa5.pdf",\r
+}\r
+\r
+###############################################################################\r
+# The following documents now deal with the special topic of array bound check optimization.\r
+# The order is chronologic from the real beginning to the most recent publications.\r
+###############################################################################\r
+\r
+@Article{CompilerAnalysisOfTheValueRangesForVariables:1977,\r
+ author = "W. Harrison",\r
+ title = "Compiler analysis of the value ranges for variables",\r
+ journal = "IEEE Transactions on Software Engineering",\r
+ volume = "SE-3",\r
+ number = "3",\r
+ month = may,\r
+ year = "1977",\r
+ keywords = "data flow analysis,",\r
+}\r
+\r
+@InProceedings{ImplementationOfAnArrayBoundChecker:1977,\r
+ title = "Implementation of an Array Bound Checker",\r
+ author = "Norihisa Suzuki and Kiyoshi Ishihata",\r
+ year = "1977",\r
+ bibdate = "2010-01-28",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/popl/popl77.html#SuzukiI77",\r
+ booktitle = "POPL",\r
+ cdrom = "POPL/00001437.PDF",\r
+ pages = "132--143",\r
+ URL = "http://doi.acm.org/10.1145/512950.512963",\r
+}\r
+\r
+@Article{EconomicRangeChecksInPascal:1978,\r
+ author = "J. Welsh",\r
+ title = "Economic range checks in {Pascal}",\r
+ journal = "Software -- Practice \& Experience",\r
+ volume = "8",\r
+ pages = "85--97",\r
+ year = "1978",\r
+}\r
+\r
+@Article{GlobalOptimizationBySuppressionOfPartialRedundancies:1979,\r
+ author = "E. Morel and C. Renvoise",\r
+ title = "Global optimization by suppression of partial\r
+ redundancies",\r
+ journal = "Communications of the ACM",\r
+ volume = "22",\r
+ number = "2",\r
+ pages = "96--103",\r
+ month = feb,\r
+ year = "1979",\r
+}\r
+\r
+@InProceedings{OptimizationOfRangeChecking:1982,\r
+ author = "Victoria Markstein and John Cocke and Peter\r
+ Markstein",\r
+ title = "Optimization of Range Checking",\r
+ booktitle = "Proceedings of the {SIGPLAN} '82 Symposium on Compiler\r
+ Construction",\r
+ address = "Boston, Massachusetts",\r
+ month = jun # " 23--25,",\r
+ year = "1982",\r
+ pages = "114--119",\r
+}\r
+\r
+@Article{OptimizationOfRangeChecking:1987,\r
+ author = "Victoria Markstein and Peter Markstein and John\r
+ Cocke",\r
+ title = "Optimization of range checking",\r
+ journal = "ACM SIG{\-}PLAN Notices",\r
+ volume = "39",\r
+ number = "4",\r
+ pages = "58--65",\r
+ month = apr,\r
+ year = "2004",\r
+ CODEN = "SINODQ",\r
+ ISSN = "0362-1340",\r
+ bibdate = "Tue Apr 12 09:38:13 MDT 2005",\r
+ bibsource = "http://portal.acm.org/",\r
+ acknowledgement = "Nelson H. F. Beebe, University of Utah, Department\r
+ of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake\r
+ City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1\r
+ 801 581 4148, e-mail: \path|beebe@math.utah.edu|,\r
+ \path|beebe@acm.org|, \path|beebe@computer.org|\r
+ (Internet), URL:\r
+ \path|http://www.math.utah.edu/~beebe/|",\r
+}\r
+\r
+@Article{AFreshLookAtOptimizingArrayBoundChecking:1990,\r
+ author = "Rajiv Gupta",\r
+ title = "A fresh look at optimizing array bound checking",\r
+ journal = "ACM SIG{\-}PLAN Notices",\r
+ volume = "25",\r
+ number = "6",\r
+ pages = "272--282",\r
+ month = jun,\r
+ year = "1990",\r
+ CODEN = "SINODQ",\r
+ ISSN = "0362-1340",\r
+ bibdate = "Sun Dec 14 09:15:53 MST 2003",\r
+ bibsource = "http://portal.acm.org/",\r
+ acknowledgement = "Nelson H. F. Beebe, University of Utah, Department\r
+ of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake\r
+ City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1\r
+ 801 581 4148, e-mail: \path|beebe@math.utah.edu|,\r
+ \path|beebe@acm.org|, \path|beebe@computer.org|\r
+ (Internet), URL:\r
+ \path|http://www.math.utah.edu/~beebe/|",\r
+}\r
+\r
+@Article{OptimizationOfArraySubscriptRangeChecks:1992,\r
+ title = "Optimization of Array Subscript Range Checks",\r
+ author = "Johnathan M. Asuru",\r
+ journal = "ACM Letters on Programming Languages and Systems",\r
+ pages = "109--118",\r
+ month = jun,\r
+ year = "1992",\r
+ volume = "1",\r
+ number = "2",\r
+}\r
+\r
+@Article{OptimizingArrayBoundChecksUsingFlowAnalysis:1993,\r
+ title = "Optimizing Array Bound Checks Using Flow Analysis",\r
+ author = "Rajiv Gupta",\r
+ journal = "LOPLAS",\r
+ year = "1993",\r
+ number = "1-4",\r
+ volume = "2",\r
+ bibdate = "2002-12-02",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/journals/loplas/loplas2.html#Gupta93",\r
+ pages = "135--150",\r
+ URL = "http://doi.acm.org/10.1145/176454.176507",\r
+}\r
+\r
+@InProceedings{EliminationOfRedundantArraySubscriptRangeChecks:1995,\r
+ title = "Elimination of Redundant Array Subscript Range\r
+ Checks",\r
+ author = "Priyadarshan Kolte and Michael Wolfe",\r
+ year = "1995",\r
+ bibdate = "2010-01-10",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/pldi/pldi95.html#KolteW95",\r
+ booktitle = "PLDI",\r
+ pages = "270--278",\r
+ URL = "http://doi.acm.org/10.1145/207110.207160",\r
+}\r
+\r
+@InProceedings{EliminatingArrayBoundCheckingThroughDependentTypes:1998,\r
+ title = "Eliminating Array Bound Checking Through Dependent\r
+ Types",\r
+ author = "Hongwei Xi and Frank Pfenning",\r
+ year = "1998",\r
+ bibdate = "2010-01-10",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/pldi/pldi98.html#XiP98",\r
+ booktitle = "PLDI",\r
+ pages = "249--257",\r
+ URL = "http://doi.acm.org/10.1145/277650.277732",\r
+}\r
+\r
+@Article{OptimizingArrayReferenceCheckingInJavaPrograms:1998,\r
+ title = "Optimizing Array Reference Checking in Java Programs",\r
+ author = "Samuel P. Midkiff and Jos{\'e} E. Moreira and Marc\r
+ Snir",\r
+ journal = "IBM Systems Journal",\r
+ year = "1998",\r
+ number = "3",\r
+ volume = "37",\r
+ bibdate = "2002-01-03",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/journals/ibmsj/ibmsj37.html#MidkiffMS98",\r
+ pages = "409--453",\r
+}\r
+\r
+@InProceedings{TowardsArrayBoundCheckEliminationInJavaTMVirtualMachineLanguage:1999,\r
+ title = "Towards array bound check elimination in Java $^{TM}$\r
+ virtual machine language",\r
+ author = "Hongwei Xi and Songtao Xia",\r
+ bibdate = "2006-02-15",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/cascon/cascon1999.html#XiX99",\r
+ booktitle = "CASCON",\r
+ booktitle = "Proceedings of the 1999 conference of the Centre for\r
+ Advanced Studies on Collaborative Research, November\r
+ 8-11, 1999, Mississauga, Ontario, Canada",\r
+ publisher = "IBM",\r
+ year = "1999",\r
+ editor = "Stephen A. MacKay and J. Howard Johnson",\r
+ pages = "14",\r
+ URL = "http://doi.acm.org/10.1145/781995.782009",\r
+}\r
+\r
+@InProceedings{ABCDEliminatingArrayBoundsChecksOnDemand:2000,\r
+ author = "Rastislav Bodik and Rajiv Gupta and Vivek Sarkar",\r
+ title = "{ABCD}: eliminating array bounds checks on demand",\r
+ booktitle = "Proceedings of the ACM SIGPLAN 2000 Conference on\r
+ Programming Language Design and Implementation",\r
+ year = "2000",\r
+ pages = "321--333",\r
+ abstract = "similar to SSI, has phi functions, and also pi\r
+ functions to rename at conditional branches and after\r
+ array bounds checks",\r
+ URL = "http://doi.acm.org/10.1145/349299.349342",\r
+}\r
+\r
+@book{ProcessorWithAcceleratedArrayAcessBoundsChecking:2000,\r
+ title= {USPatent: Processor with Accelerated Array Acess Bounds Checking},\r
+ author= {Marc Tremblay and James M. O'Connor and William N. Joy},\r
+ publisher= {Sun Microsystems, Inc.},\r
+ year= {2000},\r
+ pages= {31}\r
+}\r
+\r
+@InProceedings{AFrameworkForOptimizingJavaUsingAttributes:2000,\r
+ title = "A framework for optimizing Java using attributes",\r
+ author = "Patrice Pominville and Feng Qian and Raja\r
+ Vall{\'e}e-Rai and Laurie J. Hendren and Clark\r
+ Verbrugge",\r
+ bibdate = "2006-02-15",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/cascon/cascon2000.html#PominvilleQVHV00",\r
+ booktitle = "CASCON",\r
+ booktitle = "Proceedings of the 2000 conference of the Centre for\r
+ Advanced Studies on Collaborative Research, November\r
+ 13-16, 2000, Mississauga, Ontario, Canada",\r
+ publisher = "IBM",\r
+ year = "2000",\r
+ editor = "Stephen A. MacKay and J. Howard Johnson",\r
+ pages = "8",\r
+ URL = "http://doi.acm.org/10.1145/782034.782042",\r
+}\r
+\r
+@book{ApparatusAndMethodForArrayBoundsCheckingWithAShadowFile:2001,\r
+ title= {USPatent: Apparatus and Method for Array Bounds Checking with a Shadow File},\r
+ author= {Gautam Dewan},\r
+ publisher= {Sun Microsystems, Inc.},\r
+ address= {},\r
+ year= {2001},\r
+ volume= {6},\r
+ pages= {}\r
+}\r
+\r
+@InProceedings{DerivingPreconditionsForArrayBoundCheckElimination:2001,\r
+ title = "Deriving Pre-Conditions for Array Bound Check\r
+ Elimination",\r
+ author = "Wei-Ngan Chin and Siau-Cheng Khoo and Dana N. Xu",\r
+ year = "2000",\r
+ bibdate = "2004-06-01",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/aplas/aplas2000.html#ChinKX00",\r
+ booktitle = "APLAS",\r
+ pages = "9--21",\r
+}\r
+\r
+@InProceedings{AComparisonOfArrayBoundsCheckingOnSuperscalarAndVLIWArchitectures:2002,\r
+ author = {Chris Bentley and Scott A. Watterson and David K. Lowenthal},\r
+ title = {A Comparison of Array Bounds Checking on Superscalar and VLIW Architectures},\r
+ booktitle = {IEEE Workshop on Workload Characterization},\r
+ year = {2002}\r
+}\r
+\r
+@Article{AComprehensiveApproachToArrayBoundsCheckEliminationForJava:2002,\r
+ author = "Feng Qian and Laurie Hendren and Clark Verbrugge",\r
+ title = "A Comprehensive Approach to Array Bounds Check\r
+ Elimination for {Java}",\r
+ journal = "Lecture Notes in Computer Science",\r
+ volume = "2304",\r
+ pages = "325--??",\r
+ year = "2002",\r
+ CODEN = "LNCSD9",\r
+ ISSN = "0302-9743",\r
+ bibdate = "Tue Sep 10 19:09:22 MDT 2002",\r
+ bibsource = "http://link.springer-ny.com/link/service/series/0558/tocs/t2304.htm",\r
+ URL = "http://link.springer-ny.com/link/service/series/0558/bibs/2304/23040325.htm;\r
+ http://link.springer-ny.com/link/service/series/0558/papers/2304/23040325.pdf",\r
+ acknowledgement = "Nelson H. F. Beebe, Center for Scientific\r
+ Computing, University of Utah, Department of\r
+ Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake\r
+ City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1\r
+ 801 581 4148, e-mail: \path|beebe@math.utah.edu|,\r
+ \path|beebe@acm.org|, \path|beebe@computer.org|,\r
+ \path|beebe@ieee.org| (Internet), URL:\r
+ \path|http://www.math.utah.edu/~beebe/|",\r
+}\r
+\r
+@InProceedings{EliminationOfJavaArrayBoundsChecksInThePresenceOfIndirection:2002,\r
+ author = "Mikel Luj{\'a}n and John R. Gurd and T. L. Freeman and\r
+ Jos{\'e} Migue",\r
+ title = "Elimination of Java array bounds checks in the\r
+ presence of indirection",\r
+ pages = "76--85",\r
+ booktitle = "Proceedings of the 2002 joint {ACM}-{ISCOPE}\r
+ conference on Java Grande ({JGI}-02)",\r
+ month = nov # " ~3--5",\r
+ publisher = "ACM Press",\r
+ address = "New York",\r
+ year = "2002",\r
+}\r
+\r
+@book{MethodForOptimizingArrayBoundsChecksInPrograms:2002,\r
+ title= {USPatent: Method for Optimizing Array Bounds Checks in Programs},\r
+ author= {Manish Gupta and Samuel Pratt Midkiff and Jose Eduardo Moreira},\r
+ publisher= {IBM Corporation},\r
+ year= {2002},\r
+ pages= {58}\r
+}\r
+\r
+@Article{ArrayBoundsCheckEliminationUtilizingAPageProtectionMechanism:2003,\r
+ title= {Array Bounds Check Elimination Utilizing a Page Protection Mechanism},\r
+ author= {Motohiro Kawahito},\r
+ publisher= {IBM Research, Tokyo Research Laboratory},\r
+ journal= {RT0550 Computer Science},\r
+ address= {1623-14, Shimotsuruma, Yamato, Kanagawa, 242-8502, Japan},\r
+ year= {2003},\r
+ pages= {6}\r
+}\r
+\r
+@Article{EfficientAndEffectiveArrayBoundChecking:2005,\r
+ author = "Thi Viet Nga Nguyen and Fran{\c{c}}ois Irigoin",\r
+ title = "Efficient and effective array bound checking",\r
+ journal = "ACM Transactions on Programming Languages and\r
+ Systems",\r
+ volume = "27",\r
+ number = "3",\r
+ pages = "527--570",\r
+ month = may,\r
+ year = "2005",\r
+ CODEN = "ATPSDT",\r
+ ISSN = "0164-0925",\r
+ bibdate = "Thu Jul 7 12:37:29 MDT 2005",\r
+ bibsource = "http://www.acm.org/pubs/contents/journals/toplas/",\r
+ acknowledgement = "Nelson H. F. Beebe, University of Utah, Department\r
+ of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake\r
+ City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1\r
+ 801 581 4148, e-mail: \path|beebe@math.utah.edu|,\r
+ \path|beebe@acm.org|, \path|beebe@computer.org|\r
+ (Internet), URL:\r
+ \path|http://www.math.utah.edu/~beebe/|",\r
+ fjournal = "ACM Transactions on Programming Languages and\r
+ Systems",\r
+}\r
+\r
+@Article{SymbolicBoundsAnalysisOfPointersArrayIndicesAndAccessedMemoryRegions:2005,\r
+ author = "Rugina and Rinard",\r
+ title = "Symbolic Bounds Analysis of Pointers, Array Indices,\r
+ and Accessed Memory Regions",\r
+ journal = "ACMTOPLAS: ACM Transactions on Programming Languages\r
+ and Systems",\r
+ volume = "27",\r
+ year = "2005",\r
+}\r
+\r
+@InProceedings{ArrayBoundsCheckEliminationForTheJavaHotSpotTMClientCompiler:2007,\r
+ title = "Array bounds check elimination for the Java\r
+ HotSpot{\texttrademark} client compiler",\r
+ author = "Thomas W{\"u}rthinger and Christian Wimmer and\r
+ Hanspeter M{\"o}ssenb{\"o}ck",\r
+ bibdate = "2007-10-22",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/pppj/pppj2007.html#WurthingerWM07",\r
+ booktitle = "PPPJ",\r
+ booktitle = "Proceedings of the 5th International Symposium on\r
+ Principles and Practice of Programming in Java, {PPPJ}\r
+ 2007, Lisboa, Portugal, September 5-7, 2007",\r
+ publisher = "ACM",\r
+ year = "2007",\r
+ volume = "272",\r
+ editor = "Vasco Amaral and Luis Marcelino and Lu{\'i}s Veiga and\r
+ H. Conrad Cunningham",\r
+ ISBN = "978-1-59593-672-1",\r
+ pages = "125--133",\r
+ series = "ACM International Conference Proceeding Series",\r
+ URL = "http://doi.acm.org/10.1145/1294325.1294343",\r
+}\r
+\r
+@Misc{VerifiableRangeAnalysisAnnotationsForArrayBoundsCheckElimination:2007,\r
+ author = {Jeffery Von Ronne and Kleanthis Psarris and David Niedzielski},\r
+ title = {Verifiable Range Analysis Annotations for Array Bounds Check Elimination},\r
+ year = {}\r
+}\r
+\r
+@InProceedings{APracticalAndPreciseInferenceAndSpecializerForArrayBoundChecksElimination:2008,\r
+ title = "A practical and precise inference and specializer for\r
+ array bound checks elimination",\r
+ author = "Corneliu Popeea and Dana N. Xu and Wei-Ngan Chin",\r
+ bibdate = "2008-04-04",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/pepm/pepm2008.html#PopeeaXC08",\r
+ booktitle = "PEPM",\r
+ booktitle = "Proceedings of the 2008 {ACM} {SIGPLAN} Symposium on\r
+ Partial Evaluation and Semantics-based Program\r
+ Manipulation, {PEPM} 2008, San Francisco, California,\r
+ {USA}, January 7-8, 2008",\r
+ publisher = "ACM",\r
+ year = "2008",\r
+ editor = "Robert Gl{\"u}ck and Oege de Moor",\r
+ ISBN = "978-1-59593-977-7",\r
+ pages = "177--187",\r
+ URL = "http://doi.acm.org/10.1145/1328408.1328434",\r
+}\r
+\r
+@Misc{EfficientIntraproceduralArrayBoundChecking:2008,\r
+ title = "Efficient Intraprocedural Array Bound Checking",\r
+ author = "Thi Viet and Nga Nguyenfranc and Ois Irigoin and Ronan\r
+ Keryelllit and Enst Bretagne",\r
+ year = "2008",\r
+ month = feb # "~07",\r
+ abstract = "Array bound checking is critical for code safety and\r
+ debugging but users are not ready to trade much\r
+ execution time for it. A considerable research work has\r
+ been carried out during the past 25 years but\r
+ experimental results are scarce. Commercial\r
+ implementations are limited to intraprocedural array\r
+ bound checking and are not really fulfilling user\r
+ expectations fot compilation and execution times.\r
+ Instead of designing a new specific algorithm, we\r
+ implemented two algorithms representative of the main\r
+ published approaches by re-using automatic\r
+ parallelization techniques available in PIPS, an\r
+ interprocedural parallelizer. The first algorithm is\r
+ based on redundant bound checking elimination. The\r
+ second one is based on insertion of unavoidable tests.\r
+ Results with the SPEC CFP95 benchmarks show that\r
+ commercial products could easily be improved using\r
+ automatic parallelization techniques and that user\r
+ expectations can be fulfilled for most benchmarks.\r
+ However, additional techniques would have be used to\r
+ obtain excellent results for all benchmarks. Our\r
+ approach to optimize bound checking can also be applied\r
+ to other imperative languages such as Fortran, Pascal,\r
+ Java when used for scientific applications.",\r
+ bibsource = "OAI-PMH server at citeseerx.ist.psu.edu",\r
+ contributor = "CiteSeerX",\r
+ language = "en",\r
+ oai = "oai:CiteSeerXPSU:10.1.1.80.9869",\r
+ relation = "10.1.1.19.5510; 10.1.1.36.3970; 10.1.1.33.6934;\r
+ 10.1.1.127.8252; 10.1.1.121.8818; 10.1.1.44.8796;\r
+ 10.1.1.53.9852; 10.1.1.141.4211; 10.1.1.85.5471;\r
+ 10.1.1.34.2234; 10.1.1.41.326; 10.1.1.18.3004;\r
+ 10.1.1.30.1142; 10.1.1.34.7836",\r
+ rights = "Metadata may be used without restrictions as long as\r
+ the oai identifier remains attached to it.",\r
+ subject = "array bound checking; range checking; subscript out of\r
+ range; bound violation; program verification",\r
+ URL = "http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.80.9869;\r
+ http://www.cri.ensmp.fr/classement/doc/A-316.ps",\r
+}\r
+\r
+@Article{SafeBoundsCheckAnnotations:2008,\r
+ title = "Safe bounds check annotations",\r
+ author = "Jeffery von Ronne and Andreas Gampe and David\r
+ Niedzielski and Kleanthis Psarris",\r
+ journal = "Concurrency and Computation: Practice and Experience",\r
+ year = "2009",\r
+ number = "1",\r
+ volume = "21",\r
+ bibdate = "2009-05-07",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/journals/concurrency/concurrency21.html#RonneGNP09",\r
+ pages = "41--57",\r
+ URL = "http://dx.doi.org/10.1002/cpe.1341",\r
+}\r
+\r
+@InProceedings{SpeculativeImprovementsToVerfifiableBoundsCheckElimination:2008,\r
+ title = "Speculative improvements to verifiable bounds check\r
+ elimination",\r
+ author = "Andreas Gampe and Jeffery von Ronne and David\r
+ Niedzielski and Kleanthis Psarris",\r
+ bibdate = "2008-09-23",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/pppj/pppj2008.html#GampeRNP08",\r
+ booktitle = "PPPJ",\r
+ booktitle = "Proceedings of the 6th International Symposium on\r
+ Principles and Practice of Programming in Java, {PPPJ}\r
+ 2008, Modena, Italy, September 9-11, 2008",\r
+ publisher = "ACM",\r
+ year = "2008",\r
+ volume = "347",\r
+ editor = "Lu{\'i}s Veiga and Vasco Amaral and R. Nigel Horspool\r
+ and Giacomo Cabri",\r
+ ISBN = "978-1-60558-223-8",\r
+ pages = "85--94",\r
+ series = "ACM International Conference Proceeding Series",\r
+ URL = "http://doi.acm.org/10.1145/1411732.1411745",\r
+}\r
+\r
+@InProceedings{ArrayBoundsCheckEliminationForJavaBasedOnSparseRepresentation:2009,\r
+ title = "Array Bounds Check Elimination for Java Based on\r
+ Sparse Representation",\r
+ author = "Keqiao Yang and Zeng Huang and Min Yang",\r
+ bibdate = "2010-04-23",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/sera/sera2009.html#YangHY09",\r
+ booktitle = "SERA",\r
+ booktitle = "Proceedings of the Seventh {ACIS} International\r
+ Conference on Software Engineering Research, Management\r
+ and Applications, {SERA} 2009, Haikou, China, 2-4\r
+ December 2009",\r
+ publisher = "IEEE Computer Society",\r
+ year = "2009",\r
+ editor = "Roger Y. Lee and Wencai Du and Haeng-Kon Kim and\r
+ Shaochun Xu",\r
+ ISBN = "978-0-7695-3903-4",\r
+ pages = "189--196",\r
+ URL = "http://doi.ieeecomputersociety.org/10.1109/SERA.2009.11",\r
+}\r
+\r
+@Article{ArrayBoundsCheckEliminationInTheContextOfDeoptimization:2009,\r
+ title = "Array bounds check elimination in the context of\r
+ deoptimization",\r
+ author = "Thomas W{\"u}rthinger and Christian Wimmer and\r
+ Hanspeter M{\"o}ssenb{\"o}ck",\r
+ journal = "Sci. Comput. Program",\r
+ year = "2009",\r
+ number = "5-6",\r
+ volume = "74",\r
+ bibdate = "2009-06-15",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/journals/scp/scp74.html#WurthingerWM09",\r
+ pages = "279--295",\r
+ URL = "http://dx.doi.org/10.1016/j.scico.2009.01.002",\r
+}\r
+\r
+@InProceedings{AVerifiableControlFlowAwareConstraintAnalyzerForBoundsCheckElimination:2009,\r
+ title = "A Verifiable, Control Flow Aware Constraint Analyzer\r
+ for Bounds Check Elimination",\r
+ author = "David Niedzielski and Jeffery von Ronne and Andreas\r
+ Gampe and Kleanthis Psarris",\r
+ bibdate = "2009-08-20",\r
+ bibsource = "DBLP,\r
+ http://dblp.uni-trier.de/db/conf/sas/sas2009.html#NiedzielskiRGP09",\r
+ booktitle = "SAS",\r
+ booktitle = "Static Analysis, 16th International Symposium, {SAS}\r
+ 2009, Los Angeles, {CA}, {USA}, August 9-11, 2009.\r
+ Proceedings",\r
+ publisher = "Springer",\r
+ year = "2009",\r
+ volume = "5673",\r
+ editor = "Jens Palsberg and Zhendong Su",\r
+ ISBN = "978-3-642-03236-3",\r
+ pages = "137--153",\r
+ series = "Lecture Notes in Computer Science",\r
+ URL = "http://dx.doi.org/10.1007/978-3-642-03237-0",\r
+}\r
+\r
+@Misc{SafeMultiphaseBondsCheckEliminationInJava:2010,\r
+ author = {Andreas Gampe and David Niedzielski and Jeffery Von Ronne and Kleanthis Psarris},\r
+ title = {Safe, Multiphase Bounds Check Elimination in Java},\r
+ year = {2010}\r
+}\r
+\r
+###############################################################################\r
+# Documents that cover important auxiliary information!\r
+###############################################################################\r
+\r
+@Article{AFastAlgorithmForFindingDominatorsInAFlowGraph:1979,\r
+ author = "Thomas Lengauer and Robert E. Tarjan",\r
+ title = "A Fast Algorithm for Finding Dominators in a Flow\r
+ Graph",\r
+ journal = "ACM Transactions on Programming Languages and\r
+ Systems",\r
+ volume = "1",\r
+ number = "1",\r
+ pages = "121--141",\r
+ month = jul,\r
+ year = "1979",\r
+ reffrom = "Touzeau:acm:cc:1984",\r
+}\r
+\r
+@Misc{ASImpleFastDominanceAlgorithm:2001,\r
+ title = "A Simple, Fast Dominance Algorithm",\r
+ author = "Keith D. Cooper and Timothy J. Harvey and Ken\r
+ Kennedy",\r
+ year = "2001",\r
+ month = aug # "~12",\r
+ abstract = "This paper returns to a simple formulation of\r
+ dominance as a global data-flow problem. Some insights\r
+ into the nature of dominance lead to an implementation\r
+ of an O(N ) algorithm that runs faster, in practice,\r
+ than the classic Lengauer-Tarjan algorithm, which has a\r
+ timebound of O(E log(N)).Wecompare the algorithm to\r
+ Lengauer-Tarjan because it is the best known and most\r
+ widely used of the fast algorithms for dominance.\r
+ Working from the same implementation insights, we also\r
+ rederive (from earlier work on control dependence by\r
+ Ferrante, et al.)amethod Contract/grant sponsor: This\r
+ research was supported, in part, by Darpa through\r
+ Usafrl contract F30602-97-2-298, and the State of Texas\r
+ through its Advanced Technology Program, grant number\r
+ 3604-0122-1999",\r
+ citeseer-references = "oai:CiteSeerPSU:472597; oai:CiteSeerPSU:87236;\r
+ oai:CiteSeerPSU:87236; oai:CiteSeerPSU:106151;\r
+ oai:CiteSeerPSU:54768",\r
+ annote = "Keith D. Cooper (Rice University; Houston , TX); Ken\r
+ Kennedy (SUMMARY);",\r
+ bibsource = "OAI-PMH server at cs1.ist.psu.edu",\r
+ language = "en",\r
+ oai = "oai:CiteSeerPSU:573270",\r
+ rights = "unrestricted",\r
+ URL = "http://citeseer.ist.psu.edu/573270.html;\r
+ http://www.cs.rice.edu/~keith/EMBED/dom.pdf",\r
+}\r
+\r
+\r
+\r
+###############################################################################\r
+# End\r
+###############################################################################\r
--- /dev/null
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
+% ------------------------------------------------------------------------\r
+% Grundlagen Wissenschaftlichen Arbeitens - LaTeX Style File\r
+% ------------------------------------------------------------------------\r
+% File name: gwa.sty\r
+% Author: Wilfried Elmenreich\r
+% Modifications: Raimund Kirner (13.03.2006)\r
+% Revision: 1.1\r
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
+\r
+%\r
+%----------------------------------------------------------------- ID ---\r
+%\r
+\r
+\NeedsTeXFormat{LaTeX2e} \ProvidesPackage{gwa}\r
+\r
+%\r
+%------------------------------------------------------------ Packages --\r
+%\r
+\r
+\RequirePackage{times}\r
+\RequirePackage{a4}\r
+\r
+%\r
+%--------------------------------------------------------- Page format --\r
+%\r
+\r
+\setlength{\topmargin}{-1.2cm}\r
+\setlength{\textwidth}{16.5cm}\r
+\setlength{\textheight}{23cm}\r
+\setlength{\oddsidemargin}{0.3cm}\r
+\setlength{\evensidemargin}{-0.6cm}\r
+\setlength{\parindent}{3.5mm}\r
+\setlength{\columnsep}{6mm}\r
+\setlength{\hoffset}{0cm}\r
+\r
+\def\kompakt{\setlength{\baselineskip}{.93\baselineskip}\setlength{\columnsep}{5.5mm}}\r
+\r
+\renewcommand{\floatpagefraction}{0.9}\r
+\renewcommand{\textfraction}{0.05}\r
+\renewcommand{\topfraction}{1.0}\r
+\renewcommand{\bottomfraction}{1.0}\r
+\r
+%\DeclareOption{latex}{\r
+%\setlength{\oddsidemargin}{1.1cm}\r
+%\setlength{\evensidemargin}{0.1cm}}\r
+%\r
+%\DeclareOption{pdflatex}{\r
+%\setlength{\oddsidemargin}{0.5cm}\r
+%\setlength{\evensidemargin}{-0.5cm}}\r
+\r
+%\ProcessOptions\r
+\r
+%\r
+%----------------------------------------- Caption and list formatting --\r
+%\r
+\r
+\def\section{\@startsection{section}{2}{0cm}{-1.5ex plus -.1ex minus\r
+ -.2ex}{1.5ex}{\large\sc}}\r
+\def\subsection{\@startsection{subsection}{2}{0cm}{-1.5ex plus -.1ex minus\r
+ -.2ex}{1.5ex}{\normalsize\sc}}\r
+ \def\subsubsection{\@startsection{subsubsection}{2}{0cm}{-1.5ex plus -.1ex minus\r
+ -.2ex}{1.5ex}{\normalsize\sc}}\r
+%\renewcommand \thesection {\@Roman\c@section}\r
+%\renewcommand\thesubsection {\@Alph\c@subsection}\r
+\r
+\renewcommand\labelitemi{\normalfont\bfseries --}\r
+\renewcommand\labelitemii{$\m@th\bullet$}\r
+\r
+%\r
+%----------------------------------------- Title and author formatting --\r
+%\r
+\r
+\def\affiliations#1{\gdef\@affiliations{#1}}\r
+\def\inst#1{\unskip$^{#1}$}\r
+\r
+\def\authN#1{{\large#1}}\r
+\def\matNr#1{{\normalsize\/Matr.Nr. #1}}\r
+\def\kennZ#1{{\normalsize\/Kennzahl #1}}\r
+\def\authI#1{{\normalsize#1}}\r
+\def\authU#1{{\normalsize#1}}\r
+\def\email#1{{\normalsize#1}}\r
+\r
+\makeatletter\r
+\r
+\makeatletter\r
+\r
+\def\@maketitle{%\r
+ \newpage\r
+ \null\r
+ \vskip 4em%\r
+ \begin{center}%\r
+ \let \footnote \thanks\r
+ {\vskip -6em \LARGE \@title \par}%\r
+ \vskip 1.5em%\r
+ {\large\r
+ \lineskip .5em%\r
+ \begin{tabular}[t]{c}%\r
+ \@author\r
+ \end{tabular}\par}%\r
+ \vskip 1em%\r
+ {\normalsize \@date}%\r
+ \end{center}%\r
+ \par\r
+ \vskip 1em\r
+}\r
+\r
+%\bibliographystyle{unsrt}\r
+\pagestyle{plain}\r
+\r
+%\r
+%---------------------------------------------------- Abstract command --\r
+%\r
+\r
+\newenvironment{absenv}{%\r
+ \list{}{\advance\topsep by0.35cm\r
+ \relax\small\r
+ \leftmargin=0cm\r
+ \labelwidth=\z@\r
+ \listparindent=0cm\r
+ \itemindent=0cm\r
+ \rightmargin\leftmargin\r
+ }\item[\hskip\labelsep\r
+ \bfseries Abstract] --- \em \setlength{\parskip}{0pt}}\r
+\r
+\renewcommand{\abstract}[1]{\r
+ \begin{absenv}\r
+ #1\r
+ \end{absenv}\r
+ \vskip 1.5em\r
+ \thispagestyle{plain}}\r
+\r
+%\r
+%---------------------------------------------------- Abstract command --\r
+%\r
+\r
+\renewenvironment{thebibliography}[1]\r
+ {\section*{\refname}%\r
+ \@mkboth{\MakeUppercase\refname}{\MakeUppercase\refname}%\r
+ \list{\@biblabel{\@arabic\c@enumiv}}%\r
+ {\settowidth\labelwidth{\@biblabel{#1}}%\r
+ \setlength{\parsep}{0em}\r
+ \setlength{\itemsep}{1pt}\r
+ \leftmargin\labelwidth\r
+ \advance\leftmargin\labelsep\r
+ \@openbib@code\r
+ \usecounter{enumiv}%\r
+ \let\p@enumiv\@empty\r
+ \renewcommand\theenumiv{\@arabic\c@enumiv}}%\r
+ \sloppy\r
+ \clubpenalty4000\r
+ \@clubpenalty \clubpenalty\r
+ \widowpenalty4000%\r
+ \sfcode`\.\@m}\r
+\r
+% = eof ==================================================================\r
--- /dev/null
+%%
+%% This is file `ngerman.sty',
+%% generated with the docstrip utility.
+%%
+%% The original source files were:
+%%
+%% german.dtx (with options: `new')
+%%
+%% This file is part of the `german' collection,
+%% providing German language support for
+%% plain TeX or LaTeX version 2e/2.09.
+%%
+%% ----------- Copyright (C) 1998, 1999 by B.Raichle ----------
+%% ------------------- All rights reserved. -------------------
+%% Maintained by Bernd Raichle (Uni Stuttgart),
+%% using ideas by H.Partl (TU Wien, Uni.f.Bodenkultur Wien)
+%% and many other people.
+%%
+%%
+%% IMPORTANT NOTICE:
+%%
+%% This program can be redistributed and/or modified under the terms
+%% of the LaTeX Project Public License Distributed from CTAN
+%% archives in directory macros/latex/base/lppl.txt; either
+%% version 1 of the License, or any later version.
+%%
+%%
+%% Error Reports (in case of UNCHANGED versions) should be sent to:
+%%
+%% Bernd Raichle <raichle@Informatik.Uni-Stuttgart.DE>
+%%
+\expandafter\ifx\csname ngrm\string @VersionNo\endcsname\relax
+\else
+ \ifnum\number\csname ngrm\string @VersionNo\endcsname<9806\relax
+ \else \ngermanTeX \expandafter\expandafter\expandafter\endinput
+ \fi\fi
+\expandafter\mathchardef\csname ngrm\string @VersionNo\endcsname
+=9806\relax % = v2.5e
+\message{v2.5e 1998-07-08}
+\begingroup\expandafter\expandafter\expandafter\endgroup
+\expandafter\ifx\csname ProvidesPackage\endcsname\relax\else
+ \ProvidesPackage{ngerman}[1998/07/08 v2.5e %
+ Support for writing german texts (br)]
+\fi
+\chardef\atcode=\catcode`\@
+\catcode`\@=11 % \makeatletter
+\expandafter\ifx\csname @ifundefined\endcsname\relax
+ \def\@ifundefined#1{%
+ \expandafter\ifx\csname #1\endcsname\relax
+ \expandafter\grmn@dqfirst\else\expandafter\grmn@dqsecond\fi}
+\fi
+\def\grmn@dqfirst#1#2{#1}
+\def\grmn@dqsecond#1#2{#2}
+\begingroup\expandafter\expandafter\expandafter\endgroup
+\expandafter\ifx\csname DeclareTextSymbol\endcsname\relax
+\@ifundefined{SS}{\def\SS{SS}}{}
+\else
+\begingroup\expandafter\expandafter\expandafter\endgroup
+\expandafter\ifx\csname ProvideTextCommandDefault\endcsname\relax
+ \immediate\write17{}
+ \immediate\write17{%
+!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!}
+ \immediate\write17{%
+!! Dies ist eine zu alte LaTeX2e-Version, die nicht}
+ \immediate\write17{%
+!! alle fuer german/ngerman notwendigen Deklarationen}
+ \immediate\write17{%
+!! zur Verfuegung stellt. Dennoch koennen Sie diese}
+ \immediate\write17{%
+!! Pakete, eventuell mit kleinen Fehlern, verwenden.}
+ \immediate\write17{!!}
+ \immediate\write17{%
+!! Bitte installieren Sie eine neuere LaTeX2e-Version,}
+ \immediate\write17{%
+!! da zukuenftige Versionen der Pakete diese}
+ \immediate\write17{%
+!! LaTeX2e-Version nicht mehr unterstuetzen werden!}
+ \immediate\write17{%
+!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!}
+ \immediate\write17{}
+\fi
+\@ifundefined{UseTextSymbol}{%
+ \def\UseTextSymbol#1#2{{\fontencoding{#1}\selectfont #2}}
+}{}
+\@ifundefined{UseTextAccent}{%
+ \def\UseTextAccent#1#2#3{%
+ {\let\@curr@enc\f@encoding
+ \fontencoding{#1}\selectfont
+ #2{\fontencoding\@curr@enc\selectfont #3}}}%
+}{}
+\@ifundefined{ProvideTextCommand}{%
+ \def\ProvideTextCommand#1#2{%
+ %%% misses \RobustTextCommand{#1}{...etc.etc...}!!
+ \expandafter\providecommand\csname #2\string#1\endcsname}%
+}{}
+\@ifundefined{ProvideTextCommandDefault}{%
+ \def\ProvideTextCommandDefault#1{%
+ \ProvideTextCommand{#1}{U}}%
+}{}
+\@ifundefined{DeclareTextCompositeCommand}{%
+ \def\DeclareTextCompositeCommand#1#2#3#4{%
+ % define a `dummy' text composite
+ \DeclareTextComposite{#1}{#2}{#3}{`\Z}%
+ % then redefine this command including the new command
+ \expandafter\def\csname\expandafter\string\csname
+ #2\endcsname\string#1-\string#3\endcsname##1##2{#4}}%
+}{}
+\@ifundefined{OT1\string\ss}{%
+ \wlog{ngerman: Re-declaration of \string\ss\space for OT1!}%
+ \DeclareTextSymbol{\ss}{OT1}{25}}{}
+\@ifundefined{OT1\string\i}{%
+ \wlog{ngerman: Re-declaration of \string\i\space for OT1!}%
+ \DeclareTextSymbol{\i}{OT1}{16}}{}
+\ProvideTextCommandDefault{\"}{\UseTextAccent{OT1}{\"}}
+\ProvideTextCommandDefault{\ss}{\UseTextSymbol{OT1}\ss}
+\ProvideTextCommandDefault{\i}{\UseTextSymbol{OT1}\i}
+\ProvideTextCommandDefault{\SS}{SS}
+\@ifundefined{textquotedblleft}{%
+ \ProvideTextCommandDefault{\textquotedblleft}{%
+ \UseTextSymbol{OT1}\textquotedblleft}%
+ \DeclareTextSymbol{\textquotedblleft}{OT1}{92}%
+ \DeclareTextSymbol{\textquotedblleft}{T1}{16}%
+}{}
+\@ifundefined{textquotedblright}{%
+ \ProvideTextCommandDefault{\textquotedblright}{%
+ \UseTextSymbol{OT1}\textquotedblright}%
+ \DeclareTextSymbol{\textquotedblright}{OT1}{`\"}%
+ \DeclareTextSymbol{\textquotedblright}{T1}{17}%
+ %% \DeclareTextSymbol{\textquotedbl}{T1}{`\"}%
+}{}
+\@ifundefined{textquoteleft}{%
+ \ProvideTextCommandDefault{\textquoteleft}{%
+ \UseTextSymbol{OT1}\textquoteleft}%
+ \DeclareTextSymbol{\textquoteleft}{OT1}{`\`}%
+ \DeclareTextSymbol{\textquoteleft}{T1}{`\`}%
+}{}
+\@ifundefined{textquoteright}{%
+ \ProvideTextCommandDefault{\textquoteright}{%
+ \UseTextSymbol{OT1}\textquoteright}%
+ \DeclareTextSymbol{\textquoteright}{OT1}{`\'}%
+ \DeclareTextSymbol{\textquoteright}{T1}{`\'}%
+}{}
+\@ifundefined{quotesinglbase}{%
+ \DeclareTextSymbol{\quotesinglbase}{T1}{13}}{}
+\@ifundefined{quotedblbase}{%
+ \DeclareTextSymbol{\quotedblbase}{T1}{18}}{}
+\@ifundefined{guillemotleft}{%
+ \DeclareTextSymbol{\guillemotleft}{T1}{19}}{}
+\@ifundefined{guillemotright}{%
+ \DeclareTextSymbol{\guillemotright}{T1}{20}}{}
+\@ifundefined{guilsinglleft}{%
+ \DeclareTextSymbol{\guilsinglleft}{T1}{14}}{}
+\@ifundefined{guilsinglright}{%
+ \DeclareTextSymbol{\guilsinglright}{T1}{15}}{}
+\fi
+\expandafter\let\expandafter\protect\csname protect\endcsname
+\def\allowhyphens{\penalty\@M \hskip\z@skip}
+\lccode`\^^Y=`\^^Y
+\def\set@low@box#1{\setbox\tw@\hbox{,}\setbox\z@\hbox{#1}%
+ \setbox\z@\hbox{\dimen@\ht\z@ \advance\dimen@ -\ht\tw@
+ \lower\dimen@\box\z@}%
+ \ht\z@\ht\tw@ \dp\z@\dp\tw@}
+\def\save@sf@q#1{{\ifhmode
+ \edef\@SF{\spacefactor\the\spacefactor}\else
+ \let\@SF\empty \fi \leavevmode #1\@SF}}
+\expandafter\ifx\csname grmnU@D\endcsname\relax
+ \csname newdimen\endcsname\grmnU@D
+\fi
+\def\newumlaut#1{{\grmnU@D 1ex%
+ {\setbox\z@\hbox{\char127}\dimen@-.45ex\advance\dimen@\ht\z@
+ \ifdim 1ex<\dimen@ \fontdimen5\font\dimen@ \fi}%
+ \accent127\fontdimen5\font\grmnU@D #1}\allowhyphens}
+\begingroup\expandafter\expandafter\expandafter\endgroup
+\expandafter\ifx\csname DeclareTextSymbol\endcsname\relax
+ \def\highumlaut#1{{\accent127 #1}\allowhyphens}
+\else
+ \def\highumlaut#1{\"{#1}\allowhyphens}
+\fi
+\def\mdqon{\catcode`\"\active}
+\def\mdqoff{\catcode`\"12\relax}
+\begingroup \mdqoff
+\def\x{\endgroup
+ \def\@MATHUMLAUT{\ddot}% = \mathaccent"707F
+ \def\@MATHss{\mathord{\mathchar"7019}}% TODO: correct?
+ \def\dq{"}}% TODO: or \textquotedbl?
+\x
+\begingroup
+ \def\do{\noexpand\do\noexpand}%
+ \edef\x{\endgroup
+ \def\noexpand\dospecials{\dospecials\do\"}}%
+\x
+\begingroup\expandafter\expandafter\expandafter\endgroup
+\expandafter\ifx\csname @sanitize\endcsname\relax \else
+ \begingroup
+ \def\@makeother{\noexpand\@makeother\noexpand}%
+ \edef\x{\endgroup
+ \def\noexpand\@sanitize{\@sanitize\@makeother\"}}%
+ \x
+\fi
+\let\grmn@original@three=\3 % \3 may be defined or undefined.
+\def\ck{%
+ \ifnum\grmn@dqwarninglevel>\@ne
+ \grmn@dq@warning@obsolete{\string\ck}{ck}%
+ \fi
+ \penalty\@M\-\allowhyphens ck}
+\begingroup\expandafter\expandafter\expandafter\endgroup
+\expandafter\ifx\csname DeclareTextSymbol\endcsname\relax
+\expandafter\def\csname glqq \endcsname{%
+ \save@sf@q{\set@low@box{''\/}\box\z@\kern-.04em\allowhyphens}}
+\edef\glqq{\noexpand\protect
+ \expandafter\noexpand\csname glqq \endcsname}
+\let\@glqq=\glqq
+\expandafter\def\csname grqq \endcsname{%
+ \save@sf@q{\kern-.07em``\kern.07em}}% ('')
+\edef\grqq{\noexpand\protect
+ \expandafter\noexpand\csname grqq \endcsname}
+\let\@grqq=\grqq
+\expandafter\def\csname glq \endcsname{%
+ \save@sf@q{\set@low@box{'\/}\box\z@\kern-.04em\allowhyphens}}
+\edef\glq{\noexpand\protect
+ \expandafter\noexpand\csname glq \endcsname}
+\let\@glq=\glq
+\expandafter\def\csname grq\endcsname{%
+ \save@sf@q{\kern-.0125em`\kern.07em}}
+\edef\grq{\noexpand\protect
+ \expandafter\noexpand\csname grq \endcsname}
+\let\@grq=\grq
+\expandafter\def\csname flqq \endcsname{%
+ \relax\ifmmode \mathrel{\ll}\else \save@sf@q{\penalty\@M
+ \raise .27ex\hbox{$\m@th\scriptscriptstyle \ll $}%
+ \allowhyphens}\fi}
+\edef\flqq{\noexpand\protect
+ \expandafter\noexpand\csname flqq \endcsname}
+\let\@flqq=\flqq
+\expandafter\def\csname frqq \endcsname{%
+ \relax\ifmmode \mathrel{\gg}\else \save@sf@q{\penalty\@M
+ \raise .27ex\hbox{$\m@th\scriptscriptstyle \gg $}%
+ \allowhyphens}\fi}
+\edef\frqq{\noexpand\protect
+ \expandafter\noexpand\csname frqq \endcsname}
+\let\@frqq=\frqq
+\expandafter\def\csname flq \endcsname{%
+ \relax\ifmmode <\else \save@sf@q{\penalty\@M
+ \raise .27ex\hbox{$\m@th\scriptscriptstyle <$}\allowhyphens}\fi}
+\edef\flq{\noexpand\protect
+ \expandafter\noexpand\csname flq \endcsname}
+\let\@flq=\flq
+\expandafter\def\csname frq \endcsname{%
+ \relax\ifmmode >\else \save@sf@q{\penalty\@M
+ \raise .27ex\hbox{$\m@th\scriptscriptstyle >$}\allowhyphens}\fi}
+\edef\frq{\noexpand\protect
+ \expandafter\noexpand\csname frq \endcsname}
+\let\@frq=\frq
+\else
+\DeclareRobustCommand{\glqq}{%
+ \ifmmode\hbox{\quotedblbase}\else\quotedblbase\fi}
+\ProvideTextCommandDefault{\quotedblbase}{%
+ \UseTextSymbol{OT1}\quotedblbase}
+\ProvideTextCommand{\quotedblbase}{OT1}{%
+ \save@sf@q{\set@low@box{\textquotedblright\/}\box\z@
+ \kern-.04em\allowhyphens}}
+\ProvideTextCommand{\grqq}{T1}{\textquotedblleft}
+\ProvideTextCommand{\grqq}{OT1}{%
+ \save@sf@q{\kern-.07em%
+ \ifmmode\hbox{\textquotedblleft}\else\textquotedblleft\fi
+ \kern.07em\relax}}
+\ProvideTextCommandDefault{\grqq}{\UseTextSymbol{OT1}\grqq}
+\DeclareRobustCommand{\glq}{%
+ \ifmmode\hbox{\quotesinglbase}\else\quotesinglbase\fi}
+\ProvideTextCommandDefault{\quotesinglbase}{%
+ \UseTextSymbol{OT1}\quotesinglbase}
+\ProvideTextCommand{\quotesinglbase}{OT1}{%
+ \save@sf@q{\set@low@box{\textquoteright\/}\box\z@
+ \kern-.04em\allowhyphens}}
+\ProvideTextCommand{\grq}{T1}{\textquoteleft}
+\ProvideTextCommand{\grq}{OT1}{%
+ \save@sf@q{\kern-.0125em%
+ \ifmmode\hbox{\textquoteleft}\else\textquoteleft\fi
+ \kern.07em\relax}}
+\ProvideTextCommandDefault{\grq}{\UseTextSymbol{OT1}\grq}
+\DeclareRobustCommand{\flqq}{%
+ \ifmmode\mathrel{\hbox{\guillemotleft}}\else\guillemotleft\fi}
+\ProvideTextCommandDefault{\guillemotleft}{%
+ \UseTextSymbol{OT1}\guillemotleft}
+\ProvideTextCommand{\guillemotleft}{OT1}{%
+ \ifmmode \ll \else \save@sf@q{\penalty\@M
+ \raise .27ex\hbox{$\m@th\scriptscriptstyle \ll $}%
+ \allowhyphens}\fi}
+\DeclareRobustCommand{\frqq}{%
+ \ifmmode\mathrel{\hbox{\guillemotright}}\else\guillemotright\fi}
+\ProvideTextCommandDefault{\guillemotright}{%
+ \UseTextSymbol{OT1}\guillemotright}
+\ProvideTextCommand{\guillemotright}{OT1}{%
+ \ifmmode \gg \else \save@sf@q{\penalty\@M
+ \raise .27ex\hbox{$\m@th\scriptscriptstyle \gg $}%
+ \allowhyphens}\fi}
+\DeclareRobustCommand{\flq}{%
+ \ifmmode\mathbin{\hbox{\guilsinglleft}}\else\guilsinglleft\fi}
+\ProvideTextCommandDefault{\guilsinglleft}{%
+ \UseTextSymbol{OT1}\guilsinglleft}
+\ProvideTextCommand{\guilsinglleft}{OT1}{%
+ \ifmmode <\else \save@sf@q{\penalty\@M
+ \raise .27ex\hbox{$\m@th\scriptscriptstyle <$}\allowhyphens}\fi}
+\DeclareRobustCommand{\frq}{%
+ \ifmmode\mathbin{\hbox{\guilsinglright}}\else\guilsinglright\fi}
+\ProvideTextCommandDefault{\guilsinglright}{%
+ \UseTextSymbol{OT1}\guilsinglright}
+\ProvideTextCommand{\guilsinglright}{OT1}{%
+ \ifmmode >\else \save@sf@q{\penalty\@M
+ \raise .27ex\hbox{$\m@th\scriptscriptstyle >$}\allowhyphens}\fi}
+\fi
+\begingroup\expandafter\expandafter\expandafter\endgroup
+\expandafter\ifx\csname DeclareTextSymbol\endcsname\relax
+\def\umlauthigh{\def\"##1{{\accent127 ##1}}}
+\def\umlautlow{\def\"{\protect\newumlaut}}
+\else
+\def\umlauthigh{\def\grmn@OTumlaut##1{{\accent 127 ##1}}}
+\def\umlautlow{\def\grmn@OTumlaut{\protect\newumlaut}}
+\umlauthigh
+\DeclareTextAccent{\"}{T1}{4}
+\DeclareTextAccent{\"}{OT1}{127}
+\DeclareTextCompositeCommand{\"}{OT1}{a}{\grmn@OTumlaut{a}}%
+\DeclareTextCompositeCommand{\"}{OT1}{o}{\grmn@OTumlaut{o}}%
+\DeclareTextCompositeCommand{\"}{OT1}{u}{\grmn@OTumlaut{u}}%
+\DeclareTextCompositeCommand{\"}{OT1}{A}{\grmn@OTumlaut{A}}%
+\DeclareTextCompositeCommand{\"}{OT1}{O}{\grmn@OTumlaut{O}}%
+\DeclareTextCompositeCommand{\"}{OT1}{U}{\grmn@OTumlaut{U}}%
+\DeclareTextComposite{\"}{T1}{a}{228}
+\begingroup\expandafter\expandafter\expandafter\endgroup
+\expandafter\ifx\csname AtBeginDocument\endcsname\relax \else
+ \AtBeginDocument{%
+ \DeclareTextAccent{\"}{T1}{4}% % from `ltpatch.tex'
+ \DeclareTextAccent{\"}{OT1}{127}% % from `ltpatch.tex'
+ % \DeclareTextCommand{\"}{OT1}{\newumlaut}% from `ltpatch.tex'
+ % % has to be removed
+ \DeclareTextCompositeCommand{\"}{OT1}{a}{\grmn@OTumlaut{a}}%
+ \DeclareTextCompositeCommand{\"}{OT1}{o}{\grmn@OTumlaut{o}}%
+ \DeclareTextCompositeCommand{\"}{OT1}{u}{\grmn@OTumlaut{u}}%
+ \DeclareTextCompositeCommand{\"}{OT1}{A}{\grmn@OTumlaut{A}}%
+ \DeclareTextCompositeCommand{\"}{OT1}{O}{\grmn@OTumlaut{O}}%
+ \DeclareTextCompositeCommand{\"}{OT1}{U}{\grmn@OTumlaut{U}}%
+ \DeclareTextComposite{\"}{T1}{a}{228}% % from `ltpatch.tex'
+ }
+\fi
+\fi
+\def\dqwarninglevel#1{\chardef\grmn@dqwarninglevel=#1\relax}
+ \dqwarninglevel{2}
+\expandafter\ifx\csname on@line\endcsname\relax
+ \ifx\inputlineno\undefined \def\on@line{}%
+ \else
+ \ifnum\inputlineno<\z@ \def\on@line{}%
+ \else \def\on@line{ on input line \the\inputlineno}%
+\fi\fi\fi
+\def\grmn@dq@error#1{%
+ \errhelp{Use `` for a simple double quote character.}%
+ \errmessage{ngerman: The command \dq\string#1 is undefined}}
+\def\grmn@dq@warning#1{%
+ \immediate\write\sixt@@n
+ {ngerman: \dq\string#1 is possibly wrong\on@line.}}
+\def\grmn@dq@warning@obsolete#1#2{%
+ \immediate\write\sixt@@n
+ {ngerman: #1 is now obsolete, please use #2 instead\on@line.}}
+\def\grmn@dqobsolete@three#1{#1#1%
+ \ifnum\grmn@dqwarninglevel>\@ne
+ \grmn@dq@warning@obsolete{\dq#1#1}{#1#1#1}%
+ \fi
+ \penalty\@M\-\allowhyphens}
+\def\grmn@dqobsolete@ck#1#2{%
+ \ifnum\grmn@dqwarninglevel>\@ne
+ \grmn@dq@warning@obsolete{\dq#1#2}{#1#2}%
+ \fi
+ \penalty\@M\-\allowhyphens#1}
+\def\grmn@dq@macro#1#2{%
+ \expandafter#1\csname @grmn@@\string #2dq\endcsname}
+\def\def@dqmacro#1#2#3{%
+ \grmn@dqredefcheck{#1}%
+ \grmn@dq@macro\def{#1}{{#2}{#3}}}
+\def\let@dqmacro#1#2{\begingroup
+ \grmn@dqredefcheck{#1}%
+ \edef\x{\endgroup \let
+ \grmn@dq@macro\noexpand{#1}\grmn@dq@macro\noexpand{#2}}%
+ \x}
+\def\grmn@dqredefcheck#1{}
+\def\@active@dq#1{%
+ \grmn@dq@macro\ifx{#1}\relax
+ \ifnum\grmn@dqwarninglevel>\z@ \grmn@dq@error{#1}\fi
+ \expandafter\grmn@@normal@dq
+ \else
+ \expandafter\grmn@@active@dq
+ \fi {#1}}
+\def\grmn@@active@dq#1{%
+ \grmn@dq@macro\ifx{#1}\noexpand
+ \expandafter\grmn@normal@dq
+ \else
+ \expandafter\grmn@@@active@dq
+ \fi {#1}}
+\def\grmn@@normal@dq#1{``#1}
+\def\grmn@normal@dq#1{\dq #1}
+\begingroup
+ \catcode`\(=1\lccode`\(=`\{\catcode`\{=12
+ \catcode`\)=2\lccode`\)=`\}\catcode`\}=12
+ \catcode`\ =11\relax% <= do not delete this and the
+\lowercase(\endgroup% <=== following percent characters!
+\def\grmn@@@active@dq#1(%
+\expandafter\grmn@@@@active@dq\expandafter{\string#1})%
+\def\grmn@@@@active@dq(%
+\ifx\protect\relax\else\ifx\protect\empty\else%
+\expandafter\expandafter\expandafter\protect%
+\fi\fi%
+\active@dq \dq@prtct )%
+\def\dq@prtct#1#(\@dq@prtct)%
+\def\@dq@prtct#1(\string\dq@prtct{\string#1})%
+\def\dq@prtct #1{#2}(\string\dq@prtct{\string#2})%
+\def\active@dq #1{#2}(\grmn@active@@dq(#2))%
+)%
+\def\active@dq#1#{\@active@dq}%
+\def\grmn@active@@dq#1{%
+ \csname grmn@dq\ifmmode second\else first\fi
+ \expandafter\expandafter\expandafter\expandafter
+ \grmn@dq@macro\endcsname{#1}}
+\grmn@dq@macro\let{0}=\noexpand
+\let@dqmacro{1}{0}\let@dqmacro{2}{0}\let@dqmacro{3}{0}
+\let@dqmacro{4}{0}\let@dqmacro{5}{0}\let@dqmacro{6}{0}
+\let@dqmacro{7}{0}\let@dqmacro{8}{0}\let@dqmacro{9}{0}
+\let@dqmacro{A}{0}\let@dqmacro{B}{0}\let@dqmacro{C}{0}
+\let@dqmacro{D}{0}\let@dqmacro{E}{0}\let@dqmacro{F}{0}
+\def@dqmacro{}{\dq{}}{\dq{}}
+\def@dqmacro{a}{\"a}{\@MATHUMLAUT a}
+\def@dqmacro{o}{\"o}{\@MATHUMLAUT o}
+\def@dqmacro{u}{\"u}{\@MATHUMLAUT u}
+\def@dqmacro{A}{\"A}{\@MATHUMLAUT A}
+\def@dqmacro{O}{\"O}{\@MATHUMLAUT O}
+\def@dqmacro{U}{\"U}{\@MATHUMLAUT U}
+\begingroup\expandafter\expandafter\expandafter\endgroup
+\expandafter\ifx\csname DeclareTextSymbol\endcsname\relax
+ \def@dqmacro{s}{\ss{}}{\@MATHss}
+\else
+ \def@dqmacro{s}{\ss}{\@MATHss}
+\fi
+\def@dqmacro{S}{\SS}{\SS}
+\let@dqmacro{z}{s}
+\def@dqmacro{Z}{SZ}{SZ}
+\def@dqmacro{e}{\highumlaut e}{\@MATHUMLAUT e}
+\def@dqmacro{E}{\highumlaut E}{\@MATHUMLAUT E}
+\def@dqmacro{i}{\highumlaut{\i}}{\@MATHUMLAUT\imath}
+\def@dqmacro{I}{\highumlaut I}{\@MATHUMLAUT I}
+\def@dqmacro{`}{\glqq}{\glqq}
+\def@dqmacro{'}{\grqq}{\grqq}
+\def@dqmacro{<}{\flqq}{\flqq}
+\def@dqmacro{>}{\frqq}{\frqq}
+\def@dqmacro{-}{\penalty\@M\-\allowhyphens}%
+ {\penalty\@M\-\allowhyphens}
+\def@dqmacro{|}{\penalty\@M\discretionary{-}{}{\kern.03em}%
+ \allowhyphens}{}
+\def@dqmacro{"}{\hskip\z@skip}{\hskip\z@skip}
+\def@dqmacro{~}{\leavevmode\hbox{-}}{-}
+\def@dqmacro{=}{\penalty\@M-\hskip\z@skip}%
+ {\penalty\@M-\hskip\z@skip}
+\def@dqmacro{c}{\grmn@dqobsolete@ck ck}{c}
+\def@dqmacro{C}{\grmn@dqobsolete@ck CK}{C}
+\def@dqmacro{l}{\grmn@dqobsolete@three l}{l}
+\def@dqmacro{L}{\grmn@dqobsolete@three L}{L}
+\def@dqmacro{m}{\grmn@dqobsolete@three m}{m}
+\def@dqmacro{M}{\grmn@dqobsolete@three M}{M}
+\def@dqmacro{n}{\grmn@dqobsolete@three n}{n}
+\def@dqmacro{N}{\grmn@dqobsolete@three N}{N}
+\def@dqmacro{p}{\grmn@dqobsolete@three p}{p}
+\def@dqmacro{P}{\grmn@dqobsolete@three P}{P}
+\def@dqmacro{r}{\grmn@dqobsolete@three r}{r}
+\def@dqmacro{R}{\grmn@dqobsolete@three R}{R}
+\def@dqmacro{t}{\grmn@dqobsolete@three t}{t}
+\def@dqmacro{T}{\grmn@dqobsolete@three T}{T}
+\def@dqmacro{F}{\grmn@dqobsolete@three F}{F}
+\def@dqmacro{f}{\grmn@dqobsolete@three f}{f}
+\def\grmn@dqredefcheck#1{%
+ \wlog{ngerman: \grmn@dq@macro\ifx{#1}\relax \else re\fi
+ defining dq-command for `\string#1'\on@line.}}%
+\def\month@ngerman{\ifcase\month \or
+ Januar\or Februar\or M\"arz\or April\or Mai\or Juni\or
+ Juli\or August\or September\or Oktober\or November\or Dezember\fi}
+\def\datengerman{\def\today{\number\day.~\month@ngerman
+ \space\number\year}}
+\def\datenaustrian{\def\today{\number\day.~\ifnum 1=\month
+ J\"anner\else \month@ngerman\fi \space\number\year}}
+\def\month@english{\ifcase\month \or
+ January\or February\or March\or April\or May\or June\or
+ July\or August\or September\or October\or November\or December\fi}
+\def\dateUSenglish{\def\today{\month@english
+ \space\number\day, \number\year}}
+\def\dateenglish{\def\today{\number\day \ifcase\day \or
+ st\or nd\or rd\or th\or th\or th\or th\or th\or th\or th\or% 1..10
+ th\or th\or th\or th\or th\or th\or th\or th\or th\or th\or% 11..20
+ st\or nd\or rd\or th\or th\or th\or th\or th\or th\or th\or% 21..30
+ st\fi
+ ~\month@english \space\number\year}}
+\def\datefrench{\def\today{\number\day \ifnum1=\day \/$^{\rm er}$\fi
+ \space\ifcase\month \or
+ janvier\or f\'evrier\or mars\or avril\or mai\or juin\or
+ juillet\or ao\^ut\or septembre\or
+ octobre\or novembre\or d\'ecembre\fi
+ \space\number\year}}
+\def\captionsngerman{%
+ \def\prefacename{Vorwort}%
+ \def\refname{Literatur}%
+ \def\abstractname{Zusammenfassung}%
+ \def\bibname{Literaturverzeichnis}%
+ \def\chaptername{Kapitel}%
+ \def\appendixname{Anhang}%
+ \def\contentsname{Inhaltsverzeichnis}% % oder nur: Inhalt
+ \def\listfigurename{Abbildungsverzeichnis}%
+ \def\listtablename{Tabellenverzeichnis}%
+ \def\indexname{Index}%
+ \def\figurename{Abbildung}%
+ \def\tablename{Tabelle}% % oder: Tafel
+ \def\partname{Teil}%
+ \def\enclname{Anlage(n)}% % oder: Beilage(n)
+ \def\ccname{Verteiler}% % oder: Kopien an
+ \def\headtoname{An}%
+ \def\pagename{Seite}%
+ \def\seename{siehe}%
+ \def\alsoname{siehe auch}}
+\let\captionsnaustrian=\captionsngerman
+\def\captionsenglish{%
+ \def\prefacename{Preface}%
+ \def\refname{References}%
+ \def\abstractname{Abstract}%
+ \def\bibname{Bibliography}%
+ \def\chaptername{Chapter}%
+ \def\appendixname{Appendix}%
+ \def\contentsname{Contents}%
+ \def\listfigurename{List of Figures}%
+ \def\listtablename{List of Tables}%
+ \def\indexname{Index}%
+ \def\figurename{Figure}%
+ \def\tablename{Table}%
+ \def\partname{Part}%
+ \def\enclname{encl}%
+ \def\ccname{cc}%
+ \def\headtoname{To}%
+ \def\pagename{Page}%
+ \def\seename{see}%
+ \def\alsoname{see also}}
+\let\captionsUSenglish=\captionsenglish
+\def\captionsfrench{%
+ \def\prefacename{Pr\'eface}%
+ \def\refname{R\'ef\'erences}%
+ \def\abstractname{R\'esum\'e}%
+ \def\bibname{Bibliographie}%
+ \def\chaptername{Chapitre}%
+ \def\appendixname{Annexe}%
+ \def\contentsname{Table des mati\`eres}%
+ \def\listfigurename{Liste des figures}%
+ \def\listtablename{Liste des tableaux}%
+ \def\indexname{Index}%
+ \def\figurename{Figure}%
+ \def\tablename{Tableau}%
+ \def\partname{Partie}%
+ \def\enclname{P.~J.}%
+ \def\ccname{Copie \`a}%
+ \def\headtoname{A}%
+ \def\pagename{Page}%
+ \def\seename{voir}%
+ \def\alsoname{voir aussi}}%
+\def\extrasUSenglish{}
+\let\noextrasUSenglish=\extrasUSenglish
+\let\extrasenglish=\extrasUSenglish
+\let\noextrasenglish=\extrasenglish
+\def\extrasngerman{\frenchspacing \uchyph\@ne
+ \lefthyphenmin\tw@ \righthyphenmin\tw@}
+\def\noextrasngerman{%
+ \ifnum\sfcode`\.=\@m \else \noexpand\nonfrenchspacing \fi
+ \uchyph\the\uchyph\relax
+ \lefthyphenmin\the\lefthyphenmin
+ \righthyphenmin\the\righthyphenmin}
+\let\extrasnaustrian=\extrasngerman
+\let\noextrasnaustrian=\noextrasngerman
+\def\extrasfrench{\frenchspacing}
+\def\noextrasfrench{%
+ \ifnum\sfcode`\.=\@m \else \noexpand\nonfrenchspacing \fi}
+\@ifundefined{l@USenglish}{%
+ \@ifundefined{l@english}{\chardef\l@USenglish=255 }%
+ {\chardef\l@USenglish=\l@english}%
+ \wlog{ngerman -- \string\language\space number for USenglish %
+ undefined, default \number\l@USenglish\space used.}%
+}{}
+\@ifundefined{l@english}{%
+ \chardef\l@english=\l@USenglish
+ \wlog{ngerman -- \string\language\space number for UKenglish %
+ undefined, default \number\l@english\space used.}%
+}{}
+\@ifundefined{l@ngerman}{%
+ \@ifundefined{l@naustrian}{%
+ \chardef\l@ngerman=255 %
+ \message{ngerman -- \string\language\space number for ngerman %
+ undefined, default \number\l@ngerman\space used,}%
+ \message{ngerman -- Please read \string"gerdoc.tex\string" how %
+ to install hyphenation patterns.}%
+ }{%
+ \chardef\l@ngerman=\l@naustrian
+ \wlog{ngerman -- \string\language\space number for ngerman %
+ undefined, default \number\l@ngerman\space used.}%
+ }%
+}{}
+\@ifundefined{l@naustrian}{%
+ \chardef\l@naustrian=\l@ngerman
+ \wlog{ngerman -- \string\language\space number for naustrian %
+ undefined, default \number\l@naustrian\space used.}%
+}{}
+\@ifundefined{l@french}{%
+ \chardef\l@french=255
+ \wlog{ngerman -- \string\language\space number for French %
+ undefined, default \number\l@french\space used.}%
+}{}
+\def\grmn@originalTeX{}
+\def\languagename{}
+\expandafter\def\csname selectlanguage \endcsname#1{\relax
+ \expandafter\ifx\csname l@#1\endcsname\relax
+ \errhelp{Your command will be ignored, type <return> to proceed}%
+ \errmessage{You haven't defined the language #1 yet}%
+ \else
+ \grmn@originalTeX
+ \edef\languagename{#1}%
+ \edef\grmn@originalTeX{\csname noextras#1\endcsname
+ \def\noexpand\grmn@originalTeX{}}%
+ \csname date#1\endcsname
+ \csname captions#1\endcsname
+ \csname extras#1\endcsname\relax
+ % Diese Zeile ist fuer `bibgerm' ...
+ \csname bibs#1\endcsname
+ % ... sie wird in spaeteren `german.sty'-Versionen nicht
+ % mehr vorhanden sein. Also nicht darauf verlassen!
+ \language \csname l@#1\endcsname\relax
+ \fi}
+\begingroup\catcode`\ =11\relax% <= do not delete this and the
+\toks0={\endgroup% <=== following percent characters!
+\def\selectlanguage#1{\protect\selectlanguage {%
+\ifnum\escapechar=\expandafter`\string#1\empty%
+\else\string#1\empty\fi}}}%
+\the\toks0\relax%
+\def\p@selectlanguage{\selectlanguage}
+\def\iflanguage#1{%
+ \ifx\csname l@#1\endcsname\relax
+ \expandafter\grmn@dqsecond
+ \else \ifnum\csname l@#1\endcsname=\language
+ \expandafter\expandafter\expandafter\grmn@dqfirst
+ \else
+ \expandafter\expandafter\expandafter\grmn@dqsecond
+ \fi\fi
+}
+\expandafter\ifx\csname language\endcsname\relax
+ \csname newcount\endcsname\language
+ \language=0 \fi
+\expandafter\ifx\csname lefthyphenmin\endcsname\relax
+ \csname newcount\endcsname\lefthyphenmin
+ \lefthyphenmin=2 \fi
+\expandafter\ifx\csname righthyphenmin\endcsname\relax
+ \csname newcount\endcsname\righthyphenmin
+ \righthyphenmin=3 \fi
+\expandafter\ifx\csname setlanguage\endcsname\relax
+ \def\setlanguage{\relax
+ \ifhmode \else
+ \errhelp{Use \selectlanguage to switch languages.}%
+ \errmessage{\setlanguage allowed only in horizontal mode}%
+ \fi
+ \begingroup\afterassignment\endgroup\count@=}
+\fi
+\begingroup \mdqon
+\def\x{\endgroup
+ \def\originalTeX{\mdqoff \let"\dq \umlauthigh
+ \let\3\grmn@original@three
+ \selectlanguage{USenglish}}%
+ \def\ngermanTeX{\mdqon \let"\@active@dq \umlautlow
+ \let\grmn@original@three\3\let\3\ss
+ \selectlanguage{ngerman}}}%
+\x
+\catcode`\@=\atcode % return to previous catcode
+\ngermanTeX
+\endinput
+%%
+%% End of file `ngerman.sty'.
projects / cacao.git / commitdiff