1 | // Basic-block-related classes for RTL SSA -*- C++ -*- |
2 | // Copyright (C) 2020-2024 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 *); |
302 | |