[m-rev.] Constraint-based typechecking
Paul Bone
pbone at csse.unimelb.edu.au
Wed Feb 18 13:04:58 AEDT 2009
On Tue, Feb 17, 2009 at 03:57:59PM +1100, Andrew Wesley Ebert wrote:
> Estimated hours taken: 300
> Branches: main
>
> Created a constraint-based typechecker. The typechecker works by generating
> a collection of constraints on the types of variables in each clause of the
> program, then solving these constraints using propagation. Information on the
> types of local variables (clauses_info^clauses_vartypes) and the IDs of
> predicate calls (hlds_goal_expr^call_pred_id) is passed back into the HLDS.
>
> In the event that the program being compiled is not type-correct, the
> typechecker will generate an error message describing the error. If the
> constraints on a variable cannot fully determine a type, the typechecker will
> report each possible type the variable could take. If the constraints on the
> type of a variable are unatisfiable, the compiler will report each minimal
> unsatisfiable subset of the constraints, pointing out the likely location(s)
> of the error.
>
> The constraint-based typechecker can handle ambiguous predicate calls and
> functor unifications much more efficiently than the old typechecker. However,
> it cannot handle anything related to existentially qualified variables,
> typeclass constraints and typeclass methods. The detail and clarity of error
> reporting is also rather poor.
>
> These changes have not yet been comprehensively debugged, although it
> should work in most cases, given the exceptions detailed above.
>
> To use the constraint-based typechecker instead of the original typechecker,
> enable the option --type-check-constraints when compiling your program.
>
> compiler/type_constraints.m:
> Built from scratch.
>
> compiler/mercury_compile.m:
> Imported the constraint-based typechecker.
> Enabled constraint-based typechecking if the --type-check-constraints
> option is set.
>
> compiler/options.m:
> Added the --type-check-constraints option.
>
> library/list.m:
> Added a list.filter_map_foldl predicate.
> Added a list.zip_single predicate.
>
> library/set.m:
> Added a predicate version of set.filter_map.
>
> library/maybe.m:
> Added a predicate maybe.remove_maybe to semideterministically strip the
> "yes" off of a maybe expression.
>
Hi Andrew.
I made this crash.
I have a predicate that the current typechecker 'gives up' on. It
should be possible to infer all the types in it however. I tried your
typechecker to see if it would work, but it crashed by throwing an
exception. To reporoduce this error checkout a CVS compiler and apply
the attached patched. When compiling it, it should fail to typecheck
mdprof_feedback.m in the deep_profiler directory. Then use your
compiler with the new typechecking code as follows:
pbone at taura:/home/taura/workspaces/pbone/implicit_parallelism/deep_profiler$
../compiler/mercury_compile --compile-to-c --grade asm_fast.gc \
--mercury-linkage static --flags DEEP_FLAGS --no-warn-unused-imports \
--type-check-constraints mdprof_feedback
Uncaught Mercury exception:
Software Error: list.map_corresponding/4: mismatched list arguments.
Stack dump not available in this grade.
Thanks.
-------------- next part --------------
Index: deep_profiler/mdprof_feedback.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/mdprof_feedback.m,v
retrieving revision 1.15
diff -u -p -b -r1.15 mdprof_feedback.m
--- deep_profiler/mdprof_feedback.m 30 Jan 2009 03:51:44 -0000 1.15
+++ deep_profiler/mdprof_feedback.m 18 Feb 2009 01:50:43 -0000
@@ -55,6 +55,7 @@
:- import_module list.
:- import_module map.
:- import_module maybe.
+:- import_module multi_map.
:- import_module pair.
:- import_module pqueue.
:- import_module require.
@@ -187,8 +188,8 @@ help_message =
The cost of maintaining a lock for a single dependant variable
in a conjunction, measured in the profiler's call sequence
counts.
- --implicit-parallelism-proc-cost-threshold <value>
- The cost threshold for procedures to be considered for implicit
+ --implicit-parallelism-clique-cost-threshold <value>
+ The cost threshold for cliques to be considered for implicit
parallelism, measured on the profiler's call sequence counts.
--implicit-parallelism-call-site-cost-threshold <value>
The cost of a call site to be considered for parallelism
@@ -280,7 +281,7 @@ read_deep_file(Input, Verbose, MaybeDeep
; desired_parallelism
; implicit_parallelism_sparking_cost
; implicit_parallelism_locking_cost
- ; implicit_parallelism_proc_cost_threshold
+ ; implicit_parallelism_clique_cost_threshold
; implicit_parallelism_call_site_cost_threshold.
% TODO: Introduce an option to disable parallelisation of dependant
@@ -314,8 +315,8 @@ long("implicit-parallelism",
long("desired-parallelism", desired_parallelism).
long("implicit-parallelism-sparking-cost", implicit_parallelism_sparking_cost).
long("implicit-parallelism-locking-cost", implicit_parallelism_locking_cost).
-long("implicit-parallelism-proc-cost-threshold",
- implicit_parallelism_proc_cost_threshold).
+long("implicit-parallelism-clique-cost-threshold",
+ implicit_parallelism_clique_cost_threshold).
long("implicit-parallelism-call-site-cost-threshold",
implicit_parallelism_call_site_cost_threshold).
@@ -338,7 +339,7 @@ defaults(desired_parallelism,
% be tested for.
defaults(implicit_parallelism_sparking_cost, int(100)).
defaults(implicit_parallelism_locking_cost, int(100)).
-defaults(implicit_parallelism_proc_cost_threshold, int(100000)).
+defaults(implicit_parallelism_clique_cost_threshold, int(100000)).
defaults(implicit_parallelism_call_site_cost_threshold, int(50000)).
:- pred construct_measure(string::in, stat_measure::out) is semidet.
@@ -369,7 +370,7 @@ construct_measure("median", stat_med
cpc_desired_parallelism :: float,
cpc_sparking_cost :: int,
cpc_locking_cost :: int,
- cpc_proc_threshold :: int,
+ cpc_clique_threshold :: int,
cpc_call_site_threshold :: int
).
@@ -411,7 +412,9 @@ check_options(Options0, RequestedFeedbac
error("Invalid value for calls_above_threshold_sorted_measure: " ++
Measure)
),
- lookup_int_option(Options, implicit_parallelism_proc_cost_threshold,
+ % Clique costs are used here. They are almost equivilent to procedure
+ % costs.
+ lookup_int_option(Options, implicit_parallelism_clique_cost_threshold,
CATSThreshold),
CallsAboveThresholdSortedOpts =
calls_above_threshold_sorted_opts(MeasureType, CATSThreshold),
@@ -439,7 +442,7 @@ check_options(Options0, RequestedFeedbac
SparkingCost),
lookup_int_option(Options, implicit_parallelism_locking_cost,
LockingCost),
- lookup_int_option(Options, implicit_parallelism_proc_cost_threshold,
+ lookup_int_option(Options, implicit_parallelism_clique_cost_threshold,
CPCProcThreshold),
lookup_int_option(Options,
implicit_parallelism_call_site_cost_threshold,
@@ -566,42 +569,22 @@ append_warning(StringProcLabel, MaybeGoa
candidate_parallel_conjunctions(Opts, Deep, Warnings, !Feedback) :-
Opts = candidate_parallel_conjunctions_opts(DesiredParallelism,
- SparkingCost, LockingCost, ProcThreshold, _CallSiteThreshold),
- % First retrieve the top procedures above the configured threshold.
- % This is done 'overall' not 'per_call' because parallelising a procedure
- % that is used a lot is more beneficial than parallelising a procedure that
- % is used once when the more-frequently used function accounts for a higher
- % amount of the programs runtime. It may be disqualified later if per call
- % it has very little benefit.
- % TODO: don't bother using the 'create_report' interface to get this
- % report, we should call it directly instead.
- TopProcsCmd = deep_cmd_top_procs(threshold_value(float(ProcThreshold)),
- cost_callseqs, self_and_desc, overall),
- create_report(TopProcsCmd, Deep, TopProcsReport),
- ( TopProcsReport = report_top_procs(MaybeTopProcsReport) ->
- (
- MaybeTopProcsReport = ok(TopProcs),
- TopProcsList = TopProcs ^ tp_top_procs
- ;
- MaybeTopProcsReport = error(TopProcsReportError),
- error(TopProcsReportError)
- )
- ;
- error("create_report gave incorrect report, expected top_procs_report")
- ),
-
- % Take the top procs list and look for conjunctions that can be
- % parallelised and give an estimated speedup when parallelised. There may
- % be more than one opportunity for parallelism in any given procedure.
- candidate_parallel_conjunctions_procs(Opts, Deep, TopProcsList,
- [], Conjunctions, cord.empty, Warnings),
+ SparkingCost, LockingCost, _CliqueThreshold, _CallSiteThreshold),
- % XXX: Analysing the clique tree to reduce the amount of nested parallel
- % execution should be done here.
+ % Find opertunities for parallelism by walking the clique tree. Don't
+ % Descened into cliques cheaper than the threshold.
+ deep_lookup_clique_index(Deep, Deep ^ root, RootCliquePtr),
+ TotalCallseqs = Deep ^ profile_stats ^ num_callseqs,
+ % The +1 here accounts for the cost of the pseudo call into the mercury
+ % runtime.
+ RootCliqueCost = cost_info(1, TotalCallseqs + 1),
+ candidate_parallel_conjunctions_clique(Opts, Deep, RootCliqueCost,
+ RootCliquePtr, ConjunctionsMultiMap, Warnings),
+ multi_map.to_flat_assoc_list(ConjunctionsMultiMap, ConjunctionsAssocList),
CandidateParallelConjunctions =
feedback_data_candidate_parallel_conjunctions(DesiredParallelism,
- SparkingCost, LockingCost, Conjunctions),
+ SparkingCost, LockingCost, ConjunctionsAssocList),
put_feedback_data(CandidateParallelConjunctions, !Feedback).
:- type implicit_parallelism_info
@@ -613,12 +596,222 @@ candidate_parallel_conjunctions(Opts, De
ipi_var_table :: var_table
).
+:- type cost_info
+ ---> cost_info(
+ cci_calls :: int,
+ cci_callseqs_total :: int
+ ).
+
+:- type candidate_par_conjunctions ==
+ multi_map(string_proc_label, candidate_par_conjunction).
+
+:- pred candidate_parallel_conjunctions_clique(
+ candidate_parallel_conjunctions_opts::in, deep::in, cost_info::in,
+ clique_ptr::in, candidate_par_conjunctions::out, cord(warning)::out)
+ is det.
+
+candidate_parallel_conjunctions_clique(Opts, Deep, ParentCostInfo, CliquePtr,
+ Candidates, Warnings) :-
+ create_clique_report(Deep, CliquePtr, MaybeCliqueReport),
+ (
+ MaybeCliqueReport = ok(CliqueReport),
+ CliqueProcs = CliqueReport ^ cr_clique_procs,
+ % All cliques must contain at least one procedure.
+ ( [ FirstCliqueProcPrime ] = CliqueProcs ->
+ FirstCliqueProc = FirstCliqueProcPrime
+ ;
+ error(this_file ++ "A clique must have et least one procedure")
+ ),
+ CliqueIsRecursive = is_clique_recursive(CliqueReport),
+ (
+ CliqueIsRecursive = clique_is_recursive,
+ % The clique is entered via the first procedure in the list.
+ candidate_parallel_conjunctions_recursive_clique_proc(Opts, Deep,
+ ParentCostInfo, FirstCliqueProc, Candidates, Warnings)
+% list.map2(candidate_parallel_conjunctions_clique_proc(Opts, Deep),
+% CliqueProcs, CandidatesList, WarningsList),
+% list.condense(CandidatesList, Candidates),
+% Warnings = cord_list_to_cord(WarningsList)
+ ;
+ CliqueIsRecursive = clique_is_not_recursive,
+ candidate_parallel_conjunctions_clique_proc(Opts, Deep,
+ ParentCostInfo, set.init, CliquePtr, FirstCliqueProc,
+ Candidates, Warnings)
+ )
+ ;
+ MaybeCliqueReport = error(Error),
+ error(this_file ++ Error)
+ ).
+
+:- type clique_is_recursive
+ ---> clique_is_recursive
+ ; clique_is_not_recursive.
+
+:- func is_clique_recursive(clique_report) = clique_is_recursive.
+
+is_clique_recursive(CliqueReport) = CliqueIsRecursive :-
+ CliqueProcs = CliqueReport ^ cr_clique_procs,
+ ( CliqueProcs = [_, _ | _] ->
+ % If there is more than one procedure then the clique must be mutually
+ % recursive. This computation is trivial compared to the case below.
+ CliqueIsRecursive = clique_is_recursive
+ ; CliqueProcs = [CliqueProc] ->
+ % Look for a self recursion in the single clique procedure.
+ CliquePtr = CliqueReport ^ cr_clique_ptr,
+ (
+ % If at least one call site within the clique's proc makes a call
+ % to this same clique then this is a recursive clique - this also
+ % covers higher-order calls.
+ some [CliqueProcDyanmic, CallSite, CalleePerf]
+ (
+ (
+ CliqueProcDynamic = CliqueProc ^ cpr_first_proc_dynamic
+ ;
+ member(CliqueProcDynamic,
+ CliqueProc ^ cpr_other_proc_dynamics)
+ ),
+ member(CallSite, CliqueProcDynamic ^ cpdr_call_sites),
+ member(CalleePerf, CallSite ^ ccsr_callee_perfs),
+ CliquePtr = CalleePerf ^ perf_row_subject ^ cdesc_clique_ptr
+ )
+ ->
+ CliqueIsRecursive = clique_is_recursive
+ ;
+ CliqueIsRecursive = clique_is_not_recursive
+ )
+ ;
+ error(this_file ++ "Clique must have at least one procedure")
+ ).
+
+:- pred candidate_parallel_conjunctions_clique_proc(
+ candidate_parallel_conjunctions_opts::in, deep::in, cost_info::in,
+ set(proc_desc)::in, clique_ptr::in, clique_proc_report::in,
+ candidate_par_conjunctions::out, cord(warning)::out) is det.
+
+candidate_parallel_conjunctions_clique_proc(Opts, Deep, _ParentCostInfo,
+ ProcsAnalysed, CliquePtr, CliqueProc, Candidates, Warnings) :-
+ Summary = CliqueProc ^ cpr_proc_summary,
+ MaybeTotal = Summary ^ perf_row_maybe_total,
+ (
+ MaybeTotal = yes(Total),
+ TotalCost = Total ^ perf_row_callseqs
+ ;
+ MaybeTotal = no,
+ error(this_file ++
+ "Could not retrive total callseqs cost from clique proc")
+ ),
+ % Use the total cost of a procedure in a clique to decide whether we should
+ % stop recursing the call graph at this point. If the procedure does not
+ % contribute to the runtime of the program in an absolote way then do not
+ % recurse further.
+ ( TotalCost < Opts ^ cpc_clique_threshold ->
+ Candidates = multi_map.init,
+ Warnings = cord.empty
+ ;
+ % Analyse this procedure for parallelism opertunities.
+ candidate_parallel_conjunctions_proc(Opts, Deep, Summary,
+ ProcCandidates, ProcWarnings),
+ % Analyse child cliques of this clique proc for parallelism
+ % opertunities. Recursive calls point to this same clique, in these
+ % cases call candidate_parallel_conjunctions_clique_proc on the
+ % procedure within this clique that they call.
+ AllProcDynamics = [CliqueProc ^ cpr_first_proc_dynamic |
+ CliqueProc ^ cpr_other_proc_dynamics],
+ list.map((pred(ProcDynamic::in, CliquePerfsI::out) is det :-
+ CallSiteReports = ProcDynamic ^ cpdr_call_sites,
+ list.map(
+ (pred(CallSiteReport::in, CliquePerfsII::out) is det :-
+ CliquePerfsII = CallSiteReport ^ ccsr_callee_perfs
+ ), CallSiteReports, CliquePerfsI0),
+ list.condense(CliquePerfsI0, CliquePerfsI)
+ ), AllProcDynamics, CliquePerfs0),
+ list.condense(CliquePerfs0, CliquePerfs),
+ list.map2(candidate_parallel_conjunctions_sub_clique(Opts, Deep,
+ ProcsAnalysed, map.init, CliquePtr),
+ CliquePerfs, SCCandidatesL, SCWarnings),
+ list.foldl(merge, SCCandidatesL,
+ multi_map.init, SCCandidates),
+ Candidates = map.merge(ProcCandidates, SCCandidates),
+ Warnings = ProcWarnings ++ cord_list_to_cord(SCWarnings)
+ ).
+
+:- pred candidate_parallel_conjunctions_sub_clique(
+ candidate_parallel_conjunctions_opts::in, deep::in, set(proc_desc)::in,
+ map(proc_desc, clique_proc_report)::in, clique_ptr::in,
+ perf_row_data(clique_desc)::in, candidate_par_conjunctions::out,
+ cord(warning)::out) is det.
+
+candidate_parallel_conjunctions_sub_clique(Opts, Deep, ProcsAnalysed0,
+ CliqueProcReportMap, ParentCliquePtr, CliquePerf,
+ Candidates, Warnings) :-
+ CliqueDesc = CliquePerf ^ perf_row_subject,
+ CliquePtr = CliqueDesc ^ cdesc_clique_ptr,
+ CliqueEntryProc = CliqueDesc ^ cdesc_entry_member,
+ MaybePerfTotal = CliquePerf ^ perf_row_maybe_total,
+ (
+ MaybePerfTotal = yes(PerfTotal)
+ ;
+ MaybePerfTotal = no,
+ error(this_file ++
+ "Could not retrive total callseqs cost from clique")
+ ),
+ CliqueCost = PerfTotal ^ perf_row_callseqs,
+ Calls = CliquePerf ^ perf_row_calls,
+ CostInfo = cost_info(Calls, CliqueCost),
+ ( ParentCliquePtr = CliquePtr ->
+ % This is a recursive call within the same clique.
+ ( member(CliqueEntryProc, ProcsAnalysed0) ->
+ % If we've analysed this clique in this proc already then don't do
+ % it again.
+ Candidates = multi_map.init,
+ Warnings = cord.empty
+ ;
+ map.lookup(CliqueProcReportMap, CliqueEntryProc, CliqueProcReport),
+ ProcsAnalysed = set.insert(ProcsAnalysed0, CliqueEntryProc),
+ candidate_parallel_conjunctions_clique_proc(Opts, Deep,
+ CostInfo, ProcsAnalysed, ParentCliquePtr, CliqueProcReport,
+ Candidates, Warnings)
+ )
+ ;
+ ( CliqueCost > Opts ^ cpc_clique_threshold ->
+ candidate_parallel_conjunctions_clique(Opts, Deep, CostInfo,
+ CliquePtr, Candidates, Warnings)
+ ;
+ Candidates = multi_map.init,
+ Warnings = cord.empty
+ )
+ ).
+
+:- pred candidate_parallel_conjunctions_recursive_clique_proc(
+ candidate_parallel_conjunctions_opts::in, deep::in, cost_info::in,
+ clique_proc_report::in, candidate_par_conjunctions::out,
+ cord(warning)::out) is det.
+
+candidate_parallel_conjunctions_recursive_clique_proc(_Opts, _Deep,
+ _ParentCostInfo, _CliqueProc, Candidates, Warnings) :-
+% MaybeTotal = CliqueProc ^ cpr_proc_summary ^ perf_row_maybe_total,
+% (
+% MaybeTotal = yes(Total)
+% ;
+% MaybeTotal = no,
+% error(this_file ++
+% "Could not retrive total callseqs cost from clique proc")
+% ),
+
+% ( Total ^ perf_row_callseqs >
+
+ Candidates = multi_map.init,
+ Warnings = cord.empty.
+
+
+%----------------------------------------------------------------------------%
+
:- pred candidate_parallel_conjunctions_procs(
candidate_parallel_conjunctions_opts::in, deep::in,
list(perf_row_data(proc_desc))::in,
- assoc_list(string_proc_label, candidate_par_conjunction)::in,
- assoc_list(string_proc_label, candidate_par_conjunction)::out,
+ candidate_par_conjunctions::in, candidate_par_conjunctions::out,
cord(warning)::in, cord(warning)::out) is det.
+:- pragma obsolete(candidate_parallel_conjunctions_procs/7).
candidate_parallel_conjunctions_procs(_, _, [], !Candidates, !Warnings).
candidate_parallel_conjunctions_procs(Opts, Deep, [PrefRowData | PrefRowDatas],
@@ -627,7 +820,7 @@ candidate_parallel_conjunctions_procs(Op
Warnings),
% This partially reverses the list of candidates, but order shouldn't be
% important.
- !:Candidates = Candidates ++ !.Candidates,
+ !:Candidates = multi_map.merge(Candidates, !.Candidates),
!:Warnings = !.Warnings ++ Warnings,
candidate_parallel_conjunctions_procs(Opts, Deep, PrefRowDatas,
!Candidates, !Warnings).
@@ -637,7 +830,7 @@ candidate_parallel_conjunctions_procs(Op
:- pred candidate_parallel_conjunctions_proc(
candidate_parallel_conjunctions_opts::in, deep::in,
perf_row_data(proc_desc)::in,
- assoc_list(string_proc_label, candidate_par_conjunction)::out,
+ candidate_par_conjunctions::out,
cord(warning)::out) is det.
candidate_parallel_conjunctions_proc(Opts, Deep, PrefRowData, Candidates,
@@ -681,13 +874,13 @@ candidate_parallel_conjunctions_proc(Opt
goal_get_conjunctions_worth_parallelising(Goal, empty_goal_path, Info,
ProcLabel, Candidates0, _, _,
Warnings, initial_inst_map(ProcDefnRep), _),
- list.map((pred(Candidate0::in, Candidate::out) is det :-
- Candidate = (ProcLabel - Candidate0)
- ), Candidates0, Candidates)
+ list.foldl((pred(Candidate::in, Map0::in, Map::out) is det :-
+ multi_map.set(Map0, ProcLabel, Candidate, Map)
+ ), Candidates0, multi_map.init, Candidates)
;
% Builtin procedures cannot be found in the program representation, and
% cannot be parallelised either.
- Candidates = [],
+ Candidates = multi_map.init,
append_warning(ProcLabel, no,
warning_cannot_lookup_proc_defn,
cord.empty, Warnings)
@@ -1248,7 +1441,8 @@ get_call_site_cost(CallSitePerf) = Cost
CostTotal = PerfTotal ^ perf_row_callseqs_percall
;
MaybePerfTotal = no,
- CostTotal = 0.0
+ error(this_file ++
+ "Could not retrive total callseqs cost from call site")
),
Cost = CostSelf + CostTotal.
Index: deep_profiler/report.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/report.m,v
retrieving revision 1.18
diff -u -p -b -r1.18 report.m
--- deep_profiler/report.m 11 Feb 2009 00:35:52 -0000 1.18
+++ deep_profiler/report.m 18 Feb 2009 02:03:14 -0000
@@ -127,7 +127,11 @@
cr_ancestor_call_sites :: list(
perf_row_data(ancestor_desc)),
- % Reports for every procedure in the clique.
+ % Reports for every procedure in the clique. The first
+ % procedure in the list is the entry procedure (if the parent
+ % clique had a valid CSD.) and that CSD was found in the
+ % clique. TODO: we might want to express this within this
+ % type.
cr_clique_procs :: list(clique_proc_report)
).
-------------- 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/20090218/d785b00e/attachment.sig>
More information about the reviews
mailing list