gcc/tree-ssanames.c

   1 /* Generic routines for manipulating SSA_NAME expressions
   2    Copyright (C) 2003-2021 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "tree.h"
  25 #include "gimple.h"
  26 #include "tree-pass.h"
  27 #include "ssa.h"
  28 #include "gimple-iterator.h"
  29 #include "stor-layout.h"
  30 #include "tree-into-ssa.h"
  31 #include "tree-ssa.h"
  32 #include "cfgloop.h"
  33 #include "tree-scalar-evolution.h"
  34
  35 /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
  36    many of which may be thrown away shortly after their creation if jumps
  37    were threaded through PHI nodes.
  38
  39    While our garbage collection mechanisms will handle this situation, it
  40    is extremely wasteful to create nodes and throw them away, especially
  41    when the nodes can be reused.
  42
  43    For PR 8361, we can significantly reduce the number of nodes allocated
  44    and thus the total amount of memory allocated by managing SSA_NAMEs a
  45    little.  This additionally helps reduce the amount of work done by the
  46    garbage collector.  Similar results have been seen on a wider variety
  47    of tests (such as the compiler itself).
  48
  49    Right now we maintain our free list on a per-function basis.  It may
  50    or may not make sense to maintain the free list for the duration of
  51    a compilation unit.
  52
  53    External code should rely solely upon HIGHEST_SSA_VERSION and the
  54    externally defined functions.  External code should not know about
  55    the details of the free list management.
  56
  57    External code should also not assume the version number on nodes is
  58    monotonically increasing.  We reuse the version number when we
  59    reuse an SSA_NAME expression.  This helps keep arrays and bitmaps
  60    more compact.  */
  61
  62
  63 /* Version numbers with special meanings.  We start allocating new version
  64    numbers after the special ones.  */
  65 #define UNUSED_NAME_VERSION 0
  66
  67 unsigned int ssa_name_nodes_reused;
  68 unsigned int ssa_name_nodes_created;
  69
  70 #define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames
  71 #define FREE_SSANAMES_QUEUE(fun) (fun)->gimple_df->free_ssanames_queue
  72
  73
  74 /* Initialize management of SSA_NAMEs to default SIZE.  If SIZE is
  75    zero use default.  */
  76
  77 void
  78 init_ssanames (struct function *fn, int size)
  79 {
  80   if (!size)
  81     vec_alloc (SSANAMES (fn), 50);
  82   else
  83     vec_safe_reserve (SSANAMES (fn), size, true);
  84
  85   /* Version 0 is special, so reserve the first slot in the table.  Though
  86      currently unused, we may use version 0 in alias analysis as part of
  87      the heuristics used to group aliases when the alias sets are too
  88      large.
  89
  90      We use vec::quick_push here because we know that SSA_NAMES has at
  91      least 50 elements reserved in it.  */
  92   SSANAMES (fn)->quick_push (NULL_TREE);
  93   FREE_SSANAMES (fn) = NULL;
  94   FREE_SSANAMES_QUEUE (fn) = NULL;
  95
  96   fn->gimple_df->ssa_renaming_needed = 0;
  97   fn->gimple_df->rename_vops = 0;
  98 }
  99
 100 /* Finalize management of SSA_NAMEs.  */
 101
 102 void
 103 fini_ssanames (struct function *fn)
 104 {
 105   unsigned i;
 106   tree name;
 107   /* Some SSA names leak into global tree data structures so we can't simply
 108      ggc_free them.  But make sure to clear references to stmts since we now
 109      ggc_free the CFG itself.  */
 110   FOR_EACH_VEC_SAFE_ELT (SSANAMES (fn), i, name)
 111     if (name)
 112       SSA_NAME_DEF_STMT (name) = NULL;
 113   vec_free (SSANAMES (fn));
 114   vec_free (FREE_SSANAMES (fn));
 115   vec_free (FREE_SSANAMES_QUEUE (fn));
 116 }
 117
 118 /* Dump some simple statistics regarding the re-use of SSA_NAME nodes.  */
 119
 120 void
 121 ssanames_print_statistics (void)
 122 {
 123   fprintf (stderr, "%-32s" PRsa (11) "\n", "SSA_NAME nodes allocated:",
 124            SIZE_AMOUNT (ssa_name_nodes_created));
 125   fprintf (stderr, "%-32s" PRsa (11) "\n", "SSA_NAME nodes reused:",
 126            SIZE_AMOUNT (ssa_name_nodes_reused));
 127 }
 128
 129 /* Verify the state of the SSA_NAME lists.
 130
 131    There must be no duplicates on the free list.
 132    Every name on the free list must be marked as on the free list.
 133    Any name on the free list must not appear in the IL.
 134    No names can be leaked.  */
 135
 136 DEBUG_FUNCTION void
 137 verify_ssaname_freelists (struct function *fun)
 138 {
 139   if (!gimple_in_ssa_p (fun))
 140     return;
 141
 142   auto_bitmap names_in_il;
 143
 144   /* Walk the entire IL noting every SSA_NAME we see.  */
 145   basic_block bb;
 146   FOR_EACH_BB_FN (bb, fun)
 147     {
 148       tree t;
 149       /* First note the result and arguments of PHI nodes.  */
 150       for (gphi_iterator gsi = gsi_start_phis (bb);
 151            !gsi_end_p (gsi);
 152            gsi_next (&gsi))
 153         {
 154           gphi *phi = gsi.phi ();
 155           t = gimple_phi_result (phi);
 156           bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
 157
 158           for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
 159             {
 160               t = gimple_phi_arg_def (phi, i);
 161               if (TREE_CODE (t) == SSA_NAME)
 162                 bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
 163             }
 164         }
 165
 166       /* Then note the operands of each statement.  */
 167       for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
 168            !gsi_end_p (gsi);
 169            gsi_next (&gsi))
 170         {
 171           ssa_op_iter iter;
 172           gimple *stmt = gsi_stmt (gsi);
 173           FOR_EACH_SSA_TREE_OPERAND (t, stmt, iter, SSA_OP_ALL_OPERANDS)
 174             bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
 175         }
 176     }
 177
 178   /* Now walk the free list noting what we find there and verifying
 179      there are no duplicates.  */
 180   auto_bitmap names_in_freelists;
 181   if (FREE_SSANAMES (fun))
 182     {
 183       for (unsigned int i = 0; i < FREE_SSANAMES (fun)->length (); i++)
 184         {
 185           tree t = (*FREE_SSANAMES (fun))[i];
 186
 187           /* Verify that the name is marked as being in the free list.  */
 188           gcc_assert (SSA_NAME_IN_FREE_LIST (t));
 189
 190           /* Verify the name has not already appeared in the free list and
 191              note it in the list of names found in the free list.  */
 192           gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t)));
 193           bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t));
 194         }
 195     }
 196
 197   /* Similarly for the names in the pending free list.  */
 198   if (FREE_SSANAMES_QUEUE (fun))
 199     {
 200       for (unsigned int i = 0; i < FREE_SSANAMES_QUEUE (fun)->length (); i++)
 201         {
 202           tree t = (*FREE_SSANAMES_QUEUE (fun))[i];
 203
 204           /* Verify that the name is marked as being in the free list.  */
 205           gcc_assert (SSA_NAME_IN_FREE_LIST (t));
 206
 207           /* Verify the name has not already appeared in the free list and
 208              note it in the list of names found in the free list.  */
 209           gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t)));
 210           bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t));
 211         }
 212     }
 213
 214   /* If any name appears in both the IL and the freelists, then
 215      something horrible has happened.  */
 216   bool intersect_p = bitmap_intersect_p (names_in_il, names_in_freelists);
 217   gcc_assert (!intersect_p);
 218
 219   /* Names can be queued up for release if there is an ssa update
 220      pending.  Pretend we saw them in the IL.  */
 221   if (names_to_release)
 222     bitmap_ior_into (names_in_il, names_to_release);
 223
 224   /* Function splitting can "lose" SSA_NAMEs in an effort to ensure that
 225      debug/non-debug compilations have the same SSA_NAMEs.  So for each
 226      lost SSA_NAME, see if it's likely one from that wart.  These will always
 227      be marked as default definitions.  So we loosely assume that anything
 228      marked as a default definition isn't leaked by pretending they are
 229      in the IL.  */
 230   for (unsigned int i = UNUSED_NAME_VERSION + 1; i < num_ssa_names; i++)
 231     if (ssa_name (i) && SSA_NAME_IS_DEFAULT_DEF (ssa_name (i)))
 232       bitmap_set_bit (names_in_il, i);
 233
 234   unsigned int i;
 235   bitmap_iterator bi;
 236   auto_bitmap all_names;
 237   bitmap_set_range (all_names, UNUSED_NAME_VERSION + 1, num_ssa_names - 1);
 238   bitmap_ior_into (names_in_il, names_in_freelists);
 239
 240   /* Any name not mentioned in the IL and not in the feelists
 241      has been leaked.  */
 242   EXECUTE_IF_AND_COMPL_IN_BITMAP(all_names, names_in_il,
 243                                  UNUSED_NAME_VERSION + 1, i, bi)
 244     gcc_assert (!ssa_name (i));
 245 }
 246
 247 /* Move all SSA_NAMEs from FREE_SSA_NAMES_QUEUE to FREE_SSA_NAMES.
 248
 249    We do not, but should have a mode to verify the state of the SSA_NAMEs
 250    lists.  In particular at this point every name must be in the IL,
 251    on the free list or in the queue.  Anything else is an error.  */
 252
 253 void
 254 flush_ssaname_freelist (void)
 255 {
 256   /* If there were any SSA names released reset the SCEV cache.  */
 257   if (! vec_safe_is_empty (FREE_SSANAMES_QUEUE (cfun)))
 258     scev_reset_htab ();
 259   vec_safe_splice (FREE_SSANAMES (cfun), FREE_SSANAMES_QUEUE (cfun));
 260   vec_safe_truncate (FREE_SSANAMES_QUEUE (cfun), 0);
 261 }
 262
 263 /* Initialize SSA_NAME_IMM_USE_NODE of a SSA NAME.  */
 264
 265 void
 266 init_ssa_name_imm_use (tree name)
 267 {
 268   use_operand_p imm;
 269   imm = &(SSA_NAME_IMM_USE_NODE (name));
 270   imm->use = NULL;
 271   imm->prev = imm;
 272   imm->next = imm;
 273   imm->loc.ssa_name = name;
 274 }
 275
 276 /* Return an SSA_NAME node for variable VAR defined in statement STMT
 277    in function FN.  STMT may be an empty statement for artificial
 278    references (e.g., default definitions created when a variable is
 279    used without a preceding definition).  If VERISON is not zero then
 280    allocate the SSA name with that version.  */
 281
 282 tree
 283 make_ssa_name_fn (struct function *fn, tree var, gimple *stmt,
 284                   unsigned int version)
 285 {
 286   tree t;
 287   gcc_assert (VAR_P (var)
 288               || TREE_CODE (var) == PARM_DECL
 289               || TREE_CODE (var) == RESULT_DECL
 290               || (TYPE_P (var) && is_gimple_reg_type (var)));
 291
 292   /* Get the specified SSA name version.  */
 293   if (version != 0)
 294     {
 295       t = make_node (SSA_NAME);
 296       SSA_NAME_VERSION (t) = version;
 297       if (version >= SSANAMES (fn)->length ())
 298         vec_safe_grow_cleared (SSANAMES (fn), version + 1, true);
 299       gcc_assert ((*SSANAMES (fn))[version] == NULL);
 300       (*SSANAMES (fn))[version] = t;
 301       ssa_name_nodes_created++;
 302     }
 303   /* If our free list has an element, then use it.  */
 304   else if (!vec_safe_is_empty (FREE_SSANAMES (fn)))
 305     {
 306       t = FREE_SSANAMES (fn)->pop ();
 307       ssa_name_nodes_reused++;
 308
 309       /* The node was cleared out when we put it on the free list, so
 310          there is no need to do so again here.  */
 311       gcc_assert ((*SSANAMES (fn))[SSA_NAME_VERSION (t)] == NULL);
 312       (*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t;
 313     }
 314   else
 315     {
 316       t = make_node (SSA_NAME);
 317       SSA_NAME_VERSION (t) = SSANAMES (fn)->length ();
 318       vec_safe_push (SSANAMES (fn), t);
 319       ssa_name_nodes_created++;
 320     }
 321
 322   if (TYPE_P (var))
 323     {
 324       TREE_TYPE (t) = TYPE_MAIN_VARIANT (var);
 325       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE);
 326     }
 327   else
 328     {
 329       TREE_TYPE (t) = TREE_TYPE (var);
 330       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var);
 331     }
 332   SSA_NAME_DEF_STMT (t) = stmt;
 333   if (POINTER_TYPE_P (TREE_TYPE (t)))
 334     SSA_NAME_PTR_INFO (t) = NULL;
 335   else
 336     SSA_NAME_RANGE_INFO (t) = NULL;
 337
 338   SSA_NAME_IN_FREE_LIST (t) = 0;
 339   SSA_NAME_IS_DEFAULT_DEF (t) = 0;
 340   init_ssa_name_imm_use (t);
 341
 342   return t;
 343 }
 344
 345 /* Helper function for set_range_info.
 346
 347    Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name
 348    NAME.  */
 349
 350 void
 351 set_range_info_raw (tree name, enum value_range_kind range_type,
 352                     const wide_int_ref &min, const wide_int_ref &max)
 353 {
 354   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 355   gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
 356   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 357   unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
 358
 359   /* Allocate if not available.  */
 360   if (ri == NULL)
 361     {
 362       size_t size = (sizeof (range_info_def)
 363                      + trailing_wide_ints <3>::extra_size (precision));
 364       ri = static_cast<range_info_def *> (ggc_internal_alloc (size));
 365       ri->ints.set_precision (precision);
 366       SSA_NAME_RANGE_INFO (name) = ri;
 367       ri->set_nonzero_bits (wi::shwi (-1, precision));
 368     }
 369
 370   /* Record the range type.  */
 371   if (SSA_NAME_RANGE_TYPE (name) != range_type)
 372     SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
 373
 374   /* Set the values.  */
 375   ri->set_min (min);
 376   ri->set_max (max);
 377
 378   /* If it is a range, try to improve nonzero_bits from the min/max.  */
 379   if (range_type == VR_RANGE)
 380     {
 381       wide_int xorv = ri->get_min () ^ ri->get_max ();
 382       if (xorv != 0)
 383         xorv = wi::mask (precision - wi::clz (xorv), false, precision);
 384       ri->set_nonzero_bits (ri->get_nonzero_bits () & (ri->get_min () | xorv));
 385     }
 386 }
 387
 388 /* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name
 389    NAME while making sure we don't store useless range info.  */
 390
 391 void
 392 set_range_info (tree name, enum value_range_kind range_type,
 393                 const wide_int_ref &min, const wide_int_ref &max)
 394 {
 395   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 396
 397   /* A range of the entire domain is really no range at all.  */
 398   tree type = TREE_TYPE (name);
 399   if (min == wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type))
 400       && max == wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
 401     {
 402       range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 403       if (ri == NULL)
 404         return;
 405       if (ri->get_nonzero_bits () == -1)
 406         {
 407           ggc_free (ri);
 408           SSA_NAME_RANGE_INFO (name) = NULL;
 409           return;
 410         }
 411     }
 412
 413   set_range_info_raw (name, range_type, min, max);
 414 }
 415
 416 /* Store range information for NAME from a value_range.  */
 417
 418 void
 419 set_range_info (tree name, const value_range &vr)
 420 {
 421   wide_int min = wi::to_wide (vr.min ());
 422   wide_int max = wi::to_wide (vr.max ());
 423   set_range_info (name, vr.kind (), min, max);
 424 }
 425
 426 /* Set nonnull attribute to pointer NAME.  */
 427
 428 void
 429 set_ptr_nonnull (tree name)
 430 {
 431   gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
 432   struct ptr_info_def *pi = get_ptr_info (name);
 433   pi->pt.null = 0;
 434 }
 435
 436 /* Change non-zero bits bitmask of NAME.  */
 437
 438 void
 439 set_nonzero_bits (tree name, const wide_int_ref &mask)
 440 {
 441   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 442   if (SSA_NAME_RANGE_INFO (name) == NULL)
 443     {
 444       if (mask == -1)
 445         return;
 446       set_range_info_raw (name, VR_RANGE,
 447                           wi::to_wide (TYPE_MIN_VALUE (TREE_TYPE (name))),
 448                           wi::to_wide (TYPE_MAX_VALUE (TREE_TYPE (name))));
 449     }
 450   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 451   ri->set_nonzero_bits (mask);
 452 }
 453
 454 /* Return a widest_int with potentially non-zero bits in SSA_NAME
 455    NAME, the constant for INTEGER_CST, or -1 if unknown.  */
 456
 457 wide_int
 458 get_nonzero_bits (const_tree name)
 459 {
 460   if (TREE_CODE (name) == INTEGER_CST)
 461     return wi::to_wide (name);
 462
 463   /* Use element_precision instead of TYPE_PRECISION so complex and
 464      vector types get a non-zero precision.  */
 465   unsigned int precision = element_precision (TREE_TYPE (name));
 466   if (POINTER_TYPE_P (TREE_TYPE (name)))
 467     {
 468       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
 469       if (pi && pi->align)
 470         return wi::shwi (-(HOST_WIDE_INT) pi->align
 471                          | (HOST_WIDE_INT) pi->misalign, precision);
 472       return wi::shwi (-1, precision);
 473     }
 474
 475   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 476   if (!ri)
 477     return wi::shwi (-1, precision);
 478
 479   return ri->get_nonzero_bits ();
 480 }
 481
 482 /* Return TRUE is OP, an SSA_NAME has a range of values [0..1], false
 483    otherwise.
 484
 485    This can be because it is a boolean type, any unsigned integral
 486    type with a single bit of precision, or has known range of [0..1]
 487    via VRP analysis.  */
 488
 489 bool
 490 ssa_name_has_boolean_range (tree op)
 491 {
 492   gcc_assert (TREE_CODE (op) == SSA_NAME);
 493
 494   /* Boolean types always have a range [0..1].  */
 495   if (TREE_CODE (TREE_TYPE (op)) == BOOLEAN_TYPE)
 496     return true;
 497
 498   /* An integral type with a single bit of precision.  */
 499   if (INTEGRAL_TYPE_P (TREE_TYPE (op))
 500       && TYPE_UNSIGNED (TREE_TYPE (op))
 501       && TYPE_PRECISION (TREE_TYPE (op)) == 1)
 502     return true;
 503
 504   /* An integral type with more precision, but the object
 505      only takes on values [0..1] as determined by VRP
 506      analysis.  */
 507   if (INTEGRAL_TYPE_P (TREE_TYPE (op))
 508       && (TYPE_PRECISION (TREE_TYPE (op)) > 1)
 509       && wi::eq_p (get_nonzero_bits (op), 1))
 510     return true;
 511
 512   return false;
 513 }
 514
 515 /* We no longer need the SSA_NAME expression VAR, release it so that
 516    it may be reused.
 517
 518    Note it is assumed that no calls to make_ssa_name will be made
 519    until all uses of the ssa name are released and that the only
 520    use of the SSA_NAME expression is to check its SSA_NAME_VAR.  All
 521    other fields must be assumed clobbered.  */
 522
 523 void
 524 release_ssa_name_fn (struct function *fn, tree var)
 525 {
 526   if (!var)
 527     return;
 528
 529   /* Never release the default definition for a symbol.  It's a
 530      special SSA name that should always exist once it's created.  */
 531   if (SSA_NAME_IS_DEFAULT_DEF (var))
 532     return;
 533
 534   /* If VAR has been registered for SSA updating, don't remove it.
 535      After update_ssa has run, the name will be released.  */
 536   if (name_registered_for_update_p (var))
 537     {
 538       release_ssa_name_after_update_ssa (var);
 539       return;
 540     }
 541
 542   /* release_ssa_name can be called multiple times on a single SSA_NAME.
 543      However, it should only end up on our free list one time.   We
 544      keep a status bit in the SSA_NAME node itself to indicate it has
 545      been put on the free list.
 546
 547      Note that once on the freelist you cannot reference the SSA_NAME's
 548      defining statement.  */
 549   if (! SSA_NAME_IN_FREE_LIST (var))
 550     {
 551       int saved_ssa_name_version = SSA_NAME_VERSION (var);
 552       use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
 553
 554       if (MAY_HAVE_DEBUG_BIND_STMTS)
 555         insert_debug_temp_for_var_def (NULL, var);
 556
 557       if (flag_checking)
 558         verify_imm_links (stderr, var);
 559       while (imm->next != imm)
 560         delink_imm_use (imm->next);
 561
 562       (*SSANAMES (fn))[SSA_NAME_VERSION (var)] = NULL_TREE;
 563       memset (var, 0, tree_size (var));
 564
 565       imm->prev = imm;
 566       imm->next = imm;
 567       imm->loc.ssa_name = var;
 568
 569       /* First put back the right tree node so that the tree checking
 570          macros do not complain.  */
 571       TREE_SET_CODE (var, SSA_NAME);
 572
 573       /* Restore the version number.  */
 574       SSA_NAME_VERSION (var) = saved_ssa_name_version;
 575
 576       /* Note this SSA_NAME is now in the first list.  */
 577       SSA_NAME_IN_FREE_LIST (var) = 1;
 578
 579       /* Put in a non-NULL TREE_TYPE so dumping code will not ICE
 580          if it happens to come along a released SSA name and tries
 581          to inspect its type.  */
 582       TREE_TYPE (var) = error_mark_node;
 583
 584       /* And finally queue it so that it will be put on the free list.  */
 585       vec_safe_push (FREE_SSANAMES_QUEUE (fn), var);
 586     }
 587 }
 588
 589 /* If the alignment of the pointer described by PI is known, return true and
 590    store the alignment and the deviation from it into *ALIGNP and *MISALIGNP
 591    respectively.  Otherwise return false.  */
 592
 593 bool
 594 get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp,
 595                         unsigned int *misalignp)
 596 {
 597   if (pi->align)
 598     {
 599       *alignp = pi->align;
 600       *misalignp = pi->misalign;
 601       return true;
 602     }
 603   else
 604     return false;
 605 }
 606
 607 /* State that the pointer described by PI has unknown alignment.  */
 608
 609 void
 610 mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
 611 {
 612   pi->align = 0;
 613   pi->misalign = 0;
 614 }
 615
 616 /* Store the power-of-two byte alignment and the deviation from that
 617    alignment of pointer described by PI to ALIOGN and MISALIGN
 618    respectively.  */
 619
 620 void
 621 set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align,
 622                             unsigned int misalign)
 623 {
 624   gcc_checking_assert (align != 0);
 625   gcc_assert ((align & (align - 1)) == 0);
 626   gcc_assert ((misalign & ~(align - 1)) == 0);
 627
 628   pi->align = align;
 629   pi->misalign = misalign;
 630 }
 631
 632 /* If pointer described by PI has known alignment, increase its known
 633    misalignment by INCREMENT modulo its current alignment.  */
 634
 635 void
 636 adjust_ptr_info_misalignment (struct ptr_info_def *pi, poly_uint64 increment)
 637 {
 638   if (pi->align != 0)
 639     {
 640       increment += pi->misalign;
 641       if (!known_misalignment (increment, pi->align, &pi->misalign))
 642         {
 643           pi->align = known_alignment (increment);
 644           pi->misalign = 0;
 645         }
 646     }
 647 }
 648
 649 /* Return the alias information associated with pointer T.  It creates a
 650    new instance if none existed.  */
 651
 652 struct ptr_info_def *
 653 get_ptr_info (tree t)
 654 {
 655   struct ptr_info_def *pi;
 656
 657   gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
 658
 659   pi = SSA_NAME_PTR_INFO (t);
 660   if (pi == NULL)
 661     {
 662       pi = ggc_cleared_alloc<ptr_info_def> ();
 663       pt_solution_reset (&pi->pt);
 664       mark_ptr_info_alignment_unknown (pi);
 665       SSA_NAME_PTR_INFO (t) = pi;
 666     }
 667
 668   return pi;
 669 }
 670
 671
 672 /* Creates a new SSA name using the template NAME tobe defined by
 673    statement STMT in function FN.  */
 674
 675 tree
 676 copy_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
 677 {
 678   tree new_name;
 679
 680   if (SSA_NAME_VAR (name))
 681     new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt);
 682   else
 683     {
 684       new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt);
 685       SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name));
 686     }
 687
 688   return new_name;
 689 }
 690
 691
 692 /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
 693    the SSA name NAME.  */
 694
 695 void
 696 duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
 697 {
 698   struct ptr_info_def *new_ptr_info;
 699
 700   gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
 701   gcc_assert (!SSA_NAME_PTR_INFO (name));
 702
 703   if (!ptr_info)
 704     return;
 705
 706   new_ptr_info = ggc_alloc<ptr_info_def> ();
 707   *new_ptr_info = *ptr_info;
 708
 709   SSA_NAME_PTR_INFO (name) = new_ptr_info;
 710 }
 711
 712 /* Creates a duplicate of the range_info_def at RANGE_INFO of type
 713    RANGE_TYPE for use by the SSA name NAME.  */
 714 void
 715 duplicate_ssa_name_range_info (tree name, enum value_range_kind range_type,
 716                                struct range_info_def *range_info)
 717 {
 718   struct range_info_def *new_range_info;
 719
 720   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 721   gcc_assert (!SSA_NAME_RANGE_INFO (name));
 722
 723   if (!range_info)
 724     return;
 725
 726   unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
 727   size_t size = (sizeof (range_info_def)
 728                  + trailing_wide_ints <3>::extra_size (precision));
 729   new_range_info = static_cast<range_info_def *> (ggc_internal_alloc (size));
 730   memcpy (new_range_info, range_info, size);
 731
 732   gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
 733   SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
 734   SSA_NAME_RANGE_INFO (name) = new_range_info;
 735 }
 736
 737
 738
 739 /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT
 740    in function FN.  */
 741
 742 tree
 743 duplicate_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
 744 {
 745   tree new_name = copy_ssa_name_fn (fn, name, stmt);
 746   if (POINTER_TYPE_P (TREE_TYPE (name)))
 747     {
 748       struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
 749
 750       if (old_ptr_info)
 751         duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
 752     }
 753   else
 754     {
 755       struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name);
 756
 757       if (old_range_info)
 758         duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name),
 759                                        old_range_info);
 760     }
 761
 762   return new_name;
 763 }
 764
 765
 766 /* Reset all flow sensitive data on NAME such as range-info, nonzero
 767    bits and alignment.  */
 768
 769 void
 770 reset_flow_sensitive_info (tree name)
 771 {
 772   if (POINTER_TYPE_P (TREE_TYPE (name)))
 773     {
 774       /* points-to info is not flow-sensitive.  */
 775       if (SSA_NAME_PTR_INFO (name))
 776         {
 777           /* [E]VRP can derive context sensitive alignment info and
 778              non-nullness properties.  We must reset both.  */
 779           mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name));
 780           SSA_NAME_PTR_INFO (name)->pt.null = 1;
 781         }
 782     }
 783   else
 784     SSA_NAME_RANGE_INFO (name) = NULL;
 785 }
 786
 787 /* Clear all flow sensitive data from all statements and PHI definitions
 788    in BB.  */
 789
 790 void
 791 reset_flow_sensitive_info_in_bb (basic_block bb)
 792 {
 793   for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
 794        gsi_next (&gsi))
 795     {
 796       gimple *stmt = gsi_stmt (gsi);
 797       ssa_op_iter i;
 798       tree op;
 799       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
 800         reset_flow_sensitive_info (op);
 801     }
 802
 803   for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
 804        gsi_next (&gsi))
 805     {
 806       tree phi_def = gimple_phi_result (gsi.phi ());
 807       reset_flow_sensitive_info (phi_def);
 808     }
 809 }
 810
 811 /* Release all the SSA_NAMEs created by STMT.  */
 812
 813 void
 814 release_defs (gimple *stmt)
 815 {
 816   tree def;
 817   ssa_op_iter iter;
 818
 819   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 820     if (TREE_CODE (def) == SSA_NAME)
 821       release_ssa_name (def);
 822 }
 823
 824
 825 /* Replace the symbol associated with SSA_NAME with SYM.  */
 826
 827 void
 828 replace_ssa_name_symbol (tree ssa_name, tree sym)
 829 {
 830   SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym);
 831   TREE_TYPE (ssa_name) = TREE_TYPE (sym);
 832 }
 833
 834 /* Release the vector of free SSA_NAMEs and compact the vector of SSA_NAMEs
 835    that are live.  */
 836
 837 static void
 838 release_free_names_and_compact_live_names (function *fun)
 839 {
 840   unsigned i, j;
 841   int n = vec_safe_length (FREE_SSANAMES (fun));
 842
 843   /* Now release the freelist.  */
 844   vec_free (FREE_SSANAMES (fun));
 845
 846   /* And compact the SSA number space.  We make sure to not change the
 847      relative order of SSA versions.  */
 848   for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
 849     {
 850       tree name = ssa_name (i);
 851       if (name)
 852         {
 853           if (i != j)
 854             {
 855               SSA_NAME_VERSION (name) = j;
 856               (*fun->gimple_df->ssa_names)[j] = name;
 857             }
 858           j++;
 859         }
 860     }
 861   fun->gimple_df->ssa_names->truncate (j);
 862
 863   statistics_counter_event (fun, "SSA names released", n);
 864   statistics_counter_event (fun, "SSA name holes removed", i - j);
 865   if (dump_file)
 866     fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n",
 867              n, n * 100.0 / num_ssa_names, i - j);
 868 }
 869
 870 /* Return SSA names that are unused to GGC memory and compact the SSA
 871    version namespace.  This is used to keep footprint of compiler during
 872    interprocedural optimization.  */
 873
 874 namespace {
 875
 876 const pass_data pass_data_release_ssa_names =
 877 {
 878   GIMPLE_PASS, /* type */
 879   "release_ssa", /* name */
 880   OPTGROUP_NONE, /* optinfo_flags */
 881   TV_TREE_SSA_OTHER, /* tv_id */
 882   PROP_ssa, /* properties_required */
 883   0, /* properties_provided */
 884   0, /* properties_destroyed */
 885   TODO_remove_unused_locals, /* todo_flags_start */
 886   0, /* todo_flags_finish */
 887 };
 888
 889 class pass_release_ssa_names : public gimple_opt_pass
 890 {
 891 public:
 892   pass_release_ssa_names (gcc::context *ctxt)
 893     : gimple_opt_pass (pass_data_release_ssa_names, ctxt)
 894   {}
 895
 896   /* opt_pass methods: */
 897   virtual unsigned int execute (function *);
 898
 899 }; // class pass_release_ssa_names
 900
 901 unsigned int
 902 pass_release_ssa_names::execute (function *fun)
 903 {
 904   release_free_names_and_compact_live_names (fun);
 905   return 0;
 906 }
 907
 908 } // anon namespace
 909
 910 gimple_opt_pass *
 911 make_pass_release_ssa_names (gcc::context *ctxt)
 912 {
 913   return new pass_release_ssa_names (ctxt);
 914 }