[m-rev.] for review: chop up a big module
Zoltan Somogyi
zs at csse.unimelb.edu.au
Thu Jan 27 17:40:56 AEDT 2011
On 27-Jan-2011, Paul Bone <pbone at csse.unimelb.edu.au> wrote:
> > deep_profiler/autopar_annotate.m:
> > The part of the old module that annotated the representations of goals.
>
> You don't want to call this instmap.m?
My intention was that the module should also contain any other predicates
that associate generally useful annotations with goals, either by putting
annotations on the goals or by putting goal ids on goals and creating arrays
indexed by those goal ids.
Besides, we learned the lesson about duplicating the names of compiler modules.
Here is the next installment of the breakup. I think I am done for now,
since autopar_search_callgraph.m now looks pretty cohesive, with one exception.
Paul, please have a look and decide in which module the predicate
pard_goal_detail_to_pard_goal belongs, or whether it should be replaced
altogether.
Zoltan.
deep_profiler/autopar_calc_overlap.m:
New module for calculating the overlap between the conjuncts of a
parallelised conjunction. Its contents are taken from the old
autopar_search_callgraph.m.
deep_profiler/autopar_costs.m:
New module for calculating the costs of goals. Its contents
are taken from the old autopar_search_callgraph.m.
deep_profiler/autopar_reports.m:
New module for creating reports. Its contents are taken from
the old autopar_search_callgraph.m.
deep_profiler/autopar_search_goals.m:
New module for searching goals for parallelizable conjunctions.
Its contents are taken from the old autopar_search_callgraph.m.
deep_profiler/autopar_search_callgraph.m:
Remove the code moved to other modules.
deep_profiler/mdprof_fb.automatic_parallelism.m:
Add the new modules.
deep_profiler/*.m:
Remove unnecessary imports.
Fix copyright years on the new modules.
browser/*.m:
compiler/*.m:
mdbcomp/*.m:
Remove unnecessary imports.
library/Mercury.options:
Make it possible to compile a whole workspace with
--warn-unused-imports by turning that option off for type_desc.m
(which has a necessary import that --warn-unused-imports thinks
is unused).
cvs diff: Diffing .
cvs diff: Diffing analysis
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/doc
cvs diff: Diffing boehm_gc/extra
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/extra
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/libatomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops/doc
cvs diff: Diffing boehm_gc/libatomic_ops/src
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/armcc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/gcc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/hpc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/ibmc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/icc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/msftc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/sunc
cvs diff: Diffing boehm_gc/libatomic_ops/tests
Index: boehm_gc/libatomic_ops/tests/test_atomic_include.h
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/boehm_gc/libatomic_ops/tests/test_atomic_include.h,v
retrieving revision 1.1.1.1
diff -u -b -r1.1.1.1 test_atomic_include.h
--- boehm_gc/libatomic_ops/tests/test_atomic_include.h 23 Feb 2010 06:28:40 -0000 1.1.1.1
+++ boehm_gc/libatomic_ops/tests/test_atomic_include.h 27 Jan 2011 05:58:51 -0000
@@ -5,15 +5,6 @@
* see doc/COPYING for details.
*/
-void test_atomic(void);
-void test_atomic_release(void);
-void test_atomic_acquire(void);
-void test_atomic_read(void);
-void test_atomic_write(void);
-void test_atomic_full(void);
-void test_atomic_release_write(void);
-void test_atomic_acquire_read(void);
-
/* Some basic sanity tests. These do not test the barrier semantics. */
#undef TA_assert
cvs diff: Diffing boehm_gc/libatomic_ops-1.2
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/doc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/tests
cvs diff: Diffing boehm_gc/m4
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing browser
Index: browser/declarative_execution.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/browser/declarative_execution.m,v
retrieving revision 1.66
diff -u -b -r1.66 declarative_execution.m
--- browser/declarative_execution.m 13 Jan 2011 00:36:51 -0000 1.66
+++ browser/declarative_execution.m 27 Jan 2011 05:44:49 -0000
@@ -473,7 +473,6 @@
:- import_module exception.
:- import_module int.
:- import_module map.
-:- import_module require.
:- import_module store.
:- import_module univ.
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/call_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/call_gen.m,v
retrieving revision 1.199
diff -u -b -r1.199 call_gen.m
--- compiler/call_gen.m 13 Jan 2011 00:36:51 -0000 1.199
+++ compiler/call_gen.m 27 Jan 2011 05:50:46 -0000
@@ -65,7 +65,6 @@
:- 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.
Index: compiler/deep_profiling.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/deep_profiling.m,v
retrieving revision 1.108
diff -u -b -r1.108 deep_profiling.m
--- compiler/deep_profiling.m 13 Jan 2011 00:36:52 -0000 1.108
+++ compiler/deep_profiling.m 27 Jan 2011 05:51:09 -0000
@@ -65,7 +65,6 @@
:- import_module ll_backend.coverage_profiling.
:- import_module mdbcomp.goal_path.
:- import_module mdbcomp.prim_data.
-:- import_module mdbcomp.program_representation.
:- import_module parse_tree.builtin_lib_types.
:- import_module parse_tree.prog_type.
:- import_module transform_hlds.
Index: compiler/goal_path.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/goal_path.m,v
retrieving revision 1.58
diff -u -b -r1.58 goal_path.m
--- compiler/goal_path.m 13 Jan 2011 00:36:52 -0000 1.58
+++ compiler/goal_path.m 27 Jan 2011 05:49:54 -0000
@@ -68,15 +68,11 @@
:- import_module mdbcomp.
:- import_module parse_tree.prog_data.
-:- import_module assoc_list.
-:- import_module cord.
:- import_module int.
:- import_module list.
:- import_module map.
:- import_module maybe.
-:- import_module pair.
:- import_module require.
-:- import_module svbimap.
:- import_module svmap.
%-----------------------------------------------------------------------------%
Index: compiler/md4.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/md4.m,v
retrieving revision 1.4
diff -u -b -r1.4 md4.m
--- compiler/md4.m 19 Jan 2011 01:47:59 -0000 1.4
+++ compiler/md4.m 27 Jan 2011 05:50:04 -0000
@@ -41,8 +41,6 @@
:- implementation.
-:- import_module require.
-
%-----------------------------------------------------------------------------%
:- pragma foreign_decl("C", "local", "
Index: compiler/mode_ordering.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/mode_ordering.m,v
retrieving revision 1.34
diff -u -b -r1.34 mode_ordering.m
--- compiler/mode_ordering.m 13 Jan 2011 00:36:53 -0000 1.34
+++ compiler/mode_ordering.m 27 Jan 2011 05:49:30 -0000
@@ -45,7 +45,6 @@
:- import_module check_hlds.clause_to_proc.
:- import_module check_hlds.mode_constraint_robdd.
-:- import_module hlds.goal_path.
:- import_module hlds.hlds_goal.
:- import_module hlds.inst_graph.
:- import_module mode_robdd.
Index: compiler/process_util.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/process_util.m,v
retrieving revision 1.34
diff -u -b -r1.34 process_util.m
--- compiler/process_util.m 19 Jan 2011 01:47:59 -0000 1.34
+++ compiler/process_util.m 27 Jan 2011 05:50:22 -0000
@@ -123,8 +123,6 @@
:- implementation.
-:- import_module require.
-
%-----------------------------------------------------------------------------%
build_with_check_for_interrupt(VeryVerbose, Build, Cleanup, Succeeded,
Index: compiler/timestamp.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/timestamp.m,v
retrieving revision 1.16
diff -u -b -r1.16 timestamp.m
--- compiler/timestamp.m 19 Jan 2011 07:01:49 -0000 1.16
+++ compiler/timestamp.m 27 Jan 2011 05:50:57 -0000
@@ -55,7 +55,6 @@
:- import_module int.
:- import_module maybe.
-:- import_module require.
:- import_module string.
%-----------------------------------------------------------------------------%
Index: compiler/trace_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/trace_gen.m,v
retrieving revision 1.34
diff -u -b -r1.34 trace_gen.m
--- compiler/trace_gen.m 13 Jan 2011 00:36:53 -0000 1.34
+++ compiler/trace_gen.m 27 Jan 2011 05:51:18 -0000
@@ -235,7 +235,6 @@
:- import_module check_hlds.inst_match.
:- import_module check_hlds.mode_util.
:- import_module check_hlds.type_util.
-:- import_module hlds.goal_path.
:- import_module hlds.code_model.
:- import_module hlds.hlds_llds.
:- import_module hlds.instmap.
cvs diff: Diffing compiler/notes
cvs diff: Diffing deep_profiler
Index: deep_profiler/autopar_annotate.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/autopar_annotate.m,v
retrieving revision 1.1
diff -u -b -r1.1 autopar_annotate.m
--- deep_profiler/autopar_annotate.m 27 Jan 2011 02:53:46 -0000 1.1
+++ deep_profiler/autopar_annotate.m 27 Jan 2011 05:11:54 -0000
@@ -1,7 +1,7 @@
%-----------------------------------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%-----------------------------------------------------------------------------%
-% Copyright (C) 2006-2011 The University of Melbourne.
+% Copyright (C) 2011 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -45,36 +45,9 @@
:- implementation.
-:- import_module analysis_utils.
-:- import_module branch_and_bound.
-:- import_module coverage.
-:- import_module create_report.
:- import_module mdbcomp.goal_path.
-:- import_module measurement_units.
-:- import_module measurements.
-:- import_module message.
-:- import_module profile.
-:- import_module recursion_patterns.
-:- import_module report.
-:- import_module solutions.
-:- import_module var_use_analysis.
-
-:- import_module array.
-:- import_module assoc_list.
-:- import_module bool.
-:- import_module cord.
-:- import_module float.
-:- import_module int.
-:- import_module io.
-:- import_module lazy.
+
:- import_module list.
-:- import_module map.
-:- import_module maybe.
-:- import_module pair.
-:- import_module require.
-:- import_module std_util.
-:- import_module string.
-:- import_module svmap.
%----------------------------------------------------------------------------%
%
Index: deep_profiler/autopar_calc_overlap.m
===================================================================
RCS file: deep_profiler/autopar_calc_overlap.m
diff -N deep_profiler/autopar_calc_overlap.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ deep_profiler/autopar_calc_overlap.m 27 Jan 2011 05:13:51 -0000
@@ -0,0 +1,627 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2011 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: autopar_calc_overlap.m
+% Author: pbone.
+%
+% This module contains the code that calculates the likely overlap
+% between conjuncts in a parallelized conjunction.
+%
+%-----------------------------------------------------------------------------%
+
+:- module mdprof_fb.automatic_parallelism.autopar_calc_overlap.
+:- interface.
+
+:- import_module mdprof_fb.automatic_parallelism.autopar_types.
+
+ % calculate_parallel_cost(Info, !Parallelisation).
+ %
+ % Analyse the parallel conjuncts and determine their likely performance.
+ %
+ % This is the new parallel execution overlap algorithm, it is general and
+ % therefore we also use it for independent conjunctions.
+ %
+:- pred calculate_parallel_cost(parallelisation_cost_data::out,
+ incomplete_parallelisation::in, incomplete_parallelisation::out) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module mdbcomp.
+:- import_module mdbcomp.feedback.
+:- import_module mdbcomp.feedback.automatic_parallelism.
+:- import_module mdbcomp.program_representation.
+:- import_module mdprof_fb.automatic_parallelism.autopar_costs.
+:- import_module measurements.
+:- import_module var_use_analysis.
+
+:- import_module assoc_list.
+:- import_module digraph.
+:- import_module float.
+:- import_module int.
+:- import_module lazy.
+:- import_module list.
+:- import_module map.
+:- import_module maybe.
+:- import_module pair.
+:- import_module require.
+:- import_module set.
+:- import_module string.
+:- import_module svmap.
+
+%----------------------------------------------------------------------------%
+
+calculate_parallel_cost(CostData, !Parallelisation) :-
+ ParConj = ip_get_par_conjs(!.Parallelisation),
+ NumCalls = !.Parallelisation ^ ip_num_calls,
+
+ maybe_calc_sequential_cost(
+ (func(P) = P ^ ip_maybe_goals_before_cost),
+ (func(P0, MaybeCost) = P0 ^ ip_maybe_goals_before_cost := MaybeCost),
+ ip_get_goals_before, CostBeforePercall, NumCalls, !Parallelisation),
+ maybe_calc_sequential_cost(
+ (func(P) = P ^ ip_maybe_goals_after_cost),
+ (func(P0, MaybeCost) = P0 ^ ip_maybe_goals_after_cost := MaybeCost),
+ ip_get_goals_after, CostAfterPercall, NumCalls, !Parallelisation),
+
+ Info = !.Parallelisation ^ ip_info,
+ Opts = Info ^ ipi_opts,
+ SparkCost = Opts ^ cpcp_sparking_cost,
+ SparkDelay = Opts ^ cpcp_sparking_delay,
+ BarrierCost = Opts ^ cpcp_barrier_cost,
+ ContextWakeupDelay = Opts ^ cpcp_context_wakeup_delay,
+ Metrics0 = init_empty_parallel_exec_metrics(CostBeforePercall,
+ CostAfterPercall, NumCalls, float(SparkCost), float(SparkDelay),
+ float(BarrierCost), float(ContextWakeupDelay)),
+ Overlap0 = peo_empty_conjunct,
+
+ SharedVars = ip_calc_sharedvars_set(!.Parallelisation),
+ CostData0 = parallelisation_cost_data(SharedVars, Overlap0, Metrics0, init),
+ NumMiddleGoals = ip_get_num_goals_middle(!.Parallelisation),
+ list.foldl3(calculate_parallel_cost_step(Info, NumMiddleGoals), ParConj,
+ 1, _, 0, _, CostData0, CostData),
+ !Parallelisation ^ ip_maybe_par_cost_data := yes(CostData).
+
+:- pred maybe_calc_sequential_cost((func(T) = maybe(goal_cost_csq))::in,
+ (func(T, maybe(goal_cost_csq)) = T)::in,
+ (func(T) = list(pard_goal_detail))::in, float::out,
+ int::in, T::in, T::out) is det.
+
+maybe_calc_sequential_cost(GetMaybe, SetMaybe, GetGoals, CostPercall, Calls,
+ !Acc) :-
+ MaybeCost = GetMaybe(!.Acc),
+ (
+ MaybeCost = yes(Cost)
+ ;
+ MaybeCost = no,
+ Goals = GetGoals(!.Acc),
+ conj_calc_cost(Goals, Calls, Cost),
+ !:Acc = SetMaybe(!.Acc, yes(Cost))
+ ),
+ CostPercall = goal_cost_get_percall(Cost).
+
+:- type is_last_par_conjunct
+ ---> is_last_par_conjunct
+ ; not_last_par_conjunct.
+
+:- pred calculate_parallel_cost_step(implicit_parallelism_info::in,
+ int::in, seq_conj(pard_goal_detail)::in, int::in, int::out,
+ int::in, int::out,
+ parallelisation_cost_data::in, parallelisation_cost_data::out) is det.
+
+calculate_parallel_cost_step(Info, NumMiddleGoals, Conjunct, !ConjNum,
+ !NumGoals, !CostData) :-
+ !.CostData = parallelisation_cost_data(SharedVars, Overlap0, Metrics0,
+ PM0),
+ !:NumGoals = !.NumGoals + length(Conjuncts),
+ ( !.NumGoals = NumMiddleGoals ->
+ IsLastConjunct = is_last_par_conjunct
+ ;
+ IsLastConjunct = not_last_par_conjunct
+ ),
+ Conjunct = seq_conj(Conjuncts),
+ calculate_parallel_cost_step(Info, SharedVars, IsLastConjunct, Conjuncts,
+ !ConjNum, PM0, PM, Overlap0, Overlap, Metrics0, Metrics),
+ !:CostData = parallelisation_cost_data(SharedVars, Overlap, Metrics, PM).
+
+:- pred calculate_parallel_cost_step(implicit_parallelism_info::in,
+ set(var_rep)::in, is_last_par_conjunct::in, list(pard_goal_detail)::in,
+ int::in, int::out, map(var_rep, float)::in, map(var_rep, float)::out,
+ parallel_execution_overlap::in, parallel_execution_overlap::out,
+ parallel_exec_metrics_incomplete::in,
+ parallel_exec_metrics_incomplete::out) is det.
+
+calculate_parallel_cost_step(Info, AllSharedVars, IsLastConjunct, Conjunct,
+ !ConjNum, !ProductionsMap, !Overlap, !Metrics) :-
+ Algorithm = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs,
+
+ Calls = parallel_exec_metrics_get_num_calls(!.Metrics),
+ conj_calc_cost(Conjunct, Calls, CostB0),
+ CostB = goal_cost_get_percall(CostB0),
+ list.foldl2(conj_produced_and_consumed_vars, Conjunct,
+ set.init, RightProducedVars0, set.init, RightConsumedVars0),
+ RightProducedVars = set.intersect(RightProducedVars0, AllSharedVars),
+ RightConsumedVars = set.intersect(RightConsumedVars0, AllSharedVars),
+ ProducedVars =
+ set.from_sorted_list(map.sorted_keys(!.ProductionsMap)),
+ Vars = set.intersect(ProducedVars, RightConsumedVars),
+
+ % This conjunct will actually start after it has been sparked by
+ % the previous conjunct, which in turn may have been sparked by an
+ % earlier conjunct.
+ SparkDelay = Info ^ ipi_opts ^ cpcp_sparking_delay,
+ StartTime0 = float((!.ConjNum - 1) * SparkDelay),
+
+ % If there are conjuncts after this conjunct, we will have
+ % the additional cost of sparking them.
+ (
+ IsLastConjunct = not_last_par_conjunct,
+ SparkCost = float(Info ^ ipi_opts ^ cpcp_sparking_cost)
+ ;
+ IsLastConjunct = is_last_par_conjunct,
+ SparkCost = 0.0
+ ),
+ StartTime = StartTime0 + SparkCost,
+
+ (
+ Algorithm = parallelise_dep_conjs_overlap,
+
+ % Get the list of variables consumed by this conjunct
+ % that will be turned into futures.
+ list.foldl4(get_consumptions_and_productions_list, Conjunct, Vars, _,
+ RightProducedVars, _, 0.0, _,
+ [], ConsumptionsAndProductionsList0),
+ list.reverse(ConsumptionsAndProductionsList0,
+ ConsumptionsAndProductionsList),
+
+ % Determine how the parallel conjuncts overlap.
+ list.foldl5(
+ calculate_dependent_parallel_cost_2(Info, !.ProductionsMap),
+ ConsumptionsAndProductionsList, 0.0, LastSeqConsumeTime,
+ StartTime, LastParConsumeTime, StartTime, LastResumeTime,
+ [], RevExecution0, map.init, ConsumptionsMap),
+
+ % Calculate the point at which this conjunct finishes execution
+ % and complete the RevExecutions structure..
+ list.reverse(RevExecution, Execution),
+ CostBParElapsed = LastParConsumeTime + (CostB - LastSeqConsumeTime),
+ RevExecution = [ (LastResumeTime - CostBParElapsed) | RevExecution0 ],
+
+ CostSignals = float(Info ^ ipi_opts ^ cpcp_future_signal_cost *
+ count(RightProducedVars)),
+ CostWaits = float(Info ^ ipi_opts ^ cpcp_future_wait_cost *
+ count(Vars)),
+ calc_cost_and_dead_time(Execution, CostBPar, DeadTime)
+ ;
+ ( Algorithm = parallelise_dep_conjs_naive
+ ; Algorithm = do_not_parallelise_dep_conjs
+ ; Algorithm = parallelise_dep_conjs_num_vars
+ ),
+
+ CostBPar = CostB + SparkCost,
+ Execution = [StartTime - (StartTime + CostB)],
+ ConsumptionsMap = init,
+ CostSignals = 0.0,
+ CostWaits = 0.0,
+ DeadTime = 0.0
+ ),
+
+ % CostB - the cost of B if it where to be executed in sequence.
+ % CostBPar - CostB plus the overheads of parallel exection (not including
+ % the dead time).
+ % DeadTime - The time that B spends blocked on other computations.
+ % XXX: Need to account for SparkDelay here,
+ !:Metrics = init_parallel_exec_metrics_incomplete(!.Metrics, CostSignals,
+ CostWaits, CostB, CostBPar, DeadTime),
+
+ % Build the productions map for the next conjunct. This map contains
+ % all the variables produced by this code, not just that are used for
+ % dependent parallelisation.
+ list.foldl3(get_productions_map(RightProducedVars), Conjunct, StartTime, _,
+ Execution, _, !ProductionsMap),
+
+ DepConjExec = dependent_conjunct_execution(Execution,
+ !.ProductionsMap, ConsumptionsMap),
+ !:Overlap = peo_conjunction(!.Overlap, DepConjExec, Vars),
+ !:ConjNum = !.ConjNum + 1.
+
+ % calculate_dependent_parallel_cost_2(Info, ProductionsMap,
+ % Var - SeqConsTime, !PrevSeqConsumeTime, !PrevParConsumeTime,
+ % !ResumeTime, !RevExecution, !ConsumptionsMap).
+ %
+ % The main loop of the parallel overlap analysis.
+ %
+ % * ProductionsMap: A map of variable productions to the left of this
+ % conjunct.
+ %
+ % * Var: The current variable under consideration.
+ %
+ % * SeqConsTime: The type of event for this variable in this conjunct and
+ % the time at which it occurs. It is either consumed or produced by this
+ % conjunct.
+ %
+ % * !PrevSeqConsumeTime: Accumulates the time of the previous consumption
+ % during sequential execution, or if there is none it represents the
+ % beginning of sequential execution (0.0).
+ %
+ % * !PrevParConsumeTime: Accumulates the time of the previous consumption
+ % during parallel execution. Or if there is none this represents the
+ % tame that the parallel conjunct first begun execution.
+ %
+ % * !ResumeTime: Accumulates the time that execution last resumed if it
+ % became blocked, or the beginning of the parallel conjunct's execution.
+ %
+ % * !RevExecution: Accumulates a list of pairs, each pair stores the time
+ % that execution begun and the time that it pasted. This never includes
+ % the remaining execution after all variables have been consumed. This
+ % is used by our caller to calculate the production times of this
+ % conjunct for later ones.
+ %
+ % * !ConsumptionsMap: Accumuates a map of variable consumptions.
+ %
+:- pred calculate_dependent_parallel_cost_2(implicit_parallelism_info::in,
+ map(var_rep, float)::in, pair(var_rep, production_or_consumption)::in,
+ float::in, float::out, float::in, float::out, float::in, float::out,
+ assoc_list(float, float)::in, assoc_list(float, float)::out,
+ map(var_rep, float)::in, map(var_rep, float)::out) is det.
+
+calculate_dependent_parallel_cost_2(Info, ProductionsMap, Var - SeqEventTime,
+ !PrevSeqConsumeTime, !PrevParConsumeTime, !ResumeTime,
+ !RevExecution, !ConsumptionsMap) :-
+ (
+ SeqEventTime = consumption(SeqConsTime),
+ calculate_dependent_parallel_cost_consumption(Info, ProductionsMap,
+ Var - SeqConsTime, !PrevSeqConsumeTime, !PrevParConsumeTime,
+ !ResumeTime, !RevExecution, !ConsumptionsMap)
+ ;
+ SeqEventTime = production(SeqProdTime),
+ calculate_dependent_parallel_cost_production(Info, SeqProdTime,
+ !PrevSeqConsumeTime, !PrevParConsumeTime, !ResumeTime,
+ !RevExecution, !ConsumptionsMap)
+ ).
+
+:- pred calculate_dependent_parallel_cost_consumption(
+ implicit_parallelism_info::in, map(var_rep, float)::in,
+ pair(var_rep, float)::in, float::in, float::out,
+ float::in, float::out, float::in, float::out,
+ assoc_list(float, float)::in, assoc_list(float, float)::out,
+ map(var_rep, float)::in, map(var_rep, float)::out) is det.
+
+calculate_dependent_parallel_cost_consumption(Info, ProductionsMap,
+ Var - SeqConsTime, !PrevSeqConsumeTime, !PrevParConsumeTime,
+ !ResumeTime, !RevExecution, !ConsumptionsMap) :-
+ map.lookup(ProductionsMap, Var, ProdTime),
+ % Consider (P & Q):
+ %
+ % Q cannot consume the variable until P produces it. Also Q cannot consume
+ % the variable until it is ready for it. These are the two parameters to
+ % max/2.
+ %
+ % The second parameter can be explained further. Q may have waited on a
+ % future previously, if so !.PrevParConsumeTime is when it finished
+ % waiting, and SeqConsTime - !.PrevSeqConsumeTime is how long Q will take
+ % between the two waits.
+ %
+ ParConsTimeBlocked = ProdTime,
+ ParConsTimeNotBlocked = !.PrevParConsumeTime +
+ (SeqConsTime - !.PrevSeqConsumeTime),
+ ParConsTime0 = max(ParConsTimeBlocked, ParConsTimeNotBlocked) +
+ float(Info ^ ipi_opts ^ cpcp_future_wait_cost),
+
+ (
+ % True if Q had to suspend waiting for P. Note that we don't include
+ % FutureSyncTime here. This is true if Q has to block at all even if
+ % it can be made runable before the context switch is complete.
+ ProdTime > ParConsTimeNotBlocked
+ ->
+ % Include the time that it may take to resume this thread.
+ ParConsTime = ParConsTime0 +
+ float(Info ^ ipi_opts ^ cpcp_context_wakeup_delay),
+ !:RevExecution =
+ [(!.ResumeTime - ParConsTimeNotBlocked) | !.RevExecution],
+ !:ResumeTime = ParConsTime
+ ;
+ ParConsTime = ParConsTime0
+ ),
+
+ !:PrevSeqConsumeTime = SeqConsTime,
+ !:PrevParConsumeTime = ParConsTime,
+
+ svmap.det_insert(Var, ParConsTime, !ConsumptionsMap).
+
+:- pred calculate_dependent_parallel_cost_production(
+ implicit_parallelism_info::in, float::in, float::in, float::out,
+ float::in, float::out, float::in, float::out,
+ assoc_list(float, float)::in, assoc_list(float, float)::out,
+ map(var_rep, float)::in, map(var_rep, float)::out) is det.
+
+calculate_dependent_parallel_cost_production(Info,
+ SeqProdTime, !PrevSeqConsumeTime, !PrevParConsumeTime,
+ !ResumeTime, !RevExecution, !ConsumptionsMap) :-
+ SignalCost = float(Info ^ ipi_opts ^ cpcp_future_signal_cost),
+
+ ParProdTime = !.PrevParConsumeTime +
+ (SeqProdTime - !.PrevSeqConsumeTime) + SignalCost,
+ !:PrevSeqConsumeTime = SeqProdTime,
+ !:PrevParConsumeTime = ParProdTime.
+
+ % Abstract code for querying a graph for a goal dependency.
+ %
+:- pred graph_do_lookup(
+ pred(digraph(int), digraph_key(int), set(digraph_key(int)))::
+ in(pred(in, in, out) is det),
+ digraph(int)::in, int::in, set(int)::out) is det.
+
+graph_do_lookup(Lookup, Graph, GoalNum, Deps) :-
+ Lookup(Graph, lookup_key(Graph, GoalNum), DepsKeys),
+ Deps = set(map(lookup_vertex(Graph), set.to_sorted_list(DepsKeys))).
+
+ % foldl(get_productions_map(Goals, 0,0, _, Vars, _, map.init, Map).
+ %
+ % If Goals is semidet this can produce incorrect values in the !Time
+ % accumulator that lead to exceptions. This is prevented by only
+ % attempting to parallelise goals that are det or cc_multi.
+ %
+ % Build a map of variable productions in Goals.
+ %
+:- pred get_productions_map(set(var_rep)::in, pard_goal_detail::in,
+ float::in, float::out,
+ assoc_list(float, float)::in, assoc_list(float, float)::out,
+ map(var_rep, float)::in, map(var_rep, float)::out) is det.
+
+get_productions_map(Vars, Goal, !Time, !Executions, !Map) :-
+ InstMapInfo = Goal ^ goal_annotation ^ pgd_inst_map_info,
+ BoundVars0 = InstMapInfo ^ im_bound_vars,
+ BoundVars = set.intersect(BoundVars0, Vars),
+ adjust_time_for_waits(!Time, !Executions),
+ set.fold(var_production_time_to_map(!.Time, Goal), BoundVars, !Map),
+ !:Time = !.Time + goal_cost_get_percall(Goal ^ goal_annotation ^ pgd_cost).
+
+:- pred adjust_time_for_waits(float::in, float::out,
+ assoc_list(float, float)::in, assoc_list(float, float)::out) is det.
+
+adjust_time_for_waits(!Time, !Executions) :-
+ (
+ !.Executions = [Execution | NextExecution],
+ ( Start - End ) = Execution,
+ ( (!.Time + adjust_time_for_waits_epsilon) < Start ->
+ error("adjust_time_for_waits: " ++
+ "Time occurs before the current execution")
+ ; !.Time =< (End + adjust_time_for_waits_epsilon) ->
+ % The production is within the current execution, no adjustment is
+ % necessary.
+ true
+ ;
+ % The time is after this execution.
+ !:Executions = NextExecution,
+ adjust_time_for_waits_2(End, !Time, !Executions)
+ )
+ ;
+ !.Executions = [],
+ error("adjust_time_for_waits: Time occurs after all executions")
+ ).
+
+:- pred adjust_time_for_waits_2(float::in, float::in, float::out,
+ assoc_list(float, float)::in, assoc_list(float, float)::out) is det.
+
+adjust_time_for_waits_2(LastEnd, !Time, !Executions) :-
+ (
+ !.Executions = [ Execution | NextExecution ],
+ ( Start - End ) = Execution,
+
+ % Do the adjustment.
+ !:Time = !.Time + (Start - LastEnd),
+
+ ( (!.Time + adjust_time_for_waits_epsilon) < Start ->
+ error(format("adjust_time_for_waits: Adjustment didn't work, " ++
+ "time occurs before the current execution. " ++
+ "Time: %f, Start: %f.", [f(!.Time), f(Start)]))
+ ; !.Time =< (End + adjust_time_for_waits_epsilon) ->
+ % The adjustment worked.
+ true
+ ;
+ % Further adjustment is needed.
+ !:Executions = NextExecution,
+ adjust_time_for_waits_2(End, !Time, !Executions)
+ )
+ ;
+ !.Executions = [],
+ error("adjust_time_for_waits: Ran out of executions")
+ ).
+
+:- func adjust_time_for_waits_epsilon = float.
+
+adjust_time_for_waits_epsilon = 0.0001.
+
+ % Calculate the time spend during execution and the time spent between
+ % executions (dead time).
+ %
+:- pred calc_cost_and_dead_time(assoc_list(float, float)::in, float::out,
+ float::out) is det.
+
+calc_cost_and_dead_time([], 0.0, 0.0).
+calc_cost_and_dead_time([Start - Stop | Executions], !:Time, DeadTime) :-
+ !:Time = Stop - Start,
+ calc_cost_and_dead_time_2(Executions, Stop, !Time, 0.0, DeadTime).
+
+:- pred calc_cost_and_dead_time_2(assoc_list(float, float)::in, float::in,
+ float::in, float::out, float::in, float::out) is det.
+
+calc_cost_and_dead_time_2([], _, !Time, !DeadTime).
+calc_cost_and_dead_time_2([Start - Stop | Executions], LastStop,
+ !Time, !DeadTime) :-
+ !:Time = !.Time + Stop - Start,
+ !:DeadTime = !.DeadTime + Start - LastStop,
+ calc_cost_and_dead_time_2(Executions, Stop, !Time, !DeadTime).
+
+ % var_production_time_to_map(TimeBefore, Goal, Var, !Map).
+ %
+ % Find the latest production time of Var in Goal, and add TimeBefore + the
+ % production time to the map. An exception is thrown if a duplicate map
+ % entry is found, our caller must prevent this.
+ %
+:- pred var_production_time_to_map(float::in, pard_goal_detail::in,
+ var_rep::in, map(var_rep, float)::in, map(var_rep, float)::out) is det.
+
+var_production_time_to_map(TimeBefore, Goal, Var, !Map) :-
+ var_first_use_time(find_production, TimeBefore, Goal, Var, Time),
+ svmap.det_insert(Var, Time, !Map).
+
+ % Either a production or consumption time. Consumptions should sort before
+ % productions.
+ %
+:- type production_or_consumption
+ ---> consumption(float)
+ ; production(float).
+
+ % foldl(get_consumptions_list(Vars), Goals, 0.0, _, [], RevConsumptions),
+ %
+ % Compute the order and time of variable consumptions in goals.
+ %
+:- pred get_consumptions_and_productions_list(pard_goal_detail::in,
+ set(var_rep)::in, set(var_rep)::out,
+ set(var_rep)::in, set(var_rep)::out, float::in, float::out,
+ assoc_list(var_rep, production_or_consumption)::in,
+ assoc_list(var_rep, production_or_consumption)::out) is det.
+
+get_consumptions_and_productions_list(Goal, !ConsumedVars, !ProducedVars,
+ !Time, !List) :-
+ InstMapInfo = Goal ^ goal_annotation ^ pgd_inst_map_info,
+
+ AllConsumptionVars = InstMapInfo ^ im_consumed_vars,
+ ConsumptionVars = set.intersect(!.ConsumedVars, AllConsumptionVars),
+ set.map(var_consumptions(!.Time, Goal),
+ ConsumptionVars, ConsumptionTimesSet0),
+ !:ConsumedVars = difference(!.ConsumedVars, ConsumptionVars),
+ % Since we re-sort the list we don't need a sorted one to start with,
+ % but the set module doesn't export a "to_list" predicate. (Getting
+ % a sorted list has no cost since the set is a sorted list internally).
+ set.to_sorted_list(ConsumptionTimesSet0, ConsumptionTimes0),
+ list.sort(compare_times, ConsumptionTimes0, ConsumptionTimes),
+
+ AllProductionVars = InstMapInfo ^ im_bound_vars,
+ ProductionVars = set.intersect(!.ProducedVars, AllProductionVars),
+ set.map(var_productions(!.Time, Goal),
+ ProductionVars, ProductionTimesSet0),
+ !:ProducedVars = difference(!.ProducedVars, ProductionVars),
+ set.to_sorted_list(ProductionTimesSet0, ProductionTimes0),
+ list.sort(compare_times, ProductionTimes0, ProductionTimes),
+
+ merge_consumptions_and_productions(ConsumptionTimes, ProductionTimes,
+ ConsumptionAndProductionTimes),
+ !:List = ConsumptionAndProductionTimes ++ !.List,
+ !:Time = !.Time + goal_cost_get_percall(Goal ^ goal_annotation ^ pgd_cost).
+
+:- pred compare_times(pair(A, float)::in, pair(A, float)::in,
+ comparison_result::out) is det.
+
+compare_times(_ - TimeA, _ - TimeB, Result) :-
+ % Note that the Time arguments are swapped, this list must be
+ % produced in latest to earliest order.
+ compare(Result, TimeB, TimeA).
+
+:- pred merge_consumptions_and_productions(
+ assoc_list(var_rep, float)::in, assoc_list(var_rep, float)::in,
+ assoc_list(var_rep, production_or_consumption)::out) is det.
+
+merge_consumptions_and_productions([], [], []).
+merge_consumptions_and_productions([],
+ [Var - Time | Prods0], [Var - production(Time) | Prods]) :-
+ merge_consumptions_and_productions([], Prods0, Prods).
+merge_consumptions_and_productions([Var - Time | Cons0], [],
+ [Var - consumption(Time) | Cons]) :-
+ merge_consumptions_and_productions(Cons0, [], Cons).
+merge_consumptions_and_productions(Cons@[ConsVar - ConsTime | Cons0],
+ Prods@[ProdVar - ProdTime | Prods0], [ProdOrCons | ProdsAndCons]) :-
+ ( ProdTime < ConsTime ->
+ % Order earlier events first,
+ ProdOrCons = ProdVar - production(ProdTime),
+ merge_consumptions_and_productions(Cons, Prods0, ProdsAndCons)
+ ;
+ % In this branch either the consumption occurs first or the events
+ % occur at the same time in which case we order consumptions first.
+ ProdOrCons = ConsVar - consumption(ConsTime),
+ merge_consumptions_and_productions(Cons0, Prods, ProdsAndCons)
+ ).
+
+:- pred var_consumptions(float::in, pard_goal_detail::in, var_rep::in,
+ pair(var_rep, float)::out) is det.
+
+var_consumptions(TimeBefore, Goal, Var, Var - Time) :-
+ var_first_use_time(find_consumption, TimeBefore, Goal, Var, Time).
+
+:- pred var_productions(float::in, pard_goal_detail::in, var_rep::in,
+ pair(var_rep, float)::out) is det.
+
+var_productions(TimeBefore, Goal, Var, Var - Time) :-
+ var_first_use_time(find_production, TimeBefore, Goal, Var, Time).
+
+:- type find_production_or_consumption
+ ---> find_production
+ ; find_consumption.
+
+ % var_first_use_time(FindProdOrCons, Time0, Goal, Var, Time).
+ %
+ % if FindProdOrCons = find_production
+ % Time is Time0 + the time that Goal produces Var.
+ % elif FindProdOrCons = find_consumption
+ % Time is Time0 + the time that Goal first consumes Var.
+ %
+:- pred var_first_use_time(find_production_or_consumption::in,
+ float::in, pard_goal_detail::in, var_rep::in, float::out) is det.
+
+var_first_use_time(FindProdOrCons, TimeBefore, Goal, Var, Time) :-
+ (
+ FindProdOrCons = find_production,
+ Map = Goal ^ goal_annotation ^ pgd_var_production_map
+ ;
+ FindProdOrCons = find_consumption,
+ Map = Goal ^ goal_annotation ^ pgd_var_consumption_map
+ ),
+ map.lookup(Map, Var, LazyUse),
+ Use = force(LazyUse),
+ UseType = Use ^ vui_use_type,
+ (
+ (
+ UseType = var_use_production,
+ (
+ FindProdOrCons = find_production
+ ;
+ FindProdOrCons = find_consumption,
+ unexpected($module, $pred,
+ "Found production when looking for consumption")
+ )
+ ;
+ UseType = var_use_consumption,
+ (
+ FindProdOrCons = find_production,
+ unexpected($module, $pred,
+ "Found consumption when looking for production")
+ ;
+ FindProdOrCons = find_consumption
+ )
+ ),
+ UseTime = Use ^ vui_cost_until_use
+ ;
+ UseType = var_use_other,
+ % The analysis didn't recognise the instantiation here, so use a
+ % conservative default for the production time.
+ % XXX: How often does this occur?
+ (
+ FindProdOrCons = find_production,
+ UseTime = goal_cost_get_percall(Goal ^ goal_annotation ^ pgd_cost)
+ ;
+ FindProdOrCons = find_consumption,
+ UseTime = 0.0
+ )
+ ),
+ Time = TimeBefore + UseTime.
+
+%----------------------------------------------------------------------------%
Index: deep_profiler/autopar_costs.m
===================================================================
RCS file: deep_profiler/autopar_costs.m
diff -N deep_profiler/autopar_costs.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ deep_profiler/autopar_costs.m 27 Jan 2011 05:15:44 -0000
@@ -0,0 +1,337 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2011 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: autopar_costs.m
+% Authors: pbone, zs.
+%
+% This module contains the code for computing costs of goals, as well as
+% costs up to the time of the production or first consumption of a variable.
+%
+%-----------------------------------------------------------------------------%
+
+:- module mdprof_fb.automatic_parallelism.autopar_costs.
+:- interface.
+
+:- import_module mdbcomp.
+:- import_module mdbcomp.goal_path.
+:- import_module mdbcomp.program_representation.
+:- import_module mdprof_fb.automatic_parallelism.autopar_types.
+:- import_module measurements.
+:- import_module report.
+:- import_module var_use_analysis.
+
+:- import_module lazy.
+:- import_module list.
+:- import_module map.
+:- import_module maybe.
+
+%-----------------------------------------------------------------------------%
+
+:- pred conj_calc_cost(list(pard_goal_detail)::in, int::in,
+ goal_cost_csq::out) is det.
+
+:- pred disj_calc_cost(list(pard_goal_detail)::in, int::in,
+ goal_cost_csq::out) is det.
+
+:- pred switch_calc_cost(list(case_rep(pard_goal_detail_annotation))::in,
+ int::in, goal_cost_csq::out) is det.
+
+:- pred ite_calc_cost(pard_goal_detail::in, pard_goal_detail::in,
+ pard_goal_detail::in, goal_cost_csq::out) is det.
+
+%-----------------------------------------------------------------------------%
+
+:- pred atomic_goal_build_use_map(atomic_goal_rep::in,
+ list(goal_path_step)::in, implicit_parallelism_info::in,
+ var_use_type::in, var_rep::in,
+ map(var_rep, lazy(var_use_info))::in,
+ map(var_rep, lazy(var_use_info))::out) is det.
+
+%-----------------------------------------------------------------------------%
+
+:- pred recursion_type_get_interesting_parallelisation_depth(
+ recursion_type, maybe(recursion_depth)).
+:- mode recursion_type_get_interesting_parallelisation_depth(
+ in(recursion_type_known_costs), out(maybe_yes(ground))) is det.
+:- mode recursion_type_get_interesting_parallelisation_depth(
+ in, out) is det.
+
+%-----------------------------------------------------------------------------%
+
+:- pred implicit_par_info_intermodule_var_use(implicit_parallelism_info::in,
+ intermodule_var_use::out) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module analysis_utils.
+:- import_module coverage.
+:- import_module mdbcomp.feedback.
+:- import_module mdbcomp.feedback.automatic_parallelism.
+:- import_module message.
+:- import_module profile.
+:- import_module program_representation_utils.
+
+:- import_module bool.
+:- import_module cord.
+:- import_module float.
+:- import_module int.
+:- import_module io.
+:- import_module require.
+:- import_module set.
+:- import_module solutions.
+:- import_module string.
+:- import_module svmap.
+
+%----------------------------------------------------------------------------%
+
+conj_calc_cost([], Calls, simple_goal_cost(Calls)).
+conj_calc_cost([Conj | Conjs], _, Cost) :-
+ Coverage = Conj ^ goal_annotation ^ pgd_coverage,
+ get_coverage_after_det(Coverage, After),
+ conj_calc_cost(Conjs, After, ConjsCost),
+ ConjCost = Conj ^ goal_annotation ^ pgd_cost,
+ Cost = add_goal_costs_seq(ConjCost, ConjsCost).
+
+disj_calc_cost([], Calls, simple_goal_cost(Calls)).
+disj_calc_cost([Disj | Disjs], _, Cost) :-
+ Coverage = Disj ^ goal_annotation ^ pgd_coverage,
+ get_coverage_before_and_after_det(Coverage, Before, After),
+ ( Before = 0 ->
+ % Avoid a divide by zero.
+ Cost = dead_goal_cost
+ ;
+ _Successes = After,
+ Failures = Before - After,
+ % XXX: We assume this is a semidet disjunction
+ disj_calc_cost(Disjs, Failures, FailureCost),
+ DisjCost = Disj ^ goal_annotation ^ pgd_cost,
+ SuccessCost = atomic_goal_cost(After),
+ BranchCost = add_goal_costs_branch(Before, FailureCost, SuccessCost),
+ Cost = add_goal_costs_seq(DisjCost, BranchCost)
+ ).
+
+switch_calc_cost([], Calls, simple_goal_cost(Calls)).
+switch_calc_cost([Case | Cases], TotalCalls, Cost) :-
+ ( TotalCalls = 0 ->
+ % Avoid a divide by zero.
+ Cost = dead_goal_cost
+ ;
+ Coverage = Case ^ cr_case_goal ^ goal_annotation ^ pgd_coverage,
+ get_coverage_before_det(Coverage, CaseCalls),
+ switch_calc_cost(Cases, TotalCalls - CaseCalls, CasesCost),
+ CaseCost = Case ^ cr_case_goal ^ goal_annotation ^ pgd_cost,
+ Cost = add_goal_costs_branch(TotalCalls, CaseCost, CasesCost)
+ ).
+
+ite_calc_cost(Cond, Then, Else, Cost) :-
+ CondCost = Cond ^ goal_annotation ^ pgd_cost,
+ ThenCost = Then ^ goal_annotation ^ pgd_cost,
+ ElseCost = Else ^ goal_annotation ^ pgd_cost,
+ Coverage = Cond ^ goal_annotation ^ pgd_coverage,
+ get_coverage_before_det(Coverage, Before),
+ ThenElseCost = add_goal_costs_branch(Before, ThenCost, ElseCost),
+ Cost = add_goal_costs_seq(CondCost, ThenElseCost).
+
+:- func simple_goal_cost(int) = goal_cost_csq.
+
+simple_goal_cost(Calls) = Cost :-
+ ( Calls = 0 ->
+ Cost = dead_goal_cost
+ ;
+ Cost = atomic_goal_cost(Calls)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+atomic_goal_build_use_map(AtomicGoal, RevGoalPathSteps, Info, VarUseType, Var,
+ !Map) :-
+ atomic_goal_is_call(AtomicGoal, IsCall),
+ (
+ IsCall = atomic_goal_is_trivial,
+ (
+ VarUseType = var_use_consumption,
+ CostUntilUse = 0.0
+ ;
+ ( VarUseType = var_use_production
+ ; VarUseType = var_use_other
+ ),
+ CostUntilUse = 1.0
+ ),
+ LazyUse = val(var_use_info(CostUntilUse, 1.0, VarUseType))
+ ;
+ IsCall = atomic_goal_is_call(Args),
+ LazyUse = delay(
+ (func) = compute_var_use_lazy(Info, RevGoalPathSteps, Var,
+ Args, VarUseType))
+ ),
+ svmap.det_insert(Var, LazyUse, !Map).
+
+:- func compute_var_use_lazy(implicit_parallelism_info, list(goal_path_step),
+ var_rep, list(var_rep), var_use_type) = var_use_info.
+
+compute_var_use_lazy(Info, RevGoalPathSteps, Var, Args, VarUseType) = Use :-
+ CliquePtr = Info ^ ipi_clique,
+ RevGoalPath = rgp(RevGoalPathSteps),
+ map.lookup(Info ^ ipi_call_sites, RevGoalPath, CostAndCallee),
+ (
+ cost_and_callees_is_recursive(CliquePtr, CostAndCallee),
+ map.search(Info ^ ipi_rec_call_sites, RevGoalPath, RecCost)
+ ->
+ Cost = RecCost
+ ;
+ Cost = CostAndCallee ^ cac_cost
+ ),
+
+ solutions(
+ compute_var_use_lazy_arg(Info, Var, Args, CostAndCallee,
+ Cost, VarUseType),
+ Uses),
+ (
+ VarUseType = var_use_consumption,
+ Uses = [FirstUse | OtherUses],
+ list.foldl(earliest_use, OtherUses, FirstUse, Use)
+ ;
+ ( VarUseType = var_use_production
+ ; VarUseType = var_use_other
+ ),
+ (
+ Uses = [Use]
+ ;
+ Uses = [_, _ | _],
+ unexpected($module, $pred, "Too many solutions ")
+ )
+ ).
+
+:- pred earliest_use(var_use_info::in, var_use_info::in, var_use_info::out)
+ is det.
+
+earliest_use(A, B, Ealiest) :-
+ TimeA = A ^ vui_cost_until_use,
+ TimeB = B ^ vui_cost_until_use,
+ ( TimeA < TimeB ->
+ Ealiest = A
+ ;
+ Ealiest = B
+ ).
+
+:- pred compute_var_use_lazy_arg(implicit_parallelism_info::in, var_rep::in,
+ list(var_rep)::in, cost_and_callees::in, cs_cost_csq::in, var_use_type::in,
+ var_use_info::out) is multi.
+
+compute_var_use_lazy_arg(Info, Var, Args, CostAndCallee, Cost, VarUseType,
+ Use) :-
+ ( 0.0 < cs_cost_get_calls(Cost) ->
+ CostPercall = cs_cost_get_percall(Cost),
+ ( list.member_index0(Var, Args, ArgNum) ->
+ HigherOrder = CostAndCallee ^ cac_call_site_is_ho,
+ (
+ HigherOrder = higher_order_call,
+ % We cannot push signals or waits into higher order calls.
+ pessimistic_var_use_info(VarUseType, CostPercall, Use)
+ ;
+ HigherOrder = first_order_call,
+ ( singleton_set(CostAndCallee ^ cac_callees, CalleePrime) ->
+ Callee = CalleePrime
+ ;
+ unexpected($module, $pred,
+ "first-order call site has wrong number of CSDs")
+ ),
+ CSDPtr = Callee ^ c_csd,
+ RecursionType = Info ^ ipi_recursion_type,
+ recursion_type_get_interesting_parallelisation_depth(
+ RecursionType, MaybeCurDepth),
+ compute_var_use_2(Info, ArgNum, RecursionType, MaybeCurDepth,
+ VarUseType, CostPercall, CSDPtr, Use, Messages),
+ trace [io(!IO)] (
+ stderr_stream(Stderr, !IO),
+ write_out_messages(Stderr, Messages, !IO)
+ )
+ )
+ ;
+ Use = var_use_info(0.0, CostPercall, VarUseType),
+ ( VarUseType = var_use_consumption ->
+ true
+ ;
+ unexpected($module, $pred,
+ "Var use type most be consumption if " ++
+ "\\+ member(Var, Args)")
+ )
+ )
+ ;
+ % This call site is never called.
+ pessimistic_var_use_info(VarUseType, 0.0, Use)
+ ).
+
+:- pred compute_var_use_2(implicit_parallelism_info::in, int::in,
+ recursion_type::in, maybe(recursion_depth)::in, var_use_type::in,
+ float::in, call_site_dynamic_ptr::in, var_use_info::out,
+ cord(message)::out) is det.
+
+compute_var_use_2(Info, ArgNum, RecursionType, MaybeCurDepth, VarUseType, Cost,
+ CSDPtr, Use, !:Messages) :-
+ !:Messages = empty,
+ Deep = Info ^ ipi_deep,
+ CliquePtr = Info ^ ipi_clique,
+ implicit_par_info_intermodule_var_use(Info, FollowCallsAcrossModules),
+ VarUseOptions = var_use_options(Deep, FollowCallsAcrossModules,
+ VarUseType),
+ call_site_dynamic_var_use_info(CliquePtr, CSDPtr, ArgNum,
+ RecursionType, MaybeCurDepth, Cost, set.init, VarUseOptions, MaybeUse),
+ (
+ MaybeUse = ok(Use)
+ ;
+ MaybeUse = error(Error),
+ pessimistic_var_use_info(VarUseType, Cost, Use),
+ append_message(pl_csd(CSDPtr),
+ warning_cannot_compute_first_use_time(Error),
+ !Messages)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+implicit_par_info_intermodule_var_use(Info, FollowCallsAcrossModules) :-
+ IntermoduleVarUse = Info ^ ipi_opts ^ cpcp_intermodule_var_use,
+ (
+ IntermoduleVarUse = yes,
+ FollowCallsAcrossModules = follow_any_call
+ ;
+ IntermoduleVarUse = no,
+ ProcLabel = Info ^ ipi_proc_label,
+ ( ProcLabel = str_ordinary_proc_label(_, _, Module, _, _, _)
+ ; ProcLabel = str_special_proc_label(_, _, Module, _, _, _)
+ ),
+ FollowCallsAcrossModules = follow_calls_into_module(Module)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+recursion_type_get_interesting_parallelisation_depth(RecursionType,
+ MaybeDepth) :-
+ (
+ RecursionType = rt_not_recursive,
+ MaybeDepth = yes(recursion_depth_from_float(0.0))
+ ;
+ RecursionType = rt_single(_, _, _DepthF, _, _),
+ % The interesting recursion depth is at the bottom of the recursion, if
+ % we can't parallelise here then there's no point parallelising the
+ % loop in general.
+ % XXX: Update metrics to understand that this is a loop.
+ MaybeDepth = yes(recursion_depth_from_float(2.0))
+ ;
+ ( RecursionType = rt_divide_and_conquer(_, _)
+ ; RecursionType = rt_mutual_recursion(_)
+ ; RecursionType = rt_other(_)
+ ; RecursionType = rt_errors(_)
+ ),
+ MaybeDepth = no
+ ).
+
+%-----------------------------------------------------------------------------%
Index: deep_profiler/autopar_find_best_par.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/autopar_find_best_par.m,v
retrieving revision 1.1
diff -u -b -r1.1 autopar_find_best_par.m
--- deep_profiler/autopar_find_best_par.m 27 Jan 2011 02:53:46 -0000 1.1
+++ deep_profiler/autopar_find_best_par.m 27 Jan 2011 05:17:23 -0000
@@ -1,7 +1,7 @@
%-----------------------------------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%-----------------------------------------------------------------------------%
-% Copyright (C) 2006-2011 The University of Melbourne.
+% Copyright (C) 2011 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -17,11 +17,11 @@
:- module mdprof_fb.automatic_parallelism.autopar_find_best_par.
:- interface.
-:- import_module message.
:- import_module mdbcomp.
:- import_module mdbcomp.feedback.
:- import_module mdbcomp.feedback.automatic_parallelism.
:- import_module mdprof_fb.automatic_parallelism.autopar_types.
+:- import_module message.
:- import_module cord.
:- import_module list.
@@ -46,36 +46,20 @@
:- implementation.
-% XXX temporary only
-:- import_module mdprof_fb.automatic_parallelism.autopar_search_callgraph.
-
-:- import_module analysis_utils.
:- import_module branch_and_bound.
-:- import_module coverage.
-:- import_module create_report.
-:- import_module mdbcomp.goal_path.
:- import_module mdbcomp.program_representation.
-:- import_module measurement_units.
+:- import_module mdprof_fb.automatic_parallelism.autopar_calc_overlap.
+:- import_module mdprof_fb.automatic_parallelism.autopar_search_goals. % XXX
:- import_module measurements.
-:- import_module program_representation_utils.
-:- import_module recursion_patterns.
-:- import_module report.
-:- import_module solutions.
-:- import_module var_use_analysis.
:- import_module array.
-:- import_module assoc_list.
-:- import_module bool.
:- import_module digraph.
:- import_module float.
:- import_module io.
:- import_module int.
-:- import_module lazy.
:- import_module map.
-:- import_module pair.
:- import_module require.
:- import_module set.
-:- import_module std_util.
:- import_module string.
:- import_module svmap.
Index: deep_profiler/autopar_reports.m
===================================================================
RCS file: deep_profiler/autopar_reports.m
diff -N deep_profiler/autopar_reports.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ deep_profiler/autopar_reports.m 27 Jan 2011 05:18:58 -0000
@@ -0,0 +1,336 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2011 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: autopar_reports.m
+% Author: pbone.
+%
+% This module contains code for creating reports for debugging.
+%
+%-----------------------------------------------------------------------------%
+
+:- module mdprof_fb.automatic_parallelism.autopar_reports.
+:- interface.
+
+:- import_module mdbcomp.
+:- import_module mdbcomp.feedback.
+:- import_module mdbcomp.feedback.automatic_parallelism.
+:- import_module mdbcomp.program_representation.
+
+:- import_module cord.
+:- import_module pair.
+
+:- pred create_candidate_parallel_conj_proc_report(
+ pair(string_proc_label, candidate_par_conjunctions_proc)::in,
+ cord(string)::out) is det.
+
+:- pred create_candidate_parallel_conj_report(var_table::in,
+ candidate_par_conjunction(pard_goal)::in, cord(string)::out) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module mdbcomp.goal_path.
+:- import_module measurement_units.
+:- import_module message.
+:- import_module program_representation_utils.
+
+:- import_module assoc_list.
+:- import_module float.
+:- import_module int.
+:- import_module list.
+:- import_module maybe.
+:- import_module require.
+:- import_module set.
+:- import_module std_util.
+:- import_module string.
+
+%----------------------------------------------------------------------------%
+
+create_candidate_parallel_conj_proc_report(Proc - CandidateParConjunctionProc,
+ Report) :-
+ CandidateParConjunctionProc = candidate_par_conjunctions_proc(VarTable,
+ PushGoals, CandidateParConjunctions),
+ print_proc_label_to_string(Proc, ProcString),
+ list.map(create_push_goal_report, PushGoals, PushGoalReports),
+ list.map(create_candidate_parallel_conj_report(VarTable),
+ CandidateParConjunctions, CandidateParConjunctionReports),
+ Header = string.format(
+ " %s\n",
+ [s(ProcString)]),
+ Report = cord.singleton(Header) ++
+ cord_list_to_cord(PushGoalReports) ++
+ cord.singleton("\n") ++
+ cord_list_to_cord(CandidateParConjunctionReports).
+
+:- pred create_push_goal_report(push_goal::in, cord(string)::out) is det.
+
+create_push_goal_report(PushGoal, Report) :-
+ PushGoal = push_goal(PushGoalPathStr, Lo, Hi, PushedGoalPathStrs),
+ string.format("\n PushGoal: %s, lo %d, hi %d\n",
+ [s(PushGoalPathStr), i(Lo), i(Hi)], HeadPushGoalStr),
+ FormatPushedGoals = (
+ func(PushedGoalPathStr) =
+ string.format(" %s\n", [s(PushedGoalPathStr)])
+ ),
+ TailPushGoalStrs = list.map(FormatPushedGoals, PushedGoalPathStrs),
+ Report = cord.from_list([HeadPushGoalStr | TailPushGoalStrs]).
+
+create_candidate_parallel_conj_report(VarTable, CandidateParConjunction,
+ Report) :-
+ CandidateParConjunction = candidate_par_conjunction(GoalPathString,
+ MaybePushGoal, FirstConjNum, IsDependent, GoalsBefore, GoalsBeforeCost,
+ Conjs, GoalsAfter, GoalsAfterCost, ParExecMetrics),
+ ParExecMetrics = parallel_exec_metrics(NumCalls, SeqTime, ParTime,
+ SparkCost, BarrierCost, SignalsCost, WaitsCost, FirstConjDeadTime,
+ FutureDeadTime),
+ ParOverheads = parallel_exec_metrics_get_overheads(ParExecMetrics),
+ (
+ IsDependent = conjuncts_are_independent,
+ DependanceString = "no"
+ ;
+ IsDependent = conjuncts_are_dependent(Vars),
+ map(lookup_var_name(VarTable), Vars, VarNames),
+ VarsString = join_list(", ", to_sorted_list(VarNames)),
+ DependanceString = format("on %s", [s(VarsString)])
+ ),
+ Speedup = parallel_exec_metrics_get_speedup(ParExecMetrics),
+ TimeSaving = parallel_exec_metrics_get_time_saving(ParExecMetrics),
+ TotalDeadTime = FirstConjDeadTime + FutureDeadTime,
+
+ string.format(
+ " Path: %s\n",
+ [s(GoalPathString)], Header1Str),
+ Header1 = cord.singleton(Header1Str),
+
+ (
+ MaybePushGoal = no,
+ Header2 = cord.empty
+ ;
+ MaybePushGoal = yes(PushGoal),
+ PushGoal = push_goal(PushGoalPathStr, Lo, Hi, PushedGoalPathStrs),
+ string.format(" PushGoal: %s, lo %d, hi %d\n",
+ [s(PushGoalPathStr), i(Lo), i(Hi)], HeadPushGoalStr),
+ FormatPushedGoals = (
+ func(PushedGoalPathStr) =
+ string.format(" %s\n", [s(PushedGoalPathStr)])
+ ),
+ TailPushGoalStrs = list.map(FormatPushedGoals, PushedGoalPathStrs),
+ Header2 = cord.from_list([HeadPushGoalStr | TailPushGoalStrs])
+ ),
+
+ string.format(
+ " Dependent: %s\n" ++
+ " NumCalls: %s\n" ++
+ " SeqTime: %s\n" ++
+ " ParTime: %s\n" ++
+ " SparkCost: %s\n" ++
+ " BarrierCost: %s\n" ++
+ " SignalsCost: %s\n" ++
+ " WaitsCost: %s\n" ++
+ " ParOverheads total: %s\n" ++
+ " Speedup: %s\n" ++
+ " Time saving: %s\n" ++
+ " First conj dead time: %s\n" ++
+ " Future dead time: %s\n" ++
+ " Total dead time: %s\n\n",
+ [s(DependanceString),
+ s(commas(NumCalls)),
+ s(two_decimal_fraction(SeqTime)),
+ s(two_decimal_fraction(ParTime)),
+ s(two_decimal_fraction(SparkCost)),
+ s(two_decimal_fraction(BarrierCost)),
+ s(two_decimal_fraction(SignalsCost)),
+ s(two_decimal_fraction(WaitsCost)),
+ s(two_decimal_fraction(ParOverheads)),
+ s(four_decimal_fraction(Speedup)),
+ s(two_decimal_fraction(TimeSaving)),
+ s(two_decimal_fraction(FirstConjDeadTime)),
+ s(two_decimal_fraction(FutureDeadTime)),
+ s(two_decimal_fraction(TotalDeadTime))],
+ Header2Str),
+ Header3 = cord.singleton(Header2Str),
+
+ ( rev_goal_path_from_string(GoalPathString, RevGoalPath) ->
+ RevGoalPath = rgp(RevGoalPathSteps)
+ ;
+ unexpected($module, $pred, "couldn't parse goal path")
+ ),
+ some [!ConjNum] (
+ !:ConjNum = FirstConjNum,
+ format_sequential_conjunction(VarTable, 4, RevGoalPathSteps,
+ GoalsBefore, GoalsBeforeCost, !.ConjNum, ReportGoalsBefore0),
+ ReportGoalsBefore = indent(3) ++ singleton("Goals before:\n") ++
+ ReportGoalsBefore0,
+
+ !:ConjNum = !.ConjNum + length(GoalsBefore),
+ format_parallel_conjunction(VarTable, 4, RevGoalPathSteps,
+ !.ConjNum, Conjs, ReportParConj0),
+ ReportParConj = indent(3) ++ singleton("Parallel conjunction:\n") ++
+ ReportParConj0,
+
+ !:ConjNum = !.ConjNum + 1,
+ format_sequential_conjunction(VarTable, 4, RevGoalPathSteps,
+ GoalsAfter, GoalsAfterCost, !.ConjNum, ReportGoalsAfter0),
+ ReportGoalsAfter = indent(3) ++ singleton("Goals after:\n") ++
+ ReportGoalsAfter0
+ ),
+ Report = Header1 ++ Header2 ++ Header3 ++ ReportGoalsBefore ++ nl
+ ++ ReportParConj ++ nl ++ ReportGoalsAfter ++ nl.
+
+:- pred format_parallel_conjunction(var_table::in, int::in,
+ list(goal_path_step)::in, int::in,
+ list(seq_conj(pard_goal))::in, cord(string)::out) is det.
+
+format_parallel_conjunction(VarTable, Indent, RevGoalPathSteps, ConjNum, Conjs,
+ !:Report) :-
+ IndentStr = indent(Indent),
+ !:Report = IndentStr ++ singleton("(\n"),
+ format_parallel_conjuncts(VarTable, Indent,
+ [step_conj(ConjNum) | RevGoalPathSteps], 1, Conjs, !Report).
+
+:- pred format_parallel_conjuncts(var_table::in, int::in,
+ list(goal_path_step)::in, int::in, list(seq_conj(pard_goal))::in,
+ cord(string)::in, cord(string)::out) is det.
+
+format_parallel_conjuncts(_VarTable, Indent, _RevGoalPathSteps, _ConjNum0,
+ [], !Report) :-
+ IndentStr = indent(Indent),
+ !:Report = snoc(!.Report ++ IndentStr, ")\n").
+format_parallel_conjuncts(VarTable, Indent, RevGoalPathSteps, ConjNum0,
+ [Conj | Conjs], !Report) :-
+ Conj = seq_conj(Goals),
+ (
+ Goals = [],
+ unexpected($module, $pred, "empty conjunct in parallel conjunction")
+ ;
+ Goals = [Goal | GoalsTail],
+ RevInnerGoalPathSteps = [step_conj(ConjNum0) | RevGoalPathSteps],
+ (
+ GoalsTail = [],
+ % A singleton conjunction gets printed as a single goal.
+ print_goal_to_strings(print_goal_info(id, VarTable), Indent + 1,
+ RevInnerGoalPathSteps, Goal, ConjReport)
+ ;
+ GoalsTail = [_ | _],
+ Cost = foldl(
+ (func(GoalI, Acc) =
+ Acc + GoalI ^ goal_annotation ^ pga_cost_percall),
+ Goals, 0.0),
+ format_sequential_conjunction(VarTable, Indent + 1,
+ RevInnerGoalPathSteps, Goals, Cost, 1, ConjReport)
+ )
+ ),
+ !:Report = !.Report ++ ConjReport,
+ (
+ Conjs = []
+ ;
+ Conjs = [_ | _],
+ !:Report = snoc(!.Report ++ indent(Indent), "&\n")
+ ),
+ ConjNum = ConjNum0 + 1,
+ format_parallel_conjuncts(VarTable, Indent, RevGoalPathSteps, ConjNum,
+ Conjs, !Report).
+
+:- pred format_sequential_conjunction(var_table::in, int::in,
+ list(goal_path_step)::in, list(pard_goal)::in, float::in, int::in,
+ cord(string)::out) is det.
+
+format_sequential_conjunction(VarTable, Indent, RevGoalPathSteps, Goals, Cost,
+ FirstConjNum, !:Report) :-
+ !:Report = empty,
+ ( FirstConjNum = 1 ->
+ !:Report = !.Report ++
+ indent(Indent) ++
+ singleton(format("%% conjunction: %s",
+ [s(rev_goal_path_to_string(rgp(RevGoalPathSteps)))])) ++
+ nl_indent(Indent) ++
+ singleton(format("%% Cost: %s",
+ [s(two_decimal_fraction(Cost))])) ++
+ nl ++ nl
+ ;
+ true
+ ),
+ format_sequential_conjuncts(VarTable, Indent, RevGoalPathSteps, Goals,
+ FirstConjNum, _, !Report).
+
+:- pred format_sequential_conjuncts(var_table::in, int::in,
+ list(goal_path_step)::in, list(pard_goal)::in, int::in, int::out,
+ cord(string)::in, cord(string)::out) is det.
+
+format_sequential_conjuncts(_, _, _, [], !ConjNum, !Report).
+format_sequential_conjuncts(VarTable, Indent, RevGoalPathSteps, [Conj | Conjs],
+ !ConjNum, !Report) :-
+ print_goal_to_strings(print_goal_info(id, VarTable), Indent,
+ [step_conj(!.ConjNum) | RevGoalPathSteps], Conj, ConjReport),
+ !:Report = !.Report ++ ConjReport,
+ !:ConjNum = !.ConjNum + 1,
+ (
+ Conjs = []
+ ;
+ Conjs = [_ | _],
+ !:Report = !.Report ++ indent(Indent) ++ singleton(",\n"),
+ format_sequential_conjuncts(VarTable, Indent, RevGoalPathSteps, Conjs,
+ !ConjNum, !Report)
+ ).
+
+:- instance goal_annotation(pard_goal_annotation) where [
+ pred(print_goal_annotation_to_strings/3) is format_pard_goal_annotation
+].
+
+:- pred format_pard_goal_annotation(var_table::in, pard_goal_annotation::in,
+ cord(cord(string))::out) is det.
+
+format_pard_goal_annotation(VarTable, GoalAnnotation, Report) :-
+ GoalAnnotation = pard_goal_annotation(CostPercall, CostAboveThreshold,
+ Productions, Consumptions),
+ (
+ CostAboveThreshold = cost_above_par_threshold,
+ CostAboveThresholdStr = "above threshold"
+ ;
+ CostAboveThreshold = cost_not_above_par_threshold,
+ CostAboveThresholdStr = "not above threshold"
+ ),
+ CostLine = singleton(format("cost: %s (%s)",
+ [s(two_decimal_fraction(CostPercall)), s(CostAboveThresholdStr)])),
+ format_var_use_report(VarTable, productions, Productions,
+ ProductionsReport),
+ format_var_use_report(VarTable, consumptions, Consumptions,
+ ConsumptionsReport),
+ Report = singleton(CostLine) ++ ProductionsReport ++ ConsumptionsReport.
+
+:- func productions = string.
+
+productions = "Productions".
+
+:- func consumptions = string.
+
+consumptions = "Consumptions".
+
+:- pred format_var_use_report(var_table::in, string::in,
+ assoc_list(var_rep, float)::in, cord(cord(string))::out) is det.
+
+format_var_use_report(VarTable, Label, List, Report) :-
+ (
+ List = [_ | _],
+ list.map(format_var_use_line(VarTable), List, Lines),
+ Report = singleton(singleton(Label ++ ":")) ++ cord.from_list(Lines)
+ ;
+ List = [],
+ Report = empty
+ ).
+
+:- pred format_var_use_line(var_table::in, pair(var_rep, float)::in,
+ cord(string)::out) is det.
+
+format_var_use_line(VarTable, Var - Use, singleton(String)) :-
+ format(" %s: %s", [s(VarName), s(two_decimal_fraction(Use))], String),
+ lookup_var_name(VarTable, Var, VarName).
+
+%-----------------------------------------------------------------------------%
Index: deep_profiler/autopar_search_callgraph.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/autopar_search_callgraph.m,v
retrieving revision 1.2
diff -u -b -r1.2 autopar_search_callgraph.m
--- deep_profiler/autopar_search_callgraph.m 27 Jan 2011 03:05:04 -0000 1.2
+++ deep_profiler/autopar_search_callgraph.m 27 Jan 2011 05:20:11 -0000
@@ -1,7 +1,7 @@
%-----------------------------------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%-----------------------------------------------------------------------------%
-% Copyright (C) 2006-2011 The University of Melbourne.
+% Copyright (C) 2011 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -18,16 +18,14 @@
:- module mdprof_fb.automatic_parallelism.autopar_search_callgraph.
:- interface.
-:- import_module profile.
-:- import_module message.
:- import_module mdbcomp.
:- import_module mdbcomp.feedback.
:- import_module mdbcomp.feedback.automatic_parallelism.
-:- import_module mdbcomp.program_representation.
:- import_module mdprof_fb.automatic_parallelism.autopar_types.
+:- import_module message.
+:- import_module profile.
:- import_module cord.
-:- import_module pair.
%-----------------------------------------------------------------------------%
@@ -40,64 +38,44 @@
%-----------------------------------------------------------------------------%
-:- pred create_candidate_parallel_conj_proc_report(
- pair(string_proc_label, candidate_par_conjunctions_proc)::in,
- cord(string)::out) is det.
-
-%-----------------------------------------------------------------------------%
-
-% XXX temporary exports.
-
- % Check if it is appropriate to parallelise this call. That is it must be
- % model_det and have a cost above the call site cost threshold.
- %
-:- pred can_parallelise_goal(goal_rep(T)::in) is semidet.
+% XXX temporary exports
- % calculate_parallel_cost(Info, !Parallelisation).
- %
- % Analyse the parallel conjuncts and determine their likely performance.
- %
- % This is the new parallel execution overlap algorithm, it is general and
- % therefore we also use is for independent conjunctions.
- %
-:- pred calculate_parallel_cost(parallelisation_cost_data::out,
- incomplete_parallelisation::in, incomplete_parallelisation::out) is det.
+:- pred pard_goal_detail_to_pard_goal(
+ candidate_par_conjunction(pard_goal_detail)::in,
+ pard_goal_detail::in, pard_goal::out) is det.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
:- implementation.
-:- import_module mdprof_fb.automatic_parallelism.autopar_annotate.
-:- import_module mdprof_fb.automatic_parallelism.autopar_find_best_par.
-
:- import_module analysis_utils.
-:- import_module branch_and_bound.
:- import_module coverage.
-:- import_module create_report.
:- import_module mdbcomp.goal_path.
+:- import_module mdbcomp.program_representation.
+:- import_module mdprof_fb.automatic_parallelism.autopar_annotate.
+:- import_module mdprof_fb.automatic_parallelism.autopar_costs.
+:- import_module mdprof_fb.automatic_parallelism.autopar_search_goals.
:- import_module measurement_units.
:- import_module measurements.
:- import_module program_representation_utils.
:- import_module recursion_patterns.
:- import_module report.
-:- import_module solutions.
:- import_module var_use_analysis.
+:- import_module pair.
+:- import_module list.
:- import_module array.
:- import_module assoc_list.
:- import_module bool.
-:- import_module digraph.
:- import_module float.
:- import_module io.
:- import_module int.
:- import_module lazy.
-:- import_module list.
:- import_module map.
:- import_module maybe.
:- import_module require.
:- import_module set.
-:- import_module std_util.
:- import_module string.
:- import_module svmap.
@@ -135,10 +113,6 @@
ConjunctionsAssocList),
put_feedback_data(CandidateParallelConjunctions, !Feedback).
-:- pred pard_goal_detail_to_pard_goal(
- candidate_par_conjunction(pard_goal_detail)::in,
- pard_goal_detail::in, pard_goal::out) is det.
-
pard_goal_detail_to_pard_goal(CPC, !Goal) :-
IsDependent = CPC ^ cpc_is_dependent,
(
@@ -700,1304 +674,6 @@
CPCs),
svmap.set(ProcLabel, CandidateProc, !Map).
-:- pred goal_get_conjunctions_worth_parallelising(
- implicit_parallelism_info::in, list(goal_path_step)::in,
- pard_goal_detail::in, pard_goal_detail::out,
- cord(candidate_par_conjunction(pard_goal_detail))::out,
- cord(push_goal)::out, cord(pard_goal_detail)::out, cord(message)::out)
- is det.
-
-goal_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
- !Goal, Candidates, Pushes, Singles, Messages) :-
- !.Goal = goal_rep(GoalExpr0, DetismRep, Annotation0),
- Coverage = Annotation0 ^ pgd_coverage,
- get_coverage_before_det(Coverage, Calls),
- (
- (
- GoalExpr0 = conj_rep(Conjs0),
- conj_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
- Conjs0, Conjs, 1, [], SinglesSoFar, [], RevSingleCands,
- cord.empty, CandidatesBelow, cord.empty, PushesBelow,
- cord.empty, MessagesBelow),
- GoalExpr = conj_rep(Conjs),
- list.reverse(RevSingleCands, SingleCands),
- (
- SingleCands = [],
- Candidates = CandidatesBelow,
- Pushes = PushesBelow,
- Singles = cord.from_list(SinglesSoFar),
- Messages = MessagesBelow,
- Cost = Annotation0 ^ pgd_cost
- ;
- SingleCands = [CostlyIndex - SinglesBefore],
- push_and_build_candidate_conjunctions(Info, RevGoalPathSteps,
- Conjs, CostlyIndex, SinglesBefore,
- MessagesThisLevel, CandidatesThisLevel),
- (
- CandidatesThisLevel = [],
- Candidates = CandidatesBelow,
- Pushes = PushesBelow,
- % No candidate was built, pass our singles to our caller.
- Singles = cord.from_list(SinglesSoFar)
- ;
- CandidatesThisLevel = [FirstCandidate | LaterCandidates],
- merge_same_level_pushes(FirstCandidate, LaterCandidates,
- PushThisLevel),
- Candidates = CandidatesBelow ++
- cord.from_list(CandidatesThisLevel),
- Pushes = cord.snoc(PushesBelow, PushThisLevel),
- % Any single expensive goals inside this conjunction
- % cannot have later expensive goals pushed next to them
- % without reanalysis of the whole goal, which we do not do.
- Singles = cord.empty
- ),
- Messages = MessagesBelow ++ MessagesThisLevel,
- % XXX We should update the cost for CandidatesThisLevel.
- Cost = Annotation0 ^ pgd_cost
- ;
- SingleCands = [_, _ | _],
- assoc_list.keys(SingleCands, CostlyIndexes),
- build_candidate_conjunction(Info, RevGoalPathSteps,
- Conjs, CostlyIndexes, MessagesThisLevel, MaybeCandidate),
- Pushes = PushesBelow,
- Messages = MessagesBelow ++ MessagesThisLevel,
- (
- MaybeCandidate = yes(Candidate),
- Candidates = cord.cons(Candidate, CandidatesBelow),
- ExecMetrics = Candidate ^ cpc_par_exec_metrics,
- Cost = call_goal_cost(ExecMetrics ^ pem_num_calls,
- ExecMetrics ^ pem_par_time),
- % We parallelized this conjunction. Trying to push a goal
- % after it next to a costly goal inside it would require
- % pushing that following goal into a conjunct of this
- % parallel conjunction. Due to our current prohibition
- % on reordering, that costly goal would have to be inside
- % the last parallel conjunct. That would require replacing
- % Candidate with another candidate that includes the
- % following goal. While that is in theory doable, it is not
- % doable *here*, since at this point yet know whether
- % a following costly goal even exists. On the other hand,
- % any later part of this algorithm that does discover
- % a later costly goal won't know how to redo this overlap
- % calculation. We avoid the problem by pretending that this
- % conjunction contains no expensive goals.
- Singles = cord.empty
- ;
- MaybeCandidate = no,
- Candidates = CandidatesBelow,
- Singles = cord.from_list(SinglesSoFar),
- Cost = Annotation0 ^ pgd_cost
- )
- )
- ;
- GoalExpr0 = disj_rep(Disjs0),
- list.map_foldl5(
- disj_get_conjunctions_worth_parallelising(Info,
- RevGoalPathSteps),
- Disjs0, Disjs, 1, _, cord.empty, Candidates,
- cord.empty, Pushes, cord.empty, Singles,
- cord.empty, Messages),
- disj_calc_cost(Disjs, Calls, Cost),
- GoalExpr = disj_rep(Disjs)
- ;
- GoalExpr0 = switch_rep(Var, CanFail, Cases0),
- list.map_foldl5(
- switch_case_get_conjunctions_worth_parallelising(Info,
- RevGoalPathSteps),
- Cases0, Cases, 1, _, cord.empty, Candidates,
- cord.empty, Pushes, cord.empty, Singles,
- cord.empty, Messages),
- switch_calc_cost(Cases, Calls, Cost),
- GoalExpr = switch_rep(Var, CanFail, Cases)
- ;
- GoalExpr0 = ite_rep(Cond0, Then0, Else0),
- ite_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
- Cond0, Cond, Then0, Then, Else0, Else,
- Candidates, Pushes, Singles, Messages),
- ite_calc_cost(Cond, Then, Else, Cost),
- GoalExpr = ite_rep(Cond, Then, Else)
- ;
- GoalExpr0 = scope_rep(SubGoal0, MaybeCut),
- RevSubGoalPathSteps = [step_scope(MaybeCut) | RevGoalPathSteps],
- goal_get_conjunctions_worth_parallelising(Info,
- RevSubGoalPathSteps, SubGoal0, SubGoal,
- Candidates, Pushes, Singles, Messages),
- Cost = SubGoal ^ goal_annotation ^ pgd_cost,
- GoalExpr = scope_rep(SubGoal, MaybeCut)
- ;
- GoalExpr0 = negation_rep(SubGoal0),
- RevSubGoalPathSteps = [step_neg | RevGoalPathSteps],
- % We ignore _Singles here because you cannot push goals
- % after a negation into the negation.
- goal_get_conjunctions_worth_parallelising(Info,
- RevSubGoalPathSteps, SubGoal0, SubGoal,
- Candidates, Pushes, _Singles, Messages),
- Singles = cord.empty,
- Cost = SubGoal ^ goal_annotation ^ pgd_cost,
- GoalExpr = negation_rep(SubGoal)
- ),
- Annotation = Annotation0 ^ pgd_cost := Cost
- ;
- GoalExpr0 = atomic_goal_rep(_, _, _, _),
- identify_costly_goal(Annotation0, Costly),
- (
- Costly = is_costly_goal,
- Singles = cord.singleton(!.Goal)
- ;
- Costly = is_not_costly_goal,
- Singles = cord.empty
- ),
- Candidates = cord.empty,
- Pushes = cord.empty,
- Messages = cord.empty,
- GoalExpr = GoalExpr0,
- Annotation = Annotation0
- ),
- !:Goal = goal_rep(GoalExpr, DetismRep, Annotation).
-
-:- pred disj_get_conjunctions_worth_parallelising(
- implicit_parallelism_info::in, list(goal_path_step)::in,
- pard_goal_detail::in, pard_goal_detail::out,
- int::in, int::out,
- cord(candidate_par_conjunction(pard_goal_detail))::in,
- cord(candidate_par_conjunction(pard_goal_detail))::out,
- cord(push_goal)::in, cord(push_goal)::out,
- cord(pard_goal_detail)::in, cord(pard_goal_detail)::out,
- cord(message)::in, cord(message)::out) is det.
-
-disj_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
- !Disj, !DisjNum, !Candidates, !Pushes, !Singles, !Messages) :-
- RevDisjGoalPathSteps = [step_disj(!.DisjNum) | RevGoalPathSteps],
- goal_get_conjunctions_worth_parallelising(Info, RevDisjGoalPathSteps,
- !Disj, Candidates, Pushes, Singles, Messages),
- !:Candidates = !.Candidates ++ Candidates,
- !:Pushes = !.Pushes ++ Pushes,
- !:Singles = !.Singles ++ Singles,
- !:Messages = !.Messages ++ Messages,
- !:DisjNum = !.DisjNum + 1.
-
-:- pred switch_case_get_conjunctions_worth_parallelising(
- implicit_parallelism_info::in, list(goal_path_step)::in,
- case_rep(pard_goal_detail_annotation)::in,
- case_rep(pard_goal_detail_annotation)::out,
- int::in, int::out,
- cord(candidate_par_conjunction(pard_goal_detail))::in,
- cord(candidate_par_conjunction(pard_goal_detail))::out,
- cord(push_goal)::in, cord(push_goal)::out,
- cord(pard_goal_detail)::in, cord(pard_goal_detail)::out,
- cord(message)::in, cord(message)::out) is det.
-
-switch_case_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps, !Case,
- !CaseNum, !Candidates, !Pushes, !Singles, !Messages) :-
- !.Case = case_rep(MainConsIdRep, OtherConsIdReps, Goal0),
- RevCaseGoalPathSteps = [step_switch(!.CaseNum, no) | RevGoalPathSteps],
- goal_get_conjunctions_worth_parallelising(Info, RevCaseGoalPathSteps,
- Goal0, Goal, Candidates, Pushes, Singles, Messages),
- !:Case = case_rep(MainConsIdRep, OtherConsIdReps, Goal),
- !:Candidates = !.Candidates ++ Candidates,
- !:Pushes = !.Pushes ++ Pushes,
- !:Singles = !.Singles ++ Singles,
- !:Messages = !.Messages ++ Messages,
- !:CaseNum = !.CaseNum + 1.
-
-:- pred ite_get_conjunctions_worth_parallelising(
- implicit_parallelism_info::in, list(goal_path_step)::in,
- pard_goal_detail::in, pard_goal_detail::out,
- pard_goal_detail::in, pard_goal_detail::out,
- pard_goal_detail::in, pard_goal_detail::out,
- cord(candidate_par_conjunction(pard_goal_detail))::out,
- cord(push_goal)::out, cord(pard_goal_detail)::out,
- cord(message)::out) is det.
-
-ite_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
- !Cond, !Then, !Else, Candidates, Pushes, Singles, Messages) :-
- RevCondGoalPathSteps = [step_ite_cond | RevGoalPathSteps],
- RevThenGoalPathSteps = [step_ite_then | RevGoalPathSteps],
- RevElseGoalPathSteps = [step_ite_else | RevGoalPathSteps],
- % We ignore _CondSingles here because you cannot push goals
- % following an if-then-else into the condition.
- goal_get_conjunctions_worth_parallelising(Info, RevCondGoalPathSteps,
- !Cond, CondCandidates, CondPushes, _CondSingles, CondMessages),
- goal_get_conjunctions_worth_parallelising(Info, RevThenGoalPathSteps,
- !Then, ThenCandidates, ThenPushes, ThenSingles, ThenMessages),
- goal_get_conjunctions_worth_parallelising(Info, RevElseGoalPathSteps,
- !Else, ElseCandidates, ElsePushes, ElseSingles, ElseMessages),
- Candidates = CondCandidates ++ ThenCandidates ++ ElseCandidates,
- Pushes = CondPushes ++ ThenPushes ++ ElsePushes,
- Singles = ThenSingles ++ ElseSingles,
- Messages = CondMessages ++ ThenMessages ++ ElseMessages.
-
-:- pred conj_get_conjunctions_worth_parallelising(
- implicit_parallelism_info::in, list(goal_path_step)::in,
- list(pard_goal_detail)::in, list(pard_goal_detail)::out, int::in,
- list(pard_goal_detail)::in, list(pard_goal_detail)::out,
- assoc_list(int, list(pard_goal_detail))::in,
- assoc_list(int, list(pard_goal_detail))::out,
- cord(candidate_par_conjunction(pard_goal_detail))::in,
- cord(candidate_par_conjunction(pard_goal_detail))::out,
- cord(push_goal)::in, cord(push_goal)::out,
- cord(message)::in, cord(message)::out) is det.
-
-conj_get_conjunctions_worth_parallelising(_Info, _RevGoalPathSteps,
- [], [], _ConjNum, !SinglesSoFar, !RevSingleCands,
- !CandidatesBelow, !Pushes, !MessagesBelow).
-conj_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
- [Conj0 | Conjs0], [Conj | Conjs], ConjNum, SinglesSoFar0, SinglesSoFar,
- !RevSingleCands, !CandidatesBelow, !Pushes, !MessagesBelow) :-
- RevConjGoalPathSteps = [step_conj(ConjNum) | RevGoalPathSteps],
- goal_get_conjunctions_worth_parallelising(Info, RevConjGoalPathSteps,
- Conj0, Conj, Candidates, Pushes, SinglesCord, Messages),
- Singles = cord.list(SinglesCord),
- !:CandidatesBelow = !.CandidatesBelow ++ Candidates,
- !:Pushes = !.Pushes ++ Pushes,
- !:MessagesBelow = !.MessagesBelow ++ Messages,
- identify_costly_goal(Conj ^ goal_annotation, Costly),
- (
- Costly = is_costly_goal,
- !:RevSingleCands = [ConjNum - SinglesSoFar0 | !.RevSingleCands],
- SinglesSoFar1 = Singles
- ;
- Costly = is_not_costly_goal,
- % This goal might be costly if it is pushed into the cotexted
- % of one of SinglesSoFar. This is common for recursive goals.
- filter(single_context_makes_goal_costly(Info, Conj), SinglesSoFar0,
- SinglesSoFarMakeConjCostly),
- (
- SinglesSoFarMakeConjCostly = []
- ;
- SinglesSoFarMakeConjCostly = [_ | _],
- !:RevSingleCands = [ConjNum - SinglesSoFarMakeConjCostly |
- !.RevSingleCands]
- ),
-
- (
- SinglesSoFar0 = [],
- Singles = [],
- SinglesSoFar1 = []
- ;
- SinglesSoFar0 = [_ | _],
- Singles = [],
- SinglesSoFar1 = SinglesSoFar0
- ;
- SinglesSoFar0 = [],
- Singles = [_ | _],
- SinglesSoFar1 = Singles
- ;
- SinglesSoFar0 = [_ | _],
- Singles = [_ | _],
- % XXX choose between SinglesSoFar0 and Singles, either on max cost
- % or total cost.
- SinglesSoFar1 = Singles
- )
- ),
- conj_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
- Conjs0, Conjs, ConjNum + 1, SinglesSoFar1, SinglesSoFar,
- !RevSingleCands, !CandidatesBelow, !Pushes, !MessagesBelow).
-
-:- pred single_context_makes_goal_costly(implicit_parallelism_info::in,
- pard_goal_detail::in, pard_goal_detail::in) is semidet.
-
-single_context_makes_goal_costly(Info, Goal, Single) :-
- SingleCost = Single ^ goal_annotation ^ pgd_cost,
- SingleCount = goal_cost_get_calls(SingleCost),
- fix_goal_counts(Info, SingleCount, Goal, ConjNewCounts),
- identify_costly_goal(ConjNewCounts ^ goal_annotation, is_costly_goal).
-
- % Given a conjunction with two or more costly goals (identified by
- % CostlyGoalsIndexes), check whether executing the conjunction in parallel
- % can yield a speedup.
- %
-:- pred build_candidate_conjunction(implicit_parallelism_info::in,
- list(goal_path_step)::in, list(pard_goal_detail)::in, list(int)::in,
- cord(message)::out,
- maybe(candidate_par_conjunction(pard_goal_detail))::out) is det.
-
-build_candidate_conjunction(Info, RevGoalPathSteps, Conjs, CostlyGoalsIndexes,
- !:Messages, MaybeCandidate) :-
- ProcLabel = Info ^ ipi_proc_label,
- !:Messages = cord.empty,
- NumCostlyGoals = list.length(CostlyGoalsIndexes),
- Location = pl_goal(ProcLabel, rgp(RevGoalPathSteps)),
- append_message(Location,
- info_found_conjs_above_callsite_threshold(NumCostlyGoals),
- !Messages),
-
- pardgoals_build_candidate_conjunction(Info, Location, RevGoalPathSteps, no,
- Conjs, MaybeCandidate, !Messages),
- (
- MaybeCandidate = yes(_Candidate),
- append_message(Location,
- info_found_n_conjunctions_with_positive_speedup(1),
- !Messages)
- ;
- MaybeCandidate = no
- ).
-
- % Given a conjunction one costly goal (identified by CostlyIndex) directly
- % in it and other costly goals SinglesBefore inside alternate execution
- % paths in an earlier conjunct (conjunct i < CostlyIndex), check whether
- % pushing CostlyIndex next to SinglesBefore and executing those
- % conjunctions in parallel can yield a speedup.
- %
-:- pred push_and_build_candidate_conjunctions(implicit_parallelism_info::in,
- list(goal_path_step)::in, list(pard_goal_detail)::in, int::in,
- list(pard_goal_detail)::in, cord(message)::out,
- list(candidate_par_conjunction(pard_goal_detail))::out) is det.
-
-push_and_build_candidate_conjunctions(_Info, _RevGoalPathSteps, _Conjs,
- _CostlyIndex, [], cord.empty, []).
-push_and_build_candidate_conjunctions(Info, RevGoalPathSteps, Conjs,
- CostlyIndex, [Single | Singles], Messages, Candidates) :-
- push_and_build_candidate_conjunction(Info, RevGoalPathSteps, Conjs,
- CostlyIndex, Single, HeadMessages, MaybeHeadCandidate),
- push_and_build_candidate_conjunctions(Info, RevGoalPathSteps, Conjs,
- CostlyIndex, Singles, TailMessages, TailCandidates),
- Messages = HeadMessages ++ TailMessages,
- (
- MaybeHeadCandidate = yes(HeadCandidate),
- Candidates = [HeadCandidate | TailCandidates]
- ;
- MaybeHeadCandidate = no,
- Candidates = TailCandidates
- ).
-
-:- pred push_and_build_candidate_conjunction(implicit_parallelism_info::in,
- list(goal_path_step)::in, list(pard_goal_detail)::in, int::in,
- pard_goal_detail::in, cord(message)::out,
- maybe(candidate_par_conjunction(pard_goal_detail))::out) is det.
-
-push_and_build_candidate_conjunction(Info, RevGoalPathSteps, Conjs,
- CostlyIndex, Single, !:Messages, MaybeCandidate) :-
- SingleRevPath = Single ^ goal_annotation ^ pgd_original_path,
- SingleRevPath = rgp(SingleRevSteps),
- list.reverse(SingleRevSteps, SingleSteps),
- list.reverse(RevGoalPathSteps, GoalPathSteps),
- (
- goal_path_inside_relative(fgp(GoalPathSteps), fgp(SingleSteps),
- RelativePath),
- RelativePath = fgp(RelativeSteps),
- RelativeSteps = [step_conj(RelConjStep) | TailRelativeSteps],
- RelConjStep < CostlyIndex,
- list.take(CostlyIndex, Conjs, ConjsUptoCostly),
- list.drop(RelConjStep - 1, ConjsUptoCostly,
- [GoalToPushInto | GoalsToPush])
- ->
- RevPushGoalPathSteps = [step_conj(RelConjStep) | RevGoalPathSteps],
- push_goals_create_candidate(Info, RevPushGoalPathSteps,
- TailRelativeSteps, GoalToPushInto, GoalsToPush,
- RevCandidateGoalPathSteps, CandidateConjs),
-
- ProcLabel = Info ^ ipi_proc_label,
- !:Messages = cord.empty,
- % XXX Location is a lie
- Location = pl_goal(ProcLabel, rgp(RevGoalPathSteps)),
- append_message(Location,
- info_found_pushed_conjs_above_callsite_threshold,
- !Messages),
-
- (
- list.split_last(RelativeSteps, MostRelativeSteps,
- LastRelativeStep),
- LastRelativeStep = step_conj(_)
- ->
- % We push GoalsToPush into the existing conjunction
- % containing Single.
- PushGoalSteps = MostRelativeSteps
- ;
- % We push GoalsToPush next to Single in a newly created
- % conjunction.
- PushGoalSteps = RelativeSteps
- ),
-
- PushGoal = push_goal(rev_goal_path_to_string(rgp(RevGoalPathSteps)),
- RelConjStep + 1, CostlyIndex,
- [goal_path_to_string(fgp(PushGoalSteps))]),
- pardgoals_build_candidate_conjunction(Info, Location,
- RevCandidateGoalPathSteps, yes(PushGoal), CandidateConjs,
- MaybeCandidate, !Messages),
- (
- MaybeCandidate = yes(_),
- append_message(Location,
- info_found_n_conjunctions_with_positive_speedup(1),
- !Messages)
- ;
- MaybeCandidate = no
- )
- ;
- unexpected($module, $pred, "bad goal path for Single")
- ).
-
-:- pred merge_same_level_pushes(
- candidate_par_conjunction(pard_goal_detail)::in,
- list(candidate_par_conjunction(pard_goal_detail))::in,
- push_goal::out) is det.
-
-merge_same_level_pushes(MainCandidate, [], MainPush) :-
- MaybeMainPush = MainCandidate ^ cpc_maybe_push_goal,
- (
- MaybeMainPush = yes(MainPush)
- ;
- MaybeMainPush = no,
- unexpected($module, $pred, "no push")
- ).
-merge_same_level_pushes(MainCandidate, [HeadCandidate | TailCandidates],
- Push) :-
- merge_same_level_pushes(HeadCandidate, TailCandidates, RestPush),
- MaybeMainPush = MainCandidate ^ cpc_maybe_push_goal,
- (
- MaybeMainPush = yes(MainPush)
- ;
- MaybeMainPush = no,
- unexpected($module, $pred, "no push")
- ),
- (
- MainPush = push_goal(GoalPathStr, Lo, Hi, [MainPushInto]),
- RestPush = push_goal(GoalPathStr, Lo, Hi, RestPushInto)
- ->
- Push = push_goal(GoalPathStr, Lo, Hi, [MainPushInto | RestPushInto])
- ;
- unexpected($module, $pred, "mismatch on pushed goals")
- ).
-
-:- pred push_goals_create_candidate(implicit_parallelism_info::in,
- list(goal_path_step)::in, list(goal_path_step)::in,
- pard_goal_detail::in, list(pard_goal_detail)::in,
- list(goal_path_step)::out, list(pard_goal_detail)::out) is det.
-
-push_goals_create_candidate(Info, RevCurPathSteps,
- [], GoalToPushInto, GoalsToPush0,
- RevCandidateGoalPathSteps, CandidateConjs) :-
- RevCandidateGoalPathSteps = RevCurPathSteps,
- % The pushed goals will have different costs in this context, in particular
- % the number of times they're called varies, This affects the per-call
- % costs of recursive calls.
- Calls = goal_cost_get_calls(GoalToPushInto ^ goal_annotation ^ pgd_cost),
- map(fix_goal_counts(Info, Calls), GoalsToPush0, GoalsToPush),
- CandidateConjs = [GoalToPushInto | GoalsToPush].
-push_goals_create_candidate(Info, RevCurPathSteps,
- [HeadRelStep | TailRelSteps], GoalToPushInto, GoalsToPush0,
- RevCandidateGoalPathSteps, CandidateConjs) :-
- GoalToPushInto = goal_rep(GoalExpr, _, _),
- (
- HeadRelStep = step_conj(N),
- ( GoalExpr = conj_rep(Goals) ->
- (
- TailRelSteps = [],
- % Conjoin GoalsToPush not with just the expensive goal,
- % but with the whole conjunction containing it.
- RevCandidateGoalPathSteps = RevCurPathSteps,
- % The pushed goals will have different costs in this context,
- % in particular the number of times they're called varies, This
- % affects the per-call costs of recursive calls.
- Cost = GoalToPushInto ^ goal_annotation ^ pgd_cost,
- Calls = goal_cost_get_calls(Cost),
- map(fix_goal_counts(Info, Calls), GoalsToPush0, GoalsToPush),
- CandidateConjs = Goals ++ GoalsToPush
- ;
- TailRelSteps = [_ | _],
- list.det_drop(N - 1, Goals, Tail),
- ( Tail = [SubGoal] ->
- push_goals_create_candidate(Info,
- [HeadRelStep | RevCurPathSteps],
- TailRelSteps, SubGoal, GoalsToPush0,
- RevCandidateGoalPathSteps, CandidateConjs)
- ;
- % We can't push goals into the non-last conjunct without
- % re-ordering, which is currently not supported. By
- % building a conjunction here we may still be able to
- % create a worthwhile parallelisation. However, there is a
- % trade-off to explore between this and not generating the
- % single expensive goal from within the conjunction and
- % therefore possibly finding other single expensive goals
- % later in this conjunction.
- RevCandidateGoalPathSteps = RevCurPathSteps,
- Cost = GoalToPushInto ^ goal_annotation ^ pgd_cost,
- Calls = goal_cost_get_calls(Cost),
- map(fix_goal_counts(Info, Calls), GoalsToPush0,
- GoalsToPush),
- CandidateConjs = Goals ++ GoalsToPush
- )
- )
- ;
- unexpected($module, $pred, "not conj")
- )
- ;
- HeadRelStep = step_disj(N),
- ( GoalExpr = disj_rep(Goals) ->
- list.index1_det(Goals, N, SubGoal),
- push_goals_create_candidate(Info, [HeadRelStep | RevCurPathSteps],
- TailRelSteps, SubGoal, GoalsToPush0,
- RevCandidateGoalPathSteps, CandidateConjs)
- ;
- unexpected($module, $pred, "not disj")
- )
- ;
- HeadRelStep = step_switch(N, _),
- ( GoalExpr = switch_rep(_, _, Cases) ->
- list.index1_det(Cases, N, Case),
- Case = case_rep(_, _, SubGoal),
- push_goals_create_candidate(Info, [HeadRelStep | RevCurPathSteps],
- TailRelSteps, SubGoal, GoalsToPush0,
- RevCandidateGoalPathSteps, CandidateConjs)
- ;
- unexpected($module, $pred, "not switch")
- )
- ;
- HeadRelStep = step_ite_then,
- ( GoalExpr = ite_rep(_, Then, _) ->
- push_goals_create_candidate(Info, [HeadRelStep | RevCurPathSteps],
- TailRelSteps, Then, GoalsToPush0,
- RevCandidateGoalPathSteps, CandidateConjs)
- ;
- unexpected($module, $pred, "not ite_then")
- )
- ;
- HeadRelStep = step_ite_else,
- ( GoalExpr = ite_rep(_, _, Else) ->
- push_goals_create_candidate(Info, [HeadRelStep | RevCurPathSteps],
- TailRelSteps, Else, GoalsToPush0,
- RevCandidateGoalPathSteps, CandidateConjs)
- ;
- unexpected($module, $pred, "not ite_else")
- )
- ;
- HeadRelStep = step_ite_cond,
- % We cannot push into a condition.
- unexpected($module, $pred, "ite_cond")
- ;
- HeadRelStep = step_neg,
- % We cannot push into a negated goal.
- unexpected($module, $pred, "neg")
- ;
- HeadRelStep = step_scope(_),
- ( GoalExpr = scope_rep(SubGoal, _) ->
- push_goals_create_candidate(Info, [HeadRelStep | RevCurPathSteps],
- TailRelSteps, SubGoal, GoalsToPush0,
- RevCandidateGoalPathSteps, CandidateConjs)
- ;
- unexpected($module, $pred, "not scope")
- )
- ;
- HeadRelStep = step_lambda,
- % These should not exist in a profiled program.
- unexpected($module, $pred, "lambda")
- ;
- HeadRelStep = step_try,
- % These should not exist in a profiled program.
- unexpected($module, $pred, "try")
- ;
- HeadRelStep = step_atomic_main,
- % These should not exist in a profiled program.
- unexpected($module, $pred, "atomic_main")
- ;
- HeadRelStep = step_atomic_orelse(_),
- % These should not exist in a profiled program.
- unexpected($module, $pred, "atomic_orelse")
- ).
-
-:- pred fix_goal_counts(implicit_parallelism_info::in, int::in,
- pard_goal_detail::in, pard_goal_detail::out) is det.
-
-fix_goal_counts(Info, Count, !Goal) :-
- Annotation0 = !.Goal ^ goal_annotation,
- Cost0 = Annotation0 ^ pgd_cost,
- (
- GoalType = Annotation0 ^ pgd_pg_type,
- GoalType = pgt_call(_, CostAndCallees),
- % XXX This doesn't work if this is a non-atomic goal containing a
- % recursive call.
- set.member(Callee, CostAndCallees ^ cac_callees),
- % The call is recursive if it calls into the current clique.
- Info ^ ipi_clique = Callee ^ c_clique
- ->
- % for recursive calls.
- CostTotal = goal_cost_get_total(Cost0),
- PercallCost = CostTotal / float(Count)
- ;
- PercallCost = goal_cost_get_percall(Cost0)
- ),
- Cost = call_goal_cost(Count, PercallCost),
- !Goal ^ goal_annotation ^ pgd_cost := Cost,
- ( goal_cost_above_par_threshold(Info, Cost) ->
- AboveThreshold = cost_above_par_threshold
- ;
- AboveThreshold = cost_not_above_par_threshold
- ),
- !Goal ^ goal_annotation ^ pgd_cost_above_threshold := AboveThreshold.
-
-:- pred pardgoals_build_candidate_conjunction(implicit_parallelism_info::in,
- program_location::in, list(goal_path_step)::in,
- maybe(push_goal)::in, list(pard_goal_detail)::in,
- maybe(candidate_par_conjunction(pard_goal_detail))::out,
- cord(message)::in, cord(message)::out) is det.
-
-pardgoals_build_candidate_conjunction(Info, Location, RevGoalPathSteps,
- MaybePushGoal, Goals, MaybeCandidate, !Messages) :-
- % Setting up the first parallel conjunct is a different algorithm to the
- % latter ones, at this point we have the option of moving goals from before
- % the first costly call to either before or during the parallel
- % conjunction. Executing them during the parallel conjunction can be more
- % efficient. However if goals within other parallel conjuncts depend on
- % them and don't depend upon the first costly call then this would make the
- % conjunction dependent when it could be independent.
- find_best_parallelisation(Info, Location, Goals, MaybeBestParallelisation,
- !Messages),
- (
- MaybeBestParallelisation = yes(BestParallelisation),
- FirstConjNum = 1,
- ParalleliseDepConjs = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs,
- BestParallelisation = bp_parallel_execution(GoalsBefore, ParConjs,
- GoalsAfter, IsDependent, Metrics),
- Speedup = parallel_exec_metrics_get_speedup(Metrics),
- Calls = Metrics ^ pem_num_calls,
- conj_calc_cost(GoalsBefore, Calls, GoalsBeforeCost0),
- GoalsBeforeCost = goal_cost_get_percall(GoalsBeforeCost0),
- conj_calc_cost(GoalsAfter, Calls, GoalsAfterCost0),
- GoalsAfterCost = goal_cost_get_percall(GoalsAfterCost0),
- RevGoalPathString = rev_goal_path_to_string(rgp(RevGoalPathSteps)),
- Candidate = candidate_par_conjunction(RevGoalPathString, MaybePushGoal,
- FirstConjNum, IsDependent, GoalsBefore, GoalsBeforeCost, ParConjs,
- GoalsAfter, GoalsAfterCost, Metrics),
- (
- Speedup > 1.0,
- (
- ParalleliseDepConjs = do_not_parallelise_dep_conjs
- =>
- IsDependent = conjuncts_are_independent
- )
- ->
- MaybeCandidate = yes(Candidate)
- ;
- MaybeCandidate = no,
- trace [
- compile_time(flag("debug_parallel_conjunction_speedup")),
- io(!IO)
- ]
- (
- (
- ( Location = pl_proc(ProcLabel)
- ; Location = pl_goal(ProcLabel, _)
- )
- ;
- Location = pl_clique(_),
- unexpected($module, $pred, "location is a clique")
- ;
- Location = pl_csd(_),
- unexpected($module, $pred, "location is a csd")
- ),
-
- convert_candidate_par_conjunction(
- pard_goal_detail_to_pard_goal, Candidate, FBCandidate),
- VarTable = Info ^ ipi_var_table,
- create_candidate_parallel_conj_report(VarTable,
- FBCandidate, Report),
- print_proc_label_to_string(ProcLabel, ProcLabelString),
- io.format("Not parallelising conjunction in %s, " ++
- "insufficient speedup or too dependent:\n",
- [s(ProcLabelString)], !IO),
- io.write_string(append_list(cord.list(Report)), !IO),
- io.flush_output(!IO)
- )
- )
- ;
- MaybeBestParallelisation = no,
- MaybeCandidate = no
- ).
-
-%----------------------------------------------------------------------------%
-
-calculate_parallel_cost(CostData, !Parallelisation) :-
- ParConj = ip_get_par_conjs(!.Parallelisation),
- NumCalls = !.Parallelisation ^ ip_num_calls,
-
- maybe_calc_sequential_cost(
- (func(P) = P ^ ip_maybe_goals_before_cost),
- (func(P0, MaybeCost) = P0 ^ ip_maybe_goals_before_cost := MaybeCost),
- ip_get_goals_before, CostBeforePercall, NumCalls, !Parallelisation),
- maybe_calc_sequential_cost(
- (func(P) = P ^ ip_maybe_goals_after_cost),
- (func(P0, MaybeCost) = P0 ^ ip_maybe_goals_after_cost := MaybeCost),
- ip_get_goals_after, CostAfterPercall, NumCalls, !Parallelisation),
-
- Info = !.Parallelisation ^ ip_info,
- Opts = Info ^ ipi_opts,
- SparkCost = Opts ^ cpcp_sparking_cost,
- SparkDelay = Opts ^ cpcp_sparking_delay,
- BarrierCost = Opts ^ cpcp_barrier_cost,
- ContextWakeupDelay = Opts ^ cpcp_context_wakeup_delay,
- Metrics0 = init_empty_parallel_exec_metrics(CostBeforePercall,
- CostAfterPercall, NumCalls, float(SparkCost), float(SparkDelay),
- float(BarrierCost), float(ContextWakeupDelay)),
- Overlap0 = peo_empty_conjunct,
-
- SharedVars = ip_calc_sharedvars_set(!.Parallelisation),
- CostData0 = parallelisation_cost_data(SharedVars, Overlap0, Metrics0, init),
- NumMiddleGoals = ip_get_num_goals_middle(!.Parallelisation),
- list.foldl3(calculate_parallel_cost_step(Info, NumMiddleGoals), ParConj,
- 1, _, 0, _, CostData0, CostData),
- !Parallelisation ^ ip_maybe_par_cost_data := yes(CostData).
-
-:- pred maybe_calc_sequential_cost((func(T) = maybe(goal_cost_csq))::in,
- (func(T, maybe(goal_cost_csq)) = T)::in,
- (func(T) = list(pard_goal_detail))::in, float::out,
- int::in, T::in, T::out) is det.
-
-maybe_calc_sequential_cost(GetMaybe, SetMaybe, GetGoals, CostPercall, Calls,
- !Acc) :-
- MaybeCost = GetMaybe(!.Acc),
- (
- MaybeCost = yes(Cost)
- ;
- MaybeCost = no,
- Goals = GetGoals(!.Acc),
- conj_calc_cost(Goals, Calls, Cost),
- !:Acc = SetMaybe(!.Acc, yes(Cost))
- ),
- CostPercall = goal_cost_get_percall(Cost).
-
-:- type is_last_par_conjunct
- ---> is_last_par_conjunct
- ; not_last_par_conjunct.
-
-:- pred calculate_parallel_cost_step(implicit_parallelism_info::in,
- int::in, seq_conj(pard_goal_detail)::in, int::in, int::out,
- int::in, int::out,
- parallelisation_cost_data::in, parallelisation_cost_data::out) is det.
-
-calculate_parallel_cost_step(Info, NumMiddleGoals, Conjunct, !ConjNum,
- !NumGoals, !CostData) :-
- !.CostData = parallelisation_cost_data(SharedVars, Overlap0, Metrics0,
- PM0),
- !:NumGoals = !.NumGoals + length(Conjuncts),
- ( !.NumGoals = NumMiddleGoals ->
- IsLastConjunct = is_last_par_conjunct
- ;
- IsLastConjunct = not_last_par_conjunct
- ),
- Conjunct = seq_conj(Conjuncts),
- calculate_parallel_cost_step(Info, SharedVars, IsLastConjunct, Conjuncts,
- !ConjNum, PM0, PM, Overlap0, Overlap, Metrics0, Metrics),
- !:CostData = parallelisation_cost_data(SharedVars, Overlap, Metrics, PM).
-
-:- pred calculate_parallel_cost_step(implicit_parallelism_info::in,
- set(var_rep)::in, is_last_par_conjunct::in, list(pard_goal_detail)::in,
- int::in, int::out, map(var_rep, float)::in, map(var_rep, float)::out,
- parallel_execution_overlap::in, parallel_execution_overlap::out,
- parallel_exec_metrics_incomplete::in,
- parallel_exec_metrics_incomplete::out) is det.
-
-calculate_parallel_cost_step(Info, AllSharedVars, IsLastConjunct, Conjunct,
- !ConjNum, !ProductionsMap, !Overlap, !Metrics) :-
- Algorithm = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs,
-
- Calls = parallel_exec_metrics_get_num_calls(!.Metrics),
- conj_calc_cost(Conjunct, Calls, CostB0),
- CostB = goal_cost_get_percall(CostB0),
- list.foldl2(conj_produced_and_consumed_vars, Conjunct,
- set.init, RightProducedVars0, set.init, RightConsumedVars0),
- RightProducedVars = set.intersect(RightProducedVars0, AllSharedVars),
- RightConsumedVars = set.intersect(RightConsumedVars0, AllSharedVars),
- ProducedVars =
- set.from_sorted_list(map.sorted_keys(!.ProductionsMap)),
- Vars = set.intersect(ProducedVars, RightConsumedVars),
-
- % This conjunct will actually start after it has been sparked by
- % the previous conjunct, which in turn may have been sparked by an
- % earlier conjunct.
- SparkDelay = Info ^ ipi_opts ^ cpcp_sparking_delay,
- StartTime0 = float((!.ConjNum - 1) * SparkDelay),
-
- % If there are conjuncts after this conjunct, we will have
- % the additional cost of sparking them.
- (
- IsLastConjunct = not_last_par_conjunct,
- SparkCost = float(Info ^ ipi_opts ^ cpcp_sparking_cost)
- ;
- IsLastConjunct = is_last_par_conjunct,
- SparkCost = 0.0
- ),
- StartTime = StartTime0 + SparkCost,
-
- (
- Algorithm = parallelise_dep_conjs_overlap,
-
- % Get the list of variables consumed by this conjunct
- % that will be turned into futures.
- list.foldl4(get_consumptions_and_productions_list, Conjunct, Vars, _,
- RightProducedVars, _, 0.0, _,
- [], ConsumptionsAndProductionsList0),
- list.reverse(ConsumptionsAndProductionsList0,
- ConsumptionsAndProductionsList),
-
- % Determine how the parallel conjuncts overlap.
- list.foldl5(
- calculate_dependent_parallel_cost_2(Info, !.ProductionsMap),
- ConsumptionsAndProductionsList, 0.0, LastSeqConsumeTime,
- StartTime, LastParConsumeTime, StartTime, LastResumeTime,
- [], RevExecution0, map.init, ConsumptionsMap),
-
- % Calculate the point at which this conjunct finishes execution
- % and complete the RevExecutions structure..
- list.reverse(RevExecution, Execution),
- CostBParElapsed = LastParConsumeTime + (CostB - LastSeqConsumeTime),
- RevExecution = [ (LastResumeTime - CostBParElapsed) | RevExecution0 ],
-
- CostSignals = float(Info ^ ipi_opts ^ cpcp_future_signal_cost *
- count(RightProducedVars)),
- CostWaits = float(Info ^ ipi_opts ^ cpcp_future_wait_cost *
- count(Vars)),
- calc_cost_and_dead_time(Execution, CostBPar, DeadTime)
- ;
- ( Algorithm = parallelise_dep_conjs_naive
- ; Algorithm = do_not_parallelise_dep_conjs
- ; Algorithm = parallelise_dep_conjs_num_vars
- ),
-
- CostBPar = CostB + SparkCost,
- Execution = [StartTime - (StartTime + CostB)],
- ConsumptionsMap = init,
- CostSignals = 0.0,
- CostWaits = 0.0,
- DeadTime = 0.0
- ),
-
- % CostB - the cost of B if it where to be executed in sequence.
- % CostBPar - CostB plus the overheads of parallel exection (not including
- % the dead time).
- % DeadTime - The time that B spends blocked on other computations.
- % XXX: Need to account for SparkDelay here,
- !:Metrics = init_parallel_exec_metrics_incomplete(!.Metrics, CostSignals,
- CostWaits, CostB, CostBPar, DeadTime),
-
- % Build the productions map for the next conjunct. This map contains
- % all the variables produced by this code, not just that are used for
- % dependent parallelisation.
- list.foldl3(get_productions_map(RightProducedVars), Conjunct, StartTime, _,
- Execution, _, !ProductionsMap),
-
- DepConjExec = dependent_conjunct_execution(Execution,
- !.ProductionsMap, ConsumptionsMap),
- !:Overlap = peo_conjunction(!.Overlap, DepConjExec, Vars),
- !:ConjNum = !.ConjNum + 1.
-
- % calculate_dependent_parallel_cost_2(Info, ProductionsMap,
- % Var - SeqConsTime, !PrevSeqConsumeTime, !PrevParConsumeTime,
- % !ResumeTime, !RevExecution, !ConsumptionsMap).
- %
- % The main loop of the parallel overlap analysis.
- %
- % * ProductionsMap: A map of variable productions to the left of this
- % conjunct.
- %
- % * Var: The current variable under consideration.
- %
- % * SeqConsTime: The type of event for this variable in this conjunct and
- % the time at which it occurs. It is either consumed or produced by this
- % conjunct.
- %
- % * !PrevSeqConsumeTime: Accumulates the time of the previous consumption
- % during sequential execution, or if there is none it represents the
- % beginning of sequential execution (0.0).
- %
- % * !PrevParConsumeTime: Accumulates the time of the previous consumption
- % during parallel execution. Or if there is none this represents the
- % tame that the parallel conjunct first begun execution.
- %
- % * !ResumeTime: Accumulates the time that execution last resumed if it
- % became blocked, or the beginning of the parallel conjunct's execution.
- %
- % * !RevExecution: Accumulates a list of pairs, each pair stores the time
- % that execution begun and the time that it pasted. This never includes
- % the remaining execution after all variables have been consumed. This
- % is used by our caller to calculate the production times of this
- % conjunct for later ones.
- %
- % * !ConsumptionsMap: Accumuates a map of variable consumptions.
- %
-:- pred calculate_dependent_parallel_cost_2(implicit_parallelism_info::in,
- map(var_rep, float)::in, pair(var_rep, production_or_consumption)::in,
- float::in, float::out, float::in, float::out, float::in, float::out,
- assoc_list(float, float)::in, assoc_list(float, float)::out,
- map(var_rep, float)::in, map(var_rep, float)::out) is det.
-
-calculate_dependent_parallel_cost_2(Info, ProductionsMap, Var - SeqEventTime,
- !PrevSeqConsumeTime, !PrevParConsumeTime, !ResumeTime,
- !RevExecution, !ConsumptionsMap) :-
- (
- SeqEventTime = consumption(SeqConsTime),
- calculate_dependent_parallel_cost_consumption(Info, ProductionsMap,
- Var - SeqConsTime, !PrevSeqConsumeTime, !PrevParConsumeTime,
- !ResumeTime, !RevExecution, !ConsumptionsMap)
- ;
- SeqEventTime = production(SeqProdTime),
- calculate_dependent_parallel_cost_production(Info, SeqProdTime,
- !PrevSeqConsumeTime, !PrevParConsumeTime, !ResumeTime,
- !RevExecution, !ConsumptionsMap)
- ).
-
-:- pred calculate_dependent_parallel_cost_consumption(
- implicit_parallelism_info::in, map(var_rep, float)::in,
- pair(var_rep, float)::in, float::in, float::out,
- float::in, float::out, float::in, float::out,
- assoc_list(float, float)::in, assoc_list(float, float)::out,
- map(var_rep, float)::in, map(var_rep, float)::out) is det.
-
-calculate_dependent_parallel_cost_consumption(Info, ProductionsMap,
- Var - SeqConsTime, !PrevSeqConsumeTime, !PrevParConsumeTime,
- !ResumeTime, !RevExecution, !ConsumptionsMap) :-
- map.lookup(ProductionsMap, Var, ProdTime),
- % Consider (P & Q):
- %
- % Q cannot consume the variable until P produces it. Also Q cannot consume
- % the variable until it is ready for it. These are the two parameters to
- % max/2.
- %
- % The second parameter can be explained further. Q may have waited on a
- % future previously, if so !.PrevParConsumeTime is when it finished
- % waiting, and SeqConsTime - !.PrevSeqConsumeTime is how long Q will take
- % between the two waits.
- %
- ParConsTimeBlocked = ProdTime,
- ParConsTimeNotBlocked = !.PrevParConsumeTime +
- (SeqConsTime - !.PrevSeqConsumeTime),
- ParConsTime0 = max(ParConsTimeBlocked, ParConsTimeNotBlocked) +
- float(Info ^ ipi_opts ^ cpcp_future_wait_cost),
-
- (
- % True if Q had to suspend waiting for P. Note that we don't include
- % FutureSyncTime here. This is true if Q has to block at all even if
- % it can be made runable before the context switch is complete.
- ProdTime > ParConsTimeNotBlocked
- ->
- % Include the time that it may take to resume this thread.
- ParConsTime = ParConsTime0 +
- float(Info ^ ipi_opts ^ cpcp_context_wakeup_delay),
- !:RevExecution =
- [(!.ResumeTime - ParConsTimeNotBlocked) | !.RevExecution],
- !:ResumeTime = ParConsTime
- ;
- ParConsTime = ParConsTime0
- ),
-
- !:PrevSeqConsumeTime = SeqConsTime,
- !:PrevParConsumeTime = ParConsTime,
-
- svmap.det_insert(Var, ParConsTime, !ConsumptionsMap).
-
-:- pred calculate_dependent_parallel_cost_production(
- implicit_parallelism_info::in, float::in, float::in, float::out,
- float::in, float::out, float::in, float::out,
- assoc_list(float, float)::in, assoc_list(float, float)::out,
- map(var_rep, float)::in, map(var_rep, float)::out) is det.
-
-calculate_dependent_parallel_cost_production(Info,
- SeqProdTime, !PrevSeqConsumeTime, !PrevParConsumeTime,
- !ResumeTime, !RevExecution, !ConsumptionsMap) :-
- SignalCost = float(Info ^ ipi_opts ^ cpcp_future_signal_cost),
-
- ParProdTime = !.PrevParConsumeTime +
- (SeqProdTime - !.PrevSeqConsumeTime) + SignalCost,
- !:PrevSeqConsumeTime = SeqProdTime,
- !:PrevParConsumeTime = ParProdTime.
-
-:- pred depends_lookup(dependency_graphs::in, int::in, set(int)::out) is det.
-
-depends_lookup(DependencyGraphs, GoalNum, Deps) :-
- graph_do_lookup(lookup_from, DependencyGraphs ^ dm_forward, GoalNum, Deps).
-
-:- pred depends_lookup_tc(dependency_graphs::in, int::in, set(int)::out)
- is det.
-
-depends_lookup_tc(DependencyGraphs, GoalNum, Deps) :-
- graph_do_lookup(lookup_from, DependencyGraphs ^ dm_forward_tc, GoalNum,
- Deps).
-
-:- pred depends_lookup_rev(dependency_graphs::in, int::in, set(int)::out)
- is det.
-
-depends_lookup_rev(DependencyGraphs, GoalNum, RevDeps) :-
- graph_do_lookup(lookup_to, DependencyGraphs ^ dm_forward, GoalNum,
- RevDeps).
-
-:- pred depends_lookup_tc_rev(dependency_graphs::in, int::in, set(int)::out)
- is det.
-
-depends_lookup_tc_rev(DependencyGraphs, GoalNum, RevDeps) :-
- graph_do_lookup(lookup_to, DependencyGraphs ^ dm_forward_tc, GoalNum,
- RevDeps).
-
- % Abstract code for querying a graph for a goal dependency.
- %
-:- pred graph_do_lookup(
- pred(digraph(int), digraph_key(int), set(digraph_key(int)))::
- in(pred(in, in, out) is det),
- digraph(int)::in, int::in, set(int)::out) is det.
-
-graph_do_lookup(Lookup, Graph, GoalNum, Deps) :-
- Lookup(Graph, lookup_key(Graph, GoalNum), DepsKeys),
- Deps = set(map(lookup_vertex(Graph), set.to_sorted_list(DepsKeys))).
-
- % foldl(get_productions_map(Goals, 0,0, _, Vars, _, map.init, Map).
- %
- % If Goals is semidet this can produce incorrect values in the !Time
- % accumulator that lead to exceptions. This is prevented by only
- % attempting to parallelise goals that are det or cc_multi.
- %
- % Build a map of variable productions in Goals.
- %
-:- pred get_productions_map(set(var_rep)::in, pard_goal_detail::in,
- float::in, float::out,
- assoc_list(float, float)::in, assoc_list(float, float)::out,
- map(var_rep, float)::in, map(var_rep, float)::out) is det.
-
-get_productions_map(Vars, Goal, !Time, !Executions, !Map) :-
- InstMapInfo = Goal ^ goal_annotation ^ pgd_inst_map_info,
- BoundVars0 = InstMapInfo ^ im_bound_vars,
- BoundVars = set.intersect(BoundVars0, Vars),
- adjust_time_for_waits(!Time, !Executions),
- set.fold(var_production_time_to_map(!.Time, Goal), BoundVars, !Map),
- !:Time = !.Time + goal_cost_get_percall(Goal ^ goal_annotation ^ pgd_cost).
-
-:- pred adjust_time_for_waits(float::in, float::out,
- assoc_list(float, float)::in, assoc_list(float, float)::out) is det.
-
-adjust_time_for_waits(!Time, !Executions) :-
- (
- !.Executions = [Execution | NextExecution],
- ( Start - End ) = Execution,
- ( (!.Time + adjust_time_for_waits_epsilon) < Start ->
- error("adjust_time_for_waits: " ++
- "Time occurs before the current execution")
- ; !.Time =< (End + adjust_time_for_waits_epsilon) ->
- % The production is within the current execution, no adjustment is
- % necessary.
- true
- ;
- % The time is after this execution.
- !:Executions = NextExecution,
- adjust_time_for_waits_2(End, !Time, !Executions)
- )
- ;
- !.Executions = [],
- error("adjust_time_for_waits: Time occurs after all executions")
- ).
-
-:- pred adjust_time_for_waits_2(float::in, float::in, float::out,
- assoc_list(float, float)::in, assoc_list(float, float)::out) is det.
-
-adjust_time_for_waits_2(LastEnd, !Time, !Executions) :-
- (
- !.Executions = [ Execution | NextExecution ],
- ( Start - End ) = Execution,
-
- % Do the adjustment.
- !:Time = !.Time + (Start - LastEnd),
-
- ( (!.Time + adjust_time_for_waits_epsilon) < Start ->
- error(format("adjust_time_for_waits: Adjustment didn't work, " ++
- "time occurs before the current execution. " ++
- "Time: %f, Start: %f.", [f(!.Time), f(Start)]))
- ; !.Time =< (End + adjust_time_for_waits_epsilon) ->
- % The adjustment worked.
- true
- ;
- % Further adjustment is needed.
- !:Executions = NextExecution,
- adjust_time_for_waits_2(End, !Time, !Executions)
- )
- ;
- !.Executions = [],
- error("adjust_time_for_waits: Ran out of executions")
- ).
-
-:- func adjust_time_for_waits_epsilon = float.
-
-adjust_time_for_waits_epsilon = 0.0001.
-
- % Calculate the time spend during execution and the time spent between
- % executions (dead time).
- %
-:- pred calc_cost_and_dead_time(assoc_list(float, float)::in, float::out,
- float::out) is det.
-
-calc_cost_and_dead_time([], 0.0, 0.0).
-calc_cost_and_dead_time([Start - Stop | Executions], !:Time, DeadTime) :-
- !:Time = Stop - Start,
- calc_cost_and_dead_time_2(Executions, Stop, !Time, 0.0, DeadTime).
-
-:- pred calc_cost_and_dead_time_2(assoc_list(float, float)::in, float::in,
- float::in, float::out, float::in, float::out) is det.
-
-calc_cost_and_dead_time_2([], _, !Time, !DeadTime).
-calc_cost_and_dead_time_2([Start - Stop | Executions], LastStop,
- !Time, !DeadTime) :-
- !:Time = !.Time + Stop - Start,
- !:DeadTime = !.DeadTime + Start - LastStop,
- calc_cost_and_dead_time_2(Executions, Stop, !Time, !DeadTime).
-
- % var_production_time_to_map(TimeBefore, Goal, Var, !Map).
- %
- % Find the latest production time of Var in Goal, and add TimeBefore + the
- % production time to the map. An exception is thrown if a duplicate map
- % entry is found, our caller must prevent this.
- %
-:- pred var_production_time_to_map(float::in, pard_goal_detail::in,
- var_rep::in, map(var_rep, float)::in, map(var_rep, float)::out) is det.
-
-var_production_time_to_map(TimeBefore, Goal, Var, !Map) :-
- var_first_use_time(find_production, TimeBefore, Goal, Var, Time),
- svmap.det_insert(Var, Time, !Map).
-
- % Either a production or consumption time. Consumptions should sort before
- % productions.
- %
-:- type production_or_consumption
- ---> consumption(float)
- ; production(float).
-
- % foldl(get_consumptions_list(Vars), Goals, 0.0, _, [], RevConsumptions),
- %
- % Compute the order and time of variable consumptions in goals.
- %
-:- pred get_consumptions_and_productions_list(pard_goal_detail::in,
- set(var_rep)::in, set(var_rep)::out,
- set(var_rep)::in, set(var_rep)::out, float::in, float::out,
- assoc_list(var_rep, production_or_consumption)::in,
- assoc_list(var_rep, production_or_consumption)::out) is det.
-
-get_consumptions_and_productions_list(Goal, !ConsumedVars, !ProducedVars,
- !Time, !List) :-
- InstMapInfo = Goal ^ goal_annotation ^ pgd_inst_map_info,
-
- AllConsumptionVars = InstMapInfo ^ im_consumed_vars,
- ConsumptionVars = set.intersect(!.ConsumedVars, AllConsumptionVars),
- set.map(var_consumptions(!.Time, Goal),
- ConsumptionVars, ConsumptionTimesSet0),
- !:ConsumedVars = difference(!.ConsumedVars, ConsumptionVars),
- % Since we re-sort the list we don't need a sorted one to start with,
- % but the set module doesn't export a "to_list" predicate. (Getting
- % a sorted list has no cost since the set is a sorted list internally).
- set.to_sorted_list(ConsumptionTimesSet0, ConsumptionTimes0),
- list.sort(compare_times, ConsumptionTimes0, ConsumptionTimes),
-
- AllProductionVars = InstMapInfo ^ im_bound_vars,
- ProductionVars = set.intersect(!.ProducedVars, AllProductionVars),
- set.map(var_productions(!.Time, Goal),
- ProductionVars, ProductionTimesSet0),
- !:ProducedVars = difference(!.ProducedVars, ProductionVars),
- set.to_sorted_list(ProductionTimesSet0, ProductionTimes0),
- list.sort(compare_times, ProductionTimes0, ProductionTimes),
-
- merge_consumptions_and_productions(ConsumptionTimes, ProductionTimes,
- ConsumptionAndProductionTimes),
- !:List = ConsumptionAndProductionTimes ++ !.List,
- !:Time = !.Time + goal_cost_get_percall(Goal ^ goal_annotation ^ pgd_cost).
-
-:- pred compare_times(pair(A, float)::in, pair(A, float)::in,
- comparison_result::out) is det.
-
-compare_times(_ - TimeA, _ - TimeB, Result) :-
- % Note that the Time arguments are swapped, this list must be
- % produced in latest to earliest order.
- compare(Result, TimeB, TimeA).
-
-:- pred merge_consumptions_and_productions(
- assoc_list(var_rep, float)::in, assoc_list(var_rep, float)::in,
- assoc_list(var_rep, production_or_consumption)::out) is det.
-
-merge_consumptions_and_productions([], [], []).
-merge_consumptions_and_productions([],
- [Var - Time | Prods0], [Var - production(Time) | Prods]) :-
- merge_consumptions_and_productions([], Prods0, Prods).
-merge_consumptions_and_productions([Var - Time | Cons0], [],
- [Var - consumption(Time) | Cons]) :-
- merge_consumptions_and_productions(Cons0, [], Cons).
-merge_consumptions_and_productions(Cons@[ConsVar - ConsTime | Cons0],
- Prods@[ProdVar - ProdTime | Prods0], [ProdOrCons | ProdsAndCons]) :-
- ( ProdTime < ConsTime ->
- % Order earlier events first,
- ProdOrCons = ProdVar - production(ProdTime),
- merge_consumptions_and_productions(Cons, Prods0, ProdsAndCons)
- ;
- % In this branch either the consumption occurs first or the events
- % occur at the same time in which case we order consumptions first.
- ProdOrCons = ConsVar - consumption(ConsTime),
- merge_consumptions_and_productions(Cons0, Prods, ProdsAndCons)
- ).
-
-:- pred var_consumptions(float::in, pard_goal_detail::in, var_rep::in,
- pair(var_rep, float)::out) is det.
-
-var_consumptions(TimeBefore, Goal, Var, Var - Time) :-
- var_first_use_time(find_consumption, TimeBefore, Goal, Var, Time).
-
-:- pred var_productions(float::in, pard_goal_detail::in, var_rep::in,
- pair(var_rep, float)::out) is det.
-
-var_productions(TimeBefore, Goal, Var, Var - Time) :-
- var_first_use_time(find_production, TimeBefore, Goal, Var, Time).
-
-:- type find_production_or_consumption
- ---> find_production
- ; find_consumption.
-
- % var_first_use_time(FindProdOrCons, Time0, Goal, Var, Time).
- %
- % if FindProdOrCons = find_production
- % Time is Time0 + the time that Goal produces Var.
- % elif FindProdOrCons = find_consumption
- % Time is Time0 + the time that Goal first consumes Var.
- %
-:- pred var_first_use_time(find_production_or_consumption::in,
- float::in, pard_goal_detail::in, var_rep::in, float::out) is det.
-
-var_first_use_time(FindProdOrCons, TimeBefore, Goal, Var, Time) :-
- (
- FindProdOrCons = find_production,
- Map = Goal ^ goal_annotation ^ pgd_var_production_map
- ;
- FindProdOrCons = find_consumption,
- Map = Goal ^ goal_annotation ^ pgd_var_consumption_map
- ),
- map.lookup(Map, Var, LazyUse),
- Use = force(LazyUse),
- UseType = Use ^ vui_use_type,
- (
- (
- UseType = var_use_production,
- (
- FindProdOrCons = find_production
- ;
- FindProdOrCons = find_consumption,
- unexpected($module, $pred,
- "Found production when looking for consumption")
- )
- ;
- UseType = var_use_consumption,
- (
- FindProdOrCons = find_production,
- unexpected($module, $pred,
- "Found consumption when looking for production")
- ;
- FindProdOrCons = find_consumption
- )
- ),
- UseTime = Use ^ vui_cost_until_use
- ;
- UseType = var_use_other,
- % The analysis didn't recognise the instantiation here, so use a
- % conservative default for the production time.
- % XXX: How often does this occur?
- (
- FindProdOrCons = find_production,
- UseTime = goal_cost_get_percall(Goal ^ goal_annotation ^ pgd_cost)
- ;
- FindProdOrCons = find_consumption,
- UseTime = 0.0
- )
- ),
- Time = TimeBefore + UseTime.
-
%----------------------------------------------------------------------------%
:- pred pardgoal_consumed_vars_accum(pard_goal_detail::in,
@@ -2007,825 +683,11 @@
RefedVars = Goal ^ goal_annotation ^ pgd_inst_map_info ^ im_consumed_vars,
set.union(RefedVars, !Vars).
-can_parallelise_goal(Goal) :-
- Detism = Goal ^ goal_detism_rep,
- ( Detism = det_rep
- ; Detism = cc_multidet_rep
- ).
- % XXX We would check purity here except that purity information is not
- % present in the bytecode.
-
-:- pred goal_cost_above_par_threshold(implicit_parallelism_info::in,
- goal_cost_csq::in) is semidet.
-
-goal_cost_above_par_threshold(Info, Cost) :-
- goal_cost_get_calls(Cost) > 0,
- PercallCost = goal_cost_get_percall(Cost),
- PercallCost > float(Info ^ ipi_opts ^ cpcp_call_site_threshold).
-
-:- pred atomic_pard_goal_type(implicit_parallelism_info::in,
- list(goal_path_step)::in, atomic_goal_rep::in, inst_map_info::in,
- pard_goal_type::out, cord(message)::out) is det.
-
-atomic_pard_goal_type(Info, RevGoalPathSteps, AtomicGoal, InstMapInfo,
- GoalType, !:Messages) :-
- !:Messages = cord.empty,
- InstMapBefore = InstMapInfo ^ im_before,
- InstMapAfter = InstMapInfo ^ im_after,
- atomic_goal_is_call(AtomicGoal, IsCall),
- (
- IsCall = atomic_goal_is_trivial,
- GoalType = pgt_other_atomic_goal
- ;
- IsCall = atomic_goal_is_call(Args),
- % Lookup var use information.
- map.lookup(Info ^ ipi_call_sites, rgp(RevGoalPathSteps), CallSite),
- list.map_foldl(compute_var_modes(InstMapBefore, InstMapAfter),
- Args, VarsAndModes, 0, _),
- GoalType = pgt_call(VarsAndModes, CallSite)
- ).
-
-:- pred atomic_pard_goal_cost(implicit_parallelism_info::in,
- list(goal_path_step)::in, coverage_info::in, atomic_goal_rep::in,
- goal_cost_csq::out) is det.
-
-atomic_pard_goal_cost(Info, RevGoalPathSteps, Coverage, AtomicGoal, Cost) :-
- atomic_goal_is_call(AtomicGoal, IsCall),
- (
- IsCall = atomic_goal_is_trivial,
- get_coverage_before_det(Coverage, Calls),
- Cost = atomic_goal_cost(Calls)
- ;
- IsCall = atomic_goal_is_call(_),
- RevGoalPath = rgp(RevGoalPathSteps),
- map.lookup(Info ^ ipi_call_sites, RevGoalPath, CallSite),
- (
- cost_and_callees_is_recursive(Info ^ ipi_clique, CallSite),
- map.search(Info ^ ipi_rec_call_sites, RevGoalPath, RecCost)
- ->
- CSCost = RecCost
- ;
- CSCost = CallSite ^ cac_cost
- ),
- Cost = call_goal_cost(CSCost)
- ).
-
-:- pred compute_var_modes(inst_map::in, inst_map::in,
- var_rep::in, var_and_mode::out, int::in, int::out) is det.
-
-compute_var_modes(InstMapBefore, InstMapAfter, Arg, VarAndMode, !ArgNum) :-
- var_get_mode(InstMapBefore, InstMapAfter, Arg, Mode),
- VarAndMode = var_and_mode(Arg, Mode),
- !:ArgNum = !.ArgNum + 1.
-
-:- pred atomic_goal_build_use_map(atomic_goal_rep::in,
- list(goal_path_step)::in, implicit_parallelism_info::in,
- var_use_type::in, var_rep::in,
- map(var_rep, lazy(var_use_info))::in,
- map(var_rep, lazy(var_use_info))::out) is det.
-
-atomic_goal_build_use_map(AtomicGoal, RevGoalPathSteps, Info, VarUseType, Var,
- !Map) :-
- atomic_goal_is_call(AtomicGoal, IsCall),
- (
- IsCall = atomic_goal_is_trivial,
- (
- VarUseType = var_use_consumption,
- CostUntilUse = 0.0
- ;
- ( VarUseType = var_use_production
- ; VarUseType = var_use_other
- ),
- CostUntilUse = 1.0
- ),
- LazyUse = val(var_use_info(CostUntilUse, 1.0, VarUseType))
- ;
- IsCall = atomic_goal_is_call(Args),
- LazyUse = delay(
- (func) = compute_var_use_lazy(Info, RevGoalPathSteps, Var,
- Args, VarUseType))
- ),
- svmap.det_insert(Var, LazyUse, !Map).
-
-:- func compute_var_use_lazy(implicit_parallelism_info, list(goal_path_step),
- var_rep, list(var_rep), var_use_type) = var_use_info.
-
-compute_var_use_lazy(Info, RevGoalPathSteps, Var, Args, VarUseType) = Use :-
- CliquePtr = Info ^ ipi_clique,
- RevGoalPath = rgp(RevGoalPathSteps),
- map.lookup(Info ^ ipi_call_sites, RevGoalPath, CostAndCallee),
- (
- cost_and_callees_is_recursive(CliquePtr, CostAndCallee),
- map.search(Info ^ ipi_rec_call_sites, RevGoalPath, RecCost)
- ->
- Cost = RecCost
- ;
- Cost = CostAndCallee ^ cac_cost
- ),
-
- solutions(
- compute_var_use_lazy_arg(Info, Var, Args, CostAndCallee,
- Cost, VarUseType),
- Uses),
- (
- VarUseType = var_use_consumption,
- Uses = [FirstUse | OtherUses],
- list.foldl(earliest_use, OtherUses, FirstUse, Use)
- ;
- ( VarUseType = var_use_production
- ; VarUseType = var_use_other
- ),
- (
- Uses = [Use]
- ;
- Uses = [_, _ | _],
- unexpected($module, $pred, "Too many solutions ")
- )
- ).
-
-:- pred earliest_use(var_use_info::in, var_use_info::in, var_use_info::out)
- is det.
-
-earliest_use(A, B, Ealiest) :-
- TimeA = A ^ vui_cost_until_use,
- TimeB = B ^ vui_cost_until_use,
- ( TimeA < TimeB ->
- Ealiest = A
- ;
- Ealiest = B
- ).
-
-:- pred compute_var_use_lazy_arg(implicit_parallelism_info::in, var_rep::in,
- list(var_rep)::in, cost_and_callees::in, cs_cost_csq::in, var_use_type::in,
- var_use_info::out) is multi.
-
-compute_var_use_lazy_arg(Info, Var, Args, CostAndCallee, Cost, VarUseType,
- Use) :-
- ( 0.0 < cs_cost_get_calls(Cost) ->
- CostPercall = cs_cost_get_percall(Cost),
- ( list.member_index0(Var, Args, ArgNum) ->
- HigherOrder = CostAndCallee ^ cac_call_site_is_ho,
- (
- HigherOrder = higher_order_call,
- % We cannot push signals or waits into higher order calls.
- pessimistic_var_use_info(VarUseType, CostPercall, Use)
- ;
- HigherOrder = first_order_call,
- ( singleton_set(CostAndCallee ^ cac_callees, CalleePrime) ->
- Callee = CalleePrime
- ;
- unexpected($module, $pred,
- "first-order call site has wrong number of CSDs")
- ),
- CSDPtr = Callee ^ c_csd,
- RecursionType = Info ^ ipi_recursion_type,
- recursion_type_get_interesting_parallelisation_depth(
- RecursionType, MaybeCurDepth),
- compute_var_use_2(Info, ArgNum, RecursionType, MaybeCurDepth,
- VarUseType, CostPercall, CSDPtr, Use, Messages),
- trace [io(!IO)] (
- stderr_stream(Stderr, !IO),
- write_out_messages(Stderr, Messages, !IO)
- )
- )
- ;
- Use = var_use_info(0.0, CostPercall, VarUseType),
- ( VarUseType = var_use_consumption ->
- true
- ;
- unexpected($module, $pred,
- "Var use type most be consumption if " ++
- "\\+ member(Var, Args)")
- )
- )
- ;
- % This call site is never called.
- pessimistic_var_use_info(VarUseType, 0.0, Use)
- ).
-
-:- pred compute_var_use_2(implicit_parallelism_info::in, int::in,
- recursion_type::in, maybe(recursion_depth)::in, var_use_type::in,
- float::in, call_site_dynamic_ptr::in, var_use_info::out,
- cord(message)::out) is det.
-
-compute_var_use_2(Info, ArgNum, RecursionType, MaybeCurDepth, VarUseType, Cost,
- CSDPtr, Use, !:Messages) :-
- !:Messages = empty,
- Deep = Info ^ ipi_deep,
- CliquePtr = Info ^ ipi_clique,
- implicit_par_info_intermodule_var_use(Info, FollowCallsAcrossModules),
- VarUseOptions = var_use_options(Deep, FollowCallsAcrossModules,
- VarUseType),
- call_site_dynamic_var_use_info(CliquePtr, CSDPtr, ArgNum,
- RecursionType, MaybeCurDepth, Cost, set.init, VarUseOptions, MaybeUse),
- (
- MaybeUse = ok(Use)
- ;
- MaybeUse = error(Error),
- pessimistic_var_use_info(VarUseType, Cost, Use),
- append_message(pl_csd(CSDPtr),
- warning_cannot_compute_first_use_time(Error),
- !Messages)
- ).
-
-:- pred goal_build_use_map(goal_rep(goal_id)::in,
- list(goal_path_step)::in, goal_cost_csq::in, implicit_parallelism_info::in,
- var_use_type::in, var_rep::in,
- map(var_rep, lazy(var_use_info))::in,
- map(var_rep, lazy(var_use_info))::out) is det.
-
-goal_build_use_map(Goal, RevGoalPathSteps, Cost, Info, VarUseType, Var, !Map) :-
- LazyUse = delay((func) = compute_goal_var_use_lazy(Goal, RevGoalPathSteps,
- Cost, Info, VarUseType, Var)),
- svmap.det_insert(Var, LazyUse, !Map).
-
-:- func compute_goal_var_use_lazy(goal_rep(goal_id), list(goal_path_step),
- goal_cost_csq, implicit_parallelism_info, var_use_type, var_rep)
- = var_use_info.
-
-compute_goal_var_use_lazy(Goal, RevGoalPathSteps, Cost, Info, VarUseType, Var)
- = Use :-
- Info = implicit_parallelism_info(Deep, _ProgRep, _Params, CliquePtr,
- CallSiteMap, RecursiveCallSiteMap, ContainingGoalMap, CoverageArray,
- _InstMapArray, RecursionType, _VarTable, _ProcLabel),
- CostPercall = goal_cost_get_percall(Cost),
- (
- ( RecursionType = rt_not_recursive
- ; RecursionType = rt_single(_, _, _, _, _)
- ),
- recursion_type_get_interesting_parallelisation_depth(RecursionType,
- yes(RecDepth)),
- implicit_par_info_intermodule_var_use(Info, FollowCallsAcrossModules),
- VarUseOptions = var_use_options(Deep, FollowCallsAcrossModules,
- VarUseType),
- var_first_use(CliquePtr, CallSiteMap, RecursiveCallSiteMap,
- ContainingGoalMap, CoverageArray, RecursionType, RecDepth, Goal,
- rgp(RevGoalPathSteps), CostPercall, Var, VarUseOptions, Use)
- ;
- ( RecursionType = rt_divide_and_conquer(_, _)
- ; RecursionType = rt_mutual_recursion(_)
- ; RecursionType = rt_other(_)
- ; RecursionType = rt_errors(_)
- ),
- % var_first_use doesn't work for these recursion types.
- pessimistic_var_use_info(VarUseType, CostPercall, Use),
- append_message(pl_clique(CliquePtr),
- warning_cannot_compute_first_use_time(
- "Recursion type unknown for var_first_use/12"),
- empty, Messages),
- trace [io(!IO)] (
- io.stderr_stream(Stderr, !IO),
- write_out_messages(Stderr, Messages, !IO)
- )
- ).
-
-:- pred implicit_par_info_intermodule_var_use(implicit_parallelism_info::in,
- intermodule_var_use::out) is det.
-
-implicit_par_info_intermodule_var_use(Info, FollowCallsAcrossModules) :-
- IntermoduleVarUse = Info ^ ipi_opts ^ cpcp_intermodule_var_use,
- (
- IntermoduleVarUse = yes,
- FollowCallsAcrossModules = follow_any_call
- ;
- IntermoduleVarUse = no,
- ProcLabel = Info ^ ipi_proc_label,
- ( ProcLabel = str_ordinary_proc_label(_, _, Module, _, _, _)
- ; ProcLabel = str_special_proc_label(_, _, Module, _, _, _)
- ),
- FollowCallsAcrossModules = follow_calls_into_module(Module)
- ).
-
-:- pred recursion_type_get_interesting_parallelisation_depth(
- recursion_type, maybe(recursion_depth)).
-:- mode recursion_type_get_interesting_parallelisation_depth(
- in(recursion_type_known_costs), out(maybe_yes(ground))) is det.
-:- mode recursion_type_get_interesting_parallelisation_depth(
- in, out) is det.
-
-recursion_type_get_interesting_parallelisation_depth(RecursionType,
- MaybeDepth) :-
- (
- RecursionType = rt_not_recursive,
- MaybeDepth = yes(recursion_depth_from_float(0.0))
- ;
- RecursionType = rt_single(_, _, _DepthF, _, _),
- % The interesting recursion depth is at the bottom of the recursion, if
- % we can't parallelise here then there's no point parallelising the
- % loop in general.
- % XXX: Update metrics to understand that this is a loop.
- MaybeDepth = yes(recursion_depth_from_float(2.0))
- ;
- ( RecursionType = rt_divide_and_conquer(_, _)
- ; RecursionType = rt_mutual_recursion(_)
- ; RecursionType = rt_other(_)
- ; RecursionType = rt_errors(_)
- ),
- MaybeDepth = no
- ).
-
-:- pred var_get_mode(inst_map::in, inst_map::in, var_rep::in,
- var_mode_rep::out) is det.
-
-var_get_mode(InstMapBefore, InstMapAfter, VarRep, VarModeRep) :-
- inst_map_get(InstMapBefore, VarRep, InstBefore, _),
- inst_map_get(InstMapAfter, VarRep, InstAfter, _),
- VarModeRep = var_mode_rep(InstBefore, InstAfter).
-
- % Transform a goal in a conjunction into a pard_goal.
- %
-:- pred goal_to_pard_goal(implicit_parallelism_info::in,
- list(goal_path_step)::in, goal_rep(goal_id)::in,
- pard_goal_detail::out, cord(message)::in, cord(message)::out) is det.
-
-goal_to_pard_goal(Info, RevGoalPathSteps, !Goal, !Messages) :-
- !.Goal = goal_rep(GoalExpr0, Detism, GoalId),
- InstMapInfo = get_goal_attribute_det(Info ^ ipi_inst_map_array, GoalId),
- Coverage = get_goal_attribute_det(Info ^ ipi_coverage_array, GoalId),
- get_coverage_before_det(Coverage, Before),
- (
- (
- GoalExpr0 = conj_rep(Conjs0),
- list.map_foldl2(conj_to_pard_goals(Info, RevGoalPathSteps),
- Conjs0, Conjs, 1, _, !Messages),
- conj_calc_cost(Conjs, Before, Cost),
- GoalExpr = conj_rep(Conjs)
- ;
- GoalExpr0 = disj_rep(Disjs0),
- list.map_foldl2(disj_to_pard_goals(Info, RevGoalPathSteps),
- Disjs0, Disjs, 1, _, !Messages),
- disj_calc_cost(Disjs, Before, Cost),
- GoalExpr = disj_rep(Disjs)
- ;
- GoalExpr0 = switch_rep(Var, CanFail, Cases0),
- list.map_foldl2(case_to_pard_goal(Info, RevGoalPathSteps),
- Cases0, Cases, 1, _, !Messages),
- switch_calc_cost(Cases, Before, Cost),
- GoalExpr = switch_rep(Var, CanFail, Cases)
- ;
- GoalExpr0 = ite_rep(Cond0, Then0, Else0),
- goal_to_pard_goal(Info, [step_ite_cond | RevGoalPathSteps],
- Cond0, Cond, !Messages),
- goal_to_pard_goal(Info, [step_ite_then | RevGoalPathSteps],
- Then0, Then, !Messages),
- goal_to_pard_goal(Info, [step_ite_else | RevGoalPathSteps],
- Else0, Else, !Messages),
- ite_calc_cost(Cond, Then, Else, Cost),
- GoalExpr = ite_rep(Cond, Then, Else)
- ;
- GoalExpr0 = negation_rep(SubGoal0),
- goal_to_pard_goal(Info, [step_neg | RevGoalPathSteps],
- SubGoal0, SubGoal, !Messages),
- Cost = SubGoal ^ goal_annotation ^ pgd_cost,
- GoalExpr = negation_rep(SubGoal)
- ;
- GoalExpr0 = scope_rep(SubGoal0, MaybeCut),
- goal_to_pard_goal(Info, [step_scope(MaybeCut) | RevGoalPathSteps],
- SubGoal0, SubGoal, !Messages),
- Cost = SubGoal ^ goal_annotation ^ pgd_cost,
- GoalExpr = scope_rep(SubGoal, MaybeCut)
- ),
- PardGoalType = pgt_non_atomic_goal,
-
- BoundVars = to_sorted_list(InstMapInfo ^ im_bound_vars),
- list.foldl(
- goal_build_use_map(!.Goal, RevGoalPathSteps, Cost, Info,
- var_use_production),
- BoundVars, map.init, ProductionUseMap),
- ConsumedVars = to_sorted_list(InstMapInfo ^ im_consumed_vars),
- list.foldl(
- goal_build_use_map(!.Goal, RevGoalPathSteps, Cost, Info,
- var_use_consumption),
- ConsumedVars, map.init, ConsumptionUseMap)
- ;
- GoalExpr0 = atomic_goal_rep(Context, Line, BoundVars, AtomicGoal),
- GoalExpr = atomic_goal_rep(Context, Line, BoundVars, AtomicGoal),
- atomic_pard_goal_type(Info, RevGoalPathSteps, AtomicGoal, InstMapInfo,
- PardGoalType, Messages),
- atomic_pard_goal_cost(Info, RevGoalPathSteps, Coverage, AtomicGoal,
- Cost),
-
- list.foldl(
- atomic_goal_build_use_map(AtomicGoal, RevGoalPathSteps, Info,
- var_use_production),
- BoundVars, map.init, ProductionUseMap),
- ConsumedVars = to_sorted_list(InstMapInfo ^ im_consumed_vars),
- list.foldl(
- atomic_goal_build_use_map(AtomicGoal, RevGoalPathSteps, Info,
- var_use_consumption),
- ConsumedVars, map.init, ConsumptionUseMap),
-
- !:Messages = !.Messages ++ Messages
- ),
- % XXX: The goal annotations cannot represent reasons why a goal
- % can't be parallelised, for example it could be nondet, semidet or
- % impure.
- (
- can_parallelise_goal(!.Goal),
- goal_cost_above_par_threshold(Info, Cost)
- ->
- CostAboveThreshold = cost_above_par_threshold
- ;
- CostAboveThreshold = cost_not_above_par_threshold
- ),
- PardGoalAnnotation = pard_goal_detail(PardGoalType, InstMapInfo,
- rgp(RevGoalPathSteps), Coverage, Cost, CostAboveThreshold,
- ProductionUseMap, ConsumptionUseMap),
- !:Goal = goal_rep(GoalExpr, Detism, PardGoalAnnotation).
-
-:- pred conj_to_pard_goals(implicit_parallelism_info::in,
- list(goal_path_step)::in, goal_rep(goal_id)::in,
- pard_goal_detail::out, int::in, int::out,
- cord(message)::in, cord(message)::out) is det.
-
-conj_to_pard_goals(Info, RevGoalPathSteps, !Goal, !ConjNum, !Messages) :-
- goal_to_pard_goal(Info, [step_conj(!.ConjNum) | RevGoalPathSteps],
- !Goal, !Messages),
- !:ConjNum = !.ConjNum + 1.
-
-:- pred disj_to_pard_goals(implicit_parallelism_info::in,
- list(goal_path_step)::in, goal_rep(goal_id)::in,
- pard_goal_detail::out, int::in, int::out,
- cord(message)::in, cord(message)::out) is det.
-
-disj_to_pard_goals(Info, RevGoalPathSteps, !Goal, !DisjNum, !Messages) :-
- goal_to_pard_goal(Info, [step_disj(!.DisjNum) | RevGoalPathSteps],
- !Goal, !Messages),
- !:DisjNum = !.DisjNum + 1.
-
-:- pred case_to_pard_goal(implicit_parallelism_info::in,
- list(goal_path_step)::in, case_rep(goal_id)::in,
- case_rep(pard_goal_detail_annotation)::out, int::in, int::out,
- cord(message)::in, cord(message)::out) is det.
-
-case_to_pard_goal(Info, RevGoalPathSteps, !Case, !CaseNum, !Messages) :-
- !.Case = case_rep(ConsId, OtherConsId, Goal0),
- goal_to_pard_goal(Info, [step_switch(!.CaseNum, no) | RevGoalPathSteps],
- Goal0, Goal, !Messages),
- !:CaseNum = !.CaseNum + 1,
- !:Case = case_rep(ConsId, OtherConsId, Goal).
-
-%----------------------------------------------------------------------------%
-
-:- pred conj_calc_cost(list(pard_goal_detail)::in, int::in,
- goal_cost_csq::out) is det.
-
-conj_calc_cost([], Calls, simple_goal_cost(Calls)).
-conj_calc_cost([Conj | Conjs], _, Cost) :-
- Coverage = Conj ^ goal_annotation ^ pgd_coverage,
- get_coverage_after_det(Coverage, After),
- conj_calc_cost(Conjs, After, ConjsCost),
- ConjCost = Conj ^ goal_annotation ^ pgd_cost,
- Cost = add_goal_costs_seq(ConjCost, ConjsCost).
-
-:- pred disj_calc_cost(list(pard_goal_detail)::in, int::in,
- goal_cost_csq::out) is det.
-
-disj_calc_cost([], Calls, simple_goal_cost(Calls)).
-disj_calc_cost([Disj | Disjs], _, Cost) :-
- Coverage = Disj ^ goal_annotation ^ pgd_coverage,
- get_coverage_before_and_after_det(Coverage, Before, After),
- ( Before = 0 ->
- % Avoid a divide by zero.
- Cost = dead_goal_cost
- ;
- _Successes = After,
- Failures = Before - After,
- % XXX: We assume this is a semidet disjunction
- disj_calc_cost(Disjs, Failures, FailureCost),
- DisjCost = Disj ^ goal_annotation ^ pgd_cost,
- SuccessCost = atomic_goal_cost(After),
- BranchCost = add_goal_costs_branch(Before, FailureCost, SuccessCost),
- Cost = add_goal_costs_seq(DisjCost, BranchCost)
- ).
-
-:- pred switch_calc_cost(list(case_rep(pard_goal_detail_annotation))::in,
- int::in, goal_cost_csq::out) is det.
-
-switch_calc_cost([], Calls, simple_goal_cost(Calls)).
-switch_calc_cost([Case | Cases], TotalCalls, Cost) :-
- ( TotalCalls = 0 ->
- % Avoid a divide by zero.
- Cost = dead_goal_cost
- ;
- Coverage = Case ^ cr_case_goal ^ goal_annotation ^ pgd_coverage,
- get_coverage_before_det(Coverage, CaseCalls),
- switch_calc_cost(Cases, TotalCalls - CaseCalls, CasesCost),
- CaseCost = Case ^ cr_case_goal ^ goal_annotation ^ pgd_cost,
- Cost = add_goal_costs_branch(TotalCalls, CaseCost, CasesCost)
- ).
-
-:- pred ite_calc_cost(pard_goal_detail::in, pard_goal_detail::in,
- pard_goal_detail::in, goal_cost_csq::out) is det.
-
-ite_calc_cost(Cond, Then, Else, Cost) :-
- CondCost = Cond ^ goal_annotation ^ pgd_cost,
- ThenCost = Then ^ goal_annotation ^ pgd_cost,
- ElseCost = Else ^ goal_annotation ^ pgd_cost,
- Coverage = Cond ^ goal_annotation ^ pgd_coverage,
- get_coverage_before_det(Coverage, Before),
- ThenElseCost = add_goal_costs_branch(Before, ThenCost, ElseCost),
- Cost = add_goal_costs_seq(CondCost, ThenElseCost).
-
-:- func simple_goal_cost(int) = goal_cost_csq.
-
-simple_goal_cost(Calls) = Cost :-
- ( Calls = 0 ->
- Cost = dead_goal_cost
- ;
- Cost = atomic_goal_cost(Calls)
- ).
-
%----------------------------------------------------------------------------%
%
% Useful utility predicates.
%
-create_candidate_parallel_conj_proc_report(Proc - CandidateParConjunctionProc,
- Report) :-
- CandidateParConjunctionProc = candidate_par_conjunctions_proc(VarTable,
- PushGoals, CandidateParConjunctions),
- print_proc_label_to_string(Proc, ProcString),
- list.map(create_push_goal_report, PushGoals, PushGoalReports),
- list.map(create_candidate_parallel_conj_report(VarTable),
- CandidateParConjunctions, CandidateParConjunctionReports),
- Header = string.format(
- " %s\n",
- [s(ProcString)]),
- Report = cord.singleton(Header) ++
- cord_list_to_cord(PushGoalReports) ++
- cord.singleton("\n") ++
- cord_list_to_cord(CandidateParConjunctionReports).
-
-:- pred create_push_goal_report(push_goal::in, cord(string)::out) is det.
-
-create_push_goal_report(PushGoal, Report) :-
- PushGoal = push_goal(PushGoalPathStr, Lo, Hi, PushedGoalPathStrs),
- string.format("\n PushGoal: %s, lo %d, hi %d\n",
- [s(PushGoalPathStr), i(Lo), i(Hi)], HeadPushGoalStr),
- FormatPushedGoals = (
- func(PushedGoalPathStr) =
- string.format(" %s\n", [s(PushedGoalPathStr)])
- ),
- TailPushGoalStrs = list.map(FormatPushedGoals, PushedGoalPathStrs),
- Report = cord.from_list([HeadPushGoalStr | TailPushGoalStrs]).
-
-:- pred create_candidate_parallel_conj_report(var_table::in,
- candidate_par_conjunction(pard_goal)::in, cord(string)::out) is det.
-
-create_candidate_parallel_conj_report(VarTable, CandidateParConjunction,
- Report) :-
- CandidateParConjunction = candidate_par_conjunction(GoalPathString,
- MaybePushGoal, FirstConjNum, IsDependent, GoalsBefore, GoalsBeforeCost,
- Conjs, GoalsAfter, GoalsAfterCost, ParExecMetrics),
- ParExecMetrics = parallel_exec_metrics(NumCalls, SeqTime, ParTime,
- SparkCost, BarrierCost, SignalsCost, WaitsCost, FirstConjDeadTime,
- FutureDeadTime),
- ParOverheads = parallel_exec_metrics_get_overheads(ParExecMetrics),
- (
- IsDependent = conjuncts_are_independent,
- DependanceString = "no"
- ;
- IsDependent = conjuncts_are_dependent(Vars),
- map(lookup_var_name(VarTable), Vars, VarNames),
- VarsString = join_list(", ", to_sorted_list(VarNames)),
- DependanceString = format("on %s", [s(VarsString)])
- ),
- Speedup = parallel_exec_metrics_get_speedup(ParExecMetrics),
- TimeSaving = parallel_exec_metrics_get_time_saving(ParExecMetrics),
- TotalDeadTime = FirstConjDeadTime + FutureDeadTime,
-
- string.format(
- " Path: %s\n",
- [s(GoalPathString)], Header1Str),
- Header1 = cord.singleton(Header1Str),
-
- (
- MaybePushGoal = no,
- Header2 = cord.empty
- ;
- MaybePushGoal = yes(PushGoal),
- PushGoal = push_goal(PushGoalPathStr, Lo, Hi, PushedGoalPathStrs),
- string.format(" PushGoal: %s, lo %d, hi %d\n",
- [s(PushGoalPathStr), i(Lo), i(Hi)], HeadPushGoalStr),
- FormatPushedGoals = (
- func(PushedGoalPathStr) =
- string.format(" %s\n", [s(PushedGoalPathStr)])
- ),
- TailPushGoalStrs = list.map(FormatPushedGoals, PushedGoalPathStrs),
- Header2 = cord.from_list([HeadPushGoalStr | TailPushGoalStrs])
- ),
-
- string.format(
- " Dependent: %s\n" ++
- " NumCalls: %s\n" ++
- " SeqTime: %s\n" ++
- " ParTime: %s\n" ++
- " SparkCost: %s\n" ++
- " BarrierCost: %s\n" ++
- " SignalsCost: %s\n" ++
- " WaitsCost: %s\n" ++
- " ParOverheads total: %s\n" ++
- " Speedup: %s\n" ++
- " Time saving: %s\n" ++
- " First conj dead time: %s\n" ++
- " Future dead time: %s\n" ++
- " Total dead time: %s\n\n",
- [s(DependanceString),
- s(commas(NumCalls)),
- s(two_decimal_fraction(SeqTime)),
- s(two_decimal_fraction(ParTime)),
- s(two_decimal_fraction(SparkCost)),
- s(two_decimal_fraction(BarrierCost)),
- s(two_decimal_fraction(SignalsCost)),
- s(two_decimal_fraction(WaitsCost)),
- s(two_decimal_fraction(ParOverheads)),
- s(four_decimal_fraction(Speedup)),
- s(two_decimal_fraction(TimeSaving)),
- s(two_decimal_fraction(FirstConjDeadTime)),
- s(two_decimal_fraction(FutureDeadTime)),
- s(two_decimal_fraction(TotalDeadTime))],
- Header2Str),
- Header3 = cord.singleton(Header2Str),
-
- ( rev_goal_path_from_string(GoalPathString, RevGoalPath) ->
- RevGoalPath = rgp(RevGoalPathSteps)
- ;
- unexpected($module, $pred, "couldn't parse goal path")
- ),
- some [!ConjNum] (
- !:ConjNum = FirstConjNum,
- format_sequential_conjunction(VarTable, 4, RevGoalPathSteps,
- GoalsBefore, GoalsBeforeCost, !.ConjNum, ReportGoalsBefore0),
- ReportGoalsBefore = indent(3) ++ singleton("Goals before:\n") ++
- ReportGoalsBefore0,
-
- !:ConjNum = !.ConjNum + length(GoalsBefore),
- format_parallel_conjunction(VarTable, 4, RevGoalPathSteps,
- !.ConjNum, Conjs, ReportParConj0),
- ReportParConj = indent(3) ++ singleton("Parallel conjunction:\n") ++
- ReportParConj0,
-
- !:ConjNum = !.ConjNum + 1,
- format_sequential_conjunction(VarTable, 4, RevGoalPathSteps,
- GoalsAfter, GoalsAfterCost, !.ConjNum, ReportGoalsAfter0),
- ReportGoalsAfter = indent(3) ++ singleton("Goals after:\n") ++
- ReportGoalsAfter0
- ),
- Report = Header1 ++ Header2 ++ Header3 ++ ReportGoalsBefore ++ nl
- ++ ReportParConj ++ nl ++ ReportGoalsAfter ++ nl.
-
-:- pred format_parallel_conjunction(var_table::in, int::in,
- list(goal_path_step)::in, int::in,
- list(seq_conj(pard_goal))::in, cord(string)::out) is det.
-
-format_parallel_conjunction(VarTable, Indent, RevGoalPathSteps, ConjNum, Conjs,
- !:Report) :-
- IndentStr = indent(Indent),
- !:Report = IndentStr ++ singleton("(\n"),
- format_parallel_conjuncts(VarTable, Indent,
- [step_conj(ConjNum) | RevGoalPathSteps], 1, Conjs, !Report).
-
-:- pred format_parallel_conjuncts(var_table::in, int::in,
- list(goal_path_step)::in, int::in, list(seq_conj(pard_goal))::in,
- cord(string)::in, cord(string)::out) is det.
-
-format_parallel_conjuncts(_VarTable, Indent, _RevGoalPathSteps, _ConjNum0,
- [], !Report) :-
- IndentStr = indent(Indent),
- !:Report = snoc(!.Report ++ IndentStr, ")\n").
-format_parallel_conjuncts(VarTable, Indent, RevGoalPathSteps, ConjNum0,
- [Conj | Conjs], !Report) :-
- Conj = seq_conj(Goals),
- (
- Goals = [],
- unexpected($module, $pred, "empty conjunct in parallel conjunction")
- ;
- Goals = [Goal | GoalsTail],
- RevInnerGoalPathSteps = [step_conj(ConjNum0) | RevGoalPathSteps],
- (
- GoalsTail = [],
- % A singleton conjunction gets printed as a single goal.
- print_goal_to_strings(print_goal_info(id, VarTable), Indent + 1,
- RevInnerGoalPathSteps, Goal, ConjReport)
- ;
- GoalsTail = [_ | _],
- Cost = foldl(
- (func(GoalI, Acc) =
- Acc + GoalI ^ goal_annotation ^ pga_cost_percall),
- Goals, 0.0),
- format_sequential_conjunction(VarTable, Indent + 1,
- RevInnerGoalPathSteps, Goals, Cost, 1, ConjReport)
- )
- ),
- !:Report = !.Report ++ ConjReport,
- (
- Conjs = []
- ;
- Conjs = [_ | _],
- !:Report = snoc(!.Report ++ indent(Indent), "&\n")
- ),
- ConjNum = ConjNum0 + 1,
- format_parallel_conjuncts(VarTable, Indent, RevGoalPathSteps, ConjNum,
- Conjs, !Report).
-
-:- pred format_sequential_conjunction(var_table::in, int::in,
- list(goal_path_step)::in, list(pard_goal)::in, float::in, int::in,
- cord(string)::out) is det.
-
-format_sequential_conjunction(VarTable, Indent, RevGoalPathSteps, Goals, Cost,
- FirstConjNum, !:Report) :-
- !:Report = empty,
- ( FirstConjNum = 1 ->
- !:Report = !.Report ++
- indent(Indent) ++
- singleton(format("%% conjunction: %s",
- [s(rev_goal_path_to_string(rgp(RevGoalPathSteps)))])) ++
- nl_indent(Indent) ++
- singleton(format("%% Cost: %s",
- [s(two_decimal_fraction(Cost))])) ++
- nl ++ nl
- ;
- true
- ),
- format_sequential_conjuncts(VarTable, Indent, RevGoalPathSteps, Goals,
- FirstConjNum, _, !Report).
-
-:- pred format_sequential_conjuncts(var_table::in, int::in,
- list(goal_path_step)::in, list(pard_goal)::in, int::in, int::out,
- cord(string)::in, cord(string)::out) is det.
-
-format_sequential_conjuncts(_, _, _, [], !ConjNum, !Report).
-format_sequential_conjuncts(VarTable, Indent, RevGoalPathSteps, [Conj | Conjs],
- !ConjNum, !Report) :-
- print_goal_to_strings(print_goal_info(id, VarTable), Indent,
- [step_conj(!.ConjNum) | RevGoalPathSteps], Conj, ConjReport),
- !:Report = !.Report ++ ConjReport,
- !:ConjNum = !.ConjNum + 1,
- (
- Conjs = []
- ;
- Conjs = [_ | _],
- !:Report = !.Report ++ indent(Indent) ++ singleton(",\n"),
- format_sequential_conjuncts(VarTable, Indent, RevGoalPathSteps, Conjs,
- !ConjNum, !Report)
- ).
-
-:- instance goal_annotation(pard_goal_annotation) where [
- pred(print_goal_annotation_to_strings/3) is format_pard_goal_annotation
-].
-
-:- pred format_pard_goal_annotation(var_table::in, pard_goal_annotation::in,
- cord(cord(string))::out) is det.
-
-format_pard_goal_annotation(VarTable, GoalAnnotation, Report) :-
- GoalAnnotation = pard_goal_annotation(CostPercall, CostAboveThreshold,
- Productions, Consumptions),
- (
- CostAboveThreshold = cost_above_par_threshold,
- CostAboveThresholdStr = "above threshold"
- ;
- CostAboveThreshold = cost_not_above_par_threshold,
- CostAboveThresholdStr = "not above threshold"
- ),
- CostLine = singleton(format("cost: %s (%s)",
- [s(two_decimal_fraction(CostPercall)), s(CostAboveThresholdStr)])),
- format_var_use_report(VarTable, productions, Productions,
- ProductionsReport),
- format_var_use_report(VarTable, consumptions, Consumptions,
- ConsumptionsReport),
- Report = singleton(CostLine) ++ ProductionsReport ++ ConsumptionsReport.
-
-:- func productions = string.
-
-productions = "Productions".
-
-:- func consumptions = string.
-
-consumptions = "Consumptions".
-
-:- pred format_var_use_report(var_table::in, string::in,
- assoc_list(var_rep, float)::in, cord(cord(string))::out) is det.
-
-format_var_use_report(VarTable, Label, List, Report) :-
- (
- List = [_ | _],
- list.map(format_var_use_line(VarTable), List, Lines),
- Report = singleton(singleton(Label ++ ":")) ++ cord.from_list(Lines)
- ;
- List = [],
- Report = empty
- ).
-
-:- pred format_var_use_line(var_table::in, pair(var_rep, float)::in,
- cord(string)::out) is det.
-
-format_var_use_line(VarTable, Var - Use, singleton(String)) :-
- format(" %s: %s", [s(VarName), s(two_decimal_fraction(Use))], String),
- lookup_var_name(VarTable, Var, VarName).
-
-%-----------------------------------------------------------------------------%
-
:- pred debug_cliques_below_threshold(candidate_child_clique::in,
io::di, io::uo) is det.
Index: deep_profiler/autopar_search_goals.m
===================================================================
RCS file: deep_profiler/autopar_search_goals.m
diff -N deep_profiler/autopar_search_goals.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ deep_profiler/autopar_search_goals.m 27 Jan 2011 05:21:27 -0000
@@ -0,0 +1,1043 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2011 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: autopar_search_goals.m
+% Authors: pbone, zs.
+%
+% This module contains the code for searching goals for conjunctions worth
+% parallelising.
+%
+%-----------------------------------------------------------------------------%
+
+:- module mdprof_fb.automatic_parallelism.autopar_search_goals.
+:- interface.
+
+:- import_module mdbcomp.
+:- import_module mdbcomp.feedback.
+:- import_module mdbcomp.feedback.automatic_parallelism.
+:- import_module mdbcomp.goal_path.
+:- import_module mdbcomp.program_representation.
+:- import_module mdprof_fb.automatic_parallelism.autopar_types.
+:- import_module message.
+
+:- import_module cord.
+:- import_module list.
+
+%-----------------------------------------------------------------------------%
+
+:- pred goal_get_conjunctions_worth_parallelising(
+ implicit_parallelism_info::in, list(goal_path_step)::in,
+ pard_goal_detail::in, pard_goal_detail::out,
+ cord(candidate_par_conjunction(pard_goal_detail))::out,
+ cord(push_goal)::out, cord(pard_goal_detail)::out, cord(message)::out)
+ is det.
+
+ % Transform a goal in a conjunction into a pard_goal.
+ %
+:- pred goal_to_pard_goal(implicit_parallelism_info::in,
+ list(goal_path_step)::in, goal_rep(goal_id)::in,
+ pard_goal_detail::out, cord(message)::in, cord(message)::out) is det.
+
+ % Check if it is appropriate to parallelise this call. That is it must be
+ % model_det and have a cost above the call site cost threshold.
+ % XXX probable bug: the cost criterion is implemented elsewhere.
+ %
+:- pred can_parallelise_goal(goal_rep(T)::in) is semidet.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module analysis_utils.
+:- import_module coverage.
+:- import_module mdprof_fb.automatic_parallelism.autopar_costs.
+:- import_module mdprof_fb.automatic_parallelism.autopar_find_best_par.
+:- import_module mdprof_fb.automatic_parallelism.autopar_reports.
+:- import_module mdprof_fb.automatic_parallelism.autopar_search_callgraph.
+:- import_module measurements.
+:- import_module program_representation_utils.
+:- import_module report.
+:- import_module var_use_analysis.
+
+:- import_module assoc_list.
+:- import_module float.
+:- import_module int.
+:- import_module io.
+:- import_module lazy.
+:- import_module map.
+:- import_module maybe.
+:- import_module pair.
+:- import_module require.
+:- import_module set.
+:- import_module string.
+:- import_module svmap.
+
+%----------------------------------------------------------------------------%
+
+goal_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
+ !Goal, Candidates, Pushes, Singles, Messages) :-
+ !.Goal = goal_rep(GoalExpr0, DetismRep, Annotation0),
+ Coverage = Annotation0 ^ pgd_coverage,
+ get_coverage_before_det(Coverage, Calls),
+ (
+ (
+ GoalExpr0 = conj_rep(Conjs0),
+ conj_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
+ Conjs0, Conjs, 1, [], SinglesSoFar, [], RevSingleCands,
+ cord.empty, CandidatesBelow, cord.empty, PushesBelow,
+ cord.empty, MessagesBelow),
+ GoalExpr = conj_rep(Conjs),
+ list.reverse(RevSingleCands, SingleCands),
+ (
+ SingleCands = [],
+ Candidates = CandidatesBelow,
+ Pushes = PushesBelow,
+ Singles = cord.from_list(SinglesSoFar),
+ Messages = MessagesBelow,
+ Cost = Annotation0 ^ pgd_cost
+ ;
+ SingleCands = [CostlyIndex - SinglesBefore],
+ push_and_build_candidate_conjunctions(Info, RevGoalPathSteps,
+ Conjs, CostlyIndex, SinglesBefore,
+ MessagesThisLevel, CandidatesThisLevel),
+ (
+ CandidatesThisLevel = [],
+ Candidates = CandidatesBelow,
+ Pushes = PushesBelow,
+ % No candidate was built, pass our singles to our caller.
+ Singles = cord.from_list(SinglesSoFar)
+ ;
+ CandidatesThisLevel = [FirstCandidate | LaterCandidates],
+ merge_same_level_pushes(FirstCandidate, LaterCandidates,
+ PushThisLevel),
+ Candidates = CandidatesBelow ++
+ cord.from_list(CandidatesThisLevel),
+ Pushes = cord.snoc(PushesBelow, PushThisLevel),
+ % Any single expensive goals inside this conjunction
+ % cannot have later expensive goals pushed next to them
+ % without reanalysis of the whole goal, which we do not do.
+ Singles = cord.empty
+ ),
+ Messages = MessagesBelow ++ MessagesThisLevel,
+ % XXX We should update the cost for CandidatesThisLevel.
+ Cost = Annotation0 ^ pgd_cost
+ ;
+ SingleCands = [_, _ | _],
+ assoc_list.keys(SingleCands, CostlyIndexes),
+ build_candidate_conjunction(Info, RevGoalPathSteps,
+ Conjs, CostlyIndexes, MessagesThisLevel, MaybeCandidate),
+ Pushes = PushesBelow,
+ Messages = MessagesBelow ++ MessagesThisLevel,
+ (
+ MaybeCandidate = yes(Candidate),
+ Candidates = cord.cons(Candidate, CandidatesBelow),
+ ExecMetrics = Candidate ^ cpc_par_exec_metrics,
+ Cost = call_goal_cost(ExecMetrics ^ pem_num_calls,
+ ExecMetrics ^ pem_par_time),
+ % We parallelized this conjunction. Trying to push a goal
+ % after it next to a costly goal inside it would require
+ % pushing that following goal into a conjunct of this
+ % parallel conjunction. Due to our current prohibition
+ % on reordering, that costly goal would have to be inside
+ % the last parallel conjunct. That would require replacing
+ % Candidate with another candidate that includes the
+ % following goal. While that is in theory doable, it is not
+ % doable *here*, since at this point yet know whether
+ % a following costly goal even exists. On the other hand,
+ % any later part of this algorithm that does discover
+ % a later costly goal won't know how to redo this overlap
+ % calculation. We avoid the problem by pretending that this
+ % conjunction contains no expensive goals.
+ Singles = cord.empty
+ ;
+ MaybeCandidate = no,
+ Candidates = CandidatesBelow,
+ Singles = cord.from_list(SinglesSoFar),
+ Cost = Annotation0 ^ pgd_cost
+ )
+ )
+ ;
+ GoalExpr0 = disj_rep(Disjs0),
+ list.map_foldl5(
+ disj_get_conjunctions_worth_parallelising(Info,
+ RevGoalPathSteps),
+ Disjs0, Disjs, 1, _, cord.empty, Candidates,
+ cord.empty, Pushes, cord.empty, Singles,
+ cord.empty, Messages),
+ disj_calc_cost(Disjs, Calls, Cost),
+ GoalExpr = disj_rep(Disjs)
+ ;
+ GoalExpr0 = switch_rep(Var, CanFail, Cases0),
+ list.map_foldl5(
+ switch_case_get_conjunctions_worth_parallelising(Info,
+ RevGoalPathSteps),
+ Cases0, Cases, 1, _, cord.empty, Candidates,
+ cord.empty, Pushes, cord.empty, Singles,
+ cord.empty, Messages),
+ switch_calc_cost(Cases, Calls, Cost),
+ GoalExpr = switch_rep(Var, CanFail, Cases)
+ ;
+ GoalExpr0 = ite_rep(Cond0, Then0, Else0),
+ ite_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
+ Cond0, Cond, Then0, Then, Else0, Else,
+ Candidates, Pushes, Singles, Messages),
+ ite_calc_cost(Cond, Then, Else, Cost),
+ GoalExpr = ite_rep(Cond, Then, Else)
+ ;
+ GoalExpr0 = scope_rep(SubGoal0, MaybeCut),
+ RevSubGoalPathSteps = [step_scope(MaybeCut) | RevGoalPathSteps],
+ goal_get_conjunctions_worth_parallelising(Info,
+ RevSubGoalPathSteps, SubGoal0, SubGoal,
+ Candidates, Pushes, Singles, Messages),
+ Cost = SubGoal ^ goal_annotation ^ pgd_cost,
+ GoalExpr = scope_rep(SubGoal, MaybeCut)
+ ;
+ GoalExpr0 = negation_rep(SubGoal0),
+ RevSubGoalPathSteps = [step_neg | RevGoalPathSteps],
+ % We ignore _Singles here because you cannot push goals
+ % after a negation into the negation.
+ goal_get_conjunctions_worth_parallelising(Info,
+ RevSubGoalPathSteps, SubGoal0, SubGoal,
+ Candidates, Pushes, _Singles, Messages),
+ Singles = cord.empty,
+ Cost = SubGoal ^ goal_annotation ^ pgd_cost,
+ GoalExpr = negation_rep(SubGoal)
+ ),
+ Annotation = Annotation0 ^ pgd_cost := Cost
+ ;
+ GoalExpr0 = atomic_goal_rep(_, _, _, _),
+ identify_costly_goal(Annotation0, Costly),
+ (
+ Costly = is_costly_goal,
+ Singles = cord.singleton(!.Goal)
+ ;
+ Costly = is_not_costly_goal,
+ Singles = cord.empty
+ ),
+ Candidates = cord.empty,
+ Pushes = cord.empty,
+ Messages = cord.empty,
+ GoalExpr = GoalExpr0,
+ Annotation = Annotation0
+ ),
+ !:Goal = goal_rep(GoalExpr, DetismRep, Annotation).
+
+:- pred disj_get_conjunctions_worth_parallelising(
+ implicit_parallelism_info::in, list(goal_path_step)::in,
+ pard_goal_detail::in, pard_goal_detail::out,
+ int::in, int::out,
+ cord(candidate_par_conjunction(pard_goal_detail))::in,
+ cord(candidate_par_conjunction(pard_goal_detail))::out,
+ cord(push_goal)::in, cord(push_goal)::out,
+ cord(pard_goal_detail)::in, cord(pard_goal_detail)::out,
+ cord(message)::in, cord(message)::out) is det.
+
+disj_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
+ !Disj, !DisjNum, !Candidates, !Pushes, !Singles, !Messages) :-
+ RevDisjGoalPathSteps = [step_disj(!.DisjNum) | RevGoalPathSteps],
+ goal_get_conjunctions_worth_parallelising(Info, RevDisjGoalPathSteps,
+ !Disj, Candidates, Pushes, Singles, Messages),
+ !:Candidates = !.Candidates ++ Candidates,
+ !:Pushes = !.Pushes ++ Pushes,
+ !:Singles = !.Singles ++ Singles,
+ !:Messages = !.Messages ++ Messages,
+ !:DisjNum = !.DisjNum + 1.
+
+:- pred switch_case_get_conjunctions_worth_parallelising(
+ implicit_parallelism_info::in, list(goal_path_step)::in,
+ case_rep(pard_goal_detail_annotation)::in,
+ case_rep(pard_goal_detail_annotation)::out,
+ int::in, int::out,
+ cord(candidate_par_conjunction(pard_goal_detail))::in,
+ cord(candidate_par_conjunction(pard_goal_detail))::out,
+ cord(push_goal)::in, cord(push_goal)::out,
+ cord(pard_goal_detail)::in, cord(pard_goal_detail)::out,
+ cord(message)::in, cord(message)::out) is det.
+
+switch_case_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps, !Case,
+ !CaseNum, !Candidates, !Pushes, !Singles, !Messages) :-
+ !.Case = case_rep(MainConsIdRep, OtherConsIdReps, Goal0),
+ RevCaseGoalPathSteps = [step_switch(!.CaseNum, no) | RevGoalPathSteps],
+ goal_get_conjunctions_worth_parallelising(Info, RevCaseGoalPathSteps,
+ Goal0, Goal, Candidates, Pushes, Singles, Messages),
+ !:Case = case_rep(MainConsIdRep, OtherConsIdReps, Goal),
+ !:Candidates = !.Candidates ++ Candidates,
+ !:Pushes = !.Pushes ++ Pushes,
+ !:Singles = !.Singles ++ Singles,
+ !:Messages = !.Messages ++ Messages,
+ !:CaseNum = !.CaseNum + 1.
+
+:- pred ite_get_conjunctions_worth_parallelising(
+ implicit_parallelism_info::in, list(goal_path_step)::in,
+ pard_goal_detail::in, pard_goal_detail::out,
+ pard_goal_detail::in, pard_goal_detail::out,
+ pard_goal_detail::in, pard_goal_detail::out,
+ cord(candidate_par_conjunction(pard_goal_detail))::out,
+ cord(push_goal)::out, cord(pard_goal_detail)::out,
+ cord(message)::out) is det.
+
+ite_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
+ !Cond, !Then, !Else, Candidates, Pushes, Singles, Messages) :-
+ RevCondGoalPathSteps = [step_ite_cond | RevGoalPathSteps],
+ RevThenGoalPathSteps = [step_ite_then | RevGoalPathSteps],
+ RevElseGoalPathSteps = [step_ite_else | RevGoalPathSteps],
+ % We ignore _CondSingles here because you cannot push goals
+ % following an if-then-else into the condition.
+ goal_get_conjunctions_worth_parallelising(Info, RevCondGoalPathSteps,
+ !Cond, CondCandidates, CondPushes, _CondSingles, CondMessages),
+ goal_get_conjunctions_worth_parallelising(Info, RevThenGoalPathSteps,
+ !Then, ThenCandidates, ThenPushes, ThenSingles, ThenMessages),
+ goal_get_conjunctions_worth_parallelising(Info, RevElseGoalPathSteps,
+ !Else, ElseCandidates, ElsePushes, ElseSingles, ElseMessages),
+ Candidates = CondCandidates ++ ThenCandidates ++ ElseCandidates,
+ Pushes = CondPushes ++ ThenPushes ++ ElsePushes,
+ Singles = ThenSingles ++ ElseSingles,
+ Messages = CondMessages ++ ThenMessages ++ ElseMessages.
+
+:- pred conj_get_conjunctions_worth_parallelising(
+ implicit_parallelism_info::in, list(goal_path_step)::in,
+ list(pard_goal_detail)::in, list(pard_goal_detail)::out, int::in,
+ list(pard_goal_detail)::in, list(pard_goal_detail)::out,
+ assoc_list(int, list(pard_goal_detail))::in,
+ assoc_list(int, list(pard_goal_detail))::out,
+ cord(candidate_par_conjunction(pard_goal_detail))::in,
+ cord(candidate_par_conjunction(pard_goal_detail))::out,
+ cord(push_goal)::in, cord(push_goal)::out,
+ cord(message)::in, cord(message)::out) is det.
+
+conj_get_conjunctions_worth_parallelising(_Info, _RevGoalPathSteps,
+ [], [], _ConjNum, !SinglesSoFar, !RevSingleCands,
+ !CandidatesBelow, !Pushes, !MessagesBelow).
+conj_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
+ [Conj0 | Conjs0], [Conj | Conjs], ConjNum, SinglesSoFar0, SinglesSoFar,
+ !RevSingleCands, !CandidatesBelow, !Pushes, !MessagesBelow) :-
+ RevConjGoalPathSteps = [step_conj(ConjNum) | RevGoalPathSteps],
+ goal_get_conjunctions_worth_parallelising(Info, RevConjGoalPathSteps,
+ Conj0, Conj, Candidates, Pushes, SinglesCord, Messages),
+ Singles = cord.list(SinglesCord),
+ !:CandidatesBelow = !.CandidatesBelow ++ Candidates,
+ !:Pushes = !.Pushes ++ Pushes,
+ !:MessagesBelow = !.MessagesBelow ++ Messages,
+ identify_costly_goal(Conj ^ goal_annotation, Costly),
+ (
+ Costly = is_costly_goal,
+ !:RevSingleCands = [ConjNum - SinglesSoFar0 | !.RevSingleCands],
+ SinglesSoFar1 = Singles
+ ;
+ Costly = is_not_costly_goal,
+ % This goal might be costly if it is pushed into the cotexted
+ % of one of SinglesSoFar. This is common for recursive goals.
+ filter(single_context_makes_goal_costly(Info, Conj), SinglesSoFar0,
+ SinglesSoFarMakeConjCostly),
+ (
+ SinglesSoFarMakeConjCostly = []
+ ;
+ SinglesSoFarMakeConjCostly = [_ | _],
+ !:RevSingleCands = [ConjNum - SinglesSoFarMakeConjCostly |
+ !.RevSingleCands]
+ ),
+
+ (
+ SinglesSoFar0 = [],
+ Singles = [],
+ SinglesSoFar1 = []
+ ;
+ SinglesSoFar0 = [_ | _],
+ Singles = [],
+ SinglesSoFar1 = SinglesSoFar0
+ ;
+ SinglesSoFar0 = [],
+ Singles = [_ | _],
+ SinglesSoFar1 = Singles
+ ;
+ SinglesSoFar0 = [_ | _],
+ Singles = [_ | _],
+ % XXX choose between SinglesSoFar0 and Singles, either on max cost
+ % or total cost.
+ SinglesSoFar1 = Singles
+ )
+ ),
+ conj_get_conjunctions_worth_parallelising(Info, RevGoalPathSteps,
+ Conjs0, Conjs, ConjNum + 1, SinglesSoFar1, SinglesSoFar,
+ !RevSingleCands, !CandidatesBelow, !Pushes, !MessagesBelow).
+
+:- pred single_context_makes_goal_costly(implicit_parallelism_info::in,
+ pard_goal_detail::in, pard_goal_detail::in) is semidet.
+
+single_context_makes_goal_costly(Info, Goal, Single) :-
+ SingleCost = Single ^ goal_annotation ^ pgd_cost,
+ SingleCount = goal_cost_get_calls(SingleCost),
+ fix_goal_counts(Info, SingleCount, Goal, ConjNewCounts),
+ identify_costly_goal(ConjNewCounts ^ goal_annotation, is_costly_goal).
+
+ % Given a conjunction with two or more costly goals (identified by
+ % CostlyGoalsIndexes), check whether executing the conjunction in parallel
+ % can yield a speedup.
+ %
+:- pred build_candidate_conjunction(implicit_parallelism_info::in,
+ list(goal_path_step)::in, list(pard_goal_detail)::in, list(int)::in,
+ cord(message)::out,
+ maybe(candidate_par_conjunction(pard_goal_detail))::out) is det.
+
+build_candidate_conjunction(Info, RevGoalPathSteps, Conjs, CostlyGoalsIndexes,
+ !:Messages, MaybeCandidate) :-
+ ProcLabel = Info ^ ipi_proc_label,
+ !:Messages = cord.empty,
+ NumCostlyGoals = list.length(CostlyGoalsIndexes),
+ Location = pl_goal(ProcLabel, rgp(RevGoalPathSteps)),
+ append_message(Location,
+ info_found_conjs_above_callsite_threshold(NumCostlyGoals),
+ !Messages),
+
+ pardgoals_build_candidate_conjunction(Info, Location, RevGoalPathSteps, no,
+ Conjs, MaybeCandidate, !Messages),
+ (
+ MaybeCandidate = yes(_Candidate),
+ append_message(Location,
+ info_found_n_conjunctions_with_positive_speedup(1),
+ !Messages)
+ ;
+ MaybeCandidate = no
+ ).
+
+ % Given a conjunction one costly goal (identified by CostlyIndex) directly
+ % in it and other costly goals SinglesBefore inside alternate execution
+ % paths in an earlier conjunct (conjunct i < CostlyIndex), check whether
+ % pushing CostlyIndex next to SinglesBefore and executing those
+ % conjunctions in parallel can yield a speedup.
+ %
+:- pred push_and_build_candidate_conjunctions(implicit_parallelism_info::in,
+ list(goal_path_step)::in, list(pard_goal_detail)::in, int::in,
+ list(pard_goal_detail)::in, cord(message)::out,
+ list(candidate_par_conjunction(pard_goal_detail))::out) is det.
+
+push_and_build_candidate_conjunctions(_Info, _RevGoalPathSteps, _Conjs,
+ _CostlyIndex, [], cord.empty, []).
+push_and_build_candidate_conjunctions(Info, RevGoalPathSteps, Conjs,
+ CostlyIndex, [Single | Singles], Messages, Candidates) :-
+ push_and_build_candidate_conjunction(Info, RevGoalPathSteps, Conjs,
+ CostlyIndex, Single, HeadMessages, MaybeHeadCandidate),
+ push_and_build_candidate_conjunctions(Info, RevGoalPathSteps, Conjs,
+ CostlyIndex, Singles, TailMessages, TailCandidates),
+ Messages = HeadMessages ++ TailMessages,
+ (
+ MaybeHeadCandidate = yes(HeadCandidate),
+ Candidates = [HeadCandidate | TailCandidates]
+ ;
+ MaybeHeadCandidate = no,
+ Candidates = TailCandidates
+ ).
+
+:- pred push_and_build_candidate_conjunction(implicit_parallelism_info::in,
+ list(goal_path_step)::in, list(pard_goal_detail)::in, int::in,
+ pard_goal_detail::in, cord(message)::out,
+ maybe(candidate_par_conjunction(pard_goal_detail))::out) is det.
+
+push_and_build_candidate_conjunction(Info, RevGoalPathSteps, Conjs,
+ CostlyIndex, Single, !:Messages, MaybeCandidate) :-
+ SingleRevPath = Single ^ goal_annotation ^ pgd_original_path,
+ SingleRevPath = rgp(SingleRevSteps),
+ list.reverse(SingleRevSteps, SingleSteps),
+ list.reverse(RevGoalPathSteps, GoalPathSteps),
+ (
+ goal_path_inside_relative(fgp(GoalPathSteps), fgp(SingleSteps),
+ RelativePath),
+ RelativePath = fgp(RelativeSteps),
+ RelativeSteps = [step_conj(RelConjStep) | TailRelativeSteps],
+ RelConjStep < CostlyIndex,
+ list.take(CostlyIndex, Conjs, ConjsUptoCostly),
+ list.drop(RelConjStep - 1, ConjsUptoCostly,
+ [GoalToPushInto | GoalsToPush])
+ ->
+ RevPushGoalPathSteps = [step_conj(RelConjStep) | RevGoalPathSteps],
+ push_goals_create_candidate(Info, RevPushGoalPathSteps,
+ TailRelativeSteps, GoalToPushInto, GoalsToPush,
+ RevCandidateGoalPathSteps, CandidateConjs),
+
+ ProcLabel = Info ^ ipi_proc_label,
+ !:Messages = cord.empty,
+ % XXX Location is a lie
+ Location = pl_goal(ProcLabel, rgp(RevGoalPathSteps)),
+ append_message(Location,
+ info_found_pushed_conjs_above_callsite_threshold,
+ !Messages),
+
+ (
+ list.split_last(RelativeSteps, MostRelativeSteps,
+ LastRelativeStep),
+ LastRelativeStep = step_conj(_)
+ ->
+ % We push GoalsToPush into the existing conjunction
+ % containing Single.
+ PushGoalSteps = MostRelativeSteps
+ ;
+ % We push GoalsToPush next to Single in a newly created
+ % conjunction.
+ PushGoalSteps = RelativeSteps
+ ),
+
+ PushGoal = push_goal(rev_goal_path_to_string(rgp(RevGoalPathSteps)),
+ RelConjStep + 1, CostlyIndex,
+ [goal_path_to_string(fgp(PushGoalSteps))]),
+ pardgoals_build_candidate_conjunction(Info, Location,
+ RevCandidateGoalPathSteps, yes(PushGoal), CandidateConjs,
+ MaybeCandidate, !Messages),
+ (
+ MaybeCandidate = yes(_),
+ append_message(Location,
+ info_found_n_conjunctions_with_positive_speedup(1),
+ !Messages)
+ ;
+ MaybeCandidate = no
+ )
+ ;
+ unexpected($module, $pred, "bad goal path for Single")
+ ).
+
+:- pred merge_same_level_pushes(
+ candidate_par_conjunction(pard_goal_detail)::in,
+ list(candidate_par_conjunction(pard_goal_detail))::in,
+ push_goal::out) is det.
+
+merge_same_level_pushes(MainCandidate, [], MainPush) :-
+ MaybeMainPush = MainCandidate ^ cpc_maybe_push_goal,
+ (
+ MaybeMainPush = yes(MainPush)
+ ;
+ MaybeMainPush = no,
+ unexpected($module, $pred, "no push")
+ ).
+merge_same_level_pushes(MainCandidate, [HeadCandidate | TailCandidates],
+ Push) :-
+ merge_same_level_pushes(HeadCandidate, TailCandidates, RestPush),
+ MaybeMainPush = MainCandidate ^ cpc_maybe_push_goal,
+ (
+ MaybeMainPush = yes(MainPush)
+ ;
+ MaybeMainPush = no,
+ unexpected($module, $pred, "no push")
+ ),
+ (
+ MainPush = push_goal(GoalPathStr, Lo, Hi, [MainPushInto]),
+ RestPush = push_goal(GoalPathStr, Lo, Hi, RestPushInto)
+ ->
+ Push = push_goal(GoalPathStr, Lo, Hi, [MainPushInto | RestPushInto])
+ ;
+ unexpected($module, $pred, "mismatch on pushed goals")
+ ).
+
+:- pred push_goals_create_candidate(implicit_parallelism_info::in,
+ list(goal_path_step)::in, list(goal_path_step)::in,
+ pard_goal_detail::in, list(pard_goal_detail)::in,
+ list(goal_path_step)::out, list(pard_goal_detail)::out) is det.
+
+push_goals_create_candidate(Info, RevCurPathSteps,
+ [], GoalToPushInto, GoalsToPush0,
+ RevCandidateGoalPathSteps, CandidateConjs) :-
+ RevCandidateGoalPathSteps = RevCurPathSteps,
+ % The pushed goals will have different costs in this context, in particular
+ % the number of times they're called varies, This affects the per-call
+ % costs of recursive calls.
+ Calls = goal_cost_get_calls(GoalToPushInto ^ goal_annotation ^ pgd_cost),
+ map(fix_goal_counts(Info, Calls), GoalsToPush0, GoalsToPush),
+ CandidateConjs = [GoalToPushInto | GoalsToPush].
+push_goals_create_candidate(Info, RevCurPathSteps,
+ [HeadRelStep | TailRelSteps], GoalToPushInto, GoalsToPush0,
+ RevCandidateGoalPathSteps, CandidateConjs) :-
+ GoalToPushInto = goal_rep(GoalExpr, _, _),
+ (
+ HeadRelStep = step_conj(N),
+ ( GoalExpr = conj_rep(Goals) ->
+ (
+ TailRelSteps = [],
+ % Conjoin GoalsToPush not with just the expensive goal,
+ % but with the whole conjunction containing it.
+ RevCandidateGoalPathSteps = RevCurPathSteps,
+ % The pushed goals will have different costs in this context,
+ % in particular the number of times they're called varies, This
+ % affects the per-call costs of recursive calls.
+ Cost = GoalToPushInto ^ goal_annotation ^ pgd_cost,
+ Calls = goal_cost_get_calls(Cost),
+ map(fix_goal_counts(Info, Calls), GoalsToPush0, GoalsToPush),
+ CandidateConjs = Goals ++ GoalsToPush
+ ;
+ TailRelSteps = [_ | _],
+ list.det_drop(N - 1, Goals, Tail),
+ ( Tail = [SubGoal] ->
+ push_goals_create_candidate(Info,
+ [HeadRelStep | RevCurPathSteps],
+ TailRelSteps, SubGoal, GoalsToPush0,
+ RevCandidateGoalPathSteps, CandidateConjs)
+ ;
+ % We can't push goals into the non-last conjunct without
+ % re-ordering, which is currently not supported. By
+ % building a conjunction here we may still be able to
+ % create a worthwhile parallelisation. However, there is a
+ % trade-off to explore between this and not generating the
+ % single expensive goal from within the conjunction and
+ % therefore possibly finding other single expensive goals
+ % later in this conjunction.
+ RevCandidateGoalPathSteps = RevCurPathSteps,
+ Cost = GoalToPushInto ^ goal_annotation ^ pgd_cost,
+ Calls = goal_cost_get_calls(Cost),
+ map(fix_goal_counts(Info, Calls), GoalsToPush0,
+ GoalsToPush),
+ CandidateConjs = Goals ++ GoalsToPush
+ )
+ )
+ ;
+ unexpected($module, $pred, "not conj")
+ )
+ ;
+ HeadRelStep = step_disj(N),
+ ( GoalExpr = disj_rep(Goals) ->
+ list.index1_det(Goals, N, SubGoal),
+ push_goals_create_candidate(Info, [HeadRelStep | RevCurPathSteps],
+ TailRelSteps, SubGoal, GoalsToPush0,
+ RevCandidateGoalPathSteps, CandidateConjs)
+ ;
+ unexpected($module, $pred, "not disj")
+ )
+ ;
+ HeadRelStep = step_switch(N, _),
+ ( GoalExpr = switch_rep(_, _, Cases) ->
+ list.index1_det(Cases, N, Case),
+ Case = case_rep(_, _, SubGoal),
+ push_goals_create_candidate(Info, [HeadRelStep | RevCurPathSteps],
+ TailRelSteps, SubGoal, GoalsToPush0,
+ RevCandidateGoalPathSteps, CandidateConjs)
+ ;
+ unexpected($module, $pred, "not switch")
+ )
+ ;
+ HeadRelStep = step_ite_then,
+ ( GoalExpr = ite_rep(_, Then, _) ->
+ push_goals_create_candidate(Info, [HeadRelStep | RevCurPathSteps],
+ TailRelSteps, Then, GoalsToPush0,
+ RevCandidateGoalPathSteps, CandidateConjs)
+ ;
+ unexpected($module, $pred, "not ite_then")
+ )
+ ;
+ HeadRelStep = step_ite_else,
+ ( GoalExpr = ite_rep(_, _, Else) ->
+ push_goals_create_candidate(Info, [HeadRelStep | RevCurPathSteps],
+ TailRelSteps, Else, GoalsToPush0,
+ RevCandidateGoalPathSteps, CandidateConjs)
+ ;
+ unexpected($module, $pred, "not ite_else")
+ )
+ ;
+ HeadRelStep = step_ite_cond,
+ % We cannot push into a condition.
+ unexpected($module, $pred, "ite_cond")
+ ;
+ HeadRelStep = step_neg,
+ % We cannot push into a negated goal.
+ unexpected($module, $pred, "neg")
+ ;
+ HeadRelStep = step_scope(_),
+ ( GoalExpr = scope_rep(SubGoal, _) ->
+ push_goals_create_candidate(Info, [HeadRelStep | RevCurPathSteps],
+ TailRelSteps, SubGoal, GoalsToPush0,
+ RevCandidateGoalPathSteps, CandidateConjs)
+ ;
+ unexpected($module, $pred, "not scope")
+ )
+ ;
+ HeadRelStep = step_lambda,
+ % These should not exist in a profiled program.
+ unexpected($module, $pred, "lambda")
+ ;
+ HeadRelStep = step_try,
+ % These should not exist in a profiled program.
+ unexpected($module, $pred, "try")
+ ;
+ HeadRelStep = step_atomic_main,
+ % These should not exist in a profiled program.
+ unexpected($module, $pred, "atomic_main")
+ ;
+ HeadRelStep = step_atomic_orelse(_),
+ % These should not exist in a profiled program.
+ unexpected($module, $pred, "atomic_orelse")
+ ).
+
+:- pred fix_goal_counts(implicit_parallelism_info::in, int::in,
+ pard_goal_detail::in, pard_goal_detail::out) is det.
+
+fix_goal_counts(Info, Count, !Goal) :-
+ Annotation0 = !.Goal ^ goal_annotation,
+ Cost0 = Annotation0 ^ pgd_cost,
+ (
+ GoalType = Annotation0 ^ pgd_pg_type,
+ GoalType = pgt_call(_, CostAndCallees),
+ % XXX This doesn't work if this is a non-atomic goal containing a
+ % recursive call.
+ set.member(Callee, CostAndCallees ^ cac_callees),
+ % The call is recursive if it calls into the current clique.
+ Info ^ ipi_clique = Callee ^ c_clique
+ ->
+ % for recursive calls.
+ CostTotal = goal_cost_get_total(Cost0),
+ PercallCost = CostTotal / float(Count)
+ ;
+ PercallCost = goal_cost_get_percall(Cost0)
+ ),
+ Cost = call_goal_cost(Count, PercallCost),
+ !Goal ^ goal_annotation ^ pgd_cost := Cost,
+ ( goal_cost_above_par_threshold(Info, Cost) ->
+ AboveThreshold = cost_above_par_threshold
+ ;
+ AboveThreshold = cost_not_above_par_threshold
+ ),
+ !Goal ^ goal_annotation ^ pgd_cost_above_threshold := AboveThreshold.
+
+:- pred pardgoals_build_candidate_conjunction(implicit_parallelism_info::in,
+ program_location::in, list(goal_path_step)::in,
+ maybe(push_goal)::in, list(pard_goal_detail)::in,
+ maybe(candidate_par_conjunction(pard_goal_detail))::out,
+ cord(message)::in, cord(message)::out) is det.
+
+pardgoals_build_candidate_conjunction(Info, Location, RevGoalPathSteps,
+ MaybePushGoal, Goals, MaybeCandidate, !Messages) :-
+ % Setting up the first parallel conjunct is a different algorithm to the
+ % latter ones, at this point we have the option of moving goals from before
+ % the first costly call to either before or during the parallel
+ % conjunction. Executing them during the parallel conjunction can be more
+ % efficient. However if goals within other parallel conjuncts depend on
+ % them and don't depend upon the first costly call then this would make the
+ % conjunction dependent when it could be independent.
+ find_best_parallelisation(Info, Location, Goals, MaybeBestParallelisation,
+ !Messages),
+ (
+ MaybeBestParallelisation = yes(BestParallelisation),
+ FirstConjNum = 1,
+ ParalleliseDepConjs = Info ^ ipi_opts ^ cpcp_parallelise_dep_conjs,
+ BestParallelisation = bp_parallel_execution(GoalsBefore, ParConjs,
+ GoalsAfter, IsDependent, Metrics),
+ Speedup = parallel_exec_metrics_get_speedup(Metrics),
+ Calls = Metrics ^ pem_num_calls,
+ conj_calc_cost(GoalsBefore, Calls, GoalsBeforeCost0),
+ GoalsBeforeCost = goal_cost_get_percall(GoalsBeforeCost0),
+ conj_calc_cost(GoalsAfter, Calls, GoalsAfterCost0),
+ GoalsAfterCost = goal_cost_get_percall(GoalsAfterCost0),
+ RevGoalPathString = rev_goal_path_to_string(rgp(RevGoalPathSteps)),
+ Candidate = candidate_par_conjunction(RevGoalPathString, MaybePushGoal,
+ FirstConjNum, IsDependent, GoalsBefore, GoalsBeforeCost, ParConjs,
+ GoalsAfter, GoalsAfterCost, Metrics),
+ (
+ Speedup > 1.0,
+ (
+ ParalleliseDepConjs = do_not_parallelise_dep_conjs
+ =>
+ IsDependent = conjuncts_are_independent
+ )
+ ->
+ MaybeCandidate = yes(Candidate)
+ ;
+ MaybeCandidate = no,
+ trace [
+ compile_time(flag("debug_parallel_conjunction_speedup")),
+ io(!IO)
+ ]
+ (
+ (
+ ( Location = pl_proc(ProcLabel)
+ ; Location = pl_goal(ProcLabel, _)
+ )
+ ;
+ Location = pl_clique(_),
+ unexpected($module, $pred, "location is a clique")
+ ;
+ Location = pl_csd(_),
+ unexpected($module, $pred, "location is a csd")
+ ),
+
+ convert_candidate_par_conjunction(
+ pard_goal_detail_to_pard_goal, Candidate, FBCandidate),
+ VarTable = Info ^ ipi_var_table,
+ create_candidate_parallel_conj_report(VarTable,
+ FBCandidate, Report),
+ print_proc_label_to_string(ProcLabel, ProcLabelString),
+ io.format("Not parallelising conjunction in %s, " ++
+ "insufficient speedup or too dependent:\n",
+ [s(ProcLabelString)], !IO),
+ io.write_string(append_list(cord.list(Report)), !IO),
+ io.flush_output(!IO)
+ )
+ )
+ ;
+ MaybeBestParallelisation = no,
+ MaybeCandidate = no
+ ).
+
+%-----------------------------------------------------------------------------%
+
+goal_to_pard_goal(Info, RevGoalPathSteps, !Goal, !Messages) :-
+ !.Goal = goal_rep(GoalExpr0, Detism, GoalId),
+ InstMapInfo = get_goal_attribute_det(Info ^ ipi_inst_map_array, GoalId),
+ Coverage = get_goal_attribute_det(Info ^ ipi_coverage_array, GoalId),
+ get_coverage_before_det(Coverage, Before),
+ (
+ (
+ GoalExpr0 = conj_rep(Conjs0),
+ list.map_foldl2(conj_to_pard_goals(Info, RevGoalPathSteps),
+ Conjs0, Conjs, 1, _, !Messages),
+ conj_calc_cost(Conjs, Before, Cost),
+ GoalExpr = conj_rep(Conjs)
+ ;
+ GoalExpr0 = disj_rep(Disjs0),
+ list.map_foldl2(disj_to_pard_goals(Info, RevGoalPathSteps),
+ Disjs0, Disjs, 1, _, !Messages),
+ disj_calc_cost(Disjs, Before, Cost),
+ GoalExpr = disj_rep(Disjs)
+ ;
+ GoalExpr0 = switch_rep(Var, CanFail, Cases0),
+ list.map_foldl2(case_to_pard_goal(Info, RevGoalPathSteps),
+ Cases0, Cases, 1, _, !Messages),
+ switch_calc_cost(Cases, Before, Cost),
+ GoalExpr = switch_rep(Var, CanFail, Cases)
+ ;
+ GoalExpr0 = ite_rep(Cond0, Then0, Else0),
+ goal_to_pard_goal(Info, [step_ite_cond | RevGoalPathSteps],
+ Cond0, Cond, !Messages),
+ goal_to_pard_goal(Info, [step_ite_then | RevGoalPathSteps],
+ Then0, Then, !Messages),
+ goal_to_pard_goal(Info, [step_ite_else | RevGoalPathSteps],
+ Else0, Else, !Messages),
+ ite_calc_cost(Cond, Then, Else, Cost),
+ GoalExpr = ite_rep(Cond, Then, Else)
+ ;
+ GoalExpr0 = negation_rep(SubGoal0),
+ goal_to_pard_goal(Info, [step_neg | RevGoalPathSteps],
+ SubGoal0, SubGoal, !Messages),
+ Cost = SubGoal ^ goal_annotation ^ pgd_cost,
+ GoalExpr = negation_rep(SubGoal)
+ ;
+ GoalExpr0 = scope_rep(SubGoal0, MaybeCut),
+ goal_to_pard_goal(Info, [step_scope(MaybeCut) | RevGoalPathSteps],
+ SubGoal0, SubGoal, !Messages),
+ Cost = SubGoal ^ goal_annotation ^ pgd_cost,
+ GoalExpr = scope_rep(SubGoal, MaybeCut)
+ ),
+ PardGoalType = pgt_non_atomic_goal,
+
+ BoundVars = to_sorted_list(InstMapInfo ^ im_bound_vars),
+ list.foldl(
+ goal_build_use_map(!.Goal, RevGoalPathSteps, Cost, Info,
+ var_use_production),
+ BoundVars, map.init, ProductionUseMap),
+ ConsumedVars = to_sorted_list(InstMapInfo ^ im_consumed_vars),
+ list.foldl(
+ goal_build_use_map(!.Goal, RevGoalPathSteps, Cost, Info,
+ var_use_consumption),
+ ConsumedVars, map.init, ConsumptionUseMap)
+ ;
+ GoalExpr0 = atomic_goal_rep(Context, Line, BoundVars, AtomicGoal),
+ GoalExpr = atomic_goal_rep(Context, Line, BoundVars, AtomicGoal),
+ atomic_pard_goal_type(Info, RevGoalPathSteps, AtomicGoal, InstMapInfo,
+ PardGoalType, Messages),
+ atomic_pard_goal_cost(Info, RevGoalPathSteps, Coverage, AtomicGoal,
+ Cost),
+
+ list.foldl(
+ atomic_goal_build_use_map(AtomicGoal, RevGoalPathSteps, Info,
+ var_use_production),
+ BoundVars, map.init, ProductionUseMap),
+ ConsumedVars = to_sorted_list(InstMapInfo ^ im_consumed_vars),
+ list.foldl(
+ atomic_goal_build_use_map(AtomicGoal, RevGoalPathSteps, Info,
+ var_use_consumption),
+ ConsumedVars, map.init, ConsumptionUseMap),
+
+ !:Messages = !.Messages ++ Messages
+ ),
+ % XXX: The goal annotations cannot represent reasons why a goal
+ % can't be parallelised, for example it could be nondet, semidet or
+ % impure.
+ (
+ can_parallelise_goal(!.Goal),
+ goal_cost_above_par_threshold(Info, Cost)
+ ->
+ CostAboveThreshold = cost_above_par_threshold
+ ;
+ CostAboveThreshold = cost_not_above_par_threshold
+ ),
+ PardGoalAnnotation = pard_goal_detail(PardGoalType, InstMapInfo,
+ rgp(RevGoalPathSteps), Coverage, Cost, CostAboveThreshold,
+ ProductionUseMap, ConsumptionUseMap),
+ !:Goal = goal_rep(GoalExpr, Detism, PardGoalAnnotation).
+
+:- pred goal_build_use_map(goal_rep(goal_id)::in,
+ list(goal_path_step)::in, goal_cost_csq::in, implicit_parallelism_info::in,
+ var_use_type::in, var_rep::in,
+ map(var_rep, lazy(var_use_info))::in,
+ map(var_rep, lazy(var_use_info))::out) is det.
+
+goal_build_use_map(Goal, RevGoalPathSteps, Cost, Info, VarUseType, Var, !Map) :-
+ LazyUse = delay((func) = compute_goal_var_use_lazy(Goal, RevGoalPathSteps,
+ Cost, Info, VarUseType, Var)),
+ svmap.det_insert(Var, LazyUse, !Map).
+
+:- func compute_goal_var_use_lazy(goal_rep(goal_id), list(goal_path_step),
+ goal_cost_csq, implicit_parallelism_info, var_use_type, var_rep)
+ = var_use_info.
+
+compute_goal_var_use_lazy(Goal, RevGoalPathSteps, Cost, Info, VarUseType, Var)
+ = Use :-
+ Info = implicit_parallelism_info(Deep, _ProgRep, _Params, CliquePtr,
+ CallSiteMap, RecursiveCallSiteMap, ContainingGoalMap, CoverageArray,
+ _InstMapArray, RecursionType, _VarTable, _ProcLabel),
+ CostPercall = goal_cost_get_percall(Cost),
+ (
+ ( RecursionType = rt_not_recursive
+ ; RecursionType = rt_single(_, _, _, _, _)
+ ),
+ recursion_type_get_interesting_parallelisation_depth(RecursionType,
+ yes(RecDepth)),
+ implicit_par_info_intermodule_var_use(Info, FollowCallsAcrossModules),
+ VarUseOptions = var_use_options(Deep, FollowCallsAcrossModules,
+ VarUseType),
+ var_first_use(CliquePtr, CallSiteMap, RecursiveCallSiteMap,
+ ContainingGoalMap, CoverageArray, RecursionType, RecDepth, Goal,
+ rgp(RevGoalPathSteps), CostPercall, Var, VarUseOptions, Use)
+ ;
+ ( RecursionType = rt_divide_and_conquer(_, _)
+ ; RecursionType = rt_mutual_recursion(_)
+ ; RecursionType = rt_other(_)
+ ; RecursionType = rt_errors(_)
+ ),
+ % var_first_use doesn't work for these recursion types.
+ pessimistic_var_use_info(VarUseType, CostPercall, Use),
+ append_message(pl_clique(CliquePtr),
+ warning_cannot_compute_first_use_time(
+ "Recursion type unknown for var_first_use/12"),
+ empty, Messages),
+ trace [io(!IO)] (
+ io.stderr_stream(Stderr, !IO),
+ write_out_messages(Stderr, Messages, !IO)
+ )
+ ).
+
+:- pred conj_to_pard_goals(implicit_parallelism_info::in,
+ list(goal_path_step)::in, goal_rep(goal_id)::in,
+ pard_goal_detail::out, int::in, int::out,
+ cord(message)::in, cord(message)::out) is det.
+
+conj_to_pard_goals(Info, RevGoalPathSteps, !Goal, !ConjNum, !Messages) :-
+ goal_to_pard_goal(Info, [step_conj(!.ConjNum) | RevGoalPathSteps],
+ !Goal, !Messages),
+ !:ConjNum = !.ConjNum + 1.
+
+:- pred disj_to_pard_goals(implicit_parallelism_info::in,
+ list(goal_path_step)::in, goal_rep(goal_id)::in,
+ pard_goal_detail::out, int::in, int::out,
+ cord(message)::in, cord(message)::out) is det.
+
+disj_to_pard_goals(Info, RevGoalPathSteps, !Goal, !DisjNum, !Messages) :-
+ goal_to_pard_goal(Info, [step_disj(!.DisjNum) | RevGoalPathSteps],
+ !Goal, !Messages),
+ !:DisjNum = !.DisjNum + 1.
+
+:- pred case_to_pard_goal(implicit_parallelism_info::in,
+ list(goal_path_step)::in, case_rep(goal_id)::in,
+ case_rep(pard_goal_detail_annotation)::out, int::in, int::out,
+ cord(message)::in, cord(message)::out) is det.
+
+case_to_pard_goal(Info, RevGoalPathSteps, !Case, !CaseNum, !Messages) :-
+ !.Case = case_rep(ConsId, OtherConsId, Goal0),
+ goal_to_pard_goal(Info, [step_switch(!.CaseNum, no) | RevGoalPathSteps],
+ Goal0, Goal, !Messages),
+ !:CaseNum = !.CaseNum + 1,
+ !:Case = case_rep(ConsId, OtherConsId, Goal).
+
+%-----------------------------------------------------------------------------%
+
+:- pred atomic_pard_goal_type(implicit_parallelism_info::in,
+ list(goal_path_step)::in, atomic_goal_rep::in, inst_map_info::in,
+ pard_goal_type::out, cord(message)::out) is det.
+
+atomic_pard_goal_type(Info, RevGoalPathSteps, AtomicGoal, InstMapInfo,
+ GoalType, !:Messages) :-
+ !:Messages = cord.empty,
+ InstMapBefore = InstMapInfo ^ im_before,
+ InstMapAfter = InstMapInfo ^ im_after,
+ atomic_goal_is_call(AtomicGoal, IsCall),
+ (
+ IsCall = atomic_goal_is_trivial,
+ GoalType = pgt_other_atomic_goal
+ ;
+ IsCall = atomic_goal_is_call(Args),
+ % Lookup var use information.
+ map.lookup(Info ^ ipi_call_sites, rgp(RevGoalPathSteps), CallSite),
+ list.map_foldl(compute_var_modes(InstMapBefore, InstMapAfter),
+ Args, VarsAndModes, 0, _),
+ GoalType = pgt_call(VarsAndModes, CallSite)
+ ).
+
+:- pred atomic_pard_goal_cost(implicit_parallelism_info::in,
+ list(goal_path_step)::in, coverage_info::in, atomic_goal_rep::in,
+ goal_cost_csq::out) is det.
+
+atomic_pard_goal_cost(Info, RevGoalPathSteps, Coverage, AtomicGoal, Cost) :-
+ atomic_goal_is_call(AtomicGoal, IsCall),
+ (
+ IsCall = atomic_goal_is_trivial,
+ get_coverage_before_det(Coverage, Calls),
+ Cost = atomic_goal_cost(Calls)
+ ;
+ IsCall = atomic_goal_is_call(_),
+ RevGoalPath = rgp(RevGoalPathSteps),
+ map.lookup(Info ^ ipi_call_sites, RevGoalPath, CallSite),
+ (
+ cost_and_callees_is_recursive(Info ^ ipi_clique, CallSite),
+ map.search(Info ^ ipi_rec_call_sites, RevGoalPath, RecCost)
+ ->
+ CSCost = RecCost
+ ;
+ CSCost = CallSite ^ cac_cost
+ ),
+ Cost = call_goal_cost(CSCost)
+ ).
+
+:- pred compute_var_modes(inst_map::in, inst_map::in,
+ var_rep::in, var_and_mode::out, int::in, int::out) is det.
+
+compute_var_modes(InstMapBefore, InstMapAfter, Arg, VarAndMode, !ArgNum) :-
+ var_get_mode(InstMapBefore, InstMapAfter, Arg, Mode),
+ VarAndMode = var_and_mode(Arg, Mode),
+ !:ArgNum = !.ArgNum + 1.
+
+:- pred var_get_mode(inst_map::in, inst_map::in, var_rep::in,
+ var_mode_rep::out) is det.
+
+var_get_mode(InstMapBefore, InstMapAfter, VarRep, VarModeRep) :-
+ inst_map_get(InstMapBefore, VarRep, InstBefore, _),
+ inst_map_get(InstMapAfter, VarRep, InstAfter, _),
+ VarModeRep = var_mode_rep(InstBefore, InstAfter).
+
+%-----------------------------------------------------------------------------%
+
+can_parallelise_goal(Goal) :-
+ Detism = Goal ^ goal_detism_rep,
+ ( Detism = det_rep
+ ; Detism = cc_multidet_rep
+ ).
+ % XXX We would check purity here except that purity information is not
+ % present in the bytecode.
+
+:- pred goal_cost_above_par_threshold(implicit_parallelism_info::in,
+ goal_cost_csq::in) is semidet.
+
+goal_cost_above_par_threshold(Info, Cost) :-
+ goal_cost_get_calls(Cost) > 0,
+ PercallCost = goal_cost_get_percall(Cost),
+ PercallCost > float(Info ^ ipi_opts ^ cpcp_call_site_threshold).
+
+%-----------------------------------------------------------------------------%
Index: deep_profiler/autopar_types.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/autopar_types.m,v
retrieving revision 1.1
diff -u -b -r1.1 autopar_types.m
--- deep_profiler/autopar_types.m 27 Jan 2011 02:53:46 -0000 1.1
+++ deep_profiler/autopar_types.m 27 Jan 2011 05:22:42 -0000
@@ -1,7 +1,7 @@
%-----------------------------------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%-----------------------------------------------------------------------------%
-% Copyright (C) 2006-2011 The University of Melbourne.
+% Copyright (C) 2011 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -16,16 +16,15 @@
:- module mdprof_fb.automatic_parallelism.autopar_types.
:- interface.
-:- import_module profile.
+:- import_module analysis_utils.
+:- import_module coverage.
:- import_module mdbcomp.
:- import_module mdbcomp.feedback.
:- import_module mdbcomp.feedback.automatic_parallelism.
-:- import_module mdbcomp.program_representation.
-
-:- import_module analysis_utils.
-:- import_module coverage.
:- import_module mdbcomp.goal_path.
+:- import_module mdbcomp.program_representation.
:- import_module measurements.
+:- import_module profile.
:- import_module program_representation_utils.
:- import_module report.
:- import_module var_use_analysis.
@@ -33,8 +32,6 @@
:- import_module array.
:- import_module assoc_list.
:- import_module digraph.
-:- import_module float.
-:- import_module int.
:- import_module lazy.
:- import_module list.
:- import_module map.
@@ -263,6 +260,8 @@
:- implementation.
+:- import_module int.
+
ip_get_goals_before(Parallelisation) = GoalsBefore :-
Goals = Parallelisation ^ ip_goals,
FirstParGoalIndex = Parallelisation ^ ip_first_par_goal,
Index: deep_profiler/branch_and_bound.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/branch_and_bound.m,v
retrieving revision 1.3
diff -u -b -r1.3 branch_and_bound.m
--- deep_profiler/branch_and_bound.m 15 Dec 2010 06:30:32 -0000 1.3
+++ deep_profiler/branch_and_bound.m 27 Jan 2011 05:06:20 -0000
@@ -22,8 +22,6 @@
:- module branch_and_bound.
:- interface.
-:- import_module int.
-:- import_module float.
:- import_module set.
%-----------------------------------------------------------------------------%
@@ -105,6 +103,8 @@
:- implementation.
:- import_module benchmarking.
+:- import_module float.
+:- import_module int.
:- import_module io.
:- import_module list.
:- import_module mutvar.
Index: deep_profiler/coverage.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/coverage.m,v
retrieving revision 1.14
diff -u -b -r1.14 coverage.m
--- deep_profiler/coverage.m 17 Jan 2011 01:47:18 -0000 1.14
+++ deep_profiler/coverage.m 27 Jan 2011 05:06:48 -0000
@@ -123,7 +123,6 @@
:- import_module require.
:- import_module string.
:- import_module svmap.
-:- import_module unit.
%-----------------------------------------------------------------------------%
Index: deep_profiler/create_report.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/create_report.m,v
retrieving revision 1.33
diff -u -b -r1.33 create_report.m
--- deep_profiler/create_report.m 17 Jan 2011 01:47:18 -0000 1.33
+++ deep_profiler/create_report.m 27 Jan 2011 05:06:52 -0000
@@ -96,7 +96,6 @@
:- import_module array.
:- import_module char.
-:- import_module exception.
:- import_module float.
:- import_module int.
:- import_module list.
Index: deep_profiler/display.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/display.m,v
retrieving revision 1.13
diff -u -b -r1.13 display.m
--- deep_profiler/display.m 15 Dec 2010 06:30:33 -0000 1.13
+++ deep_profiler/display.m 27 Jan 2011 05:07:20 -0000
@@ -22,7 +22,6 @@
:- import_module list.
:- import_module maybe.
-:- import_module string.
%-----------------------------------------------------------------------------%
@@ -278,9 +277,7 @@
:- implementation.
-:- import_module assoc_list.
:- import_module int.
-:- import_module pair.
%-----------------------------------------------------------------------------%
Index: deep_profiler/html_format.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/html_format.m,v
retrieving revision 1.36
diff -u -b -r1.36 html_format.m
--- deep_profiler/html_format.m 15 Dec 2010 06:30:33 -0000 1.36
+++ deep_profiler/html_format.m 27 Jan 2011 05:07:41 -0000
@@ -65,11 +65,7 @@
:- implementation.
-:- import_module assoc_list.
-:- import_module bool.
:- import_module char.
-:- import_module exception.
-:- import_module float.
:- import_module list.
:- import_module int.
:- import_module map.
Index: deep_profiler/interface.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/interface.m,v
retrieving revision 1.22
diff -u -b -r1.22 interface.m
--- deep_profiler/interface.m 18 Aug 2008 02:14:51 -0000 1.22
+++ deep_profiler/interface.m 27 Jan 2011 05:08:04 -0000
@@ -104,11 +104,8 @@
:- implementation.
:- import_module conf.
-:- import_module util.
-:- import_module query.
:- import_module char.
-:- import_module int.
:- import_module list.
:- import_module require.
:- import_module string.
Index: deep_profiler/mdprof_cgi.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/mdprof_cgi.m,v
retrieving revision 1.32
diff -u -b -r1.32 mdprof_cgi.m
--- deep_profiler/mdprof_cgi.m 15 Dec 2010 06:30:33 -0000 1.32
+++ deep_profiler/mdprof_cgi.m 27 Jan 2011 05:08:50 -0000
@@ -31,13 +31,10 @@
:- import_module conf.
:- import_module interface.
-:- import_module mdbcomp.
-:- import_module mdbcomp.program_representation.
:- import_module profile.
:- import_module query.
:- import_module startup.
:- import_module timeout.
-:- import_module util.
:- import_module bool.
:- import_module char.
Index: deep_profiler/mdprof_dump.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/mdprof_dump.m,v
retrieving revision 1.10
diff -u -b -r1.10 mdprof_dump.m
--- deep_profiler/mdprof_dump.m 4 Aug 2008 03:17:45 -0000 1.10
+++ deep_profiler/mdprof_dump.m 27 Jan 2011 05:09:05 -0000
@@ -30,9 +30,7 @@
:- implementation.
-:- import_module array_util.
:- import_module dump.
-:- import_module profile.
:- import_module read_profile.
:- import_module bool.
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.39
diff -u -b -r1.39 mdprof_fb.automatic_parallelism.m
--- deep_profiler/mdprof_fb.automatic_parallelism.m 27 Jan 2011 02:53:46 -0000 1.39
+++ deep_profiler/mdprof_fb.automatic_parallelism.m 27 Jan 2011 05:03:10 -0000
@@ -16,10 +16,14 @@
:- module mdprof_fb.automatic_parallelism.
:- interface.
+:- include_module mdprof_fb.automatic_parallelism.autopar_reports.
:- include_module mdprof_fb.automatic_parallelism.autopar_search_callgraph.
:- implementation.
:- include_module mdprof_fb.automatic_parallelism.autopar_annotate.
+:- include_module mdprof_fb.automatic_parallelism.autopar_calc_overlap.
+:- include_module mdprof_fb.automatic_parallelism.autopar_costs.
:- include_module mdprof_fb.automatic_parallelism.autopar_find_best_par.
+:- include_module mdprof_fb.automatic_parallelism.autopar_search_goals.
:- include_module mdprof_fb.automatic_parallelism.autopar_types.
Index: deep_profiler/mdprof_feedback.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/mdprof_feedback.m,v
retrieving revision 1.34
diff -u -b -r1.34 mdprof_feedback.m
--- deep_profiler/mdprof_feedback.m 27 Jan 2011 02:53:46 -0000 1.34
+++ deep_profiler/mdprof_feedback.m 27 Jan 2011 05:02:47 -0000
@@ -38,6 +38,7 @@
:- import_module mdprof_fb.
:- import_module mdprof_fb.automatic_parallelism.
:- import_module mdprof_fb.automatic_parallelism.autopar_search_callgraph.
+:- import_module mdprof_fb.automatic_parallelism.autopar_reports.
:- import_module message.
:- import_module profile.
:- import_module startup.
@@ -226,7 +227,7 @@
ParalleliseDepConjs = do_not_parallelise_dep_conjs,
ParalleliseDepConjsStr = "no"
),
- map(create_candidate_parallel_conj_proc_report, Conjs, ReportConjs),
+ list.map(create_candidate_parallel_conj_proc_report, Conjs, ReportConjs),
Report = append_list(list(ReportHeader ++ cord_list_to_cord(ReportConjs))).
:- func help_message = string.
Index: deep_profiler/mdprof_procrep.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/mdprof_procrep.m,v
retrieving revision 1.6
diff -u -b -r1.6 mdprof_procrep.m
--- deep_profiler/mdprof_procrep.m 4 Sep 2008 11:41:02 -0000 1.6
+++ deep_profiler/mdprof_procrep.m 27 Jan 2011 05:23:16 -0000
@@ -28,19 +28,13 @@
:- implementation.
:- import_module mdbcomp.
-:- import_module mdbcomp.prim_data.
:- import_module mdbcomp.program_representation.
-:- import_module mdbcomp.rtti_access.
:- import_module program_representation_utils.
-:- import_module bool.
-:- import_module char.
:- import_module cord.
-:- import_module int.
:- import_module list.
:- import_module map.
:- import_module maybe.
-:- import_module require.
:- import_module string.
%-----------------------------------------------------------------------------%
Index: deep_profiler/mdprof_test.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/mdprof_test.m,v
retrieving revision 1.25
diff -u -b -r1.25 mdprof_test.m
--- deep_profiler/mdprof_test.m 15 Dec 2010 06:30:34 -0000 1.25
+++ deep_profiler/mdprof_test.m 27 Jan 2011 05:23:46 -0000
@@ -29,26 +29,21 @@
:- import_module conf.
:- import_module dump.
-:- import_module interface.
:- import_module mdbcomp.
:- import_module mdbcomp.program_representation.
:- import_module profile.
:- import_module query.
:- import_module startup.
-:- import_module timeout.
-:- import_module util.
:- import_module array.
:- import_module bool.
:- import_module char.
-:- import_module exception.
:- import_module getopt.
:- import_module int.
:- import_module library.
:- import_module list.
:- import_module maybe.
:- import_module require.
-:- import_module set.
:- import_module string.
%-----------------------------------------------------------------------------%
Index: deep_profiler/measurement_units.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/measurement_units.m,v
retrieving revision 1.10
diff -u -b -r1.10 measurement_units.m
--- deep_profiler/measurement_units.m 20 Jan 2011 13:44:10 -0000 1.10
+++ deep_profiler/measurement_units.m 27 Jan 2011 05:25:25 -0000
@@ -18,9 +18,6 @@
:- interface.
-:- import_module int.
-:- import_module string.
-
%-----------------------------------------------------------------------------%
%
% Memory
@@ -166,11 +163,10 @@
:- implementation.
:- import_module char.
-:- import_module exception.
:- import_module float.
:- import_module list.
-:- import_module math.
:- import_module require.
+:- import_module string.
%-----------------------------------------------------------------------------%
%
Index: deep_profiler/measurements.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/measurements.m,v
retrieving revision 1.28
diff -u -b -r1.28 measurements.m
--- deep_profiler/measurements.m 22 Jan 2011 04:27:01 -0000 1.28
+++ deep_profiler/measurements.m 27 Jan 2011 05:26:34 -0000
@@ -311,7 +311,6 @@
:- implementation.
-:- import_module bool.
:- import_module float.
:- import_module int.
:- import_module require.
Index: deep_profiler/message.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/message.m,v
retrieving revision 1.15
diff -u -b -r1.15 message.m
--- deep_profiler/message.m 20 Jan 2011 05:35:11 -0000 1.15
+++ deep_profiler/message.m 27 Jan 2011 05:27:09 -0000
@@ -24,9 +24,7 @@
:- import_module profile.
:- import_module cord.
-:- import_module int.
:- import_module io.
-:- import_module string.
%-----------------------------------------------------------------------------%
@@ -196,10 +194,12 @@
:- implementation.
+:- import_module program_representation_utils.
+
+:- import_module int.
:- import_module list.
:- import_module require.
-
-:- import_module program_representation_utils.
+:- import_module string.
%-----------------------------------------------------------------------------%
Index: deep_profiler/program_representation_utils.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/program_representation_utils.m,v
retrieving revision 1.32
diff -u -b -r1.32 program_representation_utils.m
--- deep_profiler/program_representation_utils.m 23 Jan 2011 06:30:16 -0000 1.32
+++ deep_profiler/program_representation_utils.m 27 Jan 2011 05:28:26 -0000
@@ -27,7 +27,6 @@
:- import_module cord.
:- import_module list.
:- import_module set.
-:- import_module string.
:- import_module unit.
%----------------------------------------------------------------------------%
@@ -204,15 +203,14 @@
:- import_module mdbcomp.prim_data.
-:- import_module array.
:- import_module bool.
:- import_module counter.
:- import_module int.
-:- import_module io.
:- import_module map.
:- import_module maybe.
:- import_module require.
:- import_module std_util.
+:- import_module string.
:- import_module svmap.
%----------------------------------------------------------------------------%
Index: deep_profiler/query.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/query.m,v
retrieving revision 1.41
diff -u -b -r1.41 query.m
--- deep_profiler/query.m 27 Jan 2011 03:05:04 -0000 1.41
+++ deep_profiler/query.m 27 Jan 2011 05:29:20 -0000
@@ -362,11 +362,9 @@
:- implementation.
-:- import_module apply_exclusion.
:- import_module create_report.
:- import_module display_report.
:- import_module html_format.
-:- import_module measurements.
:- import_module report.
:- import_module util.
@@ -376,7 +374,6 @@
:- import_module list.
:- import_module math.
:- import_module maybe.
-:- import_module require.
:- import_module string.
:- import_module univ.
Index: deep_profiler/read_profile.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/read_profile.m,v
retrieving revision 1.34
diff -u -b -r1.34 read_profile.m
--- deep_profiler/read_profile.m 13 Jan 2011 00:36:55 -0000 1.34
+++ deep_profiler/read_profile.m 27 Jan 2011 05:27:53 -0000
@@ -31,7 +31,6 @@
:- implementation.
:- import_module array_util.
-:- import_module exception.
:- import_module io_combinator.
:- import_module measurements.
:- import_module mdbcomp.
Index: deep_profiler/recursion_patterns.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/recursion_patterns.m,v
retrieving revision 1.13
diff -u -b -r1.13 recursion_patterns.m
--- deep_profiler/recursion_patterns.m 17 Jan 2011 01:47:18 -0000 1.13
+++ deep_profiler/recursion_patterns.m 27 Jan 2011 05:29:46 -0000
@@ -53,7 +53,6 @@
:- import_module mdbcomp.program_representation.
:- import_module measurement_units.
:- import_module measurements.
-:- import_module program_representation_utils.
:- import_module report.
:- import_module array.
Index: deep_profiler/var_use_analysis.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/deep_profiler/var_use_analysis.m,v
retrieving revision 1.14
diff -u -b -r1.14 var_use_analysis.m
--- deep_profiler/var_use_analysis.m 23 Jan 2011 06:30:16 -0000 1.14
+++ deep_profiler/var_use_analysis.m 27 Jan 2011 05:27:47 -0000
@@ -141,7 +141,6 @@
:- implementation.
-:- import_module create_report.
:- import_module measurement_units.
:- import_module program_representation_utils.
:- import_module recursion_patterns.
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/base64
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/curs
cvs diff: Diffing extras/curs/samples
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/error
cvs diff: Diffing extras/fixed
cvs diff: Diffing extras/gator
cvs diff: Diffing extras/gator/generations
cvs diff: Diffing extras/gator/generations/1
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/easyx
cvs diff: Diffing extras/graphics/easyx/samples
cvs diff: Diffing extras/graphics/mercury_allegro
cvs diff: Diffing extras/graphics/mercury_allegro/examples
cvs diff: Diffing extras/graphics/mercury_allegro/samples
cvs diff: Diffing extras/graphics/mercury_allegro/samples/demo
cvs diff: Diffing extras/graphics/mercury_allegro/samples/mandel
cvs diff: Diffing extras/graphics/mercury_allegro/samples/pendulum2
cvs diff: Diffing extras/graphics/mercury_allegro/samples/speed
cvs diff: Diffing extras/graphics/mercury_cairo
cvs diff: Diffing extras/graphics/mercury_cairo/samples
cvs diff: Diffing extras/graphics/mercury_cairo/samples/data
cvs diff: Diffing extras/graphics/mercury_cairo/tutorial
cvs diff: Diffing extras/graphics/mercury_glut
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/gears
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/lex
cvs diff: Diffing extras/lex/samples
cvs diff: Diffing extras/lex/tests
cvs diff: Diffing extras/log4m
cvs diff: Diffing extras/logged_output
cvs diff: Diffing extras/monte
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/moose/tests
cvs diff: Diffing extras/mopenssl
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/net
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/posix/samples
cvs diff: Diffing extras/quickcheck
cvs diff: Diffing extras/quickcheck/tutes
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/solver_types
cvs diff: Diffing extras/solver_types/library
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/windows_installer_generator
cvs diff: Diffing extras/windows_installer_generator/sample
cvs diff: Diffing extras/windows_installer_generator/sample/images
cvs diff: Diffing extras/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing extras/xml_stylesheets
cvs diff: Diffing java
cvs diff: Diffing java/runtime
cvs diff: Diffing library
Index: library/Mercury.options
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/Mercury.options,v
retrieving revision 1.35
diff -u -b -r1.35 Mercury.options
--- library/Mercury.options 7 Oct 2010 05:03:12 -0000 1.35
+++ library/Mercury.options 27 Jan 2011 05:36:08 -0000
@@ -94,3 +94,6 @@
# and comparison code for lazy values.
MCFLAGS-lazy += --no-warn-non-term-special-preds
+# Work around a problem with --warn-unused-imports: it complains about
+# erlang_rtti_implementation, which is needed in some grades.
+MCFLAGS-type_desc += --no-warn-unused-imports
cvs diff: Diffing mdbcomp
Index: mdbcomp/program_representation.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/mdbcomp/program_representation.m,v
retrieving revision 1.58
diff -u -b -r1.58 program_representation.m
--- mdbcomp/program_representation.m 13 Jan 2011 00:36:56 -0000 1.58
+++ mdbcomp/program_representation.m 27 Jan 2011 05:08:32 -0000
@@ -622,8 +622,6 @@
:- implementation.
-:- import_module char.
-:- import_module exception.
:- import_module int.
:- import_module map.
:- import_module require.
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/standalone_c
cvs diff: Diffing samples/concurrency
cvs diff: Diffing samples/concurrency/dining_philosophers
cvs diff: Diffing samples/concurrency/midimon
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/java_interface
cvs diff: Diffing samples/java_interface/java_calls_mercury
cvs diff: Diffing samples/java_interface/mercury_calls_java
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/solver_types
cvs diff: Diffing samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing slice
cvs diff: Diffing ssdb
cvs diff: Diffing tests
cvs diff: Diffing tests/analysis
cvs diff: Diffing tests/analysis/ctgc
cvs diff: Diffing tests/analysis/excp
cvs diff: Diffing tests/analysis/ext
cvs diff: Diffing tests/analysis/sharing
cvs diff: Diffing tests/analysis/table
cvs diff: Diffing tests/analysis/trail
cvs diff: Diffing tests/analysis/unused_args
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/general/string_format
cvs diff: Diffing tests/general/structure_reuse
cvs diff: Diffing tests/grade_subdirs
cvs diff: Diffing tests/hard_coded
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/mmc_make
cvs diff: Diffing tests/mmc_make/lib
cvs diff: Diffing tests/par_conj
cvs diff: Diffing tests/recompilation
cvs diff: Diffing tests/stm
cvs diff: Diffing tests/stm/orig
cvs diff: Diffing tests/stm/orig/stm-compiler
cvs diff: Diffing tests/stm/orig/stm-compiler/test1
cvs diff: Diffing tests/stm/orig/stm-compiler/test10
cvs diff: Diffing tests/stm/orig/stm-compiler/test2
cvs diff: Diffing tests/stm/orig/stm-compiler/test3
cvs diff: Diffing tests/stm/orig/stm-compiler/test4
cvs diff: Diffing tests/stm/orig/stm-compiler/test5
cvs diff: Diffing tests/stm/orig/stm-compiler/test6
cvs diff: Diffing tests/stm/orig/stm-compiler/test7
cvs diff: Diffing tests/stm/orig/stm-compiler/test8
cvs diff: Diffing tests/stm/orig/stm-compiler/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/stmqueue
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test10
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test11
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test9
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/trailing
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing util
cvs diff: Diffing vim
cvs diff: Diffing vim/after
cvs diff: Diffing vim/ftplugin
cvs diff: Diffing vim/syntax
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to: mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the reviews
mailing list