]>
Commit | Line | Data |
---|---|---|
73b75827 | 1 | // Function-related RTL SSA classes -*- 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 | // 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 | // Return a list of all the instructions in the function, in reverse | |
72 | // postorder. The list includes both real and artificial instructions. | |
73 | // | |
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; | |
77 | ||
78 | // Like all_insns (), but in the reverse order. | |
79 | // | |
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; | |
83 | ||
84 | // Like all_insns (), but without the debug instructions. | |
85 | iterator_range<nondebug_insn_iterator> nondebug_insns () const; | |
86 | ||
87 | // Like reverse_all_insns (), but without the debug instructions. | |
88 | iterator_range<reverse_nondebug_insn_iterator> | |
89 | reverse_nondebug_insns () const; | |
90 | ||
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; } | |
94 | ||
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; | |
99 | ||
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; | |
104 | ||
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; | |
109 | ||
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); | |
113 | ||
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; } | |
118 | ||
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. | |
125 | // | |
126 | // If the operation fails, return an invalid use_array. | |
127 | // | |
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); | |
131 | ||
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. | |
137 | // | |
138 | // Return true on success. Leave CHANGE unmodified when returning false. | |
139 | // | |
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); | |
144 | ||
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); | |
148 | ||
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 | |
153 | // marked dirty. | |
154 | void change_insns (array_slice<insn_change *> changes); | |
155 | ||
156 | // Like change_insns, but for a single change CHANGE. | |
157 | void change_insn (insn_change &change); | |
158 | ||
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. | |
161 | // If it did: | |
162 | // | |
163 | // - The SSA information is now invalid and needs to be recomputed. | |
164 | // | |
165 | // - Dominance information is no longer available (in either direction). | |
166 | // | |
167 | // - The caller will need to call cleanup_cfg at some point. | |
168 | // | |
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 (); | |
174 | ||
175 | // Print the contents of the function to PP. | |
176 | void print (pretty_printer *pp) const; | |
177 | ||
178 | private: | |
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 | |
183 | { | |
184 | public: | |
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; | |
192 | ||
193 | // The memory value that is live on exit from the block. | |
194 | set_info *mem_value; | |
195 | }; | |
196 | ||
197 | // Information used while constructing the SSA form and discarded | |
198 | // afterwards. | |
199 | class build_info | |
200 | { | |
201 | public: | |
202 | set_info *current_reg_value (unsigned int) const; | |
203 | set_info *current_mem_value () const; | |
204 | ||
205 | void record_reg_def (unsigned int, def_info *); | |
206 | void record_mem_def (def_info *); | |
207 | ||
208 | // The block that we're currently processing. | |
209 | bb_info *current_bb; | |
210 | ||
211 | // The EBB that contains CURRENT_BB. | |
212 | ebb_info *current_ebb; | |
213 | ||
214 | // Except for the local exception noted below: | |
215 | // | |
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. | |
218 | // | |
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. | |
222 | // | |
223 | // - The contents are not meaningful for other registers. | |
224 | // | |
225 | // Similarly: | |
226 | // | |
227 | // - If the current EBB has defined memory, LAST_ACCESS[0] is the last | |
228 | // definition of memory in the EBB. | |
229 | // | |
230 | // - Otherwise LAST_ACCESS[0] is the value of memory that is live on | |
231 | // - entry to the EBB. | |
232 | // | |
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; | |
236 | ||
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; | |
240 | ||
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. | |
244 | bitmap ebb_use; | |
245 | ||
246 | // A similarly conservative superset of the registers that are defined | |
247 | // by instructions in CURRENT_EBB. | |
248 | bitmap ebb_def; | |
249 | ||
250 | // BB_LIVE_OUT[BI] gives the live-out values for the basic block | |
251 | // with index BI. | |
252 | bb_live_out_info *bb_live_out; | |
253 | }; | |
254 | ||
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; } | |
258 | ||
259 | template<typename T, typename... Ts> | |
260 | T *allocate (Ts... args); | |
261 | ||
262 | template<typename T, typename... Ts> | |
263 | T *allocate_temp (Ts... args); | |
264 | ||
265 | access_array temp_access_array (access_array accesses); | |
266 | ||
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 *); | |
270 | ||
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); | |
274 | ||
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 *); | |
278 | ||
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 *, | |
284 | def_info *); | |
285 | clobber_info *split_clobber_group (clobber_group *, insn_info *); | |
286 | ||
287 | void append_def (def_info *); | |
288 | void add_def (def_info *); | |
289 | void remove_def (def_info *); | |
290 | ||
291 | void need_use_splay_tree (set_info *); | |
292 | ||
293 | static void insert_use_before (use_info *, use_info *); | |
294 | static void insert_use_after (use_info *, use_info *); | |
295 | ||
296 | void add_use (use_info *); | |
297 | void remove_use (use_info *); | |
298 | ||
299 | insn_info::order_node *need_order_node (insn_info *); | |
300 | ||
301 | void add_insn_after (insn_info *, insn_info *); | |
302 | void append_insn (insn_info *); | |
303 | void remove_insn (insn_info *); | |
304 | ||
305 | insn_info *append_artificial_insn (bb_info *, rtx_insn * = nullptr); | |
306 | ||
307 | void start_insn_accesses (); | |
308 | void finish_insn_accesses (insn_info *); | |
309 | ||
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 *); | |
314 | ||
315 | void add_reg_unused_notes (insn_info *); | |
316 | ||
317 | void add_live_out_use (bb_info *, set_info *); | |
318 | set_info *live_out_value (bb_info *, set_info *); | |
319 | ||
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 **, | |
325 | unsigned int); | |
326 | phi_info *create_degenerate_phi (ebb_info *, set_info *); | |
327 | ||
328 | bb_info *create_bb_info (basic_block); | |
329 | void append_bb (bb_info *); | |
330 | void calculate_potential_phi_regs (); | |
331 | ||
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 &); | |
336 | ||
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 (); | |
345 | ||
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 (); | |
349 | ||
350 | // The function that this object describes. | |
351 | function *m_fn; | |
352 | ||
353 | // The lowest (negative) in-use artificial insn uid minus one. | |
354 | int m_next_artificial_uid; | |
355 | ||
356 | // The highest in-use phi uid plus one. | |
357 | unsigned int m_next_phi_uid; | |
358 | ||
359 | // The highest in-use register number plus one. | |
360 | unsigned int m_num_regs; | |
361 | ||
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. | |
365 | // | |
366 | // M_DEFS[0] is for memory; MEM_REGNO + 1 == 0. | |
367 | auto_vec<def_info *> m_defs; | |
368 | ||
369 | // M_BBS[BI] gives the SSA information about the block with index BI. | |
370 | auto_vec<bb_info *> m_bbs; | |
371 | ||
372 | // An obstack used to allocate the main RTL SSA information. | |
373 | obstack m_obstack; | |
374 | ||
375 | // An obstack used for temporary work, such as while building up a list | |
376 | // of possible instruction changes. | |
377 | obstack m_temp_obstack; | |
378 | ||
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; | |
382 | ||
383 | // The entry and exit blocks. | |
384 | bb_info *m_first_bb; | |
385 | bb_info *m_last_bb; | |
386 | ||
387 | // The first and last instructions in a reverse postorder traversal | |
388 | // of the function. | |
389 | insn_info *m_first_insn; | |
390 | insn_info *m_last_insn; | |
391 | ||
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; | |
397 | ||
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; | |
402 | ||
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. | |
406 | // | |
407 | // Before RA, about 5% of registers are typically in the set. | |
408 | auto_bitmap m_potential_phi_regs; | |
409 | ||
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; | |
413 | ||
414 | // A list of instructions that have been changed in ways that need | |
415 | // further processing later, such as removing dead instructions or | |
416 | // altering the CFG. | |
417 | auto_vec<insn_info *> m_queued_insn_updates; | |
418 | ||
419 | // The INSN_UIDs of all instructions in M_QUEUED_INSN_UPDATES. | |
420 | auto_bitmap m_queued_insn_update_uids; | |
421 | ||
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; | |
426 | }; | |
427 | ||
428 | void pp_function (pretty_printer *, const function_info *); | |
429 | } | |
430 | ||
431 | void dump (FILE *, const rtl_ssa::function_info *); | |
432 | ||
433 | void DEBUG_FUNCTION debug (const rtl_ssa::function_info *); |