Branch data Line data Source code
1 : : // Access-related classes for RTL SSA -*- 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 : : // Forward declarations.
23 : : class bb_info;
24 : : class clobber_group;
25 : : class def_node;
26 : : class ebb_info;
27 : : class insn_info;
28 : : class phi_info;
29 : : class set_info;
30 : :
31 : : // Used as a boolean argunent to certain routines.
32 : : enum class ignore_clobbers { NO, YES };
33 : :
34 : : // Represents something that the SSA form tracks: either a register
35 : : // or memory.
36 : : class resource_info
37 : : {
38 : : public:
39 : : // Return true if this resource represents memory.
40 : 0 : bool is_mem () const { return regno == MEM_REGNO; }
41 : :
42 : : // Return true if this resource represents a register.
43 : : bool is_reg () const { return regno != MEM_REGNO; }
44 : :
45 : : // Print the name of the resource to PP.
46 : : void print_identifier (pretty_printer *pp) const;
47 : :
48 : : // Possibly print additional information about the resource to PP.
49 : : void print_context (pretty_printer *pp) const;
50 : :
51 : : // A combination of print_identifier and print_context.
52 : : void print (pretty_printer *pp) const;
53 : :
54 : : // The mode with which the resource is being defined or used. This is
55 : : // always BLKmode for memory. It can also be BLKmode for registers if
56 : : // we don't yet know the real mode, or if the mode is not relevant for
57 : : // some reason.
58 : : machine_mode mode;
59 : :
60 : : // The pseudo register or single hard register that the resource represents,
61 : : // or MEM_REGNO for memory.
62 : : unsigned int regno;
63 : : };
64 : :
65 : : // For simplicity, we treat memory as a single unified entity.
66 : : const resource_info memory = { E_BLKmode, MEM_REGNO };
67 : :
68 : : // Flags used when printing access_infos.
69 : : //
70 : : // Print the location at which the access occurs. This is redundant
71 : : // when the access is being printed as part of the instruction or phi node
72 : : // that contains the access.
73 : : const unsigned int PP_ACCESS_INCLUDE_LOCATION = 1U << 0;
74 : : //
75 : : // Print links to other accesses: the definition that defines a use,
76 : : // the uses of a definition, and the inputs of a phi node.
77 : : const unsigned int PP_ACCESS_INCLUDE_LINKS = 1U << 1;
78 : : //
79 : : // Print additional properties about the access.
80 : : const unsigned int PP_ACCESS_INCLUDE_PROPERTIES = 1U << 2;
81 : : //
82 : : // The usual flags when printing an access in isolation.
83 : : const unsigned int PP_ACCESS_DEFAULT = (PP_ACCESS_INCLUDE_LOCATION
84 : : | PP_ACCESS_INCLUDE_LINKS
85 : : | PP_ACCESS_INCLUDE_PROPERTIES);
86 : : //
87 : : // The usual flags when printing a def_info from its defining instruction.
88 : : const unsigned int PP_ACCESS_SETTER = (PP_ACCESS_INCLUDE_LINKS
89 : : | PP_ACCESS_INCLUDE_PROPERTIES);
90 : : //
91 : : // The usual flags when printing a use_info from its user.
92 : : const unsigned int PP_ACCESS_USER = PP_ACCESS_INCLUDE_PROPERTIES;
93 : :
94 : : // The various ways of accessing a resource. The two range checks that
95 : : // we need to perform are [SET, PHI] (for set_info) and [SET, CLOBBER]
96 : : // (for def_info), so the ordering tries to make those tests as
97 : : // efficient as possible.
98 : : enum class access_kind : uint8_t
99 : : {
100 : : // Set the resource to a useful value.
101 : : SET,
102 : :
103 : : // A form of SET that collects the possible incoming values of the
104 : : // resource using a phi node; the resource does not actually change value.
105 : : PHI,
106 : :
107 : : // Set the resource to a value that is both unknown and not useful.
108 : : CLOBBER,
109 : :
110 : : // Use the current value of the resource.
111 : : USE
112 : : };
113 : :
114 : : // A base class that represents an access to a resource.
115 : : class access_info
116 : : {
117 : : // Size: 1 LP64 word
118 : : friend class function_info;
119 : :
120 : : public:
121 : : // Return the resource that is being accessed.
122 : 114978660 : resource_info resource () const { return { m_mode, m_regno }; }
123 : :
124 : : // Return true if the access is to memory.
125 : 298052934 : bool is_mem () const { return m_regno == MEM_REGNO; }
126 : :
127 : : // Return true if the access is to a register.
128 : 101754618 : bool is_reg () const { return m_regno != MEM_REGNO; }
129 : :
130 : : // If the access is to a register, return the register number,
131 : : // otherwise return MEM_REGNO.
132 : 2707798089 : unsigned int regno () const { return m_regno; }
133 : :
134 : : // For sets, return the mode of the value to which the resource is being set.
135 : : // For uses, return the mode in which the resource is being used (which for
136 : : // hard registers might be different from the mode in which the resource
137 : : // was set).
138 : : //
139 : : // When accessing memory, the mode is always BLKmode. When accessing
140 : : // pseudo registers, the mode is always the mode of the pseudo register
141 : : // (and so doesn't, for example, take subregs into account).
142 : 291766882 : machine_mode mode () const { return m_mode; }
143 : :
144 : : // Return the kind of access that this is.
145 : 3929224092 : access_kind kind () const { return m_kind; }
146 : :
147 : : // Return true if the access occurs in a phi node or an "artificial"
148 : : // instruction (see insn_info), false if it occurs in a real instruction.
149 : 50098444 : bool is_artificial () const { return m_is_artificial; }
150 : :
151 : : // Return the opposite of is_artificial.
152 : : bool is_real () const { return !m_is_artificial; }
153 : :
154 : : // Return true if this access is a set_info whose result is used by at least
155 : : // one nondebug instruction.
156 : : bool is_set_with_nondebug_insn_uses () const;
157 : :
158 : : // Return true if the access describes a set_info and if the value
159 : : // is defined by an RTX_AUTOINC rtx.
160 : : bool is_pre_post_modify () const { return m_is_pre_post_modify; }
161 : :
162 : : // Return true if the access is a clobber_info that describes the effect
163 : : // of a called function. This kind of clobber is added for -fipa-ra
164 : : // functions that clobber only a strict subset of the normal ABI set.
165 : 971523 : bool is_call_clobber () const { return m_is_call_clobber; }
166 : :
167 : : // Return true if the access is a use_info that simply marks a point in
168 : : // the live range of a set_info at which the value is live out from
169 : : // the containing EBB.
170 : 138085455 : bool is_live_out_use () const { return m_is_live_out_use; }
171 : :
172 : : // Return true if the access is a use_info for an instruction and if
173 : : // at least some of the uses occur within a MEM address.
174 : : //
175 : : // There shouldn't be a need to check whether *all* uses occur within
176 : : // a MEM address, since in principle:
177 : : //
178 : : // A: (set (reg:SI R1) (mem:SI (post_inc:SI (reg:SI R2))))
179 : : //
180 : : // should be semantically equivalent to:
181 : : //
182 : : // B: (parallel [(set (reg:SI R1) (mem:SI (reg:SI R2)))
183 : : // (set (reg:SI R2) (plus:SI (reg:SI R2) (const_int 4)))])
184 : : //
185 : : // even though R2 occurs only in MEMs for A but occurs outside MEMs for B.
186 : 151728241 : bool includes_address_uses () const { return m_includes_address_uses; }
187 : :
188 : : // Return true if the access occurs in an instruction and if at least
189 : : // some accesses to resource () occur in a read-modify-write context.
190 : : // This is equivalent to the DF_REF_READ_WRITE flag.
191 : 148126973 : bool includes_read_writes () const { return m_includes_read_writes; }
192 : :
193 : : // Return true if the access occurs in an instruction and if at least
194 : : // some accesses to resource () occur in a subreg context.
195 : 49362953 : bool includes_subregs () const { return m_includes_subregs; }
196 : :
197 : : // Return true if the access occurs in an instruction and if at least
198 : : // some accesses to resource () occur in a multi-register REG.
199 : : // This implies that resource () is a hard register.
200 : 140774881 : bool includes_multiregs () const { return m_includes_multiregs; }
201 : :
202 : : // Return true if the access occurs in a real nondebug instruction
203 : : // and if all accesses to resource () occur in notes, rather than
204 : : // in the main instruction pattern.
205 : 149545443 : bool only_occurs_in_notes () const { return m_only_occurs_in_notes; }
206 : :
207 : : // Return true if this is a temporary access, e.g. one created for
208 : : // an insn that is about to be inserted.
209 : 80216917 : bool is_temporary () const { return m_is_temp; }
210 : :
211 : : protected:
212 : : access_info (resource_info, access_kind);
213 : :
214 : : void print_prefix_flags (pretty_printer *) const;
215 : : void print_properties_on_new_lines (pretty_printer *) const;
216 : :
217 : : private:
218 : 94088154 : void set_mode (machine_mode mode) { m_mode = mode; }
219 : :
220 : : // The values returned by the accessors above.
221 : : unsigned int m_regno;
222 : : machine_mode m_mode : MACHINE_MODE_BITSIZE;
223 : : access_kind m_kind : 2;
224 : :
225 : : protected:
226 : : // The value returned by the accessors above.
227 : : unsigned int m_is_artificial : 1;
228 : : unsigned int m_is_set_with_nondebug_insn_uses : 1;
229 : : unsigned int m_is_pre_post_modify : 1;
230 : : unsigned int m_is_call_clobber : 1;
231 : : unsigned int m_is_live_out_use : 1;
232 : : unsigned int m_includes_address_uses : 1;
233 : : unsigned int m_includes_read_writes : 1;
234 : : unsigned int m_includes_subregs : 1;
235 : : unsigned int m_includes_multiregs : 1;
236 : : unsigned int m_only_occurs_in_notes : 1;
237 : :
238 : : // True if this access is a use_insn that occurs in a nondebug instruction,
239 : : // and if there are no following uses by nondebug instructions. The next use
240 : : // is null, a use_info for a debug instruction, or a use_info for a phi node.
241 : : //
242 : : // Providing this helps to optimize use_info::next_nondebug_insn_use.
243 : : unsigned int m_is_last_nondebug_insn_use : 1;
244 : :
245 : : // True if this access is a use_info for a debug instruction or
246 : : // a phi node.
247 : : unsigned int m_is_in_debug_insn_or_phi : 1;
248 : :
249 : : private:
250 : : // Used as a flag during various update routines; has no long-lasting
251 : : // meaning.
252 : : unsigned int m_has_been_superceded : 1;
253 : :
254 : : // Indicates that this access has been allocated on the function_info's
255 : : // temporary obstack and so is not (yet) part of the proper SSA form.
256 : : unsigned int m_is_temp : 1;
257 : : };
258 : :
259 : : // A contiguous array of access_info pointers. Used to represent a
260 : : // (mostly small) number of definitions and/or uses.
261 : : using access_array = array_slice<access_info *const>;
262 : :
263 : : // A class for building an access_array on an obstack. It automatically
264 : : // frees any in-progress array if the build attempt fails before finish ()
265 : : // has been called.
266 : 68668807 : class access_array_builder : public obstack_watermark
267 : : {
268 : : public:
269 : 68668807 : using obstack_watermark::obstack_watermark;
270 : :
271 : : // Make sure that the array has enough for NUM_ACCESSES accesses.
272 : : void reserve (unsigned int num_accesses);
273 : :
274 : : // Add ACCESS to the end of the array that we're building, given that
275 : : // reserve () has already made room.
276 : : void quick_push (access_info *access);
277 : :
278 : : // Finish and return the new array. The array survives the destruction
279 : : // of the builder.
280 : : array_slice<access_info *> finish ();
281 : : };
282 : :
283 : : // An access_info that represents the use of a resource in either a phi node
284 : : // or an instruction. It records which set_info (if any) provides the
285 : : // resource's value.
286 : : class use_info : public access_info
287 : : {
288 : : // Overall size: 5 LP64 words.
289 : : friend class set_info;
290 : : friend class function_info;
291 : :
292 : : public:
293 : : // Return true if the access occurs in an instruction rather than a phi node.
294 : : // The instruction might be a debug instruction or a nondebug instruction.
295 : 628689756 : bool is_in_any_insn () const { return m_insn_or_phi.is_first (); }
296 : :
297 : : // Return true if the access occurs in a nondebug instruction,
298 : : // false if it occurs in a debug instruction or a phi node.
299 : 3713869524 : bool is_in_nondebug_insn () const { return !m_is_in_debug_insn_or_phi; }
300 : :
301 : : // Return true if the instruction occurs in a debug instruction.
302 : : bool is_in_debug_insn () const;
303 : :
304 : : // Return true if the access occurs in a phi node rather than in an
305 : : // instruction.
306 : 844554046 : bool is_in_phi () const { return m_insn_or_phi.is_second (); }
307 : :
308 : : // Return true if the access occurs in a debug instruction or a phi node,
309 : : // false if it occurs in a nondebug instruction.
310 : 781418181 : bool is_in_debug_insn_or_phi () const { return m_is_in_debug_insn_or_phi; }
311 : :
312 : : // Return the instruction that uses the resource. Only valid is
313 : : // is_in_any_insn ().
314 : 1447160111 : insn_info *insn () const { return m_insn_or_phi.known_first (); }
315 : :
316 : : // Return the phi node that uses the resource. Only valid if is_in_phi ().
317 : 33781476 : phi_info *phi () const { return m_insn_or_phi.known_second (); }
318 : :
319 : : // Return the basic block that contains the access.
320 : : bb_info *bb () const;
321 : :
322 : : // Return the extended basic block that contains the access.
323 : : ebb_info *ebb () const;
324 : :
325 : : // Return the set_info whose result the access uses, or null if the
326 : : // value of the resource is completely undefined.
327 : : //
328 : : // The value is undefined if the use is completely upwards exposed
329 : : // (i.e. has no preceding definition) or if the preceding definition
330 : : // is a clobber rather than a set.
331 : : //
332 : : // The mode of the definition can be different from the mode of the use;
333 : : // for example, a hard register might be set in DImode and used in SImode.
334 : 1953566102 : set_info *def () const { return m_def; }
335 : :
336 : : // Return the previous and next uses of the definition. See set_info
337 : : // for details about the ordering.
338 : : //
339 : : // These routines are only meaningful when def () is nonnull.
340 : : use_info *prev_use () const;
341 : : use_info *next_use () const;
342 : :
343 : : // Return the next use by a nondebug instruction, or null if none.
344 : : //
345 : : // This is only valid if is_in_nondebug_insn (). It is equivalent to,
346 : : // but more efficient than:
347 : : //
348 : : // next_use () && next_use ()->is_in_nondebug_insn ()
349 : : // ? next_use () : nullptr
350 : : use_info *next_nondebug_insn_use () const;
351 : :
352 : : // Return the next use by an instruction, or null if none. The use might
353 : : // be by a debug instruction or a nondebug instruction.
354 : : //
355 : : // This is only valid if is_in_any_insn (). It is equivalent to:
356 : : //
357 : : // next_use () && next_use ()->is_in_any_insn () ? next_use () : nullptr
358 : : use_info *next_any_insn_use () const;
359 : :
360 : : // Return the next use by a debug instruction, or null if none.
361 : : // This is only valid if is_in_debug_insn ().
362 : : use_info *next_debug_insn_use () const;
363 : :
364 : : // Return the previous use by a phi node in the list, or null if none.
365 : : //
366 : : // This is only valid if is_in_phi (). It is equivalent to:
367 : : //
368 : : // prev_use () && prev_use ()->is_in_phi () ? prev_use () : nullptr
369 : : use_info *prev_phi_use () const;
370 : :
371 : : // Return true if this is the first use of the definition. See set_info
372 : : // for details about the ordering.
373 : : //
374 : : // This routine is only meaningful when def () is nonnull.
375 : : bool is_first_use () const;
376 : :
377 : : // Return true if this is the last use of the definition. See set_info
378 : : // for details about the ordering.
379 : : //
380 : : // This routine is only meaningful when def () is nonnull.
381 : : bool is_last_use () const;
382 : :
383 : : // Print a description of def () to PP.
384 : : void print_def (pretty_printer *pp) const;
385 : :
386 : : // Print a description of the location of the use to PP.
387 : : void print_location (pretty_printer *pp) const;
388 : :
389 : : // Print a description of the use to PP under the control of
390 : : // PP_ACCESS_* flags FLAGS.
391 : : void print (pretty_printer *pp,
392 : : unsigned int flags = PP_ACCESS_DEFAULT) const;
393 : :
394 : : private:
395 : : // If we only create a set_info splay tree for sets that are used by
396 : : // three instructions or more, then only about 16% of uses need to be in
397 : : // a splay tree. It is therefore more memory-efficient to use separate
398 : : // nodes for the splay tree, instead of storing the child nodes
399 : : // directly in the use_info.
400 : :
401 : : // Make insn_info the first (and thus directly-encoded) choice since
402 : : // insn () is read much more often than phi ().
403 : : using insn_or_phi = pointer_mux<insn_info, phi_info>;
404 : :
405 : : // The use belongs to a list that is partitioned into three sections:
406 : : //
407 : : // (1) all uses in nondebug instructions, in reverse postorder
408 : : //
409 : : // (2) all uses in debug instructions, in reverse postorder
410 : : //
411 : : // (3) all phi nodes, in no particular order.
412 : : //
413 : : // In order to preserve memory:
414 : : //
415 : : // - The set_info just has a pointer to the first use.
416 : : //
417 : : // - The first use's "prev" pointer points to the last use.
418 : : //
419 : : // - The last use's "next" pointer points to the last use in a nondebug
420 : : // instruction, or null if there are no such uses.
421 : : using last_use_or_prev_use = pointer_mux<use_info>;
422 : : using last_nondebug_insn_use_or_next_use = pointer_mux<use_info>;
423 : :
424 : : use_info (insn_or_phi, resource_info, set_info *);
425 : :
426 : : use_info *last_use () const;
427 : : use_info *last_nondebug_insn_use () const;
428 : : bool calculate_is_last_nondebug_insn_use () const;
429 : :
430 : : void record_reference (rtx_obj_reference, bool);
431 : : void set_insn (insn_info *);
432 : 37728463 : void set_def (set_info *set) { m_def = set; }
433 : 46839009 : void set_is_live_out_use (bool value) { m_is_live_out_use = value; }
434 : : void copy_prev_from (use_info *);
435 : : void copy_next_from (use_info *);
436 : : void set_last_use (use_info *);
437 : : void set_prev_use (use_info *);
438 : : void set_last_nondebug_insn_use (use_info *);
439 : : void set_next_use (use_info *);
440 : : void clear_use_links ();
441 : : bool has_use_links ();
442 : : bool check_integrity ();
443 : :
444 : : // The location of the use.
445 : : insn_or_phi m_insn_or_phi;
446 : :
447 : : // The overloaded "prev" and "next" pointers, as described above.
448 : : last_use_or_prev_use m_last_use_or_prev_use;
449 : : last_nondebug_insn_use_or_next_use m_last_nondebug_insn_use_or_next_use;
450 : :
451 : : // The value of def ().
452 : : set_info *m_def;
453 : : };
454 : :
455 : : // Iterators for lists of uses.
456 : : using use_iterator = list_iterator<use_info, &use_info::next_use>;
457 : : using reverse_use_iterator = list_iterator<use_info, &use_info::prev_use>;
458 : :
459 : : // Like use_iterator, but specifically for uses by nondebug instructions,
460 : : // uses by any kind of instruction, and uses by phi nodes respectively.
461 : : // These iterators allow a nullptr end point even if there are other types
462 : : // of use in the same definition.
463 : : using nondebug_insn_use_iterator
464 : : = list_iterator<use_info, &use_info::next_nondebug_insn_use>;
465 : : using debug_insn_use_iterator
466 : : = list_iterator<use_info, &use_info::next_debug_insn_use>;
467 : : using any_insn_use_iterator
468 : : = list_iterator<use_info, &use_info::next_any_insn_use>;
469 : : using phi_use_iterator = list_iterator<use_info, &use_info::prev_phi_use>;
470 : :
471 : : // A view of an access_array in which every entry is known to be a use_info.
472 : : using use_array = const_derived_container<use_info *, access_array>;
473 : :
474 : : // An access_info that describes a definition of a resource. The definition
475 : : // can be a set or a clobber; the difference is that a set provides a known
476 : : // and potentially useful value, while a clobber provides an unknown and
477 : : // unusable value.
478 : : //
479 : : // Every definition is associated with an insn_info. All definitions of
480 : : // a given resource are stored in a linked list, maintained in reverse
481 : : // postorder.
482 : : class def_info : public access_info
483 : : {
484 : : // Overall size: 4 LP64 words
485 : : friend class function_info;
486 : : friend class clobber_group;
487 : :
488 : : public:
489 : : // Return the instruction that contains the definition.
490 : 1090321543 : insn_info *insn () const { return m_insn; }
491 : :
492 : : // Return the basic block that contains the definition.
493 : : bb_info *bb () const;
494 : :
495 : : // Return the extended basic block that contains the access.
496 : : ebb_info *ebb () const;
497 : :
498 : : // Return the previous and next definitions of the same resource,
499 : : // in reverse postorder, or null if no such definition exists.
500 : : def_info *prev_def () const;
501 : : def_info *next_def () const;
502 : :
503 : : // Return true if this is the first definition in the list.
504 : : bool is_first_def () const;
505 : :
506 : : // Return true if this is the last definition in the list.
507 : : bool is_last_def () const;
508 : :
509 : : // Print the location of the definition to PP.
510 : : void print_location (pretty_printer *pp) const;
511 : :
512 : : // Print a unique identifier for this definition to PP. The identifier has
513 : : // the form <resource>:<insn uid>.
514 : : void print_identifier (pretty_printer *pp) const;
515 : :
516 : : protected:
517 : : def_info (insn_info *insn, resource_info resource, access_kind kind);
518 : :
519 : : private:
520 : : // In order to preserve memory, the list head only points to the first
521 : : // definition in the list. The "prev" entry of the first definition
522 : : // then points to the last definition.
523 : : using last_def_or_prev_def = pointer_mux<def_info>;
524 : :
525 : : // For similar memory-saving reasons, if we want to create a splay tree
526 : : // of accesses to a resource, we hang the root off the "next" entry of
527 : : // the last definition in the list.
528 : : using splay_root_or_next_def = pointer_mux<def_node, def_info>;
529 : :
530 : 9522752 : void set_insn (insn_info *insn) { m_insn = insn; }
531 : :
532 : : def_info *last_def () const;
533 : : def_node *splay_root () const;
534 : :
535 : : void record_reference (rtx_obj_reference, bool);
536 : : void copy_prev_from (def_info *);
537 : : void copy_next_from (def_info *);
538 : : void set_last_def (def_info *);
539 : : void set_prev_def (def_info *);
540 : : void set_splay_root (def_node *);
541 : : void set_next_def (def_info *);
542 : : void clear_def_links ();
543 : : bool has_def_links ();
544 : :
545 : : // The location of the definition.
546 : : insn_info *m_insn;
547 : :
548 : : // The overloaded "prev" and "next" pointers, as described above.
549 : : last_def_or_prev_def m_last_def_or_prev_def;
550 : : splay_root_or_next_def m_splay_root_or_next_def;
551 : : };
552 : :
553 : : // Iterators for lists of definitions.
554 : : using def_iterator = list_iterator<def_info, &def_info::next_def>;
555 : : using reverse_def_iterator = list_iterator<def_info, &def_info::prev_def>;
556 : :
557 : : // A view of an access_array in which every entry is known to be a
558 : : // def_info.
559 : : using def_array = const_derived_container<def_info *, access_array>;
560 : :
561 : : // A def_info that sets the resource to a value that is both
562 : : // unknown and not useful. This is only ever used for registers,
563 : : // since memory always has some useful contents.
564 : : //
565 : : // Neighboring clobbers are grouped into clobber_groups, so that it's
566 : : // possibly to skip over all neighboring clobbers in a single step.
567 : : class clobber_info : public def_info
568 : : {
569 : : // Overall size: 8 LP64 words
570 : : friend class default_splay_tree_accessors<clobber_info *>;
571 : : friend class default_splay_tree_accessors_with_parent<clobber_info *>;
572 : : friend class function_info;
573 : : friend class clobber_group;
574 : :
575 : : public:
576 : : using splay_tree = default_rootless_splay_tree<clobber_info *>;
577 : :
578 : : // Return true if the clobber belongs to a clobber_group, false if it
579 : : // is standalone.
580 : 84667066 : bool is_in_group () const { return m_group; }
581 : :
582 : : // Return the group that the clobber is in, or null if none.
583 : : //
584 : : // Complexity: amortized O(1), worst case O(N), where N is the number
585 : : // of clobbers in the containing clobber_group.
586 : : clobber_group *group () const;
587 : :
588 : : // Print a description of the clobber to PP under the control of
589 : : // PP_ACCESS_* flags FLAGS.
590 : : void print (pretty_printer *pp,
591 : : unsigned int flags = PP_ACCESS_DEFAULT) const;
592 : :
593 : : private:
594 : : // Once normal call clobbers are taken out of the equation by
595 : : // insn_call_clobbers_notes, clobber_infos account for roughly 6% of all
596 : : // def_infos, with the rest being set_infos. clobber_infos are
597 : : // therefore much less size-sensitive than set_infos are.
598 : : //
599 : : // As noted above, we want to group neighboring clobbers together so that
600 : : // we can quickly step over them to find the previous or next "real" set.
601 : : // We also want to be able to split the group in sublinear time,
602 : : // for example when inserting a set/use pair between two clobbers
603 : : // in a group.
604 : : //
605 : : // So:
606 : : //
607 : : // - Clobbers need to have ready access to their group, so that we
608 : : // can cheaply skip over the whole group. This means that they
609 : : // need a group pointer.
610 : : //
611 : : // - We need to be able to update the group pointer lazily, so that
612 : : // the cost of updating it is counted against accesses to the clobbers
613 : : // that need updating.
614 : : //
615 : : // We also want to be able to insert clobbers into a group in
616 : : // amortized logarithmic time.
617 : : //
618 : : // We therefore use a splay tree to represent the clobbers in a group,
619 : : // with the nodes storing their parent node. It is then possible to
620 : : // perform splay operations without first getting hold of the root.
621 : : // The root of the splay tree always has a valid, up-to-date group,
622 : : // so lazy group updates can get the new group from there.
623 : : //
624 : : // Roughly 90% of clobbers have a neighboring definition in the same
625 : : // block, which means that most need to be stored in a splay tree.
626 : : // We therefore store the splay tree fields directly in the clobber_info
627 : : // rather than using a separate node object.
628 : :
629 : : clobber_info (insn_info *, unsigned int);
630 : :
631 : 1137692 : void set_group (clobber_group *group) { m_group = group; }
632 : : void update_group (clobber_group *);
633 : : clobber_group *recompute_group ();
634 : :
635 : : // The child and parent nodes in the splay tree.
636 : : clobber_info *m_children[2];
637 : : clobber_info *m_parent;
638 : :
639 : : // The last known value of group (), which might now be out of date.
640 : : clobber_group *m_group;
641 : : };
642 : :
643 : : using clobber_tree = clobber_info::splay_tree::rooted;
644 : :
645 : : // A def_info that sets the resource to a useful value. It records
646 : : // all uses of the value in a linked list. The list is partitioned
647 : : // into three sections:
648 : : //
649 : : // (1) all uses by nondebug instructions, in reverse postorder, followed by
650 : : // (2) all uses by debug instructions, in reverse postorder, followed by
651 : : // (3) all uses by phi nodes, in no particular order.
652 : : //
653 : : // There are two cases:
654 : : //
655 : : // - If we know in advance that there is a single definition of a resource R
656 : : // and therefore decide not to use phi nodes for R, (1) and (2) contain
657 : : // all uses of R, regardless of which blocks contain the uses. (3) is
658 : : // then empty.
659 : : //
660 : : // - Otherwise, (1) only contains uses in the same extended basic block
661 : : // as the definition, and it is terminated by a use that marks the end
662 : : // of the live range for the EBB. In other words, if the resource dies
663 : : // in the EBB, the last use by a nondebug instruction marks the point at
664 : : // which it dies, otherwise there is a fake live-out use at the end of
665 : : // the EBB.
666 : : //
667 : : // Since debug instructions should not affect codegen, they opportunisticly
668 : : // attach to the same set_info as nondebug instructions where possible.
669 : : // If a nondebug instruction would attach to a degenerate phi and if no
670 : : // such phi exists, debug instructions instead attach to whichever set_info
671 : : // provides the value, regardless of where that set_info is.
672 : : class set_info : public def_info
673 : : {
674 : : // Overall size: 6 LP64 words.
675 : : friend class function_info;
676 : : using use_splay_tree = splay_tree<use_info *>;
677 : :
678 : : public:
679 : : // Return the first and last uses of the set, or null if the list is empty.
680 : : // See the comment above for details about the order.
681 : 947717317 : use_info *first_use () const { return m_first_use; }
682 : : use_info *last_use () const;
683 : :
684 : : // Return the first and last uses of the set by nondebug instructions,
685 : : // or null if there are no such uses. The uses are in reverse postorder.
686 : : use_info *first_nondebug_insn_use () const;
687 : : use_info *last_nondebug_insn_use () const;
688 : :
689 : : // Return the first use of the set by debug instructions, or null if
690 : : // there is no such use.
691 : : use_info *first_debug_insn_use () const;
692 : :
693 : : // Return the first use of the set by any kind of instruction, or null
694 : : // if there are no such uses. The uses are in the order described above.
695 : : use_info *first_any_insn_use () const;
696 : :
697 : : // Return the last use of the set by phi inputs, or null if there are no
698 : : // such uses. The phi input uses are in no particular order.
699 : : use_info *last_phi_use () const;
700 : :
701 : : // Return true if at least one nondebug instruction or phi node uses
702 : : // the set's result. This is equivalent to testing whether the set is
703 : : // ever live.
704 : : bool has_nondebug_uses () const;
705 : :
706 : : // Return true if anything uses the set's result. Note that this includes
707 : : // uses by debug instructions, so it should not be used for optimization
708 : : // decisions.
709 : 10448910 : bool has_any_uses () const { return m_first_use; }
710 : :
711 : : // Return true if at least one nondebug instruction uses the set's result.
712 : : bool has_nondebug_insn_uses () const;
713 : :
714 : : // Return true if at least one phi node uses the set's result.
715 : : bool has_phi_uses () const;
716 : :
717 : : // If there is exactly one nondebug use of the set's result, return that use,
718 : : // otherwise return null. The use might be in an instruction or in a phi
719 : : // node.
720 : : use_info *single_nondebug_use () const;
721 : :
722 : : // If exactly one nondebug instruction uses the set's result, return the use
723 : : // by that instruction, otherwise return null.
724 : : use_info *single_nondebug_insn_use () const;
725 : :
726 : : // If exactly one phi node uses the set's result, return the use by that phi
727 : : // node, otherwise return null.
728 : : use_info *single_phi_use () const;
729 : :
730 : : // Return true if the set and its uses are contained within a single
731 : : // extended basic block, with the set coming first. This implies
732 : : // that all uses are by instructions rather than phi nodes.
733 : : bool is_local_to_ebb () const;
734 : :
735 : : // List all the uses of the set, in the order described above.
736 : : iterator_range<use_iterator> all_uses () const;
737 : :
738 : : // Return uses () in reverse order.
739 : : iterator_range<reverse_use_iterator> reverse_all_uses () const;
740 : :
741 : : // List the uses of the set by nondebug instructions, in reverse postorder.
742 : : iterator_range<nondebug_insn_use_iterator> nondebug_insn_uses () const;
743 : :
744 : : // List the uses of the set by debug instructions, in reverse postorder.
745 : : iterator_range<debug_insn_use_iterator> debug_insn_uses () const;
746 : :
747 : : // Return nondebug_insn_uses () in reverse order.
748 : : iterator_range<reverse_use_iterator> reverse_nondebug_insn_uses () const;
749 : :
750 : : // List the uses of the set by any kind of instruction. The list follows
751 : : // the order described above.
752 : : iterator_range<any_insn_use_iterator> all_insn_uses () const;
753 : :
754 : : // List the uses of the set by phi nodes, in no particular order.
755 : : // There is therefore no reversed equivalent of this list.
756 : : iterator_range<phi_use_iterator> phi_uses () const;
757 : :
758 : : // Print a description of the set to PP under the control of
759 : : // PP_ACCESS_* flags FLAGS.
760 : : void print (pretty_printer *pp,
761 : : unsigned int flags = PP_ACCESS_DEFAULT) const;
762 : :
763 : : protected:
764 : : set_info (insn_info *, resource_info, access_kind);
765 : :
766 : : // Print information about uses () to PP, continuing information printed
767 : : // about the set itself.
768 : : void print_uses_on_new_lines (pretty_printer *pp) const;
769 : :
770 : : private:
771 : : // Sets (including phis) account for about 94% of all definitions
772 : :
773 : : set_info (insn_info *, resource_info);
774 : :
775 : : void set_first_use (use_info *);
776 : :
777 : : // The first use in the list.
778 : : use_info *m_first_use;
779 : :
780 : : // The root of a splay tree of all uses, built lazily when we first
781 : : // think it's needed.
782 : : use_splay_tree m_use_tree;
783 : : };
784 : :
785 : : // A set_info for an on-the-side phi node. The phi node is attached
786 : : // to an extended basic block EBB and has one input for each incoming edge.
787 : : // The inputs are represented as an array of use_infos, with input I
788 : : // corresponding to EDGE_PRED (EBB->first_bb ()->cfg_bb (), I).
789 : : //
790 : : // Each phi node has a densely-allocated unique identifier, which is intended
791 : : // to be suitable for bitmaps or sbitmaps.
792 : : //
793 : : // All the phi nodes in an extended basic block are chained together
794 : : // into a linked list. The list has no particular order.
795 : : class phi_info : public set_info
796 : : {
797 : : // Overall size: 8 LP64 words
798 : : friend class function_info;
799 : :
800 : : public:
801 : : // Return the previous and next phi nodes in the extended basic block's list,
802 : : // or null if none.
803 : 6670965 : phi_info *prev_phi () const { return m_prev_phi; }
804 : 117339954 : phi_info *next_phi () const { return m_next_phi; }
805 : :
806 : : // Return the number of phi inputs. This is 1 for degenerate phis,
807 : : // otherwise it is equal to the number of incoming edges.
808 : : unsigned int num_inputs () const { return m_num_inputs; }
809 : :
810 : : // Return true if the phi node is degenerate, i.e. if it has only a
811 : : // single input.
812 : 126158335 : bool is_degenerate () const { return m_num_inputs == 1; }
813 : :
814 : : // Return the phi node's unique identifier.
815 : 235630621 : unsigned int uid () const { return m_uid; }
816 : :
817 : : // Return the array of inputs. For degenerate phi nodes, this array contains
818 : : // a single element, otherwise it has one input per incoming edge,
819 : : // with element E corresponding to incoming edge E.
820 : : use_array inputs () const;
821 : :
822 : : // Return the use_info that describes the phi input for incoming edge E.
823 : : use_info *input_use (unsigned int e) const;
824 : :
825 : : // Return the value of resource () on incoming edge E, or null if the
826 : : // value is completely undefined for that edge.
827 : : set_info *input_value (unsigned int e) const;
828 : :
829 : : // Print a description of the phi node to PP under the control of
830 : : // PP_ACCESS_* flags FLAGS.
831 : : void print (pretty_printer *pp,
832 : : unsigned int flags = PP_ACCESS_DEFAULT) const;
833 : :
834 : : private:
835 : : phi_info (insn_info *insn, resource_info resource, unsigned int uid);
836 : :
837 : : void make_degenerate (use_info *);
838 : : void set_inputs (use_array inputs);
839 : 33367506 : void set_prev_phi (phi_info *prev_phi) { m_prev_phi = prev_phi; }
840 : 60619104 : void set_next_phi (phi_info *next_phi) { m_next_phi = next_phi; }
841 : 6670965 : void clear_phi_links () { m_prev_phi = m_next_phi = nullptr; }
842 : : bool has_phi_links () { return m_prev_phi || m_next_phi; }
843 : :
844 : : // The values returned by the accessors above.
845 : : unsigned int m_uid;
846 : : unsigned int m_num_inputs;
847 : : union
848 : : {
849 : : access_info *const *m_inputs;
850 : : access_info *m_single_input;
851 : : };
852 : : phi_info *m_prev_phi;
853 : : phi_info *m_next_phi;
854 : : };
855 : :
856 : : // An iterator for lists of phi nodes.
857 : : using phi_iterator = list_iterator<phi_info, &phi_info::next_phi>;
858 : :
859 : : // One node in a splay tree of definitions. This base class represents
860 : : // a single def_info, but it is structured to allow derived classes
861 : : // to add a range.
862 : : class def_node
863 : : {
864 : : // Size: 3 LP64 words.
865 : : friend class function_info;
866 : : friend class default_splay_tree_accessors<def_node *>;
867 : :
868 : : public:
869 : : // Return the first definition that the node represents.
870 : : def_info *first_def () const;
871 : :
872 : : // Return which type of access first_def () is.
873 : 9556136 : bool contains_clobber () const { return m_clobber_or_set.is_first (); }
874 : 0 : bool contains_set () const { return m_clobber_or_set.is_second (); }
875 : :
876 : : protected:
877 : : // More nodes are clobbers rather than sets, so put clobbers first.
878 : : // Neither choice can be null.
879 : : using clobber_or_set = pointer_mux<clobber_info, set_info>;
880 : :
881 : : // Construct a node that represents FIRST_DEF (and possibly later
882 : : // definitions too, if called from a derived class).
883 : : def_node (clobber_or_set first_def);
884 : :
885 : : // The first definition in the node.
886 : : clobber_or_set m_clobber_or_set;
887 : :
888 : : private:
889 : : // The splay tree child nodes.
890 : : def_node *m_children[2];
891 : : };
892 : :
893 : : // One node in a splay tree of def_infos, representing a single set_info.
894 : : class set_node : public def_node
895 : : {
896 : : // Overall size: 3 LP64 words.
897 : : friend class function_info;
898 : :
899 : : public:
900 : : // Return the set that the node contains.
901 : : set_info *set () const { return m_clobber_or_set.known_second (); }
902 : :
903 : : // Print a description of the node to PP.
904 : : void print (pretty_printer *pp) const;
905 : :
906 : : private:
907 : : // Construct a node for SET.
908 : 15942854 : set_node (set_info *set) : def_node (set) {}
909 : : };
910 : :
911 : : // One node in a splay tree of def_infos. This class represents
912 : : // a list of contiguous clobber_infos, in execution order.
913 : : class clobber_group : public def_node
914 : : {
915 : : // Overall size: 5 LP64 words.
916 : : friend class function_info;
917 : :
918 : : public:
919 : : // Return the first and last clobbers in the group. The results are
920 : : // always nonnull.
921 : : clobber_info *first_clobber () const;
922 : 73770991 : clobber_info *last_clobber () const { return m_last_clobber; }
923 : :
924 : : // Return the last clobber before INSN in the group, or null if none.
925 : : clobber_info *prev_clobber (insn_info *insn) const;
926 : :
927 : : // Return the next clobber after INSN in the group, or null if none.
928 : : clobber_info *next_clobber (insn_info *insn) const;
929 : :
930 : : // Return true if this group has been replaced by new clobber_groups.
931 : 72242620 : bool has_been_superceded () const { return !m_last_clobber; }
932 : :
933 : : // Return a list of the clobbers in the group, in execution order.
934 : : iterator_range<def_iterator> clobbers () const;
935 : :
936 : : // Print a description of the group to PP.
937 : : void print (pretty_printer *pp) const;
938 : :
939 : : private:
940 : : clobber_group (clobber_info *);
941 : : clobber_group (clobber_info *, clobber_info *, clobber_info *);
942 : :
943 : : // Set the values of first_clobber () and last_clobber ().
944 : 270222 : void set_first_clobber (clobber_info *c) { m_clobber_or_set = c; }
945 : 153226 : void set_last_clobber (clobber_info *c) { m_last_clobber = c; }
946 : :
947 : : // The value returned by last_clobber ().
948 : : clobber_info *m_last_clobber;
949 : :
950 : : // A splay tree that contains all the clobbers in the group.
951 : : // The root of the splay tree always has an up-to-date group
952 : : // pointer, but the other clobbers in the tree might not.
953 : : clobber_tree m_clobber_tree;
954 : : };
955 : :
956 : : // A splay tree in which one node represents a standalone set_info or a
957 : : // range of consecutive clobber_infos. The nodes follow execution order
958 : : // and maintain the invariant that no two groups of clobber_infos appear
959 : : // next to each other (instead, the groups are merged).
960 : : using def_splay_tree = default_splay_tree<def_node *>;
961 : :
962 : : // This type represents a choice between:
963 : : //
964 : : // (1) a single definition of a resource
965 : : // (2) a node in a def_splay_tree that represents either a single
966 : : // set or a group of clobbers.
967 : : class def_mux : public pointer_mux<def_info, def_node>
968 : : {
969 : : using parent = pointer_mux<def_info, def_node>;
970 : :
971 : : // Provide the same constructors as the pointer_mux.
972 : 5733827 : using parent::parent;
973 : :
974 : : public:
975 : : // Return the first definition associated with this mux. If the mux holds
976 : : // a single definition, the result is that definition. If the mux holds
977 : : // a clobber_group, the result is the first clobber in the group.
978 : : def_info *first_def () const;
979 : :
980 : : // Return the last definition associated with this mux. If the mux holds
981 : : // a single definition, the result is that definition. If the mux holds
982 : : // a clobber_group, the result is the last clobber in the group.
983 : : def_info *last_def () const;
984 : :
985 : : // If the pointer represents a set_info, return that set_info,
986 : : // otherwise return null.
987 : : set_info *set () const;
988 : : };
989 : :
990 : : // This class represents the result of looking up the definition of a
991 : : // resource at a particular point, here referred to as point P.
992 : : // There are four states:
993 : : //
994 : : // - MUX is null if there were no definitions to search.
995 : : //
996 : : // - Otherwise, COMPARISON is 0 if we found a definition at P or a
997 : : // clobber_group that spans P. MUX then contains this definition
998 : : // or clobber_group.
999 : : //
1000 : : // - Otherwise, COMPARISON is greater than 0 if we found the definition
1001 : : // that precedes P or the group of clobbers that precedes P. MUX then
1002 : : // contains this definition or clobber_group.
1003 : : //
1004 : : // - Otherwise, COMPARISON is less than zero and we found the definition
1005 : : // that follows P, or the group of clobbers that follows P. MUX then
1006 : : // contains this definition or clobber_group.
1007 : : class def_lookup
1008 : : {
1009 : : public:
1010 : : // If we found a clobber_group that spans P, return the definition
1011 : : // that precedes the start of the group, or null if none.
1012 : : //
1013 : : // Otherwise, return the last definition that occurs before P,
1014 : : // or null if none.
1015 : : def_info *last_def_of_prev_group () const;
1016 : :
1017 : : // If we found a clobber_group that spans P, return the definition
1018 : : // that follows the end of the group, or null if none.
1019 : : //
1020 : : // Otherwise, return the first definition that occurs after P,
1021 : : // or null if none.
1022 : : def_info *first_def_of_next_group () const;
1023 : :
1024 : : // If we found a set_info at P, return that set_info, otherwise return null.
1025 : : set_info *matching_set () const;
1026 : :
1027 : : // If we found a set_info at P, return that set_info, otherwise return
1028 : : // prev_def ().
1029 : : def_info *matching_set_or_last_def_of_prev_group () const;
1030 : :
1031 : : // If we found a set_info at P, return that set_info, otherwise return
1032 : : // next_def ().
1033 : : def_info *matching_set_or_first_def_of_next_group () const;
1034 : :
1035 : : // P is the location of INSN. Return the last definition (of any kind)
1036 : : // that occurs before INSN, or null if none.
1037 : : def_info *prev_def (insn_info *insn) const;
1038 : :
1039 : : // P is the location of INSN. Return the next definition (of any kind)
1040 : : // that occurs after INSN, or null if none.
1041 : : def_info *next_def (insn_info *insn) const;
1042 : :
1043 : : def_mux mux;
1044 : : int comparison;
1045 : : };
1046 : :
1047 : : void pp_resource (pretty_printer *, resource_info);
1048 : : void pp_access (pretty_printer *, const access_info *,
1049 : : unsigned int flags = PP_ACCESS_DEFAULT);
1050 : : void pp_accesses (pretty_printer *, access_array,
1051 : : unsigned int flags = PP_ACCESS_DEFAULT);
1052 : : void pp_def_node (pretty_printer *, const def_node *);
1053 : : void pp_def_mux (pretty_printer *, def_mux);
1054 : : void pp_def_lookup (pretty_printer *, def_lookup);
1055 : : void pp_def_splay_tree (pretty_printer *, def_splay_tree);
1056 : :
1057 : : }
1058 : :
1059 : : void dump (FILE *, rtl_ssa::resource_info);
1060 : : void dump (FILE *, const rtl_ssa::access_info *,
1061 : : unsigned int flags = rtl_ssa::PP_ACCESS_DEFAULT);
1062 : : void dump (FILE *, rtl_ssa::access_array,
1063 : : unsigned int flags = rtl_ssa::PP_ACCESS_DEFAULT);
1064 : : void dump (FILE *, const rtl_ssa::def_node *);
1065 : : void dump (FILE *, rtl_ssa::def_mux);
1066 : : void dump (FILE *, rtl_ssa::def_lookup);
1067 : : void dump (FILE *, rtl_ssa::def_splay_tree);
1068 : :
1069 : : void DEBUG_FUNCTION debug (const rtl_ssa::resource_info *);
1070 : : void DEBUG_FUNCTION debug (const rtl_ssa::access_info *);
1071 : : void DEBUG_FUNCTION debug (const rtl_ssa::access_array);
1072 : : void DEBUG_FUNCTION debug (const rtl_ssa::def_node *);
1073 : : void DEBUG_FUNCTION debug (const rtl_ssa::def_mux &);
1074 : : void DEBUG_FUNCTION debug (const rtl_ssa::def_lookup &);
1075 : : void DEBUG_FUNCTION debug (const rtl_ssa::def_splay_tree &);
|
