1 // Function-related RTL SSA classes -*- C++ -*-
2 // Copyright (C) 2020-2021 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 // SSA-related information about a function. It contains three levels
23 // of information, each in reverse postorder:
25 // - a list of extended basic blocks
26 // - a list of basic blocks
27 // - a list of instructions
29 // It also maintains a list of definitions of memory, and a list of
30 // definitions of each register.
32 // See doc/rtl.texi for more details about the way this information
33 // is organized and how changes to it are made.
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.
42 // Because various structures use pointer_mux, we need at least 2 bytes
44 static const size_t obstack_alignment
= sizeof (void *);
47 // Construct SSA form for function FN.
48 function_info (function
*fn
);
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;
55 // Like ebbs (), but in the reverse order.
56 iterator_range
<reverse_ebb_iterator
> reverse_ebbs () const;
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;
62 // Like bbs (), but in the reverse order.
63 iterator_range
<reverse_bb_iterator
> reverse_bbs () const;
65 // Return the SSA information for the basic block with index INDEX.
66 bb_info
*bb (unsigned int index
) const { return m_bbs
[index
]; }
68 // Return the SSA information for CFG_BB.
69 bb_info
*bb (basic_block cfg_bb
) const { return m_bbs
[cfg_bb
->index
]; }
71 // Return a list of all the instructions in the function, in reverse
72 // postorder. The list includes both real and artificial instructions.
74 // Iterations over the list will pick up any new instructions that are
75 // inserted after the iterator's current instruction.
76 iterator_range
<any_insn_iterator
> all_insns () const;
78 // Like all_insns (), but in the reverse order.
80 // Iterations over the list will pick up any new instructions that are
81 // inserted before the iterator's current instruction.
82 iterator_range
<reverse_any_insn_iterator
> reverse_all_insns () const;
84 // Like all_insns (), but without the debug instructions.
85 iterator_range
<nondebug_insn_iterator
> nondebug_insns () const;
87 // Like reverse_all_insns (), but without the debug instructions.
88 iterator_range
<reverse_nondebug_insn_iterator
>
89 reverse_nondebug_insns () const;
91 // Return the first and last instructions in insns ().
92 insn_info
*first_insn () const { return m_first_insn
; }
93 insn_info
*last_insn () const { return m_last_insn
; }
95 // Return a list of all definitions of memory, in reverse postorder.
96 // This includes both real stores by instructions and artificial
97 // definitions by things like phi nodes.
98 iterator_range
<def_iterator
> mem_defs () const;
100 // Return a list of all definitions of register REGNO, in reverse postorder.
101 // This includes both real stores by instructions and artificial
102 // definitions by things like phi nodes.
103 iterator_range
<def_iterator
> ref_defs (unsigned int regno
) const;
105 // Check if all uses of register REGNO are either unconditionally undefined
106 // or use the same single dominating definition. Return the definition
107 // if so, otherwise return null.
108 set_info
*single_dominating_def (unsigned int regno
) const;
110 // Look for a definition of RESOURCE at INSN. Return the result of the
111 // search as a def_lookup; see the comments there for more details.
112 def_lookup
find_def (resource_info resource
, insn_info
*insn
);
114 // Return an RAII object that owns all temporary RTL SSA memory
115 // allocated during a change attempt. The object should remain in
116 // scope until the change has been aborted or successfully completed.
117 obstack_watermark
new_change_attempt () { return &m_temp_obstack
; }
119 // Make a best attempt to check whether the values used by USES are
120 // available on entry to BB, without solving a full dataflow problem.
121 // If all the values are already live on entry to BB or can be made
122 // available there, return a use_array that describes the uses as
123 // if they occured at the start of BB. These uses are purely temporary,
124 // and will not become permanent unless applied using change_insns.
126 // If the operation fails, return an invalid use_array.
128 // WATERMARK is a watermark returned by new_change_attempt ().
129 use_array
make_uses_available (obstack_watermark
&watermark
,
130 use_array uses
, bb_info
*bb
);
132 // If CHANGE doesn't already clobber REGNO, try to add such a clobber,
133 // limiting the movement range in order to make the clobber valid.
134 // When determining whether REGNO is live, ignore accesses made by an
135 // instruction I if IGNORE (I) is true. The caller then assumes the
136 // responsibility of ensuring that CHANGE and I are placed in a valid order.
138 // Return true on success. Leave CHANGE unmodified when returning false.
140 // WATERMARK is a watermark returned by new_change_attempt ().
141 template<typename IgnorePredicate
>
142 bool add_regno_clobber (obstack_watermark
&watermark
, insn_change
&change
,
143 unsigned int regno
, IgnorePredicate ignore
);
145 // Return true if change_insns will be able to perform the changes
146 // described by CHANGES.
147 bool verify_insn_changes (array_slice
<insn_change
*const> changes
);
149 // Perform all the changes in CHANGES, keeping the instructions in the
150 // order specified by the CHANGES array. On return, the SSA information
151 // remains up-to-date. The same is true for instruction-level DF
152 // information, although the block-level DF information might be
154 void change_insns (array_slice
<insn_change
*> changes
);
156 // Like change_insns, but for a single change CHANGE.
157 void change_insn (insn_change
&change
);
159 // If the changes that have been made to instructions require updates
160 // to the CFG, perform those updates now. Return true if something changed.
163 // - The SSA information is now invalid and needs to be recomputed.
165 // - Dominance information is no longer available (in either direction).
167 // - The caller will need to call cleanup_cfg at some point.
169 // ??? We could probably update the SSA information for simple updates,
170 // but currently nothing would benefit. These late CFG changes are
171 // relatively rare anyway, since gimple optimisers should remove most
172 // unnecessary control flow.
173 bool perform_pending_updates ();
175 // Print the contents of the function to PP.
176 void print (pretty_printer
*pp
) const;
179 // Information about the values that are live on exit from a basic block.
180 // This class is only used when constructing the SSA form, it isn't
181 // designed for being kept up-to-date.
182 class bb_live_out_info
185 // REG_VALUES contains all the registers that live out from the block,
186 // in order of increasing register number. There are NUM_REG_VALUES
187 // in total. Registers do not appear here if their values are known
188 // to be completely undefined; in that sense, the information is
189 // closer to DF_LIVE than to DF_LR.
190 unsigned int num_reg_values
;
191 set_info
**reg_values
;
193 // The memory value that is live on exit from the block.
197 // Information used while constructing the SSA form and discarded
202 set_info
*current_reg_value (unsigned int) const;
203 set_info
*current_mem_value () const;
205 void record_reg_def (unsigned int, def_info
*);
206 void record_mem_def (def_info
*);
208 // The block that we're currently processing.
211 // The EBB that contains CURRENT_BB.
212 ebb_info
*current_ebb
;
214 // Except for the local exception noted below:
216 // - If register R has been defined in the current EBB, LAST_ACCESS[R + 1]
217 // is the last definition of R in the EBB.
219 // - If register R is currently live but has not yet been defined
220 // in the EBB, LAST_ACCESS[R + 1] is the current value of R,
221 // or null if the register's value is completely undefined.
223 // - The contents are not meaningful for other registers.
227 // - If the current EBB has defined memory, LAST_ACCESS[0] is the last
228 // definition of memory in the EBB.
230 // - Otherwise LAST_ACCESS[0] is the value of memory that is live on
231 // - entry to the EBB.
233 // The exception is that while building instructions, LAST_ACCESS[I]
234 // can temporarily be the use of regno I - 1 by that instruction.
235 access_info
**last_access
;
237 // A bitmap of registers that are live on entry to this EBB, with a tree
238 // view for quick lookup. Only used if MAY_HAVE_DEBUG_INSNS.
239 bitmap ebb_live_in_for_debug
;
241 // A conservative superset of the registers that are used by
242 // instructions in CURRENT_EBB. That is, all used registers
243 // are in the set, but some unused registers might be too.
246 // A similarly conservative superset of the registers that are defined
247 // by instructions in CURRENT_EBB.
250 // BB_LIVE_OUT[BI] gives the live-out values for the basic block
252 bb_live_out_info
*bb_live_out
;
255 // Return an RAII object that owns all objects allocated by
256 // allocate_temp during its lifetime.
257 obstack_watermark
temp_watermark () { return &m_temp_obstack
; }
259 template<typename T
, typename
... Ts
>
260 T
*allocate (Ts
... args
);
262 template<typename T
, typename
... Ts
>
263 T
*allocate_temp (Ts
... args
);
265 access_array
temp_access_array (access_array accesses
);
267 clobber_group
*need_clobber_group (clobber_info
*);
268 def_node
*need_def_node (def_info
*);
269 def_splay_tree
need_def_splay_tree (def_info
*);
271 use_info
*make_use_available (use_info
*, bb_info
*);
272 def_array
insert_temp_clobber (obstack_watermark
&, insn_info
*,
273 unsigned int, def_array
);
275 void insert_def_before (def_info
*, def_info
*);
276 void insert_def_after (def_info
*, def_info
*);
277 void remove_def_from_list (def_info
*);
279 void add_clobber (clobber_info
*, clobber_group
*);
280 void remove_clobber (clobber_info
*, clobber_group
*);
281 void prepend_clobber_to_group (clobber_info
*, clobber_group
*);
282 void append_clobber_to_group (clobber_info
*, clobber_group
*);
283 void merge_clobber_groups (clobber_info
*, clobber_info
*,
285 clobber_info
*split_clobber_group (clobber_group
*, insn_info
*);
287 void append_def (def_info
*);
288 void add_def (def_info
*);
289 void remove_def (def_info
*);
291 void need_use_splay_tree (set_info
*);
293 static void insert_use_before (use_info
*, use_info
*);
294 static void insert_use_after (use_info
*, use_info
*);
296 void add_use (use_info
*);
297 void remove_use (use_info
*);
299 insn_info::order_node
*need_order_node (insn_info
*);
301 void add_insn_after (insn_info
*, insn_info
*);
302 void append_insn (insn_info
*);
303 void remove_insn (insn_info
*);
305 insn_info
*append_artificial_insn (bb_info
*, rtx_insn
* = nullptr);
307 void start_insn_accesses ();
308 void finish_insn_accesses (insn_info
*);
310 void record_use (build_info
&, insn_info
*, rtx_obj_reference
);
311 void record_call_clobbers (build_info
&, insn_info
*, rtx_call_insn
*);
312 void record_def (build_info
&, insn_info
*, rtx_obj_reference
);
313 void add_insn_to_block (build_info
&, rtx_insn
*);
315 void add_reg_unused_notes (insn_info
*);
317 void add_live_out_use (bb_info
*, set_info
*);
318 set_info
*live_out_value (bb_info
*, set_info
*);
320 void append_phi (ebb_info
*, phi_info
*);
321 void remove_phi (phi_info
*);
322 void delete_phi (phi_info
*);
323 void replace_phi (phi_info
*, set_info
*);
324 phi_info
*create_phi (ebb_info
*, resource_info
, access_info
**,
326 phi_info
*create_degenerate_phi (ebb_info
*, set_info
*);
328 bb_info
*create_bb_info (basic_block
);
329 void append_bb (bb_info
*);
330 void calculate_potential_phi_regs ();
332 insn_info
*add_placeholder_after (insn_info
*);
333 void possibly_queue_changes (insn_change
&);
334 void finalize_new_accesses (insn_change
&);
335 void apply_changes_to_insn (insn_change
&);
337 void init_function_data ();
338 void add_entry_block_defs (build_info
&);
339 void add_phi_nodes (build_info
&);
340 void add_artificial_accesses (build_info
&, df_ref_flags
);
341 void add_block_contents (build_info
&);
342 void record_block_live_out (build_info
&);
343 void populate_backedge_phis (build_info
&);
344 void process_all_blocks ();
346 void simplify_phi_setup (phi_info
*, set_info
**, bitmap
);
347 void simplify_phi_propagate (phi_info
*, set_info
**, bitmap
, bitmap
);
348 void simplify_phis ();
350 // The function that this object describes.
353 // The lowest (negative) in-use artificial insn uid minus one.
354 int m_next_artificial_uid
;
356 // The highest in-use phi uid plus one.
357 unsigned int m_next_phi_uid
;
359 // The highest in-use register number plus one.
360 unsigned int m_num_regs
;
362 // M_DEFS[R] is the first definition of register R - 1 in a reverse
363 // postorder traversal of the function, or null if the function has
364 // no definition of R. Applying last () gives the last definition of R.
366 // M_DEFS[0] is for memory; MEM_REGNO + 1 == 0.
367 auto_vec
<def_info
*> m_defs
;
369 // M_BBS[BI] gives the SSA information about the block with index BI.
370 auto_vec
<bb_info
*> m_bbs
;
372 // An obstack used to allocate the main RTL SSA information.
375 // An obstack used for temporary work, such as while building up a list
376 // of possible instruction changes.
377 obstack m_temp_obstack
;
379 // The start of each obstack, so that all memory in them can be freed.
380 char *m_obstack_start
;
381 char *m_temp_obstack_start
;
383 // The entry and exit blocks.
387 // The first and last instructions in a reverse postorder traversal
389 insn_info
*m_first_insn
;
390 insn_info
*m_last_insn
;
392 // The last nondebug instruction in the list of instructions.
393 // This is only different from m_last_insn when building the initial
394 // SSA information; after that, the last instruction is always a
395 // BB end instruction.
396 insn_info
*m_last_nondebug_insn
;
398 // Temporary working state when building up lists of definitions and uses.
399 // Keeping them around should reduce the number of unnecessary reallocations.
400 auto_vec
<access_info
*> m_temp_defs
;
401 auto_vec
<access_info
*> m_temp_uses
;
403 // The set of registers that might need to have phis associated with them.
404 // Registers outside this set are known to have a single definition that
405 // dominates all uses.
407 // Before RA, about 5% of registers are typically in the set.
408 auto_bitmap m_potential_phi_regs
;
410 // A list of phis that are no longer in use. Their uids are still unique
411 // and so can be recycled.
412 phi_info
*m_free_phis
;
414 // A list of instructions that have been changed in ways that need
415 // further processing later, such as removing dead instructions or
417 auto_vec
<insn_info
*> m_queued_insn_updates
;
419 // The INSN_UIDs of all instructions in M_QUEUED_INSN_UPDATES.
420 auto_bitmap m_queued_insn_update_uids
;
422 // A basic_block is in this bitmap if we need to call purge_dead_edges
423 // on it. As with M_QUEUED_INSN_UPDATES, these updates are queued until
424 // a convenient point.
425 auto_bitmap m_need_to_purge_dead_edges
;
428 void pp_function (pretty_printer
*, const function_info
*);
431 void dump (FILE *, const rtl_ssa::function_info
*);
433 void DEBUG_FUNCTION
debug (const rtl_ssa::function_info
*);