1 // Access-related utilities for RTL SSA -*- C++ -*-
2 // Copyright (C) 2020-2023 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 a referene to the whole of register REGNO.
23 inline resource_info
24 full_register (unsigned int regno)
25 {
26 return { GET_MODE (regno_reg_rtx[regno]), regno };
27 }
28
29 // Return true if sorted array ACCESSES includes an access to hard registers.
30 inline bool
31 accesses_include_hard_registers (const access_array &accesses)
32 {
33 return accesses.size () && HARD_REGISTER_NUM_P (accesses.front ()->regno ());
34 }
35
36 // Return true if sorted array ACCESSES includes an access to memory.
37 inline bool
38 accesses_include_memory (const access_array &accesses)
39 {
40 return accesses.size () && accesses.back ()->is_mem ();
41 }
42
43 // If sorted array ACCESSES includes an access to memory, return the access,
44 // otherwise return null.
45 template<typename T>
46 inline auto
47 memory_access (T accesses) -> decltype (accesses[0])
48 {
49 if (accesses.size () && accesses.back ()->is_mem ())
50 return accesses.back ();
51 return nullptr;
52 }
53
54 // If sorted array ACCESSES includes a reference to REGNO, return the
55 // access, otherwise return null.
56 template<typename T>
57 inline auto
58 find_access (T accesses, unsigned int regno) -> decltype (accesses[0])
59 {
60 unsigned int start = 0;
61 unsigned int end = accesses.size ();
62 while (start < end)
63 {
64 unsigned int mid = (start + end) / 2;
65 unsigned int found = accesses[mid]->regno ();
66 if (found == regno)
67 return accesses[mid];
68 if (found < regno)
69 start = mid + 1;
70 else
71 end = mid;
72 }
73 return nullptr;
74 }
75
76 // If sorted array ACCESSES includes a reference to REGNO, return the
77 // index of the access, otherwise return -1.
78 inline int
79 find_access_index (access_array accesses, unsigned int regno)
80 {
81 unsigned int start = 0;
82 unsigned int end = accesses.size ();
83 while (start < end)
84 {
85 unsigned int mid = (start + end) / 2;
86 unsigned int found = accesses[mid]->regno ();
87 if (found == regno)
88 return mid;
89 if (found < regno)
90 start = mid + 1;
91 else
92 end = mid;
93 }
94 return -1;
95 }
96
97 // If ACCESS is a set whose result is used by at least one instruction,
98 // return the access as a set_info, otherwise return null.
99 inline const set_info *
100 set_with_nondebug_insn_uses (const access_info *access)
101 {
102 if (access->is_set_with_nondebug_insn_uses ())
103 // No need for as_a; this test is just as definitive.
104 return static_cast<const set_info *> (access);
105 return nullptr;
106 }
107
108 // A non-const version of the above.
109 inline set_info *
110 set_with_nondebug_insn_uses (access_info *access)
111 {
112 if (access->is_set_with_nondebug_insn_uses ())
113 return static_cast<set_info *> (access);
114 return nullptr;
115 }
116
117 // Return true if SET is the only set of SET->resource () and if it
118 // dominates all uses (excluding uses of SET->resource () at points
119 // where SET->resource () is always undefined).
120 inline bool
121 is_single_dominating_def (const set_info *set)
122 {
123 return set->is_first_def () && set->is_last_def ();
124 }
125
126 // SET is known to be available on entry to BB. Return true if it is
127 // also available on exit from BB. (The value might or might not be live.)
128 inline bool
129 remains_available_on_exit (const set_info *set, bb_info *bb)
130 {
131 return (set->is_last_def ()
132 || *set->next_def ()->insn () > *bb->end_insn ());
133 }
134
135 // ACCESS is known to be associated with an instruction rather than
136 // a phi node. Return which instruction that is.
137 inline insn_info *
138 access_insn (const access_info *access)
139 {
140 // In release builds this function reduces to a single pointer reference.
141 if (auto *def = dyn_cast<const def_info *> (access))
142 return def->insn ();
143 return as_a<const use_info *> (access)->insn ();
144 }
145
146 // If ACCESS records a use, return the value that it uses. If ACCESS records
147 // a set, return that set. If ACCESS records a clobber, return null.
148 inline const set_info *
149 access_value (const access_info *access)
150 {
151 if (!access)
152 return nullptr;
153
154 if (auto *use = dyn_cast<const use_info *> (access))
155 return use->def ();
156
157 return dyn_cast<const set_info *> (access);
158 }
159
160 // A non-const version of the above.
161 inline set_info *
162 access_value (access_info *access)
163 {
164 auto *const_access = const_cast<const access_info *> (access);
165 return const_cast<set_info *> (access_value (const_access));
166 }
167
168 // If ACCESS is a degenerate phi, return the set_info that defines its input,
169 // otherwise return ACCESS itself.
170 template<typename T>
171 inline const T *
172 look_through_degenerate_phi (const T *access)
173 {
174 if (auto *phi = dyn_cast<const phi_info *> (access))
175 if (phi->is_degenerate ())
176 return phi->input_value (0);
177 return access;
178 }
179
180 // A non-const version of the above.
181 template<typename T>
182 inline T *
183 look_through_degenerate_phi (T *access)
184 {
185 auto *const_access = const_cast<const T *> (access);
186 return const_cast<T *> (look_through_degenerate_phi (const_access));
187 }
188
189 // If CLOBBER is in a group, return the first clobber in the group,
190 // otherwise return CLOBBER itself.
191 inline clobber_info *
192 first_clobber_in_group (clobber_info *clobber)
193 {
194 if (clobber->is_in_group ())
195 return clobber->group ()->first_clobber ();
196 return clobber;
197 }
198
199 // If CLOBBER is in a group, return the last clobber in the group,
200 // otherwise return CLOBBER itself.
201 inline clobber_info *
202 last_clobber_in_group (clobber_info *clobber)
203 {
204 if (clobber->is_in_group ())
205 return clobber->group ()->last_clobber ();
206 return clobber;
207 }
208
209 // If DEF is a clobber in a group, return the containing group,
210 // otherwise return DEF.
211 inline def_mux
212 clobber_group_or_single_def (def_info *def)
213 {
214 if (auto *clobber = dyn_cast<clobber_info *> (def))
215 if (clobber->is_in_group ())
216 return clobber->group ();
217 return def;
218 }
219
220 // Return the first definition associated with NODE. If NODE holds
221 // a single set, the result is that set. If NODE holds a clobber_group,
222 // the result is the first clobber in the group.
223 inline def_info *
224 first_def (def_node *node)
225 {
226 return node->first_def ();
227 }
228
229 // Likewise for something that is either a node or a single definition.
230 inline def_info *
231 first_def (def_mux mux)
232 {
233 return mux.first_def ();
234 }
235
236 // Return the last definition associated with NODE. If NODE holds
237 // a single set, the result is that set. If NODE holds a clobber_group,
238 // the result is the last clobber in the group.
239 inline def_info *
240 last_def (def_node *node)
241 {
242 if (auto *group = dyn_cast<clobber_group *> (node))
243 return group->last_clobber ();
244 return node->first_def ();
245 }
246
247 // Likewise for something that is either a node or a single definition.
248 inline def_info *
249 last_def (def_mux mux)
250 {
251 return mux.last_def ();
252 }
253
254 int lookup_use (splay_tree<use_info *> &, insn_info *);
255 int lookup_def (def_splay_tree &, insn_info *);
256 int lookup_clobber (clobber_tree &, insn_info *);
257 int lookup_call_clobbers (insn_call_clobbers_tree &, insn_info *);
258
259 // Search backwards from immediately before INSN for the first instruction
260 // recorded in TREE, ignoring any instruction I for which IGNORE (I) is true.
261 // Return null if no such instruction exists.
262 template<typename IgnorePredicate>
263 insn_info *
264 prev_call_clobbers_ignoring (insn_call_clobbers_tree &tree, insn_info *insn,
265 IgnorePredicate ignore)
266 {
267 if (!tree)
268 return nullptr;
269
270 int comparison = lookup_call_clobbers (tree, insn);
271 while (comparison <= 0 || ignore (tree->insn ()))
272 {
273 if (!tree.splay_prev_node ())
274 return nullptr;
275
276 comparison = 1;
277 }
278 return tree->insn ();
279 }
280
281 // Search forwards from immediately after INSN for the first instruction
282 // recorded in TREE, ignoring any instruction I for which IGNORE (I) is true.
283 // Return null if no such instruction exists.
284 template<typename IgnorePredicate>
285 insn_info *
286 next_call_clobbers_ignoring (insn_call_clobbers_tree &tree, insn_info *insn,
287 IgnorePredicate ignore)
288 {
289 if (!tree)
290 return nullptr;
291
292 int comparison = lookup_call_clobbers (tree, insn);
293 while (comparison >= 0 || ignore (tree->insn ()))
294 {
295 if (!tree.splay_next_node ())
296 return nullptr;
297
298 comparison = -1;
299 }
300 return tree->insn ();
301 }
302
303 // If ACCESS is a set, return the first use of ACCESS by a nondebug insn I
304 // for which IGNORE (I) is false. Return null if ACCESS is not a set or if
305 // no such use exists.
306 template<typename IgnorePredicate>
307 inline use_info *
308 first_nondebug_insn_use_ignoring (const access_info *access,
309 IgnorePredicate ignore)
310 {
311 if (const set_info *set = set_with_nondebug_insn_uses (access))
312 {
313 // Written this way to emphasize to the compiler that first_use
314 // must be nonnull in this situation.
315 use_info *use = set->first_use ();
316 do
317 {
318 if (!ignore (use->insn ()))
319 return use;
320 use = use->next_nondebug_insn_use ();
321 }
322 while (use);
323 }
324 return nullptr;
325 }
326
327 // If ACCESS is a set, return the last use of ACCESS by a nondebug insn I for
328 // which IGNORE (I) is false. Return null if ACCESS is not a set or if no
329 // such use exists.
330 template<typename IgnorePredicate>
331 inline use_info *
332 last_nondebug_insn_use_ignoring (const access_info *access,
333 IgnorePredicate ignore)
334 {
335 if (const set_info *set = set_with_nondebug_insn_uses (access))
336 {
337 // Written this way to emphasize to the compiler that
338 // last_nondebug_insn_use must be nonnull in this situation.
339 use_info *use = set->last_nondebug_insn_use ();
340 do
341 {
342 if (!ignore (use->insn ()))
343 return use;
344 use = use->prev_use ();
345 }
346 while (use);
347 }
348 return nullptr;
349 }
350
351 // If DEF is null, return null.
352 //
353 // Otherwise, search backwards for an access to DEF->resource (), starting at
354 // the end of DEF's live range. Ignore clobbers if IGNORE_CLOBBERS_SETTING
355 // is YES, otherwise treat them like any other access. Also ignore any
356 // access A for which IGNORE (access_insn (A)) is true.
357 //
358 // Thus if DEF is a set that is used by nondebug insns, the first access
359 // that the function considers is the last such use of the set. Otherwise,
360 // the first access that the function considers is DEF itself.
361 //
362 // Return the access found, or null if there is no access that meets
363 // the criteria.
364 //
365 // Note that this function does not consider separately-recorded call clobbers,
366 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
367 template<typename IgnorePredicate>
368 access_info *
369 last_access_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting,
370 IgnorePredicate ignore)
371 {
372 while (def)
373 {
374 auto *clobber = dyn_cast<clobber_info *> (def);
375 if (clobber && ignore_clobbers_setting == ignore_clobbers::YES)
376 def = first_clobber_in_group (clobber);
377 else
378 {
379 if (use_info *use = last_nondebug_insn_use_ignoring (def, ignore))
380 return use;
381
382 insn_info *insn = def->insn ();
383 if (!ignore (insn))
384 return def;
385 }
386 def = def->prev_def ();
387 }
388 return nullptr;
389 }
390
391 // Search backwards for an access to DEF->resource (), starting
392 // immediately before the point at which DEF occurs. Ignore clobbers
393 // if IGNORE_CLOBBERS_SETTING is YES, otherwise treat them like any other
394 // access. Also ignore any access A for which IGNORE (access_insn (A))
395 // is true.
396 //
397 // Thus if DEF->insn () uses DEF->resource (), that use is the first access
398 // that the function considers, since an instruction's uses occur strictly
399 // before its definitions.
400 //
401 // Note that this function does not consider separately-recorded call clobbers,
402 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
403 template<typename IgnorePredicate>
404 inline access_info *
405 prev_access_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting,
406 IgnorePredicate ignore)
407 {
408 return last_access_ignoring (def->prev_def (), ignore_clobbers_setting,
409 ignore);
410 }
411
412 // If DEF is null, return null.
413 //
414 // Otherwise, search forwards for a definition of DEF->resource (),
415 // starting at DEF itself. Ignore clobbers if IGNORE_CLOBBERS_SETTING
416 // is YES, otherwise treat them like any other access. Also ignore any
417 // definition D for which IGNORE (D->insn ()) is true.
418 //
419 // Return the definition found, or null if there is no access that meets
420 // the criteria.
421 //
422 // Note that this function does not consider separately-recorded call clobbers,
423 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
424 template<typename IgnorePredicate>
425 def_info *
426 first_def_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting,
427 IgnorePredicate ignore)
428 {
429 while (def)
430 {
431 auto *clobber = dyn_cast<clobber_info *> (def);
432 if (clobber && ignore_clobbers_setting == ignore_clobbers::YES)
433 def = last_clobber_in_group (clobber);
434 else if (!ignore (def->insn ()))
435 return def;
436
437 def = def->next_def ();
438 }
439 return nullptr;
440 }
441
442 // Search forwards for the next access to DEF->resource (),
443 // starting immediately after DEF's instruction. Ignore clobbers if
444 // IGNORE_CLOBBERS_SETTING is YES, otherwise treat them like any other access.
445 // Also ignore any access A for which IGNORE (access_insn (A)) is true;
446 // in this context, ignoring a set includes ignoring all uses of the set.
447 //
448 // Thus if DEF is a set with uses by nondebug insns, the first access that the
449 // function considers is the first such use of the set.
450 //
451 // Return the access found, or null if there is no access that meets the
452 // criteria.
453 //
454 // Note that this function does not consider separately-recorded call clobbers,
455 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
456 template<typename IgnorePredicate>
457 access_info *
458 next_access_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting,
459 IgnorePredicate ignore)
460 {
461 if (use_info *use = first_nondebug_insn_use_ignoring (def, ignore))
462 return use;
463
464 return first_def_ignoring (def->next_def (), ignore_clobbers_setting,
465 ignore);
466 }
467
468 // Return true if ACCESS1 should before ACCESS2 in an access_array.
469 inline bool
470 compare_access_infos (const access_info *access1, const access_info *access2)
471 {
472 gcc_checking_assert (access1 == access2
473 || access1->regno () != access2->regno ());
474 return access1->regno () < access2->regno ();
475 }
476
477 // Sort [BEGIN, END) into ascending regno order. The sequence must have
478 // at most one access to a given a regno.
479 inline void
480 sort_accesses (access_info **begin, access_info **end)
481 {
482 auto count = end - begin;
483 if (count <= 1)
484 return;
485
486 if (count == 2)
487 {
488 gcc_checking_assert (begin[0]->regno () != begin[1]->regno ());
489 if (begin[0]->regno () > begin[1]->regno ())
490 std::swap (begin[0], begin[1]);
491 return;
492 }
493
494 std::sort (begin, end, compare_access_infos);
495 }
496
497 // Sort the accesses in CONTAINER, which contains pointers to access_infos.
498 template<typename T>
499 inline void
500 sort_accesses (T &container)
501 {
502 return sort_accesses (container.begin (), container.end ());
503 }
504
505 // The underlying non-template implementation of merge_access_arrays.
506 access_array merge_access_arrays_base (obstack_watermark &, access_array,
507 access_array);
508 // Merge access arrays ACCESSES1 and ACCESSES2, including the allocation
509 // in the area governed by WATERMARK. Return an invalid access_array if
510 // ACCESSES1 and ACCESSES2 contain conflicting accesses to the same resource.
511 //
512 // T can be an access_array, a def_array or a use_array.
513 template<typename T>
514 inline T
515 merge_access_arrays (obstack_watermark &watermark, T accesses1, T accesses2)
516 {
517 return T (merge_access_arrays_base (watermark, accesses1, accesses2));
518 }
519
520 // The underlying non-template implementation of insert_access.
521 access_array insert_access_base (obstack_watermark &, access_info *,
522 access_array);
523
524 // Return a new access_array that contains the result of inserting ACCESS1
525 // into sorted access array ACCESSES2. Allocate the returned array in the
526 // area governed by WATERMARK. Return an invalid access_array if ACCESSES2
527 // contains a conflicting access to the same resource as ACCESS1.
528 //
529 // T can be an access_array, a def_array or a use_array.
530 template<typename T>
531 inline T
532 insert_access (obstack_watermark &watermark,
533 typename T::value_type access1, T accesses2)
534 {
535 return T (insert_access_base (watermark, access1, accesses2));
536 }
537
538 // The underlying non-template implementation of remove_note_accesses.
539 access_array remove_note_accesses_base (obstack_watermark &, access_array);
540
541 // If ACCESSES contains accesses that only occur in notes, return a new
542 // array without such accesses, allocating it in the area governed by
543 // WATERMARK. Return ACCESSES itself otherwise.
544 //
545 // T can be an access_array, a def_array or a use_array.
546 template<typename T>
547 inline T
548 remove_note_accesses (obstack_watermark &watermark, T accesses)
549 {
550 return T (remove_note_accesses_base (watermark, accesses));
551 }
552
553 }