摘要:

AbstractSingle‐assignment and functional languages have value semantics that do not permit side‐effects. This lack of side‐effects makes automatic detection of parallelism and optimization for data locality in programs much easier. However, the same property poses a challenge in implementing these languages efficiently. This paper describes an optimizing compiler system that solves the key problem of aggregate copy elimination. The methods developed rely exclusively on compile‐time algorithms, including interprocedural analysis, that are applied to an intermediate data flow representation. By dividing the problem into update‐in‐place and build‐in‐place analysis, a small set of relatively simple techniques—edge substitution, graph pattern matching, substructure sharing and substructure targeting—was found to be very powerful. If combined properly and implemented carefully, the algorithms eliminate unnecessary copy operations to a very high degree. No run‐time overhead is imposed on

ISSN:0038-0644    

DOI:10.1002/spe.4380231102

出版商:John Wiley&Sons, Ltd.    

年代:1993

数据来源: WILEY

摘要:

AbstractWe report our experiences with the implementation ofInterProcedural Alias Analysis(IPA) for Fortran. Implicit aliasing caused by reference parameter passing can be uncovered in a program with multiple compilation units by interprocedural analysis. For scalar objects and for full arrays, the IPA processor described here finds all alias relations. For indexed array elements and partial arrays, conservative assumptions must still be made in the absence of precise knowledge about the subscripts. IPA has been integrated intonascent, the front‐end of a Fortran translator under development at the Oregon Graduate Institute (OGI). This report explains the goals and limitations of alias analysis for conventional procedural languages with reference parameters, shows in detail the actual design and implementation of IPA, and provides algorithmic and speed improvements over the best previously known aliasing algorithms. Empirical results gathered during the analysis of large Fortran programs are also listed and discusse

ISSN:0038-0644    

DOI:10.1002/spe.4380231103

出版商:John Wiley&Sons, Ltd.    

年代:1993

数据来源: WILEY

摘要:

AbstractThe HAGAR project is building a high‐performance disk controller. It is an embedded system for which many hundreds of thousands of lines of embedded software will have to be developed concurrently with the development of the hardware. We found existing methods for embedded software development, such as simulation and remote cross development, to be inadequate for us. To meet our special needs, we developed a distributed development environment that combines and extends the capabilities of existing methods while fixing their drawbacks.Our environment is based on a processor‐pool architecture, in which multiple hardware sets are pooled and managed systematically. It supports embedded software development for many programmers at different sites. It allows for the emulation of non‐existing hardware adaptor cards and for the integration of embedded software testing with hardware simulation. The environment provides a single system image, hiding many hardware and configuration details from its users. From the perspective of the programmers, our environment makes developing embedded software for special hardware systems as easy as developing application programs for a UNIX workst

ISSN:0038-0644    

DOI:10.1002/spe.4380231104

出版商:John Wiley&Sons, Ltd.    

年代:1993

数据来源: WILEY

摘要:

AbstractWe recount the history of a new qsortfunction for a C library. Our function is clearer, faster and more robust than existing sorts. It chooses partitioning elements by a new sampling scheme; it partitions by a novel solution to Dijkstra's Dutch National Flag problem; and it swaps efficiently. Its behavior was assessed with timing and debugging testbeds, and with a program to certify performance. The design techniques apply in domains beyond sorting.

ISSN:0038-0644    

DOI:10.1002/spe.4380231105

出版商:John Wiley&Sons, Ltd.    

年代:1993

数据来源: WILEY

摘要:

AbstractIn recent years several authors have investigated binary search trees with minimal internal path length. In this paper we propose relaxing the requirement of inserting all nodes on one level before going to the next level. This leads to a new class of binary search trees called ISA [k] trees. We investigated the average locate cost per node, average shift cost per node, total insertion cost, and average successful search cost for ISA[k] trees. We also present an insertion algorithm with associated predecessor and successor functions for ISA[k] trees. For large binary search trees (over 160 nodes) our results suggest the use of ISA[2]or ISA[3] trees for best performance.

ISSN:0038-0644    

DOI:10.1002/spe.4380231106

出版商:John Wiley&Sons, Ltd.    

年代:1993

数据来源: WILEY

ISSN:0038-0644    

DOI:10.1002/spe.4380231101

出版商:John Wiley&Sons, Ltd.    

年代:1993

数据来源: WILEY