Macro systems are powerful language extension tools for Architecture Description Languages (ADLs). Their generative power in combination with the simplicity of specification languages allows for a substantial reduction of repetitive specification sections. This paper explores how the introduction of function- and record types in a template-based macro system impacts the specification of ADLs. We present design and implementation of a pattern-based syntax macro system for the Vienna Architecture Description Language (VADL). The macro system is directly integrated into the language and is analyzed at parse time using a context-sensitive pred-LL(*) parser. The usefulness of the macro system is illustrated by some typical macro application design patterns. The effectiveness is shown by a detailed evaluation of the Instruction Set Architecture (ISA) specification of five different processor architectures. The observed specification reduction can be up to 90 times, leading to improved maintainability, readability and runtime performance of the specifications.

Tree-parsing instruction selection as used in, e.g., lcc, uses dynamic costs to gain flexibility and handle situations (such as read-modify-write instructions) that do not fit into the basic tree-parsing model. The disadvantage of dynamic costs is that we can no longer turn the tree grammar into a tree automaton (as is done by burg) for fast instruction selection for JIT compilers. In this paper we introduce constraints that say whether a tree-grammar rule is applicable or not. While theoretically less powerful than dynamic costs, constraints cover the practical uses of dynamic costs; more importantly, they allow turning the tree grammar with constraints into a tree automaton (with instruction-selection-time checks), resulting in faster instruction selection than with pure instruction-selection-time dynamic programming. We integrate constraints in an instruction selector that matches DAGs with tree rules. We evaluate this concept in lcc and the CACAO JavaVM JIT compiler, and see instruction selector speedups by a factor 1.33--1.89.

PyPy is a widely known virtual machine for the Python programming language. PyPy itself is implemented in the statically typed subset of Python called RPython. RPython includes a tracing Just-In-Time (JIT) compiler and is capable of generating the compiler for a language from the specification of the interpreter for that language. In PyPy 4.0.0 we extended the tracing JIT compiler to support vectorization of loops and emit code for the SSE4 vector operations of the x86 instruction set. This article presents the details of the new vectorizer of PyPy. The vectorizer uses a loop unrolling approach to vectorization. It has been designed for efficient compilation as the compilation is done during the execution of the application. The scientific library NumPy introduced arrays which are homogeneous, primitive typed and contiguous in memory. These kind of arrays are used to avoid the problems with dynamic typing. Our contribution to PyPy's new vectorizer supports scalar and constant expansion, accumulator splitting for reductions, guard strengthening and array bounds check removal. The empirical evaluation shows that the vectorizer can gain speedups close to the theoretical optimum of the SSE4 instruction set.

In this paper we present CASM, a language based on Abstract State Machines (ASM), and its optimizing compiler. ASM is a well-defined (formal) method based on algebraic concepts. A distinct feature of ASM is its combination of parallel and sequential execution semantics. This makes it an excellent choice to formally specify and verify micro-architectures. We present a compilation scheme and an implementation of a runtime system supporting efficient execution of ASM.

SUMMARY Application‐specific instruction set processors have proven successful in meeting the various design constraints of modern embedded systems and often provide the only viable trade‐off between computing power and opposing metrics such as power consumption. A promising approach to facilitate the exploration of processor design alternatives are processor description languages, which capture the instruction set and hardware organization of a processor. With the use of those processor models, various design tasks, for example, the adaption of software development tools, the generation of hardware models, and various verification tasks, can be automatized. These languages thus allow effective shortening of development turnaround times. In this work, the novel xADL language is presented, which, in contrast to most contemporary processor description languages, focuses on a structural modeling of the processor's hardware organization. However, a behavioral model of the instruction set is automatically derived using instruction set extraction. This provides a tight coupling between the structural hardware view and the instruction set view of the processor and reduces the complexity of processor models in comparison with existing languages. The feasibility of our approach is demonstrated by a compiler backend generator based on tree pattern matching. An important property of our generator is its ability to automatically verify whether the resulting compiler is complete, that is, it can process all possible input programs. The generated compilers are competitive to handcrafted production compilers, showing speedups of up to 20%for certain benchmarks. On average, moderate slowdowns between 3%and 15%have been observed for several processor models while considerable reductions in code size have been measured. Copyright © 2012 John Wiley & Sons, Ltd.

