Search

Most compilers apply optimizations in a fixed order regardless of input programs. However, it is well known that optimizations can have enabling, and disabling interactions or equivalent effects. The effects of interference are program specific and hence no single sequence is universally appropriate for all input programs. In this paper we explore the problem of searching for optimal sequences of compiler optimizations to apply for a given program and describe novel strategies that bring us a step closer to searching this problem space efficiently. We also construct models for accurately predicting the runtime performance of a program when a sequence of optimizations is applied to it. The early results of the models on a small set of input programs are encouraging and suggest that the approaches we describe are worthy of further consideration.

The most intuitive memory consistency model for shared-memory multi-threaded programming is sequential consistency (SC). However, current concurrent programming languages support a relaxed model, as such relaxations are deemed necessary for enabling important optimizations. This paper demonstrates that an SC-preserving compiler, one that ensures that every SC behavior of a compiler-generated binary is an SC behavior of the source program, retains most of the performance benefits of an optimizing compiler. The key observation is that a large class of optimizations crucial for performance are either already SC-preserving or can be modified to preserve SC while retaining much of their effectiveness. An SC-preserving compiler, obtained by restricting the optimization phases in LLVM, a state-of-the-art C/C++ compiler, incurs an average slowdown of 3.8% and a maximum slowdown of 34% on a set of 30 programs from the SPLASH-2, PARSEC, and SPEC CINT2006 benchmark suites. While the performance overhead of preserving SC in the compiler is much less than previously assumed, it might still be unacceptable for certain applications. We believe there are several avenues for improving performance without giving up SC-preservation. In this vein, we observe that the overhead of our SC-preserving compiler arises mainly from its inability to aggressively perform a class of optimizations we identify as eager-load optimizations. This class includes common-subexpression elimination, constant propagation, global value numbering, and common cases of loop-invariant code motion. We propose a notion of interference checks in order to enable eager-load optimizations while preserving SC. Interference checks expose to the compiler a commonly used hardware speculation mechanism that can efficiently detect whether a particular variable has changed its value since last read.

We show how some classical static analyses for imperative programs, and the optimizing transformations which they enable, may be expressed and proved correct using elementary logical and denotationaltechniques. The key ingredients are an interpretation of program properties as relations, rather than predicates, and a realization that although many program analyses are traditionally formulated in very intensional terms, the associated transformations are actually enabled by more liberal extensional properties.We illustrate our approach with formal systems for analysing and transforming while-programs. The first is a simple type system which tracks constancy and dependency information and can be used to perform dead-code elimination, constant propagation and program slicing as well as capturing a form of secure information flow. The second is a relational version of Hoare logic, which significantly generalizes our first type system and can also justify optimizations including hoisting loop invariants. Finally we show how a simple available expression analysis and redundancy elimination transformation may be justified by translation into relational Hoare logic.

We present a new computational method for discovering cis- regulatory elements which circumvents the need to cluster genes based on their expression profiles. Based on a model in which upstream motifs contribute additively to the expression level of a gene, it requires a single genome-wide set of expression ratios and the upstream sequence for each gene, and outputs statistically significant motifs. Analysis of publicly available expression data for Sac charomyes cerevisiae reveals several new putative regulatory elements, some of which plausibly control the early, transient induction of genes during sporulation. Known motifs generally have high statistical significance.