OSDN Git Service

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