gcc/tree-ssa-alias.c

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