# ESI: The Precision Results on Goal-Dependent Analysis

[Page last updated on 2001/02/19 10:29:56.]

Here are the precision results on the impact of structural information for goal-dependent mode analysis. Remember, only a small part of the precision improvement obtained is captured by these numbers (here is why).

The table below has the following columns:

pairs
The total number of possible pair-sharings of argument positions in the reachable part of the program. Suppose that a program defines, among others, a predicate `p/n` which is not declared as dead code by the analysis. This counts as n(n-1)/2 possible pair-sharings, since each argument position may share with each other.
vars
The total number of argument positions in the reachable part of the program.
indep
The total number of argument pairs that were declared independent by the analysis (of course, indep ≤ pairs).
ground
The total number of ground argument positions in the reachable part of the program.
linear
The total number of linear argument positions in the reachable part of the program (note that ground or free variables are also linear).
free
The total number of free argument positions in the reachable part of the program.
bound
The total number of bound (or nonvar) argument positions in the reachable part of the program (note that ground variables are clearly bound).

Notice that structural information has the potential of pruning some computation paths on the ground that they cannot be followed by the program being analyzed. This explains why in some cases the columns pairs and vars in the table show a difference: in those cases the analysis with Pattern(·) discovered that some predicates could never succeed or never be called (because of a systematic failure before each of their call points).

For those looking at this page through color-enabled devices: table entries in red indicate that the integration of explicit structural information led to precision loss; green indicates improved precision; brown indicates that no such qualitative conclusion could be drawn (because one of the analyses timed out).

