Search

Στην παρούσα διδακτορική διατριβή παρουσιάζεται ένας μεταγλωττιστής της γλώσσας MATLAB ο οποίος παράγει κώδικα C αξιοποιώντας εντολές ειδικού σκοπού του εκάστοτε επεξεργαστή στόχου όπως εντολές επεξεργασίας πολλαπλών δεδομένων (SIMD) και βαθμωτές (scalar) εντολές μαθηματικών συναρτήσεων/λειτουργιών που υποστηρίζονται από το υλικό. Ο μεταγλωττιστής παράγει ANSI C κώδικα και οι εντολές ειδικού σκοπού αναπαρίστανται από εσωτερικές (intrinsic) συναρτήσεις επιτρέποντας τη συμβατότητα του μεταγλωττιστή σε οποιοδήποτε επεξεργαστή (και το μεταγλωττιστή του).Αρχικά, παρουσιάζεται ένα παραμετρικό μοντέλο επεξεργαστή, το οποίο χρησιμοποιείται για την περιγραφή των εντολών ειδικού σκοπού. Το μοντέλο αυτό επιτρέπει την περιγραφή εξειδικευμένων εντολών, λειτουργίες εισαγωγής δεδομένων σε διανύσματα (packing) για παράλληλη επεξεργασία και εσωτερικές δομές δεδομένων όπως οι τύποι δεδομένων των διανυσμάτων ενός επεξεργαστή. Το μοντέλο επεξεργαστή χρησιμοποιείται από έναν αλγόριθμο επιλογής εντολών (instruction selection) με σκοπό να αντιστοιχήσει τον πηγαίο κώδικα εισόδου με τις διαθέσιμες μονάδες του υλικού της αρχιτεκτονικής-στόχου. Το μοντέλο του επεξεργαστή χρησιμοποιείται επίσης από το στάδιο της εξαγωγής τύπων δεδομένων (type inference) ώστε να εξάγεται ο τύπος του αποτελέσματος των συναρτήσεων που αναπαριστόνται από εντολές ειδικού σκοπού. Το παραμετρικό μοντέλο επεξεργαστή διαμορφώνει ένα πλαίσιο μεταγλώττισης υποστηρίζοντας διαφορετικούς επεξεργαστές-στόχους κάτι που έχει ως αποτέλεσμα την παραγωγή βελτιστοποιημένου κώδικα για οποιαδήποτε αρχιτεκτονική.Στην συνέχεια, περιγράφεται η υποδομή του μεταγλωττιστή με έμφαση στα τμήματα υποστήριξης της παράλληλης επεξεργασίας δεδομένων και παραγωγής διανυσματικού Cκώδικα. Αρχικά, παρουσιάζεται ο αλγόριθμος επιλογής εντολών ο οποίος αντιστοιχίζει τις εντολές και συναρτήσεις MATLAB με τις εντολές ειδικού σκοπού της αρχιτεκτονικής-στόχου. Ο αλγόριθμος επιλέγει την κατάλληλη από τις εντολές που περιλαμβάνονται στο μοντέλο του επεξεργαστή. Στη συνέχεια, λειτουργίες εισαγωγής και εξαγωγής δεδομένων σε μεταβλητές διανύσματα εισάγονται στην ενδιάμεση αναπαράσταση για να επιτρέψουν την παραγωγή κώδικα παράλληλης επεξεργασίας. Η διαδικασία αφορά την εισαγωγή των συγκεκριμένων λειτουργιών ώστε να μετατρέπονται τα δεδομένα σε κατάλληλη μορφή για παράλληλη επεξεργασία. Στη συνέχεια, ένας αλγόριθμος αρίθμησης των τοπικών μεταβλητών (local value numbering) εκτελείται με σκοπό την αφαίρεση από την ενδιάμεση αναπαράσταση των περιττών λειτουργιών εισαγωγής/εξαγωγής δεδομένων σε διανύσματα οι οποίες εισάγονται από το προηγούμενο στάδιο μεταγλώττισης. Τέλος, περιγράφεται το στάδιο παραγωγής κώδικα, εστιάζοντας στην παραγωγή κώδικα για παράλληλη επεξεργασίας δεδομένων και την παραγωγή κώδικα για τύπους δεδομένων σταθερής υποδιαστολής. Η παραγωγή διανυσματικού κώδικα περιλαμβάνει την παραγωγή βρόχων οι οποίοι αναπαριστούν τα τμήματα του κώδικα που περιλαμβάνουν διανυσματικές εντολές ειδικού σκοπού, την παραγωγή λειτουργιών εισαγωγής/εξαγωγής δεδομένων σε διανύσματα καθώς επίσης και τις εντολές παράλληλης επεξεργασίας. Η παραγωγή κώδικα για τύπους δεδομένων σταθερής υποδιαστολής αφορά την παραγωγή επιπλέον C κώδικα για τη διαχείριση της αριθμητικής δεδομένων σταθερής υποδιαστολής (π.χ. λειτουργίες ολίσθησης). Ο μεταγλωττιστής υποστηρίζει την παράλληλη επεξεργασία δεδομένων και επιτρέπει την παραγωγή διανυσματικού κώδικα αξιοποιώντας τις εντολές ειδικού σκοπού του εκάστοτε επεξεργαστή-στόχου. Ο παραγόμενος κώδικας επιτυγχάνει αξιοσημείωτη βελτίωση ως προς το χρόνο εκτέλεσης έναντι άλλων τεχνικών οι οποίες δεν παράγουν διανυσματικό κώδικα και/ή δεν αξιοποιούν εντολές ειδικού σκοπού ενός επεξεργαστή.Στην παρούσα διδακτορική διατριβή παρουσιάζεται επίσης η αξιολόγηση του μεταγλωττιστή σε διαφορετικές αρχιτεκτονικές. Για την αξιολόγηση του μεταγλωττιστή χρησιμοποιήθηκαν δύο επεξεργαστές ειδικών εφαρμογών (ASIP) εκ των οποίων ο ένας περιλαμβάνει εντολές επεξεργασίας πολλαπλών δεδομένων, και τέσσερις επεξεργαστές αρχιτεκτονικών ARM και x86. Για την αξιολόγηση του μεταγλωττιστή, χρησιµοποιήθηκαν οκτώ εφαρμογές ψηφιακής επεξεργασίας σήματος χρησιμοποιώντας διαφορετικά πλάτη παραλληλίας, τύπους δεδομένων κινητής και σταθερής υποδιαστολής καθώς επίσης και τύπους/μορφές δεδομένων για παράλληλη επεξεργασία. Η απόδοση ως προς το χρόνο εκτέλεσης του παραγόμενου κώδικα συγκρίθηκε με την απόδοση του κώδικα που παράγεται από τον MathWorks Coder. Ο προτεινόμενος μεταγλωττιστής επιτυγχάνει σημαντική βελτίωση της απόδοσης (ταχύτητας) σε όλες τις εξεταζόμενες αρχιτεκτονικές και ειδικά όταν χρησιμοποιούνται εντολές επεξεργασίας πολλαπλών δεδομένων. Επιπλεόν πραγματοποιήθηκαν δοκιμές για την αξιολόγηση της αυτόματης διανυσματοποίησης κώδικα (auto-vectorization) από δημοφιλείς μεταγλωττιστές της γλώσσας C όπως οι Clang/LLVM, GCC και MSVC. Οι δοκιμές πραγματοποιήθηκαν στους κώδικες οι οποίοι παράγονται από τον MathWorks Coder και τον προτεινόμενο μεταγλωττιστή. Τα πειραματικά αποτελέσματα έδειξαν ότι οι C μεταγλωττιστές διανυσματοποιουν ένα μικρό ποσοστό των βρόχων που μπορούν πραγματικά να διανυσματοποιηθούν οδηγώντας στο συμπέρασμα ότι οι μονάδες των επεξεργαστών που υποστηρίζουν την παράλλήλη επεξεργασία δεδομένων δεν μπορούν να αξιοποιηθούν πλήρως από αυτούς. Αντίθετα ο προτεινόμενος μεταγλωττιστής υποστηρίζει μια ευρύτερη κατηγορία περιπτώσεων.

