Partial evaluation allows specializing programs by substituting some of their inputs with static values and evaluating the resulting static expressions. When applied to a language interpreter, it specializes the interpreter to a fixed source program, resulting in a specialized interpreter that existing compilers can optimize and generate efficient machine code for. Although this approach achieves good peak performance in just-in-time compilers, partial evaluation is costly with respect to compilation time. In the case of bytecode interpreters, partial evaluation must process and transform each bytecode instruction. Since instructions with the same opcodes share common functionality, partial evaluation applies the same transformations repeatedly. Consequently, partial evaluation significantly increases the compilation time of just-in-time compilation.We propose partial-evaluation templates, i.e., reusable collections of ahead-of-time-compiled graphs that are generated by a hand-written cogen approach. The templates are parametric in their static inputs, and cover common functionality in a bytecode interpreter implementation. At compile time, templates specialize themselves by substituting their static inputs, reducing themselves to a single pre-compiled graph that the compiler inlines and optimizes. This reduces the size of the intermediate representation and speeds up partial evaluation, as well as optimizations.We integrated our approach into GraalVM, a state-of-the-art high-performance polyglot virtual machine, and GraalWasm, a bytecode-interpreter-based WebAssembly runtime. We extended the existing GraalVM compiler with a binding-time analysis that generates the templates and introduced a specializer for the templates into the existing partial evaluator. We enabled template generation for nearly all opcodes in GraalWasm, which reduced partial-evaluation time by up to 36 % and warmup time by up to 17 % without impacting peak performance.

Conditional constant propagation is a compiler optimization that detects and propagates constant values for expressions in the input program taking unreachable branches into account. It uses a data flow analysis that traverses the program’s control flow graph to discover instructions that produce constant values. In this paper we document our work to adapt conditional constant propagation to the Sea of Nodes program representation of GraalVM. In the Sea of Nodes, the program is represented as a graph in which most nodes ‘float’ and are only restricted by data flow edges. Classical data flow analysis is not possible in this setting because most operations are not ordered and not assigned to basic blocks. We present a novel approach to data flow analysis optimized for the Sea of Nodes. The analysis starts from known constant nodes in the graph and propagates information directly along data flow edges. Most nodes in the graph can never contribute new constants and are therefore never visited, a property we call lazy iteration. Dependences on control flow are taken into account by evaluating SSA φ nodes in a particular order according to a carefully defined priority metric. Our analysis is implemented in the GraalVM compiler. Experiments on the Renaissance benchmark suite show that lazy iteration only visits 20.5 % of all nodes in the graph. With the constants and unreachable branches found by our analysis, and previously undetected by the GraalVM compiler, we achieve an average speedup of 1.4 % over GraalVM’s optimized baseline.

Language interoperability (e.g., calling Python methods from Java programs) is a critical challenge in software development, often leading to code inconsistencies, human errors, and reduced readability.

Picking the right data structure for the right job is one of the key challenges for every developer. However, especially in the realm of object-oriented programming, the memory layout of data structures is often still suboptimal for certain data access patterns, due to objects being scattered across the heap. Therefore, this work presents an approach for the automated transformation of arrays of objects into a contiguous format (called columnar arrays). At run time, we identify suitable arrays, perform the transformation and use a dynamic compiler to gain performance improvements. In the evaluation, we show that our approach can improve the performance of certain queries over large, uniform arrays.

Dynamic taint analysis assigns taint labels to sensitive data and tracks the propagation of such tainted data during program execution. This program analysis technique has been implemented in various analysis platforms targeting specific programming languages or program representations and has been applied to diverse fields such as software security and debugging. While some of these platforms support customization of their taint analysis, such customization is typically limited to certain analysis properties or to predefined options. This limitation can require analysis developers to modify the analysis platform in order to adapt other analysis properties or to implement new taint analysis applications.

Dynamic taint analysis is a popular analysis technique which tracks the propagation of specific values while a program executes. To this end, a taint label is attached to these values and is dynamically propagated to any values derived from them. Frequent application of this analysis technique in many fields has led to the development of general-purpose analysis platforms with taint propagation capabilities. However, these platforms generally limit analysis developers to a specific implementation language, to specific propagation semantics or to specific taint label representations.

Today’s huge memories make it possible to store and process large data structures in memory instead of in a database. Hence, accesses to this data should be optimized, which is normally relegated either to the runtimes and compilers or is left to the developers, who often lack the knowledge about optimization strategies. As arrays are often part of the language, developers frequently use them as an underlying storage mechanism. Thus, optimization of arrays may be vital to improve performance of data-intensive applications. While compilers can apply numerous optimizations to speed up accesses, it would also be beneficial to adapt the actual layout of the data in memory to improve cache utilization. However, runtimes and compilers typically do not perform such memory layout optimizations. In this work, we present an approach to dynamically perform memory layout optimizations on arrays of objects to transform them into a columnar memory layout, a storage layout frequently used in analytical applications that enables faster processing of read-intensive workloads. By integration into a state-of-the-art JavaScript runtime, our approach can speed up queries for large workloads by up to 9x, where the initial transformation overhead is amortized over time.

Compiler optimizations are often based on hand-crafted heuristics to guide the optimization process. These heuristics are designed to benefit the average program and are otherwise static or only customized by profiling information. We propose machine-learning-based self-optimizing compiler heuristics, a novel approach for fitting optimization decisions in a dynamic compiler to specific environments. This is done by updating a machine learning model with extracted performance data at run time. Related work—which primarily targets static compilers—has already shown that machine learning can outperform hand-crafted heuristics. Our approach is specifically designed for dynamic compilation and uses concepts such as deoptimization for transparently switching between generating data and performing machine learning decisions in single program runs. We implemented our approach in the GraalVM, a high-performance production VM for dynamic compilation. When evaluating our approach by replacing loop peeling heuristics with learned models we encountered speedups larger than 30% for several benchmarks and only few slowdowns of up to 7%.

