OSDN Git Service

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