The Experts below are selected from a list of 6471 Experts worldwide ranked by ideXlab platform

Michael Schlansker - One of the best experts on this subject based on the ideXlab platform.

  • global predicate analysis and its application to register allocation
    International Symposium on Microarchitecture, 1996
    Co-Authors: David Mitford Gillies, Richard Johnson, Michael Schlansker
    Abstract:

    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. How ever, 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% better register allocation due to the algorithms presented in this paper.

  • Global Predicate Analysis and its Application to Register Allocation
    1996
    Co-Authors: David Gillies, Richard Johnson, Ju Richard Johnson, Michael Schlansker
    Abstract:

    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 queri..

Craig Chambers - One of the best experts on this subject based on the ideXlab platform.

  • a retrospective on customization Optimizing Compiler technology for self a dynamically typed object oriented programming language
    Programming Language Design and Implementation, 2004
    Co-Authors: Craig Chambers, David Ungar
    Abstract:

    Dynamically-typed object-oriented languages please programmers, but their lack of static type information penalizes performance. Our new implementation techniques extract static type information from declaration-free programs. Our system compiles several copies of a given procedure, each customized for one receiver type, so that the type of the receiver is bound at compile time. The Compiler predicts types that are statically unknown but likely, and inserts run-time type tests to verify its predictions. It splits calls, compiling a copy on each control path, optimized to the specific types on that path. Coupling these new techniques with compile-time message lookup, aggressive procedure inlining, and traditional optimizations has doubled the performance of dynamically-typed object-oriented languages.

  • A framework for call graph construction algorithms
    ACM Transactions on Programming Languages and Systems, 2001
    Co-Authors: David Grove, Craig Chambers
    Abstract:

    A large number of call graph construction algorithms for object-oriented and functional languages have been proposed, each embodying different tradeoffs between analysis cost and call graph precision. In this article we present a unifying framework for understanding call graph construction algorithms and an empirical comparison of a representative set of algorithms. We first present a general parameterized algorithm that encompasses many well-known and novel call graph construction algorithms. We have implemented this general algorithm in the Vortex Compiler infrastructure, a mature, multilanguage, Optimizing Compiler. The Vortex implementation provides a "level playing field" for meaningful cross-algorithm performance comparisons. The costs and benefits of a number of call graph construction algorithms are empirically assessed by applying their Vortex implementation to a suite of sizeable (5,000 to 50,000 lines of code) Cecil and Java programs. For many of these applications, interprocedural analysis enabled substantial speed-ups over an already highly optimized baseline. Furthermore, a significant fraction of these speed-ups can be obtained through the use of a scalable, near-linear time call graph construction algorithm.

  • fast interprocedural class analysis
    Symposium on Principles of Programming Languages, 1998
    Co-Authors: Greg Defouw, David Grove, Craig Chambers
    Abstract:

    Previous algorithms for interprocedural control flow analysis of higher-order and/or object-oriented languages have been described that perform propagation or constraint satisfaction and take O(N3) time (such as Shivers's O-CFA and Heintze's set-based analysis), or unification and take O(Nα (N,N) time (such as Steensgaard's pointer analysis), or optimistic reachability analysis and take O(N) time (such as Bacon and Sweeney's Rapid Type Analysis). We describe a general parameterized analysis framework that integrates propagation-based and unification-based analysis primitives and optimistic reachability analysis, whose instances mimic these existing algorithms as well as several new algorithms taking O(N), O(Nα(N,N)), O(N2), and O(N2α(N,N)) time; our O(N) and O(Nα(N,N)) algorithms produce more precise results than the previous algorithms with these complexities. We implemented our algorithm framework in the Vortex Optimizing Compiler, and we measured the cost and benefit of these interprocedural analysis algorithms in practice on a collection of substantial Cecil and Java programs.

  • frameworks for intra and interprocedural dataflow analysis
    1998
    Co-Authors: Craig Chambers, Jeffrey Dean, David Grove
    Abstract:

    Because dataflow analyses are difficult to implement from scratch, reusable dataflow analysis frameworks have been developed which provide generic support facilities for managing propagation of dataflow information and iteration in loops. We have designed a framework that improves on previous work by making it easy to perform graph transformations as part of iterative analysis, to run multiple analyses “in parallel” to achieve the precision of a single monolithic analysis while preserving modularity and reusability of the component analyses, and to construct contextsensitive interprocedural analyses from intraprocedural versions. We have implemented this framework in the Vortex Optimizing Compiler and used the framework to help build both traditional optimizations and non-traditional optimizations of dynamically-dispatched messages and first-class, lexically-nested functions.

  • the design and implementation of the self Compiler an Optimizing Compiler for object oriented programming languages
    1992
    Co-Authors: Craig Chambers
    Abstract:

    Object-oriented programming languages promise improved programmer productivity through abstract data types, inheritance, and message passing. Unfortunately, traditional implementations of object-oriented language features are much slower than traditional implementations of their non-object-oriented counterparts. This dissertation describes a collection of implementation techniques that can improve the run-time performance of object-oriented languages. The new techniques identify those messages whose receiver can only be of a single representation and eliminate the overhead of message passing by replacing the message with a normal direct procedure call; these direct procedure calls are then amenable to traditional inline-expansion. Type analysis extracts representation-level type information about the receivers of messages. Customization transforms a single source method into several compiled versions, each version specific to a particular inheriting receiver type; customization allows all messages to self to be inlined away (or at least replaced with direct procedure calls). To avoid generating too much compiled code, the Compiler is invoked at run-time, generating customized versions only for those method/receiver type pairs used by a particular program. Splitting transforms a single path through a source method into multiple separate fragments of compiled code, each fragment specific to a particular combination of run-time types. Messages to expressions of these discriminated types can then be optimized away in the split versions. These techniques have been implemented as part of the Compiler for the SELF language, a purely object-oriented language designed as a refinement of Smalltalk-80. If only pre-existing implementation technology were used for SELF, programs in SELF would run one to two orders of magnitude slower than their counterparts written in a traditional non-object-oriented language. However, by applying the techniques described in this dissertation, the performance of the SELF system is five times better than the fastest Smalltalk-80 system, better than that of an Optimizing Scheme implementation, and close to half that of an Optimizing C implementation. These techniques could be applied to other object-oriented languages to boost their performance or enable a more object-oriented programming style.

David Mitford Gillies - One of the best experts on this subject based on the ideXlab platform.

  • global predicate analysis and its application to register allocation
    International Symposium on Microarchitecture, 1996
    Co-Authors: David Mitford Gillies, Richard Johnson, Michael Schlansker
    Abstract:

    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. How ever, 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% better register allocation due to the algorithms presented in this paper.

Richard Johnson - One of the best experts on this subject based on the ideXlab platform.

  • global predicate analysis and its application to register allocation
    International Symposium on Microarchitecture, 1996
    Co-Authors: David Mitford Gillies, Richard Johnson, Michael Schlansker
    Abstract:

    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. How ever, 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% better register allocation due to the algorithms presented in this paper.

  • Global Predicate Analysis and its Application to Register Allocation
    1996
    Co-Authors: David Gillies, Richard Johnson, Ju Richard Johnson, Michael Schlansker
    Abstract:

    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 queri..

Thomas M Conte - One of the best experts on this subject based on the ideXlab platform.

  • Compiler driven cached code compression schemes for embedded ilp processors
    International Symposium on Microarchitecture, 1999
    Co-Authors: Sergei Y Larin, Thomas M Conte
    Abstract:

    During the last 15 years, embedded systems have grown in complexity and performance to rival desktop systems. The architectures of these systems present unique challenges to processor microarchitecture, including instruction encoding and instruction fetch processes. This paper presents new techniques for reducing embedded system code size without reducing functionality. This approach is to extract the pipeline decoder logic for an embedded VLIW processor in software at system development time. The code size reduction is achieved by Huffman compressing or tailor encoding the ISA of the original program. Some interesting results were found. In particular, the degree of compression for the ROM doesn't translate into an improvement in instructions delivered per cycle. Experiments found that when the missprediction penalty of the added Huffman decoder stage was taken into account, a Tailored ISA approach produced higher performance. Methods that compress the entire operation using Huffman encodings, and decompress at ICache hit time still achieved a median performance advantage, while providing higher ROM size savings. All results were generated by an Optimizing Compiler and tool suite, and presented for an encoding similar to the Intel/HP IA-64 architecture.