1. Theory
1.1. TODO
1.1.1. Interprocedural analysis formalization
1.1.1.1. Every local is represented by global + stack
1.1.1.2. 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
1.1.5.1. Safety (alias closure)
1.1.5.2. Prevention of redundant nullification (due to aliases + in general)
1.1.6. Issues with multiple threads
1.1.6.1. 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]
1.2.5.1. Consistency
1.2.5.2. 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
3.1.1.1. Access A
3.1.1.1.1. F field, S stmt
3.1.1.2. AccessGraph
3.1.1.2.1. Map<A, Set<A>> edges
3.1.1.3. AccessGraphMap
3.1.1.3.1. Map<V, AccessGraph> graphs
3.1.2. Operations
3.1.2.1. AccessGraph
3.1.2.1.1. addEdge(a, a)
3.1.2.1.2. removeEdge(a, a)
3.1.2.1.3. removeEdges(a, f)
3.1.2.1.4. suffixOf(a)
3.1.2.1.5. suffixOf(a, f)
3.1.2.1.6. appendTo(a, g)
3.1.2.1.7. union(g)
3.1.2.2. AccessGraphMap
3.1.2.2.1. gen(v)
3.1.2.2.2. gen(v, a)
3.1.2.2.3. kill(v)
3.1.2.2.4. kill(v, f)
3.1.2.2.5. union(s)
3.1.2.2.6. assign(v, v)
3.1.2.2.7. getfield(v, v, f, s)
3.1.2.2.8. setfield(v, f, v, p?)
3.2. Heap Points-To Library
3.2.1. Structure
3.2.1.1. Map<V, Set<H>> roots
3.2.1.2. Map<H, Map<F, Set<H>>> heap
3.2.2. Operations
3.2.2.1. aliasesOf(v, gs) : List<Access>
3.2.2.2. addEdge(v, s)
3.2.2.3. addEdge(s, f, s)
3.2.2.4. removeEdge(v, s)
3.2.2.5. removeEdge(s, f, s)
3.2.2.6. union(p)
3.2.2.7. assign(v, v)
3.2.2.8. getfield(v, v, f)
3.2.2.9. setfield(v, f, v)
3.2.2.10. 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
3.3.3.1. Overall design of context-sensitive analysis
3.3.3.2. Forward without dependence
3.3.3.3. Backward with dependence
3.3.3.4. Forward with dependence
3.3.4. Interprocedural Points-To Analysis
3.3.5. Interprocedural Liveness Analysis
3.3.6. Null Insertions
3.3.6.1. 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
4.2.1.1. Time to analyze (Scalability)
4.2.1.2. Memory required
4.2.1.3. Size and number of points-to/access graphs
4.2.2. Transformed program
4.2.2.1. Increase in code size due to null insertions
4.2.2.2. Memory usage before/after
4.2.2.2.1. GCSpy
4.2.2.3. Execution time before/after