1 // Function-related RTL SSA classes -*- C++ -*- 2 // Copyright (C) 2020-2022 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. bb(unsigned int index)66 bb_info *bb (unsigned int index) const { return m_bbs[index]; } 67 68 // Return the SSA information for CFG_BB. bb(basic_block 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 (). first_insn()92 insn_info *first_insn () const { return m_first_insn; } last_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> reg_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. new_change_attempt()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 // WILL_BE_DEBUG_USES is true if the returned use_array will be 130 // used only for debug instructions. 131 use_array make_uses_available (obstack_watermark &watermark, 132 use_array uses, bb_info *bb, 133 bool will_be_debug_uses); 134 135 // If CHANGE doesn't already clobber REGNO, try to add such a clobber, 136 // limiting the movement range in order to make the clobber valid. 137 // When determining whether REGNO is live, ignore accesses made by an 138 // instruction I if IGNORE (I) is true. The caller then assumes the 139 // responsibility of ensuring that CHANGE and I are placed in a valid order. 140 // 141 // Return true on success. Leave CHANGE unmodified when returning false. 142 // 143 // WATERMARK is a watermark returned by new_change_attempt (). 144 template<typename IgnorePredicate> 145 bool add_regno_clobber (obstack_watermark &watermark, insn_change &change, 146 unsigned int regno, IgnorePredicate ignore); 147 148 // Return true if change_insns will be able to perform the changes 149 // described by CHANGES. 150 bool verify_insn_changes (array_slice<insn_change *const> changes); 151 152 // Perform all the changes in CHANGES, keeping the instructions in the 153 // order specified by the CHANGES array. On return, the SSA information 154 // remains up-to-date. The same is true for instruction-level DF 155 // information, although the block-level DF information might be 156 // marked dirty. 157 void change_insns (array_slice<insn_change *> changes); 158 159 // Like change_insns, but for a single change CHANGE. 160 void change_insn (insn_change &change); 161 162 // If the changes that have been made to instructions require updates 163 // to the CFG, perform those updates now. Return true if something changed. 164 // If it did: 165 // 166 // - The SSA information is now invalid and needs to be recomputed. 167 // 168 // - Dominance information is no longer available (in either direction). 169 // 170 // - The caller will need to call cleanup_cfg at some point. 171 // 172 // ??? We could probably update the SSA information for simple updates, 173 // but currently nothing would benefit. These late CFG changes are 174 // relatively rare anyway, since gimple optimisers should remove most 175 // unnecessary control flow. 176 bool perform_pending_updates (); 177 178 // Print the contents of the function to PP. 179 void print (pretty_printer *pp) const; 180 181 private: 182 class bb_phi_info; 183 class build_info; 184 class bb_walker; 185 186 // Return an RAII object that owns all objects allocated by 187 // allocate_temp during its lifetime. temp_watermark()188 obstack_watermark temp_watermark () { return &m_temp_obstack; } 189 190 template<typename T, typename... Ts> 191 T *allocate (Ts... args); 192 193 template<typename T, typename... Ts> 194 T *allocate_temp (Ts... args); 195 196 access_array temp_access_array (access_array accesses); 197 198 clobber_group *need_clobber_group (clobber_info *); 199 def_node *need_def_node (def_info *); 200 def_splay_tree need_def_splay_tree (def_info *); 201 202 use_info *make_use_available (use_info *, bb_info *, bool); 203 def_array insert_temp_clobber (obstack_watermark &, insn_info *, 204 unsigned int, def_array); 205 206 void insert_def_before (def_info *, def_info *); 207 void insert_def_after (def_info *, def_info *); 208 void remove_def_from_list (def_info *); 209 210 void add_clobber (clobber_info *, clobber_group *); 211 void remove_clobber (clobber_info *, clobber_group *); 212 void prepend_clobber_to_group (clobber_info *, clobber_group *); 213 void append_clobber_to_group (clobber_info *, clobber_group *); 214 void merge_clobber_groups (clobber_info *, clobber_info *, 215 def_info *); 216 clobber_info *split_clobber_group (clobber_group *, insn_info *); 217 218 void append_def (def_info *); 219 void add_def (def_info *); 220 void remove_def (def_info *); 221 222 void need_use_splay_tree (set_info *); 223 224 static void insert_use_before (use_info *, use_info *); 225 static void insert_use_after (use_info *, use_info *); 226 227 void add_use (use_info *); 228 void remove_use (use_info *); 229 230 insn_info::order_node *need_order_node (insn_info *); 231 232 void add_insn_after (insn_info *, insn_info *); 233 void append_insn (insn_info *); 234 void remove_insn (insn_info *); 235 236 insn_info *append_artificial_insn (bb_info *, rtx_insn * = nullptr); 237 238 void start_insn_accesses (); 239 void finish_insn_accesses (insn_info *); 240 241 use_info *create_reg_use (build_info &, insn_info *, resource_info); 242 void record_use (build_info &, insn_info *, rtx_obj_reference); 243 void record_call_clobbers (build_info &, insn_info *, rtx_call_insn *); 244 void record_def (build_info &, insn_info *, rtx_obj_reference); 245 void add_insn_to_block (build_info &, rtx_insn *); 246 247 void add_reg_unused_notes (insn_info *); 248 249 void add_live_out_use (bb_info *, set_info *); 250 set_info *live_out_value (bb_info *, set_info *); 251 252 void append_phi (ebb_info *, phi_info *); 253 void remove_phi (phi_info *); 254 void delete_phi (phi_info *); 255 void replace_phi (phi_info *, set_info *); 256 phi_info *create_phi (ebb_info *, resource_info, access_info **, 257 unsigned int); 258 phi_info *create_degenerate_phi (ebb_info *, set_info *); 259 260 bb_info *create_bb_info (basic_block); 261 void append_bb (bb_info *); 262 263 insn_info *add_placeholder_after (insn_info *); 264 void possibly_queue_changes (insn_change &); 265 void finalize_new_accesses (insn_change &); 266 void apply_changes_to_insn (insn_change &); 267 268 void init_function_data (); 269 void calculate_potential_phi_regs (build_info &); 270 void place_phis (build_info &); 271 void create_ebbs (build_info &); 272 void add_entry_block_defs (build_info &); 273 void calculate_ebb_live_in_for_debug (build_info &); 274 void add_phi_nodes (build_info &); 275 void add_artificial_accesses (build_info &, df_ref_flags); 276 void add_block_contents (build_info &); 277 void record_block_live_out (build_info &); 278 void start_block (build_info &, bb_info *); 279 void end_block (build_info &, bb_info *); 280 void populate_phi_inputs (build_info &); 281 void process_all_blocks (); 282 283 void simplify_phi_setup (phi_info *, set_info **, bitmap); 284 void simplify_phi_propagate (phi_info *, set_info **, bitmap, bitmap); 285 void simplify_phis (); 286 287 // The function that this object describes. 288 function *m_fn; 289 290 // The lowest (negative) in-use artificial insn uid minus one. 291 int m_next_artificial_uid; 292 293 // The highest in-use phi uid plus one. 294 unsigned int m_next_phi_uid; 295 296 // The highest in-use register number plus one. 297 unsigned int m_num_regs; 298 299 // M_DEFS[R] is the first definition of register R - 1 in a reverse 300 // postorder traversal of the function, or null if the function has 301 // no definition of R. Applying last () gives the last definition of R. 302 // 303 // M_DEFS[0] is for memory; MEM_REGNO + 1 == 0. 304 auto_vec<def_info *> m_defs; 305 306 // M_BBS[BI] gives the SSA information about the block with index BI. 307 auto_vec<bb_info *> m_bbs; 308 309 // An obstack used to allocate the main RTL SSA information. 310 obstack m_obstack; 311 312 // An obstack used for temporary work, such as while building up a list 313 // of possible instruction changes. 314 obstack m_temp_obstack; 315 316 // The start of each obstack, so that all memory in them can be freed. 317 char *m_obstack_start; 318 char *m_temp_obstack_start; 319 320 // The entry and exit blocks. 321 bb_info *m_first_bb; 322 bb_info *m_last_bb; 323 324 // The first and last instructions in a reverse postorder traversal 325 // of the function. 326 insn_info *m_first_insn; 327 insn_info *m_last_insn; 328 329 // The last nondebug instruction in the list of instructions. 330 // This is only different from m_last_insn when building the initial 331 // SSA information; after that, the last instruction is always a 332 // BB end instruction. 333 insn_info *m_last_nondebug_insn; 334 335 // Temporary working state when building up lists of definitions and uses. 336 // Keeping them around should reduce the number of unnecessary reallocations. 337 auto_vec<access_info *> m_temp_defs; 338 auto_vec<access_info *> m_temp_uses; 339 340 // A list of phis that are no longer in use. Their uids are still unique 341 // and so can be recycled. 342 phi_info *m_free_phis; 343 344 // A list of instructions that have been changed in ways that need 345 // further processing later, such as removing dead instructions or 346 // altering the CFG. 347 auto_vec<insn_info *> m_queued_insn_updates; 348 349 // The INSN_UIDs of all instructions in M_QUEUED_INSN_UPDATES. 350 auto_bitmap m_queued_insn_update_uids; 351 352 // A basic_block is in this bitmap if we need to call purge_dead_edges 353 // on it. As with M_QUEUED_INSN_UPDATES, these updates are queued until 354 // a convenient point. 355 auto_bitmap m_need_to_purge_dead_edges; 356 }; 357 358 void pp_function (pretty_printer *, const function_info *); 359 } 360 361 void dump (FILE *, const rtl_ssa::function_info *); 362 363 void DEBUG_FUNCTION debug (const rtl_ssa::function_info *); 364