Celebrity Compilers - Introduction to Compiler Construction in a Java World - page 290

their own method tables to store the addresses of their stubs. All object instances of the same
type will refer to the same method table. Each method table contains information about
the type, such as whether it is an interface, abstract class, or concrete class; the number of
interfaces implemented by the type; the interface map for method dispatch; the number of
slots in the method table; and an embedded method slot table, which points to the method
implementations called method descriptors. Method slot table entries are always ordered as
inherited virtuals, introduced virtuals, instance methods, and static methods. As Figure 8.5
shows, ToString , Equals , GetHashCode , and Finalize are the first four methods in the
method slot table for any type. These are virtual methods inherited from System.Object .
.cctor and .ctor are grouped with static methods and instance methods, respectively.
Initially, all entries in the method tables refer to the JIT compiler through method
descriptors. Method descriptors are generated during the loading process and they all point
to the CIL code (CodeOrIL in Figure 8.5) with a padding of 5 bytes (PreJit Stub in Figure
8.5) containing the instructions to make a call to the JIT Compiler. As discussed in Section
8.2, it is possible that some code might never be called during execution. So instead of
converting all of the CIL code into native machine code, the JIT compiler converts the
CIL as needed. Once a method is called for the first time, the call instruction contained
in the associated stub passes control to the JIT compiler, which converts the CIL code
for that method into native code and modifies the stub to direct execution to the location
of the native code by overwriting the call instruction with an unconditional jump to the
JIT-compiled native code. In other words, while methods are being stubbed out, the JIT
compiler overwrites the call instruction, replacing the address in the method table with the
compiled codes memory address. The machine code produced for the stubbed out methods is
stored in memory. Subsequent calls to the JIT-compiled method directly invoke the machine
code that was generated after the first call; thus, time to compile and run the program is
reduced [Kommalapati and Christian, 2005].
Conversion of CIL to native code is done in several stages. The first stage is import-
ing, in which the CIL code is rst converted to JIT's internal representation. The JIT
compiler has to make sure that the CIL code is type safe before converting it into machine
code|conrming that the code can access memory locations and call methods only through
properly defined types.
The second stage is morphing, where some transformations are applied to the internal
structures to simplify or lightly optimize the code. Examples of such transformations are
constant propagation and method inlining.
In the third stage, the JIT compiler performs a traditional flow-graph analysis to deter-
mine the liveness of variables, loop detection, etc. The information obtained in this stage is
used in the subsequent stages.
The fourth stage is about heavy optimizations like common sub-expression and range
check elimination, loop hoisting, and so on.
Then comes the register allocation stage, where the JIT compiler must effectively map
variables to registers.
Finally, the code generation and emitting stages come. While generating the machine
code, the JIT compiler must consider what processor it is generating code for and the
OS version. For example, it may embed the address of some Win32 APIs in to the native
code produced, and the address of these APIs could change between different service packs
of a specific Windows OS [Richter, 2005]. After generating the machine code for a specific
method, the JIT compiler packs everything together and returns to the CLR, which will then
redirect control to the newly generated code. Garbage collection and debugger information
is also recorded here. Whenever memory is low, the JIT compiler will free up memory by
placing back the stubs of methods that had not been called frequently during program
operation up to that point.