[m-rev.] diff: Fix bug #364: Add a specific cost analysis for nondet disjunctions.

[Paul Bone]

Branches: master, version-14_01-branch

---

Fix bug #364: Add a specific cost analysis for nondet disjunctions.

This bug was caused because we assumed that all disjunctions that the cost
analysis examined were semidet disjunctions.  This patch adds a separate
predicate to calculate the cost of nondet disjunctions, it simply sums up
the costs of the disjuncts.

deep_profiler/autopar_costs.m:
    As above.

deep_profiler/autopar_search_goals.m
    Conform to above changes.

deep_profiler/autopar_search_callgraph.m:
    When the auto-parallelisation analysis of a procedure throws an
    exception print out the identity of the procedure.

NEWS:
    Add news item.
---
 NEWS                                     |  2 ++
 deep_profiler/autopar_costs.m            | 44 ++++++++++++++++++++++++++++----
 deep_profiler/autopar_search_callgraph.m | 32 +++++++++++++++++++----
 deep_profiler/autopar_search_goals.m     |  4 +--
 4 files changed, 70 insertions(+), 12 deletions(-)

diff --git a/NEWS b/NEWS
index f2f948b..9079523 100644
--- a/NEWS
+++ b/NEWS
@@ -3,6 +3,8 @@ NEWS for Mercury 14.01.2
 
 This is a bug-fix release.
 
