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

source code of gcc/rtl-ssa/access-utils.h