Branch data Line data Source code
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 : 229690812 : move_later_than (insn_range_info range, insn_info *insn)
31 : : {
32 : 229690812 : 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 : 149274564 : move_earlier_than (insn_range_info range, insn_info *insn)
59 : : {
60 : 149274564 : insn_info *last = earlier_insn (range.last, insn->prev_nondebug_insn ());
61 : 149274564 : return { range.first, last };
62 : : }
63 : :
64 : : // Return true if it is possible to insert a new instruction after INSN.
65 : : inline bool
66 : 12025058 : can_insert_after (insn_info *insn)
67 : : {
68 : 12025058 : return (insn->is_bb_head ()
69 : 12025058 : || (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 : 67366830 : canonicalize_move_range (insn_range_info &move_range, insn_info *insn)
77 : : {
78 : 67367023 : while (move_range.first != insn && !can_insert_after (move_range.first))
79 : 197 : if (auto *next = move_range.first->next_nondebug_insn ())
80 : 193 : 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 : 67802140 : while (move_range.last != insn && !can_insert_after (move_range.last))
89 : 435314 : if (auto *prev = move_range.last->prev_nondebug_insn ())
90 : 435314 : 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 : 67366826 : 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 : 1843626 : 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 : 1843626 : resource_info resource = full_register (regno);
131 : 1843626 : def_lookup dl = crtl->ssa->find_def (resource, insn);
132 : :
133 : 1843626 : def_info *prev = dl.last_def_of_prev_group ();
134 : 1843626 : ebb_info *ebb = insn->ebb ();
135 : 1843626 : 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 : 747023 : bb_info *bb = insn->bb ();
153 : : insn_info *limit;
154 : 1494046 : if (!bitmap_bit_p (DF_LR_IN (ebb->first_bb ()->cfg_bb ()), regno))
155 : 747023 : 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 : 747023 : 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 : 1096603 : access_info *prev_access = last_access (prev, ignore_clobbers::YES,
167 : : ignore);
168 : 1096603 : if (prev_access)
169 : 940812 : 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 : 1843626 : def_info *next = dl.matching_set_or_first_def_of_next_group ();
175 : 1843626 : access_info *next_access = first_access (next, ignore_clobbers::YES, ignore);
176 : 1843626 : if (next_access)
177 : 1404077 : move_range = move_earlier_than (move_range, access_insn (next_access));
178 : :
179 : 1843626 : 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 : 52172704 : restrict_movement_for_defs (insn_range_info &move_range, def_array defs,
210 : : IgnorePredicates ignore)
211 : : {
212 : 118700475 : for (def_info *def : defs)
213 : : {
214 : : // Skip fresh defs that are being inserted, as these shouldn't
215 : : // constrain movement.
216 : 66638792 : 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 : 66638792 : 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 : 66638792 : access = prev_access (def, ignore_clobbers (is_clobber), ignore);
230 : 66638792 : if (access)
231 : 41347201 : 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 : 66638792 : access = next_access (def, ignore_clobbers (is_clobber), ignore);
236 : 66638792 : if (access)
237 : 55213050 : 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 : 66638792 : unsigned int regno = def->regno ();
242 : 66638792 : if (!HARD_REGISTER_NUM_P (regno) || is_clobber)
243 : 45821892 : continue;
244 : :
245 : 20816900 : ebb_info *ebb = def->ebb ();
246 : 34551694 : for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ())
247 : : {
248 : 13845815 : if (!call_group->clobbers (def->resource ()))
249 : 1649119 : continue;
250 : :
251 : : // Exit now if we've already failed, and if the splay accesses
252 : : // below would be wasted work.
253 : 12196696 : if (!move_range)
254 : 52172704 : return false;
255 : :
256 : : insn_info *insn;
257 : 12085675 : insn = prev_call_clobbers (*call_group, def->insn (), ignore);
258 : 12085675 : if (insn)
259 : 5924763 : move_range = move_later_than (move_range, insn);
260 : :
261 : 12085675 : insn = next_call_clobbers (*call_group, def->insn (), ignore);
262 : 12085675 : if (insn)
263 : 8585698 : 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 : 52061683 : def_info *def = memory_access (defs);
270 : 52061683 : if (def && !def->is_temporary ())
271 : : {
272 : 13578125 : move_range = move_later_than (move_range, def->bb ()->head_insn ());
273 : 13578125 : move_range = move_earlier_than (move_range, def->bb ()->end_insn ());
274 : : }
275 : :
276 : 52061683 : 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 : 53985973 : restrict_movement_for_uses (insn_range_info &move_range, use_array uses,
283 : : IgnorePredicates ignore)
284 : : {
285 : 193831350 : for (const use_info *use : uses)
286 : : {
287 : : // Ignore uses of undefined values.
288 : 139992371 : set_info *set = use->def ();
289 : 139992371 : if (!set)
290 : 1330287 : 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 : 138662084 : if (use->is_in_debug_insn ())
299 : 2997670 : 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 : 135664414 : insn_info *insn = set->insn ();
306 : 43396801 : if (!ignore.should_ignore_def (set)
307 : 135664414 : && !ignore.should_ignore_insn (insn))
308 : 135664414 : 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 : 192589114 : access = first_access (set->next_def (), ignore_clobbers::NO, ignore);
314 : 135664414 : if (access)
315 : 56094780 : 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 : 135664414 : unsigned int regno = use->regno ();
321 : 135664414 : if (!HARD_REGISTER_NUM_P (regno))
322 : 88975604 : continue;
323 : :
324 : 46688810 : ebb_info *ebb = use->ebb ();
325 : 79851733 : for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ())
326 : : {
327 : 33309917 : if (!call_group->clobbers (use->resource ()))
328 : 14529566 : continue;
329 : :
330 : 18780351 : if (!move_range)
331 : 53985973 : return false;
332 : :
333 : 18633357 : insn_info *insn = next_call_clobbers (*call_group, use->insn (),
334 : : ignore);
335 : 18633357 : if (insn)
336 : 10867517 : 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 : 53838979 : if (use_info *use = memory_access (uses))
345 : 21457666 : move_range = move_later_than (move_range, use->bb ()->head_insn ());
346 : :
347 : 53838979 : return bool (move_range);
348 : : }
349 : :
350 : : }
|