++ Fix the handling of nondet code by the auto-parallelisation analysis in
+  mdprof_create_feedback.  (Bug #364)
 
 NEWS for Mercury 14.01.1
 ------------------------
diff --git a/deep_profiler/autopar_costs.m b/deep_profiler/autopar_costs.m
index 15f428c..a349830 100644
--- a/deep_profiler/autopar_costs.m
+++ b/deep_profiler/autopar_costs.m
@@ -35,7 +35,7 @@
 :- 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,
+:- pred disj_calc_cost(detism_rep::in, 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,
@@ -99,8 +99,25 @@ conj_calc_cost([Conj | Conjs], _, Cost) :-
     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) :-
+disj_calc_cost(Detism, Disjs, Calls, Cost) :-
+    Solutions = detism_get_solutions(Detism),
+    (
+        ( Solutions = at_most_zero_rep
+        ; Solutions = at_most_one_rep
+        ),
+        % This is a semidet or committed choice disjunction, there's no
+        % backtracking.
+        disj_calc_cost_semidet(Disjs, Calls, Cost)
+    ;
+        Solutions = at_most_many_rep,
+        disj_calc_cost_nondet(Disjs, Calls, Cost)
+    ).
+
+:- pred disj_calc_cost_semidet(list(pard_goal_detail)::in, int::in,
+    goal_cost_csq::out) is det.
+
+disj_calc_cost_semidet([], Calls, simple_goal_cost(Calls)).
+disj_calc_cost_semidet([Disj | Disjs], _, Cost) :-
     Coverage = Disj ^ goal_annotation ^ pgd_coverage,
     get_coverage_before_and_after_det(Coverage, Before, After),
     ( Before = 0 ->
@@ -109,14 +126,31 @@ disj_calc_cost([Disj | Disjs], _, Cost) :-
     ;
         _Successes = After,
         Failures = Before - After,
-        % XXX: We assume this is a semidet disjunction
-        disj_calc_cost(Disjs, Failures, FailureCost),
+        disj_calc_cost_semidet(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 disj_calc_cost_nondet(list(pard_goal_detail)::in, int::in,
+    goal_cost_csq::out) is det.
+
+disj_calc_cost_nondet([], Calls, simple_goal_cost(Calls)).
+disj_calc_cost_nondet([Disj | Disjs], Calls, Cost) :-
+    Coverage = Disj ^ goal_annotation ^ pgd_coverage,
+    get_coverage_before_det(Coverage, Before),
+    ( Before = 0 ->
+        % Avoid a divide by zero.
+        Cost = dead_goal_cost
+    ;
+        % TODO: This is very approximate, it calculates the percall cost.
+        % For nondet code we probably want the per-call and per-redo cost.
+        disj_calc_cost_nondet(Disjs, Calls, DisjsCost),
+        DisjCost = Disj ^ goal_annotation ^ pgd_cost,
+        Cost = add_goal_costs_seq(DisjCost, DisjsCost)
+    ).
+
 switch_calc_cost([], Calls, simple_goal_cost(Calls)).
 switch_calc_cost([Case | Cases], TotalCalls, Cost) :-
     ( TotalCalls = 0 ->
diff --git a/deep_profiler/autopar_search_callgraph.m b/deep_profiler/autopar_search_callgraph.m
index a201ce8..5ea6707 100644
--- a/deep_profiler/autopar_search_callgraph.m
+++ b/deep_profiler/autopar_search_callgraph.m
@@ -51,21 +51,23 @@
 :- import_module measurement_units.
 :- import_module measurements.
 :- import_module program_representation_utils.
+:- import_module read_profile.
 :- import_module recursion_patterns.
 :- import_module report.
 :- import_module var_use_analysis.
 
-:- import_module pair.
-:- import_module list.
 :- import_module array.
 :- import_module assoc_list.
 :- import_module bool.
+:- import_module exception.
 :- import_module float.
-:- import_module io.
 :- 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 set.
 :- import_module string.
@@ -403,8 +405,28 @@ candidate_parallel_conjunctions_clique_proc(Opts, Deep, RecursionType,
         ),
 
         % Analyse this procedure for parallelism opportunities.
-        candidate_parallel_conjunctions_proc(Opts, Deep, PDPtr, RecursionType,
-            RecursiveCallSiteCostMap, Candidates, ProcMessages),
+        promise_equivalent_solutions [Candidates, ProcMessages]
+        ( try [] (
+            candidate_parallel_conjunctions_proc(Opts, Deep, PDPtr,
+                RecursionType, RecursiveCallSiteCostMap, CandidatesPrime,
+                ProcMessagesPrime)
+        )
+        then (
+            Candidates = CandidatesPrime,
+            ProcMessages = ProcMessagesPrime
+        )
+        catch_any Exp -> (
+            trace [io(!IO)] (
+                PDPtr = proc_dynamic_ptr(PDId),
+                deep_lookup_proc_dynamics(Deep, PDPtr, PD),
+                deep_lookup_proc_statics(Deep, PD ^ pd_proc_static, PS),
+                ProcName = PS ^ ps_q_refined_id,
+                io.format(io.stderr_stream,
+                    "Exception while analyising proc dynamic %d (%s)\n",
+                    [i(PDId), s(ProcName)], !IO)
+            ),
+            throw(Exp)
+        )),
         !:Messages = !.Messages ++ ProcMessages,
         Messages = !.Messages
     ).
diff --git a/deep_profiler/autopar_search_goals.m b/deep_profiler/autopar_search_goals.m
index de7f17f..b4e0efc 100644
--- a/deep_profiler/autopar_search_goals.m
+++ b/deep_profiler/autopar_search_goals.m
@@ -167,7 +167,7 @@ goal_get_conjunctions_worth_parallelising(Info, RevGoalPath,
                 Disjs0, Disjs, 1, _, cord.empty, Candidates,
                 cord.empty, Pushes, cord.empty, Singles,
                 cord.empty, Messages),
-            disj_calc_cost(Disjs, Calls, Cost),
+            disj_calc_cost(DetismRep, Disjs, Calls, Cost),
             GoalExpr = disj_rep(Disjs)
         ;
             GoalExpr0 = switch_rep(Var, CanFail, Cases0),
@@ -786,7 +786,7 @@ goal_to_pard_goal(Info, RevGoalPath, Goal, DetailGoal, !Messages) :-
             GoalExpr = disj_rep(Disjs),
             list.map_foldl2(disj_to_pard_goals(Info, RevGoalPath),
                 Disjs, DetailDisjs, 1, _, !Messages),
-            disj_calc_cost(DetailDisjs, Before, Cost),
+            disj_calc_cost(Detism, DetailDisjs, Before, Cost),
             DetailGoalExpr = disj_rep(DetailDisjs)
         ;
             GoalExpr = switch_rep(Var, CanFail, Cases),
-- 
2.1.0