Xref: utzoo comp.compilers:1543 comp.software-eng:4487 Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!apple!snorkelwacker.mit.edu!mintaka!spdcc!ima!iecc!compilers-sender From: baxter@zola.ICS.UCI.EDU (Ira Baxter) Newsgroups: comp.compilers,comp.software-eng Subject: Cost/Benefit of compiler optimization techniques? Keywords: optimize, design Message-ID: <9011280511.aa16546@ICS.UCI.EDU> Date: 28 Nov 90 13:11:25 GMT Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Ira Baxter Organization: Compilers Central Lines: 60 Approved: compilers@iecc.cambridge.ma.us Compiler optimizations for conventional procedural languages on conventional architectures (for sake of argument, consider both CISC and RISC in this class) seem to come at two levels: Machine-independent optimizations Machine-dependent optimizations Aho's Dragon book suggests "some of the most useful optimizations" that fall into the machine-independent class are: Function-preserving optimizations: Common subexpression elimination Use of algebraic identities Copy propagation Dead-code elimination Constant folding Loop Optimizations: Code Motion Induction-variable elimination Reduction in Strength Others come to mind: Use of programmer-supplied data assertions or branch-probabilities Trace scheduling Procedure inlining Partial evaluation For code generation, some optimizations beyond a vanilla code generator are: Careful use of machine idioms Register allocation (by hueristic methods, graph coloring, etc.) JMP-chain elimination Peephole optimization Dynamic-programming for optimal code generation But there is little information about the relative utility of each of these techniques. I am interested in finding out the "most useful" optimizations (at both levels) for conventional procedural languages (FORTRAN, C, etc.), by comparing average quantitative payoffs which rank them (say, reduction in execution time measured over some large suite of user programs) to some measure of the average effort to implement that optimization (measured in man-somethings). Essentially what I am asking is, "What are the cost/benefit ratios of various techniques"? Additional useful information would be something like conditional utility, i.e., if technique A is used, then technique B is X% less useful. Surely enough compilers have been built so this information is known and documented. Pointers to literature, knowledgeable sources, and even corrections to the form of the question would be appreciated. I'll summarize. Thanks in advance. [Do I want to build a compiler? Not this week. But this information is clearly something every would-be compiler writer should have.] IDB (714) 856-6693 ICS Dept/ UC Irvine, Irvine CA 92717 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.