Search

Compilers are computer programs that translate a program written in one language into a program written in another language. At the same time, a compiler is a large software system, with many internal components and algorithms and complex interactions between them. Thus, the study of compiler construction is an introduction to techniques for the translation and improvement of programs, and a practical exercise in software engineering. This chapter provides a conceptual overview of all the major components of a modern compiler.

Prevailing data-intensive applications, such as artificial intelligence and internet of things, demand considerable compute capability. Coarse-grained reconfigurable architectures (CGRAs) can meet this demand via providing abundant compute resources. However, compilation has become an essential problem because the increasing resources need to be orchestrated efficiently. Static compilation is insufficient due to conservative resource allocation and exponentially increasing time cost while state-of-the-art dynamic compilation still performs poorly in both generality and efficiency. This article proposes a dynamic compilation system for CGRAs through online pattern-based configuration transformation, which enables virtualization to improve resource utilization and flexibility. It utilizes statically-generated patterns to straightforwardly determine dynamic placement of registers and operations so that the transformation algorithm has a low complexity. Domain-specific features are extracted by a k-means clustering algorithm to help improve the quality of patterns. The experimental results show that statically compiled applications can be transformed onto arbitrary resources at runtime, reserving 73.5 (22.8-163.3 percent) of the original performance $/$ / resource on average, 9.1 (0-52.9 percent) better than the state-of-the-art non-general methods.

Many modern RDBMS provide procedural extensions for SQL programming language, which allow users to perform server-side complex computations. Use of such extensions improves modularity and code reuse, simplifies programming of application logic, and helps developers to avoid network overhead and enhance performance. Interpretation is mostly used to execute SQL queries and procedural extensions code, resulting in significant computational overhead because of indirect function calls and performing of generic checks. Moreover, most RDBMS use different engines for SQL queries execution and procedural extensions code execution, and it is necessary to perform additional computations to switch between different engines. Thus, interpretation of SQL queries combined with interpretation of procedural extensions code may drastically degrade performance of RDBMS. One solution is to use a dynamic compilation technique. In this paper, we describe the technique of dynamic compilation of PL/pgSQL procedural language for the PostgreSQL database system using LLVM compiler infrastructure. Dynamic compiler of PL/pgSQL procedural language is developed as part of PostgreSQL queries dynamic compiler. Proposed technique helps to get rid of computational overhead caused by interpretation usage. Synthetic performance tests show that the developed solution speeds up SQL queries execution by several times.

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. The second Futamura projection solves this problem by self-applying partial evaluation on the partial evaluation algorithm, effectively generating language-specific compilers from interpreters. This typically reduces compilation time compared to the first projection. Previous work employed the second projection to some extent, however we are not aware of any usage of the generic second Futamura projection in a state-of-the-art language runtime. To solve the problems of self-application and code-size explosion, this paper proposes CompGen, an approach based on code generation of subsets of language interpreters. It is loosely based upon the idea of the second Futamura projection. Our implementation of CompGen for GraalVM shows that our usage of a novel code-generation algorithm allows us to generate efficient compilers that emit fast target programs which easily outperform the first Futamura projection in compilation time. We evaluated our approach with the high-performance JavaScript implementation of GraalVM and standard JavaScript benchmarks, showing that our approach achieves >2X speedups of partial evaluation.

Dynamic compilers collect a variety of information to optimize programs and achieve peak performance. Nevertheless, particularly in data-heavy applications, analysis of the processed data - data structures, metrics, relations - could enable additional optimizations in terms of access patterns and data locality. Query planning in database systems is one source of inspiration, but due to the required overhead to collect such information, it is infeasible in dynamic compilers. With this project, we propose integrating data analysis into a dynamic runtime to speed up big data applications. The goal is to use the detailed run-time information for speculative compiler optimizations based on the shape and complexion of the data to improve performance.

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. In this paper, we investigate how speculative optimizations can reduce the peak performance impact of taint propagation on programs executed on a managed runtime. We also explain how a managed runtime can implement DTA to be amenable to such optimizations. We implemented our ideas in TruffleTaint, a DTA platform which supports both dynamic languages like JavaScript and languages like C and C++ which are typically compiled statically. We evaluated TruffleTaint on several benchmarks from the popular Computer Language Benchmarks Game and SPECint 2017 benchmark suites. Our evaluation shows that TruffleTaint is often able to avoid slowdown entirely when programs do not operate on tainted data, and that it exhibits slowdown of on average ∼2.10x and up to ∼5.52x when they do, which is comparable to state-of-the-art taint analysis platforms optimized for performance.

Big-data systems have gained significant momentum, and Apache Spark is becoming a de-facto standard for modern data analytics. Spark relies on code generation to optimize the execution performance of SQL queries on a variety of data sources. Despite its already efficient runtime, Spark's code generation suffers from significant runtime overheads related to data de-serialization during query execution. Such performance penalty can be significant, especially when applications operate on human-readable data formats such as CSV or JSON.

