Line data Source code
1 : // Basic-block-related classes for RTL SSA -*- C++ -*-
2 : // Copyright (C) 2020-2026 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 91961237 : 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 568065504 : 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 208605433 : unsigned int index () const { return m_cfg_bb->index; }
68 :
69 : // Return the EBB that contains this block.
70 1341655278 : 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 137632605 : 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 216257453 : 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 74730939 : void set_prev_bb (bb_info *bb) { m_prev_bb = bb; }
128 68787977 : 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 74730939 : void set_ebb (ebb_info *ebb) { m_ebb = ebb; }
131 74730939 : void set_head_insn (insn_info *insn) { m_head_insn = insn; }
132 74730939 : 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 52088866 : ebb_call_clobbers_info *next () const { return m_next; }
159 :
160 : // Return the function abi used by all the calls in the group.
161 10503457 : 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 101969819 : insn_info *phi_insn () const { return m_phi_insn; }
217 :
218 : // Return the first and last blocks in the EBB.
219 333572098 : bb_info *first_bb () const { return m_first_bb; }
220 112707041 : bb_info *last_bb () const { return m_last_bb; }
221 :
222 : // Return the first of the EBB's phi nodes.
223 146826837 : 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 105385378 : void set_first_phi (phi_info *phi) { m_first_phi = phi; }
274 45977392 : 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 *);
|
