Re: Run time optimizations

In 93-04-069


Sanjay Jinturkar <sj3e@server.cs.virginia.edu> writes:
>[Generate optimistic and conservative code and do runtime checks?]


john@iecc.cambridge.ma.us writes:
>[Or dynamically deoptimize code as the assumptions fail.]


I know of three general techniques:


* Statically generate optimistic and conservative code, with runtime tests
to decide which to use. Sometimes, checks can be CSE'd to further improve
performance. Sometimes the optimized and conservative code are the same
but e.g, the code must run sequentially to be conservative but can usually
run in parallel. Examples: loop unrolling, with a prologue to ``peel''
off some number of iterations then execute an optimized (unrolled) loop.
Runtime disambiguation [Nicolau 89], which checks for aliasing then
branches to the appropriate statically-generated case. ``Runtime
compilation'' [Saltz, Berryman & Wu 90], which delays loop scheduling
until runtime indirection values are known (e.g., x[i] = y[a[i]] +
z[b[i]], `a' and `b' unknown at compile time) and a schedule is generated
before the loop body. Inline the expected common part of a function,
resorting to function calls for uncommon cases [Chow 88], aka ``shrink
wrapping''.


* Look at runtime values and decide how to generate code that is more
optimized than the general case but still conservative given the runtime
values. Examples: Bitblt [Pike, Locanthi & Reiser 85], OS system calls
[Pu, Massalin & Ioannidis 88], cache simulation [Przybylski, Horowitz &
Hennessy 88], virtual machines [Deutsch & Schiffman 84], executing
user-supplied commands [Chamberlin et. al. 81], etc.


* Generate optimisitic code with runtime checks. When runtime checks
fail, regenerate the code. There are three general approaches here:
discard the old code and generate code optimized to the new values
[Johnston79]; generate less-optimized code [Sall & Weiss 79] that may
still be better-optmized than conservative static code; or cache several
optimized versions and select between them, generating new versions when
the cache lookup fails [Holze, Chambers & Ungar 91].


Time for a plug: Since I'm a leading advocate of runtime code generation,
I suggest you (everybody!) rush right out and pick up a copy of ``A Case
for Runtime Code Generation,'' [Keppel, Eggers and Henry 91], available
via anonymous ftp from `cs.washington.edu' (128.95.1.4) in the tech
reports subdirectory, number 91-11-04.


;-D on ( Optimizing for the com onion case ) Pardo




%A D. D. Chamberlin
%A M. M. Astrahan
%A W. F. King
%A R. Alorie
%A J. W. Mehl
%A T. G. Price
%A M. Schkolnick
%A P. Griffiths Selinger
%A D. R. Slutz
%A B. W. Wade
%A R. A. Yost
%T Support for Repetitive Transactions and Ad Hoc Queries in System R
%J ACM Transactions on Databse Systems
%V 6
%N 1
%D March 1981
%P 70-94


%A Fred Chow
%T Minimizing Register Usage Penalty at Procedure Calls
%J Sigplan 88 Conference on Programming Language Design and
Implementation
%D 1988
%K shrink wrapping


%A Peter Deutsch
%A Alan M. Schiffman
%T Efficient Implementation of the Smalltalk-80 System
%J 11th Annual Symposium on Principles of Programming Languages
(POPL-11)
%D January 1984
%P 297-302


%A Urs Ho\\*:lze
%A Craig Chambers
%A David Ungar
%T Optimizing Dynamically-Typed Object-Oriented Languages With
Polymorphic Inline Caches
%R Proceedings of the European Conference on Object-Oriented
Programming (ECOOP)
%D July 1991


%A Ronald L. Johnston
%T The Dynamic Incremental Compiler of APL\e3000
%I Association for Computing Machinery (ACM)
%J APL Quote Quad
%V 9
%N 4
%D June 1979
%P 82-87


%A David Keppel
%A Susan J. Eggers
%A Robert R. Henry
%T A Case for Runtime Code Generation
%R UWCSE 91-11-04
%I University of Washington Department of Computer Science and
Engineering
%D November 1991


%A Alexandru Nicolau
%T Run-Time Disambiguation: Coping with Statically Upredictable
Dependencies
%J IEEE Transactions on Computers
%V 38
%N 5
%D May 1989
%P 663-678


%A Rob Pike
%A Bart N. Locanthi
%A John F. Reiser
%T Hardware/Software Trade-offs for Bitmap Graphics on the Blit
%J Software - Practice and Experience
%V 15
%N 2
%P 131-151
%D February 1985


%A Steven Przybylski
%A Mark Horowitz
%A John Hennessy
%T Performance Tradeoffs in Cache Design
%J Proceedings of the 15th Annual International Symposium on Computer
Architecture
%D May 1988
%P 290-298


%A Calton Pu
%A Henry Massalin
%A John Ioannidis
%T The Synthesis Kernel
%J Computing Systems
%V 1
%N 1
%D Winter 1988
%P 11-32


%A H. J. Saal
%A Z. Weiss
%T A Software High Performance APL Interpreter
%J Quote Quad
%V 9
%N 4
%D June 1979
%P 74-81


%A Joel Saltz
%A Harry Berryman
%A Janet Wu
%T Multiprocessors and Runtime Compilation
%J Proceedings of the International Workshop on Compilers for Parallel
Computers
%C Paris
%D December 1990
--

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