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 *);