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
20namespace 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.
34class 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
46public:
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
219private:
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
403void pp_function (pretty_printer *, const function_info *);
404}
405
406void dump (FILE *, const rtl_ssa::function_info *);
407
408void DEBUG_FUNCTION debug (const rtl_ssa::function_info *);
409

source code of gcc/rtl-ssa/functions.h