Dynamic languages such as Perl, Python, JavaScript, Ruby, and PHP are becoming increasingly popular. Many dynamic language implementers choose a layered approach, where a guest language runs on a host virtual machine (VM), while implementing their language. Implementers have two possible execution choices on a host VM: hosted interpreters and host VM targeted compilers. Hosted interpreters run as a regular application on a host VM, whereas, host VM targeted compilers translate the hosted language programs to host VM's instruction set, and execute it on the host VM. Hosted interpreters are comparatively simpler to implement but suffer from poor performance. On the other hand, host VM targeted compilers are complex to build but lead to better performance.In this dissertation, we explore hosted dynamic language interpreters targeting the Java virtual machine (JVM). The purpose of our research is to close the performance gap between hosted interpreters and host VM targeted compilers. Next, we implement a generic, high-performance profiler framework for hosted dynamic languages on a Java virtual machine with modest implementation effort. Our framework has a unique feature, which makes it possible to compare and analyze the programs implementing the same algorithms across different dynamic languages.

The efficient implementation of function calls and non-local control transfers is a critical part of modern language implementations and is important in the implementation of everything from recursion, higher-order functions, concurrency and coroutines, to task-based parallelism. In a compiler, these features can be supported by a variety of mechanisms, including call stacks, segmented stacks, and heap-allocated continuation closures. An implementor of a high-level language with advanced control features might ask the question ``what is the best choice for my implementation?'' Unfortunately, the current literature does not provide much guidance, since previous studies suffer from various flaws in methodology and are outdated for modern hardware. In the absence of recent, well-normalized measurements and a holistic overview of their implementation specifics, the path of least resistance when choosing a strategy is to trust folklore, but the folklore is also suspect. This paper attempts to remedy this situation by providing an ``apples-to-apples'' comparison of six different approaches to implementing call stacks and continuations. This comparison uses the same source language, compiler pipeline, LLVM-backend, and runtime system, with the only differences being those required by the differences in implementation strategy. We compare the implementation challenges of the different approaches, their sequential performance, and their suitability to support advanced control mechanisms, including supporting heavily threaded code. In addition to the comparison of implementation strategies, the paper's contributions also include a number of useful implementation techniques that we discovered along the way.

The synchronous model of computation is well suited for real-time systems, because it allows static analysis in order to find and guarantee their reaction times. Todays multi-core systems are becoming the predominant computing platforms. Synchronous programs are typically compiled into single threaded code, which makes them unsuitable for exploiting parallelism of the multi-core platforms. Moreover, static timing analysis becomes highly intractable for multi-core systems. This article proposes a novel methodology that aims at finding the mapping and schedule of synchronous programs that guarantees, statically, reaction times when mapped onto a multi-core system consisting of two types of time-predictable cores. The proposed methodology combines design space exploration based on evolutionary algorithm and scheduling of parts of synchronous programs. It allows minimizing the resource usage in terms of number of cores by finding the mapping and schedule with the guaranteed reaction time for architectures with different number of cores. In particular, we: (a) transform a synchronous program written in synchronous SystemJ to a graph-based model represented with two types of computation nodes suitable for execution on two types of time-predictable cores, (b) perform mapping of computation nodes on a customizable multi-core platform using genetic operations, and (c) generate a resulting static schedule of computation nodes for each mapping as part of the design space exploration. The design flow, from program specification and node mapping to the design space exploration and multi-core scheduling is completely automated.

