Topic: code optimization by special case analysis

topics > computer science > programming > Group: code generation

code optimization
code optimization by code rewrite
code optimization by instruction reordering or scheduling
compile-time execution
machine code and assembly language
register allocation


When compiling a general purpose language, generated code can be improved by detecting specific situations. For instance, peephole optimization recognizes code sequences which can be shortened. Another example is "pre-execution" of expressions involving constant values; especially valuable for literal expressions. Specific optimization can be complicated; for instance ECL's frozen list of constraints; and broader as in conversion of associated binary operators to n-ary operators.

Specific optimization shouldn't be prevented by overly general intermediate codes. For instance a branch-if-higher code should be used when ordering disjoint quantities. This code allows generation of either greater-than or greater-than-or-equal branches. During specific optimization care is needed because most optimization are only valid under a particular context; for instance division by a power of two is equivalent to shifting right only if the dividend is positive. (cbb 5/80)

Subtopic: special-case up

Quote: optimizations: loop control variables in registers, unused assignments, strength reduction, duplicate elimination, packed constants [»goodJB8_1976]
QuoteRef: ahoAV_1973 ;;920 optimize by special casing general operations
Quote: more efficient code if don't overspecify the language; e.g., include a pseudo-op for branch with equal case unspecified [»dewaRB1_1977]

Subtopic: peephole optimization up

Quote: efficient, peephole superoptimizer with thousands of indexed replacement rules; 1.7x to 10x faster than optimized code [»bansS10_2006]
Quote: the retargetable peephole optimizer replaces logically adjacent instructions with a single instruction, or cheaper instructions [»daviJW11_1987]
Quote: peephole optimization is still important; a sign that something is wrong [»karrM6_1984]
Quote: condition codes difficult to optimize; use values instead and generate condition codes at final assembly; uses peephole optimization [»auslM6_1982]
Quote: peephole optimization by collecting short instruction sequences with a single entry point, multiple exits, and canonical registers and constants [»bansS10_2006]
Quote: detect equivalent instruction sequences by executing from two pseudo-random machine states and a 256 byte memory; compute fingerprint of the results [»bansS10_2006]

Subtopic: code compression up

Quote: Squeeze reduces code size by 30% through binary-rewriting; turn common code sequences into procedures, eliminate redundant computation and useless-code, rewrite save/restore [»debrSK3_2000]

Subtopic: result caching up

Quote: can store results of executing an expensive function [»bentJL_1982]

Subtopic: space-for-time up

Quote: space-for-time; can speed data access by storing additional information or by changing the structure [»bentJL_1982]

Subtopic: delayed execution up

Quote: can delay evaluating an item until it is needed [»bentJL_1982]

Subtopic: addressing, housekeeping up

Quote: good addressing code most important optimization for FORTRAN type languages
Quote: addressing optimizations: strength reduction, induction variables, common subexpressions, constant folding [»alleFE_1982]
Quote: all PL.8 data accessed from the stack frame; may be optimized to a register [»auslM6_1982]
Quote: optimize addressing and housekeeping computations through the intermediate language; necessary for efficiency [»auslM6_1982]

Subtopic: superoptimizer up

Quote: the superoptimizer finds the shortest program for a function and an instruction set [»massH10_1987]
Quote: superoptimizer culls bad programs by testing function for some set of inputs; manually inspect what passes [»massH10_1987]

Subtopic: divide by shifting up

Quote: divide negative numbers by two with shifting by first adding 1 [»steeGL11_1977]

Subtopic: freeze list up

Quote: have a freeze list that tells compiler about modes; e.g., if know x and y are integers can generate fixadd(x,y) [»wegbB5_1974, OK]
QuoteRef: wegbB_1971 ;;260 frozen list eg if foo (a,b,c) is a foomode procedure and foomode is frozen then know its data type i.e. type of arguments and result

Related Topics up

Topic: code optimization (54 items)
Topic: code optimization by code rewrite (30 items)
Topic: code optimization by instruction reordering or scheduling (16 items)
Topic: compile-time execution (17 items)
Topic: machine code and assembly language (49 items)
Topic: register allocation
(28 items)

Updated barberCB 7/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.