OSDN Git Service

13ec95b9e9d0b1f33ae353e25e6c16dfde3156a6
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-alias.c
1 /* Alias analysis for trees.
2    Copyright (C) 2004, 2005, 2006, 2007 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 3, 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 COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "timevar.h"
31 #include "expr.h"
32 #include "ggc.h"
33 #include "langhooks.h"
34 #include "flags.h"
35 #include "function.h"
36 #include "diagnostic.h"
37 #include "tree-dump.h"
38 #include "tree-gimple.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
41 #include "tree-pass.h"
42 #include "tree-ssa-structalias.h"
43 #include "convert.h"
44 #include "params.h"
45 #include "ipa-type-escape.h"
46 #include "vec.h"
47 #include "bitmap.h"
48 #include "vecprim.h"
49 #include "pointer-set.h"
50 #include "alloc-pool.h"
51
52 /* Broad overview of how aliasing works:
53    
54    First we compute points-to sets, which is done in
55    tree-ssa-structalias.c
56       
57    During points-to set constraint finding, a bunch of little bits of
58    information is collected.
59    This is not done because it is necessary for points-to, but because
60    points-to has to walk every statement anyway.  The function performing
61    this collecting is update_alias_info.
62
63    Bits update_alias_info collects include:
64    1. Directly escaping variables and variables whose value escapes
65    (using is_escape_site).  This is the set of variables and values that
66    escape prior to transitive closure of the clobbers.
67    2.  The set of variables dereferenced on the LHS (into
68    dereferenced_ptr_stores) 
69    3. The set of variables dereferenced on the RHS (into
70    dereferenced_ptr_loads) 
71    4. The set of all pointers we saw.
72    5. The number of loads and stores for each variable
73    6. The number of statements touching memory
74    7. The set of address taken variables.
75    
76    
77    #1 is computed by a combination of is_escape_site, and counting the
78    number of uses/deref operators.  This function properly accounts for
79    situations like &ptr->field, which is *not* a dereference.
80    
81    After points-to sets are computed, the sets themselves still
82    contain points-to specific variables, such as a variable that says
83    the pointer points to anything, a variable that says the pointer
84    points to readonly memory, etc.
85
86    These are eliminated in a later phase, as we will see.
87
88    The rest of the phases are located in tree-ssa-alias.c
89
90    The next phase after points-to set computation is called
91    "setup_pointers_and_addressables"
92
93    This pass does 3 main things:
94    
95    1. All variables that can have TREE_ADDRESSABLE removed safely (IE
96    non-globals whose address is not taken), have TREE_ADDRESSABLE
97    removed.
98    2. All variables that may be aliased (which is the set of addressable
99    variables and globals) at all, are marked for renaming, and have
100    symbol memory tags created for them.
101    3. All variables which are stored into have their SMT's added to
102    written vars. 
103
104
105    After this function is run, all variables that will ever have an
106    SMT, have one, though its aliases are not filled in.
107
108    The next phase is to compute flow-insensitive aliasing, which in
109    our case, is a misnomer.  it is really computing aliasing that
110    requires no transitive closure to be correct.  In particular, it
111    uses stack vs non-stack, TBAA, etc, to determine whether two
112    symbols could *ever* alias .  This phase works by going through all
113    the pointers we collected during update_alias_info, and for every
114    addressable variable in the program, seeing if they alias.  If so,
115    the addressable variable is added to the symbol memory tag for the
116    pointer.
117
118    As part of this, we handle symbol memory tags that conflict but
119    have no aliases in common, by forcing them to have a symbol in
120    common (through unioning alias sets or adding one as an alias of
121    the other), or by adding one as an alias of another.  The case of
122    conflicts with no aliases in common occurs mainly due to aliasing
123    we cannot see.  In particular, it generally means we have a load
124    through a pointer whose value came from outside the function.
125    Without an addressable symbol to point to, they would get the wrong
126    answer.
127
128    After flow insensitive aliasing is computed, we compute name tags
129    (called compute_flow_sensitive_info).  We walk each pointer we
130    collected and see if it has a usable points-to set.  If so, we
131    generate a name tag using that pointer, and make an alias bitmap for
132    it.  Name tags are shared between all things with the same alias
133    bitmap.  The alias bitmap will be translated from what points-to
134    computed.  In particular, the "anything" variable in points-to will be
135    transformed into a pruned set of SMT's and their aliases that
136    compute_flow_insensitive_aliasing computed.
137    Note that since 4.3, every pointer that points-to computed a solution for
138    will get a name tag (whereas before 4.3, only those whose set did
139    *not* include the anything variable would).  At the point where name
140    tags are all assigned, symbol memory tags are dead, and could be
141    deleted, *except* on global variables.  Global variables still use
142    symbol memory tags as of right now.
143
144    After name tags are computed, the set of clobbered variables is
145    transitively closed.  In particular, we compute the set of clobbered
146    variables based on the initial set of clobbers, plus the aliases of
147    pointers which either escape, or have their value escape.
148
149    After this, maybe_create_global_var is run, which handles a corner
150    case where we have no call clobbered variables, but have pure and
151    non-pure functions.
152    
153    Staring at this function, I now remember it is a hack for the fact
154    that we do not mark all globals in the program as call clobbered for a
155    function unless they are actually used in that function.  Instead,  we
156    only mark the set that is actually clobbered.  As a result, you can
157    end up with situations where you have no call clobbered vars set.
158    
159    After maybe_create_global_var, we set pointers with the REF_ALL flag
160    to have alias sets that include all clobbered
161    memory tags and variables.
162    
163    After this, memory partitioning is computed (by the function
164    compute_memory_partitions) and alias sets are reworked accordingly.
165
166    Lastly, we delete partitions with no symbols, and clean up after
167    ourselves.  */
168
169 /* Structure to map a variable to its alias set.  */
170 struct alias_map_d
171 {
172   /* Variable and its alias set.  */
173   tree var;
174   alias_set_type set;
175 };
176
177
178 /* Counters used to display statistics on alias analysis.  */
179 struct alias_stats_d
180 {
181   unsigned int alias_queries;
182   unsigned int alias_mayalias;
183   unsigned int alias_noalias;
184   unsigned int simple_queries;
185   unsigned int simple_resolved;
186   unsigned int tbaa_queries;
187   unsigned int tbaa_resolved;
188   unsigned int structnoaddress_queries;
189   unsigned int structnoaddress_resolved;
190 };
191
192
193 /* Local variables.  */
194 static struct alias_stats_d alias_stats;
195 static bitmap_obstack alias_bitmap_obstack;
196
197 /* Local functions.  */
198 static void compute_flow_insensitive_aliasing (struct alias_info *);
199 static void finalize_ref_all_pointers (struct alias_info *);
200 static void dump_alias_stats (FILE *);
201 static bool may_alias_p (tree, alias_set_type, tree, alias_set_type, bool);
202 static tree create_memory_tag (tree type, bool is_type_tag);
203 static tree get_smt_for (tree, struct alias_info *);
204 static tree get_nmt_for (tree);
205 static void add_may_alias (tree, tree);
206 static struct alias_info *init_alias_info (void);
207 static void delete_alias_info (struct alias_info *);
208 static void compute_flow_sensitive_aliasing (struct alias_info *);
209 static void setup_pointers_and_addressables (struct alias_info *);
210 static void create_global_var (void);
211 static void maybe_create_global_var (void);
212 static void set_pt_anything (tree);
213
214 void debug_mp_info (VEC(mem_sym_stats_t,heap) *);
215
216 static alloc_pool mem_sym_stats_pool;
217
218 /* Return memory reference stats for symbol VAR.  Create a new slot in
219    cfun->gimple_df->mem_sym_stats if needed.  */
220
221 static struct mem_sym_stats_d *
222 get_mem_sym_stats_for (tree var)
223 {
224   void **slot;
225   struct mem_sym_stats_d *stats;
226   struct pointer_map_t *map = gimple_mem_ref_stats (cfun)->mem_sym_stats;
227   
228   gcc_assert (map);
229
230   slot = pointer_map_insert (map, var);
231   if (*slot == NULL)
232     {
233       stats = pool_alloc (mem_sym_stats_pool);
234       memset (stats, 0, sizeof (*stats));
235       stats->var = var;
236       *slot = (void *) stats;
237     }
238   else
239     stats = (struct mem_sym_stats_d *) *slot;
240
241   return stats;
242 }
243
244
245 /* Return memory reference statistics for variable VAR in function FN.
246    This is computed by alias analysis, but it is not kept
247    incrementally up-to-date.  So, these stats are only accurate if
248    pass_may_alias has been run recently.  If no alias information
249    exists, this function returns NULL.  */
250
251 static mem_sym_stats_t
252 mem_sym_stats (struct function *fn, tree var)
253 {
254   void **slot;
255   struct pointer_map_t *stats_map = gimple_mem_ref_stats (fn)->mem_sym_stats;
256
257   if (stats_map == NULL)
258     return NULL;
259
260   slot = pointer_map_contains (stats_map, var);
261   if (slot == NULL)
262     return NULL;
263
264   return (mem_sym_stats_t) *slot;
265 }
266
267
268 /* Set MPT to be the memory partition associated with symbol SYM.  */
269
270 static inline void
271 set_memory_partition (tree sym, tree mpt)
272 {
273 #if defined ENABLE_CHECKING
274   if (mpt)
275     gcc_assert (TREE_CODE (mpt) == MEMORY_PARTITION_TAG
276                 && !is_gimple_reg (sym));
277 #endif
278
279   var_ann (sym)->mpt = mpt;
280   if (mpt)
281     {
282       if (MPT_SYMBOLS (mpt) == NULL)
283         MPT_SYMBOLS (mpt) = BITMAP_ALLOC (&alias_bitmap_obstack);
284
285       bitmap_set_bit (MPT_SYMBOLS (mpt), DECL_UID (sym));
286
287       /* MPT inherits the call-clobbering attributes from SYM.  */
288       if (is_call_clobbered (sym))
289         {
290           MTAG_GLOBAL (mpt) = 1;
291           mark_call_clobbered (mpt, ESCAPE_IS_GLOBAL);
292         }
293     }
294 }
295
296
297 /* Mark variable VAR as being non-addressable.  */
298
299 static void
300 mark_non_addressable (tree var)
301 {
302   tree mpt;
303
304   if (!TREE_ADDRESSABLE (var))
305     return;
306
307   mpt = memory_partition (var);
308
309   if (!MTAG_P (var))
310     var_ann (var)->call_clobbered = false;
311
312   bitmap_clear_bit (gimple_call_clobbered_vars (cfun), DECL_UID (var));
313   TREE_ADDRESSABLE (var) = 0;
314
315   if (mpt)
316     {
317       /* Note that it's possible for a symbol to have an associated
318          MPT and the MPT have a NULL empty set.  During
319          init_alias_info, all MPTs get their sets cleared out, but the
320          symbols still point to the old MPTs that used to hold them.
321          This is done so that compute_memory_partitions can now which
322          symbols are losing or changing partitions and mark them for
323          renaming.  */
324       if (MPT_SYMBOLS (mpt))
325         bitmap_clear_bit (MPT_SYMBOLS (mpt), DECL_UID (var));
326       set_memory_partition (var, NULL_TREE);
327     }
328 }
329
330
331 /* qsort comparison function to sort type/name tags by DECL_UID.  */
332
333 static int
334 sort_tags_by_id (const void *pa, const void *pb)
335 {
336   const_tree const a = *(const_tree const *)pa;
337   const_tree const b = *(const_tree const *)pb;
338  
339   return DECL_UID (a) - DECL_UID (b);
340 }
341
342 /* Initialize WORKLIST to contain those memory tags that are marked call
343    clobbered.  Initialized WORKLIST2 to contain the reasons these
344    memory tags escaped.  */
345
346 static void
347 init_transitive_clobber_worklist (VEC (tree, heap) **worklist,
348                                   VEC (int, heap) **worklist2,
349                                   bitmap on_worklist)
350 {
351   referenced_var_iterator rvi;
352   tree curr;
353
354   FOR_EACH_REFERENCED_VAR (curr, rvi)
355     {
356       if (MTAG_P (curr) && is_call_clobbered (curr))
357         {
358           VEC_safe_push (tree, heap, *worklist, curr);
359           VEC_safe_push (int, heap, *worklist2,
360                          var_ann (curr)->escape_mask);
361           bitmap_set_bit (on_worklist, DECL_UID (curr));
362         }
363     }
364 }
365
366 /* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if
367    ALIAS is not already marked call clobbered, and is a memory
368    tag.  */
369
370 static void
371 add_to_worklist (tree alias, VEC (tree, heap) **worklist,
372                  VEC (int, heap) **worklist2, int reason,
373                  bitmap on_worklist)
374 {
375   if (MTAG_P (alias) && !is_call_clobbered (alias)
376       && !bitmap_bit_p (on_worklist, DECL_UID (alias)))
377     {
378       VEC_safe_push (tree, heap, *worklist, alias);
379       VEC_safe_push (int, heap, *worklist2, reason);
380       bitmap_set_bit (on_worklist, DECL_UID (alias));
381     }
382 }
383
384 /* Mark aliases of TAG as call clobbered, and place any tags on the
385    alias list that were not already call clobbered on WORKLIST.  */
386
387 static void
388 mark_aliases_call_clobbered (tree tag, VEC (tree, heap) **worklist,
389                              VEC (int, heap) **worklist2,
390                              bitmap on_worklist, bitmap queued)
391 {
392   bitmap aliases;
393   bitmap_iterator bi;
394   unsigned int i;
395   tree entry;
396   var_ann_t ta = var_ann (tag);
397
398   if (!MTAG_P (tag))
399     return;
400   aliases = may_aliases (tag);
401   if (!aliases)
402     return;
403
404   EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
405     {
406       entry = referenced_var (i);
407       /* If you clobber one part of a structure, you
408          clobber the entire thing.  While this does not make
409          the world a particularly nice place, it is necessary
410          in order to allow C/C++ tricks that involve
411          pointer arithmetic to work.  */
412       if (TREE_CODE (entry) == STRUCT_FIELD_TAG)
413         bitmap_set_bit (queued, DECL_UID (SFT_PARENT_VAR (entry)));
414       else if (!unmodifiable_var_p (entry))
415         {
416           add_to_worklist (entry, worklist, worklist2, ta->escape_mask,
417                            on_worklist);
418           mark_call_clobbered (entry, ta->escape_mask);
419         }
420     }
421   if (!bitmap_empty_p (queued))
422     {
423       EXECUTE_IF_SET_IN_BITMAP (queued, 0, i, bi)
424         {
425           subvar_t svars = get_subvars_for_var (referenced_var (i));
426           unsigned int i;
427           tree subvar;
428
429           for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
430             if (!unmodifiable_var_p (subvar))
431                mark_call_clobbered (subvar, ta->escape_mask);
432         }
433       bitmap_clear (queued);
434     }
435 }
436
437 /* Tags containing global vars need to be marked as global.
438    Tags containing call clobbered vars need to be marked as call
439    clobbered. */
440
441 static void
442 compute_tag_properties (void)
443 {
444   referenced_var_iterator rvi;
445   tree tag;
446   bool changed = true;
447   VEC (tree, heap) *taglist = NULL;
448
449   FOR_EACH_REFERENCED_VAR (tag, rvi)
450     {
451       if (!MTAG_P (tag) || TREE_CODE (tag) == STRUCT_FIELD_TAG)
452         continue;
453       VEC_safe_push (tree, heap, taglist, tag);
454     }
455
456   /* We sort the taglist by DECL_UID, for two reasons.
457      1. To get a sequential ordering to make the bitmap accesses
458      faster.
459      2. Because of the way we compute aliases, it's more likely that
460      an earlier tag is included in a later tag, and this will reduce
461      the number of iterations.
462
463      If we had a real tag graph, we would just topo-order it and be
464      done with it.  */
465   qsort (VEC_address (tree, taglist),
466          VEC_length (tree, taglist),
467          sizeof (tree),
468          sort_tags_by_id);
469
470   /* Go through each tag not marked as global, and if it aliases
471      global vars, mark it global. 
472      
473      If the tag contains call clobbered vars, mark it call
474      clobbered.  
475
476      This loop iterates because tags may appear in the may-aliases
477      list of other tags when we group.  */
478
479   while (changed)
480     {
481       unsigned int k;
482
483       changed = false;      
484       for (k = 0; VEC_iterate (tree, taglist, k, tag); k++)
485         {
486           bitmap ma;
487           bitmap_iterator bi;
488           unsigned int i;
489           tree entry;
490           bool tagcc = is_call_clobbered (tag);
491           bool tagglobal = MTAG_GLOBAL (tag);
492           
493           if (tagcc && tagglobal)
494             continue;
495           
496           ma = may_aliases (tag);
497           if (!ma)
498             continue;
499
500           EXECUTE_IF_SET_IN_BITMAP (ma, 0, i, bi)
501             {
502               entry = referenced_var (i);
503               /* Call clobbered entries cause the tag to be marked
504                  call clobbered.  */
505               if (!tagcc && is_call_clobbered (entry))
506                 {
507                   mark_call_clobbered (tag, var_ann (entry)->escape_mask);
508                   tagcc = true;
509                   changed = true;
510                 }
511
512               /* Global vars cause the tag to be marked global.  */
513               if (!tagglobal && is_global_var (entry))
514                 {
515                   MTAG_GLOBAL (tag) = true;
516                   changed = true;
517                   tagglobal = true;
518                 }
519
520               /* Early exit once both global and cc are set, since the
521                  loop can't do any more than that.  */
522               if (tagcc && tagglobal)
523                 break;
524             }
525         }
526     }
527   VEC_free (tree, heap, taglist);
528 }
529
530 /* Set up the initial variable clobbers and globalness.
531    When this function completes, only tags whose aliases need to be
532    clobbered will be set clobbered.  Tags clobbered because they   
533    contain call clobbered vars are handled in compute_tag_properties.  */
534
535 static void
536 set_initial_properties (struct alias_info *ai)
537 {
538   unsigned int i;
539   referenced_var_iterator rvi;
540   tree var;
541   tree ptr;
542   bitmap queued;
543
544   /* Temporary bitmap to avoid quadratic behavior in marking
545      call clobbers.  */
546   queued = BITMAP_ALLOC (&alias_bitmap_obstack);
547
548   FOR_EACH_REFERENCED_VAR (var, rvi)
549     {
550       if (is_global_var (var) 
551           && (!var_can_have_subvars (var)
552               || get_subvars_for_var (var) == NULL))
553         {
554           if (!unmodifiable_var_p (var))
555             mark_call_clobbered (var, ESCAPE_IS_GLOBAL);
556         }
557       else if (TREE_CODE (var) == PARM_DECL
558                && gimple_default_def (cfun, var)
559                && POINTER_TYPE_P (TREE_TYPE (var)))
560         {
561           tree def = gimple_default_def (cfun, var);
562           get_ptr_info (def)->value_escapes_p = 1;
563           get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM;      
564         }
565     }
566
567   for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
568     {
569       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
570       tree tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
571       
572       if (pi->value_escapes_p)
573         {
574           /* If PTR escapes then its associated memory tags and
575              pointed-to variables are call-clobbered.  */
576           if (pi->name_mem_tag)
577             mark_call_clobbered (pi->name_mem_tag, pi->escape_mask);
578
579           if (tag)
580             mark_call_clobbered (tag, pi->escape_mask);
581
582           if (pi->pt_vars)
583             {
584               bitmap_iterator bi;
585               unsigned int j;         
586               EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
587                 {
588                   tree alias = referenced_var (j);
589
590                   /* If you clobber one part of a structure, you
591                      clobber the entire thing.  While this does not make
592                      the world a particularly nice place, it is necessary
593                      in order to allow C/C++ tricks that involve
594                      pointer arithmetic to work.  */
595                   if (TREE_CODE (alias) == STRUCT_FIELD_TAG)
596                     bitmap_set_bit (queued, DECL_UID (SFT_PARENT_VAR (alias)));
597                   else if (!unmodifiable_var_p (alias))
598                     mark_call_clobbered (alias, pi->escape_mask);
599                 }
600               /* Process variables we need to clobber all parts of.  */
601               if (!bitmap_empty_p (queued))
602                 {
603                   EXECUTE_IF_SET_IN_BITMAP (queued, 0, j, bi)
604                     {
605                       subvar_t svars = get_subvars_for_var (referenced_var (j));
606                       unsigned int i;
607                       tree subvar;
608
609                       for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
610                         if (!unmodifiable_var_p (subvar))
611                           mark_call_clobbered (subvar, pi->escape_mask);
612                     }
613                   bitmap_clear (queued);
614                 }
615             }
616         }
617
618       /* If the name tag is call clobbered, so is the symbol tag
619          associated with the base VAR_DECL.  */
620       if (pi->name_mem_tag
621           && tag
622           && is_call_clobbered (pi->name_mem_tag))
623         mark_call_clobbered (tag, pi->escape_mask);
624
625       /* Name tags and symbol tags that we don't know where they point
626          to, might point to global memory, and thus, are clobbered.
627
628          FIXME:  This is not quite right.  They should only be
629          clobbered if value_escapes_p is true, regardless of whether
630          they point to global memory or not.
631          So removing this code and fixing all the bugs would be nice.
632          It is the cause of a bunch of clobbering.  */
633       if ((pi->pt_global_mem || pi->pt_anything) 
634           && pi->is_dereferenced && pi->name_mem_tag)
635         {
636           mark_call_clobbered (pi->name_mem_tag, ESCAPE_IS_GLOBAL);
637           MTAG_GLOBAL (pi->name_mem_tag) = true;
638         }
639       
640       if ((pi->pt_global_mem || pi->pt_anything) 
641           && pi->is_dereferenced
642           && tag)
643         {
644           mark_call_clobbered (tag, ESCAPE_IS_GLOBAL);
645           MTAG_GLOBAL (tag) = true;
646         }
647     }
648
649   BITMAP_FREE (queued);
650 }
651
652 /* Compute which variables need to be marked call clobbered because
653    their tag is call clobbered, and which tags need to be marked
654    global because they contain global variables.  */
655
656 static void
657 compute_call_clobbered (struct alias_info *ai)
658 {
659   VEC (tree, heap) *worklist = NULL;
660   VEC (int,heap) *worklist2 = NULL;
661   bitmap on_worklist, queued;
662
663   timevar_push (TV_CALL_CLOBBER);
664   on_worklist = BITMAP_ALLOC (NULL);
665   queued = BITMAP_ALLOC (NULL);
666     
667   set_initial_properties (ai);
668   init_transitive_clobber_worklist (&worklist, &worklist2, on_worklist);
669   while (VEC_length (tree, worklist) != 0)
670     {
671       tree curr = VEC_pop (tree, worklist);
672       int reason = VEC_pop (int, worklist2);
673
674       bitmap_clear_bit (on_worklist, DECL_UID (curr));
675       mark_call_clobbered (curr, reason);
676       mark_aliases_call_clobbered (curr, &worklist, &worklist2,
677                                    on_worklist, queued);
678     }
679   VEC_free (tree, heap, worklist);
680   VEC_free (int, heap, worklist2);
681   BITMAP_FREE (on_worklist);
682   BITMAP_FREE (queued);
683   compute_tag_properties ();
684   timevar_pop (TV_CALL_CLOBBER);
685 }
686
687
688 /* Dump memory partition information to FILE.  */
689
690 static void
691 dump_memory_partitions (FILE *file)
692 {
693   unsigned i, npart;
694   unsigned long nsyms;
695   tree mpt;
696
697   fprintf (file, "\nMemory partitions\n\n");
698   for (i = 0, npart = 0, nsyms = 0;
699        VEC_iterate (tree, gimple_ssa_operands (cfun)->mpt_table, i, mpt);
700        i++)
701     {
702       if (mpt)
703         {
704           bitmap syms = MPT_SYMBOLS (mpt);
705           unsigned long n = (syms) ? bitmap_count_bits (syms) : 0;
706
707           fprintf (file, "#%u: ", i);
708           print_generic_expr (file, mpt, 0);
709           fprintf (file, ": %lu elements: ", n);
710           dump_decl_set (file, syms);
711           npart++;
712           nsyms += n;
713         }
714     }
715
716   fprintf (file, "\n%u memory partitions holding %lu symbols\n", npart, nsyms);
717 }
718
719
720 /* Dump memory partition information to stderr.  */
721
722 void
723 debug_memory_partitions (void)
724 {
725   dump_memory_partitions (stderr);
726 }
727
728
729 /* Return true if memory partitioning is required given the memory
730    reference estimates in STATS.  */
731
732 static inline bool
733 need_to_partition_p (struct mem_ref_stats_d *stats)
734 {
735   long num_vops = stats->num_vuses + stats->num_vdefs;
736   long avg_vops = CEIL (num_vops, stats->num_mem_stmts);
737   return (num_vops > (long) MAX_ALIASED_VOPS
738           && avg_vops > (long) AVG_ALIASED_VOPS);
739 }
740
741
742 /* Count the actual number of virtual operators in CFUN.  Note that
743    this is only meaningful after virtual operands have been populated,
744    so it should be invoked at the end of compute_may_aliases.
745
746    The number of virtual operators are stored in *NUM_VDEFS_P and
747    *NUM_VUSES_P, the number of partitioned symbols in
748    *NUM_PARTITIONED_P and the number of unpartitioned symbols in
749    *NUM_UNPARTITIONED_P.
750
751    If any of these pointers is NULL the corresponding count is not
752    computed.  */
753
754 static void
755 count_mem_refs (long *num_vuses_p, long *num_vdefs_p,
756                 long *num_partitioned_p, long *num_unpartitioned_p)
757 {
758   block_stmt_iterator bsi;
759   basic_block bb;
760   long num_vdefs, num_vuses, num_partitioned, num_unpartitioned;
761   referenced_var_iterator rvi;
762   tree sym;
763
764   num_vuses = num_vdefs = num_partitioned = num_unpartitioned = 0;
765
766   if (num_vuses_p || num_vdefs_p)
767     FOR_EACH_BB (bb)
768       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
769         {
770           tree stmt = bsi_stmt (bsi);
771           if (stmt_references_memory_p (stmt))
772             {
773               num_vuses += NUM_SSA_OPERANDS (stmt, SSA_OP_VUSE);
774               num_vdefs += NUM_SSA_OPERANDS (stmt, SSA_OP_VDEF);
775             }
776         }
777
778   if (num_partitioned_p || num_unpartitioned_p)
779     FOR_EACH_REFERENCED_VAR (sym, rvi)
780       {
781         if (is_gimple_reg (sym))
782           continue;
783
784         if (memory_partition (sym))
785           num_partitioned++;
786         else
787           num_unpartitioned++;
788       }
789
790   if (num_vdefs_p)
791     *num_vdefs_p = num_vdefs;
792
793   if (num_vuses_p)
794     *num_vuses_p = num_vuses;
795
796   if (num_partitioned_p)
797     *num_partitioned_p = num_partitioned;
798
799   if (num_unpartitioned_p)
800     *num_unpartitioned_p = num_unpartitioned;
801 }
802
803
804 /* The list is sorted by increasing partitioning score (PSCORE).
805    This score is computed such that symbols with high scores are
806    those that are least likely to be partitioned.  Given a symbol
807    MP->VAR, PSCORE(S) is the result of the following weighted sum
808
809    PSCORE(S) =   FW * 64 + FR * 32
810                + DW * 16 + DR *  8 
811                + IW *  4 + IR *  2
812                + NO_ALIAS
813
814    where
815
816    FW           Execution frequency of writes to S
817    FR           Execution frequency of reads from S
818    DW           Number of direct writes to S
819    DR           Number of direct reads from S
820    IW           Number of indirect writes to S
821    IR           Number of indirect reads from S
822    NO_ALIAS     State of the NO_ALIAS* flags
823
824    The basic idea here is that symbols that are frequently
825    written-to in hot paths of the code are the last to be considered
826    for partitioning.  */
827
828 static inline long
829 mem_sym_score (mem_sym_stats_t mp)
830 {
831   /* Unpartitionable SFTs are automatically thrown to the bottom of
832      the list.  They are not stored in partitions, but they are used
833      for computing overall statistics.  */
834   if (TREE_CODE (mp->var) == STRUCT_FIELD_TAG
835       && SFT_UNPARTITIONABLE_P (mp->var))
836     return LONG_MAX;
837
838   return mp->frequency_writes * 64 + mp->frequency_reads * 32
839          + mp->num_direct_writes * 16 + mp->num_direct_reads * 8
840          + mp->num_indirect_writes * 4 + mp->num_indirect_reads * 2
841          + var_ann (mp->var)->noalias_state;
842 }
843
844
845 /* Dump memory reference stats for function CFUN to FILE.  */
846
847 void
848 dump_mem_ref_stats (FILE *file)
849 {
850   long actual_num_vuses, actual_num_vdefs;
851   long num_partitioned, num_unpartitioned;
852   struct mem_ref_stats_d *stats;
853   
854   stats = gimple_mem_ref_stats (cfun);
855
856   count_mem_refs (&actual_num_vuses, &actual_num_vdefs, &num_partitioned,
857                   &num_unpartitioned);
858
859   fprintf (file, "\nMemory reference statistics for %s\n\n", 
860            lang_hooks.decl_printable_name (current_function_decl, 2));
861
862   fprintf (file, "Number of memory statements:     %ld\n",
863            stats->num_mem_stmts);
864   fprintf (file, "Number of call sites:            %ld\n",
865            stats->num_call_sites);
866   fprintf (file, "Number of pure/const call sites: %ld\n",
867            stats->num_pure_const_call_sites);
868   fprintf (file, "Number of asm sites:             %ld\n",
869            stats->num_asm_sites);
870   fprintf (file, "Estimated number of loads:       %ld (%ld/stmt)\n",
871            stats->num_vuses,
872            (stats->num_mem_stmts)
873            ? CEIL (stats->num_vuses, stats->num_mem_stmts)
874            : 0);
875   fprintf (file, "Actual number of loads:          %ld (%ld/stmt)\n",
876            actual_num_vuses, 
877            (stats->num_mem_stmts)
878            ? CEIL (actual_num_vuses, stats->num_mem_stmts)
879            : 0);
880
881   if (actual_num_vuses > stats->num_vuses + (stats->num_vuses / 25))
882     fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n");
883
884   fprintf (file, "Estimated number of stores:      %ld (%ld/stmt)\n",
885            stats->num_vdefs,
886            (stats->num_mem_stmts)
887            ? CEIL (stats->num_vdefs, stats->num_mem_stmts)
888            : 0);
889   fprintf (file, "Actual number of stores:         %ld (%ld/stmt)\n",
890            actual_num_vdefs, 
891            (stats->num_mem_stmts)
892            ? CEIL (actual_num_vdefs, stats->num_mem_stmts)
893            : 0);
894
895   if (actual_num_vdefs > stats->num_vdefs + (stats->num_vdefs / 25))
896     fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n");
897
898   fprintf (file, "Partitioning thresholds:         MAX = %d   AVG = %d "
899            "(%sNEED TO PARTITION)\n", MAX_ALIASED_VOPS, AVG_ALIASED_VOPS,
900            stats->num_mem_stmts && need_to_partition_p (stats) ? "" : "NO ");
901   fprintf (file, "Number of partitioned symbols:   %ld\n", num_partitioned);
902   fprintf (file, "Number of unpartitioned symbols: %ld\n", num_unpartitioned);
903 }
904
905
906 /* Dump memory reference stats for function FN to stderr.  */
907
908 void
909 debug_mem_ref_stats (void)
910 {
911   dump_mem_ref_stats (stderr);
912 }
913
914
915 /* Dump memory reference stats for variable VAR to FILE.  */
916
917 static void
918 dump_mem_sym_stats (FILE *file, tree var)
919 {
920   mem_sym_stats_t stats = mem_sym_stats (cfun, var);
921
922   if (stats == NULL)
923     return;
924
925   fprintf (file, "read frequency: %6ld, write frequency: %6ld, "
926            "direct reads: %3ld, direct writes: %3ld, "
927            "indirect reads: %4ld, indirect writes: %4ld, symbol: ",
928            stats->frequency_reads, stats->frequency_writes,
929            stats->num_direct_reads, stats->num_direct_writes,
930            stats->num_indirect_reads, stats->num_indirect_writes);
931   print_generic_expr (file, stats->var, 0);
932   fprintf (file, ", tags: ");
933   dump_decl_set (file, stats->parent_tags);
934 }
935
936
937 /* Dump memory reference stats for variable VAR to stderr.  */
938
939 void
940 debug_mem_sym_stats (tree var)
941 {
942   dump_mem_sym_stats (stderr, var);
943 }
944
945 /* Dump memory reference stats for variable VAR to FILE.  For use
946    of tree-dfa.c:dump_variable.  */
947
948 void
949 dump_mem_sym_stats_for_var (FILE *file, tree var)
950 {
951   mem_sym_stats_t stats = mem_sym_stats (cfun, var);
952
953   if (stats == NULL)
954     return;
955
956   fprintf (file, ", score: %ld", mem_sym_score (stats));
957   fprintf (file, ", direct reads: %ld", stats->num_direct_reads);
958   fprintf (file, ", direct writes: %ld", stats->num_direct_writes);
959   fprintf (file, ", indirect reads: %ld", stats->num_indirect_reads);
960   fprintf (file, ", indirect writes: %ld", stats->num_indirect_writes);
961 }
962
963 /* Dump memory reference stats for all memory symbols to FILE.  */
964
965 static void
966 dump_all_mem_sym_stats (FILE *file)
967 {
968   referenced_var_iterator rvi;
969   tree sym;
970
971   FOR_EACH_REFERENCED_VAR (sym, rvi)
972     {
973       if (is_gimple_reg (sym))
974         continue;
975
976       dump_mem_sym_stats (file, sym);
977     }
978 }
979
980
981 /* Dump memory reference stats for all memory symbols to stderr.  */
982
983 void
984 debug_all_mem_sym_stats (void)
985 {
986   dump_all_mem_sym_stats (stderr);
987 }
988
989
990 /* Dump the MP_INFO array to FILE.  */
991
992 static void
993 dump_mp_info (FILE *file, VEC(mem_sym_stats_t,heap) *mp_info)
994 {
995   unsigned i;
996   mem_sym_stats_t mp_p;
997
998   for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
999     if (!mp_p->partitioned_p)
1000       dump_mem_sym_stats (file, mp_p->var);
1001 }
1002
1003
1004 /* Dump the MP_INFO array to stderr.  */
1005
1006 void
1007 debug_mp_info (VEC(mem_sym_stats_t,heap) *mp_info)
1008 {
1009   dump_mp_info (stderr, mp_info);
1010 }
1011
1012
1013 /* Update memory reference stats for symbol VAR in statement STMT.
1014    NUM_DIRECT_READS and NUM_DIRECT_WRITES specify the number of times
1015    that VAR is read/written in STMT (indirect reads/writes are not
1016    recorded by this function, see compute_memory_partitions).  */
1017
1018 void
1019 update_mem_sym_stats_from_stmt (tree var, tree stmt, long num_direct_reads,
1020                                 long num_direct_writes)
1021 {
1022   mem_sym_stats_t stats;
1023
1024   gcc_assert (num_direct_reads >= 0 && num_direct_writes >= 0);
1025
1026   stats = get_mem_sym_stats_for (var);
1027
1028   stats->num_direct_reads += num_direct_reads;
1029   stats->frequency_reads += ((long) bb_for_stmt (stmt)->frequency
1030                              * num_direct_reads);
1031
1032   stats->num_direct_writes += num_direct_writes;
1033   stats->frequency_writes += ((long) bb_for_stmt (stmt)->frequency
1034                               * num_direct_writes);
1035 }
1036
1037
1038 /* Given two MP_INFO entries MP1 and MP2, return -1 if MP1->VAR should
1039    be partitioned before MP2->VAR, 0 if they are the same or 1 if
1040    MP1->VAR should be partitioned after MP2->VAR.  */
1041
1042 static inline int
1043 compare_mp_info_entries (mem_sym_stats_t mp1, mem_sym_stats_t mp2)
1044 {
1045   long pscore1 = mem_sym_score (mp1);
1046   long pscore2 = mem_sym_score (mp2);
1047
1048   if (pscore1 < pscore2)
1049     return -1;
1050   else if (pscore1 > pscore2)
1051     return 1;
1052   else
1053     return DECL_UID (mp1->var) - DECL_UID (mp2->var);
1054 }
1055
1056
1057 /* Comparison routine for qsort.  The list is sorted by increasing
1058    partitioning score (PSCORE).  This score is computed such that
1059    symbols with high scores are those that are least likely to be
1060    partitioned.  */
1061
1062 static int
1063 mp_info_cmp (const void *p, const void *q)
1064 {
1065   mem_sym_stats_t e1 = *((const mem_sym_stats_t *) p);
1066   mem_sym_stats_t e2 = *((const mem_sym_stats_t *) q);
1067   return compare_mp_info_entries (e1, e2);
1068 }
1069
1070
1071 /* Sort the array of reference counts used to compute memory partitions.
1072    Elements are sorted in ascending order of execution frequency and 
1073    descending order of virtual operators needed.  */
1074
1075 static inline void
1076 sort_mp_info (VEC(mem_sym_stats_t,heap) *list)
1077 {
1078   unsigned num = VEC_length (mem_sym_stats_t, list);
1079
1080   if (num < 2)
1081     return;
1082
1083   if (num == 2)
1084     {
1085       if (compare_mp_info_entries (VEC_index (mem_sym_stats_t, list, 0),
1086                                    VEC_index (mem_sym_stats_t, list, 1)) > 0)
1087         {  
1088           /* Swap elements if they are in the wrong order.  */
1089           mem_sym_stats_t tmp = VEC_index (mem_sym_stats_t, list, 0);
1090           VEC_replace (mem_sym_stats_t, list, 0,
1091                        VEC_index (mem_sym_stats_t, list, 1));
1092           VEC_replace (mem_sym_stats_t, list, 1, tmp);
1093         }
1094
1095       return;
1096     }
1097
1098   /* There are 3 or more elements, call qsort.  */
1099   qsort (VEC_address (mem_sym_stats_t, list),
1100          VEC_length (mem_sym_stats_t, list), 
1101          sizeof (mem_sym_stats_t),
1102          mp_info_cmp);
1103 }
1104
1105
1106 /* Return the memory partition tag (MPT) associated with memory
1107    symbol SYM.  */
1108
1109 static tree
1110 get_mpt_for (tree sym)
1111 {
1112   tree mpt;
1113
1114   /* Don't create a new tag unnecessarily.  */
1115   mpt = memory_partition (sym);
1116   if (mpt == NULL_TREE)
1117     {
1118       mpt = create_tag_raw (MEMORY_PARTITION_TAG, TREE_TYPE (sym), "MPT");
1119       TREE_ADDRESSABLE (mpt) = 0;
1120       add_referenced_var (mpt);
1121       VEC_safe_push (tree, heap, gimple_ssa_operands (cfun)->mpt_table, mpt);
1122       gcc_assert (MPT_SYMBOLS (mpt) == NULL);
1123       set_memory_partition (sym, mpt);
1124     }
1125
1126   return mpt;
1127 }
1128
1129
1130 /* Add MP_P->VAR to a memory partition and return the partition.  */
1131
1132 static tree
1133 find_partition_for (mem_sym_stats_t mp_p)
1134 {
1135   unsigned i;
1136   VEC(tree,heap) *mpt_table;
1137   tree mpt;
1138
1139   mpt_table = gimple_ssa_operands (cfun)->mpt_table;
1140   mpt = NULL_TREE;
1141
1142   /* Find an existing partition for MP_P->VAR.  */
1143   for (i = 0; VEC_iterate (tree, mpt_table, i, mpt); i++)
1144     {
1145       mem_sym_stats_t mpt_stats;
1146
1147       /* If MPT does not have any symbols yet, use it.  */
1148       if (MPT_SYMBOLS (mpt) == NULL)
1149         break;
1150
1151       /* Otherwise, see if MPT has common parent tags with MP_P->VAR,
1152          but avoid grouping clobbered variables with non-clobbered
1153          variables (otherwise, this tends to creates a single memory
1154          partition because other call-clobbered variables may have
1155          common parent tags with non-clobbered ones).  */
1156       mpt_stats = get_mem_sym_stats_for (mpt);
1157       if (mp_p->parent_tags
1158           && mpt_stats->parent_tags
1159           && is_call_clobbered (mpt) == is_call_clobbered (mp_p->var)
1160           && bitmap_intersect_p (mpt_stats->parent_tags, mp_p->parent_tags))
1161         break;
1162
1163       /* If no common parent tags are found, see if both MPT and
1164          MP_P->VAR are call-clobbered.  */
1165       if (is_call_clobbered (mpt) && is_call_clobbered (mp_p->var))
1166         break;
1167     }
1168
1169   if (mpt == NULL_TREE)
1170     mpt = get_mpt_for (mp_p->var);
1171   else
1172     set_memory_partition (mp_p->var, mpt);
1173
1174   mp_p->partitioned_p = true;
1175
1176   mark_sym_for_renaming (mp_p->var);
1177   mark_sym_for_renaming (mpt);
1178
1179   return mpt;
1180 }
1181
1182
1183 /* Rewrite the alias set for TAG to use the newly created partitions.
1184    If TAG is NULL, rewrite the set of call-clobbered variables.
1185    NEW_ALIASES is a scratch bitmap to build the new set of aliases for
1186    TAG.  */
1187
1188 static void
1189 rewrite_alias_set_for (tree tag, bitmap new_aliases)
1190 {
1191   bitmap_iterator bi;
1192   unsigned i;
1193   tree mpt, sym;
1194
1195   EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, i, bi)
1196     {
1197       sym = referenced_var (i);
1198       mpt = memory_partition (sym);
1199       if (mpt)
1200         bitmap_set_bit (new_aliases, DECL_UID (mpt));
1201       else
1202         bitmap_set_bit (new_aliases, DECL_UID (sym));
1203     }
1204
1205   /* Rebuild the may-alias array for TAG.  */
1206   bitmap_copy (MTAG_ALIASES (tag), new_aliases);
1207 }
1208
1209
1210 /* Determine how many virtual operands can be saved by partitioning
1211    MP_P->VAR into MPT.  When a symbol S is thrown inside a partition
1212    P, every virtual operand that used to reference S will now
1213    reference P.  Whether it reduces the number of virtual operands
1214    depends on:
1215
1216    1- Direct references to S are never saved.  Instead of the virtual
1217       operand to S, we will now have a virtual operand to P.
1218
1219    2- Indirect references to S are reduced only for those memory tags
1220       holding S that already had other symbols partitioned into P.
1221       For instance, if a memory tag T has the alias set { a b S c },
1222       the first time we partition S into P, the alias set will become
1223       { a b P c }, so no virtual operands will be saved. However, if
1224       we now partition symbol 'c' into P, then the alias set for T
1225       will become { a b P }, so we will be saving one virtual operand
1226       for every indirect reference to 'c'.
1227
1228    3- Is S is call-clobbered, we save as many virtual operands as
1229       call/asm sites exist in the code, but only if other
1230       call-clobbered symbols have been grouped into P.  The first
1231       call-clobbered symbol that we group does not produce any
1232       savings.
1233
1234    MEM_REF_STATS points to CFUN's memory reference information.  */
1235
1236 static void
1237 estimate_vop_reduction (struct mem_ref_stats_d *mem_ref_stats,
1238                         mem_sym_stats_t mp_p, tree mpt)
1239 {
1240   unsigned i;
1241   bitmap_iterator bi;
1242   mem_sym_stats_t mpt_stats;
1243
1244   /* We should only get symbols with indirect references here.  */
1245   gcc_assert (mp_p->num_indirect_reads > 0 || mp_p->num_indirect_writes > 0);
1246
1247   /* Note that the only statistics we keep for MPT is the set of
1248      parent tags to know which memory tags have had alias members
1249      partitioned, and the indicator has_call_clobbered_vars.
1250      Reference counts are not important for MPT.  */
1251   mpt_stats = get_mem_sym_stats_for (mpt);
1252
1253   /* Traverse all the parent tags for MP_P->VAR.  For every tag T, if
1254      partition P is already grouping aliases of T, then reduce the
1255      number of virtual operands by the number of direct references
1256      to T.  */
1257   if (mp_p->parent_tags)
1258     {
1259       if (mpt_stats->parent_tags == NULL)
1260         mpt_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack);
1261
1262       EXECUTE_IF_SET_IN_BITMAP (mp_p->parent_tags, 0, i, bi)
1263         {
1264           if (bitmap_bit_p (mpt_stats->parent_tags, i))
1265             {
1266               /* Partition MPT is already partitioning symbols in the
1267                  alias set for TAG.  This means that we are now saving
1268                  1 virtual operand for every direct reference to TAG.  */
1269               tree tag = referenced_var (i);
1270               mem_sym_stats_t tag_stats = mem_sym_stats (cfun, tag);
1271               mem_ref_stats->num_vuses -= tag_stats->num_direct_reads;
1272               mem_ref_stats->num_vdefs -= tag_stats->num_direct_writes;
1273             }
1274           else
1275             {
1276               /* This is the first symbol in tag I's alias set that is
1277                  being grouped under MPT.  We will not save any
1278                  virtual operands this time, but record that MPT is
1279                  grouping a symbol from TAG's alias set so that the
1280                  next time we get the savings.  */
1281               bitmap_set_bit (mpt_stats->parent_tags, i);
1282             }
1283         }
1284     }
1285
1286   /* If MP_P->VAR is call-clobbered, and MPT is already grouping
1287      call-clobbered symbols, then we will save as many virtual
1288      operands as asm/call sites there are.  */
1289   if (is_call_clobbered (mp_p->var))
1290     {
1291       if (mpt_stats->has_call_clobbered_vars)
1292         mem_ref_stats->num_vdefs -= mem_ref_stats->num_call_sites
1293                                     + mem_ref_stats->num_asm_sites;
1294       else
1295         mpt_stats->has_call_clobbered_vars = true;
1296     }
1297 }
1298
1299
1300 /* Helper for compute_memory_partitions.  Transfer reference counts
1301    from pointers to their pointed-to sets.  Counters for pointers were
1302    computed by update_alias_info.  MEM_REF_STATS points to CFUN's
1303    memory reference information.  */
1304
1305 static void
1306 update_reference_counts (struct mem_ref_stats_d *mem_ref_stats)
1307 {
1308   unsigned i;
1309   bitmap_iterator bi;
1310   mem_sym_stats_t sym_stats;
1311
1312   for (i = 1; i < num_ssa_names; i++)
1313     {
1314       tree ptr;
1315       struct ptr_info_def *pi;
1316
1317       ptr = ssa_name (i);
1318       if (ptr
1319           && POINTER_TYPE_P (TREE_TYPE (ptr))
1320           && (pi = SSA_NAME_PTR_INFO (ptr)) != NULL
1321           && pi->is_dereferenced)
1322         {
1323           unsigned j;
1324           bitmap_iterator bj;
1325           tree tag;
1326           mem_sym_stats_t ptr_stats, tag_stats;
1327
1328           /* If PTR has flow-sensitive points-to information, use
1329              PTR's name tag, otherwise use the symbol tag associated
1330              with PTR's symbol.  */
1331           if (pi->name_mem_tag)
1332             tag = pi->name_mem_tag;
1333           else
1334             tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
1335
1336           ptr_stats = get_mem_sym_stats_for (ptr);
1337           tag_stats = get_mem_sym_stats_for (tag);
1338
1339           /* TAG has as many direct references as dereferences we
1340              found for its parent pointer.  */
1341           tag_stats->num_direct_reads += ptr_stats->num_direct_reads;
1342           tag_stats->num_direct_writes += ptr_stats->num_direct_writes;
1343
1344           /* All the dereferences of pointer PTR are considered direct
1345              references to PTR's memory tag (TAG).  In turn,
1346              references to TAG will become virtual operands for every
1347              symbol in TAG's alias set.  So, for every symbol ALIAS in
1348              TAG's alias set, add as many indirect references to ALIAS
1349              as direct references there are for TAG.  */
1350           if (MTAG_ALIASES (tag))
1351             EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, j, bj)
1352               {
1353                 tree alias = referenced_var (j);
1354                 sym_stats = get_mem_sym_stats_for (alias);
1355
1356                 /* All the direct references to TAG are indirect references
1357                    to ALIAS.  */
1358                 sym_stats->num_indirect_reads += ptr_stats->num_direct_reads;
1359                 sym_stats->num_indirect_writes += ptr_stats->num_direct_writes;
1360                 sym_stats->frequency_reads += ptr_stats->frequency_reads;
1361                 sym_stats->frequency_writes += ptr_stats->frequency_writes;
1362
1363                 /* Indicate that TAG is one of ALIAS's parent tags.  */
1364                 if (sym_stats->parent_tags == NULL)
1365                   sym_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack);
1366                 bitmap_set_bit (sym_stats->parent_tags, DECL_UID (tag));
1367               }
1368         }
1369     }
1370
1371   /* Call-clobbered symbols are indirectly written at every
1372      call/asm site.  */
1373   EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
1374     {
1375       tree sym = referenced_var (i);
1376       sym_stats = get_mem_sym_stats_for (sym);
1377       sym_stats->num_indirect_writes += mem_ref_stats->num_call_sites
1378                                         + mem_ref_stats->num_asm_sites;
1379     }
1380
1381   /* Addressable symbols are indirectly written at some ASM sites.
1382      Since only ASM sites that clobber memory actually affect
1383      addressable symbols, this is an over-estimation.  */
1384   EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun), 0, i, bi)
1385     {
1386       tree sym = referenced_var (i);
1387       sym_stats = get_mem_sym_stats_for (sym);
1388       sym_stats->num_indirect_writes += mem_ref_stats->num_asm_sites;
1389     }
1390 }
1391
1392
1393 /* Helper for compute_memory_partitions.  Add all memory symbols to
1394    *MP_INFO_P and compute the initial estimate for the total number of
1395    virtual operands needed.  MEM_REF_STATS points to CFUN's memory
1396    reference information.  On exit, *TAGS_P will contain the list of
1397    memory tags whose alias set need to be rewritten after
1398    partitioning.  */
1399
1400 static void
1401 build_mp_info (struct mem_ref_stats_d *mem_ref_stats,
1402                VEC(mem_sym_stats_t,heap) **mp_info_p,
1403                VEC(tree,heap) **tags_p)
1404 {
1405   tree var;
1406   referenced_var_iterator rvi;
1407
1408   FOR_EACH_REFERENCED_VAR (var, rvi)
1409     {
1410       mem_sym_stats_t sym_stats;
1411       tree old_mpt;
1412
1413       /* We are only interested in memory symbols other than MPTs.  */
1414       if (is_gimple_reg (var) || TREE_CODE (var) == MEMORY_PARTITION_TAG)
1415         continue;
1416
1417       /* Collect memory tags into the TAGS array so that we can
1418          rewrite their alias sets after partitioning.  */
1419       if (MTAG_P (var) && MTAG_ALIASES (var))
1420         VEC_safe_push (tree, heap, *tags_p, var);
1421
1422       /* Since we are going to re-compute partitions, any symbols that
1423          used to belong to a partition must be detached from it and
1424          marked for renaming.  */
1425       if ((old_mpt = memory_partition (var)) != NULL)
1426         {
1427           mark_sym_for_renaming (old_mpt);
1428           set_memory_partition (var, NULL_TREE);
1429           mark_sym_for_renaming (var);
1430         }
1431
1432       sym_stats = get_mem_sym_stats_for (var);
1433
1434       /* Add VAR's reference info to MP_INFO.  Note that the only
1435          symbols that make sense to partition are those that have
1436          indirect references.  If a symbol S is always directly
1437          referenced, partitioning it will not reduce the number of
1438          virtual operators.  The only symbols that are profitable to
1439          partition are those that belong to alias sets and/or are
1440          call-clobbered.  */
1441       if (sym_stats->num_indirect_reads > 0
1442           || sym_stats->num_indirect_writes > 0)
1443         VEC_safe_push (mem_sym_stats_t, heap, *mp_info_p, sym_stats);
1444
1445       /* Update the number of estimated VOPS.  Note that direct
1446          references to memory tags are always counted as indirect
1447          references to their alias set members, so if a memory tag has
1448          aliases, do not count its direct references to avoid double
1449          accounting.  */
1450       if (!MTAG_P (var) || !MTAG_ALIASES (var))
1451         {
1452           mem_ref_stats->num_vuses += sym_stats->num_direct_reads;
1453           mem_ref_stats->num_vdefs += sym_stats->num_direct_writes;
1454         }
1455
1456       mem_ref_stats->num_vuses += sym_stats->num_indirect_reads;
1457       mem_ref_stats->num_vdefs += sym_stats->num_indirect_writes;
1458     }
1459 }
1460
1461
1462 /* Compute memory partitions.  A memory partition (MPT) is an
1463    arbitrary grouping of memory symbols, such that references to one
1464    member of the group is considered a reference to all the members of
1465    the group.
1466    
1467    As opposed to alias sets in memory tags, the grouping into
1468    partitions is completely arbitrary and only done to reduce the
1469    number of virtual operands.  The only rule that needs to be
1470    observed when creating memory partitions is that given two memory
1471    partitions MPT.i and MPT.j, they must not contain symbols in
1472    common.
1473
1474    Memory partitions are used when putting the program into Memory-SSA
1475    form.  In particular, in Memory-SSA PHI nodes are not computed for
1476    individual memory symbols.  They are computed for memory
1477    partitions.  This reduces the amount of PHI nodes in the SSA graph
1478    at the expense of precision (i.e., it makes unrelated stores affect
1479    each other).
1480    
1481    However, it is possible to increase precision by changing this
1482    partitioning scheme.  For instance, if the partitioning scheme is
1483    such that get_mpt_for is the identity function (that is,
1484    get_mpt_for (s) = s), this will result in ultimate precision at the
1485    expense of huge SSA webs.
1486
1487    At the other extreme, a partitioning scheme that groups all the
1488    symbols in the same set results in minimal SSA webs and almost
1489    total loss of precision.
1490
1491    There partitioning heuristic uses three parameters to decide the
1492    order in which symbols are processed.  The list of symbols is
1493    sorted so that symbols that are more likely to be partitioned are
1494    near the top of the list:
1495
1496    - Execution frequency.  If a memory references is in a frequently
1497      executed code path, grouping it into a partition may block useful
1498      transformations and cause sub-optimal code generation.  So, the
1499      partition heuristic tries to avoid grouping symbols with high
1500      execution frequency scores.  Execution frequency is taken
1501      directly from the basic blocks where every reference is made (see
1502      update_mem_sym_stats_from_stmt), which in turn uses the
1503      profile guided machinery, so if the program is compiled with PGO
1504      enabled, more accurate partitioning decisions will be made.
1505
1506    - Number of references.  Symbols with few references in the code,
1507      are partitioned before symbols with many references.
1508
1509    - NO_ALIAS attributes.  Symbols with any of the NO_ALIAS*
1510      attributes are partitioned after symbols marked MAY_ALIAS.
1511
1512    Once the list is sorted, the partitioning proceeds as follows:
1513
1514    1- For every symbol S in MP_INFO, create a new memory partition MP,
1515       if necessary.  To avoid memory partitions that contain symbols
1516       from non-conflicting alias sets, memory partitions are
1517       associated to the memory tag that holds S in its alias set.  So,
1518       when looking for a memory partition for S, the memory partition
1519       associated with one of the memory tags holding S is chosen.  If
1520       none exists, a new one is created.
1521
1522    2- Add S to memory partition MP.
1523
1524    3- Reduce by 1 the number of VOPS for every memory tag holding S.
1525
1526    4- If the total number of VOPS is less than MAX_ALIASED_VOPS or the
1527       average number of VOPS per statement is less than
1528       AVG_ALIASED_VOPS, stop.  Otherwise, go to the next symbol in the
1529       list.  */
1530
1531 static void
1532 compute_memory_partitions (void)
1533 {
1534   tree tag;
1535   unsigned i;
1536   mem_sym_stats_t mp_p;
1537   VEC(mem_sym_stats_t,heap) *mp_info;
1538   bitmap new_aliases;
1539   VEC(tree,heap) *tags;
1540   struct mem_ref_stats_d *mem_ref_stats;
1541   int prev_max_aliased_vops;
1542
1543   mem_ref_stats = gimple_mem_ref_stats (cfun);
1544   gcc_assert (mem_ref_stats->num_vuses == 0 && mem_ref_stats->num_vdefs == 0);
1545
1546   if (mem_ref_stats->num_mem_stmts == 0)
1547     return;
1548
1549   timevar_push (TV_MEMORY_PARTITIONING);
1550
1551   mp_info = NULL;
1552   tags = NULL;
1553   prev_max_aliased_vops = MAX_ALIASED_VOPS;
1554
1555   /* Since we clearly cannot lower the number of virtual operators
1556      below the total number of memory statements in the function, we
1557      may need to adjust MAX_ALIASED_VOPS beforehand.  */
1558   if (MAX_ALIASED_VOPS < mem_ref_stats->num_mem_stmts)
1559     MAX_ALIASED_VOPS = mem_ref_stats->num_mem_stmts;
1560
1561   /* Update reference stats for all the pointed-to variables and
1562      memory tags.  */
1563   update_reference_counts (mem_ref_stats);
1564
1565   /* Add all the memory symbols to MP_INFO.  */
1566   build_mp_info (mem_ref_stats, &mp_info, &tags);
1567
1568   /* No partitions required if we are below the threshold.  */
1569   if (!need_to_partition_p (mem_ref_stats))
1570     {
1571       if (dump_file)
1572         fprintf (dump_file, "\nMemory partitioning NOT NEEDED for %s\n",
1573                  get_name (current_function_decl));
1574       goto done;
1575     }
1576
1577   /* Sort the MP_INFO array so that symbols that should be partitioned
1578      first are near the top of the list.  */
1579   sort_mp_info (mp_info);
1580
1581   if (dump_file)
1582     {
1583       fprintf (dump_file, "\nMemory partitioning NEEDED for %s\n\n",
1584                get_name (current_function_decl));
1585       fprintf (dump_file, "Memory symbol references before partitioning:\n");
1586       dump_mp_info (dump_file, mp_info);
1587     }
1588
1589   /* Create partitions for variables in MP_INFO until we have enough
1590      to lower the total number of VOPS below MAX_ALIASED_VOPS or if
1591      the average number of VOPS per statement is below
1592      AVG_ALIASED_VOPS.  */
1593   for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
1594     {
1595       tree mpt;
1596
1597       /* If we are below the threshold, stop.  */
1598       if (!need_to_partition_p (mem_ref_stats))
1599         break;
1600
1601       /* SFTs that are marked unpartitionable should not be added to
1602          partitions.  These SFTs are special because they mark the
1603          first SFT into a structure where a pointer is pointing to.
1604          This is needed by the operand scanner to find adjacent
1605          fields.  See add_vars_for_offset for details.  */
1606       if (TREE_CODE (mp_p->var) == STRUCT_FIELD_TAG
1607           && SFT_UNPARTITIONABLE_P (mp_p->var))
1608         continue;
1609
1610       mpt = find_partition_for (mp_p);
1611       estimate_vop_reduction (mem_ref_stats, mp_p, mpt);
1612     }
1613
1614   /* After partitions have been created, rewrite alias sets to use
1615      them instead of the original symbols.  This way, if the alias set
1616      was computed as { a b c d e f }, and the subset { b e f } was
1617      grouped into partition MPT.3, then the new alias set for the tag
1618      will be  { a c d MPT.3 }.
1619      
1620      Note that this is not strictly necessary.  The operand scanner
1621      will always check if a symbol belongs to a partition when adding
1622      virtual operands.  However, by reducing the size of the alias
1623      sets to be scanned, the work needed inside the operand scanner is
1624      significantly reduced.  */
1625   new_aliases = BITMAP_ALLOC (&alias_bitmap_obstack);
1626
1627   for (i = 0; VEC_iterate (tree, tags, i, tag); i++)
1628     {
1629       rewrite_alias_set_for (tag, new_aliases);
1630       bitmap_clear (new_aliases);
1631     }
1632
1633   BITMAP_FREE (new_aliases);
1634
1635   if (dump_file)
1636     {
1637       fprintf (dump_file, "\nMemory symbol references after partitioning:\n");
1638       dump_mp_info (dump_file, mp_info);
1639     }
1640
1641 done:
1642   /* Free allocated memory.  */
1643   VEC_free (mem_sym_stats_t, heap, mp_info);
1644   VEC_free (tree, heap, tags);
1645
1646   MAX_ALIASED_VOPS = prev_max_aliased_vops;
1647
1648   timevar_pop (TV_MEMORY_PARTITIONING);
1649 }
1650
1651
1652 /* Compute may-alias information for every variable referenced in function
1653    FNDECL.
1654
1655    Alias analysis proceeds in 3 main phases:
1656
1657    1- Points-to and escape analysis.
1658
1659    This phase walks the use-def chains in the SSA web looking for three
1660    things:
1661
1662         * Assignments of the form P_i = &VAR
1663         * Assignments of the form P_i = malloc()
1664         * Pointers and ADDR_EXPR that escape the current function.
1665
1666    The concept of 'escaping' is the same one used in the Java world.  When
1667    a pointer or an ADDR_EXPR escapes, it means that it has been exposed
1668    outside of the current function.  So, assignment to global variables,
1669    function arguments and returning a pointer are all escape sites, as are
1670    conversions between pointers and integers.
1671
1672    This is where we are currently limited.  Since not everything is renamed
1673    into SSA, we lose track of escape properties when a pointer is stashed
1674    inside a field in a structure, for instance.  In those cases, we are
1675    assuming that the pointer does escape.
1676
1677    We use escape analysis to determine whether a variable is
1678    call-clobbered.  Simply put, if an ADDR_EXPR escapes, then the variable
1679    is call-clobbered.  If a pointer P_i escapes, then all the variables
1680    pointed-to by P_i (and its memory tag) also escape.
1681
1682    2- Compute flow-sensitive aliases
1683
1684    We have two classes of memory tags.  Memory tags associated with the
1685    pointed-to data type of the pointers in the program.  These tags are
1686    called "symbol memory tag" (SMT).  The other class are those associated
1687    with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that
1688    when adding operands for an INDIRECT_REF *P_i, we will first check
1689    whether P_i has a name tag, if it does we use it, because that will have
1690    more precise aliasing information.  Otherwise, we use the standard symbol
1691    tag.
1692
1693    In this phase, we go through all the pointers we found in points-to
1694    analysis and create alias sets for the name memory tags associated with
1695    each pointer P_i.  If P_i escapes, we mark call-clobbered the variables
1696    it points to and its tag.
1697
1698
1699    3- Compute flow-insensitive aliases
1700
1701    This pass will compare the alias set of every symbol memory tag and
1702    every addressable variable found in the program.  Given a symbol
1703    memory tag SMT and an addressable variable V.  If the alias sets of
1704    SMT and V conflict (as computed by may_alias_p), then V is marked
1705    as an alias tag and added to the alias set of SMT.
1706
1707    For instance, consider the following function:
1708
1709             foo (int i)
1710             {
1711               int *p, a, b;
1712             
1713               if (i > 10)
1714                 p = &a;
1715               else
1716                 p = &b;
1717             
1718               *p = 3;
1719               a = b + 2;
1720               return *p;
1721             }
1722
1723    After aliasing analysis has finished, the symbol memory tag for pointer
1724    'p' will have two aliases, namely variables 'a' and 'b'.  Every time
1725    pointer 'p' is dereferenced, we want to mark the operation as a
1726    potential reference to 'a' and 'b'.
1727
1728             foo (int i)
1729             {
1730               int *p, a, b;
1731
1732               if (i_2 > 10)
1733                 p_4 = &a;
1734               else
1735                 p_6 = &b;
1736               # p_1 = PHI <p_4(1), p_6(2)>;
1737
1738               # a_7 = VDEF <a_3>;
1739               # b_8 = VDEF <b_5>;
1740               *p_1 = 3;
1741
1742               # a_9 = VDEF <a_7>
1743               # VUSE <b_8>
1744               a_9 = b_8 + 2;
1745
1746               # VUSE <a_9>;
1747               # VUSE <b_8>;
1748               return *p_1;
1749             }
1750
1751    In certain cases, the list of may aliases for a pointer may grow too
1752    large.  This may cause an explosion in the number of virtual operands
1753    inserted in the code.  Resulting in increased memory consumption and
1754    compilation time.
1755
1756    When the number of virtual operands needed to represent aliased
1757    loads and stores grows too large (configurable with option --param
1758    max-aliased-vops and --param avg-aliased-vops), alias sets are
1759    grouped to avoid severe compile-time slow downs and memory
1760    consumption. See compute_memory_partitions.  */
1761
1762 unsigned int
1763 compute_may_aliases (void)
1764 {
1765   struct alias_info *ai;
1766
1767   timevar_push (TV_TREE_MAY_ALIAS);
1768   
1769   memset (&alias_stats, 0, sizeof (alias_stats));
1770
1771   /* Initialize aliasing information.  */
1772   ai = init_alias_info ();
1773
1774   /* For each pointer P_i, determine the sets of variables that P_i may
1775      point-to.  For every addressable variable V, determine whether the
1776      address of V escapes the current function, making V call-clobbered
1777      (i.e., whether &V is stored in a global variable or if its passed as a
1778      function call argument).  */
1779   compute_points_to_sets (ai);
1780
1781   /* Collect all pointers and addressable variables, compute alias sets,
1782      create memory tags for pointers and promote variables whose address is
1783      not needed anymore.  */
1784   setup_pointers_and_addressables (ai);
1785
1786   /* Compute type-based flow-insensitive aliasing for all the type
1787      memory tags.  */
1788   compute_flow_insensitive_aliasing (ai);
1789
1790   /* Compute flow-sensitive, points-to based aliasing for all the name
1791      memory tags.  */
1792   compute_flow_sensitive_aliasing (ai);
1793   
1794   /* Compute call clobbering information.  */
1795   compute_call_clobbered (ai);
1796
1797   /* If the program makes no reference to global variables, but it
1798      contains a mixture of pure and non-pure functions, then we need
1799      to create use-def and def-def links between these functions to
1800      avoid invalid transformations on them.  */
1801   maybe_create_global_var ();
1802
1803   /* If the program contains ref-all pointers, finalize may-alias information
1804      for them.  This pass needs to be run after call-clobbering information
1805      has been computed.  */
1806   if (ai->ref_all_symbol_mem_tag)
1807     finalize_ref_all_pointers (ai);
1808
1809   /* Compute memory partitions for every memory variable.  */
1810   compute_memory_partitions ();
1811
1812   /* Remove partitions with no symbols.  Partitions may end up with an
1813      empty MPT_SYMBOLS set if a previous round of alias analysis
1814      needed to partition more symbols.  Since we don't need those
1815      partitions anymore, remove them to free up the space.  */
1816   {
1817     tree mpt;
1818     unsigned i;
1819     VEC(tree,heap) *mpt_table;
1820
1821     mpt_table = gimple_ssa_operands (cfun)->mpt_table;
1822     i = 0;
1823     while (i < VEC_length (tree, mpt_table))
1824       {
1825         mpt = VEC_index (tree, mpt_table, i);
1826         if (MPT_SYMBOLS (mpt) == NULL)
1827           VEC_unordered_remove (tree, mpt_table, i);
1828         else
1829           i++;
1830       }
1831   }
1832
1833   /* Populate all virtual operands and newly promoted register operands.  */
1834   {
1835     block_stmt_iterator bsi;
1836     basic_block bb;
1837     FOR_EACH_BB (bb)
1838       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1839         update_stmt_if_modified (bsi_stmt (bsi));
1840   }
1841
1842   /* Debugging dumps.  */
1843   if (dump_file)
1844     {
1845       dump_mem_ref_stats (dump_file);
1846       dump_alias_info (dump_file);
1847       dump_points_to_info (dump_file);
1848
1849       if (dump_flags & TDF_STATS)
1850         dump_alias_stats (dump_file);
1851
1852       if (dump_flags & TDF_DETAILS)
1853         dump_referenced_vars (dump_file);
1854     }
1855
1856   /* Report strict aliasing violations.  */
1857   strict_aliasing_warning_backend ();
1858
1859   /* Deallocate memory used by aliasing data structures.  */
1860   delete_alias_info (ai);
1861
1862   if (need_ssa_update_p ())
1863     update_ssa (TODO_update_ssa);
1864
1865   timevar_pop (TV_TREE_MAY_ALIAS);
1866   
1867   return 0;
1868 }
1869
1870 /* Data structure used to count the number of dereferences to PTR
1871    inside an expression.  */
1872 struct count_ptr_d
1873 {
1874   tree ptr;
1875   unsigned count;
1876 };
1877
1878
1879 /* Helper for count_uses_and_derefs.  Called by walk_tree to look for
1880    (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA.  */
1881
1882 static tree
1883 count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
1884 {
1885   struct count_ptr_d *count_p = (struct count_ptr_d *) data;
1886
1887   /* Do not walk inside ADDR_EXPR nodes.  In the expression &ptr->fld,
1888      pointer 'ptr' is *not* dereferenced, it is simply used to compute
1889      the address of 'fld' as 'ptr + offsetof(fld)'.  */
1890   if (TREE_CODE (*tp) == ADDR_EXPR)
1891     {
1892       *walk_subtrees = 0;
1893       return NULL_TREE;
1894     }
1895
1896   if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
1897     count_p->count++;
1898
1899   return NULL_TREE;
1900 }
1901
1902
1903 /* Count the number of direct and indirect uses for pointer PTR in
1904    statement STMT.  The number of direct uses is stored in
1905    *NUM_USES_P.  Indirect references are counted separately depending
1906    on whether they are store or load operations.  The counts are
1907    stored in *NUM_STORES_P and *NUM_LOADS_P.  */
1908
1909 void
1910 count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p,
1911                        unsigned *num_loads_p, unsigned *num_stores_p)
1912 {
1913   ssa_op_iter i;
1914   tree use;
1915
1916   *num_uses_p = 0;
1917   *num_loads_p = 0;
1918   *num_stores_p = 0;
1919
1920   /* Find out the total number of uses of PTR in STMT.  */
1921   FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
1922     if (use == ptr)
1923       (*num_uses_p)++;
1924
1925   /* Now count the number of indirect references to PTR.  This is
1926      truly awful, but we don't have much choice.  There are no parent
1927      pointers inside INDIRECT_REFs, so an expression like
1928      '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
1929      find all the indirect and direct uses of x_1 inside.  The only
1930      shortcut we can take is the fact that GIMPLE only allows
1931      INDIRECT_REFs inside the expressions below.  */
1932   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
1933       || (TREE_CODE (stmt) == RETURN_EXPR
1934           && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
1935       || TREE_CODE (stmt) == ASM_EXPR
1936       || TREE_CODE (stmt) == CALL_EXPR)
1937     {
1938       tree lhs, rhs;
1939
1940       if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1941         {
1942           lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1943           rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1944         }
1945       else if (TREE_CODE (stmt) == RETURN_EXPR)
1946         {
1947           tree e = TREE_OPERAND (stmt, 0);
1948           lhs = GIMPLE_STMT_OPERAND (e, 0);
1949           rhs = GIMPLE_STMT_OPERAND (e, 1);
1950         }
1951       else if (TREE_CODE (stmt) == ASM_EXPR)
1952         {
1953           lhs = ASM_OUTPUTS (stmt);
1954           rhs = ASM_INPUTS (stmt);
1955         }
1956       else
1957         {
1958           lhs = NULL_TREE;
1959           rhs = stmt;
1960         }
1961
1962       if (lhs
1963           && (TREE_CODE (lhs) == TREE_LIST
1964               || EXPR_P (lhs)
1965               || GIMPLE_STMT_P (lhs)))
1966         {
1967           struct count_ptr_d count;
1968           count.ptr = ptr;
1969           count.count = 0;
1970           walk_tree (&lhs, count_ptr_derefs, &count, NULL);
1971           *num_stores_p = count.count;
1972         }
1973
1974       if (rhs
1975           && (TREE_CODE (rhs) == TREE_LIST
1976               || EXPR_P (rhs)
1977               || GIMPLE_STMT_P (rhs)))
1978         {
1979           struct count_ptr_d count;
1980           count.ptr = ptr;
1981           count.count = 0;
1982           walk_tree (&rhs, count_ptr_derefs, &count, NULL);
1983           *num_loads_p = count.count;
1984         }
1985     }
1986
1987   gcc_assert (*num_uses_p >= *num_loads_p + *num_stores_p);
1988 }
1989
1990 /* Remove memory references stats for function FN.  */
1991
1992 void
1993 delete_mem_ref_stats (struct function *fn)
1994 {
1995   if (gimple_mem_ref_stats (fn)->mem_sym_stats)
1996     {
1997       free_alloc_pool (mem_sym_stats_pool);
1998       pointer_map_destroy (gimple_mem_ref_stats (fn)->mem_sym_stats);
1999     }
2000   gimple_mem_ref_stats (fn)->mem_sym_stats = NULL;
2001 }
2002
2003
2004 /* Initialize memory reference stats.  */
2005
2006 static void
2007 init_mem_ref_stats (void)
2008 {
2009   struct mem_ref_stats_d *mem_ref_stats = gimple_mem_ref_stats (cfun);
2010
2011   mem_sym_stats_pool = create_alloc_pool ("Mem sym stats",
2012                                           sizeof (struct mem_sym_stats_d),
2013                                           100);
2014   memset (mem_ref_stats, 0, sizeof (struct mem_ref_stats_d));
2015   mem_ref_stats->mem_sym_stats = pointer_map_create ();
2016 }
2017
2018
2019 /* Helper for init_alias_info.  Reset existing aliasing information.  */
2020
2021 static void
2022 reset_alias_info (void)
2023 {
2024   referenced_var_iterator rvi;
2025   tree var;
2026   unsigned i;
2027   bitmap active_nmts, all_nmts;
2028
2029   /* Clear the set of addressable variables.  We do not need to clear
2030      the TREE_ADDRESSABLE bit on every symbol because we are going to
2031      re-compute addressability here.  */
2032   bitmap_clear (gimple_addressable_vars (cfun));
2033
2034   active_nmts = BITMAP_ALLOC (&alias_bitmap_obstack);
2035   all_nmts = BITMAP_ALLOC (&alias_bitmap_obstack);
2036
2037   /* Clear flow-insensitive alias information from each symbol.  */
2038   FOR_EACH_REFERENCED_VAR (var, rvi)
2039     {
2040       if (is_gimple_reg (var))
2041         continue;
2042
2043       if (MTAG_P (var))
2044         MTAG_ALIASES (var) = NULL;
2045
2046       /* Memory partition information will be computed from scratch.  */
2047       if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
2048         MPT_SYMBOLS (var) = NULL;
2049
2050       /* Collect all the name tags to determine if we have any
2051          orphaned that need to be removed from the IL.  A name tag
2052          will be orphaned if it is not associated with any active SSA
2053          name.  */
2054       if (TREE_CODE (var) == NAME_MEMORY_TAG)
2055         bitmap_set_bit (all_nmts, DECL_UID (var));
2056
2057       /* Since we are about to re-discover call-clobbered
2058          variables, clear the call-clobbered flag.  Variables that
2059          are intrinsically call-clobbered (globals, local statics,
2060          etc) will not be marked by the aliasing code, so we can't
2061          remove them from CALL_CLOBBERED_VARS.  
2062
2063          NB: STRUCT_FIELDS are still call clobbered if they are for a
2064          global variable, so we *don't* clear their call clobberedness
2065          just because they are tags, though we will clear it if they
2066          aren't for global variables.  */
2067       if (TREE_CODE (var) == NAME_MEMORY_TAG
2068           || TREE_CODE (var) == SYMBOL_MEMORY_TAG
2069           || TREE_CODE (var) == MEMORY_PARTITION_TAG
2070           || !is_global_var (var))
2071         clear_call_clobbered (var);
2072     }
2073
2074   /* Clear flow-sensitive points-to information from each SSA name.  */
2075   for (i = 1; i < num_ssa_names; i++)
2076     {
2077       tree name = ssa_name (i);
2078
2079       if (!name || !POINTER_TYPE_P (TREE_TYPE (name)))
2080         continue;
2081
2082       if (SSA_NAME_PTR_INFO (name))
2083         {
2084           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
2085
2086           /* Clear all the flags but keep the name tag to
2087              avoid creating new temporaries unnecessarily.  If
2088              this pointer is found to point to a subset or
2089              superset of its former points-to set, then a new
2090              tag will need to be created in create_name_tags.  */
2091           pi->pt_anything = 0;
2092           pi->pt_null = 0;
2093           pi->value_escapes_p = 0;
2094           pi->is_dereferenced = 0;
2095           if (pi->pt_vars)
2096             bitmap_clear (pi->pt_vars);
2097
2098           /* Add NAME's name tag to the set of active tags.  */
2099           if (pi->name_mem_tag)
2100             bitmap_set_bit (active_nmts, DECL_UID (pi->name_mem_tag));
2101         }
2102     }
2103
2104   /* Name memory tags that are no longer associated with an SSA name
2105      are considered stale and should be removed from the IL.  All the
2106      name tags that are in the set ALL_NMTS but not in ACTIVE_NMTS are
2107      considered stale and marked for renaming.  */
2108   bitmap_and_compl_into (all_nmts, active_nmts);
2109   mark_set_for_renaming (all_nmts);
2110
2111   BITMAP_FREE (all_nmts);
2112   BITMAP_FREE (active_nmts);
2113 }
2114
2115
2116 /* Initialize the data structures used for alias analysis.  */
2117
2118 static struct alias_info *
2119 init_alias_info (void)
2120 {
2121   struct alias_info *ai;
2122   referenced_var_iterator rvi;
2123   tree var;
2124
2125   ai = XCNEW (struct alias_info);
2126   ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
2127   sbitmap_zero (ai->ssa_names_visited);
2128   ai->processed_ptrs = VEC_alloc (tree, heap, 50);
2129   ai->written_vars = pointer_set_create ();
2130   ai->dereferenced_ptrs_store = pointer_set_create ();
2131   ai->dereferenced_ptrs_load = pointer_set_create ();
2132
2133   /* Clear out all memory reference stats.  */
2134   init_mem_ref_stats ();
2135
2136   /* If aliases have been computed before, clear existing information.  */
2137   if (gimple_aliases_computed_p (cfun))
2138     reset_alias_info ();
2139   else
2140     {
2141       /* If this is the first time we compute aliasing information,
2142          every non-register symbol will need to be put into SSA form
2143          (the initial SSA form only operates on GIMPLE registers).  */
2144       FOR_EACH_REFERENCED_VAR (var, rvi)
2145         if (!is_gimple_reg (var))
2146           mark_sym_for_renaming (var);
2147     }
2148
2149   /* Next time, we will need to reset alias information.  */
2150   cfun->gimple_df->aliases_computed_p = true;
2151   if (alias_bitmap_obstack.elements != NULL)
2152     bitmap_obstack_release (&alias_bitmap_obstack);    
2153   bitmap_obstack_initialize (&alias_bitmap_obstack);
2154
2155   return ai;
2156 }
2157
2158
2159 /* Deallocate memory used by alias analysis.  */
2160
2161 static void
2162 delete_alias_info (struct alias_info *ai)
2163 {
2164   size_t i;
2165
2166   sbitmap_free (ai->ssa_names_visited);
2167
2168   VEC_free (tree, heap, ai->processed_ptrs);
2169
2170   for (i = 0; i < ai->num_addressable_vars; i++)
2171     free (ai->addressable_vars[i]);
2172   free (ai->addressable_vars);
2173   
2174   for (i = 0; i < ai->num_pointers; i++)
2175     free (ai->pointers[i]);
2176   free (ai->pointers);
2177
2178   pointer_set_destroy (ai->written_vars);
2179   pointer_set_destroy (ai->dereferenced_ptrs_store);
2180   pointer_set_destroy (ai->dereferenced_ptrs_load);
2181   free (ai);
2182
2183   delete_mem_ref_stats (cfun);
2184   delete_points_to_sets ();
2185 }
2186
2187
2188 /* Used for hashing to identify pointer infos with identical
2189    pt_vars bitmaps.  */
2190
2191 static int
2192 eq_ptr_info (const void *p1, const void *p2)
2193 {
2194   const struct ptr_info_def *n1 = (const struct ptr_info_def *) p1;
2195   const struct ptr_info_def *n2 = (const struct ptr_info_def *) p2;
2196   return bitmap_equal_p (n1->pt_vars, n2->pt_vars);
2197 }
2198
2199 static hashval_t
2200 ptr_info_hash (const void *p)
2201 {
2202   const struct ptr_info_def *n = (const struct ptr_info_def *) p;
2203   return bitmap_hash (n->pt_vars);
2204 }
2205
2206
2207 /* Create name tags for all the pointers that have been dereferenced.
2208    We only create a name tag for a pointer P if P is found to point to
2209    a set of variables (so that we can alias them to *P) or if it is
2210    the result of a call to malloc (which means that P cannot point to
2211    anything else nor alias any other variable).
2212
2213    If two pointers P and Q point to the same set of variables, they
2214    are assigned the same name tag.  */
2215
2216 static void
2217 create_name_tags (void)
2218 {
2219   size_t i;
2220   VEC (tree, heap) *with_ptvars = NULL;
2221   tree ptr;
2222   htab_t ptr_hash;
2223
2224   /* Collect the list of pointers with a non-empty points to set.  */
2225   for (i = 1; i < num_ssa_names; i++)
2226     {
2227       tree ptr = ssa_name (i);
2228       struct ptr_info_def *pi;
2229
2230       if (!ptr
2231           || !POINTER_TYPE_P (TREE_TYPE (ptr))
2232           || !SSA_NAME_PTR_INFO (ptr))
2233         continue;
2234
2235       pi = SSA_NAME_PTR_INFO (ptr);
2236
2237       if (pi->pt_anything || !pi->is_dereferenced)
2238         {
2239           /* No name tags for pointers that have not been
2240              dereferenced or point to an arbitrary location.  */
2241           pi->name_mem_tag = NULL_TREE;
2242           continue;
2243         }
2244
2245       /* Set pt_anything on the pointers without pt_vars filled in so
2246          that they are assigned a symbol tag.  */
2247       if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars)) 
2248         VEC_safe_push (tree, heap, with_ptvars, ptr);
2249       else
2250         set_pt_anything (ptr);
2251     }
2252   
2253   /* If we didn't find any pointers with pt_vars set, we're done.  */
2254   if (!with_ptvars)
2255     return;
2256
2257   ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL);
2258
2259   /* Now go through the pointers with pt_vars, and find a name tag
2260      with the same pt_vars as this pointer, or create one if one
2261      doesn't exist.  */
2262   for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++)
2263     {
2264       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2265       tree old_name_tag = pi->name_mem_tag;
2266       struct ptr_info_def **slot;
2267       
2268       /* If PTR points to a set of variables, check if we don't
2269          have another pointer Q with the same points-to set before
2270          creating a tag.  If so, use Q's tag instead of creating a
2271          new one.
2272          
2273          This is important for not creating unnecessary symbols
2274          and also for copy propagation.  If we ever need to
2275          propagate PTR into Q or vice-versa, we would run into
2276          problems if they both had different name tags because
2277          they would have different SSA version numbers (which
2278          would force us to take the name tags in and out of SSA).  */
2279       slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT);
2280       if (*slot)
2281         pi->name_mem_tag = (*slot)->name_mem_tag;
2282       else
2283         {
2284           *slot = pi;
2285
2286           /* If we didn't find a pointer with the same points-to set
2287              as PTR, create a new name tag if needed.  */
2288           if (pi->name_mem_tag == NULL_TREE)
2289             pi->name_mem_tag = get_nmt_for (ptr);
2290         }
2291       
2292       /* If the new name tag computed for PTR is different than
2293          the old name tag that it used to have, then the old tag
2294          needs to be removed from the IL, so we mark it for
2295          renaming.  */
2296       if (old_name_tag && old_name_tag != pi->name_mem_tag)
2297         mark_sym_for_renaming (old_name_tag);
2298
2299       /* Inherit volatility from the pointed-to type.  */
2300       TREE_THIS_VOLATILE (pi->name_mem_tag)
2301         |= TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
2302       
2303       /* Mark the new name tag for renaming.  */
2304       mark_sym_for_renaming (pi->name_mem_tag);
2305     }
2306
2307   htab_delete (ptr_hash);
2308
2309   VEC_free (tree, heap, with_ptvars);
2310 }
2311
2312
2313 /* Union the alias set SET into the may-aliases for TAG.  */
2314
2315 static void
2316 union_alias_set_into (tree tag, bitmap set)
2317 {
2318   bitmap ma = MTAG_ALIASES (tag);
2319   
2320   if (bitmap_empty_p (set))
2321     return;
2322   
2323   if (!ma)
2324     ma = MTAG_ALIASES (tag) = BITMAP_ALLOC (&alias_bitmap_obstack);
2325   bitmap_ior_into (ma, set);
2326 }
2327
2328
2329 /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
2330    the name memory tag (NMT) associated with P_i.  If P_i escapes, then its
2331    name tag and the variables it points-to are call-clobbered.  Finally, if
2332    P_i escapes and we could not determine where it points to, then all the
2333    variables in the same alias set as *P_i are marked call-clobbered.  This
2334    is necessary because we must assume that P_i may take the address of any
2335    variable in the same alias set.  */
2336
2337 static void
2338 compute_flow_sensitive_aliasing (struct alias_info *ai)
2339 {
2340   size_t i;
2341   tree ptr;
2342   
2343   timevar_push (TV_FLOW_SENSITIVE);
2344   set_used_smts ();
2345   
2346   for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
2347     {
2348       if (!find_what_p_points_to (ptr))
2349         set_pt_anything (ptr);
2350     }
2351
2352   create_name_tags ();
2353
2354   for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
2355     {
2356       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2357       tree tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
2358
2359       /* Set up aliasing information for PTR's name memory tag (if it has
2360          one).  Note that only pointers that have been dereferenced will
2361          have a name memory tag.  */
2362       if (pi->name_mem_tag && pi->pt_vars)
2363         {
2364           if (!bitmap_empty_p (pi->pt_vars))
2365             {
2366               union_alias_set_into (pi->name_mem_tag, pi->pt_vars);
2367               union_alias_set_into (tag, pi->pt_vars);
2368               bitmap_clear_bit (MTAG_ALIASES (tag), DECL_UID (tag));
2369             
2370               /* It may be the case that this the tag uid was the only
2371                  bit we had set in the aliases list, and in this case,
2372                  we don't want to keep an empty bitmap, as this
2373                  asserts in tree-ssa-operands.c .  */
2374               if (bitmap_empty_p (MTAG_ALIASES (tag)))
2375                 BITMAP_FREE (MTAG_ALIASES (tag));
2376             }
2377         }
2378     }
2379   timevar_pop (TV_FLOW_SENSITIVE);
2380 }
2381
2382
2383 /* Return TRUE if at least one symbol in TAG2's alias set is also
2384    present in TAG1's alias set.  */
2385
2386 static bool
2387 have_common_aliases_p (bitmap tag1aliases, bitmap tag2aliases)
2388 {
2389
2390   /* This is the old behavior of have_common_aliases_p, which is to
2391      return false if both sets are empty, or one set is and the other
2392      isn't.  */
2393      if ((tag1aliases == NULL && tag2aliases != NULL)
2394       || (tag2aliases == NULL && tag1aliases != NULL)
2395       || (tag1aliases == NULL && tag2aliases == NULL))
2396     return false;
2397
2398   return bitmap_intersect_p (tag1aliases, tag2aliases);
2399 }
2400
2401 /* Compute type-based alias sets.  Traverse all the pointers and
2402    addressable variables found in setup_pointers_and_addressables.
2403    
2404    For every pointer P in AI->POINTERS and addressable variable V in
2405    AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's symbol
2406    memory tag (SMT) if their alias sets conflict.  V is then marked as
2407    an aliased symbol so that the operand scanner knows that statements
2408    containing V have aliased operands.  */
2409
2410 static void
2411 compute_flow_insensitive_aliasing (struct alias_info *ai)
2412 {
2413   size_t i;
2414
2415   timevar_push (TV_FLOW_INSENSITIVE);
2416   /* For every pointer P, determine which addressable variables may alias
2417      with P's symbol memory tag.  */
2418   for (i = 0; i < ai->num_pointers; i++)
2419     {
2420       size_t j;
2421       struct alias_map_d *p_map = ai->pointers[i];
2422       tree tag = symbol_mem_tag (p_map->var);
2423       tree var;
2424
2425       /* Call-clobbering information is not finalized yet at this point.  */
2426       if (PTR_IS_REF_ALL (p_map->var))
2427         continue;
2428
2429       for (j = 0; j < ai->num_addressable_vars; j++)
2430         {
2431           struct alias_map_d *v_map;
2432           var_ann_t v_ann;
2433           bool tag_stored_p, var_stored_p;
2434           
2435           v_map = ai->addressable_vars[j];
2436           var = v_map->var;
2437           v_ann = var_ann (var);
2438
2439           /* Skip memory tags and variables that have never been
2440              written to.  We also need to check if the variables are
2441              call-clobbered because they may be overwritten by
2442              function calls.  */
2443           tag_stored_p = pointer_set_contains (ai->written_vars, tag)
2444                          || is_call_clobbered (tag);
2445           var_stored_p = pointer_set_contains (ai->written_vars, var)
2446                          || is_call_clobbered (var);
2447           if (!tag_stored_p && !var_stored_p)
2448             continue;
2449              
2450           if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false))
2451             {
2452               /* We should never have a var with subvars here, because
2453                  they shouldn't get into the set of addressable vars */
2454               gcc_assert (!var_can_have_subvars (var)
2455                           || get_subvars_for_var (var) == NULL);
2456
2457               /* Add VAR to TAG's may-aliases set.  */
2458               add_may_alias (tag, var);
2459             }
2460         }
2461     }
2462
2463   /* Since this analysis is based exclusively on symbols, it fails to
2464      handle cases where two pointers P and Q have different memory
2465      tags with conflicting alias set numbers but no aliased symbols in
2466      common.
2467
2468      For example, suppose that we have two memory tags SMT.1 and SMT.2
2469      such that
2470      
2471                 may-aliases (SMT.1) = { a }
2472                 may-aliases (SMT.2) = { b }
2473
2474      and the alias set number of SMT.1 conflicts with that of SMT.2.
2475      Since they don't have symbols in common, loads and stores from
2476      SMT.1 and SMT.2 will seem independent of each other, which will
2477      lead to the optimizers making invalid transformations (see
2478      testsuite/gcc.c-torture/execute/pr15262-[12].c).
2479
2480      To avoid this problem, we do a final traversal of AI->POINTERS
2481      looking for pairs of pointers that have no aliased symbols in
2482      common and yet have conflicting alias set numbers.  */
2483   for (i = 0; i < ai->num_pointers; i++)
2484     {
2485       size_t j;
2486       struct alias_map_d *p_map1 = ai->pointers[i];
2487       tree tag1 = symbol_mem_tag (p_map1->var);
2488       bitmap may_aliases1 = MTAG_ALIASES (tag1);
2489
2490       if (PTR_IS_REF_ALL (p_map1->var))
2491         continue;
2492
2493       for (j = i + 1; j < ai->num_pointers; j++)
2494         {
2495           struct alias_map_d *p_map2 = ai->pointers[j];
2496           tree tag2 = symbol_mem_tag (p_map2->var);
2497           bitmap may_aliases2 = may_aliases (tag2);
2498
2499           if (PTR_IS_REF_ALL (p_map2->var))
2500             continue;
2501
2502           /* If the pointers may not point to each other, do nothing.  */
2503           if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
2504             continue;
2505
2506           /* The two pointers may alias each other.  If they already have
2507              symbols in common, do nothing.  */
2508           if (have_common_aliases_p (may_aliases1, may_aliases2))
2509             continue;
2510
2511           if (may_aliases2 && !bitmap_empty_p (may_aliases2))
2512             {
2513               union_alias_set_into (tag1, may_aliases2);
2514             }
2515           else
2516             {
2517               /* Since TAG2 does not have any aliases of its own, add
2518                  TAG2 itself to the alias set of TAG1.  */
2519               add_may_alias (tag1, tag2);
2520             }
2521         }
2522
2523     }
2524   timevar_pop (TV_FLOW_INSENSITIVE);
2525 }
2526
2527
2528 /* Finalize may-alias information for ref-all pointers.  Traverse all
2529    the addressable variables found in setup_pointers_and_addressables.
2530
2531    If flow-sensitive alias analysis has attached a name memory tag to
2532    a ref-all pointer, we will use it for the dereferences because that
2533    will have more precise aliasing information.  But if there is no
2534    name tag, we will use a special symbol tag that aliases all the
2535    call-clobbered addressable variables.  */
2536
2537 static void
2538 finalize_ref_all_pointers (struct alias_info *ai)
2539 {
2540   size_t i;
2541
2542   /* First add the real call-clobbered variables.  */
2543   for (i = 0; i < ai->num_addressable_vars; i++)
2544     {
2545       tree var = ai->addressable_vars[i]->var;
2546       if (is_call_clobbered (var))
2547         add_may_alias (ai->ref_all_symbol_mem_tag, var);
2548     }
2549
2550   /* Then add the call-clobbered pointer memory tags.  See
2551      compute_flow_insensitive_aliasing for the rationale.  */
2552   for (i = 0; i < ai->num_pointers; i++)
2553     {
2554       tree ptr = ai->pointers[i]->var, tag;
2555       /* Avoid adding to self and clean up.  */
2556       if (PTR_IS_REF_ALL (ptr))
2557         {
2558           struct ptr_info_def *pi = get_ptr_info (ptr);
2559           if (pi->is_dereferenced)
2560             pi->pt_anything = 0;
2561           continue;
2562         }
2563       tag = symbol_mem_tag (ptr);
2564       if (is_call_clobbered (tag))
2565         add_may_alias (ai->ref_all_symbol_mem_tag, tag);
2566     }
2567
2568 }
2569
2570
2571 /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS.  */
2572
2573 static void
2574 create_alias_map_for (tree var, struct alias_info *ai)
2575 {
2576   struct alias_map_d *alias_map;
2577   alias_map = XCNEW (struct alias_map_d);
2578   alias_map->var = var;
2579   alias_map->set = get_alias_set (var);
2580   ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
2581 }
2582
2583
2584 /* Create memory tags for all the dereferenced pointers and build the
2585    ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias
2586    sets.  Based on the address escape and points-to information collected
2587    earlier, this pass will also clear the TREE_ADDRESSABLE flag from those
2588    variables whose address is not needed anymore.  */
2589
2590 static void
2591 setup_pointers_and_addressables (struct alias_info *ai)
2592 {
2593   size_t num_addressable_vars, num_pointers;
2594   referenced_var_iterator rvi;
2595   tree var;
2596   VEC (tree, heap) *varvec = NULL;
2597   safe_referenced_var_iterator srvi;
2598
2599   /* Size up the arrays ADDRESSABLE_VARS and POINTERS.  */
2600   num_addressable_vars = num_pointers = 0;
2601   
2602   FOR_EACH_REFERENCED_VAR (var, rvi)
2603     {
2604       if (may_be_aliased (var))
2605         num_addressable_vars++;
2606
2607       if (POINTER_TYPE_P (TREE_TYPE (var)))
2608         {
2609           /* Since we don't keep track of volatile variables, assume that
2610              these pointers are used in indirect store operations.  */
2611           if (TREE_THIS_VOLATILE (var))
2612             pointer_set_insert (ai->dereferenced_ptrs_store, var);
2613
2614           num_pointers++;
2615         }
2616     }
2617
2618   /* Create ADDRESSABLE_VARS and POINTERS.  Note that these arrays are
2619      always going to be slightly bigger than we actually need them
2620      because some TREE_ADDRESSABLE variables will be marked
2621      non-addressable below and only pointers with unique symbol tags are
2622      going to be added to POINTERS.  */
2623   ai->addressable_vars = XCNEWVEC (struct alias_map_d *, num_addressable_vars);
2624   ai->pointers = XCNEWVEC (struct alias_map_d *, num_pointers);
2625   ai->num_addressable_vars = 0;
2626   ai->num_pointers = 0;
2627
2628   FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi)
2629     {
2630       subvar_t svars;
2631
2632       /* Name memory tags already have flow-sensitive aliasing
2633          information, so they need not be processed by
2634          compute_flow_insensitive_aliasing.  Similarly, symbol memory
2635          tags are already accounted for when we process their
2636          associated pointer. 
2637       
2638          Structure fields, on the other hand, have to have some of this
2639          information processed for them, but it's pointless to mark them
2640          non-addressable (since they are fake variables anyway).  */
2641       if (MTAG_P (var) && TREE_CODE (var) != STRUCT_FIELD_TAG)
2642         continue;
2643
2644       /* Remove the ADDRESSABLE flag from every addressable variable whose
2645          address is not needed anymore.  This is caused by the propagation
2646          of ADDR_EXPR constants into INDIRECT_REF expressions and the
2647          removal of dead pointer assignments done by the early scalar
2648          cleanup passes.  */
2649       if (TREE_ADDRESSABLE (var))
2650         {
2651           if (!bitmap_bit_p (gimple_addressable_vars (cfun), DECL_UID (var))
2652               && TREE_CODE (var) != RESULT_DECL
2653               && !is_global_var (var))
2654             {
2655               bool okay_to_mark = true;
2656
2657               /* Since VAR is now a regular GIMPLE register, we will need
2658                  to rename VAR into SSA afterwards.  */
2659               mark_sym_for_renaming (var);
2660
2661               /* If VAR can have sub-variables, and any of its
2662                  sub-variables has its address taken, then we cannot
2663                  remove the addressable flag from VAR.  */
2664               if (var_can_have_subvars (var)
2665                   && (svars = get_subvars_for_var (var)))
2666                 {
2667                   unsigned int i;
2668                   tree subvar;
2669
2670                   for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
2671                     {         
2672                       if (bitmap_bit_p (gimple_addressable_vars (cfun),
2673                                         DECL_UID (subvar)))
2674                         okay_to_mark = false;
2675                       mark_sym_for_renaming (subvar);
2676                     }
2677                 }
2678
2679               /* The address of VAR is not needed, remove the
2680                  addressable bit, so that it can be optimized as a
2681                  regular variable.  */
2682               if (okay_to_mark)
2683                 {
2684                   /* The memory partition holding VAR will no longer
2685                      contain VAR, and statements referencing it will need
2686                      to be updated.  */
2687                   if (memory_partition (var))
2688                     mark_sym_for_renaming (memory_partition (var));
2689
2690                   mark_non_addressable (var);
2691                 }
2692             }
2693         }
2694
2695       /* Global variables and addressable locals may be aliased.  Create an
2696          entry in ADDRESSABLE_VARS for VAR.  */
2697       if (may_be_aliased (var))
2698         {
2699           if (!var_can_have_subvars (var)
2700               || get_subvars_for_var (var) == NULL)
2701             create_alias_map_for (var, ai);
2702
2703           mark_sym_for_renaming (var);
2704         }
2705
2706       /* Add pointer variables that have been dereferenced to the POINTERS
2707          array and create a symbol memory tag for them.  */
2708       if (POINTER_TYPE_P (TREE_TYPE (var)))
2709         {
2710           if ((pointer_set_contains (ai->dereferenced_ptrs_store, var)
2711                || pointer_set_contains (ai->dereferenced_ptrs_load, var)))
2712             {
2713               tree tag, old_tag;
2714               var_ann_t t_ann;
2715
2716               /* If pointer VAR still doesn't have a memory tag
2717                  associated with it, create it now or re-use an
2718                  existing one.  */
2719               tag = get_smt_for (var, ai);
2720               t_ann = var_ann (tag);
2721
2722               /* The symbol tag will need to be renamed into SSA
2723                  afterwards. Note that we cannot do this inside
2724                  get_smt_for because aliasing may run multiple times
2725                  and we only create symbol tags the first time.  */
2726               mark_sym_for_renaming (tag);
2727
2728               /* Similarly, if pointer VAR used to have another type
2729                  tag, we will need to process it in the renamer to
2730                  remove the stale virtual operands.  */
2731               old_tag = symbol_mem_tag (var);
2732               if (old_tag)
2733                 mark_sym_for_renaming (old_tag);
2734
2735               /* Associate the tag with pointer VAR.  */
2736               set_symbol_mem_tag (var, tag);
2737
2738               /* If pointer VAR has been used in a store operation,
2739                  then its memory tag must be marked as written-to.  */
2740               if (pointer_set_contains (ai->dereferenced_ptrs_store, var))
2741                 pointer_set_insert (ai->written_vars, tag);
2742             }
2743           else
2744             {
2745               /* The pointer has not been dereferenced.  If it had a
2746                  symbol memory tag, remove it and mark the old tag for
2747                  renaming to remove it out of the IL.  */
2748               tree tag = symbol_mem_tag (var);
2749               if (tag)
2750                 {
2751                   mark_sym_for_renaming (tag);
2752                   set_symbol_mem_tag (var, NULL_TREE);
2753                 }
2754             }
2755         }
2756     }
2757
2758   VEC_free (tree, heap, varvec);
2759 }
2760
2761
2762 /* Determine whether to use .GLOBAL_VAR to model call clobbering
2763    semantics.  If the function makes no references to global
2764    variables and contains at least one call to a non-pure function,
2765    then we need to mark the side-effects of the call using .GLOBAL_VAR
2766    to represent all possible global memory referenced by the callee.  */
2767
2768 static void
2769 maybe_create_global_var (void)
2770 {
2771   /* No need to create it, if we have one already.  */
2772   if (gimple_global_var (cfun) == NULL_TREE)
2773     {
2774       struct mem_ref_stats_d *stats = gimple_mem_ref_stats (cfun);
2775
2776       /* Create .GLOBAL_VAR if there are no call-clobbered
2777          variables and the program contains a mixture of pure/const
2778          and regular function calls.  This is to avoid the problem
2779          described in PR 20115:
2780
2781               int X;
2782               int func_pure (void) { return X; }
2783               int func_non_pure (int a) { X += a; }
2784               int foo ()
2785               {
2786                 int a = func_pure ();
2787                 func_non_pure (a);
2788                 a = func_pure ();
2789                 return a;
2790               }
2791
2792          Since foo() has no call-clobbered variables, there is
2793          no relationship between the calls to func_pure and
2794          func_non_pure.  Since func_pure has no side-effects, value
2795          numbering optimizations elide the second call to func_pure.
2796          So, if we have some pure/const and some regular calls in the
2797          program we create .GLOBAL_VAR to avoid missing these
2798          relations.  */
2799       if (bitmap_empty_p (gimple_call_clobbered_vars (cfun))
2800           && stats->num_call_sites > 0
2801           && stats->num_pure_const_call_sites > 0
2802           && stats->num_call_sites > stats->num_pure_const_call_sites)
2803         create_global_var ();
2804     }
2805 }
2806
2807
2808 /* Return TRUE if pointer PTR may point to variable VAR.
2809    
2810    MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR
2811         This is needed because when checking for type conflicts we are
2812         interested in the alias set of the memory location pointed-to by
2813         PTR.  The alias set of PTR itself is irrelevant.
2814    
2815    VAR_ALIAS_SET is the alias set for VAR.  */
2816
2817 static bool
2818 may_alias_p (tree ptr, alias_set_type mem_alias_set,
2819              tree var, alias_set_type var_alias_set,
2820              bool alias_set_only)
2821 {
2822   tree mem;
2823
2824   alias_stats.alias_queries++;
2825   alias_stats.simple_queries++;
2826
2827   /* By convention, a variable cannot alias itself.  */
2828   mem = symbol_mem_tag (ptr);
2829   if (mem == var)
2830     {
2831       alias_stats.alias_noalias++;
2832       alias_stats.simple_resolved++;
2833       return false;
2834     }
2835
2836   /* If -fargument-noalias-global is > 2, pointer arguments may
2837      not point to anything else.  */
2838   if (flag_argument_noalias > 2 && TREE_CODE (ptr) == PARM_DECL)
2839     {
2840       alias_stats.alias_noalias++;
2841       alias_stats.simple_resolved++;
2842       return false;
2843     }
2844
2845   /* If -fargument-noalias-global is > 1, pointer arguments may
2846      not point to global variables.  */
2847   if (flag_argument_noalias > 1 && is_global_var (var)
2848       && TREE_CODE (ptr) == PARM_DECL)
2849     {
2850       alias_stats.alias_noalias++;
2851       alias_stats.simple_resolved++;
2852       return false;
2853     }
2854
2855   /* If either MEM or VAR is a read-only global and the other one
2856      isn't, then PTR cannot point to VAR.  */
2857   if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var))
2858       || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem)))
2859     {
2860       alias_stats.alias_noalias++;
2861       alias_stats.simple_resolved++;
2862       return false;
2863     }
2864
2865   gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG);
2866
2867   if (!DECL_NO_TBAA_P (ptr))
2868     {
2869       alias_stats.tbaa_queries++;
2870
2871       /* If the alias sets don't conflict then MEM cannot alias VAR.  */
2872       if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
2873         {
2874           alias_stats.alias_noalias++;
2875           alias_stats.tbaa_resolved++;
2876           return false;
2877         }
2878
2879       /* If VAR is a record or union type, PTR cannot point into VAR
2880          unless there is some explicit address operation in the
2881          program that can reference a field of the type pointed-to by
2882          PTR.  This also assumes that the types of both VAR and PTR
2883          are contained within the compilation unit, and that there is
2884          no fancy addressing arithmetic associated with any of the
2885          types involved.  */
2886       if (mem_alias_set != 0 && var_alias_set != 0)
2887         {
2888           tree ptr_type = TREE_TYPE (ptr);
2889           tree var_type = TREE_TYPE (var);
2890       
2891           /* The star count is -1 if the type at the end of the
2892              pointer_to chain is not a record or union type. */ 
2893           if ((!alias_set_only) && 
2894               ipa_type_escape_star_count_of_interesting_type (var_type) >= 0)
2895             {
2896               int ptr_star_count = 0;
2897           
2898               /* ipa_type_escape_star_count_of_interesting_type is a
2899                  little too restrictive for the pointer type, need to
2900                  allow pointers to primitive types as long as those
2901                  types cannot be pointers to everything.  */
2902               while (POINTER_TYPE_P (ptr_type))
2903                 {
2904                   /* Strip the *s off.  */ 
2905                   ptr_type = TREE_TYPE (ptr_type);
2906                   ptr_star_count++;
2907                 }
2908           
2909               /* There does not appear to be a better test to see if
2910                  the pointer type was one of the pointer to everything
2911                  types.  */
2912               if (ptr_star_count > 0)
2913                 {
2914                   alias_stats.structnoaddress_queries++;
2915                   if (ipa_type_escape_field_does_not_clobber_p (var_type, 
2916                                                                 TREE_TYPE (ptr)))
2917                     {
2918                       alias_stats.structnoaddress_resolved++;
2919                       alias_stats.alias_noalias++;
2920                       return false;
2921                     }
2922                 }
2923               else if (ptr_star_count == 0)
2924                 {
2925                   /* If PTR_TYPE was not really a pointer to type, it cannot 
2926                      alias.  */ 
2927                   alias_stats.structnoaddress_queries++;
2928                   alias_stats.structnoaddress_resolved++;
2929                   alias_stats.alias_noalias++;
2930                   return false;
2931                 }
2932             }
2933         }
2934     }
2935
2936   alias_stats.alias_mayalias++;
2937   return true;
2938 }
2939
2940
2941 /* Add ALIAS to the set of variables that may alias VAR.  */
2942
2943 static void
2944 add_may_alias (tree var, tree alias)
2945 {
2946   /* Don't allow self-referential aliases.  */
2947   gcc_assert (var != alias);
2948
2949   /* ALIAS must be addressable if it's being added to an alias set.  */
2950 #if 1
2951   TREE_ADDRESSABLE (alias) = 1;
2952 #else
2953   gcc_assert (may_be_aliased (alias));
2954 #endif
2955
2956   /* VAR must be a symbol or a name tag.  */
2957   gcc_assert (TREE_CODE (var) == SYMBOL_MEMORY_TAG
2958               || TREE_CODE (var) == NAME_MEMORY_TAG);
2959
2960   if (MTAG_ALIASES (var) == NULL)
2961     MTAG_ALIASES (var) = BITMAP_ALLOC (&alias_bitmap_obstack);
2962   
2963   bitmap_set_bit (MTAG_ALIASES (var), DECL_UID (alias));
2964 }
2965
2966
2967 /* Mark pointer PTR as pointing to an arbitrary memory location.  */
2968
2969 static void
2970 set_pt_anything (tree ptr)
2971 {
2972   struct ptr_info_def *pi = get_ptr_info (ptr);
2973
2974   pi->pt_anything = 1;
2975   pi->pt_vars = NULL;
2976
2977   /* The pointer used to have a name tag, but we now found it pointing
2978      to an arbitrary location.  The name tag needs to be renamed and
2979      disassociated from PTR.  */
2980   if (pi->name_mem_tag)
2981     {
2982       mark_sym_for_renaming (pi->name_mem_tag);
2983       pi->name_mem_tag = NULL_TREE;
2984     }
2985 }
2986
2987
2988 /* Return true if STMT is an "escape" site from the current function.  Escape
2989    sites those statements which might expose the address of a variable
2990    outside the current function.  STMT is an escape site iff:
2991
2992         1- STMT is a function call, or
2993         2- STMT is an __asm__ expression, or
2994         3- STMT is an assignment to a non-local variable, or
2995         4- STMT is a return statement.
2996
2997    Return the type of escape site found, if we found one, or NO_ESCAPE
2998    if none.  */
2999
3000 enum escape_type
3001 is_escape_site (tree stmt)
3002 {
3003   tree call = get_call_expr_in (stmt);
3004   if (call != NULL_TREE)
3005     {
3006       if (!TREE_SIDE_EFFECTS (call))
3007         return ESCAPE_TO_PURE_CONST;
3008
3009       return ESCAPE_TO_CALL;
3010     }
3011   else if (TREE_CODE (stmt) == ASM_EXPR)
3012     return ESCAPE_TO_ASM;
3013   else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
3014     {
3015       tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3016
3017       /* Get to the base of _REF nodes.  */
3018       if (TREE_CODE (lhs) != SSA_NAME)
3019         lhs = get_base_address (lhs);
3020
3021       /* If we couldn't recognize the LHS of the assignment, assume that it
3022          is a non-local store.  */
3023       if (lhs == NULL_TREE)
3024         return ESCAPE_UNKNOWN;
3025
3026       if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == NOP_EXPR
3027           || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == CONVERT_EXPR
3028           || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR)
3029         {
3030           tree from
3031             = TREE_TYPE (TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 0));
3032           tree to = TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 1));
3033
3034           /* If the RHS is a conversion between a pointer and an integer, the
3035              pointer escapes since we can't track the integer.  */
3036           if (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to))
3037             return ESCAPE_BAD_CAST;
3038
3039           /* Same if the RHS is a conversion between a regular pointer and a
3040              ref-all pointer since we can't track the SMT of the former.  */
3041           if (POINTER_TYPE_P (from) && !TYPE_REF_CAN_ALIAS_ALL (from)
3042               && POINTER_TYPE_P (to) && TYPE_REF_CAN_ALIAS_ALL (to))
3043             return ESCAPE_BAD_CAST;
3044         }
3045
3046       /* If the LHS is an SSA name, it can't possibly represent a non-local
3047          memory store.  */
3048       if (TREE_CODE (lhs) == SSA_NAME)
3049         return NO_ESCAPE;
3050
3051       /* FIXME: LHS is not an SSA_NAME.  Even if it's an assignment to a
3052          local variables we cannot be sure if it will escape, because we
3053          don't have information about objects not in SSA form.  Need to
3054          implement something along the lines of
3055
3056          J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P.
3057          Midkiff, ``Escape analysis for java,'' in Proceedings of the
3058          Conference on Object-Oriented Programming Systems, Languages, and
3059          Applications (OOPSLA), pp. 1-19, 1999.  */
3060       return ESCAPE_STORED_IN_GLOBAL;
3061     }
3062   else if (TREE_CODE (stmt) == RETURN_EXPR)
3063     return ESCAPE_TO_RETURN;
3064
3065   return NO_ESCAPE;
3066 }
3067
3068 /* Create a new memory tag of type TYPE.
3069    Does NOT push it into the current binding.  */
3070
3071 tree
3072 create_tag_raw (enum tree_code code, tree type, const char *prefix)
3073 {
3074   tree tmp_var;
3075
3076   tmp_var = build_decl (code, create_tmp_var_name (prefix), type);
3077
3078   /* Make the variable writable.  */
3079   TREE_READONLY (tmp_var) = 0;
3080
3081   /* It doesn't start out global.  */
3082   MTAG_GLOBAL (tmp_var) = 0;
3083   TREE_STATIC (tmp_var) = 0;
3084   TREE_USED (tmp_var) = 1;
3085
3086   return tmp_var;
3087 }
3088
3089 /* Create a new memory tag of type TYPE.  If IS_TYPE_TAG is true, the tag
3090    is considered to represent all the pointers whose pointed-to types are
3091    in the same alias set class.  Otherwise, the tag represents a single
3092    SSA_NAME pointer variable.  */
3093
3094 static tree
3095 create_memory_tag (tree type, bool is_type_tag)
3096 {
3097   tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG,
3098                              type, (is_type_tag) ? "SMT" : "NMT");
3099
3100   /* By default, memory tags are local variables.  Alias analysis will
3101      determine whether they should be considered globals.  */
3102   DECL_CONTEXT (tag) = current_function_decl;
3103
3104   /* Memory tags are by definition addressable.  */
3105   TREE_ADDRESSABLE (tag) = 1;
3106
3107   set_symbol_mem_tag (tag, NULL_TREE);
3108
3109   /* Add the tag to the symbol table.  */
3110   add_referenced_var (tag);
3111
3112   return tag;
3113 }
3114
3115
3116 /* Create a name memory tag to represent a specific SSA_NAME pointer P_i.
3117    This is used if P_i has been found to point to a specific set of
3118    variables or to a non-aliased memory location like the address returned
3119    by malloc functions.  */
3120
3121 static tree
3122 get_nmt_for (tree ptr)
3123 {
3124   struct ptr_info_def *pi = get_ptr_info (ptr);
3125   tree tag = pi->name_mem_tag;
3126
3127   if (tag == NULL_TREE)
3128     tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false);
3129   return tag;
3130 }
3131
3132
3133 /* Return the symbol memory tag associated to pointer PTR.  A memory
3134    tag is an artificial variable that represents the memory location
3135    pointed-to by PTR.  It is used to model the effects of pointer
3136    de-references on addressable variables.
3137    
3138    AI points to the data gathered during alias analysis.  This
3139    function populates the array AI->POINTERS.  */
3140
3141 static tree
3142 get_smt_for (tree ptr, struct alias_info *ai)
3143 {
3144   size_t i;
3145   tree tag;
3146   tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
3147   alias_set_type tag_set = get_alias_set (tag_type);
3148
3149   /* We use a unique memory tag for all the ref-all pointers.  */
3150   if (PTR_IS_REF_ALL (ptr))
3151     {
3152       if (!ai->ref_all_symbol_mem_tag)
3153         ai->ref_all_symbol_mem_tag = create_memory_tag (void_type_node, true);
3154       return ai->ref_all_symbol_mem_tag;
3155     }
3156
3157   /* To avoid creating unnecessary memory tags, only create one memory tag
3158      per alias set class.  Note that it may be tempting to group
3159      memory tags based on conflicting alias sets instead of
3160      equivalence.  That would be wrong because alias sets are not
3161      necessarily transitive (as demonstrated by the libstdc++ test
3162      23_containers/vector/cons/4.cc).  Given three alias sets A, B, C
3163      such that conflicts (A, B) == true and conflicts (A, C) == true,
3164      it does not necessarily follow that conflicts (B, C) == true.  */
3165   for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
3166     {
3167       struct alias_map_d *curr = ai->pointers[i];
3168       tree curr_tag = symbol_mem_tag (curr->var);
3169       if (tag_set == curr->set)
3170         {
3171           tag = curr_tag;
3172           break;
3173         }
3174     }
3175
3176   /* If VAR cannot alias with any of the existing memory tags, create a new
3177      tag for PTR and add it to the POINTERS array.  */
3178   if (tag == NULL_TREE)
3179     {
3180       struct alias_map_d *alias_map;
3181
3182       /* If PTR did not have a symbol tag already, create a new SMT.*
3183          artificial variable representing the memory location
3184          pointed-to by PTR.  */
3185       tag = symbol_mem_tag (ptr);
3186       if (tag == NULL_TREE)
3187         tag = create_memory_tag (tag_type, true);
3188
3189       /* Add PTR to the POINTERS array.  Note that we are not interested in
3190          PTR's alias set.  Instead, we cache the alias set for the memory that
3191          PTR points to.  */
3192       alias_map = XCNEW (struct alias_map_d);
3193       alias_map->var = ptr;
3194       alias_map->set = tag_set;
3195       ai->pointers[ai->num_pointers++] = alias_map;
3196     }
3197
3198   /* If the pointed-to type is volatile, so is the tag.  */
3199   TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type);
3200
3201   /* Make sure that the symbol tag has the same alias set as the
3202      pointed-to type.  */
3203   gcc_assert (tag_set == get_alias_set (tag));
3204
3205   return tag;
3206 }
3207
3208
3209 /* Create GLOBAL_VAR, an artificial global variable to act as a
3210    representative of all the variables that may be clobbered by function
3211    calls.  */
3212
3213 static void
3214 create_global_var (void)
3215 {
3216   tree global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
3217                                 void_type_node);
3218   DECL_ARTIFICIAL (global_var) = 1;
3219   TREE_READONLY (global_var) = 0;
3220   DECL_EXTERNAL (global_var) = 1;
3221   TREE_STATIC (global_var) = 1;
3222   TREE_USED (global_var) = 1;
3223   DECL_CONTEXT (global_var) = NULL_TREE;
3224   TREE_THIS_VOLATILE (global_var) = 0;
3225   TREE_ADDRESSABLE (global_var) = 0;
3226
3227   create_var_ann (global_var);
3228   mark_call_clobbered (global_var, ESCAPE_UNKNOWN);
3229   add_referenced_var (global_var);
3230   mark_sym_for_renaming (global_var);
3231   cfun->gimple_df->global_var = global_var;
3232 }
3233
3234
3235 /* Dump alias statistics on FILE.  */
3236
3237 static void 
3238 dump_alias_stats (FILE *file)
3239 {
3240   const char *funcname
3241     = lang_hooks.decl_printable_name (current_function_decl, 2);
3242   fprintf (file, "\nAlias statistics for %s\n\n", funcname);
3243   fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries);
3244   fprintf (file, "Total alias mayalias results:\t%u\n", 
3245            alias_stats.alias_mayalias);
3246   fprintf (file, "Total alias noalias results:\t%u\n",
3247            alias_stats.alias_noalias);
3248   fprintf (file, "Total simple queries:\t%u\n",
3249            alias_stats.simple_queries);
3250   fprintf (file, "Total simple resolved:\t%u\n",
3251            alias_stats.simple_resolved);
3252   fprintf (file, "Total TBAA queries:\t%u\n",
3253            alias_stats.tbaa_queries);
3254   fprintf (file, "Total TBAA resolved:\t%u\n",
3255            alias_stats.tbaa_resolved);
3256   fprintf (file, "Total non-addressable structure type queries:\t%u\n",
3257            alias_stats.structnoaddress_queries);
3258   fprintf (file, "Total non-addressable structure type resolved:\t%u\n",
3259            alias_stats.structnoaddress_resolved);
3260 }
3261   
3262
3263 /* Dump alias information on FILE.  */
3264
3265 void
3266 dump_alias_info (FILE *file)
3267 {
3268   size_t i;
3269   const char *funcname
3270     = lang_hooks.decl_printable_name (current_function_decl, 2);
3271   referenced_var_iterator rvi;
3272   tree var;
3273
3274   fprintf (file, "\nAlias information for %s\n\n", funcname);
3275
3276   dump_memory_partitions (file);
3277
3278   fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname);
3279
3280   fprintf (file, "Aliased symbols\n\n");
3281   
3282   FOR_EACH_REFERENCED_VAR (var, rvi)
3283     {
3284       if (may_be_aliased (var))
3285         dump_variable (file, var);
3286     }
3287
3288   fprintf (file, "\nDereferenced pointers\n\n");
3289
3290   FOR_EACH_REFERENCED_VAR (var, rvi)
3291     if (symbol_mem_tag (var))
3292       dump_variable (file, var);
3293
3294   fprintf (file, "\nSymbol memory tags\n\n");
3295   
3296   FOR_EACH_REFERENCED_VAR (var, rvi)
3297     {
3298       if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
3299         dump_variable (file, var);
3300     }
3301
3302   fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname);
3303
3304   fprintf (file, "SSA_NAME pointers\n\n");
3305   for (i = 1; i < num_ssa_names; i++)
3306     {
3307       tree ptr = ssa_name (i);
3308       struct ptr_info_def *pi;
3309       
3310       if (ptr == NULL_TREE)
3311         continue;
3312
3313       pi = SSA_NAME_PTR_INFO (ptr);
3314       if (!SSA_NAME_IN_FREE_LIST (ptr)
3315           && pi
3316           && pi->name_mem_tag)
3317         dump_points_to_info_for (file, ptr);
3318     }
3319
3320   fprintf (file, "\nName memory tags\n\n");
3321   
3322   FOR_EACH_REFERENCED_VAR (var, rvi)
3323     {
3324       if (TREE_CODE (var) == NAME_MEMORY_TAG)
3325         dump_variable (file, var);
3326     }
3327
3328   fprintf (file, "\n");
3329 }
3330
3331
3332 /* Dump alias information on stderr.  */
3333
3334 void
3335 debug_alias_info (void)
3336 {
3337   dump_alias_info (stderr);
3338 }
3339
3340
3341 /* Return the alias information associated with pointer T.  It creates a
3342    new instance if none existed.  */
3343
3344 struct ptr_info_def *
3345 get_ptr_info (tree t)
3346 {
3347   struct ptr_info_def *pi;
3348
3349   gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
3350
3351   pi = SSA_NAME_PTR_INFO (t);
3352   if (pi == NULL)
3353     {
3354       pi = GGC_CNEW (struct ptr_info_def);
3355       SSA_NAME_PTR_INFO (t) = pi;
3356     }
3357
3358   return pi;
3359 }
3360
3361
3362 /* Dump points-to information for SSA_NAME PTR into FILE.  */
3363
3364 void
3365 dump_points_to_info_for (FILE *file, tree ptr)
3366 {
3367   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
3368
3369   print_generic_expr (file, ptr, dump_flags);
3370
3371   if (pi)
3372     {
3373       if (pi->name_mem_tag)
3374         {
3375           fprintf (file, ", name memory tag: ");
3376           print_generic_expr (file, pi->name_mem_tag, dump_flags);
3377         }
3378
3379       if (pi->is_dereferenced)
3380         fprintf (file, ", is dereferenced");
3381
3382       if (pi->value_escapes_p)
3383         fprintf (file, ", its value escapes");
3384
3385       if (pi->pt_anything)
3386         fprintf (file, ", points-to anything");
3387
3388       if (pi->pt_null)
3389         fprintf (file, ", points-to NULL");
3390
3391       if (pi->pt_vars)
3392         {
3393           fprintf (file, ", points-to vars: ");
3394           dump_decl_set (file, pi->pt_vars);
3395         }
3396     }
3397
3398   fprintf (file, "\n");
3399 }
3400
3401
3402 /* Dump points-to information for VAR into stderr.  */
3403
3404 void
3405 debug_points_to_info_for (tree var)
3406 {
3407   dump_points_to_info_for (stderr, var);
3408 }
3409
3410
3411 /* Dump points-to information into FILE.  NOTE: This function is slow, as
3412    it needs to traverse the whole CFG looking for pointer SSA_NAMEs.  */
3413
3414 void
3415 dump_points_to_info (FILE *file)
3416 {
3417   basic_block bb;
3418   block_stmt_iterator si;
3419   ssa_op_iter iter;
3420   const char *fname =
3421     lang_hooks.decl_printable_name (current_function_decl, 2);
3422   referenced_var_iterator rvi;
3423   tree var;
3424
3425   fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname);
3426
3427   /* First dump points-to information for the default definitions of
3428      pointer variables.  This is necessary because default definitions are
3429      not part of the code.  */
3430   FOR_EACH_REFERENCED_VAR (var, rvi)
3431     {
3432       if (POINTER_TYPE_P (TREE_TYPE (var)))
3433         {
3434           tree def = gimple_default_def (cfun, var);
3435           if (def)
3436             dump_points_to_info_for (file, def);
3437         }
3438     }
3439
3440   /* Dump points-to information for every pointer defined in the program.  */
3441   FOR_EACH_BB (bb)
3442     {
3443       tree phi;
3444
3445       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3446         {
3447           tree ptr = PHI_RESULT (phi);
3448           if (POINTER_TYPE_P (TREE_TYPE (ptr)))
3449             dump_points_to_info_for (file, ptr);
3450         }
3451
3452         for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
3453           {
3454             tree stmt = bsi_stmt (si);
3455             tree def;
3456             FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3457               if (TREE_CODE (def) == SSA_NAME
3458                   && POINTER_TYPE_P (TREE_TYPE (def)))
3459                 dump_points_to_info_for (file, def);
3460           }
3461     }
3462
3463   fprintf (file, "\n");
3464 }
3465
3466
3467 /* Dump points-to info pointed to by PTO into STDERR.  */
3468
3469 void
3470 debug_points_to_info (void)
3471 {
3472   dump_points_to_info (stderr);
3473 }
3474
3475 /* Dump to FILE the list of variables that may be aliasing VAR.  */
3476
3477 void
3478 dump_may_aliases_for (FILE *file, tree var)
3479 {
3480   bitmap aliases;
3481   
3482   aliases = MTAG_ALIASES (var);
3483   if (aliases)
3484     {
3485       bitmap_iterator bi;
3486       unsigned int i;
3487       tree al;
3488
3489       fprintf (file, "{ ");
3490       EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
3491         {
3492           al = referenced_var (i);
3493           print_generic_expr (file, al, dump_flags);
3494           fprintf (file, " ");
3495         }
3496       fprintf (file, "}");
3497     }
3498 }
3499
3500
3501 /* Dump to stderr the list of variables that may be aliasing VAR.  */
3502
3503 void
3504 debug_may_aliases_for (tree var)
3505 {
3506   dump_may_aliases_for (stderr, var);
3507 }
3508
3509
3510 /* Return true if VAR may be aliased.  */
3511
3512 bool
3513 may_be_aliased (tree var)
3514 {
3515   /* Obviously.  */
3516   if (TREE_ADDRESSABLE (var))
3517     return true;
3518
3519   /* Globally visible variables can have their addresses taken by other
3520      translation units.  */
3521   if (MTAG_P (var)
3522       && (MTAG_GLOBAL (var) || TREE_PUBLIC (var)))
3523     return true;
3524   else if (!MTAG_P (var)
3525            && (DECL_EXTERNAL (var) || TREE_PUBLIC (var)))
3526     return true;
3527
3528   /* Automatic variables can't have their addresses escape any other
3529      way.  This must be after the check for global variables, as
3530      extern declarations do not have TREE_STATIC set.  */
3531   if (!TREE_STATIC (var))
3532     return false;
3533
3534   /* If we're in unit-at-a-time mode, then we must have seen all
3535      occurrences of address-of operators, and so we can trust
3536      TREE_ADDRESSABLE.  Otherwise we can only be sure the variable
3537      isn't addressable if it's local to the current function.  */
3538   if (flag_unit_at_a_time)
3539     return false;
3540
3541   if (decl_function_context (var) == current_function_decl)
3542     return false;
3543
3544   return true;
3545 }
3546
3547 /* The following is based on code in add_stmt_operand to ensure that the
3548    same defs/uses/vdefs/vuses will be found after replacing a reference
3549    to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value
3550    is the address of var.  Return a memtag for the ptr, after adding the 
3551    proper may_aliases to it (which are the aliases of var, if it has any,
3552    or var itself).  */
3553
3554 static tree
3555 add_may_alias_for_new_tag (tree tag, tree var)
3556 {
3557   bitmap aliases = NULL;
3558   
3559   if (MTAG_P (var))
3560     aliases = may_aliases (var);
3561
3562   /* Case 1: |aliases| == 1  */
3563   if (aliases
3564       && bitmap_single_bit_set_p (aliases))
3565     {
3566       tree ali = referenced_var (bitmap_first_set_bit (aliases));
3567       if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG)
3568         return ali;
3569     }
3570
3571   /* Case 2: |aliases| == 0  */
3572   if (aliases == NULL)
3573     add_may_alias (tag, var);
3574   else
3575     {
3576       /* Case 3: |aliases| > 1  */
3577       union_alias_set_into (tag, aliases);
3578     }
3579   return tag;
3580 }
3581
3582 /* Create a new symbol tag for PTR.  Construct the may-alias list of this type
3583    tag so that it has the aliasing of VAR, or of the relevant subvars of VAR
3584    according to the location accessed by EXPR.
3585
3586    Note, the set of aliases represented by the new symbol tag are not marked
3587    for renaming.  */
3588
3589 void
3590 new_type_alias (tree ptr, tree var, tree expr)
3591 {
3592   tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
3593   tree tag;
3594   subvar_t svars;
3595   tree ali = NULL_TREE;
3596   HOST_WIDE_INT offset, size, maxsize;
3597   tree ref;
3598   VEC (tree, heap) *overlaps = NULL;
3599   unsigned int len, i;
3600   tree subvar;
3601
3602
3603   gcc_assert (symbol_mem_tag (ptr) == NULL_TREE);
3604   gcc_assert (!MTAG_P (var));
3605
3606   ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
3607   gcc_assert (ref);
3608
3609   tag = create_memory_tag (tag_type, true);
3610   set_symbol_mem_tag (ptr, tag);
3611
3612   /* Add VAR to the may-alias set of PTR's new symbol tag.  If VAR has
3613      subvars, add the subvars to the tag instead of the actual var.  */
3614   if (var_can_have_subvars (ref)
3615       && (svars = get_subvars_for_var (ref)))
3616     {
3617       for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
3618         {
3619           bool exact;
3620
3621           if (overlap_subvar (offset, maxsize, subvar, &exact))
3622             VEC_safe_push (tree, heap, overlaps, subvar);
3623         }
3624       gcc_assert (overlaps != NULL);
3625     }
3626   else if (var_can_have_subvars (var)
3627            && (svars = get_subvars_for_var (var)))
3628     {
3629       /* If the REF is not a direct access to VAR (e.g., it is a dereference
3630          of a pointer), we should scan the virtual operands of REF the same
3631          way as tree-ssa-operands do.  At the moment, this is somewhat
3632          difficult, so we just give up and add all the subvars of VAR.
3633          On mem-ssa branch, the scanning for virtual operands have been
3634          split from the rest of tree-ssa-operands, so it should be much
3635          easier to fix this problem correctly once mem-ssa is merged.  */
3636       for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
3637         VEC_safe_push (tree, heap, overlaps, subvar);
3638
3639       gcc_assert (overlaps != NULL);
3640     }
3641   else
3642     ali = add_may_alias_for_new_tag (tag, var);
3643
3644   len = VEC_length (tree, overlaps);
3645   if (len > 0)
3646     {
3647       if (dump_file && (dump_flags & TDF_DETAILS))
3648         fprintf (dump_file, "\nnumber of overlapping subvars = %u\n", len);
3649
3650       if (len == 1)
3651         ali = add_may_alias_for_new_tag (tag, VEC_index (tree, overlaps, 0));
3652       else if (len > 1)
3653         {
3654           unsigned int k;
3655           tree sv_var;
3656
3657           for (k = 0; VEC_iterate (tree, overlaps, k, sv_var); k++)
3658             {
3659               ali = add_may_alias_for_new_tag (tag, sv_var);
3660
3661               if (ali != tag)
3662                 {
3663                   /* Can happen only if 'Case 1' of add_may_alias_for_new_tag
3664                      took place.  Since more than one svar was found, we add 
3665                      'ali' as one of the may_aliases of the new tag.  */ 
3666                   add_may_alias (tag, ali);
3667                   ali = tag;
3668                 }
3669             }
3670         }
3671       VEC_free (tree, heap, overlaps);
3672     }
3673
3674   set_symbol_mem_tag (ptr, ali);
3675   TREE_READONLY (tag) = TREE_READONLY (var);
3676   MTAG_GLOBAL (tag) = is_global_var (var);
3677 }
3678
3679 /* This represents the used range of a variable.  */
3680
3681 typedef struct used_part
3682 {
3683   HOST_WIDE_INT minused;
3684   HOST_WIDE_INT maxused;
3685   /* True if we have an explicit use/def of some portion of this variable,
3686      even if it is all of it. i.e. a.b = 5 or temp = a.b.  */
3687   bool explicit_uses;
3688   /* True if we have an implicit use/def of some portion of this
3689      variable.  Implicit uses occur when we can't tell what part we
3690      are referencing, and have to make conservative assumptions.  */
3691   bool implicit_uses;
3692   /* True if the structure is only written to or taken its address.  */
3693   bool write_only;
3694 } *used_part_t;
3695
3696 /* An array of used_part structures, indexed by variable uid.  */
3697
3698 static htab_t used_portions;
3699
3700 struct used_part_map
3701 {
3702   unsigned int uid;
3703   used_part_t to;
3704 };
3705
3706 /* Return true if the uid in the two used part maps are equal.  */
3707
3708 static int
3709 used_part_map_eq (const void *va, const void *vb)
3710 {
3711   const struct used_part_map *a = (const struct used_part_map *) va;
3712   const struct used_part_map *b = (const struct used_part_map *) vb;
3713   return (a->uid == b->uid);
3714 }
3715
3716 /* Hash a from uid in a used_part_map.  */
3717
3718 static unsigned int
3719 used_part_map_hash (const void *item)
3720 {
3721   return ((const struct used_part_map *)item)->uid;
3722 }
3723
3724 /* Free a used part map element.  */
3725
3726 static void 
3727 free_used_part_map (void *item)
3728 {
3729   free (((struct used_part_map *)item)->to);
3730   free (item);
3731 }
3732
3733 /* Lookup a used_part structure for a UID.  */
3734
3735 static used_part_t
3736 up_lookup (unsigned int uid)
3737 {
3738   struct used_part_map *h, in;
3739   in.uid = uid;
3740   h = (struct used_part_map *) htab_find_with_hash (used_portions, &in, uid);
3741   if (!h)
3742     return NULL;
3743   return h->to;
3744 }
3745
3746 /* Insert the pair UID, TO into the used part hashtable.  */
3747  
3748 static void 
3749 up_insert (unsigned int uid, used_part_t to)
3750
3751   struct used_part_map *h;
3752   void **loc;
3753
3754   h = XNEW (struct used_part_map);
3755   h->uid = uid;
3756   h->to = to;
3757   loc = htab_find_slot_with_hash (used_portions, h,
3758                                   uid, INSERT);
3759   if (*loc != NULL)
3760     free (*loc);
3761   *(struct used_part_map **)  loc = h;
3762 }
3763
3764
3765 /* Given a variable uid, UID, get or create the entry in the used portions
3766    table for the variable.  */
3767
3768 static used_part_t
3769 get_or_create_used_part_for (size_t uid)
3770 {
3771   used_part_t up;
3772   if ((up = up_lookup (uid)) == NULL)
3773     {
3774       up = XCNEW (struct used_part);
3775       up->minused = INT_MAX;
3776       up->maxused = 0;
3777       up->explicit_uses = false;
3778       up->implicit_uses = false;
3779       up->write_only = true;
3780     }
3781
3782   return up;
3783 }
3784
3785
3786 /* Create and return a structure sub-variable for field type FIELD at
3787    offset OFFSET, with size SIZE, of variable VAR.  If ALIAS_SET not
3788    -1 this field is non-addressable and we should use this alias set
3789    with this field.  */
3790
3791 static tree
3792 create_sft (tree var, tree field, unsigned HOST_WIDE_INT offset,
3793             unsigned HOST_WIDE_INT size, alias_set_type alias_set,
3794             bool base_for_components)
3795 {
3796   tree subvar = create_tag_raw (STRUCT_FIELD_TAG, field, "SFT");
3797
3798   /* We need to copy the various flags from VAR to SUBVAR, so that
3799      they are is_global_var iff the original variable was.  */
3800   DECL_CONTEXT (subvar) = DECL_CONTEXT (var);
3801   MTAG_GLOBAL (subvar) = DECL_EXTERNAL (var);
3802   TREE_PUBLIC  (subvar) = TREE_PUBLIC (var);
3803   TREE_STATIC (subvar) = TREE_STATIC (var);
3804   TREE_READONLY (subvar) = TREE_READONLY (var);
3805   TREE_ADDRESSABLE (subvar) = TREE_ADDRESSABLE (var);
3806
3807   /* Add the new variable to REFERENCED_VARS.  */
3808   set_symbol_mem_tag (subvar, NULL);
3809   add_referenced_var (subvar);
3810   SFT_PARENT_VAR (subvar) = var;
3811   SFT_OFFSET (subvar) = offset;
3812   SFT_SIZE (subvar) = size;
3813   SFT_ALIAS_SET (subvar) = alias_set;
3814   SFT_BASE_FOR_COMPONENTS_P (subvar) = base_for_components;
3815   SFT_UNPARTITIONABLE_P (subvar) = false;
3816
3817   return subvar;
3818 }
3819
3820
3821 /* Given an aggregate VAR, create the subvariables that represent its
3822    fields.  */
3823
3824 static void
3825 create_overlap_variables_for (tree var)
3826 {
3827   VEC(fieldoff_s,heap) *fieldstack = NULL;
3828   used_part_t up;
3829   size_t uid = DECL_UID (var);
3830
3831   up = up_lookup (uid);
3832   if (!up
3833       || up->write_only)
3834     return;
3835
3836   push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL,
3837                                TREE_TYPE (var));
3838   /* Make sure to not create SFTs for structs we won't generate variable
3839      infos for.  See tree-ssa-structalias.c:create_variable_info_for ().  */
3840   if (VEC_length (fieldoff_s, fieldstack) > 1
3841       && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
3842     {
3843       subvar_t *subvars;
3844       fieldoff_s *fo;
3845       bool notokay = false;
3846       int fieldcount = 0;
3847       int i;
3848       HOST_WIDE_INT lastfooffset = -1;
3849       HOST_WIDE_INT lastfosize = -1;
3850       tree lastfotype = NULL_TREE;
3851
3852       /* Not all fields have DECL_SIZE set, and those that don't, we don't
3853          know their size, and thus, can't handle.
3854          The same is true of fields with DECL_SIZE that is not an integer
3855          constant (such as variable sized fields).
3856          Fields with offsets which are not constant will have an offset < 0 
3857          We *could* handle fields that are constant sized arrays, but
3858          currently don't.  Doing so would require some extra changes to
3859          tree-ssa-operands.c.  */
3860
3861       for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3862         {
3863           if (!fo->size
3864               || TREE_CODE (fo->size) != INTEGER_CST
3865               || fo->offset < 0)
3866             {
3867               notokay = true;
3868               break;
3869             }
3870           fieldcount++;
3871         }
3872
3873       /* The current heuristic we use is as follows:
3874          If the variable has no used portions in this function, no
3875          structure vars are created for it.
3876          Otherwise,
3877          If the variable has less than SALIAS_MAX_IMPLICIT_FIELDS,
3878          we always create structure vars for them.
3879          If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
3880          some explicit uses, we create structure vars for them.
3881          If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
3882          no explicit uses, we do not create structure vars for them.
3883       */
3884       
3885       if (fieldcount >= SALIAS_MAX_IMPLICIT_FIELDS
3886           && !up->explicit_uses)
3887         {
3888           if (dump_file && (dump_flags & TDF_DETAILS))
3889             {
3890               fprintf (dump_file, "Variable ");
3891               print_generic_expr (dump_file, var, 0);
3892               fprintf (dump_file, " has no explicit uses in this function, and is > SALIAS_MAX_IMPLICIT_FIELDS, so skipping\n");
3893             }
3894           notokay = true;
3895         }
3896       
3897       /* Bail out, if we can't create overlap variables.  */
3898       if (notokay)
3899         {
3900           VEC_free (fieldoff_s, heap, fieldstack);
3901           return;
3902         }
3903       
3904       /* Otherwise, create the variables.  */
3905       subvars = lookup_subvars_for_var (var);
3906       *subvars = VEC_alloc (tree, gc, VEC_length (fieldoff_s, fieldstack));
3907  
3908       sort_fieldstack (fieldstack);
3909
3910       for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); ++i)
3911         {
3912           HOST_WIDE_INT fosize;
3913           tree currfotype, subvar;
3914
3915           fosize = TREE_INT_CST_LOW (fo->size);
3916           currfotype = fo->type;
3917
3918           /* If this field isn't in the used portion,
3919              or it has the exact same offset and size as the last
3920              field, skip it.  Note that we always need the field at
3921              offset 0 so we can properly handle pointers to the
3922              structure.  */
3923
3924           if ((fo->offset != 0
3925                && ((fo->offset <= up->minused
3926                     && fo->offset + fosize <= up->minused)
3927                    || fo->offset >= up->maxused))
3928               || (fo->offset == lastfooffset
3929                   && fosize == lastfosize
3930                   && currfotype == lastfotype))
3931             continue;
3932           subvar = create_sft (var, fo->type, fo->offset,
3933                                fosize, fo->alias_set, fo->base_for_components);
3934           VEC_quick_push (tree, *subvars, subvar);
3935
3936           if (dump_file)
3937             {
3938               fprintf (dump_file, "structure field tag %s created for var %s",
3939                        get_name (subvar), get_name (var));
3940               fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC,
3941                        SFT_OFFSET (subvar));
3942               fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC,
3943                        SFT_SIZE (subvar));
3944               fprintf (dump_file, "\n");
3945             }
3946           
3947           lastfotype = currfotype;
3948           lastfooffset = fo->offset;
3949           lastfosize = fosize;
3950         }
3951
3952       /* Once we have created subvars, the original is no longer call
3953          clobbered on its own.  Its call clobbered status depends
3954          completely on the call clobbered status of the subvars.
3955
3956          add_referenced_var in the above loop will take care of
3957          marking subvars of global variables as call clobbered for us
3958          to start, since they are global as well.  */
3959       clear_call_clobbered (var);
3960     }
3961
3962   VEC_free (fieldoff_s, heap, fieldstack);
3963 }
3964
3965
3966 /* Find the conservative answer to the question of what portions of what 
3967    structures are used by this statement.  We assume that if we have a
3968    component ref with a known size + offset, that we only need that part
3969    of the structure.  For unknown cases, or cases where we do something
3970    to the whole structure, we assume we need to create fields for the 
3971    entire structure.  */
3972
3973 static tree
3974 find_used_portions (tree *tp, int *walk_subtrees, void *lhs_p)
3975 {
3976   switch (TREE_CODE (*tp))
3977     {
3978     case GIMPLE_MODIFY_STMT:
3979       /* Recurse manually here to track whether the use is in the
3980          LHS of an assignment.  */
3981       find_used_portions (&GIMPLE_STMT_OPERAND (*tp, 0), walk_subtrees, tp);
3982       return find_used_portions (&GIMPLE_STMT_OPERAND (*tp, 1),
3983                                  walk_subtrees, NULL);
3984     case REALPART_EXPR:
3985     case IMAGPART_EXPR:
3986     case COMPONENT_REF:
3987     case ARRAY_REF:
3988       {
3989         HOST_WIDE_INT bitsize;
3990         HOST_WIDE_INT bitmaxsize;
3991         HOST_WIDE_INT bitpos;
3992         tree ref;
3993         ref = get_ref_base_and_extent (*tp, &bitpos, &bitsize, &bitmaxsize);
3994         if (DECL_P (ref)
3995             && var_can_have_subvars (ref)
3996             && bitmaxsize != -1)
3997           {
3998             size_t uid = DECL_UID (ref);
3999             used_part_t up;
4000
4001             up = get_or_create_used_part_for (uid);         
4002
4003             if (bitpos <= up->minused)
4004               up->minused = bitpos;
4005             if ((bitpos + bitmaxsize >= up->maxused))
4006               up->maxused = bitpos + bitmaxsize;
4007
4008             if (bitsize == bitmaxsize)
4009               up->explicit_uses = true;
4010             else
4011               up->implicit_uses = true;
4012             if (!lhs_p)
4013               up->write_only = false;
4014             up_insert (uid, up);
4015
4016             *walk_subtrees = 0;
4017             return NULL_TREE;
4018           }
4019       }
4020       break;
4021       /* This is here to make sure we mark the entire base variable as used
4022          when you take its address.  Because our used portion analysis is
4023          simple, we aren't looking at casts or pointer arithmetic to see what
4024          happens when you take the address.  */
4025     case ADDR_EXPR:
4026       {
4027         tree var = get_base_address (TREE_OPERAND (*tp, 0));
4028
4029         if (var 
4030             && DECL_P (var)
4031             && DECL_SIZE (var)
4032             && var_can_have_subvars (var)
4033             && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
4034           {
4035             used_part_t up;
4036             size_t uid = DECL_UID (var);
4037             
4038             up = get_or_create_used_part_for (uid);
4039  
4040             up->minused = 0;
4041             up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
4042             up->implicit_uses = true;
4043             if (!lhs_p)
4044               up->write_only = false;
4045
4046             up_insert (uid, up);
4047             *walk_subtrees = 0;
4048             return NULL_TREE;
4049           }
4050       }
4051       break;
4052     case CALL_EXPR:
4053       {
4054         int i;
4055         int nargs = call_expr_nargs (*tp);
4056         for (i = 0; i < nargs; i++)
4057           {
4058             tree *arg = &CALL_EXPR_ARG (*tp, i);
4059             if (TREE_CODE (*arg) == ADDR_EXPR)
4060               find_used_portions (arg, walk_subtrees, NULL);
4061           }
4062         *walk_subtrees = 0;
4063         return NULL_TREE;
4064       }
4065     case VAR_DECL:
4066     case PARM_DECL:
4067     case RESULT_DECL:
4068       {
4069         tree var = *tp;
4070         if (DECL_SIZE (var)
4071             && var_can_have_subvars (var)
4072             && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
4073           {
4074             used_part_t up;
4075             size_t uid = DECL_UID (var);
4076             
4077             up = get_or_create_used_part_for (uid);
4078  
4079             up->minused = 0;
4080             up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
4081             up->implicit_uses = true;
4082
4083             up_insert (uid, up);
4084             *walk_subtrees = 0;
4085             return NULL_TREE;
4086           }
4087       }
4088       break;
4089       
4090     default:
4091       break;
4092       
4093     }
4094   return NULL_TREE;
4095 }
4096
4097 /* Create structure field variables for structures used in this function.  */
4098
4099 static unsigned int
4100 create_structure_vars (void)
4101 {
4102   basic_block bb;
4103   safe_referenced_var_iterator rvi;
4104   VEC (tree, heap) *varvec = NULL;
4105   tree var;
4106