[m-rev.] diff: fix performance problem in inst_match.m

[Zoltan Somogyi]

Fix a performance problem in mode analysis, which showed up especially badly
when redoing mode checking after common subexpression elimination on Peter
Ross's mas_objects.data.m test file.

compiler/inst_match.m:
	Use a logarithmic instead of linear complexity algorithm for checking
	whether we have expanded a given inst before.
	
library/set_tree234.m:
	Fix the underlying problem, which was that using set_tree234.member
	to *check* membership was linear in the number of set elements, due
	to the absence of an in,in mode.

Zoltan.

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/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/inst_match.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/inst_match.m,v
retrieving revision 1.75
diff -u -b -r1.75 inst_match.m
--- compiler/inst_match.m	31 Jul 2006 08:31:42 -0000	1.75
+++ compiler/inst_match.m	1 Aug 2006 03:02:17 -0000
@@ -377,7 +377,7 @@
 :- pragma inline(expansion_member/2).
 
 expansion_member(E, S) :-
-    set_tree234.member(S, E).
+    set_tree234.is_member(S, E) = yes.
 
 :- pred expansion_insert(inst_match_inputs::in,
     expansions::in, expansions::out) is det.
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing debian/patches
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
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/concurrency
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/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_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/logged_output
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/moose/tests
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/odbc
cvs diff: Diffing extras/posix
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/stream
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/set_tree234.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_tree234.m,v
retrieving revision 1.7
diff -u -b -r1.7 set_tree234.m
--- library/set_tree234.m	19 Apr 2006 05:17:56 -0000	1.7
+++ library/set_tree234.m	1 Aug 2006 03:02:08 -0000
@@ -42,7 +42,9 @@
 
     % `set_tree234.member(X, Set)' is true iff `X' is a member of `Set'.
     %
-:- pred set_tree234.member(set_tree234(T)::in, T::out) is nondet.
+:- pred set_tree234.member(set_tree234(T), T).
+:- mode set_tree234.member(in, in) is semidet.
+:- mode set_tree234.member(in, out) is nondet.
 
     % `set_tree234.is_member(Set, X, Result)' returns
     % `Result = yes' iff `X' is a member of `Set'.
@@ -293,28 +295,37 @@
 
 set_tree234.empty(empty).
 
-set_tree234.member(empty, _) :- fail.
-set_tree234.member(two(E0, T0, T1), E) :-
+:- pragma promise_equivalent_clauses(set_tree234.member/2).
+
+set_tree234.member(Set::in, Element::out) :-
+    set_tree234.all_members(Set, Element).
+set_tree234.member(Set::in, Element::in) :-
+    set_tree234.is_member(Set, Element) = yes.
+
+:- pred set_tree234.all_members(set_tree234(T)::in, T::out) is nondet.
+
+set_tree234.all_members(empty, _) :- fail.
+set_tree234.all_members(two(E0, T0, T1), E) :-
     (
         E = E0
     ;
-        set_tree234.member(T0, E)
+        set_tree234.all_members(T0, E)
     ;
-        set_tree234.member(T1, E)
+        set_tree234.all_members(T1, E)
     ).
-set_tree234.member(three(E0, E1, T0, T1, T2), E) :-
+set_tree234.all_members(three(E0, E1, T0, T1, T2), E) :-
     (
         E = E0
     ;
         E = E1
     ;
-        set_tree234.member(T0, E)
+        set_tree234.all_members(T0, E)
     ;
-        set_tree234.member(T1, E)
+        set_tree234.all_members(T1, E)
     ;
-        set_tree234.member(T2, E)
+        set_tree234.all_members(T2, E)
     ).
-set_tree234.member(four(E0, E1, E2, T0, T1, T2, T3), E) :-
+set_tree234.all_members(four(E0, E1, E2, T0, T1, T2, T3), E) :-
     (
         E = E0
     ;
@@ -322,13 +333,13 @@
     ;
         E = E2
     ;
-        set_tree234.member(T0, E)
+        set_tree234.all_members(T0, E)
     ;
-        set_tree234.member(T1, E)
+        set_tree234.all_members(T1, E)
     ;
-        set_tree234.member(T2, E)
+        set_tree234.all_members(T2, E)
     ;
-        set_tree234.member(T3, E)
+        set_tree234.all_members(T3, E)
     ).
 
 set_tree234.is_member(T, E, R) :-
cvs diff: Diffing mdbcomp
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/diff
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
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 tests
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/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
--------------------------------------------------------------------------