2016-07-28 Steven G. Kargl <kargl@gcc.gnu.org>
[official-gcc.git] / gcc / ipa-reference.c
blobb52db42ed28f0a1db7f5b51431ec48fa46f32498
1 /* Callgraph based analysis of static variables.
2 Copyright (C) 2004-2016 Free Software Foundation, Inc.
3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
5 This file is part of GCC.
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.
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.
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/>. */
21 /* This file gathers information about how variables whose scope is
22 confined to the compilation unit are used.
24 The transitive call site specific clobber effects are computed
25 for the variables whose scope is contained within this compilation
26 unit.
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. */
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"
53 static void remove_node_data (struct cgraph_node *node,
54 void *data ATTRIBUTE_UNUSED);
55 static void duplicate_node_data (struct cgraph_node *src,
56 struct cgraph_node *dst,
57 void *data ATTRIBUTE_UNUSED);
59 /* The static variables defined within the compilation unit that are
60 loaded or stored directly by function that owns this structure. */
62 struct ipa_reference_local_vars_info_d
64 bitmap statics_read;
65 bitmap statics_written;
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. */
73 struct ipa_reference_global_vars_info_d
75 bitmap statics_read;
76 bitmap statics_written;
79 /* Information we save about every function after ipa-reference is completed. */
81 struct ipa_reference_optimization_summary_d
83 bitmap statics_not_read;
84 bitmap statics_not_written;
87 typedef struct ipa_reference_local_vars_info_d *ipa_reference_local_vars_info_t;
88 typedef struct ipa_reference_global_vars_info_d *ipa_reference_global_vars_info_t;
89 typedef struct ipa_reference_optimization_summary_d *ipa_reference_optimization_summary_t;
91 struct ipa_reference_vars_info_d
93 struct ipa_reference_local_vars_info_d local;
94 struct ipa_reference_global_vars_info_d global;
97 typedef struct ipa_reference_vars_info_d *ipa_reference_vars_info_t;
99 /* This splay tree contains all of the static variables that are
100 being considered by the compilation level alias analysis. */
101 static splay_tree reference_vars_to_consider;
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 /* Set of all statics that should be ignored because they are touched by
108 -fno-ipa-reference code. */
109 static bitmap ignore_module_statics;
111 /* Obstack holding bitmaps of local analysis (live from analysis to
112 propagation) */
113 static bitmap_obstack local_info_obstack;
114 /* Obstack holding global analysis live forever. */
115 static bitmap_obstack optimization_summary_obstack;
117 /* Holders of ipa cgraph hooks: */
118 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
119 static struct cgraph_node_hook_list *node_removal_hook_holder;
121 /* Vector where the reference var infos are actually stored.
122 Indexed by UID of call graph nodes. */
123 static vec<ipa_reference_vars_info_t> ipa_reference_vars_vector;
125 /* TODO: find a place where we should release the vector. */
126 static vec<ipa_reference_optimization_summary_t> ipa_reference_opt_sum_vector;
128 /* Return the ipa_reference_vars structure starting from the cgraph NODE. */
129 static inline ipa_reference_vars_info_t
130 get_reference_vars_info (struct cgraph_node *node)
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];
138 /* Return the ipa_reference_vars structure starting from the cgraph NODE. */
139 static inline ipa_reference_optimization_summary_t
140 get_reference_optimization_summary (struct cgraph_node *node)
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];
148 /* Return the ipa_reference_vars structure starting from the cgraph NODE. */
149 static inline void
150 set_reference_vars_info (struct cgraph_node *node,
151 ipa_reference_vars_info_t info)
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;
159 /* Return the ipa_reference_vars structure starting from the cgraph NODE. */
160 static inline void
161 set_reference_optimization_summary (struct cgraph_node *node,
162 ipa_reference_optimization_summary_t info)
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;
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. */
174 bitmap
175 ipa_reference_get_not_read_global (struct cgraph_node *fn)
177 if (!opt_for_fn (current_function_decl, flag_ipa_reference))
178 return NULL;
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);
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;
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. */
203 bitmap
204 ipa_reference_get_not_written_global (struct cgraph_node *fn)
206 if (!opt_for_fn (current_function_decl, flag_ipa_reference))
207 return NULL;
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);
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;
228 /* Hepler for is_proper_for_analysis. */
229 static bool
230 is_improper (symtab_node *n, void *v ATTRIBUTE_UNUSED)
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;
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;
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;
248 /* We can not track variables with address taken. */
249 if (TREE_ADDRESSABLE (t))
250 return true;
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;
257 return false;
260 /* Return true if the variable T is the right kind of static variable to
261 perform compilation unit scope escape analysis. */
263 static inline bool
264 is_proper_for_analysis (tree t)
266 if (bitmap_bit_p (ignore_module_statics, ipa_reference_var_uid (t)))
267 return false;
269 if (symtab_node::get (t)
270 ->call_for_symbol_and_aliases (is_improper, NULL, true))
271 return false;
273 return true;
276 /* Lookup the tree node for the static variable that has UID and
277 convert the name to a string for debugging. */
279 static const char *
280 get_static_name (int index)
282 splay_tree_node stn =
283 splay_tree_lookup (reference_vars_to_consider, index);
284 return fndecl_name ((tree)(stn->value));
287 /* Dump a set of static vars to FILE. */
288 static void
289 dump_static_vars_set_to_file (FILE *f, bitmap set)
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)
300 fprintf (f, "%s ", get_static_name (index));
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. */
308 static bool
309 union_static_var_sets (bitmap &x, bitmap y)
311 if (x != all_module_statics)
313 if (y == all_module_statics)
315 BITMAP_FREE (x);
316 x = all_module_statics;
318 else if (bitmap_ior_into (x, y))
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))
328 BITMAP_FREE (x);
329 x = all_module_statics;
333 return x == all_module_statics;
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. */
339 static bitmap
340 copy_static_var_set (bitmap set)
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;
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. */
357 static void
358 propagate_bits (ipa_reference_global_vars_info_t x_global, struct cgraph_node *x)
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)
367 enum availability avail;
368 struct cgraph_node *y = e->callee->function_symbol (&avail);
369 if (!y)
370 continue;
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))))
378 if (get_reference_vars_info (y))
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;
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;
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;
394 union_static_var_sets (x_global->statics_read,
395 y_global->statics_read);
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;
404 union_static_var_sets (x_global->statics_written,
405 y_global->statics_written);
407 else
408 gcc_unreachable ();
413 static bool ipa_init_p = false;
415 /* The init routine for analyzing global static variable usage. See
416 comments at top for description. */
417 static void
418 ipa_init (void)
420 if (ipa_init_p)
421 return;
423 ipa_init_p = true;
425 if (dump_file)
426 reference_vars_to_consider = splay_tree_new (splay_tree_compare_ints, 0, 0);
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);
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);
440 /* Set up the persistent info for FN. */
442 static ipa_reference_local_vars_info_t
443 init_function_info (struct cgraph_node *fn)
445 ipa_reference_vars_info_t info
446 = XCNEW (struct ipa_reference_vars_info_d);
448 /* Add the info to the tree's annotation. */
449 set_reference_vars_info (fn, info);
451 info->local.statics_read = BITMAP_ALLOC (&local_info_obstack);
452 info->local.statics_written = BITMAP_ALLOC (&local_info_obstack);
454 return &info->local;
458 /* This is the main routine for finding the reference patterns for
459 global variables within a function FN. */
461 static void
462 analyze_function (struct cgraph_node *fn)
464 ipa_reference_local_vars_info_t local;
465 struct ipa_ref *ref = NULL;
466 int i;
467 tree var;
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++)
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)))
484 if (dump_file)
485 splay_tree_insert (reference_vars_to_consider,
486 ipa_reference_var_uid (var),
487 (splay_tree_value)var);
489 switch (ref->use)
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 ();
506 if (fn->cannot_return_p ())
507 bitmap_clear (local->statics_written);
511 /* Called when new clone is inserted to callgraph late. */
513 static void
514 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
515 void *data ATTRIBUTE_UNUSED)
517 ipa_reference_optimization_summary_t ginfo;
518 ipa_reference_optimization_summary_t dst_ginfo;
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);
531 /* Called when node is removed. */
533 static void
534 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
536 ipa_reference_optimization_summary_t ginfo;
537 ginfo = get_reference_optimization_summary (node);
538 if (ginfo)
540 if (ginfo->statics_not_read
541 && ginfo->statics_not_read != all_module_statics)
542 BITMAP_FREE (ginfo->statics_not_read);
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);
552 /* Analyze each function in the cgraph to see which global or statics
553 are read or written. */
555 static void
556 generate_summary (void)
558 struct cgraph_node *node;
559 unsigned int index;
560 bitmap_iterator bi;
562 ipa_init ();
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))
568 struct ipa_ref *ref = NULL;
569 int i;
570 tree var;
571 for (i = 0; node->iterate_reference (i, ref); i++)
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));
581 FOR_EACH_DEFINED_FUNCTION (node)
582 analyze_function (node);
584 if (dump_file)
585 EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
587 fprintf (dump_file, "\nPromotable global:%s (uid=%u)\n",
588 get_static_name (index), index);
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))
596 ipa_reference_local_vars_info_t l;
597 unsigned int index;
598 bitmap_iterator bi;
600 l = &get_reference_vars_info (node)->local;
601 fprintf (dump_file,
602 "\nFunction name:%s/%i:",
603 node->asm_name (), node->order);
604 fprintf (dump_file, "\n locals read: ");
605 if (l->statics_read)
606 EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
607 0, index, bi)
609 fprintf (dump_file, "%s ",
610 get_static_name (index));
612 fprintf (dump_file, "\n locals written: ");
613 if (l->statics_written)
614 EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
615 0, index, bi)
617 fprintf (dump_file, "%s ", get_static_name (index));
622 /* Set READ_ALL/WRITE_ALL based on decl flags of NODE. */
624 static void
625 read_write_all_from_decl (struct cgraph_node *node,
626 bool &read_all, bool &write_all)
628 tree decl = node->decl;
629 int flags = flags_from_decl_or_type (decl);
630 if ((flags & ECF_LEAF)
631 && node->get_availability () < AVAIL_INTERPOSABLE)
633 else if (flags & ECF_CONST)
635 else if ((flags & ECF_PURE) || node->cannot_return_p ())
637 read_all = true;
638 if (dump_file && (dump_flags & TDF_DETAILS))
639 fprintf (dump_file, " %s/%i -> read all\n",
640 node->asm_name (), node->order);
642 else
644 /* TODO: To be able to produce sane results, we should also handle
645 common builtins, in particular throw. */
646 read_all = true;
647 write_all = true;
648 if (dump_file && (dump_flags & TDF_DETAILS))
649 fprintf (dump_file, " %s/%i -> read all, write all\n",
650 node->asm_name (), node->order);
654 /* Set READ_ALL/WRITE_ALL based on decl flags of NODE or any member
655 in the cycle of NODE. */
657 static void
658 get_read_write_all_from_node (struct cgraph_node *node,
659 bool &read_all, bool &write_all)
661 struct cgraph_edge *e, *ie;
663 /* When function is overwritable, we can not assume anything. */
664 if (node->get_availability () <= AVAIL_INTERPOSABLE
665 || (node->analyzed && !opt_for_fn (node->decl, flag_ipa_reference)))
666 read_write_all_from_decl (node, read_all, write_all);
668 for (e = node->callees;
669 e && !(read_all && write_all);
670 e = e->next_callee)
672 enum availability avail;
673 struct cgraph_node *callee = e->callee->function_symbol (&avail);
674 gcc_checking_assert (callee);
675 if (avail <= AVAIL_INTERPOSABLE
676 || (callee->analyzed && !opt_for_fn (callee->decl, flag_ipa_reference)))
677 read_write_all_from_decl (callee, read_all, write_all);
680 for (ie = node->indirect_calls;
681 ie && !(read_all && write_all);
682 ie = ie->next_callee)
683 if (!(ie->indirect_info->ecf_flags & ECF_CONST))
685 read_all = true;
686 if (dump_file && (dump_flags & TDF_DETAILS))
687 fprintf (dump_file, " indirect call -> read all\n");
688 if (!ie->cannot_lead_to_return_p ()
689 && !(ie->indirect_info->ecf_flags & ECF_PURE))
691 if (dump_file && (dump_flags & TDF_DETAILS))
692 fprintf (dump_file, " indirect call -> write all\n");
693 write_all = true;
698 /* Skip edges from and to nodes without ipa_reference enables. This leave
699 them out of strongy connected coponents and makes them easyto skip in the
700 propagation loop bellow. */
702 static bool
703 ignore_edge_p (cgraph_edge *e)
705 return (!opt_for_fn (e->caller->decl, flag_ipa_reference)
706 || !opt_for_fn (e->callee->function_symbol ()->decl,
707 flag_ipa_reference));
710 /* Produce the global information by preforming a transitive closure
711 on the local information that was produced by ipa_analyze_function. */
713 static unsigned int
714 propagate (void)
716 struct cgraph_node *node;
717 struct cgraph_node **order =
718 XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
719 int order_pos;
720 int i;
721 bool remove_p;
723 if (dump_file)
724 cgraph_node::dump_cgraph (dump_file);
726 remove_p = ipa_discover_readonly_nonaddressable_vars ();
727 generate_summary ();
729 /* Propagate the local information through the call graph to produce
730 the global information. All the nodes within a cycle will have
731 the same info so we collapse cycles first. Then we can do the
732 propagation in one pass from the leaves to the roots. */
733 order_pos = ipa_reduced_postorder (order, true, true, ignore_edge_p);
734 if (dump_file)
735 ipa_print_order (dump_file, "reduced", order, order_pos);
737 for (i = 0; i < order_pos; i++ )
739 unsigned x;
740 struct cgraph_node *w;
741 ipa_reference_vars_info_t node_info;
742 ipa_reference_global_vars_info_t node_g;
743 ipa_reference_local_vars_info_t node_l;
744 bool read_all = false;
745 bool write_all = false;
747 node = order[i];
748 if (node->alias || !opt_for_fn (node->decl, flag_ipa_reference))
749 continue;
751 node_info = get_reference_vars_info (node);
752 gcc_assert (node_info);
753 node_l = &node_info->local;
754 node_g = &node_info->global;
756 if (dump_file && (dump_flags & TDF_DETAILS))
757 fprintf (dump_file, "Starting cycle with %s/%i\n",
758 node->asm_name (), node->order);
760 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
762 /* If any node in a cycle is read_all or write_all, they all are. */
763 FOR_EACH_VEC_ELT (cycle_nodes, x, w)
765 if (dump_file && (dump_flags & TDF_DETAILS))
766 fprintf (dump_file, " Visiting %s/%i\n",
767 w->asm_name (), w->order);
768 get_read_write_all_from_node (w, read_all, write_all);
769 if (read_all && write_all)
770 break;
773 /* Initialized the bitmaps global sets for the reduced node. */
774 if (read_all)
775 node_g->statics_read = all_module_statics;
776 else
777 node_g->statics_read = copy_static_var_set (node_l->statics_read);
778 if (write_all)
779 node_g->statics_written = all_module_statics;
780 else
781 node_g->statics_written = copy_static_var_set (node_l->statics_written);
783 /* Merge the sets of this cycle with all sets of callees reached
784 from this cycle. */
785 FOR_EACH_VEC_ELT (cycle_nodes, x, w)
787 if (read_all && write_all)
788 break;
790 if (w != node)
792 ipa_reference_vars_info_t w_ri = get_reference_vars_info (w);
793 ipa_reference_local_vars_info_t w_l = &w_ri->local;
794 int flags = flags_from_decl_or_type (w->decl);
796 if (!(flags & ECF_CONST))
797 read_all = union_static_var_sets (node_g->statics_read,
798 w_l->statics_read);
799 if (!(flags & ECF_PURE)
800 && !w->cannot_return_p ())
801 write_all = union_static_var_sets (node_g->statics_written,
802 w_l->statics_written);
805 propagate_bits (node_g, w);
808 /* All nodes within a cycle have the same global info bitmaps. */
809 FOR_EACH_VEC_ELT (cycle_nodes, x, w)
811 ipa_reference_vars_info_t w_ri = get_reference_vars_info (w);
812 w_ri->global = *node_g;
815 cycle_nodes.release ();
818 if (dump_file)
820 for (i = 0; i < order_pos; i++)
822 unsigned x;
823 struct cgraph_node *w;
825 node = order[i];
826 if (node->alias || !opt_for_fn (node->decl, flag_ipa_reference))
827 continue;
829 fprintf (dump_file,
830 "\nFunction name:%s/%i:",
831 node->asm_name (), node->order);
833 ipa_reference_vars_info_t node_info = get_reference_vars_info (node);
834 ipa_reference_global_vars_info_t node_g = &node_info->global;
836 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
837 FOR_EACH_VEC_ELT (cycle_nodes, x, w)
839 ipa_reference_vars_info_t w_ri = get_reference_vars_info (w);
840 ipa_reference_local_vars_info_t w_l = &w_ri->local;
841 if (w != node)
842 fprintf (dump_file, "\n next cycle: %s/%i ",
843 w->asm_name (), w->order);
844 fprintf (dump_file, "\n locals read: ");
845 dump_static_vars_set_to_file (dump_file, w_l->statics_read);
846 fprintf (dump_file, "\n locals written: ");
847 dump_static_vars_set_to_file (dump_file, w_l->statics_written);
849 cycle_nodes.release ();
851 fprintf (dump_file, "\n globals read: ");
852 dump_static_vars_set_to_file (dump_file, node_g->statics_read);
853 fprintf (dump_file, "\n globals written: ");
854 dump_static_vars_set_to_file (dump_file, node_g->statics_written);
855 fprintf (dump_file, "\n");
859 /* Cleanup. */
860 FOR_EACH_DEFINED_FUNCTION (node)
862 ipa_reference_vars_info_t node_info;
863 ipa_reference_global_vars_info_t node_g;
864 ipa_reference_optimization_summary_t opt;
866 node_info = get_reference_vars_info (node);
867 if (!node->alias && opt_for_fn (node->decl, flag_ipa_reference)
868 && (node->get_availability () > AVAIL_INTERPOSABLE
869 || (flags_from_decl_or_type (node->decl) & ECF_LEAF)))
871 node_g = &node_info->global;
873 opt = XCNEW (struct ipa_reference_optimization_summary_d);
874 set_reference_optimization_summary (node, opt);
876 /* Create the complimentary sets. */
878 if (bitmap_empty_p (node_g->statics_read))
879 opt->statics_not_read = all_module_statics;
880 else
882 opt->statics_not_read
883 = BITMAP_ALLOC (&optimization_summary_obstack);
884 if (node_g->statics_read != all_module_statics)
885 bitmap_and_compl (opt->statics_not_read,
886 all_module_statics,
887 node_g->statics_read);
890 if (bitmap_empty_p (node_g->statics_written))
891 opt->statics_not_written = all_module_statics;
892 else
894 opt->statics_not_written
895 = BITMAP_ALLOC (&optimization_summary_obstack);
896 if (node_g->statics_written != all_module_statics)
897 bitmap_and_compl (opt->statics_not_written,
898 all_module_statics,
899 node_g->statics_written);
902 free (node_info);
905 ipa_free_postorder_info ();
906 free (order);
908 bitmap_obstack_release (&local_info_obstack);
909 ipa_reference_vars_vector.release ();
910 if (dump_file)
911 splay_tree_delete (reference_vars_to_consider);
912 reference_vars_to_consider = NULL;
913 return remove_p ? TODO_remove_functions : 0;
916 /* Return true if we need to write summary of NODE. */
918 static bool
919 write_node_summary_p (struct cgraph_node *node,
920 lto_symtab_encoder_t encoder,
921 bitmap ltrans_statics)
923 ipa_reference_optimization_summary_t info;
925 /* See if we have (non-empty) info. */
926 if (!node->definition || node->global.inlined_to)
927 return false;
928 info = get_reference_optimization_summary (node);
929 if (!info || (bitmap_empty_p (info->statics_not_read)
930 && bitmap_empty_p (info->statics_not_written)))
931 return false;
933 /* See if we want to encode it.
934 Encode also referenced functions since constant folding might turn it into
935 a direct call.
937 In future we might also want to include summaries of functions references
938 by initializers of constant variables references in current unit. */
939 if (!reachable_from_this_partition_p (node, encoder)
940 && !referenced_from_this_partition_p (node, encoder))
941 return false;
943 /* See if the info has non-empty intersections with vars we want to encode. */
944 if (!bitmap_intersect_p (info->statics_not_read, ltrans_statics)
945 && !bitmap_intersect_p (info->statics_not_written, ltrans_statics))
946 return false;
947 return true;
950 /* Stream out BITS&LTRANS_STATICS as list of decls to OB.
951 LTRANS_STATICS_BITCOUNT specify number of bits in LTRANS_STATICS
952 or -1. When it is positive, just output -1 when
953 BITS&LTRANS_STATICS == BITS&LTRANS_STATICS. */
955 static void
956 stream_out_bitmap (struct lto_simple_output_block *ob,
957 bitmap bits, bitmap ltrans_statics,
958 int ltrans_statics_bitcount)
960 int count = 0;
961 unsigned int index;
962 bitmap_iterator bi;
963 if (bits == all_module_statics)
965 streamer_write_hwi_stream (ob->main_stream, -1);
966 return;
968 EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
969 count ++;
970 if (count == ltrans_statics_bitcount)
972 streamer_write_hwi_stream (ob->main_stream, -1);
973 return;
975 streamer_write_hwi_stream (ob->main_stream, count);
976 if (!count)
977 return;
978 EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
980 tree decl = (tree)splay_tree_lookup (reference_vars_to_consider, index)->value;
981 lto_output_var_decl_index (ob->decl_state, ob->main_stream, decl);
985 /* Serialize the ipa info for lto. */
987 static void
988 ipa_reference_write_optimization_summary (void)
990 struct lto_simple_output_block *ob
991 = lto_create_simple_output_block (LTO_section_ipa_reference);
992 unsigned int count = 0;
993 int ltrans_statics_bitcount = 0;
994 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
995 bitmap ltrans_statics = BITMAP_ALLOC (NULL);
996 int i;
998 reference_vars_to_consider = splay_tree_new (splay_tree_compare_ints, 0, 0);
1000 /* See what variables we are interested in. */
1001 for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
1003 symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
1004 varpool_node *vnode = dyn_cast <varpool_node *> (snode);
1005 if (vnode
1006 && bitmap_bit_p (all_module_statics,
1007 ipa_reference_var_uid (vnode->decl))
1008 && referenced_from_this_partition_p (vnode, encoder))
1010 tree decl = vnode->decl;
1011 bitmap_set_bit (ltrans_statics, ipa_reference_var_uid (decl));
1012 splay_tree_insert (reference_vars_to_consider,
1013 ipa_reference_var_uid (decl),
1014 (splay_tree_value)decl);
1015 ltrans_statics_bitcount ++;
1020 if (ltrans_statics_bitcount)
1021 for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
1023 symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
1024 cgraph_node *cnode = dyn_cast <cgraph_node *> (snode);
1025 if (cnode && write_node_summary_p (cnode, encoder, ltrans_statics))
1026 count++;
1029 streamer_write_uhwi_stream (ob->main_stream, count);
1030 if (count)
1031 stream_out_bitmap (ob, ltrans_statics, ltrans_statics,
1032 -1);
1034 /* Process all of the functions. */
1035 if (ltrans_statics_bitcount)
1036 for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
1038 symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
1039 cgraph_node *cnode = dyn_cast <cgraph_node *> (snode);
1040 if (cnode && write_node_summary_p (cnode, encoder, ltrans_statics))
1042 ipa_reference_optimization_summary_t info;
1043 int node_ref;
1045 info = get_reference_optimization_summary (cnode);
1046 node_ref = lto_symtab_encoder_encode (encoder, snode);
1047 streamer_write_uhwi_stream (ob->main_stream, node_ref);
1049 stream_out_bitmap (ob, info->statics_not_read, ltrans_statics,
1050 ltrans_statics_bitcount);
1051 stream_out_bitmap (ob, info->statics_not_written, ltrans_statics,
1052 ltrans_statics_bitcount);
1055 BITMAP_FREE (ltrans_statics);
1056 lto_destroy_simple_output_block (ob);
1057 splay_tree_delete (reference_vars_to_consider);
1060 /* Deserialize the ipa info for lto. */
1062 static void
1063 ipa_reference_read_optimization_summary (void)
1065 struct lto_file_decl_data ** file_data_vec
1066 = lto_get_file_decl_data ();
1067 struct lto_file_decl_data * file_data;
1068 unsigned int j = 0;
1069 bitmap_obstack_initialize (&optimization_summary_obstack);
1071 node_removal_hook_holder =
1072 symtab->add_cgraph_removal_hook (&remove_node_data, NULL);
1073 node_duplication_hook_holder =
1074 symtab->add_cgraph_duplication_hook (&duplicate_node_data, NULL);
1075 all_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
1077 while ((file_data = file_data_vec[j++]))
1079 const char *data;
1080 size_t len;
1081 struct lto_input_block *ib
1082 = lto_create_simple_input_block (file_data,
1083 LTO_section_ipa_reference,
1084 &data, &len);
1085 if (ib)
1087 unsigned int i;
1088 unsigned int f_count = streamer_read_uhwi (ib);
1089 int b_count;
1090 if (!f_count)
1091 continue;
1092 b_count = streamer_read_hwi (ib);
1093 if (dump_file)
1094 fprintf (dump_file, "all module statics:");
1095 for (i = 0; i < (unsigned int)b_count; i++)
1097 unsigned int var_index = streamer_read_uhwi (ib);
1098 tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1099 var_index);
1100 bitmap_set_bit (all_module_statics,
1101 ipa_reference_var_uid (v_decl));
1102 if (dump_file)
1103 fprintf (dump_file, " %s", fndecl_name (v_decl));
1106 for (i = 0; i < f_count; i++)
1108 unsigned int j, index;
1109 struct cgraph_node *node;
1110 ipa_reference_optimization_summary_t info;
1111 int v_count;
1112 lto_symtab_encoder_t encoder;
1114 index = streamer_read_uhwi (ib);
1115 encoder = file_data->symtab_node_encoder;
1116 node = dyn_cast<cgraph_node *> (lto_symtab_encoder_deref
1117 (encoder, index));
1118 info = XCNEW (struct ipa_reference_optimization_summary_d);
1119 set_reference_optimization_summary (node, info);
1120 info->statics_not_read = BITMAP_ALLOC (&optimization_summary_obstack);
1121 info->statics_not_written = BITMAP_ALLOC (&optimization_summary_obstack);
1122 if (dump_file)
1123 fprintf (dump_file,
1124 "\nFunction name:%s/%i:\n static not read:",
1125 node->asm_name (), node->order);
1127 /* Set the statics not read. */
1128 v_count = streamer_read_hwi (ib);
1129 if (v_count == -1)
1131 info->statics_not_read = all_module_statics;
1132 if (dump_file)
1133 fprintf (dump_file, " all module statics");
1135 else
1136 for (j = 0; j < (unsigned int)v_count; j++)
1138 unsigned int var_index = streamer_read_uhwi (ib);
1139 tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1140 var_index);
1141 bitmap_set_bit (info->statics_not_read,
1142 ipa_reference_var_uid (v_decl));
1143 if (dump_file)
1144 fprintf (dump_file, " %s", fndecl_name (v_decl));
1147 if (dump_file)
1148 fprintf (dump_file,
1149 "\n static not written:");
1150 /* Set the statics not written. */
1151 v_count = streamer_read_hwi (ib);
1152 if (v_count == -1)
1154 info->statics_not_written = all_module_statics;
1155 if (dump_file)
1156 fprintf (dump_file, " all module statics");
1158 else
1159 for (j = 0; j < (unsigned int)v_count; j++)
1161 unsigned int var_index = streamer_read_uhwi (ib);
1162 tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1163 var_index);
1164 bitmap_set_bit (info->statics_not_written,
1165 ipa_reference_var_uid (v_decl));
1166 if (dump_file)
1167 fprintf (dump_file, " %s", fndecl_name (v_decl));
1169 if (dump_file)
1170 fprintf (dump_file, "\n");
1173 lto_destroy_simple_input_block (file_data,
1174 LTO_section_ipa_reference,
1175 ib, data, len);
1177 else
1178 /* Fatal error here. We do not want to support compiling ltrans units with
1179 different version of compiler or different flags than the WPA unit, so
1180 this should never happen. */
1181 fatal_error (input_location,
1182 "ipa reference summary is missing in ltrans unit");
1186 namespace {
1188 const pass_data pass_data_ipa_reference =
1190 IPA_PASS, /* type */
1191 "static-var", /* name */
1192 OPTGROUP_NONE, /* optinfo_flags */
1193 TV_IPA_REFERENCE, /* tv_id */
1194 0, /* properties_required */
1195 0, /* properties_provided */
1196 0, /* properties_destroyed */
1197 0, /* todo_flags_start */
1198 0, /* todo_flags_finish */
1201 class pass_ipa_reference : public ipa_opt_pass_d
1203 public:
1204 pass_ipa_reference (gcc::context *ctxt)
1205 : ipa_opt_pass_d (pass_data_ipa_reference, ctxt,
1206 NULL, /* generate_summary */
1207 NULL, /* write_summary */
1208 NULL, /* read_summary */
1209 ipa_reference_write_optimization_summary, /*
1210 write_optimization_summary */
1211 ipa_reference_read_optimization_summary, /*
1212 read_optimization_summary */
1213 NULL, /* stmt_fixup */
1214 0, /* function_transform_todo_flags_start */
1215 NULL, /* function_transform */
1216 NULL) /* variable_transform */
1219 /* opt_pass methods: */
1220 virtual bool gate (function *)
1222 return ((in_lto_p || flag_ipa_reference)
1223 /* Don't bother doing anything if the program has errors. */
1224 && !seen_error ());
1227 virtual unsigned int execute (function *) { return propagate (); }
1229 }; // class pass_ipa_reference
1231 } // anon namespace
1233 ipa_opt_pass_d *
1234 make_pass_ipa_reference (gcc::context *ctxt)
1236 return new pass_ipa_reference (ctxt);
1239 /* Reset all state within ipa-reference.c so that we can rerun the compiler
1240 within the same process. For use by toplev::finalize. */
1242 void
1243 ipa_reference_c_finalize (void)
1245 if (ipa_init_p)
1247 bitmap_obstack_release (&optimization_summary_obstack);
1248 ipa_init_p = false;
1251 if (node_removal_hook_holder)
1253 symtab->remove_cgraph_removal_hook (node_removal_hook_holder);
1254 node_removal_hook_holder = NULL;
1256 if (node_duplication_hook_holder)
1258 symtab->remove_cgraph_duplication_hook (node_duplication_hook_holder);
1259 node_duplication_hook_holder = NULL;