This article discusses a MATLAB-to-C vectorizing compiler that exploits custom instructions, for example, for Single Instruction Multiple Data (SIMD) processing and instructions for complex arithmetic present in Application-Specific Instruction Set Processors (ASIPs). Custom instructions are represented via specialized intrinsic functions in the generated code, and the generated code can be used as input to any C/C++ compiler supporting the target processor. Furthermore, the specialized instruction set of the target processor is described in a parameterized way using a target processor-independent architecture description approach, thus allowing the support of any processor. The compiler has been used for the generation of application code for two different ASIPs for several benchmarks. The code generated by the compiler achieves a speedup between 2× --74× and 2× --97× compared to the code generated by the MathWorks MATLAB-to-C compiler. Experimental results also prove that the compiler efficiently exploits SIMD custom instructions achieving a 3.3 factor speedup compared to cases where no SIMD processing is used. Thus the compiler can be employed to reduce the development time/effort/cost and time to market through raising the abstraction of application design in an embedded systems/system-on-chip development context.

The Roofline model is widely used to visualize the performance of executed code together with the upper performance bounds given by the memory bandwidth and the processor peak performance. The model can thus provide an insightful visualization of bottlenecks. In this paper, we try to establish realistic bandwidth ceilings for the sparse triangular solve step of PARDISO, a leading sparse direct solver package, which is also part of the Intel MKL library. The performance of the forward and backward substitution process is analyzed and benchmarked for a representative set of sparse matrices on seven modern x86-type multicore architectures and the Knights Landing manycore architecture. It is shown how to accurately measure the necessary quantities also for threaded code, and the measurement approach, its validation, as well as limitations are discussed. Our modeling approach covers the serial and parallel execution phases, allowing for in-socket performance predictions.

Системы программирования со словарной организацией (ФОРТ и ДССП) предоставляют пользователю-программисту уникальную возможность путём наращивания словаря сотворить по сути свой собственный язык программирования. При этом в качестве новых в словарь можно добавлять и такие слова, которые предназначены для управления ходом исполнения программы. В статье подробно рассматриваются приёмы разработки в среде ДССП-ТВМ (версии ДССП для троичной машины) особых процедур для таких слов (команд), которые обеспечивают функционирование добавляемых в язык ДССП своих собственных управляющих конструкций, Programming systems with the dictionary organization (FORTH and DSSP) give to the user programmer a unique opportunity by building of the dictionary to create in fact an own programming lan-guage. As new words it is possible to add to the dictionary also such words which are intended to control the commands flow of program execution. In the article methods of development in the DSSP-TVM (the version of DSSP for the ternary computer) special procedures for such words (commands) which provide functioning of the own control constructions to be added to the DSSP language are considered in detail, №2 (2018)

International audience; This paper introduces the CODECAST tool: an in-browser C language interpreter, paired with an event and voice recorder and player that facilitates teaching and learning to program by synchronizing audio with source code edition, visualization, step by step execution and testing.

Many guest languages are implemented using the Java Virtual Machine (JVM) as a host environment. There are two major implementation choices: custom compilers and so-called hosted interpreters. Custom compilers are complex to build but offer good performance. Hosted interpreters are comparatively simpler to implement but until now have suffered from poor performance. We studied the performance of hosted interpreters and identified common bottlenecks preventing their efficient execution. First, similar to interpreters written in C/C++, instruction dispatch is expensive on the JVM. Second, Java’s semantics require expensive runtime exception checks that negatively affect array performance essential to interpreters. We present two optimizations targeting these bottlenecks and show that the performance of optimized interpreters increases dramatically: we report speedups by a factor of up to 2.45 over the Jython interpreter, 3.57 over the Rhino interpreter, and 2.52 over the JRuby interpreter, respectively. The resulting performance is comparable with that of custom compilers. Our optimizations are enabled by a few simple annotations that require only modest implementation effort; in return, performance increases substantially.

In Chap. 8 we presented a compiler from micro-C to code for an abstract stack machine. In this chapter we describe real machine code in the form of assembly code for the x86 architecture, and show how to compile micro-C programs to such code. Executing micro-C programs translated into real machine code will be much faster, both because it avoids the interpretive overhead incurred by the abstract machine, and because it uses machine registers instead of the stack for expression evaluation.

The previous chapter explored the different programming languages used in Squarespace websites. You learned to recognize the difference between HTML, CSS, and JavaScript and the different roles these languages have within a website. This chapter will explore the tools for working with custom code and the Squarespace code injectors. There are many different places to inject, or add, custom code. However, before we can add custom code you need the right tools for writing the code.

in this paper, we propose a new technique to recommend programmers with high quality parallel code that are similar to a given sequential code. This is done by transforming well-grounded parallel code A into its sequential equivalent B, storing them (A->B) into database, given a sequential code C, search the database for syntactic or semantic similar code B and retrieve its parallel version code A, which can be used as the replacement or reference for the original code C. We also outline our solutions towards realizing this technique and present a preliminary study that shows promising results.

Static textual analysis techniques have been recently applied to process and synthesize source code. The underlying tenet is that important information is embedded in code identifiers and internal code comments. Such information can be analyzed to provide automatic aid for several software engineering activities. To facilitate this line of work, we present STAC, a tool for supporting Static Textual Analysis of Code. STAC is designed as a light-weight stand-alone tool that provides a practical one-stop solution for code indexing. Code indexing is the process of extracting important textual information from source code. Accurate indexing has been found to significantly influence the performance of code retrieval and analysis methods. STAC provides features for extracting and processing textual patterns found in Java, C++, and C# code artifacts. These features include identifier splitting, stemming, lemmatization, and spell-checking. STAC is also provided as an API to help researchers to integrate basic code indexing features into their code.

Important challenges for embedded systems can be addressed by dynamic binary translation. A dynamic binary translator stores translated instructions in a software-managed code cache, which is usually large to minimize overhead. This article shows how to use a small scratchpad memory for the code cache. A small code cache may require frequent code evictions and retranslation, which degrade performance. We propose techniques to reduce the number of instructions inserted by the translator and a way to form fragments that minimizes translated code size. With our techniques, a much smaller code cache can hold a program's translated code working set.

