gcc/rtl-ssa/blocks.h

   1 // Basic-block-related classes for RTL SSA                          -*- C++ -*-
   2 // Copyright (C) 2020-2023 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.
  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.
  54   bb_info *next_bb () const { return m_next_bb; }
  55
  56   // Return true if this block is the function's 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.
  60   bool is_exit_block () const { return !m_next_bb; }
  61
  62   // Return the underlying basic_block structure.
  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.
  67   unsigned int index () const { return m_cfg_bb->index; }
  68
  69   // Return the EBB that contains this block.
  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.
 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.
 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
 127   void set_prev_bb (bb_info *bb) { m_prev_bb = bb; }
 128   void set_next_bb (bb_info *bb) { m_next_bb = bb; }
 129   void set_cfg_bb (basic_block cfg_bb) { m_cfg_bb = cfg_bb; }
 130   void set_ebb (ebb_info *ebb) { m_ebb = ebb; }
 131   void set_head_insn (insn_info *insn) { m_head_insn = 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.
 158   ebb_call_clobbers_info *next () const { return m_next; }
 159
 160   // Return the function abi used by all the calls in the group.
 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.
 216   insn_info *phi_insn () const { return m_phi_insn; }
 217
 218   // Return the first and last blocks in the EBB.
 219   bb_info *first_bb () const { return m_first_bb; }
 220   bb_info *last_bb () const { return m_last_bb; }
 221
 222   // Return the first of the EBB's phi nodes.
 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
 273   void set_first_phi (phi_info *phi) { m_first_phi = phi; }
 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 *);