MPLR 2024 – Proceedings

21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes (MPLR 2024)

Frontmatter

Keynote

Can WebAssembly Be Software’s Final Substrate? (Keynote)
Ben L. Titzer
(Carnegie Mellon University, USA)
Since the dawn of computing, many formats for executable programs have come and gone. The design of an executable format encounters design choices and tradeoffs such as expressiveness, ease of parsing/decoding/execution, the level of abstraction, and performance. With the advent of WebAssembly, a portable low-level compilation target for many languages, an intriguing question arises: can we finally standardize a universal binary format and software virtual machine? After many years, I believe that we finally can. Unlike language-specific bytecode formats whose abstraction level serves only one language family well, or machine-code formats that serve specific ISAs and operating systems well, WebAssembly sits between these levels of abstraction. In this talk I will share my vision for a future where all software sits on a standardized, well-specified, formally-verified substrate that allows innovation above and below, and unlocks high performance and portability for all programming languages.

@InProceedings{MPLR24p1, author = {Ben L. Titzer}, title = {Can WebAssembly Be Software’s Final Substrate? (Keynote)}, booktitle = {Proc.\ MPLR}, publisher = {ACM}, pages = {1--1}, doi = {10.1145/3679007.3691540}, year = {2024}, } Publisher's Version

Optimization

Lazy Sparse Conditional Constant Propagation in the Sea of Nodes
Christoph Aigner, Gergö Barany, and Hanspeter Mössenböck
(JKU Linz, Austria; Oracle Labs, Austria)
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.

@InProceedings{MPLR24p2, author = {Christoph Aigner and Gergö Barany and Hanspeter Mössenböck}, title = {Lazy Sparse Conditional Constant Propagation in the Sea of Nodes}, booktitle = {Proc.\ MPLR}, publisher = {ACM}, pages = {2--13}, doi = {10.1145/3679007.3685059}, year = {2024}, } Publisher's Version

Mutator-Driven Object Placement using Load Barriers
Jonas Norlinder, Albert Mingkun Yang, David Black-Schaffer, and Tobias Wrigstad
(Uppsala University, Sweden; Oracle, Sweden)
Object placement impacts cache utilisation, which is itself critical for performance. Managed languages offer fewer tools than unmanaged languages in the way of controlling object placement due to the abstract view of memory. On the other hand, managed languages often have garbage collectors (GC) that move objects as part of defragmentation. In the context of OpenJDK, Hot-Cold Objects Segregation GC (HCSGC) added locality improvement on-top of ZGC by piggybacking on its loaded value-barrier based design. In addition to the open problem of tuning HCSGC, we identify a contradiction in two of its design goals and propose LR, that addresses both these problems. We implement LR on-top of ZGC and compare it with GCs in OpenJDK and with the best performing HCSGC configuration using DaCapo, JGraphT and SPECjbb2015. While using less resources, LR outperforms HCSGC in 18 configurations, matches performance in 17, and regresses in 3.

@InProceedings{MPLR24p14, author = {Jonas Norlinder and Albert Mingkun Yang and David Black-Schaffer and Tobias Wrigstad}, title = {Mutator-Driven Object Placement using Load Barriers}, booktitle = {Proc.\ MPLR}, publisher = {ACM}, pages = {14--27}, doi = {10.1145/3679007.3685060}, year = {2024}, } Publisher's Version Published Artifact Archive submitted (340 kB) Artifacts Available

Interactive Programming for Microcontrollers by Offloading Dynamic Incremental Compilation
Fumika Mochizuki, Tetsuro Yamazaki, and Shigeru Chiba
(University of Tokyo, Japan)
Interactive execution environments are suitable for trial-and-error basis programming for microcontrollers. However, they are mostly implemented as interpreters to meet microcontrollers' limited memory size and demands for portability. Hence, their execution performance is not sufficiently high. In this paper, we propose offloading dynamic incremental compilation and linking to a host computer connected to a microcontroller. Since the computing resources of the host computer are sufficient to execute incremental dynamic compilation, they are used to enhance the relatively poor computing resources of the microcontroller. To show the feasibility of this idea, we design a small programming language named BlueScript and implement its interactive execution environment. Our experiment reveals that BlueScript executes a program one to two orders of magnitude faster than MicroPython, while its interactivity is comparable to that of MicroPython despite using dynamic incremental compilation.