Code quality and compilation speed are two challenges to JIT compilers, while selective compilation is commonly used to trade-off these two issues. Meanwhile, with more and more Java applications running in mobile devices, selective compilation meets many problems. Since these applications always have flat execution profile and short live time, a lightweight JIT technique without losing code quality is extremely needed. However, the overhead of compiling stack-based Java bytecode to heterogeneous register-based machine code is significant in embedded devices. This paper presents a fast and effective JIT technique for mobile devices, building on a register-based Java bytecode format which is more similar to the underlying machine architecture. Through a comprehensive study on the characteristics of Java applications, we observe that virtual registers used by more than 90% Java methods can be directly fulfilled by 11 physical registers. Based on this observation, this paper proposes Swift, a novel JIT compiler on register-based bytecode, which generates native code for RISC machines. After mapping virtual registers to physical registers, the code is generated efficiently by looking up a translation table. And the code quality is guaranteed by the static compiler which is used to generate register-based bytecode. Besides, we design two lightweight optimizations and an efficient code unloader to make Swift more suitable for embedded environment. As the prevalence of Android, a prototype of Swift is implemented upon DEX bytecode which is the official distribution format of Android applications. Swift is evaluated with three benchmarks (SPECjvm98, EmbeddedCaffeineMark3 and JemBench2) on two different ARM SOCs: S3C6410 (armv6) and OMAP3530 (armv7). The results show that Swift achieves a speedup of 3.13 over the best-performing interpreter on the selected benchmarks. Compared with the state-of-the-art JIT compiler in Android, JITC-Droid, Swift achieves a speedup of 1.42.

International audience; This paper presents a non-intrusive method for Objective Caml code coverage analysis. While classic methods rewrite the source code to an instrumented version that will produce traces at runtime, our approach chooses not to rewrite the source code. Instead, we use a virtual machine to monitor instructions execution and produce traces. These low-level traces are used to create a machine code coverage report. Combined with control-flow debug information, they can be analyzed to produce a source code coverage report. The purpose of this approach is to make available a method to generate code coverage analysis with the same binary for testing and for production. Our customized virtual machine respects the same semantics as the original virtual machine; one of its original aspects is that it is implemented in the Objective Caml, the very language we build the tool for.This work is part of the Coverage project, which aims to develop open source tools for safety-critical embedded applications and their code generators.

Based on feedback information, a large number of optimizations can be performed by the compiler. This information actually indicates the changing behavior of the applications and can be used to specialize code accordingly. Code specialization is a way to facilitate the compiler to perform optimizations by providing the information regarding variables in the code. It is however difficult to select the variables which maximize the benefit of specialization. Also the overhead of specialization and code size increase are the main issues while specializing code. This paper suggests a novel method for improving the performance using specialization based on feedback information and analysis. The code is iteratively specialized after selecting candidate variables by using a heuristic, followed by generation of optimized templates. These templates require a limited set of instructions to be specialized at runtime and are valid for a large number of values. The overhead of runtime specialization is further minimized through optimal software cache of template clones whose instantiation can be performed at static compile time. The experiments have been performed on Itanium-II(IA-64) and Pentium-IV processors using icc and gcc compilers. A significant improvement in terms of execution speed and reduction of code size has been achieved for SPEC and FFTW benchmarks.

Traditional Java code generation and instruction fetch path is not efficient, as Java binary code is typically written into the data cache first, and then is loaded into the instruction cache through the shared L2 cache or memory, which takes both time and energy. In this paper, we study three hardware-based code caching strategies, which attempt to write and read the dynamically generated Java code faster and more energy-efficiently. Our experimental results indicate that with proper architectural support, writing code directly into the instruction cache can improve the performance for a variety of Java applications by 9.6% on average, with up to 42.9%. Also, the average energy dissipation of these Java programs can be reduced by 6% with efficient code caching.

Swift is a new, principled approach to building Web applications that are secure by construction. Modern Web applications typically implement some functionality as client-side JavaScript code, for improved interactivity. Moving code and data to the client can create security vulnerabilities, but currently there are no good methods for deciding when it is secure to do so. Swift automatically partitions application code while providing assurance that the resulting placement is secure and efficient. Application code is written as Java-like code annotated with information flow policies that specify the confidentiality and integrity of Web application information. The compiler uses these policies to automatically partition the program into JavaScript code running in the client browser and Java code running on the server. To improve interactive performance, code and data are placed on the client. However, security-critical code and data are always placed on the server. The compiler may also automatically replicate code across the client and server, to obtain both security and performance.

Embedded systems are characterized by the requirement of demanding small memory footprint code. A popular architectural modification to improve code density in RISC embedded processors is to use a reduced bit-width instruction set. This approach reduces the length of the instructions to improve code size. However, having less addressable registers by the reduced instructions, these architectures suffer a slight performance degradation as more reduced instructions are required to execute a given task. On the other hand, 0-operand computers such as stack and queue machines implicitly access their source and destination operands making instructions naturally short. Queue machines offer a highly parallel computation model, unlike the stack model. This paper proposes a novel alternative for reducing code size by using a queue-based reduced instruction set while retaining the high parallelism characteristics in programs. We introduce an efficient code generation algorithm to generate programs for our reduced instruction set. Our algorithm successfully constrains the code to the reduced instruction set with the addition of only 4% extra code, in average. We show that our proposed technique is able to generate about 16% more compact code than MIPS16, 26% over ARM/Thumb, and 50% over MIPS32 code. Furthermore, we show that our compiler is able to extract about the same parallelism than fully optimized RISC code.

