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
20namespace 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.
24bool 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.)
29inline insn_range_info
30move_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.)
38inline insn_range_info
39move_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.)
48inline insn_range_info
49move_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.)
57inline insn_range_info
58move_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.
65inline bool
66can_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.
75inline bool
76canonicalize_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.
101template<typename IgnorePredicate>
102bool
103restrict_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.
178template<typename IgnorePredicate>
179bool
180restrict_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.
266template<typename IgnorePredicate>
267bool
268restrict_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

source code of gcc/rtl-ssa/movement.h