@InProceedings{MPLR24p28, author = {Fumika Mochizuki and Tetsuro Yamazaki and Shigeru Chiba}, title = {Interactive Programming for Microcontrollers by Offloading Dynamic Incremental Compilation}, booktitle = {Proc.\ MPLR}, publisher = {ACM}, pages = {28--40}, doi = {10.1145/3679007.3685062}, year = {2024}, } Publisher's Version

Programming

mruby on Resource-Constrained Low-Power Coprocessors of Embedded Devices
Go Suzuki, Takuo Watanabe, and Sosuke Moriguchi
(Tokyo Institute of Technology, Tokyo, Japan)
As IoT devices advance, their microcontroller systems-on-a-chip (SoCs) demand higher speeds, more memory, and advanced peripherals, leading to increased power consumption. Integrating low-power (LP) coprocessors in SoCs can reduce power usage while maintaining responsiveness. However, switching application execution to and from the coprocessors generally involves complex and platform-specific procedures. We propose a JIT compilation method for managed programming languages to streamline LP coprocessor use. Our prototype for the programming language mruby includes a JIT compiler and a seamless processor-switching mechanism, enabling rapid development of IoT applications leveraging LP coprocessors. This work-in-progress paper describes the design and implementation of the extended mruby interpreter and presents preliminary evaluations of its power consumption and latency on ESP32-S3 and ESP32-C6.

@InProceedings{MPLR24p41, author = {Go Suzuki and Takuo Watanabe and Sosuke Moriguchi}, title = {mruby on Resource-Constrained Low-Power Coprocessors of Embedded Devices}, booktitle = {Proc.\ MPLR}, publisher = {ACM}, pages = {41--47}, doi = {10.1145/3679007.3685064}, year = {2024}, } Publisher's Version Archive submitted (5.7 MB)

Imagine There’s No Source Code: Replay Diagnostic Location Information in Dynamic EDSL Meta-programming
Baltasar Trancón y Widemann and Markus Lepper
(TH Brandenburg, Germany; semantics, Germany)
Programs in embedded domain-specific languages are realized as graphs of objects of the host language rather than as static input texts. This property enables dynamic meta-programming, but also makes it harder to attach location information to diagnostic messages that arise at a later stage, after the program graph construction. Thus, EDSL-generating expressions and algorithms can be difficult to debug. Here, we present a technique for transparently capturing and replaying location information about the origin of EDSL program objects. It has been implemented in the context of the LLJava-live EDSL-to-bytecode compiler framework on the JVM. The basic idea can be generalized to other contexts, and to any managed runtime environment with reified stack traces.

@InProceedings{MPLR24p48, author = {Baltasar Trancón y Widemann and Markus Lepper}, title = {Imagine There’s No Source Code: Replay Diagnostic Location Information in Dynamic EDSL Meta-programming}, booktitle = {Proc.\ MPLR}, publisher = {ACM}, pages = {48--54}, doi = {10.1145/3679007.3685061}, year = {2024}, } Publisher's Version Archive submitted (160 kB)

Existential Containers in Scala
Dimitri Racordon, Eugene Flesselle, and Matthieu Bovel
(EPFL, Switzerland)
Type classes have been well-established as a powerful tool to write generic algorithms and data structures while escaping vexing limitations of subtyping with respect to extensibility, binary methods, and partial abstractions. Unfortunately, type classes are typically inadequate to express run-time polymorphism and dynamic dispatch, two features considered central to object-oriented systems. This paper explains how to alleviate this problem in Scala. We present existential containers, a form of existential types bounded by type classes rather than types, and explain how to implement them using Scala’s existing features.

@InProceedings{MPLR24p55, author = {Dimitri Racordon and Eugene Flesselle and Matthieu Bovel}, title = {Existential Containers in Scala}, booktitle = {Proc.\ MPLR}, publisher = {ACM}, pages = {55--64}, doi = {10.1145/3679007.3685056}, year = {2024}, } Publisher's Version Info

