OSDN Git Service

2006-01-14 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-alias.c
1 /* Alias analysis for trees.
2    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
3    Contributed by Diego Novillo <dnovillo@redhat.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
31 #include "timevar.h"
32 #include "expr.h"
33 #include "ggc.h"
34 #include "langhooks.h"
35 #include "flags.h"
36 #include "function.h"
37 #include "diagnostic.h"
38 #include "tree-dump.h"
39 #include "tree-gimple.h"
40 #include "tree-flow.h"
41 #include "tree-inline.h"
42 #include "tree-pass.h"
43 #include "tree-ssa-structalias.h"
44 #include "convert.h"
45 #include "params.h"
46 #include "ipa-type-escape.h"
47 #include "vec.h"
48 #include "bitmap.h"
49
50 /* Obstack used to hold grouping bitmaps and other temporary bitmaps used by
51    aliasing  */
52 static bitmap_obstack alias_obstack;
53
54 /* 'true' after aliases have been computed (see compute_may_aliases).  */
55 bool aliases_computed_p;
56
57 /* Structure to map a variable to its alias set and keep track of the
58    virtual operands that will be needed to represent it.  */
59 struct alias_map_d
60 {
61   /* Variable and its alias set.  */
62   tree var;
63   HOST_WIDE_INT set;
64
65   /* Total number of virtual operands that will be needed to represent
66      all the aliases of VAR.  */
67   long total_alias_vops;
68
69   /* Nonzero if the aliases for this memory tag have been grouped
70      already.  Used in group_aliases.  */
71   unsigned int grouped_p : 1;
72
73   /* Set of variables aliased with VAR.  This is the exact same
74      information contained in VAR_ANN (VAR)->MAY_ALIASES, but in
75      bitmap form to speed up alias grouping.  */
76   bitmap may_aliases;
77 };
78
79
80 /* Counters used to display statistics on alias analysis.  */
81 struct alias_stats_d
82 {
83   unsigned int alias_queries;
84   unsigned int alias_mayalias;
85   unsigned int alias_noalias;
86   unsigned int simple_queries;
87   unsigned int simple_resolved;
88   unsigned int tbaa_queries;
89   unsigned int tbaa_resolved;
90   unsigned int structnoaddress_queries;
91   unsigned int structnoaddress_resolved;
92 };
93
94
95 /* Local variables.  */
96 static struct alias_stats_d alias_stats;
97
98 /* Local functions.  */
99 static void compute_flow_insensitive_aliasing (struct alias_info *);
100 static void dump_alias_stats (FILE *);
101 static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT, bool);
102 static tree create_memory_tag (tree type, bool is_type_tag);
103 static tree get_tmt_for (tree, struct alias_info *);
104 static tree get_nmt_for (tree);
105 static void add_may_alias (tree, tree);
106 static void replace_may_alias (tree, size_t, tree);
107 static struct alias_info *init_alias_info (void);
108 static void delete_alias_info (struct alias_info *);
109 static void compute_flow_sensitive_aliasing (struct alias_info *);
110 static void setup_pointers_and_addressables (struct alias_info *);
111 static void create_global_var (void);
112 static void maybe_create_global_var (struct alias_info *ai);
113 static void group_aliases (struct alias_info *);
114 static void set_pt_anything (tree ptr);
115
116 /* Global declarations.  */
117
118 /* Call clobbered variables in the function.  If bit I is set, then
119    REFERENCED_VARS (I) is call-clobbered.  */
120 bitmap call_clobbered_vars;
121
122 /* Addressable variables in the function.  If bit I is set, then
123    REFERENCED_VARS (I) has had its address taken.  Note that
124    CALL_CLOBBERED_VARS and ADDRESSABLE_VARS are not related.  An
125    addressable variable is not necessarily call-clobbered (e.g., a
126    local addressable whose address does not escape) and not all
127    call-clobbered variables are addressable (e.g., a local static
128    variable).  */
129 bitmap addressable_vars;
130
131 /* When the program has too many call-clobbered variables and call-sites,
132    this variable is used to represent the clobbering effects of function
133    calls.  In these cases, all the call clobbered variables in the program
134    are forced to alias this variable.  This reduces compile times by not
135    having to keep track of too many V_MAY_DEF expressions at call sites.  */
136 tree global_var;
137
138
139 /* Compute may-alias information for every variable referenced in function
140    FNDECL.
141
142    Alias analysis proceeds in 3 main phases:
143
144    1- Points-to and escape analysis.
145
146    This phase walks the use-def chains in the SSA web looking for three
147    things:
148
149         * Assignments of the form P_i = &VAR
150         * Assignments of the form P_i = malloc()
151         * Pointers and ADDR_EXPR that escape the current function.
152
153    The concept of 'escaping' is the same one used in the Java world.  When
154    a pointer or an ADDR_EXPR escapes, it means that it has been exposed
155    outside of the current function.  So, assignment to global variables,
156    function arguments and returning a pointer are all escape sites, as are
157    conversions between pointers and integers.
158
159    This is where we are currently limited.  Since not everything is renamed
160    into SSA, we lose track of escape properties when a pointer is stashed
161    inside a field in a structure, for instance.  In those cases, we are
162    assuming that the pointer does escape.
163
164    We use escape analysis to determine whether a variable is
165    call-clobbered.  Simply put, if an ADDR_EXPR escapes, then the variable
166    is call-clobbered.  If a pointer P_i escapes, then all the variables
167    pointed-to by P_i (and its memory tag) also escape.
168
169    2- Compute flow-sensitive aliases
170
171    We have two classes of memory tags.  Memory tags associated with the
172    pointed-to data type of the pointers in the program.  These tags are
173    called "type memory tag" (TMT).  The other class are those associated
174    with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that
175    when adding operands for an INDIRECT_REF *P_i, we will first check
176    whether P_i has a name tag, if it does we use it, because that will have
177    more precise aliasing information.  Otherwise, we use the standard type
178    tag.
179
180    In this phase, we go through all the pointers we found in points-to
181    analysis and create alias sets for the name memory tags associated with
182    each pointer P_i.  If P_i escapes, we mark call-clobbered the variables
183    it points to and its tag.
184
185
186    3- Compute flow-insensitive aliases
187
188    This pass will compare the alias set of every type memory tag and every
189    addressable variable found in the program.  Given a type memory tag TMT
190    and an addressable variable V.  If the alias sets of TMT and V conflict
191    (as computed by may_alias_p), then V is marked as an alias tag and added
192    to the alias set of TMT.
193
194    For instance, consider the following function:
195
196             foo (int i)
197             {
198               int *p, a, b;
199             
200               if (i > 10)
201                 p = &a;
202               else
203                 p = &b;
204             
205               *p = 3;
206               a = b + 2;
207               return *p;
208             }
209
210    After aliasing analysis has finished, the type memory tag for pointer
211    'p' will have two aliases, namely variables 'a' and 'b'.  Every time
212    pointer 'p' is dereferenced, we want to mark the operation as a
213    potential reference to 'a' and 'b'.
214
215             foo (int i)
216             {
217               int *p, a, b;
218
219               if (i_2 > 10)
220                 p_4 = &a;
221               else
222                 p_6 = &b;
223               # p_1 = PHI <p_4(1), p_6(2)>;
224
225               # a_7 = V_MAY_DEF <a_3>;
226               # b_8 = V_MAY_DEF <b_5>;
227               *p_1 = 3;
228
229               # a_9 = V_MAY_DEF <a_7>
230               # VUSE <b_8>
231               a_9 = b_8 + 2;
232
233               # VUSE <a_9>;
234               # VUSE <b_8>;
235               return *p_1;
236             }
237
238    In certain cases, the list of may aliases for a pointer may grow too
239    large.  This may cause an explosion in the number of virtual operands
240    inserted in the code.  Resulting in increased memory consumption and
241    compilation time.
242
243    When the number of virtual operands needed to represent aliased
244    loads and stores grows too large (configurable with @option{--param
245    max-aliased-vops}), alias sets are grouped to avoid severe
246    compile-time slow downs and memory consumption.  See group_aliases.  */
247
248 static void
249 compute_may_aliases (void)
250 {
251   struct alias_info *ai;
252   
253   memset (&alias_stats, 0, sizeof (alias_stats));
254
255   /* Initialize aliasing information.  */
256   ai = init_alias_info ();
257
258   /* For each pointer P_i, determine the sets of variables that P_i may
259      point-to.  For every addressable variable V, determine whether the
260      address of V escapes the current function, making V call-clobbered
261      (i.e., whether &V is stored in a global variable or if its passed as a
262      function call argument).  */
263   compute_points_to_sets (ai);
264
265   /* Collect all pointers and addressable variables, compute alias sets,
266      create memory tags for pointers and promote variables whose address is
267      not needed anymore.  */
268   setup_pointers_and_addressables (ai);
269
270   /* Compute flow-sensitive, points-to based aliasing for all the name
271      memory tags.  Note that this pass needs to be done before flow
272      insensitive analysis because it uses the points-to information
273      gathered before to mark call-clobbered type tags.  */
274   compute_flow_sensitive_aliasing (ai);
275
276   /* Compute type-based flow-insensitive aliasing for all the type
277      memory tags.  */
278   compute_flow_insensitive_aliasing (ai);
279
280   /* If the program has too many call-clobbered variables and/or function
281      calls, create .GLOBAL_VAR and use it to model call-clobbering
282      semantics at call sites.  This reduces the number of virtual operands
283      considerably, improving compile times at the expense of lost
284      aliasing precision.  */
285   maybe_create_global_var (ai);
286
287   /* Debugging dumps.  */
288   if (dump_file)
289     {
290       dump_referenced_vars (dump_file);
291       if (dump_flags & TDF_STATS)
292         dump_alias_stats (dump_file);
293       dump_points_to_info (dump_file);
294       dump_alias_info (dump_file);
295     }
296
297   /* Deallocate memory used by aliasing data structures.  */
298   delete_alias_info (ai);
299
300   {
301     block_stmt_iterator bsi;
302     basic_block bb;
303     FOR_EACH_BB (bb)
304       {
305         for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
306           {
307             update_stmt_if_modified (bsi_stmt (bsi));
308           }
309       }
310   }
311
312 }
313
314 struct tree_opt_pass pass_may_alias = 
315 {
316   "alias",                              /* name */
317   NULL,                                 /* gate */
318   compute_may_aliases,                  /* execute */
319   NULL,                                 /* sub */
320   NULL,                                 /* next */
321   0,                                    /* static_pass_number */
322   TV_TREE_MAY_ALIAS,                    /* tv_id */
323   PROP_cfg | PROP_ssa,                  /* properties_required */
324   PROP_alias,                           /* properties_provided */
325   0,                                    /* properties_destroyed */
326   0,                                    /* todo_flags_start */
327   TODO_dump_func | TODO_update_ssa
328     | TODO_ggc_collect | TODO_verify_ssa
329     | TODO_verify_stmts,                /* todo_flags_finish */
330   0                                     /* letter */
331 };
332
333
334 /* Data structure used to count the number of dereferences to PTR
335    inside an expression.  */
336 struct count_ptr_d
337 {
338   tree ptr;
339   unsigned count;
340 };
341
342
343 /* Helper for count_uses_and_derefs.  Called by walk_tree to look for
344    (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA.  */
345
346 static tree
347 count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
348 {
349   struct count_ptr_d *count_p = (struct count_ptr_d *) data;
350
351   /* Do not walk inside ADDR_EXPR nodes.  In the expression &ptr->fld,
352      pointer 'ptr' is *not* dereferenced, it is simply used to compute
353      the address of 'fld' as 'ptr + offsetof(fld)'.  */
354   if (TREE_CODE (*tp) == ADDR_EXPR)
355     {
356       *walk_subtrees = 0;
357       return NULL_TREE;
358     }
359
360   if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
361     count_p->count++;
362
363   return NULL_TREE;
364 }
365
366
367 /* Count the number of direct and indirect uses for pointer PTR in
368    statement STMT.  The two counts are stored in *NUM_USES_P and
369    *NUM_DEREFS_P respectively.  *IS_STORE_P is set to 'true' if at
370    least one of those dereferences is a store operation.  */
371
372 void
373 count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p,
374                        unsigned *num_derefs_p, bool *is_store)
375 {
376   ssa_op_iter i;
377   tree use;
378
379   *num_uses_p = 0;
380   *num_derefs_p = 0;
381   *is_store = false;
382
383   /* Find out the total number of uses of PTR in STMT.  */
384   FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
385     if (use == ptr)
386       (*num_uses_p)++;
387
388   /* Now count the number of indirect references to PTR.  This is
389      truly awful, but we don't have much choice.  There are no parent
390      pointers inside INDIRECT_REFs, so an expression like
391      '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
392      find all the indirect and direct uses of x_1 inside.  The only
393      shortcut we can take is the fact that GIMPLE only allows
394      INDIRECT_REFs inside the expressions below.  */
395   if (TREE_CODE (stmt) == MODIFY_EXPR
396       || (TREE_CODE (stmt) == RETURN_EXPR
397           && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
398       || TREE_CODE (stmt) == ASM_EXPR
399       || TREE_CODE (stmt) == CALL_EXPR)
400     {
401       tree lhs, rhs;
402
403       if (TREE_CODE (stmt) == MODIFY_EXPR)
404         {
405           lhs = TREE_OPERAND (stmt, 0);
406           rhs = TREE_OPERAND (stmt, 1);
407         }
408       else if (TREE_CODE (stmt) == RETURN_EXPR)
409         {
410           tree e = TREE_OPERAND (stmt, 0);
411           lhs = TREE_OPERAND (e, 0);
412           rhs = TREE_OPERAND (e, 1);
413         }
414       else if (TREE_CODE (stmt) == ASM_EXPR)
415         {
416           lhs = ASM_OUTPUTS (stmt);
417           rhs = ASM_INPUTS (stmt);
418         }
419       else
420         {
421           lhs = NULL_TREE;
422           rhs = stmt;
423         }
424
425       if (lhs && (TREE_CODE (lhs) == TREE_LIST || EXPR_P (lhs)))
426         {
427           struct count_ptr_d count;
428           count.ptr = ptr;
429           count.count = 0;
430           walk_tree (&lhs, count_ptr_derefs, &count, NULL);
431           *is_store = true;
432           *num_derefs_p = count.count;
433         }
434
435       if (rhs && (TREE_CODE (rhs) == TREE_LIST || EXPR_P (rhs)))
436         {
437           struct count_ptr_d count;
438           count.ptr = ptr;
439           count.count = 0;
440           walk_tree (&rhs, count_ptr_derefs, &count, NULL);
441           *num_derefs_p += count.count;
442         }
443     }
444
445   gcc_assert (*num_uses_p >= *num_derefs_p);
446 }
447
448 /* Initialize the data structures used for alias analysis.  */
449
450 static struct alias_info *
451 init_alias_info (void)
452 {
453   struct alias_info *ai;
454   referenced_var_iterator rvi;
455   tree var;
456
457   bitmap_obstack_initialize (&alias_obstack);
458   ai = XCNEW (struct alias_info);
459   ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
460   sbitmap_zero (ai->ssa_names_visited);
461   VARRAY_TREE_INIT (ai->processed_ptrs, 50, "processed_ptrs");
462   ai->written_vars = BITMAP_ALLOC (&alias_obstack);
463   ai->dereferenced_ptrs_store = BITMAP_ALLOC (&alias_obstack);
464   ai->dereferenced_ptrs_load = BITMAP_ALLOC (&alias_obstack);
465
466   /* If aliases have been computed before, clear existing information.  */
467   if (aliases_computed_p)
468     {
469       unsigned i;
470   
471       /* Similarly, clear the set of addressable variables.  In this
472          case, we can just clear the set because addressability is
473          only computed here.  */
474       bitmap_clear (addressable_vars);
475
476       /* Clear flow-insensitive alias information from each symbol.  */
477       FOR_EACH_REFERENCED_VAR (var, rvi)
478         {
479           var_ann_t ann = var_ann (var);
480           
481           ann->is_alias_tag = 0;
482           ann->may_aliases = NULL;
483           NUM_REFERENCES_CLEAR (ann);
484
485           /* Since we are about to re-discover call-clobbered
486              variables, clear the call-clobbered flag.  Variables that
487              are intrinsically call-clobbered (globals, local statics,
488              etc) will not be marked by the aliasing code, so we can't
489              remove them from CALL_CLOBBERED_VARS.  
490
491              NB: STRUCT_FIELDS are still call clobbered if they are for
492              a global variable, so we *don't* clear their call clobberedness
493              just because they are tags, though we will clear it if they
494              aren't for global variables.  */
495           if (TREE_CODE (var) == NAME_MEMORY_TAG
496               || TREE_CODE (var) == TYPE_MEMORY_TAG
497               || !is_global_var (var))
498             clear_call_clobbered (var);
499         }
500
501       /* Clear flow-sensitive points-to information from each SSA name.  */
502       for (i = 1; i < num_ssa_names; i++)
503         {
504           tree name = ssa_name (i);
505
506           if (!name || !POINTER_TYPE_P (TREE_TYPE (name)))
507             continue;
508
509           if (SSA_NAME_PTR_INFO (name))
510             {
511               struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
512
513               /* Clear all the flags but keep the name tag to
514                  avoid creating new temporaries unnecessarily.  If
515                  this pointer is found to point to a subset or
516                  superset of its former points-to set, then a new
517                  tag will need to be created in create_name_tags.  */
518               pi->pt_anything = 0;
519               pi->pt_null = 0;
520               pi->value_escapes_p = 0;
521               pi->is_dereferenced = 0;
522               if (pi->pt_vars)
523                 bitmap_clear (pi->pt_vars);
524             }
525         }
526     }
527
528   /* Next time, we will need to reset alias information.  */
529   aliases_computed_p = true;
530
531   return ai;
532 }
533
534
535 /* Deallocate memory used by alias analysis.  */
536
537 static void
538 delete_alias_info (struct alias_info *ai)
539 {
540   size_t i;
541   referenced_var_iterator rvi;
542   tree var;
543
544   sbitmap_free (ai->ssa_names_visited);
545   ai->processed_ptrs = NULL;
546
547   for (i = 0; i < ai->num_addressable_vars; i++)
548     free (ai->addressable_vars[i]);
549   
550   FOR_EACH_REFERENCED_VAR(var, rvi)
551     {
552       var_ann_t ann = var_ann (var);
553       NUM_REFERENCES_CLEAR (ann);
554     }
555
556   free (ai->addressable_vars);
557
558   for (i = 0; i < ai->num_pointers; i++)
559     free (ai->pointers[i]);
560   free (ai->pointers);
561
562   BITMAP_FREE (ai->written_vars);
563   BITMAP_FREE (ai->dereferenced_ptrs_store);
564   BITMAP_FREE (ai->dereferenced_ptrs_load);
565   bitmap_obstack_release (&alias_obstack);
566   free (ai);
567
568   delete_points_to_sets ();
569 }
570
571 /* Create name tags for all the pointers that have been dereferenced.
572    We only create a name tag for a pointer P if P is found to point to
573    a set of variables (so that we can alias them to *P) or if it is
574    the result of a call to malloc (which means that P cannot point to
575    anything else nor alias any other variable).
576
577    If two pointers P and Q point to the same set of variables, they
578    are assigned the same name tag.  */
579
580 static void
581 create_name_tags (void)
582 {
583   size_t i;
584   VEC (tree, heap) *with_ptvars = NULL;
585   tree ptr;
586
587   /* Collect the list of pointers with a non-empty points to set.  */
588   for (i = 1; i < num_ssa_names; i++)
589     {
590       tree ptr = ssa_name (i);
591       struct ptr_info_def *pi;
592
593       if (!ptr
594           || !POINTER_TYPE_P (TREE_TYPE (ptr))
595           || !SSA_NAME_PTR_INFO (ptr))
596         continue;
597
598       pi = SSA_NAME_PTR_INFO (ptr);
599
600       if (pi->pt_anything || !pi->is_dereferenced)
601         {
602           /* No name tags for pointers that have not been
603              dereferenced or point to an arbitrary location.  */
604           pi->name_mem_tag = NULL_TREE;
605           continue;
606         }
607
608       /* Set pt_anything on the pointers without pt_vars filled in so
609          that they are assigned a type tag.  */
610       
611       if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars)) 
612         VEC_safe_push (tree, heap, with_ptvars, ptr);
613       else
614         set_pt_anything (ptr);
615     }
616   
617   /* If we didn't find any pointers with pt_vars set, we're done.  */
618   if (!with_ptvars)
619     return;
620
621   /* Now go through the pointers with pt_vars, and find a name tag
622      with the same pt_vars as this pointer, or create one if one
623      doesn't exist.  */
624   for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++)
625     {
626       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
627       size_t j;
628       tree ptr2;
629       tree old_name_tag = pi->name_mem_tag;
630       
631       /* If PTR points to a set of variables, check if we don't
632          have another pointer Q with the same points-to set before
633          creating a tag.  If so, use Q's tag instead of creating a
634          new one.
635          
636          This is important for not creating unnecessary symbols
637          and also for copy propagation.  If we ever need to
638          propagate PTR into Q or vice-versa, we would run into
639          problems if they both had different name tags because
640          they would have different SSA version numbers (which
641          would force us to take the name tags in and out of SSA).  */
642       for (j = 0; j < i && VEC_iterate (tree, with_ptvars, j, ptr2); j++)
643         {
644           struct ptr_info_def *qi = SSA_NAME_PTR_INFO (ptr2);
645           
646           if (bitmap_equal_p (pi->pt_vars, qi->pt_vars))
647             {
648               pi->name_mem_tag = qi->name_mem_tag;
649               break;
650             }
651         }
652       
653       /* If we didn't find a pointer with the same points-to set
654          as PTR, create a new name tag if needed.  */
655       if (pi->name_mem_tag == NULL_TREE)
656         pi->name_mem_tag = get_nmt_for (ptr);
657       
658       /* If the new name tag computed for PTR is different than
659          the old name tag that it used to have, then the old tag
660          needs to be removed from the IL, so we mark it for
661          renaming.  */
662       if (old_name_tag && old_name_tag != pi->name_mem_tag)
663         mark_sym_for_renaming (old_name_tag);
664       
665       TREE_THIS_VOLATILE (pi->name_mem_tag)
666         |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
667       
668       /* Mark the new name tag for renaming.  */
669       mark_sym_for_renaming (pi->name_mem_tag);
670     }
671
672   VEC_free (tree, heap, with_ptvars);
673 }
674
675
676 /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
677    the name memory tag (NMT) associated with P_i.  If P_i escapes, then its
678    name tag and the variables it points-to are call-clobbered.  Finally, if
679    P_i escapes and we could not determine where it points to, then all the
680    variables in the same alias set as *P_i are marked call-clobbered.  This
681    is necessary because we must assume that P_i may take the address of any
682    variable in the same alias set.  */
683
684 static void
685 compute_flow_sensitive_aliasing (struct alias_info *ai)
686 {
687   size_t i;
688   
689   for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
690     {
691       tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
692       if (!find_what_p_points_to (ptr))
693         set_pt_anything (ptr);
694     }
695
696   create_name_tags ();
697
698   for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
699     {
700       unsigned j;
701       tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
702       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
703       var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr));
704       bitmap_iterator bi;
705
706       if (pi->value_escapes_p || pi->pt_anything)
707         {
708           /* If PTR escapes or may point to anything, then its associated
709              memory tags and pointed-to variables are call-clobbered.  */
710           if (pi->name_mem_tag)
711             mark_call_clobbered (pi->name_mem_tag);
712
713           if (v_ann->type_mem_tag)
714             mark_call_clobbered (v_ann->type_mem_tag);
715
716           if (pi->pt_vars)
717             EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
718               mark_call_clobbered (referenced_var (j));
719         }
720
721       /* Set up aliasing information for PTR's name memory tag (if it has
722          one).  Note that only pointers that have been dereferenced will
723          have a name memory tag.  */
724       if (pi->name_mem_tag && pi->pt_vars)
725         EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
726           {
727             add_may_alias (pi->name_mem_tag, referenced_var (j));
728             add_may_alias (v_ann->type_mem_tag, referenced_var (j));
729           }
730
731       /* If the name tag is call clobbered, so is the type tag
732          associated with the base VAR_DECL.  */
733       if (pi->name_mem_tag
734           && v_ann->type_mem_tag
735           && is_call_clobbered (pi->name_mem_tag))
736         mark_call_clobbered (v_ann->type_mem_tag);
737     }
738 }
739
740
741 /* Compute type-based alias sets.  Traverse all the pointers and
742    addressable variables found in setup_pointers_and_addressables.
743    
744    For every pointer P in AI->POINTERS and addressable variable V in
745    AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's type
746    memory tag (TMT) if their alias sets conflict.  V is then marked as
747    an alias tag so that the operand scanner knows that statements
748    containing V have aliased operands.  */
749
750 static void
751 compute_flow_insensitive_aliasing (struct alias_info *ai)
752 {
753   size_t i;
754
755   /* Initialize counter for the total number of virtual operands that
756      aliasing will introduce.  When AI->TOTAL_ALIAS_VOPS goes beyond the
757      threshold set by --params max-alias-vops, we enable alias
758      grouping.  */
759   ai->total_alias_vops = 0;
760
761   /* For every pointer P, determine which addressable variables may alias
762      with P's type memory tag.  */
763   for (i = 0; i < ai->num_pointers; i++)
764     {
765       size_t j;
766       struct alias_map_d *p_map = ai->pointers[i];
767       tree tag = var_ann (p_map->var)->type_mem_tag;
768       var_ann_t tag_ann = var_ann (tag);
769
770       p_map->total_alias_vops = 0;
771       p_map->may_aliases = BITMAP_ALLOC (&alias_obstack);
772
773       for (j = 0; j < ai->num_addressable_vars; j++)
774         {
775           struct alias_map_d *v_map;
776           var_ann_t v_ann;
777           tree var;
778           bool tag_stored_p, var_stored_p;
779           
780           v_map = ai->addressable_vars[j];
781           var = v_map->var;
782           v_ann = var_ann (var);
783
784           /* Skip memory tags and variables that have never been
785              written to.  We also need to check if the variables are
786              call-clobbered because they may be overwritten by
787              function calls.
788
789              Note this is effectively random accessing elements in
790              the sparse bitset, which can be highly inefficient.
791              So we first check the call_clobbered status of the
792              tag and variable before querying the bitmap.  */
793           tag_stored_p = is_call_clobbered (tag)
794                          || bitmap_bit_p (ai->written_vars, DECL_UID (tag));
795           var_stored_p = is_call_clobbered (var)
796                          || bitmap_bit_p (ai->written_vars, DECL_UID (var));
797           if (!tag_stored_p && !var_stored_p)
798             continue;
799              
800           if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false))
801             {
802               size_t num_tag_refs, num_var_refs;
803
804               num_tag_refs = NUM_REFERENCES (tag_ann);
805               num_var_refs = NUM_REFERENCES (v_ann);
806
807               /* Add VAR to TAG's may-aliases set.  */
808
809               /* We should never have a var with subvars here, because
810                  they shouldn't get into the set of addressable vars */
811               gcc_assert (!var_can_have_subvars (var)
812                           || get_subvars_for_var (var) == NULL);
813
814               add_may_alias (tag, var);
815               /* Update the bitmap used to represent TAG's alias set
816                  in case we need to group aliases.  */
817               bitmap_set_bit (p_map->may_aliases, DECL_UID (var));
818
819               /* Update the total number of virtual operands due to
820                  aliasing.  Since we are adding one more alias to TAG's
821                  may-aliases set, the total number of virtual operands due
822                  to aliasing will be increased by the number of references
823                  made to VAR and TAG (every reference to TAG will also
824                  count as a reference to VAR).  */
825               ai->total_alias_vops += (num_var_refs + num_tag_refs);
826               p_map->total_alias_vops += (num_var_refs + num_tag_refs);
827
828
829             }
830         }
831     }
832
833   /* Since this analysis is based exclusively on symbols, it fails to
834      handle cases where two pointers P and Q have different memory
835      tags with conflicting alias set numbers but no aliased symbols in
836      common.
837
838      For example, suppose that we have two memory tags TMT.1 and TMT.2
839      such that
840      
841                 may-aliases (TMT.1) = { a }
842                 may-aliases (TMT.2) = { b }
843
844      and the alias set number of TMT.1 conflicts with that of TMT.2.
845      Since they don't have symbols in common, loads and stores from
846      TMT.1 and TMT.2 will seem independent of each other, which will
847      lead to the optimizers making invalid transformations (see
848      testsuite/gcc.c-torture/execute/pr15262-[12].c).
849
850      To avoid this problem, we do a final traversal of AI->POINTERS
851      looking for pairs of pointers that have no aliased symbols in
852      common and yet have conflicting alias set numbers.  */
853   for (i = 0; i < ai->num_pointers; i++)
854     {
855       size_t j;
856       struct alias_map_d *p_map1 = ai->pointers[i];
857       tree tag1 = var_ann (p_map1->var)->type_mem_tag;
858       bitmap may_aliases1 = p_map1->may_aliases;
859
860       for (j = i + 1; j < ai->num_pointers; j++)
861         {
862           struct alias_map_d *p_map2 = ai->pointers[j];
863           tree tag2 = var_ann (p_map2->var)->type_mem_tag;
864           bitmap may_aliases2 = p_map2->may_aliases;
865
866           /* If the pointers may not point to each other, do nothing.  */
867           if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
868             continue;
869
870           /* The two pointers may alias each other.  If they already have
871              symbols in common, do nothing.  */
872           if (bitmap_intersect_p (may_aliases1, may_aliases2))
873             continue;
874
875           if (!bitmap_empty_p (may_aliases2))
876             {
877               unsigned int k;
878               bitmap_iterator bi;
879
880               /* Add all the aliases for TAG2 into TAG1's alias set.
881                  FIXME, update grouping heuristic counters.  */
882               EXECUTE_IF_SET_IN_BITMAP (may_aliases2, 0, k, bi)
883                 add_may_alias (tag1, referenced_var (k));
884               bitmap_ior_into (may_aliases1, may_aliases2);
885             }
886           else
887             {
888               /* Since TAG2 does not have any aliases of its own, add
889                  TAG2 itself to the alias set of TAG1.  */
890               add_may_alias (tag1, tag2);
891               bitmap_set_bit (may_aliases1, DECL_UID (tag2));
892             }
893         }
894     }
895   
896   if (dump_file)
897     fprintf (dump_file, "\n%s: Total number of aliased vops: %ld\n",
898              get_name (current_function_decl),
899              ai->total_alias_vops);
900
901   /* Determine if we need to enable alias grouping.  */
902   if (ai->total_alias_vops >= MAX_ALIASED_VOPS)
903     group_aliases (ai);
904 }
905
906
907 /* Comparison function for qsort used in group_aliases.  */
908
909 static int
910 total_alias_vops_cmp (const void *p, const void *q)
911 {
912   const struct alias_map_d **p1 = (const struct alias_map_d **)p;
913   const struct alias_map_d **p2 = (const struct alias_map_d **)q;
914   long n1 = (*p1)->total_alias_vops;
915   long n2 = (*p2)->total_alias_vops;
916
917   /* We want to sort in descending order.  */
918   return (n1 > n2 ? -1 : (n1 == n2) ? 0 : 1);
919 }
920
921 /* Group all the aliases for TAG to make TAG represent all the
922    variables in its alias set.  Update the total number
923    of virtual operands due to aliasing (AI->TOTAL_ALIAS_VOPS).  This
924    function will make TAG be the unique alias tag for all the
925    variables in its may-aliases.  So, given:
926
927         may-aliases(TAG) = { V1, V2, V3 }
928
929    This function will group the variables into:
930
931         may-aliases(V1) = { TAG }
932         may-aliases(V2) = { TAG }
933         may-aliases(V2) = { TAG }  */
934
935 static void
936 group_aliases_into (tree tag, bitmap tag_aliases, struct alias_info *ai)
937 {
938   unsigned int i;
939   var_ann_t tag_ann = var_ann (tag);
940   size_t num_tag_refs = NUM_REFERENCES (tag_ann);
941   bitmap_iterator bi;
942
943   EXECUTE_IF_SET_IN_BITMAP (tag_aliases, 0, i, bi)
944     {
945       tree var = referenced_var (i);
946       var_ann_t ann = var_ann (var);
947
948       /* Make TAG the unique alias of VAR.  */
949       ann->is_alias_tag = 0;
950       ann->may_aliases = NULL;
951
952       /* Note that VAR and TAG may be the same if the function has no
953          addressable variables (see the discussion at the end of
954          setup_pointers_and_addressables).  */
955       if (var != tag)
956         add_may_alias (var, tag);
957
958       /* Reduce total number of virtual operands contributed
959          by TAG on behalf of VAR.  Notice that the references to VAR
960          itself won't be removed.  We will merely replace them with
961          references to TAG.  */
962       ai->total_alias_vops -= num_tag_refs;
963     }
964
965   /* We have reduced the number of virtual operands that TAG makes on
966      behalf of all the variables formerly aliased with it.  However,
967      we have also "removed" all the virtual operands for TAG itself,
968      so we add them back.  */
969   ai->total_alias_vops += num_tag_refs;
970
971   /* TAG no longer has any aliases.  */
972   tag_ann->may_aliases = NULL;
973 }
974
975
976 /* Group may-aliases sets to reduce the number of virtual operands due
977    to aliasing.
978
979      1- Sort the list of pointers in decreasing number of contributed
980         virtual operands.
981
982      2- Take the first entry in AI->POINTERS and revert the role of
983         the memory tag and its aliases.  Usually, whenever an aliased
984         variable Vi is found to alias with a memory tag T, we add Vi
985         to the may-aliases set for T.  Meaning that after alias
986         analysis, we will have:
987
988                 may-aliases(T) = { V1, V2, V3, ..., Vn }
989
990         This means that every statement that references T, will get 'n'
991         virtual operands for each of the Vi tags.  But, when alias
992         grouping is enabled, we make T an alias tag and add it to the
993         alias set of all the Vi variables:
994
995                 may-aliases(V1) = { T }
996                 may-aliases(V2) = { T }
997                 ...
998                 may-aliases(Vn) = { T }
999
1000         This has two effects: (a) statements referencing T will only get
1001         a single virtual operand, and, (b) all the variables Vi will now
1002         appear to alias each other.  So, we lose alias precision to
1003         improve compile time.  But, in theory, a program with such a high
1004         level of aliasing should not be very optimizable in the first
1005         place.
1006
1007      3- Since variables may be in the alias set of more than one
1008         memory tag, the grouping done in step (2) needs to be extended
1009         to all the memory tags that have a non-empty intersection with
1010         the may-aliases set of tag T.  For instance, if we originally
1011         had these may-aliases sets:
1012
1013                 may-aliases(T) = { V1, V2, V3 }
1014                 may-aliases(R) = { V2, V4 }
1015
1016         In step (2) we would have reverted the aliases for T as:
1017
1018                 may-aliases(V1) = { T }
1019                 may-aliases(V2) = { T }
1020                 may-aliases(V3) = { T }
1021
1022         But note that now V2 is no longer aliased with R.  We could
1023         add R to may-aliases(V2), but we are in the process of
1024         grouping aliases to reduce virtual operands so what we do is
1025         add V4 to the grouping to obtain:
1026
1027                 may-aliases(V1) = { T }
1028                 may-aliases(V2) = { T }
1029                 may-aliases(V3) = { T }
1030                 may-aliases(V4) = { T }
1031
1032      4- If the total number of virtual operands due to aliasing is
1033         still above the threshold set by max-alias-vops, go back to (2).  */
1034
1035 static void
1036 group_aliases (struct alias_info *ai)
1037 {
1038   size_t i;
1039
1040   /* Sort the POINTERS array in descending order of contributed
1041      virtual operands.  */
1042   qsort (ai->pointers, ai->num_pointers, sizeof (struct alias_map_d *),
1043          total_alias_vops_cmp);
1044
1045   /* For every pointer in AI->POINTERS, reverse the roles of its tag
1046      and the tag's may-aliases set.  */
1047   for (i = 0; i < ai->num_pointers; i++)
1048     {
1049       size_t j;
1050       tree tag1 = var_ann (ai->pointers[i]->var)->type_mem_tag;
1051       bitmap tag1_aliases = ai->pointers[i]->may_aliases;
1052
1053       /* Skip tags that have been grouped already.  */
1054       if (ai->pointers[i]->grouped_p)
1055         continue;
1056
1057       /* See if TAG1 had any aliases in common with other type tags.
1058          If we find a TAG2 with common aliases with TAG1, add TAG2's
1059          aliases into TAG1.  */
1060       for (j = i + 1; j < ai->num_pointers; j++)
1061         {
1062           bitmap tag2_aliases = ai->pointers[j]->may_aliases;
1063
1064           if (bitmap_intersect_p (tag1_aliases, tag2_aliases))
1065             {
1066               tree tag2 = var_ann (ai->pointers[j]->var)->type_mem_tag;
1067
1068               bitmap_ior_into (tag1_aliases, tag2_aliases);
1069
1070               /* TAG2 does not need its aliases anymore.  */
1071               bitmap_clear (tag2_aliases);
1072               var_ann (tag2)->may_aliases = NULL;
1073
1074               /* TAG1 is the unique alias of TAG2.  */
1075               add_may_alias (tag2, tag1);
1076
1077               ai->pointers[j]->grouped_p = true;
1078             }
1079         }
1080
1081       /* Now group all the aliases we collected into TAG1.  */
1082       group_aliases_into (tag1, tag1_aliases, ai);
1083
1084       /* If we've reduced total number of virtual operands below the
1085          threshold, stop.  */
1086       if (ai->total_alias_vops < MAX_ALIASED_VOPS)
1087         break;
1088     }
1089
1090   /* Finally, all the variables that have been grouped cannot be in
1091      the may-alias set of name memory tags.  Suppose that we have
1092      grouped the aliases in this code so that may-aliases(a) = TMT.20
1093
1094         p_5 = &a;
1095         ...
1096         # a_9 = V_MAY_DEF <a_8>
1097         p_5->field = 0
1098         ... Several modifications to TMT.20 ... 
1099         # VUSE <a_9>
1100         x_30 = p_5->field
1101
1102      Since p_5 points to 'a', the optimizers will try to propagate 0
1103      into p_5->field, but that is wrong because there have been
1104      modifications to 'TMT.20' in between.  To prevent this we have to
1105      replace 'a' with 'TMT.20' in the name tag of p_5.  */
1106   for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
1107     {
1108       size_t j;
1109       tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
1110       tree name_tag = SSA_NAME_PTR_INFO (ptr)->name_mem_tag;
1111       VEC(tree,gc) *aliases;
1112       tree alias;
1113       
1114       if (name_tag == NULL_TREE)
1115         continue;
1116
1117       aliases = var_ann (name_tag)->may_aliases;
1118       for (j = 0; VEC_iterate (tree, aliases, j, alias); j++)
1119         {
1120           var_ann_t ann = var_ann (alias);
1121
1122           if ((!MTAG_P (alias)
1123                || TREE_CODE (alias) == STRUCT_FIELD_TAG)
1124               && ann->may_aliases)
1125             {
1126               tree new_alias;
1127
1128               gcc_assert (VEC_length (tree, ann->may_aliases) == 1);
1129
1130               new_alias = VEC_index (tree, ann->may_aliases, 0);
1131               replace_may_alias (name_tag, j, new_alias);
1132             }
1133         }
1134     }
1135
1136   if (dump_file)
1137     fprintf (dump_file,
1138              "%s: Total number of aliased vops after grouping: %ld%s\n",
1139              get_name (current_function_decl),
1140              ai->total_alias_vops,
1141              (ai->total_alias_vops < 0) ? " (negative values are OK)" : "");
1142 }
1143
1144
1145 /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS.  */
1146
1147 static void
1148 create_alias_map_for (tree var, struct alias_info *ai)
1149 {
1150   struct alias_map_d *alias_map;
1151   alias_map = XCNEW (struct alias_map_d);
1152   alias_map->var = var;
1153   alias_map->set = get_alias_set (var);
1154   ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
1155 }
1156
1157
1158 /* Create memory tags for all the dereferenced pointers and build the
1159    ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias
1160    sets.  Based on the address escape and points-to information collected
1161    earlier, this pass will also clear the TREE_ADDRESSABLE flag from those
1162    variables whose address is not needed anymore.  */
1163
1164 static void
1165 setup_pointers_and_addressables (struct alias_info *ai)
1166 {
1167   size_t n_vars, num_addressable_vars, num_pointers;
1168   referenced_var_iterator rvi;
1169   tree var;
1170   VEC (tree, heap) *varvec = NULL;
1171   safe_referenced_var_iterator srvi;
1172
1173   /* Size up the arrays ADDRESSABLE_VARS and POINTERS.  */
1174   num_addressable_vars = num_pointers = 0;
1175   
1176   FOR_EACH_REFERENCED_VAR (var, rvi)
1177     {
1178       if (may_be_aliased (var))
1179         num_addressable_vars++;
1180
1181       if (POINTER_TYPE_P (TREE_TYPE (var)))
1182         {
1183           /* Since we don't keep track of volatile variables, assume that
1184              these pointers are used in indirect store operations.  */
1185           if (TREE_THIS_VOLATILE (var))
1186             bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
1187
1188           num_pointers++;
1189         }
1190     }
1191
1192   /* Create ADDRESSABLE_VARS and POINTERS.  Note that these arrays are
1193      always going to be slightly bigger than we actually need them
1194      because some TREE_ADDRESSABLE variables will be marked
1195      non-addressable below and only pointers with unique type tags are
1196      going to be added to POINTERS.  */
1197   ai->addressable_vars = XCNEWVEC (struct alias_map_d *, num_addressable_vars);
1198   ai->pointers = XCNEWVEC (struct alias_map_d *, num_pointers);
1199   ai->num_addressable_vars = 0;
1200   ai->num_pointers = 0;
1201
1202   /* Since we will be creating type memory tags within this loop, cache the
1203      value of NUM_REFERENCED_VARS to avoid processing the additional tags
1204      unnecessarily.  */
1205   n_vars = num_referenced_vars;
1206
1207   FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi)
1208     {
1209       var_ann_t v_ann = var_ann (var);
1210       subvar_t svars;
1211
1212       /* Name memory tags already have flow-sensitive aliasing
1213          information, so they need not be processed by
1214          compute_flow_insensitive_aliasing.  Similarly, type memory
1215          tags are already accounted for when we process their
1216          associated pointer. 
1217       
1218          Structure fields, on the other hand, have to have some of this
1219          information processed for them, but it's pointless to mark them
1220          non-addressable (since they are fake variables anyway).  */
1221       if (MTAG_P (var) && TREE_CODE (var) != STRUCT_FIELD_TAG)
1222         continue;
1223
1224       /* Remove the ADDRESSABLE flag from every addressable variable whose
1225          address is not needed anymore.  This is caused by the propagation
1226          of ADDR_EXPR constants into INDIRECT_REF expressions and the
1227          removal of dead pointer assignments done by the early scalar
1228          cleanup passes.  */
1229       if (TREE_ADDRESSABLE (var))
1230         {
1231           if (!bitmap_bit_p (addressable_vars, DECL_UID (var))
1232               && TREE_CODE (var) != RESULT_DECL
1233               && !is_global_var (var))
1234             {
1235               bool okay_to_mark = true;
1236
1237               /* Since VAR is now a regular GIMPLE register, we will need
1238                  to rename VAR into SSA afterwards.  */
1239               mark_sym_for_renaming (var);
1240
1241               /* If VAR can have sub-variables, and any of its
1242                  sub-variables has its address taken, then we cannot
1243                  remove the addressable flag from VAR.  */
1244               if (var_can_have_subvars (var)
1245                   && (svars = get_subvars_for_var (var)))
1246                 {
1247                   subvar_t sv;
1248
1249                   for (sv = svars; sv; sv = sv->next)
1250                     {         
1251                       if (bitmap_bit_p (addressable_vars, DECL_UID (sv->var)))
1252                         okay_to_mark = false;
1253                       mark_sym_for_renaming (sv->var);
1254                     }
1255                 }
1256
1257               /* The address of VAR is not needed, remove the
1258                  addressable bit, so that it can be optimized as a
1259                  regular variable.  */
1260               if (okay_to_mark)
1261                 mark_non_addressable (var);
1262             }
1263         }
1264
1265       /* Global variables and addressable locals may be aliased.  Create an
1266          entry in ADDRESSABLE_VARS for VAR.  */
1267       if (may_be_aliased (var)    
1268           && (!var_can_have_subvars (var) 
1269               || get_subvars_for_var (var) == NULL))
1270         {
1271           create_alias_map_for (var, ai);
1272           mark_sym_for_renaming (var);
1273         }
1274
1275       /* Add pointer variables that have been dereferenced to the POINTERS
1276          array and create a type memory tag for them.  */
1277       if (POINTER_TYPE_P (TREE_TYPE (var)))
1278         {
1279           if ((bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var))
1280                || bitmap_bit_p (ai->dereferenced_ptrs_load, DECL_UID (var))))
1281             {
1282               tree tag;
1283               var_ann_t t_ann;
1284
1285               /* If pointer VAR still doesn't have a memory tag
1286                  associated with it, create it now or re-use an
1287                  existing one.  */
1288               tag = get_tmt_for (var, ai);
1289               t_ann = var_ann (tag);
1290
1291               /* The type tag will need to be renamed into SSA
1292                  afterwards. Note that we cannot do this inside
1293                  get_tmt_for because aliasing may run multiple times
1294                  and we only create type tags the first time.  */
1295               mark_sym_for_renaming (tag);
1296
1297               /* Similarly, if pointer VAR used to have another type
1298                  tag, we will need to process it in the renamer to
1299                  remove the stale virtual operands.  */
1300               if (v_ann->type_mem_tag)
1301                 mark_sym_for_renaming (v_ann->type_mem_tag);
1302
1303               /* Associate the tag with pointer VAR.  */
1304               v_ann->type_mem_tag = tag;
1305
1306               /* If pointer VAR has been used in a store operation,
1307                  then its memory tag must be marked as written-to.  */
1308               if (bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var)))
1309                 bitmap_set_bit (ai->written_vars, DECL_UID (tag));
1310
1311               /* If pointer VAR is a global variable or a PARM_DECL,
1312                  then its memory tag should be considered a global
1313                  variable.  */
1314               if (TREE_CODE (var) == PARM_DECL || is_global_var (var))
1315                 mark_call_clobbered (tag);
1316
1317               /* All the dereferences of pointer VAR count as
1318                  references of TAG.  Since TAG can be associated with
1319                  several pointers, add the dereferences of VAR to the
1320                  TAG.  */
1321               NUM_REFERENCES_SET (t_ann, 
1322                                   NUM_REFERENCES (t_ann)
1323                                   + NUM_REFERENCES (v_ann));
1324             }
1325           else
1326             {
1327               /* The pointer has not been dereferenced.  If it had a
1328                  type memory tag, remove it and mark the old tag for
1329                  renaming to remove it out of the IL.  */
1330               var_ann_t ann = var_ann (var);
1331               tree tag = ann->type_mem_tag;
1332               if (tag)
1333                 {
1334                   mark_sym_for_renaming (tag);
1335                   ann->type_mem_tag = NULL_TREE;
1336                 }
1337             }
1338         }
1339     }
1340   VEC_free (tree, heap, varvec);
1341 }
1342
1343
1344 /* Determine whether to use .GLOBAL_VAR to model call clobbering semantics. At
1345    every call site, we need to emit V_MAY_DEF expressions to represent the
1346    clobbering effects of the call for variables whose address escapes the
1347    current function.
1348
1349    One approach is to group all call-clobbered variables into a single
1350    representative that is used as an alias of every call-clobbered variable
1351    (.GLOBAL_VAR).  This works well, but it ties the optimizer hands because
1352    references to any call clobbered variable is a reference to .GLOBAL_VAR.
1353
1354    The second approach is to emit a clobbering V_MAY_DEF for every 
1355    call-clobbered variable at call sites.  This is the preferred way in terms 
1356    of optimization opportunities but it may create too many V_MAY_DEF operands
1357    if there are many call clobbered variables and function calls in the 
1358    function.
1359
1360    To decide whether or not to use .GLOBAL_VAR we multiply the number of
1361    function calls found by the number of call-clobbered variables.  If that
1362    product is beyond a certain threshold, as determined by the parameterized
1363    values shown below, we use .GLOBAL_VAR.
1364
1365    FIXME.  This heuristic should be improved.  One idea is to use several
1366    .GLOBAL_VARs of different types instead of a single one.  The thresholds
1367    have been derived from a typical bootstrap cycle, including all target
1368    libraries. Compile times were found increase by ~1% compared to using
1369    .GLOBAL_VAR.  */
1370
1371 static void
1372 maybe_create_global_var (struct alias_info *ai)
1373 {
1374   unsigned i, n_clobbered;
1375   bitmap_iterator bi;
1376   
1377   /* No need to create it, if we have one already.  */
1378   if (global_var == NULL_TREE)
1379     {
1380       /* Count all the call-clobbered variables.  */
1381       n_clobbered = 0;
1382       EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
1383         {
1384           n_clobbered++;
1385         }
1386
1387       /* If the number of virtual operands that would be needed to
1388          model all the call-clobbered variables is larger than
1389          GLOBAL_VAR_THRESHOLD, create .GLOBAL_VAR.
1390
1391          Also create .GLOBAL_VAR if there are no call-clobbered
1392          variables and the program contains a mixture of pure/const
1393          and regular function calls.  This is to avoid the problem
1394          described in PR 20115:
1395
1396               int X;
1397               int func_pure (void) { return X; }
1398               int func_non_pure (int a) { X += a; }
1399               int foo ()
1400               {
1401                 int a = func_pure ();
1402                 func_non_pure (a);
1403                 a = func_pure ();
1404                 return a;
1405               }
1406
1407          Since foo() has no call-clobbered variables, there is
1408          no relationship between the calls to func_pure and
1409          func_non_pure.  Since func_pure has no side-effects, value
1410          numbering optimizations elide the second call to func_pure.
1411          So, if we have some pure/const and some regular calls in the
1412          program we create .GLOBAL_VAR to avoid missing these
1413          relations.  */
1414       if (ai->num_calls_found * n_clobbered >= (size_t) GLOBAL_VAR_THRESHOLD
1415           || (n_clobbered == 0
1416               && ai->num_calls_found > 0
1417               && ai->num_pure_const_calls_found > 0
1418               && ai->num_calls_found > ai->num_pure_const_calls_found))
1419         create_global_var ();
1420     }
1421
1422   /* Mark all call-clobbered symbols for renaming.  Since the initial
1423      rewrite into SSA ignored all call sites, we may need to rename
1424      .GLOBAL_VAR and the call-clobbered variables.   */
1425   EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
1426     {
1427       tree var = referenced_var (i);
1428
1429       /* If the function has calls to clobbering functions and
1430          .GLOBAL_VAR has been created, make it an alias for all
1431          call-clobbered variables.  */
1432       if (global_var && var != global_var)
1433         {
1434           subvar_t svars;
1435           add_may_alias (var, global_var);
1436           if (var_can_have_subvars (var)
1437               && (svars = get_subvars_for_var (var)))
1438             {
1439               subvar_t sv;
1440               for (sv = svars; sv; sv = sv->next)
1441                 mark_sym_for_renaming (sv->var);
1442             }
1443         }
1444       
1445       mark_sym_for_renaming (var);
1446     }
1447 }
1448
1449
1450 /* Return TRUE if pointer PTR may point to variable VAR.
1451    
1452    MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR
1453         This is needed because when checking for type conflicts we are
1454         interested in the alias set of the memory location pointed-to by
1455         PTR.  The alias set of PTR itself is irrelevant.
1456    
1457    VAR_ALIAS_SET is the alias set for VAR.  */
1458
1459 static bool
1460 may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set,
1461              tree var, HOST_WIDE_INT var_alias_set,
1462              bool alias_set_only)
1463 {
1464   tree mem;
1465
1466   alias_stats.alias_queries++;
1467   alias_stats.simple_queries++;
1468
1469   /* By convention, a variable cannot alias itself.  */
1470   mem = var_ann (ptr)->type_mem_tag;
1471   if (mem == var)
1472     {
1473       alias_stats.alias_noalias++;
1474       alias_stats.simple_resolved++;
1475       return false;
1476     }
1477   
1478   /* If -fargument-noalias-global is >1, pointer arguments may
1479      not point to global variables.  */
1480   if (flag_argument_noalias > 1 && is_global_var (var)
1481       && TREE_CODE (ptr) == PARM_DECL)
1482     {
1483       alias_stats.alias_noalias++;
1484       alias_stats.simple_resolved++;
1485       return false;
1486     }
1487
1488   /* If either MEM or VAR is a read-only global and the other one
1489      isn't, then PTR cannot point to VAR.  */
1490   if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var))
1491       || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem)))
1492     {
1493       alias_stats.alias_noalias++;
1494       alias_stats.simple_resolved++;
1495       return false;
1496     }
1497
1498   gcc_assert (TREE_CODE (mem) == TYPE_MEMORY_TAG);
1499
1500   alias_stats.tbaa_queries++;
1501
1502   /* If the alias sets don't conflict then MEM cannot alias VAR.  */
1503   if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
1504     {
1505       alias_stats.alias_noalias++;
1506       alias_stats.tbaa_resolved++;
1507       return false;
1508     }
1509
1510   /* If var is a record or union type, ptr cannot point into var
1511      unless there is some operation explicit address operation in the
1512      program that can reference a field of the ptr's dereferenced
1513      type.  This also assumes that the types of both var and ptr are
1514      contained within the compilation unit, and that there is no fancy
1515      addressing arithmetic associated with any of the types
1516      involved.  */
1517
1518   if ((mem_alias_set != 0) && (var_alias_set != 0))
1519     {
1520       tree ptr_type = TREE_TYPE (ptr);
1521       tree var_type = TREE_TYPE (var);
1522       
1523       /* The star count is -1 if the type at the end of the pointer_to 
1524          chain is not a record or union type. */ 
1525       if ((!alias_set_only) && 
1526           ipa_type_escape_star_count_of_interesting_type (var_type) >= 0)
1527         {
1528           int ptr_star_count = 0;
1529           
1530           /* Ipa_type_escape_star_count_of_interesting_type is a little to
1531              restrictive for the pointer type, need to allow pointers to
1532              primitive types as long as those types cannot be pointers
1533              to everything.  */
1534           while (POINTER_TYPE_P (ptr_type))
1535             /* Strip the *'s off.  */ 
1536             {
1537               ptr_type = TREE_TYPE (ptr_type);
1538               ptr_star_count++;
1539             }
1540           
1541           /* There does not appear to be a better test to see if the 
1542              pointer type was one of the pointer to everything 
1543              types.  */
1544           
1545           if (ptr_star_count > 0)
1546             {
1547               alias_stats.structnoaddress_queries++;
1548               if (ipa_type_escape_field_does_not_clobber_p (var_type, 
1549                                                             TREE_TYPE (ptr))) 
1550                 {
1551                   alias_stats.structnoaddress_resolved++;
1552                   alias_stats.alias_noalias++;
1553                   return false;
1554                 }
1555             }
1556           else if (ptr_star_count == 0)
1557             {
1558               /* If ptr_type was not really a pointer to type, it cannot 
1559                  alias.  */ 
1560               alias_stats.structnoaddress_queries++;
1561               alias_stats.structnoaddress_resolved++;
1562               alias_stats.alias_noalias++;
1563               return false;
1564             }
1565         }
1566     }
1567
1568   alias_stats.alias_mayalias++;
1569   return true;
1570 }
1571
1572
1573 /* Add ALIAS to the set of variables that may alias VAR.  */
1574
1575 static void
1576 add_may_alias (tree var, tree alias)
1577 {
1578   size_t i;
1579   var_ann_t v_ann = get_var_ann (var);
1580   var_ann_t a_ann = get_var_ann (alias);
1581   tree al;
1582
1583   /* Don't allow self-referential aliases.  */
1584   gcc_assert (var != alias);
1585
1586   /* ALIAS must be addressable if it's being added to an alias set.  */
1587 #if 1
1588   TREE_ADDRESSABLE (alias) = 1;
1589 #else
1590   gcc_assert (may_be_aliased (alias));
1591 #endif
1592
1593   if (v_ann->may_aliases == NULL)
1594     v_ann->may_aliases = VEC_alloc (tree, gc, 2);
1595
1596   /* Avoid adding duplicates.  */
1597   for (i = 0; VEC_iterate (tree, v_ann->may_aliases, i, al); i++)
1598     if (alias == al)
1599       return;
1600
1601   /* If VAR is a call-clobbered variable, so is its new ALIAS.
1602      FIXME, call-clobbering should only depend on whether an address
1603      escapes.  It should be independent of aliasing.  */
1604   if (is_call_clobbered (var))
1605     mark_call_clobbered (alias);
1606
1607   /* Likewise.  If ALIAS is call-clobbered, so is VAR.  */
1608   else if (is_call_clobbered (alias))
1609     mark_call_clobbered (var);
1610
1611   VEC_safe_push (tree, gc, v_ann->may_aliases, alias);
1612   a_ann->is_alias_tag = 1;
1613 }
1614
1615
1616 /* Replace alias I in the alias sets of VAR with NEW_ALIAS.  */
1617
1618 static void
1619 replace_may_alias (tree var, size_t i, tree new_alias)
1620 {
1621   var_ann_t v_ann = var_ann (var);
1622   VEC_replace (tree, v_ann->may_aliases, i, new_alias);
1623
1624   /* If VAR is a call-clobbered variable, so is NEW_ALIAS.
1625      FIXME, call-clobbering should only depend on whether an address
1626      escapes.  It should be independent of aliasing.  */
1627   if (is_call_clobbered (var))
1628     mark_call_clobbered (new_alias);
1629
1630   /* Likewise.  If NEW_ALIAS is call-clobbered, so is VAR.  */
1631   else if (is_call_clobbered (new_alias))
1632     mark_call_clobbered (var);
1633 }
1634
1635
1636 /* Mark pointer PTR as pointing to an arbitrary memory location.  */
1637
1638 static void
1639 set_pt_anything (tree ptr)
1640 {
1641   struct ptr_info_def *pi = get_ptr_info (ptr);
1642
1643   pi->pt_anything = 1;
1644   pi->pt_vars = NULL;
1645
1646   /* The pointer used to have a name tag, but we now found it pointing
1647      to an arbitrary location.  The name tag needs to be renamed and
1648      disassociated from PTR.  */
1649   if (pi->name_mem_tag)
1650     {
1651       mark_sym_for_renaming (pi->name_mem_tag);
1652       pi->name_mem_tag = NULL_TREE;
1653     }
1654 }
1655
1656
1657 /* Return true if STMT is an "escape" site from the current function.  Escape
1658    sites those statements which might expose the address of a variable
1659    outside the current function.  STMT is an escape site iff:
1660
1661         1- STMT is a function call, or
1662         2- STMT is an __asm__ expression, or
1663         3- STMT is an assignment to a non-local variable, or
1664         4- STMT is a return statement.
1665
1666    AI points to the alias information collected so far.  */
1667
1668 bool
1669 is_escape_site (tree stmt, struct alias_info *ai)
1670 {
1671   tree call = get_call_expr_in (stmt);
1672   if (call != NULL_TREE)
1673     {
1674       ai->num_calls_found++;
1675
1676       if (!TREE_SIDE_EFFECTS (call))
1677         ai->num_pure_const_calls_found++;
1678
1679       return true;
1680     }
1681   else if (TREE_CODE (stmt) == ASM_EXPR)
1682     return true;
1683   else if (TREE_CODE (stmt) == MODIFY_EXPR)
1684     {
1685       tree lhs = TREE_OPERAND (stmt, 0);
1686
1687       /* Get to the base of _REF nodes.  */
1688       if (TREE_CODE (lhs) != SSA_NAME)
1689         lhs = get_base_address (lhs);
1690
1691       /* If we couldn't recognize the LHS of the assignment, assume that it
1692          is a non-local store.  */
1693       if (lhs == NULL_TREE)
1694         return true;
1695
1696       /* If the RHS is a conversion between a pointer and an integer, the
1697          pointer escapes since we can't track the integer.  */
1698       if ((TREE_CODE (TREE_OPERAND (stmt, 1)) == NOP_EXPR
1699            || TREE_CODE (TREE_OPERAND (stmt, 1)) == CONVERT_EXPR
1700            || TREE_CODE (TREE_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR)
1701           && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND
1702                                         (TREE_OPERAND (stmt, 1), 0)))
1703           && !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
1704         return true;
1705
1706       /* If the LHS is an SSA name, it can't possibly represent a non-local
1707          memory store.  */
1708       if (TREE_CODE (lhs) == SSA_NAME)
1709         return false;
1710
1711       /* FIXME: LHS is not an SSA_NAME.  Even if it's an assignment to a
1712          local variables we cannot be sure if it will escape, because we
1713          don't have information about objects not in SSA form.  Need to
1714          implement something along the lines of
1715
1716          J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P.
1717          Midkiff, ``Escape analysis for java,'' in Proceedings of the
1718          Conference on Object-Oriented Programming Systems, Languages, and
1719          Applications (OOPSLA), pp. 1-19, 1999.  */
1720       return true;
1721     }
1722   else if (TREE_CODE (stmt) == RETURN_EXPR)
1723     return true;
1724
1725   return false;
1726 }
1727
1728 /* Create a new memory tag of type TYPE.
1729    Does NOT push it into the current binding.  */
1730
1731 static tree
1732 create_tag_raw (enum tree_code code, tree type, const char *prefix)
1733 {
1734   tree tmp_var;
1735   tree new_type;
1736
1737   /* Make the type of the variable writable.  */
1738   new_type = build_type_variant (type, 0, 0);
1739   TYPE_ATTRIBUTES (new_type) = TYPE_ATTRIBUTES (type);
1740
1741   tmp_var = build_decl (code, create_tmp_var_name (prefix),
1742                         type);
1743   /* Make the variable writable.  */
1744   TREE_READONLY (tmp_var) = 0;
1745
1746   /* It doesn't start out global.  */
1747   MTAG_GLOBAL (tmp_var) = 0;
1748   TREE_STATIC (tmp_var) = 0;
1749   TREE_USED (tmp_var) = 1;
1750
1751   return tmp_var;
1752 }
1753
1754 /* Create a new memory tag of type TYPE.  If IS_TYPE_TAG is true, the tag
1755    is considered to represent all the pointers whose pointed-to types are
1756    in the same alias set class.  Otherwise, the tag represents a single
1757    SSA_NAME pointer variable.  */
1758
1759 static tree
1760 create_memory_tag (tree type, bool is_type_tag)
1761 {
1762   var_ann_t ann;
1763   tree tag = create_tag_raw (is_type_tag ? TYPE_MEMORY_TAG : NAME_MEMORY_TAG,
1764                              type, (is_type_tag) ? "TMT" : "NMT");
1765
1766   /* By default, memory tags are local variables.  Alias analysis will
1767      determine whether they should be considered globals.  */
1768   DECL_CONTEXT (tag) = current_function_decl;
1769
1770   /* Memory tags are by definition addressable.  */
1771   TREE_ADDRESSABLE (tag) = 1;
1772
1773   ann = get_var_ann (tag);
1774   ann->type_mem_tag = NULL_TREE;
1775
1776   /* Add the tag to the symbol table.  */
1777   add_referenced_tmp_var (tag);
1778
1779   return tag;
1780 }
1781
1782
1783 /* Create a name memory tag to represent a specific SSA_NAME pointer P_i.
1784    This is used if P_i has been found to point to a specific set of
1785    variables or to a non-aliased memory location like the address returned
1786    by malloc functions.  */
1787
1788 static tree
1789 get_nmt_for (tree ptr)
1790 {
1791   struct ptr_info_def *pi = get_ptr_info (ptr);
1792   tree tag = pi->name_mem_tag;
1793
1794   if (tag == NULL_TREE)
1795     tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false);
1796
1797   /* If PTR is a PARM_DECL, it points to a global variable or malloc,
1798      then its name tag should be considered a global variable.  */
1799   if (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
1800       || pi->pt_global_mem)
1801     mark_call_clobbered (tag);
1802
1803   return tag;
1804 }
1805
1806
1807 /* Return the type memory tag associated to pointer PTR.  A memory tag is an
1808    artificial variable that represents the memory location pointed-to by
1809    PTR.  It is used to model the effects of pointer de-references on
1810    addressable variables.
1811    
1812    AI points to the data gathered during alias analysis.  This function
1813    populates the array AI->POINTERS.  */
1814
1815 static tree
1816 get_tmt_for (tree ptr, struct alias_info *ai)
1817 {
1818   size_t i;
1819   tree tag;
1820   tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
1821   HOST_WIDE_INT tag_set = get_alias_set (tag_type);
1822
1823   /* To avoid creating unnecessary memory tags, only create one memory tag
1824      per alias set class.  Note that it may be tempting to group
1825      memory tags based on conflicting alias sets instead of
1826      equivalence.  That would be wrong because alias sets are not
1827      necessarily transitive (as demonstrated by the libstdc++ test
1828      23_containers/vector/cons/4.cc).  Given three alias sets A, B, C
1829      such that conflicts (A, B) == true and conflicts (A, C) == true,
1830      it does not necessarily follow that conflicts (B, C) == true.  */
1831   for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
1832     {
1833       struct alias_map_d *curr = ai->pointers[i];
1834       tree curr_tag = var_ann (curr->var)->type_mem_tag;
1835       if (tag_set == curr->set
1836           && TYPE_READONLY (tag_type) == TYPE_READONLY (TREE_TYPE (curr_tag)))
1837         {
1838           tag = curr_tag;
1839           break;
1840         }
1841     }
1842
1843   /* If VAR cannot alias with any of the existing memory tags, create a new
1844      tag for PTR and add it to the POINTERS array.  */
1845   if (tag == NULL_TREE)
1846     {
1847       struct alias_map_d *alias_map;
1848
1849       /* If PTR did not have a type tag already, create a new TMT.*
1850          artificial variable representing the memory location
1851          pointed-to by PTR.  */
1852       if (var_ann (ptr)->type_mem_tag == NULL_TREE)
1853         tag = create_memory_tag (tag_type, true);
1854       else
1855         tag = var_ann (ptr)->type_mem_tag;
1856
1857       /* Add PTR to the POINTERS array.  Note that we are not interested in
1858          PTR's alias set.  Instead, we cache the alias set for the memory that
1859          PTR points to.  */
1860       alias_map = XCNEW (struct alias_map_d);
1861       alias_map->var = ptr;
1862       alias_map->set = tag_set;
1863       ai->pointers[ai->num_pointers++] = alias_map;
1864     }
1865
1866   /* If the pointed-to type is volatile, so is the tag.  */
1867   TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type);
1868
1869   /* Make sure that the type tag has the same alias set as the
1870      pointed-to type.  */
1871   gcc_assert (tag_set == get_alias_set (tag));
1872
1873   /* If PTR's pointed-to type is read-only, then TAG's type must also
1874      be read-only.  */
1875   gcc_assert (TYPE_READONLY (tag_type) == TYPE_READONLY (TREE_TYPE (tag)));
1876
1877   return tag;
1878 }
1879
1880
1881 /* Create GLOBAL_VAR, an artificial global variable to act as a
1882    representative of all the variables that may be clobbered by function
1883    calls.  */
1884
1885 static void
1886 create_global_var (void)
1887 {
1888   global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
1889                            void_type_node);
1890   DECL_ARTIFICIAL (global_var) = 1;
1891   TREE_READONLY (global_var) = 0;
1892   DECL_EXTERNAL (global_var) = 1;
1893   TREE_STATIC (global_var) = 1;
1894   TREE_USED (global_var) = 1;
1895   DECL_CONTEXT (global_var) = NULL_TREE;
1896   TREE_THIS_VOLATILE (global_var) = 0;
1897   TREE_ADDRESSABLE (global_var) = 0;
1898
1899   add_referenced_tmp_var (global_var);
1900   mark_sym_for_renaming (global_var);
1901 }
1902
1903
1904 /* Dump alias statistics on FILE.  */
1905
1906 static void 
1907 dump_alias_stats (FILE *file)
1908 {
1909   const char *funcname
1910     = lang_hooks.decl_printable_name (current_function_decl, 2);
1911   fprintf (file, "\nAlias statistics for %s\n\n", funcname);
1912   fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries);
1913   fprintf (file, "Total alias mayalias results:\t%u\n", 
1914            alias_stats.alias_mayalias);
1915   fprintf (file, "Total alias noalias results:\t%u\n",
1916            alias_stats.alias_noalias);
1917   fprintf (file, "Total simple queries:\t%u\n",
1918            alias_stats.simple_queries);
1919   fprintf (file, "Total simple resolved:\t%u\n",
1920            alias_stats.simple_resolved);
1921   fprintf (file, "Total TBAA queries:\t%u\n",
1922            alias_stats.tbaa_queries);
1923   fprintf (file, "Total TBAA resolved:\t%u\n",
1924            alias_stats.tbaa_resolved);
1925   fprintf (file, "Total non-addressable structure type queries:\t%u\n",
1926            alias_stats.structnoaddress_queries);
1927   fprintf (file, "Total non-addressable structure type resolved:\t%u\n",
1928            alias_stats.structnoaddress_resolved);
1929 }
1930   
1931
1932 /* Dump alias information on FILE.  */
1933
1934 void
1935 dump_alias_info (FILE *file)
1936 {
1937   size_t i;
1938   const char *funcname
1939     = lang_hooks.decl_printable_name (current_function_decl, 2);
1940   referenced_var_iterator rvi;
1941   tree var;
1942
1943   fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname);
1944
1945   fprintf (file, "Aliased symbols\n\n");
1946   
1947   FOR_EACH_REFERENCED_VAR (var, rvi)
1948     {
1949       if (may_be_aliased (var))
1950         dump_variable (file, var);
1951     }
1952
1953   fprintf (file, "\nDereferenced pointers\n\n");
1954
1955   FOR_EACH_REFERENCED_VAR (var, rvi)
1956     {
1957       var_ann_t ann = var_ann (var);
1958       if (ann->type_mem_tag)
1959         dump_variable (file, var);
1960     }
1961
1962   fprintf (file, "\nType memory tags\n\n");
1963   
1964   FOR_EACH_REFERENCED_VAR (var, rvi)
1965     {
1966       if (TREE_CODE (var) == TYPE_MEMORY_TAG)
1967         dump_variable (file, var);
1968     }
1969
1970   fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname);
1971
1972   fprintf (file, "SSA_NAME pointers\n\n");
1973   for (i = 1; i < num_ssa_names; i++)
1974     {
1975       tree ptr = ssa_name (i);
1976       struct ptr_info_def *pi;
1977       
1978       if (ptr == NULL_TREE)
1979         continue;
1980
1981       pi = SSA_NAME_PTR_INFO (ptr);
1982       if (!SSA_NAME_IN_FREE_LIST (ptr)
1983           && pi
1984           && pi->name_mem_tag)
1985         dump_points_to_info_for (file, ptr);
1986     }
1987
1988   fprintf (file, "\nName memory tags\n\n");
1989   
1990   FOR_EACH_REFERENCED_VAR (var, rvi)
1991     {
1992       if (TREE_CODE (var) == NAME_MEMORY_TAG)
1993         dump_variable (file, var);
1994     }
1995
1996   fprintf (file, "\n");
1997 }
1998
1999
2000 /* Dump alias information on stderr.  */
2001
2002 void
2003 debug_alias_info (void)
2004 {
2005   dump_alias_info (stderr);
2006 }
2007
2008
2009 /* Return the alias information associated with pointer T.  It creates a
2010    new instance if none existed.  */
2011
2012 struct ptr_info_def *
2013 get_ptr_info (tree t)
2014 {
2015   struct ptr_info_def *pi;
2016
2017   gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
2018
2019   pi = SSA_NAME_PTR_INFO (t);
2020   if (pi == NULL)
2021     {
2022       pi = GGC_NEW (struct ptr_info_def);
2023       memset ((void *)pi, 0, sizeof (*pi));
2024       SSA_NAME_PTR_INFO (t) = pi;
2025     }
2026
2027   return pi;
2028 }
2029
2030
2031 /* Dump points-to information for SSA_NAME PTR into FILE.  */
2032
2033 void
2034 dump_points_to_info_for (FILE *file, tree ptr)
2035 {
2036   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2037
2038   print_generic_expr (file, ptr, dump_flags);
2039
2040   if (pi)
2041     {
2042       if (pi->name_mem_tag)
2043         {
2044           fprintf (file, ", name memory tag: ");
2045           print_generic_expr (file, pi->name_mem_tag, dump_flags);
2046         }
2047
2048       if (pi->is_dereferenced)
2049         fprintf (file, ", is dereferenced");
2050
2051       if (pi->value_escapes_p)
2052         fprintf (file, ", its value escapes");
2053
2054       if (pi->pt_anything)
2055         fprintf (file, ", points-to anything");
2056
2057       if (pi->pt_null)
2058         fprintf (file, ", points-to NULL");
2059
2060       if (pi->pt_vars)
2061         {
2062           unsigned ix;
2063           bitmap_iterator bi;
2064
2065           fprintf (file, ", points-to vars: { ");
2066           EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi)
2067             {
2068               print_generic_expr (file, referenced_var (ix), dump_flags);
2069               fprintf (file, " ");
2070             }
2071           fprintf (file, "}");
2072         }
2073     }
2074
2075   fprintf (file, "\n");
2076 }
2077
2078
2079 /* Dump points-to information for VAR into stderr.  */
2080
2081 void
2082 debug_points_to_info_for (tree var)
2083 {
2084   dump_points_to_info_for (stderr, var);
2085 }
2086
2087
2088 /* Dump points-to information into FILE.  NOTE: This function is slow, as
2089    it needs to traverse the whole CFG looking for pointer SSA_NAMEs.  */
2090
2091 void
2092 dump_points_to_info (FILE *file)
2093 {
2094   basic_block bb;
2095   block_stmt_iterator si;
2096   ssa_op_iter iter;
2097   const char *fname =
2098     lang_hooks.decl_printable_name (current_function_decl, 2);
2099   referenced_var_iterator rvi;
2100   tree var;
2101
2102   fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname);
2103
2104   /* First dump points-to information for the default definitions of
2105      pointer variables.  This is necessary because default definitions are
2106      not part of the code.  */
2107   FOR_EACH_REFERENCED_VAR (var, rvi)
2108     {
2109       if (POINTER_TYPE_P (TREE_TYPE (var)))
2110         {
2111           tree def = default_def (var);
2112           if (def)
2113             dump_points_to_info_for (file, def);
2114         }
2115     }
2116
2117   /* Dump points-to information for every pointer defined in the program.  */
2118   FOR_EACH_BB (bb)
2119     {
2120       tree phi;
2121
2122       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2123         {
2124           tree ptr = PHI_RESULT (phi);
2125           if (POINTER_TYPE_P (TREE_TYPE (ptr)))
2126             dump_points_to_info_for (file, ptr);
2127         }
2128
2129         for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2130           {
2131             tree stmt = bsi_stmt (si);
2132             tree def;
2133             FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
2134               if (POINTER_TYPE_P (TREE_TYPE (def)))
2135                 dump_points_to_info_for (file, def);
2136           }
2137     }
2138
2139   fprintf (file, "\n");
2140 }
2141
2142
2143 /* Dump points-to info pointed to by PTO into STDERR.  */
2144
2145 void
2146 debug_points_to_info (void)
2147 {
2148   dump_points_to_info (stderr);
2149 }
2150
2151 /* Dump to FILE the list of variables that may be aliasing VAR.  */
2152
2153 void
2154 dump_may_aliases_for (FILE *file, tree var)
2155 {
2156   VEC(tree, gc) *aliases;
2157   
2158   if (TREE_CODE (var) == SSA_NAME)
2159     var = SSA_NAME_VAR (var);
2160
2161   aliases = var_ann (var)->may_aliases;
2162   if (aliases)
2163     {
2164       size_t i;
2165       tree al;
2166       fprintf (file, "{ ");
2167       for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
2168         {
2169           print_generic_expr (file, al, dump_flags);
2170           fprintf (file, " ");
2171         }
2172       fprintf (file, "}");
2173     }
2174 }
2175
2176
2177 /* Dump to stderr the list of variables that may be aliasing VAR.  */
2178
2179 void
2180 debug_may_aliases_for (tree var)
2181 {
2182   dump_may_aliases_for (stderr, var);
2183 }
2184
2185 /* Return true if VAR may be aliased.  */
2186
2187 bool
2188 may_be_aliased (tree var)
2189 {
2190   /* Obviously.  */
2191   if (TREE_ADDRESSABLE (var))
2192     return true;
2193
2194   /* Globally visible variables can have their addresses taken by other
2195      translation units.  */
2196
2197   if (MTAG_P (var)
2198       && (MTAG_GLOBAL (var) || TREE_PUBLIC (var)))
2199     return true;
2200   else if (!MTAG_P (var)
2201       && (DECL_EXTERNAL (var) || TREE_PUBLIC (var)))
2202     return true;
2203
2204   /* Automatic variables can't have their addresses escape any other way.
2205      This must be after the check for global variables, as extern declarations
2206      do not have TREE_STATIC set.  */
2207   if (!TREE_STATIC (var))
2208     return false;
2209
2210   /* If we're in unit-at-a-time mode, then we must have seen all occurrences
2211      of address-of operators, and so we can trust TREE_ADDRESSABLE.  Otherwise
2212      we can only be sure the variable isn't addressable if it's local to the
2213      current function.  */
2214   if (flag_unit_at_a_time)
2215     return false;
2216   if (decl_function_context (var) == current_function_decl)
2217     return false;
2218
2219   return true;
2220 }
2221
2222
2223 /* Given two symbols return TRUE if one is in the alias set of the other.  */
2224 bool
2225 is_aliased_with (tree tag, tree sym)
2226 {
2227   size_t i;
2228   VEC(tree,gc) *aliases;
2229   tree al;
2230
2231   if (var_ann (sym)->is_alias_tag)
2232     {
2233       aliases = var_ann (tag)->may_aliases;
2234
2235       if (aliases == NULL)
2236         return false;
2237
2238       for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
2239         if (al == sym)
2240           return true;
2241     }
2242   else
2243     {
2244       aliases = var_ann (sym)->may_aliases;
2245
2246       if (aliases == NULL)
2247         return false;
2248
2249       for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
2250         if (al == tag)
2251           return true;
2252     }
2253
2254   return false;
2255 }
2256
2257
2258 /* Add VAR to the list of may-aliases of PTR's type tag.  If PTR
2259    doesn't already have a type tag, create one.  */
2260
2261 void
2262 add_type_alias (tree ptr, tree var)
2263 {
2264   VEC(tree, gc) *aliases;
2265   tree tag, al;
2266   var_ann_t ann = var_ann (ptr);
2267   subvar_t svars;
2268   VEC (tree, heap) *varvec = NULL;  
2269   unsigned i;
2270
2271   if (ann->type_mem_tag == NULL_TREE)
2272     {
2273       tree q = NULL_TREE;
2274       tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
2275       HOST_WIDE_INT tag_set = get_alias_set (tag_type);
2276       safe_referenced_var_iterator rvi;
2277
2278       /* PTR doesn't have a type tag, create a new one and add VAR to
2279          the new tag's alias set.
2280
2281          FIXME, This is slower than necessary.  We need to determine
2282          whether there is another pointer Q with the same alias set as
2283          PTR.  This could be sped up by having type tags associated
2284          with types.  */
2285       FOR_EACH_REFERENCED_VAR_SAFE (q, varvec, rvi)
2286         {
2287           if (POINTER_TYPE_P (TREE_TYPE (q))
2288               && tag_set == get_alias_set (TREE_TYPE (TREE_TYPE (q))))
2289             {
2290               /* Found another pointer Q with the same alias set as
2291                  the PTR's pointed-to type.  If Q has a type tag, use
2292                  it.  Otherwise, create a new memory tag for PTR.  */
2293               var_ann_t ann1 = var_ann (q);
2294               if (ann1->type_mem_tag)
2295                 ann->type_mem_tag = ann1->type_mem_tag;
2296               else
2297                 ann->type_mem_tag = create_memory_tag (tag_type, true);
2298               goto found_tag;
2299             }
2300         }
2301
2302       /* Couldn't find any other pointer with a type tag we could use.
2303          Create a new memory tag for PTR.  */
2304       ann->type_mem_tag = create_memory_tag (tag_type, true);
2305     }
2306
2307 found_tag:
2308   /* If VAR is not already PTR's type tag, add it to the may-alias set
2309      for PTR's type tag.  */
2310   gcc_assert (!MTAG_P (var));
2311   tag = ann->type_mem_tag;
2312
2313   /* If VAR has subvars, add the subvars to the tag instead of the
2314      actual var.  */
2315   if (var_can_have_subvars (var)
2316       && (svars = get_subvars_for_var (var)))
2317     {
2318       subvar_t sv;      
2319       for (sv = svars; sv; sv = sv->next)
2320         add_may_alias (tag, sv->var);
2321     }
2322   else
2323     add_may_alias (tag, var);
2324
2325   /* TAG and its set of aliases need to be marked for renaming.  */
2326   mark_sym_for_renaming (tag);
2327   if ((aliases = var_ann (tag)->may_aliases) != NULL)
2328     {
2329       for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
2330         mark_sym_for_renaming (al);
2331     }
2332
2333   /* If we had grouped aliases, VAR may have aliases of its own.  Mark
2334      them for renaming as well.  Other statements referencing the
2335      aliases of VAR will need to be updated.  */
2336   if ((aliases = var_ann (var)->may_aliases) != NULL)
2337     {
2338       for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
2339         mark_sym_for_renaming (al);
2340     }
2341   VEC_free (tree, heap, varvec);
2342 }
2343
2344
2345 /* Create a new type tag for PTR.  Construct the may-alias list of this type
2346    tag so that it has the aliasing of VAR. 
2347
2348    Note, the set of aliases represented by the new type tag are not marked
2349    for renaming.  */
2350
2351 void
2352 new_type_alias (tree ptr, tree var)
2353 {
2354   var_ann_t p_ann = var_ann (ptr);
2355   tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
2356   var_ann_t v_ann = var_ann (var);
2357   tree tag;
2358   subvar_t svars;
2359
2360   gcc_assert (p_ann->type_mem_tag == NULL_TREE);
2361   gcc_assert (!MTAG_P (var));
2362
2363   /* Add VAR to the may-alias set of PTR's new type tag.  If VAR has
2364      subvars, add the subvars to the tag instead of the actual var.  */
2365   if (var_can_have_subvars (var)
2366       && (svars = get_subvars_for_var (var)))
2367     {
2368       subvar_t sv;
2369
2370       tag = create_memory_tag (tag_type, true);
2371       p_ann->type_mem_tag = tag;
2372
2373       for (sv = svars; sv; sv = sv->next)
2374         add_may_alias (tag, sv->var);
2375     }
2376   else
2377     {
2378       /* The following is based on code in add_stmt_operand to ensure that the
2379          same defs/uses/vdefs/vuses will be found after replacing a reference
2380          to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value
2381          is the address of var.  */
2382       VEC(tree, gc) *aliases = v_ann->may_aliases;
2383
2384       if ((aliases != NULL)
2385           && (VEC_length (tree, aliases) == 1))
2386         {
2387           tree ali = VEC_index (tree, aliases, 0);
2388
2389           if (TREE_CODE (ali) == TYPE_MEMORY_TAG)
2390             {
2391               p_ann->type_mem_tag = ali;
2392               return;
2393             }
2394         }
2395
2396       tag = create_memory_tag (tag_type, true);
2397       p_ann->type_mem_tag = tag;
2398
2399       if (aliases == NULL)
2400         add_may_alias (tag, var);
2401       else
2402         {
2403           unsigned i;
2404           tree al;
2405
2406           for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
2407             add_may_alias (tag, al);
2408         }
2409     }    
2410 }
2411
2412
2413
2414 /* This represents the used range of a variable.  */
2415
2416 typedef struct used_part
2417 {
2418   HOST_WIDE_INT minused;
2419   HOST_WIDE_INT maxused;
2420   /* True if we have an explicit use/def of some portion of this variable,
2421      even if it is all of it. i.e. a.b = 5 or temp = a.b.  */
2422   bool explicit_uses;
2423   /* True if we have an implicit use/def of some portion of this
2424      variable.  Implicit uses occur when we can't tell what part we
2425      are referencing, and have to make conservative assumptions.  */
2426   bool implicit_uses;
2427 } *used_part_t;
2428
2429 /* An array of used_part structures, indexed by variable uid.  */
2430
2431 static htab_t used_portions;
2432
2433 struct used_part_map
2434 {
2435   unsigned int uid;
2436   used_part_t to;
2437 };
2438
2439 /* Return true if the uid in the two used part maps are equal.  */
2440
2441 static int
2442 used_part_map_eq (const void *va, const void *vb)
2443 {
2444   const struct used_part_map *a = (const struct used_part_map *) va;
2445   const struct used_part_map *b = (const struct used_part_map *) vb;
2446   return (a->uid == b->uid);
2447 }
2448
2449 /* Hash a from uid in a used_part_map.  */
2450
2451 static unsigned int
2452 used_part_map_hash (const void *item)
2453 {
2454   return ((const struct used_part_map *)item)->uid;
2455 }
2456
2457 /* Free a used part map element.  */
2458
2459 static void 
2460 free_used_part_map (void *item)
2461 {
2462   free (((struct used_part_map *)item)->to);
2463   free (item);
2464 }
2465
2466 /* Lookup a used_part structure for a UID.  */
2467
2468 static used_part_t
2469 up_lookup (unsigned int uid)
2470 {
2471   struct used_part_map *h, in;
2472   in.uid = uid;
2473   h = (struct used_part_map *) htab_find_with_hash (used_portions, &in, uid);
2474   if (!h)
2475     return NULL;
2476   return h->to;
2477 }
2478
2479 /* Insert the pair UID, TO into the used part hashtable.  */
2480  
2481 static void 
2482 up_insert (unsigned int uid, used_part_t to)
2483
2484   struct used_part_map *h;
2485   void **loc;
2486
2487   h = XNEW (struct used_part_map);
2488   h->uid = uid;
2489   h->to = to;
2490   loc = htab_find_slot_with_hash (used_portions, h,
2491                                   uid, INSERT);
2492   if (*loc != NULL)
2493     free (*loc);
2494   *(struct used_part_map **)  loc = h;
2495 }
2496
2497
2498 /* Given a variable uid, UID, get or create the entry in the used portions
2499    table for the variable.  */
2500
2501 static used_part_t
2502 get_or_create_used_part_for (size_t uid)
2503 {
2504   used_part_t up;
2505   if ((up = up_lookup (uid)) == NULL)
2506     {
2507       up = XCNEW (struct used_part);
2508       up->minused = INT_MAX;
2509       up->maxused = 0;
2510       up->explicit_uses = false;
2511       up->implicit_uses = false;
2512     }
2513
2514   return up;
2515 }
2516
2517
2518 /* Create and return a structure sub-variable for field type FIELD of
2519    variable VAR.  */
2520
2521 static tree
2522 create_sft (tree var, tree field)
2523 {
2524   var_ann_t ann;
2525   tree subvar = create_tag_raw (STRUCT_FIELD_TAG, field, "SFT");
2526
2527   /* We need to copy the various flags from VAR to SUBVAR, so that
2528      they are is_global_var iff the original variable was.  */
2529   DECL_CONTEXT (subvar) = DECL_CONTEXT (var);
2530   MTAG_GLOBAL (subvar) = DECL_EXTERNAL (var);
2531   TREE_PUBLIC  (subvar) = TREE_PUBLIC (var);
2532   TREE_STATIC (subvar) = TREE_STATIC (var);
2533   TREE_READONLY (subvar) = TREE_READONLY (var);
2534
2535   /* Add the new variable to REFERENCED_VARS.  */
2536   ann = get_var_ann (subvar);
2537   ann->type_mem_tag = NULL;     
2538   add_referenced_tmp_var (subvar);
2539   SFT_PARENT_VAR (subvar) = var;
2540
2541   return subvar;
2542 }
2543
2544
2545 /* Given an aggregate VAR, create the subvariables that represent its
2546    fields.  */
2547
2548 static void
2549 create_overlap_variables_for (tree var)
2550 {
2551   VEC(fieldoff_s,heap) *fieldstack = NULL;
2552   used_part_t up;
2553   size_t uid = DECL_UID (var);
2554
2555   if (!up_lookup (uid))
2556     return;
2557
2558   up = up_lookup (uid);
2559   push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL);
2560   if (VEC_length (fieldoff_s, fieldstack) != 0)
2561     {
2562       subvar_t *subvars;
2563       fieldoff_s *fo;
2564       bool notokay = false;
2565       int fieldcount = 0;
2566       int i;
2567       HOST_WIDE_INT lastfooffset = -1;
2568       HOST_WIDE_INT lastfosize = -1;
2569       tree lastfotype = NULL_TREE;
2570
2571       /* Not all fields have DECL_SIZE set, and those that don't, we don't
2572          know their size, and thus, can't handle.
2573          The same is true of fields with DECL_SIZE that is not an integer
2574          constant (such as variable sized fields).
2575          Fields with offsets which are not constant will have an offset < 0 
2576          We *could* handle fields that are constant sized arrays, but
2577          currently don't.  Doing so would require some extra changes to
2578          tree-ssa-operands.c.  */
2579
2580       for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
2581         {
2582           if (!fo->size
2583               || TREE_CODE (fo->size) != INTEGER_CST
2584               || fo->offset < 0)
2585             {
2586               notokay = true;
2587               break;
2588             }
2589           fieldcount++;
2590         }
2591
2592       /* The current heuristic we use is as follows:
2593          If the variable has no used portions in this function, no
2594          structure vars are created for it.
2595          Otherwise,
2596          If the variable has less than SALIAS_MAX_IMPLICIT_FIELDS,
2597          we always create structure vars for them.
2598          If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
2599          some explicit uses, we create structure vars for them.
2600          If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
2601          no explicit uses, we do not create structure vars for them.
2602       */
2603       
2604       if (fieldcount >= SALIAS_MAX_IMPLICIT_FIELDS
2605           && !up->explicit_uses)
2606         {
2607           if (dump_file && (dump_flags & TDF_DETAILS))
2608             {
2609               fprintf (dump_file, "Variable ");
2610               print_generic_expr (dump_file, var, 0);
2611               fprintf (dump_file, " has no explicit uses in this function, and is > SALIAS_MAX_IMPLICIT_FIELDS, so skipping\n");
2612             }
2613           notokay = true;
2614         }
2615       
2616       /* Bail out, if we can't create overlap variables.  */
2617       if (notokay)
2618         {
2619           VEC_free (fieldoff_s, heap, fieldstack);
2620           return;
2621         }
2622       
2623       /* Otherwise, create the variables.  */
2624       subvars = lookup_subvars_for_var (var);
2625       
2626       sort_fieldstack (fieldstack);
2627
2628       for (i = VEC_length (fieldoff_s, fieldstack);
2629            VEC_iterate (fieldoff_s, fieldstack, --i, fo);)
2630         {
2631           subvar_t sv;
2632           HOST_WIDE_INT fosize;
2633           tree currfotype;
2634
2635           fosize = TREE_INT_CST_LOW (fo->size);
2636           currfotype = fo->type;
2637
2638           /* If this field isn't in the used portion,
2639              or it has the exact same offset and size as the last
2640              field, skip it.  */
2641
2642           if (((fo->offset <= up->minused
2643                 && fo->offset + fosize <= up->minused)
2644                || fo->offset >= up->maxused)
2645               || (fo->offset == lastfooffset
2646                   && fosize == lastfosize
2647                   && currfotype == lastfotype))
2648             continue;
2649           sv = GGC_NEW (struct subvar);
2650           sv->offset = fo->offset;
2651           sv->size = fosize;
2652           sv->next = *subvars;
2653           sv->var = create_sft (var, fo->type);
2654
2655           if (dump_file)
2656             {
2657               fprintf (dump_file, "structure field tag %s created for var %s",
2658                        get_name (sv->var), get_name (var));
2659               fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC,
2660                        sv->offset);
2661               fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC,
2662                        sv->size);
2663               fprintf (dump_file, "\n");
2664             }
2665           
2666           lastfotype = currfotype;
2667           lastfooffset = fo->offset;
2668           lastfosize = fosize;
2669           *subvars = sv;
2670         }
2671
2672       /* Once we have created subvars, the original is no longer call
2673          clobbered on its own.  Its call clobbered status depends
2674          completely on the call clobbered status of the subvars.
2675
2676          add_referenced_var in the above loop will take care of
2677          marking subvars of global variables as call clobbered for us
2678          to start, since they are global as well.  */
2679       clear_call_clobbered (var);
2680     }
2681
2682   VEC_free (fieldoff_s, heap, fieldstack);
2683 }
2684
2685
2686 /* Find the conservative answer to the question of what portions of what 
2687    structures are used by this statement.  We assume that if we have a
2688    component ref with a known size + offset, that we only need that part
2689    of the structure.  For unknown cases, or cases where we do something
2690    to the whole structure, we assume we need to create fields for the 
2691    entire structure.  */
2692
2693 static tree
2694 find_used_portions (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2695 {
2696   switch (TREE_CODE (*tp))
2697     {
2698     case REALPART_EXPR:
2699     case IMAGPART_EXPR:
2700     case COMPONENT_REF:
2701     case ARRAY_REF:
2702       {
2703         HOST_WIDE_INT bitsize;
2704         HOST_WIDE_INT bitmaxsize;
2705         HOST_WIDE_INT bitpos;
2706         tree ref;
2707         ref = get_ref_base_and_extent (*tp, &bitpos, &bitsize, &bitmaxsize);
2708         if (DECL_P (ref)
2709             && var_can_have_subvars (ref)
2710             && bitmaxsize != -1)
2711           {
2712             size_t uid = DECL_UID (ref);
2713             used_part_t up;
2714
2715             up = get_or_create_used_part_for (uid);         
2716
2717             if (bitpos <= up->minused)
2718               up->minused = bitpos;
2719             if ((bitpos + bitmaxsize >= up->maxused))
2720               up->maxused = bitpos + bitmaxsize;
2721
2722             if (bitsize == bitmaxsize)
2723               up->explicit_uses = true;
2724             else
2725               up->implicit_uses = true;
2726             up_insert (uid, up);
2727
2728             *walk_subtrees = 0;
2729             return NULL_TREE;
2730           }
2731       }
2732       break;
2733       /* This is here to make sure we mark the entire base variable as used
2734          when you take its address.  Because our used portion analysis is
2735          simple, we aren't looking at casts or pointer arithmetic to see what
2736          happens when you take the address.  */
2737     case ADDR_EXPR:
2738       {
2739         tree var = get_base_address (TREE_OPERAND (*tp, 0));
2740
2741         if (var 
2742             && DECL_P (var)
2743             && DECL_SIZE (var)
2744             && var_can_have_subvars (var)
2745             && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
2746           {
2747             used_part_t up;
2748             size_t uid = DECL_UID (var);
2749             
2750             up = get_or_create_used_part_for (uid);
2751  
2752             up->minused = 0;
2753             up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
2754             up->implicit_uses = true;
2755
2756             up_insert (uid, up);
2757             *walk_subtrees = 0;
2758             return NULL_TREE;
2759           }
2760       }
2761       break;
2762     case VAR_DECL:
2763     case PARM_DECL:
2764     case RESULT_DECL:
2765       {
2766         tree var = *tp;
2767         if (DECL_SIZE (var)
2768             && var_can_have_subvars (var)
2769             && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
2770           {
2771             used_part_t up;
2772             size_t uid = DECL_UID (var);
2773             
2774             up = get_or_create_used_part_for (uid);
2775  
2776             up->minused = 0;
2777             up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
2778             up->implicit_uses = true;
2779
2780             up_insert (uid, up);
2781             *walk_subtrees = 0;
2782             return NULL_TREE;
2783           }
2784       }
2785       break;
2786       
2787     default:
2788       break;
2789       
2790     }
2791   return NULL_TREE;
2792 }
2793
2794 /* Create structure field variables for structures used in this function.  */
2795
2796 static void
2797 create_structure_vars (void)
2798 {
2799   basic_block bb;
2800   safe_referenced_var_iterator rvi;
2801   VEC (tree, heap) *varvec = NULL;
2802   tree var;
2803
2804   used_portions = htab_create (10, used_part_map_hash, used_part_map_eq, 
2805                                free_used_part_map);
2806   
2807   FOR_EACH_BB (bb)
2808     {
2809       block_stmt_iterator bsi;
2810       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2811         {
2812           walk_tree_without_duplicates (bsi_stmt_ptr (bsi), 
2813                                         find_used_portions,
2814                                         NULL);
2815         }
2816     }
2817   FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, rvi)
2818     {
2819       /* The C++ FE creates vars without DECL_SIZE set, for some reason.  */
2820       if (var     
2821           && DECL_SIZE (var)
2822           && var_can_have_subvars (var)
2823           && !MTAG_P (var)
2824           && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
2825         create_overlap_variables_for (var);
2826     }
2827   htab_delete (used_portions);
2828   VEC_free (tree, heap, varvec);
2829
2830 }
2831
2832 static bool
2833 gate_structure_vars (void)
2834 {
2835   return flag_tree_salias != 0;
2836 }
2837
2838 struct tree_opt_pass pass_create_structure_vars = 
2839 {
2840   "salias",              /* name */
2841   gate_structure_vars,   /* gate */
2842   create_structure_vars, /* execute */
2843   NULL,                  /* sub */
2844   NULL,                  /* next */
2845   0,                     /* static_pass_number */
2846   0,                     /* tv_id */
2847   PROP_cfg,              /* properties_required */
2848   0,                     /* properties_provided */
2849   0,                     /* properties_destroyed */
2850   0,                     /* todo_flags_start */
2851   TODO_dump_func,        /* todo_flags_finish */
2852   0                      /* letter */
2853 };