1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
|
// Basic-block-related classes for RTL SSA -*- C++ -*-
// Copyright (C) 2020-2024 Free Software Foundation, Inc.
//
// This file is part of GCC.
//
// GCC is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 3, or (at your option) any later
// version.
//
// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License
// along with GCC; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
namespace rtl_ssa {
// SSA-related information about a basic block. Each block contains
// the following, which are conceptually executed in order:
//
// - an artificial "head" insn_info that holds artificial uses and definitions
// for the start of the block.
//
// - one insn_info for each "real" instruction in the block
// (i.e. those that have an RTL pattern).
//
// - an artificial "end" insn_info that holds artificial uses and definitions
// for the end of the block.
//
// Blocks are grouped together into extended basic blocks. In cases where
// multiple EBBs exist (such as in a full diamond), we try to pick the one
// that's most frequently executed.
//
// Blocks are chained together in reverse postorder. (Rather than use a
// list, we could instead have stored the index of the block in the overall
// postorder. However, using lists should make it cheaper to update the
// information after trivial CFG manipulations.)
class bb_info
{
// Size: 6 LP64 words.
friend class function_info;
public:
// Return the previous basic block in reverse postorder, or null if this
// is the entry block.
bb_info *prev_bb () const { return m_prev_bb; }
// Return the next basic block in reverse postorder, or null if this
// is the exit block.
bb_info *next_bb () const { return m_next_bb; }
// Return true if this block is the function's entry block.
bool is_entry_block () const { return !m_prev_bb; }
// Return true if this block is the function's exit block.
bool is_exit_block () const { return !m_next_bb; }
// Return the underlying basic_block structure.
basic_block cfg_bb () const { return m_cfg_bb; }
// Return the unique identifier of the underlying basic_block. These uids
// do not follow any particular order.
unsigned int index () const { return m_cfg_bb->index; }
// Return the EBB that contains this block.
ebb_info *ebb () const { return m_ebb; }
// Return a list of all the instructions in the block, in execution order.
// The list includes the head and end instructions described above.
//
// Iterations over the list will pick up any new instructions that are
// inserted after the iterator's current instruction.
iterator_range<any_insn_iterator> all_insns () const;
// Like all_insns (), except that the instructions are in reverse order.
//
// Iterations over the list will pick up any new instructions that are
// inserted before the iterator's current instruction.
iterator_range<reverse_any_insn_iterator> reverse_all_insns () const;
// Like all_insns (), but without the debug instructions.
iterator_range<nondebug_insn_iterator> nondebug_insns () const;
// Like reverse_all_insns (), but without the debug instructions.
iterator_range<reverse_nondebug_insn_iterator>
reverse_nondebug_insns () const;
// Like all_insns (), but without the artificial instructions.
iterator_range<any_insn_iterator> real_insns () const;
// Like reverse_all_insns (), but without the artificial instructions.
iterator_range<reverse_any_insn_iterator> reverse_real_insns () const;
// Like real_insns (), but without the debug instructions.
iterator_range<nondebug_insn_iterator> real_nondebug_insns () const;
// Like reverse_real_insns (), but without the debug instructions.
iterator_range<reverse_nondebug_insn_iterator>
reverse_real_nondebug_insns () const;
// Return the instruction that holds the artificial uses and
// definitions at the head of the block. The associated RTL insn
// is the block head note.
//
// This instruction always exists, even if it has no uses and definitions.
insn_info *head_insn () const { return m_head_insn; }
// Return the instruction that holds the artificial uses and definitions
// at the end of the block. There is no associated RTL insn.
//
// This instruction always exists, even if it has no uses and definitions.
insn_info *end_insn () const { return m_end_insn; }
// Print "bb" + index () to PP.
void print_identifier (pretty_printer *pp) const;
// Print a full description of the block to PP.
void print_full (pretty_printer *) const;
private:
bb_info (basic_block);
void set_prev_bb (bb_info *bb) { m_prev_bb = bb; }
void set_next_bb (bb_info *bb) { m_next_bb = bb; }
void set_cfg_bb (basic_block cfg_bb) { m_cfg_bb = cfg_bb; }
void set_ebb (ebb_info *ebb) { m_ebb = ebb; }
void set_head_insn (insn_info *insn) { m_head_insn = insn; }
void set_end_insn (insn_info *insn) { m_end_insn = insn; }
// The values returned by the functions above.
bb_info *m_prev_bb;
bb_info *m_next_bb;
basic_block m_cfg_bb;
ebb_info *m_ebb;
insn_info *m_head_insn;
insn_info *m_end_insn;
};
// Iterators for lists of basic blocks.
using bb_iterator = list_iterator<bb_info, &bb_info::next_bb>;
using reverse_bb_iterator = list_iterator<bb_info, &bb_info::prev_bb>;
// This class collects together instructions for which has_call_clobbers ()
// is true, storing them in a splay tree that follows reverse postorder.
// Instances of the class form a singly-linked list, with one instance
// per predefined_function_abi.
class ebb_call_clobbers_info : public insn_call_clobbers_tree
{
// Size 3 LP64 words.
friend class function_info;
public:
// Return the next group in the list.
ebb_call_clobbers_info *next () const { return m_next; }
// Return the function abi used by all the calls in the group.
const predefined_function_abi *abi () const { return m_abi; }
// Return true if at least one call in the group should conservatively
// be assumed to clobber RESOURCE.
bool clobbers (resource_info) const;
// Print a summary of what the class describes to PP, without printing
// the actual instructions.
void print_summary (pretty_printer *pp) const;
// Print a full description of the object to PP, including the
// instructions it contains.
void print_full (pretty_printer *) const;
private:
ebb_call_clobbers_info (const predefined_function_abi *);
// The values returned by the accessors above.
ebb_call_clobbers_info *m_next;
const predefined_function_abi *m_abi;
};
// A list of ebb_call_clobbers_infos.
using ebb_call_clobbers_iterator
= list_iterator<ebb_call_clobbers_info, &ebb_call_clobbers_info::next>;
// Information about an extended basic block.
//
// Each EBB has a list of phi nodes and starts with an artificial phi
// instruction that conceptually "executes" the phi nodes. The phi
// nodes are independent of one another and so can be executed in any
// order. The order of the phi nodes in the list is not significant.
//
// Each EBB also maintains a list of ebb_call_clobbers_info structures
// that describe all instructions for which has_call_clobbers () is true.
// See the comment above that class for details.
class ebb_info
{
// Size: 5 LP64 words.
friend class function_info;
public:
// Return the previous EBB in reverse postorder, or null if this EBB
// contains the entry block.
ebb_info *prev_ebb () const;
// Return the next EBB in reverse postorder, or null if this EBB contains
// the exit block.
ebb_info *next_ebb () const;
// Return the instruction that holds the EBB's phi nodes (and does
// nothing else). There is no associated RTL insn.
//
// This instruction always exists, even if the EBB does not currently
// need any phi nodes.
insn_info *phi_insn () const { return m_phi_insn; }
// Return the first and last blocks in the EBB.
bb_info *first_bb () const { return m_first_bb; }
bb_info *last_bb () const { return m_last_bb; }
// Return the first of the EBB's phi nodes.
phi_info *first_phi () const { return m_first_phi; }
// Return the head of the list of ebb_call_clobbers_infos.
ebb_call_clobbers_info *first_call_clobbers () const;
// Return the list of ebb_call_clobbers_infos.
iterator_range<ebb_call_clobbers_iterator> call_clobbers () const;
// Return a list of the EBB's phi nodes, in arbitrary order.
iterator_range<phi_iterator> phis () const;
// Return a list of the blocks in the EBB, in execution order.
iterator_range<bb_iterator> bbs () const;
// Return a list of the blocks in the EBB, in reverse execution order.
iterator_range<reverse_bb_iterator> reverse_bbs () const;
// Return a list of all the instructions in the EBB, in execution order.
// The list includes phi_insn (), the head and end of each block,
// and the real instructions in each block.
//
// Iterations over the list will pick up any new instructions that are
// inserted after the iterator's current instruction.
iterator_range<any_insn_iterator> all_insns () const;
// Like all_insns (), except that the instructions are in reverse order.
//
// Iterations over the list will pick up any new instructions that are
// inserted before the iterator's current instruction.
iterator_range<reverse_any_insn_iterator> reverse_all_insns () const;
// Like all_insns (), but without the debug instructions.
iterator_range<nondebug_insn_iterator> nondebug_insns () const;
// Like reverse_all_insns (), but without the debug instructions.
iterator_range<reverse_nondebug_insn_iterator>
reverse_nondebug_insns () const;
// Return an insn_range that covers the same instructions as all_insns ().
insn_range_info insn_range () const;
// Print "ebb" + first_bb ()->index () to PP.
void print_identifier (pretty_printer *pp) const;
// Print a full description of the EBB to PP.
void print_full (pretty_printer *pp) const;
private:
ebb_info (bb_info *, bb_info *);
void set_first_phi (phi_info *phi) { m_first_phi = phi; }
void set_phi_insn (insn_info *insn) { m_phi_insn = insn; }
void set_first_call_clobbers (ebb_call_clobbers_info *);
// The values returned by the functions above.
phi_info *m_first_phi;
insn_info *m_phi_insn;
bb_info *m_first_bb;
bb_info *m_last_bb;
ebb_call_clobbers_info *m_first_call_clobbers;
};
// Iterators for lists of extended basic blocks.
using ebb_iterator = list_iterator<ebb_info, &ebb_info::next_ebb>;
using reverse_ebb_iterator = list_iterator<ebb_info, &ebb_info::prev_ebb>;
void pp_bb (pretty_printer *, const bb_info *);
void pp_ebb_call_clobbers (pretty_printer *, const ebb_call_clobbers_info *);
void pp_ebb (pretty_printer *, const ebb_info *);
}
void dump (FILE *, const rtl_ssa::bb_info *);
void dump (FILE *, const rtl_ssa::ebb_call_clobbers_info *);
void dump (FILE *, const rtl_ssa::ebb_info *);
void DEBUG_FUNCTION debug (const rtl_ssa::bb_info *);
void DEBUG_FUNCTION debug (const rtl_ssa::ebb_call_clobbers_info *);
void DEBUG_FUNCTION debug (const rtl_ssa::ebb_info *);
|