title: Maintaining Consistency and Bounding Capacity of Software Code Caches

authors:
Derek Bruening
Saman P. Amarasinghe

abstract: Software code caches are becoming ubiquitous, in dynamic optimizers, runtime tool platforms, dynamic translators fast simulators and emulators, and dynamic compilers. Caching frequently executed fragments of code provides significant performance boosts, reducing the overhead of translation and emulation and meeting or exceeding native performance in dynamic optimizers. One disadvantage of caching, memory expansion, can sometimes be ignored when executing a single application. However, as optimizers and translators are applied more and more in production systems, the memory expansion from running multiple applications simultaneously becomes problematic. A second drawback to caching is the added requirement of maintaining consistency between the code cache and the original code. On architectures like IA-32 that do not require explicit application actions when modifying code, detecting code changes is challenging. Again, consistency can be ignored for certain sets of applications, but as caching systems scale up to executing large, modern, complex programs, consistency becomes critical. This paper presents efficient schemes for keeping a software code cache consistent and for dynamically bounding code cache size to match the current working set of the application. These schemes are evaluated in the DynamoRIO runtime code manipulation system, and operate on stock hardware in the presence of multiple threads and dynamic behavior, including dynamically-loaded, generated, and even modified code.


venue: cgo

title: Automatic Generation of High-Performance Trace Compressors

authors:
Martin Burtscher
Nana B. Sam

abstract: Program execution traces are frequently used in industry and academia. Yet, most trace-compression algorithms have to be re-implemented every time the trace format is changed, which takes time, is error prone, and often results in inefficient solutions. This paper describes and evaluates TCgen, a too that automatically generates portable, customized, high-performance trace compressors. All the user has to do is provide a description of the trace format and select one or more predictors to compress the fields in the trace records. TCgen translates this specification into C source code and optimizes it for the specified trace format and predictor algorithms. On average, the generated code is faster and compresses better than the six other compression algorithms we have tested. For example, a comparison with SBC, one of the best trace-compression algorithms in the current literature, shows that TCgen's synthesized code compresses SPECcpu2000 address traces 23% more, decompresses them 24% faster, and compresses them 1029% faster.


title: Combining Models and Guided Empirical Search to Optimize for Multiple Levels of the Memory Hierarchy

authors:
Chun Chen
Jacqueline Chame
Mary W. Hall

abstract: This paper describes an algorithm for simultaneously optimizing across multiple levels of the memory hierarchy for dense-matrix computations. Our approach combines compiler models and heuristics with guided empirical search to take advantage of their complementary strengths. The models and heuristics limit the search to a small number of candidate implementations, and the empirical results provide the most accurate information to the compiler to select among candidates and tune optimization parameter values. We have developed an initial implementation and applied this approach to two case studies, matrix multiply and Jacobi relaxation. For matrix multiply, our results on two architectures, SGI R10000 and Sun UltraSparc IIe, outperform the native compiler, and either outperform or achieve comparable performance as the ATLAS self-tuning library and the hand-tuned vendor BLAS library. Jacobi results also substantially outperform the native compilers.


title: Optimizing Address Code Generation for Array-Intensive DSP Applications

authors:
Guilin Chen
Mahmut T. Kandemir

abstract: The application code size is a critical design factor for many embedded systems. Unfortunately, most available compilers optimize primarily for speed of execution rather than code density. As a result, the compiler-generated code can be much larger than necessary. In particular, in the DSP domain, the past research found that optimizing address code generation can be very important since address code can account for over 50% of all program bits. This paper presents a compiler-directed scheme to minimize the number of instructions to be generated to manipulate address registers found in DSP architectures. As opposed to most of the prior techniques that attempt to reduce the number of such instructions through careful address register assignment, this paper proposes modifying loop access patterns in array-intensive signal processing applications. In addition, it demonstrates how the proposed scheme can cooperate with a data layout optimizer for increasing its benefits further. We also discuss how optimizations that target effective address code generation can conflict with data locality-enhancing transformations. We evaluate the proposed approach using twelve array-intensive embedded applications. Our experimental results indicate that the proposed approach not only leads to significant reductions in code size but also outperforms prior efforts on reducing code size of array-intensive DSP applications.


title: A General Compiler Framework for Speculative Optimizations Using Data Speculative Code Motion

authors:
Xiaoru Dai
Antonia Zhai
Wei-Chung Hsu
Pen-Chung Yew

abstract: Data speculative optimization refers to code transformations that allow load and store instructions to be moved across potentially dependent memory operations. Existing research work on data speculative optimizations has mainly focused on individual code transformation. The required speculative analysis that identifies data speculative optimization opportunities and the required recovery code generation that guarantees the correctness of their execution are handled separately for each optimization. This paper proposes a new compiler framework to facilitate the design and implementation of general data speculative optimizations such as dead store elimination, redundancy elimination, copy propagation, and code scheduling. This framework allows different data speculative optimizations to share the followings: (i) a speculative analysis mechanism to identify data speculative optimization opportunities by ignoring low probability data dependences from optimizations, and (ii) a recovery code generation mechanism to guarantee the correctness of the data speculative optimizations. The proposed recovery code generation is based on data speculative code motion (DSCM) that uses code motion to facilitate a desired transformation. Based on the position of the moved instruction, recovery code can be generated accordingly. The proposed framework greatly simplifies the task of incorporating data speculation into non-speculative optimizations by sharing the recovery code generation and the speculative analysis. We have implemented the proposed framework in the ORC 2.1 compiler and demonstrated its effectiveness on SPEC2000 benchmark programs.


title: Performance of Runtime Optimization on BLAST

authors:
Abhinav Das
Jiwei Lu
Howard Chen
Jinpyo Kim
Pen-Chung Yew
Wei-Chung Hsu
Dong-yuan Chen

abstract: Optimization of a real world application BLAST is used to demonstrate the limitations of static and profile-guided optimizations and to highlight the potential of runtime optimization systems. We analyze the performance profile of this application to determine performance bottlenecks and evaluate the effect of aggressive compiler optimizations on BLAST. We find that applying common optimizations (e.g. O3) can degrade performance. Profile guided optimizations do not show much improvement across the board, as current implementations do not address critical performance bottlenecks in BLAST. In some cases, these optimizations lower performance significantly due to unexpected secondary effects of aggressive optimizations. We also apply runtime optimization to BLAST using the ADORE framework. ADORE is able to detect performance bottlenecks and deploy optimizations resulting in performance gains up to 58% on some queries using data cache prefetching.


title: Practical and Accurate Low-Level Pointer Analysis

authors:
Bolei Guo
Matthew J. Bridges
Spyridon Triantafyllis
Guilherme Ottoni
Easwaran Raman
David I. August

abstract: Pointer analysis is traditionally performed once, early in the compilation process, upon an intermediate representation (IR) with source-code semantics. However, performing pointer analysis only once at this level imposes a phase-ordering constraint, causing alias information to become stale after subsequent code transformations. Moreover, high-level pointer analysis cannot be used at link time or run time, where the source code is unavailable. This paper advocates performing pointer analysis on a low-level intermediate representation. We present the first context-sensitive and partially flow-sensitive points-to analysis designed to operate at the assembly level. As we will demonstrate, low-level pointer analysis can be as accurate as high-level analysis. Additionally, our low-level pointer analysis also enables a quantitative comparison of propagating high-level pointer analysis results through subsequent code transformations, versus recomputing them at the low level. We show that, for C programs, the former practice is considerably less accurate than the latter.


title: Virtual Machine Learning: Thinking like a Computer Architect

abstract: Summary form only given. Modern commercial software is written in languages that execute on a virtual machine. Such languages often have dynamic features that require rich runtime support and preclude traditional static optimization. Implementations of these languages have employed dynamic optimization strategies to achieve significant performance improvements. In this paper the author describes some of these strategies and demonstrates their effectiveness. The author then argues that further advances in this field are being hindered by our bias toward adapting traditional static optimization techniques. Instead, we need to think more like a computer architect to create new approaches to optimization in virtual machines.


title: Effective Adaptive Computing Environment Management via Dynamic Optimization

authors:
Shiwen Hu
Madhavi Gopal Valluri
Lizy Kurian John

abstract: To minimize the surging power consumption of microprocessors, adaptive computing environments (ACEs) where microarchitectural resources can be dynamically tuned to match a program's runtime requirement and characteristics are becoming increasingly common. Adaptive computing environments usually have multiple configurable hardware units, necessitating exploration of a large number of combinatorial configurations in order to identify the most energy-efficient configuration. In this paper, we propose a scheme for efficient management of multiple configurable units, utilizing the inherent capabilities of dynamic optimization systems. Most dynamic optimizers typically detect dominant code regions (hotspots). We develop an ACE management scheme where hotpot boundaries are used for phase detection and adaptation. Since hotspots are of variable sizes and are often nested, program phase behavior which is hierarchical in nature is automatically captured in this technique. To demonstrate the usefulness and effectiveness of our framework, we use the proposed framework to dynamically adapt the sizes of L1 data and L2 caches that have different reconfiguration latencies and overheads. Our technique reduces L1D and L2 cache energy consumption by 47% and 58%, while a popular previously proposed technique only achieves reduction of 32% and 52% respectively.


title: A Progressive Register Allocator for Irregular Architectures

authors:
David Koes
Seth Copen Goldstein

