This paper discusses a repertoire of well-known and new compiler optimizations that help produce excellent server application performance and investigates their performance contributions. These optimizations combined produce a 40% speed-up in on-line transaction processing (OLTP) performance and have been implemented in the Intel C/C++ Itanium compiler. In particular, the paper presents compiler optimizations that take advantage of the Itanium register stack, proposes an enhanced Linux preemption model and demonstrates their performance potential for server applications.

This paper explores Speculative Precomputation, a technique that uses idle thread context in a multithreaded architecture to improve performance of single-threaded applications. It attacks program stalls from data cache misses by pre-computing future memory accesses in available thread contexts, and prefetching these data. This technique is evaluated by simulating the performance of a research processor based on the Itanium™ ISA supporting Simultaneous Multithreading. Two primary forms of Speculative Precomputation are evaluated. If only the non-speculative thread spawns speculative threads, performance gains of up to 30% are achieved when assuming ideal hardware. However, this speedup drops considerably with more realistic hardware assumptions. Permitting speculative threads to directly spawn additional speculative threads reduces the overhead associated with spawning threads and enables significantly more aggressive speculation, overcoming this limitation. Even with realistic costs for spawning threads, speedups as high as 169% are achieved, with an average speedup of 76%.

In this article, we present a new framework for elimination-based exhaustive and incremental data flow analysis using the DJ graph representation of a program.Unlike previous approaches to elimination-based incremental data flow analysis, our approach can handle arbitrary structural and nonstructural changes to program flowgraphs, including irreducibility.We show how our approach is related to dominance frontiers, and we exploit this relationship to establish the complexity of our exhaustive analysis and to aid the design of our incremental analysis.

In this article, we present a new algorithm for incrementally maintaining the dominator tree of an arbitrary flowgraph.Previous work most relevant to this article includes only the Carroll-Ryder algorithm and the Ramalingam-Reps algorithm.Both these methods are restricted to reducible flowgraphs.By contrast, our approach can handle irreducible as well as reducible flowgraphs.For the case where an edge is inserted, our incremental algorithm is also faster than previous incremental algorithms in the worst case.For the deletion case, our algorithm has a quadratic time complexity in the worst case.

We present a new elimination-based framework for exhaustive and incremental data flow analysis using the DJ graph representation of a program. Unlike the previous approaches to elimination-based incremental data flow analysis, our approach can handle arbitrary non-structural and structural changes to program flowgraphs, including those causing irreducibility. We show how our approach is related to (iterated) dominance frontiers, and exploit this relationship to establish the complexity of our exhaustive analysis and to aid the design of our incremental analysis.

Loop identification is a necessary step in loop transformations for high-performance architectures. One classical technique for detecting loops is Tarjan's interval-finding algorithm. The intervals identified by Tarjan's method are single-entry, strongly connected subgraphs that closely reflect a program's loop structure. We present a simple algorithm for identifying both reducible and irreducible loops using DJ graphs. Our method is a generalization of Tarjan's method, as it identifies nested intervals (or loops) even in the presence of irreducibility.

Parallel data flow analysis methods offer the promise of calculating detailed semantic information about a program at compile-time more efficiently than sequential techniques. Previous work on parallel elimination methods (Zobel, 1990) has been hampered by the lack of control over interval size; this can prohibit effective parallel execution of these methods. To overcome this problem, we have designed the region analysis method, a new elimination method for data flow analysis. Region analysis emphasizes flow graph partitioning to enable better load balancing in a more effective parallel algorithm. We present the design of region analysis and the empirical results we have obtained that indicate: the prevalence of large intervals in flow graphs derived from real programs; and the performance improvement of region analysis over parallel Allen-Cocke interval analysis. Our implementation analyzed programs from the Perfect Benchmarks and netlib running on a Sequent Symmetry S81.>

We present a comprehensive approach to performing data flow analysis in parallel. We first identify three types of parallelism inherent in the data flow solution process: independent-problem parallelism, separate-unit parallelism and algorithmic parallelism. We then describe a unified framework to exploit them. Our investigations of typical Fortran programs reveal an abundance of the last two types of parallelism. In particular, we illustrate the exploitation of algorithmic parallelism in the design of our parallel hybrid data flow analysis algorithm and report on its empirical performance.

The authors have designed a family of parallel dataflow analysis algorithms for execution on a message-passing MIMD (multiple instruction multiple data) architecture, based on general purpose, hybrid dataflow analysis algorithms. They have exploited the natural task partitioning of the hybrid algorithms and have explored a static mapping-dynamic scheduling strategy. Alternative mapping-scheduling choices and refinements of the flow graph condensation utilized are discussed. This parallel hybrid algorithm family is illustrated on the reaching definitions problem, although parallel algorithms also exist for many interprocedural (e.g., aliasing) and intraprocedural (e.g., available expressions) problems.>