[m-rev.] diff: speed up llds backend using set_tree234

Zoltan Somogyi zs at unimelb.edu.au
Tue Apr 24 14:26:38 AEST 2012


compiler/frameopt.m:
compiler/jumpopt.m:
compiler/labelopt.m:
compiler/optimize.m:
	Speed up the compiler by 0.8% when generating low level C code
	by using 234 trees instead of lists to store sets of labels.

Zoltan.

cvs diff: Diffing .
Index: frameopt.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/frameopt.m,v
retrieving revision 1.127
diff -u -b -r1.127 frameopt.m
--- frameopt.m	3 Jan 2012 11:04:47 -0000	1.127
+++ frameopt.m	24 Apr 2012 03:57:39 -0000
@@ -99,7 +99,7 @@
 :- import_module bool.
 :- import_module counter.
 :- import_module list.
-:- import_module set.
+:- import_module set_tree234.
 
 %-----------------------------------------------------------------------------%
 
@@ -145,7 +145,7 @@
     % structures, while MayAlterRtti should say whether we are allowed to
     % perform optimizations that may interfere with RTTI.
     %
-:- pred frameopt_keep_nondet_frame(proc_label::in, set(label)::in,
+:- pred frameopt_keep_nondet_frame(proc_label::in, set_tree234(label)::in,
     counter::in, counter::out, list(instruction)::in, list(instruction)::out,
     bool::out) is det.
 
@@ -328,7 +328,7 @@
     find_succeed_labels(Instrs, !SuccMap).
 
 :- pred keep_nondet_frame(list(instruction)::in, list(instruction)::out,
-    proc_label::in, label::in, instr::in, tailmap::in, set(label)::in,
+    proc_label::in, label::in, instr::in, tailmap::in, set_tree234(label)::in,
     bool::in, bool::out) is det.
 
 keep_nondet_frame([], [], _, _, _, _, _, !Changed).
@@ -344,7 +344,7 @@
         map.search(SuccMap, RetLabel, BetweenIncl),
         BetweenIncl = [llds_instr(livevals(_), _), llds_instr(goto(_), _)],
         PrevInstr = livevals(Livevals),
-        not set.member(RetLabel, LayoutLabels)
+        not set_tree234.member(RetLabel, LayoutLabels)
     ->
         keep_nondet_frame(Instrs0, Instrs1, ProcLabel, KeepFrameLabel,
             Uinstr0, SuccMap, LayoutLabels, !.Changed, _),
Index: jumpopt.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/jumpopt.m,v
retrieving revision 1.122
diff -u -b -r1.122 jumpopt.m
--- jumpopt.m	17 Oct 2011 04:31:29 -0000	1.122
+++ jumpopt.m	24 Apr 2012 03:58:08 -0000
@@ -22,7 +22,7 @@
 :- import_module bool.
 :- import_module counter.
 :- import_module list.
-:- import_module set.
+:- import_module set_tree234.
 
 %-----------------------------------------------------------------------------%
 
@@ -53,7 +53,7 @@
     % Mod will say whether the instruction sequence was modified
     % by the optimization.
     %
-:- pred optimize_jumps_in_proc(set(label)::in, may_alter_rtti::in,
+:- pred optimize_jumps_in_proc(set_tree234(label)::in, may_alter_rtti::in,
     proc_label::in, bool::in, bool::in, bool::in, bool::in,
     counter::in, counter::out, list(instruction)::in, list(instruction)::out,
     bool::out) is det.
@@ -251,7 +251,7 @@
                 joi_sdproc_map      :: tailmap,
                 joi_fork_map        :: tailmap,
                 joi_succ_map        :: tailmap,
-                joi_layout_labels   :: set(label),
+                joi_layout_labels   :: set_tree234(label),
                 joi_full_jump_opt   :: bool,
                 joi_may_alter_rtti  :: may_alter_rtti
             ).
@@ -501,7 +501,7 @@
                 JumpOptInfo ^ joi_may_alter_rtti = must_not_alter_rtti
             ;
                 LayoutLabels = JumpOptInfo ^ joi_layout_labels,
-                set.member(RetLabel, LayoutLabels)
+                set_tree234.member(RetLabel, LayoutLabels)
             )
         ->
             % We cannot optimize the call. Test for this once, here, instead