abstract: Register allocation is one of the most important optimizations a compiler performs. Conventional graph-coloring based register allocators are fast and do well on regular, RISC-like, architectures, but perform poorly on irregular, CISC-like, architectures with few registers and non-orthogonal instruction sets. At the other extreme, optimal register allocators based on integer linear programming are capable of fully modeling and exploiting the peculiarities of irregular architectures but do not scale well. We introduce the idea of a progressive allocator. A progressive allocator finds an initial allocation of quality comparable to a conventional allocator, but as more time is allowed for computation the quality of the allocation approaches optimal. This paper presents a progressive register allocator which uses a multi-commodity network flow model to elegantly represent the intricacies of irregular architectures. We evaluate our allocator as a substitute for gcc 's local register allocation pass.


title: Optimizing Sorting with Genetic Algorithms

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

abstract: The growing complexity of modern processors has made the generation of highly efficient code increasingly difficult. Manual code generation is very time consuming, but it is often the only choice since the code generated by today's compiler technology often has much lower performance than the best hand-tuned codes. A promising code generation strategy, implemented by systems like ATLAS, FFTW, and SPIRAL, uses empirical search to find the parameter values of the implementation, such as the tile size and instruction schedules, that deliver near-optimal performance for a particular machine. However, this approach has only proven successful on scientific codes whose performance does not depend on the input data. In this paper we study machine learning techniques to extend empirical search to the generation of sorting routines, whose performance depends on the input characteristics and the architecture of the target machine. We build on a previous study that selects a "pure" sorting algorithm at the outset of the computation as a function of the standard deviation. The approach discussed in this paper uses genetic algorithms and a classifier system to build hierarchically-organized hybrid sorting algorithms capable of adapting to the input data. Our results show that such algorithms generated using the approach presented in this paper are quite effective at taking into account the complex interactions between architectural and input data characteristics and that the resulting code performs significantly better than conventional sorting implementations and the code generated by our earlier study. In particular, the routines generated using our approach perform better than all the commercial libraries that we tried including IBM ESSL, INTEL MKL and the C++ STL The best algorithm we have been able to generate is on the average 26% and 62% faster than the IBM ESSL in an IBM Power 3 and IBM Power 4, respectively.


title: Phase-Aware Remote Profiling

authors:
Priya Nagpurkar
Chandra Krintz
Timothy Sherwood

abstract: Recent advances in networking and embedded device technology have made the vision of ubiquitous computing a reality; users can access the Internet's vast offerings anytime and anywhere. Moreover, battery-powered devices such as personal digital assistants and Web-enabled mobile phones have successfully emerged as new access points to the world's digital, infrastructure. This ubiquity offers a new opportunity for software developers: users can now participate in the software development, optimization, and evolution process while they use their software. Such participation requires effective techniques for gathering profile information from remote, resource-constrained devices. Further, these techniques must be unobtrusive and transparent to the user; profiles must be gathered using minimal computation, communication, and power. Toward this end, we present a flexible hardware-software scheme for efficient remote profiling. We rely on the extraction of meta information from executing programs in the form of phases, and then use this information to guide intelligent online sampling and to manage the communication of those samples. Our results indicate that phase-based remote profiling can reduce the communication, computation, and energy consumption overheads by 50-75% over random and periodic sampling.


title: Compile-Time Concurrent Marking Write Barrier Removal

authors:
V. Krishna Nandivada
David Detlefs

abstract: Garbage collectors incorporating concurrent marking to cope with large live data sets and stringent pause time constraints have become common in recent years. The snapshot-at-the-beginning style of concurrent marking has several advantages over the incremental update alternative, but one main disadvantage: it requires the mutator to execute a significantly more expensive write barrier. This paper demonstrates that a large fraction of these write barriers are unnecessary, and may be eliminated by static analysis.


title: Sentinel PRE: Hoisting beyond Exception Dependency with Dynamic Deoptimization

authors:
Rei Odaira
Kei Hiraki

abstract: Many excepting instructions cannot be removed by existing partial redundancy elimination (PRE) algorithms because the ordering constraints must be preserved between the excepting instructions, which we call exception dependencies. In this work, we propose Sentinel PRE, a PRE algorithm that overcomes exception dependencies and retains program semantics. Sentinel PRE first hoists excepting instructions without considering exception dependencies, and then detects exception reordering by fast analysis. If an exception occurs at a reordered instruction, it deoptimizes the code into the one before hoisting. Since we rarely encounter exceptions in real programs, the optimized code is executed in almost all cases. We implemented Sentinel PRE in a Java just-in-time compiler and conducted experiments. The results show 9.0% performance improvement in the LU program in the Java Grande Forum Benchmark Suite.


title: Compiler Managed Dynamic Instruction Placement in a Low-Power Code Cache

authors:
Rajiv A. Ravindran
Pracheeti D. Nagarkar
Ganesh S. Dasika
Eric D. Marsman
Robert M. Senger
Scott A. Mahlke
Richard B. Brown

abstract: Modern embedded microprocessors use low power on-chip memories called scratch-pad memories to store frequently executed instructions and data. Unlike traditional caches, scratch-pad memories lack the complex tag checking and comparison logic, thereby proving to be efficient in area and power. In this work, we focus on exploiting scratch-pad memories for storing hot code segments within an application. Static placement techniques focus on placing the most frequently executed portions of programs into the scratch-pad. However, static schemes are inherently limited by not allowing the contents of the scratch-pad memory to change at run time. In a large fraction of applications, the instruction memory footprints exceed the scratch-pad memory size, thereby limiting the usefulness of the scratch-pad. We propose a compiler managed dynamic placement algorithm, wherein multiple hot code sequences, or traces, are overlapped with each other in the scratch-pad memory at different points in time during execution. Special copy instructions are provided to copy the traces into the scratch-pad memory at run-time. Using a power estimate, the compiler initially selects the most frequent traces in an application for relocation into the scratch-pad memory. Through iterative code motion and redundancy elimination, copy instructions are inserted in infrequently executed regions of the code. For a 64-byte code cache, the compiler managed dynamic placement achieves an average of 64% energy improvement over the static solution in a low-power embedded microcontroller.


title: SWIFT: Software Implemented Fault Tolerance

authors:
George A. Reis
Jonathan Chang
Neil Vachharajani
Ram Rangan
David I. August

abstract: To improve performance and reduce power, processor designers employ advances that shrink feature sizes, lower voltage levels, reduce noise margins, and increase clock rates. However, these advances make processors more susceptible to transient faults that can affect correctness. While reliable systems typically employ hardware techniques to address soft-errors, software techniques can provide a lower-cost and more flexible alternative. This paper presents a novel, software-only, transient-fault-detection technique, called SWIFT. SWIFT efficiently manages redundancy by reclaiming unused instruction-level resources present during the execution of most programs. SWIFT also provides a high level of protection and performance with an enhanced control-flow checking mechanism. We evaluate an implementation of SWIFT on an Itanium 2 which demonstrates exceptional fault coverage with a reasonable performance cost. Compared to the best known single-threaded approach utilizing an ECC memory system, SWIFT demonstrates a 51% average speedup.


title: Superword-Level Parallelism in the Presence of Control Flow

authors:
Jaewook Shin
Mary W. Hall
Jacqueline Chame

abstract: In this paper, we describe how to extend the concept of superword-level parallelization (SLP), used for multimedia extension architectures, so that it can be applied in the presence of control flow constructs. Superword-level parallelization involves identifying scalar instructions in a large basic block that perform the same operation, and, if dependences do not prevent it, combining them into a superword operation on a multi-word object. A key insight is that we can use techniques related to optimizations for architectures supporting predicated execution, even for multimedia ISAs that do not provide hardware predication. We derive large basic blocks with predicated instructions to which SLP can be applied. We describe how to minimize overheads for superword predicates and re-introduce control flow for scalar operations. We discuss other extensions to SLP to address common features of real multimedia codes. We present automatically-generated performance results on 8 multimedia codes to demonstrate the power of this approach. We observe speedups ranging from 1.97X to 15.07X as compared to both sequential execution and SLP alone.


title: Predicting Unroll Factors Using Supervised Classification

authors:
Mark Stephenson
Saman P. Amarasinghe

abstract: Compilers base many critical decisions on abstracted architectural models. While recent research has shown that modeling is effective for some compiler problems, building accurate models requires a great deal of human time and effort. This paper describes how machine learning techniques can be leveraged to help compiler writers model complex systems. Because learning techniques can effectively make sense of high dimensional spaces, they can be a valuable tool for clarifying and discerning complex decision boundaries. In this work we focus on loop unrolling, a well-known optimization for exposing instruction level parallelism. Using the Open Research Compiler as a testbed, we demonstrate how one can use supervised learning techniques to determine the appropriateness of loop unrolling. We use more than 2,500 loops - drawn from 72 benchmarks - to train two different learning algorithms to predict unroll factors (i.e., the amount by which to unroll a loop) for any novel loop. The technique correctly predicts the unroll factor for 65% of the loops in our dataset, which leads to a 5% overall improvement for the SPEC 2000 benchmark suite (9% for the SPEC 2000 floating point benchmarks).


title: Automatically Reducing Repetitive Synchronization with a Just-in-Time Compiler for Java

authors:
Mark G. Stoodley
Vijay Sundaresan

abstract: We describe an automatic technique to remove repetitive synchronization in Java/spl trade/ programs by removing selected MONITORENTER/EXIT operations. Once these operations are removed, parts of a method that were not originally locked become protected by a lock. If it is unsafe to synchronize the code between the original locked regions, however, the code is not transformed. Scalability is also protected by not allowing a lock to be held for a significantly longer time than it would be held in the original program code. Our base algorithm improved the throughput of the industry-standard SPECjbb2000 benchmark by 2% to 5% for three different platforms. We also describe an extension to our algorithm to better handle virtual calls, which are prevalent in Java code, and this extension provides up to a further 5% improvement. Our computationally efficient algorithm was implemented and evaluated in a production Just-In-Time (JIT) compiler.


