[m-rev.] diff: more structure reuse bugs
Peter Wang
novalazy at gmail.com
Mon May 19 11:03:08 AEST 2008
Branches: main
Fix four bugs with structure reuse.
compiler/structure_reuse.direct.detect_garbage.m:
When verifying that the variable on the LHS of a deconstruction is
dead, the computed set of live data to check against was too small, in
the same way as for the verification of indirect reuse calls. The fix
is to use the same code as in the indirect reuse analysis to perform
the check.
compiler/structure_reuse.versions.m:
Although we discovered unconditional reuse opportunities in
construction unifications, we forgot to actually update the
how_to_construct field in those constructions to tell the code
generator to implement that reuse. Fix that.
When a procedure has both conditional and unconditional reuse
opportunities, we forgot to take advantage of the unconditional reuse
opportunities in the original procedure (not the reuse version of the
procedure). Fix that.
Don't process the bodies of imported procedures to implement structure
reuse but *do* add stubs to mirror the reuse versions of procedures
defined in other modules so that those procedures can be called.
tests/hard_coded/Mercury.options:
tests/hard_coded/Mmakefile:
tests/hard_coded/uncond_reuse.exp:
tests/hard_coded/uncond_reuse.exp2:
tests/hard_coded/uncond_reuse.m:
tests/hard_coded/uncond_reuse_bad.exp:
tests/hard_coded/uncond_reuse_bad.m:
Add test cases.
Btw, it turns out that structure reuse is really unusable with the old
intermodule optimisation system. When creating an .opt file we may derive
one set of reuse conditions for a procedure P. When generating the .c file,
the extra information from other .opt files may allows us to find more reuse
opportunities, with a harsher set of reuse conditions. These conditions
would be written to the .trans_opt file, but there is no guarantee that an
importing module reads both the .opt and .trans_opt file, so a caller might
call the reuse version of P but not satisfy its true reuse conditions.
Index: compiler/structure_reuse.direct.detect_garbage.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/structure_reuse.direct.detect_garbage.m,v
retrieving revision 1.16
diff -u -r1.16 structure_reuse.direct.detect_garbage.m
--- compiler/structure_reuse.direct.detect_garbage.m 9 May 2008 05:45:11 -0000 1.16
+++ compiler/structure_reuse.direct.detect_garbage.m 16 May 2008 04:44:21 -0000
@@ -36,6 +36,7 @@
:- import_module libs.compiler_util.
:- import_module parse_tree.prog_data.
:- import_module transform_hlds.ctgc.datastruct.
+:- import_module transform_hlds.ctgc.livedata.
:- import_module bool.
:- import_module io.
@@ -237,13 +238,7 @@
\+ sharing_as_is_top(Sharing),
% Check the live set of data structures at this program point.
- set.union(LFU, LBU, LU),
- LU_data = set.to_sorted_list(set.map(datastruct_init, LU)),
- LiveData = list.condense(
- list.map(
- extend_datastruct(ModuleInfo, ProcInfo, Sharing),
- LU_data)),
- \+ var_is_live(Var, LiveData)
+ var_not_live(ModuleInfo, ProcInfo, GoalInfo, Sharing, Var)
->
% If all the above conditions are met, then the top
% cell data structure based on Var is dead right after
@@ -267,10 +262,21 @@
"complicated_unify/3 encountered.")
).
-:- pred var_is_live(prog_var::in, list(datastruct)::in) is semidet.
+:- pred var_not_live(module_info::in, proc_info::in, hlds_goal_info::in,
+ sharing_as::in, prog_var::in) is semidet.
-var_is_live(Var, LiveData) :-
- list.member(datastruct_init(Var), LiveData).
+var_not_live(ModuleInfo, ProcInfo, GoalInfo, Sharing, Var) :-
+ LiveData = livedata_init_at_goal(ModuleInfo, ProcInfo, GoalInfo, Sharing),
+ nodes_are_not_live(ModuleInfo, ProcInfo, [datastruct_init(Var)], LiveData,
+ NotLive),
+ (
+ NotLive = nodes_are_live([])
+ ;
+ ( NotLive = nodes_all_live
+ ; NotLive = nodes_are_live([_ | _])
+ ),
+ fail
+ ).
%-----------------------------------------------------------------------------%
Index: compiler/structure_reuse.versions.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/structure_reuse.versions.m,v
retrieving revision 1.14
diff -u -r1.14 structure_reuse.versions.m
--- compiler/structure_reuse.versions.m 7 May 2008 05:05:52 -0000 1.14
+++ compiler/structure_reuse.versions.m 16 May 2008 04:44:22 -0000
@@ -95,41 +95,44 @@
% to correctly update the reuse annotations.
%
create_reuse_procedures(ReuseTable, !ModuleInfo, !IO):-
- AllPPIds = map.keys(ReuseTable),
+ map.foldl2(divide_reuse_procs, ReuseTable, [], CondPPIds, [], UncondPPIds),
- % Ignore reuse table entries for imported procedures.
- DefinedHere = (pred(PPId::in) is semidet :-
- PPId = proc(PredId, _),
- module_info_pred_info(!.ModuleInfo, PredId, PredInfo),
- pred_info_get_import_status(PredInfo, Status),
- status_defined_in_this_module(Status) = yes
- ),
- list.filter(DefinedHere, AllPPIds, PPIds),
-
- CondPPIds = list.filter(has_conditional_reuse(ReuseTable), PPIds),
- UncondPPIds = list.filter(has_unconditional_reuse(ReuseTable), PPIds),
-
- % Create all the duplicates:
+ % Create duplicates of the procedures which have conditional reuse.
list.map_foldl(create_fresh_pred_proc_info_copy,
CondPPIds, ReuseCondPPIds, !ModuleInfo),
- % Process all the goals to update the reuse annotations:
+ % Process all the goals to update the reuse annotations. In the reuse
+ % versions of procedures we can take advantage of potential reuse
+ % opportunities.
module_info_get_structure_reuse_map(!.ModuleInfo, ReuseMap),
- ReusePPIds = ReuseCondPPIds ++ UncondPPIds,
- list.foldl2(process_proc(ReuseMap), ReusePPIds, !ModuleInfo, !IO).
+ list.foldl2(process_proc(convert_potential_reuse, ReuseMap),
+ ReuseCondPPIds, !ModuleInfo, !IO),
-:- pred has_conditional_reuse(reuse_as_table::in, pred_proc_id::in) is semidet.
+ % In the original procedures, only the unconditional reuse opportunities
+ % can be taken.
+ list.foldl2(process_proc(leave_potential_reuse, ReuseMap),
+ CondPPIds, !ModuleInfo, !IO),
+ list.foldl2(process_proc(leave_potential_reuse, ReuseMap),
+ UncondPPIds, !ModuleInfo, !IO).
-has_conditional_reuse(ReuseTable, PPId) :-
- reuse_as_table_search(PPId, ReuseTable, reuse_as_and_status(ReuseAs, _)),
- reuse_as_conditional_reuses(ReuseAs).
-
-:- pred has_unconditional_reuse(reuse_as_table::in, pred_proc_id::in)
- is semidet.
-
-has_unconditional_reuse(ReuseTable, PPId) :-
- reuse_as_table_search(PPId, ReuseTable, reuse_as_and_status(ReuseAs, _)),
- reuse_as_all_unconditional_reuses(ReuseAs).
+ % Separate procedures in the reuse table into those with some conditional
+ % reuse opportunities, and those with only unconditional reuse.
+ %
+:- pred divide_reuse_procs(pred_proc_id::in, reuse_as_and_status::in,
+ list(pred_proc_id)::in, list(pred_proc_id)::out,
+ list(pred_proc_id)::in, list(pred_proc_id)::out) is det.
+
+divide_reuse_procs(PPId, ReuseAs_Status, !CondPPIds, !UncondPPIds) :-
+ ReuseAs_Status = reuse_as_and_status(ReuseAs, _),
+ ( reuse_as_conditional_reuses(ReuseAs) ->
+ !:CondPPIds = [PPId | !.CondPPIds]
+ ; reuse_as_all_unconditional_reuses(ReuseAs) ->
+ !:UncondPPIds = [PPId | !.UncondPPIds]
+ ; reuse_as_no_reuses(ReuseAs) ->
+ true
+ ;
+ unexpected(this_file, "divide_reuse_procs")
+ ).
%------------------------------------------------------------------------------%
@@ -191,43 +194,54 @@
%------------------------------------------------------------------------------%
+:- type convert_potential_reuse
+ ---> convert_potential_reuse
+ ; leave_potential_reuse.
+
% Process the goal of the procedure with the given pred_proc_id so that
% all potential reuses are replaced by real reuses, and all calls to
% procedures that have a reuse version are replaced by calls to their
% reuse version (if of course, that is in accordance with the reuse
% annotations).
%
-:- pred process_proc(structure_reuse_map::in,
+:- pred process_proc(convert_potential_reuse::in, structure_reuse_map::in,
pred_proc_id::in, module_info::in, module_info::out,
io::di, io::uo) is det.
-process_proc(ReuseMap, PPId, !ModuleInfo, !IO) :-
+process_proc(ConvertPotentialReuse, ReuseMap, PPId, !ModuleInfo, !IO) :-
write_proc_progress_message("(reuse version) ", PPId, !.ModuleInfo, !IO),
some [!ProcInfo] (
module_info_pred_proc_info(!.ModuleInfo, PPId, PredInfo0, !:ProcInfo),
- proc_info_get_goal(!.ProcInfo, Goal0),
- process_goal(ReuseMap, Goal0, Goal, !IO),
- proc_info_set_goal(Goal, !ProcInfo),
-
- % A dead variable needs to appear in the non-local set of the
- % construction unification in which its space is reused, so we
- % requantify. Then we recompute instmap deltas with the updated
- % non-local sets.
- requantify_proc(!ProcInfo),
- recompute_instmap_delta_proc(do_not_recompute_atomic_instmap_deltas,
- !ProcInfo, !ModuleInfo),
- module_info_set_pred_proc_info(PPId, PredInfo0, !.ProcInfo,
- !ModuleInfo)
+ pred_info_get_import_status(PredInfo0, ImportStatus),
+ ( ImportStatus = status_imported(_) ->
+ % Don't process the bodies of imported predicates.
+ true
+ ;
+ proc_info_get_goal(!.ProcInfo, Goal0),
+ process_goal(ConvertPotentialReuse, ReuseMap, Goal0, Goal, !IO),
+ proc_info_set_goal(Goal, !ProcInfo),
+
+ % A dead variable needs to appear in the non-local set of the
+ % construction unification in which its space is reused, so we
+ % requantify. Then we recompute instmap deltas with the updated
+ % non-local sets.
+ requantify_proc(!ProcInfo),
+ recompute_instmap_delta_proc(do_not_recompute_atomic_instmap_deltas,
+ !ProcInfo, !ModuleInfo),
+ module_info_set_pred_proc_info(PPId, PredInfo0, !.ProcInfo,
+ !ModuleInfo)
+ )
).
-:- pred process_goal(structure_reuse_map::in, hlds_goal::in, hlds_goal::out,
- io::di, io::uo) is det.
+:- pred process_goal(convert_potential_reuse::in, structure_reuse_map::in,
+ hlds_goal::in, hlds_goal::out, io::di, io::uo) is det.
-process_goal(ReuseMap, !Goal, !IO) :-
+process_goal(ConvertPotentialReuse, ReuseMap, !Goal, !IO) :-
!.Goal = hlds_goal(GoalExpr0, GoalInfo0),
(
GoalExpr0 = conj(ConjType, Goals0),
- list.map_foldl(process_goal(ReuseMap), Goals0, Goals, !IO),
+ list.map_foldl(process_goal(ConvertPotentialReuse, ReuseMap),
+ Goals0, Goals, !IO),
GoalExpr = conj(ConjType, Goals),
!:Goal = hlds_goal(GoalExpr, GoalInfo0)
;
@@ -250,7 +264,8 @@
Args, BI, UC, ReuseCalleePredName),
!:Goal = hlds_goal(GoalExpr, GoalInfo0)
;
- ReuseDescription0 = potential_reuse(reuse_call(CondDescr))
+ ReuseDescription0 = potential_reuse(reuse_call(CondDescr)),
+ ConvertPotentialReuse = convert_potential_reuse
->
% Replace the call to the reuse version, and change the
% potential reuse annotation to a real annotation.
@@ -271,25 +286,35 @@
GoalExpr0 = unify(_, _, _, Unification0, _),
ReuseDescription0 = goal_info_get_reuse(GoalInfo0),
(
- ReuseDescription0 = potential_reuse(Descr)
- ->
+ (
+ ReuseDescription0 = reuse(Descr)
+ ;
+ ReuseDescription0 = potential_reuse(Descr),
+ ConvertPotentialReuse = convert_potential_reuse
+ ),
ReuseDescription = reuse(Descr),
- unification_set_reuse(Descr, Unification0,
- Unification),
+ unification_set_reuse(Descr, Unification0, Unification),
GoalExpr = GoalExpr0 ^ unify_kind := Unification,
goal_info_set_reuse(ReuseDescription, GoalInfo0, GoalInfo),
!:Goal = hlds_goal(GoalExpr, GoalInfo)
;
- true
+ ReuseDescription0 = potential_reuse(_),
+ ConvertPotentialReuse = leave_potential_reuse
+ ;
+ ReuseDescription0 = no_reuse_info
+ ;
+ ReuseDescription0 = missed_reuse(_)
)
;
GoalExpr0 = disj(Goals0),
- list.map_foldl(process_goal(ReuseMap), Goals0, Goals, !IO),
+ list.map_foldl(process_goal(ConvertPotentialReuse, ReuseMap),
+ Goals0, Goals, !IO),
GoalExpr = disj(Goals),
!:Goal = hlds_goal(GoalExpr, GoalInfo0)
;
GoalExpr0 = switch(A, B, Cases0),
- list.map_foldl(process_case(ReuseMap), Cases0, Cases, !IO),
+ list.map_foldl(process_case(ConvertPotentialReuse, ReuseMap),
+ Cases0, Cases, !IO),
GoalExpr = switch(A, B, Cases),
!:Goal = hlds_goal(GoalExpr, GoalInfo0)
;
@@ -297,14 +322,16 @@
GoalExpr0 = negation(_Goal)
;
GoalExpr0 = scope(A, SubGoal0),
- process_goal(ReuseMap, SubGoal0, SubGoal, !IO),
+ process_goal(ConvertPotentialReuse, ReuseMap, SubGoal0, SubGoal, !IO),
GoalExpr = scope(A, SubGoal),
!:Goal = hlds_goal(GoalExpr, GoalInfo0)
;
GoalExpr0 = if_then_else(A, IfGoal0, ThenGoal0, ElseGoal0),
- process_goal(ReuseMap, IfGoal0, IfGoal, !IO),
- process_goal(ReuseMap, ThenGoal0, ThenGoal, !IO),
- process_goal(ReuseMap, ElseGoal0, ElseGoal, !IO),
+ process_goal(ConvertPotentialReuse, ReuseMap, IfGoal0, IfGoal, !IO),
+ process_goal(ConvertPotentialReuse, ReuseMap, ThenGoal0, ThenGoal,
+ !IO),
+ process_goal(ConvertPotentialReuse, ReuseMap, ElseGoal0, ElseGoal,
+ !IO),
GoalExpr = if_then_else(A, IfGoal, ThenGoal, ElseGoal),
!:Goal = hlds_goal(GoalExpr, GoalInfo0)
;
@@ -347,13 +374,13 @@
ReusePredName = PredName
).
-:- pred process_case(structure_reuse_map::in, case::in, case::out,
- io::di, io::uo) is det.
+:- pred process_case(convert_potential_reuse::in, structure_reuse_map::in,
+ case::in, case::out, io::di, io::uo) is det.
-process_case(ReuseMap, !Case, !IO) :-
- !.Case = case(MainConsId, OtherConsIds, Goal0),
- process_goal(ReuseMap, Goal0, Goal, !IO),
- !:Case = case(MainConsId, OtherConsIds, Goal).
+process_case(ConvertPotentialReuse, ReuseMap, Case0, Case, !IO) :-
+ Case0 = case(MainConsId, OtherConsIds, Goal0),
+ process_goal(ConvertPotentialReuse, ReuseMap, Goal0, Goal, !IO),
+ Case = case(MainConsId, OtherConsIds, Goal).
%------------------------------------------------------------------------------%
Index: tests/hard_coded/Mercury.options
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mercury.options,v
retrieving revision 1.32
diff -u -r1.32 Mercury.options
--- tests/hard_coded/Mercury.options 23 Apr 2008 05:16:50 -0000 1.32
+++ tests/hard_coded/Mercury.options 16 May 2008 04:44:23 -0000
@@ -37,6 +37,8 @@
MCFLAGS-intermod_type_qual2 = --intermodule-optimization
MCFLAGS-intermod_multimode = --intermodule-optimization
MCFLAGS-intermod_multimode_main = --intermodule-optimization
+MCFLAGS-uncond_reuse = --ctgc
+MCFLAGS-uncond_reuse_bad = --ctgc
# We disable intermodule-optimization here because it isn't compatible with
# intermodule-analysis.
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.349
diff -u -r1.349 Mmakefile
--- tests/hard_coded/Mmakefile 28 Apr 2008 00:50:55 -0000 1.349
+++ tests/hard_coded/Mmakefile 16 May 2008 04:44:23 -0000
@@ -249,6 +249,8 @@
type_spec_modes \
type_to_term_bug \
uc_export_enum \
+ uncond_reuse \
+ uncond_reuse_bad \
unicode_test \
unify_existq_cons \
unify_expression \
Index: tests/hard_coded/uncond_reuse.exp
===================================================================
RCS file: tests/hard_coded/uncond_reuse.exp
diff -N tests/hard_coded/uncond_reuse.exp
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/uncond_reuse.exp 16 May 2008 04:44:25 -0000
@@ -0,0 +1 @@
+same address (good)
Index: tests/hard_coded/uncond_reuse.exp2
===================================================================
RCS file: tests/hard_coded/uncond_reuse.exp2
diff -N tests/hard_coded/uncond_reuse.exp2
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/uncond_reuse.exp2 16 May 2008 04:44:25 -0000
@@ -0,0 +1 @@
+grade probably doesn't support reuse
Index: tests/hard_coded/uncond_reuse.m
===================================================================
RCS file: tests/hard_coded/uncond_reuse.m
diff -N tests/hard_coded/uncond_reuse.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/uncond_reuse.m 16 May 2008 04:44:25 -0000
@@ -0,0 +1,62 @@
+% Test that an unconditional reuse opportunity is actually taken.
+
+:- module uncond_reuse.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is cc_multi.
+
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module int.
+:- import_module string.
+
+%-----------------------------------------------------------------------------%
+
+:- type f
+ ---> f(int, int).
+
+main(!IO) :-
+ copy(f(1, 2), F0),
+ addr(F0, Addr0),
+ F0 = f(A, B),
+ F = f(A + 1, B + 1), % unconditional reuse here
+ addr(F, Addr),
+
+ ( capable_grade($grade) ->
+ ( Addr0 = Addr ->
+ io.write_string("same address (good)\n", !IO)
+ ;
+ io.write_string("different addresses (bad)\n", !IO)
+ )
+ ;
+ io.write_string("grade probably doesn't support reuse\n", !IO)
+ ).
+
+% Only C grades for now.
+:- pred capable_grade(string::in) is semidet.
+
+capable_grade(Grade) :-
+ string.prefix(Grade, Prefix),
+ ( Prefix = "none"
+ ; Prefix = "reg"
+ ; Prefix = "jump"
+ ; Prefix = "asm"
+ ; Prefix = "fast"
+ ; Prefix = "hl"
+ ).
+
+:- pred addr(T::in, int::out) is cc_multi.
+
+:- pragma foreign_proc("C",
+ addr(T::in, Addr::out),
+ [will_not_call_mercury, promise_pure, thread_safe, no_sharing],
+"
+ Addr = (MR_Word) T;
+").
+
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=8 sw=4 et wm=0 tw=0
Index: tests/hard_coded/uncond_reuse_bad.exp
===================================================================
RCS file: tests/hard_coded/uncond_reuse_bad.exp
diff -N tests/hard_coded/uncond_reuse_bad.exp
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/uncond_reuse_bad.exp 16 May 2008 04:44:25 -0000
@@ -0,0 +1,3 @@
+BBox before: bb(point(-2.25, -5.0, -1.5), point(3.3, 3.6, 9.3))
+BBox after: bb(point(-2.25, -5.0, -1.5), point(3.3, 3.6, 9.3))
+something(bb(point(-2.25, -5.0, -1.5), point(3.3, 3.6, 9.3)), -2.25, 100)
Index: tests/hard_coded/uncond_reuse_bad.m
===================================================================
RCS file: tests/hard_coded/uncond_reuse_bad.m
diff -N tests/hard_coded/uncond_reuse_bad.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/uncond_reuse_bad.m 16 May 2008 04:44:25 -0000
@@ -0,0 +1,58 @@
+% Regression test for bad unconditional direct structure reuse.
+
+:- module uncond_reuse_bad.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module float.
+
+:- type bounding_box
+ ---> bb(vector, vector).
+
+:- type vector
+ ---> point(float, float, float).
+
+:- type something % == sizeof(vector)
+ ---> something(
+ bounding_box,
+ float,
+ int
+ ).
+
+main(!IO) :-
+ BBox = make_bb,
+ % Created in here for unconditional direct reuse.
+
+ BBox = bb(Min, _Max),
+ Min = point(X1, _Y1, _Z1),
+
+ io.write_string("BBox before: ", !IO),
+ io.write(BBox, !IO),
+ io.nl(!IO),
+
+ Something = something(BBox, X1, 100),
+ % Bad reuse of Min occurs here.
+
+ io.write_string("BBox after: ", !IO),
+ io.write(BBox, !IO),
+ io.nl(!IO),
+
+ io.write(Something, !IO),
+ io.nl(!IO).
+
+:- func make_bb = bounding_box.
+:- pragma no_inline(make_bb/0).
+
+make_bb = BBox :-
+ Orig = bb(point(-2.25, -5.0, -1.5), point(3.3, 3.6, 9.3)),
+ copy(Orig, BBox).
+
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=8 sw=4 et wm=0 tw=0
--------------------------------------------------------------------------
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