[m-rev.] diff: quantification speed improvement

[Zoltan Somogyi]

compiler/quantification.m:
	Union the sets of variables in the arms of a disjunction or switch
	using a balanced merge. This improves compilation speed on Doug
	Auclair's training_cars_full.m test case by 0.8%.

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/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/src/atomic_ops/sysdeps/gcc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/hpc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/ibmc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/icc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/msftc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/sunc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/tests
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing boehm_gc/windows-untested
cvs diff: Diffing boehm_gc/windows-untested/vc60
cvs diff: Diffing boehm_gc/windows-untested/vc70
cvs diff: Diffing boehm_gc/windows-untested/vc71
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/quantification.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/quantification.m,v
retrieving revision 1.116
diff -u -b -r1.116 quantification.m
--- compiler/quantification.m	12 Jun 2007 07:21:25 -0000	1.116
+++ compiler/quantification.m	29 Jun 2007 00:37:44 -0000
@@ -408,17 +408,23 @@
 
 implicitly_quantify_goal_quant_info_2(Expr0, Expr, _, !Info) :-
     Expr0 = disj(Goals0),
-    implicitly_quantify_disj(Goals0, Goals, !Info),
+    NonLocalVarSets0 = [],
+    implicitly_quantify_disj(Goals0, Goals, !Info,
+        NonLocalVarSets0, NonLocalVarSets),
+    union_list(NonLocalVarSets, NonLocalVars),
+    set_nonlocals(NonLocalVars, !Info),
     Expr = disj(Goals).
 
 implicitly_quantify_goal_quant_info_2(Expr0, Expr, _, !Info) :-
     Expr0 = switch(Var, Det, Cases0),
-    implicitly_quantify_cases(Cases0, Cases, !Info),
+    NonLocalVarSets0 = [],
+    implicitly_quantify_cases(Cases0, Cases, !Info,
+        NonLocalVarSets0, NonLocalVarSets),
     % The switch variable is guaranteed to be nonlocal to the switch, since
     % it has to be bound elsewhere, so we put it in the nonlocals here.
-    get_nonlocals(!.Info, NonLocals0),
-    insert(NonLocals0, Var, NonLocals),
-    set_nonlocals(NonLocals, !Info),
+    union_list(NonLocalVarSets, NonLocalVars0),
+    insert(NonLocalVars0, Var, NonLocalVars),
+    set_nonlocals(NonLocalVars, !Info),
     Expr = switch(Var, Det, Cases).
 
 implicitly_quantify_goal_quant_info_2(Expr0, Expr, _, !Info) :-
@@ -840,33 +846,28 @@
     set_nonlocals(NonLocalVars, !Info).
 
 :- pred implicitly_quantify_disj(list(hlds_goal)::in, list(hlds_goal)::out,
-    quant_info::in, quant_info::out) is det.
+    quant_info::in, quant_info::out,
+    list(set_of_var)::in, list(set_of_var)::out) is det.
 
-implicitly_quantify_disj([], [], !Info) :-
-    NonLocalVars = init,
-    set_nonlocals(NonLocalVars, !Info).
-implicitly_quantify_disj([Goal0 | Goals0], [Goal | Goals], !Info) :-
+implicitly_quantify_disj([], [], !Info, !NonLocalVarSets).
+implicitly_quantify_disj([Goal0 | Goals0], [Goal | Goals], !Info,
+        !NonLocalVarSets) :-
     implicitly_quantify_goal_quant_info(Goal0, Goal, !Info),
-    get_nonlocals(!.Info, NonLocalVars0),
-    implicitly_quantify_disj(Goals0, Goals, !Info),
-    get_nonlocals(!.Info, NonLocalVars1),
-    union(NonLocalVars0, NonLocalVars1, NonLocalVars),
-    set_nonlocals(NonLocalVars, !Info).
+    get_nonlocals(!.Info, GoalNonLocalVars),
+    !:NonLocalVarSets = [GoalNonLocalVars | !.NonLocalVarSets],
+    implicitly_quantify_disj(Goals0, Goals, !Info, !NonLocalVarSets).
 
 :- pred implicitly_quantify_cases(list(case)::in, list(case)::out,
-    quant_info::in, quant_info::out) is det.
+    quant_info::in, quant_info::out,
+    list(set_of_var)::in, list(set_of_var)::out) is det.
 
-implicitly_quantify_cases([], [], !Info) :-
-    NonLocalVars = init,
-    set_nonlocals(NonLocalVars, !Info).
+implicitly_quantify_cases([], [], !Info, !NonLocalVarSets).
 implicitly_quantify_cases([case(Cons, Goal0) | Cases0],
-        [case(Cons, Goal) | Cases], !Info) :-
+        [case(Cons, Goal) | Cases], !Info, !NonLocalVarSets) :-
     implicitly_quantify_goal_quant_info(Goal0, Goal, !Info),
-    get_nonlocals(!.Info, NonLocalVars0),
-    implicitly_quantify_cases(Cases0, Cases, !Info),
-    get_nonlocals(!.Info, NonLocalVars1),
-    union(NonLocalVars0, NonLocalVars1, NonLocalVars),
-    set_nonlocals(NonLocalVars, !Info).
+    get_nonlocals(!.Info, GoalNonLocalVars),
+    !:NonLocalVarSets = [GoalNonLocalVars | !.NonLocalVarSets],
+    implicitly_quantify_cases(Cases0, Cases, !Info, !NonLocalVarSets).
 
 %-----------------------------------------------------------------------------%
 
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/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/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/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_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/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
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/c_interface/standalone_c
cvs diff: Diffing samples/diff
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 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
--------------------------------------------------------------------------