pldi04

Cloning-Based Context-Sensitive Pointer Alias Analysis using BDDs: 

Cloning-Based Context-Sensitive Pointer Alias Analysis using BDDs John Whaley Monica Lam Stanford University June 10, 2004

Unification vs. Inclusion: 

Unification vs. Inclusion Earlier scalable pointer analysis was context-insensitive unification-based [Steensgaard ’96] Pointers are either unaliased or point to the same set of objects. Near-linear, but VERY imprecise. Inclusion-based pointer analysis Can point to overlapping sets of objects. Closure calculation is O(n3) Various optimizations [Fahndrich,Su,Heintze,…] BDD formulation, simple, scalable [Berndl,Zhu]

Context Sensitivity: 

Context Sensitivity Context sensitivity is important for precision. Unrealizable paths. Object id(Object x) { return x; } a = id(b); c = id(d);

Context Sensitivity: 

Object id(Object x) { return x; } Object id(Object x) { return x; } Context Sensitivity Context sensitivity is important for precision. Unrealizable paths. Conceptually give each caller its own copy. a = id(b); c = id(d);

Summary-Based Analysis: 

Summary-Based Analysis Popular method for context sensitivity. Two phases: Bottom-up: Summarize effects of methods. Top-down: Propagate information down. Problems: Difficult to summarize pointer analysis. Summary-based analysis using BDD: not shown to scale [Zhu’02] Queries (e.g. which context points to x) require expanding an exponential number of contexts.

Cloning-Based Analysis: 

Cloning-Based Analysis Simple brute force technique. Clone every path through the call graph. Run context-insensitive algorithm on expanded call graph. The catch: exponential blowup

Cloning is exponential!: 

Cloning is exponential!

Recursion: 

Recursion Actually, cloning is unbounded in the presence of recursive cycles. Technique: We treat all methods within a strongly-connected component as a single node.

Recursion: 

Recursion A G B C D E F

Top 20 Sourceforge Java Apps: 

Top 20 Sourceforge Java Apps 1016 1012 108 104 100

Cloning is infeasible (?): 

Cloning is infeasible (?) Typical large program has ~1014 paths If you need 1 byte to represent a clone: Would require 256 terabytes of storage Registered ECC 1GB DIMMs: $98.6 million Power: 96.4 kilowatts = Power for 128 homes 300 GB hard disks: 939 x $250 = $234,750 Time to read (sequential): 70.8 days Seems unreasonable!

BDD comes to the rescue: 

BDD comes to the rescue There are many similarities across contexts. Many copies of nearly-identical results. BDDs can represent large sets of redundant data efficiently. Need a BDD encoding that exploits the similarities.

Contribution (1): 

Contribution (1) Can represent context-sensitive call graph efficiently with BDDs and a clever context numbering scheme Inclusion-based pointer analysis 1014 contexts, 19 minutes Generates all answers

Contribution (2) : 

Contribution (2) BDD hacking is complicated  bddbddb (BDD-based deductive database) Pointer algorithm in 6 lines of Datalog Automatic translate into efficient BDD implementation 10x performance over hand-tuned solver (2164 lines of Java)

Contribution (3): 

Contribution (3) bddbddb: General Datalog solver Supports simple declarative queries Easy use of context-sensitive pointer results Simple context-sensitive analyses: Escape analysis Type refinement Side effect analysis Many more presented in the paper

Context-sensitive call graphs in BDD: 

Context-sensitive call graphs in BDD

Call graph relation: 

Call graph relation Call graph expressed as a relation. Five edges: Calls(A,B) Calls(A,C) Calls(A,D) Calls(B,D) Calls(C,D) B D C A

Call graph relation: 

Call graph relation Relation expressed as a binary function. A=00, B=01, C=10, D=11 B D C A 00 10 01 11

Binary Decision Diagrams: 

Binary Decision Diagrams Graphical encoding of a truth table. x2 x4 x3 x3 x4 x4 x4 0 0 0 1 0 0 0 0 x2 x4 x3 x3 x4 x4 x4 0 1 1 1 0 0 0 1 x1 0 edge 1 edge

Binary Decision Diagrams: 

Binary Decision Diagrams Collapse redundant nodes. x2 x4 x3 x3 x4 x4 x4 0 0 0 0 0 0 0 x2 x4 x3 x3 x4 x4 x4 0 0 0 0 x1 1 1 1 1 1

Binary Decision Diagrams: 

Binary Decision Diagrams Collapse redundant nodes. x2 x4 x3 x3 x4 x4 x4 x2 x4 x3 x3 x4 x4 x4 0 x1 1

Binary Decision Diagrams: 

Binary Decision Diagrams Collapse redundant nodes. x2 x4 x3 x3 x2 x3 x3 x4 x4 0 x1 1

Binary Decision Diagrams: 

