Line data Source code
1 : // Instruction-related RTL SSA classes -*- 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 : // A fake cost for instructions that we haven't costed yet.
23 : const int UNKNOWN_COST = INT_MAX;
24 :
25 : // Enumerates the kinds of note that can be added to an instruction.
26 : // See the comment above insn_info for details.
27 : enum class insn_note_kind : uint8_t
28 : {
29 : ORDER_NODE,
30 : CALL_CLOBBERS
31 : };
32 :
33 : // The base class for notes that can be added to an instruction.
34 : // See the comment above insn_info for details.
35 : class insn_note
36 : {
37 : // Size: 2 LP64 words.
38 : friend class insn_info;
39 : friend class function_info;
40 :
41 : public:
42 : // Return what kind of note this is.
43 0 : insn_note_kind kind () const { return m_kind; }
44 :
45 : // Return the next note in the list, or null if none.
46 0 : insn_note *next_note () const { return m_next_note; }
47 :
48 : // Used with T = Derived *, where Derived is derived from insn_note.
49 : // Convert the note to Derived, asserting that it has the right kind.
50 : template<typename T>
51 : T as_a ();
52 :
53 : // Used with T = Derived *, where Derived is derived from insn_note.
54 : // If the note is a Derived note, return it in that form, otherwise
55 : // return null.
56 : template<typename T>
57 : T dyn_cast ();
58 :
59 : protected:
60 : // Construct a note with the given kind.
61 : insn_note (insn_note_kind);
62 :
63 : private:
64 : // The next note in the list, or null if none.
65 : insn_note *m_next_note;
66 :
67 : // The kind of note this is.
68 : insn_note_kind m_kind : 8;
69 :
70 : protected:
71 : // Fill in the remaining LP64 word with data that derived classes can use.
72 : unsigned int m_data8 : 8;
73 : unsigned int m_data16 : 16;
74 : unsigned int m_data32 : 32;
75 : };
76 :
77 : // Instructions have one of these notes if insn_info::has_call_clobbers ()
78 : // is true. All such instructions in an EBB are first grouped together
79 : // by the predefined_function_abis of the functions that they call.
80 : // Then, for each such predefined ABI, the call_clobbers notes are put
81 : // into a splay tree whose nodes follow execution order.
82 : class insn_call_clobbers_note : public insn_note
83 : {
84 : friend class function_info;
85 : friend class default_splay_tree_accessors<insn_call_clobbers_note *>;
86 :
87 : public:
88 : static const insn_note_kind kind = insn_note_kind::CALL_CLOBBERS;
89 :
90 : // Return the identifier of the predefined_function_abi.
91 0 : unsigned int abi_id () const { return m_data32; }
92 :
93 : // Return the instruction to which the note is attached.
94 103046320 : insn_info *insn () const { return m_insn; }
95 :
96 : protected:
97 : insn_call_clobbers_note (unsigned int abi_id, insn_info *insn);
98 :
99 : // The splay tree pointers.
100 : insn_call_clobbers_note *m_children[2];
101 :
102 : // The value returned by insn ().
103 : insn_info *m_insn;
104 : };
105 :
106 : // A splay tree of insn_call_clobbers_notes.
107 : using insn_call_clobbers_tree = default_splay_tree<insn_call_clobbers_note *>;
108 :
109 : // SSA-related information about an instruction. It also represents
110 : // artificial instructions that are added to make the dataflow correct;
111 : // these artificial instructions fall into three categories:
112 : //
113 : // - Instructions that hold the phi nodes for an extended basic block (is_phi).
114 : //
115 : // - Instructions that represent the head of a basic block and that hold
116 : // all the associated artificial uses and definitions.
117 : //
118 : // - Instructions that represent the end of a basic block and that again
119 : // hold all the associated artificial uses and definitions.
120 : //
121 : // Dataflow-wise, each instruction goes through three stages:
122 : //
123 : // (1) Use all the values in uses ().
124 : //
125 : // (2) If has_call_clobbers (), clobber the registers indicated by
126 : // insn_callee_abi.
127 : //
128 : // (3) Define all the values in defs ().
129 : //
130 : // Having stage (2) is a trade-off: it makes processing the instructions
131 : // more complicated, but it saves having to allocate memory for every
132 : // individual call clobber. Without it, clobbers for calls would often
133 : // make up a large proportion of the total definitions in a function.
134 : //
135 : // All the instructions in a function are chained together in a list
136 : // that follows a reverse postorder traversal of the CFG. The list
137 : // contains both debug and nondebug instructions, but it is possible
138 : // to hop from one nondebug instruction to the next with constant complexity.
139 : //
140 : // Instructions can have supplemental information attached in the form
141 : // of "notes", a bit like REG_NOTES for the underlying RTL insns.
142 : class insn_info
143 : {
144 : // Size: 9 LP64 words.
145 : friend class ebb_info;
146 : friend class function_info;
147 :
148 : public:
149 : // Compare instructions by their positions in the function list described
150 : // above. Thus for two instructions in the same basic block, I1 < I2 if
151 : // I1 comes before I2 in the block.
152 : bool operator< (const insn_info &) const;
153 : bool operator<= (const insn_info &) const;
154 : bool operator>= (const insn_info &) const;
155 : bool operator> (const insn_info &) const;
156 :
157 : // Return -1 if this instruction comes before INSN in the reverse
158 : // postorder, 0 if this instruction is INSN, or 1 if this instruction
159 : // comes after INSN in the reverse postorder.
160 : int compare_with (const insn_info *insn) const;
161 :
162 : // Return the previous and next instructions in the list described above,
163 : // or null if there are no such instructions.
164 : insn_info *prev_any_insn () const;
165 : insn_info *next_any_insn () const;
166 :
167 : // Only valid if !is_debug_insn (). Return the previous and next
168 : // nondebug instructions in the list described above, skipping over
169 : // any intervening debug instructions. These are constant-time operations.
170 : insn_info *prev_nondebug_insn () const;
171 : insn_info *next_nondebug_insn () const;
172 :
173 : // Return the underlying RTL insn. This instruction is null if is_phi ()
174 : // or is_bb_end () are true. The instruction is a basic block note if
175 : // is_bb_head () is true.
176 837673334 : rtx_insn *rtl () const { return m_rtl; }
177 :
178 : // Return true if the instruction is a real insn with an rtl pattern.
179 : // Return false if it is an artificial instruction that represents the
180 : // phi nodes in an extended basic block or the head or end of a basic block.
181 13284917 : bool is_real () const { return m_cost_or_uid >= 0; }
182 :
183 : // Return the opposite of is_real ().
184 1211645829 : bool is_artificial () const { return m_cost_or_uid < 0; }
185 :
186 : // Return true if the instruction was a real instruction but has now
187 : // been deleted. In this case the instruction is no longer part of
188 : // the SSA information.
189 0 : bool has_been_deleted () const { return m_rtl && !INSN_P (m_rtl); }
190 :
191 : // Return true if the instruction is a debug instruction (and thus
192 : // also a real instruction).
193 6260259382 : bool is_debug_insn () const { return m_is_debug_insn; }
194 :
195 : // Return true if the instruction is something that we can optimize.
196 : // This implies that it is a real instruction that contains an asm
197 : // or that contains something that matches an .md define_insn pattern.
198 590675081 : bool can_be_optimized () const { return m_can_be_optimized; }
199 :
200 : // Return true if the instruction is a call instruction.
201 : //
202 : // ??? We could cache this information, but since most callers would
203 : // go on to access PATTERN (rtl ()), a cache might not be helpful and
204 : // could even be counterproductive.
205 126300462 : bool is_call () const { return CALL_P (m_rtl); }
206 :
207 : // Return true if the instruction is a jump instruction.
208 : //
209 : // ??? See is_call for the reason we don't cache this.
210 47805805 : bool is_jump () const { return JUMP_P (m_rtl); }
211 :
212 : // Return true if the instruction is real and contains an inline asm.
213 308903959 : bool is_asm () const { return m_is_asm; }
214 :
215 : // Return true if the instruction is real and includes an RTX_AUTOINC
216 : // operation.
217 68666259 : bool has_pre_post_modify () const { return m_has_pre_post_modify; }
218 :
219 : // Return true if the instruction is real and has volatile references,
220 : // in the sense of volatile_refs_p. This includes volatile memory,
221 : // volatile asms and UNSPEC_VOLATILEs.
222 69382704 : bool has_volatile_refs () const { return m_has_volatile_refs; }
223 :
224 : // Return true if the instruction is aritificial and if its (sole)
225 : // purpose is to hold the phi nodes in an extended basic block.
226 : bool is_phi () const;
227 :
228 : // Return true if the instruction is artificial and if it represents
229 : // the head of a basic block. If so, the instruction conceptually
230 : // executes before the real instructions in the block. The uses
231 : // and definitions represent the df_get_artificial_uses and
232 : // df_get_artificial_defs entries for the head of the block.
233 : bool is_bb_head () const;
234 :
235 : // Return true if the instruction is artificial and if it represents
236 : // the end of a basic block. The uses and definitions represent the
237 : // the df_get_artificial_uses and df_get_artificial_defs entries for
238 : // the end of the block.
239 : bool is_bb_end () const;
240 :
241 : // Return the basic block that the instruction is in.
242 1109170378 : bb_info *bb () const { return m_bb; }
243 :
244 : // Return the extended basic block that the instruction is in;
245 : // see bb_info for details.
246 : ebb_info *ebb () const;
247 :
248 : // If the instruction is real, return the unique identifier of the
249 : // underlying RTL insn. If the instruction is artificial, return
250 : // a unique negative identifier for the instructions.
251 : //
252 : // Note that the identifiers are not linear: it can be the case that
253 : // an instruction with a higher uid comes earlier in a block than an
254 : // instruction with a lower uid. The identifiers are however persistent;
255 : // the identifier remains the same after the instruction has been moved
256 : // or changed.
257 : int uid () const;
258 :
259 : // Return the list of things that this instruction uses. Registers
260 : // come first, in register number order, followed by memory.
261 : use_array uses () const;
262 :
263 : // Return true if the instruction is a call and if the clobbers
264 : // described by insn_callee_abi have been omitted from the list
265 : // of definitions.
266 : bool has_call_clobbers () const;
267 :
268 : // Return the list of things that this instruction sets or clobbers.
269 : // Registers come first, in register number order, followed by memory.
270 : //
271 : // If has_call_clobbers () is true, the list omits both the full and
272 : // partial register clobbers described by insn_callee_abi.
273 : def_array defs () const;
274 :
275 : // The number of entries in uses ().
276 18476320 : unsigned int num_uses () const { return m_num_uses; }
277 :
278 : // The number of entries in defs ().
279 131920053 : unsigned int num_defs () const { return m_num_defs; }
280 :
281 : // Return the cost of the instruction, as calculated by the target.
282 : // For performance reasons, the cost is evaluated lazily on first use.
283 : //
284 : // Artificial instructions have a cost of 0.
285 : unsigned int cost () const;
286 :
287 : // Return the first insn_note attached to the instruction, or null
288 : // if none.
289 2221504 : insn_note *first_note () const { return m_first_note; }
290 :
291 : // See if a note of type T is attached to the instruction. Return it
292 : // if so, otherwise return null.
293 : template<typename T>
294 : const T *find_note () const;
295 :
296 : // Print "i" + uid () for real instructions and "a" + -uid () for
297 : // artificial instructions.
298 : void print_identifier (pretty_printer *) const;
299 :
300 : // Print a short(ish) description of where the instruction is.
301 : void print_location (pretty_printer *) const;
302 :
303 : // Combine print_identifier and print_location.
304 : void print_identifier_and_location (pretty_printer *) const;
305 :
306 : // Print a full description of the instruction.
307 : void print_full (pretty_printer *) const;
308 :
309 50722 : bool is_temporary () const { return m_is_temp; }
310 :
311 : private:
312 : // The first-order way of representing the order between instructions
313 : // is to assign "program points", with higher point numbers coming
314 : // later in the reverse postorder than lower point numbers. However,
315 : // after a sequence of instruction movements, we may end up in a situation
316 : // that adjacent instructions have the same program point.
317 : //
318 : // When that happens, we put the instructions into a splay tree that
319 : // records their relative order. Each node of the splay tree is an
320 : // order_node note that is attached to its respective instruction.
321 : // The root of the splay tree is not stored, since the only thing
322 : // we need the tree for is to compare two nodes.
323 : class order_node : public insn_note
324 : {
325 : public:
326 : static const insn_note_kind kind = insn_note_kind::ORDER_NODE;
327 :
328 : order_node (int uid);
329 :
330 : // Return the uid of the instruction that this node describes.
331 0 : int uid () const { return m_data32; }
332 :
333 : // Change the uid of the instruction that this node describes.
334 913 : void set_uid (int uid) { m_data32 = uid; }
335 :
336 : // The splay tree pointers.
337 : order_node *m_children[2];
338 : order_node *m_parent;
339 : };
340 : using order_splay_tree = default_rootless_splay_tree<order_node *>;
341 :
342 : insn_info (bb_info *bb, rtx_insn *rtl, int cost_or_uid);
343 :
344 : static void print_uid (pretty_printer *, int);
345 :
346 : void calculate_cost () const;
347 : void set_properties (const rtx_properties &);
348 : void set_accesses (access_info **, unsigned int, unsigned int);
349 : void copy_accesses (access_array, access_array);
350 18476320 : void set_cost (unsigned int cost) { m_cost_or_uid = cost; }
351 25361 : void set_bb (bb_info *bb) { m_bb = bb; }
352 :
353 : void add_note (insn_note *note);
354 : void remove_note (insn_note *note);
355 :
356 : order_node *get_order_node () const;
357 : order_node *get_known_order_node () const;
358 : int slow_compare_with (const insn_info &) const;
359 :
360 : insn_info *last_debug_insn () const;
361 :
362 827790673 : unsigned int point () const { return m_point; }
363 : void copy_prev_from (insn_info *);
364 : void copy_next_from (insn_info *);
365 : void set_prev_sametype_insn (insn_info *);
366 : void set_last_debug_insn (insn_info *);
367 : void set_next_any_insn (insn_info *);
368 827816034 : void set_point (unsigned int point) { m_point = point; }
369 : void clear_insn_links ();
370 : bool has_insn_links ();
371 :
372 : // m_prev_sametye_or_last_debug_insn represents a choice between two things:
373 : //
374 : // (1) A pointer to the previous instruction in the list that has the
375 : // same is_debug_insn () value, or null if no such instruction exists.
376 : //
377 : // (2) A pointer to the end of a sublist of debug instructions.
378 : //
379 : // (2) is used if this instruction is a debug instruction and the
380 : // previous instruction is not. (1) is used otherwise.
381 : //
382 : // m_next_nondebug_or_debug_insn points to the next instruction but also
383 : // records whether that next instruction is a debug instruction or a
384 : // nondebug instruction.
385 : //
386 : // Thus the list is chained as follows:
387 : //
388 : // ----> ----> ----> ----> ---->
389 : // NONDEBUG NONDEBUG DEBUG DEBUG DEBUG NONDEBUG ...
390 : // <---- ^ +-- <---- <---- ^ +--
391 : // | | | |
392 : // | +------------------------+ |
393 : // | |
394 : // +-----------------------------------+
395 : pointer_mux<insn_info> m_prev_sametype_or_last_debug_insn;
396 : pointer_mux<insn_info> m_next_nondebug_or_debug_insn;
397 :
398 : // The values returned by the accessors above.
399 : bb_info *m_bb;
400 : rtx_insn *m_rtl;
401 :
402 : // The list of definitions followed by the list of uses.
403 : access_info **m_accesses;
404 :
405 : // The number of definitions and the number uses. FIRST_PSEUDO_REGISTER + 1
406 : // is the maximum number of accesses to hard registers and memory, and
407 : // MAX_RECOG_OPERANDS is the maximum number of pseudos that can be
408 : // defined by an instruction, so the number of definitions in a real
409 : // instruction should fit easily in 16 bits. However, there are no
410 : // limits on the number of definitions in artifical instructions.
411 : unsigned int m_num_uses;
412 : unsigned int m_num_defs;
413 :
414 : // Flags returned by the accessors above.
415 : unsigned int m_is_debug_insn : 1;
416 : unsigned int m_can_be_optimized : 1;
417 : unsigned int m_is_asm : 1;
418 : unsigned int m_has_pre_post_modify : 1;
419 : unsigned int m_has_volatile_refs : 1;
420 :
421 : // Indicates the insn is a temporary / new user-allocated insn.
422 : unsigned int m_is_temp : 1;
423 :
424 : // For future expansion.
425 : unsigned int m_spare : 26;
426 :
427 : // The program point at which the instruction occurs.
428 : //
429 : // Note that the values of the program points are influenced by -g
430 : // and so should not used to make codegen decisions.
431 : unsigned int m_point;
432 :
433 : // Negative if the instruction is artificial, nonnegative if it is real.
434 : //
435 : // For real instructions: the cost of the instruction, or UNKNOWN_COST
436 : // if we haven't measured it yet.
437 : //
438 : // For artificial instructions: the (negative) unique identifier of the
439 : // instruction.
440 : mutable int m_cost_or_uid;
441 :
442 : // On LP64 systems, there's a gap here that could be used for future
443 : // expansion.
444 :
445 : // The list of notes that have been attached to the instruction.
446 : insn_note *m_first_note;
447 : };
448 :
449 : // Iterators for unfiltered lists of instructions.
450 : using any_insn_iterator = list_iterator<insn_info, &insn_info::next_any_insn>;
451 : using reverse_any_insn_iterator
452 : = list_iterator<insn_info, &insn_info::prev_any_insn>;
453 :
454 : // Iterators for nondebug instructions only.
455 : using nondebug_insn_iterator
456 : = list_iterator<insn_info, &insn_info::next_nondebug_insn>;
457 : using reverse_nondebug_insn_iterator
458 : = list_iterator<insn_info, &insn_info::prev_nondebug_insn>;
459 :
460 : // A class that describes an inclusive range of instructions.
461 : class insn_range_info
462 : {
463 : public:
464 : insn_range_info () = default;
465 :
466 : // Create a range that contains a singleton instruction.
467 96774605 : insn_range_info (insn_info *insn) : first (insn), last (insn) {}
468 :
469 : // Create a range [FIRST, LAST], given that *FIRST <= *LAST.
470 : insn_range_info (insn_info *first, insn_info *last);
471 :
472 : // Return true if the range contains at least one instruction.
473 257689075 : explicit operator bool () const { return *first <= *last; }
474 :
475 : bool operator== (const insn_range_info &) const;
476 : bool operator!= (const insn_range_info &) const;
477 :
478 : // If the range contains a single instruction, return that instruction,
479 : // otherwise return null.
480 : insn_info *singleton () const;
481 :
482 : // Return true if the range includes INSN.
483 : bool includes (insn_info *insn) const;
484 :
485 : // If INSN is inside the range, return INSN, otherwise return the
486 : // nearest in-range instruction.
487 : insn_info *clamp_insn_to_range (insn_info *insn) const;
488 :
489 : // Return true if this range is a subrange of OTHER, i.e. if OTHER
490 : // includes every instruction that this range does.
491 : bool is_subrange_of (const insn_range_info &other) const;
492 :
493 : // The lower and upper bounds of the range.
494 : insn_info *first;
495 : insn_info *last;
496 : };
497 :
498 : void pp_insn (pretty_printer *, const insn_info *);
499 :
500 : }
501 :
502 : void dump (FILE *, const rtl_ssa::insn_info *);
503 :
504 : void DEBUG_FUNCTION debug (const rtl_ssa::insn_info *);
|