Side-channel attacks are a concrete and practical threat to the security of computing systems, ranging from high performance platforms to embedded devices. In this paper, we will provide a brief systematization of the current existing approaches to analyze the side-channel vulnerability of an implementation, or automatically implement countermeasures, relying on methodologies typical of compiler systems. We will dedicate a spotlight to a significant progress in the countermeasures techniques which is represented by the application of dynamic compilation techniques to prevent a side-channel attacker from devising a model of the attacked application. We conclude the work highlighting promising research directions in this field.

In recent years, as performance and capacity of main and external memory grow, performance of database management systems (DBMSes) on certain kinds of queries is more determined by raw CPU speed. Currently, PostgreSQL uses the interpreter to execute SQL queries. This yields an overhead caused by indirect calls to handler functions and runtime checks, which could be avoided if the query were compiled into native code "on-the-fly", i.e. just-in-time (JIT) compiled: at run time the specific table structure is known as well as data types and built-in functions used in the query as well as the query itself. This is especially important for complex queries, performance of which is CPU-bound. We’ve developed a PostgreSQL extension that implements SQL query JIT compilation using LLVM compiler infrastructure. In this paper we show how to implement JIT compilation to speed up sequential scan operator (SeqScan) as well as expressions in WHERE clauses. We describe some important optimizations that are possible only with dynamic compilation, such as precomputing tuple attributes offsets only for attributes used by the query. We also discuss the maintainability of our extension, i.e. the automation for translating PostgreSQL backend functions into LLVM IR, using the same source code both for our JIT compiler and the existing interpreter. Currently, with LLVM JIT we achieve up to 5x speedup on synthetic tests as compared to original PostgreSQL interpreter.

In recent years, as performance and capacity of main and external memory grow, performance of database management systems (DBMSes) on certain kinds of queries is more determined by raw CPU speed. Currently, PostgreSQL uses the interpreter to execute SQL queries. This yields an overhead caused by indirect calls to handler functions and runtime checks, which could be avoided if the query were compiled into native code "on-the-fly", i.e. just-in-time (JIT) compiled: at run time the specific table structure is known as well as data types and built-in functions used in the query as well as the query itself. This is especially important for complex queries, performance of which is CPU-bound. We have developed a PostgreSQL extension that implements SQL query JIT compilation using LLVM compiler infrastructure. In this paper we show how to implement LLVM-analogues of the main operators of the PostgreSQL, how to replace Volcano iterator model abstraction (open(), next(), close()) by the abstraction that is more suitable to generate code for a particular query. Currently, with LLVM JIT we achieve up to 4.3x speedup on TPC-H Q1 query as compared to original PostgreSQL interpreter.

Register allocation is a major step for all compilers. Various register allocation algorithms have been developed over the decades. This work describes a new class of rapid register allocation algorithms and presents experimental data on their behavior. Our research encourages the avoidance of graphing and graph-coloring based on the fact that precise graph-coloring is nondeterministic polynomial time-complete (NP-complete), which is not suitable for real-time tasks. In addition, practical graph-coloring algorithms tend to use polynomial-time heuristics. In dynamic compilation environments, their super linear complexity makes them unsuitable for register allocation and code generation. Existing tools for code generation and register allocation do not completely fulfill the requirements of fast compilation. Existing approaches either do not allow for the optimization of register allocation to be achieved comprehensively with a sufficient degree of performance or they require an unjustifiable amount of time and/or resources. Therefore, we propose a new class of register allocation and code generation algorithms that can be performed in linear time. These algorithms are based on the mathematical foundations of abstract interpretation and the computation of the level of abstraction. They have been implemented in a specialized library for just-in-time compilation. The specialization of this library involves the execution of common intermediate language (CIL) and low level virtual machine (LLVM) with a focus on embedded systems.

We present libVersioningCompiler, a C++ library designed to support the dynamic generation of multiple versions of the same compute kernel in a HPC scenario. It can be used to provide continuous optimization, code specialization based on the input data or on workload changes, or otherwise to dynamically adjust the application, without the burden of a full dynamic compiler. The library supports multiple underlying compilers but specifically targets the llvm framework.We also provide examples of use, showing the overhead of the library, and providing guidelines for its efficient use. Keywords: Dynamic compilation, Versioning compiler, Continuous optimization

Heterogeneous hardware is central to modern advances in performance and efficiency. Mainstream programming models for heterogeneous architectures, however, sacrifice safety and expressiveness in favor of low-level control over performance details. The interfaces between hardware units consist of verbose, unsafe APIs; hardware-specific languages make it difficult to move code between units; and brittle preprocessor macros complicate the task of specializing general code for efficient accelerated execution. We propose a unified low-level programming model for heterogeneous systems that offers control over performance, safe communication constructs, cross-device code portability, and hygienic metaprogramming for specialization. The language extends constructs from multi-stage programming to separate code for different hardware units, to communicate between them, and to express compile-time code optimization. We introduce static staging, a different take on multi-stage programming that lets the compiler generate all code and communication constructs ahead of time. To demonstrate our approach, we use static staging to implement BraidGL, a real-time graphics programming language for CPU-GPU systems. Current real-time graphics software in OpenGL uses stringly-typed APIs for communication and unsafe preprocessing to generate specialized GPU code variants. In BraidGL, programmers instead write hybrid CPU-GPU software in a unified language. The compiler statically generates target-specific code and guarantees safe communication between the CPU and the graphics pipeline stages. Example scenes demonstrate the language's productivity advantages: BraidGL eliminates the safety and expressiveness pitfalls of OpenGL and makes common specialization techniques easy to apply. The case study demonstrates how static staging can express core placement and specialization in general heterogeneous programming.

