1 | // Function-related RTL SSA classes -*- 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 | |
20 | namespace rtl_ssa { |
21 | |
22 | // SSA-related information about a function. It contains three levels |
23 | // of information, each in reverse postorder: |
24 | // |
25 | // - a list of extended basic blocks |
26 | // - a list of basic blocks |
27 | // - a list of instructions |
28 | // |
29 | // It also maintains a list of definitions of memory, and a list of |
30 | // definitions of each register. |
31 | // |
32 | // See doc/rtl.texi for more details about the way this information |
33 | // is organized and how changes to it are made. |
34 | class function_info |
35 | { |
36 | // The default obstack alignment takes long double into account. |
37 | // Since we have no use for that here, and since we allocate many |
38 | // relatively small objects, it's better to specify an alignment |
39 | // explicitly. The allocation routines assert that the alignment |
40 | // is enough for the objects being allocated. |
41 | // |
42 | // Because various structures use pointer_mux, we need at least 2 bytes |
43 | // of alignment. |
44 | static const size_t obstack_alignment = sizeof (void *); |
45 | |
46 | public: |
47 | // Construct SSA form for function FN. |
48 | function_info (function *fn); |
49 | ~function_info (); |
50 | |
51 | // Return a list of all the extended basic blocks in the function, in reverse |
52 | // postorder. The list includes the entry and exit blocks. |
53 | iterator_range<ebb_iterator> ebbs () const; |
54 | |
55 | // Like ebbs (), but in the reverse order. |
56 | iterator_range<reverse_ebb_iterator> reverse_ebbs () const; |
57 | |
58 | // Return a list of all the basic blocks in the function, in reverse |
59 | // postorder. The list includes the entry and exit blocks. |
60 | iterator_range<bb_iterator> bbs () const; |
61 | |
62 | // Like bbs (), but in the reverse order. |
63 | iterator_range<reverse_bb_iterator> reverse_bbs () const; |
64 | |
65 | // Return the SSA information for the basic block with index INDEX. |
66 | bb_info *bb (unsigned int index) const { return m_bbs[index]; } |
67 | |
68 | // Return the SSA information for CFG_BB. |
69 | bb_info *bb (basic_block cfg_bb) const { return m_bbs[cfg_bb->index]; } |
70 | |
71 | // Create a temporary def. |
72 | set_info *create_set (obstack_watermark &watermark, |
73 | insn_info *insn, |
74 | resource_info resource); |
75 | |
76 | // Create a temporary use of SET as part of a change to INSN. |
77 | // SET can be a pre-existing definition or one that is being created |
78 | // as part of the same change group. |
79 | use_info *create_use (obstack_watermark &watermark, |
80 | insn_info *insn, |
81 | set_info *set); |
82 | |
83 | // Create a temporary insn with code INSN_CODE and pattern PAT. |
84 | insn_info *create_insn (obstack_watermark &watermark, |
85 | rtx_code insn_code, |
86 | rtx pat); |
87 | |
88 | // Return a list of all the instructions in the function, in reverse |
89 | // postorder. The list includes both real and artificial instructions. |
90 | // |
91 | // Iterations over the list will pick up any new instructions that are |
92 | // inserted after the iterator's current instruction. |
93 | iterator_range<any_insn_iterator> all_insns () const; |
94 | |
95 | // Like all_insns (), but in the reverse order. |
96 | // |
97 | // Iterations over the list will pick up any new instructions that are |
98 | // inserted before the iterator's current instruction. |
99 | iterator_range<reverse_any_insn_iterator> reverse_all_insns () const; |
100 | |
101 | // Like all_insns (), but without the debug instructions. |
102 | iterator_range<nondebug_insn_iterator> nondebug_insns () const; |
103 | |
104 | // Like reverse_all_insns (), but without the debug instructions. |
105 | iterator_range<reverse_nondebug_insn_iterator> |
106 | reverse_nondebug_insns () const; |
107 | |
108 | // Return the first and last instructions in insns (). |
109 | insn_info *first_insn () const { return m_first_insn; } |
110 | insn_info *last_insn () const { return m_last_insn; } |
111 | |
112 | // Return a list of all definitions of memory, in reverse postorder. |
113 | // This includes both real stores by instructions and artificial |
114 | // definitions by things like phi nodes. |
115 | iterator_range<def_iterator> mem_defs () const; |
116 | |
117 | // Return a list of all definitions of register REGNO, in reverse postorder. |
118 | // This includes both real stores by instructions and artificial |
119 | // definitions by things like phi nodes. |
120 | iterator_range<def_iterator> reg_defs (unsigned int regno) const; |
121 | |
122 | // Return true if SET is the only set of SET->resource () and if it |
123 | // dominates all uses (excluding uses of SET->resource () at points |
124 | // where SET->resource () is always undefined). |
125 | bool is_single_dominating_def (const set_info *set) const; |
126 | |
127 | // Check if all uses of register REGNO are either unconditionally undefined |
128 | // or use the same single dominating definition. Return the definition |
129 | // if so, otherwise return null. |
130 | set_info *single_dominating_def (unsigned int regno) const; |
131 | |
132 | // Look for a definition of RESOURCE at INSN. Return the result of the |
133 | // search as a def_lookup; see the comments there for more details. |
134 | def_lookup find_def (resource_info resource, insn_info *insn); |
135 | |
136 | // Return an RAII object that owns all temporary RTL SSA memory |
137 | // allocated during a change attempt. The object should remain in |
138 | // scope until the change has been aborted or successfully completed. |
139 | obstack_watermark new_change_attempt () { return &m_temp_obstack; } |
140 | |
141 | // SET and INSN belong to the same EBB, with SET occuring before INSN. |
142 | // Return true if SET is still available at INSN. |
143 | bool remains_available_at_insn (const set_info *set, insn_info *insn); |
144 | |
145 | // SET either occurs in BB or is known to be available on entry to BB. |
146 | // Return true if it is also available on exit from BB. (The value |
147 | // might or might not be live.) |
148 | bool remains_available_on_exit (const set_info *set, bb_info *bb); |
149 | |
150 | // Make a best attempt to check whether the values used by USES are |
151 | // available on entry to BB, without solving a full dataflow problem. |
152 | // If all the values are already live on entry to BB or can be made |
153 | // available there, return a use_array that describes the uses as |
154 | // if they occured at the start of BB. These uses are purely temporary, |
155 | // and will not become permanent unless applied using change_insns. |
156 | // |
157 | // If the operation fails, return an invalid use_array. |
158 | // |
159 | // WATERMARK is a watermark returned by new_change_attempt (). |
160 | // WILL_BE_DEBUG_USES is true if the returned use_array will be |
161 | // used only for debug instructions. |
162 | use_array make_uses_available (obstack_watermark &watermark, |
163 | use_array uses, bb_info *bb, |
164 | bool will_be_debug_uses); |
165 | |
166 | // If CHANGE doesn't already clobber REGNO, try to add such a clobber, |
167 | // limiting the movement range in order to make the clobber valid. |
168 | // When determining whether REGNO is live, ignore accesses made by an |
169 | // instruction I if IGNORE (I) is true. The caller then assumes the |
170 | // responsibility of ensuring that CHANGE and I are placed in a valid order. |
171 | // |
172 | // Return true on success. Leave CHANGE unmodified when returning false. |
173 | // |
174 | // WATERMARK is a watermark returned by new_change_attempt (). |
175 | template<typename IgnorePredicate> |
176 | bool add_regno_clobber (obstack_watermark &watermark, insn_change &change, |
177 | unsigned int regno, IgnorePredicate ignore); |
178 | |
179 | // Return true if change_insns will be able to perform the changes |
180 | // described by CHANGES. |
181 | bool verify_insn_changes (array_slice<insn_change *const> changes); |
182 | |
183 | // Perform all the changes in CHANGES, keeping the instructions in the |
184 | // order specified by the CHANGES array. On return, the SSA information |
185 | // remains up-to-date. The same is true for instruction-level DF |
186 | // information, although the block-level DF information might be |
187 | // marked dirty. |
188 | void change_insns (array_slice<insn_change *> changes); |
189 | |
190 | // Like change_insns, but for a single change CHANGE. |
191 | void change_insn (insn_change &change); |
192 | |
193 | // Given a use USE, re-parent it to get its def from NEW_DEF. |
194 | void reparent_use (use_info *use, set_info *new_def); |
195 | |
196 | // If the changes that have been made to instructions require updates |
197 | // to the CFG, perform those updates now. Return true if something changed. |
198 | // If it did: |
199 | // |
200 | // - The SSA information is now invalid and needs to be recomputed. |
201 | // |
202 | // - Dominance information is no longer available (in either direction). |
203 | // |
204 | // - The caller will need to call cleanup_cfg at some point. |
205 | // |
206 | // ??? We could probably update the SSA information for simple updates, |
207 | // but currently nothing would benefit. These late CFG changes are |
208 | // relatively rare anyway, since gimple optimisers should remove most |
209 | // unnecessary control flow. |
210 | bool perform_pending_updates (); |
211 | |
212 | // Print the contents of the function to PP. |
213 | void print (pretty_printer *pp) const; |
214 | |
215 | // Allocate an object of type T above the obstack watermark WM. |
216 | template<typename T, typename... Ts> |
217 | T *change_alloc (obstack_watermark &wm, Ts... args); |
218 | |
219 | private: |
220 | class bb_phi_info; |
221 | class build_info; |
222 | class bb_walker; |
223 | |
224 | // Return an RAII object that owns all objects allocated by |
225 | // allocate_temp during its lifetime. |
226 | obstack_watermark temp_watermark () { return &m_temp_obstack; } |
227 | |
228 | template<typename T, typename... Ts> |
229 | T *allocate (Ts... args); |
230 | |
231 | template<typename T, typename... Ts> |
232 | T *allocate_temp (Ts... args); |
233 | |
234 | access_array temp_access_array (access_array accesses); |
235 | |
236 | clobber_group *need_clobber_group (clobber_info *); |
237 | def_node *need_def_node (def_info *); |
238 | def_splay_tree need_def_splay_tree (def_info *); |
239 | |
240 | use_info *make_use_available (use_info *, bb_info *, bool); |
241 | def_array insert_temp_clobber (obstack_watermark &, insn_info *, |
242 | unsigned int, def_array); |
243 | |
244 | void insert_def_before (def_info *, def_info *); |
245 | void insert_def_after (def_info *, def_info *); |
246 | void remove_def_from_list (def_info *); |
247 | |
248 | void add_clobber (clobber_info *, clobber_group *); |
249 | void remove_clobber (clobber_info *, clobber_group *); |
250 | void prepend_clobber_to_group (clobber_info *, clobber_group *); |
251 | void append_clobber_to_group (clobber_info *, clobber_group *); |
252 | void merge_clobber_groups (clobber_info *, clobber_info *, |
253 | def_info *); |
254 | clobber_info *split_clobber_group (clobber_group *, insn_info *); |
255 | |
256 | void append_def (def_info *); |
257 | void add_def (def_info *); |
258 | void remove_def (def_info *); |
259 | |
260 | void need_use_splay_tree (set_info *); |
261 | |
262 | static void insert_use_before (use_info *, use_info *); |
263 | static void insert_use_after (use_info *, use_info *); |
264 | |
265 | void add_use (use_info *); |
266 | void remove_use (use_info *); |
267 | |
268 | insn_info::order_node *need_order_node (insn_info *); |
269 | |
270 | void add_insn_after (insn_info *, insn_info *); |
271 | void append_insn (insn_info *); |
272 | void remove_insn (insn_info *); |
273 | |
274 | insn_info *append_artificial_insn (bb_info *, rtx_insn * = nullptr); |
275 | |
276 | void start_insn_accesses (); |
277 | void finish_insn_accesses (insn_info *); |
278 | |
279 | use_info *create_reg_use (build_info &, insn_info *, resource_info); |
280 | void record_use (build_info &, insn_info *, rtx_obj_reference); |
281 | void record_call_clobbers (build_info &, insn_info *, rtx_call_insn *); |
282 | void record_def (build_info &, insn_info *, rtx_obj_reference); |
283 | void add_insn_to_block (build_info &, rtx_insn *); |
284 | |
285 | void add_reg_unused_notes (insn_info *); |
286 | |
287 | void add_live_out_use (bb_info *, set_info *); |
288 | set_info *live_out_value (bb_info *, set_info *); |
289 | |
290 | void append_phi (ebb_info *, phi_info *); |
291 | void remove_phi (phi_info *); |
292 | void delete_phi (phi_info *); |
293 | void replace_phi (phi_info *, set_info *); |
294 | phi_info *create_phi (ebb_info *, resource_info, access_info **, |
295 | unsigned int); |
296 | phi_info *create_degenerate_phi (ebb_info *, set_info *); |
297 | |
298 | bb_info *create_bb_info (basic_block); |
299 | void append_bb (bb_info *); |
300 | |
301 | void process_uses_of_deleted_def (set_info *); |
302 | insn_info *add_placeholder_after (insn_info *); |
303 | void possibly_queue_changes (insn_change &); |
304 | void finalize_new_accesses (insn_change &, insn_info *, |
305 | hash_set<def_info *> &); |
306 | void apply_changes_to_insn (insn_change &, |
307 | hash_set<def_info *> &); |
308 | |
309 | void init_function_data (); |
310 | void calculate_potential_phi_regs (build_info &); |
311 | void place_phis (build_info &); |
312 | void create_ebbs (build_info &); |
313 | void add_entry_block_defs (build_info &); |
314 | void calculate_ebb_live_in_for_debug (build_info &); |
315 | void add_phi_nodes (build_info &); |
316 | void add_artificial_accesses (build_info &, df_ref_flags); |
317 | void add_block_contents (build_info &); |
318 | void record_block_live_out (build_info &); |
319 | void start_block (build_info &, bb_info *); |
320 | void end_block (build_info &, bb_info *); |
321 | void populate_phi_inputs (build_info &); |
322 | void process_all_blocks (); |
323 | |
324 | void simplify_phi_setup (phi_info *, set_info **, bitmap); |
325 | void simplify_phi_propagate (phi_info *, set_info **, bitmap, bitmap); |
326 | void simplify_phis (); |
327 | |
328 | // The function that this object describes. |
329 | function *m_fn; |
330 | |
331 | // The lowest (negative) in-use artificial insn uid minus one. |
332 | int m_next_artificial_uid; |
333 | |
334 | // The highest in-use phi uid plus one. |
335 | unsigned int m_next_phi_uid; |
336 | |
337 | // The highest in-use register number plus one. |
338 | unsigned int m_num_regs; |
339 | |
340 | // M_DEFS[R] is the first definition of register R - 1 in a reverse |
341 | // postorder traversal of the function, or null if the function has |
342 | // no definition of R. Applying last () gives the last definition of R. |
343 | // |
344 | // M_DEFS[0] is for memory; MEM_REGNO + 1 == 0. |
345 | auto_vec<def_info *> m_defs; |
346 | |
347 | // M_BBS[BI] gives the SSA information about the block with index BI. |
348 | auto_vec<bb_info *> m_bbs; |
349 | |
350 | // An obstack used to allocate the main RTL SSA information. |
351 | obstack m_obstack; |
352 | |
353 | // An obstack used for temporary work, such as while building up a list |
354 | // of possible instruction changes. |
355 | obstack m_temp_obstack; |
356 | |
357 | // The start of each obstack, so that all memory in them can be freed. |
358 | char *m_obstack_start; |
359 | char *m_temp_obstack_start; |
360 | |
361 | // The entry and exit blocks. |
362 | bb_info *m_first_bb; |
363 | bb_info *m_last_bb; |
364 | |
365 | // The first and last instructions in a reverse postorder traversal |
366 | // of the function. |
367 | insn_info *m_first_insn; |
368 | insn_info *m_last_insn; |
369 | |
370 | // The last nondebug instruction in the list of instructions. |
371 | // This is only different from m_last_insn when building the initial |
372 | // SSA information; after that, the last instruction is always a |
373 | // BB end instruction. |
374 | insn_info *m_last_nondebug_insn; |
375 | |
376 | // Temporary working state when building up lists of definitions and uses. |
377 | // Keeping them around should reduce the number of unnecessary reallocations. |
378 | auto_vec<access_info *> m_temp_defs; |
379 | auto_vec<access_info *> m_temp_uses; |
380 | |
381 | // A list of phis that are no longer in use. Their uids are still unique |
382 | // and so can be recycled. |
383 | phi_info *m_free_phis; |
384 | |
385 | // A list of instructions that have been changed in ways that need |
386 | // further processing later, such as removing dead instructions or |
387 | // altering the CFG. |
388 | auto_vec<insn_info *> m_queued_insn_updates; |
389 | |
390 | // The INSN_UIDs of all instructions in M_QUEUED_INSN_UPDATES. |
391 | auto_bitmap m_queued_insn_update_uids; |
392 | |
393 | // A basic_block is in this bitmap if we need to call purge_dead_edges |
394 | // on it. As with M_QUEUED_INSN_UPDATES, these updates are queued until |
395 | // a convenient point. |
396 | auto_bitmap m_need_to_purge_dead_edges; |
397 | |
398 | // The set of hard registers that are fully or partially clobbered |
399 | // by at least one insn_call_clobbers_note. |
400 | HARD_REG_SET m_clobbered_by_calls; |
401 | }; |
402 | |
403 | void pp_function (pretty_printer *, const function_info *); |
404 | } |
405 | |
406 | void dump (FILE *, const rtl_ssa::function_info *); |
407 | |
408 | void DEBUG_FUNCTION debug (const rtl_ssa::function_info *); |
409 | |