\usepackage{gwa}\r
\usepackage{graphicx}\r
\usepackage{url}\r
-\usepackage{ngerman}\r
+%\usepackage{ngerman}\r
\usepackage[latin1]{inputenc}\r
\usepackage{textcomp}\r
\usepackage{multicol}\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
+ Before designing new optimization 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
+ be integrated automatically without developers knowledge or should\r
ABCs only be integrated selectively by programmers or quality assurance.\r
\r
\subsubsection{Compare Instruction Strategy}\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
+ really worthwhile 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
+ processor systems that didn't really consider 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
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
+ applications. For example Java is mainly used due to its 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
mentions some libraries and also explain some new special data structures\r
that follow this approach.\r
\r
- \subsubsection{Necessarity for ABC Optimization}\r
+ \subsubsection{Necessity 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
+ be the architect's and implementor's 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
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
+ On the other side Java declares its 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
\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
+ interesting source for the beginning because it focuses 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
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
+ and in the past several forms based on Static Single Assignment (SSA) were\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
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
+ inferred 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
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
+ But not only the array access instructions themselves 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
+ three deal with the code structure where these ABCs occur. 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
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
+ reductions 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
\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
+ 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
+ In the author's 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
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
+ also necessary for more elaborate 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
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
+ constraints to the eSSA instructions and builds 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
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
+ analyze but can in some circumstances really allow good optimizations. \par\r
\r
Gurd and Freeman et al. presented a further paper \r
\cite{EliminationOfJavaArrayBoundsChecksInThePresenceOfIndirection:2002} that\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
+ \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
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
+ whole problem. The first idea is based on Gupta's 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
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
+ explanation about this is widely out of this document's scope. \par\r
\r
In 2007 two new directions were started that are explained more precisely in the\r
next chapter. \par\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
+ array accessing and can lead to deoptimization (OSR at safepoint back to stack)\r
+ if the new conditions can't prove the previous 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
+ embedded in the VM and very effective going 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
\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
+ The work on the Cacao Java VM was started in 1996 by Reinhard 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
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
+ This further constrains 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
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
+ 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
\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
+ calculating the dominators 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
+ After this happened 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
\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
+ contained. So this means that a basic block is guaranteed to\r
be executed in one exact sequence.\r
\r
\end{description}\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
+ // force index variable to be on left side\r
+ ForceRightSideToBeConstant (ld, lc)\r
+ obtainDynamicConstraints (ld, lc)\r
}\r
}\r
\r
\r
%% Codesection end -------------------------------------------------------------\r
\r
- Postconditions are that the methods jitdata structure holds correct, executable\r
+ Postconditions are that the method's 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
\end{center}\r
\end{table}\r
\r
- From this data with polynomic behavior a fixed per centage of speed acceleration should\r
+ From this data with polynomic behavior a fixed percentage 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
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
+ part of the ABC optimization algorithm includes the necessity 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
\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
+ that normally 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
projects / cacao.git / commitdiff