title: A Programmable Hardware Path Profiler

authors:
Kapil Vaswani
Matthew J. Thazhuthaveetil
Y. N. Srikant

abstract: For aggressive path-based program optimizations to be profitable in cost-sensitive environments, accurate path profiles must be available at low overheads. In this paper, we propose a low-overhead, non-intrusive hardware path profiling scheme that can be programmed to detect several types of paths including acyclic, intra-procedural paths, paths for a whole program path and extended paths. The profiler consists of a path stack, which detects paths and generates a sequence of path descriptors using branch information from the processor pipeline, and a hot path table that collects a profile of hot paths for later use by a program optimizer. With assistance from the processor's event detection logic, our profiler can track a host of architectural metrics along paths, enabling context-sensitive performance monitoring and bottleneck analysis. We illustrate the utility of our scheme by associating paths with a power metric that estimates power consumption in the cache hierarchy caused by instructions along the path. Experiments using programs from the SPEC CPU2000 benchmark suite show that our path profiler, occupying 7KB of hardware real-estate, collects accurate path profiles (average overlap of 88% with a perfect profile) at negligible execution time overheads (0.6% on average).


title: Efficient SIMD Code Generation for Runtime Alignment and Length Conversion

authors:
Peng Wu
Alexandre E. Eichenberger
Amy Wang

abstract: When generating codes for today's multimedia extensions, one of the major challenges is to deal with memory alignment issues. While hand programming still yields best performing SIMD codes, it is both time consuming and error prone. Compiler technology has greatly improved, including techniques that simdize loops with misaligned accesses by automatically rearranging misaligned memory streams in registers. Current techniques are applicable to runtime alignments, but they aggressively reduce the alignment overhead only when all alignments are known at compile time. This paper presents two major enhancements to the state of the art, improving both performance and coverage. First, we propose a novel technique to simdize loops with runtime alignment nearly as efficiently as those with compile-time misalignment. Runtime alignment is pervasive in real applications because it is either part of the algorithms, or it is an artifact of the compiler's inability to extract accurate alignment information from complex applications. Second, we incorporate length conversion operations, e.g., conversions between data of different sizes, into the alignment handling framework. Length conversions are pervasive in multimedia applications where mixed integer types are often used. Supporting length conversion can greatly improve the coverage of simdizable loops. Experimental results indicate that our runtime alignment technique achieves a 19% to 32% speedup increase over prior art for a benchmark stressing the impact of misaligned data. We also demonstrate speedup factors of up to 8.11 for real benchmarks over sequential execution.


title: Building Intrusion-Tolerant Secure Software

authors:
Tao Zhang
Xiaotong Zhuang
Santosh Pande

abstract: In this work, we develop a secret sharing based compiler solution to achieve confidentiality, integrity and availability (intrusion tolerance) of critical data together, rather than tackling them one by one as in previous approaches. Under our scheme, the compiler automatically identifies some critical data values, whereas the user specifies some others. The compiler generates code for scattering/assembling and verifying of those critical data values using secret sharing scheme. In this way, we achieve data confidentiality and integrity. We also provide mechanisms to gracefully recover upon data tampering, achieving intrusion tolerance. The implementation of our secret sharing scheme is carefully crafted to achieve low overhead. We further propose several compiler optimizations such as secret-sharing-aware register allocation, rematerialization etc. to reduce the cost of secret sharing further, making our scheme a practical solution in a high performance system.


title: Model-Based Framework: An Approach for Profit-Driven Optimization

authors:
Min Zhao
Bruce R. Childers
Mary Lou Soffa

abstract: Although optimizations have been applied for a number of years to improve the performance of software, problems that have been long-standing remain, which include knowing what optimizations to apply and how to apply them. To systematically tackle these problems, we need to understand the properties of optimizations. In our current research, we are investigating the profitability property, which is useful for determining the benefit of applying an optimization. Due to the high cost of applying optimizations and then experimentally evaluating their profitability, we use an analytic model framework for predicting the profitability of optimizations. In this paper, we target scalar optimizations, and in particular, describe framework instances for partial redundancy elimination (PRE) and loop invariant code motion (LICM). We implemented the framework for both optimizations and compare profit-driven PRE and LICM with a heuristic-driven approach. Our experiments demonstrate that a model-based approach is effective and efficient in that it can accurately predict the profitability of optimizations with low overhead. By predicting the profitability using models, we can selectively apply optimizations. The model-based approach does not require tuning of parameters used in heuristic approaches and works well across different code contexts and optimizations.


title: Reactive Techniques for Controlling Software Speculation

authors:
Craig B. Zilles
Naveen Neelakantam

abstract: Aggressive software speculation holds significant potential, because it enables program transformations to reduce the program's critical path. Like any form of speculation, however, the key to software speculation is employing it only where it is likely to succeed. While mechanisms for controlling hardware speculation (e.g., saturating counters updated after each instance) are well understood, these techniques do not translate directly to software techniques because changing a speculation requires changing the code. As it stands, the dominant software speculation control technique, non-reactive profile-guided optimization, lacks the robustness to support aggressive speculation. The primary thesis of this paper is that software speculation can be made to be robust by adding a reactive controller that can dynamically adjust the speculation. We make two primary observations about such systems: 1) reactive control systems can select behaviors on which to speculate with performance that equals or exceeds self-training, and 2) such control systems are remarkably latency tolerant. Although reactivity is required, it can be done at a low frequency; latencies of hundreds of thousands, or even millions of cycles, can be tolerated for most actions. Together these two characteristics imply that robust aggressive software speculation is a realistic goal.


title: Using Machine Learning to Focus Iterative Optimization

authors:
Felix V. Agakov
Edwin V. Bonilla
John Cavazos
Björn Franke
Grigori Fursin
Michael F. P. O'Boyle
John Thomson
Marc Toussaint
Christopher K. I. Williams

abstract: Iterative compiler optimization has been shown to outperform static approaches. This, however, is at the cost of large numbers of evaluations of the program. This paper develops a new methodology to reduce this number and hence speed up iterative optimization. It uses predictive modelling from the domain of machine learning to automatically focus search on those areas likely to give greatest performance. This approach is independent of search algorithm, search space or compiler infrastructure and scales gracefully with the compiler optimization space size. Off-line, a training set of programs is iteratively evaluated and the shape of the spaces and program features are modelled. These models are learnt and used to focus the iterative optimization of a new program. We evaluate two learnt models, an independent and Markov model, and evaluate their worth on two embedded platforms, the Texas Instrument C67I3 and the AMD Au1500. We show that such learnt models can speed up iterative search on large spaces by an order of magnitude. This translates into an average speedup of 1.22 on the TI C6713 and 1.27 on the AMD Au1500 in just 2 evaluations.


title: Software-Based Transparent and Comprehensive Control-Flow Error Detection

authors:
Edson Borin
Cheng Wang
Youfeng Wu
Guido Araujo

abstract: Shrinking microprocessor feature size and growing transistor density may increase the soft-error rates to unacceptable levels in the near future. While reliable systems typically employ hardware techniques to address soft-errors, software-based techniques can provide a less expensive and more flexible alternative. This paper presents a control-flow error classification and proposes two new software-based comprehensive control-flow error detection techniques. The new techniques are better than the previous ones in the sense that they detect errors in all the branch-error categories. We implemented the techniques in our dynamic binary translator so that the techniques can be applied to existing x86 binaries transparently. We compared our new techniques with the previous ones and we show that our methods cover more errors while has similar performance overhead.


title: Thread-Shared Software Code Caches

authors:
Derek Bruening
Vladimir Kiriansky
Timothy Garnett
Sanjeev Banerji

abstract: Software code caches are increasingly being used to amortize the runtime overhead of dynamic optimizers, simulators, emulators, dynamic translators, dynamic compilers, and other tools. Despite the now-wide spread use of code caches, techniques for efficiently sharing them across multiple threads have not been fully explored. Some systems simply do not support threads, while others resort to thread-private code caches. Although thread-private caches are much simpler to manage, synchronize, and provide scratch space for, they simply do not scale when applied to many-threaded programs. Thread-shared code caches are needed to target server applications, which employ hundreds of worker threads all performing similar tasks. Yet, those systems that do share their code caches often have brute-force, inefficient solutions to the challenges of concurrent code cache access: a single global lock on runtime system code and suspension of all threads for any cache management action. This limits the possibilities for cache design and has performance problems with applications that require frequent cache invalidations to maintain cache consistency. In this paper, we discuss the design choices when building thread-shared code caches and enumerate the difficulties of thread-local storage, synchronization, trace building, in-cache lookup tables, and cache eviction. We present efficient solutions to these problems that both scale well and do not require thread suspension. We evaluate our results in DynamoRIO, an industrial-strength dynamic binary translation system, on real-world server applications. On these applications our thread-shared caches use an order of magnitude less memory and improve throughput by up to four times compared to thread-private caches.


title: Inline Analysis: Beyond Selection Heuristics

authors:
Dhruva R. Chakrabarti
Shin-Ming Liu

