Line data Source code
1 : /* Data structure for the modref pass.
2 : Copyright (C) 2020-2026 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 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "backend.h"
25 : #include "tree.h"
26 : #include "ipa-modref-tree.h"
27 : #include "selftest.h"
28 : #include "tree-ssa-alias.h"
29 : #include "gimple.h"
30 : #include "cgraph.h"
31 : #include "tree-streamer.h"
32 :
33 : /* Return true if both accesses are the same. */
34 : bool
35 2195422 : modref_access_node::operator == (const modref_access_node &a) const
36 : {
37 2195422 : if (parm_index != a.parm_index)
38 : return false;
39 1043696 : if (parm_index != MODREF_UNKNOWN_PARM
40 1043696 : && parm_index != MODREF_GLOBAL_MEMORY_PARM)
41 : {
42 1043696 : if (parm_offset_known != a.parm_offset_known)
43 : return false;
44 1043696 : if (parm_offset_known
45 1043696 : && !known_eq (parm_offset, a.parm_offset))
46 : return false;
47 : }
48 731908 : if (range_info_useful_p () != a.range_info_useful_p ())
49 : return false;
50 731908 : if (range_info_useful_p ()
51 731908 : && (!known_eq (a.offset, offset)
52 22826 : || !known_eq (a.size, size)
53 0 : || !known_eq (a.max_size, max_size)))
54 : return false;
55 : return true;
56 : }
57 :
58 : /* Return true A is a subaccess. */
59 : bool
60 25565086 : modref_access_node::contains (const modref_access_node &a) const
61 : {
62 25565086 : poly_offset_int aoffset_adj = 0;
63 25565086 : if (parm_index != MODREF_UNKNOWN_PARM)
64 : {
65 25565083 : if (parm_index != a.parm_index)
66 : return false;
67 15727545 : if (parm_offset_known)
68 : {
69 14625836 : if (!a.parm_offset_known)
70 : return false;
71 : /* Accesses are never below parm_offset, so look
72 : for smaller offset.
73 : If access ranges are known still allow merging
74 : when bit offsets comparison passes. */
75 14612962 : if (!known_le (parm_offset, a.parm_offset)
76 14612962 : && !range_info_useful_p ())
77 : return false;
78 : /* We allow negative aoffset_adj here in case
79 : there is an useful range. This is because adding
80 : a.offset may result in non-negative offset again.
81 : Ubsan fails on val << LOG_BITS_PER_UNIT where val
82 : is negative. */
83 14612962 : aoffset_adj = (poly_offset_int::from (a.parm_offset, SIGNED)
84 14612962 : - poly_offset_int::from (parm_offset, SIGNED))
85 29225924 : * BITS_PER_UNIT;
86 : }
87 : }
88 15714674 : if (range_info_useful_p ())
89 : {
90 14612962 : if (!a.range_info_useful_p ())
91 : return false;
92 : /* Sizes of stores are used to check that object is big enough
93 : to fit the store, so smaller or unknown store is more general
94 : than large store. */
95 14612962 : if (known_size_p (size)
96 14612962 : && (!known_size_p (a.size)
97 14353989 : || !known_le (size, a.size)))
98 : return false;
99 12838895 : if (known_size_p (max_size))
100 12678222 : return known_subrange_p (poly_offset_int::from (a.offset, SIGNED)
101 25356444 : + aoffset_adj, a.max_size,
102 12678222 : poly_offset_int::from (offset, SIGNED),
103 12678222 : max_size);
104 : else
105 160673 : return known_le (poly_offset_int::from (offset, SIGNED),
106 : poly_offset_int::from (a.offset, SIGNED)
107 : + aoffset_adj);
108 : }
109 : return true;
110 : }
111 :
112 : /* Update access range to new parameters.
113 : If RECORD_ADJUSTMENTS is true, record number of changes in the access
114 : and if threshold is exceeded start dropping precision
115 : so only constantly many updates are possible. This makes dataflow
116 : to converge. */
117 : void
118 1042790 : modref_access_node::update (poly_int64 parm_offset1,
119 : poly_int64 offset1, poly_int64 size1,
120 : poly_int64 max_size1, bool record_adjustments)
121 : {
122 1042790 : if (known_eq (parm_offset, parm_offset1)
123 1018728 : && known_eq (offset, offset1)
124 785473 : && known_eq (size, size1)
125 1813256 : && known_eq (max_size, max_size1))
126 : return;
127 1037747 : if (!record_adjustments
128 1037747 : || (++adjustments) < param_modref_max_adjustments)
129 : {
130 1037689 : parm_offset = parm_offset1;
131 1037689 : offset = offset1;
132 1037689 : size = size1;
133 1037689 : max_size = max_size1;
134 : }
135 : else
136 : {
137 58 : if (dump_file)
138 1 : fprintf (dump_file, "--param modref-max-adjustments limit reached:");
139 58 : if (!known_eq (parm_offset, parm_offset1))
140 : {
141 0 : if (dump_file)
142 0 : fprintf (dump_file, " parm_offset cleared");
143 0 : parm_offset_known = false;
144 : }
145 58 : if (!known_eq (size, size1))
146 : {
147 0 : size = -1;
148 0 : if (dump_file)
149 0 : fprintf (dump_file, " size cleared");
150 : }
151 58 : if (!known_eq (max_size, max_size1))
152 : {
153 58 : max_size = -1;
154 58 : if (dump_file)
155 1 : fprintf (dump_file, " max_size cleared");
156 : }
157 58 : if (!known_eq (offset, offset1))
158 : {
159 0 : offset = 0;
160 0 : if (dump_file)
161 0 : fprintf (dump_file, " offset cleared");
162 : }
163 58 : if (dump_file)
164 1 : fprintf (dump_file, "\n");
165 : }
166 : }
167 :
168 : /* Merge in access A if it is possible to do without losing
169 : precision. Return true if successful.
170 : If RECORD_ADJUSTMENTs is true, remember how many interval
171 : was prolonged and punt when there are too many. */
172 : bool
173 4485722 : modref_access_node::merge (const modref_access_node &a,
174 : bool record_adjustments)
175 : {
176 4485722 : poly_int64 offset1 = 0;
177 4485722 : poly_int64 aoffset1 = 0;
178 4485722 : poly_int64 new_parm_offset = 0;
179 :
180 : /* We assume that containment was tested earlier. */
181 4485722 : gcc_checking_assert (!contains (a) && !a.contains (*this));
182 4485722 : if (parm_index != MODREF_UNKNOWN_PARM)
183 : {
184 4485722 : if (parm_index != a.parm_index)
185 : return false;
186 2684728 : if (parm_offset_known)
187 : {
188 2684728 : if (!a.parm_offset_known)
189 : return false;
190 2684728 : if (!combined_offsets (a, &new_parm_offset, &offset1, &aoffset1))
191 : return false;
192 : }
193 : }
194 : /* See if we can merge ranges. */
195 2684728 : if (range_info_useful_p ())
196 : {
197 : /* In this case we have containment that should be
198 : handled earlier. */
199 2684728 : gcc_checking_assert (a.range_info_useful_p ());
200 :
201 : /* If a.size is less specified than size, merge only
202 : if intervals are otherwise equivalent. */
203 2684728 : if (known_size_p (size)
204 2684728 : && (!known_size_p (a.size) || known_lt (a.size, size)))
205 : {
206 286129 : if (((known_size_p (max_size) || known_size_p (a.max_size))
207 286097 : && !known_eq (max_size, a.max_size))
208 294293 : || !known_eq (offset1, aoffset1))
209 : return false;
210 0 : update (new_parm_offset, offset1, a.size, max_size,
211 : record_adjustments);
212 0 : return true;
213 : }
214 : /* If sizes are same, we can extend the interval. */
215 2398599 : if ((known_size_p (size) || known_size_p (a.size))
216 2411503 : && !known_eq (size, a.size))
217 : return false;
218 2108456 : if (known_le (offset1, aoffset1))
219 : {
220 1408747 : if (!known_size_p (max_size)
221 1408747 : || known_ge (offset1 + max_size, aoffset1))
222 : {
223 759178 : update2 (new_parm_offset, offset1, size, max_size,
224 : aoffset1, a.size, a.max_size,
225 : record_adjustments);
226 759178 : return true;
227 : }
228 : }
229 699709 : else if (known_le (aoffset1, offset1))
230 : {
231 699709 : if (!known_size_p (a.max_size)
232 699709 : || known_ge (aoffset1 + a.max_size, offset1))
233 : {
234 229966 : update2 (new_parm_offset, offset1, size, max_size,
235 : aoffset1, a.size, a.max_size,
236 : record_adjustments);
237 229966 : return true;
238 : }
239 : }
240 : return false;
241 : }
242 0 : update (new_parm_offset, offset1,
243 : size, max_size, record_adjustments);
244 0 : return true;
245 : }
246 :
247 : /* Return true if A1 and B1 can be merged with lower information
248 : less than A2 and B2.
249 : Assume that no containment or lossless merging is possible. */
250 : bool
251 173487 : modref_access_node::closer_pair_p (const modref_access_node &a1,
252 : const modref_access_node &b1,
253 : const modref_access_node &a2,
254 : const modref_access_node &b2)
255 : {
256 : /* Merging different parm indexes comes to complete loss
257 : of range info. */
258 173487 : if (a1.parm_index != b1.parm_index)
259 : return false;
260 90172 : if (a2.parm_index != b2.parm_index)
261 : return true;
262 : /* If parm is known and parm indexes are the same we should
263 : already have containment. */
264 89052 : gcc_checking_assert (a1.parm_offset_known && b1.parm_offset_known);
265 89052 : gcc_checking_assert (a2.parm_offset_known && b2.parm_offset_known);
266 :
267 : /* First normalize offsets for parm offsets. */
268 89052 : poly_int64 new_parm_offset, offseta1, offsetb1, offseta2, offsetb2;
269 89052 : if (!a1.combined_offsets (b1, &new_parm_offset, &offseta1, &offsetb1)
270 89052 : || !a2.combined_offsets (b2, &new_parm_offset, &offseta2, &offsetb2))
271 0 : gcc_unreachable ();
272 :
273 :
274 : /* Now compute distance of the intervals. */
275 89052 : poly_offset_int dist1, dist2;
276 89052 : if (known_le (offseta1, offsetb1))
277 : {
278 86153 : if (!known_size_p (a1.max_size))
279 0 : dist1 = 0;
280 : else
281 172306 : dist1 = (poly_offset_int)offsetb1
282 172306 : - (poly_offset_int)offseta1
283 172306 : - (poly_offset_int)a1.max_size;
284 : }
285 : else
286 : {
287 2899 : if (!known_size_p (b1.max_size))
288 0 : dist1 = 0;
289 : else
290 5798 : dist1 = (poly_offset_int)offseta1
291 5798 : - (poly_offset_int)offsetb1
292 5798 : - (poly_offset_int)b1.max_size;
293 : }
294 89052 : if (known_le (offseta2, offsetb2))
295 : {
296 85668 : if (!known_size_p (a2.max_size))
297 0 : dist2 = 0;
298 : else
299 171336 : dist2 = (poly_offset_int)offsetb2
300 171336 : - (poly_offset_int)offseta2
301 171336 : - (poly_offset_int)a2.max_size;
302 : }
303 : else
304 : {
305 3384 : if (!known_size_p (b2.max_size))
306 0 : dist2 = 0;
307 : else
308 3384 : dist2 = offseta2
309 6768 : - (poly_offset_int)offsetb2
310 6768 : - (poly_offset_int)b2.max_size;
311 : }
312 : /* It may happen that intervals overlap in case size
313 : is different. Prefer the overlap to non-overlap. */
314 89052 : if (known_lt (dist1, 0) && known_ge (dist2, 0))
315 64 : return true;
316 88988 : if (known_lt (dist2, 0) && known_ge (dist1, 0))
317 4650 : return false;
318 84338 : if (known_lt (dist1, 0))
319 : /* If both overlaps minimize overlap. */
320 371 : return known_le (dist2, dist1);
321 : else
322 : /* If both are disjoint look for smaller distance. */
323 83967 : return known_le (dist1, dist2);
324 : }
325 :
326 : /* Merge in access A while losing precision. */
327 : void
328 1291 : modref_access_node::forced_merge (const modref_access_node &a,
329 : bool record_adjustments)
330 : {
331 1291 : if (parm_index != a.parm_index)
332 : {
333 3 : gcc_checking_assert (parm_index != MODREF_UNKNOWN_PARM);
334 3 : parm_index = MODREF_UNKNOWN_PARM;
335 3 : return;
336 : }
337 :
338 : /* We assume that containment and lossless merging
339 : was tested earlier. */
340 1288 : gcc_checking_assert (!contains (a) && !a.contains (*this)
341 : && !merge (a, record_adjustments));
342 1288 : gcc_checking_assert (parm_offset_known && a.parm_offset_known);
343 :
344 1288 : poly_int64 new_parm_offset, offset1, aoffset1;
345 1288 : if (!combined_offsets (a, &new_parm_offset, &offset1, &aoffset1))
346 : {
347 0 : parm_offset_known = false;
348 0 : return;
349 : }
350 1288 : gcc_checking_assert (range_info_useful_p ()
351 : && a.range_info_useful_p ());
352 1288 : if (record_adjustments)
353 0 : adjustments += a.adjustments;
354 1288 : update2 (new_parm_offset,
355 : offset1, size, max_size,
356 : aoffset1, a.size, a.max_size,
357 : record_adjustments);
358 : }
359 :
360 : /* Merge two ranges both starting at parm_offset1 and update THIS
361 : with result. */
362 : void
363 990432 : modref_access_node::update2 (poly_int64 parm_offset1,
364 : poly_int64 offset1, poly_int64 size1,
365 : poly_int64 max_size1,
366 : poly_int64 offset2, poly_int64 size2,
367 : poly_int64 max_size2,
368 : bool record_adjustments)
369 : {
370 990432 : poly_int64 new_size = size1;
371 :
372 990432 : if (!known_size_p (size2)
373 990432 : || known_le (size2, size1))
374 989756 : new_size = size2;
375 : else
376 : gcc_checking_assert (known_le (size1, size2));
377 :
378 990432 : if (known_le (offset1, offset2))
379 : ;
380 229984 : else if (known_le (offset2, offset1))
381 : {
382 229984 : std::swap (offset1, offset2);
383 229984 : std::swap (max_size1, max_size2);
384 : }
385 : else
386 : gcc_unreachable ();
387 :
388 990432 : poly_int64 new_max_size;
389 :
390 990432 : if (!known_size_p (max_size1))
391 2 : new_max_size = max_size1;
392 990430 : else if (!known_size_p (max_size2))
393 1413 : new_max_size = max_size2;
394 : else
395 : {
396 2967051 : poly_offset_int s = (poly_offset_int)max_size2
397 1978034 : + (poly_offset_int)offset2
398 989017 : - (poly_offset_int)offset1;
399 989017 : if (s.to_shwi (&new_max_size))
400 : {
401 989017 : if (known_le (new_max_size, max_size1))
402 55 : new_max_size = max_size1;
403 : }
404 : else
405 0 : new_max_size = -1;
406 : }
407 :
408 990432 : update (parm_offset1, offset1,
409 : new_size, new_max_size, record_adjustments);
410 990432 : }
411 :
412 : /* Given access nodes THIS and A, return true if they
413 : can be done with common parm_offsets. In this case
414 : return parm offset in new_parm_offset, new_offset
415 : which is start of range in THIS and new_aoffset that
416 : is start of range in A. */
417 : bool
418 3772378 : modref_access_node::combined_offsets (const modref_access_node &a,
419 : poly_int64 *new_parm_offset,
420 : poly_int64 *new_offset,
421 : poly_int64 *new_aoffset) const
422 : {
423 3772378 : gcc_checking_assert (parm_offset_known && a.parm_offset_known);
424 3772378 : if (known_le (a.parm_offset, parm_offset))
425 : {
426 3008780 : *new_offset = offset
427 3008780 : + ((parm_offset - a.parm_offset)
428 3008780 : << LOG2_BITS_PER_UNIT);
429 3008780 : *new_aoffset = a.offset;
430 3008780 : *new_parm_offset = a.parm_offset;
431 3008780 : return true;
432 : }
433 763598 : else if (known_le (parm_offset, a.parm_offset))
434 : {
435 763598 : *new_aoffset = a.offset
436 763598 : + ((a.parm_offset - parm_offset)
437 763598 : << LOG2_BITS_PER_UNIT);
438 763598 : *new_offset = offset;
439 763598 : *new_parm_offset = parm_offset;
440 763598 : return true;
441 : }
442 : else
443 : return false;
444 : }
445 :
446 : /* Try to optimize the access ACCESSES list after entry INDEX was modified. */
447 : void
448 1010105 : modref_access_node::try_merge_with (vec <modref_access_node, va_gc> *&accesses,
449 : size_t index)
450 : {
451 1010105 : size_t i;
452 :
453 2740522 : for (i = 0; i < accesses->length ();)
454 1730417 : if (i != index)
455 : {
456 689936 : bool found = false, restart = false;
457 689936 : modref_access_node *a = &(*accesses)[i];
458 689936 : modref_access_node *n = &(*accesses)[index];
459 :
460 689936 : if (n->contains (*a))
461 : found = true;
462 682619 : if (!found && n->merge (*a, false))
463 : found = restart = true;
464 657251 : gcc_checking_assert (found || !a->merge (*n, false));
465 689936 : if (found)
466 : {
467 40002 : accesses->unordered_remove (i);
468 40002 : if (index == accesses->length ())
469 : {
470 2216 : index = i;
471 2216 : i++;
472 : }
473 40002 : if (restart)
474 32685 : i = 0;
475 : }
476 : else
477 649934 : i++;
478 : }
479 : else
480 1040481 : i++;
481 1010105 : }
482 :
483 : /* Stream out to OB. */
484 :
485 : void
486 28983 : modref_access_node::stream_out (struct output_block *ob) const
487 : {
488 28983 : streamer_write_hwi (ob, parm_index);
489 28983 : if (parm_index != MODREF_UNKNOWN_PARM)
490 : {
491 28697 : streamer_write_uhwi (ob, parm_offset_known);
492 28697 : if (parm_offset_known)
493 : {
494 19337 : streamer_write_poly_int64 (ob, parm_offset);
495 19337 : streamer_write_poly_int64 (ob, offset);
496 19337 : streamer_write_poly_int64 (ob, size);
497 19337 : streamer_write_poly_int64 (ob, max_size);
498 : }
499 : }
500 28983 : }
501 :
502 : modref_access_node
503 21603 : modref_access_node::stream_in (struct lto_input_block *ib)
504 : {
505 21603 : int parm_index = streamer_read_hwi (ib);
506 21603 : bool parm_offset_known = false;
507 21603 : poly_int64 parm_offset = 0;
508 21603 : poly_int64 offset = 0;
509 21603 : poly_int64 size = -1;
510 21603 : poly_int64 max_size = -1;
511 :
512 21603 : if (parm_index != MODREF_UNKNOWN_PARM)
513 : {
514 21317 : parm_offset_known = streamer_read_uhwi (ib);
515 21317 : if (parm_offset_known)
516 : {
517 13908 : parm_offset = streamer_read_poly_int64 (ib);
518 13908 : offset = streamer_read_poly_int64 (ib);
519 13908 : size = streamer_read_poly_int64 (ib);
520 13908 : max_size = streamer_read_poly_int64 (ib);
521 : }
522 : }
523 21603 : return {offset, size, max_size, parm_offset, parm_index,
524 21603 : parm_offset_known, false};
525 : }
526 :
527 : /* Insert access with OFFSET and SIZE.
528 : Collapse tree if it has more than MAX_ACCESSES entries.
529 : If RECORD_ADJUSTMENTs is true avoid too many interval extensions.
530 : Return true if record was changed.
531 :
532 : Return 0 if nothing changed, 1 if insert was successful and -1
533 : if entries should be collapsed. */
534 : int
535 9226365 : modref_access_node::insert (vec <modref_access_node, va_gc> *&accesses,
536 : modref_access_node a, size_t max_accesses,
537 : bool record_adjustments)
538 : {
539 9226365 : size_t i, j;
540 9226365 : modref_access_node *a2;
541 :
542 : /* Verify that list does not contain redundant accesses. */
543 9226365 : if (flag_checking)
544 : {
545 : size_t i, i2;
546 : modref_access_node *a, *a2;
547 :
548 19705006 : FOR_EACH_VEC_SAFE_ELT (accesses, i, a)
549 : {
550 23490012 : FOR_EACH_VEC_SAFE_ELT (accesses, i2, a2)
551 13011360 : if (i != i2)
552 7772034 : gcc_assert (!a->contains (*a2));
553 : }
554 : }
555 :
556 11421787 : FOR_EACH_VEC_SAFE_ELT (accesses, i, a2)
557 : {
558 4923566 : if (a2->contains (a))
559 : return 0;
560 3204239 : if (a.contains (*a2))
561 : {
562 52358 : a.adjustments = 0;
563 52358 : a2->parm_index = a.parm_index;
564 52358 : a2->parm_offset_known = a.parm_offset_known;
565 52358 : a2->update (a.parm_offset, a.offset, a.size, a.max_size,
566 : record_adjustments);
567 52358 : modref_access_node::try_merge_with (accesses, i);
568 52358 : return 1;
569 : }
570 3151881 : if (a2->merge (a, record_adjustments))
571 : {
572 956459 : modref_access_node::try_merge_with (accesses, i);
573 956459 : return 1;
574 : }
575 2195422 : gcc_checking_assert (!(a == *a2));
576 : }
577 :
578 : /* If this base->ref pair has too many accesses stored, we will clear
579 : all accesses and bail out. */
580 6498221 : if (accesses && accesses->length () >= max_accesses)
581 : {
582 1291 : if (max_accesses < 2)
583 : return -1;
584 : /* Find least harmful merge and perform it. */
585 : int best1 = -1, best2 = -1;
586 21863 : FOR_EACH_VEC_SAFE_ELT (accesses, i, a2)
587 : {
588 174778 : for (j = i + 1; j < accesses->length (); j++)
589 154206 : if (best1 < 0
590 307121 : || modref_access_node::closer_pair_p
591 305830 : (*a2, (*accesses)[j],
592 152915 : (*accesses)[best1],
593 151486 : best2 < 0 ? a : (*accesses)[best2]))
594 : {
595 15876 : best1 = i;
596 15876 : best2 = j;
597 : }
598 20572 : if (modref_access_node::closer_pair_p
599 41144 : (*a2, a,
600 20572 : (*accesses)[best1],
601 19865 : best2 < 0 ? a : (*accesses)[best2]))
602 : {
603 1184 : best1 = i;
604 1184 : best2 = -1;
605 : }
606 : }
607 1291 : (*accesses)[best1].forced_merge (best2 < 0 ? a : (*accesses)[best2],
608 : record_adjustments);
609 : /* Check that merging indeed merged ranges. */
610 1291 : gcc_checking_assert ((*accesses)[best1].contains
611 : (best2 < 0 ? a : (*accesses)[best2]));
612 1291 : if (!(*accesses)[best1].useful_p ())
613 : return -1;
614 1288 : if (dump_file && best2 >= 0)
615 1 : fprintf (dump_file,
616 : "--param modref-max-accesses limit reached;"
617 : " merging %i and %i\n", best1, best2);
618 1287 : else if (dump_file)
619 1 : fprintf (dump_file,
620 : "--param modref-max-accesses limit reached;"
621 : " merging with %i\n", best1);
622 1288 : modref_access_node::try_merge_with (accesses, best1);
623 1288 : if (best2 >= 0)
624 200 : insert (accesses, a, max_accesses, record_adjustments);
625 1288 : return 1;
626 : }
627 6496930 : a.adjustments = 0;
628 6496930 : vec_safe_push (accesses, a);
629 6496930 : return 1;
630 : }
631 :
632 : /* Return true if range info is useful. */
633 : bool
634 61906700 : modref_access_node::range_info_useful_p () const
635 : {
636 61906700 : return parm_index != MODREF_UNKNOWN_PARM
637 61906700 : && parm_index != MODREF_GLOBAL_MEMORY_PARM
638 53342565 : && parm_offset_known
639 114289633 : && (known_size_p (size)
640 566280 : || known_size_p (max_size)
641 212470 : || known_ge (offset, 0));
642 : }
643 :
644 : /* Dump range to debug OUT. */
645 : void
646 616 : modref_access_node::dump (FILE *out)
647 : {
648 616 : if (parm_index != MODREF_UNKNOWN_PARM)
649 : {
650 539 : if (parm_index == MODREF_GLOBAL_MEMORY_PARM)
651 4 : fprintf (out, " Base in global memory");
652 535 : else if (parm_index >= 0)
653 530 : fprintf (out, " Parm %i", parm_index);
654 5 : else if (parm_index == MODREF_STATIC_CHAIN_PARM)
655 5 : fprintf (out, " Static chain");
656 : else
657 0 : gcc_unreachable ();
658 539 : if (parm_offset_known)
659 : {
660 386 : fprintf (out, " param offset:");
661 386 : print_dec ((poly_int64)parm_offset, out, SIGNED);
662 : }
663 : }
664 616 : if (range_info_useful_p ())
665 : {
666 386 : fprintf (out, " offset:");
667 386 : print_dec ((poly_int64)offset, out, SIGNED);
668 386 : fprintf (out, " size:");
669 386 : print_dec ((poly_int64)size, out, SIGNED);
670 386 : fprintf (out, " max_size:");
671 386 : print_dec ((poly_int64)max_size, out, SIGNED);
672 386 : if (adjustments)
673 1 : fprintf (out, " adjusted %i times", adjustments);
674 : }
675 616 : fprintf (out, "\n");
676 616 : }
677 :
678 : /* Return tree corresponding to parameter of the range in STMT. */
679 : tree
680 13854537 : modref_access_node::get_call_arg (const gcall *stmt) const
681 : {
682 13854537 : if (parm_index == MODREF_UNKNOWN_PARM
683 13854537 : || parm_index == MODREF_GLOBAL_MEMORY_PARM)
684 : return NULL;
685 13853475 : if (parm_index == MODREF_STATIC_CHAIN_PARM)
686 357426 : return gimple_call_chain (stmt);
687 : /* MODREF_RETSLOT_PARM should not happen in access trees since the store
688 : is seen explicitly in the caller. */
689 13496049 : gcc_checking_assert (parm_index >= 0);
690 13496049 : if (parm_index >= (int)gimple_call_num_args (stmt))
691 : return NULL;
692 13496029 : return gimple_call_arg (stmt, parm_index);
693 : }
694 :
695 : /* Return tree corresponding to parameter of the range in STMT. */
696 : bool
697 7965956 : modref_access_node::get_ao_ref (const gcall *stmt, ao_ref *ref) const
698 : {
699 7965956 : tree arg;
700 :
701 7965956 : if (!parm_offset_known
702 6172748 : || !(arg = get_call_arg (stmt))
703 14138694 : || !POINTER_TYPE_P (TREE_TYPE (arg)))
704 1793276 : return false;
705 6172680 : poly_offset_int off = (poly_offset_int)offset
706 6172680 : + ((poly_offset_int)parm_offset << LOG2_BITS_PER_UNIT);
707 6172680 : poly_int64 off2;
708 6172680 : if (!off.to_shwi (&off2))
709 : return false;
710 6172680 : ao_ref_init_from_ptr_and_range (ref, arg, true, off2, size, max_size);
711 6172680 : return true;
712 : }
713 :
714 : /* Return true A is a subkill. */
715 : bool
716 4200265 : modref_access_node::contains_for_kills (const modref_access_node &a) const
717 : {
718 4200265 : poly_int64 aoffset_adj = 0;
719 :
720 4200265 : gcc_checking_assert (parm_index != MODREF_UNKNOWN_PARM
721 : && a.parm_index != MODREF_UNKNOWN_PARM);
722 4200265 : if (parm_index != a.parm_index)
723 : return false;
724 3389205 : gcc_checking_assert (parm_offset_known && a.parm_offset_known);
725 3389205 : aoffset_adj = (a.parm_offset - parm_offset)
726 3389205 : * BITS_PER_UNIT;
727 3389205 : gcc_checking_assert (range_info_useful_p () && a.range_info_useful_p ());
728 3389205 : return known_subrange_p (a.offset + aoffset_adj,
729 3389205 : a.max_size, offset, max_size);
730 : }
731 :
732 : /* Merge two ranges both starting at parm_offset1 and update THIS
733 : with result. */
734 : bool
735 458511 : modref_access_node::update_for_kills (poly_int64 parm_offset1,
736 : poly_int64 offset1,
737 : poly_int64 max_size1,
738 : poly_int64 offset2,
739 : poly_int64 max_size2,
740 : bool record_adjustments)
741 : {
742 458511 : if (known_le (offset1, offset2))
743 : ;
744 51317 : else if (known_le (offset2, offset1))
745 : {
746 51317 : std::swap (offset1, offset2);
747 51317 : std::swap (max_size1, max_size2);
748 : }
749 : else
750 : gcc_unreachable ();
751 :
752 458511 : poly_int64 new_max_size = max_size2 + offset2 - offset1;
753 458511 : if (known_le (new_max_size, max_size1))
754 : new_max_size = max_size1;
755 458511 : if (known_eq (parm_offset, parm_offset1)
756 442229 : && known_eq (offset, offset1)
757 401561 : && known_eq (size, new_max_size)
758 458511 : && known_eq (max_size, new_max_size))
759 : return false;
760 :
761 458511 : if (!record_adjustments
762 458511 : || (++adjustments) < param_modref_max_adjustments)
763 : {
764 458511 : parm_offset = parm_offset1;
765 458511 : offset = offset1;
766 458511 : max_size = new_max_size;
767 458511 : size = new_max_size;
768 458511 : gcc_checking_assert (useful_for_kill_p ());
769 : return true;
770 : }
771 : return false;
772 : }
773 :
774 : /* Merge in access A if it is possible to do without losing
775 : precision. Return true if successful.
776 : Unlike merge assume that both accesses are always executed
777 : and merge size the same was as max_size. */
778 : bool
779 1161567 : modref_access_node::merge_for_kills (const modref_access_node &a,
780 : bool record_adjustments)
781 : {
782 1161567 : poly_int64 offset1 = 0;
783 1161567 : poly_int64 aoffset1 = 0;
784 1161567 : poly_int64 new_parm_offset = 0;
785 :
786 : /* We assume that containment was tested earlier. */
787 1161567 : gcc_checking_assert (!contains_for_kills (a) && !a.contains_for_kills (*this)
788 : && useful_for_kill_p () && a.useful_for_kill_p ());
789 :
790 1161567 : if (parm_index != a.parm_index
791 1161567 : || !combined_offsets (a, &new_parm_offset, &offset1, &aoffset1))
792 253309 : return false;
793 :
794 908258 : if (known_le (offset1, aoffset1))
795 : {
796 720971 : if (!known_size_p (max_size)
797 720971 : || known_ge (offset1 + max_size, aoffset1))
798 407194 : return update_for_kills (new_parm_offset, offset1, max_size,
799 407194 : aoffset1, a.max_size, record_adjustments);
800 : }
801 187287 : else if (known_le (aoffset1, offset1))
802 : {
803 187287 : if (!known_size_p (a.max_size)
804 187287 : || known_ge (aoffset1 + a.max_size, offset1))
805 51317 : return update_for_kills (new_parm_offset, offset1, max_size,
806 51317 : aoffset1, a.max_size, record_adjustments);
807 : }
808 : return false;
809 : }
810 :
811 : /* Insert new kill A into KILLS. If RECORD_ADJUSTMENTS is true limit number
812 : of changes to each entry. Return true if something changed. */
813 :
814 : bool
815 1278989 : modref_access_node::insert_kill (vec<modref_access_node> &kills,
816 : modref_access_node &a, bool record_adjustments)
817 : {
818 1278989 : size_t index;
819 1278989 : modref_access_node *a2;
820 1278989 : bool merge = false;
821 :
822 1278989 : gcc_checking_assert (a.useful_for_kill_p ());
823 :
824 : /* See if we have corresponding entry already or we can merge with
825 : neighboring entry. */
826 1614639 : FOR_EACH_VEC_ELT (kills, index, a2)
827 : {
828 877179 : if (a2->contains_for_kills (a))
829 : return false;
830 792600 : if (a.contains_for_kills (*a2))
831 : {
832 17802 : a.adjustments = 0;
833 17802 : *a2 = a;
834 17802 : merge = true;
835 17802 : break;
836 : }
837 774798 : if (a2->merge_for_kills (a, record_adjustments))
838 : {
839 : merge = true;
840 : break;
841 : }
842 : }
843 : /* If entry was not found, insert it. */
844 1194410 : if (!merge)
845 : {
846 857423 : if ((int)kills.length () >= param_modref_max_accesses)
847 : {
848 158 : if (dump_file)
849 2 : fprintf (dump_file, "--param modref-max-accesses limit reached:");
850 158 : return false;
851 : }
852 737302 : a.adjustments = 0;
853 737302 : kills.safe_push (a);
854 737302 : return true;
855 : }
856 : /* Extending range in an entry may make it possible to merge it with
857 : other entries. */
858 : size_t i;
859 :
860 1140615 : for (i = 0; i < kills.length ();)
861 683665 : if (i != index)
862 : {
863 207352 : bool found = false, restart = false;
864 207352 : modref_access_node *a = &kills[i];
865 207352 : modref_access_node *n = &kills[index];
866 :
867 207352 : if (n->contains_for_kills (*a))
868 : found = true;
869 203066 : if (!found && n->merge_for_kills (*a, false))
870 : found = restart = true;
871 187989 : gcc_checking_assert (found || !a->merge_for_kills (*n, false));
872 207352 : if (found)
873 : {
874 23649 : kills.unordered_remove (i);
875 23649 : if (index == kills.length ())
876 : {
877 0 : index = i;
878 0 : i++;
879 : }
880 23649 : if (restart)
881 19363 : i = 0;
882 : }
883 : else
884 183703 : i++;
885 : }
886 : else
887 476313 : i++;
888 : return true;
889 : }
890 :
891 :
892 : #if CHECKING_P
893 :
894 : namespace selftest {
895 :
896 : static void
897 4 : test_insert_search_collapse ()
898 : {
899 4 : modref_base_node<alias_set_type> *base_node;
900 4 : modref_ref_node<alias_set_type> *ref_node;
901 4 : modref_access_node a = unspecified_modref_access_node;
902 :
903 4 : modref_tree<alias_set_type> *t = new modref_tree<alias_set_type>();
904 4 : ASSERT_FALSE (t->every_base);
905 :
906 : /* Insert into an empty tree. */
907 4 : t->insert (1, 2, 2, 1, 2, a, false);
908 4 : ASSERT_NE (t->bases, NULL);
909 4 : ASSERT_EQ (t->bases->length (), 1);
910 4 : ASSERT_FALSE (t->every_base);
911 4 : ASSERT_EQ (t->search (2), NULL);
912 :
913 4 : base_node = t->search (1);
914 4 : ASSERT_NE (base_node, NULL);
915 4 : ASSERT_EQ (base_node->base, 1);
916 4 : ASSERT_NE (base_node->refs, NULL);
917 4 : ASSERT_EQ (base_node->refs->length (), 1);
918 4 : ASSERT_EQ (base_node->search (1), NULL);
919 :
920 4 : ref_node = base_node->search (2);
921 4 : ASSERT_NE (ref_node, NULL);
922 4 : ASSERT_EQ (ref_node->ref, 2);
923 :
924 : /* Insert when base exists but ref does not. */
925 4 : t->insert (1, 2, 2, 1, 3, a, false);
926 4 : ASSERT_NE (t->bases, NULL);
927 4 : ASSERT_EQ (t->bases->length (), 1);
928 4 : ASSERT_EQ (t->search (1), base_node);
929 4 : ASSERT_EQ (t->search (2), NULL);
930 4 : ASSERT_NE (base_node->refs, NULL);
931 4 : ASSERT_EQ (base_node->refs->length (), 2);
932 :
933 4 : ref_node = base_node->search (3);
934 4 : ASSERT_NE (ref_node, NULL);
935 :
936 : /* Insert when base and ref exist, but access is not dominated by nor
937 : dominates other accesses. */
938 4 : t->insert (1, 2, 2, 1, 2, a, false);
939 4 : ASSERT_EQ (t->bases->length (), 1);
940 4 : ASSERT_EQ (t->search (1), base_node);
941 :
942 4 : ref_node = base_node->search (2);
943 4 : ASSERT_NE (ref_node, NULL);
944 :
945 : /* Insert when base and ref exist and access is dominated. */
946 4 : t->insert (1, 2, 2, 1, 2, a, false);
947 4 : ASSERT_EQ (t->search (1), base_node);
948 4 : ASSERT_EQ (base_node->search (2), ref_node);
949 :
950 : /* Insert ref to trigger ref list collapse for base 1. */
951 4 : t->insert (1, 2, 2, 1, 4, a, false);
952 4 : ASSERT_EQ (t->search (1), base_node);
953 4 : ASSERT_EQ (base_node->refs, NULL);
954 4 : ASSERT_EQ (base_node->search (2), NULL);
955 4 : ASSERT_EQ (base_node->search (3), NULL);
956 4 : ASSERT_TRUE (base_node->every_ref);
957 :
958 : /* Further inserts to collapsed ref list are ignored. */
959 4 : t->insert (1, 2, 2, 1, 5, a, false);
960 4 : ASSERT_EQ (t->search (1), base_node);
961 4 : ASSERT_EQ (base_node->refs, NULL);
962 4 : ASSERT_EQ (base_node->search (2), NULL);
963 4 : ASSERT_EQ (base_node->search (3), NULL);
964 4 : ASSERT_TRUE (base_node->every_ref);
965 :
966 : /* Insert base to trigger base list collapse. */
967 4 : t->insert (1, 2, 2, 5, 0, a, false);
968 4 : ASSERT_TRUE (t->every_base);
969 4 : ASSERT_EQ (t->bases, NULL);
970 4 : ASSERT_EQ (t->search (1), NULL);
971 :
972 : /* Further inserts to collapsed base list are ignored. */
973 4 : t->insert (1, 2, 2, 7, 8, a, false);
974 4 : ASSERT_TRUE (t->every_base);
975 4 : ASSERT_EQ (t->bases, NULL);
976 4 : ASSERT_EQ (t->search (1), NULL);
977 :
978 4 : delete t;
979 4 : }
980 :
981 : static void
982 4 : test_merge ()
983 : {
984 4 : modref_tree<alias_set_type> *t1, *t2;
985 4 : modref_base_node<alias_set_type> *base_node;
986 4 : modref_access_node a = unspecified_modref_access_node;
987 :
988 4 : t1 = new modref_tree<alias_set_type>();
989 4 : t1->insert (3, 4, 1, 1, 1, a, false);
990 4 : t1->insert (3, 4, 1, 1, 2, a, false);
991 4 : t1->insert (3, 4, 1, 1, 3, a, false);
992 4 : t1->insert (3, 4, 1, 2, 1, a, false);
993 4 : t1->insert (3, 4, 1, 3, 1, a, false);
994 :
995 4 : t2 = new modref_tree<alias_set_type>();
996 4 : t2->insert (10, 10, 10, 1, 2, a, false);
997 4 : t2->insert (10, 10, 10, 1, 3, a, false);
998 4 : t2->insert (10, 10, 10, 1, 4, a, false);
999 4 : t2->insert (10, 10, 10, 3, 2, a, false);
1000 4 : t2->insert (10, 10, 10, 3, 3, a, false);
1001 4 : t2->insert (10, 10, 10, 3, 4, a, false);
1002 4 : t2->insert (10, 10, 10, 3, 5, a, false);
1003 :
1004 4 : t1->merge (3, 4, 1, t2, NULL, NULL, false);
1005 :
1006 4 : ASSERT_FALSE (t1->every_base);
1007 4 : ASSERT_NE (t1->bases, NULL);
1008 4 : ASSERT_EQ (t1->bases->length (), 3);
1009 :
1010 4 : base_node = t1->search (1);
1011 4 : ASSERT_NE (base_node->refs, NULL);
1012 4 : ASSERT_FALSE (base_node->every_ref);
1013 4 : ASSERT_EQ (base_node->refs->length (), 4);
1014 :
1015 4 : base_node = t1->search (2);
1016 4 : ASSERT_NE (base_node->refs, NULL);
1017 4 : ASSERT_FALSE (base_node->every_ref);
1018 4 : ASSERT_EQ (base_node->refs->length (), 1);
1019 :
1020 4 : base_node = t1->search (3);
1021 4 : ASSERT_EQ (base_node->refs, NULL);
1022 4 : ASSERT_TRUE (base_node->every_ref);
1023 :
1024 4 : delete t1;
1025 4 : delete t2;
1026 4 : }
1027 :
1028 :
1029 : void
1030 4 : ipa_modref_tree_cc_tests ()
1031 : {
1032 4 : test_insert_search_collapse ();
1033 4 : test_merge ();
1034 4 : }
1035 :
1036 : } // namespace selftest
1037 :
1038 : #endif
1039 :
1040 : void
1041 48707236 : gt_ggc_mx (modref_tree < int >*const &tt)
1042 : {
1043 48707236 : if (tt->bases)
1044 : {
1045 7549242 : ggc_test_and_set_mark (tt->bases);
1046 7549242 : gt_ggc_mx (tt->bases);
1047 : }
1048 48707236 : }
1049 :
1050 : void
1051 241220 : gt_ggc_mx (modref_tree < tree_node * >*const &tt)
1052 : {
1053 241220 : if (tt->bases)
1054 : {
1055 179215 : ggc_test_and_set_mark (tt->bases);
1056 179215 : gt_ggc_mx (tt->bases);
1057 : }
1058 241220 : }
1059 :
1060 0 : void gt_pch_nx (modref_tree<int>* const&) {}
1061 0 : void gt_pch_nx (modref_tree<tree_node*>* const&) {}
1062 0 : void gt_pch_nx (modref_tree<int>* const&, gt_pointer_operator, void *) {}
1063 0 : void gt_pch_nx (modref_tree<tree_node*>* const&, gt_pointer_operator, void *) {}
1064 :
1065 8521294 : void gt_ggc_mx (modref_base_node<int>* &b)
1066 : {
1067 8521294 : ggc_test_and_set_mark (b);
1068 8521294 : if (b->refs)
1069 : {
1070 8520513 : ggc_test_and_set_mark (b->refs);
1071 8520513 : gt_ggc_mx (b->refs);
1072 : }
1073 8521294 : }
1074 :
1075 188289 : void gt_ggc_mx (modref_base_node<tree_node*>* &b)
1076 : {
1077 188289 : ggc_test_and_set_mark (b);
1078 188289 : if (b->refs)
1079 : {
1080 188289 : ggc_test_and_set_mark (b->refs);
1081 188289 : gt_ggc_mx (b->refs);
1082 : }
1083 188289 : if (b->base)
1084 187749 : gt_ggc_mx (b->base);
1085 188289 : }
1086 :
1087 0 : void gt_pch_nx (modref_base_node<int>*) {}
1088 0 : void gt_pch_nx (modref_base_node<tree_node*>*) {}
1089 0 : void gt_pch_nx (modref_base_node<int>*, gt_pointer_operator, void *) {}
1090 0 : void gt_pch_nx (modref_base_node<tree_node*>*, gt_pointer_operator, void *) {}
1091 :
1092 11170915 : void gt_ggc_mx (modref_ref_node<int>* &r)
1093 : {
1094 11170915 : ggc_test_and_set_mark (r);
1095 11170915 : if (r->accesses)
1096 : {
1097 8567252 : ggc_test_and_set_mark (r->accesses);
1098 8567252 : gt_ggc_mx (r->accesses);
1099 : }
1100 11170915 : }
1101 :
1102 188313 : void gt_ggc_mx (modref_ref_node<tree_node*>* &r)
1103 : {
1104 188313 : ggc_test_and_set_mark (r);
1105 188313 : if (r->accesses)
1106 : {
1107 8341 : ggc_test_and_set_mark (r->accesses);
1108 8341 : gt_ggc_mx (r->accesses);
1109 : }
1110 188313 : if (r->ref)
1111 188237 : gt_ggc_mx (r->ref);
1112 188313 : }
1113 :
1114 0 : void gt_pch_nx (modref_ref_node<int>* ) {}
1115 0 : void gt_pch_nx (modref_ref_node<tree_node*>*) {}
1116 0 : void gt_pch_nx (modref_ref_node<int>*, gt_pointer_operator, void *) {}
1117 0 : void gt_pch_nx (modref_ref_node<tree_node*>*, gt_pointer_operator, void *) {}
1118 :
1119 12204839 : void gt_ggc_mx (modref_access_node &)
1120 : {
1121 12204839 : }
|