Binary Decision Diagrams Collapse redundant nodes. x2 x4 x3 x3 x2 x3 x4 x4 0 x1 1

Binary Decision Diagrams: 

Binary Decision Diagrams Eliminate unnecessary nodes. x2 x4 x3 x3 x2 x3 x4 x4 0 x1 1

Binary Decision Diagrams: 

Binary Decision Diagrams Eliminate unnecessary nodes. x2 x3 x2 x3 x4 0 x1 1

Binary Decision Diagrams: 

Binary Decision Diagrams Size is correlated to amount of redundancy, NOT size of relation. As the set gets larger, the number of don’t-care bits increases, leading to fewer necessary nodes.

Expanded Call Graph: 

Expanded Call Graph A D B C E F G H 0 1 2 0 1 2 2 1 0

Numbering Clones: 

Numbering Clones A D B C E F G H A D B C E F G H E E F F G G H H H H H 0 0 0 0 1 2 0-2 0-2 0-2 3-5 0 0 0 0 1 2 0 1 2 2 1 0 0 1 2 3 4 5 0

Pointer Analysis: 

Pointer Analysis

Pointer Analysis Example: 

Pointer Analysis Example h1: v1 = new Object(); h2: v2 = new Object(); v1.f = v2; v3 = v1.f; Input Relations vPointsTo(v1,h1) vPointsTo(v2,h2) Store(v1,f,v2) Load(v1,f,v3) Output Relations hPointsTo(h1,f,h2) vPointsTo(v3,h2) v1 h1 v2 h2 f v3

Inference Rule in Datalog: 

hPointsTo(h1, f, h2) :- Store(v1, f, v2), vPointsTo(v1, h1), vPointsTo(v2, h2). v1 h1 v2 h2 f Inference Rule in Datalog v1.f = v2; Stores:

Context-sensitive pointer analysis: 

Context-sensitive pointer analysis Compute call graph with context-insensitive pointer analysis. Datalog rules for: assignments, loads, stores discover call targets, bind parameters type filtering Apply rules until fix-point reached. Compute expanded call graph relation. Apply context-insensitive algorithm to expanded call graph.

bddbddb:BDD-Based Deductive DataBase: 

bddbddb: BDD-Based Deductive DataBase

Datalog: 

Datalog Declarative logic programming language designed for databases Horn clauses Operates on relations Datalog is expressive Relational algebra: Explicitly specify relational join, project, rename. Relational calculus: Specify relations between variables; operations are implicit. Datalog: Allows recursively-defined relations.

Datalog  BDD: 

Datalog  BDD Join, project, rename are directly mapped to built-in BDD operations Automatically optimizes: Rule application order Incrementalization Variable ordering BDD parameter tuning Many more…

Experimental Results: 

Experimental Results

Experimental Results: 

Experimental Results Top 20 Java projects on SourceForge Real programs with 100K+ users each Using automatic bddbddb solver Each analysis only a few lines of code Easy to try new algorithms, new queries Test system: Pentium 4 2.2GHz, 1GB RAM RedHat Fedora Core 1, JDK 1.4.2_04, javabdd library, Joeq compiler

Slide38: 

Slide39: 

Multi-type variables: 

Multi-type variables A variable is multi-type if it can point to objects of different types. Measure of analysis precision One line in Datalog Two ways of handling context sensitivity: Projected: Merge all contexts together Full: Keep each context separate

Slide41: 

Related Work: 

Related Work Context-insensitive pointer analysis Steensgaard: Unification-based (POPL’96) Andersen: Inclusion-based (’94) Optimizations: too many to list Berndl: formulate in BDD (PLDI’03) Das: one-level-flow (PLDI’00) Hybrid unification/inclusion

Related Work: 

Related Work Scalable context-sensitive pointer analysis Fähndrich etal, instantiation constraints (PLDI’00) CFL-reachability Unification-based: Imprecise. Handles recursion well. Computes on-demand. GOLF: Das etal. (SAS’01) One level of context sensitivity. Foster, Fahndrich, Aiken (SAS’00) Throws away information. Wilson andamp; Lam: PTF (PLDI’95) Doesn't really scale (especially complexity)

Related Work: 

Related Work Whaley andamp; Rinard: Escape analysis (OOPSLA’99) Compositional summaries: only weak updates. Achieves scalability by collapsing escaped nodes. Emami andamp; Hendren: Invocation graphs (PLDI’94) Only shown to scale to 8K lines. Zhu andamp; Calman: (PLDI’04) To be presented next in this session. More complete coverage in the paper.

Conclusion: 

Conclusion The first scalable context-sensitive inclusion-based pointer analysis. Achieves context sensitivity by cloning. bddbddb: Datalog  efficient BDD Easy to query results, develop new analyses. Very efficient! andlt;19 minutes, andlt;600mb on largest benchmark. Complete system is publically available at: http://suif.stanford.edu/bddbddb