The first Futamura projection enables compilation and high performance code generation of user programs by partial evaluation of language interpreters. Previous work has shown that online partial evaluation can yield the same peak performance as a specialized JIT compiler. However, this comes with the downside of additional compile time: Online partial evaluation of language interpreters has to specialize interpreter code on the fly to the dynamic types used at run time to create efficient target code. As a result, the time spent on partial evaluation itself is a significant contributor to the overall compile time of a method.

Companies need to collect and analyze time series data to continuously monitor the behavior of software systems during operation, which can in turn be used for performance monitoring, anomaly detection or identifying problems after system crashes. However, gaining insights into common data patterns in time series is challenging, in particular, when analyzing data concerning different properties and from multiple systems. Clustering approaches have been hardly studied in the context of monitoring data, despite their possible benefits. In this paper, we present a feature-based approach to identify clusters in unlabeled infrastructure monitoring data collected from multiple independent software systems. We introduce time series properties which are grouped into feature sets and combine them with various unsupervised machine learning models to find the methods best suited for our clustering goal. We thoroughly evaluate our approach using two large-scale, industrial monitoring datasets. Finally, we apply one of the top-ranked methods to thousands of time series from hundreds of software systems, thereby showing the usefulness of our approach.

Dynamic taint analysis (DTA) is a popular program analysis technique with applications to diverse fields such as software vulnerability detection and reverse engineering. It consists of marking sensitive data as tainted and tracking its propagation at runtime. While DTA has been implemented on top of many different analysis platforms, these implementations generally incur significant slowdown from taint propagation. Since a purely dynamic analysis cannot predict which instructions will operate on tainted values at runtime, programs have to be fully instrumented for taint propagation even when they never actually observe tainted values. We propose leveraging speculative optimizations to reduce slowdown on the peak performance of programs instrumented for DTA on a managed runtime capable of dynamic compilation.

Code duplication is a major opportunity to enable optimizations in subsequent compiler phases. However, duplicating code prematurely or too liberally can result in tremendous code size increases. Thus, modern compilers use trade-offs between estimated costs in terms of code size increase and benefits in terms of performance increase. In the context of this ongoing research project, we propose the use of machine learning to provide trade-off functions with accurate predictions for code size impact. To evaluate our approach, we implemented a neural network predictor in the GraalVM compiler and compared its performance against a human-crafted, highly tuned heuristic. First results show promising performance improvements, leading to code size reductions of more than 10% for several benchmarks. Additionally, we present an assistance mode for finding flaws in the human-crafted heuristic, leading to improvements for the duplication optimization itself.

Programmers can use various data types when developing software. However, if the program is compiled to machine code, most of this type information is lost. If analysis of a compiled program is necessary, the lost data types have to be recovered again, to make the code understandable. Existing approaches for the type recovery problem require detailed knowledge about the CPU architecture in question. An architecture-agnostic approach is missing so far.

Many monitoring tools that help developers in analyzing the run-time behavior of their applications share a common shortcoming: they require their users to have a fair amount of experience in monitoring applications to understand the used terminology and the available analysis features. Consequently, novice users who lack this knowledge often struggle to use these tools efficiently. In this paper, we introduce the guided exploration (GE) method that aims to make interactive monitoring tools easier to use and learn. In general, tools that implement GE should provide four support operations on each analysis step: they should automatically (1) detect and (2) highlight the most important information on the screen, (3) explain why it is important, and (4) suggest which next steps are appropriate. This way, tools guide users through their analysis processes, helping them to explore the root cause of a problem. At the same time, users learn the capabilities of the tool and how to use them efficiently. We show how GE can be implemented in new monitoring tools as well as how it can be integrated into existing ones. To demonstrate GE's feasibility and usefulness, we present how we extended the memory monitoring tool AntTracks to provided guided exploration support during memory leak analysis and memory churn analysis. We use these guidances in two user scenarios to inspect and improve the memory behavior of the monitored applications. We hope that our contribution will help usability researchers and developers in making monitoring tools more novice-friendly by improving their usability and learnability.

Developing software systems is inherently subject to errors that can later cause failures in production. While testing can help to identify critical issues, it is limited to concrete inputs and states. Exhaustive testing is infeasible in practice; hence we can never prove the absence of faults. Symbolic execution, i.e., the process of symbolically reasoning about the program state during execution, can inspect the behavior of a system under all possible concrete inputs at run time. It automatically generates logical constraints that match the program semantics and uses theorem provers to verify the existence of error states within the application. This paper presents a novel symbolic execution engine called SymJEx, implemented on top of the multi-language Java Virtual Machine GraalVM. SymJEx uses the Graal compiler's intermediate representation to derive and evaluate path conditions, allowing GraalVM users to leverage the engine to improve software quality. In this work, we show how SymJEx finds non-trivial faults in existing software systems and compare our approach with established symbolic execution engines.

Dynamic taint analysis is a popular program analysis technique in which sensitive data is marked as tainted and the propagation of tainted data is tracked in order to determine whether that data reaches critical program locations. This analysis technique has been successfully applied to software vulnerability detection, malware analysis, testing and debugging, and many other fields. However, existing approaches of dynamic taint analysis are either language-specific or they target native code. Neither is suitable for analyzing applications in which high-level dynamic languages such as JavaScript and low-level languages such as C interact.In these approaches, the language boundary forms an opaque barrier that prevents a sound analysis of data flow in the other language and can thus lead to the analysis being evaded.

