OSDN Git Service

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