Probabilistic pointer analysis (PPA) is a compile-time analysis method that estimates the probability that a points-to relationship will hold at a particular program point. The results are useful for optimizing and parallelizing compilers, which need to quantitatively assess the profitability of transformations when performing aggressive optimizations and parallelization. This paper presents a PPA technique using the static single assignment (SSA) form. When computing the probabilistic points-to relationships of a specific pointer, a pointer relation graph (PRG) is first built to represent all of the possible points-to relationships of the pointer. The PRG is transformed by a sequence of reduction operations into a compact graph, from which the probabilistic points-to relationships of the pointer can be determined. In addition, PPA is further extended to interprocedural cases by considering function related statements. We have implemented our proposed scheme including static and profiling versions in the Open64 compiler, and performed experiments to obtain the accuracy and scalability. The static version estimates branch probabilities by assuming that every conditional is equally likely to be true or false, and that every loop executes 10 times before terminating. The profiling version measures branch probabilities dynamically from past program executions using a default workload provided with the benchmark. The average errors for selected benchmarks were 3.80 percent in the profiling version and 9.13 percent in the static version. Finally, SPEC CPU2006 is used to evaluate the scalability, and the result indicates that our scheme is sufficiently efficient in practical use. The average analysis time was 35.59 seconds for an average of 98,696 lines of code.

Managing power concerns in microprocessors has become a pressing research problem across the domains of computer architecture, CAD, and compilers. As a result, several parameterized cycle-level power simulators have been introduced. While these simulators can be quite useful for microarchitectural studies, their generality limits how accurate they can be for any one chip family. Furthermore, their hardware focus means that they do not explicitly enable studying the interaction of different software layers, such as Java applications and their underlying runtime system software. This paper describes and evaluates XTREM, a power-simulation tool tailored for the Intel XScale microarchitecture. In building XTREM, our goals were to develop a microarchitecture simulator that, while still offering size parameterizations for cache and other structures, more accurately reflected a realistic processor pipeline. We present a detailed set of validations based on multimeter power measurements and hardware performance counter sampling. XTREM exhibits an average performance error of only 6.5% and an even smaller average power error: 4%. The paper goes on to present an application study enabled by the simulator. Namely, we use XTREM to produce an energy consumption breakdown for Java CDC and CLDC applications. Our simulator measurements indicate that a large percentage of the total energy consumption (up to 35%) is devoted to the virtual machine's support functions.

A general framework that integrates both control and data speculation using alias profiling and/or compiler heuristic rules has shown to improve CPU2000 performance on Itanium systems. However, speculative optimizations require check instructions and recovery code to ensure correct execution when speculation fails at runtime. How to generate check instructions and their associated recovery code efficiently and effectively is an issue yet to be well studied. It is also, very important that the recovery code generated in the earlier phases integrate gracefully in the later optimization phases. At the very least, it should not hinder later optimizations, thus, ensuring overall performance improvement. This paper proposes a framework that uses an if-block structure to facilitate check instructions and recovery code generation for general speculative optimizations. It allows speculative instructions and their recovery code generated in the early compiler optimization phases to be integrated effectively with the subsequent optimization phases. It also allows multilevel speculation for multilevel pointers and multilevel expression trees to be handled with no additional complexity. The proposed recovery code generation framework has been implemented and evaluated in the Open Research Compiler (ORC).

Programming network processors is challenging. To sustain high line rates, network processors have extremely tight memory access and instruction budgets. Achieving desired performance has traditionally required hand-coded assembly. Researchers have recently proposed high-level programming languages for packet processing, but the challenges of compiling these languages into code that is competitive with hand-tuned assembly remain unanswered.This paper describes the Shangri-La compiler, which accepts a packet program written in a C-like high-level language and applies scalar and specialized optimizations to generate a highly optimized binary. Hot code paths identified by profiling are mapped across processing elements to maximize processor utilization. Since our compilation target has no hardware caches, software-controlled caches are generated for frequently accessed application data structures. Packet handling optimizations significantly reduce per-packet memory access and instruction counts. Finally, a custom stack model maps stack frames to the fastest levels of the target processor's heterogeneous memory hierarchy.Binaries generated by the compiler were evaluated on the Intel IXP2400 network processor with eight packet processing cores and eight threads per core. Our results show the importance of both traditional and specialized optimization techniques for achieving the maximum forwarding rates on three network applications, L3-Switch, MPLS and Firewall.

