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