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 : 138515542 : move_later_than (insn_range_info range, insn_info *insn)
31 : : {
32 : 138515542 : 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 : 80820101 : move_earlier_than (insn_range_info range, insn_info *insn)
59 : : {
60 : 80820101 : insn_info *last = earlier_insn (range.last, insn->prev_nondebug_insn ());
61 : 80820101 : return { range.first, last };
62 : : }
63 : :
64 : : // Return true if it is possible to insert a new instruction after INSN.
65 : : inline bool
66 : 6 : can_insert_after (insn_info *insn)
67 : : {
68 : 6 : return (insn->is_bb_head ()
69 : 6 : || (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 : 31990251 : canonicalize_move_range (insn_range_info &move_range, insn_info *insn)
77 : : {
78 : 31990255 : while (move_range.first != insn && !can_insert_after (move_range.first))
79 : 4 : move_range.first = move_range.first->next_nondebug_insn ();
80 : 31990251 : while (move_range.last != insn && !can_insert_after (move_range.last))
81 : 0 : move_range.last = move_range.last->prev_nondebug_insn ();
82 : 31990251 : 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 : 1650641 : 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 : 1650641 : resource_info resource = full_register (regno);
109 : 1650641 : def_lookup dl = crtl->ssa->find_def (resource, insn);
110 : :
111 : 1650641 : def_info *prev = dl.last_def_of_prev_group ();
112 : 1650641 : ebb_info *ebb = insn->ebb ();
113 : 1650641 : 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 : 674829 : bb_info *bb = insn->bb ();
131 : : insn_info *limit;
132 : 1349658 : if (!bitmap_bit_p (DF_LR_IN (ebb->first_bb ()->cfg_bb ()), regno))
133 : 674829 : limit = ebb->phi_insn ();
134 : 0 : else if (bitmap_bit_p (DF_LR_IN (bb->cfg_bb ()), regno))
135 : : return false;
136 : : else
137 : 0 : limit = bb->head_insn ();
138 : 674829 : move_range = move_later_than (move_range, limit);
139 : : }
140 : : else
141 : : {
142 : : // Stop the instruction moving beyond the previous relevant access
143 : : // to REGNO.
144 : : access_info *prev_access
145 : 975812 : = last_access_ignoring (prev, ignore_clobbers::YES, ignore);
146 : 975812 : if (prev_access)
147 : 829014 : move_range = move_later_than (move_range, access_insn (prev_access));
148 : : }
149 : :
150 : : // Stop the instruction moving beyond the next relevant definition of REGNO.
151 : 1650641 : def_info *next = dl.matching_set_or_first_def_of_next_group ();
152 : 1650641 : next = first_def_ignoring (next, ignore_clobbers::YES, ignore);
153 : 1650641 : if (next)
154 : 1245403 : move_range = move_earlier_than (move_range, next->insn ());
155 : :
156 : 1650641 : 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 : 27359115 : restrict_movement_for_defs_ignoring (insn_range_info &move_range,
181 : : def_array defs, IgnorePredicate ignore)
182 : : {
183 : 68818816 : for (def_info *def : defs)
184 : : {
185 : : // Skip fresh defs that are being inserted, as these shouldn't
186 : : // constrain movement.
187 : 41459701 : if (def->is_temporary ())
188 : 0 : 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 : 41459701 : bool is_clobber = is_a<clobber_info *> (def);
196 : :
197 : : // Search back for the first unfiltered use or definition of the
198 : : // same resource.
199 : : access_info *access;
200 : 41459701 : access = prev_access_ignoring (def, ignore_clobbers (is_clobber),
201 : : ignore);
202 : 41459701 : if (access)
203 : 21752872 : move_range = move_later_than (move_range, 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 : 41459701 : access = next_access_ignoring (def, ignore_clobbers (is_clobber),
219 : : ignore);
220 : 41459701 : if (access)
221 : 30776775 : move_range = move_earlier_than (move_range, access_insn (access));
222 : :
223 : : // If DEF sets a hard register, take any call clobbers
224 : : // into account.
225 : 41459701 : unsigned int regno = def->regno ();
226 : 41459701 : if (!HARD_REGISTER_NUM_P (regno) || is_clobber)
227 : 31021718 : continue;
228 : :
229 : 10437983 : ebb_info *ebb = def->ebb ();
230 : 18673924 : for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ())
231 : : {
232 : 8235941 : if (!call_group->clobbers (def->resource ()))
233 : 597071 : continue;
234 : :
235 : : // Exit now if we've already failed, and if the splay accesses
236 : : // below would be wasted work.
237 : 7638870 : if (!move_range)
238 : 27359115 : return false;
239 : :
240 : : insn_info *insn;
241 : 7638870 : insn = prev_call_clobbers_ignoring (*call_group, def->insn (),
242 : : ignore);
243 : 7638870 : if (insn)
244 : 3468535 : move_range = move_later_than (move_range, insn);
245 : :
246 : 7638870 : insn = next_call_clobbers_ignoring (*call_group, def->insn (),
247 : : ignore);
248 : 7638870 : if (insn)
249 : 5257729 : move_range = move_earlier_than (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 : 27359115 : def_info *def = memory_access (defs);
256 : 27359115 : if (def && !def->is_temporary ())
257 : : {
258 : 7010176 : move_range = move_later_than (move_range, def->bb ()->head_insn ());
259 : 7010176 : move_range = move_earlier_than (move_range, def->bb ()->end_insn ());
260 : : }
261 : :
262 : 27359115 : 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 : 28614204 : restrict_movement_for_uses_ignoring (insn_range_info &move_range,
269 : : use_array uses, IgnorePredicate ignore)
270 : : {
271 : 120212455 : for (const use_info *use : uses)
272 : : {
273 : : // Ignore uses of undefined values.
274 : 91605154 : set_info *set = use->def ();
275 : 91605154 : if (!set)
276 : 267 : 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 : 91604887 : if (use->is_in_debug_insn ())
285 : 2777424 : 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 : 88827463 : insn_info *insn = set->insn ();
292 : 88827463 : if (!ignore (insn))
293 : 88827463 : move_range = move_later_than (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 : 118743158 : def = first_def_ignoring (set->next_def (), ignore_clobbers::NO,
309 : : ignore);
310 : 88827463 : if (def)
311 : 29228357 : move_range = move_earlier_than (move_range, 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 : 88827463 : unsigned int regno = use->regno ();
317 : 88827463 : if (!HARD_REGISTER_NUM_P (regno))
318 : 67140099 : continue;
319 : :
320 : 21687364 : ebb_info *ebb = use->ebb ();
321 : 41320742 : for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ())
322 : : {
323 : 19640281 : if (!call_group->clobbers (use->resource ()))
324 : 6469753 : continue;
325 : :
326 : 13170528 : if (!move_range)
327 : 28614204 : return false;
328 : :
329 : 13163625 : insn_info *insn = next_call_clobbers_ignoring (*call_group,
330 : : use->insn (), ignore);
331 : 13163625 : if (insn)
332 : 7301661 : move_range = move_earlier_than (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 : 28607301 : if (use_info *use = memory_access (uses))
341 : 12972158 : move_range = move_later_than (move_range, use->bb ()->head_insn ());
342 : :
343 : 28607301 : return bool (move_range);
344 : : }
345 : :
346 : : }
|
