common-subexpr.bib

% -*- Mode: BibTeX -*-
%
% Common subexpression elimination bibliography








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Lexically identical
%





@Article{Ullman73,
  author = 	 "J. D. Ullman",
  title = 	 "Fast Algorithms for the Elimination of Common Subexpressions",
  journal =	 "Acta Informatica",
  year =	 1973,
  volume =	 2,
  number =	 3,
  pages =	 "191--213"
}


@article{MorelR79,
  title="Global Optimization by Suppression of Partial Redundancies",
  author="Etienne Morel and Claude Renvoise",
  journal=cacm,
  year=1979,
  volume=22,
  number=2,
  month=feb,
  pages="96--103"
}


@article{DrechslerS88,
  title="A Solution to a Problem with {Morel} and {Renvoise's}
                 ``{Global} Optimization by Suppression of Partial
                 Redundancies''",
  author="Karl-Heinz Drechsler and Manfred P. Stadel",
  pages="635--640",
  journal=toplas,
  year=1988,
  month=oct,
  volume=10,
  number=4
}


@article{Sorkin89,
  title="Some Comments on ``{A} Solution to a Problem with {M}orel and
                 {R}envoise's `{G}lobal Optimization by Suppression of
                 Partial Redundancies'\,''",
  author="Arthur Sorkin",
  pages="666--668",
  journal=toplas,
  year=1989,
  month=oct,
  volume=11,
  number=4
}


@ARTICLE{Dhamdhere90,
   AUTHOR      = "D. M. Dhamdhere",
   TITLE    = "A Usually Linear Algorithm for Register Assignment Using
	       Edge Placement of Load and Store Instructions",
   JOURNAL     = "Computer Languages",
   VOLUME      = 15,
   NUMBER      = 2,
   PAGES    = {83--94},
   YEAR     = 1990}

@ARTICLE{JoshiD82:i,
   AUTHOR      = "S. M. Joshi and D. M. Dhamdhere",
   TITLE    = "A Composite Hoisting-Strength Reduction Transformation for
	       Global Program Optimization:  Part {I}",
   JOURNAL     = IJCM,
   VOLUME      = 11,
   PAGES    = {21--41},
   YEAR     = 1982}

@ARTICLE{JoshiD82:ii,
   AUTHOR      = "S. M. Joshi and D. M. Dhamdhere",
   TITLE    = "A Composite Hoisting-Strength Reduction Transformation for
	       Global Program Optimization:  Part {II}",
   JOURNAL     = IJCM,
   VOLUME      = 11,
   PAGES    = {111--126},
   YEAR     = 1982}


@TECHREPORT{Chow83,
   AUTHOR      = "F. C. Chow",
   TITLE    = "A Portable Machine-independent Global Optimizer---Design and
	       Measurements",
   INSTITUTION = "Stanford University",
   NUMBER      = "TR 83-254",
   MONTH    = Dec,
   YEAR     = 1983}




@InProceedings{DhamdhereRZ92,
  author = 	 "Dhananjay M. Dhamdere and Barry K. Rosen and F. Kenneth
		  Zadeck",
  title = 	 "How to analyze large programs efficiently and informatively",
  crossref =     "PLDI92",
  pages =	 "212--223",
}


@InProceedings{KnoopRS92,
  author = 	 "Jens Knoop and Oliver R{\"u}thing and Bernhard Steffen",
  title = 	 "Lazy code motion",
  crossref =     "PLDI92",
  pages =	 "224--234",
}


@Article{DrechslerS93,
  author = 	 "Karl-Heinz Drechsler and Manfred P. Stadel",
  title = 	 "A variation of {K}noop, {R}{\"u}thing, and {S}teffen's {\em
		  {L}azy Code Motion}",
  journal =	 SIGPLANNotices,
  year =	 1993,
  volume =	 28,
  number =	 5,
  pages =	 "29--38",
  month =	 May
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Value numbering
%



@TechReport{CockeS70,
  author = 	 "John Cocke and Jacob T. Schwartz",
  title = 	 "Programming Languages and Their Compilers",
  institution =  "Courant Institute, NYU",
  year = 	 1970,
  month =	 apr,
  note =	 "Preliminary notes"
}




@Article{Cocke70,
  author = 	 "John Cocke",
  title = 	 "Global common subexpression elimination",
  journal =	 "SIGPLAN Notices",
  year =	 1970,
  volume =	 5,
  number =	 7,
  month =        Jul,
  pages =	 "20--24"
}


@CONFERENCE{Rosen88,
  title="Global Value Numbers and Redundant Computations",
  author="Barry K. Rosen and Mark N. Wegman and F. Kenneth Zadeck",
   crossref   = "POPL88",
   PAGES    = {12--27},
}


