Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2013 | Book

Optimal Register Allocation in Polynomial Time Read chapter Read first chapter

Compiler Construction

22nd International Conference, CC 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings

Editors: Ranjit Jhala, Koen De Bosschere

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This book constitutes the proceedings of the 22nd International Conference on Compiler Construction, CC 2013, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, which took place in Rome, Italy, in March 2013. The 13 papers presented in this book were carefully reviewed and selected from 53 submissions. They have been organized into five topical sections on register allocation, pointer analysis, data and information flow, machine learning, and refactoring.

Table of Contents

Frontmatter

Session I: Register Allocation

Optimal Register Allocation in Polynomial Time
Abstract
A graph-coloring register allocator that optimally allocates registers for structured programs in polynomial time is presented. It can handle register aliasing. The assignment of registers is optimal with respect to spill and rematerialization costs, register preferences and coalescing. The register allocator is not restricted to programs in SSA form or chordal interference graphs. It assumes the number of registers is to be fixed and requires the input program to be structured, which is automatically true for many programming languages and for others, such as C, is equivalent to a bound on the number of goto labels per function. Non-structured programs can be handled at the cost of either a loss of optimality or an increase in runtime. This is the first optimal approach that has polynomial runtime and works for such a huge class of programs.
An implementation is already the default register allocator in most backends of a mainstream cross-compiler for embedded systems.
Philipp Klaus Krause
Optimal and Heuristic Global Code Motion for Minimal Spilling
Abstract
The interaction of register allocation and instruction scheduling is a well-studied problem: Certain ways of arranging instructions within basic blocks reduce overlaps of live ranges, leading to the insertion of less costly spill code. However, there is little previous research on the extension of this problem to global code motion, i.e., the motion of instructions between blocks. We present an algorithm that models global code motion as an optimization problem with the goal of minimizing overlaps between live ranges in order to minimize spill code.
Our approach analyzes the program to identify the live range overlaps for all possible placements of instructions in basic blocks and all orderings of instructions within blocks. Using this information, we formulate an optimization problem to determine code motions and partial local schedules that minimize the overall cost of live range overlaps. We evaluate solutions of this optimization problem using integer linear programming, where feasible, and a simple greedy heuristic.
We conclude that global code motion with the sole goal of avoiding spills rarely leads to performance improvements because code is placed too conservatively. On the other hand, purely local optimal instruction scheduling for minimal spilling is effective at improving performance when compared to a heuristic scheduler for minimal register use.
Gergö Barany, Andreas Krall

Session II: Pointer Analysis

Efficient and Effective Handling of Exceptions in Java Points-to Analysis
Abstract
A joint points-to and exception analysis has been shown to yield benefits in both precision and performance. Treating exceptions as regular objects, however, incurs significant and rather unexpected overhead. We show that in a typical joint analysis most of the objects computed to flow in and out of a method are due to exceptional control-flow and not normal call-return control-flow. For instance, a context-insensitive analysis of the Antlr benchmark from the DaCapo suite computes 4-5 times more objects going in or out of a method due to exceptional control-flow than due to normal control-flow. As a consequence, the analysis spends a large amount of its time considering exceptions.
We show that the problem can be addressed both effectively and elegantly by coarsening the representation of exception objects. An interesting find is that, instead of recording each distinct exception object, we can collapse all exceptions of the same type, and use one representative object per type, to yield nearly identical precision (loss of less than 0.1%) but with a boost in performance of at least 50% for most analyses and benchmarks and large space savings (usually 40% or more).
George Kastrinis, Yannis Smaragdakis
An Incremental Points-to Analysis with CFL-Reachability
Abstract
Developing scalable and precise points-to analyses is increasingly important for analysing and optimising object-oriented programs where pointers are used pervasively. An incremental analysis for a program updates the existing analysis information after program changes to avoid reanalysing it from scratch. This can be efficiently deployed in software development environments where code changes are often small and frequent. This paper presents an incremental approach for demand-driven context-sensitive points-to analyses based on Context-Free Language (CFL) reachability. By tracing the CFL-reachable paths traversed in computing points-to sets, we can precisely identify and recompute on demand only the points-to sets affected by the program changes made. Combined with a flexible policy for controlling the granularity of traces, our analysis achieves significant speedups with little space overhead over reanalysis from scratch when evaluated with a null dereferencing client using 14 Java benchmarks.
Yi Lu, Lei Shang, Xinwei Xie, Jingling Xue
FESA: Fold- and Expand-Based Shape Analysis
Abstract
A static shape analysis is presented that can prove the absence of NULL- and dangling pointer dereferences in standard algorithms on lists, trees and graphs. It is conceptually simpler than other analyses that use symbolically represented logic to describe the heap. Instead, it represents the heap as a single graph and a Boolean formula. The key idea is to summarize two nodes by calculating their common points-to information, which is done using the recently proposed fold and expand operations. The force of this approach is that both, fold and expand, retain relational information between points-to edges, thereby essentially inferring new shape invariants. We show that highly precise shape invariants can be inferred using off-the-shelf SAT-solvers. Cheaper approximations may augment standard points-to analysis used in compiler optimisations.
Holger Siegel, Axel Simon