abstract: Research on procedure inlining has mainly focused on heuristics that decide whether inlining a particular call-site maximizes application performance. However, other equally important aspects of inline analysis such as call-site analysis order, indirect effects of inlining, and selection of the most profitable version of a procedure warrant more attention. This paper evaluates a number of different sequences in which call-sites are examined for inlining and shows that choosing the correct order is crucial to obtaining the best run-time performance. We then present a novel, work-list-based, and updated sequence that achieves the best results. While applying cross-module inline analysis on large applications with thousands of files and millions of lines of code, we separate the analysis from the transformation phase and allow the former to work solely on summary information in order to reduce compile-time and memory consumption. A focus of this paper is to enumerate the summaries that our compiler maintains, present a technique to compute the goodness factor on which the work-list sequence is based, and describe methods to continuously update the summaries as and when a call-site is accepted for inlining. We then introduce inline specialization, a new technique that facilitates inlining into call chains selectively. The power of inline specialization lies in its ability to choose the most profitable version of the called procedure without having to maintain multiple versions at any point of time. We discuss implementation of these techniques in the HPUX Itanium/spl reg/ production compiler and present experimental results showing that a dynamic work-list based analysis order, comprehensive summary updates, and inline specialization significantly improve performance of applications.


title: Java JNI Bridge: A Framework for Mixed Native ISA Execution

authors:
Miaobo Chen
Shalom Goldenberg
Suresh Srinivas
Valery Ushakov
Young Wang
Qi Zhang
Eric Lin
Yoav Zach

abstract: Managed runtime environments (MRTEs) such as the Java platform promise a cross platform "write once, deploy anywhere" mechanism. However, MRTE applications that contain native method calls are not seamlessly portable across platforms. In this paper, we describe a new approach to transparently run Java applications containing native method calls to one ISA (instruction set architecture) on a different ISA's Java platform. This approach operates within the same operating system process that executes the application but with the support of a dynamic translator. This paper describes the technical challenges and solutions of such an in-process implementation within a production Java Virtual Machine (JVM). These include interfacing the JVM with a dynamic translator to support native calls to a different ISA, pursuing a JVM-independent implementation, enhancing the dynamic translator to support shared libraries in addition to executables, marshalling arguments across ISA boundaries, and providing full support for all Java features such as multi-threading. The paper presents performance results for an end-user application, showing our approach to be 2-3 times faster than other approaches.


title: Compiler-directed Data Partitioning for Multicluster Processors

authors:
Michael L. Chu
Scott A. Mahlke

abstract: Multicluster architectures overcome the scaling problem of centralized resources by distributing the datapath, register file, and memory subsystem across multiple clusters connected by a communication network. Traditional compiler partitioning algorithms focus solely on distributing operations across the clusters to maximize instruction-level parallelism. The distribution of data objects is generally ignored. In this work, we examine explicit partitioning of data objects and its affects on operation partitioning. The partitioning of data objects must consider several factors: object size, access frequency/pattern, and dependence patterns between operations that manipulate the objects. This work proposes a compiler-directed approach to synergistically partition both data objects and computation across multiple clusters. First, a global view of the application determines the interaction between data memory objects and their associated computation. Next, data objects are partitioned across multiple clusters with knowledge of the associated computation required by the application. Finally, the resulting distribution of the data objects is relayed to a region-level computation partitioner, which carefully places computation operations in a performance-centric manner.


title: Tailoring Graph-coloring Register Allocation For Runtime Compilation

authors:
Keith D. Cooper
Anshuman Dasgupta

abstract: Just-in-time compilers are invoked during application execution and therefore need to ensure fast compilation times. Consequently, runtime compiler designers are averse to implementing compile-time intensive optimization algorithms. Instead, they tend to select faster but less effective transformations. In this paper, we explore this trade-off for an important optimization - global register allocation. We present a graph-coloring register allocator that has been redesigned for runtime compilation. Compared to Chaitin-Briggs (1994), a standard graph-coloring technique, the reformulated algorithm requires considerably less allocation time and produces allocations that are only marginally worse than those of Chaitin-Briggs. Our experimental results indicate that the allocator performs better than the linear-scan and Chaitin-Briggs allocators on most benchmarks in a runtime compilation environment. By increasing allocation efficiency and preserving optimization quality, the presented algorithm increases the suitability and profitability of a graph-coloring register allocation strategy for a runtime compiler.


title: Region Monitoring for Local Phase Detection in Dynamic Optimization Systems

authors:
Abhinav Das
Jiwei Lu
Wei-Chung Hsu

abstract: Dynamic optimization relies on phase detection for two important functions (1) To detect change in code working set and (2) To detect change in performance characteristics that can affect optimization strategy. Current prototype runtime optimization systems (J. Lu et al) compare aggregate metrics like CPI over fixed time intervals to detect a change in working set and a change in performance. While simple and cost-effective, these metrics are sensitive to sampling rate and interval size. A phase detection scheme that computes performance metrics by aggregating the performance of individually optimized regions can be misled by some regions impacting aggregate metrics adversely. In this paper, we investigate the benefits and limitations of using aggregate metrics for phase detection, which we call global phase detection (GPD). We present a new model to detect change in working set and propose that the scope of phase detection be limited to within the candidate regions for optimization. By associating phase detection to individual regions we can isolate the effects of regions that are inherently unstable. This approach, which we call local phase detection (LPD), shows improved performance on several benchmarks even when global phase detection is not able to detect stable phases.


title: A Cross-Architectural Interface for Code Cache Manipulation

authors:
Kim M. Hazelwood
Robert S. Cohn

abstract: Software code caches help amortize the overhead of dynamic binary transformation by enabling reuse of transformed code. Since code caches contain a potentially-altered copy of every instruction that executes, run-time access to a code cache can be a very powerful opportunity. Unfortunately, current research infrastructures lack the ability to model and direct code caching, and as a result, past code cache investigations have required access to the source code of the binary transformation system. This paper presents a code cache-aware interface to the pin dynamic instrumentation system. While a program executes, our interface allows a user to inspect the code cache, receive callbacks when key events occur, and manipulate the code cache contents at will. We demonstrate the utility of this interface on four architectures (IA32, EM64T, IPF, XScale) and present several tools written using our API. These tools include a self-modifying code handler, a two-phase instrumentation analyzer, a code cache visualizer, and custom code cache replacement policies. We also show that tools written using our interface have comparable performance to direct, source-level implementations. Both our interface and sample open-source tools that utilize the interface have been incorporated into the standard distribution of the pin dynamic instrumentation engine, which has been downloaded over 5,000 times in 18 months.


title: Practical Structure Layout Optimization and Advice

authors:
Robert Hundt
Sandya Mannarswamy
Dhruva R. Chakrabarti

abstract: With the delta between processor clock frequency and memory latency ever increasing and with the standard locality improving transformations maturing, compilers increasingly seek to modify an application's data layout to improve spatial and temporal locality and to reduce cache miss and page fault penalties. In this paper, we describe a practical implementation of the data layout optimizations structure splitting, structure peeling, structure field reordering and dead field removal, both for profile and non-profile based compilations. We demonstrate significant performance gains, but find that automatic transformations fail for a relatively high number of record types because of legality violations or profitability constraints. Additionally, we find a class of desirable transformations for which the framework cannot provide satisfying results. To address this issue, we complement the automatic transformations with an advisory tool. We reuse the compiler analysis done for automatic transformation and correlate its results with performance data collected during runtime for structure fields, such as data cache misses and latencies. We then use the compiler as a performance analysis and reporting tool and provide insight into how to layout structure types more efficiently.


title: 2D-Profiling: Detecting Input-Dependent Branches with a Single Input Data Set

authors:
Hyesoon Kim
M. Aater Suleman
Onur Mutlu
Yale N. Patt

abstract: Static compilers use profiling to predict run-time program behavior. Generally, this requires multiple input sets to capture wide variations in run-time behavior. This is expensive in terms of resources and compilation time. We introduce a new mechanism, 2D-profiling, which profiles with only one input set and predicts whether the result of the profile would change significantly across multiple input sets. We use 2D-profiling to predict whether a branch's prediction accuracy varies across input sets. The key insight is that if the prediction accuracy of an individual branch varies significantly over a profiling run with one input set, then it is more likely that the prediction accuracy of that branch varies across input sets. We evaluate 2D-profiling with the SPEC CPU 2000 integer benchmarks and show that it can identify input-dependent branches accurately.


title: Exhaustive Optimization Phase Order Space Exploration

authors:
Prasad A. Kulkarni
David B. Whalley
Gary S. Tyson
Jack W. Davidson

abstract: The phase-ordering problem is a long standing issue for compiler writers. Most optimizing compilers typically have numerous different code-improving phases, many of which can be applied in any order. These phases interact by enabling or disabling opportunities for other optimization phases to be applied. As a result, varying the order of applying optimization phases to a program can produce different code, with potentially significant performance variation amongst them. Complicating this problem further is the fact that there is no universal optimization phase order that will produce the best code, since the best phase order depends on the function being compiled, the compiler, and the target architecture characteristics. Moreover, finding the optimal optimization sequence for even a single function is hard as the space of attempted optimization phase sequences is huge and the interactions between different optimizations are poorly understood. Most previous studies performed to search for the most effective optimization phase sequence assume the optimization phase order search space to be extremely large, and hence consider exhaustive exploration of this space infeasible. In this paper we show that even though the attempted search space is extremely large, with careful and aggressive pruning it is possible to limit the actual search space with no loss of information so that it can be completely evaluated in a matter of minutes or a few hours for most functions. We were able to exhaustively enumerate all the possible function instances that can be produced by different phase orderings performed by our compiler for more than 98% of the functions in our benchmark suite. In this paper we describe the algorithm we used to make exhaustive search of the optimization phase order space possible. We then analyze this space to automatically calculate relationships between different phases. Finally, we show that the results of this analysis can be used to reduce the compilation time for a conventional batch compiler.


title: Selecting Software Phase Markers with Code Structure Analysis

authors:
Jeremy Lau
Erez Perelman
Brad Calder

