]>
Commit | Line | Data |
---|---|---|
73b75827 | 1 | // RTL SSA utilities relating to instruction movement -*- C++ -*- |
83ffe9cd | 2 | // Copyright (C) 2020-2023 Free Software Foundation, Inc. |
73b75827 RS |
3 | // |
4 | // This file is part of GCC. | |
5 | // | |
6 | // GCC is free software; you can redistribute it and/or modify it under | |
7 | // the terms of the GNU General Public License as published by the Free | |
8 | // Software Foundation; either version 3, or (at your option) any later | |
9 | // version. | |
10 | // | |
11 | // GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
12 | // WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | // for more details. | |
15 | // | |
16 | // You should have received a copy of the GNU General Public License | |
17 | // along with GCC; see the file COPYING3. If not see | |
18 | // <http://www.gnu.org/licenses/>. | |
19 | ||
20 | namespace rtl_ssa { | |
21 | ||
22 | // Restrict movement range RANGE so that the instruction is placed later | |
23 | // than INSN. (The movement range is the range of instructions after which | |
24 | // an instruction can be placed.) | |
25 | inline insn_range_info | |
26 | move_later_than (insn_range_info range, insn_info *insn) | |
27 | { | |
28 | return { later_insn (range.first, insn), range.last }; | |
29 | } | |
30 | ||
31 | // Restrict movement range RANGE so that the instruction is placed no earlier | |
32 | // than INSN. (The movement range is the range of instructions after which | |
33 | // an instruction can be placed.) | |
34 | inline insn_range_info | |
35 | move_no_earlier_than (insn_range_info range, insn_info *insn) | |
36 | { | |
37 | insn_info *first = later_insn (range.first, insn->prev_nondebug_insn ()); | |
38 | return { first, range.last }; | |
39 | } | |
40 | ||
41 | // Restrict movement range RANGE so that the instruction is placed no later | |
42 | // than INSN. (The movement range is the range of instructions after which | |
43 | // an instruction can be placed.) | |
44 | inline insn_range_info | |
45 | move_no_later_than (insn_range_info range, insn_info *insn) | |
46 | { | |
47 | return { range.first, earlier_insn (range.last, insn) }; | |
48 | } | |
49 | ||
50 | // Restrict movement range RANGE so that the instruction is placed earlier | |
51 | // than INSN. (The movement range is the range of instructions after which | |
52 | // an instruction can be placed.) | |
53 | inline insn_range_info | |
54 | move_earlier_than (insn_range_info range, insn_info *insn) | |
55 | { | |
56 | insn_info *last = earlier_insn (range.last, insn->prev_nondebug_insn ()); | |
57 | return { range.first, last }; | |
58 | } | |
59 | ||
60 | // Return true if it is possible to insert a new instruction after INSN. | |
61 | inline bool | |
62 | can_insert_after (insn_info *insn) | |
63 | { | |
64 | return insn->is_bb_head () || (insn->is_real () && !insn->is_jump ()); | |
65 | } | |
66 | ||
67 | // Try to restrict move range MOVE_RANGE so that it is possible to | |
68 | // insert INSN after both of the end points. Return true on success, | |
69 | // otherwise leave MOVE_RANGE in an invalid state. | |
70 | inline bool | |
71 | canonicalize_move_range (insn_range_info &move_range, insn_info *insn) | |
72 | { | |
73 | while (move_range.first != insn && !can_insert_after (move_range.first)) | |
74 | move_range.first = move_range.first->next_nondebug_insn (); | |
75 | while (move_range.last != insn && !can_insert_after (move_range.last)) | |
76 | move_range.last = move_range.last->prev_nondebug_insn (); | |
77 | return bool (move_range); | |
78 | } | |
79 | ||
80 | // Try to restrict movement range MOVE_RANGE of INSN so that it can set | |
81 | // or clobber REGNO. Assume that if: | |
82 | // | |
83 | // - an instruction I2 contains another access A to REGNO; and | |
84 | // - IGNORE (I2) is true | |
85 | // | |
86 | // then either: | |
87 | // | |
88 | // - A will be removed; or | |
89 | // - something will ensure that the new definition of REGNO does not | |
90 | // interfere with A, without this having to be enforced by I1's move range. | |
91 | // | |
92 | // Return true on success, otherwise leave MOVE_RANGE in an invalid state. | |
93 | // | |
94 | // This function only works correctly for instructions that remain within | |
95 | // the same extended basic block. | |
96 | template<typename IgnorePredicate> | |
97 | bool | |
98 | restrict_movement_for_dead_range (insn_range_info &move_range, | |
99 | unsigned int regno, insn_info *insn, | |
100 | IgnorePredicate ignore) | |
101 | { | |
102 | // Find a definition at or neighboring INSN. | |
103 | resource_info resource = full_register (regno); | |
104 | def_lookup dl = crtl->ssa->find_def (resource, insn); | |
105 | ||
4a3073f0 | 106 | def_info *prev = dl.last_def_of_prev_group (); |
73b75827 RS |
107 | ebb_info *ebb = insn->ebb (); |
108 | if (!prev || prev->ebb () != ebb) | |
109 | { | |
110 | // REGNO is not defined or used in EBB before INSN, but it | |
111 | // might be live on entry. To keep complexity under control, | |
112 | // handle only these cases: | |
113 | // | |
114 | // - If the register is not live on entry to EBB, the register is | |
115 | // free from the start of EBB to the first definition in EBB. | |
116 | // | |
117 | // - Otherwise, if the register is live on entry to BB, refuse | |
118 | // to allocate the register. We could in principle try to move | |
119 | // the instruction to later blocks in the EBB, but it's rarely | |
120 | // worth the effort, and could lead to linear complexity. | |
121 | // | |
122 | // - Otherwise, don't allow INSN to move earlier than its current | |
123 | // block. Again, we could in principle look backwards to find where | |
124 | // REGNO dies, but it's rarely worth the effort. | |
125 | bb_info *bb = insn->bb (); | |
126 | insn_info *limit; | |
127 | if (!bitmap_bit_p (DF_LR_IN (ebb->first_bb ()->cfg_bb ()), regno)) | |
128 | limit = ebb->phi_insn (); | |
129 | else if (bitmap_bit_p (DF_LR_IN (bb->cfg_bb ()), regno)) | |
130 | return false; | |
131 | else | |
132 | limit = bb->head_insn (); | |
133 | move_range = move_later_than (move_range, limit); | |
134 | } | |
135 | else | |
136 | { | |
137 | // Stop the instruction moving beyond the previous relevant access | |
138 | // to REGNO. | |
139 | access_info *prev_access | |
140 | = last_access_ignoring (prev, ignore_clobbers::YES, ignore); | |
141 | if (prev_access) | |
142 | move_range = move_later_than (move_range, access_insn (prev_access)); | |
143 | } | |
144 | ||
145 | // Stop the instruction moving beyond the next relevant definition of REGNO. | |
4a3073f0 RS |
146 | def_info *next = dl.matching_set_or_first_def_of_next_group (); |
147 | next = first_def_ignoring (next, ignore_clobbers::YES, ignore); | |
73b75827 RS |
148 | if (next) |
149 | move_range = move_earlier_than (move_range, next->insn ()); | |
150 | ||
151 | return canonicalize_move_range (move_range, insn); | |
152 | } | |
153 | ||
154 | // Try to restrict movement range MOVE_RANGE so that it is possible for the | |
155 | // instruction being moved ("instruction I1") to perform all the definitions | |
156 | // in DEFS while still preserving dependencies between those definitions | |
157 | // and surrounding instructions. Assume that if: | |
158 | // | |
159 | // - DEFS contains a definition D of resource R; | |
160 | // - an instruction I2 contains another access A to R; and | |
161 | // - IGNORE (I2) is true | |
162 | // | |
163 | // then either: | |
164 | // | |
165 | // - A will be removed; or | |
166 | // - something will ensure that D and A maintain their current order, | |
167 | // without this having to be enforced by I1's move range. | |
168 | // | |
169 | // Return true on success, otherwise leave MOVE_RANGE in an invalid state. | |
170 | // | |
171 | // This function only works correctly for instructions that remain within | |
172 | // the same extended basic block. | |
173 | template<typename IgnorePredicate> | |
174 | bool | |
175 | restrict_movement_for_defs_ignoring (insn_range_info &move_range, | |
176 | def_array defs, IgnorePredicate ignore) | |
177 | { | |
178 | for (def_info *def : defs) | |
179 | { | |
180 | // If the definition is a clobber, we can move it with respect | |
181 | // to other clobbers. | |
182 | // | |
183 | // ??? We could also do this if a definition and all its uses | |
184 | // are being moved at once. | |
185 | bool is_clobber = is_a<clobber_info *> (def); | |
186 | ||
187 | // Search back for the first unfiltered use or definition of the | |
188 | // same resource. | |
189 | access_info *access; | |
190 | access = prev_access_ignoring (def, ignore_clobbers (is_clobber), | |
191 | ignore); | |
192 | if (access) | |
193 | move_range = move_later_than (move_range, access_insn (access)); | |
194 | ||
195 | // Search forward for the first unfiltered use of DEF, | |
196 | // or the first unfiltered definition that follows DEF. | |
197 | // | |
198 | // We don't need to consider uses of following definitions, since | |
199 | // if IGNORE (D->insn ()) is true for some definition D, the caller | |
200 | // is guarantees that either | |
201 | // | |
202 | // - D will be removed, and thus its uses will be removed; or | |
203 | // - D will occur after DEF, and thus D's uses will also occur | |
204 | // after DEF. | |
205 | // | |
206 | // This is purely a simplification: we could also process D's uses, | |
207 | // but we don't need to. | |
208 | access = next_access_ignoring (def, ignore_clobbers (is_clobber), | |
209 | ignore); | |
210 | if (access) | |
211 | move_range = move_earlier_than (move_range, access_insn (access)); | |
212 | ||
213 | // If DEF sets a hard register, take any call clobbers | |
214 | // into account. | |
215 | unsigned int regno = def->regno (); | |
216 | if (!HARD_REGISTER_NUM_P (regno) || is_clobber) | |
217 | continue; | |
218 | ||
219 | ebb_info *ebb = def->ebb (); | |
220 | for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ()) | |
221 | { | |
222 | if (!call_group->clobbers (def->resource ())) | |
223 | continue; | |
224 | ||
225 | // Exit now if we've already failed, and if the splay accesses | |
226 | // below would be wasted work. | |
227 | if (!move_range) | |
228 | return false; | |
229 | ||
230 | insn_info *insn; | |
231 | insn = prev_call_clobbers_ignoring (*call_group, def->insn (), | |
232 | ignore); | |
233 | if (insn) | |
234 | move_range = move_later_than (move_range, insn); | |
235 | ||
236 | insn = next_call_clobbers_ignoring (*call_group, def->insn (), | |
237 | ignore); | |
238 | if (insn) | |
239 | move_range = move_earlier_than (move_range, insn); | |
240 | } | |
241 | } | |
242 | ||
243 | // Make sure that we don't move stores between basic blocks, since we | |
244 | // don't have enough information to tell whether it's safe. | |
245 | if (def_info *def = memory_access (defs)) | |
246 | { | |
247 | move_range = move_later_than (move_range, def->bb ()->head_insn ()); | |
248 | move_range = move_earlier_than (move_range, def->bb ()->end_insn ()); | |
249 | } | |
250 | ||
251 | return bool (move_range); | |
252 | } | |
253 | ||
254 | // Like restrict_movement_for_defs_ignoring, but for the uses in USES. | |
255 | template<typename IgnorePredicate> | |
256 | bool | |
257 | restrict_movement_for_uses_ignoring (insn_range_info &move_range, | |
258 | use_array uses, IgnorePredicate ignore) | |
259 | { | |
260 | for (const use_info *use : uses) | |
261 | { | |
262 | // Ignore uses of undefined values. | |
263 | set_info *set = use->def (); | |
264 | if (!set) | |
265 | continue; | |
266 | ||
267 | // Ignore uses by debug instructions. Debug instructions are | |
268 | // never supposed to move, and uses by debug instructions are | |
269 | // never supposed to be transferred elsewhere, so we know that | |
270 | // the caller must be changing the uses on the debug instruction | |
271 | // and checking whether all new uses are available at the debug | |
272 | // instruction's original location. | |
273 | if (use->is_in_debug_insn ()) | |
274 | continue; | |
275 | ||
276 | // If the used value is defined by an instruction I2 for which | |
277 | // IGNORE (I2) is true, the caller guarantees that I2 will occur | |
278 | // before change.insn (). Otherwise, make sure that the use occurs | |
279 | // after the definition. | |
280 | insn_info *insn = set->insn (); | |
281 | if (!ignore (insn)) | |
282 | move_range = move_later_than (move_range, insn); | |
283 | ||
284 | // Search forward for the first unfiltered definition that follows SET. | |
285 | // | |
286 | // We don't need to consider the uses of these definitions, since | |
287 | // if IGNORE (D->insn ()) is true for some definition D, the caller | |
288 | // is guarantees that either | |
289 | // | |
290 | // - D will be removed, and thus its uses will be removed; or | |
291 | // - D will occur after USE, and thus D's uses will also occur | |
292 | // after USE. | |
293 | // | |
294 | // This is purely a simplification: we could also process D's uses, | |
295 | // but we don't need to. | |
296 | def_info *def; | |
297 | def = first_def_ignoring (set->next_def (), ignore_clobbers::NO, | |
298 | ignore); | |
299 | if (def) | |
300 | move_range = move_earlier_than (move_range, def->insn ()); | |
301 | ||
302 | // If USE uses a hard register, take any call clobbers into account too. | |
303 | // SET will necessarily occur after any previous call clobber, so we | |
304 | // only need to check for later clobbers. | |
305 | unsigned int regno = use->regno (); | |
306 | if (!HARD_REGISTER_NUM_P (regno)) | |
307 | continue; | |
308 | ||
309 | ebb_info *ebb = use->ebb (); | |
310 | for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ()) | |
311 | { | |
312 | if (!call_group->clobbers (use->resource ())) | |
313 | continue; | |
314 | ||
315 | if (!move_range) | |
316 | return false; | |
317 | ||
318 | insn_info *insn = next_call_clobbers_ignoring (*call_group, | |
319 | use->insn (), ignore); | |
320 | if (insn) | |
321 | move_range = move_earlier_than (move_range, insn); | |
322 | } | |
323 | } | |
324 | ||
325 | // Make sure that we don't move loads into an earlier basic block. | |
326 | // | |
327 | // ??? It would be good to relax this for loads that can be safely | |
328 | // speculated. | |
329 | if (use_info *use = memory_access (uses)) | |
330 | move_range = move_later_than (move_range, use->bb ()->head_insn ()); | |
331 | ||
332 | return bool (move_range); | |
333 | } | |
334 | ||
335 | } |