Previous article

Next article


E-Bunny: A Dynamic Compiler for Embedded Java Virtual Machines

Mourad Debbabi, Abdelouahed Gherbi, Lamia Ketari, Chamseddine Talhi, Hamdi Yahyaoui, Sami Zhioua, Concordia Institute for Information Systems Engineering Concordia University, Quebec, Canada
Nadia Tawbi, Computer Science Department, Laval University, Quebec, Canada

space REFEREED
ARTICLE


PDF Icon
PDF Version

Abstract

A new acceleration technology for Java embedded virtual machines is presented in this paper. Based on the selective dynamic compilation technique, this technology addresses the J2ME/CLDC (Java 2 Micro Edition for Connected Limited Device Configuration) platform. The primary objective of our work is to come up with an efficient, lightweight and low-footprint accelerated embedded Java Virtual Machine. This is achieved by the means of integrating a selective dynamic compiler that we called E-Bunny into the J2ME/CLDC virtual machine KVM. This paper presents the motivations, the architecture, the design and the implementation issues of E-Bunny and how we addressed them. Experimental results on the performance of our modified KVM demonstrate that we accomplished a speedup of 400% with respect to the Sun’s latest version of KVM. This experimentation was carried on using standard J2ME benchmarks.


1 MOTIVATIONS AND BACKGROUND

With the advent and rising popularity of wireless systems, there is a proliferation of small internet-enabled devices (e.g. PDAs, cell phones, pagers, etc.). In this context, Java is emerging as a standard execution environment due to its security, portability, mobility and network support features. In particular, J2ME/CLDC (Java 2 Micro- Edition for Connected Limited Device Configuration) [13] is now recognized as the standard Java platform in the domain of mobile wireless devices such as pagers, handheld PDAs, TV set-top boxes, appliances, etc. It gained big momentum and is now standardized by the Java Community Process (JCP) and adopted by many standardization bodies such as 3GPP, MEXE and OMA. Another factor that has amplified the wide industrial adoption of J2ME/CLDC is the broad range of Java based solutions that are available in the market. All these factors make Java and J2ME/CLDC an ideal solution for software development in the arena of embedded systems.

The heart of J2ME/CLDC technology is Sun’s Kilobyte Virtual Machine (KVM) [14]. The KVM is a Java virtual machine initially designed with the constraints of low-end mobile devices in mind. The performance and the security of the KVM will be two key factors in the successful deployment of Java technology in wireless and embedded systems.

The primary intent of our research initiative is to dramatically improve the performance of J2ME/CLDC virtual machines such as the KVM.

Lately, a surge of interest has been expressed in the acceleration of Java virtual machines for embedded systems. Two main approaches have been explored: hardware and software acceleration.

For hardware acceleration, a plethora of companies (Zucotto Wireless [3], Nazomi [4], etc.), had proposed Java processors that execute in silicon Java bytecodes. Although these hardware accelerators achieve a significant speedup in terms of virtual machine performance, it remains that their use comes with a high price in terms of power consumption. This energy issue is really damaging especially in the case of low-end mobile devices. Moreover, the cost (royalties, licensing, etc.) of these hardware acceleration technologies is an additional obstacle to their adoption by the industry. These drawbacks of hardware acceleration created an interesting but challenging niche for software acceleration of embedded Java virtual machines. For software acceleration, a large spectrum of techniques has been advanced [1, 5, 6, 7, 12, 16]. These techniques could be classified into 4 categories: general optimizations, ahead-of-time optimizations, just-in-time compilation and selective dynamic compilation. General optimizations consist in designing and implementing more efficient virtual machine components (better garbage collector, fast threading system, accelerated lookups, etc.). Ahead-of-time optimizations consist in using extensive static analysis (flow analysis, annotated type analysis, abstract interpretation, etc.) to optimize programs before execution. Just-in-time (JIT) compilation consists of the dynamic compilation of Java executables (bytecode). This dynamic compilation is achieved thanks to a compiler that is embedded in the Java virtual machine. The compiler is in charge of translating bytecode into the native code of the host platform on which the code is being executed. The selective dynamic compilation consists in compiling, on the fly, into native code only a selected set of methods that are performance-critical.

Experience demonstrated that general and ahead-of-time optimizations can lead to reasonable accelerations. However, they cannot compete with just-in-time and selective dynamic compilation in reaching big speedups (for instance an acceleration of more than 200 %) [15].

It is established that just-in-time compilers require a lot of memory to store the dynamic compiler and the binary code that it generates. The compilation process also implements sophisticated flow analysis and register allocation algorithms in order to generate optimized and high-quality native code. JIT compilers allow to reach high speedup but the static analysis that they use induces a significant overhead in terms of memory and time. This makes JIT compilers much more appropriate for J2SE (Java 2 Standard Edition) and J2EE (Java 2 Enterprise Edition) platforms.

Selective dynamic compilation deviates from the JIT compilation by selecting and compiling, on the fly, only those fragments of the class files that are frequently executed. These code fragments are generally referred to as hotspots. For instance, one can select only those methods that are frequently invoked and convert them to native code. By doing so, significant acceleration of the virtual machine could be reached since efficient optimizations are concentrated on performance critical fragments of the program. Another major advantage of this approach is to reduce memory overhead because only a part of a program is converted to native code. This makes selective dynamic compilation more adequate for embedded systems than JIT compilers.

