gcc/tree-ssanames.c

   1 /* Generic routines for manipulating SSA_NAME expressions
   2    Copyright (C) 2003-2014 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 "tm.h"
  24 #include "tree.h"
  25 #include "stor-layout.h"
  26 #include "basic-block.h"
  27 #include "tree-ssa-alias.h"
  28 #include "internal-fn.h"
  29 #include "gimple-expr.h"
  30 #include "is-a.h"
  31 #include "gimple.h"
  32 #include "gimple-ssa.h"
  33 #include "tree-phinodes.h"
  34 #include "ssa-iterators.h"
  35 #include "stringpool.h"
  36 #include "tree-ssanames.h"
  37 #include "tree-into-ssa.h"
  38 #include "tree-ssa.h"
  39 #include "tree-pass.h"
  40
  41 /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
  42    many of which may be thrown away shortly after their creation if jumps
  43    were threaded through PHI nodes.
  44
  45    While our garbage collection mechanisms will handle this situation, it
  46    is extremely wasteful to create nodes and throw them away, especially
  47    when the nodes can be reused.
  48
  49    For PR 8361, we can significantly reduce the number of nodes allocated
  50    and thus the total amount of memory allocated by managing SSA_NAMEs a
  51    little.  This additionally helps reduce the amount of work done by the
  52    garbage collector.  Similar results have been seen on a wider variety
  53    of tests (such as the compiler itself).
  54
  55    Right now we maintain our free list on a per-function basis.  It may
  56    or may not make sense to maintain the free list for the duration of
  57    a compilation unit.
  58
  59    External code should rely solely upon HIGHEST_SSA_VERSION and the
  60    externally defined functions.  External code should not know about
  61    the details of the free list management.
  62
  63    External code should also not assume the version number on nodes is
  64    monotonically increasing.  We reuse the version number when we
  65    reuse an SSA_NAME expression.  This helps keep arrays and bitmaps
  66    more compact.  */
  67
  68
  69 /* Version numbers with special meanings.  We start allocating new version
  70    numbers after the special ones.  */
  71 #define UNUSED_NAME_VERSION 0
  72
  73 unsigned int ssa_name_nodes_reused;
  74 unsigned int ssa_name_nodes_created;
  75
  76 #define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames
  77
  78
  79 /* Initialize management of SSA_NAMEs to default SIZE.  If SIZE is
  80    zero use default.  */
  81
  82 void
  83 init_ssanames (struct function *fn, int size)
  84 {
  85   if (size < 50)
  86     size = 50;
  87
  88   vec_alloc (SSANAMES (fn), size);
  89
  90   /* Version 0 is special, so reserve the first slot in the table.  Though
  91      currently unused, we may use version 0 in alias analysis as part of
  92      the heuristics used to group aliases when the alias sets are too
  93      large.
  94
  95      We use vec::quick_push here because we know that SSA_NAMES has at
  96      least 50 elements reserved in it.  */
  97   SSANAMES (fn)->quick_push (NULL_TREE);
  98   FREE_SSANAMES (fn) = NULL;
  99
 100   fn->gimple_df->ssa_renaming_needed = 0;
 101   fn->gimple_df->rename_vops = 0;
 102 }
 103
 104 /* Finalize management of SSA_NAMEs.  */
 105
 106 void
 107 fini_ssanames (void)
 108 {
 109   vec_free (SSANAMES (cfun));
 110   vec_free (FREE_SSANAMES (cfun));
 111 }
 112
 113 /* Dump some simple statistics regarding the re-use of SSA_NAME nodes.  */
 114
 115 void
 116 ssanames_print_statistics (void)
 117 {
 118   fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
 119   fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
 120 }
 121
 122 /* Return an SSA_NAME node for variable VAR defined in statement STMT
 123    in function FN.  STMT may be an empty statement for artificial
 124    references (e.g., default definitions created when a variable is
 125    used without a preceding definition).  */
 126
 127 tree
 128 make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
 129 {
 130   tree t;
 131   use_operand_p imm;
 132
 133   gcc_assert (TREE_CODE (var) == VAR_DECL
 134               || TREE_CODE (var) == PARM_DECL
 135               || TREE_CODE (var) == RESULT_DECL
 136               || (TYPE_P (var) && is_gimple_reg_type (var)));
 137
 138   /* If our free list has an element, then use it.  */
 139   if (!vec_safe_is_empty (FREE_SSANAMES (fn)))
 140     {
 141       t = FREE_SSANAMES (fn)->pop ();
 142       if (GATHER_STATISTICS)
 143         ssa_name_nodes_reused++;
 144
 145       /* The node was cleared out when we put it on the free list, so
 146          there is no need to do so again here.  */
 147       gcc_assert ((*SSANAMES (fn))[SSA_NAME_VERSION (t)] == NULL);
 148       (*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t;
 149     }
 150   else
 151     {
 152       t = make_node (SSA_NAME);
 153       SSA_NAME_VERSION (t) = SSANAMES (fn)->length ();
 154       vec_safe_push (SSANAMES (fn), t);
 155       if (GATHER_STATISTICS)
 156         ssa_name_nodes_created++;
 157     }
 158
 159   if (TYPE_P (var))
 160     {
 161       TREE_TYPE (t) = var;
 162       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE);
 163     }
 164   else
 165     {
 166       TREE_TYPE (t) = TREE_TYPE (var);
 167       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var);
 168     }
 169   SSA_NAME_DEF_STMT (t) = stmt;
 170   if (POINTER_TYPE_P (TREE_TYPE (t)))
 171     SSA_NAME_PTR_INFO (t) = NULL;
 172   else
 173     SSA_NAME_RANGE_INFO (t) = NULL;
 174
 175   SSA_NAME_IN_FREE_LIST (t) = 0;
 176   SSA_NAME_IS_DEFAULT_DEF (t) = 0;
 177   imm = &(SSA_NAME_IMM_USE_NODE (t));
 178   imm->use = NULL;
 179   imm->prev = imm;
 180   imm->next = imm;
 181   imm->loc.ssa_name = t;
 182
 183   return t;
 184 }
 185
 186 /* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name NAME.  */
 187
 188 void
 189 set_range_info (tree name, enum value_range_type range_type, double_int min,
 190                 double_int max)
 191 {
 192   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 193   gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
 194   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 195
 196   /* Allocate if not available.  */
 197   if (ri == NULL)
 198     {
 199       ri = ggc_alloc_cleared_range_info_def ();
 200       SSA_NAME_RANGE_INFO (name) = ri;
 201       ri->nonzero_bits = double_int::mask (TYPE_PRECISION (TREE_TYPE (name)));
 202     }
 203
 204   /* Record the range type.  */
 205   if (SSA_NAME_RANGE_TYPE (name) != range_type)
 206     SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
 207
 208   /* Set the values.  */
 209   ri->min = min;
 210   ri->max = max;
 211
 212   /* If it is a range, try to improve nonzero_bits from the min/max.  */
 213   if (range_type == VR_RANGE)
 214     {
 215       int prec = TYPE_PRECISION (TREE_TYPE (name));
 216       double_int xorv;
 217
 218       min = min.zext (prec);
 219       max = max.zext (prec);
 220       xorv = min ^ max;
 221       if (xorv.high)
 222         xorv = double_int::mask (2 * HOST_BITS_PER_WIDE_INT
 223                                  - clz_hwi (xorv.high));
 224       else if (xorv.low)
 225         xorv = double_int::mask (HOST_BITS_PER_WIDE_INT
 226                                  - clz_hwi (xorv.low));
 227       ri->nonzero_bits = ri->nonzero_bits & (min | xorv);
 228     }
 229 }
 230
 231
 232 /* Gets range information MIN, MAX and returns enum value_range_type
 233    corresponding to tree ssa_name NAME.  enum value_range_type returned
 234    is used to determine if MIN and MAX are valid values.  */
 235
 236 enum value_range_type
 237 get_range_info (const_tree name, double_int *min, double_int *max)
 238 {
 239   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 240   gcc_assert (min && max);
 241   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 242
 243   /* Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs
 244      with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision.  */
 245   if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name)))
 246               > 2 * HOST_BITS_PER_WIDE_INT))
 247     return VR_VARYING;
 248
 249   *min = ri->min;
 250   *max = ri->max;
 251   return SSA_NAME_RANGE_TYPE (name);
 252 }
 253
 254 /* Change non-zero bits bitmask of NAME.  */
 255
 256 void
 257 set_nonzero_bits (tree name, double_int mask)
 258 {
 259   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 260   if (SSA_NAME_RANGE_INFO (name) == NULL)
 261     set_range_info (name, VR_RANGE,
 262                     tree_to_double_int (TYPE_MIN_VALUE (TREE_TYPE (name))),
 263                     tree_to_double_int (TYPE_MAX_VALUE (TREE_TYPE (name))));
 264   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 265   ri->nonzero_bits
 266     = mask & double_int::mask (TYPE_PRECISION (TREE_TYPE (name)));
 267 }
 268
 269 /* Return a double_int with potentially non-zero bits in SSA_NAME
 270    NAME, or double_int_minus_one if unknown.  */
 271
 272 double_int
 273 get_nonzero_bits (const_tree name)
 274 {
 275   if (POINTER_TYPE_P (TREE_TYPE (name)))
 276     {
 277       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
 278       if (pi && pi->align)
 279         {
 280           double_int al = double_int::from_uhwi (pi->align - 1);
 281           return ((double_int::mask (TYPE_PRECISION (TREE_TYPE (name))) & ~al)
 282                   | double_int::from_uhwi (pi->misalign));
 283         }
 284       return double_int_minus_one;
 285     }
 286
 287   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 288   if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name)))
 289               > 2 * HOST_BITS_PER_WIDE_INT))
 290     return double_int_minus_one;
 291
 292   return ri->nonzero_bits;
 293 }
 294
 295 /* We no longer need the SSA_NAME expression VAR, release it so that
 296    it may be reused.
 297
 298    Note it is assumed that no calls to make_ssa_name will be made
 299    until all uses of the ssa name are released and that the only
 300    use of the SSA_NAME expression is to check its SSA_NAME_VAR.  All
 301    other fields must be assumed clobbered.  */
 302
 303 void
 304 release_ssa_name_fn (struct function *fn, tree var)
 305 {
 306   if (!var)
 307     return;
 308
 309   /* Never release the default definition for a symbol.  It's a
 310      special SSA name that should always exist once it's created.  */
 311   if (SSA_NAME_IS_DEFAULT_DEF (var))
 312     return;
 313
 314   /* If VAR has been registered for SSA updating, don't remove it.
 315      After update_ssa has run, the name will be released.  */
 316   if (name_registered_for_update_p (var))
 317     {
 318       release_ssa_name_after_update_ssa (var);
 319       return;
 320     }
 321
 322   /* release_ssa_name can be called multiple times on a single SSA_NAME.
 323      However, it should only end up on our free list one time.   We
 324      keep a status bit in the SSA_NAME node itself to indicate it has
 325      been put on the free list.
 326
 327      Note that once on the freelist you can not reference the SSA_NAME's
 328      defining statement.  */
 329   if (! SSA_NAME_IN_FREE_LIST (var))
 330     {
 331       tree saved_ssa_name_var = SSA_NAME_VAR (var);
 332       int saved_ssa_name_version = SSA_NAME_VERSION (var);
 333       use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
 334
 335       if (MAY_HAVE_DEBUG_STMTS)
 336         insert_debug_temp_for_var_def (NULL, var);
 337
 338 #ifdef ENABLE_CHECKING
 339       verify_imm_links (stderr, var);
 340 #endif
 341       while (imm->next != imm)
 342         delink_imm_use (imm->next);
 343
 344       (*SSANAMES (fn))[SSA_NAME_VERSION (var)] = NULL_TREE;
 345       memset (var, 0, tree_size (var));
 346
 347       imm->prev = imm;
 348       imm->next = imm;
 349       imm->loc.ssa_name = var;
 350
 351       /* First put back the right tree node so that the tree checking
 352          macros do not complain.  */
 353       TREE_SET_CODE (var, SSA_NAME);
 354
 355       /* Restore the version number.  */
 356       SSA_NAME_VERSION (var) = saved_ssa_name_version;
 357
 358       /* Hopefully this can go away once we have the new incremental
 359          SSA updating code installed.  */
 360       SET_SSA_NAME_VAR_OR_IDENTIFIER (var, saved_ssa_name_var);
 361
 362       /* Note this SSA_NAME is now in the first list.  */
 363       SSA_NAME_IN_FREE_LIST (var) = 1;
 364
 365       /* And finally put it on the free list.  */
 366       vec_safe_push (FREE_SSANAMES (fn), var);
 367     }
 368 }
 369
 370 /* If the alignment of the pointer described by PI is known, return true and
 371    store the alignment and the deviation from it into *ALIGNP and *MISALIGNP
 372    respectively.  Otherwise return false.  */
 373
 374 bool
 375 get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp,
 376                         unsigned int *misalignp)
 377 {
 378   if (pi->align)
 379     {
 380       *alignp = pi->align;
 381       *misalignp = pi->misalign;
 382       return true;
 383     }
 384   else
 385     return false;
 386 }
 387
 388 /* State that the pointer described by PI has unknown alignment.  */
 389
 390 void
 391 mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
 392 {
 393   pi->align = 0;
 394   pi->misalign = 0;
 395 }
 396
 397 /* Store the the power-of-two byte alignment and the deviation from that
 398    alignment of pointer described by PI to ALIOGN and MISALIGN
 399    respectively.  */
 400
 401 void
 402 set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align,
 403                             unsigned int misalign)
 404 {
 405   gcc_checking_assert (align != 0);
 406   gcc_assert ((align & (align - 1)) == 0);
 407   gcc_assert ((misalign & ~(align - 1)) == 0);
 408
 409   pi->align = align;
 410   pi->misalign = misalign;
 411 }
 412
 413 /* If pointer described by PI has known alignment, increase its known
 414    misalignment by INCREMENT modulo its current alignment.  */
 415
 416 void
 417 adjust_ptr_info_misalignment (struct ptr_info_def *pi,
 418                               unsigned int increment)
 419 {
 420   if (pi->align != 0)
 421     {
 422       pi->misalign += increment;
 423       pi->misalign &= (pi->align - 1);
 424     }
 425 }
 426
 427 /* Return the alias information associated with pointer T.  It creates a
 428    new instance if none existed.  */
 429
 430 struct ptr_info_def *
 431 get_ptr_info (tree t)
 432 {
 433   struct ptr_info_def *pi;
 434
 435   gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
 436
 437   pi = SSA_NAME_PTR_INFO (t);
 438   if (pi == NULL)
 439     {
 440       pi = ggc_alloc_cleared_ptr_info_def ();
 441       pt_solution_reset (&pi->pt);
 442       mark_ptr_info_alignment_unknown (pi);
 443       SSA_NAME_PTR_INFO (t) = pi;
 444     }
 445
 446   return pi;
 447 }
 448
 449
 450 /* Creates a new SSA name using the template NAME tobe defined by
 451    statement STMT in function FN.  */
 452
 453 tree
 454 copy_ssa_name_fn (struct function *fn, tree name, gimple stmt)
 455 {
 456   tree new_name;
 457
 458   if (SSA_NAME_VAR (name))
 459     new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt);
 460   else
 461     {
 462       new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt);
 463       SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name));
 464     }
 465
 466   return new_name;
 467 }
 468
 469
 470 /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
 471    the SSA name NAME.  */
 472
 473 void
 474 duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
 475 {
 476   struct ptr_info_def *new_ptr_info;
 477
 478   gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
 479   gcc_assert (!SSA_NAME_PTR_INFO (name));
 480
 481   if (!ptr_info)
 482     return;
 483
 484   new_ptr_info = ggc_alloc_ptr_info_def ();
 485   *new_ptr_info = *ptr_info;
 486
 487   SSA_NAME_PTR_INFO (name) = new_ptr_info;
 488 }
 489
 490 /* Creates a duplicate of the range_info_def at RANGE_INFO of type
 491    RANGE_TYPE for use by the SSA name NAME.  */
 492 void
 493 duplicate_ssa_name_range_info (tree name, enum value_range_type range_type,
 494                                struct range_info_def *range_info)
 495 {
 496   struct range_info_def *new_range_info;
 497
 498   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 499   gcc_assert (!SSA_NAME_RANGE_INFO (name));
 500   gcc_assert (!SSA_NAME_ANTI_RANGE_P (name));
 501
 502   if (!range_info)
 503     return;
 504
 505   new_range_info = ggc_alloc_range_info_def ();
 506   *new_range_info = *range_info;
 507
 508   gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
 509   SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
 510   SSA_NAME_RANGE_INFO (name) = new_range_info;
 511 }
 512
 513
 514
 515 /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT
 516    in function FN.  */
 517
 518 tree
 519 duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt)
 520 {
 521   tree new_name = copy_ssa_name_fn (fn, name, stmt);
 522   if (POINTER_TYPE_P (TREE_TYPE (name)))
 523     {
 524       struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
 525
 526       if (old_ptr_info)
 527         duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
 528     }
 529   else
 530     {
 531       struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name);
 532
 533       if (old_range_info)
 534         duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name),
 535                                        old_range_info);
 536     }
 537
 538   return new_name;
 539 }
 540
 541
 542 /* Release all the SSA_NAMEs created by STMT.  */
 543
 544 void
 545 release_defs (gimple stmt)
 546 {
 547   tree def;
 548   ssa_op_iter iter;
 549
 550   /* Make sure that we are in SSA.  Otherwise, operand cache may point
 551      to garbage.  */
 552   gcc_assert (gimple_in_ssa_p (cfun));
 553
 554   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 555     if (TREE_CODE (def) == SSA_NAME)
 556       release_ssa_name (def);
 557 }
 558
 559
 560 /* Replace the symbol associated with SSA_NAME with SYM.  */
 561
 562 void
 563 replace_ssa_name_symbol (tree ssa_name, tree sym)
 564 {
 565   SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym);
 566   TREE_TYPE (ssa_name) = TREE_TYPE (sym);
 567 }
 568
 569 /* Return SSA names that are unused to GGC memory and compact the SSA
 570    version namespace.  This is used to keep footprint of compiler during
 571    interprocedural optimization.  */
 572 static unsigned int
 573 release_dead_ssa_names (void)
 574 {
 575   unsigned i, j;
 576   int n = vec_safe_length (FREE_SSANAMES (cfun));
 577
 578   /* Now release the freelist.  */
 579   vec_free (FREE_SSANAMES (cfun));
 580
 581   /* And compact the SSA number space.  We make sure to not change the
 582      relative order of SSA versions.  */
 583   for (i = 1, j = 1; i < cfun->gimple_df->ssa_names->length (); ++i)
 584     {
 585       tree name = ssa_name (i);
 586       if (name)
 587         {
 588           if (i != j)
 589             {
 590               SSA_NAME_VERSION (name) = j;
 591               (*cfun->gimple_df->ssa_names)[j] = name;
 592             }
 593           j++;
 594         }
 595     }
 596   cfun->gimple_df->ssa_names->truncate (j);
 597
 598   statistics_counter_event (cfun, "SSA names released", n);
 599   statistics_counter_event (cfun, "SSA name holes removed", i - j);
 600   if (dump_file)
 601     fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n",
 602              n, n * 100.0 / num_ssa_names, i - j);
 603   return 0;
 604 }
 605
 606 namespace {
 607
 608 const pass_data pass_data_release_ssa_names =
 609 {
 610   GIMPLE_PASS, /* type */
 611   "release_ssa", /* name */
 612   OPTGROUP_NONE, /* optinfo_flags */
 613   false, /* has_gate */
 614   true, /* has_execute */
 615   TV_TREE_SSA_OTHER, /* tv_id */
 616   PROP_ssa, /* properties_required */
 617   0, /* properties_provided */
 618   0, /* properties_destroyed */
 619   TODO_remove_unused_locals, /* todo_flags_start */
 620   0, /* todo_flags_finish */
 621 };
 622
 623 class pass_release_ssa_names : public gimple_opt_pass
 624 {
 625 public:
 626   pass_release_ssa_names (gcc::context *ctxt)
 627     : gimple_opt_pass (pass_data_release_ssa_names, ctxt)
 628   {}
 629
 630   /* opt_pass methods: */
 631   unsigned int execute () { return release_dead_ssa_names (); }
 632
 633 }; // class pass_release_ssa_names
 634
 635 } // anon namespace
 636
 637 gimple_opt_pass *
 638 make_pass_release_ssa_names (gcc::context *ctxt)
 639 {
 640   return new pass_release_ssa_names (ctxt);
 641 }