[m-rev.] diff: Make the recursion patterns analysis more robust.

[Paul Bone]

Make the recursion patterns analysis more robust.

Handle semidet and committed choice disjunctions in the recursion patterns
analysis.

deep_profiler/recursion_patterns.m:
    As above.

deep_profiler/measurement_units.m:
    Add a new function, not_probability that returns the probability that a
    certain probability will not occur.

Index: deep_profiler/measurement_units.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/measurement_units.m,v
retrieving revision 1.7
diff -u -p -b -r1.7 measurement_units.m
--- deep_profiler/measurement_units.m	26 Aug 2010 06:29:27 -0000	1.7
+++ deep_profiler/measurement_units.m	8 Oct 2010 12:46:26 -0000
@@ -137,6 +137,9 @@
 :- func or(probability, probability) = probability.
 :- func and(probability, probability) = probability.
 
+    % The probability of the given probability not occuring.
+:- func not_probability(probability) = probability.
+
 %-----------------------------------------------------------------------------%
 %
 % Code for formatting numbers.
@@ -306,6 +309,8 @@ or(A, B) = A + B.
     % Combine conjoint probabilities with multiplication.
 and(A, B) = A * B.
 
+not_probability(X) = 1.0 - X.
+
 %-----------------------------------------------------------------------------%
 %
 % Code for formatting numbers.
Index: deep_profiler/recursion_patterns.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/recursion_patterns.m,v
retrieving revision 1.5
diff -u -p -b -r1.5 recursion_patterns.m
--- deep_profiler/recursion_patterns.m	7 Oct 2010 02:38:10 -0000	1.5
+++ deep_profiler/recursion_patterns.m	8 Oct 2010 12:46:26 -0000
@@ -276,8 +276,7 @@ single_rec_average_recursion_cost(BaseCo
             ).
 
 :- type recursion_error
-    --->    re_unhandled_determinism(detism_rep)
-    ;       re_unhandled_disjunction.
+    --->    re_unhandled_determinism(detism_rep).
 
     % goal_recursion_data(RecursiveCallees, Goal, GoalPath,
     %   init_recursion_data, RecursionData)
@@ -306,8 +305,8 @@ goal_recursion_data(ThisClique, CallSite
                 Conjs, !:RecursionData)
         ;
             GoalExpr = disj_rep(Disjs),
-            disj_recursion_data(ThisClique, CallSiteMap, GoalPath, 1, Disjs,
-                !:RecursionData)
+            disj_recursion_data(ThisClique, CallSiteMap, GoalPath, 1, certain, 
+                Disjs, !:RecursionData)
         ;
             GoalExpr = switch_rep(_, _, Cases),
             switch_recursion_data(ThisClique, CallSiteMap, GoalPath, 1, Cases,
@@ -370,18 +369,8 @@ conj_recursion_data(ThisClique, CallSite
         RecursionData = proc_dead_code
     ;
         ConjRecursionData = recursion_data(_, _, _), 
-        ( 
-            get_coverage_before_and_after(Conj ^ goal_annotation, Before, After)
-        ->
-            ( After > Before ->
-                % Nondet code can overflow this probability.
-                ConjSuccessProb = certain
-            ;
-                ConjSuccessProb = probable(float(After) / float(Before))
-            )
-        ;
-            error(this_file ++ "expected complete coverage information")
-        ), 
+        success_probability_from_coverage(Conj ^ goal_annotation,
+            ConjSuccessProb),
         SuccessProb = and(SuccessProb0, ConjSuccessProb),
         conj_recursion_data(ThisClique, CallSiteMap, GoalPath, ConjNum + 1,
             SuccessProb, Conjs, ConjsRecursionData),
@@ -391,11 +380,52 @@ conj_recursion_data(ThisClique, CallSite
 
 :- pred disj_recursion_data(clique_ptr::in, 
     map(goal_path, cost_and_callees)::in, goal_path::in, int::in, 
-    list(goal_rep(coverage_info))::in, recursion_data::out) is det.
+    probability::in, list(goal_rep(coverage_info))::in, recursion_data::out)
+    is det.
+
+disj_recursion_data(_, _, _, _, _, [], simple_recursion_data(0.0, 0)).
+disj_recursion_data(ThisClique, CallSiteMap, GoalPath, DisjNum, FailureProb0, 
+        [Disj | Disjs], RecursionData) :-
+    % Handle only semidet and committed-choice disjunctions, once a goal
+    % succeeds it cannot be re-entered.
+    goal_recursion_data(ThisClique, CallSiteMap,
+        goal_path_add_at_end(GoalPath, step_disj(DisjNum)), Disj,
+        DisjRecursionData),
+    (
+        DisjRecursionData = proc_dead_code,
+        % If the first disjunct was never tried then no other disjuncts will
+        % ever be tried.
+        RecursionData = proc_dead_code
+    ;
+        DisjRecursionData = recursion_data(_, _, _),
+        % Handle this just like a semidet conjunction, except that we go to the
+        % next disjunct if it _fails_.
+        success_probability_from_coverage(Disj ^ goal_annotation,
+            ConjSuccessProb),
+        ConjFailureProb = not_probability(ConjSuccessProb), 
+        FailureProb = and(FailureProb0, ConjFailureProb),
+        disj_recursion_data(ThisClique, CallSiteMap, GoalPath, DisjNum + 1,
+            FailureProb, Disjs, DisjsRecursionData),
+        merge_recursion_data_sequence(DisjRecursionData, DisjsRecursionData,
+            RecursionData)
+    ).
 
-disj_recursion_data(_, _, _, _, _, !:RecursionData) :-
-    !:RecursionData = simple_recursion_data(0.0, 0),
-    recursion_data_add_error(re_unhandled_disjunction, !RecursionData).
+:- pred success_probability_from_coverage(coverage_info::in, probability::out)
+    is det.
+
+success_probability_from_coverage(Coverage, SuccessProb) :-
+    ( 
+        get_coverage_before_and_after(Coverage, Before, After)
+    ->
+        ( After > Before ->
+            % Nondet code can overflow this probability.
+            SuccessProb = certain
+        ;
+            SuccessProb = probable(float(After) / float(Before))
+        )
+    ;
+        error(this_file ++ "expected complete coverage information")
+    ). 
 
 :- pred ite_recursion_data(clique_ptr::in, 
     map(goal_path, cost_and_callees)::in, goal_path::in, 
@@ -700,8 +730,6 @@ simple_recursion_data(Cost, Calls) = 
 
 error_to_string(re_unhandled_determinism(Detism)) = 
     format("%s code is not handled", [s(string(Detism))]).
-error_to_string(re_unhandled_disjunction) = 
-    "Disjunctions are not currently handled".
 
 %----------------------------------------------------------------------------%
 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: Digital signature
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20101008/dddb33bc/attachment.sig>