[m-rev.] For post-commit review: Add coverage profiling to the deep profiler.

Paul Bone pbone at csse.unimelb.edu.au
Wed Jul 30 09:54:43 AEST 2008


Estimated Hours Taken: 100
Branches: main

Introduce coverage profiling. While regular profiling shows which procedures
are used the most, coverage profiling goes further, and also shows the most
common execution paths through each procedure. We intend coverage profiling
data to be used by a future automatic parallelization pass in the compiler.
However, it should also be useful for other purposes.

This diff adds a compiler option, --coverage-profiling, that, when specified,
adds program instrumentation to record execution counts at selected points
in procedure bodies. The implementation currently stores coverage profiling
information in ProcStatic structures. We will later investigate the impact
of storing this information in ProcDynamic structures instead.

For now coverage statistics can be viewed with the mdprof_dump tool.

compiler/deep_profiling.m:
	Introduced coverage profiling transformation after deep profiling
	transformation, it will be run if at least one coverage point type is
	enabled.

compiler/goal_util.m:
	Created create_conj_from_list/3, to create a conjunction from a list of
	goals.

compiler/hlds_goal.m:
	Added dp_goal_info structure that stores information relevant to the deep
	profiling pass.
	Added egi_maybe_dp field to extra_goal_info to store a dp_goal_info
	structure when required by the deep profiler.

compiler/hlds_pred.m:
	Added a list of coverage_point_info structures to the hlds_proc_static
	structure.

compiler/hlds_out.m:
	Added the ability to dump the dp_goal_info structure when the correct
	option is given.

compiler/layout.m:
	Added extra layout structures to store coverage point static and dynamic
	data for each procedure.

compiler/layout_out.m:
	Added code to write out new layout structures in the Low Level C
	Backend.
	Added code to write out references to coverage point data from the proc
	static structures.
	Conform to changes in layout.m.

compiler/opt_debug.m:
	Conform to changes in layout.m,

compiler/options.m:
	Added command line parameters to enable coverage profiling and different
	coverage points, as well as options that can cause coverage points not
	to be inserted in some circumstances.

compiler/handle_options.m:
	Added hlds dump options to the 'all' aliases for dumping the new
	dp_goal_info structure in the hlds_info.

deep_profiler/dump.m:
    Modified to dump coverage profiling data read in from Deep.data file.

deep_profiler/profile.m:
    Added coverage points to proc static structure.

deep_profiler/read_profile.m:
    Incremented Deep.data format version number.
    Read coverage points from Deep.data file.
    Confirm to changes in profile.m.

library/profiling_builtin.m:
	Added real declaration and dummy implementation of
	increment_coverage_point_count/2.  This represents the instrumentation
	introduced by the coverage profiling transformation.

mdbcomp/program_representation.m:
    Added types to support coverage profiling, including a foreign_enum for
	cp_type.
	Added coverage_point_type_c_value to convert a coverage point type to a
	string representing it's C value.

runtime/mercury_deep_profiling.c:
    Incremented Deep.data format version.
    Implemented writing out of coverage points to the Deep.data file.

runtime/mercury_deep_profiling.h:
	Modified runtime structures to support storing coverage point
	information in proc static structures.

doc/user_guide.texi:
	Documented coverage profiling options, however this is commented out since
	it's experimental.


Index: compiler/deep_profiling.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/deep_profiling.m,v
retrieving revision 1.74
diff -u -p -r1.74 deep_profiling.m
--- compiler/deep_profiling.m	27 Feb 2008 07:23:04 -0000	1.74
+++ compiler/deep_profiling.m	29 Jul 2008 23:55:11 -0000
@@ -34,6 +34,7 @@
 :- import_module check_hlds.mode_util.
 :- import_module check_hlds.type_util.
 :- import_module hlds.code_model.
+:- import_module hlds.goal_util.
 :- import_module hlds.hlds_goal.
 :- import_module hlds.hlds_pred.
 :- import_module hlds.hlds_rtti.
@@ -520,6 +521,7 @@ deep_prof_transform_proc(ModuleInfo, Pre
     proc_info::in, proc_info::out) is det.
 
 transform_normal_proc(ModuleInfo, PredProcId, !ProcInfo) :-
+    module_info_get_globals(ModuleInfo, Globals),
     proc_info_get_goal(!.ProcInfo, Goal0),
     Goal0 = hlds_goal(_, GoalInfo0),
     proc_info_get_varset(!.ProcInfo, VarSet0),
@@ -541,12 +543,25 @@ transform_normal_proc(ModuleInfo, PredPr
             counter.init(0), [], !.VarInfo, FileName, MaybeRecInfo),
 
         % This call transforms the goals of the procedure.