@CONFERENCE{AlpernWZ88,
  title="Detecting Equality of Variables in Programs",
  author="Bowen Alpern and Mark N. Wegman and F. Kenneth Zadeck",
  crossref   = "POPL88",
   PAGES    = {296--306},
}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



@Book{AhoSU86,
  author = 	 "Alfred V. Aho and Ravi Sethi and Jeffrey D. Ullman",
  title = 	 "Compilers:  Principles, Techniques, and Tools",
  publisher = 	 "Addison-Wesley",
  year = 	 1986,
  OMITseries =	 "Computer Science Series",
  address =	 "Reading, Massachusetts"
}


@Article{BrunoS76,
  author = 	 "John Bruno and Ravi Sethi",
  title = 	 "Code generation for a one-register machine",
  journal =	 JACM,
  year =	 1976,
  volume =	 23,
  number =	 3,
  pages =	 "502--510",
  month =	 Jul
}


@Article{AhoJU77,
  author = 	 "A. V. Aho and S. C. Johnson and J. D.  Ullman",
  title = 	 "Code Generation for Expressions with Common Subexpressions",
  journal =	 JACM,
  year =	 1977,
  volume =	 24,
  number =	 1,
  pages =	 "146--160",
  month =	 Jan
}


@InCollection{Jarke85,
  author = 	 "Mattias Jarke",
  title = 	 "Common Subexpression Isolation in Multiple Query Optimization",
  booktitle = 	 "Query Processing in Database Systems",
  publisher =	 "Springer-Verlag",
  year =	 1985,
  editor =	 "Won Kim and Davis S. Reiner and Don S. Batory",
  pages =	 "191--205",
  series =	 "Topics in Information Systems",
  address =	 "Berlin"
}


@Article{SmithC75,
  author = 	 "John Miles Smith and Philip Yen-Tang Chang",
  title = 	 "Optimizing the Performance of a Relational Algebra
		  Database Interface",
  journal =	 CACM,
  year =	 1975,
  volume =	 18,
  number =	 10,
  pages =	 "568--579",
  month =	 Oct
}


@Article{Hall76,
  author = 	 "Patrick A. V. Hall",
  title = 	 "Optimization of Single Expressions in a Relational Data
		  Base System",
  journal =	 "IBM Journal of Research and Development",
  year =	 1976,
  volume =	 20,
  pages =	 "244--257",
  month =	 May
}