abstract: Most programs are repetitive, where similar behavior can be seen at different execution times. Algorithms have been proposed that automatically group similar portions of a program's execution into phases, where samples of execution in the same phase have homogeneous behavior and similar resource requirements. In this paper, we present an automated profiling approach to identify code locations whose executions correlate with phase changes. These ''software phase markers" can be used to easily detect phase changes across different inputs to a program without hardware support. Our approach builds a combined hierarchical procedure call and loop graph to represent a program's execution, where each edge also tracks the max, average, and standard deviation in hierarchical execution variability on paths from that edge. We search this annotated call-loop graph for instructions in the binary that accurately identify the start of unique stable behaviors across different inputs. We show that our phase markers can be used to accurately partition execution into units of repeating homogeneous behavior by counting execution cycles and data cache hits. We also compare the use of our software markers to prior work on guiding data cache reconfiguration using data-reuse markers. Finally, we show that the phase markers can be used to partition the program's execution at code transitions to pick accurately simulation points for SimPoint. When simulation points are defined in terms of phase markers, they can potentially be re-used across inputs, compiler optimizations, and different instruction set architectures for the same source code.


title: Optimizing Dynamic Binary Translation for SIMD Instructions

authors:
Jianhui Li
Qi Zhang
Shu Xu
Bo Huang

abstract: Dynamic binary translation technology allows a program written for one architecture to be executed on a second architecture without recompiling the source code. Effective dynamic binary translation of SIMD (single instruction multiple data) instructions has become more and more important as SIMD extensions have gained popularity among general-purpose CPUs within the last decade. Many SIMD extensions allow an SIMD register to hold data of different types at different times. Supporting multiple data types within the same register complicates the task of a dynamic translator, which may or may not be able to determine the type of the register at translation time. We propose the SIMD data type tracking algorithm to translate the SIMD instructions and three algorithms to further optimize the translation. Our results show that the three optimizing algorithms give overall 3.89% performance improvement for SPEC2K INT benchmarks and 6.61%for SPEC2KFP benchmarks.


title: Data and Computation Transformations for Brook Streaming Applications on Multiprocessors

authors:
Shih-Wei Liao
Zhaohui Du
Gansha Wu
Guei-Yuan Lueh

abstract: Multicore processors are about to become prevalent in the PC world. Meanwhile, over 90% of the computing cycles are estimated to be consumed by streaming media applications (Rixner et al., 1998). Although stream programming exposes parallelism naturally, we found that achieving high performance on multiprocessors is challenging. Therefore, we develop a parallel compiler for the Brook streaming language with aggressive data and computation transformations. First, we formulate fifteen Brook stream operators in terms of systems of inequalities. Our compiler optimizes the modeled operators to improve memory footprint and performance. Second, the stream computation including both kernels and operators is mapped to the affine partitioning model by modeling each kernel as an implicit loop nest over stream elements. Note that our general abstraction is not limited to Brook. Our modeling and transformations yield high performance on uniprocessors as well. The geometric mean of speedups is 4.7 on ten streaming applications on a Xeon. On multiprocessors, we show that exploiting the standard intra-kernel data parallelism is inferior to our general modeling. The former yields a speedup of 1.5 for ten applications on a 4-way Xeon, while the latter achieves a speedup of 6.4 over the same baseline. We show that our compiler effectively reduces memory footprint, exploits parallelism, and circumvents phase-ordering issues.


title: Post Register Allocation Spill Code Optimization

authors:
Christopher Lupo
Kent D. Wilken

abstract: A highly optimized register allocator should provide an efficient placement of save/restore code for procedures that contain calls. This paper presents a new approach to placing callee-saved save and restore instructions that generalizes Chow's shrink-wrapping technique (Chow, 1988). An efficient, profile-guided, hierarchical spill code placement algorithm is used to analyze the structure of a procedure to calculate the minimum dynamic execution count locations to place callee-saved save and restore code. The algorithm is implemented in the Gnu Compiler Collection and has been tested on the SPEC CPU2000 Integer Benchmark suite. Results show that the technique reduces the number of dynamic load and store instructions by 15% compared to saving and restoring at procedure entry and exit while Chow's shrink-wrapping technique reduces dynamic load and store instructions by only 1% compared to saving and restoring at procedure entry and exit. The dynamic number of callee-saved save and restore instructions inserted with this new approach is never greater than the number produced by Chow's shrink-wrapping technique or the placement at procedure entry and exit.


title: Profiling over Adaptive Ranges

authors:
Shashidhar Mysore
Banit Agrawal
Timothy Sherwood
Nisheeth Shrivastava
Subhash Suri

abstract: Modern computer systems are called on to deal with billions of events every second, whether they are instructions executed, memory locations accessed, or packets forwarded. This presents a serious challenge to those who seek to quantify, analyze, or optimize such systems, because important trends and behaviors may easily be lost in a sea of data. We present range adaptive profiling (RAP) as a new and general purpose profiling method capable of hierarchically classifying streams of data efficiently in hardware. Through the use of RAP, events in an input stream are dynamically classified into increasingly precise categories based on the frequency with which they occur. The more important a class, or range of events, the more precisely it is quantified. Despite the dynamic nature of our technique, we build upon tight theoretic bounds covering both worst-case error as well as the required memory. In the limit, it is known that error and the memory bounds can be independent of the stream size, and grow only linearly with the level of precision desired. Significantly, we expose the critical constants in these algorithms and through careful engineering, algorithm re-design, and use of heuristics, we show how a high performance profile system can be implemented for range adaptive profiling. RAP can be used on various profiles such as PCs, load values, and memory addresses, and has a broad range of uses, from hot-region profiling to quantifying cache miss value locality. We propose two methods of implementation, one in software and the other with specialized hardware, and we show that with just 8k bytes of memory range profiles can be gathered with an average accuracy of 98%.


title: Online Phase Detection Algorithms

authors:
Priya Nagpurkar
Chandra Krintz
Michael Hind
Peter F. Sweeney
V. T. Rajan

abstract: Today's virtual machines (VMs) dynamically optimize an application as it is executing, often employing optimizations that are specialized for the current execution profile. An online phase detector determines when an executing program is in a stable period of program execution (a phase) or is in transition. A VM using an online phase detector can apply specialized optimizations during a phase or reconsider optimization decisions between phases. Unfortunately, extant approaches to detecting phase behavior rely on either offline profiling, hardware support, or are targeted toward a particular optimization. In this work, we focus on the enabling technology of online phase detection. More specifically, we contribute (a) a novel framework for online phase detection, (b) multiple instantiations of the framework that produce novel online phase detection algorithms, (c) a novel client- and machine-independent baseline methodology for evaluating the accuracy of an online phase detector, (d) a metric to compare online detectors to this baseline, and (e) a detailed empirical evaluation, using Java applications, of the accuracy of the numerous phase detectors.


title: BIRD: Binary Interpretation using Runtime Disassembly

authors:
Susanta Nanda
Wei Li
Lap-Chung Lam
Tzi-cker Chiueh

abstract: The majority of security vulnerabilities published in the literature is due to software bugs. Many researchers have developed program transformation and analysis techniques to automatically detect or eliminate such vulnerabilities. So far, most of them cannot be applied to commercially distributed applications on the Windows/x86 platform, because it is almost impossible to disassemble a binary file with 100% accuracy and coverage on that platform. This paper presents the design, implementation, and evaluation of a binary analysis and instrumentation infrastructure for the Windows/x86 platform called BIRD (binary interpretation using runtime disassembly), which provides two services to developers of security-enhancing program transformation tools: converting binary code into assembly language instructions for further analysis, and inserting instrumentation code at specific places of a given binary without affecting its execution semantics. Instead of requiring a high-fidelity instruction set architectural emulator, BIRD combines static disassembly with an on-demand dynamic disassembly approach to guarantee that each instruction in a binary file is analyzed or transformed before it is executed. It takes 12 student months to develop the first BIRD prototype, which can successfully work for all applications in Microsoft office suite as well as Internet explorer and IIS Web server, including all DLLs that they use. Moreover, the additional throughput penalty of the BIRD prototype on production server applications such as Apache, IIS, and BIND is uniformly below 4%.


title: Multi-platform Auto-vectorization

authors:
Dorit Nuzman
Richard Henderson

abstract: The recent proliferation of the single instruction multiple data (SIMD) model has lead to a wide variety of implementations. These have been incorporated into many platforms, from gaming machines and DSPs to general purpose architectures. In this paper, we present an automatic vectorizer as implemented in GCC, the most multi-targetable compiler available today. We discuss the considerations involved in developing a multi-platform vectorization technology, and demonstrate how our vectorization scheme is suited to a variety of SIMD architectures. Experiments on four different SIMD platforms demonstrate that our automatic vectorization scheme is able to efficiently support individual platforms, achieving significant speedups on key kernels.


title: Fast and Effective Orchestration of Compiler Optimizations for Automatic Performance Tuning

authors:
Zhelong Pan
Rudolf Eigenmann

abstract: Although compile-time optimizations generally improve program performance, degradations caused by individual techniques are to be expected. One promising research direction to overcome this problem is the development of dynamic, feedback-directed optimization orchestration algorithms, which automatically search for the combination of optimization techniques that achieves the best program performance. The challenge is to develop an orchestration algorithm that finds, in an exponential search space, a solution that is close to the best, in acceptable time. In this paper, we build such a fast and effective algorithm, called combined elimination (CE). The key advance of CE over existing techniques is that it takes the least tuning time (57% of the closest alternative), while achieving the same program performance. We conduct the experiments on both a Pentium IV machine and a SPARC II machine, by measuring performance of SPEC CPU2000 benchmarks under a large set of 38 GCC compiler options. Furthermore, through orchestrating a small set of optimizations causing the most degradation, we show that the performance achieved by CE is close to the upper bound obtained by an exhaustive search algorithm. The gap is less than 0.2% on average.


