1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
|
%-----------------------------------------------------------------------------%
% Copyright (C) 1995-2000 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
% Main author: zs.
% This module traverses the goal for each procedure, looking
% for conjunctions containing assignment unifications to or from
% a variable that is local to the conjunction. Such unifications
% effectively just introduce a new local name for a variable.
% This module optimizes away such unifications by replacing all
% occurrences of the local name with the other name.
%
% Note that the output of this pass is not in super-homogeneous form,
% since if two equivalent variables are passed in two argument positions,
% they will not be distinct after this pass. This is not a problem, since
% this pass occurs after the passes that rely on super-homogeneous form.
%
% This HLDS-to-HLDS optimization is applied after the front end has
% completed all of its semantic checks (i.e. after determinism analysis),
% but before code generation.
%
% It allows optimizations such as middle recursion to be simplified,
% and it reduces the pressure on the stack slot allocator.
%-----------------------------------------------------------------------------%
:- module excess.
:- interface.
:- import_module hlds_module, hlds_pred.
% optimize away excess assignments for a single procedure
:- pred excess_assignments_proc(proc_info, module_info, proc_info).
% :- mode excess_assignments_proc(di, in, uo) is det.
:- mode excess_assignments_proc(in, in, out) is det.
%-----------------------------------------------------------------------------%
:- implementation.
:- import_module hlds_goal, goal_util, prog_data, varset, term.
:- import_module list, bool, map, set, std_util, require.
%-----------------------------------------------------------------------------%
excess_assignments_proc(ProcInfo0, _ModuleInfo, ProcInfo) :-
proc_info_goal(ProcInfo0, Goal0),
excess_assignments_in_goal(Goal0, [], Goal, ElimVars),
proc_info_set_goal(ProcInfo0, Goal, ProcInfo1),
% XXX We probably ought to remove these vars from the type map as well.
proc_info_varset(ProcInfo1, Varset0),
varset__delete_vars(Varset0, ElimVars, Varset),
proc_info_set_varset(ProcInfo1, Varset, ProcInfo).
%-----------------------------------------------------------------------------%
% We want to replace code sequences of the form
%
% (
% <Foo>,
% LocalVar = OtherVar,
% <Bar>
% )
%
% with
%
% (
% <Foo> [LocalVar/OtherVar],
% <Bar> [LocalVar/OtherVar],
% )
%
% where <Foo> and <Bar> are sequences of conjuncts,
% LocalVar is a variable that is local to the conjuncts,
% and the notation `<Foo> [X/Y]' means <Foo> with all
% occurrences of `X' replaced with `Y'.
:- pred excess_assignments_in_goal(hlds_goal, list(prog_var),
hlds_goal, list(prog_var)).
:- mode excess_assignments_in_goal(in, in, out, out) is det.
excess_assignments_in_goal(GoalExpr0 - GoalInfo0, ElimVars0, Goal, ElimVars) :-
(
GoalExpr0 = conj(Goals0),
goal_info_get_nonlocals(GoalInfo0, NonLocals),
excess_assignments_in_conj(Goals0, [], ElimVars0, NonLocals,
Goals, ElimVars),
conj_list_to_goal(Goals, GoalInfo0, Goal)
;
GoalExpr0 = par_conj(Goals0, _SM),
goal_info_get_nonlocals(GoalInfo0, NonLocals),
excess_assignments_in_conj(Goals0, [], ElimVars0, NonLocals,
Goals, ElimVars),
par_conj_list_to_goal(Goals, GoalInfo0, Goal)
;
GoalExpr0 = disj(Goals0, SM),
excess_assignments_in_disj(Goals0, ElimVars0, Goals, ElimVars),
Goal = disj(Goals, SM) - GoalInfo0
;
GoalExpr0 = not(NegGoal0),
excess_assignments_in_goal(NegGoal0, ElimVars0,
NegGoal, ElimVars),
Goal = not(NegGoal) - GoalInfo0
;
GoalExpr0 = switch(Var, CanFail, Cases0, SM),
excess_assignments_in_switch(Cases0, ElimVars0,
Cases, ElimVars),
Goal = switch(Var, CanFail, Cases, SM) - GoalInfo0
;
GoalExpr0 = if_then_else(Vars, Cond0, Then0, Else0, SM),
excess_assignments_in_goal(Cond0, ElimVars0, Cond, ElimVars1),
excess_assignments_in_goal(Then0, ElimVars1, Then, ElimVars2),
excess_assignments_in_goal(Else0, ElimVars2, Else, ElimVars),
Goal = if_then_else(Vars, Cond, Then, Else, SM) - GoalInfo0
;
GoalExpr0 = some(Var, CanRemove, SubGoal0),
excess_assignments_in_goal(SubGoal0, ElimVars0,
SubGoal, ElimVars),
Goal = some(Var, CanRemove, SubGoal) - GoalInfo0
;
GoalExpr0 = generic_call(_, _, _, _),
Goal = GoalExpr0 - GoalInfo0,
ElimVars = ElimVars0
;
GoalExpr0 = call(_, _, _, _, _, _),
Goal = GoalExpr0 - GoalInfo0,
ElimVars = ElimVars0
;
GoalExpr0 = unify(_, _, _, _, _),
Goal = GoalExpr0 - GoalInfo0,
ElimVars = ElimVars0
;
GoalExpr0 = pragma_foreign_code(_, _, _, _, _, _, _),
Goal = GoalExpr0 - GoalInfo0,
ElimVars = ElimVars0
;
GoalExpr0 = bi_implication(_, _),
% these should have been expanded out by now
error("detect_cse_in_goal_2: unexpected bi_implication")
).
%-----------------------------------------------------------------------------%
% We apply each substitution as soon as we find the need for it.
% This is to handle code which has V_4 = V_5, V_5 = V_6. If at most
% one of these variables is nonlocal, we can eliminate both assignments.
% If (say) V_4 and V_6 are nonlocal, then after the V_5 => V_4
% substitution has been made, the second assignment V_4 = V_6
% is left alone.
%
% This code is used for both sequential conjunction (conj/1) and
% parallel conjunction (par_conj/2).
:- pred excess_assignments_in_conj(list(hlds_goal), list(hlds_goal),
list(prog_var), set(prog_var), list(hlds_goal), list(prog_var)).
:- mode excess_assignments_in_conj(in, in, in, in, out, out) is det.
excess_assignments_in_conj([], RevGoals, ElimVars, _, Goals, ElimVars) :-
list__reverse(RevGoals, Goals).
excess_assignments_in_conj([Goal0 | Goals0], RevGoals0, ElimVars0, NonLocals,
Goals, ElimVars) :-
(
Goal0 = unify(_, _, _, Unif, _) - _,
Unif = assign(LeftVar, RightVar),
( \+ set__member(LeftVar, NonLocals) ->
LocalVar = LeftVar, ReplacementVar = RightVar
; \+ set__member(RightVar, NonLocals) ->
LocalVar = RightVar, ReplacementVar = LeftVar
;
fail
)
->
map__init(Subn0),
map__det_insert(Subn0, LocalVar, ReplacementVar, Subn),
goal_util__rename_vars_in_goals(Goals0, no, Subn, Goals1),
goal_util__rename_vars_in_goals(RevGoals0, no, Subn, RevGoals1),
ElimVars1 = [LocalVar | ElimVars0]
;
Goals1 = Goals0,
excess_assignments_in_goal(Goal0, ElimVars0, Goal1, ElimVars1),
RevGoals1 = [Goal1 | RevGoals0]
),
excess_assignments_in_conj(Goals1, RevGoals1, ElimVars1,
NonLocals, Goals, ElimVars).
%-----------------------------------------------------------------------------%
:- pred excess_assignments_in_disj(list(hlds_goal), list(prog_var),
list(hlds_goal), list(prog_var)).
:- mode excess_assignments_in_disj(in, in, out, out) is det.
excess_assignments_in_disj([], ElimVars, [], ElimVars).
excess_assignments_in_disj([Goal0 | Goals0], ElimVars0,
[Goal | Goals], ElimVars) :-
excess_assignments_in_goal(Goal0, ElimVars0, Goal, ElimVars1),
excess_assignments_in_disj(Goals0, ElimVars1, Goals, ElimVars).
:- pred excess_assignments_in_switch(list(case), list(prog_var),
list(case), list(prog_var)).
:- mode excess_assignments_in_switch(in, in, out, out) is det.
excess_assignments_in_switch([], ElimVars, [], ElimVars).
excess_assignments_in_switch([case(Cons, Goal0) | Cases0], ElimVars0,
[case(Cons, Goal) | Cases], ElimVars) :-
excess_assignments_in_goal(Goal0, ElimVars0, Goal, ElimVars1),
excess_assignments_in_switch(Cases0, ElimVars1, Cases, ElimVars).
%-----------------------------------------------------------------------------%
|
