Line data Source code
1 : // RTL SSA utilities relating to instruction movement -*- C++ -*-
2 : // Copyright (C) 2020-2026 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 268198810 : move_later_than (insn_range_info range, insn_info *insn)
31 : {
32 268198810 : return { later_insn (range.first, 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 (range.first, 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 (range.last, 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 171262387 : move_earlier_than (insn_range_info range, insn_info *insn)
59 : {
60 171262387 : insn_info *last = earlier_insn (range.last, insn->prev_nondebug_insn ());
61 171262387 : return { range.first, last };
62 : }
63 :
64 : // Return true if it is possible to insert a new instruction after INSN.
65 : inline bool
66 16597002 : can_insert_after (insn_info *insn)
67 : {
68 16597002 : return (insn->is_bb_head ()
69 16597002 : || (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 82827714 : canonicalize_move_range (insn_range_info &move_range, insn_info *insn)
77 : {
78 83943721 : while (move_range.first != insn && !can_insert_after (move_range.first))
79 1116011 : if (auto *next = move_range.first->next_nondebug_insn ())
80 1116007 : move_range.first = next;
81 : else
82 : {
83 : // Invalidate the range. prev_nondebug_insn is always nonnull
84 : // if next_nondebug_insn is null.
85 4 : move_range.last = move_range.first->prev_nondebug_insn ();
86 4 : return false;
87 : }
88 83308686 : while (move_range.last != insn && !can_insert_after (move_range.last))
89 480976 : if (auto *prev = move_range.last->prev_nondebug_insn ())
90 480976 : move_range.last = prev;
91 : else
92 : {
93 : // Invalidate the range. next_nondebug_insn is always nonnull
94 : // if prev_nondebug_insn is null.
95 0 : move_range.first = move_range.last->next_nondebug_insn ();
96 0 : return false;
97 : }
98 82827710 : return bool (move_range);
99 : }
100 :
101 : // Try to restrict movement range MOVE_RANGE of INSN so that it can set
102 : // or clobber REGNO.
103 : //
104 : // IGNORE is an object that provides the same interface as ignore_nothing.
105 : // Assume that if:
106 : //
107 : // - an instruction I2 contains another access A to REGNO; and
108 : // - IGNORE says that I2 should be ignored
109 : //
110 : // then either:
111 : //
112 : // - A will be removed; or
113 : // - something will ensure that the new definition of REGNO does not
114 : // interfere with A, without this having to be enforced by I1's move range.
115 : //
116 : // If IGNORE says that a definition D of REGNO should be ignored, assume that
117 : // the new definition of REGNO will not conflict with D.
118 : //
119 : // Return true on success, otherwise leave MOVE_RANGE in an invalid state.
120 : //
121 : // This function only works correctly for instructions that remain within
122 : // the same extended basic block.
123 : template<typename IgnorePredicates>
124 : bool
125 1966660 : restrict_movement_for_dead_range (insn_range_info &move_range,
126 : unsigned int regno, insn_info *insn,
127 : IgnorePredicates ignore)
128 : {
129 : // Find a definition at or neighboring INSN.
130 1966660 : resource_info resource = full_register (regno);
131 1966660 : def_lookup dl = crtl->ssa->find_def (resource, insn);
132 :
133 1966660 : def_info *prev = dl.last_def_of_prev_group ();
134 1966660 : ebb_info *ebb = insn->ebb ();
135 1966660 : if (!prev || prev->ebb () != ebb)
136 : {
137 : // REGNO is not defined or used in EBB before INSN, but it
138 : // might be live on entry. To keep complexity under control,
139 : // handle only these cases:
140 : //
141 : // - If the register is not live on entry to EBB, the register is
142 : // free from the start of EBB to the first definition in EBB.
143 : //
144 : // - Otherwise, if the register is live on entry to BB, refuse
145 : // to allocate the register. We could in principle try to move
146 : // the instruction to later blocks in the EBB, but it's rarely
147 : // worth the effort, and could lead to linear complexity.
148 : //
149 : // - Otherwise, don't allow INSN to move earlier than its current
150 : // block. Again, we could in principle look backwards to find where
151 : // REGNO dies, but it's rarely worth the effort.
152 776089 : bb_info *bb = insn->bb ();
153 : insn_info *limit;
154 1552178 : if (!bitmap_bit_p (DF_LR_IN (ebb->first_bb ()->cfg_bb ()), regno))
155 776089 : limit = ebb->phi_insn ();
156 0 : else if (bitmap_bit_p (DF_LR_IN (bb->cfg_bb ()), regno))
157 : return false;
158 : else
159 0 : limit = bb->head_insn ();
160 776089 : move_range = move_later_than (move_range, limit);
161 : }
162 : else
163 : {
164 : // Stop the instruction moving beyond the previous relevant access
165 : // to REGNO.
166 1190571 : access_info *prev_access = last_access (prev, ignore_clobbers::YES,
167 : ignore);
168 1190571 : if (prev_access)
169 1026745 : move_range = move_later_than (move_range, access_insn (prev_access));
170 : }
171 :
172 : // Stop the instruction moving beyond the next relevant use or definition
173 : // of REGNO.
174 1966660 : def_info *next = dl.matching_set_or_first_def_of_next_group ();
175 1966660 : access_info *next_access = first_access (next, ignore_clobbers::YES, ignore);
176 1966660 : if (next_access)
177 1513127 : move_range = move_earlier_than (move_range, access_insn (next_access));
178 :
179 1966660 : return canonicalize_move_range (move_range, insn);
180 : }
181 :
182 : // Try to restrict movement range MOVE_RANGE so that it is possible for the
183 : // instruction being moved ("instruction I1") to perform all the definitions
184 : // in DEFS while still preserving dependencies between those definitions
185 : // and surrounding instructions.
186 : //
187 : // IGNORE is an object that provides the same interface as ignore_nothing.
188 : // Assume that if:
189 : //
190 : // - DEFS contains a definition D of resource R;
191 : // - an instruction I2 contains another access A to R; and
192 : // - IGNORE says that I2 should be ignored
193 : //
194 : // then either:
195 : //
196 : // - A will be removed; or
197 : // - something will ensure that D and A maintain their current order,
198 : // without this having to be enforced by I1's move range.
199 : //
200 : // Assume the same thing about a definition D and all uses of D if IGNORE
201 : // says that D should be ignored.
202 : //
203 : // Return true on success, otherwise leave MOVE_RANGE in an invalid state.
204 : //
205 : // This function only works correctly for instructions that remain within
206 : // the same extended basic block.
207 : template<typename IgnorePredicates>
208 : bool
209 59681740 : restrict_movement_for_defs (insn_range_info &move_range, def_array defs,
210 : IgnorePredicates ignore)
211 : {
212 197268113 : for (def_info *def : defs)
213 : {
214 : // Skip fresh defs that are being inserted, as these shouldn't
215 : // constrain movement.
216 78199925 : if (def->is_temporary ())
217 0 : continue;
218 :
219 : // If the definition is a clobber, we can move it with respect
220 : // to other clobbers.
221 : //
222 : // ??? We could also do this if a definition and all its uses
223 : // are being moved at once.
224 78199925 : bool is_clobber = is_a<clobber_info *> (def);
225 :
226 : // Search back for the first relevant use or definition of the
227 : // same resource.
228 : access_info *access;
229 78199925 : access = prev_access (def, ignore_clobbers (is_clobber), ignore);
230 78199925 : if (access)
231 48865175 : move_range = move_later_than (move_range, access_insn (access));
232 :
233 : // Search forward for the next relevant use or definition of the
234 : // same resource.
235 78199925 : access = next_access (def, ignore_clobbers (is_clobber), ignore);
236 78199925 : if (access)
237 65502949 : move_range = move_earlier_than (move_range, access_insn (access));
238 :
239 : // If DEF sets a hard register, take any call clobbers
240 : // into account.
241 78199925 : unsigned int regno = def->regno ();
242 78199925 : if (!HARD_REGISTER_NUM_P (regno) || is_clobber)
243 50749595 : continue;
244 :
245 27450330 : ebb_info *ebb = def->ebb ();
246 43860890 : for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ())
247 : {
248 16705852 : if (!call_group->clobbers (def->resource ()))
249 1738017 : continue;
250 :
251 : // Exit now if we've already failed, and if the splay accesses
252 : // below would be wasted work.
253 14967835 : if (!move_range)
254 59681740 : return false;
255 :
256 : insn_info *insn;
257 14672543 : insn = prev_call_clobbers (*call_group, def->insn (), ignore);
258 14672543 : if (insn)
259 7371580 : move_range = move_later_than (move_range, insn);
260 :
261 14672543 : insn = next_call_clobbers (*call_group, def->insn (), ignore);
262 14672543 : if (insn)
263 10246955 : move_range = move_earlier_than (move_range, insn);
264 : }
265 : }
266 :
267 : // Make sure that we don't move stores between basic blocks, since we
268 : // don't have enough information to tell whether it's safe.
269 59386448 : def_info *def = memory_access (defs);
270 59386448 : if (def && !def->is_temporary ())
271 : {
272 14166328 : move_range = move_later_than (move_range, def->bb ()->head_insn ());
273 14166328 : move_range = move_earlier_than (move_range, def->bb ()->end_insn ());
274 : }
275 :
276 59386448 : return bool (move_range);
277 : }
278 :
279 : // Like restrict_movement_for_defs, but for the uses in USES.
280 : template<typename IgnorePredicates>
281 : bool
282 61647836 : restrict_movement_for_uses (insn_range_info &move_range, use_array uses,
283 : IgnorePredicates ignore)
284 : {
285 280766781 : for (const use_info *use : uses)
286 : {
287 : // Ignore uses of undefined values.
288 157644523 : set_info *set = use->def ();
289 157644523 : if (!set)
290 1284330 : continue;
291 :
292 : // Ignore uses by debug instructions. Debug instructions are
293 : // never supposed to move, and uses by debug instructions are
294 : // never supposed to be transferred elsewhere, so we know that
295 : // the caller must be changing the uses on the debug instruction
296 : // and checking whether all new uses are available at the debug
297 : // instruction's original location.
298 156360193 : if (use->is_in_debug_insn ())
299 3466254 : continue;
300 :
301 : // If the used value is defined by an ignored instruction I2,
302 : // the caller guarantees that I2 will occur before change.insn ()
303 : // and that its value will still be available at change.insn ().
304 : // Otherwise, make sure that the use occurs after the definition.
305 152893939 : insn_info *insn = set->insn ();
306 45443218 : if (!ignore.should_ignore_def (set)
307 152893939 : && !ignore.should_ignore_insn (insn))
308 152893939 : move_range = move_later_than (move_range, insn);
309 :
310 : // Search forward after SET's live range for the first relevant
311 : // use or definition of the same resource.
312 : access_info *access;
313 218457211 : access = first_access (set->next_def (), ignore_clobbers::NO, ignore);
314 152893939 : if (access)
315 64855430 : move_range = move_earlier_than (move_range, access_insn (access));
316 :
317 : // If USE uses a hard register, take any call clobbers into account too.
318 : // SET will necessarily occur after any previous call clobber, so we
319 : // only need to check for later clobbers.
320 152893939 : unsigned int regno = use->regno ();
321 152893939 : if (!HARD_REGISTER_NUM_P (regno))
322 100874638 : continue;
323 :
324 52019301 : ebb_info *ebb = use->ebb ();
325 87617448 : for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ())
326 : {
327 35771561 : if (!call_group->clobbers (use->resource ()))
328 15215221 : continue;
329 :
330 20556340 : if (!move_range)
331 61647836 : return false;
332 :
333 20382926 : insn_info *insn = next_call_clobbers (*call_group, use->insn (),
334 : ignore);
335 20382926 : if (insn)
336 11362116 : move_range = move_earlier_than (move_range, insn);
337 : }
338 : }
339 :
340 : // Make sure that we don't move loads into an earlier basic block.
341 : //
342 : // ??? It would be good to relax this for loads that can be safely
343 : // speculated.
344 61474422 : if (use_info *use = memory_access (uses))
345 24622634 : move_range = move_later_than (move_range, use->bb ()->head_insn ());
346 :
347 61474422 : return bool (move_range);
348 : }
349 :
350 : }
|
