title: Nsight Python: A Python-First Profiling Toolkit for Seamless GPU Kernel Analysis (Tool)

authors:
Bastian Hagedorn
Alexander Collins
Tony Mongkolsmai
Vinod Grover

abstract:
The proliferation of Python DSLs for developing kernels has democratized GPU programming. While kernel development is now Python-native, performance analysis and optimization still rely on external tools and fragmented workflows.

We introduce Nsight Python, a Python profiling toolkit that bridges this gap by bringing performance analysis for GPU kernels into the Python ecosystem. Nsight Python is framework-agnostic and works seamlessly with any Python framework through simple decorators and context managers that mark code regions for analysis. The tool automatically handles performance measurement, data collection, and result aggregation across multiple configurations.

Key innovations include: (1) Python-native interface enabling direct GPU kernel analysis within existing Python workflows, (2) configuration-driven execution model that correlates measured metrics with input parameters, (3) access to thousands of core metrics and enabling custom derived and relative metric computations through parameter correlation, (4) built-in thermal management to prevent GPU throttling during batch analysis, and (5) structured customizable visualization with automatic plot generation based on parameter roles.

With Nsight Python, the entire kernel development process—from implementation to iterative optimization and analysis—is now truly Python-native, providing detailed insights without requiring external profilers or disrupting workflows.


venue: cc

title: It's about Time: Temporal Abstractions for Asynchronous GPU Tensor Computations

authors:
Bastian Hagedorn
Vinod Grover

abstract:
The rise of asynchronous execution and specialized concurrent thread groups has reshaped GPU programming, but it also introduces complex timing and coordination challenges. Developers must carefully manage data readiness, concurrency, and hardware-specific tensor units that current low-level primitives make error-prone and hardware-dependent.

We present Async Graphene, a set of high-level abstractions for asynchronous and concurrent GPU programming. It builds on three pillars: (1) Async Tensor Types, which encode temporal relationships in the type system to prevent synchronization errors; (2) Concurrency Primitives, which structure complex control flow through specialization and pipelining; and (3) Tensor-Unit Orchestration, which simplifies low-level tensor hardware management.

On critical workloads such as GEMM and FlashAttention, Async Graphene delivers performance competitive with hand-optimized frameworks while significantly reducing development complexity. By making temporal behavior explicit, it allows compilers to address asynchrony and concurrency challenges without obscuring performance-critical details.


title: Optimizing Sparse Tensor Compilation for Sparse Output

authors:
Shideh Hashemian
Michael F. P. O'Boyle
Amir Shaikhha

abstract: Sparse tensor algebra plays an important role in many scientific and engineering applications, yet existing sparse libraries and compilers face challenges when the output tensor is sparse. Array-based storage formats, such as CSR, require costly memory reallocations and rely on intermediate tensors (workspaces) to handle sparse scattering into the output, which limits performance and scalability. We introduce a new approach that employs our proposed flexible map-based storage format to directly support sparse scattering into the output without requiring extra workspaces. Our system then applies code and storage-specific optimizations to maximize efficiency. Experimental results across a range of kernels and datasets demonstrate an average speedup of 8.06× over a state-of-the-art compiler and 5.28× over a sparse tensor library.


title: SSMR: Statically Detecting Speculation Safe Memory Regions to Mitigate Transient Execution Attacks

authors:
Ange-Thierry Ishimwe
Sam McDiarmid-Sterling
Zack McKevitt
Tamara Silbergleit Lehman

abstract: Transient execution attacks exploit speculative execution to leak confidential data through unauthorized transient memory accesses. We make the observation that transient attacks can be identified by one unusual memory access, the transient sensitive data access. To protect systems from such attacks while minimizing performance overhead, we propose leveraging compile-time information to identify memory operations that cannot extract sensitive data and can therefore be deemed safe. Safe memory operations are allowed to execute transiently, causing no extra performance cost. Unsafe memory operations delay accessing the memory system until they are no longer in a speculative state, preventing unauthorized transient accesses to sensitive data. To communicate this information to the microarchitecture, we introduce the set safe memory region (ssmr) instruction. Inserted automatically by the compiler, it establishes the memory regions that may be accessed transiently by a sequence of instructions. This defense incurs only a 7% performance overhead compared to the insecure baseline and mitigates at least two variants of transient execution attacks.


title: RIFS: Run-Time Invariant Function Specialization

authors:
Saba Jamilan
Snehasish Kumar
Heiner Litz

abstract: Compilers apply optimizations such as function specialization and constant propagation to eliminate redundant work at compile time. However, because compilers must prove that values are constant, many profitable optimization opportunities remain unrealized. In this paper, we propose run-time invariant function specialization (RIFS), a profile-guided compiler technique that specializes functions based on runtime invariant call-site-specific argument values. RIFS introduces a novel value-profiling LLVM pass to identify runtime invariant arguments, even though they cannot be proven constant statically. A subsequent LLVM transformation pass generates specialized function variants tailored to these value profiles. To efficiently select among potentially thousands of specialization candidates, we develop a predictive cost model that estimates the performance benefit of each candidate prior to code generation. We integrate our passes seamlessly into the existing PGO-enabled LLVM toolchain. We evaluate RIFS across 11 real-world applications, demonstrating substantial improvements over state-of-the-art optimization techniques. RIFS achieves an average speedup of 6.3% and an instruction reduction of 2.5% over the LLVM -O3+PGO baseline.


title: Inside VOLT: Designing an Open-Source GPU Compiler (Tool)

authors:
Shinnung Jeong
Chihyo Ahn
Huanzhi Pu
Jisheng Zhao
Hyesoon Kim
Blaise Tine

abstract:
Recent efforts in open-source GPU research are opening new avenues in a domain that has long been tightly coupled with a few commercial vendors. Emerging open GPU architectures define SIMT functionality through their own ISAs, but executing existing GPU programs and optimizing performance on these ISAs relies on a compiler framework that is technically complex and often undercounted in open-hardware development costs.

To address this challenge, the Vortex-Optimized Lightweight Toolchain (VOLT) has been proposed. This paper presents its design principles, overall structure, and the key compiler transformations required to support SIMT execution on Vortex. VOLT enables SIMT code generation and optimization across multiple levels of abstraction through a hierarchical design that accommodates diverse front-end languages and open GPU hardware. To ensure extensibility as GPU architectures evolve, VOLT centralizes fundamental SIMT-related analyses and optimizations in the middle-end, allowing them to be reused across front-ends and easily adapted to emerging open-GPU variants. Through two case studies on ISA extensions and host-runtime API, this paper also demonstrates how VOLT can support extensions.


title: Compact Representation and Interleaved Solving for Scalable Constraint-Based Points-to Analysis

authors:
Ramya Kasaraneni
V. Krishna Nandivada

abstract:
Constraint-based points-to analysis using Andersen-style inclusion constraints is widely used for its convenience, generality, and precision in modeling complex program behaviors. Typically, such analyses generate constraints and resolve them by computing the transitive closure of a constraint graph. However, traditional constraint modeling often introduces redundancy during constraint generation, solving, or both. In the context of points-to analysis for object-oriented languages like Java, this redundancy primarily stems from the modeling of virtual calls and heap operations. As a result, the analysis produces redundant constraints and inflated constraint graphs, thereby increasing analysis time.

To address these limitations, we propose a novel constraint representation and solving system PInter, which extends the traditional inclusion constraint model. It presents a novel technique to represent the constraints in compact and expressive way. Further, it defers generation of constraints until relevant objects are discovered, enabling demand-driven and interleaved constraint generation and solving. We present a proof of correctness of PInter. We used PInter to implement two different Java points-to analyses, within the Soot framework, and evaluated it on 12 applications drawn from the DaCapo benchmark suite. As is standard, we used Tamiflex to handle dynamic features of Java benchmarks and performed a soundy evaluation. Our results show that, compared to traditional methods, PInter reduced the constraint count by 96% (geomean) and the analysis time by 78% (geomean). We also evaluated PInter against Soot’s Spark and the flow-, context- insensitive analysis in Doop, and found that PInter achieved significantly faster performance.


title: TinyGen: Portable and Compact Code Generation for Tiny Machine Learning

authors:
Gaeun Ko
Seonyeong Heo

abstract:
Tiny machine learning (TinyML) enables low-power microcontrollers to leverage the power of artificial intelligence without relying on remote computing resources. Typically, developing a TinyML application relies primarily on existing TinyML frameworks, which provide runtime APIs for loading and executing machine learning models. However, such framework-based TinyML development has limitations in terms of portability, programmability, and resource efficiency, motivating the need for a new approach to the TinyML development and deployment process.

To address these challenges, this work introduces TinyGen, a new code generation framework for TinyML. TinyGen generates portable high-level code directly from a target model without depending on external runtime APIs. It statically analyzes the tensor and operator usage of the target model to enable compact code generation. This work demonstrates that TinyGen reduces binary code size by 31.2% on average compared to an existing TinyML framework while requiring fewer lines of code to write TinyML applications.


title: Schedgehammer: Auto-tuning Compiler Optimizations beyond Numerical Parameters

authors:
Johannes Lenfers
Sven Spehr
Justus Dieckmann
Johannes Jansen
Martin Paul Lücke
Sergei Gorlatch

abstract:
This paper introduces Schedgehammer, a general-purpose auto-scheduling framework that optimizes program execution across diverse compiler infrastructures. Unlike existing auto-schedulers that are tightly coupled to specific intermediate representations or rely on template-based search, Schedgehammer provides a generic, reusable framework for optimization schedules by modeling them as graph-structured objects. This approach captures dependencies among transformations and parameters across compilers, enabling systematic mutation and validation.