The course in Compiler Construction is part of the Computer Science masters program at Luleå University of Technology (LTU). Since the fall of 2014, the course is given by the Embedded Systems group. This paper outlines the course syllabus and its relation to CPS/IoT and embedded systems in general. In particular, the course introduces domain specific language design with the outset from the imperative RTFM-core language. Students are exposed to design choices for the language, spanning from programming model, compiler design issues, back-end tools, and even runtime environments. The intention is to give a holistic perspective and motivate the use of compilation techniques towards robust, efficient, and verifiable (embedded) software. Of course, developing basic skills is not overlooked and as part of the laboratory assignments, students extend the min-imalistic Object Oriented language RTFM-cOOre and develop the compiler accordingly targeting the RTFM-core language as an intermediate representation. As the RTFM-core/-cOOre compilers are implemented using OCaml/Men-hir, the students are also exposed to functional languages and to their advantages in the context of compiler construction. However, for their own development they may choose alternative design tools and languages. This gives us the opportunity to review and correlate achievements and efficiency to the choice of tools and languages and it is an outset for future course development.

The recent expansion of cloud-based solutions highlights that legacy programming languages and technologies, such as the PHP language, are still in heavy use. Furthermore, it turns out that for their effective integration into modern platforms, it is important to understand the legacy code base to provide modern analysis, testing and eventually compiler tooling. The dynamic language PHP would be the perfect candidate for such a synergy, due to its extensive usage, frequent issues in source codes and the need for a better performance and scalability. In this paper, we describe a solution that combines known static language code analysis techniques and that is enhanced by numerous modifications. As a result, we have a design and implementation of a PHP dynamic language code analysis, compiler and runtime, which improves performance and allows for more advanced high level code analysis and tools, all incorporated into the modern platform of .NET Core while taking advantage of the Microsoft Roslyn Compiler Platform.

Modern virtual machines for JavaScript use just-in-time (JIT) compilation to produce binary code. JIT compilers cannot perform complex optimizations. In contrast, static compilation has unlimited capabilities for complex optimizing transformations, but it cannot be efficiently applied to dynamic languages, such as JavaScript. In this paper, a general approach to the ahead-of-time compilation of programs in dynamic languages is proposed, and this approach is used for improving two virtual machines JavaScript- Core and V8. In the implementation of the improved JavaScriptCore engine with ahead-of-time compilation, the specifics of using JavaScript programs as a part of locally stored applications for the ARM platform were taken into account. In the V8 engine for the x86-64 platform, the ahead-of-time compilation is implemented by caching an optimized internal representation in a separate file.

Information systems face many threats, such as covert channels, which declassify hidden information by, e.g., analyzing the program execution time. Such threats exist at various stages of the execution of instructions. Even if software developers are able to neutralize these threats in source code, new attack vectors can arise in compiler-generated machine code from these representations. Existing approaches for preventing vulnerabilities have numerous restrictions related to both their functionality and the range of threats that can be found and removed. This study presents a technique for removing threats and generating safer code using dynamic compilation in an execution environment by combining information from program analysis of the malicious code and re-compiling such code to run securely. The proposed approach stores summary information in the form of rules that can be shared among analyses. The annotations enable us to conduct the analyses to mitigate threats. Developers can update the analyses and control the volume of resources that are allocated to perform these analyses by changing the precision. The authors’ experiments show that the binary code created by applying the suggested method is of high quality.

Sistemas que utilizam compilação dinâmica geram código alvo em tempo de execução, fazendo com que o tempo de compilação seja incluı́do no tempo total do sistema. Portanto, é crucial que o sistema de compilação dinâmico tenham ao mesmo tempo um baixo custo e seja capaz de gerar código de boa qualidade. Neste artigo apresentamos um sistema de aprendizado de máquina para seleção inteligente de otimizações que aprende quais as melhores sequências de otimizações para cada região de código compilado por um compilador dinâmico. O sistema foi implementado e testado em um tradutor dinâmico de binários, o OI-DBT, trazendo um ganho médio de desempenho de 26,32%.

Partial evaluation, based on the first Futamura projection, allows compiling language interpreters with given user programs to efficient target programs. GraalVM is an example system that implements this mechanism. It combines partial evaluation with profiling information and dynamic compilation, to transform interpreters into high-performance machine code at run time. However, partial evaluation is compile-time intensive, as it requires the abstract interpretation of interpreter implementations. Thus, optimizing partial evaluation is still subject to research to this day. We present an approach to speed up partial evaluation, by generating source code ahead of time, which performs partial evaluation specific to interpreter implementations. Generated code, when executed for a given user program at run time, directly emits partially evaluated interpreter instructions for language constructs it knows and sees in the program. This yields the target program faster than performing the first Futamura projection. The generated source code behaves similarly to a specialized partial evaluator deduced by performing the second Futamura projection, although no self-applying partial evaluator is involved during code generation.

As the efficiency of main and external memory grows, alongside with decreasing hardware costs, the performance of database management systems (DBMS) on certain kinds of queries is more determined by CPU characteristics and the way it is utilized. Relational DBMS utilize diverse execution models to run SQL queries. Those models have different properties, but in either way suffer from substantial overhead during query plan interpretation. The overhead comes from indirect calls to handler functions, runtime checks and large number of branch instructions. One way to solve this problem is dynamic query compilation that is reasonable only in those cases when query interpretation time is larger than the time of compilation and optimized machine code execution. This requirement can be satisfied only when the amount of data to be processed is large enough. If query interpretation takes milliseconds to finish, then the cost of dynamic compilation can be hundreds of times more than the execution time of generated machine code. To pay off the cost of dynamic compilation, the generated machine code has to be reused in subsequent executions, thus saving the cost of code compilation and optimization. In this paper, we examine the method of machine code caching in our query JIT-compiler for DBMS PostgreSQL. The proposed method allows us to eliminate compilation overhead. The results show that dynamic compilation of queries with machine code caching feature gives a significant speedup on OLTP queries.

In High Performance Computing, it is often useful to fine tune an application code via recompilation of specific computational intensive code fragments to leverage runtime knowledge. Traditional compilers rarely provide such capabilities, while solutions such as LIBVC allow C/C++ code to employ dynamic compilation. We evaluate the impact of the introduction of Just-in-Time (JIT) compilation in a framework supporting partial dynamic (re-) compilation of functions to provide continuous optimization in high performance environments. We show that JIT solutions can have comparable performance in terms of code quality and smaller compilation overhead w.r.t. the LIBVC alternatives. We further demonstrate the strength of our approach against a state-of-the-art interpreter-based dynamic evaluation solution.

Tracing just-in-time compilation is a popular compilation technique for the efficient implementation of dynamic languages, which is commonly used for JavaScript, Python and PHP. We provide a formal model of tracing JIT compilation of programs using abstract interpretation. Hot path detection corresponds to an abstraction of the trace semantics of the program. The optimization phase corresponds to a transform of the original program that preserves its trace semantics up to an observation modeled by some abstraction. We provide a generic framework to express dynamic optimizations and prove them correct. We instantiate it to prove the correctness of dynamic type specialization and constant variable folding. We show that our framework is more general than the model of tracing compilation introduced by Guo and Palsberg [2011] based on operational bisimulations., To appear in ACM Transactions on Programming Languages and Systems

In recent years, JavaScript has become one of the most popular programming languages on the web. Many massive applications are written using JavaScript, such as Gmail, Google docs, etc. JavaScript is also used in the Node.js - server-side web application developing platform. Moreover, JavaScript is the main language for developing applications on some operating systems for mobile and media devices. Examples of such systems are Tizen and FirefoxOS. Due to increasing popularity of JavaScript many big companies produced and continue to develop their own dynamic compilers for this language. JIT compilation makes it possible to implement many well-known classic optimizations to improve programs performance. To maintain a trade-off between quick startup and doing sophisticated optimizations, JavaScript engines usually use multiple tiers for compiling hot functions: lower tier JITs generate less efficient code, but can start almost immediately (e.g., even with interpretation), while higher tier JITs aim at generating very effective code for hot places, but at the cost of long compilation time. So even highly optimized JavaScript execution engines require some time to "warm-up" before reaching their peak performance. This work is dedicated to the performance improvement of modern dynamic multitier JIT compilers by designing and implementing profile-based optimizations in JavaScript V8 JIT compiler.

Kronos is a signal-processing programming language based on the principles of semifunctional reactive systems. It is aimed at efficient signal processing at the elementary level, and built to scale towards higher-level tasks by utilizing the powerful programming paradigms of “metaprogramming” and reactive multirate systems. The Kronos language features expressive source code as well as a streamlined, efficient runtime. The programming model presented is adaptable for both sample-stream and event processing, offering a cleanly functional programming paradigm for a wide range of musical signal-processing problems, exemplified herein by a selection and discussion of code examples.

We present PyGB, a high-level Python domainspecific language (DSL) for GraphBLAS building blocks for graph algorithms. GraphBLAS is based on a small number of linear algebra operations, and it is described using mathematical notation and concepts. However, the concrete realizations of GraphBLAS concentrate on efficiency and widely usable programming interfaces. The GraphBLAS C language API standardized by the GraphBLAS Forum is the major example of such a realization, and our GraphBLAS Template Library (GBTL) implemented in the C++ language is another. PyGB exposes the \cpp interface of GBTL through a DSL that leverages Python's mature scientific computing ecosystem and high-level syntax. The syntax of PyGB more closely resembles the GraphBLAS mathematical notation than GBTL. The DSL dispatches to dynamically compiled templated classes to achieve comparable performance to the native GBTL code. We highlight the features of PyGB through code examples and discuss how Python's syntax and dynamic execution enable us to provide the high-level abstraction with minimal performance penalty. We demonstrate the stages of execution, from type inference to template compilation, to dynamic linking and invocation from the Python interpreter. Our experimental evaluation shows that for sufficiently large inputs, the overhead of PyGB is negligible and compilation times are not worse than for native GBTL implementation. Last, we outline concrete features we plan to implement in the future to extend PyGB.

