1 // Basic-block-related classes for RTL SSA -*- 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 basic block. Each block contains 23 // the following, which are conceptually executed in order: 24 // 25 // - an artificial "head" insn_info that holds artificial uses and definitions 26 // for the start of the block. 27 // 28 // - one insn_info for each "real" instruction in the block 29 // (i.e. those that have an RTL pattern). 30 // 31 // - an artificial "end" insn_info that holds artificial uses and definitions 32 // for the end of the block. 33 // 34 // Blocks are grouped together into extended basic blocks. In cases where 35 // multiple EBBs exist (such as in a full diamond), we try to pick the one 36 // that's most frequently executed. 37 // 38 // Blocks are chained together in reverse postorder. (Rather than use a 39 // list, we could instead have stored the index of the block in the overall 40 // postorder. However, using lists should make it cheaper to update the 41 // information after trivial CFG manipulations.) 42 class bb_info 43 { 44 // Size: 6 LP64 words. 45 friend class function_info; 46 47 public: 48 // Return the previous basic block in reverse postorder, or null if this 49 // is the entry block. prev_bb()50 bb_info *prev_bb () const { return m_prev_bb; } 51 52 // Return the next basic block in reverse postorder, or null if this 53 // is the exit block. next_bb()54 bb_info *next_bb () const { return m_next_bb; } 55 56 // Return true if this block is the function's entry block. is_entry_block()57 bool is_entry_block () const { return !m_prev_bb; } 58 59 // Return true if this block is the function's exit block. is_exit_block()60 bool is_exit_block () const { return !m_next_bb; } 61 62 // Return the underlying basic_block structure. cfg_bb()63 basic_block cfg_bb () const { return m_cfg_bb; } 64 65 // Return the unique identifier of the underlying basic_block. These uids 66 // do not follow any particular order. index()67 unsigned int index () const { return m_cfg_bb->index; } 68 69 // Return the EBB that contains this block. ebb()70 ebb_info *ebb () const { return m_ebb; } 71 72 // Return a list of all the instructions in the block, in execution order. 73 // The list includes the head and end instructions described above. 74 // 75 // Iterations over the list will pick up any new instructions that are 76 // inserted after the iterator's current instruction. 77 iterator_range<any_insn_iterator> all_insns () const; 78 79 // Like all_insns (), except that the instructions are in reverse order. 80 // 81 // Iterations over the list will pick up any new instructions that are 82 // inserted before the iterator's current instruction. 83 iterator_range<reverse_any_insn_iterator> reverse_all_insns () const; 84 85 // Like all_insns (), but without the debug instructions. 86 iterator_range<nondebug_insn_iterator> nondebug_insns () const; 87 88 // Like reverse_all_insns (), but without the debug instructions. 89 iterator_range<reverse_nondebug_insn_iterator> 90 reverse_nondebug_insns () const; 91 92 // Like all_insns (), but without the artificial instructions. 93 iterator_range<any_insn_iterator> real_insns () const; 94 95 // Like reverse_all_insns (), but without the artificial instructions. 96 iterator_range<reverse_any_insn_iterator> reverse_real_insns () const; 97 98 // Like real_insns (), but without the debug instructions. 99 iterator_range<nondebug_insn_iterator> real_nondebug_insns () const; 100 101 // Like reverse_real_insns (), but without the debug instructions. 102 iterator_range<reverse_nondebug_insn_iterator> 103 reverse_real_nondebug_insns () const; 104 105 // Return the instruction that holds the artificial uses and 106 // definitions at the head of the block. The associated RTL insn 107 // is the block head note. 108 // 109 // This instruction always exists, even if it has no uses and definitions. head_insn()110 insn_info *head_insn () const { return m_head_insn; } 111 112 // Return the instruction that holds the artificial uses and definitions 113 // at the end of the block. There is no associated RTL insn. 114 // 115 // This instruction always exists, even if it has no uses and definitions. end_insn()116 insn_info *end_insn () const { return m_end_insn; } 117 118 // Print "bb" + index () to PP. 119 void print_identifier (pretty_printer *pp) const; 120 121 // Print a full description of the block to PP. 122 void print_full (pretty_printer *) const; 123 124 private: 125 bb_info (basic_block); 126 set_prev_bb(bb_info * bb)127 void set_prev_bb (bb_info *bb) { m_prev_bb = bb; } set_next_bb(bb_info * bb)128 void set_next_bb (bb_info *bb) { m_next_bb = bb; } set_cfg_bb(basic_block cfg_bb)129 void set_cfg_bb (basic_block cfg_bb) { m_cfg_bb = cfg_bb; } set_ebb(ebb_info * ebb)130 void set_ebb (ebb_info *ebb) { m_ebb = ebb; } set_head_insn(insn_info * insn)131 void set_head_insn (insn_info *insn) { m_head_insn = insn; } set_end_insn(insn_info * insn)132 void set_end_insn (insn_info *insn) { m_end_insn = insn; } 133 134 // The values returned by the functions above. 135 bb_info *m_prev_bb; 136 bb_info *m_next_bb; 137 basic_block m_cfg_bb; 138 ebb_info *m_ebb; 139 insn_info *m_head_insn; 140 insn_info *m_end_insn; 141 }; 142 143 // Iterators for lists of basic blocks. 144 using bb_iterator = list_iterator<bb_info, &bb_info::next_bb>; 145 using reverse_bb_iterator = list_iterator<bb_info, &bb_info::prev_bb>; 146 147 // This class collects together instructions for which has_call_clobbers () 148 // is true, storing them in a splay tree that follows reverse postorder. 149 // Instances of the class form a singly-linked list, with one instance 150 // per predefined_function_abi. 151 class ebb_call_clobbers_info : public insn_call_clobbers_tree 152 { 153 // Size 3 LP64 words. 154 friend class function_info; 155 156 public: 157 // Return the next group in the list. next()158 ebb_call_clobbers_info *next () const { return m_next; } 159 160 // Return the function abi used by all the calls in the group. abi()161 const predefined_function_abi *abi () const { return m_abi; } 162 163 // Return true if at least one call in the group should conservatively 164 // be assumed to clobber RESOURCE. 165 bool clobbers (resource_info) const; 166 167 // Print a summary of what the class describes to PP, without printing 168 // the actual instructions. 169 void print_summary (pretty_printer *pp) const; 170 171 // Print a full description of the object to PP, including the 172 // instructions it contains. 173 void print_full (pretty_printer *) const; 174 175 private: 176 ebb_call_clobbers_info (const predefined_function_abi *); 177 178 // The values returned by the accessors above. 179 ebb_call_clobbers_info *m_next; 180 const predefined_function_abi *m_abi; 181 }; 182 183 // A list of ebb_call_clobbers_infos. 184 using ebb_call_clobbers_iterator 185 = list_iterator<ebb_call_clobbers_info, &ebb_call_clobbers_info::next>; 186 187 // Information about an extended basic block. 188 // 189 // Each EBB has a list of phi nodes and starts with an artificial phi 190 // instruction that conceptually "executes" the phi nodes. The phi 191 // nodes are independent of one another and so can be executed in any 192 // order. The order of the phi nodes in the list is not significant. 193 // 194 // Each EBB also maintains a list of ebb_call_clobbers_info structures 195 // that describe all instructions for which has_call_clobbers () is true. 196 // See the comment above that class for details. 197 class ebb_info 198 { 199 // Size: 5 LP64 words. 200 friend class function_info; 201 202 public: 203 // Return the previous EBB in reverse postorder, or null if this EBB 204 // contains the entry block. 205 ebb_info *prev_ebb () const; 206 207 // Return the next EBB in reverse postorder, or null if this EBB contains 208 // the exit block. 209 ebb_info *next_ebb () const; 210 211 // Return the instruction that holds the EBB's phi nodes (and does 212 // nothing else). There is no associated RTL insn. 213 // 214 // This instruction always exists, even if the EBB does not currently 215 // need any phi nodes. phi_insn()216 insn_info *phi_insn () const { return m_phi_insn; } 217 218 // Return the first and last blocks in the EBB. first_bb()219 bb_info *first_bb () const { return m_first_bb; } last_bb()220 bb_info *last_bb () const { return m_last_bb; } 221 222 // Return the first of the EBB's phi nodes. first_phi()223 phi_info *first_phi () const { return m_first_phi; } 224 225 // Return the head of the list of ebb_call_clobbers_infos. 226 ebb_call_clobbers_info *first_call_clobbers () const; 227 228 // Return the list of ebb_call_clobbers_infos. 229 iterator_range<ebb_call_clobbers_iterator> call_clobbers () const; 230 231 // Return a list of the EBB's phi nodes, in arbitrary order. 232 iterator_range<phi_iterator> phis () const; 233 234 // Return a list of the blocks in the EBB, in execution order. 235 iterator_range<bb_iterator> bbs () const; 236 237 // Return a list of the blocks in the EBB, in reverse execution order. 238 iterator_range<reverse_bb_iterator> reverse_bbs () const; 239 240 // Return a list of all the instructions in the EBB, in execution order. 241 // The list includes phi_insn (), the head and end of each block, 242 // and the real instructions in each block. 243 // 244 // Iterations over the list will pick up any new instructions that are 245 // inserted after the iterator's current instruction. 246 iterator_range<any_insn_iterator> all_insns () const; 247 248 // Like all_insns (), except that the instructions are in reverse order. 249 // 250 // Iterations over the list will pick up any new instructions that are 251 // inserted before the iterator's current instruction. 252 iterator_range<reverse_any_insn_iterator> reverse_all_insns () const; 253 254 // Like all_insns (), but without the debug instructions. 255 iterator_range<nondebug_insn_iterator> nondebug_insns () const; 256 257 // Like reverse_all_insns (), but without the debug instructions. 258 iterator_range<reverse_nondebug_insn_iterator> 259 reverse_nondebug_insns () const; 260 261 // Return an insn_range that covers the same instructions as all_insns (). 262 insn_range_info insn_range () const; 263 264 // Print "ebb" + first_bb ()->index () to PP. 265 void print_identifier (pretty_printer *pp) const; 266 267 // Print a full description of the EBB to PP. 268 void print_full (pretty_printer *pp) const; 269 270 private: 271 ebb_info (bb_info *, bb_info *); 272 set_first_phi(phi_info * phi)273 void set_first_phi (phi_info *phi) { m_first_phi = phi; } set_phi_insn(insn_info * insn)274 void set_phi_insn (insn_info *insn) { m_phi_insn = insn; } 275 void set_first_call_clobbers (ebb_call_clobbers_info *); 276 277 // The values returned by the functions above. 278 phi_info *m_first_phi; 279 insn_info *m_phi_insn; 280 bb_info *m_first_bb; 281 bb_info *m_last_bb; 282 ebb_call_clobbers_info *m_first_call_clobbers; 283 }; 284 285 // Iterators for lists of extended basic blocks. 286 using ebb_iterator = list_iterator<ebb_info, &ebb_info::next_ebb>; 287 using reverse_ebb_iterator = list_iterator<ebb_info, &ebb_info::prev_ebb>; 288 289 void pp_bb (pretty_printer *, const bb_info *); 290 void pp_ebb_call_clobbers (pretty_printer *, const ebb_call_clobbers_info *); 291 void pp_ebb (pretty_printer *, const ebb_info *); 292 293 } 294 295 void dump (FILE *, const rtl_ssa::bb_info *); 296 void dump (FILE *, const rtl_ssa::ebb_call_clobbers_info *); 297 void dump (FILE *, const rtl_ssa::ebb_info *); 298 299 void DEBUG_FUNCTION debug (const rtl_ssa::bb_info *); 300 void DEBUG_FUNCTION debug (const rtl_ssa::ebb_call_clobbers_info *); 301 void DEBUG_FUNCTION debug (const rtl_ssa::ebb_info *); 302