phase-ordering optimizations (SUMMARY)

This is a summary of replies to my comp.compiler request for information
on phase ordering and integrating optimizations. Many thanks to all who
sent references/comments!


My original posting:
      I'm looking for references to work on interactions between various
      compiler optimizations. Specifically, I'd be interested in references to
      papers on the ordering of optimization phases, integration of optimization
      phases to eliminate the need for ordering, and cooperation between
      optimizations and scheduling & resource allocation. I'm familiar with
      Joshi & Dhamdhere's work on combining strengh reduction and code hoisting,
      with Goodman & Hsu's algorithm for combining reg.allocation and code
      scheduling in basic blocks, and with Ruttenberg and Freundenberger's work
      on combining instruction scheduling and global register allocation.


References to the papers I mentioned:


@article{ JD82a:ijcm,
      author = "S. M. Joshi and D. M. Dhamdhere",
      title = "A Composite Hoisting--Strength Reduction Transformation
for Global Program Optimization (Part I)",
      journal = "Int. J. of Computer Math",
      pages = {22-41},
      year = 1982
}


@article{ JD82b:ijcm,
      author = "S. M. Joshi and D. M. Dhamdhere",
      title = "A Composite Hoisting--Strength Reduction Transformation
for Global Program Optimization (Part II)",
      journal = "Int. J. of Computer Math",
      pages = {111-126},
      year = 1982
}


@inproceedings{ GH88:ics,
      author = "James R. Goodman and {Wei-Chung} Hsu",
      title = "Code Scheduling and Register Allocation in Large
Basic Blocks",
      booktitle = "Proc. of the 1988 Int. Conference on Supercomputing",
      address = "St. Malo, France",
      note = "Published by SIGARCH Computer Architecture News",
      month = "July 4--8, "
      year = 1988,
      pages = {442-452},
}


@unpublished{ RF91:unpub,
      author = "John C. Ruttenberg and Stefan M. Freudenberger",
      title = "Phase Ordering of Register Allocation
and Instruction Scheduling",
      booktitle = "Workshop on Code Generation -- Concepts, Tools,
       Techniques",
      month = apr,
      year = 1991,
}
[ I do not know whether the proceedings of this workshop were ever published.
    The workshop was somewhere in Germany in 1991. ]


------------------------------------------------------------------------------
Eliot Moss (moss%ibis@cs.umass.edu), Steve Walk (srw@ihlpv.att.com), and
Martin Meyer <martin@uni-paderborn.de> suggested the following paper:


@inproceedings{ Whitfield&Soffa1990,
      author = "Debbie Whitfield and Mary Lou Soffa",
      title = "An Approach to Ordering Optimizing Transformations",
      booktitle = "Second {ACM} {SIGPLAN} Symposium on Principles and
Practice of Parallel Programming",
      address = "Seattle, Washington",
      month = "March 14--16, ",
      year = 1990,
      pages = {137-147},
      note = "Published as {ACM SIGPLAN} Notices 25(3)",
}


-------------------------------------------------------------------------------
from anton@mips.complang.tuwien.ac.at (Anton Martin Ertl):


The following article extends Goodman&Hsu's Integrated Prepass
Scheduling to colouring global register allocation and introduces
another algorithm:


@InProceedings{bradlee+91asplos,
    author = "David G. Bradlee and Susan J. Eggers and Robert R. Henry",
    title = "Integrating Register Allocation and Instruction
Scheduling for {RISCs}",
    booktitle = asplos,
    year = "1991",
    pages = "122--131"
}


One of the claimned advantages of the Davidson&Fraser approach to Code
generation is the ability to apply the phases in arbitrary order (and
repeatedly), solving many phase ordering problems. I find in my
bibliography the following references. You probably should read
benitez&davidson88 first, which presents a nice overview of the approach.


@inproceedings(davidson86,
author="Jack W. Davidson",
title="A Retargetable Instruction Reorganizer",
booktitle="Proceedings of the SIGPLAN '86 Symposium on Compiler
Construction",
year="1986",
pages="234--241"
)


@Article{davidson&fraser84,
    author = "Jack W. Davidson and Christopher W. Fraser",
    title = "Code Selection through Object Code Optimization",
    journal = toplas,
    year = "1984",
    volume = "6",
    number = "4",
    pages = "505--526",
    month = oct
}


@InProceedings{benitez&davidson88,
    author = "Manuel E. Benitez and Jack W. Davidson",
    title = "A Portable Global Optimizer and Linker",
    booktitle = "Proceedings of the SIGPLAN '88 Conference on
Programming Language Design and Implementation",
    year = "1988",
    pages = "329--338"
}


