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