OSDN Git Service

3180a9d0209986fb2139d7929dc740ee1201b755
[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
63 static void remove_node_data (struct cgraph_node *node,
64                               void *data ATTRIBUTE_UNUSED);
65 static void duplicate_node_data (struct cgraph_node *src,
66                                  struct cgraph_node *dst,
67                                  void *data ATTRIBUTE_UNUSED);
68
69 /* The static variables defined within the compilation unit that are
70    loaded or stored directly by function that owns this structure.  */
71
72 struct ipa_reference_local_vars_info_d
73 {
74   bitmap statics_read;
75   bitmap statics_written;
76
77   /* Set when this function calls another function external to the
78      compilation unit or if the function has a asm clobber of memory.
79      In general, such calls are modeled as reading and writing all
80      variables (both bits on) but sometime there are attributes on the
81      called function so we can do better.  */
82   bool calls_read_all;
83   bool calls_write_all;
84 };
85
86 /* Statics that are read and written by some set of functions. The
87    local ones are based on the loads and stores local to the function.
88    The global ones are based on the local info as well as the
89    transitive closure of the functions that are called.  The
90    structures are separated to allow the global structures to be
91    shared between several functions since every function within a
92    strongly connected component will have the same information.  This
93    sharing saves both time and space in the computation of the vectors
94    as well as their translation from decl_uid form to ann_uid
95    form.  */
96
97 struct ipa_reference_global_vars_info_d
98 {
99   bitmap statics_read;
100   bitmap statics_written;
101   bitmap statics_not_read;
102   bitmap statics_not_written;
103 };
104
105 typedef struct ipa_reference_local_vars_info_d *ipa_reference_local_vars_info_t;
106 typedef struct ipa_reference_global_vars_info_d *ipa_reference_global_vars_info_t;
107 struct ipa_reference_vars_info_d
108 {
109   ipa_reference_local_vars_info_t local;
110   ipa_reference_global_vars_info_t global;
111 };
112
113 typedef struct ipa_reference_vars_info_d *ipa_reference_vars_info_t;
114
115 /* This splay tree contains all of the static variables that are
116    being considered by the compilation level alias analysis.  For
117    module_at_a_time compilation, this is the set of static but not
118    public variables.  Any variables that either have their address
119    taken or participate in otherwise unsavory operations are deleted
120    from this list.  */
121 static GTY((param1_is(int), param2_is(tree)))
122      splay_tree reference_vars_to_consider;
123
124 /* This bitmap is used to knock out the module static variables whose
125    addresses have been taken and passed around.  */
126 static bitmap module_statics_escape;
127
128 /* A bit is set for every module static we are considering.  This is
129    ored into the local info when asm code is found that clobbers all
130    memory. */
131 static bitmap all_module_statics;
132
133 /* Obstack holding bitmaps of local analysis (live from analysis to
134    propagation)  */
135 static bitmap_obstack local_info_obstack;
136 /* Obstack holding global analysis live forever.  */
137 static bitmap_obstack global_info_obstack;
138
139 /* Holders of ipa cgraph hooks: */
140 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
141 static struct cgraph_node_hook_list *node_removal_hook_holder;
142
143 enum initialization_status_t
144 {
145   UNINITIALIZED,
146   RUNNING,
147   FINISHED
148 };
149
150 tree memory_identifier_string;
151
152 /* Vector where the reference var infos are actually stored. */
153 DEF_VEC_P (ipa_reference_vars_info_t);
154 DEF_VEC_ALLOC_P (ipa_reference_vars_info_t, heap);
155 static VEC (ipa_reference_vars_info_t, heap) *ipa_reference_vars_vector;
156
157 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
158 static inline ipa_reference_vars_info_t
159 get_reference_vars_info (struct cgraph_node *node)
160 {
161   if (!ipa_reference_vars_vector
162       || VEC_length (ipa_reference_vars_info_t, ipa_reference_vars_vector) <= (unsigned int)node->uid)
163     return NULL;
164   return VEC_index (ipa_reference_vars_info_t, ipa_reference_vars_vector, node->uid);
165 }
166
167 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
168 static inline void
169 set_reference_vars_info (struct cgraph_node *node, ipa_reference_vars_info_t info)
170 {
171   if (!ipa_reference_vars_vector
172       || VEC_length (ipa_reference_vars_info_t, ipa_reference_vars_vector) <= (unsigned int)node->uid)
173      VEC_safe_grow_cleared (ipa_reference_vars_info_t, heap, ipa_reference_vars_vector, node->uid + 1);
174   VEC_replace (ipa_reference_vars_info_t, ipa_reference_vars_vector, node->uid, info);
175 }
176
177 /* Get a bitmap that contains all of the globally referenced static
178    variables for function FN.  */
179
180 static ipa_reference_global_vars_info_t
181 get_global_reference_vars_info (struct cgraph_node *fn)
182 {
183   ipa_reference_vars_info_t info = get_reference_vars_info (fn);
184
185   if (info)
186     return info->global;
187   else
188     /* This phase was not run.  */
189     return NULL;
190 }
191
192 /* Return a bitmap indexed by VAR_DECL uid for the static variables
193    that are read during the execution of the function FN.  Returns
194    NULL if no data is available.  */
195
196 bitmap
197 ipa_reference_get_read_global (struct cgraph_node *fn)
198 {
199   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
200   if (g)
201     return g->statics_read;
202   else
203     return NULL;
204 }
205
206 /* Return a bitmap indexed by VAR_DECL uid for the static variables
207    that are written during the execution of the function FN.  Note
208    that variables written may or may not be read during the function
209    call.  Returns NULL if no data is available.  */
210
211 bitmap
212 ipa_reference_get_written_global (struct cgraph_node *fn)
213 {
214   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
215   if (g)
216     return g->statics_written;
217   else
218     return NULL;
219 }
220
221 /* Return a bitmap indexed by_DECL_UID uid for the static variables
222    that are not read during the execution of the function FN.  Returns
223    NULL if no data is available.  */
224
225 bitmap
226 ipa_reference_get_not_read_global (struct cgraph_node *fn)
227 {
228   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
229   if (g)
230     return g->statics_not_read;
231   else
232     return NULL;
233 }
234
235 /* Return a bitmap indexed by DECL_UID uid for the static variables
236    that are not written during the execution of the function FN.  Note
237    that variables written may or may not be read during the function
238    call.  Returns NULL if no data is available.  */
239
240 bitmap
241 ipa_reference_get_not_written_global (struct cgraph_node *fn)
242 {
243   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
244   if (g)
245     return g->statics_not_written;
246   else
247     return NULL;
248 }
249
250 \f
251
252 /* Add VAR to all_module_statics and the two
253    reference_vars_to_consider* sets.  */
254
255 static inline void
256 add_static_var (tree var)
257 {
258   int uid = DECL_UID (var);
259   gcc_assert (TREE_CODE (var) == VAR_DECL);
260   if (!bitmap_bit_p (all_module_statics, uid))
261     {
262       splay_tree_insert (reference_vars_to_consider,
263                          uid, (splay_tree_value)var);
264       bitmap_set_bit (all_module_statics, uid);
265     }
266 }
267
268 /* Return true if the variable T is the right kind of static variable to
269    perform compilation unit scope escape analysis.  */
270
271 static inline bool
272 is_proper_for_analysis (tree t)
273 {
274   /* If the variable has the "used" attribute, treat it as if it had a
275      been touched by the devil.  */
276   if (DECL_PRESERVE_P (t))
277     return false;
278
279   /* Do not want to do anything with volatile except mark any
280      function that uses one to be not const or pure.  */
281   if (TREE_THIS_VOLATILE (t))
282     return false;
283
284   /* We cannot touch decls where the type needs constructing.  */
285   if (TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t)))
286     return false;
287
288   /* This is a variable we care about.  Check if we have seen it
289      before, and if not add it the set of variables we care about.  */
290   if (!bitmap_bit_p (all_module_statics, DECL_UID (t)))
291     add_static_var (t);
292
293   return true;
294 }
295
296 /* Lookup the tree node for the static variable that has UID and
297    convert the name to a string for debugging.  */
298
299 static const char *
300 get_static_name (int index)
301 {
302   splay_tree_node stn =
303     splay_tree_lookup (reference_vars_to_consider, index);
304   if (stn)
305     return lang_hooks.decl_printable_name ((tree)(stn->value), 2);
306   return NULL;
307 }
308
309 /* Or in all of the bits from every callee of X into X_GLOBAL, the caller's cycle,
310    bit vector.  There are several cases to check to avoid the sparse
311    bitmap oring.  */
312
313 static void
314 propagate_bits (ipa_reference_global_vars_info_t x_global, struct cgraph_node *x)
315 {
316   struct cgraph_edge *e;
317   for (e = x->callees; e; e = e->next_callee)
318     {
319       struct cgraph_node *y = e->callee;
320
321       /* Only look into nodes we can propagate something.  */
322       if (cgraph_function_body_availability (e->callee) > AVAIL_OVERWRITABLE)
323         {
324           if (get_reference_vars_info (y))
325             {
326               ipa_reference_vars_info_t y_info
327                 = get_reference_vars_info (y);
328               ipa_reference_global_vars_info_t y_global = y_info->global;
329
330               /* Calls in current cycle do not have global computed yet.  */
331               if (!y_info->global)
332                 continue;
333
334               if (x_global->statics_read
335                   != all_module_statics)
336                 {
337                   if (y_global->statics_read
338                       == all_module_statics)
339                     {
340                       BITMAP_FREE (x_global->statics_read);
341                       x_global->statics_read
342                         = all_module_statics;
343                     }
344                   /* Skip bitmaps that are pointer equal to node's bitmap
345                      (no reason to spin within the cycle).  */
346                   else if (x_global->statics_read
347                            != y_global->statics_read)
348                     bitmap_ior_into (x_global->statics_read,
349                                      y_global->statics_read);
350                 }
351
352               if (x_global->statics_written
353                   != all_module_statics)
354                 {
355                   if (y_global->statics_written
356                       == all_module_statics)
357                     {
358                       BITMAP_FREE (x_global->statics_written);
359                       x_global->statics_written
360                         = all_module_statics;
361                     }
362                   /* Skip bitmaps that are pointer equal to node's bitmap
363                      (no reason to spin within the cycle).  */
364                   else if (x_global->statics_written
365                            != y_global->statics_written)
366                     bitmap_ior_into (x_global->statics_written,
367                                      y_global->statics_written);
368                 }
369             }
370           else
371             gcc_unreachable ();
372         }
373     }
374 }
375
376 /* The init routine for analyzing global static variable usage.  See
377    comments at top for description.  */
378 static void
379 ipa_init (void)
380 {
381   static bool init_p = false;
382
383   if (init_p)
384     return;
385
386   init_p = true;
387
388   memory_identifier_string = build_string(7, "memory");
389
390   reference_vars_to_consider =
391     splay_tree_new_ggc (splay_tree_compare_ints);
392
393   bitmap_obstack_initialize (&local_info_obstack);
394   bitmap_obstack_initialize (&global_info_obstack);
395   module_statics_escape = BITMAP_ALLOC (&local_info_obstack);
396   all_module_statics = BITMAP_ALLOC (&global_info_obstack);
397
398   node_removal_hook_holder =
399       cgraph_add_node_removal_hook (&remove_node_data, NULL);
400   node_duplication_hook_holder =
401       cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
402 }
403
404 /* Check out the rhs of a static or global initialization VNODE to see
405    if any of them contain addressof operations.  Note that some of
406    these variables may  not even be referenced in the code in this
407    compilation unit but their right hand sides may contain references
408    to variables defined within this unit.  */
409
410 static void
411 analyze_variable (struct varpool_node *vnode)
412 {
413   int i;
414   struct ipa_ref *ref;
415   for (i = 0; ipa_ref_list_reference_iterate (&vnode->ref_list, i, ref); i++)
416     {
417       tree var;
418       if (ref->refered_type != IPA_REF_VARPOOL)
419         continue;
420       var = ipa_ref_varpool_node (ref)->decl;
421       if (ipa_ref_varpool_node (ref)->externally_visible
422           || !ipa_ref_varpool_node (ref)->analyzed
423           || !is_proper_for_analysis (var))
424         continue;
425       switch (ref->use)
426         {
427         case IPA_REF_LOAD:
428         case IPA_REF_STORE:
429           gcc_unreachable ();
430           break;
431         case IPA_REF_ADDR:
432           bitmap_set_bit (module_statics_escape, DECL_UID (var));
433           break;
434         }
435     }
436 }
437
438
439 /* Set up the persistent info for FN.  */
440
441 static ipa_reference_local_vars_info_t
442 init_function_info (struct cgraph_node *fn)
443 {
444   ipa_reference_vars_info_t info
445     = XCNEW (struct ipa_reference_vars_info_d);
446   ipa_reference_local_vars_info_t l
447     = XCNEW (struct ipa_reference_local_vars_info_d);
448
449   /* Add the info to the tree's annotation.  */
450   set_reference_vars_info (fn, info);
451
452   info->local = l;
453   l->statics_read = BITMAP_ALLOC (&local_info_obstack);
454   l->statics_written = BITMAP_ALLOC (&local_info_obstack);
455
456   return l;
457 }
458
459
460 /* This is the main routine for finding the reference patterns for
461    global variables within a function FN.  */
462
463 static void
464 analyze_function (struct cgraph_node *fn)
465 {
466   ipa_reference_local_vars_info_t local;
467   struct ipa_ref *ref;
468   int i;
469   tree var;
470   struct cgraph_edge *ie;
471
472   local = init_function_info (fn);
473   /* Process indirect calls.  All direct calles are handled at propagation
474      time.  */
475   for (ie = fn->indirect_calls; ie; ie = ie->next_callee)
476     if (!(ie->indirect_info->ecf_flags & ECF_CONST))
477       {
478         local->calls_read_all = true;
479         if (!(ie->indirect_info->ecf_flags & ECF_PURE)
480             && ((ie->indirect_info->ecf_flags & (ECF_NOTHROW | ECF_NORETURN))
481                 !=  (ECF_NOTHROW | ECF_NORETURN)))
482           local->calls_write_all = true;
483       }
484   for (i = 0; ipa_ref_list_reference_iterate (&fn->ref_list, i, ref); i++)
485     {
486       if (ref->refered_type != IPA_REF_VARPOOL)
487         continue;
488       var = ipa_ref_varpool_node (ref)->decl;
489       if (ipa_ref_varpool_node (ref)->externally_visible
490           || !ipa_ref_varpool_node (ref)->analyzed
491           || !is_proper_for_analysis (var))
492         continue;
493       switch (ref->use)
494         {
495         case IPA_REF_LOAD:
496           bitmap_set_bit (local->statics_read, DECL_UID (var));
497           break;
498         case IPA_REF_STORE:
499           bitmap_set_bit (local->statics_written, DECL_UID (var));
500           break;
501         case IPA_REF_ADDR:
502           bitmap_set_bit (module_statics_escape, DECL_UID (var));
503           break;
504         }
505     }
506
507   if ((flags_from_decl_or_type (fn->decl) & (ECF_NOTHROW | ECF_NORETURN))
508       == (ECF_NOTHROW | ECF_NORETURN))
509     {
510       local->calls_write_all = false;
511       bitmap_clear (local->statics_written);
512     }
513
514   /* Free bitmaps of direct references if we can not use them anyway.  */
515   if (local->calls_write_all)
516     BITMAP_FREE (local->statics_written);
517   if (local->calls_read_all)
518     BITMAP_FREE (local->statics_read);
519 }
520
521 /* Remove local data associated with function FN.  */
522 static void
523 clean_function_local_data (struct cgraph_node *fn)
524 {
525   ipa_reference_vars_info_t info = get_reference_vars_info (fn);
526   ipa_reference_local_vars_info_t l = info->local;
527   if (l)
528     {
529       if (l->statics_read
530           && l->statics_read != all_module_statics)
531         BITMAP_FREE (l->statics_read);
532       if (l->statics_written
533           &&l->statics_written != all_module_statics)
534         BITMAP_FREE (l->statics_written);
535       free (l);
536       info->local = NULL;
537     }
538 }
539
540 /* Remove all data associated with function FN.  */
541
542 static void
543 clean_function (struct cgraph_node *fn)
544 {
545   ipa_reference_vars_info_t info = get_reference_vars_info (fn);
546   ipa_reference_global_vars_info_t g = info->global;
547
548   clean_function_local_data (fn);
549   if (g)
550     {
551       if (g->statics_read
552           && g->statics_read != all_module_statics)
553         BITMAP_FREE (g->statics_read);
554
555       if (g->statics_written
556           && g->statics_written != all_module_statics)
557         BITMAP_FREE (g->statics_written);
558
559       if (g->statics_not_read
560           && g->statics_not_read != all_module_statics)
561         BITMAP_FREE (g->statics_not_read);
562
563       if (g->statics_not_written
564           && g->statics_not_written != all_module_statics)
565         BITMAP_FREE (g->statics_not_written);
566       free (g);
567       info->global = NULL;
568     }
569
570   free (get_reference_vars_info (fn));
571   set_reference_vars_info (fn, NULL);
572 }
573
574 static bitmap
575 copy_global_bitmap (bitmap src)
576 {
577   bitmap dst;
578   if (!src)
579     return NULL;
580   if (src == all_module_statics)
581     return all_module_statics;
582   dst = BITMAP_ALLOC (&global_info_obstack);
583   bitmap_copy (dst, src);
584   return dst;
585 }
586
587
588 /* Called when new clone is inserted to callgraph late.  */
589
590 static void
591 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
592                      void *data ATTRIBUTE_UNUSED)
593 {
594   ipa_reference_global_vars_info_t ginfo;
595   ipa_reference_global_vars_info_t dst_ginfo;
596
597   ginfo = get_global_reference_vars_info (src);
598   if (!ginfo)
599     return;
600   init_function_info (dst);
601   if (ginfo)
602     {
603       get_reference_vars_info (dst)->global = XCNEW (struct ipa_reference_global_vars_info_d);
604       dst_ginfo = get_global_reference_vars_info (dst);
605       dst_ginfo->statics_read = copy_global_bitmap (ginfo->statics_read);
606       dst_ginfo->statics_written = copy_global_bitmap (ginfo->statics_written);
607       dst_ginfo->statics_not_read = copy_global_bitmap (ginfo->statics_not_read);
608       dst_ginfo->statics_not_written = copy_global_bitmap (ginfo->statics_not_written);
609     }
610 }
611
612 /* Called when node is removed.  */
613
614 static void
615 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
616 {
617   if (get_reference_vars_info (node))
618     clean_function (node);
619 }
620
621 /* Analyze each function in the cgraph to see which global or statics
622    are read or written.  */
623
624 static void
625 generate_summary (void)
626 {
627   struct cgraph_node *node;
628   struct varpool_node *vnode;
629   unsigned int index;
630   bitmap_iterator bi;
631   bitmap bm_temp;
632
633   ipa_init ();
634   bm_temp = BITMAP_ALLOC (&local_info_obstack);
635
636   /* Process all of the variables first.  */
637   FOR_EACH_STATIC_INITIALIZER (vnode)
638     analyze_variable (vnode);
639
640   /* Process all of the functions next.  */
641   for (node = cgraph_nodes; node; node = node->next)
642     if (node->analyzed)
643       analyze_function (node);
644
645   /* Prune out the variables that were found to behave badly
646      (i.e. have their address taken).  */
647   EXECUTE_IF_SET_IN_BITMAP (module_statics_escape, 0, index, bi)
648     {
649       splay_tree_remove (reference_vars_to_consider, index);
650     }
651
652   bitmap_and_compl_into (all_module_statics,
653                          module_statics_escape);
654
655   BITMAP_FREE(module_statics_escape);
656   module_statics_escape = NULL;
657
658   if (dump_file)
659     EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
660       {
661         fprintf (dump_file, "\nPromotable global:%s",
662                  get_static_name (index));
663       }
664
665   for (node = cgraph_nodes; node; node = node->next)
666     if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
667       {
668         ipa_reference_local_vars_info_t l;
669         l = get_reference_vars_info (node)->local;
670
671         /* Any variables that are not in all_module_statics are
672            removed from the local maps.  This will include all of the
673            variables that were found to escape in the function
674            scanning.  */
675         if (l->statics_read)
676           bitmap_and_into (l->statics_read,
677                            all_module_statics);
678         if (l->statics_written)
679           bitmap_and_into (l->statics_written,
680                            all_module_statics);
681       }
682
683   BITMAP_FREE(bm_temp);
684
685   if (dump_file)
686     for (node = cgraph_nodes; node; node = node->next)
687       if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
688         {
689           ipa_reference_local_vars_info_t l;
690           unsigned int index;
691           bitmap_iterator bi;
692
693           l = get_reference_vars_info (node)->local;
694           fprintf (dump_file,
695                    "\nFunction name:%s/%i:",
696                    cgraph_node_name (node), node->uid);
697           fprintf (dump_file, "\n  locals read: ");
698           if (l->statics_read)
699             EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
700                                       0, index, bi)
701               {
702                 fprintf (dump_file, "%s ",
703                          get_static_name (index));
704               }
705           fprintf (dump_file, "\n  locals written: ");
706           if (l->statics_written)
707             EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
708                                       0, index, bi)
709               {
710                 fprintf(dump_file, "%s ",
711                         get_static_name (index));
712               }
713           if (l->calls_read_all)
714              fprintf (dump_file, "\n  calls read all: ");
715           if (l->calls_write_all)
716              fprintf (dump_file, "\n  calls read all: ");
717         }
718 }
719 \f
720 /* Set READ_ALL/WRITE_ALL based on DECL flags.  */
721 static void
722 read_write_all_from_decl (tree decl, bool * read_all, bool * write_all)
723 {
724   int flags = flags_from_decl_or_type (decl);
725   if (flags & ECF_CONST)
726     ;
727   else if (flags & ECF_PURE)
728     *read_all = true;
729   else
730     {
731        /* TODO: To be able to produce sane results, we should also handle
732           common builtins, in particular throw.
733           Indirect calls hsould be only counted and as inliner is replacing them
734           by direct calls, we can conclude if any indirect calls are left in body */
735       *read_all = true;
736       /* When function does not reutrn, it is safe to ignore anythign it writes
737          to, because the effect will never happen.  */
738       if ((flags & (ECF_NOTHROW | ECF_NORETURN))
739           != (ECF_NOTHROW | ECF_NORETURN))
740         *write_all = true;
741     }
742 }
743
744 /* Produce the global information by preforming a transitive closure
745    on the local information that was produced by ipa_analyze_function
746    and ipa_analyze_variable.  */
747
748 static unsigned int
749 propagate (void)
750 {
751   struct cgraph_node *node;
752   struct cgraph_node *w;
753   struct cgraph_node **order =
754     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
755   int order_pos = ipa_utils_reduced_inorder (order, false, true, NULL);
756   int i;
757
758   if (dump_file)
759     dump_cgraph (dump_file);
760
761   generate_summary ();
762
763   /* Propagate the local information thru the call graph to produce
764      the global information.  All the nodes within a cycle will have
765      the same info so we collapse cycles first.  Then we can do the
766      propagation in one pass from the leaves to the roots.  */
767   order_pos = ipa_utils_reduced_inorder (order, true, true, NULL);
768   if (dump_file)
769     ipa_utils_print_order(dump_file, "reduced", order, order_pos);
770
771   for (i = 0; i < order_pos; i++ )
772     {
773       ipa_reference_vars_info_t node_info;
774       ipa_reference_global_vars_info_t node_g =
775         XCNEW (struct ipa_reference_global_vars_info_d);
776       ipa_reference_local_vars_info_t node_l;
777       struct cgraph_edge *e;
778
779       bool read_all;
780       bool write_all;
781       struct ipa_dfs_info * w_info;
782
783       node = order[i];
784       node_info = get_reference_vars_info (node);
785       if (!node_info)
786         {
787           dump_cgraph_node (stderr, node);
788           dump_cgraph (stderr);
789           gcc_unreachable ();
790         }
791
792       gcc_assert (!node_info->global);
793       node_l = node_info->local;
794
795       read_all = node_l->calls_read_all;
796       write_all = node_l->calls_write_all;
797
798       /* When function is overwrittable, we can not assume anything.  */
799       if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
800         read_write_all_from_decl (node->decl, &read_all, &write_all);
801
802       for (e = node->callees; e; e = e->next_callee)
803         if (cgraph_function_body_availability (e->callee) <= AVAIL_OVERWRITABLE)
804           read_write_all_from_decl (e->callee->decl, &read_all, &write_all);
805
806
807       /* If any node in a cycle is calls_read_all or calls_write_all
808          they all are. */
809       w_info = (struct ipa_dfs_info *) node->aux;
810       w = w_info->next_cycle;
811       while (w)
812         {
813           ipa_reference_local_vars_info_t w_l =
814             get_reference_vars_info (w)->local;
815
816           /* When function is overwrittable, we can not assume anything.  */
817           if (cgraph_function_body_availability (w) <= AVAIL_OVERWRITABLE)
818             read_write_all_from_decl (w->decl, &read_all, &write_all);
819
820           for (e = w->callees; e; e = e->next_callee)
821             if (cgraph_function_body_availability (e->callee) <= AVAIL_OVERWRITABLE)
822               read_write_all_from_decl (e->callee->decl, &read_all, &write_all);
823
824           read_all |= w_l->calls_read_all;
825           write_all |= w_l->calls_write_all;
826
827           w_info = (struct ipa_dfs_info *) w->aux;
828           w = w_info->next_cycle;
829         }
830
831
832       /* Initialized the bitmaps for the reduced nodes */
833       if (read_all)
834         node_g->statics_read = all_module_statics;
835       else
836         {
837           node_g->statics_read = BITMAP_ALLOC (&global_info_obstack);
838           bitmap_copy (node_g->statics_read,
839                        node_l->statics_read);
840         }
841       if (write_all)
842         node_g->statics_written = all_module_statics;
843       else
844         {
845           node_g->statics_written = BITMAP_ALLOC (&global_info_obstack);
846           bitmap_copy (node_g->statics_written,
847                        node_l->statics_written);
848         }
849
850       propagate_bits (node_g, node);
851       w_info = (struct ipa_dfs_info *) node->aux;
852       w = w_info->next_cycle;
853       while (w)
854         {
855           ipa_reference_vars_info_t w_ri =
856             get_reference_vars_info (w);
857           ipa_reference_local_vars_info_t w_l = w_ri->local;
858
859           /* These global bitmaps are initialized from the local info
860              of all of the nodes in the region.  However there is no
861              need to do any work if the bitmaps were set to
862              all_module_statics.  */
863           if (!read_all)
864             bitmap_ior_into (node_g->statics_read,
865                              w_l->statics_read);
866           if (!write_all)
867             bitmap_ior_into (node_g->statics_written,
868                              w_l->statics_written);
869           propagate_bits (node_g, w);
870           w_info = (struct ipa_dfs_info *) w->aux;
871           w = w_info->next_cycle;
872         }
873
874       /* All nodes within a cycle have the same global info bitmaps.  */
875       node_info->global = node_g;
876       w_info = (struct ipa_dfs_info *) node->aux;
877       w = w_info->next_cycle;
878       while (w)
879         {
880           ipa_reference_vars_info_t w_ri =
881             get_reference_vars_info (w);
882
883           gcc_assert (!w_ri->global);
884           w_ri->global = XCNEW (struct ipa_reference_global_vars_info_d);
885           w_ri->global->statics_read = copy_global_bitmap (node_g->statics_read);
886           w_ri->global->statics_written = copy_global_bitmap (node_g->statics_written);
887
888           w_info = (struct ipa_dfs_info *) w->aux;
889           w = w_info->next_cycle;
890         }
891     }
892
893   if (dump_file)
894     {
895       for (i = 0; i < order_pos; i++ )
896         {
897           ipa_reference_vars_info_t node_info;
898           ipa_reference_global_vars_info_t node_g;
899           ipa_reference_local_vars_info_t node_l;
900           unsigned int index;
901           bitmap_iterator bi;
902           struct ipa_dfs_info * w_info;
903
904           node = order[i];
905           node_info = get_reference_vars_info (node);
906           node_g = node_info->global;
907           node_l = node_info->local;
908           fprintf (dump_file,
909                    "\nFunction name:%s/%i:",
910                    cgraph_node_name (node), node->uid);
911           fprintf (dump_file, "\n  locals read: ");
912           if (node_l->statics_read)
913             EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read,
914                                       0, index, bi)
915               {
916                 fprintf (dump_file, "%s ",
917                          get_static_name (index));
918               }
919           fprintf (dump_file, "\n  locals written: ");
920           if (node_l->statics_written)
921             EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written,
922                                       0, index, bi)
923               {
924                 fprintf(dump_file, "%s ",
925                         get_static_name (index));
926               }
927
928           w_info = (struct ipa_dfs_info *) node->aux;
929           w = w_info->next_cycle;
930           while (w)
931             {
932               ipa_reference_vars_info_t w_ri =
933                 get_reference_vars_info (w);
934               ipa_reference_local_vars_info_t w_l = w_ri->local;
935               fprintf (dump_file, "\n  next cycle: %s/%i ",
936                        cgraph_node_name (w), w->uid);
937               fprintf (dump_file, "\n    locals read: ");
938               if (w_l->statics_read)
939                 EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read,
940                                           0, index, bi)
941                   {
942                     fprintf (dump_file, "%s ",
943                              get_static_name (index));
944                   }
945
946               fprintf (dump_file, "\n    locals written: ");
947               if (w_l->statics_written)
948                 EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written,
949                                           0, index, bi)
950                   {
951                     fprintf (dump_file, "%s ",
952                              get_static_name (index));
953                   }
954
955               w_info = (struct ipa_dfs_info *) w->aux;
956               w = w_info->next_cycle;
957             }
958           fprintf (dump_file, "\n  globals read: ");
959           if (node_g->statics_read == all_module_statics)
960             fprintf (dump_file, "ALL");
961           else
962             EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read,
963                                       0, index, bi)
964               {
965                 fprintf (dump_file, "%s ",
966                          get_static_name (index));
967               }
968           fprintf (dump_file, "\n  globals written: ");
969           if (node_g->statics_written == all_module_statics)
970             fprintf (dump_file, "ALL");
971           else
972             EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written,
973                                       0, index, bi)
974               {
975                 fprintf (dump_file, "%s ",
976                          get_static_name (index));
977               }
978         }
979     }
980
981   /* Cleanup. */
982   for (i = 0; i < order_pos; i++ )
983     {
984       ipa_reference_vars_info_t node_info;
985       ipa_reference_global_vars_info_t node_g;
986       node = order[i];
987       node_info = get_reference_vars_info (node);
988       node_g = node_info->global;
989
990       /* Create the complimentary sets.  These are more useful for
991          certain apis.  */
992       node_g->statics_not_read = BITMAP_ALLOC (&global_info_obstack);
993       node_g->statics_not_written = BITMAP_ALLOC (&global_info_obstack);
994
995       if (node_g->statics_read != all_module_statics)
996         bitmap_and_compl (node_g->statics_not_read,
997                           all_module_statics,
998                           node_g->statics_read);
999
1000       if (node_g->statics_written
1001           != all_module_statics)
1002         bitmap_and_compl (node_g->statics_not_written,
1003                           all_module_statics,
1004                           node_g->statics_written);
1005    }
1006
1007   free (order);
1008
1009   for (node = cgraph_nodes; node; node = node->next)
1010     {
1011       ipa_reference_vars_info_t node_info;
1012       node_info = get_reference_vars_info (node);
1013       /* Get rid of the aux information.  */
1014
1015       if (node->aux)
1016         {
1017           free (node->aux);
1018           node->aux = NULL;
1019         }
1020
1021       if (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE)
1022         clean_function (node);
1023       else if (node_info)
1024         clean_function_local_data (node);
1025     }
1026   bitmap_obstack_release (&local_info_obstack);
1027   ipa_discover_readonly_nonaddressable_vars ();
1028   return 0;
1029 }
1030
1031
1032 static bool
1033 gate_reference (void)
1034 {
1035   return (flag_ipa_reference
1036           /* Don't bother doing anything if the program has errors.  */
1037           && !(errorcount || sorrycount));
1038 }
1039
1040 struct ipa_opt_pass_d pass_ipa_reference =
1041 {
1042  {
1043   IPA_PASS,
1044   "static-var",                         /* name */
1045   gate_reference,                       /* gate */
1046   propagate,                            /* execute */
1047   NULL,                                 /* sub */
1048   NULL,                                 /* next */
1049   0,                                    /* static_pass_number */
1050   TV_IPA_REFERENCE,                     /* tv_id */
1051   0,                                    /* properties_required */
1052   0,                                    /* properties_provided */
1053   0,                                    /* properties_destroyed */
1054   0,                                    /* todo_flags_start */
1055   0                                     /* todo_flags_finish */
1056  },
1057  NULL,                                  /* generate_summary */
1058  NULL,                                  /* write_summary */
1059  NULL,                                  /* read_summary */
1060  NULL,                                  /* write_optimization_summary */
1061  NULL,                                  /* read_optimization_summary */
1062  NULL,                                  /* stmt_fixup */
1063  0,                                     /* TODOs */
1064  NULL,                                  /* function_transform */
1065  NULL                                   /* variable_transform */
1066 };
1067
1068 #include "gt-ipa-reference.h"