Empirical Measurements and Observations
Both LFCPA1 and FCPA2 were executed on SPEC CPU2006 Integer Benchmarks, as well as some programs from SPEC2000 benchmarks. The results of measurements are tabulated below. We compare three implementations: LFCPA, FCPA, 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.
LFCPA = Liveness-based PTA, FCPA = Full precise PTA, GPTA = GCC's PTA | |||||||||
Program | kLoC | Call Sites | Time in milliseconds | Points-to Pairs | |||||
---|---|---|---|---|---|---|---|---|---|
LFCPA | FCPA | GPTA | LFCPA | FCPA | 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 |
h264ref | 36.0 | 1992 | 2.2x105 | 2.0x105 | ? | 4.3x103 | 1683 | ? | 1.6x107 |
LFCPA = Liveness-based PTA, FCPA = Full precise PTA, GPTA = GCC's PTA | |||||||||
Program | Total no. of bbs | No. and percentage of basic blocks (BBs) for points-to (pt) pair counts | |||||||
---|---|---|---|---|---|---|---|---|---|
0 pt pairs | 1-4 pt pairs | 5-8 pt pairs | 9+ pt pairs | ||||||
LFCPA | FCPA | LFCPA | FCPA | LFCPA | FCPA | LFCPA | FCPA | ||
lbm | 252 | 229 (90.9%) | 61 (24.2%) | 23 (9.1%) | 82 (32.5%) | 0 | 66 (26.2%) | 0 | 43 (17.1%) |
mcf | 472 | 356 (75.4%) | 160(33.9%) | 116(24.6%) | 2 (0.4%) | 0 | 1 (0.2%) | 0 | 309 (65.5%) |
libquantum | 1642 | 1520 (92.6%) | 793(48.3%) | 119(7.2%) | 796 (48.5%) | 3(0.2%) | 46 (2.8%) | 0 | 7(0.4%) |
bzip2 | 2746 | 2624 (95.6%) | 1058(39.5%) | 118(4.3%) | 12 (0.4%) | 3(0.1%) | 12 (0.4%) | 1(0.0%) | 1637(59.6%) | 9+ pt pairs in LFCPA: Tot 1, Min 12, Max 12, Mean 12.0, Median 12, Mode 12 |
sjeng | 6000 | 4571 (76.2%) | 3239(54.0%) | 1208(20.1%) | 12 (0.2%) | 221(3.7%) | 41 (0.7%) | 0 | 2708(45.1%) |
hmmer | 14418 | 13483 (93.5%) | 8357(58.0%) | 896(6.2%) | 21 (0.1%) | 24(0.2%) | 91 (0.6%) | 15(0.1%) | 5949(41.3%) | 9+ pt pairs in LFCPA: Tot 6, Min 10, Max 16, Mean 13.3, Median 13, Mode 10 |
parser | 6875 | 4823 (70.2%) | 1821(26.5%) | 1591(23.1%) | 25 (0.4%) | 252(3.7%) | 154 (2.2%) | 209(3.0%) | 4875(70.9%) | 9+ pt pairs in LFCPA: Tot 13, Min 9, Max 53, Mean 27.9, Median 18, Mode 9 |
h264ref | 21315 | 13729 (64.4%) | ? | 4760(22.3%) | ? | 2035(9.5%) | ? | 791(3.7%) | ? | 9+ pt pairs in LFCPA: Tot 44, Min 9, Max 98, Mean 36.3, Median 31, Mode 9 |
LFCPA = Liveness-based PTA, FCPA = Full precise PTA, GPTA = GCC's PTA | |||||||||
Program | Total no. of functions | No. and percentage of functions for call-string counts | |||||||
---|---|---|---|---|---|---|---|---|---|
0 call strings | 1-4 call strings | 5-8 call strings | 9+ call strings | ||||||
LFCPA | FCPA | LFCPA | FCPA | LFCPA | FCPA | LFCPA | FCPA | ||
lbm | 22 | 16 (72.7%) | 3 (13.6%) | 9 (36.0%) | 22 (88.0%) | 0 | 0 | 0 | 0 |
mcf | 25 | 16 (72.7%) | 3(12.0%) | 9(36.0%) | 22 (88.0%) | 0 | 0 | 0 | 0 |
bzip2 | 100 | 88 (88.0%) | 38(38.0%) | 12(12.0%) | 62 (62.0%) | 0 | 0 | 0 | 0 |
libquantum | 118 | 100 (84.7%) | 56(47.5%) | 17(14.4%) | 62 (52.5%) | 1(0.8%) | 0 | 0 | 0 |
sjeng | 151 | 96 (63.6%) | 37(24.5%) | 43(28.5%) | 45 (29.8%) | 12 (7.9%) | 15(9.9%) | 0 | 54(35.8%) |
hmmer | 584 | 548 (93.8%) | 330(56.5%) | 32(5.5%) | 175 (30.0%) | 4 (0.7%) | 26(4.5%) | 0 | 53(9.1%) |
parser | 372 | 246 (66.1%) | 76(20.4%) | 118(31.6%) | 135 (36.3%) | 4 (1.1%) | 63(16.9%) | 4(1.1%) | 98(26.3%) | 9+ call strings in LFCPA: Tot 4, Min 10, Max 52, Mean 32.5, Median 29, Mode 10 |
h264ref | 624 | 351 (56.2%) | ? | 240(38.5%) | ? | 14 (2.2%) | ? | 19(3.0%) | ? | 9+ call strings in LFCPA: Tot 14, Min 9, Max 56, Mean 27.9, Median 24, Mode 9 |
It is evident from the measurements that: