OSDN Git Service

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