1 /* Callgraph based analysis of static variables.
2 Copyright (C) 2004-2021 Free Software Foundation, Inc.
3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
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 /* This file gathers information about how variables whose scope is
22 confined to the compilation unit are used.
23
24 The transitive call site specific clobber effects are computed
25 for the variables whose scope is contained within this compilation
26 unit.
27
28 First each function and static variable initialization is analyzed
29 to determine which local static variables are either read, written,
30 or have their address taken. Any local static that has its address
31 taken is removed from consideration. Once the local read and
32 writes are determined, a transitive closure of this information is
33 performed over the call graph to determine the worst case set of
34 side effects of each call. In later parts of the compiler, these
35 local and global sets are examined to make the call clobbering less
36 traumatic, promote some statics to registers, and improve aliasing
37 information. */
38
39 #include "config.h"
40 #include "system.h"
41 #include "coretypes.h"
42 #include "backend.h"
43 #include "tree.h"
44 #include "gimple.h"
45 #include "tree-pass.h"
46 #include "cgraph.h"
47 #include "data-streamer.h"
48 #include "calls.h"
49 #include "ipa-utils.h"
50 #include "ipa-reference.h"
51 #include "alloc-pool.h"
52 #include "symbol-summary.h"
53
54 /* The static variables defined within the compilation unit that are
55 loaded or stored directly by function that owns this structure. */
56
57 struct ipa_reference_local_vars_info_d
58 {
59 bitmap statics_read;
60 bitmap statics_written;
61 };
62
63 /* Statics that are read and written by some set of functions. The
64 local ones are based on the loads and stores local to the function.
65 The global ones are based on the local info as well as the
66 transitive closure of the functions that are called. */
67
68 struct ipa_reference_global_vars_info_d
69 {
70 bitmap statics_read;
71 bitmap statics_written;
72 };
73
74 /* Information we save about every function after ipa-reference is completed. */
75
76 struct ipa_reference_optimization_summary_d
77 {
78 bitmap statics_read;
79 bitmap statics_written;
80 };
81
82 typedef ipa_reference_local_vars_info_d *ipa_reference_local_vars_info_t;
83 typedef ipa_reference_global_vars_info_d *ipa_reference_global_vars_info_t;
84 typedef ipa_reference_optimization_summary_d *
85 ipa_reference_optimization_summary_t;
86
87 struct ipa_reference_vars_info_d
88 {
89 struct ipa_reference_local_vars_info_d local;
90 struct ipa_reference_global_vars_info_d global;
91 };
92
93 typedef struct ipa_reference_vars_info_d *ipa_reference_vars_info_t;
94
95 /* This map contains all of the static variables that are
96 being considered by the compilation level alias analysis. */
97 typedef hash_map<tree, int> reference_vars_map_t;
98 static reference_vars_map_t *ipa_reference_vars_map;
99 static int ipa_reference_vars_uids;
100 static vec<tree> *reference_vars_to_consider;
101 varpool_node_hook_list *varpool_node_hooks;
102
103 /* Set of all interesting module statics. A bit is set for every module
104 static we are considering. This is added to the local info when asm
105 code is found that clobbers all memory. */
106 static bitmap all_module_statics;
107 /* Zero bitmap. */
108 static bitmap no_module_statics;
109 /* Set of all statics that should be ignored because they are touched by
110 -fno-ipa-reference code. */
111 static bitmap ignore_module_statics;
112
113 /* Obstack holding bitmaps of local analysis (live from analysis to
114 propagation) */
115 static bitmap_obstack local_info_obstack;
116 /* Obstack holding global analysis live forever. */
117 static bitmap_obstack optimization_summary_obstack;
118
119 class ipa_ref_var_info_summary_t: public fast_function_summary
120 <ipa_reference_vars_info_d *, va_heap>
121 {
122 public:
ipa_ref_var_info_summary_t(symbol_table * symtab)123 ipa_ref_var_info_summary_t (symbol_table *symtab):
124 fast_function_summary <ipa_reference_vars_info_d *, va_heap> (symtab) {}
125 };
126
127 static ipa_ref_var_info_summary_t *ipa_ref_var_info_summaries = NULL;
128
129 class ipa_ref_opt_summary_t: public fast_function_summary
130 <ipa_reference_optimization_summary_d *, va_heap>
131 {
132 public:
ipa_ref_opt_summary_t(symbol_table * symtab)133 ipa_ref_opt_summary_t (symbol_table *symtab):
134 fast_function_summary <ipa_reference_optimization_summary_d *, va_heap> (symtab) {}
135
136 virtual void remove (cgraph_node *src_node,
137 ipa_reference_optimization_summary_d *data);
138 virtual void duplicate (cgraph_node *src_node, cgraph_node *dst_node,
139 ipa_reference_optimization_summary_d *src_data,
140 ipa_reference_optimization_summary_d *dst_data);
141 };
142
143 static ipa_ref_opt_summary_t *ipa_ref_opt_sum_summaries = NULL;
144
145 /* Return ID used by ipa-reference bitmaps. -1 if failed. */
146 int
ipa_reference_var_uid(tree t)147 ipa_reference_var_uid (tree t)
148 {
149 if (!ipa_reference_vars_map)
150 return -1;
151 int *id = ipa_reference_vars_map->get
152 (symtab_node::get (t)->ultimate_alias_target (NULL)->decl);
153 if (!id)
154 return -1;
155 return *id;
156 }
157
158 /* Return ID used by ipa-reference bitmaps. Create new entry if
159 T is not in map. Set EXISTED accordinly */
160 int
ipa_reference_var_get_or_insert_uid(tree t,bool * existed)161 ipa_reference_var_get_or_insert_uid (tree t, bool *existed)
162 {
163 int &id = ipa_reference_vars_map->get_or_insert
164 (symtab_node::get (t)->ultimate_alias_target (NULL)->decl, existed);
165 if (!*existed)
166 id = ipa_reference_vars_uids++;
167 return id;
168 }
169
170 /* Return the ipa_reference_vars structure starting from the cgraph NODE. */
171 static inline ipa_reference_vars_info_t
get_reference_vars_info(struct cgraph_node * node)172 get_reference_vars_info (struct cgraph_node *node)
173 {
174 if (ipa_ref_var_info_summaries == NULL)
175 return NULL;
176
177 ipa_reference_vars_info_t v = ipa_ref_var_info_summaries->get (node);
178 return v == NULL ? NULL : v;
179 }
180
181 /* Return the ipa_reference_vars structure starting from the cgraph NODE. */
182 static inline ipa_reference_optimization_summary_t
get_reference_optimization_summary(struct cgraph_node * node)183 get_reference_optimization_summary (struct cgraph_node *node)
184 {
185 if (ipa_ref_opt_sum_summaries == NULL)
186 return NULL;
187
188 ipa_reference_optimization_summary_t v
189 = ipa_ref_opt_sum_summaries->get (node);
190
191 return v == NULL ? NULL : v;
192 }
193
194 /* Return a bitmap indexed by ipa_reference_var_uid for the static variables
195 that are *not* read during the execution of the function FN. Returns
196 NULL if no data is available. */
197
198 bitmap
ipa_reference_get_read_global(struct cgraph_node * fn)199 ipa_reference_get_read_global (struct cgraph_node *fn)
200 {
201 if (!opt_for_fn (current_function_decl, flag_ipa_reference))
202 return NULL;
203
204 enum availability avail;
205 struct cgraph_node *fn2 = fn->function_symbol (&avail);
206 ipa_reference_optimization_summary_t info =
207 get_reference_optimization_summary (fn2);
208
209 if (info
210 && (avail >= AVAIL_AVAILABLE
211 || (avail == AVAIL_INTERPOSABLE
212 && flags_from_decl_or_type (fn->decl) & ECF_LEAF))
213 && opt_for_fn (fn2->decl, flag_ipa_reference))
214 return info->statics_read;
215 else if (avail == AVAIL_NOT_AVAILABLE
216 && flags_from_decl_or_type (fn->decl) & ECF_LEAF)
217 return no_module_statics;
218 else
219 return NULL;
220 }
221
222 /* Return a bitmap indexed by ipa_reference_var_uid for the static variables
223 that are *not* written during the execution of the function FN. Note
224 that variables written may or may not be read during the function
225 call. Returns NULL if no data is available. */
226
227 bitmap
ipa_reference_get_written_global(struct cgraph_node * fn)228 ipa_reference_get_written_global (struct cgraph_node *fn)
229 {
230 if (!opt_for_fn (current_function_decl, flag_ipa_reference))
231 return NULL;
232
233 enum availability avail;
234 struct cgraph_node *fn2 = fn->function_symbol (&avail);
235 ipa_reference_optimization_summary_t info =
236 get_reference_optimization_summary (fn2);
237
238 if (info
239 && (avail >= AVAIL_AVAILABLE
240 || (avail == AVAIL_INTERPOSABLE
241 && flags_from_decl_or_type (fn->decl) & ECF_LEAF))
242 && opt_for_fn (fn2->decl, flag_ipa_reference))
243 return info->statics_written;
244 else if (avail == AVAIL_NOT_AVAILABLE
245 && flags_from_decl_or_type (fn->decl) & ECF_LEAF)
246 return no_module_statics;
247 else
248 return NULL;
249 }
250
251
252 /* Hepler for is_proper_for_analysis. */
253 static bool
is_improper(symtab_node * n,void * v ATTRIBUTE_UNUSED)254 is_improper (symtab_node *n, void *v ATTRIBUTE_UNUSED)
255 {
256 tree t = n->decl;
257 /* If the variable has the "used" attribute, treat it as if it had a
258 been touched by the devil. */
259 if (DECL_PRESERVE_P (t))
260 return true;
261
262 /* Do not want to do anything with volatile except mark any
263 function that uses one to be not const or pure. */
264 if (TREE_THIS_VOLATILE (t))
265 return true;
266
267 /* We do not need to analyze readonly vars, we already know they do not
268 alias. */
269 if (TREE_READONLY (t))
270 return true;
271
272 /* We cannot track variables with address taken. */
273 if (TREE_ADDRESSABLE (t))
274 return true;
275
276 /* TODO: We could track public variables that are not addressable, but
277 currently frontends don't give us those. */
278 if (TREE_PUBLIC (t))
279 return true;
280
281 return false;
282 }
283
284 /* Return true if the variable T is the right kind of static variable to
285 perform compilation unit scope escape analysis. */
286
287 static inline bool
is_proper_for_analysis(tree t)288 is_proper_for_analysis (tree t)
289 {
290 int id = ipa_reference_var_uid (t);
291
292 if (id != -1 && bitmap_bit_p (ignore_module_statics, id))
293 return false;
294
295 if (symtab_node::get (t)
296 ->call_for_symbol_and_aliases (is_improper, NULL, true))
297 return false;
298
299 return true;
300 }
301
302 /* Lookup the tree node for the static variable that has UID and
303 convert the name to a string for debugging. */
304
305 static const char *
get_static_name(int index)306 get_static_name (int index)
307 {
308 return fndecl_name ((*reference_vars_to_consider)[index]);
309 }
310
311 /* Dump a set of static vars to FILE. */
312 static void
dump_static_vars_set_to_file(FILE * f,bitmap set)313 dump_static_vars_set_to_file (FILE *f, bitmap set)
314 {
315 unsigned int index;
316 bitmap_iterator bi;
317 if (set == NULL)
318 return;
319 else if (set == all_module_statics)
320 fprintf (f, "ALL");
321 else if (set == no_module_statics)
322 fprintf (f, "NO");
323 else
324 EXECUTE_IF_SET_IN_BITMAP (set, 0, index, bi)
325 {
326 fprintf (f, "%s ", get_static_name (index));
327 }
328 }
329
330 /* Compute X |= Y, taking into account the possibility that
331 either X or Y is already the maximum set.
332 Return true if X is the maximum set after taking the union with Y. */
333
334 static bool
union_static_var_sets(bitmap & x,bitmap y)335 union_static_var_sets (bitmap &x, bitmap y)
336 {
337 if (x != all_module_statics)
338 {
339 if (y == all_module_statics)
340 {
341 BITMAP_FREE (x);
342 x = all_module_statics;
343 }
344 else if (bitmap_ior_into (x, y))
345 {
346 /* The union may have reduced X to the maximum set.
347 In that case, we want to make that visible explicitly.
348 Even though bitmap_equal_p can be very expensive, it
349 turns out to be an overall win to check this here for
350 an LTO bootstrap of GCC itself. Liberally extrapoliate
351 that result to be applicable to all cases. */
352 if (bitmap_equal_p (x, all_module_statics))
353 {
354 BITMAP_FREE (x);
355 x = all_module_statics;
356 }
357 }
358 }
359 return x == all_module_statics;
360 }
361
362 /* Return a copy of SET on the bitmap obstack containing SET.
363 But if SET is NULL or the maximum set, return that instead. */
364
365 static bitmap
copy_static_var_set(bitmap set,bool for_propagation)366 copy_static_var_set (bitmap set, bool for_propagation)
367 {
368 if (set == NULL || set == all_module_statics)
369 return set;
370 if (!for_propagation && set == no_module_statics)
371 return set;
372 bitmap_obstack *o = set->obstack;
373 gcc_checking_assert (o);
374 bitmap copy = BITMAP_ALLOC (o);
375 bitmap_copy (copy, set);
376 return copy;
377 }
378
379 /* Compute the union all of the statics read and written by every callee of X
380 into X_GLOBAL->statics_read and X_GLOBAL->statics_written. X_GLOBAL is
381 actually the set representing the cycle containing X. If the read and
382 written sets of X_GLOBAL has been reduced to the maximum set, we don't
383 have to look at the remaining callees. */
384
385 static void
propagate_bits(ipa_reference_global_vars_info_t x_global,struct cgraph_node * x)386 propagate_bits (ipa_reference_global_vars_info_t x_global, struct cgraph_node *x)
387 {
388 struct cgraph_edge *e;
389 bool read_all = x_global->statics_read == all_module_statics;
390 bool write_all = x_global->statics_written == all_module_statics;
391 for (e = x->callees;
392 e && !(read_all && write_all);
393 e = e->next_callee)
394 {
395 enum availability avail;
396 struct cgraph_node *y = e->callee->function_symbol (&avail);
397 if (!y)
398 continue;
399
400 /* Only look into nodes we can propagate something. */
401 int flags = flags_from_decl_or_type (y->decl);
402 if (opt_for_fn (y->decl, flag_ipa_reference)
403 && (avail > AVAIL_INTERPOSABLE
404 || (avail == AVAIL_INTERPOSABLE && (flags & ECF_LEAF))))
405 {
406 if (get_reference_vars_info (y))
407 {
408 ipa_reference_vars_info_t y_info = get_reference_vars_info (y);
409 ipa_reference_global_vars_info_t y_global = &y_info->global;
410
411 /* Calls in the current cycle do not have their global set
412 computed yet (but everything else does because we're
413 visiting nodes in topological order). */
414 if (!y_global->statics_read)
415 continue;
416
417 /* If the function is const, it reads no memory even if it
418 seems so to local analysis. */
419 if (flags & ECF_CONST)
420 continue;
421
422 union_static_var_sets (x_global->statics_read,
423 y_global->statics_read);
424
425 /* If the function is pure, it has no stores even if it
426 seems so to local analysis. If we cannot return from
427 the function, we can safely ignore the call. */
428 if ((flags & ECF_PURE)
429 || e->cannot_lead_to_return_p ())
430 continue;
431
432 union_static_var_sets (x_global->statics_written,
433 y_global->statics_written);
434 }
435 else
436 gcc_unreachable ();
437 }
438 }
439 }
440
441 /* Delete NODE from map. */
442
443 static void
varpool_removal_hook(varpool_node * node,void *)444 varpool_removal_hook (varpool_node *node, void *)
445 {
446 ipa_reference_vars_map->remove (node->decl);
447 }
448
449 static bool ipa_init_p = false;
450
451 /* The init routine for analyzing global static variable usage. See
452 comments at top for description. */
453 static void
ipa_init(void)454 ipa_init (void)
455 {
456 if (ipa_init_p)
457 return;
458
459 ipa_init_p = true;
460
461 if (dump_file)
462 vec_alloc (reference_vars_to_consider, 10);
463
464 if (ipa_ref_opt_sum_summaries != NULL)
465 {
466 delete ipa_ref_opt_sum_summaries;
467 ipa_ref_opt_sum_summaries = NULL;
468 delete ipa_reference_vars_map;
469 }
470 ipa_reference_vars_map = new reference_vars_map_t(257);
471 varpool_node_hooks
472 = symtab->add_varpool_removal_hook (varpool_removal_hook, NULL);
473 ipa_reference_vars_uids = 0;
474
475 bitmap_obstack_initialize (&local_info_obstack);
476 bitmap_obstack_initialize (&optimization_summary_obstack);
477 all_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
478 no_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
479 ignore_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
480
481 if (ipa_ref_var_info_summaries == NULL)
482 ipa_ref_var_info_summaries = new ipa_ref_var_info_summary_t (symtab);
483 }
484
485
486 /* Set up the persistent info for FN. */
487
488 static ipa_reference_local_vars_info_t
init_function_info(struct cgraph_node * fn)489 init_function_info (struct cgraph_node *fn)
490 {
491 ipa_reference_vars_info_t info
492 = ipa_ref_var_info_summaries->get_create (fn);
493
494 info->local.statics_read = BITMAP_ALLOC (&local_info_obstack);
495 info->local.statics_written = BITMAP_ALLOC (&local_info_obstack);
496 info->global.statics_read = NULL;
497
498 return &info->local;
499 }
500
501
502 /* This is the main routine for finding the reference patterns for
503 global variables within a function FN. */
504
505 static void
analyze_function(struct cgraph_node * fn)506 analyze_function (struct cgraph_node *fn)
507 {
508 ipa_reference_local_vars_info_t local;
509 struct ipa_ref *ref = NULL;
510 int i;
511 tree var;
512
513 if (!opt_for_fn (fn->decl, flag_ipa_reference))
514 return;
515 local = init_function_info (fn);
516 for (i = 0; fn->iterate_reference (i, ref); i++)
517 {
518 int id;
519 bool existed;
520 if (!is_a <varpool_node *> (ref->referred))
521 continue;
522 var = ref->referred->decl;
523 if (!is_proper_for_analysis (var))
524 continue;
525 /* This is a variable we care about. Check if we have seen it
526 before, and if not add it the set of variables we care about. */
527 id = ipa_reference_var_get_or_insert_uid (var, &existed);
528 if (!existed)
529 {
530 bitmap_set_bit (all_module_statics, id);
531 if (dump_file)
532 reference_vars_to_consider->safe_push (var);
533 }
534 switch (ref->use)
535 {
536 case IPA_REF_LOAD:
537 bitmap_set_bit (local->statics_read, id);
538 break;
539 case IPA_REF_STORE:
540 if (ref->cannot_lead_to_return ())
541 break;
542 bitmap_set_bit (local->statics_written, id);
543 break;
544 case IPA_REF_ADDR:
545 break;
546 default:
547 gcc_unreachable ();
548 }
549 }
550
551 if (fn->cannot_return_p ())
552 bitmap_clear (local->statics_written);
553 }
554
555
556 /* Called when new clone is inserted to callgraph late. */
557
558 void
duplicate(cgraph_node *,cgraph_node *,ipa_reference_optimization_summary_d * ginfo,ipa_reference_optimization_summary_d * dst_ginfo)559 ipa_ref_opt_summary_t::duplicate (cgraph_node *, cgraph_node *,
560 ipa_reference_optimization_summary_d *ginfo,
561 ipa_reference_optimization_summary_d
562 *dst_ginfo)
563 {
564 dst_ginfo->statics_read =
565 copy_static_var_set (ginfo->statics_read, false);
566 dst_ginfo->statics_written =
567 copy_static_var_set (ginfo->statics_written, false);
568 }
569
570 /* Called when node is removed. */
571
572 void
remove(cgraph_node *,ipa_reference_optimization_summary_d * ginfo)573 ipa_ref_opt_summary_t::remove (cgraph_node *,
574 ipa_reference_optimization_summary_d *ginfo)
575 {
576 if (ginfo->statics_read
577 && ginfo->statics_read != all_module_statics
578 && ginfo->statics_read != no_module_statics)
579 BITMAP_FREE (ginfo->statics_read);
580
581 if (ginfo->statics_written
582 && ginfo->statics_written != all_module_statics
583 && ginfo->statics_written != no_module_statics)
584 BITMAP_FREE (ginfo->statics_written);
585 }
586
587 /* Analyze each function in the cgraph to see which global or statics
588 are read or written. */
589
590 static void
generate_summary(void)591 generate_summary (void)
592 {
593 struct cgraph_node *node;
594 unsigned int index;
595 bitmap_iterator bi;
596
597 ipa_init ();
598
599 /* Process all of the functions next. */
600 FOR_EACH_DEFINED_FUNCTION (node)
601 if (!node->alias && !opt_for_fn (node->decl, flag_ipa_reference))
602 {
603 struct ipa_ref *ref = NULL;
604 int i;
605 tree var;
606 for (i = 0; node->iterate_reference (i, ref); i++)
607 {
608 if (!is_a <varpool_node *> (ref->referred))
609 continue;
610 var = ref->referred->decl;
611 if (!is_proper_for_analysis (var))
612 continue;
613 bitmap_set_bit (ignore_module_statics, ipa_reference_var_uid (var));
614 }
615 }
616 FOR_EACH_DEFINED_FUNCTION (node)
617 analyze_function (node);
618
619 if (dump_file)
620 EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
621 {
622 fprintf (dump_file, "\nPromotable global:%s (uid=%u)\n",
623 get_static_name (index), index);
624 }
625
626 if (dump_file)
627 FOR_EACH_DEFINED_FUNCTION (node)
628 if (node->get_availability () >= AVAIL_INTERPOSABLE
629 && opt_for_fn (node->decl, flag_ipa_reference))
630 {
631 ipa_reference_local_vars_info_t l;
632 unsigned int index;
633 bitmap_iterator bi;
634
635 l = &get_reference_vars_info (node)->local;
636 fprintf (dump_file,
637 "\nFunction name:%s:", node->dump_name ());
638 fprintf (dump_file, "\n locals read: ");
639 if (l->statics_read)
640 EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
641 0, index, bi)
642 {
643 fprintf (dump_file, "%s ",
644 get_static_name (index));
645 }
646 fprintf (dump_file, "\n locals written: ");
647 if (l->statics_written)
648 EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
649 0, index, bi)
650 {
651 fprintf (dump_file, "%s ", get_static_name (index));
652 }
653 }
654 }
655
656 /* Set READ_ALL/WRITE_ALL based on decl flags of NODE. */
657
658 static void
read_write_all_from_decl(struct cgraph_node * node,bool & read_all,bool & write_all)659 read_write_all_from_decl (struct cgraph_node *node,
660 bool &read_all, bool &write_all)
661 {
662 tree decl = node->decl;
663 int flags = flags_from_decl_or_type (decl);
664 if ((flags & ECF_LEAF)
665 && node->get_availability () < AVAIL_INTERPOSABLE)
666 ;
667 else if (flags & ECF_CONST)
668 ;
669 else if ((flags & ECF_PURE) || node->cannot_return_p ())
670 {
671 read_all = true;
672 if (dump_file && (dump_flags & TDF_DETAILS))
673 fprintf (dump_file, " %s -> read all\n", node->dump_name ());
674 }
675 else
676 {
677 /* TODO: To be able to produce sane results, we should also handle
678 common builtins, in particular throw. */
679 read_all = true;
680 write_all = true;
681 if (dump_file && (dump_flags & TDF_DETAILS))
682 fprintf (dump_file, " %s -> read all, write all\n",
683 node->dump_name ());
684 }
685 }
686
687 /* Set READ_ALL/WRITE_ALL based on decl flags of NODE or any member
688 in the cycle of NODE. */
689
690 static void
get_read_write_all_from_node(struct cgraph_node * node,bool & read_all,bool & write_all)691 get_read_write_all_from_node (struct cgraph_node *node,
692 bool &read_all, bool &write_all)
693 {
694 struct cgraph_edge *e, *ie;
695
696 /* When function is overwritable, we cannot assume anything. */
697 if (node->get_availability () <= AVAIL_INTERPOSABLE
698 || (node->analyzed && !opt_for_fn (node->decl, flag_ipa_reference)))
699 read_write_all_from_decl (node, read_all, write_all);
700
701 for (e = node->callees;
702 e && !(read_all && write_all);
703 e = e->next_callee)
704 {
705 enum availability avail;
706 struct cgraph_node *callee = e->callee->function_symbol (&avail);
707 gcc_checking_assert (callee);
708 if (avail <= AVAIL_INTERPOSABLE
709 || (callee->analyzed && !opt_for_fn (callee->decl,
710 flag_ipa_reference)))
711 read_write_all_from_decl (callee, read_all, write_all);
712 }
713
714 for (ie = node->indirect_calls;
715 ie && !(read_all && write_all);
716 ie = ie->next_callee)
717 if (!(ie->indirect_info->ecf_flags & ECF_CONST))
718 {
719 read_all = true;
720 if (dump_file && (dump_flags & TDF_DETAILS))
721 fprintf (dump_file, " indirect call -> read all\n");
722 if (!ie->cannot_lead_to_return_p ()
723 && !(ie->indirect_info->ecf_flags & ECF_PURE))
724 {
725 if (dump_file && (dump_flags & TDF_DETAILS))
726 fprintf (dump_file, " indirect call -> write all\n");
727 write_all = true;
728 }
729 }
730 }
731
732 /* Skip edges from and to nodes without ipa_reference enabled.
733 Ignore not available symbols. This leave
734 them out of strongly connected components and makes them easy to skip in the
735 propagation loop bellow. */
736
737 static bool
ignore_edge_p(cgraph_edge * e)738 ignore_edge_p (cgraph_edge *e)
739 {
740 enum availability avail;
741 cgraph_node *ultimate_target
742 = e->callee->function_or_virtual_thunk_symbol (&avail, e->caller);
743
744 return (avail < AVAIL_INTERPOSABLE
745 || (avail == AVAIL_INTERPOSABLE
746 && !(flags_from_decl_or_type (e->callee->decl) & ECF_LEAF))
747 || !opt_for_fn (e->caller->decl, flag_ipa_reference)
748 || !opt_for_fn (ultimate_target->decl, flag_ipa_reference));
749 }
750
751 /* Produce the global information by preforming a transitive closure
752 on the local information that was produced by ipa_analyze_function. */
753
754 static unsigned int
propagate(void)755 propagate (void)
756 {
757 struct cgraph_node *node;
758 struct cgraph_node **order =
759 XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
760 int order_pos;
761 int i;
762 bool remove_p;
763
764 if (dump_file)
765 cgraph_node::dump_cgraph (dump_file);
766
767 remove_p = ipa_discover_variable_flags ();
768 generate_summary ();
769
770 /* Propagate the local information through the call graph to produce
771 the global information. All the nodes within a cycle will have
772 the same info so we collapse cycles first. Then we can do the
773 propagation in one pass from the leaves to the roots. */
774 order_pos = ipa_reduced_postorder (order, true, ignore_edge_p);
775 if (dump_file)
776 ipa_print_order (dump_file, "reduced", order, order_pos);
777
778 for (i = 0; i < order_pos; i++ )
779 {
780 unsigned x;
781 struct cgraph_node *w;
782 ipa_reference_vars_info_t node_info;
783 ipa_reference_global_vars_info_t node_g;
784 ipa_reference_local_vars_info_t node_l;
785 bool read_all = false;
786 bool write_all = false;
787
788 node = order[i];
789 if (node->alias || !opt_for_fn (node->decl, flag_ipa_reference))
790 continue;
791
792 node_info = get_reference_vars_info (node);
793 gcc_assert (node_info);
794 node_l = &node_info->local;
795 node_g = &node_info->global;
796
797 if (dump_file && (dump_flags & TDF_DETAILS))
798 fprintf (dump_file, "Starting cycle with %s\n", node->dump_name ());
799
800 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
801
802 /* If any node in a cycle is read_all or write_all, they all are. */
803 FOR_EACH_VEC_ELT (cycle_nodes, x, w)
804 {
805 if (dump_file && (dump_flags & TDF_DETAILS))
806 fprintf (dump_file, " Visiting %s\n", w->dump_asm_name ());
807 get_read_write_all_from_node (w, read_all, write_all);
808 if (read_all && write_all)
809 break;
810 }
811
812 /* Initialized the bitmaps global sets for the reduced node. */
813 if (read_all)
814 node_g->statics_read = all_module_statics;
815 else
816 node_g->statics_read = copy_static_var_set (node_l->statics_read, true);
817 if (write_all)
818 node_g->statics_written = all_module_statics;
819 else
820 node_g->statics_written
821 = copy_static_var_set (node_l->statics_written, true);
822
823 /* Merge the sets of this cycle with all sets of callees reached
824 from this cycle. */
825 FOR_EACH_VEC_ELT (cycle_nodes, x, w)
826 {
827 if (read_all && write_all)
828 break;
829
830 if (w != node)
831 {
832 ipa_reference_vars_info_t w_ri = get_reference_vars_info (w);
833 ipa_reference_local_vars_info_t w_l = &w_ri->local;
834 int flags = flags_from_decl_or_type (w->decl);
835
836 if (!(flags & ECF_CONST))
837 read_all = union_static_var_sets (node_g->statics_read,
838 w_l->statics_read);
839 if (!(flags & ECF_PURE)
840 && !w->cannot_return_p ())
841 write_all = union_static_var_sets (node_g->statics_written,
842 w_l->statics_written);
843 }
844
845 propagate_bits (node_g, w);
846 }
847
848 /* All nodes within a cycle have the same global info bitmaps. */
849 FOR_EACH_VEC_ELT (cycle_nodes, x, w)
850 {
851 ipa_reference_vars_info_t w_ri = get_reference_vars_info (w);
852 w_ri->global = *node_g;
853 }
854
855 cycle_nodes.release ();
856 }
857
858 if (dump_file)
859 {
860 for (i = 0; i < order_pos; i++)
861 {
862 unsigned x;
863 struct cgraph_node *w;
864
865 node = order[i];
866 if (node->alias || !opt_for_fn (node->decl, flag_ipa_reference))
867 continue;
868
869 fprintf (dump_file, "\nFunction name:%s:", node->dump_asm_name ());
870
871 ipa_reference_vars_info_t node_info = get_reference_vars_info (node);
872 ipa_reference_global_vars_info_t node_g = &node_info->global;
873
874 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
875 FOR_EACH_VEC_ELT (cycle_nodes, x, w)
876 {
877 ipa_reference_vars_info_t w_ri = get_reference_vars_info (w);
878 ipa_reference_local_vars_info_t w_l = &w_ri->local;
879 if (w != node)
880 fprintf (dump_file, "\n next cycle: %s ", w->dump_asm_name ());
881 fprintf (dump_file, "\n locals read: ");
882 dump_static_vars_set_to_file (dump_file, w_l->statics_read);
883 fprintf (dump_file, "\n locals written: ");
884 dump_static_vars_set_to_file (dump_file, w_l->statics_written);
885 }
886 cycle_nodes.release ();
887
888 fprintf (dump_file, "\n globals read: ");
889 dump_static_vars_set_to_file (dump_file, node_g->statics_read);
890 fprintf (dump_file, "\n globals written: ");
891 dump_static_vars_set_to_file (dump_file, node_g->statics_written);
892 fprintf (dump_file, "\n");
893 }
894 }
895
896 if (ipa_ref_opt_sum_summaries == NULL)
897 {
898 ipa_ref_opt_sum_summaries = new ipa_ref_opt_summary_t (symtab);
899 ipa_ref_opt_sum_summaries->disable_insertion_hook ();
900 }
901
902 /* Cleanup. */
903 FOR_EACH_DEFINED_FUNCTION (node)
904 {
905 ipa_reference_vars_info_t node_info;
906 ipa_reference_global_vars_info_t node_g;
907
908 /* No need to produce summaries for inline clones. */
909 if (node->inlined_to)
910 continue;
911
912 node_info = get_reference_vars_info (node);
913 if (!node->alias && opt_for_fn (node->decl, flag_ipa_reference))
914 {
915 node_g = &node_info->global;
916 bool read_all =
917 (node_g->statics_read == all_module_statics
918 || bitmap_equal_p (node_g->statics_read, all_module_statics));
919 bool written_all =
920 (node_g->statics_written == all_module_statics
921 || bitmap_equal_p (node_g->statics_written,
922 all_module_statics));
923
924 /* There is no need to produce summary if we collected nothing
925 useful. */
926 if (read_all && written_all)
927 continue;
928
929 ipa_reference_optimization_summary_d *opt
930 = ipa_ref_opt_sum_summaries->get_create (node);
931
932 /* Create the complimentary sets. */
933
934 if (bitmap_empty_p (node_g->statics_read))
935 opt->statics_read = no_module_statics;
936 else if (read_all)
937 opt->statics_read = all_module_statics;
938 else
939 {
940 opt->statics_read
941 = BITMAP_ALLOC (&optimization_summary_obstack);
942 bitmap_copy (opt->statics_read, node_g->statics_read);
943 }
944
945 if (bitmap_empty_p (node_g->statics_written))
946 opt->statics_written = no_module_statics;
947 else if (written_all)
948 opt->statics_written = all_module_statics;
949 else
950 {
951 opt->statics_written
952 = BITMAP_ALLOC (&optimization_summary_obstack);
953 bitmap_copy (opt->statics_written, node_g->statics_written);
954 }
955 }
956 }
957
958 ipa_free_postorder_info ();
959 free (order);
960
961 bitmap_obstack_release (&local_info_obstack);
962
963 if (ipa_ref_var_info_summaries != NULL)
964 {
965 delete ipa_ref_var_info_summaries;
966 ipa_ref_var_info_summaries = NULL;
967 }
968
969 if (dump_file)
970 {
971 vec_free (reference_vars_to_consider);
972 reference_vars_to_consider = NULL;
973 }
974 else
975 gcc_checking_assert (!reference_vars_to_consider);
976 return remove_p ? TODO_remove_functions : 0;
977 }
978
979 /* Return true if we need to write summary of NODE. */
980
981 static bool
write_node_summary_p(struct cgraph_node * node,lto_symtab_encoder_t encoder,bitmap ltrans_statics)982 write_node_summary_p (struct cgraph_node *node,
983 lto_symtab_encoder_t encoder,
984 bitmap ltrans_statics)
985 {
986 ipa_reference_optimization_summary_t info;
987
988 /* See if we have (non-empty) info. */
989 if (!node->definition || node->inlined_to)
990 return false;
991 info = get_reference_optimization_summary (node);
992 if (!info)
993 return false;
994
995 /* See if we want to encode it.
996 Encode also referenced functions since constant folding might turn it into
997 a direct call.
998
999 In future we might also want to include summaries of functions references
1000 by initializers of constant variables references in current unit. */
1001 if (!reachable_from_this_partition_p (node, encoder)
1002 && !referenced_from_this_partition_p (node, encoder))
1003 return false;
1004
1005 /* See if the info has non-empty intersections with vars we want to
1006 encode. */
1007 bitmap_iterator bi;
1008 unsigned int i;
1009 EXECUTE_IF_AND_COMPL_IN_BITMAP (ltrans_statics, info->statics_read, 0,
1010 i, bi)
1011 return true;
1012 EXECUTE_IF_AND_COMPL_IN_BITMAP (ltrans_statics, info->statics_written, 0,
1013 i, bi)
1014 return true;
1015 return false;
1016 }
1017
1018 /* Stream out BITS<RANS_STATICS as list of decls to OB.
1019 LTRANS_STATICS_BITCOUNT specify number of bits in LTRANS_STATICS
1020 or -1. When it is positive, just output -1 when
1021 BITS<RANS_STATICS == BITS<RANS_STATICS. */
1022
1023 static void
stream_out_bitmap(struct lto_simple_output_block * ob,bitmap bits,bitmap ltrans_statics,int ltrans_statics_bitcount)1024 stream_out_bitmap (struct lto_simple_output_block *ob,
1025 bitmap bits, bitmap ltrans_statics,
1026 int ltrans_statics_bitcount)
1027 {
1028 int count = 0;
1029 unsigned int index;
1030 bitmap_iterator bi;
1031 if (bits == all_module_statics)
1032 {
1033 streamer_write_hwi_stream (ob->main_stream, -1);
1034 return;
1035 }
1036 EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
1037 count ++;
1038 if (count == ltrans_statics_bitcount)
1039 {
1040 streamer_write_hwi_stream (ob->main_stream, -1);
1041 return;
1042 }
1043 streamer_write_hwi_stream (ob->main_stream, count);
1044 if (!count)
1045 return;
1046 EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
1047 {
1048 tree decl = (*reference_vars_to_consider) [index];
1049 lto_output_var_decl_ref (ob->decl_state, ob->main_stream, decl);
1050 }
1051 }
1052
1053 /* Serialize the ipa info for lto. */
1054
1055 static void
ipa_reference_write_optimization_summary(void)1056 ipa_reference_write_optimization_summary (void)
1057 {
1058 struct lto_simple_output_block *ob
1059 = lto_create_simple_output_block (LTO_section_ipa_reference);
1060 unsigned int count = 0;
1061 int ltrans_statics_bitcount = 0;
1062 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
1063 auto_bitmap ltrans_statics;
1064 int i;
1065
1066 gcc_checking_assert (!reference_vars_to_consider);
1067 vec_alloc (reference_vars_to_consider, ipa_reference_vars_uids);
1068 reference_vars_to_consider->safe_grow (ipa_reference_vars_uids, true);
1069
1070 /* See what variables we are interested in. */
1071 for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
1072 {
1073 symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
1074 varpool_node *vnode = dyn_cast <varpool_node *> (snode);
1075 int id;
1076
1077 if (vnode
1078 && (id = ipa_reference_var_uid (vnode->decl)) != -1
1079 && referenced_from_this_partition_p (vnode, encoder))
1080 {
1081 tree decl = vnode->decl;
1082 bitmap_set_bit (ltrans_statics, id);
1083 (*reference_vars_to_consider)[id] = decl;
1084 ltrans_statics_bitcount ++;
1085 }
1086 }
1087
1088
1089 if (ltrans_statics_bitcount)
1090 for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
1091 {
1092 symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
1093 cgraph_node *cnode = dyn_cast <cgraph_node *> (snode);
1094 if (cnode && write_node_summary_p (cnode, encoder, ltrans_statics))
1095 count++;
1096 }
1097
1098 streamer_write_uhwi_stream (ob->main_stream, count);
1099 if (count)
1100 stream_out_bitmap (ob, ltrans_statics, ltrans_statics,
1101 -1);
1102
1103 /* Process all of the functions. */
1104 if (ltrans_statics_bitcount)
1105 for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
1106 {
1107 symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
1108 cgraph_node *cnode = dyn_cast <cgraph_node *> (snode);
1109 if (cnode && write_node_summary_p (cnode, encoder, ltrans_statics))
1110 {
1111 ipa_reference_optimization_summary_t info;
1112 int node_ref;
1113
1114 info = get_reference_optimization_summary (cnode);
1115 node_ref = lto_symtab_encoder_encode (encoder, snode);
1116 streamer_write_uhwi_stream (ob->main_stream, node_ref);
1117
1118 stream_out_bitmap (ob, info->statics_read, ltrans_statics,
1119 ltrans_statics_bitcount);
1120 stream_out_bitmap (ob, info->statics_written, ltrans_statics,
1121 ltrans_statics_bitcount);
1122 }
1123 }
1124 lto_destroy_simple_output_block (ob);
1125 vec_free (reference_vars_to_consider);
1126 reference_vars_to_consider = NULL;
1127 }
1128
1129 /* Deserialize the ipa info for lto. */
1130
1131 static void
ipa_reference_read_optimization_summary(void)1132 ipa_reference_read_optimization_summary (void)
1133 {
1134 struct lto_file_decl_data ** file_data_vec
1135 = lto_get_file_decl_data ();
1136 struct lto_file_decl_data * file_data;
1137 unsigned int j = 0;
1138 bitmap_obstack_initialize (&optimization_summary_obstack);
1139
1140 gcc_checking_assert (ipa_ref_opt_sum_summaries == NULL);
1141 ipa_ref_opt_sum_summaries = new ipa_ref_opt_summary_t (symtab);
1142 ipa_ref_opt_sum_summaries->disable_insertion_hook ();
1143 ipa_reference_vars_map = new reference_vars_map_t(257);
1144 varpool_node_hooks
1145 = symtab->add_varpool_removal_hook (varpool_removal_hook, NULL);
1146 ipa_reference_vars_uids = 0;
1147
1148 all_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
1149 no_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
1150
1151 while ((file_data = file_data_vec[j++]))
1152 {
1153 const char *data;
1154 size_t len;
1155 class lto_input_block *ib
1156 = lto_create_simple_input_block (file_data,
1157 LTO_section_ipa_reference,
1158 &data, &len);
1159 if (ib)
1160 {
1161 unsigned int i;
1162 unsigned int f_count = streamer_read_uhwi (ib);
1163 int b_count;
1164 if (!f_count)
1165 continue;
1166 b_count = streamer_read_hwi (ib);
1167 if (dump_file)
1168 fprintf (dump_file, "all module statics:");
1169 for (i = 0; i < (unsigned int)b_count; i++)
1170 {
1171 tree v_decl = lto_input_var_decl_ref (ib, file_data);
1172 bool existed;
1173 bitmap_set_bit (all_module_statics,
1174 ipa_reference_var_get_or_insert_uid
1175 (v_decl, &existed));
1176 gcc_checking_assert (!existed);
1177 if (dump_file)
1178 fprintf (dump_file, " %s", fndecl_name (v_decl));
1179 }
1180
1181 for (i = 0; i < f_count; i++)
1182 {
1183 unsigned int j, index;
1184 struct cgraph_node *node;
1185 int v_count;
1186 lto_symtab_encoder_t encoder;
1187
1188 index = streamer_read_uhwi (ib);
1189 encoder = file_data->symtab_node_encoder;
1190 node = dyn_cast<cgraph_node *> (lto_symtab_encoder_deref
1191 (encoder, index));
1192
1193 ipa_reference_optimization_summary_d *info
1194 = ipa_ref_opt_sum_summaries->get_create (node);
1195
1196 if (dump_file)
1197 fprintf (dump_file,
1198 "\nFunction name:%s:\n static read:",
1199 node->dump_asm_name ());
1200
1201 /* Set the statics read. */
1202 v_count = streamer_read_hwi (ib);
1203 if (v_count == -1)
1204 {
1205 info->statics_read = all_module_statics;
1206 if (dump_file)
1207 fprintf (dump_file, " all module statics");
1208 }
1209 else if (v_count == 0)
1210 info->statics_read = no_module_statics;
1211 else
1212 {
1213 info->statics_read = BITMAP_ALLOC
1214 (&optimization_summary_obstack);
1215 for (j = 0; j < (unsigned int)v_count; j++)
1216 {
1217 tree v_decl = lto_input_var_decl_ref (ib, file_data);
1218 bitmap_set_bit (info->statics_read,
1219 ipa_reference_var_uid (v_decl));
1220 if (dump_file)
1221 fprintf (dump_file, " %s", fndecl_name (v_decl));
1222 }
1223 }
1224
1225 if (dump_file)
1226 fprintf (dump_file,
1227 "\n static written:");
1228 /* Set the statics written. */
1229 v_count = streamer_read_hwi (ib);
1230 if (v_count == -1)
1231 {
1232 info->statics_written = all_module_statics;
1233 if (dump_file)
1234 fprintf (dump_file, " all module statics");
1235 }
1236 else if (v_count == 0)
1237 info->statics_written = no_module_statics;
1238 else
1239 {
1240 info->statics_written = BITMAP_ALLOC
1241 (&optimization_summary_obstack);
1242 for (j = 0; j < (unsigned int)v_count; j++)
1243 {
1244 tree v_decl = lto_input_var_decl_ref (ib, file_data);
1245 bitmap_set_bit (info->statics_written,
1246 ipa_reference_var_uid (v_decl));
1247 if (dump_file)
1248 fprintf (dump_file, " %s", fndecl_name (v_decl));
1249 }
1250 }
1251 if (dump_file)
1252 fprintf (dump_file, "\n");
1253 }
1254
1255 lto_destroy_simple_input_block (file_data,
1256 LTO_section_ipa_reference,
1257 ib, data, len);
1258 }
1259 else
1260 /* Fatal error here. We do not want to support compiling ltrans units
1261 with different version of compiler or different flags than
1262 the WPA unit, so this should never happen. */
1263 fatal_error (input_location,
1264 "ipa reference summary is missing in ltrans unit");
1265 }
1266 }
1267
1268 namespace {
1269
1270 const pass_data pass_data_ipa_reference =
1271 {
1272 IPA_PASS, /* type */
1273 "static-var", /* name */
1274 OPTGROUP_NONE, /* optinfo_flags */
1275 TV_IPA_REFERENCE, /* tv_id */
1276 0, /* properties_required */
1277 0, /* properties_provided */
1278 0, /* properties_destroyed */
1279 0, /* todo_flags_start */
1280 0, /* todo_flags_finish */
1281 };
1282
1283 class pass_ipa_reference : public ipa_opt_pass_d
1284 {
1285 public:
pass_ipa_reference(gcc::context * ctxt)1286 pass_ipa_reference (gcc::context *ctxt)
1287 : ipa_opt_pass_d (pass_data_ipa_reference, ctxt,
1288 NULL, /* generate_summary */
1289 NULL, /* write_summary */
1290 NULL, /* read_summary */
1291 ipa_reference_write_optimization_summary, /*
1292 write_optimization_summary */
1293 ipa_reference_read_optimization_summary, /*
1294 read_optimization_summary */
1295 NULL, /* stmt_fixup */
1296 0, /* function_transform_todo_flags_start */
1297 NULL, /* function_transform */
1298 NULL) /* variable_transform */
1299 {}
1300
1301 /* opt_pass methods: */
gate(function *)1302 virtual bool gate (function *)
1303 {
1304 return ((in_lto_p || flag_ipa_reference)
1305 /* Don't bother doing anything if the program has errors. */
1306 && !seen_error ());
1307 }
1308
execute(function *)1309 virtual unsigned int execute (function *) { return propagate (); }
1310
1311 }; // class pass_ipa_reference
1312
1313 } // anon namespace
1314
1315 ipa_opt_pass_d *
make_pass_ipa_reference(gcc::context * ctxt)1316 make_pass_ipa_reference (gcc::context *ctxt)
1317 {
1318 return new pass_ipa_reference (ctxt);
1319 }
1320
1321 /* Reset all state within ipa-reference.c so that we can rerun the compiler
1322 within the same process. For use by toplev::finalize. */
1323
1324 void
ipa_reference_c_finalize(void)1325 ipa_reference_c_finalize (void)
1326 {
1327 if (ipa_ref_opt_sum_summaries != NULL)
1328 {
1329 delete ipa_ref_opt_sum_summaries;
1330 ipa_ref_opt_sum_summaries = NULL;
1331 delete ipa_reference_vars_map;
1332 ipa_reference_vars_map = NULL;
1333 symtab->remove_varpool_removal_hook (varpool_node_hooks);
1334 }
1335
1336 if (ipa_init_p)
1337 {
1338 bitmap_obstack_release (&optimization_summary_obstack);
1339 ipa_init_p = false;
1340 }
1341 }
1342