Debuggers are traditionally used to investigate and observe the dynamic behavior of software. Reverse debuggers record a program execution and provide a method to step through the program forward and backward, to quickly locate the operation of interest. However, recording based approaches usually assume a specific method of recording the program execution. Furthermore, the recording and analysis is often linked in a certain way, so that it is not trivial, to quickly add support for new architectures or other recording tools.

Tool support is essential to help developers in understanding the memory behavior of complex software systems. Anomalies such as memory leaks can dramatically impact application performance and can even lead to crashes. Unfortunately, most memory analysis tools lack advanced visualizations (especially of the memory evolution over time) that could facilitate developers in analyzing suspicious memory behavior.In this paper, we present Memory Cities, a technique to visualize an application's heap memory evolution over time using the software city metaphor. While this metaphor is typically used to visualize static artifacts of a software system such as class hierarchies, we use it to visualize the dynamic memory behavior of an application. In our approach, heap objects can be grouped by multiple properties such as their types or their allocation sites. The resulting object groups are visualized as buildings arranged in districts, where the size of a building corresponds to the number of heap objects or bytes it represents. Continuously updating the city over time creates the immersive feeling of an evolving city. This can be used to detect and analyze memory leaks, i.e., to search for suspicious growth behavior. Memory cities further utilize various visual attributes to ease this task. For example, they highlight strongly growing buildings using color, while making less suspicious buildings semi-transparent.We implemented memory cities as a standalone application developed in Unity, with a JSON-based interface to ensure easy data import from external tools. We show how memory cites can use data provided by AntTracks, a trace-based memory monitoring tool, and present case studies on different applications to demonstrate the tool's applicability and feasibility.

The actor model is popular for many types of server applications. Efficient snapshotting of applications is crucial in the deployment of pre-initialized applications or moving running applications to different machines, e.g for debugging purposes. A key issue is that snapshotting blocks all other operations. In modern latency-sensitive applications, stopping the application to persist its state needs to be avoided, because users may not tolerate the increased request latency. In order to minimize the impact of snapshotting on request latency, our approach persists the application’s state asynchronously by capturing partial heaps, completing snapshots step by step. Additionally, our solution is transparent and supports arbitrary object graphs. We prototyped our snapshotting approach on top of the Truffle/Graal platform and evaluated it with the Savina benchmarks and the Acme Air microservice application. When performing a snapshot every thousand Acme Air requests, the number of slow requests ( 0.007% of all requests) with latency above 100ms increases by 5.43%. Our Savina microbenchmark results detail how different utilization patterns impact snapshotting cost. To the best of our knowledge, this is the first system that enables asynchronous snapshotting of actor applications, i.e. without stop-the-world synchronization, and thereby minimizes the impact on latency. We thus believe it enables new deployment and debugging options for actor systems.

Dynamic taint analysis is a program analysis technique in which data is marked and its propagation is tracked while the program is executing. It is applied to solve problems in many fields, especially in software security. Current taint analysis platforms are limited to a single programming language, and therefore cannot support programs which, as is common today, are implemented in multiple programming languages. Current implementations of dynamic taint analysis also incur a significant performance overhead.

On-stack replacement (OSR) is a common technique employed by dynamic compilers to reduce program warm-up time. OSR allows switching from interpreted to compiled code during the execution of this code. The main targets are long running loops, which need to be represented explicitly, with dedicated information about condition and body, to be optimized at run time. Bytecode interpreters, however, represent control flow implicitly via unstructured jumps and thus do not exhibit the required high-level loop representation. To enable OSR also for jump-based - often called unstructured - languages, we propose the partial reconstruction of loops in order to explicitly represent them in a bytecode interpreter. Besides an outline of the general idea, we implemented our approach in Sulong, a bytecode interpreter for LLVM bitcode, which allows the execution of C/C++. We conducted an evaluation with a set of C benchmarks, which showed speed-ups in warm-up of up to 9x for certain benchmarks. This facilitates execution of programs with long-running loops in rarely called functions, which would yield significant slowdown without OSR. While shown with a prototype implementation, the overall idea of our approach is generalizable for all bytecode interpreters.

Modern memory monitoring tools do not only offer analyses at a single point in time, but also offer features to analyze the memory evolution over time. These features provide more detailed insights into an application's behavior, yet they also make the tools more complex and harder to use.

C programs can use compiler builtins to provide functionality that the C language lacks. On Linux, GCC provides several thousands of builtins that are also supported by other mature compilers, such as Clang and ICC. Maintainers of other tools lack guidance on whether and which builtins should be implemented to support popular projects. To assist tool developers who want to support GCC builtins, we analyzed builtin use in 4,913 C projects from GitHub. We found that 37% of these projects relied on at least one builtin. Supporting an increasing proportion of projects requires support of an exponentially increasing number of builtins; however, implementing only 10 builtins already covers over 30% of the projects. Since we found that many builtins in our corpus remained unused, the effort needed to support 90% of the projects is moderate, requiring about 110 builtins to be implemented. For each project, we analyzed the evolution of builtin use over time and found that the majority of projects mostly added builtins. This suggests that builtins are not a legacy feature and must be supported in future tools. Systematic testing of builtin support in existing tools revealed that many lacked support for builtins either partially or completely; we also discovered incorrect implementations in various tools, including the formally verified CompCert compiler.

Memory leaks are a major threat in modern software systems. They occur if objects are unintentionally kept alive longer than necessary and are often indicated by continuously growing data structures.

