Name
Abstract | ||
|---|---|---|
The first interprocedural modification side-effects analysis for C (MODC) that obtains better than worst-case precision on programs with general-purpose pointer usage is presented with empirical results. The analysis consists of an algorithm schema corresponding to a family of MODC algorithms with two independent phases: one for determining pointer-induced aliases and a subsequent one for propagating interprocedural side effects. These MODC algorithms are parameterized by the aliasing method used. The empirical results compare the performance of two dissimilar MODC algorithms: MODC(FSAlias) uses a flow-sensitive, calling-context-sensitive interprocedural alias analysis; MODC(FIAlias uses a flow-insensitive, calling-context-insensitive alias analysis which is much faster, but less accurate. These two algorithms were profiled on 45 programs ranging in size from 250 to 30,000 lines of C code, and the results demonstrate dramatically the possible cost-precision trade-offs. This first comparative implementation of MODC analyses offers insight into the differences between flow-/context-sensitive and flow-/context-insensitive analyses. The analysis cost versus precision trade-offs in side-effect information obtained are reported. The results show surprisingly that the precision of flow-sensitive side-effect analysis is not always prohibitive in cost, and that the precision of flow-insensitive analysis is substantially better than worst-case estimates and seems sufficient for certain applications. On average MODC(FSAlias) for procedures and calls is in the range of 20% more precise than MODC(FIAlias); however, the performance was found to be at least an order of magnitude slower than MODC(FIAlias). |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1145/383043.381532 | ACM Trans. Program. Lang. Syst. |
Keywords | Field | DocType |
side effect,alias analysis | Pointer (computer programming),Parameterized complexity,Mod,Programming language,Computer science,Pointer aliasing,Algorithm,Aliasing,Ranging,Alias analysis,Order of magnitude | Journal |
Volume | Issue | ISSN |
23 | 2 | 0164-0925 |
Citations | PageRank | References |
66 | 5.73 | 80 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| B. G. Ryder | 1 | 2775 | 275.92 |
| William Landi | 2 | 66 | 5.73 |
| Phil Stocks | 3 | 263 | 20.84 |
| Sean Zhang | 4 | 108 | 10.46 |
| Rita Altucher | 5 | 66 | 5.73 |