Rewriting executable files to measure program behavior

Inserting instrumentation code in a program is an effective technique for detecting, recording, and measuring many aspects of a program's performance. Instrumentation code can be added at any stage of the compilation process by specially-modified system tools such as a compiler or linker or by new tools from a measurement system. For several reasons, adding instrumentation code after the compilation process—by rewriting the executable file—presents fewer complications and leads to more complete measurements. This paper describes the difficulties in adding code to executable files that arose in developing the profiling and tracing tools qp and qpt. The techniques used by these tools to instrument programs on MIPS and SPARC processors are applicable in other instrumentation systems running on many processors and operating systems. In addition, many difficulties could have been avoided with minor changes to compilers and executable file formats. These changes would simplify this approach to measuring program performance and make it more generally useful.     

一种面向可重构硬件的编译中间表示方法

中间表示氓是构建编译和高级综合工具的基础。本文设计了一种面向可重构硬件的编译中间表示方法。这一工作是我们设计的高级综合工具的一部分。实验结果表明,应用这 一中间表示,可以将C源程序高效地映射到目标可重构硬件上。     

On Efficiency and Optimization of C++ Programs

The efficiency of object-oriented programs has become a point of great interest. One necessary factor for program efficiency is the optimization techniques involved. This paper presents the performance of several variations of a given C++ program and compares them with a version that uses no object-oriented features. Our result indicates that some object-oriented features in C++ are not well optimized in current C++ compilers. We thus discuss some code optimization techniques that can improve the efficiency based on the given C++ program.     

Quick compilers using peephole optimization

Abstract machine modelling is a popular technique for developing portable compilers. A compiler can be quickly realized by translating the abstract machine operations to target machine operations. The problem with these compilers is that they trade execution efficiency for portability. Typically, the code emitted by these compilers runs two to three times slower than the code generated by compilers that employ sophisticated code generators. This paper describes a C compiler that uses abstract machine modelling to achieve portability. The emitted target machine code is improved by a simple, classical rule-directed peephole optimizer. Our experiments with this compiler on four machines show that a small number of very general handwritten patterns (under 40) yields code that is comparable to the code from compilers that use more sophisticated code generators. As an added bonus, compilation time on some machines is reduced by 10 to 20 per cent.     

Issues in Ada compiler technology

The key technical issues involved in producing high-quality Ada compilers and related support tools are discussed. These include real-time issues, programming tools and environments, and code optimization. Also addressed are some important problems that compiler designers face, for example, determining which deficiencies of existing Ada systems can be attributed to the language and which are simply hard-to-implement features or unresolved issued in Ada compiler technology     

A study of irreducibility in C programs

Compilers use a variety of techniques to optimize and transform loops. However, many of these optimizations do not work when the loop is irreducible. Node splitting techniques transform irreducible loops into reducible loops, but many real‐world compilers choose to leave them unoptimized. This article describes an empirical study of irreducibility in current versions of open‐source software, and then compares them with older versions. We also study machine‐generated C code from a number of software tools. We find that irreducibility is extremely rare, and is becoming less common with time. We conclude that leaving irreducible loops unoptimized is a perfectly feasible future‐proof option due to the rarity of its occurrence in non‐trivial software. Copyright © 2011 John Wiley & Sons, Ltd.     

Incremental scanning and parsing with galaxy

The algorithms and techniques used in incremental scanning and parsing of the Galaxy language are presented. Incremental compilers, programming environments that feature instantaneous change processing as well as the execution time efficiency of compiled programs and code development using the Galaxy language are discussed. It is shown that the algorithms guarantee minimal rescanning and reparsing are space and time efficient and are easily adapted to any language of equivalent class, including such languages as C and Pascal     

基于XML Schema技术的编译符号表生成方法

传统的编译中间代码通常不能在移动、嵌入式和分布式等环境之间转换，而符号表的构造与管理贯穿整个中间代码的生成过程。本文提出一种基于XML Schema及其相关技术生成编译中间代码的符号表的方法。首先给出整体方案，然后阐述了如何运用XML Schema等技术表示编译器的前端，以及后端的目标机体系结构。生成的编译器符号表能通过XML工具统一管理和验证，从而使生成的编译中间代码有较高的可移植性，能被不同环境中的编译器采用。     

An assessment of the XR project for compiler development and transportation

