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 instruction
325 // recorded in TREE, ignoring any instruction I for which IGNORE (I) is true.
326 // Return null if no such instruction exists.
327 template<typename IgnorePredicate
>
329 prev_call_clobbers_ignoring (insn_call_clobbers_tree
&tree
, insn_info
*insn
,
330 IgnorePredicate ignore
)
335 int comparison
= lookup_call_clobbers (tree
, insn
);
336 while (comparison
<= 0 || ignore (tree
->insn ()))
338 if (!tree
.splay_prev_node ())
343 return tree
->insn ();
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.
349 template<typename IgnorePredicate
>
351 next_call_clobbers_ignoring (insn_call_clobbers_tree
&tree
, insn_info
*insn
,
352 IgnorePredicate ignore
)
357 int comparison
= lookup_call_clobbers (tree
, insn
);
358 while (comparison
>= 0 || ignore (tree
->insn ()))
360 if (!tree
.splay_next_node ())
365 return tree
->insn ();
368 // Search forwards from immediately after INSN for the first instruction
369 // recorded in TREE. Return null if no such instruction exists.
371 next_call_clobbers (insn_call_clobbers_tree
&tree
, insn_info
*insn
)
373 auto ignore
= [](const insn_info
*) { return false; };
374 return next_call_clobbers_ignoring (tree
, insn
, ignore
);
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.
380 template<typename IgnorePredicate
>
382 first_nondebug_insn_use_ignoring (const access_info
*access
,
383 IgnorePredicate ignore
)
385 if (const set_info
*set
= set_with_nondebug_insn_uses (access
))
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 ();
392 if (!ignore (use
->insn ()))
394 use
= use
->next_nondebug_insn_use ();
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
404 template<typename IgnorePredicate
>
406 last_nondebug_insn_use_ignoring (const access_info
*access
,
407 IgnorePredicate ignore
)
409 if (const set_info
*set
= set_with_nondebug_insn_uses (access
))
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 ();
416 if (!ignore (use
->insn ()))
418 use
= use
->prev_use ();
425 // If DEF is null, return null.
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.
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.
436 // Return the access found, or null if there is no access that meets
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.
441 template<typename IgnorePredicate
>
443 last_access_ignoring (def_info
*def
, ignore_clobbers ignore_clobbers_setting
,
444 IgnorePredicate ignore
)
448 auto *clobber
= dyn_cast
<clobber_info
*> (def
);
449 if (clobber
&& ignore_clobbers_setting
== ignore_clobbers::YES
)
450 def
= first_clobber_in_group (clobber
);
453 if (use_info
*use
= last_nondebug_insn_use_ignoring (def
, ignore
))
456 insn_info
*insn
= def
->insn ();
460 def
= def
->prev_def ();
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))
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.
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.
477 template<typename IgnorePredicate
>
479 prev_access_ignoring (def_info
*def
, ignore_clobbers ignore_clobbers_setting
,
480 IgnorePredicate ignore
)
482 return last_access_ignoring (def
->prev_def (), ignore_clobbers_setting
,
486 // If DEF is null, return null.
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.
493 // Return the definition found, or null if there is no access that meets
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.
498 template<typename IgnorePredicate
>
500 first_def_ignoring (def_info
*def
, ignore_clobbers ignore_clobbers_setting
,
501 IgnorePredicate ignore
)
505 auto *clobber
= dyn_cast
<clobber_info
*> (def
);
506 if (clobber
&& ignore_clobbers_setting
== ignore_clobbers::YES
)
507 def
= last_clobber_in_group (clobber
);
508 else if (!ignore (def
->insn ()))
511 def
= def
->next_def ();
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.
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.
525 // Return the access found, or null if there is no access that meets the
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.
530 template<typename IgnorePredicate
>
532 next_access_ignoring (def_info
*def
, ignore_clobbers ignore_clobbers_setting
,
533 IgnorePredicate ignore
)
535 if (use_info
*use
= first_nondebug_insn_use_ignoring (def
, ignore
))
538 return first_def_ignoring (def
->next_def (), ignore_clobbers_setting
,
542 // Return true if ACCESS1 should before ACCESS2 in an access_array.
544 compare_access_infos (const access_info
*access1
, const access_info
*access2
)
546 gcc_checking_assert (access1
== access2
547 || access1
->regno () != access2
->regno ());
548 return access1
->regno () < access2
->regno ();
551 // Sort [BEGIN, END) into ascending regno order. The sequence must have
552 // at most one access to a given a regno.
554 sort_accesses (access_info
**begin
, access_info
**end
)
556 auto count
= end
- begin
;
562 gcc_checking_assert (begin
[0]->regno () != begin
[1]->regno ());
563 if (begin
[0]->regno () > begin
[1]->regno ())
564 std::swap (begin
[0], begin
[1]);
568 std::sort (begin
, end
, compare_access_infos
);
571 // Sort the accesses in CONTAINER, which contains pointers to access_infos.
574 sort_accesses (T
&container
)
576 return sort_accesses (container
.begin (), container
.end ());
579 // The underlying non-template implementation of merge_access_arrays.
580 access_array
merge_access_arrays_base (obstack_watermark
&, 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.
586 // T can be an access_array, a def_array or a use_array.
589 merge_access_arrays (obstack_watermark
&watermark
, T accesses1
, T accesses2
)
591 return T (merge_access_arrays_base (watermark
, accesses1
, accesses2
));
594 // The underlying non-template implementation of insert_access.
595 access_array
insert_access_base (obstack_watermark
&, access_info
*,
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.
603 // T can be an access_array, a def_array or a use_array.
606 insert_access (obstack_watermark
&watermark
,
607 typename
T::value_type access1
, T accesses2
)
609 return T (insert_access_base (watermark
, access1
, accesses2
));
612 // Return a copy of USES that drops any use of DEF.
613 use_array
remove_uses_of_def (obstack_watermark
&, use_array uses
,
616 // The underlying non-template implementation of remove_note_accesses.
617 access_array
remove_note_accesses_base (obstack_watermark
&, access_array
);
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.
623 // T can be an access_array, a def_array or a use_array.
626 remove_note_accesses (obstack_watermark
&watermark
, T accesses
)
628 return T (remove_note_accesses_base (watermark
, accesses
));
631 // Return true if ACCESSES1 and ACCESSES2 have at least one resource in common.
632 bool accesses_reference_same_resource (access_array accesses1
,
633 access_array accesses2
);
635 // Return true if INSN clobbers the value of any resources in ACCESSES.
636 bool insn_clobbers_resources (insn_info
*insn
, access_array accesses
);