title: Compiling for EDGE Architectures

authors:
Aaron Smith
Jon Gibson
Bertrand A. Maher
Nicholas Nethercote
Bill Yoder
Doug Burger
Kathryn S. McKinley
James H. Burrill

abstract: Explicit data graph execution (EDGE) architectures offer the possibility of high instruction-level parallelism with energy efficiency. In EDGE architectures, the compiler breaks a program into a sequence of structured blocks that the hardware executes atomically. The instructions within each block communicate directly, instead of communicating through shared registers. The TRIPS EDGE architecture imposes restrictions on its blocks to simplify the microarchitecture: each TRIPS block has at most 128 instructions, issues at most 32 loads and/or stores, and executes at most 32 register bank reads and 32 writes. To detect block completion, each TRIPS block must produce a constant number of outputs (stores and register writes) and a branch decision. The goal of the TRIPS compiler is to produce TRIPS blocks full of useful instructions while enforcing these constraints. This paper describes a set of compiler algorithms that meet these sometimes conflicting goals, including an algorithm that assigns load and store identifiers to maximize the number of loads and stores within a block. We demonstrate the correctness of these algorithms in simulation on SPEC2000, EEMBC, and microbenchmarks extracted from SPEC2000 and others. We measure speedup in cycles over an Alpha 21264 on microbenchmarks.


title: A Compiler-Guided Approach for Reducing Disk Power Consumption by Exploiting Disk Access Locality

authors:
Seung Woo Son
Guangyu Chen
Mahmut T. Kandemir

abstract: Power consumption of large servers and clusters has recently been a popular research topic, since this issue is important from both technical and environmental viewpoints. The prior research proposed disk power management as one of the important ways of reducing overall power of a large system and considered both hardware-based and software-guided disk power reduction schemes. One of the common characteristics of the previously proposed approaches to disk power reduction is that they work with a given disk access pattern. In comparison, the goal of the approach proposed in this paper is to restructure application code using an optimizing compiler so that disk idle periods are lengthened. This in turn allows the underlying disk power management scheme to be more effective since such schemes usually prefer the long idle periods over the short ones. Our approach targets at large scientific applications that operate on disk-resident arrays using nested loops and exhibit regular data access patterns. To test the effectiveness of the proposed approach, we implemented it within an optimizing compiler and performed experiments with six data-intensive applications that manipulate disk-resident data. Our experimental analysis shows that the proposed approach is very successful in practice and reduces the total disk energy consumption on average by 18.17%, as compared to an execution without any disk power management, and by 11.55%, as compared to an execution that employs disks with low-power capabilities without our code restructuring approach.


title: Dynamic Class Hierarchy Mutation

authors:
Lixin Su
Mikko H. Lipasti

abstract: Class hierarchies in object-oriented programs are used to capture various attributes of the underlying objects they represent, allowing programmers to encapsulate common attributes in base classes while distributing private attributes in lower-level derived classes. In essence, the semantics of the class hierarchy elegantly capture some of the possible states that a particular object can assume. However, class hierarchies are often poorly designed or evolve in ways that fail to fully capture the stateful behavior of objects. This paper proposes an automated approach for detecting stateful class attributes, and then mutating the class hierarchy dynamically to capture such behavior by creating implicit derived classes that can be specialized for specific object states. Our scheme captures both run-time static behavior, which could have been captured by the programmer by restructuring the class hierarchy at the source level; as well as run-time variant behavior, which cannot be captured using source code transformations. In the latter case, objects transition from one state to another and are dynamically mutated from a derived class to a peer derived class corresponding to the object's new state. These class hierarchy mutations create new opportunities for conventional optimizations such as constant propagation, function specialization, and dead code elimination. For our benchmark set, which includes two versions of SPECjbb, we measure speedups of 1.9% to 31.4% within our Jikes-based prototype implementation, with negligible increases in compilation overhead and object code size.


title: Experiences with Multi-threading and Dynamic Class Loading in a Java Just-In-Time Compiler

authors:
Vijay Sundaresan
Daryl Maier
Pramod Ramarao
Mark G. Stoodley

abstract: In this paper, we describe the techniques that have been implemented in the IBM TestaRossa (TR) just-in-time (JIT) compiler to safely perform aggressive code patching and collect accurate profiles in the context of a Java application employing multiple threads and dynamic class loading and unloading. Previous work in these areas either did not account for the synchronization cost of safety or dynamic class loading/unloading effects in a heavily multithreaded program or did not consider how different patching techniques may be required for different platforms where instruction cache coherence guarantees vary. We evaluate the space and time overhead to make our profiling framework correct, showing that privatizing the profiling variables to achieve correctness impacts execution time only minimally but it can grow the stack frames for profiled methods by less than 15% on average for the SPECjvm98 and SPECjbb2000 benchmarks. Since methods are profiled for only a brief time and the stack frames themselves are not large, we do not consider this growth to be prohibitive. The techniques reported in this paper are implemented in the 1.5.0 release of the IBM Developer Kit for Java targeting 12 different processor-operating system platforms.


title: Space-Efficient 64-bit Java Objects through Selective Typed Virtual Addressing

authors:
Kris Venstermans
Lieven Eeckhout
Koen De Bosschere

abstract: Memory performance is an important design issue for contemporary systems given the ever increasing memory gap. This paper proposes a space-efficient Java object model for reducing the memory consumption of 64-bit Java virtual machines. We propose selective typed virtual addressing (STVA) which uses typed virtual addressing (TVA) or implicit typing for reducing the header of 64-bit Java objects. The idea behind TVA is to encode the object's type in the object's virtual address. In other words, all objects of a given type are allocated in a contiguous memory segment. As such, the type information can be removed from the object's header which reduces the number of allocated bytes per object. Whenever type information is needed for the given object, masking is applied to the object's virtual address. Unlike previous work on implicit typing, we apply TVA to a selected number of frequently allocated and/or long-lived object types. This limits the amount of memory fragmentation. We implement STVA in the 64-bit version of the Jikes RVM on an AIX IBM platform and compare its performance against a traditional VM implementation without STVA using a multitude of Java benchmarks. We conclude that STVA reduces memory consumption by on average 15.5% (and up to 39% for some benchmarks). In terms of performance, STVA generally does not affect performance, however for some benchmarks we observe statistically significant performance speedups, up to 24%.


title: Constructing Virtual Architectures on a Tiled Processor

authors:
David Wentzlaff
Anant Agarwal

abstract: As the amount of available silicon resources on one chip increases, we have seen the advent of ever increasing parallel resources integrated on-chip. Many architectures use these resources as individually controllable, parallel processing elements. While such architectures excel at parallel applications, they seldom support legacy single-threaded applications. In this work, we propose using parallel resources to facilitate execution of legacy codes with acceptable performance on parallel architectures containing a drastically different instruction set through the use of an all software parallel dynamic binary translation engine. This engine spatially implements different portions of a superscalar processor across distinct parallel elements thus exploiting the pipeline parallelism inherent in a superscalar. This virtual micro architecture facilitates changing the allocation of silicon resources between different superscalar units in software which is not possible when special purpose physical resources are built. We propose building dynamically reconfigurable architectures that inspect the current virtual machine configuration along with the dynamic instruction stream and change the configuration to best suit the program's needs at runtime. An x86 to Raw parallel translation engine was built in which tiles dedicated to translation can be traded for tiles dedicated to the memory system as an example of dynamic reconfiguration.


title: International Symposium on Code Generation and Optimization - Front Cover

abstract: The following topics are dealt with: code optimization; dynamic optimization object-oriented code generation; phase detection; phase profiling; tiled compilation; multicore compilation; static code generation; SIMD compilation optimization space exploration; security; and reliability.


title: International Symposium on Code Generation and Optimization - Title Page


title: International Symposium on Code Generation and Optimization - Copyright

abstract: Copyright and Reprint Permissions: Abstracting is permitted with credit to the source. Libraries may photocopy beyond the limits of US copyright law, for private use of patrons, those articles in this volume that carry a code at the bottom of the first page, provided that the per-copy fee indicated in the code is paid through the Copyright Clearance Center. The papers in this book comprise the proceedings of the meeting mentioned on the cover and title page. They reflect the authors' opinions and, in the interests of timely dissemination, are published as presented and without change. Their inclusion in this publication does not necessarily constitute endorsement by the editors or the Institute of Electrical and Electronics Engineers, Inc.


title: Message from the General Co-Chairs


title: Message from the Program Chair


title: Committees


title: Reviewers


title: Corporate Sponsors


title: A Self-Repairing Prefetcher in an Event-Driven Dynamic Optimization Framework

authors:
Weifeng Zhang
Brad Calder
Dean M. Tullsen

abstract: Software prefetching has been demonstrated as a powerful technique to tolerate long load latencies. However, to be effective, prefetching must target the most critical (frequently missing) loads, and prefetch them sufficiently far in advance. This is difficult to do correctly with a static optimizer, because locality characteristics and cache latencies vary across data inputs and across different machines. This paper presents a mechanism that dynamically inserts prefetch instructions into frequently executed hot traces. Hot traces are dynamically analyzed to identify delinquent loads and the appropriate prefetch distance for those loads. Those prefetches are then inserted into the hot trace. The low overhead of the event-driven dynamic optimization system allows the optimizer to continuously monitor the performance of the software prefetches. This is done to find an accurate and stable prefetch distance and to adapt to changes in program behavior using what we call self-repairing prefetching. Relative to the baseline hardware stride prefetching, we find a total 23% improvement when we use the self-repairing mechanism to adoptively discover the best prefetch distance for each load, which is 12% better performance than dynamic prefetching techniques without adaptive repairing.