With increasing demand for distributed intelligent physical systems performing big data analytics on the field and in real-time, processing-in-memory (PIM) architectures integrating 3D-stacked memory and logic layers could provide higher performance and energy efficiency. Towards this end, the PIM design requires principled and rigorous optimization strategies to identify interactions and manage data movement across different vaults. In this paper, we introduce Prometheus, a novel PIM-based framework that constructs a comprehensive model of computation and communication (MoCC) based on a static and dynamic compilation of an application. Firstly, by adopting a low level virtual machine (LLVM) intermediate representation (IR), an input application is modeled as a two-layered graph consisting of (i) a computation layer in which the nodes denote computation IR instructions and edges denote data dependencies among instructions, and (ii) a communication layer in which the nodes denote memory operations (e.g., load/store) and edges represent memory dependencies detected by alias analysis. Secondly, we develop an optimization framework that partitions the multi-layer network into processing communities within which the computational workload is maximized while balancing the load among computational clusters. Thirdly, we propose a community-to-vault mapping algorithm for designing a scalable hybrid memory cube (HMC)-based system where vaults are interconnected through a network-on-chip (NoC) approach rather than a crossbar architecture. This ensures scalability to hundreds of vaults in each cube. Experimental results demonstrate that Prometheus consisting of 64 HMC-based vaults improves system performance by 9.8x and achieves 2.3x energy reduction, compared to conventional systems.

Register allocation is a mandatory task for almost every compiler and consumes a significant portion of compile time. In a just-in-time compiler, compile time is a particular issue because compilation happens during program execution and contributes to the overall application run time. Parallelization can help here. We developed a theoretical model for parallel register allocation and show that it can be used in practice without a negative impact on the quality of the allocation result. Doing so reduces compilation latency, i.e., the duration until the result of a compilation is available.Our analysis shows that parallelization can theoretically decrease allocation latency by almost 50%. We implemented an initial prototype which reduces the register allocation latency by 28% when using four threads, compared to the single-threaded allocation.

The so-called Notification-Oriented Paradigm (NOP) is a new technique to develop software. NOP is a rule-oriented approach where each rule and fact-base element is split in small entities. These entities particularly collaborate by means of precise notifications only when their state changes. This allows carrying out an inference process free of structural and temporal redundancies. Due to its peculiar properties, NOP tends to be an alternative to achieve suitable performance in program execution, easiness in codification level, and appropriate code modularity, structuration and decoupling. In order to validate these supposed features, a framework was implemented in C++. Even though it quite demonstrated the features of the paradigm in terms of execution performance and development process, it still presented a gap therein. In this context, this paper presents a preliminary programming language and compiler to explore NOP features. This new approach simplifies the development in NOP and speedup execution performance.

Modern compilers provide code optimizations before and during run-time, thus moving required domain knowledge about the compilation process away from the developer and speeding up resulting software. These optimizations are often based on formal proof, or alternatively have recovery paths as backup. Genetic improvement (GI), a field of science utilizing genetic programming, a stochastic optimization technique, has been previously utilized to fix bugs in software and improve non-functional software requirements. This work proposes to research the applicability of GI in an offline phase directly at the interpreter or compiler level. The primary goal is to reformulate existing source code in such a way that existing optimizations can be applied in order to increase performance even further and requiring even less domain knowledge from the developer about a programming language and/or compiler. From these reformulations, patterns can be identified that allow code restructuring without the overhead GI poses.

Virtual Machines (VMs) with Just-In-Time (JIT) compilers are traditionally thought to execute programs in two phases: the initial warmup phase determines which parts of a program would most benefit from dynamic compilation, before JIT compiling those parts into machine code; subsequently the program is said to be at a steady state of peak performance. Measurement methodologies almost always discard data collected during the warmup phase such that reported measurements focus entirely on peak performance. We introduce a fully automated statistical approach, based on changepoint analysis, which allows us to determine if a program has reached a steady state and, if so, whether that represents peak performance or not. Using this, we show that even when run in the most controlled of circumstances, small, deterministic, widely studied microbenchmarks often fail to reach a steady state of peak performance on a variety of common VMs. Repeating our experiment on 3 different machines, we found that at most 43.5% of pairs consistently reach a steady state of peak performance., Comment: 40 pages, 11 figures, 9 tables, 3 listings