We demonstrate Schedgehammer’s flexibility on TVM and TACO, showing that it effectively optimizes dense and sparse computations. Across benchmarks, it achieves performance comparable to specialized auto-schedulers such as Ansor, highlighting that a unified, extensible abstraction can generalize scheduling beyond individual compiler ecosystems.


title: DiTOX: Fault Detection and Localization in the ONNX Optimizer

authors:
Nikolaos Louloudakis
Ajitha Rajan

abstract: The ONNX Optimizer, part of the official ONNX repository and widely adopted for graph-level model optimizations, is used by default to optimize ONNX models. Despite its popularity, its ability to preserve model correctness has not been systematically evaluated. We present DiTOX, an automated framework for comprehensively assessing the correctness of the ONNX Optimizer using differential testing, fault localization, and evaluation techniques that generalize to other compiler optimizers. DiTOX applies optimization passes to a corpus of ONNX models, executes both original and optimized versions on user-defined inputs, and detects discrepancies in behavior or optimizer failures. When divergences are observed, DiTOX isolates the responsible optimization pass through iterative, fine-grained analysis. We evaluated DiTOX on 130 models from the ONNX Model Hub spanning vision and language tasks. We found that 9.2% of model instances crashed the optimizer or produced invalid models under default settings. Moreover, output discrepancies occurred in 30% of classification models and 16.6% of object detection and segmentation models, while text-based models were largely robust. Overall, DiTOX uncovered 15 issues—14 previously unknown—affecting 9 of the 47 optimization passes as well as the optimizer infrastructure. All issues were reported to the ONNX Optimizer developers. Our results demonstrate that DiTOX provides a simple and effective approach for validating AI model optimizers and is readily extensible beyond ONNX.


title: Accelerating Sparse Algebra with Program Synthesis

authors:
José Wesley de Souza Magalhães
Shideh Hashemian
Alexander Brauckmann
Jackson Woodruff
Elizabeth Polgreen
Michael F. P. O'Boyle

abstract:
Linear algebra libraries and tensor domain-specific languages are able to deliver high performance for modern scientific and machine learning workloads. While there has been recent work in automatically translating legacy software to use these libraries/DSLs using pattern matching and program lifting, this has been largely limited to dense linear algebra.

This paper tackles the more challenging problem of porting legacy sparse linear algebra code to libraries and DSLs. It exploits the power of large language models to predict a sketch of the solution and then uses type-based program synthesis to search the space of possible code to target parameter bindings. We implement this in a tool named SLEB (Sparse LiftEr with Binding) and evaluate it on a large set of benchmarks and real-world datasets, comparing against two state-of-the-art compiler techniques, LiLAC and SpEQ; and GPT 4.o. Overall, we lift 94% of programs compared to 11%, 17%, and 48% for LiLAC, SpEQ, and GPT 4.o respectively. This delivers a geomean speedup of 2.6x and 7.2x on a CPU and GPU platform, respectively.


title: Practical MHP Analysis for Java

authors:
A. Samuel Moses
V. Krishna Nandivada

abstract: May happen in Parallel (MHP) analysis is one of the most foundational analysis in the context of programs written in parallel languages like Java. The currently known techniques for doing MHP analysis of Java applications suffer from two main challenges: (i) scalability to real-world large applications, (ii) precision in the presence of complex programs. In this manuscript, we address these two issues with a goal of making MHP analysis for Java applications a practical option. We propose a new MHP analysis scheme called GRIP-MHP. It includes techniques to reduce time taken to perform MHP analysis significantly; it does so by using novel schemes to reduce the size of the input graph (representing the original application). GRIP-MHP also addresses many drawbacks in existing techniques, thereby improving the applicability and precision of MHP analysis for real-world Java applications. We implemented GRIP-MHP in the Soot compiler framework. Our experiments show that GRIP-MHP runs successfully in reasonable time on all the tested benchmarks in DaCapo and Renaissance (geomean 20.176×improvement, over prior work). We find that GRIP-MHP performs more precise joining of threads significant leading to improvements in precision of the analysis results: geomean, 1.85×reduction in MHP pairs, over prior work.


title: Type Deduction Analysis: Reconstructing Transparent Pointer Types in LLVM-IR

authors:
Niccolò Nicolosi
Gabriele Magnani
Emilio Corigliano
Davide Baroffio
Federico Reghenzani
Giovanni Agosta

abstract: With version 17, LLVM finalized the transition to opaque pointer types, eliminating explicit pointee‑type information from the Intermediate Representation (IR). Thus, starting from LLVM 17, each pointer type is represented in IR by the unique type ptr. Despite eliminating redundant pointer bitcasts and consequently reducing IR size and compile time, this change disrupts analyses that have reason to rely on pointee-type information, forcing existing compiler projects to depend on outdated LLVM versions. This information can in fact be insightful in fields like approximate computing, where the compiler can apply non-conservative optimizations, or in passes that require it to make analyses and transformations that do not impact the correctness of the program. To address this problem, we present a new Type Deduction Analysis pass that reconstructs transparent pointer types directly from opaque‑pointer IR. Moreover, we illustrate two different case-studies on existing LLVM projects, namely TAFFO and ASPIS, that demonstrate the need for pointee-type information in LLVM compilers.


title: CHEHAB: Automatic Compiler Code Optimization for Fully Homomorphic Encryption

authors:
Abdessamed Seddiki
Arab Mohammed
Zakaria Hebbal
Aimad Chabounia
Eduardo Chielle
Karima Benatchba
Challal Yacine
Djamel Eddine Menacer
Michail Maniatakos
Riyadh Baghdadi

abstract: Fully Homomorphic Encryption (FHE) enables computations to be performed directly on encrypted data without requiring decryption, providing strong privacy guarantees. However, FHE remains computationally expensive, and writing efficient FHE programs is a complex, error-prone, and time-consuming task that demands significant cryptographic expertise. Programmers are often unaware of available optimizations, and applying them manually requires substantial effort. In this paper, we present CHEHAB, a compiler that automatically vectorizes scalar code, optimizes it, and generates highly efficient FHE programs. CHEHAB supports both structured and unstructured code and takes as input programs written in a domain-specific language embedded in C++. It relies on a Term Rewriting System (TRS) based on equality saturation to simplify and transform programs. CHEHAB targets two key challenges in FHE compilation: (1) automatic vectorization of scalar code, and (2) reduction of instruction execution latency and ciphertext noise growth. By leveraging equality saturation, CHEHAB explores a large optimization space to reduce instruction count and circuit depth while improving vector utilization. Experimental evaluation on a set of representative kernels shows that CHEHAB outperforms Coyote, a state-of-the-art vectorizing compiler for FHE. On average, CHEHAB generates code that is 7.38× faster at runtime, incurs 2.49× less accumulated noise, and achieves 251× faster compilation time. CHEHAB is released as an open-source compiler to support reproducibility and further research in FHE compilation.


venue: cgo

title: Dynamic Profiling and Trace Cache Generation

authors:
Marc Berndl
Laurie J. Hendren

abstract: Dynamic program optimization is increasingly important for achieving good runtime performance. A key issue is how to select which code to optimize. One approach is to dynamically detect traces, long sequences of instructions spanning multiple methods, which are likely to execute to completion. Traces are easy to optimize and have been shown to be a good unit for optimization. The paper reports on a new approach for dynamically detecting, creating and storing traces in a Java virtual machine. We first describe four important criteria for a successful trace strategy: good instruction stream coverage, low dispatch rate, cache stability, and optimizability of traces. We then present our approach based on branch correlation graphs. A branch correlation graph stores information about the correlation between pairs of branches, as well as additional state information. We present the complete design for an efficient implementation of the system, including a detailed discussion of the trace cache and profiling mechanisms. We have implemented an experimental framework to measure the traces generated by our approach in a direct-threaded Java VM (SableVM) and we present experimental results to show that the traces we generate meet the design criteria.


title: An Infrastructure for Adaptive Dynamic Optimization

authors:
Derek Bruening
Timothy Garnett
Saman P. Amarasinghe

abstract: Dynamic optimization is emerging as a promising approach to overcome many of the obstacles of traditional static compilation. But while there are a number of compiler infrastructures for developing static optimizations, there are very few for developing dynamic optimizations. We present a framework for implementing dynamic analyses and optimizations. We provide an interface for building external modules, or clients, for the DynamoRIO dynamic code modification system. This interface abstracts away many low-level details of the DynamoRIO runtime system while exposing a simple and powerful, yet efficient and lightweight API. This is achieved by restricting optimization units to linear streams of code and using adaptive levels of detail for representing instructions. The interface is not restricted to optimization and can be used for instrumentation, profiling, dynamic translation, etc. To demonstrate the usefulness and effectiveness of our framework, we implemented several optimizations. These improve the performance of some applications by as much as 40% relative to native execution. The average speedup relative to base DynamoRIO performance is 12%.


title: Optimizing Memory Accesses For Spatial Computation

authors:
Mihai Budiu
Seth Copen Goldstein

abstract: We present the internal representation and optimizations used by the CASH compiler for improving the memory parallelism of pointer-based programs. CASH uses an SSA-based representation for memory, which compactly summarizes both control-flow- and dependence information. In CASH, memory optimization is a four-step process: (1) first an initial, relatively coarse representation of memory dependences is built; (2) next, unnecessary memory dependences are removed using dependence tests; (3) third, redundant memory operations are removed (4) finally, parallelism is increased by pipelining memory accesses in loops. While the first three steps above are very general, the loop pipelining transformations are particularly applicable for spatial computation, which is the primary target of CASH. The redundant memory removal optimizations presented are: load/store hoisting (subsuming partial redundancy elimination and common-subexpression elimination), load-after-store removal, store-before-store removal (dead store removal) and loop-invariant load motion. One of our loop pipelining transformations is a new form of loop parallelization, called loop decoupling. This transformation separates independent memory accesses within a loop body into several independent loops, which are allowed dynamically to slip with respect to each other A new computational primitive, a token generator is used to dynamically control the amount of slip, allowing maximum freedom, while guaranteeing that no memory dependences are violated.


