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