In C, memory errors, such as buffer overflows, are among the most dangerous software errors; as we show, they are still on the rise. Current dynamic bug-finding tools that try to detect such errors are based on the low-level execution model of the underlying machine. They insert additional checks in an ad-hoc fashion, which makes them prone to omitting checks for corner cases. To address this, we devised a novel approach to finding bugs during the execution of a program. At the core of this approach is an interpreter written in a high-level language that performs automatic checks (such as bounds, NULL, and type checks). By mapping data structures in C to those of the high-level language, accesses are automatically checked and bugs discovered. We have implemented this approach and show that our tool (called Safe Sulong) can find bugs that state-of-the-art tools overlook, such as out-of-bounds accesses to the main function arguments.

Compilers perform a variety of advanced optimizations to improve the quality of the generated machine code. However, optimizations that depend on the data flow of a program are often limited by control-flow merges. Code duplication can solve this problem by hoisting, i.e. duplicating, instructions from merge blocks to their predecessors. However, finding optimization opportunities enabled by duplication is a non-trivial task that requires compile-time intensive analysis. This imposes a challenge on modern (just-in-time) compilers: Duplicating instructions tentatively at every control flow merge is not feasible because excessive duplication leads to uncontrolled code growth and compile time increases. Therefore, compilers need to find out whether a duplication is beneficial enough to be performed.

Faults are common in large software systems and must be analyzed to prevent future failures such as system outages. Due to their sheer amount, the observed failures cannot be inspected individually but must be automatically grouped and prioritized. An open challenge is to find similarities in failures across different systems. We propose a novel approach for identifying error-prone software technologies via a cross-system analysis based on monitoring and crash data. Our approach ranks the error-prone software technologies and analyzes the occurred exceptions, thus making it easier for developers to investigate cross-system failures. Finding such failures is highly advantageous as fixing a fault may benefit many affected systems. A preliminary case study on monitoring data of hundreds of different systems demonstrates the feasibility of our approach.

C codebases frequently embed nonportable and unstandardized elements such as inline assembly code. Such elements are not well understood, which poses a problem to tool developers who aspire to support C code. This paper investigates the use of x86-64 inline assembly in 1264 C projects from GitHub and combines qualitative and quantitative analyses to answer questions that tool authors may have. We found that 28.1% of the most popular projects contain inline assembly code, although the majority contain only a few fragments with just one or two instructions. The most popular instructions constitute a small subset concerned largely with multicore semantics, performance optimization, and hardware control. Our findings are intended to help developers of C-focused tools, those testing compilers, and language designers seeking to reduce the reliance on inline assembly. They may also aid the design of tools focused on inline assembly itself.

Software becomes more and more complex. Performance degradations and anomalies can often only be understood by using monitoring approaches, e.g., for tracing the allocations and lifetimes of objects on the heap. However, this leads to huge amounts of data that have to be classified, grouped and visualized in order to be useful for developers. In this paper, we present a flexible offline memory analysis approach that allows classifying heap objects based on arbitrary criteria. A small set of predefined classification criteria such as the type and the allocation site of an object can further be extended by additional user-defined criteria. In contrast to state-of-the-art tools, which group objects based on a single criterion, our approach allows the combination of multiple criteria using multi-level grouping. The resulting classification trees allow a flexible in-depth analysis of the data and a natural hierarchical visualization of the results.

Dynamic programming languages such as Python and Ruby are widely used, and much effort is spent on making them efficient. One substantial research effort in this direction is the enabling of parallel code execution. While there has been significant progress, making dynamic collections efficient, scalable, and thread-safe is an open issue. Typical programs in dynamic languages use few but versatile collection types. Such collections are an important ingredient of dynamic environments, but are difficult to make safe, efficient, and scalable. In this paper, we propose an approach for efficient and concurrent collections by gradually increasing synchronization levels according to the dynamic needs of each collection instance. Collections reachable only by a single thread have no synchronization, arrays accessed in bounds have minimal synchronization, and for the general case, we adopt the Layout Lock paradigm and extend its design with a lightweight version that fits the setting of dynamic languages. We apply our approach to Ruby's Array and Hash collections. Our experiments show that our approach has no overhead on single-threaded benchmarks, scales linearly for Array and Hash accesses, achieves the same scalability as Fortran and Java for classic parallel algorithms, and scales better than other Ruby implementations on Ruby workloads.

Today's complex software systems combine high-level concurrency models. Each model is used to solve a specific set of problems. Unfortunately, debuggers support only the low-level notions of threads and shared memory, forcing developers to reason about these notions instead of the high-level concurrency models they chose.

Efficiently tracking an application's object allocations is of interest for areas such as memory leak detection or memory usage optimization. The state-of-the-art approach of instrumenting every allocation site with a counter introduces considerable overhead. This makes allocation tracking in a production environment unattractive. Our approach reduces this overhead by instrumenting control flow paths instead of allocation sites and dynamically determining the hot path through a method. Our ultimate goal is to reduce the amount of required counter increments by such a degree that using it in production environments becomes feasible. We present an implementation of our approach for the Java HotSpot Virtual Machine. First measurements already show a reduction of required increments of up to 30% compared to the state of the art.

Benchmark suites are an indispensable part of scientific research to compare different approaches against each another. The diversity of benchmarks is an important asset to evaluate novel approaches for effectiveness and weaknesses. In this paper, we describe the memory characteristics and the GC behavior of commonly used Java benchmarks, i.e., the DaCapo benchmark suite, the DaCapo Scala benchmark suite and the SPECjvm2008 benchmark suite. The paper can serve as a useful guide to select benchmarks in accordance with desired application characteristics on modern virtual machines as well as with different compilers and garbage collectors. It also helps to put results that are based on these benchmarks into perspective. Additionally, we compare Java's current default collector to the G1 GC.

Concurrent code commonly uses locks. Choosing between simpler but less scalable and more sophisticated but error-prone locking mechanisms is difficult during development. Therefore, lock contention analysis at run-time is crucial to aid such decisions.

