[m-rev.] for review: separate before and after coverage information

[Paul Bone]

On Wed, Oct 01, 2008 at 04:28:06PM +1000, Zoltan Somogyi wrote:
> For review by Paul.
> 
> Zoltan.
> 
> Simplify the coverage propagation algorithm in several respects.
> 
> First, pass around the coverage before and after each goal separately,
> since almost all decisions affect the two program points differently.
> This allows us to eliminate much code whose job it used to be to split
> up coverage_infos and merge them back together just so they could be
> split again the next time around. In this new arragement, we join them
> together only when they are final and about to be attached to the goal
> they annotate.
> 
> Second, we now explicitly assume that updating either the before or
> after count of a goal cannot lose knowledge, i.e. that we cannot go from
> e.g. before_known(X) to before_unknown. This *should* have been true with
> the previous system as well, but it was hard to see, because the code used
> to deliberately reset one or other of the before and after counts to unknown
> when processing subgoals. This diff deletes the code that tried to reestablish
> this invariant.
> 
> Third, we now separate out the data structures used to hold sums of execution
> counts, and give them their own type to avoid possible mixups.
> 
> deep_profiler/program_representation_utils.m:
> 	Make the changes above. The improved conceptual clarity allows us
> 	move much of the complexity of the main coverage propagation algorithm
> 	into utility predicates, thus raising the level of abstraction.
> 
> 	In a few places, the updated algorithm can propagate more coverage
> 	information than the old version.
> 
> deep_profiler/program_representation_utils.m:
> mdbcomp/program_representation.m:
> 	Change the names of some function symbols to add the _rep suffix,
> 	to fit in with the naming scheme we use for the other components of
> 	program representations.
> 
> deep_profiler/report.m:
> 	Rename a function symbol to make help avoid misunderstanding of its
> 	meaning.
> 
> Index: deep_profiler/display_report.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/display_report.m,v
> retrieving revision 1.13
> diff -u -b -r1.13 display_report.m
> --- deep_profiler/display_report.m	25 Sep 2008 03:47:03 -0000	1.13
> +++ deep_profiler/display_report.m	1 Oct 2008 05:56:04 -0000
> @@ -565,52 +578,56 @@
>      % Annotate a goal and its children with coverage information.
>      %
>  :- pred goal_annotate_coverage(coverage_reference_info::in, goal_path::in,
> -    coverage_info::in, coverage_info::out,
> +    coverage_before::in, coverage_before::out,
> +    coverage_after::in, coverage_after::out,
>      goal_rep(unit)::in, goal_rep(coverage_info)::out) is det.
>  
> -goal_annotate_coverage(Info, GoalPath, !Coverage, Goal0, Goal) :-
> +goal_annotate_coverage(Info, GoalPath, !Before, !After, Goal0, Goal) :-
>      Goal0 = goal_rep(GoalExpr0, Detism, _),
>  
>      % Calculate coverage of any inner goals.
> +    % XXX Why call propagate_detism_coverage only for cut scope goals and
> +    % atomic goals?

The coverage may be known before a negation or a cut scope goal, but it
cannot be caluclated from the inner goals, which
negation_annotate_coverage and scope_annotate_coverage understand.
However if the entire goal is deterministic the coverage after the goal
is known based on the coverage before it.

I'll add a comment to this effect and move the calls to
propagate_detism_coverage into scope_annotate_coverage and
negation_annotate_coverage.

> @@ -725,80 +761,89 @@
>      %   - The coverage after a disjunction is equal to the sum of coverages
>      %     after each disjunct.
>      %
> -:- pred disj_annotate_coverage(coverage_reference_info::in, detism_rep::in,
> -    goal_path::in, coverage_info::in, coverage_info::out,
> +:- pred disj_annotate_coverage(coverage_reference_info::in,
> +    detism_rep::in, goal_path::in,
> +    coverage_before::in, coverage_before::out,
> +    coverage_after::in, coverage_after::out,
>      list(goal_rep(unit))::in, list(goal_rep(coverage_info))::out) is det.
>  
> -disj_annotate_coverage(Info, Detism, GoalPath, !Coverage,
> +disj_annotate_coverage(Info, Detism, GoalPath, !Before, !After,
>          Disjs0, Disjs) :-
> -    CoverageBefore = get_coverage_before(!.Coverage),
> +    % XXX In theory, we could update Before using information from any counter
> +    % at the start of the difirst disjunct, but we don't do that (yet).

I'm not sure if this is true,  There may be cases where not all
disjuncts are tried, such as when a disjunction is in a cc_nondet scope,
or is called from such a scope.

>
> ...
>
> -ite_annotate_coverage(Info, GoalPath, !Coverage,
> +ite_annotate_coverage(Info, GoalPath, !Before, !After,
>          Cond0, Cond, Then0, Then, Else0, Else) :-
>      CondGoalPath = goal_path_add_at_end(GoalPath, step_ite_cond),
>      ThenGoalPath = goal_path_add_at_end(GoalPath, step_ite_then),
>      ElseGoalPath = goal_path_add_at_end(GoalPath, step_ite_else),
>      CondDetism = Cond0 ^ goal_detism_rep,
> -    split_coverage(!.Coverage, CoverageBefore0, CoverageAfter0),
>  
>      % Step 1:
>      %   Call goal_annotate_coverage for the condition goal.
> -    goal_annotate_coverage(Info, CondGoalPath, CoverageBefore0, CondCoverage,
> -        Cond0, Cond),
> +    goal_annotate_coverage(Info, CondGoalPath,
> +        !.Before, BeforeCond, after_unknown, AfterCond, Cond0, Cond),
> +    after_to_before_coverage(AfterCond, BeforeThen0),
>  
>      % Step 2:
> -    %   Lookup coverage information for the then and else goals.  Set the
> -    %   coverage before the then and else goals.
> -    ( coverage_count_after(CondCoverage, CountAfterCond) ->
> -        ThenCoverage0 = coverage_known_before(CountAfterCond)
> -    ;
> -        get_branch_coverage(Info, ThenGoalPath, ThenCoverage0)
> -    ),
> -    get_branch_coverage(Info, ElseGoalPath, ElseCoverage0),
> -
> -        trace [ compile_time(flag("debug_coverage_propagation")), io(!IO) ] (
> -        io.format("ITE Coverage inferred after then and else branches:\n" ++
> -            "\tWhole: %s\n\tThen: %s\n\tElse: %s\n" ++
> +    %   Lookup coverage information for the starts of the then and else goals.
> +    (
> +        BeforeThen0 = before_known(_),
> +        BeforeThen1 = BeforeThen0
> +    ;
> +        BeforeThen0 = before_unknown,
> +        get_branch_start_coverage(Info, ThenGoalPath, BeforeThen1)
> +    ),
> +    % XXX It should be possible, if the condition is not at_most_many,
> +    % to compute BeforeElse as the difference between the counts in
> +    % the initial value of !.Before and AfterCond, if both are known.
> +    % check_ite_coverage already knows the relationship.

This is not that simple,  if the condition throws an exception then:
    !.Before - AfterCond = CondFails + CondExcps

So the number of exceptions needs tracking in order to find the number
of failures.  The same problem exists with inferring the coverage after
a negated goal.


The rest of this patch is fine.  Thanks.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20081007/c0aa04f0/attachment.sig>