1 /* Data structure for the modref pass.
2 Copyright (C) 2020-2021 Free Software Foundation, Inc.
3 Contributed by David Cepelik and Jan Hubicka
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 /* modref_tree represent a decision tree that can be used by alias analysis
22 oracle to determine whether given memory access can be affected by a function
23 call. For every function we collect two trees, one for loads and other
24 for stores. Tree consist of following levels:
25
26 1) Base: this level represent base alias set of the access and refers
27 to sons (ref nodes). Flag all_refs means that all possible references
28 are aliasing.
29
30 Because for LTO streaming we need to stream types rather than alias sets
31 modref_base_node is implemented as a template.
32 2) Ref: this level represent ref alias set and links to accesses unless
33 all_refs flag is set.
34 Again ref is an template to allow LTO streaming.
35 3) Access: this level represent info about individual accesses. Presently
36 we record whether access is through a dereference of a function parameter
37 */
38
39 #ifndef GCC_MODREF_TREE_H
40 #define GCC_MODREF_TREE_H
41
42 struct ipa_modref_summary;
43
44 /* Memory access. */
45 struct GTY(()) modref_access_node
46 {
47
48 /* Access range information (in bits). */
49 poly_int64 offset;
50 poly_int64 size;
51 poly_int64 max_size;
52
53 /* Offset from parameter pointer to the base of the access (in bytes). */
54 poly_int64 parm_offset;
55
56 /* Index of parameter which specifies the base of access. -1 if base is not
57 a function parameter. */
58 int parm_index;
59 bool parm_offset_known;
60
61 /* Return true if access node holds no useful info. */
62 bool useful_p () const
63 {
64 return parm_index != -1;
65 }
66 /* Return true if range info is useful. */
67 bool range_info_useful_p () const
68 {
69 return parm_index != -1 && parm_offset_known;
70 }
71 /* Return true if both accesses are the same. */
72 bool operator == (modref_access_node &a) const
73 {
74 if (parm_index != a.parm_index)
75 return false;
76 if (parm_index >= 0)
77 {
78 if (parm_offset_known != a.parm_offset_known)
79 return false;
80 if (parm_offset_known
81 && !known_eq (parm_offset, a.parm_offset))
82 return false;
83 }
84 if (range_info_useful_p ()
85 && (!known_eq (a.offset, offset)
86 || !known_eq (a.size, size)
87 || !known_eq (a.max_size, max_size)))
88 return false;
89 return true;
90 }
91 };
92
93 /* Access node specifying no useful info. */
94 const modref_access_node unspecified_modref_access_node
95 = {0, -1, -1, 0, -1, false};
96
97 template <typename T>
98 struct GTY((user)) modref_ref_node
99 {
100 T ref;
101 bool every_access;
102 vec <modref_access_node, va_gc> *accesses;
103
104 modref_ref_node (T ref):
105 ref (ref),
106 every_access (false),
107 accesses (NULL)
108 {}
109
110 /* Search REF; return NULL if failed. */
111 modref_access_node *search (modref_access_node access)
112 {
113 size_t i;
114 modref_access_node *a;
115 FOR_EACH_VEC_SAFE_ELT (accesses, i, a)
116 if (*a == access)
117 return a;
118 return NULL;
119 }
120
121 /* Collapse the tree. */
122 void collapse ()
123 {
124 vec_free (accesses);
125 accesses = NULL;
126 every_access = true;
127 }
128
129 /* Insert access with OFFSET and SIZE.
130 Collapse tree if it has more than MAX_ACCESSES entries.
131 Return true if record was changed. */
132 bool insert_access (modref_access_node a, size_t max_accesses)
133 {
134 /* If this base->ref pair has no access information, bail out. */
altivec_register_p(int regno)135 if (every_access)
136 return false;
137
138 /* Otherwise, insert a node for the ref of the access under the base. */
139 modref_access_node *access_node = search (a);
140 if (access_node)
141 return false;
142
143 /* If this base->ref pair has too many accesses stored, we will clear
144 all accesses and bail out. */
145 if ((accesses && accesses->length () >= max_accesses)
146 || !a.useful_p ())
spe_register_p(int regno)147 {
148 if (dump_file && a.useful_p ())
149 fprintf (dump_file,
150 "--param param=modref-max-accesses limit reached\n");
151 collapse ();
152 return true;
153 }
154 vec_safe_push (accesses, a);
155 return true;
156 }
157 };
158
159 /* Base of an access. */
160 template <typename T>
161 struct GTY((user)) modref_base_node
162 {
163 T base;
164 vec <modref_ref_node <T> *, va_gc> *refs;
165 bool every_ref;
166
167 modref_base_node (T base):
168 base (base),
169 refs (NULL),
170 every_ref (false) {}
171
172 /* Search REF; return NULL if failed. */
173 modref_ref_node <T> *search (T ref)
174 {
ppc_floating_point_unit_p(struct gdbarch * gdbarch)175 size_t i;
176 modref_ref_node <T> *n;
177 FOR_EACH_VEC_SAFE_ELT (refs, i, n)
178 if (n->ref == ref)
179 return n;
180 return NULL;
181 }
182
183 /* Insert REF; collapse tree if there are more than MAX_REFS.
184 Return inserted ref and if CHANGED is non-null set it to true if
185 something changed. */
186 modref_ref_node <T> *insert_ref (T ref, size_t max_refs,
ppc_supply_reg(struct regcache * regcache,int regnum,const char * regs,size_t offset)187 bool *changed = NULL)
188 {
189 modref_ref_node <T> *ref_node;
190
191 /* If the node is collapsed, don't do anything. */
192 if (every_ref)
193 return NULL;
194
195 /* Otherwise, insert a node for the ref of the access under the base. */
196 ref_node = search (ref);
197 if (ref_node)
198 return ref_node;
199
200 if (changed)
201 *changed = true;
202
203 /* Collapse the node if too full already. */
204 if (refs && refs->length () >= max_refs)
205 {
206 if (dump_file)
207 fprintf (dump_file, "--param param=modref-max-refs limit reached\n");
208 collapse ();
209 return NULL;
210 }
211
212 ref_node = new (ggc_alloc <modref_ref_node <T> > ())modref_ref_node <T>
213 (ref);
214 vec_safe_push (refs, ref_node);
215 return ref_node;
216 }
217
218 void collapse ()
219 {
220 size_t i;
221 modref_ref_node <T> *r;
222
223 if (refs)
224 {
225 FOR_EACH_VEC_SAFE_ELT (refs, i, r)
226 {
227 r->collapse ();
228 ggc_free (r);
229 }
230 vec_free (refs);
231 }
232 refs = NULL;
233 every_ref = true;
234 }
235 };
236
237 /* Map translating parameters across function call. */
238
239 struct modref_parm_map
240 {
241 /* Index of parameter we translate to.
242 -1 indicates that parameter is unknown
243 -2 indicates that parameter points to local memory and access can be
244 discarded. */
245 int parm_index;
246 bool parm_offset_known;
247 poly_int64 parm_offset;
248 };
249
ppc_supply_fpregset(const struct regset * regset,struct regcache * regcache,int regnum,const void * fpregs,size_t len)250 /* Access tree for a single function. */
251 template <typename T>
252 struct GTY((user)) modref_tree
253 {
254 vec <modref_base_node <T> *, va_gc> *bases;
255 size_t max_bases;
256 size_t max_refs;
257 size_t max_accesses;
258 bool every_base;
259
260 modref_tree (size_t max_bases, size_t max_refs, size_t max_accesses):
261 bases (NULL),
262 max_bases (max_bases),
263 max_refs (max_refs),
264 max_accesses (max_accesses),
265 every_base (false) {}
266
267 /* Insert BASE; collapse tree if there are more than MAX_REFS.
268 Return inserted base and if CHANGED is non-null set it to true if
269 something changed. */
270
271 modref_base_node <T> *insert_base (T base, bool *changed = NULL)
272 {
273 modref_base_node <T> *base_node;
274
275 /* If the node is collapsed, don't do anything. */
276 if (every_base)
277 return NULL;
278
279 /* Otherwise, insert a node for the base of the access into the tree. */
280 base_node = search (base);
281 if (base_node)
282 return base_node;
283
284 if (changed)
285 *changed = true;
286
287 /* Collapse the node if too full already. */
288 if (bases && bases->length () >= max_bases)
289 {
290 if (dump_file)
291 fprintf (dump_file, "--param param=modref-max-bases limit reached\n");
292 collapse ();
293 return NULL;
294 }
295
296 base_node = new (ggc_alloc <modref_base_node <T> > ())
297 modref_base_node <T> (base);
298 vec_safe_push (bases, base_node);
299 return base_node;
300 }
301
302 /* Insert memory access to the tree.
303 Return true if something changed. */
304 bool insert (T base, T ref, modref_access_node a)
305 {
306 if (every_base)
307 return false;
308
309 bool changed = false;
310
311 /* No useful information tracked; collapse everything. */
312 if (!base && !ref && !a.useful_p ())
313 {
314 collapse ();
315 return true;
316 }
317
318 modref_base_node <T> *base_node = insert_base (base, &changed);
319 if (!base_node || base_node->every_ref)
320 return changed;
321 gcc_checking_assert (search (base) != NULL);
322
323 /* No useful ref info tracked; collapse base. */
324 if (!ref && !a.useful_p ())
325 {
326 base_node->collapse ();
327 return true;
328 }
329
330 modref_ref_node <T> *ref_node = base_node->insert_ref (ref, max_refs,
331 &changed);
332
333 /* If we failed to insert ref, just see if there is a cleanup possible. */
334 if (!ref_node)
335 {
336 /* No useful ref information and no useful base; collapse everything. */
337 if (!base && base_node->every_ref)
338 {
339 collapse ();
340 gcc_checking_assert (changed);
341 }
342 else if (changed)
343 cleanup ();
344 }
345 else
346 {
347 if (ref_node->every_access)
348 return changed;
349 changed |= ref_node->insert_access (a, max_accesses);
350 /* See if we failed to add useful access. */
351 if (ref_node->every_access)
352 {
353 /* Collapse everything if there is no useful base and ref. */
354 if (!base && !ref)
355 {
356 collapse ();
357 gcc_checking_assert (changed);
358 }
359 /* Collapse base if there is no useful ref. */
360 else if (!ref)
361 {
362 base_node->collapse ();
363 gcc_checking_assert (changed);
364 }
365 }
366 }
367 return changed;
368 }
369
370 /* Remove tree branches that are not useful (i.e. they will always pass). */
371
372 void cleanup ()
373 {
374 size_t i, j;
375 modref_base_node <T> *base_node;
376 modref_ref_node <T> *ref_node;
377
378 if (!bases)
379 return;
380
381 for (i = 0; vec_safe_iterate (bases, i, &base_node);)
382 {
383 if (base_node->refs)
384 for (j = 0; vec_safe_iterate (base_node->refs, j, &ref_node);)
385 {
386 if (!ref_node->every_access
387 && (!ref_node->accesses
388 || !ref_node->accesses->length ()))
389 {
390 base_node->refs->unordered_remove (j);
391 vec_free (ref_node->accesses);
392 ggc_delete (ref_node);
393 }
394 else
395 j++;
396 }
397 if (!base_node->every_ref
398 && (!base_node->refs || !base_node->refs->length ()))
399 {
400 bases->unordered_remove (i);
401 vec_free (base_node->refs);
402 ggc_delete (base_node);
403 }
404 else
405 i++;
406 }
407 if (bases && !bases->length ())
408 {
409 vec_free (bases);
410 bases = NULL;
411 }
412 }
413
414 /* Merge OTHER into the tree.
415 PARM_MAP, if non-NULL, maps parm indexes of callee to caller. -2 is used
416 to signalize that parameter is local and does not need to be tracked.
417 Return true if something has changed. */
418 bool merge (modref_tree <T> *other, vec <modref_parm_map> *parm_map)
419 {
420 if (!other || every_base)
421 return false;
422 if (other->every_base)
423 {
424 collapse ();
425 return true;
426 }
427
428 bool changed = false;
429 size_t i, j, k;
430 modref_base_node <T> *base_node, *my_base_node;
431 modref_ref_node <T> *ref_node;
432 modref_access_node *access_node;
433 bool release = false;
434
435 /* For self-recursive functions we may end up merging summary into itself;
436 produce copy first so we do not modify summary under our own hands. */
437 if (other == this)
438 {
439 release = true;
440 other = modref_tree<T>::create_ggc (max_bases, max_refs, max_accesses);
441 other->copy_from (this);
442 }
443
444 FOR_EACH_VEC_SAFE_ELT (other->bases, i, base_node)
445 {
446 if (base_node->every_ref)
447 {
448 my_base_node = insert_base (base_node->base, &changed);
449 if (my_base_node && !my_base_node->every_ref)
450 {
451 my_base_node->collapse ();
452 cleanup ();
453 changed = true;
454 }
455 }
456 else
457 FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
458 {
459 if (ref_node->every_access)
460 {
461 changed |= insert (base_node->base,
462 ref_node->ref,
463 unspecified_modref_access_node);
464 }
465 else
466 FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
467 {
468 modref_access_node a = *access_node;
469
470 if (a.parm_index != -1 && parm_map)
471 {
472 if (a.parm_index >= (int)parm_map->length ())
473 a.parm_index = -1;
474 else if ((*parm_map) [a.parm_index].parm_index == -2)
475 continue;
476 else
477 {
478 a.parm_offset
479 += (*parm_map) [a.parm_index].parm_offset;
480 a.parm_offset_known
481 &= (*parm_map)
482 [a.parm_index].parm_offset_known;
483 a.parm_index
484 = (*parm_map) [a.parm_index].parm_index;
485 }
486 }
487 changed |= insert (base_node->base, ref_node->ref, a);
488 }
489 }
490 }
491 if (release)
492 ggc_delete (other);
493 return changed;
494 }
495
496 /* Copy OTHER to THIS. */
497 void copy_from (modref_tree <T> *other)
498 {
499 merge (other, NULL);
500 }
501
502 /* Search BASE in tree; return NULL if failed. */
503 modref_base_node <T> *search (T base)
504 {
505 size_t i;
506 modref_base_node <T> *n;
507 FOR_EACH_VEC_SAFE_ELT (bases, i, n)
508 if (n->base == base)
509 return n;
510 return NULL;
511 }
512
513 /* Return ggc allocated instance. We explicitly call destructors via
514 ggc_delete and do not want finalizers to be registered and
515 called at the garbage collection time. */
516 static modref_tree<T> *create_ggc (size_t max_bases, size_t max_refs,
517 size_t max_accesses)
518 {
519 return new (ggc_alloc_no_dtor<modref_tree<T>> ())
520 modref_tree<T> (max_bases, max_refs, max_accesses);
521 }
522
523 /* Remove all records and mark tree to alias with everything. */
524 void collapse ()
525 {
526 size_t i;
527 modref_base_node <T> *n;
528
529 if (bases)
530 {
531 FOR_EACH_VEC_SAFE_ELT (bases, i, n)
532 {
533 n->collapse ();
534 ggc_free (n);
535 }
536 vec_free (bases);
537 }
538 bases = NULL;
539 every_base = true;
540 }
541
542 /* Release memory. */
543 ~modref_tree ()
544 {
545 collapse ();
546 }
547
548 /* Update parameter indexes in TT according to MAP. */
549 void
550 remap_params (vec <int> *map)
551 {
552 size_t i;
553 modref_base_node <T> *base_node;
554 FOR_EACH_VEC_SAFE_ELT (bases, i, base_node)
555 {
556 size_t j;
557 modref_ref_node <T> *ref_node;
558 FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
559 {
560 size_t k;
561 modref_access_node *access_node;
562 FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
563 if (access_node->parm_index > 0)
564 {
565 if (access_node->parm_index < (int)map->length ())
566 access_node->parm_index = (*map)[access_node->parm_index];
567 else
568 access_node->parm_index = -1;
569 }
570 }
571 }
572 }
573 };
574
575 void modref_c_tests ();
576
577 void gt_ggc_mx (modref_tree <int>* const&);
578 void gt_ggc_mx (modref_tree <tree_node*>* const&);
579 void gt_pch_nx (modref_tree <int>* const&);
580 void gt_pch_nx (modref_tree <tree_node*>* const&);
581 void gt_pch_nx (modref_tree <int>* const&, gt_pointer_operator op, void *cookie);
582 void gt_pch_nx (modref_tree <tree_node*>* const&, gt_pointer_operator op,
refine_prologue_limit(CORE_ADDR pc,CORE_ADDR lim_pc)583 void *cookie);
584
585 void gt_ggc_mx (modref_base_node <int>*);
586 void gt_ggc_mx (modref_base_node <tree_node*>* &);
587 void gt_pch_nx (modref_base_node <int>* const&);
588 void gt_pch_nx (modref_base_node <tree_node*>* const&);
589 void gt_pch_nx (modref_base_node <int>* const&, gt_pointer_operator op,
590 void *cookie);
591 void gt_pch_nx (modref_base_node <tree_node*>* const&, gt_pointer_operator op,
592 void *cookie);
593
594 void gt_ggc_mx (modref_ref_node <int>*);
595 void gt_ggc_mx (modref_ref_node <tree_node*>* &);
596 void gt_pch_nx (modref_ref_node <int>* const&);
597 void gt_pch_nx (modref_ref_node <tree_node*>* const&);
598 void gt_pch_nx (modref_ref_node <int>* const&, gt_pointer_operator op,
599 void *cookie);
600 void gt_pch_nx (modref_ref_node <tree_node*>* const&, gt_pointer_operator op,
601 void *cookie);
602
603 #endif
604