title: Aggressive Loop Unrolling in a Retargetable Optimizing Compiler

authors:
Jack W. Davidson
Sanjay Jinturkar


venue: cc

title: Removing Anti Dependences by Repairing

authors:
M. Anton Ertl
Andreas Krall


title: A Parallel Debugger with Support for Distributed Arrays, Multiple Executables and Dynamic Processes

authors:
Peter Fritzson
Roland Wismüller
Olav Hansen
Jonas Sala
Peter Skov


title: Non-monotone Fixpoint Iterations to Resolve Second Order Effects

authors:
Alfons Geser
Jens Knoop
Gerald Lüttgen
Oliver Rüthing
Bernhard Steffen


title: Controlled Node Splitting

authors:
Johan Janssen
Henk Corporaal


title: Maptool - Supporting Modular Syntax Development

authors:
Basim M. Kadhim
William M. Waite


title: Efficient Storage Reuse of Aggregates in Single Assignment Languages

authors:
Zhonghua Li
Chris C. Kirkham


title: A Faster Earley Parser

authors:
Philippe McLean
R. Nigel Horspool


title: Code Generation = A* + BURS

authors:
Albert Nymeyer
Joost-Pieter Katoen
Ymte Westra
Henk Alblas


title: A Compiler for Natural Semantics


title: A Comparison of Modulo Scheduling Techniques for Software Pipelining

authors:
Peter Pfahler
Georg Piepenbrock


title: One-Pass, Optimal Tree Parsing - With Or Without Trees

authors:
Todd A. Proebsting
Benjamin R. Whaley


title: Using Partial Evaluation in Support of Portability, Reusability, and Maintainability


title: Points-to Analysis by Type Inference of Programs with Structures and Unions


title: Generalized Constant Propagation: A Study in C

authors:
Clark Verbrugge
Phong Co
Laurie J. Hendren


title: Compact Dispatch Tables for Dynamically Typed Object Oriented Languages

authors:
Jan Vitek
R. Nigel Horspool


title: Compiler Construction: Craftmanship or Engineering?


title: Pipelining-Dovetailing: A Transformation to Enhance Software Pipelining for Nested Loops

authors:
Jian Wang
Guang R. Gao


title: Analyzing Direct Non-local Dependencies in Attribute Grammars


title: Cool: A Control-Flow Generator for System Analysis

authors:
Volker Braun
Jens Knoop
Dirk Koschützki


title: Myths and Facts about the Efficient Implementation of Finite Automata and Lexical Analysis

authors:
Klaus Brouwer
Wolfgang Gellerich
Erhard Plödereder


title: Challenges and Oppurtunities Visual Programming Languages Bring to Programming Language Research


title: Live Range Splitting in a Graph Coloring Register Allocator

authors:
Keith D. Cooper
L. Taylor Simpson


title: Issues in Translating Smalltalk into Java

authors:
R. L. Engelbrecht
Derrick G. Kourie


title: Detecting Parallelism in C Programs with Recursive Darta Structures

authors:
Rakesh Ghiya
Laurie J. Hendren
Yingchun Zhu


title: A Code Motion Framework for Global Instruction Scheduling


title: Generalised Recursive Descent parsing and Fellow-Determinism

authors:
Adrian Johnstone
Elizabeth Scott

abstract: This paper presents a construct for mapping arbitrary non-left recursive context-free grammars into recursive descent parsers that: handle ambiguous grammars correctly; perform with LL(1) efficiency on LL(1) grammars; allow straightforward implementation of both inherited and synthesized attributes; and allow semantic actions to be added at any point in the grammar. We describe both the basic algorithm and a tool, GRDP, which generates parsers which use this technique. Modifications of the basic algorithm to improve efficiency lead to a discussion of follow-determinism , a fundamental property that gives insights into the behaviour of both LL and LR parsers. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


title: The Eli System

authors:
Uwe Kastens
Peter Pfahler
Matthias T. Jung


title: Strength Reduction via SSAPRE

authors:
Robert Kennedy
Fred C. Chow
Peter Dahl
Shin-Ming Liu
Raymond Lo
Mark Streich


title: Basic-Block Graphs: Living Dinosaurs?

authors:
Jens Knoop
Dirk Koschützki
Bernhard Steffen


title: Lrc - A Generator for Incremental Language-Oriented Tools

authors:
Matthijs F. Kuiper
João Saraiva


title: Extended SSA Numbering: Introducing SSA Properties to Language with Multi-level Pointers

authors:
Christopher Lapkowski
Laurie J. Hendren


title: An Extended Static Checker for Modular-3

authors:
K. Rustan M. Leino
Greg Nelson


title: A New Fast Algorithm for Optimal Register Allocation in Modulo Scheduled Loops

authors:
Sylvain Lelait
Guang R. Gao
Christine Eisenbeis


title: Local Stack Allocation

authors:
Martin Maierhofer
M. Anton Ertl


title: A New Approach to Control Flow Analysis

authors:
Pasquale Malacaria
Chris Hankin


title: Analysis of Loops

authors:
Florian Martin
Martin Alt
Reinhard Wilhelm
Christian Ferdinand


title: Storage Allocation Strategies for Recursive Attributes Evaluators

authors:
Kazunori Mizushima
Takuya Katayama


title: Flow Logics for Constraint Based Analysis

authors:
Hanne Riis Nielson
Flemming Nielson


title: Portable Debugging and Profiling


title: Intermodular Slicing of Object-oriented Programs


title: VLIW Compilation Techniques for Superscalar Architectures

authors:
Esther Stümpel
Michael Thies
Uwe Kastens


title: Tool Support for Language Design and Prototyping with Montages

authors:
Matthias Anlauff
Philipp W. Kutter
Alfonso Pierantonio


title: Faster Generalized LR Parsing

authors:
John Aycock
R. Nigel Horspool

abstract: Tomita devised a method of generalized LR (GLR) parsing to parse ambiguous grammars efficiently. A GLR parser uses linear-time LR parsing techniques as long as possible, falling back on more expensive general techniques when necessary.Much research has addressed speeding up LR parsers. However, we argue that this previous work is not transferable to GLR parsers. Instead, we speed up LR parsers by building larger pushdown automata, trading space for time. A variant of the GLR algorithm then incorporates our faster LR parsers.Our timings show that our new method for GLR parsing can parse highly ambiguous grammars significantly faster than a standard GLR parser.


title: A Programmable ANSI C Transformation Engine

authors:
Maarten Boekhold
Ireneusz Karkowski
Henk Corporaal
Andrea G. M. Cilio


title: Compilation and Memory Management for ASF+SDF

authors:
Mark van den Brand
Paul Klint
Pieter A. Olivier


title: Floating Point to Fixed Point Conversion of C Code

authors:
Andrea G. M. Cilio
Henk Corporaal


title: Link-Time Improvement of Scheme Programs

authors:
Saumya K. Debray
Robert Muth
Scott A. Watterson


title: Extending Modulo Scheduling with Memory Reference Merging


title: TRAPing Modelica with Python


title: Register Pressure Sensitive Redundancy Elimination

authors:
Rajiv Gupta
Rastislav Bodík


title: Code Optimization by Integer Linear Programming

authors:
Daniel Kästner
Marc Langenbach


title: Expansion-Based Removal of Semantic Partial Redundancies

authors:
Jens Knoop
Oliver Rüthing
Bernhard Steffen


title: Evaluation of Algorithms for Local Register Allocation

authors:
Vincenzo Liberatore
Martin Farach-Colton
Ulrich Kremer


title: Experimental Comparison of call string and functional Approaches to Interprocedural Analysis


title: Interprocedural Path Profiling

authors:
David Melski
Thomas W. Reps


title: Implementation Issues of Loop-Level Speculative Run-Time Parallelization

authors:
Devang Patel
Lawrence Rauchwerger


title: A Comparison of Compiler Tiling Algorithms

authors:
Gabriel Rivera
Chau-Wen Tseng


title: Virtual Cache Line: A New Technique to Improve Cache Exploitation for Recursive Data Structures

authors:
Shai Rubin
David Bernstein
Michael Rodeh


title: The Design of the PROMIS Compiler

authors:
Hideki Saito
Nicholas Stavrakos
Steven Carroll
Constantine D. Polychronopoulos
Alexandru Nicolau


title: Data Structure Free Compilation

authors:
João Saraiva
S. Doaitse Swierstra


title: Debugging Eli-Generated Compilers With Noosa


title: Optimizing Object-Oriented Languages Through Architechtural Transformations

authors:
Tom Tourwé
Wolfgang De Meuter


title: Efficient State-Diagram Construction Methods for Software Pipelining

authors:
Chihong Zhang
Ramaswamy Govindarajan
Sean Ryan
Guang R. Gao


title: Demand-Driven Construction of Call Graphs


title: Simple Generation of Static Single-Assignment Form

authors:
John Aycock
R. Nigel Horspool


title: Fast Escape Analysis and Stack Allocation for Object-Based Programs

authors:
David Gay
Bjarne Steensgaard


title: Global Software Pipelining with Iteration Preselection


title: Pipelined Java Virtual Machine Interpreters

authors:
Jan Hoogerbrugge
Lex Augusteijn


title: Advanced Compiler Optimization for Calm RISC8 Low-End Embedded Processor


title: Constant Propagation on the Value Graph: Simple Constants and Beyond

authors:
Jens Knoop
Oliver Rüthing


title: Analysis of Irregular Single-Indexed Array Accesses and Its Applications in Compiler Optimizations

authors:
Yuan Lin
David A. Padua


title: MATOU: An Implementation of Mode-Automata

authors:
Florence Maraninchi
Yann Rémond
Yannick Raoul


title: Advanced Scalarization of Array Syntax


title: A Static Study of Java Exceptions Using JESP

authors:
Barbara G. Ryder
Donald Smith
Ulrich Kremer
Michael Gordon
Nirav Shah


title: Functional Incremental Attribute Evaluation

authors:
João Saraiva
S. Doaitse Swierstra
Matthijs F. Kuiper


title: Automatic Removal of Array Memory Leaks in Java

authors:
Ran Shaham
Elliot K. Kolodner
Shmuel Sagiv


title: Compiling Adaptive Programs by Partial Evaluation


title: Techniques for Effectively Exploiting a Zero Overhead Loop Buffer

authors:
Gang-Ryung Uh
Yuhong Wang
David B. Whalley
Sanjay Jinturkar
Chris Burns
Vincent Cao


title: Optimizing Java Bytecode Using the Soot Framework: Is It Feasible?

authors:
Raja Vallée-Rai
Etienne Gagnon
Laurie J. Hendren
Patrick Lam
Patrice Pominville
Vijay Sundaresan


title: A Framework for Loop Distribution on Limited On-Chip Memory Processors

authors:
Lei Wang
Waibhav Tembe
Santosh Pande


title: Shape Analysis

authors:
Reinhard Wilhelm
Shmuel Sagiv
Thomas W. Reps


title: Techniques for Reducing the Overhead of Run-Time Parallelization

authors:
Hao Yu
Lawrence Rauchwerger


title: SmartTools: A Generator of Interactive Environments Tools

authors:
Isabelle Attali
Carine Courbis
Pascal Degenne
Alexandre Fau
Didier Parigot
Claude Pasquier


title: Directly-Executable Earley Parsing


title: The ASF+SDF Meta-environment: A Component-Based Language Development Environment

authors:
Mark van den Brand
Arie van Deursen
Jan Heering
H. A. de Jong
Merijn de Jonge
Tobias Kuipers
Paul Klint
Leon Moonen
Pieter A. Olivier
Jeroen Scheerder
Jurgen J. Vinju
Eelco Visser
Joost Visser