title: Optimal and Efficient Speculation-Based Partial Redundancy Elimination

authors:
Qiong Cai
Jingling Xue

abstract: Existing profile-guided partial redundancy elimination (PRE) methods use speculation to enable the removal of partial redundancies along more frequently executed paths at the expense of introducing additional expression evaluations along less frequently executed paths. While being capable of minimizing the number of expression evaluations in some cases, they are, in general, not computationally optimal in achieving this objective. In addition, the experimental results for their effectiveness are mostly missing. This work addresses the following three problems: (1) Is the computational optimality of speculative PRE solvable in polynomial time? (2) Is edge profiling - less costly than path profiling - sufficient to guarantee the computational optimality? (3) Is the optimal algorithm (if one exists) lightweight enough to be used efficiently in a dynamic compiler? In this paper, we provide positive answers to the first two problems and promising results to the third. We present an algorithm that analyzes edge insertion points based on an edge profile. Our algorithm guarantees optimally that the total number of computations for an expression in the transformed code is always minimized with respect to the edge profile given. This implies that edge profiling, which is less costly than path profiling, is sufficient to guarantee this optimality. The key in the development of our algorithm lies in the removal of some non-essential edges (and consequently, all resulting non-essential nodes) from a flow graph so that the problem of finding an optimal code motion is reduced to one of finding a minimal cut in the reduced (flow) graph thus obtained. We have implemented our algorithm in Intel's Open Runtime Platform (ORP). Our preliminary results over a number of Java benchmarks show that our algorithm is lightweight and can be potentially a practical component in a dynamic compiler. As a result, our algorithm can also be profitably employed in a profile-guided static compiler in which compilation cost can often be sacrificed for code efficiency.


title: Dynamic Trace Selection Using Performance Monitoring Hardware Sampling

authors:
Howard Chen
Wei-Chung Hsu
Dong-yuan Chen

abstract: Optimizing programs at run-time provides opportunities to apply aggressive optimizations to programs based on information that was not available at compile time. At run time, programs can be adapted to better exploit architectural features, optimize the use of dynamic libraries, and simplify code based on run-time constants. Our profiling system provides a framework for collecting information required for performing run-time optimization. We sample the performance hardware registers available on an Itanium processor, and select a set of code that is likely to lead to important performance-events. We gather distribution information about the performance-events we wish to monitor, and test our traces by estimating the ability for dynamic patching of a program to execute run-time generated traces. Our results show that we are able to capture 58% of execution time across various SPEC2000 integer benchmarks using our profile and patching techniques on a relatively small number of frequently executed execution paths. Our profiling and detection system overhead increases execution time by only 2-4%.


title: TEST: A Tracer for Extracting Speculative Thread

authors:
Michael K. Chen
Kunle Olukotun

abstract: Thread-level speculation (TLS) allows sequential programs to be arbitrarily decomposed into threads that can be safely executed in parallel. A key challenge for TLS processors is choosing thread decompositions that speedup the program. Current techniques for identifying decompositions have practical limitations in real systems. Traditional parallelizing compilers do not work effectively on most integer programs, and software profiling slows down program execution too much for real-time analysis. Tracer for Extracting Speculative Threads (TEST) is hardware support that analyzes sequential program execution to estimate performance of possible thread decompositions. This hardware is used in a dynamic parallelization system that automatically transforms unmodified, sequential Java programs to run on TLS processors. In this system, the best thread decompositions found by TEST are dynamically recompiled to run speculatively. The paper describes the analysis performed by TEST and presents simulation results demonstrating its effectiveness on real programs. Estimates are also provided that show the tracer requires minimal hardware additions to our speculative chip-multiprocessor (< 1% of the total transistor count) and causes only minor slowdowns to programs during analysis (3-25%).


title: Phi-Predication for Light-Weight If-Conversion

authors:
Weihaw Chuang
Brad Calder
Jeanne Ferrante

abstract: Predicated execution can eliminate hard to predict branches and help to enable instruction level parallelism. Many current predication variants exist where the result update is conditional based upon the outcome of the guarding predicate. However conditional writing of a register creates a naming problem for an out-of-order processor and can stall the issuing of instructions. This problem arises from potential multiple predicated definitions reaching a use, which is unresolved until the prior predicate values are computed. We focus on a light-weight form of predication, phi-predication, where all predicated instructions write a result value to their register regardless of the predicate value (i.e. even if it is false). Therefore, the predicate does not guard the writing of the result register; it instead acts as a form of selection between two input registers. This eliminates the naming problem for an out-of-order processor. Our phi-predicated ISA is derived from the predicated features of the Multiflow ISA, with extensions to efficiently predicate complex control flow. Our compiler modifications also expand upon prior techniques to provide efficient code generation. We examine the use of phi-predication for an in-order and out-of-order architecture and compare its performance to using select-op and IA64 ISA predication.


title: Optimizations to Prevent Cache Penalties for the Intel ® Itanium 2 Processor

authors:
Jean-Francois Collard
Daniel M. Lavery

abstract: This paper describes scheduling optimizations in the Intel/spl reg/ Itanium/spl reg/ compiler to prevent cache penalties due to various micro-architectural effects on the Itanium 2 processor. This paper does not try to improve cache hit rates but to avoid penalties, which probably all processors have in one form or another, even in the case of cache hits. These optimizations make use of sophisticated methods for disambiguation of memory references, and this paper examines the performance improvement obtained by integrating these methods into the cache optimizations.


title: The Transmeta Code Morphing - Software: Using Speculation, Recovery, and Adaptive Retranslation to Address Real-Life Challenges

authors:
James C. Dehnert
Brian Grant
John P. Banning
Richard Johnson
Thomas Kistler
Alexander Klaiber
Jim Mattson

abstract: Transmeta's Crusoe microprocessor is a full, system-level implementation of the x86 architecture, comprising a native VLIW microprocessor with a software layer, the Code Morphing Software (CMS), that combines an interpreter, dynamic binary translator, optimizer, and run-time system. In its general structure, CMS resembles other binary translation systems described in the literature, but it is unique in several respects. The wide range of PC workloads that CMS must handle gracefully in real-life operation, plus the need for full system-level x86 compatibility, expose several issues that have received little or no attention in previous literature, such as exceptions and interrupts, I/O, DMA, and self-modifying code. In this paper we discuss some of the challenges raised by these issues, and present the techniques developed in Crusoe and CMS to meet those challenges. The key to these solutions is the Crusoe paradigm of aggressive speculation, recovery to a consistent x86 state using unique hardware commit-and-rollback support, and adaptive retranslation when exceptions occur too often to be handled efficiently by interpretation.


title: Code Optimization for Code Compression

authors:
Milenko Drinic
Darko Kirovski
Hoi Vo

abstract: With the emergence of software delivery platforms such as Microsoft's .NET, the reduced size of transmitted binaries has become a very important system parameter, strongly affecting system performance. We present two novel pre-processing steps for code compression that explore program binaries' syntax and semantics to achieve superior compression ratios. The first preprocessing step involves heuristic partitioning of a program binary into streams with high auto-correlation. The second preprocessing step uses code optimization via instruction rescheduling in order to improve prediction probabilities for a given compression engine. We have developed three heuristics for instruction rescheduling that explore tradeoffs of the solution quality versus algorithm run-time. The pre-processing steps are integrated with the generic paradigm of prediction by partial matching (PPM) which is the basis of our compression codec. The compression algorithm is implemented for x86 binaries and tested on several large Microsoft applications. Binaries compressed using our compression codec are 18-24% smaller than those compressed using the best available off-the-shelf compressor.


title: Addressing Mode Selection

authors:
Erik Eckstein
Bernhard Scholz

abstract: Many processor architectures provide a set of addressing modes in their address generation units. For example DSP (digital signal processors) have powerful addressing modes for efficiently implementing numerical algorithms. Typical addressing modes of DSP are auto post-modification and indexing for address registers. The selection of the optimal addressing modes in the means of minimal code size and minimal execution time depends on many parameters and is NP complete in general. In this work we present a new approach for solving the addressing mode selection (AMS) problem. We provide a method for modeling the target architecture's addressing modes as cost functions for a partitioned Boolean quadratic optimization problem (PBQP). For solving the PBQP we present an efficient and effective way to implement large matrices for modeling the cost model. We have integrated the addressing mode selection with the Atair C-Compiler for the uPD7705x DSP from NEC. In our experiments we show that the addressing mode selection can be optimally solved for almost all benchmark programs and the compile-time overhead of the address mode selection is within acceptable bounds for a production DSP compiler.


title: Design, Implementation and Evaluation of Adaptive Recompilation with On-Stack Replacement

authors:
Stephen J. Fink
Feng Qian

abstract: Modern virtual machines often maintain multiple compiled versions of a method. An on-stack replacement (OSR) mechanism enables a virtual machine to transfer execution between compiled versions, even while a method runs. Relying on this mechanism, the system can exploit powerful techniques to reduce compile time and code space, dynamically de-optimize code, and invalidate speculative optimizations. The paper presents a new, simple, mostly compiler-independent mechanism to transfer execution into compiled code. Additionally, we present enhancements to an analytic model for recompilation to exploit OSR for more aggressive optimization. We have implemented these techniques in Jikes RVM and present a comprehensive evaluation, including a study of fully automatic, online, profile-driven deferred compilation.


title: Local Scheduling Techniques for Memory Coherence in a Clustered VLIW Processor with a Distributed Data Cache

authors:
Enric Gibert
F. Jesús Sánchez
Antonio González

abstract: Clustering is a common technique to deal with wire delays. Fully-distributed architectures, where the register file, the functional units and the cache memory are partitioned, are particularly effective to deal with these constraints and besides they are very scalable. However the distribution of the data cache introduces a new problem: memory instructions may reach the cache in an order different to the sequential program order, thus possibly violating its contents. In this paper two local scheduling mechanisms that guarantee the serialization of aliased memory instructions are proposed and evaluated: the construction of memory dependent chains (MDC solution), and two transformations (store replication and load-store synchronization) applied to the original data dependence graph (DDGT solution). These solutions do not require any extra hardware. The proposed scheduling techniques are evaluated for a word-interleaved cache clustered VLIW processor (although these techniques can also be used for any other distributed cache configuration). Results for the Mediabench benchmark suite demonstrate the effectiveness of such techniques. In particular, the DDGT solution increases the proportion of local accesses by 16% compared to MDC, and stall time is reduced by 32% since load instructions can be freely scheduled in any cluster However the MDC solution reduces compute time and it often outperforms the former. Finally the impact of both techniques on an architecture with attraction buffers is studied and evaluated.


title: Optimization Opportunities Created by Global Data Reordering

authors:
Gadi Haber
Moshe Klausner
Vadim Eisenberg
Bilha Mendelson
Maxim Gurevich

abstract: Memory access has proven to be one of the bottlenecks in modern architectures. Improving memory locality and eliminating the amount of memory access can help release this bottleneck. We present a method for link-time profile-based optimization by reordering the global data of the program and modifying its code accordingly. The proposed optimization reorders the entire global data of the program, according to a representative execution rate of each instruction (or basic block) in the code. The data reordering is done in a way that enables the replacement of frequently-executed Load instructions, which reference the global data, with fast Add Immediate instructions. In addition, it tries to improve the global data locality and to reduce the total size of the global data area. The optimization was implemented into FDPR (Feedback Directed Program Restructuring), a post-link optimizer, which is part of the IBM AIX operating system for the IBM pSeries servers. Our results on SPECint2000 show a significant improvement of up to 11% (average 3%) in execution time, along with up to 97.9% (average 83%) reduction in memory references to the global variables via the global data access mechanism of the program.


title: Adaptive Online Context-Sensitive Inlining

authors:
Kim M. Hazelwood
David Grove

abstract: As current trends in software development move toward more complex object-oriented programming, inlining has become a vital optimization that provides substantial performance improvements to C++ and Java programs. Yet, the aggressiveness of the inlining algorithm must be carefully monitored to effectively balance performance and code size. The state-of-the-art is to use profile information (associated with call edges) to guide inlining decisions. In the presence of virtual method calls, profile information for one call edge may not be sufficient for making effectual inlining decisions. Therefore, we explore the use of profiling data with additional levels of context sensitivity. In addition to exploring fixed levels of context sensitivity, we explore several adaptive schemes that attempt to find the ideal degree of context sensitivity for each call site. Our techniques are evaluated on the basis of runtime performance, code size and dynamic compilation time. On average, we found that with minimal impact on performance (+/-1%) context sensitivity can enable 10% reductions in compiled code space and compile time. Performance on individual programs varied from -4.2% to 5.3% while reductions in compile time and code space of up to 33.0% and 56.7% respectively were obtained.


title: Integrated Prepass Scheduling for a Java Just-In-Time Compiler on the IA-64 Architecture

authors:
Tatsushi Inagaki
Hideaki Komatsu
Toshio Nakatani

abstract: We present a new integrated prepass scheduling (IPS) algorithm for a Java just-in-time (JIT) compiler which integrates register minimization into list scheduling. We use backtracking in the list scheduling when we have used up all the available registers. To reduce the overhead of backtracking, we incrementally maintain a set of candidate instructions for undoing scheduling. To maximize the ILP after undoing scheduling, we select an instruction chain with the smallest increase in the total execution time. We implemented our new algorithm in a production-level Java JIT compiler for the Intel Itanium processor. The experiment showed that, compared to the best known algorithm by Govindarajan et al., our IPS algorithm improved the performance by up to +1.8% while it reduced the compilation time for IPS by 58% on average.


title: Jumbo: Run-Time Code Generation for Java and Its Applications

authors:
Sam Kamin
Lars Clausen
Ava Jarvis

abstract: Run-time code generation is a well-known technique for improving the efficiency of programs by exploiting dynamic information. Unfortunately, the difficulty of constructing run-time code-generators has hampered their widespread use. We describe Jumbo, a tool for easily creating run-time code generators for Java. Jumbo is a compiler for a two-level version of Java, where programs can contain quoted code fragments. The Jumbo API allows the code fragments to be combined at run-time and then executed. We illustrate Jumbo with several examples that show significant speedups over similar code written in plain Java, and argue further that Jumbo is a generalized software component system.


title: Dynamic Binary Translation for Accumulator-Oriented Architectures

authors:
Ho-Seop Kim
James E. Smith

abstract: A dynamic binary translation system for a co-designed virtual machine is described and evaluated. The underlying hardware directly executes an accumulator-oriented instruction set that exposes instruction dependence chains (strands) to a distributed microarchitecture containing a simple instruction pipeline. To support conventional program binaries, a source instruction set (Alpha in our study) is dynamically translated to the target accumulator instruction set. The binary translator identifies chains of inter-instruction dependences and assigns them to dependence-carrying accumulators. Because the underlying superscalar microarchitecture is capable of dynamic instruction scheduling, the binary translation system does not perform aggressive optimizations or re-schedule code; this significantly reduces binary translation overhead. Detailed timing simulation of the dynamically translated code running on an accumulator-based distributed microarchitecture shows the overall system is capable of achieving similar performance to an ideal out-of-order superscalar processor, ignoring the significant clock frequency advantages that the accumulator-based hardware is likely to have. As part of the study, we evaluate an instruction set modification that simplifies precise trap implementation. This approach significantly reduces the number of instructions required for register state copying, thereby improving performance. We also observe that translation chaining methods can have substantial impact on the performance, and we evaluate a number of chaining methods.


title: Coupling On-Line and Off-Line Profile Information to Improve Program Performance

abstract: In this paper we describe a novel execution environment for Java programs that substantially improves execution performance by incorporating both on-line and off-line profile information to guide dynamic optimization. By using both types of profile collection techniques, we are able to exploit the strengths of each constituent approach: profile accuracy and low overhead. Such coupling also reduces the negative impact of these approaches when each is used in isolation. On-line profiling introduces overhead for dynamic instrumentation, measurement, and decision making. Off-line profile information can be inaccurate when program inputs for execution and optimization differ from those used for profiling. To combat these drawbacks and to achieve the benefits from both online and off-line profiling, we developed a dynamic compilation system (based on JikesRVM) that makes use of both. As a result, we are able improve Java program performance by 9% on average, for the programs studied.


title: Speculative Register Promotion Using Advanced Load Address Table (ALAT)

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

abstract: The pervasive use of pointers with complicated patterns in C programs often constrains compiler alias analysis to yield conservative register allocation and promotion. Speculative register promotion with hardware support has the potential to more aggressively promote memory references into registers in the presence of aliases. This paper studies the use of the advanced load address table (ALAT), a data speculation feature defined in the IA-64 architecture, for speculative register promotion. An algorithm for speculative register promotion based on partial redundancy elimination is presented. The algorithm is implemented in Intel's open research compiler (ORC). Experiments on SPEC CPU2000 benchmark programs are conducted to show that speculative register promotion can improve performance of some benchmarks by 1% to 7%.


title: METRIC: Tracking Down Inefficiencies in the Memory Hierarchy via Binary Rewriting

authors:
Jaydeep Marathe
Frank Mueller
Tushar Mohan
Bronis R. de Supinski
Sally A. McKee
Andy Yoo

abstract: We present METRIC, an environment for determining memory inefficiencies by examining data traces. METRIC is designed to alter the performance behavior of applications that are mostly constrained by their latency to resolve memory references. We make four primary contributions. First, we present methods to extract partial data traces from running applications by observing their memory behavior via dynamic binary rewriting. Second, we present a methodology to represent partial data traces in constant space for regular references through a novel technique for online compression of reference streams. Third, we employ offline cache simulation to derive indications about memory performance bottlenecks from partial data traces. By exploiting summarized memory metrics, by-reference metrics as well as cache evictor information, we can pin-point the sources of performance problems. Fourth, we demonstrate the ability to derive opportunities for optimizations and assess their benefits in several experiments resulting in up to 40% lower miss ratios.


title: Reality-Based Optimization

abstract: Profile-based optimization has been studied extensively. Numerous papers and real systems have shown substantial improvements. However, most of these papers have been limited to either branch prediction or instruction cache performance. Also, most of these papers have looked at small applications with a limited number of testing and training scenarios. In this paper, we look at real use of large real-world desktop applications. We also assume memory consumption and disk performance are the primary metrics of interest. For this domain, we show that it is very difficult to get adequate coverage of large applications even with an extensive collection of training scenarios. We propose instead to augment traditional scenarios with data derived from real use. We show that this methodology allows us to reduce memory pressure by 29% and disk reads by 33% compared to traditional approaches.


title: Retargetable and Reconfigurable Software Dynamic Translation

authors:
Kevin Scott
Naveen Kumar
S. Velusamy
Bruce R. Childers
Jack W. Davidson
Mary Lou Soffa