This paper presents an extremely lightweight selective dynamic compiler for embedded Java virtual machine called E-Bunny. It is built on top of KVM. The contributions are threefold:

  • Our system is the first academic work that targets CLDC-based embedded Java virtual machines optimization by dynamic compilation. The remaining systems are commercial products such as [15] and [17].
  • Our solution, besides the compilation of all kind of bytecodes, covers the different issues of the integration of a dynamic compiler into a virtual machine such as multi-threading support, exception handling, garbage collection, switching mechanism between the compiler and the interpreter modes, etc.
  • Our solution is efficient. It allows to accelerate the performance by a factor of 4 while the memory footprint overhead does not exceed 138 KB.

The remainder of this paper is organized as follows. Section 2 highlights related work relevant to the dynamic compilation in the embedded context. In section 3, we present the architecture as well as the key ideas of our system. Design issues are detailed in section 4. Section 5 presents the results of our implementation and finally section 6 is a conclusion.

2 RELATED WORK

Dynamic compilation became a popular approach to optimize Java performance. Almost all standard Java virtual machines [1, 2, 12, 20, 19] are endowed with a dynamic compiler.

Java HotSpot VM [12], which is the core component of Java 2 Standard Edition, is equipped with a selective dynamic compiler. Performance critical methods are detected by means of a counter-based profiler with additional heuristics. These heuristics investigate the caller methods in order to compile them with the triggering method. On-Stack-Replacement is also used to trigger compilation while a method is still running. The Java Hotspot VM dynamic compiler applies several classical optimizations and is considered as one of the most efficient in the market. Another important reason of this efficiency is the aggressive method in-lining it applies. Indeed, methods that are detected frequent are not only compiled but also in-lined. The benefit of this optimization is that it produces larger blocks of code for the compiler to perform optimizations. Operating on large blocks of code increases the effectiveness of classical optimizations. However, using On-Stack-Replacement or applying expensive optimizations such as aggressive method in-lining is not adequate for embedded systems because they require important resources particularly memory space.

IBM Jalapeño [1] is a Java virtual machine equipped with a Just-In-Time compiler with different levels of optimizations. That is, according to the frequency of a method, this is compiled with the appropriate level of optimization. The profiler used by Jalapeño is very complex and is part of a bigger system called Adaptive Optimization System (AOS). As Java Hotspot VM, the features of IBM Jalapeño cannot be applied in an embedded context due to lack of resources. For instance, a Just-In-Time approach is not suitable because it requires that all methods are compiled, whereas, embedded systems lack the necessary memory to store all method generated code.

Other Java virtual machines are endowed with dynamic compilers including IBM JDK [19], Intel ORP [1], IBM Mixed-Mode-Compiler [20], Latte [21] and OpenJIT [11].

Embedded systems lack hardware resources that are available in desktop systems such as hundreds megabytes of RAM or microprocessors operating at over 2 GHz. This sets several limitations on what dynamic compilation could accomplish in embedded systems. In the sequel, we outline these limitations.

In the context of embedded systems, dynamic compilation should cope with two major difficulties. First, the dynamic compiler should be maintained in memory while the application is executing. This is very challenging because of the stringent lack of memory resources. Second, heavyweight code optimizations are not affordable because of their overhead. However, without such optimizations, a dynamic compiler produces a code of low quality and large quantity. This code requires additional memory to be stored. It is worth mentioning that the produced native code could be 8 times the size of the original bytecode [15]. Hence, embedded dynamic compilers are required to be extremely frugal with memory resources. Another consequence of the big size of native instructions compared to bytecode is the risk of instruction cache overflow. Indeed, among the hardware limitations of embedded systems is the reduced amount of on-chip processor instruction cache. The amount of this resource is suitable for bytecode interpretation. However, due to its big size, the machine code produced by the dynamic compiler can be several times larger than the size of the available instruction cache [15]. This leads to several cache misses that decreases the program performance.

Despite these difficulties, dynamic compilation is also used in CLDC-based em- bedded virtual machines [15, 17, 18]. However, except one paper about KJIT [18], no detailed information about these systems is available in the literature due to commercial reasons.

KJIT [18] is a lightweight dynamic compiler that uses as its foundation the KVM. KJIT does not use any form of profiling for the simple reason that all methods are compiled. This strategy seems to be very heavyweight and only feasible in server or desktop systems. The key idea to make this strategy adequate for embedded Java virtual machines is to compile only a subset of bytecodes. The remaining bytecodes continue to be handled by the interpreter. Indeed, whenever one of the interpreted bytecodes is encountered, execution switches back from the compiled mode to the interpreted mode. This requires an efficient handling of the switching mechanism since this operation is highly frequent. This is achieved in KJIT by pre-processing the bytecode before their compilation. The cost of pre-processing, however, is an additional time required for pre-processing together with an additional space required to store the generated bytecode. The latter is 30% larger than the original bytecode.

CLDC Hotspot VM [15] is an embedded virtual machine introduced by Sun Microsystems. As its name indicates, it is strongly inspired by the standard Java Hotsopt VM. All features of Java Hotspot VM that can be adapted to resourceconstrained environments are applied. Among these features, we find a selective dynamic compiler. Performance critical methods are detected by a single statistical profiler. The compilation is performed in one pass. Three basic optimizations are applied: constant folding, constant propagation and loop peeling. The memory footprint required by CLDC Hotspot (including APIs) reaches 1 megabyte which is almost the double of the space required by KVM. No more details are provided about the CLDC Hotspot dynamic compiler.

3 ARCHITECTURE

