Name
Abstract | ||
|---|---|---|
We present set-based pre-analysis: a virtually universal optimization technique for flow-insensitive points-to analysis. Points-to analysis computes a static abstraction of how object values flow through a program's variables. Set-based pre-analysis relies on the observation that much of this reasoning can take place at the set level rather than the value level. Computing constraints at the set level results in significant optimization opportunities: we can rewrite the input program into a simplified form with the same essential points-to properties. This rewrite results in removing both local variables and instructions, thus simplifying the subsequent value-based points-to computation. Effectively, set-based pre-analysis puts the program in a normal form optimized for points-to analysis. Compared to other techniques for off-line optimization of points-to analyses in the literature, the new elements of our approach are the ability to eliminate statements, and not just variables, as well as its modularity: set-based pre-analysis can be performed on the input just once, e.g., allowing the pre-optimization of libraries that are subsequently reused many times and for different analyses. In experiments with Java programs, set-based pre-analysis eliminates 30% of the program's local variables and 30% or more of computed context-sensitive points-to facts, over a wide set of benchmarks and analyses, resulting in a ~20% average speedup (max: 110%, median: 18%). |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2509136.2509524 | OOPSLA |
Keywords | Field | DocType |
input program,subsequent value-based points-to computation,computed context-sensitive points-to fact,local variable,set-based pre-processing,points-to analysis,different analysis,set-based pre-analysis,essential points-to property,java program,flow-insensitive points-to analysis,optimization | Programming language,Abstraction,Result set,Computer science,Algorithm,Theoretical computer science,A-normal form,Java,Local variable,Modularity,Computation,Speedup | Conference |
Volume | Issue | ISSN |
48 | 10 | 0362-1340 |
Citations | PageRank | References |
6 | 0.44 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yannis Smaragdakis | 1 | 2247 | 147.50 |
| George Balatsouras | 2 | 84 | 4.43 |
| George Kastrinis | 3 | 122 | 6.95 |