Managing power concerns in icroprocessors has become a pressing research problem across the domains of computer architecture, CAD, and compilers. As a result, several parameterized cycle-level power simulators have been introduced. While these simulators can be quite useful for microarchitectural studies, their generality limits how accurate they can be for any one chip family. Furthermore, their hardware focus means that they do not explicitly enable studying the interaction of different software layers, such as Java applications and their underlying Runtime system software.This paper describes and evaluates XTREM, a power simulation tool tailored for the Intel XScale icroarchitecture. In building XTREM, our goals were to develop a icroarchitecture simulator that, while still offering size parameterizations for cache, TLB, etc., more accurately reflected a realistic processor pipeline. We present a detailed set of validations based on ultimeter power measurements and hardware performance counter sampling. Based on these validations across a wide range of stressmarks, Java benchmarks, and non-Java benchmarks, XTREM has an average performance error of only 6.5% and an even smaller average power error: 4%. The paper goes on to present a selection of application studies enabled by the simulator. For example, presenting power behavior vs. time for selected embedded C and Java CLDC benchmarks, we can make power distinctions between the two programming domains as well as distinguishing Java application (JITted code) power from Java Runtime system power. We also study how the Intel XScale core 's power consumption varies for different data activity factors, creating power swings as large as 50mW for a 200Mhz core. We are planning to release XTREM for wider use, and feel that it offers a useful step forward for compiler and embedded software designers.

Speculative execution, such as control speculation or data speculation, is an effective way to improve program performance. Using edge/path profile information or simple heuristic rules, existing compiler frameworks can adequately incorporate and exploit control speculation. However, very little has been done so far to allow existing compiler frameworks to incorporate and exploit data speculation effectively in various program transformations beyond instruction scheduling. This paper proposes a speculative static single assignment form to incorporate information from alias profiling and/or heuristic rules for data speculation, thus allowing existing frameworks to be extended to support both control and data speculation. Such a general framework is very useful for EPIC architectures that provide run-time checking (such as advanced load address table ) on data speculation to guarantee the correctness of program execution. We use SSAPRE as one example to illustrate how to incorporate data speculation in partial redundancy elimination, register promotion, and strength reduction. Our extended framework allows both control and data speculations to be performed on top of SSAPRE and, thus, enables more aggressive speculative optimizations. The proposed framework has been implemented on Intel's Open Research Compiler. We present experimental data on some SPEC2000 benchmark programs to demonstrate the usefulness of this framework.

When performing aggressive optimizations and parallelization to exploit features of advanced architectures, optimizing and parallelizing compilers need to quantitatively assess the profitability of any transformations in order to achieve high performance. Useful optimizations and parallelization can be performed if it is known that certain points-to relationships would hold with high or low probabilities. For instance, if the probabilities are low, a compiler could transform programs to perform data speculation or partition iterations into threads in speculative multithreading, or it would avoid conducting code specialization. Consequently, it is essential for compilers to incorporate pointer analysis techniques that can estimate the possibility for every points-to relationship that it would hold during the execution. However, conventional pointer analysis techniques do not provide such quantitative descriptions and, thus, hinder compilers from more aggressive optimizations, such as thread partitioning in speculative multithreading, data speculations, code specialization, etc. We address this issue by proposing a probabilistic points-to analysis technique to compute the probability of every points-to relationship at each program point. A context-sensitive interprocedural algorithm has been implemented based on the iterative data flow analysis framework, and has been incorporated into SUIF and MachSUIF. Experimental results show this technique can estimate the probabilities of points-to relationships in benchmark programs with reasonable small errors, about 4.6 percent on average. Furthermore, the current implementation cannot disambiguate heap and array elements. The errors are further significantly reduced when the future implementation incorporates techniques to disambiguate heap and array elements.