The symbol * appears near the name of a program in those cases where CHINA indicates possible incorrectness of the analysis' results. See the page on questions and answers if this shocks you.

 Program pairs vars indep ground linear free bound `4colors.pl` 246/246 46/46 246/246 27/27 46/46 16/16 27/27 `4men.pl` 30/30 50/50 30/30 45/45 50/50 5/5 45/45 `8puzzle.pl` 42/42 40/40 42/42 31/31 40/40 9/9 31/31 `LeanTaP.pl` 294/294 276/276 145/167 51/51 82/94 23/25 124/124 `ac_fix.pl` 130/130 142/142 130/130 133/133 140/140 7/7 133/133 `action.pl` 160/160 180/180 15/17 4/5 10/11 6/6 35/35 `aircraft.pl` 1092/1092 1339/1339 1091/1091 1176/1176 1339/1339 124/124 1177/1177 `all_permutations.pl` 42/42 32/32 22/22 2/2 11/11 9/9 15/15 `altappend.pl` 26/26 28/28 17/17 0/0 28/28 4/4 17/17 `ann.pl` 834/834 482/481 563/570 110/109 191/193 77/80 243/248 `append.pl` 6/6 6/6 0/0 0/0 0/0 0/0 1/1 `apprevlast.pl` 18/18 24/24 7/7 2/2 4/4 2/2 11/11 `aqua_c.pl` 36778/36766 11913/11901 18359/18360 1485/1487 3558/3559 1577/1576 4910/5026 `astar.pl` 57/57 65/65 55/55 47/47 62/62 11/11 50/50 `attractions.pl` 70/70 66/66 11/11 5/5 19/19 1/1 21/21 `attractions2.pl` 33/33 45/45 16/16 5/5 20/20 4/4 20/20 `barnes_hut.pl` 824/824 262/262 768/768 190/190 217/217 27/27 199/199 `bid.pl` 82/82 96/96 82/82 76/76 96/96 18/18 76/76 `bigot.pl` 81/81 77/77 81/81 58/58 77/77 12/12 58/58 `bintrees.pl` 56/56 60/60 35/35 2/2 55/55 23/23 26/26 `birds.pl` 36/36 90/90 35/35 73/73 81/81 4/4 73/73 `bnet.pl` 402/402 232/232 386/386 159/159 190/190 30/30 185/185 `bnet2.pl` 402/402 232/232 386/386 159/159 190/190 30/30 185/185 `boyer_wamcc.pl` 162/162 158/158 41/41 4/4 21/21 17/17 64/64 `bp0-6.pl` 528/528 230/230 523/523 182/182 206/206 19/19 207/207 `browse_wamcc.pl` 122/122 98/98 110/110 46/46 68/68 11/11 59/59 `bryant.pl` 2416/2416 612/612 2160/2160 212/212 270/270 58/58 410/410 `cal_wamcc.pl` 58/58 48/48 58/58 41/41 48/48 7/7 41/41 `cardsol.pl` 49/49 65/65 48/48 46/46 65/65 9/9 50/50 `caslog.pl` 25164/25078 9599/9559 11604/11776 1803/1847 2893/2933 974/972 4842/4830 `chasen-all.pl` 158/158 185/185 71/72 55/58 89/92 33/33 130/132 `chat80.pl` 7430/7430 3270/3270 5337/5337 872/872 1613/1613 585/585 1453/1462 `chat_parser.pl` 4070/4070 1484/1484 3332/3332 505/505 908/908 357/357 643/643 `chess.pl` 512/512 399/399 476/476 218/218 278/278 55/55 270/270 `circan.pl` 37/37 53/53 27/28 14/14 23/25 7/9 29/29 `color.pl` 27/27 35/35 26/26 16/16 25/25 5/5 28/28 `compound.pl` 16/16 20/20 16/16 14/14 20/20 6/6 14/14 `conman.pl` 45/45 83/83 23/23 11/11 32/32 12/12 23/23 `crip.pl` 218/218 208/208 218/218 179/179 208/208 25/25 180/180 `cry_add.pl` 66/66 71/71 40/40 17/17 30/30 12/12 42/42 `cry_mult.pl` 148/148 97/97 127/127 50/50 63/63 13/13 73/73 `crypt_wamcc.pl` 36/36 40/40 36/36 31/31 40/40 0/0 33/33 `cs2.pl` 330/330 184/184 330/330 148/148 184/184 35/35 148/148 `curry2indy.pl *` 1486/1486 1415/1415 1414/1414 887/887 1239/1239 336/336 961/961 `custord.pl` 30/30 40/40 27/27 19/19 28/28 7/7 19/19 `cycles.pl *` 136/136 123/123 58/58 11/11 35/35 23/23 57/57 `dcg1.pl` 84/84 84/84 84/84 57/57 84/84 23/23 57/57 `demo_fsa2.pl` 8/8 16/16 6/6 4/4 6/6 1/1 8/8 `dfid.pl` 24/24 42/42 24/24 36/36 42/42 6/6 36/36 `dfsscc.pl` 111/111 121/121 55/55 20/20 48/48 23/23 54/54 `diffsimpsv.pl` 46/46 48/48 45/45 40/40 46/46 6/6 40/40 `dioph.pl` 80/80 56/56 79/79 35/35 56/56 15/15 41/41 `disj_r.pl` 90/90 116/116 90/90 96/96 116/116 19/19 97/97 `dlists.pl` 52/52 62/62 0/0 0/0 0/0 0/0 31/31 `dposan.pl` 331/331 377/377 194/213 81/96 154/166 48/50 176/195 `draw.pl` 614/614 268/268 610/610 189/189 237/237 41/41 212/212 `eliza.pl` 224/224 208/208 115/115 69/69 106/106 33/33 120/120 `english.pl` 74/74 60/60 67/67 28/28 60/60 4/4 34/34 `ezan.pl` 3449/3449 1847/1847 2008/2011 449/455 749/755 280/280 887/887 `factors.pl` 26/26 16/16 26/26 11/11 16/16 5/5 11/11 `famtree_lguzik.pl` 110/110 58/58 100/100 33/33 35/35 2/2 33/33 `fecht.pl` 386/386 66/66 278/278 1/1 66/66 33/33 9/9 `fft.pl` 130/130 94/94 123/123 46/46 94/94 19/19 52/52 `flatten.pl` 10/10 14/14 2/2 2/2 3/3 1/1 8/8 `fraction.pl` 66/66 44/44 66/66 32/32 44/44 12/12 32/32 `french.pl` 96/96 66/66 89/89 34/34 66/66 4/4 39/39 `fst.pl` 36/36 40/40 27/27 24/24 30/30 6/6 24/24 `ga.pl` 866/866 294/294 860/860 202/202 290/290 66/66 206/206 `gauss.pl` 46/46 46/46 46/46 37/37 46/46 9/9 37/37 `gcd.pl` 106/106 46/46 103/103 19/19 46/46 11/11 20/20 `gilberto.pl` 38/38 24/24 0/0 0/0 0/0 0/0 4/4 `gnup-1.1.0_pl2wam.pl` 3801/3801 2469/2469 2286/2289 563/565 1051/1053 394/394 1019/1034 `grammar.pl` 32/32 34/34 28/28 7/9 34/34 16/16 16/16 `ham_bshort.pl` 138/138 106/106 102/102 60/60 84/84 21/21 62/62 `hamiltonian.pl` 32/32 42/42 32/32 34/34 42/42 7/7 35/35 `hanoiapp.pl` 26/26 16/16 26/26 14/14 16/16 2/2 14/14 `hebtrans.pl` 24/20 52/47 22/19 27/30 40/40 3/3 36/36 `ilap.pl` 200/200 156/156 185/185 60/60 75/75 15/15 95/95 `ileanTAP.pl` 746/746 246/246 337/337 17/17 59/59 22/27 51/61 `ime_v2-2-1.pl` 454/454 210/210 409/409 101/101 143/143 37/37 144/144 `indy2curry.pl` 366/366 262/262 360/360 187/187 256/256 43/43 198/198 `intervals.pl` 118/118 134/134 34/34 6/6 20/20 14/14 39/39 `jugs.pl` 69/69 67/67 32/32 5/5 22/22 13/13 43/43 `kalah_r.pl` 364/364 246/246 364/364 199/199 246/246 38/38 201/201 `kipeg.pl` 38/38 40/40 38/38 33/33 40/40 6/6 33/33 `knight.pl` 115/115 91/91 100/100 25/25 88/88 13/13 56/56 `lc.pl` 106/106 112/112 32/105 11/91 28/112 17/18 53/94 `leantap_small.pl` 44/44 36/36 19/19 0/0 10/10 6/6 4/4 `life.pl` 250/250 126/126 248/248 109/109 126/126 15/15 109/109 `linTAP.pl` 906/906 304/304 388/388 18/18 80/80 42/42 138/138 `lin_reg.pl` 146/146 36/36 146/146 27/27 36/36 9/9 27/27 `linking2.pl` 38/38 26/26 21/21 0/0 18/18 15/15 5/5 `linloss.pl` 4/4 8/8 1/1 2/2 2/2 0/0 4/4 `linsys.pl` 62/62 68/68 62/62 59/59 68/68 8/8 59/59 `ljt.pl` 514/514 290/290 514/514 275/275 290/290 13/13 277/277 `lojban.pl` 1440/1440 958/958 835/835 109/109 340/340 214/214 297/297 `lookup.pl` 6/6 10/10 5/5 2/2 10/10 1/1 5/5 `loops.pl` 63/63 83/83 44/44 16/16 76/76 15/15 51/51 `lowest.pl` 4/4 10/10 2/2 0/0 4/4 3/3 5/5 `lptp-1.05.pl` 7092/7091 5021/5014 3744/3857 1327/1353 1960/1986 566/566 2747/2809 `lptp-1.06.pl` 7092/7092 5021/5021 3744/3858 1329/1362 1962/1995 566/566 2749/2818 `magicex.pl` 2/2 6/6 2/2 0/0 6/6 1/1 0/0 `maps.pl` 64/64 32/32 64/64 21/21 32/32 8/8 21/21 `mastermind.pl` 72/72 92/92 62/62 55/55 65/65 9/9 65/65 `mathlib.pl` 87/87 98/98 43/43 22/22 33/33 10/10 51/51 `matrix.pl` 80/80 68/68 75/75 18/18 68/68 15/15 34/34 `maze.pl` 78/78 58/58 78/78 49/49 58/58 7/7 49/49 `meta_qsort_wamcc.pl` 22/22 34/34 8/8 0/0 5/5 5/5 8/8 `mgpl4.pl` 1243/1243 916/916 901/902 264/269 440/445 104/104 499/512 `mgtp-g-I-temp.pl` 2013/2013 1177/1177 1899/1899 664/664 863/1016 164/164 725/725 `mm.pl` 996/996 675/675 495/495 70/70 197/197 99/99 296/350 `mpuzzle.pl` 44/44 41/41 36/36 18/18 26/26 4/4 29/29 `music.pl` 20/20 22/22 9/9 2/2 10/10 6/6 10/10 `nand_wamcc.pl` 1375/1375 589/589 1375/1375 519/519 589/589 62/62 519/519 `nani.pl` 96/96 164/164 94/94 118/118 145/145 20/20 119/119 `nbody.pl` 597/597 343/343 479/479 155/155 202/202 43/43 233/233 `ncDP.pl` 150/150 120/120 150/150 99/99 120/120 20/20 100/100 `neural.pl` 196/30 184/27 182/30 123/18 147/27 17/9 152/18 `newton.pl` 94/94 56/56 92/92 22/22 56/56 11/11 27/27 `noughts_and_crosses.pl` 58/58 88/88 53/53 65/65 88/88 8/8 68/68 `occ.pl` 8/8 12/12 0/0 0/0 0/0 0/0 11/11 `ocheck0.pl` 2/2 6/6 0/1 0/3 3/6 3/3 3/3 `ocheck1.pl` 14/8 20/14 7/8 0/4 10/14 10/10 4/4 `ocheck2.pl` 24/24 16/16 20/20 8/8 16/16 8/8 8/8 `ocheck3.pl` 90/90 36/36 48/66 6/6 21/36 15/30 6/6 `ocheck4.pl` 12/12 24/24 6/7 3/3 15/17 9/13 6/6 `ocheck5.pl` 4/4 10/10 1/1 0/0 4/4 3/3 4/4 `ochecklin.pl` 2/2 6/6 0/0 0/0 3/3 2/2 3/3 `oldchina.pl` 6955/6955 4182/4182 4074/4285 826/850 1618/1692 732/732 1924/1979 `ordsets.pl` 106/106 50/50 80/80 2/2 50/50 28/28 9/9 `othello.pl` 163/163 159/159 161/161 130/130 149/149 13/13 137/137 `pairs.pl` 14/14 16/16 5/5 0/0 3/3 3/3 8/8 `palindrome.pl` 28/28 28/28 23/23 7/7 25/25 6/6 17/17 `parser_dcg.pl` 436/436 366/366 336/344 61/61 279/366 202/202 146/146 `path.pl` 46/46 64/64 44/44 48/48 57/57 6/6 48/48 `peephole1.pl` 658/658 414/414 370/370 27/27 165/165 70/70 94/94 `peg.pl` 82/82 54/54 82/82 44/44 54/54 9/9 45/45 `pentomino.pl` 392/392 266/266 341/341 127/127 168/168 40/40 205/205 `permute.pl` 40/40 46/46 26/26 7/7 22/22 15/15 23/23 `petsan.pl` 7144/7144 2550/2550 4875/4889 804/816 1177/1189 319/319 1445/1480 `pg.pl` 78/78 62/62 78/78 51/51 62/62 6/6 53/53 `pmatch.pl` 1992/1984 697/681 911/919 133/139 262/256 94/94 271/277 `poly10.pl` 50/50 52/52 50/50 44/44 52/52 8/8 44/44 `powers.pl` 50/50 32/32 50/50 17/17 32/32 9/9 17/17 `powerset.pl` 14/14 16/16 2/2 0/0 1/1 1/1 8/8 `press.pl` 294/294 266/266 174/178 44/44 77/79 30/30 178/180 `primefactors.pl` 20/20 22/22 20/20 15/15 22/22 5/5 15/15 `primes.pl` 68/68 40/40 67/67 30/30 40/40 6/6 31/31 `primes2.pl` 20/20 24/24 20/20 20/20 24/24 4/4 20/20 `primes3.pl` 18/18 24/24 18/18 20/20 24/24 4/4 20/20 `prointrp.pl` 20/20 28/28 9/9 1/2 7/8 6/6 5/6 `puzzle.pl` 36/36 56/56 24/22 8/8 56/21 12/12 25/25 `pythagoras.pl` 16/16 20/20 16/16 13/13 20/20 5/5 13/13 `q8.pl` 36/36 36/36 20/20 7/7 23/23 9/9 18/18 `qplan.pl` 448/448 310/310 439/439 232/232 299/299 52/52 244/244 `queens.pl` 46/46 32/32 46/46 26/26 32/32 6/6 26/26 `queens8_wamcc.pl` 22/22 32/32 22/22 27/27 32/32 5/5 27/27 `queens_wamcc.pl` 28/28 32/32 28/28 27/27 32/32 5/5 27/27 `quotan.pl` 1133/1133 825/825 645/656 148/156 284/289 98/102 398/411 `raytrace.pl` 1478/1478 765/765 1390/1390 522/522 618/618 95/95 564/564 `raytrace2.pl` 1516/1516 781/781 1480/1480 626/626 733/733 106/106 634/634 `raytrace_inst.pl` 1780/1780 801/801 1679/1679 540/540 642/642 87/87 586/586 `rdtok.pl` 148/148 136/136 138/138 82/82 126/128 27/27 93/93 `read.pl` 470/470 298/298 384/384 127/127 209/212 64/64 156/156 `reducer.pl` 322/322 216/216 134/134 53/53 85/85 27/27 81/81 `reform_compiler.pl *` 79271/79271 23247/23247 50768/51892 4765/5066 8923/9253 3421/3452 10947/11116 `robot.pl` 137/137 147/147 87/90 32/41 82/91 19/19 80/92 `rsp.pl` 122/122 80/80 94/99 25/31 35/43 5/7 48/51 `rubik.pl` 230/230 384/384 182/182 172/172 235/235 55/55 224/224 `sb_asm.pl` 394/394 346/346 174/174 42/42 76/76 32/32 147/147 `scc.pl` 508/508 220/220 506/506 174/174 220/220 26/26 183/183 `schedule.pl` 214/214 84/84 214/214 66/66 84/84 18/18 66/66 `sdda.pl` 197/197 180/180 69/79 28/32 53/58 25/25 71/80 `search_lguzik.pl` 20/20 28/28 19/19 13/13 16/16 3/3 14/14 `semi.pl` 92/92 92/92 77/77 26/26 86/86 30/30 42/42 `semigroup.pl` 15662/15662 3958/3958 11525/11525 1741/1741 1756/1756 15/15 3919/3919 `sets.pl` 20/20 22/22 11/11 0/0 18/18 7/7 6/6 `sg_mc_big.pl` 1348/1348 496/496 1269/1269 20/20 42/42 17/17 431/431 `shape.pl` 18/18 20/20 14/14 6/6 6/6 0/0 10/10 `sharing_enum.pl` 289/289 257/257 160/160 69/69 136/136 49/49 125/125 `shortest.pl` 55/55 73/73 34/34 23/23 41/41 8/8 31/31 `sieve.pl` 18/18 24/24 18/18 20/20 24/24 4/4 20/20 `sim_v5-2.pl` 460/460 538/538 458/458 419/419 538/538 107/107 419/419 `simple_analyzer.pl` 1036/1036 508/508 661/661 89/89 165/165 69/69 272/272 `sorts.pl` 106/106 114/114 71/71 3/3 112/112 33/33 51/51 `sprftp.pl *` 2922/2922 1637/1637 1689/1719 278/294 492/515 186/190 596/675 `stack-opt.pl` 60/60 32/32 40/40 3/3 16/16 10/10 4/4 `staticcalls.pl` 49/49 57/57 30/30 7/7 18/18 9/9 27/27 `stats.pl` 76/76 26/26 76/76 16/16 26/26 10/10 16/16 `strips.pl` 633/633 499/499 226/226 29/29 100/100 55/55 213/215 `synth.pl` 2949/2949 2128/2128 1986/1986 547/547 851/851 276/276 980/980 `tak_wamcc.pl` 12/12 8/8 11/11 2/2 8/8 1/1 2/2 `ternary.pl` 8/8 14/14 4/4 3/3 14/14 2/2 8/8 `tictactoe.pl` 343/343 145/145 342/342 104/104 127/127 12/12 109/109 `trs.pl` 240/240 160/160 104/118 12/21 32/46 11/11 72/84 `tsp.pl` 502/502 220/220 488/489 122/126 220/220 38/38 144/144 `unify.pl` 828/828 304/304 647/647 70/70 154/154 38/38 148/148 `vhdl97_parser.pl` 4880/4880 4587/4587 2583/2583 659/659 1663/1663 944/944 1529/1529 `vsp.pl` 113/113 101/101 44/44 10/10 14/14 4/4 26/26 `yaqueens.pl` 40/40 54/54 40/40 45/45 54/54 8/8 46/46 `yasmm.pl` 78/78 60/60 61/63 31/31 37/51 6/6 41/42 `zebra.pl` 54/54 34/34 54/54 19/19 34/34 11/11 20/20