Quff: A Dynamically Typed Hybrid Quantum-Classical Programming Language
Christopher John Wright, Mikel Luján, Pavlos Petoumenos, and John Goodacre
(University of Manchester, United Kingdom)
Current strategies for quantum software development still exhibit complexity on top of the already-intricate nature of quantum mechanics. Quantum programming languages are either restricted to low-level, gate-based operations appended to classical objects for circuit generation, or require modelling of quantum state transformations in Hilbert space through algebraic representation.
This paper presents the Quff language which is a high-level, dynamically typed quantum-classical programming language. The Quff compiler and runtime system facilitates quantum software development with high-level expression abstracted across the quantum-classical paradigms. Quff is constructed on top of the Truffle framework which aids the implementation and efficiency of the stack, while reusing the JVM infrastructure. The presented comparisons display that Quff lends itself as an effective, easy-to-use solution for the development of executable quantum programs with automatic circuit generation and efficient computation.

@InProceedings{MPLR24p65, author = {Christopher John Wright and Mikel Luján and Pavlos Petoumenos and John Goodacre}, title = {Quff: A Dynamically Typed Hybrid Quantum-Classical Programming Language}, booktitle = {Proc.\ MPLR}, publisher = {ACM}, pages = {65--81}, doi = {10.1145/3679007.3685063}, year = {2024}, } Publisher's Version

Analysis

Towards Realistic Results for Instrumentation-Based Profilers for JIT-Compiled Systems
Humphrey Burchell, Octave Larose, and Stefan Marr
(University of Kent, United Kingdom)
Profilers are crucial tools for identifying and improving ap- plication performance. However, for language implementa- tions with just-in-time (JIT) compilation, e.g., for Java and JavaScript, instrumentation-based profilers can have signifi- cant overheads and report unrealistic results caused by the instrumentation. In this paper, we examine state-of-the-art instrumentation- based profilers for Java to determine the realism of their results. We assess their overhead, the effect on compilation time, and the generated bytecode. We found that the pro- filer with the lowest overhead increased run time by 82×. Additionally, we investigate the realism of results by test- ing a profiler’s ability to detect whether inlining is enabled, which is an important compiler optimization. Our results document that instrumentation can alter program behavior so that performance observations are unrealistic, i.e., they do not reflect the performance of the uninstrumented program. As a solution, we sketch late-compiler-phase-based in- strumentation for just-in-time compilers, which gives us the precision of instrumentation-based profiling with an over- head that is multiple magnitudes lower than that of standard instrumentation-based profilers, with a median overhead of 23.3% (min. 1.4%, max. 464%). By inserting probes late in the compilation process, we avoid interfering with compiler optimizations, which yields more realistic results.

@InProceedings{MPLR24p82, author = {Humphrey Burchell and Octave Larose and Stefan Marr}, title = {Towards Realistic Results for Instrumentation-Based Profilers for JIT-Compiled Systems}, booktitle = {Proc.\ MPLR}, publisher = {ACM}, pages = {82--89}, doi = {10.1145/3679007.3685058}, year = {2024}, } Publisher's Version

Toward Declarative Auditing of Java Software for Graceful Exception Handling
Leo St. Amour and Eli Tilevich
(Virginia Tech, Blacksburg, USA)
Despite their language-integrated design, Java exceptions can be difficult to use effectively. Although Java exceptions are syntactically straightforward, negligent practices often result in code logic that is not only inelegant but also unsafe. This paper explores the challenge of auditing Java software to enhance the effectiveness and safety of its exception logic. We revisit common anti-patterns associated with Java exception usage and argue that, for auditing, their detection requires a more nuanced approach than mere identification. Specifically, we investigate whether reporting such anti-patterns can be prioritized for subsequent examination. We prototype our approach as Händel, in which anti-patterns and their priority, or weight, are expressed declaratively using probabilistic logic programming. Evaluation with representative open-source code bases suggests Händel’s promise in detecting, reporting, and ranking the anti-patterns, thus helping streamline Java software auditing to ensure the safety and quality of exception-handling logic.

@InProceedings{MPLR24p90, author = {Leo St. Amour and Eli Tilevich}, title = {Toward Declarative Auditing of Java Software for Graceful Exception Handling}, booktitle = {Proc.\ MPLR}, publisher = {ACM}, pages = {90--97}, doi = {10.1145/3679007.3685057}, year = {2024}, } Publisher's Version

Dynamic Possible Source Count Analysis for Data Leakage Prevention
Eri Ogawa, Tetsuro Yamazaki, and Ryota Shioya
(University of Tokyo, Japan; IBM Research, Tokyo, Japan)
Dynamic Taint Analysis (DTA) is a widely studied technique that can effectively detect various attacks and information leakage. In the context of detecting information leakage, taint is a flag added to data to indicate whether secret data can be inferred from it. DTA tracks the flow of tainted data in a language runtime environment and identifies secret data leakage when tainted data is transmitted externally. We found that existing DTAs can produce false negatives and false positives in complex data flows because of the binary nature of taint. Since taint is binary, meaning either secret data is inferable (=1) or non-inferable (=0), it cannot represent intermediate states that may slightly infer the secret data, and these states are quantized to 0 or 1. As a result of this quantization, existing methods are unable to distinguish between outputs that are practically secure and those that pose a real security threat in complex data flows, resulting in false positives and false negatives. To address this problem, we introduce the concept of Possible Source Count (PSC) and propose Dynamic Possible source Count Analysis (DPCA), which tracks PSC instead of taint. PSC is a metric that indicates how many secrets can be identified by observing the data. DPCA tracks and computes the PSC of each data item using dynamic symbolic execution. By evaluating the PSC of data that reaches the sink point, DPCA can effectively distinguish between data that is practically secure and data that poses a security threat.

@InProceedings{MPLR24p98, author = {Eri Ogawa and Tetsuro Yamazaki and Ryota Shioya}, title = {Dynamic Possible Source Count Analysis for Data Leakage Prevention}, booktitle = {Proc.\ MPLR}, publisher = {ACM}, pages = {98--111}, doi = {10.1145/3679007.3685065}, year = {2024}, } Publisher's Version

The Cost of Profiling in the HotSpot Virtual Machine
Rene Mueller, Maria Carpen-Amarie, Matvii Aslandukov, and Konstantinos Tovletoglou
(Huawei Zurich Research Center, Switzerland; Kharkiv National University of Radio Electronics, Ukraine; Independent Researcher, Switzerland)
Modern language runtimes use just-in-time compilation to execute applications natively. Typically, multiple compiler tiers cooperate so that compilation at a later stage can leverage profiling information generated by earlier tiers. This allows for machine code that is optimized to the actual workload and hardware. In this work, we study the profiling overhead caused by code instrumentation in the HotSpot Java virtual machine for 23 applications from the Renaissance suite and five additional benchmarks. Our study confirms two common assumptions. First, most applications move quickly through the profiling phase. However, we also show applications that tier up surprisingly slowly and, thus, are more affected by profiling overheads. We find that the instrumentation needed for profiling can slow application execution down by up to 35×. A key factor is the memory contention on the shared profiling data structures in multi-threaded applications. Second, most virtual call sites are monomorphic, i.e., they only have a single receiver type. This can reduce the run-time cost of otherwise expensive receiver type profiling at virtual call sites. Our analysis suggests that, for the most part, profiling overhead in language runtimes is not a cause for concern. However, we show that there are situations, e.g., in multi-threaded applications, where profiling impact can be consequential.

@InProceedings{MPLR24p112, author = {Rene Mueller and Maria Carpen-Amarie and Matvii Aslandukov and Konstantinos Tovletoglou}, title = {The Cost of Profiling in the HotSpot Virtual Machine}, booktitle = {Proc.\ MPLR}, publisher = {ACM}, pages = {112--126}, doi = {10.1145/3679007.3685055}, year = {2024}, } Publisher's Version

proc time: 3.96