E-Bunny is a selective dynamic compiler for embedded Java virtual machines that uses as its foundation the KVM. In this section, we present the key features that make E-Bunny an appropriate Java acceleration technology for embedded systems.

The major features of E-Bunny are:

  • Reduced Memory Footprint: The footprint resulting from the integration of the E-Bunny dynamic compiler does not exceed 150 KB. The key idea to reduce the code size of E-Bunny is to merge the compilation processing of some bytecodes. This is possible because several bytecodes have joint processing (e.g. invokespecial, invokevirtual). This strategy is applied mainly for some bytecodes that have fast versions [9](e.g. getstatic, getstatic fast, getstaticp fast, getstatic2 fast).
  • Selective Compilation: Since selective dynamic compilation is the most adequate compilation-based acceleration technique for embedded systems, it was adopted in E-Bunny. Only a subset of methods is compiled. The methods are selected according to their invocation frequencies. The unit of compilation is exclusively a method.
  • Efficient Stack-Based Code Generation: For the compilation strategy, a trade-off has to be made between the compilation cost and the generated code quality. Although a register-based code is more efficient, we do not generate such code because it requires more passes over the bytecode. In E-Bunny, we generate a stack-based code because it requires only one pass over the bytecode. Thus, a one-pass code generation strategy is adopted, without using neither intermediate representations nor heavyweight optimizations. Only optimizations that might be applied in one pass are allowed.
  • Using two stacks: Portability is an important issue in embedded systems. Virtual machines with dynamic compilers are strongly machine-dependent because they compile the bytecode into the target machine native code. Thus, it is unavoidable to become dependent on the target machine and consequently less portable. CLDC Hotspot [15] and IBM Mixed-Mode [20] virtual machines, which adopt a mixed-mode approach, use only the native stack for both interpretation and compiled methods execution. However, the native stack is part of the target machine architecture. This makes the virtual machine very dependent on the target machine. Our dynamic compilation approach advocates the use of two stacks (one for interpretation and one for compiled methods execution) to preserve portability to a high extent. Hence, interpretation remains totally machine-independent. Moreover, the platform-specific code is isolated in specific modules. Future porting of E-Bunny to another platform requires the modification or the re-creation of only these modules. However, the drawback of this way to preserve portability is the complexity introduced by the use of two stacks. Indeed, (1) method arguments must be transferred between the two stacks when necessary, (2) the garbage collector must consider the native stack when it scans the heap and (3) additional context information must be added to the thread data structure.
  • Multi-threading Support: Another challenge introduced by dynamic compilation is the multi-threading support. Conventionally, each thread has its own execution stack. Since our approach uses two kind of stacks, each thread is assigned two stacks upon its creation: a Java stack to interpret methods and a native stack to run compiled ones. For the Java stack, we adopt the KVM way to manage the Java stacks. KVM allocates the Java stack from the heap and manipulates it at a software level. For the native stack, the approach adopted is to organize the native stack as a pool of segments and allocate a segment to each thread. Thus, the native stack will be shared by all living threads.
  • LRU Algorithm for Cache Management: A limited memory space is allocated to the compiled code. When this space is full, a cache strategy based on a Least Recently Used (LRU) algorithm [10] is adopted to free the necessary space.

Figure 1: E-Bunny Architecture

The E-Bunny architecture is depicted in Figure 1. It includes four major components: the execution engine, the profiler, the compiler and the cache manager. Initially, all invoked Java methods are interpreted. During interpretation, a counterbased profiler gathers profiling information. As the code is interpreted, the profiler identifies hotspot methods. Once a method is recognized as hotspot, its bytecodes are translated into native code by the compiler. The produced native code is stored in the dynamic compiler cache. On future references to the same method, the cached compiled method is executed instead of interpreting it. In the sequel, we highlight the main components of the proposed embedded dynamic compiler architecture.

Interpreter

By interpreter, we mean the KVM’s interpreter. It is the only way in KVM to execute Java programs. The interpreter is basically a loop that fetches, decodes and interprets bytecodes of a given method. E-Bunny adopts a mixed-mode1 execution approach. Therefore, the interpreter cooperates with the machine code execution component to switch between the two modes: interpreted and native.

Machine Code Execution Component

The machine code execution component is responsible for invoking compiled methods. Basically, it looks for the corresponding machine code in the cache and then executes it. In addition, this component is responsible for transferring, if any, methods arguments from one stack to the other. More details about this mechanism are given in Section 4. When the machine code of a given method is executed, the cache must be set up-to-date according to the cache algorithm. The machine code execution component triggers the cache update.

Profiler

A simple counter-based profiler is used in E-Bunny. A per-method counter is incremented each time the method is invoked. A method is considered as hotspot when its counter reaches an a-priori defined threshold. Consequently, a compilation request is triggered. Our profiling strategy assumes that every method called by a compiled method must be compiled. So, a compiled method cannot invoke an interpreted method. The motivation behind this strategy is to reduce the complexity of the switch mechanism between interpreted and native modes.

Compiler

The compiler is the core component of E-Bunny. It is triggered by the profiler. Basically, it compiles Java methods to machine code. The E-Bunny compiler is extremely lightweight. It goes through the bytecode in one pass and generates a stack-based code. Unlike traditional compilers, neither intermediate representations nor heavyweight optimizations are used. The compilation strategy is described in Section 4.

Cache Manager

