Topic: code optimization
Topic: code optimization by special case analysis
Topic: intermediate representation of code
Topic: managing shared memory
 
Subtopic: common subexpressions
Quote: bitvector 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 NPcomplete 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: nary operators
QuoteRef: ahoAV_1973 ;;897 if associative binary operators then transform (cluster) into nary 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 depthfirst search of the stronglyconnected components in the SSAgraph [»coopKD9_2001]
 Quote: after OSR, need to remove global, common subexpressions and replace linear function tests [»coopKD9_2001]
 Subtopic: multithreaded rewrite
Quote: allow processors to reorder instructions during execution, and allow writebuffers, 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: bitvector 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; 810% 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)