The Java®HotSpot Virtual Machine includes a multi-tier compilation system that may invoke a compiler at any time. Lower tiers instrument the program to gather information for the highly optimizing compiler at the top tier, and this compiler bases its optimizations on these profiles. But if the assumptions made by the top-tier compiler are proven wrong (e.g., because the profile does not cover all execution paths), the method is deoptimized: the code generated for the method is discarded and the method is then executed at Tier 0 again. Eventually, after profile information has been gathered, the method is recompiled at the top tier again (this time with less-optimistic assumptions). Users of the system experience such deoptimization cycles (discard, profile, compile) as performance fluctuations and potentially as variations in the system's responsiveness. Unpredictable performance however is problematic in many time-critical environments even if the system is not a hard real-time system.A profile cache captures the profile of earlier executions. When the application is executed again, with a fresh VM, the top tier (highly optimizing) compiler can base its decisions on a profile that reflects prior executions and not just the recent history observed during this run. We report in this paper the design and effectiveness of a profile cache for Java applications which is implemented and evaluated as part of the multi-tier compilation system of the HotSpot Java Virtual Machine in OpenJDK version 9. For a set of benchmarks, profile caching reduces the number of (re)compilations by up to 23%, the number of deoptimizations by up to 90%, and thus improves performance predictability.

Register allocation is an integral part of compilation, regardless of whether a compiler aims for fast compilation or optimal code quality. State-of-the-art dynamic compilers often use global register allocation approaches such as linear scan. Recent results suggest that non-global trace-based register allocation approaches can compete with global approaches in terms of allocation quality. Instead of processing the whole compilation unit (i.e., method) at once, a trace-based register allocator divides the problem into linear code segments, called traces.In this work, we present a register allocation framework that can exploit the additional flexibility of traces to select different allocation strategies based on the characteristics of a trace. This provides us with fine-grained control over the trade-off between compile time and peak performance in a just-in-time compiler.Our framework features three allocation strategies: a linear-scan-based approach that achieves good code quality, a single-pass bottom-up strategy that aims for short allocation times, and an allocator for trivial traces.To demonstrate the flexibility of the framework, we select 8 allocation policies and show their impact on compile time and peak performance. This approach can reduce allocation time by 7%--43% at a peak performance penalty of about 1%--11% on average.For systems that do not focus on peak performance, our approach allows to adjust the time spent for register allocation, and therefore the overall compilation time, thus finding the optimal balance between compile time and peak performance according to an application's requirements.

Just-in-time (JIT) compilation during program execution and ahead-of-time (AOT) compilation during software installation are alternate techniques used by managed language virtual machines (VM) to generate optimized native code while simultaneously achieving binary code portability and high execution performance. Profile data collected by JIT compilers at run-time can enable profile-guided optimizations (PGO) to customize the generated native code to different program inputs. AOT compilation removes the speed and energy overhead of online profile collection and dynamic compilation, but may not be able to achieve the quality and performance of customized native code. The goal of this work is to investigate and quantify the implications of the AOT compilation model on the quality of the generated native code for current VMs. First, we quantify the quality of native code generated by the two compilation models for a state-of-the-art (HotSpot) Java VM. Second, we determine how the amount of profile data collected affects the quality of generated code. Third, we develop a mechanism to determine the accuracy or similarity for different profile data for a given program run, and investigate how the accuracy of profile data affects its ability to effectively guide PGOs. Finally, we categorize the profile data types in our VM and explore the contribution of each such category to performance.

The traditional C, C ++, Java compiler system are large and integrate a large number of libraries and frameworks, allowing developers to use conveniently, are not conducive to understand the compiler theory and technology. In this paper, aiming at the above problems, we research a simple structure of code compiler technology, developed a simple compiler system with common sense, making the reader better learn compiler theory and technology and increasing the interest of this course. Firstly, the main features and applications what Tina interpreter were discussed, and the analysis and discussion of the implementation process. The actual situation in the field of researching, proposed Tina compiler which is the design method of this solution. Secondly, from code structure and format of Tina, it analyzes the common lexical, grammatical problems. Research on the compiler technology, control structures and procedures, parsing judgment for detailed analysis. Compilation process is divided into lexical analysis, syntax analysis and code generation three processing stages,which let the Windows system as the development platform and let C language as development tools and use recursive technique and the data structure of lists and queue and stacks implementing the three modules of the specific design.

Just-in-time compilers and their aggressive speculative optimizations reduced the performance gap between dynamic and static languages drastically. To successfully speculate, compilers rely on the program variability observed at run time to be low, and use heuristics to determine when optimization is beneficial. However, some variability patterns are hard to capture with heuristics. Specifically, ephemeral, warmup, rare, and highly indirect variability are challenges for today's compiler heuristics. As a consequence, they can lead to reduced application performance. However, these types of variability are identifiable at the application level and could be mitigated with information provided by developers. As a solution, we propose a metaobject protocol for dynamic compilation systems to enable application developers to provide such information at run time. As a proof of concept, we demonstrate performance improvements for a few scenarios in a dynamic language built on top of the Truffle and Graal system.

Due to the increasing complexity of software systems, model-driven engineering has been introduced to shift the developer's focus from machine-centric program code to human-centric models of the software under development. In model-driven approaches, program code in conventional programming languages (e.g., C++, Java) is commonly generated from models and then compiled or interpreted. Intermediate translation of models to program code raises two fundamental issues: 1) semantic inconsistency and information loss between an executable and its source model, and 2) suboptimality of executables, since compilers are unable to exploit model semantics. These issues are not tolerable in embedded real-time and safety-critical applications. To tame them, we propose direct compilation of models bypassing intermediate translations to conventional programming languages.