State-of-the-art memory monitoring tools collect lots of raw data. Yet, the analysis of this data is often not well supported. Existing tools restrict the user in the way how to analyze the underlying data, how to process it, and how to visualize it. This results in the dilemma that the raw data often contains more information than what can be exploited. We present a novel user-centric approach, allowing custom offline analysis and visualization of memory monitoring data by employing user-defined classification on heap objects. Putting the user in the center of the analysis process and providing flexible query and classification interfaces can change the way how we monitor memory usage. Our goal is to turn special-purpose memory monitoring tools into more general and customizable tools.

Comparing the performance of programming languages is difficult because they differ in many aspects including preferred programming abstractions, available frameworks, and their runtime systems. Nonetheless, the question about relative performance comes up repeatedly in the research community, industry, and wider audience of enthusiasts.

We are in the multi-core era. Dynamically-typed languages are in widespread use, but their support for multithreading still lags behind. One of the reasons is that the sophisticated techniques they use to efficiently represent their dynamic object models are often unsafe in multithreaded environments.

Concurrent programming has become a necessity in order to benefit from recent advances in processor design. However, implementing correct and scalable locking for accessing shared resources remains a challenge. Examining lock contention in an application at runtime is vital to determine where more sophisticated but error-prone locking pays off. In this paper, we present a novel approach for analyzing lock contention in Java applications by tracing locking events in the Java Virtual Machine. Unlike common methods, our approach observes not only when a thread is blocked on a lock, but also which other thread blocked it by holding that lock, and records both their call chains. This reveals the causes of lock contention instead of showing only its symptoms. We describe the techniques which we use to efficiently record trace events, metadata, and call chains. We present a versatile tool for the analysis of the traces which enables users to identify locking bottlenecks and their characteristics in an effective way. We implemented our approach in the widely used HotSpot Virtual Machine, and with a mean runtime overhead of 7.8%, we consider it efficient enough to monitor production systems.

Understanding and tracking down memory-related performance problems is a tedious task, especially when it involves automatically managed memory, i.e., garbage collection. A multitude of monitoring tools show the substantial need of developers to deal with these problems efficiently. Unfortunately, state-of-the-art tools either generate an inscrutable amount of trace data or produce only a coarse-grained view of the application's memory behavior. While the first approach generates information that is very detailed albeit difficult to handle, the second approach is more efficient but may fail to provide vital information.

Programmers combine different programming languages because it allows them to use the most suitable language for a given problem, to gradually migrate existing projects from one language to another, or to reuse existing source code. However, existing cross-language mechanisms suffer from complex interfaces, insufficient flexibility, or poor performance. We present the TruffleVM, a multi-language runtime that allows composing different language implementations in a seamless way. It reduces the amount of required boiler-plate code to a minimum by allowing programmers to access foreign functions or objects by using the notation of the host language. We compose language implementations that translate source code to an intermediate representation (IR), which is executed on top of a shared runtime system. Language implementations use language-independent messages that the runtime resolves at their first execution by transforming them to efficient foreign-language-specific operations. The TruffleVM avoids conversion or marshaling of foreign objects at the language boundary and allows the dynamic compiler to perform its optimizations across language boundaries, which guarantees high performance. This paper presents an implementation of our ideas based on the Truffle system and its guest language implementations JavaScript, Ruby, and C.

We present an approach to cross-compile Java bytecodes to Java-Script, building on existing Java optimizing compiler technology. Static analysis determines which Java classes and methods are reachable. These are then translated to JavaScript using a re-configured Java just-in-time compiler with a new back end that generates JavaScript instead of machine code. Standard compiler optimizations such as method inlining and global value numbering, as well as advanced optimizations such as escape analysis, lead to compact and optimized JavaScript code. Compiler IR is unstructured, so structured control flow needs to be reconstructed before code generation is possible. We present details of our control flow reconstruction algorithm. Our system is based on Graal, an open-source optimizing compiler for the Java HotSpot VM and other VMs. The modular and VM-independent architecture of Graal allows us to reuse the intermediate representation, the bytecode parser, and the high-level optimizations. Our custom back end first performs control flow reconstruction and then JavaScript code generation. The generated JavaScript undergoes a set of optimizations to increase readability and performance. Static analysis is performed on the Graal intermediate representation as well. Benchmark results for medium-sized Java benchmarks such as SPECjbb2005 run with acceptable performance on the V8 JavaScript VM.

Sampling profilers are popular because of their low and adjustable overhead and because they do not distort the profile by modifying the application code. A typical sampling profiler periodically suspends the application threads, walks their stacks, and merges the resulting stack traces into a calling context tree. Java virtual machines offer a convenient interface to accomplish this, but rely on safepoints, a synchronization mechanism that requires all threads to park in a safe location. However, a profiler is primarily interested in the running threads, and waiting for all threads to reach a safe location significantly increases the overhead. In most cases, taking a complete stack trace is also unnecessary because many stack frames remain unchanged between samples.

Virtualization enables the efficient sharing of hardware resources among multiple virtual machines (VMs). Because the physical resources are limited, the scheduler must often suspend one VM to allow some other VM to run. The operating system in a VM is typically unaware of the suspension and accounts periods of suspension as CPU time to the executing application thread. This misrepresentation of resource usage makes it difficult to tell whether a performance problem is caused by an actual bottleneck in the application or by the virtualization infrastructure. We present a novel approach to compute to what degree the threads of an application in a virtual machine are affected by suspension. Our approach does not require any modifications to the operating system or to the virtualization software. It periodically samples the system-wide amount of "steal time" that is reported by the virtualization infrastructure, and divides it among the monitored threads according to their CPU usage. With a prototype implementation, we demonstrate that our approach accounts accurate amounts of steal time to application threads, that it can be used to compute the true resource usage of an application, and that it incurs only negligible performance overhead.