Parallax is a novel self-contained code integrity verification approach, that protects instructions by overlapping Return-Oriented Programming (ROP) gadgets with them. Our technique implicitly verifies integrity by translating selected code (verification code) into ROP code which uses gadgets scattered over the binary. Tampering with the protected instructions destroys the gadgets they contain, so that the verification code fails, thereby preventing the adversary from using the modified binary. Unlike prior solutions, Parallax does not rely on code checksumming, so it is not vulnerable to instruction cache modification attacks which affect checksumming techniques. Further, unlike previous algorithms which withstand such attacks, Parallax does not compute hashes of the execution state, and can thus protect code with non-deterministic state. Parallax limits performance overhead to the verification code, while the protected code executes at its normal speed. This allows us to protect performance-critical code, and confine the slowdown to other code regions. Our experiments show that Parallax can protect up to 90% of code bytes, including most control flow instructions, with a performance overhead of under 4%.

Code-reuse attacks such as return-oriented programming (ROP) pose a severe threat to modern software. Designing practical and effective defenses against code-reuse attacks is highly challenging. One line of defense builds upon fine-grained code diversification to prevent the adversary from constructing a reliable code-reuse attack. However, all solutions proposed so far are either vulnerable to memory disclosure or are impractical for deployment on commodity systems. In this paper, we address the deficiencies of existing solutions and present the first practical, fine-grained code randomization defense, called Read actor, resilient to both static and dynamic ROP attacks. We distinguish between direct memory disclosure, where the attacker reads code pages, and indirect memory disclosure, where attackers use code pointers on data pages to infer the code layout without reading code pages. Unlike previous work, Read actor resists both types of memory disclosure. Moreover, our technique protects both statically and dynamically generated code. We use a new compiler-based code generation paradigm that uses hardware features provided by modern CPUs to enable execute-only memory and hide code pointers from leakage to the adversary. Finally, our extensive evaluation shows that our approach is practical -- we protect the entire Google Chromium browser and its V8 JIT compiler -- and efficient with an average SPEC CPU2006 performance overhead of only 6.4%.

Dynamic binary optimizers store altered copies of original program instructions in software-managed code caches in order to maximize reuse of transformed code. Code caches store code blocks that may vary in size, reference other code blocks, and carry a high replacement overhead. These unique constraints reduce the effectiveness of conventional cache management policies. Our work directly addresses these unique constraints and presents several contributions to the code-cache management problem. First, we show that evicting more than the minimum number of code blocks from the code cache results in less run-time overhead than the existing alternatives. Such granular evictions reduce overall execution time, as the fixed costs of invoking the eviction mechanism are amortized across multiple cache insertions. Second, a study of the ideal lifetimes of dynamically generated code blocks illustrates the benefit of a replacement algorithm based on a generational heuristic. We describe and evaluate a generational approach to code cache management that makes it easy to identify long-lived code blocks and simultaneously avoid any fragmentation because of the eviction of short-lived blocks. Finally, we present results from an implementation of our generational approach in the DynamoRIO framework and illustrate that, as dynamic optimization systems become more prevalent, effective code cache-management policies will be essential for reliable, scalable performance of modern applications.

Just-in-time (JIT) compilers are widely used to implement stack-based virtual machines, such as the Java and .NET virtual machines. One disadvantage of most JIT compilers is that they are unportable; much of the back-end is specific to the target machine. An alternative to machine-specific code generation methods is to define a routine in a high-level language for each virtual machine instruction. These can be compiled to native code using a normal C compiler. The native code for these routines can then be strung together, allowing very simple, unoptimized code to be produced just in time. In this paper we present such a system based on an existing implementation of the Forth language. We present a novel system of optimizations for the system based on exploiting common sequences of virtual machine instructions. We use a small domain specific language and tool to generate stack-optimized code for sequences of virtual machine instructions, and for choosing the most useful sequences for a code-copying compiler. By measuring the length of the resulting executable code, we allow machine-specific sequences to be chosen without any machine-dependent code in our system. Experimental results show that best (average) speedups of 47.2% (15.75%) are possible on a Pentium 4 machine, and even higher an a PowerPC based machine. Furthermore, our optimizations allow the size of the generated code to be reduced by an average of 17.9% on the Pentium 4, and 20.5% on the PowerPC over a wide range of programs. Copyright © 2006 John Wiley & Sons, Ltd.

High-performance just-in-time compilers for Java need to invest considerable effort before actual code generation can commence. This is in part due to the very nature of the Java Virtual Machine, which is not well matched to the requirements of optimizing code generators. Alternative transportation formats based on Static Single Assignment form should theoretically be superior to virtual machines, but this claim has not previously been validated in practice. This paper revisits the topic and attempts to quantify the effect of using an SSA-based mobile code representation (IR) instead of a virtual-machine based one.To this end, we have integrated full support for a verifiable SSA-based IR into Jikes RVM, an existing Java execution environment. The resulting system is capable of loading and executing Java programs represented in either format, traditional JVM bytecode as well as the SSA-based representation, and it can even execute programs made up of a mixture of the two formats. In our implementation, the two alternative just-in-time compilation pipelines share a common low-level code generator.Performance results are encouraging and show simultaneous improvements in both compilation time and code quality relative to Jikes RVM's standard optimizing compiler for JVM class files. They support the hypothesis that SSA-based intermediate representations offer advantages in the context of just-in-time compilation.

