[m-rev.] for post-commit review: goal ids

[Paul Bone]

On Mon, Dec 20, 2010 at 06:46:07PM +1100, Zoltan Somogyi wrote:
> For review by anyone. I don't particularly care whether it makes it to
> the release branch or not.
> 
> Zoltan.
> 
> The existing representation of goal_paths is suboptimal for several reasons.
> 
> - Sometimes we need forward goal paths (e.g. to look up goals), and sometimes
>   we need reverse goal paths (e.g. when computing goal paths in the first
>   place). We had two types for them, but
>   
>   - their names, goal_path and goal_path_consable, were not expressive, and
>   - we could store only one of them in goal_infos.
> 
> - Testing whether goal A is a subgoal of goal B is quite error-prone using
>   either form of goal paths.
> 
> - Using a goal path as a key in a map, which several compiler passes want to
>   do, requires lots of expensive comparisons.
> 
> This diff replaces most uses of goal paths with goal ids. A goal id is an
> integer, so it can be used as a key in faster maps, or even in arrays.
> Every goal in the body of a procedure gets its id allocated in a depth first
> search. Since we process each goal before we dive into is descendants,
> the goal representing the whole body of a procedure always gets goal id 0.
> The depth first traversal also builds up a map (the containing goal map)
> that tells us the parent goal of ever subgoal, with the obvious exception

    s/ever/every/

> of the root goal itself. From the containing goal map, one can compute
> both reverse and forward goal paths. It can also serve as the basis of an
> efficient test of whether the goal identified by goal id A is an ancestor
> of another goal identified by goal id B. We don't yet use this test,
> but I expect we will in the future.
> 
> mdbcomp/program_representation.m:
> 	Add the goal_id type.
> 
> 	Replace the existing goal_path and goal_path_consable types
> 	with two new types, forward_goal_path and reverse_goal_path.
> 	Since these now have wrappers around the list of goal path steps
> 	that identify each kind of goal path, it is now ok to expose their
> 	representations. This makes several compiler passes easier to code.
> 
> 	Update the set of operations on goal paths to work on the new data
> 	structures.
> 
> 	Add a couple of step types to represent lambdas and try goals.
> 	Their omission prior to this would have been a bug for constraint-based
> 	mode analysis, or any other compiler pass prior to the expansion out
> 	of lambda and try goals that wanted to use goal paths to identify
> 	subgoals.

ITYM
    ...expanding out...

