Topic:
code optimization
Topic:
code optimization by special case analysis
Topic:
intermediate representation of code
Topic:
managing shared memory
| |
Subtopic: common subexpressions 
| Quote: bit-vector algorithm for lazy code motion subsumes loop invariant code motion, common subexpression elimination, and redundancy elimination; computation as early as necessary and as late as possible [»knooJ6_1992]
| | Quote: optimize range checks using strength reduction, code motion, and common subexpression elimination; reduced cost to 2% [»markV6_1982]
| | Quote: the problem of optimal code generation is NP-complete for common subexpressions [»ahoAV1_1977]
| | Quote: value numbering allows common subexpression elimination over assignments within an extended basic block [»auslM6_1982]
| | Quote: if subexpressions are higher precision than variables, common subexpression elimination may be wrong [»farnC7_1988]
| | Quote: associative and distributive reordering can change the propagation of error; parentheses should always be honored [»farnC7_1988]
| | Quote: instead of moving code out of a loop, insert a duplicate copy; common subexpression elimination to remove the original copy [»auslM6_1982]
| | QuoteRef: ahoAV_1973 ;;918 if two equivalent expressions do not have any subexpressions changed on any path between a dominating block and a block then can reuse result
|
Subtopic: n-ary operators
| QuoteRef: ahoAV_1973 ;;897 if associative binary operators then transform (cluster) into n-ary operators eg (a+(b+c)) to (+ a,b,c)
|
Subtopic: constant operands
| Quote: replicate loop test at head and tail of loop; optimization eliminates the first test if constant operands [»auslM6_1982]
|
Subtopic: expression rewrite
| Quote: operator strength reduction rewrites expensive operations as simpler operations; e.g., 'add' instead of 'multiply' for array indexing [»coopKD9_2001]
| | Quote: OSR is a practical algorithm for operator strength reduction using SSA form; as good as ACK
| | Quote: description of Allen, Cocke, and Kennedy's ACK algorithm for operator strength reduction [»coopKD9_2001]
| | Quote: OSR identifies induction variables by a depth-first search of the strongly-connected components in the SSA-graph [»coopKD9_2001]
| | Quote: after OSR, need to remove global, common subexpressions and replace linear function tests [»coopKD9_2001]
|
Subtopic: multi-threaded rewrite
| Quote: allow processors to reorder instructions during execution, and allow write-buffers, including forward substitution and scalar replacement [»pughW6_1999]
|
Subtopic: commutative operations
| QuoteRef: ahoAV_1973 ;;870 handle commutative reordering by ordering operands
| | QuoteRef: ahoAV_1973 ;;894 if memory reference commutative operators then commute syntax tree so all id leave on right hand side
|
Subtopic: induction variables
| QuoteRef: ahoAV_1973 ;;926 induction variables-- for arbitrary paths through a region shows a arithmetic progression
| | QuoteRef: ahoAV_1973 ;;927 if induction variable same initial value and not used outside can be removed, if several induction variables all but one can be computed on exit
| | QuoteRef: ahoAV_1973 ;;929 multiplication of an induction variable by a region independent value can be replaced by an add and an initialization
|
Subtopic: loop rewrite
| Quote: consolidate constant values for a loop by rearranging expressions within loops; called reassociation [»auslM6_1982]
| | Quote: trap elimination moves bounds tests from loops by modifying the loop termination test [»auslM6_1982]
| | Quote: bit-vector algorithm for lazy code motion subsumes loop invariant code motion, common subexpression elimination, and redundancy elimination; computation as early as necessary and as late as possible [»knooJ6_1992]
| | Quote: instead of moving code out of a loop, insert a duplicate copy; common subexpression elimination to remove the original copy [»auslM6_1982]
|
Subtopic: branch rewrite
| Quote: combine basic blocks by eliminating unnecessary branches; called straightening [»auslM6_1982]
| | Quote: use execution profile data to reposition code; identify chains of basic blocks and split never executed code from procedures; 8-10% faster [»pettK6_1990]
|
Subtopic: loop unrolling
| QuoteRef: ahoAV_1973 ;;932 if loop only a few times can turn it into a sequence
|
Subtopic: binary rewrite
| Quote: implemented adaptive profiler (SWAT) with the Vulcan binary rewriting system
|
Subtopic: invalid rewrites
Quote: with memory coherence, legal transformations are not closed under composition; i.e., downstream components can produce an illegal reordering of memory references; prohibits bytecode transformations
[»pughW6_1999]
|
Related Topics
Topic: code optimization (54 items)
Topic: code optimization by special case analysis (22 items)
Topic: intermediate representation of code (29 items)
Topic: managing shared memory
(74 items)
|
