[m-rev.] for review: explicitly free dead cells
Peter Wang
novalazy at gmail.com
Thu Aug 21 15:43:35 AEST 2008
On icfp2000 it's about 3% faster than the ctgc-enabled ray tracer in
hlc.gc. Don't know about the compiler yet.
Zoltan, do you think it will be hard to solve the problem noted in
unify_gen.m?
Branches: main
Add the ability, when structure reuse is enabled, to free dead heap cells
which can't otherwise be reused. This currently only works with the high-level
C backend.
Fix a bug where we might try to reuse static data in MLDS grades. As with the
the LLDS grades, check at run-time that the cell to reuse is within the heap
range.
compiler/options.m:
Add `--structure-reuse-free-cells' option (disabled by default).
compiler/structure_reuse.direct.choose_reuse.m:
Fix a bug which caused the code to mark deconstructions with `can_cgc'
to never be run. Run the code if `--structure-reuse-free-cells'
is enabled.
compiler/ml_unify_gen.m:
Make the code which implements cell reuse generate code like this:
MR_assign_if_in_heap(Lval, Rval);
if (Lval) {
/* assign fields */
} else {
Lval = MR_new_object(...);
}
where `MR_assign_if_in_heap' assigns NULL to Lval if Rval doesn't look
like a dynamically allocated address.
Strip tag bits off the argument to `delete_object' statements.
compiler/mlds.m:
Add an MLDS statement `assign_if_in_heap'.
Change `delete_object' to take an rval argument instead of an lval,
for stripping tag bits.
compiler/mlds_to_c.m:
Generate output for `assign_if_in_heap' and `delete_object'.
compiler/ml_elim_nested.m:
compiler/ml_optimize.m:
compiler/mlds_to_gcc.m:
compiler/mlds_to_il.m:
compiler/mlds_to_java.m:
Conform to MLDS statement changes.
compiler/unify_gen.m:
Add commented out code to generate `free_heap' instructions in LLDS
grades.
runtime/mercury_heap.h:
Make `MR_free_heap' macro test that its argument is the heap range
before calling `GC_FREE', so we don't try to free static data.
Add `MR_assign_if_in_heap'.
diff --git a/compiler/ml_elim_nested.m b/compiler/ml_elim_nested.m
index af37263..b916b1e 100644
--- a/compiler/ml_elim_nested.m
+++ b/compiler/ml_elim_nested.m
@@ -1762,9 +1762,14 @@ fixup_atomic_stmt(Atomic0, Atomic, !Info) :-
fixup_rval(Rval0, Rval, !Info),
Atomic = assign(Lval, Rval)
;
- Atomic0 = delete_object(Lval0),
+ Atomic0 = assign_if_in_heap(Lval0, Rval0),
fixup_lval(Lval0, Lval, !Info),
- Atomic = delete_object(Lval)
+ fixup_rval(Rval0, Rval, !Info),
+ Atomic = assign_if_in_heap(Lval, Rval)
+ ;
+ Atomic0 = delete_object(Rval0),
+ fixup_rval(Rval0, Rval, !Info),
+ Atomic = delete_object(Rval)
;
Atomic0 = new_object(Target0, MaybeTag, HasSecTag, Type, MaybeSize,
MaybeCtorName, Args0, ArgTypes, MayUseAtomic),
diff --git a/compiler/ml_optimize.m b/compiler/ml_optimize.m
index b454dbf..0e8342a 100644
--- a/compiler/ml_optimize.m
+++ b/compiler/ml_optimize.m
@@ -1166,9 +1166,14 @@ eliminate_var_in_atomic_stmt(Stmt0, Stmt, !VarElimInfo) :-
eliminate_var_in_rval(Rval0, Rval, !VarElimInfo),
Stmt = assign(Lval, Rval)
;
- Stmt0 = delete_object(Lval0),
+ Stmt0 = assign_if_in_heap(Lval0, Rval0),
eliminate_var_in_lval(Lval0, Lval, !VarElimInfo),
- Stmt = delete_object(Lval)
+ eliminate_var_in_rval(Rval0, Rval, !VarElimInfo),
+ Stmt = assign_if_in_heap(Lval, Rval)
+ ;
+ Stmt0 = delete_object(Rval0),
+ eliminate_var_in_rval(Rval0, Rval, !VarElimInfo),
+ Stmt = delete_object(Rval)
;
Stmt0 = new_object(Target0, MaybeTag, HasSecTag, Type,
MaybeSize, MaybeCtorName, Args0, ArgTypes, MayUseAtomic),
diff --git a/compiler/ml_unify_gen.m b/compiler/ml_unify_gen.m
index 44552a9..5dc901f 100644
--- a/compiler/ml_unify_gen.m
+++ b/compiler/ml_unify_gen.m
@@ -210,7 +210,9 @@ ml_gen_unification(Unification, CodeModel, Context, Decls, Statements,
% this is safe.
CanCGC = can_cgc,
ml_gen_var(!.Info, Var, VarLval),
- Stmt = ml_stmt_atomic(delete_object(VarLval)),
+ % XXX avoid strip_tag when we know what tag it will have
+ Delete = delete_object(unop(std_unop(strip_tag), lval(VarLval))),
+ Stmt = ml_stmt_atomic(Delete),
CGC_Statements = [statement(Stmt, mlds_make_context(Context)) ]
;
CanCGC = cannot_cgc,
@@ -810,7 +812,10 @@ ml_gen_new_object(MaybeConsId, Tag, HasSecTag, MaybeCtorName, Var,
ml_gen_type(!.Info, Type, MLDS_DestType),
CastVar2Rval = unop(cast(MLDS_DestType), Var2Rval),
- AssignStatement = ml_gen_assign(Var1Lval, CastVar2Rval, Context),
+ MLDS_Context = mlds_make_context(Context),
+ AssignStatement = statement(
+ ml_stmt_atomic(assign_if_in_heap(Var1Lval, CastVar2Rval)),
+ MLDS_Context),
% For each field in the construction unification we need to generate
% an rval. ExtraRvals need to be inserted at the start of the object.
@@ -823,8 +828,23 @@ ml_gen_new_object(MaybeConsId, Tag, HasSecTag, MaybeCtorName, Var,
Context, FieldStatements, TakeAddrInfos, !Info),
ml_gen_field_take_address_assigns(TakeAddrInfos, VarLval, MLDS_Type,
MaybeTag, Context, !.Info, TakeAddrStatements),
- Statements = [AssignStatement | ExtraRvalStatements] ++
- FieldStatements ++ TakeAddrStatements,
+ IfBody = statement(ml_stmt_block([],
+ ExtraRvalStatements ++ FieldStatements ++ TakeAddrStatements),
+ MLDS_Context),
+
+ % If the reassignment isn't possible because the target is statically
+ % allocated then fall back to dynamic allocation.
+ ml_gen_new_object(MaybeConsId, Tag, HasSecTag, MaybeCtorName, Var,
+ ExtraRvals, ExtraTypes, ArgVars, ArgModes, TakeAddr,
+ construct_dynamically, Context, DynamicDecls, DynamicStmt, !Info),
+ IfElse = statement(ml_stmt_block(DynamicDecls, DynamicStmt),
+ MLDS_Context),
+
+ IfStatement = statement(
+ ml_stmt_if_then_else(lval(Var1Lval), IfBody, yes(IfElse)),
+ mlds_make_context(Context)),
+
+ Statements = [AssignStatement, IfStatement],
Decls = []
;
HowToConstruct = construct_in_region(_RegVar),
diff --git a/compiler/mlds.m b/compiler/mlds.m
index 0047d26..c6f86d2 100644
--- a/compiler/mlds.m
+++ b/compiler/mlds.m
@@ -1238,9 +1238,15 @@
% Assign the value specified by rval to the location
% specified by lval.
+ ; assign_if_in_heap(mlds_lval, mlds_rval)
+ % assign_if_in_heap(Location, Value):
+ % Assign the address specified by rval to the location specified
+ % by lval if the address is in the bounds of the garbage collected
+ % heap. Otherwise assign a null pointer to lval.
+
% Heap management.
- ; delete_object(mlds_lval)
+ ; delete_object(mlds_rval)
% Compile time garbage collect (ie explicitly
% deallocate) the memory used by the lval.
diff --git a/compiler/mlds_to_c.m b/compiler/mlds_to_c.m
index a7caf57..8964ceb 100644
--- a/compiler/mlds_to_c.m
+++ b/compiler/mlds_to_c.m
@@ -3134,8 +3134,19 @@ mlds_output_atomic_stmt(Indent, _FuncInfo, assign(Lval, Rval), _, !IO) :-
mlds_output_rval(Rval, !IO),
io.write_string(";\n", !IO).
-mlds_output_atomic_stmt(_Indent, _FuncInfo, delete_object(_Lval), _, !IO) :-
- sorry(this_file, "delete_object not implemented").
+mlds_output_atomic_stmt(Indent, _FuncInfo, assign_if_in_heap(Lval, Rval), _, !IO) :-
+ mlds_indent(Indent, !IO),
+ io.write_string("MR_assign_if_in_heap(", !IO),
+ mlds_output_lval(Lval, !IO),
+ io.write_string(", ", !IO),
+ mlds_output_rval(Rval, !IO),
+ io.write_string(");\n", !IO).
+
+mlds_output_atomic_stmt(Indent, _FuncInfo, delete_object(Rval), _, !IO) :-
+ mlds_indent(Indent, !IO),
+ io.write_string("MR_free_heap(", !IO),
+ mlds_output_rval(Rval, !IO),
+ io.write_string(");\n", !IO).
mlds_output_atomic_stmt(Indent, FuncInfo, NewObject, Context, !IO) :-
NewObject = new_object(Target, MaybeTag, _HasSecTag, Type, MaybeSize,
diff --git a/compiler/mlds_to_gcc.m b/compiler/mlds_to_gcc.m
index 8692a63..3bc1580 100644
--- a/compiler/mlds_to_gcc.m
+++ b/compiler/mlds_to_gcc.m
@@ -3094,6 +3094,9 @@ gen_atomic_stmt(DefnInfo, assign(Lval, Rval), _) -->
build_rval(Rval, DefnInfo, GCC_Rval),
gcc__gen_assign(GCC_Lval, GCC_Rval).
+gen_atomic_stmt(_, assign_if_in_heap(_, _), _) -->
+ { sorry(this_file, "gen_atomic_stmt: assign_if_in_heap") }.
+
%
% heap management
%
diff --git a/compiler/mlds_to_il.m b/compiler/mlds_to_il.m
index dcec99a..1725ed9 100644
--- a/compiler/mlds_to_il.m
+++ b/compiler/mlds_to_il.m
@@ -531,7 +531,8 @@ rename_cond(match_range(RvalA, RvalB))
rename_atomic(comment(S)) = comment(S).
rename_atomic(assign(L, R)) = assign(rename_lval(L), rename_rval(R)).
-rename_atomic(delete_object(O)) = delete_object(rename_lval(O)).
+rename_atomic(assign_if_in_heap(L, R)) = assign(rename_lval(L), rename_rval(R)).
+rename_atomic(delete_object(O)) = delete_object(rename_rval(O)).
rename_atomic(new_object(L, Tag, HasSecTag, Type, MaybeSize, Ctxt, Args,
Types, MayUseAtomic))
= new_object(rename_lval(L), Tag, HasSecTag, Type, MaybeSize,
@@ -2034,10 +2035,14 @@ atomic_statement_to_il(assign(Lval, Rval), Instrs, !Info) :-
LoadRvalInstrs,
StoreLvalInstrs
]).
+
+atomic_statement_to_il(assign_if_in_heap(_, _), _, !Info) :-
+ sorry(this_file, "assign_if_in_heap").
+
atomic_statement_to_il(comment(Comment), Instrs, !Info) :-
Instrs = node([comment(Comment)]).
-atomic_statement_to_il(delete_object(Target), Instrs, !Info) :-
+atomic_statement_to_il(delete_object(_Target), Instrs, !Info) :-
% XXX We assume the code generator knows what it is doing and is only
% going to delete real objects (e.g. reference types). It would perhaps
% be prudent to check the type of delete_object (if it had one) to
@@ -2046,8 +2051,13 @@ atomic_statement_to_il(delete_object(Target), Instrs, !Info) :-
% We implement delete_object by storing null in the lval, which hopefully
% gives the garbage collector a good solid hint that this storage is
% no longer required.
- get_load_store_lval_instrs(Target, LoadInstrs, StoreInstrs, !Info),
- Instrs = tree_list([LoadInstrs, instr_node(ldnull), StoreInstrs]).
+ %
+ % XXX commented out because `delete_object' was changed to take an rval
+ % instead of an lval
+ %
+ % get_load_store_lval_instrs(Target, LoadInstrs, StoreInstrs, !Info),
+ % Instrs = tree_list([LoadInstrs, instr_node(ldnull), StoreInstrs]).
+ Instrs = empty.
atomic_statement_to_il(new_object(Target0, _MaybeTag, HasSecTag, Type, Size,
MaybeCtorName, Args0, ArgTypes0, _MayUseAtomic), Instrs, !Info) :-
diff --git a/compiler/mlds_to_java.m b/compiler/mlds_to_java.m
index 2221552..3cb3221 100644
--- a/compiler/mlds_to_java.m
+++ b/compiler/mlds_to_java.m
@@ -2811,6 +2811,9 @@ output_atomic_stmt(Indent, ModuleInfo, FuncInfo, assign(Lval, Rval), _, !IO) :-
),
io.write_string(";\n", !IO).
+output_atomic_stmt(_, _, _, assign_if_in_heap(_, _), _, !IO) :-
+ sorry(this_file, "output_atomic_stmt: assign_if_in_heap").
+
% heap management
%
output_atomic_stmt(_Indent, _, _FuncInfo, delete_object(_Lval), _, _, _) :-
diff --git a/compiler/options.m b/compiler/options.m
index faee9af..7feb4fb 100644
--- a/compiler/options.m
+++ b/compiler/options.m
@@ -631,6 +631,7 @@
; structure_reuse_constraint_arg
; structure_reuse_max_conditions
; structure_reuse_repeat
+ ; structure_reuse_free_cells
% Stuff for the old termination analyser.
; termination
@@ -1349,6 +1350,7 @@ option_defaults_2(special_optimization_option, [
structure_reuse_constraint_arg - int(0),
structure_reuse_max_conditions - int(10),
structure_reuse_repeat - int(0),
+ structure_reuse_free_cells - bool(no),
termination - bool(no),
termination_single_args - int(0),
termination_norm - string("total"),
@@ -2316,6 +2318,7 @@ long_option("structure-reuse-constraint-arg", structure_reuse_constraint_arg).
long_option("ctgc-constraint-arg", structure_reuse_constraint_arg).
long_option("structure-reuse-max-conditions", structure_reuse_max_conditions).
long_option("structure-reuse-repeat", structure_reuse_repeat).
+long_option("structure-reuse-free-cells", structure_reuse_free_cells).
% HLDS->LLDS optimizations
long_option("smart-indexing", smart_indexing).
@@ -3697,6 +3700,11 @@ options_help_ctgc -->
% "--structure-reuse-max-conditions",
% "\tSoft limit on the number of reuse conditions to accumulate",
% "\tfor a procedure. (default: 10)"
+
+% This option is likely to break many optimisations which haven't been updated.
+% "--structure-reuse-free-cells",
+% "\tImmediately free cells which are known to be dead but which",
+% "\tcannot be reused."
]).
:- pred options_help_termination(io::di, io::uo) is det.
diff --git a/compiler/structure_reuse.direct.choose_reuse.m b/compiler/structure_reuse.direct.choose_reuse.m
index 7bd82b7..d081a6a 100644
--- a/compiler/structure_reuse.direct.choose_reuse.m
+++ b/compiler/structure_reuse.direct.choose_reuse.m
@@ -135,8 +135,13 @@ determine_reuse(Strategy, ModuleInfo, ProcInfo, DeadCellTable, !Goal,
process_goal(BackGroundInfo, DeadCellTable, RemainingDeadCellTable,
!Goal, reuse_as_init, ReuseAs, !IO),
- % Check for cell caching.
- check_for_cell_caching(RemainingDeadCellTable, !Goal, !IO).
+ globals.io_lookup_bool_option(structure_reuse_free_cells, FreeCells, !IO),
+ (
+ FreeCells = yes,
+ check_for_cell_caching(RemainingDeadCellTable, !Goal, !IO)
+ ;
+ FreeCells = no
+ ).
%-----------------------------------------------------------------------------%
@@ -471,42 +476,47 @@ process_goal(Background, !DeadCellTable, !Goal, !ReuseAs, !IO):-
% Select the deconstructions-constructions with highest value.
%
Match = highest_match_degree_ratio(MatchTable),
-
- % Maybe dump all the matches recorded in the table, highlight the
- % match with the highest value.
- %
- maybe_write_string(VeryVerbose, "% Reuse results: \n", !IO),
- maybe_dump_match_table(VeryVerbose, MatchTable, Match, !IO),
-
- OldGoal = !.Goal,
- OldReuseAs = !.ReuseAs,
-
- % Realise the reuses by explicitly annotating the procedure goal.
- annotate_reuses_in_goal(Background, Match, !Goal),
-
- % Remove the deconstructions from the available map of dead cells.
- remove_deconstructions_from_dead_cell_table(Match, !DeadCellTable),
-
- % Add the conditions involved in the reuses to the existing
- % conditions.
- ModuleInfo = Background ^ back_module_info,
- ProcInfo = Background ^ back_proc_info,
- reuse_as_least_upper_bound(ModuleInfo, ProcInfo,
- match_get_condition(Background, Match), !ReuseAs),
-
- % If there would be too many reuse conditions on this procedure
- % by taking the reuse opportunity, just drop it.
- globals.io_lookup_int_option(structure_reuse_max_conditions,
- MaxConditions, !IO),
- ( reuse_as_count_conditions(!.ReuseAs) > MaxConditions ->
- !:Goal = OldGoal,
- !:ReuseAs = OldReuseAs
+ (
+ Match ^ con_specs = []
;
- true
- ),
+ Match ^ con_specs = [_ | _],
+
+ % Maybe dump all the matches recorded in the table, highlight the
+ % match with the highest value.
+ %
+ maybe_write_string(VeryVerbose, "% Reuse results: \n", !IO),
+ maybe_dump_match_table(VeryVerbose, MatchTable, Match, !IO),
+
+ OldGoal = !.Goal,
+ OldReuseAs = !.ReuseAs,
+
+ % Realise the reuses by explicitly annotating the procedure goal.
+ annotate_reuses_in_goal(Background, Match, !Goal),
+
+ % Remove the deconstructions from the available map of dead cells.
+ remove_deconstructions_from_dead_cell_table(Match, !DeadCellTable),
+
+ % Add the conditions involved in the reuses to the existing
+ % conditions.
+ ModuleInfo = Background ^ back_module_info,
+ ProcInfo = Background ^ back_proc_info,
+ reuse_as_least_upper_bound(ModuleInfo, ProcInfo,
+ match_get_condition(Background, Match), !ReuseAs),
+
+ % If there would be too many reuse conditions on this procedure
+ % by taking the reuse opportunity, just drop it.
+ globals.io_lookup_int_option(structure_reuse_max_conditions,
+ MaxConditions, !IO),
+ ( reuse_as_count_conditions(!.ReuseAs) > MaxConditions ->
+ !:Goal = OldGoal,
+ !:ReuseAs = OldReuseAs
+ ;
+ true
+ ),
- % Process the goal for further reuse-matches.
- process_goal(Background, !DeadCellTable, !Goal, !ReuseAs, !IO)
+ % Process the goal for further reuse-matches.
+ process_goal(Background, !DeadCellTable, !Goal, !ReuseAs, !IO)
+ )
).
:- pred remove_deconstructions_from_dead_cell_table(match::in,
@@ -1364,6 +1374,9 @@ maybe_dump_full_table(yes, M, !IO) :-
% structures, without imposing any reuse constraints are annotated so that
% these cells can be cached whenever the user specifies that option.
%
+ % XXX cell caching is not actually implemented, but we use the same
+ % information to free dead cells that have no reuse opportunity
+ %
:- pred check_for_cell_caching(dead_cell_table::in, hlds_goal::in,
hlds_goal::out, io::di, io::uo) is det.
@@ -1371,9 +1384,11 @@ check_for_cell_caching(DeadCellTable0, !Goal, !IO) :-
dead_cell_table_remove_conditionals(DeadCellTable0, DeadCellTable),
globals.io_lookup_bool_option(very_verbose, VeryVerbose, !IO),
( dead_cell_table_is_empty(DeadCellTable) ->
- maybe_write_string(VeryVerbose, "% No cells to be cached.\n", !IO)
+ maybe_write_string(VeryVerbose,
+ "% No cells to be cached/freed.\n", !IO)
;
- maybe_write_string(VeryVerbose, "% Marking cacheable cells.\n", !IO),
+ maybe_write_string(VeryVerbose,
+ "% Marking cacheable/freeable cells.\n", !IO),
check_for_cell_caching_2(DeadCellTable, !Goal)
).
diff --git a/compiler/unify_gen.m b/compiler/unify_gen.m
index ec8386e..518dcb1 100644
--- a/compiler/unify_gen.m
+++ b/compiler/unify_gen.m
@@ -135,11 +135,31 @@ generate_unification(CodeModel, Uni, GoalInfo, Code, !CI) :-
Code = empty
)
;
- Uni = deconstruct(Var, ConsId, Args, Modes, _CanFail, _CanCGC),
+ Uni = deconstruct(Var, ConsId, Args, Modes, _CanFail, CanCGC),
( CodeModel = model_det ->
- generate_det_deconstruction(Var, ConsId, Args, Modes, Code, !CI)
+ generate_det_deconstruction(Var, ConsId, Args, Modes, Code0, !CI)
;
- generate_semi_deconstruction(Var, ConsId, Args, Modes, Code, !CI)
+ generate_semi_deconstruction(Var, ConsId, Args, Modes, Code0, !CI)
+ ),
+ (
+ CanCGC = can_cgc,
+ % XXX we can't free the cell yet.
+ % Any live variables which are only reachable via Var (or its
+ % aliases?) must be produced beforehand.
+ %
+ % XXX avoid strip_tag when we know what tag it will have
+ % VarName = variable_name(!.CI, Var),
+ % FreeVar = node([
+ % llds_instr(free_heap(unop(strip_tag, VarRval)),
+ % "Free " ++ VarName)
+ % ]),
+ ProduceArgs = empty,
+ ProduceVar = empty,
+ FreeVar = empty,
+ Code = tree_list([Code0, ProduceArgs, ProduceVar, FreeVar])
+ ;
+ CanCGC = cannot_cgc,
+ Code = Code0
)
;
Uni = simple_test(Var1, Var2),
diff --git a/runtime/mercury_heap.h b/runtime/mercury_heap.h
index 5121833..29a0c65 100644
--- a/runtime/mercury_heap.h
+++ b/runtime/mercury_heap.h
@@ -176,7 +176,13 @@
#define MR_mark_hp(dest) ((void) 0)
#define MR_restore_hp(src) ((void) 0)
- #define MR_free_heap(ptr) GC_FREE((ptr))
+ #define MR_free_heap(ptr) \
+ do { \
+ MR_Word *tmp = (MR_Word *) (ptr); \
+ if (MR_in_heap_range(tmp)) { \
+ GC_FREE(tmp); \
+ } \
+ } while (0)
#else /* not MR_CONSERVATIVE_GC */
@@ -448,6 +454,12 @@
} \
} while (0)
+#define MR_assign_if_in_heap(dest, addr) \
+ do { \
+ MR_Word tmp = (addr); \
+ (dest) = MR_in_heap_range(tmp) ? tmp : (MR_Word) NULL; \
+ } while (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