[m-dev.] [reuse] diff: extra feedback + alias-pass optimization
Nancy Mazur
Nancy.Mazur at cs.kuleuven.ac.be
Mon Oct 23 18:32:20 AEDT 2000
Hi,
===================================================================
Estimated hours taken: 2
Add some extra information in the cases where reuse is missed (give some
feedback on why the reuse-test failed).
Try to optimize the alias-pass by performing normalization at the end
of disjunctions (inducing possible loss of precision).
sr_indirect.m:
Give extra feedback on missed reuses.
sr_data.m:
hlds_goal.m:
Move short_reuse_info to sr_data.
hlds_out.m:
Give extra feedback when reuse is missed in places where a call
is made to a procedure having conditional reuse.
sr_dead.m:
pa_run.m:
pa_alias_as.m:
Perform normalization of the big alias abstract substitutions
within the least upper bound operation (used at the end of
disjunctions).
Index: hlds_goal.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_goal.m,v
retrieving revision 1.76.2.4
diff -u -r1.76.2.4 hlds_goal.m
--- hlds_goal.m 2000/10/09 17:53:07 1.76.2.4
+++ hlds_goal.m 2000/10/23 07:24:18
@@ -690,11 +690,6 @@
; first
; later.
-:- type short_reuse_info --->
- no_reuse
- ; cell_died
- ; cell_reused(prog_var)
- ; reuse_call.
:- type goal_path == list(goal_path_step).
Index: hlds_out.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_out.m,v
retrieving revision 1.243.2.8
diff -u -r1.243.2.8 hlds_out.m
--- hlds_out.m 2000/10/13 08:55:03 1.243.2.8
+++ hlds_out.m 2000/10/23 07:24:20
@@ -1130,7 +1130,7 @@
(
{ REUSE = reuse(cell_died) }
->
- io__write_string("cell just died (deconstruction).\n")
+ io__write_string("cell just died (deconstruction).\n")
;
{ REUSE = reuse(cell_reused(ProgVar)) }
->
@@ -1143,7 +1143,12 @@
->
io__write_string("call to procedure with reuse.\n")
;
- { require__error("No legal alternative for short_reuse_info anymore left.") }
+ { REUSE = reuse(missed_reuse_call(Causes)) }
+ ->
+ io__write_string("failed reuse call:\n"),
+ write_missed_reuse_call_text(Indent,Causes)
+ ;
+ { require__error("Not a legal alternative for short_reuse_info at this stage.\n") }
)
),
@@ -1238,6 +1243,21 @@
;
[]
).
+
+:- pred write_missed_reuse_call_text( int::in, list(string)::in,
+ io__state::di, io__state::uo) is det.
+write_missed_reuse_call_text( Indent, Causes ) -->
+ list__foldl(
+ write_missed_reuse_call_text_2( Indent ),
+ Causes).
+
+:- pred write_missed_reuse_call_text_2( int::in, string::in,
+ io__state::di, io__state::uo) is det.
+write_missed_reuse_call_text_2( Indent, Text ) -->
+ hlds_out__write_indent( Indent ),
+ io__write_string("%\t"),
+ io__write_string(Text),
+ io__nl.
:- pred hlds_out__write_goal_2(hlds_goal_expr, module_info, prog_varset, bool,
int, string, maybe_vartypes, io__state, io__state).
Index: pa_alias_as.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/pa_alias_as.m,v
retrieving revision 1.1.2.6
diff -u -r1.1.2.6 pa_alias_as.m
--- pa_alias_as.m 2000/10/17 18:48:36 1.1.2.6
+++ pa_alias_as.m 2000/10/23 07:24:21
@@ -15,7 +15,7 @@
%-- import_module
% library modules
-:- import_module set, list, map, string.
+:- import_module set, list, map, string, int.
:- import_module io, term, std_util.
% compiler modules
@@ -34,6 +34,7 @@
%-----------------------------------------------------------------------------%
%-- exported predicates
+
:- pred init( alias_as::out ) is det.
:- pred is_bottom( alias_as::in ) is semidet.
@@ -84,9 +85,9 @@
:- mode least_upper_bound( in, in, in, in, out) is det.
% compute least upper bound of a list of abstract substitutions.
-:- pred least_upper_bound_list( proc_info, module_info,
+:- pred least_upper_bound_list( proc_info, module_info, hlds_goal_info,
list(alias_as), alias_as).
-:- mode least_upper_bound_list( in, in, in, out) is det.
+:- mode least_upper_bound_list( in, in, in, in, out) is det.
% extend( NEW, OLD, RESULT).
% extend a given abstract substitution with new information.
@@ -173,6 +174,10 @@
% near future: alias_as should also include top(string),
% where string could be some sort of message.
+% constants
+:- func alias_limit = int.
+
+alias_limit = 100000.
%-----------------------------------------------------------------------------%
@@ -375,8 +380,36 @@
RESULT = AS
).
-least_upper_bound_list( ProcInfo, HLDS, AS_LIST, AS ) :-
- list__foldl(least_upper_bound(ProcInfo, HLDS) , AS_LIST, bottom, AS).
+least_upper_bound_list( ProcInfo, HLDS, GoalInfo, Alias_list0, AS ) :-
+ list__map(
+ maybe_normalize( ProcInfo, HLDS, GoalInfo ),
+ Alias_list0,
+ Alias_list),
+ list__foldl(least_upper_bound(ProcInfo, HLDS) , Alias_list,
+ bottom, AS).
+
+:- pred maybe_normalize( proc_info, module_info, hlds_goal_info,
+ alias_as, alias_as).
+:- mode maybe_normalize( in, in, in, in, out ) is det.
+
+maybe_normalize( ProcInfo, HLDS, GoalInfo, Alias0, Alias ) :-
+ (
+ Alias0 = top(_),
+ Alias = Alias0
+ ;
+ Alias0 = bottom,
+ Alias = Alias0
+ ;
+ Alias0 = real_as(_),
+ (
+ size(Alias0) > alias_limit
+ ->
+ normalize_with_goal_info( ProcInfo, HLDS, GoalInfo,
+ Alias0, Alias)
+ ;
+ Alias = Alias0
+ )
+ ).
extend(ProcInfo, HLDS, A1, A2, RESULT ):-
(
@@ -617,13 +650,22 @@
).
%-----------------------------------------------------------------------------%
+
+:- pred normalize_with_goal_info( proc_info::in, module_info::in,
+ hlds_goal_info::in, alias_as::in, alias_as::out) is det.
+normalize_with_goal_info( ProcInfo, HLDS, GoalInfo, Alias0, Alias):-
+ goal_info_get_instmap_delta(GoalInfo, InstMapDelta),
+ instmap__init_reachable(InitIM),
+ instmap__apply_instmap_delta(InitIM, InstMapDelta, InstMap),
+ normalize( ProcInfo, HLDS, InstMap, Alias0, Alias).
+
-normalize( ProcInfo, HLDS, _INSTMAP, ALIASin, ALIASout):-
+normalize( ProcInfo, HLDS, _InstMap, Alias0, Alias):-
% normalize only using type-info's
- normalize_wti( ProcInfo, HLDS, ALIASin, ALIAS1),
+ normalize_wti( ProcInfo, HLDS, Alias0, Alias1),
% removing doubles is not enough -- subsumption should
% be verified.
- simplify_upon_subsumption( ProcInfo, HLDS, ALIAS1, ALIASout).
+ simplify_upon_subsumption( ProcInfo, HLDS, Alias1, Alias).
:- pred normalize_wti( proc_info, module_info, alias_as, alias_as).
:- mode normalize_wti( in, in, in, out) is det.
Index: pa_run.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/pa_run.m,v
retrieving revision 1.1.2.9
diff -u -r1.1.2.9 pa_run.m
--- pa_run.m 2000/10/17 18:48:36 1.1.2.9
+++ pa_run.m 2000/10/23 07:24:21
@@ -324,11 +324,12 @@
pa_alias_as__top(A0, Msg, A).
% error("(pa) generic_call not handled") .
-analyse_goal_expr( switch(_Var,_CF,Cases,_SM), _Info,
+analyse_goal_expr( switch(_Var,_CF,Cases,_SM), Info,
ProcInfo, HLDS, T0, T, A0, A ):-
list__map_foldl( analyse_case(ProcInfo, HLDS, A0),
Cases, SwitchAliases, T0, T),
- pa_alias_as__least_upper_bound_list(ProcInfo,HLDS,SwitchAliases, A ).
+ pa_alias_as__least_upper_bound_list(ProcInfo,HLDS,Info,
+ SwitchAliases, A ).
:- pred analyse_case( proc_info, module_info,
alias_as, case, alias_as,
@@ -345,7 +346,7 @@
pa_alias_as__extend_unification( ProcInfo, HLDS, Unification,
Info, A0, A).
-analyse_goal_expr( disj(Goals, _SM), _Info, ProcInfo, HLDS, T0, T, A0, A ):-
+analyse_goal_expr( disj(Goals, _SM), Info, ProcInfo, HLDS, T0, T, A0, A ):-
list__map_foldl(
pred( Goal::in, Alias::out, FPT0::in, FPT::out) is det :-
( analyse_goal( ProcInfo, HLDS, Goal,
@@ -353,7 +354,8 @@
Goals,
DisjAliases,
T0, T ),
- pa_alias_as__least_upper_bound_list( ProcInfo, HLDS, DisjAliases, A ).
+ pa_alias_as__least_upper_bound_list( ProcInfo, HLDS, Info,
+ DisjAliases, A ).
analyse_goal_expr( not(Goal), _Info, ProcInfo, HLDS , T0, T, A0, A ):-
analyse_goal( ProcInfo, HLDS, Goal, T0, T, A0, A).
Index: sr_data.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_data.m,v
retrieving revision 1.1.2.10
diff -u -r1.1.2.10 sr_data.m
--- sr_data.m 2000/10/17 12:33:33 1.1.2.10
+++ sr_data.m 2000/10/23 07:24:21
@@ -18,7 +18,7 @@
:- import_module map, set, std_util, list, io, term.
:- import_module pa_alias_as, pa_datastruct.
:- import_module sr_live.
-:- import_module hlds_goal, hlds_pred, hlds_module, prog_data.
+:- import_module hlds_pred, hlds_module, prog_data.
% The information placed in the goal info which is used by
% structure reuse.
@@ -30,6 +30,13 @@
; choice(choice_info)
; reuse(short_reuse_info)
.
+
+:- type short_reuse_info --->
+ no_reuse
+ ; cell_died
+ ; cell_reused(prog_var)
+ ; reuse_call
+ ; missed_reuse_call(list(string)).
:- type reuse_var == pair(prog_var, reuse_condition).
:- type choice_info
Index: sr_dead.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_dead.m,v
retrieving revision 1.1.2.7
diff -u -r1.1.2.7 sr_dead.m
--- sr_dead.m 2000/10/17 18:48:37 1.1.2.7
+++ sr_dead.m 2000/10/23 07:24:21
@@ -90,7 +90,7 @@
ListPools, ListAliases),
dead_cell_pool_least_upper_bound_disj( Outscope,
ListPools, Pool ),
- pa_alias_as__least_upper_bound_list( ProcInfo, HLDS,
+ pa_alias_as__least_upper_bound_list( ProcInfo, HLDS, Info0,
ListAliases, Alias),
Info = Info0,
Expr = switch( A, B, Cases, SM ),
@@ -135,7 +135,7 @@
dead_cell_pool_least_upper_bound_disj( Outscope,
ListPools, Pool),
pa_alias_as__least_upper_bound_list( ProcInfo,
- HLDS, ListAliases, Alias)
+ HLDS, Info0, ListAliases, Alias)
),
Info = Info0,
Expr = disj(Goals, SM ),
@@ -172,7 +172,7 @@
PoolElse, Alias0, AliasElse),
dead_cell_pool_least_upper_bound_disj( Outscope,
[ PoolThen, PoolElse ], Pool),
- pa_alias_as__least_upper_bound_list( ProcInfo, HLDS,
+ pa_alias_as__least_upper_bound_list( ProcInfo, HLDS, Info0,
[ AliasThen, AliasElse ], Alias),
Info = Info0,
Expr = if_then_else( Vars, Cond, Then, Else, SM),
Index: sr_indirect.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_indirect.m,v
retrieving revision 1.1.2.11
diff -u -r1.1.2.11 sr_indirect.m
--- sr_indirect.m 2000/10/17 18:48:37 1.1.2.11
+++ sr_indirect.m 2000/10/23 07:24:22
@@ -31,6 +31,7 @@
:- import_module sr_data, sr_util, sr_live.
:- import_module sr_fixpoint_table.
:- import_module globals, options.
+:- import_module pa_datastruct.
compute_fixpoint(HLDS0, HLDSout) -->
% compute the strongly connected components
@@ -334,7 +335,7 @@
indirect_reuse_pool_least_upper_bound_disjunction(
ListPools,
Pool),
- pa_alias_as__least_upper_bound_list(ProcInfo, HLDS,
+ pa_alias_as__least_upper_bound_list(ProcInfo, HLDS, Info0,
ListAliases,
Alias1),
set__power_union(set__list_to_set(ListStatic), Static),
@@ -380,7 +381,7 @@
indirect_reuse_pool_least_upper_bound_disjunction(
ListPools,
Pool),
- pa_alias_as__least_upper_bound_list(ProcInfo, HLDS,
+ pa_alias_as__least_upper_bound_list(ProcInfo, HLDS, Info0,
ListAliases,
Alias1),
@@ -421,7 +422,7 @@
[AI_Then ^ pool, AI_Else ^ pool],
Pool),
- pa_alias_as__least_upper_bound_list(ProcInfo, HLDS,
+ pa_alias_as__least_upper_bound_list(ProcInfo, HLDS, Info0,
[AI_Then ^ alias, AI_Else ^ alias],
Alias1),
Static = AI_Then ^ static `set__union` AI_Else ^ static,
@@ -520,7 +521,7 @@
FP0, FP),
indirect_reuse_pool_least_upper_bound_disjunction( ListPools,
Pool),
- pa_alias_as__least_upper_bound_list(ProcInfo, HLDS,
+ pa_alias_as__least_upper_bound_list(ProcInfo, HLDS, Info0,
ListAliases,
Alias1),
% reduce the aliases
@@ -572,7 +573,7 @@
indirect_reuse_pool_least_upper_bound_disjunction(
ListPools,
Pool),
- pa_alias_as__least_upper_bound_list(ProcInfo, HLDS,
+ pa_alias_as__least_upper_bound_list(ProcInfo, HLDS, Info0,
ListAliases,
Alias1),
% reduce the aliases
@@ -624,7 +625,7 @@
[PoolTHEN, PoolELSE],
Pool),
- pa_alias_as__least_upper_bound_list(ProcInfo, HLDS,
+ pa_alias_as__least_upper_bound_list(ProcInfo, HLDS, Info0,
[AliasTHEN, AliasELSE],
Alias1),
FP = FP3,
@@ -761,11 +762,92 @@
YesNo = yes
;
Pool = Pool0,
- Info = Info0,
+
+ examine_cause_of_missed_reuse( LBUi, LFUi,
+ StaticTerms, Memo,
+ Cause ),
+
+ goal_info_set_reuse(Info0,
+ reuse(missed_reuse_call(Cause)), Info),
YesNo = no
)
).
-
+
+:- pred examine_cause_of_missed_reuse( set(prog_var)::in,
+ set(prog_var)::in,
+ set(prog_var)::in,
+ memo_reuse::in, list(string)::out) is det.
+examine_cause_of_missed_reuse( LFU, LBU, Static, Memo, Causes ) :-
+ (
+ Memo = yes(Conditions)
+ ->
+ list__filter_map(
+ examine_cause_of_missed_condition(LFU, LBU, Static),
+ Conditions,
+ Causes)
+ ;
+ Cause = "No failed reuse because there is no reuse.",
+ Causes = [Cause]
+ ).
+
+:- pred examine_cause_of_missed_condition( set(prog_var)::in,
+ set(prog_var)::in,
+ set(prog_var)::in,
+ reuse_condition::in,
+ string::out) is semidet.
+
+examine_cause_of_missed_condition( LFU, LBU, StaticVars, Condition, Cause ) :-
+ sr_live__init(DummyLive),
+ pa_alias_as__init( BottomAlias),
+ pa_alias_as__live( LFU, DummyLive, BottomAlias, LFU_Live),
+ pa_alias_as__live( LBU, DummyLive, BottomAlias, LBU_Live),
+ Condition = condition( Nodes, _LU, _LA ),
+ %
+ NodesL = set__to_sorted_list(Nodes),
+ (
+ % check whether reason for no reuse is StaticVars
+ list__filter_map(
+ (pred(Node::in, Var::out) is semidet :-
+ get_var(Node, Var),
+ set__member(Var, StaticVars)
+ ),
+ NodesL,
+ R),
+ R \= []
+ ->
+ % due to static vars
+ Cause = "Node is static."
+ ;
+ % not due to static vars
+ % check for LFU
+ list__filter(
+ ( pred(D::in) is semidet :-
+ sr_live__is_live_datastruct( D, LFU_Live)
+ ),
+ NodesL,
+ RF),
+ RF \= []
+ ->
+ % due to lfu
+ Cause = "Node is in local forward use."
+ ;
+ % not due to LFU
+ % check LBU
+ list__filter(
+ ( pred(D::in) is semidet :-
+ sr_live__is_live_datastruct( D, LBU_Live)
+ ),
+ NodesL,
+ RB),
+ RB \= []
+ ->
+ % due to lbu
+ Cause = "Node is in local backward use."
+ ;
+ Cause = "Node is live because it has a live alias."
+ ).
+
+
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
:- pred lookup_memo_reuse( pred_id, proc_id, module_info,
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to: mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions: mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------
More information about the developers
mailing list