schedule
   
NEWS
List of Conferences

GCC wins ACM SIGPLAN Programming Languages Software Award

Tutorial at PLDI 2014

Videos of the lectures in Essential Abstractions in GCC Workshop .

Workshop on Essential Abstractions in GCC (June 29 - July 3, 2013)

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.

Table 1. Time and unique points-to pairs measurements. Both LFCPA and FCPA are flow- and context-sensitive, whereas GPTA is flow- and context-insensitive. For h264ref, FCPA ran out of memory.
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



Table 2. Liveness restricts the analysis to usable pointer information which is small and sparse.
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



Table 3. Context information for computing usable pointer information is small and sparse.
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:

  • The usable pointer information is (a) rather sparse (64% of basic blocks have 0 points-to pairs), and (b) rather small (four programs have at most 8 points-to pairs and in other programs, 9+ points-to pairs reach fewer than 4% basic blocks). In contrast, GPTA computes an orders of magnitude larger number of points-to pairs at each basic block (see the last column in Table 1).
  • The number of contexts required for computing the usable pointer information is (a) rather sparse (56% or more basic blocks have 0 call strings), and (b) rather small (six programs have at most 8 call strings; in other programs, 9+ call strings reach less than 3% basic blocks). Thus, contrary to the common apprehension, context in- formation need not be exponential in practice. Value-based termination reduces the number of call strings dramatically and the use of liveness enhances this effect further by restricting the computation of data flow values to the usable information.

1. Also referred to as lipta in the previous version of paper
2. Also referred to as ipta in the previous version of paper

Tested on Firefox version 3.0.8 and above     |    Site designed and maintained by GRC    |    © 2013, GCC Resource Center