abstract: Software dynamic translation (SDT) is a technology that permits the modification of an executing program's instructions. In recent years, SDT has received increased attention, from both industry and academia, as a feasible and effective approach to solving a variety of significant problems. Despite this increased attention, the task of initiating a new project in software dynamic translation remains a difficult one. To address this concern, and in particular, to promote the adoption of SDT technology into an even wider range of applications, we have implemented Strata, a cross-platform infrastructure for building software dynamic translators. This paper describes Strata's architecture, our experience retargeting it to three different processors, and our use of Strata to build two novel SDT systems - one for safe execution of untrusted binaries and one for fast prototyping of architectural simulators.


title: Optimization for the Intel® Itanium ®Architectur Register Stack

authors:
Alex Settle
Daniel A. Connors
Gerolf Hoflehner
Daniel M. Lavery

abstract: The Intel/spl reg/ Itanium/spl reg/ architecture contains a number of innovative compiler-controllable features designed to exploit instruction level parallelism. New code generation and optimization techniques are critical to the application of these features to improve processor performance. For instance, the Itanium/spl reg/ architecture provides a compiler-controllable virtual register stack to reduce the penalty of memory accesses associated with procedure calls. The Itanium/spl reg/ Register Stack Engine (RSE) transparently manages the register stack and saves and restores physical registers to and from memory as needed. Existing code generation techniques for the register stack aggressively allocate virtual registers without regard to the register pressure on different control-flow paths. As such, applications with large data sets may stress the RSE, and cause substantial execution delays due to the high number of register saves and restores. Since the Itanium/spl reg/ architecture is developed around Explicitly Parallel Instruction Computing (EPIC) concepts, solutions to increasing the register stack efficiency favor code generation techniques rather than hardware approaches.


title: Predicate-Aware Scheduling: A Technique for Reducing Resource Constraints

authors:
Mikhail Smelyanskiy
Scott A. Mahlke
Edward S. Davidson
Hsien-Hsin S. Lee

abstract: Predicated execution enables the removal of branches wherein segments of branching code are converted into straight-line segments of conditional operations. An important, but generally ignored side effect of this transformation is that the compiler must assign distinct resources to all the predicated operations at a given time to ensure that those resources are available at run-time. However, a resource is only put to productive use when the predicates associated with its operations evaluate to True. We propose predicate-aware scheduling to reduce the superfluous commitment of resources to operations whose predicates evaluate to False at run-time. The central idea is to assign multiple operations to the same resource at the same time, thereby oversubscribing its use. This assignment is intelligently performed to ensure that no two operations simultaneously assigned to the same resource will have both of their predicates evaluate to True. Thus, no resource is dynamically oversubscribed. The overall effect of predicate aware scheduling is to use resources more efficiently, thereby increasing performance when resource constraints are a bottleneck.


title: Improving Quasi-Dynamic Schedules through Region Slip

authors:
Francesco Spadini
Brian Fahs
Sanjay J. Patel
Steven S. Lumetta

abstract: Modern processors perform dynamic scheduling to achieve better utilization of execution resources. A schedule created at run-time is often better than one created at compile-time as it can dynamically adapt to specific events encountered at execution-time. In this paper, we examine some fundamental impediments to effective static scheduling. More specifically, we examine the question of why schedules generated quasi-dynamically by a low-level runtime optimizer and executed on a statically scheduled machine perform worse than using a dynamically-scheduled approach. We observe that such schedules suffer because of region boundaries and a skewed distribution of parallelism towards the beginning of a region. To overcome these limitations, we investigate a new concept, region slip, in which the schedules of different statically-scheduled regions can be interleaved in the processor issue queue to reduce the region boundary effects that cause empty issue slots.


title: Inlining of Mathematical Functions in HP-UX for Itanium ® 2

abstract: HP-UX compilers inline mathematical functions for Itanium processor family (IPF) systems to improve throughput 4X-8X versus external library calls, achieving speeds comparable to highly tuned vector functions, without requiring the user to code for a vector interface and without sacrificing accuracy or edge-case behaviors. This paper highlights IPF architectural features that support implementation of high-performance, high-quality mathematics functions for inlining. It discusses strategies for utilizing the features and developing inlineable sequences on a large scale, and it presents requisite compiler features and language extensions. Also, this paper describes compiler mechanisms that produce inlineable code and inline it.


title: Compiler Optimization-Space Exploration

authors:
Spyridon Triantafyllis
Manish Vachharajani
Neil Vachharajani
David I. August

abstract: To meet the demands of modern architectures, optimizing compilers must incorporate an ever larger number of increasingly complex transformation algorithms. Since code transformations may often degrade performance or interfere with subsequent transformations, compilers employ predictive heuristics to guide optimizations by predicting their effects a priori. Unfortunately, the unpredictability of optimization interaction and the irregularity of today's wide-issue machines severely limit the accuracy of these heuristics. As a result, compiler writers may temper high variance optimizations with overly conservative heuristics or may exclude these optimizations entirely. While this process results in a compiler capable of generating good average code quality across the target benchmark set, it is at the cost of missed optimization opportunities in individual code segments. To replace predictive heuristics, researchers have proposed compilers which explore many optimization options, selecting the best one a posteriori. Unfortunately, these existing iterative compilation techniques are not practical for reasons of compile time and applicability. We present the Optimization-Space Exploration (OSE) compiler organization, the first practical iterative compilation strategy applicable to optimizations in general-purpose compilers. Instead of replacing predictive heuristics, OSE uses the compiler writer's knowledge encoded in the heuristics to select a small number of promising optimization alternatives for a given code segment. Compile time is limited by evaluating only these alternatives for hot code segments using a general compile-time performance estimator An OSE-enhanced version of Intel's highly-tuned, aggressively optimizing production compiler for IA-64 yields a significant performance improvement, more than 20% in some cases, on Itanium for SPEC codes.


title: Hiding Program Slices for Software Security

authors:
Xiangyu Zhang
Rajiv Gupta

abstract: Given the high cost of producing software, development of technology for prevention of software piracy is important for the software industry. In this paper we present a novel approach for preventing the creation of unauthorized copies of software. Our approach splits software modules into open and hidden components. The open components are installed (executed) on an insecure machine while the hidden components are installed (executed) on a secure machine. We assume that while open components can be stolen, to obtain a fully functioning copy of the software, the hidden components must be recovered. We describe an algorithm that constructs hidden components by slicing the original software components. We argue that recovery of hidden components constructed through slicing, in order to obtain a fully functioning copy of the software, is a complex task. We further develop security analysis to capture the complexity of recovering hidden components. Finally we apply our technique to several large Java programs to study the complexity of recovering constructed hidden components and to measure the runtime overhead introduced by splitting of software into open and hidden components.


title: Improving 64-Bit Java IPF Performance by Compressing Heap References

authors:
Ali-Reza Adl-Tabatabai
Jay Bharadwaj
Michal Cierniak
Marsha Eng
Jesse Fang
Brian T. Lewis
Brian R. Murphy
James M. Stichnoth

abstract: 64-bit processor architectures like the Intel/spl reg/ Itanium/spl reg/ processor family are designed for large applications that need large memory addresses. When running applications that fit within a 32-bit address space, 64-bit CPUs are at a disadvantage compared to 32-bit CPUs because of the larger memory footprints for their data. This results in worse cache and TLB utilization, and consequently lower performance because of increased miss ratios. This paper considers software techniques for virtual machines that allow 32-bit pointers to be used on 64-bit CPUs for managed runtime applications that do not need the full 64-bit address space. We describe our pointer compression techniques and discuss our experience implementing these for Java applications. In addition, we give performance results with our techniques for both the SPEC JVM98 and SPEC JBB2000 benchmarks. We demonstrate a 12% performance improvement on SPEC JBB2000 and a reduction in the number of garbage collections required for a given heap size.


title: Specialized Dynamic Optimizations for High-Performance Energy-Efficient Microarchitecture

authors:
Yoav Almog
Roni Rosner
Naftali Schwartz
Ari Schmorak

abstract: We study several major characteristics of dynamic optimization within the PARROT power-aware, trace-cache-based microarchitectural framework. We investigate the benefit of providing optimizations which although tightly coupled with the microarchitecture in substance are decoupled in time. The tight coupling in substance provides the potential for tailoring optimizations for microarchitecture in a manner impossible or impractical not only for traditional static compilers but even for a JIT. We show that the contribution of common, generic optimizations to processor performance and energy efficiency may be more than doubled by creating a more intimate correlation between hardware specifics and the optimizer. In particular, dynamic optimizations can profit greatly from hardware supporting fused and SIMDified operations. At the same time, the decoupling in time allows optimizations to be arbitrarily aggressive without significant performance loss. We demonstrate that requiring up to 512 repetitions before a trace is optimized sacrifices almost no performance or efficiency as compared with lower thresholds. These results confirm the feasibility of energy efficient hardware implementation of an aggressive optimizer.


title: Software-Controlled Operand-Gating

authors:
Ramon Canal
Antonio González
James E. Smith

abstract: Operand gating is a technique for improving processor energy efficiency by gating off sections of the data path that are unneeded by short-precision (narrow) operands. A method for implementing software-controlled power gating is proposed and evaluated. The instruction set architecture (ISA) is enhanced to include opcodes that specify operand widths (if not already included in the ISA). A compiler or a binary translator uses statically available information to determine initial value ranges. The technique is enhanced through a profile-based analysis that results in the specialization of certain code regions for a given value range. After the analysis, instruction opcodes are assigned using the minimum required width. To evaluate this technique the Alpha instruction set is enhanced to include opcodes for 8, 16, and 32 bit operands. Applying the proposed software technique to the Speclnt95 benchmarks results in energy-delay savings of 14%. When combined with previously proposed hardware-based techniques, the energy-delay benefit is 28%.


title: A Compiler Scheme for Reusing Intermediate Computation Results

authors:
Yonghua Ding
Zhiyuan Li

