1 // RTL SSA utilities relating to instruction movement -*- C++ -*-
2 // Copyright (C) 2020-2023 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 // 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
106 def_info *prev = dl.last_def_of_prev_group ();
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.
146 def_info *next = dl.matching_set_or_first_def_of_next_group ();
147 next = first_def_ignoring (next, ignore_clobbers::YES, ignore);
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 }