Once a method is recognized as hotspot and compiled, the corresponding machine code needs to be stored in the heap. In E-Bunny, a fixed space, called the cache, is pre-allocated in the heap to store the generated code. The cache is pre-allocated in the permanent space of the heap to avoid any conflicts with the garbage collection mechanism. Conventionally, the garbage collector does not scan the permanent space. When the cache becomes full, the cache manager must select elements to remove in order to free space for newly compiled methods. For this purpose an LRU algorithm is used. This algorithm selects the method (or the methods) that has (have) not been invoked for the largest period of time and removes it (or them) from the cache. A queue is used to keep the chronological order of invoked methods. This queue is updated each time a compiled method is invoked. The LRU algorithm does not prevent methods from being recompiled several times, but our experiments show that using an LRU algorithm reduces efficiently the re-compilation rate.

4 DESIGN

In this section we discuss the design issues of E-Bunny. First, we detail the compilation strategy. Second, we focus on a delicate aspect of selective dynamic compilation which is the switch mechanism between interpreted and compiled modes. Then, we illustrate how E-Bunny supports multi-threading. Finally, we describe the interaction with the garbage collection mechanism.

Compilation Strategy

Our compilation strategy spans over a lightweight one pass compilation technique. This strategy avoids complex computations performed by common compilers and generates a code of reasonable quality. Indeed, the generated code is stack-based as Java bytecode but uses many information computed at the compilation step (field offsets, Constant Pool entry address etc.). These information are grafted in the generated code in order to avoid unnecessary further re-computation. Compiling a method goes through three steps. First, generating context saving instructions (the prologue). Second, translating bytecodes into machine code instructions. Third, generating context restoration instructions (the epilogue). The second step, which is the core step of our compilation strategy, consists in translating each bytecode into a sequence of native instructions. We distinguish two categories of bytecodes. The first kind includes bytecodes that are completely translated into native instructions in a straight manner. They are called: simple bytecodes. The second kind of bytecodes are more complex to translate and are called complex bytecodes. E-Bunny targets Intel IA-32 architecture [8]. IA-32 is a 32 bit CISC machine which provides eight general purpose registers (EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESP). EBP and ESP are dedicated to stack management. The remaining registers fulfill different other tasks. Hence, compiling a method consists in generating assembly instructions that reproduces the bytecode behavior on an IA-32 platform.

Context Saving and Context Restoration

Context saving and context restoration instructions are used to re-establish the calling method context after the execution exits from the callee method. Context saving instructions figure on top of the method generated code. They carry out three basic operations. First, save old EBP register value (of the calling method) on the native stack. Second, assign a new value to EBP register (of the callee method). Third, assign the new value of EBP to LastEBP field of the current thread structure (CurrentThread->LastEBP =EBP). Actually, LastEBP is a new field added to the thread data structure in E-Bunny. It gives for each thread the EBP value of the last called compiled method. This information is used to two purposes: garbage collection and exception handling. Context saving instructions in E-Bunny are illustrated in Table 1.

Table 1: Context Saving

Table 2: Context Restoration

Context restoration instructions figure on the end of method generated code. Since all Java methods finish by a return bytecode (ireturn, lreturn, areturn or return), context restoration instructions are generated when translating return bytecodes. Context restoration instructions carry out two operations. First, restore the old value of EBP register (saved on the native stack). Second, assign this value to LastEBP field of CurrentThread data structure. Consequently, when returning to the calling method, EBP register and CurrentThread->LastEBP are set to the appropriate values. Context restoration instructions in E-Bunny are illustrated in Table 2.

Simple Bytecodes Translation

The simple bytecode category includes loads (e.g. iload, iaload, ldc), stores (e.g. astore, lastore), stack manipulation (e.g. pop, dup), arithmetic, logic and shift (e.g. iadd, land, ishr, l2i) and branching (e.g. ifne, if_icmpeq, goto) bytecodes. These bytecodes are directly translated into stack-based machine code which reproduces the interpreter behavior on the native stack. As an example, we give the translation details of two bytecodes iload and ifeq. We have chosen iload bytecode to show how it behaves on the native stack and ifeq bytecode to illustrate how E-Bunny translates forward branching instructions in one pass.

Table 3: iload Bytecode Translation

Figure 2: iload on the Native Stack

The iload bytecode loads integer (32 bit value) from local variables to the top of the stack (stack operand). It is directly mapped to a push instruction as shown in Table 3. The symbols “[ ]” denote the content of the specified location. The FrameSize variable is an integer that gives the number of local variables of the current method. The displacement is multiplied by 4 because addresses in Intel2 grow by 4. The value 3 in the offset of the push instruction denotes EIP register and two empty spaces (space 1 and space 2) as illustrated in Figure 2. Notice that space 1 and space 2 are left for the returned value of the method (see Section 4).

An important issue of the one pass translation strategy is how to deal with control flow bytecodes (or branching bytecodes). In the sequel, we highlight this issue and how it is processed in E-Bunny.

Control flow bytecodes are translated using a bytecode map table called BCNativeMap. It is an integer table that maps each bytecode index to its corresponding machine instruction index. For instance, BCNativeMap[5] = 31 means that the machine instructions corresponding to the fifth bytecode start at index 31 in the NativeCode table. A BCNativeMap table is associated with each compiled method. It is initialized to zero, and filled progressively when the translation of the method is going on. At a given moment of translation, the BCNativeMap table is filled for the scanned bytecodes and empty (zero values) for the rest.

