OSDN Git Service

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