A hardware managed register stack, Register Stack Engine (RSE), is implemented in Itanium® architecture to provide a unified and flexible register structure to software. The compiler allocates each procedure a register stack frame with its size explicitly specified using an alloc instruction. When the total number of registers used by the procedures on the call stack exceeds the number of physical registers, RSE performs automatically register overflows and fills to ensure that the current procedure has its requested registers available. The virtual register stack frames and RSE alleviate the need of explicit spills by the compiler, but our experimental results indicate that a trade-off exists between using stacked registers and explicit spills under high register pressure due to the uneven cost between them. In this work, we introduce the stacked register quota assignment problem based on the observation that reducing stacked register usage in some procedures could reduce the total memory access time of spilling registers, which includes the time caused by the loads/stores due to explicit register spills and RSE overflows/fills. We propose a new inter-procedural algorithm to solve the problem by allocating stacked registers across procedures based on a quantitative cost model. The results show that our approach can improve performance significantly for the programs with high RSE overflow cost, e.g. perlbmk and crafty, improved by 14% and 3.7%, respectively.

Compiler-directed data speculation has been implemented on Itanium systems to allow for a compiler to move a load across a store even when the two operations are potentially aliased This not only breaks data dependency to reduce critical path length, but also allows a load to be scheduled far apart from its uses to hide cache miss latencies. However, the effectiveness of data speculation is affected by the sophistication of alias analysis technique as well as the aggressiveness of the instruction scheduler. In general, the more sophisticated is the alias analysis technique, the less performance gain is from data speculation, and the more aggressive is the instruction scheduler, the more opportunity is for data speculation. In this paper we evaluate in various scenarios the performance potentials of data speculation for SPEC2000C benchmarks. For each scenario, we determine the performance contributions of data speculation due to both critical path reduction and cache miss latency reduction. We also show interesting statistics about the effects of scheduling constraints, the percentage of critical dependencies, the impacts of cache miss latencies, and the distances between the load locations before and after data speculation.

Speculative multithreading (SpMT) architecture can exploit thread-level parallelism that cannot be identified statically. Speedup can be obtained by speculatively executing threads in parallel that are extracted from a sequential program. However, performance degradation might happen if the threads are highly dependent, since a recovery mechanism will be activated when a speculative thread executes incorrectly and such a recovery action usually incurs a very high penalty. Therefore, it is essential for SpMT to quantify the degree of dependences and to turn off speculation if the degree of dependences passes certain thresholds. This paper presents a technique that quantitatively computes dependences between loop iterations and such information can be used to determine if loop iterations can be executed in parallel by speculative threads. This technique can be broken into two steps. First probabilistic points-to analysis is performed to estimate the probabilities of points-to relationships in case there are pointer references in programs, and then the degree of dependences between loop iterations is computed quantitatively. Preliminary experimental results show compiler-directed thread-level speculation based on the information gathered by this technique can achieve significant performance improvement on SpMT.

Current memory hierarchies exploit locality of references to reduce load latency and thereby improve processor performance. Locality based schemes aim at reducing the number of cache misses and tend to ignore the nature of misses. This leads to a potential mis-match between load latency requirements and latencies realized using a traditional memory system. To bridge this gap, we partition loads as critical and non-critical. A load that needs to complete early to prevent processor stalls is classified as critical, while a load that can tolerate a long latency is considered non-critical.

We present a new register promotion algorithm based on Static Single Assignment (SSA) form. Register promotion is aimed at promoting program names from memory locations to registers. Our algorithm is profile-driven and is based on the scope of intervals. In cases where a complete promotion is not possible because of the presence of function calls or pointer references, the proposed algorithm is capable of eliminating loads and stores on frequently executed paths by placing loads and stores on less frequently executed paths. We also describe an efficient method to incrementally update SSA form when new definitions are cloned from an existing name during register promotion. On SPECInt95 benchmarks, our algorithm removes about ~12% of memory operations which access scalar variables.