@TechReport{Hall74,
  author = 	 "Patrick A. V. Hall",
  title = 	 "Common Subexpression Identification in General Algebraic
		  Systems",
  institution =  "IBM United Kingdom Scientific Centre",
  year = 	 1974,
  number =	 "UKSC 0060",
  address =	 "Peterlee, County Durham, England",
  month =	 Nov
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Memoization
%

@Book{AbelsonS85,
  author = 	 "Harold Abelson and Gerald Jay Sussman",
  title = 	 "Structure and Interpretation of Computer Programs",
  publisher = 	 "MIT Press and McGraw-Hill",
  year = 	 1985,
  series =	 "MIT Electrical Engineering and Computer Science Series"
}


@InProceedings{PughT89,
  author = 	 "William Pugh and Tim Teitelbaum",
  title = 	 "Incremental Computation via Function Caching",
  booktitle =	 "Principles of Programming Languages",
  pages =	 "315--328",
  year =	 1989
}






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Reordering or reassociation
%





@Misc{Meadows92:personal,
  author =	 "Larry Meadows",
  howpublished = "Personal communication",
  year =	 1992
}


@InProceedings{Mercer88,
  author = 	 "Randall Mercer",
  title = 	 "The {CONVEX} {FORTRAN} 5.0 Compiler",
  editor =	 "Lana P. Kartashev and Steven I. Kartashev",
  volume =	 "II",
  booktitle =	 "Third International Conference on Supercomputing",
  pages =	 "164--175",
  year =	 1988,
  address =	 "Boston, Massachusetts",
  month =	 May
}


@Misc{Hicks92:personal,
  author =	 "James E. Hicks",
  howpublished = "Personal communication",
  year =	 1992
}
@TechReport{Traub86,
  author = 	 "Kenneth R. Traub",
  title = 	 "A Compiler for the {MIT} Tagged-Token Dataflow Architecture",
  institution =  MITLCS,
  year = 	 1986,
  number =	 "MIT-LCS-TR-370",
  address =	 "Cambridge, Massachusetts",
  month =	 Aug
}


@TechReport{HallT74,
  author = 	 "P. A. V. Hall and S. J. P. Todd",
  title = 	 "Factorizations of Algebraic Expressions",
  institution =  "IBM United Kingdom Scientific Centre",
  year = 	 1974,
  number =	 "UKSC 0055",
  address =	 "Peterlee, County Durham, England",
  month =	 Apr
}


@Article{Frailey70,
  author = 	 "D. J. Frailey",
  title = 	 "Expression Optimization Using Unary Compliment Operators",
  journal =	 "SIGPLAN Notices",
  year =	 1970,
  volume =	 5,
  number =	 7,
  pages =	 "42--51",
  month =	 Jul
}


@Article{Breuer69,
  author = 	 "Melvin A. Breuer",
  title = 	 "Generation of Optimal Code for Expressions via Factorization",
  journal =	 CACM,
  year =	 1969,
  volume =	 12,
  number =	 6,
  pages =	 "333--340",
  month =	 Jun
}




@CONFERENCE{AuslanderH82,
   AUTHOR      = "M. Auslander and M. Hopkins",
   TITLE    = "An Overview of the {PL.8} Compiler",
   crossref   = "CC82",
   PAGES    = {22--31},
}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Loop unrolling
%




@Article{WeissS90,
  author = 	 "Shlomo Weiss and James E. Smith",
  title = 	 "A study of scalar compilation techniques for pipelined
		  supercomputers",
  journal =	 "ACM Transactions on Mathematical Software",
  year =	 1990,
  volume =	 16,
  number =	 3,
  pages =	 "223--245",
  month =	 Sep
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Manuals
%

@Manual{IBMXLFORTRAN,
  title = 	 "XL FORTRAN Compiler/6000 Version 2.2 User's Guide",
  organization = "IBM"
}

@Manual{IBMXLC,
  title = 	 "XL C User's Guide",
  organization = "IBM"
}




@Manual{Stallman92,
  title = 	 "Using and Porting {GNU} {CC}",
  author =	 "Richard M. Stallman",
  organization = "Free Software Foundation",
  address =	 "Cambridge, Massachusetts",
  year =	 1992,
  month =	 Feb,
  note = 	 "For GNU CC version 2.0."
}


@Manual{Stallman89,
  title = 	 "The {C} Preprocessor",
  author =	 "Richard M. Stallman",
  organization = "Free Software Foundation",
  address =	 "Cambridge, Massachusetts",
  year =	 1989,
  month =	 Apr,
  edition = 	 "First"
}


@Manual{suncc,
  title = 	 "{C} Programmer's Guide",
  organization = "Sun Microsystems",
  year =	 1989,
  note =	 "Part number 800-3844-10"
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Etc.
%

@TechReport{CockeM80,
  author = 	 "John Cocke and Peter Markstein",
  title = 	 "Measurement of Program Improvement Algorithms",
  institution =  "IBM Thomas J. Watson Research Center",
  year = 	 1980,
  type =	 "Computer Science",
  number =	 35193,
  address =	 "Yorktown Heights, New York",
  month =	 Feb # "~7,"
}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% From Knoop
%%%

@STRING{complang="Journal of Computer Languages"}
@STRING{jpl="Journal of Programming Languages"}
@STRING{sigplannot="{ACM SIGPLAN} Notices"}

@STRING{esop="European Symposium on Programming (ESOP)"}
@STRING{pldi="{ACM SIGPLAN} Conference on Programming Language Design and Implementation"}
@STRING{popl="{ACM} Symposium on the Principles of Programming Languages"}
@STRING{tapsoft="International Joint Conference on Theory and Practice of Software Development (TAPSOFT)"}


@phdthesis{Chowphd,
    author = {Chow, F.},
    title  = {A portable machine independent optimizer -- {Design} and
    	measurements},
    school  = {Stanford University, Dept.\ of Electrical Engineering},
    address = {Stanford, CA},
    note = {{P}ublished as {T}ech.\ {R}ep.\ 83-254, {C}omputer {S}ystems
    	{L}ab., {S}tanford {U}niversity},
    year = {1983}
}

@booklet{CS70,
  author = {Cocke, J. and Schwartz,  J. T.},
  title = {Programming Languages and Their Compilers},
  howpublished = {Courant Institute of Mathematical Sciences, NY},
  year = {1970}
}

@article{Dh83,
   author = {Dhamdhere, D. M.},
   title =  {Characterization of program loops in code optimization},
   journal = complang,
    volume = {8},
    number = {2},
    pages = {69--76},
    year = {1983}
}

@article{Dh88,
   author = {Dhamdhere, D. M.},
   journal = sigplannot,
   number = {10},
   pages = {172--180},
   title = {A fast Algorithm for Code Movement Optimization},
   volume = {23},
   year = {1988}
}

@article{Dh89,
   author = {Dhamdhere, D. M.},
   journal = ijcm,
   pages = {1--14},
   title = {A new Algorithm for Composite Hoisting and Strength
           Reduction Optimisation},
   volume = {27},
   year = {1989}
}

@article{Dhcorr,
   author = {Dhamdhere, D. M.},
   journal = ijcm,
   title = {Corrigendum: {A} new Algorithm for Composite Hoisting and Strength
           Reduction Optimisation},
   year = {1989}
}

@article{Dh91,
   author = {Dhamdhere, D. M.},
   journal = toplas,
   number = 2,
   pages = {291--294},
   title = {Practical Adaptation of the Global Optimization
  Algorithm of {M}orel and {R}envoise},
   volume = 13,
   year = 1991,
   note = {Technical Correspondence}
}

@inproceedings{DRZPLDI92,
   author = {Dhamdhere, D. M. and Rosen, B. K. and Zadeck, F. K.},
   title = {How to Analyze Large Programs Efficiently and Informatively},
  crossref =     "PLDI92",
   pages = {212--223},
}

@article{DS88,
   author = {Drechsler, K.-H. and Stadel, M. P.},
   journal = toplas,
   number = 4,
   pages = {635--640},
   title = {A solution to a Problem with {M}orel and {R}envoise's
           ``{G}lobal Optimization by Suppression of Partial
           Redundancies''},
   volume = 10,
   note = {Technical Correspondence},
   year = 1988
}

@article{DS93,
   author = {Drechsler, K.-H. and Stadel, M. P.},
   journal = sigplannot,
   volume = 28,
   number = 5,
   pages = {29--38},
   title = {A variation of Knoop,  R\"uthing and Steffen's Lazy Code Motion},
   year = 1993
}

@article{JD82a,
   author = {Joshi, S. M. and Dhamdhere, D. M.},
   journal = ijcm,
   pages = {21--41},
   title = {A Composite Hoisting-Strength Reduction Transformation for
   	Global Program Optimization -- Part  {I}},
   volume = {11},
   year = {1982}
}

@article{JD82b,
   author = {Joshi, S. M. and Dhamdhere, D. M.},
   journal = ijcm,
   pages = {111--126},
   title = {A Composite Hoisting-Strength Reduction Transformation
           for Global Program Optimization -- Part {II}},
   volume = {11},
   year = {1982}
}

@inproceedings{KRSPLDI92,
   author = {Knoop, J. and R\"uthing, O. and Steffen, B.},
   title = {Lazy code motion},
  crossref =     "PLDI92",
   pages = {224--234},
}

@unpublished{KRStoplas93,
   author = {Knoop, J. and R\"uthing, O. and Steffen, B.},
     note = "Submitted to ~" # toplas #". Extended and revised version of
     	\cite{KRSPLDI92}",
     title = {Optimal Code Motion: {Theory} and  Practice},
   year = {1993}
}

@article{KRSjpl93,
   author = {Knoop, J. and R\"uthing, O. and Steffen, B.},
   journal =  jpl,
   title = {Lazy Strength Reduction},
   year = 1993,
   volume = 1,
   number = 1,
   pages = {71--91},
   publisher = {Chapman \& Hall},
   address = {London, UK},
  }

@article{MR79,
   author = {Morel, E. and Renvoise, C.},
   journal = cacm,
   number = 2,
   pages = {96--103},
   title = {Global Optimization by Suppression of Partial Redundancies},
   volume = 22,
   year = 1979
}

@inproceedings{RWZPOPL88,
   author = {Rosen, B. K. and Wegman, M. N. and Zadeck, F. K.},
   address = {San Diego, CA},
   booktitle = "Proc. 15$^{th}$~" # popl,
   pages = {12--27},
   title = {Global value numbers and redundant computations},
   year = {1988}
}

@inproceedings{SKResop90,
   title = {The Value Flow Graph: {A} Program Representation
   	for Optimal Program Transformations},
   author = {Steffen, B. and Knoop, J. and R\"uthing, O.},
   crossref = "ESOP1990",
   pages = {389--405},
}

@inproceedings{SKRtapsoft91,
   author = {Steffen, B. and Knoop, J. and R\"uthing, O.},
   address = {Brighton, UK},
   booktitle = "Proc. 4$^{th}$~" # tapsoft,
   pages = {394--415},
   publisher = {Springer-Verlag},
   series = LNCS # "~494",
   title = { Efficient Code Motion and an Adaption to Strength Reduction},
   year = {1991}
}

@article{So89,
      author = {Sorkin, A.},
      title = {Some Comments on a Solution to a Problem with
       {M}orel and {R}envoise's ``{G}lobal
       Optimization by Suppression of Partial  Redundancies''},
      journal = toplas,
      volume = 11,
      number = 4,
      pages = {666--668},
      year = 1989,
      note = {Technical Correspondence}
}

@inproceedings{width,
author = {D. M. Dhamdhere and Uday P. Khedker},
title = {Complexity of bidirectional data flow analysis},
booktitle = popl,
pages = {397--???},
year = 1993
}