Java Virtual Machines (JVMs) for resource-constrained devices, e.g., hand-helds and cell phones, commonly employ interpretation for program translation. However, compilers are able to produce significantly better code quality, and, hence, use device resources more efficiently than interpreters, since compilers can consider large sections of code concurrently and exploit optimization opportunities. Moreover, compilation-based systems store code for reuse by future invocations obviating the redundant computation required for reinterpretation of repeatedly executed code.However, code storage required for compilation can increase the memory footprint of the virtual machine (VM) significantly. As a result, for devices with limited memory resources, this additional code storage may preclude some programs from executing, significantly increase memory management overhead, and substantially reduce the amount of memory available for use by the application.To address the limitations of native code storage, we present the design, implementation, and empirical evaluation of a compiled-code management system that can be integrated into any compilation-based JVM. The system unloads compiled code to reduce the memory footprint of the VM. It does so by dynamically identifying and unloading dead or infrequently used code; if the code is later reused, it is recompiled by the system. As such, our system adaptively trades off memory footprint and its associated memory management costs, with recompilation overhead. Our empirical evaluation shows that our code management system significantly reduces the memory requirements of a compile-only JVM, while maintaining the performance benefits enabled by compilation.We investigate a number of implementation alternatives that use dynamic program behavior and system resource availability to determine when to unload as well as what code to unload. From our empirical evaluation of these alternatives, we identify a set of strategies that enable significant reductions in the memory overhead required for application code. Our system reduces code size by 36--62%, on average, which translates into significant execution-time benefits for the benchmarks and JVM configurations that we studied.

SUMMARY Java is normally compiled to bytecode, which is verified and then executed by the Java Virtual Machine. Bytecode produced via compilation must pass verification. The main cause of complexity for bytecode verification is subroutines, used by compilers to generate more compact code. The techniques to verify subroutines proposed in the literature reject certain programs produced by mundane compilers, are difficult to realize within an implementation of the Java Virtual Machine or are relatively complicated. This paper presents a novel technique which is very simple to understand, implement and prove sound. It is also very powerful: the set of accepted programs has a simple characterization which most likely includes all the code produced by current compilers and which enables future compilers to make more extensive use of subroutines. Copyright c � 2004 John Wiley & Sons, Ltd.

This paper presents some code generation issues in the context of the PQCC Production-Quality Compiler-Compiler project [8]. The approach taken is unusual in several ways. The machine-dependent information for selection of code sequences, register assignments, etc., has been separated throughout, in tabular form, from the machine-independent algorithms. This not only greatly simplifies the development of code generators for new machines or languages, but paves the way for automatic generation of these tables from formal machine descriptions such as ISP [1]. A parse-tree-like internal program representation is used, facilitating the use of context and data dependency information about expressions. The code generation process has been broken into several phases. This leads to simplification and better understanding of the code generation process, and also allows important improvements in the quality of generated code. The algorithms for preliminary determination of addressing modes, allocation of registers and other locations, and the code selection case analysis are discussed. The algorithms described in the paper are being implemented and used in the PQCC compiler.

Generating high quality code for embedded processors is made difficult by irregular architectures and highly encoded parallel instructions. Rather than dealing with the target machine at every stage of the compilation, a promising new methodology employs generic algorithms to optimize code for an idealized abstraction of the true target machine. This code, called reference code, is then mapped to the real instruction set by enhanced genetic algorithms. One perturbs the original schedule to find a number of alternative (parallel) instruction sequences, and the other evolves feasible register assignments, if possible, for each sequence. This paper describes the strategy for mapping idealized code into actual code. The COGEN(T) system employs this methodology to produce good code for different commercial DSPs and ASIPs.

A binary translator examines binary code for a source machine and generates code for a target machine. Understanding what to do with delayed branches in binary code can involve tricky case analyses, for example, if there is a branch instruction in a delay slot. This article presents a disciplined method for deriving such case analyses. The method identifies problematic cases, shows the translations for the nonproblematic cases, and gives confidence that all cases are considered. The method supports such common architectures as SPARC, MIPS, and PA-RISC, and it should apply to any tool that analyzes machine instructions. We begin by writing a very simple interpreter for the source machine's code. We then transform the interpreter into an interpreter for a target machine without delayed branches. To maintain the semantics of the program being interpreted, we simultaneously transform the sequence of source-machine instructions into a sequence of target-machine instructions. The transformation of the instructions becomes our algorithm for binary translation.

An applet is program code which is downloaded dynamically from a server on the World Wide Web and which can be executed while maintaining security on the client side. The majority of applet systems at present, as represented by the Java Applet, implement the applets using virtual machine code which is independent of computer architecture. This is advantageous in terms of installation and use in different machine environments. Because virtual machine code is associated with execution by an interpreter or conversion to native code, the design of the virtual machine code greatly impacts performance during execution. Normally, however, representation of virtual machine code is fixed for each applet system and cannot be altered. The authors focused on the independence of virtual machine code and implementing an applet execution environment which is independent of the design of virtual machine code by making the Just-In-Time (JIT) compiler which converts virtual machine code to native code mobile. In this approach, native code conversion modules which are appropriate for the virtual machine code being used in the applet description are downloaded dynamically. In addition, this applet execution environment provides monitoring functions during applet execution so that a native code applet generated from any virtual machine code can be executed safely. The applet execution monitoring mechanism allows for the programming of system control policies for users, and allows for flexible applet execution control for various levels of monitoring. In this paper, the authors describe an implementation using their newly designed virtual machine code representation in both the SPARC and Intel x86 architecture environments, as well as experiments using this implementation. © 2003 Wiley Periodicals, Inc. Syst Comp Jpn, 34(2): 32–42, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10013

Based on NC Code, in this paper, a kind of virtual descriptive language—V Code is designed and achieved for VA simulation. It is divided into three parts: scene setting code, motion controlling code and environment rendering code. At the same time, V Code definition, function classification, V Code interpreter and V Code generator are given; the grammar structure of each V Code is designed. At last, the application example of solar PECVD equipment is listed to verify V Code's effectiveness. The results show that VA simulation based on V Code is easy to understand and promote the application in many enterprises. And, it is very easy to edit equipment simulation motion program, flexible to control the simulation process, and effective to enhance the structural simulation program and improve the efficiency of the implementation process. Keywords-V Code; Virtual simulation; VA; V Code In recent years, many researches on both the theories and the application of VA are conducted in many countries. Germany, United States and other developed countries lie in the leading position. Reference (1-6) mainly studied the assembly sequence planning and gave feasible algorithm. Paper (7) analyzes the human factors of the assembly process. Domestic scholars also carried out fruitful research for VA and related fields, and made many valuable new theories and new methods (8-10). All of the literature mentioned above, which is based on secondary development for business software, mainly study the assembly sequence planning, human-computer interaction, virtual scene design and other technologies to develop VA system. Most of these studies are still in the initial stages, it is difficult for assembly workers to understand, and hard to widely use in the manufacture enterprises and really have a real benefit. So, VA simulation based on V Code can easily set up virtual simulation environment and body structure of simulation equipment; easily edit equipment simulation motion program, very flexibly control the simulation process, effectively enhance the structural simulation program, simplify program, and improve the efficiency of the implementation process. The presentation of V Code lays a good foundation for the VA simulation in the promotion of all types of enterprises in the future.