Object allocations and garbage collection can have a considerable impact on the performance of Java applications. Without monitoring tools, such performance problems are hard to track down, and if such tools are applied, they often cause a significant overhead and tend to distort the behavior of the monitored application. In this paper we present a new light-weight memory monitoring approach in which we trace allocations, deallocations and movements of objects using VM-specific knowledge. We strive for utmost compactness of the trace by using a binary format with optimized encodings for different cases of memory events and by omitting all information that can be reconstructed offline when the trace is processed.

Sampling is a popular approach to collecting data for profiling and monitoring, because it has a small impact on performance and does not modify the observed application. When sampling stack traces, they can be merged into a calling context tree that shows where the application spends its time and where performance problems lie. However, Java VM implementations usually rely on safepoints for sampling stack traces. Safepoints can cause inaccuracies and have a considerable performance impact. We present a new approach that does not use safepoints, but instead relies on the operating system to take snapshots of the stack at arbitrary points. These snapshots are then asynchronously decoded to call traces, which are merged into a calling context tree. We show that we are able to decode over 90% of the snapshots, and that our approach has very small impact on performance even at high sampling rates.

Garbage collection, if not tuned properly, can considerably impact application performance. Unfortunately, configuring a garbage collector is a tedious task as only few guidelines exist and tuning is often done by trial and error. We present what is, to our knowledge, the first published work on automatically tuning Java garbage collectors in a black-box manner considering all available parameters. We propose the use of iterated local search methods to automatically compute application-specific garbage collector configurations. Our experiments show that automatic tuning can reduce garbage collection time by up to 77% for a specific application and a specific workload and by 35% on average across all benchmarks (compared to the default configuration). We evaluated our approach for 3 different garbage collectors on the DaCapo and SPECjbb benchmarks, as well as on a real-world industrial application.

Trace-based Just-In-Time (JIT) compilation generates machine code for frequently executed paths (so-called traces) instead of whole methods. While this has several advantages, it complicates invocation of compiled traces as well as exception handling, so that previous trace-based compilers limited the way in which traces could be invoked. We present a significantly enhanced trace-based compiler where arbitrary transitions between interpreted and compiled traces are possible. For that, we introduce suitable trace calling conventions and extend exception handling to work both within traces and across trace boundaries. Furthermore, we use the recorded trace information for optimizations and combine the tracing ideas with ideas from partial-method compilation to avoid code bloat. An extensive evaluation with the benchmark suites DaCapo 9.12 Bach and SPECjvm2008 shows that our trace-based compiler achieves up to 59% higher peak performance than the method-based Java HotSpot client compiler. On a few benchmarks, our fairly simple trace-based compiler shows a higher peak performance than the Java HotSpot server compiler, which is one of today's best optimizing JIT compilers for Java.

Method inlining is one of the most important optimizations in method-based just-in-time (JIT) compilers. It widens the compilation scope and therefore allows optimizing multiple methods as a whole, which increases the performance. However, if method inlining is used too frequently, the compilation time increases and too much machine code is generated. This has negative effects on the performance. Trace-based JIT compilers only compile frequently executed paths, so-called traces, instead of whole methods. This may result in faster compilation, less generated machine code, and better optimized machine code. In the previous work, we implemented a trace recording infrastructure and a trace-based compiler for [Formula: see text], by modifying the Java HotSpot VM. Based on this work, we evaluate the effect of trace inlining on the performance and the amount of generated machine code. Trace inlining has several major advantages when compared to method inlining. First, trace inlining is more selective than method inlining, because only frequently executed paths are inlined. Second, the recorded traces may capture information about virtual calls, which simplify inlining. A third advantage is that trace information is context sensitive so that different method parts can be inlined depending on the specific call site. These advantages allow more aggressive inlining while the amount of generated machine code is still reasonable. We evaluate several inlining heuristics on the benchmark suites DaCapo 9.12 Bach, SPECjbb2005, and SPECjvm2008 and show that our trace-based compiler achieves an up to 51% higher peak performance than the method-based Java HotSpot client compiler. Furthermore, we show that the large compilation scope of our trace-based compiler has a positive effect on other compiler optimizations such as constant folding or null check elimination.

Dynamic updates to running programs improve development productivity and reduce downtime of long-running applications. This feature is however severely limited in current virtual machines for object-oriented languages. In particular, changes to classes often apply only to methods invoked after a class change, but not to active methods on the call stack of threads. Additionally, adding and removing methods as well as fields is often not supported.

Deterministic replay debugging is an approach to finding bugs in deployed software. It records an application run in the field so that it can deterministically be replayed offline in a development system for debugging purposes. To enable deterministic replay debugging, it is necessary to record all external influences and sources of nondeterminism in the original program run. From that trace log and from a known initial state, the program can be replayed deterministically without requiring any connection to the original environment. In this paper, we present a solution for deterministic replay debugging of hard real-time multitasking SoftPLC applications written in the IEC 61131-3 languages. By taking advantage of the special properties of these programs and by careful engineering, our technique allows recording a SoftPLC application run in the field with minimal overhead and obeying real-time constraints. In later phases, which are offline, the original program run is reconstructed from the minimal information recorded so it can be replayed for debugging. In comparison to previous work, our solution has several advantages: Instead of recording task scheduling information, it reconstructs the task interleaving based on data dependencies, thereby significantly simplifying the recording phase. Additionally, it incorporates a technique for periodically capturing the complete internal state of the system, which can later be used as a starting point for replay. We present the conceptual basis of our approach, a tool chain which provides deterministic replay debugging to the user as a set of fully automated tools, and an evaluation as well as an industrial case study for validating the approach.

