Topic:
code optimization
Topic:
code optimization by flow analysis
Topic:
dependency analysis
Topic:
model checker
Topic:
transformation of programs
| |
Summary
Global analysis is the traditional method of compiler optimization; and also the most costly. The favorite optimizations are common subexpressions elimination, moving loop invariants outside of loops (strength reduction), reusing temporary storage, eliminating unused code, and turning short loops into straight line code. These require flow analysis with manipulation of the program representation tree. For instance commutative expressions are put into a standard form before recognition of common sub-expressions. (cbb 5/80)
Subtopic: dynamic -> static 
| Quote: Microtool maps known dynamic stack states into static states for direct addressing [»elshJL1_1991]
|
Subtopic: whole program analysis
| Quote: ESP uses whole program analysis to generate code for event-driven state-machines; independent processes with context switch [»kumaS6_2001]
|
Subtopic: type inference
| Quote: SmallEiffel uses global type inference to replace late binding with direct calls to concrete code; efficiently handles multiple inheritance, genericity, dead code [»zendO10_1997]
|
Subtopic: dynamic programming
| Quote: use dynamic programming to generate optimal code for expression trees in linear time [»ahoAV7_1976]
| | Quote: use dynamic programming to assign index registers in tree-structured programs with minimal cost [»agresWW1_1979]
|
Subtopic: graph analysis
| Quote: use dominators and postdominators to identify identical subgraphs of the control flow graph
| | Quote: points-to analysis--for every dereference, determine a superset of the pointer's possible references [»dasM6_2000]
| | Quote: fast, context-sensitive, field-sensitive, pointer analysis algorithm with full heap cloning; analyzes Linux kernel in 3.1 seconds [»lattC6_2007]
|
Subtopic: expression equivalence
| Quote: a complete, polynomial-time randomized algorithm for global value numbering to detect equivalent expressions [»gulwS1_2004]
| | Quote: expression equivalence used for constant and copy propagation, common sub-expression elimination, invariant code motion, induction variable elimination, branch elimination, branch fusion, and loop jamming [»gulwS1_2004]
| | Quote: Herbrand expression equivalence treats operators as uninterpreted functions; used for global value numbering; expression equivalence is undecidable [»gulwS1_2004]
|
Subtopic: random interpretation
| Quote: random interpretation assigns random linear interpretations to operators and executes with random inputs; combines program states with a random affine combination
|
Subtopic: memory optimization
| Quote: object inlining allocates single-reference child objects within their container class; averages 10% faster; expensive to compute [»dolbJ10_1998]
| | Quote: contaminated garbage collection via an equilive equivalence relation with union by rank and path compression; four 32-bit words per object [»cannDJ6_2000]
|
Subtopic: exhaustive analysis
| Quote: 15-25% improvement by selecting the best of 200-4,5500 compilation sequences; within 5-10% of optimal [»almaL6_2004]
|
Subtopic: query optimization
| Quote: Kleisli optimizations include code motion, parallelism, laziness, server migration [»wongL9_2000]
| | Quote: Kleisli optimizer phases defined by a rule-base and application strategy; e.g., BottomUpOnce, TopDownOnce, MaxOnce
|
Subtopic: profiling
| Quote: efficiently profile intraprocedural, acyclic paths--the longest paths that do not traverse a loop's back edge [»ballT7_2000]
| | Quote: large scale optimization through in-memory data structures and execution profiles [»ayerA6_1998]
|
Subtopic: bounds checks
| Quote: ABCD-eliminate array bounds checks on demand; sparse SSA analysis; removes 45% of bounds checks [»bodiR6_2000]
| | Quote: ABCD uses simple difference constraints and an inequality graph; e.g., "i-A.length<0" [»bodiR6_2000]
|
Subtopic: code size optimization
| 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: redundant code
| QuoteRef: ahoAV_1973 ;;850 optimization- eliminate useless assignments, redundant computations
|
Subtopic: incremental development
Quote: separate compilation not necessary; can perform global analysis, C code generation, and recompilation of modified files
[»zendO10_1997]
|
Related Topics
Topic: code optimization (54 items)
Topic: code optimization by flow analysis (47 items)
Topic: dependency analysis (34 items)
Topic: model checker (49 items)
Topic: transformation of programs
(27 items)
|
