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