Branch data Line data Source code
1 : : // Function-related RTL SSA classes -*- C++ -*-
2 : : // Copyright (C) 2020-2025 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 : 170213204 : 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 : 2005840 : 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 : 63052490 : 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 : : // Use IGNORE to guide this process, where IGNORE is an object that
169 : : // provides the same interface as ignore_nothing.
170 : : //
171 : : // That is, when determining whether REGNO is live, ignore accesses made
172 : : // by an instruction I if IGNORE says that I should be ignored. The caller
173 : : // then assumes the responsibility of ensuring that CHANGE and I are placed
174 : : // in a valid order. Similarly, ignore live ranges associated with a
175 : : // definition of REGNO if IGNORE says that that definition should be
176 : : // ignored.
177 : : //
178 : : // Return true on success. Leave CHANGE unmodified when returning false.
179 : : //
180 : : // WATERMARK is a watermark returned by new_change_attempt ().
181 : : template<typename IgnorePredicates>
182 : : bool add_regno_clobber (obstack_watermark &watermark, insn_change &change,
183 : : unsigned int regno, IgnorePredicates ignore);
184 : :
185 : : // Return true if change_insns will be able to perform the changes
186 : : // described by CHANGES.
187 : : bool verify_insn_changes (array_slice<insn_change *const> changes);
188 : :
189 : : // Perform all the changes in CHANGES, keeping the instructions in the
190 : : // order specified by the CHANGES array. On return, the SSA information
191 : : // remains up-to-date. The same is true for instruction-level DF
192 : : // information, although the block-level DF information might be
193 : : // marked dirty.
194 : : void change_insns (array_slice<insn_change *> changes);
195 : :
196 : : // Like change_insns, but for a single change CHANGE.
197 : : void change_insn (insn_change &change);
198 : :
199 : : // Given a use USE, re-parent it to get its def from NEW_DEF.
200 : : void reparent_use (use_info *use, set_info *new_def);
201 : :
202 : : // If the changes that have been made to instructions require updates
203 : : // to the CFG, perform those updates now. Return true if something changed.
204 : : // If it did:
205 : : //
206 : : // - The SSA information is now invalid and needs to be recomputed.
207 : : //
208 : : // - Dominance information is no longer available (in either direction).
209 : : //
210 : : // - The caller will need to call cleanup_cfg at some point.
211 : : //
212 : : // ??? We could probably update the SSA information for simple updates,
213 : : // but currently nothing would benefit. These late CFG changes are
214 : : // relatively rare anyway, since gimple optimisers should remove most
215 : : // unnecessary control flow.
216 : : bool perform_pending_updates ();
217 : :
218 : : // Print the contents of the function to PP.
219 : : void print (pretty_printer *pp) const;
220 : :
221 : : // Allocate an object of type T above the obstack watermark WM.
222 : : template<typename T, typename... Ts>
223 : : T *change_alloc (obstack_watermark &wm, Ts... args);
224 : :
225 : : private:
226 : : class bb_phi_info;
227 : : class build_info;
228 : : class bb_walker;
229 : :
230 : : // Return an RAII object that owns all objects allocated by
231 : : // allocate_temp during its lifetime.
232 : 14251817 : obstack_watermark temp_watermark () { return &m_temp_obstack; }
233 : :
234 : : template<typename T, typename... Ts>
235 : : T *allocate (Ts... args);
236 : :
237 : : template<typename T, typename... Ts>
238 : : T *allocate_temp (Ts... args);
239 : :
240 : : access_array temp_access_array (access_array accesses);
241 : :
242 : : clobber_group *need_clobber_group (clobber_info *);
243 : : def_node *need_def_node (def_info *);
244 : : def_splay_tree need_def_splay_tree (def_info *);
245 : :
246 : : use_info *make_use_available (use_info *, bb_info *, bool);
247 : : def_array insert_temp_clobber (obstack_watermark &, insn_info *,
248 : : unsigned int, def_array);
249 : :
250 : : void insert_def_before (def_info *, def_info *);
251 : : void insert_def_after (def_info *, def_info *);
252 : : void remove_def_from_list (def_info *);
253 : :
254 : : void add_clobber (clobber_info *, clobber_group *);
255 : : void remove_clobber (clobber_info *, clobber_group *);
256 : : void prepend_clobber_to_group (clobber_info *, clobber_group *);
257 : : void append_clobber_to_group (clobber_info *, clobber_group *);
258 : : void merge_clobber_groups (clobber_info *, clobber_info *,
259 : : def_info *);
260 : : std::array<clobber_group *, 2> split_clobber_group (clobber_group *,
261 : : insn_info *);
262 : :
263 : : void append_def (def_info *);
264 : : void add_def (def_info *);
265 : : void remove_def (def_info *);
266 : :
267 : : void need_use_splay_tree (set_info *);
268 : :
269 : : static void insert_use_before (use_info *, use_info *);
270 : : static void insert_use_after (use_info *, use_info *);
271 : :
272 : : void add_use (use_info *);
273 : : void remove_use (use_info *);
274 : :
275 : : insn_info::order_node *need_order_node (insn_info *);
276 : :
277 : : void add_insn_after (insn_info *, insn_info *);
278 : : void replace_nondebug_insn (insn_info *, insn_info *);
279 : : void append_insn (insn_info *);
280 : : void remove_insn (insn_info *);
281 : :
282 : : insn_info *append_artificial_insn (bb_info *, rtx_insn * = nullptr);
283 : :
284 : : void start_insn_accesses ();
285 : : void finish_insn_accesses (insn_info *);
286 : :
287 : : use_info *create_reg_use (build_info &, insn_info *, resource_info);
288 : : void record_use (build_info &, insn_info *, rtx_obj_reference);
289 : : void record_call_clobbers (build_info &, insn_info *, rtx_call_insn *);
290 : : void record_def (build_info &, insn_info *, rtx_obj_reference);
291 : : void add_insn_to_block (build_info &, rtx_insn *);
292 : :
293 : : void add_reg_unused_notes (insn_info *);
294 : :
295 : : void add_live_out_use (bb_info *, set_info *);
296 : : set_info *live_out_value (bb_info *, set_info *);
297 : :
298 : : void append_phi (ebb_info *, phi_info *);
299 : : void remove_phi (phi_info *);
300 : : void delete_phi (phi_info *);
301 : : void replace_phi (phi_info *, set_info *);
302 : : phi_info *create_phi (ebb_info *, resource_info, access_info **,
303 : : unsigned int);
304 : : phi_info *create_degenerate_phi (ebb_info *, set_info *);
305 : :
306 : : bb_info *create_bb_info (basic_block);
307 : : void append_bb (bb_info *);
308 : :
309 : : void process_uses_of_deleted_def (set_info *);
310 : : insn_info *add_placeholder_after (insn_info *);
311 : : void possibly_queue_changes (insn_change &);
312 : : void finalize_new_accesses (insn_change &, insn_info *,
313 : : hash_set<def_info *> &);
314 : : void apply_changes_to_insn (insn_change &,
315 : : hash_set<def_info *> &);
316 : :
317 : : void init_function_data ();
318 : : void calculate_potential_phi_regs (build_info &);
319 : : void place_phis (build_info &);
320 : : void create_ebbs (build_info &);
321 : : void add_entry_block_defs (build_info &);
322 : : void calculate_ebb_live_in_for_debug (build_info &);
323 : : void add_phi_nodes (build_info &);
324 : : void add_artificial_accesses (build_info &, df_ref_flags);
325 : : void add_block_contents (build_info &);
326 : : void record_block_live_out (build_info &);
327 : : void start_block (build_info &, bb_info *);
328 : : void end_block (build_info &, bb_info *);
329 : : void populate_phi_inputs (build_info &);
330 : : void process_all_blocks ();
331 : :
332 : : void simplify_phi_setup (phi_info *, set_info **, bitmap);
333 : : void simplify_phi_propagate (phi_info *, set_info **, bitmap, bitmap);
334 : : void simplify_phis ();
335 : :
336 : : // The function that this object describes.
337 : : function *m_fn;
338 : :
339 : : // The lowest (negative) in-use artificial insn uid minus one.
340 : : int m_next_artificial_uid;
341 : :
342 : : // The highest in-use phi uid plus one.
343 : : unsigned int m_next_phi_uid;
344 : :
345 : : // The highest in-use register number plus one.
346 : : unsigned int m_num_regs;
347 : :
348 : : // M_DEFS[R] is the first definition of register R - 1 in a reverse
349 : : // postorder traversal of the function, or null if the function has
350 : : // no definition of R. Applying last () gives the last definition of R.
351 : : //
352 : : // M_DEFS[0] is for memory; MEM_REGNO + 1 == 0.
353 : : auto_vec<def_info *> m_defs;
354 : :
355 : : // M_BBS[BI] gives the SSA information about the block with index BI.
356 : : auto_vec<bb_info *> m_bbs;
357 : :
358 : : // An obstack used to allocate the main RTL SSA information.
359 : : obstack m_obstack;
360 : :
361 : : // An obstack used for temporary work, such as while building up a list
362 : : // of possible instruction changes.
363 : : obstack m_temp_obstack;
364 : :
365 : : // The start of each obstack, so that all memory in them can be freed.
366 : : char *m_obstack_start;
367 : : char *m_temp_obstack_start;
368 : :
369 : : // The entry and exit blocks.
370 : : bb_info *m_first_bb;
371 : : bb_info *m_last_bb;
372 : :
373 : : // The first and last instructions in a reverse postorder traversal
374 : : // of the function.
375 : : insn_info *m_first_insn;
376 : : insn_info *m_last_insn;
377 : :
378 : : // The last nondebug instruction in the list of instructions.
379 : : // This is only different from m_last_insn when building the initial
380 : : // SSA information; after that, the last instruction is always a
381 : : // BB end instruction.
382 : : insn_info *m_last_nondebug_insn;
383 : :
384 : : // Temporary working state when building up lists of definitions and uses.
385 : : // Keeping them around should reduce the number of unnecessary reallocations.
386 : : auto_vec<access_info *> m_temp_defs;
387 : : auto_vec<access_info *> m_temp_uses;
388 : :
389 : : // A list of phis that are no longer in use. Their uids are still unique
390 : : // and so can be recycled.
391 : : phi_info *m_free_phis;
392 : :
393 : : // A list of instructions that have been changed in ways that need
394 : : // further processing later, such as removing dead instructions or
395 : : // altering the CFG.
396 : : auto_vec<insn_info *> m_queued_insn_updates;
397 : :
398 : : // The INSN_UIDs of all instructions in M_QUEUED_INSN_UPDATES.
399 : : auto_bitmap m_queued_insn_update_uids;
400 : :
401 : : // A basic_block is in this bitmap if we need to call purge_dead_edges
402 : : // on it. As with M_QUEUED_INSN_UPDATES, these updates are queued until
403 : : // a convenient point.
404 : : auto_bitmap m_need_to_purge_dead_edges;
405 : :
406 : : // The set of hard registers that are fully or partially clobbered
407 : : // by at least one insn_call_clobbers_note.
408 : : HARD_REG_SET m_clobbered_by_calls;
409 : : };
410 : :
411 : : void pp_function (pretty_printer *, const function_info *);
412 : : }
413 : :
414 : : void dump (FILE *, const rtl_ssa::function_info *);
415 : :
416 : : void DEBUG_FUNCTION debug (const rtl_ssa::function_info *);
|