]>
Commit | Line | Data |
---|---|---|
73b75827 | 1 | // Access-related classes for RTL SSA -*- C++ -*- |
83ffe9cd | 2 | // Copyright (C) 2020-2023 Free Software Foundation, Inc. |
73b75827 RS |
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 | 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 | resource_info resource () const { return { m_mode, m_regno }; } | |
123 | ||
124 | // Return true if the access is to memory. | |
125 | bool is_mem () const { return m_regno == MEM_REGNO; } | |
126 | ||
127 | // Return true if the access is to a register. | |
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. | |
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). | |
142 | machine_mode mode () const { return m_mode; } | |
143 | ||
144 | // Return the kind of access that this is. | |
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. | |
149 | 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 | 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 | 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 | 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 | 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 | 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 | 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 | 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: | |
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. | |
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. | |
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. | |
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. | |
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 (). | |
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 (). | |
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. | |
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 *); | |
429 | void set_def (set_info *set) { m_def = set; } | |
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. | |
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 | ||
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. | |
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 | ||
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. | |
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. | |
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 | ||
b61461ac IL |
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 | ||
73b75827 RS |
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. | |
791 | phi_info *prev_phi () const { return m_prev_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. | |
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. | |
800 | bool is_degenerate () const { return m_num_inputs == 1; } | |
801 | ||
802 | // Return the phi node's unique identifier. | |
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); | |
827 | void set_prev_phi (phi_info *prev_phi) { m_prev_phi = prev_phi; } | |
828 | void set_next_phi (phi_info *next_phi) { m_next_phi = next_phi; } | |
829 | void clear_phi_links () { m_prev_phi = m_next_phi = nullptr; } | |
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. | |
861 | bool contains_clobber () const { return m_clobber_or_set.is_first (); } | |
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. | |
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. | |
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; | |
910 | clobber_info *last_clobber () const { return m_last_clobber; } | |
911 | ||
4a3073f0 RS |
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 | ||
73b75827 RS |
918 | // Return true if this group has been replaced by new clobber_groups. |
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 (). | |
931 | void set_first_clobber (clobber_info *c) { m_clobber_or_set = 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 | // | |
6d751681 | 987 | // - Otherwise, COMPARISON is greater than 0 if we found the definition |
73b75827 RS |
988 | // that precedes P or the group of clobbers that precedes P. MUX then |
989 | // contains this definition or clobber_group. | |
990 | // | |
6d751681 RS |
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. | |
73b75827 RS |
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. | |
4a3073f0 | 1002 | def_info *last_def_of_prev_group () const; |
73b75827 RS |
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. | |
4a3073f0 | 1009 | def_info *first_def_of_next_group () const; |
73b75827 RS |
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 (). | |
4a3073f0 | 1016 | def_info *matching_set_or_last_def_of_prev_group () const; |
73b75827 RS |
1017 | |
1018 | // If we found a set_info at P, return that set_info, otherwise return | |
1019 | // next_def (). | |
4a3073f0 RS |
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; | |
73b75827 RS |
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 &); |