gcc/tree-ssanames.c

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