Measuring the time spent on small individual fractions of program code is a common technique for analysing performance behavior and detecting performance bottlenecks. The benefits of the approach include a detailed individual attribution of performance and understandable feedback loops when experimenting with different code versions. There are however severe pitfalls when following this approach that can lead to vastly misleading results. Modern dynamic compilers use complex optimisation techniques that take a large part of the program into account. There can be therefore unexpected side-effects when combining different code snippets or even when running a presumably unrelated part of the code. This talk will present performance paradoxes with examples from the domain of dynamic compilation of Java programs. Furthermore, it will discuss an alternative approach to modelling code performance characteristics that takes the challenges of complex optimising compilers into account.

This paper describes how the latest CakeML compiler supports verified compilation down to multiple realistically modelled target architectures. In particular, we describe how the compiler definition, the various language semantics, and the correctness proofs were organised to minimize target-specific overhead. With our setup we have incorporated compilation to four 64-bit architectures, ARMv8, x86-64, MIPS-64, RISC-V, and one 32-bit architecture, ARMv6. Our correctness theorem allows interference from the environment: the top-level correctness statement takes into account execution of foreign code and per-instruction interference from external processes, such as interrupt handlers in operating systems. The entire CakeML development is formalised in the HOL4 theorem prover.

Despite meriting the growing consensus between researchers and practitioners of ontology modeling, the Web Ontology Language OWL still has a modest presence in the communities of “traditional” web developers and software engineers. This resulted in hoarding the semantic web field in a rather small circle of people with a certain profile of expertise. In this paper we present OntoJIT, our novel approach toward a democratized semantic web where we bring OWL ontologies into the comfort-zone of end-application developers. We focus particularly on parsing OWL source files into executable ontologies in an object oriented programming paradigm. We finally demonstrate the dynamic code-base created as the result of parsing some reference OWL DL ontologies.

There are many domain libraries, but despite the performance benefits of compilation, domain-specific languages are comparatively rare due to the high cost of implementing an optimizing compiler. We propose commensal compilation, a new strategy for compiling embedded domain-specific languages by reusing the massive investment in modern language virtual machine platforms. Commensal compilers use the host language's front-end, use host platform APIs that enable back-end optimizations by the host platform JIT, and use an autotuner for optimization selection. The cost of implementing a commensal compiler is only the cost of implementing the domain-specific optimizations. We demonstrate the concept by implementing a commensal compiler for the stream programming language StreamJIT atop the Java platform. Our compiler achieves performance 2.8 times better than the StreamIt native code (via GCC) compiler with considerably less implementation effort., United States. Dept. of Energy. Office of Science (X-Stack Award DE-SC0008923), Intel Corporation (Science and Technology Center for Big Data), SMART3 Graduate Fellowship

Programming heterogeneous MPSoCs (Multi-Processor Systems on Chip) is a grand challenge for embedded SoC providers and users today. In this paper, we argue for the need and significance of positioning the language and tool design from the perspective of practicality to address this challenge. We motivate, describe and justify such a practical design of a compilation framework for heterogeneous MPSoCs targeting the domain of streaming applications, named MAPS (MPSoC Application Programming Studio). MAPS defines a clean, light-weight C language extension to capture streaming programming models. A retargetable source-to-source compiler is developed to provide key capabilities to construct practical compilation frameworks for real-world, complex MPSoC platforms. Our results have shown that MAPS is a promising compiler infrastructure that enables programming of heterogeneous MPSoCs and increases productivity of MPSoC software developers.

The dataflow programming paradigm shows an important way to improve programming productivity for streaming systems. In this paper we propose COStream, a programming language based on synchronous data flow execution model for data-driven application. We also propose a compiler framework for COStream on general-purpose multi-core architectures. It features an inter-thread software pipelining scheduler to exploit the parallelism among the cores. We implemented the COStream compiler framework on x86 multi-core architecture and performed experiments to evaluate the system.

Dynamically typed programming languages have become very popular in recent years. These languages ease the task of programmers but introduce significant runtime overheads since variables are neither declared nor bound to a particular type. In particular, every time an object property is accessed, we have to obtain the type of the object to which it belongs just before the access, in order to properly compute the address of the property. This adds an important overhead to each of these accesses. In this paper, we present ERICO, a hybrid HW/SW mechanism that removes most of this overhead. This technique is based on a runtime-built structure that provides the information required to identify the addresses of object properties in a very efficient manner. Besides, a hardware cache of this structure stores its most frequently used elements to speedup its access. To demonstrate the effectiveness of this new mechanism, we implement it in a JavaScript engine and show that on average it produces 11% speedup (up to 31% for some applications) and 10.6% energy reduction.

With the fast development of science and technology, as an emerging Web technology, JSP provides quality tools for professionals and non-professionals to develop high-level web sites. But, currently there are few visualized learning tools about JSP compiling, the most are written interpretations, which offers no intuitive sense for the learners. Aimed at this situation, the compiler compiled a standalone version of the basic learning software of JSP compiling by integrating what have learned and conforming the relative contents. This software contains rudiments, viewing courseware, experimental video, focused explanation, dynamic compiling, exercise, online test, help, etc., besides, the interface is simple and pleasing to the eye, the content is solid and comprehensive, and the operation is convenient and swift, which furnishes the JSP fans with a good guide. Specially, the dynamic compiling module provides the visualized compilation process which could effectively help the users understanding the dynamic compilation process of JSP.