In times of ever-growing system complexity and thus increasing possibilities for errors, high-quality requirements are crucial to prevent design errors in later project phases and to facilitate design verification and validation. To ensure and improve the consistency, completeness and correctness of requirements, formal languages have been introduced as an alternative to using natural language (NL) requirement descriptions. However, in many cases existing NL requirements must be taken into account. The formalization of those requirements by now is a primarily manual task, which therefore is both cumbersome and error-prone. We introduce the tool DODT that semi-automatically transforms NL requirements into semi-formal boilerplate requirements. The transformation builds upon a domain ontology (DO) containing knowledge of the problem domain and upon natural language processing techniques. The tool strongly reduced the required manual effort for the transformation. In addition the quality of the requirements was improved.

Various shape analysis algorithms have been introduced but their relation in terms of precision often remains unclear as different analyses use different representations of analysis results. The aim of our work is to extract alias sets from shape analysis results to compute a relative precision factor that expresses for a given program how much more precise one analysis is than the other. We present a significant improvement over an existing algorithm based on 3-valued logic to compute alias sets from shape graphs. Instead of looking only at the final nodes in pointer access paths, our common tail algorithm takes sequences of selectors into account. The common tail algorithm is strictly more precise than the existing algorithm by Reps, Sagiv, and Wilhelm, for our benchmarks we can reduce the number of conservative results by a factor of up to 5 in the best case while incurring an additional analysis overhead that is below 10% even in the worst case of our benchmarks. We selected two well-known graph-based shape analyses that use different representations of analysis results to demonstrate the usefulness of our approach. The shape analysis proposed by Nielson, Nielson & Hankin (NNH) and the analysis by Sagiv, Reps & Wilhelm (SRW) were implemented for a subset of C++ in the SATIrE program analysis framework. We are thus able to determine that NNH is more precise than SRW by a factor of 1.62 on average for our set of benchmarks.

Register allocation has gained renewed attention in the recent past. Several authors propose a separation of the problem into decoupled sub-tasks including spilling, allocation, assignment, and coalescing. This approach is largely motivated by recent advances in SSA-based register allocation that suggest that a decomposition does not significantly degrade the overall allocation quality.

Instruction selection is a well-studied compiler phase that translates the compiler's intermediate representation of programs to a sequence of target-dependent machine instructions optimizing for various compiler objectives (e.g. speed and space). Most existing instruction selection techniques are limited to the scope of a single statement or a basic block and cannot cope with irregular instruction sets that are frequently found in embedded systems.

With increasing complexity of modern embedded systems, the availability of highly optimizing compilers becomes more and more important. At the same time, application specific instruction-set processors (ASIPs) are used to fine-tune hardware platforms to the intended application, demanding the availability of retargetable components throughout thewhole tool chain.

Abstract To achieve maximum efficiency, modern embedded processors for media applications exploit single instruction multiple data (SIMD) instructions. SIMD instructions provide a form of vectorization where a large machine word is viewed as a vector of subwords and the same operation is performed on all subwords in parallel. Systematic usage of SIMD instructions can significantly improve program performance. With C becoming the dominant language for programming embedded devices, there is a clear need for C compilers that use SIMD instructions whenever appropriate. However, SIMD instructions typically require each memory access to be aligned with the instruction's data access size. Therefore an important problem in designing the compiler is to determine whether a C pointer is aligned, i.e. whether it refers to the beginning of a machine word. In this paper, we describe our SIMD generation algorithm and present an analysis method which determines the alignment of pointers at compile time. The alignment information is used to reduce the number of dynamic alignment checks and the overhead incurred by them. Our method uses an interprocedural analysis which propagates pointer alignment information in function bodies and through function calls. The effectiveness of our method is supported by experimental results which show that in typical programs the alignments of about 50% of the pointers can be statically determined. Copyright © 2006 John Wiley & Sons, Ltd.