—Many mechanisms have been proposed and de-ployed to prevent exploits against software vulnerabilities. Amongthem, W X is one of the most effective and efficient. W Xprevents memory pages from being simultaneously writableand executable, rendering the decades old shellcode injectiontechnique infeasible.In this paper, we demonstrate that the traditional shellcodeinjection attack can be revived through a code cache injectiontechnique. Specifically, dynamic code generation, a techniquewidely used in just-in-time (JIT) compilation and dynamic binarytranslation (DBT), generates and modifies code on the fly in orderto promote performance or security. The dynamically generatedcode fragments are stored in a code cache, which is writableand executable either at the same time or alternately, resultingin an opportunity for exploitation. This threat is especiallyrealistic when the generated code is multi-threaded, becauseswitching between writable and executable leaves a time windowfor exploitation. To illustrate this threat, we have crafted a proof-of-concept exploit against modern browsers that support WebWorkers.To mitigate this code cache injection threat, we propose anew dynamic code generation architecture. This new architecturerelocates the dynamic code generator to a separate process,in which the code cache is writable. In the original processwhere the generated code executes, the code cache remains read-only. The code cache is synchronized across the writing processand the execution process through shared memory. Interactionbetween the code generator and the generated code is handledtransparently through remote procedure calls (RPC). We haveported the Google V8 JavaScript engine and the Strata DBTto this new architecture. Our implementation experience showedthat the engineering effort for porting to this new architectureis minimal. Evaluation of our prototype implementation showedthat this new architecture can defeat the code cache injectionattack with small performance overhead.

We present b2llvm, a multi-platform code generator for the B-method. The b2llvm code generator currently handles the following elements of the B language: simple data types, imperative instructions and component compositions. In particular, this paper describes a translation for essential implementation constructs of the B language into LLVM source code, implemented into the b2llvm compiler. We use an example-based approach for this description.

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, caching 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. The resulting 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.

This paper presents TruffleC, a C interpreter that allows the dynamic execution of C code on top of a Java Virtual Machine (JVM). Rather than producing a static build of a C application, TruffleC is a self-optimizing abstract syntax tree (AST) interpreter combined with a just-in-time (JIT) compiler. Our self-optimizing interpreter specializes the AST based on run-time feedback. AST specialization relies on optimistic assumptions and allows us to build inline caches for polymorphic function pointer calls, to profile runtime values and to potentially replace them with constants, or to speculatively remove code that was not executed yet.After AST specialization, the JIT compiler translates the AST to highly optimized machine code. The machine code uses dynamic deoptimization points at which the control switches back to the interpreter in case of a violated assumption.We evaluated TruffleC using a C micro-benchmark in terms of peak performance. This evaluation showed that TruffleC outperforms the code produced by industry standard compilers such as GCC or Clang/LLVM. The evaluation of other benchmarks ("Computer Language Benchmarks Game") showed that the TruffleC performance is on average only 7% slower than the best performance out of the GCC and Clang/LLVM performances.

Managed runtime environments (MREs) like web browsers or the Java Virtual Machine (JVM) include multiple dynamic compilers (or compiler configurations) to provide a good tradeoff between compilation speed and generated code quality: Longer compilation times typically imply better code quality and hence better peak performance than shorter compilation times, which provide good warmup/startup performance and lower peak performance. A system that uses multiple compilers is referred to as a multi-tiered compilation system.Multi-tiered compilation systems pose a significant challenge to the code cache, since methods can be compiled multiple times at different compilation levels. The characteristics of muti-tiered compiled code (e.g., lifetime, size, etc.) can lead to an inefficient code cache usage. This paper discusses the challenges in the context of the Java Virtual Machine (JVM) and proposes a new code cache design that aims at solving these challenges.A detailed performance evaluation shows that our new code cache design improves overall performance by up to 7%. The performance gain results from a combination of faster code cache sweeping as well as better instruction TLB and instruction cache behavior.

International audience; Attacks on smart cards can only be based on a black box approach where the code of cryptographic primitives and operating system are not accessible. To perform hardware or software attacks, a white box approach providing access to the binary code is more effi- cient. In this paper, we propose a methodology to discover the romized code whose access is protected by the virtual machine. It uses a hooked code in an indirection table. We gained access to real processor, thus allowing us to run a shell code written in 8051 assembler language. As a result, this code has been able to dump completely the ROM of a Java Card operating system. One of the issues is the possibility to reverse the cryptographic algorithm and all the embedded countermeasures. Finally, our attack is evaluated on different cards from distinct manufacturers.

One of the fundamental problems with the static analysis of binary (executable) code is that of recognizing, in a machine-independent way, the target addresses of n -conditional branches implemented via a jump table. Without these addresses, the decoding of the machine instructions for a given procedure is incomplete, leading to imprecise analysis of the code. In this paper we present a technique for recovering jump tables and their target addresses in a machine and compiler independent way. The technique is based on slicing and copy propagation. The assembly code of a procedure that contains an indexed jump is transformed into a normal form which allows us to determine where the jump table is located and what information it contains (e.g. offsets from the table or absolute addresses). The presented technique has been implemented and tested on SPARC and Pentium code generated by C , C ++ , Fortran and Pascal compilers. Our tests show that up to 89% more of the code in a text segment can be found by using this technique, when compared against the standard method of decoding. The technique was developed as part of our retargetable binary translation framework UQBT; however, it is also suitable for other binary-manipulation and analysis tools such as binary profilers, instrumentors and decompilers.