A software engineering project, the XR project, is described, and its results assessed. The goal of the XR project is to contribute to the mechanical development and transportation of compilers on widely used Chinese-made computers. The basic tools are the compiler writing language XHY and the intermediate language CJY. All the compilers are written in XHY and produce code in CJY form. In this paper, experiences, statistics and lessons of practising this project are given, together with an overview and a conclusion.     

Tice: A real-time language compilable using C++ compilers

Model-based development (MBD) holds the promise to capture potential timing problems in embedded software during the early phases of the development, securing the production of bug-free embedded software. For most MBD approaches, the source code is just an intermediate artifact that can be generated automatically from the models. This assumption clashes with an undeniable fact: a large share of the commercial embedded software exploits existing libraries or is developed using C/C++ natively. A way to reconcile the ambitions of MBD with the use of a programming language is by offering new language constructs and an innovative compilation tool-chain that prevents model error and timing problems “by construction.” However, the persistent popularity of C/C++ among embedded programmers and the limited availability of tools have severely limited the uptake of alternative programming languages for embedded software. Therefore, we propose an original route. Our language proposal, named Tice, has been shaped as a C++ active library. Tice retains full compatibility with existing C++ code, which can be integrated easily into new Tice-based projects. The enforcement of Tice syntax and semantics can be made by a standard C++ compiler, forgoing the need for new tools. In this article, we describe Tice's syntax, semantics, and model of computation and communication. We demonstrate Tice's practical applicability on an industrial scale use-case and give ample evidence for Tice's efficient compilation using off-the-shelf C++ compilers. Finally, we show Tice's code generation process.     

Using profile information to assist classic code optimizations

This paper describes the design and implementation of an optimizing compiler that automatically generates profile information to assist classic code optimizations. This compiler contains two new components, an execution profiler and a profile-based code optimizer, which are not commonly found in traditional optimizing compilers. The execution profiler inserts probes into the input program, executes the input program for several inputs, accumulates profile information and supplies this information to the optimizer. The profile-based code optimizer uses the profile information to expose new optimization opportunities that are not visible to traditional global optimization methods. Experimental results show that the profile-based code optimizer significantly improves the performance of production C programs that have already been optimized by a high-quality global code optimizer.     

Compiler Hacking for Source Code Analysis

Many activities related to software quality assessment and improvement, such as empirical model construction, data flow analysis, testing or reengineering, rely on static source code analysis as the first and fundamental step for gathering the necessary input information. In the past, two different strategies have been adopted to develop tool suites. There are tools encompassing or implementing the source parse step, where the parser is internal to the toolkit, and is developed and maintained with it. A different approach builds tools on the top of external already-available components such as compilers that output the program abstract syntax tree, or that make it available via an API.This paper discusses techniques, issues and challenges linked to compiler patching or wrapping for analysis purposes. In particular, different approaches for accessing the compiler parsing information are compared, and the techniques used to decouple the parsing front end from the analysis modules are discussed.Moreover, the paper presents an approach and a tool, XOgastan, developed exploiting the gcc/g++ ability to save a representation of the intermediate abstract syntax tree. XOgastan translates the gcc/g++ dumped abstract syntax tree format into a Graph eXchange Language representation, which makes it possible to take advantage of currently available XML tools for any subsequent analysis step. The tool is illustrated and its design discussed, showing its architecture and the main implementation choices made.     

DSP分块内存和多AGU的编译指示优化

分块内存和多地址生成器(AGU)是DSP普遍采用的体系结构.传统的C语言编译器没有针对分块内存和多AGU结构进行代码优化,导致生成代码无法满足性能需求,影响了C语言编译器在数字信号处理领域的应用.为了解决这个问题,提出基于编译指示,与分块内存和多AGU结构相关的编译优化算法.该算法利用定义引用链和引用定义链中的数据流信息,为地址计算指令和访存指令分配AGU,从而提高生成代码的指令级并行度.实验结果表明此算法能够达到较好的优化效果.     

Optimizing Procedure Calls for Delayed Non-local Execution Protocol

This work originated from the challenge to strengthen a C-like language compiler developed to support the compilation of sleepers, which are tools which allow complete access to the run-time stack in a delayed non-local execution protocol. Sleepers use a specialized form of procedure call, for which the gain in time execution and space memory allocation becomes a crucial need. These two objectives have been attained thanks to a methodology which generalizes the traditional distinction between tail-calls and normal-calls, introducing the orthogonal distinction between calls in which the calling environment is needed after the call site and calls in which it is not. These two dichotomies divide the space of calls into four classes. The strategy described in this paper is a simple and general framework which can be used to optimize the call-procedure statement in C compilers. The paper discusses optimization techniques appropriate to each class in turn, providing code details for SPARC and ALPHA processors.     

