]>
Commit | Line | Data |
---|---|---|
73b75827 | 1 | // Access-related utilities for RTL SSA -*- C++ -*- |
99dee823 | 2 | // Copyright (C) 2020-2021 Free Software Foundation, Inc. |
73b75827 RS |
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 | { | |
00bad763 | 26 | return { GET_MODE (regno_reg_rtx[regno]), regno }; |
73b75827 RS |
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 | } |