1 // RTL SSA utilities relating to instruction movement -*- C++ -*-
2 // Copyright (C) 2020-2024 Free Software Foundation, Inc.
4 // This file is part of GCC.
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
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
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/>.
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
*);
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 move_later_than (insn_range_info range
, insn_info
*insn
)
32 return { later_insn (range
.first
, insn
), range
.last
};
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
)
41 insn_info
*first
= later_insn (range
.first
, insn
->prev_nondebug_insn ());
42 return { first
, range
.last
};
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
)
51 return { range
.first
, earlier_insn (range
.last
, insn
) };
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 move_earlier_than (insn_range_info range
, insn_info
*insn
)
60 insn_info
*last
= earlier_insn (range
.last
, insn
->prev_nondebug_insn ());
61 return { range
.first
, last
};
64 // Return true if it is possible to insert a new instruction after INSN.
66 can_insert_after (insn_info
*insn
)
68 return (insn
->is_bb_head ()
69 || (insn
->is_real () && !control_flow_insn_p (insn
->rtl ())));
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.
76 canonicalize_move_range (insn_range_info
&move_range
, insn_info
*insn
)
78 while (move_range
.first
!= insn
&& !can_insert_after (move_range
.first
))
79 move_range
.first
= move_range
.first
->next_nondebug_insn ();
80 while (move_range
.last
!= insn
&& !can_insert_after (move_range
.last
))
81 move_range
.last
= move_range
.last
->prev_nondebug_insn ();
82 return bool (move_range
);
85 // Try to restrict movement range MOVE_RANGE of INSN so that it can set
86 // or clobber REGNO. Assume that if:
88 // - an instruction I2 contains another access A to REGNO; and
89 // - IGNORE (I2) is true
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.
97 // Return true on success, otherwise leave MOVE_RANGE in an invalid state.
99 // This function only works correctly for instructions that remain within
100 // the same extended basic block.
101 template<typename IgnorePredicate
>
103 restrict_movement_for_dead_range (insn_range_info
&move_range
,
104 unsigned int regno
, insn_info
*insn
,
105 IgnorePredicate ignore
)
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
);
111 def_info
*prev
= dl
.last_def_of_prev_group ();
112 ebb_info
*ebb
= insn
->ebb ();
113 if (!prev
|| prev
->ebb () != ebb
)
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:
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.
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.
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 ();
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
))
137 limit
= bb
->head_insn ();
138 move_range
= move_later_than (move_range
, limit
);
142 // Stop the instruction moving beyond the previous relevant access
144 access_info
*prev_access
145 = last_access_ignoring (prev
, ignore_clobbers::YES
, ignore
);
147 move_range
= move_later_than (move_range
, access_insn (prev_access
));
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
);
154 move_range
= move_earlier_than (move_range
, next
->insn ());
156 return canonicalize_move_range (move_range
, insn
);
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:
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
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.
174 // Return true on success, otherwise leave MOVE_RANGE in an invalid state.
176 // This function only works correctly for instructions that remain within
177 // the same extended basic block.
178 template<typename IgnorePredicate
>
180 restrict_movement_for_defs_ignoring (insn_range_info
&move_range
,
181 def_array defs
, IgnorePredicate ignore
)
183 for (def_info
*def
: defs
)
185 // Skip fresh defs that are being inserted, as these shouldn't
186 // constrain movement.
187 if (def
->is_temporary ())
190 // If the definition is a clobber, we can move it with respect
191 // to other clobbers.
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
*> (def
);
197 // Search back for the first unfiltered use or definition of the
200 access
= prev_access_ignoring (def
, ignore_clobbers (is_clobber
),
203 move_range
= move_later_than (move_range
, access_insn (access
));
205 // Search forward for the first unfiltered use of DEF,
206 // or the first unfiltered definition that follows DEF.
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
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
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
),
221 move_range
= move_earlier_than (move_range
, access_insn (access
));
223 // If DEF sets a hard register, take any call clobbers
225 unsigned int regno
= def
->regno ();
226 if (!HARD_REGISTER_NUM_P (regno
) || is_clobber
)
229 ebb_info
*ebb
= def
->ebb ();
230 for (ebb_call_clobbers_info
*call_group
: ebb
->call_clobbers ())
232 if (!call_group
->clobbers (def
->resource ()))
235 // Exit now if we've already failed, and if the splay accesses
236 // below would be wasted work.
241 insn
= prev_call_clobbers_ignoring (*call_group
, def
->insn (),
244 move_range
= move_later_than (move_range
, insn
);
246 insn
= next_call_clobbers_ignoring (*call_group
, def
->insn (),
249 move_range
= move_earlier_than (move_range
, insn
);
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 (defs
);
256 if (def
&& !def
->is_temporary ())
258 move_range
= move_later_than (move_range
, def
->bb ()->head_insn ());
259 move_range
= move_earlier_than (move_range
, def
->bb ()->end_insn ());
262 return bool (move_range
);
265 // Like restrict_movement_for_defs_ignoring, but for the uses in USES.
266 template<typename IgnorePredicate
>
268 restrict_movement_for_uses_ignoring (insn_range_info
&move_range
,
269 use_array uses
, IgnorePredicate ignore
)
271 for (const use_info
*use
: uses
)
273 // Ignore uses of undefined values.
274 set_info
*set
= use
->def ();
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 ())
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 ();
293 move_range
= move_later_than (move_range
, insn
);
295 // Search forward for the first unfiltered definition that follows SET.
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
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
305 // This is purely a simplification: we could also process D's uses,
306 // but we don't need to.
308 def
= first_def_ignoring (set
->next_def (), ignore_clobbers::NO
,
311 move_range
= move_earlier_than (move_range
, def
->insn ());
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
))
320 ebb_info
*ebb
= use
->ebb ();
321 for (ebb_call_clobbers_info
*call_group
: ebb
->call_clobbers ())
323 if (!call_group
->clobbers (use
->resource ()))
329 insn_info
*insn
= next_call_clobbers_ignoring (*call_group
,
330 use
->insn (), ignore
);
332 move_range
= move_earlier_than (move_range
, insn
);
336 // Make sure that we don't move loads into an earlier basic block.
338 // ??? It would be good to relax this for loads that can be safely
340 if (use_info
*use
= memory_access (uses
))
341 move_range
= move_later_than (move_range
, use
->bb ()->head_insn ());
343 return bool (move_range
);