Branch data Line data Source code
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 : 29242320 : 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 : 311893868 : 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 : 64658273 : unsigned int index () const { return m_cfg_bb->index; }
68 : :
69 : : // Return the EBB that contains this block.
70 : 418858386 : 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 : 43840352 : 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 : 44072203 : 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 : 23176867 : void set_prev_bb (bb_info *bb) { m_prev_bb = bb; }
128 : 21201603 : 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 : 23176867 : void set_ebb (ebb_info *ebb) { m_ebb = ebb; }
131 : 23176867 : void set_head_insn (insn_info *insn) { m_head_insn = insn; }
132 : 23176867 : 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 : 27869870 : ebb_call_clobbers_info *next () const { return m_next; }
159 : :
160 : : // Return the function abi used by all the calls in the group.
161 : 3582803 : 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 : 28368511 : insn_info *phi_insn () const { return m_phi_insn; }
217 : :
218 : : // Return the first and last blocks in the EBB.
219 : 101765350 : bb_info *first_bb () const { return m_first_bb; }
220 : 32128759 : bb_info *last_bb () const { return m_last_bb; }
221 : :
222 : : // Return the first of the EBB's phi nodes.
223 : 42068115 : 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 : 29307389 : void set_first_phi (phi_info *phi) { m_first_phi = phi; }
274 : 14619549 : 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 *);
|