Multi-dimensional systems containing nested loops are widely used to model scientific applications such as image processing, geophysical signal processing and fluid dynamics. However, branches within these loops may degrade the performance of pipelined architectures. This paper presents the theory, supporting hardware and experiments of a novel technique, based on multi-dimensional retiming, for reducing pipeline hazards caused by branches within nested loops. This technique, called Multi-Dimensional Branch Anticipation Scheduling, is able to achieve near-optimal schedule length for nested loops containing branch instructions.

To fully utilize the wide machine resources in modern high-performance microprocessors it is necessary to exploit parallelism beyond individual basic blocks. Architectural support for predicated execution increases the degree of instruction level parallelism by allowing instructions from different basic blocks to be converted to straight-line code guarded by boolean predicates. However predicated execution also presents significant challenges to an optimizing compiler. For example, in live range analysis, a predicated definition does not necessarily end the live range of a virtual register. This paper describes techniques to analyze the relations among predicates in order to improve the precision and effectiveness of various compiler analysis and transformation phases in the presence of predicated code. Our predicate analysis operates globally to obtain relations among predicates. Moreover, we analyze control flow and predication in a single unified framework. The result can be queried by subsequent optimization and analysis phases. Based on this framework, we extend a traditional method to a predicate-aware register allocator which takes global predicate relations into account. We have implemented the proposed algorithms to effectively reduce register pressure. Our experimental results show 24.6% of a large test suite obtain, on average, 20.71% and better register allocation due to the algorithms presented in this paper.

An increasing number of programming languages, such as Fortran 90 and APL, are providing a rich set of intrinsic array functions and array expressions. These constructs which constitute an important part of data parallel languages provide excellent opportunities for compiler optimizations. In this paper, we present a new approach to combine consecutive data access patterns of array constructs into a composite access function to the source arrays. Our scheme is based on the composition of access functions, which is similar to a composition of mathematic functions. Our new scheme can handle not only data movements of arrays of different numbers of dimensions and segmented array operations but also masked array expressions and multiple sources array operations. As a result, our proposed scheme is the first synthesis scheme which can synthesize Fortran 90 RESHAPE, EOSHIFT, MERGE, and WHERE constructs together. Experimental results show speedups from 1.21 to 2.95 for code fragments from real applications on a Sequent multiprocessor machine by incorporating the proposed optimizations.

Array language provides an effective paradigm for developing portable parallel programs but will only be used if compilers generate efficient code for array operations this paper presents an inter-statement optimization technique which merges related array operations in different statements. A merged statement creates opportunities for previously developed inter-primitive optimizations of array operators The potential advantages of statement merge are the elimination of a program variable, demand driven evaluation, reductions of data movement and loop overhead. The combination of statement merge and inter-primitive optimizations achieves a 3 8 fold execution time speedup in a scientific application

We present a classification scheme for array language primitives that quantifies the variation in parallelism and data locality that results from the fusion of any two primitives. We also present an algorithm based on this scheme that efficiently determines when it is beneficial to fuse any two primitives. Experimental results show that five LINPACK routines report 50% performance improvement from the fusion of array operators.>

Programs written m APL implicitly contain data parallelism because the high level APL primitives denoting array o erations may be executed in parallel.Our experiment $ APL/C compiler translates ordinary APL programs into the C language with additional parallel constmcts for synchronization support.We target the RP3, a shared-memory MIMD machine built at IBM T.J. WatsonResearch Center, running the Mach operating system.The compiler uses Mach kernel prirmtives to build a parallel run-time environment to reduce the run-time overhead.We have developed a novel method for dynamically determining the required number of processors for a primitive function.The compiler can further apply a form of the loop fusion technique to groups of scalar primitive functions to gain additional improvement.