Code selection is an important task in code generation for programmable processors, where the goal is to find an efficient mapping of machine-independent intermediate code to processor-specific machine instructions. Traditional approaches to code selection are based on tree parsing which enables fast and optimal code selection for intermediate code given as a set of data-flow trees. While this approach is generally useful in compilers for general-purpose processors, it may lead to poor code quality in the case of embedded processors. The reason is that the special architectural features of embedded processors require performing code selection on data-flow graphs, which are a more general representation of intermediate code. In this paper, we present data-flow graph-based code selection techniques for two architectural families of embedded processors: media processors with support for SIMD instructions and fixed-point DSPs with irregular data paths. Both techniques exploit the fact that, in the area of embedded systems, high code quality is a much more important goal than high compilation speed. We demonstrate that certain architectural features can only be utilized by graph-based code selection, while in other cases this approach leads to a significant increase in code quality as compared to tree-based code selection.

In recent years there has been an increasing trend toward the incorpor ation of computers into a variety of devices where the amount of memory available is limited. This makes it desirable to try to reduce the size of applications where possible. This article explores the use of compiler techniques to accomplish code compaction to yield smaller executables. The main contribution of this article is to show that careful, aggressive, interprocedural optimization, together with procedural abstraction of repeated code fragments, can yield significantly better reductions in code size than previous approaches, which have generally focused on abstraction of repeated instruction sequences. We also show how “equivalent” code fragments can be detected and factored out using conventional compiler techniques, and without having to resort to purely linear treatments of code sequences as in suffix-tree-based approaches, thereby setting up a framework for code compaction that can be more flexible in its treatment of what code fragments are considered equivalent. Our ideas have been implemented in the form of a binary-rewriting tool that reduces the size of executables by about 30% on the average.

The Java .class file is a compact encoding of programs for a stack-based virtual machine. It is intended for use in a networked environment, which requires machine independence and minimized consumption of network bandwidth. However, as in all interpreted virtual machines, performance does not match that of code generated for the target machine. We propose verifiable, machine-independent annotations to the Java class file to bring the quality of the code generated by a ‘just-in-time’ compiler closer to that of an optimizing compiler without a significant increase in code generation time. This division of labor has expensive machine-independent analysis performed off-line and inexpensive machine-dependent code-generation performed on the client. We call this phenomenon ‘super-linear analysis and linear exploitation.’ These annotations were designed mindful of the concurrency features of the Java language. In this paper we report results from our machine-independent, prioritized register assignment. We also discuss other possible annotations. Copyright © 2000 John Wiley & Sons, Ltd.

There is an enormous amount of parallelism exposed to fine-grain multithreaded architectures to cover latencies. It is a demanding task for a multithreading programmer to manage such a degree of parallelism by hand. To use multithreaded architectures efficiently it is essential to have compiler support for automatically partitioning programs into threads. This paper solves a fundamental problem in compiling for multithreaded architectures, automatically partitioning a program into threads. The focus of such partitioning is to overlap the remote communication latency and minimize the total execution time. We first formulate the partitioning problem based on a multithreaded execution cost model. Then, we prove such a formulation is NP-hard. Therefore, we propose two heuristic thread-partitioning methods to solve this problem in practice. The advanced partitioning algorithm is a novel extension of list scheduling, and it takes advantage of the cost model to generate near-optimum partitioning results. The remote-path-based partitioning algorithm is a simplified version of the advanced one but it is easy for compiler implementation. The two partitioning algorithms were implemented respectively in a thread partitioning testbed and a research EARTH-C compiler. The experimental results show that both partitioning algorithms are effective to generate efficient threaded code, and code generated by the compiler is comparable to hand-written code.

Atlas was a wonderful machine, with over 1000 instructions, 128 registers in an architecture that allowed double modification, and an address space of 24 bits-at a time when stores were measured in kilobytes. Unfortunately, compiler writers were unable to use these facilities to the full-or anywhere near it. Almost all of the bits of compiled code were zeroes. For MU5, for the first-and probably the only-time, programmers were given the task of designing the order code so that they could fully utilize it. The author explains why compiler writers were unable to use Atlas at all well and how we designed the MU5 order code to enable us to compile code more effectively.

Many parallel architectures support a memory model where some memory accesses are local and, thus, inexpensive, while other memory accesses are remote and potentially quite expensive. In the case of memory references via pointers, it is often difficult to determine if the memory reference is guaranteed to be local and, thus, can be handled via an inexpensive memory operation. Determining which memory accesses are local can be done by the programmer, the compiler, or a combination of both. The overall goal is to minimize the work required by the programmer and have the compiler automate the process as much as possible. This paper reports on compiler techniques for determining when indirect memory references are local. The locality analysis has been implemented for a parallel dialect of C called EARTH-C, and it uses an algorithm inspired by type inference algorithms for fast points-to analysis. The algorithm statically estimates when an indirect reference via a pointer can be safely assumed to be a local access. The locality inference algorithm is also used to guide the automatic specialization of functions in order to take advantage of locality specific to particular calling contexts. In addition to these purely static techniques, we also suggest fine-grain and coarse-grain dynamic techniques. In this case, dynamic locality checks are inserted into the program and specialized code for the local case is inserted. In the fine-grain case, the checks are put around single memory references, while in the coarse-grain case the checks are put around larger program segments. The static locality analysis and automatic specialization has been implemented in the EARTH-C compiler, which produces low-level threaded code for the EARTH multithreaded architecture. Experimental results are presented for a set of benchmarks that operate on irregular, dynamically allocated data structures. Overall, the techniques give moderate to significant speedups, with the combination of static and dynamic techniques giving the best performance overall.