Heap Analysis

Get Started. It's Free
or sign up with your email address
Heap Analysis by Mind Map: Heap Analysis

1. Theory

1.1. TODO

1.1.1. Interprocedural analysis formalization Every local is represented by global + stack Treat call/return sites as stack push/pop

1.1.2. Convergence of inter-dependent analyses

1.1.3. Proof of monotonicity of points-to analysis

1.1.4. Proof of correctness??

1.1.5. Null-insertion Safety (alias closure) Prevention of redundant nullification (due to aliases + in general)

1.1.6. Issues with multiple threads Shared Variable Analysis

1.2. DONE

1.2.1. Access Graphs [hra]

1.2.2. Liveness Analysis [hra]

1.2.3. Need for alias analysis [mtp-1]

1.2.4. Problems with traditional points-to [mtp-1]

1.2.5. Points-to graph based on access patterns [mtp-1] Consistency Reachability

1.2.6. Points-to analysis [mtp-1]

2. Writing

2.1. Diagrams

2.2. Paper format

2.2.1. ISMM

2.2.2. OOPSLA

2.3. Sections to write

3. Impementation

3.1. Access Graphs Library

3.1.1. Structure Access A F field, S stmt AccessGraph Map<A, Set<A>> edges AccessGraphMap Map<V, AccessGraph> graphs

3.1.2. Operations AccessGraph addEdge(a, a) removeEdge(a, a) removeEdges(a, f) suffixOf(a) suffixOf(a, f) appendTo(a, g) union(g) AccessGraphMap gen(v) gen(v, a) kill(v) kill(v, f) union(s) assign(v, v) getfield(v, v, f, s) setfield(v, f, v, p?)

3.2. Heap Points-To Library

3.2.1. Structure Map<V, Set<H>> roots Map<H, Map<F, Set<H>>> heap

3.2.2. Operations aliasesOf(v, gs) : List<Access> addEdge(v, s) addEdge(s, f, s) removeEdge(v, s) removeEdge(s, f, s) union(p) assign(v, v) getfield(v, v, f) setfield(v, f, v) new(s)

3.3. SOOT-based implementation

3.3.1. Intraprocedural Liveness Analysis

3.3.2. Intraprocedural Points-To Analysis

3.3.3. Interprocedural Framework Overall design of context-sensitive analysis Forward without dependence Backward with dependence Forward with dependence

3.3.4. Interprocedural Points-To Analysis

3.3.5. Interprocedural Liveness Analysis

3.3.6. Null Insertions Intraprocedural Access Path Analysis

3.3.7. Advanced Points-To Analysis (Interprocedural only)

4. Evaluation

4.1. Test Programs

4.1.1. SPECJVM98

4.1.2. Programs from HRA paper

4.2. Measurements

4.2.1. Analysis Time to analyze (Scalability) Memory required Size and number of points-to/access graphs

4.2.2. Transformed program Increase in code size due to null insertions Memory usage before/after GCSpy Execution time before/after