-        deep_prof_transform_goal(empty, Goal0, TransformedGoal, _,
+        deep_prof_transform_goal(empty, Goal0, Goal1, _,
             DeepInfo0, DeepInfo),
-
         !:VarInfo = DeepInfo ^ deep_varinfos,
         CallSites = DeepInfo ^ deep_call_sites,
 
+        % Do coverage profiling if requested.
+        globals.lookup_bool_option(Globals, coverage_profiling,
+            DoCoverageProfiling),
+        (
+            DoCoverageProfiling = yes,
+            coverage_prof_transform_goal(ModuleInfo, PredProcId,
+                MaybeRecInfo, Goal1, TransformedGoal, !VarInfo,
+                CoveragePoints)
+        ;
+            DoCoverageProfiling = no,
+            CoveragePoints = [],
+            TransformedGoal = Goal1
+        ),
+
         (
             MaybeRecInfo = yes(RecInfo),
             RecInfo ^ role = inner_proc(OuterPredProcId)
@@ -556,13 +571,12 @@ transform_normal_proc(ModuleInfo, PredPr
             PredProcId = proc(PredId, ProcId)
         ),
 
-        module_info_get_globals(ModuleInfo, Globals),
         globals.lookup_bool_option(Globals, use_activation_counts,
             UseActivationCounts),
         
         IsInInterface = is_proc_in_interface(ModuleInfo, PredId, ProcId),
         ProcStatic = hlds_proc_static(FileName, LineNumber, IsInInterface,
-            CallSites),
+            CallSites, CoveragePoints),
         ShroudedPredProcId = shroud_pred_proc_id(proc(PredId, ProcId)),
         ProcStaticConsId = deep_profiling_proc_layout(ShroudedPredProcId),
         generate_unify(ProcStaticConsId, ProcStaticVar,
@@ -784,6 +798,12 @@ build_non_proc_body(ModuleInfo, TopCSD, 
     Goal = hlds_goal(GoalExpr, GoalInfo).
 
 
+    % Transform an inner procedure for deep profiling.  Inner procedures are
+    % created by the tail recursion preservation pass above.
+    %
+    % XXX: Inner procedures have no coverage profiling transformation done to
+    % them yet.  This is because they are currently broken, and hence disabled.
+    %
 :- pred transform_inner_proc(module_info::in, pred_proc_id::in,
     proc_info::in, proc_info::out) is det.
 
@@ -1834,6 +1854,1289 @@ record_hlds_proc_static(ProcStatic, Excp
     MaybeDeepInfo = yes(DeepInfo),
     proc_info_set_maybe_deep_profile_info(MaybeDeepInfo, !ProcInfo).
 
+
+%-----------------------------------------------------------------------------%
+% Coverage Profiling.
+%-----------------------------------------------------------------------------%
+
+    % This structure is passed between predicates in this section.
+    %
+:- type proc_coverage_info
+    --->    proc_coverage_info(
+                ci_coverage_points          :: map(int, coverage_point_info),
+                                            % A map from coverage point indexes
+                                            % to coverage point information,
+                                            % Updated as coverage points are
+                                            % inserted.
+                
+                ci_cp_index_counter         :: counter,
+                                            % Used to track the next coverage
+                                            % point index to be allocated.
+                                            
+                ci_var_info                 :: var_info,
+                                            % Information about variables, this
+                                            % is updated as variables are
+                                            % introduced. 
+
+                ci_module_info              :: module_info,
+                ci_pred_proc_id             :: pred_proc_id,
+                ci_maybe_rec_info           :: maybe(deep_recursion_info),
+                ci_coverage_profiling_opts  :: coverage_profiling_options
+            ).
+
+    % Store what coverage profiling options have been selected.
+    %
+:- type coverage_profiling_options
+    --->    coverage_profiling_options(
+                
+                %
+                % These fields correspond to coverage profiling options that
+                % may be specified on the command line.  Except cpu_use_2pass.
+                %
+                cpo_may_fail            :: bool,
+                cpo_multi               :: bool,
+                cpo_any                 :: bool,
+                cpo_branch_ite          :: bool,
+                cpo_branch_switch       :: bool,
+                cpo_branch_disj         :: bool,
+                cpo_use_portcounts      :: bool,
+                cpo_use_trivial         :: bool,
+
+                cpo_use_2pass           :: bool
+                                        % cpu_use_2pass is true if some
+                                        % information needs to be collected in
+                                        % an initial forwards-pass. 
+            ).
+
+    % Return wheather each coverage point type should be enabled and iff
+    % coverage any coverage points are enabled then preform the coverage
+    % proflining pass.
+    %
+:- pred coverage_profiling_options(module_info::in,
+    coverage_profiling_options::out) is det.
+
+coverage_profiling_options(ModuleInfo, CoveragePointOptions) :-
+    module_info_get_globals(ModuleInfo, Globals),
+
+    %
+    % Coverage point types.
+    %
+    globals.lookup_bool_option(Globals, profile_deep_coverage_may_fail,
+        MayFail),
+    globals.lookup_bool_option(Globals, profile_deep_coverage_multi,
+        Multi),
+    globals.lookup_bool_option(Globals, profile_deep_coverage_any,
+        Any),
+    globals.lookup_bool_option(Globals, profile_deep_coverage_branch_ite,
+        BranchIf),
+    globals.lookup_bool_option(Globals, profile_deep_coverage_branch_switch,
+        BranchSwitch),
+    globals.lookup_bool_option(Globals, profile_deep_coverage_branch_disj,
+        BranchDisj),
+
+    %
+    % Interpret options for tuning the coverage profiling pass.
+    %
+    globals.lookup_bool_option(Globals, profile_deep_coverage_use_portcounts,
+        UsePortCounts),
+    globals.lookup_bool_option(Globals, profile_deep_coverage_use_trivial,
+        UseTrivial),
+    bool.or(UsePortCounts, UseTrivial, Use2Pass),
+
+    CoveragePointOptions = coverage_profiling_options(MayFail, Multi, Any,
+        BranchIf, BranchSwitch, BranchDisj, UsePortCounts, UseTrivial,
+        Use2Pass).
+
+
+
+    % Transform the goal if coverage profiling should be performed, otherwise
+    % return it un-altered.
+    %
+:- pred coverage_prof_transform_goal(module_info::in, pred_proc_id::in,
+    maybe(deep_recursion_info)::in, hlds_goal::in, hlds_goal::out,
+    var_info::in, var_info::out, list(coverage_point_info)::out) is det.
+
+coverage_prof_transform_goal(ModuleInfo, PredProcId, MaybeRecInfo, !Goal,
+        !VarInfo, CoveragePoints) :-
+    coverage_profiling_options(ModuleInfo, CoverageProfilingOptions),
+    CoverageInfo0 = init_proc_coverage_info(!.VarInfo, ModuleInfo,
+        PredProcId, MaybeRecInfo, CoverageProfilingOptions),
+    (
+        CoverageProfilingOptions ^ cpo_use_2pass = yes,
+        coverage_prof_first_pass(CoverageProfilingOptions, !Goal,
+            goal_has_port_counts, _)
+    ;
+        CoverageProfilingOptions ^ cpo_use_2pass = no
+    ),
+    coverage_prof_second_pass_goal(cord.empty, !Goal,
+        coverage_after_known, _, CoverageInfo0, CoverageInfo, _),
+    CoverageInfo ^ ci_coverage_points = CoveragePointsMap,
+    CoverageInfo ^ ci_var_info = !:VarInfo,
+    coverage_points_map_list(CoveragePointsMap, CoveragePoints).
+   
+
+    % Transform a goal for coverage profiling.  This is the second pass of
+    % the coverage profiling transformation.  This is done in several steps.
+    %
+    % If the first pass has been performed then relevant information is
+    % collected from the goal_info structure.
+    %
+    % Step 1: Make a decision weather to insert a coverage point after this
+    % goal or not.  This applies to may_fail multi and any coverage point
+    % types only.  Other coverage point types are handled seperatly.
+    %
+    % Step 2: Determine if coverage information is known for goals that
+    % execute before this goal completes.  This includes goals before this
+    % goal (such as within a conjunction) or goals within this goal.
+    % Information collected in the first pass is used here.
+    %
+    % Step 3: Transform inner goals if this goal is non-atomic.
+    %
+    % Step 4: Insert a coverage point after this goal if we decided to
+    % at step 1.  This is done here after any inner goals have been
+    % transformed.
+    % 
+:- pred coverage_prof_second_pass_goal(goal_path::in, 
+    hlds_goal::in, hlds_goal::out, 
+    coverage_after_known::in, coverage_after_known::out, 
+    proc_coverage_info::in, proc_coverage_info::out, bool::out) is det.
+
+coverage_prof_second_pass_goal(Path, Goal0, Goal,
+    CoverageAfterKnown0, NextCoverageAfterKnown, !Info, AddedImpurity) :- 
+    Goal0 = hlds_goal(GoalExpr0, GoalInfo0),
+    Detism = GoalInfo0 ^ goal_info_get_determinism,
+   
+    %
+    % Depending on command line arguments first pass information may or
+    % may-not be available, if it is not avalible sensible defaults are
+    % assumed.
+    %
+    Use2Pass = !.Info ^ ci_coverage_profiling_opts ^ cpo_use_2pass,
+    (
+        Use2Pass = yes,
+        dp_goal_info(GoalTrivial, GoalHasPortCounts) = 
+            goal_info_get_dp_info(GoalInfo0)
+    ;
+        Use2Pass = no,
+        
+        % XXX: Zoltan says;
+        % Is this the best default you can get? You should be able to do
+        % better for goals like unifications.
+        
+        GoalTrivial = goal_is_nontrivial,
+        GoalHasPortCounts = goal_does_not_have_port_counts
+    ),
+  
+    %
+    % Step 1.
+    %
+    % Consider inserting a coverage point after this goal to measure how
+    % many solutions it may have.
+    %
+    (
+        GoalTrivial = goal_is_nontrivial,
+        (
+            GoalHasPortCounts = goal_does_not_have_port_counts,
+            (
+                CoverageAfterKnown0 = coverage_after_unknown,
+                
+                (
+                    % I havn't thought about parallel conjunctions here,
+                    % They should have the same declartive semantics as
+                    % plain conjunctions, and I beleive they arn't possible
+                    % where the first goal is anything other than model_det,
+                    % Only other models can affect the coverage after the
+                    % second goal.  However I can't be sure the
+                    % implementation won't change.
+                    %
+                    % Because parallel conjunctions arn't common and this is
+                    % really only an optimiztion so I've only enabled it for
+                    % plain conjunctions.
+                    %
+                    GoalExpr0 = conj(plain_conj, _)
+                ->
+                    %
+                    % Never insert coverage points after conjunctions, wait
+                    % until the algorithm recurses to inside the conjunction
+                    % and make a better decision about the last conjunct.
+                    % This can reduce the number of coverage points inserted
+                    % in some cases.
+                    %
+                    MaybeCPType = no
+                ;
+                    (
+                        ( Detism = detism_semi
+                        ; Detism = detism_cc_non
+                        ),
+                        
+                        CoverMayFail = !.Info ^ ci_coverage_profiling_opts ^
+                            cpo_may_fail,
+                        (
+                            CoverMayFail = yes,
+                            MaybeCPType = yes(cp_type_solns_may_fail)
+                        ;
+                            CoverMayFail = no,
+                            MaybeCPType = no
+                        )
+                    ;
+                        Detism = detism_multi,
+                        
+                        CoverMulti = !.Info ^ ci_coverage_profiling_opts ^
+                            cpo_multi,
+                        (
+                            CoverMulti = yes,
+                            MaybeCPType = yes(cp_type_solns_multi)
+                        ;
+                            CoverMulti = no,
+                            MaybeCPType = no
+                        )
+                    ;
+                        Detism = detism_non,
+                        
+                        CoverAny = !.Info ^ ci_coverage_profiling_opts ^
+                            cpo_any,
+                        (
+                            CoverAny = yes,
+                            MaybeCPType = yes(cp_type_solns_any)
+                        ;
+                            CoverAny = no,
+                            MaybeCPType = no
+                        )
+                    ;
+                        %
+                        % In this case we know that execution will always stop
+                        % at this goal, no coverage point is needed (or would
+                        % work).
+                        %
+                        ( Detism = detism_erroneous
+                        ; Detism = detism_failure
+                        ),
+                        MaybeCPType = no
+                    ;
+                        %
+                        % This should never occur, as other coverage points
+                        % would have been inserted to ensure coverage is known
+                        % here, unless they are disabled.  We don't insert a
+                        % coverage point here since we shouldn't have to.
+                        %
+                        ( Detism = detism_det
+                        ; Detism = detism_cc_multi
+                        ),
+                        MaybeCPType = no
+                    )
+                )
+            ;
+                CoverageAfterKnown0 = coverage_after_known,
+                MaybeCPType = no
+            )
+        ;
+            GoalHasPortCounts = goal_has_port_counts,
+            MaybeCPType = no
+        )
+    ;
+        GoalTrivial = goal_is_trivial,
+
+        MaybeCPType = no
+    ),
+
+    %
+    % Step 2.
+    %
+    % Update coverage known information.  
+    %
+    (
+        MaybeCPType = yes(_),
+        CoverageAfterKnown = coverage_after_known
+    ;
+        MaybeCPType = no,
+        (
+            % If the goal has a port count then coverage is known at the
+            % point directy before this goal.
+            GoalHasPortCounts = goal_has_port_counts,
+            CoverageAfterKnown = coverage_after_known
+        ;
+            GoalHasPortCounts = goal_does_not_have_port_counts,
+            (
+                % If there is not exactly one solution then the coverage is
+                % not known.
+                ( Detism = detism_semi
+                ; Detism = detism_multi
+                ; Detism = detism_non
+                ; Detism = detism_cc_non
+                ; Detism = detism_erroneous
+                ; Detism = detism_failure
+                ),
+                CoverageAfterKnown = coverage_after_unknown
+            ; 
+                % Otherwise the coverage remains the same.
+                ( Detism = detism_det
+                ; Detism = detism_cc_multi
+                ),
+                CoverageAfterKnown = CoverageAfterKnown0
+            )
+        )
+    ),
+
+    %
+    % Step 3.
+    %
+    % Apply transformation recursively.
+    %
+    (   
+        ( GoalExpr0 = unify(_, _, _, _, _)
+        ; GoalExpr0 = plain_call(_, _, _, _, _, _)
+        ; GoalExpr0 = generic_call(_, _, _, _)
+        ; GoalExpr0 = call_foreign_proc(_, _, _, _, _, _, _)
+        ),
+        AddedImpurityInner = no,
+        GoalExpr1 = GoalExpr0,
+        NextCoverageAfterKnown = CoverageAfterKnown
+    ;
+        GoalExpr0 = conj(ConjType, Goals0),
+        coverage_prof_second_pass_conj(Path, 1, ConjType, Goals0, Goals,
+            CoverageAfterKnown, NextCoverageAfterKnown, !Info,
+            AddedImpurityInner),
+        GoalExpr1 = conj(ConjType, Goals)
+    ;
+        %
+        % There may be optimizations that can allow us to avoid inserting
+        % superfluous coverage points, however they are most likely to be
+        % non-trivial.
+        %
+        GoalExpr0 = disj(Goals0),
+        coverage_prof_second_pass_disj(Path, 1, Goals0, Goals, !Info,
+            AddedImpurityInner),
+        (
+            ( Detism = detism_det
+            ; Detism = detism_cc_multi
+            ),
+            NextCoverageAfterKnown = CoverageAfterKnown
+        ;
+            ( Detism = detism_semi
+            ; Detism = detism_multi
+            ; Detism = detism_non
+            ; Detism = detism_cc_non
+            ; Detism = detism_erroneous
+            ; Detism = detism_failure
+            ),
+            NextCoverageAfterKnown = coverage_after_unknown
+        ),
+        GoalExpr1 = disj(Goals)
+    ;
+        GoalExpr0 = switch(Var, SwitchCanFail, Cases0),
+        coverage_prof_second_pass_switchcase(Path, 1, SwitchCanFail,
+            Cases0, Cases, CoverageAfterKnown, NextCoverageAfterKnown0,
+            !Info, AddedImpurityInner),
+        (
+            SwitchCanFail = cannot_fail,
+            NextCoverageAfterKnown = NextCoverageAfterKnown0
+        ;
+            SwitchCanFail = can_fail,
+            NextCoverageAfterKnown = coverage_after_unknown
+        ),
+        GoalExpr1 = switch(Var, SwitchCanFail, Cases)
+    ;
+        GoalExpr0 = negation(NegGoal0),
+        coverage_prof_second_pass_goal(snoc(Path, step_neg), 
+            NegGoal0, NegGoal, CoverageAfterKnown, NextCoverageAfterKnown,
+            !Info, AddedImpurityInner), 
+        GoalExpr1 = negation(NegGoal)
+    ;
+        GoalExpr0 = scope(Reason, ScopeGoal0),
+        ( 
+            Detism = ScopeGoal0 ^ hlds_goal_info ^
+                goal_info_get_determinism
+        ->
+            ScopeCut = scope_is_no_cut
+        ;
+            ScopeCut = scope_is_cut
+        ),
+        coverage_prof_second_pass_goal(snoc(Path, step_scope(ScopeCut)),
+            ScopeGoal0, ScopeGoal,
+            CoverageAfterKnown, NextCoverageAfterKnown, !Info,
+            AddedImpurityInner), 
+        GoalExpr1 = scope(Reason, ScopeGoal)
+    ;
+        GoalExpr0 = if_then_else(ITEExistVars, Cond, Then, Else),
+        coverage_prof_second_pass_ite(Path, ITEExistVars,
+            Cond, Then, Else, GoalExpr1,
+            CoverageAfterKnown, NextCoverageAfterKnown, !Info,
+            AddedImpurityInner)
+    ;
+        GoalExpr0 = shorthand(_),
+        unexpected(this_file, 
+            "deep_profiling.coverage_prof_transform_goal: " ++ 
+            "shorthand should have gone by now")
+    ),
+    add_impurity_if_needed(AddedImpurityInner, GoalInfo0, GoalInfo1),
+    Goal1 = hlds_goal(GoalExpr1, GoalInfo1),
+    
+    %
+    % Step 4.
+    %
+    % Insert the coverage point if we decided to earlier.
+    %
+    (
+        MaybeCPType = yes(CPType),
+        CPInfo = coverage_point_info(Path, CPType),
+       
+        make_coverage_point(CPInfo, CPGoals, !Info),
+        create_conj_from_list([Goal1 | CPGoals], plain_conj, Goal),
+
+        AddedImpurity = yes
+    ;
+        MaybeCPType = no,
+        Goal = Goal1,
+        AddedImpurity = AddedImpurityInner
+    ).
+
+
+    % Perform the coverage profiling transformation for conjuncts starting
+    % at the tail of the goal list and moving back towards the head.  The
+    % goal list represents the list of goals within a conjunction minus
+    % 'Pos' goals removed from the head.
+    %
+    % This is done tail first as to take advantage of knoledge of goals after
+    % the current goal within the conjunction.
+    %
+:- pred coverage_prof_second_pass_conj(goal_path::in, int::in,
+    conj_type::in, list(hlds_goal)::in, list(hlds_goal)::out,
+    coverage_after_known::in, coverage_after_known::out,
+    proc_coverage_info::in, proc_coverage_info::out, bool::out) is det.
+
+coverage_prof_second_pass_conj(_, _, _, [], [], !CoverageAfterKnown,
+    !Info, no).
+coverage_prof_second_pass_conj(Path, Pos, ConjType, 
+        [Goal0 | Goals0], Goals, 
+        CoverageAfterKnown0, NextCoverageAfterKnown, !Info,
+        AddedImpurity) :-
+    coverage_prof_second_pass_conj(Path, Pos+1, ConjType,
+        Goals0, Goals1, CoverageAfterKnown0, CoverageAfterKnown, !Info,
+        AddedImpurityTail),
+    coverage_prof_second_pass_goal(snoc(Path, step_conj(Pos)),
+        Goal0, Goal1, CoverageAfterKnown, NextCoverageAfterKnown, !Info,
+        AddedImpurityHead),
+    (
+        Goal1 = hlds_goal(conj(plain_conj, ConjGoals), _),
+        ConjType = plain_conj
+    ->
+        Goals = ConjGoals ++ Goals1
+    ;
+        Goals = [ Goal1 | Goals1 ]
+    ),
+    bool.or(AddedImpurityHead, AddedImpurityTail, AddedImpurity).
+
+
+    % Perform the coverage profiling transformation over goals within a
+    % disjunction.  The list of goals represents the tail of the disjunction
+    % currently being transformed.
+    %
+    % Disjuncts are also transformed in reverse order, as knoledge from
+    % later disjuncts can be used to reduce the number of coverage points
+    % placed in earlier disjuncts.
+    %
+:- pred coverage_prof_second_pass_disj(goal_path::in, int::in,
+    list(hlds_goal)::in, list(hlds_goal)::out,
+    proc_coverage_info::in, proc_coverage_info::out, bool::out) is det.
+
+coverage_prof_second_pass_disj(_, _, [], [], !Info, no).
+
+coverage_prof_second_pass_disj(Path, Pos, [Goal0 | Goals0], [Goal | Goals],
+        !Info, AddedImpurity) :-
+    % Transform the tail of the disjunction.
+    coverage_prof_second_pass_disj(Path, Pos+1, Goals0, Goals, !Info,
+        AddedImpurityTail),
+
+    % Transform this goal and optionally add a coverage point before it.
+    DisjPath = snoc(Path, step_disj(Pos)),
+    coverage_prof_second_pass_goal(DisjPath, Goal0, Goal1, 
+        coverage_after_unknown, NextCoverageAfterKnown, !Info,
+        AddedImpurityHead0),
+    CPOBranchDisj = !.Info ^ ci_coverage_profiling_opts ^ cpo_branch_disj,
+    (
+        CPOBranchDisj = yes,
+        (
+            NextCoverageAfterKnown = coverage_after_unknown,
+            insert_coverage_point_before(coverage_point_info(DisjPath,
+                cp_type_branch_arm), Goal1, Goal, !Info),
+            AddedImpurityHead = yes
+        ;
+            NextCoverageAfterKnown = coverage_after_known,
+            Goal = Goal1,
+            AddedImpurityHead = AddedImpurityHead0
+        )
+    ;
+        CPOBranchDisj = no,
+        Goal = Goal1,
+        AddedImpurityHead = AddedImpurityHead0
+    ),
+
+    bool.or(AddedImpurityHead, AddedImpurityTail, AddedImpurity).
+
+
+:- pred coverage_prof_second_pass_switchcase(goal_path::in, int::in, 
+    can_fail::in, list(case)::in, list(case)::out, 
+    coverage_after_known::in, coverage_after_known::out, 
+    proc_coverage_info::in, proc_coverage_info::out, bool::out) is det.
+
+coverage_prof_second_pass_switchcase(_, _, _, [], [], 
+    _, coverage_after_known, !Info, no).
+
+coverage_prof_second_pass_switchcase(Path, Pos, SwitchCanFail,
+        [Case0 | Cases0], [Case | Cases], CoverageAfterSwitchKnown,
+        NextCoverageAfterKnown, !Info, AddedImpurity) :-
+    Goal0 = Case0 ^ case_goal,
+
+    %
+    % If the switch cannot fail and this is the last case then the coverage
+    % at the end of this case can be computed from the coverage after the
+    % entire switch and coverage information for the tail of the switch
+    % such as branch coverage points.
+    %
+    (
+        Cases0 = [],
+        (
+            SwitchCanFail = cannot_fail,
+            CoverageAfterHeadKnown = CoverageAfterSwitchKnown
+        ;
+            SwitchCanFail = can_fail,
+            CoverageAfterHeadKnown = coverage_after_unknown
+        )
+    ;
+        Cases0 = [_ | _],
+        CoverageAfterHeadKnown = coverage_after_unknown
+    ),
+
+    SwitchPath = snoc(Path, step_disj(Pos)),
+    coverage_prof_second_pass_goal(SwitchPath, Goal0, Goal1, 
+        CoverageAfterHeadKnown, NextCoverageAfterKnown0, !Info,
+        AddedImpurityHead0),
+    
+    % Possibly insert coverage point.
+    CPOBranchSwitch = !.Info ^ ci_coverage_profiling_opts ^
+        cpo_branch_switch,
+    (
+        CPOBranchSwitch = yes,
+        (
+            NextCoverageAfterKnown0 = coverage_after_unknown,
+            insert_coverage_point_before(coverage_point_info(SwitchPath,
+                cp_type_branch_arm), Goal1, Goal, !Info),
+            AddedImpurityHead = yes,
+            NextCoverageAfterKnownHead = coverage_after_known
+        ;
+            NextCoverageAfterKnown0 = coverage_after_known,
+            Goal = Goal1,
+            AddedImpurityHead = AddedImpurityHead0,
+            NextCoverageAfterKnownHead = NextCoverageAfterKnown0
+        )
+    ;
+        CPOBranchSwitch = no,
+        Goal = Goal1,
+        AddedImpurityHead = AddedImpurityHead0,
+        NextCoverageAfterKnownHead = NextCoverageAfterKnown0
+    ),
+
+    % Handle recursive case and prepare output variables.
+    coverage_prof_second_pass_switchcase(Path, Pos+1,
+        SwitchCanFail, Cases0, Cases,
+        CoverageAfterSwitchKnown, NextCoverageAfterKnownTail, !Info,
+        AddedImpurityTail),
+    Case = Case0 ^ case_goal := Goal,
+    coverage_after_known_branch(NextCoverageAfterKnownHead,
+        NextCoverageAfterKnownTail, NextCoverageAfterKnown), 
+    bool.or(AddedImpurityHead, AddedImpurityTail, AddedImpurity).
+
+
+    % Determine if branch coverage points should be inserted in either or
+    % both of the then and else branches, insert them and transform the
+    % sub-goals.
+    %
+    % This is performed by first transforming the Else and Then branches,
+    % then making decisions about cooverage points and inserting them, then
+    % transforming the condition and constructing the new ITE goal_expr.
+    %
+:- pred coverage_prof_second_pass_ite(goal_path::in, list(prog_var)::in, 
+    hlds_goal::in, hlds_goal::in, hlds_goal::in, hlds_goal_expr::out,
+    coverage_after_known::in, coverage_after_known::out, 
+    proc_coverage_info::in, proc_coverage_info::out, bool::out) is det.
+
+coverage_prof_second_pass_ite(Path, ITEExistVars, Cond0, Then0, Else0, 
+        GoalExpr, CoverageAfterITEKnown, NextCoverageAfterKnown,
+        !Info, AddedImpurity) :-
+    %
+    % If the then and else goals have exactly one solution and coverage is
+    % known after the ite, then the coverage at the end of one branch can
+    % be computed from the other branch and the coverage known after the
+    % ITE.  This helps later to insert fewer coverage points in the
+    % beginning of the branches, and may also help reduce coverage points
+    % within the branches. 
+    %
+    (
+        CoverageAfterITEKnown = coverage_after_known,
+        ThenDetism = Then0 ^ hlds_goal_info ^ goal_info_get_determinism,
+        (
+            ( ThenDetism = detism_det
+            ; ThenDetism = detism_cc_multi
+            ),
+            ElseDetism = Else0 ^ hlds_goal_info ^ goal_info_get_determinism,
+            (
+                ( ElseDetism = detism_det
+                ; ElseDetism = detism_cc_multi
+                ),
+                
+                %
+                % Now which should have coverage known,
+                %
+                Use2Pass = !.Info ^ ci_coverage_profiling_opts ^
+                    cpo_use_2pass,
+                (
+                    Use2Pass = yes,
+                    dp_goal_info(_, ThenHasPortCounts) =
+                        goal_info_get_dp_info(Then0 ^ hlds_goal_info)
+                ;
+                    Use2Pass = no,
+                    ThenHasPortCounts = goal_does_not_have_port_counts
+                ),
+                
+                (
+                    ThenHasPortCounts = goal_does_not_have_port_counts,
+
+                    CoverageAfterElseKnown = coverage_after_known,
+                    CoverageAfterThenKnown = coverage_after_unknown
+                ;
+                    ThenHasPortCounts = goal_has_port_counts,
+                   
+                    % 
+                    % Although we don't know if Else has port counts, at
+                    % this point we're either making the deliberate
+                    % decision below or an arbitrary decision, so
+                    % it doesn't matter if Else has port counts or not.
+                    %
+                    CoverageAfterElseKnown = coverage_after_unknown,
+                    CoverageAfterThenKnown = coverage_after_known
+                )
+            ;
+                ( ElseDetism = detism_semi
+                ; ElseDetism = detism_multi
+                ; ElseDetism = detism_non
+                ; ElseDetism = detism_cc_non
+                ; ElseDetism = detism_erroneous
+                ; ElseDetism = detism_failure
+                ),
+                CoverageAfterElseKnown = coverage_after_unknown,
+                CoverageAfterThenKnown = coverage_after_unknown
+            )
+        ;
+            ( ThenDetism = detism_semi
+            ; ThenDetism = detism_multi
+            ; ThenDetism = detism_non
+            ; ThenDetism = detism_cc_non
+            ; ThenDetism = detism_erroneous
+            ; ThenDetism = detism_failure
+            ),
+            CoverageAfterElseKnown = coverage_after_unknown,
+            CoverageAfterThenKnown = coverage_after_unknown
+        )
+    ;
+        CoverageAfterITEKnown = coverage_after_unknown,
+        CoverageAfterElseKnown = coverage_after_unknown,
+        CoverageAfterThenKnown = coverage_after_unknown
+    ),
+    
+    
+    % Transform Else branch,
+    coverage_prof_second_pass_goal(snoc(Path, step_ite_else), Else0, Else1, 
+        CoverageAfterElseKnown, CoverageBeforeElseKnown1, !Info, 
+        AddedImpurityElseGoal),
+   
+    % Transform Then branch.
+    coverage_prof_second_pass_goal(snoc(Path, step_ite_then), Then0, Then1,
+        CoverageAfterThenKnown, CoverageBeforeThenKnown1, !Info,
+        AddedImpurityThenGoal),
+    
+    %
+    % Gather information and decide what coverage points to insert.
+    %
+    % Notice that it doesn't matter if any of the goals are trivial or not,
+    % we want to know what branch is taken regardless of how inexpensive it
+    % may be as different variables may be used in different branches.
+    %
+    % Whatever we do we will ensure that the coverage will be known at the
+    % beginning of each branch,
+    %
+    CPOBranchIf = !.Info ^ ci_coverage_profiling_opts ^ cpo_branch_ite,
+    dp_goal_info(_, CondHasPortCounts) =
+        Cond0 ^ hlds_goal_info ^ goal_info_get_dp_info, 
+    (
+        CPOBranchIf = yes,
+        CondHasPortCounts = goal_does_not_have_port_counts,
+        
+        (
+            CoverageBeforeThenKnown1 = coverage_after_unknown,
+            
+            InsertCPThen = yes(coverage_point_info(snoc(Path, step_ite_then),
+                cp_type_branch_arm))
+        ;
+            CoverageBeforeThenKnown1 = coverage_after_known,
+            
+            InsertCPThen = no
+        ),
+        (
+            CoverageBeforeElseKnown1 = coverage_after_unknown,
+       
+            InsertCPElse = yes(coverage_point_info(snoc(Path, step_ite_else),
+                cp_type_branch_arm))
+        ;
+            CoverageBeforeElseKnown1 = coverage_after_known,
+            
+            InsertCPElse = no
+        )
+    ;
+        CPOBranchIf = yes,
+        CondHasPortCounts = goal_has_port_counts,
+        
+        % Don't insert any coverage points.
+        InsertCPThen = no,
+        InsertCPElse = no
+    ;
+        CPOBranchIf = no,
+        
+        % Don't insert any coverage points,
+        InsertCPThen = no,
+        InsertCPElse = no
+    ),
+
+    %
+    % Insert any coverage points.
+    %
+    maybe_insert_coverage_point_before(InsertCPElse, Else1, Else,
+        CoverageBeforeElseKnown1, CoverageBeforeElseKnown, !Info, 
+        AddedImpurityElseCP),
+    bool.or(AddedImpurityElseGoal, AddedImpurityElseCP, AddedImpurityElse),
+
+    maybe_insert_coverage_point_before(InsertCPThen, Then1, Then,
+        CoverageBeforeThenKnown1, CoverageBeforeThenKnown, !Info,
+        AddedImpurityThenCP),
+    bool.or(AddedImpurityThenGoal, AddedImpurityThenCP, AddedImpurityThen),
+
+    %
+    % Transform Cond branch.
+    %
+    coverage_after_known_branch(CoverageBeforeThenKnown,
+        CoverageBeforeElseKnown, CoverageKnownAfterCond),
+    coverage_prof_second_pass_goal(snoc(Path, step_ite_cond), 
+        Cond0, Cond, CoverageKnownAfterCond, NextCoverageAfterKnown, !Info,
+        AddedImpurityCond),
+    
+    %
+    % Build goal experession and tidy up.
+    %
+    AddedImpurity = bool.or(AddedImpurityCond,
+        bool.or(AddedImpurityThen, AddedImpurityElse)), 
+    GoalExpr = if_then_else(ITEExistVars, Cond, Then, Else).
+
+
+    % Insert a coverage point in a conjunction before the current goal if
+    % the coverage point info has been provided.
+    %
+:- pred maybe_insert_coverage_point_before(maybe(coverage_point_info)::in,
+    hlds_goal::in, hlds_goal::out,
+    coverage_after_known::in, coverage_after_known::out, 
+    proc_coverage_info::in, proc_coverage_info::out, bool::out) is det.
+
+maybe_insert_coverage_point_before(no, !Goal, !CoverageAfterKnown,
+    !Info, no).
+
+maybe_insert_coverage_point_before(yes(CPInfo), !Goal,
+        _, coverage_after_known, !Info, yes) :-
+    insert_coverage_point_before(CPInfo, !Goal, !Info).
+
+
+    % Insert a coverage point before the given goal,  This returns a flat
+    % conjunction consisting of a coverage point followed by the input
+    % goal.
+    %
+:- pred insert_coverage_point_before(coverage_point_info::in,
+    hlds_goal::in, hlds_goal::out, 
+    proc_coverage_info::in, proc_coverage_info::out) is det.
+
+insert_coverage_point_before(CPInfo, !Goal, !Info) :-
+    make_coverage_point(CPInfo, CPGoals, !Info),
+    (
+        !.Goal = hlds_goal(conj(plain_conj, InnerGoals), _)
+    ->
+        Goals = CPGoals ++ InnerGoals
+    ;
+        Goals = CPGoals ++ [!.Goal]
+    ),
+    create_conj_from_list(Goals, plain_conj, !:Goal).
+
+
+    % Used to describe if coverage information is known at a partiular point
+    % within a procedure.
+    %
+:- type coverage_after_known
+    --->    coverage_after_known
+    ;       coverage_after_unknown.
+
+    % At a branch of execution two coverage known values must be merged,
+    % this is at the beginning of the branch since it's used for the main
+    % pass which is done in reverse.
+    %
+:- pred coverage_after_known_branch(coverage_after_known::in,
+    coverage_after_known::in, coverage_after_known::out) is det.
+
+coverage_after_known_branch(coverage_after_known, coverage_after_known,
+    coverage_after_known).
+coverage_after_known_branch(coverage_after_known, coverage_after_unknown,
+    coverage_after_unknown).
+coverage_after_known_branch(coverage_after_unknown, _,
+    coverage_after_unknown).
+    
+    % Create a coverage info struture, initializing some values to sensible
+    % defaults..
+    %
+:- func init_proc_coverage_info(var_info, module_info, pred_proc_id,
+        maybe(deep_recursion_info), coverage_profiling_options) = 
+    proc_coverage_info.
+
+init_proc_coverage_info(VarInfo, ModuleInfo, PredProcId, MaybeRecInfo,
+        CoverageProfilingOptions) = CoverageInfo :-
+    CoverageInfo = proc_coverage_info(map.init, counter.init(0), VarInfo,
+        ModuleInfo, PredProcId, MaybeRecInfo, CoverageProfilingOptions).
+
+    % Boolean or for goal_trivial data type.
+    %
+:- pred goal_trivial_and(goal_trivial::in, goal_trivial::in,
+    goal_trivial::out) is det.
+
+goal_trivial_and(A, B, Trivial) :-
+    (
+        A = goal_is_trivial,
+        B = goal_is_trivial
+    ->
+        Trivial = goal_is_trivial
+    ;
+        Trivial = goal_is_nontrivial
+    ).
+
+
+:- pred goal_has_port_counts_and(goal_has_port_counts::in,
+    goal_has_port_counts::in, goal_has_port_counts::out) is det.
+
+goal_has_port_counts_and(A, B, HasPortCounts) :-
+    (
+        A = goal_has_port_counts,
+        B = goal_has_port_counts
+    ->
+        HasPortCounts = goal_has_port_counts
+    ;
+        HasPortCounts = goal_does_not_have_port_counts
+    ).
+
+
+    % Given the a goal and whether port counts are availible before it
+    % determine if port counts can be used to determine how often execution
+    % reaches the poind imediatly after this goal.
+    %
+:- pred has_port_counts_after(hlds_goal::in, goal_has_port_counts::in,
+    goal_has_port_counts::in, goal_has_port_counts::out) is det.
+
+has_port_counts_after(Goal, PCDirect, PCBefore, PC) :-
+    (
+        % 
+        % The trivial case.  If port counts are directly availible then
+        % the can be used to determine coverage immediately after it.
+        %
+        PCDirect = goal_has_port_counts,
+        PC = goal_has_port_counts
+    ;
+        PCDirect = goal_does_not_have_port_counts,
+        
+        %
+        % If port counts arn't directly avalible but are before this goal
+        % and this goal behaves deterministically (it cannot fail or redo),
+        % then they can be used to determine how often execution reaches the
+        % point after this goal).
+        %
+        Detism = Goal ^ hlds_goal_info ^ goal_info_get_determinism,
+        has_port_counts_if_det(Detism, PCBefore, PC)
+    ).
+    
+    
+    % Given the current goal's determinism and wheather the next earliest goal
+    % has port counts does this goal have port counts
+    %
+:- pred has_port_counts_if_det(determinism::in, goal_has_port_counts::in,
+    goal_has_port_counts::out) is det.
+
+has_port_counts_if_det(Detism, HasPortCounts0, HasPortCounts) :-
+    (
+        ( Detism = detism_det
+        ; Detism = detism_cc_multi )
+    ->
+        HasPortCounts = HasPortCounts0
+    ;
+        HasPortCounts = goal_does_not_have_port_counts
+    ).
+
+
+
+    % Used to gather some information about goals before the coverage
+    % transformation.
+    %
+:- pred coverage_prof_first_pass(coverage_profiling_options::in, hlds_goal::in,
+    hlds_goal::out, goal_has_port_counts::in, dp_goal_info::out) is det.
+
+coverage_prof_first_pass(CPOptions, Goal0, hlds_goal(GoalExpr, GoalInfo),
+        HasPortCountsBefore, Info) :-
+    Goal0 = hlds_goal(GoalExpr0, GoalInfo0),
+
+    (
+        %
+        % Call Goals
+        %
+        ( GoalExpr0 = plain_call(_, _, _, _, _, _)
+        ; GoalExpr0 = generic_call(_, _, _, _)
+        ; GoalExpr0 = call_foreign_proc(_, _, _, _, _, _, _) ),
+        
+        Trivial0 = goal_is_nontrivial,
+        HasPortCountsDirect = goal_has_port_counts,
+        GoalExpr = GoalExpr0
+    ;
+        GoalExpr0 = unify(_, _, _, _, _),
+
+        Trivial0 = goal_is_trivial,
+        HasPortCountsDirect = goal_does_not_have_port_counts,
+        GoalExpr = GoalExpr0
+    ;
+        GoalExpr0 = conj(ConjType, Goals0),
+        map_foldl2(coverage_prof_first_pass_conj(CPOptions), Goals0, Goals,
+            goal_is_trivial, Trivial0, HasPortCountsBefore,
+            HasPortCountsDirect),
+        GoalExpr = conj(ConjType, Goals) 
+    ;
+        GoalExpr0 = disj(Goals0),
+        coverage_prof_first_pass_disj(CPOptions, Goals0, Goals,
+            Trivial0, HasPortCountsBefore, HasPortCountsDirect0),
+        GoalExpr = disj(Goals),
+        
+        %
+        % Only if the disjunction cannot fail can we know the coverage after
+        % the disjunction if port counts are available from every disjunct.
+        %
+        Detism = goal_info_get_determinism(GoalInfo0),
+        determinism_components(Detism, CanFail, _),
+        (
+            CanFail = can_fail,
+            HasPortCountsDirect = goal_does_not_have_port_counts
+        ;
+            CanFail = cannot_fail,
+            HasPortCountsDirect0 = HasPortCountsDirect
+        )
+    ;
+        GoalExpr0 = switch(Var, CanFail, Cases0),
+        coverage_prof_first_pass_switchcase(CPOptions, Cases0, Cases, Trivial0,
+            HasPortCountsCases),
+        GoalExpr = switch(Var, CanFail, Cases),
+        (
+            CanFail = can_fail,
+            HasPortCountsDirect = goal_does_not_have_port_counts
+        ;
+            CanFail = cannot_fail,
+            HasPortCountsDirect = HasPortCountsCases
+        )
+    ;
+        GoalExpr0 = negation(InnerGoal0),
+        coverage_prof_first_pass(CPOptions, InnerGoal0, InnerGoal,
+            HasPortCountsBefore, dp_goal_info(Trivial0, HasPortCountsDirect)),
+        GoalExpr = negation(InnerGoal)
+    ;
+        GoalExpr0 = scope(Reason, InnerGoal0),
+        coverage_prof_first_pass(CPOptions, InnerGoal0, InnerGoal,
+            HasPortCountsBefore, dp_goal_info(Trivial0, HasPortCountsDirect)),
+        GoalExpr = scope(Reason, InnerGoal)
+    ;
+        GoalExpr0 = if_then_else(Vars, CondGoal0, ThenGoal0, ElseGoal0),
+       
+        %
+        % The then and else parts of a ITE goal will be able to use the
+        % port counts provided by the cond goal if it has them.
+        %
+        coverage_prof_first_pass(CPOptions, CondGoal0, CondGoal,
+            HasPortCountsBefore, dp_goal_info(TrivialCond, HasPortCountsCond)),
+        
+        coverage_prof_first_pass(CPOptions, ThenGoal0, ThenGoal,
+            HasPortCountsCond, dp_goal_info(TrivialThen, HasPortCountsThen)),
+        coverage_prof_first_pass(CPOptions, ElseGoal0, ElseGoal,
+            HasPortCountsCond, dp_goal_info(TrivialElse, HasPortCountsElse)),
+
+        GoalExpr = if_then_else(Vars, CondGoal, ThenGoal, ElseGoal),
+
+
+        %
+        % An ITE is trivial iff all of it's inner goals are trivial, 
+        %
+        goal_trivial_and(TrivialCond, TrivialThen, Trivial1),
+        goal_trivial_and(Trivial1, TrivialElse, Trivial0),
+
+        %
+        % And it has port counts iff it will end in a goal with a port count
+        % regardless of how the condition evaluates.
+        %
+        goal_has_port_counts_and(HasPortCountsThen, HasPortCountsElse,
+            HasPortCountsDirect)
+    ;
+        GoalExpr0 = shorthand(_),
+        unexpected(this_file, 
+            "deep_profiling.goal_is_nontrivial: " ++ 
+            "shorthand should have gone by now")
+    ),
+    
+    (
+        CPOptions ^ cpo_use_portcounts = yes,
+        has_port_counts_after(Goal0, HasPortCountsDirect, HasPortCountsBefore,
+            HasPortCounts)
+    ;
+        CPOptions ^ cpo_use_portcounts = no,
+        HasPortCounts = goal_does_not_have_port_counts
+    ),
+   
+    (
+        CPOptions ^ cpo_use_trivial = yes,
+        Trivial = Trivial0
+    ;
+        CPOptions ^ cpo_use_trivial = no,
+        Trivial = goal_is_nontrivial
+    ),
+
+    %
+    % Annotate the goal with this new information.
+    %
+    Info = dp_goal_info(Trivial, HasPortCounts),
+    goal_info_set_maybe_dp_info(yes(Info), GoalInfo0, GoalInfo).
+
+
+    % Combine information about goals within a conjunction
+    %
+:- pred coverage_prof_first_pass_conj(coverage_profiling_options::in,
+    hlds_goal::in, hlds_goal::out, goal_trivial::in, goal_trivial::out,
+    goal_has_port_counts::in, goal_has_port_counts::out) is det.
+
+coverage_prof_first_pass_conj(CPOptions, Goal0, Goal, TrivialAcc, Trivial,
+        HasPortCountsAcc, HasPortCounts) :-
+    coverage_prof_first_pass(CPOptions, Goal0, Goal, HasPortCountsAcc,
+        dp_goal_info(TrivialGoal, HasPortCounts)),
+    goal_trivial_and(TrivialAcc, TrivialGoal, Trivial).
+
+
+    % Combine information about goals within a disjunction
+    %
+    % A portcount may be avalible to the goal executed when first entering a
+    % disjunction.  However it's impractical to deterimine if any disjuncts
+    % other than the first are ever tried.  So port counts at the beginning of
+    % them are unknown.
+    %
+:- pred coverage_prof_first_pass_disj(coverage_profiling_options::in,
+    list(hlds_goal)::in, list(hlds_goal)::out, goal_trivial::out, 
+    goal_has_port_counts::in, goal_has_port_counts::out) is det.
+
+coverage_prof_first_pass_disj(_, [], [], goal_is_trivial, !HasPortCounts).
+
+coverage_prof_first_pass_disj(CPOptions, [ Goal0 | Goals0 ], [ Goal | Goals ],
+        Trivial, HasPortCountsBefore, HasPortCounts) :-
+    coverage_prof_first_pass(CPOptions, Goal0, Goal, HasPortCountsBefore,
+        dp_goal_info(TrivialGoal, HasPortCountsGoal)),
+    coverage_prof_first_pass_disj(CPOptions, Goals0, Goals, TrivialDisj,
+        goal_does_not_have_port_counts, HasPortCountsDisj), 
+    goal_trivial_and(TrivialGoal, TrivialDisj, Trivial),
+    goal_has_port_counts_and(HasPortCountsGoal, HasPortCountsDisj,
+        HasPortCounts).
+
+
+    % A switch is handled like a disjunction except that it can't be known
+    % how often execution will enter the first case, so this also cannot use
+    % the portcount of a goal before it.
+    %
+:- pred coverage_prof_first_pass_switchcase(coverage_profiling_options::in,
+    list(case)::in, list(case)::out, goal_trivial::out, 
+    goal_has_port_counts::out) is det.
+
+coverage_prof_first_pass_switchcase(_, [], [], goal_is_trivial, 
+    goal_has_port_counts).
+
+coverage_prof_first_pass_switchcase(CPOptions, 
+    [ Case0 | Cases0 ], [ Case | Cases ], Trivial, HasPortCounts) :-
+    Case0 = case(FirstFunctor, LaterFunctors, Goal0),
+
+    coverage_prof_first_pass(CPOptions, Goal0, Goal,
+        goal_does_not_have_port_counts, 
+        dp_goal_info(TrivialGoal, HasPortCountsGoal)),
+    coverage_prof_first_pass_switchcase(CPOptions, Cases0, Cases,
+        TrivialSwitchcase, HasPortCountsSwitchcase), 
+    goal_trivial_and(TrivialGoal, TrivialSwitchcase, Trivial),
+    goal_has_port_counts_and(HasPortCountsGoal, HasPortCountsSwitchcase,
+        HasPortCounts),
+
+    Case = case(FirstFunctor, LaterFunctors, Goal).
+
+
+    % Builds a list of goals that will form a conjunction) for a coverage
+    % point.
+    %
+:- pred make_coverage_point(coverage_point_info::in, list(hlds_goal)::out, 
+    proc_coverage_info::in, proc_coverage_info::out) is det.
+
+make_coverage_point(CoveragePointInfo, Goals, !CoverageInfo) :-
+    CoveragePointInfos0 = !.CoverageInfo ^ ci_coverage_points,
+    CPIndexCounter0 = !.CoverageInfo ^ ci_cp_index_counter,
+
+    counter.allocate(CPIndex, CPIndexCounter0, CPIndexCounter),
+    map.det_insert(CoveragePointInfos0, CPIndex, CoveragePointInfo, 
+        CoveragePointInfos),
+    !:CoverageInfo = !.CoverageInfo ^ ci_coverage_points := CoveragePointInfos,
+    !:CoverageInfo = !.CoverageInfo ^ ci_cp_index_counter := CPIndexCounter,
+
+    %
+    % Build unifications for the coverage point index and the proc static.
+    %
+    some [!VarInfo] (
+        !:VarInfo = !.CoverageInfo ^ ci_var_info,
+        
+        generate_var("CPIndex", int_type, CPIndexVar, !VarInfo),
+        generate_unify(int_const(CPIndex), CPIndexVar, GoalUnifyIndex),
+        generate_var("ProcLayout", c_pointer_type, ProcLayoutVar, !VarInfo),
+        proc_static_cons_id(!.CoverageInfo, ProcStaticConsId),
+        generate_unify(ProcStaticConsId, ProcLayoutVar, GoalUnifyProcLayout), 
+        
+        !:CoverageInfo = !.CoverageInfo ^ ci_var_info := !.VarInfo
+    ),
+
+    %
+    % Build a call to the instrumentation code.
+    %
+    ModuleInfo = !.CoverageInfo ^ ci_module_info,
+    get_deep_profile_builtin_ppid(ModuleInfo, "increment_coverage_point_count", 
+        2, PredId, ProcId),
+    Ground = ground(shared, none),
+    make_foreign_args([ ProcLayoutVar, CPIndexVar ],
+        [ (yes("ProcLayout" - (Ground -> Ground)) - native_if_possible),
+          (yes("CPIndex" - (Ground -> Ground)) - native_if_possible) ],
+        [ c_pointer_type, int_type ], ForeignArgVars),
+    coverage_point_ll_code(ForeignCallAttrs, ForeignCode),
+    CallGoalExpr = call_foreign_proc(ForeignCallAttrs, PredId, ProcId, 
+        ForeignArgVars, [], no, ForeignCode),
+    
+    Vars = [ ProcLayoutVar, CPIndexVar ],
+    NonLocals = list_to_set(Vars),
+    instmap_delta_from_assoc_list(assoc_list.from_corresponding_lists(Vars, 
+        [Ground, Ground]), InstMapDelta),
+    CallGoalInfo = impure_init_goal_info(NonLocals, InstMapDelta, detism_det),
+    CallGoal = hlds_goal(CallGoalExpr, CallGoalInfo), 
+
+    % construct complete goal list.
+    Goals = [ GoalUnifyIndex, GoalUnifyProcLayout, CallGoal ].
+      
+
+
+    % Turn a map of coverage points and their indexs into a list in sorted
+    % order.
+    %
+:- pred coverage_points_map_list(map(int, coverage_point_info)::in, 
+    list(coverage_point_info)::out) is det.
+
+coverage_points_map_list(Map, List) :-
+    to_sorted_assoc_list(Map, AssocList),
+    values(AssocList, List).
+
+
+    % Retrive the pred and proc ids from either the deep_mabye_rec_info or
+    % deep_pred_proc_id fields of a deep_info structure.
+    %
+:- pred pred_proc_id(proc_coverage_info::in, pred_id::out, proc_id::out) is det.
+
+pred_proc_id(CoverageInfo, PredId, ProcId) :-
+    MaybeRecInfo = CoverageInfo ^ ci_maybe_rec_info,
+    PredProcId = CoverageInfo ^ ci_pred_proc_id,
+    (
+        MaybeRecInfo = yes(RecInfo),
+        RecInfo ^ role = inner_proc(OuterPredProcId)
+    ->
+        OuterPredProcId = proc(PredId, ProcId)
+    ;
+        PredProcId = proc(PredId, ProcId)
+    ).
+    
+    
+    % Create a proc static cons id from the deep recursion info.  This is used
+    % in several places.
+    %
+:- pred proc_static_cons_id(proc_coverage_info::in, cons_id::out) is det.
+
+proc_static_cons_id(CoverageInfo, ProcStaticConsId) :-
+    pred_proc_id(CoverageInfo, PredId, ProcId),
+    ShroudedPredProcId = shroud_pred_proc_id(proc(PredId, ProcId)),
+    ProcStaticConsId = deep_profiling_proc_layout(ShroudedPredProcId).
+
+
+    % Returns a string containing the Low Level C code for a coverage point.
+    %
+:- pred coverage_point_ll_code(pragma_foreign_proc_attributes::out, 
+    pragma_foreign_code_impl::out) is det.
+
+coverage_point_ll_code(ForeignProcAttrs, ForeignCodeImpl) :-
+    some [ !ForeignProcAttrs ] (
+        % I don't think this would be thread safe but the cost of the mutexes
+        % may be too high.
+        !:ForeignProcAttrs = default_attributes(lang_c),
+        set_may_call_mercury(proc_will_not_call_mercury, !ForeignProcAttrs),
+        set_purity(purity_impure, !ForeignProcAttrs),
+        set_terminates(proc_terminates, !ForeignProcAttrs),
+        set_may_throw_exception(proc_will_not_throw_exception, 
+            !ForeignProcAttrs),
+        ForeignProcAttrs = !.ForeignProcAttrs
+    ),
+    ForeignCodeImpl = fc_impl_ordinary(Code, no),
+    Code = 
+"{
+#ifdef MR_DEEP_PROFILING
+
+    const MR_ProcLayout *pl;
+    MR_ProcStatic       *ps;
+
+    MR_enter_instrumentation();
+
+  #ifdef MR_DEEP_PROFILING_LOWLEVEL_DEBUG
+    if (MR_calldebug && MR_lld_print_enabled) {
+        MR_print_deep_prof_vars(stdout, ""increment_coverage_point_count"");
+        printf("", ProcLayout: 0x%x, CPIndex: %d\\n"", ProcLayout, CPIndex);
+    }
+  #endif
+
+    pl = (const MR_ProcLayout *) ProcLayout;
+
+    MR_deep_assert(NULL, NULL, NULL, pl != NULL);
+    ps = pl->MR_sle_proc_static;
+    MR_deep_assert(NULL, pl, NULL, ps != NULL);
+
+    MR_deep_assert(NULL, pl, ps, 
+        CPIndex >= ps->MR_ps_num_coverage_points);
+    MR_deep_assert(NULL, pl, ps, ps->MR_ps_coverage_points != NULL);
+
+    ps->MR_ps_coverage_points[CPIndex]++;
+
+    /*
+     * This procedure doesn't collect statistics about the deep profiler as
+     * they can be generated by the profiling data it's self.
+     */
+
+    MR_leave_instrumentation();
+#else
+    MR_fatal_error(
+        ""increment_coverage_point_count: deep profiling not enabled"");
+#endif /* MR_DEEP_PROFILING */
+}".
+
 %-----------------------------------------------------------------------------%
 
 :- func this_file = string.
Index: compiler/goal_util.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/goal_util.m,v
retrieving revision 1.158
diff -u -p -r1.158 goal_util.m
--- compiler/goal_util.m	28 Apr 2008 00:50:53 -0000	1.158
+++ compiler/goal_util.m	29 Jul 2008 23:55:11 -0000
@@ -234,6 +234,12 @@
     %
 :- pred flatten_conj(hlds_goals::in, hlds_goals::out) is det.
 
+    % Create a conjunction of the specified type using the specified goals,
+    % This fills in the hlds_goal_info.
+    %
+:- pred create_conj_from_list(list(hlds_goal)::in, conj_type::in,
+    hlds_goal::out) is det.
+
     % Create a conjunction of the specified type using the specified two goals.
     % This fills in the hlds_goal_info.
     %
@@ -1329,7 +1335,15 @@ flatten_conj([Goal | Goals0], Goals) :-
 %-----------------------------------------------------------------------------%
 
 create_conj(GoalA, GoalB, Type, ConjGoal) :-
-    GoalsInConj = [ GoalA, GoalB ],
+    create_conj_from_list([GoalA, GoalB], Type, ConjGoal).
+
+create_conj_from_list(GoalsInConj, Type, ConjGoal) :-
+    (
+        GoalsInConj = [ GoalA | _ ]
+    ;
+        GoalsInConj = [],
+        unexpected(this_file, "create_conj_from_list: empty conjunction")
+    ),
     ConjGoalExpr = conj(Type, GoalsInConj),
     goal_list_nonlocals(GoalsInConj, NonLocals),
     goal_list_instmap_delta(GoalsInConj, InstMapDelta),
Index: compiler/handle_options.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/handle_options.m,v
retrieving revision 1.321
diff -u -p -r1.321 handle_options.m
--- compiler/handle_options.m	23 Jul 2008 23:20:33 -0000	1.321
+++ compiler/handle_options.m	29 Jul 2008 23:55:11 -0000
@@ -1156,6 +1156,11 @@ postprocess_options_2(OptionTable0, Targ
 
         option_implies(target_debug, strip, bool(no), !Globals),
 
+
+        % Coverage profiling requires deep profiling.
+        option_implies(coverage_profiling, profile_deep, bool(yes),
+            !Globals),
+        
         % Inlining happens before the deep profiling transformation, so if
         % we allowed inlining to happen, then we would lose all profiling
         % information about the inlined calls - this is not usually what we
@@ -2103,6 +2108,7 @@ postprocess_options_lowlevel(!Globals) :
     ),
     globals.set_option(static_code_addresses, bool(StaticCodeAddrs), !Globals).
 
+    
     % option_implies(SourceBoolOption, ImpliedOption, ImpliedOptionValue):
     % If the SourceBoolOption is set to yes, then the ImpliedOption is set
     % to ImpliedOptionValue.
@@ -2837,9 +2843,12 @@ char_is_not(A, B) :-
 
 :- pred convert_dump_alias(string::in, string::out) is semidet.
 
-convert_dump_alias("ALL", "abcdfgilmnprstuvzBCDIMPRSTUZ").
-convert_dump_alias("allD", "abcdfgilmnprstuvzBCDMPT").
-convert_dump_alias("all", "abcdfgilmnprstuvzBCMPSTZ").
+%
+% none of the 'all' aliases actually include all the options,
+%
+convert_dump_alias("ALL", "abcdEfgilmnprstuvzBCDIMPRSTUZ").
+convert_dump_alias("allD", "abcdEfgilmnprstuvzBCDMPT").
+convert_dump_alias("all", "abcdEfgilmnprstuvzBCMPSTZ").
 convert_dump_alias("most", "bcdfgilmnprstuvzP").
 convert_dump_alias("trans", "bcdglmnstuvz").
 convert_dump_alias("mintrans", "bcdglmnstvz").
Index: compiler/hlds_goal.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/hlds_goal.m,v
retrieving revision 1.193
diff -u -p -r1.193 hlds_goal.m
--- compiler/hlds_goal.m	19 Jun 2008 09:07:05 -0000	1.193
+++ compiler/hlds_goal.m	29 Jul 2008 23:55:11 -0000
@@ -1073,6 +1073,25 @@
 
 :- type missed_message == string.
 
+
+    % Information used by the deep profilier to preform coverage profiling.
+    % Predicates to operate on these types exist in deep_profiling.m
+    %
+:- type goal_trivial
+    --->    goal_is_trivial
+    ;       goal_is_nontrivial.
+   
+:- type goal_has_port_counts
+    --->    goal_has_port_counts
+    ;       goal_does_not_have_port_counts.
+
+:- type dp_goal_info
+    --->    dp_goal_info(
+                goal_trivial,
+                goal_has_port_counts
+            ).
+
+
 :- pred goal_info_init(hlds_goal_info::out) is det.
 :- pred goal_info_init(prog_context::in, hlds_goal_info::out) is det.
 :- pred goal_info_init(set(prog_var)::in, instmap_delta::in, determinism::in,
@@ -1106,6 +1125,7 @@
 :- func goal_info_get_maybe_lfu(hlds_goal_info) = maybe(set(prog_var)).
 :- func goal_info_get_maybe_lbu(hlds_goal_info) = maybe(set(prog_var)).
 :- func goal_info_get_maybe_reuse(hlds_goal_info) = maybe(reuse_description).
+:- func goal_info_get_maybe_dp_info(hlds_goal_info) = maybe(dp_goal_info).
 
 :- pred goal_info_set_determinism(determinism::in,
     hlds_goal_info::in, hlds_goal_info::out) is det.
@@ -1139,6 +1159,8 @@
     hlds_goal_info::out) is det.
 :- pred goal_info_set_reuse(reuse_description::in, hlds_goal_info::in,
     hlds_goal_info::out) is det.
+:- pred goal_info_set_maybe_dp_info(maybe(dp_goal_info)::in, hlds_goal_info::in,
+    hlds_goal_info::out) is det.
 
     % The following functions produce an 'unexpected' error when the
     % requested values have not been set.
@@ -1147,6 +1169,7 @@
 :- func goal_info_get_lfu(hlds_goal_info) = set(prog_var).
 :- func goal_info_get_lbu(hlds_goal_info) = set(prog_var).
 :- func goal_info_get_reuse(hlds_goal_info) = reuse_description.
+:- func goal_info_get_dp_info(hlds_goal_info) = dp_goal_info.
 
 :- pred goal_info_get_occurring_vars(hlds_goal_info::in, set(prog_var)::out)
     is det.
@@ -1731,7 +1754,9 @@ simple_call_id_pred_or_func(simple_call_
 
                 egi_maybe_rbmm          :: maybe(rbmm_goal_info),
 
-                egi_maybe_mode_constr   :: maybe(mode_constr_goal_info)
+                egi_maybe_mode_constr   :: maybe(mode_constr_goal_info),
+
+                egi_maybe_dp            :: maybe(dp_goal_info)
             ).
 
 :- pragma inline(goal_info_init/1).
@@ -1778,7 +1803,7 @@ goal_info_init(NonLocals, InstMapDelta, 
 
 hlds_goal_extra_info_init(Context) = ExtraInfo :-
     HO_Values = map.init,
-    ExtraInfo = extra_goal_info(Context, HO_Values, no, no, no).
+    ExtraInfo = extra_goal_info(Context, HO_Values, no, no, no, no).
 
 :- func ctgc_goal_info_init = ctgc_goal_info.
 
@@ -1800,6 +1825,7 @@ goal_info_get_maybe_rbmm(GoalInfo) = Goa
 goal_info_get_maybe_mode_constr(GoalInfo) =
     GoalInfo ^ gi_extra ^ egi_maybe_mode_constr.
 goal_info_get_maybe_ctgc(GoalInfo) = GoalInfo ^ gi_extra ^ egi_maybe_ctgc.
+goal_info_get_maybe_dp_info(GoalInfo) = GoalInfo ^ gi_extra ^ egi_maybe_dp.
 
 goal_info_set_determinism(Determinism, !GoalInfo) :-
     !GoalInfo ^ gi_determinism := Determinism.
@@ -1825,6 +1851,8 @@ goal_info_set_maybe_mode_constr(ModeCons
     !GoalInfo ^ gi_extra ^ egi_maybe_mode_constr := ModeConstrInfo.
 goal_info_set_maybe_ctgc(CTGCInfo, !GoalInfo) :-
     !GoalInfo ^ gi_extra ^ egi_maybe_ctgc := CTGCInfo.
+goal_info_set_maybe_dp_info(DPInfo, !GoalInfo) :-
+    !GoalInfo ^ gi_extra ^ egi_maybe_dp := DPInfo.
 
     % The code-gen non-locals are always the same as the
     % non-locals when structure reuse is not being performed.
@@ -2094,6 +2122,17 @@ goal_info_get_reuse(GoalInfo) = Reuse :-
             "Requesting reuse information while CTGC field not set.")
     ).
 
+goal_info_get_dp_info(GoalInfo) = DPInfo :-
+    MaybeDPInfo = goal_info_get_maybe_dp_info(GoalInfo),
+    (
+        MaybeDPInfo = yes(DPInfo)
+    ;
+        MaybeDPInfo = no,
+        unexpected(this_file,
+            "Requesting dp_info while maybe_dp_info field not set.")
+    ).
+
+
 %-----------------------------------------------------------------------------%
 
 goal_get_purity(hlds_goal(_GoalExpr, GoalInfo)) =
@@ -2442,7 +2481,7 @@ rename_vars_in_goal_info(Must, Subn, !Go
     ),
 
     ExtraInfo0 = extra_goal_info(Context, HO_Values, MaybeCTGC0, MaybeRBMM0,
-        MaybeMCI0),
+        MaybeMCI0, MaybeDPInfo0),
     (
         MaybeCTGC0 = no,
         MaybeCTGC = no
@@ -2501,8 +2540,9 @@ rename_vars_in_goal_info(Must, Subn, !Go
             MakeVisible, NeedVisible),
         MaybeMCI = yes(MCI)
     ),
