gcc/tree-ssa-alias.c

   1 /* Alias analysis for trees.
   2    Copyright (C) 2004, 2005, 2006, 2007 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 3, 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "timevar.h"
  31 #include "expr.h"
  32 #include "ggc.h"
  33 #include "langhooks.h"
  34 #include "flags.h"
  35 #include "function.h"
  36 #include "diagnostic.h"
  37 #include "tree-dump.h"
  38 #include "tree-gimple.h"
  39 #include "tree-flow.h"
  40 #include "tree-inline.h"
  41 #include "tree-pass.h"
  42 #include "tree-ssa-structalias.h"
  43 #include "convert.h"
  44 #include "params.h"
  45 #include "ipa-type-escape.h"
  46 #include "vec.h"
  47 #include "bitmap.h"
  48 #include "vecprim.h"
  49 #include "pointer-set.h"
  50 #include "alloc-pool.h"
  51
  52 /* Broad overview of how aliasing works:
  53
  54    First we compute points-to sets, which is done in
  55    tree-ssa-structalias.c
  56
  57    During points-to set constraint finding, a bunch of little bits of
  58    information is collected.
  59    This is not done because it is necessary for points-to, but because
  60    points-to has to walk every statement anyway.  The function performing
  61    this collecting is update_alias_info.
  62
  63    Bits update_alias_info collects include:
  64    1. Directly escaping variables and variables whose value escapes
  65    (using is_escape_site).  This is the set of variables and values that
  66    escape prior to transitive closure of the clobbers.
  67    2.  The set of variables dereferenced on the LHS (into
  68    dereferenced_ptr_stores)
  69    3. The set of variables dereferenced on the RHS (into
  70    dereferenced_ptr_loads)
  71    4. The set of all pointers we saw.
  72    5. The number of loads and stores for each variable
  73    6. The number of statements touching memory
  74    7. The set of address taken variables.
  75
  76
  77    #1 is computed by a combination of is_escape_site, and counting the
  78    number of uses/deref operators.  This function properly accounts for
  79    situations like &ptr->field, which is *not* a dereference.
  80
  81    After points-to sets are computed, the sets themselves still
  82    contain points-to specific variables, such as a variable that says
  83    the pointer points to anything, a variable that says the pointer
  84    points to readonly memory, etc.
  85
  86    These are eliminated in a later phase, as we will see.
  87
  88    The rest of the phases are located in tree-ssa-alias.c
  89
  90    The next phase after points-to set computation is called
  91    "setup_pointers_and_addressables"
  92
  93    This pass does 3 main things:
  94
  95    1. All variables that can have TREE_ADDRESSABLE removed safely (IE
  96    non-globals whose address is not taken), have TREE_ADDRESSABLE
  97    removed.
  98    2. All variables that may be aliased (which is the set of addressable
  99    variables and globals) at all, are marked for renaming, and have
 100    symbol memory tags created for them.
 101    3. All variables which are stored into have their SMT's added to
 102    written vars.
 103
 104
 105    After this function is run, all variables that will ever have an
 106    SMT, have one, though its aliases are not filled in.
 107
 108    The next phase is to compute flow-insensitive aliasing, which in
 109    our case, is a misnomer.  it is really computing aliasing that
 110    requires no transitive closure to be correct.  In particular, it
 111    uses stack vs non-stack, TBAA, etc, to determine whether two
 112    symbols could *ever* alias .  This phase works by going through all
 113    the pointers we collected during update_alias_info, and for every
 114    addressable variable in the program, seeing if they alias.  If so,
 115    the addressable variable is added to the symbol memory tag for the
 116    pointer.
 117
 118    As part of this, we handle symbol memory tags that conflict but
 119    have no aliases in common, by forcing them to have a symbol in
 120    common (through unioning alias sets or adding one as an alias of
 121    the other), or by adding one as an alias of another.  The case of
 122    conflicts with no aliases in common occurs mainly due to aliasing
 123    we cannot see.  In particular, it generally means we have a load
 124    through a pointer whose value came from outside the function.
 125    Without an addressable symbol to point to, they would get the wrong
 126    answer.
 127
 128    After flow insensitive aliasing is computed, we compute name tags
 129    (called compute_flow_sensitive_info).  We walk each pointer we
 130    collected and see if it has a usable points-to set.  If so, we
 131    generate a name tag using that pointer, and make an alias bitmap for
 132    it.  Name tags are shared between all things with the same alias
 133    bitmap.  The alias bitmap will be translated from what points-to
 134    computed.  In particular, the "anything" variable in points-to will be
 135    transformed into a pruned set of SMT's and their aliases that
 136    compute_flow_insensitive_aliasing computed.
 137    Note that since 4.3, every pointer that points-to computed a solution for
 138    will get a name tag (whereas before 4.3, only those whose set did
 139    *not* include the anything variable would).  At the point where name
 140    tags are all assigned, symbol memory tags are dead, and could be
 141    deleted, *except* on global variables.  Global variables still use
 142    symbol memory tags as of right now.
 143
 144    After name tags are computed, the set of clobbered variables is
 145    transitively closed.  In particular, we compute the set of clobbered
 146    variables based on the initial set of clobbers, plus the aliases of
 147    pointers which either escape, or have their value escape.
 148
 149    After this, maybe_create_global_var is run, which handles a corner
 150    case where we have no call clobbered variables, but have pure and
 151    non-pure functions.
 152
 153    Staring at this function, I now remember it is a hack for the fact
 154    that we do not mark all globals in the program as call clobbered for a
 155    function unless they are actually used in that function.  Instead,  we
 156    only mark the set that is actually clobbered.  As a result, you can
 157    end up with situations where you have no call clobbered vars set.
 158
 159    After maybe_create_global_var, we set pointers with the REF_ALL flag
 160    to have alias sets that include all clobbered
 161    memory tags and variables.
 162
 163    After this, memory partitioning is computed (by the function
 164    compute_memory_partitions) and alias sets are reworked accordingly.
 165
 166    Lastly, we delete partitions with no symbols, and clean up after
 167    ourselves.  */
 168
 169 /* Structure to map a variable to its alias set.  */
 170 struct alias_map_d
 171 {
 172   /* Variable and its alias set.  */
 173   tree var;
 174   alias_set_type set;
 175 };
 176
 177
 178 /* Counters used to display statistics on alias analysis.  */
 179 struct alias_stats_d
 180 {
 181   unsigned int alias_queries;
 182   unsigned int alias_mayalias;
 183   unsigned int alias_noalias;
 184   unsigned int simple_queries;
 185   unsigned int simple_resolved;
 186   unsigned int tbaa_queries;
 187   unsigned int tbaa_resolved;
 188   unsigned int structnoaddress_queries;
 189   unsigned int structnoaddress_resolved;
 190 };
 191
 192
 193 /* Local variables.  */
 194 static struct alias_stats_d alias_stats;
 195 static bitmap_obstack alias_bitmap_obstack;
 196
 197 /* Local functions.  */
 198 static void compute_flow_insensitive_aliasing (struct alias_info *);
 199 static void dump_alias_stats (FILE *);
 200 static bool may_alias_p (tree, alias_set_type, tree, alias_set_type, bool);
 201 static tree create_memory_tag (tree type, bool is_type_tag);
 202 static tree get_smt_for (tree, struct alias_info *);
 203 static tree get_nmt_for (tree);
 204 static void add_may_alias (tree, tree);
 205 static struct alias_info *init_alias_info (void);
 206 static void delete_alias_info (struct alias_info *);
 207 static void compute_flow_sensitive_aliasing (struct alias_info *);
 208 static void setup_pointers_and_addressables (struct alias_info *);
 209 static void create_global_var (void);
 210 static void maybe_create_global_var (void);
 211 static void set_pt_anything (tree);
 212
 213 void debug_mp_info (VEC(mem_sym_stats_t,heap) *);
 214
 215 static alloc_pool mem_sym_stats_pool;
 216
 217 /* Return memory reference stats for symbol VAR.  Create a new slot in
 218    cfun->gimple_df->mem_sym_stats if needed.  */
 219
 220 static struct mem_sym_stats_d *
 221 get_mem_sym_stats_for (tree var)
 222 {
 223   void **slot;
 224   struct mem_sym_stats_d *stats;
 225   struct pointer_map_t *map = gimple_mem_ref_stats (cfun)->mem_sym_stats;
 226
 227   gcc_assert (map);
 228
 229   slot = pointer_map_insert (map, var);
 230   if (*slot == NULL)
 231     {
 232       stats = pool_alloc (mem_sym_stats_pool);
 233       memset (stats, 0, sizeof (*stats));
 234       stats->var = var;
 235       *slot = (void *) stats;
 236     }
 237   else
 238     stats = (struct mem_sym_stats_d *) *slot;
 239
 240   return stats;
 241 }
 242
 243
 244 /* Return memory reference statistics for variable VAR in function FN.
 245    This is computed by alias analysis, but it is not kept
 246    incrementally up-to-date.  So, these stats are only accurate if
 247    pass_may_alias has been run recently.  If no alias information
 248    exists, this function returns NULL.  */
 249
 250 static mem_sym_stats_t
 251 mem_sym_stats (struct function *fn, tree var)
 252 {
 253   void **slot;
 254   struct pointer_map_t *stats_map = gimple_mem_ref_stats (fn)->mem_sym_stats;
 255
 256   if (stats_map == NULL)
 257     return NULL;
 258
 259   slot = pointer_map_contains (stats_map, var);
 260   if (slot == NULL)
 261     return NULL;
 262
 263   return (mem_sym_stats_t) *slot;
 264 }
 265
 266
 267 /* Set MPT to be the memory partition associated with symbol SYM.  */
 268
 269 static inline void
 270 set_memory_partition (tree sym, tree mpt)
 271 {
 272 #if defined ENABLE_CHECKING
 273   if (mpt)
 274     gcc_assert (TREE_CODE (mpt) == MEMORY_PARTITION_TAG
 275                 && !is_gimple_reg (sym));
 276 #endif
 277
 278   var_ann (sym)->mpt = mpt;
 279   if (mpt)
 280     {
 281       if (MPT_SYMBOLS (mpt) == NULL)
 282         MPT_SYMBOLS (mpt) = BITMAP_ALLOC (&alias_bitmap_obstack);
 283
 284       bitmap_set_bit (MPT_SYMBOLS (mpt), DECL_UID (sym));
 285
 286       /* MPT inherits the call-clobbering attributes from SYM.  */
 287       if (is_call_clobbered (sym))
 288         {
 289           MTAG_GLOBAL (mpt) = 1;
 290           mark_call_clobbered (mpt, ESCAPE_IS_GLOBAL);
 291         }
 292     }
 293 }
 294
 295
 296 /* Mark variable VAR as being non-addressable.  */
 297
 298 static void
 299 mark_non_addressable (tree var)
 300 {
 301   tree mpt;
 302
 303   if (!TREE_ADDRESSABLE (var))
 304     return;
 305
 306   mpt = memory_partition (var);
 307
 308   if (!MTAG_P (var))
 309     var_ann (var)->call_clobbered = false;
 310
 311   bitmap_clear_bit (gimple_call_clobbered_vars (cfun), DECL_UID (var));
 312   TREE_ADDRESSABLE (var) = 0;
 313
 314   if (mpt)
 315     {
 316       /* Note that it's possible for a symbol to have an associated
 317          MPT and the MPT have a NULL empty set.  During
 318          init_alias_info, all MPTs get their sets cleared out, but the
 319          symbols still point to the old MPTs that used to hold them.
 320          This is done so that compute_memory_partitions can now which
 321          symbols are losing or changing partitions and mark them for
 322          renaming.  */
 323       if (MPT_SYMBOLS (mpt))
 324         bitmap_clear_bit (MPT_SYMBOLS (mpt), DECL_UID (var));
 325       set_memory_partition (var, NULL_TREE);
 326     }
 327 }
 328
 329
 330 /* qsort comparison function to sort type/name tags by DECL_UID.  */
 331
 332 static int
 333 sort_tags_by_id (const void *pa, const void *pb)
 334 {
 335   const_tree const a = *(const_tree const *)pa;
 336   const_tree const b = *(const_tree const *)pb;
 337
 338   return DECL_UID (a) - DECL_UID (b);
 339 }
 340
 341 /* Initialize WORKLIST to contain those memory tags that are marked call
 342    clobbered.  Initialized WORKLIST2 to contain the reasons these
 343    memory tags escaped.  */
 344
 345 static void
 346 init_transitive_clobber_worklist (VEC (tree, heap) **worklist,
 347                                   VEC (int, heap) **worklist2,
 348                                   bitmap on_worklist)
 349 {
 350   referenced_var_iterator rvi;
 351   tree curr;
 352
 353   FOR_EACH_REFERENCED_VAR (curr, rvi)
 354     {
 355       if (MTAG_P (curr) && is_call_clobbered (curr))
 356         {
 357           VEC_safe_push (tree, heap, *worklist, curr);
 358           VEC_safe_push (int, heap, *worklist2,
 359                          var_ann (curr)->escape_mask);
 360           bitmap_set_bit (on_worklist, DECL_UID (curr));
 361         }
 362     }
 363 }
 364
 365 /* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if
 366    ALIAS is not already marked call clobbered, and is a memory
 367    tag.  */
 368
 369 static void
 370 add_to_worklist (tree alias, VEC (tree, heap) **worklist,
 371                  VEC (int, heap) **worklist2, int reason,
 372                  bitmap on_worklist)
 373 {
 374   if (MTAG_P (alias) && !is_call_clobbered (alias)
 375       && !bitmap_bit_p (on_worklist, DECL_UID (alias)))
 376     {
 377       VEC_safe_push (tree, heap, *worklist, alias);
 378       VEC_safe_push (int, heap, *worklist2, reason);
 379       bitmap_set_bit (on_worklist, DECL_UID (alias));
 380     }
 381 }
 382
 383 /* Mark aliases of TAG as call clobbered, and place any tags on the
 384    alias list that were not already call clobbered on WORKLIST.  */
 385
 386 static void
 387 mark_aliases_call_clobbered (tree tag, VEC (tree, heap) **worklist,
 388                              VEC (int, heap) **worklist2, bitmap on_worklist)
 389 {
 390   bitmap aliases;
 391   bitmap_iterator bi;
 392   unsigned int i;
 393   tree entry;
 394   var_ann_t ta = var_ann (tag);
 395
 396   if (!MTAG_P (tag))
 397     return;
 398   aliases = may_aliases (tag);
 399   if (!aliases)
 400     return;
 401
 402   EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
 403     {
 404       entry = referenced_var (i);
 405       /* If you clobber one part of a structure, you
 406          clobber the entire thing.  While this does not make
 407          the world a particularly nice place, it is necessary
 408          in order to allow C/C++ tricks that involve
 409          pointer arithmetic to work.  */
 410       if (!unmodifiable_var_p (entry))
 411         {
 412           add_to_worklist (entry, worklist, worklist2, ta->escape_mask,
 413                            on_worklist);
 414           mark_call_clobbered (entry, ta->escape_mask);
 415         }
 416     }
 417 }
 418
 419 /* Tags containing global vars need to be marked as global.
 420    Tags containing call clobbered vars need to be marked as call
 421    clobbered. */
 422
 423 static void
 424 compute_tag_properties (void)
 425 {
 426   referenced_var_iterator rvi;
 427   tree tag;
 428   bool changed = true;
 429   VEC (tree, heap) *taglist = NULL;
 430
 431   FOR_EACH_REFERENCED_VAR (tag, rvi)
 432     {
 433       if (!MTAG_P (tag))
 434         continue;
 435       VEC_safe_push (tree, heap, taglist, tag);
 436     }
 437
 438   /* We sort the taglist by DECL_UID, for two reasons.
 439      1. To get a sequential ordering to make the bitmap accesses
 440      faster.
 441      2. Because of the way we compute aliases, it's more likely that
 442      an earlier tag is included in a later tag, and this will reduce
 443      the number of iterations.
 444
 445      If we had a real tag graph, we would just topo-order it and be
 446      done with it.  */
 447   qsort (VEC_address (tree, taglist),
 448          VEC_length (tree, taglist),
 449          sizeof (tree),
 450          sort_tags_by_id);
 451
 452   /* Go through each tag not marked as global, and if it aliases
 453      global vars, mark it global.
 454
 455      If the tag contains call clobbered vars, mark it call
 456      clobbered.
 457
 458      This loop iterates because tags may appear in the may-aliases
 459      list of other tags when we group.  */
 460
 461   while (changed)
 462     {
 463       unsigned int k;
 464
 465       changed = false;
 466       for (k = 0; VEC_iterate (tree, taglist, k, tag); k++)
 467         {
 468           bitmap ma;
 469           bitmap_iterator bi;
 470           unsigned int i;
 471           tree entry;
 472           bool tagcc = is_call_clobbered (tag);
 473           bool tagglobal = MTAG_GLOBAL (tag);
 474
 475           if (tagcc && tagglobal)
 476             continue;
 477
 478           ma = may_aliases (tag);
 479           if (!ma)
 480             continue;
 481
 482           EXECUTE_IF_SET_IN_BITMAP (ma, 0, i, bi)
 483             {
 484               entry = referenced_var (i);
 485               /* Call clobbered entries cause the tag to be marked
 486                  call clobbered.  */
 487               if (!tagcc && is_call_clobbered (entry))
 488                 {
 489                   mark_call_clobbered (tag, var_ann (entry)->escape_mask);
 490                   tagcc = true;
 491                   changed = true;
 492                 }
 493
 494               /* Global vars cause the tag to be marked global.  */
 495               if (!tagglobal && is_global_var (entry))
 496                 {
 497                   MTAG_GLOBAL (tag) = true;
 498                   changed = true;
 499                   tagglobal = true;
 500                 }
 501
 502               /* Early exit once both global and cc are set, since the
 503                  loop can't do any more than that.  */
 504               if (tagcc && tagglobal)
 505                 break;
 506             }
 507         }
 508     }
 509   VEC_free (tree, heap, taglist);
 510 }
 511
 512 /* Set up the initial variable clobbers and globalness.
 513    When this function completes, only tags whose aliases need to be
 514    clobbered will be set clobbered.  Tags clobbered because they
 515    contain call clobbered vars are handled in compute_tag_properties.  */
 516
 517 static void
 518 set_initial_properties (struct alias_info *ai)
 519 {
 520   unsigned int i;
 521   referenced_var_iterator rvi;
 522   tree var;
 523   tree ptr;
 524
 525   FOR_EACH_REFERENCED_VAR (var, rvi)
 526     {
 527       if (is_global_var (var))
 528         {
 529           if (!unmodifiable_var_p (var))
 530             mark_call_clobbered (var, ESCAPE_IS_GLOBAL);
 531         }
 532       else if (TREE_CODE (var) == PARM_DECL
 533                && gimple_default_def (cfun, var)
 534                && POINTER_TYPE_P (TREE_TYPE (var)))
 535         {
 536           tree def = gimple_default_def (cfun, var);
 537           get_ptr_info (def)->value_escapes_p = 1;
 538           get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM;
 539         }
 540     }
 541
 542   for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
 543     {
 544       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
 545       tree tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
 546
 547       if (pi->value_escapes_p)
 548         {
 549           /* If PTR escapes then its associated memory tags and
 550              pointed-to variables are call-clobbered.  */
 551           if (pi->name_mem_tag)
 552             mark_call_clobbered (pi->name_mem_tag, pi->escape_mask);
 553
 554           if (tag)
 555             mark_call_clobbered (tag, pi->escape_mask);
 556
 557           if (pi->pt_vars)
 558             {
 559               bitmap_iterator bi;
 560               unsigned int j;
 561               EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
 562                 {
 563                   tree alias = referenced_var (j);
 564
 565                   /* If you clobber one part of a structure, you
 566                      clobber the entire thing.  While this does not make
 567                      the world a particularly nice place, it is necessary
 568                      in order to allow C/C++ tricks that involve
 569                      pointer arithmetic to work.  */
 570                   if (!unmodifiable_var_p (alias))
 571                     mark_call_clobbered (alias, pi->escape_mask);
 572                 }
 573             }
 574         }
 575
 576       /* If the name tag is call clobbered, so is the symbol tag
 577          associated with the base VAR_DECL.  */
 578       if (pi->name_mem_tag
 579           && tag
 580           && is_call_clobbered (pi->name_mem_tag))
 581         mark_call_clobbered (tag, pi->escape_mask);
 582
 583       /* Name tags and symbol tags that we don't know where they point
 584          to, might point to global memory, and thus, are clobbered.
 585
 586          FIXME:  This is not quite right.  They should only be
 587          clobbered if value_escapes_p is true, regardless of whether
 588          they point to global memory or not.
 589          So removing this code and fixing all the bugs would be nice.
 590          It is the cause of a bunch of clobbering.  */
 591       if ((pi->pt_global_mem || pi->pt_anything)
 592           && pi->is_dereferenced && pi->name_mem_tag)
 593         {
 594           mark_call_clobbered (pi->name_mem_tag, ESCAPE_IS_GLOBAL);
 595           MTAG_GLOBAL (pi->name_mem_tag) = true;
 596         }
 597
 598       if ((pi->pt_global_mem || pi->pt_anything)
 599           && pi->is_dereferenced
 600           && tag)
 601         {
 602           mark_call_clobbered (tag, ESCAPE_IS_GLOBAL);
 603           MTAG_GLOBAL (tag) = true;
 604         }
 605     }
 606 }
 607
 608 /* Compute which variables need to be marked call clobbered because
 609    their tag is call clobbered, and which tags need to be marked
 610    global because they contain global variables.  */
 611
 612 static void
 613 compute_call_clobbered (struct alias_info *ai)
 614 {
 615   VEC (tree, heap) *worklist = NULL;
 616   VEC (int,heap) *worklist2 = NULL;
 617   bitmap on_worklist;
 618
 619   timevar_push (TV_CALL_CLOBBER);
 620   on_worklist = BITMAP_ALLOC (NULL);
 621
 622   set_initial_properties (ai);
 623   init_transitive_clobber_worklist (&worklist, &worklist2, on_worklist);
 624   while (VEC_length (tree, worklist) != 0)
 625     {
 626       tree curr = VEC_pop (tree, worklist);
 627       int reason = VEC_pop (int, worklist2);
 628
 629       bitmap_clear_bit (on_worklist, DECL_UID (curr));
 630       mark_call_clobbered (curr, reason);
 631       mark_aliases_call_clobbered (curr, &worklist, &worklist2, on_worklist);
 632     }
 633   VEC_free (tree, heap, worklist);
 634   VEC_free (int, heap, worklist2);
 635   BITMAP_FREE (on_worklist);
 636   compute_tag_properties ();
 637   timevar_pop (TV_CALL_CLOBBER);
 638 }
 639
 640
 641 /* Dump memory partition information to FILE.  */
 642
 643 static void
 644 dump_memory_partitions (FILE *file)
 645 {
 646   unsigned i, npart;
 647   unsigned long nsyms;
 648   tree mpt;
 649
 650   fprintf (file, "\nMemory partitions\n\n");
 651   for (i = 0, npart = 0, nsyms = 0;
 652        VEC_iterate (tree, gimple_ssa_operands (cfun)->mpt_table, i, mpt);
 653        i++)
 654     {
 655       if (mpt)
 656         {
 657           bitmap syms = MPT_SYMBOLS (mpt);
 658           unsigned long n = (syms) ? bitmap_count_bits (syms) : 0;
 659
 660           fprintf (file, "#%u: ", i);
 661           print_generic_expr (file, mpt, 0);
 662           fprintf (file, ": %lu elements: ", n);
 663           dump_decl_set (file, syms);
 664           npart++;
 665           nsyms += n;
 666         }
 667     }
 668
 669   fprintf (file, "\n%u memory partitions holding %lu symbols\n", npart, nsyms);
 670 }
 671
 672
 673 /* Dump memory partition information to stderr.  */
 674
 675 void
 676 debug_memory_partitions (void)
 677 {
 678   dump_memory_partitions (stderr);
 679 }
 680
 681
 682 /* Return true if memory partitioning is required given the memory
 683    reference estimates in STATS.  */
 684
 685 static inline bool
 686 need_to_partition_p (struct mem_ref_stats_d *stats)
 687 {
 688   long num_vops = stats->num_vuses + stats->num_vdefs;
 689   long avg_vops = CEIL (num_vops, stats->num_mem_stmts);
 690   return (num_vops > (long) MAX_ALIASED_VOPS
 691           && avg_vops > (long) AVG_ALIASED_VOPS);
 692 }
 693
 694
 695 /* Count the actual number of virtual operators in CFUN.  Note that
 696    this is only meaningful after virtual operands have been populated,
 697    so it should be invoked at the end of compute_may_aliases.
 698
 699    The number of virtual operators are stored in *NUM_VDEFS_P and
 700    *NUM_VUSES_P, the number of partitioned symbols in
 701    *NUM_PARTITIONED_P and the number of unpartitioned symbols in
 702    *NUM_UNPARTITIONED_P.
 703
 704    If any of these pointers is NULL the corresponding count is not
 705    computed.  */
 706
 707 static void
 708 count_mem_refs (long *num_vuses_p, long *num_vdefs_p,
 709                 long *num_partitioned_p, long *num_unpartitioned_p)
 710 {
 711   block_stmt_iterator bsi;
 712   basic_block bb;
 713   long num_vdefs, num_vuses, num_partitioned, num_unpartitioned;
 714   referenced_var_iterator rvi;
 715   tree sym;
 716
 717   num_vuses = num_vdefs = num_partitioned = num_unpartitioned = 0;
 718
 719   if (num_vuses_p || num_vdefs_p)
 720     FOR_EACH_BB (bb)
 721       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 722         {
 723           tree stmt = bsi_stmt (bsi);
 724           if (stmt_references_memory_p (stmt))
 725             {
 726               num_vuses += NUM_SSA_OPERANDS (stmt, SSA_OP_VUSE);
 727               num_vdefs += NUM_SSA_OPERANDS (stmt, SSA_OP_VDEF);
 728             }
 729         }
 730
 731   if (num_partitioned_p || num_unpartitioned_p)
 732     FOR_EACH_REFERENCED_VAR (sym, rvi)
 733       {
 734         if (is_gimple_reg (sym))
 735           continue;
 736
 737         if (memory_partition (sym))
 738           num_partitioned++;
 739         else
 740           num_unpartitioned++;
 741       }
 742
 743   if (num_vdefs_p)
 744     *num_vdefs_p = num_vdefs;
 745
 746   if (num_vuses_p)
 747     *num_vuses_p = num_vuses;
 748
 749   if (num_partitioned_p)
 750     *num_partitioned_p = num_partitioned;
 751
 752   if (num_unpartitioned_p)
 753     *num_unpartitioned_p = num_unpartitioned;
 754 }
 755
 756
 757 /* The list is sorted by increasing partitioning score (PSCORE).
 758    This score is computed such that symbols with high scores are
 759    those that are least likely to be partitioned.  Given a symbol
 760    MP->VAR, PSCORE(S) is the result of the following weighted sum
 761
 762    PSCORE(S) =   FW * 64 + FR * 32
 763                + DW * 16 + DR *  8
 764                + IW *  4 + IR *  2
 765                + NO_ALIAS
 766
 767    where
 768
 769    FW           Execution frequency of writes to S
 770    FR           Execution frequency of reads from S
 771    DW           Number of direct writes to S
 772    DR           Number of direct reads from S
 773    IW           Number of indirect writes to S
 774    IR           Number of indirect reads from S
 775    NO_ALIAS     State of the NO_ALIAS* flags
 776
 777    The basic idea here is that symbols that are frequently
 778    written-to in hot paths of the code are the last to be considered
 779    for partitioning.  */
 780
 781 static inline long
 782 mem_sym_score (mem_sym_stats_t mp)
 783 {
 784   return mp->frequency_writes * 64 + mp->frequency_reads * 32
 785          + mp->num_direct_writes * 16 + mp->num_direct_reads * 8
 786          + mp->num_indirect_writes * 4 + mp->num_indirect_reads * 2
 787          + var_ann (mp->var)->noalias_state;
 788 }
 789
 790
 791 /* Dump memory reference stats for function CFUN to FILE.  */
 792
 793 void
 794 dump_mem_ref_stats (FILE *file)
 795 {
 796   long actual_num_vuses, actual_num_vdefs;
 797   long num_partitioned, num_unpartitioned;
 798   struct mem_ref_stats_d *stats;
 799
 800   stats = gimple_mem_ref_stats (cfun);
 801
 802   count_mem_refs (&actual_num_vuses, &actual_num_vdefs, &num_partitioned,
 803                   &num_unpartitioned);
 804
 805   fprintf (file, "\nMemory reference statistics for %s\n\n",
 806            lang_hooks.decl_printable_name (current_function_decl, 2));
 807
 808   fprintf (file, "Number of memory statements:     %ld\n",
 809            stats->num_mem_stmts);
 810   fprintf (file, "Number of call sites:            %ld\n",
 811            stats->num_call_sites);
 812   fprintf (file, "Number of pure/const call sites: %ld\n",
 813            stats->num_pure_const_call_sites);
 814   fprintf (file, "Number of asm sites:             %ld\n",
 815            stats->num_asm_sites);
 816   fprintf (file, "Estimated number of loads:       %ld (%ld/stmt)\n",
 817            stats->num_vuses,
 818            (stats->num_mem_stmts)
 819            ? CEIL (stats->num_vuses, stats->num_mem_stmts)
 820            : 0);
 821   fprintf (file, "Actual number of loads:          %ld (%ld/stmt)\n",
 822            actual_num_vuses,
 823            (stats->num_mem_stmts)
 824            ? CEIL (actual_num_vuses, stats->num_mem_stmts)
 825            : 0);
 826
 827   if (actual_num_vuses > stats->num_vuses + (stats->num_vuses / 25))
 828     fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n");
 829
 830   fprintf (file, "Estimated number of stores:      %ld (%ld/stmt)\n",
 831            stats->num_vdefs,
 832            (stats->num_mem_stmts)
 833            ? CEIL (stats->num_vdefs, stats->num_mem_stmts)
 834            : 0);
 835   fprintf (file, "Actual number of stores:         %ld (%ld/stmt)\n",
 836            actual_num_vdefs,
 837            (stats->num_mem_stmts)
 838            ? CEIL (actual_num_vdefs, stats->num_mem_stmts)
 839            : 0);
 840
 841   if (actual_num_vdefs > stats->num_vdefs + (stats->num_vdefs / 25))
 842     fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n");
 843
 844   fprintf (file, "Partitioning thresholds:         MAX = %d   AVG = %d "
 845            "(%sNEED TO PARTITION)\n", MAX_ALIASED_VOPS, AVG_ALIASED_VOPS,
 846            stats->num_mem_stmts && need_to_partition_p (stats) ? "" : "NO ");
 847   fprintf (file, "Number of partitioned symbols:   %ld\n", num_partitioned);
 848   fprintf (file, "Number of unpartitioned symbols: %ld\n", num_unpartitioned);
 849 }
 850
 851
 852 /* Dump memory reference stats for function FN to stderr.  */
 853
 854 void
 855 debug_mem_ref_stats (void)
 856 {
 857   dump_mem_ref_stats (stderr);
 858 }
 859
 860
 861 /* Dump memory reference stats for variable VAR to FILE.  */
 862
 863 static void
 864 dump_mem_sym_stats (FILE *file, tree var)
 865 {
 866   mem_sym_stats_t stats = mem_sym_stats (cfun, var);
 867
 868   if (stats == NULL)
 869     return;
 870
 871   fprintf (file, "read frequency: %6ld, write frequency: %6ld, "
 872            "direct reads: %3ld, direct writes: %3ld, "
 873            "indirect reads: %4ld, indirect writes: %4ld, symbol: ",
 874            stats->frequency_reads, stats->frequency_writes,
 875            stats->num_direct_reads, stats->num_direct_writes,
 876            stats->num_indirect_reads, stats->num_indirect_writes);
 877   print_generic_expr (file, stats->var, 0);
 878   fprintf (file, ", tags: ");
 879   dump_decl_set (file, stats->parent_tags);
 880 }
 881
 882
 883 /* Dump memory reference stats for variable VAR to stderr.  */
 884
 885 void
 886 debug_mem_sym_stats (tree var)
 887 {
 888   dump_mem_sym_stats (stderr, var);
 889 }
 890
 891 /* Dump memory reference stats for variable VAR to FILE.  For use
 892    of tree-dfa.c:dump_variable.  */
 893
 894 void
 895 dump_mem_sym_stats_for_var (FILE *file, tree var)
 896 {
 897   mem_sym_stats_t stats = mem_sym_stats (cfun, var);
 898
 899   if (stats == NULL)
 900     return;
 901
 902   fprintf (file, ", score: %ld", mem_sym_score (stats));
 903   fprintf (file, ", direct reads: %ld", stats->num_direct_reads);
 904   fprintf (file, ", direct writes: %ld", stats->num_direct_writes);
 905   fprintf (file, ", indirect reads: %ld", stats->num_indirect_reads);
 906   fprintf (file, ", indirect writes: %ld", stats->num_indirect_writes);
 907 }
 908
 909 /* Dump memory reference stats for all memory symbols to FILE.  */
 910
 911 static void
 912 dump_all_mem_sym_stats (FILE *file)
 913 {
 914   referenced_var_iterator rvi;
 915   tree sym;
 916
 917   FOR_EACH_REFERENCED_VAR (sym, rvi)
 918     {
 919       if (is_gimple_reg (sym))
 920         continue;
 921
 922       dump_mem_sym_stats (file, sym);
 923     }
 924 }
 925
 926
 927 /* Dump memory reference stats for all memory symbols to stderr.  */
 928
 929 void
 930 debug_all_mem_sym_stats (void)
 931 {
 932   dump_all_mem_sym_stats (stderr);
 933 }
 934
 935
 936 /* Dump the MP_INFO array to FILE.  */
 937
 938 static void
 939 dump_mp_info (FILE *file, VEC(mem_sym_stats_t,heap) *mp_info)
 940 {
 941   unsigned i;
 942   mem_sym_stats_t mp_p;
 943
 944   for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
 945     if (!mp_p->partitioned_p)
 946       dump_mem_sym_stats (file, mp_p->var);
 947 }
 948
 949
 950 /* Dump the MP_INFO array to stderr.  */
 951
 952 void
 953 debug_mp_info (VEC(mem_sym_stats_t,heap) *mp_info)
 954 {
 955   dump_mp_info (stderr, mp_info);
 956 }
 957
 958
 959 /* Update memory reference stats for symbol VAR in statement STMT.
 960    NUM_DIRECT_READS and NUM_DIRECT_WRITES specify the number of times
 961    that VAR is read/written in STMT (indirect reads/writes are not
 962    recorded by this function, see compute_memory_partitions).  */
 963
 964 void
 965 update_mem_sym_stats_from_stmt (tree var, tree stmt, long num_direct_reads,
 966                                 long num_direct_writes)
 967 {
 968   mem_sym_stats_t stats;
 969
 970   gcc_assert (num_direct_reads >= 0 && num_direct_writes >= 0);
 971
 972   stats = get_mem_sym_stats_for (var);
 973
 974   stats->num_direct_reads += num_direct_reads;
 975   stats->frequency_reads += ((long) bb_for_stmt (stmt)->frequency
 976                              * num_direct_reads);
 977
 978   stats->num_direct_writes += num_direct_writes;
 979   stats->frequency_writes += ((long) bb_for_stmt (stmt)->frequency
 980                               * num_direct_writes);
 981 }
 982
 983
 984 /* Given two MP_INFO entries MP1 and MP2, return -1 if MP1->VAR should
 985    be partitioned before MP2->VAR, 0 if they are the same or 1 if
 986    MP1->VAR should be partitioned after MP2->VAR.  */
 987
 988 static inline int
 989 compare_mp_info_entries (mem_sym_stats_t mp1, mem_sym_stats_t mp2)
 990 {
 991   long pscore1 = mem_sym_score (mp1);
 992   long pscore2 = mem_sym_score (mp2);
 993
 994   if (pscore1 < pscore2)
 995     return -1;
 996   else if (pscore1 > pscore2)
 997     return 1;
 998   else
 999     return DECL_UID (mp1->var) - DECL_UID (mp2->var);
1000 }
1001
1002
1003 /* Comparison routine for qsort.  The list is sorted by increasing
1004    partitioning score (PSCORE).  This score is computed such that
1005    symbols with high scores are those that are least likely to be
1006    partitioned.  */
1007
1008 static int
1009 mp_info_cmp (const void *p, const void *q)
1010 {
1011   mem_sym_stats_t e1 = *((const mem_sym_stats_t *) p);
1012   mem_sym_stats_t e2 = *((const mem_sym_stats_t *) q);
1013   return compare_mp_info_entries (e1, e2);
1014 }
1015
1016
1017 /* Sort the array of reference counts used to compute memory partitions.
1018    Elements are sorted in ascending order of execution frequency and
1019    descending order of virtual operators needed.  */
1020
1021 static inline void
1022 sort_mp_info (VEC(mem_sym_stats_t,heap) *list)
1023 {
1024   unsigned num = VEC_length (mem_sym_stats_t, list);
1025
1026   if (num < 2)
1027     return;
1028
1029   if (num == 2)
1030     {
1031       if (compare_mp_info_entries (VEC_index (mem_sym_stats_t, list, 0),
1032                                    VEC_index (mem_sym_stats_t, list, 1)) > 0)
1033         {
1034           /* Swap elements if they are in the wrong order.  */
1035           mem_sym_stats_t tmp = VEC_index (mem_sym_stats_t, list, 0);
1036           VEC_replace (mem_sym_stats_t, list, 0,
1037                        VEC_index (mem_sym_stats_t, list, 1));
1038           VEC_replace (mem_sym_stats_t, list, 1, tmp);
1039         }
1040
1041       return;
1042     }
1043
1044   /* There are 3 or more elements, call qsort.  */
1045   qsort (VEC_address (mem_sym_stats_t, list),
1046          VEC_length (mem_sym_stats_t, list),
1047          sizeof (mem_sym_stats_t),
1048          mp_info_cmp);
1049 }
1050
1051
1052 /* Return the memory partition tag (MPT) associated with memory
1053    symbol SYM.  */
1054
1055 static tree
1056 get_mpt_for (tree sym)
1057 {
1058   tree mpt;
1059
1060   /* Don't create a new tag unnecessarily.  */
1061   mpt = memory_partition (sym);
1062   if (mpt == NULL_TREE)
1063     {
1064       mpt = create_tag_raw (MEMORY_PARTITION_TAG, TREE_TYPE (sym), "MPT");
1065       TREE_ADDRESSABLE (mpt) = 0;
1066       add_referenced_var (mpt);
1067       VEC_safe_push (tree, heap, gimple_ssa_operands (cfun)->mpt_table, mpt);
1068       gcc_assert (MPT_SYMBOLS (mpt) == NULL);
1069       set_memory_partition (sym, mpt);
1070     }
1071
1072   return mpt;
1073 }
1074
1075
1076 /* Add MP_P->VAR to a memory partition and return the partition.  */
1077
1078 static tree
1079 find_partition_for (mem_sym_stats_t mp_p)
1080 {
1081   unsigned i;
1082   VEC(tree,heap) *mpt_table;
1083   tree mpt;
1084
1085   mpt_table = gimple_ssa_operands (cfun)->mpt_table;
1086   mpt = NULL_TREE;
1087
1088   /* Find an existing partition for MP_P->VAR.  */
1089   for (i = 0; VEC_iterate (tree, mpt_table, i, mpt); i++)
1090     {
1091       mem_sym_stats_t mpt_stats;
1092
1093       /* If MPT does not have any symbols yet, use it.  */
1094       if (MPT_SYMBOLS (mpt) == NULL)
1095         break;
1096
1097       /* Otherwise, see if MPT has common parent tags with MP_P->VAR,
1098          but avoid grouping clobbered variables with non-clobbered
1099          variables (otherwise, this tends to creates a single memory
1100          partition because other call-clobbered variables may have
1101          common parent tags with non-clobbered ones).  */
1102       mpt_stats = get_mem_sym_stats_for (mpt);
1103       if (mp_p->parent_tags
1104           && mpt_stats->parent_tags
1105           && is_call_clobbered (mpt) == is_call_clobbered (mp_p->var)
1106           && bitmap_intersect_p (mpt_stats->parent_tags, mp_p->parent_tags))
1107         break;
1108
1109       /* If no common parent tags are found, see if both MPT and
1110          MP_P->VAR are call-clobbered.  */
1111       if (is_call_clobbered (mpt) && is_call_clobbered (mp_p->var))
1112         break;
1113     }
1114
1115   if (mpt == NULL_TREE)
1116     mpt = get_mpt_for (mp_p->var);
1117   else
1118     set_memory_partition (mp_p->var, mpt);
1119
1120   mp_p->partitioned_p = true;
1121
1122   mark_sym_for_renaming (mp_p->var);
1123   mark_sym_for_renaming (mpt);
1124
1125   return mpt;
1126 }
1127
1128
1129 /* Rewrite the alias set for TAG to use the newly created partitions.
1130    If TAG is NULL, rewrite the set of call-clobbered variables.
1131    NEW_ALIASES is a scratch bitmap to build the new set of aliases for
1132    TAG.  */
1133
1134 static void
1135 rewrite_alias_set_for (tree tag, bitmap new_aliases)
1136 {
1137   bitmap_iterator bi;
1138   unsigned i;
1139   tree mpt, sym;
1140
1141   EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, i, bi)
1142     {
1143       sym = referenced_var (i);
1144       mpt = memory_partition (sym);
1145       if (mpt)
1146         bitmap_set_bit (new_aliases, DECL_UID (mpt));
1147       else
1148         bitmap_set_bit (new_aliases, DECL_UID (sym));
1149     }
1150
1151   /* Rebuild the may-alias array for TAG.  */
1152   bitmap_copy (MTAG_ALIASES (tag), new_aliases);
1153 }
1154
1155
1156 /* Determine how many virtual operands can be saved by partitioning
1157    MP_P->VAR into MPT.  When a symbol S is thrown inside a partition
1158    P, every virtual operand that used to reference S will now
1159    reference P.  Whether it reduces the number of virtual operands
1160    depends on:
1161
1162    1- Direct references to S are never saved.  Instead of the virtual
1163       operand to S, we will now have a virtual operand to P.
1164
1165    2- Indirect references to S are reduced only for those memory tags
1166       holding S that already had other symbols partitioned into P.
1167       For instance, if a memory tag T has the alias set { a b S c },
1168       the first time we partition S into P, the alias set will become
1169       { a b P c }, so no virtual operands will be saved. However, if
1170       we now partition symbol 'c' into P, then the alias set for T
1171       will become { a b P }, so we will be saving one virtual operand
1172       for every indirect reference to 'c'.
1173
1174    3- Is S is call-clobbered, we save as many virtual operands as
1175       call/asm sites exist in the code, but only if other
1176       call-clobbered symbols have been grouped into P.  The first
1177       call-clobbered symbol that we group does not produce any
1178       savings.
1179
1180    MEM_REF_STATS points to CFUN's memory reference information.  */
1181
1182 static void
1183 estimate_vop_reduction (struct mem_ref_stats_d *mem_ref_stats,
1184                         mem_sym_stats_t mp_p, tree mpt)
1185 {
1186   unsigned i;
1187   bitmap_iterator bi;
1188   mem_sym_stats_t mpt_stats;
1189
1190   /* We should only get symbols with indirect references here.  */
1191   gcc_assert (mp_p->num_indirect_reads > 0 || mp_p->num_indirect_writes > 0);
1192
1193   /* Note that the only statistics we keep for MPT is the set of
1194      parent tags to know which memory tags have had alias members
1195      partitioned, and the indicator has_call_clobbered_vars.
1196      Reference counts are not important for MPT.  */
1197   mpt_stats = get_mem_sym_stats_for (mpt);
1198
1199   /* Traverse all the parent tags for MP_P->VAR.  For every tag T, if
1200      partition P is already grouping aliases of T, then reduce the
1201      number of virtual operands by the number of direct references
1202      to T.  */
1203   if (mp_p->parent_tags)
1204     {
1205       if (mpt_stats->parent_tags == NULL)
1206         mpt_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack);
1207
1208       EXECUTE_IF_SET_IN_BITMAP (mp_p->parent_tags, 0, i, bi)
1209         {
1210           if (bitmap_bit_p (mpt_stats->parent_tags, i))
1211             {
1212               /* Partition MPT is already partitioning symbols in the
1213                  alias set for TAG.  This means that we are now saving
1214                  1 virtual operand for every direct reference to TAG.  */
1215               tree tag = referenced_var (i);
1216               mem_sym_stats_t tag_stats = mem_sym_stats (cfun, tag);
1217               mem_ref_stats->num_vuses -= tag_stats->num_direct_reads;
1218               mem_ref_stats->num_vdefs -= tag_stats->num_direct_writes;
1219             }
1220           else
1221             {
1222               /* This is the first symbol in tag I's alias set that is
1223                  being grouped under MPT.  We will not save any
1224                  virtual operands this time, but record that MPT is
1225                  grouping a symbol from TAG's alias set so that the
1226                  next time we get the savings.  */
1227               bitmap_set_bit (mpt_stats->parent_tags, i);
1228             }
1229         }
1230     }
1231
1232   /* If MP_P->VAR is call-clobbered, and MPT is already grouping
1233      call-clobbered symbols, then we will save as many virtual
1234      operands as asm/call sites there are.  */
1235   if (is_call_clobbered (mp_p->var))
1236     {
1237       if (mpt_stats->has_call_clobbered_vars)
1238         mem_ref_stats->num_vdefs -= mem_ref_stats->num_call_sites
1239                                     + mem_ref_stats->num_asm_sites;
1240       else
1241         mpt_stats->has_call_clobbered_vars = true;
1242     }
1243 }
1244
1245
1246 /* Helper for compute_memory_partitions.  Transfer reference counts
1247    from pointers to their pointed-to sets.  Counters for pointers were
1248    computed by update_alias_info.  MEM_REF_STATS points to CFUN's
1249    memory reference information.  */
1250
1251 static void
1252 update_reference_counts (struct mem_ref_stats_d *mem_ref_stats)
1253 {
1254   unsigned i;
1255   bitmap_iterator bi;
1256   mem_sym_stats_t sym_stats;
1257
1258   for (i = 1; i < num_ssa_names; i++)
1259     {
1260       tree ptr;
1261       struct ptr_info_def *pi;
1262
1263       ptr = ssa_name (i);
1264       if (ptr
1265           && POINTER_TYPE_P (TREE_TYPE (ptr))
1266           && (pi = SSA_NAME_PTR_INFO (ptr)) != NULL
1267           && pi->is_dereferenced)
1268         {
1269           unsigned j;
1270           bitmap_iterator bj;
1271           tree tag;
1272           mem_sym_stats_t ptr_stats, tag_stats;
1273
1274           /* If PTR has flow-sensitive points-to information, use
1275              PTR's name tag, otherwise use the symbol tag associated
1276              with PTR's symbol.  */
1277           if (pi->name_mem_tag)
1278             tag = pi->name_mem_tag;
1279           else
1280             tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
1281
1282           ptr_stats = get_mem_sym_stats_for (ptr);
1283           tag_stats = get_mem_sym_stats_for (tag);
1284
1285           /* TAG has as many direct references as dereferences we
1286              found for its parent pointer.  */
1287           tag_stats->num_direct_reads += ptr_stats->num_direct_reads;
1288           tag_stats->num_direct_writes += ptr_stats->num_direct_writes;
1289
1290           /* All the dereferences of pointer PTR are considered direct
1291              references to PTR's memory tag (TAG).  In turn,
1292              references to TAG will become virtual operands for every
1293              symbol in TAG's alias set.  So, for every symbol ALIAS in
1294              TAG's alias set, add as many indirect references to ALIAS
1295              as direct references there are for TAG.  */
1296           if (MTAG_ALIASES (tag))
1297             EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, j, bj)
1298               {
1299                 tree alias = referenced_var (j);
1300                 sym_stats = get_mem_sym_stats_for (alias);
1301
1302                 /* All the direct references to TAG are indirect references
1303                    to ALIAS.  */
1304                 sym_stats->num_indirect_reads += ptr_stats->num_direct_reads;
1305                 sym_stats->num_indirect_writes += ptr_stats->num_direct_writes;
1306                 sym_stats->frequency_reads += ptr_stats->frequency_reads;
1307                 sym_stats->frequency_writes += ptr_stats->frequency_writes;
1308
1309                 /* Indicate that TAG is one of ALIAS's parent tags.  */
1310                 if (sym_stats->parent_tags == NULL)
1311                   sym_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack);
1312                 bitmap_set_bit (sym_stats->parent_tags, DECL_UID (tag));
1313               }
1314         }
1315     }
1316
1317   /* Call-clobbered symbols are indirectly written at every
1318      call/asm site.  */
1319   EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
1320     {
1321       tree sym = referenced_var (i);
1322       sym_stats = get_mem_sym_stats_for (sym);
1323       sym_stats->num_indirect_writes += mem_ref_stats->num_call_sites
1324                                         + mem_ref_stats->num_asm_sites;
1325     }
1326
1327   /* Addressable symbols are indirectly written at some ASM sites.
1328      Since only ASM sites that clobber memory actually affect
1329      addressable symbols, this is an over-estimation.  */
1330   EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun), 0, i, bi)
1331     {
1332       tree sym = referenced_var (i);
1333       sym_stats = get_mem_sym_stats_for (sym);
1334       sym_stats->num_indirect_writes += mem_ref_stats->num_asm_sites;
1335     }
1336 }
1337
1338
1339 /* Helper for compute_memory_partitions.  Add all memory symbols to
1340    *MP_INFO_P and compute the initial estimate for the total number of
1341    virtual operands needed.  MEM_REF_STATS points to CFUN's memory
1342    reference information.  On exit, *TAGS_P will contain the list of
1343    memory tags whose alias set need to be rewritten after
1344    partitioning.  */
1345
1346 static void
1347 build_mp_info (struct mem_ref_stats_d *mem_ref_stats,
1348                VEC(mem_sym_stats_t,heap) **mp_info_p,
1349                VEC(tree,heap) **tags_p)
1350 {
1351   tree var;
1352   referenced_var_iterator rvi;
1353
1354   FOR_EACH_REFERENCED_VAR (var, rvi)
1355     {
1356       mem_sym_stats_t sym_stats;
1357       tree old_mpt;
1358
1359       /* We are only interested in memory symbols other than MPTs.  */
1360       if (is_gimple_reg (var) || TREE_CODE (var) == MEMORY_PARTITION_TAG)
1361         continue;
1362
1363       /* Collect memory tags into the TAGS array so that we can
1364          rewrite their alias sets after partitioning.  */
1365       if (MTAG_P (var) && MTAG_ALIASES (var))
1366         VEC_safe_push (tree, heap, *tags_p, var);
1367
1368       /* Since we are going to re-compute partitions, any symbols that
1369          used to belong to a partition must be detached from it and
1370          marked for renaming.  */
1371       if ((old_mpt = memory_partition (var)) != NULL)
1372         {
1373           mark_sym_for_renaming (old_mpt);
1374           set_memory_partition (var, NULL_TREE);
1375           mark_sym_for_renaming (var);
1376         }
1377
1378       sym_stats = get_mem_sym_stats_for (var);
1379
1380       /* Add VAR's reference info to MP_INFO.  Note that the only
1381          symbols that make sense to partition are those that have
1382          indirect references.  If a symbol S is always directly
1383          referenced, partitioning it will not reduce the number of
1384          virtual operators.  The only symbols that are profitable to
1385          partition are those that belong to alias sets and/or are
1386          call-clobbered.  */
1387       if (sym_stats->num_indirect_reads > 0
1388           || sym_stats->num_indirect_writes > 0)
1389         VEC_safe_push (mem_sym_stats_t, heap, *mp_info_p, sym_stats);
1390
1391       /* Update the number of estimated VOPS.  Note that direct
1392          references to memory tags are always counted as indirect
1393          references to their alias set members, so if a memory tag has
1394          aliases, do not count its direct references to avoid double
1395          accounting.  */
1396       if (!MTAG_P (var) || !MTAG_ALIASES (var))
1397         {
1398           mem_ref_stats->num_vuses += sym_stats->num_direct_reads;
1399           mem_ref_stats->num_vdefs += sym_stats->num_direct_writes;
1400         }
1401
1402       mem_ref_stats->num_vuses += sym_stats->num_indirect_reads;
1403       mem_ref_stats->num_vdefs += sym_stats->num_indirect_writes;
1404     }
1405 }
1406
1407
1408 /* Compute memory partitions.  A memory partition (MPT) is an
1409    arbitrary grouping of memory symbols, such that references to one
1410    member of the group is considered a reference to all the members of
1411    the group.
1412
1413    As opposed to alias sets in memory tags, the grouping into
1414    partitions is completely arbitrary and only done to reduce the
1415    number of virtual operands.  The only rule that needs to be
1416    observed when creating memory partitions is that given two memory
1417    partitions MPT.i and MPT.j, they must not contain symbols in
1418    common.
1419
1420    Memory partitions are used when putting the program into Memory-SSA
1421    form.  In particular, in Memory-SSA PHI nodes are not computed for
1422    individual memory symbols.  They are computed for memory
1423    partitions.  This reduces the amount of PHI nodes in the SSA graph
1424    at the expense of precision (i.e., it makes unrelated stores affect
1425    each other).
1426
1427    However, it is possible to increase precision by changing this
1428    partitioning scheme.  For instance, if the partitioning scheme is
1429    such that get_mpt_for is the identity function (that is,
1430    get_mpt_for (s) = s), this will result in ultimate precision at the
1431    expense of huge SSA webs.
1432
1433    At the other extreme, a partitioning scheme that groups all the
1434    symbols in the same set results in minimal SSA webs and almost
1435    total loss of precision.
1436
1437    There partitioning heuristic uses three parameters to decide the
1438    order in which symbols are processed.  The list of symbols is
1439    sorted so that symbols that are more likely to be partitioned are
1440    near the top of the list:
1441
1442    - Execution frequency.  If a memory references is in a frequently
1443      executed code path, grouping it into a partition may block useful
1444      transformations and cause sub-optimal code generation.  So, the
1445      partition heuristic tries to avoid grouping symbols with high
1446      execution frequency scores.  Execution frequency is taken
1447      directly from the basic blocks where every reference is made (see
1448      update_mem_sym_stats_from_stmt), which in turn uses the
1449      profile guided machinery, so if the program is compiled with PGO
1450      enabled, more accurate partitioning decisions will be made.
1451
1452    - Number of references.  Symbols with few references in the code,
1453      are partitioned before symbols with many references.
1454
1455    - NO_ALIAS attributes.  Symbols with any of the NO_ALIAS*
1456      attributes are partitioned after symbols marked MAY_ALIAS.
1457
1458    Once the list is sorted, the partitioning proceeds as follows:
1459
1460    1- For every symbol S in MP_INFO, create a new memory partition MP,
1461       if necessary.  To avoid memory partitions that contain symbols
1462       from non-conflicting alias sets, memory partitions are
1463       associated to the memory tag that holds S in its alias set.  So,
1464       when looking for a memory partition for S, the memory partition
1465       associated with one of the memory tags holding S is chosen.  If
1466       none exists, a new one is created.
1467
1468    2- Add S to memory partition MP.
1469
1470    3- Reduce by 1 the number of VOPS for every memory tag holding S.
1471
1472    4- If the total number of VOPS is less than MAX_ALIASED_VOPS or the
1473       average number of VOPS per statement is less than
1474       AVG_ALIASED_VOPS, stop.  Otherwise, go to the next symbol in the
1475       list.  */
1476
1477 static void
1478 compute_memory_partitions (void)
1479 {
1480   tree tag;
1481   unsigned i;
1482   mem_sym_stats_t mp_p;
1483   VEC(mem_sym_stats_t,heap) *mp_info;
1484   bitmap new_aliases;
1485   VEC(tree,heap) *tags;
1486   struct mem_ref_stats_d *mem_ref_stats;
1487   int prev_max_aliased_vops;
1488
1489   mem_ref_stats = gimple_mem_ref_stats (cfun);
1490   gcc_assert (mem_ref_stats->num_vuses == 0 && mem_ref_stats->num_vdefs == 0);
1491
1492   if (mem_ref_stats->num_mem_stmts == 0)
1493     return;
1494
1495   timevar_push (TV_MEMORY_PARTITIONING);
1496
1497   mp_info = NULL;
1498   tags = NULL;
1499   prev_max_aliased_vops = MAX_ALIASED_VOPS;
1500
1501   /* Since we clearly cannot lower the number of virtual operators
1502      below the total number of memory statements in the function, we
1503      may need to adjust MAX_ALIASED_VOPS beforehand.  */
1504   if (MAX_ALIASED_VOPS < mem_ref_stats->num_mem_stmts)
1505     MAX_ALIASED_VOPS = mem_ref_stats->num_mem_stmts;
1506
1507   /* Update reference stats for all the pointed-to variables and
1508      memory tags.  */
1509   update_reference_counts (mem_ref_stats);
1510
1511   /* Add all the memory symbols to MP_INFO.  */
1512   build_mp_info (mem_ref_stats, &mp_info, &tags);
1513
1514   /* No partitions required if we are below the threshold.  */
1515   if (!need_to_partition_p (mem_ref_stats))
1516     {
1517       if (dump_file)
1518         fprintf (dump_file, "\nMemory partitioning NOT NEEDED for %s\n",
1519                  get_name (current_function_decl));
1520       goto done;
1521     }
1522
1523   /* Sort the MP_INFO array so that symbols that should be partitioned
1524      first are near the top of the list.  */
1525   sort_mp_info (mp_info);
1526
1527   if (dump_file)
1528     {
1529       fprintf (dump_file, "\nMemory partitioning NEEDED for %s\n\n",
1530                get_name (current_function_decl));
1531       fprintf (dump_file, "Memory symbol references before partitioning:\n");
1532       dump_mp_info (dump_file, mp_info);
1533     }
1534
1535   /* Create partitions for variables in MP_INFO until we have enough
1536      to lower the total number of VOPS below MAX_ALIASED_VOPS or if
1537      the average number of VOPS per statement is below
1538      AVG_ALIASED_VOPS.  */
1539   for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
1540     {
1541       tree mpt;
1542
1543       /* If we are below the threshold, stop.  */
1544       if (!need_to_partition_p (mem_ref_stats))
1545         break;
1546
1547       mpt = find_partition_for (mp_p);
1548       estimate_vop_reduction (mem_ref_stats, mp_p, mpt);
1549     }
1550
1551   /* After partitions have been created, rewrite alias sets to use
1552      them instead of the original symbols.  This way, if the alias set
1553      was computed as { a b c d e f }, and the subset { b e f } was
1554      grouped into partition MPT.3, then the new alias set for the tag
1555      will be  { a c d MPT.3 }.
1556
1557      Note that this is not strictly necessary.  The operand scanner
1558      will always check if a symbol belongs to a partition when adding
1559      virtual operands.  However, by reducing the size of the alias
1560      sets to be scanned, the work needed inside the operand scanner is
1561      significantly reduced.  */
1562   new_aliases = BITMAP_ALLOC (&alias_bitmap_obstack);
1563
1564   for (i = 0; VEC_iterate (tree, tags, i, tag); i++)
1565     {
1566       rewrite_alias_set_for (tag, new_aliases);
1567       bitmap_clear (new_aliases);
1568     }
1569
1570   BITMAP_FREE (new_aliases);
1571
1572   if (dump_file)
1573     {
1574       fprintf (dump_file, "\nMemory symbol references after partitioning:\n");
1575       dump_mp_info (dump_file, mp_info);
1576     }
1577
1578 done:
1579   /* Free allocated memory.  */
1580   VEC_free (mem_sym_stats_t, heap, mp_info);
1581   VEC_free (tree, heap, tags);
1582
1583   MAX_ALIASED_VOPS = prev_max_aliased_vops;
1584
1585   timevar_pop (TV_MEMORY_PARTITIONING);
1586 }
1587
1588
1589 /* Compute may-alias information for every variable referenced in function
1590    FNDECL.
1591
1592    Alias analysis proceeds in 3 main phases:
1593
1594    1- Points-to and escape analysis.
1595
1596    This phase walks the use-def chains in the SSA web looking for three
1597    things:
1598
1599         * Assignments of the form P_i = &VAR
1600         * Assignments of the form P_i = malloc()
1601         * Pointers and ADDR_EXPR that escape the current function.
1602
1603    The concept of 'escaping' is the same one used in the Java world.  When
1604    a pointer or an ADDR_EXPR escapes, it means that it has been exposed
1605    outside of the current function.  So, assignment to global variables,
1606    function arguments and returning a pointer are all escape sites, as are
1607    conversions between pointers and integers.
1608
1609    This is where we are currently limited.  Since not everything is renamed
1610    into SSA, we lose track of escape properties when a pointer is stashed
1611    inside a field in a structure, for instance.  In those cases, we are
1612    assuming that the pointer does escape.
1613
1614    We use escape analysis to determine whether a variable is
1615    call-clobbered.  Simply put, if an ADDR_EXPR escapes, then the variable
1616    is call-clobbered.  If a pointer P_i escapes, then all the variables
1617    pointed-to by P_i (and its memory tag) also escape.
1618
1619    2- Compute flow-sensitive aliases
1620
1621    We have two classes of memory tags.  Memory tags associated with the
1622    pointed-to data type of the pointers in the program.  These tags are
1623    called "symbol memory tag" (SMT).  The other class are those associated
1624    with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that
1625    when adding operands for an INDIRECT_REF *P_i, we will first check
1626    whether P_i has a name tag, if it does we use it, because that will have
1627    more precise aliasing information.  Otherwise, we use the standard symbol
1628    tag.
1629
1630    In this phase, we go through all the pointers we found in points-to
1631    analysis and create alias sets for the name memory tags associated with
1632    each pointer P_i.  If P_i escapes, we mark call-clobbered the variables
1633    it points to and its tag.
1634
1635
1636    3- Compute flow-insensitive aliases
1637
1638    This pass will compare the alias set of every symbol memory tag and
1639    every addressable variable found in the program.  Given a symbol
1640    memory tag SMT and an addressable variable V.  If the alias sets of
1641    SMT and V conflict (as computed by may_alias_p), then V is marked
1642    as an alias tag and added to the alias set of SMT.
1643
1644    For instance, consider the following function:
1645
1646             foo (int i)
1647             {
1648               int *p, a, b;
1649
1650               if (i > 10)
1651                 p = &a;
1652               else
1653                 p = &b;
1654
1655               *p = 3;
1656               a = b + 2;
1657               return *p;
1658             }
1659
1660    After aliasing analysis has finished, the symbol memory tag for pointer
1661    'p' will have two aliases, namely variables 'a' and 'b'.  Every time
1662    pointer 'p' is dereferenced, we want to mark the operation as a
1663    potential reference to 'a' and 'b'.
1664
1665             foo (int i)
1666             {
1667               int *p, a, b;
1668
1669               if (i_2 > 10)
1670                 p_4 = &a;
1671               else
1672                 p_6 = &b;
1673               # p_1 = PHI <p_4(1), p_6(2)>;
1674
1675               # a_7 = VDEF <a_3>;
1676               # b_8 = VDEF <b_5>;
1677               *p_1 = 3;
1678
1679               # a_9 = VDEF <a_7>
1680               # VUSE <b_8>
1681               a_9 = b_8 + 2;
1682
1683               # VUSE <a_9>;
1684               # VUSE <b_8>;
1685               return *p_1;
1686             }
1687
1688    In certain cases, the list of may aliases for a pointer may grow too
1689    large.  This may cause an explosion in the number of virtual operands
1690    inserted in the code.  Resulting in increased memory consumption and
1691    compilation time.
1692
1693    When the number of virtual operands needed to represent aliased
1694    loads and stores grows too large (configurable with option --param
1695    max-aliased-vops and --param avg-aliased-vops), alias sets are
1696    grouped to avoid severe compile-time slow downs and memory
1697    consumption. See compute_memory_partitions.  */
1698
1699 unsigned int
1700 compute_may_aliases (void)
1701 {
1702   struct alias_info *ai;
1703
1704   timevar_push (TV_TREE_MAY_ALIAS);
1705
1706   memset (&alias_stats, 0, sizeof (alias_stats));
1707
1708   /* Initialize aliasing information.  */
1709   ai = init_alias_info ();
1710
1711   /* For each pointer P_i, determine the sets of variables that P_i may
1712      point-to.  For every addressable variable V, determine whether the
1713      address of V escapes the current function, making V call-clobbered
1714      (i.e., whether &V is stored in a global variable or if its passed as a
1715      function call argument).  */
1716   compute_points_to_sets (ai);
1717
1718   /* Collect all pointers and addressable variables, compute alias sets,
1719      create memory tags for pointers and promote variables whose address is
1720      not needed anymore.  */
1721   setup_pointers_and_addressables (ai);
1722
1723   /* Compute type-based flow-insensitive aliasing for all the type
1724      memory tags.  */
1725   compute_flow_insensitive_aliasing (ai);
1726
1727   /* Compute flow-sensitive, points-to based aliasing for all the name
1728      memory tags.  */
1729   compute_flow_sensitive_aliasing (ai);
1730
1731   /* Compute call clobbering information.  */
1732   compute_call_clobbered (ai);
1733
1734   /* If the program makes no reference to global variables, but it
1735      contains a mixture of pure and non-pure functions, then we need
1736      to create use-def and def-def links between these functions to
1737      avoid invalid transformations on them.  */
1738   maybe_create_global_var ();
1739
1740   /* Compute memory partitions for every memory variable.  */
1741   compute_memory_partitions ();
1742
1743   /* Remove partitions with no symbols.  Partitions may end up with an
1744      empty MPT_SYMBOLS set if a previous round of alias analysis
1745      needed to partition more symbols.  Since we don't need those
1746      partitions anymore, remove them to free up the space.  */
1747   {
1748     tree mpt;
1749     unsigned i;
1750     VEC(tree,heap) *mpt_table;
1751
1752     mpt_table = gimple_ssa_operands (cfun)->mpt_table;
1753     i = 0;
1754     while (i < VEC_length (tree, mpt_table))
1755       {
1756         mpt = VEC_index (tree, mpt_table, i);
1757         if (MPT_SYMBOLS (mpt) == NULL)
1758           VEC_unordered_remove (tree, mpt_table, i);
1759         else
1760           i++;
1761       }
1762   }
1763
1764   /* Populate all virtual operands and newly promoted register operands.  */
1765   {
1766     block_stmt_iterator bsi;
1767     basic_block bb;
1768     FOR_EACH_BB (bb)
1769       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1770         update_stmt_if_modified (bsi_stmt (bsi));
1771   }
1772
1773   /* Debugging dumps.  */
1774   if (dump_file)
1775     {
1776       dump_mem_ref_stats (dump_file);
1777       dump_alias_info (dump_file);
1778       dump_points_to_info (dump_file);
1779
1780       if (dump_flags & TDF_STATS)
1781         dump_alias_stats (dump_file);
1782
1783       if (dump_flags & TDF_DETAILS)
1784         dump_referenced_vars (dump_file);
1785     }
1786
1787   /* Report strict aliasing violations.  */
1788   strict_aliasing_warning_backend ();
1789
1790   /* Deallocate memory used by aliasing data structures.  */
1791   delete_alias_info (ai);
1792
1793   if (need_ssa_update_p ())
1794     update_ssa (TODO_update_ssa);
1795
1796   timevar_pop (TV_TREE_MAY_ALIAS);
1797
1798   return 0;
1799 }
1800
1801 /* Data structure used to count the number of dereferences to PTR
1802    inside an expression.  */
1803 struct count_ptr_d
1804 {
1805   tree ptr;
1806   unsigned count;
1807 };
1808
1809
1810 /* Helper for count_uses_and_derefs.  Called by walk_tree to look for
1811    (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA.  */
1812
1813 static tree
1814 count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
1815 {
1816   struct count_ptr_d *count_p = (struct count_ptr_d *) data;
1817
1818   /* Do not walk inside ADDR_EXPR nodes.  In the expression &ptr->fld,
1819      pointer 'ptr' is *not* dereferenced, it is simply used to compute
1820      the address of 'fld' as 'ptr + offsetof(fld)'.  */
1821   if (TREE_CODE (*tp) == ADDR_EXPR)
1822     {
1823       *walk_subtrees = 0;
1824       return NULL_TREE;
1825     }
1826
1827   if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
1828     count_p->count++;
1829
1830   return NULL_TREE;
1831 }
1832
1833
1834 /* Count the number of direct and indirect uses for pointer PTR in
1835    statement STMT.  The number of direct uses is stored in
1836    *NUM_USES_P.  Indirect references are counted separately depending
1837    on whether they are store or load operations.  The counts are
1838    stored in *NUM_STORES_P and *NUM_LOADS_P.  */
1839
1840 void
1841 count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p,
1842                        unsigned *num_loads_p, unsigned *num_stores_p)
1843 {
1844   ssa_op_iter i;
1845   tree use;
1846
1847   *num_uses_p = 0;
1848   *num_loads_p = 0;
1849   *num_stores_p = 0;
1850
1851   /* Find out the total number of uses of PTR in STMT.  */
1852   FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
1853     if (use == ptr)
1854       (*num_uses_p)++;
1855
1856   /* Now count the number of indirect references to PTR.  This is
1857      truly awful, but we don't have much choice.  There are no parent
1858      pointers inside INDIRECT_REFs, so an expression like
1859      '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
1860      find all the indirect and direct uses of x_1 inside.  The only
1861      shortcut we can take is the fact that GIMPLE only allows
1862      INDIRECT_REFs inside the expressions below.  */
1863   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
1864       || (TREE_CODE (stmt) == RETURN_EXPR
1865           && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
1866       || TREE_CODE (stmt) == ASM_EXPR
1867       || TREE_CODE (stmt) == CALL_EXPR)
1868     {
1869       tree lhs, rhs;
1870
1871       if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1872         {
1873           lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1874           rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1875         }
1876       else if (TREE_CODE (stmt) == RETURN_EXPR)
1877         {
1878           tree e = TREE_OPERAND (stmt, 0);
1879           lhs = GIMPLE_STMT_OPERAND (e, 0);
1880           rhs = GIMPLE_STMT_OPERAND (e, 1);
1881         }
1882       else if (TREE_CODE (stmt) == ASM_EXPR)
1883         {
1884           lhs = ASM_OUTPUTS (stmt);
1885           rhs = ASM_INPUTS (stmt);
1886         }
1887       else
1888         {
1889           lhs = NULL_TREE;
1890           rhs = stmt;
1891         }
1892
1893       if (lhs
1894           && (TREE_CODE (lhs) == TREE_LIST
1895               || EXPR_P (lhs)
1896               || GIMPLE_STMT_P (lhs)))
1897         {
1898           struct count_ptr_d count;
1899           count.ptr = ptr;
1900           count.count = 0;
1901           walk_tree (&lhs, count_ptr_derefs, &count, NULL);
1902           *num_stores_p = count.count;
1903         }
1904
1905       if (rhs
1906           && (TREE_CODE (rhs) == TREE_LIST
1907               || EXPR_P (rhs)
1908               || GIMPLE_STMT_P (rhs)))
1909         {
1910           struct count_ptr_d count;
1911           count.ptr = ptr;
1912           count.count = 0;
1913           walk_tree (&rhs, count_ptr_derefs, &count, NULL);
1914           *num_loads_p = count.count;
1915         }
1916     }
1917
1918   gcc_assert (*num_uses_p >= *num_loads_p + *num_stores_p);
1919 }
1920
1921 /* Remove memory references stats for function FN.  */
1922
1923 void
1924 delete_mem_ref_stats (struct function *fn)
1925 {
1926   if (gimple_mem_ref_stats (fn)->mem_sym_stats)
1927     {
1928       free_alloc_pool (mem_sym_stats_pool);
1929       pointer_map_destroy (gimple_mem_ref_stats (fn)->mem_sym_stats);
1930     }
1931   gimple_mem_ref_stats (fn)->mem_sym_stats = NULL;
1932 }
1933
1934
1935 /* Initialize memory reference stats.  */
1936
1937 static void
1938 init_mem_ref_stats (void)
1939 {
1940   struct mem_ref_stats_d *mem_ref_stats = gimple_mem_ref_stats (cfun);
1941
1942   mem_sym_stats_pool = create_alloc_pool ("Mem sym stats",
1943                                           sizeof (struct mem_sym_stats_d),
1944                                           100);
1945   memset (mem_ref_stats, 0, sizeof (struct mem_ref_stats_d));
1946   mem_ref_stats->mem_sym_stats = pointer_map_create ();
1947 }
1948
1949
1950 /* Helper for init_alias_info.  Reset existing aliasing information.  */
1951
1952 static void
1953 reset_alias_info (void)
1954 {
1955   referenced_var_iterator rvi;
1956   tree var;
1957   unsigned i;
1958   bitmap active_nmts, all_nmts;
1959
1960   /* Clear the set of addressable variables.  We do not need to clear
1961      the TREE_ADDRESSABLE bit on every symbol because we are going to
1962      re-compute addressability here.  */
1963   bitmap_clear (gimple_addressable_vars (cfun));
1964
1965   active_nmts = BITMAP_ALLOC (&alias_bitmap_obstack);
1966   all_nmts = BITMAP_ALLOC (&alias_bitmap_obstack);
1967
1968   /* Clear flow-insensitive alias information from each symbol.  */
1969   FOR_EACH_REFERENCED_VAR (var, rvi)
1970     {
1971       if (is_gimple_reg (var))
1972         continue;
1973
1974       if (MTAG_P (var))
1975         MTAG_ALIASES (var) = NULL;
1976
1977       /* Memory partition information will be computed from scratch.  */
1978       if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
1979         MPT_SYMBOLS (var) = NULL;
1980
1981       /* Collect all the name tags to determine if we have any
1982          orphaned that need to be removed from the IL.  A name tag
1983          will be orphaned if it is not associated with any active SSA
1984          name.  */
1985       if (TREE_CODE (var) == NAME_MEMORY_TAG)
1986         bitmap_set_bit (all_nmts, DECL_UID (var));
1987
1988       /* Since we are about to re-discover call-clobbered
1989          variables, clear the call-clobbered flag.  Variables that
1990          are intrinsically call-clobbered (globals, local statics,
1991          etc) will not be marked by the aliasing code, so we can't
1992          remove them from CALL_CLOBBERED_VARS.
1993
1994          NB: STRUCT_FIELDS are still call clobbered if they are for a
1995          global variable, so we *don't* clear their call clobberedness
1996          just because they are tags, though we will clear it if they
1997          aren't for global variables.  */
1998       if (TREE_CODE (var) == NAME_MEMORY_TAG
1999           || TREE_CODE (var) == SYMBOL_MEMORY_TAG
2000           || TREE_CODE (var) == MEMORY_PARTITION_TAG
2001           || !is_global_var (var))
2002         clear_call_clobbered (var);
2003     }
2004
2005   /* Clear flow-sensitive points-to information from each SSA name.  */
2006   for (i = 1; i < num_ssa_names; i++)
2007     {
2008       tree name = ssa_name (i);
2009
2010       if (!name || !POINTER_TYPE_P (TREE_TYPE (name)))
2011         continue;
2012
2013       if (SSA_NAME_PTR_INFO (name))
2014         {
2015           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
2016
2017           /* Clear all the flags but keep the name tag to
2018              avoid creating new temporaries unnecessarily.  If
2019              this pointer is found to point to a subset or
2020              superset of its former points-to set, then a new
2021              tag will need to be created in create_name_tags.  */
2022           pi->pt_anything = 0;
2023           pi->pt_null = 0;
2024           pi->value_escapes_p = 0;
2025           pi->is_dereferenced = 0;
2026           if (pi->pt_vars)
2027             bitmap_clear (pi->pt_vars);
2028
2029           /* Add NAME's name tag to the set of active tags.  */
2030           if (pi->name_mem_tag)
2031             bitmap_set_bit (active_nmts, DECL_UID (pi->name_mem_tag));
2032         }
2033     }
2034
2035   /* Name memory tags that are no longer associated with an SSA name
2036      are considered stale and should be removed from the IL.  All the
2037      name tags that are in the set ALL_NMTS but not in ACTIVE_NMTS are
2038      considered stale and marked for renaming.  */
2039   bitmap_and_compl_into (all_nmts, active_nmts);
2040   mark_set_for_renaming (all_nmts);
2041
2042   BITMAP_FREE (all_nmts);
2043   BITMAP_FREE (active_nmts);
2044 }
2045
2046
2047 /* Initialize the data structures used for alias analysis.  */
2048
2049 static struct alias_info *
2050 init_alias_info (void)
2051 {
2052   struct alias_info *ai;
2053   referenced_var_iterator rvi;
2054   tree var;
2055
2056   ai = XCNEW (struct alias_info);
2057   ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
2058   sbitmap_zero (ai->ssa_names_visited);
2059   ai->processed_ptrs = VEC_alloc (tree, heap, 50);
2060   ai->written_vars = pointer_set_create ();
2061   ai->dereferenced_ptrs_store = pointer_set_create ();
2062   ai->dereferenced_ptrs_load = pointer_set_create ();
2063
2064   /* Clear out all memory reference stats.  */
2065   init_mem_ref_stats ();
2066
2067   /* If aliases have been computed before, clear existing information.  */
2068   if (gimple_aliases_computed_p (cfun))
2069     reset_alias_info ();
2070   else
2071     {
2072       /* If this is the first time we compute aliasing information,
2073          every non-register symbol will need to be put into SSA form
2074          (the initial SSA form only operates on GIMPLE registers).  */
2075       FOR_EACH_REFERENCED_VAR (var, rvi)
2076         if (!is_gimple_reg (var))
2077           mark_sym_for_renaming (var);
2078     }
2079
2080   /* Next time, we will need to reset alias information.  */
2081   cfun->gimple_df->aliases_computed_p = true;
2082   if (alias_bitmap_obstack.elements != NULL)
2083     bitmap_obstack_release (&alias_bitmap_obstack);
2084   bitmap_obstack_initialize (&alias_bitmap_obstack);
2085
2086   return ai;
2087 }
2088
2089
2090 /* Deallocate memory used by alias analysis.  */
2091
2092 static void
2093 delete_alias_info (struct alias_info *ai)
2094 {
2095   size_t i;
2096
2097   sbitmap_free (ai->ssa_names_visited);
2098
2099   VEC_free (tree, heap, ai->processed_ptrs);
2100
2101   for (i = 0; i < ai->num_addressable_vars; i++)
2102     free (ai->addressable_vars[i]);
2103   free (ai->addressable_vars);
2104
2105   for (i = 0; i < ai->num_pointers; i++)
2106     free (ai->pointers[i]);
2107   free (ai->pointers);
2108
2109   pointer_set_destroy (ai->written_vars);
2110   pointer_set_destroy (ai->dereferenced_ptrs_store);
2111   pointer_set_destroy (ai->dereferenced_ptrs_load);
2112   free (ai);
2113
2114   delete_mem_ref_stats (cfun);
2115   delete_points_to_sets ();
2116 }
2117
2118
2119 /* Used for hashing to identify pointer infos with identical
2120    pt_vars bitmaps.  */
2121
2122 static int
2123 eq_ptr_info (const void *p1, const void *p2)
2124 {
2125   const struct ptr_info_def *n1 = (const struct ptr_info_def *) p1;
2126   const struct ptr_info_def *n2 = (const struct ptr_info_def *) p2;
2127   return bitmap_equal_p (n1->pt_vars, n2->pt_vars);
2128 }
2129
2130 static hashval_t
2131 ptr_info_hash (const void *p)
2132 {
2133   const struct ptr_info_def *n = (const struct ptr_info_def *) p;
2134   return bitmap_hash (n->pt_vars);
2135 }
2136
2137
2138 /* Create name tags for all the pointers that have been dereferenced.
2139    We only create a name tag for a pointer P if P is found to point to
2140    a set of variables (so that we can alias them to *P) or if it is
2141    the result of a call to malloc (which means that P cannot point to
2142    anything else nor alias any other variable).
2143
2144    If two pointers P and Q point to the same set of variables, they
2145    are assigned the same name tag.  */
2146
2147 static void
2148 create_name_tags (void)
2149 {
2150   size_t i;
2151   VEC (tree, heap) *with_ptvars = NULL;
2152   tree ptr;
2153   htab_t ptr_hash;
2154
2155   /* Collect the list of pointers with a non-empty points to set.  */
2156   for (i = 1; i < num_ssa_names; i++)
2157     {
2158       tree ptr = ssa_name (i);
2159       struct ptr_info_def *pi;
2160
2161       if (!ptr
2162           || !POINTER_TYPE_P (TREE_TYPE (ptr))
2163           || !SSA_NAME_PTR_INFO (ptr))
2164         continue;
2165
2166       pi = SSA_NAME_PTR_INFO (ptr);
2167
2168       if (pi->pt_anything || !pi->is_dereferenced)
2169         {
2170           /* No name tags for pointers that have not been
2171              dereferenced or point to an arbitrary location.  */
2172           pi->name_mem_tag = NULL_TREE;
2173           continue;
2174         }
2175
2176       /* Set pt_anything on the pointers without pt_vars filled in so
2177          that they are assigned a symbol tag.  */
2178       if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
2179         VEC_safe_push (tree, heap, with_ptvars, ptr);
2180       else
2181         set_pt_anything (ptr);
2182     }
2183
2184   /* If we didn't find any pointers with pt_vars set, we're done.  */
2185   if (!with_ptvars)
2186     return;
2187
2188   ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL);
2189
2190   /* Now go through the pointers with pt_vars, and find a name tag
2191      with the same pt_vars as this pointer, or create one if one
2192      doesn't exist.  */
2193   for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++)
2194     {
2195       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2196       tree old_name_tag = pi->name_mem_tag;
2197       struct ptr_info_def **slot;
2198
2199       /* If PTR points to a set of variables, check if we don't
2200          have another pointer Q with the same points-to set before
2201          creating a tag.  If so, use Q's tag instead of creating a
2202          new one.
2203
2204          This is important for not creating unnecessary symbols
2205          and also for copy propagation.  If we ever need to
2206          propagate PTR into Q or vice-versa, we would run into
2207          problems if they both had different name tags because
2208          they would have different SSA version numbers (which
2209          would force us to take the name tags in and out of SSA).  */
2210       slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT);
2211       if (*slot)
2212         pi->name_mem_tag = (*slot)->name_mem_tag;
2213       else
2214         {
2215           *slot = pi;
2216
2217           /* If we didn't find a pointer with the same points-to set
2218              as PTR, create a new name tag if needed.  */
2219           if (pi->name_mem_tag == NULL_TREE)
2220             pi->name_mem_tag = get_nmt_for (ptr);
2221         }
2222
2223       /* If the new name tag computed for PTR is different than
2224          the old name tag that it used to have, then the old tag
2225          needs to be removed from the IL, so we mark it for
2226          renaming.  */
2227       if (old_name_tag && old_name_tag != pi->name_mem_tag)
2228         mark_sym_for_renaming (old_name_tag);
2229
2230       /* Inherit volatility from the pointed-to type.  */
2231       TREE_THIS_VOLATILE (pi->name_mem_tag)
2232         |= TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
2233
2234       /* Mark the new name tag for renaming.  */
2235       mark_sym_for_renaming (pi->name_mem_tag);
2236     }
2237
2238   htab_delete (ptr_hash);
2239
2240   VEC_free (tree, heap, with_ptvars);
2241 }
2242
2243
2244 /* Union the alias set SET into the may-aliases for TAG.  */
2245
2246 static void
2247 union_alias_set_into (tree tag, bitmap set)
2248 {
2249   bitmap ma = MTAG_ALIASES (tag);
2250
2251   if (bitmap_empty_p (set))
2252     return;
2253
2254   if (!ma)
2255     ma = MTAG_ALIASES (tag) = BITMAP_ALLOC (&alias_bitmap_obstack);
2256   bitmap_ior_into (ma, set);
2257 }
2258
2259
2260 /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
2261    the name memory tag (NMT) associated with P_i.  If P_i escapes, then its
2262    name tag and the variables it points-to are call-clobbered.  Finally, if
2263    P_i escapes and we could not determine where it points to, then all the
2264    variables in the same alias set as *P_i are marked call-clobbered.  This
2265    is necessary because we must assume that P_i may take the address of any
2266    variable in the same alias set.  */
2267
2268 static void
2269 compute_flow_sensitive_aliasing (struct alias_info *ai)
2270 {
2271   size_t i;
2272   tree ptr;
2273
2274   timevar_push (TV_FLOW_SENSITIVE);
2275   set_used_smts ();
2276
2277   for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
2278     {
2279       if (!find_what_p_points_to (ptr))
2280         set_pt_anything (ptr);
2281     }
2282
2283   create_name_tags ();
2284
2285   for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
2286     {
2287       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2288
2289       /* Set up aliasing information for PTR's name memory tag (if it has
2290          one).  Note that only pointers that have been dereferenced will
2291          have a name memory tag.  */
2292       if (pi->name_mem_tag && pi->pt_vars)
2293         {
2294           if (!bitmap_empty_p (pi->pt_vars))
2295             union_alias_set_into (pi->name_mem_tag, pi->pt_vars);
2296         }
2297     }
2298   timevar_pop (TV_FLOW_SENSITIVE);
2299 }
2300
2301
2302 /* Return TRUE if at least one symbol in TAG2's alias set is also
2303    present in TAG1's alias set.  */
2304
2305 static bool
2306 have_common_aliases_p (bitmap tag1aliases, bitmap tag2aliases)
2307 {
2308
2309   /* This is the old behavior of have_common_aliases_p, which is to
2310      return false if both sets are empty, or one set is and the other
2311      isn't.  */
2312   if (tag1aliases == NULL || tag2aliases == NULL)
2313     return false;
2314
2315   return bitmap_intersect_p (tag1aliases, tag2aliases);
2316 }
2317
2318 /* Compute type-based alias sets.  Traverse all the pointers and
2319    addressable variables found in setup_pointers_and_addressables.
2320
2321    For every pointer P in AI->POINTERS and addressable variable V in
2322    AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's symbol
2323    memory tag (SMT) if their alias sets conflict.  V is then marked as
2324    an aliased symbol so that the operand scanner knows that statements
2325    containing V have aliased operands.  */
2326
2327 static void
2328 compute_flow_insensitive_aliasing (struct alias_info *ai)
2329 {
2330   size_t i;
2331
2332   timevar_push (TV_FLOW_INSENSITIVE);
2333   /* For every pointer P, determine which addressable variables may alias
2334      with P's symbol memory tag.  */
2335   for (i = 0; i < ai->num_pointers; i++)
2336     {
2337       size_t j;
2338       struct alias_map_d *p_map = ai->pointers[i];
2339       tree tag = symbol_mem_tag (p_map->var);
2340       tree var;
2341
2342       for (j = 0; j < ai->num_addressable_vars; j++)
2343         {
2344           struct alias_map_d *v_map;
2345           var_ann_t v_ann;
2346           bool tag_stored_p, var_stored_p;
2347
2348           v_map = ai->addressable_vars[j];
2349           var = v_map->var;
2350           v_ann = var_ann (var);
2351
2352           /* Skip memory tags and variables that have never been
2353              written to.  We also need to check if the variables are
2354              call-clobbered because they may be overwritten by
2355              function calls.  */
2356           tag_stored_p = pointer_set_contains (ai->written_vars, tag)
2357                          || is_call_clobbered (tag);
2358           var_stored_p = pointer_set_contains (ai->written_vars, var)
2359                          || is_call_clobbered (var);
2360           if (!tag_stored_p && !var_stored_p)
2361             continue;
2362
2363           if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false))
2364             {
2365               /* Add VAR to TAG's may-aliases set.  */
2366               add_may_alias (tag, var);
2367             }
2368         }
2369     }
2370
2371   /* Since this analysis is based exclusively on symbols, it fails to
2372      handle cases where two pointers P and Q have different memory
2373      tags with conflicting alias set numbers but no aliased symbols in
2374      common.
2375
2376      For example, suppose that we have two memory tags SMT.1 and SMT.2
2377      such that
2378
2379                 may-aliases (SMT.1) = { a }
2380                 may-aliases (SMT.2) = { b }
2381
2382      and the alias set number of SMT.1 conflicts with that of SMT.2.
2383      Since they don't have symbols in common, loads and stores from
2384      SMT.1 and SMT.2 will seem independent of each other, which will
2385      lead to the optimizers making invalid transformations (see
2386      testsuite/gcc.c-torture/execute/pr15262-[12].c).
2387
2388      To avoid this problem, we do a final traversal of AI->POINTERS
2389      looking for pairs of pointers that have no aliased symbols in
2390      common and yet have conflicting alias set numbers.  */
2391   for (i = 0; i < ai->num_pointers; i++)
2392     {
2393       size_t j;
2394       struct alias_map_d *p_map1 = ai->pointers[i];
2395       tree tag1 = symbol_mem_tag (p_map1->var);
2396       bitmap may_aliases1 = MTAG_ALIASES (tag1);
2397
2398       for (j = 0; j < ai->num_pointers; j++)
2399         {
2400           struct alias_map_d *p_map2 = ai->pointers[j];
2401           tree tag2 = symbol_mem_tag (p_map2->var);
2402           bitmap may_aliases2 = may_aliases (tag2);
2403
2404           /* By convention tags don't alias themselves.  */
2405           if (tag1 == tag2)
2406             continue;
2407
2408           /* If the pointers may not point to each other, do nothing.  */
2409           if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
2410             continue;
2411
2412           /* The two pointers may alias each other.  If they already have
2413              symbols in common, do nothing.  */
2414           if (have_common_aliases_p (may_aliases1, may_aliases2))
2415             continue;
2416
2417           add_may_alias (tag1, tag2);
2418         }
2419     }
2420   timevar_pop (TV_FLOW_INSENSITIVE);
2421 }
2422
2423
2424 /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS.  */
2425
2426 static void
2427 create_alias_map_for (tree var, struct alias_info *ai)
2428 {
2429   struct alias_map_d *alias_map;
2430   alias_map = XCNEW (struct alias_map_d);
2431   alias_map->var = var;
2432   alias_map->set = get_alias_set (var);
2433   ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
2434 }
2435
2436
2437 /* Create memory tags for all the dereferenced pointers and build the
2438    ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias
2439    sets.  Based on the address escape and points-to information collected
2440    earlier, this pass will also clear the TREE_ADDRESSABLE flag from those
2441    variables whose address is not needed anymore.  */
2442
2443 static void
2444 setup_pointers_and_addressables (struct alias_info *ai)
2445 {
2446   size_t num_addressable_vars, num_pointers;
2447   referenced_var_iterator rvi;
2448   tree var;
2449   VEC (tree, heap) *varvec = NULL;
2450   safe_referenced_var_iterator srvi;
2451
2452   /* Size up the arrays ADDRESSABLE_VARS and POINTERS.  */
2453   num_addressable_vars = num_pointers = 0;
2454
2455   FOR_EACH_REFERENCED_VAR (var, rvi)
2456     {
2457       if (may_be_aliased (var))
2458         num_addressable_vars++;
2459
2460       if (POINTER_TYPE_P (TREE_TYPE (var)))
2461         {
2462           /* Since we don't keep track of volatile variables, assume that
2463              these pointers are used in indirect store operations.  */
2464           if (TREE_THIS_VOLATILE (var))
2465             pointer_set_insert (ai->dereferenced_ptrs_store, var);
2466
2467           num_pointers++;
2468         }
2469     }
2470
2471   /* Create ADDRESSABLE_VARS and POINTERS.  Note that these arrays are
2472      always going to be slightly bigger than we actually need them
2473      because some TREE_ADDRESSABLE variables will be marked
2474      non-addressable below and only pointers with unique symbol tags are
2475      going to be added to POINTERS.  */
2476   ai->addressable_vars = XCNEWVEC (struct alias_map_d *, num_addressable_vars);
2477   ai->pointers = XCNEWVEC (struct alias_map_d *, num_pointers);
2478   ai->num_addressable_vars = 0;
2479   ai->num_pointers = 0;
2480
2481   FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi)
2482     {
2483       /* Name memory tags already have flow-sensitive aliasing
2484          information, so they need not be processed by
2485          compute_flow_insensitive_aliasing.  Similarly, symbol memory
2486          tags are already accounted for when we process their
2487          associated pointer.
2488
2489          Structure fields, on the other hand, have to have some of this
2490          information processed for them, but it's pointless to mark them
2491          non-addressable (since they are fake variables anyway).  */
2492       if (MTAG_P (var))
2493         continue;
2494
2495       /* Remove the ADDRESSABLE flag from every addressable variable whose
2496          address is not needed anymore.  This is caused by the propagation
2497          of ADDR_EXPR constants into INDIRECT_REF expressions and the
2498          removal of dead pointer assignments done by the early scalar
2499          cleanup passes.  */
2500       if (TREE_ADDRESSABLE (var))
2501         {
2502           if (!bitmap_bit_p (gimple_addressable_vars (cfun), DECL_UID (var))
2503               && TREE_CODE (var) != RESULT_DECL
2504               && !is_global_var (var))
2505             {
2506               bool okay_to_mark = true;
2507
2508               /* Since VAR is now a regular GIMPLE register, we will need
2509                  to rename VAR into SSA afterwards.  */
2510               mark_sym_for_renaming (var);
2511
2512               /* The address of VAR is not needed, remove the
2513                  addressable bit, so that it can be optimized as a
2514                  regular variable.  */
2515               if (okay_to_mark)
2516                 {
2517                   /* The memory partition holding VAR will no longer
2518                      contain VAR, and statements referencing it will need
2519                      to be updated.  */
2520                   if (memory_partition (var))
2521                     mark_sym_for_renaming (memory_partition (var));
2522
2523                   mark_non_addressable (var);
2524                 }
2525             }
2526         }
2527
2528       /* Global variables and addressable locals may be aliased.  Create an
2529          entry in ADDRESSABLE_VARS for VAR.  */
2530       if (may_be_aliased (var))
2531         {
2532           create_alias_map_for (var, ai);
2533           mark_sym_for_renaming (var);
2534         }
2535
2536       /* Add pointer variables that have been dereferenced to the POINTERS
2537          array and create a symbol memory tag for them.  */
2538       if (POINTER_TYPE_P (TREE_TYPE (var)))
2539         {
2540           if ((pointer_set_contains (ai->dereferenced_ptrs_store, var)
2541                || pointer_set_contains (ai->dereferenced_ptrs_load, var)))
2542             {
2543               tree tag, old_tag;
2544               var_ann_t t_ann;
2545
2546               /* If pointer VAR still doesn't have a memory tag
2547                  associated with it, create it now or re-use an
2548                  existing one.  */
2549               tag = get_smt_for (var, ai);
2550               t_ann = var_ann (tag);
2551
2552               /* The symbol tag will need to be renamed into SSA
2553                  afterwards. Note that we cannot do this inside
2554                  get_smt_for because aliasing may run multiple times
2555                  and we only create symbol tags the first time.  */
2556               mark_sym_for_renaming (tag);
2557
2558               /* Similarly, if pointer VAR used to have another type
2559                  tag, we will need to process it in the renamer to
2560                  remove the stale virtual operands.  */
2561               old_tag = symbol_mem_tag (var);
2562               if (old_tag)
2563                 mark_sym_for_renaming (old_tag);
2564
2565               /* Associate the tag with pointer VAR.  */
2566               set_symbol_mem_tag (var, tag);
2567
2568               /* If pointer VAR has been used in a store operation,
2569                  then its memory tag must be marked as written-to.  */
2570               if (pointer_set_contains (ai->dereferenced_ptrs_store, var))
2571                 pointer_set_insert (ai->written_vars, tag);
2572             }
2573           else
2574             {
2575               /* The pointer has not been dereferenced.  If it had a
2576                  symbol memory tag, remove it and mark the old tag for
2577                  renaming to remove it out of the IL.  */
2578               tree tag = symbol_mem_tag (var);
2579               if (tag)
2580                 {
2581                   mark_sym_for_renaming (tag);
2582                   set_symbol_mem_tag (var, NULL_TREE);
2583                 }
2584             }
2585         }
2586     }
2587
2588   VEC_free (tree, heap, varvec);
2589 }
2590
2591
2592 /* Determine whether to use .GLOBAL_VAR to model call clobbering
2593    semantics.  If the function makes no references to global
2594    variables and contains at least one call to a non-pure function,
2595    then we need to mark the side-effects of the call using .GLOBAL_VAR
2596    to represent all possible global memory referenced by the callee.  */
2597
2598 static void
2599 maybe_create_global_var (void)
2600 {
2601   /* No need to create it, if we have one already.  */
2602   if (gimple_global_var (cfun) == NULL_TREE)
2603     {
2604       struct mem_ref_stats_d *stats = gimple_mem_ref_stats (cfun);
2605
2606       /* Create .GLOBAL_VAR if there are no call-clobbered
2607          variables and the program contains a mixture of pure/const
2608          and regular function calls.  This is to avoid the problem
2609          described in PR 20115:
2610
2611               int X;
2612               int func_pure (void) { return X; }
2613               int func_non_pure (int a) { X += a; }
2614               int foo ()
2615               {
2616                 int a = func_pure ();
2617                 func_non_pure (a);
2618                 a = func_pure ();
2619                 return a;
2620               }
2621
2622          Since foo() has no call-clobbered variables, there is
2623          no relationship between the calls to func_pure and
2624          func_non_pure.  Since func_pure has no side-effects, value
2625          numbering optimizations elide the second call to func_pure.
2626          So, if we have some pure/const and some regular calls in the
2627          program we create .GLOBAL_VAR to avoid missing these
2628          relations.  */
2629       if (bitmap_empty_p (gimple_call_clobbered_vars (cfun))
2630           && stats->num_call_sites > 0
2631           && stats->num_pure_const_call_sites > 0
2632           && stats->num_call_sites > stats->num_pure_const_call_sites)
2633         create_global_var ();
2634     }
2635 }
2636
2637
2638 /* Return TRUE if pointer PTR may point to variable VAR.
2639
2640    MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR
2641         This is needed because when checking for type conflicts we are
2642         interested in the alias set of the memory location pointed-to by
2643         PTR.  The alias set of PTR itself is irrelevant.
2644
2645    VAR_ALIAS_SET is the alias set for VAR.  */
2646
2647 static bool
2648 may_alias_p (tree ptr, alias_set_type mem_alias_set,
2649              tree var, alias_set_type var_alias_set,
2650              bool alias_set_only)
2651 {
2652   tree mem;
2653
2654   alias_stats.alias_queries++;
2655   alias_stats.simple_queries++;
2656
2657   /* By convention, a variable cannot alias itself.  */
2658   mem = symbol_mem_tag (ptr);
2659   if (mem == var)
2660     {
2661       alias_stats.alias_noalias++;
2662       alias_stats.simple_resolved++;
2663       return false;
2664     }
2665
2666   /* If -fargument-noalias-global is > 2, pointer arguments may
2667      not point to anything else.  */
2668   if (flag_argument_noalias > 2 && TREE_CODE (ptr) == PARM_DECL)
2669     {
2670       alias_stats.alias_noalias++;
2671       alias_stats.simple_resolved++;
2672       return false;
2673     }
2674
2675   /* If -fargument-noalias-global is > 1, pointer arguments may
2676      not point to global variables.  */
2677   if (flag_argument_noalias > 1 && is_global_var (var)
2678       && TREE_CODE (ptr) == PARM_DECL)
2679     {
2680       alias_stats.alias_noalias++;
2681       alias_stats.simple_resolved++;
2682       return false;
2683     }
2684
2685   /* If either MEM or VAR is a read-only global and the other one
2686      isn't, then PTR cannot point to VAR.  */
2687   if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var))
2688       || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem)))
2689     {
2690       alias_stats.alias_noalias++;
2691       alias_stats.simple_resolved++;
2692       return false;
2693     }
2694
2695   /* If the pointed to memory has alias set zero, or the pointer
2696      is ref-all, or the pointer decl is marked that no TBAA is to
2697      be applied, the MEM can alias VAR.  */
2698   if (mem_alias_set == 0
2699       || DECL_POINTER_ALIAS_SET (ptr) == 0
2700       || TYPE_REF_CAN_ALIAS_ALL (TREE_TYPE (ptr))
2701       || DECL_NO_TBAA_P (ptr))
2702     {
2703       alias_stats.alias_mayalias++;
2704       alias_stats.simple_resolved++;
2705       return true;
2706     }
2707
2708   gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG);
2709
2710   alias_stats.tbaa_queries++;
2711
2712   /* If the alias sets don't conflict then MEM cannot alias VAR.  */
2713   if (mem_alias_set != var_alias_set
2714       && !alias_set_subset_of (mem_alias_set, var_alias_set))
2715     {
2716       alias_stats.alias_noalias++;
2717       alias_stats.tbaa_resolved++;
2718       return false;
2719     }
2720
2721   /* If VAR is a record or union type, PTR cannot point into VAR
2722      unless there is some explicit address operation in the
2723      program that can reference a field of the type pointed-to by
2724      PTR.  This also assumes that the types of both VAR and PTR
2725      are contained within the compilation unit, and that there is
2726      no fancy addressing arithmetic associated with any of the
2727      types involved.  */
2728   if (mem_alias_set != 0 && var_alias_set != 0)
2729     {
2730       tree ptr_type = TREE_TYPE (ptr);
2731       tree var_type = TREE_TYPE (var);
2732
2733       /* The star count is -1 if the type at the end of the
2734          pointer_to chain is not a record or union type. */
2735       if (!alias_set_only
2736           && ipa_type_escape_star_count_of_interesting_type (var_type) >= 0)
2737         {
2738           int ptr_star_count = 0;
2739
2740           /* ipa_type_escape_star_count_of_interesting_type is a
2741              little too restrictive for the pointer type, need to
2742              allow pointers to primitive types as long as those
2743              types cannot be pointers to everything.  */
2744           while (POINTER_TYPE_P (ptr_type))
2745             {
2746               /* Strip the *s off.  */
2747               ptr_type = TREE_TYPE (ptr_type);
2748               ptr_star_count++;
2749             }
2750
2751           /* There does not appear to be a better test to see if
2752              the pointer type was one of the pointer to everything
2753              types.  */
2754           if (ptr_star_count > 0)
2755             {
2756               alias_stats.structnoaddress_queries++;
2757               if (ipa_type_escape_field_does_not_clobber_p (var_type,
2758                                                             TREE_TYPE (ptr)))
2759                 {
2760                   alias_stats.structnoaddress_resolved++;
2761                   alias_stats.alias_noalias++;
2762                   return false;
2763                 }
2764             }
2765           else if (ptr_star_count == 0)
2766             {
2767               /* If PTR_TYPE was not really a pointer to type, it cannot
2768                  alias.  */
2769               alias_stats.structnoaddress_queries++;
2770               alias_stats.structnoaddress_resolved++;
2771               alias_stats.alias_noalias++;
2772               return false;
2773             }
2774         }
2775     }
2776
2777   alias_stats.alias_mayalias++;
2778   return true;
2779 }
2780
2781
2782 /* Add ALIAS to the set of variables that may alias VAR.  */
2783
2784 static void
2785 add_may_alias (tree var, tree alias)
2786 {
2787   /* Don't allow self-referential aliases.  */
2788   gcc_assert (var != alias);
2789
2790   /* ALIAS must be addressable if it's being added to an alias set.  */
2791 #if 1
2792   TREE_ADDRESSABLE (alias) = 1;
2793 #else
2794   gcc_assert (may_be_aliased (alias));
2795 #endif
2796
2797   /* VAR must be a symbol or a name tag.  */
2798   gcc_assert (TREE_CODE (var) == SYMBOL_MEMORY_TAG
2799               || TREE_CODE (var) == NAME_MEMORY_TAG);
2800
2801   if (MTAG_ALIASES (var) == NULL)
2802     MTAG_ALIASES (var) = BITMAP_ALLOC (&alias_bitmap_obstack);
2803
2804   bitmap_set_bit (MTAG_ALIASES (var), DECL_UID (alias));
2805 }
2806
2807
2808 /* Mark pointer PTR as pointing to an arbitrary memory location.  */
2809
2810 static void
2811 set_pt_anything (tree ptr)
2812 {
2813   struct ptr_info_def *pi = get_ptr_info (ptr);
2814
2815   pi->pt_anything = 1;
2816   pi->pt_vars = NULL;
2817
2818   /* The pointer used to have a name tag, but we now found it pointing
2819      to an arbitrary location.  The name tag needs to be renamed and
2820      disassociated from PTR.  */
2821   if (pi->name_mem_tag)
2822     {
2823       mark_sym_for_renaming (pi->name_mem_tag);
2824       pi->name_mem_tag = NULL_TREE;
2825     }
2826 }
2827
2828
2829 /* Return true if STMT is an "escape" site from the current function.  Escape
2830    sites those statements which might expose the address of a variable
2831    outside the current function.  STMT is an escape site iff:
2832
2833         1- STMT is a function call, or
2834         2- STMT is an __asm__ expression, or
2835         3- STMT is an assignment to a non-local variable, or
2836         4- STMT is a return statement.
2837
2838    Return the type of escape site found, if we found one, or NO_ESCAPE
2839    if none.  */
2840
2841 enum escape_type
2842 is_escape_site (tree stmt)
2843 {
2844   tree call = get_call_expr_in (stmt);
2845   if (call != NULL_TREE)
2846     {
2847       if (!TREE_SIDE_EFFECTS (call))
2848         return ESCAPE_TO_PURE_CONST;
2849
2850       return ESCAPE_TO_CALL;
2851     }
2852   else if (TREE_CODE (stmt) == ASM_EXPR)
2853     return ESCAPE_TO_ASM;
2854   else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
2855     {
2856       tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
2857
2858       /* Get to the base of _REF nodes.  */
2859       if (TREE_CODE (lhs) != SSA_NAME)
2860         lhs = get_base_address (lhs);
2861
2862       /* If we couldn't recognize the LHS of the assignment, assume that it
2863          is a non-local store.  */
2864       if (lhs == NULL_TREE)
2865         return ESCAPE_UNKNOWN;
2866
2867       if (CONVERT_EXPR_P (GIMPLE_STMT_OPERAND (stmt, 1))
2868           || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR)
2869         {
2870           tree from
2871             = TREE_TYPE (TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 0));
2872           tree to = TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 1));
2873
2874           /* If the RHS is a conversion between a pointer and an integer, the
2875              pointer escapes since we can't track the integer.  */
2876           if (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to))
2877             return ESCAPE_BAD_CAST;
2878         }
2879
2880       /* If the LHS is an SSA name, it can't possibly represent a non-local
2881          memory store.  */
2882       if (TREE_CODE (lhs) == SSA_NAME)
2883         return NO_ESCAPE;
2884
2885       /* FIXME: LHS is not an SSA_NAME.  Even if it's an assignment to a
2886          local variables we cannot be sure if it will escape, because we
2887          don't have information about objects not in SSA form.  Need to
2888          implement something along the lines of
2889
2890          J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P.
2891          Midkiff, ``Escape analysis for java,'' in Proceedings of the
2892          Conference on Object-Oriented Programming Systems, Languages, and
2893          Applications (OOPSLA), pp. 1-19, 1999.  */
2894       return ESCAPE_STORED_IN_GLOBAL;
2895     }
2896   else if (TREE_CODE (stmt) == RETURN_EXPR)
2897     return ESCAPE_TO_RETURN;
2898
2899   return NO_ESCAPE;
2900 }
2901
2902 /* Create a new memory tag of type TYPE.
2903    Does NOT push it into the current binding.  */
2904
2905 tree
2906 create_tag_raw (enum tree_code code, tree type, const char *prefix)
2907 {
2908   tree tmp_var;
2909
2910   tmp_var = build_decl (code, create_tmp_var_name (prefix), type);
2911
2912   /* Make the variable writable.  */
2913   TREE_READONLY (tmp_var) = 0;
2914
2915   /* It doesn't start out global.  */
2916   MTAG_GLOBAL (tmp_var) = 0;
2917   TREE_STATIC (tmp_var) = 0;
2918   TREE_USED (tmp_var) = 1;
2919
2920   return tmp_var;
2921 }
2922
2923 /* Create a new memory tag of type TYPE.  If IS_TYPE_TAG is true, the tag
2924    is considered to represent all the pointers whose pointed-to types are
2925    in the same alias set class.  Otherwise, the tag represents a single
2926    SSA_NAME pointer variable.  */
2927
2928 static tree
2929 create_memory_tag (tree type, bool is_type_tag)
2930 {
2931   tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG,
2932                              type, (is_type_tag) ? "SMT" : "NMT");
2933
2934   /* By default, memory tags are local variables.  Alias analysis will
2935      determine whether they should be considered globals.  */
2936   DECL_CONTEXT (tag) = current_function_decl;
2937
2938   /* Memory tags are by definition addressable.  */
2939   TREE_ADDRESSABLE (tag) = 1;
2940
2941   set_symbol_mem_tag (tag, NULL_TREE);
2942
2943   /* Add the tag to the symbol table.  */
2944   add_referenced_var (tag);
2945
2946   return tag;
2947 }
2948
2949
2950 /* Create a name memory tag to represent a specific SSA_NAME pointer P_i.
2951    This is used if P_i has been found to point to a specific set of
2952    variables or to a non-aliased memory location like the address returned
2953    by malloc functions.  */
2954
2955 static tree
2956 get_nmt_for (tree ptr)
2957 {
2958   struct ptr_info_def *pi = get_ptr_info (ptr);
2959   tree tag = pi->name_mem_tag;
2960
2961   if (tag == NULL_TREE)
2962     tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false);
2963   return tag;
2964 }
2965
2966
2967 /* Return the symbol memory tag associated to pointer PTR.  A memory
2968    tag is an artificial variable that represents the memory location
2969    pointed-to by PTR.  It is used to model the effects of pointer
2970    de-references on addressable variables.
2971
2972    AI points to the data gathered during alias analysis.  This
2973    function populates the array AI->POINTERS.  */
2974
2975 static tree
2976 get_smt_for (tree ptr, struct alias_info *ai)
2977 {
2978   size_t i;
2979   tree tag;
2980   tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
2981   alias_set_type tag_set = get_alias_set (tag_type);
2982
2983   /* To avoid creating unnecessary memory tags, only create one memory tag
2984      per alias set class.  Note that it may be tempting to group
2985      memory tags based on conflicting alias sets instead of
2986      equivalence.  That would be wrong because alias sets are not
2987      necessarily transitive (as demonstrated by the libstdc++ test
2988      23_containers/vector/cons/4.cc).  Given three alias sets A, B, C
2989      such that conflicts (A, B) == true and conflicts (A, C) == true,
2990      it does not necessarily follow that conflicts (B, C) == true.  */
2991   for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
2992     {
2993       struct alias_map_d *curr = ai->pointers[i];
2994       tree curr_tag = symbol_mem_tag (curr->var);
2995       if (tag_set == curr->set)
2996         {
2997           tag = curr_tag;
2998           break;
2999         }
3000     }
3001
3002   /* If VAR cannot alias with any of the existing memory tags, create a new
3003      tag for PTR and add it to the POINTERS array.  */
3004   if (tag == NULL_TREE)
3005     {
3006       struct alias_map_d *alias_map;
3007
3008       /* If PTR did not have a symbol tag already, create a new SMT.*
3009          artificial variable representing the memory location
3010          pointed-to by PTR.  */
3011       tag = symbol_mem_tag (ptr);
3012       if (tag == NULL_TREE)
3013         tag = create_memory_tag (tag_type, true);
3014
3015       /* Add PTR to the POINTERS array.  Note that we are not interested in
3016          PTR's alias set.  Instead, we cache the alias set for the memory that
3017          PTR points to.  */
3018       alias_map = XCNEW (struct alias_map_d);
3019       alias_map->var = ptr;
3020       alias_map->set = tag_set;
3021       ai->pointers[ai->num_pointers++] = alias_map;
3022     }
3023
3024   /* If the pointed-to type is volatile, so is the tag.  */
3025   TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type);
3026
3027   /* Make sure that the symbol tag has the same alias set as the
3028      pointed-to type or at least accesses through the pointer will
3029      alias that set.  The latter can happen after the vectorizer
3030      created pointers of vector type.  */
3031   gcc_assert (tag_set == get_alias_set (tag)
3032               || alias_set_subset_of (tag_set, get_alias_set (tag)));
3033
3034   return tag;
3035 }
3036
3037
3038 /* Create GLOBAL_VAR, an artificial global variable to act as a
3039    representative of all the variables that may be clobbered by function
3040    calls.  */
3041
3042 static void
3043 create_global_var (void)
3044 {
3045   tree global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
3046                                 void_type_node);
3047   DECL_ARTIFICIAL (global_var) = 1;
3048   TREE_READONLY (global_var) = 0;
3049   DECL_EXTERNAL (global_var) = 1;
3050   TREE_STATIC (global_var) = 1;
3051   TREE_USED (global_var) = 1;
3052   DECL_CONTEXT (global_var) = NULL_TREE;
3053   TREE_THIS_VOLATILE (global_var) = 0;
3054   TREE_ADDRESSABLE (global_var) = 0;
3055
3056   create_var_ann (global_var);
3057   mark_call_clobbered (global_var, ESCAPE_UNKNOWN);
3058   add_referenced_var (global_var);
3059   mark_sym_for_renaming (global_var);
3060   cfun->gimple_df->global_var = global_var;
3061 }
3062
3063
3064 /* Dump alias statistics on FILE.  */
3065
3066 static void
3067 dump_alias_stats (FILE *file)
3068 {
3069   const char *funcname
3070     = lang_hooks.decl_printable_name (current_function_decl, 2);
3071   fprintf (file, "\nAlias statistics for %s\n\n", funcname);
3072   fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries);
3073   fprintf (file, "Total alias mayalias results:\t%u\n",
3074            alias_stats.alias_mayalias);
3075   fprintf (file, "Total alias noalias results:\t%u\n",
3076            alias_stats.alias_noalias);
3077   fprintf (file, "Total simple queries:\t%u\n",
3078            alias_stats.simple_queries);
3079   fprintf (file, "Total simple resolved:\t%u\n",
3080            alias_stats.simple_resolved);
3081   fprintf (file, "Total TBAA queries:\t%u\n",
3082            alias_stats.tbaa_queries);
3083   fprintf (file, "Total TBAA resolved:\t%u\n",
3084            alias_stats.tbaa_resolved);
3085   fprintf (file, "Total non-addressable structure type queries:\t%u\n",
3086            alias_stats.structnoaddress_queries);
3087   fprintf (file, "Total non-addressable structure type resolved:\t%u\n",
3088            alias_stats.structnoaddress_resolved);
3089 }
3090
3091
3092 /* Dump alias information on FILE.  */
3093
3094 void
3095 dump_alias_info (FILE *file)
3096 {
3097   size_t i;
3098   const char *funcname
3099     = lang_hooks.decl_printable_name (current_function_decl, 2);
3100   referenced_var_iterator rvi;
3101   tree var;
3102
3103   fprintf (file, "\nAlias information for %s\n\n", funcname);
3104
3105   dump_memory_partitions (file);
3106
3107   fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname);
3108
3109   fprintf (file, "Aliased symbols\n\n");
3110
3111   FOR_EACH_REFERENCED_VAR (var, rvi)
3112     {
3113       if (may_be_aliased (var))
3114         dump_variable (file, var);
3115     }
3116
3117   fprintf (file, "\nDereferenced pointers\n\n");
3118
3119   FOR_EACH_REFERENCED_VAR (var, rvi)
3120     if (symbol_mem_tag (var))
3121       dump_variable (file, var);
3122
3123   fprintf (file, "\nSymbol memory tags\n\n");
3124
3125   FOR_EACH_REFERENCED_VAR (var, rvi)
3126     {
3127       if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
3128         dump_variable (file, var);
3129     }
3130
3131   fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname);
3132
3133   fprintf (file, "SSA_NAME pointers\n\n");
3134   for (i = 1; i < num_ssa_names; i++)
3135     {
3136       tree ptr = ssa_name (i);
3137       struct ptr_info_def *pi;
3138
3139       if (ptr == NULL_TREE)
3140         continue;
3141
3142       pi = SSA_NAME_PTR_INFO (ptr);
3143       if (!SSA_NAME_IN_FREE_LIST (ptr)
3144           && pi
3145           && pi->name_mem_tag)
3146         dump_points_to_info_for (file, ptr);
3147     }
3148
3149   fprintf (file, "\nName memory tags\n\n");
3150
3151   FOR_EACH_REFERENCED_VAR (var, rvi)
3152     {
3153       if (TREE_CODE (var) == NAME_MEMORY_TAG)
3154         dump_variable (file, var);
3155     }
3156
3157   fprintf (file, "\n");
3158 }
3159
3160
3161 /* Dump alias information on stderr.  */
3162
3163 void
3164 debug_alias_info (void)
3165 {
3166   dump_alias_info (stderr);
3167 }
3168
3169
3170 /* Return the alias information associated with pointer T.  It creates a
3171    new instance if none existed.  */
3172
3173 struct ptr_info_def *
3174 get_ptr_info (tree t)
3175 {
3176   struct ptr_info_def *pi;
3177
3178   gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
3179
3180   pi = SSA_NAME_PTR_INFO (t);
3181   if (pi == NULL)
3182     {
3183       pi = GGC_CNEW (struct ptr_info_def);
3184       SSA_NAME_PTR_INFO (t) = pi;
3185     }
3186
3187   return pi;
3188 }
3189
3190
3191 /* Dump points-to information for SSA_NAME PTR into FILE.  */
3192
3193 void
3194 dump_points_to_info_for (FILE *file, tree ptr)
3195 {
3196   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
3197
3198   print_generic_expr (file, ptr, dump_flags);
3199
3200   if (pi)
3201     {
3202       if (pi->name_mem_tag)
3203         {
3204           fprintf (file, ", name memory tag: ");
3205           print_generic_expr (file, pi->name_mem_tag, dump_flags);
3206         }
3207
3208       if (pi->is_dereferenced)
3209         fprintf (file, ", is dereferenced");
3210
3211       if (pi->value_escapes_p)
3212         fprintf (file, ", its value escapes");
3213
3214       if (pi->pt_anything)
3215         fprintf (file, ", points-to anything");
3216
3217       if (pi->pt_null)
3218         fprintf (file, ", points-to NULL");
3219
3220       if (pi->pt_vars)
3221         {
3222           fprintf (file, ", points-to vars: ");
3223           dump_decl_set (file, pi->pt_vars);
3224         }
3225     }
3226
3227   fprintf (file, "\n");
3228 }
3229
3230
3231 /* Dump points-to information for VAR into stderr.  */
3232
3233 void
3234 debug_points_to_info_for (tree var)
3235 {
3236   dump_points_to_info_for (stderr, var);
3237 }
3238
3239
3240 /* Dump points-to information into FILE.  NOTE: This function is slow, as
3241    it needs to traverse the whole CFG looking for pointer SSA_NAMEs.  */
3242
3243 void
3244 dump_points_to_info (FILE *file)
3245 {
3246   basic_block bb;
3247   block_stmt_iterator si;
3248   ssa_op_iter iter;
3249   const char *fname =
3250     lang_hooks.decl_printable_name (current_function_decl, 2);
3251   referenced_var_iterator rvi;
3252   tree var;
3253
3254   fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname);
3255
3256   /* First dump points-to information for the default definitions of
3257      pointer variables.  This is necessary because default definitions are
3258      not part of the code.  */
3259   FOR_EACH_REFERENCED_VAR (var, rvi)
3260     {
3261       if (POINTER_TYPE_P (TREE_TYPE (var)))
3262         {
3263           tree def = gimple_default_def (cfun, var);
3264           if (def)
3265             dump_points_to_info_for (file, def);
3266         }
3267     }
3268
3269   /* Dump points-to information for every pointer defined in the program.  */
3270   FOR_EACH_BB (bb)
3271     {
3272       tree phi;
3273
3274       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3275         {
3276           tree ptr = PHI_RESULT (phi);
3277           if (POINTER_TYPE_P (TREE_TYPE (ptr)))
3278             dump_points_to_info_for (file, ptr);
3279         }
3280
3281         for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
3282           {
3283             tree stmt = bsi_stmt (si);
3284             tree def;
3285             FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3286               if (TREE_CODE (def) == SSA_NAME
3287                   && POINTER_TYPE_P (TREE_TYPE (def)))
3288                 dump_points_to_info_for (file, def);
3289           }
3290     }
3291
3292   fprintf (file, "\n");
3293 }
3294
3295
3296 /* Dump points-to info pointed to by PTO into STDERR.  */
3297
3298 void
3299 debug_points_to_info (void)
3300 {
3301   dump_points_to_info (stderr);
3302 }
3303
3304 /* Dump to FILE the list of variables that may be aliasing VAR.  */
3305
3306 void
3307 dump_may_aliases_for (FILE *file, tree var)
3308 {
3309   bitmap aliases;
3310
3311   aliases = MTAG_ALIASES (var);
3312   if (aliases)
3313     {
3314       bitmap_iterator bi;
3315       unsigned int i;
3316       tree al;
3317
3318       fprintf (file, "{ ");
3319       EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
3320         {
3321           al = referenced_var (i);
3322           print_generic_expr (file, al, dump_flags);
3323           fprintf (file, " ");
3324         }
3325       fprintf (file, "}");
3326     }
3327 }
3328
3329
3330 /* Dump to stderr the list of variables that may be aliasing VAR.  */
3331
3332 void
3333 debug_may_aliases_for (tree var)
3334 {
3335   dump_may_aliases_for (stderr, var);
3336 }
3337
3338
3339 /* Return true if VAR may be aliased.  */
3340
3341 bool
3342 may_be_aliased (tree var)
3343 {
3344   /* Obviously.  */
3345   if (TREE_ADDRESSABLE (var))
3346     return true;
3347
3348   /* Globally visible variables can have their addresses taken by other
3349      translation units.  */
3350   if (MTAG_P (var)
3351       && (MTAG_GLOBAL (var) || TREE_PUBLIC (var)))
3352     return true;
3353   else if (!MTAG_P (var)
3354            && (DECL_EXTERNAL (var) || TREE_PUBLIC (var)))
3355     return true;
3356
3357   /* Automatic variables can't have their addresses escape any other
3358      way.  This must be after the check for global variables, as
3359      extern declarations do not have TREE_STATIC set.  */
3360   if (!TREE_STATIC (var))
3361     return false;
3362
3363   /* If we're in unit-at-a-time mode, then we must have seen all
3364      occurrences of address-of operators, and so we can trust
3365      TREE_ADDRESSABLE.  Otherwise we can only be sure the variable
3366      isn't addressable if it's local to the current function.  */
3367   if (flag_unit_at_a_time)
3368     return false;
3369
3370   if (decl_function_context (var) == current_function_decl)
3371     return false;
3372
3373   return true;
3374 }
3375
3376 /* The following is based on code in add_stmt_operand to ensure that the
3377    same defs/uses/vdefs/vuses will be found after replacing a reference
3378    to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value
3379    is the address of var.  Return a memtag for the ptr, after adding the
3380    proper may_aliases to it (which are the aliases of var, if it has any,
3381    or var itself).  */
3382
3383 static tree
3384 add_may_alias_for_new_tag (tree tag, tree var)
3385 {
3386   bitmap aliases = NULL;
3387
3388   if (MTAG_P (var))
3389     aliases = may_aliases (var);
3390
3391   /* Case 1: |aliases| == 1  */
3392   if (aliases
3393       && bitmap_single_bit_set_p (aliases))
3394     {
3395       tree ali = referenced_var (bitmap_first_set_bit (aliases));
3396       if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG)
3397         return ali;
3398     }
3399
3400   /* Case 2: |aliases| == 0  */
3401   if (aliases == NULL)
3402     add_may_alias (tag, var);
3403   else
3404     {
3405       /* Case 3: |aliases| > 1  */
3406       union_alias_set_into (tag, aliases);
3407     }
3408   return tag;
3409 }
3410
3411 /* Create a new symbol tag for PTR.  Construct the may-alias list of
3412    this type tag so that it has the aliasing of VAR according to the
3413    location accessed by EXPR.
3414
3415    Note, the set of aliases represented by the new symbol tag are not
3416    marked for renaming.  */
3417
3418 void
3419 new_type_alias (tree ptr, tree var, tree expr)
3420 {
3421   tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
3422   tree tag;
3423   tree ali = NULL_TREE;
3424   HOST_WIDE_INT offset, size, maxsize;
3425   tree ref;
3426
3427   gcc_assert (symbol_mem_tag (ptr) == NULL_TREE);
3428   gcc_assert (!MTAG_P (var));
3429
3430   ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
3431   gcc_assert (ref);
3432
3433   tag = create_memory_tag (tag_type, true);
3434   set_symbol_mem_tag (ptr, tag);
3435
3436   ali = add_may_alias_for_new_tag (tag, var);
3437
3438   set_symbol_mem_tag (ptr, ali);
3439   MTAG_GLOBAL (tag) = is_global_var (var);
3440 }
3441
3442
3443 /* Reset the call_clobbered flags on our referenced vars.  In
3444    theory, this only needs to be done for globals.  */
3445
3446 static unsigned int
3447 reset_cc_flags (void)
3448 {
3449   tree var;
3450   referenced_var_iterator rvi;
3451
3452   FOR_EACH_REFERENCED_VAR (var, rvi)
3453     var_ann (var)->call_clobbered = false;
3454   return 0;
3455 }
3456
3457 struct gimple_opt_pass pass_reset_cc_flags =
3458 {
3459  {
3460   GIMPLE_PASS,
3461   NULL,          /* name */
3462   NULL,          /* gate */
3463   reset_cc_flags, /* execute */
3464   NULL,                  /* sub */
3465   NULL,                  /* next */
3466   0,                     /* static_pass_number */
3467   0,                     /* tv_id */
3468   PROP_referenced_vars |PROP_cfg, /* properties_required */
3469   0,                     /* properties_provided */
3470   0,                     /* properties_destroyed */
3471   0,                     /* todo_flags_start */
3472   0                      /* todo_flags_finish */
3473  }
3474 };
3475
3476
3477 /* A dummy pass to cause aliases to be computed via TODO_rebuild_alias.  */
3478
3479 struct gimple_opt_pass pass_build_alias =
3480 {
3481  {
3482   GIMPLE_PASS,
3483   "alias",                  /* name */
3484   NULL,                     /* gate */
3485   NULL,                     /* execute */
3486   NULL,                     /* sub */
3487   NULL,                     /* next */
3488   0,                        /* static_pass_number */
3489   0,                        /* tv_id */
3490   PROP_cfg | PROP_ssa,      /* properties_required */
3491   PROP_alias,               /* properties_provided */
3492   0,                        /* properties_destroyed */
3493   0,                        /* todo_flags_start */
3494   TODO_rebuild_alias | TODO_dump_func  /* todo_flags_finish */
3495  }
3496 };