gcc/tree-ssanames.c

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