title: Compiler Optimizations to Reduce Security Overhead

authors:
Tao Zhang
Xiaotong Zhuang
Santosh Pande

abstract: In this work, we present several compiler optimizations to reduce the overhead due to software protection. We first propose an aggressive rematerialization algorithm which attempts to maximally realize non-trusted values from other trusted values thereby avoiding the security cost for those non-trusted values. We further propose a compiler technique to utilize the secure storage in our machine model efficiently. To optimize the security cost on data that has to be stored in non-trusted storage, we propose a data grouping technique. Security operations can be performed over the group of data instead of over each piece separately. We show an interesting application of the data grouping technique to reduce the security cost. We test the effectiveness of our optimizations on a recently proposed software protection scheme that involves large overhead. Our results show that the above optimizations are effective and reduce the security overhead significantly.


title: Heterogeneous Clustered VLIW Microarchitectures

authors:
Alex Aletà
Josep M. Codina
Antonio González
David R. Kaeli

abstract: Increasing performance, while at the same time reducing power consumption, is a major design tradeoff in current microprocessors. In this paper, we investigate the potential of using a heterogeneous clustered VLIW microarchitecture. In the proposed microarchitecture, each cluster, the interconnection network and the supporting memory hierarchy can run at different frequencies and voltages. Some of the clusters can then be configured to be performance-oriented and run at high frequency, while the other clusters can be configured to be low-power-oriented and run at lower frequencies, thus reducing overall consumption. For this heterogeneous design to be effective, we need to select the most suitable frequencies and voltages for each component. We propose a scheme to choose these parameters based on a model that estimates the energy consumption and the execution time of floating-point codes at compile time. Finally, we present a modulo scheduling technique based on graph partitioning that exploits the opportunities presented on heterogeneous clustered microarchitectures. Results show that the Energy-Delay product (ED2) can be significantly reduced by 15% on average for a microarchitecture with 4-clusters and by as much as 35% for selected programs


title: Loop Optimization using Hierarchical Compilation and Kernel Decomposition

authors:
Denis Barthou
Sébastien Donadio
Patrick Carribault
Alexandre Duchateau
William Jalby

abstract: The increasing complexity of hardware features for recent processors makes high performance code generation very challenging. In particular, several optimization targets have to be pursued simultaneously (minimizing L1/L2/L3/TLB misses and maximizing instruction level parallelism). Very often, these optimization goals impose different and contradictory constraints on the transformations to be applied. We propose a new hierarchical compilation approach for the generation of high performance code relying on the use of state-of-the-art compilers. This approach is not application-dependent and do not require any assembly hand-coding. It relies on the decomposition of the original loop nest into simpler kernels, typically 1D to 2D loops, much simpler to optimize. We successfully applied this approach to optimize dense matrix muliply primitives (not only for the square case but to the more general rectangular cases) and convolution. The performance of the optimized codes on Itanium 2 and Pentium 4 architectures outperforms ATLAS and in most cases, matches hand-tuned vendor libraries (e.g. MKL)


title: A Dimension Abstraction Approach to Vectorization in Matlab

authors:
Neil Birkbeck
Jonathan Levesque
José Nelson Amaral

abstract: Matlab is a matrix-processing language that offers very efficient built-in operations for data organized in arrays. However Matlab operation is slow when the program accesses data through interpreted loops. Often during the development of a Matlab application writing loop-based code is more intuitive than crafting the data organization into arrays. Furthermore, many Matlab users do not command the linear algebra expertise necessary to write efficient code. Thus loop-based Matlab coding is a fairly common practice. This paper presents a tool that automatically converts loop-based Matlab code into equivalent array-based form and built-in Matlab constructs. Array-based code is produced by checking the input and output dimensions of equations within loops, and by transposing terms when necessary to generate correct code. This paper also describes an extensible loop pattern database that allows user-defined patterns to be discovered and replaced by more efficient Matlab routines that perform the same computation. The safe conversion of loop-based into more efficient array-based code is made possible by the introduction of a new abstract representation for dimensions


title: On the Complexity of Register Coalescing

authors:
Florent Bouchez
Alain Darte
Fabrice Rastello

abstract: Memory transfers are becoming more important to optimize, for both performance and power consumption. With this goal in mind, new register allocation schemes are developed, which revisit not only the spilling problem but also the coalescing problem. Indeed, a more aggressive strategy to avoid load/store instructions may increase the constraints to suppress (coalesce) move instructions. This paper is devoted to the complexity of the coalescing phase, in particular in the light of recent developments on the SSA form. We distinguish several optimizations that occur in coalescing heuristics: a) aggressive coalescing removes as many moves as possible, regardless of the colorability of the resulting interference graph; b) conservative coalescing removes as many moves as possible while keeping the colorability of the graph; c) incremental conservative coalescing removes one particular move while keeping the colorability of the graph; d) optimistic coalescing coalesces moves aggressively, then gives up about as few moves as possible so that the graph becomes colorable again. We almost completely classify the NP-completeness of these problems, discussing also on the structure of the interference graph: arbitrary, chordal, or k-colorable in a greedy fashion. We believe that such a study is a necessary step for designing new coalescing strategies


title: GPU Computing: Programming a Massively Parallel Processor

abstract: Summary form only given. Many researchers have observed that general purpose computing with programmable graphics hardware (GPUs) has shown promise to solve many of the world's compute intensive problems, many orders of magnitude faster the conventional CPUs. The challenge has been working within the constraints of a graphics programming environment and limited language support to leverage this huge performance potential. GPU computing with CUDA is a new approach to computing where hundreds of on-chip processor cores simultaneously communicate and cooperate to solve complex computing problems, transforming the GPU into a massively parallel processor. The NVIDIA C-compiler for the GPU provides a complete development environment that gives developers the tools they need to solve new problems in computation-intensive applications such as product design, data analysis, technical computing, and game physics. In this talk, I will provide a description of how CUDA can solve compute intensive problems and highlight the challenges when compiling parallel programs for GPUs including the differences between graphics shaders vs. CUDA applications


title: Rapidly Selecting Good Compiler Optimizations using Performance Counters

authors:
John Cavazos
Grigori Fursin
Felix V. Agakov
Edwin V. Bonilla
Michael F. P. O'Boyle
Olivier Temam

abstract: Applying the right compiler optimizations to a particular program can have a significant impact on program performance. Due to the non-linear interaction of compiler optimizations, however, determining the best setting is non-trivial. There have been several proposed techniques that search the space of compiler options to find good solutions; however such approaches can be expensive. This paper proposes a different approach using performance counters as a means of determining good compiler optimization settings. This is achieved by learning a model off-line which can then be used to determine good settings for any new program. We show that such an approach outperforms the state-of-the-art and is two orders of magnitude faster on average. Furthermore, we show that our performance counter-based approach outperforms techniques based on static code features. Using our technique we achieve a 17% improvement over the highest optimization setting of the commercial PathScale EKOPath 2.3.1 optimizing compiler on the SPEC benchmark suite on a AMD Athlon 64 3700+ platform


title: Virtual Cluster Scheduling Through the Scheduling Graph

authors:
Josep M. Codina
F. Jesús Sánchez
Antonio González

abstract: This paper presents an instruction scheduling and cluster assignment approach for clustered processors. The proposed technique makes use of a novel representation named the scheduling graph which describes all possible schedules. A powerful deduction process is applied to this graph, reducing at each step the set of possible schedules. In contrast to traditional list scheduling techniques, the proposed scheme tries to establish relations among instructions rather than assigning each instruction to a particular cycle. The main advantage is that wrong or poor schedules can be anticipated and discarded earlier. In addition, cluster assignment of instructions is performed using another novel concept called virtual clusters, which define sets of instructions that must execute in the same cluster. These clusters are managed during the deduction process to identify incompatibilities among instructions. The mapping of virtual to physical clusters is postponed until the scheduling of the instructions has finalized. The advantages this novel approach features include: (1) accurate scheduling information when assigning, and, (2) accurate information of the cluster assignment constraints imposed by scheduling decisions. We have implemented and evaluated the proposed scheme with superblocks extracted from Speclnt95 and MediaBench. The results show that this approach produces better schedules than the previous state-of-the-art. Speed-ups are up to 15%, with average speed-ups ranging from 2.5% (2-Clusters) to 9.5% (4-Clusters)


title: Pipelined Execution of Critical Sections Using Software-Controlled Caching in Network Processors

authors:
Jinquan Dai
Long Li
Bo Huang

abstract: To keep up with the explosive Internet packet processing demands, modern network processors (NPs) employ a highly parallel, multi-threaded and multi-core architecture. In such a parallel paradigm, accesses to the shared variables in the external memory (and the associated memory latency) are contained in the critical sections, so that they can be executed atomically and sequentially by different threads in the network processor. In this paper, we present a novel program transformation that is used in the Intelreg Auto-partitioning C Compiler for IXP to exploit the inherent finer-grained parallelism of those critical sections, using the software-controlled caching mechanism available in the NPs. Consequently, those critical sections can be executed in a pipelined fashion by different threads, thereby effectively hiding the memory latency and improving the performance of network applications. Experimental results show that the proposed transformation provides impressive speedup (up-to 9.9times) and scalability (up-to 80 threads) of the performance for the real-world network application (a 10Gbps Ethernet Core/Metro Router)


title: Understanding Tradeoffs in Software Transactional Memory

authors:
David Dice
Nir Shavit