title: Efficient Symbolic Analysis for Optimizing Compilers


title: A Bounded Graph-Connect Construction for LR-regular Parsers

authors:
Jacques Farré
José Fortes Gálvez


title: Compiler Transformation of Pointers to Explicit Array Accesses in DSP Applications

authors:
Björn Franke
Michael F. P. O'Boyle


title: Comparing Tail Duplication with Compensation Code in Single Path Global Instruction Scheduling


title: Visual Patterns in the VLEli System

authors:
Matthias T. Jung
Uwe Kastens
Christian Schindler
Carsten Schmidt


title: Array Unification: A Locality Optimization Technique


title: Imperative Program Transformation by Rewriting

authors:
David Lacey
Oege de Moor


title: Virtual Classes and Their Implementation

abstract: One of the characteristics of BETA [ 4 ] is the unification of abstraction mechanisms such as class, procedure, process type, generic class, interface, etc. into one abstraction mechanism: the pattern . In addition to keeping the language small, the unification has given a systematic treatment of all abstraction mechanisms and leads to a number of new possibilities. One of the interesting results of the unification is the notion of virtual class [[ 7 ],[ 8 ], which is the BETA mechanism for expressing genericity. A class may define an attribute in the form of a virtual class just as a class may define an attribute in the form of a virtual procedure. A subclass may then refine the definition of the virtual class attribute into a more specialized class. This is very much in the same way as a virtual procedure can be refined - resulting in a more specialized procedure. Virtual classes can be seen as an object-oriented version of generics. Other attempts to provide genericity for OO languages has been based on various forms of parametric polymorphism and function application rather than inheritance. Virtual classes have been used for more than 15 years in the BETA community and they have demonstrated their usefulness as a powerful abstraction mechanism. There has recently been an increasing interest in virtual classes and a number of proposals for adding virtual classes to other languages, extending virtual classes, and unifying virtual classes and parameterized classes have been made [[ 1 ],[ 2 ],[ 3 ],[ 13 ],[ 14 ],[ 15 ],[ 16 ],[ 17 ]. Another distinguishing feature of BETA is the notion of nested class [ 6 ]. The nested class construct originates already with Simula and is supported in a more general form in BETA. Nested classes have thus been available to the OO community for almost 4 decades, and the mechanism has found many uses in particular to structure large systems. Despite the usefulness, mainstream OO languages have not included general nesting mechanisms although C++ has a restricted form of nested classes, only working as a scoping mechanism. Recently nested classes has been added to the Java language. From a semantic analysis point of view the combination of inheritance, and general nesting adds some complexity to the semantic analysis, since the search space for names becomes two-dimensional. With virtual classes, the analysis becomes even more complicated — for details see ref. [ 10 ]. The unification of class and procedure has also lead to an inheritance mechanism for procedures [ 5 ] where method-combination is based on the inner -construct known from Simula. In BETA, patterns are first-class values , which implies that procedures as well as classes are first-class values. BETA also supports the notion of class-less objects, which has been adapted in the form of anonymous classes in Java. Finally, it might be mentioned that BETA supports coroutines as well as concurrent active objects . For further details about BETA, see [ 6 , 9 , 11 ]. The Mjølner System is a program development environment for BETA and may be obtained from ref. [ 12 ].


title: Alias Analysis by Means of a Model Checker

authors:
Vincenzo Martena
Pierluigi San Pietro


title: A Novel Probabilistic Data Flow Framework

authors:
Eduard Mehofer
Bernhard Scholz


title: Software Pipelining of Nested Loops

authors:
Kalyan Muthukumar
Gautam Doshi


title: Optimal Live Range Merge for Address Register Allocation in Embedded Programs

authors:
Guilherme Ottoni
Sandro Rigo
Guido Araujo
Subramanian Rajagopalan
Sharad Malik


title: A Framework for Optimizing Java Using Attributes

authors:
Patrice Pominville
Feng Qian
Raja Vallée-Rai
Laurie J. Hendren
Clark Verbrugge


title: Interprocedural Shape Analysis for Recursive Programs

authors:
Noam Rinetzky
Shmuel Sagiv


title: Points-to and Side-Effect Analyses for Programs Built with Precompiled Libraries

authors:
Atanas Rountev
Barbara G. Ryder


title: Design-Driven Compilation

authors:
Radu Rugina
Martin C. Rinard


title: User-Extensible Simplification - Type-Based Optimizer Generators

authors:
Sibylle Schupp
Douglas P. Gregor
David R. Musser
Shin-Ming Liu


title: Constant-Time Root Scanning for Deterministic Garbage Collection


title: Speculative Prefetching of Induction Pointers

authors:
Artour Stoutchinin
José Nelson Amaral
Guang R. Gao
James C. Dehnert
Suneel Jain
Alban Douillet


title: A Practical, Robust Method for Generating Variable Range Tables

authors:
Caroline Tice
Susan L. Graham


title: Register Saturation in Superscalar and VLIW Codes


title: Goal-Directed Value Profiling

authors:
Scott A. Watterson
Saumya K. Debray


title: A First Step Towards Time Optimal Software Pipelining of Loops with Control Flows

authors:
Han-Saem Yun
Jihong Kim
Soo-Mook Moon


title: Evaluating a Demand Driven Technique for Call Graph Construction

authors:
Gagan Agrawal
Jinqian Li
Qi Su


title: Disambiguation Filters for Scannerless Generalized LR Parsers

authors:
Mark van den Brand
Jeroen Scheerder
Jurgen J. Vinju
Eelco Visser


title: Global Variable Promotion: Using Registers to Reduce Cache Power Dissipation

authors:
Andrea G. M. Cilio
Henk Corporaal


title: Modular Static Program Analysis

authors:
Patrick Cousot
Radhia Cousot


title: Building an Interpreter with Vmgen

authors:
M. Anton Ertl
David Gregg


title: Compiler Construction Using LOTOS NT

authors:
Hubert Garavel
Frédéric Lang
Radu Mateescu


title: Precise Exception Semantics in Dynamic Compilation

authors:
Michael Gschwind
Erik R. Altman


title: A Representation for Bit Section Based Analysis and Optimization

authors:
Rajiv Gupta
Eduard Mehofer
Youtao Zhang


title: Compiling Mercury to High-Level C Code

authors:
Fergus Henderson
Zoltan Somogyi


title: Influence of Loop Optimizations on Energy Consumption of Multi-bank Memory Systems

authors:
Mahmut T. Kandemir
Ibrahim Kolcu
Ismail Kadayif


title: LISA: An Interactive Environment for Programming Language Development

authors:
Marjan Mernik
Mitja Lenic
Enis Avdicausevic
Viljem Zumer


title: Decompiling Java Bytecode: Problems, Traps and Pitfalls

authors:
Jerome Miecznikowski
Laurie J. Hendren


title: Effective Enhancement of Loop Versioning in Java

authors:
Vitaly V. Mikheev
Stanislav A. Fedoseev
Vladimir V. Sukharev
Nikita V. Lipsky


title: A Graph-Free Approach to Data-Flow Analysis


title: Linear Scan Register Allocation in the Context of SSA Form and Register Constraints

authors:
Hanspeter Mössenböck
Michael Pfeiffer


title: CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs

authors:
George C. Necula
Scott McPeak
Shree Prakash Rahul
Westley Weimer


title: Online Subpath Profiling

authors:
David Oren
Yossi Matias
Shmuel Sagiv


title: A Comprehensive Approach to Array Bounds Check Elimination for Java

authors:
Feng Qian
Laurie J. Hendren
Clark Verbrugge


title: Optimizing Static Power Dissipation by Functional Units in Superscalar Processors

authors:
Siddharth Rele
Santosh Pande
Soner Önder
Rajiv Gupta


title: StreamIt: A Language for Streaming Applications

authors:
William Thies
Michal Karczmarek
Saman P. Amarasinghe

abstract: We characterize high-performance streaming applications as a new and distinct domain of programs that is becoming increasingly important. The StreamIt language provides novel high-level representations to improve programmer productivity and program robustness within the streaming domain. At the same time, the StreamIt compiler aims to improve the performance of streaming applications via stream-specific analyses and optimizations. In this paper, we motivate, describe and justify the language features of StreamIt, which include: a structured model of streams, a messaging system for control, a re-initialization mechanism, and a natural textual syntax.


title: Value-Profile Guided Stride Prefetching for Irregular Code

authors:
Youfeng Wu
Mauricio J. Serrano
Rakesh Krishnaiyer
Wei Li
Jesse Fang


title: Forwarding in Attribute Grammars for Modular Language Design

authors:
Eric Van Wyk
Oege de Moor
Kevin Backhouse
Paul Kwiatkowski


title: Data Compression Transformations for Dynamically Allocated Data Structures

authors:
Youtao Zhang
Rajiv Gupta


title: Register Allocation by Optimal Graph Coloring


title: Integrating Generations with Advanced Reference Counting Garbage Collectors

authors:
Hezi Azatchi
Erez Petrank


title: Improving Data Locality by Chunking

authors:
Cédric Bastoul
Paul Feautrier


title: Run-Time Type Checking for Binary Programs

authors:
Michael Burrows
Stephen N. Freund
Janet L. Wiener


title: A New One-Pass Transformation into Monadic Normal Form

abstract: We present a translation from the call-by-value λ-calculus to monadic normal forms that includes short-cut boolean evaluation. The translation is higher-order, operates in one pass, duplicates no code, generates no chains of thunks, and is properly tail recursive. It makes a crucial use of symbolic computation at translation time.


title: Effective Inline-Threaded Interpretation of Java Bytecode Using Preparation Sequences

authors:
Etienne Gagnon
Laurie J. Hendren


title: Integrating High-Level Optimizations in a Production Compiler: Design and Implementation Experience

authors:
Somnath Ghosh
Abhay Kanhere
Rakesh Krishnaiyer
Dattatraya Kulkarni
Wei Li
Chu-Cheow Lim
John Ng


title: The Verifying Compiler: A Grand Challenge for Computing Research


title: Combined Code Motion and Register Allocation Using the Value State Dependence Graph

authors:
Neil Johnson
Alan Mycroft


title: Generalised Regular Parsers

authors:
Adrian Johnstone
Elizabeth Scott


title: The MAGICA Type Inference Engine for MATLAB

authors:
Pramod G. Joisha
Prithviraj Banerjee


title: Address Register Assignment for Reducing Code Size

authors:
Mahmut T. Kandemir
Mary Jane Irwin
Guilin Chen
J. Ramanujam


title: Precision in Practice: A Type-Preserving Java Compiler

authors:
Christopher League
Zhong Shao
Valery Trifonov


title: Offset Assignment Showdown: Evaluation of DSP Address Code Optimization Algorithms


title: Scaling Java Points-to Analysis Using SPARK

authors:
Ondrej Lhoták
Laurie J. Hendren


title: A Compilation and Optimization Model for Aspect-Oriented Programs

authors:
Hidehiko Masuhara
Gregor Kiczales
Christopher Dutchyn


title: The Interprocedural Express-Lane Transformation

authors:
David Melski
Thomas W. Reps


title: A Pattern Matching Compiler for Multiple Target Languages

authors:
Pierre-Etienne Moreau
Christophe Ringeissen
Marian Vittek


title: Automatic Detection of Uninitialized Variables

authors:
Thi Viet Nga Nguyen
François Irigoin
Corinne Ancourt
Fabien Coelho


title: Polyglot: An Extensible Compiler Framework for Java

authors:
Nathaniel Nystrom
Michael R. Clarkson
Andrew C. Myers


title: Rapid and Robust Compiler Construction Using Template-Based Metacompilation


title: Dimensions of Precision in Reference Analysis of Object-Oriented Programming Languages


title: Early Control of Register Pressure for Software Pipelined Loops

authors:
Sid Ahmed Ali Touati
Christine Eisenbeis


title: Analyzing Memory Accesses in x86 Executables

authors:
Gogul Balakrishnan
Thomas W. Reps


title: Region-Based Partial Dead Code Elimination on Predicated Code

authors:
Qiong Cai
Lin Gao
Jingling Xue


title: Data Dependence Profiling for Speculative Optimizations

authors:
Tong Chen
Jin Lin
Xiaoru Dai
Wei-Chung Hsu
Pen-Chung Yew


title: The Limits of Alias Analysis for Scalar Optimizations

authors:
Rezaul Alam Chowdhury
Peter Djeu
Brendon Cahoon
James H. Burrill
Kathryn S. McKinley


title: A Symbolic Approach to Bernstein Expansion for Program Analysis and Optimization

authors:
Philippe Clauss
Irina Tchoupaeva


title: Using Multiple Memory Access Instructions for Reducing Code Size

authors:
Neil Johnson
Alan Mycroft


title: Generalised Parsing: Some Costs

authors:
Adrian Johnstone
Elizabeth Scott
Giorgios Economopoulos

abstract: We discuss generalisations of bottom up parsing, emphasising the relative costs for real programming languages. Our goal is to provide a roadmap of the available approaches in terms of their space and time performance for programming language applications, focusing mainly on GLR style algorithms. It is well known that the original Tomita GLR algorithm fails to terminate on hidden left recursion: here we analyse two approaches to correct GLR parsing (i) the modification due to Farshi that is incorporated into Visser’s work and (ii) our own right-nullable GLR (RNGLR) algorithm, showing that Farshi’s approach can be expensive. We also present results from our new Binary RNGLR algorithm which is asymptotically the fastest parser in this family and show that the recently reported reduction incorporated parsers can require automata that are too large to be practical on current machines. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


title: FFT Compiler Techniques

authors:
Stefan Kral
Franz Franchetti
Juergen Lorenz
Christoph W. Ueberhuber
Peter Wurzinger


title: Integrating the Soot Compiler Infrastructure into an IDE

authors:
Jennifer Lhoták
Ondrej Lhoták
Laurie J. Hendren


title: Declarative Composition of Stack Frames

authors:
Christian Lindig
Norman Ramsey


title: Elkhound: A Fast, Practical GLR Parser Generator

authors:
Scott McPeak
George C. Necula


title: Periodic Polyhedra


title: Reducing the Cost of Object Boxing

authors:
Tim Owen
Des Watson


title: Stochastic Bit-Width Approximation Using Extreme Value Theory for Customizable Processors

authors:
Emre Özer
Andy Nisbet
David Gregg


title: An Automata-Theoretic Algorithm for Counting Solutions to Presburger Formulas

authors:
Erin Parker
Siddhartha Chatterjee


title: Pruning Interference and Ready Dependence for Slicing Concurrent Java Programs

authors:
Venkatesh Prasad Ranganath
John Hatcliff


title: Widening Integer Arithmetic

authors:
Kevin Redwine
Norman Ramsey


title: Increasing the Applicability of Scalar Replacement

authors:
Byoungro So
Mary W. Hall


title: Developing a Foundation for Code Optimization


title: Value-Based Partial Redundancy Elimination

authors:
Thomas VanDrunen
Antony L. Hosking


title: CodeSurfer/x86-A Platform for Analyzing x86 Executables

authors:
Gogul Balakrishnan
Radu Gruian
Thomas W. Reps
Tim Teitelbaum


title: Generalized Index-Set Splitting

authors:
Christopher Barton
Arie Tal
Bob Blainey
José Nelson Amaral


title: Tiger - An Interpreter Generation Tool

authors:
Kevin Casey
David Gregg
M. Anton Ertl


title: Data Slicing: Separating the Heap into Independent Regions

authors:
Jeremy Condit
George C. Necula


title: Task Partitioning for Multi-core Network Processors

authors:
Robert Ennals
Richard Sharp
Alan Mycroft


title: XML Goes Native: Run-Time Representations for Xtatic

authors:
Vladimir Gapeyev
Michael Y. Levin
Benjamin C. Pierce
Alan Schmitt


title: Boosting the Performance of Multimedia Applications Using SIMD Instructions

authors:
Weihua Jiang
Chao Mei
Bo Huang
Jianhui Li
Jiahua Zhu
Binyu Zang
Chuanqi Zhu


title: Hob: A Tool for Verifying Data Structure Consistency

authors:
Patrick Lam
Viktor Kuncak
Martin C. Rinard


title: Using Inter-Procedural Side-Effect Information in JIT Optimizations

authors:
Anatole Le
Ondrej Lhoták
Laurie J. Hendren


title: A Compiler-Based Approach to Data Security

authors:
Feihui Li
Guilin Chen
Mahmut T. Kandemir
Richard R. Brooks


title: Jazz: A Tool for Demand-Driven Structural Testing

authors:
Jonathan Misurda
James A. Clause
Juliya L. Reed
Bruce R. Childers
Mary Lou Soffa


title: Composing Source-to-Source Data-Flow Transformations with Rewriting Strategies and Dependent Dynamic Rewrite Rules

authors:
Karina Olmos
Eelco Visser


title: Compilation of Generic Regular Path Expressions Using C++ Class Templates


title: Age-Oriented Concurrent Garbage Collection

authors:
Harel Paz
Erez Petrank
Stephen M. Blackburn


title: An Efficient On-the-Fly Cycle Collection

authors:
Harel Paz
Erez Petrank
David F. Bacon
Elliot K. Kolodner
V. T. Rajan


title: A Study of Type Analysis for Speculative Method Inlining in a JIT Environment

authors:
Feng Qian
Laurie J. Hendren


title: Source-Level Debugging for Multiple Languages with Modest Programming Effort

authors:
Sukyoung Ryu
Norman Ramsey

abstract: We present techniques that enable source-level debugging for multiple languages at the cost of only modest programming effort. The key idea is to avoid letting debugging requirements constrain the internal structure of the compiler. Constraints are minimized primarily by hiding the source-language type system and target-machine representations from the debugger. This approach enables us to support a new language and compiler while reusing existing elements: a multi-language, multi-platform debugger; the compiler's implementation of source-language types and expressions; information already present in the compiler's private data structures; and our compile-time support library, which helps the compiler meet its obligations to the debugger without exposing language-dependent details. We evaluate our approach using two case studies: the production compiler lcc and an instructional compiler for MiniJava.


title: Optimizing C Multithreaded Memory Management Using Thread-Local Storage

authors:
Yair Sade
Shmuel Sagiv
Ran Shaham


title: Verification of Source Code Transformations by Program Equivalence Checking

authors:
K. C. Shashidhar
Maurice Bruynooghe
Francky Catthoor
Gerda Janssens


title: Experiences with Enumeration of Integer Projections of Parametric Polytopes

authors:
Sven Verdoolaege
Kristof Beyls
Maurice Bruynooghe
Francky Catthoor


title: Completeness Analysis for Incomplete Object-Oriented Programs

authors:
Jingling Xue
Phung Hua Nguyen


title: When Abstraction Fails


title: Iterative Collective Loop Fusion

authors:
Thomas J. Ashby
Michael F. P. O'Boyle


title: Demonstration: On-Line Visualization and Analysis of Real-Time Systems with TuningFork

authors:
David F. Bacon
Perry Cheng
Daniel Frampton
David Grove
Matthias Hauswirth
V. T. Rajan


title: Enhanced Bitwidth-Aware Register Allocation

authors:
Rajkishore Barik
Vivek Sarkar


title: Hybrid Optimizations: Which Optimization Algorithm to Use?

authors:
John Cavazos
J. Eliot B. Moss
Michael F. P. O'Boyle


title: Converting Intermediate Code to Assembly Code Using Declarative Machine Descriptions

authors:
João Dias
Norman Ramsey


title: Path-Based Reuse Distance Analysis

authors:
Changpeng Fang
Steve Carr
Soner Önder
Zhenlin Wang


title: Accurately Choosing Execution Runs for Software Fault Localization

authors:
Liang Guo
Abhik Roychoudhury
Tao Wang


title: Selective Runtime Memory Disambiguation in a Dynamic Binary Translator

authors:
Bolei Guo
Youfeng Wu
Cheng Wang
Matthew J. Bridges
Guilherme Ottoni
Neil Vachharajani
Jonathan Chang
David I. August


title: Register Allocation for Programs in SSA-Form

authors:
Sebastian Hack
Daniel Grund
Gerhard Goos

abstract: As register allocation is one of the most important phases in optimizing compilers, much work has been done to improve its quality and speed. We present a novel register allocation architecture for programs in SSA-form which simplifies register allocation significantly. We investigate certain properties of SSA-programs and their interference graphs, showing that they belong to the class of chordal graphs. This leads to a quadratic-time optimal coloring algorithm and allows for decoupling the tasks of coloring, spilling and coalescing completely. After presenting heuristic methods for spilling and coalescing, we compare our coalescing heuristic to an optimal method based on integer linear programming.


title: Loop Transformations in the Ahead-of-Time Optimization of Java Bytecode

authors:
Simon D. Hammond
David Lacey

abstract:
Loop optimizations such as loop unrolling, unfolding and invariant code motion have long been used in a wide variety of compilers to improve the running time of applications. In this paper we present a series of experimental results detailing the effect these techniques have on the running time of Java applications following ahead of time optimization.

We also detail the optimization tools and transformations developed for this paper which extend the SOOT framework discussed in a number of previous papers on the subject.

Our experimentation, conducted on the SciMark 2.0 benchmarking suite, demonstrates that when optimized using the techniques mentioned, Java applications can benefit from performance improvements of up to 20%.

We finish with a discussion of the results obtained, including results on how the optimizations affect JIT compilation and class size and proceed to argue that ahead-of-time loop unrolling and unfolding optimization may have a role to play in improving the performance of Java applications, particularly in scientific applications.


title: Data-Flow Analysis as Model Checking Within the jABC

authors:
Anna-Lena Lamprecht
Tiziana Margaria
Bernhard Steffen


title: Context-Sensitive Points-to Analysis: Is It Worth It?

authors:
Ondrej Lhoták
Laurie J. Hendren


title: Performance Characterization of the 64-bit x86 Architecture from Compiler Optimizations' Perspective

authors:
Jack Liu
Youfeng Wu


title: The CGiS Compiler-A Tool Demonstration

authors:
Philipp Lucas
Nicolas Fritz
Reinhard Wilhelm


title: SARA: Combining Stack Allocation and Register Allocation

authors:
V. Krishna Nandivada
Jens Palsberg


title: Using Dependent Types to Port Type Systems to Low-Level Languages


title: Interprocedural Dataflow Analysis in the Presence of Large Libraries

authors:
Atanas Rountev
Scott Kagan
Thomas J. Marlowe


title: Efficient Flow-Sensitive Interprocedural Data-Flow Analysis in the Presence of Pointers

authors:
Teck Bok Tok
Samuel Z. Guyer
Calvin Lin


title: Polyhedral Code Generation in the Real World

authors:
Nicolas Vasilache
Cédric Bastoul
Albert Cohen


title: A Fresh Look at PRE as a Maximum Flow Problem

authors:
Jingling Xue
Jens Knoop


title: Lightweight Lexical Closures for Legitimate Execution Stack Access

authors:
Masahiro Yasugi
Tasuku Hiraishi
Taiichi Yuasa


title: Accurate Garbage Collection in Uncooperative Environments with Lazy Pointer Stacks

authors:
Jason Baker
Antonio Cunei
Filip Pizlo
Jan Vitek


title: Obfuscating Java: The Most Pain for the Least Gain

authors:
Michael Batchelder
Laurie J. Hendren


title: Program Refactoring, Program Synthesis, and Model-Driven Development


title: A Practical Escape and Effect Analysis for Building Lightweight Method Summaries

authors:
Sigmund Cherem
Radu Rugina


title: Preprocessing Strategy for Effective Modulo Scheduling on Multi-issue Digital Signal Processors

authors:
Doosan Cho
Ravi Ayyagari
Gang-Ryung Uh
Yunheung Paek


title: A Declarative Framework for Analysis and Optimization

authors:
Henry Falconer
Paul H. J. Kelly
David M. Ingram
Michael R. Mellor
Tony Field
Olav Beckmann


title: New Algorithms for SIMD Alignment

authors:
Liza Fireman
Erez Petrank
Ayal Zaks


title: A Fast Cutting-Plane Algorithm for Optimal Coalescing

authors:
Daniel Grund
Sebastian Hack


title: Layout Transformations for Heap Objects Using Static Access Patterns

authors:
Jinseong Jeon
Keoncheol Shin
Hwansoo Han


title: Correcting the Dynamic Call Graph Using Control-Flow Constraints

authors:
Byeongcheol Lee
Kevin Resnick
Michael D. Bond
Kathryn S. McKinley


title: Register Allocation and Optimal Spill Code Scheduling in Software Pipelined Loops Using 0-1 Integer Linear Programming Formulation

authors:
Santosh Nagarakatte
R. Govindarajan


title: Using Prefetching to Improve Reference-Counting Garbage Collectors

authors:
Harel Paz
Erez Petrank


title: Extended Linear Scan: An Alternate Foundation for Global Register Allocation

authors:
Vivek Sarkar
Rajkishore Barik


title: A New Elimination-Based Data Flow Analysis Framework Using Annotated Decomposition Trees

authors:
Bernhard Scholz
Johann Blieberger


title: An Array Allocation Scheme for Energy Reduction in Partitioned Memory Architectures

authors:
K. Shyam
R. Govindarajan


title: Hardware JIT Compilation for Off-the-Shelf Dynamically Reconfigurable FPGAs

authors:
Etienne Bergeron
Marc Feeley
Jean-Pierre David


title: Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model

authors:
Uday Bondhugula
Muthu Manikandan Baskaran
Sriram Krishnamoorthy
J. Ramanujam
Atanas Rountev
P. Sadayappan


title: An Adaptive Strategy for Inline Substitution

authors:
Keith D. Cooper
Timothy J. Harvey
Todd Waterman


title: Keep Off the Grass: Locking the Right Path for Atomicity

authors:
Dave Cunningham
Khilan Gudka
Susan Eisenbach


title: Generating SIMD Vectorized Permutations

authors:
Franz Franchetti
Markus Püschel


title: Efficiency, Precision, Simplicity, and Generality in Interprocedural Data Flow Analysis: Resurrecting the Classical Call Strings Method

authors:
Uday P. Khedker
Bageshri Karkare


title: Control Flow Emulation on Tiled SIMD Architectures

authors:
Ghulam Lashari
Ondrej Lhoták
Michael McCool


title: A System for Generating Static Analyzers for Machine Instructions

authors:
Junghee Lim
Thomas W. Reps


title: Coqa: Concurrent Objects with Quantized Atomicity

authors:
Yu David Liu
Xiaoqi Lu
Scott F. Smith


title: On the Relative Completeness of Bytecode Analysis Versus Source Code Analysis

authors:
Francesco Logozzo
Manuel Fähndrich


title: Java Bytecode Verification for @NonNull Types

authors:
Chris Male
David J. Pearce
Alex Potanin
Constantine Dymnikov


title: Efficient Context-Sensitive Shape Analysis with Graph Based Heap Models

authors:
Mark Marron
Manuel V. Hermenegildo
Deepak Kapur
Darko Stefanovic


title: Automatic Transformation of Bit-Level C Code to Support Multiple Equivalent Data Layouts

authors:
Marius Nita
Dan Grossman


title: Compiler-Guaranteed Safety in Code-Copying Virtual Machines

authors:
Gregory B. Prokopski
Clark Verbrugge

abstract: Virtual Machine authors face a difficult choice between low performance, cheap interpreters, or specialized and costly compilers. A method able to bridge this wide gap is the existing code-copying technique that reuses chunks of the VM’s binary code to create a simple JIT. This technique is not reliable without a compiler guaranteeing that copied chunks are still functionally equivalent despite aggressive optimizations. We present a proof-of-concept, minimal-impact modification of a highly optimizing compiler, GCC. A VM programmer marks chunks of VM source code as copyable. The chunks of native code resulting from compilation of the marked source become addressable and self-contained. Chunks can be safely copied at VM runtime, concatenated and executed together. This allows code-copying VMs to safely achieve speedup up to 3 times, 1.67 on average, over the direct interpretation. This maintainable enhancement makes the code-copying technique reliable and thus practically usable.


title: Improved Memory-Access Analysis for x86 Executables

authors:
Thomas W. Reps
Gogul Balakrishnan


title: IDE Dataflow Analysis in the Presence of Large Object-Oriented Libraries

authors:
Atanas Rountev
Mariana Sharp
Guoqing Xu


title: Design Choices in a Compiler Course or How to Make Undergraduates Love Formal Notation


title: Supporting Legacy Binary Code in a Software Transaction Compiler with Dynamic Binary Translation and Optimization

authors:
Cheng Wang
Victor Ying
Youfeng Wu


title: Visualization of Program Dependence Graphs

authors:
Thomas Würthinger
Christian Wimmer
Hanspeter Mössenböck


title: How to Do a Million Watchpoints: Efficient Debugging Using Dynamic Instrumentation

authors:
Qin Zhao
Rodric M. Rabbah
Saman P. Amarasinghe
Larry Rudolph
Weng-Fai Wong

abstract: Application debugging is a tedious but inevitable chore in any software development project. An effective debugger can make programmers more productive by allowing them to pause execution and inspect the state of the process, or monitor writes to memory to detect data corruption. This paper introduces the new concept of Efficient Debugging using Dynamic Instrumentation (EDDI). The paper demonstrates for the first time the feasibility of using dynamic instrumentation ondemand to accelerate software debuggers, especially when the available hardware support is lacking or inadequate. As an example, EDDI can simultaneously monitor millions of memory locations without crippling the host processing platform. It does this in software and hence provides a portable debugging environment. It is also well suited for interactive debugging because of its low overhead. EDDI provides a scalable and extensible debugging framework that can substantially increase the feature set of current debuggers.


title: Implementation and Use of Transactional Memory with Dynamic Separation

authors:
Martín Abadi
Andrew Birrell
Tim Harris
Johnson Hsieh
Michael Isard


title: Scheduling Tasks to Maximize Usage of Aggregate Variables in Place

authors:
Samah Abu-Mahmeed
Cheryl McCosh
Zoran Budimlic
Ken Kennedy
Kaushik Ravindran
Kevin Hogan
Paul Austin
Steve Rogers
Jacob Kornerup


title: How to CPS Transform a Monad

authors:
Annette Bieniusa
Peter Thiemann


title: Register Spilling and Live-Range Splitting for SSA-Form Programs

authors:
Matthias Braun
Sebastian Hack


title: Dynamic Look Ahead Compilation: A Technique to Hide JIT Compilation Latencies in Multicore Environment

authors:
Simone Campanoni
Martino Sykora
Giovanni Agosta
Stefano Crespi Reghizzi


title: Live Debugging of Distributed Systems

authors:
Darren Dao
Jeannie R. Albrecht
Charles Killian
Amin Vahdat


title: Faster Scannerless GLR Parsing

authors:
Giorgios Economopoulos
Paul Klint
Jurgen J. Vinju


title: Loop-Aware Instruction Scheduling with Dynamic Contention Tracking for Tiled Dataflow Architectures

authors:
Muhammad Umar Farooq
Lizy K. John


title: Exploiting Speculative TLP in Recursive Programs by Dynamic Thread Prediction

authors:
Lin Gao
Lian Li
Jingling Xue
Tin-Fook Ngai


title: Precise Management of Scratchpad Memories for Localising Array Accesses in Scientific Codes


title: Decorated Attribute Grammars: Attribute Evaluation Meets Strategic Programming

authors:
Lennart C. L. Kats
Anthony M. Sloane
Eelco Visser


title: Blind Optimization for Exploiting Hardware Features

authors:
Dan Knights
Todd Mytkowicz
Peter F. Sweeney
Michael C. Mozer
Amer Diwan


title: Extensible Proof-Producing Compilation

authors:
Magnus O. Myreen
Konrad Slind
Michael J. C. Gordon


title: Parsing C/C++ Code without Pre-processing


title: SSA Elimination after Register Allocation

authors:
Fernando Magno Quintão Pereira
Jens Palsberg


title: Challenges in Code Optimization of Parallel Programs


title: Compile-Time Analysis and Specialization of Clocks in Concurrent Programs

authors:
Nalini Vasudevan
Olivier Tardieu
Julian Dolby
Stephen A. Edwards


title: From Specification to Optimisation: An Architecture for Optimisation of Java Bytecode

authors:
Richard Warburton
Sara Kalvala


title: A Framework for Exploring Optimization Properties

authors:
Min Zhao
Bruce R. Childers
Mary Lou Soffa


title: Automatic C-to-CUDA Code Generation for Affine Programs

authors:
Muthu Manikandan Baskaran
J. Ramanujam
P. Sadayappan


title: The Polyhedral Model Is More Widely Applicable Than You Think

authors:
Mohamed-Walid Benabderrahmane
Louis-Noël Pouchet
Albert Cohen
Cédric Bastoul


title: Preference-Guided Register Assignment

authors:
Matthias Braun
Christoph Mallon
Sebastian Hack


title: Verifying Local Transformations on Relaxed Memory Models

authors:
Sebastian Burckhardt
Madanlal Musuvathi
Vasu Singh


title: Optimizing Matlab through Just-In-Time Specialization

authors:
Maxime Chevalier-Boisvert
Laurie J. Hendren
Clark Verbrugge


title: Using Ownership to Reason about Inherent Parallelism in Object-Oriented Programs

authors:
Andrew Craik
Wayne Kelly


title: Unrestricted Code Motion: A Program Representation and Transformation Algorithms Based on Future Values

authors:
Shuhan Ding
Soner Önder


title: Strategies for Predicate-Aware Register Allocation


title: JReq: Database Queries in Imperative Languages

authors:
Ming-Yee Iu
Emmanuel Cecchet
Willy Zwaenepoel

abstract: Instead of writing SQL queries directly, programmers often prefer writing all their code in a general purpose programming language like Java and having their programs be automatically rewritten to use database queries. Traditional tools such as object-relational mapping tools are able to automatically translate simple navigational queries written in object-oriented code to SQL. More recently, techniques for translating object-oriented code written in declarative or functional styles into SQL have been developed. For code written in an imperative style though, current techniques are still limited to basic queries. JReq is a system that is able to identify complex query operations like aggregation and nesting in imperative code and translate them into efficient SQL queries. The SQL code generated by JReq exhibits performance comparable with hand-written SQL code.


title: Is Reuse Distance Applicable to Data Locality Analysis on Chip Multiprocessors?

authors:
Yunlian Jiang
Eddy Z. Zhang
Kai Tian
Xipeng Shen


title: Mining Opportunities for Code Improvement in a Just-In-Time Compiler

authors:
Adam Jocksch
Marcel Mitran
Joran Siu
Nikola Grcevski
José Nelson Amaral


title: Programming Clouds


title: RATA: Rapid Atomic Type Analysis by Abstract Interpretation - Application to JavaScript Optimization

authors:
Francesco Logozzo
Herman Venter


title: Practical Extensions to the IFDS Algorithm

authors:
Nomair A. Naeem
Ondrej Lhoták
Jonathan Rodriguez


title: Punctual Coalescing


title: Validating Register Allocation and Spilling

authors:
Silvain Rideau
Xavier Leroy


title: The Hot Path SSA Form: Extending the Static Single Assignment Form for Speculative Optimizations

authors:
Subhajit Roy
Y. N. Srikant


title: Clean Translation of an Imperative Reversible Programming Language


title: Interpreter Instruction Scheduling


title: SSA-Based Register Allocation with PBQP

authors:
Sebastian Buchwald
Andreas Zwinkau
Thomas Bersch


title: A Static Task Partitioning Approach for Heterogeneous Systems Using OpenCL

authors:
Dominik Grewe
Michael F. P. O'Boyle


title: Data Layout Transformation for Stencil Computations on Short-Vector SIMD Architectures

authors:
Thomas Henretty
Kevin Stock
Louis-Noël Pouchet
Franz Franchetti
J. Ramanujam
P. Sadayappan

abstract: Stencil computations are at the core of applications in many domains such as computational electromagnetics, image processing, and partial differential equation solvers used in a variety of scientific and engineering applications. Short-vector SIMD instruction sets such as SSE and VMX provide a promising and widely available avenue for enhancing performance on modern processors. However a fundamental memory stream alignment issue limits achieved performance with stencil computations on modern short SIMD architectures. In this paper, we propose a novel data layout transformation that avoids the stream alignment conflict, along with a static analysis technique for determining where this transformation is applicable. Significant performance increases are demonstrated for a variety of stencil codes on three modern SIMD-capable processors.


title: Using Disjoint Reachability for Parallelization

authors:
James Christopher Jenista
Yong Hun Eom
Brian Demsky


title: Subregion Analysis and Bounds Check Elimination for High Level Arrays

authors:
Mackale Joyner
Zoran Budimlic
Vivek Sarkar


title: Staged Static Techniques to Efficiently Implement Array Copy Semantics in a MATLAB JIT Compiler

authors:
Nurudeen Lameed
Laurie J. Hendren


title: Practical Loop Transformations for Tensor Contraction Expressions on Multi-level Memory Hierarchies

authors:
Wenjing Ma
Sriram Krishnamoorthy
Gagan Agrawal


title: Faster Alias Set Analysis Using Summaries

authors:
Nomair A. Naeem
Ondrej Lhoták


title: Future-Proofing Collections: From Mutable to Persistent to Parallel


title: JPure: A Modular Purity System for Java


title: Tainted Flow Analysis on e-SSA-Form Programs

authors:
Andrei Rimsa
Marcelo d'Amorim
Fernando Magno Quintão Pereira


title: Actor-Based Parallel Dataflow Analysis

authors:
Jonathan Rodriguez
Ondrej Lhoták


title: Dynamic Elimination of Overflow Tests in a Trace Compiler

authors:
Rodrigo Sol
Christophe Guillon
Fernando Magno Quintão Pereira
Mariza Andrade da Silva Bigonha


title: Probabilistic Points-to Analysis for Java

authors:
Qiang Sun
Jianjun Zhao
Yuting Chen


title: Compiler Support for Value-Based Indirect Branch Prediction

authors:
Muhammad Umar Farooq
Lei Chen
Lizy Kurian John


title: A New Method for Program Inversion

authors:
Cong Hou
George Vulov
Daniel J. Quinlan
David R. Jefferson
Richard Fujimoto
Richard W. Vuduc


title: VMAD: An Advanced Dynamic Program Analysis and Instrumentation Framework

authors:
Alexandra Jimborean
Luis Mastrangelo
Vincent Loechner
Philippe Clauss


title: Improving Performance of OpenCL on CPUs

authors:
Ralf Karrenberg
Sebastian Hack


title: Static Detection of Unsafe Component Loadings

authors:
Taeho Kwon
Zhendong Su


title: Programming Paradigm Driven Heap Analysis

authors:
Mark Marron
Ondrej Lhoták
Anindya Banerjee


title: GC-Safe Interprocedural Unboxing

authors:
Leaf Petersen
Neal Glew


title: Parallel Replication-Based Points-To Analysis

authors:
Sandeep Putta
Rupesh Nasre


title: Analytical Bounds for Optimal Tile Size Selection

authors:
Jun Shirako
Kamal Sharma
Naznin Fauzia
Louis-Noël Pouchet
J. Ramanujam
P. Sadayappan
Vivek Sarkar


title: Sambamba: A Runtime System for Online Adaptive Parallelization

authors:
Kevin Streit
Clemens Hammacher
Andreas Zeller
Sebastian Hack


title: Automatic Restructuring of GPU Kernels for Exploiting Inter-thread Data Locality

authors:
Swapneela Unkule
Christopher Shaltz
Apan Qasem


title: Object Model Construction for Inheritance in C++ and Its Applications to Program Analysis

authors:
Jing Yang
Gogul Balakrishnan
Naoto Maeda
Franjo Ivancic
Aarti Gupta
Nishant Sinha
Sriram Sankaranarayanan
Naveen Sharma


title: Compiler Support for Fine-Grain Software-Only Checkpointing

authors:
Chuck (Chengyan) Zhao
J. Gregory Steffan
Cristiana Amza
Allan Kielstra


title: An Incremental Points-to Analysis with CFL-Reachability

authors:
Yi Lu
Lei Shang
Xinwei Xie
Jingling Xue


title: Optimal and Heuristic Global Code Motion for Minimal Spilling

authors:
Gergö Barany
Andreas Krall


title: On LR Parsing with Selective Delays

authors:
Eberhard Bertsch
Mark-Jan Nederhof
Sylvain Schmitz


title: PolyGLoT: A Polyhedral Loop Transformation Framework for a Graphical Dataflow Language

authors:
Somashekaracharya G. Bhaskaracharya
Uday Bondhugula


title: Simple and Efficient Construction of Static Single Assignment Form

authors:
Matthias Braun
Sebastian Buchwald
Sebastian Hack
Roland Leißa
Christoph Mallon
Andreas Zwinkau

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. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


title: On the Determination of Inlining Vectors for Program Optimization

authors:
Rosario Cammarota
Alexandru Nicolau
Alexander V. Veidenbaum
Arun Kejariwal
Debora Donato
Mukund Madhugiri


title: Efficient and Effective Handling of Exceptions in Java Points-to Analysis

authors:
George Kastrinis
Yannis Smaragdakis


title: Compiler-Guided Identification of Critical Sections in Parallel Code

authors:
Stefan Kempf
Ronald Veldema
Michael Philippsen


title: Optimal Register Allocation in Polynomial Time


title: Automatic Generation of Program Affinity Policies Using Machine Learning

authors:
Ryan W. Moore
Bruce R. Childers


title: Refactoring MATLAB

authors:
Soroush Radpour
Laurie J. Hendren
Max Schäfer


title: FESA: Fold- and Expand-Based Shape Analysis

authors:
Holger Siegel
Axel Simon


title: Architecture-Independent Dynamic Information Flow Tracking

authors:
Ryan Whelan
Tim Leek
David R. Kaeli


title: Taming Control Divergence in GPUs through Control Flow Linearization

authors:
Jayvant Anantpur
R. Govindarajan

abstract: Branch divergence is a very commonly occurring performance problem in GPGPU in which the execution of diverging branches is serialized to execute only one control flow path at a time. Existing hardware mechanism to reconverge threads using a stack causes duplicate execution of code for unstructured control flow graphs. Also the stack mechanism cannot effectively utilize the available parallelism among diverging branches. Further, the amount of nested divergence allowed is also limited by depth of the branch divergence stack. In this paper we propose a simple and elegant transformation to handle all of the above mentioned problems. The transformation converts an unstructured CFG to a structured CFG without duplicating user code. It incurs only a linear increase in the number of basic blocks and also the number of instructions. Our solution linearizes the CFG using a predicate variable. This mechanism reconverges the divergent threads as early as possible. It also reduces the depth of the reconvergence stack. The available parallelism in nested branches can be effectively extracted by scheduling the basic blocks to reduce the effect of stalls due to memory accesses. It can also increase execution efficiency of nested loops with different trip counts for different threads. We implemented the proposed transformation at PTX level using the Ocelot compiler infrastructure. We evaluated the technique using various benchmarks to show that it can be effective in handling the performance problem due to divergence in unstructured CFGs.


title: Liveness-Based Garbage Collection

authors:
Rahul Asati
Amitabha Sanyal
Amey Karkare
Alan Mycroft


title: Addressing JavaScript JIT Engines Performance Quirks: A Crowdsourced Adaptive Compiler

authors:
Rafael Auler
Edson Borin
Peli de Halleux
Michal Moskal
Nikolai Tillmann


title: The PAPAGENO Parallel-Parser Generator

authors:
Alessandro Barenghi
Stefano Crespi Reghizzi
Dino Mandrioli
Federica Panella
Matteo Pradella


title: deGoal a Tool to Embed Dynamic Code Generators into Applications

authors:
Henri-Pierre Charles
Damien Couroussé
Victor Lomüller
Fernando Akira Endo
Rémy Gauguey


title: Using the SSA-Form in a Code Generator


title: Improving the Performance of X10 Programs by Clock Removal

authors:
Paul Feautrier
Eric Violard
Alain Ketterlin


title: CBMC-GC: An ANSI C Compiler for Secure Two-Party Computations

authors:
Martin Franz
Andreas Holzer
Stefan Katzenbeisser
Christian Schallhart
Helmut Veith


title: String Analysis for Dynamic Field Access

authors:
Magnus Madsen
Esben Andreasen

abstract: In JavaScript, and scripting languages in general, dynamic field access is a commonly used feature. Unfortunately, current static analysis tools either completely ignore dynamic field access or use overly conservative approximations that lead to poor precision and scalability. We present new string domains to reason about dynamic field access in a static analysis tool. A key feature of the domains is that the equal, concatenate and join operations take $\mathcal{O}$ (1) time. Experimental evaluation on four common JavaScript libraries, including jQuery and Prototype, shows that traditional string domains are insufficient. For instance, the commonly used constant string domain can only ensure that at most 21% dynamic field accesses are without false positives. In contrast, our string domain $\mathcal{H}$ ensures no false positives for up to 90% of all dynamic field accesses. We demonstrate that a dataflow analysis equipped with the $\mathcal{H}$ domain gains significant precision resulting in an analysis speedup of more than 1.5x for 7 out of 10 benchmark programs.


title: A First Step towards a Compiler for Business Processes

authors:
Thomas M. Prinz
Norbert Spieß
Wolfram Amme


title: Recovery of Class Hierarchies and Composition Relationships from Machine Code

authors:
Venkatesh Srinivasan
Thomas W. Reps


title: A Flexible and Efficient ML Lexer Tool Based on Extended Regular Expression Submatching

authors:
Martin Sulzmann
Pippijn van Steenhoven


title: Inter-iteration Scalar Replacement Using Array SSA Form

authors:
Rishi Surendran
Rajkishore Barik
Jisheng Zhao
Vivek Sarkar


title: Parameterized Construction of Program Representations for Sparse Dataflow Analyses

authors:
André Luiz Camargos Tavares
Benoit Boissinot
Fernando Magno Quintão Pereira
Fabrice Rastello

abstract: Data-flow analyses usually associate information with control flow regions. Informally, if these regions are too small, like a point between two consecutive statements, we call the analysis dense. On the other hand, if these regions include many such points, then we call it sparse. This paper presents a systematic method to build program representations that support sparse analyses. To pave the way to this framework we clarify the bibliography about well-known intermediate program representations. We show that our approach, up to parameter choice, subsumes many of these representations, such as the SSA, SSI and e-SSA forms. In particular, our algorithms are faster, simpler and more frugal than the previous techniques used to construct SSI - Static Single Information - form programs. We produce intermediate representations isomorphic to Choi et al.’s Sparse Evaluation Graphs (SEG) for the family of data-flow problems that can be partitioned per variables. However, contrary to SEGs, we can handle - sparsely - problems that are not in this family. We have tested our ideas in the LLVM compiler, comparing different program representations in terms of size and construction time.


title: Exploitation of GPUs for the Parallelisation of Probably Parallel Legacy Code

authors:
Zheng Wang
Daniel Christopher Powell
Björn Franke
Michael F. P. O'Boyle


title: A Backend Extension Mechanism for PQL/Java with Free Run-Time Optimisation

authors:
Hilmar Ackermann
Christoph Reichenbach
Christian Müller
Yannis Smaragdakis


title: Faster, Practical GLL Parsing

authors:
Ali Afroozeh
Anastasia Izmaylova


title: Staged Points-to Analysis for Large Code Bases

authors:
Nicholas Allen
Bernhard Scholz
Padmanabhan Krishnan


title: A Synchronous-Based Code Generator for Explicit Hybrid Systems Languages

authors:
Timothy Bourke
Jean-Louis Colaço
Bruno Pagano
Cédric Pasteur
Marc Pouzet


title: Optgen: A Generator for Local Optimizations


title: Exact and Approximated Data-Reuse Optimizations for Tiling with Parametric Sizes

authors:
Alain Darte
Alexandre Isoard

abstract: Loop tiling is a loop transformation widely used to improve spatial and temporal data locality, to increase computation granularity, and to enable blocking algorithms, which are particularly useful when offloading kernels on computing units with smaller memories. When caches are not available or used, data transfers and local storage must be software-managed, and some useless remote communications can be avoided by exploiting data reuse between tiles. An important parameter of tiling is the sizes of the tiles, which impact the size of the required local memory. However, for most analyzes involving several tiles, which is the case for inter-tile data reuse, the tile sizes induce non-linear constraints, unless they are numerical constants. This complicates or prevents a parametric analysis with polyhedral optimization techniques.


title: Verifying Fast and Sparse SSA-Based Optimizations in Coq

authors:
Delphine Demange
David Pichardie
Léo Stefanesco


title: Towards a Scalable Framework for Context-Free Language Reachability

authors:
Nicholas Hollingum
Bernhard Scholz


title: Protocols by Default - Safe MPI Code Generation Based on Session Types

authors:
Nicholas Ng
José Gabriel de Figueiredo Coutinho
Nobuko Yoshida


title: A Graphical Model for Context-Free Grammar Parsing

authors:
Keshav Pingali
Gianfranco Bilardi


title: A Refactoring Library for Scala Compiler Extensions

authors:
Amanj Sherwany
Nosheen Zaza
Nathaniel Nystrom


title: Feature-Specific Profiling

authors:
Vincent St-Amour
Leif Andersen
Matthias Felleisen


title: Iguana: a practical data-dependent parsing framework

abstract: Data-dependent grammars extend context-free grammars with arbitrary computation, variable binding, and constraints. These features provide the user with the freedom and power to express syntactic constructs outside the realm of context-free grammars, e.g., indentation rules in Haskell and type definitions in C. Data-dependent grammars have been recently presented by Jim et al. as a grammar formalism that enables construction of parsers from a rich format specification. Although some features of data-dependent grammars are available in current parsing tools, e.g., semantic predicates in ANTLR, data-dependent grammars have not yet fully found their way into practice. In this paper we present Iguana, a data-dependent parsing framework, implemented on top of the GLL parsing algorithm. In addition to basic features of data-dependent grammars, Iguana also provides high-level syntactic constructs, e.g., for operator precedence and indentation rules, which are implemented as desugaring to data-dependent grammars. These high-level constructs enable a concise and declarative way to define the syntax of programming languages. Moreover, Iguana's extensible data-dependent grammar API allows the user to easily add new high-level constructs or modify existing ones. We have used Iguana to parse various real programming languages, such as OCaml, Haskell, Java, and C#. In this paper we describe the architecture and features of Iguana, and report on its current implementation status.


title: SYCO: a systematic testing tool for concurrent objects

authors:
Elvira Albert
Miguel Gómez-Zamalloa
Miguel Isabel

abstract: We present the concepts, usage and prototypical implementation of SYCO: a SYstematic testing tool for Concurrent Objects. The system receives as input a program, a selection of method to be tested, and a set of initial values for its parameters. SYCO offers a visual web interface to carry out the testing process and visualize the results of the different executions as well as the sequences of tasks scheduled as a sequence diagram. Its kernel includes state-of-the-art partial-order reduction techniques to avoid redundant computations during testing. Besides, SYCO incorporates an option to effectively catch deadlock errors. In particular, it uses advanced techniques which guide the execution towards potential deadlock paths and discard paths that are guaranteed to be deadlock free.


title: Mapping deviation: a technique to adapt or to guard loop transformation intuitions for legality

abstract: Parallel architectures are now omnipresent in mainstream electronic devices and exploiting them efficiently is a challenge for all developers. Hence, they need the support of languages, libraries and tools to assist them in the optimization or parallelization task. Compilers can provide a major help by automating this work. However they are very fragile black-boxes. A compiler may take a bad optimization decision because of imprecise heuristics or may turn off an optimization because of imprecise analyses, without providing much control or feedback to the end user. To address this issue, we introduce mapping deviation, a new compiler technique that aims at providing a useful feedback on the semantics of a given program restructuring. Starting from a transformation intuition a user or a compiler wants to apply, our algorithm studies its correctness and can suggest changes or conditions to make it possible rather than being limited to the classical go/no-go answer. This algorithm builds on state-of-the-art polyhedral representation of programs and provides a high flexibility. We present two example applications of this technique: improving semi-automatic optimization tools for programmers and automatically designing runtime tests to check the correctness of a transformation for compilers.


title: Verified construction of static single assignment form

authors:
Sebastian Buchwald
Denis Lohner
Sebastian Ullrich

abstract: Modern compilers use intermediate representations in static single assignment (SSA) form, which simplifies many optimizations. However, the high implementation complexity of efficient SSA construction algorithms poses a challenge to verified compilers. In this paper, we consider a variant of the recent SSA construction algorithm by Braun et al. that combines simplicity and efficiency, and is therefore a promising candidate to tackle this challenge. We prove the correctness of the algorithm using the theorem prover Isabelle/HOL. Furthermore, we prove that the algorithm constructs pruned SSA form and, in case of a reducible control flow graph, minimal SSA form. To the best of our knowledge, these are the first formal proofs regarding the quality of an SSA construction algorithm. Finally, we replace the SSA construction of the CompCertSSA project with code extracted by Isabelle's code generator to demonstrate the applicability to real world programs.


title: Restrictification of function arguments

authors:
Victor Hugo Sperle Campos
Péricles Rafael Oliveira Alves
Henrique Nazaré Santos
Fernando Magno Quintão Pereira

abstract: Pointer aliasing still hinders compiler optimizations, in spite of years of research on pointer disambiguation. Because the automatic disambiguation of pointers is a difficult endeavor, several programming languages offer programmers mechanisms to distinguish memory references, such as the “restrict” keyword in C. However, the use of such mechanisms is prone to human mistakes. In this paper we present a suite of automatic techniques that mitigate this problem. We have designed, implemented and tested three different ways to disambiguate pointers passed as arguments of functions. Our techniques combine static analyses to infer symbolic bounds of memory regions and code versioning. We generate a clone for each function whose arguments we can disambiguate and optimize it assuming the absence of aliasing among formal parameters. At runtime, we use the results of the symbolic interval tests to decide which version of a function we should call: the original one or the “restricted” clone, whenever we can prove that no aliasing can occur at runtime. An implementation of our restrictification methods in LLVM shows that we can vectorize up to 63% more operations than what could be accomplished using the -O3 optimization level of said compiler. When applying the optimization on OpenCV benchmarks, we have observed speedups as great as 40%.


title: Reducing memory buffering overhead in software thread-level speculation

authors:
Zhen Cao
Clark Verbrugge

abstract: Software-based, automatic parallelization through Thread-Level Speculation (TLS) has significant practical potential, but also high overhead costs. Traditional "lazy" buffering mechanisms enable strong isolation of speculative threads, but imply large memory overheads, while more recent "eager" mechanisms improve scalability, but are more sensitive to data dependencies and have higher rollback costs. We here describe an integrated system that incorporates the best of both designs, automatically selecting the best buffering mechanism. Our approach builds on well-optimized designs for both techniques, and we describe specific optimizations that improve both lazy and eager buffer management as well. We implement our design within MUTLS, a software-TLS system based on the LLVM compiler framework. Results show that we can get 75% geometric mean performance of OpenMP versions on 9 memory intensive benchmarks. Application of these optimizations is thus a useful part of the optimization stack needed for effective and practical software TLS.


title: Extended lattice-based memory allocation

authors:
Alain Darte
Alexandre Isoard
Tomofumi Yuki

abstract: This work extends lattice-based memory allocation, an earlier work on memory reuse through array contraction. Such an optimization is used for optimizing high-level programming languages where storage mapping may be abstracted away from programmers and to complement code transformations that introduce intermediate buffers. The main motivation for this extension is to improve the handling of more general forms of specifications we see today, e.g., with loop tiling, pipelining, and other forms of parallelism available in explicitly-parallel languages. Specifically, we handle the case when conflicting constraints (those that describe the array indices that cannot share the same location) are specified as a (non-convex) union of polyhedra. The choice of directions (or basis) of array reuse becomes important when dealing with non-convex specifications. We extend the two dual approaches in the original work to handle unions of polyhedra, and to select a suitable basis. Our final approach relies on a combination of the two, also revealing their links with, on one hand, the construction of multi-dimensional schedules for parallelism and tiling (but with a fundamental difference that we identify) and, on the other hand, the construction of universal reuse vectors (UOV), which was only used so far in a specific context, for schedule-independent mapping.


title: Mechanizing conventional SSA for a verified destruction with coalescing

authors:
Delphine Demange
Yon Fernández de Retana

abstract: Modern optimizing compilers rely on the Static Single Assignment (SSA) form to make optimizations fast and simpler to implement. From a semantic perspective, the SSA form is nowadays fairly well understood, as witnessed by recent advances in the field of formally verified compilers. The destruction of the SSA form, however, remains a difficult problem, even in a non-verified environment. In fact, the out-of-SSA transformation has been revisited, for correctness and performance issues, up until recently. Unsurprisingly, state-of-the-art compiler formalizations thus either completely ignore, only partially handle, or implement naively the SSA destruction. This paper reports on the implementation of such a destruction within a verified compiler. We formally define and prove the properties of the generation of Conventional SSA (CSSA) which make its destruction simple to implement and prove. Second, we implement and prove correct a coalescing destruction of CSSA, a la Boissinot et al., where variables can be coalesced according to a refined notion of interference. This formalization work extends the CompCertSSA compiler, whose correctness proof is mechanized in the Coq proof assistant. Our CSSA-based, coalescing destruction removes, on average, more than 99% of introduced copies, and leads to encouraging results concerning spilling during post-SSA register allocation.


title: Register allocation and promotion through combined instruction scheduling and loop unrolling

authors:
Lukasz Domagala
Duco van Amstel
Fabrice Rastello
P. Sadayappan

abstract: Register allocation is a much studied problem. A particularly important context for optimizing register allocation is within loops, since a significant fraction of the execution time of programs is often inside loop code. A variety of algorithms have been proposed in the past for register allocation, but the complexity of the problem has resulted in a decoupling of several important aspects, including loop unrolling, register promotion, and instruction reordering. In this paper, we develop an approach to register allocation and promotion in a unified optimization framework that simultaneously considers the impact of loop unrolling and instruction scheduling. This is done via a novel instruction tiling approach where instructions within a loop are represented along one dimension and innermost loop iterations along the other dimension. By exploiting the regularity along the loop dimension, and imposing essential dependence based constraints on intra-tile execution order, the problem of optimizing register pressure is cast in a constraint programming formalism. Experimental results are provided from thousands of innermost loops extracted from the SPEC benchmarks, demonstrating improvements over the current state-of-the-art.


title: Heap bounds protection with low fat pointers

authors:
Gregory J. Duck
Roland H. C. Yap

abstract: Heap buffer overflow (underflow) errors are a common source of security vulnerabilities. One prevention mechanism is to add object bounds meta information and to instrument the program with explicit bounds checks for all memory access. The so-called "fat pointers" approach is one method for maintaining and propagating the meta information where native machine pointers are replaced with "fat" objects that explicitly store object bounds. Another approach is "low fat pointers", which encodes meta information within a native pointer itself, eliminating space overheads and also code compatibility issues. This paper presents a new low-fat pointer encoding that is fully compatible with existing libraries (e.g. pre-compiled libraries unaware of the encoding) and standard hardware (e.g. x86_64). We show that our approach has very low memory overhead, and competitive with existing state-of-the-art bounds instrumentation solutions.


title: Kindergarten cop: dynamic nursery resizing for GHC

authors:
Henrique Ferreiro
Laura M. Castro
Vladimir Janjic
Kevin Hammond

abstract: Generational garbage collectors are among the most popular garbage collectors used in programming language runtime systems. Their performance is known to depend heavily on choosing the appropriate size of the area where new objects are allocated (the nursery). In imperative languages, it is usual to make the nursery as large as possible, within the limits imposed by the heap size. Functional languages, however, have quite different memory be- haviour. In this paper, we study the effect that the nursery size has on the performance of lazy functional programs, through the interplay between cache locality and the frequency of collections. We demonstrate that, in contrast with imperative programs, having large nurseries is not always the best solution. Based on these re- sults, we propose two novel algorithms for dynamic nursery resiz- ing that aim to achieve a compromise between good cache locality and the frequency of garbage collections. We present an implemen- tation of these algorithms in the state-of-the-art GHC compiler for the functional language Haskell, and evaluate them using an exten- sive benchmark suite. In the best case, we demonstrate a reduction in total execution times of up to 88.5%, or an 8.7 overall speedup, compared to using the production GHC garbage collector. On aver- age, our technique gives an improvement of 9.3% in overall perfor- mance across a standard suite of 63 benchmarks for the production GHC compiler.


title: Thread-level speculation with kernel support

authors:
Clemens Hammacher
Kevin Streit
Andreas Zeller
Sebastian Hack

abstract: Runtime systems for speculative parallelization can be substantially sped up by implementing them with kernel support. We describe a novel implementation of a thread-level speculation (TLS) system using virtual memory to isolate speculative state, implemented in a Linux kernel module. This design choice not only maximizes performance, but also allows to guarantee soundness in the presence of system calls, such as I/O. Its ability to maintain speedups even on programs with frequent mis-speculation, significantly extends its usability, for instance in speculative parallelization. We demonstrate the advantage of kernel-based TLS on a number of programs from the Cilk suite, where this approach is superior to the state of the art in each single case (7.28x on average). All systems described in this paper are made available as open source.


title: Multiversioned decoupled access-execute: the key to energy-efficient compilation of general-purpose programs

authors:
Konstantinos Koukos
Per Ekemark
Georgios Zacharopoulos
Vasileios Spiliopoulos
Stefanos Kaxiras
Alexandra Jimborean

abstract: Computer architecture design faces an era of great challenges in an attempt to simultaneously improve performance and energy efficiency. Previous hardware techniques for energy management become severely limited, and thus, compilers play an essential role in matching the software to the more restricted hardware capabilities. One promising approach is software decoupled access-execute (DAE), in which the compiler transforms the code into coarse-grain phases that are well-matched to the Dynamic Voltage and Frequency Scaling (DVFS) capabilities of the hardware. While this method is proved efficient for statically analyzable codes, general-purpose applications pose significant challenges due to pointer aliasing, complex control flow and unknown runtime events. We propose a universal compile-time method to decouple general-purpose applications, using simple but efficient heuristics. Our solutions overcome the challenges of complex code and show that automatic decoupled execution significantly reduces the energy expenditure of irregular or memory-bound applications and even yields slight performance boosts. Overall, our technique achieves over 20% on average energy-delay-product (EDP) improvements (energy over 15% and performance over 5%) across 14 benchmarks from SPEC CPU 2006 and Parboil benchmark suites, with peak EDP improvements surpassing 70%.


title: Safe and flexible adaptation via alternate data structure representations

authors:
Amlan Kusum
Iulian Neamtiu
Rajiv Gupta

abstract: The choice of data structures is crucial for achieving high performance. For applications that are long-running and/or operate on large data sets, the best choice for main data structures can change multiple times over the course of a single execution. For example, in a graph-processing application where the graph evolves over time, the best data structure for representing the graph may change as the program executes. Similarly, in a database or a key-value store application, with changes in relative frequencies of different types of queries over time, the most efficient data structure changes as well. We introduce an approach that allows applications to adapt to current conditions (input characteristics, operations on data, state) by switching their data structures on-the-fly with little overhead and without the developer worrying about safety or specifying adaptation points (this is handled by our compiler infrastructure). We use our approach on different classes of problems that are compute- and memory-intensive: graph algorithms, database indexing, and two real-world applications, the Memcached object cache and the Space Tyrant online game server. Our results show that off-the-shelf applications can be transformed into adaptive applications with modest programmer effort; that the adaptive versions outperform the original, fixed-representation versions; and that adaptation can be performed on-the-fly safely and with very little runtime overhead.


title: Register allocation and instruction scheduling in Unison

authors:
Roberto Castañeda Lozano
Mats Carlsson
Gabriel Hjort Blindell
Christian Schulte

abstract: This paper describes Unison, a simple, flexible, and potentially optimal software tool that performs register allocation and instruction scheduling in integration using combinatorial optimization. The tool can be used as an alternative or as a complement to traditional approaches, which are fast but complex and suboptimal. Unison is most suitable whenever high-quality code is required and longer compilation times can be tolerated (such as in embedded systems or library releases), or the targeted processors are so irregular that traditional compilers fail to generate satisfactory code.


title: Automatic data layout generation and kernel mapping for CPU+GPU architectures

authors:
Deepak Majeti
Kuldeep S. Meel
Rajkishore Barik
Vivek Sarkar

abstract: The ubiquity of hybrid CPU+GPU architectures has led to renewed interest in automatic data layout generation owing to the fact that data layouts have a large impact on performance, and that different data layouts yield the best performance on CPUs vs. GPUs. Unfortunately, current programming models still fail to provide an effective solution to the problem of automatic data layout generation for CPU+GPU processors. Specifically, the interaction among wholeprogram data layout optimizations, data movement optimizations, and mapping of kernels across heterogeneous cores pose a major challenge to current programming systems. In this paper, we introduce a novel two-level hierarchical formulation of the data layout and kernel mapping problem for modern heterogeneous architectures. The bottom level formulation deals with the data layout problem for a parallel code region on a given processor, which is NPHard, and we provide a greedy algorithm that uses an affinity graph to obtain approximate solutions. The top level formulation targets data layouts and kernel mapping for the entire program for which we provide a polynomial-time solution using a graph-based shortest path algorithm that uses the data layouts for the code regions (sections) for a given processor computed in the bottom level formulation. We implement this data layout transformation in the new Heterogeneous Habanero-C (H2C) parallel programming framework and propose performance models to characterize the data layout impact on both the CPU and GPU. Our data layout framework shows significant performance improvements of up to 2.9x (geometric mean 1.5x) on a multicore CPU+GPU compared to the manually specified layouts for a set of parallel programs running on a heterogeneous platform consisting of an Intel Xeon CPU and an NVIDIA GPU. Further, our framework also shows performance improvements of up to 2.7x (geometric mean 1.6x) on just the multicore CPU, demonstrating the applicability of our approach to both heterogeneous and homogeneous hardware platforms.


title: Input space splitting for OpenCL

authors:
Simon Moll
Johannes Doerfert
Sebastian Hack

abstract: The performance of OpenCL programs suffers from memory and control flow divergence. Therefore, OpenCL compilers employ static analyses to identify non-divergent control flow and memory accesses in order to produce faster code. However, divergence is often input-dependent, hence can be observed for some, but not all inputs. In these cases, vectorizing compilers have to generate slow code because divergence can occur at run time. In this paper, we use a polyhedral abstraction to partition the input space of an OpenCL kernel. For each partition, divergence analysis produces more precise results i.e., it can classify more code parts as non-divergent. Consequently, specializing the kernel for the input space partitions allows for generating better SIMD code because of less divergence. We implemented our technique in an OpenCL driver for the AVX instruction set and evaluate it on a range of OpenCL benchmarks. We observe speed ups of up to 9x for irregular kernels over a state-of-the-art vectorizing OpenCL driver.


title: Performance implications of transient loop-carried data dependences in automatically parallelized loops

authors:
Niall Murphy
Timothy M. Jones
Robert Mullins
Simone Campanoni

abstract: Recent approaches to automatic parallelization have taken advantage of the low-latency on-chip interconnect provided in modern multicore processors, demonstrating significant speedups, even for complex workloads. Although these techniques can already extract significant thread-level parallelism from application loops, we are interested in quantifying and exploiting any additional performance that remains on the table. This paper confirms the existence of significant extra thread-level parallelism within loops parallelized by the HELIX compiler. However, improving static data dependence analysis is unable to reach the additional performance offered because the existing loop-carried dependences are true only on a small subset of loop iterations. We therefore develop three approaches to take advantage of the transient nature of these data dependences through speculation, via transactional memory support. Results show that coupling the state-of-the-art data dependence analysis with fine-grained speculation achieves most of the speedups and may help close the gap towards the limit of HELIX-style thread-level parallelism.


title: Static deadlock detection for concurrent go by global session graph synthesis

authors:
Nicholas Ng
Nobuko Yoshida

abstract: Go is a programming language developed at Google, with channel-based concurrent features based on CSP. Go can detect global communication deadlocks at runtime when all threads of execution are blocked, but deadlocks in other paths of execution could be undetected. We present a new static analyser for concurrent Go code to find potential communication errors such as communication mismatch and deadlocks at compile time. Our tool extracts the communication operations as session types, which are then converted into Communicating Finite State Machines (CFSMs). Finally, we apply a recent theoretical result on choreography synthesis to generate a global graph representing the overall communication pattern of a concurrent program. If the synthesis is successful, then the program is free from communication errors. We have implemented the technique in a tool, and applied it to analyse common Go concurrency patterns and an open source application with over 700 lines of code.


title: GreenThumb: superoptimizer construction framework

authors:
Phitchaya Mangpo Phothilimthana
Aditya Thakur
Rastislav Bodík
Dinakar Dhurjati

abstract: Developing an optimizing compiler backend remains a laborious process, especially for nontraditional ISAs that have been appearing recently. Superoptimization sidesteps the need for many code transformations by searching for the most optimal instruction sequence semantically equivalent to the original code fragment. Even though superoptimization discovers the best machine-specific code optimizations, it has yet to become widely-used. We propose GreenThumb, an extensible framework that reduces the cost of constructing superoptimizers and provides a fast search algorithm that can be reused for any ISA, exploiting the unique strengths of enumerative, stochastic, and symbolic (SAT-solver-based) search algorithms. To extend GreenThumb to a new ISA, it is only necessary to implement an emulator for the ISA and provide some ISA-specific search utility functions.


title: Reachability and error diagnosis in LR(1) parsers

abstract: Given an LR(1) automaton, what are the states in which an error can be detected? For each such "error state", what is a minimal input sentence that causes an error in this state? We propose an algorithm that answers these questions. This allows building a collection of pairs of an erroneous input sentence and a (handwritten) diagnostic message, ensuring that this collection covers every error state, and maintaining this property as the grammar evolves. We report on an application of this technique to the CompCert ISO C99 parser, and discuss its strengths and limitations.


title: On fusing recursive traversals of K-d trees

authors:
Samyam Rajbhandari
Jinsung Kim
Sriram Krishnamoorthy
Louis-Noël Pouchet
Fabrice Rastello
Robert J. Harrison
P. Sadayappan

abstract: Loop fusion is a key program transformation for data locality optimization that is implemented in production compilers. But optimizing compilers for imperative languages currently cannot ex- ploit fusion opportunities across a set of recursive tree traversal computations with producer-consumer relationships. In this paper, we develop a compile-time approach to dependence characterization and program transformation to enable fusion across recursively specified traversals over k-d trees. We present the FuseT source-to- source code transformation framework to automatically generate fused composite recursive operators from an input program containing a sequence of primitive recursive operators. We use our framework to implement fused operators for MADNESS, Multi-resolution Adaptive Numerical Environment for Scientific Simulation. We show that locality optimization through fusion can offer significant performance improvement.


title: Sparse representation of implicit flows with applications to side-channel detection

authors:
Bruno Rodrigues
Fernando Magno Quintão Pereira
Diego F. Aranha

abstract: Information flow analyses traditionally use the Program Dependence Graph (PDG) as a supporting data-structure. This graph relies on Ferrante et al.'s notion of control dependences to represent implicit flows of information. A limitation of this approach is that it may create O(|I| x |E|) implicit flow edges in the PDG, where I are the instructions in a program, and E are the edges in its control flow graph. This paper shows that it is possible to compute information flow analyses using a different notion of implicit dependence, which yields a number of edges linear on the number of definitions plus uses of variables. Our algorithm computes these dependences in a single traversal of the program's dominance tree. This efficiency is possible due to a key property of programs in Static Single Assignment form: the definition of a variable dominates all its uses. Our algorithm correctly implements Hunt and Sands system of security types. Contrary to their original formulation, which required O(IxI) space and time for structured programs, we require only O(I). We have used our ideas to build FlowTracker, a tool that uncovers side-channel vulnerabilities in cryptographic algorithms. FlowTracker handles programs with over one-million assembly instructions in less than 200 seconds, and creates 24% less implicit flow edges than Ferrante et al.'s technique. FlowTracker has detected an issue in a constant-time implementation of Elliptic Curve Cryptography; it has found several time-variant constructions in OpenSSL, one issue in TrueCrypt and it has validated the isochronous behavior of the NaCl library.


title: Improved MHP Analysis

authors:
Aravind Sankar
Soham Chakraborty
V. Krishna Nandivada

abstract: May-Happen-in-Parallel (MHP) analysis is becoming the backbone of many of the parallel analyses and optimizations. In this paper, we present new approaches to do MHP analysis for X10-like languages that support async-finish-atomic parallelism. We present a fast incremental MHP algorithm to derive all the statements that may run in parallel with a given statement. We also extend the MHP algorithm of Agarwal et al. (answers if two given X10 statements may run in parallel, and under what condition) to improve the computational complexity, without compromising on the precision.


title: On fast large-scale program analysis in Datalog

authors:
Bernhard Scholz
Herbert Jordan
Pavle Subotic
Till Westmann

abstract: Designing and crafting a static program analysis is challenging due to the complexity of the task at hand. Among the challenges are modelling the semantics of the input language, finding suitable abstractions for the analysis, and handwriting efficient code for the analysis in a traditional imperative language such as C++. Hence, the development of static program analysis tools is costly in terms of development time and resources for real world languages. To overcome, or at least alleviate the costs of developing a static program analysis, Datalog has been proposed as a domain specific language (DSL). With Datalog, a designer expresses a static program analysis in the form of a logical specification. While a domain specific language approach aids in the ease of development of program analyses, it is commonly accepted that such an approach has worse runtime performance than handcrafted static analysis tools. In this work, we introduce a new program synthesis methodology for Datalog specifications to produce highly efficient monolithic C++ analyzers. The synthesis technique requires the re-interpretation of the semi-naive evaluation as a scaffolding for translation using partial evaluation. To achieve high-performance, we employ staged-compilation techniques and specialize the underlying relational data structures for a given Datalog specification. Experimentation on benchmarks for large-scale program analysis validates the superior performance of our approach over available Datalog tools and demonstrates our competitiveness with state-of-the-art handcrafted tools.


title: Automatic fault location for data structures

authors:
Vineet Singh
Rajiv Gupta
Iulian Neamtiu

abstract: Specification-based data structure verification is a powerful debugging technique. In this work we combine specification-based data structure verification with automatic detection of faulty program statements that corrupt data structures. The user specifies the consistency constraints for dynamic data structures as relationships among the nodes of a memory graph. Our system detects constraint violations to identify corrupted data structures during program execution and then automatically locates faulty code responsible for data structure corruption. Our approach offers two main advantages: (1) a highly precise automatic fault location method, and (2) a simple specification language. We employ incremental constraint checking for time efficient constraint matching and fault location. On average, while Tarantula statistical debugging technique narrows the fault to 10 statements, our technique narrows it to ≈ 4 statements..


title: SVF: interprocedural static value-flow analysis in LLVM

authors:
Yulei Sui
Jingling Xue

abstract: This paper presents SVF, a tool that enables scalable and precise interprocedural Static Value-Flow analysis for C programs by leveraging recent advances in sparse analysis. SVF, which is fully implemented in LLVM, allows value-flow construction and pointer analysis to be performed in an iterative manner, thereby providing increasingly improved precision for both. SVF accepts points- to information generated by any pointer analysis (e.g., Andersen’s analysis) and constructs an interprocedural memory SSA form, in which the def-use chains of both top-level and address-taken variables are captured. Such value-flows can be subsequently exploited to support various forms of program analysis or enable more precise pointer analysis (e.g., flow-sensitive analysis) to be performed sparsely. By dividing a pointer analysis into three loosely coupled components: Graph, Rules and Solver, SVF provides an extensible interface for users to write their own solutions easily. SVF is publicly available at http://unsw-corg.github.io/SVF.


title: Static detection of energy defect patterns in Android applications

authors:
Haowei Wu
Shengqian Yang
Atanas Rountev

abstract: For static analysis researchers, Android software presents a wide variety of interesting challenges. The target of our work is static detection of energy-drain defects in Android applications. The management of energy-intensive resources (e.g., GPS) creates various opportunities for software defects. Our goal is to detect statically “missing deactivation” energy-drain defects in the user interface of the application. First, we define precisely two patterns of run-time energy-drain behaviors, based on modeling of Android GUI control-flow paths and energy-related listener leaks along such paths. Next, we define a static detection algorithm targeting these patterns. The analysis considers valid interprocedural control-flow paths in a callback method and its transitive callees, in order to detect operations that add or remove listeners. Sequences of callbacks are then analyzed for possible listener leaks. Our evaluation considers the detection of GUI-related energy-drain defects reported in prior work, as well as new defects not discovered by prior approaches. In summary, the detection is very effective and precise, suggesting that the proposed analysis is suitable for practical use in static checking tools for Android.


title: Relaxed dependence tracking for parallel runtime support

authors:
Minjia Zhang
Swarnendu Biswas
Michael D. Bond

abstract: It is notoriously difficult to achieve both correctness and scalability for many shared-memory parallel programs. To improve correctness and scalability, researchers have developed various kinds of parallel runtime support such as multithreaded record & replay and software transactional memory. Existing forms of runtime support slow programs significantly in order to track an execution's cross-thread dependences accurately. This paper investigates the potential for runtime support to hide latency introduced by dependence tracking, by tracking dependences in a relaxed way---meaning that not all dependences are tracked accurately. The key challenge in relaxing dependence tracking is preserving both the program's semantics and the runtime support's guarantees. We present an approach called relaxed dependence tracking (RT) and demonstrate its potential by building two types of RT-based runtime support. Our evaluation shows that RT hides much of the latency incurred by dependence tracking, although RT-based runtime support incurs costs and complexity in order to handle relaxed dependence information. By demonstrating how to relax dependence tracking to hide latency while preserving correctness, this work shows the potential for addressing a key cost of dependence tracking, thus advancing knowledge in the design of parallel runtime support.


title: Dynamic symbolic execution for polymorphism

authors:
Lian Li
Yi Lu
Jingling Xue


title: Optimization space pruning without regrets

authors:
Ulysse Beaugnon
Antoine Pouille
Marc Pouzet
Jacques A. Pienaar
Albert Cohen


title: Lightweight data race detection for production runs

authors:
Swarnendu Biswas
Man Cao
Minjia Zhang
Michael D. Bond
Benjamin P. Wood


title: Granullar: gradual nullable types for Java

authors:
Dan Brotherston
Werner Dietl
Ondrej Lhoták


title: rev.ng: a unified binary analysis framework to recover CFGs and function boundaries

authors:
Alessandro Di Federico
Mathias Payer
Giovanni Agosta


title: Data structure-aware heap partitioning

authors:
Nouraldin Jaber
Milind Kulkarni


title: Partially redundant fence elimination for x86, ARM, and power processors

authors:
Robin Morisset
Francesco Zappa Nardelli


title: Let it recover: multiparty protocol-induced recovery

authors:
Rumyana Neykova
Nobuko Yoshida


title: Static optimization in PHP 7

authors:
Nikita Popov
Biagio Cosenza
Ben H. H. Juurlink
Dmitry Stogov


title: Optimized two-level parallelization for GPU accelerators using the polyhedral model

authors:
Jun Shirako
Akihiro Hayashi
Vivek Sarkar


title: Compile-time function memoization

authors:
Arjun Suresh
Erven Rohou
André Seznec


title: From functional programs to pipelined dataflow circuits

authors:
Richard Townsend
Martha A. Kim
Stephen A. Edwards


title: One compiler: deoptimization to optimized code

authors:
Christian Wimmer
Vojin Jovanovic
Erik Eckstein
Thomas Würthinger