To deal with control flow bytecodes, there are two situations: forward branches and backward branches. The translation of backward branches is straightforward. BCNativeMap table is used to get the target machine instruction index, and then to generate the corresponding jump native instruction. However, the translation of forward branches is more complex. Indeed, the corresponding BCNativeMap entry of a forward branch is not resolved yet (contains zero) as the target bytecode is not already compiled. The complete translation of the forward branching bytecode is postponed until the target bytecode is reached. Actually, a jump native instruction op-code (e.g. JL, JNE, JMP) is generated with an unresolved operand. Each next bytecode is checked whether it is a target of an unresolved branching. In such case, the corresponding offset is computed and then used to patch the unresolved operand of the jump native instruction. To handle multiple unresolved forward branching, a linked list is used. In Table 4, we give the translation algorithm of ifeq bytecode and the corresponding machine instructions.

Table 4: ifeq Bytecode Translation

Table 5: putfield Bytecode Translation

Complex Bytecodes Translation

In KVM, interpretation of some bytecodes involves the use of some virtual machine runtime services such as method lookup or field reference resolution. For example, getfield bytecode uses field reference resolution subroutine to resolve the reference of the appropriate field. In E-Bunny, bytecodes that require virtual machine services are called complex bytecodes. Translating this kind of bytecodes is more complex. A possible approach consists in generating the corresponding native code, instruction by instruction, including virtual machine services. This yields a complex and a very bulky code. The approach adopted in E-Bunny is to define for each bytecode a specific function that calls necessary virtual machine services. These functions are called from the native code. Hence, the generated machine code is compact and less complex. Complex bytecodes category includes field access, objects creation, array manipulation, method invocation, return, monitor, casting and exception bytecodes. In the sequel we illustrate the translation mechanism of field access bytecodes and exception bytecode (athrow).

Field access bytecodes are putfield, getfield, putstatic, getstatic and their fast versions. These bytecodes access to object fields using symbolic references, to get or set their values. Such symbolic references have to be resolved so that the access could be possible. In E-Bunny, for each bytecode a specific function is defined. For getfield and getstatic, this function calls the field reference resolution subroutine and returns the value of the field in EAX register (EAX:ECX for long values). This value is then pushed on the native stack. For putfield and putstatic, this function calls the field reference resolution subroutine, sets this field and returns the field size in the EAX register. This value is then used to update the native stack. The translation of putfield is given in Table 5. The cp index denotes a Constant Pool index. The “ Switch” operator is used to clarify the illustration. Actually, it is implemented with jump instructions.

Method invocation bytecodes require a special care because they involve more complex processing than other bytecodes. Furthermore they are performance critical (on average 11% of total bytecodes are method invocation bytecodes [16]). The processing that method invocation bytecodes should carry out includes: performing a method reference resolution, checking the validity of the receiver object, performing a dynamic method lookup, creating a new frame for the invoked method, etc. Moreover, these bytecodes deal with the switch mechanism between interpreted and compiled modes (more details about the switch mechanism are given in next section).

In E-Bunny, to translate invoke bytecodes, specific functions have been defined (callVirtual for invokevirtual and invokespecial, callStatic for invokeStatic and callinterface for invokeinterface). These functions behave differently according to the kind of the called method (compiled or native). The conventions adopted to design these functions are the following: If the invoked method is native, the defined functions resolve the invoked method reference, check the validity of the receiving object, make the method lookup, transfer the arguments form the native stack to the Java stack (because the native functions consider the Java stack to get the arguments), invoke the native functions and finally transfer returned value to Java stack. In addition, these functions, set EAX register to 1 (to distinguish the native function call from the compiled method invocation) and EDX register to an integer value necessary to update the native stack.

Table 6: invokevirtual Bytecode Translation

Table 7: athrow Bytecode Translation

If the invoked method is compiled, these defined functions resolve the invoked method reference, check the validity of the receiving object, make the method lookup, get the machine code from the cache, update the latter and exit. We note here that the defined function does not call the invoked method. Instead, the machine code address of the called method and the local variables number are returned respectively in EDX register and in the top of the stack. These values are used to prepare the invocation. After that, the method is invoked. When it exits, the method context information is discarded using the value computed by the translated return bytecode. As an illustration of this mechanism, the translation of the invokevirtual bytecode is given in Table 6.

Another important feature of the Java language is the exception handling mechanism. An exception is raised by the athrow bytecode. A major constraint that the dynamic compilation should respect is to preserve exception handling semantics. The dynamic compilation introduces new issues relevant to exception propagation. Indeed, a compiled method could propagate an exception to an interpreted method. E-Bunny handles the following situations:

  • The method where the exception is thrown and the one where the exception is caught, are both interpreted: the original virtual machine exception handling mechanism is used.
  • The method where the exception is thrown, is interpreted and the one where the exception is caught is a compiled method. This case is excluded since the adopted profiling strategy assumes that a compiled method cannot invoke an interpreted one.
  • The method, where the exception is thrown, is a compiled method. There are two possible situations: the method catching the exception is either interpreted or compiled. In order to locate the method handling the exception, first, BCNativeMap is used to identify the bytecode corresponding to the native instruction throwing the exception. Then, an exception handler lookup is performed. If the method catching the exception (the method containing the handler) is a compiled one then its BCNativeMap is used to locate the native instruction corresponding to the bytecode handling the exception. A jump to this instruction is performed. Otherwise, we switch to the interpreted mode at the level of this bytecode.

Table 8: Interpreted to Native Switch Algorithm

The generated code for the athrow bytecode calls a specific function called throwExc. This function uses the virtual machine exception handling functionality to locate the exception handler. Then, it resumes the execution at the appropriate location. The translation of athrow is illustrated in Table 7.