Plug-in frameworks facilitate the development of customizable and extensible software, yet they often lack support for flexible and dynamic (re)configuration. We have created Plux.NET, a novel plug-in framework for plug-and-play composition. In Plux, a composer replaces programmatic composition with automatic composition. Components just specify their requirements and provisions using metadata, and the composer assembles the components guided by that metadata. This paper introduces rule-based composition behaviors, which are a means for controlling the composition process declaratively. Behavior rules constrain the composer by preventing certain operations or by triggering new ones. They help to establish a rule conformant composition state. Thereby, Plux supports developers in declarative and rule-based composition in order to minimize programming effort.

Plug-in components are a means for making feature-rich applications customizable. Combined with plug-and-play composition, end users can assemble customized applica-tions without programming. If plug-and-play composition is also dynamic, applications can be reconfigured on the fly to load only components the user needs for his current work. We have created Plux.NET, a plug-in framework that supports dynamic plug-and-play composition. The basis for plug-and-play in Plux is the composer which replaces pro-grammatic composition by automatic composition. Compo-nents just specify their requirements and provisions using metadata. The composer then assembles the components based on that metadata by matching requirements and pro-visions. When the composer needs to reuse general-purpose components in different parts of an application, the compo-nent model requires genericity. The composer depends on metadata that specify which components should be connected and for general-purpose components those meta-data need to be different on each reuse. We present an ap-proach for generic plug-ins with component templates and an implementation for Plux. The general-purpose compo-nents become templates and the templates get parameter-ized when they are composed.

While dynamic code evolution in object-oriented systems is an important feature supported by dynamic languages, there is currently only limited support for dynamic code evolution in high-performance, state-of-the-art runtime systems for statically typed languages, such as the Java Virtual Machine. In this tool demonstration, we present the Dynamic Code Evolution VM, which is based on a recent version of Oracle's state-of-the-art Java HotSpot(TM) VM and allows unlimited changes to loaded classes at runtime. Based on the Dynamic Code Evolution VM, we developed an enhanced version of the Mantisse GUI builder (which is part of the NetBeans IDE) that allows adding GUI components without restarting the application under development. Furthermore, we redesigned the dynamic AOP framework HotWave to take advantage of the enhanced dynamic code evolution capabilities. The new version, HotWave2, now supports most AspectJ constructs, including around() advice and static cross-cutting. We will demonstrate both the enhanced Mantisse GUI builder as well as HotWave2, weaving several aspects for dynamic analysis in sizable applications at runtime.

Object fusing is an optimization that embeds certain referenced objects into their referencing object. The order of objects on the heap is changed in such a way that objects that are accessed together are placed next to each other in memory. Their offset is then fixed, that is, the objects are colocated, allowing field loads to be replaced by address arithmetic. Array fusing specifically optimizes arrays, which are frequently used for the implementation of dynamic data structures. Therefore, the length of arrays often varies, and fields referencing such arrays have to be changed. An efficient code pattern detects these changes and allows the optimized access of such fields. We integrated these optimizations into Sun Microsystems' Java HotSpot™ VM. The analysis is performed automatically at runtime, requires no actions on the part of the programmer, and supports dynamic class loading. To safely eliminate a field load, the colocation of the object that holds the field and the object that is referenced by the field must be guaranteed. Two preconditions must be satisfied: The objects must be allocated at the same time, and the field must not be overwritten later. These preconditions are checked by the just-in-time compiler to avoid an interprocedural data flow analysis. The garbage collector ensures that groups of colocated objects are not split by copying groups as a whole. The evaluation shows that the dynamic approach successfully identifies and optimizes frequently accessed fields for several benchmarks with a low compilation and analysis overhead. It leads to a speedup of up to 76% for simple benchmarks and up to 6% for complex workloads.

Array inlining expands the concepts of object inlining to arrays. Groups of objects and arrays that reference each other are placed consecutively in memory so that their relative offsets are fixed, i.e. they are colocated. This allows memory loads to be replaced by address arithmetic, which reduces the costs of field and array accesses. We implemented this optimization for Sun Microsystems' Java HotSpot VM. The optimization is performed automatically and requires no actions on the part of the programmer.

Version 6 of Sun Microsystems' Java HotSpot™ VM ships with a redesigned version of the client just-in-time compiler that includes several research results of the last years. The client compiler is at the heart of the VM configuration used by default for interactive desktop applications. For such applications, low startup and pause times are more important than peak performance. This paper outlines the new architecture of the client compiler and shows how it interacts with the VM. It presents the intermediate representation that now uses static single-assignment (SSA) form and the linear scan algorithm for global register allocation. Efficient support for exception handling and deoptimization fulfills the demands that are imposed by the dynamic features of the Java programming language. The evaluation shows that the new client compiler generates better code in less time. The popular SPECjvm98 benchmark suite is executed 45% faster, while the compilation speed is also up to 40% better. This indicates that a carefully selected set of global optimizations can also be integrated in just-in-time compilers that focus on compilation speed and not on peak performance. In addition, the paper presents the impact of several optimizations on execution and compilation speed. As the source code is freely available, the Java HotSpot™ VM and the client compiler are the ideal basis for experiments with new feedback-directed optimizations in a production-level Java just-in-time compiler. The paper outlines research projects that add fast algorithms for escape analysis, automatic object inlining, and array bounds check elimination.