Embedded systems have an extremely short time to market and therefore require easily retargetable compilers. Architecture description languages (ADLs) provide a single concise architecture specification for the generation of hardware, instruction set simulators and compilers. In this article, we present an ADL for compiler generation. From a specification, we can derive an optimized tree pattern matching instruction selector, a register allocator and an instruction scheduler. Compared to a hand-crafted back end, the generated compiler produces smaller and faster code.The ADL is rich enough that other tools, such as assemblers, linkers, simulators and documentation, can all be obtained from a single specification.

Abstract In a virtual machine interpreter, the code for each virtual machine instruction has similarities to code for other instructions. We present an interpreter generator that takes simple virtual machine instruction descriptions as input and generates C code for processing the instructions in several ways: execution, virtual machine code generation, disassembly, tracing, and profiling. The generator is designed to support efficient interpreters: it supports threaded code, aching the top‐of‐stack item in a register, combining simple instructions into superinstructions, and other optimizations. We have used the generator to create interpreters for Forth and Java. Theresulting interpreters are faster than other interpreters for the same languages and they are typically 2–10 times slower than code produced by native‐code compilers. We also present results for the effects of the individual optimizations supported by the generator. Copyright © 2002 John Wiley & Sons, Ltd

Efficient implementation of monitors and exceptions is crucial for the performance of Java. One implementation of threads showed a factor of 30 difference in runtime on some benchmark programs. This paper describes an efficient implementation of monitors for Java as used in the CACAO just-in-time compiler. With this implementation the thread overhead is less than 40% for typical application programs and can be completely eliminated for some applications. This paper also gives the implementation details of the new exception handling scheme in CACAO. The new approach reduces the size of the generated native code by a half and allows null pointers to be checked by hardware. By using these techniques, the CACAO system has become the fastest JavaVM implementation for the Alpha processor. © 1998 John Wiley & Sons, Ltd.

A type inclusion test determines whether one type is a subtype of another. Efficient type testing techniques exist for single subtyping, but not for languages with multiple subtyping. To date, the fast constant-time technique relies on a binary matrix encoding of the subtype relation with quadratic space requirements. In this paper, we present three new encodings of the subtype relation, the packed encoding, the bit-packed encoding and the compact encoding. These encodings have different characteristics. The bit-packed encoding delivers the best compression rates: on average 85% for real life programs. The packed encoding performs type inclusion tests in only 4 machine instructions. We present a fast algorithm for computing these encoding which runs in less than 13 milliseconds for PE and BPE, and 23 milliseconds for CE on an Alpha processor. Finally, we compare our results with other constant-time type inclusion tests on a suite of 11 large -benchmark hierarchies.

This paper describes the design and implementation of CACAO, a just-in-time compiler for Java. The CACAO system translates Java byte code on demand into native code for the ALPHA processor. During this translation process the stack-oriented Java byte code is transformed into a register-oriented intermediate code. Local variables and stack locations are replaced by pseudo-registers eliminating the 32-bit restriction on address types. A fast register allocation algorithm is applied to map the pseudo-registers to machine registers. During code generation, field offsets are computed for proper alignment on 64-bit architectures. Even though the CACAO system has to incur loading and compilation time, it executes Java programs up to 85 times faster than the JDK interpreter, and up to seven times faster than the kaffe JIT compiler. It is slightly slower than equivalent C programs compiled at the highest optimization level. © 1997 John Wiley & Sons, Ltd.

This paper studies the problem of simultaneous register allocation and software pipelining. We present the register requirement graph to dynamically reflect the register requirement during software pipelining and develop a Register-Pressure-Sensitive (RPS) scheduling technique. Three algorithms-RPS without spilling, RPS with spilling and software pipelining with a limited number of registers-are proposed. The preliminary experimental results show the efficiency of the three algorithms.

Speculative execution on superscalar processors demands substantially better branch prediction than what has been previously available. In this paper we present code replication techniques that improve the accuracy of semi-static branch prediction to a level comparable to dynamic branch prediction schemes. Our technique uses profiling to collect information about the correlation between different branches and about the correlation between the subsequent outcomes of a single branch. Using this information and code replication the outcome of branches is represented in the program state. Our experiments have shown that the misprediction rate can almost be halved while the code size is increased by one third.