Session III: Data and Information Flow

Simple and Efficient Construction of Static Single Assignment Form
Abstract
We present a simple SSA construction algorithm, which allows direct translation from an abstract syntax tree or bytecode into an SSA-based intermediate representation. The algorithm requires no prior analysis and ensures that even during construction the intermediate representation is in SSA form. This allows the application of SSA-based optimizations during construction. After completion, the intermediate representation is in minimal and pruned SSA form. In spite of its simplicity, the runtime of our algorithm is on par with Cytron et al.’s algorithm.
Matthias Braun, Sebastian Buchwald, Sebastian Hack, Roland Leißa, Christoph Mallon, Andreas Zwinkau
PolyGLoT: A Polyhedral Loop Transformation Framework for a Graphical Dataflow Language
Abstract
Polyhedral techniques for program transformation are now used in several proprietary and open source compilers. However, most of the research on polyhedral compilation has focused on imperative languages such as C, where the computation is specified in terms of statements with zero or more nested loops and other control structures around them. Graphical dataflow languages, where there is no notion of statements or a schedule specifying their relative execution order, have so far not been studied using a powerful transformation or optimization approach. The execution semantics and referential transparency of dataflow languages impose a different set of challenges. In this paper, we attempt to bridge this gap by presenting techniques that can be used to extract polyhedral representation from dataflow programs and to synthesize them from their equivalent polyhedral representation.
We then describe PolyGLoT, a framework for automatic transformation of dataflow programs which we built using our techniques and other popular research tools such as Clan and Pluto. For the purpose of experimental evaluation, we used our tools to compile LabVIEW, one of the most widely used dataflow programming languages. Results show that dataflow programs transformed using our framework are able to outperform those compiled otherwise by up to a factor of seventeen, with a mean speed-up of 2.30× while running on an 8-core Intel system.
Somashekaracharya G. Bhaskaracharya, Uday Bondhugula
Architecture-Independent Dynamic Information Flow Tracking
Abstract
Dynamic information flow tracking is a well-known dynamic software analysis technique with a wide variety of applications that range from making systems more secure, to helping developers and analysts better understand the code that systems are executing. Traditionally, the fine-grained analysis capabilities that are desired for the class of these systems which operate at the binary level require tight coupling to a specific ISA. This places a heavy burden on developers of these systems since significant domain knowledge is required to support each ISA, and the ability to amortize the effort expended on one ISA implementation cannot be leveraged to support other ISAs. Further, the correctness of the system must carefully evaluated for each new ISA.
In this paper, we present a general approach to information flow tracking that allows us to support multiple ISAs without mastering the intricate details of each ISA we support, and without extensive verification. Our approach leverages binary translation to an intermediate representation where we have developed detailed, architecture-neutral information flow models. To support advanced instructions that are typically implemented in C code in binary translators, we also present a combined static/dynamic analysis that allows us to accurately and automatically support these instructions. We demonstrate the utility of our system in three different application settings: enforcing information flow policies, classifying algorithms by information flow properties, and characterizing types of programs which may exhibit excessive information flow in an information flow tracking system.
Ryan Whelan, Tim Leek, David Kaeli

Session IV: Machine Learning

