Compiler constructions : 19th international conference, CC 2010, held as part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010, Paphos, Cyprus, March 20-28, 2010 : proceedings

ETAPS 2010 was the 13th instance of the European Joint Conferences on T- oryand Practiceof Software. ETAPS is anannual federatedconference that was establishedin1998bycombininganumberofexistingandnewconferences. This yearitcomprisedtheusual?vesisterconferences(CC, ESOP, FASE, FOSSACS, TACAS), 19 satellite workshops (ACCAT, ARSPA-WITS, Bytecode, CMCS, COCV, DCC, DICE, FBTC, FESCA, FOSS-AMA, GaLoP, GT-VMT, LDTA, MBT, PLACES, QAPL, SafeCert, WGT, and WRLA) and seven invited l- tures (excluding those that were speci?c to the satellite events). The ?ve main conferences this year received 497 submissions (including 31 tool demonstration papers), 130 of which were accepted (10 tool demos), giving an overall acc- tance rate of 26%, with most of the conferences at around 24%. Congratulations thereforetoalltheauthorswhomadeittothe?nalprogramme!Ihopethatmost of the other authors will still have found a way of participating in this exciting event, and that you will all continue submitting to ETAPS and contributing to make of it the best conference on software science and engineering. The events that comprise ETAPS address various aspects of the system - velopment process, including speci?cation, design, implementation, analysis and improvement. The languages, methodologies and tools which support these - tivities are all well within its scope. Di?erent blends of theory and practice are represented, withaninclinationtowardtheorywithapracticalmotivationonthe one hand and soundly based practice on the other. Many of the issues involved in software design apply to systems in general, including hardware systems, and the emphasis on software is not intended to be exclusive. ETAPS is a confederation in which each event retains its own identity, with a separate Programme Committee and proceedings. Title Page Foreword Preface Organization Table of Contents Invited Talk Programming Clouds Introduction Orleans Design Philosophy Centrality of Failure Orleans Programming Model Orleans Data Model Conclusion References Optimization Techniques Mining Opportunities for Code Improvement in a Just-In-Time Compiler Introduction Motivating Case Study The Mining Tool Preparation of Data for Mining Operation of the Mining Algorithm Support Thresholds for Mining Opportunities Discovered Experimental Data on the Usage of the Mining Tool Profiling and Storage Requirements Time Needed to Mine Sequences Reported by Mining Related Work Conclusion References Unrestricted Code Motion: A Program Representation and Transformation Algorithms Based on Future Values Introduction The Concept of Future Values Code Motion in Acyclic Code Future Predicated Form Elimination of -Nodes Merging of Instructions Instruction-Level Recursion Code Motion in Cyclic Code and Recursive Future Predicated Form $\phi$-Nodes in Loop Header Conversion of Loops into Instruction-Level Recursion Code Motion Involving Memory Dependencies and Function Calls Optimizations Using RFPF Algorithms for Converting RFPF Back to CFG Related Work Conclusion References Optimizing {\sc Matlab} through Just-In-Time Specialization Introduction Optimization Challenges Design Overview Just-In-Time Specialization Function Versioning Additional Optimizations Type and Shape Inference System Abstract Domain Merge Operator Inference Rules Inference Process Evaluation Baseline Performance Type Inference Efficiency JIT Specialization Related Work Conclusions and Future Work References RATA: Rapid Atomic Type Analysis by Abstract Interpretation – Application to {\tt JavaScript} Optimization Introduction The {\tt JavaScript}= Language Background IEEE754 Standard Abstract Interpretation Numerical Abstract Domains Extended Intervals Kinds K-Intervals Rapid Atomic Type Analysis Numerical Analysis Variation Analysis Atomic Types Experiments Related Work Conclusions References Program Transformations JReq: Database Queries in Imperative Languages Introduction Background JReq Query Syntax General Approach and Syntax Examples Translating JQS Using JReq Preprocessing Transformation of Loops Query Identification and Generation Implementation Expressiveness and Limitations Evaluation TPC-W TPC-H Conclusions References Verifying Local Transformations on Relaxed Memory Models Introduction Related Work Semantic Foundation A Simple Imperative Language for Shared Memory Denotational Semantics Verifying Local Program Transformations Invisible Rewrite Rules Application Conclusion and Future Work References Program Analysis Practical Extensions to the IFDS Algorithm Introduction Background: The Original IFDS Algorithm Running Example: Type Analysis Demand Construction of the Supergraph Return Flow Functions Static Single Assignment (SSA) Form Example of Precision Loss Exploiting Structure in the Set $D$ Empirical Evaluation Related Work Conclusions References Using Ownership to Reason about Inherent Parallelism in Object-Oriented Programs Introduction Background Introduction to Ownership Types Ownership Syntax Side-Effects Separating Ownership from Encapsulation Ownerships and Data Dependencies The Runtime Representation Context Testing Static Test Minimization Task Parallelism Loop Parallelism Loop Parallelism Pipelining Data Parallel for Loops Proof of Correctness Worked Example Related Work Conclusions and Future Work References Register Allocation Punctual Coalescing Introduction Background An Efficient Punctual Coalescing Algorithm ILP Formulation Example Experimental Results Limitations of Punctual Coalescing Conclusion References Strategies for Predicate-Aware Register Allocation Introduction Predication Overview Background Chaitin-Style Register Allocation Itanium® 2 Processor Architecture Register Allocation for Predicated Code Impact of Predicated Code Predicate Partition Graph (PPG) and Query System (PQS) A Family of Predicate-Aware Register Allocators Results Related Work Conclusions References Preference-Guided Register Assignment Introduction Contributions SSA-Based Register Allocation Register Assignment Register Constraints Implementing Parallel Moves Coalescing with Register Preferences Register Preferences Preference Analysis Affinity Chunks Optimistic Move Insertion Block Coloring Order Experimental Evaluation Compile Time Code Quality Related Work Conclusions References Validating Register Allocation and Spilling Introduction A Bird's Eye View of Register Allocation and Spilling Source Language Target Language The Effect of Register Allocation on the Code The Validation Algorithm Structural Checks Dataflow Analysis The Validation Algorithm Soundness Proof Dynamic Semantics Equation Satisfaction Forward Simulation Implementation and Experimental Results Related Work Conclusions and Future Work References High-Performance Systems Automatic C-to-CUDA Code Generation for Affine Programs Introduction Background GPU Architecture and the CUDA Programming Model GPU Computing Architecture CUDA Programming Model GPU Execution Model Design of C-to-CUDA Generator Multi-level Parallel Tiled Code Generation Data Movement between Off-Chip and On-Chip Memories Syntactic Post-processing Experimental Results Coulombic Potential (cp) N-Body Simulation (nbody) MRI Kernels Stencil Computation Kernels Gauss Seidel Successive over Relaxation Related Work Conclusions References Is Reuse Distance Applicable to Data Locality Analysis on Chip Multiprocessors? Introduction Concept and Properties of Concurrent Reuse Distance Review of Standalone Reuse Distance and Its Properties Concurrent Reuse Distance Concurrent Reuse Distance for Multithreading Programs Independence to Architecture and Inputs Probabilistic Model for Approximating Concurrent Reuse Distance Evaluation Synthetic Traces Traces from Real Programs Discussions Related Work Conclusions References The Polyhedral Model Is More Widely Applicable Than You Think Introduction Polyhedral Representation of Programs Static Control Parts Relaxing the Constraints Revisiting the Polyhedral Framework Program Analysis Program Transformation Code Generation Reducing Control Overhead Computing the Value of Predicates Predicate Placement Experimental Results Related Work Conclusion References The Hot Path SSA Form: Extending the Static Single Assignment Form for Speculative Optimizations Introduction Background The Static Single Assignment Form Acyclic Path Profiling A Peek at the Hot Path SSA Form Thermal Properties of a Program Thermal States of Program Entities The Structure of Profiled Acyclic Paths The Hot Path SSA (HPSSA) Form Constructing the HPSSA Form Thermal Frontiers: Placing -functions Allocating $\tau$-function Arguments Speculative Sparse Conditional Constant Propagation Implementation and Experiments Related Work Conclusions References Author Index This book constitutes the proceedings of the 24th International Conference on Compiler Construction, CC 2015, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, in London, UK, in April 2015.The 11 papers presented in this volume were carefully reviewed and selected from 34 submissions. Constitutes the refereed proceedings of the 19th International Conference on Compiler Construction, CC 2010, held in Paphos, Cyprus, in March 2010, as part of ETAPS 2010, the Joint European Conferences on Theory and Practice of Software.