Empirical Measurements and Observations

Both lipta and ipta were executed on SPEC CPU2006 Integer Benchmarks, as well as some programs from SPEC2000 benchmarks. The results of measurements are presented in Table 1. We compare three implementations: lipta, ipta, and GCC's points-to analysis (gpta). All the three methods use the same approach of handling arrays, heap locations, pointer arithmetic, function pointers, and field sensitivity.

Table 1. Empirical measurements. Both lipta and ipta are flow- and context-sensitive, whereas gpta is flow- and context-insensitive. A "?" indicates that the analysis ran out of memory.
lipta = Lazy PTA,  ipta = Simple PTA,   gpta = GCC's PTA
Program kLoC Call Sites Time in milliseconds Points-to Pairs
lipta ipta gpta lipta ipta gpta
liveness pta
lbm 0.9 33 0.55 0.52 1.9 5.2 12 507 1911
mcf 1.6 29 1.04 0.62 9.5 3.4 41 367 2159
libquantum 2.6 258 2.0 1.8 5.6 4.8 49 119 2701
bzip2 3.7 233 4.5 4.8 28.1 30.2 60 210 8.8x104
parser 7.7 1123 1.2x103 145.6 4.3x105 422.12 531 4196 1.9x104
sjeng 10.5 678 858.2 99.0 3.2x104 38.1 267 818 1.1x104
hmmer 20.6 1292 90.0 62.9 2.9x105 246.3 232 5805 1.9x106
gap 35.6 5312 4.6x104 1.3x103 1.0x105 1.7x104 421 1272 2.5x109
h264ref 36.0 1992 2.2x105 2.0x105 ? 4.3x103 1683 ? 1.6x107


It is evident from the measurements that:

A paper proposing lazy pointer analysis and surmising our empirical measurements can be downloaded from here.