+    MaybeDPInfo = MaybeDPInfo0,
     ExtraInfo = extra_goal_info(Context, HO_Values, MaybeCTGC, MaybeRBMM,
-        MaybeMCI),
+        MaybeMCI, MaybeDPInfo),
 
     !:GoalInfo = goal_info(Detism, InstMapDelta, NonLocals, Purity,
         Features, GoalPath, CodeGenInfo, ExtraInfo).
Index: compiler/hlds_out.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/hlds_out.m,v
retrieving revision 1.452
diff -u -p -r1.452 hlds_out.m
--- compiler/hlds_out.m	5 Jun 2008 03:29:11 -0000	1.452
+++ compiler/hlds_out.m	29 Jul 2008 23:55:11 -0000
@@ -1441,6 +1441,32 @@ write_goal_a(hlds_goal(GoalExpr, GoalInf
     ;
         true
     ),
+    ( string.contains_char(Verbose, 'E') ->
+        MaybeDPInfo = goal_info_get_maybe_dp_info(GoalInfo),
+        (
+            MaybeDPInfo = yes(dp_goal_info(Trivial, HasPortCounts)),
+            write_indent(Indent, !IO),
+            (
+                Trivial = goal_is_trivial,
+                io.write_string("% Goal is trivial, ", !IO)
+            ;
+                Trivial = goal_is_nontrivial,
+                io.write_string("% Goal is non-trivial, ", !IO)
+            ),
+            (
+                HasPortCounts = goal_has_port_counts,
+                io.write_string("Goal has port counts avalible.\n", !IO)
+            ;
+                HasPortCounts = goal_does_not_have_port_counts,
+                io.write_string("Goal does not have port counts avalible.\n", 
+                    !IO)
+            )
+        ;
+            MaybeDPInfo = no
+        )
+    ;
+        true
+    ),
     write_goal_2(GoalExpr, ModuleInfo, VarSet, AppendVarNums, Indent, Follow,
         TypeQual, !IO),
     ( string.contains_char(Verbose, 'i') ->
Index: compiler/hlds_pred.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/hlds_pred.m,v
retrieving revision 1.245
diff -u -p -r1.245 hlds_pred.m
--- compiler/hlds_pred.m	21 Jul 2008 03:10:08 -0000	1.245
+++ compiler/hlds_pred.m	29 Jul 2008 23:55:11 -0000
@@ -1683,7 +1683,8 @@ attribute_list_to_attributes(Attributes,
                 proc_static_file_name   :: string,
                 proc_static_line_number :: int,
                 proc_is_in_interface    :: bool,
-                call_site_statics       :: list(call_site_static_data)
+                call_site_statics       :: list(call_site_static_data),
+                coverage_points         :: list(coverage_point_info) 
             ).
 
     % The hlds_deep_excp_vars gives the variables that hold the values returned
Index: compiler/layout.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/layout.m,v
retrieving revision 1.37
diff -u -p -r1.37 layout.m
--- compiler/layout.m	12 Sep 2007 06:21:06 -0000	1.37
+++ compiler/layout.m	29 Jul 2008 23:55:11 -0000
@@ -253,7 +253,9 @@
     ;       module_common_layout(module_name)
     ;       module_layout(module_name)
     ;       proc_static(rtti_proc_label)
-    ;       proc_static_call_sites(rtti_proc_label).
+    ;       proc_static_call_sites(rtti_proc_label)
+    ;       proc_static_coverage_point_static(rtti_proc_label)
+    ;       proc_static_coverage_point_dynamic(rtti_proc_label).
 
 :- type label_layout_details
     --->    label_layout_details(proc_label, int, label_vars).
Index: compiler/layout_out.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/layout_out.m,v
retrieving revision 1.97
diff -u -p -r1.97 layout_out.m
--- compiler/layout_out.m	17 Apr 2008 04:21:51 -0000	1.97
+++ compiler/layout_out.m	29 Jul 2008 23:55:11 -0000
@@ -438,6 +438,18 @@ output_layout_name(Data, !IO) :-
         ProcLabel = make_proc_label_from_rtti(RttiProcLabel),
         output_proc_label_no_prefix(ProcLabel, !IO)
     ;
+        Data = proc_static_coverage_point_static(RttiProcLabel),
+        io.write_string(mercury_data_prefix, !IO),
+        io.write_string("_proc_static_coverage_points_static__", !IO),
+        ProcLabel = make_proc_label_from_rtti(RttiProcLabel),
+        output_proc_label_no_prefix(ProcLabel, !IO)
+    ;
+        Data = proc_static_coverage_point_dynamic(RttiProcLabel),
+        io.write_string(mercury_data_prefix, !IO),
+        io.write_string("_proc_static_coverage_points_dynamic__", !IO),
+        ProcLabel = make_proc_label_from_rtti(RttiProcLabel),
+        output_proc_label_no_prefix(ProcLabel, !IO)
+    ;
         Data = table_io_decl(RttiProcLabel),
         io.write_string(mercury_data_prefix, !IO),
         io.write_string("_table_io_decl__", !IO),
@@ -611,6 +623,16 @@ output_layout_name_storage_type_name(Nam
         output_layout_name(Name, !IO),
         io.write_string("[]", !IO)
     ;
+        Name = proc_static_coverage_point_static(_RttiProcLabel),
+        io.write_string("static const MR_CoveragePointStatic ", !IO),
+        output_layout_name(Name, !IO),
+        io.write_string("[]", !IO)
+    ;
+        Name = proc_static_coverage_point_dynamic(_RttiProcLabel),
+        io.write_string("static MR_Unsigned ", !IO),
+        output_layout_name(Name, !IO),
+        io.write_string("[]", !IO)
+    ;
         Name = table_io_decl(_RttiProcLabel),
         io.write_string("static const MR_TableIoDecl ", !IO),
         output_layout_name(Name, !IO)
@@ -649,6 +671,8 @@ layout_name_would_include_code_addr(modu
 layout_name_would_include_code_addr(module_layout(_)) = no.
 layout_name_would_include_code_addr(proc_static(_)) = no.
 layout_name_would_include_code_addr(proc_static_call_sites(_)) = no.
+layout_name_would_include_code_addr(proc_static_coverage_point_static(_)) = no.
+layout_name_would_include_code_addr(proc_static_coverage_point_dynamic(_)) = no.
 layout_name_would_include_code_addr(table_io_decl(_)) = no.
 
 :- func label_vars_to_type(label_vars) = string.
@@ -2098,9 +2122,18 @@ output_proc_static_data_defn(RttiProcLab
     ProcLayoutProcStatic = proc_layout_proc_static(HLDSProcStatic,
         DeepExcpVars),
     HLDSProcStatic = hlds_proc_static(FileName, LineNumber, IsInInterface,
-        CallSites),
+        CallSites, CoveragePoints),
+   
+    % Write out data the proc static will reference.
     list.foldl2(output_call_site_static_decl, CallSites, !DeclSet, !IO),
     output_call_site_static_array(RttiProcLabel, CallSites, !DeclSet, !IO),
+    output_coverage_point_static_array(RttiProcLabel, CoveragePoints, !DeclSet,
+        !IO),
+    length(CoveragePoints, NumCoveragePoints),
+    output_coverage_point_dynamic_array(RttiProcLabel, NumCoveragePoints, 
+        !DeclSet, !IO),
+
+    % Write out the proc static.
     LayoutName = proc_static(RttiProcLabel),
     io.write_string("\n", !IO),
     output_layout_name_storage_type_name(LayoutName, yes, !IO),
@@ -2132,7 +2165,16 @@ output_proc_static_data_defn(RttiProcLab
     io.write_int(MiddleCSDSlot, !IO),
     io.write_string(",\n", !IO),
     io.write_int(OldOutermostSlot, !IO),
-    io.write_string("\n};\n", !IO),
+    io.write_string(",\n", !IO),
+    io.write_int(NumCoveragePoints, !IO),
+    io.write_string(",\n", !IO),
+    CoveragePointStaticName = proc_static_coverage_point_static(RttiProcLabel),
+    output_layout_name(CoveragePointStaticName, !IO),
+    io.write_string(",\n", !IO),
+    CoveragePointDynamicName = 
+        proc_static_coverage_point_dynamic(RttiProcLabel),
+    output_layout_name(CoveragePointDynamicName, !IO),
+    io.write_string("};\n", !IO),
     decl_set_insert(decl_data_addr(layout_addr(LayoutName)), !DeclSet).
 
 :- pred output_call_site_static_array(rtti_proc_label::in,
@@ -2213,6 +2255,52 @@ output_call_site_static_decl(CallSiteSta
 
 %-----------------------------------------------------------------------------%
 
+
+% Write out a C representation of the coverage point static data.
+:- pred output_coverage_point_static_array(rtti_proc_label::in, 
+    list(coverage_point_info)::in, decl_set::in, decl_set::out,
+    io::di, io::uo) is det.
+
+output_coverage_point_static_array(RttiProcLabel, CoveragePoints, !DeclSet,
+        !IO) :- 
+    LayoutName = proc_static_coverage_point_static(RttiProcLabel),
+    io.write_string("\n", !IO),
+    output_layout_name_storage_type_name(LayoutName, yes, !IO),
+    io.write_string(" = {\n", !IO),
+    list.foldl(output_coverage_point_static, CoveragePoints, !IO),
+    io.write_string("};\n", !IO),
+    decl_set_insert(decl_data_addr(layout_addr(LayoutName)), !DeclSet).
+
+
+:- pred output_coverage_point_static(coverage_point_info::in, io::di, io::uo) 
+    is det.
+
+output_coverage_point_static(coverage_point_info(GoalPath, CPType), !IO) :-
+    io.write_string("{ """, !IO),
+    GoalPathString = goal_path_to_string(GoalPath),
+    io.write_string(GoalPathString, !IO),
+    io.write_string(""", ", !IO),
+    coverage_point_type_c_value(CPType, CPTypeCValue),
+    io.write_string(CPTypeCValue, !IO),
+    io.write_string(" },\n", !IO).
+
+
+:- pred output_coverage_point_dynamic_array(rtti_proc_label::in, int::in, 
+    decl_set::in, decl_set::out, io::di, io::uo) is det.
+
+output_coverage_point_dynamic_array(RttiProcLabel, NumCoveragePoints, !DeclSet, !IO) :-
+    LayoutName = proc_static_coverage_point_dynamic(RttiProcLabel),
+    io.write_string("\n", !IO),
+    output_layout_name_storage_type_name(LayoutName, yes, !IO),
+    io.write_string(" = {\n", !IO),
+    duplicate(NumCoveragePoints, "0,", Zeros),
+    io.write_strings(Zeros, !IO),
+    io.write_string("};\n", !IO),
+    decl_set_insert(decl_data_addr(layout_addr(LayoutName)), !DeclSet).
+
+
+%-----------------------------------------------------------------------------%
+
 :- pred output_table_io_decl(rtti_proc_label::in, proc_layout_kind::in,
     int::in, rval::in, rval::in, decl_set::in, decl_set::out,
     io::di, io::uo) is det.
Index: compiler/opt_debug.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/opt_debug.m,v
retrieving revision 1.206
diff -u -p -r1.206 opt_debug.m
--- compiler/opt_debug.m	11 Feb 2008 21:26:05 -0000	1.206
+++ compiler/opt_debug.m	29 Jul 2008 23:55:11 -0000
@@ -564,6 +564,12 @@ dump_layout_name(proc_static(RttiProcLab
     "proc_static(" ++ dump_rttiproclabel(RttiProcLabel) ++ ")".
 dump_layout_name(proc_static_call_sites(RttiProcLabel)) =
     "proc_static_call_sites(" ++ dump_rttiproclabel(RttiProcLabel) ++ ")".
+dump_layout_name(proc_static_coverage_point_static(RttiProcLabel)) =
+    "proc_static_coverage_point_static(" ++ dump_rttiproclabel(RttiProcLabel) 
+        ++ ")".
+dump_layout_name(proc_static_coverage_point_dynamic(RttiProcLabel)) =
+    "proc_static_coverage_point_dynamic(" ++ dump_rttiproclabel(RttiProcLabel) 
+        ++ ")".
 dump_layout_name(table_io_decl(RttiProcLabel)) =
     "table_io_decl(" ++ dump_rttiproclabel(RttiProcLabel) ++ ")".
 
Index: compiler/options.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.623
diff -u -p -r1.623 options.m
--- compiler/options.m	29 Jul 2008 05:13:21 -0000	1.623
+++ compiler/options.m	29 Jul 2008 23:55:11 -0000
@@ -293,6 +293,21 @@
             % cycle detection should be used for deep profiling. Actually,
             % we only want to use the `yes' value, but we keep support for
             % the `no' value for benchmarks for the paper.
+    
+            % Perform coverage profiling, (enables deep profiling).
+    ;       coverage_profiling
+   
+            % What types of coverage points to instrument the code with.
+    ;       profile_deep_coverage_may_fail
+    ;       profile_deep_coverage_multi
+    ;       profile_deep_coverage_any
+    ;       profile_deep_coverage_branch_ite
+    ;       profile_deep_coverage_branch_switch
+    ;       profile_deep_coverage_branch_disj
+
+            % Tunables for the coverage profiling pass.
+    ;       profile_deep_coverage_use_portcounts
+    ;       profile_deep_coverage_use_trivial
 
     ;       use_zeroing_for_ho_cycles
     ;       use_lots_of_ho_specialization
@@ -1140,6 +1155,15 @@ option_defaults_2(compilation_model_opti
     profile_memory                      -   bool(no),
     profile_deep                        -   bool(no),
     use_activation_counts               -   bool(no),
+    coverage_profiling                  -   bool(no),
+    profile_deep_coverage_may_fail      -   bool(yes),
+    profile_deep_coverage_multi         -   bool(yes),
+    profile_deep_coverage_any           -   bool(yes),
+    profile_deep_coverage_branch_ite    -   bool(yes),
+    profile_deep_coverage_branch_switch -   bool(yes),
+    profile_deep_coverage_branch_disj   -   bool(yes),
+    profile_deep_coverage_use_portcounts -  bool(yes),
+    profile_deep_coverage_use_trivial   -   bool(yes),
     use_zeroing_for_ho_cycles           -   bool(yes),
     use_lots_of_ho_specialization       -   bool(no),
     deep_profile_tail_recursion         -   bool(no),
@@ -1957,6 +1981,24 @@ long_option("profile-time",         prof
 long_option("profile-memory",       profile_memory).
 long_option("profile-deep",         profile_deep).
 long_option("use-activation-counts",    use_activation_counts).
+long_option("coverage-profiling", 
+                    coverage_profiling).
+long_option("profile-deep-coverage-may-fail",
+                    profile_deep_coverage_may_fail).
+long_option("profile-deep-coverage-multi", 
+                    profile_deep_coverage_multi).
+long_option("profile-deep-coverage-any", 
+                    profile_deep_coverage_any).
+long_option("profile-deep-coverage-branch-ite",
+                    profile_deep_coverage_branch_ite).
+long_option("profile-deep-coverage-branch-switch",
+                    profile_deep_coverage_branch_switch).
+long_option("profile-deep-coverage-branch-disj",
+                    profile_deep_coverage_branch_disj).
+long_option("profile-deep-coverage-use-portcounts",
+                    profile_deep_coverage_use_portcounts).
+long_option("profile-deep-coverage-use-trivial",
+                    profile_deep_coverage_use_trivial).
 long_option("use-zeroing-for-ho-cycles",
                     use_zeroing_for_ho_cycles).
 long_option("use-lots-of-ho-specialization",
@@ -3878,6 +3920,36 @@ options_help_compilation_model -->
 %       "--profile-memory\t\t(grade modifier: `.profmem')",
 %       "\tSimilar to `--memory-profiling', except that it only",
 %       "\tgathers memory usage information, not call counts.",
+        
+        "--coverage-profiling",
+        "\tEnable coverage profiling, implies --deep-profiling (above).",
+
+%       "Switches to effect coverage profiling (part of deep profiling). ",
+%       "they enable different types of coverage points.",
+
+%       "--profile-deep-coverage-may-fail",
+%       "\tEnable coverage points after goals that may fail.",
+%       "--profile-deep-coverage-multi",
+%       "\tEnable coverage points after goals that may succeed more than ",
+%       "\tonce.",
+%       "--profile-deep-coverage-any",
+%       "\tEnable coverage points after goals that may succeed more than ",
+%       "\tonce or fail.",
+%       "--profile-deep-coverage-branch-if",
+%       "\tEnable coverage points at the beginning of if branches.",
+%       "--profile-deep-coverage-branch-switch",
+%       "\tEnable coverage points at the beginning of switch branches.",
+%       "--profile-deep-coverage-branch-disj",
+%       "\tEnable coverage points at the beginning of disjunction branches.",
+
+%       "Switches to tune the coverage profiling pass, useful for ",
+%       "debugging.",
+%       
+%       "--no-profile-deep-coverage-use-portcounts",
+%       "\tTurn off usage of port counts in the deep profilier to provide",
+%       "\tsome coverage information.",
+%       "--no-profile-deep-coverage-use-trivial",
+%       "\tTurn off usage of trivial goal information",
 
         "--record-term-sizes-as-words\t\t(grade modifier: `.tsw')",
         "\tAugment each heap cells with its size in words.",
Index: deep_profiler/dump.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/dump.m,v
retrieving revision 1.13
diff -u -p -r1.13 dump.m
--- deep_profiler/dump.m	17 Feb 2008 06:48:38 -0000	1.13
+++ deep_profiler/dump.m	29 Jul 2008 23:55:11 -0000
@@ -536,7 +536,8 @@ dump_proc_static(Restriction, Index, Pro
         )
     ->
         ProcStatic = proc_static(Id, DeclModule, RefinedId, RawId,
-            FileName, LineNumber, InInterface, Sites, IsZeroed),
+            FileName, LineNumber, InInterface, Sites, CoveragePoints, 
+            IsZeroed),
         IdStr = dump_proc_id(Id),
         io.format("ps%d:\n", [i(Index)], !IO),
         io.format("\tps_id\t\t= %s", [s(IdStr)], !IO),
@@ -572,6 +573,7 @@ dump_proc_static(Restriction, Index, Pro
         ),
         io.format("\t%s\n", [s(IsZeroStr)], !IO),
         array_foldl_from_0(dump_proc_static_call_sites, Sites, !IO),
+        array_foldl_from_0(dump_coverage_point, CoveragePoints, !IO),
         io.nl(!IO)
     ;
         true
@@ -584,6 +586,17 @@ dump_proc_static_call_sites(Slot, CSSPtr
     CSSPtr = call_site_static_ptr(CSSI),
     io.format("\tps_site[%d]: css%d\n", [i(Slot), i(CSSI)], !IO).
 
+
+:- pred dump_coverage_point(int::in, coverage_point::in, io::di, io::uo) 
+    is det.
+
+dump_coverage_point(Num, CoveragePoint, !IO) :-
+    CoveragePoint = coverage_point(Count, Path, Type),
+    goal_path_to_string(Path) = PathString,
+    io.format("\tcoverage_point[%d]: %s, %s: %d\n", 
+        [i(Num), s(string(Type)), s(PathString), i(Count)], !IO).
+
+
 %----------------------------------------------------------------------------%
 
 :- func dump_proc_id(string_proc_label) = string.
Index: deep_profiler/profile.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/profile.m,v
retrieving revision 1.18
diff -u -p -r1.18 profile.m
--- deep_profiler/profile.m	9 May 2008 10:59:59 -0000	1.18
+++ deep_profiler/profile.m	29 Jul 2008 23:55:11 -0000
@@ -162,15 +162,16 @@
 
 :- type proc_static
     --->    proc_static(
-                ps_id           :: string_proc_label, % procedure ID
-                ps_decl_module  :: string,      % declaring module
-                ps_refined_id   :: string,      % refined procedure id
-                ps_raw_id       :: string,      % raw procedure id
-                ps_file_name    :: string,      % file name of proc
-                ps_line_number  :: int,         % line number of proc
-                ps_in_interface :: bool,        % is in interface?
-                ps_sites        :: array(call_site_static_ptr),
-                ps_is_zeroed    :: is_zeroed
+                ps_id               :: string_proc_label, % procedure ID
+                ps_decl_module      :: string,      % declaring module
+                ps_refined_id       :: string,      % refined procedure id
+                ps_raw_id           :: string,      % raw procedure id
+                ps_file_name        :: string,      % file name of proc
+                ps_line_number      :: int,         % line number of proc
+                ps_in_interface     :: bool,        % is in interface?
+                ps_sites            :: array(call_site_static_ptr),
+                ps_coverage_points  :: array(coverage_point),
+                ps_is_zeroed        :: is_zeroed
             ).
 
 :- type call_site_dynamic
@@ -225,6 +226,23 @@
                 call_site_static_ptr
             ).
 
+    % This is similar to the coverage_point type in
+    % mdbcomp/program_representation.m, however it includes an integer count
+    % of how often execution reached this point in the program.
+    %
+:- type coverage_point
+    --->    coverage_point(
+                int,
+                    % The number of times execution reached this point,
+                goal_path,
+                    % Identifies the goal that this coverage point is near.  If
+                    % cp_type is cp_type_branch_arm the coverage point is
+                    % immediately before this goal, otherwise it is immediately
+                    % after.
+                cp_type
+                    % The type of this coverage point.
+            ).
+
 :- pred is_call_site_kind(int::in, call_site_kind::out) is semidet.
 
 %-----------------------------------------------------------------------------%
Index: deep_profiler/read_profile.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/read_profile.m,v
retrieving revision 1.22
diff -u -p -r1.22 read_profile.m
--- deep_profiler/read_profile.m	23 Nov 2007 07:35:52 -0000	1.22
+++ deep_profiler/read_profile.m	29 Jul 2008 23:55:11 -0000
@@ -31,6 +31,7 @@
 :- implementation.
 
 :- import_module array_util.
+:- import_module exception.
 :- import_module io_combinator.
 :- import_module measurements.
 :- import_module mdbcomp.
@@ -135,7 +136,7 @@ read_deep_id_string(Res, !IO) :-
 % This must the same string as the one written by MR_write_out_deep_id_string
 % in runtime/mercury_deep_profiling.c.
 
-deep_id_string = "Mercury deep profiler data version 4\n".
+deep_id_string = "Mercury deep profiler data version 5\n".
 
 :- func init_deep(int, int, int, int, int, int, int, int, int, int, int)
     = initial_deep.
@@ -167,7 +168,7 @@ init_deep(MaxCSD, MaxCSS, MaxPD, MaxPS, 
             )),
         array.init(MaxPS + 1,
             proc_static(dummy_proc_id, "", "", "", "", -1, no,
-                array([]), not_zeroed))
+                array([]), array([]), not_zeroed))
     ).
 
 :- pred read_nodes(initial_deep::in, maybe_error(initial_deep)::out,
@@ -290,45 +291,54 @@ read_proc_static(Res, !IO) :-
     trace [compile_time(flag("debug_read_profdeep")), io(!IO)] (
         io.write_string("reading proc_static.\n", !IO)
     ),
-    io_combinator.maybe_error_sequence_6(
+    io_combinator.maybe_error_sequence_7(
         read_ptr(ps),
         read_proc_id,
         read_string,
         read_num,
         read_deep_byte,
         read_num,
+        read_num,
         (pred(PSI0::in, Id0::in, F0::in, L0::in, I0::in,
-                N0::in, Stuff0::out) is det :-
-            Stuff0 = ok({PSI0, Id0, F0, L0, I0, N0})
+                NCS0::in, NCP0::in, Stuff0::out) is det :-
+            Stuff0 = ok({PSI0, Id0, F0, L0, I0, NCS0, NCP0})
         ),
         Res1, !IO),
     (
-        Res1 = ok({PSI, Id, FileName, LineNumber, Interface, N}),
-        read_n_things(N, read_ptr(css), Res2, !IO),
+        Res1 = ok({PSI, Id, FileName, LineNumber, Interface, NCS, NCP}),
+        read_n_things(NCS, read_ptr(css), Res2, !IO),
         (
             Res2 = ok(CSSIs),
-            CSSPtrs = list.map(make_cssptr, CSSIs),
-            DeclModule = decl_module(Id),
-            RefinedStr = refined_proc_id_to_string(Id),
-            RawStr = raw_proc_id_to_string(Id),
-            ( Interface = 0 ->
-                IsInInterface = no
+            read_n_things(NCP, read_coverage_point, Res3, !IO), 
+            (
+                Res3 = ok(CoveragePoints),
+                CSSPtrs = list.map(make_cssptr, CSSIs),
+                DeclModule = decl_module(Id),
+                RefinedStr = refined_proc_id_to_string(Id),
+                RawStr = raw_proc_id_to_string(Id),
+                ( Interface = 0 ->
+                    IsInInterface = no
+                ;
+                    IsInInterface = yes
+                ),
+                % The `not_zeroed' for whether the procedure's proc_static
+                % is ever zeroed is the default. The startup phase will set it
+                % to `zeroed' in the proc_statics which are ever zeroed.
+                ProcStatic = proc_static(Id, DeclModule,
+                    RefinedStr, RawStr, FileName, LineNumber,
+                    IsInInterface, array(CSSPtrs), array(CoveragePoints), 
+                    not_zeroed),
+                Res = ok2(ProcStatic, PSI),
+                trace [compile_time(flag("debug_read_profdeep")), io(!IO)] (
+                    io.write_string("read proc_static ", !IO),
+                    io.write_int(PSI, !IO),
+                    io.write_string(": ", !IO),
+                    io.write(ProcStatic, !IO),
+                    io.write_string("\n", !IO)
+                )
             ;
-                IsInInterface = yes
-            ),
-            % The `not_zeroed' for whether the procedure's proc_static
-            % is ever zeroed is the default. The startup phase will set it
-            % to `zeroed' in the proc_statics which are ever zeroed.
-            ProcStatic = proc_static(Id, DeclModule,
-                RefinedStr, RawStr, FileName, LineNumber,
-                IsInInterface, array(CSSPtrs), not_zeroed),
-            Res = ok2(ProcStatic, PSI),
-            trace [compile_time(flag("debug_read_profdeep")), io(!IO)] (
-                io.write_string("read proc_static ", !IO),
-                io.write_int(PSI, !IO),
-                io.write_string(": ", !IO),
-                io.write(ProcStatic, !IO),
-                io.write_string("\n", !IO)
+                Res3 = error(Err),
+                Res = error2(Err)
             )
         ;
             Res2 = error(Err),
@@ -402,6 +412,21 @@ read_proc_id_user_defined(PredOrFunc, Re
         ),
         Res, !IO).
 
+:- pred read_coverage_point(maybe_error(coverage_point)::out, io::di, io::uo) 
+    is det.
+
+read_coverage_point(Res, !IO) :-
+    io_combinator.maybe_error_sequence_3(
+        read_string,
+        read_cp_type,
+        read_num,
+        (pred(GoalPathString::in, CPType::in, CPCount::in, CP::out) is det :-
+            goal_path_from_string_det(GoalPathString, GoalPath),
+            CP = ok(coverage_point(CPCount, GoalPath, CPType))
+        ),
+        Res, !IO).
+
+
 :- func raw_proc_id_to_string(string_proc_label) = string.
 
 raw_proc_id_to_string(str_special_proc_label(TypeName, TypeModule, _DefModule,
@@ -973,6 +998,31 @@ read_ptr(_Kind, Res, !IO) :-
         io.write_string("\n", !IO)
     ).
 
+
+:- pred read_cp_type(maybe_error(cp_type)::out, io::di, io::uo) is det.
+
+read_cp_type(MaybeRes, !IO) :-
+    read_num(MaybeRes0, !IO),
+    (
+        MaybeRes0 = ok(Res0),
+        num_to_cp_type(Res0, Res),
+        MaybeRes = ok(Res)
+    ;
+        MaybeRes0 = error(Msg),
+        MaybeRes = error(Msg)
+    ).
+
+
+:- pred num_to_cp_type(int::in, cp_type::out) is det.
+
+:- pragma foreign_proc("C", num_to_cp_type(Int::in, CPType::out),
+    [will_not_call_mercury, thread_safe, promise_pure], "
+
+        CPType = Int;
+
+    ").
+
+
 :- pred read_num(maybe_error(int)::out, io::di, io::uo) is det.
 
 read_num(Res, !IO) :-
Index: doc/user_guide.texi
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/doc/user_guide.texi,v
retrieving revision 1.571
diff -u -p -r1.571 user_guide.texi
--- doc/user_guide.texi	29 Jul 2008 05:13:22 -0000	1.571
+++ doc/user_guide.texi	29 Jul 2008 23:55:13 -0000
@@ -6830,6 +6830,7 @@ A - argument passing information,
 B - mode constraint information,
 C - clause information,
 D - instmap deltas of goals,
+E - deep profiling information,
 G - compile-time garbage collection information,
 I - imported predicates,
 M - mode and inst information,
@@ -7541,6 +7542,70 @@ Enable deep profiling by inserting the a
 This option is only supported by the low-level C back-end.
 
 @ignore
+    Coverage profiling is experimental, some options below tune coverage
+    profiling however they are intended for developers.
+
+ at sp 1
+ at item @code{--coverage-profiling} (grades: any grade containing @samp{.profdeep})
+ at findex --coverage-profiling
+ at cindex Coverage Profiling
+Enable coverage profiling by inserting coverage points used to measure how
+execution moves through a procedure.  This option is only supported by the
+low-level C back-end.
+        
+ at sp 1
+
+Switches to effect coverage profiling (part of deep profiling).  they enable
+different types of coverage points.
+
+ at sp 1
+ at item @code{--profile-deep-coverage-may-fail}
+ at findex --profile-deep-coverage-may-fail
+Enable coverage points after goals that may fail.
+
+ at sp 1
+ at item @code{--profile-deep-coverage-multi}
+ at findex --profile-deep-coverage-multi
+Enable coverage points after goals that may succeed more than once.
+
+ at sp 1
+ at item @code{--profile-deep-coverage-any}
+ at findex --profile-deep-coverage-any
+Enable coverage points after goals that may succeed more than once or fail.
+
+ at sp 1
+ at item @code{--profile-deep-coverage-branch-if}
+ at findex --profile-deep-coverage-branch-if
+Enable coverage points at the beginning of if branches.
+
+ at sp 1
+ at item @code{--profile-deep-coverage-branch-switch}
+ at findex --profile-deep-coverage-branch-switch
+Enable coverage points at the beginning of switch branches.
+
+ at sp 1
+ at item @code{--profile-deep-coverage-branch-disj}
+ at findex --profile-deep-coverage-branch-disj
+Enable coverage points at the beginning of disjunction branches.
+
+ at sp 1
+Switches to tune the coverage profiling pass, useful for 
+debugging.
+
+ at sp 1
+ at item @code{--no-profile-deep-coverage-use-portcounts}
+ at findex --no-profile-deep-coverage-use-portcounts
+Turn off usage of port counts in the deep profilier to provide some coverage
+information.
+
+ at sp
+ at item @code{--no-profile-deep-coverage-use-trivial}
+ at findex --no-profile-deep-coverage-use-trivial
+Turn off usage of trivial goal information
+
+ at end ignore
+
+ at ignore
 	The following are basically useless, hence undocumented.
 
 @sp 1
Index: library/profiling_builtin.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/profiling_builtin.m,v
retrieving revision 1.20
diff -u -p -r1.20 profiling_builtin.m
--- library/profiling_builtin.m	31 May 2007 03:03:37 -0000	1.20
+++ library/profiling_builtin.m	29 Jul 2008 23:55:13 -0000
@@ -107,6 +107,8 @@
 
 :- impure pred reset_activation_info_sr(proc_dynamic::in) is det.
 
+:- impure pred increment_coverage_point_count(proc_layout::in, int::in) is det.
+
 :- type call_site_nums_2
     --->    call_site_nums_2(int, int).
 
@@ -803,6 +805,23 @@
 }").
 
 %---------------------------------------------------------------------------%
+% instance of increment_coverage_point_counto
+%---------------------------------------------------------------------------%
+
+:- pragma foreign_proc("C",
+    increment_coverage_point_count(_ProcLayout::in, _CPIndex::in),
+    [thread_safe, will_not_call_mercury],
+"{
+/*
+ * This builtin is only ever used when code is instrumented with an inline
+ * version,  from complier/deep_profiling.m
+ */
+MR_fatal_error(
+    ""increment_coverage_point_count: builtin cannot be called normally"");
+}").
+
+
+%---------------------------------------------------------------------------%
 % instances of save_recursion_depth_N
 %---------------------------------------------------------------------------%
 
Index: mdbcomp/program_representation.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/mdbcomp/program_representation.m,v
retrieving revision 1.31
diff -u -p -r1.31 program_representation.m
--- mdbcomp/program_representation.m	23 Jul 2008 23:20:34 -0000	1.31
+++ mdbcomp/program_representation.m	29 Jul 2008 23:55:13 -0000
@@ -495,6 +495,34 @@
 
 %-----------------------------------------------------------------------------%
 
+:- type coverage_point_info
+    --->    coverage_point_info(
+                goal_path,
+                    % Identifies the goal that this coverage point is near.  If
+                    % cp_type is cp_type_branch_arm the coverage point is
+                    % immediately before this goal, otherwise it is immediately
+                    % after.
+                cp_type
+                    % The type of this coverage point.
+            ).
+
+% This enumeration specifies the type of coverage point.  A branch arm is an
+% arm of an if-then-else, switch or disj goal, the type can be determined by
+% the goal_path above.
+:- type cp_type
+    --->    cp_type_solns_may_fail
+    ;       cp_type_solns_multi
+    ;       cp_type_solns_any
+    ;       cp_type_branch_arm.
+
+
+    % Gives the value in C for this coverage point type.
+    %
+:- pred coverage_point_type_c_value(cp_type::in, string::out) is det.
+
+
+%-----------------------------------------------------------------------------%
+
 :- implementation.
 
 :- import_module char.
@@ -1428,4 +1456,27 @@ pred_is_external("backjump", "builtin_ba
     }
 ").
 
+
+%-----------------------------------------------------------------------------%
+
+%
+% Please keep runtime/mercury_deep_profiling.h updated when modifing this
+% section.
+%
+
+coverage_point_type_c_value(cp_type_solns_may_fail,
+    "MR_cp_type_solns_may_fail").
+coverage_point_type_c_value(cp_type_solns_multi, "MR_cp_type_solns_multi").
+coverage_point_type_c_value(cp_type_solns_any, "MR_cp_type_solns_any").
+coverage_point_type_c_value(cp_type_branch_arm, "MR_cp_type_branch_arm").
+
+:- pragma foreign_enum("C", cp_type/0,
+    [
+        cp_type_solns_may_fail - "MR_cp_type_solns_may_fail",
+        cp_type_solns_multi    - "MR_cp_type_solns_multi",
+        cp_type_solns_any      - "MR_cp_type_solns_any",
+        cp_type_branch_arm     - "MR_cp_type_branch_arm"
+    ]).
+
+
 %-----------------------------------------------------------------------------%
Index: runtime/mercury_deep_profiling.c
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_deep_profiling.c,v
retrieving revision 1.29
diff -u -p -r1.29 mercury_deep_profiling.c
--- runtime/mercury_deep_profiling.c	23 Dec 2007 23:57:18 -0000	1.29
+++ runtime/mercury_deep_profiling.c	29 Jul 2008 23:55:14 -0000
@@ -287,6 +287,9 @@ typedef enum node_kind {
 #define MR_FIXED_SIZE_INT_BYTES 4
 
 static  void    MR_write_csd_ptr(FILE *fp, const MR_CallSiteDynamic *csd);
+static  void    MR_write_out_coverage_point(FILE *fp, 
+                    const MR_CoveragePointStatic *cp_static, 
+                    const MR_Unsigned *cp);
 static  void    MR_write_ptr(FILE *fp, MR_NodeKind kind, const int node_id);
 static  void    MR_write_kind(FILE *fp, MR_CallSiteKind kind);
 static  void    MR_write_byte(FILE *fp, const char byte);
@@ -682,7 +685,7 @@ static void
 MR_write_out_deep_id_string(FILE *fp)
 {
     /* Must be the same as deep_id_string in deep_profiler/read_profile.m */
-    const char  *id_string = "Mercury deep profiler data version 4\n";
+    const char  *id_string = "Mercury deep profiler data version 5\n";
 
     fputs(id_string, fp);
 }
@@ -897,7 +900,12 @@ MR_write_out_proc_static(FILE *deep_fp, 
     MR_write_num(deep_fp, ps->MR_ps_line_number);
     MR_write_byte(deep_fp, ps->MR_ps_is_in_interface);
     MR_write_num(deep_fp, ps->MR_ps_num_call_sites);
+    MR_write_num(deep_fp, ps->MR_ps_num_coverage_points);
 
+    /*
+    ** Write out pointers to Call Site Statics.  These are read in with the
+    ** proc static.
+    */
     for (i = 0; i < ps->MR_ps_num_call_sites; i++) {
         (void) MR_insert_call_site_static(&ps->MR_ps_call_sites[i], &css_id,
             NULL, MR_FALSE);
@@ -913,6 +921,30 @@ MR_write_out_proc_static(FILE *deep_fp, 
         MR_write_ptr(deep_fp, kind_css, css_id);
     }
 
+    /*
+    ** Write out coverage points.  This is read in as part of the proc static.
+    **/
+    /* TODO: Don't know if MR_Unsigned will work with MR_write_num() will work
+    ** on 64bit machines, depends on size of unsigned.
+    */
+    for (i = 0; i < ps->MR_ps_num_coverage_points; i++)
+    {
+#ifdef MR_DEEP_PROFILING_DEBUG
+        if (debug_fp != NULL) {
+            fprintf(debug_fp, "in proc_static %p/%p/%d, coverage point %d\n",
+                proc_layout, ps, ps_id, i);
+        }
+#endif
+        
+        MR_write_out_coverage_point(deep_fp, 
+            &ps->MR_ps_coverage_points_static[i], &ps->MR_ps_coverage_points[i]);
+    }
+    
+    
+    /*
+    ** Write out the actual call site statics,  These are read in after the
+    ** proc static, not as part of it.
+    */
     for (i = 0; i < ps->MR_ps_num_call_sites; i++) {
 #ifdef MR_DEEP_PROFILING_DEBUG
         if (debug_fp != NULL) {
@@ -1331,6 +1363,24 @@ MR_write_csd_ptr(FILE *fp, const MR_Call
     MR_write_ptr(fp, kind_csd, csd_id);
 }
 
+
+static void
+MR_write_out_coverage_point(FILE *fp, const MR_CoveragePointStatic *cp_static,
+    const MR_Unsigned *cp)
+{
+#ifdef  MR_DEEP_PROFILING_DETAIL_DEBUG
+    if (debug_fp != NULL) {
+        fprintf(debug_fp, "coverage point: %s,%d: %d\n", 
+            cp_static->MR_cp_goal_path, cp_static->MR_cp_type, *cp);
+    }
+#endif
+
+    MR_write_string(fp, cp_static->MR_cp_goal_path),
+    MR_write_num(fp, cp_static->MR_cp_type),
+    MR_write_num(fp, *cp);
+}
+
+
 static void
 MR_write_ptr(FILE *fp, MR_NodeKind kind, int node_id)
 {
Index: runtime/mercury_deep_profiling.h
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_deep_profiling.h,v
retrieving revision 1.18
diff -u -p -r1.18 mercury_deep_profiling.h
--- runtime/mercury_deep_profiling.h	12 Sep 2007 06:21:15 -0000	1.18
+++ runtime/mercury_deep_profiling.h	29 Jul 2008 23:55:14 -0000
@@ -55,8 +55,25 @@ struct MR_ProfilingMetrics_Struct {
 #endif
 };
 
+/*
+** The coverage point types.  Please update the enum and type within
+** mdbcomp/program_representation.m when updating this structure.
+*/
+typedef enum {
+	MR_cp_type_solns_may_fail,
+	MR_cp_type_solns_multi,
+	MR_cp_type_solns_any,
+	MR_cp_type_branch_arm
+} MR_CPType; 
+
+typedef struct {
+	const char				*MR_cp_goal_path;
+	const MR_CPType			MR_cp_type;
+} MR_CoveragePointStatic;
+
+
 struct MR_CallSiteStatic_Struct {
-    	MR_CallSiteKind				MR_css_kind;
+	MR_CallSiteKind				MR_css_kind;
 	MR_ProcLayout				*MR_css_callee_ptr_if_known;
 	MR_ConstString				MR_css_type_subst_if_known;
 	MR_ConstString				MR_css_file_name;
@@ -69,7 +86,7 @@ struct MR_ProcStatic_Struct {
 	int					MR_ps_line_number;
 	int					MR_ps_is_in_interface;
 	int					MR_ps_num_call_sites;
-	const MR_CallSiteStatic			*MR_ps_call_sites;
+	const MR_CallSiteStatic 		*MR_ps_call_sites;
 #ifdef MR_USE_ACTIVATION_COUNTS
 	int					MR_ps_activation_count;
 #endif
@@ -77,6 +94,21 @@ struct MR_ProcStatic_Struct {
 	int					MR_ps_cur_csd_stack_slot;
 	int					MR_ps_next_csd_stack_slot;
 	int					MR_ps_old_outermost_stack_slot;
+
+	/*
+	** The number of coverage points in a procedure and static information
+	** about them are fixed at compile time, so they are associated with
+	** proc statics rather than proc dynamics.
+	*/
+	const MR_Unsigned			MR_ps_num_coverage_points;
+	const MR_CoveragePointStatic * const	MR_ps_coverage_points_static;
+	
+	/*
+	** Coverage data is kept in the ProcStatic structure initially, at a
+	** later stage more fine-grained coverage idata may be associated with
+	** ProcDynamic if performance is not affected too much.
+	*/
+	MR_Unsigned * const			MR_ps_coverage_points;
 };
 
 struct MR_CallSiteDynamic_Struct {
-------------- 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/20080730/4891a868/attachment.sig>


More information about the reviews mailing list