OSDN Git Service

a66e6279e163652edb323cfebd4fb029e3d760aa
[pf3gnuchains/gcc-fork.git] / gcc / ipa-reference.c
1 /* Callgraph based analysis of static variables.
2    Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010
3    Free Software Foundation, Inc.
4    Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 /* This file gathers information about how variables whose scope is
23    confined to the compilation unit are used.
24
25    The transitive call site specific clobber effects are computed
26    for the variables whose scope is contained within this compilation
27    unit.
28
29    First each function and static variable initialization is analyzed
30    to determine which local static variables are either read, written,
31    or have their address taken.  Any local static that has its address
32    taken is removed from consideration.  Once the local read and
33    writes are determined, a transitive closure of this information is
34    performed over the call graph to determine the worst case set of
35    side effects of each call.  In later parts of the compiler, these
36    local and global sets are examined to make the call clobbering less
37    traumatic, promote some statics to registers, and improve aliasing
38    information.  */
39
40 #include "config.h"
41 #include "system.h"
42 #include "coretypes.h"
43 #include "tm.h"
44 #include "tree.h"
45 #include "tree-flow.h"
46 #include "tree-inline.h"
47 #include "tree-pass.h"
48 #include "langhooks.h"
49 #include "pointer-set.h"
50 #include "splay-tree.h"
51 #include "ggc.h"
52 #include "ipa-utils.h"
53 #include "ipa-reference.h"
54 #include "gimple.h"
55 #include "cgraph.h"
56 #include "output.h"
57 #include "flags.h"
58 #include "timevar.h"
59 #include "diagnostic.h"
60 #include "langhooks.h"
61 #include "lto-streamer.h"
62 #include "toplev.h"
63
64 static void remove_node_data (struct cgraph_node *node,
65                               void *data ATTRIBUTE_UNUSED);
66 static void duplicate_node_data (struct cgraph_node *src,
67                                  struct cgraph_node *dst,
68                                  void *data ATTRIBUTE_UNUSED);
69
70 /* The static variables defined within the compilation unit that are
71    loaded or stored directly by function that owns this structure.  */
72
73 struct ipa_reference_local_vars_info_d
74 {
75   bitmap statics_read;
76   bitmap statics_written;
77
78   /* Set when this function calls another function external to the
79      compilation unit or if the function has a asm clobber of memory.
80      In general, such calls are modeled as reading and writing all
81      variables (both bits on) but sometime there are attributes on the
82      called function so we can do better.  */
83   bool calls_read_all;
84   bool calls_write_all;
85 };
86
87 /* Statics that are read and written by some set of functions. The
88    local ones are based on the loads and stores local to the function.
89    The global ones are based on the local info as well as the
90    transitive closure of the functions that are called. */
91
92 struct ipa_reference_global_vars_info_d
93 {
94   bitmap statics_read;
95   bitmap statics_written;
96 };
97
98 /* Information we save about every function after ipa-reference is completted.  */
99
100 struct ipa_reference_optimization_summary_d
101 {
102   bitmap statics_not_read;
103   bitmap statics_not_written;
104 };
105
106 typedef struct ipa_reference_local_vars_info_d *ipa_reference_local_vars_info_t;
107 typedef struct ipa_reference_global_vars_info_d *ipa_reference_global_vars_info_t;
108 typedef struct ipa_reference_optimization_summary_d *ipa_reference_optimization_summary_t;
109
110 struct ipa_reference_vars_info_d
111 {
112   struct ipa_reference_local_vars_info_d local;
113   struct ipa_reference_global_vars_info_d global;
114 };
115
116 typedef struct ipa_reference_vars_info_d *ipa_reference_vars_info_t;
117
118 /* This splay tree contains all of the static variables that are
119    being considered by the compilation level alias analysis.  */
120 static splay_tree reference_vars_to_consider;
121
122 /* A bit is set for every module static we are considering.  This is
123    ored into the local info when asm code is found that clobbers all
124    memory. */
125 static bitmap all_module_statics;
126
127 /* Obstack holding bitmaps of local analysis (live from analysis to
128    propagation)  */
129 static bitmap_obstack local_info_obstack;
130 /* Obstack holding global analysis live forever.  */
131 static bitmap_obstack optimization_summary_obstack;
132
133 /* Holders of ipa cgraph hooks: */
134 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
135 static struct cgraph_node_hook_list *node_removal_hook_holder;
136
137 /* Vector where the reference var infos are actually stored. */
138 DEF_VEC_P (ipa_reference_vars_info_t);
139 DEF_VEC_ALLOC_P (ipa_reference_vars_info_t, heap);
140 static VEC (ipa_reference_vars_info_t, heap) *ipa_reference_vars_vector;
141 DEF_VEC_P (ipa_reference_optimization_summary_t);
142 DEF_VEC_ALLOC_P (ipa_reference_optimization_summary_t, heap);
143 static VEC (ipa_reference_optimization_summary_t, heap) *ipa_reference_opt_sum_vector;
144
145 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
146 static inline ipa_reference_vars_info_t
147 get_reference_vars_info (struct cgraph_node *node)
148 {
149   if (!ipa_reference_vars_vector
150       || VEC_length (ipa_reference_vars_info_t,
151                      ipa_reference_vars_vector) <= (unsigned int) node->uid)
152     return NULL;
153   return VEC_index (ipa_reference_vars_info_t, ipa_reference_vars_vector,
154                     node->uid);
155 }
156
157 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
158 static inline ipa_reference_optimization_summary_t
159 get_reference_optimization_summary (struct cgraph_node *node)
160 {
161   if (!ipa_reference_opt_sum_vector
162       || (VEC_length (ipa_reference_optimization_summary_t,
163                      ipa_reference_opt_sum_vector)
164           <= (unsigned int) node->uid))
165     return NULL;
166   return VEC_index (ipa_reference_optimization_summary_t, ipa_reference_opt_sum_vector,
167                     node->uid);
168 }
169
170 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
171 static inline void
172 set_reference_vars_info (struct cgraph_node *node,
173                          ipa_reference_vars_info_t info)
174 {
175   if (!ipa_reference_vars_vector
176       || VEC_length (ipa_reference_vars_info_t,
177                      ipa_reference_vars_vector) <= (unsigned int) node->uid)
178     VEC_safe_grow_cleared (ipa_reference_vars_info_t, heap,
179                            ipa_reference_vars_vector, node->uid + 1);
180   VEC_replace (ipa_reference_vars_info_t, ipa_reference_vars_vector,
181                node->uid, info);
182 }
183
184 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
185 static inline void
186 set_reference_optimization_summary (struct cgraph_node *node,
187                                     ipa_reference_optimization_summary_t info)
188 {
189   if (!ipa_reference_opt_sum_vector
190       || (VEC_length (ipa_reference_optimization_summary_t,
191                       ipa_reference_opt_sum_vector)
192           <= (unsigned int) node->uid))
193     VEC_safe_grow_cleared (ipa_reference_optimization_summary_t,
194                            heap, ipa_reference_opt_sum_vector, node->uid + 1);
195   VEC_replace (ipa_reference_optimization_summary_t,
196                ipa_reference_opt_sum_vector, node->uid, info);
197 }
198
199 /* Return a bitmap indexed by_DECL_UID uid for the static variables
200    that are not read during the execution of the function FN.  Returns
201    NULL if no data is available.  */
202
203 bitmap
204 ipa_reference_get_not_read_global (struct cgraph_node *fn)
205 {
206   ipa_reference_optimization_summary_t info;
207
208   info = get_reference_optimization_summary (fn);
209   if (info)
210     return info->statics_not_read;
211   else
212     return NULL;
213 }
214
215 /* Return a bitmap indexed by DECL_UID uid for the static variables
216    that are not written during the execution of the function FN.  Note
217    that variables written may or may not be read during the function
218    call.  Returns NULL if no data is available.  */
219
220 bitmap
221 ipa_reference_get_not_written_global (struct cgraph_node *fn)
222 {
223   ipa_reference_optimization_summary_t info;
224
225   info = get_reference_optimization_summary (fn);
226   if (info)
227     return info->statics_not_written;
228   else
229     return NULL;
230 }
231
232 \f
233
234 /* Add VAR to all_module_statics and the two
235    reference_vars_to_consider* sets.  */
236
237 static inline void
238 add_static_var (tree var)
239 {
240   int uid = DECL_UID (var);
241   gcc_assert (TREE_CODE (var) == VAR_DECL);
242   if (!bitmap_bit_p (all_module_statics, uid))
243     {
244       if (dump_file)
245         splay_tree_insert (reference_vars_to_consider,
246                            uid, (splay_tree_value)var);
247       bitmap_set_bit (all_module_statics, uid);
248     }
249 }
250
251 /* Return true if the variable T is the right kind of static variable to
252    perform compilation unit scope escape analysis.  */
253
254 static inline bool
255 is_proper_for_analysis (tree t)
256 {
257   /* We handle only variables whose address is never taken.  */
258   if (TREE_ADDRESSABLE (t))
259     return false;
260   /* If the variable has the "used" attribute, treat it as if it had a
261      been touched by the devil.  */
262   if (DECL_PRESERVE_P (t))
263     return false;
264
265   /* Do not want to do anything with volatile except mark any
266      function that uses one to be not const or pure.  */
267   if (TREE_THIS_VOLATILE (t))
268     return false;
269
270   /* We cannot touch decls where the type needs constructing.  */
271   if (TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t)))
272     return false;
273
274   /* This is a variable we care about.  Check if we have seen it
275      before, and if not add it the set of variables we care about.  */
276   if (all_module_statics
277       && !bitmap_bit_p (all_module_statics, DECL_UID (t)))
278     add_static_var (t);
279
280   return true;
281 }
282
283 /* Lookup the tree node for the static variable that has UID and
284    convert the name to a string for debugging.  */
285
286 static const char *
287 get_static_name (int index)
288 {
289   splay_tree_node stn =
290     splay_tree_lookup (reference_vars_to_consider, index);
291   if (stn)
292     return lang_hooks.decl_printable_name ((tree)(stn->value), 2);
293   return NULL;
294 }
295
296 /* Or in all of the bits from every callee of X into X_GLOBAL, the caller's cycle,
297    bit vector.  There are several cases to check to avoid the sparse
298    bitmap oring.  */
299
300 static void
301 propagate_bits (ipa_reference_global_vars_info_t x_global, struct cgraph_node *x)
302 {
303   struct cgraph_edge *e;
304   for (e = x->callees; e; e = e->next_callee)
305     {
306       struct cgraph_node *y = e->callee;
307
308       /* Only look into nodes we can propagate something.  */
309       if (cgraph_function_body_availability (e->callee) > AVAIL_OVERWRITABLE)
310         {
311           if (get_reference_vars_info (y))
312             {
313               ipa_reference_vars_info_t y_info
314                 = get_reference_vars_info (y);
315               ipa_reference_global_vars_info_t y_global = &y_info->global;
316
317               /* Calls in current cycle do not have global computed yet.  */
318               if (!y_global->statics_read)
319                 continue;
320
321               if (x_global->statics_read
322                   != all_module_statics)
323                 {
324                   if (y_global->statics_read
325                       == all_module_statics)
326                     {
327                       BITMAP_FREE (x_global->statics_read);
328                       x_global->statics_read
329                         = all_module_statics;
330                     }
331                   /* Skip bitmaps that are pointer equal to node's bitmap
332                      (no reason to spin within the cycle).  */
333                   else if (x_global->statics_read
334                            != y_global->statics_read)
335                     bitmap_ior_into (x_global->statics_read,
336                                      y_global->statics_read);
337                 }
338
339               if (x_global->statics_written
340                   != all_module_statics)
341                 {
342                   if (y_global->statics_written
343                       == all_module_statics)
344                     {
345                       BITMAP_FREE (x_global->statics_written);
346                       x_global->statics_written
347                         = all_module_statics;
348                     }
349                   /* Skip bitmaps that are pointer equal to node's bitmap
350                      (no reason to spin within the cycle).  */
351                   else if (x_global->statics_written
352                            != y_global->statics_written)
353                     bitmap_ior_into (x_global->statics_written,
354                                      y_global->statics_written);
355                 }
356             }
357           else
358             gcc_unreachable ();
359         }
360     }
361 }
362
363 /* The init routine for analyzing global static variable usage.  See
364    comments at top for description.  */
365 static void
366 ipa_init (void)
367 {
368   static bool init_p = false;
369
370   if (init_p)
371     return;
372
373   init_p = true;
374
375   if (dump_file)
376     reference_vars_to_consider = splay_tree_new (splay_tree_compare_ints, 0, 0);
377
378   bitmap_obstack_initialize (&local_info_obstack);
379   bitmap_obstack_initialize (&optimization_summary_obstack);
380   all_module_statics = BITMAP_ALLOC (&local_info_obstack);
381
382   node_removal_hook_holder =
383       cgraph_add_node_removal_hook (&remove_node_data, NULL);
384   node_duplication_hook_holder =
385       cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
386 }
387
388
389 /* Set up the persistent info for FN.  */
390
391 static ipa_reference_local_vars_info_t
392 init_function_info (struct cgraph_node *fn)
393 {
394   ipa_reference_vars_info_t info
395     = XCNEW (struct ipa_reference_vars_info_d);
396
397   /* Add the info to the tree's annotation.  */
398   set_reference_vars_info (fn, info);
399
400   info->local.statics_read = BITMAP_ALLOC (&local_info_obstack);
401   info->local.statics_written = BITMAP_ALLOC (&local_info_obstack);
402
403   return &info->local;
404 }
405
406
407 /* This is the main routine for finding the reference patterns for
408    global variables within a function FN.  */
409
410 static void
411 analyze_function (struct cgraph_node *fn)
412 {
413   ipa_reference_local_vars_info_t local;
414   struct ipa_ref *ref;
415   int i;
416   tree var;
417   struct cgraph_edge *ie;
418
419   local = init_function_info (fn);
420   /* Process indirect calls.  All direct calles are handled at propagation
421      time.  */
422   for (ie = fn->indirect_calls; ie; ie = ie->next_callee)
423     if (!(ie->indirect_info->ecf_flags & ECF_CONST))
424       {
425         local->calls_read_all = true;
426         if (!(ie->indirect_info->ecf_flags & ECF_PURE)
427             && ((ie->indirect_info->ecf_flags & (ECF_NOTHROW | ECF_NORETURN))
428                 !=  (ECF_NOTHROW | ECF_NORETURN)))
429           local->calls_write_all = true;
430       }
431   for (i = 0; ipa_ref_list_reference_iterate (&fn->ref_list, i, ref); i++)
432     {
433       if (ref->refered_type != IPA_REF_VARPOOL)
434         continue;
435       var = ipa_ref_varpool_node (ref)->decl;
436       if (ipa_ref_varpool_node (ref)->externally_visible
437           || !ipa_ref_varpool_node (ref)->analyzed
438           || !is_proper_for_analysis (var))
439         continue;
440       switch (ref->use)
441         {
442         case IPA_REF_LOAD:
443           bitmap_set_bit (local->statics_read, DECL_UID (var));
444           break;
445         case IPA_REF_STORE:
446           bitmap_set_bit (local->statics_written, DECL_UID (var));
447           break;
448         case IPA_REF_ADDR:
449           break;
450         }
451     }
452
453   if ((flags_from_decl_or_type (fn->decl) & (ECF_NOTHROW | ECF_NORETURN))
454       == (ECF_NOTHROW | ECF_NORETURN))
455     {
456       local->calls_write_all = false;
457       bitmap_clear (local->statics_written);
458     }
459
460   /* Free bitmaps of direct references if we can not use them anyway.  */
461   if (local->calls_write_all)
462     BITMAP_FREE (local->statics_written);
463   if (local->calls_read_all)
464     BITMAP_FREE (local->statics_read);
465 }
466
467 static bitmap
468 copy_global_bitmap (bitmap src)
469 {
470   bitmap dst;
471   if (!src)
472     return NULL;
473   dst = BITMAP_ALLOC (&optimization_summary_obstack);
474   bitmap_copy (dst, src);
475   return dst;
476 }
477
478
479 /* Called when new clone is inserted to callgraph late.  */
480
481 static void
482 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
483                      void *data ATTRIBUTE_UNUSED)
484 {
485   ipa_reference_optimization_summary_t ginfo;
486   ipa_reference_optimization_summary_t dst_ginfo;
487
488   ginfo = get_reference_optimization_summary (src);
489   if (!ginfo)
490     return;
491   dst_ginfo = XCNEW (struct ipa_reference_optimization_summary_d);
492   set_reference_optimization_summary (dst, dst_ginfo);
493   dst_ginfo->statics_not_read = copy_global_bitmap (ginfo->statics_not_read);
494   dst_ginfo->statics_not_written = copy_global_bitmap (ginfo->statics_not_written);
495 }
496
497 /* Called when node is removed.  */
498
499 static void
500 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
501 {
502   ipa_reference_optimization_summary_t ginfo;
503   ginfo = get_reference_optimization_summary (node);
504   if (ginfo)
505     {
506       if (ginfo->statics_not_read
507           && ginfo->statics_not_read != all_module_statics)
508         BITMAP_FREE (ginfo->statics_not_read);
509
510       if (ginfo->statics_not_written
511           && ginfo->statics_not_written != all_module_statics)
512         BITMAP_FREE (ginfo->statics_not_written);
513       free (ginfo);
514       set_reference_optimization_summary (node, NULL);
515     }
516 }
517
518 /* Analyze each function in the cgraph to see which global or statics
519    are read or written.  */
520
521 static void
522 generate_summary (void)
523 {
524   struct cgraph_node *node;
525   unsigned int index;
526   bitmap_iterator bi;
527   bitmap bm_temp;
528
529   ipa_init ();
530   bm_temp = BITMAP_ALLOC (&local_info_obstack);
531
532   /* Process all of the functions next.  */
533   for (node = cgraph_nodes; node; node = node->next)
534     if (node->analyzed)
535       analyze_function (node);
536
537   if (dump_file)
538     EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
539       {
540         fprintf (dump_file, "\nPromotable global:%s",
541                  get_static_name (index));
542       }
543
544   BITMAP_FREE(bm_temp);
545
546   if (dump_file)
547     for (node = cgraph_nodes; node; node = node->next)
548       if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
549         {
550           ipa_reference_local_vars_info_t l;
551           unsigned int index;
552           bitmap_iterator bi;
553
554           l = &get_reference_vars_info (node)->local;
555           fprintf (dump_file,
556                    "\nFunction name:%s/%i:",
557                    cgraph_node_name (node), node->uid);
558           fprintf (dump_file, "\n  locals read: ");
559           if (l->statics_read)
560             EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
561                                       0, index, bi)
562               {
563                 fprintf (dump_file, "%s ",
564                          get_static_name (index));
565               }
566           fprintf (dump_file, "\n  locals written: ");
567           if (l->statics_written)
568             EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
569                                       0, index, bi)
570               {
571                 fprintf(dump_file, "%s ",
572                         get_static_name (index));
573               }
574           if (l->calls_read_all)
575              fprintf (dump_file, "\n  calls read all: ");
576           if (l->calls_write_all)
577              fprintf (dump_file, "\n  calls read all: ");
578         }
579 }
580 \f
581 /* Set READ_ALL/WRITE_ALL based on DECL flags.  */
582
583 static void
584 read_write_all_from_decl (tree decl, bool * read_all, bool * write_all)
585 {
586   int flags = flags_from_decl_or_type (decl);
587   if (flags & ECF_CONST)
588     ;
589   else if (flags & ECF_PURE)
590     *read_all = true;
591   else
592     {
593        /* TODO: To be able to produce sane results, we should also handle
594           common builtins, in particular throw.  */
595       *read_all = true;
596       /* When function does not return, it is safe to ignore anythign it writes
597          to, because the effect will never happen.  */
598       if ((flags & (ECF_NOTHROW | ECF_NORETURN))
599           != (ECF_NOTHROW | ECF_NORETURN))
600         *write_all = true;
601     }
602 }
603
604 /* Produce the global information by preforming a transitive closure
605    on the local information that was produced by ipa_analyze_function */
606
607 static unsigned int
608 propagate (void)
609 {
610   struct cgraph_node *node;
611   struct cgraph_node *w;
612   struct cgraph_node **order =
613     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
614   int order_pos = ipa_utils_reduced_inorder (order, false, true, NULL);
615   int i;
616
617   if (dump_file)
618     dump_cgraph (dump_file);
619
620   ipa_discover_readonly_nonaddressable_vars ();
621   generate_summary ();
622
623   /* Propagate the local information thru the call graph to produce
624      the global information.  All the nodes within a cycle will have
625      the same info so we collapse cycles first.  Then we can do the
626      propagation in one pass from the leaves to the roots.  */
627   order_pos = ipa_utils_reduced_inorder (order, true, true, NULL);
628   if (dump_file)
629     ipa_utils_print_order(dump_file, "reduced", order, order_pos);
630
631   for (i = 0; i < order_pos; i++ )
632     {
633       ipa_reference_vars_info_t node_info;
634       ipa_reference_global_vars_info_t node_g;
635       ipa_reference_local_vars_info_t node_l;
636       struct cgraph_edge *e;
637
638       bool read_all;
639       bool write_all;
640       struct ipa_dfs_info * w_info;
641
642       node = order[i];
643       node_info = get_reference_vars_info (node);
644       if (!node_info)
645         {
646           dump_cgraph_node (stderr, node);
647           dump_cgraph (stderr);
648           gcc_unreachable ();
649         }
650
651       node_l = &node_info->local;
652       node_g = &node_info->global;
653
654       read_all = node_l->calls_read_all;
655       write_all = node_l->calls_write_all;
656
657       /* When function is overwrittable, we can not assume anything.  */
658       if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
659         read_write_all_from_decl (node->decl, &read_all, &write_all);
660
661       for (e = node->callees; e; e = e->next_callee)
662         if (cgraph_function_body_availability (e->callee) <= AVAIL_OVERWRITABLE)
663           read_write_all_from_decl (e->callee->decl, &read_all, &write_all);
664
665
666       /* If any node in a cycle is calls_read_all or calls_write_all
667          they all are. */
668       w_info = (struct ipa_dfs_info *) node->aux;
669       w = w_info->next_cycle;
670       while (w)
671         {
672           ipa_reference_local_vars_info_t w_l =
673             &get_reference_vars_info (w)->local;
674
675           /* When function is overwrittable, we can not assume anything.  */
676           if (cgraph_function_body_availability (w) <= AVAIL_OVERWRITABLE)
677             read_write_all_from_decl (w->decl, &read_all, &write_all);
678
679           for (e = w->callees; e; e = e->next_callee)
680             if (cgraph_function_body_availability (e->callee) <= AVAIL_OVERWRITABLE)
681               read_write_all_from_decl (e->callee->decl, &read_all, &write_all);
682
683           read_all |= w_l->calls_read_all;
684           write_all |= w_l->calls_write_all;
685
686           w_info = (struct ipa_dfs_info *) w->aux;
687           w = w_info->next_cycle;
688         }
689
690
691       /* Initialized the bitmaps for the reduced nodes */
692       if (read_all)
693         node_g->statics_read = all_module_statics;
694       else
695         {
696           node_g->statics_read = BITMAP_ALLOC (&local_info_obstack);
697           bitmap_copy (node_g->statics_read,
698                        node_l->statics_read);
699         }
700       if (write_all)
701         node_g->statics_written = all_module_statics;
702       else
703         {
704           node_g->statics_written = BITMAP_ALLOC (&local_info_obstack);
705           bitmap_copy (node_g->statics_written,
706                        node_l->statics_written);
707         }
708
709       propagate_bits (node_g, node);
710       w_info = (struct ipa_dfs_info *) node->aux;
711       w = w_info->next_cycle;
712       while (w)
713         {
714           ipa_reference_vars_info_t w_ri =
715             get_reference_vars_info (w);
716           ipa_reference_local_vars_info_t w_l = &w_ri->local;
717
718           /* These global bitmaps are initialized from the local info
719              of all of the nodes in the region.  However there is no
720              need to do any work if the bitmaps were set to
721              all_module_statics.  */
722           if (!read_all)
723             bitmap_ior_into (node_g->statics_read,
724                              w_l->statics_read);
725           if (!write_all)
726             bitmap_ior_into (node_g->statics_written,
727                              w_l->statics_written);
728           propagate_bits (node_g, w);
729           w_info = (struct ipa_dfs_info *) w->aux;
730           w = w_info->next_cycle;
731         }
732
733       /* All nodes within a cycle have the same global info bitmaps.  */
734       node_info->global = *node_g;
735       w_info = (struct ipa_dfs_info *) node->aux;
736       w = w_info->next_cycle;
737       while (w)
738         {
739           ipa_reference_vars_info_t w_ri =
740             get_reference_vars_info (w);
741
742           w_ri->global = *node_g;
743
744           w_info = (struct ipa_dfs_info *) w->aux;
745           w = w_info->next_cycle;
746         }
747     }
748
749   if (dump_file)
750     {
751       for (i = 0; i < order_pos; i++ )
752         {
753           ipa_reference_vars_info_t node_info;
754           ipa_reference_global_vars_info_t node_g;
755           ipa_reference_local_vars_info_t node_l;
756           unsigned int index;
757           bitmap_iterator bi;
758           struct ipa_dfs_info * w_info;
759
760           node = order[i];
761           node_info = get_reference_vars_info (node);
762           node_g = &node_info->global;
763           node_l = &node_info->local;
764           fprintf (dump_file,
765                    "\nFunction name:%s/%i:",
766                    cgraph_node_name (node), node->uid);
767           fprintf (dump_file, "\n  locals read: ");
768           if (node_l->statics_read)
769             EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read,
770                                       0, index, bi)
771               {
772                 fprintf (dump_file, "%s ",
773                          get_static_name (index));
774               }
775           fprintf (dump_file, "\n  locals written: ");
776           if (node_l->statics_written)
777             EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written,
778                                       0, index, bi)
779               {
780                 fprintf(dump_file, "%s ",
781                         get_static_name (index));
782               }
783
784           w_info = (struct ipa_dfs_info *) node->aux;
785           w = w_info->next_cycle;
786           while (w)
787             {
788               ipa_reference_vars_info_t w_ri =
789                 get_reference_vars_info (w);
790               ipa_reference_local_vars_info_t w_l = &w_ri->local;
791               fprintf (dump_file, "\n  next cycle: %s/%i ",
792                        cgraph_node_name (w), w->uid);
793               fprintf (dump_file, "\n    locals read: ");
794               if (w_l->statics_read)
795                 EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read,
796                                           0, index, bi)
797                   {
798                     fprintf (dump_file, "%s ",
799                              get_static_name (index));
800                   }
801
802               fprintf (dump_file, "\n    locals written: ");
803               if (w_l->statics_written)
804                 EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written,
805                                           0, index, bi)
806                   {
807                     fprintf (dump_file, "%s ",
808                              get_static_name (index));
809                   }
810
811               w_info = (struct ipa_dfs_info *) w->aux;
812               w = w_info->next_cycle;
813             }
814           fprintf (dump_file, "\n  globals read: ");
815           if (node_g->statics_read == all_module_statics)
816             fprintf (dump_file, "ALL");
817           else
818             EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read,
819                                       0, index, bi)
820               {
821                 fprintf (dump_file, "%s ",
822                          get_static_name (index));
823               }
824           fprintf (dump_file, "\n  globals written: ");
825           if (node_g->statics_written == all_module_statics)
826             fprintf (dump_file, "ALL");
827           else
828             EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written,
829                                       0, index, bi)
830               {
831                 fprintf (dump_file, "%s ",
832                          get_static_name (index));
833               }
834         }
835     }
836
837   /* Cleanup. */
838   for (node = cgraph_nodes; node; node = node->next)
839     {
840       ipa_reference_vars_info_t node_info;
841       ipa_reference_global_vars_info_t node_g;
842       ipa_reference_optimization_summary_t opt;
843
844       if (!node->analyzed)
845         continue;
846
847       node_info = get_reference_vars_info (node);
848       if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
849         {
850           node_g = &node_info->global;
851
852           opt = XCNEW (struct ipa_reference_optimization_summary_d);
853           set_reference_optimization_summary (node, opt);
854
855           /* Create the complimentary sets.  */
856           opt->statics_not_read = BITMAP_ALLOC (&optimization_summary_obstack);
857           opt->statics_not_written = BITMAP_ALLOC (&optimization_summary_obstack);
858
859           if (node_g->statics_read != all_module_statics)
860             bitmap_and_compl (opt->statics_not_read,
861                               all_module_statics,
862                               node_g->statics_read);
863
864           if (node_g->statics_written
865               != all_module_statics)
866             bitmap_and_compl (opt->statics_not_written,
867                               all_module_statics,
868                               node_g->statics_written);
869         }
870       if (node_info)
871         free (node_info);
872       if (node->aux)
873         {
874           free (node->aux);
875           node->aux = NULL;
876         }
877    }
878
879   free (order);
880
881   bitmap_obstack_release (&local_info_obstack);
882   VEC_free (ipa_reference_vars_info_t, heap, ipa_reference_vars_vector);
883   ipa_reference_vars_vector = NULL;
884   if (dump_file)
885     splay_tree_delete (reference_vars_to_consider);
886   reference_vars_to_consider = NULL;
887   all_module_statics = NULL;
888   return 0;
889 }
890
891 /* Return true if we need to write summary of NODE. */
892
893 static bool
894 write_node_summary_p (struct cgraph_node *node,
895                       cgraph_node_set set,
896                       varpool_node_set vset,
897                       bitmap ltrans_statics)
898 {
899   ipa_reference_optimization_summary_t info;
900
901   /* See if we have (non-empty) info.  */
902   if (!node->analyzed || node->global.inlined_to)
903     return false;
904   info = get_reference_optimization_summary (node);
905   if (!info || (bitmap_empty_p (info->statics_not_read)
906                 && bitmap_empty_p (info->statics_not_written)))
907     return false;
908
909   /* See if we want to encode it.
910      Encode also referenced functions since constant folding might turn it into
911      a direct call.
912
913      In future we might also want to include summaries of functions references
914      by initializers of constant variables references in current unit.  */
915   if (!reachable_from_this_partition_p (node, set)
916       && !referenced_from_this_partition_p (&node->ref_list, set, vset))
917     return false;
918
919   /* See if the info has non-empty intersections with vars we want to encode.  */
920   if (!bitmap_intersect_p (info->statics_not_read, ltrans_statics)
921       && !bitmap_intersect_p (info->statics_not_written, ltrans_statics))
922     return false;
923   return true;
924 }
925
926 /* Stream out BITS&LTRANS_STATICS as list of decls to OB.  */
927
928 static void
929 stream_out_bitmap (struct lto_simple_output_block *ob,
930                    bitmap bits, bitmap ltrans_statics)
931 {
932   unsigned int count = 0;
933   unsigned int index;
934   bitmap_iterator bi;
935   EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
936     count ++;
937   lto_output_uleb128_stream (ob->main_stream, count);
938   if (!count)
939     return;
940   EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
941     {
942       tree decl = (tree)splay_tree_lookup (reference_vars_to_consider, index)->value;
943       lto_output_var_decl_index(ob->decl_state, ob->main_stream, decl);
944     }
945 }
946
947 /* Serialize the ipa info for lto.  */
948
949 static void
950 ipa_reference_write_optimization_summary (cgraph_node_set set,
951                                           varpool_node_set vset)
952 {
953   struct cgraph_node *node;
954   struct varpool_node *vnode;
955   struct lto_simple_output_block *ob
956     = lto_create_simple_output_block (LTO_section_ipa_reference);
957   unsigned int count = 0;
958   lto_cgraph_encoder_t encoder = ob->decl_state->cgraph_node_encoder;
959   bitmap ltrans_statics = BITMAP_ALLOC (NULL);
960
961   reference_vars_to_consider = splay_tree_new (splay_tree_compare_ints, 0, 0);
962
963   /* See what variables we are interested in.  */
964   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
965     if (referenced_from_this_partition_p (&vnode->ref_list, set, vset))
966       {
967         tree decl = vnode->decl;
968         if (is_proper_for_analysis (decl))
969           {
970             bitmap_set_bit (ltrans_statics, DECL_UID (decl));
971             splay_tree_insert (reference_vars_to_consider,
972                                DECL_UID (decl), (splay_tree_value)decl);
973           }
974       }
975
976   for (node = cgraph_nodes; node; node = node->next)
977     if (write_node_summary_p (node, set, vset, ltrans_statics))
978         count++;
979
980   lto_output_uleb128_stream (ob->main_stream, count);
981
982   /* Process all of the functions.  */
983   for (node = cgraph_nodes; node; node = node->next)
984     if (write_node_summary_p (node, set, vset, ltrans_statics))
985       {
986         ipa_reference_optimization_summary_t info;
987         int node_ref;
988
989         info = get_reference_optimization_summary (node);
990         node_ref = lto_cgraph_encoder_encode (encoder, node);
991         lto_output_uleb128_stream (ob->main_stream, node_ref);
992
993         stream_out_bitmap (ob, info->statics_not_read, ltrans_statics);
994         stream_out_bitmap (ob, info->statics_not_written, ltrans_statics);
995       }
996   BITMAP_FREE (ltrans_statics);
997   lto_destroy_simple_output_block (ob);
998   splay_tree_delete (reference_vars_to_consider);
999 }
1000
1001 /* Deserialize the ipa info for lto.  */
1002
1003 static void
1004 ipa_reference_read_optimization_summary (void)
1005 {
1006   struct lto_file_decl_data ** file_data_vec
1007     = lto_get_file_decl_data ();
1008   struct lto_file_decl_data * file_data;
1009   unsigned int j = 0;
1010   bitmap_obstack_initialize (&optimization_summary_obstack);
1011
1012   node_removal_hook_holder =
1013       cgraph_add_node_removal_hook (&remove_node_data, NULL);
1014   node_duplication_hook_holder =
1015       cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
1016
1017   while ((file_data = file_data_vec[j++]))
1018     {
1019       const char *data;
1020       size_t len;
1021       struct lto_input_block *ib
1022         = lto_create_simple_input_block (file_data,
1023                                          LTO_section_ipa_reference,
1024                                          &data, &len);
1025       if (ib)
1026         {
1027           unsigned int i;
1028           unsigned int f_count = lto_input_uleb128 (ib);
1029
1030           for (i = 0; i < f_count; i++)
1031             {
1032               unsigned int j, index;
1033               struct cgraph_node *node;
1034               ipa_reference_optimization_summary_t info;
1035               int v_count;
1036               lto_cgraph_encoder_t encoder;
1037
1038               index = lto_input_uleb128 (ib);
1039               encoder = file_data->cgraph_node_encoder;
1040               node = lto_cgraph_encoder_deref (encoder, index);
1041               info = XCNEW (struct ipa_reference_optimization_summary_d);
1042               set_reference_optimization_summary (node, info);
1043               info->statics_not_read = BITMAP_ALLOC (&optimization_summary_obstack);
1044               info->statics_not_written = BITMAP_ALLOC (&optimization_summary_obstack);
1045               if (dump_file)
1046                 fprintf (dump_file,
1047                          "\nFunction name:%s/%i:\n  static not read:",
1048                          cgraph_node_name (node), node->uid);
1049
1050               /* Set the statics not read.  */
1051               v_count = lto_input_uleb128 (ib);
1052               for (j = 0; j < (unsigned int)v_count; j++)
1053                 {
1054                   unsigned int var_index = lto_input_uleb128 (ib);
1055                   tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1056                                                                  var_index);
1057                   bitmap_set_bit (info->statics_not_read, DECL_UID (v_decl));
1058                   if (dump_file)
1059                     fprintf (dump_file, " %s",
1060                              lang_hooks.decl_printable_name (v_decl, 2));
1061                 }
1062
1063               if (dump_file)
1064                 fprintf (dump_file,
1065                          "\n  static not written:");
1066               /* Set the statics not written.  */
1067               v_count = lto_input_uleb128 (ib);
1068               for (j = 0; j < (unsigned int)v_count; j++)
1069                 {
1070                   unsigned int var_index = lto_input_uleb128 (ib);
1071                   tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1072                                                                  var_index);
1073                   bitmap_set_bit (info->statics_not_written, DECL_UID (v_decl));
1074                   if (dump_file)
1075                     fprintf (dump_file, " %s",
1076                              lang_hooks.decl_printable_name (v_decl, 2));
1077                 }
1078               if (dump_file)
1079                 fprintf (dump_file, "\n");
1080             }
1081
1082           lto_destroy_simple_input_block (file_data,
1083                                           LTO_section_ipa_reference,
1084                                           ib, data, len);
1085         }
1086       else
1087         /* Fatal error here.  We do not want to support compiling ltrans units with
1088            different version of compiler or different flags than the WPA unit, so
1089            this should never happen.  */
1090         fatal_error ("ipa reference summary is missing in ltrans unit");
1091     }
1092 }
1093
1094 static bool
1095 gate_reference (void)
1096 {
1097   return (flag_ipa_reference
1098           /* Don't bother doing anything if the program has errors.  */
1099           && !(errorcount || sorrycount));
1100 }
1101
1102 struct ipa_opt_pass_d pass_ipa_reference =
1103 {
1104  {
1105   IPA_PASS,
1106   "static-var",                         /* name */
1107   gate_reference,                       /* gate */
1108   propagate,                            /* execute */
1109   NULL,                                 /* sub */
1110   NULL,                                 /* next */
1111   0,                                    /* static_pass_number */
1112   TV_IPA_REFERENCE,                     /* tv_id */
1113   0,                                    /* properties_required */
1114   0,                                    /* properties_provided */
1115   0,                                    /* properties_destroyed */
1116   0,                                    /* todo_flags_start */
1117   0                                     /* todo_flags_finish */
1118  },
1119  NULL,                                  /* generate_summary */
1120  NULL,                                  /* write_summary */
1121  NULL,                                  /* read_summary */
1122  ipa_reference_write_optimization_summary,/* write_optimization_summary */
1123  ipa_reference_read_optimization_summary,/* read_optimization_summary */
1124  NULL,                                  /* stmt_fixup */
1125  0,                                     /* TODOs */
1126  NULL,                                  /* function_transform */
1127  NULL                                   /* variable_transform */
1128 };