Map
Index
Random
Help
Topics
th

Topic: code optimization by flow analysis

topics > computer science > programming > Group: code generation



Topic:
aliasing
Topic:
code optimization
Topic:
code optimization by global analysis
Topic:
conditional compilation
Topic:
debugging by usage rules
Topic:
dependency analysis
Topic:
flavor analysis and typestates for supplementary type checking
Topic:
graphs
Topic:
pointers to data
Topic:
race conditions
Topic:
register allocation by use-def graphs
Topic:
safe use of pointers
Topic:
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.