1 // Instruction-related RTL SSA classes -*- C++ -*-
2 // Copyright (C) 2020-2023 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 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
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 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
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 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 private:
310 // The first-order way of representing the order between instructions
311 // is to assign "program points", with higher point numbers coming
312 // later in the reverse postorder than lower point numbers. However,
313 // after a sequence of instruction movements, we may end up in a situation
314 // that adjacent instructions have the same program point.
315 //
316 // When that happens, we put the instructions into a splay tree that
317 // records their relative order. Each node of the splay tree is an
318 // order_node note that is attached to its respective instruction.
319 // The root of the splay tree is not stored, since the only thing
320 // we need the tree for is to compare two nodes.
321 class order_node : public insn_note
322 {
323 public:
324 static const insn_note_kind kind = insn_note_kind::ORDER_NODE;
325
326 order_node (int uid);
327
328 // Return the uid of the instruction that this node describes.
329 int uid () const { return m_data32; }
330
331 // The splay tree pointers.
332 order_node *m_children[2];
333 order_node *m_parent;
334 };
335 using order_splay_tree = default_rootless_splay_tree<order_node *>;
336
337 // prev_insn_or_last_debug_insn represents a choice between two things:
338 //
339 // (1) A pointer to the previous instruction in the list that has the
340 // same is_debug_insn () value, or null if no such instruction exists.
341 //
342 // (2) A pointer to the end of a sublist of debug instructions.
343 //
344 // (2) is used if this instruction is a debug instruction and the
345 // previous instruction is not. (1) is used otherwise.
346 //
347 // next_nondebug_or_debug_insn points to the next instruction but also
348 // records whether that next instruction is a debug instruction or a
349 // nondebug instruction.
350 //
351 // Thus the list is chained as follows:
352 //
353 // ----> ----> ----> ----> ---->
354 // NONDEBUG NONDEBUG DEBUG DEBUG DEBUG NONDEBUG ...
355 // <---- ^ +-- <---- <---- ^ +--
356 // | | | |
357 // | +------------------------+ |
358 // | |
359 // +-----------------------------------+
360 using prev_insn_or_last_debug_insn = pointer_mux<insn_info>;
361 using next_nondebug_or_debug_insn = pointer_mux<insn_info>;
362
363 insn_info (bb_info *bb, rtx_insn *rtl, int cost_or_uid);
364
365 static void print_uid (pretty_printer *, int);
366
367 void calculate_cost () const;
368 void set_properties (const rtx_properties &);
369 void set_accesses (access_info **, unsigned int, unsigned int);
370 void copy_accesses (access_array, access_array);
371 void set_cost (unsigned int cost) { m_cost_or_uid = cost; }
372 void set_bb (bb_info *bb) { m_bb = bb; }
373
374 void add_note (insn_note *note);
375
376 order_node *get_order_node () const;
377 order_node *get_known_order_node () const;
378 int slow_compare_with (const insn_info &) const;
379
380 insn_info *last_debug_insn () const;
381
382 unsigned int point () const { return m_point; }
383 void copy_prev_from (insn_info *);
384 void copy_next_from (insn_info *);
385 void set_prev_sametype_insn (insn_info *);
386 void set_last_debug_insn (insn_info *);
387 void set_next_any_insn (insn_info *);
388 void set_point (unsigned int point) { m_point = point; }
389 void clear_insn_links ();
390 bool has_insn_links ();
391
392 // The values returned by the accessors above.
393 prev_insn_or_last_debug_insn m_prev_insn_or_last_debug_insn;
394 next_nondebug_or_debug_insn m_next_nondebug_or_debug_insn;
395 bb_info *m_bb;
396 rtx_insn *m_rtl;
397
398 // The list of definitions followed by the list of uses.
399 access_info **m_accesses;
400
401 // The number of definitions and the number uses. FIRST_PSEUDO_REGISTER + 1
402 // is the maximum number of accesses to hard registers and memory, and
403 // MAX_RECOG_OPERANDS is the maximum number of pseudos that can be
404 // defined by an instruction, so the number of definitions in a real
405 // instruction should fit easily in 16 bits. However, there are no
406 // limits on the number of definitions in artifical instructions.
407 unsigned int m_num_uses;
408 unsigned int m_num_defs;
409
410 // Flags returned by the accessors above.
411 unsigned int m_is_debug_insn : 1;
412 unsigned int m_can_be_optimized : 1;
413 unsigned int m_is_asm : 1;
414 unsigned int m_has_pre_post_modify : 1;
415 unsigned int m_has_volatile_refs : 1;
416
417 // For future expansion.
418 unsigned int m_spare : 27;
419
420 // The program point at which the instruction occurs.
421 //
422 // Note that the values of the program points are influenced by -g
423 // and so should not used to make codegen decisions.
424 unsigned int m_point;
425
426 // Negative if the instruction is artificial, nonnegative if it is real.
427 //
428 // For real instructions: the cost of the instruction, or UNKNOWN_COST
429 // if we haven't measured it yet.
430 //
431 // For artificial instructions: the (negative) unique identifier of the
432 // instruction.
433 mutable int m_cost_or_uid;
434
435 // On LP64 systems, there's a gap here that could be used for future
436 // expansion.
437
438 // The list of notes that have been attached to the instruction.
439 insn_note *m_first_note;
440 };
441
442 // Iterators for unfiltered lists of instructions.
443 using any_insn_iterator = list_iterator<insn_info, &insn_info::next_any_insn>;
444 using reverse_any_insn_iterator
445 = list_iterator<insn_info, &insn_info::prev_any_insn>;
446
447 // Iterators for nondebug instructions only.
448 using nondebug_insn_iterator
449 = list_iterator<insn_info, &insn_info::next_nondebug_insn>;
450 using reverse_nondebug_insn_iterator
451 = list_iterator<insn_info, &insn_info::prev_nondebug_insn>;
452
453 // A class that describes an inclusive range of instructions.
454 class insn_range_info
455 {
456 public:
457 insn_range_info () = default;
458
459 // Create a range that contains a singleton instruction.
460 insn_range_info (insn_info *insn) : first (insn), last (insn) {}
461
462 // Create a range [FIRST, LAST], given that *FIRST <= *LAST.
463 insn_range_info (insn_info *first, insn_info *last);
464
465 // Return true if the range contains at least one instruction.
466 explicit operator bool () const { return *first <= *last; }
467
468 bool operator== (const insn_range_info &) const;
469 bool operator!= (const insn_range_info &) const;
470
471 // If the range contains a single instruction, return that instruction,
472 // otherwise return null.
473 insn_info *singleton () const;
474
475 // Return true if the range includes INSN.
476 bool includes (insn_info *insn) const;
477
478 // If INSN is inside the range, return INSN, otherwise return the
479 // nearest in-range instruction.
480 insn_info *clamp_insn_to_range (insn_info *insn) const;
481
482 // Return true if this range is a subrange of OTHER, i.e. if OTHER
483 // includes every instruction that this range does.
484 bool is_subrange_of (const insn_range_info &other) const;
485
486 // The lower and upper bounds of the range.
487 insn_info *first;
488 insn_info *last;
489 };
490
491 // A class that represents a closure of operator== for instructions.
492 // This is used by insn_is; see there for details.
493 class insn_is_closure
494 {
495 public:
496 insn_is_closure (const insn_info *insn) : m_insn (insn) {}
497 bool operator() (const insn_info *other) const { return m_insn == other; }
498
499 private:
500 const insn_info *m_insn;
501 };
502
503 void pp_insn (pretty_printer *, const insn_info *);
504
505 }
506
507 void dump (FILE *, const rtl_ssa::insn_info *);
508
509 void DEBUG_FUNCTION debug (const rtl_ssa::insn_info *);