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 | |
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 | 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 | 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. |
448 | using any_insn_iterator = list_iterator<insn_info, &insn_info::next_any_insn>; |
449 | using reverse_any_insn_iterator |
450 | = list_iterator<insn_info, &insn_info::prev_any_insn>; |
451 | |
452 | // Iterators for nondebug instructions only. |
453 | using nondebug_insn_iterator |
454 | = list_iterator<insn_info, &insn_info::next_nondebug_insn>; |
455 | using 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. |
459 | class insn_range_info |
460 | { |
461 | public: |
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. |
498 | class insn_is_closure |
499 | { |
500 | public: |
501 | insn_is_closure (const insn_info *insn) : m_insn (insn) {} |
502 | bool operator() (const insn_info *other) const { return m_insn == other; } |
503 | |
504 | private: |
505 | const insn_info *m_insn; |
506 | }; |
507 | |
508 | void pp_insn (pretty_printer *, const insn_info *); |
509 | |
510 | } |
511 | |
512 | void dump (FILE *, const rtl_ssa::insn_info *); |
513 | |
514 | void DEBUG_FUNCTION debug (const rtl_ssa::insn_info *); |
515 | |