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 2555137 : modref_access_node::operator == (const modref_access_node &a) const
36 : {
37 2555137 : if (parm_index != a.parm_index)
38 : return false;
39 1311591 : if (parm_index != MODREF_UNKNOWN_PARM
40 1311591 : && parm_index != MODREF_GLOBAL_MEMORY_PARM)
41 : {
42 1311591 : if (parm_offset_known != a.parm_offset_known)
43 : return false;
44 1311591 : if (parm_offset_known
45 1311591 : && !known_eq (parm_offset, a.parm_offset))
46 : return false;
47 : }
48 753942 : if (range_info_useful_p () != a.range_info_useful_p ())
49 : return false;
50 753942 : if (range_info_useful_p ()
51 753942 : && (!known_eq (a.offset, offset)
52 18609 : || !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 30672660 : modref_access_node::contains (const modref_access_node &a) const
61 : {
62 30672660 : poly_offset_int aoffset_adj = 0;
63 30672660 : if (parm_index != MODREF_UNKNOWN_PARM)
64 : {
65 30672621 : if (parm_index != a.parm_index)
66 : return false;
67 19801288 : if (parm_offset_known)
68 : {
69 18679373 : 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 18666511 : if (!known_le (parm_offset, a.parm_offset)
76 18666511 : && !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 18666511 : aoffset_adj = (poly_offset_int::from (a.parm_offset, SIGNED)
84 18666511 : - poly_offset_int::from (parm_offset, SIGNED))
85 37333022 : * BITS_PER_UNIT;
86 : }
87 : }
88 19788465 : if (range_info_useful_p ())
89 : {
90 18666511 : 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 18666511 : if (known_size_p (size)
96 18666511 : && (!known_size_p (a.size)
97 18388671 : || !known_le (size, a.size)))
98 : return false;
99 15617435 : if (known_size_p (max_size))
100 15404329 : return known_subrange_p (poly_offset_int::from (a.offset, SIGNED)
101 30808658 : + aoffset_adj, a.max_size,
102 15404329 : poly_offset_int::from (offset, SIGNED),
103 15404329 : max_size);
104 : else
105 213106 : 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 1113871 : 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 1113871 : if (known_eq (parm_offset, parm_offset1)
123 1080255 : && known_eq (offset, offset1)
124 843661 : && known_eq (size, size1)
125 1941816 : && known_eq (max_size, max_size1))
126 : return;
127 1109115 : if (!record_adjustments
128 1109115 : || (++adjustments) < param_modref_max_adjustments)
129 : {
130 1109057 : parm_offset = parm_offset1;
131 1109057 : offset = offset1;
132 1109057 : size = size1;
133 1109057 : 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 5290752 : modref_access_node::merge (const modref_access_node &a,
174 : bool record_adjustments)
175 : {
176 5290752 : poly_int64 offset1 = 0;
177 5290752 : poly_int64 aoffset1 = 0;
178 5290752 : poly_int64 new_parm_offset = 0;
179 :
180 : /* We assume that containment was tested earlier. */
181 5290752 : gcc_checking_assert (!contains (a) && !a.contains (*this));
182 5290752 : if (parm_index != MODREF_UNKNOWN_PARM)
183 : {
184 5290752 : if (parm_index != a.parm_index)
185 : return false;
186 3336032 : if (parm_offset_known)
187 : {
188 3336032 : if (!a.parm_offset_known)
189 : return false;
190 3336032 : if (!combined_offsets (a, &new_parm_offset, &offset1, &aoffset1))
191 : return false;
192 : }
193 : }
194 : /* See if we can merge ranges. */
195 3336032 : if (range_info_useful_p ())
196 : {
197 : /* In this case we have containment that should be
198 : handled earlier. */
199 3336032 : 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 3336032 : if (known_size_p (size)
204 3336032 : && (!known_size_p (a.size) || known_lt (a.size, size)))
205 : {
206 448742 : if (((known_size_p (max_size) || known_size_p (a.max_size))
207 448704 : && !known_eq (max_size, a.max_size))
208 459002 : || !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 2887290 : if ((known_size_p (size) || known_size_p (a.size))
216 2901497 : && !known_eq (size, a.size))
217 : return false;
218 2366944 : if (known_le (offset1, aoffset1))
219 : {
220 1587009 : if (!known_size_p (max_size)
221 1587009 : || known_ge (offset1 + max_size, aoffset1))
222 : {
223 816224 : update2 (new_parm_offset, offset1, size, max_size,
224 : aoffset1, a.size, a.max_size,
225 : record_adjustments);
226 816224 : return true;
227 : }
228 : }
229 779935 : else if (known_le (aoffset1, offset1))
230 : {
231 779935 : if (!known_size_p (a.max_size)
232 779935 : || known_ge (aoffset1 + a.max_size, offset1))
233 : {
234 241391 : update2 (new_parm_offset, offset1, size, max_size,
235 : aoffset1, a.size, a.max_size,
236 : record_adjustments);
237 241391 : 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 294177 : 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 294177 : if (a1.parm_index != b1.parm_index)
259 : return false;
260 153750 : 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 151914 : gcc_checking_assert (a1.parm_offset_known && b1.parm_offset_known);
265 151914 : gcc_checking_assert (a2.parm_offset_known && b2.parm_offset_known);
266 :
267 : /* First normalize offsets for parm offsets. */
268 151914 : poly_int64 new_parm_offset, offseta1, offsetb1, offseta2, offsetb2;
269 151914 : if (!a1.combined_offsets (b1, &new_parm_offset, &offseta1, &offsetb1)
270 151914 : || !a2.combined_offsets (b2, &new_parm_offset, &offseta2, &offsetb2))
271 0 : gcc_unreachable ();
272 :
273 :
274 : /* Now compute distance of the intervals. */
275 151914 : poly_offset_int dist1, dist2;
276 151914 : if (known_le (offseta1, offsetb1))
277 : {
278 149011 : if (!known_size_p (a1.max_size))
279 0 : dist1 = 0;
280 : else
281 298022 : dist1 = (poly_offset_int)offsetb1
282 298022 : - (poly_offset_int)offseta1
283 298022 : - (poly_offset_int)a1.max_size;
284 : }
285 : else
286 : {
287 2903 : if (!known_size_p (b1.max_size))
288 0 : dist1 = 0;
289 : else
290 5806 : dist1 = (poly_offset_int)offseta1
291 5806 : - (poly_offset_int)offsetb1
292 5806 : - (poly_offset_int)b1.max_size;
293 : }
294 151914 : if (known_le (offseta2, offsetb2))
295 : {
296 148528 : if (!known_size_p (a2.max_size))
297 0 : dist2 = 0;
298 : else
299 297056 : dist2 = (poly_offset_int)offsetb2
300 297056 : - (poly_offset_int)offseta2
301 297056 : - (poly_offset_int)a2.max_size;
302 : }
303 : else
304 : {
305 3386 : if (!known_size_p (b2.max_size))
306 0 : dist2 = 0;
307 : else
308 3386 : dist2 = offseta2
309 6772 : - (poly_offset_int)offsetb2
310 6772 : - (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 151914 : if (known_lt (dist1, 0) && known_ge (dist2, 0))
315 64 : return true;
316 151850 : if (known_lt (dist2, 0) && known_ge (dist1, 0))
317 4650 : return false;
318 147200 : 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 146829 : return known_le (dist1, dist2);
324 : }
325 :
326 : /* Merge in access A while losing precision. */
327 : void
328 2185 : modref_access_node::forced_merge (const modref_access_node &a,
329 : bool record_adjustments)
330 : {
331 2185 : if (parm_index != a.parm_index)
332 : {
333 39 : gcc_checking_assert (parm_index != MODREF_UNKNOWN_PARM);
334 39 : parm_index = MODREF_UNKNOWN_PARM;
335 39 : return;
336 : }
337 :
338 : /* We assume that containment and lossless merging
339 : was tested earlier. */
340 2146 : gcc_checking_assert (!contains (a) && !a.contains (*this)
341 : && !merge (a, record_adjustments));
342 2146 : gcc_checking_assert (parm_offset_known && a.parm_offset_known);
343 :
344 2146 : poly_int64 new_parm_offset, offset1, aoffset1;
345 2146 : if (!combined_offsets (a, &new_parm_offset, &offset1, &aoffset1))
346 : {
347 0 : parm_offset_known = false;
348 0 : return;
349 : }
350 2146 : gcc_checking_assert (range_info_useful_p ()
351 : && a.range_info_useful_p ());
352 2146 : if (record_adjustments)
353 0 : adjustments += a.adjustments;
354 2146 : 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 1059761 : 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 1059761 : poly_int64 new_size = size1;
371 :
372 1059761 : if (!known_size_p (size2)
373 1059761 : || known_le (size2, size1))
374 1058367 : new_size = size2;
375 : else
376 : gcc_checking_assert (known_le (size1, size2));
377 :
378 1059761 : if (known_le (offset1, offset2))
379 : ;
380 241411 : else if (known_le (offset2, offset1))
381 : {
382 241411 : std::swap (offset1, offset2);
383 241411 : std::swap (max_size1, max_size2);
384 : }
385 : else
386 : gcc_unreachable ();
387 :
388 1059761 : poly_int64 new_max_size;
389 :
390 1059761 : if (!known_size_p (max_size1))
391 2 : new_max_size = max_size1;
392 1059759 : else if (!known_size_p (max_size2))
393 2776 : new_max_size = max_size2;
394 : else
395 : {
396 3170949 : poly_offset_int s = (poly_offset_int)max_size2
397 2113966 : + (poly_offset_int)offset2
398 1056983 : - (poly_offset_int)offset1;
399 1056983 : if (s.to_shwi (&new_max_size))
400 : {
401 1056983 : 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 1059761 : update (parm_offset1, offset1,
409 : new_size, new_max_size, record_adjustments);
410 1059761 : }
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 4647887 : 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 4647887 : gcc_checking_assert (parm_offset_known && a.parm_offset_known);
424 4647887 : if (known_le (a.parm_offset, parm_offset))
425 : {
426 3381339 : *new_offset = offset
427 3381339 : + ((parm_offset - a.parm_offset)
428 3381339 : << LOG2_BITS_PER_UNIT);
429 3381339 : *new_aoffset = a.offset;
430 3381339 : *new_parm_offset = a.parm_offset;
431 3381339 : return true;
432 : }
433 1266548 : else if (known_le (parm_offset, a.parm_offset))
434 : {
435 1266548 : *new_aoffset = a.offset
436 1266548 : + ((a.parm_offset - parm_offset)
437 1266548 : << LOG2_BITS_PER_UNIT);
438 1266548 : *new_offset = offset;
439 1266548 : *new_parm_offset = parm_offset;
440 1266548 : 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 1079097 : modref_access_node::try_merge_with (vec <modref_access_node, va_gc> *&accesses,
449 : size_t index)
450 : {
451 1079097 : size_t i;
452 :
453 3070857 : for (i = 0; i < accesses->length ();)
454 1991760 : if (i != index)
455 : {
456 880471 : bool found = false, restart = false;
457 880471 : modref_access_node *a = &(*accesses)[i];
458 880471 : modref_access_node *n = &(*accesses)[index];
459 :
460 880471 : if (n->contains (*a))
461 : found = true;
462 872701 : if (!found && n->merge (*a, false))
463 : found = restart = true;
464 845697 : gcc_checking_assert (found || !a->merge (*n, false));
465 880471 : if (found)
466 : {
467 42544 : accesses->unordered_remove (i);
468 42544 : if (index == accesses->length ())
469 : {
470 2489 : index = i;
471 2489 : i++;
472 : }
473 42544 : if (restart)
474 34774 : i = 0;
475 : }
476 : else
477 837927 : i++;
478 : }
479 : else
480 1111289 : i++;
481 1079097 : }
482 :
483 : /* Stream out to OB. */
484 :
485 : void
486 29436 : modref_access_node::stream_out (struct output_block *ob) const
487 : {
488 29436 : streamer_write_hwi (ob, parm_index);
489 29436 : if (parm_index != MODREF_UNKNOWN_PARM)
490 : {
491 29150 : streamer_write_uhwi (ob, parm_offset_known);
492 29150 : if (parm_offset_known)
493 : {
494 19717 : streamer_write_poly_int64 (ob, parm_offset);
495 19717 : streamer_write_poly_int64 (ob, offset);
496 19717 : streamer_write_poly_int64 (ob, size);
497 19717 : streamer_write_poly_int64 (ob, max_size);
498 : }
499 : }
500 29436 : }
501 :
502 : modref_access_node
503 21892 : modref_access_node::stream_in (struct lto_input_block *ib)
504 : {
505 21892 : int parm_index = streamer_read_hwi (ib);
506 21892 : bool parm_offset_known = false;
507 21892 : poly_int64 parm_offset = 0;
508 21892 : poly_int64 offset = 0;
509 21892 : poly_int64 size = -1;
510 21892 : poly_int64 max_size = -1;
511 :
512 21892 : if (parm_index != MODREF_UNKNOWN_PARM)
513 : {
514 21606 : parm_offset_known = streamer_read_uhwi (ib);
515 21606 : if (parm_offset_known)
516 : {
517 14195 : parm_offset = streamer_read_poly_int64 (ib);
518 14195 : offset = streamer_read_poly_int64 (ib);
519 14195 : size = streamer_read_poly_int64 (ib);
520 14195 : max_size = streamer_read_poly_int64 (ib);
521 : }
522 : }
523 21892 : return {offset, size, max_size, parm_offset, parm_index,
524 21892 : 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 9593045 : 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 9593045 : size_t i, j;
540 9593045 : modref_access_node *a2;
541 :
542 : /* Verify that list does not contain redundant accesses. */
543 9593045 : if (flag_checking)
544 : {
545 : size_t i, i2;
546 : modref_access_node *a, *a2;
547 :
548 21097044 : FOR_EACH_VEC_SAFE_ELT (accesses, i, a)
549 : {
550 27439673 : FOR_EACH_VEC_SAFE_ELT (accesses, i2, a2)
551 15935663 : if (i != i2)
552 10183658 : gcc_assert (!a->contains (*a2));
553 : }
554 : }
555 :
556 12148182 : FOR_EACH_VEC_SAFE_ELT (accesses, i, a2)
557 : {
558 5388462 : if (a2->contains (a))
559 : return 0;
560 3632088 : if (a.contains (*a2))
561 : {
562 54110 : a.adjustments = 0;
563 54110 : a2->parm_index = a.parm_index;
564 54110 : a2->parm_offset_known = a.parm_offset_known;
565 54110 : a2->update (a.parm_offset, a.offset, a.size, a.max_size,
566 : record_adjustments);
567 54110 : modref_access_node::try_merge_with (accesses, i);
568 54110 : return 1;
569 : }
570 3577978 : if (a2->merge (a, record_adjustments))
571 : {
572 1022841 : modref_access_node::try_merge_with (accesses, i);
573 1022841 : return 1;
574 : }
575 2555137 : 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 6759720 : if (accesses && accesses->length () >= max_accesses)
581 : {
582 2185 : if (max_accesses < 2)
583 : return -1;
584 : /* Find least harmful merge and perform it. */
585 : int best1 = -1, best2 = -1;
586 37061 : FOR_EACH_VEC_SAFE_ELT (accesses, i, a2)
587 : {
588 296362 : for (j = i + 1; j < accesses->length (); j++)
589 261486 : if (best1 < 0
590 520787 : || modref_access_node::closer_pair_p
591 518602 : (*a2, (*accesses)[j],
592 259301 : (*accesses)[best1],
593 257870 : best2 < 0 ? a : (*accesses)[best2]))
594 : {
595 28648 : best1 = i;
596 28648 : best2 = j;
597 : }
598 34876 : if (modref_access_node::closer_pair_p
599 69752 : (*a2, a,
600 34876 : (*accesses)[best1],
601 33816 : best2 < 0 ? a : (*accesses)[best2]))
602 : {
603 1990 : best1 = i;
604 1990 : best2 = -1;
605 : }
606 : }
607 2185 : (*accesses)[best1].forced_merge (best2 < 0 ? a : (*accesses)[best2],
608 : record_adjustments);
609 : /* Check that merging indeed merged ranges. */
610 2185 : gcc_checking_assert ((*accesses)[best1].contains
611 : (best2 < 0 ? a : (*accesses)[best2]));
612 2185 : if (!(*accesses)[best1].useful_p ())
613 : return -1;
614 2146 : 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 2145 : else if (dump_file)
619 1 : fprintf (dump_file,
620 : "--param modref-max-accesses limit reached;"
621 : " merging with %i\n", best1);
622 2146 : modref_access_node::try_merge_with (accesses, best1);
623 2146 : if (best2 >= 0)
624 254 : insert (accesses, a, max_accesses, record_adjustments);
625 2146 : return 1;
626 : }
627 6757535 : a.adjustments = 0;
628 6757535 : vec_safe_push (accesses, a);
629 6757535 : return 1;
630 : }
631 :
632 : /* Return true if range info is useful. */
633 : bool
634 74404268 : modref_access_node::range_info_useful_p () const
635 : {
636 74404268 : return parm_index != MODREF_UNKNOWN_PARM
637 74404268 : && parm_index != MODREF_GLOBAL_MEMORY_PARM
638 65601385 : && parm_offset_known
639 139043169 : && (known_size_p (size)
640 602186 : || known_size_p (max_size)
641 225367 : || known_ge (offset, 0));
642 : }
643 :
644 : /* Dump range to debug OUT. */
645 : void
646 618 : modref_access_node::dump (FILE *out)
647 : {
648 618 : if (parm_index != MODREF_UNKNOWN_PARM)
649 : {
650 541 : if (parm_index == MODREF_GLOBAL_MEMORY_PARM)
651 4 : fprintf (out, " Base in global memory");
652 537 : else if (parm_index >= 0)
653 532 : 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 541 : if (parm_offset_known)
659 : {
660 388 : fprintf (out, " param offset:");
661 388 : print_dec ((poly_int64)parm_offset, out, SIGNED);
662 : }
663 : }
664 618 : if (range_info_useful_p ())
665 : {
666 388 : fprintf (out, " offset:");
667 388 : print_dec ((poly_int64)offset, out, SIGNED);
668 388 : fprintf (out, " size:");
669 388 : print_dec ((poly_int64)size, out, SIGNED);
670 388 : fprintf (out, " max_size:");
671 388 : print_dec ((poly_int64)max_size, out, SIGNED);
672 388 : if (adjustments)
673 1 : fprintf (out, " adjusted %i times", adjustments);
674 : }
675 618 : fprintf (out, "\n");
676 618 : }
677 :
678 : /* Return tree corresponding to parameter of the range in STMT. */
679 : tree
680 13603228 : modref_access_node::get_call_arg (const gcall *stmt) const
681 : {
682 13603228 : if (parm_index == MODREF_UNKNOWN_PARM
683 13603228 : || parm_index == MODREF_GLOBAL_MEMORY_PARM)
684 : return NULL;
685 13602145 : if (parm_index == MODREF_STATIC_CHAIN_PARM)
686 366577 : 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 13235568 : gcc_checking_assert (parm_index >= 0);
690 13235568 : if (parm_index >= (int)gimple_call_num_args (stmt))
691 : return NULL;
692 13235548 : return gimple_call_arg (stmt, parm_index);
693 : }
694 :
695 : /* Return tree corresponding to parameter of the range in STMT. */
696 : bool
697 7807229 : modref_access_node::get_ao_ref (const gcall *stmt, ao_ref *ref) const
698 : {
699 7807229 : tree arg;
700 :
701 7807229 : if (!parm_offset_known
702 6050285 : || !(arg = get_call_arg (stmt))
703 13857504 : || !POINTER_TYPE_P (TREE_TYPE (arg)))
704 1757012 : return false;
705 6050217 : poly_offset_int off = (poly_offset_int)offset
706 6050217 : + ((poly_offset_int)parm_offset << LOG2_BITS_PER_UNIT);
707 6050217 : poly_int64 off2;
708 6050217 : if (!off.to_shwi (&off2))
709 : return false;
710 6050217 : ao_ref_init_from_ptr_and_range (ref, arg, true, off2, size, max_size);
711 6050217 : return true;
712 : }
713 :
714 : /* Return true A is a subkill. */
715 : bool
716 4640933 : modref_access_node::contains_for_kills (const modref_access_node &a) const
717 : {
718 4640933 : poly_int64 aoffset_adj = 0;
719 :
720 4640933 : gcc_checking_assert (parm_index != MODREF_UNKNOWN_PARM
721 : && a.parm_index != MODREF_UNKNOWN_PARM);
722 4640933 : if (parm_index != a.parm_index)
723 : return false;
724 3737501 : gcc_checking_assert (parm_offset_known && a.parm_offset_known);
725 3737501 : aoffset_adj = (a.parm_offset - parm_offset)
726 3737501 : * BITS_PER_UNIT;
727 3737501 : gcc_checking_assert (range_info_useful_p () && a.range_info_useful_p ());
728 3737501 : return known_subrange_p (a.offset + aoffset_adj,
729 3737501 : 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 502227 : 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 502227 : if (known_le (offset1, offset2))
743 : ;
744 52837 : else if (known_le (offset2, offset1))
745 : {
746 52837 : std::swap (offset1, offset2);
747 52837 : std::swap (max_size1, max_size2);
748 : }
749 : else
750 : gcc_unreachable ();
751 :
752 502227 : poly_int64 new_max_size = max_size2 + offset2 - offset1;
753 502227 : if (known_le (new_max_size, max_size1))
754 : new_max_size = max_size1;
755 502227 : if (known_eq (parm_offset, parm_offset1)
756 485318 : && known_eq (offset, offset1)
757 443689 : && known_eq (size, new_max_size)
758 502227 : && known_eq (max_size, new_max_size))
759 : return false;
760 :
761 502227 : if (!record_adjustments
762 502227 : || (++adjustments) < param_modref_max_adjustments)
763 : {
764 502227 : parm_offset = parm_offset1;
765 502227 : offset = offset1;
766 502227 : max_size = new_max_size;
767 502227 : size = new_max_size;
768 502227 : 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 1287515 : modref_access_node::merge_for_kills (const modref_access_node &a,
780 : bool record_adjustments)
781 : {
782 1287515 : poly_int64 offset1 = 0;
783 1287515 : poly_int64 aoffset1 = 0;
784 1287515 : poly_int64 new_parm_offset = 0;
785 :
786 : /* We assume that containment was tested earlier. */
787 1287515 : gcc_checking_assert (!contains_for_kills (a) && !a.contains_for_kills (*this)
788 : && useful_for_kill_p () && a.useful_for_kill_p ());
789 :
790 1287515 : if (parm_index != a.parm_index
791 1287515 : || !combined_offsets (a, &new_parm_offset, &offset1, &aoffset1))
792 281634 : return false;
793 :
794 1005881 : if (known_le (offset1, aoffset1))
795 : {
796 800303 : if (!known_size_p (max_size)
797 800303 : || known_ge (offset1 + max_size, aoffset1))
798 449390 : return update_for_kills (new_parm_offset, offset1, max_size,
799 449390 : aoffset1, a.max_size, record_adjustments);
800 : }
801 205578 : else if (known_le (aoffset1, offset1))
802 : {
803 205578 : if (!known_size_p (a.max_size)
804 205578 : || known_ge (aoffset1 + a.max_size, offset1))
805 52837 : return update_for_kills (new_parm_offset, offset1, max_size,
806 52837 : 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 1366492 : modref_access_node::insert_kill (vec<modref_access_node> &kills,
816 : modref_access_node &a, bool record_adjustments)
817 : {
818 1366492 : size_t index;
819 1366492 : modref_access_node *a2;
820 1366492 : bool merge = false;
821 :
822 1366492 : 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 1738256 : FOR_EACH_VEC_ELT (kills, index, a2)
827 : {
828 962323 : if (a2->contains_for_kills (a))
829 : return false;
830 872156 : if (a.contains_for_kills (*a2))
831 : {
832 18336 : a.adjustments = 0;
833 18336 : *a2 = a;
834 18336 : merge = true;
835 18336 : break;
836 : }
837 853820 : 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 1276325 : if (!merge)
845 : {
846 902593 : if ((int)kills.length () >= param_modref_max_accesses)
847 : {
848 244 : if (dump_file)
849 2 : fprintf (dump_file, "--param modref-max-accesses limit reached:");
850 244 : return false;
851 : }
852 775689 : a.adjustments = 0;
853 775689 : kills.safe_push (a);
854 775689 : 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 1252379 : for (i = 0; i < kills.length ();)
861 751987 : if (i != index)
862 : {
863 231424 : bool found = false, restart = false;
864 231424 : modref_access_node *a = &kills[i];
865 231424 : modref_access_node *n = &kills[index];
866 :
867 231424 : if (n->contains_for_kills (*a))
868 : found = true;
869 226933 : if (!found && n->merge_for_kills (*a, false))
870 : found = restart = true;
871 211253 : gcc_checking_assert (found || !a->merge_for_kills (*n, false));
872 231424 : if (found)
873 : {
874 24662 : kills.unordered_remove (i);
875 24662 : if (index == kills.length ())
876 : {
877 0 : index = i;
878 0 : i++;
879 : }
880 24662 : if (restart)
881 20171 : i = 0;
882 : }
883 : else
884 206762 : i++;
885 : }
886 : else
887 520563 : 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 83658228 : gt_ggc_mx (modref_tree < int >*const &tt)
1042 : {
1043 83658228 : if (tt->bases)
1044 : {
1045 12453258 : ggc_test_and_set_mark (tt->bases);
1046 12453258 : gt_ggc_mx (tt->bases);
1047 : }
1048 83658228 : }
1049 :
1050 : void
1051 243294 : gt_ggc_mx (modref_tree < tree_node * >*const &tt)
1052 : {
1053 243294 : if (tt->bases)
1054 : {
1055 179639 : ggc_test_and_set_mark (tt->bases);
1056 179639 : gt_ggc_mx (tt->bases);
1057 : }
1058 243294 : }
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 13907947 : void gt_ggc_mx (modref_base_node<int>* &b)
1066 : {
1067 13907947 : ggc_test_and_set_mark (b);
1068 13907947 : if (b->refs)
1069 : {
1070 13906856 : ggc_test_and_set_mark (b->refs);
1071 13906856 : gt_ggc_mx (b->refs);
1072 : }
1073 13907947 : }
1074 :
1075 188443 : void gt_ggc_mx (modref_base_node<tree_node*>* &b)
1076 : {
1077 188443 : ggc_test_and_set_mark (b);
1078 188443 : if (b->refs)
1079 : {
1080 188443 : ggc_test_and_set_mark (b->refs);
1081 188443 : gt_ggc_mx (b->refs);
1082 : }
1083 188443 : if (b->base)
1084 187902 : gt_ggc_mx (b->base);
1085 188443 : }
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 19013112 : void gt_ggc_mx (modref_ref_node<int>* &r)
1093 : {
1094 19013112 : ggc_test_and_set_mark (r);
1095 19013112 : if (r->accesses)
1096 : {
1097 15147946 : ggc_test_and_set_mark (r->accesses);
1098 15147946 : gt_ggc_mx (r->accesses);
1099 : }
1100 19013112 : }
1101 :
1102 188467 : void gt_ggc_mx (modref_ref_node<tree_node*>* &r)
1103 : {
1104 188467 : ggc_test_and_set_mark (r);
1105 188467 : if (r->accesses)
1106 : {
1107 8346 : ggc_test_and_set_mark (r->accesses);
1108 8346 : gt_ggc_mx (r->accesses);
1109 : }
1110 188467 : if (r->ref)
1111 188391 : gt_ggc_mx (r->ref);
1112 188467 : }
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 22005693 : void gt_ggc_mx (modref_access_node &)
1120 : {
1121 22005693 : }
|
