Branch data Line data Source code
1 : : /* Data structure for the modref pass.
2 : : Copyright (C) 2020-2025 Free Software Foundation, Inc.
3 : : Contributed by David Cepelik and Jan Hubicka
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it under
8 : : the terms of the GNU General Public License as published by the Free
9 : : Software Foundation; either version 3, or (at your option) any later
10 : : version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : : for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : /* modref_tree represent a decision tree that can be used by alias analysis
22 : : oracle to determine whether given memory access can be affected by a function
23 : : call. For every function we collect two trees, one for loads and other
24 : : for stores. Tree consist of following levels:
25 : :
26 : : 1) Base: this level represent base alias set of the access and refers
27 : : to sons (ref nodes). Flag all_refs means that all possible references
28 : : are aliasing.
29 : :
30 : : Because for LTO streaming we need to stream types rather than alias sets
31 : : modref_base_node is implemented as a template.
32 : : 2) Ref: this level represent ref alias set and links to accesses unless
33 : : all_refs flag is set.
34 : : Again ref is an template to allow LTO streaming.
35 : : 3) Access: this level represent info about individual accesses. Presently
36 : : we record whether access is through a dereference of a function parameter
37 : : and if so we record the access range.
38 : : */
39 : :
40 : : #ifndef GCC_MODREF_TREE_H
41 : : #define GCC_MODREF_TREE_H
42 : :
43 : : struct ipa_modref_summary;
44 : :
45 : : /* parm indexes greater than 0 are normal parms.
46 : : Some negative values have special meaning. */
47 : : enum modref_special_parms {
48 : : MODREF_UNKNOWN_PARM = -1,
49 : : MODREF_STATIC_CHAIN_PARM = -2,
50 : : MODREF_RETSLOT_PARM = -3,
51 : : /* Used for bases that points to memory that escapes from function. */
52 : : MODREF_GLOBAL_MEMORY_PARM = -4,
53 : : /* Used in modref_parm_map to take references which can be removed
54 : : from the summary during summary update since they now points to local
55 : : memory. */
56 : : MODREF_LOCAL_MEMORY_PARM = -5
57 : : };
58 : :
59 : : /* Modref record accesses relative to function parameters.
60 : : This is entry for single access specifying its base and access range.
61 : :
62 : : Accesses can be collected to boundedly sized arrays using
63 : : modref_access_node::insert. */
64 : : struct GTY(()) modref_access_node
65 : : {
66 : : /* Access range information (in bits). */
67 : : poly_int64 offset;
68 : : poly_int64 size;
69 : : poly_int64 max_size;
70 : :
71 : : /* Offset from parameter pointer to the base of the access (in bytes). */
72 : : poly_int64 parm_offset;
73 : :
74 : : /* Index of parameter which specifies the base of access. -1 if base is not
75 : : a function parameter. */
76 : : int parm_index;
77 : : bool parm_offset_known;
78 : : /* Number of times interval was extended during dataflow.
79 : : This has to be limited in order to keep dataflow finite. */
80 : : unsigned char adjustments;
81 : :
82 : : /* Return true if access node holds some useful info. */
83 : 9536968 : bool useful_p () const
84 : : {
85 : 9536968 : return parm_index != MODREF_UNKNOWN_PARM;
86 : : }
87 : : /* Return true if access can be used to determine a kill. */
88 : 4731235 : bool useful_for_kill_p () const
89 : : {
90 : 4167193 : return parm_offset_known && parm_index != MODREF_UNKNOWN_PARM
91 : 4167193 : && parm_index != MODREF_GLOBAL_MEMORY_PARM
92 : 4167193 : && parm_index != MODREF_RETSLOT_PARM && known_size_p (size)
93 : 4167191 : && known_eq (max_size, size)
94 : 8896624 : && known_gt (size, 0);
95 : : }
96 : : /* Dump range to debug OUT. */
97 : : void dump (FILE *out);
98 : : /* Return true if both accesses are the same. */
99 : : bool operator == (modref_access_node &a) const;
100 : : /* Return true if range info is useful. */
101 : : bool range_info_useful_p () const;
102 : : /* Return tree corresponding to parameter of the range in STMT. */
103 : : tree get_call_arg (const gcall *stmt) const;
104 : : /* Build ao_ref corresponding to the access and return true if successful. */
105 : : bool get_ao_ref (const gcall *stmt, class ao_ref *ref) const;
106 : : /* Stream access to OB. */
107 : : void stream_out (struct output_block *ob) const;
108 : : /* Stream access in from IB. */
109 : : static modref_access_node stream_in (struct lto_input_block *ib);
110 : : /* Insert A into vector ACCESSES. Limit size of vector to MAX_ACCESSES and
111 : : if RECORD_ADJUSTMENT is true keep track of adjustment counts.
112 : : Return 0 if nothing changed, 1 is insertion succeeded and -1 if failed. */
113 : : static int insert (vec <modref_access_node, va_gc> *&accesses,
114 : : modref_access_node a, size_t max_accesses,
115 : : bool record_adjustments);
116 : : /* Same as insert but for kills where we are conservative the other way
117 : : around: if information is lost, the kill is lost. */
118 : : static bool insert_kill (vec<modref_access_node> &kills,
119 : : modref_access_node &a, bool record_adjustments);
120 : : private:
121 : : bool contains (const modref_access_node &) const;
122 : : bool contains_for_kills (const modref_access_node &) const;
123 : : void update (poly_int64, poly_int64, poly_int64, poly_int64, bool);
124 : : bool update_for_kills (poly_int64, poly_int64, poly_int64,
125 : : poly_int64, poly_int64, bool);
126 : : bool merge (const modref_access_node &, bool);
127 : : bool merge_for_kills (const modref_access_node &, bool);
128 : : static bool closer_pair_p (const modref_access_node &,
129 : : const modref_access_node &,
130 : : const modref_access_node &,
131 : : const modref_access_node &);
132 : : void forced_merge (const modref_access_node &, bool);
133 : : void update2 (poly_int64, poly_int64, poly_int64, poly_int64,
134 : : poly_int64, poly_int64, poly_int64, bool);
135 : : bool combined_offsets (const modref_access_node &,
136 : : poly_int64 *, poly_int64 *, poly_int64 *) const;
137 : : static void try_merge_with (vec <modref_access_node, va_gc> *&, size_t);
138 : : };
139 : :
140 : : /* Access node specifying no useful info. */
141 : : const modref_access_node unspecified_modref_access_node
142 : : = {0, -1, -1, 0, MODREF_UNKNOWN_PARM, false, 0};
143 : :
144 : : template <typename T>
145 : : struct GTY((user)) modref_ref_node
146 : : {
147 : : T ref;
148 : : bool every_access;
149 : : vec <modref_access_node, va_gc> *accesses;
150 : :
151 : 7674090 : modref_ref_node (T ref):
152 : 7674090 : ref (ref),
153 : 7674090 : every_access (false),
154 : 7674090 : accesses (NULL)
155 : : {}
156 : :
157 : : /* Collapse the tree. */
158 : 10131470 : void collapse ()
159 : : {
160 : 10131470 : vec_free (accesses);
161 : 10131470 : accesses = NULL;
162 : 10131470 : every_access = true;
163 : 10131470 : }
164 : :
165 : : /* Insert access with OFFSET and SIZE.
166 : : Collapse tree if it has more than MAX_ACCESSES entries.
167 : : If RECORD_ADJUSTMENTs is true avoid too many interval extensions.
168 : : Return true if record was changed. */
169 : 11108129 : bool insert_access (modref_access_node a, size_t max_accesses,
170 : : bool record_adjustments)
171 : : {
172 : : /* If this base->ref pair has no access information, bail out. */
173 : 11108129 : if (every_access)
174 : : return false;
175 : :
176 : : /* Only the following kind of parameters needs to be tracked.
177 : : We do not track return slots because they are seen as a direct store
178 : : in the caller. */
179 : 11108118 : gcc_checking_assert (a.parm_index >= 0
180 : : || a.parm_index == MODREF_STATIC_CHAIN_PARM
181 : : || a.parm_index == MODREF_GLOBAL_MEMORY_PARM
182 : : || a.parm_index == MODREF_UNKNOWN_PARM);
183 : :
184 : 11108118 : if (!a.useful_p ())
185 : : {
186 : : if (!every_access)
187 : : {
188 : 2408169 : collapse ();
189 : 2408169 : return true;
190 : : }
191 : : return false;
192 : : }
193 : :
194 : 8699949 : int ret = modref_access_node::insert (accesses, a, max_accesses,
195 : : record_adjustments);
196 : 8699949 : if (ret == -1)
197 : : {
198 : 3 : if (dump_file)
199 : 0 : fprintf (dump_file,
200 : : "--param modref-max-accesses limit reached; collapsing\n");
201 : 3 : collapse ();
202 : : }
203 : 8699949 : return ret != 0;
204 : : }
205 : : };
206 : :
207 : : /* Base of an access. */
208 : : template <typename T>
209 : : struct GTY((user)) modref_base_node
210 : : {
211 : : T base;
212 : : vec <modref_ref_node <T> *, va_gc> *refs;
213 : : bool every_ref;
214 : :
215 : 6364401 : modref_base_node (T base):
216 : 6364401 : base (base),
217 : 6364401 : refs (NULL),
218 : 6364401 : every_ref (false) {}
219 : :
220 : : /* Search REF; return NULL if failed. */
221 : 13981422 : modref_ref_node <T> *search (T ref)
222 : : {
223 : : size_t i;
224 : : modref_ref_node <T> *n;
225 : 16967014 : FOR_EACH_VEC_SAFE_ELT (refs, i, n)
226 : 9292806 : if (n->ref == ref)
227 : : return n;
228 : : return NULL;
229 : : }
230 : :
231 : : /* Insert REF; collapse tree if there are more than MAX_REFS.
232 : : Return inserted ref and if CHANGED is non-null set it to true if
233 : : something changed. */
234 : 13981288 : modref_ref_node <T> *insert_ref (T ref, size_t max_refs,
235 : : bool *changed = NULL)
236 : : {
237 : : modref_ref_node <T> *ref_node;
238 : :
239 : : /* If the node is collapsed, don't do anything. */
240 : 13981288 : if (every_ref)
241 : : return NULL;
242 : :
243 : : /* Otherwise, insert a node for the ref of the access under the base. */
244 : 13981288 : ref_node = search (ref);
245 : 13981288 : if (ref_node)
246 : : return ref_node;
247 : :
248 : : /* We always allow inserting ref 0. For non-0 refs there is upper
249 : : limit on number of entries and if exceeded,
250 : : drop ref conservatively to 0. */
251 : 7674150 : if (ref && refs && refs->length () >= max_refs)
252 : : {
253 : 98 : if (dump_file)
254 : 0 : fprintf (dump_file, "--param modref-max-refs limit reached;"
255 : : " using 0\n");
256 : 98 : ref = 0;
257 : 98 : ref_node = search (ref);
258 : 98 : if (ref_node)
259 : : return ref_node;
260 : : }
261 : :
262 : 7674090 : if (changed)
263 : 7609829 : *changed = true;
264 : :
265 : 7674090 : ref_node = new (ggc_alloc <modref_ref_node <T> > ())modref_ref_node <T>
266 : : (ref);
267 : 7674090 : vec_safe_push (refs, ref_node);
268 : 7674090 : return ref_node;
269 : : }
270 : :
271 : 6379618 : void collapse ()
272 : : {
273 : : size_t i;
274 : : modref_ref_node <T> *r;
275 : :
276 : 6379618 : if (refs)
277 : : {
278 : 14025279 : FOR_EACH_VEC_SAFE_ELT (refs, i, r)
279 : : {
280 : 7673454 : r->collapse ();
281 : 7673454 : ggc_free (r);
282 : : }
283 : 12703650 : vec_free (refs);
284 : : }
285 : 6379618 : refs = NULL;
286 : 6379618 : every_ref = true;
287 : 6379618 : }
288 : : };
289 : :
290 : : /* Map translating parameters across function call. */
291 : :
292 : : struct modref_parm_map
293 : : {
294 : : /* Default constructor. */
295 : 25413706 : modref_parm_map ()
296 : 25413706 : : parm_index (MODREF_UNKNOWN_PARM), parm_offset_known (false), parm_offset ()
297 : : {}
298 : :
299 : : /* Index of parameter we translate to.
300 : : Values from special_params enum are permitted too. */
301 : : int parm_index;
302 : : bool parm_offset_known;
303 : : poly_int64 parm_offset;
304 : : };
305 : :
306 : : /* Access tree for a single function. */
307 : : template <typename T>
308 : : struct GTY((user)) modref_tree
309 : : {
310 : : vec <modref_base_node <T> *, va_gc> *bases;
311 : : bool every_base;
312 : :
313 : 10537026 : modref_tree ():
314 : 10537026 : bases (NULL),
315 : 10537026 : every_base (false) {}
316 : :
317 : : /* Insert BASE; collapse tree if there are more than MAX_REFS.
318 : : Return inserted base and if CHANGED is non-null set it to true if
319 : : something changed.
320 : : If table gets full, try to insert REF instead. */
321 : :
322 : 14014959 : modref_base_node <T> *insert_base (T base, T ref,
323 : : unsigned int max_bases,
324 : : bool *changed = NULL)
325 : : {
326 : : modref_base_node <T> *base_node;
327 : :
328 : : /* If the node is collapsed, don't do anything. */
329 : 14014959 : if (every_base)
330 : : return NULL;
331 : :
332 : : /* Otherwise, insert a node for the base of the access into the tree. */
333 : 14014941 : base_node = search (base);
334 : 14014941 : if (base_node)
335 : : return base_node;
336 : :
337 : : /* We always allow inserting base 0. For non-0 base there is upper
338 : : limit on number of entries and if exceeded,
339 : : drop base conservatively to ref and if it still does not fit to 0. */
340 : 6441099 : if (base && bases && bases->length () >= max_bases)
341 : : {
342 : 77503 : base_node = search (ref);
343 : 77503 : if (base_node)
344 : : {
345 : 2499 : if (dump_file)
346 : 0 : fprintf (dump_file, "--param modref-max-bases"
347 : : " limit reached; using ref\n");
348 : 2499 : return base_node;
349 : : }
350 : 75004 : if (dump_file)
351 : 0 : fprintf (dump_file, "--param modref-max-bases"
352 : : " limit reached; using 0\n");
353 : 75004 : base = 0;
354 : 75004 : base_node = search (base);
355 : 75004 : if (base_node)
356 : : return base_node;
357 : : }
358 : :
359 : 6364401 : if (changed)
360 : 6302051 : *changed = true;
361 : :
362 : 6364401 : base_node = new (ggc_alloc <modref_base_node <T> > ())
363 : : modref_base_node <T> (base);
364 : 6364401 : vec_safe_push (bases, base_node);
365 : 6364401 : return base_node;
366 : : }
367 : :
368 : : /* Insert memory access to the tree.
369 : : Return true if something changed. */
370 : 18905503 : bool insert (unsigned int max_bases,
371 : : unsigned int max_refs,
372 : : unsigned int max_accesses,
373 : : T base, T ref, modref_access_node a,
374 : : bool record_adjustments)
375 : : {
376 : 18905503 : if (every_base)
377 : : return false;
378 : :
379 : 14477045 : bool changed = false;
380 : :
381 : : /* We may end up with max_size being less than size for accesses past the
382 : : end of array. Those are undefined and safe to ignore. */
383 : 14477045 : if (a.range_info_useful_p ()
384 : 6637158 : && known_size_p (a.size) && known_size_p (a.max_size)
385 : 20830127 : && known_lt (a.max_size, a.size))
386 : : {
387 : 14 : if (dump_file)
388 : 0 : fprintf (dump_file,
389 : : " - Paradoxical range. Ignoring\n");
390 : 14 : return false;
391 : : }
392 : 14477031 : if (known_size_p (a.size)
393 : 14477031 : && known_eq (a.size, 0))
394 : : {
395 : 125 : if (dump_file)
396 : 0 : fprintf (dump_file,
397 : : " - Zero size. Ignoring\n");
398 : 125 : return false;
399 : : }
400 : 14476906 : if (known_size_p (a.max_size)
401 : 14476906 : && known_eq (a.max_size, 0))
402 : : {
403 : 669 : if (dump_file)
404 : 0 : fprintf (dump_file,
405 : : " - Zero max_size. Ignoring\n");
406 : 669 : return false;
407 : : }
408 : 14476237 : gcc_checking_assert (!known_size_p (a.max_size)
409 : : || !known_le (a.max_size, 0));
410 : :
411 : : /* No useful information tracked; collapse everything. */
412 : 14476237 : if (!base && !ref && !a.useful_p ())
413 : : {
414 : 532325 : collapse ();
415 : 532325 : return true;
416 : : }
417 : :
418 : : modref_base_node <T> *base_node
419 : 13943912 : = insert_base (base, ref, max_bases, &changed);
420 : 13943912 : base = base_node->base;
421 : : /* If table got full we may end up with useless base. */
422 : 13943912 : if (!base && !ref && !a.useful_p ())
423 : : {
424 : 4 : collapse ();
425 : 4 : return true;
426 : : }
427 : 13943908 : if (base_node->every_ref)
428 : 18622 : return changed;
429 : 13925286 : gcc_checking_assert (search (base) != NULL);
430 : :
431 : : /* No useful ref info tracked; collapse base. */
432 : 13925286 : if (!ref && !a.useful_p ())
433 : : {
434 : 9530 : base_node->collapse ();
435 : 9530 : return true;
436 : : }
437 : :
438 : : modref_ref_node <T> *ref_node
439 : 13915756 : = base_node->insert_ref (ref, max_refs, &changed);
440 : 13915756 : ref = ref_node->ref;
441 : :
442 : 13915756 : if (ref_node->every_access)
443 : 2824127 : return changed;
444 : 11091629 : changed |= ref_node->insert_access (a, max_accesses,
445 : : record_adjustments);
446 : : /* See if we failed to add useful access. */
447 : 11091629 : if (ref_node->every_access)
448 : : {
449 : : /* Collapse everything if there is no useful base and ref. */
450 : 2408059 : if (!base && !ref)
451 : : {
452 : 0 : collapse ();
453 : 0 : gcc_checking_assert (changed);
454 : : }
455 : : /* Collapse base if there is no useful ref. */
456 : 2408059 : else if (!ref)
457 : : {
458 : 8 : base_node->collapse ();
459 : 8 : gcc_checking_assert (changed);
460 : : }
461 : : }
462 : : return changed;
463 : : }
464 : :
465 : : /* Insert memory access to the tree.
466 : : Return true if something changed. */
467 : 14427066 : bool insert (tree fndecl,
468 : : T base, T ref, const modref_access_node &a,
469 : : bool record_adjustments)
470 : : {
471 : 28854132 : return insert (opt_for_fn (fndecl, param_modref_max_bases),
472 : 14427066 : opt_for_fn (fndecl, param_modref_max_refs),
473 : 14427066 : opt_for_fn (fndecl, param_modref_max_accesses),
474 : 14427066 : base, ref, a, record_adjustments);
475 : : }
476 : :
477 : : /* Remove tree branches that are not useful (i.e. they will always pass). */
478 : :
479 : 170551 : void cleanup ()
480 : : {
481 : : size_t i, j;
482 : : modref_base_node <T> *base_node;
483 : : modref_ref_node <T> *ref_node;
484 : :
485 : 170551 : if (!bases)
486 : 170551 : return;
487 : :
488 : 132004 : for (i = 0; vec_safe_iterate (bases, i, &base_node);)
489 : : {
490 : 74531 : if (base_node->refs)
491 : 141806 : for (j = 0; vec_safe_iterate (base_node->refs, j, &ref_node);)
492 : : {
493 : 73727 : if (!ref_node->every_access
494 : 73727 : && (!ref_node->accesses
495 : 22632 : || !ref_node->accesses->length ()))
496 : : {
497 : 0 : base_node->refs->unordered_remove (j);
498 : 0 : vec_free (ref_node->accesses);
499 : 0 : ggc_delete (ref_node);
500 : : }
501 : : else
502 : 73727 : j++;
503 : : }
504 : 74531 : if (!base_node->every_ref
505 : 74531 : && (!base_node->refs || !base_node->refs->length ()))
506 : : {
507 : 0 : bases->unordered_remove (i);
508 : 0 : vec_free (base_node->refs);
509 : 0 : ggc_delete (base_node);
510 : : }
511 : : else
512 : 74531 : i++;
513 : : }
514 : 57473 : if (bases && !bases->length ())
515 : : {
516 : 0 : vec_free (bases);
517 : 0 : bases = NULL;
518 : : }
519 : : }
520 : :
521 : : /* Merge OTHER into the tree.
522 : : PARM_MAP, if non-NULL, maps parm indexes of callee to caller.
523 : : Similar CHAIN_MAP, if non-NULL, maps static chain of callee to caller.
524 : : Return true if something has changed. */
525 : 6804204 : bool merge (unsigned int max_bases,
526 : : unsigned int max_refs,
527 : : unsigned int max_accesses,
528 : : modref_tree <T> *other, vec <modref_parm_map> *parm_map,
529 : : modref_parm_map *static_chain_map,
530 : : bool record_accesses,
531 : : bool promote_unknown_to_global = false)
532 : : {
533 : 6804204 : if (!other || every_base)
534 : : return false;
535 : 4778580 : if (other->every_base)
536 : : {
537 : 828945 : collapse ();
538 : 828945 : return true;
539 : : }
540 : :
541 : 3949635 : bool changed = false;
542 : : size_t i, j, k;
543 : : modref_base_node <T> *base_node, *my_base_node;
544 : : modref_ref_node <T> *ref_node;
545 : : modref_access_node *access_node;
546 : 3949635 : bool release = false;
547 : :
548 : : /* For self-recursive functions we may end up merging summary into itself;
549 : : produce copy first so we do not modify summary under our own hands. */
550 : 3949635 : if (other == this)
551 : : {
552 : 15166 : release = true;
553 : 15166 : other = modref_tree<T>::create_ggc ();
554 : 15166 : other->copy_from (this);
555 : : }
556 : :
557 : 7981192 : FOR_EACH_VEC_SAFE_ELT (other->bases, i, base_node)
558 : : {
559 : 4031557 : if (base_node->every_ref)
560 : : {
561 : 7598 : my_base_node = insert_base (base_node->base, 0,
562 : : max_bases, &changed);
563 : 7598 : if (my_base_node && !my_base_node->every_ref)
564 : : {
565 : 6215 : my_base_node->collapse ();
566 : 6215 : cleanup ();
567 : 6215 : changed = true;
568 : : }
569 : : }
570 : : else
571 : 12933451 : FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
572 : : {
573 : 4877935 : if (ref_node->every_access)
574 : : {
575 : 1704463 : changed |= insert (max_bases, max_refs, max_accesses,
576 : : base_node->base,
577 : : ref_node->ref,
578 : : unspecified_modref_access_node,
579 : : record_accesses);
580 : : }
581 : : else
582 : 11617651 : FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
583 : : {
584 : 3566244 : modref_access_node a = *access_node;
585 : :
586 : 3566244 : if (a.parm_index != MODREF_UNKNOWN_PARM
587 : 3566244 : && a.parm_index != MODREF_GLOBAL_MEMORY_PARM
588 : 3383274 : && parm_map)
589 : : {
590 : 4479956 : if (a.parm_index >= (int)parm_map->length ())
591 : : a.parm_index = MODREF_UNKNOWN_PARM;
592 : : else
593 : : {
594 : 2239932 : modref_parm_map &m
595 : : = a.parm_index == MODREF_STATIC_CHAIN_PARM
596 : 2239932 : ? *static_chain_map
597 : : : (*parm_map) [a.parm_index];
598 : 2239932 : if (m.parm_index == MODREF_LOCAL_MEMORY_PARM)
599 : 792350 : continue;
600 : 1447582 : a.parm_offset += m.parm_offset;
601 : 1447582 : a.parm_offset_known &= m.parm_offset_known;
602 : 1447582 : a.parm_index = m.parm_index;
603 : : }
604 : : }
605 : 2773894 : if (a.parm_index == MODREF_UNKNOWN_PARM
606 : 662907 : && promote_unknown_to_global)
607 : 248 : a.parm_index = MODREF_GLOBAL_MEMORY_PARM;
608 : 2773894 : changed |= insert (max_bases, max_refs, max_accesses,
609 : : base_node->base, ref_node->ref,
610 : : a, record_accesses);
611 : : }
612 : : }
613 : : }
614 : 3949635 : if (release)
615 : 15166 : ggc_delete (other);
616 : 3949635 : return changed;
617 : : }
618 : :
619 : : /* Merge OTHER into the tree.
620 : : PARM_MAP, if non-NULL, maps parm indexes of callee to caller.
621 : : Similar CHAIN_MAP, if non-NULL, maps static chain of callee to caller.
622 : : Return true if something has changed. */
623 : 5509462 : bool merge (tree fndecl,
624 : : modref_tree <T> *other, vec <modref_parm_map> *parm_map,
625 : : modref_parm_map *static_chain_map,
626 : : bool record_accesses,
627 : : bool promote_unknown_to_global = false)
628 : : {
629 : 11018924 : return merge (opt_for_fn (fndecl, param_modref_max_bases),
630 : 5509462 : opt_for_fn (fndecl, param_modref_max_refs),
631 : 5509462 : opt_for_fn (fndecl, param_modref_max_accesses),
632 : : other, parm_map, static_chain_map, record_accesses,
633 : 5509462 : promote_unknown_to_global);
634 : : }
635 : :
636 : : /* Copy OTHER to THIS. */
637 : 1294738 : void copy_from (modref_tree <T> *other)
638 : : {
639 : 1294738 : merge (INT_MAX, INT_MAX, INT_MAX, other, NULL, NULL, false);
640 : 1294738 : }
641 : :
642 : : /* Search BASE in tree; return NULL if failed. */
643 : 28092786 : modref_base_node <T> *search (T base)
644 : : {
645 : : size_t i;
646 : : modref_base_node <T> *n;
647 : 55870483 : FOR_EACH_VEC_SAFE_ELT (bases, i, n)
648 : 49353559 : if (n->base == base)
649 : : return n;
650 : : return NULL;
651 : : }
652 : :
653 : : /* Return true if tree contains access to global memory. */
654 : 8160900 : bool global_access_p ()
655 : : {
656 : : size_t i, j, k;
657 : : modref_base_node <T> *base_node;
658 : : modref_ref_node <T> *ref_node;
659 : : modref_access_node *access_node;
660 : 8160900 : if (every_base)
661 : : return true;
662 : 7729584 : FOR_EACH_VEC_SAFE_ELT (bases, i, base_node)
663 : : {
664 : 3312916 : if (base_node->every_ref)
665 : : return true;
666 : 7512038 : FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
667 : : {
668 : 3862766 : if (ref_node->every_access)
669 : : return true;
670 : 8012720 : FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
671 : 3254690 : if (access_node->parm_index == MODREF_UNKNOWN_PARM
672 : 3254690 : || access_node->parm_index == MODREF_GLOBAL_MEMORY_PARM)
673 : : return true;
674 : : }
675 : : }
676 : : return false;
677 : : }
678 : :
679 : : /* Return ggc allocated instance. We explicitly call destructors via
680 : : ggc_delete and do not want finalizers to be registered and
681 : : called at the garbage collection time. */
682 : 10537014 : static modref_tree<T> *create_ggc ()
683 : : {
684 : 5358258 : return new (ggc_alloc_no_dtor<modref_tree<T>> ())
685 : : modref_tree<T> ();
686 : : }
687 : :
688 : : /* Remove all records and mark tree to alias with everything. */
689 : 14674325 : void collapse ()
690 : : {
691 : : size_t i;
692 : : modref_base_node <T> *n;
693 : :
694 : 14674325 : if (bases)
695 : : {
696 : 10849923 : FOR_EACH_VEC_SAFE_ELT (bases, i, n)
697 : : {
698 : 6363765 : n->collapse ();
699 : 6363765 : ggc_free (n);
700 : : }
701 : 8972316 : vec_free (bases);
702 : : }
703 : 14674325 : bases = NULL;
704 : 14674325 : every_base = true;
705 : 14674325 : }
706 : :
707 : : /* Release memory. */
708 : 10535690 : ~modref_tree ()
709 : : {
710 : 10535690 : collapse ();
711 : 10535690 : }
712 : :
713 : : /* Update parameter indexes in TT according to MAP. */
714 : : void
715 : 38550 : remap_params (vec <int> *map)
716 : : {
717 : : size_t i;
718 : : modref_base_node <T> *base_node;
719 : 71812 : FOR_EACH_VEC_SAFE_ELT (bases, i, base_node)
720 : : {
721 : : size_t j;
722 : : modref_ref_node <T> *ref_node;
723 : 70393 : FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
724 : : {
725 : : size_t k;
726 : : modref_access_node *access_node;
727 : 43435 : FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
728 : 13442 : if (access_node->parm_index >= 0)
729 : : {
730 : 26632 : if (access_node->parm_index < (int)map->length ())
731 : 12211 : access_node->parm_index = (*map)[access_node->parm_index];
732 : : else
733 : 1105 : access_node->parm_index = MODREF_UNKNOWN_PARM;
734 : : }
735 : : }
736 : : }
737 : 38550 : }
738 : : };
739 : :
740 : : void gt_ggc_mx (modref_tree <int>* const&);
741 : : void gt_ggc_mx (modref_tree <tree_node*>* const&);
742 : : void gt_pch_nx (modref_tree <int>* const&);
743 : : void gt_pch_nx (modref_tree <tree_node*>* const&);
744 : : void gt_pch_nx (modref_tree <int>* const&, gt_pointer_operator op, void *cookie);
745 : : void gt_pch_nx (modref_tree <tree_node*>* const&, gt_pointer_operator op,
746 : : void *cookie);
747 : :
748 : : void gt_ggc_mx (modref_base_node <int>*);
749 : : void gt_ggc_mx (modref_base_node <tree_node*>* &);
750 : : void gt_pch_nx (modref_base_node <int>* const&);
751 : : void gt_pch_nx (modref_base_node <tree_node*>* const&);
752 : : void gt_pch_nx (modref_base_node <int>* const&, gt_pointer_operator op,
753 : : void *cookie);
754 : : void gt_pch_nx (modref_base_node <tree_node*>* const&, gt_pointer_operator op,
755 : : void *cookie);
756 : :
757 : : void gt_ggc_mx (modref_ref_node <int>*);
758 : : void gt_ggc_mx (modref_ref_node <tree_node*>* &);
759 : : void gt_pch_nx (modref_ref_node <int>* const&);
760 : : void gt_pch_nx (modref_ref_node <tree_node*>* const&);
761 : : void gt_pch_nx (modref_ref_node <int>* const&, gt_pointer_operator op,
762 : : void *cookie);
763 : : void gt_pch_nx (modref_ref_node <tree_node*>* const&, gt_pointer_operator op,
764 : : void *cookie);
765 : :
766 : : #endif
|
