gcc/tree-ssanames.c

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