Topic: code optimization by flow analysis

topics > computer science > programming > Group: code generation

code optimization
code optimization by global analysis
conditional compilation
debugging by usage rules
dependency analysis
flavor analysis and typestates for supplementary type checking
pointers to data
race conditions
register allocation by use-def graphs
safe use of pointers
static single assignment; SSA
Subtopic: parallel programs up

Quote: efficient, unidirectional bitvector analysis for parallel programs with shared memory; optimal for interference [»knooJ5_1995]
Quote: bitvector analysis can ignore the various interleavings of parallel components; parallel-meet over all paths (PMOP) is equivalent to parallel bitvector maximal fixed point [»knooJ5_1995]

Subtopic: annotated representation up

Quote: for optimization, the intermediate representation should be tree-based with control flow, dominator, and use-def information included [»franM11_1998]
Quote: C's 'restrict' annotation splits aliases of p created outside of a procedure from those inside; enables better program checking and optimization [»aikeA6_2003]
Quote: pointer interfaces specify how procedures change the points-to information [»rugiR4_2001]
Quote: region interfaces specify the regions of memory accessed by a procedure

Subtopic: single-instruction graphs up

Quote: single-instruction graphs are clearly better than basic-block flow graphs; store analysis results with edges [»knooJ3_1998]
Quote: extended SSA numbering for indirect pointer references; requires pointer analysis and side-effect analysis; easy to add [»labkC3_1998]

Subtopic: flow analysis up

Quote: linear algorithm to decompose program into primes; e.g., sequence, ifthen, whiledo [»formIR9_1982]
Quote: use dominators and postdominators to identify identical subgraphs of the control flow graph

Subtopic: variable range table up

Quote: build a variable range table in one dataflow-analysis pass; identifies all locations of a variable in registers and memory [»ticeC4_2001]

Subtopic: context-sensitive analysis up

Quote: efficient, context-sensitive pointer alias analysis using a context-insensitive algorithm; clone all methods in a call graph, one per context of interest [»whalJ6_2004]
Quote: clone by context for efficient type inference, thread escape analysis, points-to analysis, and pointer alias analysis
Quote: for analysis, identify the memory locations accessed by a procedure from specific callsites; use pointer parameters to distinguish callsites [»lianD6_2000]
Quote: improved prediction of cache behavior by analyzing calling contexts and separating first loop invocation from successive invocations [»martF3_1998]
Quote: fast, context-sensitive, field-sensitive, pointer analysis algorithm with full heap cloning; analyzes Linux kernel in 3.1 seconds [»lattC6_2007]

Subtopic: bitvector analysis up

Quote: unidirectional bitvector analysis used for liveness, reaching def, def-use, code motion, partial dead code, and strength reduction; works for parallel programs [»knooJ5_1995]

Subtopic: path analysis up

Quote: efficient algorithms to compute the correct traces of a model checker; linear in size of state space [»ballT1_2003]
Quote: count backward branches to replay asynchronous interrupts [»slyeJH10_1998]
Quote: PREfix for path-by-path analysis across function boundaries; finds null pointers, improper memory allocation/deallocation; uninitialized variables, resource state errors, improper library usage [»laruJR5_2004]

Subtopic: race analysis up

Quote: Chord computes reachable pairs, aliasing pairs, escaping pairs, and unlocked pairs; using call-graph, alias, thread-escape, and lock analysis [»naikM6_2006]
Quote: Chord uses annotations to specify which threads can not execute in parallel; 42 annotations per 1.5 million lines of code [»naikM6_2006]

Subtopic: points-to analysis, alias up

Quote: inclusion-based pointer analysis using online cycle detection; much faster or much less memory; either lazy or eager [»hardB6_2007]
Quote: link-time pointer alias analysis that handles pointer arithmetic and out-of-bound references; identifies 30-60% of memory reference instructions [»debrS1_1998]
Quote: points-to analysis--for every dereference, determine a superset of the pointer's possible references [»dasM6_2000]
Quote: one level flow algorithm for efficient, pointer analysis of reference parameters; avoids unification at top levels [»dasM6_2000]
Quote: field-based Andersen-style points-to analysis of a million lines of code in under a second [»heinN6_2001]
Quote: points-to analysis with a database, on-the-fly transitive closure, caching of reachability computations, and cycle elimination
Quote: clone by context for efficient type inference, thread escape analysis, points-to analysis, and pointer alias analysis
Quote: verify pointer interfaces with an intraprocedural, flow-sensitive pointer analysis; matches computed points-to information with a call site's pointer interface [»rugiR4_2001]
Quote: Chord uses k-object sensitivity with k=3; the abstract context of an instance method is an abstract object bound to 'this'; precise alias analysis [»naikM6_2006]

Subtopic: null pointer analysis up

Quote: practical algorithm for eliminating null pointer checks in Java; maintains precise exception support; converted to hardware traps [»kawaM11_2000]

Subtopic: reachability analysis, deadlock up

Quote: improve static reachability analysis for deadlock detection with state space reduction, symbolic model checking, and inequality necessary conditions [»corbJC3_1996]

Subtopic: liveness analysis up

Quote: use liveness analysis to reduce retained garbage; about 50% more expensive than type analysis

Subtopic: dead code analysis up

Quote: with GP can delete parts of a routine which will not be used in the final program [»randS_1957]

Subtopic: procedural esacape analysis up

Quote: use escape analysis to identify object lifetimes; e.g., for stack allocation [»gayD3_2000]
Quote: interprocedural escape analysis of object-oriented programs; linear in size of program and static call graph; 5-10% performance improvement [»gayD3_2000]
Quote: an object escapes a method if it is returned or assigned to a field [»gayD3_2000]
Quote: analyze escape constraints with types and static single assignment (SSA); linear time and space
Quote: clone by context for efficient type inference, thread escape analysis, points-to analysis, and pointer alias analysis

Subtopic: code motion up

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]

Subtopic: program blocks up

Quote: a linear region of a program has one entry and one exit [»freiRA11_1974]
QuoteRef: ahoAV_1973 ;;915 a program block directly dominates some other block if it is the latest block on all paths through the program
QuoteRef: ahoAV_1973 ;;922 strongly connected region of program flow graph consists of unique entry, path between all blocks in region, allows independence
QuoteRef: ahoAV_1973 ;;937 data flow analysis for global code movement uses intervals and bit vectors

Subtopic: condition flags up

Quote: PL.8 intermediate language uses a status register for compares and conditional jumps; no source language control structures [»auslM6_1982]
Quote: condition codes difficult to optimize; use values instead and generate condition codes at final assembly; uses peephole optimization [»auslM6_1982]

Related Topics up

Topic: aliasing (28 items)
Topic: code optimization (54 items)
Topic: code optimization by global analysis (24 items)
Topic: conditional compilation (1 item)
Topic: debugging by usage rules (41 items)
Topic: dependency analysis (34 items)
Topic: flavor analysis and typestates for supplementary type checking (68 items)
Topic: graphs (18 items)
Topic: pointers to data (55 items)
Topic: race conditions (33 items)
Topic: register allocation by use-def graphs (9 items)
Topic: safe use of pointers (102 items)
Topic: static single assignment; SSA
(19 items)

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