@@ -762,7 +762,7 @@
             opt_util.skip_comments(Instrs0, Instrs1),
             Instrs1 = [Instr1 | Instrs2],
             ( Instr1 = llds_instr(label(ElimLabel), _) ->
-                not set.member(ElimLabel, LayoutLabels),
+                not set_tree234.member(ElimLabel, LayoutLabels),
                 opt_util.skip_comments(Instrs2, Instrs3),
                 Instrs3 = [GotoInstr | AfterGoto],
                 HaveLabel = yes
Index: labelopt.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/labelopt.m,v
retrieving revision 1.39
diff -u -b -r1.39 labelopt.m
--- labelopt.m	23 May 2011 05:08:04 -0000	1.39
+++ labelopt.m	24 Apr 2012 03:52:13 -0000
@@ -20,7 +20,7 @@
 
 :- import_module bool.
 :- import_module list.
-:- import_module set.
+:- import_module set_tree234.
 
 %-----------------------------------------------------------------------------%
 
@@ -29,15 +29,15 @@
     % the label branches away, we also remove the instruction block following
     % the label.
     %
-:- pred labelopt_main(bool::in, set(label)::in,
+:- pred labelopt_main(bool::in, set_tree234(label)::in,
     list(instruction)::in, list(instruction)::out, bool::out) is det.
 
     % Build up a set showing which labels are referred to.  The input set is
     % the list of labels referred to from outside the given list of
     % instructions.
     %
-:- pred build_useset(list(instruction)::in, set(label)::in, set(label)::out)
-    is det.
+:- pred build_useset(list(instruction)::in,
+    set_tree234(label)::in, set_tree234(label)::out) is det.
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
@@ -68,7 +68,7 @@
 build_useset([Instr | Instructions], !Useset) :-
     Instr = llds_instr(Uinstr, _Comment),
     opt_util.instr_labels(Uinstr, Labels, _CodeAddresses),
-    set.insert_list(Labels, !Useset),
+    set_tree234.insert_list(Labels, !Useset),
     build_useset(Instructions, !Useset).
 
 %-----------------------------------------------------------------------------%
@@ -85,7 +85,7 @@
     % to handle very long instruction lists.
     %
 :- pred opt_labels_in_instr_list(list(instruction)::in, list(instruction)::out,
-    set(label)::in, bool::out) is det.
+    set_tree234(label)::in, bool::out) is det.
 
 opt_labels_in_instr_list(Instrs0, Instrs, Useset, Mod) :-
     Fallthrough = yes,
@@ -95,7 +95,7 @@
 
 :- pred opt_labels_in_instr_list_2(list(instruction)::in,
     list(instruction)::in, list(instruction)::out,
-    bool::in, bool::out, bool::in, set(label)::in) is det.
+    bool::in, bool::out, bool::in, set_tree234(label)::in) is det.
 
 opt_labels_in_instr_list_2([], !RevInstrs, !Mod, _Fallthrough, _Useset).
 opt_labels_in_instr_list_2([Instr0 | Instrs0], !RevInstrs, !Mod,
@@ -109,7 +109,7 @@
                 ; EntryType = entry_label_local
                 )
             ;
-                set.member(Label, Useset)
+                set_tree234.member(Label, Useset)
             )
         ->
             !:RevInstrs = [Instr0 | !.RevInstrs],
Index: optimize.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/optimize.m,v
retrieving revision 1.72
diff -u -b -r1.72 optimize.m
--- optimize.m	23 May 2011 05:08:08 -0000	1.72
+++ optimize.m	24 Apr 2012 03:55:39 -0000
@@ -63,7 +63,7 @@
 :- import_module map.
 :- import_module maybe.
 :- import_module require.
-:- import_module set.
+:- import_module set_tree234.
 :- import_module string.
 
 %-----------------------------------------------------------------------------%
@@ -102,9 +102,9 @@
             LayoutLabels = list.map(
                 make_internal_label_for_proc_label(ProcLabel),
                 LayoutLabelNums),
-            set.sorted_list_to_set(LayoutLabels, LayoutLabelSet)
+            set_tree234.sorted_list_to_set(LayoutLabels, LayoutLabelSet)
         ;
-            set.init(LayoutLabelSet)
+            LayoutLabelSet = set_tree234.init
         ),
         Statistics = Info ^ lopt_detailed_statistics,
         optimize_initial(Info, LayoutLabelSet, ProcLabel, CodeModel,
@@ -300,9 +300,9 @@
 
 %-----------------------------------------------------------------------------%
 
-:- pred optimize_initial(llds_opt_info::in, set(label)::in, proc_label::in,
-    code_model::in, may_alter_rtti::in, counter::in, counter::out,
-    opt_debug_info::in, opt_debug_info::out,
+:- pred optimize_initial(llds_opt_info::in, set_tree234(label)::in,
+    proc_label::in, code_model::in, may_alter_rtti::in,
+    counter::in, counter::out, opt_debug_info::in, opt_debug_info::out,
     list(instruction)::in, list(instruction)::out) is det.
 
 optimize_initial(Info, LayoutLabelSet, ProcLabel, CodeModel, MayAlterRtti,
@@ -335,7 +335,7 @@
 
 %-----------------------------------------------------------------------------%
 
-:- pred optimize_repeat(llds_opt_info::in, int::in, set(label)::in,
+:- pred optimize_repeat(llds_opt_info::in, int::in, set_tree234(label)::in,
     proc_label::in, may_alter_rtti::in, counter::in, counter::out,
     opt_debug_info::in, opt_debug_info::out,
     list(instruction)::in, list(instruction)::out) is det.
@@ -365,7 +365,7 @@
     % We short-circuit jump sequences before normal peepholing
     % to create more opportunities for use of the tailcall macro.
     %
-:- pred optimize_repeated(llds_opt_info::in, bool::in, set(label)::in,
+:- pred optimize_repeated(llds_opt_info::in, bool::in, set_tree234(label)::in,
     proc_label::in, may_alter_rtti::in, counter::in, counter::out,
     opt_debug_info::in, opt_debug_info::out,
     list(instruction)::in, list(instruction)::out, bool::out) is det.
@@ -471,7 +471,7 @@
         maybe_report_stats(Statistics, !IO)
     ).
 
-:- pred optimize_middle(llds_opt_info::in, bool::in, set(label)::in,
+:- pred optimize_middle(llds_opt_info::in, bool::in, set_tree234(label)::in,
     proc_label::in, code_model::in, may_alter_rtti::in,
     counter::in, counter::out, opt_debug_info::in, opt_debug_info::out,
     list(instruction)::in, list(instruction)::out) is det.
@@ -604,8 +604,8 @@
         UseLocalVars = no
     ).
 
-:- pred optimize_last(llds_opt_info::in, set(label)::in, proc_label::in,
-    counter::in, counter::out, opt_debug_info::in,
+:- pred optimize_last(llds_opt_info::in, set_tree234(label)::in,
+    proc_label::in, counter::in, counter::out, opt_debug_info::in,
     list(instruction)::in, list(instruction)::out) is det.
 
 optimize_last(Info, LayoutLabelSet, ProcLabel, !C, !.OptDebugInfo, !Instrs) :-
cvs diff: Diffing notes
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------



More information about the reviews mailing list