Branch data Line data Source code
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 : 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 : 59053800 : 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 : 309248162 : 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 : 4 : bool is_real () const { return m_cost_or_uid >= 0; }
182 : :
183 : : // Return the opposite of is_real ().
184 : 424372569 : 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 : 1952164787 : 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 : 251235311 : 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 : 0 : 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 : 112408427 : 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 : 427997753 : 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 : 2980495 : unsigned int num_uses () const { return m_num_uses; }
277 : :
278 : : // The number of entries in defs ().
279 : 2980495 : 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 : 0 : 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 : 0 : 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 : : // 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 : 2980495 : void set_cost (unsigned int cost) { m_cost_or_uid = cost; }
374 : 0 : 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 : 249260047 : 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 : 249260047 : 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 : 30200567 : 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 : 111746560 : 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 : 43834124 : insn_is_closure (const insn_info *insn) : m_insn (insn) {}
502 : 202380440 : 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 *);
|
