1 // Access-related utilities for RTL SSA -*- 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 a referene to the whole of register REGNO.
24 full_register (unsigned int regno
)
26 return { GET_MODE (regno_reg_rtx
[regno
]), regno
};
29 // Return true if sorted array ACCESSES includes an access to hard registers.
31 accesses_include_hard_registers (const access_array
&accesses
)
33 return accesses
.size () && HARD_REGISTER_NUM_P (accesses
.front ()->regno ());
36 // Return true if ACCESSES includes a reference to a non-fixed hard register.
38 accesses_include_nonfixed_hard_registers (access_array accesses
)
40 for (access_info
*access
: accesses
)
42 if (!HARD_REGISTER_NUM_P (access
->regno ()))
44 if (!fixed_regs
[access
->regno ()])
50 // Return true if sorted array ACCESSES includes an access to memory.
52 accesses_include_memory (const access_array
&accesses
)
54 return accesses
.size () && accesses
.back ()->is_mem ();
57 // If sorted array ACCESSES includes an access to memory, return the access,
58 // otherwise return null.
61 memory_access (T accesses
) -> decltype (accesses
[0])
63 if (accesses
.size () && accesses
.back ()->is_mem ())
64 return accesses
.back ();
68 // If ACCESSES has a memory access, drop it. Otherwise, return ACCESSES
72 drop_memory_access (T accesses
)
74 if (!memory_access (accesses
))
77 access_array
arr (accesses
);
78 return T (arr
.begin (), accesses
.size () - 1);
81 // Filter ACCESSES to return an access_array of only those accesses that
82 // satisfy PREDICATE. Alocate the new array above WATERMARK.
83 template<typename T
, typename FilterPredicate
>
85 filter_accesses (obstack_watermark
&watermark
,
87 FilterPredicate predicate
)
89 access_array_builder
builder (watermark
);
90 builder
.reserve (accesses
.size ());
91 for (auto access
: accesses
)
92 if (predicate (access
))
93 builder
.quick_push (access
);
94 return T (builder
.finish ());
97 // Given an array of ACCESSES, remove any access with regno REGNO.
98 // Allocate the new access array above WM.
101 remove_regno_access (obstack_watermark
&watermark
,
102 T accesses
, unsigned int regno
)
104 using Access
= decltype (accesses
[0]);
105 auto pred
= [regno
](Access a
) { return a
->regno () != regno
; };
106 return filter_accesses (watermark
, accesses
, pred
);
109 // As above, but additionally check that we actually did remove an access.
112 check_remove_regno_access (obstack_watermark
&watermark
,
113 T accesses
, unsigned regno
)
115 auto orig_size
= accesses
.size ();
116 auto result
= remove_regno_access (watermark
, accesses
, regno
);
117 gcc_assert (result
.size () < orig_size
);
121 // If sorted array ACCESSES includes a reference to REGNO, return the
122 // access, otherwise return null.
125 find_access (T accesses
, unsigned int regno
) -> decltype (accesses
[0])
127 unsigned int start
= 0;
128 unsigned int end
= accesses
.size ();
131 unsigned int mid
= (start
+ end
) / 2;
132 unsigned int found
= accesses
[mid
]->regno ();
134 return accesses
[mid
];
143 // If sorted array ACCESSES includes a reference to REGNO, return the
144 // index of the access, otherwise return -1.
146 find_access_index (access_array accesses
, unsigned int regno
)
148 unsigned int start
= 0;
149 unsigned int end
= accesses
.size ();
152 unsigned int mid
= (start
+ end
) / 2;
153 unsigned int found
= accesses
[mid
]->regno ();
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.
166 inline const set_info
*
167 set_with_nondebug_insn_uses (const access_info
*access
)
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
);
175 // A non-const version of the above.
177 set_with_nondebug_insn_uses (access_info
*access
)
179 if (access
->is_set_with_nondebug_insn_uses ())
180 return static_cast<set_info
*> (access
);
184 // ACCESS is known to be associated with an instruction rather than
185 // a phi node. Return which instruction that is.
187 access_insn (const access_info
*access
)
189 // In release builds this function reduces to a single pointer reference.
190 if (auto *def
= dyn_cast
<const def_info
*> (access
))
192 return as_a
<const use_info
*> (access
)->insn ();
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.
197 inline const set_info
*
198 access_value (const access_info
*access
)
203 if (auto *use
= dyn_cast
<const use_info
*> (access
))
206 return dyn_cast
<const set_info
*> (access
);
209 // A non-const version of the above.
211 access_value (access_info
*access
)
213 auto *const_access
= const_cast<const access_info
*> (access
);
214 return const_cast<set_info
*> (access_value (const_access
));
217 // If ACCESS is a degenerate phi, return the set_info that defines its input,
218 // otherwise return ACCESS itself.
221 look_through_degenerate_phi (const T
*access
)
223 if (auto *phi
= dyn_cast
<const phi_info
*> (access
))
224 if (phi
->is_degenerate ())
225 return phi
->input_value (0);
229 // A non-const version of the above.
232 look_through_degenerate_phi (T
*access
)
234 auto *const_access
= const_cast<const T
*> (access
);
235 return const_cast<T
*> (look_through_degenerate_phi (const_access
));
238 // If CLOBBER is in a group, return the first clobber in the group,
239 // otherwise return CLOBBER itself.
240 inline clobber_info
*
241 first_clobber_in_group (clobber_info
*clobber
)
243 if (clobber
->is_in_group ())
244 return clobber
->group ()->first_clobber ();
248 // If CLOBBER is in a group, return the last clobber in the group,
249 // otherwise return CLOBBER itself.
250 inline clobber_info
*
251 last_clobber_in_group (clobber_info
*clobber
)
253 if (clobber
->is_in_group ())
254 return clobber
->group ()->last_clobber ();
258 // If DEF is a clobber in a group, return the containing group,
259 // otherwise return DEF.
261 clobber_group_or_single_def (def_info
*def
)
263 if (auto *clobber
= dyn_cast
<clobber_info
*> (def
))
264 if (clobber
->is_in_group ())
265 return clobber
->group ();
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.
273 first_def (def_node
*node
)
275 return node
->first_def ();
278 // Likewise for something that is either a node or a single definition.
280 first_def (def_mux mux
)
282 return mux
.first_def ();
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.
289 last_def (def_node
*node
)
291 if (auto *group
= dyn_cast
<clobber_group
*> (node
))
292 return group
->last_clobber ();
293 return node
->first_def ();
296 // Likewise for something that is either a node or a single definition.
298 last_def (def_mux mux
)
300 return mux
.last_def ();
303 // If INSN's definitions contain a single set, return that set, otherwise
306 single_set_info (insn_info
*insn
)
308 set_info
*set
= nullptr;
309 for (auto def
: insn
->defs ())
310 if (auto this_set
= dyn_cast
<set_info
*> (def
))
319 int lookup_use (splay_tree
<use_info
*> &, insn_info
*);
320 int lookup_def (def_splay_tree
&, insn_info
*);
321 int lookup_clobber (clobber_tree
&, insn_info
*);
322 int lookup_call_clobbers (insn_call_clobbers_tree
&, insn_info
*);
324 // Search backwards from immediately before INSN for the first "relevant"
325 // instruction recorded in TREE. IGNORE is an object that provides the same
326 // interface as ignore_nothing; it defines which insns are "relevant"
327 // and which should be ignored.
329 // Return null if no such relevant instruction exists.
330 template<typename IgnorePredicates
>
332 prev_call_clobbers (insn_call_clobbers_tree
&tree
, insn_info
*insn
,
333 IgnorePredicates ignore
)
338 int comparison
= lookup_call_clobbers (tree
, insn
);
339 while (comparison
<= 0 || ignore
.should_ignore_insn (tree
->insn ()))
341 if (!tree
.splay_prev_node ())
346 return tree
->insn ();
349 // Search forwards from immediately after INSN for the first "relevant"
350 // instruction recorded in TREE. IGNORE is an object that provides the
351 // same interface as ignore_nothing; it defines which insns are "relevant"
352 // and which should be ignored.
354 // Return null if no such relevant instruction exists.
355 template<typename IgnorePredicates
>
357 next_call_clobbers (insn_call_clobbers_tree
&tree
, insn_info
*insn
,
358 IgnorePredicates ignore
)
363 int comparison
= lookup_call_clobbers (tree
, insn
);
364 while (comparison
>= 0 || ignore
.should_ignore_insn (tree
->insn ()))
366 if (!tree
.splay_next_node ())
371 return tree
->insn ();
374 // Search forwards from immediately after INSN for the first instruction
375 // recorded in TREE. Return null if no such instruction exists.
377 next_call_clobbers (insn_call_clobbers_tree
&tree
, insn_info
*insn
)
379 return next_call_clobbers (tree
, insn
, ignore_nothing ());
382 // If ACCESS is a set, return the first "relevant" use of ACCESS by a
383 // nondebug insn. IGNORE is an object that provides the same interface
384 // as ignore_nothing; it defines which accesses and insns are "relevant"
385 // and which should be ignored.
387 // Return null if ACCESS is not a set or if no such relevant use exists.
388 template<typename IgnorePredicates
>
390 first_nondebug_insn_use (const access_info
*access
, IgnorePredicates ignore
)
392 if (const set_info
*set
= set_with_nondebug_insn_uses (access
))
394 // Written this way to emphasize to the compiler that first_use
395 // must be nonnull in this situation.
396 use_info
*use
= set
->first_use ();
399 if (!ignore
.should_ignore_insn (use
->insn ()))
401 use
= use
->next_nondebug_insn_use ();
408 // If ACCESS is a set, return the last "relevant" use of ACCESS by a
409 // nondebug insn. IGNORE is an object that provides the same interface
410 // as ignore_nothing; it defines which accesses and insns are "relevant"
411 // and which should be ignored.
413 // Return null if ACCESS is not a set or if no such relevant use exists.
414 template<typename IgnorePredicates
>
416 last_nondebug_insn_use (const access_info
*access
, IgnorePredicates ignore
)
418 if (const set_info
*set
= set_with_nondebug_insn_uses (access
))
420 // Written this way to emphasize to the compiler that
421 // last_nondebug_insn_use must be nonnull in this situation.
422 use_info
*use
= set
->last_nondebug_insn_use ();
425 if (!ignore
.should_ignore_insn (use
->insn ()))
427 use
= use
->prev_use ();
434 // If DEF is null, return null.
436 // Otherwise, search backwards for an access to DEF->resource (), starting at
437 // the end of DEF's live range. Ignore clobbers if IGNORE_CLOBBERS_SETTING
438 // is YES, otherwise treat them like any other access. Also ignore any
439 // accesses and insns that IGNORE says should be ignored, where IGNORE
440 // is an object that provides the same interface as ignore_nothing.
442 // Thus if DEF is a set that is used by nondebug insns, the first access
443 // that the function considers is the last such use of the set. Otherwise,
444 // the first access that the function considers is DEF itself.
446 // Return the access found, or null if there is no access that meets
449 // Note that this function does not consider separately-recorded call clobbers,
450 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
451 template<typename IgnorePredicates
>
453 last_access (def_info
*def
, ignore_clobbers ignore_clobbers_setting
,
454 IgnorePredicates ignore
)
458 auto *clobber
= dyn_cast
<clobber_info
*> (def
);
459 if (clobber
&& ignore_clobbers_setting
== ignore_clobbers::YES
)
460 def
= first_clobber_in_group (clobber
);
461 else if (!ignore
.should_ignore_def (def
))
463 if (use_info
*use
= last_nondebug_insn_use (def
, ignore
))
465 if (!ignore
.should_ignore_insn (def
->insn ()))
468 def
= def
->prev_def ();
473 // Search backwards for an access to DEF->resource (), starting
474 // immediately before the point at which DEF occurs. Ignore clobbers
475 // if IGNORE_CLOBBERS_SETTING is YES, otherwise treat them like any other
476 // access. Also ignore any accesses and insns that IGNORE says should be
477 // ignored, where IGNORE is an object that provides the same interface as
480 // Thus if DEF->insn () uses DEF->resource (), that use is the first access
481 // that the function considers, since an instruction's uses occur strictly
482 // before its definitions.
484 // Note that this function does not consider separately-recorded call clobbers,
485 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
486 template<typename IgnorePredicates
>
488 prev_access (def_info
*def
, ignore_clobbers ignore_clobbers_setting
,
489 IgnorePredicates ignore
)
491 return last_access (def
->prev_def (), ignore_clobbers_setting
, ignore
);
494 // If DEF is null, return null.
496 // Otherwise, search forwards for an access to DEF->resource (),
497 // starting at DEF itself. Ignore clobbers if IGNORE_CLOBBERS_SETTING
498 // is YES, otherwise treat them like any other access. Also ignore any
499 // accesses and insns that IGNORE says should be ignored, where IGNORE
500 // is an object that provides the same interface as ignore_nothing.
502 // Return the definition found, or null if there is no access that meets
505 // Note that this function does not consider separately-recorded call clobbers,
506 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
507 template<typename IgnorePredicates
>
509 first_access (def_info
*def
, ignore_clobbers ignore_clobbers_setting
,
510 IgnorePredicates ignore
)
514 auto *clobber
= dyn_cast
<clobber_info
*> (def
);
515 if (clobber
&& ignore_clobbers_setting
== ignore_clobbers::YES
)
516 def
= last_clobber_in_group (clobber
);
517 else if (!ignore
.should_ignore_def (def
))
519 if (!ignore
.should_ignore_insn (def
->insn ()))
521 if (use_info
*use
= first_nondebug_insn_use (def
, ignore
))
524 def
= def
->next_def ();
529 // Search forwards for the next access to DEF->resource (),
530 // starting immediately after DEF's instruction. Ignore clobbers if
531 // IGNORE_CLOBBERS_SETTING is YES, otherwise treat them like any other access.
532 // Also ignore any accesses and insns that IGNORE says should be ignored,
533 // where IGNORE is an object that provides the same interface as
536 // Thus if DEF is a set with uses by nondebug insns, the first access that the
537 // function considers is the first such use of the set. Otherwise, the first
538 // access that the function considers is the definition after DEF.
540 // Return the access found, or null if there is no access that meets the
543 // Note that this function does not consider separately-recorded call clobbers,
544 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
545 template<typename IgnorePredicates
>
547 next_access (def_info
*def
, ignore_clobbers ignore_clobbers_setting
,
548 IgnorePredicates ignore
)
550 if (!ignore
.should_ignore_def (def
))
551 if (use_info
*use
= first_nondebug_insn_use (def
, ignore
))
554 return first_access (def
->next_def (), ignore_clobbers_setting
, ignore
);
557 // Return true if ACCESS1 should before ACCESS2 in an access_array.
559 compare_access_infos (const access_info
*access1
, const access_info
*access2
)
561 gcc_checking_assert (access1
== access2
562 || access1
->regno () != access2
->regno ());
563 return access1
->regno () < access2
->regno ();
566 // Sort [BEGIN, END) into ascending regno order. The sequence must have
567 // at most one access to a given a regno.
569 sort_accesses (access_info
**begin
, access_info
**end
)
571 auto count
= end
- begin
;
577 gcc_checking_assert (begin
[0]->regno () != begin
[1]->regno ());
578 if (begin
[0]->regno () > begin
[1]->regno ())
579 std::swap (begin
[0], begin
[1]);
583 std::sort (begin
, end
, compare_access_infos
);
586 // Sort the accesses in CONTAINER, which contains pointers to access_infos.
589 sort_accesses (T
&container
)
591 return sort_accesses (container
.begin (), container
.end ());
594 // The underlying non-template implementation of merge_access_arrays.
595 access_array
merge_access_arrays_base (obstack_watermark
&, access_array
,
597 // Merge access arrays ACCESSES1 and ACCESSES2, including the allocation
598 // in the area governed by WATERMARK. Return an invalid access_array if
599 // ACCESSES1 and ACCESSES2 contain conflicting accesses to the same resource.
601 // T can be an access_array, a def_array or a use_array.
604 merge_access_arrays (obstack_watermark
&watermark
, T accesses1
, T accesses2
)
606 return T (merge_access_arrays_base (watermark
, accesses1
, accesses2
));
609 // The underlying non-template implementation of insert_access.
610 access_array
insert_access_base (obstack_watermark
&, access_info
*,
613 // Return a new access_array that contains the result of inserting ACCESS1
614 // into sorted access array ACCESSES2. Allocate the returned array in the
615 // area governed by WATERMARK. Return an invalid access_array if ACCESSES2
616 // contains a conflicting access to the same resource as ACCESS1.
618 // T can be an access_array, a def_array or a use_array.
621 insert_access (obstack_watermark
&watermark
,
622 typename
T::value_type access1
, T accesses2
)
624 return T (insert_access_base (watermark
, access1
, accesses2
));
627 // Return a copy of USES that drops any use of DEF.
628 use_array
remove_uses_of_def (obstack_watermark
&, use_array uses
,
631 // The underlying non-template implementation of remove_note_accesses.
632 access_array
remove_note_accesses_base (obstack_watermark
&, access_array
);
634 // If ACCESSES contains accesses that only occur in notes, return a new
635 // array without such accesses, allocating it in the area governed by
636 // WATERMARK. Return ACCESSES itself otherwise.
638 // T can be an access_array, a def_array or a use_array.
641 remove_note_accesses (obstack_watermark
&watermark
, T accesses
)
643 return T (remove_note_accesses_base (watermark
, accesses
));
646 // Return true if ACCESSES1 and ACCESSES2 have at least one resource in common.
647 bool accesses_reference_same_resource (access_array accesses1
,
648 access_array accesses2
);
650 // Return true if INSN clobbers the value of any resources in ACCESSES.
651 bool insn_clobbers_resources (insn_info
*insn
, access_array accesses
);