@InProceedings{fraser&wendt88,
    author = "Christopher W. Fraser and Alan L. Wendt",
    title = "Automatic Generation of Fast Optimizing Code Generators",
    booktitle = "Proceedings of the SIGPLAN '88 Conference on
Programming Language Design and Implementation",
    year = "1988",
    pages = "79--84"
}


Coagulation was developped for solving the
code-selection/register-allocation phase ordering problem. It's
similar to Ruttenberg&Freudenberger's work.


@InProceedings{morris91,
    author = "W. G. Morris",
    title = "{CCG}: A Prototype Coagulating Code Generator",
    booktitle = "Proceedings of the SIGPLAN '91 Conference on
Programming Language Design and Implementation",
    year = "1991",
    pages = "45--58",
    address = "Toronto",
    month = jun
}


The original article on coagulation is in the SIGPLAN '84 Proceedings.


- anton


---
The original coagulation paper is:
@inproceedings{ Kar84:socc,
      author = "Michael Karr",
      title = "Code Generation by Coagulation",
      booktitle = "Proc. 1984 SIGPLAN Symposium on Compiler Construction",
      address = "Montreal, Canada"
      month = "June 17--22, ",
      year = 1984,
      pages = {1-12},
      note = "Published as ACM SIGPLAN Notices 19(6)"
}


I also found the following paper by Fraser&Wendt:
@inproceedings{ FW86:socc,
      author = "Christopher W. Fraser and Alan L. Wendt",
      title = "Integrating Code Generation and Optimization",
      booktitle = "Proc. of the 1986 SIGPLAN Symp. on Compiler Construction",
      address = "Palo Alto, California",
      month = "June 25--27, ",
      year = 1986,
      pages = {242-248},
      note = "Published as ACM SIGPLAN Notices 21(7)",
}


-------------------------------------------------------------------------------
Reply-To: berson@cs.pitt.edu (David A. Berson)


> Specifically, I'd be interested in references to
> papers on the ordering of optimization phases, integration of optimization
> phases to eliminate the need for ordering, and cooperation between
> optimizations and scheduling & resource allocation.


How about the following?
%A Deborah Whitfield
%A Mary Lou Soffa
%T Automatic Generation of Global Optimizers
%P 120-129
%J PROC SIGPLAN '91 CONF PLDI
%D JUN 26-28, 1991
%C Toronto, Ontario, Canada


%A Deborah Lynn Whitfield
%T A Unifying Framework For Optimizing Transformations
%I Ph.D. Dissertation, University of Pittsburgh
%R TECH REPORT 91-24
%D 1991


This looks at how different optimizations can impact each other and then
suggests orderings. The paper is taken from the dissertation.


-------------------------------------------------------------------------------
Reply-To: Arild Skjolsvold <arilds@microsoft.com>


A book called "Register Allocation in Optimizing Compilers" discusses
the phase ordering problem. This book describes the PQCC project, so
other papers about that project is relevant as well I'd guess. The
author of the book?? I can't remember, sorry...


-arild


---
The book reference is:
@book{ Lev83:book,
      author = "Bruce W. Leverett",
      title = "Register Allocation in Optimizing Compilers",
      year = 1983,
      publisher = "UMI Research Press",
      address = "Ann Arbor, Mich."
}


-------------------------------------------------------------------------------
Reply-To: Martin Meyer <martin@uni-paderborn.de>


In addition to Whitfield&Soffa1990, Martin suggested:


%A Deborah Whitfield
%T A Unifying Framework for Optimizing Transformations
%J Technical Report 91-24
%I University of Pittsburgh, Pennsylvania


It describes dependences, enabling and disabling conditions for
various optimizing transformations (standard transformations as well
as loop transformations).


Hope, it helps.


- martin


-------------------------------------------------------------------------------
Reply-To: loegel@redfox.ssc.gov (George Loegel)


Giegerich, R. "Logic Specification of Code Generation Techniques",
Lecture Notes in Computer Science No. 217, pp. 96-111, 1985


In this paper each kind of optimization is described as an algebraic
transformation and combining optimizations is simply a matter of
sequencing the transformations. Giegerich describes these algebras in
PROLOG. Code generation takes place by satisfying a set of conditions
between the input to the code generator and the target machine.
---
[ LNCS #217 title is "Programs as Data Objects" ]


-------------------------------------------------------------------------------
Richard Johnson
rjohnson@cs.cornell.edu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.