Dynamic or Just-in-Time (JIT) compilation is essential to achieve high-performance emulation for programs written in managed languages, such as Java and C#. It has been observed that a conservative JIT compilation policy is most effective to obtain good runtime performance without impeding application progress on single-core machines. At the same time, it is often suggested that a more aggressive dynamic compilation strategy may perform best on modern machines that provide abundant computing resources, especially with virtual machines (VMs) that are also capable of spawning multiple concurrent compiler threads. However, comprehensive research on the best JIT compilation policy for such modern processors and VMs is currently lacking. The goal of this work is to explore the properties of single-tier and multitier JIT compilation policies that can enable existing and future VMs to realize the best program performance on modern machines. In this work, we design novel experiments and implement new VM configurations to effectively control the compiler aggressiveness and optimization levels ( if and when methods are compiled) in the industry-standard Oracle HotSpot Java VM to achieve this goal. We find that the best JIT compilation policy is determined by the nature of the application and the speed and effectiveness of the dynamic compilers. We extend earlier results showing the suitability of conservative JIT compilation on single-core machines for VMs with multiple concurrent compiler threads. We show that employing the free compilation resources (compiler threads and hardware cores) to aggressively compile more program methods quickly reaches a point of diminishing returns. At the same time, we also find that using the free resources to reduce compiler queue backup (compile selected hot methods early ) significantly benefits program performance, especially for slower (highly optimizing) JIT compilers. For such compilers, we observe that accurately prioritizing JIT method compiles is crucial to realize the most performance benefit with the smallest hardware budget. Finally, we show that a tiered compilation policy, although complex to implement, greatly alleviates the impact of more and early JIT compilation of programs on modern machines.

Compile-time metaprograms are programs executed during the compilation of a source file, usually targeting to update its source code. Even though metaprograms are essentially programs, they are typically treated as exceptional cases without sharing common practices and development tools. Toward this direction, we identify a set of primary requirements related to language implementation, metaprogramming features, software engineering support, and programming environments and elaborate on addressing these requirements in the implementation of a metaprogramming language. In particular, we introduce the notion of integrated compile-time metaprograms, as coherent programs assembled from specific metacode fragments present in the source code. We show the expressiveness of this programming model and illustrate its advantages through various metaprogram scenarios. Additionally, we present an integrated tool chain, supporting full-scale build features and compile-time metaprogram debugging. Copyright © 2013 John Wiley & Sons, Ltd.

This paper studies the application programming interface in configuration software. Based on comprehensively considering softwares application, a mini-message bus configuration languageMMBCL language is designed by using C language, whose compiler and development environment are fulfilled. The designing, syntax analysis, semantic analysis of MMBCL are deeply discussed. This configuration language is simple, similar to C language, easy to write, consistent with industrial control standard. And it has successfully applied to the industrial project and proves the efficiencies of the configuration language and the compiler.

In this article, we consider the semantic design and verified compilation of a C-like programming language for concurrent shared-memory computation on x86 multiprocessors. The design of such a language is made surprisingly subtle by several factors: the relaxed-memory behavior of the hardware, the effects of compiler optimization on concurrent code, the need to support high-performance concurrent algorithms, and the desire for a reasonably simple programming model. In turn, this complexity makes verified compilation both essential and challenging. We describe ClightTSO, a concurrent extension of CompCert’s Clight in which the TSO-based memory model of x86 multiprocessors is exposed for high-performance code, and CompCertTSO, a formally verified compiler from ClightTSO to x86 assembly language, building on CompCert. CompCertTSO is verified in Coq: for any well-behaved and successfully compiled ClightTSO source program, any permitted observable behavior of the generated assembly code (if it does not run out of memory) is also possible in the source semantics. We also describe some verified fence-elimination optimizations, integrated into CompCertTSO.

The main reason for the invention of computer programming languages is for these languages to express a command-to-control machine behavior. Some of these programming languages have specific advantages that are used in specific environments such as structured query language (SQL), hypertext markup language (HTML), and spreadsheet. The common definitions of these languages are domain-specific languages (DSLs). Although DSLs are the best way to deal with specific systems, it is hard to use with other environments or platforms. Groovy is a dynamic programming language that runs on the Java virtual machine. Groovy has some features that allow programmers to manage DSLs within its unique style. Groovy has some disadvantages because it does not support all Java features and syntax while also producing unnecessary byte code during compilation. This paper proposes an extended-architecture technique to implement a computer programming language and compiler through extending Java with Groovy language. The extensible language is called ‘JGroovy’. And JGroovy is supported both by Java and Groovy language. We implement the compiler for JGroovy and call it the ‘JGroovy compiler’ (JGC). By its extended architecture, JGC is more compatible for Java source code than Javac can claim to be. And it also produces a better and more compact byte code than the Groovy compiler, with an approximate improvement of 8–12%. © 2013 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.