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 2373757 : modref_access_node::operator == (const modref_access_node &a) const
36 : {
37 2373757 : if (parm_index != a.parm_index)
38 : return false;
39 1215468 : if (parm_index != MODREF_UNKNOWN_PARM
40 1215468 : && parm_index != MODREF_GLOBAL_MEMORY_PARM)
41 : {
42 1215468 : if (parm_offset_known != a.parm_offset_known)
43 : return false;
44 1215468 : if (parm_offset_known
45 1215468 : && !known_eq (parm_offset, a.parm_offset))
46 : return false;
47 : }
48 727796 : if (range_info_useful_p () != a.range_info_useful_p ())
49 : return false;
50 727796 : if (range_info_useful_p ()
51 727796 : && (!known_eq (a.offset, offset)
52 21020 : || !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 28266535 : modref_access_node::contains (const modref_access_node &a) const
61 : {
62 28266535 : poly_offset_int aoffset_adj = 0;
63 28266535 : if (parm_index != MODREF_UNKNOWN_PARM)
64 : {
65 28266514 : if (parm_index != a.parm_index)
66 : return false;
67 18340318 : if (parm_offset_known)
68 : {
69 17238935 : 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 17226159 : if (!known_le (parm_offset, a.parm_offset)
76 17226159 : && !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 17226159 : aoffset_adj = (poly_offset_int::from (a.parm_offset, SIGNED)
84 17226159 : - poly_offset_int::from (parm_offset, SIGNED))
85 34452318 : * BITS_PER_UNIT;
86 : }
87 : }
88 18327563 : if (range_info_useful_p ())
89 : {
90 17226159 : 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 17226159 : if (known_size_p (size)
96 17226159 : && (!known_size_p (a.size)
97 16968485 : || !known_le (size, a.size)))
98 : return false;
99 14358461 : if (known_size_p (max_size))
100 14198240 : return known_subrange_p (poly_offset_int::from (a.offset, SIGNED)
101 28396480 : + aoffset_adj, a.max_size,
102 14198240 : poly_offset_int::from (offset, SIGNED),
103 14198240 : max_size);
104 : else
105 160221 : 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 1072354 : 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 1072354 : if (known_eq (parm_offset, parm_offset1)
123 1046667 : && known_eq (offset, offset1)
124 817965 : && known_eq (size, size1)
125 1875638 : && known_eq (max_size, max_size1))
126 : return;
127 1067258 : if (!record_adjustments
128 1067258 : || (++adjustments) < param_modref_max_adjustments)
129 : {
130 1067200 : parm_offset = parm_offset1;
131 1067200 : offset = offset1;
132 1067200 : size = size1;
133 1067200 : 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 4942578 : modref_access_node::merge (const modref_access_node &a,
174 : bool record_adjustments)
175 : {
176 4942578 : poly_int64 offset1 = 0;
177 4942578 : poly_int64 aoffset1 = 0;
178 4942578 : poly_int64 new_parm_offset = 0;
179 :
180 : /* We assume that containment was tested earlier. */
181 4942578 : gcc_checking_assert (!contains (a) && !a.contains (*this));
182 4942578 : if (parm_index != MODREF_UNKNOWN_PARM)
183 : {
184 4942578 : if (parm_index != a.parm_index)
185 : return false;
186 3134553 : if (parm_offset_known)
187 : {
188 3134553 : if (!a.parm_offset_known)
189 : return false;
190 3134553 : if (!combined_offsets (a, &new_parm_offset, &offset1, &aoffset1))
191 : return false;
192 : }
193 : }
194 : /* See if we can merge ranges. */
195 3134553 : if (range_info_useful_p ())
196 : {
197 : /* In this case we have containment that should be
198 : handled earlier. */
199 3134553 : 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 3134553 : if (known_size_p (size)
204 3134553 : && (!known_size_p (a.size) || known_lt (a.size, size)))
205 : {
206 425414 : if (((known_size_p (max_size) || known_size_p (a.max_size))
207 425382 : && !known_eq (max_size, a.max_size))
208 435205 : || !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 2709139 : if ((known_size_p (size) || known_size_p (a.size))
216 2722043 : && !known_eq (size, a.size))
217 : return false;
218 2214836 : if (known_le (offset1, aoffset1))
219 : {
220 1507215 : if (!known_size_p (max_size)
221 1507215 : || known_ge (offset1 + max_size, aoffset1))
222 : {
223 792008 : update2 (new_parm_offset, offset1, size, max_size,
224 : aoffset1, a.size, a.max_size,
225 : record_adjustments);
226 792008 : return true;
227 : }
228 : }
229 707621 : else if (known_le (aoffset1, offset1))
230 : {
231 707621 : if (!known_size_p (a.max_size)
232 707621 : || known_ge (aoffset1 + a.max_size, offset1))
233 : {
234 227125 : update2 (new_parm_offset, offset1, size, max_size,
235 : aoffset1, a.size, a.max_size,
236 : record_adjustments);
237 227125 : 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 189417 : 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 189417 : if (a1.parm_index != b1.parm_index)
259 : return false;
260 103672 : 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 102552 : gcc_checking_assert (a1.parm_offset_known && b1.parm_offset_known);
265 102552 : gcc_checking_assert (a2.parm_offset_known && b2.parm_offset_known);
266 :
267 : /* First normalize offsets for parm offsets. */
268 102552 : poly_int64 new_parm_offset, offseta1, offsetb1, offseta2, offsetb2;
269 102552 : if (!a1.combined_offsets (b1, &new_parm_offset, &offseta1, &offsetb1)
270 102552 : || !a2.combined_offsets (b2, &new_parm_offset, &offseta2, &offsetb2))
271 0 : gcc_unreachable ();
272 :
273 :
274 : /* Now compute distance of the intervals. */
275 102552 : poly_offset_int dist1, dist2;
276 102552 : if (known_le (offseta1, offsetb1))
277 : {
278 99653 : if (!known_size_p (a1.max_size))
279 0 : dist1 = 0;
280 : else
281 199306 : dist1 = (poly_offset_int)offsetb1
282 199306 : - (poly_offset_int)offseta1
283 199306 : - (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 102552 : if (known_le (offseta2, offsetb2))
295 : {
296 99168 : if (!known_size_p (a2.max_size))
297 0 : dist2 = 0;
298 : else
299 198336 : dist2 = (poly_offset_int)offsetb2
300 198336 : - (poly_offset_int)offseta2
301 198336 : - (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 102552 : if (known_lt (dist1, 0) && known_ge (dist2, 0))
315 64 : return true;
316 102488 : if (known_lt (dist2, 0) && known_ge (dist1, 0))
317 4650 : return false;
318 97838 : 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 97467 : return known_le (dist1, dist2);
324 : }
325 :
326 : /* Merge in access A while losing precision. */
327 : void
328 1409 : modref_access_node::forced_merge (const modref_access_node &a,
329 : bool record_adjustments)
330 : {
331 1409 : if (parm_index != a.parm_index)
332 : {
333 21 : gcc_checking_assert (parm_index != MODREF_UNKNOWN_PARM);
334 21 : parm_index = MODREF_UNKNOWN_PARM;
335 21 : return;
336 : }
337 :
338 : /* We assume that containment and lossless merging
339 : was tested earlier. */
340 1388 : gcc_checking_assert (!contains (a) && !a.contains (*this)
341 : && !merge (a, record_adjustments));
342 1388 : gcc_checking_assert (parm_offset_known && a.parm_offset_known);
343 :
344 1388 : poly_int64 new_parm_offset, offset1, aoffset1;
345 1388 : if (!combined_offsets (a, &new_parm_offset, &offset1, &aoffset1))
346 : {
347 0 : parm_offset_known = false;
348 0 : return;
349 : }
350 1388 : gcc_checking_assert (range_info_useful_p ()
351 : && a.range_info_useful_p ());
352 1388 : if (record_adjustments)
353 0 : adjustments += a.adjustments;
354 1388 : 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 1020521 : 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 1020521 : poly_int64 new_size = size1;
371 :
372 1020521 : if (!known_size_p (size2)
373 1020521 : || known_le (size2, size1))
374 1019751 : new_size = size2;
375 : else
376 : gcc_checking_assert (known_le (size1, size2));
377 :
378 1020521 : if (known_le (offset1, offset2))
379 : ;
380 227143 : else if (known_le (offset2, offset1))
381 : {
382 227143 : std::swap (offset1, offset2);
383 227143 : std::swap (max_size1, max_size2);
384 : }
385 : else
386 : gcc_unreachable ();
387 :
388 1020521 : poly_int64 new_max_size;
389 :
390 1020521 : if (!known_size_p (max_size1))
391 2 : new_max_size = max_size1;
392 1020519 : else if (!known_size_p (max_size2))
393 1459 : new_max_size = max_size2;
394 : else
395 : {
396 3057180 : poly_offset_int s = (poly_offset_int)max_size2
397 2038120 : + (poly_offset_int)offset2
398 1019060 : - (poly_offset_int)offset1;
399 1019060 : if (s.to_shwi (&new_max_size))
400 : {
401 1019060 : 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 1020521 : update (parm_offset1, offset1,
409 : new_size, new_max_size, record_adjustments);
410 1020521 : }
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 4299199 : 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 4299199 : gcc_checking_assert (parm_offset_known && a.parm_offset_known);
424 4299199 : if (known_le (a.parm_offset, parm_offset))
425 : {
426 3111579 : *new_offset = offset
427 3111579 : + ((parm_offset - a.parm_offset)
428 3111579 : << LOG2_BITS_PER_UNIT);
429 3111579 : *new_aoffset = a.offset;
430 3111579 : *new_parm_offset = a.parm_offset;
431 3111579 : return true;
432 : }
433 1187620 : else if (known_le (parm_offset, a.parm_offset))
434 : {
435 1187620 : *new_aoffset = a.offset
436 1187620 : + ((a.parm_offset - parm_offset)
437 1187620 : << LOG2_BITS_PER_UNIT);
438 1187620 : *new_offset = offset;
439 1187620 : *new_parm_offset = parm_offset;
440 1187620 : 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 1039633 : modref_access_node::try_merge_with (vec <modref_access_node, va_gc> *&accesses,
449 : size_t index)
450 : {
451 1039633 : size_t i;
452 :
453 2923918 : for (i = 0; i < accesses->length ();)
454 1884285 : if (i != index)
455 : {
456 814185 : bool found = false, restart = false;
457 814185 : modref_access_node *a = &(*accesses)[i];
458 814185 : modref_access_node *n = &(*accesses)[index];
459 :
460 814185 : if (n->contains (*a))
461 : found = true;
462 806871 : if (!found && n->merge (*a, false))
463 : found = restart = true;
464 781464 : gcc_checking_assert (found || !a->merge (*n, false));
465 814185 : if (found)
466 : {
467 40035 : accesses->unordered_remove (i);
468 40035 : if (index == accesses->length ())
469 : {
470 2161 : index = i;
471 2161 : i++;
472 : }
473 40035 : if (restart)
474 32721 : i = 0;
475 : }
476 : else
477 774150 : i++;
478 : }
479 : else
480 1070100 : i++;
481 1039633 : }
482 :
483 : /* Stream out to OB. */
484 :
485 : void
486 29186 : modref_access_node::stream_out (struct output_block *ob) const
487 : {
488 29186 : streamer_write_hwi (ob, parm_index);
489 29186 : if (parm_index != MODREF_UNKNOWN_PARM)
490 : {
491 28900 : streamer_write_uhwi (ob, parm_offset_known);
492 28900 : if (parm_offset_known)
493 : {
494 19538 : streamer_write_poly_int64 (ob, parm_offset);
495 19538 : streamer_write_poly_int64 (ob, offset);
496 19538 : streamer_write_poly_int64 (ob, size);
497 19538 : streamer_write_poly_int64 (ob, max_size);
498 : }
499 : }
500 29186 : }
501 :
502 : modref_access_node
503 21804 : modref_access_node::stream_in (struct lto_input_block *ib)
504 : {
505 21804 : int parm_index = streamer_read_hwi (ib);
506 21804 : bool parm_offset_known = false;
507 21804 : poly_int64 parm_offset = 0;
508 21804 : poly_int64 offset = 0;
509 21804 : poly_int64 size = -1;
510 21804 : poly_int64 max_size = -1;
511 :
512 21804 : if (parm_index != MODREF_UNKNOWN_PARM)
513 : {
514 21518 : parm_offset_known = streamer_read_uhwi (ib);
515 21518 : if (parm_offset_known)
516 : {
517 14109 : parm_offset = streamer_read_poly_int64 (ib);
518 14109 : offset = streamer_read_poly_int64 (ib);
519 14109 : size = streamer_read_poly_int64 (ib);
520 14109 : max_size = streamer_read_poly_int64 (ib);
521 : }
522 : }
523 21804 : return {offset, size, max_size, parm_offset, parm_index,
524 21804 : 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 9214023 : 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 9214023 : size_t i, j;
540 9214023 : modref_access_node *a2;
541 :
542 : /* Verify that list does not contain redundant accesses. */
543 9214023 : if (flag_checking)
544 : {
545 : size_t i, i2;
546 : modref_access_node *a, *a2;
547 :
548 20125506 : FOR_EACH_VEC_SAFE_ELT (accesses, i, a)
549 : {
550 25390121 : FOR_EACH_VEC_SAFE_ELT (accesses, i2, a2)
551 14478627 : if (i != i2)
552 9022880 : gcc_assert (!a->contains (*a2));
553 : }
554 : }
555 :
556 11587780 : FOR_EACH_VEC_SAFE_ELT (accesses, i, a2)
557 : {
558 5128127 : if (a2->contains (a))
559 : return 0;
560 3412002 : if (a.contains (*a2))
561 : {
562 51833 : a.adjustments = 0;
563 51833 : a2->parm_index = a.parm_index;
564 51833 : a2->parm_offset_known = a.parm_offset_known;
565 51833 : a2->update (a.parm_offset, a.offset, a.size, a.max_size,
566 : record_adjustments);
567 51833 : modref_access_node::try_merge_with (accesses, i);
568 51833 : return 1;
569 : }
570 3360169 : if (a2->merge (a, record_adjustments))
571 : {
572 986412 : modref_access_node::try_merge_with (accesses, i);
573 986412 : return 1;
574 : }
575 2373757 : 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 6459653 : if (accesses && accesses->length () >= max_accesses)
581 : {
582 1409 : if (max_accesses < 2)
583 : return -1;
584 : /* Find least harmful merge and perform it. */
585 : int best1 = -1, best2 = -1;
586 23869 : FOR_EACH_VEC_SAFE_ELT (accesses, i, a2)
587 : {
588 190826 : for (j = i + 1; j < accesses->length (); j++)
589 168366 : if (best1 < 0
590 335323 : || modref_access_node::closer_pair_p
591 333914 : (*a2, (*accesses)[j],
592 166957 : (*accesses)[best1],
593 165528 : best2 < 0 ? a : (*accesses)[best2]))
594 : {
595 17302 : best1 = i;
596 17302 : best2 = j;
597 : }
598 22460 : if (modref_access_node::closer_pair_p
599 44920 : (*a2, a,
600 22460 : (*accesses)[best1],
601 21753 : best2 < 0 ? a : (*accesses)[best2]))
602 : {
603 1284 : best1 = i;
604 1284 : best2 = -1;
605 : }
606 : }
607 1409 : (*accesses)[best1].forced_merge (best2 < 0 ? a : (*accesses)[best2],
608 : record_adjustments);
609 : /* Check that merging indeed merged ranges. */
610 1409 : gcc_checking_assert ((*accesses)[best1].contains
611 : (best2 < 0 ? a : (*accesses)[best2]));
612 1409 : if (!(*accesses)[best1].useful_p ())
613 : return -1;
614 1388 : 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 1387 : else if (dump_file)
619 1 : fprintf (dump_file,
620 : "--param modref-max-accesses limit reached;"
621 : " merging with %i\n", best1);
622 1388 : modref_access_node::try_merge_with (accesses, best1);
623 1388 : if (best2 >= 0)
624 200 : insert (accesses, a, max_accesses, record_adjustments);
625 1388 : return 1;
626 : }
627 6458244 : a.adjustments = 0;
628 6458244 : vec_safe_push (accesses, a);
629 6458244 : return 1;
630 : }
631 :
632 : /* Return true if range info is useful. */
633 : bool
634 69746926 : modref_access_node::range_info_useful_p () const
635 : {
636 69746926 : return parm_index != MODREF_UNKNOWN_PARM
637 69746926 : && parm_index != MODREF_GLOBAL_MEMORY_PARM
638 61182676 : && parm_offset_known
639 129969413 : && (known_size_p (size)
640 561732 : || known_size_p (max_size)
641 207756 : || 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 14057871 : modref_access_node::get_call_arg (const gcall *stmt) const
681 : {
682 14057871 : if (parm_index == MODREF_UNKNOWN_PARM
683 14057871 : || parm_index == MODREF_GLOBAL_MEMORY_PARM)
684 : return NULL;
685 14056792 : if (parm_index == MODREF_STATIC_CHAIN_PARM)
686 366649 : 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 13690143 : gcc_checking_assert (parm_index >= 0);
690 13690143 : if (parm_index >= (int)gimple_call_num_args (stmt))
691 : return NULL;
692 13690123 : return gimple_call_arg (stmt, parm_index);
693 : }
694 :
695 : /* Return tree corresponding to parameter of the range in STMT. */
696 : bool
697 8068949 : modref_access_node::get_ao_ref (const gcall *stmt, ao_ref *ref) const
698 : {
699 8068949 : tree arg;
700 :
701 8068949 : if (!parm_offset_known
702 6280230 : || !(arg = get_call_arg (stmt))
703 14349169 : || !POINTER_TYPE_P (TREE_TYPE (arg)))
704 1788787 : return false;
705 6280162 : poly_offset_int off = (poly_offset_int)offset
706 6280162 : + ((poly_offset_int)parm_offset << LOG2_BITS_PER_UNIT);
707 6280162 : poly_int64 off2;
708 6280162 : if (!off.to_shwi (&off2))
709 : return false;
710 6280162 : ao_ref_init_from_ptr_and_range (ref, arg, true, off2, size, max_size);
711 6280162 : return true;
712 : }
713 :
714 : /* Return true A is a subkill. */
715 : bool
716 4374094 : modref_access_node::contains_for_kills (const modref_access_node &a) const
717 : {
718 4374094 : poly_int64 aoffset_adj = 0;
719 :
720 4374094 : gcc_checking_assert (parm_index != MODREF_UNKNOWN_PARM
721 : && a.parm_index != MODREF_UNKNOWN_PARM);
722 4374094 : if (parm_index != a.parm_index)
723 : return false;
724 3561484 : gcc_checking_assert (parm_offset_known && a.parm_offset_known);
725 3561484 : aoffset_adj = (a.parm_offset - parm_offset)
726 3561484 : * BITS_PER_UNIT;
727 3561484 : gcc_checking_assert (range_info_useful_p () && a.range_info_useful_p ());
728 3561484 : return known_subrange_p (a.offset + aoffset_adj,
729 3561484 : 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 481541 : 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 481541 : if (known_le (offset1, offset2))
743 : ;
744 51013 : else if (known_le (offset2, offset1))
745 : {
746 51013 : std::swap (offset1, offset2);
747 51013 : std::swap (max_size1, max_size2);
748 : }
749 : else
750 : gcc_unreachable ();
751 :
752 481541 : poly_int64 new_max_size = max_size2 + offset2 - offset1;
753 481541 : if (known_le (new_max_size, max_size1))
754 : new_max_size = max_size1;
755 481541 : if (known_eq (parm_offset, parm_offset1)
756 465380 : && known_eq (offset, offset1)
757 424932 : && known_eq (size, new_max_size)
758 481541 : && known_eq (max_size, new_max_size))
759 : return false;
760 :
761 481541 : if (!record_adjustments
762 481541 : || (++adjustments) < param_modref_max_adjustments)
763 : {
764 481541 : parm_offset = parm_offset1;
765 481541 : offset = offset1;
766 481541 : max_size = new_max_size;
767 481541 : size = new_max_size;
768 481541 : 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 1211942 : modref_access_node::merge_for_kills (const modref_access_node &a,
780 : bool record_adjustments)
781 : {
782 1211942 : poly_int64 offset1 = 0;
783 1211942 : poly_int64 aoffset1 = 0;
784 1211942 : poly_int64 new_parm_offset = 0;
785 :
786 : /* We assume that containment was tested earlier. */
787 1211942 : gcc_checking_assert (!contains_for_kills (a) && !a.contains_for_kills (*this)
788 : && useful_for_kill_p () && a.useful_for_kill_p ());
789 :
790 1211942 : if (parm_index != a.parm_index
791 1211942 : || !combined_offsets (a, &new_parm_offset, &offset1, &aoffset1))
792 253788 : return false;
793 :
794 958154 : if (known_le (offset1, aoffset1))
795 : {
796 762223 : if (!known_size_p (max_size)
797 762223 : || known_ge (offset1 + max_size, aoffset1))
798 430528 : return update_for_kills (new_parm_offset, offset1, max_size,
799 430528 : aoffset1, a.max_size, record_adjustments);
800 : }
801 195931 : else if (known_le (aoffset1, offset1))
802 : {
803 195931 : if (!known_size_p (a.max_size)
804 195931 : || known_ge (aoffset1 + a.max_size, offset1))
805 51013 : return update_for_kills (new_parm_offset, offset1, max_size,
806 51013 : 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 1297929 : modref_access_node::insert_kill (vec<modref_access_node> &kills,
816 : modref_access_node &a, bool record_adjustments)
817 : {
818 1297929 : size_t index;
819 1297929 : modref_access_node *a2;
820 1297929 : bool merge = false;
821 :
822 1297929 : 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 1642372 : FOR_EACH_VEC_ELT (kills, index, a2)
827 : {
828 909671 : if (a2->contains_for_kills (a))
829 : return false;
830 824269 : if (a.contains_for_kills (*a2))
831 : {
832 17441 : a.adjustments = 0;
833 17441 : *a2 = a;
834 17441 : merge = true;
835 17441 : break;
836 : }
837 806828 : 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 1212527 : if (!merge)
845 : {
846 852632 : 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 732543 : a.adjustments = 0;
853 732543 : kills.safe_push (a);
854 732543 : 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 1195078 : for (i = 0; i < kills.length ();)
861 715252 : if (i != index)
862 : {
863 216270 : bool found = false, restart = false;
864 216270 : modref_access_node *a = &kills[i];
865 216270 : modref_access_node *n = &kills[index];
866 :
867 216270 : if (n->contains_for_kills (*a))
868 : found = true;
869 212135 : if (!found && n->merge_for_kills (*a, false))
870 : found = restart = true;
871 197114 : gcc_checking_assert (found || !a->merge_for_kills (*n, false));
872 216270 : if (found)
873 : {
874 23291 : kills.unordered_remove (i);
875 23291 : if (index == kills.length ())
876 : {
877 0 : index = i;
878 0 : i++;
879 : }
880 23291 : if (restart)
881 19156 : i = 0;
882 : }
883 : else
884 192979 : i++;
885 : }
886 : else
887 498982 : 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 48704314 : gt_ggc_mx (modref_tree < int >*const &tt)
1042 : {
1043 48704314 : if (tt->bases)
1044 : {
1045 7549226 : ggc_test_and_set_mark (tt->bases);
1046 7549226 : gt_ggc_mx (tt->bases);
1047 : }
1048 48704314 : }
1049 :
1050 : void
1051 241216 : gt_ggc_mx (modref_tree < tree_node * >*const &tt)
1052 : {
1053 241216 : if (tt->bases)
1054 : {
1055 179168 : ggc_test_and_set_mark (tt->bases);
1056 179168 : gt_ggc_mx (tt->bases);
1057 : }
1058 241216 : }
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 8521538 : void gt_ggc_mx (modref_base_node<int>* &b)
1066 : {
1067 8521538 : ggc_test_and_set_mark (b);
1068 8521538 : if (b->refs)
1069 : {
1070 8520790 : ggc_test_and_set_mark (b->refs);
1071 8520790 : gt_ggc_mx (b->refs);
1072 : }
1073 8521538 : }
1074 :
1075 188149 : void gt_ggc_mx (modref_base_node<tree_node*>* &b)
1076 : {
1077 188149 : ggc_test_and_set_mark (b);
1078 188149 : if (b->refs)
1079 : {
1080 188149 : ggc_test_and_set_mark (b->refs);
1081 188149 : gt_ggc_mx (b->refs);
1082 : }
1083 188149 : if (b->base)
1084 187609 : gt_ggc_mx (b->base);
1085 188149 : }
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 11170716 : void gt_ggc_mx (modref_ref_node<int>* &r)
1093 : {
1094 11170716 : ggc_test_and_set_mark (r);
1095 11170716 : if (r->accesses)
1096 : {
1097 8568383 : ggc_test_and_set_mark (r->accesses);
1098 8568383 : gt_ggc_mx (r->accesses);
1099 : }
1100 11170716 : }
1101 :
1102 188173 : void gt_ggc_mx (modref_ref_node<tree_node*>* &r)
1103 : {
1104 188173 : ggc_test_and_set_mark (r);
1105 188173 : if (r->accesses)
1106 : {
1107 8327 : ggc_test_and_set_mark (r->accesses);
1108 8327 : gt_ggc_mx (r->accesses);
1109 : }
1110 188173 : if (r->ref)
1111 188097 : gt_ggc_mx (r->ref);
1112 188173 : }
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 12207708 : void gt_ggc_mx (modref_access_node &)
1120 : {
1121 12207708 : }
|