abstract: There has been a flurry of recent work on the design of high performance software and hybrid hardware/software transactional memories (STMs and HyTMs). This paper re-examines the design decisions behind several of these state-of-the-art algorithms, adopting some ideas, rejecting others, all in an attempt to make STMs faster. We created the transactional locking (TL) framework of STM algorithms and used it to conduct a range of comparisons of the performance of non-blocking, lock-based, and Hybrid STM algorithms versus fine-grained hand-crafted ones. We were able to make several illuminating observations regarding lock acquisition order, the interaction of STMs with memory management schemes, and the role of overheads and abort rates in STM performance


title: Graph-Based Procedural Abstraction

authors:
Alexander Dreweke
Marc Wörlein
Ingrid Fischer
Dominic Schell
Thorsten Meinl
Michael Philippsen

abstract: Procedural abstraction (PA) extracts duplicate code segments into a newly created method and hence reduces code size. For embedded micro computers the amount of memory is still limited so code reduction is an important issue. This paper presents a novel approach to PA, that is especially targeted towards embedded systems. Earlier approaches of PA are blind with respect to code reordering, i.e., two code segments with the same semantic effect but with different instruction orders were not detected as candidates for PA. Instead of instruction sequences, in our approach the data flow graphs of basic blocks are considered. Compared to known PA techniques more than twice the number of instructions can be saved on a set of binaries, by detecting frequently appearing graph fragments with a graph mining tool based on the well known gSpan algorithm. The detection and extraction of graph fragments is not as straight forward as extracting sequential code fragments. NP-complete graph operations and special rules to decide which parts can be abstracted are needed. However, this effort pays off as smaller sizes significantly reduce costs on mass-produced embedded systems


title: Parallel Programming Environment: A Key to Translating Tera-Scale Platforms into a Big Success

abstract: Summary form only given. Moore's Law will continue to increase the number of transistors on die for a couple of decades, as silicon technology moves from 65nm today to 45nm, 32 nm and 22nm in the future. Since the power and thermal constraints increase with frequency, multi-core or many-core will be the way of the future microprocessor. In the near future, HW platforms will have many-cores (>16 cores) on die to achieve >1 TIPs computation power, which will communicate each other through an on-die interconnect fabric with >1 TB/s on-die bandwidth and <30 cycles latency. Off-die D-cache will employ 3D stacked memory technology to tremendously increase off-die cache/memory bandwidth and reduce the latency. Fast copper flex cables will link CPU-DRAM on socket and the optical silicon photonics will provide up to 1 Tb/s I/O bandwidth between boxes. The HW system with TIPs of compute power operating in Tera-bytes of data make this a "Tera-scale" platform. What are the SW implications with the HW changes from uniprocessor to Tera-scale platform with many-cores as "the way of the future?" It will be great challenge for programming environments to help programmers to develop concurrent code for most client software. A good concurrent programming environment should extend the existing programming languages that typical programmers are familiar with, and bring benefits for concurrent programming. There are lots of research topics. Examples of these topics include flexible parallel programming models based on needs from applications, better synchronization mechanisms like Transactional Memory to replace simple "Thread + Lock" structure, nested data parallel language primitives with new protocols, fine-grained synchronization mechanisms with HW support, maybe fine-grained message passing, advanced compiler optimizations for the threaded code, and SW tools in the concurrent programming environment. A more interesting problem is how to use such a many-core system to improve single-threaded performance


title: Compilation Techniques for Real-Time Java Programs

authors:
Mike Fulton
Mark G. Stoodley

abstract: In this paper, we introduce the IBMreg WebSpherereg real time product, which incorporates a virtual machine that is fully Javatrade compliant as well as compliant with the Real-Time Specification for Java (RTSJ). We describe IBM's real-time Java enhancements, particularly in the area of our Testarossa (TR) ahead-of-time (AOT) compiler, our TR just-in-time (JIT) compiler, and our Metronome (Bacon, et al., 2003) deterministic garbage collector (GC). The main focus of this paper is on the various techniques employed by the TR compilers to optimize and regulate the performance of code running in a real-time Java environment through a simple Java source code example. Through the example, we highlight the additional checks required to provide a conformant RTSJ implementation as well as the performance issues with ahead-of-time code generation and the overheads required to support Metronome. We show how these checks are implemented in a production JVM, and then report the cost of the real-time changes in practice for the example as well as the SPECjvm98 benchmark suite, SPECjbb2000, and SPECjbb2005


title: Isla Vista Heap Sizing: Using Feedback to Avoid Paging

authors:
Chris Grzegorczyk
Sunil Soman
Chandra Krintz
Richard Wolski

abstract: Managed runtime environments (MREs) employ garbage collection (GC) for automatic memory management. However, GC induces pressure on the virtual memory (VM) manager, since it may touch pages that are not related to the working set of the application. Paging due to GC can significantly hurt performance, even when the application's working set fits into physical memory. We present a feedback-directed heap resizing mechanism to avoid GC-induced paging, using information from the operating system (OS). We avoid costly GCs when there is physical memory available, and trade off GC for paging when memory is constrained. Our mechanism is simple and uses allocation stall events during GC alone to trigger heap resizing, without user participation or OS kernel modification. Our system enables significant performance improvements when real memory is restricted and similar to, or better performance than, the current state-of-the-art MRE, when memory is unconstrained


title: Code Compaction of an Operating System Kernel

authors:
Haifeng He
John Trimble
Somu Perianayagam
Saumya K. Debray
Gregory R. Andrews

abstract: General-purpose operating systems, such as Linux, are increasingly being used in embedded systems. Computational resources are usually limited, and embedded processors often have a limited amount of memory. This makes code size especially important. This paper describes techniques for automatically reducing the memory footprint of general-purpose operating systems on embedded platforms. The problem is complicated by the fact that kernel code tends to be quite different from ordinary application code, including the presence of a significant amount of hand-written assembly code, multiple entry points, implicit control flow paths involving interrupt handlers, and frequent indirect control flow via function pointers. We use a novel "approximate decompilation" technique to apply source-level program analysis to hand-written assembly code. A prototype implementation of our ideas on an Intel x86 platform, applied to a Linux kernel that has been configured to exclude unnecessary code, obtains a code size reduction of close to 24%


title: Evaluating Indirect Branch Handling Mechanisms in Software Dynamic Translation Systems

authors:
Jason Hiser
Daniel W. Williams
Wei Hu
Jack W. Davidson
Jason Mars
Bruce R. Childers

abstract: Software dynamic translation (SDT) systems are used for program instrumentation, dynamic optimization, security, intrusion detection, and many other uses. As noted by many researchers, a major source of SDT overhead is the execution of code which is needed to translate an indirect branch's target address into the address of the translated destination block. This paper discusses the sources of indirect branch (IB) overhead in SDT systems and evaluates several techniques for overhead reduction. Measurements using SPEC CPU2000 show that the appropriate choice and configuration of IB translation mechanisms can significantly reduce the IB handling overhead. In addition, cross-architecture evaluation of IB handling mechanisms reveals that the most efficient implementation and configuration can be highly dependent on the implementation of the underlying architecture


title: Exploiting Narrow Accelerators with Data-Centric Subgraph Mapping

authors:
Amir Hormati
Nathan Clark
Scott A. Mahlke

abstract: The demand for high performance has driven acyclic computation accelerators into extensive use in modern embedded and desktop architectures. Accelerators that are ideal from a software perspective, are difficult or impossible to integrate in many modern architectures, though, due to area and timing requirements. This reality is coupled with the observation that many application domains under-utilize accelerator hardware, because of the narrow data they operate on and the nature of their computation. In this work, we take advantage of these facts to design accelerators capable of executing in modern architectures by narrowing datapath width and reducing interconnect. Novel compiler techniques are developed in order to generate high-quality code for the reduced-cost accelerators and prevent performance loss to the extent possible. First, data width profiling is used to statistically determine how wide program data will be at run time. This information is used by the subgraph mapping algorithm to optimally select subgraphs for execution on targeted narrow accelerators. Overall, our data-centric compilation techniques achieve on average 6.5%, and up to 12%, speed up over previous subgraph mapping algorithms for 8-bit accelerators. We also show that, with appropriate compiler support, the increase in the total number of execution cycles in reduced-interconnect accelerators is less than 1% of the fully-connected accelerator


title: Profile-assisted Compiler Support for Dynamic Predication in Diverge-Merge Processors

authors:
Hyesoon Kim
José A. Joao
Onur Mutlu
Yale N. Patt

abstract: Dynamic predication has been proposed to reduce the branch misprediction penalty due to hard-to-predict branch instructions. A proposed dynamic predication architecture, the diverge-merge processor (DMP), provides large performance improvements by dynamically predicating a large set of complex control-flow graphs that result in branch mispredictions. DMP requires significant support from a profiling compiler to determine which branch instructions and control-flow structures can be dynamically predicated. However, previous work on dynamic predication did not extensively examine the tradeoffs involved in profiling and code generation for dynamic predication architectures. This paper describes compiler support for obtaining high performance in the diverge-merge processor. We describe new profile-driven algorithms and heuristics to select branch instructions that are suitable and profitable for dynamic predication. We also develop a new profile-based analytical cost-benefit model to estimate, at compile-time, the performance benefits of the dynamic predication of different types of control-flow structures including complex hammocks and loops. Our evaluations show that DMP can provide 20.4% average performance improvement over a conventional processor on SPEC integer benchmarks with our optimized compiler algorithms, whereas the average performance improvement of the best-performing alternative simple compiler algorithm is 4.5%. We also find that, with the proposed algorithms, DMP performance is not significantly affected by the differences in profile- and run-time input data sets