ESI: The Precision Results on Goal-Dependent Analysis

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.