> browser/declarative_tree.m:
> mdbcomp/rtti_access.m:
> mdbcomp/slice_and_dice.m:
> mdbcomp/trace_counts.m:
> slice/mcov.m:
> deep_profiler/*.m:
> 	Conform to the changes in goal path representation.
> 
> compiler/hlds_goal:
> 	Replace the goal_path field with a goal_id field in the goal_info,
> 	indicating that from now on, this should be used to identify goals.
> 
> 	Keep a reverse_goal_path field in the goal_info for use by RBMM and
> 	CTGC. Those analyses were too hard to convert to using goal_ids,
> 	especially since RBMM uses goal_paths to identify goals in multi-pass
> 	algorithms that should be one-pass and should not NEED to identify
> 	any goals for later processing.

This file and some others are missing their .m suffix.

> compiler/goal_path:
> 	Add predicates to fill in goal_ids, and update the predicates
> 	filling in the now deprecated reverse goal path fields.
> 
> 	Add the operations needed by the rest of the compiler
> 	on goal ids and containing goal maps.
> 
> 	Remove the option to set goal paths using "mode equivalent steps".
> 	Constraint based mode analysis now uses goal ids, and can now
> 	do its own equivalent optimization quite simply.
> 
> 	Move the goal_path module from the check_hlds package to the hlds
> 	package.
> 
> compiler/*.m:
> 	Conform to the changes in goal path representation.
> 
> 	Most modules now use goal_ids to identify goals, and use a containing
> 	goal map to convert the goal ids to goal paths when needed.
> 	However, the ctgc and rbmm modules still use (reverse) goal paths.
> 
> library/digraph.m:
> library/group.m:
> library/injection.m:
> library/pprint.m:
> library/pretty_printer.m:
> library/term_to_xml.m:
> 	Minor style improvements.

> Index: compiler/call_gen.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/compiler/call_gen.m,v
> retrieving revision 1.197
> diff -u -r1.197 call_gen.m
> --- compiler/call_gen.m	15 Dec 2010 06:29:29 -0000	1.197
> +++ compiler/call_gen.m	15 Dec 2010 06:33:13 -0000
> @@ -65,6 +65,7 @@
>  
>  :- import_module backend_libs.builtin_ops.
>  :- import_module hlds.arg_info.
> +:- import_module hlds.goal_path.
>  :- import_module hlds.hlds_llds.
>  :- import_module hlds.hlds_module.
>  :- import_module hlds.instmap.
> @@ -106,11 +107,20 @@
>      get_next_label(ReturnLabel, !CI),
>      call_gen.call_comment(!.CI, PredId, CodeModel, CallComment),
>      Context = goal_info_get_context(GoalInfo),
> -    GoalPath = goal_info_get_goal_path(GoalInfo),
> +    GoalId = goal_info_get_goal_id(GoalInfo),
> +    get_containing_goal_map(!.CI, MaybeContainingGoalMap),
> +    (
> +        MaybeContainingGoalMap = yes(ContainingGoalMap),
> +        GoalPath = goal_id_to_forward_path(ContainingGoalMap, GoalId),
> +        MaybeGoalPath = yes(GoalPath)
> +    ;
> +        MaybeContainingGoalMap = no,
> +        MaybeGoalPath = no
> +    ),
>      CallCode = from_list([
>          llds_instr(livevals(LiveVals), ""),
>          llds_instr(llcall(Address, code_label(ReturnLabel), ReturnLiveLvalues,
> -            Context, GoalPath, CallModel), CallComment),
> +            Context, MaybeGoalPath, CallModel), CallComment),
>          llds_instr(label(ReturnLabel), "continuation label")
>      ]),
>  
> @@ -132,7 +142,7 @@
>          goal_info_has_feature(GoalInfo, feature_debug_tail_rec_call),
>          MaybeTraceInfo = yes(TraceInfo)
>      ->
> -        generate_tailrec_event_code(TraceInfo, ArgsInfos, GoalPath, Context,
> +        generate_tailrec_event_code(TraceInfo, ArgsInfos, GoalId, Context,
>              TraceTailRecResetAndEventCode, TailRecLabel, !CI),
>          JumpCode = from_list([
>              llds_instr(livevals(LiveVals), ""),
> @@ -227,7 +237,7 @@
>      % Make the call.
>      get_next_label(ReturnLabel, !CI),
>      Context = goal_info_get_context(GoalInfo),
> -    GoalPath = goal_info_get_goal_path(GoalInfo),
> +    GoalId = goal_info_get_goal_id(GoalInfo),
>  
>      % Figure out what variables will be live at the return point, and where,
>      % for use in the accurate garbage collector, and in the debugger.
> @@ -239,10 +249,19 @@
>      handle_return(OutArgsInfos, GoalInfo, NonLiveOutputs,
>          ReturnInstMap, ReturnLiveLvalues, !CI),
>  
> +    get_containing_goal_map(!.CI, MaybeContainingGoalMap),
> +    (
> +        MaybeContainingGoalMap = yes(ContainingGoalMap),
> +        GoalPath = goal_id_to_forward_path(ContainingGoalMap, GoalId),
> +        MaybeGoalPath = yes(GoalPath)
> +    ;
> +        MaybeContainingGoalMap = no,
> +        MaybeGoalPath = no
> +    ),
>      CallCode = from_list([
>          llds_instr(livevals(LiveVals), ""),
>          llds_instr(llcall(CodeAddr, code_label(ReturnLabel), ReturnLiveLvalues,
> -            Context, GoalPath, CallModel), "Setup and call"),
> +            Context, MaybeGoalPath, CallModel), "Setup and call"),
>          llds_instr(label(ReturnLabel), "Continuation label")
>      ]),
>  

In what cases will !.CI not have a containing goal map?

Is it bad if llds_instr is not provided a goal path?

If so, how wasy is it to remove the maybe wrappers here and keep the code
deterministic?

>  
> -:- pred mode_equiv_step(goal_path_step::in) is semidet.
> +:- pred fill_conj_id_slots(slot_info::in, goal_id::in, int::in,
> +    int::in, int::out, containing_goal_map::in, containing_goal_map::out,
> +    list(hlds_goal)::in, list(hlds_goal)::out) is det.
>  
> -mode_equiv_step(Step) :-
> -    ( Step = step_disj(_)
> -    ; Step = step_neg
> -    ; Step = step_scope(_)
> -    ; Step = step_ite_else
> -    ).
> +fill_conj_id_slots(_, _, _, !GoalNum, !ContainingGoalMap, [], []).
> +fill_conj_id_slots(SlotInfo, GoalId, N0, !GoalNum, !ContainingGoalMap,
> +        [Goal0 | Goals0], [Goal | Goals]) :-
> +    N1 = N0 + 1,
> +    ContainingGoal = containing_goal(GoalId, step_conj(N1)),
> +    fill_goal_id_slots(SlotInfo, ContainingGoal, !GoalNum, !ContainingGoalMap,
> +        Goal0, Goal),
> +    fill_conj_id_slots(SlotInfo, GoalId, N1, !GoalNum, !ContainingGoalMap,
> +        Goals0, Goals).
> +

Is it clearer to make the step step_conj(N0) rather than N1, and call this
predicate with 1 for the parameter N0?

This could just be a subjective thing.

> Index: compiler/proc_gen.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/compiler/proc_gen.m,v
> retrieving revision 1.40
> diff -u -r1.40 proc_gen.m
> --- compiler/proc_gen.m	15 Dec 2010 06:29:56 -0000	1.40
> +++ compiler/proc_gen.m	15 Dec 2010 06:33:23 -0000
> @@ -300,11 +301,23 @@
>  %---------------------------------------------------------------------------%
>  
>  generate_proc_code(PredInfo, ProcInfo0, PredId, ProcId, ModuleInfo0,
> -        !GlobalData, Proc) :-
> +        !GlobalData, CProc) :-
>      % The modified module_info and proc_info are both discarded
>      % on return from generate_proc_code.
>      maybe_set_trace_level(PredInfo, ModuleInfo0, ModuleInfo),
> -    ensure_all_headvars_are_named(ProcInfo0, ProcInfo),
> +    ensure_all_headvars_are_named(ProcInfo0, ProcInfo1),
> +
> +    % We use the globals from the original module info, so that
> +    module_info_get_globals(ModuleInfo0, Globals0),
> +    globals.get_trace_level(Globals0, TraceLevel0),
> +    ( given_trace_level_is_none(TraceLevel0) = no ->
> +        fill_goal_id_slots_in_proc(ModuleInfo, ContainingGoalMap,
> +            ProcInfo1, ProcInfo),
> +        MaybeContainingGoalMap = yes(ContainingGoalMap)
> +    ;
> +        MaybeContainingGoalMap = no,
> +        ProcInfo = ProcInfo1
> +    ),

The comment above trails off.

> Index: compiler/smm_common.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/compiler/smm_common.m,v
> retrieving revision 1.6
> diff -u -r1.6 smm_common.m
> --- compiler/smm_common.m	4 Sep 2008 11:41:01 -0000	1.6
> +++ compiler/smm_common.m	9 Dec 2010 05:19:28 -0000
>  %
> -% Definition of a program point
> +% Definition of a program point.
>  %
> -    
> -    % A program point records the place at which a data structure possibly
> -    % becomes garbage. 
> -    %
> -:- type program_point 
> -    ---> 	pp( 
> -                pp_context	:: term.context, 
> -                pp_path		:: goal_path
> +
> +    % A program point identifies a place at which a data structure possibly
> +    % becomes garbage.
> +    %
> +:- type program_point
> +    --->    pp(
> +                pp_context  :: term.context,
> +                pp_id       :: reverse_goal_path
>              ).

Shound the field name still be pp_path if this is a goal path rather
than a goal id?

> Index: deep_profiler/coverage.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/coverage.m,v
> retrieving revision 1.10
> diff -u -r1.10 coverage.m
> --- deep_profiler/coverage.m	15 Dec 2010 06:30:33 -0000	1.10
> +++ deep_profiler/coverage.m	17 Dec 2010 02:41:26 -0000
> @@ -431,19 +440,20 @@
>      % conjunction.  Each goal also has it's own coverage.
>      %
>  :- pred conj_annotate_coverage_2(coverage_reference_info::in,
> -    goal_path::in, int::in, coverage_before::in, coverage_after::out,
> +    list(goal_path_step)::in, int::in,
> +    coverage_before::in, coverage_after::out,
>      list(goal_rep(unit))::in, list(goal_rep(coverage_info))::out) is det.
>  

We shoult make the list of goal path steps here an actual goal_path
type since this type is no-longer abstract.  This is also true for a
number of places below.

> Index: deep_profiler/display_report.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/display_report.m,v
> retrieving revision 1.32
> diff -u -r1.32 display_report.m
> --- deep_profiler/display_report.m	15 Dec 2010 06:30:33 -0000	1.32
> +++ deep_profiler/display_report.m	17 Dec 2010 03:03:39 -0000
> @@ -2212,8 +2212,8 @@
>  :- pred format_coverage_point_row(coverage_point::in, table_row::out) is det.
>  
>  format_coverage_point_row(CoveragePoint, Row) :-
> -    CoveragePoint = coverage_point(Count, GoalPath, CPType),
> -    GoalPathString = goal_path_to_string(GoalPath),
> +    CoveragePoint = coverage_point(Count, RevGoalPath, CPType),
> +    GoalPathString = rev_goal_path_to_string(RevGoalPath),
>      GoalPathCell = table_cell(td_s(GoalPathString)),
>      TypeCell = table_cell(td_s(string(CPType))),
>      CountCell = table_cell(td_i(Count)),
> @@ -4272,10 +4272,10 @@
>      CallSiteDesc = call_site_desc(CSSPtr, _ContainerPSPtr,
>          _FileName, _LineNumber, _ModuleName,
>          _UnQualRefinedName, _QualRefinedName,
> -        SlotNumber, GoalPath, _MaybeCallee),
> +        SlotNumber, RevGoalPath, _MaybeCallee),
>      RefinedName = call_site_desc_get_caller_refined_id(MaybeCurModuleName,
>          ModuleQual, CallSiteDesc),
> -    GoalPathStr = goal_path_to_string(GoalPath),
> +    GoalPathStr = rev_goal_path_to_string(RevGoalPath),
>      string.format("%s @ %s #%d",
>          [s(RefinedName), s(GoalPathStr), i(SlotNumber)], Name),
>      Cmd = deep_cmd_dump_call_site_static(CSSPtr),

For printing reports we should probably print goal paths in forward
order.  That is the path from the root to the goal in question.

> Index: deep_profiler/dump.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/dump.m,v
> retrieving revision 1.20
> diff -u -r1.20 dump.m
> --- deep_profiler/dump.m	15 Dec 2010 06:30:33 -0000	1.20
> +++ deep_profiler/dump.m	17 Dec 2010 02:42:32 -0000
> @@ -620,8 +620,8 @@
>  
>  :- pred format_cp_info(int::in, coverage_point_info::in, string::out) is det.
>  
> -format_cp_info(Num, coverage_point_info(Path, CPType), String) :-
> -    goal_path_to_string(Path) = PathString,
> +format_cp_info(Num, coverage_point_info(RevPath, CPType), String) :-
> +    rev_goal_path_to_string(RevPath) = PathString,
>      format("coverage_point[%d]: %s, %s",
>          [i(Num), s(string(CPType)), s(PathString)], String).

As above.

> Index: deep_profiler/mdprof_fb.automatic_parallelism.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/mdprof_fb.automatic_parallelism.m,v
> retrieving revision 1.22
> diff -u -r1.22 mdprof_fb.automatic_parallelism.m
> --- deep_profiler/mdprof_fb.automatic_parallelism.m	15 Dec 2010 06:30:33 -0000	1.22
> +++ deep_profiler/mdprof_fb.automatic_parallelism.m	17 Dec 2010 04:04:22 -0000
> @@ -480,10 +481,12 @@
>      Length = list.foldl((func(seq_conj(ConjsI), Acc) = Acc + length(ConjsI)),
>          Conj ^ cpc_conjs, 0),
>      (
> -        GoalPath \= ConjGoalPath,
> -        goal_path_inside(ConjGoalPath, GoalPath, RelativePath),
> -        goal_path_consable(RelativePath, RelativePathCons),
> -        goal_path_consable_remove_first(RelativePathCons, Step, _),
> +        % XXX zs: I am not confident of the update for goal path
> +        % representations.
> +        RevGoalPath \= RevConjGoalPath,
> +        rev_goal_path_inside(RevConjGoalPath, RevGoalPath, RevRelativePath),
> +        RevRelativePath = rgp(RevRelativePathSteps),
> +        list.last(RevRelativePathSteps, Step),
>          Step = step_conj(ConjNum),
>          ConjNum > FirstConjunct,
>          ConjNum =< FirstConjunct + Length

This is correct.  The XXX can be removed.

Everything else is fine, Thanks.


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