[m-rev.] diff: improve loop invariant testing

Fergus Henderson fjh at cs.mu.OZ.AU
Mon Feb 9 19:16:47 AEDT 2004


Estimated hours taken: 2
Branches: main

Improve the testing of loop invariant hoisting.

tests/hard_coded/Mercury.options:
	Ensure that we compile the tests of loop invariant hoisting
	with the loop invariant hoisting optimization enabled, and with
	`--trace-optimized' so that it stays enabled even in debugging grades.

tests/hard_coded/loop_inv_test.m:
tests/hard_coded/loop_inv_test.inp:
tests/hard_coded/loop_inv_test.exp:
	Add a new test of loop invariant hoisting -- one that our
	current implementation actually passes.

tests/hard_coded/Mmakefile:
	Enable the new test.

tests/hard_coded/Mmakefile:
tests/hard_coded/loop_inv_test0.m:
tests/hard_coded/loop_inv_test1.m:
tests/hard_coded/loop_inv_test2.m:
	Add some comments, explaining why we don't pass these test cases.
	
tests/hard_coded/loop_inv_test1.m:
	Modify the second test in this test case, so that it is not
	testing the same thing as loop_inv_test0.m.

Workspace: /home/jupiter/fjh/ws-jupiter/mercury
Index: tests/hard_coded/Mercury.options
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mercury.options,v
retrieving revision 1.7
diff -u -d -r1.7 Mercury.options
--- tests/hard_coded/Mercury.options	22 Jul 2003 07:04:26 -0000	1.7
+++ tests/hard_coded/Mercury.options	9 Feb 2004 08:13:22 -0000
@@ -22,6 +22,10 @@
 MCFLAGS-intermod_type_qual2 =	--intermodule-optimization
 MCFLAGS-intermod_multimode =	--intermodule-optimization
 MCFLAGS-intermod_multimode_main = --intermodule-optimization
+MCFLAGS-loop_inv_test 	= 	--loop-invariants --trace-optimized
+MCFLAGS-loop_inv_test0 	= 	--loop-invariants --trace-optimized
+MCFLAGS-loop_inv_test1 	= 	--loop-invariants --trace-optimized
+MCFLAGS-loop_inv_test2 	= 	--loop-invariants --trace-optimized
 MCFLAGS-no_inline_builtins =	--no-inline-builtins
 MCFLAGS-no_warn_singleton =	--halt-at-warn
 MCFLAGS-nondet_copy_out =	--no-inlining --nondet-copy-out
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.220
diff -u -d -r1.220 Mmakefile
--- tests/hard_coded/Mmakefile	27 Jan 2004 03:26:37 -0000	1.220
+++ tests/hard_coded/Mmakefile	9 Feb 2004 08:00:06 -0000
@@ -100,6 +100,7 @@
 	intermod_pragma_clause \
 	intermod_type_qual \
 	join_list \
+	loop_inv_test \
 	mapped_module \
 	merge_and_remove_dups \
 	minint_bug \
@@ -294,8 +295,10 @@
 #     top of library/float.m.
 #
 # XXX loop_inv_test0, loop_inv_test1, loop_inv_test2:
-#     loop invariant optimization is not properly optimizing these cases.
-#
+#     These test cases test some more sophisticated cases of loop invariant
+#     optimization which are current loop_inv pass is not capable of
+#     optimizing.
+#     
 # XXX var_not_found -- mode error in automatically generated unification
 #		predicate.  This test uses partially instantiated modes,
 #		which are not yet fully supported.
Index: tests/hard_coded/loop_inv_test.exp
===================================================================
RCS file: tests/hard_coded/loop_inv_test.exp
diff -N tests/hard_coded/loop_inv_test.exp
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/loop_inv_test.exp	9 Feb 2004 08:09:24 -0000
@@ -0,0 +1,3 @@
+enter three integers, one on each line
+R1 = 7513
+R2 = 8613
Index: tests/hard_coded/loop_inv_test.inp
===================================================================
RCS file: tests/hard_coded/loop_inv_test.inp
diff -N tests/hard_coded/loop_inv_test.inp
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/loop_inv_test.inp	9 Feb 2004 08:09:17 -0000
@@ -0,0 +1,3 @@
+100
+33
+13
Index: tests/hard_coded/loop_inv_test.m
===================================================================
RCS file: tests/hard_coded/loop_inv_test.m
diff -N tests/hard_coded/loop_inv_test.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/loop_inv_test.m	9 Feb 2004 08:12:26 -0000
@@ -0,0 +1,116 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%-----------------------------------------------------------------------------%
+
+% This module tests the loop invariant hoisting optimization.
+% It does so using foreign_procs which abort if called twice:
+% if loop invariant hoisting works, these procedures will only
+% be called once, but if loop invariant hoisting doesn't work,
+% these procedures will abort.
+
+% This test checks that we do the basics of loop invariant hoisting.
+
+:- module loop_inv_test.
+:- interface.
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+:- implementation.
+:- import_module int, string.
+
+main -->
+    io__print("enter three integers, one on each line\n"), io__flush_output,
+    io__read_line_as_string(Res1),
+    io__read_line_as_string(Res2),
+    io__read_line_as_string(Res3),
+    ( { Res1 = ok(L1), Res2 = ok(L2), Res3 = ok(L3) } ->
+	    { N1 = string__det_to_int(string__chomp(L1)) },
+	    { N2 = string__det_to_int(string__chomp(L2)) },
+	    { N3 = string__det_to_int(string__chomp(L3)) },
+	    { loop1(N1, N2, N3, R1) },
+	    { loop2(N1, N2, N3, R2) },
+	    io__print("R1 = "), io__print(R1), io__nl,
+	    io__print("R2 = "), io__print(R2), io__nl
+    ;
+        io__print("input error"), io__nl
+    ).
+
+/* Test that we can do ordinary loop hoisting:
+   p/1 will abort if called twice. */
+:- pred loop1(int::in, int::in, int::in, int::out) is det.
+loop1(N, Inv, Acc0, Acc) :-
+    ( N =< 0 ->
+        Acc = Acc0
+    ;
+        p(Inv, X),
+        Acc1 = Acc0 + X,
+        loop1(N - 1, Inv, Acc1, Acc)
+    ).
+
+/* Test that we can do ordinary loop hoisting, in the case
+   where the invariant predicate is an inlined foreign_proc
+   q/1 will abort if called twice. */
+:- pred loop2(int::in, int::in, int::in, int::out) is det.
+loop2(N, Inv, Acc0, Acc) :-
+    ( N =< 0 ->
+        Acc = Acc0
+    ;
+        q(Inv, X),
+        Acc1 = Acc0 + X,
+        loop2(N - 1, Inv, Acc1, Acc)
+    ).
+
+:- pragma no_inline(p/2).
+:- pragma inline(q/2).
+
+:- pred p(int::in, int::out) is det.
+:- pragma foreign_proc("C", p(Inv::in, X::out),
+    [will_not_call_mercury, promise_pure],
+"
+    /* Test that p/1 only gets called once. */
+    static int num_calls = 0;
+    if (num_calls++) { 
+        MR_fatal_error(""p/1 called more than once"");
+        abort();
+    }
+
+    X = Inv + 42;
+").
+:- pragma foreign_proc("C#", p(Inv::in, X::out),
+    [will_not_call_mercury, promise_pure],
+"
+    /* Test that p/1 only gets called once. */
+    static int num_calls = 0;
+    if (num_calls++) { 
+        mercury.runtime.Errors.fatal_error(""p/1 called more than once"");
+    }
+
+    X = Inv + 42;
+").
+
+:- pred q(int::in, int::out) is det.
+:- pragma foreign_proc("C", q(Inv::in, X::out),
+    [will_not_call_mercury, promise_pure],
+"
+    /* Test that q/1 only gets called once. */
+    static int num_calls = 0;
+    if (num_calls++) { 
+        MR_fatal_error(""q/1 called more than once"");
+    }
+
+    X = Inv + 53;
+").
+:- pragma foreign_proc("C#", q(Inv::in, X::out),
+    [will_not_call_mercury, promise_pure],
+"
+    /* Test that q/1 only gets called once. */
+    static int num_calls = 0;
+    if (num_calls++) { 
+        mercury.runtime.Errors.fatal_error(""q/1 called more than once"");
+    }
+
+    X = Inv + 53;
+").
+
+%-----------------------------------------------------------------------------%
Index: tests/hard_coded/loop_inv_test0.m
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/loop_inv_test0.m,v
retrieving revision 1.1
diff -u -d -r1.1 loop_inv_test0.m
--- tests/hard_coded/loop_inv_test0.m	18 Feb 2003 03:38:19 -0000	1.1
+++ tests/hard_coded/loop_inv_test0.m	9 Feb 2004 06:25:16 -0000
@@ -8,7 +8,11 @@
 % be called once, but if loop invariant hoisting doesn't work,
 % these procedures will abort.
 
-% This test checks that we do the basics of loop invariant hoisting.
+% This test checks that we can do loop invariant hoisting for
+% calls which occur in different branches of an if-then-else.
+
+% XXX we do not yet pass this test case (see XXX comment below).
+%     Should be easy to fix??
 
 :- module loop_inv_test0.
 :- interface.
@@ -50,6 +54,11 @@
 
 /* Test that we can do loop hoisting for calls which occur in
    different branches of an if-then-else: q/1 will abort if called twice. */
+% XXX currently loop invariant hoisting does NOT optimize this case,
+%     because the variable `X' gets renamed to two different variables
+%     for the two different scopes in which it occurs, and then loop
+%     invariant hoisting is not smart enough to notice that the two calls
+%     are the same.
 :- pred loop2(int::in, int::in, int::in, int::out) is det.
 loop2(N, Inv, Acc0, Acc) :-
     ( N =< 0 ->
Index: tests/hard_coded/loop_inv_test1.m
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/loop_inv_test1.m,v
retrieving revision 1.1
diff -u -d -r1.1 loop_inv_test1.m
--- tests/hard_coded/loop_inv_test1.m	18 Feb 2003 03:38:19 -0000	1.1
+++ tests/hard_coded/loop_inv_test1.m	9 Feb 2004 08:03:52 -0000
@@ -11,6 +11,11 @@
 % This test checks that we do loop invariant hoisting for
 % invariant goals which have no input arguments.
 
+% XXX We do not yet pass this test case, because the loop invariant 
+%     pass has some code which explicitly disables the optimization
+%     if there are no input arguments. (Why???)
+%     This should be very easy to fix.
+
 :- module loop_inv_test1.
 :- interface.
 :- import_module io.
@@ -35,7 +40,7 @@
         io__print("input error"), io__nl
     ).
 
