Topic: code optimization by global analysis

topics > computer science > programming > Group: code generation

code optimization
code optimization by flow analysis
dependency analysis
model checker
transformation of programs


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 up

Quote: Microtool maps known dynamic stack states into static states for direct addressing [»elshJL1_1991]

Subtopic: whole program analysis up

Quote: ESP uses whole program analysis to generate code for event-driven state-machines; independent processes with context switch [»kumaS6_2001]

Subtopic: type inference up

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 up

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 up

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 up

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 up

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 up

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 up

Quote: 15-25% improvement by selecting the best of 200-4,5500 compilation sequences; within 5-10% of optimal [»almaL6_2004]

Subtopic: query optimization up

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 up

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 up

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 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: redundant code up

QuoteRef: ahoAV_1973 ;;850 optimization- eliminate useless assignments, redundant computations

Subtopic: incremental development up

Quote: separate compilation not necessary; can perform global analysis, C code generation, and recompilation of modified files

Related Topics up

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)

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