Topic:
code optimization
Topic:
code optimization by code rewrite
Topic:
code optimization by instruction reordering or scheduling
Topic:
compile-time execution
Topic:
machine code and assembly language
Topic:
register allocation
| |
Summary
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 
| 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
| 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
| 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
| Quote: can store results of executing an expensive function [»bentJL_1982]
|
Subtopic: space-for-time
| Quote: space-for-time; can speed data access by storing additional information or by changing the structure [»bentJL_1982]
|
Subtopic: delayed execution
| Quote: can delay evaluating an item until it is needed [»bentJL_1982]
|
Subtopic: addressing, housekeeping
| 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
| 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
| Quote: divide negative numbers by two with shifting by first adding 1 [»steeGL11_1977]
|
Subtopic: freeze list
| 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
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)
|