abstract: Recent research has shown that programs often exhibit value locality. Such locality occurs when a code segment, although executed repeatedly in the program, takes only a small number of different values as input and, naturally, generates a small number of different outputs. It is potentially beneficial to replace such a code segment by a table, which records the computation results for the previous inputs. When the program execution re-enters the code segment with a repeated input, its computation can be simplified to a table look-up. We discuss a compiler scheme to identify code segments, which are good candidates for computation reuse. We discuss the conditions under which the table look-up costs less than repeating the execution, and we perform profiling to identify candidates, which have many repeated inputs at run time. Compared to previous work, this scheme requires no special hardware support and is therefore particularly useful for resource constrained systems such as handheld computing devices. We implement our scheme and its supporting analyses in GCC. We experiment with several multimedia benchmarks and the GNU Go game by executing them on a handheld computing device. The results show the scheme to improve the performance and to reduce the energy consumption quite substantially for these programs.


title: VHC: Quickly Building an Optimizer for Complex Embedded Architectures

authors:
Michael Dupré
Nathalie Drach
Olivier Temam

abstract: To meet the high demand for powerful embedded processors, VLIW architectures are increasingly complex (e.g., multiple clusters), and moreover, they now run increasingly sophisticated control-intensive applications. As a result, developing architecture-specific compiler optimizations is becoming both increasingly critical and complex, while time-to-market constraints remain very tight. We present a novel program optimization approach, called the virtual hardware compiler (VHC), that can perform as well as static compiler optimizations, but which requires far less compiler development effort, even for complex VLIW architectures and complex target applications. The principle is to augment the target processor simulator with superscalar-like features, observe how the target program is dynamically optimized during execution, and deduce an optimized binary for the static VLIW architecture. Developing an architecture-specific optimizer then amounts to modifying the processor simulator which is very fast compared to adapting static compiler optimizations to an architecture. We also show that a VHC-optimized binary trained on a number of data sets performs as well as a statically-optimized binary on other test data sets. The only drawback of the approach is a largely increased compilation time, which is often acceptable for embedded applications and devices. Using the Texas Instruments C62 VLIW processor and the associated compiler, we experimentally show that this approach performs as well as static compiler optimizations for a much lower research and development effort. Using a single-core C60 and a dual-core clustered C62 processors, we also show that the same approach can be used for efficiently retargeting binary programs within a family of processors.


title: Exploring Code Cache Eviction Granularities in Dynamic Optimization Systems

authors:
Kim M. Hazelwood
James E. Smith

abstract: Dynamic optimization systems store optimized or translated code in a software-managed code cache in order to maximize reuse of transformed code. Code caches store superblocks that are not fixed in size, contain links to other superblocks, and carry a high replacement overhead. These additional constraints reduce the effectiveness of conventional hardware-based cache management policies. In this paper, we explore code cache management policies that evict large blocks of code from the code cache, thus avoiding the bookkeeping overhead of managing single cache blocks. Through a combined simulation and analytical study of cache management overheads, we show that employing a medium-grained FIFO eviction policy results in an effective balance of cache management complexity and cache miss rates. Under high cache pressure the choice of medium granularity translates into a significant reduction in overall execution time versus both coarse and fine granularities.


title: Using Dynamic Binary Translation to Fuse Dependent Instructions

authors:
Shiliang Hu
James E. Smith

abstract: Instruction scheduling hardware can be simplified and easily pipelined if pairs of dependent instructions are fused so they share a single instruction scheduling slot. We study an implementation of the x86 ISA that dynamically translates x86 code to an underlying ISA that supports instruction fusing. A microarchitecture that is codesigned with the fused instruction set completes the implementation. We focus on the dynamic binary translator for such a codesigned x86 virtual machine. The dynamic binary translator first cracks x86 instructions belonging to hot superblocks into RISC-style microoperations, and then uses heuristics to fuse together pairs of dependent microoperations. Experimental results with SPEC2000 integer benchmarks demonstrate that: (1) the fused ISA with dynamic binary translation reduces the number of scheduling decisions by about 30% versus a conventional implementation that uses hardware cracking into RISC microoperations; (2) an instruction scheduling slot needs only hold two source register fields even though it may hold two instructions; (3) translations generated in the proposed ISA consume about 30% less storage than a corresponding fixed-length RISC-style ISA.


title: Targeted Path Profiling: Lower Overhead Path Profiling for Staged Dynamic Optimization Systems

authors:
Rahul Joshi
Michael D. Bond
Craig B. Zilles

abstract: We present a technique for reducing the overhead of collecting path profiles in the context of a dynamic optimizer. The key idea to our approach, called targeted path profiling (TPP), is to use an edge profile to simplify the collection of a path profile. This notion of profile-guided profiling is a natural fit for dynamic optimizers, which typically optimize the code in a series of stages. TPP is an extension to the Ball-Lams efficient path profiling algorithm. Its increased efficiency comes from two sources: (i) reducing the number of potential paths by not enumerating paths with cold edges, allowing array accesses to be substituted for more expensive hash table lookups, and (ii) not instrumenting regions where paths can be unambiguously derived from an edge profile. Our results suggest that on average the overhead of profile collection can be reduced by half (SPEC95) to almost two-thirds (SPEC2000) relative to the Ball-Larus algorithm with minimal impact on the information collected.


title: Physical Experimentation with Prefetching Helper Threads on Intel's Hyper-Threaded Processors

authors:
Dongkeun Kim
Shih-Wei Liao
Perry H. Wang
Juan del Cuvillo
Xinmin Tian
Xiang Zou
Hong Wang
Donald Yeung
Milind Girkar
John Paul Shen

abstract: Pre-execution techniques have received much attention as an effective way of prefetching cache blocks to tolerate the ever-increasing memory latency. A number of pre-execution techniques based on hardware, compiler, or both have been proposed and studied extensively by researchers. They report promising results on simulators that model a simultaneous multithreading (SMT) processor. We apply the helper threading idea on a real multithreaded machine, i.e., Intel Pentium 4 processor with hyper-threading technology, and show that indeed it can provide wall-clock speedup on real silicon. To achieve further performance improvements via helper threads, we investigate three helper threading scenarios that are driven by automated compiler infrastructure, and identify several key challenges and opportunities for novel hardware and software optimizations. Our study shows a program behavior changes dynamically during execution. In addition, the organizations of certain critical hardware structures in the hyper-threaded processors are either shared or partitioned in the multithreading mode and thus, the tradeoffs regarding resource contention can be intricate. Therefore, it is essential to judiciously invoke helper threads by adapting to the dynamic program behavior so that we can alleviate potential performance degradation due to resource contention. Moreover, since adapting to the dynamic behavior requires frequent thread synchronization, having light-weight thread synchronization mechanisms is important.


title: FLASH: Foresighted Latency-Aware Scheduling Heuristic for Processors with Customized Datapaths

authors:
Manjunath Kudlur
Kevin Fan
Michael L. Chu
Rajiv A. Ravindran
Nathan Clark
Scott A. Mahlke

abstract: Application-specific instruction set processors (ASIPs) have the potential to meet the challenging cost, performance, and power goals of future embedded processors by customizing the hardware to suit an application. A central problem is creating compilers that are capable of dealing with the heterogeneous and nonuniform hardware created by the customization process. The processor datapath provides an effective area to customize, but specialized datapaths often have nonuniform connectivity between the function units, making the effective latency of a function unit dependent on the consuming operation. Traditional instruction schedulers break down in this environment due to their locally greedy nature of binding the best choice for a single operation even though that choice may be poor due to a lack of communication paths. To effectively schedule with nonuniform connectivity, we propose a foresighted latency-aware scheduling heuristic (FLASH) that performs lookahead across future scheduling steps to estimate the effects of a potential binding. FLASH combines a set of lookahead heuristics to achieve effective foresight with low compile-time overhead.


title: LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation

authors:
Chris Lattner
Vikram S. Adve

abstract: We describe LLVM (low level virtual machine), a compiler framework designed to support transparent, lifelong program analysis and transformation for arbitrary programs, by providing high-level information to compiler transformations at compile-time, link-time, run-time, and in idle time between runs. LLVM defines a common, low-level code representation in static single assignment (SSA) form, with several novel features: a simple, language-independent type-system that exposes the primitives commonly used to implement high-level language features; an instruction for typed address arithmetic; and a simple mechanism that can be used to implement the exception handling features of high-level languages (and setjmp/longjmp in C) uniformly and efficiently. The LLVM compiler framework and code representation together provide a combination of key capabilities that are important for practical, lifelong analysis and transformation of programs. To our knowledge, no existing compilation approach provides all these capabilities. We describe the design of the LLVM representation and compiler framework, and evaluate the design in three ways: (a) the size and effectiveness of the representation, including the type information it provides; (b) compiler performance for several interprocedural problems; and (c) illustrative examples of the benefits LLVM provides for several challenging compiler problems.


title: A Dynamically Tuned Sorting Library

authors:
Xiaoming Li
María Jesús Garzarán
David A. Padua

abstract: Empirical search is a strategy used during the installation of library generators such as ATLAS, FFTW, and SPIRAL to identify the algorithm or the version of an algorithm that delivers the best performance. In the past, empirical search has been applied almost exclusively to scientific problems. In this paper, we discuss the application of empirical search to sorting, which is one of the best understood symbolic computing problems. When contrasted with the dense numerical computations of ATLAS, FFTW, and SPIRAL, sorting presents a new challenge, namely that the relative performance of the algorithms depend not only on the characteristics of the target machine and the size of the input data but also on the distribution of values in the input data set. Empirical search is applied in the study reported here as part of a sorting library generator. The resulting routines dynamically adapt to the characteristics of the input data by selecting the best sorting algorithm from a small set of alternatives. To generate the run time selection mechanism our generator makes use of machine learning to predict the best algorithm as a function of the characteristics of the input data set and the performance of the different algorithms on the target machine. This prediction is based on the data obtained through empirical search at installation time. Our results show that our approach is quite effective. When sorting data inputs of 12M keys with various standard deviations, our adaptive approach selected the best algorithm for all the input data sets and all platforms that we tried in our experiments. The wrong decision could have introduced a performance degradation of up to 133%, with an average value of 44%.