Switch Mechanism

In E-Bunny, compiled methods are executed in the native stack while interpreted methods are interpreted in the Java stack located in the heap. Hence, execution of Java programs overlaps between native stack and Java stack. The switch between the two modes implies context transferring between the two stacks. We distinguish two situations where the switch occurs between the two modes: interpreted to native and native to interpreted.

The interpreted to native switch occurs when interpreting an invoke bytecode and the invoked method happens to be compiled. Coming from the interpretation mode, the called method arguments are on the top of the Java stack. The switch to the native mode requires their transfer to the native stack. This is carried out according to the algorithm in Table 8. The algorithm is based on the method frame layout in the native stack, depicted in Figure 3.

Figure 3: Switch Mechanism to the Native Mode

The switch from the native mode to the interpreted mode occurs in two situations. First, when a compiled method calls an interpreted method. Second, when a compiled method exits and returns back to its interpreted caller method. The pro- filing strategy we adopt assumes that every method called by a compiled method should be compiled. The switch is then reduced only to the second situation (return case). Handling this switch consists in transferring the returned value, if any, from the native stack to the Java stack. The implementation of this action depends on the returned value type as illustrated in Table 9.

Figure 3 shows the native stack in different phases of the switch. First, before method call (a). Second, after algorithm 1 (b). Third, when the translated called method exits (c). In (c), we assume that the called method returns a one word size value (e.g. integer, short, reference, etc.).

Threads Management

A Java virtual machine provides a framework to run properly different threads. Each thread has its own stack. In the interpreted mode, these stacks are created and managed at a software level. Basically, thread stacks are allocated in the heap. However, in E-Bunny, since two stacks are used, compiled methods have to be run on a native stack. Consequently, threads should use the native stack.

In the current implementation, the native stack is organized as a pool of segments. A segment is assigned to a thread when the latter is created. The segment pool management is based on a bit map. An entry of this map is a bit indicating whether the corresponding segment is used or free. Therefore, each thread executes its compiled methods in its own segment. A consequence of managing several threads with two stacks is that each thread has two forms of context information.

Table 9: Native to Interpreted Switch Algorithm

The first is relevant to Java stack (e.g. sp: stack pointer, fp: frame pointer, lp: locals pointer) and the second is relevant to the native stack (ESP, EBP and EIP registers). The data structure representing the thread in the virtual machine holds information representing both contexts (Figure 4).

Thread scheduling in the KVM is based on a round robin scheduling model. Each thread keeps control during a time-slice. This is decremented after each bytecode that may cause a control transfer (e.g. branching and invoke bytecodes). When the time-slice becomes zero, the virtual machine stops the current thread and resumes the next one in the running threads queue. Method compilation requires the support of thread scheduling. To achieve this purpose, additional code is generated for bytecodes causing transfer control. This code, mainly, decrements the ESI register, dedicated to hold time-slice value, and triggers a thread switch when ESI reaches the NULL value. In addition, a special care to save both contexts relevant to Java and native stacks, is taken.

Garbage Collection Issues

KVM garbage collection is based on a mark-sweep with compaction algorithm. With the selective approach of E-Bunny, compiled methods are executed on the native stack. Consequently, the native stack may contain some object references. Since the current garbage collection algorithm scans only the heap, the native stack will not be considered, and then, object references on it neither will be marked nor updated. Therefore, the current garbage collection algorithm is inefficient with a selective approach.

The garbage collection algorithm has to be extended to deal with the native stack. Precisely, translated method frames in native stack have to be scanned in order to mark and update object references. In E-Bunny, the garbage collection algorithm is enhanced to address this issue. Mainly, the garbage collection functionalities are modified to take into account the object references in the native stack. Indeed, for both marking and updating loops, we check if the frame corresponds to a compiled method or not. If the method is compiled we consider the native stack, otherwise we consider the Java stack.

Figure 4: Multi-threading in E-Bunny

5 IMPLEMENTATION AND RESULTS

E-Bunny is implemented using the C programming language. In our experiments, we used the GNU compiler to build the latest version of KVM (KVM 1.0.4) with E-Bunny. Table 10 shows the executable size of KVM with and without E-Bunny. The first column gives the total executable footprint of KVM without E-Bunny. The second column gives the total executable footprint of KVM equipped with EBunny dynamic compiler. Finally, column 3 of the table shows that using GCC to build KVM with E-Bunny produces a footprint overhead of 64 KB. To summarize, E-Bunny requires 64 KB for executable footprint overhead, 64 KB for storing translated methods and 10 KB for a map between bytecodes and native instructions which is used for compiling control flow instructions and for exception handling mechanism. Hence, the total memory resources required by E-Bunny dynamic compiler is 138 KB. To evaluate the performance of E-Bunny, we have run CaffeineMark benchmark
(without the float test) on the original version of KVM with and without E-Bunny.

E-Bunny produces an overall speedup of 4 over original KVM 1.0.4 (Overall score in Figure 5). Moreover, we built the MIDP 2.0 profile, intended to CLDC devices, using E-Bunny and we ran successfully several midlets. Figure 6 shows a snapshot of MIDP emulator illustrating CaffeineMark midlet results.

Table 10: Executable File Footprint overhead

Figure 5: CaffeineMark Scores of KVM 1.0.4 and E-Bunny with GCC

6 CONCLUSION AND FUTURE WORK

