\chapter{The Java Virtual Machine } Note: Thomas Fifield, a student in ECS 50 a few years ago, wrote portions of Section \ref{yet} (excluding the source code for {\bf NumNode.java}), and added the corresponding new instructions to Section \ref{ref}. \section{Background Needed} In what follows, it is assumed that the reader has at least a rudimentary knowledge of Java. See the author's Java tutorial at \url{http://heather.cs.ucdavis.edu/~matloff/java.html} for a 30-minute introduction to the Java language. But really, for our purposes, anyone who understands C++ should have no trouble following the Java code here. \section{Goal} Keep in mind that our goal here is to study the Java (virtual) {\it machine}, not the Java language. We wish to see how the machine works, and---this is very important---see why its developers chose to design certain features of the machine the way they did. \section{Why Is It a ``Virtual'' Machine?} You may have heard about the \textbf{Java virtual machine} (JVM), associated with the Java language. What is really going on here? The name of any Java source file has a {\bf .java} suffix, just like C source file names end in {\bf .c}. Suppose for example our Java program source code is all in one file, {\bf x.java}, and that for instance we are doing our work on a PC running Linux. We first compile, using the Java compiler, \textbf{javac}: \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] % javac -g x.java \end{Verbatim} (The {\bf -g} option saves the symbol table for use by a debugger.) This produces the executable Java file, {\bf x.class}, which contains machine language, called \textbf{byte code}, to run on a {}``Java machine.{}'' But we don't have such a machine. Instead, we have a program that \underbar{emulates} the operation of such a machine. This, of course, is the reason for the `V' in {}``JVM.{}'' The emulator (\textbf{interpreter}) program is named \textbf{java} . Note that in our case here, \textbf{java} will be a program running the Intel machine language of our PC.\footnote{And, for that matter, \textbf{javac} would be an Intel machine-language program too. } We then run our program: \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] % java x \end{Verbatim} Note that Java not only runs on a virtual machine, it also is in some sense running under a virtual operating system. For example, the analog of C's \textbf{printf()} function in Java is \textbf{System.out.println()}. Recall that (if our real machine is running UNIX) a \textbf{printf()} call in a C program calls the \textbf{write()} function in the OS. But this does not happen in the Java case; our OS is running on our real machine, but our Java program is running on the JVM. What actually happens is that {\bf System.out.println()} makes a call to what amounts to an OS in the JVM, and the latter calls \textbf{write()} on the real machine. By the way, JVM chips---i.e. chips that run Java byte code---do exist, but they are not in common use. Also, note that newer versions of GCC include GCJ, which will compile Java to machine code for your machine, e.g. Intel machine language if you are on a PC. This is really nice, as it produces faster-running programs, and it is far more common than Java chips, but still, the vast majority of Java code is executed on emulators. \section{The JVM Architecture} The JVM is basically a stack-based machine, with a 32-bit word size, using 2s complement arithmetic. The term {\it stack-based machine} means that almost all operands are on the stack, and they are implicit to the instruction. For example, contrast the Intel instruction \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] addl %eax, %ebx \end{Verbatim} to the JVM instruction \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] iadd \end{Verbatim} In the Intel case, the programmer has a choice of which two things to add together, and explicitly states them. In the JVM case, the programmer has no choice; the two operands \underline{must} be the top two elements of the stack. And since those operands must be the top two elements of the stack, there is no need to specify them in the instruction, so the instruction consists only of an op code, no explicit operands.\footnote{Historical note: A number of famous machines popular in the past, such as the Burroughs mainframe and HP 3000 minicomputer series, were stack-based.} Before continuing, it's vital that we discuss what the term ``the'' stack means above. Unlike the case of C/C++/assembly language, where there is a stack for each {\it process}, here we will have a stack for each {\it method call}.\footnote{Recall that in Java, we use the term {\it method} instead of {\it function}.} So, the term ``the stack'' in the material here must always be thought of as meaning ``the stack for whatever method is currently running.'' This is referred to as the {\bf operand stack}. On the other hand, there {\it is} something analogous to the stack you have worked with before in C/C++/assembly language. Recall that in that situation, all the function calls use a common stack, and all the data for a given function call---its arguments, return value and local variables---comprise the {\bf stack frame} for that function call. Java has this too. There is a stack frame for each method call, and they are placed in the overall stack in the same last-in, first-out fashion that use saw for function calls in C/C++/assembly language. Each stack frame in Java will in turn consist of the operand stack for that method call, a section for arguments and local variables, and some other data. \subsection{Registers} The JVM register set\footnote{Remember, in the case of a real Java chip, these would be real registers, but in the JVM setting, these registers, as well as the instruction set, are simulated by the \textbf{java} program.} is fairly small: \begin{itemize} \item \textbf{pc}: program counter \item \textbf{optop}: pointer to the top of the operand stack for the currently-active method \item \textbf{frame}: pointer to the stack frame of the currently-active method \item \textbf{vars}: pointer to the beginning of the local variables of the currently-active method \end{itemize} \subsection{Memory Areas} \begin{itemize} \item the (general) Stack: A method call produces a new stack frame, which is pushed onto the Stack for that program,\footnote{More precisely, for that thread, since many Java programs are threaded.} and a return pops the frame from the program's Stack. A stack frame is subdivided into the following. \begin{itemize} \item a Local Variables section: All the local variables and arguments for the method are stored here, one per {\bf slot} (i.e. one variable per word), with the arguments stored first and then the locals. The arguments and locals are stored in order of their declaration. In the case in which the method is an instance method,\footnote{In general object-oriented programming terminology, a function is called an {\bf instance} function if it applies specifically to an instance of a class. In C++ and Java, this is signified by not being declared {\bf static}. The alternate form is {\bf class} methods, which apply to all objects of that class, and is signified in C++/Java by being declared {\bf static}.} slot 0 will contain a pointer to the object on which this method is operating, i.e. the object referred to as {\bf this} in the program's source code. \item an Operand Stack section: This is the area on which the method's instructions operate. As noted, almost all JVM instructions are stack-based; e.g. an ``add'' instruction pops the top two elements of the stack, adds them, and pushes the sum back onto the stack. So the operand stack portion of a method's stack frame is what we are referring to when we refer to an instruction as operating on ``the'' stack. \item a Frame Data section: We will not go into the details of this, but for example the Frame Data section of a called method's stack frame will include a pointer to the caller's stack frame. This enables return to the caller when the called method finishes, and enables the latter to put the return value, if any, into the caller's stack frame. \end{itemize} \item the Method Area: The classes used by the executing program are stored here. This includes: \begin{itemize} \item the bytecode and access types of the methods of the class (similar to the {\bf .text} segment of a UNIX program, except for the access types) \item the {\bf static} variables of the class (their values and access types, i.e {\bf public}, {\bf private} etc.) \end{itemize} The {\bf pc} register points to the location within the Method Area of the JVM instruction to be executed next. The Method Area also includes the Constant Pool. It contains the string and numeric literals used by the program, e.g. the 1.2 in \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] float W = 1.2; \end{Verbatim} and also contains information on where each method is stored in the Method Area, as well as the static variables for the various classes. \item the Heap: This is where Java objects exist. Whenever the Java {\bf new} operation is invoked to create an object, the necessary memory for the object is allocated within the heap.\footnote{Just as in C, where a call to {\bf malloc()} results in memory space being allocated from the heap, and just as in C++, where a call to {\bf new} results in space being taken from the heap.} This space will hold the instance variables for the object, and a pointer to the location of the object's class in the Method Area. \end{itemize} \section{First Example} Consider the following source code, {\bf Minimum.java}: \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] public class Minimum { public static void main(String[] CLArgs) { int X,Y,Z; X = Integer.parseInt(CLArgs[0]); Y = Integer.parseInt(CLArgs[1]); Z = Min(X,Y); System.out.println(Z); } public static int Min(int U, int V) { int T; if (U < V) T = U; else T = V; return T; } } \end{Verbatim} \subsection{Java Considerations} In Java, there are no global quantities of any kind. That not only means no global variables, but also no free-standing, functions---every function must be part of some class.\footnote{Java threads from the same class will share the variables of that class.} So for example we see here that even {\bf main()} is part of a class, the class {\bf Minimum}. (That class in turn must be named after the name of the source file, {\bf Minimum.java}.) The argument for {\bf main()}, {\bf CLArgs}, is the set of command-line arguments, i.e. what we normally name {\bf argv} in C/C++.\footnote{Note that in C/C++ we can name that parameter whatever we want, though it is customary to call it {\bf argv}.} There is nothing like {\bf argc}, though. The reason is that {\bf CLArgs} is of type {\bf String []}, i.e. an array of strings, and in Java even arrays are objects. Array objects include a member variable showing the length of the array, so information analogous to {\bf argc} is incorporated in {\bf CLArgs}, specifically in {\bf CLArgs.length}---the value of the {\bf length} member variable of the array class, for the instance {\bf CLArgs} of this class. The function {\bf Integer.parseInt()} is similar to {\bf atoi()} in C/C++. Note, though, since Java does not allow free-standing functions, {\bf parseInt()} must be part of a class, and it is---the {\bf Integer} class, which has lots of other functions as well. We use the compiler, {\bf javac}, to produce the class file, {\bf Minimum.class}. The latter is what is executed, when we run the Java interpreter, {\bf java}. \subsection{How to Inspect the JVM Code} We can use another program, {\bf javap}, to disassemble the contents of {\bf Minimum.class}:\footnote{So, this listing here is similar to the output of {\bf gcc -S} in a C/C++ context.} \begin{Verbatim}[fontsize=\relsize{-2}] % javap -c Minimum Compiled from Minimum.java public class Minimum extends java.lang.Object { public Minimum(); public static void main(java.lang.String[]); public static int Min(int, int); } Method Minimum() 0 aload_0 1 invokespecial #1 4 return Method void main(java.lang.String[]) 0 aload_0 1 iconst_0 2 aaload 3 invokestatic #2 6 istore_1 7 aload_0 8 iconst_1 9 aaload 10 invokestatic #2 13 istore_2 14 iload_1 15 iload_2 16 invokestatic #3 19 istore_3 20 getstatic #4 23 iload_3 24 invokevirtual #5 27 return Method int Min(int, int) 0 iload_0 1 iload_1 2 if_icmpge 10 5 iload_0 6 istore_2 7 goto 12 10 iload_1 11 istore_2 12 iload_2 13 ireturn \end{Verbatim} Note that each ``line number'' is actually an offset, i.e. the distance in bytes of the given instruction from the beginning of the given method. {\bf DON'T TRY TO UNDERSTAND THE ABOVE ASSEMBLY CODE YET.} We'll do this one part at a time, starting with the call to {\bf Min()} in the next section. \subsection{The Local Variables Section of main()} Here is what the Local Variables Section of {\bf main()}'s stack frame looks like: {\centering \begin{tabular}{|c|c|} \hline slot & variable \\ \hline \hline 0 & pointer to CLArgs \\ \hline 1 & X \\ \hline 2 & Y \\ \hline 3 & Z \\ \hline \end{tabular}\par} \subsection{The Call of Min() from main()} Now consider the call to {\bf Min()}. The code \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] Z = Min(X,Y); \end{Verbatim} gets compiled to \begin{Verbatim}[fontsize=\relsize{-2}] 14 iload_1 15 iload_2 16 invokestatic #3 19 istore_3 \end{Verbatim} As in a classical architecture, the arguments for a call are pushed onto {\bf main()}'s operand stack, as follows. The {\bf iload\_1} (``integer load'') instruction in offset 14 of {\bf main()} pushes slot 1 to the operand stack. Since slot 1 in {\bf main()} contains X, this means that X will be pushed onto {\bf main()}'s operand stack. The instruction in offset 15 will then push Y.\footnote{So, the arguments must be pushed in the order in which they appear in the call, unlike C/C++.} The {\bf invokestatic} instruction is the function call. We see here the {\bf Min()} is function number 3. By looking up information which is stored regarding {\bf Min()}, this instruction knows that {\bf Min()} has two arguments.\footnote{Again unlike C/C++, where the number of arguments in the call is unknown to the compiler.} Thus the instruction knows that it must pop two values from {\bf main()}'s operand stack, which are the arguments (placed there earlier by {\bf iload\_1} and {\bf iload\_2}), and it places them in the first two slots of {\bf Min()}'s Local Variables Area. Note that in the instruction {\bf iload\_1}, for example, the `1' is a part of the instruction name, not an operand. In fact, none of {\bf iload\_0}, {\bf iload\_1}, {\bf iload\_2} and {\bf iload\_3} has an operand; there is a separate instruction, i.e. separate op code, for each slot. But there is no {\bf iload\_5}, {\bf iload\_6} and so on. What if you need to load from some other slot, say slot 12? Then you would use the {\bf iload} instruction, which is fully general, i.e. can load from any slot, including but not limited to slots 0, 1, 2 and 3. Note that {\bf iload\_0} etc. are one-byte instructions, while {\bf iload} is a two-byte instruction, with the second byte being the slot number, so we should use those special instructions for the cases of slots 0, 1, 2 and 3. The designers of the JVM knew that most accesses to local variables would be to slots 0-3, so they decided to include special one-byte instructions to load from those slots, thus making for smaller code. Similar statements hold for {\bf istore}, etc. \subsection{Accessing Arguments from within Min()} Now, upon entry to {\bf Min()}, here is what that function's Local Variables Section will look like: {\centering \begin{tabular}{|c|c|} \hline slot & variable \\ \hline \hline 0 & U \\ \hline 1 & V \\ \hline 2 & T \\ \hline \end{tabular}\par} Since the arguments {\bf U} and {\bf V} are in slots 0 and 1, they will be accessed with instructions like {\bf iload\_0} and {\bf iload\_1}. The main new instruction in {\bf Min()} is {\bf if\_icmpge} (``if integer compare greater-than-or-equal'') in offset 2. Let's refer to the top element of the current (i.e. {\bf Min()}'s) operand stack as {\it op2} and the next-to-top element as {\it op1}. The instruction pops these two elements off the operand stack, compares them, and then jumps to the branch target if $op1 \geq op2$. Again, keep in mind that these items on {\bf Min()}'s operand stack were placed there by the {\bf iload\_0} and {\bf iload\_1} instructions. {\bf Min()}'s {\bf ireturn} instruction then pops the current (i.e. {\bf Min()}'s) operand stack and pushes the popped value on top of the caller's (i.e. {\bf main()}'s operand stack. In the case of methods which do not have return values, we use the {\bf return} instruction instead of {\bf ireturn}. \subsection{Details on the Action of Jumps} For jump instructions, the branch target is specified as the distance from the current instruction to the target. As can be seen in the JVM assembler code above, the target for the {\bf if\_icmpge} instruction in offset 2 of {\bf Min()} is offset 10 (an {\bf iload\_1} instruction). Since our {\bf if\_icmpge} instruction is in offset 2, the distance will be 8, i.e. 0x0008.\footnote{Unlike the Intel (and typical) case, the jump distance in JVM is calculated from the jump instruction, not from the one following it.} Those latter two bytes comprise the second and third bytes of the instruction. Note that the branch target must be within the current method; JVM will announce a runtime error if not. From the Sun JVM specifications (see below), we know that the op code for the {\bf if\_icmpge} instruction is 0xa2. Thus the entire instruction should be a2 00 08, and this string of three bytes should appear in the file {\bf Minimum.class}. Running the command \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] % od -t x1 Minimum.class \end{Verbatim} on a UNIX machine, we see that a2 00 08 is indeed in that file, in bytes 1255-1257 octal (685-687 decimal). \checkpoint \subsection{Multibyte Numbers Embedded in Instructions} Note in the jump example above, the instruction was a0 00 08, with a0 being the op code and 00 08 being the distance to the jump target. Note that the order of bytes in memory will be that seen above, i.e. a0 00 08, so 00 will be in a lower-address byte than 08. So, the question arises as to whether the embedded constant is intended to be 0008, i.e. 8, or 8000. The answer is the former. In other words, numbers embedded within instructions are meant to be interpreted as big-endian. \subsection{Calling Instance Methods} When an instance method is called, we use the {\bf invokevirtual} instruction instead of {\bf invokestatic}. To understand how that works. recall that in general OOP programming, an instance method includes an extra ``unofficial'' argument in the form of a pointer to the instance on which the method is invoked, i.e. the famous {\bf this} pointer in C++ (and Java). Concretely, suppose a class {\bf C} includes an instance member method {\bf M()}, say with two arguments. Then the call \begin{Verbatim}[fontsize=\relsize{-2}] M(A,B) \end{Verbatim} from within {\bf C} would in essence have three arguments---the two explicit ones, {\bf A} and {\bf B}, and also implicitly, a pointer to the current instance of {\bf C}. As with any stack-based calling system, e.g. C++ running on an Intel machine, that extra parameter must be pushed onto the stack too, just like the explicit ones. This is also done in the case of the JVM. Thus we can't use {\bf invokestatic} in the JVM case, because we must account for that ``extra'' argument. The {\bf invokestatic} instruction, as explained earlier, pops the arguments off the caller's stack and places them into the callee's Local Variables Section. That's not good enough in the case of an instance method, because that ``extra'' argument must be popped and placed into the callee's Local Variables Section too. So, the designers of the JVM also included an {\bf invokevirtual} instruction to do this; it transfers {\it all} the arguments from the caller's stack to the callee's Local Variables Section, both the explicit arguments and the ``extra'' one. So, from the callee's point of view, the item in its slot 0 will be {\bf this}, the pointer to the current object, and in fact the compiler will translate references to {\bf this} to accesses to slot 0. The only example we have so far of a call made via {\bf invokevirtual} is in the compiled code for our source line in {\bf main()}, \begin{Verbatim}[fontsize=\relsize{-2}] System.out.println(Z); \end{Verbatim} The compiled code is \begin{Verbatim}[fontsize=\relsize{-2}] 20 getstatic #4 23 iload_3 24 invokevirtual #5 \end{Verbatim} That 3 in offset 23 refers to slot 3, the location of our local variable {\bf Z}, our argument to {\bf println()}. \checkpoint The code \begin{Verbatim}[fontsize=\relsize{-2}] System.out.println(Z); \end{Verbatim} calls the {\bf println()} method on the object {\bf System.out}. The official Java documentation indicates that the latter is an instance of the class {\bf java.io.PrintStream}, which in turn is a subclass of the class {\bf java.io.FilterOutputStream}. That latter class includes a member variable {\bf out}, which is basically a pointer to the file we are writing to. In this case, we are writing to the screen (in UNIX parlance, {\bf stdout}). With that in mind, look at the instruction in offset 20. From our discussion above, you can see that this instruction must be placing a pointer to the object {\bf System.out} on the stack, and that is exactly what the {\bf getstatic} instruction is doing. It is getting a class (i.e. {\bf static}) variable from the given object, and pushing it onto the stack. \subsection{Creating and Accessing Arrays} Arguments and local variables which are arrays are maintained as addresses within the Local Variables Area. Array read accesses work by pushing the address of the array and the desired index onto the operand stack, and then executing one of the special array instructions. Array write accesses are done the same way, but with an additional push for the value to be stored. There are also special array instructions which create the array storage itself when {\bf new} is invoked. Consider the following example: \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] public int gy(int x) { int y[],z; y = new int[5]; z = x + 2; y[3] = x; return 0; } \end{Verbatim} (It does nothing of interest, but will serve as a convenient simple example.) That code is translated to: \begin{Verbatim}[fontsize=\relsize{-2}] Method int gy(int) 0 iconst_5 1 newarray int 3 astore_2 4 iload_1 5 iconst_2 6 iadd 7 istore_3 8 aload_2 9 iconst_3 10 iload_1 11 iastore 12 iconst_0 13 ireturn \end{Verbatim} Here you see the {\bf newarray} instruction is used to create space for the array, specifically enough for 5 {\bf int}s; the 5 was pushed onto the operand stack by the {\bf iconst\_5} (``integer constant'') instruction. The assignment to {\bf y[3]} is done by the code in offsets 7-11. Make sure you see how this works. In particular, the {\bf iastore} (``integer array store'') instruction first pops the stack to determine which value to store, which is slot 1, i.e. {\bf x}. (Note that lacking the {\bf static} keyword, this is an instance function.) It then pops again to determine which array element to store to (index 3), and finally pops once more to determine which array to use (slot 2, i.e. {\bf y}). In the code for {\bf main()} in our {\bf Min} example above, {\bf CLArgs} is an array of strings, thus an array of arrays, just as in C/C++. The {\bf aload\_0} (``address load'') instruction pushes the address in slot 0 i.e. the address of {\bf CLArgs}, onto the current operand stack. Similarly, {\bf iconst\_0} (``integer constant'') pushes the constant 0. All this is preparation for accessing the array element {\bf CLArgs[0]}. However, since that element is a string, thus an address again, we do not use {\bf iastore} as before, instead using the {\bf aastore} instruction (``address array store''). \checkpoint \subsection{Constructors} When the constructor for a new object is called, we need to execute a {\bf invokespecial} instruction. %%% This makes no sense in English: %% You see that in offsets 0 and 1 of {\bf Minimum()}, the %% constructor function, in the assembly listing above. %% The %%% I just editied it out. You may correct it! :o) \subsection{Philosophy Behind the Design of the JVM} Remember, we are here to learn about the Java machine, not the Java language. One aspect of that concerns why the designers of the JVM made certain choices as to the structure of the machine. Before we continue, note that the JVM {\it is} a machine, just like Intel, MIPS or the others. While it's true that we most often just use an emulator program, JVM chips have indeed been built. So for example one could certainly write a C compiler for the machine, i.e. write a compiler that translates C source code to JVM machine code. \subsubsection{Instruction Structure} Most instructions are a single byte in length, but there are a few multi-byte instructions as well. In any case, the first byte is the op code, and any operands are in the bytes that follow. As mentioned earlier, almost all JVM instructions involve stack operations, so there are no explicit operands, which is why most instructions are a single byte long. This has other implications, explained below. \subsubsection{Stack Architecture} You may wonder why the developers of the JVM chose the stack-based architecture. Actually, the literature is not clear about this. One claim is that the choice of this architecture was made in order to make it easy to write JVM interpreters for native machines that had few or no registers. If for example the developers had chosen to have the JVM have 32 registers, then on machines with fewer registers the authors of Java interpreters would not be able to model the JVM virtual registers by the real registers of the native machines. Instead, the JVM registers would have to be modeled by variables in memory. This does not sound like a very convincing argument. For one thing, it makes it more difficult for authors of interpreters on machines that do have a lot of registers to write fast interpreters. Another claim is that by having most instructions only a single byte in length, the overall program size is smaller. This would be an important consideration if it were true. Java code is often transported over the network. This happens behind the scenes when you access a Java-powered Web page. The Web site will download Java code for some operation to your machine (the one where you are running the browser), and that code will be executed by the Java interpreter on your machine. So smaller code would mean less network download delay. But is Java code smaller? Recall that RISC instructions are also very simple, but that that actually tends to make code size larger than on CISC machines, since each instruction does less work. Since the stack architecture means a lot of pushes and pops in order to manoevre data items for arithmetic, it may well be the case that code size is larger for the JVM. However,\footnote{As pointed out by student Daniel Wolfe.} the JVM situation is very different from the RISC one, because with the former we are worried about conserving network bandwidth. JVM byte code is likely to be highly compressable---certain instructions like, say, {\bf iload\_0} are probably quite frequent---so that download times could be made quite low. \checkpoint \subsubsection{Safety} Note that there are separate instructions {\bf istore\_0} and {\bf astore\_0}. Each pops the operand stack and places the popped value into slot 0. But the first assumes the popped value is an integer, while the second assumes an address.\footnote{Formally called a {\bf reference}.} In other words, unlike ``normal'' machines, in which the hardware is unaware of types, the JVM is quite aware and proactive. The JVM will check types (which are stored with the value), and a runtime error will occur if, for example, one tries to execute {\bf astore\_0} when the top of the operand stack contains an integer type. Java does allow {\bf type coercion} as in C/C++. Consider for instance the code \begin{Verbatim}[fontsize=\relsize{-2}] int I = 12; float X; ... X = I + (float) 3.8; \end{Verbatim} Here the variable {\bf I} is converted to type {\bf float} in the compiled code, using the JVM's {\bf i2f} instruction. Getting back to the safety issue, one concern is that Java code might be ``hacked'' during its transport over the network. There are various mechanisms within the JVM to check that the code is the same as when it was sent; none of these is perfect, of course, but it does provide some protection. \section{Another Example} This one finds the row in a matrix which has minimum sum. \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] public class Min2 { public static int ABC[][]; // elements will be within [0,1000000] public static void main(String[] CLArgs) { int I,J; ABC = new int[10][10]; // fill it with something, just an example for (I = 0; I < 10; I++) for (J = 0; J < 10; J++) ABC[I][J] = 2 * I + J; System.out.println(Min()); } public static int Min() { int Row,Col,MinSoFar,Sum; MinSoFar = 1000000; // note restrictions on ABC above for (Row = 0; Row < 10; Row++) { Sum = 0; for (Col = 0; Col < 10; Col++) { Sum += ABC[Row][Col]; if (Sum > MinSoFar) break; } if (Sum < MinSoFar) MinSoFar = Sum; } return MinSoFar; } } \end{Verbatim} \begin{Verbatim}[fontsize=\relsize{-2}] Compiled from Min2.java public class Min2 extends java.lang.Object { public static int ABC[][]; public Min2(); public static void main(java.lang.String[]); public static int Min(); } Method Min2() 0 aload_0 1 invokespecial #1 4 return Method void main(java.lang.String[]) 0 bipush 10 2 bipush 10 4 multianewarray #2 dim #2 8 putstatic #3 11 iconst_0 12 istore_1 13 goto 45 16 iconst_0 17 istore_2 18 goto 36 21 getstatic #3 24 iload_1 25 aaload 26 iload_2 27 iconst_2 28 iload_1 29 imul 30 iload_2 31 iadd 32 iastore 33 iinc 2 1 36 iload_2 37 bipush 10 39 if_icmplt 21 42 iinc 1 1 45 iload_1 46 bipush 10 48 if_icmplt 16 51 getstatic #4 54 invokestatic #5 57 invokevirtual #6 60 return Method int Min() 0 ldc #7 2 istore_2 3 iconst_0 4 istore_0 5 goto 52 8 iconst_0 9 istore_3 10 iconst_0 11 istore_1 12 goto 36 15 iload_3 16 getstatic #3 19 iload_0 20 aaload 21 iload_1 22 iaload 23 iadd 24 istore_3 25 iload_3 26 iload_2 27 if_icmple 33 30 goto 42 33 iinc 1 1 36 iload_1 37 bipush 10 39 if_icmplt 15 42 iload_3 43 iload_2 44 if_icmpge 49 47 iload_3 48 istore_2 49 iinc 0 1 52 iload_0 53 bipush 10 55 if_icmplt 8 58 iload_2 59 ireturn \end{Verbatim} So, for example, look at 13 of the source code, \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] ABC[I][J] = 2 * I + J; \end{Verbatim} This single Java statement compiles to a remarkable 10 JVM machine instructions! They are in offsets 21-32 of {\bf main()}. Below is an overview of what they do: \begin{Verbatim}[fontsize=\relsize{-2}] 21 push address of ABC 24 push I 25 pop I, address of ABC; push address of ABC[I] 26 push J 27 push 2 28 push I 29 pop I, 2; push 2*I 30 push J 31 pop J, 2*I; push 2*I+J 32 pop 2*I+J, J, address of ABC[I]; do ABC[I][J]=2*I+J \end{Verbatim} As you read this, recall that a two-dimensional array is considered an array of arrays. For example, row {\bf I} of {\bf ABC}, i.e. {\bf ABC[I]}, is an array. Recall also that an array name, when used without a subscript, is the address of the beginning of that array. Here {\bf ABC[I]}, considered as an array, has no subscript, while for instance {\bf ABC[I][J]} has the subscript {\bf J}. So, {\bf ABC[I]} is an address. Thus {\bf ABC} is an array of addresses! Hence the use of {\bf aaload} in offset 25. \checkpoint The {\bf multianewarray} instruction sets up space for the array, pushing the address on the stack. The {\bf putstatic} instruction then pops that address off the stack, and places it in the entry for this {\bf static} variable in the Method Area. %% Thomas started here. \section{Yet Another Example} \label{yet} This example builds a linked list of integers: \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] // this class is in the file NumNode.java public class NumNode { private static NumNode Nodes = null; // valued stored in this node int Value; // "pointer" to next item in list NumNode Next; public NumNode(int V) { Value = V; Next = null; } public static NumNode Head() { return Nodes; } public void Insert() { if (Nodes == null) { Nodes = this; return; } if (Value < Nodes.Value) { Next = Nodes; Nodes = this; return; } else if (Nodes.Next == null) { Nodes.Next = this; return; } for (NumNode N = Nodes; N.Next != null; N = N.Next) { if (Value < N.Next.Value) { Next = N.Next; N.Next = this; return; } else if (N.Next.Next == null) { N.Next.Next = this; return; } } } public static void PrintList() { if (Nodes == null) return; for (NumNode N = Nodes; N != null; N = N.Next) System.out.println(N.Value); } } \end{Verbatim} \begin{Verbatim}[fontsize=\relsize{-2}] Compiled from "NumNode.java" public class NumNode extends java.lang.Object{ int Value; NumNode Next; public NumNode(int); Code: 0: aload_0 1: invokespecial #1; //Method java/lang/Object."":()V 4: aload_0 5: iload_1 6: putfield #2; //Field Value:I 9: aload_0 10: aconst_null 11: putfield #3; //Field Next:LNumNode; 14: return public static NumNode Head(); Code: 0: getstatic #4; //Field Nodes:LNumNode; 3: areturn public void Insert(); Code: 0: getstatic #4; //Field Nodes:LNumNode; 3: ifnonnull 11 6: aload_0 7: putstatic #4; //Field Nodes:LNumNode; 10: return 11: aload_0 12: getfield #2; //Field Value:I 15: getstatic #4; //Field Nodes:LNumNode; 18: getfield #2; //Field Value:I 21: if_icmpge 36 24: aload_0 25: getstatic #4; //Field Nodes:LNumNode; 28: putfield #3; //Field Next:LNumNode; 31: aload_0 32: putstatic #4; //Field Nodes:LNumNode; 35: return 36: getstatic #4; //Field Nodes:LNumNode; 39: getfield #3; //Field Next:LNumNode; 42: ifnonnull 53 45: getstatic #4; //Field Nodes:LNumNode; 48: aload_0 49: putfield #3; //Field Next:LNumNode; 52: return 53: getstatic #4; //Field Nodes:LNumNode; 56: astore_1 57: aload_1 58: getfield #3; //Field Next:LNumNode; 61: ifnull 119 64: aload_0 65: getfield #2; //Field Value:I 68: aload_1 69: getfield #3; //Field Next:LNumNode; 72: getfield #2; //Field Value:I 75: if_icmpge 92 78: aload_0 79: aload_1 80: getfield #3; //Field Next:LNumNode; 83: putfield #3; //Field Next:LNumNode; 86: aload_1 87: aload_0 88: putfield #3; //Field Next:LNumNode; 91: return 92: aload_1 93: getfield #3; //Field Next:LNumNode; 96: getfield #3; //Field Next:LNumNode; 99: ifnonnull 111 102: aload_1 103: getfield #3; //Field Next:LNumNode; 106: aload_0 107: putfield #3; //Field Next:LNumNode; 110: return 111: aload_1 112: getfield #3; //Field Next:LNumNode; 115: astore_1 116: goto 57 119: return public static void PrintList(); Code: 0: getstatic #4; //Field Nodes:LNumNode; 3: ifnonnull 7 6: return 7: getstatic #4; //Field Nodes:LNumNode; 10: astore_0 11: aload_0 12: ifnull 33 15: getstatic #5; //Field java/lang/System.out:Ljava/io/PrintStream; 18: aload_0 19: getfield #2; //Field Value:I 22: invokevirtual #6; //Method java/io/PrintStream.println:(I)V 25: aload_0 26: getfield #3; //Field Next:LNumNode; 29: astore_0 30: goto 11 33: return static {}; Code: 0: aconst_null 1: putstatic #4; //Field Nodes:LNumNode; 4: return } \end{Verbatim} You may notice some new instructions in this example. There are actually only six of them---{\bf aconst\_null}, {\bf ifnull}, {\bf ifnonnull}, {\bf getfield}, {\bf putfield}, and {\bf areturn}. The first three of these all deal with the value {\tt NULL}, the value for null pointers. The instruction {\bf aconst\_null} is very simple. All it does is push the value of {\tt NULL} onto the stack, just like {\bf iconst\_4} would push the value of 4 onto the stack.\footnote{Recall that the `a' means ``address,'' while `i' means ``integer.''} The two instructions {\bf ifnull} and {\bf ifnonnull} are conditional jumps, just like {\bf if\_cmpeq}. However, instead of comparing the first item on the stack to the second one, they jump if the value on the top of the stack is a {\tt NULL} value (for {\bf ifnull}) or not {\tt NULL} (for {\bf ifnonull}). Let's look at one of these new conditional jumps in action. Here's the first line of the function {\bf PrintList()}: \begin{Verbatim}[fontsize=\relsize{-2}] if (Nodes == null) return; \end{Verbatim} This line compiles to the following three instructions: \begin{Verbatim}[fontsize=\relsize{-2}] 0: getstatic #4; //Field Nodes:LNumNode; 3: ifnonnull 7 6: return \end{Verbatim} It's interesting to note that an ``If Nodes {\bf is} {\tt NULL}...'' source code line generates a ``If Nodes is {\bf not} {\tt NULL}...'' instruction ({\bf ifnonnull}) in the compiled code! The reason? It takes fewer instructions to do it that way. Consider the alternative: \begin{Verbatim}[fontsize=\relsize{-2}] public static void PrintList(); Code: 0: getstatic #4; //Field Nodes:LNumNode; 3: ifnull 9 6: goto 10 9: return \end{Verbatim} The instruction {\bf areturn}\footnote{That's {\it a return}, not {\it are turn}.} does basically the same thing as {\bf ireturn}, except that it doesn't return an integer as a return value. Instead, it returns an object referance---a pointer to something other than your usual types like {\bf int} and {\bf float}.\footnote{Again, the `a' stands for ``address.''} For example, the statement \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] return Nodes; \end{Verbatim} in {\bf Head()} compiles to \begin{Verbatim} 0: getstatic #4; //Field Nodes:LNumNode; 3: areturn \end{Verbatim} The {\bf getstatic} instruction pushes the value of {\bf Nodes} onto the stack, and then the instruction {\bf areturn} pops that value, and pushes it onto the stack of the function which called {\bf Head()}. The last two new instructions, {\bf getfield} and {\bf putfield} work basically the same as {\bf getstatic} and {\bf putstatic}, except that they load and save values to and from non-static member variables (``fields'') in a class. For instance, in the line \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] if (Value < Nodes.Value) { \end{Verbatim} the fetching of {\bf Value}, whose ``full name'' is {\bf this.Value}, compiles to \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] 11: aload_0 12: getfield #2; //Field Value:I \end{Verbatim} The {\bf aload\_0} instruction pushes the address in Slot 0, which is {\bf this}, onto the stack. The {\bf getfield} instruction---yes, keep in mind that this is a JVM machine instruction---then gets the {\bf Value} field from within the class instance pointed to by {\bf this}. \checkpoint The file {\bf Intro.java} illustrates the usage of the {\bf NumNode} class: \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] // usage: java Intro nums // reads integers from the command line, storing them in a linear linked // list, maintaining ascending order, and then prints out the final list // to the screen public class Intro { public static void main(String[] Args) { int NumElements = Args.length; for (int I = 1; I <= NumElements; I++) { int Num; Num = Integer.parseInt(Args[I-1]); NumNode NN = new NumNode(Num); NN.Insert(); } System.out.println("final sorted list:"); NumNode.PrintList(); } } \end{Verbatim} It compiles to \begin{Verbatim}[fontsize=\relsize{-2}] Compiled from Intro.java public class Intro extends java.lang.Object { public Intro(); public static void main(java.lang.String[]); } Method Intro() 0 aload_0 1 invokespecial #1 4 return Method void main(java.lang.String[]) 0 aload_0 1 arraylength 2 istore_1 3 iconst_1 4 istore_2 5 goto 35 8 aload_0 9 iload_2 10 iconst_1 11 isub 12 aaload 13 invokestatic #2 16 istore_3 17 new #3 20 dup 21 iload_3 22 invokespecial #4 25 astore 4 27 aload 4 29 invokevirtual #5 32 iinc 2 1 35 iload_2 36 iload_1 37 if_icmple 8 40 getstatic #6 43 ldc #7 45 invokevirtual #8 48 invokestatic #9 51 return \end{Verbatim} There are again some new instructions to discuss here. First, consider the Java statement \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] int NumElements = Args.length; \end{Verbatim} in {\bf Intro.java}. Java is a more purely object-oriented language than C++, and one illustration of that is that in Java arrays are objects. One of the member variables in the {\bf Array} class is {\bf length}, the number of elements in the array. Thus the compiler translates the fetch of {\bf Args.length} to \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] 0 aload_0 1 arraylength \end{Verbatim} Note again that {\bf arraylength} is a JVM machine instruction. This is not a subroutine call. \checkpoint Now consider the statement \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] NumNode NN = new NumNode(Num); \end{Verbatim} It compiles to \begin{Verbatim}[fontsize=\relsize{-2}] 17 new #3 20 dup 21 iload_3 22 invokespecial #4 25 astore 4 \end{Verbatim} The JVM instruction set includes an instruction {\bf new}, which allocates space from the heap for the object to be created of class {\bf NumNode}. The instruction pushes a pointer to that space. Next, the {\bf dup} (``duplicate'') instruction pushes a second copy of that pointer, to be used later in the compiled code for \begin{Verbatim}[fontsize=\relsize{-2},numbers=left] NN.Insert(); \end{Verbatim} But before then we still need to call the constructor for the {\bf NumNode} class, which is done in offset 22, after pushing the parameter in offset 21. The assignment of the pointer to {\bf NN} then is done in offset 25. \section{Overview of JVM Instructions} \label{ref} In the following, {\it top} will refer to the element at the top of the operand stack, and {\it nexttop} will refer to the element next to it. \begin{itemize} \item {\bf aaload}: Format: 0x32 Loads an element of an array of addresses (i.e. from a multidimensional array). Treats {\it nexttop} as a pointer to an array (i.e. a variable declared of array type), and {\it top} is an index into the array. The instruction loads the array element and pushes it onto the operand stack. In other words, {\it nexttop} and {\it top} are popped, and {\it nexttop}[{\it top}] is fetched and pushed onto the operand stack. \item {\bf arraylength}: Format: 0xbe Pops the operand stack to get the array address, and then pushes the length of the array. \item {\bf aastore}: Format: 0x53 Does the opposite of {\bf aaload}, popping the operand stack first to get {\it value}, then to get {\it index}, the finally to get {\it address}. It then stores {\it value} into element {\it index} of the array starting at {\it address}. \item {\bf aconst\_null}: %% Format: 0x01 Pushes the value {\tt NULL} onto the stack. \item {\bf aload}: Format: 0x19 {\it 8bitindex} Treats the value in slot {\it 8bitindex} as an address, and pushes it onto the stack. \item {\bf aload\_0}, {\bf aload\_1}, {\bf aload\_2}, {\bf aload\_3}: Formats: 0x2a, 0x2b, 0x2c The instruction {\bf aload\_0}, is the same as {\bf aload}, but specifically for slot 0. The others are analogous. \item {\bf areturn}: %% Format: 0xb0 Does exactly the same thing as {\bf ireturn}, but instead of returning an integer, it returns an object referance. \item {\bf astore}: Format: 0x3a, {\it 8bitindex} Opposite of {\bf aload}, popping the operand stack and placing the popped value (presumed to be an address) into the specified slot. \item {\bf astore\_0}, {\bf astore\_1}, {\bf astore\_2}, {\bf astore\_3}: Formats: 0x4b, 0x4c, 0x4d, 0x4e Same as {\bf astore}, but specifically for slot 0, slot 1 etc.. \item {\bf bipush}: Format: 0x10 {\it 8bitinteger} Pushes the given 8-bit integer onto the operand stack. \item {\bf dup}: Format: 0x59 Duplicates the top word on the operand stack, so the operand stack now has two copies of that word instead of one. \item {\bf dup\_x2}: Format: 0x5b Like {\bf dup}, but places the duplicate copy of the top of the stack just past the third word in the stack. For example, (12,5,13,8) becomes (12,5,13,12,8). \item {\bf getfield}: %% Format: 0xb5 {\it 16bitindex} Opposite of {\bf putfield}. Gets value of the given non-static item, then pushes it onto the operand stack. \item {\bf getstatic}: Format: 0xb2 {\it 16bitindex} Opposite of {\bf putstatic}. Gets value of the given static item, then pushes it on the operand stack. \item {\bf goto}: Format: 0xa7 {\it 16bitjumpdistance} Unconditional jump. See {\bf if\_icmpeq} for explanation of {\it 16bitjumpdistance}. \item {\bf i2f}: Format: 0x86 Pops the top word on the stack, converts it from {\bf int} to {\bf float}, and pushes the new value back onto the stack. \item {\bf iadd}: Format: 0x60 Pops {\it nexttop} and {\it top}, and pushes the sum {\it nexttop} + {\it top}. \item {\bf iaload}: Format: 0x2e Load an element of an integer array. See {\bf aaload} above. \item {\bf iastore}: Format: 0x4f Store to an element of an integer array. See {\bf aastore} above. \item {\bf iconst\_0}, {\bf iconst\_1}, {\bf iconst\_2}, {\bf iconst\_3}, {\bf iconst\_4}, {\bf iconst\_5}: Format: 0x3, 0x4, 0x5, 0x6, 0x7, 0x8 Pushes the integer constant 0, 1, 2 etc. onto the operand stack. \item {\bf idiv}: Format: 0x6c Pops {\it nexttop} and {\it top}, and pushes the quotient {\it nexttop} / {\it top}. \item {\bf if\_icmpeq}: Format: 0x9f {\it 16bitjumpdistance} If {\it top} = {\it nexttop}, jumps the given distance to the branch target. The quantity {\it 16bitjumpdistance} is a 2-byte, 2s complement signed number, measured from the jump instruction. Both {\it top} and {\it nexttop} must be integers; a runtime error occurs if no. \item {\bf if\_icmpge}: Format: 0xa2 {\it 16bitjumpdistance} Same as {\bf if\_icmpeq}, but jumps if {\it nexttop} $\geq$ {\it top}. \item {\bf if\_icmple}: Format: 0xa4 {\it 16bitjumpdistance} Same as {\bf if\_icmpeq}, but jumps if {\it nexttop} $\leq$ {\it top}. \item {\bf if\_icmplt}: Format: 0xa1 {\it 16bitjumpdistance} Same as {\bf if\_icmpeq}, but jumps if {\it nexttop} $<$ {\it top}. \item {\bf if\_icmpne}: Format: 0xa0 {\it 16bitjumpdistance} Same as {\bf if\_icmpeq}, but jumps if {\it top} $\neq$ {\it nexttop}. \item {\bf ifnonnull}: %% Format: 0xc7 {\it 16bitjumpdistance} Same as the previous jump conditions, but jumps if {\it top} $\neq$ {\tt NULL}. \item {\bf ifnull}: %% Format: 0xc6 {\it 16bitjumpdistance} Same as the previous jump conditions, but jumps if {\it top} = {\tt NULL}. \item {\bf iinc}: Format: 0x84 {\it 8bitindex} {\it 8bitinteger} Increments slot {\it 8bitindex} by the amount {\it 8bitinteger}. \item {\bf iload}: Format: 0x15 {\it 8bitindex} Same as {\bf aload} but for integers instead of addresses. \item {\bf iload\_0}, {\bf iload\_1}, {\bf iload\_2}, {\bf iload\_3}: Formats: 0x1a, 0x1b, 0x1c, 0x1d Same as {\bf aload\_0} etc. but for integers instead of addresses. \item {\bf imul}: Format: 0x68 Pops {\it nexttop} and {\it top}, and pushes the product {\it nexttop} $\times$ {\it top}. \item {\bf invokespecial}: Format: 0xb7 {\it 16bitindex} Like {\bf invokevirtual}, but for constructors, superclass and other special situations. \item {\bf invokestatic}: Format: 0xb8 {\it 16bitindex} Method call. The quantity {\it 16bitindex} serves as an index into the Constant Pool, pointing to the given method. Creates a new stack frame for the method. Pops the method's arguments from the caller's operand stack and places them into the method's Local Variables Section. Points the {\bf frame} register to the method's stack frame, and jumps to the method. \item {\bf invokevirtual}: Format: 0xb6 {\it 16bitindex} Same as {\bf invokestatic}, but the arguments include the ``hidden'' argument {\bf this}, i.e. a pointer to the object this method is being invoked on. \item {\bf ireturn}: Format: 0xac Return from method with return value. Pops integer from current operand stack, places it on the caller's operand stack, restores the {\bf frame} register to point to the caller's stack frame, and jumps back to the caller. \item {\bf istore}: Format: 0x36 {\it 8bitindex} Same as {\bf astore} but for integers instead of addresses. \item {\bf istore\_0}, {\bf istore\_1}, {\bf istore\_2}, {\bf istore\_3}: Formats: 0x3b, 0x3c, 0x3d, 0x3e Same as {\bf astore\_0} etc. but for integers instead of addresses. \item {\bf isub}: Format: 0x64 Pops {\it nexttop} and {\it top}, and pushes the difference {\it nexttop} - {\it top}. \item {\bf ldc}: Format: 0x12 {\it 8bitindex} Gets an item from the Constant Pool and pushes it onto the operand stack. \item {\bf new}: Format: 0xbb {\it 16bitindex} Performs the Java {\bf new} operation, with {\it 16bitindex} being the index into the Constant Pool, pointing to the given class. Creates the given object using memory from the Heap, and then pushes the address of the new object on the operand stack. \item {\bf putfield}: %% Format: 0xb4 {\it 16bitindex} Pops the operand stack, and assigns the popped value to the non-static item given by {\it 16bitindex}. \item {\bf putstatic}: Format: 0xb3 {\it 16bitindex} Pops the operand stack, and assigns the popped value to the static item given by {\it 16bitindex}. \item {\bf return}: Format: 0xb1 Same as {\bf ireturn}, but for methods without a return value. \item {\bf swap}: Format: 0x5f Swaps the top two words of the operand stack. \end{itemize} \section{References} \begin{itemize} \item Bill Venners' book, {\it Inside the Java Virtual Machine}. Available on the Web (with many helpful URL links) at \url{www.artima.com}. \item Sun's ``official'' definition of the JVM: {\it The Java Virtual Machine Specification}, by Lindholm and Yellin, also available on the Web, at \url{http://java.sun.com/docs/books/vmspec/2nd-edition/html/VMSpecTOC.doc.html}. Chapter 6 gives specs (mnemonics, op codes, actions, etc.) on the entire JVM instruction set. \end{itemize}