title: Ispike: A Post-link Optimizer for the Intel®Itanium®Architecture

authors:
Chi-Keung Luk
Robert Muth
Harish Patil
Robert S. Cohn
P. Geoffrey Lowney

abstract: Ispike is a post-link optimizer developed for the Intel/spl reg/ Itanium Processor Family (IPF) processors. The IPF architecture poses both opportunities and challenges to post-link optimizations. IPF offers a rich set of performance counters to collect detailed profile information at a low cost, which is essential to post-link optimization being practical. At the same time, the predication and bundling features on IPF make post-link code transformation more challenging than on other architectures. In Ispike, we have implemented optimizations like code layout, instruction prefetching, data layout, and data prefetching that exploit the IPF advantages, and strategies that cope with the IPF-specific challenges. Using SPEC CINT2000 as benchmarks, we show that Ispike improves performance by as much as 40% on the ltanium/spl reg/2 processor, with average improvement of 8.5% and 9.9% over executables generated by the Intel/spl reg/ Electron compiler and by the Gcc compiler, respectively. We also demonstrate that statistical profiles collected via IPF performance counters and complete profiles collected via instrumentation produce equal performance benefit, but the profiling overhead is significantly lower for performance counters.


title: SYZYGY - A Framework for Scalable Cross-Module IPO

authors:
Sungdo Moon
Xinliang D. Li
Robert Hundt
Dhruva R. Chakrabarti
Luis A. Lozano
Uma Srinivasan
Shin-Ming Liu

abstract: Performing analysis across module boundaries for an entire program is important for exploiting several runtime performance opportunities. However, due to scalability problems in existing full-program analysis frameworks, such performance opportunities are only realized by paying tremendous compile-time costs. Alternative solutions, such as partial compilations or user assertions, are complicated or unsafe and as a result, not many commercial applications are compiled today with cross-module optimizations. We present SYZYGY, a practical framework for performing efficient, scalable, interprocedural optimizations. The framework is implemented in the HP-UX Itanium/spl reg/ compilers and we have successfully compiled many very large applications consisting of millions of lines of code. We achieved performance improvements of up to 40% over optimization level two and compilation time improvements in the order of 100% and more compared to a previous approach.


title: Static Identification of Delinquent Loads

authors:
Vlad-Mihai Panait
Amit Sasturkar
Weng-Fai Wong

abstract: The effective use of processor caches is crucial to the performance of applications. It has been shown that cache misses are not evenly distributed throughout a program. In applications running on RISC-style processors, a small number of delinquent load instructions are responsible for most of the cache misses. Identification of delinquent loads is the key to the success of many cache optimization and prefetching techniques. We propose a method for identifying delinquent loads that can be implemented at compile time. Our experiments over eighteen benchmarks from the SPEC suite shows that our proposed scheme is stable across benchmarks, inputs, and cache structures, identifying an average of 10% of the total number of loads in the benchmarks we tested that account for over 90% of all data cache misses. As far as we know, this is the first time a technique for static delinquent load identification with such a level of precision and coverage has been reported. While comparable techniques can also identify load instructions that cover 90% of all data cache misses, they do so by selecting over 50% of all load instructions in the code, resulting in a high number of false positives. If basic block profiling is used in conjunction with our heuristic, then our results show that it is possible to pin down just 1.3% of the load instructions that account for 82% of all data cache misses.


title: Optimizing Translation Out of SSA Using Renaming Constraints

authors:
Fabrice Rastello
François de Ferrière
Christophe Guillon

abstract: Static Single Assignment form is an intermediate representation that uses /spl Phi/ instructions to merge values at each confluent point of the control flow graph. /spl Phi/ instructions are not machine instructions and must be renamed back to move instructions when translating out of SSA form. Without a coalescing algorithm, the out of SSA translation generates many move instructions. Leung and George [A. L. Leung et al., (1999)] use a SSA form for programs represented as native machine instructions, including the use of machine dedicated registers. For this purpose, they handle renaming constraints thanks to a pinning mechanism. Pinning /spl Phi/ arguments and their corresponding definition to a common resource is also a very attractive technique for coalescing variables. Extending this idea, we propose a method to reduce the /spl Phi/-related copies during the out of SSA translation, thanks to a pinning-based coalescing algorithm that is aware of renaming constraints. We implemented our algorithm in the STMicroelectronics Linear Assembly Optimizer [B. Dupont de Dinechin et al., (2000)]. Our experiments show interesting results when comparing to the existing approaches of Leung and George [A. L. Leung et al., (1999)], Sreedhar et al. [V. Sreedhar et al., (1999)], and Appel and George for register coalescing [L. George et al., (1996)].


title: Code Generation for Single-Dimension Software Pipelining of Multi-Dimensional Loops

authors:
Hongbo Rong
Alban Douillet
Ramaswamy Govindarajan
Guang R. Gao

abstract: Traditionally, software pipelining is applied either to the innermost loop of a given loop nest or from the innermost loop to the outer loops. We proposed a scheduling method, called single-dimension software pipelining (SSP), to software pipeline a multidimensional loop nest at an arbitrary loop level. We describe our solution to SSP code generation. In contrast to traditional software pipelining, SSP handles two distinct repetitive patterns, and thus requires new code generation algorithms. Further, these two distinct repetitive patterns complicate register assignment and require two levels of register renaming. As rotating registers support renaming at only one level, our solution is based on a combination of dynamic register renaming (using rotating registers) and static register renaming (using code replication). Finally, code size increase, an even more important issue for SSP than for traditional software-pipelining, is also addressed. Optimizations are proposed to reduce code size without significant performance degradation. We first present a code generation scheme and subsequently implement it for the IA-64 architecture, making effective use of rotating registers and predicated execution. We present some initial experimental results, which demonstrate not only the feasibility and correctness of our code generation scheme, but also its code quality.


title: Single-Dimension Software Pipelining for Multi-Dimensional Loops

authors:
Hongbo Rong
Zhizhong Tang
Ramaswamy Govindarajan
Alban Douillet
Guang R. Gao

abstract: Traditionally, software pipelining is applied either to the innermost loop of a given loop nest or from the innermost loop to outer loops. We propose a three-step approach, called single-dimension software pipelining (SSP), to software pipeline a loop nest at an arbitrary loop level. The first step identifies the most profitable loop level for software pipelining in terms of initiation rate or data reuse potential. The second step simplifies the multidimensional data-dependence graph (DDG) into a 1-dimensional DDG and constructs a 1-dimensional schedule for the selected loop level. The third step derives a simple mapping function which specifies the schedule time for the operations of the multidimensional loop, based on the 1-dimensional schedule. We prove that the SSP method is correct and at least as efficient as other modulo scheduling methods. We establish the feasibility and correctness of our approach by implementing it on the IA-64 architecture. Experimental results on a small number of loops show significant performance improvements over existing modulo scheduling methods that software pipeline a loop nest from the innermost loop.


title: Probabilistic Predicate-Aware Modulo Scheduling

authors:
Mikhail Smelyanskiy
Scott A. Mahlke
Edward S. Davidson

abstract: Predicated execution enables the removal of branches by converting segments of branching code into sequences of conditional operations. An important side effect of this transformation is that the compiler must unconditionally assign resources to predicated operations. However, a resource is only put to productive use when the predicate associated with an operation evaluates to True. To reduce this superfluous commitment of resources, we propose probabilistic predicate-aware scheduling to assign multiple operations to the same resource at the same time, thereby over-subscribing its use. Assignment is performed in a probabilistic manner using a combination of predicate profile information and predicate analysis aimed at maximizing the benefits of over-subscription in view of the expected degree of conflict. Conflicts occur when two or more operations assigned to the same resource have their predicates evaluate to True. A predicate-aware VLIW processor pipeline detects such conflicts, recovers, and correctly executes the conflicting operations. By increasing the effective throughput of a fixed set of resources, probabilistic predicate-aware scheduling provided an average of 20% performance gain in our evaluations on a 4-issue processor, and 8% gain on a 6-issue processor.


title: Custom Data Layout for Memory Parallelism

authors:
Byoungro So
Mary W. Hall
Heidi E. Ziegler

abstract: We describe a generalized approach to deriving a custom data layout in multiple memory banks for array-based computations, to facilitate high-bandwidth parallel memory accesses in modern architectures, where multiple memory banks can simultaneously feed one or more functional units. We do not use a fixed data layout, but rather select application-specific layouts according to access patterns in the code. A unique feature of this approach is its flexibility in the presence of code reordering transformations, such as the loop nest transformations commonly applied to array-based computations. We have implemented this algorithm in the DEFACTO system, a design environment for automatically mapping C programs to hardware implementations for FPGA-based systems. We present experimental results for five multimedia kernels that demonstrate the benefits of this approach. Our results show that custom data layout yields results as good as, or better than, naive or fixed cyclic layouts, and is significantly better for certain access patterns and in the presence of code reordering transformations. When used in conjunction with unrolling loops in a nest to expose instruction-level parallelism, we observe greater than a 75% reduction in the number of memory access cycles and speedups ranging from 3.96 to 46.7 for 8 memories, as compared to using a single memory with no unrolling.


title: Extending Path Profiling across Loop Backedges and Procedure Boundaries

authors:
Sriraman Tallam
Xiangyu Zhang
Rajiv Gupta