We reported, a new acceleration technology for Java embedded virtual machines that is based on selective dynamic compilation. This technology targets the J2ME/CLDC (Java 2 Micro Edition for Connected Limited Device Configuration) platform. We designed and implemented an efficient, lightweight and low-footprint accelerated embedded Java Virtual Machine. This has been achieved by the means of integrating a selective dynamic compiler, called E-Bunny, into the J2ME/CLDC virtual machine KVM. We presented the motivations, the architecture, the design as well as the technical issues of E-Bunny and how we addressed them. Experimental results demonstrated that we accomplished a speedup of 400% with respect to the Sun’s latest version of KVM.

Currently, many enhancements of E-Bunny are in progress. The major one concerns the bidirectional smooth switching between the interpreted and compiled modes. In fact, the profiling strategy adopted in the current version of E-Bunny, which consists in compiling each method called from the compiled one, is less complex to implement. However, it presents a drawback since it leads to compile nonperformance- critical methods. On the other hand, a more efficient centralized thread scheduling is being implemented. This is expected to reduce the generated native code size.

Figure 6: CaffeineMark midlet ran by KVM 1.0.4 and by E-Bunny


Footnotes

1 Execution overlaps between interpretation mode and native code execution mode.

2 The terms Intel stack and native stack are used interchangeably.

REFERENCES

[1] B. Alpern, C. Attanasio, J. Barton, M. Burke, P. Cheng, J. Choi, A. Cocchi, S. Fink, D. Grove, S. Hummel M. Hind, D. Lieber, V. Litvinov, M. Mergen, T. Ngo, J. Russell, V. Sarkar, M. Serrano, J. Shepherd, S. Smith, V. Sreedhar, H. Srinivasan, and J. Whaley. "The Jalapeño Virtual Machine". IBM Systems Journal, 39(1):211–238, February 2000.

[2] M. Cierniak, G. Lueh, and J. Stichnoth. "Practicing JUDO: Java under Dynamic Optimizations". In Proceedings of SIGPLAN 2000 Conference on Programming Languages Design and Implementation, pages 13–26, Vancouver, Canada, June 2000.

[3] G. Comeau. Java Companion Processors versus Accelerators. http://www.zucotto.com, 2002.

[4] Nazomi Communications. Boosting the performance of Java Software on Smart Handheld Devices and Internet Appliance. http://www.nazomi.com, April 2002.

[5] T. Cramer, R. Friedman, T. Miller, D. Seherger, R. Wilson, and M. Wolczko. "Compiling Java Just in Time". IEEE Micro, 17(3):36–43, 1997.

[6] E. Gagnon and L. Hendren. "Effective inline-threaded interpretation of java bytecode using preparation sequences". In Proceedings of Compiler Construction, 12th International Conference, CC 2003, Held as Part of the Joint Euro- pean Conferences on Theory and Practice of Software, ETAPS 2003, Warsaw, Poland, April 7-11, 2003, volume 2622 of Lecture Notes in Computer Science, pages 170–184. Springer-Verlag, 2003.

[7] C.-H. A. Hsieh, J. C. Gyllenhaal, and W. W. Hwu. "Java Bytecode to Native Code Translation: the Caffeine Prototype and Preliminary Results". In IEEE, editor, Proceedings of the 29th annual IEEE/ACM International Symposium on Microarchitecture, December 2-4, 1996, Paris, France. IEEE Computer Society Press, 1996.

[8] Intel. IA-32 Intel Architecture Software Developer’s Manual Volume 1: Basic Architecture. Intel Corporation, California, USA, order number 245470 edition, 2000.

[9] T. Lindholm and F. Yellin. The Java Virtual Machine Specification. Addison Wesley, 1996.

[10] S. M. Majercik and M. L. Littman. "Using Caching to Solve Larger Probabilistic Planning Problems". In Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98) and of the 10th Conference on Innovative Applications of Artificial Intelligence (IAAI-98), pages 954–960, Menlo Park, July 26–30 1998. AAAI Press.

[11] F. Maruyama. "OpenJIT 2: The Design and Implementation of Application Framework for JIT Compilers". In USENIX, editor, Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM’01): April 23–24, 2001, Monterey, California, USA. Berkeley, CA, Berkeley, CA, USA, 2001. USENIX.

[12] Sun MicroSystems. "The Java HotSpot Performance Engine Architecture". Technical report, Sun MicroSystems, California, USA, April 1999.

[13] Sun MicroSystems. "Connected, Limited Device Configuration. Specification Version 1.0, Java 2 Platform Micro Edition". Technical report, Sun MicroSystems, California, USA, May 2000.

[14] Sun MicroSystems. "KVM Porting Guide". Technical report, Sun MicroSystems, California, USA, September 2001.

[15] Sun MicroSystems. "CLDC HotSpot Implementation Virtual Machine". Technical report, Sun MicroSystems, California, USA, 2002.

[16] R. Radhakrishnan, N. Vijaykrishnan, L. John, A. Sivasubramaniam, J. Rubio, and J. Sabarinathan. "Java Runtime Systems: Characterization and Architectural Implications". IEEE Transactions on Computers, 50(2):131–146, 2001.

[17] K. Schmid. "Esmertec’s Jbed Micro Edition CLDC and Jbed Profile for MID". Technical report, Esmertec AG, Dubendorf, Switzerland, Spring 2002.

[18] N. Shaylor. "A Just-in-Time Compiler for Memory-Constrained Low-Power Devices". In Proceedings of the 2nd Java Virtual Machine Research and Technology Symposium, pages 119–126, San Francisco, CA, USA, August 2002.

