1// Instruction-related RTL SSA classes -*- 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
20namespace rtl_ssa {
21
22// A fake cost for instructions that we haven't costed yet.
23const 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.
27enum 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.
35class insn_note
36{
37 // Size: 2 LP64 words.
38 friend class insn_info;
39 friend class function_info;
40
41public:
42 // Return what kind of note this is.
43 insn_note_kind kind () const { return m_kind; }
44
45 // Return the next note in the list, or null if none.
46 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
59protected:
60 // Construct a note with the given kind.
61 insn_note (insn_note_kind);
62
63private:
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
70protected:
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.
82class 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
87public:
88 static const insn_note_kind kind = insn_note_kind::CALL_CLOBBERS;
89
90 // Return the identifier of the predefined_function_abi.
91 unsigned int abi_id () const { return m_data32; }
92
93 // Return the instruction to which the note is attached.
94 insn_info *insn () const { return m_insn; }
95
96protected:
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.
107using 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.
142class insn_info
143{
144 // Size: 9 LP64 words.
145 friend class ebb_info;
146 friend class function_info;
147
148public:
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 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 bool is_real () const { return m_cost_or_uid >= 0; }
182
183 // Return the opposite of is_real ().
184 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 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 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 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 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 bool is_jump () const { return JUMP_P (m_rtl); }
211
212 // Return true if the instruction is real and contains an inline asm.
213 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 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 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 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 unsigned int num_uses () const { return m_num_uses; }
277
278 // The number of entries in defs ().
279 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 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 bool is_temporary () const { return m_is_temp; }
310
311private:
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 int uid () const { return m_data32; }
332
333 // The splay tree pointers.
334 order_node *m_children[2];
335 order_node *m_parent;
336 };
337 using order_splay_tree = default_rootless_splay_tree<order_node *>;
338
339 // prev_insn_or_last_debug_insn represents a choice between two things:
340 //
341 // (1) A pointer to the previous instruction in the list that has the
342 // same is_debug_insn () value, or null if no such instruction exists.
343 //
344 // (2) A pointer to the end of a sublist of debug instructions.
345 //
346 // (2) is used if this instruction is a debug instruction and the
347 // previous instruction is not. (1) is used otherwise.
348 //
349 // next_nondebug_or_debug_insn points to the next instruction but also
350 // records whether that next instruction is a debug instruction or a
351 // nondebug instruction.
352 //
353 // Thus the list is chained as follows:
354 //
355 // ----> ----> ----> ----> ---->
356 // NONDEBUG NONDEBUG DEBUG DEBUG DEBUG NONDEBUG ...
357 // <---- ^ +-- <---- <---- ^ +--
358 // | | | |
359 // | +------------------------+ |
360 // | |
361 // +-----------------------------------+
362 using prev_insn_or_last_debug_insn = pointer_mux<insn_info>;
363 using next_nondebug_or_debug_insn = pointer_mux<insn_info>;
364
365 insn_info (bb_info *bb, rtx_insn *rtl, int cost_or_uid);
366
367 static void print_uid (pretty_printer *, int);
368
369 void calculate_cost () const;
370 void set_properties (const rtx_properties &);
371 void set_accesses (access_info **, unsigned int, unsigned int);
372 void copy_accesses (access_array, access_array);
373 void set_cost (unsigned int cost) { m_cost_or_uid = cost; }
374 void set_bb (bb_info *bb) { m_bb = bb; }
375
376 void add_note (insn_note *note);
377
378 order_node *get_order_node () const;
379 order_node *get_known_order_node () const;
380 int slow_compare_with (const insn_info &) const;
381
382 insn_info *last_debug_insn () const;
383
384 unsigned int point () const { return m_point; }
385 void copy_prev_from (insn_info *);
386 void copy_next_from (insn_info *);
387 void set_prev_sametype_insn (insn_info *);
388 void set_last_debug_insn (insn_info *);
389 void set_next_any_insn (insn_info *);
390 void set_point (unsigned int point) { m_point = point; }
391 void clear_insn_links ();
392 bool has_insn_links ();
393
394 // The values returned by the accessors above.
395 prev_insn_or_last_debug_insn m_prev_insn_or_last_debug_insn;
396 next_nondebug_or_debug_insn m_next_nondebug_or_debug_insn;
397 bb_info *m_bb;
398 rtx_insn *m_rtl;
399
400 // The list of definitions followed by the list of uses.
401 access_info **m_accesses;
402
403 // The number of definitions and the number uses. FIRST_PSEUDO_REGISTER + 1
404 // is the maximum number of accesses to hard registers and memory, and
405 // MAX_RECOG_OPERANDS is the maximum number of pseudos that can be
406 // defined by an instruction, so the number of definitions in a real
407 // instruction should fit easily in 16 bits. However, there are no
408 // limits on the number of definitions in artifical instructions.
409 unsigned int m_num_uses;
410 unsigned int m_num_defs;
411
412 // Flags returned by the accessors above.
413 unsigned int m_is_debug_insn : 1;
414 unsigned int m_can_be_optimized : 1;
415 unsigned int m_is_asm : 1;
416 unsigned int m_has_pre_post_modify : 1;
417 unsigned int m_has_volatile_refs : 1;
418
419 // Indicates the insn is a temporary / new user-allocated insn.
420 unsigned int m_is_temp : 1;
421
422 // For future expansion.
423 unsigned int m_spare : 26;
424
425 // The program point at which the instruction occurs.
426 //
427 // Note that the values of the program points are influenced by -g
428 // and so should not used to make codegen decisions.
429 unsigned int m_point;
430
431 // Negative if the instruction is artificial, nonnegative if it is real.
432 //
433 // For real instructions: the cost of the instruction, or UNKNOWN_COST
434 // if we haven't measured it yet.
435 //
436 // For artificial instructions: the (negative) unique identifier of the
437 // instruction.
438 mutable int m_cost_or_uid;
439
440 // On LP64 systems, there's a gap here that could be used for future
441 // expansion.
442
443 // The list of notes that have been attached to the instruction.
444 insn_note *m_first_note;
445};
446
447// Iterators for unfiltered lists of instructions.
448using any_insn_iterator = list_iterator<insn_info, &insn_info::next_any_insn>;
449using reverse_any_insn_iterator
450 = list_iterator<insn_info, &insn_info::prev_any_insn>;
451
452// Iterators for nondebug instructions only.
453using nondebug_insn_iterator
454 = list_iterator<insn_info, &insn_info::next_nondebug_insn>;
455using reverse_nondebug_insn_iterator
456 = list_iterator<insn_info, &insn_info::prev_nondebug_insn>;
457
458// A class that describes an inclusive range of instructions.
459class insn_range_info
460{
461public:
462 insn_range_info () = default;
463
464 // Create a range that contains a singleton instruction.
465 insn_range_info (insn_info *insn) : first (insn), last (insn) {}
466
467 // Create a range [FIRST, LAST], given that *FIRST <= *LAST.
468 insn_range_info (insn_info *first, insn_info *last);
469
470 // Return true if the range contains at least one instruction.
471 explicit operator bool () const { return *first <= *last; }
472
473 bool operator== (const insn_range_info &) const;
474 bool operator!= (const insn_range_info &) const;
475
476 // If the range contains a single instruction, return that instruction,
477 // otherwise return null.
478 insn_info *singleton () const;
479
480 // Return true if the range includes INSN.
481 bool includes (insn_info *insn) const;
482
483 // If INSN is inside the range, return INSN, otherwise return the
484 // nearest in-range instruction.
485 insn_info *clamp_insn_to_range (insn_info *insn) const;
486
487 // Return true if this range is a subrange of OTHER, i.e. if OTHER
488 // includes every instruction that this range does.
489 bool is_subrange_of (const insn_range_info &other) const;
490
491 // The lower and upper bounds of the range.
492 insn_info *first;
493 insn_info *last;
494};
495
496// A class that represents a closure of operator== for instructions.
497// This is used by insn_is; see there for details.
498class insn_is_closure
499{
500public:
501 insn_is_closure (const insn_info *insn) : m_insn (insn) {}
502 bool operator() (const insn_info *other) const { return m_insn == other; }
503
504private:
505 const insn_info *m_insn;
506};
507
508void pp_insn (pretty_printer *, const insn_info *);
509
510}
511
512void dump (FILE *, const rtl_ssa::insn_info *);
513
514void DEBUG_FUNCTION debug (const rtl_ssa::insn_info *);
515

source code of gcc/rtl-ssa/insns.h