abstract: Since their introduction, path profiles have been used to guide the application of aggressive code optimizations and performing instruction scheduling. However, for optimization and scheduling, it is often desirable to obtain frequency counts of paths that extend across loop iterations and cross procedure boundaries. These longer paths, referred to as interesting paths, account for over 75% of the flow in a subset of SPEC benchmarks. Although the frequency counts of interesting paths can be estimated from path profiles, the degree of imprecision of these estimates is very high. We extend Ball Larus (BL) paths to create slightly longer overlapping paths and develop an instrumentation algorithm to collect their frequencies. While these paths are slightly longer than BL paths, they enable very precise estimation of frequencies of potentially much longer interesting paths. Our experiments show that the average cost of collecting frequencies of overlapping paths is 86.8%, which is 4.2 times that of BL paths. However, while the average imprecision in estimated total flow of interesting paths derived from BL path frequencies ranges from -38 % to +138 %, the average imprecision inflow estimates derived from overlapping path frequencies ranges only from -4% to +8%.


title: Exploring the Performance Potential of Itanium® Processors with ILP-based Scheduling

abstract: HP and Intel's Itanium processor family (IPF) is considered as one of the most challenging processor architectures to generate code for. During global instruction scheduling, the compiler must balance the use of strongly interdependent techniques like code motion, speculation and predication. A too conservative application of these features can lead to empty execution slots, contrary to the EPIC philosophy. But overuse can cause resource shortage which spoils the benefit. We tackle this problem using integer linear programming (ILP), a proven standard optimization method. Our ILP model comprises global, partial-ready code motion with automated generation of compensation code as well as vital IPF features like control/data speculation and predication. The ILP approach can-with some restrictions-resolve the interdependences between these decisions and deliver the global optimum. This promises a speedup for compute-intensive applications as well as some theoretically funded insights into the potential of the architecture. Experiments with several hot functions from the SPEC benchmarks show substantial improvements: our postpass optimizer reduces the schedule lengths produced by Intel's compiler by about 20-40%. The resulting speedup of these routines is 16% on average.


title: The Accuracy of Initial Prediction in Two-Phase Dynamic Binary Translators

authors:
Youfeng Wu
Maurício Breternitz Jr.
Justin Quek
Orna Etzion
Jesse Fang

abstract: Dynamic binary translators use a two-phase approach to identify and optimize frequently executed code dynamically. In the first step (profiling phase), blocks of code are interpreted or quickly translated to collect execution frequency information for the blocks. In the second phase (optimization phase), frequently executed blocks are grouped into regions and advanced optimizations are applied on them. This approach implicitly assumes that the initial profile of each block is representative of the block throughout its lifetime. We investigate the ability of the initial profile to predict the average program behavior. We compare the predicted behavior of varying lengths of the initial execution with the average program behavior for the whole program execution, and use the prediction from the training input as the reference. Our result indicates that, for the SPEC2000 benchmarks, even very short initial profiles have comparable prediction accuracy to the traditional profile-guided optimizations using the training input, although the initial profile is inadequate for predicting loop trip count information for some integer programs and several benchmarks can benefit from phase-awareness during dynamic binary translation.


title: Exposing Memory Access Regularities Using Object-Relative Memory Profiling

authors:
Qiang Wu
Artem Pyatakov
Alexey Spiridonov
Easwaran Raman
Douglas W. Clark
David I. August

abstract: Memory profiling is the process of characterizing a program's memory behavior by observing and recording its response to specific input sets. Relevant aspects of the program's memory behavior may then be used to guide memory optimizations in an aggressively optimizing compiler. In general, memory access behavior has eluded meaningful characterization because of confounding artifacts from memory allocators, linker data layout, and OS memory management. Since these artifacts may change from run to run, memory access patterns may appear different in each run even for the same input set. Worse, regular memory access behavior such as linked list traversals appear to have no structure. We present object-relative translation and decomposition techniques to eliminate these artifacts and to expose previously obscured memory access patterns. To demonstrate the potential of these ideas, we implement two different memory profilers targeted at different sets of applications. These profilers outperform the existing ones in terms of profile size and useful information per byte of data. The first profiler is a lossless profiler, called WHOMP, which uses object-relativity to achieve a 22% better compression than the previously best known scheme. The second profiler, called LEAP, uses lossy compression to get highly compact profiles while providing useful information to the targeted applications. LEAP correctly characterizes the memory alias rates for 56% more instruction pairs than the previously best known scheme with a practical running time.


title: Compiler Optimization of Memory-Resident Value Communication Between Speculative Threads

authors:
Antonia Zhai
Christopher B. Colohan
J. Gregory Steffan
Todd C. Mowry

abstract: Efficient inter-thread value communication is essential for improving performance in thread-level speculation (TLS). Although several mechanisms for improving value communication using hardware support have been proposed, there is relatively little work on exploiting the potential of compiler optimization. Building on recent research on compiler optimization of scalar value communication between speculative threads, we propose compiler techniques for the optimization of memory-resident values. In TLS, data dependences through memory-resident values are tracked by the underlying hardware and preserved by re-executing any speculative thread that violates a dependence; however, re-execution incurs a large performance penalty and should be used only to resolve data dependences that are infrequent. In contrast, value communication for frequently-occurring data dependences must be very efficient. We propose using the compiler to first identify frequently-occurring memory-resident data dependences, then insert synchronization for communicating values to preserve these dependences. We find that by synchronizing frequently-occurring data dependences we can significantly improve the efficiency of parallel execution. A comparison between compiler-inserted and hardware-inserted memory synchronization reveals that the two techniques are complementary, with each technique benefitting different benchmarks.


title: Multicores from the Compiler's Perspective: A Blessing or a Curse?

abstract: With all major processor vendors building multiple processor cores on a single chip, multicores is the next tour-de-force in computer architecture. The ability to parallelize and execute applications on multiple cores provides an opportunity to get the processor performance back on track with the Moore's law. In this article the author analyzes the seismic changes in computer architecture that lead to multicores and their impact on compilation. Next, we review different facets of the multicore compiler problem using three case studies - coarse grain parallelism from the perspective of the SUIF parallelizing compiler, instruction level parallelism with the RAW ILP compiler, and language exposed parallelism using the StreamIt language and compiler. Finally, we attempt to answer the ultimate question: with multicores, can we finally realize the dream that has eluded us for so long?.


title: Collecting and Exploiting High-Accuracy Call Graph Profiles in Virtual Machines

authors:
Matthew Arnold
David Grove

abstract: Due to the high dynamic frequency of virtual method calls in typical object-oriented programs, feedback-directed devirtualization and inlining is one of the most important optimizations performed by high-performance virtual machines. A critical input to effective feedback-directed inlining is an accurate dynamic call graph. In a virtual machine, the dynamic call graph is computed online during program execution. Therefore, to maximize overall system performance, the profiling mechanism must strike a balance between profile accuracy, the speed at which the profile becomes available to the optimizer, and profiling overhead. This paper introduces a new low-overhead sampling-based technique that rapidly converges on a high-accuracy dynamic call graph. We have implemented the technique in two high-performance virtual machines: Jikes RVM and J9. We empirically assess our profiling technique by reporting on the accuracy of the dynamic call graphs it computes and by demonstrating that increasing the accuracy of the dynamic call graph results in more effective feedback-directed inlining.


title: Context Threading: A Flexible and Efficient Dispatch Technique for Virtual Machine Interpreters

authors:
Marc Berndl
Benjamin Vitale
Mathew Zaleski
Angela Demke Brown

abstract: Direct-threaded interpreters use indirect branches to dispatch bytecodes, but deeply-pipelined architectures rely on branch prediction for performance. Due to the poor correlation between the virtual program's control flow and the hardware program counter, which we call the context problem, direct threading's indirect branches are poorly predicted by the hardware, limiting performance. Our dispatch technique, context threading, improves branch prediction and performance by aligning hardware and virtual machine state. Linear virtual instructions are dispatched with native calls and returns, aligning the hardware and virtual PC. Thus, sequential control flow is predicted by the hardware return stack. We convert virtual branching instructions to native branches, mobilizing the hardware's branch prediction resources. We evaluate the impact of context threading on both branch prediction and performance using interpreters for Java and OCaml on the Pentium and PowerPC architectures. On the Pentium IV our technique reduces mean mispredicted branches by 95%. On the PowerPC, it reduces mean branch stall cycles by 75% for OCaml and 82% for Java. Due to reduced branch hazards, context threading reduces mean execution time by 25% for Java and by 19% and 37% for OCaml on the P4 and PPC970, respectively. We also combine context threading with a conservative inlining technique and find its performance comparable to that of selective inlining.


title: Practical Path Profiling for Dynamic Optimizers

authors:
Michael D. Bond
Kathryn S. McKinley

abstract: Modern processors are hungry for instructions. To satisfy them, compilers need to find and optimize execution paths across multiple basic blocks. Path profiles provide this context, but their high overhead has so far limited their use by dynamic compilers. We present new techniques for low overhead online practical path profiling (PPP). Following targeted path profiling (TPP), PPP uses an edge profile to simplify path profile instrumentation (profile-guided profiling). PPP improves over prior work by (1) reducing the amount of profiling instrumentation on cold paths and paths that the edge profile predicts well and (2) reducing the cost of the remaining instrumentation. Experiments in an ahead-of-time compiler perform edge profile-guided inlining and unrolling prior to path profiling instrumentation. These transformations are faithful to staged optimization, and create longer, harder to predict paths. We introduce the branch-flow metric to measure path flow as a function of branch decisions, rather than weighting all paths equally as in prior work. On SPEC2000, PPP maintains high accuracy and coverage, but has only 5% overhead on average (ranging from -3% to 13%), making it appealing for use by dynamic compilers.