[19] T. Suganuma, T. Ogasawara, M. Takeuchi, T. Yasue, M. Kawahito, K. Ishizaki, H. Komatsu, and T. Nakatani. "Overview of the IBM Java Just-in-Time Compiler". IBM Systems Journal, 39(1):175–193, 2000.

[20] T. Suganuma, T. Yasue, M. Kawahito, H. Komatsu, and T. Nakatani. A Dynamic "Optimization Framework for a Java Just-in-Time Compiler". ACM SIGPLAN Notices, 36(11):180–195, November 2001.

[21] B. Yang, S.M. Moon, S. Park, J. Lee, S. Lee, J. Park, Y.C. Chung, S. Kim, K. Ebcio?glu, and E. Altman. "LaTTe: A Java VM just-in-time compiler with fast and efficient register allocation". In Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques (PACT ’99), pages 128–138, Newport Beach, California, October 12–16, 1999. IEEE Computer Society Press.

 

About the authors



space

Mourad Debbabi holds Ph.D. and M.Sc. degrees in computer science from Paris-XI Orsay, University, France. He published more than 60 research papers in international journals and conferences on computer security, formal semantics, mobile and embedded platforms, Java technology security and acceleration, cryptographic protocol specification, design and analysis, malicious code detection, programming languages, type theory and specification and verifi- cation of safety-critical systems. He is a Full Professor and the Associate Director of the Concordia Institute for Information Systems Engineering, Concordia University, Montreal, Quebec, Canada. He is the Specification Lead of four Standard JAIN (Java Intelligent Networks) Java Specification Requests (JSRs) dedicated to the elaboration of standard specifications for presence and instant messaging through the Java Community Process (JCP) program. In the past, he served as Senior Scientist at the Panasonic Information and Network Technologies Laboratory, Princeton, New Jersey, USA; Associate Professor at the Computer Science Department of Laval University, Quebec, Canada; Senior Scientist at General Electric Research Center, New York, USA; Research Associate at the Computer Science Department of Stanford University, California, USA; and Permanent Researcher at the Bull Corporate Research Center, Paris, France. He can be reached at debbabi@ciise.concordia.ca. See also http://www.ciise.concordia.ca/~debbabi.



 

Abdelouahed Gherbi received his Engineering degree in Computer Engineering in 1992 and his Master degree in 1997, from the University of Constantine, Algeria. He is a Ph.D. student in the Electrical and Computer Engineering Department at Concordia University in Montreal. The main topic of his research activities is the acceleration of embedded Java virtual machines. He can be reached at gherbi@ciise.concordia.ca.



 

Lamia Ketari is a researcher at CSA (Computer Security and Acceleration) research group at Concordia Institute for Information Systems Engineering, Concordia University, Montreal, Quebec, Canada. She holds an MBA in Management Information Systems form Laval University. Currently, she is pursuing a Ph.D. thesis on the acceleration of Java for wireless devices and semantic-based optimization correctness. In the past, she worked on malicious code detection in COTS (Commercial Off-The-Shelf) applications. More specifically, she worked, with the collaboration of other research group members, on the implementation of a tool for monitoring critical system resources for malicious code detection, called: DaMon (Dynamic Analysis Monitoring). She can be reached at ketari@ciise.concordia.ca.



 

Chamseddine Talhi is a researcher at CSA (Computer Security and Acceleration) research group at Concordia Institute for Information Systems Engineering, Concordia University, Montreal, Quebec, Canada. He holds an M.Sc. degree from Constantine University, Algeria. He is pursuing a Ph.D. thesis on the security of embedded Java platforms. He is interested in characterizing enforceable security policies in resource-constrained platforms. In the past years, he worked on formal specification and verification of telecommunication services. He participated in the design and the implementation of a Java optimizing compiler for J2ME/CLDC. He can be reached at talhi@ciise.concordia.ca.



 

Nadia Tawbi holds a Ph.D and M.Sc. degrees from Pierre et Marie Curie University, Paris France. She was affiliated to Bull SA research center from 1989 to 1996. Since this year she joined the computer science department of Laval University where she is now an associate professor. Her research interests include static analysis of programs, optimization, object oriented languages, formal verification and security. She can be reached at Nadia.Tawbi@ift.ulaval.ca.



 

Hamdi Yahyaoui is a researcher at CSA (Computer Security and Acceleration) research group at Concordia Institute for Information Systems Engineering, Concordia University, Montreal, Quebec, Canada. He holds an M.Sc. degree from Laval University. He is pursuing a Ph.D. thesis on the acceleration and semantic foundations of embedded Java virtual machines. In the past years, he worked on formal dynamic semantics and control flow analysis of Java. He participated in the design and implementation of a dynamic optimizing compiler for J2ME/CLDC. He can be reached at hamdi@ciise.concordia.ca.

 

Sami Zhioua is a Ph.D. student at Concordia Institute for Information Systems Engineering, Concordia University, Montreal, Quebec, Canada. The main topic of his research activities is the acceleration of Java in the context of embedded systems. The goal of his research is to design and implement new techniques in order to improve the performance of embedded Java virtual machines. He participated in the design and implementation of a dynamic optimizing compiler for J2ME/CLDC. He can be reached at zhioua@ciise.concordia.ca.


Cite this article as follows: Mourad Debbabi et al: ”E-Bunny: A Dynamic Compiler for Embedded Java Virtual Machines”, in Journal of Object Technology, vol. 4, no. 1, January–February 2005, pages 83–108, http://www.jot.fm/issues/issue_2005_01/article2


Previous article

Next article