OSDN Git Service

2008-03-11 Andrew Pinski <andrew_pinski@playstation.sony.com>
[pf3gnuchains/gcc-fork.git] / gcc / ipa-reference.c
1 /* Callgraph based analysis of static variables.
2    Copyright (C) 2004, 2005, 2007 Free Software Foundation, Inc.
3    Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 /* This file gathers information about how variables whose scope is
22    confined to the compilation unit are used.  
23
24    There are two categories of information produced by this pass:
25
26    1) The addressable (TREE_ADDRESSABLE) bit and readonly
27    (TREE_READONLY) bit associated with these variables is properly set
28    based on scanning all of the code withing the compilation unit.
29
30    2) The transitive call site specific clobber effects are computed
31    for the variables whose scope is contained within this compilation
32    unit.
33
34    First each function and static variable initialization is analyzed
35    to determine which local static variables are either read, written,
36    or have their address taken.  Any local static that has its address
37    taken is removed from consideration.  Once the local read and
38    writes are determined, a transitive closure of this information is
39    performed over the call graph to determine the worst case set of
40    side effects of each call.  In later parts of the compiler, these
41    local and global sets are examined to make the call clobbering less
42    traumatic, promote some statics to registers, and improve aliasing
43    information.
44    
45    Currently must be run after inlining decisions have been made since
46    otherwise, the local sets will not contain information that is
47    consistent with post inlined state.  The global sets are not prone
48    to this problem since they are by definition transitive.  
49 */
50
51 #include "config.h"
52 #include "system.h"
53 #include "coretypes.h"
54 #include "tm.h"
55 #include "tree.h"
56 #include "tree-flow.h"
57 #include "tree-inline.h"
58 #include "tree-pass.h"
59 #include "langhooks.h"
60 #include "pointer-set.h"
61 #include "ggc.h"
62 #include "ipa-utils.h"
63 #include "ipa-reference.h"
64 #include "c-common.h"
65 #include "tree-gimple.h"
66 #include "cgraph.h"
67 #include "output.h"
68 #include "flags.h"
69 #include "timevar.h"
70 #include "diagnostic.h"
71 #include "langhooks.h"
72
73 /* This splay tree contains all of the static variables that are
74    being considered by the compilation level alias analysis.  For
75    module_at_a_time compilation, this is the set of static but not
76    public variables.  Any variables that either have their address
77    taken or participate in otherwise unsavory operations are deleted
78    from this list.  */
79 static GTY((param1_is(int), param2_is(tree)))
80      splay_tree reference_vars_to_consider;
81
82 /* This bitmap is used to knock out the module static variables whose
83    addresses have been taken and passed around.  */
84 static bitmap module_statics_escape;
85
86 /* This bitmap is used to knock out the module static variables that
87    are not readonly.  */
88 static bitmap module_statics_written;
89
90 /* A bit is set for every module static we are considering.  This is
91    ored into the local info when asm code is found that clobbers all
92    memory. */
93 static bitmap all_module_statics;
94
95 static struct pointer_set_t *visited_nodes;
96
97 static bitmap_obstack ipa_obstack;
98
99 enum initialization_status_t
100 {
101   UNINITIALIZED,
102   RUNNING,
103   FINISHED
104 };
105
106 tree memory_identifier_string;
107
108 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
109 static inline ipa_reference_vars_info_t
110 get_reference_vars_info_from_cgraph (struct cgraph_node * node)
111 {
112   return get_function_ann (node->decl)->reference_vars_info;
113 }
114
115 /* Get a bitmap that contains all of the locally referenced static
116    variables for function FN.  */
117 static ipa_reference_local_vars_info_t
118 get_local_reference_vars_info (tree fn) 
119 {
120   ipa_reference_vars_info_t info = get_function_ann (fn)->reference_vars_info;
121
122   if (info)
123     return info->local;
124   else
125     /* This phase was not run.  */ 
126     return NULL;
127 }
128
129 /* Get a bitmap that contains all of the globally referenced static
130    variables for function FN.  */
131  
132 static ipa_reference_global_vars_info_t
133 get_global_reference_vars_info (tree fn) 
134 {
135   ipa_reference_vars_info_t info = get_function_ann (fn)->reference_vars_info;
136
137   if (info)
138     return info->global;
139   else
140     /* This phase was not run.  */ 
141     return NULL;
142 }
143
144 /* Return a bitmap indexed by VAR_DECL uid for the static variables
145    that may be read locally by the execution of the function fn.
146    Returns NULL if no data is available.  */
147
148 bitmap 
149 ipa_reference_get_read_local (tree fn)
150 {
151   ipa_reference_local_vars_info_t l = get_local_reference_vars_info (fn);
152   if (l) 
153     return l->statics_read;
154   else
155     return NULL;
156 }
157
158 /* Return a bitmap indexed by VAR_DECL uid for the static variables
159    that may be written locally by the execution of the function fn.
160    Returns NULL if no data is available.  */
161
162 bitmap 
163 ipa_reference_get_written_local (tree fn)
164 {
165   ipa_reference_local_vars_info_t l = get_local_reference_vars_info (fn);
166   if (l) 
167     return l->statics_written;
168   else
169     return NULL;
170 }
171
172 /* Return a bitmap indexed by VAR_DECL uid for the static variables
173    that are read during the execution of the function FN.  Returns
174    NULL if no data is available.  */
175
176 bitmap 
177 ipa_reference_get_read_global (tree fn) 
178 {
179   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
180   if (g) 
181     return g->statics_read;
182   else
183     return NULL;
184 }
185
186 /* Return a bitmap indexed by VAR_DECL uid for the static variables
187    that are written during the execution of the function FN.  Note
188    that variables written may or may not be read during the function
189    call.  Returns NULL if no data is available.  */
190
191 bitmap 
192 ipa_reference_get_written_global (tree fn) 
193 {
194   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
195   if (g) 
196     return g->statics_written;
197   else
198     return NULL;
199 }
200
201 /* Return a bitmap indexed by_DECL_UID uid for the static variables
202    that are not read during the execution of the function FN.  Returns
203    NULL if no data is available.  */
204
205 bitmap 
206 ipa_reference_get_not_read_global (tree fn) 
207 {
208   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
209   if (g) 
210     return g->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 (tree fn) 
222 {
223   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
224   if (g) 
225     return g->statics_not_written;
226   else
227     return NULL;
228 }
229
230 \f
231
232 /* Add VAR to all_module_statics and the two
233    reference_vars_to_consider* sets.  */
234
235 static inline void 
236 add_static_var (tree var) 
237 {
238   int uid = DECL_UID (var);
239   if (!bitmap_bit_p (all_module_statics, uid))
240     {
241       splay_tree_insert (reference_vars_to_consider,
242                          uid, (splay_tree_value)var);
243       bitmap_set_bit (all_module_statics, uid);
244     }
245 }
246
247 /* Return true if the variable T is the right kind of static variable to
248    perform compilation unit scope escape analysis.  */
249
250 static inline bool 
251 has_proper_scope_for_analysis (tree t)
252 {
253   /* If the variable has the "used" attribute, treat it as if it had a
254      been touched by the devil.  */
255   if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
256     return false;
257
258   /* Do not want to do anything with volatile except mark any
259      function that uses one to be not const or pure.  */
260   if (TREE_THIS_VOLATILE (t)) 
261     return false;
262
263   /* Do not care about a local automatic that is not static.  */
264   if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
265     return false;
266
267   if (DECL_EXTERNAL (t) || TREE_PUBLIC (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 (!bitmap_bit_p (all_module_statics, DECL_UID (t)))
277     add_static_var (t);
278
279   return true;
280 }
281
282 /* If T is a VAR_DECL for a static that we are interested in, add the
283    uid to the bitmap.  */
284
285 static void
286 check_operand (ipa_reference_local_vars_info_t local, 
287                tree t, bool checking_write)
288 {
289   if (!t) return;
290
291   if ((TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == FUNCTION_DECL)
292       && (has_proper_scope_for_analysis (t))) 
293     {
294       if (checking_write)
295         {
296           if (local)
297             bitmap_set_bit (local->statics_written, DECL_UID (t));
298           /* Mark the write so we can tell which statics are
299              readonly.  */
300           bitmap_set_bit (module_statics_written, DECL_UID (t));
301         }
302       else if (local)
303         bitmap_set_bit (local->statics_read, DECL_UID (t));
304     }
305 }
306
307 /* Examine tree T for references to static variables. All internal
308    references like array references or indirect references are added
309    to the READ_BM. Direct references are added to either READ_BM or
310    WRITE_BM depending on the value of CHECKING_WRITE.   */
311
312 static void
313 check_tree (ipa_reference_local_vars_info_t local, tree t, bool checking_write)
314 {
315   if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
316     return;
317
318   while (TREE_CODE (t) == REALPART_EXPR 
319          || TREE_CODE (t) == IMAGPART_EXPR
320          || handled_component_p (t))
321     {
322       if (TREE_CODE (t) == ARRAY_REF)
323         check_operand (local, TREE_OPERAND (t, 1), false);
324       t = TREE_OPERAND (t, 0);
325     }
326
327   /* The bottom of an indirect reference can only be read, not
328      written.  So just recurse and whatever we find, check it against
329      the read bitmaps.  */
330
331   /*  if (INDIRECT_REF_P (t) || TREE_CODE (t) == MEM_REF) */
332   /* FIXME when we have array_ref's of pointers.  */
333   if (INDIRECT_REF_P (t))
334     check_tree (local, TREE_OPERAND (t, 0), false);
335
336   if (SSA_VAR_P (t))
337     check_operand (local, t, checking_write);
338 }
339
340 /* Scan tree T to see if there are any addresses taken in within T.  */
341
342 static void 
343 look_for_address_of (tree t)
344 {
345   if (TREE_CODE (t) == ADDR_EXPR)
346     {
347       tree x = get_base_var (t);
348       if (TREE_CODE (x) == VAR_DECL || TREE_CODE (x) == FUNCTION_DECL) 
349         if (has_proper_scope_for_analysis (x))
350           bitmap_set_bit (module_statics_escape, DECL_UID (x));
351     }
352 }
353
354 /* Check to see if T is a read or address of operation on a static var
355    we are interested in analyzing.  LOCAL is passed in to get access
356    to its bit vectors.  Local is NULL if this is called from a static
357    initializer.  */
358
359 static void
360 check_rhs_var (ipa_reference_local_vars_info_t local, tree t)
361 {
362   look_for_address_of (t);
363
364   if (local == NULL) 
365     return;
366
367   check_tree(local, t, false);
368 }
369
370 /* Check to see if T is an assignment to a static var we are
371    interested in analyzing.  LOCAL is passed in to get access to its bit
372    vectors.  */
373
374 static void
375 check_lhs_var (ipa_reference_local_vars_info_t local, tree t)
376 {
377   if (local == NULL) 
378     return;
379    
380   check_tree(local, t, true);
381 }
382
383 /* This is a scaled down version of get_asm_expr_operands from
384    tree_ssa_operands.c.  The version there runs much later and assumes
385    that aliasing information is already available. Here we are just
386    trying to find if the set of inputs and outputs contain references
387    or address of operations to local static variables.  FN is the
388    function being analyzed and STMT is the actual asm statement.  */
389
390 static void
391 get_asm_expr_operands (ipa_reference_local_vars_info_t local, tree stmt)
392 {
393   int noutputs = list_length (ASM_OUTPUTS (stmt));
394   const char **oconstraints
395     = (const char **) alloca ((noutputs) * sizeof (const char *));
396   int i;
397   tree link;
398   const char *constraint;
399   bool allows_mem, allows_reg, is_inout;
400   
401   for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link))
402     {
403       oconstraints[i] = constraint
404         = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
405       parse_output_constraint (&constraint, i, 0, 0,
406                                &allows_mem, &allows_reg, &is_inout);
407       
408       check_lhs_var (local, TREE_VALUE (link));
409     }
410
411   for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
412     {
413       constraint
414         = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
415       parse_input_constraint (&constraint, 0, 0, noutputs, 0,
416                               oconstraints, &allows_mem, &allows_reg);
417       
418       check_rhs_var (local, TREE_VALUE (link));
419     }
420   
421   for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link))
422     if (simple_cst_equal(TREE_VALUE (link), memory_identifier_string) == 1) 
423       {
424         /* Abandon all hope, ye who enter here. */
425         local->calls_read_all = true;
426         local->calls_write_all = true;
427       }      
428 }
429
430 /* Check the parameters of a function call from CALLER to CALL_EXPR to
431    see if any of them are static vars.  Also check to see if this is
432    either an indirect call, a call outside the compilation unit, or
433    has special attributes that effect the clobbers.  The caller
434    parameter is the tree node for the caller and the second operand is
435    the tree node for the entire call expression.  */
436
437 static void
438 check_call (ipa_reference_local_vars_info_t local, tree call_expr) 
439 {
440   int flags = call_expr_flags (call_expr);
441   tree operand;
442   tree callee_t = get_callee_fndecl (call_expr);
443   enum availability avail = AVAIL_NOT_AVAILABLE;
444   call_expr_arg_iterator iter;
445
446   FOR_EACH_CALL_EXPR_ARG (operand, iter, call_expr)
447     check_rhs_var (local, operand);
448
449   if (callee_t)
450     {
451       struct cgraph_node* callee = cgraph_node(callee_t);
452       avail = cgraph_function_body_availability (callee);
453     }
454
455   if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
456     if (local) 
457       {
458         if (flags & ECF_PURE) 
459           local->calls_read_all = true;
460         else 
461           {
462             local->calls_read_all = true;
463             local->calls_write_all = true;
464           }
465       }
466 }
467
468 /* TP is the part of the tree currently under the microscope.
469    WALK_SUBTREES is part of the walk_tree api but is unused here.
470    DATA is cgraph_node of the function being walked.  */
471
472 /* FIXME: When this is converted to run over SSA form, this code
473    should be converted to use the operand scanner.  */
474
475 static tree
476 scan_for_static_refs (tree *tp, 
477                       int *walk_subtrees, 
478                       void *data)
479 {
480   struct cgraph_node *fn = (struct cgraph_node *) data;
481   tree t = *tp;
482   ipa_reference_local_vars_info_t local = NULL;
483   if (fn)
484     local = get_reference_vars_info_from_cgraph (fn)->local;
485
486   switch (TREE_CODE (t))  
487     {
488     case VAR_DECL:
489       if (DECL_INITIAL (t))
490         walk_tree (&DECL_INITIAL (t), scan_for_static_refs, fn, visited_nodes);
491       *walk_subtrees = 0;
492       break;
493
494     case GIMPLE_MODIFY_STMT:
495       {
496         /* First look on the lhs and see what variable is stored to */
497         tree lhs = GIMPLE_STMT_OPERAND (t, 0);
498         tree rhs = GIMPLE_STMT_OPERAND (t, 1);
499         check_lhs_var (local, lhs);
500
501         /* For the purposes of figuring out what the cast affects */
502
503         /* Next check the operands on the rhs to see if they are ok. */
504         switch (TREE_CODE_CLASS (TREE_CODE (rhs))) 
505           {
506           case tcc_binary:          
507           case tcc_comparison:      
508             {
509               tree op0 = TREE_OPERAND (rhs, 0);
510               tree op1 = TREE_OPERAND (rhs, 1);
511               check_rhs_var (local, op0);
512               check_rhs_var (local, op1);
513             }
514             break;
515           case tcc_unary:
516             {
517               tree op0 = TREE_OPERAND (rhs, 0);
518               check_rhs_var (local, op0);
519             }
520
521             break;
522           case tcc_reference:
523             check_rhs_var (local, rhs);
524             break;
525           case tcc_declaration:
526             check_rhs_var (local, rhs);
527             break;
528           case tcc_expression:
529             switch (TREE_CODE (rhs)) 
530               {
531               case ADDR_EXPR:
532                 check_rhs_var (local, rhs);
533                 break;
534               default:
535                 break;
536               }
537             break;
538           case tcc_vl_exp:
539             switch (TREE_CODE (rhs))
540               {
541               case CALL_EXPR:
542                 check_call (local, rhs);
543                 break;
544               default:
545                 break;
546               }
547             break;
548           default:
549             break;
550           }
551         *walk_subtrees = 0;
552       }
553       break;
554
555     case ADDR_EXPR:
556       /* This case is here to find addresses on rhs of constructors in
557          decl_initial of static variables. */
558       check_rhs_var (local, t);
559       *walk_subtrees = 0;
560       break;
561
562     case LABEL_EXPR:
563       if (DECL_NONLOCAL (TREE_OPERAND (t, 0)))
564         {
565           /* Target of long jump. */
566           local->calls_read_all = true;
567           local->calls_write_all = true;
568         }
569       break;
570
571     case CALL_EXPR: 
572       check_call (local, t);
573       *walk_subtrees = 0;
574       break;
575       
576     case ASM_EXPR:
577       get_asm_expr_operands (local, t);
578       *walk_subtrees = 0;
579       break;
580       
581     default:
582       break;
583     }
584   return NULL;
585 }
586
587
588 /* Lookup the tree node for the static variable that has UID.  */
589 static tree
590 get_static_decl (int index)
591 {
592   splay_tree_node stn = 
593     splay_tree_lookup (reference_vars_to_consider, index);
594   if (stn)
595     return (tree)stn->value;
596   return NULL;
597 }
598
599 /* Lookup the tree node for the static variable that has UID and
600    convert the name to a string for debugging.  */
601
602 static const char *
603 get_static_name (int index)
604 {
605   splay_tree_node stn = 
606     splay_tree_lookup (reference_vars_to_consider, index);
607   if (stn)
608     return lang_hooks.decl_printable_name ((tree)(stn->value), 2);
609   return NULL;
610 }
611
612 /* Or in all of the bits from every callee into X, the caller's, bit
613    vector.  There are several cases to check to avoid the sparse
614    bitmap oring.  */
615
616 static void
617 propagate_bits (struct cgraph_node *x)
618 {
619   ipa_reference_vars_info_t x_info = get_reference_vars_info_from_cgraph (x);
620   ipa_reference_global_vars_info_t x_global = x_info->global;
621
622   struct cgraph_edge *e;
623   for (e = x->callees; e; e = e->next_callee) 
624     {
625       struct cgraph_node *y = e->callee;
626
627       /* Only look at the master nodes and skip external nodes.  */
628       y = cgraph_master_clone (y);
629       if (y)
630         {
631           if (get_reference_vars_info_from_cgraph (y))
632             {
633               ipa_reference_vars_info_t y_info = get_reference_vars_info_from_cgraph (y);
634               ipa_reference_global_vars_info_t y_global = y_info->global;
635               
636               if (x_global->statics_read
637                   != all_module_statics)
638                 {
639                   if (y_global->statics_read 
640                       == all_module_statics)
641                     {
642                       BITMAP_FREE (x_global->statics_read);
643                       x_global->statics_read 
644                         = all_module_statics;
645                     }
646                   /* Skip bitmaps that are pointer equal to node's bitmap
647                      (no reason to spin within the cycle).  */
648                   else if (x_global->statics_read 
649                            != y_global->statics_read)
650                     bitmap_ior_into (x_global->statics_read,
651                                      y_global->statics_read);
652                 }
653               
654               if (x_global->statics_written 
655                   != all_module_statics)
656                 {
657                   if (y_global->statics_written 
658                       == all_module_statics)
659                     {
660                       BITMAP_FREE (x_global->statics_written);
661                       x_global->statics_written 
662                         = all_module_statics;
663                     }
664                   /* Skip bitmaps that are pointer equal to node's bitmap
665                      (no reason to spin within the cycle).  */
666                   else if (x_global->statics_written 
667                            != y_global->statics_written)
668                     bitmap_ior_into (x_global->statics_written,
669                                      y_global->statics_written);
670                 }
671             }
672           else 
673             {
674               gcc_unreachable ();
675             }
676         }
677     }
678 }
679
680 /* Look at all of the callees of X to see which ones represent inlined
681    calls.  For each of these callees, merge their local info into
682    TARGET and check their children recursively.  
683
684    This function goes away when Jan changes the inliner and IPA
685    analysis so that this is not run between the time when inlining
686    decisions are made and when the inlining actually occurs.  */
687
688 static void 
689 merge_callee_local_info (struct cgraph_node *target, 
690                          struct cgraph_node *x)
691 {
692   struct cgraph_edge *e;
693   ipa_reference_local_vars_info_t x_l = 
694     get_reference_vars_info_from_cgraph (target)->local;
695
696   /* Make the world safe for tail recursion.  */
697   struct ipa_dfs_info *node_info = (struct ipa_dfs_info *) x->aux;
698   
699   if (node_info->aux) 
700     return;
701
702   node_info->aux = x;
703
704   for (e = x->callees; e; e = e->next_callee) 
705     {
706       struct cgraph_node *y = e->callee;
707       if (y->global.inlined_to) 
708         {
709           ipa_reference_vars_info_t y_info;
710           ipa_reference_local_vars_info_t y_l;
711           struct cgraph_node* orig_y = y;
712          
713           y = cgraph_master_clone (y);
714           if (y)
715             {
716               y_info = get_reference_vars_info_from_cgraph (y);
717               y_l = y_info->local;
718               if (x_l != y_l)
719                 {
720                   bitmap_ior_into (x_l->statics_read,
721                                    y_l->statics_read);
722                   bitmap_ior_into (x_l->statics_written,
723                                    y_l->statics_written);
724                 }
725               x_l->calls_read_all |= y_l->calls_read_all;
726               x_l->calls_write_all |= y_l->calls_write_all;
727               merge_callee_local_info (target, y);
728             }
729           else 
730             {
731               fprintf(stderr, "suspect inlining of ");
732               dump_cgraph_node (stderr, orig_y);
733               fprintf(stderr, "\ninto ");
734               dump_cgraph_node (stderr, target);
735               dump_cgraph (stderr);
736               gcc_assert(false);
737             }
738         }
739     }
740
741   node_info->aux = NULL;
742 }
743
744 /* The init routine for analyzing global static variable usage.  See
745    comments at top for description.  */
746 static void 
747 ipa_init (void) 
748 {
749   struct cgraph_node *node;
750   memory_identifier_string = build_string(7, "memory");
751
752   reference_vars_to_consider =
753     splay_tree_new_ggc (splay_tree_compare_ints);
754
755   bitmap_obstack_initialize (&ipa_obstack);
756   module_statics_escape = BITMAP_ALLOC (&ipa_obstack);
757   module_statics_written = BITMAP_ALLOC (&ipa_obstack);
758   all_module_statics = BITMAP_ALLOC (&ipa_obstack);
759
760   /* This will add NODE->DECL to the splay trees.  */
761   for (node = cgraph_nodes; node; node = node->next)
762     has_proper_scope_for_analysis (node->decl);
763
764   /* There are some shared nodes, in particular the initializers on
765      static declarations.  We do not need to scan them more than once
766      since all we would be interested in are the addressof
767      operations.  */
768   visited_nodes = pointer_set_create ();
769 }
770
771 /* Check out the rhs of a static or global initialization VNODE to see
772    if any of them contain addressof operations.  Note that some of
773    these variables may  not even be referenced in the code in this
774    compilation unit but their right hand sides may contain references
775    to variables defined within this unit.  */
776
777 static void 
778 analyze_variable (struct varpool_node *vnode)
779 {
780   tree global = vnode->decl;
781   walk_tree (&DECL_INITIAL (global), scan_for_static_refs, 
782              NULL, visited_nodes);
783 }
784
785 /* This is the main routine for finding the reference patterns for
786    global variables within a function FN.  */
787
788 static void
789 analyze_function (struct cgraph_node *fn)
790 {
791   ipa_reference_vars_info_t info 
792     = XCNEW (struct ipa_reference_vars_info_d);
793   ipa_reference_local_vars_info_t l
794     = XCNEW (struct ipa_reference_local_vars_info_d);
795   tree decl = fn->decl;
796
797   /* Add the info to the tree's annotation.  */
798   get_function_ann (fn->decl)->reference_vars_info = info;
799
800   info->local = l;
801   l->statics_read = BITMAP_ALLOC (&ipa_obstack);
802   l->statics_written = BITMAP_ALLOC (&ipa_obstack);
803
804   if (dump_file)
805     fprintf (dump_file, "\n local analysis of %s\n", cgraph_node_name (fn));
806   
807   {
808     struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
809     basic_block this_block;
810
811     FOR_EACH_BB_FN (this_block, this_cfun)
812       {
813         block_stmt_iterator bsi;
814         tree phi, op;
815         use_operand_p use;
816         ssa_op_iter iter;
817
818         /* Find the addresses taken in phi node arguments.  */
819         for (phi = phi_nodes (this_block); phi; phi = PHI_CHAIN (phi))
820           {
821             FOR_EACH_PHI_ARG (use, phi, iter, SSA_OP_USE)
822               {
823                 op = USE_FROM_PTR (use);
824                 if (TREE_CODE (op) == ADDR_EXPR)
825                   check_rhs_var (l, op);
826               }
827           }
828
829         for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
830           walk_tree (bsi_stmt_ptr (bsi), scan_for_static_refs, 
831                      fn, visited_nodes);
832       }
833   }
834
835   /* There may be const decls with interesting right hand sides.  */
836   if (DECL_STRUCT_FUNCTION (decl))
837     {
838       tree step;
839       for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list;
840            step;
841            step = TREE_CHAIN (step))
842         {
843           tree var = TREE_VALUE (step);
844           if (TREE_CODE (var) == VAR_DECL 
845               && DECL_INITIAL (var)
846               && !TREE_STATIC (var))
847             walk_tree (&DECL_INITIAL (var), scan_for_static_refs, 
848                        fn, visited_nodes);
849         }
850     }
851 }
852
853 /* If FN is avail == AVAIL_OVERWRITABLE, replace the effects bit
854    vectors with worst case bit vectors.  We had to analyze it above to
855    find out if it took the address of any statics. However, now that
856    we know that, we can get rid of all of the other side effects.  */
857
858 static void
859 clean_function (struct cgraph_node *fn)
860 {
861   ipa_reference_vars_info_t info = get_reference_vars_info_from_cgraph (fn);
862   ipa_reference_local_vars_info_t l = info->local;
863   ipa_reference_global_vars_info_t g = info->global;
864   
865   if (l)
866     {
867       if (l->statics_read
868           && l->statics_read != all_module_statics)
869         BITMAP_FREE (l->statics_read);
870       if (l->statics_written
871           &&l->statics_written != all_module_statics)
872         BITMAP_FREE (l->statics_written);
873       free (l);
874     }
875   
876   if (g)
877     {
878       if (g->statics_read
879           && g->statics_read != all_module_statics)
880         BITMAP_FREE (g->statics_read);
881       
882       if (g->statics_written
883           && g->statics_written != all_module_statics)
884         BITMAP_FREE (g->statics_written);
885       
886       if (g->statics_not_read
887           && g->statics_not_read != all_module_statics)
888         BITMAP_FREE (g->statics_not_read);
889       
890       if (g->statics_not_written
891           && g->statics_not_written != all_module_statics)
892         BITMAP_FREE (g->statics_not_written);
893       free (g);
894     }
895
896   
897   free (get_function_ann (fn->decl)->reference_vars_info);
898   get_function_ann (fn->decl)->reference_vars_info = NULL;
899 }
900
901 \f
902 /* Produce the global information by preforming a transitive closure
903    on the local information that was produced by ipa_analyze_function
904    and ipa_analyze_variable.  */
905
906 static unsigned int
907 static_execute (void)
908 {
909   struct cgraph_node *node;
910   struct varpool_node *vnode;
911   struct cgraph_node *w;
912   struct cgraph_node **order =
913     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
914   int order_pos = ipa_utils_reduced_inorder (order, false, true);
915   int i;
916
917   ipa_init ();
918
919   /* Process all of the variables first.  */
920   FOR_EACH_STATIC_INITIALIZER (vnode)
921     analyze_variable (vnode);
922
923   /* Process all of the functions next. 
924
925      We do not want to process any of the clones so we check that this
926      is a master clone.  However, we do need to process any
927      AVAIL_OVERWRITABLE functions (these are never clones) because
928      they may cause a static variable to escape.  The code that can
929      overwrite such a function cannot access the statics because it
930      would not be in the same compilation unit.  When the analysis is
931      finished, the computed information of these AVAIL_OVERWRITABLE is
932      replaced with worst case info.  
933   */
934   for (node = cgraph_nodes; node; node = node->next)
935     if (node->analyzed 
936         && (cgraph_is_master_clone (node)
937             || (cgraph_function_body_availability (node) 
938                 == AVAIL_OVERWRITABLE)))
939       analyze_function (node);
940
941   pointer_set_destroy (visited_nodes);
942   visited_nodes = NULL;
943   if (dump_file) 
944     dump_cgraph (dump_file);
945
946   /* Prune out the variables that were found to behave badly
947      (i.e. have their address taken).  */
948   {
949     unsigned int index;
950     bitmap_iterator bi;
951     bitmap module_statics_readonly = BITMAP_ALLOC (&ipa_obstack);
952     bitmap bm_temp = BITMAP_ALLOC (&ipa_obstack);
953
954     EXECUTE_IF_SET_IN_BITMAP (module_statics_escape, 0, index, bi)
955       {
956         splay_tree_remove (reference_vars_to_consider, index);
957       }
958
959     bitmap_and_compl_into (all_module_statics, 
960                            module_statics_escape);
961
962     bitmap_and_compl (module_statics_readonly, all_module_statics,
963                       module_statics_written);
964
965     /* If the address is not taken, we can unset the addressable bit
966        on this variable.  */
967     EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
968       {
969         tree var = get_static_decl (index);
970         TREE_ADDRESSABLE (var) = 0;
971         if (dump_file) 
972           fprintf (dump_file, "Not TREE_ADDRESSABLE var %s\n",
973                    get_static_name (index));
974       }
975
976     /* If the variable is never written, we can set the TREE_READONLY
977        flag.  Additionally if it has a DECL_INITIAL that is made up of
978        constants we can treat the entire global as a constant.  */
979
980     bitmap_and_compl (module_statics_readonly, all_module_statics,
981                       module_statics_written);
982     EXECUTE_IF_SET_IN_BITMAP (module_statics_readonly, 0, index, bi)
983       {
984         tree var = get_static_decl (index);
985
986         /* Readonly on a function decl is very different from the
987            variable.  */
988         if (TREE_CODE (var) == FUNCTION_DECL)
989           continue;
990
991         /* Ignore variables in named sections - changing TREE_READONLY
992            changes the section flags, potentially causing conflicts with
993            other variables in the same named section.  */
994         if (DECL_SECTION_NAME (var) == NULL_TREE)
995           {
996             TREE_READONLY (var) = 1;
997             if (dump_file)
998               fprintf (dump_file, "read-only var %s\n", 
999                        get_static_name (index));
1000           }
1001       }
1002
1003     BITMAP_FREE(module_statics_escape);
1004     BITMAP_FREE(module_statics_written);
1005
1006     if (dump_file)
1007       EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
1008         {
1009           fprintf (dump_file, "\nPromotable global:%s",
1010                    get_static_name (index));
1011         }
1012
1013     for (i = 0; i < order_pos; i++ )
1014       {
1015         ipa_reference_local_vars_info_t l;
1016         node = order[i];
1017         l = get_reference_vars_info_from_cgraph (node)->local;
1018
1019         /* Any variables that are not in all_module_statics are
1020            removed from the local maps.  This will include all of the
1021            variables that were found to escape in the function
1022            scanning.  */
1023         bitmap_and_into (l->statics_read, 
1024                          all_module_statics);
1025         bitmap_and_into (l->statics_written, 
1026                          all_module_statics);
1027       }
1028
1029     BITMAP_FREE(module_statics_readonly);
1030     BITMAP_FREE(bm_temp);
1031   }
1032
1033   if (dump_file)
1034     {
1035       for (i = 0; i < order_pos; i++ )
1036         {
1037           unsigned int index;
1038           ipa_reference_local_vars_info_t l;
1039           bitmap_iterator bi;
1040
1041           node = order[i];
1042           l = get_reference_vars_info_from_cgraph (node)->local;
1043           fprintf (dump_file, 
1044                    "\nFunction name:%s/%i:", 
1045                    cgraph_node_name (node), node->uid);
1046           fprintf (dump_file, "\n  locals read: ");
1047           EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
1048                                     0, index, bi)
1049             {
1050               fprintf (dump_file, "%s ",
1051                        get_static_name (index));
1052             }
1053           fprintf (dump_file, "\n  locals written: ");
1054           EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
1055                                     0, index, bi)
1056             {
1057               fprintf(dump_file, "%s ",
1058                       get_static_name (index));
1059             }
1060         }
1061     }
1062
1063   /* Propagate the local information thru the call graph to produce
1064      the global information.  All the nodes within a cycle will have
1065      the same info so we collapse cycles first.  Then we can do the
1066      propagation in one pass from the leaves to the roots.  */
1067   order_pos = ipa_utils_reduced_inorder (order, true, true);
1068   if (dump_file)
1069     ipa_utils_print_order(dump_file, "reduced", order, order_pos);
1070
1071   for (i = 0; i < order_pos; i++ )
1072     {
1073       ipa_reference_vars_info_t node_info;
1074       ipa_reference_global_vars_info_t node_g = 
1075         XCNEW (struct ipa_reference_global_vars_info_d);
1076       ipa_reference_local_vars_info_t node_l;
1077       
1078       bool read_all;
1079       bool write_all;
1080       struct ipa_dfs_info * w_info;
1081
1082       node = order[i];
1083       node_info = get_reference_vars_info_from_cgraph (node);
1084       if (!node_info) 
1085         {
1086           dump_cgraph_node (stderr, node);
1087           dump_cgraph (stderr);
1088           gcc_unreachable ();
1089         }
1090
1091       node_info->global = node_g;
1092       node_l = node_info->local;
1093
1094       read_all = node_l->calls_read_all;
1095       write_all = node_l->calls_write_all;
1096
1097       /* If any node in a cycle is calls_read_all or calls_write_all
1098          they all are. */
1099       w_info = (struct ipa_dfs_info *) node->aux;
1100       w = w_info->next_cycle;
1101       while (w)
1102         {
1103           ipa_reference_local_vars_info_t w_l = 
1104             get_reference_vars_info_from_cgraph (w)->local;
1105           read_all |= w_l->calls_read_all;
1106           write_all |= w_l->calls_write_all;
1107
1108           w_info = (struct ipa_dfs_info *) w->aux;
1109           w = w_info->next_cycle;
1110         }
1111
1112       /* Initialized the bitmaps for the reduced nodes */
1113       if (read_all) 
1114         node_g->statics_read = all_module_statics;
1115       else 
1116         {
1117           node_g->statics_read = BITMAP_ALLOC (&ipa_obstack);
1118           bitmap_copy (node_g->statics_read, 
1119                        node_l->statics_read);
1120         }
1121
1122       if (write_all) 
1123         node_g->statics_written = all_module_statics;
1124       else
1125         {
1126           node_g->statics_written = BITMAP_ALLOC (&ipa_obstack);
1127           bitmap_copy (node_g->statics_written, 
1128                        node_l->statics_written);
1129         }
1130
1131       w_info = (struct ipa_dfs_info *) node->aux;
1132       w = w_info->next_cycle;
1133       while (w)
1134         {
1135           ipa_reference_vars_info_t w_ri = 
1136             get_reference_vars_info_from_cgraph (w);
1137           ipa_reference_local_vars_info_t w_l = w_ri->local;
1138
1139           /* All nodes within a cycle share the same global info bitmaps.  */
1140           w_ri->global = node_g;
1141           
1142           /* These global bitmaps are initialized from the local info
1143              of all of the nodes in the region.  However there is no
1144              need to do any work if the bitmaps were set to
1145              all_module_statics.  */
1146           if (!read_all)
1147             bitmap_ior_into (node_g->statics_read,
1148                              w_l->statics_read);
1149           if (!write_all)
1150             bitmap_ior_into (node_g->statics_written,
1151                              w_l->statics_written);
1152           w_info = (struct ipa_dfs_info *) w->aux;
1153           w = w_info->next_cycle;
1154         }
1155
1156       w = node;
1157       while (w)
1158         {
1159           propagate_bits (w);
1160           w_info = (struct ipa_dfs_info *) w->aux;
1161           w = w_info->next_cycle;
1162         }
1163     }
1164
1165   /* Need to fix up the local information sets.  The information that
1166      has been gathered so far is preinlining.  However, the
1167      compilation will progress post inlining so the local sets for the
1168      inlined calls need to be merged into the callers.  Note that the
1169      local sets are not shared between all of the nodes in a cycle so
1170      those nodes in the cycle must be processed explicitly.  */
1171   for (i = 0; i < order_pos; i++ )
1172     {
1173       struct ipa_dfs_info * w_info;
1174       node = order[i];
1175       merge_callee_local_info (node, node);
1176       
1177       w_info = (struct ipa_dfs_info *) node->aux;
1178       w = w_info->next_cycle;
1179       while (w)
1180         {
1181           merge_callee_local_info (w, w);
1182           w_info = (struct ipa_dfs_info *) w->aux;
1183           w = w_info->next_cycle;
1184         }
1185     }
1186
1187   if (dump_file)
1188     {
1189       for (i = 0; i < order_pos; i++ )
1190         {
1191           ipa_reference_vars_info_t node_info;
1192           ipa_reference_global_vars_info_t node_g;
1193           ipa_reference_local_vars_info_t node_l;
1194           unsigned int index;
1195           bitmap_iterator bi;
1196           struct ipa_dfs_info * w_info;
1197
1198           node = order[i];
1199           node_info = get_reference_vars_info_from_cgraph (node);
1200           node_g = node_info->global;
1201           node_l = node_info->local;
1202           fprintf (dump_file, 
1203                    "\nFunction name:%s/%i:", 
1204                    cgraph_node_name (node), node->uid);
1205           fprintf (dump_file, "\n  locals read: ");
1206           EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read,
1207                                     0, index, bi)
1208             {
1209               fprintf (dump_file, "%s ",
1210                        get_static_name (index));
1211             }
1212           fprintf (dump_file, "\n  locals written: ");
1213           EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written,
1214                                     0, index, bi)
1215             {
1216               fprintf(dump_file, "%s ",
1217                       get_static_name (index));
1218             }
1219
1220           w_info = (struct ipa_dfs_info *) node->aux;
1221           w = w_info->next_cycle;
1222           while (w) 
1223             {
1224               ipa_reference_vars_info_t w_ri = 
1225                 get_reference_vars_info_from_cgraph (w);
1226               ipa_reference_local_vars_info_t w_l = w_ri->local;
1227               fprintf (dump_file, "\n  next cycle: %s/%i ",
1228                        cgraph_node_name (w), w->uid);
1229               fprintf (dump_file, "\n    locals read: ");
1230               EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read,
1231                                         0, index, bi)
1232                 {
1233                   fprintf (dump_file, "%s ",
1234                            get_static_name (index));
1235                 }
1236
1237               fprintf (dump_file, "\n    locals written: ");
1238               EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written,
1239                                         0, index, bi)
1240                 {
1241                   fprintf(dump_file, "%s ",
1242                           get_static_name (index));
1243                 }
1244               
1245
1246               w_info = (struct ipa_dfs_info *) w->aux;
1247               w = w_info->next_cycle;
1248             }
1249           fprintf (dump_file, "\n  globals read: ");
1250           EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read,
1251                                     0, index, bi)
1252             {
1253               fprintf (dump_file, "%s ",
1254                        get_static_name (index));
1255             }
1256           fprintf (dump_file, "\n  globals written: ");
1257           EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written,
1258                                     0, index, bi)
1259             {
1260               fprintf (dump_file, "%s ",
1261                        get_static_name (index));
1262             }
1263         }
1264     }
1265
1266   /* Cleanup. */
1267   for (i = 0; i < order_pos; i++ )
1268     {
1269       ipa_reference_vars_info_t node_info;
1270       ipa_reference_global_vars_info_t node_g;
1271       node = order[i];
1272       node_info = get_reference_vars_info_from_cgraph (node);
1273       node_g = node_info->global;
1274       
1275       /* Create the complimentary sets.  These are more useful for
1276          certain apis.  */
1277       node_g->statics_not_read = BITMAP_ALLOC (&ipa_obstack);
1278       node_g->statics_not_written = BITMAP_ALLOC (&ipa_obstack);
1279
1280       if (node_g->statics_read != all_module_statics) 
1281         {
1282           bitmap_and_compl (node_g->statics_not_read, 
1283                             all_module_statics,
1284                             node_g->statics_read);
1285         }
1286
1287       if (node_g->statics_written 
1288           != all_module_statics) 
1289         bitmap_and_compl (node_g->statics_not_written, 
1290                           all_module_statics,
1291                           node_g->statics_written);
1292    }
1293
1294   free (order);
1295
1296   for (node = cgraph_nodes; node; node = node->next)
1297     {
1298       /* Get rid of the aux information.  */
1299       
1300       if (node->aux)
1301         {
1302           free (node->aux);
1303           node->aux = NULL;
1304         }
1305       
1306       if (node->analyzed 
1307           && (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE))
1308         clean_function (node);
1309     }
1310   return 0;
1311 }
1312
1313
1314 static bool
1315 gate_reference (void)
1316 {
1317   return (flag_unit_at_a_time != 0  && flag_ipa_reference
1318           /* Don't bother doing anything if the program has errors.  */
1319           && !(errorcount || sorrycount));
1320 }
1321
1322 struct tree_opt_pass pass_ipa_reference =
1323 {
1324   "static-var",                         /* name */
1325   gate_reference,                       /* gate */
1326   static_execute,                       /* execute */
1327   NULL,                                 /* sub */
1328   NULL,                                 /* next */
1329   0,                                    /* static_pass_number */
1330   TV_IPA_REFERENCE,                     /* tv_id */
1331   0,                                    /* properties_required */
1332   0,                                    /* properties_provided */
1333   0,                                    /* properties_destroyed */
1334   0,                                    /* todo_flags_start */
1335   0,                                    /* todo_flags_finish */
1336   0                                     /* letter */
1337 };
1338
1339 #include "gt-ipa-reference.h"
1340