-/* Test that we can do ordinary loop hoisting:
+/* Test that we can do ordinary loop hoisting, for a goal with no inputs.
    p/1 will abort if called twice. */
 :- pred loop1(int::in, int::in, int::out) is det.
 loop1(N, Acc0, Acc) :-
@@ -47,25 +52,21 @@
         loop1(N - 1, Acc1, Acc)
     ).
 
-/* Test that we can do loop hoisting for calls which occur in
-   different branches of an if-then-else: q/1 will abort if called twice. */
+/* Test that we can do ordinary loop hoisting for a goal with no inputs,
+   in the particular case where the invariant goal is an inline foreign_proc.
+   q/1 will abort if called twice. */
 :- pred loop2(int::in, int::in, int::out) is det.
 loop2(N, Acc0, Acc) :-
     ( N =< 0 ->
         Acc = Acc0
     ;
-        ( r(N, 3) ->
-            q(X),
-            Acc1 = Acc0 * 2 + X + 1
-        ;
-            q(X),
-            Acc1 = Acc0 * 2 + X
-        ),
+        q(X),
+        Acc1 = Acc0 + X,
         loop2(N - 1, Acc1, Acc)
     ).
 
-% :- pragma no_inline(p/1).
-% :- pragma no_inline(q/1).
+:- pragma inline(p/1).
+:- pragma no_inline(q/1).
 
 :- pred p(int::out) is det.
 :- pragma foreign_proc("C", p(X::out),
@@ -115,9 +116,5 @@
 
     X = 53;
 ").
-
-:- pragma no_inline(r/2).
-:- pred r(int::in, int::in) is semidet.
-r(X, Y) :- X > Y.
 
 %-----------------------------------------------------------------------------%
Index: tests/hard_coded/loop_inv_test2.m
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/loop_inv_test2.m,v
retrieving revision 1.1
diff -u -d -r1.1 loop_inv_test2.m
--- tests/hard_coded/loop_inv_test2.m	18 Feb 2003 03:38:19 -0000	1.1
+++ tests/hard_coded/loop_inv_test2.m	9 Feb 2004 08:00:59 -0000
@@ -11,6 +11,9 @@
 % This test checks that we do loop invariant hoisting for calls
 % that occur in the condition of an if-then-else in the loop body.
 
+% XXX We do not yet pass this test case, because the current loop
+%     invariant hoisting only hoists det subgoals.
+
 :- module loop_inv_test2.
 :- interface.
 :- import_module io.
@@ -92,10 +95,10 @@
 :- pragma foreign_proc("C", q(X::out),
     [will_not_call_mercury, promise_pure],
 "
-    /* Test that p/1 only gets called once. */
+    /* Test that q/1 only gets called once. */
     static int num_calls = 0;
     if (num_calls++) { 
-        MR_fatal_error(""loop_inv failed -- p/1 called twice"");
+        MR_fatal_error(""loop_inv failed -- q/1 called twice"");
     }
 
     X = 42;
@@ -103,7 +106,7 @@
 :- pragma foreign_proc("C#", q(X::out),
     [will_not_call_mercury, promise_pure],
 "
-    /* Test that p/1 only gets called once. */
+    /* Test that q/1 only gets called once. */
     static int num_calls = 0;
     if (num_calls++) { 
         mercury.runtime.Errors.fatal_error(

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------



More information about the reviews mailing list