Towards a toolkit for building language implementations

The current work of the authors in the area of software tools for automatic construction of compilers is described. This focuses on attempts to provide for automatic production of the semantic-analysis and intermediate-code-generation parts of the Cigale compiler-writing system, developed at the University of Nice. This work relies on use of the Amsterdam Compiler Kit (ACK) to ensure a full set of optimizers and code generators based on a semi-universal intermediate language, and, therefore, emphasizes the filling of the gap between parsing and the intermediate language. It is intended as a pragmatic contribution to the automation of the production of true compilers (rather than mere program evaluators) that generate efficient machine code.     

Compilation techniques for parallel systems

Over the past two decades tremendous progress has been made in both the design of parallel architectures and the compilers needed for exploiting parallelism on such architectures. In this paper we summarize the advances in compilation techniques for uncovering and effectively exploiting parallelism at various levels of granularity. We begin by describing the program analysis techniques through which parallelism is detected and expressed in form of a program representation. Next compilation techniques for scheduling instruction level parallelism (ILP) are discussed along with the relationship between the nature of compiler support and type of processor architecture. Compilation techniques for exploiting loop and task level parallelism on shared-memory multiprocessors (SMPs) are summarized. Locality optimizations that must be used in conjunction with parallelization techniques for achieving high performance on machines with complex memory hierarchies are also discussed. Finally we provide an overview of compilation techniques for distributed memory machines that must perform partitioning of both code and data for parallel execution. Communication optimization and code generation issues that are unique to such compilers are also briefly discussed.     

A multilevel computing architecture for embedded multimedia applications

We have designed a new architecture that simplifies integration of heterogeneous IP for multimedia and streaming applications. The multilevel computing architecture (MLCA) is a template architecture featuring multiple processing units. This template architecture for SOC systems uses superscalar techniques to exploit task-level parallelism among different processing units. It supports a natural programming model that relieves programmers from explicitly synchronizing tasks and communicating data. code transformations that improve application performance are easy to incorporate in compilers for this architecture.     

Ada System Dependency Analyzer tool

A major thrust of modern software engineering methods, languages, and tools is to promote software visibility and to present information about the underlying software architecture. With large, complex software systems, automated tools are indispensable for identifying the architectural components, the structure that interconnects them, and other subtle dependencies. This article describes the construction of an Ada System Dependency Analyzer (SDA), a software architecture analysis tool that generates a quantitative snapshot of an Ada application's software architecture. The SDA can process thousands of Ada source files during a single run and report on them as a group of files comprising a single Ada system. Our SDA tool identifies Ada source code dependencies on COTS products such as operating systems, compilers, the X Window System, and on routines written in other languages, and can thus predict software portability and reliability problems. It rapidly and accurately processes 24,000 lines of code per minute (a time-consuming, if not impossible, operation if done manually) and has successfully processed more than seven million lines of code in eight complex systems. Although originally developed for Ada, our methods and the technology we adopted will let us construct analogous tools for other programming languages such as C, C++, Cobol; and PL/I     

SuperC or distributed heterogeneous HPC

This paper describes an approach to identifying and employing an optimal, heterogeneous suite of processors to solve traditional supercomputing problems. This technique, called superconcurrency or SuperC, currently works best, using existing compilers and distributed operating systems, when the computational requirements are diverse and significant portions of the code are loosely coupled. Future implementations will benefit from new methods of benchmarking and cold profiling, and eventually from the use of AI techniques for intelligent management of the selected superconcurrent suite. These techniques, combined with anticipated bandwidth increases, will permit much more closely coupled code portions to be distributed on the heterogeneous suite. Implications for future architectures and distributed heterogeneous processing in general are also discussed.     

The design and implementation of a code generation tool

A practical approach to the development of a high-quality, re-usable code generator is described in this paper. This code generator produces code for the Prime 64V mode architecture, but the methodology used is generally applicable to the construction of compilers for most architectures. The code generator accepts a tree-structured intermediate form, linearized and represented as a file of integers. This intermediate form uses high-level operators, minimizing work by compiler front-ends that use it and providing a number of advantages in the code generation process. The output of the code generator is assembly language. This tool was found to considerably extend the capabilities of students in a graduate compiler class and has been used in the construction of Pascal and C compilers.