We implemented a new escape analysis algorithm for Sun Microsystems' Java HotSpottrade VM. The results are used to replace objects with scalar variables, to allocate objects on the stack, and to remove synchronization. This paper deals with the representation of optimized objects in the debugging information and with reallocation and garbage collection support for a safe execution of optimized methods. Assignments to fields of parameters that can refer to both stack and heap objects are associated with an extended write barrier which skips card marking for stack objects. The traversal of objects during garbage collection uses a wrapper that abstracts from stack objects and presents their pointer fields as root pointers to the garbage collector

Object inlining is an optimization that embeds certain referenced objects into their referencing object. It reduces the costs of field accesses by eliminating unnecessary field loads. The order of objects in the heap is changed in such a way that objects that are accessed together are placed next to each other in memory so that their offset is fixed, i.e. the objects are colocated. This allows field loads to be replaced by address arithmetic. We implemented this optimization for Sun Microsystems' Java HotSpot™ VM. The analysis is performed automatically at run time, requires no actions on the part of the programmer and supports dynamic class loading.

Monaco is a domain-specific language for machine automation programming. It has been developed with the objective to empower domain experts with limited programming capabilities. Its main language features are an imperative notation for reactive systems, concepts for describing asynchronous event handling in a concise way, and a state-of-the-art component approach. Monaco is a programming language with a Pascal-like syntax, but also comes with a visual programming environment. In this paper we review the language Monaco, show the visual representation scheme, report on the programming environment and compare our visual notation to Statecharts.

In object-oriented programming languages, an object is said to escape the method or thread in which it was created if it can also be accessed by other methods or threads. Knowing which objects do not escape allows a compiler to perform aggressive optimizations.This paper presents a new intraprocedural and interprocedural algorithm for escape analysis in the context of dynamic compilation where the compiler has to cope with dynamic class loading and deoptimization. It was implemented for Sun Microsystems' Java HotSpot™ client compiler and operates on an intermediate representation in SSA form. We introduce equi-escape sets for the efficient propagation of escape information between related objects. The analysis is used for scalar replacement of fields and synchronization removal, as well as for stack allocation of objects and fixed-sized arrays. The results of the interprocedural analysis support the compiler in inlining decisions and allow actual parameters to be allocated on the caller stack.Under certain circumstances, the Java HotSpot™ VM is forced to stop executing a method's machine code and transfer control to the interpreter. This is called deoptimization. Since the interpreter does not know about the scalar replacement and synchronization removal performed by the compiler, the deoptimization framework was extended to reallocate and relock objects on demand.

We present an optimized implementation of the linear scan register allocation algorithm for Sun Microsystems' Java HotSpot™ client compiler. Linear scan register allocation is especially suitable for just-in-time compilers because it is faster than the common graph-coloring approach and yields results of nearly the same quality.Our allocator improves the basic linear scan algorithm by adding more advanced optimizations: It makes use of lifetime holes, splits intervals if the register pressure is too high, and models register constraints of the target architecture with fixed intervals. Three additional optimizations move split positions out of loops, remove register-to-register moves and eliminate unnecessary spill stores. Interval splitting is based on use positions, which also capture the kind of use and whether an operand is needed in a register or not. This avoids the reservation of a scratch register.Benchmark results prove the efficiency of the linear scan algorithm: While the compilation speed is equal to the old local register allocator that is part of the Sun JDK 5.0, integer benchmarks execute about 15% faster. Floating-point benchmarks show the high impact of the Intel SSE2 extensions on the speed of numeric Java applications: With the new SSE2 support enabled, SPECjvm98 executes 25% faster compared with the current Sun JDK 5.0.

Programs are not read sequentially like a book but rather selectively like an encyclopedia. Instead of linear text we therefore suggest non-linear active text as a medium for structuring and browsing source code. Although common program editors are mainly character based we believe that non-textual information such as pictures, links, folds, and annotations can improve the readability of programs. In this paper we show how a text editor can be extended to include active text elements and give examples for how to apply these facilities to source code. Our approach is different from that of syntax-oriented editors in that our structuring is not based on the syntax of the edited texts. The implementation was done in the Oberon system which offers powerful mechanisms for extending software in an object-oriented way.

this paper we present a technique for generating SSA form in a single pass directly from the source text of a program. It can be applied to structured programs, i.e., to programs that contain only assignments and structured statements (such as IF, CASE, WHILE, REPEAT, or FOR) but no goto statements. For such programs the join nodes and thus the places where to insert f-assignments are immediately known so that f-assignments can be generated on the fly during parsing. This is useful for languages such as Simula[3], Modula-2 [13] or Oberon [14] that lack goto statements at all. If language independence is desired our algorithm can also be applied to control flow graphs instead of source programs. The advantage of generating SSA form directly during parsing is that it saves an intermediate step. Instead of building a high-level representation of a program and then transforming it, we directly generate machine-specific instructions in SSA form ready for optimizations. This saves time and memory. However, the same technique could be used for generating a machine-independent representation as well. We do not deal here with alias problems caused by assignments to array elements, to parameters 4 passed by reference, and to variables that are referenced via pointers. These problems can be dealt with in the same way as described in [5]. While Cytron's method requires the construction of the dominator tree---itself a non-trivial step--- our method does not need such a data structure. However, the dominator tree is useful in subsequent optimizations so that it is worth showing that for structured programs it can be built in a single pass during parsing, too. Section 2 of this paper explains our algorithm for generating SSA form while Section 3 shows how to build the dominator tre...

Abstract We present a simple method for connecting semantic actions to parsers. Although applicable to any kind of parser it is especially suited for LR parsers. The method is based on the idea of separating syntax analysis and semantic processing and executing semantic actions by procedures, similar to those of a recursive descent compiler. The procedures are driven by structural information about the source program, which is collected during parsing. The method is applicable to L‐attributed grammars. It can be incorporated easily into any existing parser.