On the Determination of Inlining Vectors for Program Optimization
Abstract
In this paper we propose a new technique and a framework to select inlining heuristic constraints - referred to as an inlining vector, for program optimization. The proposed technique uses machine learning to model the correspondence between inlining vectors and performance (completion time). The automatic selection of a machine learning algorithm to build such a model is part of our technique and we present a rigorous selection procedure. Subject to a given architecture, such a model evaluates the benefit of inlining combined with other global optimizations and selects an inlining vector that, in the limits of the model, minimizes the completion time of a program.
We conducted our experiments using the GNU GCC compiler and optimized 22 combinations (program, input) from SPEC CINT2006 on the state-of-the-art Intel Xeon Westmere architecture. Compared with optimization level, i.e., -O3, our technique yields performance improvements ranging from 2% to 9%.
Rosario Cammarota, Alexandru Nicolau, Alexander V. Veidenbaum, Arun Kejariwal, Debora Donato, Mukund Madhugiri
Automatic Generation of Program Affinity Policies Using Machine Learning
Abstract
Modern scientific and server programs require multisocket, multicore machines to achieve good performance. Maximizing the performance of these programs requires careful consideration of program behavior and careful management of hardware resources. In particular, a program’s affinity can have a critical performance effect. For such machines, there are many possible affinities for a multithreaded program. In this paper, we present AutoFinity, a solution to automatically generate program affinity policies that consider program behavior and the target machine. The policies are constructed with machine learning and used online to select an affinity. We implemented AutoFinity on a 4-processor, 48-core machine and evaluated it on 18 multithreaded programs with varying thread counts. Our results show that in 12 out of 15 cases where affinity impacts runtime, the policy generated by AutoFinity chose affinities that improved performance versus assignments that do not consider program and machine behavior.
Ryan W. Moore, Bruce R. Childers

Session V: Refactoring

Compiler-Guided Identification of Critical Sections in Parallel Code
Abstract
There is a huge body of sequential legacy code that needs to be refactored for multicore processors. Especially for control code for embedded systems it is often easy to split the program into multiple threads. But it is difficult to identify critical sections to avoid data races as the legacy code hides its synchronization in a static schedule, priorities and interrupts.
To ease refactoring, this paper presents a new static data-dependence analysis that identifies necessary critical sections in thread-parallel code that does not yet contain any synchronization between threads. A novel optimization pass then breaks up and shrinks the identified critical sections to maximize parallelism while preserving correctness. Our technique proved to be successful in refactoring sequential assembly-like legacy codes in an industry-sponsored project.
But as refactoring projects are hard to evaluate quantitatively and as the domain specific low-level language is of limited interest, we use a standard benchmark suite for which the optimum, i.e., the minimal set of the necessary atomic block annotations is known. We removed the annotations and let the compiler attempt to rediscover them. For 5 out of 7 benchmarks, our compiler identified the same critical sections as the original programmers did by hand. For the other two benchmarks, the compiler found slightly larger (but also correct) critical sections. In all cases, the versions of the benchmarks that the compiler annotated achieved the original run-time performance.
Stefan Kempf, Ronald Veldema, Michael Philippsen
Refactoring MATLAB
Abstract
Matlab is a very popular dynamic “scripting” language for numerical computations used by scientists, engineers and students world-wide. Matlab programs are often developed incrementally using a mixture of Matlab scripts and functions, and frequently build upon existing code which may use outdated features. This results in programs that could benefit from refactoring, especially if the code will be reused and/or distributed. Despite the need for refactoring, there appear to be no Matlab refactoring tools available. Furthermore, correct refactoring of Matlab is quite challenging because of its non-standard rules for binding identifiers. Even simple refactorings are non-trivial.
This paper presents the important challenges of refactoring Matlab along with automated techniques to handle a collection of refactorings for Matlab functions and scripts including: converting scripts to functions, extracting functions, and converting dynamic function calls to static ones. The refactorings have been implemented using the McLab compiler framework, and an evaluation is given on a large set of Matlab benchmarks which demonstrates the effectiveness of our approach.
Soroush Radpour, Laurie Hendren, Max Schäfer
On LR Parsing with Selective Delays
Abstract
The paper investigates an extension of LR parsing that allows the delay of parsing decisions until a sufficient amount of context has been processed. We provide two characterizations for the resulting class of grammars, one based on grammar transformations, the other on the direct construction of a parser. We also report on experiments with a grammar collection.
Eberhard Bertsch, Mark-Jan Nederhof, Sylvain Schmitz
Backmatter
Metadata
Title
Compiler Construction
Editors
Ranjit Jhala
Koen De Bosschere
Copyright Year
2013
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-37051-9
Print ISBN
978-3-642-37050-2
DOI
https://doi.org/10.1007/978-3-642-37051-9

Premium Partner

    Image Credits